并行K-Means与极端规模并行计算的容错优化

### 并行K-Means与极端规模并行计算的容错优化 #### 并行K-Means算法分析 在并行K-Means算法中，Combiner和Reducer起着关键作用。Combiner接收来自Mapper的 (key, list(values)) 对，其中key是c_id，list(values) 是分配给该c_id的dps列表以及整数1。Combiner会对每个c_id的dps进行局部聚合，计算p_sum和p_count，然后输出 (key, value) 对，这里的value是由p_sum和p_count组成的对象。 Reducer在Combiner执行后接收 (key, list(values)) 对，key同样是c_id，每个value由p_sum和p_count组成。Reducer会对p_sum和p_count进行累加，计算新的质心并添加到new_c_list中。同时，会进行收敛准则测试，如果满足条件则增加global_counter的值，否则算法可能会被Driver终止。 以下是Reducer的具体算法： ```plaintext Algorithm-4: Reducer Method setup ( ) 1: Load centroids to c_list; //holds current centroids 2: global_counter = 0; 3: Initialise new_c_list; //holds updated centroids Method reduce(c_id, list<values>) 1: total_sum, total_count, new_centroid, old_centroid = 0; 2: for value in values do 3: Extract dp vector from value; 4: total_sum := total_sum + value.get_p_sum(); 5: total_count := total_count + value.get_p_count(); 6: end for 7: new_centroid := total_sum / total_count; 8: add new_centroid to new_c_list 9: if new_centroid has changed or a threshold is not reached then 10: Increment global_counter by 1 11: end if 12: output(c_id, dp) Method cleanup( ) 1: Write new centroids in new_c_list to HDFS; ``` 为了评估PKMMR算法，在一个Hadoop 2.2.0集群上进行了实验，该集群包含1个主节点和16个工作节点。主节点和工作节点的硬件配置如下： |节点类型|CPU|核心数|内存|磁盘| | ---- | ---- | ---- | ---- | ---- | |主节点|2个AMD CPU，3.1 GHz|每个CPU 8核|8 × 8 GB DDR3 RAM|6 × 3 TB Near Line SAS磁盘，7200 rpm| |工作节点|1个Intel CPU，3.1 GHz|4核|4 × 4 GB DDR3 RAM|1 × 1 TB SATA磁盘，7200 rpm| 实验使用的数据集是人工生成的，数据点随机分布，初始聚类质心从数据集中随机选取，所有实验的迭代次数固定为10。 通过改变数据点数量n、维度d和聚类数k，研究距离计算对PKMMR性能的影响。实验结果表明，距离计算在迭代时间中占比很大。例如，当n固定