基于Nystrom谱聚类的词典学习

构建视觉词典是BOVW模型中关键的一个步骤,目前大多数视觉词典是基于K-means聚类方式构建。然而由于K-means聚类的局限性以及样本空间结构的复杂性与高维性,这种方式构建的视觉词典往往区分性能较差。在谱聚类的框架下,提出一种区分性能更强的视觉词典学习算法,为了减少特征在量化过程中区分性能的降低以及谱聚类固有的存储计算问题,算法根据训练样本的类别标签对训练数据进行划分,基于Nystrom谱聚类得到各子样本数据集的中心并得到最终的视觉词典。在Scene-15数据集上的实验结果验证了算法的正确性和有效性。特别当训练样本有限时,采用该算法生成的视觉词典性能较优。     

Semidefinite spectral clustering

Multi-way partitioning of an undirected weighted graph where pairwise similarities are assigned as edge weights, provides an important tool for data clustering, but is an NP-hard problem. Spectral relaxation is a popular way of relaxation, leading to spectral clustering where the clustering is performed by the eigen-decomposition of the (normalized) graph Laplacian. On the other hand, semidefinite relaxation, is an alternative way of relaxing a combinatorial optimization, leading to a convex optimization. In this paper we employ a semidefinite programming (SDP) approach to the graph equipartitioning for clustering, where sufficient conditions for strong duality hold. The method is referred to as semidefinite spectral clustering, where the clustering is based on the eigen-decomposition of the optimal feasible matrix computed by SDP. Numerical experiments with several data sets, demonstrate the useful behavior of our semidefinite spectral clustering, compared to existing spectral clustering methods.     

Local density adaptive similarity measurement for spectral clustering

Similarity measurement is crucial to the performance of spectral clustering. The Gaussian kernel function is usually adopted as the similarity measure. However, with a fixed kernel parameter, the similarity between two data points is only determined by their Euclidean distance, and is not adaptive to their surroundings. In this paper, a local density adaptive similarity measure is proposed, which uses the local density between two data points to scale the Gaussian kernel function. The proposed similarity measure satisfies the clustering assumption and has an effect of amplifying intra-cluster similarity, thus making the affinity matrix clearly block diagonal. Experimental results on both synthetic and real world data sets show that the spectral clustering algorithm with our local density adaptive similarity measure outperforms the traditional spectral clustering algorithm, the path-based spectral clustering algorithm and the self-tuning spectral clustering algorithm.     

Landmark selection for spectral clustering based on Weighted PageRank

Spectral clustering methods have various real-world applications, such as face recognition, community detection, protein sequences clustering etc. Although spectral clustering methods can detect arbitrary shaped clusters, resulting thus in high clustering accuracy, the heavy computational cost limits their scalability. In this paper, we propose an accelerated spectral clustering method based on landmark selection. According to the Weighted PageRank algorithm, the most important nodes of the data affinity graph are selected as landmarks. Furthermore, the selected landmarks are provided to a landmark spectral clustering technique to achieve scalable and accurate clustering. In our experiments, by using two benchmark face and shape image data sets, we examine several landmark selection strategies for scalable spectral clustering that either ignore or consider the topological properties of the data in the affinity graph. Also, we show that the proposed method outperforms baseline and accelerated spectral clustering methods, in terms of computational cost and clustering accuracy, respectively. Finally, we provide future directions in spectral clustering.     

结合谱聚类的标记分布学习

标记分布是一种新的学习范式,现有算法大多数直接使用条件概率建立参数模型,未充分考虑样本之间的相关性,导致计算复杂度增大。基于此,引入谱聚类算法,通过样本之间相似性关系将聚类问题转化为图的全局最优划分问题,进而提出一种结合谱聚类的标记分布学习算法（label distribution learning with spectral clustering,SC-LDL）。首先,计算样本相似度矩阵;然后,对矩阵进行拉普拉斯变换,构造特征向量空间;最后,通过K-means算法对数据进行聚类建立参数模型,预测未知样本的标记分布。与现有算法在多个数据集上的实验表明,本算法优于多个对比算法,统计假设检验进一步说明算法的有效性和优越性。     

Incremental spectral clustering by efficiently updating the eigen-system

In recent years, the spectral clustering method has gained attentions because of its superior performance. To the best of our knowledge, the existing spectral clustering algorithms cannot incrementally update the clustering results given a small change of the data set. However, the capability of incrementally updating is essential to some applications such as websphere or blogsphere. Unlike the traditional stream data, these applications require incremental algorithms to handle not only insertion/deletion of data points but also similarity changes between existing points. In this paper, we extend the standard spectral clustering to such evolving data, by introducing the incidence vector/matrix to represent two kinds of dynamics in the same framework and by incrementally updating the eigen-system. Our incremental algorithm, initialized by a standard spectral clustering, continuously and efficiently updates the eigenvalue system and generates instant cluster labels, as the data set is evolving. The algorithm is applied to a blog data set. Compared with recomputation of the solution by the standard spectral clustering, it achieves similar accuracy but with much lower computational cost. It can discover not only the stable blog communities but also the evolution of the individual multi-topic blogs. The core technique of incrementally updating the eigenvalue system is a general algorithm and has a wide range of applications—as well as incremental spectral clustering—where dynamic graphs are involved. This demonstrates the wide applicability of our incremental algorithm.     

Bagging-based spectral clustering ensemble selection

Traditional clustering ensemble methods combine all obtained clustering results at hand. However, we can often achieve a better clustering solution if only parts of the clustering results available are combined. In this paper, we generalize the selective clustering ensemble algorithm proposed by Azimi and Fern and a novel clustering ensemble method, SELective Spectral Clustering Ensemble (SELSCE), is proposed. The component clusterings of the ensemble system are generated by spectral clustering (SC) capable of engendering diverse committees. The random scaling parameter, Nyström approximation are used to perturb SC for producing the components of the ensemble system. After the generation of component clusterings, the bagging technique, usually applied in supervised learning, is used to assess the component clustering. We randomly pick part of the available clusterings to get a consensus result and then compute normalized mutual information (NMI) or adjusted rand index (ARI) between the consensus result and the component clusterings. Finally, the components are ranked by aggregating multiple NMI or ARI values. The experimental results on UCI dataset and images demonstrate that the proposed algorithm can achieve a better result than the traditional clustering ensemble methods.     

Non-negative and sparse spectral clustering

Spectral clustering aims to partition a data set into several groups by using the Laplacian of the graph such that data points in the same group are similar while data points in different groups are dissimilar to each other. Spectral clustering is very simple to implement and has many advantages over the traditional clustering algorithms such as k-means. Non-negative matrix factorization (NMF) factorizes a non-negative data matrix into a product of two non-negative (lower rank) matrices so as to achieve dimension reduction and part-based data representation. In this work, we proved that the spectral clustering under some conditions is equivalent to NMF. Unlike the previous work, we formulate the spectral clustering as a factorization of data matrix (or scaled data matrix) rather than the symmetrical factorization of the symmetrical pairwise similarity matrix as the previous study did. Under the NMF framework, where regularization can be easily incorporated into the spectral clustering, we propose several non-negative and sparse spectral clustering algorithms. Empirical studies on real world data show much better clustering accuracy of the proposed algorithms than some state-of-the-art methods such as ratio cut and normalized cut spectral clustering and non-negative Laplacian embedding.     

A spectral clustering algorithm for manufacturing cell formation

A graph clustering algorithm constructs groups of closely related parts and machines separately. After they are matched for the least intercell moves, a refining process runs on the initial cell formation to decrease the number of intercell moves. A simple modification of this main approach can deal with some practical constraints, such as the popular constraint of bounding the maximum number of machines in a cell. Our approach makes a big improvement in the computational time. More importantly, improvement is seen in the number of intercell moves when the computational results were compared with best known solutions from the literature.     

联合结构化图学习与l1范数谱嵌入的鲁棒聚类算法

谱聚类算法存在两个不足:a)将图的构造与谱分解割裂成两个独立的阶段,导致了结果的次优性;b)常用的基于l₂范数度量谱特征向量的相似性具有噪声敏感性。为了克服上述两点不足,提出基于联合结构化图学习与l₁范数谱嵌入的鲁棒聚类算法(记为CLRL1)。在该算法框架下,一方面图的学习过程与聚类过程可以有效结合起来进行协同优化,另一方面l₁范数的使用可以很好地约束谱特征向量的相似性以提升算法的鲁棒性。在多个常用数据集上进行的实验结果表明,改进算法聚类性能得到了明显提升。     

A spectral approach to clustering numerical vectors as nodes in a network

We address the issue of clustering examples by integrating multiple data sources, particularly numerical vectors and nodes in a network. We propose a new, efficient spectral approach, which integrates the two costs for clustering numerical vectors and clustering nodes in a network into a matrix trace, reducing the issue to a trace optimization problem which can be solved by an eigenvalue decomposition. We empirically demonstrate the performance of the proposed approach through a variety of experiments, including both synthetic and real biological datasets.     

Soft memberships for spectral clustering, with application to permeable language distinction

Recently, a large amount of work has been devoted to the study of spectral clustering—a powerful unsupervised classification method. This paper brings contributions to both its foundations, and its applications to text classification. Departing from the mainstream, concerned with hard membership, we study the extension of spectral clustering to soft membership (probabilistic, EM style) assignments. One of its key features is to avoid the complexity gap of hard membership. We apply this theory to a challenging problem, text clustering for languages having permeable borders, via a novel construction of Markov chains from corpora. Experiments with a readily available code clearly display the potential of the method, which brings a visually appealing soft distinction of languages that may define altogether a whole corpus.     

Fuzzy spectral clustering with robust spatial information for image segmentation

In recent years, spectral clustering has become one of the most popular clustering algorithms in areas of pattern analysis and recognition. This algorithm uses the eigenvalues and eigenvectors of a normalized similarity matrix to partition the data, and is simple to implement. However, when the image is corrupted by noise, spectral clustering cannot obtain satisfying segmentation performance. In order to overcome the noise sensitivity of the standard spectral clustering algorithm, a novel fuzzy spectral clustering algorithm with robust spatial information for image segmentation (FSC_RS) is proposed in this paper. Firstly, a non-local-weighted sum image of the original image is generated by utilizing the pixels with a similar configuration of each pixel. Then a robust gray-based fuzzy similarity measure is defined by using the fuzzy membership values among gray values in the new generated image. Thus, the similarity matrix obtained by this measure is only dependent on the number of the gray-levels and can be easily stored. Finally, the spectral graph partitioning method can be applied to this similarity matrix to group the gray values of the new generated image and then the corresponding pixels in the image are reclassified to obtain the final segmentation result. Some segmentation experiments on synthetic and real images show that the proposed method outperforms traditional spectral clustering methods and spatial fuzzy clustering in efficiency and robustness.     

Spectral clustering with more than K eigenvectors

Spectral clustering techniques are heuristic algorithms aiming to find approximate solutions to difficult graph-cutting problems, usually NP-complete, which are useful to clustering. A fundamental working hypothesis of these techniques is that the optimal partition of K classes can be obtained from the first K eigenvectors of the graph normalized Laplacian matrix L_N if the gap between the K-th and the K+1-th eigenvalue of L_N is sufficiently large. If the gap is small a perturbation may swap the corresponding eigenvectors and the results can be very different from the optimal ones.In this paper we suggest a weaker working hypothesis: the optimal partition of K classes can be obtained from a K-dimensional subspace of the first M>K eigenvectors, where M is a parameter chosen by the user. We show that the validity of this hypothesis can be confirmed by the gap size between the K-th and the M+1-th eigenvalue of L_N. Finally we present and analyse a simple probabilistic algorithm that generalizes current spectral techniques in this extended framework. This algorithm gives results on real world graphs that are close to the state of the art by selecting correct K-dimensional subspaces of the linear span of the first M eigenvectors, robust to small changes of the eigenvalues.     

Generalized regression model for sequence matching and clustering

Linear relation has been found to be valuable in rule discovery of stocks, such as if stock X goes up a, stock Y will go down b. The traditional linear regression models the linear relation of two sequences faithfully. However, if a user requires clustering of stocks into groups where sequences have high linearity or similarity with each other, it is prohibitively expensive to compare sequences one by one. In this paper, we present generalized regression model (GRM) to match the linearity of multiple sequences at a time. GRM also gives strong heuristic support for graceful and efficient clustering. The experiments on the stocks in the NASDAQ market mined interesting clusters of stock trends efficiently. Hansheng Lei received his BE from Ocean University of China in 1998, MS from the University of Science and Technology of China in 2001, and Ph.D. from the University at Buffalo, the State University of New York in February 2006, all in computer science. He is currently an assistant professor in CS/CIS Department, University of Texas at Brownsville. His research interests include biometrics, pattern recognition, machine learning, and data mining. Venu Govindaraju is a professor of Computer Science and Engineering at the University at Buffalo (UB), State University of New York. He received his B.-Tech. (Honors) from the Indian Institute of Technology (IIT), Kharagpur, India in 1986, and his Ph.D. degree in Computer Science from UB in 1992. His research is focused on pattern recognition applications in the areas of biometrics and digital libraries.     

一种基于谱聚类的半监督聚类方法

半监督聚类利用少部分标签的数据辅助大量未标签的数据进行非监督的学习,从而提高聚类的性能。提出一种基于谱聚类的半监督聚类算法,其利用标签数据的信息,调整点与点之间的距离所形成的距离矩阵,而后基于被调整的距离矩阵进行谱聚类。实验表明,该算法较之于已提出的半监督聚类算法,获得了更好的聚类性能。     

基于深度聚类的无监督特征嵌入学习

为了提高无监督嵌入学习对图像特征的判别能力,提出一种基于深度聚类的无监督学习方法。通过对图像的嵌入特征进行聚类,获得图像之间的伪类别信息,然后最小化聚类损失来优化网络模型,使得模型能够学习到图像的高判别性特征。在三个标准数据集上的图像检索性能表明了该方法的有效性,并且优于目前大多数方法。     

On defining affinity graph for spectral clustering through ranking on manifolds

Spectral clustering consists of two distinct stages: (a) construct an affinity graph from the dataset and (b) cluster the data points through finding an optimal partition of the affinity graph. The focus of the paper is the first step. Existing spectral clustering algorithms adopt Gaussian function to define the affinity graph since it is easy to implement. However, Gaussian function is hard to depict the intrinsic structure of the data, and it has to specify a scaling parameter whose selection is still an open issue in spectral clustering. Therefore, we propose a new definition of affinity graph for spectral clustering from the graph partition perspective. In particular, we propose two consistencies: smooth consistency and constraint consistency, for affinity graph to hold, and then define the affinity graph respecting these consistencies in a regularization framework of ranking on manifolds. Meanwhile the proposed definition of affinity graph is applicable to both unsupervised and semi-supervised spectral clustering. Encouraging experimental results on synthetic and real world data demonstrate the effectiveness of the proposed approach.     

多层自动确定类别的谱聚类算法

自动确定聚类数和海量数据的处理是谱聚类的关键问题。在自动确定聚类数谱聚类算法的基础上,提出了一种能处理大规模数据集的多层算法。该算法的核心思想是把大规模数据集根据一定的相关性逐级进行合并,使之成为小数据集,再对分组后的小数据集用自动确定类别的谱聚类算法聚类,最后逐层进行拆分并微调, 完成全部数据的聚类。实验证明该算法的聚类效果很好。