文本分类

汇报人：王鹏导师：王成中文文本分类汇报提纲文本表示文本分类的基本概念第一部分特征选择第三部分分类器设计第四部分分类器评价第五部分第二部分一、文本分类基本概念文本分类（Textcategorization）是指在给定分类体系下，根据文本内容自动确定文本类别的过程．20世纪90年代以前，占主导地位的文本分类方法一直是基于知识工程的分类方法，即由专业人员手工进行分类．人工分类非常费时，效率非常低．90年代以来，众多的统计方法和机器学习方法应用于自动文本分类，文本分类技术的研究引起了研究人员的极大兴趣．目前在国内也已经开始对中文文本分类进行研究，并在信息检索、Web文档自动分类、数字图书馆、自动文摘、分类新闻组、文本过滤、单词语义辨析以及文档的组织和管理等多个领域得到了初步的应用．比较有影响力的是中科院的开发的汉语词法分析系统ICTCLAS系统一、文本分类基本概念文本分类的一般过程文本表示训练过程分类过程训练文本统计统计量特征表示学习分类器新文本特征表示类别二、文本表示-词条切分中文的预处理要比英文的预处理要复杂的多，因为汉语的基元是字而不是词，句子中的词语间没有固定的分隔符（如空格），因此必需对中文文本进行词条切分处理。◆基于词典和规则的方法，应用词典匹配、汉语词法、约束矩阵等知识进行分词◆基于统计的方法:将汉语基于字与词的统计信息，如相邻字间互信息、词频及相应贡献信息等应用于分词◆混和方法二、文本表示-空间向量模型•向量空间模型(VectorSpaceModel,简称VSM)•文档（Document）：—泛指一般的文献或文献中的片断（段落、句子组或句子），一般指一篇文章。•项（Term）：当文档的内容被简单地看成是它含有的基本语言单位（字、词、词组或短语等）所组成的集合时，这些基本的语言单位统称为项，即文档可以用项集（TermList）表示为其中是项,二、文本表示-空间向量模型项的权重（TermWeight）：—对于含有n个项的文档，项常常被赋予一定的权重,表示它们在文档中的重要程度，即Ｄ＝为了简化分析，可以暂不考虑在文档中的先后顺序并要求无异（即没有重复）–这时可以把看成一个n维的坐标系，而为相应的坐标值，因而被看成是n维空间中的一个向量),...,,(21nTTTD),;...;,;,(2211nnWTWTWTDkTkTnTTT,...,,21n),...,,(21n二、文本表示-空间向量模型•相似度（Similarity）：当文档被表示为VSM，常用向量之间的内积来计算：或用夹角余弦值来表示：,))((*cos),(12212112121nkknkknkkk,*),(12121nkkkWWDDSim三、特征选择•目的:–为了提高程序的效率，提高运行速度–为了提高分类精度•一些通用的、各个类别都普遍存在的词汇对分类的贡献小•在某特定类中出现比重大而在其他类中出现比重小的词汇对文本分类的贡献大•对于每一类，我们应去除那些表现力不强的词汇，筛选出针对该类的特征项集合三、特征选择常用方法•文档频率DF•信息增益IG•互信息MI•统计量（CHI-2）三、特征选择常用方法-文档频率DF–Documentfrequency，文档频率，简称DF–指在训练语料中出现某词条的文档数–Term的DF小于某个阈值去掉(太少，没有代表性)–Term的DF大于某个阈值也去掉(太多，没有区分度)三、特征选择常用方法-信息增益IG•对于特征词条t和文档类别c，IG考察c中出现和不出现t的文档频数来衡量t对于c的信息增益，定义如下：三、特征选择常用方法-信息增益IG•信息增益的优点在于，它考虑了词条未发生的情况，即虽然某个单词不出现也可能对判断文本类别有贡献。•但在类分布和特征值分布是高度不平衡的情况下其效果就会大大降低了。三、特征选择常用方法-互信息MI•互信息(MutualInformation)在统计语言模型中被广泛使用。•它是通过计算特征词条t和类别c之间的相关性来完成提取的。其定义如下:()(,)lg()()PtcMItcPtPc三、特征选择常用方法-互信息MI•如果用A表示包含特征词条t且属于类别c的文档频数，B为包含t但是不属于c的文档频数，C表示属于c但不包含t的文档频数，N表示语料中文档的总数，t和c的互信息可由下式计算：(,)lg()()ANMItcACAB三、特征选择常用方法-统计量（CHI-2）•它度量特征词条t和文档类别c之间的相关程度，并假设t和c之间符合具有一阶自由度的分布。•特征词条对于某类的统计值越高，它与该类之间的相关性越大，携带的类别信息也越多。•反之，统计量也是反映属性t和类别c之间的独立程度。当值为0时，属性t与类别c完全独立。三、特征选择•令N表示训练语料中的文档总数，c为某一特定类别，t表示特定的词条•A表示属于c类且包含t的文档频数，B表示不属于c但是包含t的文档频数•C表示属于c类但是不包含t的文档频数，D是既不属于c也不包含t的文档频数.其定义为：))()()(()(),(22DCBADBCACBADNctABCDt~tc~c三、特征选择特征选择方法性能比较三、特征选择特征选择方法性能比较分类器设计K近邻算法-KNN•基本思想是：–在给定新文本后，考虑在训练文本集中与该新文本距离最近(最相似)的K篇文本–根据这K篇文本所属的类别判定新文本所属的类别新文本k=1,A类k=4，B类k=10，c类分类器设计K近邻算法-KNN•具体的算法步骤:–根据特征项集合重新描述训练文本向量–在新文本到达后，根据特征词，确定新文本的向量表示–在训练文本集中选出与新文本最相似的K个文本，计算公式为：其中，K值的确定目前没有很好的方法，一般先定一个初始值，然后根据试验测试的结果调整K值，一般初始值定在几百到几千之间12211(,)()()MikjkkijMMikjkkkwwsimddww分类器设计K近邻算法-KNN•在新文本的k个邻居中，依次计算每类的权重，计算公式如下：其中，为新文本的特征向量，为相似度计算公式，与上一步骤的计算公式相同,而为类别属性函数，即如果属于类，那么函数值为1，否则为0；•比较每类的权重，将文本分到权重最大的那个类别中(,)(,)(,)ijiijdKNNpxcsimxdydcx(,)isimxd(,)ijydcidjc分类器设计决策树算法-DecisionTree•决策树方法的起源是概念学习系统CLS，然后发展到ID3方法而为高潮，最后又演化为能处理连续属性的C4.5。有名的决策树方法还有CART和Assistant分类器设计决策树的表示法•决策树通过把实例从根节点排列到某个叶子节点来分类实例，叶子节点即为实例所属的分类。•树上的每一个节点说明了对实例的某个属性的测试，并且该节点的每一个后继分支对应于该属性的一个可能值分类器设计ID3决策树算法简介基本思路是不断选取产生信息增益最大的属性来划分样例集和，构造决策树。信息增益定义为结点与其子结点的信息熵之差。Pi为子集合中不同性(而二元分类即正样例和负样例)的样例的比例。分类器设计ID3决策树算法简介这样信息收益可以定义为样本按照某属性划分时造成熵减少的期望，可以区分训练样本中正负样本的能力，其计算公式是分类器设计神经网络算法-NeuralNetworks•基本思想:–神经网络是模仿人脑神经网络的结构和某些工作机制而建立的一种计算模型–常用的神经计算模型有多层感知机、反传网络、自适应映射网络等–神经网络通常由输入层、输出层和若干个隐层组成•输入层的神经元个数等于样本的特征数•输出层就是分类判决层，它的神经元个数等于样本类数分类器设计BP网络.....c1c2cn……输入层隐层输出层分类器设计支持向量机算法-SVM•主要思想是:–针对两类分类问题，在高维空间中寻找一个超平面作为两类的分割，以保证最小的分类错误率–它通过非线性变换，将输入向量映射到一个高维空间H–在H中构造最优分类超平面，从而达到最好的泛化能力分类器设计支持向量机算法-SVM支持向量最优分类面分类器设计朴素贝叶斯算法-NaïveBayes•基本思想:–计算文本属于类别的概率。–文本属于类别的概率等于文本中的每个词属于类别的概率的综合表达式。分类器设计朴素贝叶斯算法-NaïveBayes•设各个类别的集合为{c1,c2,…cn}•设d为实例的描述•确定d的类别•P(D)可以根据下式确定)d()|d()()d|(PcPcPcPiiiniiiniiPcPcPcP111)d()|d()()d|(niiicPcPP1)|d()()d(分类器设计朴素贝叶斯算法-NaïveBayes•如果假定样例的特征是独立的，可以写为：•因此，只需要知道每个特征和类别的P(wj|ci)•如果只计算单个特征的分布，大大地减少了计算量)|()|()|d(121mjijimicWPc分类器设计朴素贝叶斯算法-NaïveBayes设V为文档集合D所有词词表对每个类别ciCDi是文档D中类别Ci的文档集合P(ci)=|Di|/|D|设ni为Di中词的总数对每个词wjV令nij为Di中wij的数量P(wi|ci)=(nij+1)/(ni+|V|)分类器设计朴素贝叶斯算法-NaïveBayes•给定测试文档X•设n为X中词的个数•返回的类别:•wi是X中第i个位置的词)|()(argmax1niiiiCiccwPcP分类器评价两类分类评价•二值分类列联表ContingencyTable真正属于该类的文档数真正不属于该类的文档数判断为属于该类的文档数ab判断为不属于该类的文档数cd分类器评价两类分类评价•查全率(Recall，简记为r)r=a/(a+c)•查准率(Precision，简记为p)p=a/(a+b)分类器评价宏观平均是先对每一个类统计r,p值，然后对所有的类求p的平均值，即cCrrC()cCPpC微观平均是先建立一个全局列联表，然后根据这个全局列联表进行计算，即CCCaracCCCapab两类分类评价分类器评价•平衡点(Break-EvenPoint)对于分类系统来说，r和p值是互相影响的,一种做法是选取r和p相等时的值来表征系统性能，这个值叫做平衡点(Break-EvenPoint，简称BEP)值•F值(F-measure)另一种常用的将查全率和查准率结合起来的性能评价方法,其计算公式为两类分类评价221prFpr分类器评价多类分类评价•P=找到的该文档所属的正确类别数目/判断为该文档所属类的类别数目•R=找到的该文档所属的正确类别数目/该文档所属的所有类别数目•整个分类器的评估应该是对所有测试文档的这两个指标的统计平均•通常使用的统计平均为11点插值平均查准率(Interpolated11-pointAveragePrecision)