半监督分类方法论文（精选7篇）
半监督分类方法论文 篇1
0 引言
机器学习[1]是人工智能学习中的一个重要研究领域，它将数据转换成信息，可以揭示数据背后的真实含义，从而得到了广泛的应用。在机器学习中，人们需要利用有价值的数据信息构造精准的模型，这就必须对数据进行预处理。其中一个重要的数据预处理方法是对数据进行分类，即将复杂的海量数据按照问题所需要的数据信息进行归类，以利于问题的解决。它主要包括两个过程:首先根据训练数据集利用某种策略学习一个分类器，然后利用分类器预测新数据的类别。
按照传统的理论框架，分类问题可以分为有监督分类和无监督分类[2]。有监督分类利用已标记的样本信息建立分类器，而无监督分类利用未标记样本数据训练分类器。在大数据时代的今天，未标记样本数据的获得已变得比较容易，而标记样本数据需要通过利用人们的专业知识与经验获得，这就导致了有价值的标记样本信息不容易获得。从而使有监督分类仅通过少量的标记样本建立的分类器并不具有较好的泛化能力，同时也浪费了大量的未标记样本信息。无监督分类只利用了未标记样本数据，不仅忽略了标记样本所具有的重要信息，而且得到的分类器的准确性大大降低。据此，人们提出了半监督分类，该分类方法旨在克服有监督分类和无监督分类的缺点，建立更具有泛化能力和高性能的分类器。
1 半监督分类概况
1.1 基本思想
半监督分类就是利用少量已标记样本及其类别信息和未标记样本的数据分布信息建立一个分类模型，并利用此模型对未知样本数据集进行类别判定。该方法充分利用标记样本信息，不仅降低了对标记样本量的要求，同时也提高了分类模型的准确率和泛化能力。Zhu Xiaojin用图1[3]很好地对比了只利用标记样本得到的分类器与同时利用标记样本和未标记样本得到的分类器。显然，图1(b)中的分类模型是比较准确的。
为了能够充分地利用未标记样本信息并建立较精确的模型，半监督分类需要满足一些基本假设，常用的基本假设有聚类假设和流形假设[2]。聚类假设是指在同一聚类中的样本很可能是同一类别，决策边界应该通过数据较为稀疏的地方。流形假设是指处于一个很小的局部邻域内的样本应具有相似的性质，即具有相似的类别标记。两种假设的基本思想是一致的，其中聚类假设要求相似样本的类别输出必须是完全相同的，主要研究模型的整体特性，而流形假设不要求相似样本必须具有同一类标号，只要求具有相似的输出结果，即反映了决策函数的局部平滑性，主要研究模型的局部特性。因此，聚类假设适用于简单的纯数据分析，也可处理复杂的数据，但放松输出条件的流形假设能更有效地处理现实中的复杂数据，它的应用范围相对来说也更加广泛。
1.2 研究现状与应用领域
半监督分类在20世纪70年代就已出现，它属于半监督学习的范畴，从有监督学习的角度出发，着重于研究离散数据的分类问题，其最初的研究工作开始于Shahshahani的文献[4]。由于此分类方法有较高的准确性，且能省去许多为获得标记样本所花费的人工成本，人们对它的研究兴趣也就逐渐高涨。目前，所研究出的基本分类方法大致有以下六类[5]:基于生成模型的半监督分类方法、基于自训练的半监督分类方法、基于协同训练的半监督分类方法、基于图的半监督分类方法、基于支持向量机的半监督分类方法和基于流形正则化的半监督分类方法。
半监督分类方法的应用范围很宽广，如文本分类、信息检索、图像处理、安全监测、特征识别、疾病诊断等[6]，能够在数据挖掘、机器学习和生物信息学等领域中发挥积极的作用。
2 半监督分类的常用算法
2.1 基于生成模型的半监督分类方法
生成模型是比较早的半监督学习算法，1977年Dempster提出的EM[7]算法中就已体现。该算法直接采用聚类假设，并综合标记样本和未标记样本的数据信息，建立样本的联合概率分布模型P(X,Y)，通过假设训练样本的概率分布P(X)求出样本X属于类别Y的后验概率，即根据下式进行计算:
并根据贝叶斯决策原理对样本进行分类，再用最大期望算法(EM)进行标记评估和模型参数的优化估计。生成模型的缺点是在建立模型时首先要假定数据的概率分布，而在实际应用中，由于数据的稀疏性，所假设的特定概率分布并不一定是准确的，此时可以利用判别方法直接求解后验概率P(Y|X)，并将其作为预测模型。文献[8]将生成方法和判别方法相融合，利用其原理的优势互补来建立图像的分类模型，从而得到了更好的分类效果。在这之后，文献[9]又进一步地研究了生成模型问题，将概率生成模型引入到网络数据分类方法中，实现了在许多同质性程度较低的网络上也能够得到很好的分类效果。
生成模型主要是从统计学的角度来表示数据的分布情况，能够真实地反映出数据本身的相似度，并常用于文本分类[1]、图像视频标签[2]、医疗诊断[6]和网络数据分类[9]等领域。
2.2 基于自训练的半监督分类方法
自训练方法由Hebert等人在2005年正式提出，采用聚类假设并以有监督分类方法为基础。首先利用少量的标记样本构建初始分类器，然后对未标记样本的类别进行预测。将预测可信度较高的样本及其类别信息一并加入到训练样本中更新分类器，不断循环直到满足某个条件结束算法。该方法不仅需要一定的时间来训练分类器，而且所产生的分类器的准确性依赖于有监督分类的初始分类器，若初始分类器有偏差，将会导致最终模型的不精确，这是该方法的一大缺点。如果预测的未标记样本的类别是错误的类标号，也将导致模型由于不断地迭代而产生更大误差的结果。针对此问题，文献[10]采用了小波熵来挑选在当前分类器中最具信息量的样本，尽量减少在迭代过程中产生的误差，提高分类器的精度。为进一步扩展自训练方法的应用，文献[11]采用自训练方法进行文本分类，在模型建立中采用最大熵分类器对初始的少量已标记数据进行训练，进而对测试集进行分类预测，以进一步提高模型对文本分类的准确率。
自训练算法原理简单易理解，且使用简洁，常用于文本分类[2]、生物医学信息处理[10]和文本分类[11]等方面。
2.3 基于协同训练的半监督分类方法
标准协同训练算法[12]是由Blum和Mitchell于1998年提出的，隐含地利用了聚类假设或流形假设。首先认为一个数据集的所有特征可以划分为两个充分冗余的特征子集(也称为视图)，且在训练样本足够的情况下每个视图都足以建立一个较强的分类器。然后利用标记样本信息在两个视图上训练出两个同类型的分类器，通过分类器预测未标记样本类别，并筛选出可信度较高的样本加入到另一个分类器的训练样本中，继而更新分类器，如此迭代直到满足停止条件。该算法的基础是选取视图，而视图是建立在属性集的分割上，因此分割属性集就成为协同训练所要研究的主要问题。而文献[12]中的视图划分是任意的，可能会造成分类器的不准确，为克服此缺点，文献[13]利用了粗糙集中的属性约简对空间进行分割，能够有效地降维数据且不造成分类信息的丢失，该算法将两差异性的属性约简作为模型的两个视图，并在两个视图上进行主动学习和协同训练，从而不断地提升分类器的性能。
在视图的选择中，标准的协同训练算法要求所得到的视图是充分冗余的，而在现实的海量数据中，充分冗余视图的获取是非常困难的。针对此问题，Goldman和Zhou提出了另一种协同训练算法[14]，此算法不需要充分冗余视图，而是使用决策树在同一个属性集上训练出两个不同的分类器，并利用统计方法来估计标记置信度。但该算法的分类效果并不好，且实用范围较窄。在此研究基础上，Zhou等在2005年首次提出了Tri-training算法[15]，该算法既不需要视图充分冗余也不需要不同类型的分类器，而是在单一视图上使用三个分类器进行协同训练，并利用集成学习来提高分类模型的泛化能力，得到了很好的分类效果。紧接着，Zhou等人又于2007年在文献[16]中将Tri-training算法进一步扩展与完善，得到Co-Forest算法。该算法增加了分类器的个数，不仅保持了分类器的多样性，也提高了分类的准确性。
在基于协同训练的半监督分类方法中，由于数据的复杂性以及标记样本数据较少，初始分类器的性能较弱，导致有噪声的未标记数据引入。针对这一问题，文献[17]在Tri-training的基础上，提供人机交互和噪声过滤机制来减少噪声的引入，进行增量训练来提高未标记样本的利用正确率。接着，文献[18]也提出了一种减少噪音引入的方法，将基于图的半监督知识引入到协同训练中，运用多个分类器对未标记样本的置信度进行比较，并利用图的结构信息选取更可信的未标记样本加入训练集中，提高学习器的分类精度。近期，文献[19]同样为了降低噪声的引入，利用遗传算法辅助协同训练算法挑选有价值的未标记数据，有效更新分类器的性能。
协同训练分类方法简单易用，其改进方法也较多，应用范围非常广泛，如网页分类[2]、自然语言处理和图像内容检索[15,16]等方面。
2.4 基于图的半监督分类方法
基于图的半监督分类方法直接或间接地利用流形假设，并用一个加权无向图G(V,E)来表示所有样本之间的关系。其中，V是顶点集，表示所有训练样本，E是边集，表示所有样本中相邻两样本之间的某种近似关系，可将这种边的近似关系看作是距离或者是夹角等。首先，在构造邻近图时，两相邻样本xi和xj应满足关系[20]:
若不满足上式，样本之间则没有近邻关系。然后构造权重矩阵W(可以利用热核函数或0-1函数等构造权值)。最后利用图的相关知识建立分类决策函数，同时加入正则化项使图尽量满足平滑性。该方法不仅可以充分地考虑训练样本之间的几何结构，克服一般分类方法的一些缺点，如分类模型对不均衡类数据的识别能力较低;还能够将数据之间的结构信息转化为无向图，并利用图的理论知识解决实际问题。基于此，文献[21]中利用了局部保持投影方法(LPP)，不但保持了样本间的局部几何结构，提高对有价值数据信息的识别能力，还能够发现高维数据特征的非线性结构。由于在模型的建立中，许多方法常常利用欧氏距离来构造邻接矩阵W，但欧氏距离对噪音和稀疏矩阵不敏感，导致算法精度下降，文献[22]利用了相对变换距离选择样本的邻近点，即将原始数据空间转换到相对空间再进行样本之间的距离计算，使得噪声和孤立点远离正常点，从而保持数据的真实结构。
基于图的半监督分类算法中最具代表性的一种常用算法即是标签传播算法(LPA)[23]，它由Zhu等提出，该算法对任意的数据分布形状都能有很好的分类效果。其原理即是在图的基础上利用已标记样本的标签信息在节点之间通过其相似度进行传播，预测未标记样本的标签信息，传播规则是相似度越大的节点之间标签也就更容易传播，即属于同一类的趋势就越大。在传播过程中，保持已标记的样本标签不变，每个未标记样本节点都要根据邻近节点的标签分布情况来更新自身的标签，直到所有节点的标签都稳定时迭代结束。为进一步简化问题，Barber等人在标签传播算法中加入了约束条件[24]，并引进目标函数，问题便转化为最优化问题，从而提高了分类算法的鲁棒性和稳定性。但标签传播算法仍有缺点，该算法在迭代中会发生标签振荡[25]的现象，某些节点的标签经过几次迭代后传播回原始的标签，导致分类模型产生偏差。基于此问题，Raghavan采用异步更新的策略，设定在算法中某节点的标签由上下两轮的邻居节点的标签共同决定，提高算法的准确率。在常用的基于图的半监督算法中，往往需要预先设定图的结构，导致了样本数据在标签传递的过程中构建图不准确的缺点，文献[26]提出了一种基于自适应图的半监督分类方法，使算法能够自适应地学习到最优的图和标签，仅利用少量样本数据就可使模型得到较高的分类准确率。
基于图的分类方法巧妙地利用了数学知识，将复杂的实际问题简化为图的结构信息，实用且高效。常用于网页分类[2]、多媒体信息分类、社区发现和信息检索等[25]领域中。
2.5 基于支持向量机的半监督分类方法
支持向量机(SVM)[27]是由Vapnik等人在1992年提出的，它是一种有监督的分类方法，只利用标记样本信息，在特征空间上用最大间隔法来构造分划超平面，使超平面通过数据相对稀疏的区域并尽可能将标记样本正确分开，即直接利用了聚类假设。对于低维数据，直接利用线性支持向量机来建立分类决策函数:
并引入拉格朗日乘子将原始问题转化为其对偶问题，进而求出参数w和参数b。对于复杂的高维数据需利用核技巧将非线性问题转化为线性问题，并建立分类决策函数:
从而利用线性知识解决非线性问题。
基于支持向量机的半监督分类方法在支持向量机的基础上考虑未标记样本，即将未标记样本的约束条件和样本错误分类的损失值加入到支持向量机的目标优化函数中，得到如下分类模型[28]:
其中，C为惩罚因子，l为标记样本量，u为未标记样本量，γ表示标记样本对类别的损失值，α表示未标记样本对正类别的损失值，β表示未标记样本对负类别的损失值。该方法由Bennett在文献[28]中详细说明，并用图2形象地描述了支持向量机加入未标记样本后得到的分划超平面具有显著的优越性。
在半监督支持向量机中，通常需要引入软间隔法的松弛变量ξ≥0来软化约束条件，使分划超平面尽可能地将正类样本和负类样本分开，并利用对偶原理将最优化问题转化为凸二次规划问题。由于在求解过程中需要大量的矩阵运算，为了加快其运算速度，文献[29]提供了一种直接优化的方法，使所有变量可以并行迭代，从而减少算法的时间开销，也有文献提出快速计算的方法同样可以提高运算效率。而且在利用样本数据训练模型时，很可能会因为数据的复杂性而产生训练不充分的缺点。在文献[30]中首次将局部保持投影和线性判别分析中的类内散度矩阵融合到支持向量机中，可以在一定程度上保持样本的全局判别信息，从而避免学习不充分的缺陷。
基于支持向量机的半监督分类方法中，处理高维数据的一个很重要的方法即是核变换，为使需要求解的分划超曲面通过某种变换映射为分划超平面，利用核方法将所有样本数据从输入空间映射到核产生的特征空间，然后建立线性分划超平面，从而简化问题。且在文献[31]中，采用多核学习方法代替了单核学习，利用核组合的方法提高模型对不规则和分布不平坦数据的灵活性。由于支持向量机的分类方法广泛应用于数据分类的相关领域中，因此基于该方法的各种改进算法不断涌现，而改进模型的好坏是需要利用泛化误差来评价的，在模型的建立中通常使用交叉验证[32]提高分类模型的正确率。但交叉验证时间开销较大，仍需继续研究更有效的改进方法。
支持向量机简化了传统的分类问题，避免了复杂的统计技术，不但方法简单，而且具有很好的鲁棒性。并在文本分类[2]、生物信息、医学影像处理和安全监测等[33]方面有很好的应用。
2.6 基于流形正则化的半监督分类方法
正则化方法是由Tikhonov首先提出的，主要是解决数学领域中的不适定问题，可将其引入到机器学习的分类模型中来优化目标函数的平滑性，防止模型的过分拟合。利用传统的正则化框架求解数据的分类问题时，给定标记样本(xi,yi),i=1,2，…，l;yi∈{-1,1}，在满足Mercer定理的核函数K产生的希尔伯特空间HK中，目标分类函数是:
其中l为标记样本量，第一项是经验风险，V是损失函数，可以是平方损失(yi-f(xi))2或者是关键损失max(0,1-yif(xi));第二项是正则化项，通常取参数向量的范数形式，在这里取目标函数的L2范数，γ≥0是正则化因子，控制分类函数f在邻域空间内的复杂性。
在正则化的基础上，一种基于流形正则化的半监督分类算法框架MR[20]由Belkin等人提出，该算法基于流形假设理论，不仅能保持数据的局部流形结构，提升分类器的性能，也将未标记样本加入到目标优化函数中:
其中u为未标记样本个数，γA和γI是正则化因子，f表示由所有样本经f映射之后的类别值所组成的列向量，L为图拉普拉斯矩阵，使近邻样本经映射之后依然近邻，故第三项也即流形正则化项，控制样本几何分布的复杂性。MR算法的实质即是尽量在分类器的适用能力、决策函数的光滑性和数据的流形结构之间寻求完美的平衡。
在文献[5]中提出了一种基于后验概率和流形正则化的半监督分类方法(PPMR)。此方法不仅采用流形技术来挖掘高维空间中数据的本质，而且采用正则化罚项防止目标优化函数对数据的过分拟合。同时将后验概率加入到MR算法中，克服样本类别确定性这一缺点，通过非确定性的标记来提高分类器中边界拟合的准确性。但这样的标记需要专家知识，在大量数据中怎样利用各种经验知识来获取非确定性标记是一大难题。虽然MR算法利用流形假设理论有效地增强了学习机的分类性能，但此框架并未充分考虑全局数据的分布信息。文献[34]提出的稀疏正则化最小类散度半监督分类机解决了此问题，充分考虑数据类内分布结构信息，使模型在噪声环境中仍具有较强的判别力和鲁棒性。
流形正则化的方法通常结合图的半监督分类方法，也可结合支持向量机的半监督分类方法，并应用于病例分类、模式识别和文本分类等[33]方面。
2.7 算法小结
本文针对数据分类问题，主要分析了六种半监督分类方法，详细说明了各种方法的基本思想、研究现状和应用范围，以及这些分类算法的各自特点，并做了对比(如表1所示)。这些算法虽有不同，但相互之间也有联系，且算法之间也可以相互融合，如将自训练方法与协同训练方法结合，将图拉普拉斯矩阵与流形正则化结合等，不仅能够克服自身缺点，还能够得到更好的分类效果。但每种方法都有优缺点，针对不同的问题如何选用最合适的模型仍需继续研究。
3 研究中的困难与需要进一步研究的问题
随着信息化时代的进步，半监督分类的应用领域日益增加，对它的研究成果也都如雨后春笋，但在研究中仍存在着一些困难，模型中存在的一些问题仍需要继续进一步改进。
(1)在模型训练中，为了利用不受噪声影响的纯数据，假设复杂的数据是满足文中所讲的两种基本假设的。但实际应用中的数据可能带有大量的噪声数据，并不符合特定的分布。为描述数据的真实分布，只利用两种假设是远远不够的。那么如何研究出更加有效的假设或者是如何选取更纯的训练数据是一重要问题。
针对此，有人提出全局与局部一致性假设，使数据尽可能地满足模型的需要，该方法可取但仍有缺点。为了保持数据的原有特色，需要设计出更准确的假设(如将几种基本假设合理地相互结合)使分类模型能够使用更真实的原始数据，得出更准确的分类结果。
(2)在算法设计中，不可避免的就是参数的选择问题。在一些文献中也讲述了求最优化参数的方法，如EM算法、极大似然估计等，但这些方法是否能获得最优化的参数，还需人们进一步探讨。
(3)在利用半监督分类建模中，标记样本的数目是非常有限的，如果标记样本的类别标记是错误标记或是标记样本处于异常分布区时，分类模型将会因为标记样本的错误引导和未标记样本的近邻传播产生分类偏差。虽然在文献[5]中加入了后验概率对模型定位，减少模糊异常标记样本对分类结果的影响，但分类误差是不可避免的，而且后验概率的获得也是研究中的难题。在后续的研究中，不妨改进基本的分类算法，在算法中设定某种阈值，若错误的标记样本不满足阈值则会被自动淘汰，满足阈值的样本将继续训练分类器。但该想法暂不完备，能否实现仍需仔细探讨。
(4)对半监督分类方法的研究时间还很短暂，许多现实中的问题都还不能利用它来解决。在设计出分类模型后，主要利用一些合成数据来做实验分析，为了使半监督分类具有更好的现实意义，使它广泛应用于各种实际生活中的数据集，需要继续改善算法的有效性。若要完善算法，各个领域中真实数据集的搜取问题是首要解决的难题。
(5)对于常用的算法基本上解决的是二分类问题，但实际应用中数据的分类也有许多是多分类问题，将应用于二分类问题的模型改进为应用于多分类的模型是值得进一步研究的问题。由于在半监督分类中，支持向量机的应用范围较为广泛，且随着其理论的日趋完善，人们对它的研究也更深入。因此，将支持向量机应用于多分类问题中将会是一项重要内容。
4 结语
随着海量数据的出现与信息爆炸，怎样合理地处理数据并将数据正确地分类是机器学习中研究的热点问题。为了节约人工成本，提高分析数据的效率，人们提出了各种各样的半监督分类方法。
本文首先探讨了半监督分类的研究意义、研究现状及应用领域。而后详述了半监督分类的一些常用方法，包括基于生成模型的半监督分类方法、基于自训练的半监督分类方法、基于协同训练的半监督分类方法、基于图的半监督分类方法、基于支持向量机的半监督分类方法和基于流形正则化的半监督分类方法;针对这些基本算法的缺点，综述了解决各种问题的改进算法;同时，评价了各种算法的优缺点。但在研究中依然存在困难需要人们继续努力去解决，随着对半监督分类方法研究的持续改善，它能够解决的现实问题也越来越多。因此，对半监督分类方法的理论和应用探讨将会一直是机器学习中所要研究的重要内容。
摘要：半监督学习是人工智能研究领域中的重要课题,结合有监督学习和无监督学习的优点来提高学习器的性能。针对有监督分类和无监督分类不能充分利用已标记样本和未标记样本的问题,介绍了半监督分类方法及其基本思想、研究现状、应用领域与常用算法,分析了当前半监督分类算法研究中的主要困难,同时提出了需要进一步研究的若干问题。
关键词：半监督分类,生成模型,自训练,协同训练,图,支持向量机,流形正则化
半监督分类方法论文 篇2
近年来,随着网络技术和网络规模的迅速发展,网络入侵可能性越来越大,网络攻击行为和手段越来越多,网络安全问题日益突出,入侵检测成为网络安全领域研究的热点。目前机器学习技术已经成功应用到入侵检测系统,入侵检测算法和大多数机器学习算法一样,要依赖于有标记样本数据。标记数据获取困难,它需要专业人员花费大量时间去收集和识别。由于无标记样本容易获取,利用少量标记数据进行指导学习的半监督机器技术[1]被广泛关注。半监督支持向量机(Semi-Supervised Support Vector Machines,S3VM)是一种通用有效的半监督机器学习方法。目前已经应用到入侵检测中,它的主要思想是从学习产生的多个大边缘低密度分类决策面(见图1)中找到一个最优分类决策面[2]。虽然提高了训练和检测速度,但S3VM舍弃了相当数量的分类决策面,具有一定的风险,可能会降低模型的预测精确度,另外在基于数量有限的已标记样本,很难决定哪个分类决策面是最优(已标记样本与学习出的分类决策面非常吻合)[3,4]。
针对上述问题,提出一种优化多分类决策面S3VM入侵检测方法(MLL＿S3VM),给出了理论分析和实验结果。实验结果表明,MLL＿S3VM与其它一些S3VM算法相比有较高的分类准确率。
1 半监督支持向量机
半监督支持向量机首次相近的研究是Vapnik[5]提出的直推式支持向量机(Transductive Support Vector Machine,TSVM),Joachims等人在1999年首次编码实现,其主要思想是:利用少量已标记样本和大量的未标记样本,学习到一个通过低样本密度区域的分类器模型。
在给定一个训练集中包含n个样本,其中包括l个有标记样本 {(xi,yi)}
约束条件为 y(ωxi+b)≥1-ξi, 1≤i≤l;
(ωx*i+b)≥1-ξ*i, 1≤i≤u;
ξi≥0,ξ*i≥0。
参数C1为参数有标记样本集上的惩罚因子,C2为无标记样本在训练过程中的影响因子。ξi为有标记样本xi对应的松弛变量,ξ*j为无标记样本x*j对应的松弛变量。
S3VM为了学习出一个最优的分类器,舍弃了相当数量的分类决策面,另外在已标记样本与学习出的分类决策面非常吻合的情况下,很难决定哪个大边缘低密度分类决策面是最优的。如果随便选择其中之一作为未标记样本的最终分类器,可能会降低分类的精确度,所以需要一些先验知识来区分这些分类决策面。
2 多低密度分类决策面S3VM
为了克服传统的S3VM随机选取一个分类面会降低模型分类精确度的缺陷,提出一种优化多分类决策面S3VM入侵检测方法(MLL_S3VM),该方法结合启发式抽样搜索和聚类方法筛选出差异性较大的分类决策面。
2.1 MLL_S3VM思想分析
定义1 (分类决策面影响因子)对于已有的训练集样本学习得到的N个大边缘分类决策面,其中一个分类决策面相异与其他分类决策面的程度,称为该分类面在N个大边缘分类决策面中的影响因子。Ω({
式(2)中:I是个恒等式函数。
定义 2 (临近分类面距离因子)若存在未标记样本x*i,x*i在根据ωt和ωt′的分类决策面下得到不同的类标记,并且ωt和ωt′是距离样本x*i最近的两个分类决策面,则称d(x*i,ωt)和d(x*i,ωt′)为x*i临近分类面距离因子,其中:ω表示学习出的低密度分类决策面,d(x*i,ω)≥0(注:只有不存在满足条件的ωt和ωt′时d(x*i,ω)=0)。
用h(ω,
目标是获取大边缘低密度分类决策面,同时满足学习得到的大边缘分类决策面具有边缘和差异性最大化需求,在式(3)中加入限制条件来满足需求。结合式(2),采用式(4)来表示前T个差异性最大的大边缘低密度分类决策面。
式(4)中:ωt表示学习出的低密度分类决策面,T是多低密度分类决策面数量,Ω表示分类决策面影响因子。
对式(4)进一步变化,也是MLL_S3VM目标函数
2.2 实现步骤描述
为了实现MLL_S3VM目标函数,从实现的时间空间复杂度出发,将分两个阶段对目标函数进行实现:第一阶段先学习出多个大边缘低密度分类决策面;第二阶段从这些已经学习得到的低密度分类决策面中采用聚类方法获取差异性较大的分类决策面。在获取大边缘分类面的基础上,对未标记样本进行标记,具体过程如下:
步骤1:利用已有的训练集样本学习出多个大边缘低密度分类决策面;
步骤2:根据公式对已经学习出的大边缘低密度分类决策面进行迭代优化,直到函数收敛时结束;
步骤3:采用启发式样本抽样的方法从训练结果集抽样出T个已经学习出的低密度分类决策面;
步骤4:运用经典聚类算法(K-means)获取T个差异性较大的分类决策面;
步骤5:对于未标记样本x*i,采用临近分类面距离因子方法对样本进行标记,若d(x*i,ω)=0,则x*i的类别信息可以根据其中任一分类决策面确定。d(x*i,ωt)<d(x*i,ωt′),那么x*i的类标记依据ωt′分类决策面决定,如果d(x*i,ωt)>d(x*i,ωt′),那么x*i的类标记依据ωt分类决策面决定,如果d(x*i,ωt)=d(x*i,ωt′),那么x*i的类标记采用抽签法决定。
3 实验与分析
3.1 数据预处理与参数设置
采用KDDCUP99[6]中的kddcup.data_10_percent.gz数据集作为训练集和测试集的选取来源,该数据集是在入侵检测领域广泛采用的实验数据集,该数据集中每个连接共有41种定性和定量的特征属性 ,其中有 8个属性是离散型的变量 ,其余是连续型的数字变量。将特征属性进行归一化处理,使得每类特征数据的取值范围在区间[0,1]中,这样处理一方面避免取值范围大的属性支配取值范围小的属性,另一方面也可以提高机器的处理能力。S3VM核函数采用高斯径向基核函数(Radial Base Function,RBF),聚类簇数目取。在标记样本占整个训练集中3%,5%,10%,15%的基础上,对传统半监督支持向量机算法(TS3VM)和改进后的MLL_S3VM算法进行了对比,每个实验结果是经过30次实验结果平均得到。
3.2 实验结果分析
通过检测率和误报率评价改进的入侵检测算法的性能,其中:检测率 = 检测到的异常数据个数/样本中的异常数据个数,误报率=误报为异常的正常数据个数/样本中正常数据个数。
从表1中实验结果数据可以看出,在标记样本占3%,5%,10%,15%的数据集样本中,优化改进后的MLL_S3VM算法明显优于传统的S3VM算法。传统S3VM选取一个分类决策面舍弃了相当数量且可能有用的分类决策面,MLL_S3VM综合考虑差异性较大的分类决策面,在一定程度上克服的S3VM缺陷,在检测率上有了一定的升高,误报率方面有了一定的降低。
4 结论
根据传统的S3VM方法存在的不足,提出一种基于多分类面的半监督支持向量机优化方法,一定程度上克服传统的S3VM方法训练不充分的缺陷,但是该方法在一定程度上给入侵检测增加了算法的时间、空间复杂度,应用到实时入侵检测系统上有一定的局限性,因此如何克服算法上的不足,并且进一步提高分类器的性能将是以后的研究方向。
参考文献
[1] Bennett K,Demiriz A. Semi-supervised support vector machines. Cambridge, MA: MIT Press, 1999:368—374
[2] Chapelle O,Zien A.Semi-supervised learning by low density separa-tion.In:AISTATS,2005:57—64
[3] Chapelle O,Sindhwani V,Keerthi S.Optimization techniques forsemi-supervised support vector machines.Journal of Machine Learn-ing Research,2008;9(2):203—233
[4] Yu Feng Li,Zhi Hua Zhou.Towards making unlabeled data neverhurt.In:Proceedings of the 28th International Conference on Ma-chine Learning,Bellevue,WA,2011
[5] Vapnik, V, Sterin A. On structural risk minimization or overall risk in a problem of pattern recognition. Automation and Remote Control, 1977; 10(3): 1495—1503
半监督分类方法论文 篇3
机器学习在人工智能的研究中具有非常重要的地位。支持向量机是Vapnik等在统计学习理论基础上发展起来的针对小样本的机器学习方法[1]。该方法由于具有较强的泛化能力、方便对高维的数据进行操作而得到了日益广泛的研究和应用。传统的有监督的分类方法,虽然能够有效地解决各种实际问题,但是需要事先对大量样本进行标记以获取足够的训练样本,代价高,效率低。因此,根据实际需要研究人员提出了一些半监督支持向量机分类方法。Bennett, K.,& Demiriz,A.于1999年提出了半监督支持向量机(S3VM[2]), 它基于聚类假设,试图通过探索未标记数据来规范调整决策边界, 从而提高运算的准确度。21世纪以来,Melacci,S.,&Belkin,M提出了拉普拉斯(Laplacian)支持向量机[3],主要是通过图的拉普拉斯矩阵来探索数据的流形结构,通过对无标记的数据找到合适的类别, 以使它们与已标记的数据和潜在的图的结构的不一致性最小化,从而提高了预测精确度。
本文将拉普拉斯(Laplacian)正则项引入到不平行超平面分类机[4]之中,建立了拉普拉斯正则项的半监督不平行超平面分类机。同时,在数值试验中,从精度和速度上,和经典的拉普拉斯正则项支持向量机和拉普拉斯正则项双支持向量机做了对比,表明了提出的算法的优良性。
2背景知识
半监督分类问题的数学描述如下:
给定有标签数据集
和无标签的数据集
所有负类样本点的输入构成的矩阵为
并记所有正类点的输入和无标签的数据集构成的矩阵记为M,即M[XT,UT]T,所有负类点的输入和无标签的数据集构成的矩阵记为N , 即N[XT,UT]T,所有数据集构成的矩阵记为X [M, N].
2.1拉普拉斯正则项
1998年,Miller D J和Uyar H.从数据分布的角度对半监督学习进行了直观的分析,认为通过使用大量未标记样本可以提高分类精度。在此基础上,2006年Belkinetal提出了样本点的内在联系[5], 具体的表达式为
其中f(x) 表示决策函数, L D W,这里W中的元素Wij代表数据点之间的相似度,采用k近邻方法来定义Wij。
2.2不平行超平面支持向量机
2014年,不平行超平面支持向量机[4]被提出,它通过寻找两个非平行的超平面构造最终的决策函数,对于新输入的点,离那个超平面距离近就属于那一类。
对于给定的数据集(1),在线性模型中,为了得到如下两个分类函数
不平行超平面支持向量机的原始问题为
构造如下拉格朗日函数,根据KKT条件可求解出原始问题的对偶问题为
其中
通过求解对偶问题,可构造出决策函数
3基于拉普拉斯正则项的半监督不平行超平面分类机
在本节中,针对半监督分类问题,我们提出了一个新的分类算法,称它为基于拉普拉斯正则项的半监督不平行超平面分类机。我们首先分别给出基于拉普拉斯正则项的半监督不平行超平面分类机的线性情形和非线性情形。
3.1线性情形
对于给定的数据集(1)和(2),在线性模型中,为了得到如下两个分类函数
构造如下的原始问题为
为了求解问题(12),我们考虑如下的拉格朗日函数
显然,由(10)-(13)推出
将(19)-(22)代入拉格朗日函数,结合(17)-(18)整理得到原问题的对偶问题为
根据原始问题的解和对偶问题的解关系,即式(19)-(22),可构造出决策函数
3.2非线性情形
构造如下的原始问题为
为了求解问题(25),我们考虑如下的拉格朗日函数
根据KKT条件有
显然,由(26)-(29)推出
将(32)-(35)带入拉格朗日函数,结合(30)-(31)整理得到原始问题的对偶问题为
根据原始问题的解和对偶问题的解的关系,即式(32)-(35),可构造出决策函数
4数值实验
图1表示Lap-SVM,Lap-TSVM和Lap-NPSVM的分类比较, 小正方形代表有标签正类样本点,大正方形代表无标签正类样本点,小圆代表有标签负类样本点,大圆代表无标签负类样本点。
图1的数据集来自噪音数据集[8,9],属于交叉型数据,Lap-SVM, Lap-TSVM和Lap-NHSVM做对比,从图1可以看出Lap-NHSVM具有明显比较好的分类精度,能够更好的利用未标签的数据,从而使分类效果更好。
在下面表1和表2的实验中,我们利用UCI数据中的六个数据来做数值实验,包括Diabetes,German,Ionosphere,Sonar,Australian, Heart。在机器学习中,这些数据经常会被用来检测算法的优劣,在实验中,取每个数据集的40%作为有标签的样本集,30%作为无标签的样本集,进行十次试验,取十次实验结果的平均值加减方差构成。 对于CPU时间,同样取十次实验结果的平均值。如图所示,黑体表示最高精确度对应的数据,表1表示线性情形时,Lap-SVM,Lap- TSVM和Lap-NHSVM的比较,表2表示非线性情形时,Lap-SVM, Lap-TSVM和Lap-NHSVM的比较,从实验结果可以明显的看出, 对于大部分数据集,拉普拉斯不平行超平面分类机具有更高的分类精确度,例如,对于Lonosphere数据集,Lap-NHSVM对应的精确度为88.32%,而Lap-SVM,Lap-TSVM对应的精确度远小于它,另一方面,从下表可以看出,Lap-NHSVM对应的CPU时间要比Lap- SVM的快速,却比Lap-SVM和Lap-TSVM的精确度高。
5结语
在本文中,提出了基于拉普拉斯正则项的半监督不平行超平面分类机,从数值实验可以看出,提出的分类方法具有较高的分类精确度,尤其对于某些数据集,例如交叉数据集,我们的算法可以得到更精准的结果,因此我们可以看出,本文提出的半监督不平行超平面分类方法值得肯定。
参考文献
[1]V.Vapnik.The Nature of Statistical Learning Theory.SpringerVerlag,2nd edition,1998.
[2]Bennett,K.,&Demiriz,A.(1999).Semi-supervised support vector machines.In Advances in Neural Information Processing Systems 11,368-374.
[3]Melacci,S.,&Belkin,M(2011).Laplacian support vector machines trained in the primal.Journal of Machine Learning Research,12.
[4]Shao Y H,Chen W J,Deng N Y.Nonparallel hyperplane support vector machine for binary classification problems[J].Information Sciences263(2014)22-35.
[5]Belkin et al.,(2006).Manifold regularization;a geometric framework for learning from labeled and unlabeled examples.Journal of Machine Research,7,2399-2434.
[6]O.L.Mangasarian,E.W.Wild,Multisurface proximal support vector classification via generalize deigenvalues,IEEE Transactions on Pattern Analysisand Machine Intelligence28(1)(2006)69-74.
[7]邓乃扬,田英杰.数据挖掘中的新方法-支持向量机[M].2版.北京:科学出版社,2009:356-357.
[8]O.L.Mangasarian,E.W.Wild,Multisurface proximal support vector classification via generalize deigenvalues,IEEE Transactions on Pattern Analysisand Machine Intelligence 28(1)(2006)69-74.
半监督分类方法论文 篇4
监督学习利用一组足够多的已标记的样本来发现属性和类别之间的联系, 使其可以达到理想的关联模式, 并用这些模式来观测未知数据的类别属性, 但是大量的有标记样本是非常难获得的。无监督学习事先没有明确的关联模式, 而是通过某种算法发现数据中存在的内在结构, 典型的算法有聚类。半监督[1]学习是一种新的学习问题, 结合了监督学习和无监督学习优点, 适合已标记样本小, 具有大量未标记样本的分类问题, 它讨论如何将庞大的未标记样本和少量的已标记样本结合起来从而提高学习器的泛化能力[2]。
现有的分类算法主要有支持向量机[3]、决策树[4]、贝叶斯[5]、最近邻[6]、神经网络[7]和基于关联规则[8]的分类等。支持向量机是Vapnik提出的一种新学习方法, 根据结构风险最小化原则, 以最大化分类间隔构造最优分类超平面, 非常好的解决了数据中存在的非线性、高维性、局部极小点等问题。
分类后样本可能含有噪声数据, 把这些数据加入有标识样本重新训练, 一是会加大训练时间, 二是噪声样本会影响分类精度, 在半监督分类模式下, 循环加入有噪声样本会加剧降低预测准确率。
本文采用半监督支持向量机算法来训练分类器, 在已标记样本少的情况下, 用大量的未标记样本提高分类器性能, 并对分类后的数据提出了加权去噪的方法, 建立了最优分类器。
1 支持向量机的构建
支持向量机通过确定最优分类面实现数据分类, 可分别对线性和非线性数据进行分类, 对于非线性的数据, 需要通过核函数把数据映射到高维空间, 让数据在高维空间线性可分, 从而实现对数据进行类别预测, 实现分类。
以两个类别的训练样本数据为例, 设给定的样本数据集D为 (X1, Y1) , (X2, Y2) , ⋯, (X|D|, Y|D|) , 其中Xi是训练元组, yi是相关联的类标号, yi∈{+1, -1}, i=1, 2, ..., n代表样本类别, K (∙) 为核函数。
构造最小化代价函数为:
其中C是惩罚函数, 控制错分样本的惩罚程度, ζi是松弛变量, 表示训练样本的错分程度。分离超平面为:f (x) = (w∙x) +b, 其中w是权重向量b是阈值。运用最小化对偶技术, 引入拉格朗日函数为:
其中αi和βi是拉格朗日算子。对偶化后取最优解α*时满足以下条件为:
则αi*>0的样本是支持向量。判别函数为:
内积核函数k (x, xi) 为:
2 噪声过滤机制
2.1 噪声数据的影响
由于受到噪声的干扰, 影响支持向量机的性能。为获得高精度的分类结果, 必须减少噪声干扰, 提高训练样本正确率, 消除噪声因素对分类结果的影响。在此基础上, 提出了对预测好的样本去噪的方法, 减少数据中存在的噪声样本数量, 避免对重新生成的分类器有较大影响, 提高分类准确率。
在所有算法中, 新产生的已标识数据直接加入到已标识样本集合中, 会加入正确的数据, 同样也会给训练集带来噪声数据, 随着循环次数不断增加, 积累的噪声数据会影响更新后的分类器的性能[9]。在已标识样本少的情况下, 分类器不是最优的, 机器自动分类时, 可能会错分未标记样本, 把分类后的样本直接加入到训练集重新训练, 会使分类器精度下降。引入噪声过滤机制, 提高分类精度。
2.2 基于信息熵权值的确定
信息熵用来度量不确定事物中提供的信息量的多少, 数据越有序, 信息熵越低, 反之, 如果数据越混乱, 信息熵则越高。其基本定义如下:
设X是一个离散的随机变量, 其定义空间为一个字符集E。pi (x) =p (X=x) , x∈E, 表示相应的概率分布函数, 即各信息源提供信息的概率, 计算公式如下:
根据信息论知, 离散随机变量的熵为:
则信息熵加权系数wi为:
2.3 加权的欧氏距离
欧氏距离是一个经常采用的距离公式, 用来计算n维空间中两个点之间的真实距离。加权的欧氏距离的基本思想是, 先计算出数据集中每个属性的信息熵, 以信息熵为权值, 然后用加权的欧氏距离公式计算样本间的相似度:
合理地运用加权欧氏距离, 可以反映出各变量在数据中的不同作用, 对结果能起到较好的效果。
2.4 基于加权欧氏距离的去噪方法
每个类为一个簇, 分类后结果簇内的相似度高, 而簇间的相似度低。基本思想是:选择k个对象为初始点, 每个初始对象代表一个簇的中心或平均值, 对于剩余的对象, 用加权欧氏距离计算每个对象到簇中心的距离, 最小的属于该簇则分类正确, 如果距离大于到其他簇中心的距离, 则该对象不属于该簇即分类错误, 是噪声数据。
传统的方法中, 没有考虑对象中每个属性所体现的不同作用, 而是将它们等同看待, 用欧氏距离只能计算数据间相隔的远近, 不能准确地表示簇间相似度, 因为相似不仅依赖样本间的相近程度, 而且还依赖于样本间的内在性质[10]。
在簇确定情况下, 使用加权的欧氏距离去噪算法检测样本数据中分类错误的数据。
算法1加权欧氏距离的去噪算法。
1) 随机取数值k1, k2, ⋯, kn为各类别的中心点, i∈ (1, 2, ⋯, n) , 根据平均值确定中心点位置
2) 用公式 (8) 中信息熵加权的欧氏距离计算每个样本D (xi, yi, ⋯zi) 到中心点ki的距离di。
定理:若样本A (xA1, yA2, ⋯, zAn) 分类正确, 则:
即A到该类别中心点的距离最小。
3) 判断
If dA>di, A为噪声样本
Then删掉噪声点A
3 实验结果
实验所用数据从UCI标准数据集中选取, 选用四个数据集来进行实验, 为了避免不平衡数据对分类性能的影响, 在每个数据集的类别中选取两类样本数据, 样本数目平衡且比较多, 对构造的支持向量机分类器训练和测试。所用实验详细数据集如表1所示:
分别选取每个数据集中大致选取80%的样本作为训练集, 剩余20%数据作为测试集。用支持向量机构建分类器, 做测试时, 把每个数据集分为N等份。在80%的训练集中首先选取20%作为初始已标识样本用来训练分类器, 剩余60%数据分为6等分。把类标号去掉, 作为训练时的未标识样本。数据集Abalone有1323个数据, 选取324个数据作为初始训练集, 把其中800个数据分为4分作为训练分类器时所用数据, 留取200个数据作为测试集。在数据集bank有1042个数据, 选取242个作为已标识样本训练分类器, 在训练过程中, 每次对100个数据进行分类, 对分类后的数据进行加权去噪后加入训练集, 直到未标识样本分类完成。对20%的数据测试后加入人工反馈的方法, 把分类错误的样本数据人为的加入正确的类别。表2给出了支持向量法算法在加权去噪前后的比较。
实验结果表明用加权去噪的半监督支持向量机训练方法提高了分类精度, 优于只使用支持向量机算法, 初始已标记样本少的情况下, 在训练分类器过程中用去噪的半监督思想多次加入未标识样本来扩大训练集, 优化分类器性能, 提高分类精度。
4 结论
该文提出一种信息熵加权去噪的方法, 删除分类有误的数据, 现实数据中, 存在大量的未标识数据, 而已标识数据较少的情况下, 不利于对数据进行分类, 该文用半监督思想, 先用已标识样本训练分类器, 然后用大量的未标识样本来提高分类器性能, 由于分类后的样本中可能存在噪声数据, 用基于加权欧氏距离算法对样本进行去噪, 选取置信度较高的样本加入训练集重新训练。在四个UCI数据集上的实验结果表明, 该文提出的方法效果明显, 具有良好的预测精度。
参考文献
[1]David R Anderson, Dennis J Sweeney.Statistics for business and economics[M].Beijing:China Machine press, 2010:327-330.
[2]门昌骞, 王文剑.一种基于多学习器标记的半监督SVM学习方法[J].广西师范大学学报, 2008, 26 (1) .
[3]Zhang Xuewen, Li Yangjun.Self-adjusted particle swarm optimization algorithm based economic load dispatch of power system[J].Pow er System Technology, 2006, 30 (18) :8-13.
[4]Bissantz N, Hagedorn J.Data mining[J].Business and Information Systems Engineering, 2009 (1) :118-122.
[5]Jing Y, Pavlovic V, Rehg J.Boosted Bayesian network classifiers[J].Machine Learning, 2008, 73 (1) :155-184.
[6]陈黎飞, 郭躬德.最近邻分类的多代表点学习算法[J].模式识别与人工智能, 2011, 24 (6) .
[7]Janssens D, Wets G, Brijs T, et al.Improving the performance of a multi-agent rule-based model for activity pattern decisions using Bayesian networks[J].Journal of the Transportation Research Board, 2004, 1894 (1) :75-83.
[8]张扬, 周子勇.基于关联规则的面向对象高分辨率影像分类[J].遥感技术与应用, 2012, 27 (3) .
[9]孔志周, 蔡自兴.基于统计证据的半监督多分类器整合方法[J].控制与决策, 2011, 26 (11) .
半监督分类方法论文 篇5
遥感图像具有较高的光谱分辨率,在航天、地质勘探、农业等领域获得了越来越多的应用,遥感图像分类在遥感图像应用中具有重要的作用。但对遥感图像分类也面临以下难题:其一是如果采用传统的非监督方法对遥感图像直接分类,因遥感图像的复杂性和特殊性,很难获得比较满意的结果;其二采用监督方法,需要运用大量的训练样本才能获取较好的分类结果,而标记样本的获取代价高昂,也容易出现分类器过拟合与训练样本的问题。
半监督学习[1]可以很好地解决上述问题,首先大量的廉价的无标记样本也包含样本特征信息,其次遥感图像中标记样本的获取十分昂贵。半监督学习可以利用少量的已标记样本,结合大量的无标记样本建立分类器完成学习任务。基于图的半监督图像分类在近年来图像研究领域成为了一个研究热点,此方法结合图理论,能够充分利用图像中的无标记样本信息,分类性能较好,且目标函数优化简单,因此更加高效,目前也有许多基于图的半监督分类方法[2,3,4,5,6]。
基于图的半监督图像分类方法是建立在图理论的基础上,但算法计算速度依赖于所构建图的规模大小,当数据规模过大时,如果还是每一个图节点代表一个样本点,图规模就会很庞大,计算的时间复杂度会很高,例如线性近邻传递算法(Linear Neighborhood Propagation)、局部与全局一致性算法(Local and Global Consistency),其计算复杂度为O(n3),n为样本个数。为了降低算法的复杂度,Blum和Chawla提出了图的最小割(Mincut)算法,并将其时间复杂度降低到了O(cn2),这里c为类别数。但最小割算法可能存在多个解,得到不同的分类结果。
2010年Liu等提出基于锚点建图的半监督分类方法[7](Anchor Graph Regularization,AGR)。首先采用K-means算法对数据聚类,将聚类中心作为锚点得到锚点集,其次利用锚点与已标记样本建图,缩小了图规模,时间复杂度降为O(m2n),m≪n,n为样本总数,m为聚类个数。但K-means聚类算法消耗时间过长,且遥感图像混合像元问题使部分像元很难进行非此即彼的划分,部分区域地物类别边界是过渡性的,没有明显边界划分,因此K-means不适宜对遥感图像聚类。针对上述问题,本文采用mean shift聚类算法代替K-means算法对遥感图像聚类,缩短了聚类时间,mean shift算法对噪声也有一定的鲁棒性,可以解决噪声点带来的干扰,提高聚类的有效性。其次在每个聚类中随机选取一个点作为锚点,得到锚点集,并与标记样本集建立图。该方法不仅降低了算法复杂度,可以处理大规模图像分类问题,同时在遥感图像分类中具有较好的分类结果。
1 AGR图像分类方法
设样本数据集为,共有n个样本,l个是已标记样本,剩余的为未标记样本。为了解决大规模数据问题,将标记预测函数定义为一个对锚点的加权平均函数,当得到锚点的类别信息后,就可以通过映射关系得到与锚点密切相关的无标记样本的类别信息。将锚点加权平均函数表示为:,其中uk代表锚点,标记预测函数为:
在这里定义两个向量f=[f(x1),f(x2),···,f(xn)]T和a=[f(u1),f(u2),···,f(um)]T;a为锚点的软标签预测矩阵;m为锚点个数。式(1)可以写成:
其中Z是一个权值矩阵,表示了锚点与所有样本点的线性关系:
这里使用的是高斯核函数。<i>⊂[1:m]是一个保存xi的s个最近邻锚点的索引,为了提高计算效率,规定每一个样本xi只与s个Zik中值最大的锚点具有连接关系,其他连接均为0。
由Z矩阵可以得到邻接矩阵:
式中,Λ∈Rm×m是一个对角矩阵:
由s的取值可以知道,所有的样本点都只与部分近邻锚点存在连接关系,所以矩阵W是稀疏的。Zhu提出稀疏图对算法的性能的影响优于全连通图[1]。因为全连通图中,每个样本的邻接信息中含有大量重复的、干扰的信息,而稀疏图在连接不同样本时含有较少的错误信息,对算法结果有正确的指导。由式(4)定义的邻接矩阵所构造的图就是Anchor Graph。最后Anchor Graph的图拉普拉斯矩阵为:
式中:D为对角线矩阵,
2 本文方法流程
假设已标记样本xi(i=1,2,···,l),其标记信息为yi∈{1,2,···,c},c为类别个数。用Y=[y1,y2,···,yc]∈Rl×c表示已标记样本的标记信息,如果yi=j,Yij=1,否则Yij=0。用mean shift聚类算法对遥感图像进行聚类,得到各个类别的聚类中心,把每个聚类中心作为一个锚点,得到AGR方法中的锚点集合。此时就需要求得锚点的标签预测矩阵A=[a1,a2,···,ac]∈Rm×c。选择被广泛应用的图拉普拉斯正则化项,可得到半监督学习框架:
式中:Zl∈Rl×m是Z矩阵的子矩阵,只包含标记样本;是Frobenius范数;取γ>0,为正则化参数。那么缩小后的拉普拉斯矩阵为:
缩小后的拉普拉斯矩阵存储空间更小,易于计算,空间复杂度为O(m2),时间复杂度为O(m3+m2n)。这时,目标函数Γ(A)进一步简化为:
最后,就可以得到全局最优解:
得到了锚点的标记信息,那么未标记样本的标记信息就可以通过下式得到:
式中:Zi∈Rl×m表示Z矩阵的第i行。λj=ITZaj表示归一化因子,作用是平衡倾斜的类分布。
具体的算法步骤如下:
输入:已标记样本xi(i=1,2,⋯,l),标记信息
输出:图像分类结果
(1)用mean shift算法对遥感图像进行聚类,得到m个类,从每一个聚类中选取一个点作为锚点;
(2)选择合适的γ;近邻锚点个数s取3;
(3)计算Z矩阵,根据式(4)计算邻接矩阵W;
(4)根据式(6)计算图拉普拉斯矩阵L;
(5)根据式(10)计算锚点标签预测矩阵A*;
(6)根据式(11)计算未标记样本的标记。
3 算法复杂度分析
基于图的半监督分类方法,大多数方法中是每个样本作为一个图节点建立图,所以计算复杂度为O(n3),其中n是样本个数。本文方法中,mean shift的计算复杂度是O(dn2t),其中d是数据的空间维度,t是迭代次数;基于锚点的算法的计算复杂度[7]是O(m2n),所以本文方法的计算复杂度是O(dn2t)+O(m2n),且m是聚类后得到的聚类中心个数,m≪n,所以本文方法的计算复杂度是远小于原始基于图的半监督分类方法的计算复杂度O(n3)。
4 实验结果与分析
本文在Matlab R2012a下计算机内存为2 GB,CPU为Intel Core i3,频率为2.53 GHz的机器上运行实验。实验采用的遥感图像是IKONOS卫星图像,IKONOS卫星图像包含一个全色波段,分辨率为1 m,四个多光谱波段,分辨率为4 m。图像大小为400×400,实验中对四个多光谱波段构成的遥感图像进行分类,3个RGB多光谱波段构成的真彩色图像如图1所示。根据实验区的特点,具体样本分类类别如表1所示。
图1中最左侧两片颜色灰白的区域是水泥建筑场地,右上侧灌木林中间的一个蓝色区域是一个房屋,这两片区域在本文实验中都归为“公路居民区”类别。因此本次实验样本类别个数为:“农田”像元点数32 433,“荒裸地”像元点数41 825,“植被”像元点数67 978,“公路居民区”像元点数17 764。
原文方法采用K-means聚类算法,不适应对遥感图像聚类,所以本文对遥感图像的分类结果并未与原文方法进行对比,而与遥感图像处理平台ENVI自带的监督支持向量机(SVM)方法进行对比。
本文实验SVM方法参数取值:核类型(Kernel Type)选择Polynomial,核心多项式的次数取4,Classification Probability Threshold取0,其他参数采用默认值。
本文实验中标记样本均为人工选取,实验分四次,四次实验中每类标记样本个数分别为5,20,50,100,每一次实验中所有实验方法均采用相同的标记样本,且每次实验都在上次已有标记样本的基础上添加新的标记样本。本文对实验结果的评价采用了Kappa系数和像元分类正确率(Pixel Classification Rate,PCR):
图2和图3分别为每类标记样本为50和100时,本文方法和监督SVM方法的实验结果。遥感图像中样本分为四类,红色代表“荒裸地”的样本点,绿色代表“植被”的样本点,蓝色代表“农田”的样本点,黄色代表“公路居民区”的样本点。对比图2和图3,可以发现,本文方法优于监督SVM方法,图4中区域标号图像为1的区域是农田和没有农作物荒裸地区域,没有灌木植被,本文方法明确地分为农田和荒裸地两类,而SVM方法中将一部分样本错分为植被;在标号为2的区域与右上角的空白区域一样均为裸地,本文方法分类效果很好,而SVM方法分类效果显然较差,部分样本错分为农田类别;标号为3的区域中,有一排灌木植被在农田中间,即右侧的很少一部分还属于农田,可以看到还有农作物存在,SVM方法中将此少部分农田错分为裸地,本文方法大部分样本分类正确;在标号4的区域,可以看到是农田和裸地的分界处,而可以明显看到此处属于农田,只不过左侧部分不存在农作物,所以归为裸地类别,在SVM方法分类结果中许多样本点被错分为植被,而本文方法只有极少量样本分错,这是因为半监督学习的流形假设,处于很小局部区域内的样本可能具有相似的标记,此处的样本明显与邻近的农田相似性更大。
对遥感图像的分类精度的评价指标是以分类结果的混淆矩阵为基础,总体分类精度和Kappa系数都要通过混淆矩阵计算得到,而为了更直观地评价两种方法的分类效果和优缺点,本文列出了每类标记样本数为100的分类结果的混淆矩阵:两种方法在每类标记样本为100时的分类结果见表2和表3。
混淆矩阵中每行的总和为每一类样本的真实样本数,每一列的总和为分类结果中每一类的总样本数,括号内的值为混淆矩阵对角线的和,即分类正确的样本总数。漏分误差即每类真实样本中没有被正确识别出来的样本比例;错分误差为分类结果中其他类别样本被错分为此类的样本占总和的比例。
通过混淆矩阵的数字可以直观地看到,本文方法的每一类样本的错分误差都小于SVM方法的错分误差;本文方法对“植被”类别的分类正确率不如SVM方法的分类结果,但本文方法对细节处的分类效果更优于SVM方法,例如在图4中右侧的灌木林,本文方法的分类结果中,琐碎的极少量的裸地都被分出来;“荒裸地”和“农田”类别的样本分类正确率都明显优于SVM方法;而“公路居民”类别正确率低于SVM方法,由混淆矩阵可以看到是错分为“荒裸地”的样本较多,这是因为图4中最左侧的居民区建筑因为曝光太强,错分为“荒裸地”;“公路居民区”类别和“农田”类别样本差别明显,本文方法把“公路居民区”错分为“农田”的样本数为零,而SVM方法的错分数是9,本文方法对类别“公路居民区”和“农田”之间的区分更优;本文方法总体精度和Kappa系数也明显高于监督SVM的。具体的分类结果统计如表4所示。
从表4可以看出,本文方法分类结果明显优于监督SVM方法,而监督SVM方法是ENVI软件的监督分类方法中效果最优的方法[8],且监督SVM方法在小样本时具有良好的分类效果。但半监督的学习方法,结合无标记样本,优于监督学习方法,提高了分类性能。如标记样本数较少,为5和20时,无标记样本作用明显,分类精度和Kappa系数提高较大。通过观察图像和实验发现,本此实验的遥感图像中样本比较复杂,地物交错比较严重,边界过度不明显,不同于城市居民区边界清晰,这就给分类增加了难度,这也是分类精度不是很高的原因之一。实验结果验证了本文方法在遥感图像分类中的有效性,相比监督SVM方法获得了更好的分类效果。
本文方法在图像聚类选取锚点时采用mean shift聚类算法,聚类样本数160 000,平均用时9.4 s。原文[9]方法采用K-means聚类算法选取锚点,文中给出了两次实验结果中的聚类时间,7 291个样本聚类时间是7.65 s;630000个样本聚类时间是195.16 s。因此mean shift聚类算法相比K-means算法缩短了聚类时间。
5 结语
基于图的半监督图像分类方法通常因为数据规模大而导致内存空间不足和分类时间过长,而遥感图像通常规模较大且地物复杂、信息量大,所以影响了其在遥感图像分类中的应用。本文首先采用mean shift算法对遥感图像聚类得到锚点集,利用锚点集和标记样本集建图,缩小了图规模,降低了计算复杂度,其次通过分类方法得到锚点的类别信息,最后映射还原到整个样本集,得到遥感图像分类结果。AGR方法解决了大规模图像分类,本文采用mean shift算法缩短了锚点选取时间。实验结果表明,本文方法在遥感图像分类中获得了较好的分类结果,验证了其对遥感图像分类的有效性。
参考文献
[1]HUANG G,SONG S,GUPTA J,et al.A second order cone programming approach for semi-supervised learning[J].Pattern recognition,2013,46(12):3548-3558.
[2]XIE W,LU Z,PENG Y,et al.Graph-based multimodal semisupervised image classification[J].Neuro computing,2014,138:167-179.
[3]BLUM A,CHAWLA S.Learning from labeled and unlabeled data using graph mincuts[C]//Proceedings of 2001 International Conference on Machine Learning.San Francisco:ACM,2001:19-26.
[4]WANG F,ZHANG C.Label propagation through linear neighborhoods[J].IEEE transactions on knowledge and data engineering,2008,20(1):55-67.
[5]ZHOU D,BOUSQUET O,LAL T N,et al.Learning with local and global consistency[J].Advances in neural information processing systems,2004,16(4):321-328.
[6]ZHU X J,GHAHARMANI Z,LAFFERTY J.Semi-supervised learning using Gaussian fields and harmonic functions[C]//Proceedings of 20th International Conference on Machine Learning.Menlo Park:AAAI,2003:912-919.
[7]LIU W,HE J,CHANG S F.Large graph construction for scalable semi-supervised learning[C]//Proceedings of the 27th International Conference on Machine Learning.Haifa:ACM,2010:679-686.
[8]闫琰,董秀兰,李燕.基于ENVI的遥感图像监督分类方法比较研究[J].北京测绘,2011(3):14-16.
[9]YU G,ZHANG G,DOMENICONI C,et al.Semi-supervised classification based on random subspace dimensionality reduction[J].Pattern recognition,2012,45(3):1119-1135.
[10]CHENG Y.Mean shift,mode seeking,and clustering[J].IEEE transactions on pattern analysis and machine intelligence,1995,17(8):790-799.
[11]WANG Y,CHEN S,ZHOU Z H.New semi-supervised classification method based on modified cluster assumption[J].IEEE transactions on neural networks and learning systems,2012,23(5):689-702.
半监督分类方法论文 篇6
随着卫星遥感技术的成熟, 遥感影像的应用也更加丰富, 其面向对象也从政府、专业客户转向大众。在遥感技术的研究中, 对资源分布、自然灾害、区域环境等的监测和分析依附于遥感图像分类, 而遥感图像分类是进行影像信息提取的有效手段。遥感专题信息的提取方法随着遥感技术的发展不断地改进, 从目视解译、自动分类、光谱特征的信息提取到光谱与空间特征的专题信息提取。遥感技术的常用的遥感图像分类的方法主要有监督分类和非监督分类, 本文将对二者的区别和联系进行分析研究。
2 遥感图像分类原理
遥感图像分类是指在特征空间中, 计算机对遥感图像中各类地物的光谱信息和空间信息进行统计、分析、对比和归纳, 选择相应的特征作为判据标准, 并将特征空间划分为若干互不重叠的子空间, 根据各地物像元的灰度值, 将其划分至各个子空间中, 以此来实现图像目标识别的工作。
3 监督分类
监督分类 (Supervised Classification) , 又称训练场地法, 思想是:首先从需要研究的区域选取有代表性的训练场地作为样本, 根据已知的样本求解特征参数, 确定判别函数和相应的判别准则, 依此来计算未知类别的样本观测值的函数值, 再按照判别准则进行所属类别的判别。
监督分类的主要步骤包括:首先, 选择训练样本区, 其中包括确定类别数, 选择各类有代表的样本, 并分析样本区的质量;其次, 选择合适的分类算法;最后, 对分类结果的精度评估。根据判别函数和判别规则的不同, 监督分类的方法有:最大似然法、最小距离分类法、平行六 (多) 面体法。
3.1 最大似然法。每一类地物数据在特征空间中都会构成特定的点群, 其一维数据或多维数据都会构成正态分布, 每种正态分布模型都有其分布特征, 利用每一类的训练区, 求出相应的均值、方差等特征参数, 并求出总体的概率密度函数, 以此为基础, 求出每个像元对于各类别的归属概率, 并将该像元归属到概率最大的类别中, 这类根据概率判别函数和贝叶斯判别规则来进行的分类称为最大似然法。此分类法的优点是:考虑特征空间中类别的形状、大小和定位, 精度高。缺点是数据计算量大, 计算时间长。
3.2 最小距离法。最小距离法的基本思想是:对遥感图像中每一类别选一个具有代表意义的统计特征量, 设法计算未知矢量x到有关类别集群之间的距离, 哪类距离它最近, 其就属于哪类。距离判别函数偏重于几何位置, 其最小距离判别有马氏距离、欧式距离、绝对值距离。此分类法的优点是原理简单, 计算速度快。缺点是精度较低。
3.3 平行六 (多) 面体法。平行六 (多) 面法又叫多级切割法, 在三维 (或更多维) 特征空间中, 在训练样区的数据中找出每个类别在特征空间的位置和形状, 以一个包括该群的“盒子”作为其判别函数, 若未知矢量x落入某盒子, 则x分为此类, 否则被拒绝, 再与其它盒子比较。没有落在“盒子”任何一类中的区域被称为无类别。平行六 (多) 面体法计算简单, 与其它监督分类相比, 速度快。
3.4 监督分类的特点。监督分类的优点: (1) 可充分利用分类地区的先验知识, 有目的选择需要的分类类别。 (2) 可以控制训练样本的选择, 并通过反复检验训练样本, 提高分类精度, 避免分类中的严重错误。 (3) 分类精度高。通过检查训练样本来决定训练样本是否被精确分类。 (4) 分类速度快。避免了非监督分类对光谱集群的重新归类。缺点: (1) 人为主观因素较强。 (2) 识别有限性, 仅能识别训练样本中定义的类别, 对于 (因训练者不知或因数量太少) 未被定义的类别, 其无法识别。 (3) 获取和评估训练样本耗时耗力。
4 非监督分类
非监督分类 (unsupervised classification) , 也称为聚类分析, 是指在没有先验类别 (训练场地) 作为样本的条件下, 凭遥感影像地物的光谱特征的分布规律进行“盲目”分类。它是按照灰度值向量或波谱样式在特征空间聚集的情况下划分点群或类别, 再根据像元间的相似度进行归类。其分类结果仅能区分不同类别, 而无法确定类别相关的属性。
非监督分类的过程:首先选择若干个点作为聚类的中心, 每一个中心代表一个类别, 选择初始聚类中心。其次, 按照最小距离原则将像元进行归类, 再次计算修改聚类中心, 重复进行直到满足选代条件。最后, 输出分类结果。非监督分类的方法有:ISODATA分类和K- 均值分类法。
4.1 ISODATA分类。ISODATA分类, 可自动进行类别的“合并”和“分裂”, 它是按照某个原则选择初始聚类中心, 计算像元与初始类别中心的距离, 把该像元分配到最近的类别中, 计算修改聚类中心, 反复进行, 直到满足选代要求, 确认类别, 精度评估。
4.2 K- 均值分类。K- 均值分类法的准则是使每一聚类中, 像元到该类别中心的距离的平均和最小。其基本思想是, 通过迭代, 逐次移动各类的中心, 直至得到最好的聚类结果为止。它的优点是实现简单, 而不足是过分依赖初值, 容易收敛于局部极值。
4.3 非监督分类的特点。非监督分类的优点: (1) 不需要对分类区域广泛了解, 仅用一定的知识来解释分类出的集群组。 (2) 人为误差的机率降低。 (3) 通过其分类可形成小范围但光谱特征独特的集群, 其较监督分类更均质。 (4) 凡是覆盖量小的类别均能够被区分。非监督分类的缺点: (1) 可靠的结果需进行大量分析处理才可获取。 (2) 由于存在的“同物异谱”及“异物同谱”现象, 则集群组与类别匹配难度加大。 (3) 由于各类不同光谱受地形时间的影响, 图像间的光谱集群组无法连续, 对比难度加大。
5 监督分类和非监督分类的区别
监督与非监督根本区别在于监督分类利用训练场地来获取先验类别, 而非监督分类则无需更多的先验知识, 直接根据地物的光谱统计特性进行分类, 因此非监督分类方法简单。若两地物类型对应的光谱特征差异小, 则监督分类效果更好, 事实上, 分类效果应以实际调查结果来检验。
6 实例分析
数据源:某一研究区, 获取其Landsat TM遥感影像, 分辨率是30米。选取训练样本:建立感兴区 (ROI) , 分类结果表明:最大似然法的kappa值为0.9589, ISODATA分类器的kappa值为0.7818, 故最大似然法精度高。
7 结论
遥感影像分类方法中, 最大似然法和ISODATA法应用最广泛。实际上, 具体选择哪种分类方法取决于图像特征和应用目的, 故应综合考虑, 灵活选择分类方法, 进一步提高分类精度。
摘要：从遥感图像的分类的原理入手, 比较分析遥感图像分类的监督分类和非监督分类的具体分类方法及特点, 运用某地区的遥感影像采用不同分类方法对其精度进行了评估。
关键词：遥感,图像分类,监督分类,非监督分类
参考文献
[1]闫琰, 董香兰, 李燕.基于ENVI的遥感图像监督分类方法比较研究[J].北京测绘, 2011 (3) :14-16.
[2]杨鑫.浅谈遥感图像监督分类与非监督分类[J].四川地质学报, 2008 (3) :251-254.
[3]李爽, 丁圣彦, 许叔明.遥感影像分类方法比较研究[J], 河南大学学报, 2002 (2) :70-73.
半监督分类方法论文 篇7
作为典型的非合作性识别任务,反导目标识别难以获取足够的标定数据。因此,常规监督式分类算法在弹道目标头体分辨中往往遇到学习样本不足、所获得的分类器模型过拟合、泛化能力差的问题。半监督学习旨在利用少量的标定样本与大量的未标定样本进行分类模型训练,以期有效利用大量非合作数据提升整个分类识别系统的性能。
目前多数的半监督学习方法往往给有限的已知标定样本和大量的未标定数据进行强的分布假设。最为常见的为“聚类假设”和“流形假设”两种。其中,聚类假设假定落在同一样本分布空间的两个样本也隶属于同一类;流形假设假定使用相似基于图表方法获得的预测标签在流形上分布平稳。本文同时验证两种假设在头体分辨中的应用效果,进一步地,综合两种假设进行自适应调整验证半监督算法在弹道目标头体分辨中的应用。
2 常规半监督算法
假定g(x)为决策函数,基于SVM框架实现半监督算法,依托的优化问题如下:
2.1 TSVM
由于TSVM(Transductive SVM)基于聚类假设,因此,它所获得的分类面总是避免经过高密度区域。由于未标定样本的标签始终为+1或-1,为获取解决方案,优化问题可表示为:
2.2 Laplacian SVM
Laplacian SVM源于基于图形的分类方法,该方法假定决策函数避免穿过分布于低纬度流形的数据。为确保决策函数沿流形的平滑分布,通常启用“图谱”来衡量样本(含已标定的和未标定的),待求的优化问题表示如下:
令决策函数g隶属于由核函数k生成的希尔伯特空间H,已被证明,Laplacian SVM所涉及的流形正则化问题可通过一个基于“重组核”的经典的SVM问题解决,该“重组核”表示如下:
3 非合作弹道目标识别中的半监督分类器设计
作为典型的非合作任务,弹道导弹目标识别因其密级高、非合作性强而很难获得其特征空间的先验分布信息。针对上述问题,本节利用多核方法将目前主流假设前提进行综合,以获得适应性强、泛化能力高的半监督分类器。
本节基于多核学习框架将“流形信息”引入到TSVM(基于“聚类假设”的半监督算法)中,借助于多核学习的自学习能力,此处设计的TSVM-MKL算法所涉及的优化问题如下:
此处约定t=0时,t/0=0,否则,其值为∞。TSVM-MKL的决策函数定义为
式中,fk为由核矩阵kk决定的函数。同样地,在解决上述优化问题时,本节设置平衡因子以约束大量未知样本中的正类、负类样本的分布情况。假设未知样本中,正类样本的比例为γ,即应满足下式:
损失函数V和U均基于传统的Hinge Loss函数,其中,的一个可行性的定义可表示为:
该优化问题启用CCCP(Difference of Convex functions)算法进行求解。详细算法表述如下:
4 数据验证
本节以实测数据为例,对所提算法进行验证。弹道目标识别的任务为进行弹头群、弹体群的区分。其中,弹头群包括弹头、诱饵、末修仓、头体分离时的碎片等目标。弹头具有自旋稳定机构,角度变化比较稳定;弹体群目标包括:各子级弹体残骸、级间分离时的碎片等目标。不具有稳定机构,产生翻滚,角度变化剧烈。目标特征采用分段RCS序列的低频能量比和变异系数。特征提取前对原始RCS序列进行了野值剔除。
观测数据中,头目标有60个样本,体目标有50个样本。为检验本文所提算法的有效性,抽取其中的10个样本作为标注样本(5个弹头、5个弹体),其余样本作为测试样本。TSVM-MKL的试验设置为:Laplacian图谱的N取值为5;基本核函数均取为“gaussian”型,核参数设置为“0.25”、“0.5”、“1”三个。与之对比的是基于常规SVM算法在上述数据上进行试验,采用5折交叉验证进行参数寻优,核函数同样设置为“gaussian”型,核参数的搜索空间为logspace(-2,1,5),正则参数的搜索空间为logspace(-1,3,10),所得结果见表1。
由结果可知,SVM在如此小的标定样本下难以获得有效分类,而本文所提的TSVM-MKL依然能够获得超过80%的分类准确率。
5 总结
本文从数据挖掘角度出发,基于多核学习算法进行非合作性弹道目标的头体分辨。由于所提算法综合了多种假设前提,因此,算法适应性较强。基于实测数据的分析验证了所提算法的有效性。
参考文献
[1]X.Tian,G.Gasso,S.Canu.A multiple kernel framework for inductive semi-supervised SVM learning,Neurocomputing,2012.
【半监督分类方法论文】推荐阅读：
国家食品药品监督管理局关于纳米生物材料类医疗器械产品分类调整12-07
分类方法01-07
指标分类方法01-18
采煤方法分类06-14
综合分类方法07-13
分类方法比较08-21
测量方法的分类10-23
常用的培训方法分类10-05
检查机构认可分类方法12-02