自动聚类是一种典型的无监督机器学习（无监督学习）方法。聚类试图将数据集中的样本划分为若干个通常不相交的子集，每个子集称为一个簇，通过这样的划分，每一个簇可能对应一些潜在的概念（类别）。

在无监督学习中，训练样本的标记信息是未知的，目的是通过对无标记训练样本的学习来揭晓数据的内在性质及规律，为进一步的数据分析提供基础。此类学习任务中，研究最多的、应用最广泛的是“聚类”。

聚类试图将数据集中的样本划分为若干个通常不相交的子集，每个子集称为一个簇，通过这样的划分，每一个簇可能对应一些潜在的概念（类别），如“浅色瓜”、“深色瓜”，有籽瓜“、”无籽瓜“，甚至”本地瓜“、“外地瓜”。

需说明的是，概念对于聚类算法而言事先是未知的，聚类过程仅能自动形成簇结构，簇所对应的概念语义需由使用者来把握和命名。

聚类既能作为一个单独的过程，用于寻找数据内在的分布结构，也可作为分类等其他学习任务的前驱过程。例如，在一些商业应用中需对新用户的类型进行判别，但定义“用户类型”对商家来说可能不太容易，此时往往可先对用户数据进行聚类，根据聚类结果将每个簇定义为一个类，然后基于这些类训练分类模型，用于判别新用户的类型。

基于不同的学习策略，人们设计出多种类型的算法。

假定样本集 包含 个无标记样本，每个样本 是一个 维特征向量，则聚类算法将样本集 划分为 个不相交的簇 ，其中， ，且 。相应地，我们用 表示样本 的“簇标记”，即 。于是，聚类的结果可用包含 m 个元素的簇标记向量 表示。

原型聚类亦称为“基于原型的聚类”，此类算法假设聚类结构能够通过一组原型刻画，在现实聚类任务中极为常用。通常情形下，算法先对原型进行初始化，然后对原型进行迭代更新求解。采用不同的原型表示、不同的求解方式，将产生不同的算法。

给定样本集 ，‘k-均值’ （k-means）算法针对聚类所得簇划分 最小化平方误差

其中， 是簇 的均值向量。直观看来，上式在一定程度上刻画了簇内样本围绕均值向量的紧密程度，E值越小，则簇内样本相似度越高。

最小化平方误差（上式）并不容易，找到它的最优解需考察样本集D所有可能的簇划分，这是一个NP难问题。因此，k 均值算法采用了贪心策略，通过迭代优化来近似求解，算法流程如下：

输入：样本集；聚类簇数 k

过程：

1）从 D 中随机选择 k 个样本作为初始均值向量

2）repeat

3) 令

4） for do

5) 计算样本 与各均值向量的距离：

6) 根据距离最近的均值向量确定的簇标记：

7） end for

8) fordo

9) 计算新均值向量：

10) if then

11） 将当前均值向量更新为

12） else

13) 保持当前均值向量不变

14） end if

15) end for

16) until 当前均值向量均未更新

输出：簇划分

与 k 均值类似，“学习向量量化”（Learning Vector Quantization，简称LVQ） 也是试图找到一组原型向量来刻画聚类结构，但与一般聚类算法不同的是，LVQ假设数据样本带有类别标记，学习过程利用样本的这些监督信息来辅助聚类。

算法流程如下：

输入：样本集；

原型向量个数 q ，各原型向量预设的类别标记；

学习率

过程：

1） 初始一组原型向量

2） repeat

3） 从样本集合 D 中随机选取样本

4） 计算样本 与的距离：

5) 找出与 距离最近的原型向量 ，

6) if then

7)

8) else

9)

10) end if

11) 将原型向量 更新为

12）until 满足停止条件

输出：原型向量

与k均值、LVQ用原型向量来刻画聚类结构不同，高斯混合模型采用概率模型来表达聚类原型。

基本思想：假设整个数据集服从高斯混合分布，待聚类的数据点看成是分布的采样点，通过采样点利用类似极大似然估计的方法估计高斯分布的参数。求出参数即得出了数据点对分类的隶属函数。

密度聚类亦称为“基于密度的聚类”，此类算法假设聚类结构能通过样本分布的紧密程度确定。通常情形下，密度聚类算法能够从样本密度的角度来考察样本之间的可连接性，并基于可连接性不断扩展聚类簇以获得最终的聚类结果。

DBSCAN是一种著名的密度聚类算法，它基于一组“邻域”参数来刻画样本分布的紧密程度。

具体算法描述如下：

输入: 包含n个对象的数据库，半径e，最少数目MinPts;

输出:所有生成的簇，达到密度要求。

1) Repeat

2) 从数据库中抽出一个未处理的点；

3) if 抽出的点是核心点 then

找出所有从该点密度可达的对象，形成一个簇；

4) else

5) 抽出的点是边缘点(非核心对象)，跳出本次循环，寻找下一个点；

5) until 所有的点都被处理。

层次聚类试图在不同层次上对数据集进行划分，从而形成树形的聚类结构。数据集的划分可采用“自底向上”的聚合策略，也可采用“自顶向下”的分拆策略。

AGNES是一种采用自底向上聚合算法。它先将数据集中的每个样本看作一个初始聚类簇，然后在算法运行的每一步找出距离最近的两个聚类簇进行合并，该过程不断重复，直至达到预设的聚类簇个数。

算法描述：

输入：包含n个对象的数据库，终止条件簇的数目k

输出：k个簇

1) 将每个对象当成一个初始簇

2) Repeat

3) 根据两个簇中最近的数据点找到最近的两个簇

4) 合并两个簇，生成新的簇的集合

5) Until达到定义的簇的数目

聚类性能度量，亦称为聚类“有效性”指标，与监督学习中性能度量类似，对聚类结果，我们需要通过某种性能度量来评估其好坏；另一方面，若明确了最终要使用的性能度量，则直接将其作为聚类过程的优化目标，从而更好地得到符合要求地聚类结果。

聚类是将样本集D划分为若干个不相干地子集，即样本簇。那么什么样地聚类结果比较好呢？直观上看，我们希望“物以类聚”，即同一簇地样本尽可能相似，不同样本地簇尽可能不同。换言之，聚类结果的“簇内相似度高”且“簇间相似度低”。

聚类性能度量有两类：一类是将聚类结果与某个参考模型进行比较，称为“外部指标”；另一类是直接考察聚类结果而不利用任何参考模型，称为“内部指标”。

Jaccard系数（Jaccard Coefficient，简称 JC）

FM指数（Fowlkes and Mallows Index，简称 FMI）

Rand 指数（Rand Index，简称 RI）

上述性能度量的结果值均在[0,1]之间，值越大越好。

DB指数（Davies-Bouldin Index，简称DBI）

Dunn指数（Dunn Index，简称DI）

DBI值越大越好，而DI相反，越小越好。