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 )窗口
本文采用衰减窗口来对不同时间的样本进行加权：
越大，表示对历史的数据的权重越低
传统的密度聚类，例如DBSCAN算法，将所有的数据全部放入内存中，然后进行计算，将计算的结果返回出来，但是这种方法不切实际。
本文提出，对于历史久远的样本数据，在计算类中心的时候，采用衰减函数进行加权。 用于调节衰减速度
core-micro-cluster
密度聚类中的核心点组成的小类，例如DBSCAN的initial阶段生成的小类。
core-micro-cluster 定义为 c-micro-cluster, CMC(w,c,r) 定义为一个core-micro-cluster, 其中w为权重：
其中点集p_{i_1}, p_{i_2}, ... ,p_{i_n} 对应的时间为: T_{i_1}, T_{i_2}, ..., T_{i_n}
c为该类的中心点：
r为平均半径：
在计算类簇的中心点的时候，使用到了衰减函数，因此这里的dist函数表示欧几里得距离
potential c-micro-cluster
这一部分借鉴了BIRCH的聚类思想，因为需要不断的update这一部分，因此采用了特征聚类树的概念。
这里需要计算特征树的几个参数：，
，
为权重参数：
,加权样本线性和：
,加权样本平方和：
类簇中心c:
类簇平均半径r：
outlier micro-cluster
该部分和上部分差不多，不过是密度不可达的点, 满足的条件如下：
p-micro-cluster 和 o-micro-cluster 这两类的聚类方法采用的BIRCH的思想，因此是能够支持增量聚类。因为特征树的两个参数本身就支持线性变换。
clustering algorithm
online-stage
在线阶段，保持p-micro-clusters 和 o-micro-clusters在内存中，因为大部分新来的点都可以被吸收到这两种类别当中，online阶段就负责在内存中维护好这两个类别的点
当一个新的点来临时，通过计算点和最近的p-micro-cluster的距离，如果距离小于等于, 则合并该点到这个p-micro-cluster中，否则尝试将该点合并到o-micro-cluster 中。详见paper 4.1 section
随着时间的推移，已经存在的p-micro-cluster 的权重不断的递减，如果权值低于，表明该micro-cluster要变成o-micro-cluster 了，因此需要一个周期性的检查，将这些“老化的” p-micro-cluster 逐渐变成 o-micro-cluster
最小时间（p-micro-cluster 老化成 o-micro-cluster）：
上述等式成立基于这个等式：
这样一来， o-micro-cluster的数量就会不断的增加，但是实际上有的o-micro-cluster 是有可能变成p-micro-cluster的，理论上任何一个'o'点都有可能变成'p'点，但是内存有限，不可能无限期等待，因此我们在每个检查周期，判断每个o-micro-cluster的权值和的大小，如果权值小于
，意味着该类在当前看来不会变成p类，可以从内存中删除该点。
的定义如下：
周期性的检查的算法：
offline-stage
在线阶段负责维护micro-clusters，如果要计算最终的clusters，需要使用到p-micro-clusters计算过程中得到的c和w参数（虚拟中心点和权重）
定理：当两个p-micro-cluster的center点的距离小于的时候，两个类就可以合并为一个新的类，迭代方法和传统的DBSCAN一样。
