(19)中华人民共和国国家知识产权局
(12)发明专利申请
(10)申请公布号 (43)申请公布日 (21)申请号 201910242200.0
(22)申请日 2019.03.28
(71)申请人 山东浪潮云信息技术有限公司
地址 250100 山东省济南市高新区浪潮路
1036号浪潮科技园S06号楼
(72)发明人 王利鑫
(74)专利代理机构 济南信达专利事务所有限公
司 37100
代理人 姜明
(51)Int.Cl.
G06K 9/62(2006.01)
G06N 3/12(2006.01)
(54)发明名称
一种基于遗传算法的数据聚类分析方法
(57)摘要
本发明特别涉及一种基于遗传算法的数据
聚类分析方法。该基于遗传算法的数据聚类分析
方法，首先从要聚类的样本集选出初始种群；对
选出的初始种群执行遗传算法；对执行完遗传算
法后产生的新种群执行K -means操作；步骤(A)-
步骤(C)反复循环，直到寻找出聚类问题的最优
解。该基于遗传算法的数据聚类分析方法，将K -
means算法的局部寻优与遗传算法的全局寻优相
结合，通过多次选择、交叉、变异的遗传操作，最
终得到最优的聚类数和初始质心集，克服了传统
K -means算法的局部性和对初始聚类中心的敏感
性，
实现了对数据的有效分类。权利要求书2页 说明书6页CN 110188785 A 2019.08.30
C N 110188785
A
1.一种基于遗传算法的数据聚类分析方法，其特征在于，包括以下步骤：
(A)首先从要聚类的样本集选出初始种群；
(B)对选出的初始种群执行遗传算法；
(C)对执行完遗传算法后产生的新种群执行K -means操作；
(D)步骤(A)-步骤(C)反复循环，直到寻找出聚类问题的最优解。
2.根据权利要求1所述的基于遗传算法的数据聚类分析方法，其特征在于：所述步骤
(A)中，初始群体随机生成，具体步骤如下：
(1)首先从样本空间中随机选出k个个体，每个个体表示一个初始聚类中心；
(2)然后根据所采用的编码方式将这组随机选出的初始聚类中心编码成一条染色体；
(3)重复进行m次染色体初始化，直到生成初始种群，所述m为种群大小。
3.根据权利要求2所述的基于遗传算法的数据聚类分析方法，其特征在于：所述步骤
(2)中，染色体编码采用基于聚类中心的浮点数编码方法。
4.根据权利要求1所述的基于遗传算法的数据聚类分析方法，其特征在于：所述步骤
(B)中，对选出的初始种群执行遗传算法，包括以下步骤：
(1)采用锦标赛选择法进行选择操作，随机地从种群中挑选一定数目的个体，然后从中选出适应度最大的个体作为父个体，重复迭代该步骤直到父个体的总数达到种群规模；
(2)采用适合浮点数编码的算术交叉算子对两个相互配对的染色体进行交叉操作，形成两个新的个体；
(3)采用均匀变异算子对交叉操作得到的新个体染色体编码串进行变异操作，从而形成一个新的个体。
5.根据权利要求4所述的基于遗传算法的数据聚类分析方法，其特征在于：所述步骤
(1)中，适应度是用来评价个体的适应度，区别群体中个体优劣的标准；个体的适应度越高，其存活的概率就越大；由于聚类准则函数J越小说明聚类划分的质量越好，聚类准则函数J 越大说明聚类划分的质量越差，
因此适应度函数表示为：
其中，
聚类准则函数J公式为：
其中，k为聚类类别数，S j 为第j个类别的样本集合，x为样本对象，z j 为S j 集合的聚类中心。
6.根据权利要求4所述的基于遗传算法的数据聚类分析方法，其特征在于：所述步骤
(2)中，交叉操作是指对两个相互配对的染色体按某种方式相互交换部分基因，从而形成两个新的个体；算术交叉是指由两个个体的线性组合而产生出两个新的个体；
当在两个个体x 1和x 2之间进行算术交叉时，
交叉操作后产生的新个体为：
其中，α是交叉参数，在均匀算术交叉中α是一个常数。
权 利 要 求 书1/2页2CN 110188785 A
