Search

These days, clustering is one of the most classical themes to analyze data structures in machine learning and pattern recognition. Recently, the anchor-based graph has been widely adopted to promote the clustering accuracy of plentiful graph-based clustering techniques. In order to achieve more satisfying clustering performance, we propose a novel clustering approach referred to as the progressive self-supervised clustering method with novel category discovery (PSSCNCD), which consists of three separate procedures specifically. First, we propose a new semisupervised framework with novel category discovery to guide label propagation processing, which is reinforced by the parameter-insensitive anchor-based graph obtained from balanced $K$ -means and hierarchical $K$ -means (BKHK). Second, we design a novel representative point selected strategy based on our semisupervised framework to discover each representative point and endow pseudolabel progressively, where every pseudolabel hypothetically corresponds to a real category in each self-supervised label propagation. Third, when sufficient representative points have been found, the labels of all samples will be finally predicted to obtain terminal clustering results. In addition, the experimental results on several toy examples and benchmark data sets comprehensively demonstrate that our method outperforms other clustering approaches. [ABSTRACT FROM AUTHOR]

Graph-based clustering aims to partition the data according to a similarity graph, which has shown impressive performance on various kinds of tasks. The quality of similarity graph largely determines the clustering results, but it is difficult to produce a high-quality one, especially when data contain noises and outliers. To solve this problem, we propose a robust rank constrained sparse learning (RRCSL) method in this article. The $L_{2,1}$ -norm is adopted into the objective function of sparse representation to learn the optimal graph with robustness. To preserve the data structure, we construct an initial graph and search the graph within its neighborhood. By incorporating a rank constraint, the learned graph can be directly used as the cluster indicator, and the final results are obtained without additional postprocessing. In addition, the proposed method cannot only be applied to single-view clustering but also extended to multiview clustering. Plenty of experiments on synthetic and real-world datasets have demonstrated the superiority and robustness of the proposed framework. [ABSTRACT FROM AUTHOR]

The multiple kernel $k$ -means (MKKM) and its variants utilize complementary information from different sources, achieving better performance than kernel $k$ -means (KKM). However, the optimization procedures of most previous works comprise two stages, learning the continuous relaxation matrix and obtaining the discrete one by extra discretization procedures. Such a two-stage strategy gives rise to a mismatched problem and severe information loss. Even worse, most existing MKKM methods overlook the correlation among prespecified kernels, which leads to the fusion of mutually redundant kernels and bad effects on the diversity of information sources, finally resulting in unsatisfying results. To address these issues, we elaborate a novel Discrete and Parameter-free Multiple Kernel $k$ -means (DPMKKM) model solved by an alternative optimization method, which can directly obtain the cluster assignment results without subsequent discretization procedure. Moreover, DPMKKM can measure the correlation among kernels by implicitly introducing a regularization term, which is able to enhance kernel fusion by reducing redundancy and improving diversity. Noteworthily, the time complexity of optimization algorithm is successfully reduced, through masterly utilizing of coordinate descent technique, which contributes to higher algorithm efficiency and broader applications. What’s more, our proposed model is parameter-free avoiding intractable hyperparameter tuning, which makes it feasible in practical applications. Lastly, extensive experiments conducted on a number of real-world datasets illustrated the effectiveness and superiority of the proposed DPMKKM model. [ABSTRACT FROM AUTHOR]

Fuzzy clustering is one of the most popular clustering approaches and has attracted considerable attention in many fields. However, high computational cost has become a bottleneck which limits its applications in large-scale problems. Moreover, most fuzzy clustering algorithms are sensitive to noise. To address these issues, a novel fuzzy clustering algorithm, called fast fuzzy clustering based on anchor graph (FFCAG), is proposed. The FFCAG algorithm integrates anchor-based similarity graph construction and membership matrix learning into a unified framework, such that the prior knowledge of anchors can be further utilized to improve clustering performance. Specifically, FFCAG first constructs an anchor-based similarity graph with a parameter-free neighbor assignment strategy. Then, it designs a quadratic programming model to learn the membership matrix of anchors, which is very different from traditional fuzzy clustering algorithms. More importantly, a novel balanced regularization term is introduced into the objective function to produce more accurate clustering results. Finally, we adopt an alternating optimization algorithm with guaranteed convergence to solve the proposed method. Experimental results performed on synthetic and real-world datasets demonstrate the proposed FFCAG can significantly reduce the computational time with comparable, even superior, clustering performance, compared with state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

$k$ k -means method using Lloyd heuristic is a traditional clustering method which has played a key role in multiple downstream tasks of machine learning because of its simplicity. However, Lloyd heuristic always finds a bad local minimum, i.e., the bad local minimum makes objective function value not small enough, which limits the performance of $k$ k -means. In this paper, we use coordinate descent (CD) method to solve the problem. First, we show that the $k$ k -means minimization problem can be reformulated as a trace maximization problem, then a simple and efficient coordinate descent scheme is proposed to solve the maximization problem. Two interesting findings through theory are that Lloyd cannot decrease the objective function value of $k$ k -means produced by our CD further, and our proposed method CD to solve $k$ k -means problem can avoid produce empty clusters. In addition, according to the computational complexity analysis, it is verified CD has the same time complexity with original $k$ k -means method. Extensive experiments including statistical hypothesis testing, on several real-world datasets with varying number of clusters, varying number of samples and varying number of dimensions show that CD performs better compared to Lloyd, i.e., lower objective value, better local minimum and fewer iterations. And CD is more robust to initialization than Lloyd whether the initialization strategy is random or initialization of $k$ k -means++. [ABSTRACT FROM AUTHOR]

Spectral clustering methods are gaining more and more interests and successfully applied in many fields because of their superior performance. However, there still exist two main problems to be solved: 1) spectral clustering methods consist of two successive optimization stages—spectral embedding and spectral rotation, which may not lead to globally optimal solutions, 2) and it is known that spectral methods are time-consuming with very high computational complexity. There are methods proposed to reduce the complexity for data vectors but not for graphs that only have information about similarity matrices. In this paper, we propose a new method to solve these two challenging problems for graph clustering. In the new method, a new framework is established to perform spectral embedding and spectral rotation simultaneously. The newly designed objective function consists of both terms of embedding and rotation, and we use an improved spectral rotation method to make it mathematically rigorous for the optimization. To further accelerate the algorithm, we derive a low-dimensional representation matrix from a graph by using label propagation, with which, in return, we can reconstruct a double-stochastic and positive semidefinite similarity matrix. Experimental results demonstrate that our method has excellent performance in time cost and accuracy. [ABSTRACT FROM AUTHOR]

Due to the multimodality of non-Gaussian data, traditional globality-preserved dimensionality reduction (DR) methods, such as linear discriminant analysis (LDA) and principal component analysis (PCA) are difficult to deal with. In this paper, we present a novel local DR framework via auto-optimized graph embedding to extract the intrinsic submanifold structure of multimodal data. Specifically, the proposed model seeks to learn an embedding space which can preserve the local neighborhood structure by constructing a ${k}$ -nearest neighbors (${k}$ NNs) graph on data points. Different than previous works, our model employs the $\boldsymbol {\ell }_{\boldsymbol {0}}$ -norm constraint and binary constraint on the similarity matrix to impose that there only be a ${k}$ nonzero value in each row of the similarity matrix, which can ensure the ${k}$ -connectivity in graph. More important, as the high-dimensional data probably contains some noises and redundant features, calculating the similarity matrix in the original space by using a kernel function is inaccurate. As a result, a mechanism of an auto-optimized graph is derived in the proposed model. Concretely, we learn the embedding space and similarity matrix simultaneously. In other words, the selection of neighbors is automatically executed in the optimal subspace rather than in the original space when the algorithm reaches convergence, which can alleviate the affect of noises and improve the robustness of the proposed model. In addition, four supervised and semisupervised local DR methods are derived by the proposed framework which can extract the discriminative features while preserving the submanifold structure of data. Last but not least, since two variables need to be optimized simultaneously in the proposed methods, and the constraints on the similarity matrix are difficult to satisfy, which is an NP-hard problem. Consequently, an efficient iterative optimization algorithm is introduced to solve the proposed problems. Extensive experiments conducted on synthetic data and several real-world datasets have demonstrated the advantages of the proposed methods in robustness and recognition accuracy. [ABSTRACT FROM AUTHOR]

Spectral clustering is an important clustering method widely used for pattern recognition and image segmentation. Classical spectral clustering algorithms consist of two separate stages: 1) solving a relaxed continuous optimization problem to obtain a real matrix followed by 2) applying ${K}$ -means or spectral rotation to round the real matrix (i.e., continuous clustering result) into a binary matrix called the cluster indicator matrix. Such a separate scheme is not guaranteed to achieve jointly optimal result because of the loss of useful information. To obtain a better clustering result, in this paper, we propose a joint model to simultaneously compute the optimal real matrix and binary matrix. The existing joint model adopts an orthonormal real matrix to approximate the orthogonal but nonorthonormal cluster indicator matrix. It is noted that only in a very special case (i.e., all clusters have the same number of samples), the cluster indicator matrix is an orthonormal matrix multiplied by a real number. The error of approximating a nonorthonormal matrix is inevitably large. To overcome the drawback, we propose replacing the nonorthonormal cluster indicator matrix with a scaled cluster indicator matrix which is an orthonormal matrix. Our method is capable of obtaining better performance because it is easy to minimize the difference between two orthonormal matrices. Experimental results on benchmark datasets demonstrate the effectiveness of the proposed method (called JSESR). [ABSTRACT FROM AUTHOR]

Spectral clustering has been playing a vital role in various research areas. Most traditional spectral clustering algorithms comprise two independent stages (e.g., first learning continuous labels and then rounding the learned labels into discrete ones), which may cause unpredictable deviation of resultant cluster labels from genuine ones, thereby leading to severe information loss and performance degradation. In this work, we study how to achieve discrete clustering as well as reliably generalize to unseen data. We propose a novel spectral clustering scheme which deeply explores cluster label properties, including discreteness, nonnegativity, and discrimination, as well as learns robust out-of-sample prediction functions. Specifically, we explicitly enforce a discrete transformation on the intermediate continuous labels, which leads to a tractable optimization problem with a discrete solution. Besides, we preserve the natural nonnegative characteristic of the clustering labels to enhance the interpretability of the results. Moreover, to further compensate the unreliability of the learned clustering labels, we integrate an adaptive robust module with \ell 2,p loss to learn prediction function for grouping unseen data. We also show that the out-of-sample component can inject discriminative knowledge into the learning of cluster labels under certain conditions. Extensive experiments conducted on various data sets have demonstrated the superiority of our proposal as compared to several existing clustering approaches. [ABSTRACT FROM PUBLISHER]

Finding overlapping communities from multimedia social networks is an interesting and important problem in data mining and recommender systems. However, extant overlapping community discovery with swarm intelligence often generates overlapping community structures with superfluous small communities. To deal with the problem, in this paper, an efficient algorithm (LEPSO) is proposed for overlapping communities discovery, which is based on line graph theory, ensemble learning, and particle swarm optimization (PSO). Specifically, a discrete PSO, consisting of an encoding scheme with ordered neighbors and a particle updating strategy with ensemble clustering, is devised for improving the optimization ability to search communities hidden in social networks. Then, a postprocessing strategy is presented for merging the finer-grained and suboptimal overlapping communities. Experiments on some real-world and synthetic datasets show that our approach is superior in terms of robustness, effectiveness, and automatically determination of the number of clusters, which can discover overlapping communities that have better quality than those computed by state-of-the-art algorithms for overlapping communities detection. [ABSTRACT FROM PUBLISHER]

Low-rank representation (LRR) has been successfully applied in exploring the subspace structures of data. However, in previous LRR-based semi-supervised subspace clustering methods, the label information is not used to guide the affinity matrix construction so that the affinity matrix cannot deliver strong discriminant information. Moreover, these methods cannot guarantee an overall optimum since the affinity matrix construction and subspace clustering are often independent steps. In this paper, we propose a robust semi-supervised subspace clustering method based on non-negative LRR (NNLRR) to address these problems. By combining the LRR framework and the Gaussian fields and harmonic functions method in a single optimization problem, the supervision information is explicitly incorporated to guide the affinity matrix construction and the affinity matrix construction and subspace clustering are accomplished in one step to guarantee the overall optimum. The affinity matrix is obtained by seeking a non-negative low-rank matrix that represents each sample as a linear combination of others. We also explicitly impose the sparse constraint on the affinity matrix such that the affinity matrix obtained by NNLRR is non-negative low-rank and sparse. We introduce an efficient linearized alternating direction method with adaptive penalty to solve the corresponding optimization problem. Extensive experimental results demonstrate that NNLRR is effective in semi-supervised subspace clustering and robust to different types of noise than other state-of-the-art methods. [ABSTRACT FROM PUBLISHER]

A novel superpixel extraction algorithm using a higher order energy optimization framework is proposed in this paper. We first adopt the $k$ -means clustering technique to quickly get an initial superpixel result. Then a higher order energy function is employed to optimize and refine these initial superpixels. We use a more general higher order energy function that includes a first-order data term, a second-order smoothness term, and a higher order term. The presegments are employed to provide the prior information of sufficient edges and segment regions for our higher order energy term. According to the texture measurement in different local regions, our algorithm adaptively computes the proper ratios of different energy terms to obtain a better superpixel performance. The experimental results demonstrate that our method using the higher order energy generates better results with well-aligned boundaries and homogeneous effects than the existing superpixel algorithms. [ABSTRACT FROM PUBLISHER]