隨著無線傳感網(wǎng)絡(luò)以及有關(guān)領(lǐng)域的相應(yīng)發(fā)展，流數(shù)據(jù)日益成為主要的數(shù)據(jù)形式之一。例如無線傳感器中的監(jiān)測數(shù)據(jù)，網(wǎng)絡(luò)入侵監(jiān)測數(shù)據(jù)，以及金融產(chǎn)業(yè)中不斷變化的股票數(shù)據(jù)等，即屬于此類。這些數(shù)據(jù)都具有與傳統(tǒng)靜態(tài)數(shù)據(jù)不同的特性，諸如實時、有序、快速變化等。而對于目前較為有限的存儲空間，數(shù)據(jù)流卻又無法長期保存在計算機中，因此如何在線實時有效地處理這些數(shù)據(jù)，從中挖掘提取有用的知識，即成為數(shù)據(jù)挖掘領(lǐng)域的熱點問題之一。

　　摘要：近幾年來，流數(shù)據(jù)成為主流的數(shù)據(jù)形式之一。如網(wǎng)絡(luò)入侵監(jiān)測數(shù)據(jù)，股票數(shù)據(jù)等都是不斷變化的流數(shù)據(jù)。聚類作為數(shù)據(jù)挖掘領(lǐng)域的主要技術(shù)手段之一，因此流數(shù)據(jù)的聚類也受到了眾多學(xué)者的廣泛關(guān)注。而流數(shù)據(jù)不同于靜態(tài)數(shù)據(jù)的特性給流數(shù)據(jù)的聚類帶來了挑戰(zhàn)。本文總結(jié)了傳統(tǒng)數(shù)據(jù)的聚類算法和流數(shù)據(jù)聚類挖掘的研究方法，并提出了對未來將群智能應(yīng)用于流數(shù)據(jù)聚類算法的展望。

　　關(guān)鍵詞：流數(shù)據(jù),聚類,數(shù)據(jù)挖掘,群智能

　　0引言

　　數(shù)據(jù)挖掘，亦稱作知識發(fā)現(xiàn)，是指從大量的數(shù)據(jù)中挖掘得到人們感興趣的知識的具體發(fā)現(xiàn)過程�，F(xiàn)如今，人們可以通過多種渠道獲取信息數(shù)據(jù)，隨著數(shù)據(jù)量的大幅增長，如何從這些數(shù)據(jù)中找到有價值的信息，就成為數(shù)據(jù)挖掘的首要任務(wù)。數(shù)據(jù)挖掘的分析方法主要有以下幾種：

　�。�1）關(guān)聯(lián)分析。兩個或多個數(shù)據(jù)變量之間存在著某種相關(guān)性，這就是關(guān)聯(lián)。通常情況下，數(shù)據(jù)庫中龐大數(shù)據(jù)的關(guān)聯(lián)性很難發(fā)現(xiàn)，而且關(guān)聯(lián)分析又具有一定的不確定性，因此產(chǎn)生的規(guī)則必須帶有可信度。

　�。�2）分類分析。分類是數(shù)據(jù)挖掘領(lǐng)域的一個重要技術(shù)手段。一般分為訓(xùn)練學(xué)習(xí)過程和測試過程。例如，決策樹、神經(jīng)網(wǎng)絡(luò)、k近鄰算法、貝葉斯算法等都是常見的分類技術(shù)。

　�。�3）聚類分析。作為數(shù)據(jù)挖掘、模式識別等工程和技術(shù)領(lǐng)域的研究熱點之一，聚類分析表現(xiàn)了高度優(yōu)良的性能和效果。聚類就是將一個整體的數(shù)據(jù)集劃分成若干個簇，使得不同簇之間的相似性盡可能地小，而同一個簇中的相似性又盡可能地大。

　　綜上所述，可知聚類技術(shù)是數(shù)據(jù)挖掘領(lǐng)域的重要技術(shù)方法之一，而數(shù)據(jù)流高速動態(tài)變化和一次掃描等特性卻給數(shù)據(jù)流聚類帶來了巨大的挑戰(zhàn)。如何能夠僅利用一次掃描就達到最好的聚類效果，以及如何生成任意形狀的聚類，則是近些年來研究者們深度探討的重點課題之一。

　　1傳統(tǒng)的數(shù)據(jù)聚類算法

　　傳統(tǒng)靜態(tài)的數(shù)據(jù)聚類算法對于后期數(shù)據(jù)流聚類算法的進一步研究具有相當(dāng)重要的現(xiàn)實意義，很多數(shù)據(jù)流聚類算法都是一些常見的經(jīng)典聚類算法的變形。聚類算法一般可以分為三類，分別是基于劃分的方法、基于層次的方法、基于密度的方法。在此，對這三類方法進行分別的探討和解析，具體如下。

　　1.1傳統(tǒng)的聚類方法

　�。�1）基于劃分的方法

　�。�2）基于層次的聚類方法

　　基于層次的方法通常分為自頂向下和自底向上兩種情況。在這些方法中，比較常用的就是Birch算法[1]。Birch算法中引入了CF聚類特征和CFtree聚類特征樹這兩個概念。具體過程為：首先全面掃描數(shù)據(jù)庫，建立一個初始的聚類特征樹；從根節(jié)點向下，計算與要插入的數(shù)據(jù)點間的距離，找尋最短距離，直至找到與該數(shù)據(jù)點最近的葉節(jié)點；如果吸收后大于閾值T，刪除或分裂葉節(jié)點。

　　Birch算法適用于大數(shù)據(jù)集的聚類處理，具有較低的算法空間復(fù)雜度和時間復(fù)雜度，聚類效果良好。但是，birch算法多是利用半徑來計算聚類的范圍，因此對于非球狀的聚類，就不會達到理想的效果。

　�。�3）基于密度的聚類方法

　　基于密度的聚類方法是將具有相似的密度點的數(shù)據(jù)聚合在一起，可以根據(jù)不同的密度變化將聚類拓展到任意的地方，這就彌補了基于距離聚類只能產(chǎn)生球狀實現(xiàn)效果的缺陷。但是這類算法的復(fù)雜度一般卻比較高。

　　1.2基于群智能的聚類方法

　　群智能就是昆蟲或者飛鳥等群體表現(xiàn)出來的群體智能，例如螞蟻覓食，筑巢等過程中所表現(xiàn)出來的智能。近年來，眾多學(xué)者將群智能應(yīng)用于數(shù)據(jù)聚類中，取得了良好的聚類效果。群智能優(yōu)化算法主要有蟻群優(yōu)化算法（ACO）、粒子群優(yōu)化算法（PSO）、人工魚群優(yōu)化算法等。

　　2003年，Merwe等人[2]最先提出了PSO與K-means算法結(jié)合的混合聚類算法。該算法利用K-means方法得到某組聚類的中心，并在粒子群初始化時將聚類中心賦值給某個粒子，其余粒子則隨機初始化，之后運用基本PSO聚類算法完成聚類。

　　Azzag等人提出了一種基于螞蟻覓食原理的聚類算法[3]。算法中，數(shù)據(jù)點可看作是具有不同屬性的螞蟻，而聚類中心就是螞蟻所要尋找的“食物”，由此數(shù)據(jù)聚類過程即成為螞蟻尋找食物源的過程。此外，文獻[4]繼續(xù)提出通過螞蟻自聚行為、達到聚類的蟻群聚類算法。該算法中，螞蟻能夠通過自我聚集行為構(gòu)建一個樹狀結(jié)構(gòu)，即螞蟻樹（AntTree）。螞蟻不僅代表數(shù)據(jù)，而且也代表該螞蟻樹的節(jié)點，初始狀態(tài)時將螞蟻置于一個固定點上，該點相當(dāng)于樹根。接著螞蟻在樹上已經(jīng)固定的螞蟻身上移動，尋找適合自己的位置。

　　將群智能應(yīng)用于聚類挖掘中，能夠獲得明顯優(yōu)于傳統(tǒng)聚類算法的實驗結(jié)果，也不會象傳統(tǒng)聚類算法（如K-means算法）一樣那么容易產(chǎn)生局部最優(yōu)解，只是算法的收斂時間較長。

　　2數(shù)據(jù)流聚類算法

　　由于數(shù)據(jù)流是隨時間不斷變化的，每單位時間段都有大量的數(shù)據(jù)到達，這就使得數(shù)據(jù)流中的數(shù)據(jù)將無法長期存儲，此時若采用傳統(tǒng)的數(shù)據(jù)挖掘聚類算法就無法得到很好的聚類效果�；�于此，可知數(shù)據(jù)流聚類挖掘與傳統(tǒng)的靜態(tài)數(shù)據(jù)聚類即有很大的不同，具體分析如下：

　　首先，簇個數(shù)無法假定。由于數(shù)據(jù)流的不斷變化，自然簇的個數(shù)也會相應(yīng)地隨之變化，因此無法預(yù)知簇的實際個數(shù)。其次，聚類成任意形狀的簇。在很多數(shù)據(jù)集，如網(wǎng)絡(luò)入侵檢測數(shù)據(jù)集中，聚類的分布情況通常是不均勻、且無規(guī)則的，因此能夠發(fā)掘任意形狀的聚類對于數(shù)據(jù)流聚類的應(yīng)用則是至關(guān)重要的。

　　最后，處理噪聲數(shù)據(jù)的能力。在眾多數(shù)據(jù)流應(yīng)用場景中，總會受到一些意外因素，如傳感器網(wǎng)絡(luò)中電池供電不足的影響等，這些均是數(shù)據(jù)流中產(chǎn)生的一些隨機的噪聲數(shù)據(jù)，如何能夠分辨并處理這些噪聲數(shù)據(jù)也是數(shù)據(jù)流聚類中的一大難題。

　　2.1數(shù)據(jù)流模型

　　流數(shù)據(jù)可以看作隨時間不斷變化的數(shù)據(jù)集合[5]。流數(shù)據(jù)集合為{X1，X2，X3，…，XN}，其中Xi包含兩個數(shù)據(jù)項，一個是數(shù)據(jù)ai，另一個則是數(shù)據(jù)讀入的時間點（時間戳）ti，即Xi=。而流數(shù)據(jù)將隨著時間不斷地發(fā)生變化，這就不可避免會有噪聲數(shù)據(jù)出現(xiàn)于其中，可將其稱為異常數(shù)據(jù)和孤立點數(shù)據(jù)。這些數(shù)據(jù)與研究中正常的數(shù)據(jù)行為模式并不一樣，因而如何識別孤立點噪聲數(shù)據(jù)也是數(shù)據(jù)流挖掘領(lǐng)域亟需解決的重點問題之一。

　　2.2窗口模型

　　在數(shù)據(jù)流聚類分析方法中，通常都基于時間窗口來進行。窗口模型一般可分為三種：界標(biāo)窗口模型，滑動窗口模型和衰減窗口模型。其中，界標(biāo)窗口模型則包括直方圖方法、抽樣方法、小波方法、哈希方法等。下面對這三種模型作以分別探討。

　　在界標(biāo)窗口模型中，其中之一的直方圖技術(shù)就是將一個大的數(shù)據(jù)集分割成若干個小數(shù)據(jù)集。該技術(shù)能夠直觀地反映大數(shù)據(jù)集的輪廓梗概，因此在商業(yè)數(shù)據(jù)庫中得到了廣泛應(yīng)用。另外，對于抽樣方法來說，顧名思義，就是從大的整體數(shù)據(jù)集中抽取樣本來代表整個數(shù)據(jù)集，并在樣本查詢中獲得結(jié)果。而小波分析方法則與傅里葉變換相似，小波分析是將數(shù)據(jù)輸入的模擬量，變換成一系列的小波參數(shù)，而大部分能量僅僅包含于少數(shù)幾個小波參數(shù)中，因此選擇利用少量的小波參數(shù)就能夠還原出原始的信號。

　　分類之二的滑動窗口模型提出了一個時間窗口的概念。設(shè)有數(shù)據(jù)流DS=（a1，a2，a3，…，an），其中的ax是數(shù)據(jù)項，Xi是數(shù)據(jù)流中的數(shù)據(jù)樣本點，Xt則是進入滑動窗口的時間點。W為窗口大小，tn是任意的時間點。只有時間窗口{tn-w+1，…，tn}內(nèi)的數(shù)據(jù)才得以處理，而窗口外的數(shù)據(jù)則予以忽略�？捎脠D1表示滑動窗口模型，具體如圖1所示。

　　2.3在線-離線聚類方法

　　Clustream算法完全能夠適應(yīng)數(shù)據(jù)流快速到達，有序無限以及單遍掃描的特點，并且還能夠挖掘出數(shù)據(jù)流的潛在演化特征。但是由于算法所采用的相似度標(biāo)準(zhǔn)是距離，這也就造成了該算法只能夠產(chǎn)生球形的聚類結(jié)果。而且當(dāng)數(shù)據(jù)流中存在噪聲數(shù)據(jù)時，算法將會表現(xiàn)出不穩(wěn)定性，而因為噪聲數(shù)據(jù)無法被現(xiàn)有的微簇所接受，噪聲數(shù)據(jù)就會創(chuàng)建新的微簇，進一步地，隨著噪聲數(shù)據(jù)的增加，微簇數(shù)量也隨之增多。與此同時，算法又將限制微簇數(shù)量，由此一些微簇就必須要進行相應(yīng)的合并或者刪除，這就不可避免地降低了算法聚類結(jié)果的準(zhǔn)確度。

　　而后，針對Clustream算法的這些不足，學(xué)者們又相繼提出了多種解決辦法。2004年，Aggarwal等人提出了HPStream（High-dimensionalProjectedStreamClusteringmethod）算法框架[7]。HPStream做出的主要改進有兩方面：一是算法中使用投影聚類的方法來處理高維數(shù)據(jù)流的聚類問題；二是使用一個衰減簇的概念來代替Clustream中提出的微簇，以保存歷史數(shù)據(jù)，從而利用衰減因子來實現(xiàn)不斷衰減歷史數(shù)據(jù)對整體聚類影響的不斷衰減。

　　在已有研究的基礎(chǔ)上，曹峰等人又提出了一種基于密度的進化數(shù)據(jù)流聚類算法DenStream算法[8]，同樣這也是一種在線-離線兩階段處理方法。該算法主要提出三個概念：核心微簇，潛在核心微簇和離群微簇。算法實現(xiàn)可描述為：當(dāng)接收到一個新的數(shù)據(jù)點時，算法首先判斷這一數(shù)據(jù)是否可以被潛在核心微簇（p微簇）接收，如果不可以，再嘗試將其合并到距離最近的離群微簇（o微簇）當(dāng)中。如果合并后的離群微簇半徑大于閾值，則將此離群微簇轉(zhuǎn)化為潛在核心微簇。離線部分主要采用DBSCAN算法的變形來實現(xiàn)聚類。算法微簇維護的流程圖如圖2所示。

　　3未來發(fā)展趨勢

　　FlockStream算法是將Denstream算法與一種多代理群智能Flocking模型相結(jié)合而加以設(shè)計并最終實現(xiàn)的。該算法采用分散的、自下而上的自我組織戰(zhàn)略對相似的數(shù)據(jù)點進行聚類分組，數(shù)據(jù)點與仿生模型中的boid相關(guān)聯(lián)并應(yīng)用啟發(fā)式策略進行聚類，在聚類效果上占有很大的優(yōu)勢[11]。該算法將仿生模型與數(shù)據(jù)流聚類算法相結(jié)合。獲得了比較好的聚類效果。

　　通過以上分析可以看到，近幾年來數(shù)據(jù)流聚類算法得到了許多學(xué)者的關(guān)注。同時，群智能算法具有魯棒性和自組織等優(yōu)點，并且能夠在沒有建立全局模型的情況下，對大量的數(shù)據(jù)搜索亦能取得良好的效果，群智能算法確實有著其它優(yōu)化算法無可比擬的優(yōu)勢。進一步地，將群智能算法與傳統(tǒng)的聚類算法相結(jié)合，也已獲取了較好的聚類效果。因此在未來的研究中，可以將群智能優(yōu)化算法應(yīng)用到流數(shù)據(jù)聚類算法中，旨在實現(xiàn)聚類效果的高效性和穩(wěn)定性。

　　參考文獻：

　　[1]ZHANGT，RAMAKRISHNANR，LLVNYM.BIRCH：Aneffieientdataclusteringmethodforverylargedatabases[C]//Proc.1996ACM-SIGMODInt.Conf.Magementofdata（SIGMOD，96），103-114.

　　[2]MERWEDWvanderENGELBRECHTAP.Dataclusteringusingparticleswarmoptimization[C]//ProcofIEEECongressonEvolutionaryComputation，2003：215-220.[3]楊欣斌，孫京誥，黃道.基于蟻群聚類算法的離群挖掘方法[J].計算機工程與應(yīng)用，2003，（9）：12-13+37.

　　[4]AZZAGH，MONMARCHEN，SLIMANCEM，etal.AntTree：anewmodelforclusteringwithartificialants[C]//IEEECongressonEvolutionaryComputation，Canberra，Australia，2003：8-12.

　　[5]ENZINGERHMR，RAGHAVANP，RAJAGOPALANS.Computingondatastreams.SRCTechnicalNote1998-011.Digitalsystemsresearchcenter：PaloAlto，California，1998.

　　[6]AGGARWALCC，HANJ，WANGJ，etal.Aframeworkforclusteringevolvingdatastreams.FREYTAGJC，LOCKEMPC，ABITEBOULS，etal，eds[C]//Proc.oftheInt’lConf.onVeryLargeDataBases.Berlin：MorganKaufmannPublishers，2003：81-92.

　　[7]AGGARWALCC，HANJ，WANGJ，eta1.Aframeworkforprojectedclusteringofhighdimensionaldatastreams[C]//Proceedingsofthe30thInformationalConferenceonVeryLargeDataBases，2004：852-863.

　　[8]CAOF，ESTERM，QIANW，etal.Density-basedclusteringoverevolvingdatastreamwithnoise[C]//ProceedingsofthesixthSIAMinternationalconferenceondatamining（SIAM’06），Bethesda，2006：326–337.

　　[9]CHENYX，TUL.Density-basedclusteringforreal-timestreamdata[C]//Proceedingsofthe13thACMSIGKDDinternationalconferenceonKnowledgeDiscoveryandDataMining.California：ACM，2007：133-142.

　　[10]黃德才，吳天虹.基于密度的混合屬性數(shù)據(jù)流聚類算法[J].控制與決策，2010，（3）：416-421.

　　[11]FORESTIEROA，PIZZUTIC，SPEZZANOG.Asinglepassalgorithmforclusteringevolvingdatastreamsbasedonswarmintelligence[J].DataMinKnowlDisc，2013，26：1–26.

---

轉(zhuǎn)載請注明來自：http://www.jinnzone.com/zhinengkexuejishulw/34214.html