考慮空間格局的譜聚類算法及其應用

于永玲，李 向，宗思生，施進發

(鄭州航空工業管理學院計算機科學與應用系，河南鄭州450015)

0 引言

聚類分析參照“物以類聚”的思想，通過研究抽取樣本數據的“潛在”結構，將數據對象分組成為多個類或簇［1－2］。它不需要先驗知識和假設，是一種非監督學習方法，廣泛應用于數據挖掘和數據分析［3］。隨著空間數據挖掘技術的興起，空間聚類已成為地理信息科學和計算機科學共同關注的研究課題之一［4］。例如，文獻［5］對1982 年至1997 年北京城市土地利用擴展的時空過程進行空間聚類和歷史形態分析，揭示了城市土地利用擴展的空間分異規律。文獻［6］提出了基于空間聚類的地價分區定級法的主要思想和主要步驟。文獻［7］以儲備成本和救援效率為目標，利用空間聚類方法建立數學模型，解決應急物資儲備區域劃分問題。類似的研究還很多，這里不逐一列舉。

現有的空間聚類算法中，沒有同時顧及空間對象的屬性特征和空間位置關系，會降低空間聚類的可靠性，甚至得出與實際情況相悖的結論。許多學者關注這個問題并展開了相關研究，例如:文獻［8］研究了在空間聚類中，最佳聚類數k 求解的優化問題;文獻［9］提出了一種基于雙重距離的空間聚類方法;文獻［10］研究了在空間數據的分布中，離散點的方向聚類問題。值得注意的是，空間地理對象既具有非空間的屬性特征，又具有與位置相關的空間特征。如果不考慮其空間特征，單一使用非空間的屬性特征來進行聚類，聚類結果會與實際情況產生較大的差異，不能全面的反映對象的內在聯系。因此，本文在充分考慮空間對象的屬性特征和空間位置關系的基礎上，改進目前比較流行的譜聚類算法［11］，在聚類過程中融合空間格局信息，首先計算所有空間對象的局部離群指數，然后結合空間鄰近關系，確定空間對象中的局部離群對象，最后以空間鄰近作為約束條件進行譜聚類，保證除了一些局部離群對象外，同一類對象在空間上處于相鄰的位置。

1 考慮空間分布格局的譜聚類算法

1.1 譜聚類算法

譜聚類算法的思想來源于譜圖劃分理論，如果將數據集看成一個無向完全圖G ={V，E}，數據點作為圖的頂點，將數據點間的相似度量化為定點連接邊的權值，則聚類問題就轉化為圖的劃分問題。要是聚類效果達到最優，也就是設計一種劃分準則，使劃分后的子圖間的相似度最小，而子圖內部的相似度最大。因此，劃分準則的好壞對聚類效果有直接的影響。目前，常用的劃分準則主要有規范割準則、比例割準則、平均割準則、多路規范割準則、最大最小割準則以及Ng 等人提出的Ng-Jordan-Weiss(NJW)等［12－13］。本文主要考慮NJW 算法(以Ng，Jordan 及Weiss 人名首字母命名)，該算法的本質是利用相似矩陣的特征向量進行聚類，選取構造矩陣的前k 個最大特征值對應的特征向量，從而在k 維空間中構成與原數據一一對應的表述，進而在k 維空間中利用k-means 或其他簡單算法進行聚類。NJW 算法的具體步驟可以查閱相關文獻，這里不再贅述。

1.2 考慮空間分布格局的譜聚類算法

為了表示研究區域內空間對象的鄰近關系，引入了鄰接關系矩陣的概念，表述如下:

設研究區域S 有n 個空間對象s = {s1，s2，…，sn}，用空間鄰接矩陣W 表達鄰接關系，當且僅當空間對象si和sj具有鄰接關系且i ≠j 時，Wij= Wjt= 1，否則Wij= 0。

每個空間對象si的m 維屬性向量為xi= x(si)= ［xi1，xi2，…，xim］。

譜聚類算法和k-means 算法對初始聚類中心的選擇都很敏感，如果空間對象存在局部離群點對聚類結果影響較大，所以本文考慮將局部離群點剔除，然后聚類，在聚類完成后，根據離群點與最終聚類中心的歐氏距離來確定離群點屬于哪一類。離群點的檢測方法很多，本文采用LOF 算法［14］，該算法計算數據集中每一個對象的局部離群指數，通過比較該指數的大小來確定局部離群點。指數越大，表明該點臨近區域的對象分布密度越小，該對象越離群。

考慮空間分布格局的譜聚類算法步驟如下:

(1)利用GIS 軟件ArcGIS 構建空間鄰接矩陣W，并指定譜聚類的聚類數目K。

(2)計算每個空間對象屬性數據的局部離群指數，若該對象的局部離群指數大于1.7 且k-鄰域內的所有點都和該點沒有鄰近關系，則該點為空間異常點，從樣本中剔除。

(3)選擇局部離群指數最小的對象作為第一個聚類中心，然后再從局部離群指數小于1 的對象中選擇屬性數據的歐式距離最遠的K 個對象作為初始聚中心。

(4)進行NJW 算法的前4 個步驟。

(5)從Y 中挑選步驟(3)中初始聚類中心對應的K 個對象作為初始聚類的各類別中心{z1(0)，z2(0)，…，zk(0)}。

(6)將各類別Zl初始化為空，執行迭代找出最佳聚類中心，在迭代過程中，如果空間對象yj與其距離最短的集合Zl中的空間對象有鄰接關系時，進行k-means 的下一步;否則下次搜索時不包括該距離，重新進行搜索。

(7)若集合Y 中的所有元素均屬于K 個不同的類別中時，更新個聚類中心值。

(8)若所有的聚類中心均保持穩定，即對l=1，2，…，K，有zl(a)=zl(a+1)，則k-means 聚類過程結束，否則重新迭代。

2 應用實例

文獻［15］指出，局部離群指數越大，表明該對象鄰近區域的對象分布越稀疏，并以京郊農田重金屬監測數據為例，比較了局部離群指數方法與內梅羅污染指數方法的評價結果的準確性。

為驗證本文所提出的算法，以包頭地區221 km2范圍內的重金屬污染數據為例進行聚類分析，每km2中取1 個土樣。根據土壤環境監測技術規范的要求，進行土壤樣品的采集與處理。實地測量得到了土壤樣品的地理坐標數據，土壤物質經過實驗室分析，獲得其中As、Cd、Cr、Cu、Hg、Ni、Pb、Zn 共8 種重金屬的總量，并且還檢測每一種重金屬的形態數據，包括水溶態、離子交換態、碳酸鹽結合態、腐殖質結合態、鐵錳氧化物結合態、有機結合態、殘渣態7 種形態數據。表1 為研究區域某一采樣點重金屬含量數據的實例。

2.1 傳統的內梅羅指數法

常用的土壤重金屬污染評價方法是內梅羅指數法［16］，該方法將污染評價量化為內梅羅污染指數PNemerow，其計算公式為:

式中，AVERAGE(Pi)表示每個土樣的8 個單項污染指數的平均值;MAX(Pi)表示單項污染指數的最大值。

表1 單個采樣點重金屬含量數據示例 μg/g

根據計算結果，可以確定土樣的污染等級。按照土壤環境質量標準的規定，共分清潔、尚清潔、輕度污染、中度污染、重污染5 個等級。這種方法僅考慮土壤中多種污染物的數學統計特性，根據重金屬污染物單因子評價指數的平均值、最大值，用簡單的公式計算合成為一個值，不能體現重金屬各種形態數據對污染的影響，并且也沒有考慮土壤樣本的空間位置關系。

事實上，由于每個土壤樣品所處地理空間位置不同，加上重金屬含量及形態數據的復雜性，對污染的評價不能簡單的表達成內梅羅指數法的數學計算公式。

2.2 本文算法

考慮到相鄰地區的重金屬污染情況有很大的空間相關性，因此在聚類過程中引入局部離群指數，量化空間分布格局，從而能夠把握重金屬污染的空間分布形態和差異規律。

為了更好地刻畫土壤重金屬污染所具有的空間地表連續性特征，使用本文所提出的考慮空間格局的譜聚類算法，對數據進行聚類分析。

由于重金屬元素Pb 的毒性強，對環境影響嚴重，本文以Pb 為例，給出基于譜聚類的空間聚類分析結果。為了使聚類結果更加形象，本文結合GIS 技術對結果進行展示，底圖由不同的圖層組成，反應行政區劃、河流、道路、工業礦業區等地理要素，裝飾圖層為聚類結果，顏色由淺至深代表污染程度加重。圖1 為采用本文方法得到的重金屬Pb 的聚類結果，圖2 為采用單純譜聚類算法和GIS 插值分析得到的重金屬Pb 的評價結果。

圖1 重金屬Pb 考慮空間分布格局的譜聚類結果

圖2 重金屬Pb 譜聚類結果

2.3 算法應用結果分析

從圖1 和圖2 可以看出:僅用單一的譜聚類算法，聚類結果存在同一類的對象在空間上處于不相鄰的現象，在包頭市的郊區和農村存在3 個污染點，在工業區包蘭線附近出現一個嚴重污染點，青山區和昆都侖區之間為一片嚴重污染區域。而采用本文方法的分析結果表明:在青山區和昆都侖區之間有一片嚴重污染區域，包鋼沿昆都侖河向南有一片成條帶分布的污染區，郊區沒有污染。野外實地考察的結果是:包頭地區因為包鋼的存在，重金屬Pb 的污染比較嚴重，受到雨水和大氣沉降的影響進入昆都侖河，順昆都侖河向下游蔓延，河流邊上的農田使用河水灌溉導致了重金屬Pb 的蔓延，污染情況基本上是沿昆都倫河呈現條帶分布;青山區和昆都侖區交接地帶多年前發生過一起加油站含鉛汽油泄漏事故，導致土壤中鉛的富集，最高值達到645 mg/g。采樣區域內不存在其他異常點源污染區域。

綜合數據分析結果與實際情況，使用本文提出的考慮空間格局的新的空間聚類算法，對數據聚類分析的結果與現狀是一致的。本文的方法不僅刻畫了重金屬污染形態數據的相似程度，而且還刻畫了各類指標的空間分布格局，聚類結果更接近實際的污染情況。

3 結論

本文提出的考慮空間格局的譜聚類算法，充分考慮了不同數據對象的空間相鄰性，綜合鄰接關系矩陣和局部離群指數，更好地表征數據樣本的空間分布，因此更適合于對空間對象的聚類分析。應用于土壤重金屬污染評價的實例證明，該算法兼顧數據的多維特性，不僅可以反映土壤污染的空間分布，還兼顧重金屬不同形態對污染的影響，優于傳統的內梅羅指數評價方法。

致謝:感謝國家地質實驗測試中心提供包頭土壤重金屬數據。

［1］ Jain A，Murty M，Flynn P.Data Clustering:A Review［J］.ACM Computing Surveys，1999，31(3):264－268.

［2］ 尹云飛，鐘智.一種聚類挖掘軟件數據的方法［J］.河南科技大學學報:自然科學版，2004，25(2):37－41.

［3］ 李向，李玲玲.GIS 支持的土壤重金屬污染評價與分析［M］.鄭州:鄭州大學出版社，2012:94－95.

［4］ 李德仁，王樹良，李德毅，等.論空間數據挖掘和知識發現的理論和方法［J］.武漢大學學報:信息科學版，2002，27(3):221－233.

［5］ 劉盛和，吳傳鈞，沈洪泉，等.基于GIS 的北京城市土地利用擴展模式［J］.地理學報，2000，55(4):407－416.

［6］ 王海軍，張德禮.基于空間聚類的城鎮土地定級方法研究［J］.武漢大學學報:信息科學版，2006，31(7):628－630.

［7］ 王晶，黃鈞.基于空間聚類的我國應急物資儲備區域劃分實證研究［J］.安全與環境學報，2012，12(4):259－263.

［8］ 楊善林，李永森，胡笑旋，等.K-means 算法中的k 值優化問題研究［J］.系統工程理論與實踐，2006(2):97－101.

［9］ 李光強，鄧敏，程濤，等.一種基于雙重距離的空間聚類方法［J］.測繪學報，2008，37(4):482－488.

［10］ 陳應顯.空間離散點的方向聚類研究［J］.計算機工程與應用，2012，48(11):7－10.

［11］ 蔡曉妍，戴冠中，楊黎斌.譜聚類算法綜述［J］.計算機科學，2008，35(7):14－18.

［12］ 王會青，陳俊杰.基于圖劃分的譜聚類方法的研究［J］.計算機工程與設計，2011，32(1):289－282.

［13］ Shi J，Malik J. Normalized Cuts and Image Segmentation［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence，2000，22(8):888－905.

［14］ 薛安榮，鞠時光，何偉華，等.局部離群點挖掘算法研究［J］.計算機學報，2007，30(8):1455－1463.

［15］ 周腳跟，趙春江.基于局部離群指數的土壤重金屬污染評價方法［J］.農業工程學報，2010，26(1):279－283.

［16］ HT/T166—2004 土壤環境監測技術規范［S］.北京:中國環境科學出版社，2004.