LVC: Local Variance-based Clustering

摘要

Clustering has raised as an important problem in many different domains like biology, computer vision, text analysis and robotics. Thus, many different clustering techniques were developed to address this essential problem and propose astonishing solutions to conquer it. However, traditional clustering techniques suffer either from their limitations to detect specific shapes like K-means and PAM or from their limitations to detect clusters with specific densities as in DBSCAN and SNN. Moreover, exploiting the data relations and similarities has been proven to provide better insights to enhance the clustering quality as shown in spectral clustering and affinity propagation. Our observations have shown that using variance of similarities between each data point and its neighbors can well distinguish between within-cluster points, points connecting two clusters and outlier points. Therefore, we have utilized this variance measure to calculate each data point density and developed a Local Variance-based Clustering (LVC) technique that employs this measure to cluster the data. Experimental results show that LVC outperforms spectral clustering and affinity propagation in clustering quality using control charts, ecoli and images datasets, while maintaining a good running time. In addition, results show that LVC can detect topics from Twitter with higher topic recall by 15% and higher term precision by 3% over DBSCAN.