（管理科学与工程专业论文）多维关联规则算法设计.pdf

北京邮电大学硕士毕业论文多维关联规则算法设计 多维关联规则算法设计 摘要 数据挖掘，也称为数据库中的知识发现( k n o w l e d g ed i s c o v e r y i nd a t a b a s e ，k d d ) ， 是从大量数据中提取出可信、新颖、有效并能被人理解的模式的高级处理过程，而关联 规则是其6 种模式中的一种。从购物篮分析到电信、银行业等海量数据的分析处理，关 联规则已经在商业领域得到了广泛的实际应用，其中，寻找挖掘海量客户数据中的多维 关联规则更是潜力无穷。 传统的a p r i o r i 算法是基于单维数据库，寻找布尔关联规则的常见算法，但其效率 较低，使用范围有限的缺点同样明显，同时对于寻找多维关联规则并不适用。本文在原 有a 砸o r i 算法的基础上，自主设计了一种计数器算法，通过对目标数据库对象的自主 计数，有效地找到了一条寻找多维关联规则的方法，为多维数据库的关联规则挖掘提供 了更多的技术支持。 计数器算法除了打破了原有a 砸o r i 算法不适用于寻找多维关联规则的缺陷之外， 最大的优势在于在寻找多维关联规则的全过程中，只需要扫描一次目标数据库，这大大 节省了对系统的负担，尤其是在对海量数据或远程数据库进行关联规则挖掘的时候，提 高了整个算法的运行效率。 文章还通过自主编译的计算机程序，利用真实的电信企业用户数据，成功地寻找并 输出了多维关联规则，实现了计数器算法的实际应用。 关键字： 数据挖掘关联规则 a p r i o r i 算法 多维关联规则计数器算法 北京邮电大学硕士毕业论文多维关联规则算法设计 a r i t h m e t i cd e s i g no fm u i t - d i m e n s i o n a ia s s o c i a t i o nr u i e a b s t r a c t d a t am i n i n g ，a l s on 锄e da sk d d ( k n o w l e d g ed i s c o v e 叫i nd a t a b a s e ) ，i sa na d v a l l c e d p r o c e s si nw h i c hw ec a np i c ku pm 锄yt m s t 向l ，n o v e l ，u s e 如la n dr e a d a b l ep a t t e m s 舶mv e r y l a r g e 锄o u n t so fd a t a ，a i l da s s o c i a t i o nr u l ei so n eo ft h e6w a y so fd a t am o d e s f r o mm e m a r k e tb a s k e ta n a l y s i st op r o c e s s i n ga i l a l y s i so fn o o dd a t ai nt e l e c o m m u n i c a t i o n s ，b a l l k n g ， a s s o c i a t i o nr u l eh a sb e e na l r e a d yw i d e l yp u ti n t op r a c t i c a la p p l i c a t i o ni nt 1 1 ec o m m e r c i a l f i e l d ，i nw h i c hs e a r c h i n gm u l t i d i m e n s i o n a la s s o c i a t i o nr u l e 舶mn o o dd a t aa r ep o t e n t i a l e n d l e s s t r a d i t i o na p r i o r ia r i t h m e t i ci st h ec o m m o n 撕t h m e t i co fs e a r c l l i n gb o o l e a i la s s o c i a t i o n r u l eb a s e do nt h eo n e - d i m e n s i o n a ld a t a b a s e ，o fw h i c ht h es h o r t c o m i n g si sa l s oo b v i o u sb yi t s l o w e re m c i e n c ya 1 1 d l eu s eo fal i m i t e dr a i l g e ，w h i l ei ta l s oc a j l tb e 印p l i e di ns e a r c h i n g m u l t i d i m e n s i o n a la s s o c i a t i o nr u l e b a s e do nt h eo r i 百n a la p r i o r ia r i t h m e t i c ，t h ea n i c l e d e s i 盟st h ea r i t h m o m e t e ra r i t h m e t i ci t s e l w l l i c ht h r o u 曲t h ei n d 印e n d e n tc o u n tt om e t a r g e to b j e c td a t a b a s e ，e f r e c t i v e l yf o u n daw a yt os e a r c h i n gm u l t i d i m e n s i o n a la s s o c i a t i o n r u l e ， w h i c hp r o v i d e da d d i t i o n a lt e c h i c a l s u p p o r tf o r a s s o c i a t i o nr u l e m i n i n go f m u l t i d i m e n s i o n a ld a ta b a s e i i la d d i t i o nt ob r e a b n gt h el i m i t a t i o no fi n a p p l i c a b i l i t yi ns e a r c h i n gm u l t i d i m e n s i o n a l a s s o c i a t i o nr u l eb yo r i 百n a la p r i o r ia r i t l l m e t i c ，t h eb i g g e s ta d v a j l t a g eo fm ea n t l l i l l o m e t e r a r i t h m e t i cl i e si nm a tt h r o u 曲m e 伽l t i r ep r o c e s so fs e a r c h i n gf o rm u l t i d i m e n s i o n a l a s s o c i a t i o nr u l e ，i tn e e d ss c a nm et a r g e td a t a b a l s eo n l yo n c e ，w h i c h 黟e a t l yr e d u c et h eb u r d e n o nt h es y s t e m ，e s p e c i a l l yi nt h ea s s o c i a t i o nr 1 1 1 em i n i n gt om en o o do fd a t ao rr e m o t e d a t a b a l s e ，i i i l p r o v i n gm eo p e r a t i o ne 伍c i e n c yo fm ee n t i r e 撕仉m e t i c t l l r o u g hc o m p u t e 卜t r a n s l a t i o np r o c e d u r e s ，u s i n g m er e a lc l i e n td a t a o f t e l e c o 删 i l u i l i c a t i o n s e n t e 印r i s e ， m ea r t i c l es u c c e e d e di n s e a r c i l i n g a 1 1 d s a v i n g t h e m u l t i d i m e n s i o n a la s s o c i a t i o nr u l e ，w l l i c ha c h i e v e dm e p r a c t i c a l叩p l i c a t i o n o ft h e 北京邮电大学硕士毕业论文多维关联规则算法设计 “t l l i i l o m e t e ra r i t h m e t i c k e y w 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 e a p r i o r ia n t h m e t i c m u l t i d i m e n s i o n a la s s o c i a t i o n r u l e 嫡t o m e t e ra r i t h m e t i c 北京邮电大学硕士毕业论文 多维关联规则算法设计 1 1 数据挖掘的历史背景 第一章绪论 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数 据越来越多。激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行更 高层次的分析，以便更好地利用这些数据。目前的数据库系统可以高效地实现数 据的录入、查询、统计等功能，但无法发现数据中存在的关系和规则，无法根据 现有的数据预测未来的发展趋势。缺乏挖掘数据背后隐藏的知识的手段，导致了 “数据爆炸但知识贫乏”的现象。 计算机技术的另一领域人工智能自1 9 5 6 年诞生之后取得了重大进展。 经历了博弈时期、自然语言理解、知识工程等阶段，目前的研究热点是机器学习。 机器学习是用计算机模拟人类学习的一门科学，比较成熟的算法有神经网络、遗 传算法等。 用数据库管理系统来存储数据，用机器学习的方法来分析数据，挖掘大量数 据背后的知识，这两者的结合促成了数据库中的知识发现( k d d ：k n o w l e d g e d i s c o v e r yi nd a t a b a s e s ) 的产生。实际上，数据库中的知识发现是一门交叉性学 科，涉及到机器学习、模式识别、统计学、智能数据库、知识获取、数据可视化、 高性能计算、专家系统等多个领域。从数据库中发现出来的知识可以用在信息管 理、过程控制、科学研究、决策支持等许多方面。 1 9 8 9 年8 月在美国底特律召开的第1 1 届国际人工智能联合会议的专题讨论 会上首次出现i d 这个术语。随后在1 9 9 1 年、1 9 9 3 年和1 9 9 4 年都举行l d 专题讨论会，汇集来自各个领域的研究人员和应用开发者，集中讨论数据统计、 海量数据分析算法、知识表示、知识运用等问题。随着参与人员的不断增多， k d d 国际会议发展成为年会。1 9 9 8 年在美国纽约举行的第四届知识发现与数据 挖掘国际学术会议不仅进行了学术讨论，并且有3 0 多家软件公司展示了他们的 数据挖掘软件产品，不少软件已在北美、欧洲等国得到应用。 数据挖掘是l d 最核心的部分，是采用机器学习、统计等方法进行知识学 第l 页一共5 4 页 北京邮电大学硕士毕业论文多维关联规则算法设计 习的阶段。数据挖掘算法的好坏将直接影响到所发现知识的好坏。目前大多数的 研究都集中在数据挖掘算法和应用上。人们往往不严格区分数据挖掘和数据库中 的知识发现，把两者混淆使用。一般在科研领域中称为i d ，而在工程领域则 称为数据挖掘。 1 2 数据挖掘在商业中的应用 数据挖掘技术从一开始就是面向应用的。它可以应用在各个不同的领域，电 讯公司和信用卡公司是用数据挖掘检验具有欺诈行为的先行者，保险公司和证券 公司也开始采用数据挖掘技术来减少欺诈，医疗部门则是另一个前景广阔的产 业：数据挖掘可以用来预测外科手术，医疗试验和药物治疗效果，零售商更多的 使用数据挖掘来决定每种商品在不同地点的库存，通过数据挖掘使用促销和优惠 卷手段，制药公司通过挖掘巨大的化学物质和基因对疾病的影响，通过数据库来 判断哪些物质可能对治疗某种疾病产生效果。可以说，在很多领域中，数据挖掘 ( d a t am i i l i n g ) 都是一个很时髦的词，尤其是在如银行、电信、保险、交通、零 售( 如超级市场) 等商业领域。 数据挖掘所能解决的典型商业问题包括：数据库营销( d a t a b a s em a r k e t i n g ) 、 客户群体划分( c u s t o m e rs e g m e n t a t i o n c l a u s s i f i c a t i o n ) 、背景分析( p m 6 1 e a n a l y s i s ) 、交叉销售( c r o s s s e l l i n g ) 等市场分析行为，以及客户流失性分析( c h u m a n a l y s i s ) 、客户信用( c r e d i ts c o 血g ) 、欺诈发现( f r a u dd e t e c t i o n ) 等等。 1 2 1 数据挖掘在市场营销的应用 数据挖掘技术在企业市场营销中得到了比较普遍的应用，他是以市场营销学 的市场微分原理为基础，其基本假定是“消费者过去的行为是其今后消费倾向的 最好说明”。 通过收集、加工和处理设计消费者消费行为的大量信息，确定特定消费群体 或个体的消费兴趣、消费习惯、消费倾向和消费需求，进而推断出相应消费群体 或个体下一步的消费行为，然后以次为基础，对所识别出来的消费群体进行特定 内容的定向营销，这与传统的不区分消费者对象特征的大规模营销手段相比，大 大节省了营销成本，提高了营销效果，从而为企业带来更多的利润。 第2 页一共5 4 页 北京邮电大学硕士毕业论文多维关联规则算法设计 商业消费信息来自市场中的各种渠道。例如，每当我们用信用卡消费时，商 业企业就可以在信用卡结算过程中收集商业消费信息，记录下我们进行消费的时 间、地点、感兴趣的商品或服务、愿意接受的价格水平和支付能力等数据；当我 们在申办信用卡、办理汽车驾驶执照、填写商品保修单等其他需要填写表格的场 合时，我们的个人信息就存入了相应的业务数据库；企业除了自行收集相关业务 信息之外，甚至可以从其它公司或机构购买此类信息为自己所用。 这些来自各种渠道的数据信息被组合，应用超级计算机、并行处理、神经元 网络、模型话算法和其他信息处理技术手段进行处理，从中得到商家用于向特定 消费群体或个体进行定想营销的决策信息。这种数据信息是如何应用的呢? 举一 个简单的例子，当银行通过对业务数据进行挖掘后，发现一个银行账户持有者突 然要求申请双人联合账户时，并且确认该消费者是第一次申请联合账户，银行会 推断该用户可能要结婚了，他就会向该用户定向推销用于购买房屋、支付子女学 费等长期投资业务，银行甚至可能将该信息卖给专营婚庆商品和服务的公司。可 以说，数据挖掘构筑了竞争优势。 在市场经济比较发达的国家和地区，许多公司都开始在原有信息系统的基础 上通过数据挖掘对业务信息进行深加工，以构筑自己的竞争优势，扩大自己的营 业额。美国运通公司( a m 甜c a ne x p r e s s ) 有一个用于记录信用卡业务的数据库， 数据量达到5 4 亿字符，并仍随着业务进展不断更新。运通公司通过对这些数据 进行挖掘，制定了“关联结算( r e l a t i o ns h i pb i l l i n g ) 优惠”的促销策略，即如 果一个顾客在一个商店用运通卡购买一套时装，那么在同一个商店再买一双鞋， 就可以得到比较大的折扣，这样既可以增加商店的销售量，也可以增加运通卡在 该商店的使用率。再如，居住在伦敦的持卡消费者如果最近刚刚乘英国航空公司 的航班去过巴黎，那么它可能会得到一个周末前往纽约的机票的打折优惠卡。 基于数据挖掘的营销，常常可以向消费者发出与其以前的消费行为相关的推 销材料。卡夫( 心a r ) 食品公司建立了一个拥有3 0 0 0 万客户资料的数据库，数 据库是通过收集对公司发出的优惠卷等其他促销手段做出积极反应的客户和销 售记录而建立起来的，卡夫公司通过数据挖掘了解特定客户的兴趣和口味，并以 此为基础向他们发送特定产品的优惠卷，并为他们推荐符合客户口味和健康状况 的卡夫产品食谱。美国的读者文摘出版公司运行着一个积累了4 0 年的业务数据 库，其中容纳有遍布全球的一亿多个用户的资料，数据库每天2 4 小时连续运行， 保证数据不断得到实施的更新。正是基于对客户资料数据库进行数据挖掘的优 势，使读者文摘出版公司能够从通俗杂志扩展到专业杂志、书刊和声像制品的出 版与发行，极大的扩展了自己的业务。 第3 页一共5 4 页 北京邮电大学硕士毕业论文多维关联规则算法设计 基于数据挖掘的营销对我国当前的市场竞争中也很具有启发意义，我们经常 可以看到繁华商业界上一些厂商对来往行人不分对象地散发大量商品宣传广告， 其结果是不需要的人随手丢弃资料，而需要的人并不一定能够得到。如果搞家电 维修服务的公司向在商场中刚刚购买家电的消费者邮寄维修服务广告，卖特效药 品的厂商向医院特定门诊就医的病人邮寄广告，肯定会比漫无目的的营销效果要 好得多。 1 2 2 数据挖掘在电信、金融方面的成功案例 1 2 2 - 1 数据挖掘技术在国外电信公司的应用 国外电信公司参与市场竞争较早，善于从数据中挖掘信息。他们使用数据仓 库系统进行客户分类、服务分析、话务量分析、销售代理分析以及地区分析等等， 了解收入和业务等。了解上述信息后，对需要而尚未购买服务的客户，以营销管 理的科学方法对其进行服务销售，因为购买率和成交率高，且后续的客户终生价 值和利润贡献度增加，达到扩大市场份额、增加利润的目的，适合科学的企业经 营模式，可以了解客户、取悦客户，持续获利，已经成为国外电信公司生存的竞 争优势。 m c i 公司是美国第二大电信公司，针对用户的消费特点，他们推出了环球 亲友计划( o r i 百n a l 衔e n d sa i l d 觚i l yp r o 伊锄) ，允许用户选择一定数量的亲友， 在给他们打电话时享受特殊条件的优惠，但前提是其亲友也必须是m c i 用户。 通过这个策划，m c i 争取到了许多用户，扩大了市场份额。 英国电信( b t ) 的总裁认为：保持一个庞大的客户群，不断开发用户需求 的业务和提供尽可能多的接入模式，是电信公司必须具备的最基本的能力。因此， 英国电信根据用户需要不断推出各种新业务，比如：连线游戏，可以是不同地方、 不同网络的用户使用连线进行交互；校园世界，可以使若干大学通过计算机网络 连在一起，实现校方资源的共享；多媒体“信息亭”，在公共场所设立信息亭， 提供收发电子邮件的职能终端等。在电信运营公司中，经常会遇到这种情况，用 户不能及时付清账单，经营者采取怎样的措施才能使公司的损失降到最低昵? 针 对这种情况，英国电信采用及其学习技术，建立了自己的预测模型，将历史上的 做法制成案例，成为培训的样本，来预测采用何种措施的效益最好。英国电信在 预测模型的开发过程中，总结了两大经验：一是在预测前先将问题简化，通过征 第4 页一共5 4 页 北京邮电大学硕士毕业论文多维关联规则算法设计 求各界专家的意见，将任务分成两类，每一类有不同的结果；二是利用神经网络 或决策数的方法，结合历史数据构成不同的判断条件。通过利用数据挖掘，英国 电信有效的对用户欠费进行了回收，并成功预防了欠费的发生。 m t t 公司是加拿大最著名的电信公司。与其他电信公司一样，m t & t 在 加拿大电信史上一直处于垄断地位。直到最近几年，8 0 年代首先影响北美的电 信分离改变了加拿大电信的运转轨迹，首先是长途展开竞争，紧跟其后，本地电 话也卷入了竞争大战。在争夺市场份额的激烈竞争中，m t & t 采用了强有力的 手段数据挖掘软件来取得竞争优势。该软件是s a s 公司开发的企业挖掘者 ( e n t e 唧s em i n e r ) ，他根据公司拥有的大量数据分析趋势，发掘模型，发现市 场机会，为决策者提供新的思路。m t & t 客户服务部总经理莫瑞说：“数据挖掘 已经成为我们商业活动的核心”，利用数据挖掘，m t & t 公司能准确的进行客户 定位，并及时了解发现客户的需要，公司在事实的基础上进行了正确的决策，摆 脱了以前仅凭经验猜测的状态，不仅在财政预算上得到了节约，更重要的是市场 份额不断增加，公司发展迅速。 1 2 2 2 数据挖掘技术在商业银行中的应用 金融事务需要搜集和处理大量的数据，由于银行在金融领域的地位、工作性 质、业务特点以及激烈的市场竞争决定了它对信息化、电子化比其他领域有更迫 切的要求。利用数据挖掘技术可以帮助银行产品开发部门描述客户以往的需求趋 势，并预测未来。美国商业银行是发达国家商业银行的典范，许多地方值得我国 学习和借鉴。 数据挖掘技术在美国银行金融领域应用广泛。金融事务需要搜集和处理大量 数据，这些数据进行分析，发现其数据模式及特征，然后可能发现某个客户、消 费群体或组合金融和商业兴趣，并可观察金融市场的变化趋势。商业银行业务的 利润和风险是共存的。为了保证最大的利润和最小的风险，必须对账户进行科学 的分析和归类，并进行信用评估。m e l o n 银行使用i n t e l l i g e n ta g e n t 数据挖掘软 件提高销售和定价金融产品的精确度，如家庭普通贷款。零售信贷客户主要有两 类：一类很少使用信贷限额( 低循环者) ，另一类能够保持较高的未清余额( 高 循环者) 。每一类都代表着销售的挑战。低循环者代表缺省和支出注销费用的危 险性较低，但会带来极少的净收入或负收入，因为他们的服务费用几乎与高循环 者的相同。银行常常为他们提供项目，鼓励他们更多的使用信贷限额或找到交叉 销售高利润产品的机会。高循环者由高等和中等危险元件构成。高危险分段具有 支付缺省和注销费用的潜力。对于中等危险分段，销售项目的重点是留住可获利 的客户并争取能带来相同利润的新客户。但根据新观点，用户的行为会随时间而 第5 页一共5 4 页 北京邮电大学硕士毕业论文多维关联规则算法设计 变化。分析客户整个生命周期的费用和收入就可以看出谁是最具创利潜能的。 m e l o n 银行认为“根据市场的某一部分进行定制 能够发现最终用户并将市场定 位于这些用户。但是，要这么做就必须了解关于最终用户特点的信息。数据挖掘 工具为m e l o n 银行提供了获取此类信息的途径。m e l o n 银行销售部在限期数据挖 掘项目上使用i n t e l l i g e n c ea g e n t 寻找信息，主要目的是确定现有m e l o n 用户购买 特定附加产品：家庭普通信贷限额的倾向，利用该工具可生成用于检测的模型。 据银行官员称：i n t e l l i g e n c ea g e n t 可帮助用户增强其商业智能，如分类或回归分 析，依赖这些能力，可对那些有较高倾向购买银行产品、服务产品和服务的客户 进行有目的的推销。该官员认为，该软件可反馈用于分析和决策高质量信息，然 后将信息输入产品的算法。除此之外，i n t e l l i g e n c e a g e n t 还有可定制能力。 美国f i r s t a r 银行使用m a r k s m a n 数据挖掘工具，根据客户的消费模式预测何 时为客户提供何种产品。f i r s t a r 银行市场调查和数据库营销部经理发现：公共数 据库中存储着关于每位消费者的大量信息，关键是要透彻分析消费者投入到新产 品中的原因，在数据库中找到一种模式，从而能够为每种新产品找到最合适的消 费者。m a r k s m a l l 能读取8 0 0 到1 0 0 0 个变量并且给它们赋值，根据消费者是否有 家庭财产贷款、赊账卡、存款证或其它储蓄、投资产品，将它们分成若干组，然 后使用数据挖掘工具预测何时向每位消费者推荐哪种产品。预测准客户的需要是 美国商业银行的竞争优势。 1 3 各章节内容介绍 对数据挖掘有的初步的认识和了解之后，下面本文将围绕数据挖掘算法中的 关联规则展开深入探讨，在已有的关联规则a p r i o r i 算法的基础上，独立创新研 究一种挖掘多维关联规则更为可行的新算法，并讨论该算法在实际中的应用。 本文共分为五章，下面简单介绍一下二至五章的主要内容： 第2 章是关联规则和a 研o r i 算法的简述，主要简单介绍了关联规则的基本 概念，所涉及的各种重要参数等等，以及在整个数据挖掘方法中的地位。a 研o r i 算法是最常见和常用的挖掘单维布尔关联规则的算法，也是本文将提出的计数器 算法的基础，这一章的后半部分将主要介绍该算法的内容和思路，以及目前公认 的一些改进方法。 第3 章是本文的中心所在，提出了挖掘多维关联规则中频繁项集的计数器算 法，主要内容包括该算法的思路、流程、伪代码，以及算法面对的主要问题。 第4 章是算法的实际应用部分，通过实际编写的计算机程序，选择了两种途 第6 页一共5 4 页 北京邮电大学硕士毕业论文多维关联规则算法设计 径实现计数器算法，分别挖掘随机产生的数据表和实际的电信企业用户数据中的 强关联规则，以实现算法的真正应用。最后在算法效率方面与原始a 研o r i 算法 进行了比较。 最后一章是对算法的综合评价，包括评价算法解决的核心问题，算法面临的 不足与缺陷，以及算法的主要改进方向等。 第7 页一共5 4 页 北京邮电大学硕士毕业论文 多维关联规则算法设计 第二章关联规则与a p r i o r i 算法简述 2 - 1 数据挖掘的定义及其分类 2 1 1 数据挖掘的定义 在绪论中已经介绍过，数据挖掘( d a t am i n i n g ) 就是指从大型数据库或数据 仓库中提取人们感兴趣的知识，这些知识是隐含的、事先未知的潜在有用信息。 数据挖掘是一个高级的处理过程，它从数据集中识别出以模式来表示的知识。高 级的处理过程是指一个多步骤的处理过程，多步骤之间相互影响、反复调整，形 成一种螺旋式上升过程。 数据挖掘的过程与人类问题求解的过程是存在巨大相似性的。具体比较见表 2 1 。挖掘过程可能需要多次的循环反复，每一个步骤一旦与预期目标不符，都 要回到前面的步骤，重新调整，重新执行。 表2 1 s t e p si ns o i v i n gap r o b i e m f l 】 聊i c a lh u m a i ld e c i s i o nm a k i l l gk n o w l e d g ed i s c o v e r yp r o c 髓s d e f i n em ep r o b l 锄d e f m em ep m b l 锄 c o l l e c tt l l ef a c t so b t a i l ld a t at od e m o n s 缸a t ep a s te x p e r i e n c e r e v i e wm eq u a l i 哆o fy o u rf a c t s p r e p r o c e s sm e d a t a g c n e r a l i z eo ny o u rf a c t s r e v i e wp o t e n t i a ls o l u t i o n s d e v e l 叩a m o d e l c h e c ky o l l rg e n e r a l i z a t i o n s v a i i d a t em em o d e l r e v i e wy o u ro b j e c t i v 铭d 嘶n ey o u ro b j e c t i v e s e v a l u a t ea us o l u t i o n st od e t e n n i l l et l l eb e s ts o l u t i o n o p m i z e l ep r o b l 锄一f m dm eb e s t s o l u t i o n 2 1 2 数据挖掘的分类 数据挖掘按照其实际作用可细分为以下6 种： 1 、分类模式 分类模式是一个分类函数( 分类器) ，能够把数据集中的数据项映射到某个 给定的类上。分类模式往往表现为一棵分类树，根据数据的值从树根开始搜索， 第8 页一共5 4 页 北京邮电大学硕士毕业论文 多维关联规则算法设计 沿着数据满足的分支往上走，走到树叶就能确定类别。 2 、回归模式 回归模式的函数定义与分类模式相似，它们的差别在于分类模式的预测值是 离散的，回归模式的预测值是连续的。如给出某种动物的特征，可以用分类模式 判定这种动物是哺乳动物还是鸟类；给出某个人的教育情况、工作经验，可以用 回归模式判定这个人的年工资在哪个范围内，是在6 0 0 0 元以下，还是在6 0 0 0 元到1 万元之间，还是在1 万元以上。 3 、时间序列模式 时间序列模式根据数据随时问变化的趋势预测将来的值。这里要考虑到时间 的特殊性质，像一些周期性的时间定义如星期、月、季节、年等，不同的日子如 节假日可能造成的影响，日期本身的计算方法，还有一些需要特殊考虑的地方如 时间前后的相关性( 过去的事情对将来有多大的影响力) 等。只有充分考虑时间 因素，利用现有数据随时间变化的一系列的值，才能更好地预测将来的值。 4 、聚类模式 聚类模式把数据划分到不同的组中，组之间的差别尽可能大，组内的差别尽 可能小。与分类模式不同，进行聚类前并不知道将要划分成几个组和什么样的组， 也不知道根据哪一( 几) 个数据项来定义组。一般来说，业务知识丰富的人应该 可以理解这些组的含义，如果产生的模式无法理解或不可用，则该模式可能是无 意义的，需要回到上阶段重新组织数据。 5 、关联模式 关联模式是数据项之间的关联规则。关联规则是如下形式的一种规则：“在 无力偿还贷款的人当中，6 0 的人的月收入在3 0 0 0 元以下。” 6 、序列模式 序列模式与关联模式相仿，而把数据之间的关联性与时间联系起来。为了发 现序列模式，不仅需要知道事件是否发生，而且需要确定事件发生的时间。例如， 在购买彩电的人们当中，6 0 的人会在3 个月内购买影碟机。 在解决实际问题时，经常要同时使用多种模式。分类模式和回归模式是使用 最普遍的模式。分类模式、回归模式、时间序列模式也被认为是受监督知识，因 为在建立模式前数据的结果是己知的，可以直接用来检测模式的准确性，模式的 产生是在受监督的情况下进行的。一般在建立这些模式时，使用一部分数据作为 样本，用另一部分数据来检验、校正模式。聚类模式、关联模式、序列模式则是 非监督知识，因为在模式建立前结果是未知的，模式的产生不受任何监督。 第9 页一共5 4 页 北京邮电大学硕士毕业论文多维关联规则算法设计 2 2 关联规则的基本概念及分类 如前所述，数据项之间的关联规则成为关联模式。我们所要讨论的问题集中 在数据挖掘中的关联规则( a s s o c i a t i o ni 沁l e s ) 上，也就是上述六个模式中的第 五个。 数据挖掘是由大多数大型零售商面临的决策支持( d e c i s i o ns u p p o r t ) 问题所 促使产生的。条形码( b 扑c o d e ) 技术的进步使得零售商有能力收集和储存大量 的销售数据，称为屑瑾铳篮仍伽眈f 夕数据。一条记录通常是由交易( n 彻s a c t i o n ) 数据和交易中所买的项( i t e i l l ) 即物品组成。更通常的是，数据记录也包含 了客户号( c u s t o m e r - i d ) ，特别当买主是持有信用卡或商店优惠卡的顾客时。 由于条形码技术的发展，零售部门可以利用前端收款机收集存储大量的售货 数据。因此，如果对这些历史事务数据进行分析，则可对顾客的购买行为提供极 有价值的信息。例如，可以帮助如何摆放货架上的商品( 如把顾客经常同时买的 商品放在一起) ，帮助如何规划市场( 怎样相互搭配进货) 。而对于电信部门，同 样可以从众多的通信数据中发掘潜在的关系，以制定更多的通信决策。由此可见， 从事务数据中发现关联规则并以此为基础挖掘出序列模式，对于改进各种商业活 动的决策非常重要。 2 2 1 研究对象及定义 假如有一个超市的经理，希望更加了解顾客的购物习惯。比如他想知道“什 么商品组或集合顾客多半会在一次购物时同时购买? ”为了回答这个问题，可以 在他的商店顾客事务零售数据上运行购物栏分析。分析结果可以用于市场规则、 广告策划和分类设计。例如，购物栏分析可以帮助经理设计不同的商店布局。一 种策略是：经常一块购买的商品可以放近一些，以便进一步刺激这些商品一起销 售。另一种策略是：将经常一块购买的商品放在商店的两端，可能诱发买这些商 品的顾客一路挑选其他商品。 如果我们想象全域是商品中可利用商品的集合，则每种商品有一个布尔变 量，表示该商品的有无。每个篮子则可用一个布尔向量表示。可以分析布尔向量， 得到反映商品频繁关联或同时购买的购买模式。这些模式可以用关联规则的形式 表示。 关联规则挖掘寻找给定数据集中项之间的特殊联系，发现的主要对象是事务 数据库。如售货数据，即上面所说的购物篮数据( b a s k e td a t a ) ，顾客的属性数据 第1 0 页一共5 4 页 北京邮电大学硕士毕业论文多维关联规则算法设计 等。 关联规则定义：设卢 i ，f ：，i 。) 是项的集合。设任务相关的数据d 是 数据库事物的集合，其中每个事物t 是项的集合，使得t ( ，。每一个事物有一个 标识符，称作t i d 。设a 是一个项集，事务t 包含a 当且仅当a c t 。关联规则 是形如a = b 的蕴含式，其中a c i ，b c i ，并且a n b = 。 2 2 2 主要参数 2 2 2 1 置信度( c o n 翻d e n c e ) 如果d 中包含a 的事物同时也包含b 的百分比是c ，那么规则a jb 在事 物集d 中具有置信度c ，它是条件概率p ( ba ) 。即 c 。妒概m 蚓印c 叭，= 筹 式( 2 1 ) 置信度是对关联规则准确度的衡量。 例如，假定任务相关数据由某公司的计算机部的事务数组成。一个置信度为 7 0 的关联规则 6 。i ) 塔( 兄“c d ，矽甜胞，”) = 6 z ! ) 疆( 兄“j ( ! h ，以陀” ) 式( 2 2 ) 表示买计算机的顾客7 0 也买软件。 置信度为1 0 0 或1 以为在数据分析时，该规则总是正确的。这种规则称为 准确的( e x a c t ) 。 2 2 1 2 2 支持度( s u p p o r t ) 规则a jb 在事物集d 中成立，具有支持度s ，其中s 是d 中事物包括a ub ( 即a 和b 二者) 的百分比，它是概率p ( aub ) ，即 一州a 圳印c ，= 笪学 式( 2 3 ) 支持度是对关联规则重要性( 或适用范围) 的衡量。 例如，假定任务相关数据由某公司的计算机部的事务数组成。一个支持度为 第l l 页一共5 4 页 北京邮电大学硕士毕业论文多维关联规则算法设计 3 0 的关联规则( 2 2 ) 表示计算机部的所有顾客的3 0 同时购买了计算机和软 件。 同时满足最小置信度阈值( m f ，l j 印) 和最小支持度阈值( m f 玎- c d 的规 则称作强规则。 2 2 2 3 期望可信度( e x p e c t - s u p p o r t ) 物品集b 出现的概率称为期望可信度，用公式表示为：p ( b ) 。 期望可信度描述在没有物品集a 的作用下，物品集b 本身的支持度。 2 2 - 2 4 作用度( e f r e c t ) 置信度对期望可信度的比值称为作用度( 也称为提升度) ，用公式表示为：p ( bia ) p ( b ) 。 作用度描述物品a 对物品b 的影响力的大小。作用度大于1 的关联规则才 有意义。 为了方便，常用o 和1 0 0 之间的值表示以上四个参数，而不是用。到l 之间的小数值。 2 2 2 5 项集( i t e m s e t ) 项的集合成为项集( i t e m s e t ) 。包含尼个项的项集称为舡项集。集合 c d 聊p “纪， 加口，z c 砌t 口，z 昭踟p 甩。妒m 坨) 是一个2 一项集。项集的出现频率是包含项集的事 务数，简称为项集的频率、支持计数或计数。如果项集的出现频率大于或等于 聊f 玎s 印与d 中事务总数的乘积，那么项集满足最小支持度胁伽s 印。如果项集 满足最小支持度，则称它为频繁项集( 丘钢u e n ti t e m s e t ) 。频繁肛项集的集合通常 记作t 。 2 2 2 6 关联规则的挖掘步骤 关联规则的挖掘是一个两步的过程： 1 ) 找出所有频繁项集：根据定义，这些项集出现的频繁性至少和预定义的最小 支持计数一样。 2 ) 由频繁项集产生强关联规则：根据定义，这些规则必须满足最小支持度和最 第1 2 页一共5 4 页 北京邮电大学硕士毕业论文多维关联规则算法设计 和6 缈。 本文主要讨论的算法就是集中解决如何使用改进的a 研o r i 算法更加有效的 挖掘多维关联规则。 2 2 3 3 根据规则集所涉及的抽象层 如果挖掘关联规则的方法可以在不同的抽象层发现规则，则称所挖掘的规则 集由多层关联规则( m u l t i 1 e v e la s s o c i a t i o nm l e ) 组成； 例如，在规则 孵( k “4 0 4 9 ”) 6 垆( 兄“坳卸c d 叩“纪，”) 式( 2 7 ) 昭e ( 兄“4 0 4 9 ”) 6 妙，( 正“c d ，印“地r ”) 式( 2 8 ) 中，购买的商品涉及不同的抽象层( 即“c d ，印“纪r ”在比“如p 矗印c d 碑，“纪，| ”高 的抽象层) ，这就属于多层关联规则。 如果在给定的规则集中，规则不涉及不同抽象层的项或属性，则该集合包含 单层关联规则( s i n g l e - 1 e v e la s s o c i a t i o nr u l e ) 。 2 2 3 4 根据关联挖掘的各种扩充 关联挖掘可以扩充到相关分析，那里可以识别项是否相关，还可以扩充到挖 掘最大模式( 即最大的频繁模式) 和频繁闭项集。使用最大模式和频繁闭项集可 以显著的压缩挖掘所产生的频繁项集数。 最大模式是频繁模式p ，使得p 的任何真超模式都不是频繁的。( 其中超模 式是指：如果p 是g 的字模式或者说子集，即g 包含p ，则g 是p 的超模式。真 超模式则指p 是g 的真子集，则g 是p 的真超模式。) 频繁闭项集事一个频繁的闭的项集，其中项集c 是闭的，如果不存在c 的真 超集c ，使得每个包含c 的事务也包含c 。 第1 4 页一共5 4 页 北京邮电大学硕士毕业论文 多维关联规则算法设计 小置信度。 2 2 3 关联规则的分类 根据不同的标准，关联规则有多种分类方法： 2 2 3 1 根据规则中所处理的值类型 如果规则考虑的关联事项的在与不在，则称为布尔关联规则( b 0 0 1 e a n a s s o c i a t i o ni u l e ) ： 例如，购买计算机也趋向于同时购买财务管理软件可以用以下关联规则表 示： c d ，穆p “胞，j 夕刀口玎c 缸l 聊口玎q g p m e ，z t q 所馏陀墨雄矽d 厂卢2 ，c d 妒出馏c e = 6 0 】 式( 2 4 ) 如果规则描述的是量化的项或属性之间的关联，则称为量化关联规则 ( q u a i l t i t a t i v ea s s o c i a t i o nm l e ) 。在这种规则中，项或属性的量化值划分为区间。 例如， 孵( x ，“4 0 4 9 ” ) 八砌聊e ( x ，“5 呱5 8 置”) j 6 缈( x ， “h i g h r s o l u t i o n j v ”、) 式( 2 5 ) 其中，x 是代表顾客的变量，且量化属性a g e 和i n c o m e 己离散化。 2 2 3 2 根据规则中涉及的数据维 如果关联规则中的项或属性每个只涉及一个维，则称为单维关联规则 ( s i n 舀e - d i m e n s i o n a la s s o c i a t i o nr u l e ) ； 例如，规则( 3 4 ) 可以写作： 砸声( 兄“，印“地，”) 6 m 声( 兄乡锄口刀c 砌竹口刀口g p 聊册o q m 阳愆” ) 式( 2 6 ) 这就是一个单维关联规则，因为它只涉及一个维6 郴。 如果规则涉及两个或多个维，则称为多维关联规则( m u l t i d i m e i l s i o n a l a s s o c i a t i o nr u l e ) 。 例如规则( 3 5 ) 就是一个多维关联规则，因为它涉及三个维孵，砌m e 第1 3 页一共5 4 页 北京邮电大学硕士毕业论文多维关联规则算法设计 2 3a p r i o r i 算法简介 a 龋1 w a l 等于1 9 9 3 年首先提出了挖掘顾客交易数据库中项集间的关联规则 问题，其核心方法是基于频集理论的递推方法。这种关联规则是单维、单层、布 尔关联规则。其中最基本的是使用候选项集找频繁项集的a p r i o r i 算法，和不产 生候选，挖掘全部频繁项集的频繁模式增长( 行e q u e n t - p a t t e m 留o w t h ) 算法，