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