基于自编码技术的ACT-Apriori算法

摘要

基于自编码技术的ACT‑Apriori算法，首先，对事务数据库D进行预处理，将事务数据库D中各项目的高频参数NS忽略并用自编码位向量SNT代替，形成简化数据库RBD，使得数据维度大幅度降低；将数据记录简化后全部读到内存，在频繁项集连接、剪枝生成候选项集的过程中，对生成候选项集的过程进行改进，直接生成候选项集，得到候选项集后扫描数据库计算支持度，由于候选项集与简化数据库RBD均已排序，在每条记录中分别搜索候选项集时，一旦搜索到大于候选项的值时，即可停止该事务的搜索。相较于现有全新的关联规则算法，本发明算法计算时间大幅度缩短，内存占有率较大程度降低，在时间复杂度和空间复杂度上有明显优化。

说明书

技术领域

本发明属于大数据挖掘算法技术领域，具体涉及一种基于自编码技术的ACT-Apriori算法。

背景技术

智能电网是利用现代网络信息技术等实现电网设备间的数据信息交换，从而实现电网实时自动化控制、智能调节、在线决策分析等功能的新型电网。智能电网的建设积累了海量数据资源，目前电力公司基于数据管理企业，基于信息驱动业务的需求日益迫切。而智能电网大数据具有“4V”特征，即：数量大(Volume)、种类多(Variety)、速度快(Velocity)、价值密度低(Value)。近年来，电力信息化日臻完善，电力设备状态监测、生产管理、运行调度、环境气象等数据逐步实现集成共享，大数据技术为电力设备状态评估和故障诊断提供了全新的解决思路和技术手段。但是随着智能电网的发展和电网规模的迅速增长，及时、准确地掌握电力设备运行状态面临巨大的问题和挑战，传统的数据处理方法已经难以满足需求，因此学者们提出了一系列大数据挖掘算法。

关联规则挖掘算法由Agrawal首先提出，该方法从大量历史数据中寻找频繁项或属性之间的关联性。现有的关联规则挖掘算法主要是Apriori算法及频繁模式树FP-Tree(Frequent Pat-tern-Tree)算法。(1)：Apriori算法的主要缺点是需要寻找大量的侯选项目集，当数据库较大时，存在组合爆炸问题，同时，Apriori算法需要多次扫描数据库，增加了计算的负担。(2)：FP-Tree算法存在的主要问题为：挖掘过程中需要不断递归地生成“树”，增加了时空复杂度；FP-Tree和条件FP-Tree每次都需要双向遍历数据库，因此难以处理数据库更新、维护问题。

总结来说，现有的关联规则算法存在两个亟待突破的瓶颈，一是多次扫描数据库产生了巨大的I/O占用率；二是产生了庞大的候选项集，对算法的运行时间和内存占用上带来了巨大的挑战。

发明内容

本发明的目的在于提供一种基于自编码技术的关联规则算法—ACT-Apriori，解决了传统的Apriori算法和FP-Tree算法需要两次扫描全局数据库增加了计算负担，当数据库较大时，容易产生组合爆炸的问题。相较于现有全新的关联规则算法，其计算时间大幅度缩短，内存占有率较大程度降低，在时间复杂度和空间复杂度上有明显优化。

本发明采取的技术方案为：

基于自编码技术的ACT-Apriori算法，首先，对事务数据库D进行预处理，将事务数据库D中各项目的高频参数NS忽略并用自编码位向量SNT代替，形成简化数据库RBD，使得数据维度大幅度降低；

将数据记录简化后全部读到内存，在频繁项集连接、剪枝生成候选项集的过程中，对生成候选项集的过程进行改进，直接生成候选项集，得到候选项集后扫描数据库计算支持度，由于候选项集与简化数据库RBD均已排序，在每条记录中分别搜索候选项集时，一旦搜索到大于候选项的值时，即可停止该事务的搜索。

基于自编码技术的ACT-Apriori算法，包括以下步骤：

步骤一、数据预处理阶段：

首先，计算事务数据库D中各项目的支持度计数并以降序排列；其次，设定项目的高频参数NS，在事务数据库D中通过选定的高频参数NS忽略部分频繁项集L，并将其用自编码位向量SNT表示，同时建立频繁项列表TF和频繁项目集列表TI，最终形成简化数据库RBD；

步骤二、频繁项集生成阶段：

S2.1：使用简化数据库RBD替换原始事务数据库D；

S2.2：在Tree数据结构中的每个节点添加新的大小为2

S2.3：设置最小支持度阈值MinSup并进行迭代，通过判断式c.TFISup[i]>MinSup在每一次迭代中进行剪枝操作，最终确定频繁项集。

所述步骤一中，

1)事务数据库D：表示存储所有已发生事务的数据集合；

2)频繁项集L：表示事务数据库D中的频繁项集，L(k)表示频繁项集L中的频繁k项集，关联规则挖掘算法的主要任务是寻找全局频繁项集L；

3)高频参数NS：表示在数据预处理阶段必须从事务数据库D中选择的频繁项集的数量。高频参数NS表示与事务数据库D中的其他事务相比，出现频率更高的事务的数量。

4)频繁项列表TF：表示数据库中的项目按其出现频率排序和选定的高频参数NS的参数情况，选择所有高频参数NS项来创建出的列表。TF列表中的每一项都被称为“最常见(频繁)项目”或“TFI”。

5)频繁项目集列表TI：项目集列表可以从TF中创建，频繁项目集列表TI代表了TF中所有可能的排列组合。频繁项目集列表TI中每个项目集的长度介于0(空集)到高频参数NS之间。其中：频繁项目集列表TI的每个成员称之为TFIT，TFIT的数量为2

6)简化数据库RBD：表示在数据预处理阶段创建的数据库。在简化数据库RBD中，TFI被一个自编码位向量代替，该位向量表示它们在每个事务中所存在的位置。为了创建简化数据库RBD，从原始事务数据库D中的每个事务中移除频繁项集L，并将它们用自编码位向量存储到一个新的字段中。这个用来存储频繁项目自编码位向量的新的字段叫做交易位SNT。

所述步骤二中，在候选频繁项集生成中，由于TFI不再包含在事务数据库D中，它们不会被添加到候选频繁项集。相反，在Tree数据结构的每个节点中添加了一个新的支持计数器列表，称为TFISup，用于跟踪TFIs，并且与原始Apriori算法相比不会丢失任何结果。每个TFISup实体代表相关项集和其中一个TFI的组合。

TFIs指的是频繁项列表TF中所有项TFI的总称TFIs。注意:类比英文中的可数名词加复数s，每一个TFI为单数，多个TFI总称为TFIs。

TF指的是频繁项列表:NS参数表示与数据库中的其他项目相比，出现频率更高的项目的数量。数据库中的项目按其出现频率排序，选择第一个NS项目来创建TF列表。TF列表中的每一项都被称为“最常见(频繁)项目”或“TFI”。

所述步骤二中，在支持计数阶段，对每个候选项集及其与TFITs的组合的支持度将被一起计算并存储在TFISup数组中，具体如下：

在支持计数阶段，使用了一个大小为2

基于自编码技术的ACT-Apriori算法，包括以下步骤：

步骤1：扫描全局事务数据库D，确定事务数据库D中各项目的支持度计数并以降序排列；

步骤2：确定高频参数NS，从事务数据库D中选定相应的高频项目并从原始数据库中删除；

步骤3：根据选定的高频项目创建频繁项列表TF和频繁项目集列表TI，以一个自编码位向量表示原始数据库中高频项目所处位置，存入交易位SNT，并行成简化形成简化数据库RBD；

步骤4：在Tree数据结构的每个节点中添加一个新的支持计数器列表TFISup，用以跟踪TFIs；

上述步骤3、步骤4中，步骤3为步骤4的基础，步骤3是将整个数据库通过所提出的NS参数、TF列表、TI列表进行简化得到简化数据库RBD；步骤4是在此简化的基础上对Tree数据结构进行优化；

Tree数据结构是关联规则算法的基本结构，如图2所示，由一个根节点、5个二级根节点、10个三级根节点、9个四级根节点及1个子节点由上而下组成，每一级根节点代表进行了一次迭代，每级根节点的数量代表了参与每次迭代的事务的数量。

步骤4中的Tree结构与步骤3中的简化数据库RBD有关，通过NS参数、TF列表、TI列表进行简化得到简化数据库RBD参与迭代，如图3所示。与原始数据库D如图2所示参与迭代，其Tree结构因为NS参数的设定减少了大量的根节点，从而代表着与不做任何优化的原始数据库D相比，简化数据库RBD在参与迭代时会有更快的迭代速度，更小的计算量。

步骤5：设定最小支持度阈值MinSup；

步骤6：将频繁项目集列表TI中的所有项目TFITs在候选项集C(k)中进行动态排序，候选项集C(k)特指在第k次迭代后所生成的候选项集；候选项集C泛指所有生成的候选项集。

如果：C.TFISup[k]

C.TFISup[k]指迭代k次后，候选项集C的支持度计数。

步骤7：完成第k遍后，继续迭代k+1,k+2,...,k+i，其中：i＝1,2,3,..,N，直至不再满足条件C.TFISup[k+i]>MinSup为止；

k指的迭代次数，i指的在k次迭代之后的迭代次数，N代指最后一次迭代数为第N次。本发明中出现k只是为了更好的说明本算法在频繁项集生成阶段的具体步骤，所以以第k次迭代作为例子，可以选择第2次迭代、第5次、第9次..第k次作为特例说明。

步骤8：全部迭代完成后，即得到全局频繁项集L，根据传统的Apriori算法生成关联规则，并将关联规则映射回原数据项。

根据传统的Apriori算法生成关联规则，具体如下：

关联规则算法分为两大部分：第一为频繁项集生成，第二为关联规则生成。本发明主要介绍了对频繁项集生成阶段在时间复杂度与空间复杂度上的优化与改进，在关联规则生成部分仍使用最原始的Apriori算法生成关联规则；关联规则的生成通过matlab中的apriori-generation函数形成，此处可以理解为数据挖掘领域通用的方法。

关联规则具体为：发现隐藏在数据集中各个事务之间的关联关系，关联规则是形如X→Y的蕴涵式，表示通过X可以推导得到Y，下面以一个最简单的例子说明：

例:小明有A、B、C这3种不同的水果，其一次会拿2个水果当晚餐，假如经过100次观测，小明拿到A水果后再拿B水果的次数为70次，拿到A水果再拿C水果的次数为30次，则此时出现两个候选项集{A,B}、{A,C}，为了确定在统计意义上A、B、C之间的关系，设定最小支持度阈值为50次，超过该次数则认为在前者发生的条件下后者必定发生。故候选项集{A,B}超过了最小支持度阈值，即为频繁项集，候选项集{A,C}为非频繁项集，进行删除。最后可生成关联规则A→B，代表在A事件发生的条件下大概率会发生B事件。

将关联规则映射回原数据项指的是：将本发明的算法应用在数据库中，以具体的数据形成频繁项集，将具体的数据代入形成关联规则即映射回原数据项。

本发明一种基于自编码技术的ACT-Apriori算法，技术效果如下：

1)本发明所提供的一种基于自编码技术的关联规则算法—ACT-Apriori，解决了传统的Apriori算法和FP-Tree算法需要两次扫描全局数据库增加了计算负担，当数据库较大时，容易产生组合爆炸的问题。相较于现有全新的关联规则算法，其计算时间大幅度缩短，内存占有率较大程度降低，在时间复杂度和空间复杂度上有明显优化。

2)与现有的关联规则算法相比，本发明算法的显著优点为：算法减少对数据库的扫描次数，在数据预处理阶段极大程度降低了数据维度，减少了内存的占用程度，缩短了生成候选项集的时间，提高了算法的运行效率。

3)本发明将全新的Apriori算法应用在大型公开数据库中，结果显示该算法分别在时间复杂度和空间复杂度上均优于传统的关联规则算法Apriori和现有全新的关联规则算法FP-Growth、FP-Network，解决了现有算法模型建立更新困难，需要双向扫描遍历数据库的问题。

附图说明

图1为TFISup示例图。

图2为原始Apriori算法数据结构图。

图3为ACT-Apriori算法数据结构图。

图4为ACT-Apriori算法流程图。

具体实施方式

基于自编码技术的关联规则算法—ACT-Apriori，首先对事务数据库D进行预处理，计算事务数据库D中各项目的支持度计数以降序排列。其次设定项目的高频参数NS，将选定的高频项目从事务数据库D中的每个事务剔除并用自编码的位向量SNT将其代替进而创建简化数据库RBD。将简化后的数据全部读入内存，在频繁项集连接、剪枝生成候选项集的过程中，对生成候选项集的过程加以改进。在生成候选项集的过程中，无需扫描全局数据库，在Tree数据结构的每一个节点以一个自编码数组TFISup作为每个节点的支持度计数列表，通过排列组合的方式直接生成候选频繁项集并快速根据最小支持度阈值生成频繁项集。

(一)、Apriori算法瓶颈分析：

关联规则Apriori经典算法采用迭代搜索数据库的方式产生频繁项集，为探索各事务之间的内在起到了很大的作用，是数据挖掘研究的一个重要的分支。但是，随着研究数据的增大，对算法性能的要求越来越高，Apriori算法的缺陷也逐渐暴漏出来。

Apriori算法存在以下两个影响性能的瓶颈：

(1)多次扫描数据库，产生巨大的I/O负载：首先，在第k次循环中，连接产生的候选k-项集中，每一个项的(k-1)项子集都需要扫描前一次产生的频繁(k-1)项集来判断该项是否为频繁项集。其次，候选项集中的每一个元素都需要扫描数据库计算支持度，从而确定是否满足最小支持度，从而确定频繁项集。如果一个候选项集包括N条元素，那么至少要对数据库扫描N次，必然产生巨大的I/O负载。

(2)产生庞大的候选项集：由于频繁(k-1)项集在连接产生候选k-项集的过程中数据是呈指数增长的，如此大的候选项集的数量，无论对算法的时间还是空间都是极大的挑战。(二)、Apriori算法改进：

1：数据预处理阶段：

数据预处理阶段最重要的步骤即为：确定高频参数NS，并将其从原始数据库中删除用一个自编码位向量代替存入交易位SNT。为更好的阐述本算法数据预处理阶段的执行过程，下面以示例1进行更详细的说明：

示例1：

若给定事务数据库如表1所示，

表1原始事务数据库

该事务数据库中共有10条事务。首先计算整个事务数据库中各项目的支持度计数如表2所示。

表2各项目支持度计数

取NS＝2，则A、C是具有较高支持度阈值的项目(即高频项目)，则项目集列表TF＝{A,C}。由定义知项目集列表TI为TF中所有可能的排列组合，因此可以从TF中创建2

表3简化数据库RBD

表4参量表

例如：TID1中，SNT＝2

2：频繁项集生成阶段：

ACT-Apriori使用下面的一些引理来寻找所有的频繁项集。

引理1：如果事务t包含项集A和项集B，则t包含项集{A+B}。其中，{A+B}表示项集A和B的构成。

通过使用引理1，在保证候选项集c包含在事务T中并且事务T还包含TI[i]之后，可以得出项目集{c+TI[i]}也将包含在事务T中的结论。ACT-Apriori使用该引理来找到所有的频繁项目集。

频繁项集生成阶段的第一部分是支持计数部分，第二部分是剪枝部分。在这一部分中，使用了一个大小为2

首先显示在该遍计算中的频繁项集，然后从C[k]中修剪非频繁项集，从而生成L[k]。在显示频繁项集阶段，对于每个项集c，我们必须考虑整个数组c.TFISup。对于该数组的每个条目，如果c.TFISup[i]>MinSup，算法将在其输出中显示项集{c+TI[i]}，因为它是频繁的。

ACT-Apriori算法中候选项集的剪枝步骤类似于经典的Apriori算法。只是，对于候选项集c，修剪是通过考虑c.TFISup[0]而不是c.TFISup数组的全部来执行的。因此，如果c.TFISup[0]

为更好的阐述本算法的第二阶段的执行过程，下面以示例2进行更详细的说明：

示例2：

该示例通过使用示例1中表示的RDB、TF和TI来显示频繁项集生成阶段的操作。在本例中，支持阈值设置为50％。在第一遍中，ACT-Apriori算法创建候选项集c[1]＝{B}、{D}、{E}、{F}、{G}、{H}。然后，通过从数据预处理阶段计算的交易位(SNT)，该算法计算每个候选项目集的支持度以及它与TI列表的组合的支持度。例如，对于候选项集{B}，计算{B}，{B，A}，{B，C}和{B，A，C}的支持计数，其中TI＝{{}，{A}，{C}，{A，C}}。表a1～表a6显示了k＝1时的结果。将保留支持度大于最小支持度阈值的所有项目集。因此，在第1遍结束时保留的项目集是:{B}、{B，A}、{B，C}、{F}、{F，A}、{F，C}、{F，A，C}、{G}、{G，A}。

表a1候选频繁1项集生成表(c[1]＝{B})

表a2候选频繁1项集生成表(c[1]＝{D})

表a3候选频繁1项集生成表(c[1]＝{E})

表a4候选频繁1项集生成表(c[1]＝{F})

表a5候选频繁1项集生成表(c[1]＝{G})

表a6候选频繁1项集生成表(c[1]＝{H})

完成ACT-Apriori算法的第一遍后，L[1]将包含{B}、{F}和{G}。在ACT-Apriori算法的第二遍中，创建了c[2]。在示例2中，c[2]＝{B，F}，{B，G}，{F，G}，然后执行支持计数阶段，并生成候选频繁项目，如表b1、表b2、表b3所示。在第2遍结束时显示的项目集包括:{B，F}、{B，F，A}、{B，G}、{B，G，A}、{F，G}、{F，G，A}。而L[2]＝{B，F}，{B，G}，{F，G}。在第3遍中，创建了c[3]＝{B，F，G}。并且在支持计数阶段之后，将生成表c中的数据。本次保留的项集为{B，F，G}，{B，F，G，A}，L[3]＝{B，F，G}。由于L[4]＝{B，F，G，A}已包含高频项目A，且L[4]＝{B，F，G，C}支持度为达到要求，则全局频繁项集为L[4]＝{B，F，G，A}。

表b1候选频繁2项集生成表(c[2]＝{B,F})

表b2候选频繁2项集生成表(c[2]＝{B,G})

表b3候选频繁2项集生成表(c[2]＝{F,G})

表c全局频繁项集生成表

在ACT-Apriori算法的第二阶段，用RDB代替原始数据库，把TFIs从其余项目中分离出来，将对候选项生成和支持计数阶段产生影响。在候选项生成中，由于TFIs不再包含在数据库中，它们不会被添加到候选项集。相反，在Tree数据结构的每个节点中添加了一个新的支持计数器列表，称为TFISup，以跟踪TFIs，并且与原始Apriori相比不会丢失任何结果。每个TFISup实体代表相关项集和其中一个TFIs的组合，其中TFIT是TFI的所有可能组合。

图1以一个最简单的实例表明了TFISup数组的使用。在支持计数阶段，对每个候选项集及其与TFITs的组合的支持将被一起计算并存储在TFISup数组中。在支持计数阶段，不需要为扫描数据库的每个部分确定TFIs的存在，TFIs在准备阶段只计算一次，这将在数据库扫描中节省大量的处理时间。

3：性能分析：

①、内存占用和运行速度分析：

在新的数据结构中，一些项目集(即一些tree节点)被忽略，因此导致与原始tree结构相比具有更小的数据结构。但是，如前所述，每个节点必须有一个22数组，因此，tree的每个节点都有一个大小为4的数组。

如图2所示，需要27个tree节点用于频繁项集挖掘。在图3中，所需的tree节点等于7。这种新的数据结构比原来的数据结构少20个tree节点。然而，新数据结构中的每个节点都需要一个大小为4的数组来保存频率，这导致7×3＝21个额外的条目，对于本例，ACT-Apriori为新的tree数据结构使用了21个额外的整数来完成支持计数，并且通过使用少20个节点来节省内存。

为更好的验证所提出的新算法在内存占用的优越性，现将Apriori算法和ACT-Apriori算法应用于大型公开数据库中，测试设备硬件条件为intel CORE i7 8

表5原始Apriori和ACT-Apriori在同一数据集不同支持度下内存占用比较

表6原始Apriori和ACT-Apriori在同一数据集不同支持度下运行时间比较

表5、表6中，0代表原始的Apriori算法，分别在不同最小支持度和不同高频参数下测试内存的占用量。通过实验证明，当NS＝6、NS＝7时，ACT-Apriori算法的内存占用量明显小于原始Apriori算法，当NS＝5、NS＝6时，ACT-Apriori算法的运算速度明显快于原始Apriori算法。

②、横向对比分析：

在特定的数据集中，NS参数对各种最小支持值有一致的影响，NS参数不仅是算法运行时间的重要因素，而且对内存使用量也有很大影响。通过实验数据可以看出NS参数在运行时间和内存使用中对数据集的影响大致相似，即当NS参数越大时，算法所需要的内存占用量和运行时间就越少。算法内存使用的减少意味着tree节点数量的减少，从而减少了查找频繁项集所需的处理时间。因此，通过适当提高NS参数，可以减少内存占用量和运行时间。

通过实验数据可得当NS＝6或7时，算法占用内存较少，当NS＝5或6时，算法运行时间较短。因此选定NS＝6作为最佳参数变量分别与原始Apriori算法和目前应用较为广泛的FP-growth算法和FP-Network算法一同应用于同一数据库中进行对比分析。

表7内存占用和运行时间横向对比分析

由表7可知，在最小支持度minsup>0.45的情况下，ACT-Apriori算法在内存占用量和运行时间上明显优于Apriori算法，相较于FP-growth算法和FP-Network算法也有一定的优势；在最小支持度minsup<0.45的情况下，ACT-Apriori算法的内存占有量有一定缩减，在算法的运行时间比Apriori算法缩减了6-7倍，比FP-growth算法缩减了3-4倍，但与FP-Network算法相比，虽有一定缩减但效果不太显著。

在大多数数据库中，有些项目比其他项目出现得更频繁。在本发明中，提出了一种新的优化方法，它可以应用于所有基于Apriori的频繁项集挖掘中。

上述优化是在基于tree数据结构实现的。在算法的数据预处理阶段，从数据库中选择高频项目并进行编码，在频繁项集挖掘阶段利用编码信息进行挖掘。实验结果表明，在真实数据集上挖掘频繁项集的执行时间有了很大的提高，该算法的执行不需要额外的内存分配，而且减少了执行所需的内存，对于快速挖掘数据中的关联规则有着十分重要的意义。