基于三角模糊數(shù)的不確定性數(shù)據(jù)聚類算法

陸億紅,翁純佳

(浙江工業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，浙江 杭州 310023)

基于三角模糊數(shù)的不確定性數(shù)據(jù)聚類算法

陸億紅,翁純佳

(浙江工業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，浙江 杭州 310023)

摘要：隨著對實驗精確度要求的不斷提高，聚類分析中的不確定性數(shù)據(jù)聚類也越來越受到關(guān)注.然而經(jīng)典的不確定數(shù)據(jù)聚類通常假設(shè)其概率密度函數(shù)(PDF)等信息是已知的，而現(xiàn)實過程中，這些指標(biāo)并沒有那么輕易就能獲取.考慮到這些情況，可以利用三角模糊數(shù)來恰當(dāng)有效地表示多維不確定性數(shù)據(jù)，并采用基于三角模糊數(shù)的低計算復(fù)雜度的距離計算方法，結(jié)合K-means基礎(chǔ)聚類方法形成一種被命名為UTDK-means(Uncertain triangular fuzzy number data K-means)的聚類方法，而它是基于三角模糊數(shù)的.實驗結(jié)果表明：基于三角模糊數(shù)的不確定數(shù)據(jù)聚類是可行的，具有一定的研究價值.

關(guān)鍵詞：不確定性數(shù)據(jù);三角模糊數(shù);聚類算法

近幾年來，互聯(lián)網(wǎng)信息技術(shù)不斷更新發(fā)展，出現(xiàn)了很多機遇和挑戰(zhàn).而在無線傳感器網(wǎng)絡(luò)[1](Wireless sensor network，WSN)等領(lǐng)域，由于各種緣故引起的不確定性問題，產(chǎn)生出一種新的數(shù)據(jù)類型——不確定數(shù)據(jù)，在實際系統(tǒng)中，隨著對結(jié)果精確度的要求不斷加強，不確定數(shù)據(jù)也越來越嚴(yán)重地影響到了系統(tǒng)的可信度和穩(wěn)定性[2].不確定數(shù)據(jù)的聚類一般可以劃分成兩種：一種是存在型的不確定數(shù)據(jù)聚類，也就是說關(guān)系數(shù)據(jù)庫中的數(shù)據(jù)元組存在與否是有一定的概率的，當(dāng)然不同元組的概率性也是會相互影響的.另一種是值的不確定性數(shù)據(jù)聚類，也就是說元組數(shù)目和類型己經(jīng)確定，但是屬性值中存在的有一定的誤差，以至于產(chǎn)生不確定信息，一般通過概率密度函數(shù)(也就是PDF)或其他統(tǒng)計量(如協(xié)方差、方差等)進行表示.在不確定數(shù)據(jù)聚類研究中，一般都是基于PDF建模的不確定性數(shù)據(jù)[3].筆者研究的是基于值的不確定性但不是基于PDF建模的不確定性數(shù)據(jù).

聚類分析屬于數(shù)據(jù)挖掘中的一個熱門研究方向，是一種無監(jiān)督的學(xué)習(xí)方法[4].通過聚類算法可以將對象集合中相近或者相似的對象聚集到同一個類中，最后得到幾個不同的類劃分[5].聚類分析分為基于劃分、基于層次和基于密度等方面,每個領(lǐng)域都有新突破[6].這幾年聚類分析也面臨著不確定數(shù)據(jù)的挑戰(zhàn)，因為在研究不確定數(shù)據(jù)的聚類問題時，傳統(tǒng)的聚類算法已經(jīng)無法勝任.關(guān)于不確定數(shù)據(jù)聚類, Michael Chau等首先在基于K-means算法的基礎(chǔ)上提出了一種不確定聚類算法,即UK-means算法,S.D.Lee等對UK-means進行了改進,提出了一個新的算法,即CK-means算法,之后還有K-medoid等不確定性聚類改進算法的出現(xiàn)，然而都是采用整個數(shù)據(jù)的PDF來表示數(shù)據(jù)的不確定性[7-9].事實上，數(shù)據(jù)完整的PDF是比較難得到的，而很多不確定數(shù)據(jù)常常以三角模糊數(shù)的形式來表示[10]，所以筆者專門研究用三角模糊數(shù)來表示的一類不確定數(shù)據(jù)，并采用新的三角模糊距離度量，設(shè)計出一種復(fù)雜度較低、聚類效果較好的不確定聚類方法：UTDK-means.

1相關(guān)定義

記R+為正實數(shù)集,F(R+)為全體正模糊數(shù)集,R為實數(shù)集,F(R)為全體模糊數(shù)集.下面是關(guān)于三角模糊數(shù)的一些概念.

定義1[11]設(shè)α∈F(R),且

式中：α=(l，m，u)為三角模糊數(shù)；l和u分別為α的上界和下界；(m-l)和(u-m)分別為α的下限和上限，m為三角模糊數(shù)α的主值，是可能性最大的值．當(dāng)(u-l)越大時，三角模糊數(shù)α=(l，m，u)就越模糊．當(dāng)l=m=u時，α成為了普通意義上的實數(shù)．

對于任意兩個三角模糊數(shù)α1=(l1，m1，u1)，α2=(l2，m2，u2)，據(jù)擴張定理可知，相應(yīng)的三角模糊數(shù)的運算規(guī)則[12]為

α1+α2=(l1+l2，m1+m2，u1+u2)

α1-α2=((l1-u2)∨0，m1-m2，u1-l2)

α1×α2=(l1×l2，m1×m2，u1×u2)

α1∕α2=(l1/u2，m1/m2，u1/l2)

λ×α2=(λ×l2，λ×m2，λ×u2)λ∈R且λ>0

根據(jù)定義2，可以計算出兩個三角模糊數(shù)之間的距離，但是觀察可知：計算出來的距離是一個定值，而不是一個新的三角模糊數(shù)，在對不確定數(shù)據(jù)進行聚類的時候這樣的結(jié)果很有可能產(chǎn)生較為不精確的結(jié)果，所以有必要定義一種新的三角模糊數(shù)距離公式.

定義3(三角模糊數(shù)的新距離)對于給定的三角模糊數(shù)α=(mα-xα，mα，mα+yα)，β=(mβ-xβ，mβ，mβ+yβ)，其中mα，xα，yα，mβ，xβ，yβ∈R，在任意維度j(1≤j≤d)上，這兩個三角模糊數(shù)之間的距離有四種可能性，如圖1(a～d)所示.在維度j上，當(dāng)兩個數(shù)是如圖1(a)所示的相離狀態(tài)時，可知他們之間的距離的最大值可表示為|mβ-mα+yβ+xα|，最小值可表示為|mβ-mα-yα-xβ|；當(dāng)兩個數(shù)是如圖1(b)所示的相接狀態(tài)時，可知他們之間的距離的最大值可表示為|mβ-mα+yβ+xα|，最小值可表示為0；當(dāng)兩個數(shù)是如圖1(c)所示的相交狀態(tài)時，可知他們之間的距離的最大值可表示為|mβ-mα+yβ+xα|，最小值可表示為0；當(dāng)兩個數(shù)是如圖1(d)所示的相包含的狀態(tài)時，可知他們之間的距離的最大值可表示為|mβ-mα+yβ+xα|，最小值可表示為0.綜合討論后可得計算式為

圖1　四種距離狀態(tài)Fig.1　Four distance state

(1)

(2)

Dmid=|mβ-mα|

(3)

式中：Dj.min為j維上的三角模糊距離中的下界；Dj.max為j維上的三角模糊距離中的上界；Dj.mid為j維上的三角模糊距離中的主值.則兩個d維的三角模糊數(shù)之間的距離D=[Dmin，Dmid,Dmax]可重新定義為

(4)

式(4)為一個新的三角模糊數(shù)距離公式，此時計算出來的三角模糊數(shù)之間的距離仍是一個三角模糊數(shù)，相比之前，保留了數(shù)據(jù)的不確定性.

為了將距離度量有效地運用到聚類算法中去，此時再利用定義3，將D轉(zhuǎn)換，得到兩個三角模糊數(shù)之間的距離，其表達(dá)式為

(5)

2UTDK-means聚類算法

2.1算法描述

對N個d維三角模糊數(shù)表示的不確定性數(shù)據(jù)的聚類，就是利用新的三角模糊數(shù)間的距離定義，基于K-means的基本聚類方法，最終找到K組分別以點cj(1≤j≤K，K為聚類數(shù)目)為簇中心的集合Cj(1≤j≤K).對于聚類結(jié)果，一般情況下原則是不同簇成員間的距離則越遠(yuǎn)越好，Cj集合內(nèi)各個點到簇中心cj的距離則是越近越好.UTDK-means算法就是基于K-means算法和新三角模糊數(shù)距離公式結(jié)合得到的多維不確定性數(shù)據(jù)的聚類算法，K組簇中心分別表示為c1，c2，…，ck，K個簇分別表示為C1,C2,…，Ck.算法描述如下：

1) 隨機分配初始簇中心c1至ck

2) Repeat

3) Fori=1 toNdo

4) 計算每一個非中心點到簇中心cj的三角模糊距離Dij，分配距離D最小的數(shù)據(jù)點Xi給cj

5) end for

6) forj=1 toKdo

7) 重新計算簇Cj的中心點cj

8) end for

9) 簇中心不再改變

10) returnC

2.2計算復(fù)雜度

根據(jù)上文推導(dǎo)出來的新的三角模糊數(shù)距離公式(5)的組成部分，與經(jīng)典的不確定數(shù)據(jù)聚類算法UK-means算法進行時間復(fù)雜度的比較.UK-means算法的距離公式為

Bsinθ+C)rdθdr

(6)

式中：c=(p,q)為簇中心；假設(shè)f(r，θ)是圓不確定區(qū)域的概率密度函數(shù)，(h，o)為圓心；B=2r(o-q)；A=2r(h-P)；C=r2+(h-P)+(o-q).

UTDK-means和UK-means算法雖然采用不同的距離公式，但是總的來說都是基于K-means算法的，而一般K-means算法的時間復(fù)雜度可表示為o(tKn)，t為算法循環(huán)的次數(shù)，K為簇的組數(shù)，n為數(shù)據(jù)點的個數(shù)[14].

充分考慮UTDK-means和UK-means算法的各自的距離公式，可以計算出在二維空間它們各自的總計算量，如表1所示.

表1兩種算法的距離計算量比較

Table 1Comparison about the computing distance of two algorithms

計算步驟UK-meansUTDK-means加法89乘法116雙重積分10

由表1分析可知：在計算兩不確定數(shù)據(jù)點之間的距離時，UTDK-means所用到的計算量比UK-means用到的計算量要小，因此整個算法的時間復(fù)雜度也是比較小的.運用UTDK-means算法，不僅沒有對PDF指標(biāo)的需求，而且有著比較小的時間復(fù)雜度，所以是有較大的研究推廣價值的.

3實驗分析

算法由Matlab實現(xiàn)，運行的硬件環(huán)境為Intel(R) Core(TM) i3-M350 2.27 GHz CPU，內(nèi)存為4 GB，硬盤為500 GB，操作系統(tǒng)為Windows 7.

3.1聚類準(zhǔn)確度

準(zhǔn)確率(Accuracy)的定義：對于某個數(shù)據(jù)集，結(jié)果集正確分類的樣本數(shù)據(jù)點數(shù)目與總樣本數(shù)據(jù)點數(shù)目之比，較高的準(zhǔn)確率表明聚類結(jié)果具有很高準(zhǔn)確度.

3.2人工數(shù)據(jù)集

圖2　人工數(shù)據(jù)集聚類效果Fig.2　Clustering performance of artificial data set

3.3UCI數(shù)據(jù)集

UCI數(shù)據(jù)庫是一個常用的標(biāo)準(zhǔn)測試數(shù)據(jù)集，這個數(shù)據(jù)庫目前共有187個數(shù)據(jù)集，用其中的某些經(jīng)典數(shù)據(jù)集做實驗是比較有說服力的.Wine，Iris和Glass就是屬于經(jīng)典的被廣泛使用的UCI數(shù)據(jù)集，其中Iris是一種統(tǒng)計數(shù)據(jù)集，分別對鶯尾屬植物的萼片寬度、萼片長度、花瓣寬度和花瓣長度等4種屬性進行統(tǒng)計，總共有150個數(shù)據(jù)點；Wine數(shù)據(jù)集統(tǒng)計了3種不同意大利葡萄酒的化學(xué)分析結(jié)果，分為13種屬性，總共有178個數(shù)據(jù)點；Glass數(shù)據(jù)集中通過10種化學(xué)成分的值來描述每一種玻璃，分為10種屬性，總共有214個數(shù)據(jù)點.表2列出了這3種數(shù)據(jù)集的主要特性.

表2　實驗中用到的數(shù)據(jù)集

對3類UCI數(shù)據(jù)集進行不確定性處理后分別運行UTDK-means算法10次，并且將三類數(shù)據(jù)集分別運行K-means算法10次，得到的準(zhǔn)確率，并取其平均數(shù),結(jié)果如表3所示.

表3　UCI數(shù)據(jù)集聚類效果

經(jīng)過人工生成的數(shù)據(jù)集和三種經(jīng)典UCI數(shù)據(jù)集對UTDK-means算法的反復(fù)實驗，并由準(zhǔn)確率作為結(jié)果指標(biāo)，可以發(fā)現(xiàn)，算法能在較低的時間復(fù)雜度下實現(xiàn)較好的聚類效果.并且Iris和Wine是三維數(shù)據(jù)集，Glass是六維數(shù)據(jù)集，所以UTDK-means是一個基于三角模糊數(shù)，支持多維不確定數(shù)據(jù)集，低時間復(fù)雜度，并且不依賴概率密度函數(shù)的聚類算法，有較大的研究推廣價值.

4結(jié)論

基于三角模糊數(shù)表示的多維不確定數(shù)據(jù)，針對概率密度函數(shù)(PDF)等指標(biāo)信息在很多實際問題中較難獲取的情況，充分利用三角模糊數(shù)的不確定性，設(shè)計一種新的三角模糊數(shù)間的距離，保留其特定的不確定性，并在此基礎(chǔ)之上，提出了UTDK-means——一種基于三角模糊數(shù)的聚類算法.同時分別在經(jīng)過不確定化的人工數(shù)據(jù)集和三種不同的UCI數(shù)據(jù)集上運行UTDK-means算法，比較了聚類結(jié)果的準(zhǔn)確度的值，得到了比較滿意的結(jié)果.但由于算法還是基于劃分的聚類方法，所以不能對任意幾何形狀的數(shù)據(jù)集進行聚類.所以，可以研究更多不同形狀分布的數(shù)據(jù)集基礎(chǔ)上UTDK-means算法的運用情況，看是否能夠推廣到基于密度的聚類方法等.

參考文獻：

[1]彭字，羅清華，彭喜元．網(wǎng)絡(luò)化測試體系中不確定性數(shù)據(jù)處理方法淺析[J]．儀器儀表學(xué)報，2010，31(1)：229．

[2]黃美發(fā)，景暉．基于擬蒙特卡羅方法的測量不確定性度評定[J]．儀器儀表學(xué)報，2009，30(1)：120-125．

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

[4]曾淦寧,吳國權(quán),徐曉群.多元聚類分析方法在杭州灣水質(zhì)分析上的應(yīng)用[J].浙江工業(yè)大學(xué)學(xué)報，2009，37(1):14-19.

[5]陸億紅.基于聚類的數(shù)據(jù)流挖掘技術(shù)的分析與研究[J].浙江工業(yè)大學(xué)學(xué)報，2007，35(3):288-291.

[6]RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks[J]. Science,2014,344(6191):1492-1496.

[7]任世錦．基于區(qū)間數(shù)的不確定性數(shù)據(jù)挖掘及其應(yīng)用研究[D]．杭州：浙江大學(xué)，2006：3-29．

[8]邱志平．不確定參數(shù)結(jié)構(gòu)靜力響應(yīng)和特征值問題的區(qū)間分析方法[D]．長春：吉林工業(yè)大學(xué)，1994．

[9]MICHAEL C,REYNOLD C,BEN K,et al. Uncertain data mining: an example in clustering location data[C]//Pacific-asia Conference on Advances in Knowledge Discovery & Data Mining. Berlin Heidelberg: Springer,2006：199-204.

[10]NGAIWK，KAO B，CHUI C K，et a1．Efficient clustering of uncertain data[C]//Proceedings of the 22nd IEEE International Conference on Data Mining. Hong Kong：IEEE Computer Society，2006：436-445．

[11]李光博，黃德才.基于灰色關(guān)聯(lián)分析的三角模糊多屬性決策法[J].浙江工業(yè)大學(xué)學(xué)報，2011，39(2):224-227.

[12]冉靜學(xué).三角模糊數(shù)排序方法的研究[J].中央民族大學(xué)學(xué)報(自然科學(xué)版),2011，20(4):37-42.

[13]許謙.確定模糊評價綜合因素權(quán)重的一個方法[J].大學(xué)數(shù)學(xué),2005,21(1):25- 30.

[14]GULLO F, PONTI G, TAGAERLLI A. Clustering uncertain data via K-medoids[C]//International Conference on Scalable Uncertainty Management. Berlin Heidelberg: Springer，2008：229-242．

[15]姜艷萍,樊治平.三角模糊數(shù)互補判斷矩陣排序的一種實用方法[J].系統(tǒng)工程,2002,20(2):89-92.

[16]YUN C H, YANG J. Reducing UK-Means to K-Means[C]//In Proceedings of the 6th IEEE International Conference on Data Mining. Omaha: IEEE Computer Science，2007：483-488．

(責(zé)任編輯：陳石平)

Research on the clustering algorithm of uncertain data based on triangular fuzzy number

LU Yihong, WENG Chunjia

(College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China)

Abstract:With the increase in the requirements of experimental accuracy, uncertain data clustering method in cluster analysis has more and more attention. Classic uncertain data clustering is generally assumed that the probability density function (PDF) and other information is known, but the reality of the process, these indicators are not so easily able to obtain. In view of this issue, we use triangular fuzzy number to represent the multi-dimensional uncertain data. and the distance calculation method with the low computational complexity based on triangular fuzzy number is combined with K-means method to form a new method called UTDK-means. The experimental results show that the clustering method based on triangular fuzzy number is efficient and worthy to study.

Keywords:uncertain data; triangular fuzzy number; clustering algorithm

收稿日期：2016-01-11

基金項目：水利部公益性行業(yè)科研專項(201401044)；國家科技支撐計劃項目(2012BAD10B01)

作者簡介：陸億紅(1968—)女，浙江永康人, 副教授,碩士, 研究方向為數(shù)據(jù)庫應(yīng)用和數(shù)據(jù)挖掘,E-mail:lyh@zjut.edu.cn.

中圖分類號：TP3

文獻標(biāo)志碼：A

文章編號：1006-4303(2016)04-0405-05