文章编号:10012506X(2009)1222994204
系统工程与电子技术
SystemsEngineeringandElectronicsVol.31 No.12Dec.2009
基于网络日志的数据挖掘预处理改进方法
孙宇航,孙应飞
(中国科学院研究生院,北京100049)
摘 要:对网络日志数据挖掘预处理技术进行研究,针对Frame页面过滤方法与超时阈值设定进行分析,提出了应用ID3算法改进Frame页面过滤过程中丢失SubFrame页面信息且需要进行站点提升步骤。在超时阈值的设定方面采用动态修正方法,提高预处理技术对长时间会话的识别能力的改进方法。通过实验验证,该方法有效地减少了预处理过程中的信息丢失,同时提高了挖掘结果的精度。关键词:网络日志;数据挖掘;预处理;会话识别中图分类号:TP311 文献标志码:A
ImprovedmethodofdataminingpreprocessingbasedonWeblog
SUNYu2hang,SUNYing2fei
(GraduateUniv.ofChineseAcademyofScience,Beijing100049,China)
Abstract:DatapreprocessingmethodofWeblogminingisstudied.Framepagesfilteringandovertimethresholdvaluesetingareanalyzed.Theimprovedmethodbasedoninductionofdecisiontree(ID3)algorithmandthresholdvaluedynamicamendmentalgorithmisproposed.ThismethoddealswithinformationlossbyFramepagesfilteringandthresholdvaluefixing.Transactionsessionidentificationabilityisalsoenchanced.Theexperimentaboutthismethodshowsthatthismethodisefficientinimprovingaccuracyofminingresult.
Keywords:Weblog;datamining;preprocessing;transactionsessionidentification
0 引 言
互联网的迅速发展使得网络信息量变得十分庞大,用户在网络上使用简单的信息搜索己经不能满足其需要,因而数据挖掘技术被应用于网络数据分析研究中,用以发现隐藏在网络上的知识,以便更好地了解网络文档之间的相互关系、组织形式和用户对这此文档的使用状况,并以此为基础来优化网络内容以及组织结构[1]。
网络日志作为用户在网络中访问站点时所进行的各种操作的实时记录,是十分重要的信息。通过分析日志中用户的访问规律
[2]
的数据。由于在网络日志中通常只有HTML文件与用户会话相关,所以通过检查URL的后缀删除不相关的数据。
用户识别:指识别出访问网站的每个用户。一般网络日志挖掘工具中常使用基于日志/站点的方法,并辅助一些启发式规则帮助识别用户。
会话识别:将用户的访问记录分为单个的会话。通常采用超时方法识别用户会话,如果两页间请求时间的差值超过一定的界限(超时阈值)就认为用户开始了一个新的会话。
路径补充:由于本地缓存和代理服务器缓存的存在,使得服务器的日志会遗漏一些重要的页面请求。路径补充就是将这些遗漏的请求补充到用户会话中,解决的方法类似于用户识别中的方法。
事务识别:用户会话是网络日志挖掘中唯一具备自然事务特征的元素,但是,对于某些挖掘算法来说,用户会话的数据粒度可能太大,需要利用分割算法将其转化为更小的事务,从而进行识别。
数据预处理过程[4]如图1所示。
预处理技术中会话识别对于后续挖掘工作的影响很大,国内外学者就此开展了广泛的研究[2211]。文献[4]提出了在会话识别和路径补充这两个步骤之间加入Frame页面
,可以识别用户的忠实度、喜好、
满意度,通过应用数据挖掘技术,分析用户访问行为、信
息需求取向等信息,进而整理归纳,可以发现潜在用户,实施有针对性的服务,为提高站点的竞争力提供了直观的依据。所以,基于网络日志的数据挖掘研究具有一定的实际意义。
对于网络日志挖掘工作,其中一个重要的环节是对网络日志数据的预处理,一般网络日志数据预处理主要包括[3]:数据净化、用户识别、会话识别、路径补充、事务识别。
数据净化:指删除网络服务器日志中与挖掘算法无关
收稿日期:2008212210;修回日期:2009203221。
作者简介:孙宇航(19802),男,硕士研究生,主要研究方向为数据挖掘。E2mail:sunyuhang@126.com
第12期孙宇航等:基于网络日志的数据挖掘预处理改进方法
·2995 ·
过滤,虽然滤除了SubFrame页面,但是这也造成其页面信息的丢失。文献[3]提出了基于ID3算法的页面过滤算法,克服了文献[4]的信息丢失问题。文献[526,10]在超时阈值的设定方面,分别采用基于时间、基于结构、基于引用的固定时间阈值设定,但存在会话记录被错误划分的问题。文献[7]提出在超时阈值的设定上采用对每一个页面生成一个阈值,有效地解决了长时间会话的识别问题。本文在参考文献的基础上,将ID3算法与超时阈值动态修正方法相结合,在克服页面过滤丢失信息的基础上,优化了超时阈值的设定,提高了预处理结果的精度。图1 网络日志挖掘预处理过程
1 预处理方法分析
1.1 Frame页面过滤
在实际的网络日志挖掘过程中,如果按照图1对网络日志进行预处理,则Frame页面和其SubFrame页面也将一起出现在用户会话文件中。如果在这样的用户会话文件上进行数据挖掘,Frame页面和其SubFrame页面作为频繁遍历路径或者频繁访问页组出现的概率很高,并且如果它们同时出现在挖掘结果中,这将会降低用户的兴趣度。鉴于这个问题,一些文献采用Frame页面过滤方法进行,即当用户请求Frame页面的URL时,Frame页面和其中的SubFrame页面作为个多窗口页面展现,可以将用户对Frame页面的请求看成是对多窗口页面的请求。这样,在
数据预处理阶段将Frame页面和其SubFrame页面作为个整体考虑,并把Frame页面对应的URL当作这个整体的代表。从全局而言,这样处理可以有效地消除Frame页面对日志挖掘的影响,最终提高挖掘结果的兴趣性。使用Frame页面过滤方法的网络日志挖掘过程[4]如图2所示。
在会话识别与路径补充这两个步骤之间增加了Frame
页面过滤。Frame页面过滤过程是根据从站点的拓扑结构中提取出的Frame2SubFrame关系表,从会话识别过程中生成的会话文件中,寻找Frame页面及其SubFrame页面,将会话文件中对Frame和其SubFrame页面的请求用Frame页面代替,从而删除会话文件中多余的SubFrame页面。由于删除了会话文件中的SubFrame页面,因此会丢失SubFrame页面中包含的超链接信息,所以就得依靠路径补充步骤提升的站点结构[5211]。1.2 超时阈值设定在会话识别的过程中,通常采用超时方法识别用户会话,如果两页间请求时间的差值超过一定的界限(超时阈值)就认为用户开始了个新的会话。通过为页面设置访问时间阈值,并根据页面内容及站点结构确定的页面重要程度对该阈值进行调整。超时阈值的设定一般分为[526,9210]:
(1)Hvisit:用户在整个站点停留时间的一个上界。如果超过这个阈值Hvisit,则认为新的会话开始。设t0为会话初始页的时间戳,同一用户的一个URL请求的时间t如果满足t-t0=Hvisit,则被加入当前会话,第一个满足t-t0 (3)HRef:利用用户访问历史和参引页来划分会话。如果一个用户的请求不能通过参引页上的链接进入,则很可能属于另一个会话,即当前请求的参引页没有在前而访问过的页而中出现,则是一个新的会话开始。 (4)最大向前参引模型(maxima1forwardreferences,MFC):在一个用户会话里不会出现用户先前已经访问过的页面,如果用户在向前浏览到一个网页时,按下返回按钮,则表示当前会话结束,一个新的会话开始。 以上阈值设定的不足之处在于: (1)可能使原本在同一个会话里的记录被划分到不同的会话中,也可能使原本不在同一个会话的记录被划分在同一个会话中; (2)由于用户会话产生的有效页面数比实际的有效页面数明显增多。因此,导致了会话识别的效率大大降低。 2 预处理改进方法 2.1 改进Frame页面过滤方法 图2 使用Frame页面过滤方法的网络日志挖掘过程 如上所述,应用Frame页面过滤方法可以有效地消除了Frame页面对日志挖掘的影响,然而网络日志挖掘的记录是十分庞大的,文献中的Frame页面过滤算法是对每个用户对话的每个页面进行是否Frame和SubFrame的判断,并且对判断出的子框架逐个地进行删除,而且因为SubFrame页面的删除导致后面必须用提升的站点结构,虽然较一般预处理技术增加了兴趣度,但是效率还是比较低 ·2996 · 系统工程与电子技术 make_node(Web) if((currentFrame,Pidi∈FS) make_tree(currentFrame,Web_left) elseifPidi∈Dom(FS)) 第31卷 的,而且也增加了开销。并且过滤中SubFrame被删除,在 后面的路径补充中能否完全恢复也值得商榷。 考虑到决策树分类算法具有允许多粒度层快速分类性质,可以较好地解决此问题。本文采用决策树算法中的ID3算法,对Frame页面过滤方法进行改进,进而提高过滤效率[3]。 2.1.1 ID3算法描述 [12] ID3算法的基本思想是贪心算法,采用自上而下的分而治之的方法构造决策树。首先检测训练数据集的所有特征,选择信息增益最大的特征A建立决策树根节点,由该特征的不同取值建立分枝,对各分枝的实例子集递归,用该方法建立树的节点和分枝,直到某子集中的数据都属于同类别,或者没有特征可以在用于对数据进行分割。算法描述如下。 算法:Generate_decisiontree由给定的训练数据集产生一棵决策树。 输入:训练样本Samples,由离散值属性表示;候选属性的集合attribute_list 输出:一棵决策树方法: (1)创建节点N; (2)ifSamples都在同一类Cthen;(3)返回N作为叶节点,以类C标记;(4)ifattribute_list为空then; (5)返回N作为叶节点,标记为Samples最普通 的类;∥使用多数表决; (6)选择attribute_list中具有最高信息增益(关 于信息增益的求法请参见文献)的属性test_attribute; (7)标记节点N为test_attribute; (8)foreachtest_attribute中已知值ai∥划分 Sample; (9)由节点N长出个条件为test_attribute=ai 的分枝; (10)设Si是Sample中test_attribute=ai的样本 集合∥一个划分;(11)ifSi为空then; (12)加上一个树叶,标记为Samples中最普通的类;(13)else加上一个由Generate_decisiontree(Si, attribute_list)返回的节点 2.1.2 基于ID3算法的Frame页面过滤算法 基于ID3算法的Frame页面过滤算法如下。 输入:FS表(PidFrame,PidSubFrame)对应的集合;候选属性的集合attribute_list(包括index.htm1,top.htm1,left.htm1,main.htm1,…} 输出:一棵判定树 Foreachuserssession {currentFrame=Pidi make_decition_tree(currentFrame,Web_right) }elsemake_decition2tree(currentFrame,Web_left ifattribute_list=null{ make_decition_tree(currentFrame,Web_right);} elseifGain(oneofattribute_list)>allgain(attrib2ute_list)∥Gain()为信息增益函数 currentFrame=test_attribute; foraioftest_attribute ifnot(test_attribute=ai} make_decition_tree(ai,Web_left) elseGenerate_decision_tree(ai,Web_right) } 本文认为网页上每个页面都是Web页面,所以它的信息增益最高,因此以它为根节点。currentFrame变量记录了当前处理的页面,如果当前页不是Frame页面时则将其添到左子树中,否则,即Pidi∈Dom(FS),则将当前页面的标识符Pidi赋给currentFrame,并将其添加到右子树中,且将它包含的SubFrame页面仍添加到左子树中。因为我们感兴趣的页面是Frame页面,所以它的点击率最高,其信息增益最大,因此我们将信息增益最大的总是添加到Web右子树中,而当前页不符合Frame页面属性的就是Sub2Frame页面,将其添加到左子树中。这样,决策树的右枝就是Frame,左枝就是SubFrame,很容易就完成了会话识别,并且因为SubFrame并没有被删去,因此在后面的路径补充中将其复原即可。较之Frame页面过滤算法,此算法略去了提升站点结构这一步,因此更大地提高了日志数据预处理的速度及预处理结果的质量。2.2 改进超时阈值设定方法 对于超时阈值的设定,本文通过使用访问时间间隔超出某阈值D来识别会话,根据统计的用户对页面的访问时间,在正态分布的假设下为每个页面设定一个合理的访问时间作为切分阈值,并结合页面内容及站点结构来确定页面重要程度对该阈值进行调整[7]。 定义1 链接内容比RLCR是指页面链入(LI)链出(L0})数与页面内容之比,记页面大小为SDS,B为页面RLCR对页面访问时间阈值D的影响因子,A是平滑系数,实验表明A选择为1.25比较合适。 计算方法如式(1)～式(3)所示。 (1)RLCR=2(0.618LI+0.382L0)/SDS (2)B=1-exp(-sqrt(sqrt(RLCR))) (3)D=At(1+B) 式中,t为访问时间。要设置每个页面的访问时间阈值D,先要获得统计后的页面的访问时间t,并结合页面的RLCR影 第12期孙宇航等:基于网络日志的数据挖掘预处理改进方法 ·2997 · 响因子B调整D统计后页面的访问时间,t的集合记为St={t1,t2,…,tn},页面的影响因子B集合记为SB={B1,B2,…,Bn}。 算法步骤如下。步骤1 根据日志文件log统计得到t的集合St,按用户将日志文件划分,即用户识别,根据正态分布统计页面的访问时间得到St; 步骤2 根据影响因子集合SB和A值调整St得到页面访问时间阈值集合SD,按式(3)结合A和SB计算得到SD; 步骤3 根据SD重新划分日志文件得到用户的会话集合。 通过表2数据对比可以看出,动态修正时间阈值方法较之固定时间阈值方法在会话识别方面克服了时间较长的会话被划分为不同会话,增加会话数量的缺陷。改进方法提高了对于较长时间的会话的识别能力,减弱了日志预处理过程中冗余会话数量对于挖掘效率与精度的影响。 4 结束语 本文针对网络日志挖掘工作的预处理过程进行研究,应用ID3算法改进Frame页面过滤方法,将信息增益最大的页面添加到Frame页,不符合的添加到SubFrame页,并且SubFrame也没有被删除,这样使得在路径补充步骤中减少了提升站点结构这一步。同时通过在会话识别中的超时阈值采用动态修正方法,增强了预处理过程中对于较长时间会话的识别能力。本文的改进方法应用到网络日志挖掘预处理过程中提高了挖掘结果的兴趣性。 3 实验分析 本文通过两个实验分别验证本文方法在页面过滤和会 话阈值方面的改进效果。 实验1 针对11MB日志其中包括12万条记录、642个不同HTML页面进行实验,从中识别出2133个用户会话。通过挖掘频繁访问页组将已往的页面过滤预处理技术与ID3页面过滤技术进行对比。方法比较如表1所示。 表1 页面过滤方法对比 方法一般技术 Frame改进技术 参考文献: [1]朱明.数据挖掘[M].合肥:中国科技大学出版社,2008:13256.[2]HanJW,MengXF,AngJ.Researchonwebmiming[J]. JournalofComputerResearch&Development,2001,38(4): 4052414. FS463673 △ 绝对支持度FS1 706030152010 242525552365 FS2597534983477 FS3829618699 △ FS5132002 △△ FS6436 3 [3]张婧,刘芳.基于ID3算法的Web日志挖掘预处理中的Frame 页面过滤技术的研究[J].计算机与信息技术,2007,15(6):729. [4]杨怡玲,管旭东,陆丽娜,等.Web日志挖掘预处理中的Frame页 0000 面过滤算法[J].计算机工程,2001,27(2):76277. [5]CooleyR,MobasherB,SrivastavaJ.Datapreparationformin2 ingworldwidewebbrowsingpatterns[J]. InformationSystem,1999,1(1):5232. Knowledgeand 1819△△ 基于ID3的 Frame改进技术 00 54 表1中的绝对支持度指包含频繁访问页组的最小用户会话个数,FSi表示长度为i的频繁访问页组个数,3表示发现的频繁访问页组是用户不感兴趣的,△表示发现的频繁访问页组是用户较感兴趣的,△△表示发现的频繁访问页组是用户感兴趣的。 通过表1可以看出,通过在Frame过滤中应用ID3算法后,其数据预处理结果的质量有了提高,同时更大程度地提高了挖掘结果的兴趣度。因为减少了提升站点结构这一步骤,该改进方法提高了预处理的效率,从而提高了整个Web日志挖掘的效率。 实验2 本实验数据来源某网站:211.154.163.3,服务器日志数据为2008年6月18日～2008年6月20日。本实验将固定时间阈值会话识别方法和动态修正时间阈值会话识别方法进行对比分析。如表2所示。 表2 时间阈值设定方法对比 训练数据 281473458241365 [6]SpiliopoulouM,MobasherB,BerendtB,etal.Aframework fortheevaluationofsessionreconstructionheuristicsinwebusageanalysis[J].INFORMSJournalofComputing,2004,15(2):1712179. [7]方元康,胡学刚,夏启寿.一种改进的Web日志会话识别方法[J]. 计算机技术与发展,2008,18(11):2142216. [8]殷贤亮,张为.Web使用挖掘中的一种改进的会话识别方法[J]. 华中科技大学学报(自然科学版),2006,34(7):33235. [9]ChenMS,ParkJS,YuPS.Dataminingforpathtraversalpat2 ternsinawebenvironment[C]∥IEEEProc.of16thInternation ConferenceDistributedComputingSystem,1996:3852392. [10]FuY,SandhuK,ShihM.Ageneralization2basedapproachto clusteringofwebusagesession[C]∥Proc.ofKDDWorkshop WebMining,LNCS1863,Springer2Verlag,2000:21228. [11]FaccaM,LanziPL.Mininginterstiongknowledgefromweb2 logs:asurvey[J].DataandKnowledgeEngineering,2005,53(3):2252241. [12]朱玉全,杨鹤标,孙蕾,等.数据挖掘技术[M].南京:东南大学 固定时间阈值(10min)方法 257613167437896 动态修正时间阈值方法 213542768934628 出版社,2006:1082111. 因篇幅问题不能全部显示，请点此查看更多更全内容