Constrained classification: The use of a priori information in cluster analysis

In many classification problems, one often possesses external and/or internal information concerning the objects or units to be analyzed which makes it appropriate to impose constraints on the set of allowable classifications and their characteristics. CONCLUS, or CONstrained CLUStering, is a new methodology devised to perform constrained classification in either an overlapping or nonoverlapping (hierarchical or nonhierarchial) manner. This paper initially reviews the related classification literature. A discussion of the use of constraints in clustering problems is then presented. The CONCLUS model and algorithm are described in detail, as well as their flexibility for use in various applications. Monte Carlo results are presented for two synthetic data sets with appropriate discussion of the resulting implications. An illustration of CONCLUS is presented with respect to a sales territory design problem where the objects classified are various Forbes-500 companies. Finally, the discussion section highlights the main contribution of the paper and offers some areas for future research.We wish to thank C. Mallows and J. D. Carroll for some helpful technical discussion and L. Clark and D. Art for their valuable computer assistance. We also wish to thank H. Pollak, R. Gnanadesikan, and J. Kettenring for their thorough reviews of a previous draft of this paper. Finally, we acknowledge helpful comments of the editor and two anonymous reviewers.