聚类分析用于洞察数据的分布，观察每个簇的特征，进一步分析特定簇的特征。由于簇是数据对象的子集合，簇内的对象彼此相似，而与其他簇的对象不相似，因此，簇可以看作数据集的“隐性”分类，聚类分析可能会发现数据集的未知分组。

聚类通过观察学习，不需要提供每个训练元素的隶属关系，属于无监督式学习（unspervised learning），无监督学习是指在没有标注的数据中寻找隐含的结构信息。数据的内部构造描绘了要分组的对象，并且决定了如何最佳地把数据对象分组。主要的聚类算法可以分为以下四类：

• 划分聚类（Partitioning Clustering）
• 层次聚类（Hierarchical clustering）
• 基于密度的方法
• 基于网格的方法

本文简单介绍最简单的划分聚类算法，划分聚类是指：给定一个n个对象的集合，划分方法构建数据的k个分组，其中，每个分区表示一个簇，并且 k<= n，也就是说，把数据划分为k个组，使得每个组至少包含一个对象，基本的划分方法采取互斥的簇划分，这使得每个对象都仅属于一个簇。为了达到全局最优，基于划分的聚类需要穷举所有可能的划分，计算量极大，实际上，常用的划分方法都采用了启发式方法，例如k-均值（k-means）、k-中心点(k-medoids），渐进地提高聚类质量，逼近局部最优解，启发式聚类方法比较适合发现中小规模的球状簇。

一，k-均值

k-均值（kmeans）是一种基于形心的计数，每一个数据元素的类型是数值型，k-均值算法把簇的形心定义为簇内点的均值，k-均值算法的过程：

输入：  k（簇的数目），D（包含n个数据的数据集）

输出：  k个簇的集合

算法：

1. 从D中任意选择k个对象作为初始簇中心；
2. repeat
3.   根据cu中对象的均值，把每个对象分配到最相似的簇；
4.   更新簇的均值，即重新计算每个簇中对象的均值；
5. until 簇均值不再发生变化

不能保证k-均值方法收敛于全局最优解，但它常常终止于局部最优解，该算法的结果可能依赖于初始簇中心的随机选择。

k-均值方法不适用于非凸形的簇，或者大小差别很大的簇，此外，它对离群点敏感，因为少量的离群点能够对均值产生极大的影响，影响其他簇的分配。

R语言中，stats包中的kmeans()函数用于实现k-均值聚类分析：

kmeans(x, centers, iter.max = 10, nstart = 1,        algorithm = c("Hartigan-Wong", "Lloyd", "Forgy","MacQueen"), trace=FALSE)

参数注释：

• x：数值型的向量或矩阵
• centers：簇的数量
• iter.max：重复的最大数量，默认值是10
• nstart：随机数据集的数量，默认值是1
• algorithm：算法的选择，默认值是Hartigan-Wong

函数返回的值：

• cluster ：整数向量，整数值是从1到k，表示簇的编号
• centers：每个簇的中心，按照簇的编号排列
• size：每个簇包含的点的数量

二，k-中心点

k-中心点不使用簇内对象的均值作为参照点，而是挑选实际的数据对象p来代表簇，其余的每个对象被分配到与其最为相似的对象代表p所在的簇中。通常情况下，使用围绕中心点划分（Partitioning Around Medoids，PAM）算法实现k-中心点聚类。

PAM算法的实现过程：

输入：  k（簇的数目），D（包含n个数据的数据集）

输出：  k个簇的集合

算法：

• 从D中随机选择k个对象作为初始的代表对象或种子；
• repeat
•   把每个剩余的对象分配到最近的代表对象p所在的簇；
•   随机地选择一个非代表对象R
•   计算用R代替代表对象p的总代价S；
•   if S<0 then 使用R代替p，形成新的k个代表对象的集合；
• until  代表对象不再变化

当存在离群点时，k-中心点方法比k-均值法更鲁棒（所谓“鲁棒性”，是指控制系统在一定（结构，大小）的参数摄动下，维持某些性能的特性），这是因为中心点不像均值法那样容易受到离群点或其他极端值的影响。但是，当n和k的值较大时，k-中心点计算的开销变得相当大，远高于k-均值法。

R语言中，cluster包中的pam()函数用于实现k-中心点聚类分析：

pam(x, k, diss = inherits(x, "dist"),metric = c("euclidean", "manhattan"), medoids = NULL, stand = FALSE, ... )

参数注释：

• diss：逻辑值，默认值是TRUE，当diss为TRUE时，x参数被认为是相异矩阵（dissimilarity matrix）；当diss为FALSE时，x参数被认为是包含变量的观测矩阵
• metric：字符类型，用于指定用于在两个观测之间计算差异的度量（mertic），有效值是"euclidean" 和"manhattan"，分别用于计算欧几里德距离和曼哈顿距离，如果diss参数为TRUE，那么该参数会被忽略。
• medoids：默认值是NULL，用于指定聚类的初始的中心点。
• stand：逻辑值，默认值是FALSE。如果设置为TRUE，那么在对x计算相异度量之前，按照列对x进行标准化（无量纲化处理），也就是说，对每列的数据进行标准化。标准化操作算法是：通过减去变量的平均值并除以变量的平均绝对偏差，对每个变量（列）进行标准化测量。 如果x已经是相异矩阵，则该参数将被忽略。

函数返回的对象：

• medoids：每个簇的中心点
• clustering：向量，用于表示每个观测所属于的簇
• silinfo：轮廓数据，包括每个观测的轮廓系数，每个簇的平均轮廓系数，整个数据集的平均轮廓系数。

三，聚类评估

当我们再数据集上试用一种聚类方法时，如何评估聚类的结果的好坏？一般来说，聚类评估主要包括以下任务：

• 估计聚类趋势：仅当数据中存在非随机数据时，聚类分析才是有意义的，因此，评估数据集是否存在随机数据。
• 确定数据集中的簇数：在使用聚类算法之前，需要估计簇数
• 测定聚类质量：在数据集上使用聚类方法之后，需要评估簇的质量。

1，估计聚类趋势

聚类要求数据是非均匀分布的，霍普金斯统计量是一种空间统计量，用于检验空间分布的变量的空间随机性。

comato包中有一个Hopkins.index()函数，用于计算霍普金斯指数，如果数据分布是均匀的，则该值接近于0.5，如果数据分布是高度倾斜的，则该值接近于1。