中文文本分类.pptx

北京理工大学北京理工大学大数据搜索与挖掘实验室大数据搜索与挖掘实验室 吕笑吕笑 2013.10.31文本分类问题的提出文本分类问题的提出 假想图书馆的图书资料不加以分类,结果如何?随着互联网技术的飞速发展，各种电子文本数据 的数量急剧增加 信息数据量的爆炸性增长使得传统的手工处理方 法变得不切合实际文本表示文本表示文本分类的基本概念文本分类的基本概念第一部分第一部分特征选择特征选择第三部分第三部分分类器设计分类器设计第四部分第四部分目目 录录分类器评价分类器评价第五部分第五部分第二部分第二部分有意义串对分类的改进有意义串对分类的改进第六部分第六部分文本分类的基本概念文本分类的基本概念文本分类文本分类(Text Categorization或Text Classification，TC)l是根据给定文本的内容，将其判别为事先确定的若干个文本类别中的某一类或某几类的过程。l这里所指的文本可以是媒体新闻、科技、报告、电子邮件、技术专利、网页、书籍或其中的一部分。l由于类别是事先定义好的，因此分类是有指导的（或者说是有监督的）文本分类的基本概念文本分类的基本概念分类体系一般人工构造政治、体育、军事。中美关系、恐怖事件。分类系统可以是层次结构，如yahoo!分类模式2类问题，属于或不属于(binary)多类问题，多个类别(multi-class)，可拆分成2类问题一个文本可以属于多类(multi-label)这里讲的分类主要基于内容很多分类体系:Reuters分类体系、中图分类文本分类的基本概念文本分类的基本概念冗余过滤 在数字图书馆和搜索引擎的建设中组织管理图书馆利用图书分类法来管理所收藏的图书资料 智能检索搜索引擎的构建过程中 信息过滤 “人找信息”成为“信息找人”其它应用 元数据提取、构建索引、文本过滤应用领域文本分类的基本概念文本分类的基本概念文本分类的一般过程文本表示训练过程分类过程训练文本统计统计量特征表示学习分类器新文本特征表示类别文本分类的基本概念文本分类的基本概念文本表示文本表示第一部分第一部分特征选择特征选择第三部分第三部分分类器设计分类器设计第四部分第四部分目目 录录分类器评价分类器评价第五部分第五部分第二部分第二部分有意义串对分类的改进有意义串对分类的改进第六部分第六部分文本表示文本表示-中文分词中文分词中文的预处理要比英文的预处理要复杂的多，因为汉语的基元是字而不是词，中文的预处理要比英文的预处理要复杂的多，因为汉语的基元是字而不是词，句子中的词语间没有固定的分隔符（如空格），因此必需对中文文本进行句子中的词语间没有固定的分隔符（如空格），因此必需对中文文本进行词词条切分处理条切分处理。基于基于词典和规则词典和规则的方法，应用词典匹配、汉语词的方法，应用词典匹配、汉语词法、约束矩阵等知识进行分词法、约束矩阵等知识进行分词基于基于统计的方法统计的方法:将汉语基于字与词的统计信息，将汉语基于字与词的统计信息，如相邻字间互信息、词频及相应贡献信息等应用于如相邻字间互信息、词频及相应贡献信息等应用于分词分词混和方法混和方法文本表示文本表示-向量空间模型向量空间模型向量空间模型(Vector Space Model,简称VSM)文档（Document）：泛指一般的文献或文献中的片断（段落、句子组或句子），一般指一篇文章。项（Term）：当文档的内容被简单地看成是它含有的基本语言单位（字、词、词组或短语等）所组成的集合时，这些基本的语言单位统称为项，即文档可以用项集（Term List）表示为 其中 是项,文本表示文本表示-向量空间模型向量空间模型n 项的权重（Term Weight）：对于含有n个项的文档 ，项常常被赋 予一定的权重,表示它们在文档中的重要程度，即 为了简化分析，可以暂不考虑 在文档中的先后顺序并要求 无异（即没有重复）这时可以把 看成一个n维的坐标系，而 为相应的坐标值，因而 被看成是n维空间中的一个向量文本表示文本表示-向量空间模型向量空间模型相似度（Similarity）：当文档被表示为VSM，常用向量之间的内积来计算：或用夹角余弦值来表示：文本分类的基本概念文本分类的基本概念特征选择特征选择第一部分第一部分文本表示文本表示第三部分第三部分分类器设计分类器设计第四部分第四部分目目 录录分类器评价分类器评价第五部分第五部分第二部分第二部分有意义串对分类的改进有意义串对分类的改进第六部分第六部分特征选择特征选择目的:为了提高程序的效率，提高运行速度为了提高分类精度一些通用的、各个类别都普遍存在的词汇对分类的贡献小在某特定类中出现比重大而在其他类中出现比重小的词汇对文本分类的贡献大对于每一类，我们应去除那些表现力不强的词汇，筛选出针对该类的特征项集合特征选择特征选择文档频率DF 信息增益IG互信息MI 统计量（CHI-2）常用方法常用方法特征选择特征选择常用方法常用方法-文档频率文档频率DFDocument frequency，文档频率，简称DF指在训练语料中出现某词条的文档数Term的DF小于某个阈值去掉(太少，没有代表性)Term的DF大于某个阈值也去掉(太多，没有区分度)特征选择特征选择常用方法常用方法-信息增益信息增益IG对于特征词条t和文档类别c，IG考察c中出现和不出现t的文档频数来衡量t对于c的信息增益，定义如下：特征选择特征选择常用方法常用方法-信息增益信息增益IG信息增益的优点在于，它考虑了词条未发生的情况，即虽然某个单词不出现也可能对判断文本类别有贡献。但在类分布和特征值分布是高度不平衡的情况下其效果就会大大降低了。特征选择特征选择常用方法常用方法-互信息互信息MI互信息(Mutual Information)在统计语言模型中被广泛使用。它是通过计算特征词条t和类别c之间的相关性来完成提取的。其定义如下:特征选择特征选择常用方法常用方法-互信息互信息MI如果用A表示包含特征词条t且属于类别c的文档频数，B为包含t但是不属于c的文档频数，C表示属于c但不包含t的文档频数，N表示语料中文档的总数，t和c的互信息可由下式计算：特征选择特征选择常用方法常用方法-统计量（统计量（CHI-2）它度量特征词条t和文档类别c之间的相关程度，并假设t和c之间符合具有一阶自由度的分布。特征词条对于某类的统计值越高，它与该类之间的相关性越大，携带的类别信息也越多。反之，统计量也是反映属性t和类别c之间的独立程度。当值为0时，属性t与类别c完全独立。特征选择特征选择常用方法常用方法-统计量（统计量（CHI-2）令N表示训练语料中的文档总数，c为某一特定类别，t表示特定的词条A表示属于c类且包含t的文档频数，B表示不属于c但是包含t的文档频数C表示属于c类但是不包含t的文档频数，D是既不属于c也不包含t的文档频数.其定义为：ABCDttcc特征选择特征选择特征选择方法性能比较特征选择方法性能比较特征选择特征选择特征选择方法性能比较特征选择方法性能比较注：以上实验结果来自于Yang,Y.,Pedersen J.P.A Comparative Study on Feature Selection in Text Categorization Proceedings of the Fourteenth International Conference on Machine Learning(ICML97),1997,pp412-420.特征选择特征选择文本分类的基本概念文本分类的基本概念分类器设计分类器设计第一部分第一部分文本表示文本表示第三部分第三部分第四部分第四部分目目 录录分类器评价分类器评价第五部分第五部分第二部分第二部分有意义串对分类的改进有意义串对分类的改进第六部分第六部分分类器设计分类器设计文本分类的方法大部分来自于模式分类，基本上可以分为三大类:一种是基于统计的方法，如Nave Bayes,KNN、类中心向量、回归模型、支持向量机、最大熵模型等方法另一种是基于连接的方法，即人工神经网络还有一种是基于规则的方法，如决策树、关联规则等，这些方法的主要区别在于规则获取方法 K K近邻算法近邻算法-KNN-KNN支持向量机算法支持向量机算法-SVM-SVM决策树算法决策树算法-Decision Tree神经网络算法神经网络算法-Neural Networks朴素贝叶斯算法朴素贝叶斯算法-Nave Bayes 分类器设计分类器设计常用分类器常用分类器分类器设计分类器设计K近邻算法近邻算法-KNN基本思想是：在给定新文本后，考虑在训练文本集中与该新文本距离最近(最相似)的K篇文本根据这K篇文本所属的类别判定新文本所属的类别 新文本k=1,A类k=4，B类k=10，c类分类器设计分类器设计K近邻算法近邻算法-KNN具体的算法步骤:根据特征项集合重新描述训练文本向量在新文本到达后，根据特征词，确定新文本的向量表示在训练文本集中选出与新文本最相似的K个文本，计算公式为：其中，K值的确定目前没有很好的方法，一般先定一个初始值，然后根据试验测试的结果调整K值，一般初始值定在几百到几千之间分类器设计分类器设计K近邻算法近邻算法-KNN在新文本的k个邻居中，依次计算每类的权重，计算公式如下：其中，为新文本的特征向量，为相似度计算公式，与上一步骤的计算公式相同,而 为类别属性函数，即如果 属于类 ，那么函数值为1，否则为0；比较每类的权重，将文本分到权重最大的那个类别中分类器设计分类器设计决策树算法决策树算法-Decision Tree决策树方法的起源是概念学习系统CLS，然后发展到ID3方法而为高潮，最后又演化为能处理连续属性的C4.5。有名的决策树方法还有CART和Assistant分类器设计分类器设计决策树的表示法决策树的表示法决策树通过把实例从根节点排列到某个叶子节点来分类实例，叶子节点即为实例所属的分类。树上的每一个节点说明了对实例的某个属性的测试，并且该节点的每一个后继分支对应于该属性的一个可能值分类器设计分类器设计ID3ID3决策树算法简介决策树算法简介基本思路是不断选取产生信息增益最大的属性来划 分样例集和，构造决策树。信息增益定义为结点与其子结点的信息熵之差。Pi为子集合中不同性(而二元分类即正样例和负样例)的样例的比例。分类器设计分类器设计ID3ID3决策树算法简介决策树算法简介这样信息收益可以定义为样本按照某属性划分时造成熵减少的期望，可以区分训练样本中正负样本的能力，其计算公式是分类器设计分类器设计ID3算法实例算法实例分类器设计分类器设计计算信息增益计算信息增益分类器设计分类器设计不同属性的信息增益不同属性的信息增益计算各属性的熵值Gain(S,Outlook)=0.246Gain(S,Humidity)=0.151Gain(S,Wind)=0.048Gain(S,Temperature)=0.029可以看到，Outlook得信息增益最大分类器设计分类器设计D1,D2,D149+,5-OutlookSunnyD1,D2,D8,D9,D112+,3-RainD4,D5,D6,D10,D143+,2-D3,D7,D12,D134+,0-Overcast?哪一个属性在这里被测试？?YesSsunny=D1,D2,D8,D9,D11Gain（Ssunny,Humidity）=0.970-(3/5)0.0-(2/5)0.0=0.970Gain(Ssunny,Temperature)=0.970-(2/5)0.0-(2/5)1.0-(1/5)0.0=0.570Gain(Ssunny,Wind)=0.970-(2/5)1.0-(3/5)0.918=0.019分类器设计分类器设计最终得到的决策树最终得到的决策树有了决策树后，就可以根据气候条件做预测了例如如果气候数据是Sunny,Cool,Normal,Strong,根据决策树到左侧的yes叶节点，可以判定属于P。分类器设计分类器设计神经网络算法神经网络算法-Neural Networks基本思想:神经网络是模仿人脑神经网络的结构和某些工作机制而建立的一种计算模型常用的神经计算模型有多层感知机、反传网络、自适应映射网络等神经网络通常由输入层、输出层和若干个隐层组成输入层的神经元个数等于样本的特征数输出层就是分类判决层，它的神经元个数等于样本类数 分类器设计分类器设计BP网络网络.c1c2cn输入层 隐层 输出层 分类器设计分类器设计支持向量机算法支持向量机算法-SVM-SVM主要思想是:针对两类分类问题，在高维空间中寻找一个超平面作为两类的分割，以保证最小的分类错误率它通过非线性变换，将输入向量映射到一个高维空间H在H中构造最优分类超平面，从而达到最好的泛化能力 分类器设计分类器设计支持向量机算法支持向量机算法-SVM-SVM支持向量最优分类面分类器设计分类器设计朴素贝叶斯算法朴素贝叶斯算法-Nave Bayes 基本思想:计算文本属于类别的概率。文本属于类别的概率等于文本中的每个词属于类别的概率的综合表达式。分类器设计分类器设计朴素贝叶斯算法朴素贝叶斯算法-Nave Bayes 设各个类别的集合为 c1,c2,cn设d为实例的描述确定d的类别P(D)可以根据下式确定分类器设计分类器设计朴素贝叶斯算法朴素贝叶斯算法-Nave Bayes 如果假定样例的特征是独立的，可以写为：因此，只需要知道每个特征和类别的P(wj|ci)如果只计算单个特征的分布，大大地减少了计算量分类器设计分类器设计朴素贝叶斯算法朴素贝叶斯算法-Nave Bayes 设V为文档集合D所有词词表对每个类别 ci C Di 是文档D中类别Ci的文档集合 P(ci)=|Di|/|D|设 ni 为Di中词的总数 对每个词 wj V 令 nij 为Di中wij的数量 P(wi|ci)=(nij+1)/(ni+|V|)分类器设计分类器设计朴素贝叶斯算法朴素贝叶斯算法-Nave Bayes 给定测试文档 X设 n 为X中词的个数返回的类别:wi是X中第i个位置的词分类器设计分类器设计特征选择特征选择文本分类的基本概念文本分类的基本概念分类器评价分类器评价第一部分第一部分文本表示文本表示第三部分第三部分第四部分第四部分目目 录录第五部分第五部分第二部分第二部分有意义串对分类的改进有意义串对分类的改进第六部分第六部分分类器评价分类器评价两类分类评价两类分类评价 二值分类列联表 Contingency Table 真正属于该类的文档数真正不属于该类的文档数判断为属于该类的文档数ab判断为不属于该类的文档数cd分类器评价分类器评价两类分类评价两类分类评价 查全率(Recall，简记为r)r=a/(a+c)查准率(Precision，简记为p)p=a/(a+b)分类器评价分类器评价宏观平均是先对每一个类统计r,p值，然后对所有的类求p的平均值，即 微观平均是先建立一个全局列联表，然后根据这个全局列联表进行计算，即 两类分类评价两类分类评价 分类器评价分类器评价平衡点(Break-Even Point)对于分类系统来说，r和p值是互相影响的,一种做法是选取r和p 相等时的值来表征系统性能，这个值叫做平衡点(Break-Even Point，简称BEP)值 F值(F-measure)另一种常用的将查全率和查准率结合起来的性能评价方法,其计算公式为 两类分类评价两类分类评价 分类器评价分类器评价多类分类评价多类分类评价 P=找到的该文档所属的正确类别数目/判断为该文档所属类的类别数目R=找到的该文档所属的正确类别数目/该文档所属的所有类别数目整个分类器的评估应该是对所有测试文档的这两个指标的统计平均 通常使用的统计平均为11点插值平均查准率(Interpolated 11-point Average Precision)分类器评价分类器评价分类器设计分类器设计特征选择特征选择文本分类的基本概念文本分类的基本概念有意义串对分类的改进有意义串对分类的改进第一部分第一部分文本表示文本表示第三部分第三部分第四部分第四部分目目 录录第五部分第五部分第二部分第二部分第六部分第六部分有意义串对分类的改进有意义串对分类的改进三点原因三点原因因为有意义串可以因为有意义串可以发现跟类别相关的发现跟类别相关的新用语、人名等特新用语、人名等特征词汇。征词汇。有意义串除了能作为有意义串除了能作为特征改进分类效果以特征改进分类效果以外，其属性值也可以外，其属性值也可以用来标示特征的权重用来标示特征的权重与单个词相比较，与单个词相比较，有意义串包含更有意义串包含更多信息量，能够多信息量，能够更准确地表达语更准确地表达语义概念，减少歧义概念，减少歧义产生的情况义产生的情况有意义串对分类的改进有意义串对分类的改进分类可分为分类可分为训练阶段训练阶段和和分类阶段分类阶段在训练阶段，一组已被标记好的文档集合被用来训练分类器；在训练阶段，一组已被标记好的文档集合被用来训练分类器；在分类阶段，分类系统用已经训练好的分类器将给定的文档在分类阶段，分类系统用已经训练好的分类器将给定的文档标记为一个预先设定好的类别。标记为一个预先设定好的类别。首先利用有意义串提取模块，从训练文档集合的所有文件中首先利用有意义串提取模块，从训练文档集合的所有文件中提取有意义串并生成有意义串集合提取有意义串并生成有意义串集合MSSet.接着将接着将MSSet和和词典词典D中的词条输入到特征提取模块中，利用特征提取方法中的词条输入到特征提取模块中，利用特征提取方法从从MSSet和和D中提取有效的特征向量中提取有效的特征向量利用利用有意义串的属性值有意义串的属性值对特征向量中的每一个特征赋权值并对特征向量中的每一个特征赋权值并将每个文档表示成将每个文档表示成m维的向量维的向量最后用生成的文档向量集合来训练分类器。生成的分类器即最后用生成的文档向量集合来训练分类器。生成的分类器即可对新的文档进行分类可对新的文档进行分类有意义串对分类的改进有意义串对分类的改进有意义串属性对特征权值的改进是核心字符串字符串S的邻接类别的邻接类别AV值值：S左边邻接的词的类别数目和右边邻接的词的类别数目的最小值，能够反映一个字符串的语用丰富程度，语用环境越多样，说明该字符串的重要程度越高。词长度词长度：字符串包含词典词的数目。词长度越大的字符串语义越明确，具有更高的分类能力，因此要加大该字符串的权重 SIG（S）=AV（S）*（logLen(S)+1）假设S=W1W2W3Wn，Wi为词典词，AV（S）表示S的邻接类别值，Len(S)表示S的词长度。SIG（S）表示一个字符串的重要性字符串S可以选择只用SIG（S）作为特征权重，也可以用SIG（S）与传统的TFIDF想结合来表示特征的权重。有意义串对分类的改进有意义串对分类的改进DictDict+MSNave Bayes68.943371.8315(+0.042)LibSVM73.632374.21(+0.008)C4.563.846464.3221(+0.007)DictDict+MSNave Bayes79.291679.7033(+0.005)LibSVM73.433275.6131(+0.030)C4.572.207171.7984(-0.007)电脑语料加入有意义串的分类准确率电脑语料加入有意义串的分类准确率科技语料加入有意义串的分类准确率科技语料加入有意义串的分类准确率有意义串对分类的改进有意义串对分类的改进DICTDICT+MS50078.8579（+0.02）100080.67581.275（+0.007）150080.966781.5667(+0.007)200080.8581.35(+0.006)语料规模对改进效果的影响（语料规模对改进效果的影响（Naive Bayes）有意义串对分类的改进有意义串对分类的改进有意义串属性对特征权重的改进有意义串属性对特征权重的改进TF*IDFSIGSIG*TF*IDF电脑语料70.234571.4917（+0.018）70.6082科技语料80.673183.9423（+0.041）79.1346