（计算机应用技术专业论文）改进的关联规则在个性化网站建设中的应用.pdf

改进的关联规则在个性化网站建设中的应用 摘要 一个网站有许多个网页组成，网站上的信息分布在这些网页上，不同的用户 对不同网页上的信息感兴趣，但是网站中大量的网页存在着结构的不合理性，链 接页面的无效性等现状，降低了用户访问页面的效率，如何通过w e b 使用挖掘技 术来了解用户的兴趣和爱好，分析用户的浏览模式，根据用户的当前访问需要， 自动实时地为用户提供推荐页面，满足多元化的需求，使得个性化服务势在必行。 本文分析了基于动态网页下信息采集的方法和算法，通过基于逻辑与运算构 造支持矩阵快速挖掘频繁模式的挖掘算法( f d l g ) 对信息进行挖掘产生关联规 则，并借助模糊动态聚类算法辅助实现个性化推荐的体系结构。 论文的主要工作如下： ( 1 ) 概述了数据挖掘的有关研究内容，探讨了关联规则数据挖掘的研究现状。 ( 2 ) 探索了动态网页下数据采集的方法，大大减少了记录量，提高了用户的 识别率。 ( 3 ) 对关联规则挖掘理论展开研究，讨论了一些传统的关联规则挖掘算法存 在的问题，然后提出了基于逻辑与运算的快速挖掘频繁模式的挖掘算法f d l g ， 减少了计算量，提高了挖掘效率。 ( 4 ) 本文提出了访问页面关联规则和访问模式聚类分析结果相结合进行个性 化推荐的方法，模糊聚类算法作为关联规则的预处理或者通过模糊聚类将相似的 用户或相似页面聚在一起，形成相似用户、页面群体，从而有利地为个性化推荐 提供服务。 关键词：数据挖掘；布尔关联规则；模糊动态聚类；w e b 日志挖掘；个性化 服务 a p p l i c a t i o no fi m p r o v e da s s o c i a t i o nr u l e si np e r s o n a l i z a t i o n w e b s r ec o n s t r u c t i o n a b s t r a c t aw e b s i t ei s c o m p o s e do fs e v e r a lw e bp a g e s ，o nw h i c ht h ei n f o r m a t i o n d i s t r i b u t e s d i f f e r e n tu s e r sg e ti n t e r e s t e di nd i f f e r e n tw e bp a g e s h o w e v e r ，t h e u n r e a s o n a b l es t r u c t u r eo fp a g e sa n di n e f f i c i e n tl i n kp a g e sd e c r e a s et h ee f f i c i e n c yo f a c c e s s i n gp a g e s p e r s o n a l i z a t i o ns e r v i c es e e m si m p e r a t i v ef o r u st ol e a r na b o u tt h e u s e r si n t e r e s t sa n da n a l y z et h eb r o w s i n gp a t t e r n sb ym e a n so fw e bm i n i n gt e c h n o l o g y , s oa st oa u t o m a t i c a l l yr e c o m m e n dar e a l t i m ep a g ef o rt h eu s e ra n dm e e tt h en e e do f c o n g l o m e r a t i o n 如t h et h e s i s m e t h o da n da l g o r i t h mo fi n f o r m a t i 锄e x t r a c t i o nb a s e do nd y n a m i c w e bp a g e sa r ea n a l y z e df d l gm i n e si n f o r m a t i o na n dp r o d u c e st h ea s s o c i a t i o nr u l e s u s i n gt h em i n i n ga l g o r i t h mf o rf r e q u e n tp a t t e r n s w i t ht h eh e l po ff u z z yd y n a m i c c l u s t e r i n ga l g o r i t h m ，as y s t e m a t i c s t r u c t u r e i sf o r m e dw i t h p e r s o n a l i z e d r e c o m m e n d a t i o n t h et h e s i si n c l u d e st h ef o l l o w i n gp a r t s ： ( 1 ) s u m m a r i z et h em s e a r c hr e s e tc o n c e r n i n gt h ed a t am i n i n ga n d d i s c u s st h e c u r r e n tr e s e a r c hs i t u a t i o no f t h ed a t am i n i n gb a s e do na s s o c i a t i o nr u l e s ( 2 ) e x p l o r et h ea l g o r i t h mf o rd a t aa c q u i s i t i o ni nd y m m i np a g e st od r a m a t i c a l l y d e c r e a s et h ea m o u n to f r e c o r da n di m p r o v et h er e c o g n i t i o nr a t e ( 3 ) m a k eas t u d yo nt h ea s s o c i a t i o nr u l e s - b a s e dm i n i n gt h e o r y ，d i s c u s s i n gt h e s h o r t a g ei nt h et r a d i t i o n a lm i n i n ga l g o r i t h m ，t h e np r o v i d i n gf d l gb a s e do nt h ef a s t f r e q u e n tm i n i n gp a r e mo f l o g i ca n do p e r a t i o nt or e d u c et h ea m o u n to f c a l c u l a t i o na n d i m p r o v et h ee f f i c i e n c y ， ( 4 ) c o m b i n i n gt h ea s s o c i m i o nr u l e so fp a g ea c c e s sa n dt h er e s u l t so fc l u s t e r i n g a n a l y s i so na c c e s sm o d e ，am e t h o do fp e r s o n a l i z e dr e c o m m e n d a t i o ni sp r o v i d e d i ti s c o n v e n i e n tf o rp e r s o n a l i z e dr e c o m m e n d a t i o nt of o r ms i m i l a ru s e l sa n dp a g eg r o u pb y m e a n so f c l u s t e r i n gt h es i m i l a rb s e r sa n dp a g e st h r o u g hf u z z yc l u s t e r i n g ， k e y w o r d s ：d a d am i n i n g ；b o o l ea s s o c i a t i o nr u l e s ；f u z z yd y n a m i cc l u s t e r i n ga l g o r i t h m ； w e bd a i l yr e c o r dm 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 e s h 插图清单 图1 1 典型的数据挖掘系统2 图1 2w e b 挖掘分类6 图2 1a p r i o r i 算法的流程图一1 5 图2 2 频繁项集支持矩阵m x 2 2 图2 3 三种算法比较2 7 图3 1 对称矩阵2 9 图3 2 原始数据矩阵2 9 图4 1 个性化推荐系统3 1 图4 2 数据采集程序流程3 3 图4 3 用户界面3 3 图4 4 关联规则数据挖掘系统界面3 7 图4 5 模糊聚类结果3 7 v i 表格清单 表2 1 事务数据库1 1 7 表2 21 一项集c 1 1 7 表2 3 频繁1 项集l 1 1 7 表2 42 - 项集c 2 18 表2 5 频繁2 项集l 2 18 表2 6 候选3 项集c 3 18 表2 7 频繁3 项集l 3 1 8 表2 8 事务数据库2 2 2 表2 9 事务项的位向量2 2 表2 1 0 支持矩阵对应数组值2 3 表4 ia s p 采集信息表3 2 表4 2 采集表的事务数据库。3 4 v l l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得金壁至些太堂或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。 学位论文储签字阅簪 签字日期：沙7 年，f 月侈日 学位论文版权使用授权书 本学位论文作者完全了解金鼹王些盔堂有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅本人授权盒胆王些 左兰可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影印，缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位做储躲i 珊 签字日期：舴f 1 月f 穸日 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名 z 沌 上| 、 签字b 强：叼年h 民增日 电话 邮编 致谢 大学毕业十年以后，在工作中逐渐发现再专业知识上的不足，非常感谢山东 信息职业技术学院给我继续学习的机会。在职攻读学位的几年里，在繁重的工作 之余同时学习，着实感觉到紧张、忙碌，尤其写论文期间，备感艰辛，但的确非 常的充实。 本论文是在我的导师王浩教授的悉心指导下完成的。在我的论文开题和撰写 过程中，王老师给予了很多的帮助，为我指明了方向。在王老师的关怀和教导下， 我不仅仅学到了知识，而王浩老师渊博的学识、严谨的治学态度、敏锐的学术思 想更是我学习的榜样。在此谨向王老师致以衷心的感谢和崇高的敬意! 感谢计算机学院所有给我们授课的老师，从这些老师那里不仅学到了专业知 识，更重要的是他们严谨的治学态度和敬业精神，特别是胡学钢教授，非常感谢 他的引见和指导。 感谢各位评审专家在百忙之中抽时间对论文进行了仔细的评阅。 另外还要感谢我的父母及家人，给予我生活上的支持和精神上的鼓励。 感谢山东信息职业技术学院所有帮助过我的领导和老师，感谢帮助过我的朋 友们! i l l 作者：国伟 2 0 0 7 年1 1 月 第一章数据挖掘 随着数据库技术的迅速发展以及数据库管理系统的广发应用，人们积累的数 据越来越多，数据挖掘是信息技术发展到一定阶段的必然能产物。 1 1 课题研究背景及意义 i n t e m e t 的发展，使其已成为信息传播、交流与共享的主要媒体。w e b 站点数 目和规模日益扩大。w e b 站点服务器每天产生大量的日志，其中蕴涵了有关用户 在网站上行为的丰富数据，分析这些数据能够发现有意义的隐藏访问模式规则， 如何对这些数据进行整理和分析，充分了解客户的兴趣爱好，设计满足不同客户 群体需要的个性化网站具有重要意义。虽然w 曲服务器日志记录了作为分析依据 的用户访问数据，但日志记录的庞大使得直接人工分析这些原始数据几乎是不可 行的。因此借助数据挖掘技术，将之运用到w 曲数据中，就形成了w e b 挖掘。w e b 挖掘是将数据挖掘技术应用于大规模w e b 数据，以期发现有效的、新颖的、潜在 有用的，以及最终可理解的模式规则的规程。随着互联网内容指数级的增长，以 及数据挖掘等新技术的出现，信息服务方式从传统的“一对多”发展到“一对一” 的个性化用户服务方式，利用w e b 挖掘技术已经成为个性化服务的一个研究热点。 1 2 数据挖掘的产生 半个多世纪以来，计算机技术的高速发展使得信息技术已经渗透到人类活动 的各个领域。随着信息技术的快速发展和信息搜集能力的日益提高，产生了海量 的数据。这些激增的数据背后隐藏着许多重要的信息，人们面对着海量的数据资 源，却往往无法找到需要的信息，难以发现有用的知识，这就是“知识爆炸”给 人们带来的困惑。如何有效地利用和处理大量的数据，成为当今世界共同关心的 问题。随着数据仓库( d a t a w a r e h o u s e ) 的出现，为更深入对数据进行分析提供 了条件。近十年来，数据挖掘的研究工作取得了很大的进展，各种数据挖掘软件 的应用极大地推动了人们掌握、处理信息的能力，并为人们带来了很好的经济效 益。 数据挖掘【3 】是在数据仓库或大型数据库的基础上，从大量的、模糊的、随机 的数据中提取出数据间重要的但容易被人工分析忽略的知识和信息，自动地发现 隐藏在数据问的模式，做出预测性分析。数据挖掘的概念有广义和狭义之分，但 是无论从哪个角度来定义数据挖掘，都应体现数据挖掘的3 个基本特性，即潜在 性、价值性与可理解性。潜在性是指挖掘出来的知识是隐藏在数据中的，事先不 知道的；价值性指数据挖掘的结果是用户感兴趣的，有用的知识和模式；理解性 是指挖掘的结果应该具有可解释性，并可以被人们所接受和利用的知识。 1 3 数据挖掘技术的过程 数据挖掘一般可细化为以下几个主要步骤1 1 1 。 ( 1 ) 数据收集 大量丰富的数据是数据挖掘的前提，没有数据，数据挖掘也就无从做起。因 此数据收集是数据挖掘的首要步骤。数据可以来自于现有事务处理系统，也可以 从数据仓库中得到。 ( 2 ) 数据预处理 数据预处理是数据挖掘( 知识发现) 过程中的一个重要步骤，尤其是在对包含 有噪声、不完整，甚至是不一致数据迸行数据挖掘时，更需要进行数据的预处理， 以提高数据挖掘对象的质量，并最终达到提高数据挖掘所获模式知识质量的目 的。同时，通过数据整理，可以对数据做简单的泛化处理，从而在原始数据的基 础之上得到更为丰富的数据信息，进而便于下一步数据挖掘的顺利进行。 ( 3 ) 数据挖掘 利用各种数据挖掘方法对数据进行分析。 ( 4 ) 数据挖掘结果的评估 数据挖掘的结果有些具有实际意义，而另一些没有实际意义，或是与实际情 况相违背，这就需要进行评估。评估可以根据用户多年的经验，也可以直接用实 际数据来验证模型的正确性，进而调整挖掘模型，不断重复进行数据挖掘。 ( 5 ) 分析决策 数据挖掘的最终目的是辅助决策，决策者可以根据数据挖掘的结果，结合实 际情况调整竞争策略等。 总之，数据挖 图i 1 典型的数据挖掘系统 2 效果。 1 4 数据挖掘方法 数据挖掘涉及的学科领域和方法很多，有多种分类法。根据挖掘任务，数据 挖掘算法的研究主要集中在关联规则挖掘( a s s o c i a t i o nr u l e sm i n i n g ) 、分类和预测 ( c l a s s i f i c a t i o na n dp r e d i c t i o n ) 、聚类( c l u s t e r ) 以及复杂数据的挖掘( m i n i n gc o m p l e x t y p e so fd a t a ) 等方面。根据挖掘的对象可有w e b 挖掘，文本挖掘等。下面主要对 关联规则挖掘、分类和预测、聚类进行介绍，有关复杂数据挖掘及其它挖掘作以 介绍，可以参见文献【i 】。 1 4 1 关联规则挖掘 关联规则挖掘的思想起源于购物篮数据的分析，一条关联规则如：9 5 购买 牛奶的顾客同时会购买面包。自从r a g r a w a l ，t i m i e l i n s k i 和a s w a m i 在1 9 9 3 年提出关联规则挖掘以来1 2 】，关联规则挖掘己经引起了研究者的广泛关注，已经 提出了许多有效的关联规则挖掘算法。关联规则挖掘将在下一章中详细讨论。 1 4 2 分类与预测 分类和预测是数据挖掘中应用领域极其广泛的重要技术之一。分类和预测是 两种数据分析形式，它们可以用于抽取能够描述重要数据集合或预测未来数据趋 势的模式。 ( 1 ) 分类 分类是根据数据集的特点构造一个分类器，利用分类器对未知类别的样本赋 予类别的一种技术。分类可以分为设计和实现两个阶段f 4 】。设计就是用一定数量 的样本( p q 做训练集或学习集) 进行分类器的设计。实现是指用所设计的分类器对 待识别的样本进行分类决策。其中设计阶段分为训练和测试两个步骤 5 1 。分类是 数据挖掘中一个重要的方法。由于机器学习、模式识别和统计学等学科对分类方 法都有研究，而且研究的历史相对数据挖掘的历史来说是很长的，所以提出了很 多的分类方法。基于基于决策树的分类方法、基于b a y e s 的分类方法和基于神经 网络的分类方法只是众多分类方法中比较典型的几种方法。其它相对常用的分类 方法还有基于关联规则的分类方法、k 近邻分类方法、粗糙集分类方法和模糊集 分类方法等等，在文献【1 8 中对这些方法进行了介绍。 ( 2 ) 预测 数据挖掘中的预测一般认为是针对连续系统而言的，可以用概率统计中的回 归统计技术建模。许多问题可以用线性回归解决，并且更多的可以对变量进行变 换，使得非线性问题可以转化为线性问题进行处理。 线性回归的简洁性使得它被广泛的应用。预测的方法还有组合预测模型的回 归分析方法、模糊分类回归法等等。 1 4 3 聚类 聚类分析是数据挖掘中重要的研究课题之一。聚类被广泛研究并应用于机器 学习、统计分析、模式识别以及数据库数据挖掘与知识发现等不同的领域。所谓 聚类【7 】【羽，就是将物理或抽象对象的集合组成为由类似的对象组成的多个类的过 程。 由聚类所生成的类是一组数据对象的集合。聚类分析的原理是使属于同一类 别的个体之间距离尽可能小，而不同类别的个体之间距离尽可能大。目前在文献 中存在大量的聚类算法。算法的选择取决于数据的类型、聚类的目的和应用。如 果聚类分析被用作描述或探查的工具，可以对同样的数据尝试多种算法，以发现 数据可能揭示的结果。主要的聚类算法可以分为【9 1 ：划分方法、层次的方法、基于 密度的方法、基于网格的方法和基于模型的方法。划分方法中的k m e a n s 算法 【1 0 】是聚类分析中理论上最可行、应用最为广泛的算法之一。 聚类与分类有相似性，都是把一个数据集分成若干不同的类。它们的不同之 处在于，分类是在知道类别和可分的类别数目的情况下进行的，也即为数据集中 的数据在给定的类别中选择一个最适合的类别；而聚类是在不知道数据集能分为 多少个类，能分成哪些类的情况下进行的。从中可以看出，聚类是没有训练集的， 是观察式学习，而不是示例式学习。 1 5 w e b 挖掘 网络的迅速发展，其上的数据资源急剧增加，w e b 成了存储、发布及获取信息 的最重要的载体。然而，w e b 是无结构的、动态的、并且w e b 页面的复杂程度远 远超过了文本文档，人们不想被w e b 上的信息所淹没，从中及时发现有用的知识， 提高信息利用率的一个有效途径，就是将传统的数据挖掘技术与w e b 结合起来， 进行w e b 挖掘。 1 5 1w e b 个性化挖掘的发展历史及国内外研究现状 w e b 个性化技术是将w e b 挖掘技术应用于个性化服务之中。自上个世纪九十 年代出现以来，已经有多种个性化服务系统：如美国m i n n e s o t a 和d e p a u l 大学开 发的w e b s i f t 系统致力于w e b 使用挖掘算法的研制开发；1 9 9 6 年，著名的网络 公司雅虎注意注意到个性化服务的巨大优势和潜在商机，推出了m yh a y o o 网站， 允许用户选择希望查看的主题中特定的栏目，构造自己专用的网页，此系统的内 容能够自动更新。2 0 0 0 年，n e c 研究院的k u r td b o l l a c k e r 等人为搜索引擎 c i t e s e e r 增加了个性化推荐功能，将c i t e s e e r 个性化。还有象w e b m a t e 、p v a 、 s y s k i l l & w e b e r t 。l i r a 是基于客户端的服务系统，但其缺点是获取用户的兴趣方式 上单一，不能综合利用用户的各种行为动态地提取用户兴趣。w e b w a t c h e r 和 g r o u p l e n s 主要是基于服务器端的系统，此类系统能够根据多个用户对某一个网 站的访问情况，利用相似性提供个性化服务，但它们不能获得某个用户对多个网 站的访问情况，因此很难全面获取用户的兴趣。2 0 0 0 年4 月，以美国为主的多个 国家个性化服务研究机构和网络公司成立了个性化服务协会，旨在推动个性化服 务的发展；我国自2 0 0 0 年也开始了个性化服务技术的研究，并取得了一些成果， 如目前最大的中文搜索网站百度，南京大学设计的个性化信息搜索智能体系 d o l t r ia g e n t 等等。尽管w e b 挖掘技术在个性化推荐系统的应用中取了广泛的 4 应用，但还是存在一些问题，主要有i lo j ： ( 1 1 性能闯题 w e b 个性化系统都不同程度地扩展了传统的浏览器服务器体系结构，w e b 信 息经过了相应处理后才能返回客户端，就必然回延长响应时间，实时个性化系统 对响应时间要求比较高，目前的w e b 挖掘算法在处理数据时通常采用离线方式， 但是由于现有的算法存在一定的不足，造成了性能的降低。例如关联规则方法如 果支持度和置信度选取不当，会造成计算时间太长或较差的推荐性能。 ( 2 ) 质量评价问题 应用w e b 挖掘技术实现w e b 个性化服务，不同系统采用不同的挖掘技术，如 何评价它们的建模效果以及系统最终的服务质量也是一个非常重要的问题。目前 对个性化系统服务质量的评价，不同系统采用不同的方式和测试数据，因此无法 评价多个不同个性化系统服务质量的优劣。需要研究一种通用的性能指标和开发 相应系统来评价各种不同的w e b 挖掘技术。 ( 3 ) 隐私问题 这是一个不可回避的问题，因为要建立个性化w e b 系统就必须有用户的参与， 同时还要分析用户的反馈信息，这就可能涉及到用户的隐私。目前的w e b 个性化 技术还不能很好地解决这个问题。 随着w w w 上信息爆炸性的增长，能利用自动工具进行所需资源的寻找，以 及跟踪、分析用户使用w e b 的模式，就变的非常必要。这些因素促使对于能够有 效地在服务器端、客户机端挖掘知识的智能系统需求大量增长。笼统地说，数据 挖掘被应用到w o r l dw i d ew e b 上，就称作w e b 挖掘，这是近来研究的焦点。 w e b 挖掘可以广义上的定义为“从w w w 上发现和分析有用的信息”。这个 定义包含了两层含义：( 1 ) 自动的在线信息搜索，也就是在w w w 资源上进行的信 息发现，称作w e b 内容挖掘。( 2 ) 研究用户访问w e b 服务器的模式，也就是挖掘 用户浏览、访问w w w 的模式，称作w e b 应用挖掘。 1 5 2w e b 数据挖掘的分类 w e b 挖掘可分为三类：w e b 内容挖掘、w e b 结构挖掘、w e b 使用挖掘【2 2 1 。如 图2 2 所示：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 2 0 的 出现，w e b 数据挖掘多出了一个分类一w 曲用户性质挖掘。 图1 2 w e b 挖掘分类 本文将详细介绍w e b 使用挖掘技术及其在个性化站点中的运用。 1 5 2 1w e b 内容挖掘 w e bf 1 日容挖掘主要包括文本挖掘和多媒体挖掘两类，其对象包括文本、图像、 音频、视频、多媒体和其他各种类型的数据。这些数据一般由非结构化的数据( 如 文本) 半结构化的数据( 如h t m l 文档) 和结构化的数据( 如表格) 构成。对非结构化 文本进行，w e b 挖掘，称为文本数据挖掘或文本挖掘，是w e b 挖掘中比较重要的 技术领域。目前，关于w e b 内容挖掘的研究大体以w e b 文本内容挖掘为主。w e b 内容挖掘有两种策略：直接挖掘文档的内容，或在其它工具搜索的基础上进行改 进。采用第1 种策略的有针对w e b 的查询语言w e bl o g ，w c b o q l 等，利用启发式 规则来寻找个人主页信息等等。采用第2 种策略的方法主要是对搜索引擎的查询 结果进行进一步的处理，得到更为精确和有用的信息。属于该类的有w e b s q l ， 及对搜索引擎的返回结果进行聚类的技术等。w e b 内容挖掘一般从资源查找和数 据库两个不同的方面进行研究。目前w e b 内容挖掘的主要研究内容是对w e b 上大 量文档集合的内容进行总结、分类、聚类、关联分析、科学文献资料浏览导航， 以及利用w e b 文档进行趋势预测。 1 5 2 2w 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 w 能够提供除文档 内容之外的有用信息。利用这些信息，可以对页面进行排序，发现重要的页面。 这方面工作的代表有p a g e r a n k 和c l e v e r 。此外，在多层次w e b 数据仓库( m l d b l 中也利用了页面的链接结构。 w e b 结构挖掘所得到的模式，可以揭示许多蕴涵在w e b 内容之外的隐含着的 有用信息。如通过文档之间的超链接，可以挖掘出文档之间的引用关系，从而有 助于找到与用户请求相关的权威页面；通过分析w e b 网页内部树形结构，可以发 6 现与给定页面集合相关的其它页面；w e b 页面的u r l 同样可以反映页面的类型以 及页面之间的从属关系，通过分析页面的u r l 信息，可以找到改变了位置的w e b 页面新位置： w e b 结构挖掘常见的算法有p a g e r a n k 、h i t s ( h y p e r t e x ti n d u c e dt o p i cs e a r c h ) ， 二次方程推断法( q u a d r a t i ce x t r ap o l a u o n ) 、分块矩阵排序算法( b l o c kr a n k a l g o r i t h m ) 、发现虚拟社区( c y b e r - - c o m m u n i t y ) 的算法，发现相似页面的算法等。 w e b 结构挖掘的算法一般可分为查询相关算法和查询无关算法两类。 1 5 2 3w e b 使用挖掘 除了w c 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 c b 使用记录 挖掘则面对的是在用户和网络交互的过程中抽取出来的第二手数据。这些数据包 括：网络服务器访闯记录、代理服务器日志记录，浏览器端日志记录、用户简介、 注册信息，用户对话交易信息，c o o k i e 中的信息、用户查询等一切用户与站点之 间可能的交互记录。一般可分为一般访问模式分析以及分析特制w c b 站点。 目前研究较多的w e b 日志挖掘技术和工具可分为两大类：模式发现和模式分 析。模式发现主要采用数据挖掘领域的一些技术和算法，对w e b 使用模式进行挖 掘。如路径分析、关联规则、聚类和分类等。模式分析是通过模式识别算法找到 的模式集合中有意义的模式、规则。它需要一些分析工具的辅助，如果没有合适 的技术和工具来帮助分析人员理解，挖掘出来的模式将得不到很好的利用。常用 的模式分析技术有；知识查询，可视化技术，联机分析处理( s l a p ) 等。 1 5 2 4w e b 用户性质挖掘 w e b 2 0 是从2 0 0 4 年至今一直都很流行的名词。w e b 2 0 时代的显著特征是个 性化、互动性、大众化和去中心，旨在给用户提供更人性化的服务。同时不再像 w e b l 0 时代用户r 能被动的接受各网站“填鸭”式的信息轰炸。在w e b 2 0 时代， 每个普通用户既是信息的获取者，也是信息的提供者。面对w e b 2 0 的诞生，w e b 数据挖掘技术又面临着新的挑战。如果说w e b 使用挖掘是通过挖掘网站访问者在 网站上留下的痕迹来获取有用的信息，那么w e b 用户性质挖掘则是要去w e b 用 户的老巢去探寻究竟。在w e b 2 0 时代，网络彻底个人化了，w e b 用户可以用自 己的方式、喜好来个性化定制自己的互联网。w e b 2 0 赋予w e b 用户最大的自由 度，同时给予有心商家有待发掘的高含金量信息数据。通过对w e b 用户自建的 b l o g 、r s s 等w e b 2 0 功能模块下客户信息的统计分析，能够帮助运营商以较低 成本获得准确度较高的客户兴趣倾向、个性化需求以及新业务发展趋势等信息。 有关在w e b 2 0 下面的数据挖掘正在进一步研究中。 7 1 6 数据挖掘存在的问题及发展趋势 尽管数据挖掘有如此多的优点，但数据挖掘也面临着许多的问题，这为数据 挖掘未来的发展提供了巨大挑战。 ( 1 ) 数据的表示：数据挖掘的基本问题就在于数据的数量和维数，数据结构 也因此显得非常复杂，如何进行探索，选择分析变量，成为首先要解决的问题， 在不同的应用系统中，有许多不同类型的数据库存在，一个功能强大的数据挖掘 系统应该能够处理不同类型的数据库和数据类型。 ( 2 ) 数据的抽样：面对海量数据，现有的统计分析方法等遇到了困难，如何 对数据进行抽样，即抽样数据的合理性，应该作以考虑和评价。 ( 3 ) 多个抽象层的交互知识挖掘- 由于很难准确地知道能够在数据库中发现什 么，数据挖掘过程应当是交互的。对于包含大量数据的数据库，应当使用适当的 抽样技术，进行交互式数据探查。交互式挖掘允许用户聚焦搜索模式，根据返回 的结果提出数据挖掘请求。特殊地，类似于o l a p 在数据立方体上做的那样，应 当通过交互地数据空间和知识空间下钻、上卷和转轴来挖掘知识。用这种方法， 用户可以与数据挖掘系统交互，以不同的粒度和从不同的角度观察数据和发现模 式。 ( 4 ) 数据挖掘查询语言和特定的数据挖掘：关系查询语言一允许用户提出特定 的数据检索查询。这种语言应当与数据库或数据仓库查询语言集成，并且对于有 效的、灵活的数据挖掘是优化的。 ( 5 ) 数据挖掘结果的表示和显示：发现的知识应当用高级语言、可视化表示或 其他方式形式表示，使其易于理解，能够直接被人们使用。这要求系统采用有表 达能力的知识表示技术，如树、表、规则、图、图表、交叉表、矩阵或曲线。 ( 6 ) 数据挖掘的结果是不确定的，数据挖掘是一个复杂的过程，在挖掘过程 中用户的参与是必不可少的。有效的决策过程往往需要多次交互和多次反复，使 数据挖掘的结果准确地满足数据挖掘的要求，并易于表达，实现在多抽象层上交 互挖掘知识。因此在研究中要寻求数据挖掘过程的可视化方法，使知识发现的过 程能够被用户理解，也便于知识发现过程中的人机交互，同时要和专业知识相结 合才能对其做出判断。 ( 7 ) 目前数据挖掘工具或者使用单一的技术，或者是有限的几种技术的集合。 就数据分析而言，没有一种万能的分析方法，每一个特定的问题，都存在一种最 适合它的技术。因此，一个真正有用的工具必须能够提供各种不同的挖掘技术 ( 8 ) 当数据挖掘使用户可以从不同角度、不同抽象层上观察数据时，将影响 到数据的私有性和安全性。数据挖掘揭示不容易被发现的模式或知识，如果不正 确使用，它可能对隐私和信息安全构成威胁。因此研究怎样的数据挖掘可能导致 数据的安全性问题，应采取何种安全性措施来防止敏感数据外泄是实际应用中必 须解决的问题。 总之，数据挖掘只是一个工具，不是万能的。数据挖掘的成功要求对期望解 决问题的领域有深刻的了解，理解数据，了解其过程，才能对数据挖掘的结果找 出合理的解释。 1 7 论文的主要内容与结构 全文共分五章，各章节安排如下： 第一章介绍论文的研究背景、国内外研究现状，阐述数据挖掘的概念、分 类、方法及发展等论文的整体结构。 第二章对关联规则技术及其理论进行研究，并对经典的关联规则挖掘算法 进行详细的讨论，并给出了改进布尔算法的应用以及与其它算法的比较。 第三章简单地介绍了模糊聚类的特点，模糊聚类的过程以及经典的算法。 第四章基于关联规则的用户浏览访问模式发现，利用经典的聚类算法寻找 相似页面或相似群体，从而为用户推荐将要访问的页面，实现了个性化推荐服务 系统原型。 第五章进行总结展望，对整篇论文进行总结，以及对后续工作进行展望。 1 8 小结 本章介绍数据挖掘技术的概念、数据挖掘过程、分类及数据挖掘的方法。并 对数据挖掘中最常用的关联规则、分类与预测、聚类等方法进行综述，详细地介 绍了w e b 挖掘的基本知识，最后对数据挖掘的发展趋势进行了介绍。 9 第二章关联规则挖掘理论与算法 关联规则【1 1 l 的概念首先由r a g r a w a l 等人提出，是描述数据库中数据项( 属 性、变量) 之间所存在的( 潜在) 关系的规则。关联规则挖掘是数据挖掘研究的一个 重要分支，关联规则是数据挖掘的众多知识类型中最为典型的一种。目前关联规 则挖掘问题已经引起了数据库、人工智能、统计学、信息检索、可视化及信息科 学等诸多领域的广大学者和研究机构的高度重视，取得了许多研究成果。由于关 联规则形式简洁、易于解释和理解并可以有效地捕捉数据间的重要关系，因此从 大型数据库中挖掘关联规则问题已成为数据挖掘中最成熟、最重要、最活跃的研 究内容。 2 1 关联规则基本理论 关联规则挖掘技术迎合了商品零售决策者的需要，于1 9 9 3 年被a g r a w a l 等人 提出，其最初动机是从事务数据库中发现关于顾客购买行为方面的知识，以指导 商品销售部门进行商品摆放、组合促销和市场规划等工作，挖掘出的知识用关联 规则的形式表达出来。例如关联规则“面包一牛奶【s = 1 ，c = 9 0 ) ”，表示购 买面包的人9 0 也购买了牛奶，同时购买面包和牛奶的销售记录占所有销售纪录 的1 。 2 1 1 关联规则基本概念 设l = i l ，i 2 ，) 是项的集合，d 是数据库事务的集合，其中每一个事务t 是项的集合，使得t c ：i 。每一个事务有一个标识符，称作t i d 。设a 是一个项集， 事务t 包含x 当且仅当a t 。关联规则是形如a - b 的规则，其中a = a 1 a a a m ，b = b 1 a a b n ，a i ，b i 是属性值对。a 属于i ，b 属于i ，并且a n b = 由。 关联规则的兴趣度度量由两个参数来表示，它们分别是支持度和置信度。前 者发现规则的有用性，后者反映规则的确定性。 ( 1 ) 支持度 若x 、b 为项目集，且a n b = 由，蕴涵式a y 称为关联规则，d 中事务包含( a u y ) 的百分比，即概率p ( a u b ) ，称为规则的支持度，记作s u p p o a ( a = b ) 。 s u p p o r t ( a 2 - b ) 2 s u p p o a ( a u y ) = p ( aub ) ( 2 ) 置信度 关联规则a y 的置信度是d 中事务包含a 的事物的同时也包含y 的百分比， 即条件概率p ( a i b ) ，记作：c o r t f i d e n c e a = b 。 。 s u p p o r t ( a u b ) ( c o n f i d e n c ea 2 b ) _ 五瓦忑：百而一1o o = p ( a i b ) 项的集合称为项集。包含k 个项的项集称为k 项集。项集的出现频率是包含 o 项集的事务数，简称为项集的频率、支持计数或计数。如果项集满足最小支持度， 则称它为频繁项集。频繁k - 项集的集合通常记作l k 。 事实上人们一般只对满足一定的支持度和置信度的关联规则感兴趣。因此， 为了发现有意义的关联规则，需要给定两个阀值：最小支持度( m i n s u p ) 和最小置 信度( r a i n c o n f ) 。这些阀值可以由用户或专家设定。满足最小支持度的规则称为频 繁项目集，同时满足最小支持度和最小置信度的规则称作强关联规则。 2 1 2 关联规则挖掘类型 ( i ) 基于规则中处理的变量的类别不同，关联规则可以分为布尔型和数值型。 布尔型关联规则处理的数据都是离散的、种类化的，它显示了这些变量之间的关 系。而数值型关联规则可以和多维关联或多层关联规则结合起来。对数值型字段 进行处理的过程中需将其进行动态的分割，或者直接对原始的数据迸行处理。当 然数值型关联规则中也可以包含布尔型变量。例如： b u y 咩，面包) = i b u y 牛奶) 【s = 2 鼢，c - 8 蝴】 是布尔型关联。 a g e ( x , 3 0 - 4 0 ) = b u y ( x , 。疾病保险) 【s ：5 ，c = 8 0 是数值型关联规则。因为其中语句含了数值型属性a g e 。 ( 2 ) 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。在 单层关联规则中，规则不涉及不同抽象层的项或属性；而在多层关联规则中，规 则涉及不同抽象层的项或属性。例如： “m m 台式机= s o n y 打印机” 是一个细节数据上的单层关联规则。 “台式机= s o n y 打印机” 是一个较高层次和细节层次之间的多层关联规则。 ( 3 ) 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。在 单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品，而在多维 的关联规则中，要处理的数据将会涉及多个维。换成另一句话，单维关联规则是 处理单个属性中的关系；多维关联规则是处理各个不同属性之间的关系。例如： “购买计算机= 购买游戏软件” 是单维关联规则，它只涉及了一个维“购买”。 “年龄 2 5 ，3 5 】八年收入【4 万，5 万】- 购买计算机” 则是多维关联规则，它涉及了三个维“年龄”、“年收入”和“购买”。 2 1 3 挖掘关联规则的基本步骤 挖掘关联规则的步骤大体可以由一个两步的过程来描述： ( 1 ) 找出所有的频繁项集。即找出所有那些支持度大于事先给定的支持度阀值 的项集。 ( 2 ) 在找出的频繁项集的基础上产生强关联规则。即产生那些支持度和置信度 分别大于或等于事先给定的支持度阀值和置信度阀值的关联规则。 在上述两个步骤中，第二个步骤相对要容易一些，因为它只需要在己经找出 的频繁项集的基础上列出所有可能的关联规则