[科普中国]-疏化处理

图聚类

图聚类是图数据挖掘、分析及应用过程中可能会用到的一个关键技术。图聚类通过将图模型中的每个结点按照聚簇进行分类，可以提高同类别聚簇图结点对象实体的关联紧密性、降低不同类聚簇图结点对象实体的关联紧密性。随着超大规模图数据信息与处理机制的出现，如何高效地进行图聚类分析与处理，以此来挖掘图数据中的潜在有效数据信息，已成为人工智能、数据挖掘等领域的热点研究方向之一。国内外研究人员对图聚类算法进行了广泛的研究，提出了很多的图聚类算法，包括经典聚类算法(如划分式聚类算法)、层次式图聚类算法、基于密度的图聚类算法、最小生成图树聚类算法等。

数据抽样数据抽样是图聚类分析与处理机制中的一种高效数据处理方式。数据抽样首先从整体数据集合中抽取局部样本，然后对样本数据进行数据挖掘、处理与分析。数据抽样可以实现时间与挖掘处理结果的高性能比以及提高图聚类分析与处理的有效性。

疏化处理的概述在图聚类分析与处理过程中，首先对图模型中的结点和边分别进行数据抽样(疏化处理)，然后对疏化处理的结果进行图聚类分析。作为图聚类分析与处理机制中较为重要的一个环节，疏化处理机制已被应用于多个研究方向。针对小规模、小区域范围的图模型数据信息，现有的疏化处理机制主要包含L-spar、k-最近邻图等几种方法1。

这些方法在对小规模、小区域范围的图模型数据信息进行处理时，能够得到很好的处理效果，但是在对较大规模、较大区域范围的图模型数据信息进行处理和应用于分布式集群计算环境时，处理效果比较差。随着图模型应用产品的不断发展和应用规模的不断扩大，图模型的数据信息变得越来越复杂，依靠单一的计算环境对图数据进行处理已不能满足数据分析与处理的需要。针对这种情况，能够通过与大规模计算机服务终端相关联来对大规模数据进行分析与处理的MapReduce并行计算理论框架得到了广泛应用。

哈希算法，是根据设定的哈希函数H(key)和处理冲突方法将一组关键字映像到一个有限的地址区间上，并以关键字在地址区间中的像作为记录在表中的存储位置，这种表称为哈希表或散列，所得存储位置称为哈希地址或散列地址。最小哈希算法是哈希算法的一种，传统的最小哈希算法(Minhash)主要应用于快速推算多个数据集合之间的相似程度，现已被应用于多个热点研究领域，如文本操作、视频数据处理等。Minhash算法主要依据Jaccard相似度进行相似推算。

以MapReduce架构理论为基础，通过Minhash算法进行并行化分析，设计出一种基于并行计算的高效疏化处理算法，即MR-LSH算法。MR-LSH算法使用并行计算MapReduce框架结构对图聚类分析稀疏化操作过程中的多个任务进行了高效的推算分析与处理，这些任务包括邻居结点数据集合推算、Minhash算法签名推演(对于每个结点而言)、每个结点之间的签名哈希存储以及图聚类过程中的稀疏化处理计算。并在Hadoop计算环境下，对MR-LSH算法的性能进行了模拟实验与分析，实验结果表明，MR-LSH算法的应用能够保证图聚类稀疏化分析与处理机制的高效性。

疏化处理算法依据模拟实验中采用的图模型稀疏化处理机制的不同，其图模型稀疏化比率参数值e也随之改变，为了应对不同数据信息量与分类的图模型数据信息，其最佳e值也会有所不同，本实验初始化e=0.15，然后进行相关操作。为了显示出MR-LSH算法在超大规模、超大区域范围的分布式集群计算环境下的高效性能，模拟实验中采取多种并行计算环境下的执行算法。MR-LSH算法首先对Map任务阶段与Reduce任务阶段进行过程处理，其次对图模型数据信息进行分析，实现图聚类过程下稀疏化分析与处理机制。

从模拟实验分析结果可知，对于超大规模、超大区域范围的分布式集群计算环境下，使用Ha-doop并行计算平台能够有效降低时间损失，从而使得Speedup得到大幅度提高。依据并行计算平台理论架构体系的原理，图模型数据信息规模愈大时，其图聚类过程稀疏化比率参数值就增大，且呈现线性关系;然而随着分布式集群计算环境下各个结点的通信交互频繁，也会消耗一定数据信息性能，在图模型数据信息交互规模较小时，图聚类过程稀疏化分析与处理机制会降低，其e参数值同比减小。与此同时，当Speedup与分布式集群计算环境逐渐增加时，其图聚类过程稀疏化分析与处理机制会有所提高，其e参数值同比增加2。

通过模拟实验可知，新型的MR-LSH算法适用于超大规模、超大区域范围的分布式集群计算环境下的图数据信息，由于在MR-LSH算法中添加了排序组合机制，使得结点与邻接结点之间的通信交互消耗得到降低，即图数据信息规模愈大，其MR-LSH算法效率性价比愈高。