搜索
1文本过滤技术杨建武Email:yangjianwu@icst.pku.edu.cn第七章：文本挖掘技术(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¾RepresenteachdelivereddocumentbyavectorTheusualapproach:Lexicalprocessing,tf.idfweights,etc¾RepresentthequerybyavectorTheusualapproach¾Themodifiedqueryisaweightedaverageoftheoriginalquery,andrelevantandnon-relevantdocumentvectors(反馈学习)RisthesetofrelevantdocumentsRisthesetofnon-relevantdocuments28基于查询的方法--Example29基于分类的方法¾Binarytextclassification:relevantvs.non-relevant¾AdaptatextclassifierButclassesareextremelyunbalanced…becausemostdocumentsarenotrelevant¾SystemmaximizesuserutilityinsteadofminimizingclassificationerrorBecausesomeerrorsaremoreimportantthanothers2creditsforagooddocument,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,因为不匹配的字