聚类分析算法改进及其在隧道病害分析中的应用研究
丁小兵
（上海工程技术大学 城市轨道交通学院 201620）
学科分类与代码：620. 2030 中图分类号：X92,U4 文献标识码：A
摘要：在学习和研究经典聚类分析算法的基础上，对k-means算法进行改进，得到MK-means改进算法。随机选取初始点，运算后会产生不同的聚类结果，把基于图论中最小支撑树思想应用到算法改进中，通过最小支撑树求得最小圈，产生k个初始聚类中心，由达到一定初始聚类阈值的点开始聚类，聚类效果更优，有效克服随机选取初始点的缺点。把改进的算法应用到地铁隧道病害分析评价中，准确划分隧道病害等级，有针对地提出防治措施，具有一定的实际应用价值。
关键词：聚类分析；模糊聚类；数据挖掘；算法改进
Improved Clustering analysis Algorithm and
its Application in the tunnel disease
(Shanghai University of Engineering Science College of
Urban Rail Transportation，Shanghai 201620 China)
Abstract: Study in the classical algorithm based on cluster analysis, try to
improve k-means algorithm,and get the MK-means Algorithm.If we randomly select
initial point iteration,that each operation will produce different clustering
results, based on the minimum spanning tree of graph theory, by calculating the
minimum spanning tree to get the minimum cycle, resulting in the beginning of
k- start cluster center, up to a certain point of the initial clustering
threshold start clustering, the result is better, and of some practical value.
Key
words: cluster analysis; fuzzy clustering; data
mining; Algorithm improvement
1、引言
隧道病害关系到铁路、公路的正常运行，据统计隧道病害的种类多达50种甚至上百种之多，如何有针对行的发现隧道病害，采取措施预防和整治关系到人民出行安全和社会的稳定。目前隧道病害处理方法多种多样，大都采用逐个病害排查，浪费时间，人力资源等。本文在深入研究经典算法基础上提出一种改进算法，通过基于最小支撑树的聚类算法的改进，采用改进的模糊聚类算法以及病害等级评价方法，对隧道的病害检测数据进行聚类分析，得出聚类结果，对隧道病害提出若干整改意见和建议，为隧道病害预防和整治提供有实际应用意义的参考。
2、k-均值算法
k-均值算法以类内平方误差和函数为目标函数，用户事先指定k个划分，通过梯度下降法迭代优化目标函数，使目标函数值最小[1]。该算法对于聚类个数k而言，本质上是一种枚举法。而k-均值算法又是硬划分的一种，每个划分至少包含一个对象，每个对象必须只属于一个划分[2]。
假设将n个样本X={x1,x2, ...,xn}划分为k个类，ni表示第i类中所包含的样本个数，
X，表示第i类的中心，则uij有如下定义和性质[3]：
1，如果第j个样本属于第i类
0，其他
，j=1,2,...,n；
，i=1,2, ...,k；
，i=1,2, ...,k；
第i类的类内平方误差为：
。
目标函数表示为：
，通过迭代，使得J(u)取得最小值：J(u*)=min{J(u)}，从而找到最优化uij*。
针对k-均值算法，当聚类内部密集，且各聚类之间区别很明显时，该算法的效果较好[4]。
3、改进的聚类算法MK-means算法
在研究经典算法的基础上，对k-means算法进行改进，提出MK-means (Mended K-Means)算法。在标准的k-均值算法中，初始点的选取是随机的。基于随机选取的初始点进行迭代运算，每次运行k-均值算法都会产生不同的聚类结果。而MK-means算法基于图论中最小支撑树的思想，通过求最小支撑树得到最小圈，产生k个初始聚类中心，得到更好的聚类结果。将该改进的算法用到隧道病害划分与预防中，具有很好的准确性和操作性，MK-means算法能够优化k-均值算法的性能。
3.1 MK-means算法
设连通图G=(V,E)，每一边e=[vi,vj]有一个非负权w(e)=wij，wij≥0。
定义1：如果T=(V,E’)是G的一个支撑树，定义E’中所有边的权值之和为支撑树T的权，记为w(T)，且
[5]。
定义2：如果支撑树T*的权w(T*)是G的所有支撑树中最小的，则称T*是G的最小支撑树，也称最小树，即，
[6]。
找到最小树以后，下一步要找到最小圈MC。
初始点选取过程如下：
首先，通过Prim算法找到最小树；
第二，通过上述算法找到最小圈；
第三，将最小圈包括的所有节点和边从最小树中除去，在剩余的节点中重新计算边长，产生新的最小树；
第四，迭代找出所有n+1-n/k个最小圈；
第五，计算n+1-n/k个最小圈的中心，作为初始聚类的中心。
通过一个例子说明计算最小圈的过程，图示数字大小表示边长：
以一个6个节点10条边的图为例，找出5个具有3个节点2条边的最小圈，这要求将6个点分成2个聚类。
图1 原图 图2 最小树 图3 最小圈
图1 表示工程原图，具有6个节点10条边；图2 给出图1中的最小树，具有6个节点5条边；图3标明找到的5个圈(1,2,3)， (2,3,6)， (2,3,4)， (3,4,5)， (3,4,6)，虚线标志的圈为最小圈。
图1给出了工程原图，要找出最小圈，首先找出最小树，如图2所示，在最小树中，计算以任意两条边三个节点围成的圈的长度，图例中，L(1,2,3)=16+5+19=40，L(2,3,6)=26，L(2,3,4)=17，L(3,4,5)=19，L(3,4,6)=30。由此可见，由2，3，4三个节点组成的圈长度最小，即最小圈。最小圈的的中心就是k-均值中第一个初始聚类中心。然后，将节点2，3，4从图中删除，其余的节点为第二个聚类，由节点1，5，6组成的圈的中心为k-均值中第二个初始聚类中心。
MK-means算法包括两个步骤：初始化和聚类计算。初始化过程包括计算最小树，产生最小圈和计算圈中心三个部分[7]。假设数据集可以看成是一个由n个点，n(n-1)/2条边组成的连通图，每个数据被视为图中的一个节点，根据连通图的特点，每两个节点之间都有一条边，这条边的权重就是边的长度，每个聚类里面大约包含[n/k]个数据点。在初始阶段，要找出k个最小圈和k个初始聚类中心。
3.2 MK-means算法的流程
Step1：初始化
输入：X={x1,x2,…,xn}
输出：k个聚类中心
定义矩阵X=[ x1,x2,…,xn]//计算最小树
for j=1
to k
定义一个空数组d=[]
令d1=x1
for i=1
to n-1
ci=D(xi’, xk’)=min{D(xi,xk)}，xi
d，xkX-d
di+1= xk’ //计算最小圈
for i=1
to (k-1)n/k+1
fi=c0+i+ c1+i+…+ cn/k-2+i+D(di,di+n/k)
fi=min{ fi} //计算最小圈中心Cj
Cj=means(di,…,di+n/k)
从数据集中删除最小圈中的数据点
j=j+1，X=X-d 算法终止，直到j=k。
Step2：利用k-均值算法产生聚类。
Step3：输出聚类结果。
4、改进算法在隧道病害分析中的应用
将改进算法应用于部分隧道病害数据分析中，该数据集为部分隧道统计数据，由于实验数据的分类是已知的，所以本文采用相对标准分类的准确率来评判聚类结果。算法的评价指标如表1所示。
表1 算法评价指标
|
指标
|
K-means
|
MK-means
|
|
1
|
2
|
3
|
1
|
|
类内点数
|
38,62,50
|
50,42,58
|
47,34,69
|
50,44,56
|
|
总误差
|
0.08
|
0.12
|
0.287
|
0.12
|
|
误分类数
|
0,12, 0
|
0,5,13
|
8,4,31
|
0,8,10
|
|
正确分类数
|
38,50,50
|
50,37,45
|
39,30,38
|
30,20,27
|
|
分类准确率
|
0.92
|
0.88
|
0.713
|
0.88
|
|
出现概率
|
0.003
|
0.3541
|
0.6429
|
1
|
本文通过VC++编制程序实现记录识别，识别规则如下：
第一步，记录识别。如果记录i的“行别”=记录j的“行别”，且记录i的“线名”=记录j的“线名”，且记录i的“隧道号”=记录j的“隧道号”，且记录i的“隧道名”=记录j的“隧道名”，则记录i=记录j；否则，记录i
记录j。
记录识别后，每条记录增加一个“隧道标识”属性，如果两条记录的上述四个属性都相同，则赋予相同的“隧道标识”。程序自上而下搜索，每一条记录都被比较一次，每一次比较都跳过作标记的记录，直到所有的记录都被标记。表2为部分隧道记录识别示例：
表2 “蜈松岭”隧道记录识别示例
|
行别
|
线名
|
隧道号
|
隧道名
|
劣化项目
|
劣化等级
|
数量
|
单位
|
ID
|
|
单
|
贵昆
|
094
|
蜈松岭
|
衬砌开裂或错动
|
2/3
|
0.090234
|
m
|
286
|
|
单
|
贵昆
|
094
|
蜈松岭
|
渗漏水
|
1/3
|
0.053079
|
m
|
286
|
|
单
|
贵昆
|
094
|
蜈松岭
|
洞内外排水设施损坏
|
2/3
|
0.140127
|
m
|
286
|
|
单
|
贵昆
|
094
|
蜈松岭
|
隧道铺底损坏
|
2/3
|
0.13482
|
m
|
286
|
|
单
|
贵昆
|
094
|
蜈松岭
|
限界不足
|
1/3
|
1
|
座
|
286
|
第二步，记录重组。识别后的记录仍然不能直接用于聚类，还需要对“劣化项目”、“劣化等级”和“数量”属性不同而其他属性相同的记录进行识别，添加隧道标号属性，标明记录所属的隧道，为聚类计算提供识别依据。
表3为通过VC++自编程序运行产生的隧道病害信息结果，详细划分出各条隧道名，病害类型，病害数量，为运用改进的聚类算法MK-means算法作准备。
表3隧道病害生成信息
|
项目编码
|
病害类型
|
病害数量
|
|
S0601
|
混凝土衬砌厚度不足
|
2
|
|
S0602
|
混凝土衬砌强度不足
|
6
|
|
S0101
|
衬砌变形或移动
|
164
|
|
S0501
|
隧道整体道床变形损坏
|
278
|
|
S0502
|
隧道仰拱变形损坏
|
321
|
|
S0103
|
衬砌压溃
|
437
|
|
S0301
|
冻害
|
460
|
|
S0402
|
运营通风不良
|
690
|
|
S0303
|
洞口仰坡坍方落石
|
961
|
|
S0503
|
隧道铺底损坏
|
198
|
|
S0302
|
洞内外排水设施损坏
|
2113
|
|
S0201
|
衬砌腐蚀
|
2629
|
|
S0403
|
照明不良
|
3716
|
|
S0102
|
衬砌开裂或错动
|
5533
|
|
S0202
|
渗漏水
|
10562
|
|
S0401
|
限界不足
|
13595
|
通过基于最小支撑树聚类的改进算法运算，得出隧道病害主要聚类点和聚类距离如图4所示：
图4. 基于最小支撑树的隧道病害聚类生成图
由基于最小支撑树的隧道病害聚类生成图，得出隧道病害评价结果，具体如表4所示：
表4 隧道病害评价结果
|
聚类ID
|
类内距离
|
类间距离
|
|
1
|
2
|
3
|
4
|
|
1
|
0.1283
|
0
|
0.6991
|
0.7680
|
0.8628
|
|
2
|
0.1466
|
0.6991
|
0
|
0.8317
|
0.9017
|
|
3
|
0.0959
|
0.7680
|
0.8317
|
0
|
0.5287
|
|
4
|
0.2011
|
0.8628
|
0.9017
|
0.5287
|
0
|
|
……
|
……
|
……
|
……
|
……
|
……
|
由上表，可以发现改进算法MK-means的优点， MK-means算法产生的分类结果准确率可达到0.88，且对于一个数据集，每次运行产生的结果都非常稳定，初始化之后，MK-means的聚类速度更快。改进的算法以在结果准确性、结果稳定性、聚类速度等几方面都优于k-均值聚类算法，它的结果稳定且接近最优结果。通过聚类可以得知：照明不良、衬砌开裂或错动、渗漏水、限界不足、隧道冻害为隧道的主要病害，运营管理部门应该从这几个方面采取防治和预防措施：
1、衬砌渗漏水地段，采用“排为主，堵为辅，堵排结合”的措施。首先对衬砌背后进行全断面压注水泥，然后清理衬砌表面并涂刷止水涂层进行内贴式防水[8]。在集中出水处设置引水孔若干，通过排水管将水引至侧沟；无水沟侧则将水引至铸铁管，由铸铁管将水导人侧沟。
2、照明不良，适当加强灯光照的强度，达到防晕效果。
3、隧道冻害，严寒及寒冷地区隧道冻害的防治，可以采用综合治水、更换土壤、保温防冻、结构加强、防止融坍等，可根据实际情况综合运用。
5、参考文献
[1] 孙吉贵，刘杰等. 聚类算法研究[J]. 软件技术. 2008. 19(1). 50-52
[2] Ruspini E H.
Numerical methods for fuzzy clustering[J]. Information Science. 1970. 15(2).
319-350
[3]
Tamra S, et.al. Pattern classification based on fuzzy relations[J]. IEEE Trans.
SMC. 1971. 1(1). 217-242
[4]
Backer E, Jain A K. A clustering performance measure based on fuzzy set
decomposition[J]. IEEE Trans. PAMI. 1981. 3(1). 66-74
[5] 高新波. 模糊聚类分析及其应用[M]. 西安. 西安电子科技大学出版社. 2004. 49-54
[6] 李洁. 基于自然计算的模糊聚类新算法研究[D]. 西安. 西安电子科技大学. 2004. 5-6
[7]
Krishnapuram R, Killer J M. A possibilistic approach to clustering[J]. IEEE
Transactions on Fuzzy System. 1993. 1(2). 98-110
[8]
Selim S Z, Ismail M A. Soft clustering of multidimensional data: a semi-fuzzy
approach[]. Pattern Recognition. 1984. 17(5). 559-568