Clustering through simulated annealing using measurements of extremity—the SAME heuristic

Abstract

Data clustering is commonly used to analyze data in numerous fields. This thesis proposes a new clustering measure, the extremity measure. The extremity measure uses two components: the extreme distance, which favors larger clusters, and the central distance, which encourages smaller clusters. By balancing these two components, the extremity measure successfully quantifies how good a clustering solution is. In this thesis, the extreme distance attempts to estimate how extreme a point is from its remaining cluster counterparts by using linear programming. This linear program, called the Extreme Distance Linear Program (EDLP) estimates how close each point is to the convex hull of the remaining cluster points. This thesis also proposes a new clustering heuristic called the Simulated Annealing using Measurements of Extremity (SAME) heuristic. SAME takes a current clustering solution and applies move, split, and dissolve operations to modify, and hopefully improve, the current clustering solution. SAME probabilistically chooses which of these operations to apply. These operations are based the characteristics of each cluster. SAME uses concepts from simulated annealing to decide whether a tested modification should be accepted. SAME is applied to various benchmark data sets and tested against an implementation of the k-means clustering algorithm, which is the most well-known clustering algorithm. The clustering solutions generated by SAME and k-means are compared using the extremity measure and the silhouette index, which is a commonly used clustering measure. In 90% of instances, SAME performs better than the k-means algorithm. Thus, SAME is an effective new technique to cluster data.