自适应遗传模拟退火的Web日志关联挖掘

1、自适应遗传模拟退火的Web日志关联挖掘摘要：提出一种基于自适应遗传模拟退火策略的Web日志关联规则挖掘算法。该算法在遗传模拟退火策略基础上，引入自适应的交叉概率和变异概率，使其具有较强的全局搜索能力，有效地避免了早熟的现象。实验结果证明，该算法能有效地解决Web日志关联规则挖掘问题。关键词：关联规则；遗传算法；模拟退火算法；Web挖掘；自适应1关联规则挖掘模型在关联规则系统中，规则本身是“如果条件怎么样、怎么样，那么结果或者情况就怎么样”的形式。可表示为“AB联规则，它迪扌舌两个部分：样部A称为H件、右部称为后件前件可以包括一个或多个条件，在某个给定的正确率中，要使后件为真，前件中的所有条件必

2、须同时为真。后件一般只包括一种情况。如:购买计算机有购买财务软件趋向的关联规则、年龄在30至40岁之间并且年收入在4200元至5000元之间的客户购买高清晰度彩色电视机趋向的关联规则可分别表示为：buy(x,”computer)buy(x,”finacial_management_softwar6)age(30,40”)Aincome(”4200,5000)buy(x,high_resolution_tv)数据项集合A和B出一项或多项屈惟们必分忙为决策属性和任务属性。通过对问题的分析，可以发现，决策属性相互间是无序的。因此可以将决策属性一次性排定顺序组成属性串，且在挖掘过程中不变其顺序。为了便

3、于问题的分析，作以下形式定义。定义1(Web事务。)在事务文件中出现的所有页面集合表示为P=p1,p2,pn。其中每个页面pi(i=1,2,n)通过其URL地址呛一表示。事务集合U表示为U=u1,u2,un，每个事务ui=i=1,2,m均为页面集合P的子集:定义2(页面权值。)假定将用户访问页面的平均停留时间作为该页面的权值。整个事务的权值为weight(uk)二刀DD(|uk|i=1DD)w(pl,uk)/|uk|。定义3(向量空间。)事务集合中的每一个事务ui(i=1,2,m)可以转换为页面空间上的n维向量，u=favgpm=SX(pm1(favg-f)+pm2(f-fmin)favg-f

4、minSX)ffavg其中，fmax为种群最大适应度,favg为短代种胖的平均适应度值，fmin为种群最小适应度值，f为宾交叉的两个个体中较大的适应度值，f为変变匸个休的适皿腹值、Pc1Pc2Pc3,Pm1Pm2Pm3取(0,1)区间的值，可在优化过程中调整。2.5个体模拟退火过程用适应度作为模拟退火遗传算法中的能量，对算法中的近邻子集采用动态调节的方式选取：M=入x(fmax-favg)。当适应度值增加时，接受该解作为下一个当前解，否则，以一定的概率p=exp(-fitness/T)接玄孩解“即p=1fi+1p二exp(SX(fi+1-fiTSX)fi+1fi其中，fi+1为r个休的适应度佔

5、，fi为父个体的适应度值，淋皮T山随右算法进柠递减其值的控制参数担为-2.6并行模式AGSAA算法采用主从式的并行遗传算法模型，该模型在不改变遗传算法结构的基础上，将一个群体的选择、交叉和变异等全局操作由主处理器串行进行，而适应度的评价和计算由各个从处理器并行执行。2.7结束条件如果经过若干代计算后，仍然没有满足用户给定阈值的规则,则终止并输出结果3实验及分析3.1实验环境为验证本文所提出方法的有效性，采用天网2001年用户查询与点击日志。其中，用户查询日志记录了用户查询时提交的关键词、提交时间、用户ip、页号及是否在cache中命中等信息。天网点击日志记录了用户的点击时间、查询串、点击的UR

6、L、点击页面的编号、点击URL的序号等信息。系统数据共维护了100多万个有效页面，被点击的URL只有16万多。经过数据净化处理，从中识别出2019条事务和317个页面。实验过程中所使用到得参数初始化定义为：种群规模150、交叉概率0.8、变异概率0.15、初始温度1、最大迭代次数genmax=220、支持度阈值10%、置信度阈值80%。实验环境为Intelc2.0GHZ、2GB内存、Windowsxp和MATLAB7.0。分别对SA、AGA和AGSAA算法进行对比试验。3.2AGSAA算法流程AGSAA算法流程如图1所示：3.3实验结果及分析表1同计算时间下三种算法关联规则提取量的比较计算时间

7、/秒规则提取量/条SAAGGAGSAA208131030141916402025325027334460354557图2描述的是在同迭代次数下SA、AGA和AGSAA三种算法产生的关联规则数的比较。从图2可看出，AGSAA算法能够有效地进行关联规则挖掘，具有较快的收敛速度。图3描述的是3种算法在同迭代次数下关联规则准确率的比较。图3表明AGSAA算法挖掘出的规则的准确率比SA和AGA算法要高。表1描述的是SA、AGA和AGSAA算法在同计算时间下关联规则提取量的比较。从表1可看出，在初始阶段，AGA算法挖掘的规则数要高于AGSAA算法，但是在中后期阶段，AGSAA算法的挖掘效果要优于SA和AG

8、A算法。这主要是因为通过引入自适应的交叉概率和变异概率，有利于AGSAA算法跳出局部最优解，增强了较差个体的变异能力，克服了早熟的现象。4结束语针对Web日志关联规则挖掘，本文在模拟退火遗传算法基础上，引入自适应的交叉概率和变异概率，且采用并行处理技术保持和丰富种群的多样性。通过对Web日志数据进行关联规则的实验和分析得出，该算法具有较强全局搜索能力，有效避免了早熟现象。表明该算法能有效地应用于Web日志关联规则挖掘中。参考文献：忠植.知识发现M.北京:清华大学出版社，2002.阮光栅基于兴趣度策略的启发式web挖掘算法J.计算机工程与应用，2009(5).朱颢东,钟勇.一种改进的模拟退火算法

9、J.计算机技术与发展,2009(6).GALED.ThegameofHexandtheBrouwerfixedpointtheoremJ.AmericanMat-HematicalMonthly,1979(10).李凤营，赵连朋，王红雨.一种基于遗传算法的关联规则改进方法J.计算机工程与应用,2008(10).武兆慧,张桂娟，刘希玉.基于模拟退火遗传算法的关联规则挖掘J.计算机应用,2005(5).SRINIVASM,PATNAILKLM.AdaptiveprobabilitiesofcrossoverandmutationingeneticalgorithmsEEETransactiononsystem,ManandCybernetics,1994(4).任子武，伞治.自适应遗传算法的改进及在系统识