数据挖掘中加权关联规则的研究.docVIP

数据挖掘中加权关联规则的研究 　　摘要：随着Internet的迅速发展和普及，网络系统中的信息“超载”现象越来越严重。面对众多信息的“海洋”，用户经常会迷失在其中，无法顺利找到自己需要的信息。本文针对网络信息推荐系统面临的主要问题，依据 Apriori算法思想，提出一种加权关联规则算法，并应用于基于大众标签的推荐系统，进行bookmark, user, tag三元实验分析,通过对tag的相似性来挖掘用户的喜好。实验结果表明：通过加权tag聚类在一定程度上解决了tag冗余的问题,进一步优化了推荐结果。 　　关键词：数据挖掘 加权关联规则 Apriori算法 改进 　　中图分类号: TP311 文献标识码：A 文章编号：1007-9416(2011)11-0138-02 　　 　　1、引言 　　针对关相互关联的规则进行挖掘的话，研究者就会提出一整套的的挖掘算法。在所有的关联规则的挖掘算法中Apriori算法应该算是最经典的算法之一。这一算法的核心方法在于频集理论的递推。由于Apriori这个算法是基于两阶段的频集思想方法进行的，因此可以将关联规则挖掘算法相应的设计分成两个子问题来研究： 　　首先：研究者必须找到一个支持度相对来说大于最小支持度的阈值的一个所谓的项集（Itemset），也就是所谓的频集（Frequent Itemset）。 　　然后就是，由第一步的频集进行相互的关联规则。 　　关于第一步所表现出的基本中心思想就是如何以一个长度为k的频集来根据Lk连接操作并且产生一个长度为k 1的候选频集集合Ck 1，最后通过所有的扫描交易相关的数据库，通过验证相关的候选频集将集合Ck 1中的所有候选频集进行相关的整合，从而生成相应的一个长度大约为k 1的频集Lk 1。但是研究发现这一步是需要不断地反复扫描相关的交易数据库，因此可以看出这一步是制约整个算法性能的关键因素所在。但是第二步相对来说简单易行，只需要给定一个频集Y={I1，I2，…，Ik}就可以了，并且将频级赋予相关的数值，k2，IjI，根据上面的来产生一个仅仅包含集合{I1，I2，…，Ik}中的所有项的相关规则就可以了（但最多只能是k条），只要生成了所有的这些规则，那么所有的只要是比最小置信度阈值大的所有关联规则就会被相应的保留下来。 　　但是我们应该清楚Apriori算法并不十全十美，也同样会存在着效率低下的相关问题，所以，不断有研究者进行改进，他们往往会以Apriori挖掘算法为基础进而提出了其他的相应算法。比如研究者会利用修剪技术（Pruning）及其方法[1]来降低所有的候选集的内容大小，或者是利用杂凑树（HashTree）[41]这种先进的方法改进每个项集的支持度并且提高生成所有频集算法的速度以及相对的性能。但是无论如何改进，由于他们的基础不变，仍然存在着一下各种缺陷： 　　一是容易产生大量的候选集，如当要生成一个很长的规则的时候，产生的中间元素也是巨大量的。 　　二是由于频集使用了参数minsupp，所以就无法对小于minsupp的事件进行分析；而如果将minsupp设成一个很低的值，那么算法的效率会降低。 　　2、基于Apriori算法的改进思路描述 　　早在1998年Brin等人就提出了有关动态项集进行计数的DIC方法。这个算法的主要思想是通过扫描不同时刻来添加相关的候选项集，同时动态项集的计数技术又将数据库整体内容划分为所谓的标记开始点的块。这个算法不同于Apriori算法的每次仅仅在完整的数据库进行扫描前确定相关的候选项的问题，同时这种变形也是可以在任何开始点的地方添加新的候选项集。但是该种结果算法所需要的数据库相对Apriori来说很少的。 　　推论1推演出来的Fp-树,是能够删除支持度比wminsup这一项目小的的项目类型,同时还不会影响到加权频繁集生成的过程的。因此我们在创建所谓的Fp-树的头表的过程中,只要我们相对保留那些支持度比wminsup要大的的项目就可以了。同时还要根据它们支持度的大小,他们各自的权值从小到大进行排列.最后才是根据这个头表进行创建Fp-树的过程。 　　3、基于大众标签的加权关联规则算法实现 　　3.1 基于大众标签的加权关联规则算法模型 　　大众标签系统是4种典型社会性软件之一。下面的就是表明用户是怎样应用tag的.而Free Tags则是用来标注用户发表的信息，系统通过把所有相同的标签信息进行归类整理,但这样做的弊端在于抹煞了信息所具有的的主观性.但对于信息提供者来说他们比其他的外来用户更加明确自己表述所具有的含义,所以即便是Free Tags所用的一些词语可能在全文中的应用的频率不高,但却比一些词频高的其他相关类型的关键字更加能够反映出整提的信息特征出来。