南京财经大学本科毕业论文
目 录
摘要 1
关键词 1
Abstract 1
Keywords 1
一、Web日志挖掘 2
（一）、数据预处理 2
（二）、模式发现 4
（三）、模式分析 5
二、关联分析 5
（一）关联规则 5
（二）Apriori方法简介 7
四、实证分析 8
（一）数据预处理 8
（二）模式发现 9
（三）模式分析 10
五、个性化推荐 11
六 、结束语 12
参考文献 13
附录 15
基于关联分析的Web日志挖掘
摘要:web日志挖掘是web数据挖掘中的一个重要组成部分，通过从Web访问日志中发现用户的访问模式，预测用户的浏览行为。本文主要介绍了web数据挖掘的一般过程及方法，对Apriori关联分析方法作了重点阐述，并利用该方法对某网站某天的部分web日志数据进行了实证分析，得出了用户浏览模式及网页内容之间的关联规则，找到单个用户在浏览页面兴趣爱好以及群体用户的浏览习惯，继而对网站的网页规划布局提出了个性化的意见。
关键词:web日志挖掘;关联分析;实证分析
Web Log Mining Based On Association Analysis
Abstract: Web log mining is an important part of web data mining, finding the user's access pattern in the Web access logs ,the researcher can predict the user's browsing behavior. This essay introduces the method of Association analysis in Web log mining,espacally the method of Apriori， at the same time ,we use this method to analysis a particular site’s log data to find the users’ browsing patterns and association rules between web pages ;It also finds the browsing interest of a single user and groups users’ browsing habits, all after then ,we put forward some individual suggestions on web planning.
Keywords: Web log mining; Association analysis; Positive analysis
随着WWW在深度和广度上的发展，Internet也前所未有地改变着我们的生活，数据信息已经在这个时代爆炸了。但是，我们又不得不面对“人们被数据淹没,人们却饥饿于知识”的现实。随着兴起与20世纪80年代末的数据挖掘在web上的应用，从某种程度上改善了上述情况。根据所挖掘的Web 数据的类型，可以将Web 数据挖掘分为以下三类：Web 内容挖掘(Web Content Mining)、Web 结构挖掘(Web Structure Mining)、Web 使用挖掘(Web Usage Mining)（也称为Web日志挖掘）。Web日志挖掘是指采用数据挖掘的技术，通过对Web服务器日志中大量的用户访问记录深入分析，发现用户的访问模式和兴趣爱好等有趣、新颖、潜在有用的以及可理解的未知信息和知识，用于分析站点的使用情况，从而辅助管理和支持决策。当前，web日志挖掘主要被用于个性化服务与定制、改进系统性能和结构、站点修改、商业智能以及web特征描述等诸多领域。
一、Web日志挖掘
Web日志挖掘主要是通过对web浏览的日志数据的分析，发现用户的浏览模式，更好地规划站点。
下面是一段日志：① 2006-10-17 00:00:00② ③ 80 ④ GET ⑤/ ⑥ Mozilla/+(Windows；+U；+Windows+NT+；+zh-CN；+rv：)+Gecko/20060426+Firefox/。主要包括：①访问时间；②用户IP地址；③访问的URL，端口；④请求方法(“GET”、“POST”等)；⑤访问模式；⑥agent，即用户使用的操作系统类型和浏览器软件。
Web日志挖掘一般都包含以下几个过程：
（一）数据预处理
数据预处理是Web 日志挖掘的首要环节, 其任务是将原始日志数据转换成适合数据挖掘和模式发现所必需的格式, 预处理可以直接简化数据挖掘过程，使结果更具客观性。数据预处理包括数据净化、用户识别、会话识别、路径补充四个步骤。
1．数据净化
数据净化, 是指将待处理的日志数据导入到关系数据库,删除Web日志数据中的错误值、缺失值等，同时把与Web数据挖掘无关的变量或数据进行清理，已达到简便运算的目的；
2.用户识别
用户识别, 是从Web日志数据中找出每个用户的访问地址，避免挖掘的重复性。目前, 由于本地缓存、代理服务器和防火墙的存在, 为用户动态的分配IP 地址, 想要识别出每一个用户变得很复杂。可以通过以下 3 种方法来识别用户:
( 1) 如果Web 服务器提供Cookie , 则具有相同Cookie 值的页面请求是来自同一个用户;
( 2) 如果Web 服务器没有提供Cookie , 但每个网站用户都要一个登录标识符( 用户ID) 方可访问站点, 则利用登录标识符识别用户;
( 3) 如果Web 服务器既没有Cookie 也没有用户ID,最常用的方法就是采用启发式规则。根据我们的日志格式采用两条启发式规则：①不同的IP地址代表不同的用户；② 如果IP地址相同，但是操作系统类型或者浏览器软件不同我们认为是不同的用户。
3.会话识别
会话, 是指同一个用户连续请求的页面。在跨越时间区段较大的Web 服务器日志中, 用户可能多次访问该站点。会话识别的目的是将用户的所有访问序列分成单个的访问序列。常用的算法有以下几种:
（1）对用户在整个网站的停留时间设一个阈值T。如果两个相邻的浏览页面之间的访问时间超过T, 则认为用户又开始了一个新的会话。一般T取30min。
（2）对用户在一个页面停留时间设一个域值△t。如果2 个连续请求的时间间隔没有超过这个值△t, 则属于同一会话。否则, 分属于两个会话。△t 一般取10min。
（3）利用用户的访问历史和引用页来划分。如果一个用户的请求不能通过引用页的链接进入, 则属于另一个会话。
（4）最大向前引用算法( MF) 。设一个用户会话里不会出现用户以前已经访问过的页面, 如果用户在向前浏览到一个网
4. 路径补充
用户会话对数据挖掘来讲，显得粗糙，仍不够精确，需把会话进一步分成具有一定语意的事务，如同篮子数据中顾客一次购买的商品。可以把Web页简单地分为两类：内容页和导航页。在编程中采用的区分导航页和内容页的方法是时间点法，即设定一时间值，实际中时间点的取值为30秒。当用户对该网页访问的时间小于时间点为导航页，大于时间点则为内容页。用户对网页的访问时间为用户前后两次访问该网页的时间差，通过调用SQL语句可以查找到用户访问网页的时间，进而区分出导航页和内容页。
（二）模式发现
模式发现, 是对预处理后的数据用数据挖掘算法来分析数据。分有统计、分类、聚类、关联规则、路径分析等多种方法。
（1）统计。统计方法是从Web 站点中抽取知识的最常用方法, 它通过分析会话文件, 对浏览时间、浏览路径等进行频度、平均值等统计分析。虽然缺乏深度, 但仍可用于改进网站结构, 增强系统安全性, 提高网站访问的效率等。
（2）分类。分类包括的挖掘技术将找出定义了一个项或事件是否属于数据中某特定子集或类的规则。该类技术是最广泛应用于各类业务问题的一类挖掘技术。分类算法最知名的是决策树方法，此外还有神经元网络、Bayesian分类等。
（3）聚类。聚类是将数据集划分为多个类，使得在同一类中的数据之间有较高的相似度，而在不同类中的数据差别尽可能大。在聚类技术中，没有预先定义好的类别和训练样本存在，所有记录都根据彼此相似程度来加以归类。主要算法有k—means、DBSCAN等。
（4）关联规则。关联分析的目的是挖掘隐藏在数据间的相互关系，自动探测以前未发现的隐藏着的模式，关联分析经常被表达为规则的形式。目前采用的主要关联规则挖掘算法有Apriori、FP-growth算法等。
（5）路径分析。路径分析可以用来确定网站上的频繁访问路径, 从而调整和优化网站结构, 使得用户访问所需网页更加简单快捷, 还可以根据用户典型的浏览模式用于智能推荐和有针对性的电子商务活动。
（三）模式分析
基于以上的所有过程，对原始数据进行进一步分析，找出用户的浏览模式规律，即用户的兴趣爱好及习惯，并使其可视化，为网页的规划及网站建设的决策提供具体理论依据。其主要方法有：查询、OLAP 技术和可视化技术等。
二、关联分析
（一）关联规则
顾名思义，关联规则（association rule）挖掘技术用于于发现数据库中属性之间的有趣联系。
设交易(transaction) 的集合，，这里交易是项的集合，可以表述为：并且。中的元素称为项。对应每一个交易有唯一的标识，如交易号，记作。设是数据集中所有项的集合，是二进制文字的集合。中的任何子集称为项目集(itemset)，若，则称集合为项集。设和分别为中的事务和项目集，如果，称事务包含项目集。项目集的支持率,若不小于用户指定的最小支持率(记作：minsupport)，则称为频繁项目集，否则称为非频繁项目集。设，是数据集中的项目集。若，则；若，如果是非频繁项目集，则也是非频繁项目集；若，如果是频繁项目集，则也是频繁项目集。
一个关联规则是形如的蕴涵式，这里，都是项目集，且，，并且，，分别称为关联规则的前提和结论。
一般使用支持度（support）和置信度（confidence）两个参数来描述关联规则的属性。
1.支持度
规则在数据库中的支持度是交易集中同时包含， 的事务数与所有事务数之比，记为 。支持度描述了，这两个项集在所有事务中同时出现的概率。
2．置信度
规则在事务集中的置信度(confidence)是指同时包含，的事务数与包含的事务数之比，它用来衡量关联规则的可信程度。记为
规则 A ( C:
支持度 = support({A}({C}) = 50%
置信度 = support({A}({C})/support({A}) = %
图1:支持度计算图解
（二）Apriori方法简介
Apriori算法最先是由Agrawal等人于1993年提出的，它的基本思想是：首先找出所有具有超出最小支持度的支持度项集，用频繁的(k—1)-项集生成候选的频繁k-项集；其次利用大项集产生所需的规则；任何频繁项集的所有子集一定是频繁项集是其核心。
Apriori算法需要两个步骤：第一个是生成条目集；第二个是使用生成的条目集创建一组关联规则。
1.算法伪代码
Ck: 长度为 k的候选项集
Lk : 长度为k的频繁项集
L1 = {频繁项};
for (k = 1; Lk !=(; k++) do begin
Ck+1 = 由 Lk产生的候选;
for each 数据库中的事务 t do
增加包含在t 中的所有候选Ck+1的计数
Lk+1 = Ck+1 中满足 min_support的候选
图2:Apriori算法图解
三、实证分析
本数据来源为某网站某天的全部Web日志数据。
（一）数据预处理
由于Web日志数据时一个非常庞大的数据集体，因此选用数据库作为分析工具，将原始数据导入数据库，取出前10000行日志数据，处理如下：
1.数据净化：存在缺失值的整行->删除，访问方式除GET、POST、OPTIONS以外的整行->删除；
2. 用户识别：由于数据中不存在IP地址相同，但是操作系统类型或者浏览器软件不同的情况，从而认为不同的IP地址代表不同的用户；
3.会话识别、及路径补充：用户会话被定义为用户在对网站的一次访问过程中所请求的URL的集合，若某一用户发出连续两个URL的请求的时间差不超过规定的时间阈值，则这两次请求被划分在同一用户会话中，否则分别属于两个不同的用户会话，对与本数据， 时间阈值设为30分钟。
（二）模式发现
1.描述性统计
对数据进行简单处理，得出以下描述性统计：
总用户数：1469
总链接数：146
TOP10访问页面:
/new/clubmain/newimg/, 1066;
/new/clubmain/newimg/, 1056;
/new/clubmain/newimg/,1052;
/new/clubmain/newimg/,1010;
/newimg/;873;
/newimg/,863;
/newimg/,854;
/newimg/,853;
/,453;
/new/publicforum/,329.
2. Apriori关联分析
（1）生成数据库集
从描述性统计中得到的不同用户作为数据库集的行自变量，不同的链接作为列自变量；当用户i浏览过链接j，则其对应项=1，否则=0；设置相应的覆盖要求，这样我们可以同时得到单项集合。
（2）生成关联规则
从单项集合中，生成可能的双项集合规则，分别计算置信度。
（3）结果部分
见表1:关联度计算结果表
(三)模式分析
当我们把最小置信度设为85%，通过关联规则的形成以及对应置信度的计算，我们可以从中得到以下有用的信息：
1.置信度大于最小置信度时：我们可以这样认为，用户群体在浏览相关网页时，所呈列的链接之间是有很大关联的，他们是用户群的共同爱好，通过网页布局的调整，从某种意义上，可以带来更高的点击率及潜在客户；
2.置信度小于最小置信度时：我们可以这样认为，用户群体对所呈列链接之间没太多的关联，亦或关联规则中的链接在争夺用户。
表1:关联度计算结果表
关联度
关联数
分母数
分子
分母
118
130
/newimg/
/newimg/
118
133
/newimg/
/newimg/
114
129
/newimg/
/newimg/
112
128
/newimg/
/newimg/
112
128
/newimg/
/newimg/
112
128
/newimg/
/newimg/
112
129
/newimg/
/newimg/
112
130
/newimg/
/newimg/
114
133
/newimg/
/newimg/
153
179
/new/clubmain/newimg/
/new/clubmain/newimg/
109
129
/newimg/
/newimg/
112
133
/newimg/
/newimg/
153
182
/new/clubmain/newimg/
/new/clubmain/newimg/
109
130
/newimg/
/newimg/
148
179
/new/clubmain/newimg/
/new/clubmain/newimg/
147
178
/new/clubmain/newimg/
/new/clubmain/newimg/
147
179
/new/clubmain/newimg/
/new/clubmain/newimg/
146
178
/new/clubmain/newimg/
/new/clubmain/newimg/
148
181
/new/clubmain/newimg/
/new/clubmain/newimg/
146
182
/new/clubmain/newimg/
/new/clubmain/newimg/
145
181
/new/clubmain/newimg/
/new/clubmain/newimg/
142
178
/new/clubmain/newimg/
/new/clubmain/newimg/
145
182
/new/clubmain/newimg/
/new/clubmain/newimg/
142
181
/new/clubmain/newimg/
/new/clubmain/newimg/
57
181
/
/new/clubmain/newimg/
……
……
……
……
……
（算法详见附录）
四、个性化推荐
通过以上的关联分析，有了用户频繁访问路径和链接之间的兴趣度，可以构建个性化推荐系统模型。对于以上的实证例子，我们可以在置信度高于最低置信度的相关链接之间，建立某种信息快速互联的桥梁，亦或是在网页规划中，充分考虑链接之间的关联关系，从而为更人性化、合理化的网页设计提供决策依据。如：当客户浏览/newimg/时，有的概率会浏览/newimg/，那么，在两者之间就存在很高的关联性，从而我们有必要对这两个链接建立某种跟紧密的联系。
五 、结束语
本文先研究了web日志挖掘当前研究成果，介绍了web日志挖掘的基本流程，然后着重介绍了如何利用Apririo关联规则算法来挖掘出用户频繁访问模式，找出浏览页面之间的关联规则，为个性化推荐系统模型提供了依据。
Web 日志挖掘作为Web数据挖掘的崭新研究方向,今年来已经取得了一些突破性的进展, 但是由于Web 的不确定性和多样性,以及Web的不断壮大，还有很多问题亟待解决, 有待于我们进一步去研究和探索。
参考文献
[1]．李国慧.Web数据挖掘研究.数据库与信息管理本,2008年1月12日
[2]. 王玉珍.Web数据挖掘的分析与探索[ J ].电脑开发与应用 2003年4月
[3]．张莉.基于模糊聚类的案例聚类算法研究.教育与教学研究,2009年4月第四期
[4]．苏晶.web数据挖掘的技术研究.中国新技术新产品,2008 （上）
[5]．叶苗群.web日志挖掘研究.宁波工程学院学报,2005年6月
[6]．郭欣,许林英.改进的关联的关联规则算法在电子商务中的应用.微机处理, 2008年10月5期
[7]．Richard , Michael .数据挖掘教程[M].清华大学出版社,2003版
[8]. 高哲,魏海平,王福威,赵晓碧.基于Web日志挖掘的Web文档聚类.计算机工程与设计,2008年9月
[9].王丽娜，Web 日志挖掘技术研究，光盘技术，2008年第4期
[10].张健沛,刘建东等.基于Web的日志挖掘数据预处理方法的研究[J].计算机工程与应用,.
[11].徐章艳,刘美玲,张师超等.Apriori算法的三种优化方法[J].计算机工程与应用,2004,25(2):190—192
[12]. 李珊,袁方.基于Web日志挖掘的页面兴趣度方法的改进.计算机时代,2007年第3期
[13]. Ellen Speaus．Mining structural information on the web．In：Proceedings of the 6th International World Wide Web Conference,April 1997
[14].Jaideep Srivastava,Robert Cooley,Mukund Deshpand，Pang-Ning Tan．Web usage mining discovery and application of usage patterns from web data．SIGKDD Explorations,2000,1（2）：12—23
[15].朱明.数据挖掘[M].中国科学技术大学出版社，2002年． 附录
#用户和文件交叉表
ctab=("",header=T)
ctab=ctab[,-1]
#计算每个文件被访问次数(忽略重复访问)
fun1<-function(val){
return(sum(val>0))
}
simc=apply(ctab,2,fun1)
#两个文件被同一用户访问的次数
mtab=("",header=T)
mtab=mtab[,-1]
#两个文件被同时访问的关联度
gld=("",header=T)
gld=(gld[,-1])
daty<("",header=F) #文件名单
tempname=(daty[,1])
n=length(tempname)
tempx=array(0,dim=c(n,0))
for(i in 1:n) tempx=(tempx,c(tempname))
tempx=(tempx)
tempy=t(tempx)
tempn=array(0,dim=c(n,0))
for(i in 1:n) tempn=(tempn,c(simc))
tempn=(tempn)
关联度=gld[order(gld)]
关联数目=mtab[order(gld)]
分母数=tempn[order(gld)]
分母=tempx[order(gld)]
分子=tempy[order(gld)]
PAGE \* MERGEFORMAT 3
