Learning low-rank kernel matrices for constrained clustering

Constrained clustering methods (that usually use must-link and/or cannot-link constraints) have been received much attention in the last decade. Recently, kernel adaptation or kernel learning has been considered as a powerful approach for constrained clustering. However, these methods usually either allow only special forms of kernels or learn non-parametric kernel matrices and scale very poorly. Therefore, they either learn a metric that has low flexibility or are applicable only on small data sets due to their high computational complexity. In this paper, we propose a more efficient non-linear metric learning method that learns a low-rank kernel matrix from must-link and cannot-link constraints and the topological structure of data. We formulate the proposed method as a trace ratio optimization problem and learn appropriate distance metrics through finding optimal low-rank kernel matrices. We solve the proposed optimization problem much more efficiently than SDP solvers. Additionally, we show that the spectral clustering methods can be considered as a special form of low-rank kernel learning methods. Extensive experiments have demonstrated the superiority of the proposed method compared to recently introduced kernel learning methods.     

Non-linear metric learning using pairwise similarity and dissimilarity constraints and the geometrical structure of data

The problem of clustering with side information has received much recent attention and metric learning has been considered as a powerful approach to this problem. Until now, various metric learning methods have been proposed for semi-supervised clustering. Although some of the existing methods can use both positive (must-link) and negative (cannot-link) constraints, they are usually limited to learning a linear transformation (i.e., finding a global Mahalanobis metric). In this paper, we propose a framework for learning linear and non-linear transformations efficiently. We use both positive and negative constraints and also the intrinsic topological structure of data. We formulate our metric learning method as an appropriate optimization problem and find the global optimum of this problem. The proposed non-linear method can be considered as an efficient kernel learning method that yields an explicit non-linear transformation and thus shows out-of-sample generalization ability. Experimental results on synthetic and real-world data sets show the effectiveness of our metric learning method for semi-supervised clustering tasks.     

A Lagrangian-based score for assessing the quality of pairwise constraints in semi-supervised clustering

Clustering algorithms help identify homogeneous subgroups from data. In some cases, additional information about the relationship among some subsets of the data exists. When using a semi-supervised clustering algorithm, an expert may provide additional information to constrain the solution based on that knowledge and, in doing so, guide the algorithm to a more useful and meaningful solution. Such additional information often takes the form of a cannot-link constraint (i.e., two data points cannot be part of the same cluster) or a must-link constraint (i.e., two data points must be part of the same cluster). A key challenge for users of such constraints in semi-supervised learning algorithms, however, is that the addition of inaccurate or conflicting constraints can decrease accuracy and little is known about how to detect whether expert-imposed constraints are likely incorrect. In the present work, we introduce a method to score each must-link and cannot-link pairwise constraint as likely incorrect. Using synthetic experimental examples and real data, we show that the resulting impact score can successfully identify individual constraints that should be removed or revised.

     

不确定成对约束的双对抗流形传播方法

成对约束传播(pairwise constraint propagation, PCP)通常研究的是在初始给定精确的成对约束基础上通过传播学习来增加成对约束的数量,从而给机器学习任务提供较多的监督信息。可是,在现实场景中,有时还有一些不精确的成对约束,因此,如何利用这些不精确的成对约束来提高成对约束传播学习的效果是一个有待解决的问题。针对这一问题,本文提出了一种不确定成对约束的传播方法。主要思想是用两个矩阵分别表示必须链接和不能链接的可能性,两种可能性之间形成对抗,同时两种成对约束之间也存在对抗关系,两类对抗相结合形成一种双对抗结构,作用于必须链接和不能链接的传播过程,使二者的对抗强度在竞争中趋于最小化。我们将该方法称为不确定成对约束传播(uncertain pairwise constraint propagation, UPCP)。在多个数据集上的实验结果表明,不确定成对约束的传播效果不超过但近似于理想化传播效果,在增强现实应用性的同时尽可能地保证了传播精度。     

On semi-supervised fuzzy c-means clustering for data with clusterwise tolerance by opposite criteria

This paper presents a new semi-supervised fuzzy c-means clustering for data with clusterwise tolerance by opposite criteria. In semi-supervised clustering, pairwise constraints, that is, must-link and cannot-link, are frequently used in order to improve clustering performances. From the viewpoint of handling pairwise constraints, a new semi-supervised fuzzy c-means clustering is proposed by introducing clusterwise tolerance-based pairwise constraints. First, a concept of clusterwise tolerance-based pairwise constraints is introduced. Second, the optimization problems of the proposed method are formulated. Especially, must-link and cannot-link are handled by opposite criteria in our proposed method. Third, a new clustering algorithm is constructed based on the above discussions. Finally, the effectiveness of the proposed algorithm is verified through numerical examples.     

基于约束动态更新的半监督层次聚类算法

提出了一种基于约束动态更新的半监督层次聚类算法. 与现存的半监督层次聚类算法类似, 该算法也使用了必连和不连约束. 但不同的是, 该算法并不是在对满足必连约束的数据样本点进行预先划分的基础上依据不连约束进行聚合操作, 而是首先将约束扩展为一个闭包, 然后在这此基础上直接依据不连约束进行聚合操作, 并在聚合的过程中依据聚类结果动态地更新必连和不连约束, 以保证最终的聚类结果同时满足必连和不连约束. 该算法的优势在于省略了对必连约束的数据样本点进行预先划分的步骤, 这一改进能够保证数据样本点获得更为合理的聚合顺序, 从而得到更为准确的聚类结果. 本文具体给出了该算法基于Ward 层次聚类算法的实现, 提出了C-Ward算法.实验表明, 与其他同类算法相比, 无论是在人工模拟数据集还是在现实数据集上, 本文提出的算法都表现出了更高的准确性和更强的稳定性.     

双层随机游走半监督聚类

半监督聚类旨在根据用户给出的必连和不连约束,把所有数据点划分到不同的簇中,从而获得更准确、更加符合用户要求的聚类结果.目前的半监督聚类算法大多数通过修改已有的聚类算法或者结合度规学习,使聚类结果与点对约束尽可能地保持一致,却很少考虑点对约束对周围无约束数据的显式影响程度.提出一种由在顶点上的低层随机游走和在组件上的高层随机游走两部分构成的双层随机游走半监督聚类算法,其中,低层随机游走主要负责计算选出的约束顶点对其他顶点的影响范围和影响程度,称为组件;高层随机游走则进一步将各个点对约束以自适应的强度在组件上进行约束传播,把它们在每个顶点上的影响综合在一个簇指示矩阵中.UCI数据集和大型真实数据集上的实验结果表明,双层随机游走半监督聚类算法比其他半监督聚类算法更准确,也比较高效.     

半监督典型相关分析算法

在典型相关分析算法(canonical correlation analysis,简称CCA)的基础上,通过引入以成对约束形式给出的监督信息,提出了一种半监督的典型相关分析算法(Semi-CCA).在此算法中,除了考虑大量的无标号样本以外,还考虑成对约束信息,即已知两样本属于同一类(正约束)或不属于同一类(负约束),同时验证了两者的相对重要性.在人工数据集、多特征手写体数据集和人脸数据集(Yale和AR)上的实验结果表明,Semi-CCA能够有效地利用少量的监督信息采提高分类性能.     

基于半监督学习的增量图像分类方法

为有效使用大量未标注的图像进行分类,提出一种基于半监督学习的图像分类方法。通过共同的隐含话题桥接少量已标注的图像和大量未标注的图像,利用已标注图像的Must-link约束和Cannot-link约束提高未标注图像分类的精度。实验结果表明,该方法有效提高Caltech-101数据集和7类图像集约10%的分类精度。此外,针对目前绝大部分半监督图像分类方法不具备增量学习能力这一缺点,提出该方法的增量学习模型。实验结果表明,增量学习模型相比无增量学习模型提高近90%的计算效率。关键词半监督学习,图像分类,增量学习中图法分类号TP391。41IncrementalImageClassificationMethodBasedonSemi-SupervisedLearningLIANGPeng^1,2,LIShao-Fa²,QINJiang-Wei²,LUOJian-Gao³¹(SchoolofComputerScienceandEngineering,GuangdongPolytechnicNormalUniversity,Guangzhou510665)²(SchoolofComputerScienceandEngineering,SouthChinaUniversityofTechnology,Guangzhou510006)³(DepartmentofComputer,GuangdongAIBPolytechnicCollege,Guangzhou510507)ABSTRACTInordertouselargenumbersofunlabeledimageseffectively,animageclassificationmethodisproposedbasedonsemi-supervisedlearning。Theproposedmethodbridgesalargeamountofunlabeledimagesandlimitednumbersoflabeledimagesbyexploitingthecommontopics。Theclassificationaccuracyisimprovedbyusingthemust-linkconstraintandcannot-linkconstraintoflabeledimages。TheexperimentalresultsonCaltech-101and7-classesimagedatasetdemonstratethattheclassificationaccuracyimprovesabout10%bytheproposedmethod。Furthermore,duetothepresentsemi-supervisedimageclassificationmethodslackingofincrementallearningability,anincrementalimplementationofourmethodisproposed。Comparingwithnon-incrementallearningmodelinliterature,theincrementallearningmethodimprovesthecomputationefficiencyofnearly90%。     

Learning deep compact similarity metric for kinship verification from face images

Recent advances in kinship verification have shown that learning an appropriate kinship similarity metric on human faces plays a critical role in this problem. However, most of existing distance metric learning (DML) based solutions rely on linearity assumption of the kinship metric model, and the domain knowledge of large cross-generation discrepancy (e.g., large age span and gender difference between parent and child images) has not been considered in metric learning, leading to degraded performance for genetic similarity measure on human faces. To address these limitations, we propose in this work a new kinship metric learning (KML) method with a coupled deep neural network (DNN) model. KML explicitly models the cross-generation discrepancy inherent on parent-child pairs, and learns a coupled deep similarity metric such that the image pairs with kinship relation are pulled close, while those without kinship relation (but with high appearance similarity) are pushed as far away as possible. Moreover, by imposing the intra-connection diversity and inter-connection consistency over the coupled DNN, we introduce the property of hierarchical compactness into the coupled network to facilitate deep metric learning with limited amount of kinship training data. Empirically, we evaluate our algorithm on several kinship benchmarks against the state-of-the-art DML alternatives, and the results demonstrate the superiority of our method.     

Constraint scores for semi-supervised feature selection: A comparative study

Recent feature selection scores using pairwise constraints (must-link and cannot-link) have shown better performances than the unsupervised methods and comparable to the supervised ones. However, these scores use only the pairwise constraints and ignore the available information brought by the unlabeled data. Moreover, these constraint scores strongly depend on the given must-link and cannot-link subsets built by the user. In this paper, we address these problems and propose a new semi-supervised constraint score that uses both pairwise constraints and local properties of the unlabeled data. Experiments using Kendall’s coefficient and accuracy rates, show that this new score is less sensitive to the given constraints than the previous scores while providing similar performances.     

Active hashing and its application to image and text retrieval

In recent years, hashing-based methods for large-scale similarity search have sparked considerable research interests in the data mining and machine learning communities. While unsupervised hashing-based methods have achieved promising successes for metric similarity, they cannot handle semantic similarity which is usually given in the form of labeled point pairs. To overcome this limitation, some attempts have recently been made on semi-supervised hashing which aims at learning hash functions from both metric and semantic similarity simultaneously. Existing semi-supervised hashing methods can be regarded as passive hashing since they assume that the labeled pairs are provided in advance. In this paper, we propose a novel framework, called active hashing, which can actively select the most informative labeled pairs for hash function learning. Specifically, it identifies the most informative points to label and constructs labeled pairs accordingly. Under this framework, we use data uncertainty as a measure of informativeness and develop a batch mode algorithm to speed up active selection. We empirically compare our method with a state-of-the-art passive hashing method on two benchmark data sets, showing that the proposed method can reduce labeling cost as well as overcome the limitations of passive hashing.     

基于约束投影的支持向量机选择性集成

提出两种基于约束投影的支持向量机选择性集成算法。首先利用随机选取的must-link和cannot-link成对约束集确定投影矩阵,将原始训练样本投影到不同的低维空间训练一组基分类器;然后,分别采用遗传优化和最小化偏离度误差两种选择性集成技术对基分类器进行组合。基于UCI数据的实验表明,提出的两种集成算法均能有效提高支持向量机的泛化性能,显著优于Bagging,Boosting,特征Bagging及LoBag等集成算法。     

Integrating local and global topological structures for semi-supervised dimensionality reduction

Dimensionality reduction plays an important role in many machine learning tasks. This paper studies semi-supervised dimensionality reduction using pairwise constraints. In this setting, domain knowledge is given in the form of pairwise constraint, which specifies whether a pair of instances belongs to the same class (must-link constraint) or different classes (cannot-link constraint). In this paper, a novel semi-supervised dimensionality reduction method called LGS3DR is proposed, which can integrate both local and global topological structures of the data as well as pairwise constraints. The LGS3DR method is effective and has a closed form solution. Experiments on data visualization and face recognition show that LGS3DR is superior to many existing dimensionality reduction methods.     

Constraint-based clustering selection

Clustering requires the user to define a distance metric, select a clustering algorithm, and set the hyperparameters of that algorithm. Getting these right, so that a clustering is obtained that meets the users subjective criteria, can be difficult and tedious. Semi-supervised clustering methods make this easier by letting the user provide must-link or cannot-link constraints. These are then used to automatically tune the similarity measure and/or the optimization criterion. In this paper, we investigate a complementary way of using the constraints: they are used to select an unsupervised clustering method and tune its hyperparameters. It turns out that this very simple approach outperforms all existing semi-supervised methods. This implies that choosing the right algorithm and hyperparameter values is more important than modifying an individual algorithm to take constraints into account. In addition, the proposed approach allows for active constraint selection in a more effective manner than other methods.     

半监督局部维数约减

在挖掘和分析高维数据任务中,有时只能获得有限的成对约束信息(must-link约束和cannot-link约束),由于缺乏数据类标号信息,监督维数约减方法常常不能得到满意的结果。在这种情况下,使用大量的无标号样本可以提高算法的性能。文中借助于成对约束信息和大量无标号样本,提出半监督局部维数约减方法(SLDR)。SLDR集成数据的局部信息和成对约束寻找一个最优投影,当数据被投影到低维空间时,不仅cannot-link约束中样本点对之间距离更远、must-link约束中样本点对之间距离更近,数据的内在几何信息还被保持。而且SLDR能推广为非线性方法,使之能够适应非线性数据的维数约减。在各种数据集上的实验结果充分验证了所提出算法的有效性。     

Locally linear metric adaptation with application to semi-supervised clustering and image retrieval

Many computer vision and pattern recognition algorithms are very sensitive to the choice of an appropriate distance metric. Some recent research sought to address a variant of the conventional clustering problem called semi-supervised clustering, which performs clustering in the presence of some background knowledge or supervisory information expressed as pairwise similarity or dissimilarity constraints. However, existing metric learning methods for semi-supervised clustering mostly perform global metric learning through a linear transformation. In this paper, we propose a new metric learning method that performs nonlinear transformation globally but linear transformation locally. In particular, we formulate the learning problem as an optimization problem and present three methods for solving it. Through some toy data sets, we show empirically that our locally linear metric adaptation (LLMA) method can handle some difficult cases that cannot be handled satisfactorily by previous methods. We also demonstrate the effectiveness of our method on some UCI data sets. Besides applying LLMA to semi-supervised clustering, we have also used it to improve the performance of content-based image retrieval systems through metric learning. Experimental results based on two real-world image databases show that LLMA significantly outperforms other methods in boosting the image retrieval performance.     

MetricFusion: Generalized metric swarm learning for similarity measure

Learning distance metrics for measuring the similarity between two data points in unsupervised and supervised pattern recognition has been widely studied in unconstrained face verification tasks. Motivated by the fact that enforcing single distance metric learning for verification via an empirical score threshold is not robust in uncontrolled experimental conditions, we therefore propose to obtain a metric swarm by learning local patches alike sub-metrics simultaneously that naturally formulates a generalized metric swarm learning (GMSL) model with a joint similarity score function solved by an efficient alternative optimization algorithm. Further, each sample pair is represented as a similarity vector via the well-learned metric swarm, such that the face verification task becomes a generalized SVM-alike classification problem. Therefore, the verification can be enforced in the represented metric swarm space that can well improve the robustness of verification under irregular data structure. Experiments are preliminarily conducted using several UCI benchmark datasets for solving general classification problem. Further, the face verification experiments on real-world LFW and PubFig datasets demonstrate that our proposed model outperforms several state-of-the-art metric learning methods.     

基于用户回复内容观点支持度的评论有用性计算

针对有监督评论有用性预测方法中的训练数据集难以构造,以及无监督方法缺乏对情感信息支撑的问题,提出基于语义和情感信息构建一种无监督模型,用于对评论有用性进行预测,同时考虑了评论和评论下回复内容对观点的支持度用来计算观点的有用性得分,进而得到评论的有用性。同时,提出结合句法分析和改进潜在狄利克雷分配（LDA）模型的评论摘要方法用于评论有用性预测模型中的观点提取,基于句法分析结果构建must-link和cannot-link两种约束条件指导主题模型学习,在保证召回率的同时提高模型准确率。该方法在实验数据集上能取得70%左右的F1值和90%左右的排序准确率,且实例应用也表明该方法对结果具有较好的解释性。     

Exploiting constraint inconsistence for dimension selection in subspace clustering: A semi-supervised approach

Selecting correct dimensions is very important to subspace clustering and is a challenging issue. This paper studies semi-supervised approach to the problem. In this setting, limited domain knowledge in the form of space level pair-wise constraints, i.e., must-links and cannot-links, are available. We propose a semi-supervised subspace clustering (S³C) algorithm that exploits constraint inconsistence for dimension selection. Our algorithm firstly correlates globally inconsistent constraints to dimensions in which they are consistent, then unites constraints with common correlating dimensions, and finally forms the subspaces according to the constraint unions. Experimental results show that S³C is superior to the typical unsupervised subspace clustering algorithm FINDIT, and the other constraint based semi-supervised subspace clustering algorithm SC-MINER.