文本挖掘课件

1、文本挖掘主要内容1文本数据分析和信息检索2文本的维度归约3文本挖掘方法4 数据挖掘大部分研究主要针对结构化数据，如关系的、数据挖掘大部分研究主要针对结构化数据，如关系的、事事务务的和数据仓库数据。的和数据仓库数据。 现实中大部分数据存储在文本数据库中，如新闻文章、研现实中大部分数据存储在文本数据库中，如新闻文章、研究论文、书籍、究论文、书籍、WEBWEB页面等。页面等。 存放在文本数据库中的数据是半结构化数据，文档中可能存放在文本数据库中的数据是半结构化数据，文档中可能包含结构化字段，如标题、作者、出版社、出版日期包含结构化字段，如标题、作者、出版社、出版日期 等，等，也包含大量非结构化数据，

2、如摘要和内容等。也包含大量非结构化数据，如摘要和内容等。文本检索应用实例文本检索过程文档检索基本步骤文本挖掘概念n文本挖掘旨在通过识别和检索令人感兴趣文本挖掘旨在通过识别和检索令人感兴趣的模式，进而从数据源中抽取有用的信息。的模式，进而从数据源中抽取有用的信息。文本挖掘的数据源是文本集合，令人感兴文本挖掘的数据源是文本集合，令人感兴趣的模式不是从形式化的数据库记录里发趣的模式不是从形式化的数据库记录里发现，而是从非结构化现，而是从非结构化的的数据中发现。数据中发现。文本挖掘的任务n 文本挖掘预处理文本挖掘预处理 原始的原始的非结构化非结构化数据源数据源结构化结构化表示表示n 文本模式挖掘文本模

3、式挖掘 文本挖掘系统核心功能是分析文本集合中各个文本之间共文本挖掘系统核心功能是分析文本集合中各个文本之间共同出现的模式同出现的模式 例如：蛋白质例如：蛋白质P1P1和酶和酶E1E1存在联系，在其他文章中说酶存在联系，在其他文章中说酶E1E1和酶和酶E2E2功能相似，还有文章把酶功能相似，还有文章把酶E2E2和蛋白质和蛋白质P2P2联系起来，联系起来，我们可以推断出我们可以推断出P1P1和和P2P2存在联系存在联系n 挖掘结果可视化挖掘结果可视化 也就是文本挖掘系统的表示层，简称也就是文本挖掘系统的表示层，简称浏览浏览文本挖掘处理过程特征的建立特征集的缩减学习与知识模式的提取知识模式模式质量的

4、评价文档集文本挖掘的一般处理过程2、文本数据分析和信息检索 信息检索泛指用户从包含各种信息的文档信息检索泛指用户从包含各种信息的文档集中查找所需要的信息或知识的过程，人集中查找所需要的信息或知识的过程，人们借助某种检索工具，运用某种特定的检们借助某种检索工具，运用某种特定的检索策略从待检索的信息源中查找出自己需索策略从待检索的信息源中查找出自己需要的信息要的信息。n1. 文本检索的基本度量文本检索的基本度量n2. 文本文本检索检索方法方法n3. 文本索引技术文本索引技术n4. 查询处理技术查询处理技术2、文本数据分析和信息检索 信息检索研究的是大量基于文本的文档信息的组信息检索研究的是大量基于

5、文本的文档信息的组织和检索，如联机图书馆系统、联机文档管理系织和检索，如联机图书馆系统、联机文档管理系统和统和WEBWEB搜索引擎。搜索引擎。数据库系统关注结构化数据数据库系统关注结构化数据段查询和事务处理。段查询和事务处理。 信息检索研究的典型问题是根据用户查询（描述信息检索研究的典型问题是根据用户查询（描述所需信息的关键词），在文档中定位相关文档。所需信息的关键词），在文档中定位相关文档。2.1 文本检索的基本度量n 查准率（查准率（Precision）是检索到的文档中的相关文）是检索到的文档中的相关文档占全部检索到的文档的百分比，它所衡量的是档占全部检索到的文档的百分比，它所衡量的是检索

6、系统的准确性检索系统的准确性n 查全率（查全率（Recall）是被检索出的文档中的相关文）是被检索出的文档中的相关文档占全部相关文档的百分比，它所衡量的是检索档占全部相关文档的百分比，它所衡量的是检索系统的全面性系统的全面性信息检索的度量方式nrelevant：与某查询相关的文档的集合。与某查询相关的文档的集合。nretrieved：系统检索到的文档的集合。系统检索到的文档的集合。nrelevant retrieved：既相关又被检索到既相关又被检索到的实际文档的集合。的实际文档的集合。n查准率查准率(precision)：既相关又被检索到的实际既相关又被检索到的实际文档与检索到的文档的百分比

7、。文档与检索到的文档的百分比。n查全率查全率(recall)：既相关又被检索到的实际文档既相关又被检索到的实际文档与查询相关的文档的百分比。与查询相关的文档的百分比。模型质量的评价实例nrelevant =A,B,C,D,E,F,G,H,I,J = 10nretrieved = B, D, F,W,Y = 5nrelevant retrieved =B,D,F = 3n查准率：查准率：precision = 3/5 = 60%n查全率：查全率：recall = 3/10 = 30% B,D,F相关并被检索到的文档所有文档A,C,E,G,H, I, J相关的文档 W,Y被检索到的文档2.2 文档

8、检索方法n文档选择文档选择n 查询是对选择相关文档指定约束条件，典型方法是布尔检索模型。n文档秩评定文档秩评定n 查询是按相关的次序评定所有文档的秩。即将查询中的关键词与文档中的关键词进行匹配，根据匹配查询的程度给每个文档打分。基于模型的检索n 布尔模型：将用户提问表示成布尔表达式，查询布尔模型：将用户提问表示成布尔表达式，查询式是由用户提问和操作符式是由用户提问和操作符and、or、not组成的表组成的表达式达式n 向量空间模型：有一特征表示集，特征通常为字向量空间模型：有一特征表示集，特征通常为字或词。用户提问与文本表示成高维空间向量，其或词。用户提问与文本表示成高维空间向量，其中每一维为

9、一特征。每个特征用权值表示。用户中每一维为一特征。每个特征用权值表示。用户提问向量的权值由用户制定提问向量的权值由用户制定n 概率模型。富有代表性的模型是二值独立检索模概率模型。富有代表性的模型是二值独立检索模型型(BIR)。BIR模型根据用户的查询模型根据用户的查询Q，可以将所，可以将所有文档有文档d分为两类，一类与查询相关分为两类，一类与查询相关(集合集合R)，另，另一类与查询不相关一类与查询不相关(集合集合N, 是是R 的补集的补集)文本符号化n 符号化：为表示文档而标识关键词。符号化：为表示文档而标识关键词。n 停用词表：看上去停用词表：看上去“不相关的不相关的”词的集合。例如：词的集

10、合。例如：a, the, of , for, with等都是停用词。等都是停用词。n 词根：文本检索系统需要识别互为句法变体的一词根：文本检索系统需要识别互为句法变体的一组词，并且只收集每组词的公共词根。例如：一组词，并且只收集每组词的公共词根。例如：一组词组词drug， drugged，和，和drugs具有公共词根具有公共词根drug，可以看做同一个词的不同出现。，可以看做同一个词的不同出现。文档建模n 向量空间模型：从向量空间模型：从d个文档的集合和个文档的集合和t个词的集合开始，可个词的集合开始，可以把每个文档用以把每个文档用t维空间维空间Rt的向量的向量v建模。建模。n 词频：指词词频

11、：指词t在文档在文档d中出现的次数，即中出现的次数，即freq(d，t).n (加权的加权的)词频矩阵词频矩阵TF(d,t)：用来度量词：用来度量词t与给定文档与给定文档d之间之间的关联度。的关联度。n 逆文档频率逆文档频率IDF：表示词：表示词t的缩放因子或重要性。如果词的缩放因子或重要性。如果词t出现在许多文档中，由于其区分能力减弱，所以它的重要出现在许多文档中，由于其区分能力减弱，所以它的重要性也降低。如果性也降低。如果|dt|d|，词，词t将有很大的将有很大的IDF缩放因子，缩放因子，反之亦然。反之亦然。文档建模n 词频矩阵词频矩阵n行对应关键词行对应关键词t，列对应文档列对应文档d向

12、量向量n将每一个文档视为空间向量将每一个文档视为空间向量vn向量值反映单词向量值反映单词t与文档与文档d的关联度的关联度向量空间模型维度权值计算方法 目前广泛采用目前广泛采用TF/IDFTF/IDF权值计算方法，权值计算方法， TF-IDF TF-IDF的主要思想是，的主要思想是，如果某个词或短语在一篇文章中出现的频率如果某个词或短语在一篇文章中出现的频率TFTF高，并且在高，并且在其他文章中很少出现，则认为此词或者短语具有很好的类其他文章中很少出现，则认为此词或者短语具有很好的类别区分能力，适合用来分类。别区分能力，适合用来分类。 TFTF词频词频(Term Frequency)(Term

13、Frequency)指的是某一个给定的词语在该文指的是某一个给定的词语在该文件中出现的次数。件中出现的次数。 IDFIDF逆逆文档频率文档频率(Inverse Document Frequency)(Inverse Document Frequency)的主要思的主要思想是：如果包含词条的文档越少，想是：如果包含词条的文档越少，IDFIDF越大，则说明词条具越大，则说明词条具有很好的类别区分能力。有很好的类别区分能力。 在完整的向量空间模型中，将在完整的向量空间模型中，将TFTF和和IDFIDF组合在一起，形成组合在一起，形成TF-IDFTF-IDF度量：度量：TF-IDFTF-IDF（d,t

14、d,t）= TF(d,t)= TF(d,t)* *IDF(t)IDF(t)基于相似性的检索212121),(vvvvvvsimn 根据一个文档集合根据一个文档集合d和一个项集合和一个项集合t，可以将每个文档表示，可以将每个文档表示为在为在t维空间维空间R中的一个文档特征向量中的一个文档特征向量v。n 向量向量v中第中第j个数值就是相应文档中第个数值就是相应文档中第j个项的量度。个项的量度。n 计算两个文档相似性可以使用上面的公式计算两个文档相似性可以使用上面的公式n 余弦计算法（余弦计算法（cosine measurecosine measure）文档间相似性计算举例文档向量化查询：相关度文档

15、间相似度（余弦定理）2.3 文本索引技术n倒排索引（倒排索引（inverted indexinverted index）n一种索引结构，包含两个哈希表索引表或两个一种索引结构，包含两个哈希表索引表或两个B+树索引表树索引表n找出与给定词集相关的所有文档找出与给定词集相关的所有文档n找出与指定文档相关的所有词找出与指定文档相关的所有词n易实现，但不能处理同义词和多义词问题，易实现，但不能处理同义词和多义词问题，posting_list非常长，非常长，存储开销大存储开销大倒排表倒排表例子倒排表存储结构特征文件（signature file）n 定义：是一个存储数据库中每一个文档的特征记录的文件定义

16、：是一个存储数据库中每一个文档的特征记录的文件n 方法：每一个特征对应一个固定长度的位串，一个比特位对方法：每一个特征对应一个固定长度的位串，一个比特位对应一个词汇，若某一位对应的词出现在文档中，则该位置应一个词汇，若某一位对应的词出现在文档中，则该位置1，否则置否则置0。n S1n S2n按位操作进行匹配，确定文档的相似形按位操作进行匹配，确定文档的相似形n可以多词对应一个比特位，来减少位串的长度，但增加搜素开销，可以多词对应一个比特位，来减少位串的长度，但增加搜素开销，存在多对一映射的缺点。存在多对一映射的缺点。2.4 查询处理技术n 创建倒排索引，查找包含关键词的文档，检索系统可以迅速回

17、答关键词查询。n 相关反馈：在获得相关文档的实例后，系统可以从实例学习提高检索的性能。n 伪反馈（盲目反馈）：当没有这些相关实例时，系统可以假设在初始的检索结果中的前几个检索的文档是相关的，并提取更多相关的关键词来扩展查询。关键词检索存在的问题n 同义词问题：同义词问题：具有相同或相近含义的两个词具有很不相同的外在形式。例如：用户的查询使用词“automobile”，而相关文档用的不是“automobile”，而是“vehicle”。n 多义词问题：多义词问题：相同的关键词，如“mining”或“java”在不同的上下文中可能意味着不同的事物。3.文本的维度规约n 对于任何一个非平凡的文档数据

18、库，词的数目T和文档数目D通常都很大，如此高的维度将导致低效的计算，因为结果频度表大小为T*D。n 高维还会导致非常稀疏的向量，增加监测和探查词之间联系的难度。n 维度归约使用数据编码或变换，以便得到原数据的归约或“压缩”表示。如果原数据可以由压缩数据重新构造而不丢失任何信息，则该数据归约是无损的。如果我们只能重新构造原数据的近似表示，则该数据归约是有损的。3.1潜在语义索引（LSI）潜在语义索引（LSI）最流行的文档维度归约算法，基于SVD（奇异值分解）LSI基本思想:提取最具代表性的特征，同时最小化同构错误。SVD分解词-文档矩阵：X=UV 是X的奇异值，U、V为左右奇异向量LSI目标函数

19、： 约束为aXXaXaaXaTTaTaoptmaxargminarg21aaTn 奇异值分解（Singular Value Decomposition）是线性代数中一种重要的矩阵分解，是矩阵分析中正规矩阵对角化的推广。n 奇异值分解在某些方面与对称矩阵或Hermite矩阵(共轭矩阵)基于特征向量的对角化类似。然而这两种矩阵分解尽管有其相关性，但还是有明显的不同。对称阵特征向量分解的基础是谱分析，而奇异值分解则是谱分析理论在任意矩阵上的推广。潜在语义标引（latent semantic indexing）方法n 潜在语义标引方法基本步骤：潜在语义标引方法基本步骤：n1.1.建立词频矩阵，建立词频

20、矩阵，frequency matrixfrequency matrixn2.2.计算计算frequency matrixfrequency matrix的奇异值分解的奇异值分解n分解分解frequency matrixfrequency matrix成成3 3个矩阵个矩阵U U，S S，V V。U U和和V V是正交矩阵（是正交矩阵（U UT TU=IU=I），），S S是奇异值的对角矩阵是奇异值的对角矩阵（K KK K）n3.3.对于每一个文档对于每一个文档 d d，用排除了用排除了SVDSVD中消除后的词的新中消除后的词的新的向量替换原有的向量的向量替换原有的向量n4.4.保存所有向量集合

21、，用高级多维索引技术为其创建索保存所有向量集合，用高级多维索引技术为其创建索引引n5.5.用转换后的文档向量进行相似度计算用转换后的文档向量进行相似度计算3.2局部保留标引（LPI）aXLXaSxaxaaTTaijjTiTaoptminarg)(minarg21aXLXaTT局部保留标引（局部保留标引（LPI）：提取最有判别力的特征）：提取最有判别力的特征LPI基本思想：保留局部信息（相邻文档可能涉及基本思想：保留局部信息（相邻文档可能涉及相邻主题，相邻主题，LPI的映射能够使设计相同语义的文的映射能够使设计相同语义的文档尽可能靠近）档尽可能靠近）LPI目标函数：目标函数：约束为约束为3.3概

22、率潜在语义标引（PLSI）概率潜在语义标引（概率潜在语义标引（PLSI）：类似于）：类似于LSI，通过混，通过混合概率模型实现维度归约。合概率模型实现维度归约。PLSI基本思想：文档中有基本思想：文档中有k个潜在的公共主题，使个潜在的公共主题，使用文档的混合权重，得到用文档的混合权重，得到k个新的语义维。个新的语义维。4.文本挖掘方法n 文本挖掘功能层次 关键词关键词相似检索相似检索词语关联分析词语关联分析自然语言处理自然语言处理文本聚类文本聚类文本分类文本分类文本挖掘功能层次文本挖掘功能层次（1）关键词检索 关键词建立倒排文件索引，与传统的信息检索使用的关键词建立倒排文件索引，与传统的信息检

23、索使用的技术类似。技术类似。（2）相似检索 找到相似内容的文本。找到相似内容的文本。（3）词语关联分析 聚焦在词语（包括关键词）之间的关联信息分析上。聚焦在词语（包括关键词）之间的关联信息分析上。（4）文本聚类和文本分类 实现文本的聚类和分类。（5）自然语言处理 揭示自然语言处理技术的语义，进行文本语义挖掘。4.1关联分析挖掘 在文本数据库中，每一文本被视为一个事务，文本中的关键词组可视为事务中的一组事务项。即文本数据库可表示为：文本编号， 关键词集 文本数据库中关键词关联挖掘的问题就变成事务数据库中事务项的关联挖掘。 关联分析挖掘可以用于找出词或关键词间的关联。 4.1关联分析挖掘 输入语义

24、输入语义信息，如信息，如事件、事事件、事实或信息实或信息提取发现提取发现的实体的实体输入是标输入是标记的集合记的集合输入是文输入是文档中关键档中关键词或词的词或词的集合集合基于关键词的方法基于关键词的方法标记方法标记方法信息提取方法信息提取方法4.1关联分析挖掘 关联分析过程：关联分析过程：对文本数据进行分析、词根处理、去除停词等预处理，再调用关联挖掘算法基于关键词的关联技术：基于关键词的关联技术：收集频繁出现的关键词或词汇，找出其关联或相互关系关联挖掘关联挖掘关联挖掘有助于找出符合关联，即领域相关的术语或短语关联挖掘有助于找出符合关联，即领域相关的术语或短语4.1关联分析挖掘n基基于关键字的

25、关联分析于关键字的关联分析n 基于关键字关联分析就是首先收集频繁一起出现的项或者关键字的集合，然后发现其中所存在的关联性n 关联分析对文本数据库进行预处理，生成关键字向量，根据关键字查询向量与文档向量之间的相关度比较结果输出文本结果，然后调用关联挖掘算法4.2文档分类分析4.2文档分类分析n自动文档分类是指利用计算机将一篇文章自动文档分类是指利用计算机将一篇文章自动地分派到一个或多个预定义的类别中自动地分派到一个或多个预定义的类别中n文档分类的关键问题是获得一个分类模式，文档分类的关键问题是获得一个分类模式，利用此分类模式也可以用于其他文档的分利用此分类模式也可以用于其他文档的分类类n有了一个

26、模式之后，需要进行人工标记和有了一个模式之后，需要进行人工标记和训练，以确定这个模式的参数，然后才能训练，以确定这个模式的参数，然后才能进行自动的文档分类进行自动的文档分类4.2文档分类分析n 应用领域应用领域 门户网站（网页）门户网站（网页） 图书馆（电子资料）图书馆（电子资料） n 自动分类优点：自动分类优点： 减小人工分类的繁杂工作减小人工分类的繁杂工作 提高信息处理的效率提高信息处理的效率 减小人工分类的主观性减小人工分类的主观性4.2文档分类分析u步骤步骤定义定义分类体系分类体系将预先分类过的文档作为将预先分类过的文档作为训练集训练集从训练集中得出从训练集中得出分类模型分类模型（需要

27、测试过程，不断（需要测试过程，不断细化）细化）用训练获得出的分类模型对其它文档加以分类用训练获得出的分类模型对其它文档加以分类4.2文档分类分析文本分类基本步骤4.2文档分类分析文本分类过程4.2文档分类分析 特征选择 方法贝叶斯分类最近邻分类相似文档具有相似文档向量，将每个文档关联到相应的类标号将文档分类看做计算文档在特定类中的统计分布文档分类 支持向量机使用数表示类，构建从词空间到类变量的直接映射函数（在高维空间中运行良好，最小二乘线性回归方法区分能力较强）基于关联的、频繁出现的文本模式集对文档分类基于关联的 分类删除文档中与与类标号统计不相关的非特征词4.3文档聚类分析n 文本聚类是根据

28、文本数据的不同特征，将其划分文本聚类是根据文本数据的不同特征，将其划分为不同数据类的过程为不同数据类的过程n 其目的是要使同一类别的文本间的距离尽可能小，其目的是要使同一类别的文本间的距离尽可能小，而不同类别的文本间的距离尽可能的大而不同类别的文本间的距离尽可能的大4.3文档聚类分析n文档自动聚类的步骤文档自动聚类的步骤（1）获取结构化的文本集）获取结构化的文本集（2）执行聚类算法，获得聚类谱系图。聚类算法）执行聚类算法，获得聚类谱系图。聚类算法的目的是获取能够反映特征空间样本点之间的的目的是获取能够反映特征空间样本点之间的“抱团抱团”性质性质（3）选取合适的聚类）选取合适的聚类IA值。在得到

29、聚类谱系图后，值。在得到聚类谱系图后，领域专家凭借经验，并结合具体的应用场合确定领域专家凭借经验，并结合具体的应用场合确定阈值阈值（4）执行聚类算法，获得聚类结果）执行聚类算法，获得聚类结果4.3文档聚类分析混合模型聚类使用潜在语义标引聚类（LSI）光谱聚类对原始数据进行维度归约，运用传统的聚类方法（如k均值，缺点是计算昂贵）对文本数据和先验知识估计模型参数，基于参数推断聚类最小化全局重构误差下，找到原文档空间的最佳子空间近似文档聚类 分析使用保持局部性标引聚类（LPI）发现局部几何结构，具有更强的区分能力4.3文档聚类分析n 文档自动聚类的类型文档自动聚类的类型n 平面划分法：对包含平面划分法：对包含n个样本的样本集构造样本集的个样本的样本集构造样本集的k个个划分，每个划分表示一个聚簇划分，每个划分表示一个聚簇n 层次聚类法：层次聚类法对给定的样本集进行层次分解。层次聚类法：层次聚类法对给定的样本集进行层次分解。根据层次分解方向的不同可分为凝聚层次聚类和分裂层次根据层次分解方向的不同可分为凝聚层次聚类和分裂层次聚类聚类n 基于密度的方法：根据样本点临近区域的密度进行聚类，基于密度的方法：根据样本点临近区域的密度进行聚类，使在给定区域内至少包含一定数据的样本点使在给定区域内至少包含一定