1. 聚类
给定样本集 \(D = \{ \bm{x}_1, \bm{x}_2, ..., \bm{x}_n \}\)，\(\bm{x}_i \in \mathbb{R}^d\)。
通过聚类将 \(n\) 个样本划分为 \(k\) 个 簇划分 \(\mathcal C = \{ C_1, C_2, ..., C_k \}\)，使得：
\[C_i \cap C_j = \emptyset, \ \forall i \not = j \ 且 \ \bigcup_{i=1}^{k}C_i = D \]找到一个划分 \(\mathcal C = \{ C_1, C_2, ..., C_k \}\) ，最小化误差平方和:
\[\min J(C_1, \ldots, C_k) = \sum_{i = 1}^{k} \sum_{\bm{x} \in C_i} ||\bm{x} - \bm{\mu}_i||^2 \]其中 \(\bm{\mu}_i\) 为第 \(i\) 个簇 \(C_i\) 的均值向量：
\[\bm{\mu}_i = \frac{1}{|C_i|}\sum_{\bm{x} \in C_i} \bm{x} \]- 样本向量 \(\bm{x}_j\) 与均值向量 \(\bm{\mu}_i\) 之间的距离，\(d_{ji} = \text{dist}_f(\bm{x}_j, \bm{\mu}_i)\)，其中函数 \(f\) 可以是 欧几里得距离 或者 曼哈顿距离。
2. \(k\text{-means}\)
2.1 算法步骤
-
随机选取 \(k\) 个簇中心 \(\bm{\mu}_1, \ldots, \bm{\mu}_k\)。
-
计算各个样本 \(\bm{x}_j\) 到各个簇中心 \(\bm{\mu}_i\) 的距离。并距离 \(\bm{x}_j\) 找到 最近的簇中心：
\[\lambda_j = \text{argmin}_{i = 1, 2, \ldots, k} d_{ji} \]将 \(\bm{x}_j\) 划分到该簇中：\(C_{\lambda_j} = C_{\lambda_j}\cup \bm{x}_j\)
-
重新计算每个簇的簇中心 \(\bm{\mu}_i, \ i = 1, \ldots, k\)：
\[\bm{\mu}_i^{'} = \frac{1}{|C_i|}\sum_{\bm{x}\in C_i}\bm{x}_i \]用重新计算的簇中心（均值向量）对簇中心进行更新。
-
如果簇中心没有发生变化，停止算法；否则，并回到步骤 2。
时间复杂度为 \(O(tkn)\)，其中 \(n\) 是样本数，\(k\) 是簇的数目，\(t\) 是算法迭代次数。一般 \(t\) 和 \(k\) 较小，因此时间复杂度近似为 \(O(n)\)。
2.2 算法的缺点
-
对于非凸/非球形的簇，聚类效果不佳。
-
对于各簇中样本规模差异太大、不同密度的簇，聚类效果不佳。
-
最终的聚类结果 受初始簇中心的影响，因此 聚类结果不唯一。
-
对 噪声/离群点很敏感。（因此通常在利用K-Means算法执行聚类分析前，要去除离群点。）
3. \(k\text{-medoids}\)
3.1 算法步骤
-
随机选取 \(k\) 个样本 作为初始的簇中心 \(\bm{\mu}_1, \ldots, \bm{\mu}_k\)。
-
计算剩余的各个样本 \(\bm{x}_j\) 到各个簇中心 \(\bm{\mu}_i\) 的距离。并距离 \(\bm{x}_j\) 找到 最近的簇中心：
\[\lambda_j = \text{argmin}_{i = 1, 2, \ldots, k} d_{ji} \]将 \(\bm{x}_j\) 划分到该簇中：\(C_{\lambda_j} = C_{\lambda_j}\cup \bm{x}_j\)
-
重新计算每个簇的簇中心 \(\bm{\mu}_i, \ i = 1, \ldots, k\)：
找到一个样本点 \(j\)，满足该簇中所有其他点到该样本点 \(j\) 距离之和最小。（称为 \(\text{medoid}\)）
\[j = \text{argmin}_{\bm{x} \in C_i}\sum_{\bm{x}^{'} \in C_i} ||\bm{x} - \bm{x}^{'}||^2 \]用重新计算的簇中心（一个样本点）对簇中心进行更新。
-
如果簇中心没有发生变化，停止算法；否则，并回到步骤 2。
3.2 算法特点
-
对噪声/离群点更鲁棒。但簇的medoid可以削弱离群点的影响。
-
算法的时间复杂度更高，为 \(O(tkn^2)\)。每次重新计算所有簇中心需要枚举所有的样本点，并计算到簇中其他样本点的距离之和，因此是 \(n^2\) 的。
补充
基于 密度的聚类算法（如 \(\text{DBSCAN}\)）能 发现任意形状的簇，且 对噪声/离群点不敏感；
而 基于划分（如 \(k\text{-means}, k\text{-medoids}\)）和基于层次的聚类算法 只能发现 球状簇。
标签：样本,复习,模式识别,聚类,mu,算法,text,bm From： https://www.cnblogs.com/MarisaMagic/p/18260789