简介
AAAI19，一篇关于聚类的文章。
研究的是聚类时，$k$ 的值怎么确定。之前对这个也有点兴趣，看了一下，作下记录。
主要转载以下文章，还有自己一些想法：
正文
本文一作 Amber Srivastava 现在是伊利诺伊大学厄巴纳香槟分校机械工程系博士生，他的主要研究方向是优化理论，聚类算法，计算机辅助设计，控制系统等。
聚类算法是在各个领域都被广泛运用的一种算法，特别是学习过统计的同学对此一定非常熟悉，通常，在聚类算法中需要给定聚类数量，即聚类数量是一个超参数。而由于在实际运用中这个值通常是不确定的，往往需要对不同聚类数量的拟合结果进行比较来确定最佳聚类数量，常用的标准有 BIC、AIC，X 均值等。本文作者提出了 persistence 的概念，作为衡量聚类结果的一个新的标准。
从作者的描述看来，这一概念的提出与分辨率的概念有直接关系。因为类（cluster）的概念可以与查看数据集的分辨率比例相关联。例如，两个极端情况下，整个数据集可以被视为一个类，每个数据点自身也可以被视为一个类。这里作者给出了一个例子，图 5 中的数据是由 9 个高斯分布生成的，分布在三个超级集群（super cluster）内。如果我们选择的分辨率非常低，如图 5（a1），整个数据集中的任意两个点不可区分，那么整个数据集将被视为单个类。如果我们选择半径 $r_1$ 的分辨率比例，如图 5（a2）所示，那么每个超级集群内的点是无法区分的，但三个超级集群之间彼此可分。即在此分辨率级别，数据集仅包含三个聚类。再进一步提高图 5（a2）中的分辨率范围后，九个高斯分布的数据点变得彼此不同，并且我们能够识别数据集中的九个聚类。
图 5：对聚类与分辨率之间关系的例证
很显然，随着分辨率的变化，聚类结果也在改变。有一些聚类结果在不同的分辨率下都是最优的，有一些则不是。如在图 5（a1）中，三个超级聚类对于在很广范围的分辨率下都是持久，如每个周围的蓝色环的厚度所示。另一方面，九个高斯分布周围的绿色环相对较薄，表明识别所有九个高斯簇的聚类解决方案相对较不持久。
作者认为在大范围分辨率下都存在的聚类结果是数据真实聚类数量的一种体现，从这里出发，设计了名为 persistence 的标准使得其能衡量聚类结果相对与分辨率的稳健性。
给定数据集 $X = { x_i : x_i \in R^d, 1<= i <= N}$ ，试图将其 $N$ 个数据点聚类到 $k$ 个类中。这一问题可以被视作一个 facility location problem（FTP），即试图放置 facility $Y = { y_j : y_j \in R^d, 1<= j <= k}$ 使得数据点与其最近 facility 之间的累积距离最小——这一思想在经典的 k-means 算法中也出现过。在 FLP 问题中，聚类问题编程求解以下优化问题：
其中 $p_i$ 是已知的 $x_i$ 的权重，常取 1/N，$d(x_i, y_i)$ 是点 $x_i$ 和 $y_j$ 之间的距离函数，常设置为欧拉距离。作者将$\min \limits_{1<=j<=k} d(x_i, y_j)$ 近似为 $ - 1/ \beta log \sum_{j=1} ^k \exp^{-\beta d(x_i, y_j)}$，因此上文中的优化问题被近似成：
参数 $\beta$ 决定了 $F$ 对 $D$ 的近似程度。当 $\beta$ 接近无穷大，$F$ 会无限趋近于 $D$；而当 $\beta$ 接近于 $0$，F 则不能很好的近似 $D$。
这里插一句：
一开始看到，聚类的目标为 $D$，而当 $\beta$ 接近无穷大时，$F$会无限趋近于 $D$，那为什么不将 $\beta$ 直接取无穷，让 $F$ 趋近于 $D$ 呢？
这是因为，$D$ 虽说是聚类的目标问题，但是其中并没有考虑聚类的类别个数；而 $F$ 的 $\beta$ 在 0 与无穷之间选取，也是为了平衡 $D$ 与聚类的类别个数之间的关系。
在 DA 算法中，$F$ 被称为 free-energy function，$β$被称为退火参数。给定 $\beta$ 的情况下，$F$ 的极小值可以通过对 $Y_j$ 求偏导得到的：
到目前为止，本文的内容都是对现有理论的描述。有趣的是，作者随后论证了退火参数β如何可以作为分辨率的度量。
当 $\beta$ 很小时，对数据集内的任意两个点 $x_1$ ，$x_2$ ，$\exp^{\beta d(x_1, y_j} \approx \exp^{\beta d(x_2, yj}$，即这两点是无法区分的。因此，在低 $\beta$ 值时，所建立的优化函数无法区分任意两点，整个数据集将被视为单个集群。随着 $\beta$ 值的增加，最初属于同一群集两个不同点，变得足够可分。当 $\beta$ 趋于无穷大，数据集的每一个点都与其他点很不相同，每一个点都将被视为一个单个的集群。即， $\beta$ 是分辨率的度量， $\text{log}\beta$ 则是分辨率范围的度量。
作者由此定义了 persistence 的概念——在 $\beta$ 值的一定范围内，最小化 $F$ 的 $\mathcal{Y}$ 值应该保持不变。因此，有 $k$ 个集群的聚类结果的 persistence 可以写作：
其中 $\beta_k$ 是类的数量从 $k-1$ 增加到 $k$ 的分辨率。数据集真正的类的数量 $k_t$ 可以通过求得 $v(k)$ 的最大值得到。$\beta_k$ 的在欧式距离情况下解析解，由于篇幅限制这里不赘述，感兴趣的读者可以去论文中查看。
图 5（a3）和（b3）是在图 5（a1）和（b1）计算 persistence 的一个例子，可以看到，对任何 k 不等于 3 和 9 的 k 值, $log \overline{\beta_3} - log \overline{\beta_2} >> log \overline{\beta_k} - log \overline{\beta_{k-1}}$ 和 $log \overline{\beta_9} - log \overline{\beta_8} >> log \overline{\beta_k} - log \overline{\beta_{k-1}}$ 都成立。另外，我们还可以观察到在图 5（a1）数据上，$log \overline{\beta_3} - log \overline{\beta_2} > log \overline{\beta_9} - log \overline{\beta_8}$，说明选择 3 个类比选择 9 个类更加合适，而在图 5（b1）数据上则相反。这与我们的观察相符。
作者也给出了 persistence 在非线性可分数据下的计算方法——选择一个 kernel function 将数据从低维投射到高维，由于显式地定义 kernel function 是很困难的，这里使用了在 svm 中也出现了的 kernel trick。文章中给出了 persistence 在 spherical clusters 等非线性可分数据上的结果。
图 6 给出了所使用的测试数据。图 6（a）是 4 个低方差高斯分布，图 6（b）是 4 个高方差高斯分布，图 6（c）和图 6（d）是合成数据 u，真正的类分别为 8 和 15；图 6（e）和图 6（f）则是有 3 类的 spherical clusters。
图 6：在不同数据上计算 persistence
可以看到利用 persistence 能够准确的预测真正的聚类数，作者在一系列真实数据上所得到的结果也印证了这一点。这篇论文所提出的算法从概念上易于理解，在理论上十分巧妙地将 DA 算法的退火参数设计为分辨率从而自然的得到 persistence 的计算公式。log 的使用可以带来一定的计算优势，特别是当数据集的大小 $N$ 增加时。并且，利用 kernel trick 该算法可以轻易扩展到非线性可分的情况。有一点遗憾的是如果能够看到算法在更高维和更多数据类型（如图像数据）上的表现就更好了。另外是由于 $\beta_k$ 的求解涉及到海森函数，作者限定了距离函数为欧拉距离以得到具体的解析解，而没有涉及更一般的解。
总结
文章提出的算法简单清晰，但是个人感觉有些啰嗦，太多的话反倒将读者搞晕了。
文章的算法虽然效果很好，但是简单来说，是设置了一个评判标准，之后遍历所有的 $k$ 进行聚类尝试，从聚类的结果再来选取出最优 $k$。如果能够不用对每个 $k$ 都进行聚类，直接在一开始能够对数据点 $X$ 的分布进行分析计算，从而确定出 $k_t$，那是最好的。
