计算机应用 ›› 2011, Vol. 31 ›› Issue (09): 2546-2550.DOI: 10.3724/SP.J.1087.2011.02546

• 人工智能 • 上一篇    下一篇

基于量子遗传谱聚算法的聚类

蒋勇1,谭怀亮2,李光文1   

  1. 1. 湖南化工职业技术学院 信息工程系,湖南 株洲 412004
    2. 湖南大学 计算机与通信学院,长沙 410082
  • 收稿日期:2011-03-23 修回日期:2011-06-10 发布日期:2011-09-01 出版日期:2011-09-01
  • 通讯作者: 蒋勇
  • 基金资助:
    教育部博士点基金资助项目(200805321029);湖南省自然科学基金资助项目(07JJ6139)

Clustering based on quantum genetic spectral clustering algorithm

JIANG Yong1,TAN Huai-liang2,LI Guang-wen1   

  1. 1. Department of Information Engineering, Hunan Chemical Industry Vacation Technology College, Zhuzhou Hunan 412004, China
    2. School of Computer and Communication, Hunan University, Changsha Hunan 410082, China
  • Received:2011-03-23 Revised:2011-06-10 Online:2011-09-01 Published:2011-09-01
  • Contact: JIANG Yong

摘要: 在处理大数据集聚类问题上,谱聚算法因存在占用存储空间大、时间复杂度高的缺陷而难以推广,针对此问题,提出采用多次分割、向上向下双向收缩的QR算法求得特征值对应的特征向量来实现降维,并在此基础上构造映射空间上的样本来实现量子遗传谱聚算法的聚类。该方法通过映射为后续的量子遗传谱聚算法聚类提供低维的输入,而量子遗传算法具有快速收敛到全局最优并且对初始化不敏感的特性,从而可以获得良好的聚类结果。实验结果显示,使用该算法的聚类比谱聚算法、K-means算法、NJW算法等单一方法具有更好的收敛性、稳定性和更高的全局最优。

关键词: 特征值分解, QR分割, 谱聚类算法, 量子遗传谱聚算法

Abstract: On clustering large data, the spectral clustering can hardly be promoted because of large occupied storage space and high time complexity. Hence, multi-segment and upward and downward double-direction shrink QR algorithm for the corresponding eigenvectors of eigenvalues was adopted to achieve dimensionality reduction. Then, a new quantum genetic spectral clustering algorithm was proposed to cluster the sample points in the mapping space. Compact input with low-dimension for quantum genetic spectral clustering was obtained after mapping, and the quantum genetic spectral clustering algorithm, characterized by its rapid convergence to global optimum and minimal sensitivity to initialization, can obtain good clustering results. The experimental results show that the proposed method is superior to the spectral clustering algorithm, K-means, NJW algorithm in astringency and stability and has a higher overall optimal solution.

Key words: eigenvalue decomposition, QR segmentation, spectral clustering algorithm, quantum genetic spectral clustering algorithm

中图分类号: