（管理科学与工程专业论文）关联规则挖掘在电信经营中的应用.pdf

北京邮电大学硕士学位论文 关联规则挖掘在电信经营中的应用 摘要 电信业丰富的数据资源提供了数据挖掘应用的广阔空间。目前，数 据挖掘的相关技术已经十分成熟，涉及数据仓库、人工智能等各个方面。 数据挖掘通过一定算法对大量数据的处理，可以发现很多有用的信息， 给电信经营决策提供支持。其中，关联规则应用，或者说货蓝分析，可 以应用在增值业务相关性分析中。 论文主要就关联规则挖掘在电信业中的具体应用进行了论述。首先 论文提出了移动业务单维关联规则挖掘应用模型，这个模型可以有益于 发现不同的增值业务之间的关联性。使用了两种算法a p i r i o r 和f p 书唾 算法进行了挖掘，并对结果进行了分析。论文还使用了种兴趣度修剪 方法，可以修剪无用的规则，使规则更加集中。从挖掘结果可以看出， 这种应用可以对电信交叉营销提供一定的决策支持。 同时论文还探讨了多维关联规则挖掘在电信中的应用，提出了一定 的应用方法。论文定义了客户消费模式挖掘模型，从多谓词客户消费层 次、年龄、使用业务等方面进行相关性挖掘。论文对多维关联规则的算 法进行了探讨。 关键宇：移动业务单维关联规则挖掘兴趣度客户消费模式挖掘模型 北京邮电大学硕士学位沦文 h 一一 t h e a p p l i c a t i o n o f a s s o c i a t i o nr u l e m i n i n g i nt e l e c o m m u n i c a t i o n a b s t r a c t t h ea b u n d a n c eo fd a t as o u r c ei n t e l e c o m m u n i c a t i o n o p e r a t i o ng i v e s a h u g e a p p l i c a t i o nf o rd a t am i n i n g t e c h n i q u e so fd a t am i n i n gh a sb e e nd e v e l o p e dq u i c l d y ，s u c h a sd a t aw a r e h o u s e ，i n t e l l i g e n t m i n i n g u s i n gc e r t a i na l g o r i t h ml a r g ea m o u n to fd a t ai s p r o c e s s e d ，a n d s o m ev a l u a b l ei n f o r m a t i o nw i l lb ep r e s e n t e d ，w h i c h g i v e as u p p o r tf o r t e l e c o m m u n i c a t i nm a r k e t i n g a n da s s o c i a t i o nr u l em i n i n ge a r l b e a p p l i e di ns e a r c h i n gt h e r e l a t i v i t yo f v a l u e - a d d e ds e r v i c e t h ep a p e ri s m a i n l yd i s c u s s e dt h ea p p l i c a t i o no fr u l ea s s o c i a t i o nr u l em i n i n gi n t e l e c o m m u n i c a t i o n f i r s t ，as i n g l e d e m e n s i o nr u l em i n i n gm o d e li sp r o p o s e d ，w h i c hh e l p f i n d i n gt h er e l a t i v i t yo f d i f f e r e n tv a l u e a d d e ds e r v i c e a p i r o r ia l g o r i t h ma n df p a l g o r i t h m i su s e df o rm i n i n g p a p e ra n a l y z e dt h eo u t p u to ft h em i n i n g ，am e t h o do f c l i p p i n gi n t e r e s t r u l e si su s e dt od e c r e a s et h en u m b e ro fr u l e s ，a n dc e n t r a t et h er u l e s f r o mt h er e s u l to f a s s o c i a t i o nr u l e m i n i n g ，t h i sa p p l i c a t i o n c a n s u p p o r t t h e d e c i s i o n m a k i n g o f c r o s s - m a r k e t i n g a n dt h ea p p l i c a t i o no f m u l t i p l e d i m e n s i o nr u l em i n i n gi nt e l e c o m m u n i c a t i o ni sa l s o d i s c u s s e d ，i nt h i s p a p e r ，aw a y f o r a p p l i c m i o n i s s u g g e s t e d p a p e r d e f i n eac u s t o m e r c o n s u m em o d e m i n i n gm o d e l ，f r o m d i f f e r e n ta t t r i b u t e ss u c ha sc u s t o m e r c h a r g e l e v e l ，a g e ，s e r v i c e t h ea l g o r i t h mo fm u l t i p l e d i m e n s i o nr u l em i n i n gi sd i s c u s s e d k e yw o r d s ：s i n g l e d e m e n s i o nr u l e m i n i n gm o d e l ，i n t e r e s t ，c u s t o m e rc o n s u m e m o d e m i n i n g m o d e l - 2 - 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他教育机 构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 己在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名 日期：幽垃互：3 幽 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即：研 究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅；学 校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段 保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论文 注杯本学位论文不属于保密范围，适用本授权书。 本人签名：至鍪整日期：兰型立! i ：皇立 导师签名：二一f 1 期： 牛 北京邮电大学硕士学位论文关联规则挖掘在电信经营中的作用 1 1 研究背景 第一章研究背景及课题 随着国内电信市场竞争的日趋激烈，电信运营商的经营模式逐渐从“技术驱 动”向“市场驱动”“客户驱动”转化。这就要求运营商要采取以客户为中心的策 略，根据客户的实际需求提供多样化、层次化、个性化的服务解决方案。因此，客 户关系管理( c r m ) 成了电信运营商增加收入和利润，提高客户满意度、忠诚度的有 效工具。在客户关系管理的流程中，为了准确、及时地进行经营决策，必须充分获 取并利用相关的数据信息对决策过程进行辅助支持。近几年迅速发展起来的数据挖 掘技术就是实现这一目标的重要手段。 通过数据挖掘我们可以： l ，客户分析：不断收集客户行为数据，帮助企业准确地回答以下问题：新客户 和老客户相比，谁会为我们带来更多的利润? 大客户存在的价值是什么? 不同年龄 段的客户对企业的价值有何不同? 客户的忠诚度受哪些因素影响? 2 客户分类：根据客户的消费模式、消费习惯、消费频度等特征对客户进行分 类，使企业能识别客户类及其特征，定义每个客户类的收益率。 3 市场定向：帮助企业面向特定的客户段，采用相应的端对端市场宣传策略， 吸引新的客户和有利可图的客户，同时牢牢保持有利可图的老客户并增加与他们的 业务量。 4 建立预测模型：预测模型帮助企业的市场促销部门通过对客户和市场变量的 调查，制定更准确的市场策略，开展更成功的市场攻势。通常，预测模型的建立需 要利用多种统计工具来解释客户行为，并对其未来的市场动向作出预测。 数据挖掘是根据企业的既定业务目标和存在的问题，对大量的业务数据进行探 索，揭示其中隐藏的规律，并将其模型化，指导并应用于企业的实际经营。 数据挖掘是建立在数据仓库基础上的高层应用，但数据挖掘跟数据仓库的其它 一些应用如0 l a p 分析、预定义报表和即席查询等有很大的区剐。后三者通常是用户 根据已知的情况对所关心的业务指标进行分析；而前者则是在业务问题和目标明确 但考察的问题不清楚时，对数据进行探索，揭示隐藏其中的规律性，进而将其模型 第t 贞共4 9 页 北京邮电大学硕士学位论文 关联规则挖掘在电詹经营中的作用 化。 数据挖掘是个循环往复的过程，通常涉及数据准备、建立模型、评估和解释 模型、运用祁巩固模型等步骤。 c1 ) 数据准备：数据准备工作包括数据的选择f 选择相关和合适的数据) 、探 索( 了解数据分布情况和异常数据等) 、修正( 包括缺失数据的插值等) 和变换( 离 散值数据与连续值数据的相互转换，数据的分组分类，数据项的计算组台等) 。 ( 2 ) 建立模型：选取数据挖掘工具提供的算法并应用于准备好的数据，选取相 应参数，生成模型。 ( 3 ) 评估和解释模型：对模型进行比较和评估，生成一个相对最优模型，并对 此模型用业务语言加以解释。 ( 4 ) 运用和巩固模型：对模型在实际应用中的表现进行监控，如果模型表现不 好，则对模型作进步的考察和修正，以反映业务运作规律的变化。 电信运营商拥有许多成熟的数据库应用系统，如网管系统、财务系统、计费账 务系统、11 2 障碍管理系统、缴费销账系统等，并产生了大量的业务处理数据。如果 针对客户关系管理相关决策分析的需求，对这些数据进行重组整合，就能充分利用 这些宝贵的数据，体现信息的真正价值。 数据挖掘技术在电信行业客户关系管理的主要应用领域如下： 客户消费模式分析 客户消费模式分析( 如固话话费行为分析) 是对客户历年来长话、市话、信息 台的大量详单、数据以及客户档案资料等相关数据进行关联分析，结合客户的分类， 可以从消费能力、消费习惯、消费周期等诸方面对客户的话费行为进j 亍分析和预测， 从雨为固话运营商的相关经营决策提供依据。 客户市场推广分析 客户市场推广分析( 如优惠策略预测仿真) 是利用数据挖掘技术实现优惠策略 的仿真，根据数据挖掘模型进行模拟计费和模拟出账，其仿真结果可以揭示优惠策 略中存在的问题，并进行相应的调整优化，以达到优惠促销插动的收益最大化。 客户欠费分析和动态防欺诈 通过数据挖掘，总结各种骗费、欠费行为的内在规律，并建立一套欺诈和欠费 行为的规则库。当客户的话费行为与该库中规则吻合时，系统可以提示运营商相关 部门采取措施，从而降低运营商的损失风险。 客户流失分析 根据已有的客户流失数据，建立客户属性、服务属性、客户消费情况等数据与 客户流失概率相关联的数学模型，找出这些数据之间的关系，并给出明确的数学公 第2 页共4 9 页 北京邮电大学硕士学位论文 关联规则挖掘在电信经营中的作用 式。然后根据此模型来监控客户流失的可能性，如果客户流失的可能性过高，则通 过促销等手段来提高客户忠诚度，防止客户流失的发生。这就彻底改变了以往电信 运蕾商在成功获得客户以后无法监控客户流失、无法有效实现客户关怀的状况。 1 2 研究内容 关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。它在数据挖掘 中是一个重要的课题，最近几年已被业界所广泛研究。 关联规则挖掘的一个典型例子是购物篮分析。关联规则研究有助于发现交易数 据库中不同商品( 项) 之间的联系，找出顾客购买行为模式，如购买了某商品对 购买其他商品的影响。分析结果可以应用于商品货架布局、货存安排以及根据购买 模式对用户进行分类。 与经典的关联规则的挖掘研究相比，其研究具有下列发展趋势： 一是从单一概念层次关联规则的发现发展到多概念层次的关联规则的发现。即 挖掘规则可以作用到数据库不同层面上。例如，在分析超市销售事务数据库过程中， 若单单从数据库中的原始字段，如面包、牛奶等进行挖掘，可能很难发现令人感兴 趣的规则。这时如果把一些抽象层次的概念也考虑进去，比如面包和牛奶更抽象的 概念：食品，则有可能发现更新的更为抽象的规则。所以研究在数据库中不同的抽 象层次上挖掘规则是数据挖掘的新的研究内容。 二是提高算法效率。共有三种提高效率的思路：一种技术是减少数据库扫描次 数，这种技术对效率会有巨大提高。一种技术是利用采祥技术，对要挖掘的数据集 合进行选择。一种技术是采用并行数据挖掘。因为大规模的数据库经常分布在若干 网络节点上，并行挖掘技术显然能提高效率。这对于在i n t e m e t 上的海量数据挖掘研 究具有重要的意义。 关联规则挖掘在电信行业有着广阔的应用前景。本文主要从以下几方面探讨了 关联规则挖掘在电信业的应用，提出相应的应用模型和算法指导。 单维关联规则数据挖掘 根据客户的消费行为特点，对客户使用的不同语音增值业务之间的关联性进行 了建模研究。这种应用将对电信企业交叉营销产生提供一定的决策支持。 多维关联规则数据挖掘 研究客户月消费额、在网时长和各种业务、营销组合、联系人数等之间是否存 在什么关联? 从中找出一种客户消费模式。 第3 页共4 9 页 北京邮电大学硕士学位论文 关联规则挖掘在电信经营中的作用 数据挖掘己广泛应用于社会的各个领域，特别是商业领域。但是在电信领域的 研究还很少。本论文主要研究了关联规则挖掘在电信增值业务领域的应用。根据电 信增值业务数据特点，建立一套适合的关联规则挖掘模型。 从具体算法的优劣性来说，很多算法已经是很成熟很经典的算法，没有一种算 法显然优于另外种方法，而只有可能的是在某一个问题上，某一种方法优于别的 方法。而重要的是，在解决具体问题的时候，怎样根据领域问题的特点，找到合适 的训练数据，应用怎样的过程来解决问题。因此，本文中对于电信增值业务的关联 规则分析，其主要的研究在于，针对这一领域的问题，找到哪些描述用户行为的数 据，应用怎样一个过程来解决该问题，而并不着眼于具体算法的改进。 本论文的主要结构如下： 第一章主要对论文的研究背景以及研究内容进行了简单介绍。 第二章从关联规则相关的技术方面，对数据仓库及关联规则作了一定的阐述。 其中数据仓库方面主要介绍了数据仓库的定义、系统构成和技术。关联规则则详细 阐述了定义，相关量的定义和计算，关联规则的发展历史，以及相关算法的主要原 理。 接下来第三章主要就关联规则在电信业中的应用展开论述。根据得到某地市的 b o s s 移动经营数据，研究了移动各种增值业务之间的相关性，主要运用了单维关联 规则挖掘方法，其中使用了a p i r i o r 和f p 树两种挖掘算法，作了一些有意义的尝试， 并使用了一个兴趣度修剪方法，使规则更加集中。 第四章进一步深入地探讨了关联规则在电信业中的应用。从单维关联规则引申 开，进行多维关联规则挖掘的应用。论文定义了多维关联规则挖掘的定义，阐述了 三种算法思想。提出了种客户消费模式挖掘方法。 2 1 数据仓库 第二章数据仓库及关联规则挖掘简介 数据仓库是一个面向主题的、具有集成性和相对稳定性、反映历史变化的数据 集合，用于支持管理决策。数据仓库面向分析型数据处理，它不同于企业现有的操 第4 页菇4 9 页 北束部电大学硕士学位论文 关联规剐挖掘在电信经营中的作用 作型数据库；数据仓库是对多个异构的数据源的有效集成，集成后按照主题进行重 组，并包含历史数据，而且存放在数据仓库中的数据一般不再修改。 l 、面向主题 操作型数据库的数据组织面向事务处理任务各个业务系统之间各自分离，而 数据仓库中的数据是按照一定的主题域进行组织的。主题是个抽象的概念，是指 用户使用数据仓库进行决策时所关心的重点方面，一个主题通常与多个操作型信息 系统相关。 2 集成性 面向事务处理的操作型数据痒通常与某些特定的应用相关，数据库之间相互独 立，并且往往是异构的。而数据仓库中的数据是在对原有分散的数据库数据抽取、 清理的基础上经过系统加工、汇总和整理得到的，必须消除源数据中的不致性， 以保证数据仓库内的信息是关于整个企业致的全局信息。 3 相对稳定性 操作型数据库中的数据通常实时更新，数据根据需要及时发生变化。数据仓库 的数据主要供企业决策分析之用，所涉及的数据操作主要是数据查询，一旦某个数 据进入数据仓库以后，一般情况下将被长期保留，也就是数据仓库中一般有大量的 查询操作，但修改和删除操作很少，通常只需要定期加载、刷新。 4 反映历史变化 操作型数据库主要关心当前某一个时间段内的数据，而数据仓库中的数据通常 包含历史信息，系统记录了企业从过去某一时点( 如开始应用数据仓库的时点) 到 目前的各个阶段的信息，通过这些信息，可以对企业的发展历程和未来趋势做出定 量分析和预测。 企业数据仓库的建设，以现有企业业务系统和大量业务数据的积累为基础。数 据仓库不是静态的概念，只有把信息及时交给需要这些信息的使用者，供他们做出 改善其业务经营的决策，信息才能发挥作用。而把信息加以整理归纳和重组，并及 时提供给相应的管理决策人员，是数据仓库的根本任务。 2 1 1 数据仓库系统的构成 个典型的企业数据仓库系统通常包含数据获取层、数据存储层和数据访蚵层 三层： 1 数据获取层：对b o s s 、m i s 、网管和其它外部数据源中的数据进行抽取、清 洗、转换，并加载到数据仓库。 第5 页共4 9 页 北京邮电大学硕士学位论文 关联规则挖掘在电洁经营巾的作墙 2 数据存储层：实现对数据仓库中数据和元数据的集中存储与管理，并可根据 需求建立面向部门和主题的数据集市。 3 ，数据访问层：通过多样化的前端分析展示工具，实现对数据仓库中数据的分 析和处理，形成市场经营和决策工作所需要的科学、准确、及时的业务信息和知识。 2 12 数据仓库的关键技术 o l a p 技术 当今的数据处理大致可以分成两大类：联机事务处理o l t p ( o n l i n et r a n s a c t i o n p r o c e s s i n g ) 、联机分析处理o l a p ( o n l i n ea n a l y t i c a lp r o c e s s i n g ) 。o l t p 是传 统的操作型数据库的主要应用，主要是基本的日常事务处理，例如计费帐单交易等。 o l a p 是数据仓库系统的主要应用，侧重决策支持，支持复杂的分析操作，以求剖析 数据，使用户能从多个角度、多侧面她观察数据库中的数据，从而深入理解包含在 数据中的信息。 o l a p 的目标是满足决策支持或者满足在多维环境下特定的查询和报表需求，它 的技术核心是“维”( d i m e n s i o n ) 这个概念，通过把一个实体的多项重要属性定义为 多个维，使用户能对不同维上的数据进行比较。 o l a p 的基本多维分析操作有钻取( r o l lu p 和d r i i id o w n ) 、切片( s l i c e ) 、切 块( d i c e ) 以及旋转( p i v o t ) 等。钻取是改变维的层次，变换分析的粒度，它包括 向上钻取( r o l lu p ) 和向下钻取( d r i l ld o w n ) 。切片和切块是在一部分维上选定 值后，关心度量数据在剩余维上的分布。旋转是变换维的方向，即在表格中重新安 排维的放置( 例如行列互换) 。 o l a p 有多种实现方法，根据存储数据的方式不同可以分为r o l a p 、m o l a p 、h o l a p 。 r o l a p 表示基于关系数据库的o l a p 实现( r e l a t i o n a lo l a p ) 。以关系数据库为核心， 以关系型结构进行多维数据的表示和存储。m o l a p 表示基于多维数据组织的o l a p 实 现( m u l t i d i m e n s i o n a lo l a p ) ，以多维数据组织方式为核心。多维数据在存储中将 形成“立方块( c u b e ) ”的结构，在m o l a p 中对“立方块”的“旋转”、“切块”、 “切片”是产生多维数据报表的主要技术。h o l a p 表示基于混合数据组织的o l a p 实 现( h y b r i do l a p ) 。如低层是关系型的，高层是多维矩阵型的。这种方式具有更好 的灵活性。 数据挖掘技术 数据挖掘是从数据库或数据仓库中发现并提取隐藏在其中的信息的一种新技 术。它建立在数据仓库基础之上，面向非专业用户，定位于桌面，支持即兴的随机 第6 其共4 9 页 北京邮电大学硕士学位论文 关联规则挖掘在电信经营中的作用 查询。数据挖掘技术能自动分析数据，对它们进行归纳性推理和联想，寻找数据间 内在的某些关联，从中发掘出潜在的、对信息预测和决策行为起着十分重要作用的 模式，从而建立新的业务模型，以达到帮助决策者制定市场策略、做出正确决策的 目的。数据挖掘技术涉及数据库、人工智能、机器学习、神经计算和统计分析等多 种技术。 在数据仓库基础上挖掘的知识通常以图表、可视化界面等形式表示出来，但所 挖掘的知识并不都是有意义的。必须进行评价、筛选和验证，把有意义的知识放到 知识库中，随着时间的推移将积累更多的知识。知识库根据挖掘的知识类型分为总 结性知识、关联性知识、分类模型知识、聚类模型知识，这些知识通过相应挖掘算 法得到。 2 2 关联规则挖掘简介 2 2 1 定义 设i = i 1 ，i 2 ，i m ) 是二进制文字的集合，其中的元素称为项( i t e m ) 。记d 为 交易( t r a n s a c t i o n ) t 的集合，这里交易t 是项的集合，并且t g i 。对应每一个交易 有唯一的标识，如交易号，记作t i d 。设x 是一个i 中项的集合，如果x t ，那么称 交易t 包含x 。 一个关联规则是形如x = 坷的蕴涵式，这里x d ，y c i ，并且x n y = 巾。规则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 ) = i t ：x u y g t ，t d f i d l 规则x y 在交易集中的可信度( c o n f i d e n c e ) 是指包含x 和y 的交易数与包含 x 的交易数之比，记为c o n f i d e n c e ( x j y ) ，即 c o n f i d e n c e ( x = ，y ) = f t ：x u y g t ，t e d ) j l ( t ：x c _ m t d | 给定一个交易集d ，挖掘关联规则问题就是产生支持度和可信度分别大于用户给 定的最小支持度( m i n s u p p ) 和最小可信度( m i n c o n f ) 的关联规则。 关联规则挖掘的一个典型例子是购物篮分析。关联规则研究有助于发现交易数 据库中不同商品( 项) 之间的联系，找出顾客购买行为模式，如购买了某一商品对 购买其他商品的影响。分析结果可以应用于商品货架布局、货存安排以及根据购买 第7 页共4 9 页 北京郝电大学硕士学位论文 关联规则挖掘在电信经营中曲作用 模式对用户进行分类。 问题i 什么商品组或集合顾客多半会在一次购物时同时购买? 图表2 - 1 关联规则图示 考察一些涉及许多物品的事务：事务l 中出现了物品甲，事务2 中出现了物品 乙，事务3 中则同时出现了物品甲和乙。那么，物品甲和乙在事务中的出现相互之 间是否有规律可循昵? 在数据库的知识发现中，关联规则就是描述这种在一个事务 中物品之间同时出现的规律的知识模式。更确切的说，关联规则通过量化的数字描 述物品甲的出现对物品乙的出现有多大的影响。 现实中，这样的例子很多。例如超级市场利用前瑞牧款机收集存储了大量的售 货数据，这些数据是一条条的购买事务记录，每条记录存储了事务处理时间，顾客 购买的物品、物品的数量及金额等。这些数据中常常隐含形式如下的关联规则：在 购买铁锤的顾客当中，有7 0 的人同时购买了铁钉。这些关联规则很有价值，商场 管理人员可以根据这些关联规则更好地规划商场，如把铁锤和铁钉这样的商品摆放 在一起，能够促进销售。 有些数据不像售货数据那样很容易就能看出一食事务是许多物品的集合，但稍 微转换一下思考角度，仍然可以像售货数据一样处理。比如人寿保险，份保单就 是一个事务。保险公司在接受保险前，往往需要记录投保人详尽的信息，有时还要 到医院做身体检查。保单上记录有投保人的年龄、性别、健康状况、工作单位、： 作地址、工资水平等。这些投保人的个人信息就可以看作事务中的物品。通过分析 这些数据，可以得到类似以下这样的关联规则：年龄在4 0 岁以上，工作在a 区的投 保人当中，有4 5 的人曾经向保险公司索赔过。在这条规则中，“年龄在4 0 岁以 上”是物品甲，“工作在a 区”是物品乙，“向保险公司索赔过”则是物品丙。可 以看出来，a 区可能污染比较严重，环境比较差，导致工作在该区的人健康状况不好， 第8 页共4 9 页 托京邮电大学硕士学位论文 关联规则挖掘在电信经营中的作用 索赔率也相对比较高。 1 可信度( c o n f i d e n c e ) 设w 中支持物品集a 的事务中，有c 的事务同时也支持物品集b ，c ? 称为关 联规则a b 的可信度，简单她说，可信度就是指在出现了物品集a 的事务t 中，物 品集b 也同时出现的概率有多大。如上面所举的铁锤和铁钉的例子，该关联规则的 可信度就回答了这样一个问题：如果一个顾客购买了铁锤，那么他也购买铁钉的可 能性有多大呢? 在上述例子中，购买铁锤的顾客中有7 0 的人购买了铁钉，所以可信 度是7 0 7 。 z ，支持度( s u p p o r t ) 设w 中有s 的事务同时支持物品集a 和b ，s 称为关联规则a b 的支持度。 支持度描述了a 和b 这两个物品集的并集c 在所有的事务中出现的概率有多大。如 果某天共有1 0 0 0 个顾客到商场购买物品，其中有i 0 0 个顾客同时购买了铁锤和铁钉， 那么上述的关联规则的支持度就是1 0 。 3 期望可信度( e x p e c t e d c o n f i d e n c e ) 设w 中有e 的事务支持物品集b ，e 称为关联规则a b 的期望可信度。期望 可信度描述了在没有任何条件影响时，物品集b 在所有事务中出现的概率有多大。 如果某天共有1 0 0 0 个顾客到商场购买物品，其中有2 0 0 个顾客购买了铁钉，则上述 的关联规则的期望可信度就是2 0 。 4 作用度( l i f t ) 作用度是可信度与期望可信度的比值。作用度描述物品集a 的出现对物品集b 的出现有多大的影响。因为物品集b 在所有事务中出现的概率是期望可信度；丽物 品集b 在有物品集a 出现的事务中出现的概率是可信度，通过可信度对期望可信度 的比值反映了在加入“物品集a 出现”的这个条件后，物品集b 的出现概率发生了 多大的变化。在上例中作用度就是7 0 2 0 = 3 5 。 用p ( a ) 表示事务中出现物品集a 的概率，p ( b a ) 表示在出现物品集a 的事务中， 出现物品集b 的概率，则以上四个参数可用公式表示，如下表。 名称 描述公式 可信度 在物品集a 出现的前提下，b 出 p ( b | a ) 现的概率 支持废 物品集a 、b 共同出现的概率p ( a n b 、 期望可信度物品集b 出现的概率 p ( b ) 作用度可信度对期望可信度的比值p ( b a ) p ( b ) 图表2 - 1 四个参数的计算公式 第9 页共4 9 页 北京部电大学硕士学位论文 关联规则挖掘在电信经营中豹作用 可信度是对关联规则的准确度的衡量，支持度是对关联规则重要性的衡量。支 持度说明了这条规则在所有事务中有多大的代表性，显然支持度越大，关联规则越 重要。有些关联规则可信度虽然很高，但支持度却很低，醴明该关联规则实用的机 会很小，因此也不重要。 期望可信度描述了在没有物品集a 的作用下，物品集b 本身的支持度；作用度 描述了物品集a 对物品集b 的影响力的大小。作用度越大，说明物品集b 受物品集a 的影响越大。一般情况，有用的关联规则的作用度都应该大于l ，只有关联规则的可 倍度大于期望可信度，才说明a 的出现对b 的出现有促进作用，也说明了它们之间 某种程度的相关性，如果作用度不大于l ，则此关联规则也就没有意义了。 2 22 关联规则发展简介 1 9 9 3 年，i b ma h n a d mr e s e a r c hc e n t e r 的a g r a w a l 等人提出了关联规则这一重 要课题，并展开了深入的研究，首先提出了a i s 算法，对销售的事务数据集进行挖掘， 并给出了形式化的关联规则描述，提出了支持度一可信度框架生成频繁集和规则的 算法。 1 9 9 4 年，a g r a w a l 等人有对a i s 算法进行了改进，提出了a p r i o r i 算法，这是 关联规则挖掘的发展过程中一个具有里程碑意义的算法，它基于一个先验规则：如果 一个k + 1 项集是频繁的，那么其k + 1 个k 项子集也必定是频繁的。a p r i o r i 算法采用 逐层遥代的方法，自底向上，发现全部的频繁集，在很大程度上提高了关联觌i j 挖 掘的效率和时空开销。其后很多的算法都是在a p r i o r i 算法基础上进行改进，谋求 性能和效率的提高。例如a p r i o r i t i d 等算法，通过存储项集的支持事务集，这样两 个项集做连接时只要求其支持事务集的交集就可以得到支持度，而不需要再一次遍 历全部事务集，但是其需要很大的空间来存储其支持事务集。 1 9 9 5 年，p a r k 等人提出了d h p ( 动态啥希裁剪) 算法，对事务集通过哈希裁剪， 将由于项数比较小的事务从哈希树上剪掉( 或加标志) ，从而减少了以后需要遍历的 事务数。s a v a s e r e ) 等人提出了分区的算法，将超大事务集分块，每一块采用以前的 算法进行局部频繁集生成，然后在进行处理产生全局频繁集 1 9 9 7 年z a k i 为首等人研究快速关联规则挖掘的新算法，提出了e c l a t ，m a x e c l a t c 1 i q u e ，m a x c l i q u e 四种算法，其主要采用了项集聚类、格遍历和事务聚类等技术。 2 0 0 0 年j i a w e ih a n 提出了不采用候选项集的f p t r e e 算法，通过f p t r e e 存储 事务集，最大程度的压缩数据并保证数据的完整性，通过对f p t r e e 的一次遍历生 成全部的频繁集。 第1 0 页共4 9 页 北京邮电大学硕士学位论文 关联规则挖掘在电信经营中的作用 2 0 0 1 年r o b e r tc a s t e l 等人提出了通过隐马尔可夫链的模拟，发现最大后验可 能的马尔可夫覆盖挖掘关联规则的m a m b o 算法。其首先求得所有属性的n 个最大马 尔可夫覆盖，然后由马尔可夫覆盖生成关联规则，然后对所有生成的关联规则进行 过滤，过滤掉对超规则没有提高改进的子规则。其主要涉及统计分析的一些理论和 方法。 2 0 0 2 年q i n g h u az o u 等人提出模式分解的关联规则挖掘算法，以往的关联规则 挖掘算法都只记录频繁集，舍弃非频繁集，模式分解算法中不但记录频繁集，也记 录非频繁集，并且将记录的非频繁集的元素用于事务的模式分解中，这样事务中就 不存在非频繁集，很大程度上提高了挖掘的速度。 2 0 0 3 年z a k i 等人提出了采用异项集的垂直挖掘算法，主要适用于稠密事务集， 对于稀疏事务集就不适合了。其原理主要采用类似a p r i o r i t i d 算法的t i d 集，但存 储的是集合之间的相异事务集d i f f s e t 欧阳为民在1 9 9 9 年也提出了基于垂直数据分 布的关联规则的高效发现算法2 0 0 2 年则提出了基于垂直挖掘的列分区的关联规则 挖掘算。 233 算法 a 铲a w a l 等于1 9 9 3 年首先提出了挖掘顾客交易数据库中项集间的关联规则问题， 其核心方法是基于频集理论的递推方法。以后诸多的研究人员对关联规则的挖掘问 题进行了大量的研究。他们的工作包括对原有的算法进行优化，如引入随机采样、 并行的思想等，以提高算法挖掘规则的效率；提出各种变体，如泛化的关联规则、 周期关联规则等，对关联规则的应用进行推广。 2 3 3 1 核心算法 a g r a w a l 等在1 9 9 3 年设计了一个基本算法，提出了挖掘关联规则的一个重要方 法一这是一个基于两阶段频集思想的方法，将关联规则挖掘算法的设计可以分解 为两个子问题： 1 ) 找到所有支持度大于最小支持度的项集( i t e m s e t ) ，这些项集称为频集( f r e q u e n t i t e m s e 0 - 2 ) 使用第1 步找到的频集产生期望的规则。 这里的第2 步相对简单一点。如给定了一个频集y = 乃厶厶， 越，再仨厶产生只 包含集合胁，如一，埘中的项的所有规则( 最多k 条) ，其中每一条规则的右部只有 篇1 1 页共4 9 页 ， 北京邮电大学顷士学位论文 关联规则挖掘在电信经营中的作用 一项，( 即形如f 卜t 7 等 ，豆受) ，这里采用的是规则的定义。一旦这些规则被生成， 那么只有那些大于用户给定的最小可信度的规则才被留下来。对于规则右部含两个 以上项的规则，在其以后的工作中进行了研究，本文后面考虑的是这种情况。 为了生成所有频集，使用了递推的方法。其核心思想如下： ( 1 ) l t ； l a r g e1 一i t e m s e t s ) ； ( 2 )f o r ( k = - 2 ；l k l 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 o ra l lt r a n s a c t i o n st 苣dd o b e g i n ( 5 )c t = s u b s e t ( c k ，t ) ；事务t 中包含的候选集 ( 6 ) f o ra l lc a n d i d a t e sc c td o ( 7 )c c o 岫t + + ； ( 8 ) e n d ( 9 ) l k = c e c 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 = w k l k ； 首先产生频繁1 项集l l ，然后是频繁2 项集l 2 ，直到有某个r 值使得l r 为空， 这时算法停止。这里在第k 次循环中，过程先产生候选k 项集的集合c k ，c k 中的每 一个项集是对两个只有一个项不同的属于l k 。的频集做一个( k 一2 ) 一连接来产生的。c k 中的项集是用来产生频集的候选集，最后的频集l k 必须是c k 的一个子集。c k 中的 每个元素需在交易数据库中进行验证来决定其是否加入l k ，这里的验证过程是算法 性能的一个瓶颈。这个方法要求多次扫描可能很大的交易数据库，即如果频集最多 包含l o 个项，那么就需要扫描交易数据库1 0 遍，这需要很大的i o 负载。 在论文中，a g r a w a l 等引入了修剪技术( p r u n i n g ) 来减小候选集c k 的大小，由 此可以显著地改进生成所有频集算法的性能。算法中引入的修剪策略基于这样一个 性质：一个项集是频集当且仅当它的所有子集都是频集。那么，如果c k 中某个候选 项集有一个化一1 ) 一子集不属于l k _ l ，则这个项集可以被修剪掉不再被考虑，这个修剪 过程可以降低计算所有的候选集的支持度的代价。文中，还引入杂凑树( h a s h t r e e ) 方法来有效地计算每个项集的支持度。 2 3 3 2 频集算法的几种优化方法 虽然a p r i o r i 算法自身已经进行了一定的优化，但是在实际的应用中，还是存在 不令人满意的地方，于是人们相继提出了一些优化的方法。 第1 2 页共4 9 页 北京邮电大学硕士学位论文 关联规则挖掘在电信经营中的作用 1 基于划分的方法。s a v a s e r e 等设计了一个基于划分( p a r t i t i o n ) 的算法，这个算 法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对它生成 所有的频集，然后把产生的频集合并，用来生成所有可能的频集，最后计算这些项 集的支持度。这里分块的大小选择要使得每个分块可以被放入主存，每个阶段只需 被扫描一次。而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保 证的。上面所讨论的算法是可以高度并行的，可以把每一分块分别分配给某一个处 理器生成频集。产生频集的每一个循环结束后，处理器之间进行通信来产生全局的 候选k 项集。通常这里的通信过程是算法执行时间的主要瓶颈：而另一方面，每个 独立的处理器生成频集的时间也是一个瓶颈。其他的方法还有在多处理器之间共享 一个杂凑树来产生频集。更多的关于生成频集的并行化方法可以在 2 1 1 , 1 7 1 中找到。 2 基于h a s h 的方法。一个高效地产生频集的基于杂凑( h a s h ) 的算法由p a r k 等提 出来。通过实验我们可以发现寻找频集主要的计算是在生成频繁2 项集l k 上，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 的算法相当简单并显著地减少了1 7 0 代价，但是一个很大的缺点 就是产生的结果不精确，即存在所谓的数据扭i 拍( d a t as k e w ) 。分布在同一页面上的数 据时常是高度相关的，可能不能表示整个数据库中模式的分布，由此而导致的是采 样5 的交易数据所花费的代价可能同扫描一遍数据库相近。l i n 和d u n h a m 讨论了 反扭i 掘( a n t i s k e w ) 算法来挖掘关联规则，在那里他们引入的技术使得扫描数据库的次 数少于2 次，算法使用了一个采样处理来收集有关数据的次数来减少扫描遍数。 b r i n 等提出的算法使用比传统算法少的扫描遍数来发现频集，同时比基于采样 的方法使用更少的候选集，这些改进了算法在低层的效率。具体的考虑是，在计算 k 项集时，一旦我们认为某个( k + 1 ) 项集可能是频集时，就并行地计算这个( k + 1 ) 一项 集的支持度，算法需要的总的扫描次数通常少于最大的频集的项数。这里他们也使 用了杂凑技术，并提出产生“相关规则”( c o r r e l a t i o n r u l e s ) 的一个新方法，这是基 于他们的3 1 z 作基础上的。 4 减少交易的个数。减少用于未来扫描的事务集的大小。一个基本的原理就是 当一个事务不包含长度为k 的大项集，则必然不包含长度为k + 1 的大项集。从而我 们就可以将这些事务移去，这样在下一遍的扫描中就可以要进行扫描的事务集的个 数。这个就是a p r i o r i t i d 的基本思想。 第1 3 页共4 9 页 北京邮电大学硕士学位论文 关联规则挖掘在电信经营中的作用 2 3 3 3 其他的频集挖搋方法 上面我们介绍的都是基于a p f i o n 的频集方法。即使进行了优化，但是a d r i o r i 方 法一些固有的缺陷还是无法克服： 1 ) 可能产生大量的候选集。当长度为1 的频集有1 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 设成一个很低的值，那么