文本挖掘综述课件PPT课件.pptVIP

文本挖掘 主要内容 Page 2 文本挖掘的背景 数据挖掘大部分研究主要针对结构化数据 如关系的 事务的和数据仓库数据 现实中大部分数据存储在文本数据库中 如新闻文章 研究论文 书籍 WEB页面等 存放在文本数据库中的数据是半结构化数据 文档中可能包含结构化字段 如标题 作者 出版社 出版日期等 也包含大量非结构化数据 如摘要和内容等 1 文本挖掘概述 Page 3 1 文本挖掘概述 传统的自然语言理解是对文本进行较低层次的理解 主要进行基于词 语法和语义信息的分析 并通过词在句子中出现的次序发现有意义的信息 文本高层次理解的对象可以是仅包含简单句子的单个文本也可以是多个文本组成的文本集 但是现有的技术手段虽然基本上解决了单个句子的分析问题 但是还很难覆盖所有的语言现象 特别是对整个段落或篇章的理解还无从下手 将数据挖掘的成果用于分析以自然语言描述的文本 这种方法被称为文本挖掘 TextMining 或文本知识发现 KnowledgeDiscoveryinText Page 4 文本检索应用实例 Page 5 文本检索过程 Page 6 文档检索基本步骤 Page 7 文本挖掘与数据挖掘的区别 文本挖掘 文档本身是半结构化的或非结构化的 无确定形式并且缺乏机器可理解的语义 数据挖掘 其对象以数据库中的结构化数据为主 并利用关系表等存储结构来发现知识因此 数据挖掘的技术不适用于文本挖掘 或至少需要预处理 Page 8 文本挖掘与数据挖掘的区别 Page 9 文本挖掘概念 文本挖掘旨在通过识别和检索令人感兴趣的模式 进而从数据源中抽取有用的信息 文本挖掘的数据源是文本集合 令人感兴趣的模式不是从形式化的数据库记录里发现 而是从非结构化的数据中发现 Page 10 文本挖掘的任务 文本挖掘预处理原始的非结构化数据源 结构化表示文本模式挖掘文本挖掘系统核心功能是分析文本集合中各个文本之间共同出现的模式例如 蛋白质P1和酶E1存在联系 在其他文章中说酶E1和酶E2功能相似 还有文章把酶E2和蛋白质P2联系起来 我们可以推断出P1和P2存在联系挖掘结果可视化也就是文本挖掘系统的表示层 简称浏览 Page 11 文本挖掘处理过程 文本挖掘的一般处理过程 Page 12 2 文本数据分析和信息检索 信息检索泛指用户从包含各种信息的文档集中查找所需要的信息或知识的过程 人们借助某种检索工具 运用某种特定的检索策略从待检索的信息源中查找出自己需要的信息 1 文本检索的基本度量2 文本检索方法3 文本索引技术4 查询处理技术 Page 13 2 文本数据分析和信息检索 信息检索研究的是大量基于文本的文档信息的组织和检索 如联机图书馆系统 联机文档管理系统和WEB搜索引擎 数据库系统关注结构化数据段查询和事务处理 信息检索研究的典型问题是根据用户查询 描述所需信息的关键词 在文档中定位相关文档 Page 14 2 1文本检索的基本度量 查准率 Precision 是检索到的文档中的相关文档占全部检索到的文档的百分比 它所衡量的是检索系统的准确性查全率 Recall 是被检索出的文档中的相关文档占全部相关文档的百分比 它所衡量的是检索系统的全面性 Page 15 信息检索的度量方式 relevant 与某查询相关的文档的集合 retrieved 系统检索到的文档的集合 relevant retrieved 既相关又被检索到的实际文档的集合 查准率 precision 既相关又被检索到的实际文档与检索到的文档的百分比 查全率 recall 既相关又被检索到的实际文档与查询相关的文档的百分比 Page 16 模型质量的评价实例 relevant A B C D E F G H I J 10 retrieved B D F W Y 5 relevant retrieved B D F 3查准率 precision 3 5 60 查全率 recall 3 10 30 W Y被检索到的文档 Page 17 2 2文档检索方法 文档选择查询是对选择相关文档指定约束条件 典型方法是布尔检索模型 文档秩评定查询是按相关的次序评定所有文档的秩 即将查询中的关键词与文档中的关键词进行匹配 根据匹配查询的程度给每个文档打分 Page 18 基于模型的检索 布尔模型 将用户提问表示成布尔表达式 查询式是由用户提问和操作符and or not组成的表达式向量空间模型 有一特征表示集 特征通常为字或词 用户提问与文本表示成高维空间向量 其中每一维为一特征 每个特征用权值表示 用户提问向量的权值由用户制定概率模型 富有代表性的模型是二值独立检索模型 BIR BIR模型根据用户的查询Q 可以将所有文档d分为两类 一类与查询相关 集合R 另一类与查询不相关 集合N 是R的补集 Page 19 文本符号化 符号化 为表示文档而标识关键词 停用词表 看上去 不相关的 词的集合 例如 a the of for with等都是停用词 词根 文本检索系统需要识别互为句法变体的一组词 并且只收集每组词的公共词根 例如 一组词drug drugged 和drugs具有公共词根drug 可以看做同一个词的不同出现 Page 20 文档建模 向量空间模型 从d个文档的集合和t个词的集合开始 可以把每个文档用t维空间Rt的向量v建模 词频 指词t在文档d中出现的次数 即freq d t 加权的 词频矩阵TF d t 用来度量词t与给定文档d之间的关联度 逆文档频率IDF 表示词t的缩放因子或重要性 如果词t出现在许多文档中 由于其区分能力减弱 所以它的重要性也降低 如果 dt d 词t将有很大的IDF缩放因子 反之亦然 Page 21 文档建模 词频矩阵行对应关键词t 列对应文档d向量将每一个文档视为空间向量v向量值反映单词t与文档d的关联度 Page 22 向量空间模型 Page 23 维度权值计算方法目前广泛采用TF IDF权值计算方法 TF IDF的主要思想是 如果某个词或短语在一篇文章中出现的频率TF高 并且在其他文章中很少出现 则认为此词或者短语具有很好的类别区分能力 适合用来分类 TF词频 TermFrequency 指的是某一个给定的词语在该文件中出现的次数 IDF逆文档频率 InverseDocumentFrequency 的主要思想是 如果包含词条的文档越少 IDF越大 则说明词条具有很好的类别区分能力 在完整的向量空间模型中 将TF和IDF组合在一起 形成TF IDF度量 TF IDF d t TF d t IDF t Page 24 基于相似性的检索 根据一个文档集合d和一个项集合t 可以将每个文档表示为在t维空间R中的一个文档特征向量v 向量v中第j个数值就是相应文档中第j个项的量度 计算两个文档相似性可以使用上面的公式 余弦计算法 cosinemeasure Page 25 文档间相似性计算举例 Page 26 文档向量化 Page 27 查询 相关度 Page 28 文档间相似度 余弦定理 Page 29 2 3文本索引技术 倒排索引 invertedindex 一种索引结构 包含两个哈希表索引表或两个B 树索引表 找出与给定词集相关的所有文档找出与指定文档相关的所有词易实现 但不能处理同义词和多义词问题 posting list非常长 存储开销大 Page 30 倒排表 Page 31 倒排表例子 Page 32 倒排表存储结构 Page 33 特征文件 signaturefile 定义 是一个存储数据库中每一个文档的特征记录的文件方法 每一个特征对应一个固定长度的位串 一个比特位对应一个词汇 若某一位对应的词出现在文档中 则该位置1 否则置0 S1S2按位操作进行匹配 确定文档的相似形可以多词对应一个比特位 来减少位串的长度 但增加搜素开销 存在多对一映射的缺点 Page 34 2 4查询处理技术 创建倒排索引 查找包含关键词的文档 检索系统可以迅速回答关键词查询 相关反馈 在获得相关文档的实例后 系统可以从实例学习提高检索的性能 伪反馈 盲目反馈 当没有这些相关实例时 系统可以假设在初始的检索结果中的前几个检索的文档是相关的 并提取更多相关的关键词来扩展查询 Page 35 关键词检索存在的问题 同义词问题 具有相同或相近含义的两个词具有很不相同的外在形式 例如 用户的查询使用词 automobile 而相关文档用的不是 automobile 而是 vehicle 多义词问题 相同的关键词 如 mining 或 java 在不同的上下文中可能意味着不同的事物 Page 36 3 文本的维度规约 对于任何一个非平凡的文档数据库 词的数目T和文档数目D通常都很大 如此高的维度将导致低效的计算 因为结果频度表大小为T D 高维还会导致非常稀疏的向量 增加监测和探查词之间联系的难度 维度归约使用数据编码或变换 以便得到原数据的归约或 压缩 表示 如果原数据可以由压缩数据重新构造而不丢失任何信息 则该数据归约是无损的 如果我们只能重新构造原数据的近似表示 则该数据归约是有损的 Page 37 3 1潜在语义索引 LSI 潜在语义索引 LSI 最流行的文档维度归约算法 基于SVD 奇异值分解 LSI基本思想 提取最具代表性的特征 同时最小化同构错误 SVD分解词 文档矩阵 X U V 是X的奇异值 U V为左右奇异向量LSI目标函数 约束为 Page 38 奇异值分解 SingularValueDecomposition 是线性代数中一种重要的矩阵分解 是矩阵分析中正规矩阵对角化的推广 奇异值分解在某些方面与对称矩阵或Hermite矩阵 共轭矩阵 基于特征向量的对角化类似 然而这两种矩阵分解尽管有其相关性 但还是有明显的不同 对称阵特征向量分解的基础是谱分析 而奇异值分解则是谱分析理论在任意矩阵上的推广 Page 39 潜在语义标引 latentsemanticindexing 方法 潜在语义标引方法基本步骤 1 建立词频矩阵 frequencymatrix2 计算frequencymatrix的奇异值分解分解frequencymatrix成3个矩阵U S V U和V是正交矩阵 UTU I S是奇异值的对角矩阵 K K 3 对于每一个文档d 用排除了SVD中消除后的词的新的向量替换原有的向量4 保存所有向量集合 用高级多维索引技术为其创建索引5 用转换后的文档向量进行相似度计算 Page 40 3 2局部保留标引 LPI 局部保留标引 LPI 提取最有判别力的特征LPI基本思想 保留局部信息 相邻文档可能涉及相邻主题 LPI的映射能够使设计相同语义的文档尽可能靠近 LPI目标函数 约束为 Page 41 3 3概率潜在语义标引 PLSI 概率潜在语义标引 PLSI 类似于LSI 通过混合概率模型实现维度归约 PLSI基本思想 文档中有k个潜在的公共主题 使用文档的混合权重 得到k个新的语义维 Page 42 4 文本挖掘方法 文本挖掘功能层次 文本挖掘功能层次 Page 43 1 关键词检索关键词建立倒排文件索引 与传统的信息检索使用的技术类似 2 相似检索找到相似内容的文本 3 词语关联分析聚焦在词语 包括关键词 之间的关联信息分析上 4 文本聚类和文本分类实现文本的聚类和分类 5 自然语言处理揭示自然语言处理技术的语义 进行文本语义挖掘 Page 44 4 1关联分析挖掘 在文本数据库中 每一文本被视为一个事务 文本中的关键词组可视为事务中的一组事务项 即文本数据库可表示为 文本编号 关键词集 文本数据库中关键词关联挖掘的问题就变成事务数据库中事务项的关联挖掘 关联分析挖掘可以用于找出词或关键词间的关联 Page 45 4 1关联分析挖掘 Page 46 4 1关联分析挖掘 关联挖掘有助于找出符合关联 即领域相关的术语或短语 Page 47 4 1关联分析挖掘 基于关键字的关联分析 基于关键字关联分析就是首先收集频繁一起出现的项或者关键字的集合 然后发现其中所存在的关联性关联分析对文本数据库进行预处理 生成关键字向量 根据关键字查询向量与文档向量之间的相关度比较结果输出文本结果 然后调用关联挖掘算法 Page 48 4 2文档分类分析 Page 49 4 2文档分类分析 自动文档分类是指利用计算机将一篇文章自动地分派到一个或多个预定义的类别中文档分类的关键问题是获得一个分类模式 利用此分类模式也可以用于其他文档的分类有了一个模式之后 需要进行人工标记和训练 以确定这个模式的参数 然后才能进行自动的文档分类 Page 50 4 2文档分类分析 应用领域门户网站 网页 图书馆 电子资料 自动分类优点 减小人工分类的繁杂工作提高信息处理的效率减小人工分类的主观性 Page 51 4 2文档分类分析 步骤定义分类体系将预先分类过的文档作为训练集从训练集中得出分类模型 需要测试过程 不断细化 用训练获得出的分类模型对其它文档加以分类 Page 52 4 2文档分类分析 文本分类基本步骤 Page 53 4 2文档分类分析 文本分类过程 Page 54 4 2文档分类分析 删除文档中与与类标号统计不相关的非特征词 Page 55 4 3文档聚类分析 文本聚类是根据文本数据的不同特征 将其划分为不同数据类的过程其目的是要使同一类别的文本间的距离尽可能小 而不同类别的文本间的距离尽可能的大 Page 56 4 3文档聚类分析 文档自动聚类的步骤 1 获取结构化的文本集 2 执行聚类算法 获得聚类谱系图 聚类算法的目的是获取能够反映特征空间样本点之间的 抱团 性质 3 选取合适的聚类IA值 在得到聚类谱系图后 领域专家凭借经验 并结合具体的应用场合确定阈值 4 执行聚类算法 获得聚类结果 Page 57 4 3文档聚类分析 Page 58 4 3文档聚类分析 文档自动聚类的类型平面划分法 对包含n个样本的样本集构造样本集的k个划分 每个划分表示一个聚簇层次聚类法 层次聚类法对给定的样本集进行层次分解 根据层次分解方向的不同可分为