基于MapReduce的并行SFLA-FCM聚类算法

Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　基于ＭａｐＲｅｄｕｃｅ的并行ＳＦＬＡ—ＦＣＭ聚类算法　苟　杰，马自堂　ＧＯＵ　Ｊｉｅ，ＭＡ　Ｚｉｔａｎｇ　解放军信息工程大学三院，郑州４５００００　Ｔｈｅ　Ｔｈｉｒｄ　Ｉｎｓｔｉｔｕｔｅ，ＰＬＡ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｚｈｅｎｇｚｈｏｕ　４５００００，Ｃｈｉｎａ　ＧＯＵ　Ｊｉｅ，ＭＡ　Ｚｉｔａｎｇ．Ｐａｒａｌｌｅｌ　ＳＦＬＡ—ＦＣＭ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ＭａｐＲｅｄｕｃｅ．Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ，２０１６，５２（１）：６６－７０．　Ａｂｓｔｒａｃｔ：Ｆｕｚｚｙ　Ｃ—Ｍｅａｎｓ（ＦＣＭ）ａｌｇｏｒｉｔｈｍ　ｉｓ　ａ　ｋｉｎｄ　ｏｆ　ｗｉｄｅｌｙ　ｕｓｅｄ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍ．Ｂｕｔ　ｔｈｅ　ｃｌｕｓｔｅｒｉｎｇ　ｑｕａｌｉｔｙ　ｏｆ　ｔｈｅ　ＦＣＭ　ｄｅｐｅｎｄｓ　ｏｎ　ｔｈｅ　ｃｈｏｉｃｅ　ｏｆ　ｉｎｉｔｉａｌ　ｖａｌｕｅｓ．Ｃｏｍｂｉｎｅｄ　ｗｉｔｈ　ｔｈｅ　ｂｅｔｔｅｒ　ｓｅａｒｃｈｉｎｇ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｆ　ｔｈｅ　Ｓｈｕｆｌｅｄ　Ｆｒｏｇ　ｆＬｅａｐｉｎｇ　Ａｌｇｏｒｉｔｈｍ（ＳＦＬＡ），ｔｈｉｓ　ｐａｐｅｒ　ｐｒｅｓｅｎｔｓ　ａ　ｐａｒａｌｌｅｌ　ＳＦＬＡ—ＦＣＭ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ＭａｐＲｅｄｕｃｅ．Ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｕｓｅｓ　ｔｈｅ　ｉｎｆｏｒｍａｔｉｏｎ　ｔｒａｎｓｍｉｔｔｉｎｇ　ｗｉｔｈｉｎ　ｓｕｂｇｒｏｕｐｓ　ａｎｄ　ｇｌｏｂａｌ　ｉｎｆｏｒｍａｔｉｏｎ　ｅｘｃｈａｎｇｅ　ｔｏ　ｓｅａｒｃｈ　ｔｈｅ　ｈｉｇｈ　ｑｕａｌｉｔｙ　ｏｆ　ｔｈｅ　ｃｌｕｓｔｅｒｉｎｇ　ｃｅｎｔｅｒ．Ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｐｒｏｃｅｓｓ　ｉｓ　ｄｅｓｉｇｎｅｄ　ｔｏ　ｃｏｎｆｏｒｍ　ｔｏ　ｔｈｅ　ＭａｐＲｅｄｕｃｅ　ｐｒｏｇｒａｍｍｉｎｇ　ｍｏｄｅｌ　ａｎｄ　ｉｔ　ｈａｓ　ｔｈｅ　ａｂｉｌｉｔｙ　ｏｆ　ｄｅａｌｉｎｇ　ｗｉｔｈ　ｌａｒｇｅ－ｓｃａｌｅ　ｄａｔａｓｅｔ．Ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔｓ　ｐｒｏｖｅ　ｔｈａｔ　ｐａｒａｌｌｅｌ　ＳＦＬＡ—ＦＣＭ　ｉｍｐｒｏｖｅｓ　ｔｈｅ　ｓｅａｒｃｈｉｎｇ　ｐｅｒｆｏｒｍａｎｃｅ　ａｎｄ　ｔｈｅ　ａｃｃｕｒａｃｙ　ｏｆ　ｃｌｕｓｔｅｒｉｎｇ　ｒｅｓｕｌｔｓ　ａｎｄ　ｈａｓ　ｈｉｇｈ　ｓｐｅｅｄｕｐ　ａｎｄ　ｓｃａｌａｂｉｌｉｔｙ．　Ｋｅｙ　ｗｏｒｄｓ：ｃｌｕｓｔｅｒｉｎｇ；Ｆｕｚｚｙ　Ｃ—Ｍｅａｎｓ（ＦＣＭ）：Ｓｈｕｆｌｅｄ　ｆＦｒｏｇ　ＬｅａｐｉｎｇＡｌｇｏｒｉｔｈｍ（ＳＦＬＡ）：ＭａｐＲｅｄｕｃｅ　摘要：模糊ｃ均值算法（Ｆｕｚｚｙ　Ｃ—Ｍｅａｎｓ，ＦＣＭ）是目前应用比较广泛的一种聚类算法。ＦＣＭ算法的聚类质量依赖　于初始聚类中心的选择并且易陷入局部极值，结合混合蛙跳算法（Ｓｈｕｆｌｅｄ　Ｆｒｏｇ　Ｌｅａｐｉｆｎｇ　Ａｌｇｏｒｉｔｈｍ，ＳＦＬＡ）较强的　搜索能力，提出一种基于ＭａｐＲｅｄｕｃｅ的并行ＳＦＬＡ—ＦＣＭ聚类算法。该算法利用ＳＦＬＡ算法的子群内模因信息传递　和全局信息交换来搜索高质量的聚类中心，根据ＭａｐＲｅｄｕｃｅ编程模型设计算法流程，实现并行化，使其具有处理大　规模数据集的能力。实验证明，并行ＳＦＬＡ．ＦＣＭ算法提高了的搜索能力和聚类结果的精度，并且具有良好的加速比　和扩展性。　天键词：聚类；模糊ｃ均值算法；混合蛙跳算法；ＭａｐＲｅｄｕｃｅ　文献标志码：Ａ　中图分类号：ＴＰ３０１　ｄｏｉ：１０．３７７８￣．ｉｓｓｎ．１００２—８３３１．１５０４．０１９９　ｌ　引言　大数据时代的来临，对传统数据挖掘业带来了巨大　模的急剧增加，传统的串行计算模式已经无法满足大数　据量的计算需求。　目前，国内外的研究者提出了许多ＦＣＭ算法的并行　的挑战。聚类分析是数据挖掘的一项关键技术，它既可　以作为一种分析手段获取数据集中隐藏的信息，又可以　作为数据挖掘其他技术的预处理阶段，提高挖掘效率。　聚类就是将事物按照某种规则，划分成若干个簇，使同　个簇中的元素尽可能的相似，不同簇中的元素尽可能　一方案。虞倩倩等人提出了基于ＭａｐＲｅｄｕｃｅ的并行模糊　Ｃ均值聚类算法，利用并行环境的优势，大幅度提高了　ＦＣＭ处理大数据集的计算效率　。在此基础上，王永贵　等人针对该算法进行了改进，减少了ＭａｐＲｅｄｕｃｅ计算过　程中的迭代次数，提高了算法的整体执行效率　。余长　俊等人则通过利用Ｃａｎｏｐｙ算法对数据集进行预处理，　先得到初始数据集的粗略划分，再利用ＦＣＭ算法进行　聚类，一定程度上提高了聚类效率　。但是，并行的ＦＣＭ　的不同”。　。模糊ｃ均值聚类算法是聚类分析与模糊理　论相结合的产物，利用模糊理论中描述事物间模棱两可　的关系，将Ｋ．ｍｅａｎｓ算法中数据元素之间的硬关系，转　化为软关系，更符合现实中的情况，提高了聚类精度，已　成功应用于模式识别、数据挖掘等领域。但随着数据规　算法对于初始聚类中心的选择具有敏感性，容易陷入局　作者简介：苟杰（１９９０一），男，硕士研究生，主要研究领域为大数据与数据挖掘，Ｅ—ｍａｉｌ：ｘｄｇｊ０００００００＠１６３．ｃｏｒｎ；马自堂（１９６２一），　男（回族），教授，主要研究领域为信息安全、密码系统工程。　收稿口期：２０１　５－０４—２２　修同日期：２０１５—０６—１９　文章编ｇ－：１００２—８３３１（２０１６）０１—００６６—０５　ＣＮＫＩ网络优先｛』ｌ版：２０１５－０８—２０，ｈｔｔｐ：／／ｗｗｗ．ｃｎｋｉ．ｎｅｔ／ｋｃｍｓ／ｄｅｔａｉｌ／１１．２１２７．ＴＰ．２０１５０８２０．１６４１．００６．ｈｔｍｌ　苟杰，马自堂：基于ＭａｐＲｅｄｕｃｅ的并行ＳＦＬＡ—ＦＣＭ聚类算法　部极值，该问题在上述改进方案中并没有得到解决。　利用群智能算法的全局搜索能力解决初值设置困　难的问题，是一种有效的解决方案。混合蛙跳算法（ＳＦＬＡ）　２．２混合蛙跳算法　混合蛙跳算法由Ｅｕｓｕｆｆ和Ｌａｎｓｅｙ为解决组合优化　问题于２００３年最先提出　。它的思想是模仿一群青蛙　在石头间跳跃觅食的过程，在觅食活动中，青蛙通过跳　跃来找到食物较多的地方。所有的青蛙划分为多个子　群，子群内部的青蛙进行交流来达到信息的共享，每一　只青蛙都代表一组解，这个解随着子群的进化而进化；　当子群发展到一定程度，各个子群间再进行信息的交　是一种全新的亚启发式协同搜索算法，结合了基于模因　进化的模因算法和基于群体行为的粒子群算法，在具有　遗传算法的全局寻优能力的同时，还具有粒子群算法较强　的局部寻优能力，并且计算简单，参数较少，容易实现　。　本文基于ＭａｐＲｅｄｕｃｅ的计算模型，提出了一种利用混合　蛙跳算法解决并行ＦＣＭ算法初值敏感的问题，并在　Ｈａｄｏｏｐ平台上进行了算法性能的实验。实验结果表　明：并行ＳＦＬＡ．ＦＣＭ算法克服了ＦＣＭ算法初值敏感的　问题，提高了算法的聚类精度，同时具有较高的加速比　和扩展性　２相关算法研究　２．１　ＦＣＭ算法　设样本空间Ｘ有　个数据元素，表示为　＝｛　，　，…，　），其中　为第ｉ个元素，　是数据元素集总量，　且　≥２；预设聚类的类别数为尼，２≤尼≤，ｚ；（ｃ　：　１，２，…，ｋ）　表示聚类中心，其中Ｃ　为第ｉ个聚类中心的簇心；将　分成ｋ类可以用一个模糊矩阵／ｚ＝（　）来表示，其中／ｚ　，　为第ｉ个数据元素属于第，类的隶属度。　．　ＦＣＭ算法的目标函数Ｊ（／ｚ，Ｃ）定义如下：　（　，ｃ）＝∑∑　列　一Ｃｉ　（１）　其中ｍ（ｍ＞１）是模糊指数，可以控制聚类结果的模糊　程度。　ＦＣＭ算法的执行过程就是通过迭代使目标函数　（　，Ｃ）达到最小值，Ｃ均值要求一个样本对于各个聚　类中心的隶属度之和为１，即　∑　＝１，　１，２，…，ｎ　（２）　在式（２）的条件下求式（１）的极小值，令　（　，Ｃ）对　Ｃ　和　的偏导数为０，可得必要条件：　＝∑　／∑　，　＝１，２，…，ｋ　（３）　“　：　——————————　：　：：ｉ　，ｚ　ｌ，　，…，…　，　；　耋（１／Ｉ　一　ｌ　Ｊ：１，２，…，ｋ　（４）　ＦＣＭ算法通过迭代的方式求解式（３）和式（４），使　用梯度下降的方式来优化目标函数，直到Ｃ　变化小于　预定阈值。该算法的聚类结果受初始聚类中心的影响　很大，若采用随机的方式确定初始聚类中心，结果容易　陷入局部极值，影响聚类效果㈣。　流，实现群体问的信息混合，直到达到最优解　…。混合　蛙跳算法实现了局部搜索和全局搜索的结合，在子群内　部通过局部搜索使模因信息在局部个体之间传递，优化　子群内的个体，然后混合所有青蛙，通过再分子群的过　程将全局信息在所有青蛙之间进行交换，该算法能够向　着全局最优的方向进行，子群内部的局部搜索与全局搜　索将分别在达到各自的收敛条件时结束。　混合蛙跳算法的一般过程描述为：　（１）随机产生Ｆ只青蛙组成初始种群Ｐ＝｛　，置，…，　｝，第ｋ只青蛙表示问题的解为　＝｛ｘ　Ｘ”…，Ｘ　｝，　其中Ｓ为解空间的维数，初始化适应度函数ｆ（ｘ１。　（２）将所有的青蛙按照适应度函数的大小降序排　列，并标记最优的青蛙　，然后将排序后的青蛙分配到　个子群中，每个种群中包含　只青蛙，则Ｆ＝ｍ　ｘ　，设　第ｉ个子群的青蛙集合为Ｆ　，分配过程表达式为：　Ｆｆ＝｛　＋ｍ（１＿ｌ１∈Ｐｌ１＜，＜　｝，１＜ｉ＜ｍ　（５）　（３）在每一个子群中，分别标记出最优的青蛙　和　最差的青蛙　执行子群内局部搜索，即对子群中　．　，进行更新操作，更新规则为：　Ｄ＝ｒ×（　一　）　（６）　ｘ＝　＋Ｄ，Ｄ≤Ｄ　（７）　其中ｒ为０到１之间的随机数，Ｄ为青蛙的跳跃步长，　Ｄ…为青蛙的最大跳跃步长，经过一次更新后，若　，　优于原先的　则取代原子群中的蛙，否则，用　，取　代　按照公式（６）、（７）重新执行更新操作。若执行后　还是没有改进，则在子群中随机产生一个新蛙代替　一　不断执行操作直到达到预设条件。　（４）将所有的蛙进行混合，重新排序和划分子群，重　复步骤（２）、（３），进行新一轮局部搜索，反复进行直到达　到最终终止条件，最好解的蛙即为最优解。　混合蛙跳算法的局部搜索和全局信息交换使得最　优解向全局最优移动，避免了陷入局部极值的困境。　３　ＭａｐＲｅｄｕｃｅ模型　ＭａｐＲｅｄｕｃｅ并行编程模型最早是由Ｇｏｏｇｌｅ公司于　２００４年提出的，Ａｐａｃｈｅ的开源项目Ｈａｄｏｏｐ处理平台正是　基于这一模型开发，它将待处理的任务划分成两个处理　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　阶段，分别为Ｍａｐ阶段和Ｒｅｄｕｃｅ阶段，每个阶段都以一　组键值对作为输入和输出。编程人员只需要根据需求对　Ｍａｐ（）函数和Ｒｅｄｕｃｅ（）函数进行重写，而不用考虑分布　式环境的底层细节，具有编程简单，容易实现的特点　。　图１展示了ＭａｐＲｅｄｕｃｅ模型的计算流程。　输入数据Ｍａｐ阶段　中间结果　Ｒｅｄｕｃｅ阶段输出数据　图１　ＭａｐＲｅｄｕｃｅ模型计算流程　（１）输入阶段：将分布式文件系统（Ｈａｄｏｏｐ　Ｄｉｓｔｒｉｂｕｔｅｄ　Ｆｉｌｅ　Ｓｙｓｔｅｍ，ＨＤＦＳ）中的待处理数据分片Ｓｐｌｉｔ，每一个　Ｓｐｌｉｔ的默认大小为６４ＭＢ（用户可自行更改大小），同时　创建数据片的副本，这些Ｓｐｌｉｔ就近分配给Ｍａｐ节点，以　减少通信量。　（２）Ｍａｐ阶段：Ｍａｐｐｅｒ遍历所有的Ｓｐｌｉｔ，并将其解析　成键值对（Ｋｅｙ／Ｖａｌｕｅ），然后调用用户编写的Ｍａｐ（）函数　对键值对ｉ　亍女哩，输出若干中间键值对（ｋｅｙｉ　／Ｖａｌｕｅｉ　）。　这里得到中间结果可以在Ｍａｐ阶段结束前进行预处理，　进行合并或者排序，减少传输给Ｒｅｄｕｃｅｒ时的通信量。　（３）中间结果处理阶段：Ｐａｒｔｉｔｉｏｎｅｒ的作用是对Ｍａｐｐｅｒ　的计算结果进行分片，以便同一分组的数据交给同一个　Ｒｅｄｕｃｅｒ处理。默认的处理方式包括ＨａｓｈＰａｒｔｉｔｉｏｎｅｒ和　ＴｏｔａｌＯｒｄｅｒＰａｒｔｉｔｉｏｎｅｒ，前者是基于哈希的分片方法，后者　是基于区间的分片方法。Ｈａｄｏｏｐ平台提供了Ｐａｒｔｉｔｉｏｎｅｒ　接口，用户可以根据需求进行重写。　（４）Ｒｅｄｕｃｅ阶段：遍历所有的中间结果，执行用户定　义的Ｒｅｄｕｃｅ（）函数，输出新的键值对（Ｋｅｙ　／Ｖａｌｕｅ　。　）。　（５）输出阶段：此阶段将Ｒｅｄｕｃｅｒ的输出结果写入到　ＨＤＦＳ中的输出目录　。　４并行ＳＦＬＡ．ＦＣＭ算法介绍　４．１算法设计　通过分析混合蛙跳算法的过程，可以发现，青蛙在　子群内部进行深度搜索更新时是相互独立的，在传统串　行的计算模式下，每个子群的迭代更新操作都是依次进　行的，前一个子群达到迭代次数后，下一个子群才能进　行迭代更新操作，这样就大大增加了算法的时间开销。　当面临大数据集时，子群的数量可能成千上百，在单一　节点上运行该算法，受制于计算机的内存和计算效率，　则出现运行时间不能容忍或者根本不可行的情况。　ＭａｐＲｅｄｕｃｅ计算模型提供的并行化设计思路需要算法的　计算过程具有一定独立性，并行化ＳＦＬＡ．ＦＣＭ算法主要利　用子群内部更新迭代的独立性来实现，具体思路如下：　Ｍａｐ阶段：由于ＭａｐＲｅｄｕｃｅ计算模型在节点问通信　时以键＼值对的形式传输数据，所以需要将初始化的青　蛙进行改造，转化成键＼值对的形式进行存储，将青蛙的　适应度作为Ｋｅｙ值，青蛙的编码信息作为Ｖａｌｕｅ值。　Ｍａｐｐｅｒ从Ｓｐｌｉｔ中读取青蛙的信息，输入数据为（行偏移　量，记录行），保证每个Ｍａｐｐｅｒ读取到的青蛙的数量大　致相同，充分利用计算机资源，避免出现负载不均衡的　情况。Ｍａｐ（）函数主要完成所有青蛙适应度的计算，并　更新Ｋｅｙ值，输出数据为（．厂（　），　）。　Ｐａｒｔｉｔｉｏｎ阶段：将所有的青蛙按照适应度的大小进　行排序，使用归并排序的方案，在Ｍａｐ阶段，每个Ｍａｐｐｅｒ　进行局部排序，在Ｒｅｄｕｃｅ阶段，启动一个Ｒｅｄｕｃｅ　Ｔａｓｋ　进行全局排序。然后根据公式（５）分配所有的青蛙，将　同一个子群的青蛙分配到同一个Ｒｅｄｕｃｅｒ进行处理。将　Ｐａｒｔｉｔｉｏｎ函数中的￣ｎｕｍＰａｒｔｉｔｉｏｎｓ设置为ｍ，即Ｒｅｄｕｃｅｒ　的个数，使其与青蛙子群的数目保持一致。Ｐａ￣ｉｔｉｏｎ函　数影响Ｒｅｄｕｃｅｒ的负载均衡，并使数据有序排列，以便于　Ｒｅｄｕｃｅ（）函数进行归约处理。　Ｒｅｄｕｃｅ阶段：Ｒｅｄｕｃｅｒ接收同一个子群的青蛙，输入　数据为（厂（　。），　），按照蛙跳算法的步骤执行子群内的　迭代搜索，输出更新后的青蛙，输出数据为（厂（　），　）。　Ｒｅｄｕｃｅ阶段完成后，将所有的青蛙混合，进行全局信息　的交换，然后把青蛙信息传输到Ｍａｐｐｅｒ继续进行种群　的重新划分，完成新一轮的迭代，如此反复，直到达到最　大迭代次数。　４．２蛙的编码方式　首先需要设计青蛙的编码方式。在混合蛙跳算法　中，青蛙代表解空间的一组解，ＦＣＭ算法的结果是找到　ｋ个最优聚类中心，所以，每只蛙由ｋ个聚类中心组成，　第Ｓ只蛙的编码如下：　Ｘ　＝　Ｘ　ｓｓＬ’Ｘ　…，Ｘ　ｓ　（８）　４．３适应度函数设计　然后需要设定适应度函数，由ＦＣＭ算法思想可知，　目标函数Ｊ（／ｚ，Ｃ）是评价ＦＣＭ聚类中心的指标，目标函　数越小，说明聚类中心越优，所以，混合蛙跳算法的适应　度函数可设定为：　厂（　）　‘９）　由此可知，目标函数越小，适应度函数越大，则聚类　中心质量越好。　４．４并行ＳＦＬＡ．ＦＣＭ算法流程　并行ＳＦＬＡ．ＦＣＭ算法流程如图２所示，具体步骤描　述如下。　步骤１设置参数及随机产生初始青蛙群体：设置蛙　的总数为Ｆ只，划分为ｍ个种群，每个种群包含ｎ只青　蛙，即满足Ｆ＝ｍ×ｎ，设定全局迭代次数　，子群迭代　苟杰。马自堂：基于ＭａｐＲｅｄｕｃｅ的并行ＳＦＬＡ—ＦＣＭ聚类算法　次数　，模糊参数ｍ和聚类类别数ｋ。设定Ｋｅｙ值存　娱乐等１８个频道的新闻数据，提供ＵＲＬ和正文信息，完　储青蛙的适应度，Ｖａｌｕｅ存储青蛙的编码。　步骤２计算适应度：将青蛙群体随机分配到Ｍａｐｐｅｒ，　保证每个Ｍａｐｐｅｒ的青蛙数大致一样，Ｍａｐｐｅｒ主要用公　整版大小为１．６５　ＧＢ，另有随机采样的样例数据３４　ＭＢ。　本文利用汉语词法分析系统ＩＣＴＣＬＡＳ对数据文档进行　特征词的提取，结合文献［１４】中提出的利用ＴＦ．ＩＤＦ（Ｔｅｍ１　Ｆｒｅｑｕｅｎｃｙ—Ｉｎｖｅｒｔｅｄ　Ｄｏｃｕｍｅｎｔ　Ｆｒｅｑｕｅｎｃｙ）计算特征词　式（９）计算每只青蛙的适应度，输出数据为（．厂（　），　）。　步骤３划分子群：Ｐａｒｔｉｔｉｏｎｅｒ将青蛙按照适应度大　小依次排序，获取最优青蛙　，然后按照公式（５）的种　群划分方式，将同一个种群的青蛙传给同一个Ｒｅｄｕｃｅｒ，　权重的方式，可以得到文档矢量信息，通过计算多维向　量间的距离得到文档间的相异度，从而可以进行聚类。　５．２参数设置　本文提出的算法需要设置的参数有：模糊指数、青　蛙总数、子群数、子群内的迭代次数、混合迭代次数、青　蛙跳跃的最大步长。为了保证算法的准确性和效率，在　初始阶段进行了多次反复实验，设置模糊指数为２，青蛙　的总数为２００，子群数量为５，每个子群中的数量为４０，　子群内的迭代次数为３０，混合迭代次数最大为１００。　并设置ｎｕｍＰａｒｔｉｔｉｏｎｓ为ｍ，即Ｒｅｄｕｃｅｒ的个数。　步骤４局部更新：Ｒｅｄｕｃｅｒ用公式（６）、（７）局部更新　接收到的种群，直到达到预设的迭代次数　。　步骤５全局更新：Ｒｅｄｕｃｅｒ计算完成后，对更新后的　所有青蛙进行混排，转向步骤２，如果达到预设的全局最　大迭代次数　时，迭代结束，输出最优解。　步骤６获取结果：将步骤４生成的聚类中心作为ＦＣＭ　青蛙的最大跳跃步长Ｄ…对于搜索的性能影响较　大，根据文献［１５］和［１６１的描述，其取值依赖于青蛙的种　算法的初始聚类中心，将所有数据依据ＦＣＭ算法聚类，　分配给所属聚类中心，到此算法结束，得到聚类结果。　群规模，青蛙的种群规模较大时，一般Ｄ…取值较大，　当种群规模较小时，Ｄ…取值相对也要较小。在本实　验环境中，进行多次实验后发现，当青蛙的Ｄ…取６时，　聚类效果最为理想。　５．３算法准确率比较　比较并行ＦＣＭ算法和并行ＳＦＬＡ．ＦＣＭ算法聚类　结果的准确性。实验采用样例数据。并行ＦＣＭ算法采　用文献［３］提供的方案，随机产生初始聚类中心，重复实　验２０次，在同样的运行环境下，使用本文提出的并行　ＳＦＬＡ－ＦＣＭ算法对同样的数据进行聚类，重复２０次，并　记录结果。　图２并行ＳＦＬＡ—ＦＣＭ算法流程　从图３中可以看出，并行ＦＣＭ的准确率波动比较　大，这是因为随机产生的初始聚类中心对聚类结果的影　响较大，又因为ＦＣＭ算法容易陷入局部极值，所以聚类　结果的准确率波动较大，不稳定；而并行ＳＦＬＡ．ＦＣＭ算　法的准确率波动范围较小，比较稳定。并行ＦＣＭ算法　的平均准确率为７５．４６％，并行ＳＦＬＡ．ＦＣＭ算法的平均　准确率为７９．８３％，高于并行ＦＣＭ算法。　５实验结果分析　５．１实验环境　本文通过在实验室环境中搭载Ｈａｄｏｏｐ进行实验，　搭建Ｈａｄｏｏｐ平台的硬件选取情况如表１所示。　表１　Ｈａｄｏｏｐ平台节点硬件信息　集群节点之间均以１００　ＭＢ带宽互联，搭建Ｈａｄｏｏｐ　平台的软件选取情况如下：Ｈａｄｏｏｐ版本为２０１３．１０．１放　出的２．２．０版本；ＯＳ为Ｕｂｕｎｔｕ１２．０４。实验数据采用的是　实验次数　图３算法准确率比较　５，４算法性能比较　比较并行ＦＣＭ算法和并行ＳＦＬＡ—ＦＣＭ算法的运行　时间和适应度函数。实验采用样例数据，重复２０次，计　搜狗实验室提供的搜狐新闻数据（ＳｏｇｏｕＣＳ），该数据集　搜集了２０１２年６月至７月期间国内、国际、体育、社会、　７０　２０１６，５２（１）　ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇ　ａｎａａｐｐＵｃａｔｉｏｎｓ计算机工程与应用　算平均运行时间和平均适应度函数。　根据表２的数据显示，并行ＳＦＬＡ．ＦＣＭ算法的运行　时间并不占优，这是由于该算法中子群内的迭代搜索消　耗了部分时间，但是算法的平均适应度和最大适应度均　高于并行ＦＣＭ算法，表现出较好的搜索性能。　表２算法性能比较　５．５算法的加速比　算法的加速比可以衡量算法的并行性能，它指的是　同一个任务单节点运行时间与多节点运行时间的比　率。选择完整版数据，将原数据分成３个样本，大小分别　为０．５　ＧＢ、１．０　ＧＢ、１．５　ＧＢ，分别在２、３、４、５个节点上使用　并行的ＳＦＬＡ．ＦＣＭ算法进行聚类。　从图４中可以看出，随着节点数目的增加，该算法　具有良好的加速比，随着数据规模的增加，加速比上升　趋势更加明显，证明并行ＳＦＬＡ．ＦＣＭ算法在处理较大规　模的数据时，性能良好。　节点数目　图４并行ＳＦＬＡ．．ＦＣＭ算法的加速比　５．６算法的扩展性　算法的扩展性体现在算法能够随着节点数目和处　理数据规模的增加表现出良好的计算性能。同样选择　完整版数据，将原数据分成３个样本，大小分别为０．５　ＧＢ、　１．０　ＧＢ、１．５　ＧＢ，分别在２、３、４、５４－－节点上使用并行ＳＦＬＡ—　ＦＣＭ算法进行聚类。从图５中可以看出，随着节点数目　和数据规模的增加，算法的运行效率基本保持稳定，表　现出良好的扩展性。　厘　苔　节点数目　图５并行ＳＦＬＡ．ＴＣＭ算法运行情况　６结束语　本文针对现有的并行模糊聚类算法对于初始聚类中　心敏感易陷于局部极值的缺陷，提出了利用混合蛙跳算　法和ＦＣＭ算法相结合的并行ＳＦＬＡ．ＦＣＭ聚类算法，利用　混合蛙跳算法较强的寻优能力，来发现高质量的聚类中　心，提高了聚类算法的精度。实验证明，并行ＳＦＬＡ．ＦＣＭ　算法具有很好的聚类性能和求解精度，并且在并行环境　下保持了良好的加速比和扩展性。　参考文献：　［１］孟小峰．大数据管理：概念、技术与挑战［Ｊ］＿计算机研究与发　展，２０１３，５０（１）：１４６—１６９．　［２］Ｈａｌｌ　Ｌ　Ｏ．Ｃｌｕｓｔｅｒｉｎｇ　ｗｉｔｈ　ａ　ｇｅｎｅｔｉｃａｌｌｙ　ｏｐｔｉｍｉｚｅｄ　ａｐｐｒｏａｃｈ［Ｊ］．　ＩＥＥＥ　Ｔｒａｎｓ　ｏｎ　Ｅ￣ｏｌｕｔｉｏｎａｒｙ　Ｃｏｍｐｕｔａｔｉｏｎ，１　９９３，３（２）：　１０３一ｌ１２．　［３］ＹＵ　Ｑｉａｎｑｉａｎ．Ｐａｒａｌｌｅｌ　ｆｕｚｚｙ　Ｃ—ｍｅａｎｓ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　ＭａｐＲｅｄｕｃｅ［Ｊ］．Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ，　２０１３，４９（１４）：１３３—１３７．　［４］王永贵．ＭａｐＲｅｄｕｃｅ模型下的模糊Ｃ均值算法研究［Ｊ］．计算　机工程，２０１４，４０（１０）：４７．５１．　［５］余长俊，云环境下基于Ｃａｎｏｐｙ聚类的ＦＣＭ算法研究［Ｊ］．计　算机科学，２０１４，４１（１１）：３１６－３１９．　［６］Ｍａｓｈｈａｄｉ　ＫＡ．Ｖａｒｉｏｕｓ　ｓｔｒａｔｅｇｉｅｓ　ｆｏｒ　ｐａｒｔｉｔｉｏｎｉｎｇ　ｏｆ　ｍｅｍｅ—　ｐｌｅｘｅｓ　ｉｎ　ｓｈｕｆｌｆｅｄ　ｆｒｏｇ　ｌｅａｐｉｎｇ　ａｌｇｏｒｉｔｈｍ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　１４ｔｈ　Ｉｎｔ　ＣＳＩ　Ｃｏｍｐｕｔｅｒ　Ｃｏｎｆ．Ｎｅｗ　Ｙｏｒｋ：ＩＥＥＥ　Ｐｒｅｓｓ，　２００９：５７６—５８１．　［７】卞艺杰．改进混合蛙跳算法和Ｋ－Ｍｅａｎｓ的新型聚类算法［Ｊ］．　计算机系统应用，２０１４，２３（７）：１１５－１１９．　［８］武小红．可能性模糊Ｃ－－均值聚类新算法［Ｊ］．电子学报，２００８，　３６（１０）：１９９６—２０００．　［９］Ｅｕｓｕｆｆ　Ｍ　Ｍ．Ｏｐｔｉｍｉｚａｔｉｏｎ　ｏｆ　ｗａｔｅｒ　ｄｉｓｔｉｒｂｕｔｉｏｎ　ｎｅｔｗｏｒｋ　ｄｅｓｉｇｎ　ｕｓｉｎｇ　ｔｈｅ　ｓｈｕｆｌｆｅｄ　ｆｒｏｇ　ｌｅａ　ｐｉｎｇ　ａｌｇｏｒｉｔｈｍ［Ｊ］．Ｗａｔｅｒ　Ｒｅｓｏｕｒ　Ｐｌａｎ　Ｍａｎａｇｅ，２００３，１２９（３）：２１０—２２５．　［１　０］Ｄｕ　Ｃｈａｎｇｈａｉ．Ａｐｐｌｉｃａｔｉｏｎ　ｏｆ　ｉｍｐｒｏｖｅｄ　Ｆｕｚｚｙ　Ｃ－－Ｍｅａｎｓ　ｃｌｕｓｔｅｒｉｎｇ　ｉｎ　ａｕｔｏｍａｔｉｃ　ｐｒｏｇｒａｍｍｉｎｇ　ｌｒａｆｉｆｃ　ｉｎｔｅｒｖａｌｓ［Ｊ］．　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ，２００９，４５（２４）：　１９０—１９３．　［１１］杨祖元．基于ＳＦＬＡ．－ＦＣＭ聚类的城市交通状态ＮＩ￣，Ｉ研究［Ｊ］．　计算机应用研究，２０１０，２７（５）：１７４３—１７４５．　［１２］Ｎｇａｚｉｍｂｉ　Ｍ．Ｄａｔａ　ｃｌｕｓｔｅｒｉｎｇ　ｕｓｉｎｇ　ＭａｐＲｅｄｕｅｅ［Ｄ］．Ｉｄａｈｏ：　Ｂｏｉｓｅ　Ｓｔａｔｅ　Ｕｎｉｖｅｒｓｉｔｙ，２００９．　［１３］Ｔｏｍ　Ｗ．Ｈａｄｏｏｐ权威指南［Ｍ】．２版．周敏奇，王晓玲，译．北　京：清华出版社，２０１１：１６７—１８６．　［１４］俞文明．Ｗｅｂ中文文本聚类研究［Ｄ］．杭州：杭州电子科技　大学，２００９．　［１５］李英海．一种基于阈值选择策略的改进混合蛙跳算法ｆＪ］．　计算机工程与应用，２００７，４３（３５）：１９．２１．　［１６］Ａｍｉｒｉ　Ｂ．Ａｐｐｌｉｃａｔｉｎｏ　ｏｆ　ｓｈｕｆｌｆｅｄ　ｆｒｏｇ　ｌｅａｐｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｏｎ　ｃｌｕｓｔｅｒｉｎｇ［Ｊ］．Ｔｈｅ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｊｏｕｒｎａｌ　ｏｆ　Ａｄｖａｎｃｅｄ　Ｍａｎｕｆａｃｔｕｒｉｎｇ　Ｔｅｃｈｎｏｌｏｇｙ，２００９，４５（１）：１９９－－２０９．