Clustering massive datasets
Emmanuel Sikali, Edward J. Wegman · 2004
Our data collection ability has increased tremendously in the last decade due to numerous advances in computer science, software development, and the Internet, coupled with faster computer chips. Today, corporations, individuals, and academic researchers are challenged by the problem of analyzing databases containing between 1010 to 1012 bytes of data with the number of fields ranging from 10 to 104. Datasets with these characteristics are classified by the Huber/Wegman taxonomy of datasets as massive. Many algorithms are currently used in data analysis; however, most of these algorithms were developed before the emergence of computer technology when most datasets could be stored on a few sheets of paper and complexity was not a problem. Attempts to use these algorithms to perform real-time analyzes or organize massive datasets with the fastest computers available today are bound to fail. Therefore, there is an urgent need to develop new algorithms, or scale up existing ones in order to handle such a challenging task. The main drawback of existing clustering algorithms is the high computational effort required to achieve the results; this is why these techniques become impracticable when applied to massive datasets. The purpose of this dissertation is to develop a low computational complexity algorithm that clusters massive datasets. The inspiration of this algorithm is based on the idea elaborated by Silverman [2] that the clusters in a dataset correspond to the peaks in the density estimate constructed from the points of the dataset. First, nonparametric kernel estimation is introduce along with nonlinear-interior quadratic prox methods that are the main mathematical programming techniques that will be used to compute the vector of bandwidth parameters. This vector is computed by minimizing the error due to the approximation of the true density, by the density estimation, using unbiased cross validation. The components of the vector of bandwidth parameters in each dimension of the data help to shape the kernel function so that features of the data are captured using the kernel density estimation. Furthermore a line search is used to find the set of all the local maxima of the curve of the kernel density estimation, which represents the set of all the cluster centers. Sampling methods are used along with mathematical programming to reduce the complexity of the algorithm. This research includes contributions in different forms, from a better clustering algorithm to the good computation of the vector of bandwidth parameters of the nonparametric kernel density estimation. The algorithm handles high dimensional data very well, it is insensitive to the order of input of records, and requires no previous knowledge of the dataset and thus takes no input parameters. The memory available for computing is the only limitation to the amount of data that the algorithm handles.