论文部分内容阅读
中图分类号：NA 文献标识码：A 文章编号：1671－7597（2011）0310019－01
0 引言
K-means算法是聚类分析中一种基本的聚类方法[1]，因其简单可靠而被广泛使用，但传统的K均值算法受初始聚类中心的影响而过早地收敛于局部最优解。于是人们考虑将遗传算法应用于K-means聚类分析来解决上述相关问题的。随着遗传算法理论基础和应用技术的逐渐成熟，近年来涌现出了大量的基于遗传算法进行聚类分析的新算法。
量子遗传算法（Quantum Genetic Algorithm, QGA）[3]是近期产生的一种概率进化算法，它以量子计算的一些概率和理论为基础。相比传统遗传算法QGA具有很多优点，但是也存在随机性和繁琐的编解码等缺点。本文采用实数编码三倍染色体表达的方法对传统QGA作了改进，并将改进后的量子遗传算法用于K均值聚类，实验结果表明本文提出的量子遗传算法K均值聚类算法的收敛性能优于传统K均值聚类算法。
1 K-means算法的基本思想
假定用户划分数为K，首先任意选取K个点作为中心，计算剩余点到各个中心的距离，以最近为原则进行归属，基于给定的聚类目标函数，每次迭代使内部对象相似性越来越大，类间对象的相似性越来越小。
K-means聚类算法的基本步骤为：
1）任意选择K个对象作为初始的簇中心；
2）计算各个对象到簇中心的距离，以最近原则进行划归；
3）更新中心点，即计算每个簇中对象的平均值；
4）如果簇的划分发生改变则转2），否则结束。
以最小化欧氏距离平方和为基础描述的K-means聚类问题为：对于给定数据空间Rm中的n个数据目标，分别将数据目标分配到K个簇中，以使得每个目标到其所在簇中心的欧氏距离平方和最小：
2 改进的量子遗传算法
2.1 量子遗传算法
在QGA中，用量子比特来表达和存储一个基因，该基因可以为“0”态或“1”态，或两者之间的任一状态，即该基因所表达的不再是某一确定的信息，而是包含所有可能的信息，对该基因的任一操作也会同时作用于所有可能的信息。一个由m 个量子比特构成的量子染色体可以描述为：
在量子遗传算法中，采用量子旋转门来实现量子状态的更新和演化，通常设计量子旋转门如下：
QGA采用式3-1所表示的量子位染色体表示种群，通过测量染色体上量子位的状态来生成所需要的二进制解，采用量子门作用于量子位概率幅度来保持种群的多样性。但是测量这是一个概率操作过程，具有很大的随机性和盲目性，而且其编码复杂，计算精度受编码位的限制，并不适合高维多极值函数的优化。
2.2 实数染色体的表达
3 基于改进量子遗传算法的K-均值聚类算法
本文将量子遗传算法和聚类分析相结合，通过量子遗传算法的全局优化能力与聚类分析的局部优化能力相结合来克服聚类算法的局部性。相比于基本的量子遗传算法，基于改进量子遗传算法的K-均值聚类算法也是从随机产生初始种群开始，只是在种群进化的过程中，完成种群进化操作后对产生的新种群的个体引入K均值优化操作，然将优化后的结果作为下一代的种群。
该算法流程描述如下：
1）初始化种群，从给定数据中任意选取K个点作为中心点，并按照式（2-4）编码，产生初始种群；
2）对种群中的每个个体按照式（1-1）计算个体的适应度值；
3）根据上一步计算出的值，对种群做互补双变异操作；
4）达到一定间隔时对适应度值低的个体做离散交叉操作，以此产生新的种群；
5）对上一步产生的新种群中每个个体执行K-means操作，并将其优化为以该个体为初始值的K均值问题的局部最优解，产生新一代的种群；
6）判断条件是否结束，如未结束转向第3）步继续操作。
4 实验结果与分析
为了检验算法的有效性，对K-均值算法，基于遗传算法的K-均值聚类算法[2]和本文提出的基于改进量子遗传算法的K-均值聚类算法进行对比试验。在Matlab环境下分别编写这三种算法。实验数据集的属性见表1所示。
实验结果分析：根据表2的实验结果，K-均值算法受初始化的影响很大，容易陷入局部最优解，不是每次都能达到最优解，特别是对于glass这种高维度的数据集，没有遗传达到全局最优解。遗传算法和改进的量子免疫遗传算法克服了K-均值的上述缺点；同时通过比较遗传聚类算法(GKA)和改进的量子遗传聚类算法(IQGKA)对每组数据20次实验，IQGKA每次都能达到最优解，而在平均迭代次数上，IQGKA的平均迭代步数都有比GKA要少。因此，改进的量子遗传聚类算法的收敛速度也比较快。
5 结束语
本文提出了一种改进的量子遗传聚类算法，克服传统二进制编码量子遗传算法繁琐编解码问题和K-均值聚类算法对初始值敏感的缺点。通过对相关数据集的测试，并与基于遗传算法的K-均值聚类算法进行比较。实验结果表明：本文提出的改进的量子遗传聚类算法其聚类性能要优于基于遗传算法的K-均值聚类算法和传统的K-均值聚类算法，尤其对于较大数据集具有较高的效率与较好的适用性。
作者简介：
邱冬生（1984-），男，硕士研究生，主要研究方向为量子信息处理。
0 引言
K-means算法是聚类分析中一种基本的聚类方法[1]，因其简单可靠而被广泛使用，但传统的K均值算法受初始聚类中心的影响而过早地收敛于局部最优解。于是人们考虑将遗传算法应用于K-means聚类分析来解决上述相关问题的。随着遗传算法理论基础和应用技术的逐渐成熟，近年来涌现出了大量的基于遗传算法进行聚类分析的新算法。
量子遗传算法（Quantum Genetic Algorithm, QGA）[3]是近期产生的一种概率进化算法，它以量子计算的一些概率和理论为基础。相比传统遗传算法QGA具有很多优点，但是也存在随机性和繁琐的编解码等缺点。本文采用实数编码三倍染色体表达的方法对传统QGA作了改进，并将改进后的量子遗传算法用于K均值聚类，实验结果表明本文提出的量子遗传算法K均值聚类算法的收敛性能优于传统K均值聚类算法。
1 K-means算法的基本思想
假定用户划分数为K，首先任意选取K个点作为中心，计算剩余点到各个中心的距离，以最近为原则进行归属，基于给定的聚类目标函数，每次迭代使内部对象相似性越来越大，类间对象的相似性越来越小。
K-means聚类算法的基本步骤为：
1）任意选择K个对象作为初始的簇中心；
2）计算各个对象到簇中心的距离，以最近原则进行划归；
3）更新中心点，即计算每个簇中对象的平均值；
4）如果簇的划分发生改变则转2），否则结束。
以最小化欧氏距离平方和为基础描述的K-means聚类问题为：对于给定数据空间Rm中的n个数据目标，分别将数据目标分配到K个簇中，以使得每个目标到其所在簇中心的欧氏距离平方和最小：
2 改进的量子遗传算法
2.1 量子遗传算法
在QGA中，用量子比特来表达和存储一个基因，该基因可以为“0”态或“1”态，或两者之间的任一状态，即该基因所表达的不再是某一确定的信息，而是包含所有可能的信息，对该基因的任一操作也会同时作用于所有可能的信息。一个由m 个量子比特构成的量子染色体可以描述为：
在量子遗传算法中，采用量子旋转门来实现量子状态的更新和演化，通常设计量子旋转门如下：
QGA采用式3-1所表示的量子位染色体表示种群，通过测量染色体上量子位的状态来生成所需要的二进制解，采用量子门作用于量子位概率幅度来保持种群的多样性。但是测量这是一个概率操作过程，具有很大的随机性和盲目性，而且其编码复杂，计算精度受编码位的限制，并不适合高维多极值函数的优化。
2.2 实数染色体的表达
3 基于改进量子遗传算法的K-均值聚类算法
本文将量子遗传算法和聚类分析相结合，通过量子遗传算法的全局优化能力与聚类分析的局部优化能力相结合来克服聚类算法的局部性。相比于基本的量子遗传算法，基于改进量子遗传算法的K-均值聚类算法也是从随机产生初始种群开始，只是在种群进化的过程中，完成种群进化操作后对产生的新种群的个体引入K均值优化操作，然将优化后的结果作为下一代的种群。
该算法流程描述如下：
1）初始化种群，从给定数据中任意选取K个点作为中心点，并按照式（2-4）编码，产生初始种群；
2）对种群中的每个个体按照式（1-1）计算个体的适应度值；
3）根据上一步计算出的值，对种群做互补双变异操作；
4）达到一定间隔时对适应度值低的个体做离散交叉操作，以此产生新的种群；
5）对上一步产生的新种群中每个个体执行K-means操作，并将其优化为以该个体为初始值的K均值问题的局部最优解，产生新一代的种群；
6）判断条件是否结束，如未结束转向第3）步继续操作。
4 实验结果与分析
为了检验算法的有效性，对K-均值算法，基于遗传算法的K-均值聚类算法[2]和本文提出的基于改进量子遗传算法的K-均值聚类算法进行对比试验。在Matlab环境下分别编写这三种算法。实验数据集的属性见表1所示。
实验结果分析：根据表2的实验结果，K-均值算法受初始化的影响很大，容易陷入局部最优解，不是每次都能达到最优解，特别是对于glass这种高维度的数据集，没有遗传达到全局最优解。遗传算法和改进的量子免疫遗传算法克服了K-均值的上述缺点；同时通过比较遗传聚类算法(GKA)和改进的量子遗传聚类算法(IQGKA)对每组数据20次实验，IQGKA每次都能达到最优解，而在平均迭代次数上，IQGKA的平均迭代步数都有比GKA要少。因此，改进的量子遗传聚类算法的收敛速度也比较快。
5 结束语
本文提出了一种改进的量子遗传聚类算法，克服传统二进制编码量子遗传算法繁琐编解码问题和K-均值聚类算法对初始值敏感的缺点。通过对相关数据集的测试，并与基于遗传算法的K-均值聚类算法进行比较。实验结果表明：本文提出的改进的量子遗传聚类算法其聚类性能要优于基于遗传算法的K-均值聚类算法和传统的K-均值聚类算法，尤其对于较大数据集具有较高的效率与较好的适用性。
作者简介：
邱冬生（1984-），男，硕士研究生，主要研究方向为量子信息处理。