文档介绍：基于Mapreduce的afsa
km聚类算法并行实现
 
 
陈书会 周莲英
Summary：针对kmeans算法对初始聚类中心敏感的问题，提出利用人工鱼群算法去优化k均值算法，即先通过人工鱼的行为进以步长Step向该状态前进一步，否则进行觅食行为。
聚群行为：若当前鱼的状态为 Xi，搜索其视野范围Visual内相邻伙伴，得到相邻伙伴的中心状态 Xc，若状态 Xc优于当前状态 Xi，且其周围的拥挤程度小于λ，则当前鱼向该状态前进一步，否则进行觅食行为。
觅食行为：若当前鱼的状态为 Xi，随机寻找一个在其视野内的状态Xj。若Xj优于当前状态 Xi，则当前鱼以步长Step向该状态前进一步，否则继续随机寻找一个新的状态。若尝试一定次数后，仍没有优于当前的状态，则当前鱼随机移动一步。
随机行为：若当前鱼的状态为 Xi，在其搜索范围内找不到更优的状态，为了扩大搜索空间，随机选择一个视野范围内的状态 Xj，便于跳出局部。
公告板：用来记录目标函数值、最优人工鱼个体状态和历史最优人工鱼个体状态。每条人工鱼在行动一次后就将自身状态与公告板进行比较，如果优于公告板状态，就改写公告板状态。
将人工鱼寻找食物的过程作为聚类时寻找类中心点的过程，满足误差平方和公式（1）即可认为找到最优中心点。
式（1）中k为聚类中心个数，ci为聚类中心，xj为聚类对象。
kmeans是划分方法中比较经典的聚类算法，由于效率高，在对大规模数据进行聚类时广泛应用。算法以k为参数，把n个对象分成k个簇，使簇内有较高的相似度，而簇间的相似度较低。kmeans具体运行过程如下：先随机选择k个对象，每个对象代表一个簇的平均值或中心；对剩余的对象，根据其与簇中心的距离，将它赋给最近的簇，重新计算每个簇的平均值。 这个过程不断重复，直到准则函数收敛，最后输出k个聚类中心。2并行afsa_km聚类算法
文献采取的改进afsa_km算法可以很好地弥补kmeans算法的缺陷，提高算法准确度。由于整个程序是串行实现的，在处理大规模数据时，效率较低。人工鱼群算法是一种并行算法，可以在Hadoop平台上执行。本文将人工鱼群和kmeans算法全都并行化，并在Hadoop上运行。
算法思想是：将鱼群划分为几个子鱼群，每个子鱼群在给定的数据集中得到本次过程的局部最优值，再汇总每个子鱼群的最优解，得到本次运行的全局最优解，算法流程如图2所示。在Hadoop中，Map函数主要完成每个子鱼群的寻优，包括觅食、群聚、追尾，输出子鱼群的最优解及适应度值。Map函数输入key为数据的行号，value为待聚类数据的各维度值。为了减少网络数据开销，使用Combine对Map端进行一次并归。
设置全局共享区域：每次节点运行完后，将各自节点上的鱼群位置和对应的适应度值记录在全局共享区，供下一次算法执行时使用。
算法首先为每个阶段初始化子鱼群，包括鱼群数量t、视野范围visual和试探次数Try_number等参数。
Map阶段的处理：
①计算子鱼群适应度，设定子鱼群初始状态X，求出对应的适应度值；②评价每条人工鱼，选择要进行的行为，包括觅食行为、聚群行为、追尾行为和随机行为；③执行人工鱼选择的行为，更新人工鱼位置信息和适应度值