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