Extracting elite pairwise constraints for clustering
Extracting elite pairwise constraints for clustering
复制标题
提取聚类的精英成对约束
DOI：
10.1016/j.neucom.2012.06.013
复制
发表时间：
2013
期刊：
影响因子：
6
通讯作者：
Xindong Wu
中科院分区：
文献类型：
--
作者：
He Jiang;Zhilei Ren;Jifeng Xuan;Xindong Wu
成对约束下的半监督聚类算法是近年来数据挖掘领域的一个研究热点。由于不同领域专家提供的成对约束可能会相互冲突，因此已经进行了大量的研究工作来评估噪声对半监督聚类的影响。在本文中，我们引入精英成对约束，包括精英必须链接（EML）和精英不能链接（ECL）的约束。与传统的约束相比，EML和ECL约束都需要在每个最优划分（即具有最小准则函数的划分）中得到满足。因此，这些新的约束不会引起冲突。首先，我们证明了获得EML或ECL约束是NP-困难的。然后，提出了一种启发式方法，称为极限交叉，以实现这些新的约束的一小部分。在实际应用中，这种新方法总是可以检索到大量的EML或ECL约束。为了评估极限交叉的有效性，本文还提出了基于多划分和基于距离的方法来生成伪精英成对约束。UCI和合成数据集上进行了大量的实验，使用半监督聚类算法名为COP-KMedoids。实验结果表明，COP-KMedoids在EML和ECL约束下的极限交叉生成可以优于那些在人造约束或没有约束。
Semi-supervised clustering under pairwise constraints (i.e. must-links and cannot-links) has been a hot topic in the data mining community in recent years. Since pairwise constraints provided by distinct domain experts may conflict with each other, a lot of research work has been conducted to evaluate the effects of noise imposing on semi-supervised clustering. In this paper, we introduce elite pairwise constraints, including elite must-link (EML) and elite cannot-link (ECL) constraints. In contrast to traditional constraints, both EML and ECL constraints are required to be satisfied in every optimal partition (i.e. a partition with the minimum criterion function). Therefore, no conflict will be caused by those new constraints. First, we prove that it is NP-hard to obtain EML or ECL constraints. Then, a heuristic method named Limit Crossing is proposed to achieve a fraction of those new constraints. In practice, this new method can always retrieve a lot of EML or ECL constraints. To evaluate the effectiveness of Limit Crossing, multi-partition based and distance based methods are also proposed in this paper to generate faux elite pairwise constraints. Extensive experiments have been conducted on both UCI and synthetic data sets using a semi-supervised clustering algorithm named COP-KMedoids. Experimental results demonstrate that COP-KMedoids under EML and ECL constraints generated by Limit Crossing can outperform those under either faux constraints or no constraints.
登录
查看更多内容
DOI：
10.1137/1.9781611972740.31
发表时间：
2004-06
期刊：
--
影响因子：
--
作者：
Sugato Basu;A. Banerjee;R. Mooney
通讯作者：
Sugato Basu;A. Banerjee;R. Mooney
影响因子：
56.9
作者：
K. Vehkalahti;B. Everitt
通讯作者：
K. Vehkalahti;B. Everitt
影响因子：
2.7
作者：
C. Domeniconi;Jing Peng;B. Yan
通讯作者：
C. Domeniconi;Jing Peng;B. Yan
影响因子：
2.3
作者：
I. Davidson;S. Ravi
通讯作者：
I. Davidson;S. Ravi
DOI：
10.1007/978-3-642-12541-6_9
发表时间：
2011-01-01
期刊：
CONCISE GUIDE TO MARKET RESEARCH: THE PROCESS, DATA, AND METHODS USING IBM SPSS STATISTICS
影响因子：
--
作者：
Mooi, Erik;Sarstedt, Marko
通讯作者：
Sarstedt, Marko