（计算机应用技术专业论文）基于web挖掘的个性化技术研究.pdf

摘要 摘要 随着网络技术的发展及机器学习、模式识别、数据挖掘等新技术的出 现，电子商务竞争已使得信息服务方式从传统的“一对多”发展到“一对 一”的个性化用户服务方式，即为恰当的用户在恰当的时间方便快捷提供 恰当的信息。而利用w e b 挖掘技术已经成为个性化服务的个研究热点。 目前，已经有很多基于w e b 挖掘的个性化算法被研究和使用，但在准确性、 方便性尤其在实用性方面，这些算法尚不能满足人们的要求。本文在对国 内外研究现状进行综合分析的基础上，对基于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 w i t ht h ed e v e l o p m e n to fn e t w o r k t e c h n o l o g ya n da p p e a r a n c eo f m a c h i n e s t u d y , m o d e lr e c o g n i t i o n , d a t am i n i n ga n do t h e rn e wt e c h n o l o g y , e l e c t r o n i c b u s i n e s sc o m p e t i t i o nh a sd e v e l o p e di n f o r m a t i o ns e r v i c es t y l ef r o mt r a d i t i o n a l “o n et om u l t i p l e ”t o “o n et oo n e p e r s o n a l i z a t i o nc u s t o m e rs e r v i c es t y l e a n d u t i l i z i n gw e bm i n i n gt e c h n o l o g yh a sb e c o m ea h o tp o i n t n o w , p e r s o n a l i z a t i o n a r i t h m e t i cb a s e do nw e bm i n i n gh a sb e e ns t u d i e d ，b u tt h ea r i t h m e t i cc s l q - tb e s a t i s f i e dw i t ht h ep e o p l e sd e m a n d sf o rt h ea c c u r a c y , c o n v e n i e n c ee s p e c i a l l y t h ep r a c t i c e b a s e do nt h es y n t h e t i c a l a n a l y s i s o ft h e s t u d yo fw e bm i n i n g p e r s o n a l i z a t i o ns e r v i c ea th o m e a n da b r o a d ，t h ep a p e rh a sm a d e s t u d yd e e p l y f i r s t ，a c c o r d i n gt o t h ec a t e g o r i e so fw e bm i n i n g ，t h ep a p e rr e l e v a n t l y d i v i d e dw e bm i n i n gp e r s o n a l i z a t i o ns e r v i c ei n t ot h r e ek i n d sa n di n t r o d u c e d t h e m ；p u tf o r w a r dt h es y s t e m a t i c s t r u c t u r eo fw e bm i n i n gp e r s o n a l i z a t i o n s e r v i c ea n di n t r o d u c e dt h ew o r k i n g p r o c e d u r eo f t h es y s t e m a te v e r ys t a g e s e c o n d ，t h es e s s i o nc l u s t e r i n ga r i t h m e t i cw a si n t r o d u c e da n di t sm e r i t s a n dd e m e r r sw e r ea n a l y s e d t i m ed i s c r e t i z a t i o na n df u z z yd i v i d et e c h n o l o g y w e r e a d o p t e d t oi m p r o v et h i sa l g o r i t h m t h i r d ，p e r s o n a l i z a t i o n r e l a t e dr e g u l a ra r i t h m e t i cw a ss t u d i e da n d a n a l y s e d f o rt h ee x i s t i n gp r o b l e m - t h er a t eo fr e c o m m e n d c o v e r a g ew a sl o w , t h em e t h o d o f r e l a t e dr e g u l a ra n d c l u s t e r i n gm u t u a lr e p l e n i s h m e n t w e r er a i s e d f i n a l l y , b ye x p e r i m e n t a l , t h a tt h ei m p r o v e da r i t h m e t i cw a ss u p e r i o r t ot h e o r i g i n a lo n ei np e r f o r m a n c eh a sb e e np r o v e d t h ea d v a n t a g e so f w e b m i n i n g p e r s o n a l i z a t i o n s e r v i c ew e r es u m m e du pa n dt h e e x i s t i n gp r o b l e m w a s a n a l y s e da n d t h eo r i e n t a t i o na n de x p e r i e n c ew e r e p r o v i d e df o rf u r t h e rs t u d y k e y w o r d sp e r s o n a l i z a t i o n ；d a t am i n i n g ；w e bm i n i n g ；a s s o c i a t i o nr u l e ； c l u s t e r i n g 第1 章绪论 1 1 研究背景 第1 章绪论 随着人类步入二十一世纪，信息需求快速增长，因特网成为信息传播、 交流与共享的主要媒体，其规模正以惊人的速度发展。全球w e b 站点数目 迅速增长，而在数量增多的同时，网站的规模也日益扩大，各个w e b 站点 的信息量及其复杂度也迅速上升，从而直接导致用户寻找信息的困难。因 此，迫切要求信息服务方式从传统的“一对多”发展到“一对一”的个性 化用户服务方式，即网站尽可能自动调整以迎合每个用户的浏览兴趣，自 动实时的为用户提供推荐页面，迅速的为用户提供所需的服务，从而让每 个用户能够感觉到他是网站的唯一用户【l 】。个性化服务的主要表现形式有： 推荐的广告列表、推荐的商品列表( 电子商务) 、推荐的超链接列表、经裁 剪的文本或图像列表。使用个性化服务可以方便用户查询和浏览、增强广 告的作用、促进网上销售、提高用户忠诚度，因此个性化服务已发展为 w 西服务较常见而且也是较流行的形式之一。 传统的个性化服务技术一般分为三类：第一类是企业w e b 站点管理员 根据用户统计数、静态个性文件或用户会话( u s e rs e s s i o n ) 记录制定一系列 规则并利用这些规则为特定用户提供特定服务；第二类是基于内容的过滤 系统( c o n t e n t b a s e df i l t e r i n g ) ，通过用户历史访问内容挖掘用户访问模式并 将该模式需求同u r l 结合以满足用户个性化需求；第三类是协同过滤系统 f c o l l a b o r a t i v ef i l t e r i n g ) ，通过用户群的相似性进行内容推荐，协同过滤技 术应用的很广泛 2 】。而基于w e b 挖掘的个性化服务采用w e b 挖掘技术，具 有不需要用户提供主观的评价信息、可以处理大规模的数据量、用户访问 模式动态获取、不会过时和使用方便等优点，因此利用w e b 挖掘技术已经 成为个性化服务的一个研究热点。 本文的研究就是在这一背景下提出的。目前基于w e b 挖掘的个性化服 燕山大学工学硕士学位论文 务已经成为电子商务网站个性化发展的最终方向。对于基于w e b 挖掘个性 化的深入研究将有力的促进电子商务网站以及信息技术的发展，因此具有 巨大的应用前景和经济效益。 1 1 1w e b 挖掘技术 随着i n t e r n e t 的飞速发展，网上的数据资源空前丰富。但是数据资源 中蕴涵的知识却至今未能得到充分的挖掘和利用，数据丰富而知识贫乏的 问题非常严重。数据挖掘( d a t am i n i n g ) 技术的出现和发展为解决这个问题 带来了一线曙光。数据挖掘是近年来数据库研究、开发和应用最活跃的分 支之一，简单地说，数据挖掘是从大量的数据中提取或“挖掘”知识【3 】。 将数据挖掘和w e b 结合起来就产生了w e b 挖掘( w e b m i n i n g ) 这一热门的研 究方向。w e b 挖掘就是利用数据挖掘技术从w e b 文档和w e b 活动中发现 和抽取人们感兴趣的、潜在的有用模式和隐藏的信息。 然而基于以下的分析，对w 曲的有效资源和知识发现还是具有极大的 挑战性3 q ( 1 ) 对有效的数据仓库和数据挖掘而言w e b 过于庞大w e b 的数据量 目前以几百兆兆字节计算，而且仍然在迅速的增长。这使得几乎不可能去 构造一个数据仓库来复制、存储或集成w e b 上的所有数据。 ( 2 ) 网页的复杂性远比任何传统的文本文档复杂得多网页缺乏统一 的结构，它包含了远比任何一组书籍或者其他文本文档多得多的风格和内 容。 ( 3 ) w e b 是一个动态性极强的信息源w e b 不仅以极快的速度增长，而 且其信息还在不断地发生着更新。新闻、股票市场、公司广告和w e b 服务 中心都在不断地更新着各自的页面。链接信息和访问记录也在频繁地更新 之中。 ( 4 ) w e b 面对的是一个广泛的形形色色的用户群体 目前因特网上连 接有约五千万台工作站，其用户群仍在不断地扩展当中。各个用户可以有 不同的背景、兴趣和使用目的。大部分用户不了解信息网络结构，不清楚 2 第1 苹绪论 搜索的高昂代价，极易在网络中迷失方向，也极容易在访问中烦乱不已和 在等待中失去耐心。 ( 5 ) w e b 上的信息只有很小的部分是相关的或有用的一个用户只 是关心w e b 上的很小很小一部分信息，w e b 所包含的其余信息对用户来说 是很不感兴趣的，而且会淹没所希望得到的搜速结果。 由上面的所述，w 曲挖掘是一个极具挑战性的课题，它实现对w e b 存 取模式、w e b 结构和规则，以及动态的w e b 内容的查找。一般地，w e b 挖掘一般可以分为三大类 5 j ：w e b 内容挖掘( w e bc o n t e n tm i n i n g ) 、w e b 使用挖掘( w e b u s a g e m 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 内容挖掘的一部分。 w e b 挖掘的大部分技术来源于数据挖掘领域、数据库营销和信息检索 领域。应用研究主要使用关联规则、聚类、时序序列、预测建模和路径分 析等，其中路径分析方法学是针对w e b 数据挖掘专门设计的。 1 1 2 个性化 个性，英文一词为“p e r s o n a l i t y ”，在个性心理学上定义为：人类个性 以其遗传学素质为基础，在与环境相互作用的过程中，由各种心理倾向与 特质的有机结合而形成的稳定的心理动力组织，决定着个人的独特行为方 式。简言之，个性是具有一定倾向性的各种心理品质的总和。个性倾向性 主要包括个人的需要、兴趣、动机、信念等不同层次的基本成分。 个性化是指使事务具有某种属性或某种趋势，因而，个性化的含义是 使事物具有个性，或使其个性凸显。个性是需要经过培养而逐步形成的， 这个过程称为使个体个性化的一个过程，其在一定的空间中得以体现、展 示，是每个个体都拥有的潜在需求，这个过程称为个性化的过程。 在个性化信息服务中个性化被定义为：个性化是通过构建一对一的牢 固信任关系来建立服务商对客户的忠诚。通常，要使顾客满意，就必须了 解每一个个体的需求，并对这些需求给出清晰的定义；其服务内容要设计 成有用且能够用，同时，又体现出个人的倾向。个性化服务应该遵循如下 3 燕山大学工学硕士学位论文 的原则： ( 1 ) 以最低的费用提供用户真正需要的、可使用的优质产品或服务； f 2 ) 为用户提供完整的优质服务。 那什么是个性化信息呢? 这可以从两个角度进行分析。第一，个性化 信息是指反映人类个性特性的一切信息，这些信息包括了这个个体的各种 属性的描述；第二，个性化信息是指出人类个性特性所决定的、对其信息 需求的一种信息组合，也就是由人类个性对信息需求的决定关系而产生的 一系列对个体有用的信息。 对于个性化信息服务，它即是一种个性化服务，又是一种信息服务。 因此，可以根据前述的两种个性化的过程和两类个性化信息，找到个性化 信息服务的定位。个性化信息服务首先应该是能够满足用户的个体信息需 求的一种服务，即根据用户提出的明确需求提供信息服务，或通过对用户 个性、使用习惯的分析而主动地向用户提供其可能需要的信息服务。其次， 个性化信息服务也应该是一种培养个性，发现个性，引导需求的服务。 无论是哪一种个性化模式，关键是了解用户的个性特征。与用户的交 互保持友善，并且经常问用户一些简单的问题，记录下用户的行为习惯， 以进一步收集信息，改善个性化的可视性。应当指出，个性化并不局限于 因特网，个性化也不要求一种服务或产品能够识别每一个用户或顾客。随 着信息处理技术的不断进步，个性化信息服务将广泛应用于人们工作、生 活的各个领域，尤其在张扬个性，倡导创造性的现代信息社会，个性化信 息服务更是倍受人们的关注和青睐。 1 1 3 基于w e b 挖掘的个性化服务 由于基于w e b 挖掘的个性化服务采用w e b 挖掘技术，与传统的个性 化服务技术相比具有不需要用户提供主观的评价信息、可以处理大规模的 数据量、用户访问模式动态获取、不会过时和使用方便等优点，因此可以 为用户提供完全自动的个性化服务。我们将基于w e b 挖掘的个性化服务按 照w e b 挖掘技术分为三类 7 1 ：基于w e b 使用挖掘、基于w e b 内容挖掘、 4 第1 章绪论 基于w e b 结构挖掘的个性化服务。 ( 1 ) 基于w e b 使用挖掘的个性化服务基于w e b 使用挖掘的个性化服 务就是分析w e b 日志数据和相关数据，利用数据挖掘方法发现用户的使用 模式，从而向用户提供个性化服务口j 。w e b 上每一个提供信息资源的服务 器上都有一个结构比较好的记录集，即w e b 访问日志。服务器日志文件经 常是以扩展的普通日志文件形式来提供信息的，w e b 同志文件中包含i p ( 主 机地址) 、时间戳( 日期时间) 、返回码、传送的字节数、方法、u r l 、h t t p 、 引用页u r l 和浏览器类型等。对于基于w e b 的电子商务服务器，保存了 大量的w e b 访问日志记录，这些日志记录提供了有关w e b 动态的丰富信 息，可以通过这些日志文件对用户的访问行为、频度、内容等进行分析， 得到关于用户的行为和方式模式。每当有获取资源的请求到来时，w e b 服 务器都将记录和积累这些关于用户交互作用的数据。分析不同的w e b 站点 和w 曲访问日志可帮助人们理解用户行为和w 如的结构，从而为用户提 供个性化的服务。w e b 使用挖掘一般分为两种：一般访问模式跟踪和定制 使用跟踪。一般访问模式跟踪通过分析w 曲日志来理解用户的访问模式和 倾向，以给出较好的w e b 结构及资源提供者的分组情况；定制使用跟踪则 分析单个用户的偏好，根据其访问模式为每个用户定制符合其个人特色的 w 曲站点服务。 ( 2 ) 基于w e b 内容挖掘的个性化服务用户对于w e b 站点页面内容的 关注是显而易见的，因此，人们提出基于w 曲内容挖掘的个性化服务技术。 w e b 内容挖掘是从w e b 资源中发现信息或知识的过程，在创建个性化服务 系统时，人们通常应用w 曲内容挖掘对网页内容进行分析，其中网页的自 动分类技术在搜索引擎、数字化图书馆等领域得到了广泛的应用。根据实 现方法的不同可以分成基于代理的方法和数据库方法。w e b 内容挖掘由于 直接处理数据对象的内容，因此得到的结果一般比较精确，在个性化系统 中得到较广泛的应用。w e b 内容挖掘研究和挖掘的数据既有文本数据，也 有图像、声频、音频等多媒体数据，既有来自于数据库的结构化数据，也 有用标记的半结构化数据和无结构的自由文本。对无结构的自由文本的挖 掘称之为文本的知识发现，对多媒体文档的挖掘称之为多媒体数据挖掘。 燕山大学工学硕士学位论文 ( 3 ) 基于w e b 结构挖掘的个性化服务w e b 结构包括页面内部的结构 以及页面之间的结构。w e b 的组织结构、w e b 文档结构及其链接关系中蕴 藏着大量潜在的、有价值的信。g ，w e b 结构挖掘是从w e b 的组织结构、 w 曲的文档结构及其链接关系中推导知识f 9 。由于w e b 文档之间的关联关 系使得w e b 不仅可以揭示w e b 文档所包含的信息，也揭示了文档间的关 联关系所代表的信息，反映了文档之间的某种联系，同时能体现某个页面 的重要程度。因此，利用w e b 结构挖掘技术是提高性化服务质量的一个重 要途径。通过挖掘w e b 结构信息，对于导航用户浏览行为、改进站点设计、 评价页面的重要性等都非常重要。p a g e r a n k 算法和c l e v e r 算法利用w e b 页面之间的链接信息来查找“权威”f a u t h o r r i e 网页和“集线器”( h u b s ) 。 w e b 结构挖掘通常需要整个w e b 的全局数据，因此在个性化搜索引擎或主 题搜索引擎研究领域得到广泛的应用。 1 2 国内外研究现状 1 9 9 5 年3 月，卡内基梅隆大学的r o b e r t a r m s t r o n g 等人在美国人工智 能协会( a a a i ) 春季会议上提出了个性化导航系统w e b w a t c h e r ，美国斯坦 福大学的m a r k ob a l a b a n o v i c 等人在同一次会议上推出了个性化推荐系统 u r a 。同年8 月，麻省理工学院的h e n r yl i e b e r m a n 在国际人工智能联合 大会( i j c a i ) 上提出了个性化导航智能体l e t i z i a 。这三个系统被公认为个性 化服务发展初期最为经典的系统，标志着个性化服务的开始【9 】。 在此后的几年中，个性化服务系统层出不穷。1 9 9 6 年，加州大学i r v i n e 分校的b r i a ns t a r r 等人提出了发现用户感兴趣页面有价值变化、进而通知 用户访问的个性化服务智能体d o i c a r e ；同年，卡内基梅隆大学的d u n j a m l a d e n i e 在w e b w a t c h e r 的基础上进行了改进，并提出了个性化推荐系统 p e r s o n a l w e b w a t c h e r ；1 9 9 6 年，著名的网络公司雅虎也注意到了个性化服 务的巨大优势和潜在商机，因而推出m y y a h o o ! 这一个性化入口。1 9 9 7 年，a t & t 实验室提出了基于合作方式的个性化推荐系统p h o a k s 以及 r e f e r r a lw e b ；斯坦福大学的m a r k ob a l a b a n o v i c 和y o a vs h o h a m 推出了基 6 第1 蕈绪论 于内容和合作方式的个性化推荐系统f a b 。同年3 月，c o m m u n i c a t i o n so f t h ea c m ) ) 组织了个性化推荐系统的专题报道，标志着个性化服务已经受 到相当的重视。1 9 9 9 年，德国d r e s d e n 技术大学的t a n j aj o e r d i n g 实现了个 性化电子商务原型系统t e l l i m ；麻省理工学院的h e n r yl i e b e r m a n 提出了 基于合作方式的个性化导航系统l e t sb r o w s e ；意大利t o r i n o 大学的l i l m n a a r d i s s o n o 和a n n ag o y 提出了个性化网上商店s e t a 。个性化服务开始向 全球发展。 2 0 0 0 年，n e c 研究院的k u r td b o l l a c k e r 等人为搜索引擎c r e s e e r 增 加了个性化推荐功能，将c i t e s e e r 个性化；m o b a s h e r 于2 0 0 0 年提出用事 务聚类的方法来构筑推荐系统，并取得了较好的效果；s c h e c h t e r 等人根据 用户的访问路径模式预测用户未来可能的h t t p 请求，让代理服务器执行 预取操作，将相关的w e b 页放入其c a c h e 中，以加快访问的速度；c o o l e y d e 等人和b u c h n e r 等人利用数据挖掘技术从访问的l o g 文件中提取用户的访 问模式，用于市场决策和智能推荐服务；n a s r a o u i 等人采用聚类用户访问 模式方法预测用户未来的访问行为；爱尔兰d u b l i n 大学的b a r r ys m y t h 和 p a u lc o t t e r 提出了个性化电视网站p t v ；2 0 0 0 年，美国n s f 基金开始支 持有关个性化服务的研究；同年4 月，以美国为主的多国个性化研究机构 和网络公司成立了个性化协会，旨在推动个性化服务的发展，同时保护个 性化服务中涉及的用户隐私。2 0 0 0 年，我国也开始了个性化服务的研究， 清华大学的路海明等提出基于多a g e n t 混合智能实现个性化推荐。 2 0 0 1 年，纽约大学的g e d i m i n a sa d o m a v i c i u s 和a l e x a n d e rt u z l l i l m 实 现了个性化电子商务网站的用户建模系统p r o ；同年，i b m 公司在其电子 商务平台w e b s p h e r e 中增加了个性化功能，以利于商家开发个性化电子商 务网站；n e c 研究院的e r i c o l o v e r 等人提出了个性化元搜索引擎原型系统 i n q u i r u s 2 。我国也广泛开展了对个性化服务的研究，提出了一些原型系统。 清华大学的冯翱等人提出了基于a g e n t 的个性化信息过滤系统o p e n b o o k m a r k ；南京大学的潘金贵等人设计并实现了个性化信息搜集智能体 d o l t r i a g e n t 。 尽管w e b 挖掘技术已经在个性化系统中得到了广泛的应用，但是还存 7 燕山大学工学硕士学位论文 在着以下几个方面的问题。 ( 1 ) 性能问题w e b 个性化系统都不同程度地扩展了传统的浏览器服 务器体系结构，w e b 信息经过相应处理后才能返回客户端，就必然会延长 响应时间。实时个性化系统对响应时间要求比较高，目前的w e b 挖掘算法 在处理数据时通常都采用离线方式，但是由于现有的算法都有一定的不足， 就造成了性能的降低。例如关联规则方法如果支持度和置信度选取不恰当， 会造成计算时间太长或较差的推荐性能，一般电子商务网站的网页数目巨 大，如果用关联规则方法进行推荐，会使系统很复杂，效率比较低。 ( 2 ) 隐私问题这是一个不可回避的问题，因为要想建立个性化w e b 系统就必须有用户的参与，同时还要分析用户反馈的信息，如果使用 c o o k i e s 一类技术，这就可能涉及到用户的隐私。目前的w e b 个性化技术 还不能很好地解决这个问题，即在实现个性化服务地同时而又不侵犯用户 的隐私。 ( 3 ) 质量评价问题应用w 曲挖掘技术实现w e b 个性化服务，不同系 统采用不同的w e b 挖掘技术，如何评价它们的建模效果以及系统最终的服 务质量也是一个非常重要的问题。目前对个性化系统服务质量的评价，不 同系统采用不同的方式和测试数据，因此无法评价多个不同个性化系统服 务质量的优劣。需要研究一种通用的性能指标和开发相应的b e n c h m a r k 来 评价w 曲各种不同的w 曲挖掘技术。 1 3 本文研究的主要内容 本文在对现有的个性化技术进行了研究和分析，指出了采用w e b 挖掘 技术是个性化发展的必由之路。分析和研究了基于w e b 挖掘的个性化服务 系统，并对现有的个性化服务系统进行了分析比较，指出了w e b 挖掘技术 存在的问题及技术的发展趋势。给出了通用的个性化服务体系结构，详细 的研究了m o b a s h e r 于2 0 0 0 年提出用事务聚类的算法，并指出了事务聚类 算法存在的不足并对此提出了改进方案。 本文的主要内容有以下四个方面： 第1 章绪论 ( 1 ) 研究了基于w e b 挖掘的个性化服务技术对基于w e b 挖掘的个性 化技术进行了深入的研究，根据w e b 挖掘的分类相应的将基于w e b 挖掘 的个性化服务分为三类，并分别详细的介绍了它们。接着我们深入的研究 了基于w e b 挖掘的个性化结构，并从数据收集方式等方面对现有的系统进 行了对比，指出了其不足之处。本文设计了一个比较新颖的基于w e b 挖掘 的个性化服务系统，并详尽的介绍了各个模块的功能和作用。 f 2 ) 研究了基于w e b 挖掘的个性化算法基于w e b 挖掘的个性化服务 使用的算法较多，但是基本可以分为两大类：关联规则算法和聚类算法。 我们从技术及实用性的角度研究了关联规则算法及聚类算法并分析了其优 缺点。 ( 3 1 对事务聚类算法进行了改进m o b a s h e r 于2 0 0 0 年提出用事务聚类 的算法进行个性化服务，由于其简单有效，因此在实际中取得了很好的效 果，所阻十分具有代表性。我们对事务聚类算法进行深入的研究后，发现 了其存在的不足和缺陷，为此我们在保留其简单有效的优点的同时，对其 不足进行了改进以提高其性能。 h ) 对关联规则进行改进个性化关联规则算法具有推荐精度高的优 点，但是其推荐覆盖率极低，为此我们提出关联规则与聚类互补的方法。 ( 5 1 实验对比首先选取一种较为合适的评价测度来进行质量评价，然 后进行了测试数据的选取以及测试方法的确定，最后通过实验对比，证明 了改进之后的算法在性能上优于原算法。 1 4 研究的理论和实际意义 本文研究的理论基础主要是w e b 挖掘技术，以及w e b 挖掘技术在个 性化服务中的应用。 本文的研究成果是研究了基于w e b 挖掘个性化的技术，对比分析了现 有的基于w e b 挖掘个性化系统的体系结构，设计了一个比较新颖的基于 w e b 挖掘的个性化服务系统，研究并实现了m o b a s h e r 于2 0 0 0 年提出用事 务聚类的算法，并指出了事务聚类不足并对其进行了改进。针对关联规则 9 燕山大学工学硕士学位论文 算法的不足，提出了关联规则与聚类互补的方法。本文所述的改进算法在 保持原算法简单有效性的同时，提高了原事务聚类算法的准确性，因此可 以将其直接运用到实际运行的商业个性化网站。对于基于电子商业网站个 性化发展具有十分现实的意义，因此具有巨大的实际应用前景和经济效益。 1 5 本文结构 第2 章主要介绍w e b 挖掘技术及其分类。首先介绍了数据挖掘的主要 技术，然后介绍了w e b 挖掘及其分类。 第3 章主要研究基于w e b 挖掘的个性化服务技术。首先对比了原有的 个性化服务技术与w e b 挖掘技术的有缺点，说明了采用w e b 挖掘技术是 个性化发展的需要；其次，我们在前面研究的基础上，分析指出了w e b 挖 掘技术存在的问题及技术的发展趋势。 第4 章设计了一个新颖的基于w e b 挖掘的个性化服务系统。首先介绍 了基于w e b 挖掘的个性化服务系统的工作原理，并从数据收集方式、挖掘 类型以及服务方式三个方面，将对现有典型的w e b 个性化系统进行比较， 并指出其不足；然后提出了设计的基于w 曲挖掘的个性化服务系统，详尽 的介绍了各个模块的功能和作用。 第5 章主要介绍了事务聚类算法并针对其不足提出了改进。首先深入 细致的研究了事务聚类算法，在总结其优点的同时，指出了其不足之处； 然后，通过对其不足的详细分析，有针对性的提出了改进方案；最后，通 过实验对比证明了改进算法在性能上优于原算法。 第6 章关联规则与聚类互补的方法。研究分析了关联规则算法并指出 了其优缺点，并针对关联规则算法推荐覆盖率低的问题，提出了关联规则 与聚类互补的方法。并通过实验进行了性能上的对比。 最后，总结了本文的工作并提出了下一步设想。 1 0 第2 章理论基础 2 1 引言 第2 章理论基础 数据挖掘( d a t am i n i n g ) 是数据库系统和新的数据库应用的一个有希望 的、欣欣向荣的学科前沿。数据挖掘通常又称数据库中知识发t 觋( k d d ) 1 1 0 】， 是自动的或方便的模式提取，这些模式代表隐藏在大型数据库、数据仓库 或其他大量信息存储中的知识。数据挖掘是一个多学科领域，从多学科汲 取营养。这些学科包括数据库技术、人工智能、机器学习、神经网络、统 计学、模式识别、知识库系统、知识获取、信息检索、高性能计算机和数 据可视化。 随着数据处理工具、先进数据库技术以及万维n ( w w w ) 技术的迅速发 展，大量的形式各异的复杂类型的数据( 如结构化与非结构化数据、超文本 与多媒体数据) 不断的涌现。因此数据挖掘面临的一个重要的课题就是针对 复杂类型数据的挖掘，这包括复杂对象、空间数据、多媒体数据、时间序 列数据、文本数据和w e b 数据，其中w e b 数据尤为重要。 i n t e r n e t 的迅速发展使得w e b 为人们提供了内容丰富且数量庞大的信 息，随着数据挖掘技术的出现阻及发展的日趋成熟，数据挖掘逐渐被应用 于w e b 数据，发现隐藏在w e b 上的知识，以便更好地了解w e b 文档之间 的相互关系、组织形式以及用户对这些文档的使用情况，在此基础上优化 w e b 内容以及组织结构【l “。面向w e b 的数据挖掘技术简称为w e b 挖掘 ( w e bm i n i n g ) ，w e b 挖掘已经成为数据挖掘的个重要的研究方向，人们 越来越多的重视这课题的研究。 w e b 挖掘就是利用数据挖掘技术从w e b 文档和w e b 活动中发现和抽 取人们感兴趣的、潜在的有用模式和隐藏的信息。w e b 挖掘可以在很多方 面发挥作用，如对搜索引擎的结构进行挖掘，确定权威w e b 页面，w e b 文 燕山大学工学硕士学位论文 档分类，w e bl o g 挖掘，智能查询等。 2 2 数据挖掘 2 2 1 数据挖掘技术产生的背景 数据库技术在2 0 世纪8 0 年代的辉煌使得它普及到人类活动的各个角 落，成为各行各业维持和发展的基本工具。经过2 0 多年的数据积累，存放 在大型数据库中的海量数据变成了难得再访问的数据档案。没有强有力的 数据分析工具，理解这些数据已经远远超出了人的能力，同时计算机网络 的广泛应用，加上使用先进的自动数据生成和采集工具，人们所拥有的数 据量极具增大。i n t e r n e t 的迅猛发展使得网络上的各种资源信息异常丰富， 在其中进行信息的查找真如大海捞针。随着信息技术的发展，信息以指数 级地增长，而隐藏在其中的知识并没有很好的挖掘和利用，数据的迅速增 加与数据分析方法的滞后之间的矛盾越来越突出，这种突出的矛盾称为“数 据爆炸而知识贫乏”。人们迫切需要利用一种崭新的技术和工具智能地、自 动地将数据转换成有用的信息和知识，获取的信息与知识可以广泛用于各 种应用，包括商业决策、生产控制、市场分析、工程设计和科学探索等【3 ”j 。 作为计算机的一个领域，机器学习主要的研究问题在于如何通过大量 的训练事例进行学习，产生知识。2 0 世纪9 0 年代机器学习成为研究的热 点之一。将数据库和机器学习结合起来，就产生了海量数据中的知识发现 ( k n o w l e d g ed i s c o v e r y i nd a t a b a s e ) ，简称k d d ，这就是数据挖掘这个新兴 的领域。 数据挖掘( d a t am i n i n g ) 技术是为了解决传统分析方法的不足，并针对 大规模数据的分析处理而出现的，它就是架设在数据和信息之间的桥梁， 通过数据挖掘工具可以发现隐藏在大量数据中的丰富知识( 诸如规律、约 束、模式等) 。数据挖掘是信息技术自然演化的结果。数据挖掘可以广泛地 用于各种应用，包括商务管理、生产控制、电子商务、金融投资、欺诈甄 第2 章理论基础 别、市场行销、市场分析、科学探索和通信网路管理等。数据挖掘有两个 任务。 ( 1 ) 机器的数据库理解：将数据库变换为在表述上可为计算机理解的更 为简洁的模型，然后利用这个模型求解新问题。 ( 2 ) 数据库理解：根据需求简化数据并将其翻译为自然的表示形式( 数 学公式，自然语言与图表等) ，发现隐含在大量数据中的规律并使之为人理 解。数据挖掘可以从实例数据中直接导出规则，用于构造知识库；也可在 数据库中对已有规则进行验证，因此对知识库的维护和更新也是有用的。 2 2 2k d d 和数据挖掘 k d d 目口数据库知识发现，为k n o w l e d g ed i s c o v e r y i nd a t a b a s e 的缩写。 这一术语首先出现在1 9 8 9 年在美国底特律召开第l l 届国际人工智能联合 会议的专题讨论会上，1 9 9 1 、1 9 9 3 和1 9 9 4 年又接着继续举行k d d 专题讨 论会【” 。1 9 9 5 年在加拿大召开了第一届知识发现和数据挖掘国际学术会 议。从1 9 9 7 年开始，k d d 已经拥有了专门的杂志k n o w l e d g e d i s c o v e r y a n d d a t am i n i n g 。国外在这方面发表了众多的研究成果和论文，并且开发了 一大批数据挖掘软件，对数据挖掘的研究已经成为了计算机领域的一个热 门课题。 众多学者认为数据挖掘和k d d 是等价的概念，人工智能领域习惯成 为k d d ，而数据库领域习惯称呼为数据挖掘；也有学者把k d d 看作是发 现知识的完拯过程，而将数据挖掘视为其中的一个基本步骤。 知识发现的过程主要由以下几个步骤组成口l 叫： ( 1 ) 数据清理( 消除噪声或者不一致的数据) ； ( 2 ) 数据集成( 多种数据源可以组合在一起) ； ( 3 ) 数据选择( 从数据库中检索与分析任务相关的数据) ； ( 4 ) 数据变换( 数据变换或统一成适合挖掘的形式，如通过汇总或聚集) ； f 5 ) 数据挖掘( 基本步骤，使用智能方法提取数据模式) ； ( 6 ) 模式评估( 根据某种兴趣度度量，识别表示知识的真正有趣的模式) ； 燕山大学工学硕士学位论文 ( 7 ) 知识表示( 使用可视化和知识表示技术，向用户提供挖掘的知识) 。 我们可以将前4 个步骤统称为数据预处理过程( d a t a p r e p r o c e s s i o n l 。 数据挖掘步骤可以与用户或知识库交互。有趣的模式提供给用户，或 作为新的知识存放在知识库中。 注意，根据这种观点，数据挖掘只是整个过程中的一步，是最重要的 一步，因为它发现隐藏的模式。 这里我们同意数据挖掘作为知识发现的一个重要步骤，但是由于在产 业界、媒体和数据库研究界，“数据挖掘”比较长的术语“数据库中只是发 现”更流行。因此，在本文中，选用术语数据挖掘。我们采用数据挖掘的 广义观点：数据挖掘是从存放在数据库、数据仓库或其他信息库中的大量 数据中挖掘有趣知识的过程。 对于数据挖掘的定义我们要作几点说明。 f 1 ) 对几个概念进行解释过程是指多阶段的一个过程，涉及数据准 备、模式搜索、知识评价以及反复的修改等。而有趣是有效性( v a l i d ) 、新 颖性( n o v e i ) 、潜在有用性f p o t e n t i a l l yu s e f u l ) 和最终可理解。 生( u l t i m a t e l y u n d e r s t a n d a b l e ) 综合在一起形成的。有效性是指发现的模式对于新的数据 仍保持有一定的可信度。新颖性要求发现的模式应该是新的，从未知的。 潜在有用性是指发现的模式能被用户理解，目前它主要是体现在简洁性上。 f 2 ) 数据挖掘质量的好坏受两个方面因素的影响一是所采用的数据 挖掘算法的有效性，二是用于挖掘的数据的质量和数量( 数据量的大小) 。 如果选择错误的数据或属性，或对数据进行了错误的转换，则有可能得不 到正确的挖掘结果，所以数据预处理对于数据挖掘来讲是非常重要的，同 时，数据预处理也是数据挖掘中的一个重要研究课题。 ( 3 ) 整个挖掘过程是一个不断重复的过程假如用户在挖掘过程中发 现选择的属性或数据有偏差，或者使用的挖掘技术产生不了预期的结果， 这时候就需要根据反馈结果，不断重复先前的过程，甚至从头重新开始， 最终得到令人满意的挖掘结果。 ( 4 ) 可视化在数据挖掘的各个阶段都扮演着重要的作用在数据准备 阶段，用户可能要使用散点图、直方图等可视化统计技术来显示有关数据， 1 4 第2 章理论基础 以便对数据有一个初步的理解，从而为更好地选取数据打下坚实的基础。 在挖掘阶段，用户有可能要使用与领域问题有关的可视化工具，来选择挖 掘算法或者调整挖掘算法的参数。在结果表示阶段，则可能又要用到其它 的可视化技术，以利于用户对挖掘结果的理解。 数据挖掘功能用于指定数据挖掘任务中要找的模式类型。数据挖掘任 务一般可以分为两类：描述和预测。描述性挖掘任务刻划数据库中数据的 一般特性。预测性任务挖掘在当前数据上进行推断，以进行预测。 数据挖掘常用的技术有 1 4 , 1 5 ： ( 1 ) 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ) 它从结构上模仿生物神 经网络，是一种通过训练来学习的非线性预测模型，可以完成分类、聚类、 特征挖掘等多种数据挖掘任务。数据挖掘的技术基础是人工智能( m 1 。但 它仅仅利用了人工智能中一些已经成熟的算法和技术，例如：人工神经网 络( a r t i f i c i a l n e u r a ln e t w o r k s ) 、遗传算法( g e n e l i ca l g o r i l h m s ) 、决策树 ( d e c i s i o nt r e e ) 、邻近搜索方法( n e a r e s tn e i g h b o rm e t h o d ) 、规则推l 里( r u l e i n d u c t i o n ) 、模糊逻辑( f u z z yl o g i c ) 等，其问题的复杂度和难度比人工智能 降低了许多。数据挖掘系统利用的技术越多，得出的结果精确性就越高。 ( 2 ) 决策树( d e c i s i o nt r e e ) 用树形结构表示决策集合，这些决策集合 通过对数据集的分类产生规则。典型的决策方法有分类回归树( c a r t ) ，一 般用于分类规则挖掘。 ( 3 ) 遗传算法( g e n e t i ca l g o r i t h m ) 基于生物进化的概念设计一系列的 过程来达到优化的目的。这些过程有基因组合、交叉、变异和自然选择。 为了应用遗传算法，需要把数据挖掘任务表达为一种搜索问题而发挥遗传 算法的优化搜索能力。 ( 4 ) 最近邻技术( n e a r e s tn e i g h b o r ) 通过k 个最与之相近的历史记录的 组合来辨别新的记录，有时候也称这种技