基于成对约束的判别型半监督聚类分析

现有一些典型的半监督聚类方法一方面难以有效地解决成对约束的违反问题,另一方面未能同时处理高维数据.通过提出一种基于成对约束的判别型半监督聚类分析方法来同时解决上述问题.该方法有效地利用了监督信息集成数据降维和聚类,即在投影空间中使用基于成对约束的K均值算法对数据聚类,再利用聚类结果选择投影空间.同时,该算法降低了基于约束的半监督聚类算法的计算复杂度,并解决了聚类过程中成对约束的违反问题.在一组真实数据集上的实验结果表明,与现有相关半监督聚类算法相比,新方法不仅能够处理高维数据,还有效地提高了聚类性能.     

一种混合约束的半监督聚类算法

提出一种混合约束的半监督聚类算法(HCC),综合考虑标号点和成对点约束信息的作用,使两种先验信息在聚类的过程中能以不同的方式发挥作用.给出理论推导、具体算法步骤、实验及分析.实验表明在HCC算法中,标号点对提高聚类结果的作用要比成对点约束信息的作用更明显,算法得到的CRI、聚类数、运行时间等多项指标都比对比算法好.     

密度敏感的半监督谱聚类

聚类通常被认为是一种无监督的数据分析方法,然而在实际问题中可以很容易地获得有限的样本先验信息,如样本的成对限制信息.大量研究表明,在聚类搜索过程中充分利用先验信息会显著提高聚类算法的性能.首先分析了在聚类过程中仅利用成对限制信息存在的不足,尝试探索数据集本身固有的先验信息--空间一致性先验信息,并提出利用这类先验信息的具体方法.接着,将两类先验信息同时引入经典的谱聚类算法中,提出一种密度敏感的半监督谱聚类算法(density-sensitive semi-supervised spectral clustering algorithm,简称DS-SSC).两类先验信息在指导聚类搜索的过程中能够起到相辅相成的作用,这使得DS-SSC算法相对于仅利用成对限制信息的聚类算法在聚类性能上有了显著的提高.在UCI基准数据集、USPS手写体数字集以及TREC的文本数据集上的实验结果验证了这一点.     

一种结合主动学习的半监督文档聚类算法

半监督文档聚类,即利用少量具有监督信息的数据来辅助无监督文档聚类,近几年来逐渐成为机器学习和数据挖掘领域研究的热点问题.由于获取大量监督信息费时费力,因此,国内外学者考虑如何获得少量但对聚类性能提高显著的监督信息.提出一种结合主动学习的半监督文档聚类算法,通过引入成对约束信息指导DBSCAN的聚类过程来提高聚类性能,得到一种半监督文档聚类算法Cons-DBSCAN.通过对约束集中所含信息量的衡量和对DBSCAN算法本身的分析,提出了一种启发式的主动学习算法,能够选取含信息量大的成对约束集,从而能够更高效地辅助半监督文档聚类.实验结果表明,所提出的算法能够高效地进行文档聚类.通过主动学习算法获得的成对约束集,能够显著地提高聚类性能.并且,算法的性能优于两个代表性的结合主动学习的半监督聚类算法.     

一种基于数据相关性的半监督模糊聚类集成方法

现有的半监督聚类集成方法能利用先验信息,使集成的准确性、鲁棒性和稳定性得到提高,但在集成阶段加入成对约束信息时,只考虑了给定的约束信息而忽视了约束点与被约束点的邻域点之间的关系.针对此问题,提出了一种基于数据相关性的半监督模糊聚类集成方法.该方法首先利用半监督模糊聚类算法建立集成信息矩阵,并将其转换为相似性矩阵;然后,利用已知的约束信息及约束点与被约束点的邻域点之间的关系来修改相似性矩阵;最后,利用图划分算法得到最终的聚类结果.真实数据上的实验结果表明,提出的方法可以有效提高聚类质量.     

一种成对约束限制的半监督文本聚类算法

半监督聚类能利用少量标记数据来提高聚类算法性能,但大部分文本聚类算法无法直接应用成对约束等先验信息。针对文本数据高维稀疏的特点,提出了一种半监督文本聚类算法。将成对约束信息扩展后嵌入文档相似度矩阵,在此基础上根据已划分与未划分文档之间的统计信息逐步找出剩余未划分文本集合中密集的且与已划分聚类中心集合相似度较小的K个初始聚类中心集合,然后将剩余的相对较难区分的文档结合成对约束限制信息划分到K个初始聚类中心集合,最后通过融合成对约束违反惩罚的收敛准则函数对聚类结果进行进一步优化。算法在聚类过程中自动确定初始聚类中心集合,避免了K均值算法对初始聚类中心选择的敏感性。在几个中英文数据集上的实验结果表明,所提算法能有效地利用少量的成对约束先验信息提高聚类效果。     

基于成对约束的交叉熵半监督聚类算法*

极大熵聚类(MEC)目标函数中缺乏成对约束的有效信息表达,在拥有少量成对约束的情况下,可能导致有效监督信息的浪费.在MEC的基础上,文中提出基于成对约束的交叉熵半监督聚类算法.利用样本交叉熵表达成对约束信息,并作为惩罚项引入至MEC的目标函数中,通过拉格朗日最优化处理目标函数,得出聚类中心与隶属度的迭代公式.实验表明,文中算法能有效利用少量的成对约束监督信息提高聚类性能,在实际数据应用中性能较好     

CEVCLUS: evidential clustering with instance-level constraints for relational data

Recent advances in clustering consider incorporating background knowledge in the partitioning algorithm, using, e.g., pairwise constraints between objects. As a matter of fact, prior information, when available, often makes it possible to better retrieve meaningful clusters in data. Here, this approach is investigated in the framework of belief functions, which allows us to handle the imprecision and the uncertainty of the clustering process. In this context, the EVCLUS algorithm was proposed for partitioning objects described by a dissimilarity matrix. It is extended here so as to take pairwise constraints into account, by adding a term to its objective function. This term corresponds to a penalty term that expresses pairwise constraints in the belief function framework. Various synthetic and real datasets are considered to demonstrate the interest of the proposed method, called CEVCLUS, and two applications are presented. The performances of CEVCLUS are also compared to those of other constrained clustering algorithms.     

基于PCA降维的成对约束半监督聚类集成

针对现有的聚类集成算法大都是无监督聚类集成算法且不能很好地处理高维数据的问题,设计一种基于PCA降维技术的成对约束半监督聚类集成算法（SSCEDR）。SSCEDR方法使用PCA主成分分析对原始数据进行降维,结合半监督聚类集成技术,在降维后的空间中将成对约束等先验知识代入到聚类集成过程中。本文通过在多组数据集上实验来验证算法的有效性。     

Hierarchical constraints

Constrained clustering received a lot of attention in the last years. However, the widely used pairwise constraints are not generally applicable for hierarchical clustering, where the goal is to derive a cluster hierarchy instead of a flat partition. Therefore, we propose for the hierarchical setting—based on the ideas of pairwise constraints—the use of must-link-before (MLB) constraints. In this paper, we discuss their properties and present an algorithm that is able to create a hierarchy by considering these constraints directly. Furthermore, we propose an efficient data structure for its implementation and evaluate its effectiveness with different datasets in a text clustering scenario.     

Improving clustering with pairwise constraints: a discriminative approach

To obtain a user-desired and accurate clustering result in practical applications, one way is to utilize additional pairwise constraints that indicate the relationship between two samples, that is, whether these samples belong to the same cluster or not. In this paper, we put forward a discriminative learning approach which can incorporate pairwise constraints into the recently proposed two-class maximum margin clustering framework. In particular, a set of pairwise loss functions is proposed, which features robust detection and penalization for violating the pairwise constraints. Consequently, the proposed method is able to directly find the partitioning hyperplane, which can separate the data into two groups and satisfy the given pairwise constraints as much as possible. In this way, it makes fewer assumptions on the distance metric or similarity matrix for the data, which may be complicated in practice, than existing popular constrained clustering algorithms. Finally, an iterative updating algorithm is proposed for the resulting optimization problem. The experiments on a number of real-world data sets demonstrate that the proposed pairwise constrained two-class clustering algorithm outperforms several representative pairwise constrained clustering counterparts in the literature.     

基于半监督自动谱聚类算法的网络故障检测

针对网络故障检测中利用先验知识不足和多数谱聚类算法需事先确定聚类数的问题,提出一种新的基于成对约束信息传播与自动确定聚类数相结合的半监督自动谱聚类算法。通过学习一种新的相似性测度函数来满足约束条件,改进NJW聚类算法,对非规范化的Laplacian矩阵特征向量进行自动谱聚类,从而提高聚类性能。在UCI标准数据集和网络实测数据上的实验表明,该算法较相关比对算法聚类准确率更高,可满足网络故障检测的实际需要。     

双层随机游走半监督聚类

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

基于成对约束的半监督凝聚层次聚类算法

对于所提出的建立在成对约束基础之上的半监督凝聚层次聚类算法,对聚类簇进行半监督处理的最主要目的在于借助于对样本监督信息的合理应用,达到提高样本在无监督状态下学习性能的目标.在现阶段的技术条件支持下,以半监督聚类分析为核心,建立在must link以及cannot link基础之上的约束关系被广泛地应用于样本聚类分析的过程当中.从这一角度上来说,为了使聚类簇与聚类簇之间的距离关系表述更加的真实与精确,就要求通过对成对约束关系的综合应用,实现对聚类簇距离的有效调整与优化.     

基于改进成对约束扩充的标签传播聚类算法

针对半监督聚类算法性能受到成对约束数量多寡的限制问题,现有的研究大都依赖于原始成对约束的数量。因此,首先提出了基于灰关联分析的成对约束初始化算法（initialization algorithm of pair constraints based on grey relational analysis,PCIG）。该算法通过均衡接近度计算数据对象间的相似度,并根据相似度的取值来确定可信区间,然后借鉴网络结构初始化方法来扩充数据对象间的成对关系。最后,将其应用于标签传播聚类算法。通过在五个基准数据集上进行实验,基于改进成对约束扩充的标签传播聚类算法与其他方法相比NMI值和ARI值有所提升。实验结果证明了改进成对约束扩充可以有效改善标签传播算法的聚类效果。     

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.     

基于主动学习的K-Hub聚类算法

K-Hub聚类算法是一种有效的高维数据聚类算法,但是它对初始聚类中心的选择非常敏感,并且对于靠近类边界的实例往往不能正确聚类.为了解决这些问题,提出一种结合主动学习和半监督聚类的K-Hub聚类算法.运用主动学习策略学习部分实例的关联限制,然后利用这些关联限制指导K-Hub的聚类过程.实验结果表明,基于主动学习的K-Hub聚类算法能有效提升K-Hub的聚类准确率.     

基于先验信息和谱分析的聚类融合算法

在聚类过程中利用先验信息能显著提高聚类算法的性能,但已存在的聚类融合算法很少考虑到数据集的先验信息。基于先验信息和谱分析,提出一种聚类融合算法,将成对限制信息引入到谱聚类算法中,用受限的谱聚类算法产生聚类成员,再采用基于互联合矩阵的集成方法生成最后的聚类结果。实验结果表明,利用先验信息能有效提高聚类的效果。     

一种基于成对约束的半监督最大间隔聚类算法

最大间隔聚类是近来聚类分析的一个研究热点,为进一步提高其聚类准确性,提出一种基于成对约束的半监督最大间隔聚类算法.该算法在最大间隔聚类的目标函数中添加针对成对约束的损失项,从而对违反给定约束条件的分界面进行惩罚.对所得到的非凸优化问题,本文提出一种基于约束凹凸过程的迭代算法来进行高效求解.实验表明,本文提出的算法能极大地提高最大间隔聚类的准确性,其聚类性能也明显优于其他两种半监督聚类算法.     

基于混合距离学习的鲁棒的模糊C均值聚类算法

距离度量对模糊聚类算法FCM的聚类结果有关键性的影响。实际应用中存在这样一种场景,聚类的数据集中存在着一定量的带标签的成对约束集合的辅助信息。为了充分利用这些辅助信息,首先提出了一种基于混合距离学习方法,它能利用这样的辅助信息来学习出数据集合的距离度量公式。然后,提出了一种基于混合距离学习的鲁棒的模糊C均值聚类算法（HR-FCM算法）,它是一种半监督的聚类算法。算法HR-FCM既保留了GIFP-FCM（Generalized FCM algorithm with improved fuzzy partitions）算法的鲁棒性等性能,也因为所采用更为合适的距离度量而具有更好的聚类性能。实验结果证明了所提算法的有效性。