英语原文共 6 页，剩余内容已隐藏，支付完成后下载完整资料

基于Spark的大数据集稀疏关联规则挖掘

刘瑞林, 杨凯, 孙燕佳, 权涛, 杨瑾

华为研究院

{ruilin.liu1,yanjia.sunl,quantao,jin.yang}@huawei.com

同济大学, 中国

ky2l23@columbia.edu

摘要—如今，无线网络的质量对于网络服务提供商（NSP）来说至关重要。糟糕的执行网络可能导致客户投诉，甚至损失用户流失的收入。为确保服务质量，具体用例质量的关键质量指标（KQI）已经与网络性能计数器（NPC）一起进行了网络性能分析。首先，NSP挖掘网络性能数据以发现可能导致用户体验差的KQI异常。如果检测到任何KQI异常，则NSP会调查相关的NPC以识别可能的根本原因。由于用例数量急剧增加，网络性能数据量日益增长，无线网络异常根源分析变得非常具有挑战性。如何有效地发现NPC和KQI异常值之间的关系成为确定无线网络异常的根本原因的关键。为了解决这个问题，本文提出了一种高效的稀有关联规则挖掘算法，称为基于Spark的稀疏关联规则挖掘（SRAM），它不仅利用了FP-growth算法的效率，而且还利用了Spark平台的强大的大数据处理机制。我们在Spark平台上实现了我们的算法，并用各种数据集进行了测试。结果表明，我们的方法可以有效地从大量数据中挖掘稀疏关联规则。

引言

智能移动设备的数量在过去几年中大幅增加。新兴趋势带来了无线网络的两大变化。首先，它创建了许多用例，如视频流，网页浏览和蜂窝网络上的VOIP呼叫。第二，它产生大量的网络流量数据。根据statista.com [l]，在2015年，美国每天生成超过26万亿兆字节（MB）的数据流量。为了提供更好的网络服务，网络服务提供商（NSP）通过不断收集称为网络性能计数器（NPC）的网络流量数据来监测网络性能，这些网络流量数据在各个级别（例如小区级RNC级）上。当检测到NPC价值降级和异常值时，NSP研究异常情况，以确定可能的根本原因，并进行修复。如今，智能手机和平板电脑等智能移动设备的普及，无线网络的使用成为普遍存在，并且显着多样化。 NPC作为无线基础设施的状态柜台，不足以反映网络浏览和视频流等特定用例的服务质量。因此，测量特定服务质量的关键质量指标（KQI）已被引入到无线网络质量分析中。 NSP不是监视NPC，而是检查异常值的KQI数据。当检测到异常KQI时，NSP分析与该KQI相关的所有NPC以识别可能的根本原因。例如，网路下载速度较慢可能是由于拥堵或覆盖率不佳造成的。如果NSP已经识别出与同一时间帧下降的吞吐量有关的NPC，那么坏的KQI可能由于交通堵塞而导致。

根本原因分析旨在找出KQI异常与NPC之间的关系，并确定网络性能下降的根本原因，成为NSP的重要需求。由于新类型的KQI / NPC不时增加，移动设备产生的会话数量爆炸式增长，实现根本原因分析的高质量和高效率是非常困难的。

在本文中，我们提出了一种基于FP-growth算法的基于Spark的稀疏关联规则挖掘（SRAM）的高效算法[2]，并利用大数据计算平台Spark [3]的功能来分析KQI / NPC数据，并找出KQI降解的根本原因。

本文的其余部分组织如下。在第二节中，我们介绍了我们用于网络根本原因分析的稀疏关联规则挖掘（SRAM）算法的基础知识。在第三节中，我们将描述我们如何使我们的算法平行提高效率。在第四节中，我们将解释我们的SRAM如何去除冗余规则。在第五节和第六节中，我们讨论了我们的算法的Spark实现和实验结果。最后，我们在第七节总结本文。

稀疏关联规则挖掘

为了确保服务质量，NSP监控网络性能数据中的KQI数据。 NSP采用异常值检测算法来识别KQI的异常值（异常值）。如果KQI异常值意味着网络服务的质量下降，则NSP将通过分析相关的NPC来调查其根本原因。现在，异常值检测算法是非常发达和广泛使用的。在工业中，异常检测方法通常是半监督的，涉及到工程学和机器学习技术。由于异常值检测不是本文的主要焦点，因此采用简化的异常检测算法，该算法使用华为无线服务工程师常用的异常检测阈值。在本文的其余部分，我们假设KQI已经被标记为“异常”或“正常”。

为了发现KQI异常与NPC的关系，我们采用关联规则挖掘（ARM）的思想。 ARM已经在电信网络领域得到广泛的应用[4]。然而，由于关联规则挖掘主要集中在从事务数据库中查找经常发生的项目集合，这些事务数据库由逐项变量列表组成，所以挖掘网络根本原因分析的“有趣”关联规则是非常具有挑战性的，这些规则通常集中在KQI异常很少发生。有两个主要挑战。首先，通常是数值的KQI和NPC必须转换成分项变量;第二，在大多数时候，KQIs和NPC都处于蜂窝网络的正常和健康状态[5]，我们不能直接应用传统的关联规则挖掘算法，它将重点放在频繁发生的模式上。

在本节中，我们介绍我们罕见的关联规则挖掘算法。首先，我们首先列出每个KQI / NPC值，然后应用修改后的关联规则挖掘算法来寻找稀疏关联规则。在本节的其余部分，我们首先介绍传统关联规则挖掘算法的背景，然后讨论我们提出的稀有关联规则挖掘算法。在下一节中，我们将展示如何使罕见的关联规则挖掘平行。

传统关联规则挖掘

由Agrawal等人介绍传统的关联规则挖掘是一种从大型交易数据集中的高度相关变量中发现有趣规则的方法。给定m个变量。令D是n个交易的交易数据集。每个事务由I的子集组成。关联规则，当且，X称为r的左侧（表示为lhs（r）），Y称为r的右侧（表示为rhs（r））。 lhs（r）是表示规则r的条件的前提，而rhs（r）是结果，如果满足lhs（r），则表示可能的结果。例如，从超市的销售数据库中获得的关联规则{milk，diaper} =gt; {beer}表明，如果其中一个客户一起购买了牛奶和尿布，那么他/她也很有可能会拿一瓶啤酒。

协会规则挖掘旨在发现“有趣”的规则。具体来说，术语“有趣”通常被解释为以下概念：

• 支持表示包含特定项目集的交易的比例，表示为。
• 置信度表示一个规则已被满足的概率，计算为。

此外，关联规则挖掘具有较少使用的概念，称为提升，其定义为：

Lift表示对结果Y的规则的增强。如果提升大于1，那意味着X和Y依赖，当X发生时，Y的概率要高得多。由于提升可以有效地描述关联规则的影响，无论其原始支持如何，所以理想的是用于测量不频繁项目集之间的关系。我们采用提升作为我们罕见的关联规则挖掘算法的重要测量。传统的关联规则挖掘算法通常使用两个阈值最小支持（表示为）和最小置信度（表示为）来识别关联规则。这些算法的框架包括两个步骤：

1）首先，应用最小支持阈值来查找数据集D中的所有频繁项集。

2）然后，使用这些频繁项集的最小置信度来生成关联规则。

在过去几十年中，已经提出了一些关联规则挖掘算法，如Apriori算法[7]，Eacute;clat算法[8]，FP-growth算法[2]等等。Apriori方法[7]使用广度优先策略来查找频繁项集。从单个项目开始，它迭代地搜索数据库以找到一个项目的频繁项目集。在每次迭代k中，所发现的大小为k-1的项目集用于生成大小为k的项目集。然而，在处理大型数据库时处理生成的候选者不仅非常昂贵，而且对于重复扫描数据库以进行模式搜索也是乏味的。 FP-growth算法[2]是频繁项集挖掘最流行的算法之一。它开发了一种高效的FP树，用于存储整个数据库的压缩和关键信息。我们罕见的关联规则挖掘算法是基于FP-growth方法。

B.用于KQI / NPC数据的稀疏关联规则挖掘

在无线网络性能数据库中，从蜂窝网络收集的每个记录由KQI（例如web延迟，web吞吐量等）和一组相应的NPC组成。由于KQIs和NPC都是反映网络状态的数值，在讨论我们罕见的关联规则挖掘算法之前，我们简要介绍了无线网络性能数据库中的KQI / NPC分项。对于KQI值，我们使用异常检测方法将值分为“正常”和“异常”项。对于NPC值，根据NPC计数器的类型，逐项进行的方式不同。例如，报警类型的NPC在报警时只有非零值，分为“正常”和“报警”项。对于比例类型NPC（例如，呼叫丢弃率，分组丢失率等），我们根据它们的分布将它们分组成多个分组。在本文中，由于KQI / NPC分项目不是主题，在下面的讨论中，我们假设KQI / NPC已经被列出。

网络中KQI / NPC的关联规则表示为Vp。 Vq，其中Vp是一组逐项NPC，Vq是一组逐项KQI。关联规则解释项目集Vp和Vq之间的关系。如果Vq是“异常”KQI，则该规则被认为是“有趣的”，表明仅当这些逐项NPC出现在Vp中时才能发现“异常”KQI。我们使用支持来测量它们在数据集D中的发生百分比。例如，表示在D中的60％记录中发生Vq和Vp的分组。另外，使用置信度来测量对数据集D中的规则进行正确的预测。例如，表示含有Vp的80％记录也包含Vq。除了支持和信心，我们使用提升来测量Vp和Vq同时出现的支持比例，如果Vp和Vq是单独发现的话。在稀疏的关联规则挖掘中，提升是解释Vp和Vq的关系的重要指标，即使在某些情况下很少发生Vp和Vq的关系，例如检测到异常值。当提升值大于1时，该关系被认为是正的，否则为负。当提升为零时，没有关系。

现在，我们准备基于FP-growth算法介绍基于Spark的稀疏关联规则挖掘（SRAM）方法，以发现解释KQI和NPC之间关系的关联规则。简而言之，SRAM通过扫描数据库两次构建FP-tree。在第一遍中，构造了一个项目头表，以保存数据库中所有项目的出现次数。列表按照按降序排列的项目出现次数排序。该列表可以通过加快每个项目的支持计算来加快修剪过程。此外，我们的SRAM算法还使用提升修剪分支，即使具有频繁的子模式，但升力小于。在第二遍，SRAM通过添加分支来构建FP-tree。最初，FP树的根被构造为标记为“NULL”的变量节点。对于数据库中的每个会话，我们首先按会话的顺序排列会话中的所有项目（按照项目头表中的相同顺序）排序。第二，创建分支，作为从根节点到此会话中所有有序项目的路径。然后分支将合并到FP-tree中。 FP-tree中的每个节点都存储一个跟踪包含该节点的会话数的计数器。如果分支是新的，它将直接添加到FP-tree中。当分支存在时，计数器将相应更新。一旦完成了FP-tree的构建，SRAM开始挖掘与KQI异常值相关联的有价值的模式。

除了考虑用于稀疏项挖掘的提升，我们通过添加并行处理所有可用项目的能力来优化FP-growth算法。更好的是，SRAM可以在挖掘不频繁的项目时同时生成关联规则。我们将在第三节中详细介绍。

平行稀疏关联规则挖掘

随着世界各个领域收集数据量的迅速增长，传统的关联规则挖掘算法如Apriori和FP-growth变得非常低效。开发并行算法以更好地利用内存并降低每台机器的CPU成本。在关联规则挖掘算法中，基于Apriori的算法需要执行多个数据集扫描，花费太多时间，特别是在大型数据库中。另一方面，可以容易地消除子任务之间的计算依赖关系的FP增长算法是并行计算的更好的候选者。已经提出使用MapReduce [9]模型的并行FP-growth（PFP）算法。 PFP可以通过MapReduce方式平行构建FP树来实现更好的性能[9]。华为已实施PFP算法，并将其贡献给Apache Spark 1.3 [10]。 PFP根据事务的足够分配不断增长的FP-tree的工作，因此比单机实现更具可扩展性。然而，关联规则生成步骤取决于频繁项集挖掘的结果，这可能是瓶颈，特别是当数据集的大小较大时。在数百万用户的典型无线网络中，流量速率可以达到每秒TB，从而驱动每秒从基础网络设备生成的千兆字节事件日志。因此，固有的计算显着影响了矿业关联规则的进一步分析。对于这种情况，为了实现更好的性能，我们的SRAM算法融合了两个步骤。具体来说，SRAM挖掘关联规则，而FP-tree生成。

为此，我们利用Apache Spark平台[3]的优势。与Hadoop的MapReduce相比，Spark将数据存储在内存中，并实时管理分布式任务。我们优化了SRAM算法，以充分利用Spark。首先，SRAM算法维护两个列表：F列表和G列表。像PFP一样，SRAM将所有项目I存储在F列表中。此外，SRAM将F列表中的所有项目分为Q组。每个组都会分配一个唯一的组ID（gid）。组信息存储在组列表（G-list）中。然后，每个事务将根据其所包含的项目分配一个或多个组ID。

在找到诸如PFP的频繁项目之后，不是挖掘关联规则，而是在构建相应的FP树之后，首先需要一次通过产生项目聚合节点HashTable。

在Map阶段，映射器为G列表中的每个组生成一个节点HashTable。具体来说，每个映射器读取G列表以获得与相同gid相对应的项目列表。对于每个项目，映射器输出一个键值对（key = Ij，value = HT（Ij），其中每个键Ij是项目（Id），并且其对应的值如下生成。

对于每个HashTable，映射器执行以下操作：

1）从G列表中选择一个项目ID，Ij。

2）为包含item-id，Ij的FP-tree的每个分支生成HashTable。 HashTable的记录

被形成为键值对key = item-id（Ij），value = freq（Ij）。关键值是分支上出现的项目Ij，值是FP-tree分支上项目从计数中捕获的项目的频率。

来自同一组的所有键值对都形成一个HashTable。除了键值对之外，HashTable为事务中发生的每个项目保留计数器。可以从FP树中读取计数。 HashTable表示包含项目ID Ij的FP-tree（一个事务）的分支。

在所有映射器实例完成之后，对于每个不同的密钥值，SRAM为每个分支创建一个HashTable作为值。输出通过键值对（key =

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[25555]，资料为PDF文档或Word文档，PDF文档可免费转换为Word