基于改进Apriori算法的关联规则挖掘系统

摘要

本发明提供一种基于改进Apriori算法的关联规则挖掘系统，包括数据预处理模块、连接模块、剪枝模块、频繁项统计模块和关联规则生成模块；所述数据预处理模块与数据库交互，负责将数据库中的文本数据转换为可进行位运算的整型格式；所述连接模块、剪枝模块和频繁项统计模块共同构成Apriori算法的具体实现，负责频繁项集的生成；所述关联规则生成模块与频繁项统计模块交互，负责将频繁项统计模块生成的频繁项转化为具体的关联规则。本发明采用了基于位运算的频繁项统计方法，简化了剪枝操作复杂度并减少了数据库扫描的次数，从而提高了关联规则挖掘效率，降低了系统资源的消耗，可以为企业、商家提供更为高效、方便的关联规则挖掘业务，具有较大实用价值。

说明书

技术领域

本发涉及一套基于改进Apriori算法的关联规则挖掘系统，是一种基于位 运算进行频繁项统计的关联规则挖掘系统，该系统在实现Apriori算法的过程 中，减少了剪枝操作中候选项集子集的检验数量并在由候选项集生成频繁项集 时减少了数据库扫描次数，属于数据挖掘领域。

背景技术

随着“啤酒、尿布”案例在营销界的成功运用，人们对不断收集的数据中 关联规则的挖掘越来越感兴趣，关联规则的应用范围也逐渐从超市营销扩展到 更多的领域。当前关联规则挖掘的算法主要有Apriori和FP树。FP树因内存消 耗大、实现复杂、系统要求高等限制，未能在实际使用中得到广泛应用，目前 多作教学案例或研究课题用。Apriori算法是关联规则挖掘过程中实际采用最多 的方法，但是该算法仍存在数据库扫描次数多、候选集大、挖掘效率低等问题。

发明内容

本发明的目的在于克服现有技术中存在的不足，提供一种基于改进Apriori 算法的关联规则挖掘系统，采用了基于位运算的频繁项统计方法，简化了剪枝 操作复杂度并减少了数据库扫描的次数，从而提高了关联规则挖掘效率，降低 了系统资源的消耗，可以为企业、商家提供更为高效、方便的关联规则挖掘业 务，具有较大实用价值。本发明采用的技术方案是：

本发明提出的基于改进Apriori算法的关联规则挖掘系统，包括数据预处 理模块、连接模块、剪枝模块、频繁项统计模块和关联规则生成模块；所述数 据预处理模块与数据库交互，负责将数据库中的文本数据转换为可进行位运算 的整型格式；所述连接模块、剪枝模块和频繁项统计模块共同构成Apriori算 法的具体实现，负责频繁项集的生成；所述关联规则生成模块与频繁项统计模 块交互，负责将频繁项统计模块生成的频繁项转化为具体的关联规则。

本发明的优点在于：基于位运算进行频繁项统计，降低了比较内容复杂度， 提高了比较效率；连接和剪枝操作中，只针对K项集中包含新加入两项的K-1 项子集进行Apriori性质验证，缩小了候选项集子集的Apriori性质验证范围， 减少了运算量；频繁项统计中是对每一条记录统计各候选集中项集的频数，而 不是传统实现中每一个项集扫描一次数据库的方法。总体来说，本发明降低了 比较内容的复杂度、减少了数据库扫描次数，从而提高了关联规则的挖掘效率。

附图说明

图1为本发明的结构框图。

图2为本发明的工作流程图。

具体实施方式

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

本发明提出的基于改进Apriori算法的关联规则挖掘系统，包括数据预处 理模块、连接模块、剪枝模块、频繁项统计模块和关联规则生成模块；所述数 据预处理模块与数据库交互，负责将数据库中的文本数据转换为可进行位运算 的整型格式；所述连接模块、剪枝模块和频繁项统计模块共同构成Apriori算 法的具体实现，负责频繁项集的生成；所述关联规则生成模块与频繁项统计模 块交互，负责将频繁项统计模块生成的频繁项转化为具体的关联规则。

具体地，所述数据预处理模块首先扫描数据库，将数据库中所有的项进行 编号，令所有项组成的集合为I＝{i₁,i₂,i₃…i_n}，则用n个二进制位表示各项，二 进制数从高到低位依次代表i₁，i₂，……i_n，每个二进制位0代表该项没有出现， 1代表出现；然后将数据库中的数据记录TID＝{i_k,k≥1∩k≤n}转换为对应的二进 制整型，重新写入数据库；并且，该模块第一次扫描数据库式统计了各项ik出 现的频数，将其中频数超过最小支持度s的项的集合称作频繁1项集L1。

举例来说，假设数据库中有4个项，分别用于记录姓名，地址，电话，邮 编；如果一条数据记录中，只有姓名和地址有数据，则这条数据记录转换为二 进制整型为1100。

所述连接模块用来由频繁k-1项集L_k-1生成频繁k项集L_k；设I_k1和I_k2是L_k-1中的项集，它们均按照约定用二进制数表示：相应项编号对应的二进制位值为1， 其它位为0，对I_k1和I_k2执行异或操作后所得结果，左起前两个为1的二进制位 u和v即为要连接的对象，设从左到右对应二进制从高位到低位；接下来从I_k1和I_k2中查找v位为0的项，并将该位置1，v位以下各位置0即完成I_k1和I_k2的连接操作，将其加入候选集C_k；对L_k-1中的任意两个项集执行类似操作。

所述剪枝模块与所述连接模块相交互，根据Apriori性质，频繁项集的任 何子集一定是频繁项集，将候选集C_k中，k-1项子集不在L_k-1中的项剪掉；对任 意C_k中的项集I_k1，其对应二进制数如0……1……0……1……1……0，除最右边 两个1以外，从左到右依次将位为1的位置0，然后与L_k-1中的每一项执行异或 操作，如果扫描完整个L_k-1，没有出现结果为0的项，则将I_k1从C_k中剪去；

所述频繁项统计模块与数据库相交互，并和所述连接模块及所述剪枝模块 共同构成Apriori算法的主体；频繁项统计模块主要负责从数据库中依次读入 每条记录TID，然后与C_k中的每一项I_k1，执行如下操作若结果 为0则对I_k1的频数统计加1；最后从C_k中选出频数超过最小支持度s的项集组 成L_k；

所述关联规则生成模块主要用来根据所述频繁项统计模块的结果生成相应 的关联规则,对L_k中的每一项I_k与L_k-1中的每一项I_k-1，执行如下操作 若结果不为0，设I_k值为0……1……0……1……1……0且对应 位为1的位置分别为k1，k2，……kn，则如果I_k最低位1比I_k-1最低位1位低， 则生成的关联规则为i_k1,i_k2,…i_kn-2,否则生成关联规则 i_k1,i_k2,…i_kn-2,置信度为I_k的频数除以I_k-1的频数，输出置信度大于最小 置信度的规则。

如图1所示，本系统分数据预处理模块、连接模块、剪枝模块、频繁项统 计模块和关联规则模块。其中所述数据预处理模块安装在操作系统之上，与 MySQL数据库直接交互。所述关联规则生成模块与具体应用程序或命令行界面交 互，输出具体关联规则。

具体地，所述数据预处理模块安装在CentOS6.5操作系统之上，通过Jdbc 与MySQL数据库连接。其中维护了二维表(编号，项)，为具体项在二进制数中 的位编号。二进制数采用Java中的int数组表示，且数组中按数组编号从小到 大对应二进制位数中从高到低位，若最后一个数组元素整数位数没有用完，补0。 MySQL中的原始数据为记录，每个记录包含若干项，每一项内容可以为任何字符 串内容，以空白符分隔。所述关联规则生成模块为Java接口，通过Java静态 函数实现，可以在任何Java程序中调用，生成的关联规则保存在List中， System.out输出。输出内容中编号会转换为具体的项的名称。具体系统工作流 程如图2所示。

本发明主要对传统Apriori算法中的连接、剪枝和频繁项统计步骤进行了 改进。数据预处理过程中将文本内容或其他格式的内容统一转化为二进制数， 整个系统在进行频繁项挖掘及关联规则生成过程中的运算都采用位运算，既降 低了内存占用率，又提高了执行效率；在连接过程中用二进制位编号代替了传 统Apriori实现过程中的排序操作；在剪枝过程中合理利用了Apriori性质和 由k-1项集产生k项集过程中数据生成的特点，只对候选项集中包含新加入两 项的k-1项子集进行检验，极大地减少了候选项集和k-1项子集的数量；在频 繁项统计过程中，采用了针对记录扫描候选项集的方式，从而减少数据库扫描 的次数。总体来说，本发明降低了关联规则挖掘过程中的内存占用率、提高了 挖掘过程中的运算速率并减少了数据库扫描次数，为企业、用户带来更高效、 方便的关联规则挖掘服务。