The Robotics Institute

Carnegie Mellon Robotics Institute

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract

A two-step procedure that finds natural clusters in geometric point data is described. The first step computes a hierarchical cluster tree minimizing an entropy objective function. The second step recursively explores the tree for a level clustering having minimum description length. Together, these two steps find natural clusters without requiring a user to specify threshold parameters or so-called magic numbers. In particular, the method automatically determines the number of clusters in the input data. The first step exploits a new hierarchical clustering procedure called numerical iterative hierarchical clustering (NIHC). The output of NIHC is a cluster tree. The second step in the procedure searches the tree for a minimum-description-length (MDL) level clustering. The MDL formulation, equivalent to maximizing the posterior probability, is suited to the clustering problem because it defines a natural prior distribution.

Notes

Text Reference

R.S. Wallace and Takeo Kanade, "Finding natural clusters having minimum description length," Proceedings of the 10th International Conference on Pattern Recognition, June, 1990, pp. 438 - 442.

BibTeX Reference

@inproceedings{Kanade_1990_3549,
   author = "R.S. Wallace and Takeo Kanade",
   title = "Finding natural clusters having minimum description length",
   booktitle = "Proceedings of the 10th International Conference on Pattern Recognition",
   pages = "438 - 442",
   month = "June",
   year = "1990",
   volume = "1",
}

The Robotics Institute

Menu