文本挖掘

1文本挖掘–信息提取（IE）参考JaimeCarbonell教授讲稿2文本中信息的提取•出发点：从文本中挖掘信息，而不是简单的词项匹配•上下文无关实体的提取–Context-FreeEntityExtraction•基于规则的实体提取•关系提取（RelationalExtraction）•在eBusiness中的应用3TextMining(1)•文本本来是给人读的，不是计算机•大多数信息以文本形式存储–100timesasmuchonlinetextasonlineDBs•HTML网页是带有结构标记的文本（带来机会和挑战）•数据挖掘操作的是数据表(i.e.numbers,fixedfields,adherencetodatamodels).4TextMining(2)•许多应用，我们需要从文本到数据库表的转换器•一般的自然语言理解问题依然太困难•但我们能够解决简单些、同时也有用的子问题吗？•Yes！1.对文本按照主题分类2.并且从文本中或者标记结构文字中提取某些信息是可能的。5TextMining(3)ComponentsofTextMining（基本策略）•按照主题（话题，topics）分类–今天稍提一下，以后专门有一讲•从分类的文本中提取事实（本讲主要内容）•在数据库或者提取的事实中进行信息挖掘6TextCategorization(文本分类)Definition：给文档或者网页贴上“标签”（label）•这些标签可能是像Yahoo类型那样的主题–e.g.finance,sports,newsworldasiabusiness“•还可能是题材种类（genre）e.g.editorials“,movie-reviews“,news•标签还可以是二元的e.g.interesting-to-menot-interesting-to-me“要点：“类”是一个很宽的概念，由应用目标定7TextCategorization(2)Methods•人工指定(asinYahoo)•按照事先确定的简单规则(asinReuters)–通常是事先建立一个“词语的布尔组合”和类别的对应关系。当一篇文档包含的词语满足了那个布尔组合，则就认定它为相应的类别。8TextCategorization(3)机器学习法•k-最近邻法（简单，有效，以后介绍）•决策树归纳（最常用的方法）•支持向量机法（Support-vectormachines），时髦的方法9命名实体的识别（NamedEntityIdentification）目的（回答下面这样的问题）：•在这100篇文章中提到了哪些人？•在这2000篇网页中提到了哪些地点？•在这些专利申请表中提到了哪些公司？•今年的消费者报告评估了什么产品？•注意，我们并不是给定X，问哪些文档含有X。此时需要有一定的语法分析能力（词汇表+有限状态机）。10NamedEntityIdentificationI(2)ExamplePresidentClintondecidedtosendspecialtradeenvoyMickeyKantortothespecialAsianeconomicmeetinginSingaporethisweek.Ms.XuemeiPeng,tradeministerfromChina,andMr.HidetoSuzukifromJapan’sMinistryofTradeandIndustrywillalsoattend.Singapore,whoishostingthemeeting,willprobablyberepresentedbyitsforeignandeconomicministers.TheAustralianrepresentative,Mr.Langford,willnotattend,thoughnoreasonhasbeengiven.Thepartieshopetoreachaframeworkforcurrencystabilization.11NamedEntityIdentificationI(3)ExtractedNamedEntities(NEs)PEOPLEPLACES__________________________________________PresidentClintonSingaporeMickeyKantorJapanMs.XuemeiPengChinaMr.HidetoSuzukiAustraliaMr.Langford12NamedEntityIdentificationII有限状态机Finite-StateMachines有限状态接收器FiniteStateAcceptor(FSA)的定义•FSA是一个有向图•它有一个起始节点，startnode•它至少有一个接收节点，acceptingnodes•有一个输入源（例如，stringofwords）•在节点上可能输出YESorNO13Finite-StateMachines(2)DefinitionofFiniteStateAcceptor(FSA)•节点之间的链接标记和输入项的匹配–精确匹配，exact-matchlinkslabelse.g.ChinamatchingonlyChina–通配符（？）匹配e.g.?matches100orChinaor...–特征匹配（feature-match）e.g.CAPmatchesanycapitalizedword–表成员匹配（list-membership，例如称呼）e.g.ifHON-LIST:=(Mr,Ms,Dr,President,...)itwouldmatchanyofthosewordsintheinput14NamedEntityIdentificationIIIFinite-StateMachines有限状态变换器，AFiniteStateTransducer(FST)•带有变量绑定的FSA•在输出“NO”或“YES”的同时给出特定变量的绑定，从而可以给出对具体实体的识别e.g.YESfirstnameHidetolastnameSuzuki15FiniteStateAcceptor(FSA)StartStateAcceptStateCAPCAPHON-LIST16FiniteStateTransducer(FST)CAPHON-LISTCAPHON:=FirstName:=LastName:=17带有角色信息的命名实体(1)Motivation•知道命名实体的角色常常是有用的，例如：–谁参加了经济会议？–谁主持了这个会议？–在这经济会上讨论了谁的情况？–这次经济会议谁缺席了？18Role-SituatedNamedEntities(2)如何确定实体的角色？•一个FSM不够了，考虑用三个FSMs–left-context-FSAentity-FSMright-context-FSA•其中左边和右边的上下文帮助确定中间实体的角色19Role-SituatedNamedEntities(3)例子（根据左右内容的含义）Ifright-context=?not(attend|participate)Thenentity.role=ABSENTIfleft-context=(meet|meeting)(in|at)Thenentity.role=HOST20关系信息的提取(1)目的想知道谁对谁做了什么。21关系信息提取(2)ExampleJohnSnellreportingforWallStreet.TodayFlexiconInc.announcedatenderofferforSupplyhouseLtd.for$30pershare,representinga30%premiumoverFriday’sclosingprice.FlexiconexpectstoacquireSupplyhousebyQ42001withoutproblemsfromfederalregulators22关系信息提取(3)此时，提取系统可以看成是若干FSMs构成的一个模板，其设计根据具体应用确定[Corporate-acquisition（公司收购）[acquirercompany-FSMr-acquirer-FSM][acquireel-acquiree-FSMcompany-FSM)][share-pricemoney-FSMr-stock-FSM][datel-event-date-FSMdate-FSM]]23关系信息提取(4)输出就是FSM的事例化[Corporate-acquisition[acquirerFlexiconInc.][acquireeSupplyhouseLtd.][share-price30USD][dateQ42001]]24事实提取：当前水平(1)观察•实体=实体+角色=关系模板–所提取信息的丰富性不断增加•但还是不等于是自然语言理解–因为只是提取了预先确定的信息类型25FactExtraction:StateoftheArt(2)它们已经有些用处•例如可以产生用于数据库的数据AcquirerAcquireeSh.priceYear__________________________________FlexiconLogi-truck181999FlexiconSupplyhouse302001buy.comreel.com102000............26FactExtraction:StateoftheArt(3)目前常用的技术途径•手工建立若干提取规则•手工建立FSTs•从预先选定的例子中进行基于特征的训练(NaiveBayes,DecisionTrees)•隐马尔科夫模型（HiddenMarkoffModels,HMM）•带有反馈驱动调整的FSTs27文本提取的应用财经•Email的自动答复–例如，要答复这样的email：WhatisthebalanceofaccountN007623013?•首先，将这email分类成balance-request类别（预先需要学习或者定规则）•然后提取账号，用账号去数据库查余额28文本提取的应用(2)财经•银行指令的模板填充–e.g.Pleasetransfer100,000USDfromN007623013tocheckingaccountA011129081tomorrow“–首先将它分类为“资金转移”类别29文本提取的应用(3)财经•然后提取出：[account-transferfromN00762301toA01112908amount100,000date??]•然后雇员检查模板，纠正错误，并添加其他必须的信息（例如，也许系统不会解释“tomorrow”，于是要人工给出具体日期）30文本提取的应用II(1)信息服务•BBS上公布的所有讲座通知提取时间/地点/讲者/题目首先也还是得到一段文字的“讲座通知”类别•email消息中公布的会议通知提取时间/参加人/地点31文本提取的大规模Web应用•建立工作职位招聘大全的数据库–扫描各种网站，通过分类，确定哪些网页是关于工作机会的描述–提取公司/日期/工资/等级/…–将提取的信息填入数据库中•建立所有网上个人简历的数据库–扫描网站，通过分类，确定哪些是个人简历–然后提取关键的内容，放到数据库的相应字段中，姓名/特长/…•中关村人才招聘网采用的是什么技术？32文本提取的应用企业情报•从竞争对手的网站上提取关键数据–新推出的产品–在价格，促销方面的变化等•提取竞争对手客户的关键数据–据此采用相应的措施来争取客户33关于论文阅读的安排•每人一篇（我指定）•两周内先交一个简短报告–论文的主要内容和贡献–可能的改进之处（进一步发展之处）•我检查后有选择的安排进一步的研讨和报告