劉杭雨,于 洪

(重慶郵電大學(xué) 計(jì)算智能重慶市重點(diǎn)實(shí)驗(yàn)室,重慶 400065)

1 引 言

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

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

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

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

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

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

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

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

2 相關(guān)定義

2.1 粒度關(guān)系

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

顯而易見(jiàn),不同的粒可能具有不同的量綱,因此需要對(duì)屬性粒進(jìn)行歸一化處理,相應(yīng)的計(jì)算公式,如公式(1)所示:

(1)

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

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

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

如圖1所示,在粒度的增量過(guò)程中,g1∩g2不一定為,因?yàn)樵谏钪袑?duì)于對(duì)象的認(rèn)識(shí),第二次也出現(xiàn)與第一次相同的認(rèn)知是很正常的.

2.2 算法流程

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

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

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

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

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

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

② for eachgado

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

④Acca(Ra);/*計(jì)算聚類(lèi)精度*/

⑤ end for

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

3 多粒度增量屬性聚類(lèi)方法

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

表1 本文中的符號(hào)
Table 1 Symbols

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

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

3.1 初始聚類(lèi)

在本文中初始聚類(lèi)文獻(xiàn)[17]提出的密度峰值聚類(lèi)算法.

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

輸入:初始屬性粒g1,截?cái)嗑嚯xdc,對(duì)象個(gè)數(shù)Num;

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

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

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

3.2 增量屬性聚類(lèi)

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

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

利用公式(2)計(jì)算Gi矩陣?yán)飳?duì)象之間的歐式距離:

(2)

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

圖3 粒度融合Fig.3 Granular fusion

圖4 xa的鄰域Fig.4 xa neighborhood

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

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

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

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

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

③ for each object do

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

⑤ end for

⑥ for each object do

⑦Neighbor(p,N);/*統(tǒng)計(jì)p鄰域中與其距離最近的N個(gè)點(diǎn)*/

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

⑨ end for

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

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

在本節(jié)中,在UCI上的一些真實(shí)數(shù)據(jù)集驗(yàn)證了本文提出的方法.表2給出了關(guān)于數(shù)據(jù)集的信息.Iris1數(shù)據(jù)集是鳶尾花卉的4個(gè)屬性所構(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個(gè)持續(xù)元音/a/音的特征描述為310個(gè)發(fā)聲困難度.Spectf Heart3數(shù)據(jù)集描述通過(guò)計(jì)算機(jī)斷層攝影對(duì)267位患者的心臟單質(zhì)子的觀察,針對(duì)每位患者總結(jié)出44個(gè)連續(xù)的特征.Mice Protein4數(shù)據(jù)集由77個(gè)蛋白質(zhì)特征組成,有38只對(duì)照小鼠和34只三體小鼠(唐氏綜合征),共72只小鼠.該數(shù)據(jù)集每個(gè)蛋白質(zhì)總共包含1080個(gè)測(cè)量值,然后將缺省值的對(duì)象刪除后得到552個(gè)測(cè)量值.Contraceptive5數(shù)據(jù)集是1987年印度尼西亞避孕方法調(diào)查的一部分.

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

Data setsSizeDimensionClustersIris115043Lsvt Voice21263102Spectf Heart3267442Mice Protein4552778Contraceptive5147393

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

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

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

表3 實(shí)驗(yàn)結(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é)

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

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