目录
聚类
聚类方法在于寻找数据中的集群（clusters），在同一个集群中的数据在某些方面更加相似。这同时也是对数据的一种压缩，因为我们使用了更小的集合—集群—来表示更大的数据。也可以理解为寻找有用特征的一种方式，如果一系列数据可以很好地被集群中心点表示，那么很有可能我们发现了更好的特征。
为了获得聚类算法，我们先要明确数据之间的相似度的概念，一般用数据之间的距离来表示。假设数据分布于特征空间 \(\mathcal X=\mathbb R^D\)，那么我们需要一个函数来计算两个数据在该空间的距离，一般使用欧氏距离 \(\vert\vert\pmb x_1-\pmb x_2\vert\vert_2=\sqrt{\sum_{i=1}^D(x_1^{(i)}-x_2^{(i)})^2}\)，但对于某些特殊的数据也使用其他距离函数。
K-均值聚类
K-均值聚类是一个迭代算法，简单并且可解释。将所有数据用 k 个类（cluster，或者称为集群）表示，这 k 个集群的中心点用所有属于这个集群的数据的均值表示，这也是为什么它被命名为均值聚类。
推导K-均值算法
设 \(\lbrace{\pmb\mu_i}\rbrace_{i=1}^k\) 为 k 个中心点，\(\lbrace r_i\rbrace_{i=1}^n\) 为 n 个数据属于哪些类，将损失函数设为所有样本与其所属类的中心的欧氏距离之和。
\[\begin{align*} J(\lbrace\pmb x_i\rbrace_{i=1}^n;\lbrace\pmb\mu_i\rbrace_{i=1}^n,\lbrace r_i\rbrace_{i=1}^n)&=\sum_{i=1}^n\vert\vert\pmb x_i-\pmb\mu_{r_i}\vert\vert^2_2\\ &=\sum_{i=1}^n(\pmb x_i-\pmb\mu_{r_i})^T(\pmb x_i-\pmb\mu_{r_i})\\ \hat r_i&=\underset{r}{\arg\min}\vert\vert\pmb x_i-\pmb\mu_r\vert\vert^2_2\\ \nabla_{\pmb\mu_j}J&=\sum_{i=1}^n\nabla_{\pmb\mu_j}(\pmb x_i-\pmb\mu_{r_i})^T(\pmb x_i-\pmb\mu_{r_i})\\ &=2\sum_{i=1}^nI\lbrace j=r_i\rbrace(\pmb\mu_j-\pmb x_i)=0\\ \hat{\pmb\mu}_j&={\sum_{i=1}^nI\lbrace j=r_i\rbrace\pmb x_i\over\sum_{i=1}^nI\lbrace j=r_i\rbrace} \end{align*} \]其中 \(I\) 为指示器函数，\(I\lbrace A\rbrace=\begin{cases}1&\text{if }A\\0&\text{else}\end{cases}\)。
使得损失函数 \(J(\lbrace\pmb x_i\rbrace_{i=1}^n;\lbrace\pmb\mu_i\rbrace_{i=1}^n,\lbrace r_i\rbrace_{i=1}^n)\) 获得极小值的结果由很多种，这说明如果使用随机初始化每个样本的集群，那么每次获得的聚类结果都很可能不一样。
实现
-
初始化 k 个不同的中心点 \(\pmb\mu^{(1)},\pmb\mu^{(2)},\dots,\pmb\mu^{(k)}\)；
-
重复迭代直到中心点不在变动
- 每个样本分配到最近的中心点 \(\pmb\mu^{(i)}\)，表明它属于类 \(i\)；
- 每个中心点 \(\pmb\mu^{(i)}\) 被更新为类 \(i\) 中所有样本的均值。
def k_means(a:np.ndarray, k:int, clusters:np.ndarray = None):
"""take an NxD numpy matrix as input"""
n, d = a.shape
if clusters is None:
clusters = np.emptys(size=(k, d))
responses = np.random.randint(k, size=(n, ))
changed = True
while changed:
changed = False
for i in range(k):
clusters[i] = a[responses == i].average(axis=0)
for j in range(n):
distances = np.fromiter((
(a[j] - clusters[i]) ** 2
).sum() for i in range(k))
if (response := np.argmin(distances)) != responses[j]:
responses[j] = response
changed = True
return responses, clusters
选择超参数 k
从压缩的角度上看，k 的选择好比压缩率和保真度之间的权衡（trade-off），更高的 k 对原数据的保留程度更高，但是中心点数目更多。
一种简单的方法是通过采用不同的 k 对数据进行聚类之后，选择两项表现综合结果最好的 k 值。如果你想获得更具有代表性的特征的话，那么建议使用更大的 k，如果想要通过聚类观察数据的话应该使用较小的 k。
通过损失函数的变化率选择最好的 k 值
不断增大 k，直到增大 k 后减少的损失降低到某一阈值以下后选择这个 k。即选择满足损失函数 \(J_k\le J_{k+1}+threshold\)。
通过集群分散度（within-cluster dispersion）选择最好的 k 值
\(D_c\) 为集群 \(c\) 的分散度，是集群中所有样本对的欧氏距离；\(W_k\) 为所有集群的归一化分散度。
\[\begin{align*} D_c&=\sum_{i=1}^n\sum_{j=1}^nI\lbrace r_i=r_j=c\rbrace\vert\vert\pmb x_i-\pmb x_j\vert\vert^2\\ W_k&=\sum_{c=1}^k{D_c\over2\sum_{i=1}^nI\lbrace r_i=c\rbrace}=\sum_{c=1}^k{\sum_{i=1}^n\sum_{j=1}^nI\lbrace r_i=r_j=c\rbrace\vert\vert\pmb x_i-\pmb x_j\vert\vert^2\over2\sum_{i=1}^nI\lbrace r_i=c\rbrace} \end{align*} \]系数 2 是因为 \(D_c\) 中所有样本对计算了两次。
这一数值体现了每个集群的离散程度。一般随着 k 的增加这一数值会变小，聚类效果越好这一数值也会减小。
但是为了真正地衡量聚类效果，我们需要比较聚类之前的数据和聚类之后的数据之间的差异，即计算间隙统计（gap statistic）
\[\begin{align*} \mathrm{Gap}_N(k)=\mathbb E_{\mathrm{null}}[\ln W_{k,\mathrm{null}}]-\ln W_k \end{align*} \]选择最佳的 \(k^*\) 满足 \(k^*=\underset{k}{\arg\max}\,\mathrm{Gap}_N(k)\)。其中，\(\mathbb E_{\mathrm{null}}\) 为我们寻找的一个空分布（null distribution，或称为参考分布 reference distribution），这个空分布是用来生成参考数据（reference data）用的。空分布的选择就是当数据中实际上并不存在“不同类”时候选择的分布。
换句话说，我们假设数据中有不同的类，比如水仙花数据中有茎叶长度的数据，通过这一数据有可能分出几个类，为了选择最好的类的个数 k，那么将茎和叶的长度分别归一化为均值 0 方差 1 的数据后，选择空分布为标准二元高斯分布 \(\mathcal N(\pmb0,\pmb I_2)\)。于是前者是隐含类的差异的数据；后者没有（或说只有 1 个类），因为它仅仅是普通的高斯分布。通常会使用多元高斯分布或者多元平均分布，更好的空分布选择请参考 Reference。
图中蓝色数据为要求的样本的数据，可以观察到大约包含三个类；红色数据为选择的空分布产生的数据，没有明显的类的差异。
为了直观化这一方法的合理性，考虑如果数据中真的有 K 个类的话，那么可以想见：\(W_k\) 将在 \(k\le K\) 时下降较快，而在 \(k>K\) 之后下降较慢。对于我们寻找到的空分布则 \(W_{k,\mathrm{null}}\) 会以一个比较平稳的速率关于 \(k\) 下降。那么可以通过寻找 \(\mathrm{Gap}_N(k)\) 的最大值，即两者之间的差异来实现寻找最合适的 \(k\)。
选择完空分布之后，从该空分布中选择 \(N\) 个数据再进行聚类得到相应的分散度 \(W_{k,\mathrm{null}}\)，求其期望则得到 \(\mathbb E_{\mathrm{null}}[\ln W_{k,\mathrm{null}}]\)。但由于这一期望实际上是不可求得的，可以通过几次抽样和一个调整值来近似计算。用蒙特卡罗方法从空分布中获得数据，令 \(B\) 为抽样次数，\(\mathrm{sd}\) 为结果的标准差，那么获得一个误差 \(s_k\)，最终结果需要满足
\[\begin{align*} \hat{\mathbb E}_{\mathrm{null}}[\ln W_{k,\mathrm{null}}]&=\frac1B\sum_{b=1}^B\ln W_{k,\mathrm{null},b}\\ \mathrm{sd}(k)&=\sqrt{\frac1B\sum_{b=1}^B\left(\ln W_{k,\mathrm{null},b}-\hat{\mathbb E}_{\mathrm{null}}[\ln W_{k,\mathrm{null}}]\right)^2}\\ s_k&=\sqrt{{1+B\over B}}\mathrm{sd}(k)\\ \mathrm{Gap}_N(k)&\ge\mathrm{Gap}_N(k+1)-s_{k+1} \end{align*} \]K-均值聚类++算法
这一算法相比标准得的 k-均值聚类可以获得更好的性能
- 在样本中随机选择一个中心点；
- 选择离现有中心点最远的点作为新的中心点，直到获得 k 个中心点；
- 使用标准的 k-均值聚类处理这 k 个中心点。
def k_means_pp(a:np.ndarray, k:int):
"""take an NxD numpy matrix as input"""
n, d = a.shape
clusters = np.emptys(size=(k, d))
distances = np.emptys(size=(n, ))
clusters[0] = a[np.random.randint(n, size=(1, ))]
for i in range(1, k):
for j in range(n):
distances[j] = min(((a[j] - clusters[c]) ** 2).sum()
for c in range(i))
clusters[i] = a[distances.argmax()]
return k_means(a, k, clusters)
从直观上，这一算法使得每个中心点都被初始化得比较分离。
K-中心点算法
def k_medoids(a:np.ndarray, k:int):
"""take an NxD numpy matrix as input"""
n, d = a.shape
responses = np.random.randint(k, size=(n, ))
while True:
for i in range(k):
chosen = a[responses == i]
distances = np.abs(
chosen.reshape(1, *chosen.shape).transpose(1,0,2) - chosen
).sum(axis=(1, 2))
clusters[i] = chosen[np.argmin(distances)]
new_responses = np.abs(
(a.reshape(1, *a.shape).transpose(1,0,2) - clusters)
).sum(axis=-1).argmin(axis=-1)
if (new_responses == responses).all():
return responses, clusters
responses = new_responses
和均值算法的不同在于 for i in range(k) 这一段（更新中心点），主要是中心点的选择方式；for j in range(n) 这一段（更新样本所属类）是相同的，但是运用了一下 numpy 的广播机制。
Reference
Finding the K in K-Means Clustering
标签：vert,sum,mu,pmb,聚类,mathrm From： https://www.cnblogs.com/violeshnv/p/16832225.html