文本挖掘（Text mining）基础- Presentation Transcript1.文本挖掘（Text Mining ）技术基础出家如初, 成佛有余 20 10 年10 月2.议题o搜索引擎文本挖掘基础o文本挖掘基础3.搜索引擎技术不单纯只是搜索o搜索引擎技术除了实现Web 搜索、图片搜索外，还能够干什么？o搜索引擎核心技术有哪些？▪网络爬虫▪中英文分词▪排序算法▪Text Mining 相关▪海量数据存储▪分布式计算▪等等4.Google 的十大核心技术o Google 的十大核心技术：▪分布式基础设施：▪GFS 、Chubby 、Protocol Buffer▪分布式大规模数据处理▪MapReduce、Sawzall▪分布式数据库技术：▪BigTable、Sharding▪数据中心优化技术▪数据中心高温化、12V 电池、服务器整合▪参考：探索Google App Engine 背后的奥秘5.搜索引擎技术使用场景：内容相似度o新闻站点的“您可能也喜欢”▪本质为：两篇文档/ 图书/ 商品内容的相似度6.搜索引擎技术使用场景：内容分类、聚类7.通用搜索引擎系统流程8.Lucene系统架构9.Lucene系统架构10.搜索引擎中文本挖掘典型问题o在搜索引擎中关于文本挖掘的典型问题▪怎样得到一篇文章的关键词、主题？▪怎样用计算机可识别的数学公式来表征一篇文档▪怎样处理查询关键词与文档的相似度▪怎样度量两篇文档的相似度？11.信息检索模型o信息检索模型（Information Retrieval Model ）是指如何对查询和文档进行表示，然后对它们进行相似度计算的框架和方法。
o信息检索模型本质上是对相关度建模。
12.信息检索模型o信息检索模型o信息检索模型可以表示为一个四元组的模型框架o IR = <D, Q, R(q,d)>o D 是文档表示，Q 是查询表示，R(q ，d ) 是一个排序函数o索引词(Index Term)o索引词是能代表文档内容的特征，可以是字、词、短语或者某种语义单元，关键词(key words) 可以看成索引词的一种。
o文档表示成多个索引词的集合o索引词的权重(Weight)o不同索引词作用是不同的，通过权重加以区分13.信息检索模型的分类o从所使用的数学方法上分：o基于集合论的IR 模型(Set Theoretic models)o布尔模型o基于模糊集的模型、扩展布尔模型o基于代数论的IR 模型(Algebraic models)o向量空间模型o LSI （隐性语义检索）模型o神经网络模型o基于概率统计的IR 模型(Probabilistic models)o概率模型o回归模型、语言模型建模IR 模型、推理网络模型、信任度网络模型14.布尔模型（Boolean Model ）o布尔模型建立在经典的集合论和布尔代数的基础上o在布尔模型中查询和文档均表示为索引词(“ 是否存在” ) 的布尔表达式，通常表示成D(t 1 ，t 2 ，⋯，t i ) 的形式。
o布尔操作( 关系) : 与(AND) 或(OR) 非(NOT)o相似度计算：查询布尔表达式和所有文档的布尔表达式进行匹配，匹配成功的文档的得分为 1 ，否则为0 。
15.布尔模型的优缺点o优点：▪简单、易理解、易实现▪现代很多搜索引擎中仍然包含布尔模型的思想，如Google 的高级检索o缺点▪只能严格匹配，文献要么相关、要么不相关，并没有一个相关级别的概念，因此很难有好的检索效果▪构造布尔逻辑式不容易，对于一般用户而言，很难用AND 、OR 、NOT 运算符的结合来准确地表达一个检索语句，标引词的简单组配不能完全反映用户的实际需要；▪检索输出完全依赖于布尔提问与文献的匹配情况，很难控制输出量的大小▪结果不能按用户定义的重要性排序输出，用户只能从头到尾浏览输出结果才能知道哪些文献更适合自己的需要16.概率模型17.概率模型优缺点o优点▪采用严格的数学理论为依据，为人们提供了一种数学理论基础来进行检索决策；PubMed 的related articles 。
▪采用相关反馈原理▪在其中没有使用用户难以运用的布尔逻辑方法；▪在操作过程中使用了词的依赖性和相互关系。
o缺点：▪计算复杂度大, 不适合大型网络▪参数估计难度较大▪条件概率值难估计▪系统的检索性能提高不明显，需与其他检索模型结合18.词频（TF ）、文件频率（DF ）o假如要搜索一个词语t i 在文件集合{d 1 ,d 2 ,...,d n } 出现的频率，则有两部分的重要信息：o t i 在某篇文档d j 中出现的次数，称为此词语在此篇文档的频率（词频）：TF(Term Frequency) o文档集合{d 1 ,d 2 ,...,d n } 中包含t i 的文档个数，称为此词语在文档集合{d 1 ,d 2 ,...,d n } 的文件频率：DF （Document Frequency ）19.TF(Term Frequency):20.IDF(inverse document frequency)21.TF-IDFo把TF(Term Frequency) 、IDF(inverse document frequency) 这两项结合起来，对单词t 和文档d ，定义o TF-IDF(t,d) = TF(t,d) * IDF(t)o TF-IDF 的作用：▪某一特定文件内的高词语频率，以及该词语在整个文件集合中的低文件频率，可以产生出高权重的TF-IDF 。
▪因此，TF-IDF 倾向於过滤掉常见的词语，保留重要的词语。
22.TF-IDF 的例子o摘自：http://bit.ly/cbDyIK23.向量空间模型VSM （Vector Space Model ）o VSM 的基本思路：用向量模型来标识一篇文档或一个查询？o把文档看作一系列索引词(Inex Term) 组成，每一个词都有一个权重(Term weight) ，不同的索引词根据自己在文档中的权重来影响文档相关性的打分计算。
o在向量空间模型中可以把所有此文档中词(term) 的权重(term weight) 看作一个向量，并以此权重向量来表征文档。
查询和文档都可转化成索引词及其权重组成的向量24.文档- 索引词词矩阵(Doc-Term Matrix)o n 篇文档，m 个索引词词构成的矩阵Am*n ，每列可以看成每篇文档的向量表示，同时，o每行也可以可以看成标引词的向量表示25.向量表示26.相似度计算o文档和查询条件之间的相关程度( 即相似度) 可由它们各自向量在向量空问中的相对位置来决定。
相似度计算函数有很多种，较常用的是两个向量夹角的余弦函数。
o文档和查询条件的相似度值由以下公式获得：dj q27.向量相似度算法o余弦相似性（cosine-based similarity ）o相关相似性（Pearson 相关系数）o修正的余弦相似性（adjusted-cosine similarity ）28.文档相似性o其中：▪Di 为文档i▪Wij是第i 个特征项在第j 个文档向量中的权值29.Vector Space Model30.向量空间模型例子摘自：http://bit.ly/cbDyIK31.Inverted Files32.Inverted Files33.Word-Level Inverted File34.o In Lucene, a TermFreqVector is a representation of all of the terms and term counts in a specific Field of a Document instanceo As a tuple:o termFreq = <term, term count D >▪<fieldName, <…,termFreq i , termFreq i+1 ,…>>o As Java:▪public String getField();▪public String[] getTerms();▪public int[] getTermFrequencies();Lucene Term Vectors (TV) Parallel Arrays35.Lucene Term Vectors (TV)▪Field.TermVector.NO: 不保存term vectors▪Field.TermVector.YES: 保存term vectors▪Field.TermVector.WITH_POSITIONS: 保存term vectors.( 保存值和token 位置信息)▪Field.TermVector.WITH_OFFSETS: 保存term vectors.( 保存值和Token 的offset)▪Field.TermVector.WITH_POSITIONS_OFFSETS: 保存term vectors.( 保存值和token 位置信息和Token 的offset)36.Lucene Scoring 评分机制37.Lucene Scoring 评分机制o参考org.apache.lucene.search.Similarityo /java/3_0_2/scoring.html▪http://bit.ly/bq7xNh38.Lucene Scoring 核心类图39.LuceneMoreLikeThiso Lucene的contrib包中提供了MoreLikeThis、MoreLikeThisQuery包，很容易实现“您可能也喜欢”的功能▪org.apache.lucene.search.similar.MoreLikeThis▪org.apache.lucene.search.similar.MoreLikeThisQueryo参考：http :// bit.ly/dpUQAPo String indexDir = "d:/index";o FSDirectory directory = FSDirectory.open(new File(indexDir));o IndexReader reader = IndexReader.open(directory);o IndexSearcher searcher = new IndexSearcher(reader);o intnumDocs = reader.maxDoc();o MoreLikeThismlt = new MoreLikeThis(reader); // #Ao mlt.setFieldNames(new String[] {"title", "author"});o mlt.setMinTermFreq(1); // #Bo mlt.setMinDocFreq(1)o..40.Lucene作为Linkedin的推荐引擎o参考：LinkedIn Signal - a look under the hood41.分词：中文特征词(Term) 的粒度o Character ，字：中o Word ，词：中国o Phrase ，短语：中国人民银行o Concept ，概念▪同义词：开心高兴兴奋▪相关词cluster ，word cluster ：葛非/ 顾俊o N-gram ，N 元组：中国国人人民民银银行o某种规律性模式：比如某个window 中出现的固定模式10/30/1042.分词：主要的分词方法o最大匹配法（Maximum Matching method, MM 法）：选取包含6-8 个汉字的符号串作为最大符号串，把最大符号串与词典中的单词条目相匹配，如果不能匹配，就削掉一个汉字继续匹配，直到在词典中找到相应的单词为止。