6.文本分类全解

数据挖掘：文本分类专题王成〔副教授〕华侨大学计算机科学与技术学院主要内容文本分类及文档的特征向量余弦相似度使用分类算法进行文本分类逆文档频率TF-IDFTF-IDF的信息论依据浅谈中文分词本节内容来源于吴军博士?数学之美?文本分类文本分类所谓新闻的分类，或者更广义的讲任何文本的分类，无非是要把相似的新闻放到同一类中如果让编辑来对新闻分类，他一定是先把新闻读懂，然后找到它的主题，最后根据主题的不同对新闻进行分类但计算机根本读不懂新闻，计算机本质上只能做快速计算，为了让计算机能“算〞新闻，就要求：1〕把文字的新闻变成可以计算的一组数字2〕然后再设计一个算法来计算两篇新闻的相似度特征向量相似性度量新闻的特征向量如何用特征向量来表示一篇新闻？幸福的家庭都是相似的，不幸的家庭各有各的不幸。托尔斯泰?安娜∙卡列尼娜?同一类新闻用词都是相似的，不同类的新闻用词各不相同。词例如词汇表有64000个词，其编号分别为1,2,...,64000统计一篇新闻中各词的出现次数，按照对应词在词汇表中的位置依次排列，就得到一个向量编号汉字词1阿2啊3阿斗4阿姨......789服装......64000做作新闻的特征向量编号汉字词10253043......78910......640002新闻的特征向量如果单词表中的某个词在新闻中没有出现，对应的值为零，那这64000个数，组成一个64000维的特征向量，我们就用这个特征向量来表示一篇新闻。这样，新闻就可以拿来“计算〞了(0,0,0,3,0,...,28,0,0,0,3)(1,0,5,0,0,...,10,0,20,0,1)(0,0,3,5,0,...,0,8,0,12,0)新闻的特征向量一篇新闻里有很多词，有些词表达的语义重要，有些相对次要。例如“的、地、得、了〞这些助词，这些词对确定新闻主题没有帮助，反而会影响分类结果，因此在计算时应忽略它们。这些词称为停用词(stopwords)新闻长短不同，同一个词在长新闻中出现的次数一般要比在短新闻中出现的次数多，因此需要根据新闻长度，对词的出现次数进行归一化，即用词的出现次数除以总词数，称为词频(TermFrequency，简称TF)，然后用词频来替代特征向量中相对应的计数值例如某新闻有1000个词，其中“原子能〞和“应用〞分别出现了2次和5次，那么它们的词频分别为0.002和0.005词频的简单应用关键字提取：对于一篇新闻，提取出词频最高的前N个词，即可作为该篇新闻的关键字度量新闻和查询的相关性：直接使用各个关键字在新闻中出现的总词频。例如，查询“原子能应用〞，“原子能〞在新闻A中的词频是0.035，“应用〞在新闻A中的词频是0.020，那么这个查询和新闻A的相关性为0.035+0.020=0.055主要内容文本分类及文档的特征向量余弦相似度使用分类算法进行文本分类逆文档频率TF-IDFTF-IDF的信息论依据浅谈中文分词度量两篇新闻的相似度设两篇新闻的特征向量为x(x1,x2,...)和y(y1,y2,...)，它们的欧氏距离为d(x,y)：那么它们的相似度可以表示为余弦相似度向量实际上是多维空间中从原点出发的有向线段。余弦相似度使用向量的夹角来衡量两个向量的相近程度，两个向量的夹角越小表示越相似，夹角越大表示越不相似。余弦相似度根据向量的点积公式假设新闻X和新闻Y的特征向量为(x1,x2,...)和(y1,y2,...)，那么它们的夹角余弦为因向量中每一个变量都是正数，因此余弦的取值在0和1之间，即夹角在0度到90度之间。当余弦等于1时，夹角为0，两新闻完全相同；当余弦为0时，夹角为90度，两新闻毫不相关。当夹角余弦越接近1时，夹角越小，说明两新闻越相似。余弦相似度练习A(1,1)B(2,2)利用余弦相似度C(3,3)similarity(A,B)=similarity(A,C)=11利用欧氏距离similarity(A,B)=similarity(A,C)=应用：论文分组1998年，约翰∙霍普金斯大学的教授雅让斯基是某国际会议的程序委员会主席，需要把提交上来的几百篇论文发给各个专家去评审决定是否录用。为保证评审的权威性，需要把每个研究方向的论文交给这个方向最有权威的专家。虽然论文作者自己给定了论文方向，但范围太广，没有什么指导意义。雅让斯基当然没有时间浏览这近千篇论文，于是就让他的学生实现了一个算法，大致思想为：1.计算所有论文间两两的余弦相似性，把相似性大于一个阈值的论文合并成一个小类。2.把每个小类中所有论文作为一个整体，计算小类的特征向量，再计算小类之间两两的余弦相似性，然后合并成大一点的小类。3.不断重复上述过程，类别越来越少，而每个类越来越大。当子类的数量比较少时，就会看清楚这些子类了。(聚类的思想)主要内容文本分类及文档的特征向量余弦相似度使用分类算法进行文本分类逆文档频率TF-IDFTF-IDF的信息论依据浅谈中文分词分类系统设计的根本步骤传感器特征提取特征选择分类器设计系统评估模式应用：新闻分类准备事先标记好类别的新闻训练数据将新闻转化为特征向量，训练分类算法使用分类算法对未知新闻进行自动分类应用：新闻分类-使用kNN计算每训练数据中每条新闻和待分类新闻的相似度找出和待分类新闻相似度最大的k条新闻找到的k条新闻中哪个类别占的最多，待分类新闻就属于哪个类别应用：新闻分类-使用朴素贝叶斯w为新闻特征向量，Ci为新闻类别。对于一条新闻，找到使P(Ci|w)最大的新闻分类，将新闻划分到该类别中P(Ci)的计算：将训练样本中属于Ci类的新闻条数除以用于训练的所有新闻条数P(w|Ci)的计算：P(w|Ci)=P(w0|Ci)P(w1|Ci)P(w2|Ci)...P(wn|Ci)其中w0,w1..为词汇表中的词，P(wk|Ci)为词wk在Ci类中的出现概率(词频或权重)主要内容文本分类及文档的特征向量余弦相似度使用分类算法进行文本分类逆文档频率TF-IDFTF-IDF的信息论依据浅谈中文分词逆文档频率(TF-IDF)以“原子能的应用〞为例，去除停用词“的〞后，它可以分成“原子能〞和“应用〞两个词但“应用〞是个非常通用的词，而“原子能〞是个很专业的词。看到“原子能〞时，或多或少能了解到新闻的主题，而看到“应用〞一词，对新闻主题根本上还是一无所知。因此，相比于“应用〞，“原子能〞对新闻主题确实定更有帮助，“原子能〞的权重应当比“应用〞高。而单纯的词频(TF)并不能反映这种权重上的差异逆文档频率(TF-IDF)因此，需要对每一个词设置一个权重，权重的设定必须满足两个条件：(1)一个词预测主题的能力越强，权重越大，反之权重越小(2)停用词的权重为零逆文档频率(TF-IDF)容易发现，如果一个关键词只在少量的新闻中出现，通过它就容易确定新闻主题，它的权重也就应该大反之，如果一个词在大量新闻中出现，通过它仍然难以确定新闻主题，因此它的权重就应该小概括的讲，假定一个关键词w在Dw条新闻中出现过，那么Dw越大，w的权重越小，反之那么权重越大逆文档频率(TF-IDF)在信息检索中，使用最多的权重是逆文档频率(InverseDocumentFrequency，简称IDF)其中D为所有文档(新闻)数量，Dw为出现关键词w的文档数量假定新闻条数是10亿，停用词“的〞在所有新闻中都出现，即Dw=10亿，那它的IDF=log(10亿/10亿)=log(1)=0假设“原子能〞在200万条新闻中出现，即Dw=200万，那么它的权重IDF=log(10亿/200万)=log(500)=9.96假设“应用〞在5亿条新闻中出现，即Dw=5亿，那么它的权重IDF=log(10亿/5亿)=log(2)=1逆文档频率(TF-IDF)将一个词的TF乘上其IDF，即为其TF-IDF权重，即TF-IDF=TF∙IDFTF-IDF中的-是连字符，不是代表相减主要内容文本分类及文档的特征向量余弦相似度使用分类算法进行文本分类逆文档频率TF-IDFTF-IDF的信息论依据浅谈中文分词信息熵(Entropy)我们常说信息很多，或信息很少，但却很难说清楚信息到底有多少比方一本50多万字的?史记?有多少信息量？或一套莎士比亚全集有多少信息量？这个问题几千年来都没有人给出很好的解答，直到1948年，香农(ClaudeShannon)在他著名的论文“通信的数学原理〞中提出了信息熵的概念，才解决了信息的度量问题，并且量化出信息的作用信息熵(Entropy)一条信息的信息量和它的不确定性有着直接的关系比方，要搞清楚一件非常不确定的事，或是我们一无所知的事情，就需要了解大量信息。相反，如果我们对某件事已经有了较多了解，那么不需要太多信息就能把它搞清楚从这个角度看，信息量就等于不确定性的多少如何量化信息的度量呢？信息熵(Entropy)假设我错过了一个有32支球队参加的足球赛，赛后我问一个知道比赛结果的观众“哪支球队是冠军〞？他不愿意直接告诉我，而让我猜，每猜一次，他要收一元钱才肯告诉我是否猜对，那我需要付多少钱才能知道谁是冠军呢？我可以把球队编号，从1到32，然后问“冠军球队在1-16号中吗？〞，假设他告诉我猜对了，我就接着问“冠军在1-8号中吗？〞，假设他说猜错了，那我就知道冠军在9-16号中。这样只要5次，我就能知道哪支球队是冠军当然，香农不是用钱，而是用比特(bit)来度量信息量，在上例中，这条消息的信息量是5比特信息量的比特数和所有可能情况的对数有关，例如本例中，信息量=log(球队数)，即5=log(32)。Why?信息熵(Entropy)实际上可能不需要5次就能猜出谁是冠军，因为一些强队得冠的可能性更高，因此第一次猜测时可以把少数几支强队分成一组，其它球队分成另一组，然后猜冠军球队是否在那几支强队中这样，也许三次或四次就能猜出结果。因此，当每支球队夺冠的可能性(概率)不等时，这条信息的信息量比5比特少香农指出，它的准确信息量应该是p1,p2,...,p32分别是这32支球队夺冠概率，香农把它称作信息熵，单位为比特；可以算出，当32支球队夺冠概率相同时，对应的信息熵为5比特。信息熵(Entropy)对于任意一个随机变量X(比方夺冠球队)，它的熵定义为变量的不确定性越大，熵也就越大，把它搞清楚所需要的信息量也就越大TF-IDF的信息论依据衡量一个词的权重时，一个简单的方法就是用每个词的信息量作为它的权重，即其中N是整个语料库大小，是个可以省略的常数，因此公式可简化成TF-IDF的信息论依据但是这个公式有个缺陷，两个词出现的频率TF相同，一个是某特定文章中的常见词，而另一个是分散在多篇文章中，显然第一个词有更高的分辨率，它的权重应更大。更好的权重公式应反映出关键词的分辨率。TF-IDF的信息论依据如果做一些理想的假设，(1)每个文献大小根本相同，均为M个词，即(2)一个关键词一旦在文献中出现，不管次数多少，奉献都等同，这样一个词在文献中要么出现c(w)=TF(w)/Dw次，要么出现零次。注意，c(w)<MTF-IDF中的-是连字符，不是代表相减。TF-IDF的信息论依据因为c(w)<M，因此M/c(w)>1，故等式右边第二项大于零，且c(w)越大，第二项越小，c(w)越小，第二项越大可以看到，一个词的信息量I(w)越大，TF-IDF值越大；出现频率相同的一个词，越分散在多篇文档中，其平均出现次数越小，第二项越大，TF-IDF值越小；反之，越集中出现，其平均出现次数越大，第二项越小，TF-IDF值越大。这些结论和信息论完全相符。主要内容文本分类及文档的特征向量余弦相似度使用分类算法进行文本分类逆文档频率TF-IDFTF-IDF的信息论依据浅谈中文分词分词在对文档转化为特征向量时，需要对文档内容进行分词，将文档转化成一个个词条(token)的列表，这个过程称为词条化(tokenization)Thequickbrownfoxjumpsoverthelazydogthequickbrownfoxjumpoverthelazydogquickbrownfoxjumpoverlazydog中文分词中国航天官员应邀到美国与太空总署官员开会中国/航天/官员/应邀/到/美国/与/太空/总署/官员/开会？中文分词最简单的方法是“查字典〞：从左向右扫描句子，遇到字典里有的词就标识出来，遇到复合词就找最长匹配(如“上海大学〞)，遇到不认识的字串就分割成单字词(有限状态机)中/国航天官员中国/航天官员中国/航/天官员中国/航天/官员中国/航天/官/员中国/航天/官员/中文分词这个简单的方法可以解决七八成的分词问题，但毕竟太简单，稍微复杂一点的情况就无能为力了。例如当遇到有二义性(有双重理解意思)的分割时：开展中国家开展/中国/家X上海大学城书店上海大学/城/书店X北京大学生北京大学/生X中文分词能否让计算机像人类一样去理解自然语言？例如，句子“徐志摩喜欢林徽因。〞可分为主语、动词短语(即谓语)和句号三局部，对每个局部进行分析，得到如下的语法分析树〔编译器〕中文分词分析它采用的文法规那么通常被计算机科学家和语言学家称为重写规那么(RewritingRules)，具体到上例，重写规那么为：句子->主语谓语句号主语->名词谓语->动词名词短语名词短语->名词名词->徐志摩动词->喜欢名词->徐志摩句号->。中文分词20世纪80年代以前，自然语言处理工作中的文法规那么都是人写的。科学家原以为随着对自然语言语法概括得越来越全面，同时计算能力的提高，这种方法可以逐步解决自然语言理解的问题。但这种想法很快遇到了麻烦。从前面例子中的图可看出，句法分析很啰唆：一个短短的句子居然分析出这么一个复杂的树结构，居然需要八条文法规那么。中文分词一个更真实的句子：美联储主席本∙伯南克昨天告诉媒体7000亿美元的救助资金将借给上百家银行、保险公司和汽车公司。这个句子依然符合“句子→主语谓语句号〞的文法规那么：主语【美联储主席本∙伯南克】||动词短语【昨天告诉媒体7000亿美元的救助资金将借给上百家银行、保险公司和汽车公司】||句号【。】接下来可进一步划分，例如主语“美联储主席本∙伯南克〞分解成两个名词短语“美联储主席〞和“本∙伯南克〞，对动词短语也可做同样分析。但这样生成的语法分析树非常大且复杂。基于规那么的自然语言处理的缺陷想通过文法规那么覆盖哪怕20%真实语句，文法规那么的数量至少几万条，语言学家几乎已经是来不及写了这些文法规那么写到后来甚至会出现矛盾，为了解决这