Den-Stream

2019-01-22 本文已影响0人 xiongraorao

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

code: None

abstract

流式数据挖掘有两个重要的限制：有限内存空间，一次性读取，并且有如下的需求：

无法预知类别的数量
能发现任意形状的类簇
能处理outliers(噪声点)

本文提出的方法能够满足上述的需求，DenStream

introduction

core-micro-cluster: 总结数据流中的任意形状的类簇
novel pruning strategy: 一个新的剪枝策略
outlier-buffer: 用来分开core-micro-cluster 和 outlier-micro-clusters 两种处理过程，提高了算法效率
高准确率

基本概念

时间窗口：界标窗口（landmark window），滑动窗口(slide window)，衰减（阻尼）(damped window )窗口
本文采用衰减窗口来对不同时间的样本进行加权：

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

$\lambda$ 越大，表示对历史的数据的权重越低

传统的密度聚类，例如DBSCAN算法，将所有的数据全部放入内存中，然后进行计算，将计算的结果返回出来，但是这种方法不切实际。

本文提出，对于历史久远的样本数据，在计算类中心的时候，采用衰减函数进行加权。 $\lambda$ 用于调节衰减速度

core-micro-cluster

密度聚类中的核心点组成的小类，例如DBSCAN的initial阶段生成的小类。

core-micro-cluster 定义为 c-micro-cluster, CMC(w,c,r) 定义为一个core-micro-cluster, 其中w为权重：
$w = \sum_{j=1}^n f(t-T_{i_j}),w \ge \mu$

其中点集p_{i_1}, p_{i_2}, ... ,p_{i_n} 对应的时间为: T_{i_1}, T_{i_2}, ..., T_{i_n}

c为该类的中心点：

$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}$

在计算类簇的中心点的时候，使用到了衰减函数，因此这里的dist函数表示欧几里得距离

potential c-micro-cluster

这一部分借鉴了BIRCH的聚类思想，因为需要不断的update这一部分，因此采用了特征聚类树的概念。

这里需要计算特征树的几个参数： $\overline {CF^1}$ ， $\overline {CF^2}$ ， $w$

$w$ 为权重参数：

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

$\overline {CF^1}$ ,加权样本线性和：

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

$\overline {CF^2}$ ,加权样本平方和：

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

类簇中心c:

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

类簇平均半径r：

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

outlier micro-cluster

该部分和上部分差不多，不过是密度不可达的点, 满足的条件如下：

$w < \beta \mu$

p-micro-cluster 和 o-micro-cluster 这两类的聚类方法采用的BIRCH的思想，因此是能够支持增量聚类。因为特征树的两个参数本身就支持线性变换。

clustering algorithm

online-stage

在线阶段，保持p-micro-clusters 和 o-micro-clusters在内存中，因为大部分新来的点都可以被吸收到这两种类别当中，online阶段就负责在内存中维护好这两个类别的点

当一个新的点来临时，通过计算点和最近的p-micro-cluster的距离，如果距离小于等于 $\epsilon$ , 则合并该点到这个p-micro-cluster中，否则尝试将该点合并到o-micro-cluster 中。详见paper 4.1 section

image.png

随着时间的推移，已经存在的p-micro-cluster 的权重不断的递减，如果权值低于 $\beta \mu$ ，表明该micro-cluster要变成o-micro-cluster 了，因此需要一个周期性的检查，将这些“老化的” p-micro-cluster 逐渐变成 o-micro-cluster

最小时间（p-micro-cluster 老化成 o-micro-cluster）：

image.png

上述等式成立基于这个等式： $2^{-\lambda T_p} \beta \mu + 1$

这样一来， o-micro-cluster的数量就会不断的增加，但是实际上有的o-micro-cluster 是有可能变成p-micro-cluster的，理论上任何一个'o'点都有可能变成'p'点，但是内存有限，不可能无限期等待，因此我们在每个检查周期，判断每个o-micro-cluster的权值和 $\xi$ 的大小，如果权值小于 $\xi$ ，意味着该类在当前看来不会变成p类，可以从内存中删除该点。
$\xi$ 的定义如下：