大数据挖掘中的K?means无监督聚类算法的改进

吴海丽

摘  要： 针对K?means聚类算法简单，并且收敛速度比较快的问题，提出基于大数据挖掘的K?means无监督聚类算法。此算法设置一定范围，在迭代次数不断动态增加中，交叉算法增加，从而使算法在迭代过程中实现全局搜索，再实现局部搜索，有助于平衡算法全局寻优及局部搜索能力，使算法收敛速度加快。对K?means聚类算法和标准差分进化算法进行分析，提出K?means聚类算法的改进，给出算法改进的步骤，利用实验对算法进行仿真。通过仿真结果表示，此算法聚类效果良好，聚类划分精度和稳定性高，还具有较高的稳定性。

关键词： 大数据挖掘; 差分进化算法; K?means聚类算法; 全局寻优; 鲁棒性; 收敛速度

中图分类号： TN911.1?34; TP391                  文献标识码： A                    文章编号： 1004?373X（2020）19?0118?04

Abstract： In view that the K?means clustering algorithm is simple and its convergence speed is fast， an unsupervised K?means clustering algorithm based on big data mining is proposed. In the algorithm， a certain range is set， the crossover algorithm increases when the number of iterations increases dynamically， so that the algorithm can achieve global search and then local search in the iterative process. Therefore， it is helpful to balance the global optimization and local search ability of the algorithm， which accelerates the convergence speed of the algorithm. The K?means clustering algorithm and the standard differential evolution algorithm are analyzed. And then， the K?means clustering algorithm is improved and the steps of algorithm improvement are given. Finally， the algorithm is simulated in experiments. The simulation results show that the algorithm has good clustering effect， high clustering partition accuracy and stability.

Keywords： big data mining; differential evolution algorithm; K?means clustering algorithm; global optimization; robustness; convergence rate

0  引  言

优化的主要目的就是寻找最优方案，虽然目前常规优化方法中存在部分问题，尤其在面临多峰、高维、函数结构复杂等问题时，求解精度和算法时间复杂度无法满足设计需求，所以要更加系统地研究该问题。进化算法编程简单，利用特殊进化测量能够使种群质量得到提高，从而得到明确的算法寻优方向[1]。K?means聚类算法属于常见聚类方法，使用较为广泛，比如，对不同客户群体购物习惯进行解析，实现客户细分;对消费者不同需求特征进行分析，使产品市场按不同消费市场进行细分。因为传统K?means算法对于聚类中心敏感，无法有效确定[K]值等问题，所以提出了K?means无监督聚类算法。

1  K?means聚类算法和标准差分进化算法

K?means均值聚类思想是以聚合中心距离与数据对象作为基础，将数据对象划分成为和距离比较近的集合。[K]属于K?means算法参数，使[m]个对象集合朝着最近子集进行划分，对比相同子集中的对象，子集数据对象的不同也存在一定的差别[2]。此算法步骤为：

1） 通过样本集选择[k]条数据样本作为初始[k]个集合中心;

2） 依据最近邻法则，将数据样本被划分到与其相互接近的集合;

3） 计算全新的类簇中心，可利用不同集合样本数据均值计算得出;

4） 不改变类簇中心，说明算法终止，到最终的结果进行返回;否则，跳至步骤2）进行返回计算。

此聚类算法中的主要问题就是对算法初始类簇中心进行选择，如果初始划分与全局最优划分出现问题，那么就会导致算法逐渐陷入局部最优。

交叉操作、变异操作为标准差分进化算法中的核心，其定义如下。

变异操作：变异操作中全新的个体是通过群体单个或者多个线性进行计算得出，差分进化算法中的变异机制比较多，以下公式中使用大量的变异策略。

交叉操作：利用现代个体[ci]中的分量和目标个体进行转变，实现测试个体[ti]的生成。二项交叉与指数交叉为主要的交叉方式，在执行二项交叉过程中，是将每条染色体中的分量作为基础，从而实现0～1之间随机数量[r]的生成。假如[r]比CR小，目标个体相应分量进行接收;否则，将目前个体分量进行保留[3?4]。

选择操作：利用贪心实现选择差分进化（DE）标准，目前[ci]对比测试个体[ti]，利用更好个体实现下一代搜索。

2  算法的改进

2.1  改进思路

控制参数对于DE算法的影响比较大，目前学术界对于参数研究并没有系统性结论，对DE算法在现实中的使用具有一定的影响。国内外相关研究人员提出了多种集成算法模型及框架，此算法具备鲁棒性与普适性，并且效果良好。目前，也出现了基于静态知识的DE集成算法，静态知识也称为经验知识，主要表示知识初级形态。

使用新变异算法的改进：相关研究人员受到PSO优化算法的影响，通过两个极值更新个体位置与速度的启发，提出全新变异因子，此因子通过两个位置信息：局部邻域良好个体位置信息、全局最优个体位置信息得到。算法为：

2.2  算法的具体操作

2.2.1  种群初始化

因为DE算法在进化初期缺少相应的经验知识，只能够在可行域内随机出现初始种群，从而降低了算法进化初期的收敛速度。如果初始种群个体到全局最优距离比较近，能够有效加快算法收敛速度。所以为了使算法在进化初期的收敛速度得到提高，通过反向学习方法及混沌搜索相互结合的方式实现初始种群的产生，使初始种群质量得到提高。先使用Logistis映射生成混沌序列，使算法初始随机数质量得到提高[4?5]，具体描述为：

式中：[xi]指混沌序列变量在第[i]次迭代过程中的值;[v]为变量控制常数，在其取值范围为[3.56，4.0]时，[xi]为混沌变量，这时系统在完全混沌的状态中，混沌序列不會重复。算法根据反向学习方法，能够实现所有混沌序列个体的反向个体生成，之后对反向个体及混沌序列种群进行合并，并且实现以上种群全部个体，根据适应度函数值大小进行排列，最后使用其中相应规模比较优的个体构成初始种群。

混沌搜索的反向学习过程为：

3） 实现种群[P]与[OP]的合并，规模设置为2[NP]。根据适应度函数大小实现排列，从中选择[NP]规模的优化个体构成算法初始种群。

2.2.2  函数适应度设计

利用适应度函数、遗传算法能够评价种群个体适应度，并且区分种群个体的优劣程序。存活概率和个体适应度两者具有正比的关系，可提高适应度和存活的可能性。K?means聚类算法指的是目标函数[G]寻找过程中的最小划分[5?7]。

在算法操作过程中，划分染色体编码的初始种群，对不同聚类点到聚类中心进行聚类计算，使其成为目标函数[G]。通过目标函数对聚类划分效果进行判断，目标函数[G]越小，聚类效果越好。

利用标准DE算法搜索目标函数解空间，以此得到目标函数最小值。那么，本文以目标函数实现适应度函数的创建：

2.2.3  算子选择

通过模仿生物界实现遗传算法，在选择操作时使生物界优胜劣汰的规则得到满足。操作选择将种群个体适应度值作为基础，利用父代个体对个体进行选择，遗传到下一代。算法设计与概率选择具有密切的关系，个体[xi]的选择概率为：

2.2.4  自适应交叉与变异算子

通过选择变异概率和交叉概率，能够有效实现遗传操作，对遗传算法计算结果造成影响。对于交叉算子来说，随着交叉概率不断增加的过程，就会提高个体生成的速度，在交叉概率比较小时，就会降低遗传搜索的速度;对于变异算子来说，个体在小变异概率中并不新颖，在大变异概率时，会失去遗传算法的效果，朝着随机搜索算法转变。

对于上述变异操作与交叉操作存在的问题，本文利用自适应交叉实现操作。[Pc]与[Pm]能够以不同情况实现自我调节，公式为：

式中：[fmax]指群体中最大适应度值;[favg]指群体平均适应度值;[f]指交叉的两个个体中较大的适应度值;[f]指变异个体适应度值;[k1]，[k2]，[k3]，[k4]取（0，1）区间的值。假如没有定义[k1]，[k2]，[k3]，[k4]的根据，可以初始确定四者的值，利用[Pc]与[Pm]对比相同优化目标下的进化代数，对应进化代数比较少的[Pc]和[Pm]是较优的，那么对应[k1]，[k2]，[k3]，[k4]也比较合理。

2.2.5  算法流程

输入：输入内容主要包括聚类样本集、种群大小、最大迭代次数、自适应交叉与变异系数。

输出：最优聚类中心与数量[9?11]。

算法描述如下：

1） 进化参数的设置。

2） 通过染色体的编码方案生成初始种群。

3） 对个体适应度值进行计算。

4） 对最好个体计算，对最好适应度和平均适应度进行记录。

5） 进行交叉、变异、选择等操作。

6） 计算个体适应度，寻找最大适应度的个体，替代上一次最大的适应度个体。

7） 对是否为最大迭代次数进行判断，假如是，就进行下一步;否则，回到步骤5）。

8） 实现最优聚类中心的输出，并且实现聚类操作。

9） 聚类结果的输出。

算法的具体操作流程如图1所示。

3  算法仿真

为了对算法的有效性进行验证，本文使用常用数据集进行实验。表1给出了数据集名称、数据对象数量与属性个数。为了保证对比的有效性，设置改进K?means算法内容为：相关ACDE函数保留原本参数设置，种群大小[NP]设置为100，最大迭代次数[Imax]设置为[11?13]200，阈值参数为3。均值与方差对比结果见表2。

本文使用DB指标作为本文算法中函数的优化选择，将20次最终DB值均值（mean）与方差（std）作为评价标准，并且通过聚类数均值和方差对算法聚类性能进行评价。通过表2可以看出，本文算法均值与方差比较小，并且接近于数据集实际种类，所以，不管是聚类效果或者稳定性，本文算法更好。另外，本文算法误分率也比较小，表示本文算法的聚类划分精度要高[13?15]。

4  结  语

在本文研究过程中基于DE算法实现动态交叉算法的设计，有效结合K?means算法和遗传算法，能够使收敛速度得到提高。通过实验结果可知，本文算法聚类效果良好，并且聚类划分精度较高，还具有较高的稳定性，提高了搜索效果。

参考文献

[1] 王勇臻，陈燕，张金松.一种改进的求解聚类问题的差分进化算法[J].计算机应用研究，2016，33（9）：2630?2633.

[2] 申彦，朱玉全.CMP上基于数据集划分的K?means多核优化算法[J].智能系统学报，2015，15（4）：607?614.

[3] 胡先兵，赵国庆.引入时频聚集交叉项干扰抑制的大数据聚类算法[J].计算機科学，2016，43（4）：197?201.

[4] 王雪梅，李晓峰，高巍巍.一种改进的K?Means聚类算法的研究[J].计算机与数字工程，2013，41（11）：1717?1719.

[5] 胡春华.基于自适应差分进化算法拟合圆的树干胸径测量方法[J].农业机械学报，2018，49（9）：183?188.

[6] 刘莉莉，曹宝香.基于差分进化算法的K?Means算法改进[J].计算机技术与发展，2015，21（10）：88?92.

[7] 刘飞，唐雅娟，刘瑶.K?means聚类算法中聚类个数的方法研究[J].电子设计工程，2017，25（15）：9?13.

[8] 李运娣，文政颖，于海鹏.基于k?means算法和相关反馈信息的图像检索方法[J].福建电脑，2015（5）：19?20.

[9] 吴雅琴，王晓东.大数据挖掘中的混合差分进化K?Means无监督聚类算法[J].重庆理工大学学报（自然科学），2019，15（5）：107?112.

[10] 王凤领.一种改进差分进化的自动聚类算法研究[J].数学的实践与认识，2018，48（21）：187?194.

[11] 王明威，万幼川，高贤君，等.纹理影像特征选择及K?means聚类优化方法[J].国防科技大学学报，2017，39（6）：152?159.

[12] 樊一康，刘建伟.支持差分隐私保护及离群点消除的并行K?means算法[J].计算机应用研究，2019，15（6）：1776?1781.

[13] 周艳平，蔡素，李金鹏.一种粒子群和改进自适应差分进化混合算法及在生产调度中的应用[J].计算机测量与控制，2019，27（8）：227?230.

[14] 宋鑫宏，张乐，方光辉.基于Voronoi盲区的差分进化WSN部署算法[J].软件导刊，2017，16（4）：59?61.

[15] 胡闯，杨庚，白云璐.面向差分隐私保护的聚类算法[J].计算机科学，2019，46（2）：120?126.