《基于WEB日志的连续频繁路径挖掘算法毕业论文.doc》由会员分享，可在线阅读，更多相关《基于WEB日志的连续频繁路径挖掘算法毕业论文.doc（13页珍藏版）》请在三一办公上搜索。
1、基于 w e b日志的多元线性回归连续频繁路径挖掘算法1 引 言 we b站点的日志数据记录了用户浏览 we b站点时的大量路径信息，对这些信息的分析有利于网站设计人员掌握用户的爱好和习惯，网站设计人员可以用来对网站的结构进行优化和页面重组基于web日志，研究频繁浏览路径已成为 web日志挖掘的热门课题目前的挖掘算法主要集中在以下几个 问题展开： 1.采用什么值作为算法的最基本分析依据，有些算法利用浏览次数作为研究依据 ，求得的浏览路径不全面；有些算法虽考虑到了浏览时间、 浏览次数及浏览内容的长度等因素，采用兴趣度作为算法基本要素， 但兴趣度定义比较模糊，不能准确说明用户对网页感兴趣程度； 2
2、.采用何种存储结构表示 web日志数据文件；有些算法基于矩阵实现挖掘，算法无法表现可重复浏览路径等等首先考虑 web 日志中浏览次数,浏览时间和浏览接收字节数等因素，采用线性回归的方式计算用户的浏览兴趣度，得到更全面的兴趣度其次采用树存储日志中的重复、连续、回溯路径，即只需访问一次数据库，建立完整的浏览路径树最后采用倒序单子树序列口求得频繁路径本文基于web日志提出一种新的频繁路径的挖掘算法首先以线性回归方法求解兴趣度，其次将此兴趣度和页面名称作为最基本要素，建立的web浏览树，此浏览树可以完整地表现出w eb日志中连续、重复的浏览路径，最后在we b浏览树上进行分析挖掘频繁浏览路径。该算法经
3、实验证明能更全面地反映用户兴趣所在，挖掘的频繁浏览路径准确、合理2 算法相关描述 2 .1 线性 回归兴趣度 2 .1 .1 问题提出 对 web日志中频繁路径的挖掘首先取决于兴趣度的大小，目前用户浏览兴趣度的求法大 多采用兴趣度浏览时间*浏览次数浏览字节数的方法，这样的兴趣度公式 不确切、不全面，说明力不够求得的浏览兴趣度值差异较大，不易发现其规律由 w e b日志，我们得知用户对网页感兴趣程度与浏览时间、浏览次数、浏览字节数有关,经实验计算分析，兴趣度与web日志中的三要素线性相关 2 .1.2 解决方法 线性回归方法是一种数学优化技术 ， 它通过最小化误差的平方和找到一组数据的最佳函数
4、匹配本文利用线性回归误差小，数据计算精度高的特点，计算的兴趣度值更符合实际,能为下一步建立浏览树提供更可信的数据 本文设定浏览兴趣度为因变量 y，浏览次数、浏览时间、浏览字节数分别为自变量 ，采用最小二乘法理论得到多元线性回归方程数学模型为由给定的数据库中一部分数据，求得线性回归系数因而确立回归方程建立了回归方程后，进行显著性检验，确认建立的回归模型是否很好地拟合了原始数据，即回归方程是否有效，利用残差分析，确定回归方程是否违反了假设理论检验回归方程有意义后，利用回归方程进行兴趣度的预测本文中，所有自变量都可由w e b日志得到，但因变量兴趣度y不能直接得到,于是首要问题是得到固定的y值兴趣度
5、即用户对 网页感兴趣 的程度，兴趣度通常可以大致分为四种情况：特别感兴趣， 一般感兴趣，偶尔感兴趣，不感兴趣每种情况均表示一个范围，故不能将其直接定义为某一个具体的数值 我们可以将其按百分制的形式欲以离散化赋值(由实验计算设定经验值) ： 定义用户最感兴趣的页面的兴趣度为100 ，其他类兴趣度的取值范 围分别为80以上 ，4 0 8 0 ，2 0 40 ，10 一20.在线性回归方程中，兴趣度值主观设定为每个兴趣度类别的中间值效果较好利用LINEST函数计算求得线性回归方程验证有效后,将web日志数据代入线性回归方程， 完成每个浏览页面的浏览兴趣度的预测和计算 2 .2 web浏览树 本文中w
6、eb浏览树完整记录了web日志的浏览路径信息，树中的每一个结点都是一个浏览页面，每个结点都包括页面内容和页面浏览兴趣度，树中的每棵子树都是沿着同一路径浏览的序列树中的每一条路径上的结点都可以重复、连续出现,解决了以往路径单一的问题 web浏览树结构描述见图1 2 .3 web浏览树的生成 建立web浏览树是整个算法的基础 web浏览树从根结点R开始， 每添加一个结点时，沿不同路径先查找是否结点已在树中存在 ，没查找到相应结点，则在此路径中查找到的结点下添加一个新的儿子结点对于查找到的结点,比较兴趣度,由不同需求可以生成三棵不同浏览树 若选取结点兴趣度最小的，可以生成严格浏览树；若选取结点兴趣度
7、最大的,可以生成理想浏览树；若取兴趣度平均值，可以生成一般浏览树这样生成的浏览树可以从不同角度反映用户浏览网页情况,使整个算法更有实用价值 算法1 描述了一般浏览树的生成算法.以下实例均以一般浏览树为例 算法1 web浏览树生成算法 输人 ： web日志转换成的数据表。 输出 ： we b浏览树 算法具体描述： 假定w eb日志数据库中有n条记录，算法l需扫描一次数据库 ， 生成web浏览树 ， 时间开销为0( n ) 文献 7 建立访问树仅表现浏览页面在web日志记录中出现次数,不能准确反映用户的真实兴趣本文综合web l og s中的浏览次数 ，浏览时间和接收字节数等信息增加了一个兴趣度属
8、性,使用户可以在生成浏览树的同时，就可以一目了然该页面的兴趣度值 ，可视性好也为下一步挖掘全面的、合理的频繁路径奠定基础 例1. 部分浏览记录如表1所示 生成的一般web浏览树如图2所示 2 .4 倒序单子树序列表生成 本文频繁路径的挖掘算法不以整个浏览树为分析依据，而是将浏览树中的每一棵子树转化为倒序单子树即从浏览树的叶子结点出发，倒序产生从叶子到根的不同子树单序列本算法中不用浏览次数作为分析频繁路径的依据，故不用生成Ta b邻接表,简化了算法,缩短算法时间例2 .生成图2所示的we b浏览树的倒序单子树序列，如图3所示 2 .5 RT树生成 在浏览页面的过程中，每一条浏览路径中的每个页面的
9、兴趣度会随着页面的不断重复、 回溯而发生变化，在倒序单子树序列的基础上形成RT树，重新确定了单子树上每个结点的兴趣度值RT树综合每个单子树序列，分别生成以每个结点为根的子树 算法2 .RT树生成算法 输人：倒序单子树序列 输出：RT树 算法具体描述： 生成的RT树是判断频繁路径的直接依据，RT树上结点的兴趣度为最终的兴趣度，根据给定的兴趣度闽值，确定最后的频繁路径假定倒序单子树序列个数为 m，浏览的页面个数为，算法2的时间开销为O( m * n ) 本文在算法上进行了改进，生成的 RT树是根据兴趣度生成的，故不用计算浏览次数总和，没必要再合并 R T树，因此简化了算法 例3生成图3中每个结点的
10、 RT树( 以结点A为例 ) 。结点 A 的RT树如图4所示遍历图 4的RT树，根据给定的兴趣度阈值，即可挖掘出所需要的频繁路径( 设兴趣度阈值为5 0 ) ，以结点A为后缀的频繁路径即为 ( ACA) ，( C A) 3 算法实现 本文以某大学 0 8年5月1日1 9点到 20点 8 0个用户I P 的web日志记录为原形 ， 用 CP U：I n t e l P e n t i u m p r o c e s s o r 1 .7 GHz内存：1.2 1 GB的笔记本在windows x p平台上用c#语言实现了本文的算法 3. 1 兴趣度的计算过程 3 .1.1 确定因变量兴趣度y值 本
11、文以大写字母映射页面名称，首先用EXCEL2003求得页面兴趣度.以页面的日志情况作为线性回归方程的原始参考数据 首先，分类原始的日志记录，并汇总计算各页面记录中与兴趣度相关的浏览次数,浏览时间,接收字节数的的平均值 平均值：A：c o u n t ：1.7 7 3 3 3 ；t i me:4 7 .5 6 8 8；s b s：2 9 .7 其次，计算各页面所占平均值的比重，这样可以反映不同用户在相同页面的不同偏爱程度部分页面的比重值见表 2 再次，计算兴趣度由实验计算设定经验值：浏览次数，浏览时间和接收字节三项比重值 (表2 ) 都大于1 .5 ,用户对此页面特别感兴趣,兴趣度值设定为9 0
12、； 三项比重值 中两个及两个以上大于1且小于1 .5 ，用户对页面一般感兴趣，兴趣度设定为60；三项比重值中两个及两个以上大于 0.5且小于1,用户对页面偶尔感兴趣,兴趣度设定为3 0；三项值都小于0 .5 ,兴趣度设定为1 03. 1 .2 线性回归方程的建立由Excel中 函数求得线性回归系数，结果如表3所示 待添加的隐藏文字内容2其第一行为所求的线性回归系数求得的线性回归方程为判定系数为 08 4 5 9 6 9 ，自由度为 7 1 ，回归平方和为2 7 4 7 03 1，残差平方和为5 0 0 1.6 9 33 .1 .3 检验线性方程线性是否显著 本文采用显著性检验一F检验来实现检验
13、判定浏览次数、 浏览时间和接收字节数与页面浏览兴趣度的相关性程度 ， 进而准确判定线性模型准确与否 对应 F分布表 ， 我们可以确定在 ( a =0 0 5) 下 ， 线性关系成立 ( 过程略 ) 3.1.4 兴趣度误差说明( 图 5 ) 用于预测的估计兴趣度值均为离散化后各兴趣度范围的平均值 ，如估计值为6 0，预测值 在 40到8 0之 间 、估计值为3 0 ，预测值在 2 0到4 0之间等等都是正确的图5是通过页面预测c页面得到的预测兴趣度与估计兴趣度的误差图 从中可以看出，只有少数估计值为 9 0 的预测值与估计值不符即数据偏差较大的项均集中在兴趣度设定值为9 0，对该页面的感兴趣度是
14、特别感兴趣时，这是由于对某一页面非常感兴趣的人数相对于其它类感兴趣的人数较少的缘故当浏览时问接收字节数和浏览次数中某个数值较大时，也易出现数据偏差 4 算法分析与比较 4.1 时间复杂性分析 本算法只需扫描一次数据库，假定数据库有I个序列，则建立 w e b浏览树的时间开销为O( L)，we b浏览树中以频繁1项集为后缀的序列个数为0 ,在倒序单子树序列上建立 n棵 R T树，建立每棵RT树的时问开销为O( 0 )，则整个算法 的时间开销为O( L) +n* O( ) 本文不用建立邻接表和合并R T树，显然会比文献7 3 时间开销小 4.2兴趣度比较 本文给定的兴趣度本身就能反映用户对页面的感
15、兴趣程度，给定一个阈值求得的频繁路径可以反映出是不同兴趣 程度类别中不同的用户的频繁路径，具有一定的代表性 表5以一般浏览树为例，给定两个不同的兴趣度阈值，I为文献 6 的实验结果， 此阈值不能代表用户对页面感兴趣程度I 1为本文的实验结果，P； 一40,此阈值40是用户对页面一般感兴趣的最低值，由此求得的频繁路径是对用户一般感兴趣和特别感兴趣的两类页面而言的，有利于有针对性地进行下一步分析页面，提高页面的利用率 表4中每一条路径反映的是以该结点为后缀的频繁路径，例如表中算法I I的结点A下的 BA路径，实际上是以A 为后缀的由A到B的路径 基于本文的数据库，和于本文来说都是较低的阙值，由此得
16、到的频繁路径应该是普遍值，能反映最大众的路径情况但显而易见，算法I得到的结果比较狭隘，不能将频繁路径全部、真实再现43 结果分析：在效率和准确性上的比较 本文不用生成邻接表，不用合并B T树，因而在算法结构上更细致，更准确地挖掘出不同用户群的连续、可回溯的频繁路径。由于页面结点，得到的路径 比较纷繁，故在此仅以一个结点为例进行比较，这样得到的结果图比较清晰， 容易说明问题,但不影响整个比较效果。给定阈值设为P ，下图列举出结点D在较小的闽值下由文献 7 与本文一般浏览树下生成 的频繁路径 ( 图 6 ,7 ) 图6和图7均在 较小的阈值进行分析，旨在使得到的结果反映出两个文献中最易生成 的路径
17、而本文综 合考虑web日志中影响兴趣度的因素，在本表中虽只以一般浏览树为例，却真实地反映了感兴趣程度不同的用户浏览的频繁路径,得出的路径主要集中在A、 B、C、 D页面，体现出频繁性，实验结果细腻，有研究价值 浏览we b页面的行为不具规律性偶然性大反映在web日志中即影响兴趣度的某一个因素值可能出现极端，本文采用线性回归的方式计算兴趣度，即使某一个因素值较大或较小，都不会直接影响最终结果因此针对一般和特殊的web日志,本文算法都可以适用;另外本文可产生三种不同的浏览树，由此三种浏览树不但可以很好地挖掘出大多数用户较大众的一般性兴趣及频繁路径，而且对于少数用户的极端兴趣度下的浏览路径也可同样进
18、行 充分 分析，产生极低兴趣度和理想兴趣度下的频繁路径，完善了算法功能,扩展性能好 本文采用窗体形式实现了算法的可视化，数据库的显示与否可以由用户根据需求自行设定，显示数据库，方便用户在操作过程中及时对应， 及时检验 增强了算法的可操作性、 可读性灵活性5 结束语 本文提出了一种基于web日志新的频繁路径的挖掘算法算法首先用线性回归方式求解兴趣度，这是一种全新的尝试，线性回归的兴趣度的计算方法笔者将作进一步研究然后由兴趣度作基本元素，根据不同需求可生成三种不同浏览树，不但从不同视角真实、全面地反映 w e b日志中的用户兴趣，同时解决了连续、可重复的路径的挖掘问题实验证明，本算法合理有效,可扩展性好
