（计算机应用技术专业论文）基于概念格的web日志挖掘的研究.pdf

摘要 随着w e b 资源的不断丰富和增加，w e b 站点结构变得越来越复 杂，传统的w e b 站点缺乏智能性和主动性，因此，面对复杂面庞大 的万维网，人们不容易找到自己感兴趣的信息，同时w e b 站点和w e b 服务器的设计难度也相应提高，这就需要对w e b 站点进行优化以提 供智能的w e b 服务，如个性化服务、自适应站点等。而优化站点的 一个重要依据就是用户的访问行为，由于w e b 日志详细地记录了用 户的访问信息，具有丰富的内涵。因此，w e b 日志挖掘能够有效地发 现用户的访问模式，为站点改进提供依据，从而解决以上问题。 本文讨论了w e b 日志挖掘的过程为数据预处理、模式发现和模 式分析；详细地分析了w e b 日志挖掘数据预处理阶段的各项任务以 及w e b 日志挖掘中的各种模式发现方法和技术；分析了采用g o d i n 算法在构造概念格时需要遍历原始概念格中的所有节点才能确定新 概念的产生子，提出了使用树结构的搜索方法来缩小新概念的产生子 及其父节点的搜索范围以完成概念格的更新，提高和改善了概念格的 构造效率。本文将概念格理论应用于w e b 日志挖掘的模式发现，解 决了w e b 日志的增量挖掘问题；研究了基于概念格的关联规则的挖 掘，提出了一种从最大频繁项集产生所有强关联规则的优化方法，减 少了模式发现中频繁项集的发现时间和不必要的规则的产生，从而提 高了模式发现的效率。 概念格的渐进式构造算法的优点在于可以实现概念格的维护和 更新，从而使得w e b 日志挖掘模式发现方法能够有效地实现智能w e b 服务所需要的模式库的更新。 关键词w e b 日志挖掘，概念格，模式发现 a b s t r a c t w i t hc o n s t a n ti n c r e m e n to fw e br e s o u r c e t h ef r a m e w o r ko fw e b s i t e sb e c o m em o r ea n dm o r ec o m p l i c a t en o w a d a y s t h e p r e s e mw e b s i t e s a r en o ti n t e l l i g e n ta n da c t i v e , s oi f sv e r yd i m c u l tf o ru s e r st of i n dt h e i r n e e d e di n f o r m a t i o nr a p i d l yi nf r o n to fs u c hh u g ea n dc o m p l e xw o r l d w i d ew e b m e a n w h i l et h ed e s i g no fw e bs i t e sb e c o m e sv e r yh a r d s o w e bs i t e ss h o u l db ei m p r o v e dt op r o v i d eb e t t e ra n di n t e l l i g e n tw e b s e r v i c e s ，s u c ha sp e r s o n a l i z e dw 曲s e r v i c e 。a d a p t i v ew 曲s i t ea n ds oo i l o n eo ft h em o s ti m p o r t a n tr e l i a n c eo f i m p r o v i n gw b bs i t e si su s e r a c c e s s i n f o r m a t i o n ，w h i c hi sr e c o r d e di nw 曲l o gf i l e sf o r m a t ，s ow e bl o g m i n i n gc a nd i s c o v e ru s e ra c c e s sp a t t e r n se f f i c i e n t l ya n dt h e r e f o r er e s o l v e t h ep r o b l e m sa b o v e i nt h i st h e s i s ，t h e p r o c e s s o fw 曲l o gm i n i n g i n c l u d i n gd a t a p r e p r o c e s s i n g ，p a t t e r n sd i s c o v e r ya n dp a t t e r n sa n a l y s i si sd i s c u s s e d w e a n a l y z ea l lt a s k so fd a t ap r e p r o c e s s i n ga n dk i n d so fp a t t e r nd i s c o v e r y t e c h r i e l e g y w ea n a l y z et h ed e f i c i e n c i e so fg o d i na l g o r i t h mt h a ti tn e e d s t ot r a v e r s ea l lt h ec o n c e p tn o d e st of i n dt h eg e n e r a t o ro ft h en e w c o n c e p t ， t h e r e f o r ep r o p o s ean e wa l g o r i t h mb a s e do nt r e es t r u c t u r et ou p d a t e c o n c e p tl a t t i c e ，w h i c hc a nr e d u c et h es e a r c h - r a n g eo fg e n e r a t o r sa n d p a r e n tn o d e s ，s oi th a sb e t t e re f f i c i e n c yt h a ng o d i na l g o r i t h m w ea p p l y c o n c e p tl a t t i c et h e o r yt od i s c o v e rp a t t e r n si nw e bl o gm i n i n g w h i c hc a n r e s o l v ei n c r e m e n t a l m i n i n gp r o b l e m w er e s e a r c ha s s o c i a t i o n r u l e s m i n i n gb a s e do nc o n c e p tl a t t i c e , o p t i m i z i n gt h eg e n e r a t i o no fs t r o n g a s s o c i a t i o nr u l e sb ym a x i m u nf r e q u e n ti t e m s e t s ，w h i c hc a nr e d u c et h e t i m eo ff i n d i n gf r e q u e n ti t e m _ s e t sa n du n n e c e s s a r yr u l e s ，t h e r e f o r e i m p m v e s t h ee f f i c i e n c yo f p a t t e r n sd i s c o v e r y t h ea d v a n t a g eo fi n c r e m e n t a lc o n c e p tf o r m a t i o na l g o r i t h mi st h a ti t c a l l u p d a t et h eo r i g i n a lc o n c e p tl a t t i c es ot h a t0 1 1 1 m e t h o do fp a t t e r n d i s c o v e r yi sm e a n i n g f u lt ou p d a t et h ep a t t e r nd a t a b a s eo fi n t e l l i g e n tw r e b s e r v i c e s k e yw o r d sw e bl o gm i n i n g ，c o n c e p tl a t t i c e ，p a t t e md i s v o v e r y 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得中南大学或其他单位的学位或证书而使用过的材料。 作者签名： 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文；学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名：丑蕉末导师签名：垩旦銎日期：卑年上月衄 生亩太堂亟堂僮论塞蓥二童绪途 第一章绪论 w w w ( w o r l dw i d e w e b ) 自2 0 世纪9 0 年代诞生以来，已经发展成为拥有上万 站点和亿万用户的巨大分布式信息空间。随着i n t e r n e t 技术的广泛应用和w e b 的迅速普及，w e b 上的信息变得无比丰富，w e b 已成为人们获取信息的一个重要 途径。但是如何从海量的w e b 数据中找到潜在的、有用的知识，就提出了一个新 的挑战。而将数据挖掘技术应用到w e b ，即w e b 挖掘，可以有效地解决问题。 w e b 挖掘包括w e b l 勾容挖掘、w e b 结构挖掘和w e b 使用挖掘，分别挖掘w e b 站点 的文件内容、结构以及站点的访问和使用信息。 由于w e b h 志详细地记录了用户访问站点的情况，因此，它成为w e b 站点访 问和使用信息的一个重要数据来源。针对w e b 日志的挖掘就是一种w e b 使用挖 掘，i i p w e b 日志挖掘。 1 1 研究背景及意义 长期以来，人们都是通过电视、广播、报纸等传统媒体来获取信息。但是随 着科技的发展和时代的进步，当今已经成为一个信息时代，一个最重要的标志就 是w o r l dw i d ew e b ( 简称、b ) 的发展和普及。 w e b 起源于2 0 世纪8 0 年代，由位于瑞士的欧洲量子物理实验室c e r n ( t h e e u r o p e a nl a b o r a t o r yf o rp a r t i c l ep h y s i c s ) 所发展出来的一种主从结构分布式超媒 体系统【l l 。到2 0 世纪9 0 年代，w e b 技术有了突破性的进展。从此，w e b 迅速成 长为全球范围内的信息宝库，成为i n t e m e t 上最为流行的信息传播方式。 w e b 作为个巨大的信息服务中心，为用户提供了大量而丰富的信息资源， 是人们生活中不可缺少的最重要的信息获取手段。然而，w e b 资源不断丰富的同 时，w e b 站点的结构也将变得越来越复杂，从而会出现以下问题： ( 1 ) 面对复杂的w e b 站点，用户想快速地获得自己所需要的资源往往比较 费劲，甚至不知道从何下手，犹如大海捞针 ( 2 ) 传统的w e b 服务缺乏智能性，只是为人们提供资源，对所有的用户一 视同仁，不能针对不同的用户提供不同的服务，不能根据用户的兴趣为用户寻找 到他们所需要的信息等。 ( 3 ) w 曲站点的经营和管理者的设计工作也变得困难，为了提高网站的声 誉和效益以吸引更多的用户，他们会竭尽全力对站点进行合理的设计或改进，来 优化自己的站点。 生直太堂臻堂僮论塞 箍= 童缝淦 这些问题使得用户对w e b 服务提出了更高的要求。提供高质量的w e b 服务 的一个重要前提就是需要了解用户需要什么和想做什么，来满足不同层次、不同 爱好的用户的信息需求因此，了解用户的访问行为特性对提高w e b 站点的服 务质量显得尤其重要。但是，由于一个w e b 站点有大量的用户对其进行访问， 而这些用户又分布在世界各个不同的地区，所以，直接去找用户了解他们的兴趣 和特性是很不实际的。而能够有效地反应用户访问w e b 站点行为的一种数据就 是w e b 日志，其具有以下特点1 2 l ： ( 1 ) w 曲日志是一种大容量大规模的数据 每个网站每天随时都会有大量的不同的用户进行访问，所以w e b 日志是随 时间不断增加的。比如，一个中小型网站每天就可以记载好几兆的信息，记录了 上万次用户的访问。因此，随着时间的推移，数据会变得非常庞大。 ( 2 ) w e b 目志具有丰富的内涵，包含决策可用的信息，是网站设计者和用 户进行沟通的桥梁。 w e b 日志记录了一系列的访问信息，从各方面详尽反映出用户访问w e b 的 细节，是取之不尽、用之不竭的宝贵资源。w e b 日志记录的访问信息包括每个用 户的访问行为，代表每个用户的个性，也记录了群体用户的访问行为，代表群体 用户的共性，这些信息经过处理后，从中提取一些特性，就具有了非常丰富的内 涵。例如，我们通过分析得到了某个用户或者某一类用户的特性，也就是说他们 对一个网站的某一部分内容非常感兴趣，访问得比较多，而这部分内容需要通过 多次点击才能访问到。那么网站设计者得到了这方面的信息后，就可以考虑将这 部分内容放到网站的首页上来，这样，下次用户访问的时候就可以直接从首页上 去访问，这样就为用户节省了更多的时间，提高了访问效率。 然而，采用传统的数据库技术对w e b 日志进行处理并没有多大的意义，因 为我们不需要对这些数据进行查询或存取等操作，我们真正需要的是对这些数据 进行深层次的处理，从中获取隐藏在w e b 目志数据背后的有用的信息，从而把 这些数据转换成有用的知识，即通过数据挖掘的方法来对w e b 日志进行分析和 处理，以发现有关用户访问站点行为的知识，这就是w e b 日志挖掘。基于w e b 日志的特点，可以看出w e b 日志是一种良好的数据挖掘对象，针对它进行挖掘 可以解决上述出现的问题，因此，w 曲日志挖掘的产生成为必然。 w e b 日志挖掘是w e b 挖掘( w e bm i n i n g ) 的一个重要分支。在已有的k d d ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，数据库中的知识发现) 方法和技术已不能满足 人们从w e b 中获取知识的需要的情况下，o e t z i o n i 于1 9 9 6 年最早提出w e b 挖 掘这个概念j 。w e b 挖掘是当今的一个十分活跃的研究领域，近年来，许多重要 的国际学术会议，如k d d ，将w e b 挖掘作为一项主要的研究内容，国内外许多 2 生亩叁堂亟堂焦逾塞筮二童缝! 金 研究人员和机构都把目光集中于这一方向，使得w e b 挖掘的理论和方法不断得 以发展。 w e b 挖掘是在i n t e m e t 迅速发展和w e b 信息量以惊人的速度增加这样的背 景下产生的。它的出现，使得从海量的w e b 信息中抽取潜在的、有用的模式和 知识成为可能。因此，w e b 挖掘是结合了w e b 和数据挖掘的一种新技术，是数 据挖掘技术在w e b 上的应用。但是由于w e b 数据结构复杂，形式多样，具有分 布、动态、异质、非结构化等特点，因此w e b 挖掘不同于传统的数据挖掘，它 要比传统的数据挖掘复杂和困难，要用到更多的有别于传统数据挖掘的技术和方 法，对传统的挖掘方法进行扩展和改进，将其应用到w 如信息上进行挖掘，得 到有用的知识。 w e b 信息就是w 曲挖掘的数据来源。w e b 包含数以亿计的w e b 站点，w e b 挖掘的数据来源就是依靠它所挖掘的站点信息。因此，凡是在w e b 站点中对用 户有价值的数据都可以成为它的数据源。典型的w e b 信息包括： w e b 页面：就是我们所说的网页，包含文本和多媒体信息( 包括音频、视频、 图片) 。 w e b 结构：w e b 页面之问的超链接关系，描述了网页之间的联系。 w e b 日志：用户浏览w e b 服务器时，会产生服务器日志，客户端日志和代 理服务器目志三种类型的同志文件，用于记录用户访问的基本情况。本文讨论的 是w e b 服务器日志，将在第二章详细讨论。 根据这些数据源的不同，将w e b 挖掘相应地分为三大类”l ：w e b 内容挖掘 ( w e bc o n t e n tm i n i n g ) 、w e b 结构挖掘( w e bs t r u c t u r em i n i n g ) 和w e b 使用挖掘 ( w e b u s a g e m i n i n g ) ( w e b 日志挖掘) ，如图l l 所示。目前，国际上对w e b 使用挖 掘的研究比较多，w e b 挖掘的国际权威会议w e b k d d 也把使用挖掘作为重点。 图1 - 1w e b 挖掘的分类 ( 1 ) w r e b 内容挖掘 w e b 内容挖掘是指对站点的w e b 页面内容进行挖掘，从而从w e b 文档的内 容或描述中抽取知识，其目的是联机自动搜索w e b 上的信息资源。w e b 内容挖 掘建立在信息检索基础之上，通过采用概念层次、页面链接等技术对传统的搜索 虫直去堂亟堂僮论奎差二重绪监 引擎进行改进，帮助搜索引擎提供更高效的服务，以协助用户搜索信息或者根据 用户的配置文件为用户过滤无用的信息。w 曲页面的信息主要包括文本信息和多 媒体信息，所以将w 曲内容挖掘分为文本挖掘和多媒体挖掘。文本挖掘是指对 文本文档( 包括t x t ，p d f ，h t m l 等1 的挖掘，主要包含文本分析( t e x t a n a l y s i s ) 、 文本解释( t e x ti n t e r p r e t a t i o n ) 、文档分类( d o c u m e n tc a t e g o r i z a t i o n ) 和文档可 视化( d o c u m e n tv i s u a l i z a t i o n ) 等挖掘技术【5 1 。挖掘的结果既可以是对某个文本 内容的概括，也可以是对整个文本集合的分类结果或聚类结果。文本挖掘目前主 要用于w e b 页面归纳和搜索结果归纳。多媒体信息挖掘，主要是指通过对w 曲 上的音频、视频数据和图像进行预处理，应用存储和搜索技术与标准的数据挖掘 方法的集成，对其中潜在的、有意义的信息和模式进行挖掘的过程。多媒体信息 挖掘可以应用于语音识别、图形和图像处理等研究领域。 ( 2 ) w e b 结构挖掘 w e b 结构挖掘是指通过分析w e b 站点的超链接结构，将w 曲页面进行分类， 以利于信息的搜索。w e b 的本意是蜘蛛网，这个名字的由来正是由于w e b 页面 之间存在着相互交织的联系，而这种联系通过超链接体现出来。大量的w e b 超 链接信息提供了关于w e b 页面内容相关性，质量和结构方面的信息，有助于自 动推断出页面的权威性( a u t h o r i t y ) 。对w e b 页面的超链接结构进行挖掘得到的 有用知识是提高检索效率的重要手段，对搜索引擎的设计有极大的帮助。 ( 3 ) w e b 日志挖掘 w 曲日志挖掘是w e b 挖掘领域中一个重要的研究方向。w e b 日志挖掘主要是 指通过分析w 曲日志文件，发现用户访问站点的模式，其过程主要包括j ：数据 预处理、模式发现、模式分析。w 曲日志挖掘可以完成两类任务：统计分析和智 能分析。统计分析包括流量分析、广告分析、网站出入口分析、用户来源分析以 及浏览器和平台分析等。智能分析是进行深层次的数据分析，通过模式发现来实 现，是具有重要意义的一类。 模式发现阶段是w 曲日志挖掘的核心部分。通过对w e b 日志进行有效的挖 掘，可以发现用户访问页面的特征、规律，发现隐藏在其中的用户访问模式，以 获得更深层次的用户访问信息，如关联规则、用户分类和聚类、页面聚类、序列 模式、频繁访问路径等，这些模式反映了用户访问w e b 站点的兴趣、行为，可 以作为站点设计者改善w e b 服务，提供高质量的w e b 服务的有力依据。挖掘出 的模式以及统计分析的结果有着广阔的应用领域。 ( 1 ) 改进w e b 服务器的性能 通过w e b 日志挖掘，可以提供网站服务效率全方位的信息。分析网站流量， 发现系统性能瓶颈，从而有助于找到平衡服务器负荷，优化传输，减少拥塞的方 4 虫直厶堂亟堂僮j 金塞箍二童绪：l 金 法，缩短用户等待时间，提高系统效率和服务质量。 ( 2 ) 优化w 曲站点的结构 站点结构描述了某w e b 站点的页面以及页面之间的关系。通常w e b 服务方 主要根据自己的领域知识设计w e b 页面的结构，而w e b 站点主要是为用户提供 服务，满足用户的需要。那么服务方的结构设计是否合理? 是否能够留住和吸引 更多的客户? 这些问题的出现就要根据需要对站点进行改进，优化站点。 ( 3 ) 实现w e b 个性化服务及自适应站点 目前w e b 系统为所有用户提供相周的服务，其典型的服务方式是通过建立 一个w e b 站点来向所有用户发布相同的信息。然而用户的需求千差万别，因此， 用户希望w e b 系统能够根据他们特性的不同提供个性化的服务。事实上，针对 用户特性并向用户提供个性化服务已经成为w e b 技术的一个研究热点。w 曲个 性化实质上就是一种以用户需求为中心的w e b 服务。利用序列模式、频繁访问 路径等方法对站点访问者的行为进行预测和聚类，为他们提供具有类似浏览模式 的用户群体的个性化服务，更好地满足用户的需求。 自适应站点是指能根据用户的访问模式自动学习和调整自身组织架构的网 站。通过观察用户的访问模式自动改进站点的结构和表现形式，以反映用户的兴 趣所在。 ( 4 ) 商业智能发现 w e b 数据的商业智能发现是将数据挖掘技术应用到电子商务以发现有商业 价值的决策知识。通过加工处理涉及消费行为的大量信息，确定特定消费群体或 个体的兴趣、消费习惯和消费需求，进而推断出他们下一步的消费行为。然后以 此为基础，对所识别出来的消费群体进行特定内容的定向营销，这与传统的不区 分消费者对象特征的大规模营销手段相比，大大节省了营销成本，提高了营销效 果，从而为企业带来更多的利润。 ( 5 ) 用户移动模式发现 未来绝大多数的移动用户可以在任何时间和地点通过无线网络来访问所需 数据，实现无约束通信和资源共享的目的，这种新的分布式计算环境称为移动计 算( m o b i l ec o m p u t i n g ) 。用户移动访问模式是移动计算环境中的一个新的挖掘方 法。移动用户的移动日志就是记录了关于移动用户位置的数据集。对移动环境中 的服务器同志进行挖掘，得到频繁用户移动模式可以更加有效地支持移动对象位 置管理服务和基于位置的移动增值服务等业务。 ( 6 ) 网络安全 分析网上银行、网上商品交易用户日志，可以防范黑客攻击、恶意诈骗。 ( 7 ) 网站评估 生直去堂亟堂僮论室筮= 重绪j 盆 w e b 日志挖掘可以获取用户对网站使用情况的第一手资料，为网站评估提供 依据。 因此，通过w e b 日志挖掘得到的模式是以上应用的一个重要的前提，w e b 日志的模式发现显得尤其重要。 1 2 国内外研究现状 1 2 1w e b 日志挖掘 对w e b 日志挖掘的研究一般都是从数据预处理、模式发现和模式分析这三 个阶段着手。目前，w e b 日志挖掘的研究侧重于数据预处理和模式发现这两个阶 段。 对数据预处理的研究，主要是研究会话识别的方法和路径补充的方法。新的 会话识别方法有基于时间窗1 ：3 模型和最大前向引用模型的方法p j 和基于时间间 隔的会话识别方法| 8 1 ：对路径补充的研究，文献【9 l 提出了用于用户访问页面路径 补充的u b p s 启发式规则，以便于更好地进行事务识别和后续的用户浏览模式识 别；大多数研究都是对来自单个服务器的日志数据直接进行数据预处理，而文献 f io 1 3 】研究了针对来自多个服务器的日志数据的预处理方法，必须先将所有日志 文件进行整合，再进行数据预处理。 w e b 日志模式发现的研究主要是针对不同挖掘任务研究各种模式发现算法。 文献 1 4 2 0 研究了w e be t 志的关联规则挖掘，文献【2 l 】首先提出路径遍历模式发 现算法，文献 2 2 - 2 5 1 都是基于访问路径树的频繁访问路径挖掘，文献 2 6 1 1 2 7 研 究了基于传统的数据挖掘算法的序列模式挖掘，文献【：8 】提出了基于访问路径树 的序列模式挖掘。 除了对数据预处理和模式发现的研究外，还有w e b 日志挖掘模型，系统或 工具的研究，以及基于w e b 日志挖掘的个性化服务等，如文献 2 9 】。 w e b 日志挖掘的模式发现需要采用不同的数据挖掘算法来实现，包括关联知 识挖掘、聚类、分类、序列模式挖掘等。其中，关联规则挖掘是关联知识发现最 常用的方法，是数据挖掘中最活跃的研究方法之一，可以用来发现用户访问的页 面之间的关联，帮助站点设计者改进站点结构。关联规则挖掘是数据挖掘领域中 的一个非常重要的研究课题，它不仅在现实中有非常重要的应用前景，而且也是 许多其他挖掘任务的基础和核- i i , 。在此方面已有大量的研究，其中a p r i o r i 算法 是一种最具有影响力和代表性的挖掘关联规则频繁项集的经典算法。后来有诸多 研究对原有a p r i o d 算法进行优化以提高算法的效率，如采用并行的思想、哈希 方法、随机采样等。另外，为了克服a p r i o r i 算法多次扫描数据库和产生大量候 6 虫直厶堂亟堂僮论室差= 童绪途 选项目集的缺陷，j i a w e i h a n 等人提出了不产生候选项集的新方法一f p g r o w t h 方法，在效率上较之a 研嘶类算法有很大的提高。 然而，以上的模式发现算法都是基于传统的数据挖掘算法的思想来发现用户 访问模式，都是针对静态数据库和最小支持度不变的条件下进行的。而越来越多 的实际应用领域中，数据库都处在更新中，即随着时间的推移，数据库规模会不 断增加，或者需要对最小支持度进行调整针对不同情况找到感兴趣的频繁项目 集。因此，如何针对动态数据库或最小支持度改变的条件下挖掘关联规则具有更 重要的应用价值，这就是所谓的增量挖掘问题。 典型的增量挖掘算法有c h e u n g 等首先提出的关联规则更新算法f l i p | q ， f u p 2 1 引l ，冯玉才等提出i l i a 和p i u a l 3 。它们都是基于a p r i o f i 算法的思想，产 生大量候选项集。后来，朱玉全等提出了基于f p - t r e e 的f i u a 算法”“。但是， 以上几种算法都只能针对某种特定情况的变化进行更新。m a x 等2 0 0 4 年提出一 种基于f p - t r e e 的m 算法1 3 4 1 ，它可以处理数据库数据增加和最小支持度改变这 两种情况，至多扫描一次数据库并且不产生候选项集的算法，性能有了较大提高。 最近的研究都开始考虑针对数据库和最小支持度同时发生变化的情况进行更新 挖掘，如文献 3 5 1 1 3 6 1 等。 综上所述，目前的关联规则挖掘算法主要存在以下不足。 ( 1 ) 传统的算法或基于传统算法的改进算法不能有效支持增量挖掘，且大 多数需要多次扫描数据库或产生大量的候选项集； ( 2 ) 已有的增量挖掘算法大多也是基于传统的挖掘算法的思想，多次扫描 数据库和产生大量的候选项集，并且只能处理数据库发生变化或者只能处理最小 支持度发生变化的情况。 由于用户对w e b 站点的访问不受时间限制而且用户数量非常大，所以w e b 服务器上的日志记录也在每分每秒不断的产生，即w e b 日志是一种随时间不断 增加的数据。要全面了解用户的访问行为必须针对新的日志进行分析得到新的用 户访问模式，用于w e b 智能化技术的模式库的更新，因此，增量挖掘对于w e b 日志挖掘模式库的更新具有重要的意义。而以上算法不能很好地解决增量问题， 针对已有挖掘算法的不足，并结合前面所述的w e b 日志的特点，利用概念格来 进行w 曲日志挖掘的模式发现。 基于概念格的关联规则挖掘具有以下优势。 ( 1 ) 最耗时的频繁项集的计算可以通过对构造好的概念格进行简单搜索来 实现，减少了对数据库的扫描次数； ( 2 ) 兼顾两方面的增量特性 对新数据的增量性 7 生直厶堂硒堂焦逾塞蕴= 童绪论 由于初始概念格记载了已处理的数据信息，当增加新的日志数据时只需根据 新数据来更新概念格而不需要重新扫描所有旧数据； 对最小支持度的增量性 当用户给定的新的最小支持度时，由于已建好的概念格保存了所有可能的频 繁项集，所以，不需要重新构造概念格，只需根据已有的概念格选出满足新的最 小支持度的频繁项集即可。 由此可见，将概念格应用到w e b 日志挖掘的研究具有广阔的应用前景和重 要的现实意义。 1 2 2 概念格 概念格的研究主要包括概念格的应用和概念格的构造。 概念格( c o n c e p tl a t t i c e ) 是形式概念分析理论( f c a ，f o r m a lc o n c e p t a n a l y s i s ) 中的一种数据结构。形式概念分析理论是由德国的数学家r u d o l f w i l l e 于1 9 8 2 年提出”“。它是一种用于识别数据集中概念结构的数据分析理论，用来 研究特定领域的概念以及概念之间的关系 3 8 1 ，概念和概念之间的关系通过概念 格表示出来，概念格通过h 船s e 图来描述。 概念格自从w i l l e 提出以来，其内在的优势得到越来越多的科研工作者的注 意，并迅速在多个领域得到发展。概念格以其独特的优势引起越来越多的研究人 员的关注，并在许多领域获得了广泛的应用，如信息检索、数字图书馆、软件工 程、知识发现等。然而，概念格的研究仍是一个极其年轻的领域，有很大的发展 前景和应用潜力。 在过去的十年里，f c a 的应用领域发生了巨大的变化，其主要应用领域逐步 由数学转向计算机科学d 9 l 。国内外的研究主要有基于概念格的分类系统、关联 规则和聚类。由于形式概念分析以概念格的形式使数据有机地组织起来，概念格 节点体现了概念内涵和外延的统一，因此非常适合于用来发现知识。概念格从关 系数据中构造出来，然后从它提取各类型的知识，如关联规则、分类规则等。 同时，在应用概念格过程中涉及到概念格的构造，概念格的构造效率是一个 很重要的问题，所以概念格的构造算法也成为了一个重要的研究课题。概念格的 典型构造算法主要分两大类：批处理算法和渐进式构造算法。为了解决数据的集 中式存储和算法串行之间的矛盾，研究者又纷纷提出了概念格的并行构造算法 t 4 0 1 1 4 l l 。渐进式构造算法也叫增量算法，是比较有应用价值的一类构造算法，其 典型算法有国外的g o d i n 算法f m 。国内研究者后来也相应地提出了一些改进算法 以提高概念格的构造效率，例如基于属性的概念格渐进式生成算法h 引，利用数 据库技术对概念格构造算法的改进引，基于剪枝的概念格渐进式构造卜i 州等。 8 生直太堂亟堂焦i 佥童 箍= 童绪论 g o d i n 算法取得了良好的效果并被广泛采用和进行分析，但是它仍存在着不 足，需要改善。针对其问题，本文给出一种改进的概念格渐进式构造算法。概念 格的渐进式构造算法的思想是在原始概念格的基础上通过新增对象来对原始概 念格进行更新产生新的概念格，通过扫描更新后的概念格就可以得到新的频繁项 集或最大频繁项集，进一步产生新的关联规则。基于概念格这一特点，提出将概 念格应用到w e b 日志挖掘来进行模式发现，并在此基础上可以进行增量挖掘以实 现模式库的更新，为智能w e b 服务的实现提供有力的依据。 1 3 论文组织 全文组织如下： 第一章绪论。本章详细阐述论文的研究背景、研究意义及研究现状。 第二章w e bd 志挖掘过程的研究。本章研究w e bf l 志挖掘过程中各环节的 关键技术，包括从数据预处理、模式发现、模式分析。重点研究数据预处理和模 式发现。首先，研究数据预处理的步骤，分析预处理阶段的各项任务，针对数据 预处理过程中涉及到的关键问题和技术进行分析，然后，研究w e b 日志挖掘模式 发现的各种方法和技术。 第三章概念格及其构造算法的改进。本章介绍概念格的相关知识，重点研 究概念格的渐进式构造算法，通过分析g o d i n 算法的不足，提出一种改进的概念 格渐进式构造算法。 第四章w e b 志挖掘模式发现的研究。本章重点讨论增量挖掘问题及关联 规则生成方法的优化，基于这两个方面，将概念格应用到w e b 日志挖掘的模式发 现，研究基于概念格的页面关联规则挖掘，可提高挖掘效率以及实现增量挖掘。 第五章总结。总结研究工作，并提出进一步的研究方向。 9 生直叁堂亟堂焦逾塞麓三重鳖b 旦盛控坦过攫的砑宜 第二章w e b 日志挖掘过程的研究 随着w e b 技术的快速发展，w e b 上积累了大量的数据，在这些数据背后隐含 着重要的知识。如何从w e b 数据中提取出有用的信息，己成为当今计算机应用领 域研究的一个热点课题。w e b 上大量的信息是以非结构化或半结构化的形式表现 出来的，而数据挖掘需要结构化的数据。w e b 服务器日志具有完整的数据结构， 正好有利于数据挖掘的进行，即w e b 日志挖掘。w e b 日志挖掘通过分析w e b 日志 发现用户的访问行为知识，从而可以应用到个性化服务、站点改进以及商业智能 等方面。 本章将研究w e b 日志挖掘的整个过程，讨论w e b 日志挖掘的数据来源，分析 w e b 服务器同志，给出w e b e l 志挖掘模型，研究数据预处理的各个步骤和w e b 日 志挖掘模式发现方法和技术。 2 1 数据来源 w e b 志挖掘从用户访问w e b 时所留下的访问记录中提取出隐含的，有价值 的知识。用户访问记录就是与w e b 相关的日志文件，它的由来取决于w e b 的体系 结构及其工作原理，如图2 1 所示，w e b 的结构是基于客户，服务器模式，包括三 个层次：客户端、代理服务器和、b 服务器。当用户访问w e b 站点的时候，它们 都会记录用户的访问信息，从而产生w e b f 志。因此，它们成为w e b 日志挖掘的 主要数据来源。 健用代理曩备时的倍息范啼不幢甩代理晨务量时的信息蠢 图2 - 1w e b 日志挖掘的数据来源 o 虫亩厶堂亟堂僮途塞筮三重监目盔丝塑过程的蛆荭 w e b 服务器端的访问数据：网站的页面内容及其链接关系、服务器日志、与 网站服务相关的数据库数据、网站用户的注册信息和c o o k e 等。站点中的动态和 静态页面为用户传达了网站为用户提供的信息，w e b n 艮务器在响应用户的请求 时，将用户的请求动作记录在服务器的日志文件中。从服务器与用户的浏览关系 中可以看出，服务器端记录的是多用户单站点的信息。 客户端的访问数据：记录了单个用户在其整个浏览过程中的行为数据，用户 的浏览过程一般涉及多个站点，因此客户端收集的是单用户一多站点的信息。客 户端的c h e 记录了用户访问内容。 代理服务器端的访问数据：代理服务器介于客户端和服务器之间，它接收客 户端的请求，并为客户从服务器端取回相应的页面，最后将页面返回给客户端。 由于代理服务器一般为多个用户提供代理服务，它可以提供多用户多站点的信 息。 w e b 服务器日志是一种w e b 服务器端的访问信息，由w e b 服务器所产生。为 了方便，我们将w e b 服务器日志简称为w c b 日志。当用户需要访问一个w e b 站点 的时候，就会使用浏览器发送请求给w e b n 鼹务器，w e b h 艮务器接收请求后就会做 出响应，将用户所请求的资源发送给用户，这时网页就通过浏览器显示在用户面 前，同时，w c b 服务器还会将用户访问本站点的信息保存下来，这些访问信息就 形成了w e b 日志 根据w 3 c 组织规定，w e b 服务器日志具有两种格式：通用日志格式( c o m m o n l o gf o r m a t ，c l f ) 和扩展型日志格式( e x t e n d e dl o gf o r m a t ，e l f ) ”“。c l f 只包 含固定的几个属性，而e l f 包含了可以配置对安全分析有帮助的很多扩展属性， 可以使日志记录更加详细，安全环境中的首选日志类型为e l f ，但是这样也可能 增加大量的与挖掘无关的数据而使数据清洗过程时间较长。下面我们主要介绍 e l f 格式的w e b 日志。 w e b 日志以文件的形式保存，扩展名为1 0 9 ，通常以天为单位记录日志，所 以，文件名通常为e x ( 年份) ( 月份) ( 日期) 。例如，e x 0 0 1 0 2 3 1 0 9 记录y 2 0 0 0 年l o 月2 3 日产生的日志，即它记录了这一天访问该站点的所有用户的访问情况。 那么这些情况到底是什么样的呢? 如图2 2 所示。 第一行s o f t w a r e 表示w c b 服务器软件是i i s 5 0 ，第二行v e r s i o n 是日志文件格 式的版本，第三行d a t e 是日志启动的时间，第四行f i e l d s 是w e b 日志的属性，第 六行和第七行就是一条日志记录，其中它的每一项都对应f i e l d s 的每一个属性， 如2 0 0 5 0 1 0 3 对应d a t e 属性，2 0 ：0 4 ：4 0 对应t i m e 属性等等，“- ”表示该属性没有值 对应。这条日志就表示了2 0 0 5 年1 月3 日，i p 地址为1 7 2 1 6 3 0 5 2 的用户访问了i p 为2 1 1 6 6 1 8 4 3 5 服务器上的一个页面i n d e x a s p 。 史直左堂亟堂位j 佥塞筮三童鳖旦壶挖掘过程鲍班宜 图2 - 2w e b 日志文件 由此可见，w e b 日志记录包含多个属性，但是这些扩展属性不是固定的，还 可以根据具体的需要将其它一些扩展属性包含进来，这要通过在i i s 中进行配置。 扩展属性如图2 3 所示： 图2 - 3w e b 日志属性 w e b 服务器在响应用户的请求时，将用户请求的文件发送出去的同时把这 次请求写入日志，所以w e b 服务器日志记录了用户访问本站点的信息。一般分 三部分：访问同志( a c c e s sl o g ) ，代理只志( a g e n tl o g ) ，引用日志( r e f e r r e r l o g ) 。访问日志主要记录基本的请求信息，包括：用户的i p 地址、时间、方法 ( 如g e t 、p o s t ) 、被请求文件的u r l 、超文本传输协议( h 1 _ r p ) 的版本号、 返回码( 请求的状态，成功或错误码) 、传输字节数等等。代理日志记录的是用 户使用的操作系统以及浏览器类型。引用日志记录了用户的请求是来自那个页 面。 1 2 主直_ 丈堂亟堂僮i 金塞筮三童鳖b 目盔挖掘过摧的硒殛 2 2w e b 日志挖掘模型 w e b 日志挖掘的主要任务是通过对w e b 日志进行处理和分析来提取隐藏在 日志数据背后的用户对w e b 站点的访问行为、特征等有价值的信息。因此，和 其他数据挖掘处理过程一样，w e b 日志挖掘也需要经过数据预处理、模式发现 和模式分析，如图2 _ 4 所示。 图2 - 4w e b 日志挖掘模型 数据预处理是根据挖掘的目的，对原始w e b 日志文件中的数据进行提取、 分解、合并，最后转化为适合进行数据挖掘的数据格式，并保存到关系型数据库 表或数据仓库中，等待进一步处理：模式发现是指运用各种算法对处理后的数据 进行挖掘，生成用户访问模式；模式分析是对用户访问模式进行分析，从而将有 价值的模式提取出来。 2 3 数据预处理 数据预处理是进行w e b 日志挖掘的前提和关键环节。由于w e b 本身的开放 性、动态性及h t t p 协议的不确定性，使得丰富的日志信息用于挖掘时必须先经过 数据预处理才能保证挖掘结果的有效性和准确性 4 7 1 。因为原始w e b 日志数据一 般存在着缺失、错误、噪音等，将直接影响到后续挖掘工作的结果质量，所以， 数据预处理的目的就是将w e b 日志转化为可靠、完整、准确的数据源，以满足 w e b 日志挖掘过程中实施挖掘的需要。w e b 日志挖掘的数据预处理一般要经过 数据清理、用户识别、会话识别、路径补充等步骤。本章将对w e b 日志挖掘的 数据预处理实施过程进行详细的探讨。 生赢太堂亟鲎僮论奎 篮三童盐b 旦：蒸挖坦过程的盟冠 2 3 1 数据清洗 数据清洗阶段是必需的，数据清洗操作应该结合网站的情况与挖掘的任务来 具体实施，它取决于整个分析过程的意图及目标。 数据清洗又称为数据清理、数据精简、数据净化。它主要是指删除w e b 日 志中与挖掘不相关的冗余项。删除无用的数据，对w e b 数据挖掘来说是十分重 要的，因为只有能正确反映用户访问模式的日志数据，才能挖掘出准确有用的知 识，以及得到有意义的结果。在一个中等规模的服务器上，访问日志文件每天能 轻易地达到数十兆字节，如果不做初始清理工作，将会导致挖掘过程极为缓慢且 低效。 由于原始日志以文本形式保存，且各属性之问没有用符号分隔开来，不利于 直接导入s q l s e r v e r 数据库，所以先要对原始日志文件进行处理，再利用数