SingleCross-clustering: an algorithm for finding elongated clusters with automatic estimation of outliers and number of clusters

Abstract

Many clustering methods perform well with spherical clusters but poorly with elongated clusters. The Single-linkage method is suitable for finding such type of long clusters, but it can be sensitive to outliers and noise in the data, causing the so-called chain-effect. This work proposes a modification of Cross-Clustering algorithm, the SingleCross-Clustering (SCC), a partial clustering algorithm that estimates the number of clusters, recognizes outliers and that is useful for the identification of elongated clusters. SCC has been validated by comparing it with a number of existing clustering methods, showing on both simulated and real datasets that SCC is a reliable solution for the identification of the correct number of clusters and of the number of clusters memberships. The algorithm has been implemented in the R package CrossClustering, which can be downloaded for free from the CRAN contributed package repository.

Keywords:

• Classification clustering algorithm
• Clustering aggregation
• Elongated clusters
• Hierarichical agglomertion
• Number of clusters
• Outliers
• Outliers detection
• Partial clustering