數據流聚類算法介紹

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

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

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

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

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

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

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

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