文本挖掘ppt课件

第八章文本挖掘文本挖掘概念关于文本挖掘名字TextMiningTextDataMiningKnowledgeDiscoveryinTextKnowledgeDiscoveryinTextualDataTextMiningismainlyaboutsomehowextractingtheinformationandknowledgefromtext对KDD定义进行扩展，文本挖掘是从大量文本数据中抽取隐含的、未知的、可能有用的信息。文本挖掘文本挖掘是数据挖掘的一个分支，它是把文本型信息源作为分析的对象，利用定量计算和定性分析的方法，从中寻找信息的结构、模型、模式等各种隐含的知识．这种知识对用户而言是新颖的，具有潜在价值。因此，文本挖掘技术的出现为文本信息的整理、分析、挖掘提供了有效手段。文本挖掘概念文本挖掘的研究意义电子化的文本数量不断增长Web中99%的可分析信息是以文本形式存在的Web网页总量超过100亿每天新增网页数千万机构内90%信息以文本形式存在数字化图书馆、数字化档案馆数字化办公传统的检索技术基于关键词的简单检索主要应用新一代搜索引擎互联网内容安全互联网非法内容分不企业知识管理企业内知识共享、企业相关外部信息CallcenternotescategorizationCRMsystems个人智能信息访问E-mailcategorizationandrouting研究难点语言难点：文本不是给计算机阅读的复杂的语言结构：语法语义更困难的：歧义多语言KDD算法难点大规模的数据集高维过适应overfitting变化的数据和知识噪声数据挖掘出的模式的可理解性文本挖掘模型结构示意图文本挖掘任务分类SearchandretrievalSemanticanalysisClusteringCategorizationFeatureextractionOntologybuildingDynamicfocus应用实例应用实例文本特征提取技术语言特征理解系统分词—实例和平民主和平、民主和、平民、主提高人民生活水平提高、高人、人民、民生、生活、活水、水平大学生活象白纸大学、生活、象、白纸、大学生、活象、白纸分词基本方法最大匹配法最大概率法最短路径分词方法难点分词歧义未登录新词最大匹配法示例S1=“计算语言学课程是三个课时”设定最大词长MaxLen=5S2=“计算语言学”、“课程”、“是”、“三”、“个”、“课时”最大匹配法示例其他基于匹配的分词方法最大匹配法逆向最大匹配法双向匹配法最佳匹配法联想-回溯法最大概率法分词基本思想是：一个待切分的汉字串可能包含多种分词结果将其中概率最大的那个作为该字串的分词结果最大概率法分词文档模型布尔模型向量空间模型经典概率模型布尔模型一种简单的检索模型，它建立在经典的集合论和布尔代数的基础上。遵循两条基本规则:每个索引词在一篇文档中只有两种状态：出现或不出现，对应权值为0或1。文档检索布尔逻辑运算布尔模型文档表示一个文档被表示为关键词的集合布尔模型文档表示优点：简单、易理解、简洁的形式化缺点：匹配准确性、信息需求能力表达不足向量空间模型向量空间模型(VectorSpaceModel,VSM)相比于布尔模型要求的准确匹配,Salton在60年代末提出的VSM模型采用了“部分匹配”的检索策略（即：出现部分索引词也可以出现在检索结果中）。向量空间模型若干独立的词项被选作索引项(indexterms)or词表vocabulary索引项代表了一个应用中的重要词项计算机科学图书馆中的索引项应该是哪些呢?向量空间模型这些索引项是不相关的un-correlated(或者说是正交的orthogonal)，形成一个向量空间vectorspace文档集一般表示向量空间中的N个文档可以用一个矩阵表示矩阵中的一个元素对应于文档中一个词项的权重。“0”意味着该词项在文档中没有意义，或该词项不在文档中出现。TFIDF举例文本：“俄罗斯频繁发生恐怖事件，俄罗斯的安全部门加大打击恐怖主义的力度。”文本间相似性计算asimilaritymeasurecanrepresentthesimilaritybetweentwodocuments,twoqueries,oronedocumentandonequery􀂙itispossibletoranktheretrieveddocumentsintheorderofpresumedimportance􀂙Asimilaritymeasureisafunctionwhichcomputesthedegreeofsimilaritybetweenapairoftextobjects􀂙Therearealargenumberofsimilaritymeasuresproposedintheliterature,becausethebestsimilaritymeasuredoesn'texist(yet!)基于概率模型的相关度查询与文档之间的相关性􀂙Okapi系统􀂙伦敦城市大学开发,􀂙20世纪80年代末问世􀂙在TREC比赛中，有不少参加者采用Okapi系统取得了很好的成绩。􀂙不过，Okapi系统不是免费的，并且不提供源代码基于VSM的相关度计算方法基于向量空间模型的常用方法􀂙欧氏距离􀂙向量内积􀂙向量夹角余弦相似度度量–内积(InnerProduct)文档D和查询式Q可以通过内积进行计算:dik是文档di中的词项k的权重，qk是查询式Q中词项k的权重对于二值向量,内积是查询式中的词项和文档中的词项相互匹配的数量对于加权向量,内积是查询式和文档中相互匹配的词项的权重乘积之和内积—举例内积的属性内积值没有界限不象概率值，要在(0,1)之间对长文档有利内积用于衡量有多少词项匹配成功，而不计算有多少词项匹配失败长文档包含大量独立词项，每个词项均多次出现，因此一般而言，和查询式中的词项匹配成功的可能性就会比短文档大。余弦(Cosine)相似度度量信息检索DocumentRetrievalisdefinedasthemachingofsomestateduserqueryagainstusefulpartsoffree-textrecords.向量空间模型向量模型的优点在于：术语权重的算法提高了检索的性能部分匹配的策略使得检索的结果文档集更接近用户的检索需求可以根据结果文档对于查询串的相关度通过CosineRanking等公式对结果文档进行排序信息检索信息检索（informationretrieval，IR），将信息按一定的方式组织和存储起来，并根据用户的需要找出有关信息的过程。发展的几个阶段手工检索(早期,情报检索)穿孔卡片检索(1950s)计算机检索(面向主题,1960s)联机检索（1970s,1980s)Web检索(1990s)信息检索信息检索：从非结构化的文档集中找出与用户需求相关的信息和其他相关技术的区别和数据库的区别数据库是结构化数据和情报检索的区别情报检索介绍如何利用情报检索工具信息检索信息检索系统主要组件建倒排索引（InvertedFile）每个文档都可以用一系列关键词来表示，从检索目的来说，这些关键词描述了文档的内容。只要找到文档，便可以找到文档中的关键词。反过来，如果按关键词建立到文档的索引，便可以根据关键词快速地检索到相关文档。信息检索系统建倒排索引具体地，关键词被存储在索引文件(indexfile)中(比如，按字母顺序存储)，对于每个关键词，都有一个指针链表，该表中的每个指针指向与该关键词相关的某个文档，所有指针链表构成置入文件(postingfile)。这种倒排文件的方法几乎被当前所有的商用IR系统所采用。信息检索系统信息检索系统信息检索系统检索性能的评估系统评价主要包括功能评价，即评价一个系统是否完成了它所侧重的目标。性能评价，主要指标是时间与空间的开销。（如：对数据检索系统的评价）信息检索系统：由于用户的查询请求本身具有模糊性，检出的结果不一定是精确答案。需要依照与查询的相关度，对结果集合的准确度进行评价。其性能评价还包括检索效果的评价。检索性能评估评估的类型实验室评估和真实环境评估，两者不同。有时，结果出入也较大。由于在实验室封闭环境下的评估具有可重复性，目前仍是主流。还有对交互查询进行评测，需要考查界面的设计、系统引导、会话持续时间等因素。检索评估基础检索评估基础:建立在测试参考集和一定的评价测度基础之上。测试集由一个文档集、一组信息查询实例、对应于每个信息查询实例的一组相关文档（由专家提供）所组成。检索策略的评估对一个给定检索策略S，对每个信息查询实例，评测由S检出的结果集合与由专家提供的相关文档集之间的相似性，量化这一指标。关于知识的组织知识的结构问题和知识是孪生的结构本身也是知识Ontologies杜威十进制系统（图书分类），国会图书馆的目录，AMS（美国数学会）的数学知识体系，美国专利内容的类别体系WebcatalogsYahoo，搜狐&Dmoz（OpenDirectory）共性的问题：人工维护中国图书馆图书分类法简表（22类）（5个大类）A马克思主义、列宁主义、毛泽东思想、邓小平理论B哲学、宗教C社会科学总论D政治、法律E军事F经济G文化、科学、教育、体育H语言、文字I文学J艺术K历史、地理N自然科学总论O数理科学和化学P天文学、地球科学Q生物科学R医药、卫生S农业科学T工业技术U交通运输V航空、航天X环境科学、安全科学Z综合性图书WebcatalogsTianwanginPku2002年Yahoo！webpageWebcatalogsYahoo！分类的概念分类：给定一个对象，从一个事先定好的分类体系中挑出一个（或者多个）最适合该对象的类别。􀂙对象：可以是任何东西􀂙事先定好的分类体系：可能有结构􀂙最适合：判断标准􀂙便于今后查找是其最直接、最普遍的应用分类体系分类体系一般人工构造政治、体育、军事分类系统可以是层次结构分类模式二类问题：属于或不属于多类问题一个对象可以属于多类人工方法和自动方法人工方法􀂙知识工程的方法建立专家系统(80年代末期)􀂙结果容易理解􀂙费时费力MEDLINE(NationalLibraryofMedicine)$2million/yearformanualindexingofjournalarticles􀂙难以保证一致性和准确性(40%左右的准确率)􀂙专家有时候凭空想象人工方法和自动方法􀂾自动的方法(学习)􀂾结果可能不易理解􀂾快速􀂾准确率相对高(准确率可达85%或者更高)􀂾来源于真实文本，可信度高文本自动分类定义TextCategorization(TC)在给定的分类体系下，根据文本的内容自动地确定文本关联的类别。从数学角度来看，文本分类是一个映射的过程，它将未标明类别的文本映射到已有的类别中，该映射可以是一一、一对多的映射。用数学公式表示如下：A为待分类的文本集合，B为分类体系中的类别集，应用领域门户网站（网页）􀂾图书馆（电子资料）􀂾情报/信息部门（情报处理）􀂾政府、企业等（电子邮件）文本自动分类基本步骤定义分类体系将预先分类过的文档作为训练集从训练集中得出分类模型（需要测试过程，不断细化）用训练获得出的分类模型对其它文档加以分类文本分类基本步骤文本分类过程文本分类实例新闻自动分类新闻自动分类Given:Collectionofexamplenewsstoriesalreadylabeledwithacategory(topic).Task:Predictcategoryfornewsstoriesnot