下载掌阅APP，畅读海量书库
立即打开
聚类分析是一种无监督学习（Unsupervised Learning）的算法，它是将数据对象按照相似性划分为多个子集的过程，每个子集称为一个“簇”（Cluster）。同一个簇中的数据相似性高，不同簇中的数据相似性低。在利用无监督学习方法划分数据时，数据是没有类别标记的，需要利用样本间的相似性去划分类别，而相似性是依据样本间的距离进行度量。
聚类任务的形式化描述如下：
假设样本集合为 D ={ x 1 , x 2 ,..., x N }，通过聚类把样本划分到不同的簇，使得相似特征的样本在同一个簇中，不相似特征的样本在不同簇中，最终形成 k 个不同簇 C ={ C 1 , C 2 ,..., C k }，若各个簇互不相交，即对任意两个簇 C i ∩ C j = φ ，则称为硬聚类，否则称为软聚类。
聚类本质上是集合划分问题。基本原则是使簇内的样本尽可能相似，通常的做法是根据簇内样本之间的距离，或是样本点在数据空间中的密度来确定。对簇的不同定义可以得到各种不同的聚类算法。聚类分析的算法可以分为基于划分的方法（Partitioning Methods）、层次法（Hierarchical Methods）、基于密度的方法（Density-based Methods）、基于网格的方法（Grid-based Methods）、基于模型的方法（Model-Based Methods）。
基于划分的方法是基于距离作为判断依据，将数据对象划分为不重叠的簇，使每个数据对象属于且只属于一个簇。首先要确定这些样本点最后聚成几类，然后挑选几个样本点作为初始中心点，通过不断迭代，直到达到“类（簇）内的样本点都足够近，类（簇）间的样本点都足够远”的目标。基于划分的距离算法有K-means、K-medoids、kernel K-means等算法。
基于层次的聚类可分为两种：凝聚法和分裂法。凝聚法采用的是一种自底向上的方法，从最底层开始，每一次通过合并最相似的聚类来形成上一层次中的聚类，当全部数据都合并到一个簇或者达到某个终止条件时，算法结束。分裂法采用的是一种自顶向下的方法，从一个包含全部样本数据的簇开始，逐层分裂为若干个簇，每个簇继续不断往下分裂，直到每个簇中仅包含一个样本数据。
在基于密度的聚类方法中，簇被看成是由低密度区域分隔开来的高密度对象区域。基于密度的聚类方法定义了领域的范围，当临近区域的密度超过某个阈值，就继续聚类，即某区域内的对象个数超过一个给定范围，则将其添加到簇中。基于密度的聚类方法可以对不规则形状的数据样本点进行聚类，同时过滤噪声数据效果比较好。DBSCAN（Density-Based Spatial Clustering of Applications with Noise）就是典型的代表。
基于网络的聚类方法将数据空间划分为由若干有限的网格单元（cell）组成的网格结构，将数据对象集映射到网格单元中，所有聚类操作都在该结构上进行。该方法的处理与数据对象个数无关，只依赖于每个量化空间中每一维上的单元数，处理速度快，但算法效率的提高是以聚类结果的准确率为代价的，经常与基于密度的聚类算法结合使用。
基于模型的方法包括基于概率模型的方法和基于神经网络模型的方法。概率模型主要指概率生成模型，同一“类”的数据属于同一种概率分布，即假设数据是根据潜在的概率分布生成的。高斯混合模型（Gaussian Mixture Models，GMM）就是最典型、常用基于概率模型的聚类方法。自组织映射（Self Organized Maps，SOM）则是一种常见的基于神经网络模型的方法。
无论是基于划分的聚类，还是基于层次的聚类，核心问题是度量两个样本之间的距离，常用的距离度量方法有：闵可夫斯基距离、马氏距离、汉明距离、夹角余弦等。
闵可夫斯基距离（Minkowski Distance）将样本看作高维空间中的点进行距离度量。对于n维空间中任意两个样本点 P =（ x 1 , x 2 ,..., x n ） T 和 Q =（ y 1 , y 2 ,..., y n ） T ， P 和 Q 的闵可夫斯基距离定义为：
其中，
为
x
i
-
y
i
的
p
范数。当
p
=1时，有：
此时， d PQ 的取值就是两个点的绝对值之和，称为曼哈顿距离（Manhattan Distance）。几何意义就是沿水平方向从 P 到 Q 的距离。
当 p =2时， P 和 Q 的距离为：
此时， d PQ 就表示二维空间中两个点 P 和 Q 之间的直线距离，称为欧几里得距离或欧氏距离（Euclidean Distance）。
与欧氏距离、曼哈顿距离一样，马氏距离（Mahalanobis Distance）常被用于评定数据之间的相似度指标，它可以看作是欧氏距离的修正，修正了欧氏距离中各维度尺度不一致且相关的问题。单个数据点的马氏距离定义为：
数据点 P 和 Q 之间的马氏距离定义为：
其中，∑是多维随机变量的协方差矩阵，为样本均值。当样本的各个特征向量相互独立，协方差是单位向量，马氏距离就成了欧氏距离。
汉明距离（Hamming Distance）需要将处理的样本数据转换为0和1表示的二进制串，样本中各分量的取值只能是0或1，例如字符串“1110”与“1001”之间的汉明距离为3。对于任意样本特征 x 和 y ，有 x,y ∈{0,1}，其汉明距离为：
汉明距离常应用在信息论、编码理论、密码学等领域。
夹角余弦（Cosine）度量将样本看成是高维空间中的向量进行度量，度量方法就是计算两个向量的余弦夹角。对于任意两个n维样本 P =（ x i 1 , x i 2 ,..., x in ）和 Q =（ y i 1 , y i 2 ,..., y in ），其夹角余弦为：
当n=2时，夹角余弦计算的就是二维空间中两条直线的夹角余弦值。夹角余弦的取值范围为[-1,1]。夹角余弦值越大，表示两个向量的夹角越小；夹角余弦越小，表示两向量的夹角越大。当两个向量的方向重合时，夹角余弦取最大值1；当两个向量的方向完全相反时，夹角余弦取最小值-1。