（计算机系统结构专业论文）基于模糊聚类的web使用模式挖掘研究.pdf

重庆大学硕士学位论文 中文摘要 摘要 t n t e r n e t 网站正在从“以网站为中心”向“以用户为中心”发展，因此 i n t e r n e t 网站的发展趋势是个性化智能网站( p e r s o n a l i z a t i o ni n t e l l i g e n t w e bs i t e ) 。个性化智能网站应尽可能地迎合每个用户的浏览兴趣并且不断调整 自己来适应用户浏览兴趣的变化。具体的说就是，任何一个网站的用户，当他在 访问个性化智能网站时候，总有一种感觉，那就是：好像整个网站都是为他设计 的，特别友好，一切都是那么有用，都是自己当前很感兴趣的东西，仿佛是自己 的知音一般。针对目前w e b 网站多、信息量大而杂的情况，如何使用户在庞大的 网络数据资源中很容易地找到自己真正需要的内容成为当前研究的重点和热点。 目前，国内外对w e b 使用模式挖掘的研究主要集中在对用户浏览路径的研究 上，其中，聚类技术常被用来分析网站浏览者对网页的浏览偏好。但是，传统聚 类只能将每一使用者浏览路径归类于单一群组中，即事先假设每一个浏览路径只 包含单一种偏好，却忽略同一使用者浏览路径可能包含多个网页偏好。为此，有 学者将模糊聚类应用其中，但国内目前基本上都是使用基于模糊等价关系矩阵及 图的模糊聚类方法。同时，在分析浏览路径相似程度方面，往往是根据网页距离 来计算，当用户以完全不同的浏览路径来访问相同网页时，容易产生错误的分析 结果。 针对这种情况，本论文提出一个结合关联法则与目标函数模糊聚类技术的 w e b 挖掘体系。论文中首先过滤浏览路径中可能造成分析误差的超链接网页，再 利用关联法则计算网页之间的关联性，以网页关联法则置信度取代网页距离，在 此基础上计算用户浏览路径之间的相似程度，最后则运用f c - m d e 目标函数模糊 聚类技术对浏览路径进行聚类，将具有相似浏览偏好的使用者浏览路径聚集成 类，同时得到各类中访问频率高的目标网页。 最后，初步实现了一个个性化智能推荐网站的设计。 关键词：w e b 挖掘，模糊聚类，用户模式，个性化，智能推荐网站 里鏖奎堂堡主堂壁堡壅 基奎塑垩 a b s t r a c t w e bs e r v e r s a r en o w e v o l v i n g t h e m s e l v e sf r o m s e r v e r - c e n t e r e dt o c l i e n t - c e n t e r e d s e r v e r s ，s o t h et r e n do fi n t e m e tw e b s i t e s d e v e l o p m e n t i s p e r s o n a l i z a t i o ni n t e l l i g e n tw e bs i t e s p e r s o n a l i z a t i o ni n t e l l i g e n tw e b s i t es h o u l dc a t e r t oe v e r yw e bu s e r si n t e r e s t sa n da d a p ti t s e l f f r e q u e n t l yt ot r a c et h ef l u c t u a t i o no f w e b u s e r si n t e r e s t s i nm o r ed e t a i l ，w h e na nc u s t o m e ro fap e r s o n a l i z a t i o ni n t e l l i g e n tw e b s i t ei sv i s i t i n gt h i ss i t e ，h es h o u l dh a v es u c haf a m i l i a rf e e l i n gt h a ti ts e e m st h ew h o l e w e bs i t ei sd e s i g n e df o rh i ma n di ts e e n q sb o s o mf r i e n db e c a u s ei ti sv e r yc o n v e n i e n c e t o h i m ，a n d a l lt h ec o n t e n t sa r ev e r yu s e f u lw h i c hh ei s i n t e r e s t i n g i n w i t ht h e e x p l o s i v e l yg r o w t ho fi n f o r m a t i o ns o u r c e sa v a i l a b l eo nt h ew o r l dw i d ew e b ，i th a s b e c o m e i n c r e a s i n g l yn e c e s s a r yf o r u s e r st ou t i l i z ea u t o m a t e dt o o l si nf i n dt h ed e s i r e d i n f o r m a t i o nr e s o u r c e s s ot h ea p p l i c a t i o no fd a t am i n i n gt e c h n i q u e st ow o r l dw i d e w e b ( r e f e r r e dt oa sw e bm i n e ) h a s b e e nt h ef o c u so fs e v e r a lr e c e n tr e s e a r c hp r o j e c t s a n d p a p e r s a tp r e s e n t ，t h er e s e a r c ho nt h ew e bu s a g em i n i n gm o s t l yc o n c e n t r a t e do nt h e u s e ra c c e s sp a t t e r nw h i c hs t a t i s t i cc l u s t e r i n gt e c h n i q u e sa r eo f e nu s e dt oa n a l y s eu s e r p r e f e r e n c eo np a g e s h o w e v e g t h i sa p p r o a c hc a no n l ys o r te a c hu s e rs e s s i o ni n t oa s i n g l e c l u s t e r t h a t i s ，i ti g n o r e s au s e rs e s s i o n m a yc o n t a i n s e v e r a l b r o w s i n g p r e f e r e n c eb ya s s u m i n ga u s e rs e s s i o ni n c l u d eo n l ya s i n g l ep r e f e r e n c e a c c o r d i n gt o t h i s i n s u f f i c i e n c y , f u z z yc l u s t e r i n gt e c h n i q u e s w e r e p r o p o s e d i n s t e a dw h i l ei n d e t n l ，m o s t l y a r e f u z z ye q u i v a l e n c er e l a t i o n s h i pc l u s t e r i n g o r g r a p hc l u s t e r i n g t e c h n i q u e i nd o m e s t i c a tt h es a m e t i m e ，t h o s em e t h o d sc a no n l yu s ed i s t a n c eo f p a g e s t oc a c u l a t et h es i m i l a r i t yb e t w e e ns e s s i o n s t h e r e f o r , i fu s e r sb r o w s et h es a r n ew c b p a g eb y d i f f e r e n tp a t h s ，t h a tc a u s e sw r o n gr e s u l t s t h i sr e s e a r c hp r o p o s e saf r a m e w o r kw h i c hc o m b i n e st h et a r g e tf u n c t i o nf u z z y c l u s t e r i n ga n da s s o c i a t i o nr u l e s a tf i r s t ，t h i sa p p m a c h f i l t e r so u tt h en o i s yd a t a ( o u t l i e r h y p e r l i n kp a g e s ) w h i c hm a y c a u s ef a l s er e s u l t t h e n ，i te m p l o y sa s s o c i a t i o nr u l e st o c a c u l a t et h ec o n f i d e n c eo f t h er u l ea st h ea s s o c i a t i o nb e t w e e nd i f f e r e n tu r l a d d r e s s e s w h i c h r e p l a c e s t h e f o r r n e f l y m e t h o db a s e do nd i s t a n c e a n d t h e n ，c a c u l a t e t h e s i m i l a r i t yb e t w e e nt h es e s s i o n s a tl a s t ，af u z z yc l u s t e r i n gt e c h n i q u eb a s e do nt a r g e t f u n c t i o nn a m e df c m d ei sa d o p t e dt oc l u s t e rt h eu s e rs e s s i o n sw h i c hc a ns o r tt h e s e s s i o n sw h i c hc o n t a i n c l o s e l yi n t e r e s t si n t oac l u s t e ra n df i n dt h ef r e q u e n t l ya c c e s s e d i i 重庆大学硕士学位论文英文摘要 p a g e s i nac l u s t e r i nt h e e n d ，w e c o m eu pw i t hal o g i cf r a m eo fap e r s o n a l i z a t i o n i n t e l l i g e n t r e c o m m e n d a t i o nw e bs i t e k e y w o r d s ：w e bm i n i n g ，f u z z yc l u s t e r i n g ，u s a g ep a t t e r n ，p e r s o n a l i z a t i o ni n t e l l i g e n t r e c o m m e n d a t i o nw e bs i t e i l l 重庆大学硕士学位论文 1 绪论 1 绪论 1 1 论文的研究背景及选题意义 匿际互联网加快了信息传播的速度，相关的网络应用都以惊人的速度增长， 例如：电子商务、电子化客户关系管理( e c r m ，e l e c t r o n i c c u s t o m e r r e l a t i o n s h i p m a n a g e m e n t ) 、远程教育( d i s t a n c e l e a r n i n g ) 等。然而，网络上信息超载( i n f o r m a t i o n o v e r l o a d ) 问题的日益严重，却也一直困扰着网站浏览者与经营者，所以了解网站 浏览者的真正信息需求，为用户提供个性化的服务，避免不必要的信息传输，已 成为目前网站经营者相当重视的问题。 近年来，数据挖掘( d a t am i n i n g ) 和国际互联网( w o r l dw i d ew e b ) 应用研 究是信息时代两大活跃的研究领域，两者的结合构成了另外一火活跃的研究领域 一w c b 数据挖掘研究。 w e b 挖掘( w e bm i n i n g ) ，从广义上解释就是通过数据挖掘技术来分析与网 站相关的资料，例如：网站浏览记录( w e bl o g ) 、网页内容( w e bc o n t e n t ) 、 网络链接结构( w e bs t r u c t u r e ) 等。随着w e b 技术的发展，各种网站数量每天都 在急剧增加，特别是将w c b 转化为关键发展工具的信息网站( 电子商务网站) ， 采用各种手段使网站更加具有生命力成为每个经营者的首要 ：作。例如当前各类 电子商务网站风起云涌，建立一个电子商务并不难，困难的是如何使建立的电子 商务网站有收益。电子商务的竞争比传统的业务竞争更加激烈，原因有多方面， 其中一个因素是客户从一个电子商务网站转到另一个网站只需点击几下鼠标就可 以了。所以，及时了解用户的需求和特点，为每个用户提供个性化、智能化的服 务，以吸引大量的用户，就变得尤为重要。其中网站浏览记录，记录了使用者每 次访问网站的一些资料，因此最能反映使用者对网站的浏览需求。因此以数据挖 掘技术来分析网站浏览记录，已成为解决上述问题的主要工具之一。 同传统的数据挖掘一样，w c b 挖掘主要包括聚类、关联和序列分析。然而w e b 日志中存在着很多的噪音数据和信息的不完整性，这导致聚集只是一个模糊的边 界，聚集中的对象成员没有一个精确的定义。这样对象成员就有可能不只属于一 个聚类。为解决这一问题，我们采用一种在各个领域己广泛应用的技术一模糊理 论，它主要是一一种研究模糊性现象、不精确性现象的数学工具。将模糊集理论巾 的模糊聚类应用于w c b 挖掘，分析用户访问w 曲的模式，设计出满足不同客户群 体需要的个性化网站，进而增加企业的竞争力。 蘑庆大学硕士学位论文 1 绪论 目前在w e b 挖掘的研究中，在运用挖掘技术分析时，大多都没有仔细考虑到 网站浏览记录的资料特征与偏离网页( o u t l i e r ) ( 用户访问目的网页所必须经过的 中间链接，大多是用户不感兴趣的网页) 的影响，因此容易造成整个分析结果的 不完整，甚至可能分析出错误的模式( p a t t e r n s ) 。同时，使用者浏览路径中有可 能包含了多种信息需求。例如某一使用者对于“书籍”与“软件”或“硬件”的 信息都很有兴趣，因而浏览了网站上有关这三方面的网页，因此在其浏览路径中 就会隐含了三种信息需求。然而，在大多数的w e b 挖掘研究中，利用传统硬聚类 技术来分析使用者较偏好浏览的网页时 好的网页群组中，而忽略了浏览路径中 为不合理的分析。 只能将使用者浏览路径归类到某个较偏 使用者对其它网页的偏好。因此，就成 目前，国内外对计算机柔性技术的研究成为热点。所谓柔性技术，它包含粗 糙集理论、模糊理论、神经网络、遗传算法等。特别是模糊理论，在解决模糊性 问题上体现出较大作用。因此，针对w e b 用户兴趣的模糊性、非单一性，引入模 糊聚类对其浏览路径进行模糊聚类，在很大程度，l 避免了传统聚类的非此即彼的 硬性划分，更客观地体现真实的用户兴趣活动。因此，将模糊聚类应用于w e b 挖 掘，分析用户访问w e b 的模式，设计出满足不同客户群体需要的智能化网站，进 而增加企业的竞争力。 1 2 国内外现状综述 目前，国内外有关w e b 用户模式挖掘的研究已经很多，主要集中在对用户浏 览路径进行挖掘，9 ，1 0 】，到今天已经可以看到很多有价值的研究和应用成果。 文献 7 】中提出了一个基于代理的s y s k i l l & w e b e r t 软件，该软件通过分析用户 访问日志预测哪些页面是用户感兴趣的页面。 文献 4 2 介绍的w e b a c e 系统采用了分类算法来划分用户的上网访问的历史 记录信息，划分出的每一个分类代表用户在这方面的一个兴趣。 文献 4 3 研究了一种文档聚类算法，利用该算法可以改善网站的设计。但该文 没有考虑个性化推荐的问题。 文献 4 4 】设计了一个w e b 挖掘算法，利用模糊集理论挖掘用户浏览模式。 文献 4 5 所介绍的系统是一个主动推送网页的系统。它每天提供一些可能会让 用户感兴趣的网页，用户根据自己的兴趣来评价这些网页，系统则根据这个评价 信息自我调整，从而改善推送系统性能。该方法需要用户参与评价。 文献 4 6 1 设计了一个个性化的新闻站点，结合用户的反馈信息提供个性化服 务。文献 4 7 1 提出了两种个性化网站的方案及其实现，包括了用户定制和计算用户 兴趣度的方法。 重庆大学硕士学位论文 1 绪论 文献 4 8 研究了如何跟踪用户的兴趣变化。 1 2 1 用户访问模式的发现方法 目前国内外对用户访问模式的研究主要还是将数据挖掘技术应用于w e b 数据 中，或者是将w e b 数据经过一定的转换保存在数据库或数据仓库中，再直接利用 数据挖掘技术产生用户访问模式。主要的方法有以下几种： 1 、统计分析1 统计技术是最常见的获取用户访问模式的方法，可以通过统计计算得到访问 频率最高的网页、网页的平均浏览时间以及访问路径的平均长度等统计信息。虽 然这些统计信息不是很深刻的分析，但是再实际应用中可以很好地改善系统性能， 增强系统安全性，为网站拓扑结构地改造提供依据以及为电子商务的销售决策提 供支持等。 2 、关联规则 在w e b 挖掘领域中，关联规则指的是满足给定晟信度的网页关系，这些网页 往往被同时浏览，即使它们之间没有超链接存在。这些关联规则可以帮助网站设 计者改造网站的拓扑结构或是作为通过“提前取页“技术来减少网页的切换延迟 的启发规则。 3 、聚类【1 2 j 聚类是指把具有相似性质的事物分在一组。在w c b 挖掘领域中，主要是对网 站的用户进行访问模式的聚类和对网页进行内容聚类。网站用户访问模式的聚类 知识可以应用于个性化网站中，为不同类别的用户动态生成针对该类用户个性的 网页。网页内容的聚类则多被用于搜索引擎的实现。 4 、分类 分类是把一个事物按照预先定义好的分类方法分组。通过对网站现有用户进 行聚类所得到的类别特征的抽取与选择，可以得到用以判断新用户所属类别的分 类依据。 5 、序列模式 序列模式的挖掘致力于发现用户与网站的会话内所浏览的网页之间在时间顺 序上的关联关系。利用已经发现的频繁序列模式可以预测用户未来的访问情况， 从而指导针对某一类用户的广告的安置。 1 2 _ 2 现有用户模式挖掘系统的分类 从1 9 9 6 年以来已出现了许多针对不同目标的分析w e b 用户模式的研究项目和 商业软件以下作一个简单的分类。分类的标准很多，本文中采用了其中主要的五 种l 1 3 j ：1 ) 获取输入的数据来源( 服务器，代理服务器客户机) ；2 ) 输入数据的类 型( 结构内容使用数据佣户注册信息) ：3 ) 各数据集中包含的用户个数( 单个 要塞查兰堡主堂堡笙苎l 丝! 竺 多个) ；4 ) 各数据集中包含的网站个数( 单个多个) ；5 ) 该项目产品所纠对的 应用领域类型( 通用型个性化服务型网站修改型特征描述型和系统改进型) 。具 体的分类结果如图1 1 所示。 图1 1w e b 用户访问模式挖掘系统的分类 f i g 1 1t h ec l a s s i f i c a t i o no f w e b u s a g e m i n i n g 1 3 论文研究的主要内容 论文的工作主要是研究出一种面向w e b 使用模式的挖掘体系。主要内容有以 下几个方面： 1 改进o p a 算法，用来去除用户浏览路径中的偏离网页i 使用者在浏览网站时，可能会因为网站设计不当，而造成使用者在浏览某一 网页时，都必须经由某一固定的路径才可浏览该网页。因此，在分析这些受到外 在因素影响的网站浏览记录时，较容易受到记录中一些偏离值的影响。例如：利 用关联规则来分析网页之间的关联性时，就很容易由于该条路径经常被访问，使 得此路径上的每个网页彼此的关联性都很高，而造成使用者测览路径相似程度上 推导结果的不正确。因此，本论文首先用改进的o p a 算法将网站日志中的偏离网 页去除。 2 摒弃传统的基于距离的用户浏览路径相似程度计算方式，提出用关联法则 计算浏览路径相似程度； 4 重庆大学硕士学位论文 在计算两条使用者浏览路径彼此的相似程度时，传统的计算方法是根据使用 者浏览路径中网页与网页的距离( s i mj l a r i t ys c o f eo fs e s s i o n ) 来判断【2 ”，2 。 若两条浏览路径中的相同网页较多时，用这种方法计算出来的相似程度比较准确。 然而，当用户沿着两条完全不同的路径，浏览相同的目的网页时，仍然用基于距 离的方法计算相似程度，得到的结果并不能有效地反映两者的真实相似程度。为 解决这个问题，本论文提出以关联规则技术为基础来计算浏览路径的相似程度。 3 提出用f c m d e 模糊聚类算法对浏览路径进行模糊聚类分析； 大多数的w e b 挖掘研究中，利用传统聚类技术来分析使用者偏好浏览的网页时， 只能将使用者浏览路径归类到某个较偏好的网页群组中，而忽略了浏览路径中，使 用者对其它网页的偏好。因此，本论文采用f c m d e 目标函数模糊聚类技术来实 现对使用者浏览路径的模糊分群，既避免了出现传统聚类的”非此即彼”的硬划分结 果，又适用于大数据量、实时性要求高的w e b 使用模式挖掘。而且，f c m d e 算 法还可有效地处理数据中的孤立点。 4 初步设计了一个个性化智能推荐网站架构。 重庆人学硕士学伉论文 2 数据挖掘技术 2 数据挖掘技术 2 1 数据挖掘的定义 数据挖掘( d a t am i n i n g ) 是近年来随着数据库和人工智能技术的发展而出现 的一种全新信息技术，它是指从数据中提取模式的过程。同时，数据挖掘又是一 种决策支持过程，高度自动化地分析企业原有数据，做出归纳性推理，从中挖掘 出潜在地模式，预测客户的行为帮助企业决策者调整市场策略，减少风险，做出 正确决策。 数据挖掘可简单理解为：从数据中挖掘有用的信息，这样既能反映数据挖掘 的目的，同时，也说明了数据挖掘所处的阶段。数据是一个抽象的概念，数掘的 特征化是数据挖掘的一个过程( 步骤) 。由于数据挖掘是针对海量数掘中有效信 息的提取，数据挖掘是一个过程，首先应对过程提供一个合理进行的规则；其次 是挖掘，挖掘是个动词，在还没有确定主动者与被动者的关系时，是无法确定“挖 掘”应该使用什么时态和语态的；第三是有用的信息，数据挖掘的信息只有有用 才能确定其作用。 总之，数据挖掘是一门交叉学科，它把人们对数据的应用从低层次的简单查 询，提升到从数据中挖掘知识，提供决策支持。在这种需求牵引下，汇聚了不同 领域的研究者，尤其是数据库技术、人工智能技术、数理统计、可视化技术、并 行计算等方面的学者和工程技术人员，投身到数据挖掘这一新兴的研究领域，形 成新的技术热点。 2 1 1 技术上的定义 数据挖掘( d a t a m i n i n g ) 【l - 2 】就是从大量的、不完全的、有噪声的、模糊的、 随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又潜在有用 的信息和知识的过程。与数据挖掘相近的同义词有k d d 、数据融合、数据分析和 决策支持等p 】。这个定义包含几层含义：数据源必须是真实的、大量的、含噪声的； 提取的是客户感兴趣的知识；提取的知识要是可接受、可理解、可运用；并不要 求提取放之四海皆准的知识，仅支持特定的问题。 2 1 2 商业角度的定义 数据挖掘是一种新的商业信息处理技术，其主要特点是对商业数据库中的大 量业务数据进行抽取、转换、分析和其它模型化处理，从中提取辅助商业决策的 关键性数据。因此，从商业角度可定义数据挖掘为：为企业既定业务目标，对大 6 重庆大学硕士学位论文 2 数据挖掘技术 量的企业数据进行探索和分析，揭示隐藏的、未知的或验证已知的规律性，并进 一步将其模型化的有效方法【7 1 。 2 2 数据挖掘的分类 目前存在很多数据挖掘方法或算法，有必要对这些方法进行分门别类。从不 同的角度看，数据挖掘技术有以下几种分类方法：挖掘对象、挖掘任务、挖掘技 术。 2 2 1 根据挖掘对象分 有如下若干种数据库或数据源：关系数据库、面向对象数据库、空间数据库、 时态数据库、文本数据源、多媒体数据库、异质数据库、遗产( 1 e g a c y ) 数据库， 以及全球互联网( w e b ) 。 2 2 2 根据挖掘任务分 有如下几种知识发现任务：分类或预测模型知识发现、数据总结、数据聚类、 关联规则发现、序列模式发现、依赖关系或依赖模型发现、异常和趋势发现等等。 如果以挖掘知识的抽象层次划分，又有原始层次( p r i m i t i v el 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 u s t e r i n g ) 聚类算法是通过对变量的比较，把具有相似特征的数据归于一类。因此，通 过聚类以后，数据集就转化为类集，在类集中同一类中数据具有相似的变量值， 不同类之间数据的变量值不具有相似性。区分不同的类是属于数据挖掘过程的一 部分，这些类不是事先定义好的，而是通过聚类算法采用全自动方式获得。 通常，聚类过程是数据挖掘过程的第一阶段。它首先把数据区分于不同的类， 以便于做进一步的分析。 2 分类法( c l a s s i f i c a t i o n ) 分类法是最普通的数据挖掘方法之一。它试图按照事先定义的标准( 如：通 过检查没有通过检查等) 对数据进行归类。 3 关联规则 它要做的是从用户指定的数据库采掘出满足一定条件的依赖性关系。关联规 则形如”4 斗爿：，支持度= j ，置信度= c ”，其中s 和c 是用户指定的支持度 和置信度的门限值，这种关联规则挖掘可以在不同的抽象概念层次上进行。例如 r ，：“尿布j 啤酒，支持度= 5 ，置信度= 5 懈”与 r ：“婴儿用品类斗饮料类，支持度= 2 5 ，置信度= 8 0 ”相比，b 在更高的 抽象层次上，更为宏观，因而有较大的支持度和置信度，更适合商层决策需要。 垩盎查堂堡主兰垡丝苎 ! ：塑塑望塑! ! 苎 如今，关联规则是商业销售、股票价格、银行交易等许多领域进行数据挖掘 的常用手段。对关联规则的研究则由串行算法转向并行算法；由对布尔型数据的 挖掘转向对数值型数据( 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 ) 分析 偏差分析又叫比较分析，它将找出一系列判别式的规则，以区别用户设定的 两个不同类。 2 2 3 根据挖掘技术分 大多数数据挖掘的方法都基于机器学习、模式识别和统计学等领域。最常用 的数据挖掘技术是： 1 统计分析方法 主要用于完成总结知识和关联知识挖掘。对关系表中各属性进行统计分析， 找到它们之间存在的关系。在关系表的属性之间一般存在两种关系a 函数关系( 能 由函数公式表示的确定性关系) ；b 席目关关系( 不能用函数公式表示的关系) 。对 它们可采用回归分析、相关分析、主成分分析等统计分析方法。 2 决策数( d e c i s i o nt r e e ) 利用信息论中信息增益寻找数据库中具有最大信息量的字段，建立决策树的 一个节点，再根据字段的不同取值建立树的分支；在每个分支子集中重复建立下 层节点和分支，这样便生成一颗决策树。接下来还要对决策树进行剪枝处理，然 后把决策树转化为规则，利用这些规则可以对新事例进行分类。典型的决策树方 法有分类回归树( c a r t ) 、i d 3 、c 4 5 等。典型的应用是分类规则的挖掘。 3 遗传算法( g e n e t i c a l g o r i t h m s ) 遗传算法是基于达尔文的进化论中基因重组、突变和自然选择等概念。 这些算法作用于对某一特定问题的组可能的解法。它们试图通过组合或“繁 殖”现存的最好的解法来产生更好的解法。利用“适者生存”的概念使较差的解 重庆大学硕士学位论文 2 数据挖掘技术 法被抛弃，从而导致解法的集合，即繁殖的结果得到改善。 通常，解法的随机突变用来防止算法受阻于好的但非最优的解法a 4 神经网络( n e u r a l n e t w o r k s ) 人工神经网络是模拟人类的形象直觉思维、是在生物神经网络研究的基础上， 根据生物神经元和神经网络的特点，通过简化、归纳、提炼总结出来的一类并行 处理网络。利用其非线性映射的思想和并行处理的方法，用神经网络本身结构可 以表达输入与输出的关联知识。它以m p 模型和h e b b 学习规则为基础，建立三 大类多种神经网络模型：前馈式网络、反馈式网络、自组织网络，完成输入空间 与输出空间的映射关系，是通过网络结构不断学习、调整，最后以网络的特定结 构来表达的，没有显式函数表达。 5 粗糙集方法( r o u g hs e t ) 粗糙集方法是模拟人类的抽象逻辑思维，它以各种更接近人们对事物的描述 方式的定性、定量或者混合信息为输入，输入空间与输出空间的映射关系是通过 简单的决策表简化得到的，它通过考察知识表达中不同属性的重要性，来确定哪 些知识是冗余的，哪些知识是有用的。进行简化知识表达空间是基于不可分辨关 系的思想和知识简化的方法，从数据中推理逻辑规则作为知识系统的模型。它是 基于一个机构( 或一组机构) 关于一些现实的大量数据信息，以对观察和测量所 得数据进行分类的能力为基础，从中发现、推理知识和分辨系统的某些特点、过 程、对象等。 6 模糊论方法 利用模糊集合理论对实际问题进行模糊聚类分析、模糊评判、模糊决策和模 糊模式识别。模糊性是客观存在的，系统的复杂性越高，精确化能力越低，也就 意味着模糊性越强。这是z a d e h 总结出的互克性原理。以上提到的模糊方法都取 得了较好的效果。 7 关联规则 关联规则是描述数据库中数据项之间存在潜在关系的规则，数据项之间的关 联即根据一个事务中某些项的出现，可推导出另一些项在同一事务中也出现，挖 掘关联规则的问题可以分为：发现最大项目集和生成规则两个步骤。而发现最大 项目集是挖掘关联规则的核心。关联规则挖掘算法中，最初有a i s h e 和s e t m 两 个算法，但它们在执行过程中产生了很多不必要的候选项目集，计算机较大。而 a p r i o r i 算法是挖掘关联规则的经典算法。因而在关联规则挖掘中处理的数据量很 大，所以需要采用一些有效的技术来提高算法的效率。另外可以使用并行技术柬 解决。在并行算法中涉及了计算、通讯、内存利用等的协调关系。其实，有价值 的关联规则经常出现在相对较高的概念层上，从较低的概念层中很难发现有用的 重庆大学硕十学位论文2 数据挖拥技术 关联规则。目前关联规则已经从单一的概念层发展到多概念层上，在概念层上一 层层往l f ，从一般到具体，发现的关联规则能提供的信息也更具体，这是个逐步 深化的知识发现过程，成为广义关联规则。 2 3 数据挖掘的过程 数据挖掘过程一般包括问题定义、数据收集、数据预处理、选择和运行挖掘 算法、分析和解释挖掘结果等步骤，其中任意两个阶段之间都可能需要多次反复。 1 问题定义 清晰地定义业务问题，认清挖掘地目的是数据挖掘地重要一步，它驱动了整 个数据挖掘过程，在很大的程度上决定着数据挖掘的效果甚至成败。这一阶段通 常需要两部分人员参与：数据挖掘分析人员和领域专家。他们相互配合，共同完 成问题定义。 2 数据收集 根据定义的问题和用户的需求选取所有与业务对象有关的适用于数据挖掘的 数据。收集数据必须考虑到以下几个方面：a 数据格式。通常特定的挖掘算法只能 使用特定的数据格式，因此必须进行相关格式转换。b 提取的数据要具有代表性。 各个类别的数据在概率分布上要符合实际情况。c 只需选择与特定挖掘任务相关的 属性集。 3 数据的预处理 该阶段主要包括噪音的处理，空值的处理，连续数据的离散化等。 4 选择和运行挖掘算法 这个阶段的任务是：针对具体问题， 据进行挖掘，提取出用户所需要的知识。 应用。 选择合适的挖掘算法，对预处理后的数 这个阶段通常包括特定挖掘算法的反复 没有通用的数据挖掘方法，特定的挖掘技术只适用于特定问题的求解。因此， 选择合适的挖掘算法对挖掘结果的价值影响很大，这里包括选取合适的模型和参 数，并使发现的模式符合应用的要求。 5 分析解释结果 为了使数据挖掘得到的模式容易被用户理解和接受，通常需要用到文档、图 表和可视化等易于被人接受的技术将它直观地表示出来。 重庆大学硕士学位论文 3 w e b 挖掘技术 3w e b 挖掘技术 3 1 数据挖掘与w e b 国际互联网地日益普及，各种形式的信息大量地产生和收集导致了信息爆炸。 虽然i n t e m e t 上有海量地数据，但由于w c b 是无结构的、动态的，并且w e b 页面 的复杂程度远远超过了文本文档，人们要想找到自己想要的数据犹如大海捞针。 在面i 临如此庞大的信息空间的情况以及w e b 信息组织的无序化，搜索是解决网络 信息的无序化和混乱的一个基本方法，现代社会的竞争趋势要求对这些信息进行 实时的和深层次的分析，如何利用数据挖掘的知识，进一步提高w e b 信息搜索的 性能是众多学者研究的热点问题。 搜索引擎( s e a r c he n g i n e ) 的出现在一定的程度上解决人们对信息的需求，但 远没有达到令客户满意的程度。信息检索界丌发了许多搜索引擎，但其覆盖率有 限，因此查全率低，一般的搜索引擎是基于关键字的查询，命中率较低，另外不 能针对特定的客户给出特殊的服务，因此每个人感兴趣的东西是不一样的，因此 不具有个性化。解决这些问题的个途径，就是将传统的数据挖掘技术和w e b 结 合起来，进行w e b 挖掘。w c b 挖掘就是从w e b 文档和w c b 活动中抽取感兴趣的 潜在的有用模式和隐藏的信息。 o r e ne t z i o n i 口2 】于1 9 9 6 年提出w e b 挖掘概念。他认为w e b 网页是有结构的并 且是可以挖掘的。文献 1 4 、 3 3 3 5 提出了多层数据库的概念，打算将w e b 转换 成一个庞大的多层次的数据库，然后基于它进行数据挖掘。然而o r e ne t a i o n i 等认 为，由于w e b 的动态和混乱，这种方式很难实现。但是随着技术的发展，基于多 层数据库的思想，已经开发出了一些试验系统。随着x m l 的成熟与广泛应用，基 于多层数据库的思想w e b 数据挖掘有着更大的开发潜力。 对有效的数据仓库和数据挖掘而言，w c b 似乎太庞大了。w c b 的数据量目前 以兆兆字节( t e r a b y t e s ) 计算，而且仍然在迅速地增长。这使得几乎不可能去构 造一个数据仓库来复制、存储或集成w e b 上地所有数据。 w c b 页面地复杂性高于任何传统地文本文档。w e b 页面缺乏统一的结构，它 包含了远比任何组书籍或其它文本文档多得多的风格和内容。 w c b 是一个动态性极强的信息源。w c b 不仅以极快的速度增长，而且其信息 还在不断地更新。新闻、股票市场、公司广告和w c b 服务中心都在不断地更新着 各自地页面。链接信息和访问记录也在频繁地更新之中。 1 4 重庆大学硕十学位论文 3 w e b 挖掘技术 w e b 面对的是一个广泛地形形色色地客户群体。 w c b 上的信息只有很少的一部分是相关的或是有用的。据说9 9 的w e b 信息 相对9 9 的客户是无用的。虽然这看起来不是很明显，但一个人只是关心w e b 上 的很少很少一部分信息确是事实。w e b 所包含的其余信息对客户来说是不感兴趣 的，而且会淹没所希望得到的搜索结果。这些问题已经推动了如何有效地发现和 利用因特网上资源地研究工作。w e b 挖掘是一个更具挑战性地课题。 w e b 网站的所有访问者都将会留下浏览的踪迹，这些信息自动存储在w e b 服 务器的日志文件内。w e b 分析工具可以通过分析和处理w e b 服务器的日志文件生 成有意义的信息。例如有多少人访问了该页面，他们从哪里来，哪些页面最受欢 迎等。当前经济模式的变化，从传统的实体商店到i n t e r n e t 上的电子交易，同时也 改变了销售商和顾客的关系。现在网上顾客的流动性很大，他们关注的主要因素 是商品的价值，而不象以前注意品牌和地理因素。因此，电子商务一。个主要的挑 战是需要了解到顾客尽可能多的爱好、价值取向，以保证在电子商务时代的竞争 力。数据挖掘可用来发现不明显的、有潜在价值的数据。w c b 上数据挖掘的潜力 之一在于应用最新的数据挖掘算法，分析i n t e m e t 服务器上的日志以及顾客、销售 和产品的外部数据，得到有用的知识信息。 在日益激烈的电子商务买方市场竞争中，任何与消费者行为有关的信息对商 家来说都是非常宝贵的。虽然电子商务网站的后台数据能够记录下来丰富的交易 信息和顾客相关的数据，但是这些数据资源中所蕴涵的大量有益信息至今却未能 得到充分地挖掘和利用。 近年来兴起的数据挖掘技术为解决这个问题带来了一线曙光。通过在w e b 上 应用数据挖掘技术( 即w e b m i n i n g 技术) ，可以分析和预测顾客的将来行为。 3 2 w e b 挖掘概念及其分类 3 2 1w e b 数据挖掘、w e b 信息检索、搜索引擎 w e b 数据挖掘( w e b d a t am i n i n g ) ，简称w e b 挖掘( w 曲m i n i n g ) ，是数据挖 掘技术在w e b 环境下的应用，是集w e b 技术、数据挖掘技术、信息科学等多个 领域的一项技术。是从大量的w e b 文档集合和在站点内进行浏览的相关数据中发 现蕴涵的、未知的、有潜在应用价值的、非平凡的模式( p a r t e r n s ) 。 相近的技术有： 1 w c b 信息检索是从信息检索技术发展过来的，它最本质的特征是系统对 w e b 文档集合和客户的需求集合的匹配与选择。随着人工智能的发展和应用，有 人提出了智能信息检索( i i r ) 的概念。 2 搜索引擎：最早的目录型的搜索引擎不提供基于关键字的查询功能，从严 重庆大学硕士学位论文 3 w e b 挖掘技术 格意义上讲，还不能算是搜索引擎。搜索引擎原意是根据客户的检索请求( 一般 是基于关键词) ，通过检索索引找出匹配的文档( 或链接) ，按照相关度返回给 客户。从这点上来讲，搜索引擎是w e b 信息检索的一个实例( 应用) 。然而，w e b 上的信息具有巨量的、异构的、非结构或半结构的、动态的、分布的等特点，与 传统的信息检索有很大的不同。在这种情况下，越来越多的搜索引擎正在积极地 用w e b 数据挖掘技术来改善检索性能。在技术层面上可以认为w e b 信息检索和搜 索引擎是等价的。 w c b 数据挖掘和w c b 信息检索是两个不同的技术，在方法论、着眼点、使用 目的、评价方法以及使用场合上都是不同的。笔者认为应该是现代信息检索利用 数据挖掘技术来进行分类聚类，从而提高信息检索性能。这些观点的不同，主要 原因是概念的界定问题。w e b 信息检索和w c b 数据挖掘两者是相辅相成的，互为 补充，各有所长。随着技术的相互渗透，它们之间的差别将会逐渐缩小。 3 2 2w e b 数据挖掘的分类 w e b 数据挖掘，可以分为三类：内容挖掘( c o n t e n t m i n i n g ) 、结构挖掘( s t r u c t l l r e m i n i n g ) 、客户使用记录挖掘( u s a g em i n i n g ) 。但也有一些学者将其划分为两个 部分：内容挖掘和客户访问记录挖掘，其中结构挖掘的内容也有人将其归于内容 挖掘f 2 】【2 ”，a 雨p , 分为内容挖掘和使用记录挖掘。笔者倾向于三种分类方式。w e b 挖掘分类如图3 1 ： 图3 1w e b 挖掘分类 f i g u r e3 1c l a s s i f ic a t i o no fw e bm i n i n g 3 3w e b 内容挖掘 w e b 文本挖掘的对象是w