（计算机应用技术专业论文）基于频繁偏爱度的使用模式挖掘系统的分析和设计.pdf

江苏大学硕士学位论文 摘要 目前，i n t e m e t 正以惊人的速度在飞速发展，其应用已经渗透到各行各业， 越来越多的公司、机构、个人在i n t e r a c t 上发布和查找消息。i n t e m e t 上不仅充满 了文本、音频和视频等多媒体信息，还包括页面间的链接，用户对页面的访问信 息等。人们迫切的希望通过数据挖掘技术来发现隐藏在原始信息中的有用知识， 然而由于i n t e m e t 自身的一些特点，很难直接使用数据挖掘技术来发现有用知识。 人们提出将数据挖掘技术和i n t e m e t 的特点相结合，即通过w e b 数据挖掘来 发现隐藏在海量信息中的有用知识，从而可以改进w e b 服务器性能、个性 化用户访问和商业智能等。 本文首先介绍了w e b 数据挖掘产生的一些背景知识、w e b 数据挖掘的概念 及其分类等，重点介绍了w e b 使用信息挖掘的相关知识，并深入分析了挖掘算 法一关联规则挖掘算法，从算法的定义、执行步骤、执行效率到最后算法的分析。 接着，提出一个使用信息挖掘的框架。该框架共分为三个模块，分别是数据 预处理模块、使用模式挖掘模块、模式分析和可视化模块。在数据预处理模块中， 本文提出一种新型的数据源来代替原有的服务器日志，不仅可以很好的记录用户 的使用信息，而且处理步骤简单、快速。在使用模式挖掘模块中，本文针对i n t e m e t 的特点对关联规则算法提出了一些改进措施，使得挖掘出来的模式真正代表了大 多数用户的频繁偏爱使用模式。在模式分析和可视化模块中介绍了目前一些常见 的方法，重点介绍了o l a p 和可视化技术。 最后，介绍了使用模式的一些应用。使用模式被广泛应用在用户个性化访问、 改进服务器性能和商业智能等，然而针对目前i n t e r a c t 的安全问题，本文提出将 使用信息挖掘应用在用户访问入侵检测中，通过挖掘出来的入侵模式对用户访问 进行入侵检测，改善i n t e m e t 的安全。 关键词：使用信息挖掘；数据挖掘；关联规则；频繁偏爱度；x m l ；入侵检测； 江苏大学硕士学位论文 a b s t r a c t i n t e r n e th a sb e e nd e v e l o p i n gq u i c k l ya tp r e s e n t ，a n dh a sb e e na p p l i e dt oa l lk i n d s o fi n d u s t r i e s m o r ea n dm o r ec o m p a n i e s 、o r g a n i z a t i o n sa n dp e o p l ep u b l i s ha n ds e a r c h i n f o r m a t i o no nt h ei n t e r n e t i n t e r n e tn o to n l yi sf u l lo ft e x t 、a u d i o 、v i d e oa n do t h e r m u l t i m e d i ai n f o r m a t i o nb u ta l s oi n c l u d e sl i n k i n gb e t w e e np a g e s ，u s a g ew h i l ep e o p l e s u r fo nt h en e t p e o p l ew i s ht od i s c o v e r ys o m eu s e f u lk n o w l e d g ew h i c hb i d e di nt h e r u d ei n f o r m a t i o nb yd a t am i n i n gt e c h n o l o g y ，h o w e v e r ，i t sh a r dt od ot h i sb e c a u s eo f i t so w nf e a t u r e s p e o p l es u g g e s tt od i s c o v e r yu s e f u lk n o w l e d g eh i d e di nt h eh u g ei n f o r m a t i o nb y w e bd a t am i n i n g ，c o m b i n gd a t am i n i n gt e c h n o l o g ya n dt h ef e a t u r e so fi n t e m e t ，t o i m p r o v et h ep e r f o r m a n c eo fs e r v e r , p e r s o n a l i z a t i o nu s e ra c c e s s i n ga n db u s i n e s s i n t e l l i g e n c ea n ds oo n f i r s t ，t h i sp a p e ri n t r o d u c e ss o m et h e o r yk n o w l e d g e ，s u c ha st h eb a c k g r o u n d k n o w l e d g eo fd a t am i n i n g ，t h ec o n c e p t i o no fw e bd a t am i n i n ga n dt h ec l a s s i f yo f w e bd a t am i n i n g ，e m p h a s i z i n go nt h ek n o w l e d g eo fw e bu s a g em i n i n g ，a n d a n a l y z i n gt h em i n i n ga r i t h m e t i ci nd e t a i l ，f r o mt h ed e f i n i t i o no fa r i t h m e t i c ，e x e c u t i o n s t e p s ，e x e c u t i o ne f f i c i e n c ya n dt h ea n a l y s i so f a r i t h m e t i ca tl a s t n e x t ，w ep u tf o r w a r daf r a m e w o r ko fu s a g em i n i n g t h ef r a m e w o r kh a st h r e e m o d u l e s ；t h e ya r ed a t ap r e t r e a t m e n t ，u s a g em i n i n g ，p a t t e r n sa n a l y s i sa n dv i s i b i l i t y i n t h em o d u l eo fd a t ap r e t r e a t m e n tw ep u tf o r w a r dan e wk i n do fd a t as o u r c ei n s t e a do f f o r m e rs e r v e rl o g ，n o to n l yl o ga s e r su s a g er o u n d l yb u ta l s oe x e c u t es i m p l ea n df a s t i nt h em o d u l eo fu s a g em i n i n gw ei m p r o v et h ec l a s s i c a la s s o c i a t i o nr u l e sa c c o r d i n g t h ef e a t u r e so fi n t e r n e t s ot h ep a t t e r n sm i n e df r o mu s a g ec o u l dd e l e g a t em o s to f u s e r s f r e q u e n ta n dp r e f e r r e dp a t t e r n sr e a l l y i nt h em o d u l eo fp a t t e r n sa n a l y s i sa n d v i s i b i l i t yw ei n t r o d u c es o m ep o p u l a rt e c h n i q u e ，e m p h a s i z i n go l a pa n dv i s u a l i z i n g a tl a s t , w ei n t r o d u c es o m ea p p l i c a t i o n so fp a t t e r n s t h ep a t t e r n sh a v eb e e n a p p l i e dt op e r s o n a l i z a t i o nu s e ra c c e s s i n g 、i m p r o v et h ef e a t u r e so fs e r v e ra n d b u s i n e s s i n t e l l i g e n c ea n ds oo n h o w e v e r , w es u g g e s ta p p l y i n gt h ep a t t e r n st o i n t r u s i o n d e t e c t i o n , t od e t e c tu s e r s v i s i t i n gb yt h ep a t t e r n sm i n e d ，s oi tw i l lh e l pt oi m p r o v et h e s e c u r i t yo f i n t e m e t k e yw o r d s ：u s a g em i n i n g ；d a t am i n i n g ；a s s o c i a t i o nr u l e s ；f r e q u e n c ya n d p r e f e r e n c e ；x m l ：i n t r u s i o nd e t e c t i o n ； i i 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 保密口，在年解密后适用本授权书。 不保密d 学位论文作者签名：羔进 多，e l 年、v 月、，日 指导教师签名身h 以 年( “月【7 日 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已注明引用的内容以外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：晏盟 日期：2 。矗年l 瑚t 2 - 日 江苏大学硕士学位论文 第一章绪论 1 1 课题的研究背景、目的和意义 数据挖掘是从k d d ( 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 ) 中引伸出来的，被 认为是k d d 过程中的一个特定步骤，它采用专门的算法从数据中抽取有用知识。 从2 0 世纪8 0 年代末开始到现在，经过近2 0 年的研究，数据挖掘继承和发展了 相关基础学科，如机器学习、统计学、神经网络等，探索出许多独具特色的理论 体系。常用的数据挖掘方法有关联规则、分类方法、聚类方法、时间序列和序列 模式挖掘等方法。通过将数据挖掘方法和特定领域的应用环境相结合，数据挖掘 已经广泛应用于各种商务管理、生产控制、市场分析和科学探索等领域【”。 然而近年来，尤其是9 0 年代末期，i n t e r a c t 技术迅速发展，许多公司都把自 己信息放到网上，w e b 不仅包含原有的新闻、广告等文本信息，还包含丰富、 动态的超链接信息，以及w e b 页面的使用信息。人们迫切的希望通过数据挖掘 技术来发现隐藏在其中的有用知识，但由于w e b 信息特别庞大、复杂、动态变 化、以及信息中的“垃圾”非常多等特点，很难直接用数据挖掘技术进行发掘。 为了解决w e b 下的数据挖掘问题，人们提出w e b 数据挖掘的概念一一将传 统的数据挖掘技术和i n t e r a c t 的特点相结合，从而能够在w e b 下有效地发现隐藏 在原始信息中的有用知识。 w e b 数据挖掘按照挖掘对象的不同一般分为三类：w e b 内容挖掘( w e b c o n t e n t 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 u s a g em i n i n g ) 。研究w e b 使用信息挖掘具有十分重要的理论意义和现实应用价 值，主要用途有 2 1 ： 1 ) 从大量的使用信息中发现用户感兴趣的使用模式。 2 ) 将w e b 上的丰富信息转变成有用的知识。 3 ) 针对不同的用户进行个性化推荐服务。 因此本文主要研究了w e b 使用信息挖掘方面的内容，并且分析和设计了一 个完整的w e b 使用信息挖掘系统。通过w e b 使用信息挖掘，我们可以从海量的 w e b 页面访问信息中发现感兴趣的知识。 江苏大学硕士学位论文 1 2 本文的主要研究内容 本文从挖掘数据源、关联规则挖掘算法、以及最后使用模式的分析和应用进 行了研究，并设计了一个完整的使用信息挖掘系统。 1 ) 挖掘数据源 传统的数据挖掘源在进行数据预处理时，要对数据源进行数据集成、数据清 洗、用户识别、会话识别、路径补全和事务识别等处理步骤，工作量大、预处理 后的数据精度不高、冗余数据多。本文提出一种全新的x m l 格式的数据挖掘源， 此数据源不仅可以完整的记录用户访问系统的信息，而且以x m l 的格式存储信 息，使用信息可以很容易的转化到数据库或数据仓库中，有效的减少了数据预处 理的工作量，提高数据处理的精度和速度，使得挖掘出精确的、有用的使用模式 成为可能。 2 ) 关联规则挖掘算法 本文采用了关联规则的经典算法一a p r i o r i 算法，考虑到w e b 下用户访问的特 点，提出将用户访问频度和页面停留时间相结合作为用户的频繁偏爱度，并对 a p r i o r i 算法提出一些改进措施，以提高a p r i o r i 算法的效率。 3 ) 使用模式的应用 挖掘出来的使用模式被广泛应用在改进w e b 服务器性能、商业智能和用户 个性化访问等方面。本文不仅介绍了使用模式在改进服务器性能和个性化用户访 问中的应用，还针对w e b 上日益严重的安全问题，提出通过挖掘异常使用模式来 构建用户访问入侵库，对用户的访问进行入侵监测。 1 3 本文的组织结构 全文共分五章。前两章主要是一些理论知识介绍，后三章是本文的重点。 第一章：主要介绍了本课题的研究背景、目的、以及研究的现实意义，并简 单介绍了本文的主要创新点。 第二章：先介绍了w e b 数据挖掘的一些背景知识和分类等内容；然后介绍 了数据挖掘算法方面的理论知识，重点介绍了关联规则算法的定义、算法步骤以 及如何提高和改善关联规则挖掘的效果。 第三章：此章是本文的重点，分析和设计了一个完整的使用信息挖掘系统， 从数据源预处理到最后的使用模式分析和可视化等，并对传统的系统构架提出了 自己的一些创新点，最后通过具体的实例进行了分析和验证。 2 江苏大学硕士学位论文 第四章：介绍了使用模式的应用。如何把挖掘出来的使用模式应用在改进 w e b 服务器性能、个性化用户访问和用户访问入侵检测这三方面。重点阐述了 使用模式在用户访问入侵检测方面的应用，试图在改善w e b 安全方面做点工作， 最后介绍了挖掘系统在一个实际项目中的应用。 第五章：对本文的研究进行了归纳和总结，并介绍了下一步的研究工作。 江苏大学硕士学位论文 第二章相关概念 2 1 w e b 数据挖掘的产生背景 目前w e b 是一个巨大的、分布广泛的和全球性的信息服务中心，它涉及新 闻、广告、消费信息、金融管理、教育、政府、电子商务和许多其他服务信息， 此外还包含了丰富和动态的超链接信息，以及w e b 页面的访问和使用信息。w e b 设计人员竭尽全力优化自己的站点以吸引和留住更多的用户，但是这必须依靠对 网站信息的充分了解。一方面，网站设计者希望可以根据用户的访问兴趣、访问 频度和访问时间等动态的调整页面结构，改进服务，开展有针对性的电子商务以 更好地满足访问者的要求：另一方面，访问者希望用最简洁的方式得到最精确的 信息，希望得到个性化的服务。然而基于以下的原因，对w e b 资源直接进行数 据挖掘还具有极大的挑战性 3 1 。 对有效的数据库和数据仓库而言，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 上的信息对具体的用户来说只有很少一部分是相关的或有用的。据 说9 9 的w e b 信息对于9 9 的用户是无用的，一个人只关心很少一部分信 息，用户对w e b 所包含的其余信息是不感兴趣的，甚至会被不感兴趣的 信息所淹没。 解决以上问题的最好方法就是将数据挖掘技术和w e b 特有的性质结合起来， 使用w e b 数据挖掘方法从大量的w e b 页面、页面间超链接以及用户对页面的访问 记录中挖掘出有用的知识。 4 江苏大学硕士学位论文 2 2 w e b 数据挖掘的分类 w e b 数据挖掘是指从w w w 的资源和行为中抽取感兴趣的、有用的和隐含的 知识。一般地，根据其挖掘对象的不同分为：w 曲内容挖掘( w e bc o n t e n tm i n i n g ) 、 w 曲结构挖掘( w e bs t r u c t u r em i n i n g ) n i w e b 吏n n 息挖掘( w e bu s a g em i n i n g ) 【4 】。 如图2 1 是w e b 数据挖掘的分类图。 2 2 1w e b 内容挖掘 图2 1w e b 数据挖掘分类图 w e b 内容挖掘是从页面文档或文档描述中抽取知识的过程。w e b 文档内容 的挖掘，基于概念索引的资源发现，以及基于代理的技术部属于这一类。目前 w e b 内容挖掘的主要方法包括【1 1 ： 1 ) 改进传统的w w w 搜索引擎，包括l y c o s ，v i s t a ，w e b c r a w l e r ，a l i w e b ， m e t a c r a w e r 。 2 ) 在w w w 上智能地提取信息的搜索工具，如i n t e l l i g e n tw e ba g e n t ， i n f o r m a t i o nf i l t e r i n g c a t e g o r i z a t i o n ，p e r s o n a l i z e dw e ba g e n t s 。 3 ) 数据库方法：把半结构化的w e b 信息重构，使得w e b 信息更结构化，然 后就可以使用标准化的数据库查询机制和数据挖掘方法进行分析。 4 ) 对页面中的文本进行文本挖掘、对页面中的多媒体信息进行多媒体信息 挖掘，具体方法有页面内容摘要、分类、聚类以及关联规则发现等。 2 2 2w e b 结构挖掘 w e b 结构挖掘是从w w w 的组织结构和链接关系中挖掘知识的过程。由于 页面之间的互连，有用的知识不仅包含在页面的内容中，而且还包含在页面的链 5 江苏大学硕士学位论文 接结构中。利用这些信息可以对页面进行排序，发现重要的页面，主要有 p a g e r a n k 和h u b a u t h o r i t y 两种算法。 2 2 。2 1 p a g e r a n k 算法 在搜索引擎中存储了数以亿计的页面，需要寻找一种好的利用链接结构来评 价页面重要性的方法。p a g e r a n k 方法是目前搜索引擎和w e b 挖掘中流行的技术， 由b r i n 和p a g e 于1 9 9 8 年提出。 p a g e r a n k 算法的基本思想如下： 1 ) 一个页面被多次引用，则这个页面可能是重要的。 2 ) 一个页面尽管没有被多次引用，但被一个重要的页面引用，则这个页面 也可能是重要的。 3 ) 一个页面的重要性被均分并传递到它所引用的页面。 2 2 2 2h u b a u t h o r i t y 算法 h u b a u t h o r i t y 算法是由k l e i n b e r g 于1 9 9 8 年提出。在w w w 出现之前，“引 用分析”在信息获取领域已经进行了长时间的研究。g a r f i e l d si m p a c tf a c t o r ( 1 9 7 2 ) 对杂志的“引用”采用了数值化的评价方法，p i n s k i 和n a r i n ( 1 9 7 6 ) 对此提出了重要 的改进，他们观察到并不是所有的“引用”都有相同的重要性，一个有影响的杂志 是递归地被其他有影响的杂志大量“引用”。 与杂志的引用率不同，w e b 链接结构具有特殊的特征，在w e b 中为了导航 等所建立的超链接不具有影响力。系统设计者基于商业竞争地考虑，很少会指向 其竞争对手的页面，为此人们提出另一种重要的w e b 页面，称为h u b 页面。 一个h u b 页面是指一个或多个w e b 页面，它提供了指向权威页面的链接集 合。h u b 页面本身可能并不突出，或者说可能没有几个链接指向他们。但是， h u b 页面却提供了指向某个公共话题最为突出的站点链接，h u b 页面起到了隐含 说明某公共话题权威页面的作用。通常，好的h u b 页面是指向许多好的权威页 面；好的权威页面是由许多好的h u b 页面所指向。这种h u b 与a u t h o r i t y 之间的 相互作用，可用于权威页面的挖掘、高质量w e b 结构和资源的自动发现【i 】。 2 2 3w e b 使用信息挖掘 w e b 使用信息挖掘是通过挖掘w e b 日志文件来发现用户访问的使用模式。通 过分析和探究隐藏在w e b 日志文件中的规律，可以识别电子商务的潜在客户，增 强对最终用户的因特网信息服务的质量和交付，改进w e b 服务器系统的性能6 】【刀。 6 江苏大学硕士学位论文 由于各种服务器的日志文件格式不同、日志文件本身数据冗余、包含噪音以 及日志文件中的信息并不完全对挖掘使用模式有用，因此需要对其日志文件进行 数据集成、数据清洗、会话识别、路径补全和事务识别等预处理操作( 1 】1 9 1 。 数据集成：记录用户使用信息的日志文件可能不仅仅分布在一台服务器上， 在数据预处理之前需要把记录用户使用信息的所有数据进行集成，以便进一步的 数据清洗。 数据清洗：日志文件中记录的信息并不全是用户请求的信息，同时记录的还 有随用户请求一起下载到客户端的图像文件、语音和视频文件、可执行的c g i 文件、含区域坐标的图像映射文件以及h t m l 文件等，这些信息都是服务器自 动推给客户端的，并不是用户直接的请求，不包含用户的使用信息，对挖掘用户 使用模式没有帮助，可以将其清洗掉。 会话识别：用户会话是指用户对服务器的一次有效访问，通过其连续请求的 页面可以获得其在网站中的访问行为和浏览兴趣。最简单的方法是采用超时估计 的方法，即如果页面间的请求时间间隔超过给定值，则认为用户已开始了一次新 的会话。通常这一时间间隔为3 0 分钟。 路径补全：由于存在防火墙、本地缓存和代理服务器等原因，用户通过浏览 器的“后退”操作使得一些重要的访问没有被记录在日志文件中，路径补全的目 的就是通过启发式方法将这些遗漏的请求补全到用户会话文件中。一般通过结合 站点的拓扑结构、引用日志和时间信息进行补全路径【l o l 。 事务识别：事务识别是建立在用户会话识别的基础上，目的是依据数据挖掘 任务的需求将事务进行分割或合并处理，使其适合于数据挖掘需求的分析。 记录用户使用信息的日志文件在进行数据预处理之后，可以利用成熟的数据 挖掘技术进行挖掘，如关联规则、序列挖掘等，从而理解用户的行为，改进w e b 页面的设计和w e b 应用程序，发现潜在的电子商务客户。 从w e b 日志数据中挖掘出的使用模式是否有用，还需要最终用户和挖掘领 域专家共同的分析，并且以一种简单和容易理解的方式展现给使用者。如果没有 合适的技术和工具来辅助分析人员，采用各种挖掘技术挖掘出来的使用模式将得 不到很好的应用。通过关联规则挖掘出来的强关联模式并不一定都是值得分析和 使用的，有些使用模式已经为人们所知，而挖掘的目的是为了发现一些不为人所 知的模式，越意外越有用；有些使用模式虽然是强关联模式，即满足最小支持度 和最小置信度，但并不是人们所频繁偏爱的使用模式，详见2 3 6 。因此在挖掘 出用户使用模式之后还要对使用模式进行分析。常用的分析技术有知识查询机 制、o l a p 技术和可视化技术。 7 江苏大学硕士学位论文 2 3 关联规则介绍 关联规则挖掘是为了发现大量数据项集之间有趣的关联或相关联系，是数据 挖掘中最活跃的研究方法之一。随着大量数据不停地收集和存储，许多业界人士 对于从他们的数据库中挖掘出关联规则越来越感兴趣。从大量商务事务记录中发 现有趣的关联关系，可以帮助许多商务决策地制定，如分类设计、交叉购物和贱 卖分析等。最著名的关联规则算法是由a g r a w a l 和s r i k a n t 提出的a p r i o r i 算法， 此外还有f p 一举o 、 ，m 、d h p 、s t e m 、a i s 等算法【l “。 2 3 1 关联规则的相关定义 关联规则是形如a j b 的蕴涵表达式，其中4 和口是不相关的项集，即 a 1 7 b = a 。 令，= ，毛，) 是所有项的集合，而r = ，f 2 ，“) 是所有事务的集合。每 个事务t 包含的项集都是，的子集a 项集x 的支持度计数可以表示为 o ( x ) 刊 f f i x t ，n l ，h 表示集合中元素的个数。 支持度s u p p o r t ( ajb ) 确定规则可以用于给定数据集的频繁程度，形式化表 示为：s u p p o r t ( a j b ) = o ( a u b ) o ( r ) 。 置信度c o n f i d e n c e ( a j b ) 确定b 在包含4 事务中出现的频繁程度，形式化表 示为：c o a t i d e n c e ( a 回= o ( a u b ) o ( a ) 。 同时满足最小支持度和最小置信度的关联规则称为强关联规则。通常我们说 的关联规则就是强关联规则。 2 3 2 关联规则的分类 根据关联规则处理的值的类别，关联规则可以分为布尔型关联规则和数值型 关联规则。布尔型关联规则处理的值是离散的、种类化的，它显示了变量间的关 系；而数值型关联规则可以和多维关联或多层关联结合起来，对数值型字段进行 处理，将其进行动态地分割，或者直接对原始的数据进行处理，当然数值型关联 规则中也可以包含种类变量( 1 i 】。 江苏大学硕士学位论文 根据规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。在单 层的关联规则中，所有的变量都没有考虑现实的数据具有多个不同层次，而在多 层的关联规则中，对数据的多层性进行了充分地考虑。 根据规则中涉及数据的维数。关联规则可以分为单维关联规则和多维关联规 则。单维关联规则处理单个维属性中的一些关系；多维关联规则处理不同维属性 之间的某些关系。 2 3 3 关联规则的一般挖掘步骤 关联规则挖掘一般分为以下两个步骤： 1 ) 发现频繁项目集 通过用户给定的最小支持度，寻找所有的频繁项目集，即满足支持度不小于 最小支持度m i n s u p 的所有子集。事实上，这些频繁项目集可能具有包含关系。 一般地，我们只关心那些不被其他频繁项目集所包含的所谓最大频繁项目集的集 合，发现所有的频繁项目集是形成关联规则的基础。 2 ) 生成关联规则 通过给定的最小可信度m i n c o f ，在每个最大频繁项目集中，寻找置信度不 小于最小置信度m i n c o f 的频繁项目集，此频繁项目集就是关联规则。 这两步中，第二步是在第一步的基础上进行的，工作量比较小。挖掘工作的 总体性能由第一步决定。 2 3 4 由a p r i o r i 挖掘算法产生关联规则 关联规则挖掘算法的关键是快速、高效地发现频繁项集。a p d o r i 算法是一 种最有影响的挖掘布尔关联规则频繁项集的算法，它使用一种称为逐层搜索的迭 代方法，首先找出频繁l 一项集的集合厶，厶用于找出频繁2 项集的集合厶，而厶 用于找出厶，如此下去，直到不能找到频繁k 一项集。 a p r i o r i 性质：i ) 若a 是频繁集，则a 的任意子集也是频繁集。 2 ) 若a 是非频繁集，则a 的任何超集也是非频繁集。 利用a p r i 耐算法生成关联规则的形式化描述如下【5 】： 1 ) 迭代所有1 项集，生成候选i 一项集c 1 。扫描所有事务，计算c 1 中每一项 9 江苏大学硕士学位论文 的支持度。 2 ) 根据最小支持度m i n s u p ，生成频繁项集厶。 3 ) 为生成频繁项目集厶，首先要生成页面结点集合 f p ) 。，集合中的元素是 由频繁项集厶一。中所有的页面结点元素组成，然后按照顺序生成候选频繁项集 g 由 即 集合生成q 共有) 4 种方式。 4 ) 计算候选频繁项集e 中每一项的支持度，如果存在某一项的支持度大于 最小支持度m i n s u p ，则转到步骤5 ) ，否则转到步骤6 ) 。 5 ) 对频繁项集厶中的每一项计算其置信度，如果其置信度大于最小置信度 m i n c o f ，则此项为f 项使用模式。f 自增1 ，转到步骤3 ) 。 6 ) 所有使用模式已经全部生成，算法结束。 2 3 5 提高a p r i o r i 算法的有效性 a p r i o r i 作为经典的频繁项目集生成算法，在数据挖掘中具有里程碑的地位， 但随着研究的深入，它的缺点也暴露出来。a p r i o r i 有两个致命的性能瓶颈【1 】： 1 ) 多次扫描事务数据库，需要很大的i o 负载。 对每次k 循环，候选集q 中的每个元素都必须扫描数据库一次来验证其是 否加入丘。如一个频繁项目集包含1 0 项，那么就至少需要扫描事务数据库l o 遍。 2 ) 可能产生庞大的候选集。 由厶一产生k 项候选集g 是呈指数增长的，如此庞大的候选集对时间和存储 空间都是严重的浪费。 a 皿o r i 算法效率的高低直接决定着关联规则发现使用模式的效率的高低， 因此有必要研究如何提高h p r i o r i 算法的效率。 ( 1 ) 基于散列技术的方法( 散列项计数) 。散列的技术可以用于压缩k - 项集g ( k 1 ) 。例如，当扫描数据库中的每个事务，由c l 中的候选1 项集产生 频繁l 一项集厶时，可以对每个事务产生所有的2 项集，将它们散列到散列表结 1 0 江苏大学硕士学位论文 构的不同桶中，并增加对应的桶计数。在散列表中对应的桶计数低于支持度阈值 的2 项集不可能是频繁2 项集，因而应该从候选项集中将其删除。 ( 2 ) 事务压缩的方法( 压缩进一步迭代扫描的事务数) 。不包括任何k 项集 的事务不可能包含任何( k + 1 ) 项集。因此，这种事务在其后可以加上标记或 删除，因为产生j 项集( j k ) 时不再需要它们。 ( 3 ) 划分的方法( 为找候选项集划分数据) 。可以使用划分技术，它只需要 两次扫描数据库，以挖掘频繁项集，如图2 - 2 。 圈 - - - - - _ i - 第一遍第二遍 网 l 繁项集l i _ j 图2 2 通过划分的方法挖掘 ( 4 ) 基于数据分割的方法。a p r i o r i 算法在执行过程中是先生成候选集，后 剪枝，但生成的候选集并不都是有效的，有些候选集根本就不是事务数据集中的 项目集。把数据分割技术应用到关联规则中，可以改善关联规则挖掘在大容量数 据集中的适应性。它的基本思想是：首先把大容量数据库从逻辑上分成几个互不 相交的块，每块应用a p r i o r i 挖掘算法生成局部的频繁项目集，通过测试他们的 支持度来得到最终的全局频繁项目集。通过数据分割的方法可以合理利用存储空 间和支持并行挖掘算法。 合理利用存储空间：无法将大容量数据集一次导入内存，数据分割为块内数 据一次性导入内存提供机会，因而提高了对大容量数据集的挖掘效率。 支持并行挖掘算法：由于引入数据分割技术，每个分块的局部频繁项目集是 独立生成的，因此可以把分块内的局部频繁项目集的生成工作分配给不同的处理 器完成，提供了开发并行挖掘算法的良好机制。 ( 5 ) 选样的方法( 在给定数据的一个子集中挖掘) 。在给定数据库d 中选取 随机样本s ，在s 而不是在数据库d 中搜索频繁项集。当效率最为重要时，如计算 密集的应用必须在频繁度不同的数据上运行，选样方法特别适合。 江苏大学硕士学位论文 2 3 6 改善关联规则的挖掘结果 关联规则挖掘普遍使用“支持度一可信度”的度量机制。一般讲，不加额外的 限制条件会产生大量的规则。这些规则并不一定全是有用或用户感兴趣的。如在 用户的访问记录中共有1 0 0 0 条记录，有6 0 0 个用户访问了a 页面，7 5 0 个用户 访问了b 页面，4 0 0 个用户既访问了a 页面也访问了b 页面，设最小支持度为 3 0 ，最小置信度为6 0 【9 j 。 关联规则a j b 的支持度为s u p p ( a j b ) = 等= 罴_ 4 0 关联删a j b 的置信度为町( 4 j b ) = 等= 器= 6 6 根据关联规则得知，此访问模式的支持度和置信度都已满足最小支持度和最 小置信度，应该是一个强关联模式，但实际上根据已知条件访问b 页面的可能 性达到7 0 ，在访问过页面a 之后再访问b 反而使b 页面的访问几率下降，说 明访问页面a 与页面b 是负相关的，访问其中一个页面后会减少访问另一个页 面的可能性，因此虽然该关联规则满足强关联的定义，但不是一个用户偏爱的使 用模式。 页面访问之间的关系可以分为三种：正相关、负相关和无关。 设页面a 的访问概率为p ( 爿) ，b 的访问概率为p ( b ) ，先访问a 后访问b 的概 率为p ( a jb ) ，如果p ( a j 印 p ( a ) + p ( b ) ，则页面a 与b 是正相关；如果 p ( a b ) p ( a ) + p ( b ) ，则页面a 与b 是负相关；如果p ( ajb ) = p 似) + p ( b ) ， 则页面a 与b 是无关。使用模式挖掘的目的就是要发现正相关的强关联规则。 衡量关联规则挖掘结果的有效性应该从多种角度来综合考虑“。 1 ) 准确性：挖掘出的规则必须反映数据的实际情况。尽管规则不可能1 0 0 被使用，但是必须要在一定的可信度范围内。 2 ) 实用型：挖掘出的规则必须是简洁可用的。 3 ) 新颖性：挖掘出的关联规则可以为用户提供新的有价值的信息。如果它们 是用户事先就知道的，那么这样的规则即使再正确也毫无价值。 改善关联规则挖掘质量是一件很困难的工作。必须采用事先预防、过程控制 以及事后评估等多种方法，其中使用合适的约束，让用户主动参与挖掘工作是解 1 2 江苏大学硕士学位论文 决问题的关键。一般可以从用户主观和系统客观两个层面上来改善关联规则的挖 掘质量 1 l 【5 1 。 1 、用户主观层面 事实上，一个规则的有用与否最终取决于用户的感觉，只有用户可以决定规 则的有效性、可行性，所以要将用户的需求和系统更加紧密地结合起来。约束数 据挖掘可以为用户参与知识发现工作提供一种有效的机制。 用户可以在不同的层面、不同的阶段、使用不同的方法来主观设定约束条件。 例如，可以把约束作为参数和算法相结合，也可以以交互的方式进行不同地尝试； 可以根据事先设定的挖掘目标，还可以作为评估规则的依据；可以在数据预处理 阶段用来减少处理数量，也可以对知识形式进行约束以减少尝试路径。常用的约 束有以下几种。 知识类型的约束 对于不同的商业应用问题，特定的知识类型可能更能反映问题。例如，如果 一个商业企业希望根据客户的特点进行有针对性的销售，那么使用分类或聚类形 式可以帮助用户形成客户群。用户可以设定明确的挖掘知识模式，减少不必要的 模式探索，增强挖掘的使用性。 数据的约束 对数据约束可以起到减少数据挖掘的数据量、提高数据质量等作用。用户可 以指定对哪些数据进行挖掘，通过制定约束把粗糙的、混杂的庞大数据集压缩到 与任务相关的数据集上。在不同的阶段，可以通过数据挖掘语言实施数据约束。 维层次约束 对于一个基于数据仓库或多维数据库的数据挖掘工作来说，不同的维为用户 提供了不同粒度的数据和数据的不同视点，但是，它也给数据挖掘工作带来新的 问题。例如，从不同粒度挖掘出来的知识可能存在冗余问题；由于维数不加限制 可能引起挖掘效率低下等问题。因此，可以限制聚焦的维数或粒度层次，也可以 针对不同的维属性设置约束条件。灵活的利用约束进行多维挖掘是目前比较集中 讨论的问题。 知识内容的约束 可以通过限定要挖掘的知识内容，减少探索的代价和加快知识的形成过程。 针对具体知识类型的约束 不同的知识类型在约束形式和使用上会有所差异，因此开展针对具体的知识 类型进行约束挖掘形式和实现机制的研究是有意义的。 2 、系统客观层面 江苏大学硕士学位论文 通过上面的例子可以分析知道，强关联规则并不一定就是非常精确的。如果 把支持度和置信度设置得足够低，那么将得到两条矛盾的规则；但另一方面，如 果把参数设置得足够高，就可能会遗漏一些重要的规则。总之，没有一对支持度 和置信度的组合可以产生完全正确的关联规则。 通过引入“兴趣度”来修剪无趣的关联规则，即避免生成“错觉”的关联规则。 一般，规则的“兴趣度”是基于统计独立性假设下真正的强度与期望之比，然而在 许多的应用中已经发现，如果只把支持度作为最初项集产生的主要决定因素，那 么支持度设置得低会产生许多无意义的规则，把支持度设置得高会丢失一些重要 的规则。对于前一种情形，计算效率是个问题；而后一种情形则存在有可能丢失 从用户观点来看是有意义的规则。 2 - 。4x i k 技术 以x m l 为基础的新一代的w w w 环境是直接面对w e b 数据的，不仅可以 很好地兼容原有的w e b 应用，而且可以更好地实现w e b 中的信息交换与共享。 l 可看作是一种半结构化的数据模型，可以很容易地将x m l 的文档描述与 关系数据库中的属性一一对应起来，实施精确的查询与模型抽取。 x m l 是由万维网协会( w 3 c ) 设计的一种中介标识语言，可提供描述结构 化资源的格式。总的来说，x m l 是一种中介标识语言，可提供描述结构化资料 的格式，详细来说，x m l 是一种类似于h t m l 、被设计用来描述数据的语言。 x m l 提供了一种独立运行程序的方法来共享数据，它能使计算机通信把i n t e m e t 的功能由信息传递扩大到人类其他多种多样的活动中去。x m l 能增加结构和语 义信息，可使计算机和服务器即时处理多种形式的信息。因此，“l 的扩展功 能不仅能从w e b 服务下载大量的信息，还能大大减少网络业务量。 x m l 具有以下特点： 1 ) 简单。x m l 经过精心设计，整个规范简单明了，它由若干规则组成，这 些规则可用于创建标记语言，并能用一种简明程序处理所有新创建的标记语言。 2 ) 开放。x m l 是从s g m l 派生而来，在市场上有许多成熟的软件可用来 帮助编写、管理等，开放式标准x m l 的基础是经过验证的标准技术，并针对网 络做了最佳优化。 3 ) 高效且可扩充，支持复用文档片断。使用者可以发明和使用自己的标签， 也可与他人共享，可延伸性大，在x m l 中可以定义无限量的一组标注。 4 ) 国际化。标准国际化，且支持世界上大多数文字。这源于统一代码的新 编码标准，这种编码标准支持世界上所有以主要语言编写的混和文本。 1 4 江苏大学硕士学位论文 面向w e b 的数据挖掘是一项复杂的技术，x m l 的出现为解决w e b 数据挖 掘的难题带来了机会。由于x m l 能够把不同来源的结构化的数据很容易的结合 在一起，因而使搜索多样的不兼容的数据库成为可能，从而为解决w e b 数据挖 掘难题带来了希望。同时由于基于x m l 的数据是自我描述的，数据不需要有内 部描述就能被交换和处理。相信随着v i l 作为w e b 上交换数据的一种标准方式 的出现