A principled and flexible framework for finding alternative clusterings

ABSTRACT

The aim of data mining is to find novel and actionable insights in data. However, most algorithms typically just find a single (possibly non-novel/actionable) interpretation of the data even though alternatives could exist. The problem of finding an alternative to a given original clustering has received little attention in the literature. Current techniques (including our previous work) are unfocused/unrefined in that they broadly attempt to find an alternative clustering but do not specify which properties of the original clustering should or should not be retained. In this work, we explore a principled and flexible framework in order to find alternative clusterings of the data. The approach is principled since it poses a constrained optimization problem, so its exact behavior is understood. It is flexible since the user can formally specify positive and negative feedback based on the existing clustering, which ranges from which clusters to keep (or not) to making a trade-off between alternativeness and clustering quality.

REFERENCES

• 1: A. Asuncion and D. Newman. UCI machine learning repository, 2007.
• 2: Eric Bae , James Bailey, COALA: A Novel Approach for the Extraction of an Alternate Clustering of High Quality and High Dissimilarity, Proceedings of the Sixth International Conference on Data Mining, p.53-62, December 18-22, 2006 [doi>10.1109/ICDM.2006.37]
• 3: Tom Coleman , James Saunderson , Anthony Wirth, Spectral clustering with inconsistent advice, Proceedings of the 25th international conference on Machine learning, p.152-159, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390176]
• 4: Ying Cui , Xiaoli Z. Fern , Jennifer G. Dy, Non-redundant Multi-view Clustering via Orthogonalization, Proceedings of the 2007 Seventh IEEE International Conference on Data Mining, p.133-142, October 28-31, 2007 [doi>10.1109/ICDM.2007.94]
• 5: Ian Davidson , Zijie Qi, Finding Alternative Clusterings Using Constraints, Proceedings of the 2008 Eighth IEEE International Conference on Data Mining, p.773-778, December 15-19, 2008 [doi>10.1109/ICDM.2008.141]
• 6: Ian Davidson , S. S. Ravi, The complexity of non-hierarchical clustering with instance and cluster level constraints, Data Mining and Knowledge Discovery, v.14 n.1, p.25-61, February 2007 [doi>10.1007/s10618-006-0053-7]
• 7: Ian Davidson , S. S. Ravi, Intractability and clustering with constraints, Proceedings of the 24th international conference on Machine learning, p.201-208, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273522]
• 8: Ian Davidson , S. S. Ravi , Martin Ester, Efficient incremental constrained clustering, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281221]
• 9: David Gondek , Thomas Hofmann, Non-Redundant Data Clustering, Proceedings of the Fourth IEEE International Conference on Data Mining, p.75-82, November 01-04, 2004
• 10: P. Jain, R. Meka, and I. S. Dhillon. Simultaneous unsupervised learning of disparate clusterings. In SDM '08: Proceedings of the SIAM International Conference on Data Mining, pages 858--869, 2008.
• 11: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Experimentation

Keywords:
clustering