（更新中）《统计学习方法》Notes(2)

前言

本篇博客基于《统计学习方法》后半部分无监督学习的相关内容，主要记录一些书中的重点内容以及自己的一点总结，以及一些方法的代码实现举例。博客中所有相关代码在https://github.com/Aron00123/Statistical-Learning-Methods-Codes.git

聚类方法

聚类指针对给定的样本，根据它们的特征的相似度或距离，将其归并到若干个“类”或“簇”的数据分析问题。聚类又分为硬聚类与软聚类——每个样本只分类到一个类别称为硬聚类，可以分到多个类别称为软聚类。硬聚类时，每个样本属于某一类；软聚类时，每一个样本依概率属于每一个类。

下面给出一些常用距离的定义：

• 闵可夫斯基距离

给定样本集合X，X是m维实数向量空间中点的集合，其中，则

$$d_{ij} = (\sum_{k=1}^{m}|x_{ki} - x_{kj} |^p)^{\frac{1}{p}}$$

其中，为2时称作欧式距离。

• 马哈拉诺比斯距离

给定样本集合X，是m维实数向量空间中点的集合，其协方差矩阵记作S，则

$$d_{ij} = [(x_i - x_j)^TS^{-1}(x_i-x_j)]^{\frac{1}{2}}$$

• 相关系数

$$r_{ij} = \frac{\underset{k=1}{\overset{m}{\sum}}(x_{ki}-\bar{x}_i)(x_{kj}-\bar{x}_j)}{[\underset{k=1}{\overset{m}{\sum}}(x_{ki}-\bar{x}_i)^2\underset{k=1}{\overset{m}{\sum}}(x_{kj}-\bar{x}_j)^2]^{\frac{1}{2}}}$$

其中。

• 夹角余弦

$$s_{ij} = \frac{\underset{k=1}{\overset{m}{\sum}}x_{ki}x_{kj}}{[\underset{k=1}{\overset{m}{\sum}}x_{ki}^2\underset{k=1}{\overset{m}{\sum}}x_{kj}^2]^{\frac{1}{2}}}$$

• 类与类之间的距离

考虑类之间的距离：

（1）最短距离（单连接）

$$D_{pq} = \min \{d_{ij}|x_i\in G_p, x_j \in G_q \}$$

（2）最长距离（完全连接）

$$D_{pq} = \max \{d_{ij}|x_i \in G_p, x_j \in G_q \}$$

（3）中心距离

$$D_{pq} = d_{\bar{x}_p\bar{x}_q}$$

（4）平均距离

$$D_{pq} = \frac{1}{n_pn_q}\sum_{x_i \in G_p }\sum_{x_j \in G_q}d_{ij}$$

层次聚类

层次聚类假设类别之间存在层次结构，将样本聚到层次化的类中。层次聚类分为聚合（agglomerative）或自下而上（bottom-up）聚类、分裂（divisive）或自上而下（top-down）聚类。层次聚类属于硬聚类。聚合聚类开始将每个样本各自分到一个类；之后将距离最近的两类合并，建立一个新的类，重复此操作直到满足停止条件；得到层次化的恶类别。分裂聚类则相反，开始将所有样本分到一个类；之后将已有类中相距最远的样本分到两个新的类，重复此操作直到满足停止条件；得到层次化的类别。

• 聚合聚类算法

输入：n个样本组成的样本集合及样本之间的距离；

输出：对样本集合的一个层次化聚类

（1）计算n个样本量量之间的欧式距离，记作矩阵；

（2）构造n个类，每个类只包含一个样本；

（3）合并类间距离最小的两个类，其中最短距离为类间距离，构建一个新的类；

（4）计算新类与当前各类的距离。若类的个数满足要求，终止计算，否则返回（3）。

层次聚类的时间复杂度是，其中m是样本维数，n是样本个数。

k均值聚类

• k均值聚类算法

输入：n个样本的集合X；

输出：样本集合聚类C；

（1）初始化。令t=0，随机选择k个样本点作为初始聚类中心；

（2）对样本进行聚类。对固定的类中心，计算每个样本到类中心的距离，将每个样本指派到与其最近的中心的类中，构成聚类结果；

（3）计算新的类中心。对聚类结果，计算当前各个类中的样本的均值，作为新的类中心；

（4）如果迭代收敛或符合停止条件，输出；否则令，返回（2）。

k均值聚类算法的复杂度是，其中m是样本维数，n是样本个数，k是类别个数。

奇异值分解