title: Density-Based Clustering over an Evolving Data Stream with Noise pdf

code: None

abstract

流式數(shù)據(jù)挖掘有兩個(gè)重要的限制：有限內(nèi)存空間，一次性讀取，并且有如下的需求：

• 無(wú)法預(yù)知類別的數(shù)量
• 能發(fā)現(xiàn)任意形狀的類簇
• 能處理outliers(噪聲點(diǎn))

本文提出的方法能夠滿足上述的需求泄私，DenStream

introduction

• core-micro-cluster: 總結(jié)數(shù)據(jù)流中的任意形狀的類簇
• novel pruning strategy: 一個(gè)新的剪枝策略
• outlier-buffer: 用來(lái)分開(kāi)core-micro-cluster 和 outlier-micro-clusters 兩種處理過(guò)程瓦戚，提高了算法效率
• 高準(zhǔn)確率

基本概念

時(shí)間窗口：界標(biāo)窗口（landmark window）蓖柔，滑動(dòng)窗口(slide window)，衰減（阻尼）(damped window )窗口
本文采用衰減窗口來(lái)對(duì)不同時(shí)間的樣本進(jìn)行加權(quán)：

越大，表示對(duì)歷史的數(shù)據(jù)的權(quán)重越低

傳統(tǒng)的密度聚類，例如DBSCAN算法畔乙，將所有的數(shù)據(jù)全部放入內(nèi)存中，然后進(jìn)行計(jì)算翩概，將計(jì)算的結(jié)果返回出來(lái)牲距，但是這種方法不切實(shí)際。

本文提出钥庇，對(duì)于歷史久遠(yuǎn)的樣本數(shù)據(jù)牍鞠，在計(jì)算類中心的時(shí)候，采用衰減函數(shù)進(jìn)行加權(quán)评姨。 用于調(diào)節(jié)衰減速度

core-micro-cluster

密度聚類中的核心點(diǎn)組成的小類难述，例如DBSCAN的initial階段生成的小類。

core-micro-cluster 定義為 c-micro-cluster, CMC(w,c,r) 定義為一個(gè)core-micro-cluster, 其中w為權(quán)重：

其中點(diǎn)集p_{i_1}, p_{i_2}, ... ,p_{i_n} 對(duì)應(yīng)的時(shí)間為: T_{i_1}, T_{i_2}, ..., T_{i_n}

c為該類的中心點(diǎn)：

r為平均半徑：

在計(jì)算類簇的中心點(diǎn)的時(shí)候吐句，使用到了衰減函數(shù)胁后，因此這里的dist函數(shù)表示歐幾里得距離

potential c-micro-cluster

這一部分借鑒了BIRCH的聚類思想，因?yàn)樾枰粩嗟膗pdate這一部分嗦枢，因此采用了特征聚類樹(shù)的概念攀芯。

這里需要計(jì)算特征樹(shù)的幾個(gè)參數(shù)：，文虏，

為權(quán)重參數(shù)：

,加權(quán)樣本線性和：

,加權(quán)樣本平方和：

類簇中心c:

類簇平均半徑r：

outlier micro-cluster

該部分和上部分差不多侣诺，不過(guò)是密度不可達(dá)的點(diǎn), 滿足的條件如下：

p-micro-cluster 和 o-micro-cluster 這兩類的聚類方法采用的BIRCH的思想，因此是能夠支持增量聚類氧秘。因?yàn)樘卣鳂?shù)的兩個(gè)參數(shù)本身就支持線性變換年鸳。

clustering algorithm

online-stage

在線階段，保持p-micro-clusters 和 o-micro-clusters在內(nèi)存中丸相，因?yàn)榇蟛糠中聛?lái)的點(diǎn)都可以被吸收到這兩種類別當(dāng)中搔确，online階段就負(fù)責(zé)在內(nèi)存中維護(hù)好這兩個(gè)類別的點(diǎn)

當(dāng)一個(gè)新的點(diǎn)來(lái)臨時(shí)，通過(guò)計(jì)算點(diǎn)和最近的p-micro-cluster的距離灭忠，如果距離小于等于, 則合并該點(diǎn)到這個(gè)p-micro-cluster中膳算，否則嘗試將該點(diǎn)合并到o-micro-cluster 中。詳見(jiàn)paper 4.1 section

image.png

隨著時(shí)間的推移更舞，已經(jīng)存在的p-micro-cluster 的權(quán)重不斷的遞減畦幢，如果權(quán)值低于，表明該micro-cluster要變成o-micro-cluster 了缆蝉，因此需要一個(gè)周期性的檢查宇葱，將這些“老化的” p-micro-cluster 逐漸變成 o-micro-cluster

最小時(shí)間（p-micro-cluster 老化成 o-micro-cluster）：

image.png

上述等式成立基于這個(gè)等式：

這樣一來(lái)瘦真， o-micro-cluster的數(shù)量就會(huì)不斷的增加，但是實(shí)際上有的o-micro-cluster 是有可能變成p-micro-cluster的黍瞧，理論上任何一個(gè)'o'點(diǎn)都有可能變成'p'點(diǎn)诸尽，但是內(nèi)存有限，不可能無(wú)限期等待印颤，因此我們?cè)诿總€(gè)檢查周期您机，判斷每個(gè)o-micro-cluster的權(quán)值和的大小，如果權(quán)值小于年局，意味著該類在當(dāng)前看來(lái)不會(huì)變成p類际看，可以從內(nèi)存中刪除該點(diǎn)。
的定義如下：

image.png

周期性的檢查的算法：

image.png

offline-stage

在線階段負(fù)責(zé)維護(hù)micro-clusters矢否，如果要計(jì)算最終的clusters仲闽，需要使用到p-micro-clusters計(jì)算過(guò)程中得到的c和w參數(shù)（虛擬中心點(diǎn)和權(quán)重）

定理：當(dāng)兩個(gè)p-micro-cluster的center點(diǎn)的距離小于的時(shí)候，兩個(gè)類就可以合并為一個(gè)新的類僵朗，迭代方法和傳統(tǒng)的DBSCAN一樣赖欣。