1、1,统计自然语言处理基础,第14章 聚类王建华2007-09-07,2,提纲,聚类概述用途种类“软”聚类,”硬”聚类层级聚类单连通、全连通平均连通自顶向下聚类非层级聚类K平均算法EM算法,3,提纲,聚类概述用途种类“软”聚类,”硬”聚类层级聚类单连通、全连通平均连通自顶向下聚类非层级聚类K平均算法EM算法,4,聚类概述,聚类算法的目标：是将一组对象划分成若干组或类别，简单地说就是相似元素同组、相异元素不同组的划分过程。定义：聚类是一个无指导的学习过程，它是指根据样本之间的某种距离在无监督条件下的聚簇过程。,5,6,聚类概述,用途：在统计自然语言处理中，聚类算法有两个重要的用途：1.用于试探性数
2、据分析2.概念一般化,7,聚类概述,用途：1.用于试探性数据分析当我们面临一个新问题,并且希望建立一个概率模型或者仅仅是为了理解现象的基本特性时,这是一个首要步骤。对于不懂英语的人也能通过下面的聚类树图对英文的词性有大致的了解。,8,9,聚类概述,用途：2.概念一般化以法英翻译为例，Friday前的介词未知，进行推断。已有的英文数据:on Sunday, on Monday, on Thursday.按照语法和语义聚类，Sunday, Monday, Thursday就会被聚到一类，因为它们有相同的上下文模式。Until day-of-the-week, last day-of-the-wee
3、k, day-of-the-week morning同类中的元素具有互换性，因此可以推断on Friday的正确性。,10,聚类概述,聚类算法与分类算法的区别:分类算法是一个有监督的学习过程,它需要对标注数据集合进行训练;聚类算法则不需要”教师”的指导,不需要提供训练数据,倾向于数据的自然划分,因此被称为无监督的学习或者自动学习.,11,聚类概述,聚类算法的分类:聚类算法可分为两大类:层级聚类非层级聚类,12,聚类概述,层级聚类每个结点都是父类的一个类；聚类可以表示成为树图的形式。,非层级聚类类别结构简单；类别之间的关系没有前者清晰；是一个迭代过程：初始聚类分配样本数据,13,聚类概述,聚类算
4、法的分类:按照聚类方法不同划分：“硬”聚类；每个样本只能属于一个聚类集合；“软”聚类；一个对象可以同时属于几个聚类集合，但是属于各个类别的概率不同；,14,聚类概述,“硬”聚类例：前面的单连通聚类树图所示的聚类。层级聚类通常都是“硬”聚类；,“软”聚类评估单词和某个主题的相关程度时，它体现出来优势。例：inning和score都是sport类的别中的单词,但是它们的概率分别是0.93和0.65,score属于government的概率为0.12,说明score还和其他类别有关。,15,提纲,聚类概述用途种类“软”聚类,”硬”聚类层级聚类单连通、全连通平均连通自顶向下聚类非层级聚类K平均算法EM
5、算法,16,层级聚类,层级聚类算法分为“自底向上”和“自顶向下”两种:“自底向上”：开始时每个对象都被作为一个类别，然后合并两个最相似的类别，直到只存在一个类别为止。“自顶向下”：开始时全体对象作为一个类别，然后每次迭代分割内聚度最小的类别集合，直到每个类别中只有一个对象。在这两类算法中，都要用到相似度函数,17,层级聚类,“自底向上”算法（3、4）将每个对象初始化为一个类别；（8）判断最相似的两个聚类；（9）将选出的最相似的聚类进行合并。,18,层级聚类,“自顶向下”（4）所有样本做为一个类别；（7）选择最小内聚度的类别；（8）分割最小内聚度的类别集合。,19,层级聚类,三种相似度函数的大概
6、计算原则单连通聚类：两个集合间最相似样本之间的相似度；有好的局部一致性；,20,单连通聚类,21,层级聚类,三种相似度函数的大概计算原则单连通聚类：两个集合间最相似样本之间的相似度；有好的局部一致性；和最小生成树的方法很类似；,22,层级聚类,三种相似度函数的大概计算原则全连通聚类两个集合间最不相似样本之间的相似度；考虑到了全局因素，避免了单连通算法中“拉长”区域的产生；,23,单连通聚类,24,层级聚类,三种相似度函数的大概计算原则全连通聚类两个集合间最不相似样本之间的相似度；考虑到了全局因素，避免了单连通算法中“拉长”区域的产生；假定“内部紧密”比“内部松散”聚类效果好；例外：夏威夷岛火山
7、；比较而言,全连通聚类更适合统计自然语言处理的要求;主要缺点在于它的算法复杂度是O(n3);,25,层级聚类,三种相似度函数的大概计算原则平均连通聚类集合内部样本之间的平均相似度;是上述两种方法的折中方案;可以替代全连通聚类,它的计算复杂度只有O(n2)；,26,相似度函数计算原则,平均连通聚类当样本定义在m维空间时，相似度量可以采用余弦法：可以在常量时间内完成平均相似度计算；,27,相似度函数计算原则,平均连通聚类平均相似度S的定义： 为非零相似度的总数,28,相似度函数计算原则,平均连通聚类算法每次迭代都确定两个集合cu和cv，使 最大；减少计算量：先计算： ，聚类合并时这个值很容易更新；
8、S(cj)的计算可以利用,29,相似度函数计算原则,平均连通聚类,30,相似度函数计算原则,如果两个聚类ci和cj的向量和已知，那么它们合并形成的聚类的平均相似度计算公式可以写为：,31,层级聚类,自顶向下聚类算法：每次都分割内聚度最小的类；前面所述的三种相似度函数同样可以作为内聚度衡量标准：单连通：最小生成树中的最小相似度；全连通：两个聚类之间最不相似的两个样本之间的距离；平均连通：聚类样本的平均相似度；自顶向下聚类操作内部还需要一个聚类过程，所以它不经常被采用；算法图见下页；,32,自顶向下聚类,33,提纲,聚类概述用途种类“软”聚类,”硬”聚类层级聚类单连通、全连通平均连通自顶向下聚类非
9、层级聚类K平均算法EM算法,34,非层级聚类,综述通常都有一个初始划分假设；绝大多数非层级聚类都需要几次迭代，每次迭代都有可能将样本 数据再分配；要定义迭代过程的停止准则函数；基本原则是确保每次迭代都改善聚类效果，当改善的幅度减缓时就可以停止迭代过程。非层级聚类的优点在于其算法的效率高。,35,非层级聚类,综述下面重点介绍两种非层级聚类的方法：K平均算法：简单，虽然有局限性，但因适用面广、效率高而得到广泛应用。EM算法：是一种算法的基本框架在统计自然语言处理中有很广泛的应用，“向内-向外”算法和“前向-后向”算法；,36,非层级聚类,K平均算法：是种“硬”聚类算法；基本思想：（1）设置初始的聚
10、类中心；（2）将样本类别判定为距某聚类中心最近的类别（3）重新计算每个聚类的中心；（4）重复（2）、（3）直到迭代结束。,37,非层级聚类,38,K平均算法,39,K平均算法,40,K平均算法,在自然语言处理中的一个应用：从纽约时报语料库中挑选出20个单词，下表是这20个词的k平均聚类的结果（k=5）;前四个类别分别对应于：government, finance, sports和research，最后一个类别对应于姓名。可见，词的聚类使我们更容易理解单词的属性及它们之间的内在联系。,41,K平均算法,42,非层级聚类,K平均算法小结：初始聚类中心点可以是随机选取的；聚类效果取决于样本数据集合本
11、身结构；如果数据本身为非定义良好的数据集合时，可以先利用层级聚类算法在样本的一个子集上聚类，确定一些合理的k平均算法初始聚类中心点，随后在这个基础上利用k平均算法聚类。,43,提纲,聚类概述用途种类“软”聚类,”硬”聚类层级聚类单连通、全连通平均连通自顶向下聚类非层级聚类K平均算法EM算法,44,非层级聚类,EM算法是一种“软”聚类方法；只提供了解决问题的框架；有效应用的场合：在包含隐含变量的机器学习问题中，如HMM模型中内部状态的变化无法从外部来观测。在模型的参数估计问题中，如果用极大似然估计难于求解时。,45,EM算法,主要分为两步：估计步骤；（Estimate）最大化步骤；(Maximi
12、ze)举例：设有n个样本，它们是由高斯混合分布产生；高斯混合分布是由k个不同的高斯分布混合生成，每个分布都相互独立。用EM算法估计高斯混合分布参数：确定每个高斯分布的（1）均值和（2）方差及（3）先验概率；,46,EM算法举例,47,EM算法举例,多元高斯分布：概率密度函数：,48,EM算法举例,多元高斯分布：先验概率满足：目标在于如下形式的极大似然估计：,49,EM算法举例,多元高斯分布：设 为第j个高斯分布的参数，需要估计的参数空间可表示为：样本X的概率公式为：,50,EM算法举例,描述一个估计高斯混合分布的EM算法：初始假设：协方差矩阵：单位矩阵；先验概率：均值： 设为任何值；,51,E
13、M算法举例,描述一个估计高斯混合分布的EM算法：估计步骤：,52,EM算法举例,描述一个估计高斯混合分布的EM算法：最大化步骤：,53,EM算法举例,描述一个估计高斯混合分布的EM算法：迭代：不断地迭代E和M步骤，重复计算上面的三个值，直到 不再有显著增加。,54,EM算法,在统计自然语言中的应用：列举：前向-后向算法；向内-向外算法；K平均算法；,55,EM算法,最后几点说明：EM算法有它的缺陷：“坏”的参数初始值设置可以导致EM算法陷进一些局最优点；EM算法的收敛速度比较慢；只有在不存在直接解决的算法的情况下，才应该考虑使用EM算法，因为它并不是解决限制条件下优化问题的高效方法。,56,结束,谢谢!,
