SLD_T: Single-Linkage Distance to Neighborhood Threshold as Internal Validation Index for Arbitrarily Shaped Clusters

Internal cluster validation (ICV) is a major task in data mining. Unlike external validation, ICV assesses the quality of a cluster based on the cluster structure without using class label information. ICV is particularly important for unlabeled datasets. Most of the ICV indices (ICVIs) measure the quality of spherical shaped clusters. ICVIs for arbitrarily shaped clusters have paramount importance for real-life datasets having arbitrarily shaped clusters. All the existing ICVIs for arbitrarily shaped clusters are targeted to determine the optimal number of clusters. An ICVI will have more impact if, besides determining the optimal number of clusters, it can be used for other purposes such as detecting and correcting inseparable clusters and using as a fitness parameter for evolutionary process in clustering. In this study, we proposed an ICVI called single-linkage distance to neighborhood threshold (SLD_T) index. The SLD_T index is the ratio of inter-cluster separation to intracluster compactness. The intercluster separation of a cluster is measured by the single-linkage distance between the cluster and its first nearest neighbor. The intracluster compactness of a cluster is measured by the maximum of the neighborhood thresholds of the cluster and its first nearest neighbor. This ratio makes it possible to identify separable and inseparable clusters depending on the SLD_T value greater than one or not. The best clustering has the highest SLD_T value among the candidate clustering. Theoretical findings validated by experimental results show promises of SLD_T index for optimal cluster number determination, inseparable cluster detection and correction, and feature subset selection.