基于领域知识的半监督聚类算法研究
第一章
绪论数据挖掘(又称知识发现)是近年来人工智能领域研究中的一个热点课题。它指从大量收集的数据中挖掘出未知的、非平凡的、有潜在决策价值的模式或知识的复杂过程[1l(21。它是在现实生活中各种数据量呈指数级不断增长，以及以数据库技术为核心的信息技术逐渐成熟的背景下产生的。聚类分析是数据挖掘的一个基本问题，其目的是将数据集中的数据对象“自然地”划分为若干个组(Gm即)或簇((Cluster)，使得处于同一组或簇内的数据对象尽可能地相似，而处于不同组或簇之间的数据对象尽可能不相似。数据对象的相似性描述通常是基于距离来计算的。如在欧式空间中，常用的距离计算方式有欧氏距离、曼哈顿距离和阂可夫斯基距离等。距离值越大，相似程度就越小，数据对象就越不可能处于同一组或簇，反之亦然。根据聚类分析过程中算法思想的不同，大致可以将聚类分析分为五类，即划分聚类、层次聚类、密度聚类、网格聚类和模型聚类方法。这些方法都有各自的优势和适用领域。
在商业、气象、军事、生物等众多领域中，聚类分析具有极为广泛的应用。从机器学习的角度来看，聚类分析是一个无监督的学习过程。然而在现实应用中，人们对待聚类数据集的相关领域知识并非一无所知。如何利用领域中先验知识或己知约束来改进聚类质量是半监督聚类分析的重要研究内容。具体来说，一方面，半监督聚类研究如何更好地利用和挖掘领域知识，以获得更多对数据挖掘任务有益的信息;另一方面，半监督聚类研究如何把获得的领域知识引入聚类，改进原有聚类算法。如通过一些常识性知识可以判断两个数据对象是否属于同一聚类中，以此作为约束条件，对聚类过程和聚类结果加以限制，就可以提高整个聚类结果的可理解性。1.1课题研究的背景和意义在数据挖掘任务中，实际数据往往由大量无标识数据和少量标识数据组成。由于标记数据的获取需要花费昂贵的代价，而且我们可以通过某种手段获得数据相关的领域知识，通过这种领域知识能够达到对数据更好的识别效果。本文所指的领域知识不但包括部分标识的数据对象，还包括利用专家系统、数据挖掘等方法得出的相关数据的知识。
半监督学习是处理此类数据的一种学习方法，近年来受到众多研究者的关注。目前，研究者们已提出多种半监督学习方法。一般来说，半监督的学习问题可分为两个方面:半监督的分类问题和半监督的聚类问题。前者是在有监督分类的基础上，通过无标识数据指导分类过程，以提高分类的准确性;后者则是在无监督聚类的基础上，通过标识数据指导聚类过程，以提高聚类质量。传统的聚类过程是一种无监督的学习过程。它主要存在以下不足:首先，它只考虑到数据本身的一些特性，忽略了先验知识的作用。这样导致了一些聚类的盲目性，所得的分类结果并不能真正满足用户需要。其次，传统的聚类方法都有一定的适用范围。如果想达到好的聚类效果，对性质不同的数据就要尝试不同的聚类方法。特别是当数据分布复杂的时候，处理起来就非常的费时费力，而且只有在聚类结果出来后才能对聚类效果进行评价。通过加入相关的领域知识，就会使得聚类过程带有一定的方向性和目的性，不但能够对聚类过程有所指导，同时还充分考虑到人的主观因素。首先，如果在聚类过程中加入约束信息，就可以避免错误的聚类倾向，从而使聚类过程向好的方向收敛。另外，主观因素对聚类结果的重要性逐渐为人们所认识。对于不同的应用，其相应的聚类结果应该不同。“如对金枪鱼、鲸和大象进行聚类，根据它们的相似性，鲸和大象也许会因为都是哺乳动物而分入一类，可是若用户的兴趣是基于‘是否生活在水中’这一特征，则鲸和金枪鱼应分入一类”。
如何把用户的倾向结合入聚类过程成为一个具有挑战性的问题[[3]一般来说，半监督聚类主要包括几下几个方面的优点:(1)有效利用领域特殊知识;(2)提高聚类效果;(3)标示特殊形状的聚类;(4)用户可以指导聚类过程，更好地反映用户需求。可见，半监督聚类能够充分利用己知的知识，提高传统聚类的适应能力和聚类效果，是对聚类从研究方式上的重要改进。这种改进更符合现实情况，具有非常重大的意义。自从2000年wagstaff提出利用两种约束关系来研究半监督聚类以来[[4]，国内外在此方面的研究己蓬勃开展起来。虽然对半监督聚类的研究己经取得了部分的成果，但在领域知识的利用、聚类算法的改进、统一模型的构建及实际应用方面都存在许多问题和分歧。目前，国内对半监督聚类的研究也处于刚刚发展阶段，对相关知识的积累比较薄弱。本文从此出发，较为详细论述了数据挖掘及半监督学习的方法，研究了如何利用领域知识进行半监督聚类分析，以及用实际例子展示了半监督聚类的应用方法及效果。本文的研究对于从事半监督聚类算法的研究分析，综合利用、挖掘领域知识及互联网用户行为分析等方面有积极的指导意义。.2国内外研究现状.2.1半监督聚类算法分类及目前主要方法1.1半监督聚类算法分类在聚类分析时，人们通过已有的领域知识，很容易做出以下判断:某两个数据对
参考文献
[1]Jiawei I-1an, Micheline Kamber著，范明，孟小峰等译.数据挖掘:概念与技术〔M].北京:机械工业出版社，2001. pp.l-25
[2]Pang-Ning Tan, Michael Steinbach,饰in Kumar.范明，范宏建译.数据挖掘导论[M].北京:人民邮电出版社，2006.
[3]何振峰.一种混合约束层次聚类算法，福州大学学报(自然科学版)[几2005.10,Uo1.33 no.5
[4]Kiri Wagstaff, Claire Cardie. Clustering w汕instance-level constraints [A]. TheSeventeenth International Conference on Mxhine Learn吨[C]. pp. 1103-1110. 2000
[5]Sugato Basu, Arindam Banerjee, Raymond Mooney, Semi-supervised clustering妙seeding, ICML [C], pp.19-26. 2002.
[6]Ayhan Demirez, K P Bennett, M. J. Embrechts. Semi-supervised clustering usinggenetic algorithms, Artificial Neural Netowrks in Engineering [J], Nov 1999.
[7]Kiri Wagstaf. Claire Cardie, Seth Rogers, and Stefan SchroedlL Constrained K meansClustering w汕Background Knowledge [A]. In Proc. of the 18th InternationalConference on Machine Learning
[8]Eric P Xing, Andrew Y Ng, Michael Jordan and Stuart Russell. Distance metric
[9]learning, with application to clustering with side-information[A]. Advances in Neural
[10]Information Processing Systemsl5[C]. pp.505-512.
[11]Dan Klein, Sepandar D.Kamvar, Christopher D.Manning. From instance-levelconstraints to space-level constraints: Making the most of prior knowledge in dateclustering, ICML [C], 2002. pp.307-
[12]Tao Li, Chris Ding, Michael I. Jordan. Solving Consensus and Semi-supervisedClustering Problems Using Nonnegative Matrix Factorization[C]. ICDM 2007.
[13]Mdchail Bilenko, Sugato Basu, Raymond J. Mooney. Integrating constraints and metriclearning in semi-supervise clustering, ICML[C], 2004.
摘要 4-6
ABSTRACT 6-8
第一章 绪论 16-22
1.1 课题研究的背景和意义 16-17
1.2 国内外研究现状 17-20
1.2.1 半监督聚类算法分类及目前主要方法 17-19
1.2.2 半监督聚类的实际应用 19-20
1.3 本文的主要工作及组织结构 20-22
第二章 数据挖掘及聚类分析技术 22-36
2.1 数据挖掘技术简介 22-25
2.1.1 数据挖掘的定义、历史和发展 22-23
2.1.2 数据挖掘的主要方法 23-25
2.2 聚类分析技术 25-30
2.2.1 聚类分析概述 25-27
2.2.2 聚类分析方法分类 27-30
2.3 基于领域知识的半监督聚类基础知识 30-34
2.3.1 半监督学习概述 30-32
2.3.2 领域知识的获取和表示 32-34
2.4 本章小结 34-36
第三章 COP-KMeans及改进的MLC-KMeans算法 36-48
3.1 COP-KMeans算法概述及其不足 36-38
3.1.1 COP-KMeans算法概述 36-37
3.1.2 COP-KMeans算法的不足 37-38
3.2 MLC-KMeans半监督聚类算法 38-42
3.2.1 MLC-KMeans算法基本思想 38-40
3.2.2 MLC-KMeans算法描述 40-42
3.3 MLC-KMean聚类效果实验分析 42-48
3.3.1 试验方案 42-43
3.3.2 实验结果 43-46
3.3.3 实验结果分析及总结 46-48
第四章 基于属性变换的半监督聚类 48-64
4.1 问题描述和出发点 48-50
4.1.1 属性变换的出发点 48-49
4.1.2 基于属性变换的半监督聚类方法描述 49-50
4.2 属性约简方法概述 50-53
4.3 基于属性约简的半监督聚类分析 53-58
4.3.1 算法描述 53-55
4.3.2 实验结果及分析 55-58
4.4 基于约束属性范围扩展的半监督聚类 58-62
4.4.1 算法描述 58-60
4.4.2 实验结果及分析 60-62
4.5 讨论与小结 62-64
第五章 基于关联规则的半监督聚类方法 64-74
5.1 问题出发点及描述 64-65
5.1.1 问题出发点 64-65
5.1.2 问题描述 65
5.2 关联规则方法及Apriori算法 65-69
5.2.1 关联规则方法概述 65-67
5.2.2 Apriori算法 67-69
5.3 基于关联规则的半监督聚类 69-72
5.3.1 算法描述 69-71
5.3.2 实验结果及分析 71-72
5.4 讨论与小结 72-74
第六章 半监督聚类在Web上的应用 74-86
6.1 web数据挖掘概述 74-76
6.1.1 Web数据的特点 74-75
6.1.2 web数据挖掘的概念和分类 75
6.1.3 web数据挖掘的意义 75-76
6.2 web数据挖掘的处理流程 76-78
6.3 半监督聚类方法在网站注册用户聚类方面的应用 78-84
6.3.1 凤凰网注册用户的聚类分析 78-81
6.3.2 注册用户的半监督聚类分析 81-84
6.4 本章小结 84-86
第七章 结束语 86-88
7.1 本文的主要工作回顾 86
7.2 进一步的工作 86-88
参考文献 88-91
附录 91-94
致谢 94-95
攻读学位期间发表的学术论文 95-96
作者和导师简介 96-97
北京化工大学硕士研究生学位论文答辩委员会决议书