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

背景隨著計算機軟硬件的不斷升級，人們獲取數(shù)據能力越來越高。在電信、金融、天氣預報、網絡入侵檢測、傳感器網絡等領域出現(xiàn)了一種不同于傳統(tǒng)靜態(tài)數(shù)據的流數(shù)據。這種數(shù)據流有自己的特點。第一頁，共27頁。數(shù)據流特點1、數(shù)據實時達到2、數(shù)據到達次序獨立，不受系統(tǒng)控制3、數(shù)據量是巨大的，不能預知其大小4、單次掃描，數(shù)據一經處理，除非特意保存，否則不能再次被處理第二頁，共27頁。數(shù)據流聚類聚類是數(shù)據挖掘中一類重要的問題，在許多領域有其應用之處。聚類定義：給定一個有許多數(shù)據元素組成的集合，我們將其分為不同的組（類、簇），使得組內的元素盡可能的相似，不同組之間的元素盡可能的不同。由于數(shù)據流的特點，對它的聚類算法提出了新的要求。第三頁，共27頁。數(shù)據流聚類算法要求1、壓縮的表達（概要數(shù)據）2、迅速、增量地處理新到達的數(shù)據3、快速、清晰地識別離群點第四頁，共27頁。CluStream概要C.C.Aggarwal等人在2003年提出了該著名的經典數(shù)據流聚類框架。它引入了簇和時間幀結構兩個主要的概念，將數(shù)據流聚類過程分為在線部分（微聚類）和離線部分（宏聚類）。在線部分實時處理新到達的數(shù)據，并周期性的存儲統(tǒng)計結果；離線部分就利用這些統(tǒng)計結果結合用戶輸入得到聚類結果。第五頁，共27頁。CluStream的影響CluStream兩階段框架是一個著名的框架，后續(xù)有許多算法在其基礎上進行各方面的改進。它的在線部分可以實時處理較快速度的流數(shù)據，并得到統(tǒng)計結果。離線部分結合用戶輸入的參數(shù)可以近似得到過去某些時候的聚類結果。第六頁，共27頁。CLuStream算法的核心概念微簇（Micro-clusters）時間衰減結構（PyramidalTimeFrame）第七頁，共27頁。數(shù)據流一種形式化描述第八頁，共27頁。數(shù)據流計算模型界標模型滑動窗口模型衰減模型第九頁，共27頁。微簇（Micro-clusters）CluStream以微簇的形式維護關于數(shù)據位置的統(tǒng)計信息。這些微簇被定義成簇特征向量在時間上的擴展。這些微簇額外增加的時間屬性很自然將其應用于解決數(shù)據流問題。在上述數(shù)據流定義下，微簇是一個2d+3（d是數(shù)據維度）的元組第十頁，共27頁。時間幀結構（PyramidalTimeFrame）上述微簇需要在某些時刻維護和存儲到磁盤以供離線階段查詢。由于數(shù)據量巨大，不可能將所有時刻的微簇信息都存儲到磁盤（這部分信息叫做快照），因此引入時間幀結構。它將時間軸劃分成不同粒度的時刻，結果是離現(xiàn)在的越近粒度越細，反之越粗。第十一頁，共27頁。T=55的時間軸劃分第十二頁，共27頁。這種時間幀結構的一些好處。 1.能滿足用戶對最近數(shù)據感興趣的需求； 2.運行100年的數(shù)據流僅僅需要存儲大概95個快照，這能滿足有限內存的需求。第十三頁，共27頁。在線部分（微簇維護）初始化簇

首先在磁盤上存儲最初始的initNumber個數(shù)據點，然后采用標準的k-means算法形成q個微簇：M1、M2…Mq。在線處理

對于以后達到的每一個數(shù)據點Xik，要么被上述的某個微簇吸收，要么放進它自己的簇中。首先計算Xik與q個微簇中的每一個的距離（實際上是其中心）。將其放到離它最近的那個簇Mp中。

第十四頁，共27頁。特殊情況

1.Xik雖然離Mp最近，但是Xik卻在Mp的邊界外； 2.由于數(shù)據流的演化，Xik可能是一個新簇的開端。處理方法

為落在邊界外的數(shù)據點創(chuàng)建一個帶獨有標志id的新簇，這需要減少一個其他已經存在的簇。這可以通過刪除一個最早的簇或者合并兩個最早的簇來實現(xiàn)。第十五頁，共27頁。如何安全刪除？ 估計每一個簇中最后m個達到的數(shù)據點的平均時間戳，然后刪除帶有最小時間戳的值（時間越早值越小且小于用戶定義的閾值）的那個簇。這種方法只增加了存儲每個簇中最后m個點的數(shù)據的信息（時間戳）。第十六頁，共27頁。何時合并？ 有些情況下，不能合并任何兩個微簇。這種情況是發(fā)生在當所有上述計算的時間值都大于那個閾值，此時需要合并某兩個靠的最近的微簇。此時用它們原來的id一起標志這個新的微簇。 同時，需要存儲金字塔時間結構對應時刻的微簇（實際上指的是微簇的特征向量值）到磁盤。第十七頁，共27頁。離線部分（宏簇創(chuàng)建）用戶在該部分可以在不同時間幅度內發(fā)現(xiàn)簇。這部分所用的數(shù)據是在線部分形成的統(tǒng)計信息，這可以滿足內存有限的需求。用戶提供兩個參數(shù)h和k，h是時間幅度，k是預定義的需要形成的簇的數(shù)目。第十八頁，共27頁。k-means算法基本步驟1

.從n個數(shù)據對象任意選擇k個對象作為初始聚類中心；2

.根據每個聚類對象的均值（中心對象），計算每個對象與這些中心對象的距離；并根據最小距離重新對相應對象進行劃分；3.重新計算每個（有變化）聚類的均值（中心對象）；4.計算標準測度函數(shù)，當滿足一定條件，如函數(shù)收斂時，則算法終止；如果條件不滿足則回到步驟2。第十九頁，共27頁。離線部分算法該部分采用改進的k-means算法（1）初始階段 不在隨機的選取種子，而是選擇可能被劃分到給定簇的種子，這些種子其實是對應微簇的中心。（2）劃分階段 一個種子到一個“偽數(shù)據點”（也就是微簇）的距離就等于它到“偽數(shù)據點”中心的距離。（3）調整階段 一個給定劃分的新種子被定義成那個劃分中帶權重的微簇中心。第二十頁，共27頁。簇演化分析CluStream可以進行演化分析演化分析就是分析數(shù)據流在過去一段時間內潛在的一些變化。比如在入侵檢測系統(tǒng)檢測到在某一時間段收到某種類型的攻擊。第二十一頁，共27頁。實驗評估一、數(shù)據集合選擇二、評估手段第二十二頁，共27頁。數(shù)據集人工數(shù)據集和真實數(shù)據集。由人工數(shù)據集相關屬性容易被控制，用它來評估算法在不同緯度和不同聚類數(shù)目上的性能。用真實數(shù)據集來評估算法的有效性以及在評估其是否能發(fā)現(xiàn)數(shù)據流潛在的演化特性。第二十三頁，共27頁。評估手段SSQ:評估聚類質量運行時間：評估算法效率靈敏度：對參數(shù)的敏感程度第二十四頁，共27頁。CluStream算法優(yōu)缺點優(yōu)點： 提出了兩階段聚類框架，算法能適應數(shù)據流快速、有序無限、單遍掃描的特點。能夠發(fā)掘數(shù)據流潛在的演化特性。缺點： 1、不能發(fā)現(xiàn)任意形狀的簇； 2、不能很好地識別離群點； 3、對高維數(shù)據聚類質量下降；第二十五頁，共27頁。后續(xù)研究基于兩層次的數(shù)據路聚類解決高維問題的數(shù)據流聚類（HPStream）基于滑動窗口的數(shù)據流聚類（Clu-Win）基于密度的數(shù)據流聚類（ACluStream、DenStream及改進）基于網格的數(shù)據流聚類（D-Stream及改進）采用樹索引的網格數(shù)據流聚類（CD-Stream、TDCA）基于分形維度的數(shù)據路聚類（FCluStream）第二十六頁，共27頁。參考文獻【1】B.Babcocketal.ModelsandIssuesinDataStreamSystems,ACMPODSConference,2002.【2】BarbaráD.Requirementsforclusteringdatastreams.ACMSIGKDDExplorationsNewsletter,2003，3(2):23-27.【3】LiadanO'Callaghanetal.Stream-DataAlgorithmsForHigh-QualityClustering,Proceedingsofthe18thInternationalConferenceonDataEngineering(ICDE'02),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.ofthe15thInt'lWorkshoponResearchIssuesinDataEngineering:StreamDataMiningandApplications(RIDE—SDMA2005).Washington:IEEEComputerSociety,2005.81-88.(孫煥良，趙法信，鮑玉斌等.CD_Stream——種基于空間劃分的流數(shù)據密度聚類算法.計算機研究與發(fā)展，2004,10.)【6】C.C.Aggarwal,HanJ,WangJ,eta1.AFrameworkforProjectedClusteringofHighDimensionalDataStreams[c].Procofthe30thVLDBConference，2004：852-863.【7】ZhuWei-Heng,YinJian,XieYi-Huang.Arbitraryshapeclusteralgorithmforclusteringdatastream.JournalofSoftware,2006,17(3):379-387.(朱蔚恒,印鑒,謝益煌.基于數(shù)據流的任意形狀聚類算法.軟件學報,2006,17(3):379-387.)【8】CaoFeng,EsteryM,QianWeining,eta1.Density-basedClusteringoveranEvolvingDataStreamwithNoise[C].Proc.ofthe2006SIAMConferenceonDataMining.Bethesda,USA:[s.n.],2006.【9】ChenYixin,LiTu.Density-basedClusteringforReal-timeStreamData[C].Proc.ofthe2007KDDConferenceonDataMining.LasVegas,USA:[s.n.],2007.【10】BarbaráD,ChenP.U