论文部分内容阅读
摘要：对现有的Apriori算法进行改进，用分治策略引入哈希技术的方法完成了压缩侯选集，减少频繁扫描数据库的次数，克服了原有关联规则的数据挖掘算法生成频繁集比较大，且需要反复扫描数据库的问题。
关键词：Web数据挖掘；网站个性化信息推荐；关联规则
中图分类号：TP301文献标识码：A文章编号：1009-3044(2008)24-1265-02
A Personalized Information Recommendation of Improved the Apriori Algorithm
YANG Jie
(Zhejiang Financial Professional College, Hangzhou 310020, China)
Abstract: This paper improved the apriori algorithm, complete the compress reserve by introducing the Hash technoloy, reduce the times of scanning the data base,overcome the problem that the data mining algorithm about association rules produce the big frequency collection and scan the database again and again.
Key words: web data mining; web personalized information recommendation; association rules
1 引言
随着网络信息技术的快速发展，网络中的信息量越来越大，Internet出现了“信息爆炸”的现象。在这种背景下，用户可能在花费了大量的时间后依然无法获取自己所需的信息资源，即产生“信息迷航”现象[1-4]。因此，通过识别不同用户的需求特点，以此采用个性化的服务策略和方式，将很好解决这个问题。
2 Apriori算法
Apriori等在1993年设计了一个基本算法Apriori[5]，提出了挖掘关联规则的一个重要的基于两阶段频集思想的方法，是最典型的层次算法，是布尔关联规则采掘算法中最成功的一类算法。其核心技术为其它各类布尔关联规则采掘算法所广泛采用。算法的思想是：如果说S是频繁项集，对于S的任意非空子集L，我们就可以通过计算可信度，也就是：conf support(S)/support(L)，并通过conf≥miniconf(最小可信度)来确定规则L→(S-L)是否确立(该规则由于S是频繁项集故肯定具有最小支持度)。
例如：ABCD是频繁项集，AB是它子集
如果conf=support(ABCD)/support(AB)≥miniconf(最小可信度)
那么规则AB→CD是成立的，否则不成立。
具体到页面会话中，S是频繁项集即S中的页面是一次访问中经常同时访问的页面，而访问序列中最后的一个页面往往是用户的访问目的。所以用频繁项集产生所需的规则时，主要导出S的前n-1个页面到最后一个页面的规则，如果此规则满足最小可信度，将此规则存入模式库中。
3 Apriori算法的改进
从Apriori算法的思路中可以看出，当有相当数量的频繁1项集，Apriori会产生大量的候选集，而且可能需要重复的扫描数据库，这无疑降低了算法的效率，本文提出的算法是通过分治策略引入哈希技术来改进产生频繁项目集，并且用数据查询语言实现关联规则挖掘算法。要得出用户的频繁访问路径，如果用户每次访问的最大向前引用都很长的话，那就需要生成若干的k项集，产生大量的候选项目集，每次需要重复的多次的扫描同一个事务库，我们提出一种改进策略。为了讨论方便，这里对I中的每个项目用其项目编号来代替。和前面一样，把所有频繁k项目集的集合记为Lk，比如L1为所有频繁1项目集的集合。这里我们假定交易数据库中的交易以及在算法中出现的任一个项目集中的项目都是按照项目编号顺序排好的。在后面的算法中，我们容易看到，只要保证开始时也就是2项目集中的项目是有序的，那么算法的执行将自动保证任一个项目集也是有序的。
通过利用哈希技术通过构建一个相当小的C2以产生更小的L2来导出C3。如果C2很庞大，数据库就不能有效修剪。此步之后，Li的大小随i值的增大迅速减小，从而导致很小的Li 1，这样对应的开销就小得多，极大的提高了整个过程的执行效率。
哈希表的优点就是避免反复查找的过程，通过定址的方法直接找到要查找的数据，通常通过设计一个哈希函数，它是一个映象，只要使得任何关键字由此所得的哈希函数值都落在表长允许范围之内就可以。基本思路如下：
1) 和Apriori的思想一样，首先生成候选1—项目集Cl。算法简单地扫描事务数据库，对每一个项目计数。
2) 设定最小事务支持数(即min_support)，可以由存储过程来计算，也可以由用户自己指定。确定频繁1—项目集的集合L1，如下表。频繁项目集L1中的任何一个业务都大于或等于最小支持度。
3) 产生候选2—项目集。算法使用L1∞L1产生候选项目集C2。C2中的每一个项目集是对两个属于L1的频繁项目集做一个连接来产生的。
4)扫描事务数据库，计算C2中每个候选项目集的支持数，用一个临时表存放C2。
5) 选出事务中每个业务不小于最小支持度的事务，从而确定频繁2项目集的集合L2，并计算其事务对应的哈希函数与项目数2组合。
6) 产生3项候选集的集合C3，利用Apriori算法的特点，采用剪枝技术，删除所有其子集不是频繁项目集的候选项目集，从而大大缩减了3项候选集的大小，为生成频繁项目集L3提高效率。
7) 生成频繁3—项目集L3，计算每条事务的支持数。
8) 如此循环下去，不断生成候选集，再由此生成频繁项目集，直到候选项为空。
运用哈希算法主要是为生成下一个候选集过滤掉不需要得项目集。当扫描数据库来计算候选k项集得支持度得时候，运用哈希技术来预先存储(k 1)项候选集，也就是经过一些修剪后把所有可能的(k 1)项集hash在一个hash表中。Hash表中每个hash单元由一个数字组成，该数字代表迄今有多少项集被hash到该单元。位矢量是基于hash表构造的，如果Hash表中相应的数目的个数大于或者等于s的话，对应的位的值就设为1，否则为0。
4 实验分析
图1用实例对Apriori算法进行分析。第一次迭代中，Apriori算法简单的扫描所有事务，计算每一项的出现次数，得到了候选1项集Cl，假设事务的最小支持度为2，那么频繁1项集L1,就由满足最小支持度要求的候选1项集构成。Apriori算法利用L1∞L1生成候选集C2。接下来，扫描数据库中10个事务，计算C2中每个候选集的支持度。然后，基于C2中每个候选2项集的支持度可以确定频繁2项集L2。候选集C3由L2产生，过程如下：L2中具有相同第一个项目的两个频繁2项集{AB}和{AC}首先识别出来。接着，Apriori检查由前面两个项目{AB}和{AC}组成的2项集{BC}是否构成一个频繁2项集。因为{BC}本身是一个频繁2项集，于是可以得到{ABC}的所有子集都是频繁的，于是{ABC}成为一个候选3项集。同理可得{ABE}也是一个候选3项集。这就是利用上文所说的Apriori性质进行连接和剪枝的过程。从L3中无法构造候选4项集，此时算法终止。
从这个算法的过程来看，产生尽可能小的候选集Ci是很重要的，因为在扫描整个数据库的过程中要计算Ci中每一个项目的支持度。
图2给出一个具体应用哈希思想的例子。构造哈希表的目的就是通过散列技术来压缩候选集，那么哈希表的构造方法在一定程度上决定了散列的效果。本文采用了除留取余法构造hash函数：(x*factor y) mod hashtblsize。显然，两个未定的参数：hash表的表长和factor系数是决定散列效果的重要因素。因为，如果哈希表的表长较小，那么散列的结果就是哈希表的每个bucket中都有多个候选集，如果每个bucket的计数都大于最小支持度，那么哈希表无法过滤掉任何一项，那么它不但没什么压缩过滤作用，而且构造的过程还消耗了时间。而factor系数是个不确定的因素，例如，我们取x=3，y=2，当hashtblsize=10的时候，无论factor取10, 20, 30结果都相同，而当hashtblsize=20的时候，结果就会产生差异。在实验分析一节我们通过实验对相同测试集，在相同最小支持度，不同表长的情况下，运用该算法产生的相关结果进行分析，比较结果，我们可以得到，当hash的表长越长时，散列的效果越好。而且我们验证了这样的结论：初始候选集的生成，尤其是频繁2项集，是提高关联规则挖掘效率的关键。用hash表有效的生成频繁2项集提高了算法效率。
5 结束语
针对目前关联规则的经典算法产生的侯选集较大、需要扫描的数据量较多的现状，利用哈希技术和分治结合的方法，对现有Apriori算法进行改进，实现提高挖掘效率，提高给出推荐页面的速度的目的。
参考文献：
[1] 汪晓岩，胡庆生，庄镇泉. 基于关联规则挖掘的个性化智能推荐服务[J]. 计算机科学，2002,29(7):63-65.
[2] 徐宝文，张卫丰. 数据挖掘技术在Web预取中的应用研究[J]. 计算机学报，2001,24(4):89-91.
[3] 许兆新，周双娥，郝燕玲. 最优关联规则的形式和挖掘思想的研究[J]. 计算机工程与应用，2001,37(20):118-119.
[4] 王运峰，张蕾. 数据库中关联规则的并行挖掘算法[J]. 计算机工程与应用，2001,37(16):99-100.
[5] 张仁平，卜淮原. 关联规则挖掘快速更新算法的研究和实现[J]. 计算机工程与应用，2001,37(6):101-103.
关键词：Web数据挖掘；网站个性化信息推荐；关联规则
中图分类号：TP301文献标识码：A文章编号：1009-3044(2008)24-1265-02
A Personalized Information Recommendation of Improved the Apriori Algorithm
YANG Jie
(Zhejiang Financial Professional College, Hangzhou 310020, China)
Abstract: This paper improved the apriori algorithm, complete the compress reserve by introducing the Hash technoloy, reduce the times of scanning the data base,overcome the problem that the data mining algorithm about association rules produce the big frequency collection and scan the database again and again.
Key words: web data mining; web personalized information recommendation; association rules
1 引言
随着网络信息技术的快速发展，网络中的信息量越来越大，Internet出现了“信息爆炸”的现象。在这种背景下，用户可能在花费了大量的时间后依然无法获取自己所需的信息资源，即产生“信息迷航”现象[1-4]。因此，通过识别不同用户的需求特点，以此采用个性化的服务策略和方式，将很好解决这个问题。
2 Apriori算法
Apriori等在1993年设计了一个基本算法Apriori[5]，提出了挖掘关联规则的一个重要的基于两阶段频集思想的方法，是最典型的层次算法，是布尔关联规则采掘算法中最成功的一类算法。其核心技术为其它各类布尔关联规则采掘算法所广泛采用。算法的思想是：如果说S是频繁项集，对于S的任意非空子集L，我们就可以通过计算可信度，也就是：conf support(S)/support(L)，并通过conf≥miniconf(最小可信度)来确定规则L→(S-L)是否确立(该规则由于S是频繁项集故肯定具有最小支持度)。
例如：ABCD是频繁项集，AB是它子集
如果conf=support(ABCD)/support(AB)≥miniconf(最小可信度)
那么规则AB→CD是成立的，否则不成立。
具体到页面会话中，S是频繁项集即S中的页面是一次访问中经常同时访问的页面，而访问序列中最后的一个页面往往是用户的访问目的。所以用频繁项集产生所需的规则时，主要导出S的前n-1个页面到最后一个页面的规则，如果此规则满足最小可信度，将此规则存入模式库中。
3 Apriori算法的改进
从Apriori算法的思路中可以看出，当有相当数量的频繁1项集，Apriori会产生大量的候选集，而且可能需要重复的扫描数据库，这无疑降低了算法的效率，本文提出的算法是通过分治策略引入哈希技术来改进产生频繁项目集，并且用数据查询语言实现关联规则挖掘算法。要得出用户的频繁访问路径，如果用户每次访问的最大向前引用都很长的话，那就需要生成若干的k项集，产生大量的候选项目集，每次需要重复的多次的扫描同一个事务库，我们提出一种改进策略。为了讨论方便，这里对I中的每个项目用其项目编号来代替。和前面一样，把所有频繁k项目集的集合记为Lk，比如L1为所有频繁1项目集的集合。这里我们假定交易数据库中的交易以及在算法中出现的任一个项目集中的项目都是按照项目编号顺序排好的。在后面的算法中，我们容易看到，只要保证开始时也就是2项目集中的项目是有序的，那么算法的执行将自动保证任一个项目集也是有序的。
通过利用哈希技术通过构建一个相当小的C2以产生更小的L2来导出C3。如果C2很庞大，数据库就不能有效修剪。此步之后，Li的大小随i值的增大迅速减小，从而导致很小的Li 1，这样对应的开销就小得多，极大的提高了整个过程的执行效率。
哈希表的优点就是避免反复查找的过程，通过定址的方法直接找到要查找的数据，通常通过设计一个哈希函数，它是一个映象，只要使得任何关键字由此所得的哈希函数值都落在表长允许范围之内就可以。基本思路如下：
1) 和Apriori的思想一样，首先生成候选1—项目集Cl。算法简单地扫描事务数据库，对每一个项目计数。
2) 设定最小事务支持数(即min_support)，可以由存储过程来计算，也可以由用户自己指定。确定频繁1—项目集的集合L1，如下表。频繁项目集L1中的任何一个业务都大于或等于最小支持度。
3) 产生候选2—项目集。算法使用L1∞L1产生候选项目集C2。C2中的每一个项目集是对两个属于L1的频繁项目集做一个连接来产生的。
4)扫描事务数据库，计算C2中每个候选项目集的支持数，用一个临时表存放C2。
5) 选出事务中每个业务不小于最小支持度的事务，从而确定频繁2项目集的集合L2，并计算其事务对应的哈希函数与项目数2组合。
6) 产生3项候选集的集合C3，利用Apriori算法的特点，采用剪枝技术，删除所有其子集不是频繁项目集的候选项目集，从而大大缩减了3项候选集的大小，为生成频繁项目集L3提高效率。
7) 生成频繁3—项目集L3，计算每条事务的支持数。
8) 如此循环下去，不断生成候选集，再由此生成频繁项目集，直到候选项为空。
运用哈希算法主要是为生成下一个候选集过滤掉不需要得项目集。当扫描数据库来计算候选k项集得支持度得时候，运用哈希技术来预先存储(k 1)项候选集，也就是经过一些修剪后把所有可能的(k 1)项集hash在一个hash表中。Hash表中每个hash单元由一个数字组成，该数字代表迄今有多少项集被hash到该单元。位矢量是基于hash表构造的，如果Hash表中相应的数目的个数大于或者等于s的话，对应的位的值就设为1，否则为0。
4 实验分析
图1用实例对Apriori算法进行分析。第一次迭代中，Apriori算法简单的扫描所有事务，计算每一项的出现次数，得到了候选1项集Cl，假设事务的最小支持度为2，那么频繁1项集L1,就由满足最小支持度要求的候选1项集构成。Apriori算法利用L1∞L1生成候选集C2。接下来，扫描数据库中10个事务，计算C2中每个候选集的支持度。然后，基于C2中每个候选2项集的支持度可以确定频繁2项集L2。候选集C3由L2产生，过程如下：L2中具有相同第一个项目的两个频繁2项集{AB}和{AC}首先识别出来。接着，Apriori检查由前面两个项目{AB}和{AC}组成的2项集{BC}是否构成一个频繁2项集。因为{BC}本身是一个频繁2项集，于是可以得到{ABC}的所有子集都是频繁的，于是{ABC}成为一个候选3项集。同理可得{ABE}也是一个候选3项集。这就是利用上文所说的Apriori性质进行连接和剪枝的过程。从L3中无法构造候选4项集，此时算法终止。
从这个算法的过程来看，产生尽可能小的候选集Ci是很重要的，因为在扫描整个数据库的过程中要计算Ci中每一个项目的支持度。
图2给出一个具体应用哈希思想的例子。构造哈希表的目的就是通过散列技术来压缩候选集，那么哈希表的构造方法在一定程度上决定了散列的效果。本文采用了除留取余法构造hash函数：(x*factor y) mod hashtblsize。显然，两个未定的参数：hash表的表长和factor系数是决定散列效果的重要因素。因为，如果哈希表的表长较小，那么散列的结果就是哈希表的每个bucket中都有多个候选集，如果每个bucket的计数都大于最小支持度，那么哈希表无法过滤掉任何一项，那么它不但没什么压缩过滤作用，而且构造的过程还消耗了时间。而factor系数是个不确定的因素，例如，我们取x=3，y=2，当hashtblsize=10的时候，无论factor取10, 20, 30结果都相同，而当hashtblsize=20的时候，结果就会产生差异。在实验分析一节我们通过实验对相同测试集，在相同最小支持度，不同表长的情况下，运用该算法产生的相关结果进行分析，比较结果，我们可以得到，当hash的表长越长时，散列的效果越好。而且我们验证了这样的结论：初始候选集的生成，尤其是频繁2项集，是提高关联规则挖掘效率的关键。用hash表有效的生成频繁2项集提高了算法效率。
5 结束语
针对目前关联规则的经典算法产生的侯选集较大、需要扫描的数据量较多的现状，利用哈希技术和分治结合的方法，对现有Apriori算法进行改进，实现提高挖掘效率，提高给出推荐页面的速度的目的。
参考文献：
[1] 汪晓岩，胡庆生，庄镇泉. 基于关联规则挖掘的个性化智能推荐服务[J]. 计算机科学，2002,29(7):63-65.
[2] 徐宝文，张卫丰. 数据挖掘技术在Web预取中的应用研究[J]. 计算机学报，2001,24(4):89-91.
[3] 许兆新，周双娥，郝燕玲. 最优关联规则的形式和挖掘思想的研究[J]. 计算机工程与应用，2001,37(20):118-119.
[4] 王运峰，张蕾. 数据库中关联规则的并行挖掘算法[J]. 计算机工程与应用，2001,37(16):99-100.
[5] 张仁平，卜淮原. 关联规则挖掘快速更新算法的研究和实现[J]. 计算机工程与应用，2001,37(6):101-103.