數(shù)據(jù)流挖掘中的聚類(lèi)技術(shù)

程軍鋒

?

數(shù)據(jù)流挖掘中的聚類(lèi)技術(shù)

程軍鋒

(隴南師范高等專(zhuān)科學(xué)校 物理與信息技術(shù)系，甘肅 隴南 742500)

在動(dòng)態(tài)數(shù)據(jù)流挖掘過(guò)程中，對(duì)數(shù)據(jù)流進(jìn)行聚類(lèi)，把未知的數(shù)據(jù)流劃分或者生成到一個(gè)簇中．發(fā)現(xiàn)隱含的知識(shí)、價(jià)值和模式，是一種非常有效的數(shù)據(jù)流挖掘技術(shù)．分析和研究了數(shù)據(jù)流挖掘的聚類(lèi)算法，并對(duì)數(shù)據(jù)流聚類(lèi)技術(shù)發(fā)展進(jìn)行了展望，提出了數(shù)據(jù)流挖掘的研究方向．

數(shù)據(jù)流；挖掘；聚類(lèi)；算法

隨著監(jiān)控設(shè)備、網(wǎng)絡(luò)點(diǎn)擊和交易等網(wǎng)絡(luò)應(yīng)用，數(shù)據(jù)流挖掘已經(jīng)成為一個(gè)研究的熱點(diǎn)．?dāng)?shù)據(jù)流是指隨時(shí)間源源不斷到達(dá)的數(shù)據(jù)，通常有數(shù)據(jù)量大、連續(xù)達(dá)到等特點(diǎn)．對(duì)于這些海量的數(shù)據(jù)，通過(guò)數(shù)據(jù)挖掘的聚類(lèi)技術(shù)找出隱藏的類(lèi)和模式，已經(jīng)被應(yīng)用到商業(yè)和金融等領(lǐng)域．

聚類(lèi)是一種非監(jiān)督學(xué)習(xí)的數(shù)據(jù)挖掘技術(shù)，聚類(lèi)是一個(gè)把數(shù)據(jù)對(duì)象劃分成多個(gè)組或簇的過(guò)程，使得簇內(nèi)的對(duì)象具有很高的相似性，但與其他簇中對(duì)象盡可能相異，也就是說(shuō)最大化類(lèi)內(nèi)部的相似性，最小化類(lèi)之間的相似性[1]．在數(shù)據(jù)流的挖掘中聚類(lèi)分析技術(shù)在許多環(huán)境下非常有用．傳統(tǒng)的聚類(lèi)算法通常通過(guò)對(duì)數(shù)據(jù)進(jìn)行反復(fù)多次掃描，以發(fā)現(xiàn)數(shù)據(jù)流中隱含的類(lèi)，但由于數(shù)據(jù)流數(shù)據(jù)隨時(shí)間不斷到達(dá)，數(shù)據(jù)量大，不會(huì)被存儲(chǔ)，不能進(jìn)行多次掃描．因此，使用傳統(tǒng)的數(shù)據(jù)挖掘聚類(lèi)算法在數(shù)據(jù)流挖掘中并不適合．

對(duì)于數(shù)據(jù)流的挖掘聚類(lèi)，通常要采用全新的數(shù)據(jù)結(jié)構(gòu)和技術(shù)．在數(shù)據(jù)流的聚類(lèi)過(guò)程中，已經(jīng)有許多比較著名的算法，這些算法有的是對(duì)傳統(tǒng)的聚類(lèi)算法進(jìn)行得改進(jìn)，使得它們更適合數(shù)據(jù)流的挖掘，還有一些是根據(jù)數(shù)據(jù)流的特點(diǎn)設(shè)計(jì)出來(lái)的全新算法，這些算法在數(shù)據(jù)流的處理和分析中都非常有用，可以產(chǎn)生用戶(hù)感興趣的結(jié)果．

1 主要的數(shù)據(jù)流聚類(lèi)算法

1.1 一趟數(shù)據(jù)流聚類(lèi)算法

一趟數(shù)據(jù)流聚類(lèi)算法基于最小距離，將新到達(dá)的數(shù)據(jù)和原有的數(shù)據(jù)進(jìn)行求熵，看這個(gè)數(shù)據(jù)和原有數(shù)據(jù)之間的相似度，如果相似度不大于某一個(gè)指定的閾值，則認(rèn)為這個(gè)數(shù)據(jù)和某個(gè)已有的簇比較相似，就把該數(shù)據(jù)歸為一個(gè)已有的最相似的簇中去．如果當(dāng)前數(shù)據(jù)和原有數(shù)據(jù)的相似度都比較小，則認(rèn)為該數(shù)據(jù)和已有的簇都不相似，該數(shù)據(jù)將作為一個(gè)新的簇并進(jìn)行構(gòu)建．通常數(shù)據(jù)間的相似度可通過(guò)簇心和該數(shù)據(jù)求它們的距離，比較著名的有歐幾里德距離和曼哈頓距離等．其中最簡(jiǎn)單一趟聚類(lèi)算法是基于k-means算法，k-means算法是通過(guò)計(jì)算一個(gè)數(shù)據(jù)對(duì)象與簇的質(zhì)心距離，來(lái)確定它們時(shí)間的相似度，把該對(duì)象賦予相似度最大的簇．一趟數(shù)據(jù)流聚類(lèi)算法實(shí)現(xiàn)簡(jiǎn)單，算法的時(shí)間復(fù)雜度和問(wèn)題規(guī)模成線(xiàn)性變化，在處理高速變化的數(shù)據(jù)流時(shí)效率不是很高，而且由于采用距離來(lái)衡量數(shù)據(jù)之間的相似度，因此對(duì)球形數(shù)據(jù)比較敏感．基于高維的一趟數(shù)據(jù)聚類(lèi)Squeezer算法也可以用于數(shù)據(jù)流的聚類(lèi)，而ID-Squeezer[2]是一種改進(jìn)的應(yīng)用于數(shù)據(jù)流文本聚類(lèi)方面的算法．

1.2 STREAM算法

STREAM算法[3]是基于中位數(shù)的數(shù)據(jù)流聚類(lèi)算法，它是一種單遍掃描，接近常數(shù)因子的近似聚類(lèi)算法，是以中位數(shù)問(wèn)題開(kāi)發(fā)的．中位數(shù)問(wèn)題是把個(gè)數(shù)據(jù)點(diǎn)聚類(lèi)成個(gè)簇或組，使得點(diǎn)與它的簇的中心點(diǎn)之間誤差平方和(SSQ)最?。甋TREAM在工作時(shí)把處理的個(gè)桶中的數(shù)據(jù)流，由于每個(gè)桶較小，都可以放在內(nèi)存．對(duì)于每個(gè)桶，STREAM把每個(gè)桶的點(diǎn)分成簇．然后，僅通過(guò)保留個(gè)中心信息來(lái)匯總桶的信息．一旦收集到足夠的中心，加權(quán)中心將再次聚類(lèi)，以產(chǎn)生另外()個(gè)簇中心集合．如此重復(fù)，以便在每個(gè)層最多保留個(gè)點(diǎn)．這種方法導(dǎo)致單次掃描，時(shí)間復(fù)雜度為()，空間復(fù)雜度為()、數(shù)據(jù)流的中位數(shù)常量因子近似算法．

STREAM算法源于中位數(shù)聚類(lèi)，使用有限時(shí)間和空間可得到不錯(cuò)的聚類(lèi)效果．然而它沒(méi)有考慮數(shù)據(jù)的演變和時(shí)間粒度的變化．聚類(lèi)可能受控于舊的、過(guò)期的數(shù)據(jù)流，不能反映數(shù)據(jù)流的動(dòng)態(tài)性，而在實(shí)際應(yīng)用中，數(shù)據(jù)流應(yīng)該是隨著時(shí)間而變化的．

1.3 CluStream算法

CluStream算法[4]由Aggarwal于2003年提出的一個(gè)解決數(shù)據(jù)流聚類(lèi)問(wèn)題的框架，CluStream是一種基于用戶(hù)指定的，聯(lián)機(jī)聚類(lèi)查詢(xún)的演變數(shù)據(jù)流聚類(lèi)算法．它將聚類(lèi)的過(guò)程分成聯(lián)機(jī)和脫機(jī)2部分．聯(lián)機(jī)部分使用微簇計(jì)算和存儲(chǔ)數(shù)據(jù)流的匯總統(tǒng)計(jì)信息，并進(jìn)行增量聯(lián)機(jī)計(jì)算和維護(hù)微簇．在CluStream算法中，微簇?fù)砭垲?lèi)特征表示，它擴(kuò)展了BIECH聚類(lèi)特征樹(shù)的聚類(lèi)特征概念．通常微簇是一個(gè)由(2d+3)的元組組成的，用(,,,,)，來(lái)表示微簇中包含的數(shù)據(jù)點(diǎn)個(gè)數(shù)，表示為微簇中數(shù)據(jù)點(diǎn)的平均值，表示微簇中數(shù)據(jù)點(diǎn)的平方和，若數(shù)據(jù)維度為，則與均為維向量，表示各個(gè)數(shù)據(jù)點(diǎn)時(shí)間標(biāo)簽的平均值，表示各個(gè)數(shù)據(jù)點(diǎn)時(shí)間標(biāo)簽的平方和．脫機(jī)部分進(jìn)行宏聚類(lèi)，并且利用存儲(chǔ)的基于傾斜時(shí)間框架模型的匯總統(tǒng)計(jì)信息來(lái)回答用戶(hù)的各種應(yīng)答．

聯(lián)機(jī)微簇分成2個(gè)階段．1) 收集統(tǒng)計(jì)：維護(hù)由內(nèi)存大小決定的個(gè)微簇M1，M2，M3，…，Mn；2) 更新微簇：把每個(gè)數(shù)據(jù)點(diǎn)加到一個(gè)已有的簇和一個(gè)新的簇中去．為了判斷是否需要定義一個(gè)新簇，為每個(gè)簇定義了一個(gè)最大邊界，如果新點(diǎn)落在這個(gè)邊界內(nèi)，將它加到簇中；否則，它將成為新簇的第一個(gè)數(shù)據(jù)點(diǎn)建立簇．聚類(lèi)特征有可加性，這個(gè)特征在流聚類(lèi)中非常有用，在聚類(lèi)過(guò)程中通過(guò)可加就可以把一些微簇進(jìn)行合并，盡量使得在內(nèi)存中有少量的微簇．當(dāng)數(shù)據(jù)點(diǎn)添加到已有簇中時(shí)，由于簇的可加性，它就被吸收了．當(dāng)某個(gè)數(shù)據(jù)點(diǎn)添加為一個(gè)新簇時(shí)，依賴(lài)于特定的標(biāo)準(zhǔn)，刪除最近最少使用的簇或合并2個(gè)已有的簇，以便為新的簇提供內(nèi)存空間．

脫機(jī)部分可以執(zhí)行用戶(hù)的宏聚類(lèi)或演繹演變分析．宏聚類(lèi)允許用戶(hù)探索不同的時(shí)間范圍內(nèi)的流聚類(lèi)，演繹分析考慮新增的數(shù)據(jù)和現(xiàn)有的數(shù)據(jù)之間的演變性質(zhì)，比如是否有原來(lái)的簇出現(xiàn)位置和信息的漂移等．

CluStream算法可以產(chǎn)生高質(zhì)量的簇，特別當(dāng)數(shù)據(jù)劇烈變化時(shí)，它為用戶(hù)提供了豐富的功能，因?yàn)樗鎯?chǔ)了關(guān)于簇演變的基本歷史信息，傾斜時(shí)間框架和微聚類(lèi)結(jié)構(gòu)為真實(shí)數(shù)據(jù)提供更好的精確性和效率．它在流大小、維度和簇方面保持了可伸縮性．

針對(duì)CluStream的兩點(diǎn)不足，Aggarwal等在次年提出了HPStream算法框架．HpStream算法是CluStream算法的一個(gè)改進(jìn)，主要使用投影聚類(lèi)處理高維數(shù)據(jù)，并使用衰減結(jié)構(gòu)來(lái)保存歷史數(shù)據(jù)，實(shí)現(xiàn)了數(shù)據(jù)的集成，使得它適合處理高維數(shù)據(jù)．但它沒(méi)有考慮數(shù)據(jù)的衰減性問(wèn)題，不能體現(xiàn)近期數(shù)據(jù)的重要性，在被應(yīng)用于處理高維數(shù)據(jù)流時(shí)效率一般．

1.4 其他數(shù)據(jù)流聚類(lèi)算法

E-stream算法通過(guò)定義5種不同演化類(lèi)型來(lái)表示數(shù)據(jù)流的演化行為，能夠反映數(shù)據(jù)流的變化特性，比較適合數(shù)據(jù)流挖掘．Den-stream算法是一種基于密度的數(shù)據(jù)流聚類(lèi)算法，改進(jìn)了STREAM、CluStream等算法基于距離的度量，對(duì)球狀數(shù)據(jù)流比較敏感，可以發(fā)現(xiàn)任意形狀的數(shù)據(jù)流．D-stream是一種基于密度和網(wǎng)格的算法，也是用于解決任意形狀的數(shù)據(jù)流聚類(lèi)，也是分成2部分，聯(lián)機(jī)部分接收數(shù)據(jù)并把它們映射到網(wǎng)格空間的對(duì)應(yīng)網(wǎng)格單元中，脫機(jī)部分根據(jù)密度，在網(wǎng)格空間中進(jìn)行聚類(lèi)．而CFR算法是一個(gè)基于回歸分析的數(shù)據(jù)流聚類(lèi)的方法，通過(guò)相關(guān)評(píng)價(jià)函數(shù)來(lái)實(shí)現(xiàn)聚類(lèi)，采用Mahalanobis距離度量簇之間的相似度．

2 數(shù)據(jù)流聚類(lèi)挖掘算法研究展望

2.1 數(shù)據(jù)流聚類(lèi)算法的改進(jìn)和提高

對(duì)于海量的數(shù)據(jù)流進(jìn)行聚類(lèi)，應(yīng)根據(jù)其動(dòng)態(tài)變化特點(diǎn)對(duì)現(xiàn)有數(shù)據(jù)流聚類(lèi)算法進(jìn)行改進(jìn)，并設(shè)計(jì)出新的數(shù)據(jù)流聚類(lèi)算法，提高對(duì)數(shù)據(jù)流聚類(lèi)的處理效率，使得它們具有較強(qiáng)的擴(kuò)展性，能夠完成數(shù)據(jù)流聚類(lèi)的各種任務(wù)．同時(shí)，把其他的新技術(shù)和一些其他領(lǐng)域的算法應(yīng)用到數(shù)據(jù)流聚類(lèi)當(dāng)中來(lái)，改進(jìn)挖掘的質(zhì)量，也是一個(gè)重要的研究方向．有文獻(xiàn)[5]提出一種基于免疫原理的數(shù)據(jù)流聚類(lèi)算法(AIN-STREAM)，該算法能夠動(dòng)態(tài)適應(yīng)數(shù)據(jù)流的變化，并能有效抑制噪聲．還有文獻(xiàn)[6]提出了一種基于關(guān)聯(lián)函數(shù)的數(shù)據(jù)流聚類(lèi)算法，通過(guò)建立解決問(wèn)題所需要的關(guān)聯(lián)函數(shù)，計(jì)算關(guān)聯(lián)函數(shù)的值，通過(guò)此值的大小來(lái)判斷數(shù)據(jù)點(diǎn)屬于某個(gè)簇的程度．

2.2 數(shù)據(jù)流聚類(lèi)算法處理能力的研究

隨著網(wǎng)絡(luò)接入設(shè)備的增多、應(yīng)用范圍的擴(kuò)大．當(dāng)前數(shù)據(jù)流類(lèi)型越來(lái)越復(fù)雜，這些數(shù)據(jù)流來(lái)自于不同的數(shù)據(jù)源，數(shù)據(jù)豐富，而且這些數(shù)據(jù)又是異構(gòu)的，這就對(duì)數(shù)據(jù)流聚類(lèi)挖掘算法提出了新的要求，要求數(shù)據(jù)流聚類(lèi)算法必須要有一定的擴(kuò)展性和適應(yīng)性，能夠?qū)?fù)雜的數(shù)據(jù)進(jìn)行聚類(lèi)，并產(chǎn)生良好的結(jié)果．有文獻(xiàn)[7]針對(duì)多條數(shù)據(jù)流的聚類(lèi)算法質(zhì)量和效率的矛盾，提出了基于相關(guān)系數(shù)的多條數(shù)據(jù)流的聚類(lèi)算法，實(shí)現(xiàn)固定長(zhǎng)度的在線(xiàn)動(dòng)態(tài)聚類(lèi)．

2.3 數(shù)據(jù)流聚類(lèi)算法的應(yīng)用研究

數(shù)據(jù)流應(yīng)用系統(tǒng)的大量應(yīng)用，對(duì)數(shù)據(jù)流聚類(lèi)算法的應(yīng)用提供了廣闊的空間，聚類(lèi)算法對(duì)于動(dòng)態(tài)變化，不可預(yù)知類(lèi)的分類(lèi)有著一定的優(yōu)勢(shì)，如何把聚類(lèi)算法應(yīng)用到實(shí)際當(dāng)中去，也是一個(gè)數(shù)據(jù)流聚類(lèi)研究的重要方面．如在網(wǎng)絡(luò)的入侵檢測(cè)系統(tǒng)、電信通話(huà)數(shù)據(jù)流、金融交易數(shù)據(jù)流和超市購(gòu)物中等．而且在不同的應(yīng)用場(chǎng)合，對(duì)數(shù)據(jù)流聚類(lèi)算法有不同的要求，但總有一種聚類(lèi)算法能夠體現(xiàn)數(shù)據(jù)流聚類(lèi)算法的應(yīng)用價(jià)值，滿(mǎn)足實(shí)際的需要．有文獻(xiàn)[8]研究了數(shù)據(jù)流聚類(lèi)在入侵檢測(cè)系統(tǒng)的應(yīng)用，提出DC-stream算法，采用在線(xiàn)離線(xiàn)兩階段聚類(lèi)，通過(guò)一套緩沖式異常點(diǎn)處理機(jī)制，在保證數(shù)據(jù)流聚類(lèi)效率和精度的同時(shí)，能夠過(guò)濾噪音數(shù)據(jù)．

3 結(jié)束語(yǔ)

隨著云計(jì)算、物聯(lián)網(wǎng)技術(shù)的發(fā)展，大數(shù)據(jù)時(shí)代即將來(lái)臨．如何在這些由監(jiān)控設(shè)備、互聯(lián)設(shè)備等傳來(lái)的持續(xù)數(shù)據(jù)流中發(fā)現(xiàn)有價(jià)值的知識(shí)和模式，必將是一項(xiàng)嚴(yán)峻的挑戰(zhàn)．同時(shí)，這也為數(shù)據(jù)流聚類(lèi)處理技術(shù)發(fā)展提供了良好的機(jī)遇．

[1] 范明,孟小峰.數(shù)據(jù)挖掘概念與技術(shù)[M].2版.北京:機(jī)械工業(yè)出版社.2007:251-305.

[2] 尤薇佳,劉魯,劉丹,等.基于Squeezer算法的文本數(shù)據(jù)流聚類(lèi)[J].控制與決策,2012(5):542-546.

[3] O’CALLAGHAN L, MISHRA N, MEYERSON A, et al. Streaming-data algorithms for high-quality clustering[C]//IEEE International Conference on Data Engineering. San Jose:IEEE Computer Society,2002:685-694.

[4] AGGARWAL C C, HAN Jiawei, WANG Jianyong, et al. A framework for clustering evolving data streams[C]//29th International Conference on Very Large Data Bases. Berlin: Morgan Kaufmann Publishers,2003:81-92.

[5] 王述云,張成洪,郝秀蘭,等.基于免疫原理的數(shù)據(jù)流聚類(lèi)算法[J].模式識(shí)別與人工智能,2009(2):246-254.

[6] 潘麗娜,王治和,黨輝.基于關(guān)聯(lián)函數(shù)的數(shù)據(jù)流聚類(lèi)算法[J].計(jì)算機(jī)應(yīng)用,2013(1):202-206.

[7] 陳崚,鄒凌君,屠莉.多數(shù)據(jù)流的實(shí)時(shí)聚類(lèi)算法[J].計(jì)算機(jī)應(yīng)用,2007(8):1976-1979.

[8] 黃紅艷,安素芳.數(shù)據(jù)流聚類(lèi)算法在入侵檢測(cè)中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用,2012(20):112-116.

The Clustering Technology in Data Stream Mining

CHENG Jun-feng

(Department of Physics and Information Technology, Longnan Teachers College, Longnan, Gansu 742500, China)

In the process of dynamic data stream mining, the data stream is divided and the unknown data stream is classified into a cluster. The implicit knowledge, values and mode are found. It is a kind of very effective data stream mining technology. It has analyzed andstudied the clustering algorithm of data stream mining, and prospected the development of clustering technology in data stream and put forward the direction of data stream mining.

data stream; mining; cluster; algorithm

(責(zé)任編校：李建明 英文校對(duì)：李玉玲)

10.3969/j.issn.1673-2065.2015.01.005

TP311

A

1673-2065(2015)01-0016-03

2014-09-25

程軍鋒(1980-)，男，甘肅禮縣人，隴南師范高等專(zhuān)科學(xué)校物理與信息技術(shù)系講師．