聚类

聚类就是一组数据对象的集合。在同一聚类中，数据对象是相似的；而在不同的聚类中，数据对象是不相似的。而“相似”的标准是较多的，因此催生了不同的聚类算法。

聚类是机器学习算法中出现最多最快的领域。总能找到一个新的标准，使得之前的算法对其无能为力。

聚类算法就根据给定的相似性评价标准，将一个数据集合分组成几个聚类（簇）。聚类的一种方法就是根据不同样本之间的差异，将每个样本的特征向量看作空间中分布的点，再根据距离函数的规律进行聚类。

一般而言，聚类算法是一种无监督学习算法。聚类所说的类不是事先给定的，而是根据数据的相似性和距离进行划分。因此，聚类的具体分划结果很可能是人类难以理解的。

聚类的关键点在于特征的选取或设计还有距离度量函数的选择。如果数据点的分布比较密集，那么就容易聚类；反之，如果数据点分布的比较混杂，就很难分类。对具体数据而言，选取合适的特征是很关键的。如果特征选取的好，那么许多问题都会迎刃而解。

距离度量

距离度量的目标是度量同类样本之间的相似性和不同类样本间的差异性。距离度量函数的选择对聚类结果有很大的影响。

距离函数 $d$ 需要具有以下性质：

1. 非负性：$d(x,y)\ge 0$
2. 同一性：$d(x,y)=0$当且仅当$x=y$
3. 对称性：$d(x,y)=d(y,x)$
4. 三角不等式：$d(x,y)+d(y,z)\ge d(x,z)$

常用的距离度量函数有欧式距离、曼哈顿距离、切比雪夫距离、马氏距离、余弦相似度等。

聚类准则

类的定义有很多种，其划分具有人为性。一个聚类结果的优劣最后只能根据实际来评价。在聚类有了样本的距离度量后，还需要一种基于数值的聚类准则，才能将相似的样本分在同一类，将不相似的样本分在不同类。例如对于欧式距离的距离度量，它可以刻画样本之间的相似性，但是当我们需要对样本的划分进行决策时，我们还需要一个准则来指导，这就是聚类准则。

例如，一种聚类准则函数的定义为：

$$J=\sum _{i=1}^k\sum _{x\in C_i}||x-u_i|{|}^2$$

其中，$k$ 为聚类的个数，$C_i$ 为第 $i$ 个类，$u_i$ 为第 $i$ 个类的均值向量。可是，这种方法没有考虑样本之间的不相似性。

基于试探的聚类搜索算法

按照最近邻规则的简单试探法

给定 $N$ 个待分类的数据样本 $\{x_1,x_2,\cdots ,x_n\}$，要求按照距离阈值 $T$，将这些样本分为若干个类 $z_1,z_2,\cdots$。算法步骤如下：

• 首先任取一个样本 $x_i$，将其作为一个类的代表 $z_1$，将其从样本集中删除。
• 从剩余的样本中任选一个样本 $x_j$，计算 $x_j$ 与所有 $z_i$ 的距离，如果对于所有 $z_i$，$d(x_j,z_i)>T$，则将 $x_j$ 作为一个新的类的代表 $z_2$，并将其从样本集中删除；反之，将 $x_j$ 分配到与其距离最近的 $z_i$ 所代表的类中。重复这一步骤，直到所有样本都被分配到某一个类中。

最大最小距离思想

以试探类间欧式距离最大值作为预选簇初距离中心的标准。算法步骤如下：

• 首先选取一个样本作为第一个类的代表 $z_1$，将其从样本集中删除。
• 计算剩余样本 $x_i$ 与所有 $z_i$ 的距离，并求出 $x_j$ 与所有 $z_i$ 的最小距离 $d_{min}(x_i)$。在所有剩余样本中，选取 $x_j$ 使得 $d_{min}(x_j)$ 最大的样本。若 $d_{min}(x_j)$ 超过一定的比例，则将 $x_j$ 作为新的类的代表，并将其从样本集中删除。重复这一步骤，直到所有样本都无法成为新的类的代表。至此，所有的类的代表已经确定。
• 将剩余的样本分配到与其距离最近的类中。

系统聚类法

将数据样本按照距离准则进行逐步渐进分类，类别由多到少，直到获得合适的分类要求为止。算法步骤如下：

• 假设有 $N$ 个样本，首先将每个样本看作一个类，即建立 $N$ 个类 $G_1^{(0)},G_2^{(0)},\cdots ,G_N^{(0)}$。计算各个类之间的距离，建立 $N\times N$ 距离矩阵 $D^{(0)}$。
• 在剩余的类别中，选择距离最近的两个类 $G_i^{(n)}$ 和 $G_j^{(n)}$ 合并成一个新的类 $G_{ij}^{(n+1)}$。计算新类与其他类的距离，建立新的距离矩阵 $D^{(n+1)}$。
• 重复上一步，直到类别满足某种条件为止。

动态聚类法

首先选取若干个样本点作为聚类中心，然后按照某种聚类准则使得样本点逐渐向聚类中心靠拢，直到满足某种条件为止。主要包含 K-means 算法 和 ISODATA 算法。

K-means 算法的过程如下：

• 选择一个聚类数量 $k$，初始化聚类中心 ${\mu }_1,{\mu }_2,\cdots ,{\mu }_k$。
• 对于每个样本点，计算其到每个聚类中心的距离，将其分配到距离最近的聚类中心所代表的类中。
• 对于每个类，重新计算其聚类中心。聚类中心为该类中所有样本点的均值。
• 重复上两步（即每次重新计算聚类中心后都重新分类），直到聚类中心收敛。

K-means 算法的结果经常受到所选聚类数目、初始聚类中心和数据本身几何分布的影响。例如，如果数据分布在一个环上，聚类中心往往会收敛到圆心上，这可能不是我们想要的结果。

ISODATA 算法的过程如下：

• 选择一个聚类数量 $K_0$，初始化聚类中心 $c_1,c_2,\cdots ,c_{K_0}$。然后将所有样本点分配到最近的聚类中心所代表的类中。
• 判断每个类的样本数量是否满足一定的条件，如果满足，则保留该类；反之，将该类中样本数量最少的样本点从该类中删除，并将其分配到其他类中。
• 对于每个类，重新计算其聚类中心。聚类中心为该类中所有样本点的均值。
• 如果当前的聚类数量 $K$ 满足 $K\le K_0/2$，则进行分裂操作。首先计算每个类的样本点的方差，选择方差最大的类。对于这个类，我们考察它的方差和样本数量是否足够大，如果满足，则将其分裂为两个类，否则不进行操作。分裂后的两个类的中心为原来类的中心加减一个偏置量，这个偏置量与原来类的方差有关。
• 如果当前的聚类数量 $K$ 满足 $K\ge 2K_0$，则进行合并操作。新的聚类中心为合并的两个聚类中心的按样本数加权的均值。
• 重复上面四步，直到聚类中心收敛。

ISODATA 算法的优点在于可以自动确定聚类的数量。但它也需要设置很多参数，所以在实际的使用中效果可能还不如 K-means 算法。

聚类评价

聚类评价即对聚类好坏的评估。一般而言，我们可以度量聚类中心之间的距离、聚类域中的样本数和聚类内部的样本之间的距离和方差来衡量。具体的评价指标有如下几种：

• 紧密度：如衡量聚类内部的样本之间的距离和方差。
• 分离度：如衡量聚类中心之间的距离。
• 邓恩指数 $\mathrm{DVI}$：综合衡量类内部的距离和类间的距离。具体为

$$\mathrm{DVI}=\frac{\underset{1\le i<j\le n}{min}d(i,j)}{\underset{1\le k\le n}{max}{d}^{\prime }(k)}$$

其中，$d^{\prime }(k)$ 为第 $k$ 个类中样本点之间的最大距离，亦称类的直径；$n$ 为聚类的个数。