（通信与信息系统专业论文）基于模糊聚类的web日志挖掘研究.pdf

基于模糊聚娄的w e b 日志挖掘研究复旦大学硕士学位论文 图表目录 图1 - 1w e b 用户访问模式挖掘系统的分类 1 1 图2 - 2w e b 日志挖掘的过程错误! 未定义书签。 图2 - 3w e b 日志挖掘中的数据预处理过程2 l 表4 - 1w e b 服务器访问日志举例3 0 表4 2l o gt a b l e 结构3 l 图4 - 2 会话识别算法描述3 3 表4 - 3 网站层次结构对会话相似度的影响举例3 4 表4 3 用户浏览网页的时间对会话相似度的影响举例3 5 表5 - 4 聚类结果总结5 l 表5 - 5 聚类结果的表示5 1 表5 5 各聚类的类内距离和类间距离5 2 图5 - 5 部分聚类结果5 3 图5 _ 6 各聚类中心的类间距离( r f c m d d ) 5 4 图5 7 各聚类中心的类间距离( d h r f c m d d ) 5 5 图6 - 1 系统的体系结构5 8 表6 - 1 日志记录和数据预处理功能表结构5 9 表6 - 2 用户聚类模式库表结构6 1 图6 - 2 根据用户聚类模式库生成推荐集合的算法6 l 图6 - 3 部署在a p a c h e 服务器上的网站首页6 2 图6 - 4 当用户会话长度没有达到临界长度时的页面显示6 3 图6 5 当前用户访f 司m a c h i n e s m a n u f a c t u r e r s d e f a u l t h t m 时页面的显示。6 4 图6 - 6 当前用户访t 习l m a c h i n c s l c a t e g o r i e s d e f a u l t h t m 时页面的显示。6 5 7 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明 并表示了谢意。 作者签名：未! 拯日期：卫：zi ：2 论文使用授权声明 本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 规定。 作者签名：趣坚导师签名丝l 瞩望：丛z 基于模糊聚类的w e b 日志挖掘研究复且大学硬士学位论文 基于模糊聚类的w e b 日志挖掘研究 摘要 随着i n t e r n e t 的迅速发展，“信息迷航”和“信息过载”的问题日益制约人们高 效地使用i n t e r n e 信息。为了解决这一严峻的问题，很多研究者提出了个性化推荐系 统的概念，即根据用户的兴趣和特点推荐用户感兴趣的信息。而目前应用最广泛 的个性化推荐系统应当属个性化推荐网站了。具体的说就是当用户在访问个性化 网站的时候，总有一种感觉，好像整个网站都是为他设计的，特别友好，一切都 是那么有用，都是自己当前很感兴趣的东西。因此，使用数据挖掘和人工智能等 相关技术对用户的浏览行为进行分析，即对w e b 日志进行挖掘已经成为提供个性 化服务的一个重要方法。 目前，国内外对w e b 日志挖掘的研究主要集中在对用户会话的研究上，包括 关联规则、协同过滤、聚类和分类等，其中。聚类技术常被用来分析网站用户对 网页的兴趣爱好。但是，传统硬性的聚类只能将用户会话类归于单一聚类中，即 事先假设每一个会话只包含单一的兴趣爱好，却忽略该会话可能包含多个兴趣爱 好。因此，有学者将模糊聚类应用其中。模糊聚类算法按照数据对象的不同，可 以分为特征向量聚类算法和关系数据聚类算法。对于关系数据聚类算法，国内目 前使用较多是基于模糊等价关系矩阵的聚类算法，而对于基于目标函数的关系聚 类算法研究并不多。同时，在分析用户会话相似度时，往往是根据会话之间相同 网页的数量或者网站的层次结构来定义会话相似度，而忽略了用户在会话中对各 个网页的访问时间，所以容易产生错误的分析结果。 本文正是在这一背景下，以w e b n 务器日志为研究对象，研究了w e b 日志挖掘 领域相关的技术，对其中w e b 日志预处理、模糊聚类算法以及个性化网站的体系 结构等进行了研究和改进，并部分实现了一个具备推荐功能的个性化网站的系统 原型。 本文的主要工作如下： 1 提出了一个改进的用户会话相似度的计算方法。该方法既考虑了用户会话 之间相同网页的数量对会话相似度的影响，同时又考虑了网站的层次结构和用户 在网页上的停留时间对会话相似度的影响，这样可以更加准确的反映用户会话之 间的相似度。 2 提出了一个改进的w e b 日志数据聚类算法一基于分裂层次的 r f c m d d ( r o b u s tf u z z ycm e d o i d s ) 。r f c m d d 算法是一种健壮的，运行速度快， 并适合于大数据量数据的模糊分割聚类算法。不过r f c m d d 也有传统分割聚类 算法的缺点：对初始聚类中心敏感和聚类的个数必须事先给出。这容易导致聚类 的主观性和随意性，会影响到正确的聚类结果。而分裂层次算法的优点就在于通 过分裂的方法来决定最终聚类的个数。因此，把r f c m d d 算法和分裂层次算法 结合起来，可以有效的克服上述缺点。 3 提出了一个个性化在线推荐系统原型。该系统分为离线挖掘和在线推荐两 个部分，提供的个性化推荐服务可以直接面向匿名用户。离线挖掘部分主要是利 用基于分裂层次的r f c m d d 算法对用户会话进行聚类，得到用户会话聚类集并生 成推荐模式库。在线推荐部分主要是获取当前用户会话，然后和推荐模式库中的 模式进行匹配，自动产生推荐页面集，提供给用户，从而达到个性化推荐的目的。 关键词：w e b 日志挖掘，模糊聚类，用户会话，个性化推荐系统 2 基于模糊聚类的w c b 日志挖掘研究复旦大学硕士学位论文 r e s e a r c ho fw e bl o gm i n i n gb a s e do nf u z z yc l u s t e r i n g a b s t r a c t w i t ht h ef a s td e v e l o p m e n to fi n t e r n e t ，i n f o r m a t i o nd i s o r i e n t a t i o na n di n f o r m a t i o n o v e r l o a d i n gh a v eb e c o m eo b s t r u c t i o n sw h i c he o n s t r a i n t t h ee f n t i e n tu s eo fi n t e r u e t i i l f o r m a t i o n i n0 r d e rt or e s o l v et h es e v e r ep r o b l e m , m a n yr e s e a r c h e r sa d v a n c e dt h e c o n c e p to fp e r s o n a l i z a t i o nr e c o m m e n d e rs y s t e m w h i c hr e c o m m e n d st h ei n f o r m a l 【i o n w h i c hu s e ri si n t e r e s t e da c c o r d i n gt oh i si n t e r e s t sa n dc h a r a c t e r s a m o n ga l lt h e r e c o m m e n d e rs y s t e m s ，t h ep e r s o n a l i z e dw e b s i t e sw i t hr e c o m m e n d e ra r et h em o s t p o p u l a r i nm o r ed e t a i l w h e nau s e rv i s i t st h ep e r s o n a l i z e dw e b s i t e ，h ew i l 】h a v es u c h af e c l i n gt h a ti ts e e m st h ew h o l ew e b s i t ei sd e s i g n e df o rh i ma n di sv e r yf r i e n d l y e v e r y t h i n gi nt h i sw e b s i t ei sv e r yu s e f u lf o rh i m s o ，a n a l y z et h eu s e rb r o w s i n g b e h a v i o ru s i n gt e c h n i q u e so fw e bm i n i n ga n da r t i f i c i a li n t e l l i g e n c eh a sb e c o m eav e r y i m p o r t a n tm e t h o dt op r o v i d ep e r s o n a l i z e ds e r v i c ef o ru s e r s a tp r e s e n t ，r e s e a r c ho nw e bu s a g em i l l i n gm o s t l yc o n c e n t r a t e do nt h eu s e r a c c e s sp a r e m ，i n c l u d i n ga s s o c i a t i o nr u l e s 、c o l l a b o r a t i v ef i l t e r i n g 、c l u s t e r i n ga n d c l a s s i l y i n g c l u s t e r i n gt e c h n i q u e sa r eo f t e nu s e dt oa n a l y z eu s e r si n t e r e s to nt h ew e b p a g e s h o w e v e r , t r a d i t i o n a lc l u s t e r i n gc a no n l ys o r te a c hu s e rs e s s i o ni n t oas i n g l e c l u s t e r t h a ti s i ti g n o r e sau s e rs e s s i o nm a yc o n t a i ns e v e r a lb r o w s i n gp r e f e r e n c eb y a s s u m i n gau s e rs e s s i o ni n c l u d e so n l yas i n g l ep r e f e r e n c e t h u ss o m er e s e a r c h e r s p r o p o s ef u z z yc l u s t e r i n gm e t h o d st oc l u s t e ru s e rs e s s i o n s a c c o r d i n gt ot h ed i f f e r e n c e o fd a t ao b j e c t s ，t h e r ea r et w of u z z yc l u s t e r i n ga l g o r i t h m s o n ei sb a s e do nf e a t u r e v e c t o ra n dt h eo t h e ri sb a s e do nr e l a t i o n a ld a t a a st or e l a t i o n a ld a t af u z z yc l u s t e r i n g a l g o r i t h m s ，m o s to f r e s e a r c h e r si nd o m e s t i cu s ef u z z ye q u i v a l e n c er e l a t i o n a lm a t r i x a n dd ol i t t l er e s e a r c ho nr e l a t i o n a lc l u s t e r i n ga l g o r i t h m sb a s e do no b j e e t i v ef u n c t i o n m e a n w h i l e t h o s em e t h o d sa r eo n l yb a s e do nt h en u m b e ro fc o r n r e _ o np a g e sa c c e s s e d b yt w os e s s i o n so rt h eh i e r a r c h i c a lo r g a n i z a t i o no fw e b s i t et oc a l c u l a t es e s s i o n s i m i l a r i t y , b u td o n tt a k et h ea c t u a lt i m et h en s e r ss p e n to nv i e w i n ge a c hp a g ei n t o a c c o u n t s oi tw i l lc a u s ew r o n gr e s u l t s o nt h i sb a c k g r o u n d ，t h i sp a p e rf o c u s e so nw e bs e r v e rl o gm i n i n g ，r e s e a r c h i n g a n di m p r o v i n gr e l a t e dt e c h n i q u e so fw b bu s a g em i n i n g ，i n c l u d i n gd a t ap r e p r o c e s s i n g o fw e bl o g 、f u z z yc l u s t e r i n ga l g o r i t h ma n dt h ea r c h i t e c t u r eo fp e r s o n a l i z e dw e b s i t e ， a n d i m p l e m e n t i n g a p r o t o t y p i c a lp e r s o n a l i z e d w e b s i t ew i t hf u n c t i o no f r e c o m m e n d a t i o n t h em a i nc o n t r i b u t i o n so f t h ep a p e ra r es u m m a r i z e db e l o w 基于模糊聚类的w e b 日志挖掘研究复旦大学硕士学位论文 i t h ep r o p o s i t i o no fa l li m p r o v e dm e t h o dt oc a l c u l a t es e s s i o ns i m i l a r i t y t h e m e t h o dn o to n l yt a k e st h en u m b e ro fc o m m o np a g e sb e t w e e ns e s s i o n s ，b u ta l s ot a k e s i n t oa c c o u n tt h ev i e w i n gt i m eu s e r ss p e n to ne a c hp a g e i tw i l lr e f l e c ts i m i l a r i t y b e t w e e ns e s s i o n sm o r ea c c u r a t e l y 2 t h ep r o p o s i t i o no fa ni m p r o v e dw e bl o gc l u s t e r i n ga l g o r i t h m - - r o b u s tf u z z yc m e d o i d sb a s e do nd i v i s i v eh i e r a r c h y r f c m d di sar o b u s tc l u s t e r i n ga l g o r i t h mw i t h i o wc o m p l e x i t v s oi t sa l w a y su s e dt oc l u s t e rl a r g ea m o u n to fd a t a b u ti t sd e m e r i t s a r et h a ts e n s i t i v i t yt ot h ei n i t i a lc l u s t e r i n gc e n t e ra n dt h en u m b e ro fc l u s t e r sm u s tb e g i v e na p r i o r i ，t h u sm a yc a u s ew r o n gc l u s t e r i n gr e s u l t h o w e v e lt h em e r i to fd i v i s i v e h i e r a r c h ya l o g o r i t h mi st h a ti tc a nd e c i d et h en u m b e ro fc l u s t e r sb yd i v i s i o n s o c o m b i n i n gr f c m d da l g o r i t h mw i t hd i v i s i v eh i e r a r c h yc a l ls o l v et h ep r o b l e m sa b o v e e f f e c t i v e l y 3 t h ep r o p o s i t i o no fap r o t o t y p i e a lp e r s o n a l i z e do n l i n er e c o m m e n d e rs y s t e m t h es y s t e mi n c l u d e st w om a i np a r t s o f f - l i n em i n i n gp a r ta n do n - l i n er e c o m m e n d a t i o n p a r ta n dc a ns e r v ea n o n y m o u su s e r sd i r e c t l y t h eo f f - l i n ep a r ti sr e s p o n s i b l ef o r c l u s t e r i n gu s e rs e s s i o n sw i t hd h - r f c m d d t h e ng e t t i n g t h ec l u s t e r i n gs e to fu s e r s e s s i o n sa n dc r e a t i n gt h er e c o m m e n d a t i o np a t t e r nd a t a b a s e t h eo n - l i n ep a r ti s r e s p o n s i b l e f o r g e t t i n g c u r r e n tu s e rs e s s i o n s ，m a t c h i n g i t w i t h p a t t e m s i n r e c o m m e n d a t i o nd a t a b a s e ，c r e a t i n gt h es e to f r e c o m m e n d a t i o np a g e sa n dp r o v i d i n gt h e s e tt ou s e r sf o rp e r s o n a l i z a t i o n k e y w o r d s ：w r e bu s a g em i n i n g ，f u z z yc l u s t e r i n g ，u s e rs e s s i o n ，p e r s o n a l i z e ds y s t e m 4 第1 章绪论 1 1 论文研究背景和选题意义 1 1 1w e b 日志挖掘的提出和研究意义 随着i n t e m e t 在信息共享、电子商务和提供在线服务方面的广泛应用，许多 企业投入大量资金建立自己的网站用于发布信息，或在别人的网站上为自己的产 品和服务作广告，或在网上开展电子商务活动，它们迫切需要了解这些投资产生 的效益和作用，以便改进企业的策略，获取更多的商业机会，为用户提供更优质 的服务。因此，理解用户的行为对这些企业来说至关重要。 用户在网站上的活动隐含了他们的需求和兴趣，如果对用户的行为加以分 析，就有可能发现些潜在的规律。了解用户在网站上的访问模式( a c c e s sp a t t e r n ) 和兴趣爱好，有助于优化网站的组织结构和空间设计，例如：在高度相关的页面 或站点之间提供快速有效的访问途径1 1 1 ，设计外观和布局更加友好的页面，以方 便用户获取信息和服务；改善企业的市场营销策略，例如：对用户进行更为准确的 分类，推荐其可能感兴趣的信息和服务，识别潜在的电子商务客户，在关心企业 产品和服务的用户经常访问的页面或站点放置广告；分析和提高w e b 服务器的性 能和信息服务质量，例如：提供w 曲页面缓冲、页面预取和页面推荐，改善服务 响应时间；为用户提供个性化的服务，例如：为用户动态调整网站结构、页面内容 和外观，使其更加符合用户的偏好和信息需求，减轻用户搜索和过滤海量信息的 负担。 w e b 服务器日志记录了用户与服务器的交互信息，对于掌握w e b 服务器的 运行情况、分析用户需求、维护系统安全、辅助站点维护人员优化站点具有重要 作用1 2 1 。对日志采用统计分析和联机分析处理( o l a p ) 的方法，可以对常用数据 进行汇总，提供关于用户行为的统计报告。但为了在更深的层次上理解用户的行 为和w e b 站点的结构，得到诸如用户的访问模式和兴趣爱好等有用信息，就要 用到数据挖掘的方法，于是产生了w e b 日志挖掘。 同传统的数据挖掘一样，w e b 日志挖掘主要包括聚类、分类、关联规则和序 列分析。w e b 日志挖掘的研究成果主要应用在以下几个方面： ( 1 ) 调整网站信息的组织和显示，优化服务性能。应用w e b 目志挖掘学习群 体用户的访问模式，并据此做出调整，使网站对于大多数用户来说更易于访问。 这些调整可以是： 1 ) 根据发现的频繁遍历路径调整网站的超链接结构。 2 ) 根据发现的频繁访问页面组，在这些逻辑上相关联( 针对同一主题，或者 面向同一类用户) 但不在同一条遍历路径的页面之间增加超链接，或把这些页面 聚集成类，并创建索引页面。 3 ) 合理设置广告页面。 ( 2 ) 响应每一个用户的特定需求，为其提供个性化服务。互联网海量信息与 用户狭窄专一需求产生矛盾，方面造成信息资源的巨大浪费，另一方面，为用 户寻找所需要的信息造成巨大的困难，因而需要提供个性化的数字服务f 舢。应用 w e b 日志挖掘通过对用户访问历史的分析，发现个体用户的访问模式，从该模式 中学习、记忆用户的兴趣、爱好、习惯和需求，建立个性化用户模型。把从w 曲 上获取的资源与个性化模型所描述的信息相比较，可以主动地有选择性地向用户 推荐符合其兴趣的个性化信息( 如页面、链接、广告、经过裁剪的文本和图片等) 。 由于滤除了与用户需求无关的信息，因而大大提高了用户获取有用信息的效率。 应用w e b 日志挖掘建立个性化用户模型的优点在于： 1 1 基于个性化用户模型把具有相似兴趣的用户加以聚类，还可以根据同一 聚类用户的兴趣和爱好向个体用户推荐其最有可能需要的信息。 2 ) 个性化用户模型是从用户的访问模式中动态提取的，能够随着用户需求 的改变而不断调整，因而总是反映用户当前最新的兴趣和需求。 3 ) 模型具有一般性的特点，适用于所有的w e b 用户。 钔不需要用户对自己的兴趣、爱好和需求进行描述。有时用户对自己的需 求很难清楚、明确地表达出来，而用户的行为自然地反映了其兴趣和需求。借助 于w e b 服务器日志中的客观数据自动发现用户的兴趣和需求，能够减少主观性 和减轻用户参与的负担。 ( 3 ) 提供在线推荐和页面预取机制。由于w e b 用户的增加和网络固有的延迟， 用户对w e b 服务器的请求常常得不到及时的响应。为了提高服务质量，w e b 浏 览器提供缓冲机制，把用户曾经访问过的w e b 页面保存在本地机器，以便减少 再次获取该页面的时间，平衡网络的负载，提高响应速度。而w e b 预取却是对 用户未来的请求进行预测，把用户可能访问的页面预先取回放在本地或代理服务 器，当用户要访问这些缓冲过的页面时，就不必从远程服务器传输了，这样能大 大减少用户等待的时间。因此，w e b 预取是一种主动的缓冲 4 1 。可以将用户当前 的访问情况与应用w e b 日志挖掘技术发现的模式( 如频繁遍历路径或频繁访问页) 进行匹配，确定用户当前所遵循的浏览模式，并分析当前请求页面中的每一个超 链接，从反映用户兴趣的角度计算每一条超链接的质量，并把质量大于指定阀值 的超链接推荐给用户或将其指向的页面预先取到本地p 】。 ( 4 ) 发现商业智能，辅助商业决策。在电子商务网站，把w e b 日志和顾客交 易信息相结合进行挖掘，能够发现关联购买集合、顾客的购买趋势，以及潜在顾 客对商品的兴趣，从而对商品信息在页面的显示进行调整以方便顾客浏览和购 买，为顾客推荐相关商品，预测顾客的购买兴趣，还可以把潜在的顾客转变为实 际的购买。 l1 2 论文选题的意义 目前对w e b 日志挖掘的研究，主要是集中对用户会话( 用户在指定时间内 对某网站的一次浏览路径) 的研究。用户会话可能包含了多种信息需求。例如某 一使用者对于“书籍”、“软件”和“硬件”的信息都很有兴趣，因而浏览了网站 上有关这三方面的网页，因此在会话中就会隐含了三种信息需求。然而，利用传 统硬性聚类技术来分析用户会话时，只能将用户会话归类到某个较偏好的网页群 组中，而忽略了会话中用户对其它网页的偏好。因此，容易造成不合理的分析。 由于w e b 日志具有数据量大的特点，所以应用传统的模糊聚类算法( 如模糊c 9 基于模糊聚类的w e b 日志挖掘研究复旦大学硕士学位论文 均值) 对w e b 日志进行挖掘，效果并不是很好。同时，在计算用户会话之间的 相似度时，大多数只考虑了用户访问的相同网页的数量和网站的层次结构，却忽 略了体现用户兴趣的一个重要因素：用户浏览网页的时间，所以计算出来的相似 度可能并不准确，对结果的正确性会造成一定的影响。 因此，针对w e b 用户兴趣的模糊性、非单一性以及w e b 日志数据的特点， 使用高效率的模糊聚类算法对用户会话进行模糊聚类，可以在很大程度上避免传 统聚类的非此即彼的硬性和低效率。通过对聚类结果可以分析用户访问w e b 的 模式，设计出满足不同客户群体需要的个性化推荐网站。 1 2 国内外研究现状 目前，国内外有关w e b 日志挖掘的研究己经有很多，主要集中在对用户会 话进行挖掘【7 肫1 0 l ，以便发现用户的访问模式。现在己经可以看到很多有价值的 研究和应用成果。 文献 7 】中提出了一个基于代理的s y s k i l l & w e b e r i 软件，该软件通过分析用户 访问日志预测哪些页面是用户感兴趣的页面。 文献【1 1 】中介绍的w e b a c e 系统采用了分类算法来划分用户的上网访问的 历史记录信息，划分出的每一个分类代表用户在这方面的一个兴趣。 文献【1 2 】研究了一种文档聚类算法，利用该算法可以改善网站的设计。但没 有考虑个性化推荐的问题。 文献 1 3 1 设计了一个w e b 挖掘算法，利用模糊集理论挖掘用户浏览模式。 文献 1 4 1 所介绍的系统是一个主动推送网页的系统。它每天提供一些可能会 让用户感兴趣的网页，用户根据自己的兴趣来评价这些网页，系统则根据这个评 价信息自我调整，从而改善推送系统性能。该方法需要用户参与评价。 文献 1 5 】设计了一个个性化的新闻站点，结合用户的反馈信息提供个性化服 务。 文献【1 6 1 提出了两种个性化网站的方案及其实现，包括了用户定制和计算用 户兴趣度的方法。 文献 1 7 1 研究了如何跟踪用户的兴趣变化。 对用户访问模式的研究主要还是将数据挖掘技术应用于w e b 日志数据中， 或者是将w e b 日志数据经过一定的转换保存在数据库或数据仓库中，再直接利 用数据挖掘技术产生用户访问模式。主要的方法有以下几种： ( 1 ) 统计分析f l 。统计技术是最常见的获取用户访问模式的方法，可以通过 统计计算得到访问频率最高的网页、网页的平均浏览时间以及访问路径的平均长 度等统计信息。虽然这些统计信息不是很深刻的分析，但是再实际应用中可以很 好地改善系统性能，增强系统安全性，为网站拓扑结构地改造提供依据以及为电 子商务的销售决策提供支持等。 ( 2 ) 关联规则。在w e b 挖掘领域中，关联规则指的是满足给定置信度的网页 关系，这些网页往往被同时浏览，即使它们之间没有超链接存在。这些关联规则 可以帮助网站设计者改造网站的拓扑结构或是作为通过“提前取页“技术来减少 1 0 基于模糊聚类的w e b 日志挖掘研究 复旦大学硕士学位论文 网页的切换延迟的启发规则。 ( 3 ) 聚类【1 9 1 。聚类是指把具有相似性质的事物分在一组。在w e b 挖掘领域中， 主要是对网站的用户进行访问模式的聚类和对网页进行内容聚类。网站用户访问 模式的聚类知识可以应用于个性化网站中，为不同类别的用户动态生成针对该类 用户个性的网页。网页内容的聚类则多被用于搜索引擎的实现。 “) 分类。分类是把一个事物按照预先定义好的分类方法分组。通过对网站 现有用户进行聚类所得到的类别特征的抽取与选择，可以得到用以判断新用户所 属类别的分类依据。 ( 5 ) 序列模式。序列模式的挖掘致力于发现用户与网站的会话内所浏览的网 页之间在时间顺序上的关联关系。利用已经发现的频繁序列模式可以预测用户未 来的访问情况。 从1 9 9 6 年以来出现了许多针对不同日标的分析w e b 用户模式的研究项目和 商业软件。以下作一个简单的分类。分类的标准很多，其中主要的五种是： 1 ) 获取输入的数据来源( 服务器代理服务器客户机) ； 2 ) 输入数据的类型( 结构内容使用数据用户注册信息) ： 各数据集中包含的用户个数( 单个多个) ； 4 ) 各数据集中包含的网站个数( 单个多个) ： 5 ) 该项目产品所针对的应用领域类型( 通用型，个性化服务型网站修改型特 征描述型和系统改进型) 。具体的分类结果如图1 1 所示： 图1 - 1w e b 用户访问模式挖掘系统的分类 l - 3 论文的组织和主要内容 基于模糊聚类的w e b 日志挖掘研究复旦大学硬士学位论文 1 3 1 论文的组织 本文的后续章节按照如下的方式组织： 第2 章概述了数据挖掘和w e b 挖掘技术的基础，包括定义、概念和分类， 后面重点介绍了w e b 日志挖掘的内容、难点和研究方向，并对挖掘的一般过程 进行了深入分析和总结。 第3 章主要介绍了模糊聚类的基础知识，包括模糊集的基础知识和模糊聚 类理论的发展。最后详细介绍了聚类的经典算法- k 均值算法以及应用模糊集理 论后产生的模糊c 均值算法。 第4 章详细描述了w e b 日志预处理的整个过程，包括数据清洗、用户识别 和会话识别等。并详细介绍一种改进的用户会话相似度的计算方法，最后通过一 些实验数据说明计算的整个过程。 第5 章首先详细介绍了f c m d d 和r f c m d d 模糊聚类算法，并分析r f c m d d 算法的优点和缺点。并针对该算法的缺点提出了改进的r f c m d d 算法一基于分 裂层次的r f c m d d 算法。最后通过实验数据来说明该算法的优越性。 第6 章结合前面的w e b 日志挖掘技术，给出了一个个性化在线推荐实验系 统原型。主要介绍了该系统的特点、设计思想和结构。 第7 章总结了本文的工作，并给出了进一步的研究方向。 1 3 2 论文的主要内容 论文的工作是研究模糊聚类在w e b 日志挖掘中的应用。主要内容有以下几个 方面： ( 1 ) 提出了一个改进的用户会话相似度的计算方法。该方法既考虑了用户会 话之间相同网页的数量对会话相似度的影响，同时又考虑了网站的层次结构和用 户在网页上的停留时间对会话相似度的影响，这样可以更加准确的反映用户会话 之间的相似度。 ( 2 ) 提出了一个改进的w e b 日志数据聚类算法一一基于分裂层次的 i t f c s d d ( r o b u s tf u z z ycm e d o i d s ) 。r f c m d d 算法是一种健壮的，运行速度快， 并适合于大数据量数据的模糊分割聚类算法。不过r f c m d d 也有传统分割聚类算 法的缺点：对初始聚类中心敏感和聚类的个数必须事先给出。这容易导致聚类的 主观性和随意性，会影响到正确的聚类结果。而分裂层次聚类算法的优点就在于 通过分裂的方法来决定最终聚类的个数。因此，通过把r f c f l d d 算法和分裂层次 聚类算法结合起来，可以有效的克服上述缺点 ( 3 ) 提出了一个个性化在线推荐实验系统原型。该系统分为离线挖掘和在线 推荐两个部分，提供的个性化推荐服务可以直接面向匿名用户。离线挖掘部分主 要是利用基于分裂层次的r f c s d d 算法对用户会话进行聚类，得到用户会话聚类 集并生成推荐模式库。在线推荐部分主要是获取当前用户会话，然后和推荐模式 库中的模式进行匹配，自动产生推荐页面集，提供给用户，从而达到个性化推荐 的目的。 1 2 基于模糊聚类的w e b 日志挖掘研究复旦大学硕士学位论文 第2 章数据挖掘与w e b 挖掘技术 2 1 数据挖掘和w e b 挖掘技术概述 2 1 1 数据挖掘的定义和分类 数据挖掘( d a t am i n n i n g ) 是近年来随着数据库和人工智能技术的发展而出 现的一种全新的信息技术，是指从数据中提取模式的过程。同时，数据挖掘又是 一种决策支持过程，高度自动化地分析企业原有数据，做出归纳性推理，从中挖 掘出潜在地模式，预 狈0 客户的行为帮助企业决策者调整市场策略，减少风险，做 出正确决策。 数据挖掘可简单理解为：从数据中挖掘有用的信息，这样既能反映数据挖掘 的目的，同时，也说明了数据挖掘所处的阶段。数据是一个抽象的概念，数据的 特征化是数据挖掘的一个过程( 步骤) 。由于数据挖掘是针对海量数据中有效信息 的提取，数据挖掘是一个过程，首先应对过程提供一个合理进行的规则；其次是 挖掘，挖掘是个动词，在还没有确定主动者与被动者的关系时，是无法确定“挖 掘”应该使用什么时态和语态的；第三是有用的信息，数据挖掘的信息只有有用 才能确定其作用。 总之，数据挖掘是一门交叉学科，它把人们对数据的应用从低层次的简单查 询，提升到从数据中挖掘知识，提供决策支持。在这种需求牵引下，汇聚了不同 领域的研究者，尤其是数据库技术、人工智能技术、数理统计、可视化技术、并 行计算等方面的学者和工程技术人员，投身到数据挖掘这一新兴的研究领域，形 成新的技术热点。 目前存在很多数据挖掘方法或算法，有必要对这些方法进行分门别类。从不 同的角度看，数据挖掘技术有以下几种分类方法：挖掘对象、挖掘任务、挖掘技 术。 ( 1 ) 根据挖掘对象分，有如下若干种数据库或数据源：关系数据库、面向对 象数据库、空间数据库、时态数据库、文本数据源、多媒体数据库、异质数据库、 遗产( 1 e g a c y ) 数据库，以及互联网( w e b ) 。 ( 2 ) 根据挖掘任务分，有如下几种知识发现任务：分类或预测模型知识发现、 数据总结、数据聚类、关联规则发现、序列模式发现、依赖关系或依赖模型发现、 异常和趋势发现等等。如果以挖掘知识的抽象层次划分，又有原始层次( p r i m i t i v e l e v e l ) 的数据挖掘、高层次( h i g hl e v e l ) 的数据挖掘和多层次( m u l t i p l el e v e l ) 的数 据挖掘。应用比较多的有一下几种： 1 ) 聚类法( c l m e r i n g ) 聚类算法是通过对变量的比较，把具有相似特征的数据归于一类。因此，通 过聚类以后，数据集就转化为类集，在类集合中同一类中数据具有相似的变量值， 不同类之间数据的变量值不具有相似性。区分不同的类是属于数据挖掘过程的一 部分，这些类不是事先定义好的，而是通过聚类算法采用全自动方式获得a 通常， 聚类过程是数据挖掘过程的第一阶段。它首先把数据区分于不同的类，以便于做 进一步的分析。 基于模糊聚类的w e b 日志挖掘研究 复旦大学硕士学位论文 2 ) 分类法( c l a s s i f i c a t i o n ) 分类法是最普通的数据挖掘方法之一它试图按照事先定义的标准( 如通过 检查没有通过检查等) 对数据进行归类。 3 ) 关联规则 它要做的是从用户指定的数据库采掘出满足一定条件的依赖性关系。关联规 则形如“a 1 一a ，支持度= ，置信度= c ”，其中s 和c 是用户指定的支持度 和置信度的门限值，这种关联规则挖掘可以在不同的抽象概念层次上进行。例如 焉：“尿布_ 啤酒，支持度= 5 ，置信度= 5 0 ”与r 2 ：“婴儿用品类分饮料类， 支持度一2 5 ，置信= 8 0 ”相比，岛在更高的抽象层次上，更为宏观，因而有较 大的支持度和置信度，更适合高层决策需要。 如今，关联规则是商业销售、股票价格、银行交易等许多领域进行数据挖掘 的常用手段。对关联规则的研究则由串行算法转向并行算法；由对布尔型数据的 挖掘转向对数值型数据( q u a n t i t a t i v e ) 的挖掘。 4 ) 总结( s u m m a r i z a t i o n ) 规则挖掘 它要做的是从用户指定的数据库中挖掘出( 以不同的角度或在不同的层次上 的) 平均最小，最大、总和、百分比等等。挖掘结果用交叉表、特征规则、统计的 曲线图表等表示。 5 ) 预测( p r e d i c t i o n ) 分析 当分类的工作偏向于插入漏掉的数据、预测数据分类或发展的趋势时，这时 的工作称为预测分析。 6 ) 趋势( t r e n d ) 分析 趋势分析又叫时间序列分析，它是从相当长的时间内的发展趋势中发现规律 和趋势。 7 ) 偏差( d e v i a t i o n ) 分析 偏差分析称为比较分析，它将找出一系列判别式的规则，以区别用户设定的 两个不同类。 ( 3 ) 根据挖掘任务分，大多数数据挖掘的方法都基于机器学习、模式识别和 统计学等领域。最常用的数据挖掘技术是： 1 ) 统计分析方法( s t a t i s t i c sa n a l y s i s ) 主要用于完成总结知识和关联知识挖掘。对关系表中各属性进行统计分析， 找到它们之间存在的关系。在关系表的属性之间一般存在两种关系：a 函数关系 ( 能由函数公式表示的确定性关系) ；b 相关关系( 不能用函数公式表示的关系) 。对 它们可采用回归分析、相关分析、主成分分析等统计分析方法。 2 ) 决策树( d e c i s i o nt r e e ) 利用信息论中信息增益寻找数据库中具有最大信息量的字段，建立决策树的 一个节点，再根据字段的不同取值建立树的分支；在每个分支子集中重复建立下 层节点和分支，这样便生成一颗决策树。接下来还要对决策树进行剪枝处理，然 1 4 基于模糊聚类的w e b 曰志挖掘研究复旦大学硕士学位论文 后把决策树转化为规则，利用这些规则可以对新事例进行分类。典型的决策树方 法有分类回归树( c a r t ) 、i d 3 ，c a 5 等。典型的应用是分类规则的挖掘。 3 ) 遗传算法( g e n e t i ca l g o d t h m s ) 遗传算法是基于达尔文的进化论中基因重组、突变和自然选择等概念。这些 算法作用于对某一特定问题的组可能的解法。它们试图通过组合或“繁殖”现存 的最好的解法来产生更好的解法。利用“适者生存”的概念使较差的解法被抛弃， 从而导致解法的集合，即繁殖的结果得到改善。通常，解法的随机突变用来防止 算法受阻于好的但并非最优的解法。 4 ) 神经网络( n e u r a ln e t w o r k s ) 人工神经网络是模拟人类的形象直觉思维、是在生物神经网络研究的基础 上，根据生物神经元和神经网络的特点，通过简化、归纳、提炼总