丁小兵

（上海工程技術(shù)大學(xué)城市軌道交通學(xué)院，201620，上?！沃蹋?/p>

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

1 k－均值算法

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

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

第i類的類內(nèi)平方誤差為：

目標(biāo)函數(shù)表示為：

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

針對k－均值算法，當(dāng)聚類內(nèi)部密集，且各聚類之間區(qū)別很明顯時，該算法的效果較好［4］。

2 改進(jìn)的聚類算法MK－means算法

在研究經(jīng)典算法的基礎(chǔ)上，對k－means算法進(jìn)行改進(jìn)，提出 MK－means（Mended K－Means）算法。在標(biāo)準(zhǔn)的k－均值算法中，初始點(diǎn)的選取是隨機(jī)的?；陔S機(jī)選取的初始點(diǎn)進(jìn)行迭代運(yùn)算，每次運(yùn)行k－均值算法都會產(chǎn)生不同的聚類結(jié)果。而MK－means算法基于圖論中最小支撐樹的思想，通過求最小支撐樹得到最小圈，產(chǎn)生k個初始聚類中心，得到更好的聚類結(jié)果。將該改進(jìn)的算法用到隧道病害劃分與預(yù)防中，具有很好的準(zhǔn)確性和操作性，MK－means算法能夠優(yōu)化k－均值算法的性能。

2.1 MK－means算法

設(shè)連通圖G＝（V，E），每一邊e＝［vi，vj］有一個非負(fù)權(quán)w（e）＝wij，wij≥0。

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

定義2：如果支撐樹T＊的權(quán)w（T＊）是G的所有支撐樹中最小的，則稱T＊是G的最小支撐樹，也稱最小樹，即w（T＊）＝minw（T）［6］。

找到最小樹以后，下一步要找到最小圈MC。

初始點(diǎn)選取過程如下：

首先，通過Prim算法找到最小樹；

第二，通過上述算法找到最小圈；

第三，將最小圈包括的所有節(jié)點(diǎn)和邊從最小樹中除去，在剩余的節(jié)點(diǎn)中重新計(jì)算邊長，產(chǎn)生新的最小樹；

第四，迭代找出所有n＋1－（n／k）個最小圈；

第五，計(jì)算n＋1－（n／k）個最小圈的中心，作為初始聚類的中心。

通過以下的例子說明計(jì)算最小圈的過程。

以一個6個節(jié)點(diǎn)10條邊的圖為例，找出5個具有3個節(jié)點(diǎn)2條邊的最小圈，這要求將6個點(diǎn)分成2個聚類。以下圖1、圖2和圖3中線段旁的數(shù)字表示邊長。圖1表示工程原圖，具有6個節(jié)點(diǎn)10條邊；圖2給出圖1中的最小樹，具有6個節(jié)點(diǎn)5條邊；圖3標(biāo)明找到的5個圈：（1，2，3），（2，3，6），（2，3，4），（3，4，5），（3，4，6），虛線標(biāo)志的圈為最小圈。

圖1 工程原圖

圖2 最小樹

圖3 最小圈

圖1給出了工程原圖，要找出最小圈，首先找出最小樹，如圖2所示。在最小樹中，計(jì)算以任意兩條邊三個節(jié)點(diǎn)圍成的圈的長度，圖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三個節(jié)點(diǎn)組成的圈長度最小，即最小圈。最小圈的的中心就是k－均值中第一個初始聚類中心。然后，將節(jié)點(diǎn)2，3，4從圖中刪除，其余的節(jié)點(diǎn)為第二個聚類，由節(jié)點(diǎn)1，5，6組成的圈的中心為k－均值中第二個初始聚類中心。

MK－means算法包括兩個步驟：初始化和聚類計(jì)算。初始化過程包括計(jì)算最小樹，產(chǎn)生最小圈和計(jì)算圈中心三個部分［7］。假設(shè)數(shù)據(jù)集可以看成是一個由n個點(diǎn)，n（n－1）／2條邊組成的連通圖，每個數(shù)據(jù)被視為圖中的一個節(jié)點(diǎn)，根據(jù)連通圖的特點(diǎn)，每兩個節(jié)點(diǎn)之間都有一條邊，這條邊的權(quán)重就是邊的長度，每個聚類里面大約包含［n／k］個數(shù)據(jù)點(diǎn)。在初始階段，要找出k個最小圈和k個初始聚類中心。

2.2 MK－means算法的流程

1）初始化。

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

輸出：k個聚類中心

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

forj＝1tok

定義一個空數(shù)組d＝［］

令d1＝x1

fori＝1ton－1

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

di＋1＝x′k∥計(jì)算最小圈

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

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

fi＝minfi∥計(jì)算最小圈中心Cj

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

從數(shù)據(jù)集中刪除最小圈中的數(shù)據(jù)點(diǎn)

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

2）聚類計(jì)算，利用k－均值算法產(chǎn)生聚類。

3）輸出聚類結(jié)果。

3 改進(jìn)算法在隧道病害分析中的應(yīng)用

將改進(jìn)算法應(yīng)用于部分隧道病害數(shù)據(jù)分析中，數(shù)據(jù)集為部分隧道的統(tǒng)計(jì)數(shù)據(jù)。因?yàn)樵囼?yàn)數(shù)據(jù)的分類是已知的，所以本文采用相對標(biāo)準(zhǔn)分類的準(zhǔn)確率來評判聚類結(jié)果。算法的評價指標(biāo)如表1所示。

表1 改進(jìn)算法評價指標(biāo)

本文通過VC＋＋編制程序?qū)崿F(xiàn)記錄識別，識別規(guī)則如下：

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

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

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

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

表3為通過VC＋＋自編程序運(yùn)行產(chǎn)生的隧道病害信息結(jié)果，為運(yùn)用改進(jìn)的聚類算法MK－means算法作準(zhǔn)備。

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

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

由表4可以發(fā)現(xiàn)改進(jìn)算法MK－means的優(yōu)點(diǎn)。

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

表3 通過VC＋＋自編程序運(yùn)行產(chǎn)生的隧道病害信息

表4 隧道病害評價結(jié)果

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

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

（2）對照明不良，應(yīng)適當(dāng)加強(qiáng)燈光照的強(qiáng)度，起到防暈的效果。

（3）對隧道凍害，嚴(yán)寒及寒冷地區(qū)隧道凍害的防治，可以采用綜合治水、更換土壤、保溫防凍、結(jié)構(gòu)加強(qiáng)、防止融坍等，可根據(jù)實(shí)際情況綜合運(yùn)用。

［1］孫吉貴，劉杰.聚類算法研究［J］.軟件技術(shù)，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］高新波.模糊聚類分析及其應(yīng)用［M］.西安：西安電子科技大學(xué)出版社，2004.

［6］李潔.基于自然計(jì)算的模糊聚類新算法研究［D］.西安：西安電子科技大學(xué)，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.