文本挖掘(Text-Mining)技术基础课件

1文本挖掘（文本挖掘（Text Text MiningMining）技术基础）技术基础出家如初,成佛有余 http:/2010年10月议题议题n搜索引擎文本挖掘基础搜索引擎文本挖掘基础n文本挖掘基础文本挖掘基础2搜索引擎技术不单纯只是搜索搜索引擎技术不单纯只是搜索n搜索引擎技术除了实现搜索引擎技术除了实现WebWeb搜索、图片搜索外，还能搜索、图片搜索外，还能够干什么？够干什么？n搜索引擎核心技术有哪些？搜索引擎核心技术有哪些？网络爬虫网络爬虫中英文分词中英文分词排序算法排序算法Text MiningText Mining相关相关海量数据存储海量数据存储分布式计算分布式计算等等等等3GoogleGoogle的十大核心技术的十大核心技术nGoogleGoogle的的十大核十大核心技心技术：术：分布式基础设施分布式基础设施：lGFSGFS、ChubbyChubby、Protocol BufferProtocol Buffer分布式大规模数据处分布式大规模数据处理理lMapReduceMapReduce、SawzallSawzall分布式数据库技术分布式数据库技术：lBigTableBigTable、ShardingSharding数据中心优化技数据中心优化技术术l数数据中心高温据中心高温化、化、12V12V电电池、服池、服务器整务器整合合参考：参考：探探索索Google App EngineGoogle App Engine背后的奥秘背后的奥秘4搜索引擎技术使用场景：内容相似度搜索引擎技术使用场景：内容相似度n新闻站点的新闻站点的“您可能也喜欢您可能也喜欢”本质为：两篇文档本质为：两篇文档/图书图书/商品内容的相似度商品内容的相似度5搜索引擎技术使用场景：内容分类、聚类搜索引擎技术使用场景：内容分类、聚类67通用搜索引擎系统流程通用搜索引擎系统流程 Lucene Lucene 系统架构系统架构8Lucene Lucene 系统架构系统架构9搜索引擎中文本挖掘典型问题搜索引擎中文本挖掘典型问题n在搜索引擎中关于文本挖掘的典型问题在搜索引擎中关于文本挖掘的典型问题怎样怎样得到得到一篇文章的关键词、主题？一篇文章的关键词、主题？怎样用怎样用计算计算机可识别的数学公式来表征一篇文档机可识别的数学公式来表征一篇文档怎样处理查询关键词与文档的相似度怎样处理查询关键词与文档的相似度怎样度量两篇文档的相似度？怎样度量两篇文档的相似度？10信息检索模型信息检索模型n信息检索模型（信息检索模型（Information Retrieval ModelInformation Retrieval Model）是指如何对查询和文档进行表示，然后对它们进行是指如何对查询和文档进行表示，然后对它们进行相似度计算的框架和方法。相似度计算的框架和方法。n信息检索模型本质上是对相关度建模。信息检索模型本质上是对相关度建模。11信息检索模型信息检索模型n信息检索模信息检索模型型 信息检索模型可以表示为一个四元组的模型框架信息检索模型可以表示为一个四元组的模型框架IR=IR=D D是文档表示，是文档表示，Q Q是查询表示，是查询表示，R(q R(q，d)d)是一个排序函数是一个排序函数n索引词索引词(Index Term)(Index Term)索索引词是能代表文档内容的特征，可以是字、词、短语或者引词是能代表文档内容的特征，可以是字、词、短语或者某种语义单元，关键词某种语义单元，关键词(key words)(key words)可以看成索引词的一种。可以看成索引词的一种。文档表示成多个索引词的集合文档表示成多个索引词的集合n索引词的权重索引词的权重(Weight)(Weight)不不同索引词作用是不同的，通过权重加以区分同索引词作用是不同的，通过权重加以区分12信息检索模型的分类信息检索模型的分类 从所使用的数学方法上分：从所使用的数学方法上分：n基于集合论的基于集合论的IRIR模型模型(Set Theoretic models)(Set Theoretic models)布尔模型布尔模型基于模糊集的模型、扩展布尔模型基于模糊集的模型、扩展布尔模型n基于代数论的基于代数论的IRIR模型模型(Algebraic models)(Algebraic models)向量空间模型向量空间模型LSILSI（隐性语义检索（隐性语义检索）模型）模型神经网络模型神经网络模型n基于概率统计的基于概率统计的IRIR模型模型(Probabilistic models)(Probabilistic models)概率模型概率模型回归模型、语言模型建模回归模型、语言模型建模IRIR模型、推理网络模型、信任度网络模型模型、推理网络模型、信任度网络模型13布尔模型（布尔模型（Boolean ModelBoolean Model）n布尔模型建立在经典的集合论和布尔代数的基础上布尔模型建立在经典的集合论和布尔代数的基础上n在布尔模型中查询和文档均表示为索引词在布尔模型中查询和文档均表示为索引词(“是否存是否存在在”)的布尔表达式，通常表示成的布尔表达式，通常表示成D(t D(t 1 1，t t 2 2，t t i i)的形式。的形式。n布尔操作布尔操作(关系关系):):与与(AND)(AND)或或(OR)(OR)非非(NOT)(NOT)n相似度计算：查询布尔表达式和所有文档的布尔表达相似度计算：查询布尔表达式和所有文档的布尔表达式进行匹配，匹配成功的文档的得分为式进行匹配，匹配成功的文档的得分为1 1，否则为，否则为0 0。14布尔模型的优缺点布尔模型的优缺点n优点：优点：简单、易理解、易实现简单、易理解、易实现现代很多搜索引擎中仍然包含布尔模型的思想，如现代很多搜索引擎中仍然包含布尔模型的思想，如GoogleGoogle的高级检索的高级检索n缺点缺点只能严格匹配只能严格匹配，文献要么相关、要么不相关，并没有一个相关级别的，文献要么相关、要么不相关，并没有一个相关级别的概念，因此很难有好的检索效果概念，因此很难有好的检索效果构造布尔逻辑式不容易，对于一般用户而言，很难用构造布尔逻辑式不容易，对于一般用户而言，很难用ANDAND、OROR、NOTNOT运运算符的结合来准确地表达一个检索语句，标引词的简单组配不能完全算符的结合来准确地表达一个检索语句，标引词的简单组配不能完全反映用户的实际需要；反映用户的实际需要；检索输出完全依赖于布尔提问与文献的匹配情况，很难控制输出量的检索输出完全依赖于布尔提问与文献的匹配情况，很难控制输出量的大小大小结果不能按用户定义的重要性排序输出，用户只能从头到尾浏览输出结果不能按用户定义的重要性排序输出，用户只能从头到尾浏览输出结果才能知道哪些文献更适合自己的需要结果才能知道哪些文献更适合自己的需要15概率模型概率模型n16概率模型优缺点概率模型优缺点n优点优点采用严格的数学理论为依据，为人们提供了一种数学理论采用严格的数学理论为依据，为人们提供了一种数学理论基础来进行检索决策；基础来进行检索决策；PubMedPubMed的的related articles related articles。采用相关反馈原理采用相关反馈原理在其中没有使用用户难以运用的布尔逻辑方法；在其中没有使用用户难以运用的布尔逻辑方法；在操作过程中使用了词的依赖性和相互关系。在操作过程中使用了词的依赖性和相互关系。n缺点：缺点：计算复杂度大计算复杂度大,不适合大型网络不适合大型网络参数估计难度较大参数估计难度较大条件概率值难估计条件概率值难估计系统的检索性能提高不明显，需与其他检索模型结合系统的检索性能提高不明显，需与其他检索模型结合17词频（词频（TFTF）、文件频率（）、文件频率（DFDF）n假如要搜索一个词语假如要搜索一个词语t ti i 在文件集合在文件集合dd1 1 ,d,d2 2 ,.,d,.,dn n 出现的频率，则有两部分的重要信息：出现的频率，则有两部分的重要信息：nt ti i 在某篇在某篇文档文档d dj j 中出现的次数，称为此词语在此篇中出现的次数，称为此词语在此篇文档的频率（词频）：文档的频率（词频）：TF(Term Frequency)TF(Term Frequency)n文档集合文档集合dd1 1 ,d,d2 2 ,.,d,.,dn n 中包含中包含t ti i 的文档个数，的文档个数，称为此词语在文档集合称为此词语在文档集合dd1 1 ,d,d2 2 ,.,d,.,dn n 的文件频率：的文件频率：DFDF（Document Frequency Document Frequency）18TF(Term Frequency):TF(Term Frequency):n19IDF(inverse document frequency)IDF(inverse document frequency)n20TF-IDFTF-IDFn把把TF(Term Frequency)TF(Term Frequency)、IDF(inverse document IDF(inverse document frequency)frequency)这两项结合起来，对单词这两项结合起来，对单词t t和文档和文档d d，定，定义义TF-IDF(t,d)=TF(t,d)*IDF(t)TF-IDF(t,d)=TF(t,d)*IDF(t)nTF-IDFTF-IDF的作用：的作用：某一特定文件内的高词语频率，以及该词语在整个文件某一特定文件内的高词语频率，以及该词语在整个文件集合中的低文件频率，可以产生出高权重的集合中的低文件频率，可以产生出高权重的TF-IDFTF-IDF。因此，因此，TF-IDFTF-IDF倾向於过滤掉常见的词语，保留重要的词倾向於过滤掉常见的词语，保留重要的词语。语。21TF-IDFTF-IDF的例子的例子摘自：摘自：http:/bit.ly/cbDyIKhttp:/bit.ly/cbDyIK22向量空间模型向量空间模型 VSMVSM（Vector Space ModelVector Space Model）nVSMVSM的基本思路：用向量的基本思路：用向量模型模型来标识一篇文档或一个查询？来标识一篇文档或一个查询？n把把文档看作一系列索引词文档看作一系列索引词(Inex Term)(Inex Term)组成，每一个词都有组成，每一个词都有一个权重一个权重(Term weight)(Term weight)，不同，不同的索引词根的索引词根据自己在文档中据自己在文档中的权重来影响文档相关性的打分计算的权重来影响文档相关性的打分计算。n在在向量空间模型中可以把所有此文档中词向量空间模型中可以把所有此文档中词(term)(term)的权重的权重(term weight)(term weight)看作一个向量，并以此权重向量看作一个向量，并以此权重向量来表来表征文档征文档。查询和文档都可转化成索引词及其权重组成的向量查询和文档都可转化成索引词及其权重组成的向量 23文档文档-索引词词矩阵索引词词矩阵(Doc-Term Matrix)(Doc-Term Matrix)n n篇文档，篇文档，m m个索引词词构成的矩阵个索引词词构成的矩阵Am*nAm*n，每列可以看，每列可以看成每篇文档的向量表示，同时，成每篇文档的向量表示，同时，每行也可以可以看成标引词的向量表示每行也可以可以看成标引词的向量表示24向量表示向量表示n25相似度计算相似度计算n文档和查询条件之间的相关程度文档和查询条件之间的相关程度(即相似度即相似度)可由它们可由它们各自向量在向量空问中的相对位置来决定。相似度计各自向量在向量空问中的相对位置来决定。相似度计算函数有很多种，较常用的是两个向量夹角的余弦函算函数有很多种，较常用的是两个向量夹角的余弦函数。数。n文档和查询条件的相似度值由以下公式获得：文档和查询条件的相似度值由以下公式获得：djq26向量相似度算法向量相似度算法n余弦相似性（余弦相似性（cosine-based similaritycosine-based similarity）n相关相似性（相关相似性（PearsonPearson相关系数相关系数 ）n修正的余弦相似性（修正的余弦相似性（adjusted-cosine adjusted-cosine similaritysimilarity）27文档相似性文档相似性n其中：其中：DiDi为文档为文档i iWijWij是第是第i i个特征项在第个特征项在第j j个文档向量中的权值个文档向量中的权值28Vector Space ModelVector Space Model29向量空间模型例子向量空间模型例子30摘自：摘自：http:/bit.ly/cbDyIKhttp:/bit.ly/cbDyIKInverted FilesInverted FilesInverted FilesInverted FilesWord-Level Inverted FileWord-Level Inverted FilenIn Lucene,a TermFreqVector is a representation of all In Lucene,a TermFreqVector is a representation of all of the terms and term counts in a specific Field of a of the terms and term counts in a specific Field of a Document instanceDocument instancenAs a tuple:As a tuple:termFreq=fieldName,nAs Java:As Java:public String getField();public String getTerms();public int getTermFrequencies();Lucene Term Vectors(TV)Lucene Term Vectors(TV)Parallel ArraysLucene Term Vectors(TV)Lucene Term Vectors(TV)nField.TermVector.NO:Field.TermVector.NO:不保存不保存term vectorsterm vectorsnField.TermVector.YES:Field.TermVector.YES:保存保存term vectorsterm vectorsnField.TermVector.WITH_POSITIONS:Field.TermVector.WITH_POSITIONS:保存保存term vectors.(term vectors.(保存保存值和值和tokentoken位置信息位置信息)nField.TermVector.WITH_OFFSETS:Field.TermVector.WITH_OFFSETS:保存保存term vectors.(term vectors.(保存值保存值和和TokenToken的的offset)offset)nField.TermVector.WITH_POSITIONS_OFFSETS:Field.TermVector.WITH_POSITIONS_OFFSETS:保存保存term term vectors.(vectors.(保存值和保存值和tokentoken位置信息和位置信息和TokenToken的的offset)offset)35Lucene Scoring Lucene Scoring 评分机制评分机制36Lucene Scoring Lucene Scoring 评分机制评分机制n参参考考org.apache.lucene.search.Similarity org.apache.lucene.search.Similarity httphttp:/lucene.apache.org/java/3_0_2/scoring.html:/lucene.apache.org/java/3_0_2/scoring.htmlhttphttp:/bit.ly/bq7xNh:/bit.ly/bq7xNh37Lucene ScoringLucene Scoring核心类图核心类图 38Lucene MoreLikeThisLucene MoreLikeThisnLucene Lucene 的的contribcontrib包中提供了包中提供了MoreLikeThis MoreLikeThis、MoreLikeThisQueryMoreLikeThisQuery包，很容易实现包，很容易实现“您可能也喜欢您可能也喜欢”的功能的功能org.apache.lucene.search.similar.MoreLikeThisorg.apache.lucene.search.similar.MoreLikeThisorg.apache.lucene.search.similar.MoreLikeThisQueryorg.apache.lucene.search.similar.MoreLikeThisQueryn参考：参考：httphttp:/:/bit.ly/dpUQAPbit.ly/dpUQAP String String indexDir=d:/indexindexDir=d:/index;FSDirectory directory=FSDirectory.open(new File(indexDir);FSDirectory directory=FSDirectory.open(new File(indexDir);IndexReader reader=IndexReader.open(directory);IndexReader reader=IndexReader.open(directory);IndexSearcher searcher=new IndexSearcher(reader);IndexSearcher searcher=new IndexSearcher(reader);int numDocs=reader.maxDoc();int numDocs=reader.maxDoc();MoreLikeThis mlt=new MoreLikeThis(reader);/#A MoreLikeThis mlt=new MoreLikeThis(reader);/#A mlt.setFieldNames(new String title,author);mlt.setFieldNames(new String title,author);mlt.setMinTermFreq(1);/#B mlt.setMinTermFreq(1);/#B mlt.setMinDocFreq(1 mlt.setMinDocFreq(1).39Lucene Lucene 作为作为Linkedin Linkedin 的推荐引擎的推荐引擎n参考：参考：LinkedIn Signal-a look under the hoodLinkedIn Signal-a look under the hood402024/6/2541分词：中文特征词分词：中文特征词(Term)(Term)的粒度的粒度nCharacterCharacter，字：中，字：中nWordWord，词：中国，词：中国nPhrasePhrase，短语：中国人民银行，短语：中国人民银行nConceptConcept，概念，概念同义词：开心同义词：开心 高兴高兴 兴奋兴奋相关词相关词clustercluster，word clusterword cluster：葛非：葛非/顾俊顾俊nN-gramN-gram，N N元组：中国元组：中国 国人国人 人民人民 民银民银 银行银行n某种规律性模式：比如某个某种规律性模式：比如某个windowwindow中出现的固定中出现的固定模式模式分词：主要的分词方法分词：主要的分词方法n最大匹配法（最大匹配法（Maximum Matching method,MMMaximum Matching method,MM法）：选取包含法）：选取包含6-86-8个汉字的个汉字的符号串作为最大符号串，把最大符号串与词典中的单词条目相匹配，如果符号串作为最大符号串，把最大符号串与词典中的单词条目相匹配，如果不能匹配，就削掉一个汉字继续匹配，直到在词典中找到相应的单词为止。不能匹配，就削掉一个汉字继续匹配，直到在词典中找到相应的单词为止。匹配的方向是从右向左。匹配的方向是从右向左。n逆向最大匹配法（逆向最大匹配法（Reverse Maximum method,RMMReverse Maximum method,RMM法）：匹配方向与法）：匹配方向与MMMM法法相反，是从左向右。实验表明：对于汉语来说，逆向最大匹配法比最大匹相反，是从左向右。实验表明：对于汉语来说，逆向最大匹配法比最大匹配法更有效。配法更有效。n双向匹配法（双向匹配法（Bi-direction Matching method,BMBi-direction Matching method,BM法）：比较法）：比较MMMM法与法与RMMRMM法的分词结果，从而决定正确的分词。法的分词结果，从而决定正确的分词。n最佳匹配法（最佳匹配法（Optimum Matching method,OMOptimum Matching method,OM法）：将词典中的单词按它法）：将词典中的单词按它们在文本中的出现频度的大小排列，高频度的单词排在前，频度低的单词们在文本中的出现频度的大小排列，高频度的单词排在前，频度低的单词排在后，从而提高匹配的速度。排在后，从而提高匹配的速度。n联想联想-回溯法（回溯法（Association-Backtracking method,ABAssociation-Backtracking method,AB法）：采用联想和法）：采用联想和回溯的机制来进行匹配。回溯的机制来进行匹配。4243分词：英文分词分词：英文分词n一般采用一般采用keyword,无需分词无需分词,单词之间有空格分开。单词之间有空格分开。nstop words：指指文文档档中中出出现现的的连连词词，介介词词，冠冠词词等等并并无无太太大大意意义义的的词词。例例如如在在英英文文中中常常用用的的停停用用词词有有the，a,it等等；在在中中文文中中常常见见的的有有“是是”，“的的”，“地地”等。等。n索索引引词词（标标引引词词，关关键键祠祠）:可可以以用用于于指指代代文文档档内内容容的的预预选选词词语语,一一般般为为名名词或名词词组。词或名词词组。n词根提取词根提取StemmingStemming：将单词：将单词“缩减缩减”为词根形式。在算法上为词根形式。在算法上StemmingStemming主要是采主要是采取某种固定的算法来做这种缩减，如去除取某种固定的算法来做这种缩减，如去除“s s”，去除，去除“inging”加加“e e”，将，将“ationalational”变为变为“ateate”，将，将 “tionaltional”变为变为“tiontion”例如：例如：cars=car,countries=countrycars=car,countries=country，interesting=interestinteresting=interestLemmatizationLemmatization：将单词：将单词“转变转变”为词根形式。在算法上为词根形式。在算法上LemmatizationLemmatization主要是采用保存某种字典的方式做这种转变，例如：主要是采用保存某种字典的方式做这种转变，例如：例如：例如：drove=drive,car=automobiledrove=drive,car=automobile，ps-2=PS/2 ps-2=PS/2参考：参考：http:/bit.ly/cgl3Ai搜索引擎的搜索引擎的Text MiningText Mining价值价值n搜索引擎本身对文本的搜索引擎本身对文本的Vector Space ModelVector Space Model、TF-IDFTF-IDF、ScroingScroing、SimilaritySimilarity等较好的支持等较好的支持n如果能够将协同行为（标签、收藏、购买、打分等）也转化为如果能够将协同行为（标签、收藏、购买、打分等）也转化为Vector Space ModelVector Space Model，则也可以利用搜索引擎来实现推荐引擎，则也可以利用搜索引擎来实现推荐引擎n搜索引擎技术中最为有趣的不是搜索本身，而是搜索引擎技术中最为有趣的不是搜索本身，而是Text MiningText Miningn因此搜索引擎不单纯只是用于因此搜索引擎不单纯只是用于“搜索搜索”的引擎，还可以可以作的引擎，还可以可以作为为Text MiningText Mining基于内容（基于内容（Content-BasedContent-Based）的推荐引擎）的推荐引擎新闻自动聚合新闻自动聚合.44议题议题n搜索引擎文本挖掘基础搜索引擎文本挖掘基础n文本挖掘基础文本挖掘基础45文本挖掘能做些什么文本挖掘能做些什么 n基于内容的推荐系统（基于内容的推荐系统（Content-BasedContent-Based）n新闻自动聚合新闻自动聚合n互联网舆情、非法内容发布互联网舆情、非法内容发布n垃圾邮件的过滤垃圾邮件的过滤n企业竞争情报系统企业竞争情报系统n知识库知识库n自动问答自动问答n机器翻译机器翻译n46文本挖掘模型结构示意图文本挖掘模型结构示意图47Text MiningText Mining相关技术相关技术48机器学习机器学习 数理统计数理统计 自然语言处理自然语言处理 数据库技术数据库技术文本分类文本分类文本聚类文本聚类文本数据处理文本数据处理文本数据压缩文本数据压缩信息访问信息访问 （信息检索、信息浏览、（信息检索、信息浏览、信息过滤、信息报告信息过滤、信息报告 ）知识发现知识发现（数据分析、数据预测（数据分析、数据预测 ）文本信息提取文本信息提取文本挖掘的关键技术文本挖掘的关键技术n文本结构分析文本结构分析n文本摘要文本摘要n文本分类文本分类n文本聚类文本聚类n文本关联分析文本关联分析n分布分析分布分析n趋势预测趋势预测49一些一些Text MiningText Mining相关的开源项目相关的开源项目n数据挖掘相关：数据挖掘相关：WekaWeka、R-ProjectR-Project、KnimeKnime、RapidMinerRapidMiner、OrangeOrange 等等n文本挖掘相关：文本挖掘相关：OpenNLPOpenNLP、LingPipeLingPipe、FreeLingFreeLing、GATEGATE 、Carrot2Carrot2 等，具体可以参考等，具体可以参考LingPipeLingPipes s CompetitionCompetitionn推荐引擎相关：推荐引擎相关：Apache MahoutApache Mahout、Duine frameworkDuine framework、Singular Value Decomposition(SVD)Singular Value Decomposition(SVD)n搜索引擎相关：搜索引擎相关：LuceneLucene、SolrSolr、SphinxSphinx、Hibernate Hibernate SearchSearch等等50参考资料参考资料系列文章（很棒的网站，强烈推荐）系列文章（很棒的网站，强烈推荐）http:/bit.ly/cBOfAyhttp:/bit.ly/cBOfAyhttp:/http:/bit.ly/c1juhibit.ly/c1juhihttp:/http:/bit.ly/cbDyIKbit.ly/cbDyIKhttp:/http:/bit.ly/cgU0zEbit.ly/cgU0zEn数学之美系列数学之美系列http:/http:/bit.ly/aVOsSdbit.ly/aVOsSdn北大北大文本挖掘技术文本挖掘技术课程课程http:/http:/bit.ly/9MaJ2Jbit.ly/9MaJ2JnLingPipeLingPipe总结的各种总结的各种Text MiningText Mining工具工具http:/http:/bit.ly/bSjEmRbit.ly/bSjEmR5152请提宝贵意见！