Search

Let { A n } n be a sequence of square matrices such that size (A n) = d n → ∞ as n → ∞. We say that { A n } n has an asymptotic spectral distribution described by a Lebesgue measurable function f : D ⊂ R k → C if, for every continuous function F : C → C with bounded support, lim n → ∞ ⁡ 1 d n ∑ i = 1 d n F (λ i (A n)) = 1 μ k (D) ∫ D F (f (x)) d x , where μ k is the Lebesgue measure in R k and λ 1 (A n) , ... , λ d n (A n) are the eigenvalues of A n. In the last decades, the asymptotic spectral distribution of increasing size matrices has become a subject of investigation by several authors. Special attention has been devoted to matrices A n arising from the discretization of differential equations, whose size d n diverges to ∞ along with the mesh-fineness parameter n. However, despite the popularity that the topic has reached nowadays, the role of the so-called test functions F appearing in the above limit relation has been inexplicably neglected so far. In particular, a natural question such as "Which is the largest set of test functions F for which the above limit relation is satisfied?" is still unanswered. In the present paper, we provide a definitive answer to this question by identifying the largest set of test functions F for which the above limit relation is satisfied. We also present some applications of this result to the analysis of spectral clustering, including new asymptotic estimates on the number of outliers. A special attention is devoted to the so-called "inner outliers" of Hermitian block Toeplitz matrices. We conclude the paper with an interpretation of the main result in the context of the vague convergence of probability measures. [ABSTRACT FROM AUTHOR]

[Display omitted] Forest disturbances such as wildfires can dramatically alter forest structure and composition, increasing the likelihood of ecosystem changes. Up-to-date and accurate measures of post-disturbance forest recovery in managed forests are critical, particularly for silvicultural planning. Measuring the live and dead vegetation post-fire is challenging because areas impacted by wildfire may be remote, difficult to access, and/or dangerous to survey. The difficulties of post-fire monitoring are compounded by the global increase in the frequency and severity of disturbances, as expansion of disturbed areas also increases the number and size of areas requiring post-disturbance monitoring. Methods that safely, efficiently, and extensively differentiate silviculturally beneficial coniferous growth from barren ground or deciduous shrubs are necessary to inform post-fire forest management. Satellite imagery can detect burn patterns, but monitoring changes in forest structure post fire is challenging due to complex vegetation responses. To overcome this challenge, this study combines post-disturbance spectral trajectory measures from a time series of historical Landsat imagery with field and remotely piloted aircraft (RPA) lidar (light detection and ranging) data to examine vegetation recovery of lodgepole pine (Pinus contorta) dominated sub-boreal forests after high-severity fires in 2006 in central British Columbia, Canada. Distinct spectral recovery trajectories were identified using data-clustering from a combination of seven Landsat spectral indices, with trajectories varying by recovery magnitude and rate. The forest structure associated with each distinct trajectory of spectral recovery was analyzed using 430 ha of spatially explicit forest structure measures (e.g., basal area, stem counts) and composition (e.g., percent coniferous) derived from 26 coincident field plots and high density RPA lidar (>200 points/m2) data. By comparing spectral trajectories to forest structure measures, we found the most spatially abundant cluster of spectral recovery coincided with a basal area of 0.62 m2/ha, high stem densities (>5000 stems/ha) and a high abundance of coniferous trees (>95 % coniferous). Around 10 % of the landscape was associated with relatively high abundance of deciduous vegetation (>20 %) in addition to very high conifer stem densities (>8000 stems/ha). By identifying the structural characteristics associated with unique Landsat spectral trajectories, we highlight the combined value of RPA lidar data and satellite image time series in providing a detailed and spatially explicit characterization of post-fire recovery relevant to managed forests. [ABSTRACT FROM AUTHOR]

Agriculture includes the production of crops, animals, aquaculture, fisheries, and forests for both food and non-food use. The primary factor in the rise of sedentary civilization among humans was agriculture, which allowed people to live in cities by producing surpluses of food from the farming of domesticated species. Uncertainties in the Agricultural Sector directly imply a steep decline in every other aspect of any society. The Agronomical Products, be they raw vegetables, or produced fruits, are all prone to Parasites and Microorganisms. In this research, we will focus on Solanum Tuberosum, and its disease Early Blight, of which, Alternaria Solani is a Causal Vector. For the detection of Early Blight in Potato Leaves, we will make use of the Image Segmentation Technique, based on Spectral Clustering, with Normalized Laplacian Cuts. The model works by segmenting, or rather segregating the affected part of the Potato leaf from the unaffected part, resulting in the formation of a few clusters, based on which the affected leaves can be classified from the healthy leaves. Though the model is a parametrized model, the results have been explored for different values of the parameters, σ i , and σ x that correspond to the varying configuration of the Gaussian Kernel. The efficiency of the Proposed Model have been compared with existing Image Clustering Models, like, Fuzzy C-means Clustering, Agglomerate Clustering, etc. [ABSTRACT FROM AUTHOR]

Multi-view data suffer from issues related to low quality and heterogeneity, which leads to instability issues in existing learning models for clustering. To overcome the limitations of traditional clustering methods, we propose a novel multi-view spectral clustering based on a contrastive feedback strategy. The proposed method constructs kernelized graphs to obtain higher-order feature representations, mapping primary sample data from different views into an isomorphic feature space and masking differences in type and structure between multiple views. In the meantime, the proposed method leverages a contrastive feedback optimization strategy based on mutual information to iteratively optimize the kernelized graphs of all views and their dynamically fused graph. This method effectively exploits the consistency and complementary information between multi-view, further improving the clustering accuracy. Experiments on multiple datasets demonstrate that the proposed method achieves satisfactory results in terms of clustering, validating the feasibility and effectiveness of the contrastive feedback strategy. • Proposes MKGF-CF to utilize multi-view data consistency and complementarity. • Addresses heterogeneity by mapping data to isomorphic feature space. • Uses mutual info feedback to select kernels, improving graph consistency. [ABSTRACT FROM AUTHOR]

Spectral clustering has attracted intensive attention in multimedia applications due to its good performance on arbitrary shaped clusters and well-defined mathematical framework. However, most existing multi-view spectral clustering methods still have the following demerits: (1) They ignore useful complementary information embedded in indicator matrices of different views. (2) The conventional post-processing methods based on the relax and discrete strategy inevitably result in the sub-optimal discrete solution. To tackle the aforementioned drawbacks, we propose a low-rank discrete multi-view spectral clustering model. Drawing inspiration from the fact that the difference between indicator matrices of different views provides useful complementary information for clustering, our model exploits the complementary information embedded in indicator matrices with tensor Schatten p -norm constraint. Further, we integrate low-rank tensor learning and discrete label recovering into a uniform framework, which avoids the uncertainty of the relaxed and discrete strategy. Extensive experiments on benchmark datasets have demonstrated the effectiveness and superiority of the proposed method. [ABSTRACT FROM AUTHOR]

Multi-view clustering is widely used to improve clustering performance. Recently, the subspace clustering tensor learning method based on Markov chain is a crucial branch of multi-view clustering. Tensor learning is commonly used to apply tensor low-rank approximation to represent the relationships between data samples. However, most of the current tensor learning methods have the following shortcomings: the information of the local graph is not taken into account, the relationships between different views are not shown, and the existing tensor low-rank representation takes a biased tensor rank function for estimation. Therefore, a nonconvex low-rank tensor approximation with graph and consistent regularizations (NLRTGC) model is proposed for multi-view subspace learning. NLRTGC retains the local manifold information through graph regularization, and adopts a consistent regularization between multi-views to keep the diagonal block structure of representation matrices. Furthermore, a nonnegative nonconvex low-rank tensor kernel function is used to replace the existing classical tensor nuclear norm via tensor-singular value decomposition (t-SVD), so as to reduce the deviation from rank. Then, an alternating direction method of multipliers (ADMM) which makes the objective function monotonically non-increasing is proposed to solve NLRTGC. Finally, the effectiveness and superiority of the NLRTGC are shown through abundant comparative experiments with various state-of-the-art algorithms on noisy datasets and real world datasets. [ABSTRACT FROM AUTHOR]

Multi-view clustering based on graph learning has attracted extensive attention due to its simplicity and efficiency in recent years. However, there are still some issues in most of the existing graph-based multi-view clustering methods. First, most of those methods require post-processing such as K-means or spectral rotation to get the final discrete clustering result. Second, graph-based clustering methods perform clustering on a fixed input similarity graph, which could induce bad clustering results if the initial graph is with low quality. Third, these methods have high computation cost, which hinders them for dealing with large-scale data. In order to solve these problems, we propose a multi-view spectral clustering method via joint Adaptive Graph Learning and Matrix Factorization (AGLMF). In this method, to reduce computational cost, we adopt the anchor-based strategy to construct the input similarity graphs. Then, we use the l 1 -norm to learn a high quality similarity graph adaptively from original similarity graphs which can make the final graph more robust than original ones. In addition, AGLMF uses symmetric non-negative matrix factorization to learn the final clustering indicators which can show the final consistent clustering result directly. Finally, experimental results on multiple multi-view datasets validate the effectiveness of the proposed algorithm when compared with previous multi-view spectral clustering algorithms. The demo code of this work is publicly available at https://github.com/theywq/AGLMF.git. [ABSTRACT FROM AUTHOR]

Spectral clustering is one of the most important clustering approaches, often yielding performance superior to other clustering approaches. However, it is not scalable to large data sets in its original form due to the computational burden of the required large-matrix eigen-decomposition. In this paper, a two-step spectral clustering algorithm is introduced by extending recent advances of scalable spectral clustering based on low-rank affinity matrix using landmarks. In the first step, a scalable spectral clustering algorithm using raw landmark-based affinity matrix is adopted. In the second step, a novel low-rank affinity matrix is learnt via the probability density estimators, constructed from the estimated clusters as derived from the first step. Since the prior information on cluster labels can be utilised in the second step, this learnt affinity matrix reflects intrinsic pairwise data relationships much better. While the proposed more complicated algorithm results in a higher computational cost than the previous landmark-based spectral research, it can be shown that the associated computational cost still scales well with data size. It is demonstrated that the proposed algorithm is capable of achieving far superior performance than other state-of-the-art algorithms for several benchmark multi-class image data sets. [ABSTRACT FROM AUTHOR]

In the context of multi-heterogeneous UAV coverage path planning, an effective solution method has been proposed. Firstly, regions are set up as fully connected graphs which are cut into multiple subgraphs by spectral clustering method to assign tasks to multi-heterogeneous UAVs. Additionally, an RL-based hyper-heuristic algorithm is proposed. Heuristic space is parameterized by GNN which is trained with the reward provided by the optimization goal to automate design and enhance the heuristic metrics, avoiding the inefficiency and suboptimality of expert design and manual parameter tuning. Compared with existing methods, the proposed algorithm has a better performance in task completion time, execution time and deviation rate, which shows its potential application in the coverage path planning problem of multi-heterogeneous UAVs. [ABSTRACT FROM AUTHOR]

Personalized document-level sentiment analysis (PDSA) plays an important role in many real-world applications. So far, various deep learning models for PDSA have been proposed. However, there has been no systematic survey in this area. To address this issue, in this paper, we overview the existing methods of PDSA, and propose a novel two-dimensional PDSA taxonomy. Specifically, in the dimension of attribute usage type , PDSA works are divided into two groups: (1) user-based and (2) user and product-based models. In the dimension of attribute processing method , PDSA works are divided into two groups: (1) feature-based and (2) relation-based models. To fill in the research blank indicated by the taxonomy, we further propose an architecture named User Correlation Mining (UCM) for PDSA. Specifically, UCM contains two components, namely Similar User Cluster Module (SUCM) and Triple Attributes BERT Model (TABM). SUCM is responsible for user clustering, and TABM aims to classify the user's sentiment based on the information of users, products, user clusters and user reviews. To evaluate the performances of the existing works as well as UCM, we conduct extensive experiments on three real-world datasets. The experiment results show that our proposed architecture UCM outperforms the other state-of-the-art methods. • To the best of our knowledge, this is the first survey of PDSA. • We propose a PDSA taxonomy, and summarize the ideas of existing works for each group. • We propose a model for PDSA based on user correlation to fill the existing vacancies. [ABSTRACT FROM AUTHOR]

Graph neural networks (GNN) recently have been successfully applied in wind power prediction by employing geo-information to construct the graphs that serve as the GNN-based prediction model. However, these graphs cannot maintain the latent correlation and attribute of the wind turbines, leading to inferior performance. This research proposes an optimizing wind power prediction model through attention mechanism and spatiotemporal graph neural networks. Initially, the spectral clustering and a self-adjacency matrix to construct the graph nodes and edges. Subsequently, the proposed ASTGNN combined from graph convolutional networks and a gated recurrent unit with an attention mechanism is designed to act as the prediction model. A comprehensive set of experiments has been carried out and the proposed method not only improved prediction accuracy but also enhanced computational efficiency. According to the results obtained, the developed model demonstrated an improvement that is up to 13 % in terms of RMSE and 6.7 % in terms of computation time compared to the latest models. [ABSTRACT FROM AUTHOR]

Current graph clustering methods emphasize individual node and edge connections, while ignoring higher-order organization at the level of motif. Recently, higher-order graph clustering approaches have been designed by motif-based hypergraphs. However, these approaches often suffer from hypergraph fragmentation issue seriously, which degrades the clustering performance greatly. Moreover, real-world graphs usually contain diverse motifs, with nodes participating in multiple motifs. A key challenge is how to achieve precise clustering results by integrating information from multiple motifs at the node level. In this paper, we propose a multi-order graph clustering model (MOGC) to integrate multiple higher-order structures and edge connections at node level. MOGC employs an adaptive weight learning mechanism to automatically adjust the contributions of different motifs for each node. This not only tackles hypergraph fragmentation issue but enhances clustering accuracy. MOGC is efficiently solved by an alternating minimization algorithm. Experiments on seven real-world datasets illustrate the effectiveness of MOGC. • We propose a multi-order graph clustering model to integrate multiple higher-order and lower-order structures at the node level. • An adaptive weight learning mechanism is formulated to automatically adjust the contributions of different motifs for each node. • We employ the model to solve fragmentation issue and achieve more accurate partition results simultaneously. • Extensive experiments show the outperformance of our proposed method. [ABSTRACT FROM AUTHOR]

Spectral clustering, a prominent unsupervised machine learning method, involves a critical task of constructing a similarity matrix. In existing approaches, this matrix is either computed once for all or updated alternatively. However, the former struggles to capture comprehensive relationships among data points, and the latter is often impractical for large-scale problems. This study introduces a new clustering framework with self-guidance and a block diagonal representation, retaining valuable information from previous cycles. To our knowledge, this is the first application of such a framework to spectral clustering, with a key distinction being the reclassification of samples in each cycle. To reduce computational overhead, we employ a block diagonal representation with Nyström approximation for constructing the similarity matrix. Theoretical results justify the rationality of approximate computations in spectral clustering. Comprehensive experiments on benchmark datasets demonstrate the superiority of our proposed algorithms over state-of-the-art methods for large-scale clustering. Notably, our framework has the potential to enhance clustering algorithms, performing well even with a randomly chosen initial guess. • First, we propose a restarted framework for large-scale spectral clustering. More precisely, we reclassify the samples to construct a new similarity matrix according to the clustering information just obtained, and run the spectral clustering method from scratch. We call this strategy restarting. • Second, to release the computation overhead and storage requirement for large-scale problems, we introduce a block diagonal representation for constructing the similarity matrix. More precisely, we make use of a block-diagonal similarity kernel matrix A, and the between cluster affinities are all zeros in the proposed method. • Third, a common disadvantage of the spectral embedding with spectral rotation method is the heavy workload for computing the clustering indicator matrix. Based on the correlation between vectors, we propose a new scheme for updating the clustering indicator matrix efficiently during cycles. [ABSTRACT FROM AUTHOR]

We consider the problem of spectral clustering under group fairness constraints, where samples from each sensitive group are approximately proportionally represented in each cluster. Traditional fair spectral clustering (FSC) methods consist of two consecutive stages, i.e., performing fair spectral embedding on a given graph and conducting k means to obtain discrete cluster labels. However, in practice, the graph is usually unknown, and we need to construct the underlying graph from potentially noisy data, the quality of which inevitably affects subsequent fair clustering performance. Furthermore, performing FSC through separate steps breaks the connections among these steps, leading to suboptimal results. To this end, we first theoretically analyze the effect of the constructed graph on FSC. Motivated by the analysis, we propose a novel graph construction method with a node-adaptive graph filter to learn graphs from noisy data. Then, all independent stages are integrated into a single objective function via a dual Laplacian framework, forming an end-to-end model that inputs raw data and outputs discrete cluster labels. An algorithm is developed to jointly and alternately update the variables in each stage. Finally, we conduct extensive experiments on synthetic, benchmark, and real data, which show that our model is superior to state-of-the-art fair clustering methods. • The effect of similarity graphs on fair spectral clustering is theoretically analyzed. • A graph construction method to learn graphs from potentially noisy data is proposed. • A dual Laplacian framework for unified fair spectral clustering is proposed. [ABSTRACT FROM AUTHOR]

Subspace clustering supposes that hyperspectral image (HSI) pixels lie in a union vector spaces of multiple sample subspaces without considering their dual space, i.e., spectral space. In this article, we propose a promising dual subspace clustering (DualSC) for improving spectral-spatial HSIs clustering by relaxing subspace clustering. To this end, DualSC simultaneously optimizes row and column subspace-representations of HSI superpixels to capture the intrinsic connection between spectral and spatial information. From the new perspective, the original subspace clustering can be treated as a special case of DualSC that has larger solution space, so tends to finding better sample representation matrix for applying spectral clustering. Besides, we provide theoretical proofs that show the proposed method relaxes the subspace space clustering with dual subspace, and can recover subspace-sparse representation of HSI samples. To the best of our knowledge, this work could be one of the first dual clustering method leveraging sample and spectral subspaces simultaneously. As a result, we conduct several clustering experiments on four canonical data sets, implying that our proposed method with strong interpretability reaches comparable performance and computing efficiency with other state-of-the-art methods. • Dual subspace clustering can capture spectral-spatial information of HSI. • Dual subspace clustering is a convex relaxation of subspace clustering. • Dual subspace clustering has sparse solution, good complexity and convergence. [ABSTRACT FROM AUTHOR]

Given the heterogeneous information of multiple views and the possible noise embedded in multi-view data, it is difficult to directly learn a consistent representation from multiple graphs to depict the intrinsic structure of all views. We propose a consistent graph learning method by exploiting both the high-order correlations underlying multiple views and the global structure of each single view. First, we calculate a transition probability matrix from each view. Second, a tensor is constructed by stacking each transition matrix as its frontal slice and then decomposed into the latent and error tensors. For the latent tensor, after rotated, a weighted tensor nuclear norm is used to encourage the rotate tensor to fully exploit the high-order correlations underlying multiple views. Furthermore, each frontal slice of the latent tensor is regularized by the nuclear norm to capture the global structure of each single view, and is restricted by probability constraints. Besides, we adopt the Frobenius-norm-based regularization to directly learn a common affinity matrix from the latent tensor. The established model is readily optimized by the alternating Lagrangian method. Extensive experiments on six real world datasets demonstrate that our method outperforms state-of-the-art methods. • The high-order correlations underlying multiple views are definitely exploited. • Simultaneously, the global structure of each single view is clearly captured. • The intrinsic affinity matrix shared by all views is directly learned. [ABSTRACT FROM AUTHOR]

The study of complex networks has significantly advanced our understanding of community structures which serves as a crucial feature of real-world graphs. Detecting communities in graphs is a challenging problem with applications in sociology, biology, and computer science. Despite the efforts of an interdisciplinary community of scientists, a satisfactory solution to this problem has not yet been achieved. This review article delves into the topic of community detection in graphs, which serves as a thorough exposition of various community detection methods from perspectives of modularity-based methods, spectral clustering, probabilistic modeling, and deep learning. Along with the methods, a new community detection method designed by us is also presented. Additionally, the performance of these methods on the datasets with and without ground truth is compared. In conclusion, this comprehensive review provides a deep understanding of community detection in graphs. • This review article provides a comprehensive exploration of the community detection methods which are grouped into modularity, spectral clustering, probabilistic modeling, and deep learning based methods. • The review contributes to a deep understanding of community detection in graphs and enhances our knowledge of network dynamics in complex systems. • The review also introduces a new community detection method, the Revised Medoid-Shift (RMS), designed to improve performance on non-Euclidean data structures like graphs. [ABSTRACT FROM AUTHOR]

In the past decade, multi-view clustering has become a research hot spot of machine learning. In traditional multi-view clustering methods, all views of the data points are assumed to be complete. However, in the practical applications, some views of data points may be missing and incomplete multi-view clustering methods are developed to handle these incomplete multi-view data. The existing incomplete multi-view clustering methods still have some defects such as insufficient use of missing information or neglecting the underlying relations among different views. To address these limitations, we propose an Anchor-based Incomplete Multi-view Spectral Clustering (AIMSC) approach. Specifically, AIMSC utilizes anchor points to connect all instances of each view and recover the missing information. Then, the similarities between all data points are derived from the similarities between data points and anchor points. Finally, anchor-based spectral clustering is executed to generate the clustering results. Experimental results on multiple benchmark datasets demonstrate the superiority of AIMSC. [ABSTRACT FROM AUTHOR]

Recently, 3D scenes parsing with deep learning approaches has been a heating topic. However, current methods with fully-supervised models require manually annotated point-wise supervision which is extremely user-unfriendly and time-consuming to obtain. As such, training 3D scene parsing models with sparse supervision is an intriguing alternative. We term this task as data-efficient 3D scene parsing and propose an effective two-stage framework named VIBUS to resolve it by exploiting the enormous unlabeled points. In the first stage, we perform self-supervised representation learning on unlabeled points with the proposed Viewpoint Bottleneck loss function. The loss function is derived from an information bottleneck objective imposed on scenes under different viewpoints, making the process of representation learning free of degradation and sampling. In the second stage, pseudo labels are harvested from the sparse labels based on uncertainty-spectrum modeling. By combining data-driven uncertainty measures and 3D mesh spectrum measures (derived from normal directions and geodesic distances), a robust local affinity metric is obtained. Finite gamma/beta mixture models are used to decompose category-wise distributions of these measures, leading to automatic selection of thresholds. We evaluate VIBUS on the public benchmark ScanNet and achieve state-of-the-art results on both validation set and online test server. Ablation studies show that both Viewpoint Bottleneck and uncertainty-spectrum modeling bring significant improvements. Codes and models are publicly available at https://github.com/AIR-DISCOVER/VIBUS. [ABSTRACT FROM AUTHOR]

Machine learning models based on sensitive data in the real-world promise advances in areas ranging from medical screening to disease outbreaks, agriculture, industry, defense science, and more. In many applications, learning participant communication rounds benefit from collecting their own private data sets, teaching detailed machine learning models on the real data, and sharing the benefits of using these models. Due to existing privacy and security concerns, most people avoid sensitive data sharing for training. Without each user demonstrating their local data to a central server, Federated Learning allows various parties to train a machine learning algorithm on their shared data jointly. This method of collective privacy learning results in the expense of important communication during training. Most large-scale machine learning applications require decentralized learning based on data sets generated on various devices and places. Such datasets represent an essential obstacle to decentralized learning, as their diverse contexts contribute to significant differences in the delivery of data across devices and locations. Researchers have proposed several ways to achieve data privacy in Federated Learning systems. However, there are still challenges with homogeneous local data. This research's approach is to select nodes (users) to share their data in Federated Learning for independent data-based equilibrium to improve accuracy, reduce training time, and increase convergence. Therefore, this research presents a combined Deep-Q-Reinforcement Learning Ensemble based on Spectral Clustering called DQRE-SCnet to choose a subset of devices in each communication round. Based on the results, it has been displayed that it is possible to decrease the number of communication rounds needed in Federated Learning. The realized reduction in the communication rounds are 51%, 25%, and 44% on the three datasets MNIST, Fashion MNIST, and CIFAR-10, respectively. [ABSTRACT FROM AUTHOR]

Spectral Clustering (SC) is an important method in areas such as data mining, image processing, computer science and so on. It attracts more and more attention owing to its effectiveness in unsupervised learning. However, SC has poor performance in the high-dimensional data. Traditional SC methods conduct the spectral embedding of the affinity matrix among data at the first beginning, and then obtain clustering results by the K -means clustering. The also have drawbacks int two processing steps: the clustering results are sensitive to the affinity matrix which may be inaccurate and the post-processing K -means may also be limited by its initialization problem. In the paper, a new approach which joints spectral embedding and clustering with structured graph optimization (called JSEGO) is proposed. In the new model, the low-dimensional representation of data can first be obtained by the spectral embedding method, which can handle with the high-dimensional data better. Then, the optimization similarity matrix would be obtained with such the embedded data. Furthermore, the learning structure graph gives feedback to the similarity matrix to generate better spectral embedded data. As a result, better similarity matrix and clustering result can be obtained by the iterations simultaneously, which are often conducted in two separate steps in the spectral clustering. As a result, the drawbacks introduced by the two processing introduces can be solved. At last, we use an alternative optimization method in the new model and conduct the theoretical analysis by comparing this proposed method with K -means clustering. Experiments based on synthetic data and actual benchmark data prove the advantage of this new approach. [ABSTRACT FROM AUTHOR]

Aiming at the problem of unlabeled ISAR image clustering of space targets, the paper proposes a new unsupervised clustering method based on adversarial autoencoder (AAE) and density peak-spectral clustering (Dpeak-SC). This method introduces the AAE into the unsupervised clustering problem of radar images for the first time and realizes the automatic extraction of the features of unlabeled space target ISAR image data. And on this basis, by combining the density peak algorithm with the spectral clustering algorithm, the ISAR image data is classified into multiple clusters with good clustering accuracy, clustering coincidence, and clustering similarity without providing any prior information. This method first implements the self-supervised training of the AAE model through the adversarial and reconstruction process. Then, it uses the trained encoder to extract the latent features of the ISAR image of the space target in the low-dimensional space. Next, a decision graph is constructed by calculating the local density and relative distance of the proposed features to determine the number of clusters in the hidden feature vector set. Finally, the spectral clustering algorithm is used to transform the problem into the graph's optimal partition problem. The clustering is realized by constructing and segmenting the undirected weight graph of the hidden feature vector set. The simulation test on the unlabeled space target ISAR image data verifies the method's effectiveness in this paper. [ABSTRACT FROM AUTHOR]

Spectral clustering is one of the most popular clustering methods. However, how to balance the efficiency and effectiveness of the large-scale spectral clustering with limited computing resources has not been properly solved for a long time. In this paper, we propose a divide-and-conquer based large-scale spectral clustering method to strike a good balance between efficiency and effectiveness. In the proposed method, a divide-and-conquer based landmark selection algorithm and a novel approximate similarity matrix approach are designed to construct a sparse similarity matrix within low computational complexities. Then clustering results can be computed quickly through a bipartite graph partition process. The proposed method achieves the lower computational complexity than most existing large-scale spectral clustering methods. Experimental results on ten large-scale datasets have demonstrated the efficiency and effectiveness of the proposed method. The MATLAB code of the proposed method and experimental datasets are available at https://github.com/Li-Hongmin/MyPaperWithCode. [ABSTRACT FROM AUTHOR]

High-dimensional data has attracted much attention because it contains more comprehensive information about samples. How to cluster these high-dimensional data has become a crucial topic in unsupervised learning. Existing clustering methods often show limited applicability due to their high computational complexity and low anti-noise ability. To address this issue, we propose a novel robust landmark graph-based clustering algorithm for high-dimensional data (RLGCH), which inherits the advantages of both k-means++ and graph-based clustering by using the results of k-means++ as pseudo labels for landmark graph-based clustering. In particular, RLGCH can achieve more reasonable clustering effectiveness than methods that just operate in the low-dimensional space or the original space since it performs k-means++ in the low-dimensional space and landmark graph-based spectral clustering in the original feature space. To avoid post-processing after optimization, the embedded factor matrix is constrained as an indicator matrix rather than a simple nonnegative matrix. To enhance the clustering robustness, the L 2 , 1 -norm is adopted to minimize the error of results between k-means++ and landmark graph-based clustering. To solve the model of RLGCH, we established a novel efficient optimization strategy to obtain all sample categories directly. Combining our clustering model and optimization strategy, the computational complexity is reduced to linear and insensitive to data dimensions. Extensive experiments on seven real-world datasets and sixteen noisy datasets show that compared with other state-of-the-art methods, RLGCH can improve the clustering efficiency and robustness greatly while guaranteeing comparable or even better clustering effectiveness. [ABSTRACT FROM AUTHOR]

In spectral clustering (SC), the clustering result highly depends on the similarity graph matrix. The k-nearest neighbors graph is a popular method to build the similarity graph matrix with a sparse structure for better graph cutting. However, many current methods require that the parameter k is specified by the user, and specifying an appropriate k for an unknown data set is often a difficult task. In this paper, we propose a new method for building the adaptive k-nearest neighbors similarity graph (AKNNG). The AKNNG specifies different k values for different data points to obtain a better graph structure. Specifically, it sets a maximum number of the nearest neighbors k max and assigns a different k value (k ⩽ k max ) for each data point. The k value is adjusted automatically by cutting some weak connections from each data point according to the m powers transform of the similarity graph. The experimental results on Spiral, Multi-clusters, Yale and Coil20 datasets have shown that when setting k max = 20 , the new method has improved the clustering accuracies of these four datasets over 4%, 6%, 4%, 5%, respectively, in comparison with those by the existing methods. The new method can also reduce the sensitiveness of the number of nearest neighbors, and build the similarity graph with less time. [ABSTRACT FROM AUTHOR]

This paper presents a straightforward yet novel approach to enhance graph-based information retrieval models, by calibrating the relationships between node terms, leading to better evaluation metrics at the retrieval phase, and by reducing the total size of the graph. This is achieved by integrating spectral clustering, embedding-based graph pruning and term re-weighting. Spectral clustering assigns each term to a specific cluster, allowing us to propose two pruning methods: out-cluster and in-cluster pruning based on node similarities. In-cluster pruning refers to pruning edges between terms within the same cluster, while out-cluster pruning refers to edges that connect different clusters. Both methods utilize spectral embeddings to assess node similarities, resulting in more manageable clusters termed concepts. These concepts are likely to contain semantically similar terms, with each term's concept defined as the centroid of its cluster. We show that this graph pruning strategy significantly enhances the performance and effectiveness of the overall model, reducing, at the same time, its graph sparsity. Moreover, during the retrieval phase, the conceptually calibrated centroids are used to re-weight terms generated by user queries, and the precomputed embeddings enable efficient query expansion through a k-Nearest Neighbors (K-NN) approach, offering substantial enhancement with minimal additional time cost. To the best of our knowledge, this is the first application of spectral clustering and embedding-based conceptualization to prune graph-based IR models. Our approach enhances both retrieval efficiency and performance while enabling effective query expansion with minimal additional computational overhead. Our proposed technique is applied across various graph-based information retrieval models, improving evaluation metrics and producing sparser graphs. • Integrates spectral clustering for effective graph pruning in information retrieval. • Proposes efficient query expansion using spectral embedding-based conceptualization. • Enhances retrieval model performance and reduces graph complexity and edge count. • Performs comparisons with prior implementations and state-of-the-art models. [ABSTRACT FROM AUTHOR]

Research concentrating on specific diseases or employing single datasets, such as medical histories and thematic data, has garnered considerable attention. However, there has been limited investigation into comorbidities. Although some ad-hoc methods have been utilized in the medical field, there is a scarcity of systematic approaches to address this challenge. The task of expressing patient features using heterogeneous and cross-domain data presents considerable difficulties. Directly mapping this data into a matrix frequently results in issues such as high dimensionality, sparsity, redundancy, and noise. Additionally, given the critical role of supervisory information in medicine, acquiring accurate information is paramount. To address these issues, we propose an enhanced clustering method that capitalizes on cross-domain knowledge augmentation. This method can iteratively learn clustering outcomes and cross-domain knowledge. The cross-domain knowledge matrix produced by our approach can be interpreted as a measure of similarity between instances across domains. We validate our proposed model in real-world electronic health records (EHR) data, and achieve significant performance improvement compared to the baseline method, successfully completing the task of exploring comorbidity. Due to the privacy of EHR data, we also conduct extensive experiments on the publicly available datasets DBLP and UCI. The experimental results show that our algorithm is superior to the baseline algorithm and has strong generality. • A new method for enhancing knowledge across domains has been proposed. • Comorbidities in electronic health records of patients has been explored. • The similarity between cross-domain data can be obtained. [ABSTRACT FROM AUTHOR]

Multi-view clustering has attracted increasing attention for handling complex data with multiple views or sources. Among them, spectral clustering-based methods become more and more popular due to it can make full use of information from different views. However, most existing multi-view spectral clustering methods typically adopt a two-step scheme, which firstly obtains the spectral embedding matrix through graph fusion or multi-feature fusion, and then uses the k-means algorithm to cluster the spectral embedding matrix to obtain the final clustering result. This two-step scheme inevitably leads to information loss, resulting in a suboptimal solution. Furthermore, the methods of graph fusion and multi-feature fusion have not taken into account the inconsistency of features between different views and the unordered nature of clustering labels, which also decreases the clustering performance. To solve these problems, we propose a novel one-step multi-view spectral clustering based on multi-feature similarity fusion. This model simultaneously conducts graph learning, multi-feature similarity fusion and discretization in a unified framework, which can mutually negotiate and optimize each other to achieve better results. Furthermore, compared to directly fusing affinity matrices or spectral embedding matrixs from different views, we take advantage of the property of the spectral embedding matrix, fuse the similarity of samples in feature space, better handle the differences between different views. Finally, the superiority of our method is verified by the experimental evaluation of several data sets. The demo code of this work is publicly available at https://github.com/kong-de-zheng/MOMSC. [Display omitted] • Introduce block diagonal constraint to make the affinity matrix accurately reflecting the data structure. • Fuse the features from different views, preserving the local structure and the consistency of multi-views. • Propose an one-step framework to optimize graph learning, multi-feature fusion and clustering. [ABSTRACT FROM AUTHOR]

Image segmentation methods based on clustering have become a advancement in the field of computer vision, and the performance of these methods mainly depends on the performance of the clustering algorithm. However, these methods have some shortcomings. First, a single feature cannot accurately obtain the complete information of the superpixels. Second, the commonly used Euclidean distance cannot extract the nonlinear manifold structure between superpixels. Third, the high-dimensional information between superpixels is not considered. Therefore, this article proposes a Tensor Multi-view Clustering Method for Natural Image Segmentation (TMCNIS), in which firstly the multiclass features of the superpixels are extracted to obtain complete information. Secondly, the Jensen–Shannon divergence is used to delineate the relationship between superpixels to obtain a more complete nonlinear structure. Thirdly, an adaptively weighted tensor Schatten-p norm is proposed to better approximate the target rank of the tensor. It also automatically shrinks the singular values appropriately to construct a finer tensor, thus fully capturing the spatial structure in the tensor. Experimental results on four clustering datasets and two image segmentation datasets demonstrate the superiority of TMCNIS compared to existing methods. • A new multi-view clustering method based on tensor Schatten-p norm was proposed. • The Jensen–Shannon divergence is used to obtain the nonlinear structure of data. • We apply the designed multi-view clustering method to natural image segmentation. [ABSTRACT FROM AUTHOR]

With the rapid development of online payment platforms, it is now possible to record massive transaction data. Clustering on transaction data significantly contributes to analyzing merchants' behavior patterns. This enables payment platforms to provide differentiated services or implement risk management strategies. However, traditional methods exploit transactions by generating low-dimensional features, leading to inevitable information loss. In this study, we use the empirical cumulative distribution of transactions to characterize merchants. We adopt Wasserstein distance to measure the dissimilarity between any two merchants and propose the Wasserstein-distance-based spectral clustering (WSC) approach. Based on the similarities between merchants' transaction distributions, a graph of merchants is generated. Thus, we treat the clustering of merchants as a graph-cut problem and solve it under the framework of spectral clustering. To ensure feasibility of the proposed method on large-scale datasets with limited computational resources, we propose a subsampling method for WSC (SubWSC). The associated theoretical properties are investigated to verify the efficiency of the proposed approach. The simulations and empirical study demonstrate that the proposed method outperforms feature-based methods in finding behavior patterns of merchants. • A novel spectral clustering method for empirical cumulative distribution functions. • Acceleration technique based on subsampling for large-scale datasets. • Exploring behavior patterns in transaction data with low information loss. [ABSTRACT FROM AUTHOR]

The traditional spectral clustering (SC) is an effective clustering method that can handle data with complex structure. SC essentially embeds data in another feature space with time-consuming spectral embedding before clustering, and has to re-embed the whole data when unseen data arrive, lacking the so-called out-of-sample-extension capability. SpectralNet (Shaham et al., 2018) is a pioneer attempt to resolve these two problems by training with random mini-batches to scale to large-scale data and by an orthogonal transformation layer to ensure orthogonality of embeddings and remove redundancy in features. However, the randomly selected data in each mini-batch might be far away from each other and fail to convey local structural information; the orthogonal transformation can only ensure orthogonality for each mini-batch instead of the whole data. In this paper, we propose a novel approach to address these two problems. By improving data selection for batches with batch augmentation using neighboring information, it helps the network to better capture local structural information. By devising core point guidance to exploit the spectral embeddings of representative points as prior information, it guides the network to learn embeddings that can better maintain the overall structures of data points. Empirical results show that our method resolves the two problems of SpectralNet and exhibits superior clustering performance to SpectralNet and other state-of-the-art deep clustering algorithms, while being able to generalize the embedding to unseen data. [ABSTRACT FROM AUTHOR]

• A method to identify fracture causes in composites based on acoustic emission and clusterization with reference datasets. • Three different single-mode-failure types are investigated experimentally with registering acoustic emission. • Clustering of the data from complex-mode-failure is realized based on single-mode failure reference data set. A new method to identify causes of fracture in composites based on acoustic emission (AE) and clusterization of AE data based on reference datasets is presented within the manuscript. Acoustic Emission (AE) is a widely used non-destructive method for fracture analysis, but data due to their multidimensionality are not easy to analyze especially if the acoustic events appear simultaneously and have similar parameters even if they are an effect of different failure mechanisms. In this research, we utilize an unsupervised learning algorithm besides the simplest K-means, through fuzzy c-means to Gaussian Mixture Model (GMM) and spectral clustering to investigate the dataset obtained from the three-point bending test manufactured by us composite. The analysis is preceded by data curation, feature determination (Laplacian score) and the best number of cluster investigations (DB index, Caliński-Harabasz score, and Silhouette method) To enable interpretation of the clustering we run an additional three groups of tests covering fibre breakage (two methods), resin fracture (in tension and in compression) and delamination (DCB test) creating reference datasets. These datasets were statistically analyzed and kernel density estimators were generated for each AE feature as well as amplitude-frequency characteristics. Clusters obtained for the main dataset were then assigned to particular causes of failure by comparing them with the reference dataset. It was found that clusters generated using spectral clustering were the most realistic ones, as it was possible to assign the cause of failure to them. [ABSTRACT FROM AUTHOR]

Ensemble clustering can obtain better and more robust results by fusing multiple base clusterings, which has received extensive attention. Although many representative algorithms have emerged in recent years, this field still has two tricky problems. First, spectral clustering can identify clusters of arbitrary shapes, but the high time and space complexity limit its application in generating base clusterings. Most existing algorithms utilize k-means to generate base clusterings, and the clustering effect on nonlinearly separable datasets needs further improvement. Second, ensemble clustering algorithms should generate multiple base clusterings. Even if low-complexity algorithms are applied, the running time is also long, which seriously affects the application of ensemble clustering algorithms on large-scale datasets. To tackle these problems, we propose a fast K-nearest neighbors approximation method, construct an anchor graph to approximate the similarity matrix, and use singular value decomposition (SVD) instead of eigenvalue decomposition (EVD) to reduce the time and space complexity of conventional spectral clustering. At the same time, we obtain multiple base clusterings by running spectral embedding once. Finally, we convert these base clusterings into a bipartite graph and use transfer cut to get the final clustering results. The proposed algorithms significantly reduce the running time of ensemble clustering. Experimental results on large-scale datasets fully prove the efficiency and superiority of our proposed algorithm. • We propose a fast ensemble clustering algorithm based on spectral clustering. • We propose a fast approximation method for K-nearest neighbors. • We utilize anchor graphs to accelerate similarity graph construction. • Our algorithm can obtain base clusterings by running spectral embedding once. [ABSTRACT FROM AUTHOR]

We propose and study an autocorrelation procedure designed to characterize and compare large sets of long time series. This time-domain procedure is contrasted with a frequency-domain approach that has recently been introduced and discussed in the literature. In both cases, instead of using all the information available from data, which would be computationally very expensive, adequate regularization rules select and summarize the most relevant information suitable for clustering purposes. Essentially, we suggest to use the autocorrelation coefficients of the time series that are only computed around the lags of greatest interest. Then, we study this method in several ways. We argue theoretically that fragmenting the autocorrelation function can have efficiency advantages when comparing time series. By means of a large simulation study, we show that the suggested procedure can condense the relevant information of the time series. We compare its results with those from the frequency domain counterpart. We further illustrate this procedure in a study of the evolution of several stock markets indices and show the effect of recent financial crises on the behaviour of these indices. [ABSTRACT FROM AUTHOR]

Anchor graphs are powerful tools for large-scale applications, but their quality depends on the selection of representative anchors, which is a difficult endeavor. Another challenge is to cluster data with incomplete multi-view features, which have missing values in some views. This paper proposes a novel method for incomplete multi-view clustering based on local and global bagging of anchor graphs. Our method does not require a specific anchor selection scheme but leverages bagging techniques to reduce the variance and discover the intrinsic anchor graph. Specifically, we first construct bagged partial anchor graphs for each incomplete view by randomly sampled anchors. Then, we integrate the bagged partial anchor graphs from multiple views into a unified and complete anchor graph. Finally, we apply global bagging to the unified anchor graph to further boost performance. Our method can generate robust anchor graphs for incomplete multi-view clustering scenarios, as evidenced by extensive experiments. • Bagging is exploited to learn robust intact anchor graph and ease difficult anchor selection. • Unstable anchor graphs induced by random anchors can be significantly enhanced with bagging. • Our method outperforms the state-of-the-art methods on six challenging datasets. [ABSTRACT FROM AUTHOR]

Multi-view Spectral Clustering (MvSC) partitions data into clusters according to multiple views for higher performance. However, most existing works overlook model interpretability and involve iterative and alternating updates on parameters with expensive computations, where out-of-sample predictions are also commonly prohibitive. In this paper, we construct a novel weighted conjugate feature duality for formulating the MvSC problem cast as a weighted principal components analysis. In this new method, a common latent space is derived with shared dual variables, which achieves the couplings by learning projections from different views into the latent space. To boost higher-order correlations, the tensor-based modeling is introduced. Our method leads to a closed-form solution in the dual through a single eigendecomposition thanks to the primal–dual representation, leading to easy algorithmic setups in practice. Our novel conjugate duality and the conceived shared latent space greatly boost the efficiency in model representation and computation: element-wise operations of kernels are involved in the dual instead of the explicit tensor computation in the primal and the size of our eigendecomposition is independent of the number of views. Besides, we can effectively incorporate the visualization of the clusters in a single latent space, which is particularly useful with many data views. For predicting unseen data under generic applications, our method can be flexibly applied with out-of-sample extensions, which can also be utilized for further efficiency in large-scale cases with fixed-size kernel schemes. Numerical experiments verify our superiority in accuracy, efficiency, and diverse data explorations. • A new method for MvSC is proposed via a novel conjugate feature duality. • With our duality, a common latent space can be imposed for different data sources. • A tensor-based modeling is derived for higher-order couplings and diversified fusion. • Our method gives an efficient representation and a closed-form solution in the dual. • Experiments verify our superiority in accuracy, efficiency, and interpretation. [ABSTRACT FROM AUTHOR]

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. • We propose a novel anchors generation method based on granular-ball computing. • We present an ensemble clustering algorithm and it is more efficient than U-SPEC. • The proposed algorithms can process millions of points on a commonly used PC. [ABSTRACT FROM AUTHOR]

Spectral clustering is widely employed for clustering data points, particularly for non-linear and non-convex structures in high-dimensional spaces. However, it faces challenges due to the high computational cost of eigen decomposition operations and the performance limitations with high-dimensional data. In this paper, we introduce BVA_LSC, a novel spectral clustering algorithm designed to address these challenges. Firstly, we incorporate an advanced feature reduction stage utilizing Barnes-Hut t-SNE and a deep Variational Autoencoder (VAE) to efficiently reduce the dimensionality of the data, thereby accelerating eigen decomposition. Secondly, we propose an adaptive landmark selection strategy that combines the Grey Wolf Optimizer (GWO) with a novel objective function and K-harmonic means clustering. This strategy dynamically determines an optimal number of landmarks, enhancing the representativeness of the data and reducing the size of the similarity matrix. We assess the performance of our algorithm on various standard datasets, demonstrating its superiority over state-of-the-art methods in terms of accuracy and efficiency. • A hybrid spectral clustering approach combining Enhanced feature reduction and adaptive landmarks selection was proposed. • Dimensionality reduction was achieved through Barnes-Hut t-SNE and non-linear Variational Autoencoder techniques, effectively. • The K-harmonic means algorithm is followed by grey wolf optimization with a new defined objective function. • A new equation is introduced to dynamically select the optimal number of landmarks based on the dataset's features. [ABSTRACT FROM AUTHOR]

Automatic classification methods widely used for diagnosing and analyzing COVID-19 cases. These methods assume known labels and rely on a single view of the dataset. Given the prevalence of COVID-19 cases and the extensive volume of patient records lacking labels, this communication underscores our unique approach—conducting the first study on COVID-19 case diagnosis in an unsupervised manner. Our work operates under the assumption of prior knowledge regarding the number of classes, such as COVID-19, pneumonia, and normal, in a case study. By adopting an unsupervised learning paradigm, we leverage the wealth of unlabeled data, reducing dependence on human experts for annotating numerous images. This paper introduces an enhanced version of a recent direct method where non-negative cluster indices and spectral embeddings are jointly estimated. Beyond the inherent advantages of this method, our proposed model introduces improvements through two additional types of constraints: (i) ensuring consistent smoothing of cluster labels across all views and (ii) imposing an orthogonality constraint on the matrix of cluster assignments. The efficacy of the proposed method is demonstrated using the public COVIDx dataset with three classes, showcasing promising results in categorizing radiographs. The proposed approach is tested on other public image datasets to assess its effectiveness. [ABSTRACT FROM AUTHOR]

In recent decades, spectral clustering has found widespread applications in various real-world scenarios, showcasing its effectiveness. Traditional spectral clustering typically follows a two-step procedure to address the optimization problem. However, this approach may result in substantial information loss and performance decline. Furthermore, the eigenvalue decomposition, a key step in spectral clustering, entails cubic computational complexity. This paper incorporates linear embedding into the objective function of spectral clustering and proposes a direct method to solve the indicator matrix. Moreover, our method achieves a linear time complexity with respect to the input data size. Our method, referred to as Spectral Clustering with Linear Embedding (SCLE), achieves a direct and efficient solution and naturally handles out-of-sample data. SCLE initiates the process with balanced and hierarchical K-means, effectively partitioning the input data into balanced clusters. After generating anchors, we compute a similarity matrix based on the distances between the input data points and the generated anchors. In contrast to the conventional two-step spectral clustering approach, we directly solve the cluster indicator matrix at a linear time complexity. Extensive experiments across multiple datasets underscore the efficiency and effectiveness of our proposed SCLE method. • Addressing spectral clustering time issues with a faster graph construction method. • Eliminating eigendecomposition, our approach saves computational time. • Avoiding intermediate variables, our method prevents information loss in updates. • Our algorithm achieves direct clustering matrix solution in linear time. [ABSTRACT FROM AUTHOR]

• This paper introduces the basic concept of graph theory, reviews the properties of Laplacian matrix and the traditional graph cuts method. Starting from four aspects in the realization process of spectral clustering (construction of similarity matrix, establishment of Laplacian matrix, selection of eigenvectors, and determination of the number of clusters), we have summarized in detail some representative algorithms in recent years. • Some successful applications of spectral clustering are summarized. In each aspect, the shortcomings of spectral clustering and some representative improved algorithms are emphatically analyzed. • This paper comprehensively analyzes some research on spectral clustering that has not yet been in-depth, and gives prospects on some valuable research directions. Spectral clustering converts the data clustering problem to the graph cut problem. It is based on graph theory. Due to the reliable theoretical basis and good clustering performance, spectral clustering has been successfully applied in many fields. Although spectral clustering has many advantages, it faces the challenges of high time and space complexity when dealing with large scale complex data. Firstly, this paper introduces the basic concept of graph theory, reviews the properties of Laplacian matrix and the traditional graph cuts method. Then, it focuses on four aspects of the realization process of spectral clustering, including the construction of similarity matrix, the establishment of Laplacian matrix, the selection of eigenvectors and the determination of the number of clusters. In addition, some successful applications of spectral clustering are summarized. In each aspect, the shortcomings of spectral clustering and some representative improved algorithms are emphatically analyzed. Finally, the paper comprehensively analyzes some research on spectral clustering that has not yet been in-depth, and gives prospects on some valuable research directions. [ABSTRACT FROM AUTHOR]

High dimensional and small samples characterize gene expression data and contain a large number of genes unrelated to disease. Feature selection improves the efficiency of disease diagnosis by selecting a small number of important genes. Unfortunately, existing algorithms do not consider the correlation between features, and search algorithms tend to fall into the local optimal solution in the feature search process. To this end, this paper proposes a feature filter and group evolution hybrid feature selection algorithm (FG-HFS) for high-dimensional gene expression data. Unlike existing algorithms, we propose using spectral clustering to group redundant features into a group. Then, we propose a redundant feature filter algorithm. According to the principle of approximate Markov blanket, grouped feature groups are filtered to delete these redundant features. Among them, filtered features are evenly divided by density according to the feature exponential strategy. Most importantly, we propose using the group evolution multi-objective genetic algorithm to search the filtered feature subsets and evaluate the candidate feature subsets according to the in-group and out-group so as to select the feature subsets with the highest accuracy and the least number. Experimental results show that the average accuracy (ACC) and Matthews correlation coefficient (MCC) indexes of the selected feature subsets (FSs) by the FG-HFS algorithm on 5 gene expression datasets are 92.76% and 88.76%, respectively, which are significantly better than the existing algorithms. In addition, the FSs and ACC/FSs indexes of the FG-HFS algorithm are also better than the existing algorithms, which fully proves the superiority of the FG-HFS algorithm. More importantly, the Wilcoxon and Friedman statistical experiments results show that the feature selection effect of FG-HFS algorithm is significantly better than that of existing algorithms, no matter in pairwise comparison or multiple comparison. • We propose using spectral clustering to group the features so that the in-group feature similarity is extremely high. • We propose a redundant feature filter algorithm since existing algorithms cannot filter redundant features. • we propose using the group evolution multi-objective genetic algorithm to search the filtered feature subsets. [ABSTRACT FROM AUTHOR]