（计算机软件与理论专业论文）web挖掘与个性化信息服务.pdf

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 i t san e ws u b j e c tt o a p p l y d a t am i n i n gi n t ow e ba n di t w i l la l s oh a v eb r o a d a p p l i c a t i o nv a l u e t h i st h e s i sm a i n l yi n c l u d e df o u rp a r t s ：f i r s t l y , i td i s c u s s e dd a t am i n i n g t e c h n i q u e s e c o n d l y ，i ta n a l y z e da s s o c i a t i o nr u l ea n ds e q u e n c em o d e u s e di nt h ep r o c e s s o fd a t am i n i n ga n dc o m p a r e dt h em a i na l g o r i t h m so f a s s o c i a t i o nr u l ea n ds e q u e n c em o d e 。 t h i r d l y , i ta n a l y z e d t h ea p p l i c a t i o no fd a t am i n i n gi nw e ba n dt h es y s t e mo fw e b m i n i n g f i n a l l y , o n t h eb a s eo fd a t a m i n i n g a n dw e bm i n i n g t e c h n i q u e ，i tb r o u g h t f o r w a r d p e r s o n a li n f o r m a t i o n s e r v i c es y s t e m 。w i t hd a t am i n i n g t e c h n i q u e ss u c h a sa s s o c i a t i o nr u l e t h ei n f o r m a t i o ns e r v i c es y s t e ma n a l y z e ds e v e rl o gf i l ea n dg o tt h eu s e rv i s i t i n gm o d es o t h a ti tc o u l dp r o v i d et h eu s e rr e a l - t i m ep e r s o n a li n f o r m a t i o ns e r v i c ea c c o r d i n gt ot h e c u r r e n ts t a t u so ft h e i ro n g o i n g v i s i t i n ga c t n i t y t h i s t h e s i se n u m e r a t e dt h ep r o b l e m si nt h e p r e p r o c e s s i n go fs e r v e rl o gf i l e s u c ha sd a t ac l e a n i n g ，u s e ri d e n t i f i c a t i o n ，t r a n s a c t i o n i d e n t i f i c a t i o na n dp a t hi d e n t i f i c a t i o na n dc o m eu pw i t hs o l v i n gm e t h o d si n t u r n s o ， t h r o u g ht h er e c o m m e n d i n ge n g i n e ，w ef u l f i l lt h et a s kt op r o v i d et h ep e r s o n a li n f o r m a t i o n s e r v i c e ：t or e c o m m e n dt h ew e b p a g e t ot h eu s e r k e y w o r d s ：d a t a m i n i n g w e b m i n i n g a s s o c i a t i o nr u l e p e r s o n a l i n f o r m a t i o ns e r v i c e 4 w e b 挖掘与个性化信息服务 第一章数据挖掘技术 1 1 数据挖掘技术概述 1 1 1 数据挖掘技术的发展背景 近十几年来，人们利用信息技术生产和搜集数据的能力大幅度提高，千 万个数据库被用于商业管理、政府办公、科学研究和工程开发等等，并且这 一势头仍将继续发展下去。于是，一个新的挑战被提了出来：在这个被称之为 信息爆炸的时代，信息过量几乎成为人人需要面对的问题。如何才能不被信 息的汪洋大海所淹没，从中发现及时有用的知识，提高信息利用率呢? 要想使 数据真正成为一个公司的资源，只有充分利用它为公司自身的业务决策和战 略发展服务才行，否则大量的数据可能成为垃圾，甚至成为包袱。因此，面 对人们被数据淹没却饥饿于知识的挑战，数据挖掘和知识发现( d m k d ) 技术应 运而生，并得以蓬勃发展，越来越显示出其强大的生命力。 数据挖掘技术是人们长期对数据库技术进行研究和开发的结果。起初各 种商业数据是存储在计算机的数据库中的，然后发展到可对数据库进行查询 和访问，进而发展到对数据库的即时遍历。数据挖掘使数据库技术进入了一 个更高级的阶段，它不仅能对过去的数据进行查询秘遍历，并且能够找出数 据之间的潜在联系，从而促进有用信息的产生。现在数据挖掘技术在商业应 用中已经可以马上投入使用，因为对这种技术进行支持的三种基础技术( 海 量数据搜集、强大的多处理器计算机、数据挖掘算法) 已经发展成熟。 f r i e d m a n 列举了激发数据挖掘的开发、应用和研究的兴趣的四个主要的 技术理由：( 1 ) 超大规模数据库的出现，例如商业数据仓库和计算机自动收集 的数据记录；( 2 ) 先进的计算机技术，例如更快和更强大的计算能力和并行体 系结构；( 3 ) 对巨大量数据的快速访问：( 4 ) 对这些数据应用精深的统计方法 计算的能力。 商业数据库现在正以一个空前的速度增长，并且数据仓库正在广泛地应 用于各种行业；对计算机硬件性能越来越高的要求，也可以用现在已经成熟 的并行多处理机的技术来满足；另外数据挖掘算法经过了这l o 多年的发展也 已经成为一种成熟，稳定，且易于理解和操作的技术。 数据挖掘的核心模块技术历经了数十年的发展，其中包括数理统计、人 工智能、机器学习。今天，这些成熟的技术，加上高性能的关系数据库引擎 以及广泛的数据集成，让数据挖掘技术在当前的数据仓库环境中进入了实用 的阶段。 1 。1 。2 数据挖掘的概念和特征 当今数据库的容量已经达到上万亿的水平( t ) l ，0 0 0 ，0 0 0 ，0 0 0 ，0 0 0 个字节。在这些大量数据的背后隐藏了很多具有决策意义的信息，那么，如何 w e b 挖掘与个性化信息服务 得到这些“知识”，成为人们亟待解决的一个问题。 计算机科学的发展为解决这一问题提供了个有力的工具：数据挖掘。 在“数据矿山”中找到蕴藏的“知识金块”，帮助企业减少不必要投资的同时 提高资金回报。数据挖掘给企业带来的潜在的投资回报几乎是无止境的。世 界范围内具有创新性的公司都开始采用数据挖掘技术来判断哪些是他们最有 价值的客户、重新制定他们的产品推广策略( 把产品推广给最需要他们的入) ， 用最小的花费得到最好的销售效果。 数据挖掘( d a t a m i n i n g ) 是一个利用各种分析工具在海量数据中发现模 型和数据间关系的过程，这些模型和关系可以用来做出预测。 数据挖掘的第一步是描述数据一计算统计变量( 比如平均值、均方差 等) ，再用图表或图片直观的表示出来，进而可以看出一些变量之间的相关性 ( 比如有一些值经常同时出现) 。选择正确的数据源对整个数据挖掘项目的成 败至关重要。 单单是数据描述并不能为人们制订行动计划提供足够的依据，必须用历 史数据建立一个预言模型，然后再用另外些数据对这个模型进行测试。一 个好的模型没必要与数据库中的数据1 0 0 的相符，就像城市交通图也不是完 全的实际交通线路的等比例缩小，但这种模型在做决策时却是一个很好的指 南和依据。 最后一步是验证该模型。比如用所有对某产品推广计划做出回应的人的 数据库做了一个模型，来预测什么样的人会对该产品感兴趣。不能在得到这 个模型后就直接利用这个模型做出决策或采取行动，应该更稳妥一点，先对 一小部分客户做一个实际的测试，然后再决定。 从以上可以看出数据挖掘与传统的数据分析( 如查询、报表、联机应用分 析) 的本质区别是数据挖掘是在没有明确假设的前提下去挖掘信息、发现知 识。数据挖掘所得到的信息应具有先前未知、有效和可实用三个特征。 先前未知的信息是指该信息是预先未曾预料到的，即数据挖掘是要发现 那些不能靠直觉发现的信息或知识，甚至是违背直觉的信息或知识，挖掘出的 信息越是出乎意料，就可能越有价值。在商业应用中最典型的例子就是一家 连锁店通过数据挖掘发现了小孩尿布的销售量和啤酒的销售量之间有着：廉入 的联系。 1 1 3 数据挖掘的功能 数据挖掘通过预测未来趋势及行为，做出前瞻性的、基于知识的决策。 数据挖掘的目标是从数据库中发现隐含的、有意义的知识。主要有以下五类 功能。 第一类自动预测趋势和行为 2 w e b 挖掘与个性化信息服务 数据挖掘自动在大型数据库中寻找预测性信息，以往需要进行大量手工 分析的问题如今可以迅速直接由数据本身得出结论。一个典型的例子是市场 预测问题，数据挖掘使用过去有关促销的数据来寻找未来投资中回报最大的 用户，其它可预测的问题包括预报破产以及认定对指定事件最有可能作出反 应的群体。 第二类关联分析 数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个 变量的取值之间存在某种规律性，就称为关联。关联可分为简单关联、时序 关联、因果关联。关联分析的目的是找岿数据库中隐藏的关联网。有时并不 知道数据库中数据的关联函数，即使知道也是不确定的，因此关联分析生成 的规则带有可信度。 第三类聚类 数据库中的记录可被划分为一系列有意义的子集，即聚类。聚类增强了 人们对客观现实的认识，是概念描述和偏差分析的先决条件。聚类技术主要 包括传统的模式识别方法和数学分类学。8 0 年代初，m c h a l s k i 提出了概念聚 类技术，其要点是，在划分对象时不仅考虑对象之间的距离，还要求划分出 的类具有某种内涵描述，从而避免了传统技术的某些片面性。 第四类概念描述 概念描述就是对某类对象的内涵进行描述，并概括这类对象的有关特征。 概念描述分为特征性描述和区别性描述，前者描述某类对象的共同特征，后 者描述不同类对象之间的区别。生成一个类的特征性描述只涉及该类对象中 所有对象的共性。生成区别性描述的方法很多，如决策树方法、遗传算法等。 第五类偏差检测 数据库中的数据常有一些异常记录，从数据库中检测这些偏差很有意义。 偏差包括很多潜在的知识，如分类中的反常实例、不满足规则的特例、观测 结果与模型预测值的偏差、量值随对间的变化等。偏差检测的基本方法是， 寻找观测结果与参照值之间有意义的差别。 1 2 数据挖掘的过程 数据挖掘是指个完整的过程，该过程从大型数据库中挖掘先前未知的 有效的，可实用的信息，并使用这些信息做出决策或丰富知识。 数据挖掘环境可示意如下图： 图1 - 1 数据挖掘环境框图 w e b 挖掘与个性化信息服务 图卜1 描述了数据挖掘环境，数据挖掘工具从数据库中抽取有用的信息， 由可视化工具表达给用户。 数据挖掘过程的各步骤内容如下： 第一步确定业务对象 清晰地定义出业务问题，认清数据挖掘的目的是数据挖掘的重要一步。挖 掘的最后结构是不可预测的，但要探索的问题应是有预见的，为了数据挖掘而 数据挖掘则带有盲目性，是不会成功的。 第二步数据准备 数据的选择：搜索所有与业务对象有关的内部和外部数据信息，并从中选 择出适用于数据挖掘应用的数据。 数据的预处理：研究数据的质量，为迸一步的分析作准备。并确定将要进 行的挖掘操作的类型。 数据的转换：将数据转换成一个分析模型。这个分析模型是针对挖掘算 法建立的。建立一个真正适合挖掘算法的分析模型是数据挖掘成功的关键。 第三步数据挖掘 对所得到的经过转换的数据进行挖掘。除了完善从选择合适的挖掘算法 外，其余一切工作都能自动地完成。 第四步结果分析 解释并评估结果。其使用的分析方法一般应视数据挖掘操作而定，通常会 用到可视化技术。 第五步知识的同化 将分析所得到的知识集成到业务信息系统的组织结构中去。 、7 、 、 酬 一被选择、卜_预处理_被转换、卜 7 的数据1 r l 后的数) 1 7u 前夕1 、， 穆 选择预处理转换挖掘分析和同化 图卜2 数据挖掘过程的步骤 一 图i - 2 描述了数据挖掘的基本过程和主要步骤。 在数据挖掘中被研究的业务对象是整个过程的基础，它驱动了整个数据 挖掘过程，也是检验最后结果和指引分析人员完成数据挖掘的依据和顾问。图 卜2 各步骤是按一定顺序完成的，当然整个过程中还会存在步骤间的反馈。数 4 w e b 挖掘与个性化信息服务 据挖掘的过程并不是自动的，绝大多数的工作需要人工完成。在这些步骤中 6 0 的时间用在数据准备上，这说明了数据挖掘对数据的严格要求，而挖掘工 作仅占总工作量的1 0 。 1 3 数据挖掘的应用 由于数据挖掘带来的显著的经济效益，使数据挖掘越来越普及。它不仅 能用于控制成本，也能给企业带来效益。 很多企业都在利用数据挖掘技术帮助管理客户生命周期的各个阶段，包 括争取新的客户、在已有客户的身上赚更多的钱、和保持住好的客户。如果 靛够确定好的客户的特点，那么就能为客户提供针对性的服务。比如，已经 发现了购买某一商品的客户的特征，那么就可以向那些具有这些特征但还没 有购买此商品的客户推销这个商品；找到流失的客户的特征就可以在那些具 有相似特征的客户还未流失之前进行针对性的弥补，因为保留一个客户要比 争取一个客户便宜的多。 数据挖掘可以应用在各个不同的领域。电讯公司和信用卡公司是用数据 挖掘检测欺诈行为的先行者。保险公司和证券公司也开始采用数据挖掘来减 少欺诈。医疗应用是另一个前景广阔的产业：数据挖掘可以用来预测外科手 术、医疗试验和药物治疗的效果。经销商更多的使用数据挖掘来决定每种商 品在不同地点的库存，通过数据挖掘更灵活的使用促销和优惠卷手段。制药 公司通过挖掘巨大的化学物质和基因对疾病的影响的数据库来判断哪些物质 可能对治疗某种疾病产生效果。 1 4 数据挖掘的局限性 当然，数据挖掘不是万能的，而只是一个工具。它不会坐在你的数据库 上一直监视着数据库，然后当它发现有意义的模型时给你发一封电子邮件。 它仍然需要了解你的业务，理解你的数据，弄清分析方法。数据挖掘只是帮 助商业人士更深入、更容易的分析数据，它无法告诉你某个模型对你的企业 的实际价值。而且数据挖掘中得到的模型必须要在现实生活中进行验证。 数据挖掘中得到的预言模型并不会告诉你一个人为什么会做一件事、采 取某个行动，它只会告诉你他会这样做，为什么则需要人去考虑。比如，数 据挖掘可能会告诉你，如果这个人是男的、年收入在5 万到6 万之间，那么 他可能会买你的商品和服务。你可能会利用这条规则，集中向这类人推销你 的商品而从中获益，但是数据挖掘工具不会告诉你他们为什么会买你的东西， 也不能保证所有符合这条规则的人都会买。 w e b 挖掘与个性化信息服务 为了保证数据挖掘结果的价值，用户必须了解自己的数据，这一点至关 重要。输入数据库中的异常数据、不相关的字段或互相冲突的字段( 比如年 龄和生日不一致) 、数据的编码方式等都会对数据挖掘输出结果的质量产生影 响。虽然一些算法自身会对上面提到的这些问题做一些考虑，但让算法自己 做所有这些决定是不明智的。 数据挖掘不会在缺乏指导的情况下自动地发现模型。用户不能这样对数 据挖掘工具说，“帮我提高直接邮件推销的响应率”，用户应该让数据挖掘工 具找( i ) 对用户的推销回应的人，或( 2 ) 即回应又做了大量订单的人的特征。 在数据挖掘中寻找这两种模型是很不相同的。 虽然数据挖掘工具使用户不必再掌握艰深的统计分析技术，但用户仍然 需要知道所选用的数据挖掘工具是如何工作的，它所采用的算法的原理是什 么。选用的技术和优化方法会对模型的准确度和生成速度产生很大影响。 数据挖掘永远不会替代有经验的商业分析师或者管理人员所起的作用， 它只是提供一个强大的工具。每个成熟的、了解市场的公司都已经具有一些 重要的、能产生高回报的模型，这些模型可能是管理人员花了很长时间，作 了很多调查，甚至是经过很多失误之后得来的。数据挖掘工具要做的就是使 这些模型得到的更容易，更方便，而且有根据。 1 5数据挖掘的现状和未来发展方向 当前，数据挖掘研究方兴未艾，其研究与开发的总体水平相当于数据库 技术在7 0 年代所处的地位，迫切需要类似于关系模式、d b m s 系统和s o l 查 询语言等理论和方法的指导，才能使数据挖掘这项技术的应用得以普遍推广。 预计在未来的一段时间内，数据挖掘的研究还会深入下去，研究焦点可能会 集中到以下几个方面： 发现语言的形式化描述，即研究专门用于知识发现的数据挖掘语言， 也许会像s o l 语言一样走向形式化和标准化； 寻求数据挖掘过程中的可视化方法，使知识发现的过程能够被用户理 解，也便于在知识发现的过程中进行人机交互； 研究在网络环境下的数据挖掘技术( w e bm i n i n g ) ，特别是在因特网 上建立d m 服务器，并且与数据库服务器配合，实现w e bm i n i n g ； 加强对各种非结构化数据的开采( d a t a m i n i n gf o r a u d i o & v i d e o ) ， 如对文本数据、图形数据、视频图像数据、声音数据乃至综合多媒体数据的 开采； w e b 挖掘与个性化信息服务 处理的数据将会涉及到更多的数据类型，这些数据类型或者比较复杂， 或者是结构比较独特。为了处理这些复杂的数据，就需要一些新的和更好的 分析和建立模型的方法，同时还会涉及到为处理这些复杂或独特数据所做的 费时的复杂数据准备的一些工具和软件。 交互式发现： 知识的维护更新。 但是，不管怎样，需求牵引与市场推动是永恒的，数据挖掘将首先满足 信息时代用户的急需，大量的基于数据挖掘的决策支持软件产品将会问世。 只有从数据中有效地提取信息，从信息中及时地发现知识，才能为人类的思 维决策和战略发展服务。 w e b 挖掘与个性化信息服务 第二章关联规则和序列模式 2 1 关联规则概述 关联规则( a s s o c i a t i o nr u l e s ) 是数据挖掘的个非常重要的问题。 关联规则是发现交易数据库中不同商品( 项) 之间的联系，这些规则找 出顾客购买行为模式，如购买了某一商品对购买其他商品的影响。发现这样 的规则可以应用于商品货架设计、货物库存安排以及根据购买模式对用户进 行分类。应用在w w w 上可以发现服务器上请求网页的相关性，用于优化网 站组织，实现网络代理中的预读功能等。 关联规则寻找在同一个事件中出现的不同项的相关性，比如在次购买 活动中所买不同商品的相关性。 关联规则可记为a j b ，a 称为前提和左部( l h s ) ，b 称为后续或右部 ( r h s ) 。如关联规则“买锤子的人也会买钉子”，左部是“买锤子”，右部是 “买钉子”。 要计算包含某个特定项或几个项的事务在数据库中出现的概率只要在数 据库中直接统计即可。某一特定关联( “锤子和钉子”) 在数据库中出现的频 率称为支持度。比如在总共1 0 0 0 个事务中有1 5 个事务同时包含了“锤子和 钉子”，则此关联的支持度为1 5 。非常低的支持度( 比如1 百万个事务中 只有一个) 可能意味着此关联不是很重要。或出现了错误数据( 如，“男性和 怀孕”) 。 要找到有意义的规则，还要考察规则中项及其组合出现的相对频率。当 已有a 时，b 发生的概率是多少? 即概率论中的条件概率。对于上述例子， 也就是问“当一个人已经买了锤子，那他有多大的可能也会买钉子? ”这个 条件概率在数据挖掘中也称为可信度，计算方法是求百分比：( a 与b 同时出 现的频率) ( a 出现的频率) 。 用一个例子更详细的解释这些概念； 总交易笔数( 事务数) ：1 ，0 0 0 包含“锤子”：5 0 包含“钉子”：8 0 包含“钳子”：2 0 包含“锤子”和“钉子”：1 5 包含“钳子”和“钉子”：1 0 包含“锤子”和“钳子”：1 0 包含“锤子”、“钳子”和“钉子”：5 则可以计算出： “锤子和钉子”的支持度= 1 5 ( 1 5 1 。0 0 0 ) “锤子、钉子和钳子”的支持度= 0 5 ( 5 1 0 0 0 ) w e b 挖掘与个性化信息服务 “锤子j 钉子”的可信度= 3 0 ( 1 5 5 0 ) “钉子j 锤子”的可信度= 1 9 ( 1 5 8 0 ) “锤子和钉子钳子”的可信度= 3 3 ( 5 1 1 5 ) “钳子j 锤子和钉子”的可信度= 2 5 ( 5 2 0 ) 可以看到买锤子的人也买钉子的可能性( 3 0 ) 高于买钉子的人要买锤子 的可能性( 1 9 ) 。锤子和钉子关联的支持度已经足够高了，意味着这是一条 有意义的关联规则。 关联规则算法的另一个重要的性质是指定项的概念层次。比如在我们讨 论的锤子和钉子的例子中没有涉及产品的品牌和型号。这一点很重要，如在 “金属制品一 五金工具 钉子 5 号钉子 x x 厂的5 号钉子”的概念层 次上，基于不同的目的，可能需要选择不同的层次。 数据挖掘得到的关联规则并不是真正的规则，他只是对数据库中数据之 间相关性的一种描述。还没有其他数据来验证得到的规则的正确性，也不能 保证利用过去的数据得到的规律在未来新的情况下仍有效。 h g r a w a l 等于1 9 9 3 年首先提出了挖掘顾客交易数据库中项集间的关联规 则问题，以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他 们的工作包括对原有的算法进行优化，如引入随机采样、并行的思想等，以 提高算法挖掘规则的效率：对关联规则的应用进行推广。 最近也有独立于a g r a w a l 的频繁项目集方法的工作，以避免频繁项目集 方法的一些缺陷，探索挖掘关联规则的新方法。同时随着o l a p 技术的成熟和 应用，将o l a p 和关联规则结合也成了一个重要的方向。也有一些工作注重于 对挖掘到的模式的价值进行评估，他们提出的模型建议了一些值褥考虑的研 究方向。 2 2 关联规则的基本概念 设仁以。厶”jl ，是二进制文字的集合，其中的元素称为项( i t e m ) 。 记d 为交易( t r a n s a c t i o n ) t 的集合，这里交易，是项的集合，并且? 三，。 对应每一个交易有唯一的标识，如交易号，记作t i d 。设j 是一个，中项的 集合，如果埏l 那么称交易，包含丘 一个关联规则是形如x y 的蕴涵式，这里x c 五y c e , 并且x r t y = q b 。规 则x j y 在交易数据库d 中的支持度( s u p p o r t ) 是交易集中包含x 和y 的交 易数与所有交易数之比，记为s u p p o r t ( x j y ) ，即 s u p p o r t ( x j y ) = l ( t ：x w y c t ，t e d l l d l 规则x j y 在交易集中的可信度( c o n f i d e n o e ) 是指包含x 和y 的交易数 与包含x 的交易数之比，记为c o n f i d e n c e ( x y ) ，即 c o n f i d e n c e ( x = y ) = i ( t ：x w y c t ，t e d f l t ：x c t ，t d ) i 给定一个交易集d ，挖掘关联规则问题就是产生支持度和可信度分别大于用 户给定的最小支持度( m i n s u p p ) 和最小可信度( m i n e o n f ) 的关联规则 w e b 挖掘与个性化信息服务 2 3 关联规则的种类 我们将关联规则按不同的标准进行分类： 1 )基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。 布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之 间的关系；而数值型关联规则可以和多维关联或多层关联规则结合起来，对 数值型字段进行处理，将其进行动态的分割，或者直接对原始的数据进行处 理，当然数值型关联规则中也可以包含种类变量。 例如：性别= “女”= 职业= “秘书”，是布尔型关联规则：性别= “女” = a v g ( 收入) = 2 3 0 0 ，涉及的收入是数值类型，所以是一个数值型关联规则。 2 ) 基于规则中数据的抽象层次，可分为单层关联规则和多层关联规则。 在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个 不同的层次的；而在多层的关联规则中，对数据的多层性已经进行了充分的 考虑。 例如：i b m 台式机= s o n y 打印机，是一个细节数据上的单层关联规则； 台式机= s o n y 打印机，是一个较高层次和细节层次之间的多层关联规则。 3 ) 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。 在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品； 而在多维的关联规则中，要处理的数据将会涉及多个维。换成另一句话，单 维关联规则是处理单个属性中的一些关系；多维关联规则是处理各个属性之 间的某些关系。 例如：啤酒= 尿布，这条规则只涉及到用户的购买的物品；性别= “女” = 职业= “秘书”，这条规则就涉及到两个字段的信息，是两个维上的一条关 联规则。 给出了关联规则的分类之后，在下面的分析过程中，我们就可以考虑某 个具体的方法适用于哪一类规则的挖掘，某类规则又可以用哪些不同的方法 进行处理。 2 4 关联规则挖掘算法 - 2 4 1 经典频繁项目集算法 a g r a w a l 等人于1 9 9 3 年首先提出了挖掘顾客交易数据库中项集间的关联 规则问题，其核心方法是基于频繁项目集理论的递推方法。以后诸多的研究 人员对关联规则的挖掘问题进行了大量的研究。他们的工作包括对原有的算 法进行优化，如引入随机采样、并行的思想等，以提高算法挖掘规则的效率； 提出各种变体，如泛化的关联规则、周期关联规则等，对关联规则的应用进 行推广。 一核心算法 w e b 挖掘与个性化信息服务 a g r a w a l 等在1 9 9 3 年设计了一个基本算法，提出了挖掘关联规则的一个 重要方法一这是一个基于两阶段频繁项目集思想的方法，将关联规则挖掘 算法的设计可以分解为两个子闯题： i ) 找到所有支持度大于最小支持度的项集( i t e m s e t ) ，这些项集称为 频繁项目集( f r e q u e n ti t e m s e t ) 。 i i ) 使用第1 步找到的频繁项目集产生期望的规则。 这里的第2 步相对简单一点。如给定了一个频繁项目集j 爿j 厶五，五2 z 厶厶产生只包含集合亿，厶，五，中的项的所有规则( 最多七条) ，其 中每一条规则的右部只有一项，( 即形如f 卜己7 ，五， 倒。一旦这些规 则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。对 于规则右部含两个以上项的规则，在其以后的工作中进行了研究。 为了生成所有频繁项目集，使用了递推的方法。其核心思想如下： ( 1 ) l l = l a r g e1 - i t e m s e t s ； ( 2 )f o r ( k = 2 ；k 1 o ；k + + ) d ob e g i n ( 3 )c k = a p r i o r i g e n ( l k 1 ) ； 新的候选集 ( 4 ) f b r a l lt r a n s a c t i o n st e dd o b e g i n ( 5 )g = s u b s e t ( c b t ) ； 事务t 中包含的候选集 ( 6 ) f o ra l lc a n d i d a t e sc c td o ( 7 ) c c o u n t + + ； ( 8 ) e n d ( 9 ) l k = f c ec ki c c o u n t m i n s u p ( 1 0 ) e n d ( 1 1 ) a n s w e r = u k l o 首先产生频繁卜项集l 。，然后是频繁2 一项集k ，直到有菜个r 值使得 l 为空，这时算法停止。这里在第k 次循环中，过程先产生候选k 一项集的集 合c t ，c k 中的每一个项集是对两个只有一个项不同的属于l 。的频繁项目集做 一个( k 一2 ) 一连接来产生的。c 。中的项集是用来产生频繁项目集的候选集，最 后的频繁项目集h 必须是的一个子集。q 中的每个元素需在交易数据库中 进行验证来决定其是否加入l k ，这里的验证过程是算法性能的一个瓶颈。这 个方法要求多次扫描可能很大的交易数据库，即如果频繁项目集最多包含1 0 个项，那么就需要扫描交易数据库1 0 遍，这需要很大的i o 负载。 在随后的工作中，a g r a w a l 等引入了修剪技术( p r u n i n g ) 来减小候选集 g 的大小，亩此可以显著地改进生成所有频繁项目集算法的性能。算法中引 入的修剪策略基于这样一个性质：一个项集是频繁项目集当且仅当它的所有 子集都是频繁项目集。那么，如果c 。中某个候选项集有一个( k 一1 ) 一子集不属 w e b 挖掘与个性化信息服务 于l 。，则这个项集可以被修剪掉不再被考虑，这个修剪过程可以降低计算所 有的候选集的支持度的代价。 二 频繁项目集算法的几种优化方法 虽然a p r i o r i 算法自身己经进行了一定的优化，但是在实际的应用中， 还是存在不令人满意的地方，于是入们相继提出了一些优化的方法。 1 基于划分的方法。s a v a s e r e 等设计了一个基于划分( p a r t i t i o n ) 的算 法，这个算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一 个分块并对它生成所有的频繁项目集，然后把产生的频繁项目集合并，用来 生成所有可能的频繁项目集，最后计算这些项集的支持度。这里分块的大小 选择要使得每个分块可以被放入主存，每个阶段只需被扫描一次。而算法的 正确性是由每一个可能的频繁项目集至少在某一个分块中是频繁项目集保证 的。上面所讨论的算法是可以高度并行的，可以把每一分块分别分配给某一 个处理器生成频繁项目集。产生频繁项目集的每一个循环结束后，处理器之 间进行通信来产生全局的候选k 一项集。通常这里的通信过程是算法执行时间 的主要瓶颈；而另一方面，每个独立的处理器生成频繁项目集的时间也是一 个瓶颈。其他的方法还有在多处理器之间共享一个杂凑树来产生频繁项目集。 2 基于h a s h 的方法，一个高效地产生频繁项目集的基于杂凑( h a s h ) 的 算法由p a r k 等提出来。通过实验我们可以发现寻找频繁项目集主要的计算是 在生成频繁2 一项集厶上，p a r k 等就是利用了这个性质引入杂凑技术来改进产 生频繁2 一项集的方法。 3 基于采样的方法。基于前一遍扫描得到的信息，对此仔细地作组合 分析，可以得到一个改进的算法，m a n n i l a 等先考虑了这一点，他们认为采 样是发现规则的一个有效途径。随后又由t o i v o n e n 进一步发展了这个思想， 先使用从数据库中抽取出来的采样得到一些在整个数据库中可能成立的规 则，然后对数据库的剩余韶分验证这个结果。t o i v o n e n 的算法相当简单并显 著地减少了i o 代价，但是一个很大的缺点就是产生的结果不精确，即存在 所谓的数据扭曲( d a t as k e w ) 。分布在同一页面上的数据时常是高度相关的， 可能不能表示整个数据库中模式的分布，由此而导致的是采样5 的交易数据 所花费的代价可能同扫描一遍数据库相近。l i n 和d u n h a m 在中讨论了反扭曲 ( a n t i s k e w ) 算法来挖掘关联规则，在那里他们引入的技术使得扫描数据库的 次数少于2 次，算法使用了一个采样处理来收集有关数据的次数来减少扫描 遍数。 b r i n 等提出的算法使用比传统算法少的扫描遍数来发现频繁项目集，同 时比基于采样的方法使用更少的候选集，这些改进了算法在低层的效率。具 体的考虑是，在计算k 一项集时，一旦我们认为某个( k + 1 ) 一项集可能是频繁项 目集时，就并行地计算这个( k + 1 ) 一项集的支持度，算法需要的总的扫描次数 w e b 挖掘与个性化信息服务 通常少于最大的频繁项目集的项数。这里他们也使用了杂凑技术，并提出产 生“相关规则”( c o r r e l a t i o nr u l e s ) 的一个新方法- 4 减少交易的个数。减少用于未来扫描的事务集的大小。一个基本的原 理就是当一个事务不包含长度为k 的大项集，则必然不包含长度为k + l 的大 项集。从而我们就可以将这些事务移去，这样在下一遍的扫描中就可以要进 行扫描的事务集的个数。这个就是a p r i o r i t i d 的基本思想。 2 4 2 其他挖掘算法 上面论述到的都是基于a p r i o r i 的频繁项目集方法。即使进行了优化， 但是a p r i o r i 方法一些固有的缺陷还是无法克服： 1 ) 可能产生大量的候选集。当长度为l 的频繁项目集有i 0 0 0 0 个的时候， 长度为2 的候选集个数将会超过i o m 。还有就是如果要生成一个很长的规则 的时候，要产生的中间元素也是巨大量的。 2 ) 无法对稀有信息进行分析。由于频繁项目集使用了参数m i n s u p ，所以就 无法对小于m i n s u p 的事件进行分析；而如果将m i n s u p 设成一个很低的值， 那么算法的效率就成了一个很难处理的问题。 下面将介绍两种方法，分别用于解决以上两个问题。 第一种采用一种f p - g r o w t h 的方法。这种方法采用了分而治之的策略： 在经过了第一次的扫描之后，把数据库中的频繁项目集压缩进一棵频繁模式 树( f p - t r e e ) ，同时依然保留其中的关联信息。随后我们再将f p t r e e 分化 成一些条件库，每个库和一个长度为1 的频繁项目集相关。然后再对这些条 件库分别进行挖掘。当原始数据量很大的时候，也可以结合划分的方法，使得 一个f p - t r e e 可以放入主存中。实验表明，f p g r o w t h 对不同长度的规则都 有很好的适应性，同时在效率上较之a p r i o r i 算法有巨大的提高。 第二个问题是基于这个的一个想法：a p r i o r i 算法得出的关系都是频繁出 现的，但是在实际的应用中，我们可能需要寻找一些高度相关的元素，即使 这些元素不是频繁出现的。在a p r i o r i 算法中，起决定作用的是支持度，而 我们现在将把可信度放在第一位，挖掘一些具有非常高可信度的规则。对于 这个问题有这样一种解决方法，整个算法基本上分成三个步骤：计算特征、 生成候选集、过滤候选集。在三个步骤中，关键的地方就是在计算特征时h a s h 方法的使用。在考虑方法的时候，有几个衡量好坏的指数：时空效率、错误 率和遗漏率。基本的方法有两类：m i n h a s h i n g ( m h ) 和 l o c a l i t y s e n s i t i v e - h a s h i n g ( l s h ) 。m i n h a s h i n g 的基本想法是：将条记 录中的头k 个为l 的字段的位置作为一个h a s h 函数。 l o c a l i t y s e n s i t i r e - h a s h i n g 的基本想法是：将整个数据库用种基于概率 的方法进行分类，使得相似的列在一起的可能性更大，不相似的列在一起的 可能性较小。我们再对这两个方法比较一下。心的遗漏率为零，错误率可以 w e b 挖掘与个性化信息服务 由k 严格控制，但是时空效率相对的较差。l s h 的遗漏率和错误率是无法同 时降低的，但是它的时空效率却相对的好很多。所以应该视具体的情况而定。 最后的实验数据也说明这种方法的确能产生一些有用的规则。 2 5 序列模式( s e q u e n c em o d e ) 概述 举例说明，比如有顾客租借录像带，典型的顺序是先租“星球大战”， 然后是“帝国反击战”，再是“杰达武士归来”( 这三部影片是以故事发生的 时间先后而情节连续的) 。值得注意的是租借这三部电影的行为并不一定需要 是连续的。在任意两部之间随便插租了什么电影，仍然还是满足了这个序列 模式，并且扩展一下，序列模式的元素也可以不只是一个元素( 如一部电影) ， 它也可以是一个项集( i t e ms e t ) 。所谓项集，指的是多个物品组成的集合， 内部元素不分排列顺序，比如“枕头和枕头套”就可以看作是由两个项( i t e m ) 组成的项集，它也可以作为某一个序列模式的元素。 2 6 序列模式的基本概念 数据源是一个给定的由客户交易( c u s t o m e rt r a n s a c t i o n ) 组成的大型数 据库，每个交易( t r a n s a c t i o n ) 由客户号( c u s t o m e r i d ) ，交易时间 ( t r a n s a c t i o n t i m e ) 以及在交易中购买的项( i t e m ) 组成。 ( 1 ) 项集( i t e m s e t ) 是由项( i t e m ) 组成的一个非空集合。 ( 2 ) 序列( s e q u e n c e ) 是一列排好序的项集 不失一般性我们假定项集中的项由一些连续整数代替，这样一个项集i 可以表示为( i 。，i ：i ) ，而这里的i j 代表了一个项。一个序列s 可以表示为 ，这里的s ，代表的是一个项集。 两个序列a 和b ( b ，b 2 b ，如果存在整数i 。 i 。 ，因为 ( 3 ) 包含于( 3 ，8 ) ，( 4 ，5 ) 包含于( 4 ，5 ，6 ) 以及( 8 ) 包含于( 8 ) 。但是序y j 不包含于 ，反之亦然。前者表示项3 和项5 是先后购买的，而后 者则表示项3 和项5 是同时购买的，这就是区别所在。在一个序列集( as e to f s e q u e n c e s ) 中如果序列s 不包含于任何其他序列中，则称序列s 为最大的 ( m a x i m a l ) 。 一个客户所有的事务( t r a n s a c t i o n s ) 可以综合的看成是一个序列，每一 个事务都由相应的一个项集来表示。事务按交易时间序排列就成了一个序列。 我们称这样的序列为客户序列( c u s t o m e r s e q u e n c e ) 。通常，将个客户的交 易按交易时间排序成t 1 ，t 2 ，t n 。t i 中的项集定义成i t e m s e t ( t i ) 。 这样，这个客户的客户序列就成了这样的一个序列：( i t e m s e t ( t 1 ) i t e m s e t ( t 2 ) i t e m s e t ( t n ) ) 。见图2 。_ 1 w e b 挖掘与个性化信息服务 c u s t o m e ri dc u s t o m e r s e q u e n c e 1 2 4 5 图2 1 客户序列视图的数据库 如果一个序列s 包含于一个客户序列中，则我们称该客户支持( s u p p o r t ) 序 列s 。一个具体序列的支持( s u p p o r t ) 定义为那一部分支持该序列的客户总数。 给定一个由客户交易组成的数据库d ，挖掘序列模式的问题就是在那些 具有客户指定最小支持度( m i n i m u ms u p p o r t ) 的