基于ID3算法的Web日志挖掘预处理中的Frame页面过滤技术的研究

1、基于ID3算法的Web日志挖掘预处理中的Frame页面过滤技术的研究摘要描绘了eb日志数据预处理技术的一种改良技术Frae过滤技术，对其关键局部与运作形式进展了研究与改良。讨论了Frae页面过滤预处理技术在eb页面挖掘中的效率问题，分析了决策树算法中最著名的算法ID3算法，并用ID3算法对Frae过滤算法进展了改良，比拟新旧算法的执行效率及算法结果质量，得出了新算法执行效率更高及质量更好的结论，从而搞高了对存在Frae页面的网站施行eb日志挖掘算法时挖掘结果的兴趣度。关键词ID3算法；eb日志挖掘；eb日志预处理;Frae页面过滤Internet的迅速开展使得eb为人们提供了内容丰富且数量庞大

2、的信息，随着数据挖掘技术的出现以及开展，数据挖掘逐渐被应用于eb数据。eb日志挖掘是三大类eb挖掘之一，它主要包括数据预处理和挖掘算法施行两个主要阶段.施行挖掘算法之前要对eb日志文件进展预处理，将其转化为用户会话集.本文着重讨论eb日志挖掘预处理技术中的Frae页面过滤预处理技术，即在传统的eb日志预处理过程中参加Frae页面过滤这一步骤，并提出了用决策树算法著名的ID3算法进展Frae页面过滤，进一步进步了日志数据预处理的质量和效率，从而为挖掘算法的施行提供更为准确的数据，进步了对存在Frae页面的网站施行eb日志挖掘算法时整个eb日志挖掘的效率及挖掘结果的兴趣性。2.1eb日志预处理技术

3、现状eb日志挖掘134是指将数据挖掘技术应用于eb效劳器日志文件，以发现隐藏在其中的用户访问形式。eb日志预处理是在eb日志挖掘前，对eb日志进展清理、过滤以及重新组合的过程，其目的是剔除日志中对挖掘过程无用的属性及数据，并将eb日志数据转换为挖掘算法可识别的保存形式。到目前为止提出的eb日志的预处理技术，它包含三种方法识别用户的活动集合：(1)eb效劳器提供kie，那么具有一样kie值的页面恳求是来自同一个用户，那么用户会话识别的主要的任务就是将eb日志划分为不同kie值所对应的页面恳求集合。(2)eb效劳器没有提供kie，但每个网站用户都要一个登录标识符方可访问站点，那么分析工具即可利用登

4、录标识符识别会话。假如eb效劳器既没有kie也没有登录标识符，可以利用主机地址，同时分析日志中每条记录的恳求页和引用页的URL，然后根据eb站点的拓扑构造超链接和其它启发式规那么识别用户会话，但是这种方法的准确度较低，不能100正确地识别出每个恳求对应的用户。这里主要讨论第3种预处理方法。一般eb日志预处理主要包括：数据净化、用户识别、会话识别、途径补充、事务识别数据净化指删除eb效劳器日志中与挖掘算法无关的数据。由于在eb日志中通常只有HTL文件与用户会话相关，所以通过检查URL的后缀删除不相关的数据。用户识别是指要识别出每个访问网站的用户。一般eb日志挖掘工具中常使用基于日志/站点的方法，

5、并辅助一些启发式规那么帮助识别用户。会话识别是将用户的访问记录分为单个的会话。通常采用超时方法识别用户会话，假如两页间恳求时间的差值超过一定的界限(超时阈值)就认为用户开场了一个新的会话。途径补充是由于本地缓存和代理效劳器缓存的存在，使得效劳器的日志会遗漏一些重要的页面恳求。途径补充就是将这些遗漏的恳求补充到用户会话中，解决的方法类似于用户识别中的方法。事务识别，用户会话是eb日志挖掘中唯一具备自然事务特征的元素，但是，对于某些挖掘算法来说可能用户会话的粒度太大，需要利用分割算法将其转化为更小的事务。一般通常采用图1所示的数据预处理过程。假如按照前面所介绍的日志预处理技术对eb日志进展预处理，

6、那么Frae页面和其SubFrae页面也将一起出如今用户会话文件中。在这样的用户会话文件上进展数据挖掘，Frae页面和SubFrae页面作为频繁遍历途径或者频繁访问页组出现的概率很高，并且他们同时出如今挖掘结果中，这就降低了挖掘结果的兴趣性。图1典型的eb日志数据预处理过程2.2Frae页面过滤预处理技术HTL标准通过“Frae标记支持多窗口页面，每个窗口里装载的页面对应一个URL。当用户恳求Frae页面的URL时，Frae页面和其中的SubFrae页面作为一个多窗口页面展如今用户面前，我们可以将用户对Frae页面的恳求看成就是对多窗口页面的恳求。这样，在数据预处理阶段将Frae页面和其中的S

7、ubFrae页面作为一个整体考虑，并且把Frae页面对应的URL当作这个整体的代表。从全局而言，这样处理可以有效地消除Frae页面对日志挖掘的影响，最终进步挖掘结果的兴趣性。图2改良的eb日志数据预处理过程为此，我们对图1中描绘的常用的eb日志数据预处理技术进展相应的改良，图2是改良后的数据预处理过程。改良的eb日志数据预处理过程中，在会话识别与途径补充这两个步骤之间增加了Frae页面过滤。Frae页面过滤要完成的任务是，根据从站点的拓扑构造中提取出的Frae-SubFrae关系表，从会话识别过程中生成的会话文件中，寻找Frae页面及其SubFrae页面，将会话文件中对Frae和其SubFra

8、e页面的恳求用Frae页面代替，从而删除会话文件中多余的SubFrae页面。由于删除了会话文件中的SubFrae页面，因此会丧失SubFrae页面中包含的超链接信息，所以接下来的途径补充步骤中必须使用提升的站点构造。如上文所述，我们应用Frae页面过滤技术有效地消除了Frae页面对日志挖掘的影响，然而我们知道eb日志挖掘的记录是成千上万的，上述Frae页面过滤算法中是对每个用户对话的每个页面进展是否Frae和SubFrae的判断，并且对判断出的子框架逐个地进展删除，而且因为SubFrae页面的删除导致后面必须用提升的站点构造，虽然较一般预处理技术增加了兴趣度，但是效率还是比拟低的，而且也增加了

9、开销。并且SubFrae过滤中被删去，在后面的途径补全中能否完全恢复也值得高榷。而且有快速分类性质允许多粒度层的决策树分类算法可以解决此问题。本文在此用决策树算法13中著名的ID3算法对进步Frae过滤效率进展了一些讨论3.1ID3算法13的描绘ID3算法的根本思想是贪心算法，采用自上而下的分而治之的方法构造决策树。首先检测训练数据集的所有特征，选择信息增益最大的特征A建立决策树根节点，由该特征的不同取值建立分枝，对各分枝的实例子集递归，用该方法建立树的节点和分枝，直到某一子集中的数据都属于同一类别，或者没有特征可以在用于对数据进展分割。算法描绘如下：算法：Generate-deisin_tr

10、ee由给定的训练数据集产生一棵决策树。输入：训练样本Saples，由离散值属性表示；候选属性的集合attribute_list输出：一棵决策树方法：1)创立结点N2)ifSaples都在同一类then3)返回N作为叶结点，以类标记;4)ifattribute_list为空then5)返回N作为叶结点，标记为Saples最普通的类；/使用多数表决。6)选择attribute_list中具有最高信息增益(关于信息增益的求法请参见文献3)的属性test_attribute;7)标记结点N为test_attribute;8)freahtest_attribute中值ai/划分Saple;9)由结点N长

11、出一个条件为test_attribute=ai的分枝；10)设Si是Saple中test_attribute=ai的样本集合/一个划分11)ifSi为空then12)加上一个树叶，标记为Saples中最普通的类；13)else加上一个由Generate_deisin_tree(Si，attribute_list_返回的结点3.2基于ID3算法的Frae页面过滤算法与效率分析输入：FS表PidFrae，PidSubFrae对的集合;侯选属性的集合attribute_list(包括index.htl，tp.htl，left.htl，ain.htl)输出：一棵断定树freahusersessinus

12、erid，pid1，pid2，pidkurrentFrae=nullake_nde(eb)if(urrentFrae，Pidi)FS)ake_tree(urrentFrae，eb_left)elseif(PidiD(FS)urrentFrae=Pidiake_deitin_tree(urrentFrae，eb_right)elseake_deisitn_tree(urrent，eb_left)ifattribute_list=nullake_deitin_tree(urrentFrae，eb_right);elseifGain(nefattribute_list)allgain(attribu

13、te_list);/Gain()为信息增益函数urrentFrae=test_attribute;fraifeahtest_attributeifnt(test_attribute=ai)ake_desitin_tree(ai，eb_left)elsegenerate_deisin_tree(ai，eb_right)我们在这里认为网页上每个页面都是eb页面，所以它的信息增益最高，因此以它为根结点。urrentFrae变量记录了当前处理的页面，假如当前页不是Frae页面时那么将其添到左子树中，否那么，即PidiD(FS)，那么将当前页面的标识符Pidi赋给urrentFrae，并将其添加到右子树

14、中，且将它包含的SubFrae页面仍添加到左子树中。因为我们感趣的页面是Frae页面，所以它的点击率最高，其信息增益最大，因此我们将信息增益最大的总是添加到eb右子树中，而当前页不符合Frae页面属性的就是SubFrae页，将其添加到左子树中。这样，决策树的右枝就是Frae，左枝就是SubFrae.很容易就完成了会话识别，并且因为SubFrae并没有被删去，因此在后面的途径补充中将其复原就可以了。较之Frae过滤算法，此算法略去了提升站点构造这一步，因此更大地进步了进步了日志数据预处理的速度及预处理结果的质量。3.3数据分析用长度为9B的日志，其中包含10万条记录。日志数据中有417个不同的H

15、TL页面，从中识别出1902个用户会话。通过挖掘频繁访问页组比拟一般数据预处理技术Frae页面过滤预处理技术和基于ID3页面过滤预处理技术。其算法比拟如下表方法绝对支持度|FG1|FG2|FG3|FG4|FG5|FG6|FG7|一般技术7023578060243*6024779465254*Frae改良技术302331162+155510072203+基于ID3的Frae改良技术20243110+11065755510+说明：绝对支持度：指包含频繁访问页组的最小用户会话个数|FGi|：长度为i的频繁访问页组的数目*：表示发现的频繁访问页组是用户不感兴趣的+：表示发现的频繁访问页组是用户较感兴趣的+：表示发现的频繁访问页组是用户感兴趣的上述数据说明，通过在eb日志预处理阶段增加ID3算法进展Frae过滤步骤后，其日志数据预处理结果的质量比一般技术及Frae改良技术都高，因此更大程度地进步了挖掘结果的兴趣性。而且由于算法本身的性质及在途径补充步骤中减少了提升站点构造这一步，因此也极大地进步预处理的效率，并由此搞高了整个eb日记挖掘的效率。文中用决策树算法中的ID3算法改良了Frae过滤算法。经历证，在通过过滤原始日志数据中阅读器自动在显示Frae页面时向效劳器恳求的SubFrae页面，对存在Frae页面的网站施行eb日志挖掘算法时，基于ID3算法的Frae页面过滤技术进一步进步了对