（计算机应用技术专业论文）基于粗糙集的web日志挖掘研究(1).pdf

硕士学位论文 摘要 随着i n t e r n e t 的迅猛发展，使得w o r l dw i d ew e b 已经深入到社会生活的方方 面面。w e b 已经发展成为拥有数十亿页面，蕴涵着具有巨大潜在价值的分布式信 息空间。人们迫切需要从这些海量的数据中查找出对自己有用的信息，对数据挖 掘研究提出了新的挑战。w 曲数据挖掘是一种将传统数据挖掘与w e b 结合起来的 技术，它将随着i n t e r n e t 的发展越来越受到各方面的关注。 。 本文工作主要包括以下几个方面： 首先，w e bh 志挖掘数据预处理。w e b 数据复杂多样，首先需要确定研究对 象，w e bf l 志挖掘的对象不是网络上的原始数据而是从用户和网络交互过程中抽 取出来的第二手数据，它包括所请求的u r l 、发出请求的i p 地址和时削戳等，这 些数据提供了有关用户访问的丰富信息。本文在这部分的研究重点是如何提取有 关用户访问的特征( 如用户的访问行为、频度、内容等) ，以及建立基于用户访问 行为的数据模型。 其次，基于粗糙集理论的w e b 同志挖掘。以前的方法对w e b 同志数据库中潜 在信息的挖掘采用先将数据组织成传统的数据挖掘方法能够处理的数据模型，然 后用数据挖掘算法( 如关联规则算法等) 进行处理。这干叶，方法虽然暂时解决了w e b 挖掘的需求但是对于w e b 数据库来说不能满足其动态增长的需要。在粗糙集理论 中，知识被看成是一种分类能力，即在域上构造分区的能力。本文在基于粗糙集 理论的思想上对预处理后的数据进行离散化，并建立了一种新的数据模型，最后 改进约简算法并约简提取出稳定的分类规则。同时考虑到不一致规则的存在，还 研究了缺省情况下如何获得决策规则。 最后，对本论文的内容进行了总结，并对下一步日志挖掘研究进行了展望。 关键字：数据挖掘；w e b 日志挖掘；粗糙集；决策规则；预处理 基于粗糙集的w e b 同忐挖掘研究 a b s t r a c t a c c o n l p a n y i n gw i t ht h eq u i c kd e v e l o p m e n to ft h ei n t e r n e t ，w o r l dw i d e 、e bh a s a l r e a d yb e e nr e l a t e dt oe v e r ya s p e c t so fs o c i a ll i f e 、e bh a sd e v e l o p e dt ob ea d i s t r i b u t e di n f o r m a t i o ns p a c ew h i c ho w n sb i l l i o n so fw e b s i t e sa n dc o n t a i n sk n o w l e d g e o fg r e a ta n dp o t e n t i a lv a l u e t h a tp e o p l ew a n tl o o kf o rt h eu s e f u li n f o r m a t i o nt h e y n e e di nt h er i c hd a t a b a s e ，p r o v i d e sn e wc h a l l e n g ef o rt h er e s e a r c ho nd a t am i n i n g w e b d a t am i n i n gi sak i n do ft e c h n i q u ec o m b i n i n gt r a d i t i o n a ld a t am i n i n ga n dw e bd a t a ， w h i c hw i l lg a i nm o r ea t t e n t i o nf r o ma i lt h ea s p e c t sa l o n gw i t ht h ed e v e l o p m e n to ft h e i n t e r n e t t h ep a p e rm a i n l yi n c l u d e ss e v e r a la s p e c t s ： f i r s t l y ，t h ed a t ap r e t r e a t m e n to fw e bl o gm i n i n g t h ew e bd a t ai sc o m p l e xa n d v a “o u s f i r s tw em u s td e t e r m i n et h er e s e a r c ho b j e c t t h co b j e c to fw e bl o gm i n i n gi s n o tt h eo r i g i n a ld a t ao nt h ew e bb u tt h es e c o n d h a n dd a t aa b s t r a c t e df j o mt h e i n t e r a c t i v ep r o c e s so fu s e r sa n dt h ei n t e r n e t ，w h i c hi n c l u d e st h ea p p e a l e du r l ，t h e a p p e a l i n gi pa n dt h et i m es t a b ，e t c a l lt h e s el o g so f f 色rr i c hi n f o r m a t i o na b o u tu s e r s v i s i t s t h er e s e a r c hf o c a lp o i n to ft h i sp a r ti nt h ep a p e ri sh o wt og e tt h ec h a r a c t e r i s t i c s o ft h ev i s i t s ( s u c ha sb e h a v i o r s ，f r e q u e n cy c o n t e n t ，e t c o fu s e r s v i s i t s ) a n dt o e s t a b l i s ht h ed a t am o d e lb a s e do nt h eb e h a v i o r so fu s e r s v i s i t s s e c o n d l y ，t h er e s e a r c ho fr o u g hs e t t h ef o r m e rw a yo fm i n i n gt h ep o t e n t i a l i n f o r m a t i o ni nt h ew e bl o gd a t a b a s ei st ot r a n s f o r mt h ed a t ai m oad a t am o d e lw h i c h c a nb em a n i p u l a t e db yt h et r a d i t i o n a ld a t am i n i n ga n dt h e nm a n i p u l a t et h e mb yd a t a m i n i n gt e c h n i q u e ( s u c ha sm ea l g o r i t h mo fa s s o c i a t i o nr u l e ) a l t h o u 曲t h i sw a ym e e t s t h en e e d so fw e bm i n i n gt e m p o r a r i l y ，i tc a nn o ts a t i s f yi t sd y n a m i ci n c r e a s i n gd e m a n d i nr o u g hs e t ，k n o w l e d g ei sc o n s i d e r e da sa na b i l i t yo fc l a s s i f i c a t i o n ，w h i c hi st h e a b i l i t yo fc o n s t r u c t i n gp a r t i t i o ni nt h ed o m a i n a c c o r d i n gt ot h et h o u g h t so fr o u g hs e t ， t h ep a p e rr e s e a r c h e st h ed i s p e r s i v e n e s so fp r e t r e a t e dd a t a ，s e t su pan e wd a t am o d e l a n di m p r o v e sr e d u c t i o na l g o r i t h ma ：n da b s t r a c t st h es t a t i cf u l eo fc l a s s i f i c a t i o n u l t i m a t e l y a tt h es a m et i m e ，i tt a k e si n t oa c c o u n tt h ee x i s t e n c eo ft l l ei n c o h e r e n c er u l e a n di tr e s e a r c h e so nh o wt oa c h i e v et h ed e c i s i o nr u l eo nt h ea b s e n to c c a s i o n f i n a l l y ，t h ep a p e rm a k e sac o n c l u s i o na n do p e n san e wp r o s p e c tt ot h en e x ts t e po f l o gm i n i n g k e yw a r d s ：d a t am i n i n g ；w 曲l o gm i n i n g ；r o u g es e t ；d e c i s i o nr u l e ；p r e t r e a t m e n t i i 兰州理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 己在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：_ 侈鑫1 舅日期：p 口午圭月a 6 同 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权兰州理工大学可以将本学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密日。 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 椰鑫毋 、。、 ( 岔扣 日期：n 。6 年f 月0 曰 日期：0 2 。o 年奎月孙f i 硕士学位论文 1 。1 引言 第1 章绪论 随着计算机技术的发展，计算机已经融入了现代社会的点点滴滴。计算机在 社会各领域的广泛深入应用，数量日益增氏的各种数据成为当今数字化社会的宝 贵资源，同时又对数据的处理与共享提出了一个极具挑战性的问题。 1 9 8 9 年，为了支持在多个研究机构之间的合作研究，欧洲核物理实验室 ( e u r o p e a nl a b o r a t o r yf o rp a r t i c i ep h v s i c s ，c e r n ) 的t i mb e m e r s l e e 领导开发了 w w w ( w o r l dw i d ew e b ) ，随后很快得到广泛应用。w e b 技术极大推动了i n t e m e t 的发展，成为了i n t e m e t i n t r a n e t 最主要的信息服务。w e b 技术的出现不但改变了 网络的应用方式，为用户提供了友好访问i n t e r n e t 资源的窗口，更重要的是它提供 了全新的刚络信息平台，为全球广阔的数据资源提供了歼放的访问接口，实现了 信息的大范围共享。 今天，w w w 已成为了网络信息的基础平台，它升i 但存放了人量的企业、政 府机关的数据，而且成为了个人信息系统( p e r s o n a li n f o r m a t i o ns y s t e m ) 的平台， 这些都促使w w w 中的数据量呈爆炸性增长，面对大量的g b 级、t b 级甚至更多 的数据，如何有效地提取出其中蕴含的有价值的知识和信息就变得具有重要意义。 在这样的背景下，产生了w 曲数据挖掘技术。利用w e b 数据挖掘技术可以从w 曲 数据中发现用户感兴趣的信息。跟踪、分析用户的访问模式，帮助用户更有效的 浏览广阔的w w w 。 目前，w 曲数据挖掘技术成为了w 曲信息发现研究方面一个重要的课题，是 一个新兴的具有广泛应用前景的研究领域。它可以广泛的应用在搜索引擎、智能 查询、个人网络助理等网络信息发现领域，还可以帮助网站的管理员更好的管理 自己的网站，帮助用户更有效的浏览w e b 。w 曲数据挖掘被视为一项回报率极高 的重要应用技术。学术界和产业界对其高度重视，世界各国都投入了大量的人力 物力进行研究、开发，目前己取得了一定的进展，其研究和应用前途不可限量。 1 2 从数据挖掘到w e b 挖掘 1 2 1 数据挖掘概述 数据挖掘( d a t a m i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机的 数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识 的过程。在信息爆炸的当今时代，信息过量几乎成为人人需要面对的问题。数据 基于粗糙集的w e b 日志挖掘研究 挖掘和知识发现是处理此类问题的有效手段。数据挖掘技术从一开始就是面向应 用的，其应用范围涉及社会的所有领域，在商业上的应用尤其受到重视。典型的 应用有：遇过分析超市交易数据，安排货架上的货物摆放及开展促销计划以提高 销售；税务局分析不同团体交所得税的记录，发现异常模型和趋势：信用卡公司 分析信用卡历史数据，进行风险判断等。在保险公司、汽车公司、人才中心、广 告公司、统计局等部门，数据挖掘都可以发挥重要的作用。因为其广泛的应用价 值，数据挖掘学科领域汇聚了不同领域的研究者，尤其是数据库、人：i i 智能、数 理统计、可视化、并行计算等方面的大量学者和工程技术人员，使得它在短短几 年内，就在理论上取得了重大进展。到目前为止，针对不同的应用需求，已研究 出大量的算法、应用工具及相应的评价体系。数据挖掘技术已经进入了空前的发 展阶段。 不同的应用背景所面对的挖掘任务不同，采取的挖掘方法也有所不同。近年 来，不同领域研究者研究出的大量的算法，从理论上保证了应用的实施。数据挖 掘根据挖掘任务不同，可分为分类或预测模型发现、数据总结、聚类、关联规则 发现、序列模式发现、依赖关系或依赖模型发现、异常和趋势发现等等。挖掘方 法一般u 丁分为：机器学习方法、统计方法、神经网络方法和数据库方法等。机器 学习方法包括归纳学习方法( 决策树、规则归纳等) 、基于范例学习、遗传算法等。 统计方法中有：回归分析( 多元回归、自回归等) 、判别分析( 贝叶斯判别、费歇尔 判别、非参数判别等) 、聚类分析( 系统聚类、动态聚类等) 、探索性分析( 主元分析 法、相关分析法等) 等。神经网络方法又可细分为：丽向神经网络( b p 算法等1 、自 组织神经网络( 自组织特征映射、竞争学习等) 等。数据库方法主要是多维数据分析 或o l a p 方法，另外还有面向属性的归纳方法等。 1 2 2w e b 挖掘概述 i n t e r n e t 目前是一个巨大的、分布广泛的和全球性的信息服务中心，它涉及新 闻、广告、金融、教育、政府、电子商务和许多其他信息服务。w e b 还包括了丰 富和动态的超链接信息，以及w 曲页面的访问和使用信息。面对w e b 丰富的内容， 巨大的数据量，加之由于万维网分布、动态、海量、异质、复杂、开放性的特点， 人们如何从这海量的数据中，查找自己想要的数据和有用信息，迫切需要种新 的技术能自动的从w e b 上发现、抽取和过滤信息。因此出现了w 曲挖掘技术。 w e b 挖掘是一项综合技术，涉及w e b 数据、数据挖掘、计算机语言学、信息 学等多个领域。不同研究者从自身的领域出发，对网络信息的含义有着不同的理 解，项目开发也各有其侧重点。例如，国外有人认为：w e b 挖掘就是利用数据挖 掘技术，自动的从网络文档以及服务中发现和抽取信息的过程。国内说法也很多， 有学者将网络环境下的数据挖掘归入网络信息检索与网络信息内容的开发。也有 硕士学位论文 学者站在信息服务的角度上提出“w 曲挖掘”，指出其有别于传统的信息检索，能 够在异构数据组成的分布式信息库中，从概念及相关因素的延伸比较上找出用户 需要的深层次的信息，并提出w e b 挖掘将改变传统的信息服务方式而形成一个全 新的适合网络时代要求的信息服务组合。w 曲数据挖掘是以从w e b 上挖掘有用知 识为目标，以数据挖掘、文本挖掘、多媒体挖掘为基础，并综合运用计算机网络、 数据库与数据仓库、人工智能、信息检索、可视化、自然语言理解等技术，将传 统的数据挖掘技术与w 曲结合起来的新型技术【2 j 。 可以一般地将w 曲挖掘定义为：w e b 挖掘是指从大量w e b 文档的集合c 中发 现隐含的模式p 。如果将c 看作输入，将p 看作输出，那么w e b 挖掘的过程就是 从输入到输出的一个映射i ：c p 。w e b 挖掘从数据挖掘发展而来，因此其定义与 我们熟知的数据挖掘定义相类似。但是，w e b 挖掘与传统的数据挖掘相比有许多 独特之处。首先，w e b 挖掘的对象是大量、异质、分布的w e b 文档。我们认为， 以w e b 作为中问件对数据库进行挖掘，以及对w e b 服务器e 的日志、用户信息等 数据所开展的挖掘工作，仍属于传统的数据挖掘的范畴。其次，w e b 在逻辑上是 一个由文档节点和超链接构成的图，因此w e b 挖掘所得到的模式可能是关于w e b 内容的，也可能是关于w e b 结构的。此外，由于w e b 文档本身是半结构化或无结 构的，且缺乏机器可理解的语义，而数据挖掘的对象局限于数据库中的结构化数 据，并利用关系表格等存储结构来发现知识，因此有些数据挖掘技术并不适用于 w 曲挖掘，即使可用也需要建立在对w e b 文档进行预处理的基础之上。这样，开 发新的w 曲挖掘技术，以及对w 曲文档进行预处理以得到关于文档的特征表示， 便成为w e b 挖掘研究的重点。 1 2 2 1w e b 挖掘面临的挑战 w 曲挖掘可在多方面发挥作用，如改进和提高搜索引擎的质量和效率、确定 权威页面、w e b 文档分类、w e bl 0 2 挖掘、智能查询、建立m e t a w e b 数据仓库等。 w w w 是一个巨大、分布广泛、全球性的信息服务中心，涉及教育、新闻、广告、 娱乐、金融、保险等信息服务，内容极其丰富。对w 曲进行有效的信息抽取和知 识发现具有极大的挑战性，会面临很多具体问题，主要有： 1 对感兴趣的信息仅限于利用各种搜索引擎进行查找，但是搜索效果很差。 尽管业界开发了很多搜索引擎，但其检索性能和服务质量并不令人满意。主 要表现在：检索方式单一，检索时间长，检索结果质量差，难以精确表达用户需 求，无法适应用户群体的多样性；检索召回率和精度低。低查准率( 精度) 导致 引擎返回的检索结果中往往含有大量无关信息。有用信息匮乏，用户难以得到真 正感兴趣或有用的信息。低查全率( 召回率) 导致很多相关的文档查不到；搜索 信息的更新周期较长，无法适应信息的快速增长；缺乏检索导航信息，用户无法 基于粗糙集的w e b 日志挖掘研究 顺利、快速地从巨大的信息网络中找到目标信息；定制服务能力差。不能根据用 户多样化的需求，自动地、最大程度地满足用户的需求；主动服务和个性化服务 能力差。 2 w e b 页面结构复杂。 w e b 页面以某种格式( h t m l 或x m l ) 呈现的半结构化数据( s e m i s t r u c t u r e d d a t a ) ，其数据结构不规则( i r r e g u l a r ) 或不完整( i n c o m p l e t e ) ，复杂程度远远高于 普通的文本文档，其数据结构隐含、模式信息量大、模式变化快。大量的文档无 任何排列次序，无分类索引。 3 w e b 信息丰富，难以搜索。 w 曲是一个异质、分布、动态的信息源，w 曲数据的更新、增长速度极快， 也无固定的模式。w e b 上的信息几乎都是隐藏的、潜在的、未知的，从w e b 上发 现这些未知的信息和有用的模式，仪用传统的基于关键字的检索方式很难实现， 现在的搜索引擎尚不具备这些功能。 4 w e b 数据增长过快，很难集成数据。 目前w c b 上的数据以t b 数量级计算，且在迅速地增长，能否构建以及如何 构建一个庞大的数据仓库把w e b 上所有分布和异质的数据集成在起，f 1 前技术 上来讲这是非常凼难的工作。最近，有些研究工作在致力于存储和集成w e b 上的 所有数据。例如在h t t p ：w w w a r c h i v e o r g i n d e x h t m l 下，可访问到一个臣大的数十 兆兆字节的因特网存档。 5 如何实现个性化服务。 不同的用户访问w e b 的兴趣、爱好和使用目的t 差万别，面对一个非常。泛 的用户群体，能否使用户根据自己的爱好兴趣定制网页，甚至w 曲s e r v e r 能否根 据发现的用户p r o f i l e 自动为用户定制网页，从而提供个性化的信息检索和查询服 务。 6 信息利用率低。 网络上信息储备量极大且信息内容十分丰富，但信息的利用率很低。w e b 上 的信息对用户个人而言，被使用到的只是极小的一部分，其余信息对用户来说是 不感兴趣的。 这些问题推动了如何有效且高效地发现和充分利用i n t e r n e t 上资源的研究工 作。万维网的分布、动态、海量、异质、变化、开放性的特点，网页内容的半结 构化特征决定了w e b 挖掘比传统的k d d 和以关键字搜索为主的信息检索问题更 为复杂和困难，很多问题甚至是n p - h a r d 问题。解决w 曲挖掘问题需要有新的数 据模型、体系结构和算法等，在理论上、方法上要有新的突破，要求有更高级的 w e b 信息处理技术【3 1 。 4 硕士学位论文 1 2 2 2w e b 挖掘产品 在过去的几年里，建立了不少w e b 挖掘系统【4 】，其中有代表性和比较成熟的 有以下3 种： n e tp e r c e p t i o n 公司：主要产品是n e tp e r c e p t i o n s ，它采用了一个叫做实时建 议的技术：让它的产品对象( 主要是网站) 能够根据用户以往的浏览行为，在其他用 户中找出与其相类似的浏览行为，根据这些用户的浏览行为来预测该用户以后的 浏览行为，从而为用户提供个性化的浏览建议，并且它是实时运行的，随着浏览 量的增加，它会变得越来越聪明。 a c c r u e 公司：软件采用开放式标准，能够适合任何公司在电子商务方面的需 求。主要有两大产品：a c c r u ei n s i g h t 和a c c r u eh i tl i s t ，前者主要是帮助顾客解 次电子商务方面的问题，后者主要用于网站流量分析。a c c r u ei n s i g h t5 是公司的 主打产品，它是一个综合性的w e b 分析工具，它能够对网站的运行状况进行深入、 细致和准确的分析，以顾客为中心设计，通过分析顾客的行为模式，帮助网站采 取措施来提高顾客对于网站的忠诚度。利用了多种w e b 数据收集方法，而不是像 很多网站那样仅仅分析l o g 文件。其中a d v a n c e dn e t w o r kc o l l e c t o r 方法以其能收 集到最大量的数据而著称。a c c r u eh i tl i s t 4 5 1 是一个功能强大的w e b 报表分析 工具，适合于中型网站，主要运用于市场分析、搜索引擎、广告等方面。 w e bt r e n d s 公司：重要产品是c o m m e r c et r e n d s3 0 ，被宣称为第一个用于 v r m ( v i s i t o rr e l a t i o n s h i pm a n a g e m e n t ) 的平台。它能够让电子商务网站更好地理解 其网站访问者的行为，帮助网站采取一些行动来将访问者变为忠实顾客。主要由 四部分组成：报表生成服务器：提供w e b 流量信息。报表能够自动生成，也可以 定制，有统计功能；c 咖p a i n a n a l y z e r ：网站的浏览者或者是看一眼就走，或者表 现出很强烈的兴趣，网站的经营管理者可以根据这些差别用我们的产品找出原因， 从而制订正确的市场战略；w 曲h o u s e b u i l d e r ：提供访问者的行为模式数据；0 l a p m a n a g e r ：深入的流量分析。能运行于不同环境如：s u ns o l a r i s ， r e dh a t l i n u x ， m i c r o s o f tw i n d o w s2 0 0 0 ，n t 平台，支持0 r a c l e8 i 和微软的s q l 7 0 。 1 3w e b 挖掘的研究现状 w c b 数据有三种类型：w e b 内容数据，如h t m l 或x m l 标记的w e b 文档； w e b 结构数据，如w e b 文档内的超链接；用户访问数据，如服务器l o g 日志信息。 相应地，w e b 挖掘也分成三类：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 e m i n i n g ) 和w e b 日志挖掘( w e b l o g m i n i n g ) ，如图1 1 所示。 1 3 1w e b 内容挖掘 w 曲内容挖掘是从w 曲页面内容及其描述信息中获取潜在的，有价值的知识 基于粗糙集的w e b 日志挖掘研究 或模式的过程。主要的方法有i r ( i n f o r m a t i o nr e t r i e v e ) 方法和数据库方法。w e b 内容挖掘主要是针对各种非结构化的数据，如文本数据、音频数据、视频数据以 及图形图像数据等各种数据相融合的多媒体数据【5j 。w e b 内容挖掘又可分为基于 文本信息的挖掘和基于多媒体信息的挖掘两种数据挖掘方式： 1 基于文本信息的挖掘。 w 曲内容挖掘多为这种方式的挖掘，它和文本挖掘功能及方法比较类似。因 此，文本挖掘的方法也可用于w e b 文本的挖掘。w e b 文档多为h t m l 、x m l 等语 占，故可用w e b 文档中的标记，如 、 等额外信息来提高w e b 文 本挖掘的性能。在对w e b 文档进行分类分析中，可以基于一组预先分好类的文档， 从预定义好的分类目录中为每个文档赋予一个类标签，如y a h o o ! 的文档及其相关 文档可以作为训练集，用于导出w e b 文档的分类模式，这一模式可以分类新的 w 曲文档。由于超链接罩包含了有关页面内容的高质量信息，故可以利用这些信 息对w e b 文档进行分类，并且这种分类比基j ：关键字的分类方法更准确、更完美。 w e b 挖掘 w 曲内容 挖掘 w 曲结构 挖掘 w 曲日志 挖掘 文本l 多媒体li 超链接ll 页而结构i l 用户访问l1 分析定制 挖掘挖掘挖掘挖掘l 模式挖掘lw e b 站点 图1 1w e b 挖掘的分类 2 基于多媒体信息的挖掘。 随着网络带宽的不断加大，多媒体信息在网上迅速增加，这对基于多媒体信 息的挖掘提出了要求。基丁多媒体信息的挖掘主要是指基于音频的挖掘、基于图 片的静态图像的挖掘和基于视频的动态图像的挖掘。 1 3 2w e b 结构挖掘 w 曲结构挖掘是从w w w 的组织结构和链接关系中推导知识。主要的方法有 p a g er a n k 【6 j 和c l e v e r 【”。w e b 结构挖掘通过分析一个网页链接和被链接的网页 数量和对象，建立w 色b 自身的链接结构模式，这种模式可以用于网页归类，并由 此获得有关不同页面问相似度和关联度的信息。w e b 结构挖掘有助于用户找到相 关主题的权威站点和指向众多权威站点的相关主题站点。搜索某个给定话题的 w c b 页面时，不仅希望得到相关的w 曲页面而且希望得到该w 曲页面是否为权威 6 硕士学位论文 的w 曲页面，即检索到的页面具有高质量或对该主题具有权威性。w 曲页面不仅 由页面构成，而且还包括从一个页面指向另一个页面的超链接。超链接里包含了 大量人类潜在的语义，它有助于自动分析出权威性语义。当一个w c b 页面的作者 建立指向另一个页面的指针时，可以看作是作者对另一个页面的注解，即对另一 个页面的认可。把一个页面的来自不同作者的注解收集起来，可以用来反映页面 的重要性。因此，可以通过这种方法来寻找权威w 曲页面。 w 曲链接结构具有如下局限性：不是每个超链接都代表寻找的认可，有些是 为了其他目的而创建的，如为了导航或付费广告等。总体上，若大部分超链接具 有认可性质，就可以用于权威判断；基于商业或竞争的考虑，很少有w e b 页面指 向其竞争领域的权威页面，如可口可乐就不会链接到其竞争对手百事司乐的w 曲 页面上；权威页面很少具有特别的描述，如y a h o o ! 主页就不会明确给出“w e b 搜索引擎”之类的自描述信息。所以人们提出了另一种重要的w e b 页面一h u b 页 面。h u b 页面是指一个或多个w 曲页面，它提供了指向权威页面的链接集合。对 于一个h u b 页面来说，它本身可能并不突出，但是却提供了指向某个话题的权威 页面的链接。可见h u b 页面起到隐含说明某话题权威页而的作用。通常好的h u b 页而指向许多好的权威页面，好的权威页面则有好的h u b 页面指向。这样町以用 h u b 页面和权威页面之间的这种相互作用，来挖掘权威页面和自动发现高质量的 w 曲结构和资源。 1 _ 3 3w e b 日志挖掘 w e b 日志挖掘是对用户访问w e b 时在服务器方留下的访问记录进行挖掘。它 通过挖掘w e b 日志文件及其相关数据来发现用户访问w 曲页面的模式，主要的方 法有c 0 0 k i e s 和远程a g e n t 技术。w e b 使用记录挖掘的对象不是网上的原始数据而 是从用户和网络的交互过程中抽取出来的第二手数据。正如我们所知道的那样， 因特网上的用户一旦连接到一个服务器上，就会在这个服务器上留下一个“脚印”， 这就是服务器上的同志文件，它包括所请求的u r l 、发出请求的i p 地址和时间戳， 这些日志记录提供了有关w 曲用户访问的丰富信息。因此，可以通过对用户留下 的这些日志文件进行挖掘，提取有关用户访问的知识。对用户的访问行为、频度、 内容等进行分析得到关于用户的行为和方式的模式，从而改进站点的结构或为用 户提供个性化服务。有关这方面的研究方向有：一般的访问模式追踪，它通过分 析使用记录来了解用户的访问模式和倾向，从而改进站点的组织结构；个性化的 访问模式追踪，它倾向于分析单个用户的偏好，其目的是根据不同用户的访问模 式来为每个用户提供个性化的页面，开展有针对性的服务以满足用户的需求。 基于租糙集的w e b 日志挖掘研究 1 4 粗糙集理论的研究现状 粗糙集理论是由波兰学者p a w l a k ，z 在1 9 8 2 年提出的，由于最初的研究大多是 以波兰文字发表在“b u l l e t i no f t h ep 0 1 i s ha c a d e m yo fs c i e n c e s ：m a t h e m a t i c s ”上， 所以该项研究当时并未引起国际计算机学界的重视，研究地域也仅限于东欧各国。 后在8 0 年代末9 0 年代初，该理论才引起了世界各国学者的注意。特别是1 9 9 1 年 p a w l a k ，z 发表了专著r o u 曲s e t ：t h e o r e t i c a la s p e c t so fr e a s o n i n ga b o u td a t a ，系 统全面地阐述了粗糙集理论，奠定了严密的数学基础，从而掀起了粗糙集的研究高 潮。该书与1 9 9 2 年出版的粗糙集理论应用专集较好地总结了这一时期该理论与实 践的研究成果，促进了它的进一步发展，现已成为学习和应用粗糙集理论的重要文 献。从1 9 9 2 年至今，每年都召开以粗糙集理论为主题的固际会议，推动了该理论的 拓展和应用。目前已成为人工智能领域中一个较新的学术热点，引起了越束越多的 科研人员的关注。 1 9 9 2 年在波兰k i e k r zd 开了第1 届国际粗糙集讨论会。这次会议主要讨论了 集合近似定义的基本思想及其应用，其巾粗糙集环境下机器学习的基础研究是这 次会议的四个专题之一。但参加这次会议的研究者较少，范围也不太j 。泛。这次 会议选出15 篇论文刊髅侄“f o u n d a t i o no f c o m p u t i n ga n dd e c i s i o ns c j e n c e s ”1 9 9 3 年第18 卷上。从此每年召丌一次以粗糙集理论为主题的国际研讨会。粗糙集理论 的几位主要倡导者，在1 9 9 5 年第1 1 期a c m 通讯上撰文，概括性地介绍了目前人 工智能应用新技术之一的裉糙集理论的基本概念以及其在知识挟取和机器学习、 决策分析、知识发现等领域的具体研究项目和进展。特别值得一提的是1 9 9 5 年召 开的第四届模糊理论与国际技术研讨会，在这次会议上，针对粗糙集与模糊集合 的基本观点与相互关系展开了激烈地讨论，较大地促进了粗糙集的研究。 中国学者也积极投身于粗糙集理论的研究，2 0 0 1 年5 月在重庆召开了“第l 届中国粗糙集与软计算学术研讨会” 8 】，邀请了粗糙集之父p a w l a k ，z 墩授做大会 报告；2 0 0 2 年1 0 月在苏州召开了“第2 届中国粗糙集与软计算学术研讨会”【9 】； 2 0 0 3 年5 月在重庆召开了“第3 届中国粗糙集与软计算学术研讨会”【1 0 】，并同时 召开了“第9 届粗糙集、模糊集、数据挖掘和粒度软计算学术研讨会” ，2 0 0 4 年9 月，在浙江舟山召开了“第4 届中国粗糙集与软计算学术研讨会” 12 1 。在国 内的计算机核心刊物上，也不时出现涉及粗糙集的论文。国内研究粗糙集理论的 立项研究的有中科院计算所、中科院自动化所、重庆邮电学院、西安交大、南昌 大学等，他们都得到了国家自然科学基金和9 7 3 计划等的资助，也涌现出了大 批像王国胤、史忠植、王珏、张文修、刘清、王驹、吴伟志等粗糙集理论的专家 学者。 8 硕士学位论文 1 5 本文研究的主要内容及框架 本文首先介绍了本课题研究的目的和意义，概述了国内外w 曲挖掘的研究现 状。接着介绍与w 曲日志挖掘相关的背景知识与相关理论，阐述了其理论基础的 概念和有关技术，并简单介绍了粗糙集理论中与本课题相关的理论。在此基础上 结合粗糙集理论提出了一种新的w e b 日志挖掘方法，首先了解了以往日志挖掘算 法实现前数据准备的特点，总结其方法的利弊发现对于用户访问数据的提取上主 要是针对比较有代表性的用户访问特征，本文综合了用户的访问特征提取出了三 种更有代表性的用户行为特征；然后建立了一种基于决策表的数据模型：最后在 新的w e b 日志挖掘规则获取算法上获取最终规则。同时还研究了w 曲l = = f 志规则获 取的实际特点，即由于同志数据存在奇异和不完整因而规则常常是缺省的。本文 在此基础上进行了缺省情况下的规则获取研究并进行了实例的验证。 本文的组织结构如下：第l 章绪论，对w e b 数据挖掘起源及发展作了较全面 的概述。从数据挖掘到w e b 挖掘的发展以及进一步到将要研究的同志挖掘做了介 绍，并目提到了国内外研究的技术现状及热点。然后对粗糙集方法作了初步的了 解；第2 章重点介绍了w e b 只志挖掘的整个实现过程。同志挖掘的4 个过程：数 据源的选择、数掘预处理、算法实现以及模式分析都一一介绍了。还有国内外学 者在日志挖掘方向的贡献和研究展望；第3 章介绍粗糙集，包括它的定义、知识 的约简、知识表达系统、决策表以及它们的最新研究进展；第4 章研究了羊日糙集 理论应j j j 于w e b 日志挖掘，结合w e b 日志的特点，用粗糙集的方法选取用户访特 特征属性，并建立基于二维决策表的数据模型，介绍了一种w 曲厂 志挖掘算法及 实现过程。最后是本文研究内容的进一步总结及工作的展望。 9 基于粗糙集的w e b 日志挖掘研究 2 1 概述 第2 章w e b 日志挖掘 随着w w w 网络的快速发展，w e b 平台已经成为网络信息的基础平台，它不但 存放了大量的企业、政府机关的数据，也成为了个人信息系统( p e r s o n a l i n f o r m a t i o n s v s t e m ) 的平台，巨大的信息量导致每天都有成千上万的用，o 在w e b 平台上浏览寻 找所需要的信息。正因为w e b 平台j e 在成为继广播、电视、报纸等传统媒体之后 又一个拥有巨大影响并且还在飞速发展的信息平台，所以怎样管理好w e b 站点使 之能够方便用户的浏览，吸引更多的用户成为许多因特网企业所关心的问题。 w e b 服务器的r 志文件( w e bl o g ) 记载了用户访问站点的数据，这些数据包括： 访问客户的i p 地址、访问时问、访问的页面、访问方式、贝面大小、浏览器类型、 响应状态等。每当站点被访问一次，w e bl o g 就在f 1 志数据库内追加相应的记录。 管理员丰要关心的是这些数据间的关系和数据的统计值，例如：访问次数和时间 的关系；访问用户所在的国家和地区分布：访问频率较高的页面；一段时间内被 访问的平均次数。这些都是简单的统计，但是随管w e b 站点的不断发展，站点的 规模与复杂程度与同俱增，w e b 站点的设计与维护变的越来越困难。利用普通的 概率论来统计分析、安排站点结构己经不能满足要求，而w e b 同志挖掘( 对w e b 服务器的日志文件进行挖掘的技术) 能够帮助w e b 站点的管理者更深入的了解站 点的使用信息。 利用w e b 几志挖掘技术，可以发现许多有价值的信息。如利用关联规则挖掘 可能发现用户所在地区与某被访问页面间的关系。而其他的数据挖掘技术，如时 间序列分析，多层关联规则挖掘和分类技术也可用于对w e bl o g 进行分析，帮助管 理员发现用户的访问规律。 2 2w e b 日志挖掘综述 2 2 1 基本概念 w 如日志挖掘的目的是在海量的w 曲日志数据中自动、快速地发现用户的访 问模式，如频繁访问路径、频繁访问页组、用户聚类等。w e br 志挖掘的相关术 语有： 服务器( s e r v e r ) ：是接受客户端请求，并对请求进行处理，提供各种服务的 终端。服务器按照功能有不同的名称，专门为多个用户提供代理服务的叫代理服 务器，提供互联网内容服务的叫w e b 服务器，这些内容通常是以w e b 页面的形式 1 0 硕士学位论文 表现的，专门为用户提供收发邮件服务的叫邮件服务器，有时候几个服务器会在 一台计算机上运行。本文提到最多的将是代理服务器和w e b 服务器。 用户( u s e r ) ：是通过浏览器从一个或多个w 曲服务器上访问文件的个人。在 实际使用中很难唯一的确定一个用户，因为一个用户可以从不同的机器上进行浏 览，也可以在同一台机器上用不同的代理服务器浏览。 页面视图( p a 2 e e w ) ：是一个用户请求的页面，页面中可能包括若干个框架、 图片和脚本。服务器记录的是到客户端的一个个文件流，而用户请求的不是这些 具体的文件，而是逻辑页面。因此，在确定提取浏览页面时要结合网站的拓扑结 构将图形文件过滤掉，从页面框架或者脚本运行情况中抽取浏览页面。 参引页面( r e f e r r a lp a g e ) ：如果通过a 页面上的链接可以请求b 页面，则称 a 是b 的参引页面。 点击流( c l i c ks t r e a m ) ：足访问页面视图的顺序序列。在服务器端可利用的数 据并不一定能够为一个站点重新构造完整的点击流提供足够的信息。任何通过客 户端缓存或代理服务器端缓存来访问的页面视图都会在服务器端不叮见。 用j ：t 会话( u s e rs e s s i o n ) ：是一个用户访问的所有页面视图的点击流。一般来 说，一个站点的用户会话数据只有一部分能够用来分析，大量w e b 服务器上的这 些存取信息并不完全公开。 2 2 2w e b 日志挖掘过程 w e b 的基本结构是：客户端一代理服务器一w e b 服务器。客户端记录的是单个用 户访问多个站点的信息。代理服务器日志记录的是多用户访问多站点的信息。w e b 服务器日志则记录多用户访问单站点的信息。因此，用户访问模式的挖掘有3 种 类型：客户端、代理服务器端和w e b 服务器端。根据挖掘目的和应用方向，挖掘 用户访问模式的侧重点也不尽相同。 客户端、代理服务器端的用户访问模式挖掘，涉及到整个w 曲并与半结构化 的w 曲数据模型直接相关。半结构化的w e b 数据模型是研究w 曲挖掘、信息检 索、智能搜索引擎及w