论文部分内容阅读
聚类学习是机器学习的一个重要研究内容,被广泛应用于金融欺诈、医疗诊断、图像处理、信息检索和生物信息学等领域.目前,不同类型的聚类模型和算法已被广泛地提出和发展.然而,随着信息技术和采样技术不断地发展,需要处理的数据不断呈现出属性类型的多样性、高维性、规模的海量性、分布的不均匀性、时空特征的动态性等复杂结构.由于聚类分析是数据驱动的,不同的数据特征往往导致不同的聚类模型及算法,没有适合于所有特征的聚类学习方法.因此,当复杂数据成为现代社会中数据资源的主体时,如何从它们中发现隐藏的类结构已成为聚类学习的一个重要研究内容,并引起了广泛地关注.本文将以复杂数据为研究对象,构建符合其相应特征的聚类模型,并对相关理论与高效算法进行了深入的研究.本文的主要研究成果有:(1)提出了一种面向高维分类数据的属性双加权优化聚类算法.在该算法中,一种新的属性加权模式被提出,并将其应用于聚类过程中形成新的聚类优化问题.严格地获得了该算法的划分矩阵、类中心集和属性权值在迭代过程中的更新规则,从而保证了算法能够在有限次迭代中获得局部最优解.证明了该算法的收敛性.实验结果表明新提出的算法既继承了Chan等人提出的属性加权算法的简单性,又有效地克服了它们在面对高维分类数据时的加权失效问题.(2)提出了一种针对快速全局K-Means聚类算法(FGKM)的加速机制.在该机制中,利用数据点的局部几何信息在保证FGKM聚类结果的同时减少其大量不必要的距离计算,从而使得FGKM聚类算法能够有效地处理大规模数据.分析了基于提出的加速机制的FGKM算法的空间和时间复杂度.实验结果表明加速后的FGKM算法相比原始的FGKM和其它改进的FGKM算法需要更少的聚类时间和距离计算次数.值得注意的是,新算法的有效性随着数据的维数和聚类数目的增加而变得更加明显.(3)揭示了非平衡数据对模糊K-Means聚类算法的表现影响以及聚类结果的“均匀效应”产生的原因.理论分析表明了模糊K-Means聚类算法相比K-Means聚类算法在聚类非平衡数据时更倾向于产生“均匀效应”,并且随着模糊因子α值的增加而变得严重.为了避免聚类结果受到“均匀效应”的影响,提出了一种基于多类中心的模糊K-Means聚类算法.在该算法中,首先应用了全局模糊K-Means聚类算法产生可信赖的类中心.进一步,基于模糊因子α和所产生的类中心之间的最大最小距离,提供了一种确定聚类数目的方法.最后,将提出的一个分离测度应用于组织多类中心去代表每个类.实验结果表明该多类中心聚类算法能够有效地聚类非平衡数据.(4)提出了一种新的面向动态分类数据流的聚类框架.在该框架中,首先提出了一种新的融合类内和类间信息的类特征描述方式以及基于它的数据类别标记方法.该方法弱化了滑动窗口中的类尺度对标记结果的影响.接着,定义了一个有效性函数,并将其应用于去评测新窗口中对象标记结果的有效性.基于该函数,概念漂移检测问题被转化为一个凸规划问题.利用该问题的最优解来帮助人们去发现漂移的概念,从而使得检测结果能够独立于数据类别标记结果.实验结果表明新的聚类框架相比其它框架不仅能够有效地标记新窗口的对象而且能准确地发现漂移的概念.(5)提出了一个泛化的聚类有效性函数,并在此基础上,分析了K-Modes目标函数、分类效用函数和信息熵函数之间的关系.分析结果表明分类效用函数在评测聚类结果的有效性上等效于信息熵函数,且优于K-Modes目标函数.由于泛化的有效性函数仅仅基于类内信息,因此,进一步回答了仅用类内信息也能够有效地评测聚类结果的问题.最后分析了聚类有效性函数的归一化在评测同一算法在不同数据集上的表现时的重要性,并给出了泛化的有效性函数在一些情况下的归一化方法.本文的研究成果进一步丰富了面向复杂数据的聚类学习研究,为生物信息数据、Web数据、客户交易数据等相关领域的数据挖掘与知识发现提供了新的技术支撑.