Algorithms for Multi-Sample Cluster Analysis
Fahad Almutairi · 2007
In this study, we develop algorithms to solve the Multi-Sample Cluster Analysis (MSCA) problem. This problem arises when we have multiple samples and we need to nd the statistical model that best ts the cluster structure of these samples. One important area among others in which our algorithms can be used is international market segmentation. In this area, samples about customerspreferences and characteristics are collected from di¤erent regions in the market. The goal in this case is to join the regions with similar customerscharacteristics in clusters (segments). We develop branch and bound algorithms and a genetic algorithm. In these algorithms, any of the available information criteria (AIC, CAIC, SBC, and ICOMP) can be used as the objective function to be optimized. Our algorithms use the Clique Partitioning Problem (CPP) formulation. They are the rst algorithms to use information criteria with the CPP formulation. When the branch and bound algorithms are allowed to run to completion, they converge to the optimal MSCA alternative. These methods also proved to nd good solutions when they were stopped short of convergence. In particular, we develop a branching strategy which uses a look-ahead technique. We refer to this strategy as the complete adaptive branching strategy. This strategy makes the branch and bound algorithm quickly search for the optimal solution in multiple branches of the enumeration tree before using a depth rst branching strategy. In computational tests, this methods performance was superior to other branching methods as well as to the genetic algorithm.