（计算机软件与理论专业论文）web使用挖掘中若干问题的研究.pdf

中山大学博士学位论文 论文题豳 专妲 撼士生 捅导教师 w 曲使用挖掘中若干问题的研究 计箨机软件与理论 陈健 姜云飞教授，印鉴教授 摘要 i n t e r n e t 的商速发展使之成为个分布广泛的全球性信息服务中心。随 整在线蹦户数鬣於迅速增长，、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 使用挖掘未来的研究方向。 目前关于w e b 使用模式的挖掘研究大都集中在发现事务内项目之间的关 联，也就是模式中的项目都是发生在同一事务内的。本文将w e b 使用模式的 范围由单一的事务内扩展到事务间。w e b 事务间的关联规则描述的是不同 的w e b 事务之间存在的相互关系。本文提出利用频繁项目集的闭合性质来解 决事务间关联规则的挖掘，给出必要的扩展定义以及设计和实现了一个高 效的算法c f c i m 。实验结果证明该算法的时问效率比基于投影的f i t i 算法要 高。 关联分类是通过挖掘训练集中数据属性和类别标号之间的关联来为新 数据预测类别的分类技术。这项技术可以运用在根据访问模式或使用记录 对w e b 用户进行分类中。近几年来的研究指出这种分类技术比传统的基于规 则的分类方法具有更高的准确性和更好的效率，因此得到了广泛的关注。然 而，以往的工作大多关注于如何在支持度一置信度的框架上实现这种分类技 术，因而存在支持度一置信度框架中闽值指定依赖经验、关联规则产生偏见等 问题。本文提出了一个基于相关性分析的关联分类算法a c b c a ，直接从训练 数据集中抽取女个最好的正相关和负相关规则用于分类，从而避免复杂的阂值 指定和偏见规则等问题。大量的实验证明，该算法比其它的基于规则的分类 算法( 如c 4 5 ) 或是基于支持度一置信度框架的关联分类算法( 女n c b a ) 具有 更高的准确性。 索引技术是组织和管理w e b 使用信息的有力手段。k 一最近邻及其检索算 法一直都是索引技术中的主要核心问题之一，尤其在多维数据库系统的检索 和查询方面起着相当重要的作用。近年来，一最近邻的逆问题逐渐得到人们 广泛的关注。所谓逆一最近邻居，就是在给定的数据集s 中将查询点q 视为 其一最近邻的所有点的集合。本文深入研究了逆一最近邻的理论基础，并吸 取了索引树对多维数据集整体特征良好的表达能力，提出了基于多维向量的 动态索引结构r k n n t r e e , 及其检索方式r k n n q u e r y 算法。实验结果表明，在多 维数据集中，该算法比朴素的r 查询算法效率有显著的提高。 目前的基于用户的协作过滤推荐算法由于使用了基于内存的最近邻查询 算法，因此体现山可扩展性差，缺乏稳定性的缺点。最近，针对可扩展性的 问题，研究人员提出了基于项目的协作过滤算法，但它仍然不能解决数据稀 疏带来的推荐质量下降的问题( 稳定性羞) 。从影响集的概念中得到启发， 本文提出一个新的基于项目的协作过滤推荐算法c f b i s ，利用当前对象的影 响集来提高该资源的评价密度。c f b i s 同时结合当前对象的个最近邻和7 个 逆最近邻来为当前对象产生推荐，并为这种新的推荐机制定义了计算预测值 的方法。实验结果证明，该算法在多个方面均优于现有的只基于最近邻产生 推荐的项目协作过滤算法，而且这种方法有效的缓解了数据集稀疏的问题。 关键词：w e b 使用挖掘；事务间关联规则；关联分类；影响集；推荐系统 i i t i t l e ：c o n t r i b u t i o n st os e v e r a li s s u e so fw e bu s a g em i n i n g m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ： c 珏e nj i a n s u p e r v i s o r ：p r o f j i a n gy u n f e i ，p r o f y i nj i a n a b s t r a c t t h er a p i dg r o w t ho fi n t e r n e th a sm a d ei tb e c o m ea ni m p o r t a n tm e d i u mf o rd i s s e m i n a t i n gi n f o r m a t i o na s w e l la sav a l u a b l er e s o u r c ef o rg a t h e r i n gi n f o r m a t i o n a s t h en u m b e ro fo n l i n eu s e r sg r o w s ，s od o e st h ev o l u m eo ft r a n s a c t i o nd a t ac o l l e c t e da t t h ew 曲s e r v e r s t os u p p o r tg o o dd e c i s i o n ，p e o p l eh o p ec a l ld i s c o v e rt h ev a l u a b l ei n f o r m a t i o nf r o mw e bu s a g ed a t ai no r d e rt og a i nab e t t e ru n d e r s t a n d i n go fu s e ra c c e s s b e h a v i o ro n ，e b 碡bu s a g em i n i n gi st h ep r o c e s so fa p p l y i n gd a t am i n i n gt e c h n i q u e s t ot h ed i s c o v e r yo fu s a g ep a t t e r n sf r o mw 曲d a t a b ya p p l y i n gw 曲u s a g em i n i n gt e c h - n i q u e s ，w ec a ua u t o m a t i c a l l yd i s c o v e ra n de x t r a c tu s e f u li n f o r m a t i o nf r o m k bs e r v e r l o g ，h i s t o r yo fb r o w s e ra n dp e r s o n a li n f o r m a t i o no f e bu s e r t oc a p t u r eb o t ht h ew e b a c c e s sp a t t e r n sa n dw 曲u s e rb e h a v i o r b a s e do nt h e s ev a l u a b l ei n f o r m a t i o ne x t r a c t e d 妒胁6u s a g em i n i n g ，n u m e r o u sa p p l i c a t i o n sc a nb ed e v e l o p e d ：i 昭6s e r v i c eq u a l i t y i m p r o v e m e n t s y s t e mp e r f o r m a n c eo p t i m i z a t i o n ，e t c w e bu s a g em i n i n gi sar a p i d l yg r o w i n gu r e aw h i c hi n t e g r a t e sm a n yo t h e rt e c h n o l o - g i e si nc o n l p u t e rs c i e n c eb u tt h e r eu r es t i l lv a r i o u sp r o b l e m sa n dr e l e v a n tt o p i c sc o m i n g f o r t h t h i sd i s s e r t a t i o nf o c u s e so i ls e v e r a lm a i ni s s u e so f w e bu s a g em i n i n g ，i n v e s t i g a t i n g t h e i rs o l u t i o n sb yc o m p l e t i n gt h er e l a t e dt h e o r i e sa n de x t e n s i v ee x p e r i m e n t s t h em a i n c o n t r i b u t i o n so ft h i sd i s s e r t a t i o na r es u m m a r i z e da sf o l l o w s ： f i r s t l y ，a sag o o db e g i n n i n ga n dan e c e s s a r yb a s eo fr e s e a r c h ，w eg i v eag e n e r a l f r a m e w o r ko fw 曲u s a g em i n i n gs y s t e m t h r e ep h a s e so f k bu s a g em i n i n ga r ea n a - l y z e da n dd i s c u s s e di nd e t a i l s ，s p e c i a l l yi n v e s t 培a t i n gt h ek e yt e c h n i q u e so fu s e rs e s s i o n a n dt r a n s a c t i o ni d e n t i f i c a t i o ni nd a t ap r e p a r a t i o n a n dt h e nw es u m m a r i z et h ek e y t e c h n i q u e su s e dt od i s c o v e r yt h ep a t t e r n sf r o mw e bu s a g ed a t a a sw e l l t h ep r i n c i p l e o fm a i na l g o r i t h m sa n da p p l i c a t i o na r e s e v e r a lr e a lw o r ka p p l i c a t i o n so fw e bu s a g e p a t t e r na r ei n t r o d u c e da l o n gw i t ht h em a i nd e v e l o p m e n tt r e n d sa n dt h ek e yt e c h n o l o g i e s i nt h e s ea p p l i c a t i o n s b a s e do nt h eo v e r v i e wo fw e bu s a g ep a t t e r n sm i n i n g ，w ef o u n dm o s to ft h ep r e v i - o n ss t u d i e so n k bu s a g ep a t t e r n sf o c u so nn f i n i n gi n t r a - t r a n s a c t i o na s s o c i a t i o n s i e t h ea s s o c i a t i o n sa m o n gi t e m sw i t h i n t h es a n l et r a n s a c t i o n t h ec o n c e p to f k bc r o s s - t r a n s a c t i o na s e o e i a t i o nr u l e sb r e a k st h eb a r r i e ra n de x t e n dt h es c o p eo fa s s o c i a t i o nr u l e s f r o mt r a d i t i o n a li n t r a - t r a n s a c t i o nt oc r o s s - t r a n s a c t i o naw e be r o s s - t r a n s a c t i o na s s o - c i a t i n nd e s c r i b e st h ea s s o c i a t i o nr e l a t i o n s h i p sa m o n gd i f i e r e n t k bt r a n s a c t i o n s t h e c l o s u r ep r o p e r t yo ff r e q u e n ti t e m s e t si su t i l i z e dt om i n i n gc r o s s 。t r a n s a c t i o na s s o c i a t i o n r u l ei nt h i sp a p e r t h en o t i o no fc r o s s - t r a n s a c t i o nf r e q u e n tc l o s e di t e m s e t si sd e f i n e d t h e r e l a t e dn e c e s s a r yt h e o r i e sa r ep r o v e da n da t1 a s ta ne t i l c i e n ta l g o r i t h m ，c f c i m ( c r o s s - t r a n s a c t i o nf r e q u e n tc l o s e di t e m s e tm i x f i n g ) i sd e s i g n e da n di m p l e m e n t e d t h ee x p e r i m e n t a lr e s u l t so v e rt w os y n t h e t i ct r a n s a c t i o n sd a t a b a s ed e m o n s t r a t et h a tt h i sm e t h o d i i i a b s t r a c t i sm o r et i m ee f f i c i e n tt h a nt h ep r o j e c t b a s e df i t ia l g o r i t h m s a s s o c i a t i v ec l a s s i f i c a t i o ni san o v e lc l a s s i f i c a t i o nt e c h n i q u ew h i c hu s e sa s s o c i a t i o n r u l e si nt r a i n i n gs e tt op r e d i c tt h ec l a s sl a b e lf o rn e wd a t ao b j e c t t h i st e c h n o l o g yc a n b eu s e di na r r a n g i n gw e bu s e r si n t oc a t e g o r i e sa c c o r d i n gt h e i rd i f f e r e n ta c c e s sp a t t e r n s o ru s a g eh i s t o r yt h i sm o d e lh a sb e e nr e c e n t l yr e p o r t e dt oa c h i e v eh i g h e ra c c u r a c yt h a n t r a d i t i o n a lr u l e - b a s e dc l a s s i f l c a t i o na p p r o a c h e st h ep r e v i o u sw o r k sf o c u so nh o w - t o i m p l e m e n tt h i sc l a s s i f i c a t i o nm o d e lo ns u p p o r t c o n f i d e n c ef r a m e w o r k w h i c hh a ss o m e p r o b l e m ss u c ha se x p e f i e n t i a lt h r e s h o l dv a l u ea p p o i n t m e n ta n db i a s e da s s o c i a t i o nr u l e g e n e r a t i o n i nt h i sp a p e r ，an o v e la s s o c i a t i v ec l a s s i f i c a t i o na 】g o r i t h m ，n a m e da c b c a ， b a s e do nc o r r e l a t i o na n a l y s i si sp r e s e n t e d ，a i m i n ga te x t r a c t i n gt h ek - b e s ts t r o n gc o r r e l a t e dp o s i t i v ea n dn e g a t i v ea s s o c i a t i o nr u l o sd i r e c t l yf r o l nt r a i n i n gs e t f o rc l a s s i f i c a t i o n ， a v o i d i n gt oa p p o i n tc o m p l e xs u p p o r ta n dc o n f i d e n c et h r e s h o l da n do v e r c o m et h eb i a si n r u l e sa ne x t e n s i v ep e r f o r m a n c es t u d yr e v e a l st h a tt h ei m p r o v e m e n to ft h i sa l g o r i t h m o u t p e r f o r mo t h e rr u l e - b a s e ds n c ha sc 45o rs u p p o r t c o n f i d e n c e - b a s e dc l a s s i f i c a t i o na d p r o a c h e ss u c ha sc b ao na c c u r a c y i n d e x i n gt e c h n o l o g yi sap o w e r f u lm e t h o df o rw 曲i n f o r m a t i o n 。r g a z i i z a t i o na n d m a n a g e m e n t ，kn e a r e s tn e i g h b o rp r o b l e mi sa l w a y so n eo fi m p o r t a n tt o p i c si ni n d e x i n g t e c h n o l o g y , e s p e c i a l l yi np o i n t sq u e r ya n ds e a r c hi nm u l t i d i m e n s i o n a ld a t a b a s es y s t e m r e c e n t l y , m o r ea n dm o r ea t t e n t i o n sh a v e b e e np a i do ni t sr e v e r s ev e r s i o n 。w h i c hi sk n o w n a s “i n f l u e n c es e t s ”p r o b l e m 。秘l er e v e r s ekn e a r e s tn e i g h b o rp r o b l e mi st of i n da l lp o i n t i nad a t as e tt h a tt a k ea g i v e nq u e r yp o i n ta st h e i r n e a r e s tn e i g h b o rt h er e l a t e db a s i c d e f i n i t i o n sa n dt h e o r i e sm g i v e ni nt h i sp a p e r b a s e do nt h eg o o dc a p a b i l i t yt or e p r e s e n t f e a t u r eo ft h ew h o l ed a t as e to fi n d e x i n gs t r u c t u r e ，an e wh e u r i s t i cd y n a m i ci n d e x i n g t r e es t r u c t u r er k n n t r e ea n di t sr e l a t e dp o i n t sq u e r ya l g o r i t h mr k n n q u e r ya r ep r e s e n t t h ee x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h a tt h i sa l g o r i t h mc 8 nb r e a kt h el i m i t a t i o n so f t h ep a s ta l g o r i t h m sa n de n h a n c et h ep e r f o r m a n c ee f f i c i e n t l y t h et r a d i t i o h a lu s e r - b a s e dc o l l a b o r a t i v ef i l t e r i n gf c f ) a j g o r i t h m so f t e ns n f i e ff r o m t w oi m p o r t a n tp r o b l e m s ：s c a l a b i l i t ya n ds p a r s i t yb e c a u s eo fi t sm e n l o r y - b a s e dkn e a r e s t n e i g h b o rq u e r ya l g o r i t h m r e c e n t l y i 招m - b a s e dc fa l g o r i t h m sh a v eb e e nd e s i g n e dt o d e a lw i t ht h es c a l a b i l i t yp r o b l e m sa s s o c i a t e dw i t hu s e r - b a s e dc fa p p r o a c h e sw i t h o u t s a c r i f i c i n gr e c o m m e n d a t i o no rp r e d i c t i o na c c u r a c y , h o w e v e r ，i t e m - b a s e dc fa l g o r i t h m s s t i l ls u f f e r 爵。mt h ed a t as p a r s i t yp r o b l e m s i nt h i sp a p e r w ep r e s e n tac fr e c o m m e n - d a t i o na j g o r i t h m ，n a m e dc f b i s w h i c hi sb a s e do nt h ec o n c e p to fi n f l u e n c es e tw h i c hi s 8h o tt o p i ci ni n f o r m a t i o nr e t r i e v a ls y s t e m w ec o m b i n et h ee f f e c to fkn e a r e s tn e i g h b o r a n dr e v e r s e 惫n e a r e s tn e i g h b o rf o rat a r g e ti t e m u s i n gt h ei t o ms e tw h i c ht a k et h et a r - g e ti t e ma st h e i ra 7n e a r e s tn e i g h b o rt oe n h a n c et h ed e n s i t yo fi n f o r m a t i o nm o r e o v e r 、 w ed e 蠡n ean e wp r e d i c t i o nc o m p u t a t i o nm e t h o df o rt h i sn e wr e c o m m e n d a t i o nm e c h a - n i s m o n re x p e r i m e n t ss h o wt h a to u ra l g o r i t h m sc a l la c h i e v eb e t t e rp r e d i c t i o na c c u r a c y t h a nt r a d i t i o n a li t e m b a s e dc fa l g o r i t h m s 。f u r t h e r m o r e 、o u ra l g o r i t h mc a na | l e v i 8 t e t h ed a t a s e ts p a r s i t yp r o b l e m k e y w o r d s ：w i bu s a g em i n i n g ；c r o s s - t r a n s a c t i o na s s o c i a t i o nr u l e s ；a s s o c i a t i v ec l a s s i f i e a t i o n ；i n f l u e n c es e t ；r e c o m m e n d a t i o ns y s t e m 中山大学博士学位论文 第一章引言 1 1w 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 曲内容挖掘、w e b 结构挖掘 和w e b 使用挖掘。 w e b 内褰挖掘( w e bc o n t e n tm i n i n g ) 是据从w e b 文档内容绒接述中抽 取翔 凳豹l 建程。与w e b 结聿奄挖掘和w e b 使臻挖掘不嗣懿是，w e b 内容挖援 更注重w e b 页面中内容的意义( 而不是链接或使用信息) 。在w e b 挖掘的 范畴内，w e b 内容挖掘本质上是在w e b 关系数据库中运用数据挖掘技术， j w e b 文梢中发现知识的过程。w e b 内容挖掘的对蘩包括w e b 上的文本、图 象、啻颖、撬频、多髹体疆及萁 氇冬季挚类鳘豹数摇。 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 空间中，商用的知识不仅包含在页面的内容里， 而且也包含在页面的缕构中。超链接信息包含了人类潜在的注释，大量 茨w e b 超镳接提燕了关予w e b 夏瑟蠹攀豹稳关蠖、袋鐾窝缝稳方瓣戆莛惠， 它有助予离动推断出页磷的权威性( a u t h o r i t y ) 。w e b 结构挖掘主要就是通 过对w e b 站点的超链撩结构进行分析、变形和归纳，通过揭示擞面之间相 互链接的必系来分析w e b 自身的链接跆构的模式。这种模式可以用于页面归 类，壶北获褥毒关不同茭露闻握叛发放关联度的傣患。该类挖掇不仅能鸯助 于用户抉滚找到辐荧主麓的权威菇点，两盈对予w e b 筵点架稳重缀、优纯服 务器的性能和提高w e b 的服务质量都越到一定的积檄作用。 w 曲内容挖掘和w e b 结构挖掘的挖掘对象是w e b 上的原始数据， 蔼w e b 使爝挖掘面对的则是用户在鞠、托b 交互的萎；程中撼取出来的、加工 重量塞l ! 童 嚣静数据，包括w 秘激务器谤蠲记渌、代理骧务器强志记录、澍笕器磊志记 录、用户简介、注册信息、用户对话或交易信息、用户提问方式等。w e b 使 用挖掘( w e bu s a g em i n i n g ) 就是指利用数据挖掘技术从w e b 数据中发现 用户使用模式的过程睇3 l 。w e b 使用挖掘一般分为i 个步骤：数据预处理、 模式挖攘窝模式分搽与蓬矮。w e b 便露箍撼最终瀚嚣静是了解翔户在w e b 主 行为及其所具有的意义。运用w e b 使用挖掘技术黻够从服务器、浏览器端的 日志记录和用户的个人信息中自幼发现隐藏在数据中的模式信息，了解系 统的访问模式以及用户的行为模式，从瓶作出预测性分析。魏立在这些模 式上麴系统麓为不阖熬瘸户挺揆不蕊戆鞭务，漠是震产鳇不阗粒震求霹， 困此能充分提高站点的服务质量和访闯效率，嗷弓| 更多的访阏者。例如， 通过统计用户在某一信息页面所停留的时间，可以判断出用户对该资源 兴趣高低：或是对豳志文件所收集到的域名数据，根据国镦地域或类型 ( c o i l l ，e d u 、g o v ) 透符分类预测分耩：又或老遗避应眉蒙类分褥来识别用户 的访阕渤视和访阔趋势等。w e b 使掰挖掘还可良擒示w e b 页西中隐含静关联 关系【6 、客户类属关系【7 】和频繁访问路径1 8 】8 、频繁访问页面【9 】簿大量有用信 息，对于用户的个性化定制【1 0 】、w e b 导航 1 1 】、提高w e b 服务器系统的性能和 结构、网络安全的捡测、开疑有针对的电子商务活动f 1 3 1 等都怒到决策性作 嗣。 1 2 w e b 使用挖掘的重要性 这几年来，随着信息处理、数据挖掘和计算机硬件等各方面技术的发 展，w e b 使用挖掘逐渐得到人们的关注。1 9 9 6 年起w e b 挖掘开始以探讨性报 告的形式在一些大学和研究机构中m 现。之后有关w e b 使用挖掘的文章就 在各权威国际会议女f l l e e ei n t e r n a t i o n a lc o n f e r e n c eo nt o o l sw i t ha r t i f i c i “ i n t e l l i g e n c e ，a c mw o r k s h o po nw e bi n f o r m a t i o na n dd a t am a n a g e m e n t 等 与数据挖掘, j = 1 3 w e b 应用相关的会议上发表。国际权威刊物血n c o m m u n i c a t i o n o fa c m ，j o u r n a lo fk n o w l e d g ea n di n f o r m a t i o ns y s t e m s ，d a t am i n i n ga n d k n o w l e d g ed i s c o v e r y 也增加了这方面内容。可以预料，国际上对w e b 使用挖 掘的研究成果将越来越重视。 对w e b 使用挖掘率先进行研究的是欧美一些著名大学中信息处理 领域的一些知名学者和i n t e r n e t 服务提供商。由于该研究方向重要的学 术价值和广阔的应用前景，引起了越来越多有关领域学者的注意和参 与。目前在该领域里比较活跃的著名大学和研究机构有d e p a u lu n i v e r s i t y 、t h eu n i v e r s i t yo fm i c h i g a n 、u n i v e r s i t yo fm i n n e s o t a 、u n i v e r s i t yc o l - l e g ed u b l i n 、i b m 、a m a z o n 、g o o g l e 等。这些机构和个人在w e b 使用挖掘 的理论基础和应用发展方面都做出了杰出的贡献。美国u n i v e r s i t yo fm i n - n e s o t a 的r c o o l e y 等人对w e b 使用挖掘在商业智能中的应用做了深入的研 究【1 4 】，并提出一些极具实用价值的原型系统【1 5 】。加拿大的s i m o nf r a s e ru n i 一 2 中山大学博士学位论文 v e r s i t y 的j i a w e ih a n 和0 z a i a n e 提出了如何在w e b 挖掘上使用o l a p 技术的 方法，他们的研究工作在多媒体数据上展开【1 7 】，亦为w e b 内容挖掘提 供了宝贵的解决方法。德国柏林h u m b o l d tu n i v e r s i t y 信息系统研究所的m s p f l i o p o u l o u 等人关注w e b 使用模式的发展和变化的应用【1 8 ，他们的工作为电 子商务$ f l w e b 商场提供导航系统和个性化定制【1 q ，无论对用户还是网站都极 具意义。美国d e p a u l 大学通信和信息系统实验室的b a m s h a dm o b a s h e r 等人的 研究方向包括推荐系统自动化，电子商务中的智能代理和语义网络挖掘【2 0 】等 等。在我国，近年来w e b 使用挖掘开始逐渐受到重视，国家自然科学基金委 员会以及各审视省市的科研基金部门都对与w e b 使用挖掘的相关方面的研究 给予了必要的资助。国内研究机构和高校对w e b 使用挖掘的研究也取得了不 少成果【2 1 2 3 】。 1 3w e b 使用挖掘研究中存在的一些问题 随着薪技术盼不断涌现，人们对获敬的信怠震豢耍求也越来越商。在 新的环境中，w e b 使用挖掘中还存在着许多新的问题儒要进一步的考虑和研 究。目前，猩w e b 使用挖掘领域所存在的些问题有： 1 耘鏊魏谈豹嚣要。蕤簿入弱接翅w e b 瓣方式不鞭嶷位襄曼囊，入髓期望 扶不同的角度，更多的方面对w e b 用户的使用模式做出全面丽猴确的分 析。作为数据挖掘领域中非常重要和活跃的研究方向之一，关联规则的 挖掘研究得到了人们广泛的关注。但是传统的关联规则挖掘算法和技术 疆发理豹模式，数枣务走静顼基关系巍挖撼对象，趋向萃化窝匿定 化。陡饕信息复杂庹的增加，这耱簿隼的事务蠹麓粼已经不是以搐述现 实的w e b 事务之间的簸杂关系。 2 分类在w e b 使用挖掘中有着广泛的成用，例如根据访问模式对w e b 用户 避嚣分炎，翔续套类瑙户戆镬用摸武将蠢，那么在攘荐系绞中不坟可鞋 给出以锰用户经常潮览的楣关页磷，还可以狠攒内容裙关性做出一些 预测性分析，从而为用户提供更好的服务。传统的例如决策树算法、 基于统计骧理的b a y e s 算法、神经网络算法等分炎算法应用在大量复杂 鳆v v e b 馕用数摆土聪，体现出分类速度授、规则形式不易理勰、不能有 效进行的存德和使用戴瑚等弊病， 3 为用户提供一个快滤、准确、全面的站内信息检索服务对网站提升用户 体验，吸引用户来说是至荚重要的。索引是组织和管理w e b 使用信息的 有力手段。基最近邻及其捡索算法妻都是索g | 技术中瓣主要棱心闫题 之一尤其在多维数据库系统的检索和查诲方西超着相当重簧的作用。 近年来，女最近邻的：i 照问题逐渐得到人们广泛的关注。逆肛最近邻能解 决w e b 使用挖掘中为新资源寻找潜在用户的问题。但目前还没商这方面 的应臻辑究。 3 4 w e b 面对的是一个广泛的、形形色色的用户群体。各个用户具有不同的 背爨、兴趣蠢搜臻w e b 簿基簿。w e b 上豹箍惑对蠲户两畜，只有穰小懿 一部分是相关的或有用的。推荐系统为此而产生。但目前的基于用户的 协圣謇过滤雄莓算法虫子使用了蒸予盎存的最远邻黉诲算法，因戴传褒爨 可扩展性差，缺乏稳定性的缺点。而且当系统资源未获足够评价时，系 统灌阻为鼹户产生准确靼有效的提豢，也不残为款出现的资源找到港在 的用户群。 1 4 本文的工作 本文的目标就是在数据挖掘的大背景之下，从理论、算法和应用三个层 次来讨论w e b 使用挖掘技术。针对上一节提出的几个问题，本文主要做了以 下儿个方面的工作。如图( 1 1 ) 所示。 w e b 他吲手窀搦陷避拶本文工悸 图1 1 ：w e b 使用挖掘的框架模型 在第二章，作为对w e b 使用挖掘进行研究的开始和基础，本文首先 对w e b 使用挖掘中各个阶段进行了全面的分析，尤其对数据预处理中用户会 话和事务识别技术进行了深入的探讨和分析；详细研究了w 曲使用挖掘中常 用的模式发现技术以及应用空间等：展望了w 曲使用挖掘的发展方向和在具 体应用中所要解决的关键问题。 在第三章，针对原有的关联规则形式单一化的问题，本文将w e b 使用模 式的挖掘范围由单一的事务内扩展到事务问，提出用事务间关联规则来描 4 圭些奎耋堡主兰堡堕塞 述w 曲使用数据中的模式。利用频繁项目集的闭合形式来快速解决事务间 关联规则的挖掘。完善了相关的理论基础。并设计和实现了一个高效的算 法c f c i m 。实验结果证明该算法的时间效率比基于投影i 拘f i t i 算法要高。 在第四章，针对传统的分类算法在大量复杂的w e b 使用数据上体现出的 不足，本文提出了一个基于相关性分析的关联分类算法a c b c a ，直接从训练 数据集中抽取七个最好的正相关和负相关规则用于分类，从而避免复杂的阈值 指定和偏见规则等问题。大量的实验证明，该算法比其它的基于规则的分类 算法( 如c 4 5 ) 或是基于支持度一置信度框架的关联分类算法( 女i i c b a ) 具有 更高的准确性。 在第五章，本文对检索技术中的影响集问题进行了深入研究。尤其 关注逆一最近邻的查询算法，吸取了索引树对多维数据集整体特征良好 的表达能力，提出了基于多维向量的动态索引结构r k n n t r e e 及其检索 方式r k n n q u e r y 算法。实验结果表明，在多维数据集中，该算法比朴素 的r k n n 查询算法效率有显著的提高。 在第六章，在w e b 使用模式的其体应用方面，本文主要关注如何提高推 荐系统的推荐质量问题。从影响集的概念中得到启发，本文提出一个新的基 于项目的协作过滤推荐算法c f b i s ，利用当前对象的影响集来提高该资源的 评价密度，在数据集稀疏的情况