文本挖掘（Text+Mining）技术基础.ppt

1,文本挖掘（TextMining）技术基础,出家如初,成佛有余2010年10月,议题,搜索引擎文本挖掘基础文本挖掘基础,2,搜索引擎技术不单纯只是搜索,搜索引擎技术除了实现Web搜索、图片搜索外，还能够干什么？搜索引擎核心技术有哪些？网络爬虫中英文分词排序算法TextMining相关海量数据存储分布式计算等等,3,Google的十大核心技术,Google的十大核心技术：分布式基础设施：GFS、Chubby、ProtocolBuffer分布式大规模数据处理MapReduce、Sawzall分布式数据库技术：BigTable、Sharding数据中心优化技术数据中心高温化、12V电池、服务器整合参考：探索GoogleAppEngine背后的奥秘,4,搜索引擎技术使用场景：内容相似度,新闻站点的“您可能也喜欢”本质为：两篇文档/图书/商品内容的相似度,5,搜索引擎技术使用场景：内容分类、聚类,6,7,通用搜索引擎系统流程,Lucene系统架构,8,Lucene系统架构,9,搜索引擎中文本挖掘典型问题,在搜索引擎中关于文本挖掘的典型问题怎样得到一篇文章的关键词、主题？怎样用计算机可识别的数学公式来表征一篇文档怎样处理查询关键词与文档的相似度怎样度量两篇文档的相似度？,10,信息检索模型,信息检索模型（InformationRetrievalModel）是指如何对查询和文档进行表示，然后对它们进行相似度计算的框架和方法。信息检索模型本质上是对相关度建模。,11,信息检索模型,信息检索模型信息检索模型可以表示为一个四元组的模型框架IR=D是文档表示，Q是查询表示，R(q，d)是一个排序函数索引词(IndexTerm)索引词是能代表文档内容的特征，可以是字、词、短语或者某种语义单元，关键词(keywords)可以看成索引词的一种。文档表示成多个索引词的集合索引词的权重(Weight)不同索引词作用是不同的，通过权重加以区分,12,信息检索模型的分类,从所使用的数学方法上分：基于集合论的IR模型(SetTheoreticmodels)布尔模型基于模糊集的模型、扩展布尔模型基于代数论的IR模型(Algebraicmodels)向量空间模型LSI（隐性语义检索）模型神经网络模型基于概率统计的IR模型(Probabilisticmodels)概率模型回归模型、语言模型建模IR模型、推理网络模型、信任度网络模型,13,布尔模型（BooleanModel）,布尔模型建立在经典的集合论和布尔代数的基础上在布尔模型中查询和文档均表示为索引词(“是否存在”)的布尔表达式，通常表示成D(t1，t2，ti)的形式。布尔操作(关系):与(AND)或(OR)非(NOT)相似度计算：查询布尔表达式和所有文档的布尔表达式进行匹配，匹配成功的文档的得分为1，否则为0。,14,布尔模型的优缺点,优点：简单、易理解、易实现现代很多搜索引擎中仍然包含布尔模型的思想，如Google的高级检索缺点只能严格匹配，文献要么相关、要么不相关，并没有一个相关级别的概念，因此很难有好的检索效果构造布尔逻辑式不容易，对于一般用户而言，很难用AND、OR、NOT运算符的结合来准确地表达一个检索语句，标引词的简单组配不能完全反映用户的实际需要；检索输出完全依赖于布尔提问与文献的匹配情况，很难控制输出量的大小结果不能按用户定义的重要性排序输出，用户只能从头到尾浏览输出结果才能知道哪些文献更适合自己的需要,15,概率模型,16,概率模型优缺点,优点采用严格的数学理论为依据，为人们提供了一种数学理论基础来进行检索决策；PubMed的relatedarticles。采用相关反馈原理在其中没有使用用户难以运用的布尔逻辑方法；在操作过程中使用了词的依赖性和相互关系。缺点：计算复杂度大,不适合大型网络参数估计难度较大条件概率值难估计系统的检索性能提高不明显，需与其他检索模型结合,17,词频（TF）、文件频率（DF）,假如要搜索一个词语ti在文件集合d1,d2,.,dn出现的频率，则有两部分的重要信息：ti在某篇文档dj中出现的次数，称为此词语在此篇文档的频率（词频）：TF(TermFrequency)文档集合d1,d2,.,dn中包含ti的文档个数，称为此词语在文档集合d1,d2,.,dn的文件频率：DF（DocumentFrequency）,18,TF(TermFrequency):,19,IDF(inversedocumentfrequency),20,TF-IDF,把TF(TermFrequency)、IDF(inversedocumentfrequency)这两项结合起来，对单词t和文档d，定义TF-IDF(t,d)=TF(t,d)*IDF(t)TF-IDF的作用：某一特定文件内的高词语频率，以及该词语在整个文件集合中的低文件频率，可以产生出高权重的TF-IDF。因此，TF-IDF倾向於过滤掉常见的词语，保留重要的词语。,21,TF-IDF的例子,摘自：http:/bit.ly/cbDyIK,22,向量空间模型VSM（VectorSpaceModel）,VSM的基本思路：用向量模型来标识一篇文档或一个查询？把文档看作一系列索引词(InexTerm)组成，每一个词都有一个权重(Termweight)，不同的索引词根据自己在文档中的权重来影响文档相关性的打分计算。在向量空间模型中可以把所有此文档中词(term)的权重(termweight)看作一个向量，并以此权重向量来表征文档。查询和文档都可转化成索引词及其权重组成的向量,23,文档-索引词词矩阵(Doc-TermMatrix),n篇文档，m个索引词词构成的矩阵Am*n，每列可以看成每篇文档的向量表示，同时，每行也可以可以看成标引词的向量表示,24,向量表示,25,相似度计算,文档和查询条件之间的相关程度(即相似度)可由它们各自向量在向量空问中的相对位置来决定。相似度计算函数有很多种，较常用的是两个向量夹角的余弦函数。文档和查询条件的相似度值由以下公式获得：,26,向量相似度算法,余弦相似性（cosine-basedsimilarity）相关相似性（Pearson相关系数）修正的余弦相似性（adjusted-cosinesimilarity）,27,文档相似性,其中：Di为文档iWij是第i个特征项在第j个文档向量中的权值,28,VectorSpaceModel,29,向量空间模型例子,30,摘自：http:/bit.ly/cbDyIK,InvertedFiles,InvertedFiles,Word-LevelInvertedFile,InLucene,aTermFreqVectorisarepresentationofallofthetermsandtermcountsinaspecificFieldofaDocumentinstanceAsatuple:termFreq=AsJava:publicStringgetField();publicStringgetTerms();publicintgetTermFrequencies();,LuceneTermVectors(TV),LuceneTermVectors(TV),Field.TermVector.NO:不保存termvectorsField.TermVector.YES:保存termvectorsField.TermVector.WITH_POSITIONS:保存termvectors.(保存值和token位置信息)Field.TermVector.WITH_OFFSETS:保存termvectors.(保存值和Token的offset)Field.TermVector.WITH_POSITIONS_OFFSETS:保存termvectors.(保存值和token位置信息和Token的offset),35,LuceneScoring评分机制,36,LuceneScoring评分机制,参考org.apache.lucene.search.Similarity/java/3_0_2/scoring.htmlhttp:/bit.ly/bq7xNh,37,LuceneScoring核心类图,38,LuceneMoreLikeThis,Lucene的contrib包中提供了MoreLikeThis、MoreLikeThisQuery包，很容易实现“您可能也喜欢”的功能org.apache.lucene.search.similar.MoreLikeThisorg.apache.lucene.search.similar.MoreLikeThisQuery参考：http:/bit.ly/dpUQAPStringindexDir=d:/index;FSDirectorydirectory=FSDirectory.open(newFile(indexDir);IndexReaderreader=IndexReader.open(directory);IndexSearchersearcher=newIndexSearcher(reader);intnumDocs=reader.maxDoc();MoreLikeThismlt=newMoreLikeThis(reader);/#Amlt.setFieldNames(newStringtitle,author);mlt.setMinTermFreq(1);/#Bmlt.setMinDocFreq(1).,39,Lucene作为Linkedin的推荐引擎,参考：LinkedInSignal-alookunderthehood,40,2020/6/10,41,分词：中文特征词(Term)的粒度,Character，字：中Word，词：中国Phrase，短语：中国人民银行Concept，概念同义词：开心高兴兴奋相关词cluster，wordcluster：葛非/顾俊N-gram，N元组：中国国人人民民银银行某种规律性模式：比如某个window中出现的固定模式,分词：主要的分词方法,最大匹配法（MaximumMatchingmethod,MM法）：选取包含6-8个汉字的符号串作为最大符号串，把最大符号串与词典中的单词条目相匹配，如果不能匹配，就削掉一个汉字继续匹配，直到在词典中找到相应的单词为止。匹配的方向是从右向左。逆向最大匹配法（ReverseMaximummethod,RMM法）：匹配方向与MM法相反，是从左向右。实验表明：对于汉语来说，逆向最大匹配法比最大匹配法更有效。双向匹配法（Bi-directionMatchingmethod,BM法）：比较MM法与RMM法的分词结果，从而决定正确的分词。最佳匹配法（OptimumMatchingmethod,OM法）：将词典中的单词按它们在文本中的出现频度的大小排列，高频度的单词排在前，频度低的单词排在后，从而提高匹配的速度。联想-回溯法（Association-Backtrackingmethod,AB法）：采用联想和回溯的机制来进行匹配。,42,43,分词：英文分词,一般采用keyword,无需分词,单词之间有空格分开。stopwords：指文档中出现的连词，介词，冠词等并无太大意义的词。例如在英文中常用的停用词有the，a,it等；在中文中常见的有“是”，“的”，“地”等。索引词（标引词，关键祠）:可以用于指代文档内容的预选词语,一般为名词或名词词组。词根提取Stemming：将单词“缩减”为词根形式。在算法上Stemming主要是采取某种固定的算法来做这种缩减，如去除“s”，去除“ing”加“e”，将“ational”变为“ate”，将“tional”变为“tion”例如：cars=car,countries=country，interesting=interestLemmatization：将单词“转变”为词根形式。在算法上Lemmatization主要是采用保存某种字典的方式做这种转变，例如：例如：drove=drive,car=automobile，ps-2=PS/2参考：http:/bit.ly/cgl3Ai,搜索引擎的TextMining价值,搜索引擎本身对文本的VectorSpaceModel、TF-IDF、Scroing、Similarity等较好的支持如果能够将协同行为（标签、收藏、购买、打分等）也转化为VectorSpaceModel，则也可以利用搜索引擎来实现推荐引擎搜索引擎技术中最为有趣的不是搜索本身，而是TextMining因此搜索引擎不单纯只是用于“搜索”的引擎，还可以可以作为TextMining基于内容（Content-Based）的推荐引擎新闻自动聚合.,44,议题,搜索引擎文本挖掘基础文本挖掘基础,45,文本挖掘能做些什么,基于内容的推荐系统（Content-Based）新闻自动聚合互联网舆情、非法内容发布垃圾邮件的过滤企业竞争情报系统知识库自动问答机器翻译,46,文本挖掘模型结构示意图,47,TextMining相关