第六章 聚类分析(2).ppt

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