Constraint-driven clustering

摘要: Clustering methods can be either data-driven or need-driven. Data-driven intend to discover the true structure of underlying data while need-driven aims at organizing meet certain application requirements. Thus, (e.g. constrained) clustering is able find more useful and actionable clusters in applications such as energy aware sensor networks, privacy preservation, market segmentation. However, existing constrained require users provide number clusters, which often unknown advance, but has a crucial impact on result. In this paper, we argue that natural way generate let application-specific constraints decide clusters. For purpose, introduce novel cluster model, Constraint-Driven (CDC), finds an priori unspecified compact satisfy all user-provided constraints. Two general types are considered, i.e. minimum significance variance constraints, well combinations these two types. We prove NP-hardness CDC problem with different propose dynamic structure, CD-Tree, organizes points leaf nodes each node approximately satisfies minimizes objective function. Based CD-Trees, develop efficient algorithm solve new problem. Our experimental evaluation synthetic real datasets demonstrates quality generated scalability algorithm.