Supervised clustering: algorithms and applications
Christoph F. Eick, Nidal M. Zeidat · 2005
This work centers on a novel data mining technique we term supervised clustering. Unlike traditional clustering, supervised clustering assumes that the examples are classified. The goal of supervised clustering is to identify class-uniform clusters that have high probability densities. Three representative-based algorithms for supervised clustering are introduced: a greedy algorithm with random restart, named SRIDHCR, that seeks for solutions by inserting and removing single objects from the current set of cluster representatives, SPAM (a variation of the popular clustering algorithm PAM), and an evolutionary computing algorithm named SCEC. The three algorithms were evaluated using a benchmark consisting of UCI machine learning datasets. As part of the evaluation of the supervised clustering algorithms, we study the landscape for the fitness function that supervised clustering tries to minimize. Results show that the fitness landscape seems to have a Canyonland shape with large number of hills and plateaus that seems unforgivable for greedy search strategies. This dissertation also discusses and presents experimental evidence on how local and regional learning techniques could benefit from supervised clustering. Specifically, we introduce a technique for class decomposition and demonstrate with experimental results how it could enhance the performance of simple classifiers. Furthermore, we present a dataset editing technique, we call supervised clustering editing (SCE), which replaces examples of a learned cluster by the cluster representative. Our experimental results demonstrate how dataset editing techniques in general and SCE technique in particular enhance the performance of NN classifiers. Other potential applications of supervised clustering such as summary generation, discovery of interesting regions in spatial databases, and distance function learning are discussed as well.