（管理科学与工程专业论文）基于关联规则的电信企业客户服务信息挖掘研究.pdf

摘要 本文主要研究如何利用关联规则发现电信企业各项电信增值服务之间的内 在关联，帮助运营商分析客户消费行为，识别客户特征，辅助运营商进行有效的 市场营销和客户服务。 首先，阅读和分析了大量国内外相关文献，总结了电信企业服务管理的研究 现状和数据挖掘在电信行业中的应用情况。然后介绍了关联规则的基本概念、经 典算法，讨论了在电信数据库中较为常见的数量关联规则挖掘的一般步骤和存在 的问题以及负关联规则的基本原理。再次，提出了基于云模型改进的正负云关联 规则挖掘算法。在电信运营商的数据库中存在着大量的数值型数据，进行数量关 联规则挖掘的难点之一就是数值区间离散化问题。传统的划分方法由于不能反映 数据间的分布规律或者是划分的边界过硬，使得最终都不能得到富有意义的、易 于理解的关联规则。本文提出了一种基于云模型的数值区间离散方法，这种划分 摒弃了以前的硬划分，使得到的结果除了保留传统硬划分所具有的优点以外，也 更加符合实际的数据分布和人的思维方式，从而最终得到概括的、易理解的、有 效的关联规则。同时，利用相关性系数判断事务间的关联关系，不但挖掘数据库 中的正关联规则，也关注有意义的负向关联。为了提高算法的效率，采用多重最 小支持度约束，对不同长度的项集设置不同的最小支持度，控制短项集产生的同 时保留了可能有意义的长项集。最后，构建了电信企业服务挖掘的系统框架，探 讨了客户行为的基本模式和影响因素，运用正负云关联规则挖掘各种电信服务之 间的关联，作为后续研究的基础，或者直接指导企业的客户服务实践。 本课题作为一项跨学科的研究，涉及客户关系管理、服务管理、数据挖掘等 领域，综合运用了数量关联规则、负关联规则、云模型等理论、方法与模型。 关键词：数量关联规则，负关联规则，云模型，电信客户服务 a b s t r a c t t h i st h e s i s m a i n l yd i s c u s s e dh o wt of i n do u ti n t r i n s i cr e l a t i o n s h i p sa l l l o n g t e l e c o mv a l u e a d d e ds e r v i c e sb ya s s o c i a t i o nr u l e s ，w h i c hc a n h e l pt e l e c o mc o m p a n i e s a n a l y z ec u s t o m e rb e h a v i o r , i d e n t i f yc u s t o m e rf e a t u r ea n dm a k ee f f e c f i v es t r a t e g i e sf o r m a r k e t i n ga n dc u s t o m e rs e r v i c e a tt h eb e g i n n i n go f r e a d i n ga n da n a l y z i n gd o m e s t i ca n de x t e r n a ld o c u m e n t s ，t h i s p a p e rs u m m a r i z e dt h ep r e s e n ts i t u a t i o no ft e l e c o ms e r v i c e m a n a g e m e n ta n d a p p l i c a t i o no fd a t am i n i n gi nt e l e c o mi n d u s t r y t h e na u t h o ri n t r o d u c e db a s i cc o n c e p t a n dc l a s s i c a la l g o r i t h mo fa s s o c i a t i o n r u l e s ，g e n e r a ls t e p sa n dp r o b l e m so fq u a n t i t a t i v e a s s o c i a t i o nr u l e sm i n i n ga sw e l la sf u n d a m e n t a lp r i n c i p l e so fn e g a t i v ea s s o c i a t i o n r u l e s n e x t ，p o s i t i v ea n dn e g a t i v ea s s o c i a t i o nr u l e sa l g o r i t h mm e l i o r a t e db yc l o u d m o d e lw a sp r e s e n t e d t h e r ea r eam a s so fd a t ao fn u m e r i c a lv a l u et y p ei nt e l e c o m c o m p a n i e s d a t a b a s e h o wt or e a s o n a b l yp a r t i t i o nd o m a i nv a l u e si sv e r yi m p o r t a n ti n q u a n t i t a t i v ea s s o c i a t i o nr u l e sm i n i n g t r a d i t i o n a lm e t h o dc a nn o tg e t 1 ee a s yt o u n d e r s t a n dk n o w l e d g eb e c a u s ei tc a l ln o tr e f l e c tt h ea c t u a ld a t ad i s t r i b u t i o no rt h e p a r t i t i o ni st o os h a r p i nt h i sp a p e r , an e wm e t h o db a s e do nc l o u dm o d e lw a s i n t r o d u c e d t h i sm e t h o dc a nr e f l e c tt h ed i s t r i b u t i o no fd a t ai nt h a td o m a i nw l l i l e k e e p i n gt h es o f tb o u n d a r i e s t h e r e f o r e ，t h ed i s c o v e r e da s s o c i a t i o nr u l e sa r ea l s oe a s y t ou n d e r s t a n d a tt h es a m et i m e ，t h i sm e t h o df o u n do u tb o t hp o s i t i v ea n dn e g a t i v e a s s o c i a t i o nr u l e si nd a t a b a s ew i t hc o r r e l a t i o nc o e f f i c i e n t s ，a n di m p r o v e dt h ee f f i c i e n c y o fa l g o r i t h mb ym u l t i p l em i n i m u ms u p p o r t sw h i c hc a nr e s t r i c tt h en u m b e ro fs h o r t i t e ms e t sw h i l ek e e pt h em e a n i n g f u ll o n gs e t s i nt h ee n d ，t h i sp a p e rc o n s t r u c t e dt h e s y s t e mf r a m e w o r ko ft e l e c o mc o m p a n ys e r v i c em i n i n g ，d i s c u s s e dt h eb a s i cm o d e la n d i n f l u e n c ef a c t o r so fc u s t o m e rb e h a v i o r , a n de x p l o r e dt h ec o n n e c t i o na m o n ga l lk i n d s o ft e l e c o ma d d e d v a l u es e r v i c e sw i t hp o s i t i v ea n dn e g a t i v ea s s o c i a t i o nr u l e s k e yw o r d s ：q u a n t i t a t i v ea s s o c i a t i o n m o d e l ；t e l e c o mc u s t o m e rs e r v i c e r u l e s ；n e g a t i v ea s s o c i a t i o nr u l e s ；c l o u d n 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 武汉理工大学或其它教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 签名：毛之哆 日傀加d _ 争 学位论文使用授权书 本人完全了解武汉理一 大学有关保留、使用学位论文的规定，即： 学校有丰义保留并向国家有天部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位论文的 全部内容编入有关数据库进行检索，可以采用影印、缩印或其他复制 手段保存或汇编本学位论文。同时授权经武汉理工大学认可的国家有 关机构或论文数据库使用或收录本学位论文，并向社会公众提供信息 服务。 ( 保密的沦文在解密后应遵守此规定) 僦引锄吨剐寺喇州鹤) 刁p 胁弘 武汉理工大学硕士学位论文 1 1 研究目的与意义 第1 章绪论 随着信息经济时代的到来，电信业已经成为国民经济的支柱行业，对经济 的发展和人民生活水平的提高起着重要的支撑作用。加入w t o 后，中国根据协 议逐步逐区域地对外开放增值电信市场及基础电信市场，随着2 0 0 7 年1 2 月1 1 日中国电信业对w t o 承诺的到期，中国取消了基础电信的地域限制。外国电信 企业将会不断加快进军中国市场的步伐，运营商将直面国际电信大鳄的竞争。 纵观国内，电信重组将原来的六家基础电信运营商合并为三家，并打破地域界 线和分业经营模式，给予三家运营商全业经营牌照，表面上看，虽然减少了市 场的竞争主体，但竞争的激烈程度并不会减弱，电信运营企业普遍感到a r p u 值和利润增长的乏力。国际、国内形势都对电信运营企业的服务内容、服务方 式、服务质量、经营管理以及服务意识提出了严峻的挑战。 当前，我国基础电信市场竞争的主要特征不是差异化，而是同质化。主要 体现在三个方面：一是服务对象同质化，主要都是面对整个中国电信市场：二 是产品类型同质化，例如中国移动有全球通、神州行、动感地带等品牌，中国 联通就有相对应的新时空、如意通、u p 新势力；三是竞争手段同质化，主要的 竞争手段就是依靠价格划。在同质化竞争主导着的电信市场，客户服务质量的 优劣直接决定着电信运营企业的市场主导权，更是决定电信运营企业盈利能力 的重要因素。研究客户，实现从“以产品为中心”向“以客户为中心的转变 是电信运营企业提高其竞争力的必然选择。 电信市场的竞争日益激烈，竞争的视角也从单纯的“产品竞争 转向综合 的“客户竞争 。客户已经不再仅仅是销售和服务的对象，而是商战中拥有的资 本，是在竞争中取胜的关键因素之一。在某种意义上说，提高客户服务质量和 顾客满意度是电信企业持续发展的生命源泉。电信服务的最终受用者是客户， 电信运营企业若想提高服务质量，必须深入的分析研究客户，把握客户的消费 特点和使用习惯，及时推出有针对性的服务，通过高满意度的服务来维持现有 客户，吸引潜在客户。 在激烈的竞争中，如何在满足客户需求和优质服务的前提下充分利用现有 武汉理工大学硕士学位论文 资源降低成本、提高效益，也是一个值得重视的课题。对于个相对成熟的电 信运营商来说，各运营支撑系统所积累的海量历史数据是一笔宝贵的财富，但 长期以来，电信企业大量而详尽的客户业务数据只被简单的应用在各种业务系 统中，而没有被更有效的开发利用，这无疑是一种浪费。数据挖掘是从海量数 据中发现趋势或模式的过程，运用到电信运营企业中，可以从大量的有关客户 的数据中挖掘出隐含的、先前未知的、对企业决策有潜在价值的知识和规则。 基于以上事实，本课题进行基于关联规则的电信企业客户服务信息挖掘研 究，力求真正了解客户对电信服务的需求推出满足客户需求的打包服务，从而 提高客户忠诚度并留住客户。通过梳理归纳所掌握的客户数据帮助电信运营企 业对客户的行为特征进行深入分析，以获得对客户的洞察力，并利用洞察结果 制定针对性、差异化的营销方案，最终实现“以客户为中心 ，为客户提供有针 对性的主动服务，提高客户满意度，保持现有客户，发展潜在顾客。 1 2 国内外研究综述 1 2 1 电信企业服务管理 电信服务是指经营者提供电信业务和电信用户使用电信业务的过程及经营 者内部活动所产生的结果【2 】。对电信服务管理的研究主要集中在两大方面：一是 从顾客感知、顾客满意度、顾客期望等方面对服务质量进行分析和评价；二是 从管理方法、服务策略、服务内容等方面针对大客户服务进行研究。 1 9 8 2 年，芬兰学者c r o n r o o s ( 1 9 8 2 ) 第一次提出了顾客感知服务质量概念，即 顾客感知服务质量为顾客对服务期望与实际服务绩效之间的比较。当实际服务 绩效大于服务期望，则顾客感知服务质量是良好的，反之亦然1 3 j 。此后，美国的 服务管理研究组合p z b ( p a r a s u r a m a n ，z e i t h a m la n db e r r y ) 对顾客感知服务质量 进行了更为深入的研究，构建了“服务质量差距模型 ( 1 9 8 5 ) ，并提出了决定顾 客感知服务质量高低的十项要素。1 9 8 8 年又将这十项评定因素缩减为为可靠性、 响应性、保证性、移情性和有形性五项，并提出了著名的服务质量评价方法一 - - s e v r q u a l t 4 1 t 5 1 。阚德涛扩展了原有的s e r v q u a l 评价指标体系，增加了补 救性服务和服务先进性两个维度六个指标，提出了一套新的评价电信企业服务 质量的指标体系。选取加权s e r v q u a l 和加权s e r v p e r f 两种评价方法，从 信度和效度方面探讨新的电信企业服务质量指标体系适用性【6 】。赵惠平从经济学 2 武汉理工大学硕士学位论文 的角度，根据s e v r q u a l 五个维度建立指标体系，提出了电信服务质量的垄断 企业模型和双寡头竞争模型，分析了电信运营商质量竞争的策略选择及其影响， 并在此基础上，构建了电信服务质量管理体系【7 】。 顾客满意即顾客根据其期望或者需要是否被满足而对产品和服务进行的评 价j 。t a y l o r 和b a k e r ( 1 9 9 4 ) 在通讯、交通、娱乐和医疗保健业中考查了感知服务 质量、顾客满意和购买意向三者的关系，并指出顾客满意在服务质量和购买意 向之间起到了很好的调节作用，并且当满意度较高的时候，服务质量和购买意 向之间存在着显著的正相关关系1 9 j 。 1 9 8 8 年瑞典首先采用用户满意度指数c s b ( c u s t o m e rs a t i s f a c t i o nb a r o m e t e r ) 量化地评价用户再来购置商品和服务的可能性。此后许多国家根据实际情况建 立了符合自己要求的客户满意度衡量体系。唐守廉，曹英作为信息产业部全国 电信用户满意度指数测评项目组的成员，借鉴各国经验建立了电信用户满意度 指数模型，如图1 1 所示。用户满意度指数模型是一个因果关系图，一共有六个 潜在变量，箭线表示变量之间的因果关系，从原因变量指向结果变量，箭线上 的系数表示各变量之间的相互影响程度。这六个潜在变量分别是用户期望、感 知质量、感知价值、用户满意度、用户抱怨和用户忠诚。其中，用户满意度既 是用户期望、感知质量和感知价值三个变量的结果，又是用户抱怨和用户忠诚 的原副1 0 】。王武平，杜纲在此基础上，采用不受指标数据相关性的影响的逼近 理想解的排序方法( t e c h n i q u ef o ro r d e rp r e f e r e n e eb ys i m i l a r i t yt oi d e a ls o l u t i o n 简称t o p s i s ) 和熵权法对电信运营商及其服务质量进行综合评价与排序【1 1 1 。龚益 鸣和刘来发把国际上较为流行的满意度测评理论和在服务质量领域内运用广泛 的服务差距分析模型整合起来，得到一个确定满意度关键因素的模型，既可以 测量服务的总体满意度，又能确定满意度的关键因剥1 2 】。 图1 1 电信用户满意度指数模型 3 武汉理工大学硕士学位论文 根据“帕雷托法则”，8 0 的利润来源于2 0 的客户，大客户业务因其高利 润或长远的价值成为各电信运营商争夺的焦点。h o m b u r g 等( 2 0 0 2 ) 认为大客 户服务管理中的关键因素是服务活动，服务人员，服务资源，服务方式【1 3 l 。正 确描述并识别大客户是大客户服务的起点。李重酷从客户价值和客户价值增长 率两个维度构建细分模型，分别以年和季度为单位进行两次聚类分级，通过比 较客户长期和短期两次分级之间的游走态势将客户分为1 6 大类。这些类不但包 括了传统意义上的价值细分的结果，同时也反映出了客户消费行为变动的态势。 从而使企业在利用分类结果时不但可以知道客户静态聚类结构，而且还可以发 现客户动态的变化趋势1 1 4 1 。在具体的服务管理方面，有些学者借助信息化工具 设计了大客户管理系统，提供数据采集分析、档案管理、服务跟踪等功能辅助 大客户服务管理【l 川1 16 1 ；有些学者从流程再造的角度，分析了当前电信大客户服 务存在的问题和原因，探讨借助流程再造提高服务的效率和质量的方法【l _ m 1 8 】； 有些学者从服务创新、服务营销、六西格玛等角度在理论层面上探讨了提高大 客户服务管理体系1 1 9 1 。 1 2 2 数据挖掘在电信行业中的应用 数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据库中， 提取隐含在其中的、人们事先不知道的、但是又潜在有用的信息和知识的过程 【2 0 j 。通过数据挖掘得到的回报就是将这些新发现的知识转变为经营上的成果， 如增加顾客的购买欲望，减少顾客的流失。因此，在银行、交通、保险、零售 等商业领域，数据挖掘技术都得到了广泛应用。在电信行业数据挖掘的典型应 用主要有： ( 1 ) 客户类型分析 客户类型分析就是根据一个或多个客户特征把所有客户划分为不同的群 体，使得同一个群体中的客户具有最大的相似性，不同群体之间的客户具有最 大的差异性。将客户正确的描述和分类是定位目标客户，提供有针对性的、高 质量的服务的第一步。曲昭伟等通过构造模糊相异矩阵，将高维、海量的客户 消费模式映射到二维平面，进一步利用遗传算法进行优化，快速而灵活地实现 客户聚类分析，发现大客户1 2 。梁静国等用模糊c 均值聚类算法作为客户聚类 的方法，得到不同客户群的聚类中心以及客户的隶属度矩阵，为客户群的特征 分析提供了量化依据【2 2 。 4 武汉理工大学硕士学位论文 ( 2 ) 消费模式分析 客户消费模式分析就是根据客户历年来长话、市话、信息等的大量详单以 及客户档案资料等相关数据，结合客户的分类，从消费能力、消费习惯、消费 周期等方面分析预测客户的消费行为；分析各种业务通信量、通信次数随时间 地域的变化情况，从而为电信运营商的相关经营决策提供依据【矧【2 4 1 。 ( 3 ) 市场推广分析 市场推广分析主要研究电信企业推出的服务或服务组合以及优惠策略被市 场接受的程度及趋势。h u n gs h i n y u a n 等提出数据挖掘可以模拟计费和出账，进 行预测仿真，其仿真结果可以解释服务套餐或优惠策略中存在的问题，并进行 相应的调整变化，以达到市场推广活动的受益最大化1 2 5 。刘永、陈治平在分析 现有套餐预演的基础上，构建了电信套餐预演的整体分析模型，包括套餐属性 整理、套餐相似度计算、模拟用户群抽取、预演指标分析等几个部分，结合电 信企业实际套餐数据对该模型各部分进行了具体的应用分析，结果证明了该模 型的有效性1 2 6 j 。 ( 4 ) 客户流失分析 客户流失在移动通信中指的是移动电话用户从一个运营商转向另一个运营 商。客户流失分析即借助数据挖掘技术，分析已经流失和未流失的用户，从他 们的自然属性和行为属性以及其他属性中找出流失用户的特征，根据客户流失 特征建立客户流失模型，然后通过此模型监控客户，预测客户流失的可能性。 如果客户流失可能性过高，则需要采取相应手段巩固提高客户忠诚度，防止客 户流失。用到的主要算法有分类、决策树、神经网络、关联规则【2 7 1 。 ( 5 ) 客户欠费欺诈分析 客户欠费欺诈分析就是通过数据挖掘技术发现各种欠费欺诈行为的内在规 律，建立相应的知识库。基于知识库分析客户的欠费欺诈行为，采取预防措施， 降低运营商的损失。采用何种模型算法建立知识库及进行客户行为匹配是学者 研究的重点【2 引。有的学者提出了基于贝叶斯网络的电信话费欺诈建模方法，并 与o l a p 相结合，分类的准确性高，可理解性强。有的学者构建了基于人工免 疫学的数据挖掘模型，在不同粒度上进行建模和检测，能提高电信欺诈检测的 准确率，实时性和智能性【2 9 j 。 5 武汉理工大学硕士学位论文 1 3 研究内容与方法 1 3 1 研究内容 本文的研究目的是改进传统数量关联规则挖掘存在的问题，将正关联规则 发现与负关联规则挖掘结合到一起，最后将改进后的关联规则应用到电信企业 客户服务信息挖掘中，指导电信企业客户服务。拟解决的关键问题主要有两个： 一是借助云模型进行数值区间软划分，得到更符合数据实际分布和人的思维模 式的关联规则；二是结合电信行业的特点，运用正负云关联规则挖掘电信增值 服务之间的相互关联，指导服务策略的制定。全文分五个部分展开论述。 第一部分是绪论，阐述本文的研究目的和意义、国内外研究现状，概括介 绍研究的主要内容与关键问题，及所采用的技术路线。 第二部分是关联规则基础理论解析，包括关联规则的基本概念，经典关联 规则生成算法及其改进，数量关联规则挖掘的一般步骤和存在的问题，同时介 绍负关联规则的基本原理。 第三部分主要是介绍云模型基础理论，以及如何通过云模型进行数值区间 的软划分以克服传统挖掘方法存在的问题，最终设计出由相关性系数和多重最 小支持度约束的正负云关联规则算法。 第四部分构建了电信企业服务挖掘的基本框架，分析了客户行为的一般模 式和影响因素，将正负云关联规则应用到电信客户服务信息挖掘中，指导电信 企业服务策略的制定。 第五部分是总结与展望，总结全文的主旨，指出研究的不足与局限性，探 讨可以进一步深入发掘的方向。 1 3 2 研究方法 从整体上看，本课题研究本着“提出问题一分析问题一解决问题 的逻辑 思路，将理论研究与实证研究相结合，定性分析与定量研究将结合。通过对国 内外文献的查阅、对比、分析，了解电信企业服务管理与数据挖掘应用的基本 情况，找出理论方法和实际应用中遇到的问题，然后综合运用云模型、负关联 规则等方法与客户行为理论展开详细研究，最后应用于电信客户服务信息挖掘 中。技术路线如图1 2 所示。 6 武汉理工大学硕士学位论文 比较分析 理论研究 a 埘o r i 算法 云模型 负关联规则 实证研究 归纳总结 国内外研究评述 形 方法问题应用问题 、r、r l 改进的关联规则 电信客户行为分析 弋 正负云关联规则在电信企业客 户服务信息挖掘中的应用 。 全文总结与展望 图1 2 本文的技术路线 7 调查问卷 访谈 消费者行为模式 客户行为影响因素 武汉理工大学硕士学位论文 第2 章关联规则基础理论解析 2 1 关联规则挖掘的基本概念 关联规则挖掘最早由a g r a w a l 等人针对购物篮分析问题而提出，其目的是为 了发现消费者购买不同商品之间的潜在联系。在传统的零售商店中顾客购买东 西的行为是零散的，但是随着超级市场的出现，顾客可以在超市一次购得所有 自己需要的商品。因此商家很容易收集和存储大量的销售数据。交易数据库可 以通过对所存数据的智能分析获得有关顾客购买模式的一般性规则。这些规则 刻画了顾客购买行为模式，可以用来指导商家科学地安排进货、库存及商品摆 放等。 一个事物数据库中的关联规则挖掘可以描述如下： 设1 = i l ，如，缸) 是一个项目集合，事务数据库胪 r l ，t 2 ，“) 是由 一系列具有唯一标识的事务组成，每个事务t i ( 卢1 ，2 ，行) 都对应，上的一 个子集。设厶， 在数据集d 上的支持度是包含 的事务在d 中所占的百 分比，即 s u p p o r t ( 6 ) - - b 纠厶c - , l l l l l o l l 对项目集，和事务数据库d ，丁中所有满足用户指定的最小支持度的项目集， 称为频繁项目集或者大项目集。在频繁项目集中挑选出所有不被其他元素包含 的频繁项目集成为最大频繁项目集。 一个定义在，和d 上形如i ji ，的关联规则可以通过满足一定的置信度来 给出。置信度是指包含 和如的事务数与包含 的事务数之比，即 c o n f i d e n c e ( i l 1 2 ) = s u p p o r t ( i li j1 2 ) s u p p o r t ( i i ) 其中厶，厶，厶n 厶= o 。d 在i 上满足最小支持度和最小置信度的关联规 则称为强关联规则。 从上述概念可以看出，给定一个事务数据库，关联规则挖掘问题就是通过 用户指定的最小支持度和最小置信度来寻找强关联规则的过程。因此关联规则 挖掘可以划分为两个步骤：第一步，通过用户给定的最小支持度，寻找所有支 持度大于等于最小支持度的频繁项目集；第二步，在每个最大频繁项目集中， 寻找置信度大于等于用户给定的最小置信度的关联规则。 8 武汉理工大学硕士学位论文 2 2 关联规则挖掘的经典算法 2 2 1a p rio r i 算法思想 a g r a w a l 等人在1 9 9 3 年提出了基于频繁项目集的a p r i o r i 算法，是目前最有 影响、最经典的布尔型关联规则挖掘算法【3 0 1 。该算法将挖掘关联规则分解成两 个子问题：一是找出所有的频繁项目集，也就是支持度大于给定的最小支持度 的项集；二是在所有的频繁项目集中产生强关联规则，即置信度大于给定的置 信度的规则。 a p r i o r i 算法通过对数据库d 的多趟扫描来发现所有的频繁项目集，在每一 趟扫描中只考虑具有同一长度七( 即项目集众所含项目的个数) 的所有艮项目集。 在第一趟扫描中，a p r i o r i 算法计算数据库d 中所有单个项目的支持度，根据最 小支持度m i n s u p 获得所有的频繁1 项集三l 。在后续的每一趟扫描中，首先以前 趟中所发现的所有频繁项目集为基础，生成所有新的候选项目集，即潜在的 频繁项目集，然后扫描数据库d ，计算这些候选项目集的支持度，最后根据最小 支持度m i n s u p 确定候选项目集中哪一些真正成为频繁项目集。依此类推，直至 不能产生新的频繁项目集为止。 2 2 2a p rio r i 算法描述 a 研o r i 算法实际上是一个递推的过程，下面描述具体的算法实现。 输入：事务数据库d ；最小支持度阈值m i n s u p 。 输出：d 中的频繁项目集三。 过程： ， ( 1 ) l i = l a r g e1 - i t e m s e t s ；所有支持度不小于m i n s u p 的1 项目集 ( 2 ) f o r ( 1 ( = 2 ；l k l g ；k + + ) d ob e g i n ( 3 )c k = a p r i o r i g e n ( l k i ) ；t i c k 是k 个元素的候选集 ( 4 ) f o ra l lt r a n s a c t i o n sted d ob e g i n ( 5 )c t = s u b s e t ( c k ，t ) ；c 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 = c c kic c o u n t 一m i n s u p 9 武汉理工大学硕士学位论文 ( 1 0 ) e n d ( 1 1 ) l = u l k ； 该算法中调用了a p r i o r i - g e n ( l k - i ) ，是为了通过( 卜1 ) 频繁项目集产生知 候选集。这种做法的好处是可以压缩产生频繁项目集的搜索空间。 a p r i o r i - g e n 函数算法如下： 输入：( k - 1 ) 频繁项目集上| 卜l 。 输出：缸候选集g ( 1 ) f o ra l li t e m s e tp l k 一1d o ( 2 ) f o ra l li t e m s e tq l k 1d o ( 3 ) i f p i t e m l = q i t e m l ，p i t e m 2 = q i t e m 2 ，p i t e m k 2 = q i t e m k 2 ， p i t e m k q ，m i n s u p ，置信度为7 5 1 0 0 = 0 7 5 ；，m i n c o n f i 看上去这个规则是正确的。但是购 买小说的概率为4 0 0 5 0 0 = 0 8 0 7 5 ，也就是说顾客只购买小说的概率大于顾客同 时购买小说和散文的概率，说明购买小说与散文之间实际上存在某种负相关。 计算负规则：不购买“，“散文 ) j ，“小说 ) ，支持度为3 2 5 5 0 0 = 0 6 5 m i n s u p ，置信度为3 2 5 4 0 0 - - 0 5 1 2 5 ；一m i n c o n f , 负规则也是正确的。但显然这两条 规则是相互矛盾的，那么根据支持度和置信度较大的为有趣的原则，可以删除 其中的条。 表2 1 小说和散文销售记录 买散文不买散文总计 买小说 7 53 2 54 0 0 不买小说 2 5 7 51 0 0 总计 1 0 04 0 05 0 0 2 4 2 负关联规则的支持度和置信度 类似于正关联规则的定义，对于项集卢 m 如，) 以及有n 条记录的 事务数据库d = 撕，t 2 ，f n ) ，相对于形如ajb 的正关联规则，形如aj - 1 b ， - - , aj b ，卅1 b 的逻辑蕴涵为负关联规则，其中一表示项集么不出现。当 负关联规则的支持度和置信度大于规定的最小支持度和置信度时，则认为它是 有意义的。 正关联规则发现的过程中，对于正项集彳= 币i 2 ，厶 的支持度计数为 数据库d 中包含项集4 的记录数，对于负项集1 b = ，f ，f ， ，其中艺表 示如项不出现。负项集- 1 b 的支持度计数为数据库d 中不包含 ，如，矗 的 记录的个数。因此对于负关联规则aj1 召的支持度为数据库d 中包含项集 f 1 ， 如，如) 但不包含项集 屯，i b ，玉) 的记录的个数除以数据库d 中总的记录 武汉理工大学硕士学位论文 数，即s ( 彳j1 b ) = | i r pu 1 bg r ，丁e ) l l l l e l l 。负关联规则4j 1 口的置信度 为c ( 么j - 1 曰) = i l r l 彳u _ 1 召s 丁，r d 川| | 丁i 彳丁，r d ) 0 。 负关联规则的支持度和置信度可以直接计算得到，但这样牺牲了效率。有 学者提出以下定理，通过对应的正项集求得负关联规则的支持度和置信度，节 省重新扫描数据库的时间，提高了算法的效率1 3 7 1 。 定理2 1 假定非空项集彳，b ，且彳n b = g 则有 ( 1 ) s ( 卅) = 1 - s ( a ) ； ( 2 ) s ( a i , j - - , b ) = s ( a ) - s ( a u b ) ； ( 3 ) s ( - - 4 u 功= s ( 研- s ( a u b ) ； ( 4 ) s ( “u - 1 功= l s ( 彳) 一s ( b ) + s ( 彳u 功； ( 5 ) c ( a 1 功= l - c ( x 动； ( 6 ) c ( 一b ) ：s ( 8 ) - s ( a ub ) ( 7 ) c ( 卅j 卅= 塑等铲= 1 - c ( - - , a 功 通过上述转化，就可以通过计算正关联规则的支持度和置信度求得对应的 负关联规则的支持度和置信度，节省了重新扫描数据库的时间，提高了算法的 效率。 1 6 武汉理工大学硕士学位论文 第3 章基于云模型改进的正负数量关联规则挖掘 3 1 云模型简介 我国学者李德毅提出了云概念，包括云模型、云发生器、云变换、云推理 等，进而发展完善成一整套云理论。云是用语言值表示的某个定性概念与其定 量表示之间的不确定性转换模型1 3 8 】，反映了客观世界中或人类知识中蕴含的两 种不确定性即模糊性和随机性，并把两者结合起来，构成定性定量间的相互映 射，为实现定性概念与定量数据间的相互转换提供了新的有力工具。 3 1 1 云的定义 设u 是一个用精确数值表示的定量论域，x u ，t 是u 空间上的定性概念， 若元素x ( x x ) 对丁所表达的定性概念的隶属确定度g ( x ) 【o ，1 】是一个有稳定 倾向的随机数，则概念丁从论域u 到区间 o ，l 】的映射在数域空间的分布，称为 云f 3 8 1 ，即 g o ) ：u j 0 ，1 】v x x ( x u ) x - - g ( x ) 此定义还可以推广到多维。 从云的基本定义可以看出，所有x u 到区间【0 ，1 】的映射是一对多的转换， x 对于丁的隶属度是一个概率分布而非固定值，而不是传统模糊隶属函数中的一 对一的关系，从而产生了云，而不是一条明晰的隶属曲线。云由许许多多的云 滴组成，一个云滴是定性概念在数量上的一次实现，这种实现带有不确定性， 但模型赋予这个点能够代表该定性概念的确定程度。单个云滴可能无足轻重， 在不同的时刻产生的云的细节可能不尽相同，但云的整体形状体现了云映射的 模糊性和随机性，反映了定性概念的基本特征。 3 1 2 云模型的数字特征 云的数字特征用期望e x 、熵e n 和超熵h e 这三个数值来表示，它们反映了 定性概念的定量特征，把模糊性和随机性集成到一起，构成知识表达的基础3 9 1 。 期望e x ：在普通论域u 中，对应于隶属度最大值的基础变量x 称为云的期 1 7 武汉理工大学硕士学位论文 望，它是在数域空间中最能够代表这个定性概念的点，反映这个概念的云滴群 的重心位置。 熵e n ：熵作为统计热力学的概念，用来度量物理系统的无组织程度。在云 模型中，熵被用来综合衡量定性概念的模糊度。熵的大小直接决定了在论域中 可被模糊概念接受的范围。熵越大，概念越宏观，模糊性和随机性越大，确定 性量化越难。 超熵h e ：超熵是熵的不确定性的度量，即熵的熵，反映了云滴的离散程度。 超熵的大小间接地表示了云的离散程度和厚度。超熵越大，云滴离散度越大， 隶属度随机性越大，云“厚度”越大。 3 1 3 正态云模型 正态云模型是基本的云模型，是表征语言原子的有力工具之一。正态分布 具有普适性，大量社会和自然科学知识中定性知识的云的期望曲线都近似服从 正态或半正态分布。在论域空间中，正态云模型的某一点的隶属度分不符合统 计学意义上的正态分布规律，以云的稳定倾向云期望曲线上的点为期望值 i 加1 。由期望和熵确定正态云的数学期望曲线为 g ( 加叫可- ( x - e x ) 2l 3 2 云发生器 云发生器是指软件模块化或者硬件固化的云模型的生成算法，这些算法建 立起定性和定量之间相互联系、相互依存的映射关系。云发生器主要包括正向 云发生器、逆向云发生器和条件云发生器，条件云发生器又分为x 条件云发生 器和y 条件云发生器【4 l 】。 3 2 1 正向云发生器 正向云发生器( c l o u dg e n e r a t o r ，简称c g ) 是用语言值描述的某个基本概 念与其数值表示之间的不确定性转换模型，是从定性到定量的映射。它根据云 的数字特征产生云滴，积累到一定数量汇聚为云，如图所示。正向云发生器实 现了从语言值表达的定性信息中获得定量数据的范围和分布规律，是一个前向 1 8 武汉理工大学硕士学位论文 的、直接的过程，输入表示定性概念的期望值戥、熵勘和超熵胁，云滴数量 ，输出的是个云滴在数据空间的定量位置及每个云滴代表该概念的确定度。 当概念对应的数域为一维时，正向云发生器的具体算法为： 输入：( e x ，e n ，h e ，加 输出：( d r o p ( x l ，c t ( x o ) ，d r o p ( x 2 ，c t 忆) ) ，d r o p ( x u , 喇) ) ； ( 1 ) 生成以砌为期望值，胁为标准差的一个正态随机数眈= n o r m ( e n ， 胁) ； ( 2 ) 生成以晟为期望，眺为标准差的一个正态随机数x 尸n o r m ( e x ，e n f ) ； 博c 胁叫篙笋| ( 4 ) 带有确定度c 舡) 的而成为数域中的一个云滴； ( 5 ) 重复前四步直至产生要求的个云滴。 其中，n o r m ( e x ，e n f ) 为生成以e x 为期望，e 协为标准差的正态随机数的函 数。给定正态云的三个数字特征值( e x ，e n ，h e ) ，上述算法可以生成任意个云滴 组成的正态云模型。 e x e n h e c g 3 2 2 逆向云发生器 d r o p ( x i ，c 如) ) 图3 1 正向云发生器 逆向云发生器是实现数值和其语言值之间的随时转换的不确定性转换模 型，是从定量到定性的映射。它将一定数量的精确数据有效转换为以恰当的定 性语言值( e x ，e n ，h e ) 表示的概念，并据此代表这些精确数据所反映的云滴的整 体。云滴对应的精确数据的数量越多，反映的概念越确切。逆向云发生器是一 个逆向的、间接的云生成过程，它把给定的符合某一分布规律的一组云滴d r o p ( x i ， c t ( x i ) ) 作为样本，产生描述云模型所对应的定性概念的三个数字特征( e x ，e n ， h e ) ，如图所示，具体算法为： 输入：( d r o p ( x 1 ，c r ( x o ) ，d r o p ( x 2 ，c t ( x g ) ，d r o p ( x u , c t ) ) 输出：慨，e n ，h e ) 1 9 武汉理工大学硕士学位论文 ( 1 ) 计算x i 的平均值e x = m e a n ( x f ) ，求得期望凰； ( 2 ) 计算x f 的方差e n 2 = s t d e v ( x i ) ，求得熵e n ； ( 3 ) 对每一数对d r o p ( x i ，c t 0 i ) ) ，计算五汤：= ( 4 ) 计算e n f 的方差h e 2 = s t d e v ( e n f ) ，求得超熵胁。 其中，m e a n ( ) 和s t d e v ( ) 分别为求样本均值和样本方差的函数。 取 勘 h e c g - 1 3 2 3 条件云发生器 图3 2 逆向云发生器 云可以根据不同的条件来生成。在给定论域的数域空间中，当已知云的三 个数字特征( e x ，e n ，h e ) 后，如果还有特定的张。条件，那么正向云发生器称为x 条件云发生器。反之，如果给定的条件是c r ( x ) = c t ( x o ) ，因为隶属度c r ( x ) 常常 用纵轴j ，表示，此时的发生器称为j ，条件云发生器。彳条件云发生器和j ，条件 云发生器是利用云模型进行不确定性推理的基础，如果将两者相连，就构成了 一个单条件规则发生器，如图所示。 d r o p ( x c 如油 图3 3x 条件云发生器和】，条件云发生器 d r o p ( x e ，c 舡i ) ) 图3 - 4 云的单条件单规则不确定性推理器 武汉理工大学硕士学位论文 从定义可以看出，条件云发生器的输出结果都是云带。x 条件云发生器的结 果是一条垂直于x 轴的竖直线，所有云滴的横坐标均为x o ，纵坐标隶属度值呈 概率分布】，条件云发生器的输出为以云的数学期望为对称中心的两条水平线。 纵坐标均为隶属度值c r ( x o ) ，两组横坐标数值呈概率分布。本文主要用到z 条件 云发生器，算法描述为： 输入：( e x