Anchor graph clustering has gained significant attention due to its effectiveness and efficiency. As the most representative points in original data, anchors are applied to connect the sample space to label space. However, when noise is present in original data, the anchor-refined label spreading mechanism may fail. To address this, we propose an Efficient Co-clustering via Anchor-refined Label Spreading (ECALS), which simultaneously clusters original data and anchors. We introduce the size constraint that ensures each cluster contains a minimum number of samples. Our method includes two variants, which are continuous and discrete model, catering to both fuzzy and discrete label matrices. Both models are applicable to out-of-sample problems and demonstrate superior performance on synthetic and real-world datasets.

Anchor-based clustering methods have gained attention for their efficiency in subspace, multi-view, and ensemble clustering tasks. Most existing methods focus on using anchors to reduce computational complexity in the original data space. However, clustering directly on anchors, followed by label propagation to the original data, can significantly improve computational efficiency. In this paper, we propose an Efficient Anchor Graph Clustering (EAGC) method that maximizes within-cluster homogeneity among anchors. Inspired by the relaxation and discretization model in spectral clustering, we propose two corresponding models, namely EAGC-R and EAGC-D. EAGC-R first obtains relaxed spectral embedding of anchors and then the embedding is discretized by K-Means. EAGC-D directly solves the discrete anchor membership matrix by coordinate descent method. Once anchor clustering results are obtained, original data labels can be obtained through anchor label transmission. Extensive experiments conducted on both synthetic and real datasets illustrate the effectiveness of proposed methods.

Anchor-based clustering methods have attracted increasing attention due to their ability to provide efficient and scalable solutions in clustering tasks, such as subspace, multi-view and ensemble clustering. Nevertheless, the majority of anchor-based methods view anchors merely as tools, concentrating on diminishing computational complexity within original data space. However, in fact, clustering can be directly performed on anchors and then the anchor clustering results could be propagated to original data. Due to the much smaller volume of anchors, this could significantly reduce the computational complexity of clustering algorithms. Building upon this idea, in this paper, we propose a fast anchor graph clustering method (FAGC) via maximizing within-cluster similarity. Inspired by the relaxation and discretization model in spectral clustering, we also propose two corresponding models, namely FAGC-R and FAGC-D. FAGC-R first obtains spectral embedding of anchors and then discretizes the embedding to obtain anchor indicator matrix. While FAGC-D directly solves the discrete anchor membership matrix. Once anchor clustering results are obtained, original data labels can be obtained through anchor label transmission. Extensive experiments conducted on synthetic and real datasets illustrate the effectiveness and efficiency of the proposed methods.

Clustering is a fundamental topic in machine learning and various methods are proposed, in which K-Means (KM) and min cut clustering are typical ones. However, they may produce empty or skewed clustering results, which are not as expected. In KM, the constrained clustering methods have been fully studied while in min cut clustering, it still needs to be developed. In this paper, we propose a parameter-insensitive min cut clustering with flexible size constraints. Specifically, we add lower limitations on the number of samples for each cluster, which can perfectly avoid the trivial solution in min cut clustering. As far as we are concerned, this is the first attempt of directly incorporating size constraints into min cut. However, it is a NP-hard problem and difficult to solve. Thus, the upper limits is also added in but it is still difficult to solve. Therefore, an additional variable that is equivalent to label matrix is introduced in and the augmented Lagrangian multiplier (ALM) is used to decouple the constraints. In the experiments, we find that the our algorithm is less sensitive to lower bound and is practical in image segmentation. A large number of experiments demonstrate the effectiveness of our proposed algorithm.

As a simple yet effective method, least squares regression (LSR) is extensively applied for data regression and classification. Combined with sparse representation, LSR can be extended to feature selection (FS) as well, in which$\ell_{1}$regularization is often applied in embedded FS algorithms. However, because the loss function is in the form of squared error, LSR and its variants are sensitive to noises, which significantly degrades the effectiveness and performance of classification and FS. To cope with the problem, we propose a generalized and robust LSR (GRLSR) for classification and FS, which is made up of arbitrary concave loss function and the$\ell_{2,p}$-norm regularization term. Meanwhile, an iterative algorithm is applied to efficiently deal with the nonconvex minimization problem, in which an additional weight to suppress the effect of noises is added to each data point. The weights can be automatically assigned according to the error of the samples. When the error is large, the value of the corresponding weight is small. It is this mechanism that allows GRLSR to reduce the impact of noises and outliers. According to the different formulations of the concave loss function, four specific methods are proposed to clarify the essence of the framework. Comprehensive experiments on corrupted datasets have proven the advantage of the proposed method.

Least squares regression (LSR) is widely applied in statistics theory due to its theoretical solution, which can be used in supervised, semisupervised, and multiclass learning. However, LSR begins to fail and its discriminative ability cannot be guaranteed when the original data have been corrupted and noised. In reality, the noises are unavoidable and could greatly affect the error construction in LSR. To cope with this problem, a robust supervised LSR (RSLSR) is proposed to eliminate the effect of noises and outliers. The loss function adopts$\ell _{2,p}$-norm ($0< p\leq 2$) instead of square loss. In addition, the probability weight is added to each sample to determine whether the sample is a normal point or not. Its physical meaning is very clear, in which if the point is normal, the probability value is 1; otherwise, the weight is 0. To effectively solve the concave problem, an iterative algorithm is introduced, in which additional weights are added to penalize normal samples with large errors. We also extend RSLSR to robust semisupervised LSR (RSSLSR) to fully utilize the limited labeled samples. A large number of classification performances on corrupted data illustrate the robustness of the proposed methods.

High-dimensional data are highly correlative and redundant, making it difficult to explore and analyze. Amount of unsupervised dimensionality reduction (DR) methods has been proposed, in which constructing a neighborhood graph is the primary step of DR methods. However, there exist two problems: 1) the construction of graph is usually separate from the selection of projection direction and 2) the original data are inevitably noisy. In this article, we propose an unsupervised adaptive embedding (UAE) method for DR to solve these challenges, which is a linear graph-embedding method. First, an adaptive allocation method of neighbors is proposed to construct the affinity graph. Second, the construction of affinity graph and calculation of projection matrix are integrated together. It considers the local relationship between samples and global characteristic of high-dimensional data, in which the cleaned data matrix is originally proposed to remove noise in subspace. The relationship between our method and local preserving projections (LPPs) is also explored. Finally, an alternative iteration optimization algorithm is derived to solve our model, the convergence and computational complexity of which are also analyzed. Comprehensive experiments on synthetic and benchmark datasets illustrate the superiority of our method.