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.

Unsupervised feature selection aims to enhance the quality of unlabeled data, thereby improving the performance of subsequent unsupervised learning models. However, most of the existing unsupervised feature selection methods rely on single-granularity modeling, which reduces the expressive capability of data to some extent. In addition, the existing studies are generally based on a forward greedy feature selection strategy, which tends to fall into a local optimum. To address these issues, this paper proposes a novel unsupervised feature selection method for handling hybrid data, called unsupervised feature selection method using fuzzy graph momentum random walk in bi-level granular-ball knowledge space. Specifically, a Bi-level Granular-ball Knowledge Space (BGKS) is first constructed by combining fine granularity and coarse granularity representations through a hybrid Gaussian kernel function. Then, a multi-granularity fuzzy graph is built on the BGKS using upper and lower fuzzy approximation operators. Based on this graph, a Momentum Random Walk (MRW) mechanism is introduced to design the Fuzzy Graph Momentum Random Walk (FGMRW) model. Finally, an iterative unsupervised feature selection algorithm is developed. Extensive experiments on 20 public datasets demonstrate that, compared with existing algorithms, the proposed method is able to maintain or even improve clustering performance while selecting fewer features, thus achieving superior overall performance. The source code of this work is publicly available athttps://github.com/HongtaoGao-code/FGMRW-UFS.

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.

Data sampling enhances classifier efficiency and robustness through data compression and quality improvement. Recently, the sampling method based on granular-ball (GB) has shown promising performance in generality and noisy clas-sification tasks. However, some limitations remain, including the absence of borderline sampling strategies and issues with class boundary blurring or shrinking due to overlap between GBs. In this paper, an approximate borderline sampling method using GBs is proposed for classification tasks. First, a restricted diffusion-based GB generation (RD-GBG) method is proposed, which prevents GB overlaps by constrained expansion, preserving precise geometric representation of GBs via redefined ones. Second, based on the concept of heterogeneous nearest neighbor, a GB-based approximate borderline sampling (GBABS) method is proposed, which is the first general sampling method capable of both borderline sampling and improving the quality of class noise datasets. Additionally, since RD-GBG incorporates noise detection and GBABS focuses on borderline samples, GBABS performs outstandingly on class noise datasets without the need for an opti-mal purity threshold. Experimental results demonstrate that the proposed methods outperform the GB-based sampling method and several representative sampling methods. Our source code is publicly available at https://github.com/CheryITse/GBABS.

Existing weighted clustering algorithms often heavily rely on specific parameters. Specifically, in addition to the number of clusters (k), several other parameters need to be manually tuned, which greatly limits their practical applicability. The fundamental issue lies in the fact that most weighted clustering methods derive feature weights through global iterations. To address this challenge, this paper introduces a novel weighted granular-ball structure, continually optimizing weights during the ball splitting process and restricting the calculation of local data point weights to the corresponding weighted granular-ball. We employ local iterations within this structure as an approximation to global weight calculations. This method eliminates the need for parameter tuning during the weight calculation process and incidentally addresses the “curse of dimensionality” in traditional granular-ball computing model. When applied to complex real-world datasets, this method accurately represents high-dimensional data, thereby improving clustering precision and extending the adaptability of the granular-ball computing model in high-dimensional spaces. Comprehensive experimental analysis demonstrates that our W-GBC algorithm performs well in terms of clustering results and competes strongly with baseline algorithms. The code has been released and is now available at https://github.com/xjnine/W-GBC.

Current data stream clustering algorithms face low efficiency in both the online and offline phases, and struggle to address the problem of cluster boundary overlap caused by concept drift. Specifically, in the online phase, the majority of existing data stream clustering algorithms require each newly arriving sample to be scanned and inserted into the appropriate micro-clusters. In offline clustering, algorithms typically require all sample points as input. Moreover, most data stream clustering algorithms struggle to effectively deal with the problem of cluster boundary overlap caused by the concept drift. To tackle these challenges, we use a granular-ball structure for the coarse-grained representation of data stream. This structure eliminates the need for computations on all data points in both the online and offline phases. Additionally, we introduce fuzziness into the granular-ball structure to resolve the issue of cluster boundary overlap caused by the concept drift. Experimental results on both synthetic and real-world datasets demonstrate that our approach achieves efficient and accurate clustering performance when compared to existing data stream clustering algorithms. Our source code is publicly available at https://github.com/xjnine/GBFuzzyStream.

Deep learning has achieved outstanding performance in natural language processing, but actuality has witnessed its fragility against adversarial attacks. Synonyms-based attacks are most disastrous since their generated samples approximate raw inputs. Several countermeasures have been proposed in the literature, but the defense effectiveness is unsatisfactory because of the clumsy single-granularity synonyms clustering. To mitigate this dilemma, we propose a Granular-Ball Sample Enhancement-based defense Framework (GBSEF) for text adversarial attacks. Specifically, GBSEF first adopts an effective general synonyms clustering algorithm, which can adaptively adjust the granularity of synonym sets (i.e., granular-balls) for diverse datasets. Regarding each ball as a dot, the function consisting of most dots well fits the original data distribution, resulting in the relationships among words being well presented by the granular-balls. GBSEF then replaces each input word with the center vector of its subordinate ball, to construct robust samples preserving syntax and semantic information simultaneously. Finally, GBSEF combines a random substitution mechanism with granular-balls. This way can prompt GBSEF to take full advantage of the multi-granularity feature of granular-balls, to get more diverse valid samples. GBSEF obtains great performance through training on these samples. Abundant evaluations demonstrate the robustness and effectiveness of GBSEF against adversarial attacks, albeit with a slight performance decrease under normal scenarios without attacks. Meanwhile, GBSEF has good transferability against adversarial samples. Compared with state-of-art defense countermeasures, under multiple attacks on four neural network models (i.e., CNN, LSTM, Bi-LSTM, BERT), GBSEF always outperforms existing baselines.

Most natural language processing tasks rely on massive labeled data to train an outstanding neural network model. However, the label noise (i.e., wrong label) is inevitably introduced when annotating large-scale text datasets, which significantly degrades the performance of neural network models. To overcome this dilemma, we propose a novel Granular-B all based tRAINing framework, named GBRAIN, to realize robust coarse-grained representation learning, thus combating label noises in diverse text tasks. Specifically, considering that most samples in the dataset are precisely labeled, GBRAIN first proposes a dynamic granular-ball clustering algorithm to blend seamlessly into the traditional neural network model. A striking feature of the clustering algorithm is that it can adaptively group the embedding vectors of similar data into the same set (hereafter referred to as a granular-ball). The embedding vectors and labels of all samples from the same set will be coarse-grainedly represented by the center vector and the label of the granular-ball, respectively. Consequently, noise labels can be rectified through the labels of most of the labeled data. Moreover, we introduce a new gradient backpropagation mechanism compatible with our framework, which can help optimize coarse-grained embedding vectors with iterative training. Empirical results on text classification and name entity recognition tasks demonstrate that our proposal GBRAIN is indeed effective in contrast to the state-of-the-art baselines.

This paper presents a novel framework for continual feature selection (CFS) in data preprocessing, particularly in the context of an open and dynamic environment where unknown classes may emerge. CFS encounters two primary challenges: the discovery of unknown knowledge and the transfer of known knowledge. To this end, we propose a GBCFS method, which combines the strengths of continual learning (CL) with granular-ball computing (GBC). The GBCFS method focuses on constructing a granular-ball knowledge base to detect unknown classes and facilitate the transfer of previously learned knowledge for further feature selection. GBCFS consists of two stages: initial learning and open learning. The former aims to establish an initial knowledge base through multi-granularity representation using granular balls. The latter utilizes prior granular-ball knowledge to identify unknowns, updates the knowledge base for granular-ball knowledge transfer, reinforces old knowledge, and integrates new knowledge. Subsequently, we devise an optimal feature subset mechanism that incorporates minimal new features into the existing optimal subset, often yielding superior results during each period. Extensive experimental results on public benchmark datasets demonstrate our method's superiority in terms of both effectiveness and efficiency compared to state-of-the-art feature selection methods.

Partial label learning (PLL) tackles scenarios where the unique ground-truth label of each sample is concealed within a candidate label set. Dimensionality reduction, considering labeling confidence estimation, has become a promising strategy to enhance the generalization performance of PLL models. However, current studies achieve dimensionality reduction, often relying on kNN-based labeling confidence estimation or disregarding potential labeling information. To address this issue, this paper proposes a novel Confidence-induced granular Partial label feature selection method using Dependency and Similarity (CPDS), which consists of two phases: Labeling Confidence Estimation (LCE) and Feature Selection (FS). For LCE, through granular ball computing, the feature space's similarity and the label space's correlation between the training data and the granular ball can be fused simultaneously, thereby effectively reconstructing more credible labeling confidence from candidate labels with more diverse semantic representation information. In the FS stage, by leveraging the LC with more diverse information, the proposed PLL neighborhood decision system further effectively combines feature dependency and label similarity to identify a feature subset with more discriminative capabilities, thereby achieving better performance for classification tasks. Among them, feature dependency effectively utilizes the dependency between neighborhoods and equivalence relations, while label similarity fully exploits the similarity between each sample and its neighbors. Extensive experiments show that CPDS significantly outperforms the compared approaches in most cases on nine controlled UCI datasets and five real-world datasets, demonstrating the superiority of the proposed method.

Traditional fuzzy set methods, designed around the finest granularity of inputs-individual points and their membership degrees-often struggle with inefficiencies and label noise. To overcome these challenges, we introduce granular-ball computing into the fuzzy set, creating the new granular-ball fuzzy set framework. This approach uses granular-ball inputs rather than single points, significantly reducing the number of entities and minimizing susceptibility to the noise affecting individual sample points. As a result, our framework enhances both efficiency and robustness compared to traditional methods and is applicable across various domains of fuzzy data processing. Furthermore, we apply this framework to fuzzy support vector machines (FSVMs), developing the Granular-ball Fuzzy Support Vector Machine (GBFSVM). Experimental tests on UCI benchmark datasets show that GBFSVM surpasses traditional models in efficiency and robustness.

This paper presents a strong data-mining method based on a rough set, which can simultaneously realize feature selection, classification, and knowledge representation. Although a rough set, a popular method for feature selection, has good interpretability, it is not sufficiently efficient and accurate to deal with large-scale datasets with high dimensions, which prevents it from being immediately applied to real-world scenarios. To address the efficiency issue of a rough set, we discover the stability of the local redundancy (SLR) of attributes and propose a theorem to prove it rigorously. Based on SLR, only the parts of objects in the boundary region are partitioned when calculating outer significance, which further improves the efficiency of the rough set. With regard to the accuracy issue, we show that overfitting may lead to ineffectiveness of the rough set, especially when processing noise attributes. We then propose relative importance, a robust measurement for an attribute, to alleviate such overfitting issues. In this paper, we propose a novel rough-set framework that significantly improves the efficiency and accuracy of existing rough-set methods. We further develop our rough set framework by proposing a “rough concept tree” for knowledge representation and classification. Experimental results on public benchmark datasets show that our proposed framework achieves higher accuracy than seven state-of-the-art feature-selection methods. All the codes are available athttps://github.com/syxiaa/powerroughset.

Feature selection is an important preprocessing step in data mining and pattern recognition. The neighborhood rough set (NRS) model is a widely-used rough set model for feature selection on continuous data. All currently known NRS models are defined on a distance metric — mostly the euclidean distance metric — which invalidates the NRS models in scenarios wherein the euclidean distance is ineffective, for example, while considering differing attribute weights. We first introduce the concept of space division of granular-rectangular, and then construct the neighborhood radius in our method by describing the relationship between child and parent spaces, which avoids the use of a distance metric and reduces the search space for the neighborhood radius. This greatly improves both the accuracy and efficiency of NRS. In addition, the upper and lower approximations of the granular-rectangular rough sets (GRRSs) comprise equivalence classes; this results in better performance of GRRS in knowledge representation compared with the traditional NRS. Experimental results on public benchmark datasets reveal that our method, GRRS, achieves higher accuracy than ten popular and state-of-the-art feature-selection methods, including two NRS algorithms. Moreover, GRRS outperforms the established NRS algorithms regarding efficiency, including the state-of-the-art NRS algorithm, GBNRS. All code has been released as an open libary called GRRS:https://github.com/syxiaa/GRRS.

In order to solve the problem that the traditional spectral clustering algorithm is time-consuming and resource consuming when applied to large-scale data, resulting in poor clustering effect or even unable to cluster, this paper proposes a spectral clustering algorithm based on granular-ball(GBSC). The algorithm changes the construction method of the similarity matrix. Based on granular-ball, the size of the similarity matrix is greatly reduced, and the construction of the similarity matrix is more reasonable. Experimental results show that the proposed algorithm achieves better speedup ratio, less memory consumption and stronger anti noise performance while achieving similar clustering results to the traditional spectral clustering algorithm. Suppose the number of granular-balls is$m$,$n$is the number of points in the dataset, and$m< < n$, the time complexity of GBSC is$O(m^{3})$. It is proved that GBSC has good adaptability to large-scale datasets. All codes have been released athttps://github.com/xjnine/GBSC.

Granular computing, a new paradigm for solving large-scale and complex problems, has made significant progresses in knowledge discovery. Granular ball computing (GBC) is a novel granular computing method, which can rapidly generate scalable and robust information granules, that is, granular balls. However, a comprehensive index for measuring the performance of a granular ball does not exist. Furthermore, GBC lacks a mechanism to deal with dynamic decision systems. Therefore, in this study, the quality index of a granular ball is first formulated. Next, with this index, a novel granular ball rough sets model (GBRS) based on GBC is proposed. GBRS is more conducive to learning knowledge from uncertain datasets and more suited to incremental learning than the latest granular ball neighborhood rough sets model based on GBC. Subsequently, an incremental mechanism is introduced into GBRS, and two incremental learning models are developed for objects increasing in stream patterns and batch patterns, respectively. In the incremental learning process, three patterns of granular balls, that is, update, fusion, and split, were well studied when a set of objects was added to the decision system. Finally, to verify the effectiveness and efficiency, we apply GBRS and these two incremental learning models into classification tasks. Compared with four current state-of-the-art classification methods based on granular computing and four classical classifiers in machine learning, the proposed classifiers in this paper achieve higher classification accuracy as well as better efficiency on benchmark datasets.

Feature reduction is an important aspect of Big Data analytics on today’s ever-larger datasets. Rough sets are a classical method widely applied in attribute reduction. Most rough set algorithms use theprioridomain knowledge of a dataset to process continuous attributes through using a membership function. Neighborhood rough sets (NRS) replace the membership function with the concept of neighborhoods, allowing NRS to handle scenarios where noa prioriknowledge is available. However, the neighborhood radius of each object in NRS is fixed, and the optimization of the radius depends on grid searching. This diminishes both the efficiency and effectiveness, leading to a time complexity of not lower than$O(N^2)$O(N2). To resolve these limitations, granular ball neighborhood rough sets (GBNRS), a novel NRS method with time complexity$O(N)$O(N), is proposed. GBNRS adaptively generates a different neighborhood for each object, resulting in greater generality and flexibility in comparison to standard NRS methods. GBNRS is compared with the current state-of-the-art NRS method, FARNeMF, and find that GBNRS obtains both higher performance and higher classification accuracy on public benchmark datasets. All code has been released in the open source GBNRS library athttp://www.cquptshuyinxia.com/GBNRS.html.

The existing noise detection methods required the classifiers or distance measurements or data overall distribution, and `curse of dimensionality' and other restrictions made them insufficiently effective in complex data, e.g., different attribute weights, high-dimensionality, containing feature noise, nonlinearity, etc. This is also the main reason that the existing noise filtering methods were not widely applied and formed an effective learning framework. To address this problem, we propose here a complete and efficient random forest method (CRF) specifically for the class noise detection by simulating the grid generation and expansion. The CRF is not based on distance measures or overall distribution or classifiers; besides, the voting mechanism makes it able to effectively process datasets containing feature noise. Furthermore, we introduce CRF based class noise filtering learning framework (CRF-NFL) and derive its mathematical model. The framework is then applied to many widely used classifiers including some state-of-the-art algorithms, e.g., k-means tree, GBDT, and XGBoost. Moreover, its parallelized is designed for large-scale data. The CRF-NFL show much better generalizability than the conventional classifiers and the relative density-based method, which is the most effective noise filtering method as far as we know. All research has formed an open source library, called CRF-NFL: http://www.cquptshuyinxia.com/CRF-NFL.html.

Class noise can cause overfitting of learning methods and deteriorate their generalizability. Although relative density can detect class noise effectively, it has a time complexity of O(N2) and a low efficiency. To address this problem, by introducing the granular computing into the relative density model, this paper proposes a Multi-Granularity Relative Density (MGRD) model for class noise detection. In an experiment, we tested the effect of parameters on its performance under classifiers. The experimental results on benchmark data sets demonstrated that it had a higher efficiency than conventional methods. In addition, it exhibited better generalizability in comparison with the conventional methods because of the good robustness of granular computing on many cases.

In the human cognition learning, the noise self-filtering filters the noise data by itself, making the human brain very robust. Although k-Nearest Neighbors (kNN) can decrease the affection of noise data by optimizing the parameter k, noise data still may deteriorate the learning results to an extent on various data. Therefore, this paper proposes the strategy for kNNs. Here, we formalize such training strategies in the context of kNNs, and they are called with “Noise Self-filtering k-Nearest Neighbors” (NSF-kNNs). As its name suggests, it is determined by the model itself based on what it has already learned, as oppose to some predefined heuristic criteria. We derive the mathematical model of the NSF-kNNs, which is an algorithm framework. The NSF-kNNs are compared with the exact kNNs and as far as we know the most efficient approximate kNN [1]. The results show the achievement of improvements in the robustness and generalizability on various data sets.