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