Graph Based Hybrid Clustering With Unbounded Regions

An extension of the hybrid clustering approach is proposed for partitioning data with possibly unbounded polygon regions. Clustering or partitioning data into relatively homogeneous and coherent subpopulations can be an effective pre-processing method to achieve data analysis tasks such as pattern recognition and classification. Our method uses a graph to model the initial manual partition of the dataset. Based on the graph model, an algorithm is developed for automatic detection of the regions defined by the partition. A clustering algorithm using Markov Chain Monte Carlo method is developed for finding optimal adjustments to the partition automatically. The regions are generalized polygons which may include points at infinity. Homogeneous coordinates are used to represent the points at infinity and to derive algorithms in a unified fashion. Keywords: Partition; clustering; Planar graph; Markov Chain Monte Carlo method; Homogeneous coordinates