（计算机软件与理论专业论文）基于web使用挖掘和关联规则的页面推荐模型的研究与实现.pdf

摘要 w e b 使用挖掘是w e b 挖掘领域中的一个重要研究方向它对于发现用户访 问网站的规律、提高w e b 系统的性能和实现w e b 系统的个性化服务等方面都 具有重要意义将w e b 使用挖掘技术和个性化推荐技术相结合就可以实现基于 w e b 使用挖掘的个性化服务( p s w u 岬。常见的p s w u m 是基于w e b 使用挖掘 的页面推荐服务 p r w u 的，面在实现p r w u m 时常用的推荐技术是关联规则 本文对基于w e b 使用挖掘和关联规则的页面推荐模型( p r w a r ) 及其相关算 法进行了研究p r w a r 贯穿了w e b 使用挖掘过程中的数据预处理、模式发现 和模式分析与应用三个阶段它一般分为离线部分和在线部分离线部分的处 理流程是：先对w e b 日志数据进行数据预处理，然后进行模式发现来获得频繁 访问模式在线部分的处理流程是：在线获得用户访问序列后对其进行某种处 理；然后基于频繁访问模式获得关联规则；最后对关联规则进行选择，把得到 的规则集中的后项加入页面推荐集合本文围绕p r w a r 所傲的主要工作如下。 ( 1 ) 提出了一种用于频繁访问模式挖掘的算法( s i ) h p ) s d h p 算法使用了 a p r i o r i a l l 算法中对事务进行连接时所用的技术，并借鉴了d h p 算法中的h a s h 技术及修剪技术来对事务数据进行处理这三者的不同点是：d h p 算法挖掘的 数据是无序的，而s d h p 算法和a p r i o r i a n 算法挖掘的数据是有序的 ( 2 ) 提出了一种利用事务划分进行页面推荐的方法m ) t p m 是对用户访 问序列运用m f p 算法进行事务划分后再进行页面推荐，而常见的利用滑动窗口 进行页面推荐的方法( s w i v 0 是利用滑动窗i ：1 得到子序列后再进行页面推荐 ( 3 ) 提出了一种基于事务划分的页面推荐模型( p r b t ) 它是以本文提出的 s d h p 算法和t p m 为基础，而常见的基于滑动窗口的页面推荐模型( p p b s w ) 是以a p r i o r i a l l 算法和s w m 为基础p r b t 和p r b s w 都属于p r w a r ( 4 ) 基于n e t 平台设计和实现了一个页面推荐原型系统( p r p s ) 它贯穿了 w e b 使用挖掘过程中的三个阶段，由五大功能模块组成p r p s 用饼语言模拟 实现了p r b t 和p r b s w 两种页面推荐模型及其相关的算法。 在p r p s 上进行实验表明：s d h p 算法不仅减少了候选项集的生成，而且压 缩了事务数据库的规模，所以它相比a p n o r i a l l 算法可以减少扫描数据库的时 闻，提高算法的执行效率；t p m 相比s w m 得到的推荐结果更加全面和更加准 确因此得出结论：p r b t 的综合性能优于p r b s w 的综合性能 关键词：w e b 使用挖掘、关联规则、频繁访问模式、事务划分、页面推荐模型 a b s t r a c t w e bu s a g em i n i n gi st h eh o tr e , a r e l ai s s u t ! o fw e bm i n i n g i tp l a y s 锄i l n a p o r l a n tr o l ei nt h e d i s c o v e r yo fv i s i t o r s b r o w s i n gl l l a v i o r s , t h ei m p r o v e m e n to fw c bs y s t e m a n dt k i m p l e m a 出岫mo f 讲躺伪l a l i z e ds c i v i o f w e bs y s t a a l b o t hw e bu s a g em i n i n ga n dp e m o n a l i z c d r e e o m m d a t i o nt e e h n l o g ym u s e df o rt h ep e r s o n a l i z e ds e l v i c cb a s e do nw e bu s a g e m i n i n g o s w o m ) 1 k 成恤dp s w o mi il h ep a g er o m m e n d a t i o l lb a s e do dw c bu s a g e m i , i n g o r w u m ) , a n d t h e n o r m a lr e c o m m e n d a t i o n m e t h o d o f t h c p r w u m i s a s s o c i a t e f u l c i nt h ep a p e r , t h ek e ya l g o r i t h m so tp a g er e c o m m e n d a t i o nm o d e lb a s e do nw e bu s a g em i n i n g a n da s s o c i a t en i l eo r w a r ) 懈s t u d i e di nd e t a i l t h ep r w a rc o n s i s t so ft h r e ep a r t so fw e b u s a g em i n i n gw h i c hmd a t a 弘q m 嘲i 唱p a u e r nd i r 沁o v c r ya n dp a t t e r na n a l y s i s i ti n e l t t d b o t t l i u ep a r ta n do n l i n cp a r t t h cp r o e e uo ft h co f l l i n ep a r ti sp r e p r o c e s s i n gt h ew e bl o ga n d d i s e o v e r i n gf r r a l u e n ta c 嘲si j a t t c r n s mp r o c e s so ft h eo n l i p a r t 缸a c q u i r i n gu l 寸鸯嘲l s e x l u e n e e s - o b t a i n i n ga s s o c i a t er t t l c sb a s e do nf l l u e n ta 嘲sp a t t e r n sa n da t t a i n i n gt h eb a i ：k i t e mo fa s s o c i a t er u l e s 鹞t h er e c o m a c n d e dp a g eb ys e l e c t i n ga s s o c i a t en t l e s t h cm a i nw o r ko f t h et h e s i si ss h o w e da 3f o l l o w i n g ： 1 aa l g o r i t h m ( s d m ) w l a i e l ii sf o rt h eu o fd i 趾o v e r i n g 蠹戡删a c c e s sp a t t e r n si s p r o p o s 缸i tu 嘲t h ek c 虹时i o 醪w h i e l j iu s e df o rl i n k i n gt l a c 1 1 s n s a c l i o l l l si na p i i 0 圳a n d i i i j l j t mh a s hm e t h o da n dp r i m i n gm c t l a o dw h i c ha i eu s e df o rp r o e e i n gt h et h et r a n s 枷o n l li n d i mm d i f f e r e n c ei st h a td i t pp r o e 潮1 1 1 0o r d c rd a t a , b ms 1 ) i - i pa n da 呻血p r o c e s st h e o r d e rd a l a zam e t h o d o l l v t ) w h i d ai su s e df o rp a g er e c o m m e n d a t i o nb a s e do i lh 馏删o np a r t i t i o n i t r e n d s p a g e sb a s e d0 1 1i r a m a c t i o np a r t i t i o na f l e ri , r o c i n gl i 鲥s ta 0 0 鼬s e q u e n c e sb y 腑a l g o l b u t t l a c m c t h o d ( s w m ) w l a i e l a i s u s e d f o r p a g er e c o m m e n d a t i o n b a s e d o n s l i a i n s w i n d o wr e e o m m e l l d sp a g e sa 矗玎a c q u i r i n gu 翻淞。a c c e s se l a i k ls e q u m 赋sb ys f i d i n gw i n d o w 3 ap a g er e c o m m a a c l a t i o nm o d e lb a s e do n 自r a n s a e t i o n o r m 9 缸p r o p o s c c l i ti sb a s e do f s d l 坤a n dt p m , b u tt h ep a g er e c o m m e n d a t i o nm o d e lb a t e d0 ns l i d i n gw i n d o w o r b s w ) i s b a s e do na p r i o r i a ua n ds w m b o t hi r b ta n dp r b s wb e l o n gt op r w a r 4 d e s i g n i n ga n dd e v e l o p i n gap a g er e , c o m m e n d a t i o np r o t o t y p es y s t e m 口r p s ) b a s e d 0 1 1 1 1 n e tp h t f o r m 皿凼s y s t e mt b 蕾o u g l l st h r e ep a r t so fw e bu s a g em i n i n ga n dc o n s i s t so fs i x f l m c l j o l lm o d u l e s i th a sr e a l i z e di r 1 3 ta n dp r b s wa n dt h e i rr e l e v a n ta l g o r i t h mb yc 帆 t h ce x p e r i m e n t a lr e , s u i nn 地i 。r p ss h o wt h a ts d h pn o to n l yr e d u c e sc a n d i d a t es e t g e l i e r a t i o n , b u ta l s o m p i i 端t h es i z eo f t r a m a e t i o nd a t a b a s e , i tc o m p a r i n gw i t ha l 坷。斛i 锄托d 峨t l a cc o m p t l t a t i o n a lc o s ts i g n i f i c a n t l y ；a n dt p mc o m p a r i n gw i t hs w m 锄a e q n i r e e s p e c i a l l ya l l - r o u n da n da c c u l t a t cr e e o z m l m d e a tr e s u l t s i n1w o r d , s y a t l a e t i e a t lf l l l l c t i o l l l o ft h e p r b tj | b e t t e rt h a nt h ep r b s w k 町w o r d s ：w e bt t s a g cm i n i n g , a s s o c i a t en i l e ，f r e q u e n t 嘲l ，a l t e m l gt r a n s a c t i o np a r t i t i o , , p a g er e c o l n d a t i o nm o d e l i i 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及 取得的研究成果据我所知，除文中已经注明引用的内容外，本论文 不包含其他个人已经发表或撰写过的研究成果对本文的研究做出重 要贡献的个人和集体，均已在文中作了明确说明并表示谢意 作者签名：日期：塑立竺 学位论文授权使用声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆被查阅有权将学位论文的内容编入有关数据库进 行检索有权将学位论文的标题和摘要汇编出版保密的学位论文在 解密后适用本规定 学位论文作者张叶删导师签名：h ) 专 华东师范大学硕士学位论文 1 1 研究的背景及意义 第一章绪论 随着计算机网络在流量、规模和复杂度等方面的飞速增长，i n t e r a c t 已经成 为一个巨大的、分布广泛的和全球性的信息服务中心i n t e r n e t 上的信息资源不 仅种类繁多，而且数量巨大，使得人们在面对这些海量的信息时来不及选择和 消化就淹没在繁杂的信息中，此现象称为信息过载【n 另一方面，i n t e r a c t 上信 息资源分布的广泛性又给用户寻找感兴趣的信息增加了困难，用户不知道如何 更有效地发现自己所需的信息资源，也就是所谓的信息迷失l 人们当前主要 借助搜索引擎来检索w e b 上的信息，但是大多数搜索引擎缺少主动性，没有考 虑用户的兴趣偏好和用户问的差异，所以无法有效地解决信息过载和信息迷失 的问题为了解决上述问题，各国的研究人员尝试了多种方法。其中比较好的 方法是选择w e b 个性化服务作为突破口 w e b 个性化服务0 1 是一种针对不同用户提供不同的服务策略和服务内容的 服务模式它通过收集和分析w e b 用户的信息来学习用户的兴趣和行为，进而 实现主动推荐服务w e b 挖掘( w e bm i n i n g ) 是实现w e b 个性化服务的核心技术 之一，它是数据挖掘技术在w e b 信息处理中的应用w e b 挖掘f l 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 l l i n g ) 和 w e b 使用挖掘( w e bu s a g em i n i n g ) ，其中w e b 使用挖掘在w e b 个性化服务中扮 演着重要角色 w e b 使用挖掘i 3 】是将数据挖掘的算法运用到w e b 服务器日志文件的挖掘 上，从而发现有意义的、隐藏的访问模式和规则的过程它通过对用户浏览网 站时的使用数据进行收集、分析和处理，建立了与用户行为相关的兴趣模型 w e b 站点的管理者通过这些模型就可以理解用户的访问行为，再运用一些个性 化推荐技术，就可以为用户提供页面推荐、商品推荐和邮件推荐等各种个性化 的推荐服务 将w e b 使用挖掘技术和个性化推荐技术结合使用，就可以使得w e b 站点能 够获取用户的访问兴趣，为用户提供贴近它们访问兴趣的个性化推荐服务，从 而能够提高老用户对网站的忠诚度和吸引更多的新用户在现在这个以用户为 中心的网络世界里，拥有的用户越多，网站的核心竞争力就越强因此，基于 w e b 使用挖掘的个性化服务就构成了一个非常活跃的研究领域，它无论是在理 论研究还是在商业应用上都具有重要意义 华东师范大学硕士学位论文 基于w e b 使用挖掘的个性化服务( p s w u m ) 中最常见的一种是基予w e b 使 用挖掘的页面推荐服务( p r w u m ) p r w u m 是通过w 曲使用挖掘获得用户浏 览页面时的兴趣取向，从而向用户推荐它们可能感兴趣的页面对于以提供内 容服务为主要功能的w e b 站点( 例如新浪和搜狐等门户网站) 来说，向用户提 供这种形式的个性化服务对它们来说具有重要的意义因为它们只有这样做才 能拓展更多的用户，从而提高自身的竞争力，就可以在激烈的竞争中立于不败 之地目前，在实现基于w e b 使用挖掘的页面推荐服务时最常用的推荐技术是 关联规则，本文也就是以此为背景，对基于w e b 使用挖掘和关联规则的页面推 荐模型及其相关的技术迸行研究 1 2 国内外研究的现状 目前国内外基于w e b 使用挖掘的研究工作大致可分为以下三类闭： ( 1 ) 以分析w e b 站点性能为目标 主要从统计学的角度，对日志数据进行简单的统计，得到用户访问最多的 页面、单位时间访闯数、访问数量随时闻分布图等绝大多数商用及免费的 w 曲日志分析工具都属于此类 ( 2 ) 以理解用户意图为目标 c h 蛐【4 瞎人提出的最大前向引用路径0 讧觚i m a lf o r w a r dp a t h ) 的发现算法， 以及h a r t i 习等人使用的数据立方体方法，便是此类的典型代表 ( 3 ) 以改进w e b 站点设计为目标 通过挖掘用户的频繁访问路径和用户聚类，重构站点的页面之间的链接关 系。以更适应用户的访问习惯，同时为用户提供个性化的信息服务 现有的用于个性化推荐方面的技术主要有以下几种类型叫： ( 1 ) 基于用户概要文件的个性化( u s e rp r o f i l e - b a s e d ) 基于用户概要文件的个性化技术被用于显示与预先定义好的用户概要文件 相关的内容用户的概要文件是指用户在注腮的时候提供的一些个人的相关信 息，诸如：姓名，年龄，职业，兴趣爱好等等由于这种技术只是根据用户的概 要文件进行分析，就忽略了同类身份用户的不同喜好，所以用户的满意程度低 ( 2 ) 基于规则的个性化( r u l e s - b a s e d ) 基于规则的个性化技术被用于显示根据事先定义好的规则产生出来的内容 这些规则可以由网站管理员制定，也可以由业务管理器定义虽然基于规则的个 性化能够一定程度上满足同类用户的不同喜好，但是由于规则的定义由管理员或 业务管理器来负责，所以用户满意程度较低，而且容易过时 ( 3 ) 协同过滤( c o l a b o r a t i r ef i l t e r i n g - b a s e d ) 2 华东师范大学硬士学位论文 协同过滤技术包括k n n 技术( k - n e a r e s tn e i g h b o r ) ，基于聚类( c l u s t e r - b a s e d ) 的协f 司过滤和基于项目( i t e m - b a s e d ) 的协同过滤三种协同过滤技术。基于协同过 滤的个性化技术相比前两种技术能够为用户提供更加满意的服务但是它不仅需 要用户主观提供评价信息，而且还需要处理大规模的包含用户兴趣模式的稀疏数 据，所以具体实现起来的难度会很大。推荐准确率也不是很高 ( 4 ) 数据挖掘( d a t am i n i n g ) 数据挖掘中用于个性化推荐的技术包括关联规则发现( a s s o c i a t i o nr u l e ) ， 序列模式发现( s e q u e n c ep a t t e r n ) 和分类( c l a s s f i c a t i o n ) 预测等数据挖掘技 术相对协同过滤技术来说实现上比较容易，而且因为采用的是精确的访闯模式匹 配。所以推荐准确率比较高 当前在基于w e b 使用挖掘的个性化推荐服务这个领域，国外的许多大学和 研究机构都对此展开了研究，也开发出了一些具有代表性的原型系统，比较有 代表性的有： ( 1 ) w e bw a t c h e r 系统 7 1 w e bw a t c h e r 是由美国卡奈基梅隆大学研制的一个w e b 测览向导智能体 它的执行策略是跟踪用户浏览w e b 站点的行为或访问路径，学习用户的访问模 式，将用户可能感兴趣的w e b 链接信息在线推荐给用户 ( 2 ) s i t e h e l p e r 系统 s i s i t e h e l p c r 是w u 等人构造的基于w e b 使用挖掘实现网站个性化服务的系 统它分析每一个用户已经访问的w e b 页，学习用户的兴趣模式，从用户感兴 趣的w e b 中提取关键词，然后提供给用户 ( 3 ) w e bl o g v 虹i l c r 系统 5 1 w e bl o gs i n e r 是加拿大s i m o nf r a s e r 大学的h a r t 等人开发的针对w e b 日 志文件的知识发现工具它将知识发现总共分为四个阶段：第一阶段根据w e b 服务器日志文件构建数据库；第二阶段构造多维w e b 日志数据立方体；第三阶 段根据数据立方体进行联机分析处理：第四阶段进行知识发现与应用 国内的学者在基于w e b 使用挖掘的个性化服务方面主要侧重于理论研究， 比较突出的有唧： 沈均毅 9 1 等人提出以w e b 站点的u r l 为行，以u s e r i d 为列，建立i 球i 产 u s e r i d 关联矩阵，元素值为用户的访问次数然后，对列向量进行相似性分析 得到相似客户群体，对行向量进行相似性分析获得相关w e b 页面，对相关页面 再做进一步处理，则可以发现频繁访问路径，并提出了w e b 页面和用户群体的 模糊聚类算法 陆丽娜【l o j 等人采用基于事务的方法，研究w e b 使用挖掘预处理及用户访问 华东师范大学硕士学位论文 序列模式挖掘方法，提出了一种基于扩展有向树模型进行用户浏览模式识别的 w e b 日志挖掘方法 王型1 1 】等人采用w e b 站点的访问日志进行事务识别后。根据群体用户对 w e b 站点的访问顺序进行路径聚类，最终每一个聚类集就反映出该聚类集中的 全体用户的访问兴趣，为了得到这种根据用户访问兴趣而对用户的划分，提出 了k - p a t h 路径聚类方法 周斌【1 2 】等人提出基于o e m 模型，综合考虑服务器的应用逻辑设计、页面 拓扑结构及用户浏览路径等多个数据源的用户访问模式及电子商务中潜在顾客 群的挖掘算法 1 3 本文所做的主要工作 本文首先介绍了w e b 使用挖掘的基础知识、过程和应用范围，然后对基于 w e b 使用挖掘和关联规则的页面推荐模型p r w a r 及其相关算法和技术进行了 研究p r w a r 贯穿了w e b 使用挖掘过程中的数据预处理、模式发现和模式分 析与应用三个阶段它一般分为离线部分和在线部分。离线部分的处理流程是： 先对w e b 日志数据进行数据预处理，然后进行模式发现来获得频繁访问模式 在线部分的处理流程是：在线获得用户访问序列后对其进行某种处理；然后基 于频繁访问模式获得关联规则；最后对关联规则进行选择，把得到的规则集中 的后项加入页面推荐集合本文围绕邢1 w a r 所做的主要工作如下： ( 1 ) 引入了一种用于用户事务识别的m f i 算法。用户事务是对用户会话进行 语义分组后得到的页面序列，它对进一步发现用户的频繁访闯模式起着重要作 用。而m f p 算法是进行事务识别的有效算法 ( 2 ) 提出了一种用于频繁访问模式挖掘的s d h p 算法s d h p 算法基于 a p r i o r i a i l 算法和d h p 算法的思想提出d h p 算法挖掘的数据是无序的，而 s d h p 算法和a p r i o r i a i l 算法挖掘的数据是有序的s d h p 算法使用了a p r i o r i a l l 算法中对事务进行连接时采用的方法，借鉴了d h p 算法中的h a s h 技术和修剪 技术来对事务数据进行处理实验表明：s d 肿算法利用h a s h 技术能够大量减 少候选项集的生成，利用修剪技术能够有效地压缩事务数据库的规模，所以它 相比a p r i o r 础算法可以减少扫描数据库的时间，从而提高了算法的执行效率 ( 3 慢出了一种利用事务划分进行页面推荐的方法t p m t p m 是对用户访 问序列运用m f p 算法进行事务识别后再进行页面推荐，而常见的利用滑动窗口 进行页面推荐的方法s w m 是利用滑动窗口得到子序列后再进行页面推荐。 四m 相比s w m 对用户访问序列的处理更加灵活，也考虑到了浏览器缓存对用 户访问序列的影响实验表明：t p m 相比s w m 得到的推荐结果更加全面和更 华东师范大学硕士学位论文 加准确，即t p m 相比s w m 的推荐效果要好 ( 4 ) 提出了一种基于事务划分的页面推荐模型p r b t 它是以本文提出的 s d h p 算法和t p m 为基础，而常见的基于滑动窗口的页面推荐模型p r b s w 是 以a p r i o r i a l l 算法和s w m 为基础。p r b t 和p r b s w 都属于p r w a r ( 5 ) 基于n e t 平台设计和实现了一个页面推荐原型系统p r p s 它贯穿了 w e b 使用挖掘的整个过程，模拟实现了p i m t 和p r b s w 两种推荐模型p r p s 由五大功能模块组成，分别是：用户交互模块、数据准备模块、会话和事务构 造模块、频繁访问模式挖掘模块和页面推荐模拟模块。p r p s 对p r b t 和p r b s w 中涉及的相关算法和技术用a 语言进行了实现在p r p s 上对这两种模型进行 实验表明：p r b t 相比p r b s w 在离线处理部分的执行效率要高，在页面推荐 的效果上要好，即p r b t 的综合性能优于p r b s w 的综合性能。 1 4 本文的组织结构 全文共分为七章，各章的内容具体安捧如下： 第一章简要介绍了论文研究课题的背景、意义和现状，i ；i 及论文的研究内 容和组织结构 第二章阐述了从数据挖掘、w e b 挖掘到w e b 使用挖掘的整个过程，重点 介绍了w e b 使用挖掘的基础知识、过程和应用范围 第三章讨论了w e b 使用挖掘的数据预处理阶段中各个步骤的常用算法， 并给出了本文实现的页面推荐原型系统中数据预处理阶段各个步骤所用算法的 描述，尤其是重点描述了事务识别步骤中的m f i 算法。 第四章介绍了关联规则挖掘中用于频繁项集发现的a p r i o r i 算法和d h p 算 法，讨论了进行频繁访问模式挖掘时常用的a p r i o r i a u 算法的执行过程和特点， 然后提出了一种甩于频繁访问模式挖掘的算法s d h p 算法，同时对d h p 算 法、s d h p 算法和a p r i o f i a l l 算法的优缺点进行了比较。 第五章首先介绍了关联规则的获取和选择的策略，接着介绍了目前常见的 基于w e b 使用挖掘和关联规则的页面推荐模型 r w a r 卜基于滑动窗1 ：3 的 页面推荐模型( p r b s v 0 ；紧接着提出了一种利用事务划分进行页面推荐的方法 t p m ；然后以本文已提出的s d h p 算法和t i m 为基础。提出了基于事务划分 的页面推荐模型( p 啪，并且详细介绍了p r b t 的离线处理和在线处理两大部 分的执行流程和各阶段所用到的算法和技术，同时还对离线处理部分和在线处 理部分的特点进行了比较；最后对p r b t 和p r b s w 两种模型的异同点进行了 比较和分析 第六章以p r b t 和p r b s w 中涉及的相关算法和技术为基础，基于n e t 5 华东师范大学硕士学位论文 平台设计和实现了一个页面推荐原型系统( p r p s ) p r p s 的设计贯穿了w e b 使 用挖掘过程中的数据预处理、模式发现和模式分析与应用三个阶段，五六大功 能模块组成，分别是：用户交互模块、数据准备模块、会话和事务构造模块、 频繁访问模式挖掘模块和页面推荐模拟模块频繁访问模式挖掘模块分别实现 了a p r i o r i a u 算法和本文提出的s d h p 算法；页面推荐模拟模块模拟实现了 p r b t 和p r b s w 两种推荐模型最后利用实验数据对这两种模型的综合性能 进行了分析和比较 第七章对论文所做的工作进行了总结，并展望了进一步的研究工作 b 华东师范大学硕士学位论文 第二章从数据挖掘到w e b 使用挖掘 2 1 数据挖掘概述 2 1 1 数据挖掘产生的背景 随着数据库技术的不断发展以及数据库管理系统的广泛应用，人们积累的 数据越来越多，两在这些激增的数据背后一般都隐藏着许多重要的信息。人们 为了获得隐藏在这些数据背后的信息，对数据库的应用就已经不满足于简单的 查询和检索，而是希望能够对其进行更高层次的分析目前的数据库系统可以 高效地实现数据的录入、查询、统计等功能，但无法发现数据中存在的关系和 规则，无法根据现有的数据预测未来的发展趋势，无法挖掘数据背后隐藏的知 识。信息量的快速膨胀，使得淹没在数据海洋中的人们常常会因为寻找不到有 用的信息而困惑不已所以如何从。数据丰富而信息贫乏【”1 ( d a 扭r i c ha n d i n f o r m a t i o np o o r ) 的窘境中解脱这一闽题，引起全世界相关领域专家学者们的 广泛重视在这样的背景下，数据挖掘技术应运而生 数据挖掘是数据库技术和机器学习结合的产物，它在学术领域的另一种称 谓是数据库中的知识发现1 9 8 9 年在美国底特律市召开的第1 1 届国际人工智 能会议上首次出现数据库中的知识发现( 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 ) i 盆- - 专业名词，简称k d d 目前公认的k d d 的严格定义是在1 9 9 6 年召开的知识 发现国际会议上由f a y y a d , p i a t e s t s k y , s h a p i r o 和s m y t h 提出：数据库中的知识 发现l 捌是从数据集中提取出有效的、新颖的、有潜在作用的、可信的，并能最 终可被理解的模式的非平凡过程 数据挖掘是从大型数据库或数据仓库中发现并提取隐藏在其中的信息的一 种技术，它不仅能对存储在数据库中的数据进行查询和遍历，而且能够找出数 据之间的潜在联系，从而帮助决策者获得数据间潜在的关联信息，发现被忽略 的知识数据挖掘引起了信息产业界的极大关注，其主要原因是企业已经保存 了大量数据。并且追切需要将这些数据转换成有用的信息和知识通过数据挖 掘获取的信息和知识可以广泛应用于各种领域，包括商务管理、生产控制、市 场分析、工程设计和科学探索等数据挖掘技术的出现是人们长期对数据库技 术进行研究和开发的结果，它使得数据库技术进入了一个更高级的阶段 7 华东师范大学硕士学位论文 2 1 2 数据挖掘的概念和过程 数据挖掘( d a t am i n i n g ) 【1 4 】是从大量的、不完全的、有噪声的、模糊的和随 机的数据集中提取有效的、新颖的、潜在有用的以及最终可理解的模式的非平 凡过程。它是一门涉及面很广的交叉学科，包括机器学习、数理统计、神经网 络、数据库、模式识别、粗糙集和模糊数学等相关技术 在上面的定义中，涉及几个需要进一步解释的概念：“数据集”、“模式”、 “过程”、“有效性”、。新颖性”、“潜在有用性”和“最终可理解性” 。数据集”是一组事实f ( 如关系数据库中的记录) “模式”是一个用语言l 来表示的一个表达式b ，它可用来描述数据集f 的某个子集“过程”是指在 数据挖掘中通常指多个环节，涉及数据准备、模式搜索、知识评价，以及反复 修改求精。该过程要求是“非平凡的”，意思是要有一定程度的智能性和自动 性( 仅仅给出所有数据的总和不能算作是一个发现过程) “有效性”是指发现 的模式对于新的数据仍保持有一定的可信度“新颖性”是要求发现的模式应 该是新的“潜在有用性”是指发现的知识将来有实际效用，如用于决策支持 系统里可提高经济效益“最终可理解性”是要求发现的模式能被用户理解， 目前它主要是体现在简洁性上有效性、新颖性、潜在有用性和最终可理解性 综合在一起可称之为，兴趣性” 数据挖掘的过程【1 4 1 可分为三步：数据准备( d a t ap r e p a r a t i o n ) 、模式挖掘 ( m i l l i n g ) 和结果的解释评估( i n t e r p r e t a t i o na n de v a l u a t i o n ) 数据准备又可以分为 三个子步骤：数据采集( d a t as e l e c t i o n ) 、数据预处理( d a t ap r e p r o c e s s i n g ) 和数据 变换( d a t a t r a n s f o r m a t i o n ) 数据采集的目标是确定挖掘任务的操作对象，即目 标数据( t a r g e td a t a ) ，它一般是根据用户的需要从原始数据库中抽取的一组相关 数据数据预处理一般包括消除噪声数据、推导计算缺值的数据、消除重复记 录以及完成数据类型转换( 如把离散型数据转换为连续型数据) 等数据变换的 主要目的是降低数据维数( d i m e n s i o nr e d u c t i o n ) ，即从初始特征中找出真正有用 的特征以减少数据挖掘时要考虑的特征或变量个数 模式挖掘阶段首先要确定挖掘的任务是什么，如数据分类、聚类、关联规 则、序列模式和预测等确定了挖掘任务后。就要决定使用什么样的挖掘算法 同样的任务可以用不同的算法来实现，选择挖掘算法有两个考虑的因素：一是 不同的数据有不同的特点；二是用户或实际运行系统的要求 完成了上述准备工作后，就可以实施数据挖掘操作了。数据挖掘算法是 k d d 的核心，要获得好的挖掘效果，必须对各种挖掘算法的要求或假设有充分 的理解。 8 华东师范大学硕士学位论文 数据挖掘阶段得到的模式最后要进行结果的解释评估，经过用户或机器的 评估，可能存在冗余或无关的模式，这时需要将其剔除；也有可能模式不能满 足用户的要求，这时则需要整个挖掘工作退回到前面的阶段。另外，挖掘结果 由于最终是面向用户的，因此可能要对发现的模式可视化，或者把结果转换为 用户易懂的另一种表示形式 2 1 3 数据挖掘的主要技术 数据挖掘的核心技术已经经过了多年的发展，今天这些成熟的技术加上高 性能的关系数据库引擎以及广泛的数据集成，让数据挖掘技术在当前的数据仓 库环境中进入了实用的阶段1 1 5 l 。总体来说，数据挖掘利用的技术越多，得出的 结果精确性就越高原因很简单，对于某一种技术不适用的问题，用其它方法 就可能奏效，当然这主要取决于问题的类型以及数据的类型和规模。数据挖掘 技术的分类方法有多种，其中比较典型的技术分为如下六类l 瑚： ( 1 ) 概念类描述。就是对某类对象的内涵进行描述，并概括这类对象的有关 特征。概念描述分为特征性描述和区另 i 性描述，前者描述某类对象的共同特征， 后者描述不同类别对象之间的区别生成一个类的特征性描述只涉及该类对象 中所有对象的共性 ( 2 ) 关联分析数据关联是数据库中存在的一类重要的可被发现的知识若 两个或多个变量的取值之间存在某种规律性，就称为关联关联可分为简单关 联、时序关联，因果关联关联分析的目的是找出数据库中隐藏的关联信息 有时并不知道数据库中数据的关联信息，或者即使知道也是不确定的，因此关 联分析生成的规则应带有可信度标识 ( 3 汾类和预测。分类是指找出描述并区分数据类或概念的模型，以便能够 使用模型预测类标记未知的对象类分类要解决的问题是为一个事件或对象归 类。在使用上，既可以用此模型分析己有的数据，也可以用它来预测未来的数 据 ( 4 ) 聚类分析数据库中的记录可被划分为一系列有意义的子集，即聚类 聚类增强了人们对客观事实的认识，是概念描述和偏差分析的先决条件 ( 5 ) 孤立点分析数据库中可能包含一些数据对象，它们与数据的一般行为 或模型不一致这些数据对象是孤立点大部分数据挖掘方法将孤立点视为噪 声或异常而丢弃然而，在一些应用中( 如欺骗检测) ，罕见的事件可能比正常 数据更为有用。对这些数据的分析称为孤立点分析。 ( 6 ) 演变分析演变分析描述了行为随时间变化的对象的规律或趋势，并对 其建立模型分析这些趋势根据这些分析模型的不同特点分为时间序列数据分 9 华东师范大学硕士学位论文 析、序列或周期模式匹配的数据分析等类型 2 2 w e b 挖掘概述 随着w e b 技术的迅猛发展，i n t e r n e t 早已经成为了信息发布和交流的全球性 媒体，它的内容涵盖了包括科研、教育、商业、金融、军事等各个领域正是 由于w e b 上包含巨大的信息量使得越来越多的用户感觉到在w e b 上寻找自己 想要的信息犹如大海捞针一样困难。研究表明；9 9 的w e b 信息相对9 9 的用 户来说都是无用的【坷用户关心的一般只是w e b 信息中极少的一部分，但是大 量的无关信息会干扰甚至淹没用户感兴趣的内容所以如何快速、准确且高效 地从浩瀚的w e b 信息资源中搜寻和发现用户感兴趣的信息和知识已经成为一 个迫切需要解决的问题，而将传统的数据挖掘技术与w e b 有机地结合在一起， 进行w e b 挖掘是解决这个问题的有效途径 2 2 1w e b 挖掘基本概念和分类 w e b 挖掘【1 7 l 是将数据挖掘技术应用于大规模w e b 数据，用以发现有效的、 新颖的、潜在有用的以及最终可理解的模式和规则的过程w e b 挖掘可以在很 多方面发挥作用，如对搜索引擎的结构进行挖掘、确定权威w e b 页面、w 岛 文档分类、w e bl o g 挖掘和智能查询等领域 w c b 挖掘虽然是从数据挖掘发展而来，但是w e b 挖掘与传统的数据挖掘相 比有许多独特之处【1 刀。首先，w c b 挖掘的对象是海量的、异构的、分布的w e b 文档和w e b 服务器日志，因此从挖掘的数据源来说已经不属于传统的数据挖掘 的范畴。其次，w c b 在逻辑上是一个由文档节点和超链接构成的图，因此w e b 本身是半结构化或无结构的，且缺乏机器可理解的语义；而数据挖掘的对象局 限于数据库中的结构化数据，并利用关系表格等存储结构来挖掘知识，因此有 些数据挖掘技术并不适合于w e b 挖掘，即使可用也需要建立在对w e b 信息进 行预处理的基础之上 w e b 挖掘的研究是一个具有挑战性的课题，它的挖掘对象包括w 曲站点文 件内容、结构以及站点日志记录按照处理对象的不同，w e b 挖掘一般可以分 为三类1 1 e 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 e m _ i n i n g ) 、w e b 使用挖掘( w e bu s a g er c n i n g ) 1 0 华东师范大学硕士学位论文 2 2 2w e b 内容挖掘 w e b 内容挖掘【1 9 l 是从文档内容或其描述中抽取知识的过程它主要分为两 类：对文本文档( 包括t e x t ，阳晒几等格式) 和对多媒体文档( 包括i m a g e ，a u d i o ， v i d e o 等媒体类型) 的挖掘。w e b 内容挖掘可以对w e b 上大量文档集合的内容进 行摘要、分类、聚类、关联分析，以及利用w e b 文档进行趋势预测等 文本摘型1 9 】是指从文档中抽取关键信息，用简洁的形式对文档内容进行摘 要或解释。这样，用户不需要浏览全文就可以了解文档或文档集合的总体内容 文本摘要在有些场合很有用，例如，搜索引擎在向用户返回查询结果时，通常 需要给出文档的摘要目前，绝大部分搜索引擎采用的方法是简单的截取文档 的前几行。 文本分类【1 9 1 是指按照预先定义好的主题类别，为文档集合中的每个文档确 定一个类别这样，用户不但能够方便地浏览文档，而且可以通过限制搜索范 围来使文档的查找更为容易。目前，y a h o o 通过文本分类来对w c b 上的文档进 行分类，这大大影响了索引的页面数f l ( y a h o o 搜索引擎索引的覆盖范围远远小 于a l t a v i s t a 等搜索引擎) 利用文本分类技术可以对大量文档进行快速、有效 的自动分类 文本聚类与分类的不同之处在于【蛳：聚类没有预先定义好主题类别，它的 目标是将文档集分成若干类，要求同一文档内文档内容的相似度尽可能大，而 不同类别间的相似度尽可能地小h e a r s t 等人研究已经证明了“聚类假设”， 即与用户查询相关的文档通常会聚类的比较靠近，而远离与用户查询不相关