數(shù)據(jù)流聚類算法CluStream介紹

經(jīng)典數(shù)據(jù)流聚類算法CluStream概要,報(bào)告人：高賀慶時(shí)間：2012-9-23,背景,隨著計(jì)算機(jī)軟硬件的不斷升級，人們獲取數(shù)據(jù)能力越來越高。在電信、金融、天氣預(yù)報(bào)、網(wǎng)絡(luò)入侵檢測、傳感器網(wǎng)絡(luò)等領(lǐng)域出現(xiàn)了一種不同于傳統(tǒng)靜態(tài)數(shù)據(jù)的流數(shù)據(jù)。這種數(shù)據(jù)流有自己的特點(diǎn)。,數(shù)據(jù)流特點(diǎn),1、數(shù)據(jù)實(shí)時(shí)達(dá)到2、數(shù)據(jù)到達(dá)次序獨(dú)立，不受系統(tǒng)控制3、數(shù)據(jù)量是巨大的，不能預(yù)知其大小4、單次掃描，數(shù)據(jù)一經(jīng)處理，除非特意保存，否則不能再次被處理,數(shù)據(jù)流聚類,聚類是數(shù)據(jù)挖掘中一類重要的問題，在許多領(lǐng)域有其應(yīng)用之處。聚類定義：給定一個(gè)有許多數(shù)據(jù)元素組成的集合，我們將其分為不同的組（類、簇），使得組內(nèi)的元素盡可能的相似，不同組之間的元素盡可能的不同。由于數(shù)據(jù)流的特點(diǎn)，對它的聚類算法提出了新的要求。,數(shù)據(jù)流聚類算法要求,1、壓縮的表達(dá)（概要數(shù)據(jù)）2、迅速、增量地處理新到達(dá)的數(shù)據(jù)3、快速、清晰地識(shí)別離群點(diǎn),CluStream概要,C.C.Aggarwal等人在2003年提出了該著名的經(jīng)典數(shù)據(jù)流聚類框架。它引入了簇和時(shí)間幀結(jié)構(gòu)兩個(gè)主要的概念，將數(shù)據(jù)流聚類過程分為在線部分（微聚類）和離線部分（宏聚類）。在線部分實(shí)時(shí)處理新到達(dá)的數(shù)據(jù)，并周期性的存儲(chǔ)統(tǒng)計(jì)結(jié)果；離線部分就利用這些統(tǒng)計(jì)結(jié)果結(jié)合用戶輸入得到聚類結(jié)果。,CluStream的影響,CluStream兩階段框架是一個(gè)著名的框架，后續(xù)有許多算法在其基礎(chǔ)上進(jìn)行各方面的改進(jìn)。它的在線部分可以實(shí)時(shí)處理較快速度的流數(shù)據(jù)，并得到統(tǒng)計(jì)結(jié)果。離線部分結(jié)合用戶輸入的參數(shù)可以近似得到過去某些時(shí)候的聚類結(jié)果。,CLuStream算法的核心概念,微簇（Micro-clusters）時(shí)間衰減結(jié)構(gòu)（PyramidalTimeFrame）,數(shù)據(jù)流一種形式化描述,數(shù)據(jù)流計(jì)算模型,界標(biāo)模型滑動(dòng)窗口模型衰減模型,微簇（Micro-clusters）,CluStream以微簇的形式維護(hù)關(guān)于數(shù)據(jù)位置的統(tǒng)計(jì)信息。這些微簇被定義成簇特征向量在時(shí)間上的擴(kuò)展。這些微簇額外增加的時(shí)間屬性很自然將其應(yīng)用于解決數(shù)據(jù)流問題。在上述數(shù)據(jù)流定義下，微簇是一個(gè)2d+3（d是數(shù)據(jù)維度）的元組,時(shí)間幀結(jié)構(gòu)（PyramidalTimeFrame）,上述微簇需要在某些時(shí)刻維護(hù)和存儲(chǔ)到磁盤以供離線階段查詢。由于數(shù)據(jù)量巨大，不可能將所有時(shí)刻的微簇信息都存儲(chǔ)到磁盤（這部分信息叫做快照），因此引入時(shí)間幀結(jié)構(gòu)。它將時(shí)間軸劃分成不同粒度的時(shí)刻，結(jié)果是離現(xiàn)在的越近粒度越細(xì)，反之越粗。,T=55的時(shí)間軸劃分,這種時(shí)間幀結(jié)構(gòu)的一些好處。1.能滿足用戶對最近數(shù)據(jù)感興趣的需求；2.運(yùn)行100年的數(shù)據(jù)流僅僅需要存儲(chǔ)大概95個(gè)快照，這能滿足有限內(nèi)存的需求。,在線部分（微簇維護(hù)）,初始化簇首先在磁盤上存儲(chǔ)最初始的initNumber個(gè)數(shù)據(jù)點(diǎn)，然后采用標(biāo)準(zhǔn)的k-means算法形成q個(gè)微簇：M1、M2Mq。在線處理對于以后達(dá)到的每一個(gè)數(shù)據(jù)點(diǎn)Xik，要么被上述的某個(gè)微簇吸收，要么放進(jìn)它自己的簇中。首先計(jì)算Xik與q個(gè)微簇中的每一個(gè)的距離（實(shí)際上是其中心）。將其放到離它最近的那個(gè)簇Mp中。,特殊情況1.Xik雖然離Mp最近，但是Xik卻在Mp的邊界外；2.由于數(shù)據(jù)流的演化，Xik可能是一個(gè)新簇的開端。處理方法為落在邊界外的數(shù)據(jù)點(diǎn)創(chuàng)建一個(gè)帶獨(dú)有標(biāo)志id的新簇，這需要減少一個(gè)其他已經(jīng)存在的簇。這可以通過刪除一個(gè)最早的簇或者合并兩個(gè)最早的簇來實(shí)現(xiàn)。,如何安全刪除？估計(jì)每一個(gè)簇中最后m個(gè)達(dá)到的數(shù)據(jù)點(diǎn)的平均時(shí)間戳，然后刪除帶有最小時(shí)間戳的值（時(shí)間越早值越小且小于用戶定義的閾值）的那個(gè)簇。這種方法只增加了存儲(chǔ)每個(gè)簇中最后m個(gè)點(diǎn)的數(shù)據(jù)的信息（時(shí)間戳）。,何時(shí)合并？有些情況下，不能合并任何兩個(gè)微簇。這種情況是發(fā)生在當(dāng)所有上述計(jì)算的時(shí)間值都大于那個(gè)閾值，此時(shí)需要合并某兩個(gè)靠的最近的微簇。此時(shí)用它們原來的id一起標(biāo)志這個(gè)新的微簇。同時(shí)，需要存儲(chǔ)金字塔時(shí)間結(jié)構(gòu)對應(yīng)時(shí)刻的微簇（實(shí)際上指的是微簇的特征向量值）到磁盤。,離線部分（宏簇創(chuàng)建）,用戶在該部分可以在不同時(shí)間幅度內(nèi)發(fā)現(xiàn)簇。這部分所用的數(shù)據(jù)是在線部分形成的統(tǒng)計(jì)信息，這可以滿足內(nèi)存有限的需求。用戶提供兩個(gè)參數(shù)h和k，h是時(shí)間幅度，k是預(yù)定義的需要形成的簇的數(shù)目。,k-means算法,基本步驟1.從n個(gè)數(shù)據(jù)對象任意選擇k個(gè)對象作為初始聚類中心；2.根據(jù)每個(gè)聚類對象的均值（中心對象），計(jì)算每個(gè)對象與這些中心對象的距離；并根據(jù)最小距離重新對相應(yīng)對象進(jìn)行劃分；3.重新計(jì)算每個(gè)（有變化）聚類的均值（中心對象）；4.計(jì)算標(biāo)準(zhǔn)測度函數(shù)，當(dāng)滿足一定條件，如函數(shù)收斂時(shí)，則算法終止；如果條件不滿足則回到步驟2。,離線部分算法,該部分采用改進(jìn)的k-means算法（1）初始階段不在隨機(jī)的選取種子，而是選擇可能被劃分到給定簇的種子，這些種子其實(shí)是對應(yīng)微簇的中心。（2）劃分階段一個(gè)種子到一個(gè)“偽數(shù)據(jù)點(diǎn)”（也就是微簇）的距離就等于它到“偽數(shù)據(jù)點(diǎn)”中心的距離。（3）調(diào)整階段一個(gè)給定劃分的新種子被定義成那個(gè)劃分中帶權(quán)重的微簇中心。,簇演化分析,CluStream可以進(jìn)行演化分析演化分析就是分析數(shù)據(jù)流在過去一段時(shí)間內(nèi)潛在的一些變化。比如在入侵檢測系統(tǒng)檢測到在某一時(shí)間段收到某種類型的攻擊。,實(shí)驗(yàn)評估,一、數(shù)據(jù)集合選擇二、評估手段,數(shù)據(jù)集,人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集。由人工數(shù)據(jù)集相關(guān)屬性容易被控制，用它來評估算法在不同緯度和不同聚類數(shù)目上的性能。用真實(shí)數(shù)據(jù)集來評估算法的有效性以及在評估其是否能發(fā)現(xiàn)數(shù)據(jù)流潛在的演化特性。,評估手段,SSQ:評估聚類質(zhì)量運(yùn)行時(shí)間：評估算法效率靈敏度：對參數(shù)的敏感程度,CluStream算法優(yōu)缺點(diǎn),優(yōu)點(diǎn)：提出了兩階段聚類框架，算法能適應(yīng)數(shù)據(jù)流快速、有序無限、單遍掃描的特點(diǎn)。能夠發(fā)掘數(shù)據(jù)流潛在的演化特性。缺點(diǎn)：1、不能發(fā)現(xiàn)任意形狀的簇；2、不能很好地識(shí)別離群點(diǎn)；3、對高維數(shù)據(jù)聚類質(zhì)量下降；,后續(xù)研究,基于兩層次的數(shù)據(jù)路聚類解決高維問題的數(shù)據(jù)流聚類（HPStream）基于滑動(dòng)窗口的數(shù)據(jù)流聚類（Clu-Win）基于密度的數(shù)據(jù)流聚類（ACluStream、DenStream及改進(jìn)）基于網(wǎng)格的數(shù)據(jù)流聚類（D-Stream及改進(jìn)）采用樹索引的網(wǎng)格數(shù)據(jù)流聚類（CD-Stream、TDCA）基于分形維度的數(shù)據(jù)路聚類（FCluStream）,參考文獻(xiàn),【1】B.Babcocketal.ModelsandIssuesinDataStreamSystems,ACMPODSConference,2002.【2】BarbarD.Requirementsforclusteringdatastreams.ACMSIGKDDExplorationsNewsletter,2003，3(2):23-27.【3】LiadanOCallaghanetal.Stream-DataAlgorithmsForHigh-QualityClustering,Proceedingsofthe18thInternationalConferenceonDataEngineering(ICDE02),2002.【4】C.C.Aggarwal,J.Han,J.Wang,P.Yu.AFrameworkforClusteringEvolvingDataStreams.VLDBConference,2003.【5】SunHL,YuG,BanYB,ZhaoFX,WangDL.CDS-Tree:Aneffectiveindexforclusteringarbitraryshapesindatastreams.In:Proc.ofthe15thIntlWorkshoponResearchIssuesinDataEngineering:StreamDataMiningandApplications(RIDESDMA2005).Washington:IEEEComputerSociety,2005.81-88.(孫煥良，趙法信，鮑玉斌等.CD_Stream種基于空間劃分的流數(shù)據(jù)密度聚類算法.計(jì)算機(jī)研究與發(fā)展，2004,10.)【6】C.C.Aggarwal,HanJ,WangJ,eta1.AFrameworkforProjectedClusteringofHighDimensionalDataStreamsc.Procofthe30thVLDBConference，2004：852-863.【7】ZhuWei-Heng,YinJian,XieYi-Huang.Arbitraryshapeclusteralgorithmforclusteringdatastream.JournalofSoftware,2006,17(3):379-387.(朱蔚恒,印鑒,謝益煌.基于數(shù)據(jù)流的任意形狀聚類算法.軟件學(xué)報(bào),2006,17(3):379-387.)【8】CaoFeng,EsteryM,QianWeining,eta1.Density-basedClusteringoveranEvolvingDataStreamwithNoiseC.Proc.ofthe2006SIAMConferenceonDataMining.Bethesda,USA:s.n.,2006.【9】ChenYixin,LiTu.Density-basedClusteringforReal-timeStreamDataC.Proc.ofthe2007KDDConferenceonDataMining.LasVegas,USA:s.n.,2007.【10】