6.3凝聚层次聚类 在层次聚类分析中,输入中不指定要分成 的类的个数。系统的输入为(,s),系统的 输出是类的层次 >大多数层次聚类过程不是基于最优的思想 而是通过反复的分区直至收敛,找出一些 近似的、未达最优标准的解决方案。 层次聚类算法分为:分裂算法和凝聚算法
6.3 凝聚层次聚类 ➢ 在层次聚类分析中，输入中不指定要分成 的类的个数。系统的输入为(X,s)，系统的 输出是类的层次。 ➢ 大多数层次聚类过程不是基于最优的思想， 而是通过反复的分区直至收敛，找出一些 近似的、未达最优标准的解决方案。 ➢ 层次聚类算法分为：分裂算法和凝聚算法
分区算法从整个样本集开始,将它分成几个 子集,然后把每个子集分成更小的集合,依 次下去,最终,生成—个由粗略到精细的分 区序列。 >凝聚算法首先把每一个对象当作一个初始类, 然后将这些类合并一个更粗略的分区,反复 合并直至得到比较精细的分区,其过程是自 底向上的过程,分区从精细到粗糙。 >凝聚算法又分为单链接和全链接算法,两者 不同之处仅在于它们描述一对类的相似度的 方法
➢ 分区算法从整个样本集开始，将它分成几个 子集，然后把每个子集分成更小的集合，依 次下去，最终，生成一个由粗略到精细的分 区序列。 ➢ 凝聚算法首先把每一个对象当作一个初始类， 然后将这些类合并一个更粗略的分区，反复 合并直至得到比较精细的分区，其过程是自 底向上的过程，分区从精细到粗糙。 ➢ 凝聚算法又分为单链接和全链接算法，两者 不同之处仅在于它们描述一对类的相似度的 方法
>单链接算法基于两类之间的距离是从两个 类中抽取的两对样本(一个取自第一类,另 个取自第二个)的距离中最小值。 >全链接算法基于两类间的距离是每对样本 的距离中的最大值。 >下图为两种算法的图解说明。 + 类 类2 类1 a)单链接距离 b)全链接距离 图6-5对于单链接和全链接聚类算法的距离
➢ 单链接算法基于两类之间的距离是从两个 类中抽取的两对样本(一个取自第一类，另 一个取自第二个)的距离中最小值。 ➢ 全链接算法基于两类间的距离是每对样本 的距离中的最大值。 ➢ 下图为两种算法的图解说明
凝聚聚类算法的基本步骤 1把每一个样本作为一个类,为所有不同的 无序样本对的类间距离构造一个序列,然 后按升序对这个序列进行排序。 2通过已排序的距离序列,对于每一个不同 的阈值d形成一个样本图,图中将距离比dk 更近的各对样本合并成一个新的类。如果 所有的样本都是这个图的元素则停止,否 则,重复该步骤。 3这个算法的输出是一个嵌套层次图,可以 用希望的相似水平去截取,在相应的子图 中生成一个由简单联合标识的分区(类聚)
➢ 凝聚聚类算法的基本步骤： 1.把每一个样本作为一个类，为所有不同的 无序样本对的类间距离构造一个序列，然 后按升序对这个序列进行排序。 2.通过已排序的距离序列，对于每一个不同 的阈值dk形成一个样本图，图中将距离比dk 更近的各对样本合并成一个新的类。如果 所有的样本都是这个图的元素则停止，否 则，重复该步骤。 3.这个算法的输出是一个嵌套层次图，可以 用希望的相似水平去截取，在相应的子图 中生成一个由简单联合标识的分区(类聚)
>例如:二维样本集共5个点X1,×2X32×4X5} 1=(0,2),x2=(0,0),x3=(1.5,0)x4=(5.0),×5=(5,2) 其图形化表示如下图 图6-6聚类分析的5个二维样本
➢ 例如：二维样本集共5个点{x1 ,x2 ,x3 ,x4 ,x5 } x1=(0,2),x2=(0,0),x3=(1.5,0),x4=(5.0),x5=(5,2) 其图形化表示如下图：