A Quantum-inspired Genetic Algorithm for data clustering
A Quantum-inspired Genetic Algorithm for data clustering
复制标题
DOI：
10.1109/cec.2008.4630993
复制
发表时间：
2008-06
期刊：
影响因子：
--
通讯作者：
Jing Xiao;YuPing Yan;Ying-biao Lin;Ling Yuan;Jun Zhang
中科院分区：
文献类型：
--
作者：
Jing Xiao;YuPing Yan;Ying-biao Lin;Ling Yuan;Jun Zhang
传统的k-means聚类算法必须事先知道聚类的个数，聚类结果对初始聚类中心的选择很敏感。敏感性可能使算法收敛于局部最优。提出了一种基于量子遗传算法的改进k-means聚类算法。KMQGA采用基于Q位的表示方法，通过量子门的旋转操作以及Q位的选择、交叉和变异操作，实现离散0-1超空间的探索和利用。在不事先知道簇的确切数量的情况下，KMQGA可以得到最佳的簇数量，并在四个操作（选择，交叉，变异和旋转）的几次迭代后提供最佳的簇质心。分别用模拟数据集和真实的数据集对KMQGA进行了验证，并与基于著名的变字符串长度遗传算法的改进k均值聚类算法（KMVGA）进行了比较。实验结果表明，KMQGA是有前途的，KMQGA的效率和搜索质量优于KMVGA。
The conventional k-means clustering algorithm must know the number of clusters in advance and the clustering result is sensitive to the selection of the initial cluster centroids. The sensitivity may make the algorithm converge to the local optima. This paper proposes an improved k-means clustering algorithm based on quantum-inspired genetic algorithm (KMQGA). In KMQGA, Q-bit based representation is employed for exploration and exploitation in discrete 0-1 hyperspace by using rotation operation of quantum gate as well as three genetic algorithm operations (selection, crossover and mutation) of Q-bit. Without knowing the exact number of clusters beforehand, the KMQGA can get the optimal number of clusters as well as providing the optimal cluster centroids after several iterations of the four operations (selection, crossover, mutation, and rotation). The simulated datasets and the real datasets are used to validate KMQGA and to compare KMQGA with an improved k-means clustering algorithm based on the famous variable string length genetic algorithm (KMVGA) respectively. The experimental results show that KMQGA is promising and the effectiveness and the search quality of KMQGA is better than those of KMVGA.