Good Clusterings Have Large Volume
Good Clusterings Have Large Volume
复制标题
DOI：
10.1287/opre.2018.1779
复制
发表时间：
2017-06
期刊：
影响因子：
--
通讯作者：
S. Borgwardt;Felix Happach
中科院分区：
文献类型：
--
作者：
S. Borgwardt;Felix Happach
数据集的聚类是数据分析的核心任务之一。许多聚类算法在实践中表现出良好的性能，而在理论中表现出糟糕的最差情况。主要的例子是最小二乘分配和流行的k均值算法。我们对这种对比很感兴趣，并通过多面体理论来研究它。几种流行的聚类算法可以连接到寻找所谓的有界形状划分多面体的顶点。这些顶点对应于具有非凡分离属性的聚类，特别是允许构建由其所谓的位置定义的分离功率图，这样每个聚类都有自己的单元。首先，我们通过相应顶点的法向锥的体积，定量地测量所有允许为聚类构建分离功率图的站点的空间。这为聚类提供了一个新的质量标准，并解释了为什么好的聚类也是最容易被一些经典算法发现的。其次，我们刻画了有界形分割多面体的边缘。通过这种方法，我们得到了正锥的显式描述。这允许我们计算关于新的质量标准的度量，甚至计算“最稳定”的站点，从而计算“最稳定”的功率图，用于集群的分离。这些计算的硬度取决于与一个顶点相关的边的数量，这可能是指数的。然而，计算工作得到了从结果中获得的大量信息的回报，我们通过一些概念验证计算来强调这些信息。
The clustering of a data set is one of the core tasks in data analytics. Many clustering algorithms exhibit a strong contrast between a favorable performance in practice and bad theoretical worst-cases. Prime examples are least-squares assignments and the popular $k$-means algorithm. We are interested in this contrast and study it through polyhedral theory. Several popular clustering algorithms can be connected to finding a vertex of the so-called bounded-shape partition polytopes. The vertices correspond to clusterings with extraordinary separation properties, in particular allowing the construction of a separating power diagram, defined by its so-called sites, such that each cluster has its own cell. First, we quantitatively measure the space of all sites that allow construction of a separating power diagram for a clustering by the volume of the normal cone at the corresponding vertex. This gives rise to a new quality criterion for clusterings, and explains why good clusterings are also the most likely to be found by some classical algorithms. Second, we characterize the edges of the bounded-shape partition polytopes. Through this, we obtain an explicit description of the normal cones. This allows us to compute measures with respect to the new quality criterion, and even compute "most stable" sites, and thereby "most stable" power diagrams, for the separation of clusters. The hardness of these computations depends on the number of edges incident to a vertex, which may be exponential. However, the computational effort is rewarded with a wealth of information that can be gained from the results, which we highlight through some proof-of-concept computations.