硕士论文-面向客户流失预测的关联规则挖掘算法应用研究.pdf

河北工业大学 硕士学位论文 面向客户流失预测的关联规则挖掘算法应用研究 姓名 罗巧玲 申请学位级别 硕士 专业 管理科学与工程 指导教师 李杰 20071001 河北工业大学硕士学位论文 i 面向客户流失预测的关联规则挖掘算法应用研究面向客户流失预测的关联规则挖掘算法应用研究 摘摘 要要 随着我国电信企业运营机制的全面调整 电信业竞争更激烈 电信企业之间的争夺加 剧了客户离网行为 客户离网成为影响电信公司经营状况的一个重要因素 利用数据挖掘 技术科学地分析那些已经流失的客户的特征 从而预测在网客户的流失倾向 已成为电信 业的一个重要研究内容 而关联规则挖掘算法基于自身的诸多优势 成为目前电信客户流 失预测应用中最具有前景的数据挖掘技术之一 也得到了越来越多研究者的关注 本文通过对电信业客户流失预测和关联规则挖掘算法的文献综述 分析了现有研究中 仍然存在的问题 并重点对现有关联规则挖掘算法无法高效率地对数量少 但客户价值大 的电信客户进行流失预测进行了剖析 提出了一种基于数据属性约减和概率的加权多维关 联规则挖掘改进算法 并进行了实验仿真 验证了算法的有效性 本文的具体贡献有如下几个方面 第一 通过对电信业客户流失预测及关联规则挖掘算法的研究综述 分析了现有关联 规则挖掘算法的分类和关联规则价值的衡量 并主要针对现有多维关联规则挖掘算法进行 客户流失预测时的优缺点进行了比较分析 指出了目前电信业数据复杂 挖掘效率低下 而且算法尚未对电信业中数量少 但价值大的流失客户给予足够重视 影响了客户流失预 测的效果 第二 针对传统算法挖掘效率低下 且忽视了数量少但价值大的客户流失问题 提出 了一种基于属性约减和概率的加权多维关联规则改进算法 其基本思路是 首先对价值大 的客户利用基于粗集的属性约减方法进行属性约减 组成数据表 然后引入了基于概率的 加权关联规则的概念 定义和公式 来挖掘那些数量很少但价值很大的流失客户的关联规 则 并用提升度来衡量关联规则 以得到客户流失的强关联规则 第三 使用Powerbuilder6 5编程 对提出的改进算法进行了实验仿真与测试 并与 传统的多维关联规则挖掘算法 Apriori算法 进行比较 提高了客户流失预测的效率 同时实验显示 改进算法能够挖掘出传统算法所不能挖掘的数量少但价值大的客户的关联 规则 使电信运营商更有针对性的挽留大价值客户 显示出了更好的预测效果 关键词 关键词 客户流失 关联规则 属性约减 加权关联规则 多维关联规则 面向客户流失预测的关联规则挖掘算法应用研究 ii RESEARCH ON ASSOCIATION RULE MINING ALGORITHM APPLICATION IN CUSTOMER CHURN PREDICTION ABSTRACT With the comprehensive adjustment of the telecommunication enterprises in China the competition in Telecommunication industry is more severe The competition leads to the customer churning which becomes one of the important elements to reduce the profit of the telecommunication enterprise Then using data mining to scientifically analyze the characteristics of the churned customer whereby to predict the churn tendency of the existing customer has become an important research in Telecommunication industry And association rule mining technology based on its so many advantages turns into one of the most prospective data mining technology in customer churn prediction and receives more and more attention from the researcher This dissertation analyzes the problems in existing research via the literature review of the customer churn prediction in telecommunication industry and association rule algorithm and emphasizes that the existing association rule algorithms can not mining the rules of the few churned customers with big value and the efficiency is low Accordingly this dissertation brings forward an improved multidimensional association rule algorithm based on attribute reduction and probability weighted item then the approach is experimentally evaluated which suggest that approach is fairly effective The contributions of this dissertation are as follows Firstly by reviewing some of research literature related to customer churn prediction and association rule mining analyzes the classification and value evaluation of existing algorithm compares the advantages and disadvantages of the existing multidimensional association rule approach in customer churn prediction points out that the telecommunication industry data is redundancy and those algorithms are inefficient moreover did not attach importance to few churned customers with big value which lead to the inefficiency in customer churn prediction Secondly according to the previous analysis a novel multidimensional association rule algorithm based on attribute reduction and probability weighted item is put forward The main 河北工业大学硕士学位论文 iii idea is as follows Firstly do attribute reduction with the data of big value customers to form a table subsequently introduce the conception definition and formula of the improved algorithm to mine the rules of the few churned customers with big value and use lift to evaluate the rules in order to find strong association rules of the customer churning Thirdly the experiment conducted by Powerbuilder6 5 programming indicated that new algorithm is more efficient in customer churn prediction and can mine rules of few churned customer with big value which traditional algorithm can not mine The new algorithm shows better predictive results and can make the telecommunication enterprises retain big value customers more pertinently KEY WORDS Customer Churn Association Rule Attribute Reduction Weighted Association Rule Multidimensional Association Rule 原创性声明 l 金 著麓 嚣女 蓊 柔每茬i 金 嚣g 霎i 栗备嚣需藿i g 霍 璧 磊羹 翥 喜萎 苔嚣 然 攀茬蓑妻譬黼2 奢i 豁卷嚣 i 鐾个人 学位论文作者签名 鼍 嵋1 千哇H 期 7 加叼九 a 关于学位论文版权使用授权的说明 本人完全了解河北工业犬学盏于收集保存 使用学位论文的规定 同意如下菩项内 容按照学校要求提交学位论文的印刷本和电子版本 学校有权保存学位论文的印刷本和 电子版 并采用影印 缩印 扫描 数字化或其它手段保存论立 学校有权提供目录检索 以及提供本学位论文全文或者部分的阅览服务 学校有权按有黄规定向国家有关部门或者 机构送交论立的复印件和电子版 在不以赢利为目的的前提F 学校可阻适当复制论文的 部分或全部内容用于学术活动 f 保密的学位论文在解密月适用本授权说明 学位论文作者整名 导师签名 呷鸭磷 轨 R 婀 订小 口 司一虮阳 河北工业大学硕士学位论文 1 第一章 绪论第一章 绪论 1 1 研究背景和意义 1 1 研究背景和意义 随着中国加入WTO这个战略政策的实施进程 中国电信市场也将进一步向世界开放 而且 目前我 国电信企业运营机制已全面调整 在国内的独家垄断局面己经打破 竞争更激烈 因此电信公司将面临 更严峻的双重竞争压力 尤其在业务迅速增长 竞争日益激烈的移动市场 运营商正在树立起大客户管 理理念 加强大客户营销和服务 提高大客户的忠诚度和满意度 这已成为运营商的战略性任务之一 1 移动市场竞争日趋激烈 又加剧了市场争夺的残酷性 电信企业之间的争夺加剧了客户离网行为 即客户流失 如何挽留住客户成为一个重要问题 客户离网是移动经营面临的一个基本问题 也 是影响经营状况的一个重要因素 一方面它会造成收入下降 市场占有率下降 营销成本增加等问题 另一方面 恶意离网会造成客户恶意欠费 给公司带来不必要的经济损失 离网分析的目的就是要通过 特定算法 分析出哪些客户具有较大的流失概率 从而对这些客户进行有效的挽留工作 尽量减少客户 流失带来的损失 通过预测流失用户的模型 可以提高对客户挽留的成功率 做到有的放矢 降低客户 离网率 降低挽留服务的成本 减少由于客户离网带来的经济损失 这就导致电信业的运营商需要寻找一种最有效的方法 通过正确而及时的决策 维护与客户的关 系 创造客户价值来保留和竞争优质客户 提高企业盈利能力 目前一种有效的方法就是建立基于数据 挖掘技术的客户关系管理系统 2 通过决策树 聚类 统计 神经网络等各种数据挖掘算法科学地分析 影响客户满意度的因素 提高客户满意度 同时分析那些已经流失的客户的特征 从而预测在网客户的 流失倾向 对流失倾向大的客户进行挽留 减少由于客户离网带来的经济损失 在众多的数据挖掘技术中 关联规则 association rule 挖掘技术 3 是最重要的数据挖掘技术 之一 由于关联规则挖掘算法本身的诸多优势 目前利用关联规则挖掘技术来降低客户流失己经成为全 球电信业决策者们共同关注的课题 4 5 6 本文的工作正是基于这样一个背景展开的 以电信业为应用背景 通过分析客户的基本数据 交易 数据和行为模式 利用关联规则挖掘技术 建立客户流失预测模型 并在此基础上进行初步的流失原因 分析和流失趋势预测 给出有效控制客户流失的建议 本文研究的目的是把理论运用于实践 数据挖掘技术是人们长期对数据库技术进行研究和开发的结 果 今天 这些成熟的技术 加上高性能的关系数据库引擎以及广泛的数据集成 让数据挖掘技术在当 前的数据仓库环境中进入了实用的阶段 而关联规则数据挖掘技术在电信行业有更广阔的应用领域 如 何结合目前电信企业的现状 将目前多维关联规则理论及其研究热点应用并指导电信企业 建立准确的 数据模型 将运用模型进行预测 在短期内迅速地产生效果 是本论文研究的意义 面向客户流失预测的关联规则挖掘算法应用研究 2 1 2 研究内容和创新点研究内容和创新点 电信业数据库系统庞大 客户流失预测使用的变量很多 传统的单维关联规则挖掘算法不适应此领 域 只能采用多维关联规则挖掘算法建立流失预测模型 因此本文重点是分析现有多维关联规则挖掘算 法的优缺点 并应用改进算法进行电信客户流失预测 1 2 1 主要研究内容 1 2 1 主要研究内容 本文的主要内容如下 1 综述目前电信业客户流失预测和关联规则挖掘算法相关理论和研究方法 2 分析多维关联规则挖掘算法的相关理论 以及算法在客户流失预测中的应用现状和存在的 问题 3 针对目前存在的问题 设计改进的多维关联规则挖掘算法 4 编程实现算法 5 以某市网通数据为例 进行实验验证 并评价改进算法 1 2 2 创新点 1 2 2 创新点 本文创新点主要有以下三点 1 选取数据源时根据网通公司评价客户价值的标准 选取客户价值相对较大的客户群体 再利 用基于粗集的属性约减算法进行属性约减 选取与客户流失相关的属性构成数据表 这样的数据表既降 低了维数 同时也有针对性的减少了记录数 从而高效率的产生更有价值的规则 2 利用加权的理论来平衡小概率项目的支持度 主要采用基于概率的加权关联规则挖掘算法 通过概率的加权 提升了小概率项目的加权支持度 有效地挖掘小概率项目的关联规则 同时基本保持 Apriori算法的挖掘效率 3 选取比较简单高效的一种系统客观层面的兴趣度计算方法 提升度 利用支持度和置信度的 值 同时引入了期望置信度的概念 从而不必再耗费资源计算 提高规则准确度和有趣性的同时 也提 高了挖掘的效率 1 3 论文结构论文结构 本文共分为六章 结构图参见图 1 1 第一章 绪论 介绍面向客户流失预测的关联规则挖掘算法的研究背景 意义 研究内容和本文的 创新点 第二章 电信业客户流失预测和关联规则挖掘算法研究综述 本章主要对电信业客户流失预测管理 河北工业大学硕士学位论文 进行介绍 对主要的客户流失预测算法进行说明 重点对有较好应用前景的关联规则挖掘算法进行分类 研究 第三章 现有的多维关联规则挖掘算法的研究分析 从整体上介绍多维关联规则挖掘算法的基本 思想 实现过程和主要步骤 研究和讨论现有多维关联规则挖掘算法在客户流失预测中存在的一些问题 并分析现有主流的一些多维关联规则挖掘算法对问题的解决情况 第四章 多维关联规则挖掘算法的改进 首先对现有的多维关联规则挖掘算法进行客户流失预测 时关注的问题进行分析 列出改进算法提出的依据 并在此基础上提出一种对数据进行属性约减 基于 概率的加权关联规则改进算法 详细介绍改进算法的基本思路和过程 第五章 多维关联规则改进算法的仿真与测试 设计改进算法的实验过程 并给出改进算法在某市 网通公司是积极数据集上的实验结果 对改进算法与传统算法进行相关性能的比较分析 第六章 总结和展望 对本文研究进行全面总结 指出存在不足 以及对未来工作的展望 绪论 电信业客户流失预测和关联规则挖掘算法综述 综述研究 多维关联规则挖掘算法改进 改进算法在电信客户流失预测中的应用 实验研究 总结和展望 现有多维关联规则挖掘算法分析 理论研究 图 1 1 论文结构图 Fig 1 1 Framework of dissertation 3 面向客户流失预测的关联规则挖掘算法应用研究 4 第二章 电信业客户流失预测和关联规则挖掘算法综述第二章 电信业客户流失预测和关联规则挖掘算法综述 2 1 电信业客户流失预测 2 1 电信业客户流失预测 我国的电信行业经过几年的高速发展 现在正步入稳定增长期 移动注册客户数量进入动态增长期 即在大量客户入网的同时 又有大批客户离网流失 现在各个行业的竞争都越来越激烈 企业获得新客 户的成本正不断的上升 比如在美国 电信公司每获得一个新客户的平均成本是 300 美元 而挽留一个 老客户的成本可能仅仅是一个电话 7 因此 分析客户流失原因 吸引潜在客户入网 增加现有客户满 意度 减少客户流失率 提高客户消费水平 充分占有市场 是移动行业在激烈市场竞争中制胜的关键 面对此种情况 各大运营商正在寻找一种最有效的方法 通过维护与客户的关系 创造客户价值来 保留和竞争优质客户 因此便出现了客户流失预测的概念 所谓客户流失预测 就是使用数据挖掘的方 法 整合客户历史海量数据 通过对客户基本状态属性与历史行为属性等数据进行深入分析 提炼出已 流失客户在流失前具有的特征 建立流失模型 预测出将在近期流失的客户 客户流失预测给电信企业的经营决策提供了大量信息 客户流失预测是一个系统的工程 需要对企 业的市场情况进行深入分析 如竞争对手分析 客户群细分 客户心理研究 并对企业的历史经营数据 进行深入的数据挖掘 客户流失预测提供给企业的并不仅仅是一个流失预测名单 还会给企业带来大量 有价值的市场信息 客户流失预测能显著提高企业的赢利能力 通过客户流失预测 通信企业开展有针对性的市场营销 活动 可以提高大客户挽留的成功率 降低客户流失率 降低挽留服务的成本 做到有的放矢 减少由 于客户流失带来的收入损失 客户流失预测能显著的提高企业的市场竞争力 通过客户流失预测 企业能开展有针对性的市场营 销活动 能极大地提高客户满意度 从而提高企业的市场竞争力 国内电信业的快速发展是近几年的事 这段时间内电信企业的精力主要集中在抢占市场 采取的手 段也主要是用经过初步的市场调研和表面上的数据分析得出的结果来制定新的服务策略 技术研究主要 是业务运营支持系统 BOSS 的更新换代 如对计费系统 客户服务系统 财务管理系统的开发和完善 8 这些系统中保留着大量的客户通话行为数据 账单 投诉咨询和客户基本信息数据 由于电信企业忙于 业务扩张 所以无暇顾及对这些数据的挖掘分析 近一两年来 一些有实力的电信企业也开始考虑到挽 留高价值客户的必要 并逐步着手对这些历史数据进行挖掘 由于起始的时间不长 大部分都只是试探 性的建立简单的模型 有的还处于调研与可行性分析阶段 没有实际投入应用的产品 9 通过对相关文献的研究 笔者总结出 目前客户流失分析常用的方法有自动聚类 各种分类器 决 策树 人工神经网络 贝叶斯算法 10 以及关联规则三大类方法 参见图 2 1 尤其是采用决策树和 其变形算法建立的流失分析预测模型 已经在国外一些电信公司应用 河北工业大学硕士学位论文 客户流失分析算法分类 聚 类 分类器 关联规则 决策树 神经网络 贝叶斯算法 图 2 1 客户流失分析算法分类 Fig 2 1 Churn analysis arithmetic classification 国外在这方面的研究相对比较早些 某些科研机构已经研究出了较为成熟的模型 投入到了市场应 用之中 现有的客户流失分析方法多采用决策树及其变形算法来进行 典型的有英国Lightbridge公司 开发的Churn Prophet CART 分类回归树 另外还有一些采用C4 5 偏差统计以及神经元网络等算 法的 11 数据挖掘中的分类 聚类和关联规则技术也是一种常规的客户流失分析方法 从市场的反馈来看 用分类回归树CART得出的模型可以很容易被人们理解 但是它在预测高低两端 客户流失率的细分群时精确度很低 神经元网络也可以产生很好的预测模型 但是这些模型很难理解 当用这些模型作预测分析时 很难对客户的流失原因有深入的了解 使用数据挖掘中的分类 聚类等技 术 也可以得到易于理解且精确度高的预测模型 但这些模型并不具备很强的健壮性 准确率也不是很 高 而且 随着数据量的激增 对模型的性能开销也越来越大 12 因为关联规则挖掘算法相对较新 目前此算法进行客户流失预测的研究成果还较少 但由于多维关 联规则挖掘有众多优点 此类算法在电信客户流失分析预测中的应用有很好的前景 许多研究机构在设 法提出多维关联规则挖掘改进算法来对客户流失预测分析模型进行优化 完善 同时 由于国内的电信 市场与国外的电信市场存在着很大的差异 在将国外的模型应用到国内之前必须进行调整 2 2 关联规则挖掘算法分析 2 2 关联规则挖掘算法分析 数据关联是数据库中存在的一类重要的可被发现的知识 若两个或多个变量的取值之间存在某种规 律性 就称为关联 关联规则侧重于确定数据中不同领域之间的联系 即寻找给定数据集中的有趣联系 有时并不知道数据库中数据的关联函数 即使知道也是不确定的 13 因此关联规则挖掘是一个自学习的 过程 通过它可以发现人们不知道的 或者是出乎人们预料的规则 Agrawal 等人于 1993 年首先提出了挖掘顾客交易数据库中项集间的关联规则问题 他提出的关联 规则是发现交易数据库中不同商品 项 之间的联系 并通过这些规则找出顾客的购买行为模式 如购买 了某一商品的同时会购买其它的商品 以及购买后对其他商品的影响 发现这样的规则可以应用于商品 货架设计 库存安排以及根据购买模式对用户进行分类 5 面向客户流失预测的关联规则挖掘算法应用研究 2 2 1 关联规则算法概析2 2 1 关联规则算法概析 一个关联规则是形如XY的蕴涵式 这里X Y都是项目集 且XI YI I i 1 i2 im 是项目集 并且XY X Y分别称为关联规则XY的前提 LHS 和结论 RHS I 关联规则作为一个研究领域仅仅是最近几年的事情 但是在出现后的几年里已经成为数据库界广泛 研究的热点 关联规则的概念最早是由Agrawal等人提出的 14 随后 诸多的研究人员对其进行了大量研究 他们的工作包括对原有的算法进行优化 如引入随机 采样 并行的思想等 以提高算法挖掘的效率 有的就是对关联规则的应用进行推广等 关联规则的研 究主要是算法和实施 理论上的研究主要是针对不同数据形式的最优算法 实际应用则强调关联规则与 数据库技术的紧密配合及实施方法的选择 随着数据仓库和联机分析处理 OLAP 的发展 逐渐形成了多层和多维关联规则的挖掘算法 文献 15 中提出了属性概念分层的概念 在文献 16 中 作者根据概念分层的定义 提出了多层关联规则的挖掘算 法 文献 17 提出了多维关联规则挖掘的基本思想 将其转化为布尔型关联规则求解 文中提出了挖掘二 维关联规则的算法 应用桶结构存储划分的数据 加快关联规则的挖掘 为了加强关联规则的通用性 人们对其中的部分概念进行了发展 文献 18 中对兴趣度进行了发展 提出了基于兴趣度的关联规则挖掘 算法 并提出了强集合项集的概念 文献 19 提出了基于约束的关联规则挖掘算法 利用规则模板和设置 初始值对规则进行过滤 以上三者的目标都是要挖掘有效的强规则 但侧重点各有不同 要挖掘有效的强规则 都需要评价度量标准 目前存在的各种关联规则 一般都有两个评价度量标 准 支持度 置信度 支持度和置信度能够比较直观地描述关联规则的性质 从关联规则定义可以看出 任意给出事务中的两个项目集 它们之间都存在关联规则 只不过属性值有所不同 如果不考虑关联规 则的支持度和置信度 那么在事务数据库中可以发现无穷多的关联规则 事实上 人们一般只对满足一 定的支持度和置信度的关联规则感兴趣 因此 为了发现有意义的关联规则 一般需要给定两个阈值 最小支持度和最小置信度 如果 support XY minsupport 且 confidence XY minconfidence 则称关联规则 XY 为强规则 否则称关联规则 XY 为弱规则 但单纯用支持度和置信度作为度量标准 往往出现错误的规则 2 2 3 中进行详细分析 于是又 引入了期望置信度和兴趣度两个标准 四个度量标准的关系见表 2 1 其中 P X 表示事务中出现项目 集 X 的概率 P Y 表示事务中出现项目集 Y 的概率 P Y X 表示在出现物品集 X 的事务中 出现物品 集 Y 的概率 6 河北工业大学硕士学位论文 表 2 1 关联规则参数表 Table 2 1 Parameters in association rules 名称 描述 公式 支持度 物品集X Y同时出现的概率 P X Y 置信度 物品集X出现时 Y出现的概率 P Y X P X Y P X 期望置信度 物品集Y出现的概率 P Y 提升度 置信度与期望置信度之比 P Y X P Y P X Y P X P Y 目前 关联规则根据不同的分类方法 可以分成不同的种类 总结各种分类方法 主要有以下几种 分类 1 基于规则中处理的变量的类别 关联规则可以分为布尔型关联规则和数值型关联规则 如果考虑的是项目存不存在 则它是布尔型关联规则 布尔型关联规则处理的值都是离散的 种类 化的 如果考虑的是量化的项或属性之间的关联 则是二数值型关联规则 例如 性别 女 职业 秘书 是布尔型关联规则 性别 女 收入 2300 涉及的收入是数值类型 是一个数值型关联规则 2 基于规则中数据的抽象层次 可以分为单层关联规则和多层关联规则 在单层的关联规则中 所有的变量都没有涉及不同抽象层的项或属性 而在多层的关联规则中 对 数据的多层性已经进行了充分的考虑 例如 buy X 台式机 buy X 打印机 是一个购买层次上的单层关联规则 buy X 台式机 buy X Sony 打印机 是一个较高层次和细节层次之间的多层 关联规则 其中 Sony 打印机是打印机类别中的一个细化子类别 3 根据关联规则是否考虑时间因素 关联规则可以分为简单关联和序列关联 简单关联规则不考虑数据项之间的时间关系 默认所有的关联都是发生在相同的时间维度上 序列 模式关联则充分考虑时间的先后顺序 挖掘出时间维度上的频繁序列 例如 buy X 计算机 buy X 杀毒软件 这是一个简单关联规则 它不考虑客户何时购买 以上两种产品 buy X 计算机 3 个月后 buy X 杀毒软件 这是序列关联 购买软件的行为发生 在初次购买的三个月后 4 基于规则中涉及到的数据的维数 关联规则可以分为单维关联规则和多维关联规则 若规则只涉及到数据的一个维 则它是单维关联规则 若规则要处理的数据涉及多个维 则它是多 维关联规则 换一句话说 单维关联规则是处理单个属性中的某些关系 多维关联规则是处理多个属性 7 面向客户流失预测的关联规则挖掘算法应用研究 之间的某些关系 例如 buy X 啤酒 buy X 尿布 这条规则只涉及到用户的购买行为 是购买维上的 关联规则 age X 20 29 occupation X student buys X laptop 这条规则就涉 及到 age occupation 和 buys 三个字段的信息 是三个维上的关联规则 5 基于关联规则是否考虑项目的不同重要程度 关联规则可以分为普通关联规则和加权关联规则 buy X 啤酒 buy X 尿布 这条规则中用户的购买项目是同等重要的 是普通 关联规则 buy X 1 5 啤酒 buy X 尿布 这条规则中用户购买的啤酒重要程度更大一些 可能是商家销售啤酒的利润更大一些 因此给予啤酒项目更多的关注 这是加权关联规则 关联规则在国外已进入了产品化阶段 主要有IBM公司的QUEST 加拿大Fresar大学的DBminer 以 及用于图像处理的SKICAT 20 关联规则挖掘的研究在我国起步较晚 目前研究的重点仍集中在对国外算 法的理解和改进上 以适合中国数据库系统的实际情况 对于数据挖掘 包括关联规则的挖掘 的实际应 用研究得相对较少 到 2000 年国内开发出了第一套主要针对关联规则挖掘的产品Dminers 它是基于C S 规范的 最近几年 国内更全面的数据挖掘产品正在研究和开发之中 但是还没有出现很好地适用于多 平台的产品 目前数据挖掘在我国的应用主要集中在一些信息化建设比较好的行业和部门 包括银行 金融 电信等 更深层次的应用和对复杂问题的解决方案还有待进一步地研究和实践 目前 许多学者对关联规则挖掘算法的改进都是围绕 Apriori 算法进行的 一般只考虑每一项在所 有的事务中是否出现 从而计算项集出现的次数 以判断是否为频繁项集 最后通过推算出的频繁项集 得出所有的强关联规则 因此属于单维的布尔类型的关联挖掘 但是在现实生活中 大量的数据库并不是简单布尔类型的 有商业价值和应用需求的量化关联关 则占据了绝大部分 以电信行业为例 该行业拥有所有其他行业所不能比拟的庞大的 完整的 实时的 并且具有极高市场指导意义的用户海量数据 是数据挖掘应用最为广泛的行业之一 而在电信行业中 对用户数据进行关联规则分析的时候 通常挖掘的都是多维关联规则 因为挖掘电信企业用户数据中的 关联规则 主要是希望寻找出各个属性之间的强关联规则 当进行客户流失预测时 市场需要的是在海 量客户数据中 挖掘出不同属性之间和客户流失状态的强关联规则 2 2 2 多维关联规则挖掘算法分析 2 2 2 多维关联规则挖掘算法分析 如前面所述 age X 20 29 occupation X student buys X laptop 这种涉及两个或多个谓词 age occupation buys 的关联规则称为多维关联规则 多维关联规则可以分为两类 1 具有不重复谓词的维间关联规则 当每个谓词在规则中仅出现一次时 称它为具有不重复谓 词 具有不重复谓词的关联规则称作维间关联规则 2 包含某些谓词的多次出现的混合维关联规则 当规则中包含某些谓词的多次出现 称作混合 8 河北工业大学硕士学位论文 9 维关联规则 本文要用的是维间关联规则 注意 在多维关联规则挖掘中 我们不是搜索频繁项集 向单维关联 规则挖掘那样 而是搜索频繁谓词集 k 谓词集是包含k个合取谓词的集合 例如 前面的谓词集 age occupation buys 是 3 谓词集 同样用Lk表示频繁k 谓词集的集合 笔者通过阅读分析大量中外文 献 总结出挖掘维间关联规则的方法主要有三类 1 使用量化属性的静态离散化挖掘多维关联规则 即使用预定义的概念分层对量化属性离散化 这种离散化在挖掘之前进行 数值属性的值用区间 替代 如果任务相关的结果数据存放在关系表中 则 Apriori 算法只需要稍加修改就可以找出所有个频 繁谓词 而不是频繁项集 即通过搜索所有的相关属性 而不是仅搜索一个属性 找出所有的频繁 k 谓词集将需要 k 或 k 十 1 次表扫描 其他策略 如散列 划分和选样可以用来改进性能 2 挖掘量化关联规则 量化关联规则是多维关联规则 其中数值属性动态离散化 以满足某种挖掘标准 这种方法是根据 数据的分布 将量化属性离散化到 箱 这些箱可能在挖掘过程中进一步组合 如系统ARCS Association Rule Clustering System 关联规则聚类系统 使用的方法就是将量化属性对映射到满 足给定分类属性条件的 2 D栅格上 然后搜索栅格点的聚类 由此产生关联规则 21 3 挖掘基于距离的关联规则 这种方法是量化属性离散化 以紧扣区间数据的语义 并不允许数据值的近似 这一过程考虑到 了数据点之间的距离 因此称为基于距离的关联规则 两遍算法可以用于挖掘此类关联规则 第一遍使 用聚类找出区间或簇 第二遍搜索频繁的一起出现的簇组 得到基于距离的关联规则 目前 使用量化属性的静态离散化挖掘维间关联规则应用比较广泛 不管是哪类挖掘维间关联规则的方法 遵循的基本思路都是将其转换为经典的布尔关联规则进行挖 掘 22 故可以借鉴经典的Apriori算法中的思想 下面我们分析维间关联规则是否可以转换为布尔型关 联规则 数据库属性可能是类别或量化的 分类属性具有有限个不同值 值之间无序 类别属性也称名词属 性 因为它们的值是 事物的名字 量化属性是数值型的 并在值之间具有一个隐含的序 23 1 如果所有的属性都是只有有限个取值的类别型属性或者数值型属性 那么可以直观地将其转换 为布尔型关联规则进行挖掘 形成对 对于每一个属性 将原关系表中的单一属性用与取 值个数对应的多个布尔型属性来替换 如果原记录取值为 1 则对应的布尔属性取值就为 1 反之 就为 0 2 如果数值型属性的取值范围很大 一个直观的方法就是将其划分为多个区间然后对每一个独立 的区间用一个布尔属性替换 形成对 完成此转换后 就可以选择合适的布尔型关联规则 进行挖掘了 由于电信业数据库属性繁多 数值型属性的取值范围很大 因此数值型属性划分区间是一个重要环 节 对于数值型属性 划分成区间的方法通常有四种 1 定义的概念分层对量化属性离散化 面向客户流失预测的关联规则挖掘算法应用研究 Kamber等人提出了使用量化属性的静态离散化和数据立方体挖掘关联规则的方法 24 这种方法中 量化属性使用预定义的概念分层 在挖掘之前离散化 数值属性的值用区间代替 如income的概念分层 用于区间值 如 0 20K 21K 30K 31K 40K 等 这种离散化是静态的 预定义的 离散化的数值属性具有区间值 这种方法要求有领域专家的参与 如果事先无法得到有关数据的相关知 识 则该方法不适用 2 使用等宽区间法 这种方法比较简单 划分速度快 如果数据分布均匀 可以采用这种方法 如果数据分布不均匀 使用这种划分方法就会造成大量信息的丢失 3 等深法划分 即每个区间的属性值数目相同 这种方法要求事先对该属性排序 而排序操作是 比较费时的 4 部分完全性原则量化分区方法 这是个折中方法 在挖掘过程中首先需要确定如何对数量属性 的值进行分区 我们首先根据部分完全性原则量化分区带来的信息丢失 然后采用等深分箱对属性值进 行分区 等深分箱可以在保持一定的部分完全性水平的基础上使得区间数目为最少 在减少信息丢失的 同时提高效率 目前 业界已经提出了许多挖掘维间关联规则的算法 25 但通过分析可以总结出 这些算法普遍存 在两个问题 1 数据库的维数太多 算法运行时间太长 挖掘效率低下 2 这些算法都认为每个项目对规则的重要性相同 但在实际应用中 许多用户会比较倾向于自己 最感兴趣或认为最重要的那部分项目 因此有必要加强这些项目对规则的影响 同时减弱另一些用户兴 趣不大或认为不重要的项目对规则的影响 2 2 3 关联规则价值衡量 2 2 3 关联规则价值衡量 挖掘出的关联规则的价值通常称为有趣性 有趣性的大小不仅与数据本身有直接联系 而且与实际 的应用环境 用户个人的职业特点 个人爱好有着重要的联系 因此评价规则的有趣性需要从多方面去 考虑 通常从两个层面来评价一个关联规则的有趣性 即系统客观层面和用户主观层面 1 系统客观层面 很多的算法都使用 支持度一置信度 的框架 这样的框架有时会产生一些错误的结果 当事务 A 并不蕴涵 B 时 利用该算法却可能会识别出 A B 是有趣的关联规则 也就是说会生成一些虚假的关 联规则 可以用一个超市中购买商品的例子说明这个问题 事务数据库 D 见表 2 2 10 河北工业大学硕士学位论文 表 2 2 事务数据库 D Table 2 2 Transaction database D TID 项目集 TID 项目集 T1 牛奶 面包 T5 纯净水 T2 牛奶 面包 纯净水 T6 纯净水 T3 牛奶 纯净水 T7 纯净水 T4 牛奶 纯净水 T8 纯净水 给定 minsupport 25 和 minconfidence 50 根据 Apriori 算法 得到如下规则 牛奶 面包 support 25 confidence 50 和 牛奶 纯净水 support 37 5 confidence 75 其中规则 牛 奶 纯净水 以 75 的置信度表示 顾客买了牛奶同时买纯净水的可能性较高 然而事实并非如此 由数据库 D 可以看出 87 5 的顾客买纯净水 而规则 牛奶纯挣水 显示买牛奶的顾客有 75 的可能 性再买纯净水 即该规则所传达的信息没有价值 且有误导性 而在所给的数据库中 我们也不可能找 到合适的最低支持度和最低置信度 使得虚假规则 牛奶纯净水 不产生 即无论如何调整 minsupport 和 minconfidence 均不能完全排除产生虚假规则 于是人们引入了提升度 26 用来修剪无趣的规则 即避免生成 错觉 的关联规则 提升度是置信度与期望置信度的比值 即 置信度 期望置信度 提升度又叫做兴趣度 interest 相关度 correlation 提升度描述项目集 X 的出现对项目集 Y 的出现有多大的影响 因为项目集 Y 在 所有事务中出现的概率是期望置信度 而物品集 Y 在有项目集 X 出现的事务中出现的概率是置信度 置 信度对期望置信度的比值反映了在加入 项目集 X 出现 的这个条件后 项目集 Y 的出现概率发生了多 大的变化 Lift X Y support X Y support X support Y 公式 2 1 一般情况 有用的关联规则的提升度都应该大于 1 只有关联规则的置信度大于期望可信度 才说 明 X 的出现对 Y 的出现有促进作用 也说明了它们之间的某种程度的相关性 给定一个事务集 D 挖掘 关联规则的问题就是产生支持度和置信度分别大于用户事先给定的最小支持度 minsupport 和最小置 信度 minconfidence 的关联规则 根据表 2 1 中公式计算可知 规则 牛奶 纯净水 的置信度虽然高达 75 但由于提升度仅为 0 75 0 875 0 8571 则该规则是有趣的 应保留 在许多应用中已发现 只要人们仍以支持度作为最初项集 产生的主要决定因素 那么要么把支持度设得很低 以不丢失任何有意义的规则 或者冒丢失一些重要 规则的风险 对于前一种情形计算效率是个问题 而后一种情形则有可能丢失从用户观点来看是有意义 的规则 2 用户主观层面 上面的讨论只是基于系统方面的考虑 但是一个规则的有用与否最终取决用户的判断 只有用户可 11 面向客户流失预测的关联规则挖掘算法应用研究 12 以决定规则的有效性 可行性 所以我们应该将用户的需求和系统更加紧密的结合起来 可以用一种基 于约束 constraint based 的挖掘 具体约束的内容或方式可以有以下几种 1 数据约束 用户可以指定对哪些数据进行挖掘 而不一定是全部的数据 项目集限制根据项目 的附加信息和用户的需要对候选项目集进行修剪 针对不同类型的项目集约束 修剪过程可以在扫描数 据库之前一次完成或在每次扫描完数据集后进行 通过规定项目或项目集限制降低了算法的搜索空间 可以使关联规则挖掘算法在较短的时间内对用户的挖掘要求做出反应 增强了关联规则挖掘算法的交互 性 2 指定挖掘的维 用户可以指定在哪些维上进行挖掘 3 规则约束 可以指定哪些类型的规则是我们所需要的 引入一个模板 template 用户使用它 来指定哪些规则是令人感兴趣的而哪些则不是 如果一条规则匹配一个包含的模板 inclusive template 则是令人感兴趣的 否则被认为是缺乏兴趣的 其中有些条件可以和算法紧密的结合 从 而既提高了效率 又使挖掘的目的更加的明确化了 2 3 本章小结 2 3 本章小结 本章首先分析了电信业客户流失预测的现状 国内外各种数据挖掘技术在电信客户流失预测中的应 用现状 并简单分析了客户流失预测中各种数据挖掘技术的利弊 针对当前应用前景最好也是研究最深 入的多维关联规则挖掘算法 从分类 价值衡量和研究现状三个方面进行了相关文献的综述 河北工业大学硕士学位论文 第三章 现有多维关联规则挖掘算法分析第三章 现有多维关联规则挖掘算法分析 3 1 现有多维关联规则挖掘算法 3 1 现有多维关联规则挖掘算法 如前面所述 传统的挖掘维间关联规则的方法 遵循的基本思路都是借鉴经典的 Apriori 算法中 的思想 将其转换为经典的布尔关联规则进行挖掘 主要步骤分为三步 数值属性区间划分 搜索频繁 谓词集 生成强关联规则 3 1 1 数值属性区间划分 3 1 1 数值属性区间划分 对于数值属性区间划分 有很多种方法 但普遍沿用量化关联规则中的部分完整度 partial completeness 它可以较好地解决区间值划分问题 令I i1 i2 im 是一属性组 P为一组正整数 IV表示I P 则 IV表示属性x和对应 整数值 令IV表示 I P l u 若x是数值型 1 u 若x是类别型 那么 值对 IR可以表示在区间 1 u 的数值属性 或者取值为 1 u的类别属性 我们将这一个三元组看作一个 项 对任意项X IR 表示以下的组 X 令D是一组记录集合 其中每一条记录R都包含一组属性 所以R IV 数值型关联规则是形如 X Y的表达式 其中X I R Y IR 若一条记录R支持项X X IR 是指对于任意 X 存在 R 1 q u 从此推出数值关联规则的支持度和置信度 它类似于布尔型关联规则 定义 3 1 16 令C表示数据库D中所有的频繁集 对于K 1 称P是K倍完整于C 当 1 CP 2 PX XX PX 且CX PX 使得 1 X是的一个概括 且 support K support 2 X X XXY Y X 使得是的一个概括 且 support K support Y Y Y Y 第一个条件保证了 P 中只包含频繁集 从而可以从中生成规则 第二个条件的前半部分说明 对 C 中的任意项集 都会有一个最多 K 倍完整于它的项集存在于 C 中 后半部分说明 项集的概括的支持度 最多只有原项集 K 倍的性质也适用到项集的子集中 若 K 1 则 P C 定理 3 1 16 对一个数值属性X 给定一实数K I 如果将属性X划分为区间 每个区间称为基础区 间 使得对于每个基础区间B B的支持度小于mi