Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)
计算机科学技术     
基于多染色体演化的自适应类别数聚类方法
倪广翼, 章孝灿, 苏程, 俞伟斌
浙江大学 地球科学系, 浙江 杭州 310027
Count adaptive clustering algorithm based on multiple-chromosome evolution
NI Guang-yi, ZHANG Xiao-can, SU Cheng, YU Wei-bin
Department of Geoscience, Zhejiang University, Hangzhou 310027, China
 全文: PDF(1646 KB)   HTML
摘要：

为了解决在遗传算法聚类分析中影响算法效率的互相关性问题以及在没有先验知识的情况下确定类别数问题,在充分分析基因的互相关性对算法效率和收敛性影响的基础上,借鉴多染色体生物的进化特性,提出多染色体取代传统单染色体的遗传算法.算法在进化过程中充分利用类簇之间的相互关系,提高了遗传算法的效率和收敛能力,并且在遗传过程中类别数量可变；为了明确地控制类别数,采用基于分布拟合的适应度函数,为在没有先验知识的情况下确定类别数提供了分析依据.通过与K均值的遗传算法（KGA）、最大期望算法（EM算法）的对比分析以及针对遥感影像的实验表明,该遗传算法在对类别数能进行自适应控制的基础上,在效率和收敛性上也都能取得较好的效果.
Abstract:

 Two well-known problems exist when genetic algorithms (GAs) applied to data clustering: the “content-sensitivity” problem which restrains efficiency, and how to determine the count of clusters without prior knowledge. In order to resolve these problems, by fully researching on the nature of how “context-sensitivity” affects efficiency and convergency, a multiple chromosome genetic clustering algorithm was proposed, which takes the advantage of the evolvement of multiple chromosome creatures. The algorithm improved the efficiency and convergency, by making use of the interrelationship among all clusters while evolving, moreover, by this way the count of cluster is variable in each individual. To control the count of clusters, fitness functions which based on distribution fitting was defined, which can provide decision information without prior knowledge. The comparison of the algorithm with the K genetic algorithm （KGA） and the expectation-maximization （EM） algorithm and the results of experiments on remote sensing image show promising results on efficiency and convergency with cluster count automatically adjusted.
出版日期: 2015-04-01
:  TP 301.6  
通讯作者: 章孝灿,男,教授,博导.     E-mail: zxc1121@zju.edu.cn
作者简介: 倪广翼(1986—), 男, 博士生, 从事GIS与遥感影像处理算法研究. E-mail: widewing@zju.edu.cn
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　

引用本文:

倪广翼, 章孝灿, 苏程, 俞伟斌. 基于多染色体演化的自适应类别数聚类方法[J]. 浙江大学学报(工学版), 10.3785/j.issn.1008-973X.2014.06.003.

NI Guang-yi, ZHANG Xiao-can, SU Cheng, YU Wei-bin. Count adaptive clustering algorithm based on multiple-chromosome evolution. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 10.3785/j.issn.1008-973X.2014.06.003.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2014.06.003    或    http://www.zjujournals.com/eng/CN/Y2014/V48/I6/980

［1］ FALKENAUER E. Genetic Algorithms and Grouping Problems［M］. New York, USA： Wiley, 1998.
［2］ HRUSCHKA E R, CAMPELLO R J G B, FREITAS A A, et al. A survey of evolutionary algorithms for clustering［J］. Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on, 2009, 39(2): 133-155.
［3］ FRNTI P, KIVIJRVI J, KAUKORANTA T, et al. Genetic algorithms for large-scale clustering problems［J］. The Computer Journal, 1997, 40(9): 547-554.
［4］ LU Y, LU S, FOTOUHI F, et al. FGKA: A fast genetic k-means clustering algorithm［C］ ∥ Proceedings of the 2004 ACM Symposium on Applied Computing. New York, USA： ACM, 2004: 622-623.
［5］ KRISHNA K, MURTY M N. Genetic K-means algorithm［J］. Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, 1999, 29(3): 433-439.
［6］ SEO H S, OH S J, LEE C W. Evolutionary genetic algorithm for efficient clustering of wireless sensor networks［C］∥ Consumer Communications and Networking Conference, 2009. CCNC 2009. 6th IEEE. Las Vegas, USA: IEEE, 2009: 15.
［7］ HRUSCHKA E R, CAMPELLO R J G B, DE CASTRO L N. Evolving clusters in gene-expression data［J］. Information Sciences, 2006, 176(13): 1898-1927.
［8］ ALVES V S, CAMPELLO R J G B, HRUSCHKA E R. Towards a fast evolutionary algorithm for clustering［C］∥ Evolutionary Computation, 2006. CEC 2006. IEEE Congress on. Vancouver, Canada: IEEE, 2006: 1776-1783.
［9］ HRUSCHKA E R, EBECKEN N F F. A genetic algorithm for cluster analysis［J］. Intelligent Data Analysis, 2003, 7(1): 15-25.
［10］ HANDL J, KNOWLES J. An evolutionary approach to multiobjective clustering［J］. Evolutionary Computation, IEEE Transactions on, 2007,11(1): 56-76.
［11］ 赖玉霞, 刘建平, 杨国兴. 基于遗传算法的 K 均值聚类分析［J］. 计算机工程, 2008, 34(20): 200-202.
LAI Yu-xia, LIU Jian-ping, YANG Guo-xing. K-Means clustering analysis based on genetic algorithm［J］. Computer Engineering, 2008, 34(20): 200-202.
［12］ MAULIK U, BANDYOPADHYAY S. Fuzzy partitioning using a real-coded variable-length genetic algorithm for pixel classification［J］. Geoscience and Remote Sensing, IEEE Transactions on, 2003, 41(5): 1075-1081.
［13］ KWEDLO W. A clustering method combining differential evolution with the K-means algorithm［J］. Pattern Recognition Letters, 2011, 32(12): 1613-1621.
［14］ 何宏, 谭永红. 一种基于动态遗传算法的聚类新方法［J］. 电子学报, 2012, 40(2): 254-259.
HE Hong, TAN Yong-hong. A novel clustering method based on dynamic genetic algorithm［J］. Acta Electronica Sinica, 2012, 40(2): 254-259.
［15］ BANDYOPADHYAY S, MAULIK U. An evolutionary technique based on K-means algorithm for optimal clustering in RN［J］. Information Sciences, 2002, 146(1): 221-237.
［16］ 钟将,吴中福,吴开贵,等.基于人工免疫网络的动态聚类算法［J］.电子学报,2004, 32(8): 1268-1272.
ZHONG Jiang, WU Zhong-fu, WU Kai-gui, et al. A novel dynamic clustering algorithm based on artificial immune network［J］. Acta Electronica Sinica, 2004, 32(8): 1268-1272.
［17］ BANDYOPADHYAY S, MAULIK U. Genetic clustering for automatic evolution of clusters and application to image classification［J］. Pattern Recognition, 2002, 35(6): 1197-1208.
［18］ HORTA D, NALDI M, CAMPELLO R, et al. Evolutionary fuzzy clustering: an overview and efficiency issues［M］∥ Foundations of Computational Intelligence Volume 4. Berlin Heidelberg: Springer,2009: 167-195.
［19］ PLACKETT R L. Karl Pearson and the chi-squared test［EB/OL］. \[2012-12-19\]. htpp:∥as. wiley. com/wiley CDA/Wiley Title/productCd-INSR. html. 1983: 59-72.
［20］ STORN R, PRICE K. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces［J］. Journal of Global Optimization, 1997, 11(4): 341-359.
［21］ DEMPSTER A P, LAIRD N M, RUBIN D B. Maximum likelihood from incomplete data via the EM algorithm［J］. Journal of the Royal Statstical Society. Series B (Methodological), 1977,39(1): 138.
［22］ FRANK A, ASUNCION A. UCI machine learning repository ［DB/OL］. ［2013-02-23］.http: ∥archive.ics.uci.edu/ml/datasets/Iris.
［23］ NALDI M C, CAMPELLO R, HRUSCHKA E R, et al. Efficiency issues of evolutionary k-means［J］. Applied Soft Computing, 2011, 11(2): 1938-1952.
[1] 董立岩, 朱琪, 李永丽. 基于最大共识的模型组合算法[J]. 浙江大学学报(工学版), 2017, 51(2): 416-421.
[2] 苗峰,谢安桓,王富安,喻峰,周华. 多阶段可替换分组并行机调度问题的求解[J]. 浙江大学学报(工学版), 2015, 49(5): 866-872.
[3] 孔勇奇, 潘志庚. 基于抽风矢量场的深度凹陷图像分割算法[J]. 浙江大学学报(工学版), 2014, 48(6): 1024-1033.
[4] 刘加海,杨茂林,雷航,廖勇. 共享资源约束下多核实时任务分配算法[J]. J4, 2014, 48(1): 113-117.
[5] 赵诗奎, 方水良, 顾新建. 柔性车间调度的新型初始机制遗传算法[J]. J4, 2013, 47(6): 1022-1030.
[6] 张俊超, 岳茂雄, 刘华锋. 结构先验约束的动态PET图像重建[J]. J4, 2012, 46(6): 961-966.
[7] 刘毅,李平,高增梁. 用于高炉铁水质量预报的改进支持向量回归[J]. J4, 2012, 46(5): 830-836.
[8] 喻海清, 刘毅, 陈坤, 纪俊, 李平. 鲁棒的递推核学习建模方法在高炉过程的应用[J]. J4, 2012, 46(4): 705-711.
[9] 方水良, 姚嫣菲, 赵诗奎. 柔性车间调度的改进遗传算法[J]. J4, 2012, 46(4): 629-635.
[10] 刘加海,杨茂林. 基于多核处理器平台的公平调度算法[J]. J4, 2011, 45(9): 1566-1570.
[11] 徐敬华, 张树有, 伊国栋, 屠立, 光耀. 面向目标变异的操作臂运动学优化设计[J]. J4, 2011, 45(2): 209-216.
[12] 倪何, 程刚, 孙丰瑞. 基于混合演化的自适应建模及其应用[J]. J4, 2010, 44(8): 1490-1495.
[13] 戴文战, 熊伟, 杨爱萍. 基于函数cot (xα)变换及背景值优化的灰色建模[J]. J4, 2010, 44(7): 1368-1372.
[14] 陈坤, 刘毅, 王海清, 等. Hammerstein系统递推辨识的自适应算法[J]. J4, 2010, 44(1): 99-103.
[15] 杨珂, 罗琼, 石教英. 图形处理器在数据库技术中的应用[J]. J4, 2009, 43(8): 1349-1360.