本章内容主要参考 费宇等《多元统计分析：基于R》， 中国人民大学出版社。

需要额外安装的软件包：

将一些个体分类是人类具有的必不可少的能力， 从婴儿开始， 就学着分辨各种事物， 奶瓶、铃铛、猫、狗，……。 同样一些事物， 可以分成不同的类别。 比如， 图书可以按学科分类， 也可以按封面图案分类， 显然学科分类更有用。 一副扑克牌， 可以按花色分类， 可以按点数分类， 可以按有无人物分类， 等等。

多元统计分析学科中的聚类分析一般指把多元观测数据的观测按照某种临近或相似性标准分成若干组， 每一组内的观测是比较相近或相似的。 这样的聚类又称为Q型聚类，即对样品的聚类。

另一种聚类是把多个变量按照其在所有观测上的取值分成若干个变量组， 每一组内的变量比较相近或相似， 这样的聚类分析称为变量聚类或R型聚类。

从数学上看两种聚类没有本质差别（只要把观测矩阵转置就得到另一种聚类问题）。

聚类分析在机器学习领域又称为无监督（无指导）学习， 这是因为数据中并没有现成的分类可供参考。 而回归分析、判别分析方法则称为有监督学习。

常用的聚类方法包括：

如果不基于数学方法， 对于二维和三维数据， 我们也能利用图像很容易地分类。 比如， 鸢尾花数据：

可以看出至少有两个类。 实际类别情况：

三维数据演示：

这样分类会有主观性， 对高维数据也不易使用。 为判断一般的高维数据点是否属于同一类， 首先应该定义两个点之间相异或者相近（相似）程度的指标。

聚类的思想是把相近的元素聚集到一起。 不同的元素距离定义会造成不同聚类结果。

设\(X\)是实数域上的线性空间， 在\(X\)中定义二元函数\(d(x,y)\)， 如果\(d(x,y)\)满足：

则称\(d(x,y)\)是\(X\)上的一个距离， 称\((X,d)\)为距离空间或度量空间。

下面定义了一些距离， 其中有一些不满足距离定义， 严格来讲只能算是相异度（dissimilarity）：

欧式距离(2范数): \[\begin{aligned} d(\boldsymbol x, \boldsymbol y) = \| \boldsymbol x - \boldsymbol y \|_2 = \sqrt{\sum_{j=1}^p (x_j - y_j)^2} . \end{aligned}\]

曼哈顿距离(1范数): \[\begin{aligned} d(\boldsymbol x, \boldsymbol y) = \| \boldsymbol x - \boldsymbol y \|_1 = \sum_{j=1}^p | x_j - y_j | . \end{aligned}\]

最大值距离(切比雪夫距离，上确界距离，无穷范数)： \[\begin{aligned} d(\boldsymbol x, \boldsymbol y) = \| \boldsymbol x - \boldsymbol y \|_\infty = \max_{j} | x_j - y_j | . \end{aligned}\]

闵可夫斯基（Minkowski）距离(\(\alpha\)范数)： \[\begin{aligned} d(\boldsymbol x, \boldsymbol y) = \| \boldsymbol x - \boldsymbol y \|_\alpha = \left[ \sum_{j=1}^p |x_j - y_j|^\alpha \right]^{1/\alpha} . \end{aligned}\] 其中\(\alpha>0\)。

马氏(Mahalanobis)距离: \[\begin{aligned} d(\boldsymbol x, \boldsymbol y) = \sqrt{ (\boldsymbol x - \boldsymbol y)^T S^{-1} (\boldsymbol x - \boldsymbol y) }, \end{aligned}\]

其中\(S\)是一个正定矩阵，一般取为样本协方差阵， 可以消除量纲与相关性的影响（相关性又与多元观测取值的聚集方向有关）。

兰氏(Lance)距离: \[\begin{aligned} d(\boldsymbol x, \boldsymbol y) = \sum_{j=1}^p \frac{|x_j - y_j|}{x_j + y_j}, \end{aligned}\] 其中所有\(x_j, y_j\)均为正数。

二进(Binary)距离： 若所有分量都取0或1， 则\(\boldsymbol x\)与\(\boldsymbol y\)的距离是各对应分量中恰有一个1的对数与至少有一个1的对数的比值。 这也称为Jaccard距离， 来自生物学中Jaccard指数的定义。 设\(\boldsymbol x\)与\(\boldsymbol y\)的各对分量中同时为1的有\(f_{11}\)对， 至少有一个1的有\(f_{01} + f_{10} + f_{11}\)对， 则Jaccard指数为 \[ J(\boldsymbol x,\boldsymbol y) = \frac{f_{11}}{f_{01} + f_{10} + f_{11}}, \] 而Jaccard距离为 \[\begin{aligned} d(\boldsymbol x, \boldsymbol y) = 1 - J(\boldsymbol x, \boldsymbol y) = \frac{f_{01} + f_{10}}{f_{01} + f_{10} + f_{11}} . \end{aligned}\]

距离越小， 两个观测点\(\boldsymbol x\)与\(\boldsymbol y\)之间越接近。

欧氏距离、曼哈顿距离、最大值距离都是闵可夫斯基距离的特例， 如果各个分量的取值差距很大， 则距离将主要由绝对值大的那个分量决定。 部分问题可以通过标准化每个分量解决， 采用马氏距离也是较好的解决方法。

以上的距离中观测的各分量都是数值型的， 实际数据中的分量有些是数值型的， 有些是分类数据。 这时常用Gower距离， 设观测数据矩阵为\(M=(x_{ij})_{n\times p}\)， 每行为一个观测，每列为一个变量（feature）， 第\(s\)行与第\(t\)行的Gower距离定义为 \[ d(s, t) = \frac{1}{p} \sum_{j=1}^p d_j(s, t, M), \] 如果第\(j\)个分量是分类变量， 则\(d_j(s, t, M)\)仅当观测\(s\)和观测\(t\)的第\(j\)分量属于同一类时等于0， 否则等于1。 如果第\(j\)分量是数值型变量， 则定义 \[ d_j(s, t, M) = \frac{|x_{sj} - x_{tj}|}{\text{range}(x_{1j}, x_{2j}, \dots, x_{nj})} . \] 其中\(\text{range}\)表示极差（最大值减去最小值）。 这样，每个\(d_j(s,t,M)\)都取值于\([0,1]\)中， 最终的\(d(s,t)\)也取值于\([0,1]\)中。 R的cluster包的daisy()函数可以计算Gower距离。

为了度量两个变量的所有观测值之间的距离， 更多地使用相似性的概念。 设数据为\(n\)个观测，每个观测有\(p\)个变量， 第\(i\)个观测为\((x_{i1}, x_{i2}, \dots, x_{ip})\)， 则第\(k\)个变量的\(n\)个观测值与第\(j\)个变量的\(n\)个观测值的相近程度可以用样本相关系数度量: \[\begin{aligned} r_{kj} = \frac{\sum_{i=1}^n (x_{ik} - \bar x_{\cdot k}) (x_{ij} - \bar x_{\cdot j}) } {\sqrt{ \sum_{i=1}^n (x_{ik} - \bar x_{\cdot k})^2 \; \sum_{i=1}^n (x_{ij} - \bar x_{\cdot j})^2}}, \ k, j = 1,2,\dots,p . \end{aligned}\] \(r_{kj}\)越大相似度越高。 在仅关心两个变量关系的强弱而不关心关系是正向还是反向的时候， 也可以用\(|r_{kj}|\)度量相似度。 式中\(\bar x_{\cdot k} = \frac{1}{n} \sum_{i=1}^n x_{ik}\) 是数据矩阵\((x_{ik})_{n\times p}\)的第\(k\)列的样本平均值。

用相关系数转化的距离： \[ d_{kj} = \sqrt{2[1 - r_{kj}]} \]

把第\(k\)个变量的\(n\)个观测值与第\(j\)个变量的\(n\)个观测值看作\(\mathbb R^n\)中的两个向量， 用这两个向量的夹角余弦度量其相近程度: \[\begin{aligned} \cos\theta_{kj} = \frac{\sum_{i=1}^n x_{ik} x_{ij}} {\sqrt{ \sum_{i=1}^n x_{ik}^2 \; \sum_{i=1}^n x_{ij}^2 }} \end{aligned}\] 此余弦取值于\([-1, 1]\)之间，值越大表明第\(k\)和第\(j\)变量相似性越高。

当观测数据集各列是中心化（每列均值为零）时， 两列的相关系数和夹角余弦是相等的。 但是，使用夹角余弦时不取绝对值。

对其它更复杂的对象往往也需要计算相异度或者距离。 igraph扩展包的shortest.paths()函数计算图中各节点之间的距离， xkcd扩展包的cophenetic()函数计算一棵树的叶结点之间的距离， distory扩展包的dist.multiPhylo()函数可以用来计算两棵树之间的距离。

两个图之间的Jaccard距离也可以有定义， 假设两个图的节点相同， 则只要比较共同的边， 据此定义Jaccard距离， igraph扩展包的similarity()函数实现了这一个功能。

距离和相异度也可以用于比较图像、音频、地图、文档等复杂对象。 细心设计的距离定义可以包含学科知识， 并可以将包含许多异质数据的困难问题简化。 例如，对新闻文本， 经常先切分词语再计算词语频数作为数据。 对数据的相似度或相异度的理解可以引发对数据的更好的呈现。

设数据为\(n\)个观测（样品）， 每个观测有\(p\)个变量， 第\(i\)个观测为\((x_{i1}, x_{i2}, \dots, x_{ip})\)， 数据组成数据矩阵\((x_{ij})_{n \times p}\)。

Q型系统聚类法的基本步骤是： 开始时将\(n\)个样品看作单独的\(n\)个类， 将最接近得两个样品合并成一类， 变成\(n-1\)个类； 继续从\(n-1\)个类中找到最相近的两个类将其合并， 变成\(n-2\)个类，如此重复直到合并成了一个大类为止。 R型系统聚类法步骤类似，只不过是针对变量组合并。

系统聚类算法需要考虑两个问题： 如何衡量两个类的相近程度； 如何选择最终分成多少个类。 前一个问题比较基本， 后一个问题更困难。

设\(G_s\)和\(G_t\)为两个类， \(d_{ij}\)表示第\(i\)样品与第\(j\)样品的距离（常用欧式距离）， 度量两个类\(G_s\)与\(G_t\)之间的距离\(D_{st}\)有如下几种常用方法：

\(G_s\)与\(G_t\)之间的距离是两类中距离最近的两个样品的距离，即 \[\begin{align*} D_{st} = \min_{i \in G_s,\; j \in G_t} d_{ij} . \end{align*}\]

\[\begin{align*} D_{st} = \max_{i \in G_s,\; j \in G_t} d_{ij} . \end{align*}\]

中间距离法(median linkage)， 这是介于最小距离与最大距离之间的一种类间距离。

重心距离法(centroid linkage)： 用\(\bar{\boldsymbol x}_s\)表示\(G_s\)中的所有观测的样本平均值， 定义\(G_s\)与\(G_t\)之间的距离为\(D_{st} = d(\bar{\boldsymbol x}_s, \bar{\boldsymbol x}_t)\)。

类平均距离法：设\(G_s\)中有\(n_s\)个观测，\(G_t\)中有\(n_t\)个观测， 定义\(G_s\)与\(G_t\)之间的距离两类的观测之间所有两两组合的距离平均，即

\[\begin{align*} D_{st} = \frac{1}{n_s n_t} \sum_{i \in G_s} \sum_{j \in G_t} d_{ij} . \end{align*}\]

设\(G_s\)和\(G_t\)为两个变量类， 用\(r_{ij}\)表示第\(i\)变量与第\(j\)变量的相似型度量值， 可以定义 \[\begin{align*} R_{st} = \max_{i \in G_s, \; j \in G_t} r_{ij} \end{align*}\] 作为两个变量组\(G_s\)与\(G_t\)之间的相似度。

注意，如果要用相关系数作为变量间相似度， \(r_{ij}\)应取为相关系数绝对值。 夹角余弦可能也需要取绝对值。

measure数据框包含了10个成年男性、10个成年女性的胸围、腰围、臀围测量值(单位：英寸)。 对这三种测量值使用聚类分析， 看能否区分男女。