程軍鋒

?

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

程軍鋒

(隴南師范高等?？茖W(xué)校 物理與信息技術(shù)系，甘肅 隴南 742500)

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

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

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

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

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

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

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

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

1.2 STREAM算法

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

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

1.3 CluStream算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)束語

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

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

[2] 尤薇佳,劉魯,劉丹,等.基于Squeezer算法的文本數(shù)據(jù)流聚類[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ù)流聚類算法[J].模式識別與人工智能,2009(2):246-254.

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

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

[8] 黃紅艷,安素芳.數(shù)據(jù)流聚類算法在入侵檢測中的應(yīng)用[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é)任編校：李建明 英文校對：李玉玲)

10.3969/j.issn.1673-2065.2015.01.005

TP311

A

1673-2065(2015)01-0016-03

2014-09-25

程軍鋒(1980-)，男，甘肅禮縣人，隴南師范高等?？茖W(xué)校物理與信息技術(shù)系講師．