基于改进的AprioriAll算法的Web序列模式挖掘研究

《基于改进的AprioriAll算法的Web序列模式挖掘研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、论文所属栏目：计算机应用基于改进的AprioriAll算法的Web序列模式挖掘研究吴海燕，朱静君，高国柱，程志锐（清华大学计算机与信息管理中心，北京100084）摘要：为了减少AprioriAll算法挖掘过程中候选序列的生成以及对序列数据库的扫描次数，提高算法的挖掘效率，提出了一种基于改进的AprioriAll算法的Web序列模式挖掘方法。首先对数据进行预处理，然后利用经过改进的AprioriAll算法进行模式挖掘。算法的改进主要有两点：一个通过改变候选序列的连接方式来减少候选序列的产生；二是通

2、过减少不必要的数据库扫描操作来提高算法的效率。通过实验验证了改进后算法在Web序列模式挖掘过程中的高效性和正确性。关键词：AprioriAll算法；序列模式；Web日志挖掘；事务；最大向前路径中图法分类号：TP311文献标识码：AResearchofWebSequentialPatternMiningBasedonImprovedAprioriAllAlgorithmWUHai-yan,ZHUJing-jun,GAOGuo-zhu，ChengZhirui(ComputerandInformati

3、onManagementCenterofTsinghuaUniversity,TsinghuaUniversity,Beijing100084,China)Abstract:ToreducethegenerationofcandidatesequencesandthescanstosequencedatabaseforAprioriAllalgorithm,anefficientsequentialpatternminingmethodbasedonimprovedAprioriAllalgor

4、ithmispresented.Firstly,dataarepreprocessed.ThendothesequentialpatternminingwithimprovedAprioriAllalgorithm.TheimprovementsofAprioriAllalgorithmaremainlytwopoints:oneistochangetheconnectionofcandidatesequencestoreducethegenerationofcandidatesequences

5、;theotheristoreducetheneedlessdatabasescanstoimprovetheefficiencyofalgorithm.Finally,theefficiencyandvalidityofimprovedAprioriAllalgorithmisvalidatedthroughexperiments.Keywords:AprioriAllalgorithm;sequentialpattern;weblogmining;transaction;maximalfor

6、wardpath0引言Internet上蕴含着海量的信息，每天都有大量的用户通过访问Internet上的各种网站来获取自己所需的信息。用户的访问行为会在网站的日志中留下记录，通过对日志进行挖掘可以得到用户的访问模式。利用这些访问模式可以改进网站的拓扑结构，使得用户能够以更少的操作获得更多的有用信息。因此，Web日志挖掘有很好的应用前景，是目前非常热门的研究领域。序列模式挖掘是Web日志挖掘的一个重要研究课题，它是由R.Agrawal和R.Srikant[1]提出的。用户访问的序列模式是指用户访问

7、序列集合中满足一定支持度阈值的频繁子序列，它们反映了用户的频繁访问模式。而要挖掘出所有的用户访问序列模式，首先就要对日志中的原始数据进行预处理，得到用户的访问序列。这需要经过数据清理、用户识别、会话[5]识别和事务识别四个步骤，最终得到用户访问的事务数据库。接下来就是利用挖掘算法对[1]事务数据库中的序列进行挖掘。AprioriAll算法是序列模式挖掘的经典算法。它的主要思想是：每次扫描序列数据库后，利用当前得到的频繁序列生成候选序列，在下次扫描序列数据库时计算所有候选序列的支持度，把满足最小支

8、持度阈值的候选序列作为下次扫描得到的频繁序列，如此循环，直到无法产生频繁序列为止。AprioriAll算法的缺点是容易产生大量的候选序列，而且候选序列的长度每增加1都需要扫描一遍序列数据库，因此在算法的执行过程中需要反复多次扫描序列数据库，造成当序列较多或者序列较长的时候算法的挖掘效率很低，而且不容易挖掘到较长的序列模式。针对于此，我们对AprioriAll算法进行了一定的改进，并在实验中取得较好的挖掘效果。本文的余下部分首先分别对数据预处理和模式挖掘做详细的介绍，然后通过实验来展示算法改进后的