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