图 书 馆
约束驱动的聚类Constraint-Driven Clustering |
|
| 课程网址: | http://videolectures.net/kdd07_ge_cdc/ |
| 主讲教师: | Rong Ge |
| 开课单位: | 西蒙弗雷泽大学 |
| 开课时间: | 2007-09-14 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | Clustering methods can be either data-driven or need-driven. Data-driven methods intend to discover the true structure of the underlying data while need-driven methods aims at organizing the true structure to meet certain application requirements. Thus, need-driven (e.g. constrained) clustering is able to find more useful and actionable clusters in applications such as energy aware sensor networks, privacy preservation, and market segmentation. However, the existing methods of constrained clustering require users to provide the number of clusters, which is often unknown in advance, but has a crucial impact on the clustering result. In this paper, we argue that a more natural way to generate actionable clusters is to let the application-specific constraints decide the number of clusters. For this purpose, we introduce a novel cluster model, Constraint-Driven Clustering (CDC), which finds an a priori unspecified number of compact clusters that satisfy all user-provided constraints. Two general types of constraints are considered, i.e. minimum significance constraints and minimum variance constraints, as well as combinations of these two types. We prove the NP-hardness of the CDC problem with different constraints. We propose a novel dynamic data structure, the CD-Tree, which organizes data points in leaf nodes such that each leaf node approximately satisfies the CDC constraints and minimizes the objective function. Based on CD-Trees, we develop an efficient algorithm to solve the new clustering problem. Our experimental evaluation on synthetic and real datasets demonstrates the quality of the generated clusters and the scalability of the algorithm. |
| 关 键 词: | 聚类方法; 数据驱动; 底层数据 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2019-05-08：cwx |
| 阅读次数: | 48 |