（统计学专业论文）具有多维限定性约束条件的交易规则模型及采掘算法研究.pdf

摘要 为了及时准确地发现在销售活动中顾客的行为呈现出什么特点，管理人员 经常采用关联规则与序列规则分析方法进行商业销售分析，从而为决策者提供 决策依据。 然而一般的关联规则与序列规则分析无法挖掘带有各种约束条件的交易规 则。在本文中，笔者提出了具有多维限定性约束条件的交易规则模型，通过对 a p r i o r i 算法、f p _ g r o w t h 算法进行扩展，实现了集中式环境下该模型的采掘算 法；通过扩展f d m - l p 算法完成了分布式环境下模型的采掘。 全文一共分为四个部分：第一部分讨论了数据挖掘与数据仓库的基本概 念；第二部分讨论了具有时间约束的交易规则模型及其实现算法；第三部分讨 论了具有多维约束条件的交易规则模型及其实现算法；在第四部分首先介绍了 如何在分布式环境下进行关联规则挖掘，然后讨论了如何实现本文提出的模型 以及需注意的几个问题。 作为一门新兴技术，数据挖掘在我国基本上还处于研究阶段，笔者衷心地 希望包括本文所提出的模型与算法在内的各种数据挖掘方法能尽早地走向实际 应用。 关键词： 数据挖掘关联规则 多维约束交易规则采掘算法 a p r i o r i 算法f p _ g r o w t h 算法f d m - l p 算法 ab s t r a c t 1 1 1o r d e r t o f i n do u t t h ec h a r a c t e r i s t i c s t i m e l ya n dr a p i d l yd u r i n g t h ec o u r s e o f s a l e ， | n a n a g e r sa l w a y sa n a l y z et h es a l ec o n d i t i o nb yu s i n ga s s o c i a t i o na n ds e q u e n c ea n a l y s e s t op r o v i d ed e c i s i o nb a s i st ot h ed e c i d e r b u tt h ec o m m o na s s o c i a t i o na n ds e q u e n c ea n a l y s e sc a nn o tm i n eo u tt h et r a n s a c t i o nm l e sw i t hm u l t i d i m e n s i o nl i m i t si nt h i sp a p e rw cc o n s t r u c tt h et r a n s a c t i o nr u l e m o d e lw i t hm u l t i d i m e n s i o nl i m i t s ，a n dt h r o u g l le x t e n d i n gt h ea p r i o r ia l g o r i t h ma n d t h ef p g r o w t ha l g o r i t h mw ec a ng e tt h ea l g o r i t h m sw h i c hc a nb eu s e dt om i n et h i s m o d e li nt h ec e n t e rc o m p u t e rs y s t e m ；t h r o u g he x t e n d i n gt h ef d m a l g o r i t h mw e g e tt h ea l g o r i t h m sw h i c hc a nb eu s e di nt h ed i s t r i b u t e dc o m p u t e rs y s t e m t h i sp a p e ri n c l u d ef o u rp a r t si nt h ef i r s tp a r tw ei n t r o d u c es o m eb a s i cc o n c e p t so f d a t aw a r e h o u s ea n dd a t am i n i n g ；i nt h es e c o n dp a r tw ed i s c u s st h et r a n s a c t i o nr u l e m o d e lw i t ht i m el i m i ta n dt h ea l g o r i t h mt om i n ei t ；t h e nw ed i s c u s st h et r a n s a c t i o nr u l e m o d e lw i t hm u l t i d i m e n s i o nl i m i ta n dt h ea l g o r i t h mt om i n ei ti nt h et h i r dp a r t ；a tl a s t w ed i s c u s sh o wt om i n ea s s o c i a t i o nr u l e si nad i s t r i b u t e dc o m p u t e rs y s t e ma n dt h e p r o b l e m sw h i c hs h o u l db ep a i da t t e n t i o nt oi no r d e rt ou s et h em o d e lc o n s t r u c t e di n t h i sp a p e r a san e wt e c h n o l o g y , d a t am i n i n gi ss t i l li nt h ep h a s eo f s t u d yi no u rc o u n t r y , w e d oh o p et h a ta l lk i n d so f d a t am i n i n gm e t h o d s ，i n c l u d i n gt h em o d e la n da l g o r i t h m s p r e s e n t e db ym y s e l f o f c o u r s e ，c a nb ep u ti n t op r a c t i c es o o n k e yw o r d s ：d a t am i n i n ga s s o c i a t i o nr u l em u l t i - d i m e n s i o nl i m i t s t r a n s a c t i o nr u l e m i n i n ga l g o r i t h ma p r i o r ia l g o r i t h m f p g r o w t ha l g o r i t h m f d m - l pa l g o r i t h m 第一章数据仓库与数据挖掘技术概论 1 1 数据仓库基础知识 1 1 1 从数据库到数据仓库( d a t aw a r e h o u s e ) 随着计算机技术的飞速发展和企业界不断提出新的要求，数据仓库技术应运 而生。传统的数据库技术是以单一的数据资源，即数据库为核心，进行从事务处 理、批处理到决策分析等各种类型的数据处理工作。然而不同类型的数据处理有 着不同的处理特点，以单一的数据组织方式进行组织的数据库并不能反映这种差 异。随着数据库技术的普及以及各种管理信息系统( m i s ) 和决策支持系统( d s s ) 的大量应用，人们开始认识到，针对不同的数据处理任务采用不同的数据组织方 式是必要的。 总的说来，当前的数据处理可以分为两种类型：操作型处理与分析型处理。 操作型处理也叫做事务处理，是指企业为完成日常的特定应用，对数据库进行的 各种联机操作，如插入、删除、汇总等。为完成此类任务而建立的计算机系统我 们一般称之为联机事务处理系统( o u t ) ，对这类系统人们主要关心的是响应时间、 数据的安全性与完整性。而分析型处理则用于企业管理人员的各类决策分析，如 d s s 、e i s ( 执行信息系统) 和多维分析等。为完成此类决策分析型任务而建立的 计算机系统我们一般称之为联机分析处理系统( o l a p ) 。为了完成指定的分析任 务，系统通常需要访问大量的历史数据并进行相当复杂的运算，而使用o l a p 系 统的管理人员更关心分析结果对决策支持的有效性和可靠性。概括的说，这两类 处理的不同主要在于以下五个方面”1 ： ( 1 ) 事务处理与分析处理的性能特征不同； ( 2 ) 分析处理对数据集成的要求明显高于事务处理； ( 3 ) 分析处理需要系统进行动态数据集成，而事务处理系统不具备这种 能力： ( 4 ) 事务处理系统一般只保留当前数据，而分析处理要以大量的历史数据为依 据； ( 5 ) 事务处理系统中保留了大量的细节数据，而分析处理要对细节数据进行不 同程度的综合。 因此，在传统的事务型环境中亢接构造分析型应用是不合适的。我们必须把 分析型数据从事务环境中提取出来，按照决策支持的需要重新组织，建立单独的 分析处理环境。数据仓库正是为了构建这种新的分析处理环境而出现的一种数据 存储和组织技术。 1 1 2 什么是数据仓库( d w ) 按照w hl n m o n 这位数据仓库系统构造方而的领头设计帅的说法，“数据仓库 是一个面向主题的、集成的、时变的、非易失的数据集合，支持管理部门的决策 过程”i t 。下l 面我们简要讨论一下数据仓库的四个特征： ( 1 ) 面向主题的：数据仓库中的数据都是围绕一些与决策有关的主题，如顾客、 供应商、产品等进行组织，排除了对决策无月 的数据； ( 2 ) 集成的：通常数据仓库中的数据来源于多个异种数据库，需要对进入数据 仓库的数据进行清理与集成，以保证命名约定、长度、精度等的一致； ( 3 ) 时变的：数据存储从历史的角度提供信息，数据仓库中的关键结构，隐式 或显式地包含时间元素； ( 4 ) 非易失的：数据仓库中的数据不需要事务处理、恢复和并发控制机制。通 常，它只需要两种操作：数据的初始化装入和数据访问。 我们说数据仓库是一个环境而不是一件产品，它提供用户用于决策支持的 当前和历史数据，而这些数据在传统的操作型数据库中很难或不能得到。数据仓 库技术是为了有效的把操作型数据集成到统一的环境中以提供决策型数据访问的 各种技术和模块的总称。所做的一切都是为了让用户更快更方便查询所需要的信 息，以便为决策提供支持。 1 1 3 数据仓库的结构 图1 ( 见下页) 是数据仓库框架的示意图”1 。最左边是数据源，包括数据库与非数 据库源。数据仓库应能通过o d b c 之类的机制访问各数据源，并能对源数据进行 净化、整理。决策者使用各种数据分析工具对进入到数据仓库中的数据进行查询、 联机分析以及数据挖掘处理，从而抽取出供决策者使用的决策信息。 1 2 数据挖掘基础知识 在上一节我们看到数据仓库框架的工具与接口层中，除了一般的查询、分析 与报表工具外，还有一种叫做数据挖掘( d a t a m i n i n g ) 的工具。在本节我们将详细讨 论什么是数据挖掘和常见的数据挖掘方法。在下节里将说明在决策分析过程中， 为什么除了进行联机分析处理( o l a p ) 以外还要使用数据挖掘t 具，以及数据挖 掘与数据仓库和联机分析处理之问的关系。 部门数据仓库 分析工具： 查询与报表 联机分析处理 数据挖掘 用户接口： 图形用户接 数据源数据集成 数据仓库( 核心) 工具与接口 图1 数据仓库框架 甘困 l 者1 1 _ j 1 - 2 1 什么是数据挖掘( d m ) 当今数据库的容量已经达到了海量的水平，很多数据库中已经存储上万亿字 节的数据。大量的数据被描述为“数据丰富，知识贫乏”，因为人们没有强有力的 工具能对这些数据进行有效地分析，发现其背后隐藏的具有决策意义的信息( 即 “知识”) 。对于这个问题，计算机科学界给出的最新回答就是：数据挖掘。数据 挖掘简单说来就是从大量数据中抽取出知识。它是一种决策支持过程，主要基于 人工智能( a i ) 、机器学习、统计学等技术，高度自动化地分析企业原有的数据， 作出归纳性的推理，从中挖掘出供决策使用的高层次的知识，帮助决策者提高决 策质量和效率【1 】。通过数据挖掘工具从海量的原始数据中抽取出各种规则与知识， 从而避免了决策者陷入浩瀚的数据海洋中。 1 2 2 数据挖掘过程 对原始的业务数据进行挖掘，一般要经过以下几个步骤”1 ： ( 1 ) 数据净化消除数据库中的干扰数据和不一致数据( 噪声数据) ； ( 2 ) 数据集成对企业内不同部门的多数据源进行综合； ( 3 ) 数据聚焦从数据库中检索出与分析任务相关的数据； ( 4 ) 数据转换对数据条目进行分割或组合以满足数据挖掘的要求； 3 团圆习习 ( 5 ) 模式发现运用各种分析方法抽取出数据模式或规则( 即知识) ； ( 6 ) 知识呈现一一将挖掘出来的模式与规则以图形化方式呈现给用户。 12 3 数据挖掘的基本分析方法 对于不同的决策目标，人们期望挖掘出不同的模式。模式是一个用语言l 来 表示的一个表达式e ，它可用来描述数据集f 中数据的特性，e 所描述的数据是集 合f 的一个子集f e 。e 作为一个模式要求它比列举数据子集f e 中所有元素的描 述方法简单。f f , j j z r l ，“如果成绩在8 1 9 0 之问，则成绩优良”可称为一个模式， 而“如果成绩为8 1 、8 2 、8 3 、8 4 、8 5 、8 6 、8 7 、8 8 、8 9 或9 0 ，则成绩优良”就不 能称之为一个模式。根据m m 的划分法，按照所挖掘的数据模式的不同，可以将 数据挖掘的分析方法划分为以下四种”： ( 1 ) 关联分析 关联分析是寻找数据库中值的相关性，即寻找在同一个事件中出现的不同项 的相关性，比如在一次购买活动中所买不同商品的相关性。关联规则可记为 a = = b ，a 称为前提和左部( l h s ) ，b 称为后续或右部( r h s ) 。如“买锤子的人 也会买钉子”便是一条关联规则。 ( 2 ) 序列分析 与关联分析相似，其目的也是为了挖掘数据项之间的联系，但序列分析的侧 重点在于分析数据项之间时间上的前后关系。序列规则也可记为j 6 f b ，表示a 发生以后将会发生b 。 关于关联规则和序列规则分析将在第二章作详细论述。 ( 3 ) 分类分析 分类要解决的问题是为一个事件或对象归类。在使用上，既可以用此模型分 析已有的数据，也可以用它来预测未来的数据。例如，用分类来预测哪些客户最 倾向于对直接邮件推销做出回应，又有哪些客户可能会换他的手机服务提供商， 或在医疗领域当遇到一个病例时用分类来判断一下从哪些药品着手比较好。 数据挖掘算法的工作方法是通过分析已知分类信息的历史数据总结出一个预 测模型。这里用于建立模型的数据称为训练集，通常是已经掌握的历史数据。如， 已经不再接受服务的用户，你很可能还保存了他们在接受服务时的历史记录。训 练集也可以是通过实际的实验得到的数据。比如你从包含公司所有顾客的数据库 中取出一部分数据做实验，向他们发送介绍新产品的推销信，然后收集对此做出 回应的客户名单，然后你就可以用这些推销回应记录建立一个预测哪些用户会对 新产品感兴趣的模型，最后把这个模型应用到公司的所有客户上。 ( 4 ) 聚类分析 聚类是把整个数据库分成不同的群组。它的目的是要群与群之问差别很明显， 而同一个群之间的数据尽量相似。与分类不同，在开始聚类之前我们并不知道要 把数据分成几组，也不知道怎么分( 依照哪几个变量) 。因此在聚类之后要有一个 对业务很熟悉的人来解释这样分群的意义。很多情况下一次聚集所得到的分群对 于特定的业务来说可能并不好，这时需要删除或增加变量以影响分群的方式，经 过几次反复之后才能最终得到一个理想的结果。神经元网络和k 。均值是比较常用 的聚集算法。 1 2 4 数据挖掘的常用技术与工具 数据挖掘的常用技术有以下几种”1 ： ( 1 ) 人工神经网络 仿照生理神经网络结构的非线形预测模型，通过学习进行模式识别。 ( 2 ) 决策树 代表着决策集的树形结构。 ( 3 ) 遗传算法 基于进化理论，并采用遗传结合、遗传变异、以及自然选择等设计方法的优 化技术。 ( 4 ) 近邻算法 将数据集合中每一个记录进行分类的方法。 ( 5 1 规则推导 从统计意义上对数据中的“如果那么”规则进行寻找和推导。 采用上述技术的某些专门的分析工具已经发展了大约十年的历史，不过这些工 具所面对的数据量通常较小。而现在这些技术已经被直接集成到许多大型的工业 标准的数据仓库和联机分析系统中去了。 1 2 5 数据挖掘工具习 ( 1 ) 基于神经网络的工具 由于对非线性数据的快速建模能力，基于神经网络的数据挖掘工具现在越来 越流行。其开采过程基本上是将数据聚类，然后分类计算权值。神经网络很适合 非线性数据和含噪声数据，所以在市场数据库的分析和建模方面应用广泛。 ( 2 ) 基于规则和决策树的工具 大部分数据挖掘工具采用规则发现或决策树分类技术来发现数据模式和规 则，其核心是某种归纳算法。这类工具通常是对数据库的数据进行开采，生产规 则和决策树，然后对新数据进行分析和预测。这类工具的主要优点是，规则和决 策树都是可读的。 ( 3 ) 基于模糊逻辑的工具 其发现方法是应用模糊逻辑进行数据查询、排序等。该工具使用模糊概念和 “最近”搜索技术的数据查询工具，它可以让用户指定目标，然后对数据库进行搜索， 找出接近目标的所有记录，并对结果进行评估。 ( 4 ) 综合多方法工具 不少数据挖掘工具采用了多种开采方法，这类工具一般规模较大适于大型 数据库( 包括并行数据库) 。这类工具开采能力很强，但价格昂贵，并要花很长时 问进行学习。 1 2 6 数据挖掘的应用 数据挖掘可以应用在各个不同的领域。很多商业企业都在利用数据挖掘技术 确定客户的特点，为客户提供针对性的服务。比如，已经发现了购买某一商品的 客户的特征，那么就可以向那些具有这些特征但还没有购买此商品的客户推销这 个商品。电讯公司和信用卡公司是用数据挖掘检测欺诈行为的先行者。保险公司 和证券公司也开始采用数据挖掘来减少欺诈。医疗应用是另一个前景广阔的产业 数据挖掘可以用来预测外科手术、医疗试验和药物治疗的效果。零销商更多 的使用数据挖掘来决定每种商品在不同地点的库存，通过数据挖掘更灵活的使用 促销和优惠手段。制药公司通过挖掘巨大的化学物质和基因对疾病的影响的数据 库来判断哪些物质可能对治疗某种疾病产生效果。总之，由于数据挖掘带来的显 著的经济效益，使之具有极为广阔的应用前景，而且随着信息技术的日益普及， 数据挖掘将有着更为广泛的应用前景。 1 3 数据挖掘与数据仓库和联机分析处理之间的关系 从图1 中我们看到，数据挖掘与联机分析处理都是建立在数据仓库基础上的分 析工具，那么是否数据挖掘一定要建立在数据仓库之上呢? 数据挖掘与联机分析 处理之间究竟有什么区别与联系? 以下将对这两个问题进行详细说明。 1 3 1 数据挖掘( d m ) 和数据仓库( d w ) 大部分情况下，数据挖掘都要先把数据从数据仓库中拿到数据挖掘库或数掂 集市中( 见图2 ) 。从数据仓库中直接得到进行数据挖掘的数据有许多好处。因为 数据仓库的数据清理和数据挖掘的数据清理要求相近，如果数据在导入数据仓库 时己经清理过，那很可能在做数据挖掘时就没必夏再清理一次了，而且所有的数 据不一致的问题都已经解决了。 图2 数据挖掘库从数据仓库中得出 数据挖掘库可能是数据仓库的一个逻辑上的子集，而不一定非得是物理上单 独的数据库。但如果数据仓库的计算资源己经很紧张，则最好还是建立一个单独 的数据挖掘库。 当然为了数据挖掘也不必非得建立一个数据仓库，数据仓库不是必需的。原 因在于把各个不同源的数据统一在一起，解决所有的数据冲突问题，然后把所有 的数据导到一个数据仓库内，是一项巨大的工程，可能要花费大量的人力与财力。 为了进行数据挖掘，也可以把一个或几个事务数据库导到一个只读的数据库中， 就把它当作数据集市，然后在它上面进行数据挖掘。 图3 数据挖掘库从事务数据库中得出 1 3 2 数据挖掘( d m ) 和联机分析处理( o l a p ) 联机分析处理是一种至上而下、不断深入的分析工具，是决策支持领域的 部分。传统的查询和报表工具是告诉你数据库中都有什么( w h a th a p p e n e d ) ，o l a p 则更进一步告诉你下一步会怎么样( w h a tn e x t ) 和如果我采取这样的措旌又会怎 么样( w h a ti f ) 。用户首先建立一个假设，然后用0 l a p 检索数据库来验证这个假 设是否正确。比如，一个分析师想找到什么原因导致了贷款拖欠，他可能先做一 个初始的假定，认为低收入的人信用度也低，然后用0 l a p 来验证他这个假设。 如果这个假设没有被证实，他可能去察看那些高负债的账户，如果还不行，他也 许要把收入和负债一起考虑，一直进行下去，直到找到他想要的结果或放弃。 也就是说，o l a p 分析师是建立一系列的假设，然后通过0 l a p 来证实或推 翻这些假设来最终得到自己的结论。o l a p 分析过程在本质上是一个演绎推理的过 程。但是如果分析的变量达到几十或上百个，那么再用0 l a p 手动分析验证这些 假设将是一件非常困难和痛苦的事情。 数据挖掘与o l a p 不同的地方是，数据挖掘不是用于验证某个假定的模式( 模 型) 的正确性，而是在数据库中自己寻找并发现模型。它在本质上是一个归纳的 过程。比如，一个用数据挖掘工具的分析师想找到引起贷款拖欠的风险因素。数 据挖掘工具可能帮他找到高负债和低收入是引起这个问题的因素，甚至还可能发 现一些分析师从来没有想过或试过的其他因素，比如年龄9 1 。 数据挖掘和0 l a p 具有一定的互补性。在利用数据挖掘出来的结论采取行动 之前，如果想要验证一下采取这样的行动会带来什么样的影响，那么o l a p 工具 能回答此类问题。而且在知识发现的早期阶段，o l a p 工具还有其他一些用途。可 以帮助探索数据，找到哪些是对一个问题比较重要的变量，发现异常数据和互相 影响的变量。这些都能有助于我们更好的了解数据，加快知识发现的过程。 第二章具有确定性时问约束的交易规则模型及采掘算法 2 1 关联规则与序列规则的基础知识 2 1 1 关联规则的概念及定义 考察一些涉及许多物品的事务：事务1 中出现了物品甲，事务2 中出现了物 品乙，事务3 中则同时出现了物品甲和乙。那么，物品甲和乙在事务中的出现相 互之间是否有规律可循呢? 在数据库的数据挖掘中，关联规则就是描述这种在一 个事务中物品之间同时出现的规律的知识模式。更确切的说，关联规则通过量化 的数字描述物品甲的出现对物品乙的出现有多大的影响。 在现实生活中。这样的例子很多。例如超级市场利用前端收款机收集存储了 大量的售货数据，这些数据是一条条的购买事务记录，每条记录存储了事务处理 时间，顾客购买的物品、物品的数量及金额等。这些数据中常常隐含形式如下的 关联规则：在购买铁锤的顾客当中，有7 0 的人同时购买了铁钉。这些关联规则 很有价值，商场管理人员可以根据这些关联规则更好地规划商场，如把铁锤和铁 钉这样的商品摆放在一起，能够促进销售。 有些数据不像售货数据那样很容易就能看出一个事务是许多物品的集合，但 稍微转换一下思考角度，仍然可以像售货数据一样处理。比如人寿保险，一份保 单就是一个事务。保险公司在接受保险前，往往需要记录投保人详尽的信息，有 时还要到医院做身体检查。保单上记录有投保人的年龄、性别、健康状况、工作 单位、工作地址、工资水平等。这些投保人的个人信息就可以看作事务中的物品。 通过分析这些数据，可以得到类似以下这样的关联规则：年龄在4 0 岁以上，工作 在a 区的投保人当中，有4 5 的人曾经向保险公司索赔过。在这条规则中，“年 龄在4 0 岁以上”是物品甲，“工作在a 区”是物品乙，“向保险公司索赔过”则 是物品丙。可以看出来，a 区可能污染比较严重，环境比较差，导致工作在该区 的人健康状况不好，索赔率也相对比较高。 2 1 2 关联规则的形式描叙 关联分析的目的是找出给定数据记录集中数据项之间的相互关系。令i - fi 1 ， i 2 ，i 。1 表示数据项集，t 表示交易集，t 表示一次交易活动每次交易只含i 的一个子集。若某次交易活动t 中包含数据项集a 和b ，且a ，b g ，a n b = 中， 则称这次交易中含有关联规则a b ”1 。对每一条规则可以用支持度和置信度”1 对 其进行描述。 ( 1 ) 支持度( s u p p o l t ) ：表示在所有交易中同时含有a 与b 的概率，即规则 a ；b 在所有交易中的普遍程度，s ( a b ) = p ( a u b ) = j “jt 中含a ，b j jdi 1 0 0 。 ( 2 ) 置信度( c o n f i d e n c e ) ：表示在所有出现了a 的活动中出现b 的概率，即 规则a b 的必然性有多大，c ( a ；b ) = p ( ba ) = l ( tt 中含a ，b ) i l t t 中含a 1l 1 0 0 。 如果不考虑关联规则的支持度和可信度，那么在事务数据库中存在无穷多的关 联规则。事实上，人们一般只对满足 定的支持度和可信度的关联规则感兴趣。 因此，只有当s ( a b ) 与c ( a b ) 超过用户指定的阈值时，我们才可以将 a b 看成t 中的一个关联规则。 关联分析常用于分析消费者在购买某些商品时，是否同时购买另一些商品。 如某企业五月份的3 0 0 0 笔销售交易中，购买彩电的交易有1 0 0 0 笔，购买彩电同 时购买了v c d 的交易有6 0 0 笔，则有关联规则“彩电一v c d 机”，且s ( 彩电一v c d 机) = 6 0 0 3 0 0 0 1 0 0 = 2 0 ，c ( 彩电 v c d 机) = 6 0 0 1 0 0 0 1 0 0 = 6 0 。对 某一条关联规则p ，s ( p ) 越大表明具有该规则的交易量在企业交易活动中的比 重越大，越应该受到关注；c ( p ) 越大表明这条规则越真实。 在实际情况下，一种更有用的关联规则是泛化关联规则。因为物品概念间存 在种层次关系，如夹克衫、滑雪衫属于外套类，外套、衬衣又属于衣服类。有 了层次关系后，可以帮助发现一些更多的有意义的规则。例如“买外套一买鞋子” ( 此处，外套和鞋子是较高层次上的物品或概念，因而该规则是一种泛化的关联 规则) 。由于商店或超市中有成千上万种物品，平均来讲，每种物品( 如滑雪衫) 的支持度很低，因此有时难以发现有用规则；但如果考虑到较高层次的物品( 如 外套) ，则其支持度就较高，从而可能发现有用的规则。 2 1 _ 3 序列规则的概念及定义 举例说明，比如有顾客租借录像带，典型的顺序是先租“星球大战”，然后是 “帝国反击战”，再是“杰达武士归来”( 这三部影片是以故事发生的时间先后而 情节连续的) 。值得注意的是租借这三部电影的行为并不一定需要是连续的。在任 意两部之间随便插租了什么电影，仍然还是满足了这个序列模式，并且扩展下， 序列模式的元素也可以不只是一个元素( 如一部电影) ，它也可以是一个项集( i t e m 即f ) 。所谓项集，指的是多个物 组成的集合，内部元素不分排列顺序，比如“枕 头和枕头套”就可以看作是由两个项( i t e m ) 组成的项集，它也可以作为某一个序 列模式的元素。 214 序列规则的形式描叙 与关联分析相似，序列分析的目的也是为了挖掘数据项之问的联系，但其侧 重点在于分析数据项之问的前后关系，若顾客在先购买了a 商品后，随后购买了 b 商品，则称该顾客的购买行为中存在序列规则q = ( a ) ， b ) ) ”。 设d = d 1 ，d 2 ，d 。) 为顾客集，每一顾客的购买行为按时间顺序形成一 个序列，我们同样可以定义序列规则q 的支持度和置信度“1 ，其中： s ( q ) = l d 1d 先购买a ，再购买b ) i idl 1 0 0 c ( q ) = l d j id j 先购买a 后购买b ) i ，l d i d i 购买a ) lx 1 0 0 例如某企业现有的1 0 0 0 名客户中，其中购买电脑的客户有4 0 0 名，在购买电 脑之后购买了财务软件的有2 0 0 名，则存在序列规则q = ( 电脑) ， 财务软件) ) ，且s ( q ) = 2 0 0 1 0 0 0 x1 0 0 = 2 0 ，c ( q ) = 2 0 0 4 0 0 x1 0 0 = 5 0 。 2 1 5 关于挖掘算法的讨论 关联规则的挖掘一般分为两步9 1 ： 第一步：找出所有频繁数据项集，即找出支持度超过指定阈值的数据项集； 第二步：在频繁数据项集中生成候选关联规则，验证置信度后生成关联规则。 在上述两步中，频繁数据项集的生成是最关键的。a p r i o d 算法是一种常用的 频繁数据项集生成算法。然而a p r i o r i 算法在生成频繁数据项集时必须先产生候选 集，且需多次扫描数据库，因此效率较差。在实际应用中还有一种不需要产生候 选集的算法，即频繁模式增长( f r e q u e n t - p a t t e r ng r o w t h ) 方法。关于a p r i o r i 算法 和频繁模式增长方法的具体细节将在第2 3 和2 4 节详细讨论。 序列规则的挖掘一般采用r & g r a w a l 等人提出的a p r i o r ia l l 算法，该算法分为 以下四个步骤”1 ： 第一步：以顾客标识为主键、交易时间为次键将交易数据排序： 第二步：筛选出频繁数据项集； 第三步：对顾客序列进行适当变换，消除其中的非频繁数据项集，并用编号 表示之，以减少计算开销； 第四步：寻找合适的频繁序列。 限于篇幅，本文不对a p r i o da j l 算法进行详细讨论，关于a p r i o f ia l l 算法的 进一步论述可参考文献 2 】。 2 1 6 关联规则与序列规则在商业销售分析中的应用 关联规则与序列规则分析在实际中有着极为广泛的、i 用，为简便起见，在本 文的后续分析中，将以商业销售分析为例进行论述。将上述两种方法用于分析顾 客的购买行为和习惯，可以使企业决策者从大量的零散业务数据中摆脱：h 来，透 过纷繁复杂的数据直接彳 到事物本来的而目，从而作出相应的决策。根据分析的 结果企业可以不断调整其营销策略，获得更好的利润。例如根据关联分析的结果 将相关联商品的信息放到同一网页，或增加网页间的直接超链；根据序列分析的 结果，有针对性地向顾客的电子邮箱中投放其最有可能! = ! 勾买的商品的广告。 2 2 具有确定性时间约束的交易规则模型 2 2 1 问题的提出 日趋激烈的市场竞争要求商业经营者更加准确的了解商场经营情况，跟踪市 场趋势，更加合理地制定商品采购与销售策略。商业销售分析即通过对历史销售 数据( 也称交易数据) 运用各种方法进行全面挖掘与分析，从而得到有价值的销 售规律与模式( 也称交易规则) ，为决策者提供决策依据。关联规则分析与序列规 则分析就是两种常见的交易规则分析方法。关联规则用于描述在每次销售活动( 即 交易) 中顾客的行为呈现出什么特点，如“8 0 的顾客在购买产品a 、b 的同时会 购买产品c ”；序列规则侧重于描述顾客的一系列购买行为在时间先后上的特点， 如“6 0 的顾客会在购买了a 产品后又购买b 产品”。从交易数据库中挖掘出的大 量关联规则与序列规则可以用于产品目录设计、商场商品的陈列方式以及有针对 性的广告策略等。 然而在商业销售分析的过程中，往往还存在另一类决策者所关心的交易规则， 用于描述如下问题“6 0 的顾客在t l 时刻购买了产品a 后，会在t 2 时刻购买 产品b ”。这类规则虽然也是分析顾客交易活动的前后因果关系，但与普通序列规 则不同。普通序列规则只能用于分析顾客将会出现的行为特点是什么( 即将要购 买的商品是什么) ，而不能提供关于顾客将在何时出现这种行为特点的信息。在本 文中，我们将上述这种具有精确时间属性的交易规则称为具有时间约束的交易规 则，从其性质而言，属于一种特殊序列规则。 我们对序列规则进行如下分析： 设i = i 1 ，i 2 ，i k ) 是商品项集，a = a l ，a 2 ，a m ) ，b = b l ，b 2 ， b 。1 且a 、b e ，a n b = 中，则“顾客购买a 商品集后购买了b 商品集”用序列规 则可以描述为q = ( a ，b ) ，其中a 、b 称为交易集。设顾客前后两次购买行为的发 生时间分别为t 。和t b ，若将购买行为序列中的时间信息作为一个属性加入到每一次 的交易集中，则上述规则可表示为q = ( a u k ) ， b u t b ) 。此时由于时间信息已经 包括在每次交易集中，可以将顾客的序列购买行为当作为同一次购买。因此序列 规则q 可以转换为关联规则p = ( a u t a ) u t b ) = ( a 1 ，a 2 ，a m ，t 。) ) j ( b l ， b ：，b 。，t b1 ) 。若t i _ t b ，p 即为一般关联规则，因此我们可以将序列规则看作 是一种特殊的关联规则。基于上述思想，可以将上述具有时间约束的交易规则作 为一种特殊关联规则带时间约束的关联规则对待。在本文巾，我们建立了该 交易规则的模型，并给出了其实现算法。 2 2 2 具有时间约束的交易规则模型“ 一般关联规则的定义如下：令l = ( i l ，i 2 ，i 。) 表示数据项集，t 表示交易 集，t 表示一次交易活动，每次交易只含i 的一个子集。若某次交易活动t 中包含 数据项集a 和b ，且a ，b c i ，a n b = 巾，则称这次交易中含有关联规则a b 。 但在一般关联规则模型中，由于是同一次交易活动，因此没有包含交易时间属性。 为描述具有时间约束的交易规则，需要对一般关联规则进行扩展。 设a ，b c i ，且a n b = 中，i 的定义同一般关联规则。定义集合t = ft l ，t 2 ， t l 为交易活动的时间约束集。其中t i 表示一个时段，如年、季度或月等，且t i c t i + 。 ( 表示t i 早于t _ 十1 ) ，o i l 1 。设t i ，t b c 了，若某顾客在t i 时段购买了产品集a 后在t b 时段又购买了产品集b ，我们就称该顾客的购买行为中含有带时间约束的 交易规则p ，该规则可以表示为p = ( a u t a ) j ( b u t b ) = ( a 1 a 2 ，a m ，t i ) 一( ( b 1 ，b 2 ，b 。，t b ) ) 。需要注意的是，由于顾客可能在同一时段( 例如同一 季度) 以内先后购买不同商品，所以有可能t l - t b ，此时退化为一般关联规则。可 以有如下两种处理方法： ( 1 ) 采用更小的时间粒度，例如将按季度分析转换为按月分析，以使t ：t b ； ( 2 ) 仍使用本文所述模型与算法进行分析，其结果与一般关联分析结果相同。 以下我们只讨论t i t b 的情况。 设d = ( d i ，d 2 ，d 。) 为顾客集，可以定义带时间约束的交易规则p 的支 持度与置信度如下： ( 1 ) 支持度( s u p p o r t ) ：表示所有顾客中，在t 时段购买了a 且t b 时段又购买 了b 的概率。s ( a u t i ) 叫b u 曲】_ l d id 。在t 时段购买a ，在t b 时段购买 b ll ，idf 1 0 0 。 ( 2 ) 置信度( c o n f i d e n c e ) ：表示所有在t 。时段购买了a 的顾客中，在t b 时段 购买了b 的概率。c 【( a u t 。) 一( b u “) = i d id ，在t 。时段购买a ，在t b 时段购买 b ) i ，| d jd j 在t 。时段! j ! j 买a ) ix 1 0 0 。 2 2 3 模型的意义 具有时间约束的交易规则模型的采掘，将使得决策者对消费者的行为分析由 定性转化为定量，从而提高决策质量，在实际应用中也具有重要的意义。上述模 型在销售分析中有着重要的意义。例如大多数在暑期购买电脑的顾客，都会在下 一学年开学前购买教学软件，将时段用月表示，此规则可表示为： 电脑，( 6 ，7 ， 8 ) ) 一f 教学软件， 9 ，1 0 ) ) 。通过挖掘大量此类具有时间约束的交易规则，商家对 顾客的行为了解将更为深刻，从而可以制定出更加合理的广告和营销策略。 2 3 具有确定性时间约束的交易规则采掘算法一 2 3 1a p f i o f i 算法基础 我们知道关联规则的挖掘分为两步“： ( 1 ) 找出所有频繁数据项集，即找出支持度超过指定阀值的数据项集； ( 2 ) 在频繁数据项集中生成候选关联规则，验证置信度后，生成关联规则。 在上述两步中，第一步是最关键的，下面介绍一种频繁数据项集的生成算法 a p r i o f i 算法。a p f i o d 算法使用一种称作逐层搜索的迭代方法，k _ 项集用于搜 索( k + 1 ) 一项集。首先找出频繁1 一项集的集合，记为l l 。l j 用于寻找频繁2 - 项集的 集合l 2 而l 2 用于寻找l 3 ，如此下去，直到不能找到频繁k - 项集合。找每个l k 都 需要扫描数据库一遍。a p r i o r i 算法可以描述如下m ： l l = 1 - i t e m s e t s ； f o r ( k = 2 ：l k 1 # a ；k + + ) d o b e g i n c k = a p r i o r i - g e no k l ) ； f o ra l lt r a n s a e t i o n st dd o b e g i n c t = s u b s e t ( c k ，t ) ； f o r a i lc a n d i d a t e sc c td o c c o u n t + + ： l4 e n d h = c c k lc c o u n t m m s u p e n d a n s w e r = uk l k ： a p r i o r i - g e n 函数以k 1 ( 所有( k - 1 ) _ 项集) 作为输入参数，返回所有k - 项集的集合 k ，以下两步实现： 第一步，连接( j o i n ) ： i n s e r ti n t oc k s e l e c tp i t e m l ，pi t e m 2 ，pi t e m ( k - 1 ) ，qi t e m ( k 1 ) f i - o mk i p ，l k - l q w h e r ep i t e m l = q i t e m l ，p i t e m k - 22q i t e m k 一2 ，p - i t e m ( k 1 ) m i ns u p p o r t ) ：) r e m m l = u k k 对生成候选集的e x _ a p r i o r i _ g e n 函数描述如下： p r o c e d u r e e x _ a p r i o r i _ g e n 阻i ，r a i n _ s u p p o r t ) f o re a c hi t e m s e t1 1 l k 1 f o re a c hi t e m s e t2d l k 一1 i f ( ( ( ，l 【l 】i t e m = 2 【1 1 i t e n l ) & & ( 1 1 【1 t i m e = 2 【1 】t i m e ) ) & & & & ( ( ，】 【k 一2 】i t e m = 如 k - 2 1i t e l n ) & ( ，1 【k - 2 t i m e = 2 【k - 2 t i m e ) ) & & ( ( ，1 【k - 1 i t e m 2 【k - 1 】i t e m ) i i ( ，l k 一1 1t i m e f 2 k - 1 】t i m e ) ) ) t h e n g = i ij o i nf 2 ： i f h a s _ i n f r e q u e n t _ s u b s e t ( c ，l k 1 ) t h e n d e l e t e c ； e l s ea d dct oc k ； r e t u r n c k h a s _ i n f r e q u e n t _ s u b s e t 过程用来测试非频繁子集，其描述如下： p r o c e d u r eh a si n f r e q u e n t _ s u b s e t ( c ：c a n d i d a t ek - i t e m s e t ，l k - 1 ：f r e q u e n t ( 1 【- 1 ) - i t e m s e o + + + r i s ep r i o rk n o w l e d g e f o re a c h ( k 1 ) 一s u b s e t sso fc i fs 畦l k - 1t h e n r e t u r n t r u e ； r e t u r ef a l s e 2 4 具有确定性时间约束的交易规则采掘算法二 在上一节中我们通过对a p r i o r i 算法进行扩展，实现了具有确定性时间约束的 交易规则的采掘。在很多情况下，a p r i o r i 算法的候选产生检查方法大幅度压缩 了候选项集的大小，并导致良好