文本挖掘重点

MINING文本挖掘（TextMining）报告人：张忠平2002/03/18提纲文本挖掘的起源文本挖掘的过程特征建立特征集缩减知识模式提取模型评价国内外研究状况文本挖掘的起源文本数据库（web文档数据）半结构化数据（semistructuredata）信息检索技术（informationretrieval）Web文本挖掘的过程Web文本挖掘的一般处理过程特征的建立特征集的缩减学习与知识模式的提取知识模式模式质量的评价文档集文本特征的建立定义：文本特征指的是关于文本的元数据。分类：描述性特征：文本的名称、日期、大小、类型等。语义性特征：文本的作者、标题、机构、内容等。表示（文档建模）：采用向量空间模型（VSM）（矩阵）特征向量（其中ti为词条项，wi(d)为ti在d中的权值）))();...;();...;(()(,,1,1dwtdwtdwtdVnnii文本特征评价函数的数学表示信息增益（informationgain）期望交叉熵（expectedcrossentropy）互信息（mutualinformation）)()(log)()()()(log)()()(______CCCCCCiiiiiiiiPWPWPWPPWPWPWPFInfGain)()(log)()()(CCCiiiiPWPWPWPFTxtCrossEntry)()(log)()(WPWPPFTxtMutualInfoCCiiiF是对应于单词W的特征；P(W)为单词W出现的概率；P(Ci)为第i类值的出现概率；p(Ci|W)为单词W出现时属于第i类的条件概率。文本特征评价函数的数学表示(续)文本证据权（theweightofevidencefortext）词频（wordfrequency）iiiiiiWPPPWPPWPFidTxtWeightofEvCCCCC))(1)(())(1)((log)()()()()(WTFFFregP(W)为单词W出现的概率；P(Ci)为第i类值的出现概率；p(Ci|W)为单词W出现时属于第i类的条件概率；TF(W)为单词在文档集中出现的次数。文档建模词频矩阵行对应关键词t，列对应文档d向量将每一个文档视为空间向量v向量值反映单词t与文档d的关联度表示文档词频的词频矩阵d1d2d3d4d5d6t132285356915320t236190765713370t325331604822126t430140702011635文档相似度计算余弦计算法（cosinemeasure）余弦相似度定义：其中为两个文档向量，内积为标准向量点积，定义为，定义为。缺点：文档“无限”，导致矩阵增大，计算量增加vvvvvvsim212121),(vv21v1vvv111vvitii211vv21,特征集的缩减潜在语义标引（latentsemanticindexing）方法利用矩阵理论中的“奇异值分解（singularvaluedecomposition,SVD）”技术，将词频矩阵转化为奇异矩阵（K×K）潜在语义标引方法基本步骤：1.建立词频矩阵，frequencymatrix2.计算frequencymatrix的奇异值分解•分解frequencymatrix成3个矩阵U，S，V。U和V是正交矩阵（UTU=I），S是奇异值的对角矩阵（K×K）3.对于每一个文档d，用排除了SVD中消除后的词的新的向量替换原有的向量4.保存所有向量集合，用高级多维索引技术为其创建索引5.用转换后的文档向量进行相似度计算其他文本检索标引技术倒排索引（invertedindex）一种索引结构，包含两个哈希表索引表或两个B+树索引表•找出与给定词集相关的所有文档•找出与指定文档相关的所有词•易实现，但不能处理同义词和多义词问题，posting_list非常长，存储开销大签名文件（signaturefile）文档表（document_table）词表(term_table)doc_IDposting_listterm_IDposting_listDoc_1t1_1,...,t1_nTerm_1doc_1,...,doc_iDoc_2t2_1,...,t2_nTerm_2doc_1,...,doc_j┇┇┇┇Doc_ntn_1,...,tn_nTerm_ndoc_1,...,doc_n词性标注定义：将句子中兼类词的词性根据上下文唯一地确定下来。兼类词分类：同型异性异义兼类词：例如：领导（动词/名词）同型异性同义兼类词：例如：小时（量词/名词）异型同性同义兼类词：例如：电脑，计算机自动词性标注就是用计算机来自动地给文本中的词标注词类。在英语、汉语等自然语言中，都存在着大量的词的兼类现象，这给文本的自动词性标注带来了很大的困难。因此，如何排除词类歧义，是文本自动词性标注研究的关键问题。标注技术路线：基于概率统计和基于规则自动词类标注早在60年代，国外学者就开始研究英语文本的自动词类标注问题，提出了一些消除兼类词歧义的方法，建立了一些自动词性标注系统。1971年，美国布朗大学的格林（Greene）和鲁宾（Rubin）建立了TAGGIT系统，采用了86个词类标记，利用了3300条上下文框架规则（contextframerules）来排除兼类词歧义，自动标注正确率达到77%.1983年，里奇（G.Leech）和加塞德（R.Garside）等人建立了CLAWS系统，用概率统计的方法来进行自动词性标注，他们使用了133×133的词类共现概率矩阵，通过统计模型来消除兼类词歧义，自动标注的正确率达到了96%.1988年，德洛斯（S.J.DeRose）对CLAWS系统作了一些改进，利用线性规划的方法来降低系统的复杂性，提出了VOLSUNGA算法，大大地提高了处理效率，使自动词性标注的正确率达到了实用的水平。基于概率统计的CLAWS算法CLAWS是英语Constituent-LikelihoodAutomaticWord-taggingSystem（成分似然性自动词性自动标注系统）的简称，它是1983年玛沙尔(Mashall)在给LOB语料库（拥有各类文体的英国英语语料库，库容量为100万词）作自动词性标注时提出的一种算法。具体做法是：先从待标注的LOB语料库中选出来部分语料，叫做“训练集”（TrainingSet）,对训练集中的语料逐词进行词性的人工标注,然后利用计算机对训练集中的任意两个相邻标记的同现概率进行统计，形成一个相邻标记的同现概率矩阵。进行自动标注时，系统从输入文本中顺序地截取一个有限长度的词串，这个词串的首词和尾词的词性应该是唯一的，这样的词串叫做跨段(span)，记为W0,W1,W2,…,Wn,Wn+1。其中，W0和Wn+1都是非兼类词，W1,W2,…,Wn是n个兼类词。利用同现概率矩阵提供的数据来计算这个跨段中由各个单词产生的每个可能标记的概率积，并选择概率积最大的标记串作为选择路径(path),以这个路径作为最佳结果输出。VOLSUNGA算法VOLSUNGA算法对CLAWS算法的改进主要有两个方面在最佳路径的选择方面，不是最后才来计算概率积最大的标记串，而是沿着从左至右的方向，采用“步步为营”的策略，对于当前考虑的词，只保留通往该词的最佳路径，舍弃其他路径，然后再从这个词出发，将这个路径同下一个词的所有标记进行匹配，继续找出最佳的路径，舍弃其他路径，这样一步一步地前进，直到整个跨段走完，得出整个跨段的最佳路径作为结果输出。根据语料库统计出每个词的相对标注概率(RelativeTagProbability)，并用这种相对标注概率来辅助最佳路径的选择。VOLSUNGA算法大大地降低了CLAWS算法的时间复杂度和空间复杂度，提高了自动词性标注的准确率。统计方法的缺陷CLAWS算法和VOLSUNGA算法都是基于统计的自动标注方法，仅仅根据同现概率来标注词性。但是，同现概率仅只是最大的可能而不是唯一的可能，以同现概率来判定兼类词，是以舍弃同现概率低的可能性前提的。为了提高自动词性标注的正确率，还必须辅之以基于规则的方法，根据语言规则来判定兼类词。基于规则的标注基于规则的方法通过考虑上下文中的词及标记对兼类词的影响决定兼类词的词性，常常作为基于概率统计方法的补充。将统计方法和规则方法结合被认为是解决词性标注问题的最佳手段。在统计语料规模较大的情况下，结合给定最小支持度及最小可信度，首先发现大于最小支持度常用模式集，然后生成关联规则。若此规则的可信度大于给定的最小可信度，则得到词性规则。只要最小可信度定义得足够高，获得的规则就可以用于处理兼类词的情况。（规则依赖于词与词性的各种组合，挖掘过程较为复杂）基于规则的词性标注（续）主要依靠上下文来判定兼类词。这是一张白纸（“白”出现在名词”纸”之前，判定为形容词）他白跑了一趟（“白”出现在动词“跑”之前，判定为副词）词性连坐：在并列的联合结构中，联合的两个成分的词类应该相同，如果其中一个为非兼类词，另一个为兼类词，则可把兼类词的词性判定为非兼类词的词性。我读了几篇文章和报告“文章”为名词，是非兼类词，“报告”为动-名兼类词，由于处于联合结构中，故可判定“报告”为名词。清华大学计算机系黄昌宁等采用统计方法建立了一个自动词性标注系统，标注正确率达96.8%，自动标注的速度为每秒175个汉字。自动语义标注一词多义，形成了词的多义现象，自动语义标注主要是解决词的多义问题。一词多义也是自然语言中的普遍现象，但是，在一定的上下文中，一个词一般只能解释为一种语义。所谓自动语义标注，就是计算机对出现在一定上下文中的词语的语义进行判定，确定其正确的语义并加以标注。语义自动标注的方法以字义定词义词=字+…+字利用检索上下文中出现的相关词的方法来确定多义词的义项词之间的亲和程度（pen）利用上下文搭配关系来确定多义词的词义词性搭配（plan）用最大可能义项来消解多义选择多义词各个义项中使用频度最高的义项为它在文本中的当前义项。这显然不是一种科学的办法，但仍然有一定的正确率。据统计，用最大可能义项来消解多义，对于封闭文本，正确率仅为67.5%，对于开放文本，正确率更低，仅为64.8%。目前不少机器翻译系统，都采用这种最大可能义项来确定多义词的词义，，这是这些机器翻译系统译文质量低劣的主要原因之一。其他文本检索标引技术（续）签名文件（signaturefile）定义：是一个存储数据库中每一个文档的特征记录的文件方法：每一个特征对应一个固定长度的位串，一个比特位对应一个词汇，若某一位对应的词出现在文档中则，则该位置1，否则置0。S1S2•按位操作进行匹配，确定文档的相似形•可以多词对应一个比特位，来减少位串的长度，但增加搜素开销，存在多对一映射的缺点。111…1110…1学习与知识模式的提取文本源文本结构分析器文本分类器中文文本挖掘模型结构示意图分词及非用词处理特征提取名字识别日期处理数字处理文本摘要生成器用户界面用户浏览检索结果学习与知识模式的提取（续）分词定义：在中文文本的词与词之间加上空格。非用词（停用词）定义：在文本中起辅助作用的词。分类：•虚词：英文中的“a,the,of,for,with,in,at,…”中文中的“的，地，得，…”•实词：数据库会议上的论文中的“数据库”一词，视为非用词词根问题compute,computes,computed视为同一个词（变形而已）自动分词自动分词的用处：中文文本的自动检索、过滤、分类及摘要中文文本的自动校对汉外机器翻译汉字识别与汉语语音识别的后处理汉语语音合成以句子为单位的汉字键盘输入汉字简繁体转换主要的分词方法最大匹配法（MaximumMatchingmethod,MM法）：选取包含6-8个汉字的符号串作为最大符号串，把最大符号串与词典中的单词条目相匹配，如果不能匹配，就