Scalable and adaptive evolutionary clustering for noisy and dynamic data
Olfa Nasraoui, Elizabeth León · 2005
In this dissertation a new evolutionary clustering algorithm, called ECSAGO from Evolutionary Clustering with Self Adaptive Genetic Operators, was developed. ECSAGO is a generalization an extension of Unsupervised Niche Clustering algorithm (UNC) that, while maintaining the desirable qualities of flexibility for a variety of applications, accuracy, and robustness to noise, is able to avoid UNC limitations related to representation, parameter dependency, and scalability in the face of large data sets. In particular, the proposed genetic clustering algorithm is able to deal with several encoding schemes, adapt the genetic operator rates automatically through the evolution, and is scalable and adaptable to different clustering problems. Extensions were done in order to deal with encoding schemes that can better represent complex search spaces, such as real and sparse spaces. Also, the UNC mating restriction condition was eliminated by introducing an appropriated encoding scheme and specialized genetic operators. The self-daptation of genetic operator rates was defined based on a hybrid parameter adaptation technique called Hybrid Adaptive Evolutionary Algorithm (HAEA), and it is performed while searching for the cluster prototypes. The scalable, ECSAGO module was defined based on a new interpretation of the mechanisms used in UNC within the context of kernel density estimation, incremental learning, data summarization, non-stationary function optimization, and memorization factor. The ECSAGO and scalable ECSAGO were used for solving real clustering problems where it is desired to discover the embedded categories in a data set without any prior knowledge about its class labels, and also used for classification problems, where an accurate clustering can form a summarized model of the data, that is later used for classification of new data and for anomaly detection. The data sets that were used in the experimental results stem from real life applications, including unsupervised classification and organization of text documents and network intrusion detection.