一種多粒度增量屬性的聚類方法

劉杭雨,于 洪

(重慶郵電大學(xué) 計算智能重慶市重點實驗室,重慶 400065)

1 引 言

聚類分析是研究對象分類問題的一種統(tǒng)計分析方法,是數(shù)據(jù)挖掘中比較重要的概念,作為數(shù)據(jù)挖掘算法中常用的一種無監(jiān)督的技術(shù)方法,已經(jīng)廣泛地應(yīng)用在許多實際應(yīng)用領(lǐng)域中,其優(yōu)勢在于不需要標(biāo)記數(shù)據(jù)信息從而增加計算量[1].

現(xiàn)在數(shù)據(jù)的規(guī)模、種類、速度和復(fù)雜度都遠遠超過了人腦的認(rèn)知能力,如何有效完成對大數(shù)據(jù)的認(rèn)知,給傳統(tǒng)聚類算法也帶來了巨大挑戰(zhàn)[2].目前大多數(shù)聚類方法只能處理靜態(tài)數(shù)據(jù),不適用于動態(tài)數(shù)據(jù)集.因而,設(shè)計一種能夠處理動態(tài)流動性數(shù)據(jù)的聚類算法成為當(dāng)前聚類分析領(lǐng)域的一個重要挑戰(zhàn).近年來在不同的應(yīng)用領(lǐng)域,大量的研究已經(jīng)應(yīng)用增量聚類算法解決部分具體的實際問題,如異常檢測[3,4],高維數(shù)據(jù)處理[5],隱私數(shù)據(jù)的增量聚類[6],基因表達數(shù)據(jù)聚類[7]等.

近年來,對大數(shù)據(jù)有效信息的獲取需求越來越高,增量式方法在數(shù)據(jù)挖掘中尤其是在聚類分析中變得非常流行,解決動態(tài)數(shù)據(jù)集的聚類逐漸成為一個新的研究方向.如今,研究者們已經(jīng)提出了一些增量聚類算法,Zhang C[8]等學(xué)者提出一種基于三支決策的增量聚類框架,通過基于代表點的新搜索樹,在數(shù)據(jù)增加時用增量方式調(diào)整先前的聚類結(jié)果已得到新的聚類結(jié)果.Bigdeli E[9]等提出了一種增量聚類的新方法,該方法以高斯混合矩陣(GMM)的形式保存類簇信息,通過引入核心點的概念自動確定類簇數(shù)目,然后對新的數(shù)據(jù)集整體進行聚類,并通過采用核心點和GMM的概念,以原有的GMM的相似性信息標(biāo)記了新的GMM矩陣.

不過上述的增量聚類研究都是基于數(shù)據(jù)對象增加而出現(xiàn)的,目前針對屬性向量增長的研究相對較少.屬性就是概念的內(nèi)涵,是針對對象不同角度的認(rèn)識.在實際生活中第一次觀察某一對象,并不能得到其全部的信息,隨著研究的深入,對于該對象不同方向的認(rèn)識會更加的清晰,對于這種對象屬性增長的情況,目前并沒有很好的方法對其進行處理.

基于這樣的一個問題,隨著人工智能的興起,粒計算在數(shù)據(jù)挖掘領(lǐng)域應(yīng)用越來越多,專家學(xué)者們也就發(fā)現(xiàn)了粒計算與聚類分析之間的相關(guān)關(guān)系[10].我們將每一個屬性看作一個粒,而粒度就是取不同個數(shù)的屬性集,也就是說,將原來的“粗粒度”,即個數(shù)較多的屬性集分割成為若干“細粒度”,或者把若干個數(shù)較少的屬性合并成一個“粗粒度”對象,進行研究.由此將粒計算的思想應(yīng)用到聚類算法當(dāng)中產(chǎn)生了一種新的粒度聚類算法,這類算法利用粒度的思想更容易地獲取信息,成為解決不確定性數(shù)據(jù)聚類的一個解決方案.在近年來,有關(guān)粒度聚類算法的研究論文層出不窮,主要應(yīng)用于圖像處理[11]、生物學(xué)中的進化計算[12]、web頁面文本聚類[13]等眾多領(lǐng)域.

數(shù)據(jù)的井噴導(dǎo)致單純的粒度計算已經(jīng)不能對數(shù)據(jù)進行有效地挖掘,有些學(xué)者開始考慮將多個粒度的思想與聚類算法相結(jié)合來處理問題.Zhang H B[14]等學(xué)者提出了基于隨機投影的三支k-medoids動態(tài)聚類算法.該算法結(jié)合多粒度思想,利用動態(tài)隨機投影三支聚類模型對高維數(shù)據(jù)進行處理,最后針對基于隨機投影的三支k-medoids動態(tài)聚類算法在相應(yīng)的數(shù)據(jù)集上進行驗證.Xu J[15]等學(xué)者提出了一種基于密度峰值的層次聚類方法(DenPEHC),該方法在每個粒度層上都能生成一個聚類結(jié)果,通過構(gòu)建網(wǎng)格粒度框架,使得DenPEHC能夠?qū)Υ笠?guī)模和高維(LSHD)數(shù)據(jù)集進行聚類.

隨著大數(shù)據(jù)時代的來臨,數(shù)據(jù)和環(huán)境無時無刻不在發(fā)生變化,傳統(tǒng)的粒度聚類算法,其往往只能適用于靜態(tài)數(shù)據(jù)集的聚類,在處理動態(tài)的增量數(shù)據(jù)時將造成前期聚類結(jié)果可靠性的喪失,而如果重新進行聚類必然會造成效率低下和計算資源的急速增長[16].而動態(tài)的增量聚類方法對于數(shù)據(jù)的橫向性增長研究比較少,即隨著研究的深入對于對象的認(rèn)識更清晰,對象的屬性增加的問題的研究現(xiàn)在比較少.

本文以粒計算等處理不確定性問題的方法,提出一種多粒度增量屬性的聚類方法對數(shù)據(jù)屬性增長的聚類問題進行求解.本方法利用密度峰值算法[17]針對初始數(shù)據(jù)集進行處理,通過尾插法將增加屬性粒集合對應(yīng)的加入初始屬性粒集合尾部融合成一個全新的粒度,以整合不同的粒子層上的信息,在不重復(fù)聚類為前提下以融合后的粒度層為基礎(chǔ),利用鄰域的思想動態(tài)地更新原有的結(jié)果,進而得到增量聚類的結(jié)果.實驗結(jié)果表明該方法是有效的.

2 相關(guān)定義

2.1 粒度關(guān)系

設(shè)有n個待聚類數(shù)據(jù)對象,每個數(shù)據(jù)對象由l個屬性粒來表示,根據(jù)實時數(shù)據(jù)構(gòu)造矩陣:

顯而易見,不同的?？赡芫哂胁煌牧烤V,因此需要對屬性粒進行歸一化處理,相應(yīng)的計算公式,如公式(1)所示:

(1)

其中i∈[1,n],j∈[1,l].

粒度層gi為數(shù)據(jù)集部分屬性粒的集合即:

圖1 粒度關(guān)系Fig.1 Granular relationship

如圖1所示,在粒度的增量過程中,g1∩g2不一定為,因為在生活中對于對象的認(rèn)識,第二次也出現(xiàn)與第一次相同的認(rèn)知是很正常的.

2.2 算法流程

本文提出的多粒度增量屬性聚類方法流程如圖2所示.

圖2 多粒度增量屬性聚類算法Fig.2 Multi-Granular incremental attribute clustering method

如圖2中所示,本文的多粒度增量屬性聚類方法首先利用初始聚類算法(初始聚類算法(ICM)詳細描述在2.1節(jié))將初始的粒度g1進行聚類(矩形虛線部分),得到初始結(jié)果R1;然后對于某一時刻新增加的屬性集合g2,首先與原有的屬性粒集合g1利用尾插法進行融合,得到新粒度G2;最后利用增量聚類方法(增量聚類算法(IAC)詳細描述在2.2節(jié))動態(tài)的更新原有結(jié)果R1,得到增量結(jié)果R2,以此迭代,直至未有新屬性粒的加入.

算法1.多粒度增量屬性聚類方法(Multi-Granularity Incremental Attribute Clustering Method,MGIAC)

輸出:聚類精度Accs,聚類結(jié)果Rs.

①R1←ICM;/*初始聚類算法(ICM)在2.1節(jié)詳細介紹*/

② for eachgado

③Ra←IAC;/*增量聚類算法(IAC)在2.2節(jié)詳細介紹*/

④Acca(Ra);/*計算聚類精度*/

⑤ end for

⑥ 判斷是否有新粒度(gi+1)的加入,若沒有則輸出最后一次聚類結(jié)果Rs,Accs;

3 多粒度增量屬性聚類方法

人們在分析問題時往往從不同的角度、不同的層次觸發(fā),其主要是大腦在多次處理同一問題時,隨著時間環(huán)境等變化,會自行的分析并利用經(jīng)驗和專業(yè)知識去刻畫與對象與之相應(yīng)的認(rèn)識,即每一次看待同一個問題,在上一次認(rèn)識的基礎(chǔ)上都可能出現(xiàn)新的發(fā)現(xiàn).

表1 本文中的符號
Table 1 Symbols

符號含義U整個數(shù)據(jù)集mi第i個屬性粒Gi第i次迭代用于聚類的粒度集合gi第i次迭代中增加的粒度集合Ri第i次的聚類結(jié)果Rs最終的結(jié)果N鄰域選取個數(shù)Acci第i次的聚類精度Dimension 1初始聚類屬性粒的個數(shù)ΔDimension i第i次增量聚類增加的屬性粒個數(shù)

本文所提出的多粒度增量屬性聚類算法分為兩個部分:第一部分為初始聚類(圖2中矩形虛線部分),主要采用密度峰值聚類算法[17]得到初始聚類結(jié)果;第二部分則是增量屬性聚類,即針對某一時刻增加的新屬性粒在不重新聚類的前提下,利用鄰域思想動態(tài)更改原有結(jié)果.(密度峰值聚類的計算方法請參見文獻[17])本文中出現(xiàn)的符號如表1所示.

3.1 初始聚類

在本文中初始聚類文獻[17]提出的密度峰值聚類算法.

算法2.初始聚類算法(Initial clustering method,ICM)

輸入:初始屬性粒g1,截斷距離dc,對象個數(shù)Num;

輸出:聚類結(jié)果R1.

①Normalization(g1);/*將g1矩陣按公式(1)歸一化*/

②R1←DPC;/*利用密度峰值聚類[17](DPC)輸出初始聚類結(jié)果*/

3.2 增量屬性聚類

在實際生活中,人們對于不同事物的認(rèn)識,往往是漸進式的,首先是對于一個對象的模糊刻畫,然后隨著時間和環(huán)境的改變,出現(xiàn)了不同方面的認(rèn)知,使得對象的認(rèn)識更加的清晰,即人類認(rèn)知不是機械的掌握一個粒度上,而是通過對每個粒度的信息的掌握,以多粒度的處理方式將信息進行細化、更新,達到了對事物的結(jié)構(gòu)化認(rèn)識.同時長期與你生活的人,往往在很多地方有著相似性,例如從事的職業(yè)或者生活習(xí)慣等,那么在對于外界而言,可以把你們認(rèn)為是同一類人,由此我們將這兩種思想,借鑒到我們的增量屬性聚類算法中.

在這項工作中,隨著時間或環(huán)境的變化,在某一時刻出現(xiàn)了新的屬性粒集合gi,考慮到屬性粒存在不同的量綱,首先將gi歸一化,然后將gi矩陣每個對象對應(yīng)的行加入到Gi-1矩陣的尾部,融合形成新的粒度Gi(如圖3所示).

利用公式(2)計算Gi矩陣?yán)飳ο笾g的歐式距離:

(2)

然后統(tǒng)計對象xa(a∈[1,n])的鄰域,找尋距離最近的N個對象,在原有的聚類結(jié)果Ri-1中查詢這N個對象的類簇歸屬,尋找包含對象最多的類簇,則i屬于該類簇.例如圖4所示xa的鄰域,當(dāng)N=5時則離xa最近5鄰居點為x1,x2,x3,x4,x5,其中有x1,x2,x3這3個對象在原有結(jié)果中屬于類簇1,x4,x5這2個對象在原有結(jié)果中屬于類簇2,那么對象xa屬于類簇1.

圖3 粒度融合Fig.3 Granular fusion

圖4 xa的鄰域Fig.4 xa neighborhood

算法3.增量屬性聚類算法(Incremental attribute clustering method,IAC)

輸入:原始粒度層Gi-1,增量粒度層gi,初始結(jié)果Ri-1,對象個數(shù)Num,鄰域選取個數(shù)N;

輸出:聚類精度Acci,聚類結(jié)果Ri.

①gi←Normalization(gi);/*將gi矩陣按公式(1)歸一化*/

②Gi←Inc_set(Gi-1,gi);/*將gi中的粒對應(yīng)的加到Gi-1矩陣?yán)锩嫔扇碌腉i*/

③ for each object do

④Di←Distance(p,q);/*計算Gi矩陣中對象間相互距離*/

⑤ end for

⑥ for each object do

⑦Neighbor(p,N);/*統(tǒng)計p鄰域中與其距離最近的N個點*/

⑧Ri(p)←Inc_cluster(p);/*根據(jù)Ri-1,統(tǒng)計鄰域中N個對象的類簇歸屬情況,選擇包含對象最多的類簇,則p屬于該類簇,將其輸出*/

⑨ end for

4 實驗分析

本文的算法采用C++語言并在工具Visual Studio 2012上實現(xiàn),所有實驗都在內(nèi)存為8G RAM、CPU頻率為2.70GHz計算機上運行.

在本節(jié)中,在UCI上的一些真實數(shù)據(jù)集驗證了本文提出的方法.表2給出了關(guān)于數(shù)據(jù)集的信息.Iris1數(shù)據(jù)集是鳶尾花卉的4個屬性所構(gòu)成的.Lsvt Voice2是牛津大學(xué)的Athanasios

1http://archive.ics.uci.edu/ml/datasets/Iris

2http://archive.ics.uci.edu/ml/datasets/LSVT+Voice+Rehabilitation

Tsanas為幫助帕金森病人的康復(fù)將126個持續(xù)元音/a/音的特征描述為310個發(fā)聲困難度.Spectf Heart3數(shù)據(jù)集描述通過計算機斷層攝影對267位患者的心臟單質(zhì)子的觀察,針對每位患者總結(jié)出44個連續(xù)的特征.Mice Protein4數(shù)據(jù)集由77個蛋白質(zhì)特征組成,有38只對照小鼠和34只三體小鼠(唐氏綜合征),共72只小鼠.該數(shù)據(jù)集每個蛋白質(zhì)總共包含1080個測量值,然后將缺省值的對象刪除后得到552個測量值.Contraceptive5數(shù)據(jù)集是1987年印度尼西亞避孕方法調(diào)查的一部分.

表2 UCI數(shù)據(jù)集
Table 2 UCI data sets

Data setsSizeDimensionClustersIris115043Lsvt Voice21263102Spectf Heart3267442Mice Protein4552778Contraceptive5147393

如表3所示,以Iris為例,首先利用密度峰值聚類算法[17]對初次粒度層(Dimension1)進行聚類,得到了初始結(jié)果以及相應(yīng)的聚類精度Acc1,以及運行時間Time1(MGIAC),然后進行方法的第二部分增量屬性算法,增加粒度層ΔDimension2與原有的粒度層結(jié)合,然后對新的多粒度層進行聚類(每次增加粒的數(shù)量與數(shù)據(jù)集屬性的個數(shù)有關(guān),如Lsvt第二次增加了10個屬性粒,而Iris第二次增加了1個屬性粒),得到相應(yīng)的聚類精度Acc2,以及增量聚類相應(yīng)的運行時間Time2(MGIAC),由表3所示,沒有新的粒度加入,則該算法結(jié)束.

如表3中所示,Time(MGIAC)表示本文的多粒度增量屬性聚類算法從初始聚類然后經(jīng)過一次或數(shù)次增量屬性聚類的有運行時間,而Time(DPC)則是利用密度峰值算法對應(yīng)增加屬性次數(shù)的重復(fù)聚類所相加的時間(如Iris的Time(DPC)為利用密度峰值聚類算法重復(fù)聚類兩次的時間).從表3中數(shù)據(jù)得本文提出的多粒度增量屬性聚類算法的時間優(yōu)于密度峰值聚類時間(Time(MGIAC)

對于Iris、Lvst、Heart、Contraceptive這4個數(shù)據(jù)集,由表3可得本文的多粒度增量屬性的聚類方法其聚類精度Acc(MGIAC)略優(yōu)于完整數(shù)據(jù)集在密度峰值聚類算法計算下的聚類精度Acc(DPC).其中我們認(rèn)為,Mice Protein數(shù)據(jù)集偏差的原因在于該數(shù)據(jù)集每個對象間的距離比較接近,并且類簇相對較多,使得本文方法的聚類結(jié)果較差.

表3 實驗結(jié)果
Table 3 Experimental results

Data setsAcciDimensioniTimei(MGIAC)Timei(DPC)Acc(MGIAC)Acc(DPC)Time(MGIAC)Time(DPC)IrisDimension 1ΔDimension 20.880.903139ms32ms39ms41ms0.90.971ms80msLsvt VoiceDimension 10.39227057ms57msΔDimension 20.4111049ms60msΔDimension 30.6672050ms61msΔDimension 40.6671051ms62ms0.6670.589207ms240msSpectf HeartDimension 10.82336187ms187msΔDimension20.8363155ms190msΔDimension 30.8923157ms192msΔDimension 40.9062159ms197ms0.9060.897656ms765msMice ProteinDimension 10.35756670ms670msΔDimension20.2816567ms690msΔDimension 30.2206573ms710msΔDimension 40.2216610ms730ms0.2210.3972420ms2800msContraceptiveDimension 10.3937930ms930msΔDimension 20.4081872ms1052msΔDimension 30.4271885ms1068ms0.4270.3942687ms3076ms

5 總 結(jié)

在生活中,對于事物的發(fā)現(xiàn)都是漸進式的.很多時候,第一次的觀察往往不能完全的描述出事物的特性,而第二次觀察一般不會拋棄第一次觀察出現(xiàn)的特性,其都是建立在第一次基礎(chǔ)上來做出評價的.針對對象數(shù)目未改變,而描述對象的粒隨著環(huán)境與時間的出現(xiàn)遞增的研究,目前涉及的比較少.因此本文針對這樣屬性增長的情況,提出了一種多粒度增量屬性的聚類方法,與一般增量聚類方法不同,該方法針對屬性粒增長的情況,通過對鄰域?qū)ο箢惔貧w屬的統(tǒng)計,以此推測增量后對象的類簇歸屬.本文的方法在UCI上的真實數(shù)據(jù)集得到了驗證,實驗結(jié)果表明本文的方法對于處理屬性增長的問題具有一定的效果;但是該方法處理類簇數(shù)比較多的數(shù)據(jù)集時效果不太好,所以接下來,該方法中還需要進一步的完善,以便于更好的處理增量屬性聚類的問題.

3http://archive.ics.uci.edu/ml/datasets/SPECTF+Heart

4http://archive.ics.uci.edu/ml/datasets/Mice+Protein+Expression

5http://archive.ics.uci.edu/ml/datasets/Contraceptive+Method+Choice