基于模糊C-均值的空間不確定數據聚類

肖宇鵬，何云斌，萬 靜，李 松

（哈爾濱理工大學計算機科學與技術學院，哈爾濱 150080）

基于模糊C-均值的空間不確定數據聚類

肖宇鵬，何云斌，萬 靜，李 松

（哈爾濱理工大學計算機科學與技術學院，哈爾濱 150080）

針對現實世界中樣本對象的不確定性及樣本對象間界限劃分的模糊性，提出基于模糊C-均值的空間不確定數據聚類算法UFCM。但由于UFCM算法在聚類過程中涉及大量期望距離的復雜積分計算，導致UFCM算法性能不理想，進而給出改進算法I-UFCM，將空間不確定對象聚類問題轉化為傳統的確定對象聚類問題，采用相似度計算公式減少期望距離的計算量，提高聚類結果的質量。實驗結果表明，與UFCM和UK-Means算法相比，I-UFCM算法在空間不確定數據集上具有更好的聚類性能，CUP耗時降低了90%以上。

模糊C-均值；不確定數據；概率密度函數；期望距離；質心

DO I：10.3969/j.issn.1000-3428.2015.10.010

1 概述

近年來，隨著聚類分析研究的不斷深入，以及數據不確定性在實際應用中普遍存在，不確定數據受到越來越多的關注，因此分析和挖掘不確定數據成為當前研究的熱點［1-3］。目前，國內外學者多采用概率密度函數對不確定數據進行建模，并在此基礎上擴展現有聚類算法實現對不確定數據的聚類分析，例如基于K-M eans算法的UK-Means算法［4］、基于DBSCAN算法的FDBSCAN算法［5］等。但上述算法在衡量樣本間相似度時計算量大。針對該問題，文獻［6］提出一種基于Voronoi圖和R-tree的剪枝策略，但該策略在構造Voronoi圖和R-tree時會產生較大的時間開銷。文獻［7］依據物理學中剛體運動的轉動慣量思想，推導出一個相似度計算公式，其效率比傳統不確定聚類算法的效率有了較大提高。文獻［8］通過子空間劃分的方法進行聚類。文獻［9］在度量的基礎上，結合三角修剪法完成二維空間下不確定數據的聚類。文獻［10］通過不確定中心點的計算實現不確定數據的劃分。但是上述算法均未考

慮樣本間界限劃分模糊的問題。

考慮到現實世界中樣本對象的不確定性和樣本間界限劃分的模糊性，使得樣本對象更適合軟劃分。因此，使用模糊聚類來分析數據的不確定性更符合實際情況。其中，模糊C-均值算法是應用最廣泛的一種聚類分析方法。該方法依據某個隸屬度來劃分樣本對象，從而使得類內誤差平方和目標函數最小。然而，文獻［11-12］研究表明：算法易受到初始點和噪聲數據的影響，并且在處理不同密度樣本數據時存在較大誤差。對此國內外研究者基于不同理論提出一系列方法對算法進行改進，例如：文獻［12-13］提出基于核聚類和擴展高斯核聚類的算法；文獻［14］在模糊 C-均值算法中引入屬性權重的概念進行聚類分析；此外，還提出結合人工智能算法［15］和數理統計方法［16］優化模糊聚類算法。以上均是針對確定樣本空間數據處理，未考慮空間樣本的不確定性。

本文在綜合分析不確定數據聚類現狀和模糊C-均值算法的基礎上，給出基于模糊C-均值算法的空間不確定數據聚類算法（UFCM）。針對空間不確定數據模型在聚類時需要大量積分計算導致算法性能較差的問題，以及傳統歐氏距離在衡量樣本間相似度時存在的不足，在UFCM算法的基礎上提出改進的UFCM算法（I-UFCM）。

2 基于模糊C-均值的不確定數據聚類

2.1 模糊C-均值聚類算法

設數據集X=｛χ1，χ2，…，χn｝為m維空間的一組待聚類樣本向量，聚類樣本的c個類別為V=｛V1，V2，…，Vc｝，c個聚類簇的中心表示為ν=｛ν1，ν2，…，νc｝。用隸屬度矩陣 Uc×n=（uij），uij∈［0，1］表示每個樣本對各聚類簇的隸屬度，其中，i=1，2，…，c；j= 1，2，…，n。2個樣本對象 χi，χP之間的歐氏距離定義為：

模糊C-均值算法的目標函數為：

其中，m∈［1，∞）是一個加權指數，隨著 m的增大，聚類的模糊性增大。根據拉格朗日數乘法，求得使目標函數在滿足約束條件的前提下取得極小值的必要條件：

模糊C-均值聚類算法在聚類過程中通過反復迭代式（4）和式（5），使得目標函數式（2）不斷減少直至最小。

2.2 空間不確定數據聚類模型

數據的不確定性主要表現在數據是否存在不確定性和數據屬性級別的不確定性兩方面［10］。在空間不確定數據聚類中，通常使用屬性級別的不確定模型，即數據集中每個數據對象的屬性不再是確定的數據值，每個數據對象也不再是一個單獨的樣本點，而是通過一個概率密度函數（Probability Density Function，PDF）來定義不確定區域。概率密度函數詳細給出了空間中每個不確定對象可能的位置。

定義1（空間不確定數據） 在m維空間Rm中，給定一組不確定空間數據對象 O=｛o1，o2，…，on｝，距離函數d：Rm×Rm→R，對于每個不確定空間數據對象oi，都有一個概率密度函數fi：Rm→R定義不確定對象的分布。根據概率密度函數得到：

通過期望距離衡量不確定對象的相似度。

定義2（期望距離） 不確定空間對象oi和任意點 p的期望距離定義［7］：

由式（7）可得2個不確定空間樣本對象間的期望距離。

定義3（不確定對象間的期望距離） 不確定空間對象oi和oj間的期望距離為：

不確定空間數據的聚類分析是對給定的一組不確定對象O及有效聚類數目k，通過映射函數h：｛1，2，…，n｝→｛1，2，…，k｝將不確定對象劃分到k個聚類簇C=｛c1，c2，…，ck｝中。聚類簇 C中的每個ci為所屬簇的代表點。聚類最終使得簇內期望距離和達到最小。

2.3 空間不確定數據聚類算法

對于不確定空間數據對象集合O，聚類的c個類別為OV=｛OV1，OV2，…，OVc｝，c個不確定聚類簇中心對象為 oν=｛oν1，oν2，…，oνc｝。不確定空間數據模糊聚類的目標函數為：

其中，ED（oj，oνi）為2個不確定空間數據對象間的期望距離。根據拉格朗日數乘法，求得使目標函數在約束條件式（3）下取得極小值的必要條件為：

基于以上分析提出算法1，即基于模糊C-均值的不確定樣本空間數據聚類算法UFCM，具體描述如下：

算法1UFCM算法

輸入 n個待聚類的不確定空間樣本對象，有效劃分數目c，迭代次數t，最大迭代次數T，閾值θ

輸出 c個使誤差平方和準則最小的聚類簇

Step1 隨機選取c個不確定初始聚類中心；

Step2 循環；

Step2.1 根據式（10）計算不確定空間樣本的隸屬度矩陣U；

Step2.2 由式（11）和矩陣U計算新的不確定對象中心集合oν；

Step2.3 根據式（9）計算目標函數JUFCM，并且t=t+1；

Step4 由最終的隸屬度矩陣U劃分樣本。

UFCM算法在計算樣本隸屬度矩陣時需要計算不確定空間對象之間的期望距離ED。當不確定空間對象的數量較多或者概率分布函數較為復雜時，式（8）計算復雜、耗時長。此外，UFCM算法基于FCM算法發展而來，傳統的模糊C-均值算法在計算樣本點間相似度時采用歐氏距離作為衡量標準。這種標準計算方法具有一定局限性，易受到噪聲點的影響，并且在處理不同大小和密度樣本數據時存在較大的誤差。

3 改進的UFCM聚類算法

針對UFCM算法的不足，提出改進的基于模糊C-均值的聚類算法（I-UFCM）。改進算法通過特定轉換機制，將不確定空間對象用一個確定的空間樣本點表示，將不確定對象的聚類問題轉化為經典的確定數據對象的聚類問題。算法采用新的相似度計算公式衡量樣本間距，再加上有效的策略，改善傳統歐氏距離測定方法的不足，從而提高聚類結果的質量。

3.1 空間不確定數據聚類的確定化

將不確定空間數據確定化，即通過一個樣本點ki表示由一組樣本點所代表的不確定空間對象 oi，從而將n個不確定空間數據對象聚類問題轉化成n個確定空間數據對象的聚類問題。因此，為每個不確定空間對象定義其質心，也稱為期望中心。

定義4（不確定對象質心） 對于每個不確定空間對象 oi，oi的分布區域為 Rm，其質心 ki定義如下［8］：

依據物理學中剛體轉動慣量思想及依此推導出的平行軸定理，對于空間任意不確定對象 oi及不確定空間中任意點 χP，根據質心式（12）和期望距離式（7）定義新的期望距離計算公式為：

ED（oi，χP）=ED（oi，ki）+D ist（χP，ki） （13）

可見，新的期望距離計算公式只需計算出ED（oi，ki）及Dist（χP，ki），即可快速便捷地計算出ED（oi，χP），從而省去多次計算概率密度函數。

因此，對于不確定空間數據模糊聚類，可以用c個聚類簇中心點ν=｛ν1，ν2，…，νc｝代替原有的c個不確定聚類簇中心對象。此時，不確定空間數據模糊聚類目標函數JUFCM為：

其中，νh（i）表示映射函數h下的聚類簇中心點。對于每一個空間不確定對象oi及其密度函數fi都是定量。因此無需反復計算對象的期望中心距離 ED（oj，kj），并且ED（oj，kj）可事先計算得出且保持不變。因此，ED（oj，kj）可用 M表示，此時目標函數為：

可見，只需給出每個空間不確定對象的質心 kj，而無需考慮每個不確定空間對象的 ED（oj，kj），即可求出目標函數在式（3）約束條件下的極小值。

3.2 相似度計算公式

在處理不同大小和密度樣本或有噪聲存在的數據時，傳統歐式距離存在較大誤差［15］。特別是在每次計算聚類簇中心點時，簇中心極易受到簇中樣本數據分布密度的影響。由于不確定空間數據整體分布的不確定性，傳統的歐氏距離計算方法不適宜應用于不確定數據聚類問題。

本文采用新的樣本間相似度衡量標準，即對一組空間樣本數據集 X=｛χ1，χ2，…，χn｝有［16］：

其中，β基于統計學知識且由樣本數據集計算得出，其定義式為：

采用新的相似度計算公式，將I-UFCM算法的模糊聚類目標準則函數改寫為：

同樣，式（15）以式（3）為約束條件構造拉格朗日函數，并求其取得極小值的必要條件為：

3.3 I-UFCM聚類算法

I-UFCM算法計算每個不確定空間對象的質心，并將其質心存入 K中，此外，改進算法選用新的相似度度量標準衡量樣本間相似度。I-UFCM算法的具體描述如下：

算法2 I-UFCM算法

輸入 n個待聚類的不確定空間樣本對象，有效劃分數目c，迭代次數t，最大迭代次數T，閾值θ

輸出 c個使聚類目標函數最小的聚類簇

Step1 根據式（12）計算每個不確定空間對象的質心，K=ki∪K；

Step2 令t=0，并初始化初始聚類中心點集合，即構造集合 ν=｛ν1，ν2，…，νc｝；

Step3 循環；

Step3.1 根據式（19）計算空間樣本ki的隸屬度矩陣U；

Step3.2 根據式（20）和隸屬度矩陣U計算新的樣本中心集合ν；

Step3.3 根據式（18）計算每次劃分的目標函數JI-UFCM，并且t=t+1；

Step5 由最終的隸屬度矩陣U劃分樣本。

對于n個空間不確定對象，I-UFCM算法首先通過計算式（12），花費O（n）的時間復雜度即可得到n個不確定樣本對象的質心。此后，在聚類過程中，I-UFCM算法采用新的相似度衡量準則，其時間復雜度為O（nct），其中，n為不確定空間樣本對象的質心；c為聚類劃分數；t為算法有效迭代次數。

4 實驗結果與分析

本文分別采用UCI數據集和人工模擬數據集對UFCM算法和I-UFCM算法進行實驗，并與傳統的UK-Means不確定聚類算法進行對比。實驗采用F-measure（F）作為聚類外部評測標準，同時從類間距和類內距出發，采用內部評測標準評測聚類效果。

4.1 不確定數據集的構造

實驗中所采用的UCI數據集的特征參數如表1所示。

表1 UCI實驗數據集的特征參數

為在UCI基礎數據集的基礎上構造不確定數據集，需要添加一個不確定數據生成策略。為每個數據源中的樣本數據定義一個概率密度函數fi，使每一個樣本對象由一組樣本點來表示，而每個樣本點都對應一個概率值，即每一個樣本對象oi，有：

其中，ωim為不確定對象oi的一個樣本點；fi（ωim）是與每個樣本相對應的概率

此外，為對比算法性能，需構造一組人工模擬數據集。人工模擬數據是在二維空間［0，l］×［0，l］中生成n個空間不確定對象的數據集。對于每一個不確定對象 oi，在邊長 d的正方形包圍框中，隨機生成m個樣本點，并且為每個樣本點賦一個介于0和1之間的均勻分布概率值。將 m個樣本點的概率值標準化，使其總和為1。從而構造一組在［0，l］×［0，l］中的 n個二維空間不確定對象的數據集。

4.2 結果分析

實驗對傳統UK-Means算法及本文提出的UFCM算法、I-UFCM算法分別進行50次獨立聚類實驗，記錄每次實驗結果，求其平均值并對比3個算法的實驗結果，如表2所示。在表2中，F-AVG（C，C～）為聚類外部評測標準F-measure（F）指標，其值越高則說明算法聚類的效果越好；Q-AVG（C）為類內距和類

間距的指標合并，即Q（C）=intra（C）-inter（C）。由于將類內距intra（C）和類間距inter（C）標準化后其范圍均在［0，1］內，因此 Q（C）取值范圍在［-1，1］之間。

表2 聚類算法有效性對比

結果顯示，對Iris，Wine和Glass 3組數據集的空間不確定對象的聚類劃分中，UFCM算法和I-UFCM算法的F平均指標及Q平均指標均高于傳統UK-Means算法。對于Balance數據集，UFCM算法的聚類 F平均指標及 Q平均指標略低于UK-Means算法。而改進后的I-UFCM算法在對Balance數據集的實驗中，表現出更優越的聚類能力，其F平均指標和Q平均指標都高于UK-Means算法和UFCM算法。

此外，構造多個人工模擬2D空間不確定數據集測試算法的性能。對于有效聚類數k值及不確定樣本對象具有相同的 m個樣本點時，為公平地評價算法性能，假設3個算法在聚類初始時均選取一致的初始聚類中心點。圖1反映了在有效聚類數k值確定的情況下，3個算法在不同規模的樣本數下的CPU耗時情況。

圖1 有效聚類數相同情況下的CPU耗時

圖1顯示本文提出的UFCM算法與UK-Means算法的耗時大體一致。而改進后的I-UFCM算法由于簡化了期望距離ED的計算復雜度，其CPU耗時相比傳統UK-Means算法和UFCM算法降低了90%以上。此外，IUFCM算法的耗時基本花費在計算不確定樣本對象的質心上，然而不確定空間對象質心的計算只需一次。一旦不確定樣本數據的質心計算完成，算法只需花費很少的時間完成空間聚類。

在空間不確定對象數量n和有效聚類數k值確定的情況下，圖2給出每個不確定樣本對象 oi在不同樣本數m下，3個算法的CPU耗時情況。同樣，在初始聚類時 3種算法均選取一致初始聚類中心點。

圖2 空間不確定對象數相同情況下的CPU耗時

由圖2可知，當每個空間不確定對象 oi的樣本數m增大時，3個算法的CPU耗時也隨之增加。在計算每個不確定空間對象oi時，改進后的I-UFCM算法的計算量和質心計算隨著樣本點數m的增加而增大。當質心一旦確定，空間不確定對象聚類問題就可簡化成精確點的聚類問題，因此，I-UFCM算法的CPU耗時仍小于傳統UK-Means算法和UFCM算法。

5 結束語

本文在模糊C-均值聚類的基礎上，提出面向空間不確定數據的聚類算法UFCM。然而由于空間不確定對象模型的復雜度高，UFCM算法在聚類過程中涉及大量期望距離的復雜積分計算，導致UFCM算法性能不理想，進一步給出改進的I-UFCM算法。I-UFCM算法將不確定空間聚類問題確定化，使用新的相似度衡量方式彌補傳統歐氏距離的不足，并通過實驗結果驗證了I-UFCM的正確性，并表明其對空間不確定數據聚類的研究具有借鑒作用。下一步將對基于連續性概率密度函數的不確定數據聚類分析進行相關研究。

［1］ 張志兵.空間數據挖掘及其相關問題研究［M］.武漢：華中科技大學出版社，2011.

［2］ Aggarwal C C，Yu P S.A Survey of Uncertain Data Algorithm s and Applications［J］.IEEE Transactions on Know ledge and Data Engineering，2009，21（5）：609-623.

［3］ Jiang Bin，Pei Jian，Tao Yufei，et al.Clustering Uncertain Data Based on Probability Distribution Similarity［J］. IEEE Transactions on Know ledge and Data Engineering，2013，25（4）：751-763.

［4］ Chau M，Cheng R，Kao B，et al.Uncertain Data Mining：An Example in Clustering Location Data［C］// Proceedings of PAKDD’06.Berlin，Germ any：Springer，2006：199-204.

［5］ Kriegel H P，Pfeifle M.Density-based Clustering of Uncertain Data［C］//Proceedings of the 11th ACM SIGKDD International Conference on Know ledge Discovery in Data Mining.New York，USA：ACM Press，2005：672-677.

［6］ Kao B，Lee S D.Clustering Uncertain Data Using Voronoi Diagrams and r-tree Index［J］.IEEE Transactions on Know ledge and Data Engineering，2010，22（9）：1219-1233.

［7］ Lee S D，Kao B，Cheng R.Reducing UK-means to K-means［C］//Proceedings of the 7th IEEE International Conference on Data Mining Workshops.Washington D.C.，USA：IEEE Press，2007：483-488.

［8］ Günnemann S，Kremer H，Seidl T.Subspace Clustering for Uncertain Data［C］//Proceedings of 2010 SIAM International Conference on Data Mining.［S.l.］：Society for Industrial and Applied Mathematics，2010：385-396.

［9］ Ngai W K，Kao B，Cheng R，et al.Metric and Trigonometric Pruning for Clustering of Uncertain Data in 2D Geometric Space［J］.Information Systems，2011，36（2）：476-497.

［10］ Gullo F，Tagarelli A.Uncertain Centroid Based Partitional Clustering of Uncertain Data［J］.Proceedings of the VLDB Endowment，2012，5（7）：610-621.

［11］ Nazari M，Shanbehzadeh J，Sarrafzadeh A.Fuzzy C-means Based on Automated Variable Feature Weighting［C］//Proceedings of International Multi Conference of Engineers and Computer Scientists.Calgary，Canada：International Association of Engineers，2013：13-15.

［12］ Ramathilagam S，Huang Yueh-Min.Extended Gaussian Kernel Version of Fuzzy C-means in the Problem of Data Analyzing［J］.Expert System s with Applications，2011，38（4）：3793-3805.

［13］ 王 亮，王士同.基于成對約束的動態加權率監督模糊核聚類［J］.計算機工程，2012，38（1）：148-150.

［14］ 王麗娟，關守義，王曉龍，等.基于屬性權重的Fuzzy CMean算法［J］.計算機學報，2006，29（10）：1797-1802.

［15］ Qu Jianhua，Shao Zengzhen，Liu Xiyu.Mixed PSO Clustering Algorithm Using Point Symmetry Distance［J］.Journal of Computational Information Systems，2010，6（6）：2027-2035.

［16］ Wu Kuo-Lung，Yang Miin-Shen.Alternative C-means Clustering Algorithms［J］.Pattern Recognition，2002，35（10）：2267-2278.

編輯陸燕菲

Clustering of Space Uncertain Data Based on Fuzzy C-means

XIAO Yupeng，HE Yunbin，WAN Jing，LI Song
（School of Computer Science and Technology，Harbin University of Science and Technology，Harbin 150080，China）

Aiming at the uncertainty of sample object in real world and the fuzzy boundary between sample objects，this paper proposes a Uncertain Fuzzy C-Means（UFCM）algorithm.Because of a lot of complex integral calculation in expected distance computation，UFCM algorithm is inefficiency.Further，an improved algorithm called I-UFCM is proposed.In this algorithm，the spatial uncertain objects are transformed into the traditional certain objects for clustering. Besides，a new formula for calculation similarity is introduced instead of traditional Euclidean norm to evaluate the distance between objects.The quality of clustering results is improved by reducing the computational amount of excepted distance.Experimental results demonstrate the clustering performance of I-UFCM algorithm is more effective than UFCM and UK-Means algorithm，and its CPU time is reduced by 90%.

fuzzy C-means；uncertain data；probability density function；excepted distance；centroid

肖宇鵬，何云斌，萬 靜，等.基于模糊 C-均值的空間不確定數據聚類［J］.計算機工程，2015，41（10）：47-52.

英文引用格式：Xiao Yupeng，He Yunbin，Wan Jing，et al.Clustering of Space Uncertain Data Based on Fuzzy C-means［J］.Computer Engineering，2015，41（10）：47-52.

1000-3428（2015）10-0047-06

A

TP18

黑龍江省自然科學基金資助項目（F201014，F201134，F201302）；黑龍江省教育廳科學技術研究基金資助項目（12531120，12541128，12511100）。

肖宇鵬（1986-），男，碩士，主研方向：空間數據挖掘；何云斌（通訊作者），教授；萬 靜，教授、博士；李 松，副教授、博士。

2014-09-24

2014-11-13E-m ail：pengF-14@163.com