文本挖掘技术07-过滤

1文本过滤技术杨建武Email:[e-mail]第七章：文本挖掘技术(2009)北京大学计算机科学技术研究所2信息过滤的定义¾从动态的信息流中将满足用户兴趣的信息挑选出来，用户的兴趣一般在较长一段时间内比较稳定不会改变(静态)。3信息过滤系统的特点¾新信息的产生速度很快，相对来说，人的兴趣变化比较缓慢，可以看成相对静态的和稳定的。¾信息过滤主要借用信息检索和用户建模(Usermodeling)两个领域的技术。¾用户的需求或者兴趣通常采用UserProfile建模来表示。¾新信息到来的时候，根据用户的UserProfile，有选择地挑出信息给用户。4信息过滤与信息检索¾信息过滤(IF)信息检索(IR)¾IF是可以看成广义IR的一部分，即和AdhocRetrieval相对的一种任务模式。¾IR通常采用Pull模式，而IF通常采用Push模式。¾和AdhocRetrieval相比：™IF信息源动态，用户需求(采用UserProfile来表示)相对静态；™IR信息源相对静态，用户需求(采用Query来表示)动态变化™IR可以认为面向一次性的查询而使用，而IF是面向用户的长期需求的重复使用™IF一般要关注用户建模，涉及用户隐私问题，而IR一般不需要。5信息过滤与信息分类¾IFvs.IC(Info.Classification)¾IF可以采用IC中的分类算法。¾某些场合下人们所称的“信息过滤”实际就是一个IC问题。如不经过用户Profile调整的垃圾邮件过滤。¾IC中的Category通常不会变化，相对而言，IF的UserProfile会动态调整。6信息过滤与信息提取¾信息提取(InformationExtraction,IE)是从无格式数据源中抽取相关字段的过程。比如抽取恐怖事件的时间、地点、人物等字段。¾IE中不太关注相关性，而只关注相关的字段。IF中要关注相关性。7Otherinfo.seekingprocessesProcessInformationNeedInformationSourceDataBasesDynamic&SpecificStable&StructuredAlertingStable&SpecificDynamicInformationRetrievalDynamic&SpecificStable&UnstructuredInformationFilteringStable&SpecificDynamic&UnstructuredInformationExtractionSpecificUnstructuredBrowsingBroadUnspecific8信息过滤的一些应用¾克服重复查询™网络信息是动态变化的,用户时常关心这种变化™而在搜索引擎中,用户只能不断地在网络上查询同样的内容,以获得变化的信息,这花费了用户大量的时间¾提供个性化信息服务™对不同的用户采取不同的服务策略,提供不同的服务内容。™实现“主动服务”，“信息找人”¾实现有害信息的过滤™反动言论，保护国家安全™谣言，保护社会稳定™色情内容，保护青少年身心健康9信息过滤的一些应用10信息过滤的一些应用¾搜索引擎检索结果的过滤：Google¾个人的邮件过滤¾新闻订阅和过滤¾浏览器过滤¾面向儿童的过滤系统¾面向客户的过滤系统和推荐系统11IF分类示意图12按Initiativeofoperation分¾主动(Active)的IF系统™主动搜集信息，并将相关信息发送给用户™通常采用Push操作™会造成信息过载问题，所以该系统要尽力建立精确的UserProfile。™代表系统BackWeb¾被动(Passive)的IF系统™不负责为用户搜集信息™通常用于邮件和新闻组信息过滤™代表系统GHOSTS13按Locationofoperation分¾在信息源端过滤™将用户的Profile发送给信息提供者，后者将和用户Profile匹配的信息回送给用户™用户通常需要付费，¾在过滤服务器端过滤™信息提供者将信息发送给过滤服务器™过滤服务器根据用户的Profile将匹配信息发给用户¾在用户端过滤™是一个局部过滤系统™如outlook的过滤功能。14从过滤方法分¾基于感知的过滤(Cognitivefiltering)™也称为基于内容的过滤(Content-basedfiltering)™将文档内容和用户的Profile进行相似度计算¾基于社会的过滤(Sociologicalfiltering)™也称为协同过滤(Collaborativefiltering™对某个用户的Profile进行匹配时，通过用户之间的相似度来计算Profile和文档的匹配程度™基于社会过滤的系统常常称为推荐系统(Recommendationsystems)™社会过滤常常使用用户建模(Usermodeling)及用户聚类(Userclustering)等技术。™社会过滤一般不单独使用，常常和基于内容的过滤配合使用。15基于内容的过滤与协同过滤16获取用户信息¾显式获取用户信息™用户直接填表™用关键词表达用户过滤需求™用文档集表达用户过滤需求¾隐式获取用户信息™无需用户直接参与，通过观察用户的动作行为判断用户需求™用户阅读文档的时间可以作为衡量该文档相关度的一个指标。™其他的一些用户行为——诸如用户是否保存、删除或是打印某篇文档也可以作为度量文档相关度的一个指标。17评估指标18评估指标¾正确率和召回率(Precision&Recall)¾基于统计的评价指标™相关系数(Correlation)：用户评估的结果排序和系统评估的结果排序的序相关系数¾基于集合的评价指标™Utility=(A*R+)+(B*N+)+(C*R-)+(D*N-)R+N+R-N-分别表示选出来的结果中真正相关文档的个数、不相关文档的个数、未选出来结果中相关文档的个数及不相关文档的个数，A、B、C、D是加权系数。™ASP(averagesetprecision)=P*R,当PorR=0,ASP不可用19评估指标¾面向用户(User-oriented)的指标™CoverageRatio=|Rk|/|U|=|A∩U|/|U|,Rk是用户已知的相关文档集合™Novelty=|Ru|/(|Ru|+|Rk|)，Ru是系统找出的用户未知的相关文档集合20主要方法21ATypicalAdaptiveFilteringSystem22过滤系统23数据信息分析部分¾靠近信息提供者¾从信息提供者处获得或者搜集数据¾文档分析或表示(例如：BooleanModel,VSM,etc)¾把这种表示传给过滤部分24用户模型部分¾收集用户信息(显式或者隐式的)¾构造用户profiles或者其它的用户模型(rules,VSM,documentscenter)¾把用户模型也传给过滤部分¾用户模型必须适应文档表示25过滤部分¾信息过滤系统(IFsystem)的核心¾将用户的profiles和数据项的表示相匹配¾昀终决策可能是二元的或者一个概率值(可以排序)¾相关信息被送到学习部分(feedback)26学习部分¾为了提高过滤系统的性能¾侦测用户兴趣的变化¾更新用户模型27基于查询的方法¾TheRocchioalgorithm¾Representeachdelivereddocumentbyavector™Theusualapproach:Lexicalprocessing,tf.idfweights,etc¾Representthequerybyavector™Theusualapproach¾Themodifiedqueryisaweightedaverageoftheoriginalquery,andrelevantandnon-relevantdocumentvectors(反馈学习)™Risthesetofrelevantdocuments™Risthesetofnon-relevantdocuments28基于查询的方法--Example29基于分类的方法¾Binarytextclassification:relevantvs.non-relevant¾Adaptatextclassifier™Butclassesareextremelyunbalanced…becausemostdocumentsarenotrelevant¾Systemmaximizesuserutilityinsteadofminimizingclassificationerror™Becausesomeerrorsaremoreimportantthanothers™2creditsforagooddocument,1penaltyforabaddocument30SVM31模式匹配算法32模式匹配算法¾基本的文本扫描操作--字符串搜索:™给定一个单独的模式p(搜索串)和一个输入串s,如果p是s的子串就回答yes，否则回答no¾Bruteforce串匹配算法¾快速串匹配算法™KMP算法™BM算法¾多模式匹配WM算法33BruteForce算法¾搜索串(模式):p1p2…pm¾文本串:s1s2…sn(通常nm)¾将模式和m个字符的字串sksk+1…sk+m-1进行匹配，k从1到n-m+1.¾模式要么和子串匹配，要么找到一个位置发现二者不匹配34BruteForce算法(2)35BruteForce算法(3)¾Bruteforce算法较慢™在位置4出现不匹配的现象，Bruteforce算法只移动了一位™由于前三个位置(abd)都匹配成功了，移动一个位置不可能找到“a”，因为它已经被识别为“b”™在文本的前缀被匹配成功后，你已经对文本串有了一些了解36KMP算法--基本思想¾KMP(Knuth-Morris-Pratt)匹配算法¾充分利用在一次失败匹配过程中获得的知识，避免重复比较已经知道的字符™关于文本的知识:abd?™需要在文本串中找到另一个“a”™我已经知道“a”不可能出现在下两个字符中,因此可以向右移动三个字符™需要实现对模式(pattern)中的字符进行分析37KMP--移动模式™从匹配成功的子模式中找出“能够相互匹配的昀长的前缀和后缀”™通过对模式的分析，我们知道A=B，在匹配过程中知道A=C,B=D;™移动模式，让A和D对齐，从位置i+j+1处开始匹配™如果在模式[1..j]中没有重复模式,则可以直接移动j个字符™有重复子模式的模式需要更多的时间去匹配，例如：aaaaaab38KMP算法--Shift表¾匹配失败时，决定移动多少个位置39KMP算法--性能¾Shift表可以在O(m)的时间复杂度下，通过对模式的分析而获得™m是模式长度™对每个模式字符，需要计算当匹配失效发生时应该跳过几个字符¾KMP算法花费O(m+n)的时间来解决此问题40BM(Boyer-Moore)算法¾基本想法:（模式串）从右到左匹配输入串¾比较pm和sm，如果sm不在关键词中出现，那么从s的前m个字符中任何一个字符开始的字符串都不可能和p相比配，因此可以安全地向右滑动m个字符，从而避免m-1次不必要的匹配。41BM算法--Δ1Shift表¾如果模式的长度为p并且字母表的大小为q(对小写字母来说q=26),则需要p×q的Δ1shift表42BM算法--Δ2Shift表¾p的尾部已经和s的某些子串相匹配，但再向左移动一位就不匹配了，此时使用Δ2Shift表™如果应用Δ1,只能移动一个字符™和KMP相似,可以知道已经匹配成功的模式后缀cab在模式的前面已经出现过,因此移动1个字符肯定无法匹配成功™应用移动模式，用前面已经出现的模式模式和S中相应的文本对齐Δ2=543BM算法--Δ2Shift表Ifmismatchatp[i]len=m-ifindlargestjsuchthatp[j..(j+len-1)]=p[(i+1)..m]shift2[i]=i–j+144BM算法--Δ1和Δ2¾同时计算出Δ1和Δ2，并使用昀大的shift™Δ1=7,因为不匹配的字