文本分类全解

,单击此处编辑母版文本样式,第二级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,单击此处编辑母版标题样式,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,文本分类全解,主要内容,文本分类及文档的特征向量,余弦相似度,使用分类算法进展文本分类,逆文档频率 TF-IDF,TF-IDF的信息论根据,浅谈中文分词,本节内容来源于吴军博士?数学之美?,文本分类,文本分类,所谓新闻的分类，或者更广义的讲任何文本的分类，无非是要把相似的新闻放到同一类中,假设让编辑来对新闻分类，他一定是先把新闻读懂，然后找到它的主题，最后根据主题的不同对新闻进展分类,但计算机根本读不懂新闻，计算机本质上只能做快速计算，为了让计算机能“算新闻，就要求：,1把文字的新闻变成可以计算的一组数字,2然后再设计一个算法来计算两篇新闻的相似度,特征向量,相似性度量,新闻的特征向量,如何用特征向量来表示一篇新闻？,幸福的家庭都是相似的，不幸的家庭各有各的不幸。,托尔斯泰?安娜卡列尼娜?,同一类新闻用词都是相似的，不同类的新闻用词各不一样。,词,例如,词汇表,有64000个词，其编号分别为1, 2, ., 64000,统计,一篇新闻中,各词的出现次数,，按照对应词在词汇表中的,位置依次排列,，就得到一个,向量,编号,汉字词,1,阿,2,啊,3,阿斗,4,阿姨,.,.,789,服装,.,.,64000,做作,新闻的特征向量,编号,汉字词,1,0,2,5,3,0,4,3,.,.,789,10,.,.,64000,2,新闻的特征向量,假设单词表中的某个词在新闻中没有出现，对应的值为零，那这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),新闻的特征向量,一篇新闻里有很多词，有些词表达的语义重要，有些相对次要。,例如“的、地、得、了这些助词，这些词对确定新闻主题没有帮助，反而会影响分类结果，因此在计算时应忽略它们。这些词称为停用词 (stop words),新闻长短不同，同一个词在长新闻中出现的次数一般要比在短新闻中出现的次数多，因此需要根据新闻长度，对词的出现次数进展归一化，即用词的出现次数除以总词数，称为词频 (Term Frequency，简称TF)，然后用词频来替代特征向量中相对应的计数值,词频的简单应用,关键字提取,：对于一篇新闻，提取出,词频最高,的前N个词，即可作为该篇新闻的,关键字,度量新闻和查询的相关性,：直接使用各个关键字在新闻中出现的总词频。,主要内容,文本分类及文档的特征向量,余弦相似度,使用分类算法进展文本分类,逆文档频率 TF-IDF,TF-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) =,1,1,利用欧氏间隔,similarity(A, B) =,similarity(A, C) =,应用：论文分组,1998年，约翰霍普金斯大学的教授雅让斯基是某国际会议的程序委员会主席，需要把提交上来的几百篇论文发给各个专家去评审决定是否录用。为保证评审的权威性，需要把每个研究方向的论文交给这个方向最有权威的专家。,虽然论文作者自己给定了论文方向，但范围太广，没有什么指导意义。雅让斯基当然没有时间阅读这近千篇论文，于是就让他的学生实现了一个算法，大致思想为：,1. 计算所有论文间两两的余弦相似性，把相似性大于一个阈值的论文合并成一个小类。,2. 把每个小类中所有论文作为一个整体，计算小类的特征向量，再计算小类之间两两的余弦相似性，然后合并成大一点的小类。,3. 不断重复上述过程，类别越来越少，而每个类越来越大。当子类的数量比较少时，就会看清楚这些子类了。(聚类的思想),主要内容,文本分类及文档的特征向量,余弦相似度,使用分类算法进展文本分类,逆文档频率 TF-IDF,TF-IDF的信息论根据,浅谈中文分词,分类系统设计的根本步骤,传感器,特征提取,特征选择,分类器设计,系统评估,形式,应用：新闻分类,准备事先标记好类别的新闻训练数据,将新闻转化为特征向量，训练分类算法,使用分类算法对未知新闻进展自动分类,应用：新闻分类 - 使用kNN,计算每训练数据中每条新闻和待分类新闻的相似度,找出和待分类新闻相似度最大的k条新闻,找到的k条新闻中哪个类别占的最多，待分类新闻就属于哪个类别,应用：新闻分类 - 使用朴素贝叶斯,w为新闻特征向量，C,i,为新闻类别。,对于一条新闻，找到使P(C,i,|w)最大的新闻分类，将新闻划分到该类别中,P(Ci)的计算：,将训练样本中属于Ci类的新闻条数除以用于训练的所有新闻条数,P(w|C,i,)的计算：,P(w|C,i,)=P(w,0,|C,i,)P(w,1,|C,i,)P(w,2,|C,i,).P(w,n,|C,i,),其中w,0,w,1,.为词汇表中的词，,P(w,k,|Ci)为词w,k,在C,i,类中,的出现概率(词频或权重),主要内容,文本分类及文档的特征向量,余弦相似度,使用分类算法进展文本分类,逆文档频率 TF-IDF,TF-IDF的信息论根据,浅谈中文分词,逆文档频率 (TF-IDF),以“原子能的应用为例，去除停用词“的后，它可以分成“原子能和“应用两个词,但“应用是个非常通用的词，而“原子能是个很专业的词。看到“原子能时，或多或少能理解到新闻的主题，而看到“应用一词，对新闻主题根本上还是一无所知。,因此，相比于“应用，“原子能对新闻主题确实定更有帮助，“原子能的权重应当比“应用高。而单纯的词频(TF)并不能反映这种权重上的差异,逆文档频率 (TF-IDF),因此，需要对每一个词设置一个权重，权重的设定必须满足两个条件：,(1) 一个词预测主题的才能越强，权重越大，反之权重越小,(2) 停用词的权重为零,逆文档频率 (TF-IDF),容易发现，假设一个关键词只在少量的新闻中出现，通过它就容易确定新闻主题，它的权重也就应该大,反之，假设一个词在大量新闻中出现，通过它仍然难以确定新闻主题，因此它的权重就应该小,概括的讲，假定一个关键词w在Dw条新闻中出现过，那么Dw越大，w的权重越小，反之那么权重越大,逆文档频率 (TF-IDF),在信息检索中，使用最多的权重是,逆文档频率,(Inverse Document Frequency，简称IDF),其中D为所有文档(新闻)数量，D,w,为出现关键词w的文档数量,假定新闻条数是10亿，停用词“的在所有新闻中都出现，即Dw=10亿，那它的 IDF=log(10亿/10亿)=log(1)=0,假设“应用在5亿条新闻中出现，即Dw=5亿，那么它的权重IDF=log(10亿/5亿)=log(2)=1,逆文档频率 (TF-IDF),将一个词的TF乘上其IDF，即为其 TF-IDF 权重，即,TF-IDF = TF,IDF,TF-IDF中的-是连字符，,不是代表相减,主要内容,文本分类及文档的特征向量,余弦相似度,使用分类算法进展文本分类,逆文档频率 TF-IDF,TF-IDF的信息论根据,浅谈中文分词,信息熵 (Entropy),我们常说信息很多，或信息很少，但却很难说清楚信息到底有多少,比方一本50多万字的?史记?有多少信息量？或一套莎士比亚全集有多少信息量？,这个问题几千年来都没有人给出很好的解答，直到1948年，香农(Claude Shannon)在他著名的论文“通信的数学原理中提出了信息熵的概念，才解决了信息的度量问题，并且量化出信息的作用,信息熵 (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) ,主语谓语句号,主语,-,名词,谓语,-,动词 名词短语,名词短语,-,名词,名词,-,徐志摩,动词,-,喜欢,名词,-,徐志摩,句号,-,。,中文分词,20世纪80年代以前，自然语言处理工作中的文法规那么都是人写的。科学家原以为随着对自然语言语法概括得越来越全面，同时计算才能的进步，这种方法可以逐步解决自然语言理解的问题。,但这种想法很快遇到了费事。从前面例子中的图可看出，句法分析很啰唆：一个短短的句子居然分析出这么一个复杂的树构造，居然需要八条文法规那么。,中文分词,一个更真实的句子：,美联储主席本,伯南克昨天告诉媒体7000亿美元的救助资金将借给上百家银行、保险公司和汽车公司。,这个句子仍然符合“句子 主语谓语句号的文法规那么：,主语【美联储主席本,伯南克】|动词短语【昨天告诉媒体7000亿美元的救助资金将借给上百家银行、保险公司和汽车公司】|句号【。】,接下来可进一步划分，例如主语“美联储主席本伯南克分解成两个名词短语“美联储主席和“本伯南克，对动词短语也可做同样分析。,但这样生成的语法分析树非常大且复杂。,基于规那么的自然语言处理的缺陷,想通过文法规那么覆盖哪怕20%真实语句，文法规那么的数量至少几万条，语言学家几乎已经是来不及写了,这些文法规那么写到后来甚至会出现矛盾，为理解决这些矛盾，还要说明各个规那么特定的使用环境(上下文有关文法),这种现象也出如今我们学习外语的时候，即使学了10年的英语语法，也不能涵盖全部的英语,即使可以写出涵盖所有自然语言现象的语法规那么集合，用计算机解析它也是相当困难的。自然语言在演变过程中，产生了词义和上下文相关的特征。因此它的文法是上下文有关文法，不同于程序语言使用的上下文无关文法。,程序语言是一门真正的语言，但比自然语言简单、严密(呆板),利用统计语言模型分词,20世纪90年代以前，海内外不少学者试图用一些文法规那么来解决分词的二义性问题，都不是很成功。,1990年前后，当时在清华大学电子工程系工作的郭进博士用统计语言模型成功解决了分词二义性问题，将汉语分词的错误率降低了一个数量级。,郭进是中国大陆自觉地用统计语言模型方法进展自然语言处理的第一人。,利用统计语言模型分词,假定一个句子S可以有几种分词方法，简单起见，假定有以下三种：,A,1,A,2,A,3,.,A,k,B,1,B,2,B,3,.,B,m,C,1,C,2,C,3,.,C,n,其中A,1, A,2, .B,1, B,2, .C,1, C,2, . 都是汉语的词。,不同分词方法可产生不同数量的词串。,最好的一种分词方法应该保证分完词后这个句子出现的概率最大，,也就是说，假设第一种是最好的分法，那么,P(A,1, A,2, . A,k,) P(B,1, B,2, .B,m,),P(A,1, A,2, . A,k,) P(C,1, C,2, .C,n,),计算每种分词方法分词后句子出现的概率，并找出其中概率最大的，就能找到,最好的分词方法,。,谢谢！,