内容回顾 试解释基于用户反馈的查询扩展 试解释自动查询扩展的工作原理 试计算 acb 和 abd 的编辑距离 (Edit distance) 1 信息检索原理 课程 第五讲文本分类与聚类技术 授课人 : 孙海龙 2016.10.21 1
提纲 文本分类概述 无监督的机器学习算法 有监督的机器学习算法 3 概述 物以类聚 : 对于大量的文档, 如何能够按照某个主题进行搜索 按照共同的主题对文档进行分组 (grouping) 对分组进行标注 (labeling) 每一个这样的分组称为一个类别 (class) 文本分类 将文档与所属类别关联的过程 Classification/categorization 相关的问题 - 文本聚类 (Clustering) 只分组, 不进行标注 可看作分类的一种特殊情况 4 2
基本方法 : 机器学习 机器学习 从数据中学习特定模式 通过得到的模式可以对新数据进行预测 三种类型算法 有监督的学习 : 有训练数据 无监督的学习 : 无训练数据 半监督的学习 : 训练数据很少 5 文本分类问题的定义 文本分类器 D: 文档集合 C={c 1,c 2,,c L }: L 个类别, 每个类别通过 label 进行描述 二元分类函数 F=D X C {0,1}, 即 <d j,c p >= 1, 如果 d j 是类 c p 的成员 0, 如果 d j 不是类 c p 的成员 多元分类函数 :multi-label 问题 6 3
无监督的分类算法 7 有监督的分类方法 8 4
有监督的算法 依赖于训练数据集 训练文档及分别所属的类别信息 训练过程需要人工进行干预 训练数据集主要用于学习分类函数 训练实例的数量越大, 分类器越准确 避免 Overfitting: 分类器过度适应训练实例 9 提纲 文本分类概述 无监督的机器学习算法 有监督的机器学习算法 10 5
无监督的分类算法 11 聚类概述 文本聚类 : 在没有学习的条件下对文本集合进行组织或划分的过程, 基本思想是将相似文本划分到同一类 ; 无监督的机器学习方法, 不需要训练过程, 且不需预先对文档手工标注类别, 因此具有一定灵活性和较高的自动化处理能力 ; 一般分为层次聚类和非层次聚类 12 6
Clustering 示例 : 夏威夷酒店的网页 13 类别 : 给 cluster 加上标注 类别的标注可以自动生成, 但通常效果不佳 14 7
K-Means: 基于划分的聚类算法 目标 : 把文档集划分成 K 个不相交的子集, 使每一个子集中的点尽可能同质 基于划分的聚类方法是从指定数量的聚类开始搜索可能的点分配方案, 来寻找使某个聚类评分函数最优的分配方法 15 K-means 算法 从 D 中随机选择 k 个初始参照点 以此参照点作为质心, 对 D 进行划分 然后重新计算 Cluster 的质心 对 D 重新划分 重复以上过程, 直到质心不再改变 16 8
K Means 举例 (K=2) Pick seeds Reassign clusters Compute centroids Reasssign clusters x x x x Compute centroids Reassign clusters Converged! 17 K-means 的两种模式 批处理模式 : 在重新计算质心之前, 所有文档都已经进行了分类 在线模式 : 每个文档分类之后, 重新计算质心 通常, 在线模式的效果要优于批处理模式 18 9
Bisecting K-Means K=2 (1) 所有文档归为一个 cluster, 并将其用 k -means 算法划分成两个聚类 (2) 选择当前误差平方和 (SSE) 最大的 cluster, 利用 2-means 对其进行划分 (3) 如果当前所有的 cluster 中文档的数量 <=s, s 为指定的阈值, 算法结束 ; 否则, 转到第 (2) 步继续处理 19 K-MEANS 算法种子的选择 聚类结果与初始种子节点的选择是相关的 随机选择的种子可能会导致收敛很慢或者收敛到局部最优 采用启发式方法或其他方法选择好的种子 20 10
层次聚类 在无标注的样本集合中建立树状层次分类结构 animal vertebrate fish reptile amphib. mammal invertebrate worm insect crustacean 层次聚类一般分为 自底向上 (bottom-up): agglomerative clustering 自顶向下 (bottom-up): divisive clustering 21 自底向上 (bottom-up) 的层次聚类方法 自底向上 ( 融合 ) 的层次聚类方法从每个单个对象出发, 先将一个对象看成单独一类 然后反复合并两个或多个合适的类别 直至满足停止条件 ( 通常为类别个数 K ) 22 11
自顶向下 (top-down) 的层次聚类方法 从对象的全集出发, 一步一步的将其划分为更多的类别 例如 : 在相似图上构造一个最小生成树 : 点代表文档, 边代表距离 然后每一步选择生成树中相似度最小 ( 或距离最远 ) 的边, 将其删除 每删除一条边, 就产生一个新的类别, 当最小的相似度达到某个阈值时算法就可以停止 23 分析 优点 简单, 能灵活处理多粒度的聚类问题, 可使用多种形式的相似性度量或距离度量, 可用于处理多种属性类型 缺点 算法终止条件不易确定, 选择合并或分裂点比较困难 24 12
类别间的相似度 在层次聚类中, 涉及到计算两个类别的相似度, 相似度函数的不同, 聚类效果也不一样 最短距离法 :single-link 最长距离法 : complete-link 中间距离法 : average-link 重心法 类平均法 离差平方和法 25 其他聚类算法 基于密度的聚类算法 DBSCAN 算法 : 一个簇中除了边界点以外, 每个点在给定半径区域内必须包含不少于一定数量的邻接点 DENCLUE 算法 : 每个数据点和其他相邻的数据点之间存在一定的影响关系, 基于该影响关系进行簇的划分及合并 自组织映射 (Self-Organizing Map) : 基于神经网络的方法 26 13
文本聚类评价方法 聚类结果效果评价 : 分离度 / 紧致度 内部评价 : 只利用数据集本身进行结果比较 外部评价 : 利用标准的分类测试集 最常用的外部评价方法 :F-measure 27 无监督的分类算法 28 14
Naïve 文本分类方法 类和类的标注作为已知输入给出 Naïve Classification 输入 : 文档集 D 文档类别 C 以及类别标注 表示 : 每个文档用向量 d j 表示 ; 每个类别的标注 c p 也用向量表示 分类 : 计算向量 d j 和类别 c p 的相似度 : 夹角余弦 29 提纲 文本分类概述 无监督的机器学习算法 有监督的机器学习算法 30 15
分类的概述 定义 : 给定分类体系, 将文本分到某个或者某几个类别中 分类模式 : 二类问题 (binary): 一篇文本属于或不属于某一类 ; 多类问题 (multi-class) : 一篇文本属于多个类别中的其中一个类别, 多类问题可拆分成两类问题 ; 一个文本可以属于多类 (multi-label) 很多分类体系 : Reuters 分类体系 中图分类 31 文本分类过程 32 16
分类器的评估过程 33 有监督的分类方法 34 17
决策树 -Decision Tree 决策树是一种多级分类法, 利用树把一个复杂的分类问题转换成若干个简单的分类问题来解决 决策树最大的特点是采用分级方法通过对训练数据的学习, 总结出一般化的规则, 然后再利用这些规则来逐步分级地解决分类问题 35 Decision Tree: 数据库示例 预测 Play 属性的决策树 预测 36 18
通过分割构建 DT 37 DT 用于文档分类 38 19
决策分类树的特点 构造好的决策树的关键在于如何选择好的逻辑判断或属性 对于同样一组例子, 可以有很多决策树能符合这组例子 一般情况下, 树越小则树的预测能力越强 要构造尽可能小的决策树, 关键在于选择恰当的逻辑判断或属性 在选择划分节点的特征项和特征取值中, 一般采用信息增益作为选择的标准 39 分类算法 -KNN 方法 KNN 分类算法由 Cover 和 Hart 于 1968 年提出 最近邻法计算待分类样本到所有代表点的距离, 将其归入距离最近的代表点所属的类别 为了克服最近邻法错判率较高的缺陷, 将最近邻推广到 k 近邻, 它选取离待分类样本最近的 k 个代表点, 看这 k 个代表点多数属于那一类, 就把测试样本归于该类 KNN 中的决策规则 y(x,c j ) = di KNN Y(d i,c j )=0 或 1,b j 为阈值 sim ( x, d ) y( d, C ) b i i j j 40 20
knn 举例 分类算法 -KNN 方法 新文本 k=1, A 类 k=5,b 类 k=10,b 类 41 分析 KNN 的方法的优点是非常直观便于理解和应用, 实际应用中也非常有效, 是目前应用最为广泛的文本分类算法之一 但是 KNN 方法的缺点也非常明显, 那就是计算代价很高, 每一个测试文本需要和所有的训练样本进行距离计算 采用 KNN 方法需要合理选择 k,k 的选择很大程度上决定了分类性能的好坏 42 21
Rocchio 分类 基于 Rocchio 相关反馈的原理 训练样本作为反馈信息 :negative, positive 文本分类 : 计算 d j 与 c p 质心 的距离 43 分类算法 : 贝叶斯分类 贝叶斯决策理论是统计模式分类中的一个最基本的方法 基于贝叶斯假设, 假定文档中词汇在判别文本所属类别时的作用是相互独立的 朴素贝叶斯分类方法独立性假设 给定一个实例的类标签, 实例中每个属性的出现独立于实例中其他属性的出现 朴素分类器可表述为 c naive = arg max P( c c ) n j ci i= 1 P( ω i c j ) 44 22
分类算法 - 贝叶斯分类 要对一个新文档分类, 就要从训练集中估计出两组概率值 P(C j ) 和 P(w i C j ) P( c c j的文档个数 ) = = j 总文档个数 N( c ) 1+ N( ) j c j N( c ) k c + N( c k k k ) P( ω i c j ωi 在 c j的文档中出现的次数 1+ Nij ) = c j的文档中出现所有词的次数特征词的个数 + N k kj 45 分析 优点是简单易于理解, 且性能一般比较好, 分类的过程直接而快速 缺点是对稀有词比较敏感, 受类别大小的影响也非常大, 对特征集合过大和噪声数据都比较敏感 46 23
支持向量机 Support Vector Machines (SVMs) 用于二元分类的向量空间方法 文档表示为 n 维向量空间 目标 : 在训练样本中找到一个决策面 (hyperplane), 能够将两个类进行最佳的划分 分类 : 基于新文档与 hyperplane 的位置关系 47 分类算法 - 支持向量机 由 V.Vapnik 和其领导的贝尔实验室的小组一起开发出来的一种机器学习的算法 其理论来源自 V.Vapnik 等提出的统计学习理论 目前公认的针对文本分类最有效的机器学习算法 与维度无关 将低维空间中的非线性问题转换为高维空间中的线性问题 如何解决多类的问题? 48 24
Ensemble 方法 Bagging/Stacking 方法 训练 R 个分类器 f i, 分类器的参数不同 其中 f i 是通过从训练集合中 (N 篇文档 ) 随机取 ( 取后放回 )N 次文档构成的训练集合训练得到的 对于新文档 d, 用这 R 个分类器去分类, 得到的最多的那个类别作为 d 的最终类别 49 Stacking 方法 - 训练样本 50 25
Stacking 方法 - 分类 51 Boosting 方法 类似 Bagging 方法, 但是训练是串行进行的, 第 k 个分类器训练时关注对前 k-1 分类器中错分的文档, 即不是随机取, 而是加大取这些文档的概率 使用同一种机器学习方法 52 26
文本维度过高的问题 基本方法 文本高维度问题 选择特征子集 减少 overfitting 问题 降低文本表示的维度 53 文本表示 - 降维技术 特征重构 : 对原始特征进行重新构造, 并映射到低维空间 隐性语义索引 (Latent Semantic Index,LSI) 隐性语义索引根据词条的共现信息探查词条之间内在的语义联系 隐性语义空间实际上是把共现的词条映射到同一维空间上, 而非共现的词条映射到不同的空间上, 这样使得隐性语义空间相比原来的空间维数要小的多, 达到降维的目的 54 27
解决高维问题 特征选择 : 依照某一准则从众多原始特征中选择部分最能反映模式类别的统计特性的相关特征, 去除在所有文档中都普遍存在的 对类别区分作用有限的特征 词频函数 : 去除低频词和高频词 信息增益 : 计算词语的类别区别能力 相对熵 : 计算词对类别之间概率分布的影响 CHI 平方 : 计算词与类别之间的相关关系 互信息 : 计算词和类别共同出现的关系 55 文本分类的评估指标 在文本分类中, 一般用准确率 P (Precision) 和召回率 R (Recall) 以及 F1 值来衡量分类系统的性能 对于第 i 个类别 准确率 召回率 F 值 li Pi = m i i 100% li Ri = 100% n Pi Ri 2 F1i = P + R i i 56 28
多类分类问题的评价 宏平均 (macro-averaging) 先对每个分类器计算上述量度, 再对所有分类器求平均 关于类别的均值 微平均 (micro-averaging) 先合并所有分类器的偶然事件表中的各元素, 得到一个总的偶然事件表, 再由此表计算各种量度 关于文本的均值 57 Q&A 58 29