改进的Parks聚类分析距离算法_图文

1、 56 华东船舶工业学院学报 ( 自然科学版 表 4 样本距离矩阵 D ( 0 Tab14 Distance matrix of samples d ij 2004 年 1 0100 0137 0160 0180 0189 0123 0187 0152 0131 0133 0144 0185 2 0137 0100 0132 0170 0178 0132 0175 0130 0155 0135 0111 0177 3 0160 0132 0100 0178 0175 0155 0170 0130 0162 0145 0130 0175 4 0180 0170 0178 0100 0130 01

2、75 0132 0177 0188 0179 0173 0129 5 0189 0178 0175 0130 0100 0182 0124 0180 0187 0182 0181 0107 6 0123 0132 0155 0175 0182 0100 0185 0149 0137 0136 0142 0179 7 0187 0175 0170 0132 0124 0185 0100 0175 0189 0180 0175 0122 8 0152 0130 0130 0177 0180 0149 0175 0100 0162 0127 0128 0179 9 0131 0155 0162 01

3、88 0187 0137 0189 0162 0100 0140 0162 0183 10 0133 0135 0145 0179 0182 0136 0180 0127 0140 0100 0139 0180 11 0144 0111 0130 0173 0181 0142 0175 0128 0162 0139 0100 0180 12 0185 0177 0175 0129 0107 0179 0122 0179 0183 0180 0180 0100 1 2 3 4 5 6 7 8 9 10 11 12 从表 4 中找出最小距离 d min = d 5 , 12 , 合并样本 5 ,

4、12 为类 13 。 用公式 6 计算类 13 与其它样本或类的 距离 d ( r , p + q = d ( r , p + d ( r , q 2 ( 6 式中 : d ( r , p + q 样本 p , q 合并成的类与样本 r 之间的距离 ; d ( r , p 样本 r 与样本 p 之间的距离 ; 样本 r 与样本 q 之间的距离 。 d ( r , q 当所有的值计算完毕后即可以得到新的距离矩 阵 D ( 1 , 并从该矩阵中找到新的最小的值 。 依此类 推 , 直至将最后一个样本合并 , 形成一个包含所有样 本的大类 。 416 建立聚类谱系图 图 3 聚类普系图 Fig. 3

5、 Clustering dendrogram 绘制样本聚类图 , 根据距离矩阵得到聚类谱系图 ( 图 3 。 5 效果检验 应用改进前后两种算法对样本进行归类 , 分别得到两种归类结果 。 为了检验归类的效果 , 也就是检 验分在同一类的样本的作业工时是否相似 。 用系数 p ( v 来表征作业时间的相似性 8 pv = sv tv ( 7 式中 : t v 第 v 类内所有样本平均作业时间 ; sv 第 v 类内所有样本作业时间标准差 。 假设整个样本分为 N 类 , 在算得 N 个的相似性系数 p v 后 , 将这 N 个相似系数求平均值 p , 依此评价 聚类的总体相似性 。 p = 1

6、 N N v =1 p v ( 8 式中 : p 全局相似系数 ; pv 第 v 类内作业时间的相似系数 ; N 归类总数 。 第 4 期 刘 滨等 : 改进 Parks 聚类分析距离算法 57 p 的值越大 , 说明作业时间的离散度越大 , 聚类的结果就越差 ; p 的值越小 , 说明作业时间的离散度 越小 , 说明归类的结果越好 。 作业时间数据见表 1 , 此数据为上海外高桥造船有限公司实测数据 。 分别运用原有算法和改良后的算法将样本归为三类 。 同时利用公式 ( 7 ( 8 计算 p v 、 p。 具体结果见 表5: 表 5 前后两算法聚类结果及其相似性系数 pv Tab15 The

7、 clustering results of primary and improved algorit hms and t he related similar coefficient p v 序号 样本 ( 工时 原有算法 3 ( 9 , 7 ( 55 , 8 ( 12 , 1111 pv 改良算法 4 ( 75 , 5 ( 68 , 7 ( 55 , 12 ( 88 原有算法 0176 0178 0136 0 . 12 改良算法 0114 0115 0106 类一 类二 2 ( 15 , 4 ( 75 , 10 ( 14 2 ( 15 , 3 ( 9 , 8 ( 12 , 10 ( 14

8、, 11 ( 11 类三 1 ( 35 , 5 ( 68 , 6 ( 37 , 9 ( 39 , 12 ( 88 1 ( 35 , 6 ( 37 , 9 ( 39 0163 p 从表 5 可以看出 , 对应于原有聚类算法得到的 p = 0163 ; 而对应于改良后的算法得到的 p = 0112 。 说明原有算法所得的归类结果作业时间相似性要差于改良后的算法 。 6 结 论 本文分析了现有聚类分析算法的不足及其原因 ,并以 Parks 距离算法为例 ,对 Parks 距离算法进行 了改良 。通过对船舶装配作业过程的聚类分析 ,证明新算法比原有算法是有进步的 ,在工程实践中有一 定的实际意义 。

9、参考文献 : 1 马萨特 D L ,考夫曼 L . 聚类分析法解析分析化学数据 M . 刘元星译 . 北京 : 化学工业出版社 ,1990. 2 SPA TH H. C1ustering Analysis Algorit hm M . Chichester : Ellis Harwood Ltd ,Uk ,1980. 3 Parks J M. Numerical Taxonomy M . New York : Academic Press , 1969. 4 GOM EZ A ,MORENO A. Knowledge maps : An essential technique for conceptualization J . Data & Knowledge Engi2 neering ,2000 ,33 ,169 - 190. 5 SN EA TH P H W ,SO KAL P R. Numerical Taxonomy M . San Francisco : W H Freeman and Company , 1973. 155