聚类方法¶

约 1018 个字预计阅读时间 3 分钟

Warning

这章我看的昏昏的，只算预发布

一些定义¶

样本间距

d_{i j} = {(\sum_{k = 1}^{p} {| x_{i k} - x_{j k} |}^{r})}^{\frac{1}{r}}

首先计算协方差矩阵 S

S = \frac{1}{n - 1} \sum_{i = 1}^{n} (x_{i} - \bar{x}) (x_{i} - \bar{x})^{T}

首先计算协方差矩阵 S

r_{i j} = \frac{S_{i j}}{\sqrt{S_{i i} S_{j j}}}

\cos θ_{i j} = \frac{x_{i}^{T} x_{j}}{\sqrt{x_{i}^{T} x_{i} x_{j}^{T} x_{j}}}

一些矩阵

样本散布矩阵协方差矩阵

S = \sum_{i = 1}^{n} (x_{i} - \bar{x}) (x_{i} - \bar{x})^{T}

S = \frac{1}{n - 1} \sum_{i = 1}^{n} (x_{i} - \bar{x}) (x_{i} - \bar{x})^{T}

类相关定义

类类直径类中心类间距离

一个类就是数据集的一个子集

类内最远间距

D_{G} = \max_{x_{i} ， x_{j} \in G} d_{i j}

也就是所有样本的平均值

\bar{x} = \frac{1}{n} \sum_{x_{i} \in G} x_{i}

可以使用两类中样的最短距离，最长距离，中心距离或者平均距离

聚合聚类¶

聚合聚类三要素为：

样本间距
合并规则
停止条件

给定以上三要素，一般的聚合聚类的算法为：

开始：每个样本为一个类
重复：一句合并规则（一般为找到最小类间间距），合并两类
停止：达到停止条件即返回，比如类的个数达到要求

该算法的复杂度为 $O (n^{3} m)$ ，其中 m 为维度数，n 为样本个数

聚合聚类属于层次聚类，因为我们可以得到从 n 类-1 类这一系列的分类结果

注意在过程中我们可以使用 $[d_{i j}]$ 矩阵来加速运算

K-means¶

时间复杂度为 $O (m n k)$

k 的选取应该大到类直径不再减小为止

谱聚类¶

数学上，谱字一般跟特征值分解的方法有关

我们把数据集 ${(x_{i})}$ 中的每一个点都对应到一个无向完全图上的点，两点之间连边的权重设置为它们的相似度。

相似度

w_{i j} = e^{- \frac{| | x_{i} - x_{j} | |^{2}}{2 σ^{2}}}

显然，距离越近，相似度越大。

对于那些足够遥远的点，我们可以不再相连，直接把相似度置 0.如何确定这些足够遥远的点呢 - 用 k 近邻确定几个邻近的点 - 用一个 $ϵ$ 半径来区分远近

定义一个点的度为其所有边的权重和，那么我们可以得到下面三个矩阵

矩阵定义

度矩阵 D权重矩阵 W拉普拉斯矩阵 L

D_{i i} = \sum_{j = 1}^{n} w_{i j}

W = [w_{i j}]

L = D - W

我们可以发现如下性质：

L 的行和为 0
L 有一个特征向量为 0，该特征值有一个特征向量为全 1
L 有 n 个非负特征值，n 是顶点数
L 办正定，且 $f^{T} L f = \frac{1}{2} \sum_{i ， j = 1}^{n} w_{i j} (f_{i} - f_{j})^{2}$
L 零特征值的重数等于连通子图的个数

所以当 L 只有一个连通子图的时候，零特征值只有 1 重，也就是全 1 向量

当 L 的连通图多于一个的时候，加入 L 可以写成：

L = [\begin{matrix} L_{1} & 0 & 0 \\ 0 & L_{2} & 0 \\ 0 & 0 & \dots \end{matrix}]

那么其对应的零特征向量为：

[\begin{matrix} 1 \\ 1 \\ ⋮ \\ 0 \\ 0 \\ ⋮ \\ 0 \\ 0 \end{matrix}] [\begin{matrix} 0 \\ 0 \\ ⋮ \\ 1 \\ 1 \\ ⋮ \\ 0 \\ 0 \end{matrix}] \dots [\begin{matrix} 0 \\ 0 \\ ⋮ \\ 0 \\ 0 \\ ⋮ \\ 1 \\ 1 \end{matrix}]

基本上可以认为，每个连通子图自己构成一个分块 $L_{i}$ ，这个 $L_{i}$ 也有一个自己对应的特征零向量

那么我们将这些特征向量拼接成一个矩阵

F = [f_{1} ， f_{2} ， \dots ， f_{n}]

然后按照行对其进行聚类就可以（也就是说每个连通子图被聚成一类）