土木工程中的凝聚层次聚类算法应用研究

李潇潼 许左琳 马荣通 龙琦

摘  要：聚类算法技术有多种，可以有效应在土木工程中进行运用。本文研究的是凝聚层次聚类算法在土木工程中的应用，分析它的优缺点。

关键词：凝聚层次;聚类算法;簇;土木工程

1 凝聚层次聚类算法含义

层次聚类，顾名思义就是要一层一层地进行聚类，可以自下而上地把小的簇合并聚集，也可以从上至下地将大的簇进行分割。自下而上地进行聚类称为凝聚式层次聚类，自上而下地进行聚类称为分裂式层次聚类。

2 凝聚层次聚类在土木工程中的应用

3凝聚式层次聚类的主要问题

（1）缺乏全局目标函数

凝聚层次聚类不能为全局优化目标函数，在每一步合并时仅仅局部地确定哪些簇应当合并。

（2）处理不同大小簇的能力，关于处理待合并的簇对的相对大小，有两种方法解决：一是加权，就是不同簇中的点具有不同的权值;二是非加权，需要考虑每个簇的点数。

（3）合并决策

对于合并两个簇，凝聚层次聚类算法可以使用所有点的对趋向于作出最优局部决策。但是，一旦进行簇合并，就不能撤销，这阻碍了局部最优标准变成全局最优标准的情况。

4优点与缺点

层次聚类能产生较高质量的聚类;有些使用这种算法是因为基本应用需要层次结构。但就计算量和存储需求而言，凝聚式层次聚类算法是昂贵的。

基本凝聚式层次聚类算法使用鄰近度矩阵，这需要存储m2/2个邻近度（假定邻近度矩阵式对称的），其中m是数据点的个数。记录簇所需要的空间正比于簇的个数为m-1，不包括单点簇。因此总的空间复杂度为O（m2）。层次聚类所需要的总时间为O（m2logm）。

参考文献

[1]  姚玉钦 李金广 河北大学学报（自然科学版）[D] 2009-4

[2]  黄蕾 数据流环境下的聚类挖掘研究[D] 华中科技大学 2007

[3]  李柯 基于用户访问矩阵的网页推荐模型研究[D] 江苏大学 2010