Entropy-Rate Clustering: Cluster Analysis via Maximizing a Submodular Function Subject to a Matroid Constraint
Entropy-Rate Clustering: Cluster Analysis via Maximizing a Submodular Function Subject to a Matroid Constraint
复制标题
DOI：
10.1109/tpami.2013.107
复制
发表时间：
2014-01
影响因子：
23.6
通讯作者：
Ming-Yu Liu;Oncel Tuzel;Srikumar Ramalingam;R. Chellappa
中科院分区：
文献类型：
--
作者：
Ming-Yu Liu;Oncel Tuzel;Srikumar Ramalingam;R. Chellappa
我们提出了一个新的目标函数聚类。该目标函数由两个部分组成：图上随机游动的熵率和平衡项。熵率有利于形成紧凑和均匀的集群，而平衡功能则鼓励具有相似大小的集群，并惩罚积极分组样本的较大集群。我们提出了一种新的图形结构的图形与数据，并表明，这种结构诱导拟阵-一种组合结构，概括了向量空间中的线性独立的概念。聚类结果由在拟阵约束下最大化目标函数的图拓扑给出。通过利用目标函数的次模性和单调性，我们提出了一个有效的贪婪算法。此外，我们证明了贪婪解的最优性的近似界为1/2。我们验证了所提出的算法在各种基准测试，并显示其竞争力的性能与流行的聚类算法。我们进一步将其应用于超像素分割任务。在伯克利分割数据集上的实验表明，它在所有标准评估指标上都优于最先进的超像素分割算法。
We propose a new objective function for clustering. This objective function consists of two components: the entropy rate of a random walk on a graph and a balancing term. The entropy rate favors formation of compact and homogeneous clusters, while the balancing function encourages clusters with similar sizes and penalizes larger clusters that aggressively group samples. We present a novel graph construction for the graph associated with the data and show that this construction induces a matroid--a combinatorial structure that generalizes the concept of linear independence in vector spaces. The clustering result is given by the graph topology that maximizes the objective function under the matroid constraint. By exploiting the submodular and monotonic properties of the objective function, we develop an efficient greedy algorithm. Furthermore, we prove an approximation bound of 1/2 for the optimality of the greedy solution. We validate the proposed algorithm on various benchmarks and show its competitive performances with respect to popular clustering algorithms. We further apply it for the task of superpixel segmentation. Experiments on the Berkeley segmentation data set reveal its superior performances over the state-of-the-art superpixel segmentation algorithms in all the standard evaluation metrics.