Kernel k-Groups via Hartigan's Method.
Kernel k-Groups via Hartigan's Method.
复制标题
DOI：
10.1109/tpami.2020.2998120
复制
发表时间：
2021-12
影响因子：
23.6
通讯作者：
Vogelstein JT
中科院分区：
文献类型：
--
作者：
Franca G;Rizzo ML;Vogelstein JT
能量统计是由Székely在80年代受到经典力学中牛顿引力势的启发而提出的，它提供了一个无模型的假设检验。在其原始形式中，能量统计是在欧几里得空间中制定的。最近，它被推广到负型度量空间。在本文中，我们考虑一个配方的聚类问题，使用加权版本的能量统计空间的负型。我们表明，这种方法导致一个二次约束的二次规划在相关的内核空间，建立连接与图分割问题和机器学习的内核方法。为了找到这样的优化问题的局部解，我们提出了核k-群，这是一个扩展的Hartigan的方法，核空间。核k-组比谱聚类更便宜，并且具有与核k-均值（基于劳埃德启发式）相同的计算成本，但我们的数值结果显示出更好的性能，特别是在更高的维度上。此外，我们验证了核k-群在稀疏随机块模型中社区检测的有效性，该模型在多个科学领域有着迷人的应用。
Energy statistics was proposed by Székely in the 80’s inspired by Newton’s gravitational potential in classical mechanics and it provides a model-free hypothesis test for equality of distributions. In its original form, energy statistics was formulated in Euclidean spaces. More recently, it was generalized to metric spaces of negative type. In this paper, we consider a formulation for the clustering problem using a weighted version of energy statistics in spaces of negative type. We show that this approach leads to a quadratically constrained quadratic program in the associated kernel space, establishing connections with graph partitioning problems and kernel methods in machine learning. To find local solutions of such an optimization problem, we propose kernel k-groups, which is an extension of Hartigan’s method to kernel spaces. Kernel k-groups is cheaper than spectral clustering and has the same computational cost as kernel k-means (which is based on Lloyd’s heuristic) but our numerical results show an improved performance, especially in higher dimensions. Moreover, we verify the efficiency of kernel k-groups in community detection in sparse stochastic block models which has fascinating applications in several areas of science.