基于KD树和混沌蜉蝣优化的并行谱聚类算法

针对大数据环境下并行谱聚类算法存在的节点负载不均衡、冗余计算、矩阵相乘时间开销大以及初始簇中心敏感等问题，提出了基于KD(k-dimension)树和混沌蜉蝣优化算法的并行谱聚类算法(PSC-MO)。首先，提出基于采样的KD-tree数据分区策略(DPS)划分数据，保证了节点间负载均衡；其次，在构建稀疏相似矩阵过程中，提出优化的分区分配策略(OPA)和基于三角不等式的KD树剪枝策略以进行跨分区的t近邻搜索，避免了过多的冗余计算；然后，提出正规化定理，通过元素对应相乘的方式代替矩阵相乘以优化Laplacian矩阵正规化过程，有效地减少了时间开销；最后，提出混沌蜉蝣优化算法(CMO),得到最佳位置作为初始簇中心后进行k-means并行聚类，解决了算法对初始簇中心敏感的问题。实验表明，PSC-MO算法不但具有良好的聚类效果，而且在大规模数据集上表现出了良好的数据和系统可扩展性。