基于MapReduce模型的改进型灰狼分簇算法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN111709512A(43)申请公布日2020.09.25(21)申请号202010460696.1(22)申请日2020.05.27(71)申请人江苏信息职业技术学院地址214153江苏省无锡市惠山区钱藕路1号(72)发明人赵彦吴冬冬续祥(74)专利代理机构南京天翼专利代理有限责任公司32112代理人朱戈胜(51)Int.Cl.G06N3/00(2006.01)权利要求书2页说明书8页附图4页(54)发明名称基于MapReduce模型的改进型灰狼分簇算法(57)摘要本发明涉及超大规模数据分簇领域，尤其涉及一种基于MapReduce模型的改进型灰狼分簇算法，其特征在于：在对原有灰狼分簇进行改进，设计改进型灰狼分簇算法，将灰狼行为规则与灰狼的狩猎策略相混合，加大攻击祈祷次数，同时引入狄利克雷分布实现先验以增强祈祷的搜索能力；最后，使用MapReduce体系结构实施IGWCA的并行化处理，达到对大型数据集实施有效分簇的目的。本发明有效解决大型数据集的分簇问题。CN111709512ACN111709512A权利要求书1/2页1.基于MapReduce模型的改进型灰狼分簇算法，其特征在于：其步骤包括：步骤1：输入数据集，输入为t维N个数据对象，簇数为K；每个灰狼的位置X代表了K个簇(C1,C2,C3,…,Ck)的簇质心；算法最终输出的是最优质心位置，α狼的位置表示质心位置；步骤2：启动MapReduce框架读取数据信息，并将接收到的数据集分块，通过Hadoop节点均匀分配各分割好的数据块；步骤3：执行MapReduce模型中的Map函数，以灰狼ID为键，以簇质心为值，将每个数据对象转换为键值对的形式进行并行处理，根据狼位置计算簇质心，通过计算相似系数，迭代更新簇质心；Map函数以{灰狼ID,质心ID}为键，相应的质心ID相似度为值，以键值对的形式进行输出；步骤4：执行MapReduce模型中的Reduce函数，Reduce函数将根据相同键的值获取最大相似度，并根据其更改每只灰狼的适应度值；在每次迭代的过程中更新α狼、β狼、δ狼的位置，直至满足停止条件为止完成迭代，得到最优质心，完成分簇。2.根据权利要求1所述的基于MapReduce模型的改进型灰狼分簇算法，其特征在于：所述步骤3中，根据狼位置计算簇质心的步骤为：步骤3.1：根据公式(10)更新每只灰狼的位置，具体为：在每次迭代的过程中，当前群中α、β、δ狼的位置信息，并根据他们的位置信息更新ω狼的位置信息；该行为的数学模型如公式(7)、(8)、(9)所示；在第i次迭代时，ω狼的位置由公式(10)计算得到：其中，分别为α、β、δ狼当前位置，为三个随机向量，表示当前解的位置；其中，由公式(11)、(12)、(13)计算得到：其中，为随机向量；步骤3.2：采用公式(14)根据灰狼行为规则提升攻击行为：2CN111709512A权利要求书2/2页j其中，IPi是改进后编号为i的灰狼在维度j上的位置；步骤3.3：采用公式(17)引入狄利克雷分布先验每只灰狼的位置，具体为：将狄利克雷分布函数应用到每只狼的位置更新中，加大探索搜索空间的扩展力度，提高搜索性能；概率密度函数如公式(15)所示：其中，χ＝(χ1,χ2,…,χk)，χi≥0，θ是服从参数χ的狄利克雷分布；其中，Γ函数的定义由公式(16)所示；公式(17)给出的是每只灰狼在第i次迭代时使用狄利克雷分布实现位置更新的方法：其中，为灰狼在第i次迭代时的位置，exstepi表示在第i次迭代处的狄利克雷先验估计，exstepi由公式(18)计算得到，代表α狼的位置；。3.根据权利要求1所述的基于MapReduce模型的改进型灰狼分簇算法，其特征在于：所述步骤3中，计算相似系数方法为：其中和的定义如公式(2)所示：3CN111709512A说明书1/8页基于MapReduce模型的改进型灰狼分簇算法技术领域[0001]本发明涉及超大规模数据分簇领域，尤其涉及一种基于MapReduce模型的改进型灰狼分簇算法。背景技术[0002]1、背景[0003]分簇属于无监督学习，其目的是发现数据的特征并对数据进行有效处理，分簇算法被广泛应用于图像多尺度分割，生物地理优化数据处理，遥感图像实时分类，社交网络信息分类处理，大数据分析等方面。当前最常用、最简单、应用较广的是K-均值分簇算法，由于该算法的分簇结果与簇质心的初始状态息息相关，因此K-均值算法极易于陷入局部最优。为了解决这一问题，大量元启发式算法被用来解决数据分簇问题。例如：巧妙利用遗传算法的特性，在特征空间找到最优质心优化所得簇的密度；使用微粒群算法优化分簇结果，解决社交网络用户信息数据分析问题；基于引力搜索和K-均值算法初