聚类简介
- 直观上讲，聚类是将对象进行分组的一项任务，使相似的对象归为一类，不相似的对象归为不同类
- 聚类存在的难点：
（1）相似归为一类，不相似归为不同类这两个目标在很多情况下是互相冲突的，从数学上讲，虽然聚类共享具有等价关系甚至传递关系，但是相似性（或距离）不具有传递关系。具体而言，假定有一对象序列，X1，….，Xm，所有相邻元素（Xi-1、Xi+1）两两都非常相似，但是X1和Xm非常不相似。这种情况常常发生在cluster超过一定尺寸的时候，元素之间的传递性假设在这些场景下不一定100%符合真实规律
（2）另一个基本问题是聚类缺乏实际情况，这是无监督学习的共同问题。聚类是一种无监督学习，即我们不能预测label，因此对于聚类，我们没有明确的成功评估过程。另一方面，对于一个给定的对象集合，可以有多种有意义的划分方式，这可能是因为对象间的距离（或相似性）有多种隐式的定义，例如将演讲者的录音根据演讲者的口音聚类或根据内容聚类。所以，给定一个数据集，有多种不同的聚类解决方案
- 不存在一个聚类函数F同时满足三种属性：尺度不变性，丰富性，一致性
- 数据挖掘对聚类的典型泛化要求：
（1）可伸缩性：大数据集与小数据集结果的准确度保持一致
（2）处理不同类型数据的能力
（3）发现任意形状的类簇
（4）对聚类算法初始化参数的知识需求的最小化
（5）处理噪声的能力
（6）增量聚类和对输入次序的不敏感
（7）高维性
（8）基于约束的聚类
（9）可解释性和可用性
- 聚类的大致分类：
（1）基于距离的聚类算法：基于距离的聚类算法是用各式各样的距离来衡量数据对象之间的相似度
（2）基于密度的聚类算法：基于密度的聚类算法主要是依据合适的密度函数等
（3）基于互连性的聚类算法: 基于互连性的聚类算法通常基于图或超图模型，将高度连通的对象聚为一类
k-means算法 -基于划分的聚类
- k-means算法首先对可能的聚类定义一个代价函数，聚类算法的目标是寻找一种使代价最小的划分。在这类范例中，聚类任务转化为一个优化问题，目标函数是一个从输入（X，d）和聚类方案 C = （C1，C2，….，Ck）映射到正实数（即损失值）的函数。给定这样一个目标函数，我们将其表示为 G，对于给定的一个输入（X，d），聚类算法的目标被定义为寻找一种聚类 C 使 G（（X，d），C）最小
- 理论和实际的工程化是存在一定的差距的。k均值目标函数在实际的聚类应用中很常见。然而，事实证明寻找k均值（k-means）算法的最优解通常是计算不可行的（NP问题，甚至接近常数近似解的求解是NP问题）
- k-means使用下面的简单的迭代算法作为替代算法：
因此，多数情况下，k均值聚类值得是这种算法的结果而不是最小化 k 均值目标函数的结果
- k均值算法的目标函数优化过程是单调非增的（也就是每次的迭代至少不会让结果更糟），但是 k均值算法本身对达到收敛的迭代次数并没有给出理论保证。此外，算法给出的 k均值目标函数输出值和目标函数的最小可能值之差，并没有平凡下界，实际上，k均值可能会收敛到局部最小值。为了提高 k均值的结果，通常使用不同的随机初始化中心点，将该程序运行多次，并选取最优的结果
- 聚类中心K：
聚类中心的个数K需要事先给定，但在实际中这个 K 值的选定是非常难以估计的，很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。这个过程会是一个漫长的调试过程，我们通过设置一个[k, k+n]范围的K类值，然后逐个观察聚类结果，最终决定该使用什么K值对当前数据集是最佳的。在实际情况中，往往是对特定的数据集有对应一个最佳的K值，而换一个数据集，可能原来的K值效果就会下降。但是同一个项目中的一类数据，总体上来说，通过一个抽样小数据集确定一个最佳K值后，对之后的所有K值都能获得较好的效果
- 初始聚类中心(质心)的选择：
Kmeans需要人为地确定初始聚类中心，不同的初始聚类中心可能导致完全不同的聚类结果。在实际使用中我们往往不知道我们的待聚类样本中哪些是我们关注的label，人工事先指定质心基本上是不现实的，在大多数情况下我们采取随机产生聚类质心这种策略
- 确定了本轮迭代的质心后，将余下的样本点根据距离度量标准进行归类：
计算样本点和所有质心的“距离”，选取“距离”最小（argmin）的那个质心作为该样本所属的类别。这里要注意的是，特征空间中两个实例点的距离是两个实例点相似程度的反映，高维向量空间点的距离求解，可以泛化为Lp距离公式，它在不同的阶次数中分为不同的形式
- 算法收敛（终止/停机）条件：
比较常用的一个停止条件是这样不断进行”划分—更新—划分—更新”，直到每个簇的中心不在移动为止
- k-means算法步骤描述：
（1）选取质心
（2）距离聚类：将每个向量分配到离各自最近的中心点，从而将数据集分成了K个类
（3）重选新质心：计算得到上步得到聚类中每一聚类观测值的均值作为新的质心
（4）重复（3），直至结果收敛，这里的收敛是指所有点到各自中心点的距离的和收敛
- K-mean的3大核心要素是：K值、距离度量公式、初始质心的选择
k-means++算法
- k-means算法缺陷在于算法一开始选择的是随机质心，基于随机质心，算法只能找到局部最优化分簇，对于kmeans这种EM过程来说，最终的聚类结果严重依赖于初始中心点的选择
- K-Means主要有两个最重大的缺陷 - 都和初始值有关：
（1）K是事先给定的，这个K值的选定是非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适
（2）K-Means算法需要用初始随机种子点来搞，这个随机种子点太重要，不同的随机种子点会有得到完全不同的结果
- k-means++算法从一定程度上解决了上述问题，k-means++选择初始seeds的基本思想就是：初始的聚类中心之间的相互距离要尽可能的远
- k-means++算法步骤：
（1）从输入的数据点集合中随机选择一个点作为第一个种子点(聚类中心)
（2）对于数据集中的每一个点x，计算它与最近聚类中心(指已选择的聚类中心)的距离D(x)并保存在一个数组里，然后把这些距离加起来得到Sum(D(x))
（3）选择一个新的数据点作为新的聚类中心，选择的原则是: D(x)较大的点被选取作为聚类中心的概率较大(kMeans不同类别的距离越远越好)：
1）先取一个能落在Sum(D(x))中的随机值Random 2）然后用Random -= D(x)，直到其结果 <= 0 3）选取在这个”递减过程”中D(x)最大的点，此时的点就是下一个”种子点”
（4）重复2和3直到k个聚类中心被选出来
（5）利用这k个初始的聚类中心来运行标准的k-means算法
- k-means这里并不直接用“hard方式”通过遍历每次选取D（x）最大的值作为下一个中心点，而是引入了随机过程，通过随机过程，柔和地体现了：
以正比于D（x）的概率（概率由距离决定）随机选择一个数据点作为新的中心点
- k-means++聚类的基本思想就是：虽然第一个中心点仍然随机选择，但其他的点则优先选择那些彼此相距很远的点
DBSCAN(Density-Based Spatial Clustering of Application with Noise)-基于密度的聚类算法
- 基于密度的聚类方法与其他方法的一个根本区别是：它不是基于各种各样的距离度量的，而是基于密度的。因此它能克服基于距离的算法只能发现“类圆形”的聚类的缺点
- DBSCAN的指导思想是：
用一个点的∈邻域内的邻居点数衡量该点所在空间的密度，只要一个区域中的点的密度大过某个阈值，就把它加到与之相近的聚类中去
- DBSCAN聚类可以找出形状不规则（oddly-shaped）的cluster，且聚类时不需要事先知道cluster的个数
- DBSCAN算法的核心思想如下：从某个选定的核心点出发，不断向密度可达的区域扩张，从而得到一个包含核心点和边界点的最大化区域，区域中任意亮点密度相连
- 考虑数据集合。DBSCAN算法的目标是将数据集合 X 分成 K 个cluster（k由算法自动推断得到，无需事先指定）及噪音点组成，为此，引入cluster标记数组
由此，DBSCAN算法的目标就是生成标记数组
，而 K 即为中互异的非负数的个数
输入：样本集D=(x1,x2,…,xm)
输出： 簇划分C.
- dbscan过程
- DBSCAN在不断发现新的核心点的同时，还通过直接密度可达，发现核心点邻域内的核心点，并把这些邻域内的核心点都归纳到第 k 个聚类中。而噪音点没每轮 k 聚类中会被全局过滤不会参与下一轮启发式发现中，只有边界点在下一次跌打中会被再次尝试检验是否能够成为新聚类的核心点