我的毕业论文：半监督机器学习的快速算法研究

六月 25th, 2009 发表评论阅读评论

本科毕业设计（论文）说明书

半监督机器学习的快速算法研究

学院理学院

专业数学与应用数学

学生姓名 Keengle

指导教师 Xiaolan Liu

提交日期 2009 年 6月 3日

华南理工大学

毕业设计（论文）任务书

兹发给 2005级应数班学生 Keengle 毕业设计（论文）任务书，内容如下：

1.毕业设计（论文）题目：半监督机器学习的快速算法研究

2.应完成的项目：

（1）半监督机器学习产生的背景

（2）了解和掌握现有的半监督学学习的主要方法，找出其优缺点

（3）改进或设计一种快速的求解方法，并分析其性能

（4）编程实现算法，应用测试数据库中的数据，或者实际的数据，将提出的算法的效果与一些现成的算法进行对比，分析结果

3.参考资料以及说明：

（1）Fei Wang etc. Label Propagation Through Linear Neighborhoods. IEEE Transactions on Knowledge and Data Engineering, 2008: 55-67.

（2）Fei Wang, Changshui Zhang. Fast Multilevel Transduction on Graphs. The 7th SIAM Conference on Data Mining. Minneapolis, Minnesota. 2007.

（3）周志华, 王珏主编. 机器学习及其应用. 北京：清华大学出版社, 2007.

（4）Chapelle etc. Semi-supervised learning. MIT press, 2006: 151-168.

（5）X. Zhu. Semi-supervised learning literature survey. Technical Report 1530, Department of Computer Sciences, University of Wisconsin at Madison, WI, Apr. 2006.

4.本毕业设计（论文）任务书于2009 年2月26 日发出，应于2009年6月3日前完成，然后提交毕业考试委员会进行答辩。

专业教研组（系）、研究所负责人审核年月日

指导教师签发年月日

毕业设计（论文）评语：

毕业设计（论文）总评成绩：

毕业设计（论文）答辩负责人签字：

年月日

摘要

半监督学习近年来成为一个热门的研究领域越来越受研究者的重视和青睐，它能在使用少量人力的同时保证学习的质量，所以在理论和实践上都很受关注。

在实际应用中，遇到的问题的规模都是比较大的，而多数基于图的半监督学习算法的计算时间都比较长，因为它们要对大矩阵进行求逆矩阵的运算。为了提高求解效率，本文基于二分法的思想提出了一种快速的半监督机器学习的二分聚类算法。

本文先对半监督学习和该论题的研究现状进行了说明，而后介绍了半监督学习的表示、两个基本假设和目前解决该问题的现有的主要算法。接下来详细介绍了本文提出的二分聚类算法。二分聚类算法是一种基于聚类分析算法的递归算法，其算法原理中使用了聚类分析、特征选择等过程。但此算法并不是一开始就试图得出所有的分类，而是每次只是把输入数据集分为两份，之后再递归对子数据集进行处理。而提高算法计算速度的关键在于对属性的使用上，对每一个二分过程，算法先试图使用少量的属性集合对数据集进行二分，当判断出分组不理想时，将回溯去使用更多的属性进行分组。通过逐步缩小的数据集以及使用部分属性进行小范围分组，从而提高了计算效率。最后，本文后一章对此算法做了实验，并对实验结果进行了比对。

实验结果表明，对于部分的半监督学习的实例，应用二分聚类算法在正确率和效率上得到令人满意的效果。

关键词：半监督学习，二分聚类，快速算法，聚类算法

Abstract

Semi-supervised learning in recent years has become an increasingly popular research field and has attached much attention of researchers. It can guarantee the quality of learning by using a small number of samples, so it is of great importance theory and practice.

In practice, the scale of the problems encountered are relatively large, while most graph-based semi-supervised learning algorithms need much computing time, as they involve computing inverse of large matrix. In order to improve efficiency, based on the idea of dichotomizing search, this paper presents a fast semi-supervised machine learning algorithm —dichotomizing clustering algorithm.

Semi-supervised learning and its research history are described. And the paper introduces the two basic assumptions of semi-supervised learning and currently existing main algorithms. In order to improve efficiency, dichotomizing clustering algorithm are proposed in the paper. dichotomizing clustering algorithm is a recursive algorithm based on cluster analysis. This algorithm does not attempt to identify all the classifications at the beginning, but each time the input data set is divided into two parts and then we use the algorithm recursively to deal with each part. The key of improving the speed of the algorithm lies in the use of attributes of each two sub-process. The algorithm first attempts to use a small number of properties to do the bisection process. If the results of the bisection process are not satisfied, the algorithm will continue to use more attributes to do classification. Progressive narrowing the number of the data sets and the properties results in the improved computational efficiency. Finally, we do some experiments to verify the results of our algorithm.

The experimental results show that the proposed dichotomizing clustering algorithm can obtain better accuracy and efficiency than some other algorithms in UCI datasets.

Keywords: Semi-supervised learning, Binary clustering, Fast algorithm, Clustering algorithm

我的论文能够如期完成，而四年大学生活也即将结束，这里我要感谢一下在我学习和生活过程中给予很大帮助的老师和同学们。

首先，我要衷心地感谢在我的毕业论文撰写过程中给予悉心指导的Xiaolan Liu老师。Xiaolan Liu老师严谨的治学态度、对学术永无止境的探索和诲人不倦的师表风范是我学习的楷模。老师为我提供了一个宽松的选题研究过程，从论文的选题、编写到最后定稿，都给予了悉心、细致的指导以及许多宝贵的意见，老师的教诲将使我受益不尽。值此论文完成之际谨向刘老师表示衷心的感谢。

其次，我要感谢在大一大二时把我带进数学殿堂的Zhengrong Liu老师和Xilin Tang老师，是他们细致、耐心的知识讲解，循序渐进的教学技巧，把我从迷茫的大学新生逐渐培养成习惯独立思考、关注逻辑的数学系学生。他们的学术造诣以及严谨的治学态度都令我受益良多。

我也要感谢在大学期间每一位曾经教过我、指导过我学习的老师，还有我身边的同学，我的家人，是他们的支持、帮助和鼓励让我完成了我的学业，在此一并感谢。