0-1 Semidefinite Programming for Cluster Analysis with Application to Customer Segmentation

Abstract

<p>In general, clustering involves partitioning a give data set into subsets based on the closeness or similarity among the data. Clustering analysis has been widely used in many applications arising from different disciplines, including market analysis, image segmentation, pattern recognition and web mining.</p> <p>Recently, a new optimization model, the so called 0-1 semidefinite programming( SDP) has been introduced by Peng and Xia in [2]. It has been proved that several scenarios of clustering, such as classical K-means clustering, normalized-cut clustering, balanced clustering and semi-supervised clustering can be embedded into the 0-1 SDP model.</p> <p>In this thesis, we try to extend the 0-1 SDP model to the scenario of weighted K-means clustering, where the instances in the data set are associated with some weights indicating the importance of the instance. We also develop a hierarchical approach to attack the unified 0-1 SDP model, in which each binary separation is achieved by the refined weighted K-means method in one dimensional space. Moreover, we apply the approach developed in this thesis to a particular industrial application, where the task is to extract a model to predict the children information of customers based on their buying behaviors. During the process of the model building, clustering analysis was applied as the first step to group customers with similar children information, and then the link between the segmentation of customers and their shopping behaviors was discovered.</p> <p>Numerical results based on our approach are reported in the thesis as well.</p>