ch7聚类2016讲述.ppt

一. 样本点之间的相似性测度 ——距离 ei∈R p ei与ek的相似程度： d2(ei,ek) 定义：距离 d(· ，·)：? ? ? ? R+ ① d(x,y)≥0 ?x,y? ? (正定性) d(x,y) = 0 当且仅当 x=y ② d(x,y) = d(y,x) （对称性） ③ d(x,y) ? d(x,z) + d(z,y) (三角不等式） 二. 类与类之间的相似性测度——聚合指数 问题：如果有两类G1，G2，怎么测量它们之间距离？ — “聚合指数” 系统聚类是逐步过程： 1. 最短距离法： I II III 一类 二类 Dmin Dmax 2. 最长距离法： 3. 重心法: 4. 类平均法： 等于G1和G2中所有样本点间距离的平均。 Dg 5. 离差平方和法： 定义: D(G1,G2)=D1+2-D1-D2 事实上：若G1和G2均能自身充分聚合，并且G1和G2又充分分离，则有D1+2-D1-D2很大。 D1 D1+2 D2 组间变差 三. 定量变量聚类分析 例：推销员问题 首先明确： ?用什么方法测度距离d2(wi,wk) ? ②用什么方法测度聚合指数D(G1,G2）? 最短距离法: I. 构造距离矩阵： Ⅱ. w1……w5自成一类: h1……h5 选择最接近的两元素聚成一类： III. 计算新类之间的关系：w3, w4,w5 , h6 D（w3，h6）=min{d(w3,w1),d(w3,w2)} =min{4,3}=3 D（w4，h6）=min{d(w4,w1),d(w4,w2)} =min{6,5}=5 D（w5，h6）=min{6,5}= 5 取最相似的并成一类： IV. 计算新类之间的关系：w5 h6 h7 取最相似并为一类：h8=h6?h7 平台高度： f(h8)=3 V. 计算新类关系：w5 ,h8 D(w5,h8)=min{D(w5,h6),D(w5,h7)}=min{4,5}=4 h9=w5∪h8 f(h9)=4 由于所有点已聚为一类，计算停止，转入绘聚类图. VI. 绘制聚类图：二分树法 分成二类：（w1 w2 w3 w4）(w5) 分成三类：（w1,w2）,(w3,w4),(w5) 全体的类集合：{h1……h5 ，h6,h7,h8,h9} h6 h7 h8 h9 f (h) 1 2 4 3 h9 ╱ ╲ h8 w5 ╱ ╲ h6 h7 ╱ ╲ ╱ ╲ w1 w2 w3 w4 (二）聚合指数：最大距离法 ? 测度距离 d2(wi,wk) ② 测度聚合指数 D(G1，G2） 最大距离法: I. 构造距离矩阵： II. w1……w5自成一类； 选择最接近的两元素聚成一类： III. 计算新类之间的关系：w3 w4 w5 h6 D（w3，h6）=max{d(w3,w1),d(w3,w2)} =max{4,3}= 4 D（w4，h6）=max{d(w4,w1),d(w4,w2)} =max{6,5}= 6 D（w5，h6）=max{6,5}= 6 取最相似的并成一类： IV. 计算新类之间的关系：w5 h6 h7 取最相似并为一类：h8=w5 ?h7 平台高度： f(h8)=4 V. 计算新类关系：h6 ,h8 D(h6,h8)=max{D(h6 ,w5),D(h6,h7)}=max{6,6}=6 h9=h6∪h8 f(h9)=6 由于所有点已聚为一类，计算停止，转入绘聚类图. VI. 绘制聚类图：二分树法 分成二类：（w1,w2 ）,(w3,w4,w5) 分成三类：（w1,w2）,(w3,w4),(w5) 全体的类集合：{h1……h5 ，h6,h7,h8,h9} h6 h7 h8 h9 f (h) 1 2 6 4 h9 ╱ ╲ h6 h8 ╱╲ ╱╲ w1 w2 w5 h7 ╱╲ w3 w4 怎样判断 应分为几类更合适 谱系图：标度突变法 SPSS软件应用（drink. sav) 1、系统聚类法