考慮空間格局的譜聚類算法及其應(yīng)用

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

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

0 引言

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

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

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

1.1 譜聚類算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 應(yīng)用實例

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

為驗證本文所提出的算法，以包頭地區(qū)221 km2范圍內(nèi)的重金屬污染數(shù)據(jù)為例進(jìn)行聚類分析，每km2中取1 個土樣。根據(jù)土壤環(huán)境監(jiān)測技術(shù)規(guī)范的要求，進(jìn)行土壤樣品的采集與處理。實地測量得到了土壤樣品的地理坐標(biāo)數(shù)據(jù)，土壤物質(zhì)經(jīng)過實驗室分析，獲得其中As、Cd、Cr、Cu、Hg、Ni、Pb、Zn 共8 種重金屬的總量，并且還檢測每一種重金屬的形態(tài)數(shù)據(jù)，包括水溶態(tài)、離子交換態(tài)、碳酸鹽結(jié)合態(tài)、腐殖質(zhì)結(jié)合態(tài)、鐵錳氧化物結(jié)合態(tài)、有機(jī)結(jié)合態(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ù)計算結(jié)果，可以確定土樣的污染等級。按照土壤環(huán)境質(zhì)量標(biāo)準(zhǔn)的規(guī)定，共分清潔、尚清潔、輕度污染、中度污染、重污染5 個等級。這種方法僅考慮土壤中多種污染物的數(shù)學(xué)統(tǒng)計特性，根據(jù)重金屬污染物單因子評價指數(shù)的平均值、最大值，用簡單的公式計算合成為一個值，不能體現(xiàn)重金屬各種形態(tài)數(shù)據(jù)對污染的影響，并且也沒有考慮土壤樣本的空間位置關(guān)系。

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

2.2 本文算法

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

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

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

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

圖2 重金屬Pb 譜聚類結(jié)果

2.3 算法應(yīng)用結(jié)果分析

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

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

3 結(jié)論

本文提出的考慮空間格局的譜聚類算法，充分考慮了不同數(shù)據(jù)對象的空間相鄰性，綜合鄰接關(guān)系矩陣和局部離群指數(shù)，更好地表征數(shù)據(jù)樣本的空間分布，因此更適合于對空間對象的聚類分析。應(yīng)用于土壤重金屬污染評價的實例證明，該算法兼顧數(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］.河南科技大學(xué)學(xué)報:自然科學(xué)版，2004，25(2):37－41.

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

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

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

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

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

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

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

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

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

［12］ 王會青，陳俊杰.基于圖劃分的譜聚類方法的研究［J］.計算機(jī)工程與設(shè)計，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］.計算機(jī)學(xué)報，2007，30(8):1455－1463.

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

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