A Lagrangian-based score for assessing the quality of pairwise constraints in semi-supervised clustering
Autor: | Rodrigo Alves Randel, Daniel Aloise, Simon J. Blanchard, Alain Hertz |
---|---|
Rok vydání: | 2021 |
Předmět: |
Computer Networks and Communications
Computer science media_common.quotation_subject computer.software_genre Disease cluster Computer Science Applications Constraint (information theory) symbols.namesake Data point symbols Key (cryptography) Pairwise comparison Quality (business) Data mining Cluster analysis computer Lagrangian Information Systems media_common |
Zdroj: | Data Mining and Knowledge Discovery. 35:2341-2368 |
ISSN: | 1573-756X 1384-5810 |
DOI: | 10.1007/s10618-021-00794-0 |
Popis: | Clustering algorithms help identify homogeneous subgroups from data. In some cases, additional information about the relationship among some subsets of the data exists. When using a semi-supervised clustering algorithm, an expert may provide additional information to constrain the solution based on that knowledge and, in doing so, guide the algorithm to a more useful and meaningful solution. Such additional information often takes the form of a cannot-link constraint (i.e., two data points cannot be part of the same cluster) or a must-link constraint (i.e., two data points must be part of the same cluster). A key challenge for users of such constraints in semi-supervised learning algorithms, however, is that the addition of inaccurate or conflicting constraints can decrease accuracy and little is known about how to detect whether expert-imposed constraints are likely incorrect. In the present work, we introduce a method to score each must-link and cannot-link pairwise constraint as likely incorrect. Using synthetic experimental examples and real data, we show that the resulting impact score can successfully identify individual constraints that should be removed or revised. |
Databáze: | OpenAIRE |
Externí odkaz: |