浅析改进的Apriori关联挖掘算法的实践

1、浅析改进的Apriori关联挖掘算法的实践         这篇浅析改进的Apriori关联挖掘算法的实践的关键词是数据挖掘,Apriori算法,图书馆管理,读者管理,                    摘要：本文介绍了数据挖掘技术在图书馆中的应用，并运用改进的Apriori关联挖掘算法对安徽省图书馆自动化系统中读

2、者流通库进行挖掘，并对挖掘出的结果及其意义进行评价，从而为图书馆读者管理、图书资源的采购提供决策支持。        关键词：数据挖掘 Apriori算法 图书馆管理 读者管理        数据挖掘技术在商业领域内的应用给图书馆带来了很大的启发。图书馆的数据库可以运用数据挖掘技术中的关联规则分析、聚类分析、决策树、时间序列分析等数据挖掘方法，以找出数据库中蕴藏的对于图书馆管理有用的潜在规则，并且通过描述和预测，为图书馆的图书采购、读者

3、服务、馆藏目录设置等管理工作提供决策支持。        关联规则是与多数人想象的挖掘过程中最相近的一种数据挖掘形式，即寻找在同一事件中出现的不同项的相关性。关联规则的研究有助于发现数据库中不同商品间的联系，找出顾客购买行为模式。在图书馆运用关联规则分析可以细分出读者群，根据其借阅情况提供不同的服务，为图书馆的管理决策提供参考。关联规则的核心算法是Apriori算法。        关联规则的基本概念及算法  

4、60;     挖掘流通借阅事务数据库中所有的关联规则的问题可以被划分成如下两个子问题：        找出所有具有最小支持度的项集(即频繁项集)，可用Apriori算法来找出频繁项集。由频繁项集产生强关联规则，对于每一个频繁项集I，找出其中所有的非空子集，然后，对于每一个这样的子集a，如果support(I)与support(a)的比值大于最小置信度，则存在规则a=>(I-a)。      

5、0; (一)关联规则算法        关联规则的挖掘主要是在数据库中找出支持用户指定的最小支持度S和最小置信度C的关联规则，从而指导人们的一些管理决策。目前，关联规则的挖掘方法主要是找出数据库中的频繁项集，然后由频繁项集产生关联规则。        (二)Aprior算法        Apriori算法是一种挖掘布尔关联规则的频繁项集的算法，它

6、主要是利用逐层搜索的迭代方法来寻找数据库中频繁出现的项集。主要步骤是：第一步，产生频繁1-项集L1，扫描数据库D，出现在D中各个数据项的集合就是频繁1-项候选项集C1，并统计出每个数据项出现的次数，次数大于最小支持计数(预先)定义的项的集合就是频繁1-项集L1;第K步，产生频繁K-项集Lk，利用上一步产生的频繁(K-1)-项集Lk-1，与自己连接产生K-项集候选集Ck，扫描数据库事务库，计算Ck中每个成员出现的次数，将小于最小支持度的候选项删除，最后产生频繁K-项集。        算法：Apriori使用根据候选

7、生成的逐层迭代找出频繁项集        输入：流通借阅数据库D;最要支持度阈值minsup        输出：D中的频繁项集L        算法代码：        1)L1一所有频繁项集1-项目集;      &

8、#160; 2)for(k=2;Lk，k+)        3)Ck=apriori_gen(Lk-1，minsupport)        4)for all CCt do        5)Ct=Subset(Ck，T)        6)For all cCt d

9、o        7)c.count+;        8)        9)Lk=cCk|support(c)>=minsup        10)        11)return L=所

10、有的Lk        Apriori算法的第1步找出频繁1-项集的集合L1。在第210步中，Lk-1用于产生候选Ck，以找出Lk。Apriori过程产生候选，第3步使用Apriori性质删除那些具有非频繁子集的候选，第4步扫描数据库，第5步使用subset函数找出事务中的候选的所有子集，第6步和第7步对每个这样的候选累加计数。最后，所有满足最小支持度的候选会形成频繁项集L。        Apriori-gen过程 

11、0;      Apriori-gen过程由Lk-1产生第K次迭代时的候选项集Ck，该过程描述如下：        For each itemset I1Lk-1        For each itemset I2Lk-1        If (I11=I21)(I12=I22(I1K-2=I2K

12、-2)(I1K-1 =I2 K-2)(I1K-I=I2K-1)        Then c=I1，I12，I1K-I，I2K-1);        Ck=Ck U c;        For(c的每个包含k-1个项目的子集s)        If(s不属于Fk-1) &

13、#160;      从Ck中删除C;                Return(Ck);        改进的Apriori算法在图书馆的具体实现        以安徽省图书馆某年度读者借阅事务库为例，可从图书馆借阅

14、记录中挖掘出形如“读者-图书”强关联规则。首先要进行数据清洗，只保留属性概念中分层最低层的属性项，将同一个读者的所有借阅记录合并为一条记录。        (一)算法思想        在读者借阅记录关联规则挖掘过程中有一些特殊的性质，因为每一个读者借阅记录的长度是固定的，即含有五个单项，前四个是属性值，最后一个是图书分类号，并且要挖掘的规则最后一项必须是图书分类号，且不能出现冲突的属性值或图书分类号。基于这些特殊性质，在数据挖掘中对A

15、priori改进算法如下：        1)把压缩过的事务集读入内存;        2)扫描事务集，找到每一类频繁单项：即频繁的年龄段、频繁的学历、频繁的职称、频繁的职业、频繁的图书分类。        3) 把各类频繁的属性单项和频繁的图书分类单项连接成 2 - 候选频繁项集， k = 2。即生成年龄-图书类，学历-图书类，职业-图书类，职称-图书类，

16、分别生成频繁2项集。        4) 检查k-候选频繁项集，记录其支持度和前件的支持度。频繁项集的连接条件是前n项是为读者属性项，且读者的属性项内容各不相同，最后一项为相同的图书分类项。        5) 输出置信度和支持度达到要求的频繁 k - 频繁项集。置信度为支持度除以前件的支持度。        6) 用得到k - 频繁项集互相连接得到k+1

17、- 候选频繁项集。通过剪枝，可减少连接的频繁项集的个数，提高程序运行的效率。下面的是剪枝连接的规则：        a) 如果频繁项集A 和 B 最后一项不同的时候不能连接。        b) 含有属于同一属性类别的不同单项，则不能连接。        c) 频繁项集也不能和自身连接。      

18、  d) 如果用conf代表前件支持度，那么当min ( A.conf， B.conf)/最小支持度<最小置信度时，不能连接 A，B。        e) 其它情况可以连接。        7) k +， 如果生成的候选频繁项集数目不为0，转4)，否则结束。        本算法主要改进是步骤6， 这是经典的Apriori算法没有的

19、。其他的连接过程可以参阅Apriori的连接。本文通过设置最小置信度阈值以找出强关联规则，令图书类型为每条规则后件，读者属性为每条规则前件，最后得到关联规则。        (二)程序实现        / apriori算法的程序        void Apriori:Do()      

20、60;         vector candidates;        vector patterns;        generate2candidates(candidates); / 生成候选2项集        while(!candidates.empty

21、() / 当候选项集为空时中止         verify_candidate(candidates， patterns);/ 过滤候选k-1项集， 返回用于连接生成候选k项集的列表，同时输出满足所有条件的规则        generate_k_candidates(patterns，candidates); / 连接生成候选k项集， 准备下一次循环       

22、 patterns.clear();                        生成K项候选频繁集：        inline void Apriori：generate_k_candidates(const vector&patterns， &

23、#160;      vector&candidates)                for(int i = 0; i < patterns.size(); +i)/ 遍历过滤后的候选k-1项集， 两两连接        for(int j = i+1; j < patter

24、ns.size(); +j)        if(Items_method：Is_compatible_Items(patternsi.items_，patternsj.items_)/ 首先判断能否连接        if(double)min(patternsi.freq_，patternsj.freq_) / minSupport_ >= minConf_)     

25、0;  Items items = Items_method：join_Items(patternsi.items_，patternsj.items_);/ 连接得到k项集， 保存到输出列表        candidates.push_back(ItemsCounter(items，0，0);                 

26、       (三)算法评价        通过上述的介绍，可以看到本算法的思路基本上与Apriori算法保持一致，即它们的共同之处是通过扫描数据得到那些支持度不小于用户给定的最小支持度的频繁项集，但是又有不同之处就是在扫描数据库之前就进行了剪枝，在剪枝后再重新连接扫描数据库，减少了扫描的次数。        在算法效率上，通过数据压缩可将挖掘的数据一次性扫描进入内存中，避免了重复磁盘I/O操作，没有压缩的数据不可能一次性读入内存，从而提高了计算效率;另通过数据压缩减少了每一项字符长度，特别是在比较两项是否相同的时候，需比较的字符数就少了很多，可以提高运算速度。通过使用数据压缩的方式，节省了内存，减少了候选集比较的时间，从而生成频繁项集速度将更快，同时加入了同属性列只能出现一次和后件必须相同的约束，使得连接次数大大减少，计算复杂度也降低了。在对图书馆这样的大型数