基于Spark的层次聚类算法的研究与应用

Based on the Hierarchical Clustering Algorithm Research and Application of Spark

摘要: 信息化高速发展的时代，信息数据大量产生，如没得到较好的整理归类，就无法满足对数据查找和使用上的快捷便利与准确性。随着信息安全科学技术的发展，这些数据在整理分类上的需求日益增长，但是在传统的聚类算法上，已经不能满足现在信息数据处理的需要。因此，对原算法的优化改进或重建新的算法成为现在最为迫切的事情。同时，在海量的数据处理上，单台计算机的硬件设施也无法满足对数据处理分类的需求。针对上述情况，基于Spark在分布式计算框架的基础上，本文对聚类算法进行了优化改进。利用Apache Spark的大数据处理框架，扩展了对计算模型的使用，并在内存上提供可以并行的计算框架，利用借着中间结果缓存在内存中，减少磁盘I/O的重复操作次数，从而可以更好地为迭代式计算、交互式查询等多种计算需求服务。通过对聚类算法的优化提高对数据分析处理归类的计算效率，实现本文研究的意义。

Abstract: In the era of rapid development of information technology, a large number of information data are generated. If they are not properly sorted and classified, they cannot meet the requirements of fast, convenient and accurate data search and use. With the development of information security science and technology, the demand for sorting and sorting of these data is increasing, but the traditional clustering algorithm can no longer meet the needs of current information data processing. Therefore, the optimization and improvement of the original algorithm or the reconstruction of a new algorithm has become the most urgent thing now. At the same time, on huge amounts of data processing, a single computer hardware facility cannot meet the demand of classification of data processing. According to the above situation, this article is based on the Spark in a distributed compu-ting framework, on the basis of the clustering algorithm is optimized to improve. The use of Apache Spark's big data processing framework extends the use of the computing model, and provides a parallel computing framework in memory. By caching intermediate results in memory, the number of repeated disk I/O operations can be reduced, so as to better serve the needs of iterative computing, interactive query and other computing requirements. Through the optimization of clustering algorithm to improve the computational efficiency of data analysis, processing and classification, the significance of this study is realized.

1. 引言

随着科学技术尤其是信息化技术的蓬勃发展，信息大数据如雨后春笋的增长。近十年以来，互联网一直处于社会发展的风口浪尖上，各大电商网络平台也在政府的大力支持帮助下，得到了快速成长。产业发展，不但拉动了经济的增长，也促使信息数据大量的产生。这些海量的数据在短时间内涌现，产生了数据混乱无序、杂乱无章的结果。因此，数据处理分析与分类管理就显的尤为重要，就目前的数据管理技术，对一般的基础数据尚能管理，但是无法满足海量大数据的管理分类要求，达到快速、高时效性的要求。

通过对数据基本分类划分，可分为结构化数据和非结构化数据。结构化数据处理分析技术已经比较成熟，但非结构化数据因其信息种类繁多、结构复杂以及数量巨大等原因，以现在的技术无法满足数据管理分析的要求，因此在技术开发处理上也亟待解决。通过利用对大数据处理工具的层次聚类算法的研究，将其应用于对海量大数据的信息处理分析，高效快速地分析整理出结果，实现数据的时效价值。

现在主流的大数据处理框架，比如Spark与Hadoop等工具。这些可扩展、分布式以及并行化的大数据处理工具渐渐进入政府、学校与企业中，取代之前相对落后的技术计算框架。基于内存计算的Spark框架是一款性能较好的数据处理工具。最早于2009年Spark大数据并行化处理框架被提出，并于下一年宣布开源。通过数个大数据公司的开发研究，Spark的生态系统越来越完善，在性能提高的同时也简化其代码可读性和开发的难度。

聚类算法面对海量大数据，其在数据处理方面就无法满足信息化价值的要求，通过引进分布式计算框架技术，完美解决了聚类算法在处理海量大数据的不足。

Spark拥有比较好的抽象化编程模型，单独处理除算法逻辑以外的其他所有问题，用户操作简单方便。同时，Spark编程模型是将输入的大数据转化为自定义的RDD，而且RDD拥有较多的操作算子，在满足一般的计算分析操作同时，也算对RDD的操作过程，所以所有操作计算过程都是RDD的迭代过程。Spark通过合理充分利用计算机内存，减少计算过程中产生中间结果对磁盘I/O读写，提高计算效率。

2. 相关知识

2.1. Spark分布式工具

2.1.1. Spark简介

Spark作为一个开源大数据计算框架，是以Scala为开发语言，利用Scala独特的函数式编程思想，提供较好的编程模型 [1]；Spark的运行模式是将自定义的程序，各自发送给集群的从节点，然后让Worker各自进行运算 [2]。让Spark分布式编程成为真正简单化的开源软件。

Spark在拥有Map Reduce的线性扩展与容错性同时，也进行了较多的本质扩展，大大提高了对内存利用的效率 [3]。Spark首先对Map进行操作，然后对Reduce进行编程模式；并优化Spark引擎，使其可以运行通用的有向无环图算子 [4]。Spark将运行的中间结果，通过内存传递给下一个程序，减少运行结果的多次写入次数。而且Spark还有一大特色，就是将弹性分布式数据收集RDD中，将代码中的任意数据都映射到集群节点中，让后续计算分析步骤相当于初始数据，无需对磁盘重新读取，减少运行时间 [5]。

2.1.2. Spark的构架

Spark的核心机制RDD是基于分布式内存的并行数据结构，它将数据存储在内存中，通过控制分区划分，优化数据分布 [6]。

Spark支持八十几种高级的算法，也支持很多种计算机语言，其中就包括了Java和Scala。Spark 兼容的文件系统有：Cassandra、Amazon S3、HDFS与HBase等 [7]。Spark的解决方案用于机器学习、图计算、交互式查询、处理离线数据和实时数据流，并且这些处理方式可以在同一个程序中无缝对接 [8]。

Spark在集群计算中，将这些数据集缓存在各个节点的内存中，减少对磁盘I/O的操作，节省时间，提高计算效率 [9]。

Spark拥有较好的兼容性，与其它开源软件可以很方便进行融合。因其自身内部调度框架是Standalone模式，所以Spark不会依赖第三方资源管理和调度系统 [10]。

Spark的运行构架见图1所示。

2.2. 聚类算法的类型

聚类算法的划分，可以分为六类：层次聚类，密度聚类，网格聚类，模型聚类，图聚类和划分聚类等。这些聚类算法各有各自的优势与特点，它们所对应的模式也各不相同，一般根据实际状况、数据的类型、结构和分析目的要求等来选取对应的聚类算法 [11]。

3. 聚类算法的优化使用

聚类算法是众多数据挖掘中的一种比较高级的算法，它也算无监督学习算法 [12]。聚类算法是将数据对象集划分为数个组或者多个簇的算法过程，它使划分后的各组或各簇内的集拥有较高的相似性，而各组或各簇之间亦不相似 [13]。

Figure 1. Shows the running architecture of Spark

图1. Spark的运行构架图

3.1. 聚类算法中的距离

3.1.1. 切比雪夫距离

以两个点p与q作为例，其对应的坐标就为p_i，q_i。这两个点之间的切比雪夫距离为公式1：

$d\left(p,q\right)=\max \left(\left|p_i-q_i\right|\right)$ (1)

此距离相当于 $\mathcal{L}p$ 度量的极值： $\underset{n\to \infty }{\lim }{\left({\displaystyle {\sum }_{i=1}^n{\left|p_i-q_i\right|}^k}\right)}^{1/k}$，因此切比雪距离又可称为 $\mathcal{L}\infty$ 度量。

a) 在平面中，如果两个坐标点是 $a\left(x_1,y_1\right)$， $b\left(x_2,y_2\right)$，则切比雪距离为：

$d_{12}=\max \left(\left|x_2-x_1\right|,\left|y_2-y_1\right|\right)$ (2)

b) 在n维空间中，两个坐标点为 $a\left(x_{11},x_{12},\cdots ,x_{1n}\right)$， $b\left(y_{11},y_{12},\cdots ,y_{1n}\right)$，则切比雪距离为：

$d_{12}=\max \left(\left|x_{1i}-x_{2i}\right|\right)$ (3)

根据上述的 $\mathcal{L}p$ 度量极值 $\mathcal{L}p$，因此该公式的等价公式是：

$d_{12}=\underset{k\to \infty }{\lim }{\left({\displaystyle {\sum }_{i=1}^n{\left|p_i-q_i\right|}^k}\right)}^{1/k}$ (4)

3.1.2. 欧式距离

欧式距离的定义是在n维空间上，两个点中间的真实距离。比如以下两点 $x\left(x_1,x_2,\cdots ,x_n\right)$ 和 $y\left(y_1,y_2,\cdots ,y_n\right)$ 之间的距离为：

$\begin{array}{c}d\left(x,y\right)=\sqrt{{(x_1-y_1)}^2+{\left(x_2-y_2\right)}^2+\cdots +{\left(x_n-y_n\right)}^2}\\ =\sqrt{{\displaystyle {\sum }_{i=1}^n{\left(x_n-y_n\right)}^2}}\end{array}$ (5)

a) 两个二维向量的点 $a\left(x_1,y_1\right)$， $b\left(x_2,y_2\right)$ 之间的欧式距离：

$d_{12}=\sqrt{{\left(x_1-y_1\right)}^2+{\left(x_2-y_2\right)}^2}$ (6)

b) 两个三维向量的点 $a\left(x_1,y_1,z_1\right)$， $b\left(x_2,y_2,z_2\right)$ 之间的欧式距离：

$d_{12}=\sqrt{{\left(x_1-y_1\right)}^2+{\left(x_2-y_2\right)}^2+{\left(z_1-z_2\right)}^2}$ (7)

c) 两个n维向量的点 $a\left(x_{11},x_{12},\cdots ,x_{1n}\right)$， $b\left(x_{21},x_{22},\cdots ,x_{2n}\right)$，之间的欧式距离：

$d_{12}=\sqrt{{\displaystyle {\sum }_{k=1}^n{\left(x_{1k}-x_{2k}\right)}^2}}$ (8)

3.2. BIRCH聚类算法

BIRCH全名是Balanced Iterative Reducing and Clustering Using Hierarchies，利用利用层次方法的平衡迭代规约和聚类 [14]。这种算法属层次聚类算法，在相同内存容量，它可以处理更多的数据；在相同数据量下，它的处理速度更快 [15]。因其具有独特的结构逻辑，一次扫描数据就能完成对数据的分析，用最小化的I/O处理，换成高质量聚类数据 [16]。

CF向量是三元组的簇聚类特征 [17]，依据给定聚类数据集，N个d维数据点：

$CF=\langle n,LS,SS\rangle$ (9)

关于簇的形心x₀，直径D和半径R，分别做公式的推导，通过数据和的平均值：

$x_0=\frac{{{\displaystyle \sum }}_{i=1}^n{x}_i}{n}=\frac{LS}{n}$ (10)

直径D是簇中每两点之间的平均距离：

$D=\sqrt{\frac{{{\displaystyle \sum }}_{i=1}^n{{\displaystyle \sum }}_{j=1}^n{\left(x_i-x_j\right)}^2}{n\left(n-1\right)}}=\sqrt{\frac{2nSS-2L{S}^2}{n\left(n-1\right)}}$ (11)

半径是簇中数据点到形心的平均距离：

$R=\sqrt{\frac{{{\displaystyle \sum }}_{i=1}^n{\left(x_i-x_0\right)}^2}{n}}$ (12)

通过直径和半径来观察簇中数据的聚集紧密程度，用作判断聚类效果的标准，从中挑选出最优聚类簇 [18]。

3.3. 聚类算法的优化

针对BIRCH算法的优化改进，输入n个聚类对象的数据集合 $D=\left\{x_1,x_2,\cdots ,x_n\right\}$，结果聚类簇的个数为k，输出k个聚类簇。

步骤如下：

a) 初定参数 $\mu$ 和 $\sigma$，经公式

$x_i=\frac{u_i}{{\sigma }_i}\left[\left(\frac{x_i{\sigma }_i}{{\mu }_i}\right)+\frac{1}{2}\right],i=1,2,\cdots ,d$ (13)

转换成汇聚点，将这个汇聚点和初始点的进行个数的比较，对参数 $\mu$ 和进行数值的调整，让其比值介于0.01~1中间，得到汇聚后的点；

b) 扫描汇聚后点，用聚类算法进行处理，结果得出k个簇；

c) 进行操作聚类簇的全排列；

d) 参考k值；如果k值小于5，就用BIRCH算法对所有排列进行操作；如果大于5，就用BIRCH算法对随机抽取十个进行操作。

3.4. 聚类算法并行编程模型

对于数据的并行模式，当环境相同时，其逻辑代码也是一样的，只有计算使用的数据不相同。主要是为了利用数据间不具联系数据的共同运算，数据先运行，再分类，并且多个程序并行执行，提高运行效率。

3.5. BIRCH聚类算法并行化

通过Spark工具来对BIRCH算法进行并行化应用。解决海量数据的井喷，单台计算机无法满足数据整理分析归类的要求，因此通过分布式集群来解决这一问题。Spark工具平台对BIRCH算法的运行流程图见图2所示。

Figure 2. Operation flow chart of BIRCH algorithm

图2. BIRCH算法的运行流程图

4. 基于Spark的大数据聚类应用

通过在物理机上塔建Spark分布式集群来进行试验。首先将系统网络根据试验的需求来配置防火墙端口，然后对Hadoop集群进行搭建，根据需求选好相应的组件，再对物理机上塔建Spark集群，最后是安装部署GeoMesa。

4.1. 实验数据分析

本文将改进的算法应用于实际的大数据分析中，分析的数据是来自在高校实验室管理中应用采集数据。大数据对高校实验室的管理，有利于将安全管理进行职能化，将各实验室的门锁用门禁系统所替代，实行刷卡进出，对刷卡数据进行采集，为提前做好实验室安全事故人员疏散作保障；并通过视频监控系统对进出实验室人员进行监督信息采集，利用大数据的分析提高仪器、设备使用率，为仪器、设备运转提供所需的保障；通过数据现象和统计分析，协助科技人员对技术的开发和升级，促进大数据实验室管理升级，提高高校实验室的实验教学质量。

4.1.1. 数据结构分析和提取

对门禁系统经过数据筛选，留下进出人员用户的身份IP，门禁IP和数据上传时间，具体如表1所示。

Table 1. Data structure table

表1. 数据结构表

将该实验楼的所有的门禁系统IP也输入系统，并提前清除该区域内需要特殊权限开启门禁的数据，减小计算量，提高分析效率。

4.1.2. 数据结构分析方法

数据结构分析方法有两种，其一就是对全体数据进行聚类操作，其二就是对独特的簇进行具体的关系分析。

a) 聚类数据

对所有的数据进行聚类分析，筛选出聚类簇中数量较多的簇，通过排序得到数量较多的簇，存储簇的中心点，再根据中心点在实验室所在的教学楼上呈现具体的物理IP位置。

b) 聚类簇内部分析

聚类数据分析后，就会将这些数据存储在GeoMesa数据库里，利用特殊的时间和事件来分析数据。

4.2. 实验结果

通过上面的聚类算法数据统计，排出前面几位实验室人次数比较多，相对集中的的区域，通过得知该区域实验室人员比较密集，并为学校建议该区域实验室作为防火防灾的重点区域，进行保护防范，同时对实验室里的仪器设备维护管理作为重点关注对象，进行有效管理。根据数据的分析，提前做好预测分析，为高校实验室进行规划管理提供参考，做到防患于未然，有效提高仪器设备使用效率，并做好仪器设备的维护保养工作。

5. 结束语

经过实验验证，对聚类算法的优化，在性能上有所提高。为高校实验室人员的区域密集度分析做出了分类统计功能，取得了一定的成果，分析出了特殊的区域，特定的时间会在什么区域出现人口密集度较高的情况等。

在改进BIRCH算法上，原来不能直接并行化运行在Spark分布式工具平台上，现在不仅可以直接运行，还简化了数据量，减少了运行时间，提高了效率。在后续的工作中将继续对算法进行优化，提高效率，通过实验，一步步提高精确度。

基金项目

教育部科技发展中心高校产学研创新基金——新一代信息技术创新项目(2018A02027)；教育部科技发展中心高校产学研创新基金——新一代信息技术创新项目(2018A01015)；共青团广东省委员2019年广东大学生科技创新培育专项资金项目《知识产权大数据分析与服务系统设计》(pdjh2019b0775)。

参考文献

NOTES

^*通讯作者。