一种基于邻接比特压缩表的频繁闭项集挖掘算法

摘要

发明公开了一种基于邻接比特压缩表的频繁闭项集挖掘算法，定义使原始事务集高度压缩的，用于频繁闭项集挖掘的数据结构——邻接比特压缩表，通过该数据结构一方面将每个项或项集所包含的交易集压缩为比特数组，并通过邻接比特的位置标识去剔除传统比特表中的0比特，使交易集高度压缩；另一方面，建立项索引表，之后将项索引压缩到邻接比特压缩表中，当原始数据集中项的维度较高，或项标识较长时，压缩效果明显；其次，通过采用运算栈与检索栈的非递归运算方法，可以降低运算过程与闭合检索的空间占用；最后，通过邻接比特压缩表之间的与运算以及或运算代替项集求交或并运算，同时采用项集预处理、回溯校验的剪枝策略，来加快整体运算过程。

说明书

技术领域

本发明涉及数据挖掘技术领域，具体为一种基于邻接比特压缩表的频繁闭项集挖掘算法。

背景技术

频繁项集(Frequent Items,FI)是若干频繁同时出现事物的集合，最早是在超市研究货物摆放规律以及客户购买商品组合时提出的概念。随着信息技术的迅猛发展以及大数据时代的到来，使得在许多场景下对事物关联关系挖掘的需求日益强烈，直接促进了频繁项集挖掘算法的研究与应用。除客户营销方面的应用外，金融风险防控、旅游路线规划、机械异常故障预警、网络日志分析等，都有实际应用。然而，FI存在大量冗余信息，于是有学者进一步提出了频繁闭项集(FCI:Frequent Closed Items)的概念，FCI可以在不损失任何信息、完整地保持事物之间关联关系的前提下，剔除所有频繁项集的冗余信息，进而解决上述问题。频繁项集或频繁闭项集挖掘算法输入的基础数据集有三种结构：水平数据集、前缀树、垂直数据集。

基于水平数据集挖掘频繁项是最早被提出的一种策略，其核心思想是通过项集的两两合并来生成候选集，之后通过候选集与原始数据集的比对来计算其支持度，进而得知其是否为频繁项。由于每个候选集都需要与原始数据集进行比对，所以原始数据集需要常驻内存，并被频繁访问。当原始数据集较大时，算法的空间效率和时间效率都较差。

基于前缀树策略的基本原理是首先扫描一遍原始数据集记录各项的支持度，之后再扫描一遍数据集，剔除非频繁项并降序排序，再之后根据排序后队列中前后项之间的位置关系构建前缀树，最后通过该前缀树可以高效地生成频繁项集。该策略的问题在于，当结点的父节点较多时，原始数据集的压缩效果较差，同时该树状结构需常驻内存，当数据规模较大时，内存占用依旧很高。

基于垂直数据集策略的基本原理是首先扫描一遍数据集，形成主索引为项ID，其内容是该项所包含交易集的一种垂直数据结构。之后基于该数据结构，由频繁K项集可快速生成频繁K+1项集。由于基于垂直数据集的策略只需扫描一遍数据集，频繁K项集运算结束后可释放其空间，故时间和空间效率可进一步提升。

频繁项集包含冗余信息，如项集{A,B}的支持度为10，项集{A,B,C}的支持度也是10，则{A,B}完全可由{A,B,C}替代。所以有学者提出了基于频发闭项集的挖掘算法来解决信息冗余的问题。由于频繁闭项集在挖掘过程中需要对待输出项集进行闭合校验，所以频繁闭项集挖掘算法又可基于是否采用哈希表校验分为两类。采用哈希表的算法需要在输出过程中首先对待输出项集进行哈希运算，之后通过哈希表快速检索其是否闭合，如闭合则将其放入哈希表中并输出，否则将其丢弃。不采用哈希表的算法在运行过程中可判断项集是否闭合。采用哈希表的算法属于由空间换时间的策略，所以普遍时间效率占优，而不使用哈希表校验的算法普遍空间效率占优。

对于空间效率优化的研究，从水平数据集到前缀树再到垂直数据集，从数据结构的角度出发使空间效率都有所提升。而对于数据结构中需要放入内存的每个元素单元，有学者提出了传统比特表的数据结构——BitTable，用位表来代替项所归属的事务标识，使初始垂直数据集有了大幅的压缩，同时用按位与运算代替之前的求交集运算，效率也极大的提升。但各项的位表需要按位对齐，导致该数据结构中存在大量的0。后来有学者进一步提出了Dynamic Bit-Vector数据结构，它剔除了BitTable首尾的0，使初始数据进一步压缩。但当BitTable中间位置的存在大量的0时，Dynamic Bit-Vector依旧要占用大量的内存。

发明内容

针对上述问题，本发明的目的在于针对现有技术中的挖掘算法空间效率不高的现状提供一种基于邻接比特压缩表的频繁闭项集挖掘算法，能够降低循环长度，加快运算效率，大幅提升运算的时间效率。技术方案如下：

一种基于邻接比特压缩表的频繁闭项集挖掘算法，包括如下步骤：

步骤1)定义基础数据结构，包括四种数据结构：原始数据集结构、邻接比特压缩表结构、初始运算数组结构，以及运算与检索栈结构；

步骤2)数据初始化：首先将原始数据集DataSet转换成垂直数据集并压缩到序列Inite″

步骤3)采用频繁闭项集挖掘主算法进行运算：运算指针P依次调用序列Inite

步骤4)确定检索栈Check

进一步的，所述步骤1具体包括：

步骤1.1)定义原始数据集结构：

原始数据集为包含若干项id交易序列，数学表达式如下：

其中，Y是包含所有id信息的全集，X

步骤1.2)定义邻接比特压缩表结构：

邻接比特压缩表为包含m个元素的序列，每个元素包含位置信息与值信息，数学表达式如下：

其中，C

步骤1.3)定义运算数组结构：

按照垂直数据集的结构将原始数据集进行调整与压缩，形成初始数据集；初始数据集包含三个部分，支持度、用邻接比特表压缩表示的项集合、用邻接比特表表示的交易集合，数学表达式如下：

其中，Inite

步骤1.4)定义运算与检索栈结构：

在运算与检索的过程中用到的栈结构，每个栈元素包括两个部分，位置标识和邻接比特压缩表结构数据，数学表达式如下：

其中，Stuck是一个先进后出的栈结构，栈内元素的loc表示当前运算元素在Inite

更进一步的，所述步骤2)中算法数据初始化过程如下：

步骤2.1)从原始数据集DataSet至序列Inite″

其中，j表示项索引id

步骤2.2)从序列Inite″

步骤2.3)从序列Inite′

trade

若

当B的交易集包含A的交易集，且B.sup＝A.sup，则B的交易集与A的交易集完全相等，此时删除B结点。

id

A.id

C.id

若A.id

若A.id

若A.id

在id

更进一步的，所述步骤3)中主算法运算过程如下：

步骤3.1)入运算栈Cal

若运算栈Cal

若运算栈Cal

若TEMP.sup＝Cal

若TEMP.sup

若TEMP.sup≥minsup则将TEMP在检索栈Check

运算栈Cal

Cal

TEMP.id

TEMP.trade

其中，count()表示trade

其中trade

A.trade

C.trade

C.trade

C.trade

A.trade

临时结点TEMP闭合检验运算：

若

步骤3.2)出运算栈Cal

步骤3.3)运算终止：当序列Inite

更进一步的，所述检索栈Check

本发明的有益效果是：

1)本发明邻接比特压缩表可用于交易集的压缩存储，通过邻接比特压缩表中的位置标识可以剔除传统比特表中的0比特，使数据高度压缩；另一方面由于数组长度变短，进而使运算时的循环长度变短，加快运算效率。

2)本发明邻接比特压缩表可用于项集的压缩存储，尤其当项标识较长(如身份ID、商品ID、地点名称等)时，运算空间占用将显著的减少；同时用邻接比特压缩表间的按位“或”运算来代替项标识间的并集运算，大幅提升运算的时间效率。

3)本发明设计出两种栈数据结构，其中运算栈作为基础运算空间执行主算法，检索栈作为检索空间执行待输出项集的闭合校验。同时采用基于双栈的非递归运算方法，可使运算时最大理论空间占用为O(2N+M)，其中N为基础运算表长度，M为检索表长度。

附图说明

图1为本发明的基于邻接比特压缩表的频繁闭项集挖掘算法流程图。

图2为本发明的原始数据集压缩至初始数据集的过程图。

图3为本发明的主算法运算逻辑，以及运算栈的演化过程。

图4为本发明的检索栈演化过程。

具体实施方式

下面结合附图和具体实施例对本发明做进一步详细说明。

本发明为一种基于邻接比特压缩表的频繁闭项集挖掘算法，首先，定义了一种使原始事务集高度压缩的，用于频繁闭项集挖掘的数据结构——邻接比特压缩表，通过该数据结构一方面可以将每个项或项集所包含的交易集压缩为比特数组，并通过邻接比特的位置标识去剔除传统比特表中的0比特，使交易集高度压缩；另一方面，建立项索引表，之后将项索引压缩到邻接比特压缩表中，当原始数据集中项的维度较高，或项标识较长时，压缩效果明显。其次，基于邻接比特压缩表，提出一种运算空间效率极佳的频繁闭项集挖掘算法，通过采用运算栈与检索栈的非递归运算方法，可以降低运算过程与闭合检索的空间占用。最后，通过邻接比特压缩表之间的与运算以及或运算代替项集求交或并运算，同时采用项集预处理、回溯校验的剪枝策略，来加快整体运算过程。

参见图1，本发明所述的一种基于邻接比特压缩表的频繁闭项集挖掘算法，包括以下步骤：

步骤1)定义基础数据结构，算法相关数据结构包括：原始数据集结构、邻接比特压缩表结构、初始运算数组机构、运算与检索栈结构等四种数据结构，运算开始前需完成对上述数据结构的定义。

步骤1.1)定义原始数据集：原始数据集为包含若干项id交易序列，例如商品订单序列、仓储入库序列、机器故障序列等，数学表达式如下：

其中，Y是包含所有id信息的全集，X

步骤1.2)定义邻接比特压缩表：邻接比特压缩表是一个包含n个元素的集合，每个元素包含位置信息与值信息，数学表达式如下：

其中，X

步骤1.3)定义初始数据集：原始数据集在本算法下无法直接进行运算，需按照垂直数据集的结构进行调整与压缩，之后形成初始数据集。初始数据集包含三个部分，支持度、用邻接比特表压缩表示的项集合、用邻接比特表表示的交易集合，数学表达式如下：

其中，Inite

步骤1.4)定义栈数据结构：在运算与检索的过程中都需要用到该栈结构，每个栈元素包括两个部分，位置标识、邻接比特压缩表结构数据，数学表达式如下：

其中Stuck是一个先进后出的栈结构，栈内元素的loc表示当前运算元素在Inite

图2分别展示了原始数据集结构、邻接比特压缩表数据结构、以及初始数据集结构。

步骤2)数据初始化：首先需要将原始数据集DataSet转换成垂直数据集并压缩到Inite″

步骤2.1)DataSet至Inite″

其中，j表示id

步骤2.2)Inite″

步骤2.3)Inite′

trade

若

当B的交易集包含A的交易集，且B.sup＝A.sup，则B的交易集与A的交易集完全相等，此时删除B结点；

id

A.id

C.id

若A.id

若A.id

若A.id

在id

步骤3)频繁闭项集挖掘主算法：运算指针P依次调用Inite

步骤3.1)入Cal

Cal

Cal

TEMP.id

TEMP.trade

其中，count()表示trade

其中trade

A.trade

C trade

C.trade

C.trade

A.trade

TEMP闭合检验运算：

若

步骤3.2)出Cal

步骤3.3)运算终止：当Inite

图3对主算法的运算逻辑进行了详细的展示。

步骤4)Check

步骤4.1)Check

图4对检索栈的形成过程进行了详细的展示。