基于不確定數據的半監督動態K-均值算法在滑坡危險性預測上的應用

景德鎮學院,江西 景德鎮 333000

滑坡災害是地質災害中最重要的災害類型之一，具有分布地區廣、運動速度快、災害損失嚴重等特點[1]。我國是滑坡災害較為多發的國家之一，且近年來發生頻率不斷增加，因此，有效的滑坡危險性預測方法仍是現今研究的熱點。

無監督聚類方法已廣泛用于滑坡危險性預測領域，無監督聚類是指在不需要任何先驗信息的情況下，通過抽取數據中的“潛在”結構，將數據劃分到不同類別。張俊等[2]采用K-means 聚類算法，選取7 個致災因子作為滑坡易發性的評價指標，對三峽庫萬州區的滑坡易發性評價體系進行分級，實驗證明滑坡易發性評價體系預測精度較高。吳亞子等[3]基于灰色聚類法，通過計算11 個因子對應評價級別的基準劃分值，對阿里地區滑坡等地質災害的危險性展開評價預估，得到了較好的預測結果。阮云凱等[4]采用K-PSO 聚類算法，確定8 個影響因子并計算影響因子權重值，在旭龍水電站庫區實驗中的滑坡危險性預測結果證明與實際發育情況具有較高的一致性。雖然無監督聚類在滑坡危險性預測上取得了一些成效，但是仍存在一些明顯的問題：首先，傳統聚類算法多應用于屬性為確定性的數據，而在處理滑坡的不確定誘發因素降雨量的聚類上效果不佳；其次，整個聚類過程由于沒有任何先驗信息的指導，很可能會產生沒有實際意義的劃分結果，且聚類精度整體偏低。因此，研究分別從這兩個方面出發，進行優化方案的探討。

不確定數據作為新型數據之一，近年來受到廣泛關注。對于降雨量這類的不確定數據，傳統針對確定性數據的歐氏距離無法有效度量其間距。基于此，郭軍鵬[5]提出了一種基于中點和半徑的不確定數據距離—Hausdorff 距離，該距離是目前使用較為廣泛的一種不確定數據距離，但同時，該距離僅適用于內部服從均勻分布的不確定數據，而在實際應用中，不確定數據的內部分布通常未知。因此，文中以Hausdorff 距離為基礎，擴展出一種適用于任意不確定數據的uv距離。

利用先驗信息來指導聚類過程，改善無監督聚類算法的性能，該類算法在數據挖掘領域被統稱為半監督聚類，先驗信息通常是數據的類別標記或約束關系。由于在滑坡危險性預測應用中，往往存在少量滑坡觀測點的類別信息，由此提出將先驗信息為類別標簽的半監督聚類應用于滑坡危險性預測的設想。在以類別標記為監督信息引導聚類過程的算法研究中，Basu 等[6]首先提出了Seeded-K-均值和Constrained-K-均值算法,它們使用少量帶類別標簽的標記數據形成seeds 集以初始化類中心，進而提高整個數據集的聚類性能，但同時，seeds 集的質量和規模對聚類結果的影響顯著。因此，文獻[7]提出一種改進的半監督聚類算法，該算法通過Tri-training 的迭代過程及數據剪輯的Depuration技術提高seeds 集質量，進一步提高了算法的聚類性能，但該算法僅從seeds 集角度進行分析改進，且改進方法未結合應用本身特點。因此，本次研究充分考慮滑坡應用本身性質，引入衡量降雨量的uv距離，設計了一種基于不確定數據的半監督動態K-均值算法(USSD-K-均值算法（Uncertain semi-supervised dynamic）)，并分別從seeds 集質量和算法過程兩個角度進行優化。首先對初始seeds集進行消噪，其次利用滑坡分布的局地集中發育特點[8]進行標簽的空間擴展，實現seeds 集優化；其次引用隸屬度概念，通過設置隸屬度閾值動態更新劃分結果，有效提高了聚類性能。

本文提出一個新的不確定數據測度，闡述基于不確定數據的半監督動態聚類算法的具體步驟，并給出時間復雜度分析，通過實驗對uv距離及USSD-K-均值算法進行性能測試并對結果比較分析，并對全文工作進行總結及展望。

1 不確定數據

1.1 不確定數據概念

不確定數據，即帶有不確定性的數據。根據其不確定性的表示方式，可以將不確定數據分為傳輸數據的點概率數、測量數據的區間數等[9]。本文所研究的滑坡危險性應用，其不確定誘發因素降雨量的表現形式為區間數，因此文中所提不確定數據均指區間數，其定義如下：

定義1給定，稱為一個區間數，mL為區間數的左端點，mU為區間數的右端點。特別地，若mL=mU，則變為一個確定數。

1.2 不確定數據距離

聚類算法通常按照某種相似準則將數據集劃分成為若干個簇，通常以數據間的距離作為相似度衡量標準，而傳統方法僅適用于確定性數據，因此，尋求一個能有效衡量不確定數據相似度的不確定數據距離是不確定性數據聚類的關鍵。基于此，文獻[5]提出了一種基于中點和半徑的不確定數據距離—Hausdorff 距離，其定義如下：

定義2對于區間數m=[mL mU]，n=[nL nU]，令，表示區間數的中點，表示區間數的半徑(X=m,n)，則區間m和n間的Hausdorff 距離：

分析式（1）易看出，在區間數內部點服從均勻分布的前提下，中點c(X)能有效反映出這些點數據的集中位置，半徑r(X)則能直觀刻畫其離散程度。但在實際應用中，區間數內部的分布通常難以獲得，因此本文以Hausdorff 距離為基礎，擴展出一種適用于任意區間數的uv距離，以下給出定義：

定義3對于區間數m=[mL mU]，n=[nL nU]，區間數內部點可能服從任意分布，則區間數m和n間的uv距離定義為：

式中u(X)描述區間數的平均值，v(X)則表示區間數的平均離差（X=m,n）。

注：假設一個任意區間數為[X1Xn]，。對于任意分布的區間數，均值u(X)可以有效反映區間內部數據的集中趨勢，而平均離差v(X)能較精準地刻畫區間內的離散程度。相較于Hausdorff 距離的局限性，新提出的uv距離適用范圍更廣。在滑坡危險性預測應用中，不確定屬性降雨量的數據雖然可以獲取，但其分布情況卻無法獲知，此時若利用Hausdorff 距離度量相似性會丟失部分有效信息，導致聚類精度較低。而基于均值和平均差的uv距離可以充分利用區間內的數據信息，進而有效度量數據間的相似性。以下進一步給出uv距離為一個度量空間的證明：

證明*區間數集η用表示，設三個區間數x，y，z∈η

（1）uv(x,y)=|u(x)-u(y)|+|v(x)-v(y)|，其中|u(x)-u(y)|≥0|v(x)-v(y)|≥0，所以uv(x,y)≥0，滿足非負性。

（2）|u(x)-u(y)|=|u(y)-u(x)|，同樣|v(x)-v(y)|=|v(y)-v(x)|，故uv(x,y)=uv(y,x)，滿足對稱性。

（3）|u(x)-u(y)|+|u(y)-u(z)|≥|u(x)-u(y)|+|u(y)-u(z)|=|u(x)-u(z)|，同樣地|v(x)-v(y)|+|v(y)-v(z)|≥|v(x)-v(y)|+|v(y)-v(z)|=|z(x)-v(z)|

故uv(x,y)+uv(y,z)≥uv(x,z)，滿足三角不等式性。因此uv距離滿足度量空間定義的三個條件。

2 基于不確定數據的半監督動態K 均值算法

2.1 半監督K-均值算法

K-均值算法是一種使用普遍的聚類算法，傳統K-均值算法屬于無監督聚類算法，它首先隨機初始聚類中心，其次根據相似性將數據分配到最近的類中心，迭代更新聚類中心，直至目標函數最小化，目標函數表示為：

其中，p表示給定的數據對象，ci為第i類的聚類中心，共有k個聚類。

不同于K-均值算法隨機選取初始聚類中心的方法，Basu 等[6]提出的半監Seeded-K-均值和Constrained-K-均值算法通過給出的少量帶類別標簽的數據形成seeds 集，并根據seeds 集確定初始聚類中心，相較于完全忽視監督信息的傳統聚類算法，半監督K-均值算法有效利用了給出的監督信息，提高了算法的聚類性能。但基于seeds 集的Seeded-K-均值和Constrained-K-均值算法對seeds 集的規模和質量十分敏感，若能得到一個規模大、質量好的seeds 集，算法性能也將得到顯著提高。

因此，為進一步提高半監督K-均值算法的聚類性能，分別從seeds 集和算法本身提出改進方案。

2.2 seeds 集優化

在基于seeds 集的半監督K-均值算法中，初始聚類中心的質量對聚類效果的影響顯著。因此提出一種seeds 集優化方法：首先對原始seeds 集消噪，通過檢測seeds 集中所有數據點，刪除差異較大的噪聲點；其次以去噪后的標簽樣本為基礎，結合滑坡分布空間上局地集中發育的性質[8]，進行標簽數據的空間擴展，最終得到規模大、質量高的seeds 集。

seeds 集由已知帶標記的數據構成，傳統方法把seeds 集直接按類別標記劃分成k個類，并以此確定k個聚類中心，但是在seeds 集中，可能存在少量這樣的數據：雖然它帶有類別標簽，但它與類中其它數據點的相似性卻很小，表現為該點的平均距離遠大于類內其它點的平均距離。將此類點直接劃分到初始類會直接影響初始中心的計算，因此首先提出一種方法，剪輯原始seeds 集中的噪聲點，其具體方法如下：首先把seeds 集DL中的數據按照類標號分成k個類：C1,C2,…,CK；n1,n2,…,nk表示每個類中的點數目，計算每個點的平均距離，刪除各類中平均距離明顯較大的點。給出點xi的平均距離公式：

注意：若聚類對象為確定性數據時，點的平均距離用歐式距離計算；若聚類對象屬性為不確定數據時，點的平均距離用uv距離計算。

算法1：標簽數據集的消噪

輸入：標簽數據集DL

輸出：標簽數據集DL_

Step 1數據集DL按類別標號初始化k個類：C1,C2,…,Ck。

Step 2計算k個類中每點的平均距離avg(xi)(xi∈Ck)。

Step 3每個類中的點分別按平均距離升序排列，刪除平均距離明顯偏大的點。

Step 4用DL_表示剩下的點組成的標簽數據及并輸出。

算法1 中，數據集劃分成k個類的時間復雜度為O(L)，其中L是標簽數據集的大小，計算每點的平均距離的時間復雜度為O(L2)，排序采取快速排序方法，時間復雜度為O(Llog2L)，因此，標簽數據集消噪的時間復雜度為O(L2)。

由于實際應用中通常可獲得的標簽樣本非常少，經過上述方法消噪后的seeds 集雖然質量得到提升，但其規模仍然很小，因此，結合數據集本身具有的空間一致性的性質[10]，根據應用實例中滑坡成群分布的基本特點完全符合這一性質的實際情況，并同時考慮到實驗能通過ARCGIS 獲取各滑坡點的空間位置的實際條件，提出一種標簽數據空間擴展方法。其具體方法如下：首先計算出消噪后的seeds 集中各類的類平均距離avg(Ck)，以avg(Ck)作為各類標簽的擴展閾值，其次求出k個類的類中心Ck，以類中心為起點，搜索空間范圍內滿足空間閾值φ范圍內的所有點，并比較這些點與Ck的平均距離，若不大于avg(Ck)，則將點Ck的類別標記賦給此點，反之，此點仍為未標記數據。

首先給出類平均距離的定義，把DL_中的數據按照類標號分成k個類：C1,C2,…,Ck，nk表示第k個類中的點數目，avg(xi)表示點xi的平均距離，類平均距離avg(Ck)為類內所有點平均距離的平均值，計算方法如下：

其次，類中心Ck的計算方法如下：

最后，空間閾值φ實質上是一個空間范圍，它表示在空間范圍φ內的所有點很可能屬于同一個類，但它的值并不固定，根據聚類應用的不同，φ值也不同。

算法2：標簽數據集的空間擴展

輸入：標簽數據集DL_，未標記數據集Ln，空間閾值φ。

輸出：標簽數據集D*L，未標記數據集Ln_。

Step 1把數據集DL_按類別標號劃分成k個類：C1,C2,…,Ck，并計算每個類的類平均距離avg(Ck)及類中心Ck。

Step 2得求出類中心Ck與Ln集中每個點的空間位置。

Step 3在未標記數據集Ln上尋找與類中心Ck在空間上滿足φ的所有點，并計算它與Ck的平均距離。

Step 4若d(Ck,Ln)≤avg(Ck)，則Ln的類別標記為k，若d(Ck,Ln)＞avg(Ck)，則點Ln仍為未標記數據。

Step 5用D*L及Ln_分別表示所有標記數據點組成的標簽數據集和未標記數據點組成的數據集并輸出。

算法2 中，計算類平均距離及類中心的時間復雜度為O(L2_)，其中，L_是數據集DL_的大小。得到類中心及Ln集中點空間位置的時間復雜度為O(k+n)，其中，k是數據集DL_中的類別，n是數據集Ln的大小。其次在數據集Ln上尋找與k個類中心空間上滿足φ的點的時間復雜度為O(kn)。因此，標簽數據集的擴展的時間復雜度為max{O(kn),O(L2_)}。

2.3 基于不確定數據的半監督動態K-均值算法（USSD-K-均值算法）

不同于傳統聚類算法針對屬性為確定性數據的情形，新提出的用于滑坡危險性預測的USSD-K-均值算法研究的對象為不確定數據，因此該算法首先引入新提出的uv距離，其次，相較于傳統半監督K-均值算法通過迭代改善目標函數多次分配所有對象的方法，USSD-K-均值算法在seeds 集優化的基礎上，引進隸屬度的概念，通過遞減隸屬度閾值對所有對象進行逐步擇優劃分，保證每次劃分結果的質量。算法3 給出USSD-K-均值算法的聚類過程。

算法3USSD-K 均值算法

輸入：標簽數據集DL，未標記數據集Ln，空間閾值φ

輸出：聚類結果

Step 1算法1。

Step 2算法2。

Step 3計算seeds 集D*L中的初始類中心。

把數據集D*L按類別標號劃分成k個類：C1,C2,…,Ck，計算每個類的中心，其計算方法：

其中，nk為第k類中點的數目。

Step 4計算未標記數據集中的點到各個類的隸屬度。

隸屬度概念來源于模糊簇，它度量對象屬于不同類的程度，通常用于模糊聚類中劃分矩陣的計算，而本文引入隸屬度概念，通過設定隸屬度閾值判斷對象是否滿足被劃分的依據，通常用Wij表示點Li在類Cj中的隸屬度，其計算方法如下：

seeds 集D*L中各類的初始中心為未標記數據集為Ln_(l1,l2,l3,…,ln_)，則表示為：

Step 5設置隸屬度閾值，并通過降低閾值做逐次劃分。

隸屬度閾值用于判斷數據對象在某類中的隸屬度是否達到將該對象劃分到這個類的標準，本文用θ代表隸屬度閾值，若Wij＞θ，則可以將對象li劃分到類cj中。通常將初始θ值設置為較高值，以保證劃分結果的高質量。β為下降系數，代表每次劃分隸屬度閾值的降低程度，通常根據實際應用中對聚類結果的精度要求設置。本節以初始θ值為0.8，下降系數β為0.9 為例進行描述：（值得注意的一點是，前期為保證劃分質量，下降系數設置為0.9，當隸屬度閾值達到一個較低的水平，此時可以增強下降系數，使隸屬度閾值大幅下降，具體地，設定β=β2）：

a) 將初始θ值設為0.8，計算Ln_集中所有對象到各類的隸屬度，若則將對象li劃分到第j類，若對象li到每個類的隸屬度均小于0.8，則它回到未標記數據集中進入下一次劃分，直至對象Wn_j被比較，第一次劃分結束。得到新的有標簽數據集D1未標記數據集

迭代更新類中心，并根據隸屬度閾值逐次劃分

……

算法3 中，seeds 集優化的總時間復雜度為max{O(L2),O(kn)}。其次計算類中心的時間復雜度為O(L*)，L*為數據集D*L的大小。計算隸屬度的時間復雜度為O(kn_)，其中，n_為數據集Ln_的大小。根據隸屬度閾值做不同劃分的時間復雜度為O(n2_)。因此，USSD-K-均值算法的整體時間復雜度為O(n2_)。

3 實驗

為驗證本文提出的uv距離及USSD-K-均值算法在衡量滑坡不確定因素降雨量及預測滑坡危險性上的效果，本次實驗以延安市寶塔區的某區域作為實驗對象，提取相關數據，并以給出的少量先驗信息為指導，分別進行對比實驗。

3.1 實驗準備

結合滑坡地質災害發生的特征及學者對該區域滑坡災害形成機理的研究，本次實驗選取坡高、坡型、坡度、坡向、植被、巖土體結構、降雨七個屬性作為滑坡危險性的評價因子。首先利用ARCGIS對該區域進行柵格劃分，選取尺寸為5 m×5 m 的柵格分辨率，得到152457 個柵格單元。其次把每個柵格單元看成一個點，導入到精度為1:5000 的數字高程度中，可以分別得出每個點的經緯度，并派生出坡型、坡度、坡高和坡向等專題圖。從各專題圖中可以獲取所需的地形地貌等信息，巖土體數據從1:1000 的地質圖中獲取，植被數據通過EVNI 遙感軟件取得，降雨量數據來源于地調中心的GIS數據庫[11]。決策因子為滑坡危險性等級，分為高、中、低三個危險性等級，研究區根據專家基于區域特征的分析已經選取了326 個觀測點并確定其危險性等級，觀測點的危險性等級包含了高危、中危、低危三個類別。

3.2 參數設置及模型建立

引入不確定數據模型—uv距離，在算法過程中，不確定屬性降雨量的衡量統一使用uv距離。首先以給出的326 個觀測點作為標記數據集形成初始seeds 集DL，根據危險性等級高危、中危、低危將其劃分成3 個類，利用算法1 進行seeds 集消噪，刪除少量噪聲點。其次根據地質與數據專家分析滑坡本身空間分布及該區域地質災害分布特點得到的結果，將空間閾值φ設置為387 m，空間閾值φ在本次滑坡應用中的實際意義為：若某點的危險性等級確定，則在其空間范圍387 m 內的所有點的危險性等級很可能與它一致。以seeds 集消噪后的觀測點作為DL_集，其余152131 個觀測點形成未標記數據集Ln，閾值φ=387 m，利用算法2 進行標簽數據的空間擴展，得到最終seeds 集D*L及未標記數據集Ln_。最后本次實驗將初始θ值設置為0.85，下降系數β為0.9，利用算法3 在數據集Ln_進行聚類，得到最終聚類結果。

3.3 評價標準

在本次滑坡危險性預測的實驗中，選取內部有效性指標Silhouette 指標[12]作為實驗的聚類評價標準，用于未知樣本集聚類效果的判斷。它通過點的緊密度和分離度來計算，其計算方法如下：

其中，式中點x屬于類Cj，a(x)表示點x與Cj中其它點的平均距離，b(x)=min{dis(x,ci)}，i=1,2,…,k,且i≠j。從式中易看出Silhouette 指標取值在[-1,1]之間，全部樣本的平均Silhouette 值越接近1，表明聚類效果越好。具體地，在滑坡危險性預測實驗中，Silhouette 指標值越高，表明其預測精度越好。

3.4 實驗分析

3.4.1uv距離效果分析 為驗證uv距離在衡量不確定因素降雨量的有效性，在保證其他參數和步驟均相同的情況下，分別基于歐氏距離、Hausdorff 距離以及新提出的uv距離衡量降雨量，使用新算法比較滑坡危險性等級的聚類效果。不同比例數據集下三種距離衡量不確定雨量時算法的聚類效果(圖1)。

從圖1 可見，新提出的uv距離衡量不確定因素降雨量時，聚類Silhouette 指標值達到0.8 以上，優于利用歐氏距離和Hausdorff 距離衡量降雨量時的聚類結果。歐式距離在衡量降雨量時，完全忽略了數據的不確定性，因此聚類效果不佳。Huasdorff 距離雖然考慮了其不確定性，但它丟失了部分內部重要信息，其衡量效果優于歐式距離，但遜于uv距離，其Silhouette 指標值平均在0.78 左右。而本文提出的基于均值和平均差的uv距離充分利用了不確定數據的內部信息，達到了較好的衡量效果。

3.4.2 USSD-K-均值算法性能分析 為驗證USSD-K-均值算法有效性，實驗基于不同比例數據集，對Seeded-K-均值算法、Constrained-K-均值算法和基于Tri-Training 和數據剪輯的半監督K-均值算法和本文提出的USSD-K-均值算法分別進行測試。圖2 給出Silhouette 指標對比結果。

從圖2 可以發現USSD-K-均值算法的聚類效果整體好于Seeded-K-均值算法、Constrained-K-均值算法及基于Tri-Training 和數據剪輯的半監K-均值算法，具體地看，Seeded-K-均值算法和Constrained-K-均值算法的聚類指標Silhouette 值平均在0.70 左右，聚類精度偏低，且隨數據集增加，seeds 集所占比例隨之減少時，初始類中心的質量無法保證，聚類精度逐漸降低。而基于Tri-Training和數據剪輯的半監督K-均值算法通過優化seeds 集提高了聚類精度，Silhouette 值范圍達到0.82 左右，它的聚類效果雖然高于傳統的半監督K-均值算法，但仍未達到滑坡危險性預測應用的預期標準。本文提出的USSD-K-均值算法從seeds 集優化及算法本身兩個角度進行改進，通過合理利用滑坡分布的特點進行空間擴展，并設置隸屬度閾值擇優劃分，其Silhouette 值高達0.86，優于其它算法。根據對比不同算法的聚類性能，不難發現USSD-K-均值算法在滑坡危險性預測上的優勢。

圖1 不同距離的衡量效果對比實驗Fig.1 Comparison of measuring effect of the different distances

圖2 不同算法聚類效果的對比實驗Fig.2 Comparison of clustering effects of different algorithms

圖3 seeds 集優化的對比實驗Fig.3 Comparison of seeds optimization

3.4.3 seeds 集優化效果分析 為進一步明確文中所提出的充分結合滑坡分布特點的seeds 集優化方法的作用，對未進行seeds 集優化的USSD-K-均值算法及USSD-K-均值算法也進行比較（圖3）。

分析圖3 易得，經過seeds 集優化后的聚類效果明顯優于未經seeds 集優化的聚類效果，尤其在樣本數量增多的情況下，seeds 集的規模不變，但其所占樣本的比例變少，此時由seeds 集引導的聚類效果不佳，如圖3 所示，當數據樣本比例達到3%時，未進行seeds 集優化的USSD-K-均值算法的Silhouette 指標值僅為0.71。而新提出的USSD-K-均值算法利用除噪和空間擴展的方式優化seeds 集，通過在空間閾值內尋找相似標簽數據的方法，在擴大seeds 集的同時保證了質量。因此，USSD-K-均值算法在滑坡危險性預測上的聚類效果取得高達0.86 的平均Silhouette 值，seeds 集優化的作用顯著。

4 結論與展望

本文首先提出一種新的不確定數據距離—uv距離，它實現了滑坡誘發因素中不確定降雨量的有效刻畫。其次基于uv距離提出一種基于不確定數據的半監督動態K-均值算法，首先利用消噪和空間擴展優化seeds 集，其次引入隸屬度并設置隸屬度閾值進行逐優劃分，達到了提高滑坡危險性預測精度的目的。實驗結果分別驗證了uv距離衡量不確定數據的有效性及USSD-K-均值算法預測滑坡危險性的良好性能。

研究中所提出的空間擴展方法有效結合了數據集本身具有的空間一致性的性質及滑坡成群分布的特點，該方法中的空間閾值φ用于控制空間擴展的規模，其取值對聚類結果影響顯著，且根據滑坡分布區域的不同，φ值也會變化。因此分析φ對計算結果的影響及研究不同區域內φ的取值將是我們下一步工作的重點。