聚類分析算法改進及其在地鐵隧道病害分析中的應用研究＊

丁小兵

（上海工程技術大學城市軌道交通學院，201620，上海∥助教）

隧道病害關系到軌道交通、公路的正常運營。據統計，隧道病害的種類有上百種之多，而目前隧道病害的處理方法雖然多種多樣，但大都采用逐個病害排查的方法，浪費時間、人力資源等。本文在深入研究經典算法基礎上提出了一種改進算法，通過基于最小支撐樹的聚類算法的改進，采用改進的模糊聚類算法以及病害等級評價方法，對隧道的病害檢測數據進行聚類分析，得出聚類結果；對隧道病害提出若干整改意見和建議，為隧道病害預防和整治提供有實際應用意義的參考。

1 k－均值算法

k－均值算法以類內平方誤差和函數為目標函數，用戶事先指定k個劃分，通過梯度下降法迭代優化目標函數，使目標函數值最小［1］。該算法對于聚類個數k而言，本質上是一種枚舉法。而k－均值算法又是硬劃分的一種，每個劃分至少包含一個對象，每個對象必須只屬于一個劃分［2］。

假設將n個樣本X＝x1，x2，...，xn劃分為k個類，ni表示第i類中所包含的樣本個數表示第i類的中心。則uij有如下定義和性質［3］：

第i類的類內平方誤差為：

目標函數表示為：

通過迭代，使得J（u）取得最小值：J（u）＊＝min｛J（u）｝，從而找到最優化。

針對k－均值算法，當聚類內部密集，且各聚類之間區別很明顯時，該算法的效果較好［4］。

2 改進的聚類算法MK－means算法

在研究經典算法的基礎上，對k－means算法進行改進，提出 MK－means（Mended K－Means）算法。在標準的k－均值算法中，初始點的選取是隨機的。基于隨機選取的初始點進行迭代運算，每次運行k－均值算法都會產生不同的聚類結果。而MK－means算法基于圖論中最小支撐樹的思想，通過求最小支撐樹得到最小圈，產生k個初始聚類中心，得到更好的聚類結果。將該改進的算法用到隧道病害劃分與預防中，具有很好的準確性和操作性，MK－means算法能夠優化k－均值算法的性能。

2.1 MK－means算法

設連通圖G＝（V，E），每一邊e＝［vi，vj］有一個非負權w（e）＝wij，wij≥0。

定義1：如果T＝（V，E′）是G的一個支撐樹，定義E′中所有邊的權值之和為支撐樹T的權，記為w（T），且

定義2：如果支撐樹T＊的權w（T＊）是G的所有支撐樹中最小的，則稱T＊是G的最小支撐樹，也稱最小樹，即w（T＊）＝minw（T）［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 最小樹

圖3 最小圈

圖1給出了工程原圖，要找出最小圈，首先找出最小樹，如圖2所示。在最小樹中，計算以任意兩條邊三個節點圍成的圈的長度，圖3中，L（1，2，3）＝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個初始聚類中心。

2.2 MK－means算法的流程

1）初始化。

輸入：X＝x1，x2，…，xn

輸出：k個聚類中心

定義矩陣X＝［x1，x2，…，xn］∥計算最小樹

forj＝1tok

定義一個空數組d＝［］

令d1＝x1

fori＝1ton－1

ci＝D（x′i，x′k＝minD（xi，xk），xi∈d，xk∈X－d

di＋1＝x′k∥計算最小圈

fori＝1 to（k－1）n／k＋1

fi＝c0＋i＋c1＋i＋…＋cn／k－2＋i＋D（di，di＋n／k）

fi＝minfi∥計算最小圈中心Cj

Cj＝means（di，…，di＋n／k）

從數據集中刪除最小圈中的數據點

j＝j＋1，X＝X－d算法終止，直到j＝k。

2）聚類計算，利用k－均值算法產生聚類。

3）輸出聚類結果。

3 改進算法在隧道病害分析中的應用

將改進算法應用于部分隧道病害數據分析中，數據集為部分隧道的統計數據。因為試驗數據的分類是已知的，所以本文采用相對標準分類的準確率來評判聚類結果。算法的評價指標如表1所示。

表1 改進算法評價指標

本文通過VC＋＋編制程序實現記錄識別，識別規則如下：

第一步，記錄識別。如果記錄i的“行別”＝記錄j的“行別”，且記錄i的“線名”＝記錄j的“線名”，且記錄i的“隧道號”＝記錄j的“隧道號”，且記錄i的“隧道名”＝記錄j的“隧道名”，則記錄i＝記錄j；否則，記錄i≠記錄j。

記錄識別后，每條記錄增加一個“隧道標識”屬性，如果兩條記錄的上述4個屬性都相同，則賦予相同的“隧道標識”。程序自上而下搜索，每一條記錄都被比較一次，每一次比較都跳過作標記的記錄，直到所有的記錄都被標記。表2為貴昆線蜈松嶺隧道記錄識別示例。

第二步，記錄重組。識別后的記錄仍然不能直接用于聚類，還需要對劣化項目、劣化等級和數量等屬性不同而其他屬性相同的記錄進行識別，添加隧道標號屬性，標明記錄所屬的隧道，為聚類計算提供識別依據。

表2 貴昆線蜈松嶺隧道記錄識別示例

表3為通過VC＋＋自編程序運行產生的隧道病害信息結果，為運用改進的聚類算法MK－means算法作準備。

通過基于最小支撐樹聚類的改進算法運算，得出隧道病害主要聚類點和聚類距離，如圖4所示。

由基于最小支撐樹的隧道病害聚類生成圖，得出隧道病害評價結果，如表4所示。

由表4可以發現改進算法MK－means的優點。

MK－means算法產生的分類結果準確率可達到0.88，且對于一個數據集，每次運行產生的結果都非常穩定，初始化之后，MK－means的聚類速度更快。改進的算法在結果準確性、穩定性、聚類速度等方面都優于k－均值聚類算法，它的結果穩定且接近最優結果。通過聚類可以得知：照明不良、襯砌開裂或錯動、滲漏水、限界不足、隧道凍害為隧道的主要病害，運營管理部門應該有針對性地采取防治和預防措施。建議措施如下：

表3 通過VC＋＋自編程序運行產生的隧道病害信息

表4 隧道病害評價結果

（1）襯砌滲漏水地段，采用“排為主，堵為輔，堵排結合”的措施。首先對襯砌背后進行全斷面壓注水泥，然后清理襯砌表面并涂刷止水涂層進行內貼式防水［8］。在集中出水處設置引水孔若干，通過排水管將水引至側溝；無水溝側則將水引至鑄鐵管，由鑄鐵管將水導人側溝。

圖4 基于最小支撐樹的隧道病害聚類生成圖

（2）對照明不良，應適當加強燈光照的強度，起到防暈的效果。

（3）對隧道凍害，嚴寒及寒冷地區隧道凍害的防治，可以采用綜合治水、更換土壤、保溫防凍、結構加強、防止融坍等，可根據實際情況綜合運用。

［1］孫吉貴，劉杰.聚類算法研究［J］.軟件技術，2008，19（1）：50.

［2］Ruspini E H.Numerical methods for fuzzy clustering［J］.Information Science，1970，15（2）：319.

［3］Tamra S，et al.Pattern classification based on fuzzy relations［J］.IEEE Trans SMC，1971，1（1）：217.

［4］Backer E，Jain A K.A clustering performance measure based on fuzzy set decomposition［J］.IEEE Trans PAMI，1981，3（1）：66.

［5］高新波.模糊聚類分析及其應用［M］.西安：西安電子科技大學出版社，2004.

［6］李潔.基于自然計算的模糊聚類新算法研究［D］.西安：西安電子科技大學，2004.

［7］Krishnapuram R，Killer J M.A possibilistic approach to clustering［J］.IEEE Trans on Fuzzy System，1993，1（2）：98.

［8］Selim S Z，Ismail M A.Soft clustering of multidimensional data：a semi－fuzzy approach［J］.Pattern Recognition，1984，17（5）：559.