密度聚类（参考西瓜书）

定义：

密度聚类假设聚类结构通过样本分布的紧密程度。此算法是基于密度的角度来考察样本之间的连接性，并基于连接性不断扩展聚类簇最后获得最终的结果。他通过判断样本在区域空间内是否大于某个阈值来决定是否将其放到与之相近的样本中。

密度聚类从样本的角度来考虑样本简的连接性，由可连接性不断扩展得到结果，它可以解决k-means和birch等算法只适用于凸样本的情况。

特点：

（1）发现任意蔟

（2）对噪声数据不敏感

（3）一次扫描

（4）计算量大，复杂度高

常用算法：DBSCAN,MDCA,OPTICS等

DBSCAN算法：

DBSCAN是一种著名的密度聚类算法,它基于一组“邻域”(neigh-borhood)参数(e,MinPts)来刻画样本分布的紧密程度.给定数据集D= {21,x2,..,.n},定义下面这几个概念:

1. e-邻域:对xj∈D,其∈邻域包含样本集D中与xj的距离不大于e的样本,即N(xj)= {xi∈D | dist(xi,xj)≤e};
2. 核心对象(core object): 若xj的E-邻域至少包含MinPts个样本，即|Ne(xj)|≥MinPts,则xj是-一个核心对象;
3. 密度直达(directly density- reachable):若xj位于xi的e-邻域中,且xi是核心对象,则称x;由xi密度直达;
4. 密度可达(density. reachable): 对xi与xj,若存在样本序列P1,P2,... ,Pn,其中p1=xi,Pn=xj且pi+1由pi密度直达,则称xj由xi密度可达;
5. 密度相连(density-conected): 对xi与xj,若存在xk使得xi与xj均由xk密度可达,则称xi与xj密度相连.

DBSCAN 定义的基本概念(MinPts= 3): 虚线显示出∈-邻域, x1是核心对 象,x2由x1密度直达,x3由x1密度可达, x3与x4密度相连.

蔟C属于D满足两个性质：

1. 连接性(connectivity): xi∈C,xj∈C→xi与xj密度相连
2. 最大性(maximality): xi∈C, xj由xi密度可达> xj∈C

若x为核心对象，由x密度可达的所有对象组成的集合X={x'∈D|x'由x密度可达}，则X即为满足连接性和最大性的蔟。

1. 优点：
2. 不需要设置k值
3. 可以发现任意形状的蔟
4. 可以聚类的同时发现噪音点，即对噪音不敏感
5. 对样本输入顺序不敢兴趣

缺点：

1. 高维数据效果不理想
2. 调参复杂，eps和Minpiont参数不好设置，无法预估。