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

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

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

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

第15頁，課件共27頁，創(chuàng)作于2023年2月特殊情況

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

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

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

.根據(jù)每個聚類對象的均值（中心對象），計算每個對象與這些中心對象的距離；并根據(jù)最小距離重新對相應(yīng)對象進行劃分；3.重新計算每個（有變化）聚類的均值（中心對象）；4.計算標(biāo)準(zhǔn)測度函數(shù)，當(dāng)滿足一定條件，如函數(shù)收斂時，則算法終止；如果條件不滿足則回到步驟2。第20頁，課件共27頁，創(chuàng)作于2023年2月離線部分算法該部分采用改進的k-means算法（1）初始階段 不在隨機的選取種子，而是選擇可能被劃分到給定簇的種子，這些種子其實是對應(yīng)微簇的中心。（2）劃分階段 一個種子到一個“偽數(shù)據(jù)點”（也就是微簇）的距離就等于它到“偽數(shù)據(jù)點”中心的距離。（3）調(diào)整階段 一個給定劃分的新種子被定義成那個劃分中帶權(quán)重的微簇中心。第21頁，課件共27頁，創(chuàng)作于2023年2月簇演化分析CluStream可以進行演化分析演化分析就是分析數(shù)據(jù)流在過去一段時間內(nèi)潛在的一些變化。比如在入侵檢測系統(tǒng)檢測到在某一時間段收到某種類型的攻擊。第22頁，課件共27頁，創(chuàng)作于2023年2月實驗評估一、數(shù)據(jù)集合選擇二、評估手段第23頁，課件共27頁，創(chuàng)作于2023年2月數(shù)據(jù)集人工數(shù)據(jù)集和真實數(shù)據(jù)集。由人工數(shù)據(jù)集相關(guān)屬性容易被控制，用它來評估算法在不同緯度和不同聚類數(shù)目上的性能。用真實數(shù)據(jù)集來評估算法的有效性以及在評估其是否能發(fā)現(xiàn)數(shù)據(jù)流潛在的演化特性。第24頁，課件共27頁，創(chuàng)作于2023年2月評估手段SSQ:評估聚類質(zhì)量運行時間：評估算法效率靈敏度：對參數(shù)的敏感程度第25頁，課件共27頁，創(chuàng)作于2023年2月CluStream算法優(yōu)缺點優(yōu)點： 提出了兩階段聚類框架，算法能適應(yīng)數(shù)據(jù)流快速、有序無限、單遍掃描的特點。能夠發(fā)掘數(shù)據(jù)流潛在的演化特性。缺點： 1、不能發(fā)現(xiàn)任意形狀的簇； 2、不能很好地識別離群點； 3、對高維數(shù)據(jù)聚類質(zhì)量下降；第26頁，課件共27頁，創(chuàng)作于2023年2月后續(xù)研究基于兩層次的數(shù)據(jù)路聚類解決高維問題的數(shù)據(jù)流聚類（HPStrea