（概率论与数理统计专业论文）基于gamma检验的聚类分析新度量及应用.pdf

摘要 在聚类分析的介绍中，随机变量的聚类方法研究的比较少到目前为止，以香农 信息理论和k o l m o g o r o v 信息论研究的比较多同时这些方法也被广泛应用于随机变 量的聚类分析本文作者在分析g a m m a t e s t 的方法时，发现该方法可用来定义一种 新的度量，同时可应用于聚类分析中，得到理想的结果 本文一共分五章：第一章用了一些篇幅介绍了当前已知的聚类分析的方法现今 的聚类方法主要集中在两大块：一是对样品聚类的方法，另一种是对随机变量聚类的 方法前者的研究已经很深入，得到许多聚类的方法，而且聚类结果也很出色然而， 对随机变量的聚类这一块的研究进展还不是很快关键问题在于比较难找到对两个随 机变量的关系的度量很原始的就是用相关系数来度量两个随机变量的关系随后研 究比较多的是通过香农信息论的方法或者k o l m o g o r o v 的信息度量方法来度量两个随 机变量的方法信息论的应用总的来说是成功的本文也会在第二章中介绍该方法的 一些理论根据，用来和本文提出的新方法的比较在第三章中，本文提出由g a m m a t e s t 得到的新的距离，并给出了计算机上实现的编程思想第四章中，作者运用一组模拟 数据，通过新定义的度量来进行聚类，同时把得到的结果与用相关系数的方法得到的 聚类结果进行比较最后在第五章中，本文讨论了对该新度量能够继续深入研究的地 方 在新定义的度量下，本文给出了计算机的程序实现程序代码详见附录i 附录 i i 为用统计软件产生随机变量的各1 0 0 个随机数附录i i i 为九个随机变量以相关系数 为度量的相似系数矩阵附录为九个随机变量以新度量为度量的相似系数矩阵 关键词：聚类分析、随机变量、g a m m a - t e s t 、度量、模拟数据 a bs t r a c t i nt h ec l u m e t i n ga n a l y s i s ，t h er e s e a r c ho nc l u s t e r i n go fr a n d o mv a r ia _ b l e si sn o tp o p u l a r s o f a r ，t h em a j o r i t yo fr e s e a r c hi sa b o u tt h es h a n n o ni n f o r m a t i o nt h e o r ya n dk o l m o g o r o v i n f o r m a t i o nt h e o r y t h ea u t h o ro ft h i sp a p e re s t a b l i s h e san e w d i s t a n c ef o rc l u s t e r i n gt h e r a n d o mv a r i a b l e sa c c o r d i n gt ot h eg a m m a - t e s tt h e o r y a n dt h i sn e wm e t h o di sv e r i f i e d b e t t e ri ns o m ea s p e c t s t h i sp a p e ri n c l u d e sf i v ec h a p t e r s i nt h ec h a p t e r1 ，a u t h o rp r e s e n t ss o m ep o p u l a r m e t h o d si nt h ec l u s t e r i n ga n a l y s i s ，b o t hc l u s t e r i n gf o rd a t aa n dr a n d o mv a r i a b l e s i nt h e c h a p t e r2 ，t h es h a n n o n i n f c i r m a t i o nt h e o r ya n dk o l m o g o r o vi n f c i r m a t i o nt h e o r ya r e i n t r o d u c e di nd e t a i l s i nt h ec h a p t e r3 ，a u t h o rp r e s e n t st h et h e o r yo fg a m m a a e s ta n d e s t a b l i s h e san e wd i s t a n c ea c c o r d i n gt ot h a tt h e o r y t h es t 印so fc o m p u t e rp r o g r a m m m g a r ea l s oi n t r o d u c e di nt h a tc h a p t e r i nt h ec h a p t e r4 ，t h es i m u l a t i v ed a t aa r eu s e di nt h e c l u s t e r i n gu s i n gt h en e wd i s t a n c e t h ec l u s t e r i n gr e s u l ti sa l s oc o m p a r e dw i t hc l u s t e r i n g r e s u l tu s i n gc o r r e l a t i o nc o e f f i c i e n ta st h ed i s t a n c ei nc l u s t e r i n g i nt h ec h a p t e r5 ，a u t h o r g i v e ss o m es u g g e s t i o n so nt h ei n d e p t hr e s e a r c ho nt h i sn e wc l u s t e r i n gm e t h o di nt h e f u t u r e t h e c o m p u t e rp r o g r a m ，s i m u l a t i v ed a t aa r ei nt h ea p p e n d i xi nt h ee n do f t h i sp a p e r k e yw o r d s ：c l u s t e r i n ga n a l y s i s 、r a n d o mv a r i a b l e s 、g a m m a - t e s t 、d i s t a n c e 、 s i m u l a t i v ed a t a i i d ( 墨，一) y 厶 i ( x ，】，) 符号说明 x i 与_ 之间的距离 第口个指标的方差 协差阵 随机变量x 和】，的互信息量 ，( 墨以)随机变量五以的互信息量 p ( x ) 日( x ) 离散随机变量取x 时的概率 随机变量x 的熵 h ( 五以)随机变量墨以的熵 如( x ) k ( x ) k ( x y ) l l g 似，y ) p 耵( 石，y ) a x ( x ) ，l ，( f ) n ( i ，j ) v f ( x ) n f ( x ) h ( c ) x v a t ( r ) 随机变量限定于b i n 内的熵 输出为x 的最小输入 输出为x y 的最小输入，x y 代表x 和】，串联 基于k o l m o g o r o v 信息论的x 和】，的互信息量 随机变量x 和y 的联合密度函数 随机变量x 的密度函数 落入x 的第i 个框里的样本点的个数 落入x 的第i 个框和y 的第j 个框交集的样本点数 f ( x ) 的一阶偏导数 f ( x ) 的二阶偏导数 c 的凸包 在集合 五x m 中离薯第k 近的点 ，的方差 i v 第一章聚类分析的经典方法 第一节聚类分析的方法 聚类分析又称群分析，它是研究对样品或指标进行分类的一种多元统计方法所谓 的“类 ，通俗的说就是相似元素的集合 聚类分析是多元统计分析的一个新的分支，正处于发展阶段，理论上虽很不完善， 但由于它能够解决许多实际问题，因此这个方法很受人们重视，特别是和其他方法联合 起来使用，往往效果更好 聚类分析的内容十分丰富，按其聚类的方法可以分为以下几种： ( 1 ) 系统聚类法：开始每个对象自成一类，然后每次将最相似的两类合并，合并后 重新计算新类与其他类的距离或相似性测度这一过程一直继续直到所有对象归为 一类为止。并类的过程可用一张谱系聚类图描述 ( 2 ) 调优法( 动态聚类法) ：首先对n 个对象初步分类，然后根据分类的损失函数 尽可能小的原则对其进行调整，直到分类合理为止 ( 3 ) 最优分割法( 有序样品聚类法) ：开始将所有样品看成一类，然后根据某种最 优准则将它们分割为二类、三类，一直分割到所需的k 类为止。这种方法适用于有序 样品的分类问题，也称为有序样品的聚类法 ( 4 ) 模糊聚类法：利用模糊集理论来处理分类问题，它对经济领域中具有模糊特征 的两态数据或多态数据具有明显的分类效果 ( 5 ) 图论聚类法：利用图论中最小支撑树的概念来处理分类问题，创造了独具风格 的方法 ( 6 ) 聚类预报法：利用聚类方法处理预报问题，在多元统计分析中，可用来作预报 的方法很多，如回归分析和判别分析。但对一些异常数据，如气象中的灾害性天气的 预报，使用回归分析或判别分析处理的效果都不好，而聚类预报弥补了这一不足，这 是一个值得重视的方法 聚类分析根据分类对象的不同又分为r 型和q 型两大类，r 型是对变量( 指标) 进行分类，o 型是对样品进行分类 r 型聚类分析的目的有以下几方面： ( 1 ) 可以了解变量间及变量组合间的亲疏关系； ( 2 ) 对变量进行分类； ( 3 ) 根据分类结果及它们之间的关系，在每一类中选择有代表性的变量作为重要变 量，利用少数几个重要的变量进一步作分析计算，如进行回归分析或q 型分析等 q 型聚类分析的目的主要是对样品进行分类分类的结果是直观的，且比传统分 类方法更细致、全面、合理，当然使用不同的分类方法通常会得到不同的分类结果 对任何观测数据都没有惟一“正确的的分类方法实际应用中，常采用不同的分类 方法，对数据进行分析计算，以便对分类提供具体意见，并由实际工作者决定所需要 的分类数及分类情况 1o 】 下面就分别介绍下聚类分析中的o 型聚类和r 型聚类 第二节q 型聚类法 q 型聚类就是：有n 个样品，每个样品均有p 个指标的值，要根据样品问某种相似 性度量，将这1 1 个样品进行分类一般样品间的“相近性”度量应用的是距离指标 设d ( 五，t ) 为样品薯和之间的距离，则满足下面三个条件： ( f ) d ( ，_ ) o ，且d ( 薯，乃) = o 薯= x j ( 豇) d ( 薯，_ ) = d ( _ ，t ) ( 胁) d ( 而，巧) d ( _ ，) + d ( 吒，_ ) 在度量样品问“相近性”时常用的距离有： m i n k o w s k i 酶d ( 硝) = - x o , i ” i 特别当m = 1 ，2 ，即如下： 绝对距离：d ( 而，- , ) - - l i - o ，一j m = l 欧氏距离：d ( 五，。) = i 圭1 ，一斤l j , m - - 2 c h e b i s h 。w 距离：d ( 再，x , ) = m a ：x i x o ，一埘，m = o o 一般的，当指标测量值相差悬殊时，应先对数据进行标准化，再计算距离即 瓴= 昙喜屯，= 击喜( 一元) 2 ，名= m a x x 。， 一呼n ) 其中口= ，p 标准化方法有两种： ，：堑玉，艺：! 型 若考虑p 个指标的相关性等问题，可采用如下距离： 榭栅酬计降掣 i ，棚椭差 m a h a l a n o b i s 足巨离：d ( t ，_ ) = ( 一一) 。1 ( 而一乃)，其中为p 个指标的协差阵 2 记略= d ( 而，) ，q 和q 表示两个类，它们所包含样品数记为， d ( q ，q ) 表类嘭和q 之间的距离 ( 1 ) 最短距离：d ( q ，g q ) = m i n d oi f q ，_ ，q ( 2 ) 最长距离：d ( q ，g q ) = m a x d olf q ，q ) ( 3 ) 类平均距离：。( q ，q ) = - - l ，x 。嘭斥x q e o 当样品间的距离都用欧氏距离时还可定义： 离荠平方和距离 。( g p ，g q ) 2 i n p + p n 玎q 。, l f i ( p ) 一i ( g ) r i ( p ) 一i ( g ) 重心距离 d ( q ，q ) = “样品”i ( p ) 和“样品 i ( g ) 的欧氏距离，毫川，毫川，毫：为q 全部元 其中i ( p ) 是q 的重心，即均值i ( p ) _ 丢喜0 川 一般聚类分析时，系统聚类法应用最广泛系统聚类法基本步骤： ( 1 ) n 个样品一开始各成一类共n 个类，计算两两之间距离，构成一对称阵 此时d ( q ，q ) = d 胛，鹋。) = d ( 2 ) 选择d ( 。) 中对角线以外的最小元素，设其为d ( q ，q ) ，将q ，q 合并为新类 g ，= q ，q ) ( 3 ) 在d ( 。) 中划去q 与q 所对应的两行与两列并加入新类g ，与剩下未聚合的各类之 间的距离所组成的一行和一列，得新的距离矩阵d ( 。) ( 4 ) 由d ( 。) 出发重复步骤( 2 ) 、( 3 ) ，得到对称阵2 ：) ，从q ：) 出发得d ( ，) ，依次类推， 直到n 个样品聚为一个大类为l e ( 5 ) 在合并过程中记下两类合并时样品的编号以及合并两类时的距离的大小( 称为水 平) 并绘成聚类的谱系图，然后根据实际问题的背景和要求选定相应的临界水平以确 定类的个数 第三节r 型聚类法 对p 个指标x = ( 五，一) r ，根据咒个观测值薯= ( 一，靠) r , i = 1 ，及某些 相似性原则，将这p 个变量五，五，一进行分类 变量间的“关联性”度量应用相似系数当为p 个指标变量进行聚类时，用相似系 数衡量变量间的关联程度 称c 筇为变量和劫阿的相似系数若对一切1 _ a p j = 1 ，2 ，刀 龅= ( a o ( a ) ) 为4 的a 一截阵 模糊聚类方法： ( 1 ) 计算相似系数矩阵r 或样品的距离矩阵d ( 2 ) 将尺= ( ) ，。p ( 或d = ( 吒) ) 中的元素压缩到。与1 之间形成模糊矩阵，记为a 如对r = ( 勺) ，令口驴2 三( 1 + 吩) ，对。= ( 略) ，令口驴2 l 一1 + 衰m 轫a xd , i ( 3 ) 建立模糊等价矩阵，即令 么2 - - a a ，a 4 全彳2 彳2 ，直至0 满尼4 2 利 这啪是模糊等价矩阵，令j = ( 毛) = a ( 4 ) 聚类，将按由大到小顺序排列，从毛开始，沿着允= 1 由大到小次序依次取 允= 磊，求匀的相应的九一截阵五 ，元素为i 归入一类，随着九的变小，合并的类越 5 来越多，最终当a = m i n a 驴时全部归入一类 5 、按九值画出聚类的谱系图 另外比较常用的还有动态聚类法和最优分割法，详细可以参考【1 0 】 6 第二章信息论在聚类分析领域的研究和应用 第一节信息论引言 一般来说，进行聚类的对象都是确定的样品或者是随机变量在对随机变量进行聚 类时，一般会用到相似系数的概念但是应用相似系数的方法来度量两个随机变量之间 的关系，往往是不精确的，有时还会漏掉很多有用的信息然而应用信息论的方法却能 很大程度上避免有用信息的遗漏 随机变量的互信息可简记为m i 如果两个随机变量是x ，】，那么它们的交互信息 量可表示为z ( x ，】，) 两个随机变量的m i 有一些简单性质： ( 1 )z ( x ，y ) = o ，当且仅当x ，y 是两个相互独立的随机变量 ( 2 )，( x ，】，) = ，( l x ) ( 3 )m i 的性质：，( x ，y ，z ) = ，( x ，y ) + 州x ，】，) ，z ) m i c 算法： ( 1 ) 应用信息论的方法计算两两的互信息量，构成一个矩阵，设定每一个随机变量为一 个类 ( 2 ) 在某种度量准则下，找出两个类i 和j 由i 和j 组成一个新的类( i j ) ( 3 ) 在矩阵里划掉i 行和j 列，计算其它个体与类( i j ) 的互信息量的值，填入第i 行和第j 列，这样又构成一个新的矩阵 ( 4 ) 如果类的个数大于2 ，继续执行第二步到第四步，一直到只有两个类为止 ( 5 ) 最后把两个类合并 7 第二节s h a n n o n 信息论 设x = 墨，y = 五。是随机变量如果它们是离散随机变量，定义i v , 的熵为： 日( ) = 一p i ( x ) l o g p i ( x ) 其中a ( x ) 表示随机变量z 取工值时的概率 日( x l 以) 为随机变量五以酌熵，定义为： 日( 五9o ) 以) = 一p ( _ ，以) l o g p ( 五，) ， 其中p ( 五，j 。) 表示( 墨) oo - 9 鼍) 取( x i , - - - x n ) 时的概率 而m i 可以定义为： ，( 墨以) = h ( x k ) - h ( x ，疋) k = 1 运用前面互信息量的性质，可以把计算多个随机变量的互信息量，转化为求两个随 机变量的互信息量，通过迭代循环的方法，最终得到多个随机变量的互信息量的值 如果随机变量是连续随机变量则假设该随机变量的密度函数是弘x ，我们首先引 入“框( b i n ) 的概念，使该随机变量成为有界的随机变量假设x 是m 维的随机变 量，每一个“框( b i n ) 内有l e b e s g u e 测度，则 鼽( x ) a j ( x ) a ”， 加( x ) 日( x ) 一m l o g a 其中，h ( x ) = 一；d x l t x ( x ) l o g , t t x ( x ) ，框( b i n ) ”的大小为“a 注意到h b 加( x ) 是真实的信息，因此是非负的然而日( x ) 不是信息量，可能为负 同时m i 定义如下： 职，y ) = j f 蛐灯( w ) l 。g 而p x ；r 丽( x , y ) ( x ，y ) 也可用极限形式来表示，如下： ( x ，】，) = 烛 乩加( x ) + 加( y ) 一玩加( x ，y ) 】 但是，计算( x ，y ) 是很复杂的，一般是取n 个样本点( 而，y i ) ，i = 1 ，玎，然后用数 8 值的方法计算出i ( x ，y ) 的近似值具体计算方法会在下文中讲到 第三节k o l m o g o r o v 信息论 k o l m o g r o v 信息论与s h a n n o n 信息论是有区别的先定义复杂度概念 关于x 的复杂度k ( x ) 是某种最小输入，使得该输入通过u n i v e r s a l 计算机后能输 出x k o l m o g r o v 信息论有一些很好的性质 定义两个字符串x 和y 的连接x yk ( x y ) 代表x y 的复杂度可以发现， k ( x y ) 大于k ( x ) ，但永远不会比k ( x ) + k ( y ) 大即 k ( x ) k ( x y ) k ( x ) + k ( 】，) 再定义k ( 驯y ) ，含义为： 以y 作为辅助输入，输出结果为x 的最短的输入，可以看出，它和k ( x y ) 一k ( y ) 有关， 事实上，有如下关系： 0 k ( x y ) k ( x y ) 一k ( 】，) k ( x ) 注意到k o l m o g r o v 信息论和s h a n n o n 信息论的相似性，可以得到： l l 。( x ，】，) k ( x ) 一k ( x r ) k ( x ) + k ( 】，) 一k ( x y ) 同时，有等式： l l g ( x ，y ) = l i g ( y ，x ) 但是，k ( x ) 理论上来说是不可计算的，一般计算的是该输入的上界 9 度量一： 第四节通过信息论的理论定义出来的度量 这里，d ( x ，y ) 是一个度量 同时满足度量的性质，即 d ( x ，y ) 1 ，对任何( x ，】，) 对 耻叫一怒 d ( x ，x ) = 0 而且该度量也有一些普遍性质，即 如果x y 对一般度量满足，则在d 的度量下也满足x y 这里x ，y 如果是连续随机变量，以上公式计算就变得很困难我们把前式改一下， 以巩西( x ，】，) 代替h ( x ，】，) ，同时把d ( x ，y ) 转化为另外一种形式： 鼢y ) 2 煅( 。( x ，y ) _ 1 ) l o g a - 研i ( ，x + , 俄y y ) 具体证明可参考文献【1 度量二： d ( 工，j ，) = 1 一等 其中k ( x y ) 是条件k o l m o g r o v 复杂度而k ( x ) 一k ( x y ) 是通过y 知道的x 的所有信息 有前人的理论( l ia n dv i t a n y i ，1 9 9 7 ) 8 可以证明： k ( x ) - k ( x y ) = k ( y ) - k ( y x ) 即知道y 的前提下，对得到信息x 的贡献，等于知道x 的前提下，得到y 的贡献这就是 所提到的x 与y 的互信息量而k ( x y ) 表示x 与y 连接起来后的复杂度 从度量的定义式可以看出，d ( x ，y ) 的值是在o ( 当通过y 完全知道x 的信息) 与 1 ( 当通过x 一点也得不到y 的信息) 之间 可以看到，定义的距离满足度量的( 1 ) ，( 2 ) ，( 3 ) - - 个性质： ( 1 ) d ( x ，y ) 0 ( 2 ) d ( x ，x ) = 0 ( 3 ) d ( x ，y ) = d ( y ，z ) 1 0 但是三角不等式的成立并不是那么明显其实可以证明，以上定义的度量d ( x ，y ) 是 满足三角不等式的证明请参考文献 2 】 第五节互信息量的计算方法 计算两个随机变量的互信息量是比较困难的，有的几乎不可能计算出来可以看 到，如果两个随机变量是独立的，那么它们的互信息量为o 即随机变量x ，y 是独立的， 则， i ( x ，】，) = 0 一般的，两个随机变量的互信息量计算公式为： 职，】，) = 脚删( 训) l 。g 厕1 t x r ( x , y ) 由此，可以看出，要计算两个随机变量的互信息量，应该知道x ，】，的各自的密度函 数和它们的联合密度函数然而，在现实生活中，对一般的随机变量，要得到它的密度函 数是很难的，有时近似分布的密度函数也是比较难得到的 通过近些年的研究，很多有效的方法被不断研究出来，来比较准确地估计两个随机变量 的互信息量这些已知的方法都有一个共同的特征：都避免了直接计算随机变量的密度 函数，而通过大量的样本点来估计两个随机变量的互信息量 下面，介绍一下已存在的估计两个随机变量的互信息量的几种方法： ( 1 ) 网格法 这是最简单，最直接的来计算两个随机变量的互信息量的方法 先给出近似计算i ( x ，】，) 的网格法的公式： 删彬，y ) 兰等棚) l o g 焉 这里，p x ( i ) = 出以( 工) ，p y ( j ) = 出以( y ) p ( i ，) = d x d y ( x ，y ) ，i 表示在区间 i 上的积分 近似计算中k 甜( x ，y ) 能够通过计算落在每个区间里的样本点来得到n x ( f ) 代 表x 落入第i 个框里的样本点的个数同理咒y ( 歹) 代表y 落入第j 个框里的样本点的个 数n ( i ，歹) 代表落入这两个交集的样本点数于是，可以近似得到： 则) = 弩 p y ( j ) = 1 n y r ( j ) 加) = 警 可以看到当n 专0 0 目框的尺度趋向于0 i ( x n 趋向于官的真实值 1 2 ( 2 ) 运用信息论计算互信息量 由于日( x ) = 一仁( x ) l o g o ) 而一般很难得到( x ) ，故不会应用这个算法来计算 h ( x ) 然而，我们可以应用k - n e a r e s t 统计方法来近似计算日( x ) 公式为： 日( x ) 而1 备n - ! l 。g ( x + l x ) + y ( 1 ) 一少( ) 这里，少( x ) 是d i g a m m a 函数，即少( 工) = 1 1 ( 工) d r ( x ) a x 则： l f ，( x 4 - 1 ) = 沙( 石) + 1 x 对很大的x ， 沙( 1 ) = c ，c = 0 5 7 7 2 1 5 6 一 i 矿( x ) l o g x 一1 2 x 将h ( x ) 计算式中的k 。一再改成k i 一再，这里k o 和如 o ，使得对任意的x 日( o ， i v f ( x ) l 6 l i n f ( x ) l 6 2 设x # t ，, k l 表示在集合 五，h 中离t 第k 近的点g a m m a - t e s t 是基于下面两个统计 量的： 矗( 护万1 善mh 州一_ 1 2 ( 七) = 面1 荟ml 蜘 i , q - y i l 2 这里y 【址1 是对应于h 【矾】的输出( 区别于在集合 y l ，y m ) 中离乃第k 近的点) 可以证明 r m ( k ) 一v a r ( r )当死( 尼) 一0 时 通过数值计算，发现如( 七) 与y u ( k ) 成近似线性关系故可以假设： ( 七) = v a r ( r ) + a ( m ，尼) 凡( 七) + d ( 如( 呦+ 当m 专c o 这里代表样本误差 所以如果要计算v a “，) 的值，我们可以先计算点( 凡( 七) ，( 尼) ) 在不同的k 下的值， 然后求回归方程，该方程与y 轴的交点即为v a r ( r ) 的近似值 定理一设厂：尺吖- + r 是连续函数，并且存在一阶和二阶的偏导数，且都在集合 c cr m 有界c 内没有孤立点再设r 是实的随机变量，均值为o ，且四阶矩存在( 鼍，乃) i = l ，m 是随机样本点，且各自独立 y f = 厂( 气) + ，； 记距离一第k 近的点为x ，定义： 对每一个k ，有 毛( 尼) = 万1 善ml h 【f 。厂j c f l 2 ( 七) = 面1 善ml 蜘 i , k - y i 2 ( 后) = v a r ( r ) + a ( m ，尼) 凡( 尼) + d ( ( 庀) ) + d ( 1 m l t 2 - k ) 在概率大于1 一o ( 1 m 2 ) ，m 专o o 下成立 这里a ( m ，七) 为 州一：坐攀型善攀 2 白( h 潍】一一i ) 同时满足 o a ( m ，七) 去砰 其中6 1 是厂在c 上的梯度的上界 这里r m ( k ) 一v a r ( r ) 在概率1 下成立，只要( 尼) 专0 具体可参考文献 4 】 1 6 第二节基于g a m m a t e s t 定义的新度量及其性质 以上比较具体地介绍了g a m m a - t e s t 的理论基础在文献 7 】中，g a m m a - t e s t 的理论 被应用于变量选择中而本文通过应用g a m m a t e s t 的理论，定义一种新的度量，应用于 聚类分析中 给定样本点( 葺，乃) ，i = 1 ，朋，满足 以= f ( x 1 ) + ，； 由于是m 中，x i 不能通过光滑函数解释的部分可以假定厂( ) 与是独立的，则 则 v a t ( y , ) = v a r ( f ( x i ) ) + v a r ( r , ) 同理，我们可以认为x 也可以通过关于y 的光滑函数来解释，即 x i = g ( y i ) + s l v a t ( x , ) = v a r ( g ( y f ) ) + v a r ( s f ) 由以上思想，定义新的距离为： d ( x ，y ) = m a x ( 当x 能被y 完全解释，同时y 能被x 完全解释时，v a t r 和v a r s 都为o ，则d ( x ，力= 0 当x 完全不能被y 解释或者y 完全不能被x 解释时，v a t r = v a r 域者v a r s = v a r x ， 则d ( x ，y ) = 1 能互相解释，说明两个随机变量关系密切完全不能解释说明两个随机 变量没什么关系，这和实际生活中，对两个随机变量的关系测度是一致的可以看出： ( 1 ) 0 d ( x ，y ) 1 ( 2 ) 当石= y 时，d ( x ，y ) = 0 ( 3 ) d ( x ，y ) = d ( y ，x ) ( 1 ) 由于v a r ( ，) 0 ，v a r ( s ) o ，由m a x 最大性质得到左侧不等式，而右侧不等式成立原因 在前面已经论述 ( 2 ) 当x ：y 时，v a r ( 厂) = 0 ，v a r ( s ) = 0 ，则d ( x ，y ) = 0 ( 3 ) 由m a x 函数的对称性且pn - i 得到 1 7 第三节基于新度量的聚类分析程序实现 定义了以上的新的度量，我们可以应用这个新的度量来解决实际的聚类问题 首先来具体介绍下应用该方法来聚类的几个必要步骤： ( 1 ) 假设有t 个随机变量五，置，墨要进行聚类首先采集m 个样本点 x a , x i ：，再r ) ，i = 1 ，2 ，m 同时设定每一个随机变量为一类； ( 2 ) 计算置j t 各自的( 七) 值 应用公式 同时 ( 栌面1 善mh 棚一咒1 2 驰，= 击铷址，一再1 2 这里记距离而第k 近的点为h 【触】， ( 3 ) 遍历k ，应用定理一，通过求回归方程的方法得到v a r ( r , ) 的估计值，同理可得到 v a r ( r j ) 的估计值 v a r ( x ) 的估计为： 而1 善m ( 蕾一- ) 2 同理得到v a r ( r ) 的估计值 ( 4 ) 计算得到d ( z ，一) 的值 应用公式 细a x c 藤，离 ( 5 ) 对所有两两的点计算d ( 五，一) 的值，形成一个距离矩阵a ( 6 ) 选出d ( 五，一) 值最小的对应的随机变量对( 五，t ) ，把它们首先归为一类 ( 7 ) 计算类之间距离( 其实只是计算类( 置，一) 与其它t 之问的距离) 可用最长距离， 最短距离，类平均距离等q ，q 记为两个类 ( 8 ) 划掉( 6 ) 中选出的( 五，一) 各自的行和列，所有空缺数字用类距离d ( p ，g ) 替代 1 8 形成新的距离矩阵a ( 9 ) 重复( 2 ) ( 8 ) ，直到所有的随机变量聚成一类为止 1 9 第四章模拟数据下新聚类方法的应用 第一节模拟数据的产生 先取三个随机变量： x u ( o ，4 ) 】，n ( 2 ，i 4 ) z u ( o ，4 ) j 模拟的九个随机变量为： 五= x i = y z l = z x 2 = x 2 k = y 2 z 2 = z 2 x 、2 e x 。 e = e y z 3 = e z 可以看到，( 五，t ，墨) ( x ，e ，匕) ( z 1 ，z 2 ，z 3 ) 各成一类这里要注意同一分布不同 次产生的随机数不同 用统计软件产生随机变量x ，】，z 的各1 0 0 个随机数见附录 第二节两种度量下的聚类结果 计算随机变量五，t ，置，x ，砭，e ，z l ，z 2 ，z 3 以相关系数为度量的相似系数矩阵 见附录i 同时计算随机变量置，置，墨，x ，艺，k ，z 1 ，z 2 ，z 3 以新度量d ( x ，】，) 为度量的相似 系数矩阵见附录 应用s a s 统计软件做这九个随机变量的聚类图 ( 1 ) 设定类之间距离为最长距离( c o m p l e t e ) 以相关系数为度量的聚类： 0 00 10 20 3 0 40 50 60 70 8 0 91 0 1 4 a x i m u md i s t a n c eb e t w e e nc l u s t e r s c l u s t e rh is t o r y n c l c l u s t e r s 8x 2 7z 2 6y 2 5x 1 4z 1 3y 1 2c l 5 1c l 2 j o i n e d _ x 3 z 3 y 3 c l 8 e l 7 c l 6 c l 3 c l 4 2 l f r e 0 2 2 2 3 3 3 6 9 m a x d i s t 0 0 2 4 4 0 0 3 0 8 0 0 7 2 0 0 9 6 6 0 11 6 o 2 2 1 2 0 8 7 8 0 9 5 0 5 n 勉 船 n 睨 聆 扒 瑟 恐 以新度量a ( x ，y ) 为度量的聚类： 0 00 10 20 30 4 0 50 60 70 80 91 0 m a ximumd is t a n c eb e t w e e nc l u s t e r s n c l - - c l u s t e r s 8z l 7x 1 6c l 7 5y 1 4c l 8 3c l 5 2c l 6 1c l 2 c l u s t e rh is t o r y j oin e d z 2 x 2 x 3 y 2 z 3 y 3 c l 3 c l 4 f r e q 2 2 3 2 3 3 6 9 m a x d i s t 0 2 4 8 0 2 5 9 1 0 5 4 3 8 0 5 5 0 5 0 5 8 8 3 0 8 6 9 1 1 w n 勉 船 n 坨 聆 扒 砣 恐 ( 2 ) 设定类之间距离为最短距离( s i n g l e ) 以相关系数为度量的聚类： 0 00 10 20 30 4 0 50 60 70 80 9 m i n i m u md i s t a n c eb e t w e e nc l u s t e r s c l u s t e rh is t o r y n c l - c l u s t e r s 8x 2 7x l 6z 2 5z l 4y 2 3y l 2c l 3 1c l 7 j o in e d - x 3 c l 8 z 3 c l 6 y 3 c l 4 c l 5 c l 2 f r e q 2 3 2 3 2 3 6 9 m i n d i s t 0 0 2 4 4 0 0 3 0 4 0 0 3 0 8 0 0 3 4 7 0 0 7 2 0 0 8 1 5 0 0 9 6 1 0 8 0 9 4 n 怼 玛 n 睨 聆 殂 毖 恐 以新度量d ( x ，y ) 为度量的聚类： m i n i m u md i s t a n c eb e t w e e nc l u s t e r s c l u s t e rh is t o r y n c l c l u s t e r s 8z 1 7x l 6c l 7 5c l 8 4y 1 3c l 4 2 c l 3 lc l 6 j o in e d z 2 x 2 x 3 z 3 y 2 y 3 c l 5 c l 2 f r e q 2 2 3 3 2 3 6 9 m i n d is t 0 2 4 8 0 2 5 9 1 o 4 1 1 0 4 4 8 5 0 5 5 0 5 0 7 3 5 9 0 9 3 4 7 0 9 7 6 3 w n 黔 n 忱 船 殂 瑟 嚣 ( 3 ) 设定类之间距离为类平均距离( a v e r a g e ) 以相关系数为度量的聚类： 0 00 1o 20 30 40 50 60 70 80 9 a v e r a g ed is t a n c eb e t w e e nc l u s t e r s c l u s t e rh is t o r y n c l - c l u s t e r s 8x 2 7z 2 6x l 5y 2 4z 1 3y 1 2c l 6 1c l 2 j oin e d 。 x 3 z 3 c l 8 y 3 c l 7 c l 5 c l 3 c l 4 f r e q 2 2 3 2 3 3 6 9 r m s d is t 0 0 2 4 4 0 0 3 0 8 0 0 7 1 6 0 0 7 2 0 0 8 5 6 0 1 6 6 7 0 8 4 2 7 0 8 8 8 4 n n 怼 船 n 坨 聆 n 毖 船 以新度量d ( x ，y ) 为度量的聚类： 0 00 10 20 30 40 50 60 70 80 91 o a v e r a g ed i s t a n c eb e t w e e nc l u s t e r s n c l一一c l u s t e r s 8z 1 7x l 6c l 7 5c l 8 4y 1 3c l 4 2c l 3 ic l 6 c l u s t e rh i s t o r y j oin e d - z 2 x 2 x 3 z 3 y 2 y 3 c l 5 c l 2 f r e q 2 2 3 3 2 3 6 9 r m s d i s t 0 2 4 8 0 2 5 9 1 0 4 8 2 0 5 2 3 1 0 5 5 0 5 0 8 0 5 2 0 9 8 6 2 0 9 9 5 8 这里应用的相关系数作为相似系数的公式采用： d ( x ，】，) = l - j c ( x ，】，) l 从聚类结果可以看过，采用两种不同的度量方法，随机变量墨，置，五，誓，艺，e ， z l ，z 2 ，z 3 和预期一样分别聚在了一起，说明本文的度量方法符合实际 n 勉 船 n 忱 髂 扒 拢 弱 第五章对新度量深入研究的讨论 第一节基于g a m m a t e s t 的不同度量的定义 在上面的新的度量定义过程中，我们选择了m a x ( ) 这个函数，即 蝇，巧) - - - - m a x ( 器，器， 其实，我们还可以选用其它的关系式来度量两个随机变量的关系，比如 烈纠) _ 幽( 摇，摇) 毗黝鼍1 器器， 皑刮器宰隅 等等 本文尚未对这些度量的不同选取对聚类结果的影响做过细致的讨论分析可能在 这些度量的选取方面，存在最优的度量有待其他文章来进一步讨论和得出有用的结 论 这个新度量只满足作为相似系数的三个条件，并不满足度量的三个条件( 在文中， 称d ( 鼍，x ，) 度量只是沿用 1 0 】上的称呼) 新定黼c 础) = m a x ( 藤i - - - ，藤蜥满童度量的第一条甑即 d ( x ，y ) = o ，当且仅当x = y 是不成立的例如 y = 互1x ，那时d ( z ，y ) = 。，但是x y 第二节聚类分析中类之间距离的选取 在以上的聚类分析中，在选取计算类与类之间的距离时，我们选取的是 最大距离，即 d ( p ，g ) 2 拒昱强j ( 置，t ) 最短距离，即 d ( b q ) ：叶m i ，n 。q 办 类平均距离，即 d ( p ，g ) 2 去荟善略 但是，我们也可以选取其他计算类之间的距离的方法，例如： 重心法，密度估计法( 两阶段密度估计法，k 最近邻估计法，均匀核估计法，w o n g 混合 法) ，可变类平均法，m c q u i t t y 相似分析法，中间距离法，w a r d 最小方差法，w a r d 离 差平方和法，具体公式可以参考文献【1 1 】 这些不同的类距离计算公式的应用，得到的聚类结果一般是不一样的本文还未对 此做过计算和比较，可能存在最优结果故也可以在这方面研究分析一番 第三节对照组所用聚类方法的选取 本文中，选取的对照组的聚类方法是比较简单的计算相关系数的方法还可以选取 其他方法来作为对照组的聚类方法值得一提的是，前面介绍了最新的信息论的方法来 聚类的理论，也同时给出了在应用信息论的前提下，所定义的各种不同的度量，例如 度量一： 度量二： 则- 1 一器 离散随机变量下 跗肛掣( 础) _ 1 ) l o g 。器 连续随卡几变量下 d ( x ，y ) = 1 一掣 其中k ( 少) 是条件k o l m o g r o v 复杂度 这些基于信息论的距离定义都满足度量的三条基本性质 度量一中的d ( x ，】，) 是基于s h a n n o n 信息论的； 度量二中的a ( x ，y ) 是基于k o l m o g r o v 复杂度的 信息论中的对信息的度量分两块：s h a n n o n 的信息理论和k o l m o g r o v 的信息理论 通过信息论方法定义的其他度量，不外乎以这两种信息理论为基础 在深度的分析