98-统计自然语言处理基础

98-统计自然语言处理基础

统计自然语言处理基础第14章 聚类王建华 2007-09-07

98-统计自然语言处理基础

提纲聚类概述用途 种类 “软”聚类,”硬”聚类

层级聚类单连通、全连通 平均连通 自顶向下聚类

非层级聚类K平均算法 EM算法

98-统计自然语言处理基础

提纲聚类概述用途 种类 “软”聚类,”硬”聚类

层级聚类单连通、全连通 平均连通 自顶向下聚类

非层级聚类K平均算法 EM算法

98-统计自然语言处理基础

聚类概述聚类算法的目标：是将一组对象划分成若干组或类别，简单地说 就是相似元素同组、相异元素不同组的划分过 程。

定义：聚类是一个无指导的学习过程，它是指根据样 本之间的某种距离在无监督条件下的聚簇过程。

98-统计自然语言处理基础

98-统计自然语言处理基础

聚类概述用途：在统计自然语言处理中，聚类算法有两个重要 的用途：1.用于试探性数据分析 2.概念一般化

98-统计自然语言处理基础

聚类概述用途：1.用于试探性数据分析当我们面临一个新问题,并且希望建立一个概率模 型或者仅仅是为了理解现象的基本特性时,这是一 个首要步骤。 对于不懂英语的人也能通过下面的聚类树图对英 文的词性有大致的了解。

98-统计自然语言处理基础

98-统计自然语言处理基础

聚类概述用途：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 的正确性。

98-统计自然语言处理基础

聚类概述聚类算法与分类算法的区别:分类算法是一个有监督的学习过程,它需要对 标注数据集合进行训练; 聚类算法则不需要”教师”的指导,不需要提 供训练数据,倾向于数据的自然划分,因此被称 为无监督的学习或者自动学习.

98-统计自然语言处理基础

聚类概述聚类算法的分类:聚类算法可分为两大类:层级聚类 非层级聚类

98-统计自然语言处理基础

聚类概述层级聚类每个结点都是父类的 一个类； 聚类可以表示成为树 图的形式。

非层级聚类类别结构简单； 类别之间的关系没有 前者清晰； 是一个迭代过程： 初始聚类 分配样本数据

98-统计自然语言处理基础

聚类概述聚类算法的分类:按照聚类方法不同划分：“硬”聚类；每个样本只能属于一个聚类集合；

“软”聚类；一个对象可以同时属于几个聚类集合，但是属于各 个类别的概率不同；

98-统计自然语言处理基础

聚类概述“硬”聚类例：前面的单连通聚 类树图所示的聚类。 层级聚类通常都是 “硬”聚类；

“软”聚类评估单词和某个主题 的相关程度时，它体 现出来优势。 例：inning和score都 是sport类的别中的单 词,但是它们的概率分 别是0.93和 0.65,score属于 government的概率 为0.12,说明score还 和其他类别有关。14

98-统计自然语言处理基础

提纲聚类概述用途

种类 “软”聚类,”硬”聚类

层级聚类单连通、全连通 平均连通 自顶向下聚类

非层级聚类K平均算法 EM算法

98-统计自然语言处理基础

层级聚类层级聚类算法分为“自底向上”和“自顶向下” 两种:“自底向上”: 开始时每个对象都被作为一个类别，然后合并两 个最相似的类别，直到只存在一个类别为止。 “自顶向下”: 开始时全体对象作为一个类别，然后每次迭代分 割内聚度最小的类别集合，直到每个类别中只有 一个对象。

在这两类算法中，都要用到相似度函数.