聚类

聚类试图将数据集中的样本划分为若干个通常是不相交的子集，每个子集称为一个“簇”（cluster），每个簇可能对应于一些潜在的概念（类别），需说明的是，这些概念对聚类算法而言事先是未知的，聚类过程仅能自动形成簇结构，簇所对应的概念语义需由使用者来把握和命名。

无监督学习

聚类是研究最多应用最广的无监督学习，在“无监督学习”（unsupervised learning）中，训练样本的标记信息是未知的，目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律，为进一步的数据分析提供基础。

无监督学习有：

聚类
密度估计
异常检测

无监督与监督的区别

监督学习（supervised learning）：通过已有的训练样本（即已知数据以及其对应的输出）进行算法模型重构。
无监督学习（unsupervised learning）：我们事先没有任何训练数据样本，需要直接对数据进行建模。用模型来揭示数据的内在性质及规律。

聚类模型的性能度量

聚类性能度量大致有两类：

“外部指标”（external index）：将聚类结果与某个“参考模型”（reference model）进行比较
“内部指标”（internal index）：直接考察聚类结果而不利用任何参考模型

聚类模型的分类

原型聚类

原型聚类假设聚类结构能通过一组原型刻画，在现实聚类任务中极为常用。其中“原型”是指样本空间中具有代表性的点。通常情形下，算法先对原型进行初始化，然后对原型进行迭代更新求解。常用的原型聚类有：

k-means
高斯混合模型

密度聚类

密度聚类算法假设聚类结构能通过样本分布的紧密程度确定。通常情形下，密度聚类算法从样本密度的角度来考察样本之间的可连接性，并基于可连接样本不断扩展聚类簇以获得最终的聚类结果。比如DBSCAN是一种著名的密度聚类算法。

层次聚类

层次聚类（hierarchical clustering）一般指通过从下往上不断合并簇，或者从上往下不断分离簇，从而形成树形的层次聚类结构。比如AGNES是一种采用自底向上聚合策略的层次聚类算法。

k-means

k-means就是把空间内点，分成K类。最大化簇间距离，最小化簇内距离。用均值来代表类中心，并用于衡量与新点的距离。

算法原理：

随机选取k个中心点；
在第j次迭代中，对于每个样本点，选取最近的中心点，归为该类；
更新中心点为每类的均值；
j=j+1 ,重复(2)(3)迭代更新，直至误差小到某个值或者到达一定的迭代步数，误差不变。

损失函数

损失函数为平方误差，损失函数刻画了簇内样本围绕簇均值向量的紧密程度，E值越小则簇内样本相似度越高。

中心点选取

随机选取
随机选取一个点，接下来选择距离该点最远的点做第二个初始类中心点，再选择距离前两个点最远的点做第三初始类中心点，以此类推
选用层次聚类或者Canopy算法进行初始聚类，然后利用这些类簇的中心点作为KMeans算法初始类簇中心点。

k值的确定

依据一个合适得类簇指标，如平均直径等，只要我们假设的类簇的数目等于或者高于真实的类簇的数目时，该指标上升会很缓慢，而一旦试图得到少于真实数目的类簇时，该指标会急剧上升。

优缺点：

优点：
1. 经典聚类算法，算法简单、快速
2. 处理大数据集的时候，该算法可以保证较好的伸缩性和高效率
3. 当簇近似高斯分布的时候，聚类效果不错
缺点:
1. K值是用户给定的，在进行数据处理前，K值是未知的，不同的K值得到的结果也不一样；
2. 对初始簇中心点是敏感的
3. 不适合发现非凸形状的簇或者大小差别较大的簇
4. 特殊值、离群值对模型的影响比较大

DBSCAN

DBSCAN(Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类方法)是一种典型的聚类算法，这类密度聚类算法一般假定类别可以通过样本分布的紧密程度决定。通常情形下，密度聚类算法从样本密度的角度来考察样本之间的可连接性，并基于可连接样本不断扩展聚类簇以获得最终的聚类结果。

密度的判定

DBSCAN是基于一组邻域来描述样本集的紧密程度的，参数($ϵ$, MinPts)用来描述邻域的样本分布紧密程度。其中，$ϵ$描述了某一样本的邻域距离阈值，MinPts描述了某一样本的距离为$ϵ$的邻域中样本个数的阈值。

$ϵ$-邻域：对于$x_j\in D$，其$ϵ$-邻域包含样本集D中与$x_j$的距离不大于$ϵ$的子样本集，即$N_{\epsilon}(x_j) = {x_i \in D | distance(x_i,x_j) \leq \epsilon}$, 这个子样本集的个数记为$|N_{\epsilon}(x_j)|$
核心对象：对于任一样本$x_j\in D$，如果其$ϵ$-邻域对应的$N_{\epsilon}(x_j)$至少包含MinPts个样本，即如果$|N_{\epsilon}(x_j)| \geq MinPts$，则$x_j$是核心对象。　
密度直达：如果$x_i$位于$x_j$的$ϵ$-邻域中，且$x_j$是核心对象，则称$x_i$由$x_j$密度直达。注意反之不一定成立，即此时不能说$x_j$由$x_i$密度直达, 除非且$x_i$也是核心对象。
密度可达：对于$x_i$和$x_j$,如果存在样本样本序列$p_1, p_2,…,p_T$，满足$p_1 = x_i, p_T = x_j$, 且$p_{t+1}$由$p_t$密度直达，则称$x_j$由$x_i$密度可达。也就是说，密度可达满足传递性。此时序列中的传递样本$p_1, p_2,…,p_{T-1}$均为核心对象，因为只有核心对象才能使其他样本密度直达。注意密度可达也不满足对称性，这个可以由密度直达的不对称性得出。
密度相连：对于$x_i$和$x_j$,如果存在核心对象样本$x_k$，使$x_i$和$x_j$均由$x_k$密度可达，则称$x_i$和$x_j$密度相连。注意密度相连关系是满足对称性的。

上面的语言太官方，下面开始说人话：

$ϵ$-邻域：对某个点，他的$ϵ$-邻域为一个区域内，该区域内任何点到该点的距离均小于$\epsilon$，如果选用欧式距离的话，某点的$ϵ$-邻域就是该点位圆心，$ϵ$位半径做园。
核心对象：如果某个样本点的$ϵ$-邻域内包含的样本点数大于某阈值MinPts，则该样本点可以称作核心对象。
密度直达：如果$x_i$位于$x_j$的$ϵ$-邻域中，且$x_j$是核心对象，则称$x_i$由$x_j$密度直达。注意反之不一定成立。
密度可达：将密度直达看作2格点的连通，如果对于$x_i$和$x_j$，存在某以连通路径，则$x_i$和$x_j$密度可达。
密度相连：对于$x_i$和$x_j$,如果存在核心对象样本$x_k$，使$x_i$和$x_j$均由$x_k$密度可达，则称$x_i$和$x_j$密度相连。注意密度相连关系是满足对称性的。

簇

基于这些概念，DBSCAN将簇定义为：由密度可达关系导出的最大的密度相连样本集合。D中不属于任何簇的样本被认为是噪声（noise）或异常（anomaly）样本。

算法步骤

算法步骤一般分为：

将所有点标记为核心点、边界点或噪声点；
删除噪声点；
为距离在Eps之内的所有核心点之间赋予一条边；
每组连通的核心点形成一个簇；
将每个边界点指派到一个与之关联的核心点的簇中（哪一个核心点的半径范围之内）。

算法总结

优点
1. 可以对任意形状的稠密数据集进行聚类，相对的，K-Means之类的聚类算法一般只适用于凸数据集。
2. 可以在聚类的同时发现异常点，对数据集中的异常点不敏感。
3. 聚类结果没有偏倚，相对的，K-Means之类的聚类算法初始值对聚类结果有很大影响。
缺点
1. 如果样本集的密度不均匀、聚类间距差相差很大时，聚类质量较差，这时用DBSCAN聚类一般不适合。
2. 如果样本集较大时，聚类收敛时间较长，此时可以对搜索最近邻时建立的KD树或者球树进行规模限制来改进。
3. 调参相对于传统的K-Means之类的聚类算法稍复杂，主要需要对距离阈值ϵ，邻域样本数阈值MinPts联合调参，

本小节参考资料

AGNES

AGNES是一种采用自底向上聚合策略的层次聚类算法。它先将数据集中的每个样本看作一个初始聚类簇，然后在算法运行的每一步中找出距离最近的两个聚类簇进行合并，该过程不断重复，直至达到预设的聚类簇个数。

距离

最小距离$d_{min}$：由两个簇的最近样本决定
最大距离$d_{max}$：由两个簇的最远样本决定
平均距离$d_{avg}$：由两个簇的所有样本共同决定