Although spectral clustering is capable of identifying clusters of arbitrary shapes, its high time and space complexity poses limitations in large-scale data clustering applications. To tackle this problem, researchers have proposed using anchor points to construct the similarity matrix, thereby reducing time and space complexity. However, current methods for generating anchor points do not fit the data well and are limited in approach. To improve upon existing anchor points generation methods, we proposes a pseudo-label-based anchor points generation approach and develops a fast spectral clustering algorithm for large-scale data, named FSC-PLGB. The algorithm first randomly selects r points as an initial granular-ball, applies K-Means on these points to obtain pseudo-labels, calculates the pseudo-purity of the granular-ball based on these pseudo labels, and then performs granular-ball division based on these pseudo-purity to generate anchor points. A similarity matrix is constructed between all sample points and anchor points, and finally, spectral clustering is applied to obtain the clustering results. The experimental results demonstrate that our proposed algorithm exhibits exceptional efficiency and significant superiority on large-scale datasets. The source code is available at https://github.com/DongdongCheng/FSC-PLGB.

With the swift advancement of information technology, vast amounts of high-dimensional data have accumulated across various domains. Clustering such data presents a significant challenge, as existing methods often suffer from slow execution speeds and reduced clustering accuracy. To tackle these issues, we introduce the granular-ball approach, which aims to decrease the number of sample points and enhance processing speed, while also improving clustering accuracy through feature selection. Granular-ball computing, a coarse-grained data representation technique, has demonstrated its advantages in enhancing classification and clustering models in recent studies. However, current granular-ball division techniques are inadequate for high-dimensional data. To confront the complexities arising from clustering high-dimensional data and improve upon existing granular-ball methods, this paper proposes a novel granular-ball division approach that leverages pseudo-labels and feature selection. This new method enables the identification of anchor points through an improved granular-ball division process, leading to the development of a fast spectral clustering algorithm for high-dimensional data, termed PLGB-FSC. Specifically, we initially employ weighted K-Means for feature to generate pseudo-labels. Subsequently, we conduct a primary stage of feature selection by utilizing the mutual information between pseudo-labels and features, thereby eliminating the interference caused by irrelevant features. We further refine the feature selection by combining standard deviation and pearson correlation coefficients to choose mutually independent features. Using these pseudo-labels, we then perform granular-ball division to obtain anchor points. Lastly, we construct a similarity matrix between all sample points and the anchor points, and leveraging spectral clustering for definitive clustering outcomes. Experimental evaluations reveal that PLGB-FSC surpasses state-of-the-art algorithms such as W-KMeans, WGB, GB-USC, RC-PCA-SC, GLUFC, FGOC, SFESA, SPCAFS, and LLSRFS, and it achieves higher accuracy and faster execution speed. The source code is available at https://github.com/DongdongCheng/PLGB-FSC.

Manifold learning is essential for analyzing high-dimensional data, but it suffers from high time complexity. To address this, researchers proposed using anchors and constructing a similarity matrix to expedite eigen decomposition and reduce sparse consumption. However, randomly selected anchors fail to represent the data well, and using K-means for anchor generation is time-consuming. In this paper, we introduce Granular-ball (GB) into unsupervised manifold learning, presenting GB-USC and GB-USEC. By employing a coarse-to-fine approach, GB-USC generates high-quality anchors aligned with the data distribution. A bipartite graph is constructed between data points and anchors, enabling low-dimensional manifold embedding using transfer cut. GB-USEC combines multiple GB-USC clusters, generating consistent low-dimensional embeddings across dimensions and determining clustering results through voting. The experimental results show that compared with the state-of-the-art algorithm U-SPEC, GB-USC achieves the similar performance with the average running time of GB-USC is 33.96% less than that of U-SPEC for several million-level datasets. Additionally, our ensemble algorithm improves the clustering efficiency by an average of 29.19% compared with U-SENC.

Due to simplicity, K-means has become a widely used clustering method. However, its clustering result is seriously affected by the initial centers and the allocation strategy makes it hard to identify manifold clusters. Many improved K-means are proposed to accelerate it and improve the quality of initialize cluster centers, but few researchers pay attention to the shortcoming of K-means in discovering arbitrary-shaped clusters. Using graph distance (GD) to measure the dissimilarity between objects is a good way to solve this problem, but computing the GD is time-consuming. Inspired by the idea that granular ball uses a ball to represent the local data, we select representatives from a local neighborhood, called natural density peaks (NDPs). On the basis of NDPs, we propose a novel K-means algorithm for identifying arbitrary-shaped clusters, called NDP-Kmeans. It defines neighbor-based distance between NDPs and takes advantage of the neighbor-based distance to compute the GD between NDPs. Afterward, an improved K-means with high-quality initial centers and GD is used to cluster NDPs. Finally, each remaining object is assigned according to its representative. The experimental results show that our algorithms can not only recognize spherical clusters but also manifold clusters. Therefore, NDP-Kmeans has more advantages in detecting arbitrary-shaped clusters than other excellent algorithms.

Density peaks clustering algorithm (DP) has difficulty in clustering large-scale data, because it requires the distance matrix to compute the density and -distance for each object, which has time complexity. Granular ball (GB) is a coarse-grained representation of data. It is based on the fact that an object and its local neighbors have similar distribution and they have high possibility of belonging to the same class. It has been introduced into supervised learning by Xia et al. to improve the efficiency of supervised learning, such as support vector machine, -nearest neighbor classification, rough set, etc. Inspired by the idea of GB, we introduce it into unsupervised learning for the first time and propose a GB-based DP algorithm, called GB-DP. First, it generates GBs from the original data with an unsupervised partitioning method. Then, it defines the density of GBs, instead of the density of objects, according to the centers, radius, and distances between its members and centers, without setting any parameters. After that, it computes the distance between the centers of GBs as the distance between GBs and defines the -distance of GBs. Finally, it uses GBs' density and -distance to plot the decision graph, employs DP algorithm to cluster them, and expands the clustering result to the original data. Since there is no need to calculate the distance between any two objects and the number of GBs is far less than the scale of a data, it greatly reduces the running time of DP algorithm. By comparing with -means, ball -means, DP, DPC-KNN-PCA, FastDPeak, and DLORE-DP, GB-DP can get similar or even better clustering results in much less running time without setting any parameters. The source code is available at https://github.com/DongdongCheng/GB-DP.

Outlier detection is one of the hot research in data mining , and has been applied to various fields such as network anomaly detection , image abnormal analysis, etc. In recent years, many outlier detecting algorithms have been proposed. However, these outlier detecting algorithms are hard to effectively detect global outliers, local outliers and outlier clusters at the same time. In this paper, we propose a novel outlier detecting algorithm based on the following ideas: (1) the density distribution should not be changed dramatically on local area; (2) the ratio of the number of k nearest neighbors and the number of reverse k nearest neighbors should not be very big. Based on above ideas, the proposed algorithm aims to find outlier turning points, then regards all outlier turning points and its sparse neighbors as outliers. Furthermore, the proposed algorithm use natural neighbors to obtain the neighborhood parameter k adaptively. The formal analysis and extensive experiments demonstrate that this technique can detect global outliers, local outliers and outlier clusters without neighborhood parameter k .

Spectral clustering is becoming more and more popular because it has good performance in discovering clusters with varying characteristics. However, it suffers from high computational cost, unstable clustering results and noises. This work presents a novel approximate spectral clustering based on dense cores and density peaks, called DCDP-ASC. It first finds a reduced data set by introducing the concept of dense cores; then defines a new distance based on the common neighborhood of dense cores and calculates geodesic distances between dense cores according to the new defined distance; after that constructs a decision graph with a parameter-free local density and geodesic distance for obtaining initial centers; finally calculates the similarity between dense cores with their new defined geodesic distance, employs normalized spectral clustering method to divide dense cores, and expands the result on dense cores to the whole data set by assigning each point to its representative. The results on some challenging data sets and the comparison of our algorithm with some other excellent methods demonstrate that the proposed method DCDP-ASC is more advantageous in identifying complex structured clusters containing a lot of noises.

Hierarchical clustering is an important research branch of cluster analysis that has extensive ranges of practical applications. Meanwhile, it still faces problems such as inaccurate, time-consuming, and difficulty in choosing linkage method. In this paper, we present a new Hierarchical Clustering method based on Local Cores and Sharing concept (HCLCS) which takes a "divide-and-merge" framework by first dividing a data set into several small clusters and then merging them hierarchically. To improve the accuracy, the merging process is further divided into two substeps: (1) pre-connect small clusters that belong very likely to the same category, and (2) merge the pre-connected intermediate clusters and the remaining unconnected small clusters in a classical hierarchical way. Extensive experiments on synthetic and real-world data sets show that HCLCS can achieve better performance than existing methods in dealing with data sets with complex structures and is less time-consuming than two state-of-the-art algorithms (SNN-DPC and RSC).

Clustering analysis has been widely used in statistics, machine learning, pattern recognition, image processing, and so on. It is a great challenge for most existing clustering algorithms to discover clusters with arbitrary shapes. Clustering algorithms based on Minimum spanning tree (MST) are able to discover clusters with arbitrary shapes, but they are time consuming and susceptible to noise points. In this paper, we employ local density peaks (LDP) to represent the whole data set and define a shared neighbors-based distance between local density peaks to better measure the dissimilarity between objects on manifold data. On the basis of local density peaks and the new distance, we propose a novel MST-based clustering algorithm called LDP-MST. It first uses local density peaks to construct MST and then repeatedly cuts the longest edge until a given number of clusters are found. The experimental results on synthetic data sets and real data sets show that our algorithm is competent with state-of-the-art methods when discovering clusters with complex structures.

It is critical to evaluate the quality of clusters for most cluster analysis. A number of cluster validity indexes have been proposed, such as the Silhouette and Davies-Bouldin indexes. However, these validity indexes cannot be used to process clusters with arbitrary shapes. Some researchers employ graph-based distance to cluster nonspherical data sets, but the computation of graph-based distances between all pairs of points in a data set is time-consuming. A potential solution is to select some representative points. Inspired by this idea, we propose a novel Local Cores-based Cluster Validity (LCCV) index to improve the performance of Silhouette index. Local cores, with local maximum density, are selected as representative points. Since graph-based distance is used to evaluate the dissimilarity between local cores, the LCCV index is effective for obtaining the optimal cluster number for data sets containing clusters with arbitrary shapes. Moreover, a hierarchical clustering algorithm based on the LCCV index is proposed. The experimental results on synthetic and real data sets indicate that the new index outperforms existing ones.

Hierarchical clustering is of great importance in data analysis. Although there are a number of hierarchical clustering algorithms including agglomerative methods, divisive methods and hybrid methods, most of them are sensitive to noise points, suffer from high computational cost and cannot effectively discover clusters with complex structures. When recognizing patterns from complex structures, humans intuitively tend to discover obvious clusters in dense regions firstly and then deal with objects on the border. Inspired by this idea, we propose a local cores-based hierarchical clustering algorithm called HCLORE. The proposed method first partitions the data set into several clusters by finding local cores, instead of optimizing an objective function through iteration like K-means; then, temporarily removes points with lower local density, so that the boundary between clusters is clearer; after that, merges clusters according to a new defined similarities between clusters; and finally, points with lower local density are assigned to the same clusters as their local cores belong to. The experimental results on synthetic data sets and real data sets show that our algorithm is more effective and efficient than existing methods when processing data sets with complex structures.

Clustering analysis has been widely used in many areas such as astronomy, bioinformatics, and pattern recognition. In 2014, Rodriguez proposed an algorithm based on the idea that cluster centers are characterized by a higher density than their neighbors and by a relatively large distance from points with higher density. But the density relies on cutoff distance, which might be affected by large statistical error, and the algorithm does not suit the clustering problem of multi-scale data. In this paper, a new neighbor concept Natural Neighbor is proposed. Natural neighbor-based density, is simple and well reflects the data distribution without any parameters. Then, we extend each cluster from its center by searching natural neighbors of points in this cluster, and we define extension rules to determine the cluster boundary. The experiment results show our algorithm is more effective on multi-scale data.