基于成对约束的半监督聚类算法研究及其并行化实现

《基于成对约束的半监督聚类算法研究及其并行化实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、国内图书分类号：TP301.6密级：公开国际图书分类号：681.14西南交通大学研究生学位论文基于成对约束的半监督聚类算法研究及其并行化实现年级二〇一〇级姓名林超申请学位级别硕士专业计算机应用技术指导老师杨燕教授二零一三年五月ClassifiedIndex:TP301.6U.D.C:681.14SouthwestJiaotongUniversityMasterDegreeThesisSEMI-SUPERVISEDCLUSTERINGALGORITHMBASEDONPAIRWISECONSTRAINTSA

2、NDITSPARALLELIMPLEMENTATIONGrade:2010Candidate:LinChaoAcademicDegreeAppliedfor:MasterSpeciality:ComputerApplicationSupervisor:Prof.YangYanMay,2013西南交通大学学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权西南交通大学可以将本论文的全部或部分

3、内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复印手段保存和汇编本学位论文。本学位论文属于1．保密□，在年解密后适用本授权书；2．不保密□，使用本授权书。（请在以上方框内打“√”）学位论文作者签名：指导老师签名：日期：日期：西南交通大学硕士学位论文主要工作（贡献）声明本人在学位论文中所做的主要工作或贡献如下：(1)针对半监督聚类算法Cop-Kmeans中的约束违反问题，提出了一种全新的改进方案。该方案不仅能够使程序在迭代过程中完全避免约束违反，在算法运行时间效率上也明显优于传统的改进方案。(2)

4、针对成对约束自身特征在半监督聚类算法中给聚类结果可能造成的不良影响，进一步提出了相应的改进方案。即分别为Must-Link和Cannot-Link约束组制定了新的分配规则，能够最大限度的削弱成对约束的这种不良影响，进而能够在一定程度上提高聚类结果的精度。(3)利用MapReduce计算模型对改进的半监督聚类算法进行并行化实现，并在Hadoop搭建的并行处理平台上处理大数据集，大大提高了聚类效率。本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作所得的成果。除文中已经注明引用的内容外，本论文不

5、包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中作了明确说明。本人完全了解违反上述声明所引起的一切法律责任将由本人承担。学位论文作者签名：日期：西南交通大学硕士研究生学位论文第III页摘要作为数据挖掘领域中的一种重要方法，聚类分析能够发现数据对象自然的分布结构。它根据数据对象之间的相似性，把数据对象分割成簇，并保证同一簇内中数据的相似性尽可能大，而不同簇间数据的相似性尽可能小。从机器学习的角度来看，聚类分析是一种无监督的学习方法，它按照一定的优化准则对数据进

6、行分割，对数据的分析不需要知道其相关的背景知识。但是，现实生活中我们对数据的信息并不是一无所知，并且我们发现通过这些少量的已知信息能够找到数据对象标识或相互之间的约束信息。半监督聚类就是在传统的无监督聚类算法中引入先验知识来指导聚类过程，提高聚类结果精度。本文选择引入成对约束作为先验知识来协助指导聚类过程，分别建立了Must-Link和Cannot-Link约束组，用以描述两个样本数据间的关系。其中，Must-Link代表两个样本数据必须被分配到同一划分，而Cannot-Link则代表两个样本数据必须被

7、分配到不同的划分。详细介绍了基于成对约束的半监督聚类算法Cop-Kmeans，对算法比较常见的约束违反的问题，提出了全新的改进方法，在解决约束违反的同时，算法的运行时间效率也优于传统的改进方案。此外，针对成对约束自身特征可能给聚类性能带来的不良影响，进一步提出了相应的改进方案，能够最大限度的削弱这种不良影响，从而能够在一定程度上改善聚类结果精度。考虑到当聚类对象是一个大数据集或者高维数据类型时，传统的单机串行聚类算法无论是在内存或者运算能力都无法满足实际需求。本文选择运用“云计算”思想，采用并行处理方式

8、处理大规模的数据集。我们利用MapReduce计算模型对改进的半监督聚类算法进行并行化实现，并在Hadoop搭建的并行处理平台上处理大数据集。实验结果表明，采用并行计算方式能够显著提高聚类效率。关键词：半监督聚类；成对约束；并行计算；MapReduce西南交通大学硕士研究生学位论文第III页AbstractAsanimportantmethodinthefieldofdatamining,clusteranalysisisabletofin