面向地學應用的不確定數據聚類算法比較研究

蔡 建 南，鄧 敏，劉 啟 亮，唐 建 波，黃 金 彩

（中南大學地理信息系，湖南 長沙 410083）

0 引言

在實際應用中，由于測量精度、地理現象本身的隨機性、隱私保護等因素，實際獲取的空間數據經常包含明顯的不確定性。例如：在傳感器網絡中，由于受到外界噪聲或者無線傳輸誤差等影響，使得輸出數據具有不確定性［1］；在氣候監測領域，一個氣象站點監測的多種氣候指標（如降水、氣溫、氣壓、濕度、風力、風向等）隨時間不斷變化，因而監測站點的氣候條件亦具有不確定性［2］；為了保護隱私，許多隱私保護的技術使用概率攝動的方法來降低原始數據的保真度［3］。為了更好地對不確定性數據進行分析，在數據分析過程中一個數據對象不再是空間內的一個確定點，而通常被建模為一個由一系列采樣點構成的不確定區域，在這個不確定區域內定義的概率密度函數用于描述對象落在每個確定位置上的概率［4］。空間數據的不確定性對空間數據挖掘的影響亦不可忽視，作為空間數據挖掘的一項主要任務，近年來不確定數據聚類分析在地學領域的應用已經引起國內外學者的廣泛關注，旨在聚類分析過程中建模空間數據的不確定性，進而獲取更加可靠的聚類結果［5，6］。在地學應用領域，很多情況下不確定數據在幾何空間上具有一定的重疊，而概率分布差異顯著。例如：不同氣溫帶的氣溫波動范圍多是重疊的，但是其氣溫的概率分布卻通常是存在差異的，該特征是區分不同氣溫帶的重要因素。目前，國內外學者雖然已經針對不確定數據聚類分析進行了初步的研究，相繼提出了一系列的不確定數據聚類算法，但是這些算法在地學應用中的有效性尚缺乏客觀的分析與比較。為此，本文首先對當前不確定聚類方法進行分析和歸納；進而，采用40組模擬數據和亞洲氣候數據集對6種代表性算法進行實驗對比分析，并對各算法的聚類質量進行定量度量，給實際應用提供指導。

1 不確定數據聚類算法

不確定數據聚類常與模糊聚類混淆［7］，二者與傳統聚類分析的區別與聯系如表1所示。傳統聚類分析的研究對象是用單個特征向量表達的確定點，且每個確定點歸屬于一個確定的簇。模糊聚類分析的研究對象也是確定點，但是每個確定點以不同隸屬度歸屬于多個簇，因此最后得到的數據集劃分結構是模糊的。不確定數據聚類的研究對象是不確定對象，但是每個不確定對象歸屬于一個確定的簇。

傳統的聚類方法可以大致分為：基于劃分的算法、基于層次的算法、基于密度的算法、基于圖論的算法、基于格網的算法、基于模型的算法和混合的算法［8］。現有不確定數據聚類分析算法多是在基于劃分和基于密度的聚類算法的基礎上，通過發展不確定對象間的相似性度量方式進行的擴展。現有研究中不確定對象間的相似性度量的方法主要有3種：1）基于期望距離的方法；2）基于模糊距離函數的方法；3）基于相對熵的方法。下面本文將針對不確定數據聚類分析中的代表性算法進行回顧。

1.1 基于劃分的算法

基于劃分的算法是一類應用最廣泛的聚類算法，其核心思想是將包含n個實體的數據庫，通過不斷優化目標劃分準則，直到數據集被劃分為所給定的k個劃分，其中每個劃分即為一個簇。代表性的算法有 K-means算法［9］和 K-medoids算法［10］等。

Chau等［11］基于 K-means算法提出 UK-means算法，用于挖掘位置不確定移動對象的聚集模式。UK-means算法與K-means算法的聚類過程完全相同，不同之處在于簇中心和距離的計算：K-means算法中，簇中心是簇中所有確定點的期望值，而UK－means算法中是計算簇中所有不確定對象的期望得到的確定點；K-means算法中，對象到簇中心的距離是兩個確定點之間的距離，而UK-means算法中是對象不確定區域內所有點到簇中心距離的期望，稱為期望距離。

為了提高UK-means算法的計算效率，一系列UK-means的改進算法相繼被提出。Ngai等［12］基于期望距離的上下界提出了多種剪枝策略，避免了很多不必要的期望距離的計算。Lee等［13］利用平行軸原理證明了UK-means算法等同于對每個不確定對象的中心進行K-means聚類，從而避免了計算各個不確定對象到簇中心的期望距離。Kao等［14］利用Voronoi圖和R樹給出了UK-means的另一個剪枝版本，進一步提高了期望距離的剪枝效率。

Jiang等［2］采用相對熵（或 KL散度，Kullback-Leibler divergence）作為不確定對象間相似性的度量函數。KL散度雖然不滿足嚴格的距離概念（如不滿足對稱性與三角不等式），但是其可以在一定程度上顧及兩個不確定對象的概率分布相似性。進而，基于K-medoids算法提出了K-Medoids-KL算法及近似的RK-Medoids-KL算法。為了進一步適應海量數據的聚類分析，Jiang等利用快速高斯變換算法提高 K-Medoids-KL和 RK-Medoids-KL算法的效率，然而其聚類精度有所降低。

1.2 基于密度的算法

基于密度的方法將簇視為一系列被低密度區域分割的高密度對象所構成的區域［6］。代表性的算法有 DBSCAN 算法［15］和 OPTICS算法［16］等。

Kriegel等［4］通過計算兩個不確定對象間距離的概率密度分布函數定義了模糊距離函數度量指標，用來表達兩個不確定對象間的相似性，進而在DBSCAN算法的基礎上提出了FDBSCAN算法，用于探測飛機零部件CAD建模數據中的聚集結構。FDBSCAN對DBSCAN算法中核對象以及直接密度可達的定義進行了擴展，提出了核對象概率和可達概率的概念，分別反映一個對象能夠成為核對象的概率及一個對象從另一個對象直接密度可達的概率。實際應用中，FDBSCAN根據每個不確定對象的樣本數據計算核對象概率及可達概率。FDBSCAN算法與DBSCAN算法的聚類過程十分相似，不同之處在于DBSCAN算法是將從當前查詢對象直接密度可達的對象加入到當前簇，而FDBSCAN算法則是將從當前查詢對象可達概率大于0.5的對象加入到當前簇。Kriegel等［17］采用相同的相似性度量方式，進一步對OPTICS算法進行改進，僅從理論上分析了FOPTICS算法的實現過程與特點。與K-Medoids-KL和 RK-Medoids-KL算法類似，Jiang等［2］采用相對熵作為不確定對象間相似性度量方式，對DBSCAN進行擴展，得到了一種基于相對熵的不確定數據聚類算法DBSCAN-KL。

進一步，從所基于的原型算法、相似性度量方式及適用性場景3個方面對當前不確定數據聚類分析算法進行系統的總結與對比，如表2所示。

2 實驗分析與應用

本文的對比試驗選取了6種代表性的算法，UK-means（UK）、FOPTICS（FOP）、K-Medoids-KL（KM-KL）、RK-Medoids-KL（RKM-KL）、DBSCAN-KL（DB-KL）和 OPTICS-KL（OP-KL）算法。由于FDBSCAN算法和FOPTICS算法都是用模糊距離函數度量對象間的相似性，而OPTICS算法與DBSCAN算法相比可以發現不同密度的簇［16］，因此本文只選擇了FOPTICS算法進行實驗分析。本文將KL散度結合到OPTICS算法中進一步發展了基于概率分布相似性的不確定數據密度聚類算法OPTICS-KL，其拓展方法與DBSCAN-KL類似，故不做詳細介紹。本文不對算法的效率進行測試，因此一些針對上述方法的效率改進方法不進行比較。通過選擇上述6種算法進行實驗分析，一方面可以分析同一原型方法、不同相似性度量方法的表現差異，另一方面可以分析相同相似性度量方法、不同原型算法的表現差異，故能夠較為全面地對當前方法的表現進行分析。

分別用模擬數據和2008年亞洲氣候數據對上述6種代表性算法進行實驗分析和比較。模擬數據為40組具有預設劃分結構的數據，其在幾何空間上高度重合，但各個不確定對象的采樣點服從不同的概率分布。實際數據是根據K?ppen-Geiger氣候分類結果［18］對各測站的氣候類型進行標記，近似地作為數據集中預知的劃分結構。由于模擬數據集和亞洲氣候數據集中的劃分結構預先已知，因此實驗采用外部評價方法評價聚類的有效性。如果兩個對象屬于同一個簇，則稱它們為一對，給出以下定義：

TP：正確肯定，兩個對象在G中是一對，在C中也是一對；

FP：錯誤肯定，兩個對象在C中是一對，在G中不是一對；

FN：錯誤否定，兩個對象在G中是一對，在C中不是一對。

其中：G表示預先設定的劃分結構，C表示聚類算法得到的結果。基于以上定義，本文采用準確率（precision）和召回率（recall）作為聚類質量的評價指標，其中，準確率表示聚類結果中正確聚類的比例；召回率表示預設聚類結構被發現的比例。具體定義如下：

2.1 模擬實驗對比分析

為了模擬幾何中心上有重疊的數據，實驗中將每個對象的不確定范圍都限制在區間［0，1］d內，然后通過一個連續分布產生一組隨機數作為連續域內一個不確定對象的采樣點。預設在同一個簇中的不確定對象的采樣點由同一個概率分布產生，包括3種不同類型的概率分布：均勻分布、高斯分布、逆高斯分布。模擬具有k個簇的數據集時，將需要模擬k個不同的概率密度函數，其中有1個均勻分布、（k－1）／2個不同方差的高斯分布，以及（k－1）／2個不同方差的逆高斯分布。為了讓隨機數都落在區間［0，1］d內，采樣點的平均值都設置為0.5，高斯分布和逆高斯分布的標準差設置為相同的較小值，具體取值如表3所示，使得隨機數落在區間外的幾率非常小，如果落在區間外，將重新產生隨機數。進而，對連續域內的模擬數據進行離散化，如圖1所示，對各維空間進行四等分，用方格的中心值表示落在同一個方格中的隨機數，得到相應離散域內的模擬數據。模擬實驗中一共考慮了4個主要因素：數據的維數d，對象個數n，樣本大小s和簇的個數k，對這4個參數設置不同的值，一共產生了40組模擬數據集，進行了8組對比實驗，各參數的取值如表4所示。

連續域內不確定數據的聚類準確率和召回率比較結果如圖2和圖3所示；離散域內不確定數據的聚類準確率和召回率比較結果如圖4和圖5所示。評價聚類質量時在考慮準確率的同時，參考召回率對試驗結果進行分析，可以發現：1）除RK-Medoids-KL和FOPTICS外，其他算法聚類質量（準確率與召回率）對數據集的維數d、對象個數n及采樣點個數s都不敏感，但所有算法都會隨著數據集中簇的個數k的增加而降低；2）對于同類型的聚類算法，采用相對熵相似性的算法聚類質量最高，即準確率與召回率都相對較高；采用期望距離相似性的聚類算法聚類質量最低；3）采用相對熵相似性的算法中，基于劃分的算法聚類質量多優于基于密度的算法，KMedoids-KL算法質量最高；采用期望距離的劃分算法UK-means算法的聚類質量最低。

圖2 連續域內不確定數據的聚類準確率比較Fig.2 Comparison of precision between six uncertain data clustering methods in the continuous case

圖3 連續域內不確定數據的聚類召回率比較Fig.3 Comparison of recall between six uncertain data clustering methods in the continuous case

2.2 實際數據對比分析

本文選取的氣象數據源于美國國家大氣研究中心（http：／／rda.ucar.edu／datasets／ds512.0／）。數據集中共包含893個氣象站點的觀測數據，且每個站點都包含366 d的氣象記錄，每條記錄包含當天的平均氣溫、總降水量和平均濕度。本文根據亞洲K?ppen-Geiger氣候分類圖［18］標記出各個站點的氣候類型（圖6），作為一種近似的真值。亞洲K?ppen-Geiger氣候分類圖中共有5種主要氣候類型：熱帶氣候、干燥氣候、暖溫帶氣候、冷溫帶氣候和極地氣候，而本文數據中沒有分布在極地氣候帶的測站，所以只有前4種主要氣候類型。一個測站每天的氣象數據可建模為一個不確定對象的樣本點，所以實際數據集中不確定對象的維數d＝3、對象個數n＝893、對象的樣本大小s＝366、簇的個數k＝4。

圖7顯示了各個算法得到的氣象站點的氣候聚類結果，圖8顯示了各個算法的聚類質量比較結果。通過對實驗結果進行定量比較，可以發現：1）各算法聚類準確率從高到低依次為：K-Medoids-KL、UK-means、RK-Medoids-KL、FOPTICS、DBSCAN-KL、OPTICS-KL。由 于 OPTICS-KL 與 DBSCAN-KL算法聚類結果主要包含一個較大的簇，故其召回率較高，但是二者準確率都較差，因此綜合考慮準確率與召回率可以發現這兩種方法的聚類質量較差；FOPTICS算法的聚類結果召回率最低，且聚類準確度中等，故可以認為其聚類質量亦較差。2）K-Medoids-KL、UK-means、RK-Medoids-KL 3種算法的召回率相差不大，且都維持了較高的水平（介于0.6～0.7之間），因此可以認為這3種方法的聚類質量較高，其中K-Medoids-KL算法的準確率最高，達到0.76。3）采用相對熵相似性的算法中，基于劃分算法的聚類準確率優于基于密度的算法；采用期望距離的劃分算法聚類準確率優于采用模糊距離函數的密度算法。

圖7 氣象數據聚類結果Fig.7 The clustering results of climate dataset

2.3 模擬與實際實驗結果分析

下面基于模擬與實際數據實驗結果，對進行測試的6種不確定聚類算法性能進行系統的總結與分析：1）RK-Medoids-KL與 FOPTICS算法的聚類質量對數據維數、對象個數及采樣個數較為敏感，其原因在于：RK-Medoids-KL算法在代表對象交換階段隨機選取能優化當前聚類結果的非代表對象與代表對象進行交換，且不能優化結果的非代表對象也具有較小的交換概率，因此RK-Medoids-KL算法的結果具有隨機性；FOPTICS算法采用模糊距離函數度量對象間的相似性，對幾何空間高度重疊的簇區分能力有限，同時設置聚類參數獲得k個簇的過程亦存在隨機性。各算法聚類質量均隨簇個數k的增加而降低，說明當前算法挖掘較為細致聚類模式的能力尚有欠缺。2）整體上，采用相對熵相似性的聚類算法聚類質量最高，采用模糊距離相似性度量的算法次之，采用期望距離相似性度量的算法聚類質量最差。這一實驗結果說明：相對熵可以同時顧及不確定對象在幾何空間和概率分布上的差異性，而期望距離僅僅利用了每個不確定對象的中心信息，缺乏區分概率分布差異性的能力。模糊距離能夠獲取數據集中更多的不確定信息，能夠在一定程度上區分不確定數據的概率分布差異性。3）實驗結果發現，采用相對熵相似性度量的方法中，基于劃分的算法（如RK-Medoids-KL和K-Medoids-KL）聚類質量要整體優于基于密度的算法（如DBSCAN-KL算法和OPTICS-KL）。當前研究一般認為基于密度算法的聚類質量要優于基于劃分的算法［6］，本文實驗結果得出相反結論可能有兩方面原因：一方面本文實驗中輸入參數k是已知的，而DBSCAN-KL算法和OPTICS-KL算法是通過將μ設置為5，并設置多個ε值進行實驗，以近似得到k個簇，不合理的參數設置可能會導致基于密度的算法的聚類質量低于基于劃分的算法；另一方面本文實驗中所采用的模擬數據與實際數據在概率空間內簇間存在相互鄰接的特點，將直接導致基于密度的算法聚類質量下降。4）在實際數據集中，雖然K-Medoids-KL算法的聚類質量最高，但是其聚類結果與K?ppen-Geiger氣候分類依然存在一定的偏差，其主要原因可能存在于兩方面：一方面在于氣候分區不僅考慮氣溫、降水、濕度的差異，還要綜合顧及其他氣候特征；另一方面簇的形態可能并非完全近似球形。本文研究對數據驅動下的氣候分區可靠性給出了定量的實驗結果。

綜合上述實驗結果與分析，可以進一步對不確定聚類方法在地學問題中的研究與應用給出如下建議：1）在實際研究中，由于簇的形態與結構是事先未知的，因此建議采用不同的不確定聚類算法進行比較分析，目前采用相對熵相似性度量的方法聚類質量相對較高；2）理論上基于密度的方法比基于劃分的方法適用性更強，不僅可以發現近似球形的簇，亦可發現非球形的簇，然而現有基于密度的方法的聚類質量反而不如基于劃分的方法，對于基于密度的方法如何選取合適的聚類參數、克服簇的鄰接等問題需要開展深入研究。

3 總結與展望

本文針對不確定數據聚類算法在地學應用中的有效性缺乏客觀比較的問題，選取了6種具有代表性算法，首先采用模擬數據進行測試，進而采用亞洲氣候數據集對其識別氣候區的能力進行比較分析。通過準確率和召回率定量度量6種方法處理幾何空間高度重疊、概率分布差異顯著的模擬數據與氣候數據時的聚類質量后，發現：1）對于同類型聚類算法，采用相對熵相似性度量的算法聚類質量總體優于采用期望距離和模糊距離函數的算法；2）采用相對熵相似性度量的劃分算法聚類質量優于基于密度的算法，其中K-Medoids-KL算法聚類質量最高。

進一步的研究工作主要集中在兩方面：1）本文僅是從數據本身的不確定性出發，對各種聚類算法的應用效果進行了實驗分析，未來研究中聚類模型本身的不確定性需要引起充分的重視；2）氣候分區的實際應用中，雖然基于概率分布相似性的劃分聚類算法能夠取得較好的結果，但是需要用戶輸入簇的個數，這是一般用戶很難確定的，因此需要進一步學習如何確定數據集中簇的個數。

［1］ CHENG R，KALASHNIKOV D V，PRABHAKAR S.Evaluating probabilistic queries over imprecise data［A］.Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data［C］.2003.551－562.

［2］ JIANG B，PEI J，TAO Y F，et al.Clustering uncertain data based on probability distribution similarity［J］.IEEE Transactions on Knowledge and Data Engineering，2013，25（4）：751－763.

［3］ AGRAWAL R，SRIKANT R.Privacy－preserving data mining［A］.ACM SIGMOD Conference，2000.

［4］ KRIEGEL H P，PFEIFLE M.Density-based clustering of uncertain data［A］.Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining［C］.2005.672－677.

［5］ SHI W Z.Principles of Modeling Uncertainties in Spatial Data and Spatial Analyses［M］.London：CRC Press，2010.

［6］ 鄧敏，劉啟亮，李光強，等.空間聚類分析及應用［M］.北京：科學出版社，2011.

［7］ SATO M，SATO Y，JAIN L C，et al.Fuzzy Clustering Models and Applications［M］.Physica-Verlag，1997.

［8］ DENG M，LIU Q L，CHENG T，et al.An adaptive spatial clustering algorithm based on Delaunay triangulation［J］.Computers，Environment and Urban Systems，2011，35（4）：320－332.

［9］ MACQUEEN J.Some methods for classification and analysis of multivariate observations［A］.Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability［C］.1967.281－297.

［10］ KAUFMAN L，ROUSSEEUW P.Clustering by Means of Medoids［M］.North-Holland，1987.

［11］ CHAU M，CHENG R，KAO B，et al.Uncertain data mining：An example in clustering location data［A］.Advances in Knowledge Discovery and Data Mining［C］.Springer Berlin Heidelberg，2006.199－204.

［12］ NGAI W K，KAO B，CHUI C K，et al.Efficient clustering of uncertain data［A］.Proceedings of the 6th International Conference on Data Mining［C］.2006.436－445.

［13］ LEE S D，KAO B，CHENG R.Reducing UK-means to K-means［A］.Proceedings of the 7th IEEE International Conference on Data Mining Workshops［C］.2007.483－488.

［14］ KAO B，LEE S D，LEE F K F，et al.Clustering uncertain data using Voronoi diagrams and r-tree index［J］.IEEE Transactions on Knowledge and Data Engineering，2011，22（9）：1219－1233.

［15］ ESTER M，KRIEGEL H P，SANDER J，et al.A density-based algorithm for discovering clusters in large spatial databases with noise［A］.Proceedings of KDD－96［C］.1996.226－231.

［16］ ANKERST M，BREUNIG M M，KRIEGEL H P，et al.Optics：Ordering points to identify the clustering structure［A］.Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data［C］.1999.49－60.

［17］ KRIEGEL H P，PFEIFLE M.Hierarchical density-based clustering of uncertain data［A］.Proceedings of the 5th IEEE International Conference on Data Mining［C］.IEEE，2005.

［18］ PEEL M C，FINLAYSON B L，MCMAHON T A.Updated world map of the K?ppen-Geiger climate classification［J］.Hydrology ＆Earth System Sciences Discussions，2007，4（2）：439－473.