Auto-clustering algorithm based on compute unified device architecture and gene expression programming

doi:10.11772/j.issn.1001-9081.2013.07.1890

Journal of Computer Applications ›› 2013, Vol. 33 ›› Issue (07): 1890-1893.DOI: 10.11772/j.issn.1001-9081.2013.07.1890

• Network and distributed techno • Previous Articles Next Articles

Auto-clustering algorithm based on compute unified device architecture and gene expression programming

DU Xin,LIU Dagang,ZHANG Kaihuo,SHEN Yuan,ZHAO Kang,NI Youcong

Faculty of Software, Fujian Normal University, Fuzhou Fujian 350108, China

Received:2013-01-04 Revised:2013-03-01 Online:2013-07-06 Published:2013-07-01
Contact: LIU Dagang

基于统一计算设备架构和基因表达式编程的自动聚类算法

杜欣,刘大刚,张开活,申远,赵康,倪友聪

福建师范大学软件学院, 福州 350108

通讯作者: 刘大刚
作者简介:杜欣(1979-)，女，新疆石河子人，副教授，博士，主要研究方向：演化计算、分布式计算；刘大刚(1988-)，男，山东潍坊人，硕士研究生，主要研究方向：演化计算、分布式计算；张开活(1990-)，男，福建福州人，主要研究方向：分布式计算。
基金资助:
福建省自然科学基金资助项目(2011J05146,2012J01250);福建省杰出青年培育计划项目(福建省教育厅［2011］29号);福建师范大学青年骨干教师培育计划项目(fjsdjk2012083);福建省科技计划重大项目(2011H6006);武汉大学软件工程国家重点实验室开放基金资助项目(SKLSE2012-09-28);福建省教育厅科技项目(JA12077,JA12080,JB11028,JB11029)

Abstract

Abstract: There are two inefficient steps in GEP-Cluster algorithm: one is screening and aggregation of clustering centers and the other is the calculation of distance between data objects and clustering centers. To solve the inefficiency, an auto-clustering algorithm based on Compute Unified Device Architecture (CUDA) and Gene Expression Programming (GEP), named as CGEP-Cluster, was proposed. Specifically, the screening, and aggregation of clustering center step was improved by Gene Read & Compute Machine (GRCM) method, and CUDA was used to parallel the calculation of distance between data objects and clustering centers. The experimental results show that compared with GEP-Cluster algorithm, CGEP-Cluster algorithm can speed up by almost eight times when the scale of data objects is large. CGEP-Cluster can be used to implement automatic clustering with the clustering number unknown and large data object scale.

Key words: Compute Unified Device Architecture (CUDA), Gene Expression Programming (GEP), clustering algorithm, GEP-cluster, evolutionary algorithm

摘要： 针对基于基因表达式编程(GEP)的自动聚类算法GEP-Cluster中聚类中心的筛选和聚合、计算数据对象到各聚类中心距离两个关键步骤效率不高的问题，提出了一种基于统一计算设备架构(CUDA)和GEP的自动聚类改进算法(CGEP-Cluster)。CGEP-Cluster算法采用基因阅读运算器方法对GEP-Cluster算法的聚类中心筛选和聚合步骤进行改进，并基于CUDA将GEP-Cluster算法中数据对象到各聚类中心距离的计算并行化。实验结果表明，在数据对象规模较大时，CGEP-Cluster算法可获得8倍左右的加速比。CGEP-Cluster算法可用于聚类数未知且数据对象规模较大情况下的自动聚类。

关键词: 统一计算设备架构, 基因表达式编程, 聚类算法, GEP-Cluster, 演化算法

CLC Number:

TP301.6

DU Xin LIU Dagang ZHANG Kaihuo SHEN Yuan ZHAO Kang NI Youcong. Auto-clustering algorithm based on compute unified device architecture and gene expression programming[J]. Journal of Computer Applications, 2013, 33(07): 1890-1893.

杜欣刘大刚张开活申远赵康倪友聪. 基于统一计算设备架构和基因表达式编程的自动聚类算法[J]. 计算机应用, 2013, 33(07): 1890-1893.

References

［1］WAGSTAFF K, CARDIE C, ROGERS S. Constrained k-means clustering with background knowledge ［C］// Proceedings of the Eighteenth International Conference on Machine Learning. San Francisco： Morgan Kaufmann, 2001： 577-584.

［2］赖玉霞,刘建平,杨国兴.基于遗传算法的K均值聚类分析［J］.计算机工程,2008,34(20)：200-202.

［3］KUO R J, SYU Y J, CHEN Z Y. Integration of particle swarm optimization and genetic algorithm for dynamic clustering ［J］. Information Sciences, 2012, 195(4)：124-140.

［4］陈瑜,唐常杰,叶尚玉,等.基于基因表达式编程的自动聚类方法［J］.四川大学学报：工程科学版,2007,39(6)：107-112.

［5］姜代红,张三友.基于基因表达式编程的K均值自动聚类算法［J］.计算机仿真,2010,27(12)：216-220.

［6］DEBATTISTI S, MARLAT N, MUSSI L. Implementation of a simple genetic algorithm within the CUDA architecture ［C］// Proceedings of the 11th Annual Conference Companion Genetic and Evolutionary Computation. New York： ACM Press, 2009： 151-152.
［7］POSPCHAL P, JAROS J, SCHWARZ J. Parallel genetic algorithm on the CUDA architecture ［C］// Proceedings of the 2010 International Conference on Applications of Evolutionary Computation. Berlin： Springer, 2010： 442-451.

［8］HARDING S, BANZHAF W. Fast genetic programming on GPUs ［C］// Proceedings of the 10th European Conference on Genetic Programming. Berlin： Springer, 2007： 90-101.

［9］CANO A, ZAFRA A, VENTURA S. Solving classification problems using genetic programming algorithms on GPUs ［C］// Proceedings of the 5th International Conference on Hybrid Artificial Intelligence Systems. Berlin： Springer, 2010： 17-26.

［10］SHAO S, LIU X, ZHOU M. A GPU-based implementation of an enhanced GEP algorithm ［C］// Proceedings of the Fourteenth International Conference on Genetic and Evolutionary Computation Conference. New York： ACM Press, 2012： 999-1006.

［11］倪胜巧,唐常杰,王有为.基于GPU的基因表达式编程性能提升技术［J］.计算机研究与发展,2008,45(增刊)：227-233.

［12］姜大志,吴志健,康立山,等.基因表达式程序设计的 GRCM 方法［J］.系统仿真学报,2006,18(6)：1466-1468.

[1]	ZHAN Hang, HE Lang, HUANG Zhangcan, LI Huafeng, ZHANG Qiang, TAN Qing. Improved feature selection and classification algorithm for gene expression programming based on layer distance [J]. Journal of Computer Applications, 2021, 41(9): 2658-2667.
[2]	WANG Jiarui, TAN Guoping, ZHOU Siyuan. Clustered wireless federated learning algorithm in high-speed internet of vehicles scenes [J]. Journal of Computer Applications, 2021, 41(6): 1546-1550.
[3]	XIE Wenbo, WEI Yongzhuang, LIU Zhenghong. Parallel implementation and analysis of SKINNY encryption algorithm using CUDA [J]. Journal of Computer Applications, 2021, 41(4): 1136-1141.
[4]	YANG Xianfeng, GUI Hongjun, FU Chunchang. F-X domain predictive filtering parallel algorithm based on compute unified device architecture [J]. Journal of Computer Applications, 2021, 41(2): 486-491.
[5]	HU Runyan, LI Cuiran. Clustering algorithm of energy harvesting wireless sensor network based on fuzzy control [J]. Journal of Computer Applications, 2020, 40(9): 2691-2697.
[6]	YAN Huajian, ZHANG Guofu, SU Zhaopin, LIU Yang. Modeling and solving of high-dimensional multi-objective adaptive allocation for emergency relief supplies [J]. Journal of Computer Applications, 2020, 40(8): 2410-2419.
[7]	HUANG Yongxin, TANG Xuefei. Discovery of functional dependencies in university data based on affinity propagation clustering and TANE algorithms [J]. Journal of Computer Applications, 2020, 40(1): 90-95.
[8]	MAO Yimin, LIU Yinping, LIANG Tian, MAO Dinghui. Functional module mining in uncertain protein-protein interaction network based on fuzzy spectral clustering [J]. Journal of Computer Applications, 2019, 39(4): 1032-1040.
[9]	DING Cheng, WANG Qiuping, WANG Xiaofeng. Krill herd algorithm based on generalized opposition-based learning and its application in data clustering [J]. Journal of Computer Applications, 2019, 39(2): 336-342.
[10]	LIU Xiaoming, SHEN Mingyu, HOU Zhengfeng. Firefly fuzzy clustering algorithm based on Levy flight [J]. Journal of Computer Applications, 2019, 39(11): 3257-3262.
[11]	YE Shuang, YANG Xiaomin, YAN Bin'yu. Image super-resolution algorithm based on adaptive anchored neighborhood regression [J]. Journal of Computer Applications, 2019, 39(10): 3040-3045.
[12]	QIU Baozhi, CHENG Luan. Parameter-free clustering algorithm based on Laplace centrality and density peaks [J]. Journal of Computer Applications, 2018, 38(9): 2511-2514.
[13]	SHAO Lun, ZHOU Xinzhi, ZHAO Chengping, ZHANG Xu. Improved K-means clustering algorithm based on multi-dimensional grid space [J]. Journal of Computer Applications, 2018, 38(10): 2850-2855.
[14]	HOU Haiyao, QIAN Yurong, YING Changtian, ZHANG Han, LU Xueyuan, ZHAO Yi. Spatio-temporal query algorithm based on Hilbert-R tree hierarchical index [J]. Journal of Computer Applications, 2018, 38(10): 2869-2874.
[15]	WANG Hong, GE Lina, WANG Suqing, WANG Liying, ZHANG Yipeng, LIANG Juncheng. Improvement of differential privacy protection algorithm based on OPTICS clustering [J]. Journal of Computer Applications, 2018, 38(1): 73-78.

Auto-clustering algorithm based on compute unified device architecture and gene expression programming

基于统一计算设备架构和基因表达式编程的自动聚类算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics