图 书 馆
柔性约束谱聚类Flexible Constrained Spectral Clustering |
|
| 课程网址: | http://videolectures.net/kdd2010_wang_fcsc/ |
| 主讲教师: | Xiang Wang |
| 开课单位: | 加州大学 |
| 开课时间: | 2010-10-01 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | Constrained clustering has been well-studied for algorithms like K-means and hierarchical agglomerative clustering. However, how to encode constraints into spectral clustering remains a developing area. In this paper, we propose a flexible and generalized framework for constrained spectral clustering. In contrast to some previous efforts that implicitly encode Must-Link and Cannot-Link constraints by modifying the graph Laplacian or the resultant eigenspace, we present a more natural and principled formulation, which preserves the original graph Laplacian and explicitly encodes the constraints. Our method offers several practical advantages: it can encode the degree of belief (weight) in Must-Link and Cannot-Link constraints; it guarantees to lower-bound how well the given constraints are satisfied using a user-specified threshold; and it can be solved deterministically in polynomial time through generalized eigendecomposition. Furthermore, by inheriting the objective function from spectral clustering and explicitly encoding the constraints, much of the existing analysis of spectral clustering techniques is still valid. Consequently our work can be posed as a natural extension to unconstrained spectral clustering and be interpreted as finding the normalized min-cut of a labeled graph. We validate the effectiveness of our approach by empirical results on real-world data sets, with applications to constrained image segmentation and clustering benchmark data sets with both binary and degree-of-belief constraints. |
| 关 键 词: | 约束聚类; 拉普拉斯算子; 置信度 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2021-01-31：nkq |
| 阅读次数: | 80 |