資源描述：
《數(shù)據(jù)流聚類算法clustream介紹》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、經(jīng)典數(shù)據(jù)流聚類算法CluStream概要報告人：高賀慶時間：2012-9-23背景隨著計算機軟硬件的不斷升級，人們獲取數(shù)據(jù)能力越來越高。在電信、金融、天氣預(yù)報、網(wǎng)絡(luò)入侵檢測、傳感器網(wǎng)絡(luò)等領(lǐng)域出現(xiàn)了一種不同于傳統(tǒng)靜態(tài)數(shù)據(jù)的流數(shù)據(jù)。這種數(shù)據(jù)流有自己的特點。數(shù)據(jù)流特點1、數(shù)據(jù)實時達(dá)到2、數(shù)據(jù)到達(dá)次序獨立，不受系統(tǒng)控制3、數(shù)據(jù)量是巨大的，不能預(yù)知其大小4、單次掃描，數(shù)據(jù)一經(jīng)處理，除非特意保存，否則不能再次被處理數(shù)據(jù)流聚類聚類是數(shù)據(jù)挖掘中一類重要的問題，在許多領(lǐng)域有其應(yīng)用之處。聚類定義：給定一個有許多數(shù)據(jù)元素組成的集合，我們將其分為不同的組（類、簇）
2、，使得組內(nèi)的元素盡可能的相似，不同組之間的元素盡可能的不同。由于數(shù)據(jù)流的特點，對它的聚類算法提出了新的要求。數(shù)據(jù)流聚類算法要求1、壓縮的表達(dá)（概要數(shù)據(jù)）2、迅速、增量地處理新到達(dá)的數(shù)據(jù)3、快速、清晰地識別離群點CluStream概要C.C.Aggarwal等人在2003年提出了該著名的經(jīng)典數(shù)據(jù)流聚類框架。它引入了簇和時間幀結(jié)構(gòu)兩個主要的概念，將數(shù)據(jù)流聚類過程分為在線部分（微聚類）和離線部分（宏聚類）。在線部分實時處理新到達(dá)的數(shù)據(jù)，并周期性的存儲統(tǒng)計結(jié)果；離線部分就利用這些統(tǒng)計結(jié)果結(jié)合用戶輸入得到聚類結(jié)果。CluStream的影響CluStr
3、eam兩階段框架是一個著名的框架，后續(xù)有許多算法在其基礎(chǔ)上進(jìn)行各方面的改進(jìn)。它的在線部分可以實時處理較快速度的流數(shù)據(jù)，并得到統(tǒng)計結(jié)果。離線部分結(jié)合用戶輸入的參數(shù)可以近似得到過去某些時候的聚類結(jié)果。CLuStream算法的核心概念微簇（Micro-clusters）時間衰減結(jié)構(gòu)（PyramidalTimeFrame）數(shù)據(jù)流一種形式化描述數(shù)據(jù)流計算模型界標(biāo)模型滑動窗口模型衰減模型微簇（Micro-clusters）CluStream以微簇的形式維護(hù)關(guān)于數(shù)據(jù)位置的統(tǒng)計信息。這些微簇被定義成簇特征向量在時間上的擴展。這些微簇額外增加的時間屬性很自然
4、將其應(yīng)用于解決數(shù)據(jù)流問題。在上述數(shù)據(jù)流定義下，微簇是一個2d+3（d是數(shù)據(jù)維度）的元組時間幀結(jié)構(gòu)（PyramidalTimeFrame）上述微簇需要在某些時刻維護(hù)和存儲到磁盤以供離線階段查詢。由于數(shù)據(jù)量巨大，不可能將所有時刻的微簇信息都存儲到磁盤（這部分信息叫做快照），因此引入時間幀結(jié)構(gòu)。它將時間軸劃分成不同粒度的時刻，結(jié)果是離現(xiàn)在的越近粒度越細(xì)，反之越粗。T=55的時間軸劃分這種時間幀結(jié)構(gòu)的一些好處。1.能滿足用戶對最近數(shù)據(jù)感興趣的需求；2.運行100年的數(shù)據(jù)流僅僅需要存儲大概95個快照，這能滿足有限內(nèi)存的需求。在線部分（微簇維護(hù)）初始化
5、簇首先在磁盤上存儲最初始的initNumber個數(shù)據(jù)點，然后采用標(biāo)準(zhǔn)的k-means算法形成q個微簇：M1、M2…Mq。在線處理對于以后達(dá)到的每一個數(shù)據(jù)點Xik，要么被上述的某個微簇吸收，要么放進(jìn)它自己的簇中。首先計算Xik與q個微簇中的每一個的距離（實際上是其中心）。將其放到離它最近的那個簇Mp中。特殊情況1.Xik雖然離Mp最近，但是Xik卻在Mp的邊界外；2.由于數(shù)據(jù)流的演化，Xik可能是一個新簇的開端。處理方法為落在邊界外的數(shù)據(jù)點創(chuàng)建一個帶獨有標(biāo)志id的新簇，這需要減少一個其他已經(jīng)存在的簇。這可以通過刪除一個最早的簇或者合并兩個最早
6、的簇來實現(xiàn)。如何安全刪除？估計每一個簇中最后m個達(dá)到的數(shù)據(jù)點的平均時間戳，然后刪除帶有最小時間戳的值（時間越早值越小且小于用戶定義的閾值）的那個簇。這種方法只增加了存儲每個簇中最后m個點的數(shù)據(jù)的信息（時間戳）。何時合并？有些情況下，不能合并任何兩個微簇。這種情況是發(fā)生在當(dāng)所有上述計算的時間值都大于那個閾值，此時需要合并某兩個靠的最近的微簇。此時用它們原來的id一起標(biāo)志這個新的微簇。同時，需要存儲金字塔時間結(jié)構(gòu)對應(yīng)時刻的微簇（實際上指的是微簇的特征向量值）到磁盤。離線部分（宏簇創(chuàng)建）用戶在該部分可以在不同時間幅度內(nèi)發(fā)現(xiàn)簇。這部分所用的數(shù)據(jù)是在
7、線部分形成的統(tǒng)計信息，這可以滿足內(nèi)存有限的需求。用戶提供兩個參數(shù)h和k，h是時間幅度，k是預(yù)定義的需要形成的簇的數(shù)目。k-means算法基本步驟1.從n個數(shù)據(jù)對象任意選擇k個對象作為初始聚類中心；2.根據(jù)每個聚類對象的均值（中心對象），計算每個對象與這些中心對象的距離；并根據(jù)最小距離重新對相應(yīng)對象進(jìn)行劃分；3.重新計算每個（有變化）聚類的均值（中心對象）；4.計算標(biāo)準(zhǔn)測度函數(shù)，當(dāng)滿足一定條件，如函數(shù)收斂時，則算法終止；如果條件不滿足則回到步驟2。離線部分算法該部分采用改進(jìn)的k-means算法（1）初始階段不在隨機的選取種子，而是選擇可能被劃
8、分到給定簇的種子，這些種子其實是對應(yīng)微簇的中心。（2）劃分階段一個種子到一個“偽數(shù)據(jù)點”（也就是微簇）的距離就等于它到“偽數(shù)據(jù)點”中心的距離。（3）調(diào)整階段一個給定劃分的新種子被
