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

1、基于ID3算法Web日志挖掘预处理中Frame页面过滤技术     摘  要  描述了Web日志数据预处理技术的一种改进技术Frame过滤技术，对其关键部分与运作模式进行了研究与改进。讨论了Frame页面过滤预处理技术在Web页面挖掘中的效率问题，分析了决策树算法中最著名的算法ID3算法，并用ID3算法对Frame过滤算法进行了改进，比较新旧算法的执行效率及算法结果质量，得出了新算法执行效率更高及质量更好的结论，从而搞高了对存在Frame页面的网站实施Web日志挖掘算法时挖掘结果的兴趣度。    

2、; 关键词  ID3算法；Web日志挖掘；Web日志预处理;Frame页面过滤      1  引言     Internet的迅速发展使得Web为人们提供了内容丰富且数量庞大的信息，随着数据挖掘技术的出现以及发展，数据挖掘逐渐被应用于Web数据。     Web日志挖掘是三大类Web挖掘之一，它主要包括数据预处理和挖掘算法实施两个主要阶段.实施挖掘算法之前要对Web日志文件进行预处理，将其转化为用户会话集.本文着重讨论Web日志挖掘预处理技术中的Frame页面过滤

3、预处理技术，即在传统的Web日志预处理过程中加入Frame页面过滤这一步骤，并提出了用决策树算法著名的ID3算法进行Frame页面过滤，进一步提高了日志数据预处理的质量和效率，从而为挖掘算法的实施提供更为准确的数据，提高了对存在Frame页面的网站实施Web日志挖掘算法时整个Web日志挖掘的效率及挖掘结果的兴趣性。 2  Web日志预处理中的Frame页面过滤技术2 2.1  Web日志预处理技术现状     Web日志挖掘1 34是指将数据挖掘技术应用于Web服务器日志文件，以发现隐藏在其中的用户访问模式。Web日志预处理是在Web日志挖掘前

4、，对Web日志进行清理、过滤以及重新组合的过程，其目的是剔除日志中对挖掘过程无用的属性及数据，并将Web日志数据转换为挖掘算法可识别的保存形式。     到目前为止提出的Web日志的预处理技术，它包含三种方法识别用户的活动集合：     (1) Web服务器提供Cookie，则具有相同Cookie值的页面请求是来自同一个用户，则用户会话识别的主要的任务就是将Web日志划分为不同Cookie值所对应的页面请求集合。     (2) Web服务器没有提供Cookie，但每个网站用户都要一个登录标识符方可访问站

5、点，则分析工具即可利用登录标识符识别会话。        如果Web服务器既没有Cookie也没有登录标识符，可以利用主机地址，同时分析日志中每条记录的请求页和引用页的URL，然后根据Web站点的拓扑结构（超链接）和其它启发式规则识别用户会话，但是这种方法的精确度较低，不能100正确地识别出每个请求对应的用户。 这里主要讨论第3种预处理方法。     一般Web日志预处理主要包括：数据净化、用户识别、会话识别、路径补充、事务识别 数据净化指删除Web服务器日志中与挖掘算法无关的数据。由于在Web日志中通常

6、只有HTML文件与用户会话相关，所以通过检查URL的后缀删除不相关的数据。     用户识别是指要识别出每个访问网站的用户。一般Web日志挖掘工具中常使用基于日志/站点的方法，并辅助一些启发式规则帮助识别用户。     会话识别是将用户的访问记录分为单个的会话。通常采用超时方法识别用户会话，如果两页间请求时间的差值超过一定的界限(超时阈值)就认为用户开始了一个新的会话。     路径补充是由于本地缓存和代理服务器缓存的存在，使得服务器的日志会遗漏一些重要的页面请求。路径补充就是将这些遗漏的请求补充到用户会

7、话中，解决的方法类似于用户识别中的方法。 事务识别，用户会话是Web日志挖掘中唯一具备自然事务特征的元素，但是，对于某些挖掘算法来说可能用户会话的粒度太大，需要利用分割算法将其转化为更小的事务。     一般通常采用图1所示的数据预处理过程。     如果按照前面所介绍的日志预处理技术对Web日志进行预处理，则Frame页面和其SubFrame页面也将一起出现在用户会话文件中。在这样的用户会话文件上进行数据挖掘，Frame页面和SubFrame页面作为频繁遍历路径或者频繁访问页组出现的概率很高，并且他们同时出现在挖掘结果中，这就降低了

8、挖掘结果的兴趣性。    图1  典型的Web日志数据预处理过程    2.2  Frame页面过滤预处理技术     HTML规范通过“Frame”标记支持多窗口页面，每个窗口里装载的页面对应一个URL。  当用户请求Frame页面的URL时，Frame页面和其中的SubFrame页面作为一个多窗口页面展现在用户面前，我们可以将用户对Frame页面的请求看成就是对多窗口页面的请求。这样，在数据预处理阶段将Frame页面和其中的SubFrame页面作为一个

9、整体考虑，并且把Frame页面对应的URL当作这个整体的代表。从全局而言，这样处理可以有效地消除Frame页面对日志挖掘的影响，最终提高挖掘结果的兴趣性。    图2 改进的Web日志数据预处理过程     为此，我们对图1中描述的常用的Web日志数据预处理技术进行相应的改进，图2是改进后的数据预处理过程。     改进的Web日志数据预处理过程中，在会话识别与路径补充这两个步骤之间增加了Frame页面过滤。Frame页面过滤要完成的任务是，根据从站点的拓扑结构中提取出的Frame-SubFra

10、me关系表，从会话识别过程中生成的会话文件中，寻找Frame页面及其SubFrame页面，将会话文件中对Frame和其SubFrame页面的请求用Frame页面代替，从而删除会话文件中多余的SubFrame页面。由于删除了会话文件中的SubFrame页面，因此会丢失SubFrame页面中包含的超链接信息，所以接下来的路径补充步骤中必须使用提升的站点结构。 3  基于ID3算法的Frame页面过滤预处理技术     如上文所述，我们应用Frame页面过滤技术有效地消除了Frame页面对日志挖掘的影响，然而我们知道Web日志挖掘的记录是成千上万的，上述Fra

11、me页面过滤算法中是对每个用户对话的每个页面进行是否Frame和SubFrame的判断，并且对判断出的子框架逐个地进行删除，而且因为SubFrame页面的删除导致后面必须用提升的站点结构，虽然较一般预处理技术增加了兴趣度，但是效率还是比较低的，而且也增加了开销。并且SubFrame过滤中被删去，在后面的路径补全中能否完全恢复也值得高榷。而且有快速分类性质允许多粒度层的决策树分类算法可以解决此问题。本文在此用决策树算法1 3中著名的ID3算法对提高Frame过滤效率进行了一些探讨  3.1  ID3算法1 3的描述     ID3算法的基本思想是

12、贪心算法，采用自上而下的分而治之的方法构造决策树。首先检测训练数据集的所有特征，选择信息增益最大的特征A建立决策树根节点，由该特征的不同取值建立分枝，对各分枝的实例子集递归，用该方法建立树的节点和分枝，直到某一子集中的数据都属于同一类别，或者没有特征可以在用于对数据进行分割。     算法描述如下：     算法：Generate-decision_tree 由给定的训练数据集产生一棵决策树。     输入：训练样本Samples，由离散值属性表示；候选属性的集合attribute_list  

13、   输出：一棵决策树     方法：     1)           创建结点N     2)           if Samples 都在同一类C then     3)       

14、;    返回N 作为叶结点，以类C标记;     4)           if attribute_list为空  then     5)           返回N作为叶结点，标记为Samples最普通的类；/使用多数表决。     6)  &

15、#160;        选择 attribute_list中具有最高信息增益(关于信息增益的求法请参见文献3)的属性test_attribute;     7)           标记结点N 为test_attribute;     8)           for

16、 each test_attribute 中已知值ai /划分Sample;     9)           由结点N长出一个条件为test_attribute=ai的分枝；     10)        设Si是Sample 中test_attribute=ai 的样本集合/一个划分     11)   

17、     if Si 为空  then     12)        加上一个树叶，标记为Samples中最普通的类；     13)        else 加上一个由Generate_decision_tree(Si， attribute _list_返回的结点 3.2  基于ID3算法的Frame页面过滤算法与效率分析  

18、   输入：FS表（PidFrame ， PidSubFrame）对的集合;侯选属性的集合attribute_list(包括index.html，top.html，left.html，main.html)     输出：一棵判定树 for each user session <userid，pid1，pid2，pidk>    currentFrame=null make_node(Web) if(currentFrame， Pidi) FS )  make_tree(currentFrame，Web_

19、left) else if(PidiDom(FS) currentFrame= Pidi make_decition_tree(currentFrame，Web_right) else make_decisiton_tree(current，Web_left) if attribute_list=null make_decition_tree(currentFrame，Web_right); else if Gain(one of attribute_list)>allgain (attribute_ list); /Gain()为信息增益函数 currentFrame=test_att

20、ribute; for ai of each test_attribute if not(test_attribute= ai) make_desition_tree(ai，Web_left) else generate_decision_tree(ai，Web_right)       我们在这里认为网页上每个页面都是Web页面，所以它的信息增益最高，因此以它为根结点。CurrentFrame变量记录了当前处理的页面，如果当前页不是Frame页面时则将其添到左子树中，否则，即PidiÎDom(FS)，则将当前页面的标识符Pidi赋给Curre

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

22、    用长度为9MB的日志，其中包含10万条记录。日志数据中有417个不同的HTML页面，从中识别出1902个用户会话。通过挖掘频繁访问页组比较一般数据预处理技术Frame页面过滤预处理技术和基于ID3页面过滤预处理技术。其算法比较如下表    方法    绝对 支持度    |FG1|    |FG2|    |FG3|   

23、0;|FG4|    |FG5|    |FG6|    |FG7|    一般技术    70    23    57    80    60    24   

24、0;3*    0    60    24    77    94    65    25    4*    0    Frame 改进技术    30

25、0;   23    31    16    2+    0    0    0    15    55    100    72   &#

26、160;20    3+    0    0    基于ID3的 Frame改进技术    20    24    31    10+    1    0    0    0    10    65    75    55    10+    0    0