（计算机应用技术专业论文）基于关联规则挖掘的个性化网站设计与实现.pdf

中国民航丈学硕士学位论文 摘要 随着互联网的迅速发展，i n t e r n e t 上的信息呈爆炸式增长，相对于巨大、无序的网 络信息空间，传统网站服务不能满足不同背景、不同目的和不同时期的访问者请求，每 个用户为了找到真正感兴趣的信息需要耗费大量的时间和精力。因此，w e b 个性化成为 了一个研究热点。 w e b 个性化即一个w e b 网站根据发现的用户喜好，为用户定制观看的内容或者提供浏 览建议，它通过以下步骤来实现：首先收集和存储站点访问者的信息，然后对信息做分 析，在分析的基础上在适当的时间将适当的内容提交给每个访问者。 w e b 数据挖掘是实现w e b 个性化的有效途径。论文在研究了w e b 数据挖掘和w e b 个性化 基础上，设计了一个个性化网站，通过利用关联规则算法对w e b 日志和注册用户的信息 进行挖掘产生的规则，实现了以对注册用户进行个性化内容推荐、个性化链接推荐和优 化网站的拓扑结构为目标的一个个性化网站。 主要完成了以下几个方面的工作： 1 设计一个个性化网站，收集了大量的注册用户信息和w e b 日志数据，为挖掘算 法实施做准备。 2 针对收集的数据采用快速a p r i o r i 算法和增量式a p r i o r i 算法进行了挖掘。通 过挖掘发现了用户访问站点中页面之间的一些访问规则，为实现网站个性化做准备。 3 在对挖掘出的规则进行筛选与分析的基础上，将之应用到网站个性化中，实现 了：( 1 ) 为注册用户推荐个性化页面；( 2 ) 优化网站的拓扑结构和建立导航链接。 关键词：个性化网站；w e b 日志挖掘；关联规则；增量式a p r i o r i 算法 中国民航大学硕t 学位论文 a b s t r a c t w i mt h er a p i dd e v e l o p m e n to fi n t e r n e ta n di n f o r m a t i o ne x p l o s i o n t h et r a d i t i o n a lw e b s e r v i c eh a sb e c o m ed i f f i c u l tt os a t i s f yt h er e q u e s to fv i s i t o r sw i mt h ed i f f e r e n tb a c k g r o u n d d i f f e r e n ti n t e n t i o no ri nt h ed i f f e r e n tt i m er e l a t i v et ot h eh u g ea n do u t o f - o r d e rn e t w o r k i n f o r m m i o ns p a c e s i tt a k e sv i s i t o r sal o to f t i m ea n de n e r g yt of i n do u tt h ei n f o r m a t i o nw h i c h i n t e r e s t e dt h e m t h e r e f o r e ，w e bp e r s o n a l i z a t i o nb e c o m e sah o ts p o ti nt h er e s e a r c h w e bp e r s o n a l i z a t i o nm e a n st h a taw e bs i t ec a l lc u s t o m i z eb r o w s i n gc o n t e n to rg i v e b r o w s i n gs u g g e s t i o nf o ru s e r sd y n a m i c a l l ya c c o r d i n gt ot h e i rb r o w s i n gf a v o r s i ti sr e a l i z e d b ys o m es t e p sa sf o l l o w s ：f i r s t l yt oc o l l e c ta n ds t o r et h ev i s i t o r s i n f o r m a t i o n ；s e c o n d l yt o a n a l y s et h ei n f o r m a t i o n ；l a s tt os u b m i tr e l e v a n tc o n t e n t t oe v e r yv i s i t o ra ta na p p r o p r i a t et i m e b a s e do nt h ea n a l y s i s w e bd a t am i n i n gi sa ne f f e c t i v ea p p r o a c ht or e a l i z ew e bp e r s o n a l i z a f i o n t 圭l i sp a p e r d e s i g n e dap e r s o n a l i z e dw e bs i t em o d e lo nt h er e s e a r c ho fw e bd a t am i n i n ga n dw e b p e r s o n a l i z a t i o nd e s i g n i tu s e st h er u l e sw h i c ha r eg e n e r a t e db ym i n i n gt h ew e bl o ga n d i n f o r m a t i o no fr e g i s t e r e du s e r st or e a l i z eap e r s o n a l i z e dw e b s i t e ，w h i c hp u r p o s ei st og u i d e r e g i s t e r e du s e r st ot h ep e r s o n a l i z e dc o n t e n ta n dr e l e v a n tl i n ka n dt oo p t i m i z et h et o p o l o g y s t r u c t u r eo f t h ew e b s i t e n em a i nw o r ko f t h i sp a p e ri n c l u d e st h r e ep a r t s ： 1 t od e s i g na n dr e a l i z eap e r s o n a l i z e dw e b s i t e c o l l e c t i n gam a s so fr e g i s t e r e du s e r s i n f o r m a t i o na n dw e bl o g i ti sr e a d yf o rr e a l i z i n gt h em i n i n ga l g o r i t h m 2 u s i n gq u i c ka p r i o r ia l g o r i t h ma n di n c r e m e n ta p r i o r ia l g o r i t h mt om i n et h ed a t a c o l l e c t e d ，t of i n dt h ea s s o c i a t i o no ft h ew e b sv i s i t e db yu s e r sa n dp r e p a r et or e a l i z et h e p e r s o n a l i z e dw e b s i t e 3 a p p l y i n gt h er u l e s w h i c ha r ef i l t e r e da n da n a l y z e dt ot h ee n t i r ew e b s i t e p e r s o n a l i z a t i o n t or e a l i z e ：( i ) r e c o m m e n d i n gp e r s o n a l i z e dw e bt ot h er e g i s t e r e du s e r s ；( 2 ) o p t i m i z i n gt h et o p o l o g ys t r u c t u r eo f w e b s i t ea n dc r e a t i n gt h en a v i g a t i o nl i n k s k e yw o r d s ：p e r s o n a l i z e dw e b s i t e ；w e bl o gm i n i n g ；a s s o c i a t i o nr u l e s ；i n c r e m e n ta p n o r i a l g o r i t h m 中国民航大学学位论文独创性声明 本人声明所甓交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所 知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得中国民航大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名： 蠢l l ：掏日期：坳王1 7 中国民航大学学位论文使用授权声明 中国民航大学、中国科学技术信息研究所、国家图二挣馆有权保留本人所送交学位论文的复印件 和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内 容相一致除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全 部或部分内容。论文的公布( 包括刊登) 授权中国民航大学研究生部办理。 研究生签名： 蠢l i ，蛏 导师签名日期：金f 中国民航大学硕士学位论文 1 1 研究背景和意义 第一章绪论 自2 0 世纪9 0 年代初互联网开始发展，在近2 0 年间已经发展成为人们获取信息的一个 重要途径。现今已经是一个拥有数亿用户，数十亿页面的巨大信息空间，同时成为我们 经济、社会、文化、教育以及娱乐等许多方面的重要组成部分，是我们工作和生活中不 可缺少的部分。 互联网上的信息资源是大量的、多种多样的并且是不断更新的，但是针对一个用户 来说互联网上众多复杂的信息中只有很少一部分对其来说是感兴趣的，大部分是无用 的。所以随着i n t e r n e t 信息继续增长，人们就必须花费大量的时间去搜索、浏览自己需 要的信息，从而找到自己真正感兴趣的信息是一个既浪费时间又浪费精力的过程，以在 互联网上搜索需要的信息为例，当用户输入要搜索的关键词后，搜索后返回的结果往往 包含了大量与用户兴趣不相关的甚至是过时的信息。然而在这种情况下一般的网站没有 考虑用户的差异，使得每个用户面对同样的信息空间，所以这种用户寻找信息的方式己 经越来越难以适应迅速增长的i n t e r n e t 信息资源。 因此从网站管理者角度来说要考虑怎样使用户从网站中有效快速的获得所需的信 息，改进网站的组织结构和服务，发现潜在的用户群体等问题；从用户角度来说用户需 要一种能够根据用户的自身的特点自动组织和调整信息的服务模式来适应用户的需要， 可以快速、有效的访问w e b 上的资源，缩短查找信息的时间，浏览更多用户感兴趣的信 息等这些问题就成为了现在急需解决的问题。已经有很多人提出了使用w e b 个性化方法 来解决当前的问题，w e b 个性化就是为特定的用户指定特定的w e b 内容和应用，b p w e b 内 容开发人员基于某些条件为特定的个人或用户组提供感兴趣的信息或应用；是用来帮助 用户在大量的信息中寻找针对当前用户最感兴趣的内容。w e b 个性化已经被电子商务网 站、电子图书馆等众多领域所接受，并成为了他们的一个重要功能，它提高了访问效率， 对于不同层次、不同爱好和使用目的的浏览用户提供个性化的信息服务。 使w e b 站点个性化现在有很多人提出了很多种方法，其中对用户兴趣的提供主要是 来自于对用户历史行为的分析，通过分析用户的历史数据，生成同当前用户的行为最相 近的一些信息，并把这些信息当成是用户最感兴趣的项推荐给用户。w e b 务器每天产 生大量的日志，其中蕴涵了有关用户在网站上的行为的丰富数据，分析这些数据能够发 现有意义的隐藏的规则，但是虽然w e b h 臣务器日志记录了作为分析依据的用户访问数据， 但日志记录的庞大使得直接人工分析这些原始数据是很困难的。可以借助数据挖掘技 术，将之运用至u w e b 数据中，就形成了w e b 数据挖掘。w e b 数据挖掘是将对这些数据进行 整理和分析，以数据挖掘技术应用于大规模w e b 数据，发现有效的、新颖的、潜在有用 中国民航大学硕士学位论文 的，以及最终可理解的模式规则的过程，从而充分了解客户的兴趣爱好，设计满足不同 用户群体需要的个性化网站，因此应用w e b 数据挖掘技术实现w e b 个性化是一个重要的研 究领域。 1 2 国内外发展现状 1 2 1w e b 个性化研究发展现状 w e b 个性化是随着i n t e r n e t 信息增长而出现的必然结果。因此，w e b 个性化无论在理 论上还是实践中都受到极大重视，目前，国外己推出了多个实现初步w e b 个性化的原型 系统，下面介绍几个有代表性的例子【l 】： 美国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 s i t ei n f o r m a t i o nf i l t e r ) 系统，该系统包括对各种l o g 文件的数据预处理、应用序列模式分析、网页及用户聚类 分析以及关联规则挖掘等方法实现的模式发现，应用信息过滤、o l a p 及可视化等技术实 现的模式分析等，并实现了一个集w e b 内容挖掘和w e b 使用挖掘结果于一体的个性化推荐 功能的系统睇j 。 德国柏林h u m b o l d t 大学研制的w u m ( w e bu t i l i z a t i o nm i n e r ) 是一个s e q u e n c em i n e r ， 主要目的是分析网站中使用者的浏览行为，它可以支援任何型态的日志纪录，并可以针 对特定的使用者，发现不相连事件的关系和模型。其提供的整合工具包含了日志的准备， 查询，以及视觉化的工具，特别是它的挖掘查询语言m i n t 支持模式描述的标准规范，可 视化机制在路径模式显示中具有突出的特点，可以很方便的知道网站是如何被浏览的【引。 雅虎公司推出的m yy a h o o ! ( m y y a h o o c o m ) 网站，允许用户选择所希望查看的主题 以及主题中特定的栏目，并且可指定展示顺序，为自己构造出专用的网页，此后系统能 够进行内容自动更新维护1 4 j 。 i b m t j w a t s o n 研究中心开发的智能推荐分析系统( i n t e l l i g e n tr e c o m m e n d a t i o n a n a l y z e r - - i r a ) 是集内容过滤和协作过滤于一体的个性化电子商务推荐原型系统。它 具有多个推荐引擎，以进行不同产品推销。每个引擎使用不同方法处理不同产品需求【5 1 。 美国n e tp e r c e o t i o n 公司开发的产品n e tp e r c e r p t i o n s 采用了一个叫做“实时建议” 的技术：让使用该产品的网站能根据用户以往浏览行为，在其他用户中找出与他有相似 浏览行为的用户，根据这些用户的浏览行为预测该用户以后的浏览行为，从而为用户提 供个性化的浏览建议。该技术利用了网站用户浏览行为的相似性，其预测准确性较高并 且它是实时运行的，因此随着浏览量的增加，其预测的准确性将愈来愈高【6 1 。 我国的网站( 如新浪网，网易等) 也开始推出w e b 个性化服务，有很多已应用的原型 系统，例如：四川大学与香港城市大学联合开发的个性化远程教学原型系统e t e a c h e r 7 l ， 广东工业大学开发的水暖器材个性化定制原型系统【8 】等。 2 中国民航大学硕士学位论文 1 2 2w e b 数据挖掘在w e b 个性化中的发展现状 通过w e b 数据挖掘方法，可以获得应用于w e b 个性化的相关信息，能够在准确获得用 户信息的基础上，为用户提供个性化服务，典型的应用如下【1 j ： w e b w a c h e r ：用户通过在浏览器中键入一个描述自己兴趣的主题词来进入它的主 页，它能帮助用户在网上导航，同时通过为用户选择链路或站点跟踪学习，改善导航的 质量【们。 s i t e h e l p e r ：通过分析每个用户的网页访问情况，了解用户的爱好，并从用户浏览 时间较长的网页中抽取出相应关键字，汇总后提交给用户，获得反馈后，再向用户推荐 网站中其他类似或相关网页【1 0 】。 e g l u e ：后台发现模式存于规则库，前台匹配部分采用动态用户配置和缓冲机制进 行规则搜索，减少在线开销【】。 s p e e d t r a c e r ：从日志文件中重建u s e rt r a v e r s a lp a t h ，然后识别出u s e rs e s s i o n ； 在此基础上，利用数据挖掘算法发现m o s tc o m m o nt r a v e r s a lp a t h 和f r e q u e n t l yv i s i t e d p a g eg r o u p ，从而提供个性化服列1 2 1 。 在国内，中科院的个性化智能信息提取系纠”】是基于用户兴趣库生成推荐：上海交 大a i w s l l 4 l 是基于w e b 日志生成推荐；一些以搜索引擎为主的网站，例如淘宝网，易趣网 等是提供个性化搜索的网站。 1 3 论文研究内容 主要研究的是个性化网站的设计与实现，即首先收集大量的注册用户的信息和w e b 日志数据，针对挖掘算法的特点对这些数据进行预处理；然后对预处理后的数据应用快 速a p r i o r i 算法和增量式a p r i o r i 算法进行挖掘，挖掘出用户访问站点中页面之间的一些 访问的规则；最后根据网站拓扑结构筛选和分析规则，在此基础上将筛选后的规则应用 到网站个性化中，实现了：1 为注册用户推荐个性化页面；2 优化网站的拓扑结构和建 立导航链接。 1 4 论文组织结构 全文共分六章。 第一章为绪论。主要介绍本论文的研究背景、国内外研究现状，并介绍本文所做的 工作及论文的研究内容和组织结构； 第二章为w e b 个性化及w e b 数据挖掘。本章主要研究了w e b 个性化的三种形式，系 统的体系结构及关键技术；数据挖掘技术的一些基本概念、分类、任务以及功能和结果 评价；w e b 数据挖掘技术的定义、过程与分类；关联规则和w e b 日志挖掘理论。 中国民航丈学硕士学位论文 第三章为个性化网站的设计。本章介绍了个性化网站拟实现的目标，体系结构，实 现步骤，其中实现步骤分为数据预处理模块，数据挖掘模块，推荐模块，以及实验数据 的准备工作。 第四章为数据预处理和数据挖掘模块的实现。对收集到的实验数据进行预处理，针 对预处理后的数据采用快速a p r i o r i 算法和增量式a p r i o r i 算法进行挖掘。通过挖掘发 现了用户访问站点中页面之间的些访问规则，为实现网站个性化做准备。 第五章为推荐模块的实现。根据网站的拓扑结构对挖掘出的规则筛选与分析，并将 其应用到个性化网站中，实现了：1 为注册用户推荐个性化页面；2 优化网站的拓扑结 构和建立导航链接。 第六章为总结。总结了论文所做的工作，并对进一步研究工作进行了分析和展望。 4 中国民航大学硕t 学位论文 2 1w e b 个性化 第二章w e b 个性化及w e b 数据挖掘 2 1 1w e b 个性化的定义 w e b 个性化是指分析用户行为与其他从w e b 文本、标题、结构、内容和用户描述收集 得到的信息之间的相关性，从而获取一定知识，并利用这些知识制定满足不同用户的站 点的过程【”】。 w e b 个性化的目的是在用户没有明确表示的情况下，提供他们想要的信息。也就是 说w e b 个性化是向用户主动提供信息，优化网站结构，能够根据用户的特点组织和调整 信息的服务模式。 2 1 2w 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 信息的效率。个性化信息检索是指根据用户的兴趣和特点 进行检索，返回与用户需求相关的检索结果，与传统的信息检索相比增加了学习更新 用户模型、优化查询和结果优化三个模块，并且在检索的同时考虑了用户的差异，所以 个性化信息检索可以提供更高的检索质量。 中国民航大学硕士学位论文 2 i 3w e b 个性化的逻辑结构 w e b 个性化逻辑结构【1 6 1 如图2 一l 。主要分为三个步骤：1 收集用户信息；2 根据用户 信息对用户进行建模；3 在构建的用户模型的基础上提供个性化的服务策略和服务内 容。 用 户 信 息 图2 一lw e b 个性化的逻辑结构 i 用户信息收集 用户信息收集模块是一种w e b 个性化系统的基础模块。用户在访问w e b 站点过程中产 生很多种信息：用户输入搜索引擎的查询关键字；w e b 服务器日志；用户手工输入的其 它信息等。根据收集的信息种类不同，用户信息收集模块采用的收集方法也不相同。若 收集服务器日志则需要在服务器端获取服务器日志文件。若要收集用户浏览的页面和浏 览行为，则既可以在客户端获得，也可以在服务器端从用户的访问记录中获得。 2 用户建模 用户建模是指从有关用户兴趣和行为的信息中归纳出可计算的用户模型的过程。可 计算性是用户模型的基本要求，在个性化服务系统中的用户模型不是针对用户个体的一 般性描述，而是一种面向算法的、具有特定数据结构的形式化的用户描述。 用户建模是w e b 个性化的基础和核心。无论何种形式的个性化服务，都需要首先建 立对用户的描述，然后才能据此提供针对不同用户的个性化服务。根据建模过程中用户 的参与程度，用户建模技术可以分为用户手工定制建模、示例建模和自动用户建模。 ( 1 ) 用户手工定制建模是指用户模型由用户自己手工输入或选择的用户建模方法。 如用户自己输入感兴趣的关键词列表或选择感兴趣的栏目等。 ( 2 ) 示例用户建模是指由用户提供与自己兴趣相关的示例及其类别属性来建立用户 模型的建模方法。由于用户对自己的兴趣和偏好等最有发言权，因此由用户提供的有关 自己兴趣的示例最能集中、准确的反应用户的兴趣和偏好等特点。 ( 3 ) 自动用户建模是指根据用户的浏览内容和浏览行为自动构建用户模型、建模过 程无须用户主动提供信息的建模方法。 自动用户建模实际上是改进了示例用户建模方法中的示例获取途径，将其转化为无 6 中国民航大学硕仁学位论文 须用户提供的自动示例获取方法。w e b 日志挖掘是一条实现自动用户建模的途径。自动 用户建模虽然存在着容易引入噪声，不利于构建高质量的用户模型的缺点，但是，自动 用户建模无需用户主动地提供信息，不会对用户造成干扰，有利于提高个性化服务的易 用性，促进个性化服务的快速发展。 综合考虑上述介绍的自动用户建模的特点，本文在实现个性化网站中采用的是w e b 日志挖掘技术，因此在用户建模阶段使用的是自动用户建模方式。 3 个性化服务模块 个性化服务模块根据用户模型向用户提供相应的服务策略和服务内容，它负责提供 具体的个性化服务如个性化推荐、个性化信息检索、个性化网站等。由于服务形式的不 同，个性化服务模块的功能也不相同。 2 1 4w e b 个性化的物理结构 在w e b 个性化系统的实现中，用户信息收集模块、用户建模模块和个性化服务模块 可以分别存在于客户端、代理端或服务器端。 1 客户端w e b 个性化系统的实现结构：用户信息的收集、用户建模和个性化服务均 在客户端实现。由于用户的信息就在本地收集和处理，因而不但能够获取丰富准确的用 户信息以构建高质量的用户模型，而且可以有效地保护用户的隐私，但缺点是不能借鉴 其他用户信息以实现合作式的个性化服务。 2 代理端w e b 个性化系统的实现结构：用户信息的收集、用户建模和个性化服务均 在代理端实现。由于用户的信息需要传给代理端然后进行用户建模，因而对用户的隐私 可能造成侵犯，其优点是可以在被代理的用户群中实现合作式的个性化服务。 3 服务器w e b 端个性化系统的实现结构：用户信息的收集、用户建模和个性化服务 均在服务器端实现。由于用户的信息在非本地的服务器端处理，因而同样有可能侵犯用 户的隐私，其优点是可以实现合作式个性化服务，还可以实现个性化网站。 4 客户端服务器端w e b 个性化系统的实现结构：用户信息的收集在客户端实现，用 户建模和个性化服务在服务器端实现。由于用户信息是在客户端收集，因而能够获得丰 富准确的用户信息，缺点是需要传输用户信息，而且也容易造成对用户隐私的侵犯。但 由于个性化服务是在服务器端实现，因而可以实现合作式的个性化服务。 5 另一种客户端服务器端w e b 个性化系统的实现结构：与4 中所描述的不同的是， 用户信息的收集和用户建模均在客户端实现，只有个性化服务在服务器端实现。由于用 户信息的收集和用户建模是在客户端收集，因而能够收集到丰富、准确的信息构建用户 模型，缺点是需要传输用户模型，也容易造成对用户隐私的侵犯。但由于个性化服务是 在服务器端实现，因而同样可以实现合作式的个性化服务。 7 中国民航大学硕上学位论文 2 2 数据挖掘 2 2 1 数据挖掘概念和过程 数据挖掘是从大型数据集( 可能是不完全的、有噪声的、不确定性的、各种存储形 式的) 中，挖掘隐含在其中的、人们事先不知道的、对决策有用的知识的过程【l ”。这个 定义包含数据源必须是真实的、大量的、含噪声的；发现的是用户感兴趣的知识；发现 的知识是可接受、可理解、可运用的，所有发现的知识都是相对的，是有特定前提和约 束条件、面向特定领域的，同时还要能够易于被用户理解，最好能用自然语言表达发现 结果，因此数据挖掘研究成果很讲究实际。数据挖掘所依赖的数据来源多种多样，可以 是常用的关系数据库、事务数据库、文本数据库、多媒体数据库等，主要取决于用户的 目的及所处的领域。 数据挖掘全过程描述如图2 2 所示。 瓤据犀 ： l ：一上 图2 - 2 数据挖掘过程 由上图可见，数据挖掘作为知识发现的过程主要分为：数据准备、数据挖掘、模式 评估和知识表达。发现知识的过程可以描述为这四个阶段的反复过程。 l _ 数据准备 数据准备阶段又由一些子阶段所构成：数据清洗目的是去除噪声或无关的数据；数 据集成其作用就是将多个数据源中的相关数据可以归并在一起。数据转换就是将数据转 换为易于进行数据挖掘的数据存储形式。 2 数据挖掘 数据挖掘阶段是知识发现过程中的核心阶段。在这个阶段，采用若干智能的方法去 挖掘数据模式或规律知识。 3 模式评估 其作用就是根据一定的评估标准从挖掘结果中筛选出有意义的模式知识。 中国民航丈学硕上学位论文 4 知识表达 就是利用可视化和知识表达技术向用户展示所挖掘出的有意义的知识。 2 2 2 数据挖掘的分类 从不同的角度看，数据挖掘有几种分类方法：根据所挖掘的知识进行分类；根据挖 掘的数据库的种类进行分类。 1 根据发现知识的种类分类： 概念描述知识挖掘，对比概念描述知识挖掘，关联知识挖掘，分类知识挖掘，聚类 知识挖掘，异类知识挖掘，趋势与演化分析知识挖掘，另外，还可以根据所挖掘知识的 抽象水平和细度对数据挖掘进行划分，就有广义( g e n e r a l i z e d ) 知识( 更抽象知识) 、 基本层次( p r i m i t i v e l e v e l ) 知识、多层次知识( 多个抽象水平) 的数据挖掘。 2 根据挖掘数据库的类型分类： 数据挖掘基于的数据库有：关系型( r e l a t i o n a l ) 、事务型( t r a n s a c t i o n a l ) 、面向对 象型( o b j e c t e d o r i e n t e d ) 、主动型( a c t i v e ) 、空间型( s p a t i a l ) 、文本型( t e x t ) 、多 媒体( m u l t i m e d i a ) 、异质( h e t e r o g e n e r o u s ) 数据库等等。 2 2 3 主要数据挖掘方法 人工神经网络：它从结构上模仿生物神经网络，是一种通过训练来学习的非线性预 测模型。可以完成分类、聚类、特征挖掘等多种数据挖掘任务。 决策树：用树型结构来表示决策集合，这些决策集合通过对数据集的分类产生规则。 典型的决策树方法有分类回归树。 遗传算法：是一种新的优化技术，基于生物进化的概念设计了一系列的过程来达到 优化的目的。这些过程有基因组合、交叉、变异和自然选择。为了应用遗传算法，需要 把数据挖掘任务表达为一种搜索问题而发挥遗传算法的优化搜索能力。 最邻近技术：这种技术通过k 个与之最相近的历史记录的组合来辨认新的纪录。也 称k 一最邻近方法。这种技术可以用作聚类、偏差分析等数据挖掘任务。 规则归纳：通过统计方法归纳、提取有价值的i f t h e n 规则。规则归纳的技术在数 据挖掘中被广泛使用，例如关联规则挖掘。 可视化：采用直观的图形方式将信息模式、数据的关联或趋势呈现给决策者，决策 者可以通过可视化技术交互式的分析数据关系。 2 2 4 数据挖掘结果评价 一个数据挖掘系统在完成一个( 组) 挖掘算法之后，常常会获得成千上万的模式或 规则。关联规则挖掘就是一个典型的例子，关联规则算法的执行结果，即使是对一个规 9 中国民航大学硕士学位论文 模较小的数据库( 几万条交易事务记录) ，也会得到数千条关联规则。显然，在这数千 条规则中，只有一小部分是有实际应用价值的。那么如何对数据挖掘步骤所获得的挖掘 结果进行有效地评估，以便最终能获得有实用价值的模式就显得尤为重要了。 评估一个模式( 知识) 是否有意义通常依据以下四条标准【l 柳：1 易于用户理解；2 对新数据或测试数据能够确定有效程度：3 具有潜在价值；4 新奇的。通过这四条标准 确定下来的一条有价值的模式就是知识。 此外，还有一些评价模式价值的客观标准。这些标准是基于所挖掘出模式的结构或 统计特征。例如，对于关联规则的一个客观评价标准就是支持度( s u p p o r t ) ，它表示满 足响应关联规则的事务记录占总记录数的比率。 尽管客观评价方法能够帮助识别一些有意义的模式知识，但也仍然需要结合一些主 观评价措施方可有效反映用户的需求和兴趣。例如，商场主管对描述常在商场购买商品 的顾客的特征模型很感兴趣，而对商场雇员的表现特征模型却兴趣不大。再者许多根据 客观评价标准是有价值的模式知识却只是普通的常识知识( 无实际价值) 。主观价值评 估标准是建立在用户对数据的信念基础上，这些评估标准基于所发现的模式是否是意外 的或与用户信念相悖，或能够提供决策支持而确定的。而意料之中的模式是有价值的则 是指它能够帮助确认用户想要认可的一个假设。 评估所挖掘模式的趣味性标准对于有效挖掘出具有应用价值的模式知识是十分重 要的。这些标准可以直接帮助指导挖掘算法获取有实际应用价值的模式知识，以及有效 摒弃无意义的格式、更为重要的是这些模式评估标准将积极指导整个知识发现过程，通 过及时消除无价值的搜索路径，提高挖掘的有效性。 2 3 关联规则 2 3 1 关联规则的基本概念和问题描述 关联规则是表示数据库中组对象之间某种关联关系的规则。自1 9 9 3 年 r a g r a w a l1 1 9 l 首先提出关联规则概念以来，关联规则挖掘便迅速受到数据挖掘领域专家 的广泛关注。关联规则挖掘的对象是事务数据库( t r a n s a c t i o n a ld a t a b a s e ) 。关联规 则挖掘的一个典型应用是购物篮分析( b a s k e ta n a l y s i s ) ，在超市购物篮分析中可以认 为每个事务表示一个顾客的购买行为，而事务对应的项目表示顾客一次性购买的商品， 该过程通过发现顾客放入其购物篮中不同商品之间的联系，从而分析顾客的购买习惯， 例如“8 0 的顾客在购买电脑的同时也会购买耳麦”，这种关联发现可以帮助零售商制定 营销策略，比如，超市经理可以将电脑和耳麦放在一起，以便在销售电脑的同时刺激耳 麦的销售。关联规则挖掘还广泛应用于商品目录设计、网络入侵检测、生物序列检测等 中。 a g r a w a l 等【1 w 人首先定义了在事务数据库中挖掘关联规则的问题，描述如下： 1 0 中国民航大学硕士学位论文 设i = i 1 ，i 2 ，i 。 是由m 个不同的项目组成的集合，给定一个事务数据库t d b ， 其中的每一个事务t 是i 中一组项目的集合，即t _ i ，t 有一个唯一的标识符t i d 。 定义2 1假设项目集x 是i 中项目的集合，如果x 包含k 个项目，那么称其为 k 一项目集。 定义2 2如果项目集x c _ t 。则我们称事务t 支持x ，项目集x 在事务数据库t d b 中的支持度( s u p p o r t ) 为事务数据库t d b 中包含x 的事务数量与事务数据库t d b 的总 事务数量之比。 定义2 3如果项目集x 在事务数据库t d b 中的支持度不小于用户事先给定的最小 支持度阈值( m i n s u p ) ，那么项目集x 称为频繁项目集( 大项目集) ；反之称之为非频 繁项目集( 小项目集) 。 定义2 4一条关联规则就是形如：x j y 的蕴涵式，其中x _ i ，y i ，x f l y = 中，x 称为规则的前件，y 称为规则的后件。支持度s 即事务数据库t d b 中至少有s 的事务包 含x u y ，表示出来就是s = s u p ( x u y ) ；置信度c 即事务数据库t d b 包含x 的事务中至少 有c 的事务同时也包含y ，用公式表示出来就是c = c o n f = s u p ( x u y ) s u p ( x ) 。支持度是 表示规则在数据库中出现的频度，置信度是表示规则的强度。 最小支持度闽值( m i n s u p ) 表示项目集在统计意义上的最低主要性，最小置信度 阈值( m i n c o n f ) 表示规则的最低可靠性。同时满足最小支持度阈值( m i n s u p ) 和最小置 信度阂值( m i n c o n f ) 的关联规则称为强关联规则。关联规则的挖掘问题就是在事务数据 库t d b 中找出满足用户事先给定的最小支持度和最小置信度的强关联规则。项目集在事 务数据库t d b 中的出现频率是包含项目集的事务数，简记为项目集的频率、支持计数或 计数。如果项目集的出现频率大于或等于m i n s u p 与t d b 中事务总数的乘积，则我们说 项目集满足最小支持度m i n _ s u p 。频繁k 一项目集的集合，通常记作l k 。 关联规则挖掘可以分解为下列两个子问题 2 0 l ： 1 找出所有频繁项目集：这些项目集出现的频率满足最小支持度m i ns u p ，即这些 项目集在事务数据库t d b 中的频繁性不小于最小支持度； 2 由频繁项目集产生强关联规则：即这些规则必须满足最小置信m i nc o n f 。一般 的想法是，如果说a b c d 和a b 是频繁项目集，那么我们能计算比率r = s u p ( a b c d ) s u p ( a b ) ，从而确定是否有规则。当且仅当r m i n c o n f 时才有此规则。注意此规则有最 小支持度，因为a b c d 是大的。 当然，除了这两个度量标准以外也可以使用附加的度量，例如兴趣度( i n t e r e s t i n g ) 度量、提升度( 1 i f t ) 度量等。在这两个子问题中，第二个子问题最容易，找出所有频 繁项目集以后，产生用户感兴趣的强关联规则是很自然的事情。目前大多数的研究工作 主要集中在第一个子问题上，关联规则挖掘的总体性能主要由它得到解决的好坏来决 定。 中国民航大学硕士学位论文 2 3 2 经典的频繁项目集生成算法 1 9 9 4 年r a g l a w a l 等人提出了a p r i o r i 算法【1 9 l 。a p r i o r i 算法是一种最有影响的挖 掘布尔关联规则频繁项目集的算法，其核心是使用候选项目集找频繁目项集。a p r i o r i 算法使用一种称作逐层搜索的迭代方法，k 一项集用于搜索( k + 1 ) 一项集。首先，找出频繁 卜项集的集合，该集合记作l ，l 。用于找频繁2 一项集的集合l ，l 2 用于找l 3 ，如此下去， 直到不能找到频繁k 一项集。找每个h 需要一次数据库扫描。 为了提高频繁项集逐层产生的效率，一种称作a p r i o r i 性质的重要性质用于压缩搜 索空间。 a p r i o r i 性质：频繁项集的所有非空子集都必须也是频繁的。a p r i o r i 性质基于如 下观察：根据定义，如果项目集i 不满足最小支持度阈值s ，则i 不是频繁的，即p ( i ) s 。 如果项a 添加到i ，则结果项集( 即i u a ) 不可能比i 更频繁出现。因此，i u a 也不是 频繁的，即p ( i u a ) s ，此时可利用原有的频繁项目集去掉不满足要求的频繁项目集。 ( 2 ) s s ，情况比较复杂，原有的非频繁项目集可能获得支持，针对此类问题，提出 了i u a 算法【2 3 1 。 i u a ( i n c r e m e n t a lu p d a t i n ga l g o r i t h m ) 算法将具有新的最小支持度s 的所有频繁k 项集 t 分成了三个互相不相交的子集：l k l ( 每个频繁项集x 属于l k ) 、l k 2 ( 每个频繁项集x 属于不在l k 的项集新产生的乓) 和l k 3 ( 每个频繁项集x 属于l k 和乓的拼接) 。同时与 之相对应的候选k 项集分别记为c k l ，c k 2 ，c k 3 。对于c k l 和c i 【2 直接利用a p r i o r i 算法中的 a p r i o r i g e n i 累i 数生成。对于c 提出了一个新的候选k 项集生成函数i u a _ g e n ( k 1 ) 来生 成。 该函数分为两步，首先将l k l 中的频繁j ( 1 j k 1 ) 项集和l k 2 中的频繁k j 项集进 行简单的拼接，然后修剪掉那些根本不可能出现在l k 3 中的项集。这样生成c k 后，对整个 数据库进行扫描，便可得到t 。当频繁项集的分布在新旧最小支持度相差不大时，该 算法可以获得较高的性能加速比。 由于i u a 算法连接过程复杂度较高，人们提出了一些改进方法，来提高候选集生成 的效率。 2 4w e b 数据挖掘 2 4 1w e b 数据挖掘定义 w e b 数据挖掘是在1 9 9 6 年首次提出的概念。m p e r k o w i t z 和0 e t z i o n i 认为1 2 4 1 ： w e bm i n i n gi st h eu s eo fd a t am i n i n gt e c h n i q u e st oa u t o m a t i c a l l yd i s c o v e ra n d e x t r a c ti n f o r m a t i o nf r o mw e bd o c u m e n t sa n ds e r v i c e s ( w e b 数据挖掘就是利用数 据挖掘技术从w e b 文档和服务中自动发现和抽取信息) 。基于w e b 的数据挖掘( w e b m i n i n g ) 正是从万维网( w o r l dw i d ew 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