文本挖掘-特征提取(part1)

1文本特征提取技术杨建武Email:[e-mail]第二章：北京大学计算机科学技术研究所文本挖掘技术(2010春)2主要内容分词与词性标注文档模型与相似度计算布尔模型向量空间模型概率模型特征变换隐语义分析(LSA)3分词4语言理解系统面向不同应用有不同的形式文本分句词法分析/分词词性标注短语分析句法分析语义分析语篇分析理解一种语言另一种语言跨语言处理语篇结构语义结构……句法结构短语结构词性序列词序列句子序列自然形态5分词实例和平民主和平、民主和、平民、主提高人民生活水平提高、高人、人民、民生、生活、活水、水平大学生活象白纸大学、生活、象、白纸大学生、活象、白纸6分词基本方法基于词典的方法最大匹配法最大概率法最短路径法未登录词识别方法基于标注的方法7词语…文本挖掘课程课时…设定最大词长MaxLen=4S2=分词词表S1=“文本挖掘课程是三个课时”最大匹配法8最大匹配法示例（1）S2=“”；S1不为空，从S1左边取出候选子串W=“文本挖掘；(MaxLen=4)（2）查词表，“文本挖掘”在词表中，将W加入到S2中，S2=“文本挖掘/”，并将W从S1中去掉，此时S1=课程是三个课时；（3）S1不为空，于是从S1左边取出候选子串W=课程是三；（4）查词表，W不在词表中，将W最右边一个字去掉，得到W=课程是；（5）查词表，W不在词表中，将W最右边一个字去掉，得到W=课程（6）查词表，W在词表中，将W加入到S2中，S2=“文本挖掘/课程/”，并将W从S1中去掉，此时S1=“是三个课时”；。。。。。。。。。。。。（N-1）S2=“文本挖掘/课程/是/三/个/课时/”，此时S1=。（N）S1为空，输出S2作为分词结果，分词过程结束。9最大匹配法个个人个人崇拜个人化个数个私个体个体户个体化利用索引加速10其它基于匹配的分词方法最大匹配法（MaximumMatchingmethod）匹配的方向是从左向右。(正向最大匹配法)逆向最大匹配法（ReverseMaximummethod）匹配方向与MM法相反，是从右向左。实验表明：对于汉语来说，逆向最大匹配法比(正向)最大匹配法更有效。双向匹配法(Bi-directionMatchingmethod)比较MM法与RMM法的分词结果，从而决定正确的分词。示例：例句：长春市长春节致辞词典：长春、长春市、春节、致辞、市长正向：长春市/长春/节/致辞逆向：长春/市长/春节/致辞？11其它基于匹配的分词方法最佳匹配法（OptimumMatchingmethod,OM法）将词典中的单词按它们在文本中的出现频度的大小排列，高频度的单词排在前，频度低的单词排在后，从而提高匹配的速度。联想-回溯法（Association-Backtrackingmethod）采用联想和回溯的机制来进行匹配。12路径1：0－1－3－5路径2：0－2－3－5该走哪条路呢？最大概率法分词基本思想是：（1）一个待切分的汉字串可能包含多种分词结果（2）将其中概率最大的那个作为该字串的分词结果13最大概率法分词Max(P(W1|S),P(W2|S))?NnwwPii语料库中的总词数在语料库中的出现次数)(独立性假设，一元语法)(...)()(),...,,()(2121iiwPwPwP)()()()|()|(WPSPWPWSPSWPS:有意见分歧W1:有/意见/分歧/W2:有意/见/分歧/14最大概率法分词示例词语概率……有0.0180有意0.0005意见0.0010见0.0002分歧0.0001……P(W1)=P(有)*P(意见)*P(分歧)=1.8×10-9P(W2)=P(有意)*P(见)*P(分歧)=1×10-11P(W1)P(W2)15最短路径分词方法基本思想：在词图上选择一条词数最少的路径优点：好于单向的最大匹配方法最大匹配：独立自主/和平/等/互利/的/原则(6)最短路径：独立自主/和/平等互利/的/原则(5)缺点：同样无法解决大部分歧义结合成分子时结合成/分子/时结合/成分/子时他说的确实在理他/说/的确/实在/理他/说/的确/实/在理他/说/的/确实/在理（都是最短路径）16分词歧义分类（1）交集型歧义AB和BC都是词典中的词网球/场/:网/球场/链长：交集型歧义字段中含有交集字段的个数组合型歧义AB和A、B都是词典中的词：个人（我）个人/；（三）个/人/混合型歧义：这样的人才能经受住考验最大匹配法解决分词歧义的能力能发现部分交集型歧义•增加歧义词表，规则等知识库无法发现组合型歧义17分词歧义的四个层级（何克抗等1991,50883字语料）词法歧义：84.1%句法歧义：10.8%语义歧义：3.4%（“学生会写文章”）语用歧义：1.7%真假歧义真歧义6%•确实能在真实语料中发现多种切分形式•比如“应用于”、“地面积”假歧义94%•虽然有多种切分可能性，但在真实语料中往往取其中一种切分形式•如“挨批评”、“市政府”分词歧义分类（2）18未登录词识别数字识别命名实体识别人名地名机构名专业术语形式词、离合词看看,看一看,打听打听,高高兴兴,乐呵呵游了一会儿泳,担什么心未登录词识别的一般方法规则概率统计19数字的识别正则表达式/regularexpression识别分数，日期的正则表达式：[0-9]+(/[0-9]+)+e.g.12/215/13/2002识别百分数的正则表达式：[\+|\-]?[0-9]+.?[0-9]*%e.g.-5.9%91%识别十进制数字的正则表达式：([0-9]+,?)+(.[0-9]+|[0-9]+)*e.g.12,34520数字的识别有限状态转移网络digit=0|1|2|3|4|5|6|7|8|921序号类型属性示例1姓氏用字Surname张，王，李，…2名字禁用字Stop死，吧，呢，…3姓名用词Name王学兵，…4普通用词Common非姓名用词：翻阅，浏览，…5非普通用词None6前称谓词Left经理王学兵，省长杨铮，…7后称谓词right王学兵经理，黄旭主席，…┇┇┇┇中文姓名识别基于标注的方法基本思想：对汉字进行标注，即由字构词(组词)；不仅考虑了文字词语出现的频率信息，同时考虑上下文语境；采用机器学习的方法。字的构词位置：词首（B）词尾（E）词中（M）单字词（S）词位标注集标记单字与多字词的词位标注举例2词位B，EB，BE，BEE，……4词位B，M，E，SS，BE，BME，BMME，……基于标注的方法基本步骤：学习（训练）：所有的字根据预定义的特征进行词位特性的学习，获得一个训练模型；词位标注：对待分串的每个字进行词位标注；组合：根据词位定义获得最终的分词结果。举例：上海人均国内生产总值五千美元。上/B海/E人/B均/E国/B内/E生/B产/E总/B值/E五/B千/M美/M元/E。/S上海/人均/国内/生产/总值/五千美元/。基于标注的方法学习方法：支持向量机（SVM）最大熵（MaximumEntropy）隐马模型（HMM）最大熵隐马模型（MEMM）条件随机场（CRFs）优缺点：优点：对歧义词和未登录词的识别都具有良好的效果；缺点：训练周期较长，计算量较大。25词性标注自动词性标注就是用计算机来自动地给文本中的词标注词性。兼类词：具有多种词性的词例如：领导（动词/名词）如何排除词性歧义？标注技术路线：基于概率统计和基于规则26自动词性标注早在60年代，国外学者就开始研究英语文本的自动词类标注问题。1971年，美国布朗大学的格林（Greene）和鲁宾（Rubin）建立了TAGGIT系统，利用了3300条上下文框架规则，自动标注正确率达到77%.1983年，里奇（G.Leech）和加塞德（R.Garside）等人建立了CLAWS系统，用概率统计的方法来进行自动词性标注，他们使用了133×133的词类共现概率矩阵，通过统计模型来消除兼类词歧义，自动标注的正确率达到了96%.27基于规则的词性标注主要依靠上下文来判定兼类词。这是一张白纸•“白”出现在名词”纸”之前，判定为形容词他白跑了一趟•“白”出现在动词“跑”之前，判定为副词28基于规则的词性标注词性连坐在并列的联合结构中，联合的两个成分的词类应该相同，如果其中一个为非兼类词，另一个为兼类词，则可把兼类词的词性判定为非兼类词的词性。例：我读了几篇文章和报告•“文章”为名词，是非兼类词，“报告”为动-名兼类词，由于处于联合结构中，故可判定“报告”为名词。29)()|()()(),()|(WPTWPTPWPWTPWTP)|()()|(TWPTPWTP,...),|()...,|()|()(2101201iiitttPtttPttPTP)|()...|()|()(11201iittPttPttPTP),...,,,,...,|()...,,,|(),|()|(111112122111)|()...|()|()|(2211iitwPtwPtwPTWP二元一元出现的总次数训练语料中之后的次数出现在训练语料中111)|(iiiiitttttP出现的总次数训练语料中的次数的词性被标记为训练语料中iiiiittwtwP)|(基于统计的词性标注T:一种词性标注的组合找概率最大的T30统计方法的缺陷统计方法是根据同现概率来标注词性。但是，同现概率仅只是最大的可能而不是唯一的可能，以同现概率来判定兼类词，是以舍弃同现概率低的可能性前提的。将统计方法和规则方法结合被认为是解决词性标注问题的最佳手段。31停用词与词形变化停用词常用词：•英文：“a,the,of,for,with,in,at,…”•中文：“的，地，得，…”虚词：介词、连词等领域实词：数据库会议上的论文中的“数据库”一词，可视为停用词词根问题compute,computes,computed同一词32主要内容分词与词性标注文档模型与相似度计算布尔模型向量空间模型概率模型特征变换隐语义分析(LSA)33