2.2 聚类

2.2.1 简介

聚类（Cluster Analysis）是将数据集中的所有样本根据相似度的大小进行划分，形成两个或多个类（簇）的过程。作为一种无监督机器学习方法，聚类经常用于数据挖掘和模式识别。簇是数据集中相似的样本集合。聚类没有训练过程，是一种无监督学习。它同分类的根本区别在于：分类需要有标号的样本进行训练。常用的聚类算法可分为基于划分方法的、基于层次方法的、基于密度方法的、基于网格方法的和基于模型方法的聚类。目前常用的聚类算法是基于层次的聚类和基于划分的聚类。基于层次的聚类主要有：平衡迭代削减聚类法、基于密度的聚类方法和使用代表点的聚类方法等；基于划分的聚类方法主要有：K均值聚类算法、K中心点聚类算法和随机搜索聚类算法等。

2.2.2 基本原理

聚类是按照相似性大小，将无标号的数据集划分为若干类或簇的过程。聚类的结果是类内样本的相似度高，类间样本的相似度低。相似性的度量通常采用样本间的距离来表示，距离函数值的大小反映相似的程度。相似度越大，两个样本间的距离函数的值越小；相似度越小，两个样本间的距离函数值越大。

常用的距离计算方法如下。

1.欧氏距离

欧氏距离（Euclidean Distance）是最常见的距离表示法。

假设x={x1,x2,",xn}，y={y1,y2,",yn}，则它们之间的距离为：

即两项间的差是每个变量值差的平方和再取平方根，目的是计算其间的整体距离，即不相似性。欧氏距离的优点是计算公式比较简单，缺点是不能将样本的不同属性（即各指标或各变量）之间的差别等同看待，在某些特定的应用背景中不能满足要求。一般的聚类大都采用欧氏距离。

2.曼哈顿距离

曼哈顿距离（Manhattan Distance）也称为城市街区距离（CityBlock Distance），是在欧氏空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。

二维平面两点a(x1,x2)与b(y1,y2)间的曼哈顿距离定义为：

两个n维向量a(x11,x12,",x1n)与b(x21,x22,",x2n)间的曼哈顿距离：

需要注意的是，曼哈顿距离依赖坐标系统的转度，而非系统在坐标轴上的平移或映射。

3.明氏距离

明氏距离（Minkowski Distance）也被称作闵氏距离，可以理解为N维空间的距离，是欧氏距离的扩展，两个n维变量a(x11,x12,",x1n)与b(x21,x22,",x2n)间的明氏距离定义为：

其中p是一个变参数。

根据变参数的不同，明氏距离可以表示以下的距离。

（1）当p=1时，明氏距离即为曼哈顿距离。

（2）当p=2时，明氏距离即为欧氏距离。

（3）当p→∞时，明氏距离即为切比雪夫距离。

4.余弦距离

余弦距离（Cosine Similarity）也称为余弦相似度，是用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小的度量。

对于二维空间，其定义为：

假设向量a、b的坐标分别为(x1,y1)、(x2,y2)，则：

设向量A=(A1,A2,",An)，B=(B1,B2,",Bn)，推广到多维：

余弦距离通过测量两个向量内积空间夹角的余弦值来度量它们的相似性。余弦值的范围在[-1，1]之间，值越趋近于1，代表两个向量的方向越接近，越相似；越趋近于-1，它们的方向越相反，越不相似；越趋近于0，表示两个向量趋近于正交。余弦距离可以用在任何维度的向量比较中，在高维正空间中采用较多。

2.2.3 常用聚类算法

下面介绍几种常用的聚类算法。

1．K近邻算法（KNN）

K近邻算法是一种常见的有监督的聚类算法，也是非参数分类的重要方法之一。K近邻算法的优点在于算法原理比较简单，容易理解和实现，不需要先验知识等；缺点在于计算量较大，在处理孤立点或噪声方面精度较低。

（1）K近邻算法基本思想

K近邻算法的基本思想是针对测试集中的一个样本点，在已经学习并且完成分类的样本空间中找到K个距离最近的样本点，距离的计算通常采用欧氏距离或明氏距离。如果找到的K个样本点大多属于某一个类别，则可以判定该样本也属于这个类别。

K近邻算法的实现主要有以下3个要素。

① 数据特征的量化。如果数据特征中存在非数值类型，则需要运用一定的手段量化成数值。若样本中存在颜色这一特征属性，可将颜色转化成灰度值来计算距离；或为了保证参数取值较大时的影响力覆盖参数取值较小时的影响力，通常需要对样本的特征数值进行归一化处理。

② 样本间距离计算公式的选择。常见的距离计算公式有欧氏距离、曼哈顿距离、明氏距离、余弦距离等。不同情况下对公式的选择不同，例如：样本变量为连续型时，通常采用欧氏距离；样本变量为非连续型时，通常采用明氏距离。

③ K值的选择。K为自定义的常数，K值的选择对聚类的结果有很大的影响。通常采用交叉验证法确定K的取值，且K的取值一般小于训练样本数的平方根。

（2）K近邻算法过程

K近邻算法过程具体描述如下。

① 构建训练集和测试集，使训练集按照已有的标准分成离散型数值类或连续型数值类。

② 根据样本集为离散型或连续型选择适当的距离计算公式，计算测试集中的数据与各个训练集数据之间的距离，并排序。

③ 利用交叉验证法确定K的取值，并选择距离最小的K个点。

④ 确定K个点所在类别的出现频率，选择出现频率最高的类别作为测试集的预测类。

2．K均值聚类（K-means）

K均值聚类是划分方法中经典的聚类算法之一。其优点是算法简单，聚类效果较好，效率较高，对于处理大数据集有较好的可伸缩性；缺点是 K 值需要事先指定，受孤立点或噪声的影响较大，而且由于算法本身是迭代的，最终得到的结果有可能是局部最优而不是全局最优。

（1）K均值算法基本思想

K均值算法的基本思想是将n个样本点划分或聚类成K个簇，使簇内具有较高的相似度，而簇间的相似度较低。首先确定所要聚类的最终数目 K，并从样本中随机选择 K 个样本作为中心；其次将集合中每个数据点被划分到与其距离最近的簇中心所在的类簇之中，形成 K 个聚类的初始分布；然后对分配完的每一个类簇内对象计算平均值，重新确定新的簇中心，继续进行数据分配过程；迭代执行若干次，若簇中心不再发生变化，且聚类准则函数收敛，则将数据对象完全分配至所属的类簇中；否则继续执行迭代过程，直至聚类准则函数收敛。

（2）K均值算法过程

K均值算法具体描述如下。

假设给定的n个样本是，每个x(i)∈Rn，其中样本间的距离选择欧氏距离。

输入：n个样本和簇的数目K。

输出：K个簇，且平方误差准则最小。

具体步骤如下。

① 确定所要聚类的最终数目K，并从样本中随机选择K个样本作为中心，即μ1,μ2,",μk∈Rn。

② 重复以下过程，直至误差平方和准则函数E收敛至某个固定值。

{

对每个样本i，计算并确定其应属类别：

对于每一个类j，重新计算类的簇中心：

计算E，并判断其是否收敛于某个固定的值。

}

其中K为确定的值，C(i)代表样本i与K个类中距离最近的类，取值为[1,K]，簇中心μj代表对属于同一个类的样本中心点的预测。

聚类准则函数用于判断聚类质量的高低，一般采用误差平方和准则函数 E 的值变化情况判断是否继续进行迭代过程，E的值在每次迭代过程中逐渐减小，最终收敛至一个固定的值，则迭代过程结束，否则继续执行迭代过程，直至E收敛。

误差平方和准则函数E定义如下：

其中，E是所有样本点的平方误差的总和，p是某一样本点，mi是簇Ci的平均值。

3．K中心点聚类（K-mediods）

K中心点聚类算法是对K均值聚类的改进，属于基于划分方法的聚类。与K均值聚类算法相比，优点是减轻了对孤立点的敏感性，提高了聚类结果的准确率；缺点是算法的复杂性比 K 均值聚类算法高。K 中心聚类算法与 K 均值聚类算法最大的区别在于选择将簇内离平均值最近的对象作为该簇的中心，而不是将簇内各对象的平均值作为簇的中心。

（1）K中心点算法基本思想

K中心点算法的基本思想如下。

① 确定所要聚类的最终数目K，并从样本中随机选择K个样本作为中心。

② 将集合中每个数据点被划分到与其距离最近的簇中心所在的类簇之中，形成K个聚类的初始分布。

③ 反复地利用各簇中的非中心点样本来替代中心点样本，并计算各簇中各中心点样本与非中心点样本的距离之和。

④ 迭代执行若干次，寻找最小距离之和，通过不断更新各距离值来不断调整聚类的结果。

（2）K中心点算法过程

K中心点算法具体描述如下。

假设给定的n个样本是，每个x(i)∈Rn，其中样本间的距离选择欧氏距离。

输入：n个样本和簇的数目K。

输出：K个簇。

具体步骤如下。

① 确定所要聚类的最终数目K，并从样本中随机选择K个样本作为中心，即o1,o2,",ok(ok∈D)。

② 对每个样本p，计算并确定其应属类别，使得其欧氏距离M最小。

③ 调整聚类中心，随机选取一个非簇中心样本orandom代替om (1≤m≤k)，重新分配所有剩余样本p，使得

④ 若M′−M <0，则orandom=om，否则本次迭代中om不发生变化。

⑤ 重复执行以上步骤，直到步骤③中M′−M <0不再成立，否则继续迭代执行②。