一种基于矩阵的关联规则算法的研究与应用-论文.pdf

《一种基于矩阵的关联规则算法的研究与应用-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第35卷第4期通化师范学院学报(自然科学)Vo1．35№42014年8月JOURNALOFTONGHUANORMALUNIVERSITYAug．2014一种基于矩阵的关联规则算法的研究与应用黄毅杰，张艺雪(1．漳州职业技术学院计算机工程系，福建漳州363000；2．漳州卫生职业学院信息技术部，福建漳州363000)摘要：对Apriori算法在数据库扫描和产生的候选项集的问题进行分析，提出一种基于矩阵的关联规则算法，该算法将事务数据库转换为向量矩阵，并通过向量矩阵的运算得到较的候选项集，提高算法的运行效率．该算法在高校教学评价的应用上取得良好

2、效果．关键词：Apriori；关联规则；向量矩阵；最小支持度；可信度中图分类号：TP301．6文献标志码：A文章编号：1008—7974(2014)04—0001—04关联规则是数据挖掘技术的主要研究方向之关联规则的支持度和可信度分别体现出了规则一．1994年，Agrawal等人提出了关联规则挖掘的经发生的频度和强度．典算法Apriori¨j．Apriori算法利用层次循环顺序搜在事务数据库D中找出同时满足最小可信度索的方法来挖掘频繁项集，但该算法需要多次扫描(rain—sup)和最小可信度(rain—conf)是关联分析的数据库并产生了大

3、量的候选项集]．最终目的J．本文提出了一种基于矩阵的关联规则算法，通2Apriori算法思想过向量矩阵来表示事务数据库，减少了扫描数据库Apriori算法的实现可分为两步：的次数，通过矩阵的运算快速生成k一项集．第一步是发现事务数据库D中的所有支持度1关联规则基本概念大于最小支持度的项集，这个工作是关联规则的关假设项的集合为，={i，，：，⋯，i}，在，中包含键所在，具有较大的计算量，也是衡量算法性能的关了m个不同的数据项．在给定的数据库D中，所有的键．事务都包含在D中，表示D中的每条事务，是，中第二步是根据第一步识别出的频繁项集提取出项的

4、集合，使得每条事务有唯一的TID标关联规则j．识．关联规则如同蕴涵式，其中，Ac，，BcI，Apriori算法的流程图如图1所示：且AnB=．设A是，的子集，A的支持度s(A)是指D中出现的概率，如果S(A)≥最小支持度(rain—sup)，则称A为频繁项集．蕴涵式A曰具有支持度5(／Ij曰)，其支持度是指A和B在D中同时发生的概率，即S(B)：P(AUB)J．蕴涵式A曰在D中的可信度C(A~B)是指D中支持A同时也支持B的记录数与支持A的记录数之比，也可理解为D中包含A的同时包含B的概率，即(：)：⋯P一(A旦：P(BI)．图1Aprio

5、ri算法的流程图收稿日期：2014—06—09作者简介：黄毅杰(1979一)，男，福建漳州人，硕士，讲师从Apfiofi算法的流程图中可以看出，Apfiofi算对各个项集进行支持度计数，每个项集都满足法需要多次反复扫描数据库，产生较大的I／O消耗，最小支持度，生成矩阵D，如表2所示．其中￡为{在k=2的时候会产生大量的候选项集，特别是在，I：2，，1：3，，3：4，厶：2，}挖掘较大型的数据库关联规则时，使得效率降低．通过D乘以D的转置矩阵得到S，其中为{3基于矩阵的关联规则算法，2，3：3，，4：2，，3，4：2算法的改进思想是通过把事务

6、数据库转换为向f00lO量矩阵减少扫描数据库次数，在K=2时，采用转化i0032S=DlX(D1)=后的矩阵乘以其转置矩阵的方法得到较少的候选项f00O2l00集，提高效率．算法步骤如下：0O(1)转换矩阵：扫描⋯遍数据库，把事务数据库0000j9转换为向量矩阵4⋯，矩阵的行代表D中的每条0O】lD2=事务，矩阵的列代表D中数据项，其中，O001()000：f1∈．106诺死．通过￡连接得到为；，1厶，4，由可知不会(2)生成频繁1一项目集：按顺序求各列向量的产生频繁4一项集，算法停止．数量积，在结果中统计l的数量，这个数量值即项目5算法性

7、能分析一匣富毫，的支持度计数suppo~一GOUnt(1j)，如果suppo~～本文提出的算法把事务数据舌库j掷转伯换的为向∞馈}；矩；∞0count()／n>最小支持度(min—sup)，则，，项的组阵，不再扫描原始的事务数据库，向量矩阵只存储0合为频繁1一项目集，否则，I为非频繁1一项目集，和1数据，大大减少了占用的空间，特别是在大数据删除该项所在的列，按照支持度计数由小到大排序，集上更能体现其运算效率．图2为本文算法jApfi．生成矩阵D．．o“算法在测试事务数据库．在最小支持度设为2％，(3)生成频繁2一项目集：通过D乘以D的转事务

8、从500到8500的增加过程中的算法的执行时置矩阵得到S，如果S矩阵右上角的数据S>间比较结果．从图中可以看出，随着事务的增加，本min—sup，则Js项的组合为频繁2一项目集，