大数据技术及遗传算法在数据挖掘中的应用研究.pdf

该文对关联规则挖掘、遗传算法和 Hadoop 平台等相关技术进行了介绍，在此基础上通过使用关联规则支持度来定义遗传算法的适应度函数，采用实数编码的方式对烘焙食品连锁店的交易数据属性值进行编码，形成染色体.为解决交叉概率和变异概率变化范围有限的问题，对两个概率公式进行自适应的优化.然后设计搭建了结合关联规则和遗传算法的连锁门店大数据挖掘平台.同时运用所设计的大数据平台收集数据对改进的遗传算法进行了实验验证，证实优化后的算法在处理复杂数据属性和收敛性上都具有一定优势.关键词：遗传算法；Hadoop；关联规则；适应度函数；遗传算子中图分类号：TP301.6文献标志码：A文章编号：1008-7974（2023）08-0080-08DOI：10.13877/22-1284.2023.08.014互联网技术和海量数据存储技术的发展，使得人们可以收集更多的数据，数据挖掘技术的诞生为人们有效利用这些数据提供了新的方法.面对糕点类连锁门店品类繁多且不断变换的商品，商家应快速地分析和运用每天产生的大量销售数据，在顾客进店时或者购买过程中及时向其推荐可能感兴趣的商品或者信息，从而提高销售效率和销售量.此外，商家也可以将数据挖掘结果所提供的特征用于新产品的开发，生产出可能受顾客欢迎的产品.遗传算法（Genetic algorithm，GA）作为一种随机并行搜索算法，应用较为广泛，它也是数据挖掘过程中的常用算法1.遗传算法在应用过程中可以通过调整其交叉算子和变异算子进行优化，比如对两个算子进行自适应改进，可以达到全局最优解与收敛速度的最佳平衡2；通过模糊 GA 和关联规则的合理融合实现更好的挖掘效果3；通过非线性排序减少 近 亲 遗 传，从 而 起 到 提 高 搜 索 效 率 的 作用4.为了获得更佳的挖掘效果，针对本研究数据特点，将遗传算法和关联规则算法进行 80越 缙：大数据技术及遗传算法在数据挖掘中的应用研究结合，根据问题实际情况对遗传算法进行自适应改进，混合成新的挖掘算法.同时利用了遗传算法天然的并行处理特性，搭建连锁门店的 Hadoop 集群，对多个门店产生的大量销售数据运用大数据技术部署新产生的挖掘算法，提升对数据的挖掘效率，最终挖掘出可用的关联规则，用于商品的销售推荐.1相关技术1.1关联规则关联规则是可以用X=Y的形式表示，X称为前项，Y称为后项.X和Y都是数据库中项集的一部分，X=Y表示X出现时Y也同时出现.衡量关联规则有用性和确定性有两个重要的量：支持度（sup）和置信度（conf）.对于商品交易来说，某段时间各次交易中同时包含X和Y两样商品的交易数 count（X=Y）与这段时间总的交易数D之比，就是这段时间X=Y的支持度，可记作：sup（X=Y）=count（X=Y）/D.关联规则的置信度是交易中同时包含X和Y两样商品的交易数 count（X=Y）与包含X的交易数 count（X）之比，可记作 conf（X=Y）=count（X=Y）/count（X）.判定关联规则是否有效，需要人为预先设定最小支持度（min_sup）和置信度最小值（min_conf），当计算出的关联规则支持度和置信度不小于阈值，就可以认为这个关联规则是有效的.关联规则的计算需要不断搜索频繁模式，反复地对交易数据库进行重复扫描，常用的挖掘算法有 Apriori 和 FP-Growth5.Apriori 算法挖掘过程中产生大量的频繁模式，有着较大的时间和空间复杂度开销.FP-Growth 算法通过生成条件模式库并构造频繁模式树对Apriori 算法作了改进，使得挖掘效率得到了很大提高，但是对于海量数据来说，时间和空间复杂度仍然较大.1.2遗传算法遗传算法作为一种基于遗传学原理模拟自然进化过程进行搜索的随机并行搜索算法，在很多领域中都有成功的应用.它在运算过程中不需要像 Apriori 和 FP-Growth 那样产生大量的频繁模式，有利于提高挖掘过程的效率，另外遗传算法具有内在的并行性，适合在分布式系统上处理数据.遗传算法的应用需要构造解空间和遗传空间，重点需要确定染色体编码方案、个体适应度量化评价方法、设计遗传算子、确定遗传算法相关运行参数等.本文基于易于实现和操作方便考虑，使用实数对研究数据进行编码，利用实数数组对每次交易（个体）信息进行存储，实数数组的元素个数对应销售单的字段，数组元素的值对应字段的属性值.内容见表 1.表 1销售单数据库的字段和属性字段1属性值11属性值m1字段2属性值12属性值m2字段n属性值1n属性值mn销售单数据库中的个体编码就是一个元素个数为n的实数数列A，AN 为字段，i=1，2，3，N，用数值 0，1，2，Km表示字段AN 的值，例如，顾客性别这个字段有两个属性值，用 1 表示“男”，2 表示“女”.此外，用 0值表示某一属性与其他属性无关联或者属性值缺失不参加挖掘.适值度函数是用来区分种群中个体优劣的标准，是进行结果选择筛选的关键条件，是 812023 年第 8 期学 报遗传算法与所应用问题的唯一接口，需要根据所解决问题的特征设定适应度函数.在关联规则中，支持度对规则的筛选起到很重要的作用，支持度低说明规则出现的概率小，重要性相对较低，因此选择关联规则支持度作为本研究的适应度函数.fitness（Ri）=sup（Si）/min_sup（i=1，2，3，n），（1）其中：sup（Si）为经过遗传操作形成的一条新规则的支持度，min_sup 为最小支持度阈值，需要根据所解决问题的实际情况进行设定，本研究取min_sup的值为38%.fitness（Ri）1 时，对应规则会被保留到下一代，fitness（Ri）1 时，对应的规则在下一代遗传操作中被淘汰.本研究在选择算子的确定上，没有采取传统的赌轮盘方法，而是直接将适应度值大于 1 的规则都遗传到下一代.在交叉算子的确定上，使用简单的单点交叉，运用交叉概率Pc在父代个体中随机选择多对个体进行交叉，父代染色体交叉点位置也随机选定.在变异算子的确定上，为了提高搜索效率，先按照Pm的值在父代中随机挑选个体，然后对这些挑选出来的个体进行变异操作，变异过程是把每个个体里面每个基因位上的值都变异一次，这样基因位上的值都在取值允许范围内变更一次，同时保证属性值存在.1.3HadoopHadoop 是一个开源的、强大的分布式大数据开发平台，采用分布式存储与处理方法，可以部署在廉价的普通商用计算机上，解决了处理海量数据高成本、低效率的难题6.适合部署于连锁门店原有的计算机管理网络系统.Hadoop 系统最核心的是分布式文件系统HDFS 和分布式计算框架 MapReduce.HDFS 采用主从结构，为大量数据提供分布式存储，NameNode 为主节点，负责系统的管理，维护文件系统的文件树及所有文件和目录的元数据.其他 DataNode 为从节点，文件以数据块的形式存储其上.HDFS 的架构如图 1所示.图 1HDFS 的系统架构MapReduce 为海量数据提供分布式计算处理7，它也采用主/从架构，JokTracker 为主，TaskTracker 为从.用户提交的计算需求称为Job，每个 Job划分为若干个 Tasks，JokTracker 负责 Job 和 Tasks 的调度，TaskTracker 负责执行Tasks.MapReduce 的处理过程分为 Map 和 Reduce 两个主要阶段：Map 将一个函数应用于数据中的成员，生成一个结果集，再经过洗牌和分类后，最后使用 Reduce 过程进行分类归纳为.本文所研究的连锁门店商品销售数据实际上是分布在各个门店的计算机内，连锁门店总部设置有服务器，具备搭建完全分布式的 Hadoop 平台，实际应用中可根据门店具体情况决定是否接入.总部的服务器作为 NameNode 和 JokTracker 节点，另选一台总部计算机作为 Secondary NameNode 做数据恢复用.其他门店计算机作为 DataNode 和 TaskTracker 节点.节点分配及节点功能结构如图 2 所示.82越 缙：大数据技术及遗传算法在数据挖掘中的应用研究图 2Hadoop 平台环境搭建2遗传算法与关联规则的结合及改进遗传算法的交叉概率Pc和变异概率Pm这两个参数对算法的行为和性能有着极大的影响.交叉概率Pc较大时，新生个体产生速度快，某些适应度较高的个体染色体被破坏，遗传模式的可能性也较大，难以保留下去.如果Pc过小，会使得进化速度过慢，甚至停滞不前得不到最终解.对于变异概率Pm，如果过大，导致遗传算法成了随机搜索算法，如果过小，不易产生新的个体，得出解的速度很慢.为此，SRINVIVAS 等提出了一种自适应遗传算法，Pc和Pm能够随着适应度变化进行相应调整8，对于适应度高于群体平均值的个体，会使用较低的交叉和变异概率，促进适应度高的个体遗传到下一代，而低于平均适应值的个体，会使用较高的交叉和变异概率，避免其遗传到下一代.这样的改进有利于提高遗传算法的效率和实用性.参考文献 9 中给出了Pc和Pm自适应改进的表达式如下9：Pc=Pc1-(Pc1-Pc2)(f-favg)fmax-favg,f favg;Pc1,f favg;（2）Pm=Pm1-(Pm1-Pm2)(fmax-f)fmax-favg,f favg;Pm1,f favg;（3）式中：Pc1和Pc2为交叉概率，值预先设定为 0.9和 0.6，Pm1和Pm2为变异概率，值预先设定为0.1 和 0.001.fmax为群体中最大的适应度值，favg是每代群体的平均适应度值，f是两个要交叉的个体中较大的适应度值，f是要变异的个体的适应度值.考虑到本研究中，对于关联规则支持度表示的适应度函数，（f-favg）/（fmax-favg），以及（fmax-f）/（fmax-favg）变化范围不是很大，导致Pc或者Pm变化范围有限，自适应效果不明显.为此，对Pc和Pm的值作如下改进：令：s=f-favgfmax-favg,t=fmax-ffmax-favg;（4）Pc=Pc1-(Pc1-Pc2)tanh(s2),f favg;Pc1,f favg;（5）Pm=Pm1-(Pm1-Pm2)tanh(t),f favg;Pm1,f Y）/sup（X）*sup（Y）.（7）正向规则比大于 1 时，表明X的出现增加了Y的出现机会；等于 1 时，表明X对Y的出现没有影响，是不相关规则；当正向规则比小于 1 时，表示Y的出现与X的出现成反比，X增加造成Y的减少，成为一种反向规则.当出现反向规则和不相关规则时应该舍去.基于以上优化后，可将本研究的算法流程归纳如下：步 骤 1：初 始 化Pc，Pm，n，给 出 min_sup，min_conf，K等 参 数，随 机 生 成 初 始 种 群P=A1，A2，A3，An.步骤 2：计算种群 P 中每个个体的适应度fintess（X=Y）.如 果 fintess（X=Y）1 则 复 制到下一代，不符合的个体删除掉，然后统计留下的个体数m.832023 年第 8 期学 报步骤 3：如果m n，就随即生成n-m个个体，保证个体数大于等于n.步骤 4：在新种群中按照Pc和Pm的值进行交叉和变异操作.步骤 5：判断是否达到进化次数 1 000 次终止条件，如果没达到，重复步骤 2 和步骤 4.步骤 6：对产生的规则进行判断，支持度、置信度、正向规则比三个条件都满足的规则提取出来，作为强关联规则.3实验分析为了验证算法的特性，本实验采用某烘焙糕点连锁店一段时间内的营业数据集进行改进算法的验证.连锁店的营业数据包含的信息较多，有 33 个字段，包括商品摆放位置、商品类别、商品口味、口感、商品主要颜色、商品香气、商品形状、商品体积、商品重量、商品包装、顾客体重、身高、年龄段、季节、是否会员、性别、商品制作工艺、坯料的性质、商品主要配料、店面所在区域、天气、温度、销售时间、促销种类、推销手段、保质期、商品价格、定价方案、饮品购买、店员数、每单购买额、店面环境、购买情况，每个字段的属性及其对应编码值如表 2 所示.为了方便实验，实验用系统平台由一个主节点和三个门店的从节点组成，选择某一客户端连接搭建好的 Hadoop 平台，根据种群属性和属性值，随机产生M个种群，运用 MapReduce 对各个群体进行分治，对种群进行单独地计算和遗传操作，流程如图 3 所示.图 3Hadoop 平台下运用改进自适应遗传算法挖掘销售数据关联规则将本算法运用于实验数据中，得到的自适应改进后Pc的变化曲线如图 4 所示.交叉概率开始由较大值 0.8 附近，随着进化代数增加而逐渐趋近于 0.3.表明开始阶段，交叉算子对新个体产生较大影响，进化后期，交叉算子的值趋于一个较小的值，这样有利于保护优表 2字段及其属性编码值对应表字段属性及其编码值商品摆放位置进店门口附近（1）店中心（2）店内边角（3）收银台（4）商品类别吐司（1）面包类（2）蛋糕类（3）糯米类（4）饼干类（5）中式糕点（6）起酥类（7）糖艺类商品口味甜咸酸辣清淡鲜味商品主要颜色白黄绿棕红黑彩色商品口感软硬冷热粘食品形状图案式几何式象形式点缀装饰顾客年龄段青少年（1）中年（2）老年（3）携带幼儿（4）购买情况是（1）否（2）84越 缙：大数据技术及遗传算法在数据挖掘中的应用研究良基因.如图 5 所示，Pm随着进化代数增加逐渐变大而趋近于 0.09，可以产生足够的新个体，尽量防止问题限于局部最优解.图 4改进的交叉概率Pc变化曲线图 5改进的交叉概率Pm变化曲线将经典遗传算法和本研究的改进算法应用于关联规则挖掘后的实验结果如图 6 所示.本研究改进算法 2 相比经典遗传算法和改进算法 1 在解的质量方面有一定提升.图 6经典遗传算法和改进算法 1、2 的收敛性比较与 FP-Growth 算法的实验对比分析上，本研究的改进遗传算法不需要产生条件模式库和构造频繁模式树，在空间复杂度上的开销要小很多，这点对于海量数据来说效果更加明显.另外在数据量相同，但是数据的字段数较大时，本文改进遗传算法的时间效率要高于 FP-Growth 算法.两者在不同数据字段数的时间比曲线如图 7 所示.图 7数据量相同属性数量不同时两种算法的时间比但是在数据量不断递增的情况下，数据量在 1 万条以下，FP-Growth 算法的时间效率要高于本文的改进遗传算法.高于 1 万以上两者时间效率逐渐接近，但是算法效率都比较低.两者在字段相同.数据量不同时的时间比如图 8 所示.图 8数据量不同时两种算法的时间比综合来看，改进自适应遗传算法结合大数据技术更适合对大量复杂数据的关联规则挖掘.利用本文研究的挖掘模式对糕点烘焙连锁店一个月营业数据的计算，挖掘强关联规则，分析了 60 万条 20 字段的销售记录，这里列出了部分有代表性的规则.852023 年第 8 期学 报体型中等偏胖的人购买口味咸的较多.携带幼儿的购买商品配料有水果的较多，另外购买商品颜色为彩色的较多.身高高的，偏向于购买商品体积较大的.购买了蛋糕类商品后再购买其他商品的较少.促销种类为办理会员充值送额度年龄为中年人员较多.年龄段为青少年的选择商品主要配料含奶油的比较多.推销手段为门店海报加店员口头推销结合效果较好.糖艺类商品摆放在收银台附近销售量较好.促销种类为会员打折女性顾客较多.销售时间为晚间，促销种类为试吃的商品，顾客购买率较高.挖掘出的规则可用于门店日常经营，对顾客进行针对性的商品推荐购买，也可用于公司新产品的开发，根据关联规则开发可能更受顾客欢迎的产品.4结语本研究综合运用 Hadoop 大数据技术和自适应遗传算法于关联规则的挖掘，目的是将发现的关联规则用于烘焙糕点连锁店的日常销售推荐.在研究过程中，对自适应遗传算法进行了部分优化，对数据挖掘的流程进行了新的设计，在关联规则中引进正向规则比的参数，提高了所挖掘规则的可靠性.经过实验验证，改进自适应遗传算法在收敛性上得到了改良，结合大数据技术在挖掘结果的质量和效率上都有一定的优势.但是在海量数据处理的效率上仍然有待改进的地方，在后期的研究中，可以从编码方法的改进，以及同其他算法的结合方面进行考虑.参考文献：1 罗勇，陈治亚.基于改进遗传算法的物流配送路径优化 J.系统工程，2012，30（8）：118-122.2 JIANG J，MA L D，LIN S L，et al.Simulation research based on a self adaptive genetic algorithmC/2010 IEEE International Conference on Intelligent Computing and Intelligent SystemsS.l.：IEEE，2010，3：267-269.3 张军，刘文杰.关联规则中基于模糊遗传算法的研究与改进挖掘技术 J.现代电子技术，2017，40（14）：23-25.4 石玉，陈小平，于盛林.利用排序对遗传算法的 改 进 和 自 适 应 交 叉 概 率J.数 据 采 集 与 处 理，2000，15（2）：185-190.5SUN H，ZHANG H X，CHEN S P，et al.TheStudy of improved FP-growth algorithm in MapReduceC/1st International Workshop on cloud Computing andInformation Security（CCIS）.2013：250-253.6 李学龙，龚海刚.大数据系统综述 J.中国科学：信息科学，2015，45（1）：1-44.7 赵晟，姜进磊.典型大数据计算框架分析 J.中兴通讯技术，2016，22（2）：14-18.8 杨祖元.城市交通信号系统智能控制策略研究 D.重庆：重庆大学，2008：51-52.9 王小平，曹立明.遗传算法：理论、应用于软件实 M.西安：西安交通大学出版社，2002：73-74.（责任编辑：王前）86越 缙：大数据技术及遗传算法在数据挖掘中的应用研究Research on the Application of Big Data Technologyand Genetic Algorithm in Data MiningYUE Jin（Anhui Wenda Univercity of Information Engineering，Hefei 231201，China）Abstract：This paper introduces the related technologies such as association rule mining，genetic algorithm and Hadoop platform.On this basis，the fitness function of genetic algorithm is defined by using thesupport degree of association rules，and the attribute value of transaction data of bakery chain stores is encoded in the way of real number coding to form chromosomes.Aiming at the problem that the variationrange of crossover probability and mutation probability is limited，the two probability formulas are adaptively optimized.Then，a chain store big data mining platform combining association rules and geneticalgorithm is designed and built.At the same time，the improved genetic algorithm is tested by using thedesigned big data platform to collect data，which proves that the optimized algorithm has certain advantages in processing complex data attributes and convergence.Keywords：genetic algorithm；hadoop；association rules；fitness function；genetic operator 87