Clustering Algorithm And Application Based On Combinatorial Optimization

In recent years, clustering analysis is widely implemented in data mining. It could be used as a stand-alone tool to analyze the distribution of data, a pretreatment for other algo-rithms, and a detection of outliers, etc.In this thesis, we introduce the classical clustering methods, such as division method, hi-erarchical analysis method and density method. We present two clustering algorithms for data mining, KCG-KM algorithm and HS-KM algorithm, based on the algorithms of facility loca-tion problem in combinatorial optimization and K-means algorithm in clustering analysis. We compare the two algorithms by numerical stimulations and show that they outperform K-means algorithm. HS-KM algorithm increases average DI by12.9%and KCG-KM algo-rithm by7.32%. HS-KM algorithm reduces average CS by4.95%and KCG-KM algorithm by4.53%. HS-KM algorithm reduces average computation time by26.6%.Since top-down divisive method is rare in hierarchical clustering, we introduce two new divisive algorithms, MCG algorithm and GW algorithm, from Max-cut problem in combina-toria optimization. We find that MCG algorithm could produce a partition within computation time O(n2), while MCG algorithm is exponential. Numerical simulation also verifies that MCG algorithm is faster and suitable for large-scale data clustering. However. GW algorithm could distinguish different distributed data points from data sets in various structures.Finally, we apply KCG algorithm and GW algorithm to the clustering of bank customers. All customers are divided into eight classes. We analyze characteristics of these classes. Then we present appropriate asset allocation and cross-sell products for each classes.