Clustering Pairwise Distances with Missing Data: Maximum Cuts Versus Normalized Cuts
Clustering Pairwise Distances with Missing Data: Maximum Cuts Versus Normalized Cuts
复制标题
DOI：
10.1007/11893318_21
复制
发表时间：
2006-10
期刊：
影响因子：
--
通讯作者：
J. Poland;T. Zeugmann
中科院分区：
文献类型：
--
作者：
J. Poland;T. Zeugmann
基于数据的成对相似性矩阵（核矩阵）的聚类算法是广泛已知和使用的，特别流行的一类是谱聚类算法。相比之下，算法与成对距离矩阵的研究很少聚类。这是令人惊讶的，因为在许多应用中，距离是直接给定的，计算相似性涉及另一个容易出错的步骤，因为内核必须选择适当的，尽管计算成本很低。本文在Frieze和Jerrum工作的基础上，提出了一种基于两两距离图的最大k割的SDP松弛的聚类算法。我们比较了该算法与俞和施的算法的基础上的谱松弛的norm-k-cut。此外，我们提出了一个简单的启发式处理丢失的数据，即，一些成对的距离或相似性是未知的情况下。我们评估的任务上的聚类自然语言术语与谷歌距离，语义距离最近推出的Cilibrasi和Vitanyi，使用相对频率计数从WWW查询和Kolmogorov复杂性理论的基础上的算法。
Clustering algorithms based on a matrix of pairwise similarities (kernel matrix) for the data are widely known and used, a particularly popular class being spectral clustering algorithms. In contrast, algorithms working with the pairwise distance matrix have been studied rarely for clustering. This is surprising, as in many applications, distances are directly given, and computing similarities involves another step that is error-prone, since the kernel has to be chosen appropriately, albeit computationally cheap. This paper proposes a clustering algorithm based on the SDP relaxation of the max-k-cut of the graph of pairwise distances, based on the work of Frieze and Jerrum. We compare the algorithm with Yu and Shi's algorithm based on spectral relaxation of a norm-k-cut. Moreover, we propose a simple heuristic for dealing with missing data, ie, the case where some of the pairwise distances or similarities are not known. We evaluate the algorithms on the task of clustering natural language terms with the Google distance, a semantic distance recently introduced by Cilibrasi and Vitanyi, using relative frequency counts from WWW queries and based on the theory of Kolmogorov complexity.