聚类简介
什么是聚类？
分类问题是机器学习中最常见的一类问题，它的目标是确定一个物体所属的类别。我们这里最常见的就是文本分类问题。例如情感分类，确定一段文本的情感极性：
今天心情不错，晴空万里 正面
烦死了，外面下雨没法回家了 负面
分类问题通常的做法是把数据样本表示为空间的一个点，然后对空间进行切割和划分，空间不同区域表示不同的类别。如下图，给定绿色和红色点，分类的训练目标是寻找一个超平面，能把绿色和红色点分离，预测时给定黄色的点，问其类别。
聚类也是要确定一个物体的类别，但和分类问题不同的是，这里没有事先定义好的类别，聚类算法要自己想办法把一批样本分开，分成多个类，**保证每一个类中的样本之间是相似的，而不同类的样本之间是不同的** 。在这里，类型被称为“**簇** ”（cluster），例如下图，左边为原始数据样本点，右边为期望得到的聚类结果。
介绍聚类算法之前，先看demo。一些聚类算法是非常“潮”的，可以做出非常惊人的聚类效果！
但是，**聚类算法并不一定有标准的答案！** 聚类本质上是集合划分问题。因为没有人工定义的类别标准，因此算法要解决的核心问题是如何定义簇。类簇定义的标注一般要求簇内的样本尽可能相似，簇间的样本尽量不同。对簇的不同定义可以得到各种不同的聚类算法。常见的聚类算法有（还有其他的归类方法这里不介绍了）：**连通性聚类** ，典型代表是层次聚类算法，它根据样本之间的联通性来构造簇，所有联通的样本属于同一个簇。**基于质心的聚类** ，典型代表是k均值算法，它用一个中心向量来表示这个簇，样本所属的簇由它到每个簇的中心距离确定。效果如下图所示：
问题的严格定义（来点高大上的感觉）
聚类问题可以抽象成数学中的**集合划分问题** 。假设一个样本集
\[C=\{x_1,x_2,...,x_l\}\]，聚类算法把这个样本集划分成 $m$ 个不相交的子集
\[C=c_1 \cup c_2 \cup ...c_m, \forall_{1 \le i,j \le m, i \ne j} c_i \cap c_j = \emptyset\]每个样本只能属于这些子集中的一个，即任意两个子集之间没有交集，同时满足同一个子集内部的各个样本之间要很相似，不同子集的样本之间要尽量不同。
主要的算法
聚类算法种类非常多，在这里简单列举和描述一下：
- 层次聚类： 可以自顶向下（有点像决策树），也可以自底向上（联想Huffman树）构建聚类，不同层次的每棵子树都是一个类别。例如生物分类界门纲目科属种。
- 基于质心的聚类： 基于质心的聚类算法计算每个簇的中心向量，以此为依据来确定每个样本所属的类别，代表K均值k-means
- 基于概率分布的聚类： 基于概率分布的聚类算法假设每个簇的样本服从相同的概率分布，典型的高斯混合模型 GMM
- 基于密度的聚类： 基于密度的聚类算法的核心思想是根据样本点某一邻域内的邻居数定义样本空间的密度，这类算法可以找出空间中形状不规则的簇，并且不用指定簇的数量。代表 DBSCAN
- 基于图的聚类： 基于图的算法把样本数据看作图的顶点，根据数据点之间的距离构造边，通过图的切割实现聚类，即将图切分成多个子图，这些子图就是对应的簇。
上图中左上是层次聚类，右上是基于质心的聚类，左下是基于概率分布的聚类，右下是基于密度的聚类。