信息科学技术学院

TextCategorizationIIWangJiminNov18,2005信息科学技术学院·网络研究所上次课主要内容分类过程构建分类器的方法Rocchio方法朴素Bayes（NaiveBayes）k-近邻法（k-NearestNeighbor，kNN）：支持向量机（supportvectormachine，SVM）分类结果评估特征选取的方法信息科学技术学院·网络研究所OutlineClassifiers神经网络(NeuralNetwork，NNet)线性最小平方拟合(LinearLeast-squareFit,LLSF)支持向量机(SupportVectorMachines,SVM)（重点内容）Thresholdstrategy信息科学技术学院·网络研究所自动文本分类的一般过程（中文网页）待分类中文网页向量表示预处理训练集实例预处理特征选取算法分类算法校验集测试每个类的阈值训练结果类别表阈值策略候选类列表特征项向量表示训练过程分类过程信息科学技术学院·网络研究所神经网络(Neuralnetwork，NNet)是人工智能中研究比较成熟的技术。神经网络最早是由心理学家和神经生物学家提出的，旨在寻求和测试神经的计算模拟。神经网络是一组连接的输入/输出单元，其中每个连接都与一个权值相连。在学习阶段，通过不断调整神经网络的相连权值，使得能够正确预测输入样本的正确类标号。信息科学技术学院·网络研究所NNet神经网络通常由输入层、输出层和隐藏层组成，输入层的神经元个数等于样本的特征数，输出层就是分类判决层，它的神经元个数等于样本的类别数。特点：对噪声数据具有较高的承受能力，但训练需要花费较长的时间。信息科学技术学院·网络研究所NNet目前最流行的神经网络学习算法是：后向传播算法（Back-propagation,BP）。它通过迭代地处理一组训练样本，将每个样本的网络预测与实际知道的类标号比较，进行学习。对于每个训练样本，修改连接权值，使得网络预测与实际类之间的均方误差最小。这种修改“后向”地进行,即由输出层，经由每个隐藏层，到第一个隐藏层。信息科学技术学院·网络研究所BP算法基本步骤1．初始化网络各层的权值及神经元阈值。（一个小的随机数）2.向前传播输入：对每一样本，计算隐藏层和输出层每个单元的净输入和输出。信息科学技术学院·网络研究所BP算法基本步骤3.后向传播误差通过更新权值和偏置以反映网络的预测误差。信息科学技术学院·网络研究所BP算法基本步骤终止条件：更新权值较小正确分类的样本百分比超过预先指定的训练周期（实践中，权收敛可能需要数十万个周期）信息科学技术学院·网络研究所OutlineClassifiers神经网络(NeuralNetwork，NNet)线性最小平方拟合(LinearLeast-squareFit,LLSF)支持向量机(SupportVectorMachines,SVM)（重点内容）Thresholdstrategy信息科学技术学院·网络研究所Linearleast-squareFit•LinearRegressionProblemLookforsomearbitrarywTsuchthatwTxi.+w0directlypredictsthelabelciofdocumentxi.Minimizethesquareerrorbetweentheobservedandpredictedclassvariable:•Sum(wTxi.+w0-ci)•Widrow-Hoff(WH)updaterule(梯度下降法的一种).•TwoequivalentinterpretationsClassifierisahyperplane---g(x)=wTx+w0=0DocumentsareprojectedontoadirectionwT(垂直于超平面)Yang’sresult:outperformingNaïveBayesandkNN信息科学技术学院·网络研究所支持向量机支持向量机(SupportVectorMachines,SVM)----今天的重点内容信息科学技术学院·网络研究所自动文本分类的一般过程（中文网页）待分类中文网页向量表示预处理训练集实例预处理特征选取算法分类算法校验集测试每个类的阈值训练结果类别表阈值策略候选类列表特征项向量表示训练过程分类过程信息科学技术学院·网络研究所分类方法的划分我们主要介绍的是文档分类算法都属于统计学习法。根据分类结果的不同，基于统计学习法的分类系统在整体上可以被分为两类：独立二元（IndependentBinary）分类系统和m元（m-ary）分类系统所谓独立二元分类，就是给定一篇文档，分类系统对每一个类都独立地判断这篇文档是否属于该类：要么属于，要么不属于，而不存在其它的结果，并且在分类过程中，不同类别之间互不影响。所谓m元分类就是给定一篇文档，系统计算这篇文档与所有预先定义的类的相似度，并按这篇文档和各个候选类的相似度排序，最后输出候选类列表。信息科学技术学院·网络研究所Thresholdstrategies阈值选取策略：对于一篇待分类文档，应用m元分类算法通常得到多个类别。一般情况下都要求从这些候选类别中选择部分类别为该文档的最终分类结果。这个过程使用的方法通常被称为阈值策略。常见的阈值选取策略Rcut:rank-basedthresholdPcut:proportion-basedthresholdScut:score-basedlocaloptimizationthreshold信息科学技术学院·网络研究所Thresholdstrategy--RcutRcut（位置截尾法,rank-basedthreshold）:以文档为中心的阈值策略假设待分类的文档数目为n，有m个类别对于每一个待分类的文档d，分类系统都返回一个长为m的候选类列表，取候选类列表的前k项，这篇文档就被认为属于这k个类。这种阈值策略就被称为位置截尾法实现非常简单，能够胜任在线分类工作无法平滑地调整分类系统的性能:即使k变化1，每篇文档的类关系都要发生变化信息科学技术学院·网络研究所Thresholdstrategy--PcutPCut（比例截尾法,proportion-basedthreshold）:以类别为中心的阈值策略Pi表示训练集中属于类i的文档所占的比例。系统首先计算出每篇待分类文档的候选类列表，然后按照按类和文档的相似度排序，生成每个类的候选文档列表对于类Ci，取这个类的候选文档列表中的前n*Pi*x篇文档属于这个类，其他的文档则不属于这个类。其中x是经验比例因子，通过改变它的大小，可以平滑地调整系统的性能。控制分入各个类的文档数，使它们保持训练集中各个类文档数的比例关系。这种算法最大的问题是过分依赖于这种比例关系，而没有考虑类在候选类列表中的位置。系统性能比较平滑，但是不能实现在线分类。信息科学技术学院·网络研究所Thresholdstrategy--ScutSCut（最优截尾法,score-basedlocaloptimizationthreshold)以类别为中心阈值策略如果一篇文档和这个类的相似度大于这个类的最优截尾相似度，那么这篇文档就属于这个类。即每个类由一个最优截尾值（某一相似度值）。这可由系统预先取得：对每一个类，评价分类系统在测试集下对于这个类的分类性能，调整截尾相似度，使得系统的性能达到最优，此时截尾相似度的值就是这个类的最优截尾相似度。SCut算法性能比较优异，但是不能很好地处理那些稀有类别（就是比较少见的类别）。信息科学技术学院·网络研究所ThresholdstrategiesYang比较研究了上述三种阈值策略，结果发现SCut算法效果明显优于PCut和RCut算法。Feng’sexperimentatTianwang（但分类效率却要差些）对一个具体的分类系统，阈值的选取需要反复测试和调整。质量效率（秒）Micro-F1Macro-F1测试时间RCut0.82660.76004324SCut0.84010.78495368基本kNN0.82660.76002426信息科学技术学院·网络研究所OutlineClassifiers神经网络(NeuralNetwork，NNet)线性最小平方拟合(LinearLeast-squareFit,LLSF)支持向量机(SupportVectorMachines,SVM)（重点内容）Thresholdstrategy信息科学技术学院·网络研究所Thankyou!