聚类方法¶
约 1018 个字 预计阅读时间 3 分钟
Warning
这章我看的昏昏的，只算预发布
一些定义¶
样本间距
\[
d_{ij} = \left( \sum_{k=1}^p \left| x_{ik} - x_{jk} \right|^r \right)^{\frac{1}{r}}
\]
首先计算协方差矩阵 S
\[
S = \frac{1}{n-1} \sum_{i=1}^n (x_i - \bar{x})(x_i - \bar{x})^T
\]
首先计算协方差矩阵 S
\[
r_{ij} = \frac{S_{ij}}{\sqrt{S_{ii}S_{jj}}}
\]
\[
\cos \theta_{ij} = \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 = \underset{x_i，x_j \in G}{\operatorname{max}} d_{ij}
\]
也就是所有样本的平均值
\[
\bar{x} = \frac{1}{n} \sum_{x_i \in G} x_i
\]
可以使用两类中样的最短距离，最长距离，中心距离或者平均距离
聚合聚类¶
聚合聚类三要素为：
- 样本间距
- 合并规则
- 停止条件
给定以上三要素，一般的聚合聚类的算法为：
- 开始：每个样本为一个类
- 重复：一句合并规则（一般为找到最小类间间距），合并两类
- 停止：达到停止条件即返回，比如类的个数达到要求
该算法的复杂度为\(O(n^3m)\)，其中 m 为维度数，n 为样本个数
聚合聚类属于层次聚类，因为我们可以得到从 n 类-1 类这一系列的分类结果
注意在过程中我们可以使用\([d_{ij}]\)矩阵来加速运算
K-means¶
时间复杂度为\(O(mnk)\)
k 的选取应该大到类直径不再减小为止
谱聚类¶
数学上，谱字一般跟特征值分解的方法有关
我们把数据集\(\{(x_i)\}\)中的每一个点都对应到一个无向完全图上的点，两点之间连边的权重设置为它们的相似度。
相似度
\[
w_{ij} = e^{-\frac{||x_i - x_j||^2}{2\sigma^2}}
\]
显然，距离越近，相似度越大。
对于那些足够遥远的点，我们可以不再相连，直接把相似度置 0.如何确定这些足够遥远的点呢 - 用 k 近邻确定几个邻近的点 - 用一个\(\epsilon\)半径来区分远近
定义一个点的度为其所有边的权重和，那么我们可以得到下面三个矩阵
矩阵定义
\[
D_{ii} = \sum_{j=1}^n w_{ij}
\]
\[
W = [w_{ij}]
\]
\[
L = D - W
\]
我们可以发现如下性质：
- L 的行和为 0
- L 有一个特征向量为 0，该特征值有一个特征向量为全 1 (1)
- L 有 n 个非负特征值，n 是顶点数
- L 办正定，且\(f^TLf = \frac{1}{2}\sum_{i，j=1}^n w_{ij}(f_i - f_j)^2\)
- L 零特征值的重数等于连通子图的个数
- 这其实就是行和为 0 的直接推论，我们拿全 1 向量左乘 L 就得到 0 向量了
所以当 L 只有一个连通子图的时候，零特征值只有 1 重，也就是全 1 向量
当 L 的连通图多于一个的时候，加入 L 可以写成：
\[
L = \begin{bmatrix}
L_1 & 0 & 0 \\
0 & L_2 & 0 \\
0 & 0 & \dots \\
\end{bmatrix}
\]
那么其对应的零特征向量为：
\[
\begin{bmatrix}
1 \\
1 \\
\vdots \\
0 \\
0 \\
\vdots \\
0 \\
0
\end{bmatrix}
\begin{bmatrix}
0 \\
0 \\
\vdots \\
1 \\
1 \\
\vdots \\
0 \\
0
\end{bmatrix}\dots
\begin{bmatrix}
0 \\
0 \\
\vdots \\
0 \\
0 \\
\vdots \\
1 \\
1
\end{bmatrix}
\]
基本上可以认为，每个连通子图自己构成一个分块\(L_i\)，这个\(L_i\)也有一个自己对应的特征零向量
那么我们将这些特征向量拼接成一个矩阵
\[
F = [f_1，f_2，\dots，f_n]
\]
然后按照行对其进行聚类就可以（也就是说每个连通子图被聚成一类）