1 概述

 聚类是针对给定的样本，依据他们特征的相似度或距离，将其归并到若干个类或簇的数据分析问题。
 聚类的目的是通过得到的类或簇来发现数据的特点，或对数据进行处理，在数据挖掘等领域有广泛的应用，聚类属于无监督学习，因为只是根据样本的相似度或距离将其归类，而类或簇事先并不知道。
 常用的聚类算法有层次聚类和k均值聚类。层次聚类又分为聚合和分裂两种方法。本文章主要介绍这两种聚类算法。

2聚类的基本概念

 本小节介绍聚类的基本概念，包括样本之间的距离或相似度，类或簇，类与类之间的距离。

2.1 相似度或距离

 给定数据 $X$X
$X=[x_{ij}]_{m*n} = \left[ \begin{matrix} x_{11}& x_{12} & ...& x_{1n} \\ x_{21} & x_{22} & ... & x_{2n} \\ ... & ... & ... & ... \\ x_{m1} & x_{m2} & ... & x_{mn} \end{matrix} \right]$X=[xij​]m∗n​=⎣⎢⎢⎡​x11​x21​...xm1​​x12​x22​...xm2​​............​x1n​x2n​...xmn​​⎦⎥⎥⎤​
 矩阵的第 $j$j 列表示第 $j$j 个样本，$j$j =1,2,…,n; 第 $i$i 行表示第 $i$i 个属性， $i$i =1,2,…,m；矩阵元素 $x_{ij}$xij​ 表示第 $j$j 个样本的第 $i$i 个属性。

 聚类的核心概念的相似度或者距离，有多种相似度或距离的定义，因为不同的距离算法会直接影响到聚类结果，所以要因地制宜选择合适的距离公式。

1. 闵可夫斯基距离
   

2. 曼哈顿距离
   

3. 欧氏距离
   

4. 切比雪夫距离
   

5. 马哈拉诺比斯距离
   

2.2 类或簇

 通过聚类得到类或簇本就是样本的子集，如果一个聚类方法，假定一个样本只能属于一个类，或类的交集为空集，那么该方法称为硬聚类，否则如果样本可以属于多个类，或类的交集不为空集，那么该方法称为软聚类，我们只考虑硬聚类的方法。
 用 $G$G 表示类或簇，用 $x_i,x_j$xi​,xj​ 表示类中的样本，用 $n_G$nG​ 表示 $G$G 中样本的个数，用 $d_{ij}$dij​ 表示样本 $x_i$xi​ 与 $x_j$xj​ 的距离。有以下的定义

定义1：
 设 $T$T 为给定的正数，若集合 $G$G 中任意两个样本$x_i,x_j$xi​,xj​，有
$d_{ij} \leq T$dij​≤T则称G为一个类或簇
定义2：
 设 $T$T 为给定的正数，若集合 $G$G 中任意样本 $x_i$xi​，一定存在 $G$G 中的另外一个样本 $x_j$xj​，使得$d_{ij} \leq T$dij​≤T则称G为一个类或簇
定义3：
设 $T$T 为给定的正数，若集合 $G$G 中任意样本 $x_i$xi​，$G$G中的另一个样本 $x_j$xj​ 满足 $\frac{1}{n_G-1}\sum_{x_j \in G} d_{ij} \leq T$nG​−11​xj​∈G∑​dij​≤T则称G为一个类或簇
定义4：
设 $T$T 和 $V$V 为给定的两个正数，如果集合 $G$G 中任意两个样本 $x_i$xi​, $x_j$xj​ 的距离 $d_{ij}$dij​ 满足 $\frac{1}{n_G(n_G-1)}\sum_{x_i \in G} \sum_{x_j \in G} d_{ij} \leq T$nG​(nG​−1)1​xi​∈G∑​xj​∈G∑​dij​≤T则称G为一个类或簇

有以下的定义

1 类的均值 $\bar{x}_G$xˉG​，又称为类的中心$$\bar{x}_G = \frac{1}{n_G}\sum_{i=1}^{n_G}x_i$xˉG​=nG​1​i=1∑nG​​xi​
2 类的直径 $D_G$DG​ $D_G = max\quad d_{xj} (x_i,x_j \in G)$DG​=maxdxj​(xi​,xj​∈G)

2.3 类与类的距离

 下面考虑类 $G_p$Gp​ 与 类 $G_q$Gq​ 之间的距离。设类 $G_p$Gp​ 有 $n_p$np​ 个样本，类 $G_q$Gq​ 有 $n_q$nq​ 个样本，$\bar{x_p}$xp​ˉ​ 表示类 $G_p$Gp​ 的中心点。$\bar{x_q}$xq​ˉ​ 表示类 $G_q$Gq​ 的中心点。

1. 最短距离
   

2. 最长距离
   

3. 中心距离
   

4. 平均距离
   

3 层次聚类

 层次聚类分为聚合和分裂两种方法。聚合聚类开始将每个样本各自分到一个类,之后将相聚最近的两类合并建立一个新的类,重复此操作，直到满足停止条件，得到层次化的类别。分裂巨类，开始将所有样本分到一个类之后，将已有类中相距最远的样本分到像两个新的类，重复此操作，直到满足停止条件。得到层次化的类别。本章只讨论聚合聚类。

3.1 聚合聚类算法

3.2 聚合聚类例题

4 k均值聚类

 K均值聚类是基于样本集合划分的聚类算法，k均值及聚类将样本集合划分为K个子集构成K个类，将n个样本分到K个类中，每个样本到其所属类的中心的距离最小，每个样本只能属于一个类，所以k均值聚类是硬聚类。

4.1 K均值算法

 K均值聚类的算法是一个迭代的过程，每次迭代包括两个步骤，首先选择k个类的中心，将样本逐个指派到与其最近的中心的类中，得到一个聚类结果，然后更新每个类的样本的均值作为类的新的中心，重复以上步骤，直到收敛为止。

4.2 k均值例题

4.2 k值的选择

 K均值聚类中的类别数k值需要预先指定。而在实际应用中最优的k值是不知道的。解决这个问题的一个方法是尝试用不同的k值聚类。检验各自得到聚类结果的质量，推测最优的k值。聚类结果的质量可以用类的平均直径来衡量，一般的类别数变小时平均之间会增加，类别数变大超过某个值以后，平均直径不变，而这个值是最优的k值。实验室可以用二分查找，快速找到最优的k值。