广西师范大学学报(自然科学版) ›› 2011, Vol. 29 ›› Issue (3): 105-109.

• • 上一篇    下一篇

基于改进属性约简的粗核聚类算法

徐丽1, 丁世飞1,2, 郭锋锋1   

  1. 1.中国矿业大学计算机科学与技术学院,江苏徐州221116;
    2.中国科学院计算技术研究所智能信息处理重点实验室,北京100080
  • 收稿日期:2011-05-16 出版日期:2011-08-20 发布日期:2018-12-03
  • 通讯作者: 丁世飞(1963—),男,山东青岛人,中国矿业大学教授,博导。E-mail:dingsf@cumt.edu.cn
  • 基金资助:
    国家自然科学基金资助项目(60975039);江苏省基础研究计划(自然科学基金)资助项目(BK2009093)

A Rough Kernel Clustering Algorithm Based on ImprovedAttribute Reduction

XU Li1, DING Shi-fei1,2, GUO Feng-feng1   

  1. 1.School of Computer Science and Technology,China University of Mining and Technology,Xuzhou Jiangsu 221116,China;
    2.Key Laboratory of Intelligent Information Processing,Institute ofComputing Technology,ChineseAcademy of Science,Beijing 100080,China
  • Received:2011-05-16 Online:2011-08-20 Published:2018-12-03

摘要: 核聚类算法是一种能够处理样本间差异微弱的有效聚类算法。以粗糙集理论为基础,将基于属性重要度的属性约简算法应用到核聚类算法中,提出一种新的聚类改进算法,由此可以得到高准确率低复杂度的良好结果。该算法在使用核函数对样本优化前,首先用基于属性重要度的约简算法对样本属性进行处理,同时引入信息熵来改进约简算法,从而删除冗余属性得到较优的属性集;然后对样本进行K-means聚类,采用软划分把样本划分到相应聚类中心的上下近似子集中,根据近似子集中样本对聚类的影响程度不同,对上下近似中的样本设置不同的权重来共同决定新的聚类中心。此算法相当于对样本进行了双重优化,采用UCI数据集来测试算法性能。通过和传统聚类算法比较,得出本算法在提高聚类精度的同时降低了复杂度,收敛速度也得到了一定提高。

关键词: 粗糙集, 属性约简, 属性重要度, 信息熵, 核聚类

Abstract: Kernel clustering is an effective algorithm which can deal with samples that have weak differences.On the basis that of new improved attribute importance under the theoryof rough set is applied to the kernel clustering algorithm.Before the samplesare optimized by the kernel function,their properties is processed by the reduction algorithmwhich is based on the attribute importance.At the same time,Information Entropyis introduced to improve the reduction algorithm.So the redundant attributes aredeleted and the optimum set of attributes is obtained;Then,the samples areclustered by K-means clustering algorithms,and the samples are divided intotheupper and lower approximate subsets of the corresponding cluster centers.Due tothe samples in approximate subsets having different influence on cluster,different weighs are designed to determine the new clustering centers.This paper adopts UCI data sets to test the performance ofthe algorithm.Through the comparison with traditional kernel clustering algorithmis shows that the proposed clustering algorithm improves the cluster result'saccuracy,reduces the complexity and shortens the convergence time significantly.

Key words: rough set, attribute reduction, attribute importance, information entropy, kernel clustering

中图分类号: 

  • TP181
[1] JAIN A K,DUBES R C.Algorithms for clustering data[M].Englewood Cliffs,NJ:Prentice-Hall,1988:1-29.
[2] 艾晶,宋自林,赵靓,等.聚类思想在挖掘关联规则中的运用[J].广西师范大学学报:自然科学版,2009,27(1):117-120.
[3] 孙吉贵,刘杰,赵连宇.聚类算法研究[J].软件学报,2008,19(1):48-61.
[4] DING Shi-fei,XU Li,ZHU Hong,et al.Research and progress of cluster algorithms based on granular computing[J].International Journal of DigitalContent Technology and its Applications,2010,4(5):96-104.
[5] 张莉,周伟达,焦李成.核聚类算法[J].计算机学报,2002,25(6):587-590.
[6] 孔锐,张国宣,施泽生,等.基于核的K-均值聚类[J].计算机工程,2004,30(11):12-15.
[7] 贺玲,蔡益朝,杨征.高维数据聚类方法综述[J].计算机应用研究,2010,27(1):23-26.
[8] 丁浩,丁世飞,胡立花.基于粗糙集的属性约简研究进展[J].计算机工程与科学,2010,32(6):92-94.
[9] 彭云,丁树良.基于属性约简的聚类分析技术[J].计算机工程与应用,2009,45(9):138-140.
[10] 周涛,张艳宁,袁和金,等.粗糙核K-means聚类算法[J].系统仿真学报,2008,20(4):921-925.
[11] PAWLAK Z.Rough set[J].International Journal of Computer and Information Science,1982,11(15):341-356.
[12] 王国胤,姚一豫,于洪.粗糙集理论与应用研究综述[J].计算机学报,2009,32(7):1229-1246.
[13] 陈玉明,苗夺谦,焦娜.基于二进制粒与粒计算的属性约简[J].广西师范大学学报:自然科学版,2008,26(2):81-84.
[14] 苗夺谦,李道国.粗糙集理论、算法与应用[M].北京:清华大学出版社,2008:152-174.
[15] 王国胤,于洪,杨大春.基于条件信息熵的决策表约简[J].计算机学报,2002,25(7):759-766.
[16] 吴尚智,苟平章.粗糙集和信息熵的属性约简算法及其应用[J].计算机工程,2011,37(7):56-61.
[1] 林越, 刘廷章, 王哲河. 具有两类上限条件的虚拟样本生成数量优化[J]. 广西师范大学学报(自然科学版), 2019, 37(1): 142-148.
[2] 郑威,文国秋,何威,胡荣耀,赵树之. 属性自表达的低秩无监督属性选择算法[J]. 广西师范大学学报(自然科学版), 2018, 36(1): 61-69.
[3] 胡玉文, 徐久成, 孙林. 决策演化集研究[J]. 广西师范大学学报(自然科学版), 2013, 31(3): 23-29.
[4] 刘海峰, 续欣莹, 申雪芬, 谢王君. 基于限制邻域关系的不完备混合决策系统属性约简[J]. 广西师范大学学报(自然科学版), 2013, 31(3): 30-36.
[5] 申雪芬, 谢王君, 刘海峰, 续欣莹. 一种改进的基于相对正域的增量式属性约简算法[J]. 广西师范大学学报(自然科学版), 2013, 31(3): 45-50.
[6] 徐章艳, 曾艳燕. 基于知识粒度的不完备决策表求核方法[J]. 广西师范大学学报(自然科学版), 2012, 30(3): 154-158.
[7] 胡卉颖, 钟智, 元昌安, 陆建波, 袁晖. 基于基因表达式编程的粗糙集属性约简研究[J]. 广西师范大学学报(自然科学版), 2012, 30(2): 23-28.
[8] 张清华, 幸禹可. 一种基于Hash的快速值约简方法[J]. 广西师范大学学报(自然科学版), 2011, 29(4): 39-44.
[9] 闫麟, 梁吉业, 王俊红. 一种基于等价描述矩阵的规则提取方法[J]. 广西师范大学学报(自然科学版), 2011, 29(3): 94-100.
[10] 鄂旭, 邵良杉, 李胜, 王全铁. 一种基于关联度的区间型数据离散化方法[J]. 广西师范大学学报(自然科学版), 2011, 29(2): 134-137.
[11] 徐久成, 李晓艳, 李双群, 张灵均. 基于相容粒的多层次纹理特征图像检索方法[J]. 广西师范大学学报(自然科学版), 2011, 29(1): 186-187.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 广西师范大学学报(自然科学版)编辑部
地址:广西桂林市三里店育才路15号 邮编:541004
电话:0773-5857325 E-mail: gxsdzkb@mailbox.gxnu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发