于永玲，李 向，宗思生，施進發(fā)

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

0 引言

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

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

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

1.1 譜聚類算法

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

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

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

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

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

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

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

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

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

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

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

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

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

2 應用實例

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

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

2.1 傳統(tǒng)的內(nèi)梅羅指數(shù)法

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

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

表1 單個采樣點重金屬含量數(shù)據(jù)示例 μg/g

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

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

2.2 本文算法

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

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

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

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

圖2 重金屬Pb 譜聚類結果

2.3 算法應用結果分析

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

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

3 結論

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

致謝:感謝國家地質(zhì)實驗測試中心提供包頭土壤重金屬數(shù)據(jù)。

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

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

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

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

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

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

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

［8］ 楊善林，李永森，胡笑旋，等.K-means 算法中的k 值優(yōu)化問題研究［J］.系統(tǒng)工程理論與實踐，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］ 周腳跟，趙春江.基于局部離群指數(shù)的土壤重金屬污染評價方法［J］.農(nóng)業(yè)工程學報，2010，26(1):279－283.

［16］ HT/T166—2004 土壤環(huán)境監(jiān)測技術規(guī)范［S］.北京:中國環(huán)境科學出版社，2004.