欢迎来到大阳城集团网站

大阳城集团网站

全国咨询热线

86-0411-85927653

最新更新

当前位置:[首页] > 公司荣誉 >

公司荣誉

统计天然谈话解决根本-PPT课件

来源: http://globalbsy.com 发布时间:2021-09-23

  统计自然语言处理基础 第14章 聚类 王建华 2019-09-07 1 提纲 ? 聚类概述 ? ? 用途 种类 ? “软”聚类,”硬”聚类 单连通、全连通 平均连通 自顶向下聚类 K平均算法 EM算法 ? 层级聚类 ? ? ? ? 非层级聚类 ? ? 2 提纲 ? 聚类概述 ? ? 用途 种类 ? “软”聚类,”硬”聚类 单连通、全连通 平均连通 自顶向下聚类 K平均算法 EM算法 ? 层级聚类 ? ? ? ? 非层级聚类 ? ? 3 聚类概述 ? 聚类算法的目标: ? 是将一组对象划分成若干组或类别,简单地说 就是相似元素同组、相异元素不同组的划分过 程。 聚类是一个无指导的学习过程,它是指根据样 本之间的某种距离在无监督条件下的聚簇过程。 ? 定义: ? 4 5 聚类概述 ? 用途: ? 在统计自然语言处理中,聚类算法有两个重要 的用途: 1.用于试探性数据分析 ? 2.概念一般化 ? 6 聚类概述 ? 用途: ? 1.用于试探性数据分析 当我们面临一个新问题,并且希望建立一个概率模 型或者仅仅是为了理解现象的基本特性时,这是一 个首要步骤。 ? 对于不懂英语的人也能通过下面的聚类树图对英 文的词性有大致的了解。 ? 7 8 聚类概述 ? 用途: ? 2.概念一般化 ? 以法英翻译为例,Friday前的介词未知,进行推断。 ? 已有的英文数据:on Sunday, on Monday, on Thursday. ? 按照语法和语义聚类,Sunday, Monday, Thursday就会被聚到一类,因为它们有相同的上下 文模式。 ? Until day-of-the-week, last day-of-the-week, dayof-the-week morning ? 同类中的元素具有互换性,因此可以推断on Friday 的正确性。 9 聚类概述 ? 聚类算法与分类算法的区别: ? ? 分类算法是一个有监督的学习过程,它需要对 标注数据集合进行训练; 聚类算法则不需要”教师”的指导,不需要提 供训练数据,倾向于数据的自然划分,因此被称 为无监督的学习或者自动学习. 10 聚类概述 ? 聚类算法的分类: ? 聚类算法可分为两大类: 层级聚类 ? 非层级聚类 ? 11 聚类概述 ? 层级聚类 ? ? 非层级聚类 ? ? ? 每个结点都是父类的 一个类; 聚类可以表示成为树 图的形式。 ? 类别结构简单; 类别之间的关系没有 前者清晰; 是一个迭代过程: ? 初始聚类 ? 分配样本数据 12 聚类概述 ? 聚类算法的分类: ? 按照聚类方法不同划分: ? “硬”聚类; ? 每个样本只能属于一个聚类集合; 一个对象可以同时属于几个聚类集合,但是属于各 个类别的概率不同; ? “软”聚类; ? 13 聚类概述 ? “硬”聚类 ? ? “软”聚类 ? ? 例:前面的单连通聚 类树图所示的聚类。 层级聚类通常都是 “硬”聚类; ? 评估单词和某个主题 的相关程度时,它体 现出来优势。 例:inning和score都 是sport类的别中的单 词,但是它们的概率分 别是0.93和 0.65,score属于 government的概率 为0.12,说明score还 和其他类别有关。 14 提纲 ? 聚类概述 ? ? 用途 种类 ? “软”聚类,”硬”聚类 单连通、全连通 平均连通 自顶向下聚类 K平均算法 EM算法 ? 层级聚类 ? ? ? ? 非层级聚类 ? ? 15 层级聚类 ? 层级聚类算法分为“自底向上”和“自顶向下” 两种: ? ? “自底向上”: ? 开始时每个对象都被作为一个类别,然后合并两 个最相似的类别,直到只存在一个类别为止。 “自顶向下”: ? 开始时全体对象作为一个类别,然后每次迭代分 割内聚度最小的类别集合,直到每个类别中只有 一个对象。 ? 在这两类算法中,都要用到相似度函数. 16 层级聚类 ? “自底向上”算法 ? ? ? (3、4)将每个对象 初始化为一个类别; (8)判断最相似的两 个聚类; (9)将选出的最相似 的聚类进行合并。 17 层级聚类 ? “自顶向下” ? ? ? (4)所有样本做为一 个类别; (7)选择最小内聚度 的类别; (8)分割最小内聚度 的类别集合。 18 层级聚类 ? 三种相似度函数的大概计算原则 ? 1.单连通聚类: 两个集合间最相似样本之间的相似度; ? 有好的局部一致性; ? 19 1.单连通聚类 20 层级聚类 ? 三种相似度函数的大概计算原则 ? 1.单连通聚类: 两个集合间最相似样本之间的相似度; ? 有好的局部一致性; ? 和最小生成树的方法很类似; ? 21 层级聚类 ? 三种相似度函数的大概计算原则 ? 2.全连通聚类 两个集合间最不相似样本之间的相似度; ? 考虑到了全局因素,避免了单连通算法中“拉长” 区域的产生; ? 22 1.单连通聚类 23 层级聚类 ? 三种相似度函数的大概计算原则 ? 2.全连通聚类 两个集合间最不相似样本之间的相似度; ? 考虑到了全局因素,避免了单连通算法中“拉长” 区域的产生; ? 假定“内部紧密”比“内部松散”聚类效果好; ? ? 例外:夏威夷岛火山; 比较而言,全连通聚类更适合统计自然语言处理的 要求; ? 主要缺点在于它的算法复杂度是O(n3); ? 24 层级聚类 ? 三种相似度函数的大概计算原则 ? 3.平均连通聚类 集合内部样本之间的平均相似度; ? 是上述两种方法的折中方案; ? 可以替代全连通聚类,它的计算复杂度只有O(n2); ? 25 相似度函数计算原则 ? 平均连通聚类 ? 当样本定