胡健　蘇書賓　毛伊敏

摘要：維度災(zāi)難、含有噪聲數(shù)據(jù)和輸入?yún)?shù)對領(lǐng)域知識的強(qiáng)依賴性，是不確定數(shù)據(jù)聚類領(lǐng)域中具有挑戰(zhàn)性的問題。針對這些問題，基于相似性度量和凝聚層次聚類思想的基礎(chǔ)上提出了高維不確定數(shù)據(jù)高效聚類HDUDEC（High Dimensional Uncertain Data Efficient Clustering）算法。該算法采用一個能夠準(zhǔn)確表達(dá)不確定高維對象之間的相似度的度量函數(shù)計算出對象之間的相似度，然后根據(jù)相似度閾值自底向上進(jìn)行聚類分析。實(shí)驗(yàn)證明新的算法需要的先驗(yàn)知識較少、可以有效地過濾噪聲數(shù)據(jù)、可以高效的獲得任意形狀的高維不確定聚類結(jié)果。

關(guān)鍵詞：高維不確定對象；凝聚層次聚類；相似性度量；不確定聚類.

中圖分類號：TP391.9 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2014）04-0673-04

不確定數(shù)據(jù)是由于不確定的測量，過時的來源或者抽樣誤差等現(xiàn)實(shí)世界的應(yīng)用中涌現(xiàn)出來的一類新數(shù)據(jù)[1，2]。數(shù)據(jù)的不確定性可以分為存在級不確定性，位置不確定性，屬性不確定性等[3]。隨著電子信息時代的到來，現(xiàn)在對不確定數(shù)據(jù)的研究面臨的挑戰(zhàn)不僅是數(shù)據(jù)的不確定性，更為嚴(yán)重的是不確定數(shù)據(jù)高維度的難題?，F(xiàn)在圖像聲音甚至是視頻數(shù)據(jù)漸漸的成為新的數(shù)據(jù)處理對象，在數(shù)據(jù)處理過程中往往要用十幾個甚至數(shù)百個屬性來描述這些特殊的對象[4]。對高維不確定數(shù)據(jù)的研究，已經(jīng)成為一個新的熱門研究方向，該文主要對屬性不確定性的高維數(shù)據(jù)的聚類進(jìn)行研究。

聚類分析是數(shù)據(jù)挖掘中一項重要的研究內(nèi)容，目的是對數(shù)據(jù)在一定的規(guī)律和要求的基礎(chǔ)上進(jìn)行分類，使沒有類別屬性的數(shù)據(jù)在一定規(guī)律和要求下分成若干類，使得類內(nèi)差異盡量小，類間差異盡量大[5]。通過對聚類結(jié)果的分析可以得到隱藏在數(shù)據(jù)集中的一些分布特性，這有利于從數(shù)據(jù)中得到一些經(jīng)驗(yàn)規(guī)律。理想的聚類算法應(yīng)該要有可擴(kuò)展性、可以發(fā)現(xiàn)任意形狀、用戶輸入?yún)?shù)少、對噪聲不敏感、可以處理高維數(shù)據(jù)、可解釋性和可用性等等[6] 。關(guān)于不確定數(shù)據(jù)的聚類研究尚處在方興未艾的階段，目前普遍是在傳統(tǒng)聚類算法的基礎(chǔ)上進(jìn)行擴(kuò)展。國內(nèi)外已經(jīng)有學(xué)者提出了一些相關(guān)的算法，主要有基于劃分的不確定聚類算法以及基于密度的不確定聚類算法。比較經(jīng)典的算法有uk-means算法[7]，ck-means算法[8]，uck-means算法[9]，uk-medoids算法[10]，F(xiàn)DBSCAN算法[11]，F(xiàn)OPTICS算法[12]，P-DBSCAN算法[13]和改進(jìn)的期望最大化算法EM（expectation maximum）[14]等等。這些算法在低維空間進(jìn)行聚類處理時一般都可以得到比較準(zhǔn)確的結(jié)果，由于維度災(zāi)難的關(guān)系，在高維空間進(jìn)行聚類處理的時往往得不到預(yù)期的結(jié)果。

本文基于相似性度量和凝聚層次聚類思想的基礎(chǔ)上提出了高維不確定數(shù)據(jù)高效聚類HDUDEC（High Dimensional Uncertain Data Efficient Clustering）算法。結(jié)合數(shù)據(jù)的高維屬性和不確定屬性研究出一個計算對象之間相似性的函數(shù)，并設(shè)計出一個適合于高維不確定數(shù)據(jù)的聚類算法。與其它不確定聚類算法相比，HDUDEC算法有以下優(yōu)點(diǎn)：

1）適應(yīng)于任意形狀的不確定數(shù)據(jù)聚類。在聚類過程中類的空間擴(kuò)展方向是隨機(jī)的。

2）適用于高維不確定數(shù)據(jù)的聚類，我們針對高維數(shù)據(jù)的特性提出了就算不同對象之間相似度的計算公式，通過對比對比對象之間的相似度來對對象集合進(jìn)行快速聚類。

3）可以有效過濾噪聲數(shù)據(jù)。可以通過設(shè)定最小對象個數(shù)閾值而自動濾除噪聲點(diǎn)。

4）可以得到比較精確的聚類結(jié)果。通過設(shè)定較高的相似度閾值來得到比較精確的聚類結(jié)果。

5）用戶需要的先驗(yàn)知識相對較少。用戶只需要在開始時輸入相似度閾值就可以。我們可以選取不同的距離閾值和數(shù)量閾值來得到想要的聚類結(jié)果。

1 相似度度量函數(shù)

數(shù)據(jù)對象之間的相似性目前主要有倆種表現(xiàn)形式：一種是采用數(shù)據(jù)對象之間的相似度來度量；還有一種是采用數(shù)據(jù)之間的差異度來度量[15]。在傳統(tǒng)的算法中一般是采用數(shù)據(jù)之間的差異度來進(jìn)行計算。但是在低維空間中能夠得到比較準(zhǔn)確的距離度量公式用在高維空間的聚類結(jié)果往往卻是很差的。因?yàn)閷⑻幚淼途S空間數(shù)據(jù)的距離計算公式運(yùn)用到高維空間中去會產(chǎn)生一些難以預(yù)料的結(jié)果，這就是所謂的“維度災(zāi)難”。實(shí)驗(yàn)證明，高維空間中的點(diǎn)具有稀疏性、同時還存在噪聲點(diǎn)是高維空間中采用距離作為度量量而使分辨能力下降的兩個主要原因[16]。為此不斷有學(xué)者提出新的相似性度量函數(shù)，文獻(xiàn)[17]所提出了Hsim（X，Y）函數(shù)，它的表達(dá)式為：

[Hsim（X，Y）=i=1d11+|xi-yi|d]

式子中的X和Y維兩個d維不確定數(shù)據(jù)對象，d代表不確定對象的維度。在計算高維數(shù)據(jù)相似度時該函數(shù)有很多優(yōu)點(diǎn)，但是還存在不足。比如對于數(shù)值比較大的維相似性度量效果就不是很好。假如給定倆個對象（3，900，2800）和（4，901，2801），如果采用Hsim函數(shù)計算，這倆個對象在第一第二第三維的相似度值是一樣的，可是第二維的相似度往往要比第一位來的高，而第三維的相似度往往要比第二維來的高。

在Hsim函數(shù)的基礎(chǔ)上，文獻(xiàn)[16]提出了提出了一種新的相似度計算公式，它的表達(dá)式為：

式子中[ai]表示第i維的期間長度，即第i維上的數(shù)據(jù)之間的差的絕對值的最大值；[X=（x1，x2，...，xd）]和[Y=（y1，y2，...，yd）]是d維空間的兩個向量；[ε]是一個很小的常數(shù)，用來保證被除數(shù)不為0。這個度量公式可以使相似度在依賴X和Y的同時還依賴全體數(shù)據(jù)。實(shí)驗(yàn)證明該函數(shù)運(yùn)用于度量高位數(shù)據(jù)的相似性，隨著維度的增加它的效果比其它用距離度量函數(shù)更加具有魯棒性。

本文在sim函數(shù)的基礎(chǔ)上結(jié)合高維數(shù)據(jù)對象的不確定性提出了一個新的相似度度量函數(shù)Usim（X，Y），該函數(shù)適合用于計算高維不確定數(shù)據(jù)的相似度。它的表達(dá)式為：endprint

x和y是對象X和對象Y在概率空間中的一個取值，[fi（x）]和[fi（y）]是對象X和對象Y中的數(shù)據(jù)點(diǎn)在概率空間中對應(yīng)的概率值。其他的參數(shù)跟sim函數(shù)一樣不變。

假設(shè)有四個不確定對象在第i條記錄的某一維上的數(shù)據(jù)分別是：3，6，6，11。第i條記錄的概率分別為0.1，0.3，0.5，0.2。根據(jù)usim函數(shù)可以得出這四個不確定對象在第i條記錄的這一維上的區(qū)間長度a=11-3=8。并可以計算出3和6的相似度為（1-|3-6|/（8+0.001）），約等于0.625。同理可得3和11為0，6和6的相似度為1。當(dāng)考慮到整個對象的相似度的時候，這一維度在對象之間的相似度貢獻(xiàn)的大小只要乘以它們的概率密度值就可以。同時函數(shù)usim還有如下一些特點(diǎn)：

1）首先計算各個對象記錄的每一維數(shù)據(jù)的相似度，再計算各維相似度的平均值，再按各個記錄的概率密度函數(shù)進(jìn)行積分求出倆個對象之間的相似度，相似度值大小在0和1之間，值越大說明這倆個對象越相似。

2）函數(shù)計算得到的值為0，表示各個記錄上各維數(shù)據(jù)相差是最大的，這時候?qū)ο笾g的相似性最小。

3）函數(shù)計算得到的值為1，表示對象中的記錄的各個維上的數(shù)據(jù)都相等，這時候?qū)ο笾g的相似性最高。

根據(jù)usim函數(shù)的特點(diǎn)可以得到當(dāng)對象之間在各個維上的數(shù)值更加接近，這些對象就會表現(xiàn)表現(xiàn)出更高的相似性，而且隨著數(shù)值接近的維數(shù)越多，對象之間相似值就越大。

2 高維不確定數(shù)據(jù)高效聚類（HDUDEC）算法

2.1 基本概念

2.2 HDUDEC算法

傳統(tǒng)的相似性度量函數(shù)不能滿足三角不等式，因此基于距離的聚類算法不適合用到基于相似度的聚類算法之中。在凝聚層次聚類算法的思想的基礎(chǔ)上，該文的HDUDEC算法采用自底向上進(jìn)行聚類。取最小值是因?yàn)楫?dāng)要把一個對象歸并到一個簇中的時候就必須判斷倆個對象之間的相似度，如果相似度的值大于或者等于給定的閾值才能歸并到簇中。

對于n個高維不確定數(shù)據(jù)對象，每個對象的每一條記錄有d維，任取一個對象歸到第一個簇中，然后逐個計算還未聚類的對象到簇之間的相似度值，把不小于給定的相似度閾值的對象歸并到對應(yīng)的簇中，對于新加入的對象進(jìn)行同樣的掃描聚類直到?jīng)]有新的對象加入為止。這樣對還未聚類的數(shù)據(jù)對象掃描一遍之后就得到一個新的簇。接著對還未聚類的對象按照上述的方法進(jìn)行聚類，直到?jīng)]有新的類生成為止。聚類完成之后，對于對象數(shù)目少于給定最小閾值的類可以認(rèn)為它們是比較孤立的對象，可以把他們當(dāng)做孤立點(diǎn)進(jìn)行處理。

定理1：設(shè)不確定數(shù)據(jù)空間中對象的集合[U={V1，V2，...，Vn}]，如果按照給定的相似度閾值Z把集合U中的部分點(diǎn)分成m個聚類[U1，U2，...，Um]，那么當(dāng)對集合U中未分類的點(diǎn)再次進(jìn)行最近鄰搜索得到m+1個聚類[Um+1]的時候，屬于m+1個聚類[Um+1]的點(diǎn)不可能已經(jīng)屬于前面的那m個類[U1，U2，...，Um]。

證明：設(shè)未分類中的一個對象[Vj（1≤j≤n）]屬于第k（k

定理1保證在過程③④中進(jìn)行新的聚類的時候，只需要在還未歸類中的點(diǎn)進(jìn)行就可以了。這樣可以大大提高算法的效率。HDUDEC算法描述如下：

輸入： [U{V1，V2，...，Vn}]// d維不確定數(shù)據(jù)對象集；

Z//最小對象數(shù)閾值；

輸出： Cluster_array//聚類結(jié)果；

PROCEDURE HDUDEC：

1.[Cluster_array←?]

2.任取一個對象[Vi（i∈（1，2，...，n））]作為一類，在U中搜索與[Vi]相似度值滿足最小相似度閾值的對象集合[U1]，并把[U1]和[Vi]歸為一類

3.對于新加入類的對象重復(fù)進(jìn)行步驟2

4.當(dāng)沒有新的點(diǎn)加入到聚類中，停止最近臨搜索并輸出未分類的對象集[U2]

5.if [U2≥Z]重復(fù)步驟3-4

6.if [U2≤Z]停止聚類，并把未歸類的對象作為噪聲點(diǎn)處理

7.當(dāng)沒有新的類別生成時停止聚類

8.if（Cluster_array中的類包含的對象個數(shù)>Z）

9.then 輸出這些Cluster_array

End

從算法中我們可以看出：

2-3，使用Usim公式計算不確定對象之間的相似度，并把符合閾值條件的對象歸并為一類。

4-7， 判斷未分類的對象數(shù)，當(dāng)對象數(shù)不滿足最小閾值閾值時候停止聚類，因?yàn)楫?dāng)對象數(shù)小于Z時產(chǎn)生新的聚類也一定不滿足最后的閾值過濾，這樣可以提高算法的效率。

8-9，把各個類的對象數(shù)跟對象數(shù)目閾值相比，把不符合對象閾值的類刪除，這樣可以通過設(shè)置對象數(shù)閾值來去除噪聲數(shù)據(jù)。

2.3 算法分析

本文提出的高維不確定聚類算法，只要輸入三個相應(yīng)的初始值就可以。對聚類結(jié)果有直接影響的只有相似度閾值，而對象數(shù)閾值是用來濾除噪聲數(shù)據(jù)的，所以算法需要知道的先驗(yàn)知識較少?？梢酝ㄟ^改變不同的相似度閾值W和數(shù)量閾值Z來得到滿意的聚類結(jié)果。

HDUDEC算法是通過計算對象的相似度并跟相似度閾值做比較得出的聚類，它可以得到各種形狀的聚類，與選擇的起始點(diǎn)沒有關(guān)系，可以很好地反映出事物之間的本質(zhì)規(guī)律。而且只需要較少的先驗(yàn)知識，降低了選擇參數(shù)的難度。對于那些孤立點(diǎn)，通過設(shè)定對象數(shù)閾值來濾除。該算法只要掃描一遍數(shù)據(jù)，其時間復(fù)雜度為[O（n?log（n））]。在實(shí)驗(yàn)中我們還發(fā)現(xiàn)了一個現(xiàn)象，那就是當(dāng)距離閾值減少到一定大小的時候，聚類的效果幾乎不會再改變。這是因?yàn)闇p小相似度閾值卻不能改變對象之間的相似度。

2.4 算法功能的一種擴(kuò)展運(yùn)用

當(dāng)已經(jīng)對原始的不確定對象集進(jìn)行聚類而原始數(shù)據(jù)集出現(xiàn)了新增加數(shù)據(jù)對象的時候，目前習(xí)慣的做法是對含有新增加數(shù)據(jù)對象的原始數(shù)據(jù)集進(jìn)行重新聚類。顯然這樣做的效率是低下的。根據(jù)定理1，當(dāng)數(shù)據(jù)集中新增加的數(shù)據(jù)對象數(shù)目不是非常巨大而且聚類精度在允許的范圍內(nèi)的時候，可以先計算出它們跟各個簇之間的相似度。然后把他們歸并到合適的類中，這樣我們可以方便高效地對數(shù)據(jù)集中在一定范圍內(nèi)動態(tài)變化的數(shù)據(jù)進(jìn)行聚類，而不必對所有數(shù)據(jù)進(jìn)行重新聚類。

3 實(shí)驗(yàn)分析

本實(shí)驗(yàn)中，采用Microsoft Windows XP操作系統(tǒng)；Intel（R）Core（TM）2 Duo CPU，P7350@2.O0GHz；2G內(nèi)存；320G硬盤；開發(fā)環(huán)境為MyEclipse8.5。

如文獻(xiàn)[8] 我們在多維空間中生成n個不確定對象的數(shù)據(jù)集，每一個不確定對象隨機(jī)地在[0，100]×[0，100]內(nèi)生成。每一個邊界盒的邊長d=10，生成s（1000）個點(diǎn)隨機(jī)地分布在邊界盒內(nèi)，每個點(diǎn)對應(yīng)一個0到1之間的概率值。這些概率值進(jìn)行歸一化進(jìn)行相加等于1。我們將采用ck-means算法和HDUDEC算法分別對它們進(jìn)行聚類分析。

在表1中，我們分別采用HDUDEC算法和ck-means算法對100個多維不確定數(shù)據(jù)對象進(jìn)行聚類實(shí)驗(yàn)，對于HDUDEC算法，設(shè)相似度閾值為0.5，數(shù)量閾值為10。對于ck-means算法，k與HDUDEC算法聚類所產(chǎn)生的類數(shù)相同。

從表中可以發(fā)現(xiàn)，ck-means算法隨著維度的增大聚類的精確度受到的影響明顯，而HDUDEC算法的精確度對維度的增加變化不是很大。實(shí)驗(yàn)結(jié)果表明HDUDEC算法可以有效的處理高維不確定數(shù)據(jù)。

4 結(jié)束語

本文對傳統(tǒng)的高維數(shù)據(jù)度量函數(shù)進(jìn)行改進(jìn)研究出了一種適合不確定高維數(shù)據(jù)相似性度量函數(shù)。在此基礎(chǔ)上結(jié)合凝聚層次聚類思想的提出了高維不確定數(shù)據(jù)高效聚類（HDUDEC）算法。實(shí)驗(yàn)證明HDUDEC算法需要的先驗(yàn)知識較少、可以有效去除噪聲數(shù)據(jù)、可以快速有效得到任意形狀的高維不確定數(shù)據(jù)的聚類。

參考文獻(xiàn)：

[1] CHENG R，KALASHINIKOV D，PRABHAKER S.Querying imprecise data in moving object environments[J].IEEE Trans Knowledge and Data Engineering，2004，16（9）：1112-1127.

[2] CANTONI V，LOMBARDI L，LOMBARDI P.Challenges for data mining in distributed sensor networks[C] //Proceedings of the 18th International Conference on Pattern Recognition.Washington， DC，USA：IEEE Computer Society Press，2006：1000-1007.

[3] AGGARWAL C C.On unifying privacy and uncertain data models[C]//Proceedings of the 24th IEEE International Conference on Data Engineering.Washington，DC，USA：IEEE Computer Society Press，2006：1000-1007.

[4] 賀玲，蔡益朝，楊征.高維數(shù)據(jù)聚類方法綜述[J].計算機(jī)應(yīng)用研究，2010（1）：23-28.

[5] 楊風(fēng)召.高維數(shù)據(jù)挖掘技術(shù)研究[M]. 南京：東南大學(xué)出版社，2007.

[6] Han J W， Kamber M.Data Mining： concepts and techniques （Second Edition）[M].Morgan Kaufmann ， Elsevier Inc， 2006：145-176.

[7] MICHAEL C，REYNOLD C，BEN K，et al.Uncertain data mining：an example in clustering location data[C]//Fro ceding of the 10th Pacific-Asia Conference on Knowledge Discovery and Data Mining（PAKDD 2006）.Berlin：Springer Verlag，2006：199-204.

[8] LEED S D，KAO B，CHENG R.Reducing uk-means to K-means[C]//The 1st Workshop on Data Mining of Uncertain Data（DUNE），in conjunction with ICDM.Trentom.NJ：IEEE Press，2007：483-488.

[9] Peng Yu，Luo Qinghua，Peng Xiyuan.UCK-means ：A customized Kmeans for clustering uncertain measurement data[C].International Conference on Fuzzy Systems and Knowledge Discovery （FSKD），Vol.2， pp. 1196-1200， July 2011.

[10] Gullo F，Ponti G，Tagarelli A.Clustering uncertain data via k-medoids[C].Proc.of the 2nd International Conference on Scalable Uncertainty Management，2008：229-242.endprint

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

[12]Kriegel H P，Pfeifle M.Hierarchical density-based clustering of uncertain data[C].Proc.of the 5th IEEE International Conference on Data Mining，2005：689-692.

[13] Xu H J， LI G H.Density-based probabilistic clustering of uncertain data[C].Proc.of the 2008 International Conference on Computer Science and Software Engineering，2008：474-477.

[14] Hamdan H，Govaert G.Mixture Model Clustering of Uncertain Data[C].Proc.of the IEEE International Conference on Fuzzy Systems，2005：879-884.

[15] 賀玲，吳玲達(dá)，蔡益朝.高維空間中數(shù)據(jù)的相似性度量[J].數(shù)學(xué)的實(shí)踐與認(rèn)識，2006，36（9）：189-194.

[16] 黃斯達(dá)，陳啟.一種基于相似性度量的高維數(shù)據(jù)聚類算法的研究[J].計算機(jī)應(yīng)用與軟件，2009（9）：187-189.

[17] Sudipto Guha，Rajeev Rastogi，Kyuseok Shim. CURE： An Efficient Clustering Algorithm for Large Databases [C]//Proceedings of the ACM SIGMOD international conference on Management of data.New York：ACM Press，1998：73-84.endprint

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

[12]Kriegel H P，Pfeifle M.Hierarchical density-based clustering of uncertain data[C].Proc.of the 5th IEEE International Conference on Data Mining，2005：689-692.

[13] Xu H J， LI G H.Density-based probabilistic clustering of uncertain data[C].Proc.of the 2008 International Conference on Computer Science and Software Engineering，2008：474-477.

[14] Hamdan H，Govaert G.Mixture Model Clustering of Uncertain Data[C].Proc.of the IEEE International Conference on Fuzzy Systems，2005：879-884.

[15] 賀玲，吳玲達(dá)，蔡益朝.高維空間中數(shù)據(jù)的相似性度量[J].數(shù)學(xué)的實(shí)踐與認(rèn)識，2006，36（9）：189-194.

[16] 黃斯達(dá)，陳啟.一種基于相似性度量的高維數(shù)據(jù)聚類算法的研究[J].計算機(jī)應(yīng)用與軟件，2009（9）：187-189.

[17] Sudipto Guha，Rajeev Rastogi，Kyuseok Shim. CURE： An Efficient Clustering Algorithm for Large Databases [C]//Proceedings of the ACM SIGMOD international conference on Management of data.New York：ACM Press，1998：73-84.endprint

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

[12]Kriegel H P，Pfeifle M.Hierarchical density-based clustering of uncertain data[C].Proc.of the 5th IEEE International Conference on Data Mining，2005：689-692.

[13] Xu H J， LI G H.Density-based probabilistic clustering of uncertain data[C].Proc.of the 2008 International Conference on Computer Science and Software Engineering，2008：474-477.

[14] Hamdan H，Govaert G.Mixture Model Clustering of Uncertain Data[C].Proc.of the IEEE International Conference on Fuzzy Systems，2005：879-884.

[15] 賀玲，吳玲達(dá)，蔡益朝.高維空間中數(shù)據(jù)的相似性度量[J].數(shù)學(xué)的實(shí)踐與認(rèn)識，2006，36（9）：189-194.

[16] 黃斯達(dá)，陳啟.一種基于相似性度量的高維數(shù)據(jù)聚類算法的研究[J].計算機(jī)應(yīng)用與軟件，2009（9）：187-189.

[17] Sudipto Guha，Rajeev Rastogi，Kyuseok Shim. CURE： An Efficient Clustering Algorithm for Large Databases [C]//Proceedings of the ACM SIGMOD international conference on Management of data.New York：ACM Press，1998：73-84.endprint