不確定聚類中距離計算方法綜述

胡 明， 唐東凱， 李芬田， 王澤儒

(1.長春工程學院， 吉林 長春 130012；2.長春工業大學 計算機科學與工程學院， 吉林 長春 130012)

不確定聚類中距離計算方法綜述

胡 明1,2， 唐東凱2*， 李芬田2， 王澤儒2

(1.長春工程學院， 吉林 長春 130012；2.長春工業大學 計算機科學與工程學院， 吉林 長春 130012)

基于概率模型，將不確定聚類算法分為基于概率模型和缺失概率模型，并分別總結了距離的計算方式。

不確定聚類； 相似性度量； 概率模型； 距離公式

0 引 言

不確定性普遍存在于數據中，是數據的固有屬性[1]。在對不確定數據進行聚類時需要考慮其不確定性，否則會出現誤差，如圖1所示。

圖1(a)原始數據集被分為3個簇(a,b,c)。圖1(b)不考慮數據的不確定性進行聚類得到簇a′,b′,c′和c″。圖1(c)不確定性被考慮時，分為簇a′,b′和c，聚類結果比圖1(b)更接近圖1(a)。

(a) 數據集

(b) 確定聚類

(c) 不確定聚類

確定數據聚類算法可以使用確定距離計算方式(如歐式距離)作為兩個對象之間的相似度度量以指導整個聚類過程，但不確定數據的特點是每個數據對象都是由多個數據點表示，不再是單個數據點[2-4]。這就使得不確定數據的聚類不能使用傳統的距離公式來進行聚類，因此，不確定數據聚類的主要難點就是如何計算不確定數據對象之間的距離。

在不確定數據聚類中，常將不確定性數據細分為存在級不確定性(Existential Uncertainty)和屬性值不確定性(Attribute Level Uncertainty)[5]。存在級不確定性由一個概率值來表示該元組存在的可能性大小，屬性值不確定性是指每個元組屬性具有多個可能的取值，且多個取值滿足某種分布(如高斯分布等)，用概率密度函數來表示。上述兩種類型的不確定數據都涉及到概率或概率分布，可以看作是基于概率模型。但在實際應用中，很難事先知道不確定數據的概率分布，而分布的范圍很容易知道，這種類型的不確定性數據可以看作是缺失概率模型的。

文中主要討論基于概率模型和缺失概率模型兩種形式的不確定聚類，總結其中的距離計算方式。

1 基于概率模型的不確定聚類中距離計算

在概率模型中，相當于在確定數據對象的維度中增加了一個概率維，在存在級不確定數據中該概率維表示該元組的存在概率，在屬性級不確定數據中由概率密度函數來表示。因此，需要考慮到不確定對象的概率或概率密度函數，才能很好地保留數據的不確定性，得到高質量的聚類結果。

1.1 屬性值不確定聚類中距離計算

屬性值不確定聚類用概率密度函數來表示數據的不確定性。文中采用孫吉貴[6]等對聚類算法的分類方式，將不確定聚類方式分為基于劃分、基于密度和基于相似概率分布，并將從以上3個方面對屬性值不確定聚類中的距離計算方式進行介紹。

1.1.1 基于劃分的不確定聚類中距離計算

基于劃分的不確定聚類算法主要有uk-means[7]、uk-medoids[8]以及uk-means的變形ck-means[9]。假設D={o1,o2,...,on}為m維不確定數據集，C={C1,C2,…,Ck}為k個不同的簇，fi(x)為不確定對象oi的概率密度函數，滿足fi(x)≥0,?x∈Rm且

在uk-means中，使用期望的平方作為距離函數，如下式：

簇心的計算如下：

在uk-means中,對于線性移動和自由移動的對象來說,計算期望的平方是容易的，但是當數據量變大時，積分的出現使得計算時間花費太大。因此，文獻[7]借鑒剛體力學上的轉動慣量以及平行軸定理對式(1)做了簡化，首先對于每個不確定對象oi，定義其質心

對于任何不確定對象oi和任何屬于Rm的點y都有：

只需要提前計算ki和ED(oi,ki)，就可以得到ED(oi,y)，不需要再次評估概率密度函數。

算法uk-means和ck-means在計算簇心的時候，都是使用一個單獨的點來代表整個簇，這對于不確定數據來說，丟失了一些信息，會對最終的聚類精度造成影響，因此Gullo F[8]等借鑒k-medoids的思想，使用一個不確定對象而不是一個確定的點來表示一個簇，提出了uk-medoids算法，針對屬性級不確定對象oi，oj的距離計算公式如下：

式中：dist(x,y)----x和y的距離(如歐式距離)。

由式(1)～式(5)可以看出，基于劃分的不確定聚類中的距離公式都是使用確定距離和概率密度函數的數值積分來計算的，其主要時間代價為數值積分的計算。

Wang K N[10]等在uk-means的基礎上討論了各種剪枝策略對計算效率的影響；肖宇鵬[11]等將ck-means的距離計算方法與模糊c-均值相結合，對模糊c-均值的目標函數做了擴展，使得模糊c-均值算法的聚類思想適用于不確定聚類；曹科研[12]等將uk-means算法中期望距離的計算方式運用到障礙空間中，并結合剪枝技術提出了適用于障礙空間中不確定聚類的算法；遲榮華[13]等利用改進的快速高斯變換方法獲取概率密度函數，減少了距離計算的時間；文獻[14]針對不同的概率密度函數討論了各自的距離計算方式，最終結合快速高斯模型提出了一種有效的距離公式。

1.1.2 基于密度的不確定聚類中距離計算

Kriegel[15]等最早提出基于密度的不確定聚類算法FDBSCAN，并在同一年改進了OPTICS算法，提出了FOPTICS算法[16]。在聚類的相似性度量上FDBSCAN和FOPTICS算法采用了距離分布函數，能夠體現出數據對象的概率密集程度。并對基于密度聚類中涉及到的核心對象概率和對象的可達概率做了重新定義。FDBSCAN算法采用距離分布函數描述數據的不確定性，如下：

Pd(o,o′)(b)=P(d(o,o′)≤b)=

其中，Pd(o,o′)為距離密度函數，且限制條件為

在式(7)數據集D中，A?D，當A中數據對象的數目大于或等于μ并且A中全部不確定數據對象到o的距離都小于或等于ε時，則稱A中數據對象的概率之和為數據對象o的核心概率對象。

FOPTICS算法與FDBSCAN算法一樣，都采用距離分布函數，唯一的不同就是FOPTICS是在模糊聚類算法OPTICS上擴展來的，采用的是模糊距離分布函數，如下：

由式(9)可得出模糊可達距離，如下：

其他基于密度的不確定聚類算法，如潘冬明[17]等借鑒相對密度算法的思想，重新定義了不確定數據的距離公式；王洪朋[18]等結合信息熵和R*的概念，提出了新的距離計算公式以及不確定聚類算法PRE-DBSCAN；許華杰[19]采用R樹索引和概率閾值索引提高算法的效率。文獻[17-19]都是以FDBSCAN和FOPTICS算法的距離計算公式為基礎的，聚類方式相同。

1.1.3 基于相似概率分布的不確定聚類中距離計算

1.1.1和1.1.2中涉及的算法只是研究數據對象的幾何屬性，并且將研究的焦點放在不確定對象的實例上，他們并沒有考慮到不確定對象之間的相似性。

概率分布和幾何位置如圖2所示。

(a) 不同均值的數據對象 (b) 相同均值的數據對象

假設不確定對象obj1服從均勻分布，obj2服從高斯分布，如果兩個不確定對象有相同的均值(見圖2(b))，很顯然，obj1和obj2的幾何位置嚴重重疊，但實際上卻是兩個不同的簇。在基于劃分的不確定聚類中，由式(1)～式(5)可以看出,只有對象的中心被考慮。而在本節的假設中，obj1和obj2有相同的中心，式(1)～式(5)無法對這種具有不同分布規律的對象集進行有效的聚類。基于密度的不確定數據聚類方法的基本思想是將密集程度大的對象集合在一起，變成一個簇，兩個不同的簇之間由稀疏區域分隔，然而在本節的假設中，obj1和obj2嚴重重合，沒有稀疏區域可以將obj1和obj2分成兩個不同的簇，所以，基于密度的方法也不能在這種情形下有效工作。

針對這種類型的不確定數據，Jiang B[20]等提出使用KL-散度(Kullback-Leibler divergence)來作為不確定對象的相似性度量，KL-散度是統計獨立性的最佳度量，不但能很好地區分圖2(b)中的兩個嚴重重疊的不同的簇，而且對于圖2(a)的情況也能很好地解決。下面給出KL-散度在相似概率分布中具體應用。

當不確定對象的屬性值離散時，假設f和g是離散域D中兩個不確定對象的概率質量函數，那么不確定對象間的KL距離定義為：

當不確定對象的屬性值連續時，假設f和g分別表示連續域D中兩個不確定對象的概率密度函數，那么不確定對象間的KL距離定義為：

王建榮[21]在文獻[12]的基礎上進行了改進，由于D(f‖g)不具有對稱性，所以做了如下變換：

KL-散度不僅適用于相似概率分布，也同樣可以擴展到基于劃分的不確定聚類算法和基于密度的不確定聚類算法中。

1.2 存在級不確定聚類中距離計算

存在級不確定數據是基于概率模型的另一種表現方式，每個元組都有一個概率值來表示該元組。文獻[21]對不確定元組做了如下定義：

定義3(不確定元組集) 不確定數據集D是一個由相互獨立的d維不確定元組(Xi,pi)構成的集合，D={(X1,p1),(X2,p2),…,(Xn,pn)}，其中,Xi是第i個元組的值，pi是該元組的存在概率，0≤pi<1。

由定義3可知，每個不確定對象都有一個概率值，傳統的距離計算方式沒有考慮到概率值，僅能用于確定數據之間，為了不丟失數據的不確定屬性，必須將元組的不確定性包含在距離度量中。文獻[22]結合歐式距離提出了一種針對存在級不確定數據的度量方式。

定義4(不確定相異度) 不確定相異度dsij指兩個不確定元組(Xi,pi)和(Xj,pj)之間的相異程度，其公式如下：

式(14)不僅考慮了兩個不確定元組之間的確定距離，而且包含了兩個不確定元組的存在概率。各個不確定元組之間的概率越接近，它們的相異度越小，相似度就越大，就越有可能屬于同一類，反之則屬于不同的簇。

2 基于缺失概率模型的不確定聚類中距離計算

以上討論的都是基于概率模型進行不確定聚類，而在實際應用中，事先很難知道數據的概率分布情況。對于這種形式的不確定數據主要有兩種形式來表示：區間數和三角模糊數，它們都不需要事先知道數據的分布情況，很容易應用到多個領域。

2.1 基于區間數的不確定聚類中距離計算

文獻[23]對區間數的定義如下：

定義5(區間數) 給定AL,AR∈Rd且AR≥AL，稱集合：A=[AL,AR]?{u|AL≤AR}為一個區間數，其中AL為區間數的下界，AR為區間數的上界。當AL=AR，即上下界相等時，區間數變為確定的數。

定義6(區間數的距離) 對于給定的區間數，X=[XL,XR]，Y=[YL,YR]，它們之間的距離為：

d(X,Y)= ‖X-Y‖=

由式(16)可以看出，使用區間數來表示不確定數據，進行聚類時，可以避免大量的積分運算，有效降低算法的時間復雜度。

2.2 基于三角模糊數的不確定聚類中距離計算

在不知道數據的概率密度函數時，除了區間數之外，三角模糊數也可以表示不確定數據。記R+為正實數集，F(R+)為全體正模糊數集，R為實數集，F(R)為全體模糊數集，下面給出三角模糊數的定義：

定義7(三角模糊數) 設α=(l,m,u)為三角模糊數；其中，α∈F(R)，l和u分別為α的上界和下界；(m-l)和(u-m)分別為α的下限和上限，m為三角模糊數α的主值，是可能性最大的值。

對于給定的三角模糊數α=(mα-xα,mα,mα+yα)，β=(mβ-xβ,mβ,mβ+yβ)，其中mα，xα，yα，mβ，xβ，yβ∈R，在任意維度j(1≤j≤d)上，這兩個三角模糊數之間的距離都有相離、相接、相交、相含4種狀態。4種狀態中在每一維上的最大和最小距離分別為：

根據以上定義，陸億紅[25-26]等重新定義了兩個d維的三角模糊數之間的距離，如下：

D= [Dmin,Dmid,Dmax]=

式(20)為三角模糊數的距離公式，此時計算出來的三角模糊數之間的距離仍是一個三角模糊數，保留了數據的不確定性。為了將距離度量有效地運用于不確定聚類，文獻[15]將式(20)做了變換，得到兩個三角模糊數之間的距離，其表達式為：

3 結 語

從概率模型的角度出發，將不確定數據聚類分為兩類：基于概率模型的不確定聚類和缺失概率模型的不確定聚類。在概率模型中，都是用數據概率密度函數或者概率質量函數來表示不確定性，由于概率的存在，在這類的不確定聚類中距離計算大多使用期望距離及其變形或KL-散度。而對于事先不知道概率模型的不確定數據來說，使用區間數和三角模糊數可以很好地計算其不確定對象之間的距離。在實際應用中，應根據不確定數據的類型選擇合適的距離計算函數。

[1] 王梁,周光焱,王黎維,等.不確定關系數據屬性級溯源表示與概率計算[J].軟件學報,2014,25(4):863-879.

[2] 范麗文.基于無線傳感器網絡不確定數據的HPDBSCAN算法研究[D].南昌：江西理工大學,2013.

[3] 張亞昕.不確定數據聚類算法研究[J].計算技術與自動化,2013,32(2):60-63.

[4] 孫佳,胡明,趙佳.K-means初始聚類中心選取優化算法[J].長春工業大學學報,2016,37(1):25-29.

[5] 周傲英,金澈清,王國仁,等.不確定性數據管理技術研究綜述[J].計算機學報,2009,32(1):1-16.

[6] 孫吉貴,劉杰,趙連宇.聚類算法研究[J].軟件學報,2008,19(1):48-61.

[7] Chau M, Cheng R, Kao B, et al. Uncertain data mining: An example in clustering location data[C]//Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining. Springer-Verlag： [s.n.],2006:199-204.

[8] Gullo F, Ponti G, Tagarelli A. Clustering uncertain data via k-medoids[C]// International Conference on Scalable Uncertainty Management. Springer-Verlag： [s.n.],2008:229-242.

[9] Lee S D, Kao B, Cheng R. Reducing uk-means to k-means[C]// IEEE International Conference on Data Mining Workshops. [S.l.]: IEEE Computer Society,2007:483-488.

[10] Wang K N, Kao B, Chui C K, et al. Efficient clustering of uncertain data[M]. [S.l.]: IEEE,2006.

[11] 肖宇鵬,何云斌,萬靜,等.基于模糊C-均值的空間不確定數據聚類[J].計算機工程,2015,41(10):47-52.

[12] 曹科研,王國仁,韓東紅,等.障礙空間中不確定數據聚類算法[J].計算機科學與探索,2012,12(6):1087-1097.

[13] 遲榮華,程媛,朱素霞,等.基于快速高斯變換的不確定數據聚類算法[J].通信學報,2017,38(3):101-111.

[14] Xiao L, Hung E. An efficient distance calculation method for uncertain objects[C]//Computational Intelligence and Data Mining, 2007. CIDM 2007.IEEE Symposium on. [S.l.]: IEEE,2007:10-17.

[15] Kriegel H P, M Pfeifle. Density-based clustering of uncertain data[C]//Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2005:672-677.

[16] Kriegel H P, Pfeifle M. Hierarchical density-based clustering of uncertain data[C]//Eleventh ACM SIGKDD International Conference on Discovery in Date Mining ACM.2005:689-692.

[17] 潘冬明,黃德才.基于相對密度的不確定數據聚類算法[J].計算機科學,2015(b11):72-74.

[18] 王洪朋.一種基于密度的不確定性數據聚類算法[D].哈爾濱:哈爾濱工程大學,2015.

[19] 許華杰,李國徽,楊兵,等.基于密度的不確定性數據概率聚類[J].計算機科學,2009,36(5):68-71.

[20] Jiang B, Pei J, Tao Y, et al. Clustering uncertain data based on probability distribution similarity[J].IEEE Transactions on Knowledge & Data Engineering,2013,25(4):751-763.

[21] 王建榮.基于概率分布相似性的不確定數據聚類算法研究[D].西安：西安電子科技大學，2014.

[22] 王曉偉,賈焰,楊樹強,等.存在級不確定數據上的概率Skyline計算[J].計算機研究與發展,2011,48(1):68-76.

[23] 陸億紅,夏聰.不確定數據的最優K近鄰和局部密度聚類算法[J].控制與決策,2016(3):541-546.

[24] 彭宇,羅清華,王丹,等.基于區間數聚類的無線傳感器網絡定位方法[J].自動化學報,2012,38(7):1190-1199.

[25] 何云斌,張志超,萬靜,等.不確定數據聚類的U-PAM算法和UM-PAM算法的研究[J].計算機科學,2016,43(6):263-269.

[26] 陸億紅,翁純佳.基于三角模糊數的不確定性數據聚類算法[J].浙江工業大學學報,2016,44(4):405-409.

Summaryofdistancecalculationformulaforuncertainclusteringalgorithm

HU Ming1,2, TANG Dongkai2*, LI Fentian2, WANG Zeru2

(School of Computer Science & Engineering, Changchun University of Technology, Changchun 130012， China)

Based on probabilistic model, uncertain clustering algorithm is classified into model-based probability and model-missed. Here we also summarize the distance calculation formulas.

uncertain clustering; similarity measure; probability model; distance formula.

2017-07-18

吉林省科技廳重大科技招標專項(20160203010GX)； 吉林省發改委產業創新專項基金項目(20170505MA2)

胡 明(1963-)，男，漢族，吉林長春人，長春工程學院教授，博士，主要從事分布式計算、數據挖掘方向研究,E-mail:huming@ccut.edu.cn. *通訊作者：唐東凱(1992-)，男，漢族，河南商丘人，長春工業大學碩士研究生，主要從事數據挖掘方向研究,E-mail:tdkhkd@126.com.

10.15923/j.cnki.cn22-1382/t.2017.5.13

TP 311

A

1674-1374(2017)05-0477-07