Den-Stream

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

code: None

abstract

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

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

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

introduction

  • core-micro-cluster: 總結(jié)數(shù)據(jù)流中的任意形狀的類(lèi)簇
  • 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)：

f(t) = 2^{- \lambda t}, \lambda > 0

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

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

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

core-micro-cluster

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

core-micro-cluster 定義為 c-micro-cluster, CMC(w,c,r) 定義為一個(gè)core-micro-cluster, 其中w為權(quán)重：
w = \sum_{j=1}^n f(t-T_{i_j}),w \ge \mu

其中點(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為該類(lèi)的中心點(diǎn)：

c = \frac {\sum_{j=1}^n f(t-T_{i_j})p_{i_j}}{w}

r為平均半徑：

r = \frac {\sum_{j=1}^n f(t-T_{i_j})dist(p_{i_j}, c)}{w}

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

potential c-micro-cluster

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

這里需要計(jì)算特征樹(shù)的幾個(gè)參數(shù)：\overline {CF^1}，\overline {CF^2}，w

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

w = \sum_{j=1}^n f(t-T_{i_j}),w \ge \beta\mu

\overline {CF^1},加權(quán)樣本線性和：

\overline {CF^1} = \sum_{j=1}^n f(t-T_{i_j})p_{i_j}

\overline {CF^2},加權(quán)樣本平方和：

\overline {CF^2} = \sum_{j=1}^n f(t-T_{i_j})p_{i_j}^2

類(lèi)簇中心c:

c = \frac {\overline {CF^1}} {w}

類(lèi)簇平均半徑r：

r = \sqrt { \frac {\overline {CF^2}} {w} - (\frac {\overline {CF^1}} {w})^2}, st. r \le \epsilon

outlier micro-cluster

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

w < \beta \mu

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

clustering algorithm

online-stage

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

當(dāng)一個(gè)新的點(diǎn)來(lái)臨時(shí)，通過(guò)計(jì)算點(diǎn)和最近的p-micro-cluster的距離，如果距離小于等于\epsilon, 則合并該點(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)值低于\beta \mu，表明該micro-cluster要變成o-micro-cluster 了，因此需要一個(gè)周期性的檢查，將這些“老化的” p-micro-cluster 逐漸變成 o-micro-cluster

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

image.png

上述等式成立基于這個(gè)等式： 2^{-\lambda T_p} \beta \mu + 1

這樣一來(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)值和\xi的大小，如果權(quán)值小于\xi，意味著該類(lèi)在當(dāng)前看來(lái)不會(huì)變成p類(lèi)，可以從內(nèi)存中刪除該點(diǎn)。
\xi的定義如下：

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)的距離小于r_q+r_p的時(shí)候，兩個(gè)類(lèi)就可以合并為一個(gè)新的類(lèi)，迭代方法和傳統(tǒng)的DBSCAN一樣。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容