Web使用挖掘技术的分析与研究.docx
- 文档编号:11708465
- 上传时间:2023-06-02
- 格式:DOCX
- 页数:13
- 大小:26.82KB
Web使用挖掘技术的分析与研究.docx
《Web使用挖掘技术的分析与研究.docx》由会员分享,可在线阅读,更多相关《Web使用挖掘技术的分析与研究.docx(13页珍藏版)》请在冰点文库上搜索。
Web使用挖掘技术的分析与研究
Web使用挖掘技术的分析与研究
摘要:
首先给出Web使用挖掘的定义和完整模型框架;然后对Web使用挖掘中主要步骤的最新研究进展状况作了详细的阐述和分析,其中包括数据采集、数据预处理、模式发现和模式分析;最后对未来的研究重点进行了展望。
关键词:
Web挖掘;Web使用挖掘;数据预处理;模式发现;模式分析
中图分类号:
TP393文献标志码:
A
文章编号:
1001-3695(2008)01-0029-04
Web上的数据正以每天新增一百万个页面的速度增长,页面数目已超过10亿[1]。
如何从这些位于分布式环境中的海量数据挖掘和抽取潜在的、用户感兴趣的有用模式和隐藏的知识成为一个重要而非常有意义的课题。
Web挖掘技术正是以此为目标应运而生的。
Web挖掘技术将传统的数据挖掘技术与Web技术结合起来[2~4],并综合运用了统计学、计算机网络、数据库与数据仓库、可视化等众多领域的技术。
定义1Web挖掘是指从大量Web文档结构和使用的集合C中发现隐含的模式p。
如果将C看做输入,p看做输出,那么Web挖掘的过程就是从输入到输出的一个映射:
?
│?
:
C→p。
?
?
一般地,Web挖掘分为三类[5]:
Web内容挖掘、Web结构挖掘和Web使用挖掘。
目前国际上对Web使用挖掘的研究比较多。
WUM[6~8]是指能够从服务器、浏览器端的日志记录和用户的个人信息中自动发现和预测隐藏在数据中的模式信息――用户群体的共同行为、兴趣以及个人用户的检索偏好、习惯等。
?
?
1Web使用挖掘的基本框架?
?
图1给出了一个WUM比较完善的系统框架模型图。
从图中可以看出它包含了数据采集、数据预处理、模式发现和模式分析四个主要的阶段。
?
?
1.1数据采集?
?
在WUM中,由于HTTP的无状态连接特性而很难得到准确的用户浏览信息。
JaideepSrivastava等人[9]和CyrusShahabi等人[10]提出从Web的结构出发,多层次地进行Web站点信息采集。
?
?
在WUM中,使用数据的采集主要可以分为以下几种形式:
?
?
a)服务器端的数据采集。
主要包括从Web服务器日志中收集和从网络监视器中收集。
Web服务器日志文件是执行WUM的重要数据来源。
该日志文件记录了用户访问站点的数据。
每当站点上的网页被访问一次,Web服务器就在日志文件中增加一条相应的记录。
如图2所示的就是一条典型的ECLF[11](extendedcommonlogfile,扩展日志格式)的记录和提取出的相关信息。
当然,Web服务器日志文件还可以以其他的格式存储,如CLF(commonlogfile,通用日志格式)或其他日志格式有NCSA、CERN、APACHE[12]。
这些记录数据反映了多个用户(可能同时)对Web站点(单站点)的(存取)访问行为。
由于Web环境中存在多级别的缓存(如用户的本地缓存和代理服务器缓存)和防火墙,用户浏览缓存的页面不在服务器端日志上记录,防火墙使得不同的用户请求在Web服务器的日志中记录的均是防火墙的IP地址,所以日志中的网站使用数据并不完全可靠(未采集到所有访问页面、采集时间不够准确、浏览用户的确定不够准确)。
用服务器端日志数据进?
┬?
WUM是不完全可靠的,还必须依靠其他使用数据收集方法。
?
?
221.202.41.83"[25/Dec/2003:
05:
00:
00+0800]"
"GET"Mozilla/4.0(compatible,MSIE5.0;Windows98;DigExt)"
IP地址221.202.41.83
访问时间25/Dec/2003:
05:
00:
00
访问页面
Web服务器对于该请?
で蠓祷氐淖刺?
信息200?
?
返回给客户端的内容大小15763Byte
该请求的引用地址
用户客户端类型?
?
Mozilla/4.0(compatible;MSIE5.0;?
?
Windows98;DigExt)
图2Web服务器ECLF记录格式及提取的信息?
?
b)应用服务器端的数据采集。
这种数据采集方法可以利用应用服务器上的应用程序(如CGI程序)来记录用户的个人信息;同时也可以通过自定义的格式动态记录用户的浏览信息。
每次用户进行访问时先进行身份验证,然后由CGI程序记录用户全部的浏览过程。
这种应用服务器级的采集方法与Web服务器级的数据采集方法相比,在用户确定方面的准确性高,但是大量的应用程序会使系统的效率很低。
?
?
c)客户端的数据采集。
客户端的浏览路径采集比服务器端的采集更具优越性。
因为它是建立在用户的行为源上的,可以准确地捕捉用户的行为。
用户的浏览路径和浏览时间的测量可以很精确,但是它需要用户的许可,有可能会侵犯用户的隐私。
客户端的用户浏览路径采集包括JavaApplet和Java?
?
Script以及Plugin、网页跟踪帧和修改浏览器等技术。
?
?
d)代理服务器端的数据采集。
代理服务器相当于一个在客户端浏览器和Web服务器之间提供了缓存功能的中介服务器,主要用于减少用户下载网页的时间以及服务器与客户机之间的网络流量[13]。
从代理服务器可以得到从多个用户到Web服务器的访问记录(无须用户许可)。
若代理访问站点网页是通过Web应用程序动态生成的,对于用户的每次请求,代理需从Web服务器取得数据。
该收集方法不能准确地确定浏览用户,对访问页面的采集不够全面,采集时间不准确。
?
?
Web使用挖掘数据采集技术汇总如表1所示。
?
?
1.2数据预处理?
?
WUM中对数据进行预处理。
其目标是将包含在多种数据源中的信息转换为适合数据挖掘和模式发现所必需的数据抽象概念,然后在事务数据库上实施挖掘算法,以期最终获得有价值的规律。
因为预处理的结果直接影响到挖掘算法产生的规则和模式,可以说预处理过程是WUM质量保证的关键。
?
?
通常WUM的预处理过程[13~15]包括数据清理、用户识别、会话识别、路径完善等几个步骤,如图3所示。
?
?
?
?
1)数据清理(datacleaning)?
?
数据清理解决了脏数据(dirtydata)的问题,消解数据中的不一致性,并将多个数据源中的数据统一成一个数据存储。
比如,将不同服务器上格式和描述都不同的原始数据规范化,去除日志文件中包含gif、jpeg、gif、map的文件名的项目。
可以预先定义一个缺省的规则库(如算法1)来帮助删除记录。
另外,还可以预先将网站分为一般网站、图片网站和音频网站等,分别建立对应的规则库;然后按照该类网站的规则库进行数据清理。
?
?
算法1?
?
a)选择记录属性。
在Web日志中,选用属性:
A={IP,r.date,r.time,request,size,referer,agent}。
?
?
b)删除无用记录。
建立一个删除列表:
DT={.GIF.JPEG.JPG.gif.jpeg.jpg.map.cgi}。
凡是对后缀名在删除列表中的文件的申请记录均应删除。
?
?
具体过程如下:
?
?
输入:
T1.log中的所有记录集L;?
?
输出:
数据清理后的关系表T2.log;//T2.log表包含A中的字段?
?
foralll?
?
i∈L//依次处理L中的每条记录?
?
{ifT1请求的文件后缀名不在DT中
?
?
then选取T1中所有属于A的字段值并存入T2.log中;}
?
?
2)用户识别(useridentification)
用户识别是从日志中识别出每个访问网站的用户。
最常被WUM工具使用的技术就是基于日志/站点的方法,并辅助一些启发式规则帮助识别用户。
?
?
启发式规则的核心思想在于:
a)不同的IP地址代表着不同的用户;b)用户的IP地址相同,但相应的代理日志表明用户的浏览器类型或操作系统发生了改变,则认为代表着不同的用户;c)用户的IP地址相同,用户使用的操作系统和浏览器也相同的情况下,则根据网站的页面链接结构对用户进行识别(如果用户请求的某个页面不能从已访问的任何页面到达,则认为这是一个新的用户)。
?
?
要说明的一点是,这些仅是帮助识别用户的启发规则,并非使用了这些规则就能准确地识别出用户。
在用户识别的过程中,还会产生一些问题。
典型的有:
?
?
a)单IP地址/多服务器会话。
Internet业务供应商(ISP)为用户提供了许多用于上网的代理服务器,因此在同一时间段内可能有许多不同用户通过同一代理服务器(单IP地址)存取同一网站。
?
?
b)多IP地址/单服务器会话。
一些ISP和私用工具会为来自不同用户的每次请求随机分配IP地址池中的某一个。
在这种情况下,一次单独的服务器会话可能会有多个IP地址。
?
?
c)多IP地址/单用户。
一个用户从不同机器上网会在不同会话中使用不同地址,这就使得追踪同一用户的重复访问变得很困难。
?
?
d)多代理/单用户。
某用户在同一机器上打开多个浏览器窗口,访问Web站点的不同部分或打开不同的浏览器进行访问,将产生单个用户的多个服务器会话。
?
?
3)会话识别(sessionidentification)在跨越时间区段较大的Web服务器日志中,用户有可能多次访问了该站点。
会话识别的目的就是将用户的访问记录分为单个会话。
用户会话S可以定义为?
?
S=〈UserId,{(Pid?
?
1,time?
?
1),…,(Pid?
?
k,time?
?
k)}〉
(1)?
?
令RS={(Pid?
?
1,time?
?
1),…,(Pid?
?
k,time?
?
k)}
S=〈UserId,RS〉
其中:
UserId是用户标志;RS是用户在一段时间内请求的Web页面的集合,它包含用户请求页面的标志符Pid和请求时间time。
通常可以采用超时方法识别用户会话,对于超时阈值的设定有两种方法:
a)设定整个用户会话的超时时间,则式
(1)中的用户会话必定满足下面的条件(其中T为预先设定的超时阈值):
time?
?
k-time?
?
1≤T。
b)设定相邻请求之间的超时时间。
如果两页间请求时间的差值超过一定的界限就认为用户开始了一个新的会话,则式
(1)中的用户会话必定满足下面的条件(其中T为预先设定的超时阈值):
time?
?
i-time?
?
?
?
i-1≤T。
其中?
?
1
?
?
超时阈值的设定直接影响Web日志数据预处理的结果输出。
设定不同的超时阈值就会产生不同的用户会话文件,从而最终影响Web日志的挖掘结果。
4)事务识别(transactionidentification)
事务识别是指将页面访问序列划分为代表Web事务或用户会话的逻辑单元。
与用户session识别不同的是,它以事务为单位,只包含与事务相关的页面。
事务识别方法中最简单的莫过于时间窗口法,即定义一个时间长度。
该时间片内用户浏览的所有页面均归为一个事务。
比较常用的则是最大向前参考法[16]。
具体做法是,从用户访问的首页开始,到第一个回退动作为止定义为一个事务;接下来的第一个向前动作引发下一事务,直到下个回退动作产生。
周而复始,将用户访问页面序列划分为一个个事务。
比如,一个用户在一次浏览过程中请求了ABCBCDE页面,根据最大前向参考法,用户访问过的访问服务器会话期间应该是ABC和BCDE。
?
?
5)路径补充(pathcompletion)
由于本地缓存和代理服务器缓存的存在或是通过post技术信息传递,使得服务器的日志会遗漏一些重要的页面请求,这样就会影响到模式发现的效率和精度。
解决的方法类似于用户识别中的方法,可以借助应用日志或站点拓扑结构推断当前请求的页面的链接来源,从而将遗漏的页面请求添加到用户的会话文件中。
1.3模式挖掘
在数据预处理完成后,Web使用数据的模式发现采用的算法如下:
?
?
a)统计分析。
统计方法是从Web中提取有用信息最常用的一种技术。
通过对session文件的分析,可以对感兴趣的信息进行统计。
一般包括各种统计数据,如最频繁访问的N个页面、每页平均浏览时间和网址路径平均访问长度等,也可能涉及一些关于限制的错误分析,如统计非法IP、无效URL和未授权访问等。
?
?
b)关联规则。
在Web使用挖掘中,关联规则主要用于发现用户之间、页面之间以及用户浏览页面和网上行为之间存在的潜在关系。
最著名的关联规则挖掘方法是R.Agrawal提出的Apriori算法。
最近也有独立Agrawal的频集方法的工作[17],以避免需要大量空间存储中间结果和需要反复扫描数据库而带来的算法上的缺陷。
无论哪种算法,关联规则的发现都遵循两个步骤:
(a)迭代识别所有的频繁项目集,要求频繁项目集的支持率不低于用户设定的最小支持度(具体见定义2);(b)从频繁项目集中构造可信度不低于用户设定的最小置信度(具体见定义3)。
定义2支持度(support)是指交易集T中包含X和Y的交易数与交易数据库D中所有的交易数之比:
?
?
c)序列模式。
序列模式与关联模式相仿,差别在于序列模式把数据间的关联性与时间先后顺序联系起来,即不仅需要知道事件是否发生,而且需要确定事件发生的时间先后。
可以把它看成是一种增加了时间属性的特定关联模型。
下列规则中,(a)是序列模式,(b)是关联规则。
比较(a)和(b)便不难发现,(a)考虑了访问的先后顺序,而(b)则没有考虑时间因素。
?
?
(a)访问页面P?
?
l和P?
?
3后有35%的用户又访问了页面P?
?
5。
?
?
(b)访问页面P?
?
1和P?
?
3的用户中有35%的用户也访问了页面P?
?
5。
?
?
d)聚类。
聚类是将数据点集合分成若干类或簇(cluster),使得每个簇中的数据点之间最大程度地相似,而不同簇中的数据点最大程度地不同,从而发现数据集中有效的、新颖的、可以理解的数据模式分布。
在WUM中,聚类技术是对符合某一访问规律特征的用户(页面)进行用户(页面)特征挖掘。
通常可以将用户浏览页面的总和视为数据空间,构造一个URL_UserID关联矩阵M?
?
?
?
m×n,如式
(2)所示。
?
?
其中:
h?
?
?
?
i,j是j客户在一段时间内访问第i个URL的次数;每一行向量M[1,j]表示所有客户对URL“1”的访问情况;每一列向量M[i,1]表示客户“1”对该商务站点中所有URL的访问情况。
因此可以这样认为:
行向量既代表了站点的结构,又蕴涵有客户共同的访问模式;而列向量既反映了客户类型,也勾勒出了客户的个性化访问子图。
再使用一些度量方法(如Hamming距离)分别度量行向量和列向量的相似性,就可以得到两种类型的聚类,即使用聚类(用户聚类)和网页聚类。
用户聚类主要是把具有相似特性(或浏览模式)的用户聚集在一组,这类知识对电子商务和为用户提供个性化的服务特别有用;网页聚类可以找出具有相关内容的网页组,这对网上搜索引擎及提供上网帮助的应用特别有用。
?
?
e)分类。
在WUM中,分类技术可以预先把页面分到不同的类中。
这样在分析以往的访问记录得知某用户以前经常访问某一类的网页之后,便可以将该类网页中还没有被该用户访问过的页面推荐给用户。
这样节省了用户搜寻所需信息的时间,同时增强了网站的个性化服务意识。
最为典型的决策树学习系统是ID3,它采用自顶向下不回溯策略,能保证找到一个简单的树。
算法C4.5和C5.0都是ID3的扩展,它们将分类领域从类别属性扩展到数值型属性。
?
?
f)路径分析。
使用路径分析技术进行WUM时,从Web站点拓扑结构图抽象而来的有向图中挖掘出最频繁的路径访问模式或大参引访问序列。
Chen等人从原始日志数据中导出最大向前引用序列MFR的过程,实际上就是在构造用户的访问子图。
路径分析可以用来确定网站上最频繁的访问路径,从而调整站点的结构。
例如可以得到类似如下的信息:
?
?
(a)访问网站的用户中有25%是从页面B开始的;?
?
(b)有15%的用户访问路径为C→M→D→E。
?
?
针对(a),可以在页面B上直接添加一些想给用户直接传达的信息,或者通过链接指向相应的页面,从而提高该信息的点击率;针对(b),可知路径C→M→D→E为频繁访问路径,可以在这几个页面上添加其他超链接或者促销信息,从而增加其他信息的访问频度。
1.4模式分析技术
挖掘出来的用户行为模式(集合),需要合适的工具和技术对其进行分析、解释和可视化,从中筛选出有趣(有用)的模式,使之成为人们可以理解的知识;否则挖掘出来的模式将得不到很好的应用。
具体包括:
?
?
a)可视化技术。
与其他数据挖掘应用领域一样,Web使用挖掘技术与可视化技术的结合还刚起步。
Web使用挖掘领域内的可视化技术主要分为基于点和基于序列两类。
基于点的可视化技术适合显示数据对象的各种统计值,如产品或页面的访问次数、页面间转移的频率或者次数等;基于序列的可视化方法着重表现用户行为的序列特征,用各种方法描绘用户的访问序列。
?
?
b)知识查询技术。
自动搜索相关的规则、模式以及其他知识,可以帮助分析用户的目标,用智能的方式回答查询。
建立一个MLDB(multiplelayereddatabase,多层数据库),用数据库技术来管理Web的元数据(metaWeb)是其中的一种方法[18]。
目前研究人员已经在SQL语言的基础上提出几种适合在数据挖掘过程中使用的查询语言,如DMQL;也有专门为Web挖掘而定义的WebSSQL、WebLQM和Squeal等。
?
?
2Web使用挖掘的应用系统?
?
1)通用系统
通用系统提供多种通用的数据挖掘功能,一般并不直接支持某种特定应用。
WebMiner[14]支持多种数据挖掘功能,并提供挖掘语言。
WebSIFT的主要特点是支持基于supportlogic的模式兴趣度、自动识别和过滤出令人感兴趣的模式。
最有影响力的是WUM系统。
它把清理后的日志数据合成聚合树(aggregatetree),挖掘和分析工作的主要内容是使用MINT语言查询聚合树。
2)商业智能
在以用户为中心导向的电子商务中,用户盈利能力分析、用户群体分类分析、用户满意度分析、用户的获得与保持和交叉营销是商业领域内很重要的工作。
在Web站点可收集大量的客户行为数据,但由于数据量很大,手工分析几乎变成了不可能的任务。
适合处理大数据量的Web使用数据挖掘技术便在此处体现出了它的商业价值。
有一些商用软件如Accure、Microstrategy和IBM的SurfAid等均是针对这个方面的应用。
?
?
3)个性化服务
Web个性化服务是指Web站点能够根据用户的喜好和需求自动调整Web站点的信息组织和表示。
一方面用户能够在它的帮助下迅速找到需要的信息,使得Web站点更具吸引力。
该应用的关键问题是用户建模和行为预测。
ThorstenJoachzms等人建立了一个称为Webwatcher的浏览导航系统。
它根据用户事先声明的浏览目的或兴趣(以关键字的形式表示)预测当前页中用户可能点击的链接,并以图形化的方式标注出此链接。
文献[15]实现了一个基于聚集模型的Web推荐系统。
?
?
4)Web性能改进和设计优化
其主要目的是利用Web使用挖掘技术向网站建立者提供各种关于网站架构的信息,也提供了用户在使用网站时的习惯。
网络管理员可以在Web缓存、网络结构安排、负载平衡和数据分布上进行统筹规划。
具体的研究有利用Web日志数据设计一个数据集市、为频繁模式挖掘提供数据源、应用于智能Web缓冲。
3未来研究重点及展望?
?
WUM技术作为一个新兴研究领域,采用了来自多个领域的技术和先验知识。
虽然它取得很多突破性的进展,但是在未来的研究当中,还有一些热点和难点的方向值得指出。
?
?
1)数据收集与预处理
在WUM过程中,如何既不侵犯用户的个人隐私,又能尽量收集到完整的网站访问日志;同时能保证服务器的工作效率和服务质量。
有关数据收集的专门工具和技术正在研究中。
另外,目前WUM的数据源主要集中在server端的log日志,在未来的研究中如何能将serverlog、proxyserverlog及client端的cookieslog中的使用数据、用户信息综合集成并预处理,是一个研究的热点和难点。
?
?
2)模式挖掘?
?
目前WUM的工具不多,而且功能上均有较大的局限性,所采用的算法质量也不高。
如何能开发出更加智能化和高效率的模式发现工具将是一个长期的研究课题。
另外,如何尽可能全面(不可能全部)地集成Web上动态、分布的数据并实施挖掘,以挖掘出更多有用信息,也是未来该领域面临的一个挑战。
?
?
3)模式分析?
?
开发一个智能化模式分析工具,将不同数据源挖掘出来的模式进行集成,并提供集统计分析、可视化分析技术、过滤和解释功能等为一体的模式分析功能,真正辅助人们理解挖掘出来的知识是一个值得不断深入研究和探索的热点。
参考文献:
?
?
[1]BRINS,MOTWANIR.WhatcanyoudowithaWebinyourpocket[J].DataEngineeringBulletin,1998,21
(2):
37-47.
[2]FELDMANR,DAGANI.Knowledgediscoveryintextualdatabases(KDT)[C]//Procofthe1stInt’lConfonKnowledgeDiscoveryandDataMining.Montreal:
[s.n.],1995:
112-117.?
?
[3]CHAKRABARTIS.Dataminingforhypertext:
atutorialsurvey[J].SIGKDDExploration,2000,1
(2):
1-11.
?
?
[4]COOLEYR,MOBASHERB,SRIVASTAVAJ.Webmining:
informationandpatterndiscoveryontheWorldWideWeb[C]//Procofthe9thInt’lConfonToolswithArtificialIntelligence.WashingtonDC:
IEEEComputerSocietyPress,1997:
558-567.
?
?
[5]MADRIASK,BHOWMICKS.ResearchissueinWebdatamining[C]//Procofthe1stInt’lonDataWarehousingandKnowledgeDiscovery.Canada:
AAAIPress,1999:
303-312.
?
?
[6]PITKOWJ.InsearchofreliableusagedataontheWWW[C]//Procofthe6thInt’lWorl
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Web 使用 挖掘 技术 分析 研究