温馨提示！由于新浪微博认证机制调整，您的新浪微博帐号绑定已过期，请重新绑定！&&|&&
LOFTER精选
网易考拉推荐
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
&图1：机器学习的流程和结构（摘自《Natural Language Processing with&Python》）一、有监督意味着需要人工标注，需要人为的给文本一个类标签。比如我有5000条商品评论，如果我要把这些评论分成积极和消极两类。那我就可以先从里面选2000条评论，然后对这2000条数据进行人工标注，把这2000条评论标为“积极”或“消极”。这“积极”和“消极”就是类标签。假设有1000条评论被标为“积极”，有1000条评论被标为“消极”。（两者数量相同对训练分类器是有用的，如果实际中数量不相同，应该减少和增加数据以使得它们数量相同）二、之后就要选择特征。特征就是分类对象所展现的部分特点，是实现分类的依据。我们经常会做出分类的行为，那我们依据些什么进行分类呢？举个例子，如果我看到一个年轻人，穿着新的正装，提着崭新的公文包，快步行走，那我就会觉得他是一个刚入职的职场新人。在这里面，“崭新”，“正装”，“公文包”，“快步行走”都是这个人所展现出的特点，也是我用来判断这个人属于哪一类的依据。这些特点和依据就是特征。可能有些特征对我判断更有用，有些对我判断没什么用，有些可能会让我判断错误，但这些都是我分类的依据。我们没办法发现一个人的所有特点，所以我们没办法客观的选择所有特点，我们只能主观的选择一部分特点来作为我分类的依据。这也是特征选择的特点，需要人为的进行一定选择。而在情感分类中，一般从“词”这个层次来选择特征。比如这句话“手机非常好用！”，我给了它一个类标签“Positive”。里面有四个词（把感叹号也算上），“手机”，“非常”，“好用”，“！”。我可以认为这4个词都对分类产生了影响，都是分类的依据。也就是无论什么地方出现了这四个词的其中之一，文本都可以被分类为“积极”。这个是把所有词都作为分类特征。同样的，对这句话，我也可以选择它的双词搭配（Bigrams）作为特征。比如“手机 非常”，“非常 好用”，“好用 ！”这三个搭配作为分类的特征。以此类推，三词搭配（Trigrams），四词搭配都是可以被作为特征的。三、再之后特征要降维。特征降维说白了就是减少特征的数量。这有两个意义，一个是特征数量减少了之后可以加快算法计算的速度（数量少了当然计算就快了），另一个是如果用一定的方法选择信息量丰富的特征，可以减少噪音，有效提高分类的准确率。所谓信息量丰富，可以看回上面这个例子“手机非常好用！”，很明显，其实不需要把“手机”，“非常”，“好用”，“！”这4个都当做特征，因为“好用”这么一个词，或者“非常 好用”这么一个双词搭配就已经决定了这个句子是“积极”的。这就是说，“好用”这个词的信息量非常丰富。那要用什么方法来减少特征数量呢？答案是通过一定的统计方法找到信息量丰富的特征。统计方法包括：词频（Term Frequency）、文档频率（Document Frequency）、互信息（Pointwise Mutual Information）、信息熵（Information Entropy）、卡方统计（Chi-Square）等等。在情感分类中，用词频选择特征，也就是选在语料库中出现频率高的词。比如我可以选择语料库中词频最高的2000个词作为特征。用文档频率选特征，是选在语料库的不同文档中出现频率最高的词。而其它三个，太高端冷艳，表示理解得还不清楚，暂且不表。。。不过意思都是一样的，都是要通过某个统计方法选择信息量丰富的特征。特征可以是词，可以是词组合。四、把语料文本变成使用特征表示。在使用分类算法进行分类之前，第一步是要把所有原始的语料文本转化为特征表示的形式。还是以上面那句话做例子，“手机非常好用！”&如果在NLTK 中，如果选择所有词作为特征，其形式是这样的：[ {“手机”: True, “非常”: True, “好用”: True, “！”: True} , positive]如果选择双词作为特征，其形式是这样的：[ {“手机 非常”: True, “非常 好用”: True, “好用 ！”: True} , positive ]如果选择信息量丰富的词作为特征，其形式是这样的：[ {“好用”: True} , positive ]（NLTK需要使用字典和数组两个数据类型，True 表示对应的元素是特征。至于为什么要用True 这样的方式，我也不知道。。。反正见到的例子都是这样的。。。有空再研究看是不是可以不这样的吧）无论使用什么特征选择方法，其形式都是一样的。都是[ {“特征1”: True,&“特征2”: True,&“特征N”: True,&}, 类标签 ]五、把用特征表示之后的文本分成开发集和测试集，把开发集分成训练集和开发测试集。机器学习分类必须有数据给分类算法训练，这样才能得到一个（基于训练数据的）分类器。有了分类器之后，就需要检测这个分类器的准确度。根据《Python 自然语言处理》的方法，数据可以分为开发集合测试集。开发集专门用于不断调整和发现最佳的分类算法和特征维度（数量），测试集应该一直保持“不被污染”。在开发集开发完毕之后，再使用测试集检验由开发集确定的最佳算法和特征维度的效果。具体如图：&图2：开发集和测试集（摘自《Natural Language Processing with&Python》）一般来说，训练集的数量应该远大于测试集，这样分类算法才能找出里面的规律，构建出高效的分类器。用回前面的例子。假设2000条已经标注了积极和消极的评论数据，开发集可以是随机的1600条，测试集是剩余的随机400条。然后开发集中，训练集可以是随机的1400条，开发测试集是200条。六、用不同的分类算法给训练集构建分类器，用开发测试集检验分类器的准确度（选出最佳算法后可以调整特征的数量来测试准确度）。这个时候终于可以使用各种高端冷艳的机器学习算法啦！我们的目标是：找到最佳的机器学习算法。可以使用朴素贝叶斯（NaiveBayes），决策树（Decision Tree）等NLTK 自带的机器学习方法。也可以更进一步，使用NLTK 的scikit-learn 接口，这样就可以调用scikit-learn 里面的所有，对，是所有机器学习算法了。我已经忍不住的泪流满面。其实方法很容易。只要以下五步。1. 仅仅使用开发集（Development Set）。2. 用分类算法训练里面的训练集（Training Set），得出分类器。3. 用分类器给开发测试集分类（Dev-Test Set），得出分类结果。4. 对比分类器给出的分类结果和人工标注的正确结果，给出分类器的准确度。5. 使用另一个分类算法，重复以上三步。在检验完所有算法的分类准确度之后，就可以选出最好的一个分类算法了。在选出最好的分类算法之后，就可以测试不同的特征维度对分类准确度的影响了。一般来说，特征太少则不足以反映分类的所有特点，使得分类准确率低；特征太多则会引入噪音，干扰分类，也会降低分类准确度。所以，需要不断的测试特征的数量，这样才可以得到最佳的分类效果。七、选择出开发集中最佳的分类算法和特征维度，使用测试集检验得出情感分类的准确度。在终于得到最佳分类算法和特征维度（数量）之后，就可以动用测试集。直接用最优的分类算法对测试集进行分类，得出分类结果。对比分类器的分类结果和人工标注的正确结果，给出分类器的最终准确度。
阅读(6369)|
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
历史上的今天
loftPermalink:'',
id:'fks_',
blogTitle:'Python 文本挖掘：使用机器学习方法进行情感分析（原理）',
blogAbstract:'在这个系列的文章里面，机器学习都可以认为是有监督的分类方法。总体流程如图：&图1：机器学习的流程和结构（摘自《Natural Language Processing with&Python》）一、有监督意味着需要人工标注，需要人为的给文本一个类标签。比如我有5000条商品评论，如果我要把这些评论分成积极和消极两类。那我就可以先从里面选2000条评论，然后对这2000条数据进行人工标注，把这2000条评论标为“积极”或“消极”。这“积极”和“消极”就是类标签。假设有1000条评论被标为“积极”，有1000条评论被标为“消',
blogTag:'',
blogUrl:'blog/static/',
isPublished:1,
istop:false,
modifyTime:4,
publishTime:3,
permalink:'blog/static/',
commentCount:2,
mainCommentCount:2,
recommendCount:3,
bsrk:-100,
publisherId:0,
recomBlogHome:false,
currentRecomBlog:false,
attachmentsFileIds:[],
groupInfo:{},
friendstatus:'none',
followstatus:'unFollow',
pubSucc:'',
visitorProvince:'',
visitorCity:'',
visitorNewUser:false,
postAddInfo:{},
mset:'000',
remindgoodnightblog:false,
isBlackVisitor:false,
isShowYodaoAd:false,
hostIntro:'',
hmcon:'0',
selfRecomBlogCount:'0',
lofter_single:''
{list a as x}
{if x.moveFrom=='wap'}
{elseif x.moveFrom=='iphone'}
{elseif x.moveFrom=='android'}
{elseif x.moveFrom=='mobile'}
${a.selfIntro|escape}{if great260}${suplement}{/if}
{list a as x}
推荐过这篇日志的人：
{list a as x}
{if !!b&&b.length>0}
他们还推荐了：
{list b as y}
转载记录：
{list d as x}
{list a as x}
{list a as x}
{list a as x}
{list a as x}
{if x_index>4}{break}{/if}
${fn2(x.publishTime,'yyyy-MM-dd HH:mm:ss')}
{list a as x}
{if !!(blogDetail.preBlogPermalink)}
{if !!(blogDetail.nextBlogPermalink)}
{list a as x}
{if defined('newslist')&&newslist.length>0}
{list newslist as x}
{if x_index>7}{break}{/if}
{list a as x}
{var first_option =}
{list x.voteDetailList as voteToOption}
{if voteToOption==1}
{if first_option==false},{/if}&&“${b[voteToOption_index]}”&&
{if (x.role!="-1") },“我是${c[x.role]}”&&{/if}
&&&&&&&&${fn1(x.voteTime)}
{if x.userName==''}{/if}
网易公司版权所有&&
{list x.l as y}
{if defined('wl')}
{list wl as x}{/list}您当前的位置：>>
计算机类论文范文半监督学习的数据流混合集成分类算法
发布时间： 17:11所属分类：浏览：1次
数据流分析和挖掘在数据挖掘和机器学习领域是一个具有挑战性的研究，它已经受到了计算机智能研究者的广泛关注[1-3]。与传统的静态数据相比，数据流具有动态性、高维度、实时性、无限性、顺序性和高速到达等特点[4]，正是这些特点使得传统方法难以实现数据流
　　数据流分析和挖掘在数据挖掘和机器学习领域是一个具有挑战性的研究，它已经受到了计算机智能研究者的广泛关注[1-3]。与传统的静态数据相比，数据流具有动态性、高维度、实时性、无限性、顺序性和高速到达等特点[4]，正是这些特点使得传统方法难以实现数据流的挖掘。而数据流分类是数据流挖掘的其中一种，它是从大量数据样本中提取知识和信息的过程，而这些样本中隐含的概念和知识可能随着时间和环境不断的发生变化，即存在的概念漂移[5]给研究带来了挑战。因此，一个高效的数据流分类算法需要在有限的时间和内存下以相当好的准确度完成任务，并且能够自适应地处理概念漂移。
　　摘要：当前已有的数据流分类模型都需要大量已标记样本来进行训练，但在实际应用中，对大量样本标记的成本相对较高。针对此问题，提出了一种基于半监督学习的数据流混合集成分类算法SMEClass，选用混合模式来组织基础分类器，用K个决策树分类器投票表决为未标记数据添加标记，以提高数据类标的置信度，增强集成分类器的准确度，同时加入一个贝叶斯分类器来有效减少标记过程中产生的噪音数据。实验结果显示，SMEClass算法与最新基于半监督学习的集成分类算法相比，其准确率有所提高，在运行时间和抗噪能力方面有明显优势。
　　关键词：数据流,半监督学习,集成分类,概念漂移,混合集成
　　在已有研究中，解决概念漂移问题的方法概括起来有三种[6]：实例选择、实例加权和集成学习。近年来研究最热的当属集成学习方法[7-9]，它克服了运用滑动窗口方法参数难以确定的缺陷。尽管集成学习已经取得了相当客观的研究进展，但它是典型的有监督学习，需要大量的类标数据进行训练学习。而且标记数据是一个耗时又费力的工作，因此便有了近年来半监督学习的研究[10-12]，它通过引入未标记数据来提高分类器的泛化性能。可以说近年来集成学习和半监督学习的研究都有了新的突破，但将两者融合来改善分类性能的研究还是凤毛麟角。2002年Bennett等人[13]提出使用标记和未标记数据共同构造集成分类模型，文中主要运用Boosting方法，它的缺点在于没有一种机制来控制对无类标数据标记的错误率；在文献[14]中Woolam等人融合半监督聚类和集成方法先将无类标数据进行标记，当标记数据占到一定比例时再对数据进行聚类，再运用类标传播技术为剩余无类标数据进行标记，最后更新集成分类器，这样当数据量很大时类标传播会耗费[&O（n3）]的时间。
　　基于上述研究中存在的缺陷，该文将集成学习和半监督学习有效的融合，提出一种基于半监督学习的混合集成分类算法（Semi-SupervisedlearningBasedMixtureEnsembleClassifier，SMEClass），由于引入未标记数据，使得集成分类器的准确性和泛化性都得到了改善，而且在对未标记数据进行标记时使用集成分类器和在数据块已有的类标数据集上训练的分类器一同进行多数投票，更增加了被标记数据的可信度。同时，在算法中也使用了概念漂移检测和噪声过滤的机制，以便能够更有效的适应含噪音和概念漂移的数据流分类。
　　1SMEClass算法模型的训练和分类的流程
　　数据流分类挖掘面临着两大难题，一是概念漂移和噪音的影响，二是数据流实例标记的高额代价，很少有算法能高效地实现两者的兼顾，因此在标记样本少的情况下，既能兼顾概念漂移和噪音影响，又能确保分类的精度将是一个挑战，SMEClass能够解决这些问题，它假设数据流中的样本数据有一部分是随机标注的，然后使用我们的集成方法来对这些数据中的未标记实例进行标记，以增加分类的性能，而且在训练过程中进行了漂移监测和噪音过滤。
　　由于数据流的特性，在此算法中使用C4.5和Na?veBayes作为基础分类器来构建混合集成模型，在每个数据块上使用类似于self-training的方法来进行半监督学习。
　　首先对方法中涉及到的符号进行说明：如表1所示。
　　2SMEClass算法
　　2.1算法的合理性论证
　　数据块到达后，用其中的有标记数据训练一个C4.5分类器，使用这个分类器和集成分类器一同对未标记数据进行预测，如果预测错误率小于随机错误率，则将这个预测类标作为此数据的类标记。在最坏的情况下，当有噪音实例时，如果拥有足够的类标数据，就能降低分类的错误率，为了达到这样的效果，借鉴了文献[16]中的思想。
　　2.2算法的执行过程
　　3数据流变化的检测和识别
　　3.1概念漂移的检测
　　3.2噪声数据的过滤
　　为了降低噪音数据对概念漂移检测的影响，集成模型中增加了一个朴素贝叶斯分类器，这是因为Na?veBayes算法简单、速度快、准确率高，还有一个重要的特性就是对噪音数据相当敏感，利用它的统计特性，能够及时地发现数据中的噪音，以达到噪音过滤的效果。
　　使用这个计算方法，在[K+1]个分类器进行投票时，如果实例被一半以上的决策树分类器和Na?veBayes分类器同时分类错误，那么概念就存在潜在的漂移，将分类错误的实例放入缓冲区；反之，认为是噪音，不用其构建新的分类器，这样就减少了那些噪音数据对漂移检测的影响。
　　4实验及结果分析
　　基于人工数据集、UCI提供的真实数据集和已有的半监督集成分类方法SEClass[15]进行对比测试。分别从算法的准确率、运行时间和可扩展性三个方面验证SMEClass方法的有效性。实验运行环境为：1.73GHz英特尔奔腾双核PC机，1GB内存，WindowsXP操作系统。
　　为了实现算法，在实验中使用MOA平台，SMEClass的参数设置如下：[K=8]（基分类器个数），[d=5000]（数据块大小）；SEClass参数如下：[L=8]（基分类器个数），[K=50]（微簇个数），[M=5000]，[e=0.9]。采用先测试再训练的顺序，这样可以有效显示模型的泛化能力。人工数据集包括HyperPlane、RandomRBF、RandomTree、SEA和Waveform。具体构造见文献[9]，真实数据集采用UCI提供的ForestCovertype。
　　表2显示了数据集的相关信息，这里对数据集分成大小固定为1000的数据块，使他们分批到达来模拟数据流的特性。
　　4.1算法准确率分析
　　算法的准确率如表3所示，由于现实生活中获得已标记数据代价太大，在实验数据集中我们只利用[20%]的已标记数据，其余[80%]的数据是未标记的，而且在实验过程中增加了噪音数据和噪音属性，以测试SMEClass算法对噪音数据的过滤能力和对含噪音属性数据集的学习能力。
　　由于文献[15]中有两个属性权值处理方式，SEClass-I在训练中不调整属性权值，SEClass-II在训练迭代过程中动态调整属性权值，通过对比实验结果可以发现SMEClass和SEClass-II的准确率较高，由于SEClass-II动态调整属性权值可以减少噪音属性的影响，而SMEClass是采用的C4.5决策树分类模型，也能实现这一点，叶节点在分裂的过程中会选择具有最大增益率的属性进行分裂，这样每次都能选择最重要的属性。而且SMEClass采用的贝叶斯分类器还能够有效降低噪音数据对准确度的影响，而SEClass没有考虑噪音数据的影响，因此在同时含有噪音属性和噪音数据的情况下，SMEClass的分类准确率要略胜一筹。
　　4.2算法的运行时间和可扩展性
　　在人工数据集RandomRBF上测试SMEClass算法和SEClass算法，改变数据集的属性维度[d]来测试两个算法在高维数据情况下的运行时间，从而检验算法的可扩展性。实验结果如图2所示，纵坐标代表算法训练时间和测试时间之和。
　　观察实验结果，两个算法的运行时间都随属性量的增加呈线性增长趋势，这是因为在训练基本分类器和测试过程中他们都是和属性数量成线性关系的，但SMEClass的时间明显少于SEClass，这是因为SEClass算法在聚类过程中需要频繁计算实例间的距离，浪费了大量的时间，而SMEClass算法不存在这样的问题，因此在时间上有明显优势。这说明SMEClass算法在处理高维数据流时比较稳定，具有良好的可扩展性。
　　5结束语
　　针对数据流类标数据获取困难这一现状，该文提出将集成学习和半监督学习有效结合的一种分类算法SMEClass，算法在数据块上采用类似于self-training的学习方法将置信度高的无类标数据赋予标记后加入类标集来改善基分类器的性能，由于在标记过程中使用了集成分类器的多数投票机制，这使加入的无类标数据更加可靠，而且增加了一个Na?veBayes分类器用来去除数据所含噪音，及时更新集成分类器以适应概念漂移。
　　实验表明，与基于聚类的半监督数据流集成分类算法SEClass相比，SMEClass算法具有更高的准确度和较强的抗噪性，而且免去了存储大量微簇的空间，且运行时间随属性维度的增加呈现线性增长，具有一定的可扩展性，因此本文的算法能够用于高维数据流分类问题。
　　参考文献：
　　[1]LiaoSH，ChuPH，HsiaoPY.Dataminingtechniquesandapplications-Adecadereviewfrom[J].ExpertSystemswithApplications，）：.
　　[2]ReadJ，BifetA，HolmesG，PfahRINGERB.Scalableandefficientmulti-labelclassificationforevolvingdatastreams[J].MachineLearning，-2），243&272.
　　[3]白雪冰，王宝军.数据流分类算法分析[J].电脑知识与技术，）：.
　　[4]ZliobaiteI.Learningunderconceptdrift：anoverview[R/OL].Technicalreport，VilniusUniversity，2009.http：//arxiv.org/pdf/pdf.
　　[5]WidmerG，KubatM.Learninginthepresenceofconceptdriftandhiddencontexts[J].MachineLearning，）：69-101.
　　[6]HoS-s，WechslerH.AMartingaleframeworkfordetectingchangesindatastreamsbytestingexchangeability[J].IEEETransactionsonPatternAnalysisandMachineIntelligence，）：.
　　[7]ScholzM，KlinkenbergR.AnEnsembleClassifierforDriftingConcepts[C]//Proceedingsofthe2ndInternationalWorkshoponKnowledgeDiscoveryinData
　　Streams.Portugal：Porto，.
　　[8]AggarwalCC，HanJ，WangJY，etal.AFrameworkforOn-DemandClassificationofEvolvingDataStreams[J].IEEETransactionsonKnowledgeandDataEngineering，）：577-589.[9]BieftA，HolmesG，PfahringerB，etal.NewEnsembleMethodsforEvolvingDataStreams[C]//Proceedingsofthe15thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMing.France：Paris，8.
　　[10]ChapelleO，ScholkopfB，ZienA，editors.Semi-SupervisedLearning[M].Cambridge：MITPress，2006.
　　[11]ZhuX.Semi-supervisedlearningliteraturesurvey[R/OL].TechnicalReport1530，DepartmentofComputerSciences，UniversityofWisconsinatMadison，2006.http：//www.cs.wisc.edu/jerryzhu/pub/ssl_survey.pdf.
　　[12]ZhouZH，LiM.Semi-supervisedlearningbydisagreement[J].KnowledgeandInformationSystems，）：415-439.
　　[13]BennettK，DemirizA，MaclinR.Exploitingunlabeleddatainensemblemethods[C]//Proceedingsofthe8thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.Canada：Edmonton，6.
上一篇： 下一篇：
相关文章推荐数据挖掘 - 分类算法比较
简介分类算法是解决分类问题的方法，是数据挖掘、机器学习和模式识别中一个重要的研究领域。分类算法通过对已知类别训练集的分析，从中发现分类规则，以此预测新数据的类别。分类算法的应用非常广泛，银行中风险评估、客户类别分类、文本检索和搜索引擎分类、安全领域中的入侵检测以及软件项目中的应用等等。分类算法介绍以下介绍典型的分类算法。Bayes贝叶斯分类器的分类原理是通过某对象的先验概率，利用贝叶斯公式计算出其后验概率，即该对象属于某一类的概率，选择具有最大后验概率的类作为该对象所属的类。目前研究较多的贝叶斯分类器主要有四种，分别是：Naive Bayes、 TAN、BAN 和 GBN。贝叶斯网络（BayesNet）贝叶斯网络是一个带有概率注释的有向无环图，图中的每一个结点均表示一个随机变量 , 图中两结点间若存在着一条弧，则表示这两结点相对应的随机变量是概率相依的，反之则说明这两个随机变量是条件独立的。网络中任意一个结点 X 均有一个相应的条件概率表 Conditional Probability Table，CPT) ，用以表示结点 X 在其父结点取各可能值时的条件概率。若结点 X 无父结点 , 则 X 的 CPT 为其先验概率分布。贝叶斯网络的结构及各结点的 CPT 定义了网络中各变量的概率分布。应用贝叶斯网络分类器进行分类主要分成两阶段。第一阶段是贝叶斯网络分类器的学习，即从样本数据中构造分类器，包括结构学习和 CPT 学习；第二阶段是贝叶斯网络分类器的推理，即计算类结点的条件概率，对分类数据进行分类。这两个阶段的时间复杂性均取决于特征值间的依赖程度，甚至可以是 NP 完全问题，因而在实际应用中，往往需要对贝叶斯网络分类器进行简化。根据对特征值间不同关联程度的假设，可以得出各种贝叶斯分类器。朴素贝叶斯（NaiveBayes）朴素贝叶斯模型（NBC）发源于古典数学理论，有着坚实的数学基础，以及稳定的分类效率。同时，NBC 模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。NBC 模型假设属性之间相互独立，这个假设在实际应用中往往是不成立的，这给 NBC 模型的正确分类带来了一定影响。在属性个数比较多或者属性之间相关性较大时，NBC 模型的分类效率比不上决策树模型。而在属性相关性较小时，NBC 模型的性能最为良好。Lazy Learning相对其它的 Inductive Learning 的算法来说，Lazy Learning 的方法在训练是仅仅是保存样本集的信息，直到测试样本到达时才进行分类决策。也就是说这个决策模型是在测试样本到来以后才生成的。相对与其它的分类算法来说，这类的分类算法可以根据每个测试样本的样本信息来学习模型，这样的学习模型可能更好的拟 合局部的样本特性。kNN 算法的思路非常简单直观：如果一个样本在特征空间中的 k 个最相似 ( 即特征空间中最邻近 ) 的样本中的大多数属于某一个类别，则该样本也属于这个类别。其基本原理是在测试样本到达的时候寻找到测试样本的 k 临近的样本，然后选择这些邻居样本的类别最集中的一种作为测试样本的类别。在 weka 中关于 kNN 的算法有两个，分别是 IB1，IBk。IB1 即 1 近邻IB1 是通过它的一个邻居来判断测试样本的类别IBk 即 K 近邻IBk 是通过它周围的 k 个邻居来判断测试样本的类别在样本中有比较多的噪音点是（noisy points）时，通过一个邻居的效果很显然会差一些，因为出现误差的情况会比较多。这种情况下，IBk 就成了一个较优的选项了。这个时候有出现了一个问题，k 这个值如何确定，一般来说这个 k 是通过经验来判断的。Trees即决策树算法，决策树是对数据进行分类，以此达到预测的目的。该决策树方法先根据训练集数据形成决策树，如果该树不能对所有对象给出正确的分类，那么选择一些例外加入到训练集数据中，重复该过程一直到形成正确的决策集。决策树代表着决策集的树形结构。决策树由决策结点、分支和叶子组成。决策树中最上面 的结点为根结点，每个分支是一个新的决策结点，或者是树的叶子。每个决策结点代表一个问题或决策，通常 对应于待分类对象的属性。每一个叶子结点代表一种可能的分类结果。沿决策树从上到下遍历的过程中，在每个结点都会遇到一个测试，对每个结点上问题的不同的 测试输出导致不同的分支，最后会到达一个叶子结点，这个过程就是利用决策树进行分类的过程，利用若干个变量来判断所属的类别。Id3 即决策树 ID3 算法ID3 算法是由 Quinlan 首先提出的。该算法是以信息论为基础，以信息熵和信息增益度为衡量标准，从而实现对数据的归纳分类。以下是一些信息论的基本概念：定义 1：若存在 n 个相同概率的消息，则每个消息的概率 p 是 1/n，一个消息传递的信息量为 Log2(n)定义 2：若有 n 个消息，其给定概率分布为 P=(p1,p2 … pn)，则由该分布传递的信息量称为 P 的熵，记为I (p) =-(i=1 to n 求和 ) piLog2(pi) 。定义 3：若一个记录集合 T 根据类别属性的值被分成互相独立的类 C1C2..Ck，则识别 T 的一个元素所属哪个类所需要的信息量为 Info (T) =I (p) ，其中 P 为 C1C2 … Ck 的概率分布，即 P= (|C1|/|T| … |Ck|/|T|)定义 4：若我们先根据非类别属性 X 的值将 T 分成集合 T1,T2 … Tn，则确定 T 中一个元素类的信息量可通过确定 Ti 的加权平均值来得到，即 Info(Ti) 的加权平均值为：Info(X, T) = (i=1 to n 求和 ) ((|Ti|/|T |) Info (Ti))定义 5：信息增益度是两个信息量之间的差值，其中一个信息量是需确定 T 的一个元素的信息量，另一个信息量是在已得到的属性 X 的值后需确定的 T 一个元素的信息量，信息增益度公式为：Gain(X, T) =Info (T)-Info(X, T)J48 即决策树 C4.5 算法C4.5 算法一种分类决策树算法 , 其核心算法是 ID3 算法。C4.5 算法继承了 ID3 算法的优点，并在以下几方面对 ID3 算法进行了改进：用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；在树构造过程中进行剪枝；能够完成对连续属性的离散化处理；能够对不完整数据进行处理。C4.5 算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。RuleDecision Table 即决策表决策表 (Decision Table)，是一中使用表的结构，精确而简洁描述复杂逻辑的方式。JRip 即 RIPPER 算法规则归纳学习从分类实例出发能够归纳出一般的概念描述。其中重要的算法为 IREP 算法和 RIPPER 算法。重复增量修枝（RIPPER）算法生成一条规则，随机地将没有覆盖的实例分成生长集合和修剪集合，规定规则集合中的每个规则是有两个规则来生成：替代规则和修订规则。MetaAdaBoostM1 即 AdaBoosting 算法Adaboost 是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器 ( 弱分类器 ) ，然后把这些弱分类器集合起来，构成一个更强的最终分类器 ( 强分类器 ) 。其算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进行训练，最后将每次训练得到的分类器最后融合起来，作为最后的决策分类器。Bagging 即 Bagging 方法Bootstrps bagging boosting 都属于集成学习方法，将训练的学习器集成在一起。原理来源于 PAC 学习模型（Probably Approximately CorrectK）。其中的 Bagging 是 bootstrap aggregating 的缩写，是最早的 Ensemble 算法之一，它也是最直接容易实现，又具有不错的效果的算法之一。Bagging 中的多样性是由有放回抽取训练样本来实现的，用这种方式随机产生多个训练数据的子集，在每一个训练集的子集上训练一个同种分类器，最终分类结果是由多个分类器的分类结果多数投票而产生的。Weka 中分类算法的参数解释Correlation coefficient (= CC) ：
相关系数Root mean squared error (= RMSE) ： 均方根误差Root relative squared error (= RRSE) ： 相对平方根误差Mean absolute error (= MAE) ：
平均绝对误差Root absolute error (= RAE)
平均绝对误差平方根Combined: (1-abs (CC)) + RRSE + RAE：
结合的Accuracy (= ACC) ：
正确率注意，Correction coefficient 只适用于连续值类别，Accuracy 只适用于离散类别Kappa statistic：这个指标用于评判分类器的分类结果与随机分类的差异度。绝对差值（Mean absolute error）：这个指标用于评判预测值与实际值之间的差异度。把多次测得值之间相互接近的程度称为精密度，精密度用偏差表示，偏差指测得值与平均值之间的差值，偏差越小，精密度则越高。中误差（Root mean square error：RMSE）：带权残差平方和的平均数的平方根，作为在一定条件下衡量测量精度的一种数值指标。中误差是衡量观测精度的一种数字标准，亦称“标准差”或“均方根差”。在相同观测条件下的一组真误差平方中数的平方根。因真误差不易求得 , 所 以通常用最小二乘法求得的观测值改正数来代替真误差。它是观测值与真值偏差的平方和观测次数 n 比值的平方根。中误差不等于真误差，它仅是一组真误差的代表值。中误差的大小反映了该组观测值精度的高低，因此，通常称中误差为观测值的中误差。分类算法的评价标准预测的准确率：这涉及到模型正确地预测新的或先前没见过的数据的类 标号能力。速度：涉及到产生和使用模型的计算花费。强壮性：这涉及给定噪声数据或具有空缺值的数据，模型正确预测的能力。可伸缩性：这涉及给定大量的数据，有效的构造模型的能力。可解释性：这涉及学习模型提供的理解和洞察的层次。分类算法的比较 以下主要采用两种数据集（Monk's Problems 和 Satimage）来分别运行不同的分类算法，采用的是 Weka 数据挖掘工具。Monk's Problems 数据集特点1. 属性全部为 nominal 类型2. 训练样本较少图 1. 训练数据集3. 训练集数据的可视化图，该图根据直方图上方一栏所选择的 class 属性（attr6）来着色。图 2. 训练数据集可视化图各分类器初步分类效果分析各分类器不做参数调整，使用默认参数进行得到的结果。表 1. 分类器初步结果比较Data SourceCategoryClassifierCorrectly ClassifiedMean absolute errorRoot relative squared errorTime taken(Seconds)
BayesBayesNet
NaiveBayes
Decision Table
AdaBoostM1
分类器比较预测的准确率比较采用基于懒惰学习的 IB1、IBk 的分类器的误差率较低，采用基于概率统计的 BayesNet 分类器的误差率较高，其他的基于决策树和基于规则的分类器误差居于前两者之间，这是因为在样本较少的情况下，采用 IB1 时，生成的决策模型是在测试样本到来以后才生成，这样的学习模型可能更好的拟合局部的样本特性。采用统计学分类方法的 BayesNet 之所以准确度较低，可能是由于贝叶斯定理的成立本身需要很强的独立性假设前提，而此假设在实际情况中经常是不成立的。但是一般地，统计分类算法趋于计算量大。进一步比较分类结果的散点图（其中正确分类的结果用叉表示，分错的结果用方框表示），发现 BayesNet 分类器针对属性 6（attr6）的预测结果分错的结果明显比 IB1 的分错结果要多些，而这些错误的散点中，又以属性 6 的取值为 2 的散点中错误的数目较多。图 3. BayesNet 的分类结果散点图图 4. IB1 分类结果散点图分类速度比较Adaboost 的分类花了 0.08 秒，Bagging 的分类花了 0.03 秒，相对于其他的分类器，这两个分类器速度较慢。这是因为这两个算法采用迭代，针对同一个训练集，训练多种分类器，然后把这些分类器集合起来，所以时间消耗较长。分类器参数调优IBK 调优【 KNN 】：6扩大邻近学习的节点范围，降低异常点的干扰（距离较大的异常点）?
【 DistanceWeighting 】：Weight by 1/distance通过修改距离权重，进一步降低异常点的干扰（距离较大的异常点）图 5. IBk 分类调优IBk 调优结果调优后准确率从 60.65% 上升到 63.43%。表 2. IBk 调优结果Data SourceCategoryClassifierCorrectly ClassifiedMean absolute errorRoot relative squared errorTime taken(Seconds)
J48 调优【 binarySplits 】：True采用 2 分法，生成决策树。图 6. J48 分类调优J48 调优结果调优后准确率从 59.72% 上升到 64.35%，但是分类模型建立时间从 0 延长到了 0.31 秒表 3. J48 调优结果Data SourceCategoryClassifierCorrectly ClassifiedMean absolute errorRoot relative squared errorTime taken(Seconds)
Salmage 数据集特点1. 属性为 numeric 类型 , 共 37 个属性2. 训练数据各类不平衡，测试数据各类不平衡图 7. 训练数据集可视化图各分类器初步分类效果分析各分类器不做参数调整，使用默认参数得到的结果如下：表 4. 分类器初步结果比较Data SourceCategoryClassifierCorrectly ClassifiedMean absolute errorRoot relative squared errorTime taken(Seconds)
BayesBayesNet
NaiveBayes
NA (Not nominal data)
Decision Table
NA (Not enough memory)
AdaBoostM1
分类器比较预测的准确率比较采用基于懒惰学习的 IB1、IBk 的分类器的准确率都较高，为 90.36%，采用 基于决策桩的 AdaBoostM 分类器的准确率较低，为 43.08%，贝叶斯分类器的准确 率较之前的数据集（Monk ’ s problem）有明显的提高，从 49% 到了 80% 左右，这主 要是因为样本空间的扩大，其他的分类器准确率也处于 80% 左右。分类速度比较DecisionTable 的分类花了 4.33 秒，Bagging 的分类花了 3.92 秒，J48 的分类模型建立花了 2.06 秒，相对于其他的分类器，这三个分类器速度较慢。分类器参数调优IBK 调优【 KNN 】：6扩大邻近学习的节点范围，降低异常点的干扰（距离较大的异常点）?
【 DistanceWeighting 】：Weight by 1/distance通过修改距离权重，进一步降低异常点的干扰（距离较大的异常点）IBK 调优结果调优后准确率从 90.36% 上升到 90.98%, 准确度有略微提升，说明通过扩大邻近学习的节点范围不能明显提高分类器的性能。表 5. IBk 调优结果Data SourceCategoryClassifierCorrectly ClassifiedMean absolute errorRoot relative squared errorTime taken(Seconds)Test DataLazyIBk90.98%0.03950.14780.02J48 调优【 binarySplits 】：True采用 2 分法，生成决策树。J48 调优结果分类性能没有提升。说明采用 2 分法对分类没有影响。相反，时间比原来的算法有略微延长。表 6. J48 调优结果Data SourceCategoryClassifierCorrectly ClassifiedMean absolute errorRoot relative squared errorTime taken(Seconds)Test DataTreesJ4886.47%0.04840.20332.23改进和建议 本文给出的调优方法只是一个简单的示例，实际上根据合理的参数调整，这些分类算法的效果还能得到更大的提升。
参考 首页，查看 IBM 软件和开放技术的最新信息。
参考 ，得到更多的关于 Weka 软件的信息。
参考 和 。
参考更多有关 weka 的内容 。
随时关注 developerWorks 和。
访问 developerWorks 获得丰富的 how-to 信息、工具和项目更新以及，帮助您用开放源码技术进行开发，并将它们与 IBM 产品结合使用。
添加或订阅评论，请先或。
有新评论时提醒我
static.content.url=/developerworks/js/artrating/SITE_ID=10Zone=Open sourceArticleID=872762ArticleTitle=数据挖掘 - 分类算法比较publish-date=}