《基于半监督学习方法的研究》-公开DOC·毕业论文.doc

基于半监督学习方法的研究摘 要 近几年来随着机器学习在数据分析和数据挖掘中的广泛应用,半监督学习的理论研究成果已经部分应用于实际问题的解决半监督学习(Semi-supervised Learning)是模式识别和机器学习中的重要研究领域,一直为国际机器学习界所广泛关注本文主要研究了半监督学习方法，具体考虑了不同度量对半监督学习的影响考虑关于标记的和未标记数据的一般问题的学习，其通常被称为半监督学习或转导推理半监督学习的原则性方法是定义一个有关标记的和未标记的点集的固有结构所共同显现的足够平稳的分类函数实验结果表明，使用指数度量的GCM算法的性能最优，而使用欧几里得度量的GCM算法的性能最差；另外，不同度量中的参数取值对算法的性能具有一定的影响关键词：半监督 机器学习 GCM CM ABSTRCATWith Machine learning methods being widely applied for real world data analysis and data mining, semi-supervised learning has been introduce for solving more and more real world problems.Semi-supervised learning, which combines information from both labeled and unlabeled data for learning tasks, has drawn wide attention. We consider the general problem of learning from labeled and unlabeled data,which is often called semi-supervised learning or transductive inference.A principled approach to semi-supervised learning is to design a classifying function which is suf_ciently smooth with respect to the intrinsic structure collectively revealed by known labeled and unlabeled points. Experimental results show that performance of GCM algorithm for using the exponential measure is superior to other measures and performance of GCM algorithm for using the Euclidean measure is inferior to other measures. Moreover, arguments for different measures impact on the performance of algorithm.Key words：Semi-supervised Machine learing GCM CM 目 录一 引言 11.1研究背景和意义 11.1.1研究背景 11.1.2研究意义 11.2国内外研究现状 11.3研究内容 21.4论文组织与安排 2二 半监督学习算法 32.1朴素贝叶斯分类器 32.1.1贝叶斯法则 32.2.2 朴素贝叶斯分类器学习 32.2 k-近邻算法 4三 常用的度量方法 63.1加权s阶Minkowski度量 63.2非线性度量 63.3 K近邻度量 63.4指数度量 63.5双曲正切度量 7四 基于核策略的半监督学习算法 84.1 CM算法 84.2 GCM算法 8五 总体设计与详细设计 105.1总体设计 105.2 详细设计 10六 实验研究与分析 136.1实验数据 136.1.1 CM算法实验数据 136.1.2 GCM算法实验数据 146.2实验方法 146.2.1 CM实验方法 146.2.2 GCM实验方法 146.3 实验结果与分析 15七 结论 17谢 辞 18参考文献 19一 引言1.1研究背景和意义1.1.1研究背景 当前社会已进入高速发展的信息化时代，每天面对的数据大量而繁琐，数据分类的工作越来越重要。

在传统的监督学习中，学习器通过对大量有标记的训练例进行学习，从而建立模型用于预测未见示例的标记目前，利用未标记示例的主流学习技术主要有半监督学习和主动学习，但是它们的基本思想却有显著不同在半监督学习中，学习器自行利用未标记示例，学习过程无人工干预主动学习假设学习器对环境有一定的控制能力，可以主动向学习器之外的神谕（可以是人，也可以是能够为示例提供真是标记的其它过程 ）进行查询来获得训练例的标记对比半监督学习和主动学习可以看出，后者在利用未标记示例的过程中需要与外界交互，而前者则完全依靠学习器自身，正因为此，许多学者对半监督学习做了大量研究1.1.2研究意义随着数据收集和存储技术的飞速发展，人类面对的信息量是大量并且繁杂的，怎样从中选择自己感兴趣的信息是一个很大的问题半监督学习问题的关键是如何获得有标记的示例，例如在进行web网页推荐时，需要用户标记出哪些网页是感兴趣的，但是很少有用户愿意花大量时间来提供标记正因为此，半监督学习可以成功解决用户面对的信息量大的问题，人们很容易获得自己需要的信息1.2国内外研究现状机器学习是人工智能的重要研究分支，它是衡量系统是否具有智能的重要标志机器学习方法主要分为监督学习与无监督学习。

监督学习可以描述为：给定一个具有已知类别的数据集{(x1,y1),…,(xn,yn)}，其中xi=(xi1,…xin)为第i个样本的属性向量，元素xij为第i个样本的第j个属性值，该属性既可以为离散值也可以为连续值；同样yi也可为离散或连续的值属性向量x与y之间存在某种复杂函数关系y = f(x)，通过监督学习算法对已知样本进行学习，可以得到用于近似表示该未知函数的预测器，监督学习主要用于回归与分类问题无监督学习是从样本的特征向量出发研究通过某种算法将特征相似的样本聚集在一起，从而达到区分具有不同特征样本的目的，无监督学习主要用于聚类监督学习的最大特点是具有先验知识（类标号）；而无监督聚类学习并不具有这种先验知识然而，在现实生活中，由于获取有标号数据是非常困难的，再加上获取它们花费的费用较高及所需时间较多，同时，无标号数据却是容易获得，而这部分数据却很少使用，即所谓的半监督分类学习[1]半监督分类学习的主要目标是如何利用少量标号数据与大量无标号数据提高系统的泛化能力最近，研究人员针对半监督学习进行了深入研究，并提出了一些半监督学习方法，例如Chapelle与Zien[2]提出的LDS算法，Zhou等[3]提出的CM算法，Zhu等提出的GRFM算法；另外，Zhou与Zhan、Wang与Zhou对半监督学习进行了研究，并提出了一些半监督学习算法。

在本文中，对CM算法进行了推广，研究了使用不同核的半监督学习算法的性能1.3研究内容通过实现CM算法，理解核矩阵（权矩阵）是算法中重要的一步将CM算法中的第一步求权矩阵中的元素公式一般化，即Wij= f（d（xi,xj））,通过几种不同的度量方法，选择出性能最佳的GCM算法1.4论文组织与安排第二部分介绍了半监督学习算法：朴素贝叶斯分类器和k-近邻算法；第三部分介绍了权矩阵的几种度量方法；第四部分介绍了CM算法和GCM算法；第五部分介绍了CM方法中算法的总体设计和详细设计；第六部分分别对CM和GCM的实验结果进行了分析；第七部分总结了本文的内容和半监督学习的发展方向 二 半监督学习算法2.1朴素贝叶斯分类器贝叶斯学习方法中实用性很高的一种为朴素贝叶斯学习器，常被成为朴素贝叶斯分类器2.1.1贝叶斯法则在机器学习中，通常我们感兴趣的是在给定训练数据D时，确定假设空间H中的最佳假设所谓最佳假设一种办法是把它定义为在给数据D以及H中的不同假设的先验概率的有关知识的最可能假设贝叶斯理论提供了一种直接计算这种可能性的方法更精确的讲，贝叶斯法则提供了一种计算假设概率的方法，它基于假设的先验概率，给定假设下观察到不同数据的概率以及观察到的数据本身。

贝叶斯法则是贝叶斯学习方法的基础，因为它提供了从先验概率P(h)以及P(D)和P(D|h)计算后验概率P(h|D)的方法贝叶斯公式：P(h|D) = (2-1)从直观上可以看出，P(h|D)随着P(h)和P(D|h)的增长而增长；同时也可以看出P(h|D)随P(D)的增加而减少这是很合理的，因为如果D独立于h时被观察到的可能性越大，那么D对h的支持度越小2.2.2 朴素贝叶斯分类器学习朴素贝叶斯类器应用的学习任务中，每个实例x可由属性值的合取描述，而且目标函数f（x）从某有限集合v中取值学习器被提供一系列关于目标函数的训练样例以及新实例（描述为属性值的元组），然后要求预测新实例的目标值贝叶斯方法的新实例分类目标是在给定描述实例的属性值〈a1，a2…an〉下，得到最可能的目标值Vmap (2-2)可使贝叶斯公式将此表达式重写为： (2-3)估计每个P（vj）很容易，只要计算每个目标值vj出现在训练数据中的频率就可以然而，除非有一个非常大的训练数据的集合，否则用这种方法估计不同的P（a1，a2…an |vj）项不太可行。

问题在于这些项的数量等于可能实例的数量乘以可能目标值的数量因此为获得合理的估计，实例空间中达到每个实例必须出现多次朴素贝叶斯分类器基于一个简单的假定：在给定目标值时属性值之间相互条件独立换言之，该假定说明在给定实例的目标值情况下，观察到联合的a1，a2….an的概率等于每个单独属性的概率乘积：P（a1，a2…an |vj）=∏iP(ai|vi) (2-4)可得到朴素贝叶斯分类器所使用的方法： Vnb=argmaxP(vi)∏P(ai|vi) (2-5)其中，Vnb表示朴素贝叶斯分类器输出的目标值注意，在朴素贝叶斯分类器中，须从训练数据中估计不同P（ai|vj）项的数量只是不同的属性值数量乘以不同目标值数量—这比要估计P（a1，a2…an |vj）项所需的量小得多概括地讲，朴素贝叶斯学习方法需要估计不同的P（vj）和P（ai|vj）项，基于它们在训练数据上达到频率这些估计对应了待学习的假设然后该假设使用上式的规则来分类新实例只要所需的条件独立性能够被满足，朴素贝叶斯分类Vnb等于MAP分类。

2.2 k-近邻算法KNN法即K最近邻法，最初由Cover和Hart于1968年提出的，是一个理论上比较成熟的方法该方法的思路非常简单直观：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别k-近邻算法是实例学习方法中最基本的方法这个算法假定所有的实例对应于n维空间中的点一个实例的最近邻是根据标准欧式距离定义的把任意的实例x表示为。