OPHCLUS:基于序关系保持的层次聚类算法

山东大学学报(工学版) ›› 2010, Vol. 40 ›› Issue (5): 48-55.

OPHCLUS:基于序关系保持的层次聚类算法

雷小锋1,庄伟1,程宇1,丁世飞1,谢昆青2

1. 中国矿业大学计算机学院, 江苏徐州 221008;
2. 北京大学信息科学技术学院智能科学系视觉与听觉国家重点实验室, 北京 100871

收稿日期:2010-03-01 出版日期:2010-10-16 发布日期:2010-03-01
作者简介:雷小锋(1975-),男,陕西合阳县人,博士后,主要研究方向为数据库与数据挖掘、机器学习.E-mail: leiyunhui@gmail.com
基金资助:
国家高技术研究发展计划(863计划)资助项目(2006AA12Z217);中国矿业大学科技基金资助项目(OD080313)

OPHCLUS:An order-preserving based hierarchical clustering algorithm

LEI Xiao-feng1, ZHUANG Wei1, CHENG Yu1, DING Shi-fei1, XIE Kun-qing2

1. School of Computer Science and Technology, China University of Mining and Technology, Xuzhou 221008, China;
2. Department of Intelligence Science／National Laboratory on Machine Perception, Peking University, Beijing 100871, China

Received:2010-03-01 Online:2010-10-16 Published:2010-03-01

摘要/Abstract

摘要：

引入序关系保持的思想,即层次聚类的簇间距离度量应该能够最大限度地维护样本点间的原始距离排序关系。定义了样本点对序关系的概念和序关系损失度量,证明了序关系损失度量可用做聚类的目标准则函数和聚类结果质量的评价标准。利用序关系损失的概念扩展出两种簇间距离度量,实现了基于序关系保持的层次聚类算法(order-preserving based hierarchical clustering algorithm, OPHCLUS)。实验仿真证明了OPHCLUS对聚类质量提升的有效性。

关键词: 层次聚类算法, 序关系保持, 簇间修正距离, 簇间0-1加权距离

Abstract:

The idea of maintaining order relation was proposed, i.e.,the original order of distance between samples should be preserved by the inter-cluster measurement of hierarchical clustering as far as possible. Based on this idea, we defined the notion of order relation of sample’s pair and the loss measurement of order relation, which could be used as the objective criteria function of clustering and the validity standard of consequent clusters. Furthermore, we extended two kinds of distance measurement from the loss of order relation, i.e.,inter-cluster adjusted distance and inter-cluster 0-1 weighted distance; implemented an order-preserving based hierarchical clustering algorithm by using these two measurements. The experiment simulation demonstrated the improvement in the clustering quality.

Key words: hierarchical clustering algorithm, maintenance of order relation, inter-cluster adjusted distance, inter-cluster 0-1 weighted distance

雷小锋1,庄伟1,程宇1,丁世飞1,谢昆青2. OPHCLUS:基于序关系保持的层次聚类算法[J]. 山东大学学报(工学版), 2010, 40(5): 48-55.

LEI Xiao-feng1, ZHUANG Wei1, CHENG Yu1, DING Shi-fei1, XIE Kun-qing2. OPHCLUS:An order-preserving based hierarchical clustering algorithm[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2010, 40(5): 48-55.

参考文献

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

本文评价

推荐阅读 10

[1]	张永花,王安玲,刘福平 . 低频非均匀电磁波在导电界面的反射相角[J]. 山东大学学报(工学版), 2006, 36(2): 22 -25 .
[2]	李侃 . 嵌入式相贯线焊接控制系统开发与实现[J]. 山东大学学报(工学版), 2008, 38(4): 37 -41 .
[3]	孔祥臻,刘延俊,王勇,赵秀华 . 气动比例阀的死区补偿与仿真[J]. 山东大学学报(工学版), 2006, 36(1): 99 -102 .
[4]	来翔 . 用胞映射方法讨论一类MKdV方程[J]. 山东大学学报(工学版), 2006, 36(1): 87 -92 .
[5]	余嘉元1 , 田金亭1 , 朱强忠2 . 计算智能在心理学中的应用[J]. 山东大学学报(工学版), 2009, 39(1): 1 -5 .
[6]	陈瑞,李红伟,田靖. 磁极数对径向磁轴承承载力的影响[J]. 山东大学学报(工学版), 2018, 48(2): 81 -85 .
[7]	王波,王宁生 . 机电装配体拆卸序列的自动生成及组合优化[J]. 山东大学学报(工学版), 2006, 36(2): 52 -57 .
[8]	季涛,高旭,孙同景,薛永端,徐丙垠 . 铁路10 kV自闭/贯通线路故障行波特征分析[J]. 山东大学学报(工学版), 2006, 36(2): 111 -116 .
[9]	秦通,孙丰荣*,王丽梅,王庆浩,李新彩. 基于极大圆盘引导的形状插值实现三维表面重建[J]. 山东大学学报(工学版), 2010, 40(3): 1 -5 .
[10]	张英,郎咏梅,赵玉晓,张鉴达,乔鹏,李善评 . 由EGSB厌氧颗粒污泥培养好氧颗粒污泥的工艺探讨[J]. 山东大学学报(工学版), 2006, 36(4): 56 -59 .