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) 其图形化表示如下图：
第一步:计算欧氏距离。 0(X1,X2)=2,d(x1,X3)=250(×1,X4)=54d(×1,x5)=5 d(X2,X3)=1.5,d(X2,X4)=5,(X2X5)=529 d(X3X4)=3.5,d(X3,X5)=4.03 d(X4,X5)=2 按升序排列 d(X2,X3)=1.5,0(×1,X2)=2,d(X4xX5)=2,o(x1,X3)=25, d(X3,X4)=35,0(×3,X5)=4.03,0(X2,X4)=5,0(X1,X5)=5, d(X2X5)=529,0(X1,X4)=539
➢ 第一步：计算欧氏距离。 d(x1 ,x2 )=2, d(x1 ,x3 )=2.5 d(x1 ,x4 )=5.4 d(x1 ,x5 )=5 d(x2 ,x3 )=1.5, d(x2 ,x4 )=5, d(x2 ,x5 )=5.29 d(x3 ,x4 )=3.5, d(x3 ,x5 )=4.03 d(x4 ,x5 )=2 按升序排列： d(x2 ,x3 )=1.5,d(x1 ,x2 )=2, d(x4 ,x5 )=2, d(x1 ,x3 )=2.5, d(x3 ,x4 )=3.5,d(x3 ,x5 )=4.03,d(x2 ,x4 )=5,d(x1 ,x5 )=5, d(x2 ,x5 )=5.29, d(x1 ,x4 )=5.39
第二步:单链接算法。 按最小距离合并×2和x3,生成新类 ×2X3}其距离为15。X4和x合并成 新类{4,×5},其距离为2。同时, 类伙2X3}和区1间的最小距离也是2.0 将其合并成一个新类1X2Xx3},其距 离为2。最后,两个类1x2x3和{x4,X5} 可以以更高的级别进行合并,其最小 单链接距离为3.5。树状图如下
➢第二步：单链接算法。 按最小距离合并x2和x3，生成新类 {x2 ,x3 }，其距离为1.5。 x4和x5合并成 一个新类{x4 ,x5 }，其距离为2。同时， 类{x2 ,x3 }和{x1 }间的最小距离也是2.0， 将其合并成一个新类{x1,x2 ,x3 } ，其距 离为2。最后，两个类{x1,x2 ,x3 }和{x4 ,x5 } 可以以更高的级别进行合并，其最小 单链接距离为3.5。树状图如下：
1.5202.2. 3.5 x4 图67用单链接方法对图6-6中的数据集聚类后的树状图 第三步:选择相似度阈值s=2.2,从图可以 出单链接算法最终生成类:{1,X2.X3}和
➢ 第三步：选择相似度阈值s=2.2，从图可以 得出单链接算法最终生成类： {x1 ,x2 ,x3 }和 {x4 ,x5 }
第二步:全链接算法。 按最小距离合并×2和x3,生成新类 x2Xx3},其距离为1.5。X4和x合并成 新类{X4,X5},其距离为2。而类 ×2X3和{x间的最大距离是25,将其 合并成一个新类x1X2.x3}。最后,两 个类1x2x3和4,X5可以以更高的级 别进行合并,其最大单链接距离为5.4。 树状图如下
➢第二步：全链接算法。 按最小距离合并x2和x3，生成新类 {x2 ,x3 }，其距离为1.5。 x4和x5合并成 一个新类{x4 ,x5 }，其距离为2。而类 {x2 ,x3 }和{x1 }间的最大距离是2.5，将其 合并成一个新类{x1,x2 ,x3 } 。最后，两 个类{x1,x2 ,x3 }和{x4 ,x5 }可以以更高的级 别进行合并，其最大单链接距离为5.4。 树状图如下：
1.5_2.0—2.22.5 54 图6-8用全链接方法对图6-6中的数据集聚类的树状图 第三步:选择相似度阈值s=22,从图可以 得出全链接算法最终生成类:{1}{×2X3} 和区x 45
➢ 第三步：选择相似度阈值s=2.2，从图可以 得出全链接算法最终生成类： {x1 },{x2 ,x3 } 和{x4 ,x5 }