METHODS FOR FAST AND RELIABLE CLUSTERING
Ismo Kärkkäinen · UEF eRepo (University of Eastern Finland) · 2006
Clustering is used in many areas as a tool to inspect the data or to generate a representation of the data that is better suited to the application. In this work, different parts related to clustering are studied. Focus is mainly on making the algorithms faster while preserving reliability. Attention is paid to the ability of the algorithms to find the number of clusters. Binary data sets and large data sets present problems for clustering algorithms. Some improvements for handling these cases are proposed. For a fixed number of clusters, the clustering problem can be solved in a fast and reliable manner, but the problem changes when the number of clusters is unknown. Performing the clustering repeatedly is no longer fast. The proposed solutions to performing clustering rapidly involve reusing the results of previous work and focusing the search to more promising model sizes. Using the previous results as a starting point improves the speed of clustering when solving the clustering for the next model size. Performing the search so that the model size is optimized along with the model produces much greater speed-up. This is due to less work is done on the models of much larger or smaller size than the number of clusters in the data. Binary data causes problems for certain clustering algorithms. These problems are addressed by changing the distance function. One proposed method is designed for a specific clustering criterion. The distance function is used to decide how to best improve the value of the criterion locally at each step of the algorithm. The second proposed method changes the distance function gradually from L∞ to L1. The proposed algorithm for large data sets converts the data into a model using only one pass over the data. The data need not be stored in memory. In this way, the data can be processed much faster, and without excessive memory consumption.