空間數據挖掘的高效和有效的聚類方法

胡馨元，殷守林，劉杰（沈陽師范大學科信軟件學院，沈陽　110034）

空間數據挖掘的高效和有效的聚類方法

胡馨元，殷守林，劉杰
（沈陽師范大學科信軟件學院，沈陽110034）

0　引言

空間數據挖掘[1-2]是指從空間數據庫中抽取沒有清楚表現出來的隱含的知識和空間關系，并發現其中有用的特征和模式的理論、方法和技術。空間數據挖掘和知識發現的過程大致可分為以下多個步驟:數據準備、數據選擇、數據預處理、數據縮減或者數據變換、確定數據挖掘目標、確定知識發現算法、數據挖掘、模式解釋、知識評價等，而數據挖掘只是其中的一個關鍵步驟。但是為簡便，人們常常用空間數據挖掘來代替空間數據挖掘和知識發現。

在空間數據處理過程中，采用所有的算法都會遇到兩個問題：第一，用戶和專家必須為算法提供空間層次概念結構，這可能并不在一些應用中使用；第二，兩種算法進行空間探索主要通過在一定程度層次結構上以一個更大的地區在一個更高的水平合并區域。這兩個問題對于很多應用來說，它很難知道一個先驗的層次結構是否是最適合的。

在聚類分析中有兩種著名的算法即圍繞中心點的劃分和大型應用中的聚類方法。

空間數據挖掘的兩個主要算法SD（Clarans）和NSD（Clarans）[3-4]。

SD（Clarans）：Spatial Dominant Approach空間占主導地位的方法。

NSD（Clarans）：Non-Spatial Dominant Approach非空間占主導地位的方法。

為了解決這些問題，我們探索了聚類分析技術是否適用。在過去三十年中聚類分析一直是個被研究的對象，而且成功應用在很多領域上。對于空間數據挖掘，我們在這里使用的方法僅用于空間屬性，那些自然相似概念的存在如歐幾里得、曼哈頓距離。正如本篇文章所展示的，聚類分析對于空間數據挖掘非常有效，作為更有效的考慮，我們發展研究自己的聚類分析算法叫做CLARANS，它為了研究大數據集而被設計。

1　基于分割的聚類方法

1.1圍繞中心點的劃分方法（PAM）

它的基本思想：為找到k個集群，它的方法就是為每個集群確定一個代表對象。這個代表對象稱為中心點它是最集中位于集群中的對象。一旦這個中心點被選中了，每一個非選擇的最相似的對象以中心點歸類[5-7]。假如Oj是一個非被選擇的對象，Oi就是一個中心點，我們就說Oj屬于由Oi代表的聚類。如果d（Oj，Oi）=minOed（Oj，Oe），其中minOe代表所有中心點Oe中的最小值。d（Oa，Ob）代表Oa到Ob的距離。

所有的相異點的值給出作為PAM的輸入，最后聚類的效率由一個對象和一個中心點的平均值測出。為了尋找這個k個中心點，PAM以任意的一個k對象開始，在每一步中只要能夠提高聚類的效率就進行Oi和Oh的互換，為了計算兩者之間互換的影響，PAM對所有非選擇性對象Oj計算Cjih的消耗。下面列出了Oj存在的幾種情況：

（1）假設Oj屬于Oi的聚類 ，讓Oj比Oh更加相似于Oj2，也就是d（Oj，Oh）≥d（Oj，Oj2），Oj2更接近于Oj，因此，如果Oi被Oh取代了成為中心點，那么Oj屬于Oj2的一個聚類。互換成本可以寫成Cjih=d（Oj，Oj2）－d（Oj，Oi）。

（2）Oj比Oh并不相似于Oj2也就是d（Oj，Oh）＜d （Oj，Oj2）。如果Oi被Oh取代了成為中心點，那么Oj屬于Oh的一個聚類此時Cjih=d（Oj，Oi）－d（Oj，Oj2）。

（3）假設Oj接近于除了Oi展示的聚類 ，讓Oj2接近于那個中心點，而且讓Oj比Oh更接近于Oj2，因此，即使Oi被Oh取代了，Oj會一直聽停留在Oj2的一個聚類中。互換成本可以寫成Cjih=0。

（4）假設Oj屬于Oj2的聚類 ，但是Oj比Oh并不接近于Oj2，用Oh取代Oi會引起Oj跳躍到Oh的一個聚類中，因此，如果Oi被Oh取代了成為中心點，那么Oj屬于Oj2的一個聚類。互換成本可以寫成Cjih=d（Oj，Oh）－d （Oj，Oj2）。

1.2圍繞中心點的劃分算法步驟

（1）任意選擇k個代表對象。

（2）Oi被選定了，Oh沒有被選中，計算所有的Oi消耗成本。

（3）選擇Oi和Oj這一對中心點符合minOi，Oh，TCih如果最小值是負的就用Oh取代Oi并且回到第二步。

（4）否則，對于每一個非被選擇的對象找到最相似的對象。

實驗結果表明，PAM適合小的數據集而不適合大的。在第二第三步中一共有k（n-k）對Oi和Oh，對于每一對中心點，

計算TCih需要檢查（n-k）個非選擇點，那兩步的時間復雜度是O（k（n-k）2），但是這樣過于復雜，因此出現了CLARA（Clustering Large Applications，大型應用中的聚類方法）。

2　CLARA算法

①對于i=1，2，3，4，5重復以下步驟。

②從所有數據集中隨機畫一個40+2k對象的樣本，讓PAM算法找到k個中心點。

③對于所有數據集中的Oj對象，確定k個中心點哪一個更接近于Oj。

④計算包含在以上步驟中的相異聚類點的平均值，如果這個值小于目前的最小值用這個值取代那個最小值，保留在第二步中找到的k個中心點作為目前最好的一組中心點集。

⑤返回到第一步開始新的交互尋找。

PAM：時間復雜度是O（k（n-k）2）。

CLARA：時間復雜度是O（k（k+40）2+k（n-k））。

3　一種基于隨機搜索的聚類算法——CLARANS

另外，令Sa是一組對象，子圖GSa，k由子集合Sa構成。如果M原始圖形Gn，k中的最小節點，而且M并不包含在GSa，k中，那么M永遠不會在GSa，k的搜索中找到。

CLARA在搜索的開始，畫了一個樣本的節點，而CLARANS在每一個搜索的步驟中畫了一個鄰居的樣本。

（1）分割聚類算法步驟

①輸入參數numlocal（局部最小值），maxneighbor（局部最大值）初始化i=1，mincost為一個大數值；

②在Gn，k中設置一個任意節點current；

③令j=1；

⑤如果S有一個很低的消耗，令current=S，回到第三步；

⑥否則，j+1。如果j≤maxneighbor回到第四步；

⑦否則j＞maxneighbor，讓current和mincost的消耗做一個比較，如果current消耗少于mincost，令min鄄cost=current（cost消耗），并且令bestnode=current；

⑧i+1，如果i＞numlocal，輸出bestnode和halt，否則返回到第二步。

由以上可以看出，CLARANS有兩個參數鄰居的最大值和局部的最小值。局部最大值越高，CLARANS越接近PAM，每個局部最小值的搜索也越長。這樣一個局部最小值更高的特性將會有更少的地方需要取得最小值。在CLARANS里面設置numlocal=2，maxneighbor設置成一個在250和k（n-k）的1.25%之間比較大的值。PAM和CLARANS的比較結果如圖1所示。

CLARA產生聚類的特性，CLARANS進行了數值規范。隨著k=5，10，20增大CLARA的誤差也越來越大，而CLARANS方法的誤差不變。如圖2所示。

圖1　PAM和CLARANS的比較結果

考慮到相同的時間，CLARANS在所有情況下很明顯勝過CLARA。當k（聚類的個數）從5增加到20的時候二者之間的誤差由4%到20%。隨著k的增大它們之間的誤差可以通過對二者彼此的復雜分析很好的被解釋。

CLARA的時間復雜度是O（k3+nk）可以說明CLARA的有一個很大消耗。但是對象個數的越多二者之間的誤差也就越小。總之，我們已經有實驗表明CLARANS 比CLARA更有高效性。

4　結語

本文提出了一種基于隨機搜索的聚類算法稱為CLARANS，實驗部分說明了此方法的有效性，比現有的數據挖掘算法能快速有效的發現新的數據，因此，CLARANS算法是一個非常有前途應用的算法，在數據挖掘方面將會起到很大的作用。

圖2　CLARA和CLARANS誤差比較

[1]周海燕.空間數據挖掘的研究[D].中國人民解放軍信息工程大學，2003.

[2]王海起，王勁峰.空間數據挖掘技術研究進展[J].地理與地理信息科學，2005，04:6-10.

[3]孫志偉，趙政.SOFM神經網絡在處理非空間屬性中的應用[J].計算機應用，2006，11:2667-2669+2673.

[4]孫志偉，趙政.DBSCAN在非空間屬性處理上的擴展[J].計算機應用，2005，06:1379-1381.

[5]吳文亮.聚類分析中K-均值與K-中心點算法的研究[D].華南理工大學，2011.

[6]Tianhua Liu，Shoulin Yin.An Improved K-means Clustering Algorithm for Kalman Filter[J].ICIC Express Letters Part B:Applications，2015，6（10）:2687-2692.

[7]徐金寶.核函數在劃分聚類中的應用與實現[J].電腦知識與技術，2013，27:6185-6188.

[8]殷守林，劉天華，李航.基于模擬退火算法的卡爾曼濾波在室內定位中的應用研究[J].沈陽師范大學學報（自然科學版），2015，01:86-90.

[9]李強，何衍，蔣靜坪.一種基于隨機游動的聚類算法[J].電子與信息學報，2009，03:523-526.

[10]陳東輝.基于目標函數的模糊聚類算法關鍵技術研究[D].西安電子科技大學，2012.

Spatial Data Mining;Partitioning Clustering Method;Random Search

Efficient and Effective Methods in Spatial Data Mining

HU Xin-yuan，YIN Shou-lin，LIU Jie
（Software College，Shenyang Normal University，Shenyang 110034）

1007-1423（2016）06-0015-04

10.3969/j.issn.1007-1423.2016.06.004

胡馨元（1990-），女，遼寧鐵嶺人，沈陽師范大學碩士研究生，研究方向為數據挖掘，企業信息化

殷守林（1990-），男，河南濮陽人，碩士研究生，研究方向為數據挖掘、網絡安全。E-mail：910675024@qq.com

劉杰（1966-），男，博士，教授，遼寧沈陽人，沈陽師范大學碩士研究生導師，研究方向為數據挖掘，軟件工程

2015-12-17

2016-02-15

空間數據挖掘可能隱式的存在于空間數據庫中。探索聚類方法是否對于空間數據挖掘有一定的幫助。為此，提出一種基于隨機搜索的新的聚類方法——分割聚類方法。使用分割聚類方法也研究出兩種空間數據挖掘算法。經過分析與驗證，在分割聚類方法的幫助下，這兩種算法非常有效且會發現很難找到與當前空間數據挖掘算法有重復之處。再者，分割聚類方法和那些存在的聚類方法相比較，實驗表明分割聚類方法具有高效性。

空間數據挖掘；分割聚類方法；隨機搜索

Spatial data mining may be the implicit existence in spatial database.Explores that whether the clustering method is useful for spatial data mining,proposes a new clustering method based on random search named partition clustering method.Using partition clustering method also develops two kinds of spatial data mining algorithms.After analysis and validation,with the help of the partition clustering method,the two kinds of algorithm is very effective and it is difficult to find same parts with the current spatial data mining algorithm. Moreover,compared with the existing clustering methods,experiment results of partition clustering method show that clustering segmentation method is very effective.