论文摘要
数据挖掘是从大量数据中发掘出隐含的、先前未知的,并具有潜在价值的模式或者知识的过程。作为数据挖掘的一种基本方法,聚类分析利用数据对象间的相似性,把数据集划分成若干个类簇。从机器学习的角度,聚类分析被归为无监督学习方法,但是,在现实应用领域内,人们可以获得与数据相关的一些领域知识,并通过这些领域知识,可以获得部分数据对象间的约束限制信息。通过加入部分先验知识对聚类进行指导可以改善聚类效果,这个过程被称为半监督聚类。近年来最受关注的半监督聚类算法则是结合限制的聚类算法。此类算法把先验知识表示为数据对象间的关联限制,即正关联限制表示两个数据对象必须同类,负关联限制表示两个数据对象一定不同类。大量的实验证明了聚类算法中加入限制信息可以改善聚类效果,但加入限制后的聚类算法也存在着一些问题,如结合限制的K-Means（CKM）算法中数据对象的分配次序直接影响着CKM算法的聚类效果。针对此问题,UALA通过评估数据对象稳定性来确定数据对象的分配次序,实验证明UALA改善了CKM算法的聚类效果,但也存在一定的缺陷。本文针对CKM算法和UALA存在的问题,从数据稳定性和限制符合度两个方面对限制进行评估,通过改变聚类迭代过程中数据对象的分配次序来达到改善聚类效果的目的。通过分析CKM算法,发现数据对象的稳定性会随着限制的加入而不断改变,具有动态特性,而UALA采用静态思想计算数据对象稳定性,因此,本文针对UALA算法存在稳定性计算的静态性与稳定性自身的劫态性不符的问题,提出了迭代学习分配次序算法（UAILA）。UAILA通过迭代计算来动态确定稳定性,达到与稳定性的动态特性相符的目的,使其更好地用于确定数据对象的分配次序,以获得一组更加符合CKM算法聚类的分配次序。通过UAILA与UALA和CKM算法的实验结果对比表明,UAILA具有更好的聚类效果。从理论上讲,算法的准确率应该随着限制数的增加而提高,但是实验发现,限制数增加有时会降低算法准确率,且算法只用一组分配次序聚类会使算法具有较窄的搜索范围,容易陷入局部最优。针对上述的两个问题,本文采用多组基于限制符合度的分配次序,提出了动态分配次序的CKM算法（DAO-CKM）。该算法通过评估限制符合度来获取限制与聚类结果之间的关联信息,并将其作为用轮盘赌策略选择分配次序的依据,且用多组分配次序来扩大搜索范围,然后再根据定义的评价准则获取一组最优的聚类结果。通过实验证明了DAO-CKM算法的有效性和优越性。