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

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

基于RFM模型的半监督聚类算法

客户分类作为客户关系管理（CRM）的重要管理方法,是企业进行市场营销的重要依据.通过对客户进行分类,有利于对客户价值进行准确评估,方便进行精准营销.本文通过对RFM模型数据集本身潜藏的先验结构化信息进行研究,标记出两组客户数据作为先验类别标记,进而得到两个初始聚类中心.基于传统K-means算法使用自适应方法确定K值和初始聚类中心.引入Must-link和Cannot-link两种约束将类别标记转换为成对约束信息,基于HMRF-KMeans成对约束,引入约束惩罚项和约束奖励项,实现对聚类引导和聚类结果的调整.使用改进的半监督聚类算法（RFM-SS-means）对标准数据集进行了测试,同时使用Food mart数据集对比了RFM-SS-means算法与传统K-means算法、two-steps算法的聚类效果.由实验结果可知,RFM-SS-means的CH系数最大,无需事先确定K值和初始聚类中心,聚类效果良好.     

融合词项关联关系的半监督微博聚类算法

针对微博文本内容短、稀疏、高维等特点,提出一种改进的半监督微博聚类算法。该算法利用词项间的关系丰富文本特征,通过定义词项文档间关联关系和词项文档内关联关系揭示词项间语义的关联程度,并由此自动生成有标记的数据来指导聚类过程。对词项先验信息进行成对约束编码,构建基于词项间成对约束的三重非负矩阵分解模型来实现微博的半监督聚类。实验结果表明,该算法可以减少繁琐的人工标记过程,并能高效地进行微博聚类。     

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

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

基于主动学习先验的半监督K-means聚类算法

基于迭代框架的主动半监督聚类框架（IASSCF）是一个流行的半监督聚类框架。该框架存在两个问题：其一,初始先验信息较少导致迭代初期聚类效果不佳,进而影响后续聚类结果;其二,每次迭代只选择信息量最大的一个样本标记,导致运行速度慢、性能提升慢。针对这两个问题,设计了一种基于主动学习先验的半监督K-means聚类算法。该方法包含初始化阶段和迭代阶段。初始化阶段主动选择代表性较高的节点集合,并基于代表节点集合构建各类的先验节点集合和约束先验集合。迭代阶段,每次迭代包含三步：1）基于当前约束先验集合,利用约束半监督聚类算法PCK-means对数据进行聚类;2）依据当前聚类结果,主动选择每个簇中最具价值信息的未标注样本点;3）利用选择样本点扩充先验节点集合及约束集合。迭代此过程至达到收敛阈值。实验结果表明,与基于原IASSCF框架的半监督K-means聚类算法相比,所提算法运行速度更快,性能更优。     

密度自适应的半监督谱聚类算法

谱聚类是一种新兴的聚类算法,数据点间的相似度定义对其聚类效果起着至关重要的作用。传统的谱聚类算法通常利用高斯核函数作为相似度函数,但是对于多密度的数据往往不能取得良好的效果。在定义新的相似度函数的基础上,提出了一种密度自适应的半监督聚类算法。该算法结合半监督聚类的成对约束理论,利用先验信息对样本点之间的相似度进行自适应调整,提高了聚类的精度。该算法在人工数据集和真实数据集上的仿真实验都取得了良好的效果。     

基于密度自适应邻域相似图的半监督谱聚类

谱聚类是基于谱图划分理论的一种聚类算法,传统的谱聚类算法属于无监督学习算法,只能利用单一数据来进行聚类。针对这种情况,提出一种基于密度自适应邻域相似图的半监督谱聚类（DAN-SSC）算法。DAN-SSC算法在传统谱聚类算法的基础上结合了半监督学习的思想,很好地解决了传统谱聚类算法无法充分利用所有数据,不得不对一些有标签数据进行舍弃的问题;将少量的成对约束先验信息扩散至整个空间,使其能更好地对聚类过程进行指导。实验结果表明,DAN-SSC算法具有可行性和有效性。     

基于改进相似度与类中心向量的半监督短文本聚类算法

通过分析现有短文本聚类算法的缺陷,提出了一种基于改进相似度与类中心向量的半监督短文本聚类算法。首先,定义强类别区分度词,利用已加标数据的类别信息提取并构造强类别区分度词集合,并对基于初始特征的余弦相似度和基于强类别区分度词项的相似度进行有效融合,得到更加合理的改进的短文本相似度计算公式。然后,通过计算样本与类中心向量的相似度实现对未分类样本的正确划分,与此同时,更新加标数据集合、类中心向量,重新抽取强类别区分度词。重复这个过程,直到实现所有数据的类别划分。实验表明：与其他同类算法相比,本文算法在聚类准确性和时间效率上有了较大的改进。     

基于成对约束的主动半监督文本聚类

在主动选取成对约束方法的基础上,提出一种基于成对约束的主动半监督文本聚类方法.利用潜在语义索引方法对文本特征空间进行降维,在聚类过程中,采用构造的约束选取方法主动地选取成对约束信息,并利用选取的成对约束信息指导文本聚类.实验结果表明,该方法能利用少量的监督信息提高文本聚类的分类准确率.     

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

半监督聚类就是利用样本的监督信息来帮助提升无监督学习的性能。在半监督聚类中,成对约束(must-link约束和cannot-link约束)作为样本的先验知识被广泛地使用。凝聚层次聚类(AHC)也叫合成聚类,是层次聚类法的一种。提出了一种基于成对约束的半监督凝聚层次聚类算法(PS-AHC),该算法利用成对约束来改变聚类簇之间的距离,使聚类簇之间的距离更真实。在UCI数据集上的实验表明,PS-AHC能有效地提高聚类的准确率,是一种有前景的半监督聚类算法。     

Text document clustering based on neighbors

Clustering is a very powerful data mining technique for topic discovery from text documents. The partitional clustering algorithms, such as the family of k-means, are reported performing well on document clustering. They treat the clustering problem as an optimization process of grouping documents into k clusters so that a particular criterion function is minimized or maximized. Usually, the cosine function is used to measure the similarity between two documents in the criterion function, but it may not work well when the clusters are not well separated. To solve this problem, we applied the concepts of neighbors and link, introduced in [S. Guha, R. Rastogi, K. Shim, ROCK: a robust clustering algorithm for categorical attributes, Information Systems 25 (5) (2000) 345–366], to document clustering. If two documents are similar enough, they are considered as neighbors of each other. And the link between two documents represents the number of their common neighbors. Instead of just considering the pairwise similarity, the neighbors and link involve the global information into the measurement of the closeness of two documents. In this paper, we propose to use the neighbors and link for the family of k-means algorithms in three aspects: a new method to select initial cluster centroids based on the ranks of candidate documents; a new similarity measure which uses a combination of the cosine and link functions; and a new heuristic function for selecting a cluster to split based on the neighbors of the cluster centroids. Our experimental results on real-life data sets demonstrated that our proposed methods can significantly improve the performance of document clustering in terms of accuracy without increasing the execution time much.     

Effective semi-supervised document clustering via active learning with instance-level constraints

Semi-supervised document clustering, which takes into account limited supervised data to group unlabeled documents into clusters, has received significant interest recently. Because of getting supervised data may be expensive, it is important to get most informative knowledge to improve the clustering performance. This paper presents a semi-supervised document clustering algorithm and a new method for actively selecting informative instance-level constraints to get improved clustering performance. The semi- supervised document clustering algorithm is a Constrained DBSCAN (Cons-DBSCAN) algorithm, which incorporates instance-level constraints to guide the clustering process in DBSCAN. An active learning approach is proposed to select informative document pairs for obtaining user feedbacks. Experimental results show that Cons-DBSCAN with our proposed active learning approach can improve the clustering performance significantly when given a relatively small amount of constraints.     

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

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

Research of semi-supervised spectral clustering algorithm based on pairwise constraints

Clustering is often considered as an unsupervised data analysis method, but making full use of the prior information in the process of clustering will significantly improve the performance of the clustering algorithm. Spectral clustering algorithm can well use the prior pairwise constraint information to cluster and has become a new hot spot of machine learning research in recent years. In this paper, we propose an effective clustering algorithm, called a semi-supervised spectral clustering algorithm based on pairwise constraints, in which the similarity matrix of data points is adjusted and optimized by pairwise constraints. The experiments on real-world data sets demonstrate the effectiveness of this algorithm.     

基于单词超团的文本聚类方法

为优化文本聚类效果,提出一种基于单词超团理论的文本聚类方法.利用文档中单词的关联模式来评估文档间的相似度,将单词超团作为文档向量辅助信息,以图划分的方式进行聚类分析.对不同聚类方法的结果进行比较,证明基于单词超团的文本聚类方法能提高文本聚类的准确性.     

类关联词约束的K-Means半监督文本聚类方法

提出了一种利用类关联词和K-Means聚类算法实现对文本文档进行分类的方法。类关联词是与类主题相关、能反映类主题的单词或短语。根据文档中包含的类关联词,形成初始聚类中心。在聚类算法过程中,类关联词提供的信息被用来约束待分类文档与聚类中心的相似度比较,加快了算法的执行。实验证明了算法的有效性。     

用于文本聚类的新型差分进化粒子群算法

针对粒子群优化（Particle Swarm Optimization,PSO）算法在维度高、特征稀疏的文本聚类过程中,随着算法迭代次数增加在后期陷入局部最优的问题,提出采用多样性更好的差分进化（Differential Evolution,DE）策略更新种群,尝试找到更好的全局最优解。考虑到种群个体间包含的聚类中心向量排列顺序的随机性对个体间的学习与更新的影响,提出一种自适应调整聚类中心向量排列顺序的方法,将个体间相似度最大的聚类中心向量尽可能排列在同一维度。通过在文本数据集上进行测试,验证了所提出的聚类中心排列调整差分进化粒子群（Index adaptive DEPSO,IDEPSO）算法在内部、外部指标上相对于其他现有算法的优势,证明了该算法的有效性和可行性。