（计算机软件与理论专业论文）家具配件销售行业的关联挖掘研究.pdf

西南交通大学硕士研究生学位论文第f 页 摘要 近些年来，家具配件销售行业的竞争压力越来越大，单纯依靠传统的方法已经不 足以帮助销售商获得更大的市场份额和利润空间了。关联挖掘是数据挖掘中的一个重 要问题，是发现和分析不同数据项之间的关联性的过程。将关联挖掘技术引入家具配 件销售行业中，获取配件产品的销售特点和联系，能够帮助销售商把握消费者的潜在 购买习惯和需求，以便制定相应的销售和进货策略。 本文研究了关联规则挖掘技术在家具配件销售行业中的应用细节和过程，并且对挖 掘出的关联规则进行了简要地分析和应用设计。在本文中，首先介绍了本次挖掘的项 目背景，并阐述了关联规则挖掘技术的国内外现状和研究的关键问题。然后介绍了关 联挖掘过程中涉及到的一些重要的概念和原理，尤其对挖掘步骤进行了简要设计和说 明。之后在需求分析的部分，详细介绍了销售数据的特点，并从功能需求、方法需求、 其他需求三个方面说明了需求的情况。接下来的概要设计部分，从数据的流动情况、 步骤的设计思想和操作过程、遇到问题解决问题的思考过程、数据库表的设计等多个 角度详细地介绍了各个挖掘步骤的情况，并在介绍过程中适当地举了些本次挖掘的实 例。详细设计部分，主要是本次挖掘的代码情况的介绍，具体的说，就是介绍了u t i l i t y 、 r u l e 、d b a d m i n 三个主要的类中各个方法的流程。最后的结果展示和分析部分，将挖 掘出的关联规则做了简要说明和示例性展示，并对这些规则进行了较为详细的分析和 应用方面的设计。 关键词：家具配件销售数据；候选配集；频繁配集；关联规则 西南交通大学硕士研究生学位论文 第1i 页 a b s tr a c t r e c e n ty e a r st h ec o m p e t i t i v ep r e s s u r ei ns a l e si n d u s t r yo ff u r n i t u r ea c c e s s o r yh a s i n c r e a s e d n ol o n g e rd o e sp u r e l yt r a d i t i o n a lm e t h o dh e l pr e t a i l e r sg a i nf u r t h e rm a r k e t p e r c e n t a g ea n dp r o f i tm a r g i n a s s o c i a t i o nr u l e sm i n i n gi sak e yi s s u ei nd a t am i n i n g i t d i s c o v e r sa n da n a l y s e st h ea s s o c i a t i o n sa m o n gd i f f e r e n ts e t so fd a t ai t e m s b yi n t r o d u c i n g t h ea s s o c i a t i o nr u l e sm i n i n gt e c h n o l o g yi n t ot h es a l e si n d u s t r yo ff u r n i t u r ea c c e s s o r y ，t h e c h a r a c t e r t i s t c sa n da s s o c i a t i o n so ft h es a l e ss t a t i c i t i c sc a nb eo b t a i n e d ，a n dt h ep o t e n t i a l p u r c h a s ec u s t o m e sa n dp u r c h a s en e e d sc a nb eg r a s p e di nv i e wt of o r m u l a t er e l e v a n ts a l e s s t r a t e g ya n dp r o c u r e m e n ts t r a t e g y t h i sp a p e ri n v e s t i g a t e st h ea p p l i c a t i o no fa s s o c i a t i o nr u l e sm i n i n gt e c h n o l o g yi nt h e f u m i t u r ea c c e s s o r ys a l e si n d u s t r y , a n dp r o b ei n t ot h ea s s o c i a t i o nr u l e st h r o u g hb r i e fa n a l y s i s a n da p p l i c a t i o nd e s i g n ，i nt h i sp a p e r , p r o j e c tb a c k g r o u n do fc u r r e n tm i n i n gi si n t r o d u c e d ， a n dt h ek e yi s s u e sa n ds i t u a t i o na th o m ea n da b r o a do fa s s o c i a t i o nr u l e sm i n i n gt e c h n o l o g y h a v e b e e ns p e c i f i e d f o l l o w i n gt h a tt h ek e yc o n c e p ta n dp r i n c i p l ei n v o l v e di nt h ea s s o c i a t i o n r u l e sm i n i n gt e c h n o l o g yw i l lb ei n t r o d u c e d ，e s p e c i a l l yt h eo v e r a l ld e s i g na n ds p e c i f i c a t i o n d e t a i l sr e g a r d i n gt h ed a t am i n i n gp r o c e d u r e l a t e ri nt h i sp a p e r ，t h e r ei st h er e q u i r e m e n t a n a l i s y s ，w h i c hp r o v i d e sd e t a i l so ft h es a l e s d a t ac h a r a c t e r t i s t i c s 、f u n c t i o nr e q u i r e m e n t , m e t h o d sr e q u i r e m e n t ，a n do t h e rr e q u i r e m e n t s f o l l o w i n gt h a ti st h es y s t e md e s i g no fc u r r e n t m i n i n g t h em i n i n gw i l lb es p e c i f i e d i nt e r m so fd a t ac i r c u l a t i o n ，p r o c e s sd e s i g na n d o p e r a t i o n ，t e c h n i c a l c o n s i d e r a t i o n , d a t a b a s et a b l ed e s i g n , a n de t c e x a m p l e sr e g a r d i n g c u r r e n tm i n i n gw i l lb ec i t e d i n t h ef o l l o w i n gd e t a i l e dd e s i g ns e s s i o n ，t h ec o d e i m p l e m e n t a t i o no ft h ec u r r e n tm i n i n gw i l lb ei n t r o d u c e d s p e c i f i c a l l y , m e t h o dp r o c e d u r eo f t h e3m a i nc l a s s u t i l i t y , r u l e a n dd b a d m i n - - - 淅l lb ei n t r o d u c e d i nt h el a s t ，t h ef i n a l r e s u l td e m o n s t r a t i o na n da n a l y s i sw i l lb ed i s p l a y e d t h ea s s o c i a t i o nr u l e sw i l lb eb r i e f l y c o n c l u d e da n dd e m o n s t r a t e d d e t a i l e da n a l y s i sa n da p p l i c a t i o nd e s i g nr e g a r d i n gt h e a s s o c i a t i o nr u l e sw i l lb ep r o v i d e d k e yw o r d s ：s a l e sd a t a so f t h ef u r n i t u r ea c c e s s o r yi n d u s t r y ；c a n d i d a t ea c c e s s o r ys e t ；f r e q u e n t a c c e s s o r y - s e t ；a s s o c i a t i o nr u l e s 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并 向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授 权西南交通大学可以将本论文的全部或部分内容编入有关数据库进行检索，可以采用 影印、缩印或扫描等复印手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密函使用本授权书。 ( 请在以上方框内打“、”) 学位论文作者签名： 陌噫 指导老师签名：力，狁双 u 日期：如扣年易月9 日 日期：2 0 蛑石月矽臼 西南交通大学硕士学位论文主要工作( 贡献) 声明 本人在学位论文中所做的主要工作或贡献如下： 第一，学习了关联挖掘的基本概念和理论，并对挖掘步骤的进行了深入的分析和 研究。 第二，投入大量精力熟悉、分析并整理家具配件销售行业的销售数据，尤其是颇 具行业特点的且数量比较大的家具配件名。 第三，根据学习所得的关联挖掘的理论和步骤分析的结果，用j a v a 语言开发一个 新的基于家具配件销售数据的关联挖掘的系统，并对获取的行业销售数据进行挖掘并 得到规则。在开发过程中，也会随着挖掘的进行，不断修改和完善挖掘步骤。 第四，对挖掘出的规则进行分析并得出一定结论，根据结论思考这些规则的应用。 第五，总结挖掘过程中用到的理论知识、遇到的问题以及思考的过程，为论文的 撰写奠定基础。 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作所得的成 果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰 写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中作了明确说明。 本人完全了解违反上述声明所引起的一切法律责任将由本人承担。 学位论文作者签名： i ， 污喙 日期：沙f p 年6 | q 矽e i 西南交通大学硕士研究生学位论文第1 页 1 1 项目背景 第1 章绪论 从数据量上说，近年来，随着计算机对数据的生成、收集、存储和处理能力的大 大提高，数据量与日俱增，传统的数据分析工具对海量数据的处理力不从心，因此， 数据挖掘技术逐渐被引入到数据处理中。数据挖掘技是随着计算机的广泛应用和数据 的大量积累快速发展起来的，旨在能从大型数据库中提取隐藏的有价值的信息，又称 知识发现i l ，2 ，引。关联挖掘技术是数据挖掘技术的一种，是用于挖掘大量数据项之间的 联系情况的。作为数据挖掘最先研究的问题之一，甚至可以说，提到数据挖掘，人们 首先想到的就是关联挖掘技术1 4 j 从市场需要的角度来说，随着市场竞争的不断加剧和技术水平的不断完善，现代 实体经济的主导因素已逐步从技术和价格转化为对市场和销售的分析以及相应策略的 制定。谁能够掌握市场和客户需求的特点，有效的保持和发掘客户，谁就能在激烈的 市场竞争中处于不败的境地。家具配件销售行业作为实体经济的一种，由于其具有非 高科技性行业、市场依赖程度高等特点，其经营业绩的好坏很大程度上都会受到对销 售的分析是否精细和准确的影响。作为一个销售行业，分析商品与商品间的销售联系 是最快捷、最直接、也是最有效的分析方式【5 j 。因此，将关联挖掘引入到家具配件销售 行业中，以科学的挖掘理论作为基础，准确地分析出商品间的销售关联，把握客户的 需求特点，才能为销售策略的制定缔造一个良好的条件基础，以便使企业的经营更好 地适应市场的发展。 家具配件销售行业也有它自身的一些独特的现象和问题。在家具配件销售行业中， 最常见的现象有：( 1 ) 将顾客所需商品送达后，才发现由于顾客订货时的遗忘或忽略， 少量必需货物未在订单中，为了满足顾客的需要，很可能需要马上再次运送，增加了 运输成本；( 2 ) 有些顾客在订货时虽然没有遗忘什么货物，但由于计划不够周详或存 货情况了解不清，可能忽略了某些货物的储备已不足以应付一定期限的生产，而当遇 到实际缺货时，需要的又比较急而且多，这种情况下，商家很可能因为临时货物不够 而无法及时运送，造成利润和信誉双方面的损失；( 3 ) 顾客采购商品往往比较倾向于 熟悉的组合方式，这种组合方式主要包括品牌和产品类型，也就是说顾客会比较习惯 于购买某些品牌的某些产品，而对其他即便是有需要的产品也会置若罔闻，久而久之 就会减少顾客对其他产品的关注程度，也就减少了商家获取更多利润的机会；( 4 ) 家 具配件销售商的进货往往不是即时性的，尤其是一些大的品牌，一般情况下，厂家每 年只会固定的提供两三次供货，所以每次厂家供货时，销售商们往往就要为购入哪些 种类的货物而费一番心思了，因为这需要商家对存货、销售和市场有一个综合的考虑。 关联规则是表示数据库中一组对象之间的某种关联关系的规n t 圳。掌握配件间的销 售关联规则，了解顾客的购买习惯和偏爱会对解决这些常见问题起到非常积极的作用。 西南交通大学硕士研究生学位论文第2 页 而对销售数据进行关联挖掘，是发现不同配件之间的销售关联规则的一种有效的手段。 实际上，这些规则不仅对解决行业常见问题有作用，对销售商的市场定位、配件定价， 新配件采购等决策问题都有非常重要的指导意义，更进一步，还可以利用这些规则进 行配件销售预测、配件价格分析、销售地点选择等。总之，配件间的销售关联规则确 实是值得花大力气去挖掘的。 1 2 关联挖掘应用的国内外现状 1 9 9 3 年，a g r a w a l 等人首次提出了挖掘顾客交易数据库中项集的关联规则的问题 【7 j ，其目的是为了发现交易数据库中不同商品之间的联系规则。这些规则刻画了顾客的 购买行为，可以用来指导商家科学地安排进货、库存以及货架设计等。关联规则挖掘 提出后，人们逐渐发现，它在交易数据库中的简单应用常常能起到意想不到的作用， 甚至极大地提高销售的业绩，所以人们对关联规则的挖掘进行了广泛而深入的研究。 在挖掘方向上，目前对关联挖掘的研究主要有以下几个方向p j ：( 1 ) 频繁关系在不 同数据对象，不同应用环境中的不同形式；( 2 ) 关联规则挖掘的效率，即提高挖掘的 速率和减少挖掘的存储空间需求；( 3 ) 如何在稠密的海量数据中进行关联规则挖掘；( 4 ) 如何挖掘有价值的关联规则；( 5 ) 如何利用关联规则。 在挖掘算法上，目前的挖掘算法大体可以分为两类：串行算法和并行算法 9 1 。串行 算包括经典的a p r i o r i 算法、采用动态h a s h 和剪枝策略的d h p 算法、采用分块挖掘的 p a r t i t i o n 算法、采用前缀树存储候选集的s e a r 和s p e a r 算法、采用分块和动态项目频 度计算的d i c 算法、采用抽样策略的s a m p l i n g 算法等。此外，z a k i 博士提出了四个 有影响的串行关联挖掘算法，分别是采用基于前缀的等价类技术和自底向上搜索策略 的e c l a t 算法、采用基于前缀的等价类技术和混合搜索策略的m a x e c l a t 算法、采用基 于团的等价类技术和自底向上搜索策略的c l i q u e 算法、采用基于团的等价类技术和混 合搜索策略的m a x c l i q u e 算法。并行算法大体上可以分为两个类别，一类是基于a p f i o f i 类的算法，主要包括各结点通过交换项目的局部支持度而获得全局支持度的c d 算法、 各结点通过交换数据而获得全局支持度的d d 算法和i d d 算法、以及结合了c d 和i d d 的基本思想的h d 算法等；另一类是基于d h p 、s e a r & s p e a r 、d i c 等的分布式关联规 则挖掘算法。此外，z a k i 博士提出了基于e c l a t 、m a x e c l a t 、c l i q u e 和m a x c l i q u e 的并 行算法p a r ( m a x ) e c l a t 、p a r ( m a x ) c l i q u e 。 在挖掘类型上，现行的关联挖掘主要有以下几种类型博1 ：( 1 ) 多层次关联规则挖掘， 这种挖掘的产生是由于很多规则是由多层次概念组成的；( 2 ) 多维关联规则挖掘，这 种挖掘的引入是因为很多规则是在多维数据库中挖掘的；( 3 ) 基于约束的关联规则挖 掘，这种挖掘的引入是因为在具体应用中，一些用户通常只对关联规则的子集感兴趣； ( 4 ) 定量关联规则挖掘，这种挖掘是为了应对有多个值的数值属性和类别属性的情况； ( 5 ) 周期关联规则挖掘，这种挖掘是为了应对一些有周期性特性的关联规则的；( 6 ) 加权关联规则挖掘，这种挖掘是为了解决当数据库中项目分布不均匀而出现频率相差 较大的现象，进而导致的最低支持度设置过高或过低的问题的；( 7 ) 负关联规则挖掘， 西南交通大学硕士研究生学位论文第3 页 这种挖掘的目的与常规挖掘有所不同，是为了挖掘那些顾客购买了某些商品，就可能 不会购买另一些商品的规则；( 8 ) 序列模式挖掘，这种挖掘最主要的特点是将分析和 产生规则的时间加了进去，力图发现在一定时间内共同出现的项目；( 9 ) 比例规则挖 掘，这种挖掘主要是针对项目间关联的，侧重于比例。 在应用行业上，关联规则的挖掘如今已经深入了包括商品零售行业、金融和保险 服务行业、科学研究领域、电信网络管理、医疗行业等一系列重要的经济领域中去， 并起到了举足轻重的作用。 1 3 本文研究的重点和关键问题 关联挖掘是一种非常重要的数据挖掘技术，主要用于分析数据项之间的联系，关 联挖掘虽然有着复杂而科学的数学理论基础，但由于理论本身需要有广义的意义以及 理论研究者不可能对每个具体行业都有足够的了解等原因，理论意义上的关联挖掘还 不能直接应用于各个实际的行业中去。本文的重点在于结合关联挖掘的基本理论，研 究关联挖掘技术在家具配件销售行业中的应用过程和细节，并对本次挖掘的结果进行 分析和应用设计。本文的挖掘结果对行业的客户分析和营销策略制定都会起到直接的 积极作用。本文中对挖掘过程的深入分析，能够为关联挖掘在各个行业的实际应用提 供一些实践经验并起到一定的借鉴作用。 在挖掘过程中，会碰到一系列挖掘细节和挖掘思想方面的问题：怎么做、什么时 候做、不同的做法会对结果产生什么样的影响、这些不同做法又各自体现了什么思想。 各种问题都需要随着挖掘的深入而进行仔细的分析和设计。从整体来看，挖掘过程中 的最关键的问题，也是本文研究的关键问题，就是如何将关联挖掘的基础理论与具有 鲜明行业特点的数据在各个步骤中组合在一起工作，以及如何分析和应用挖掘出的关 联规则。 1 4 本文章节安排 本文的篇章结构安排如下： 第1 章绪论，简述了本次关联挖掘的项目背景，关联挖掘应用的国内外现状以及 本文研究的重点和关键问题。 第2 章理论介绍，介绍了关联挖掘的一些基本概念， 用到的一些原理和方法。 第3 章需求分析，介绍了本次关联挖掘的各种需求。 第4 章概要设计，介绍了本次关联挖掘的总体步骤， 设计思想和相关数据库表的情况。 以及本次关联挖掘的过程和 然后详细介绍了各个步骤的 第5 章详细设计，详细说明了本次关联挖掘的各个步骤的代码流程情况。 第6 章结果展示和分析，有代表性的例举了本次关联挖掘的一些结果，并对这些记 过进行了简单的分析，根据这些结果和分析还设计了一些应用策略。 西南交通大学硕士研究生学位论文第4 页 第2 章理论介绍 本次关联挖掘会涉及到一些理论性较强的基本概念，包括二元表示、项集、支持 度计数等。结合挖掘过程，对这些概念做一简单的介绍有利于理解之后章节的对挖掘 过程的分析和讲解。本次关联挖掘的每个步骤都有一定基础理论来支撑，也有一些自 己的设计思想在里面。简要介绍一下这些基础理论，有利于从本质上理解这些步骤。 2 1 基本概念 在本次关联挖掘中，主要涉及到以下几个基本概念： 项与项集 事务与事务集 项集的支持度计数、项集的支持度 规则、规则的支持度计数、规则的支持度、规则的置信度 最小支持度计数阈值、最小支持度阈值、频繁项集 最小置信度阈值、关联规则 这几个概念是关联挖掘中常用的专业名词，在本次挖掘的分析中也会经常涉及到这些 概念，因此对它们进行一定的解释和说明是很有必要的。 ( 1 ) 项可以理解为属性，这个属性可以是某个名称，也可以是某种性质，只要是 能够组成集合的属性即可，由若干个项组成的集合即为项集，项集中项的个数称为项 集的长度，长度为k 的项集称为k 阶项集。 ( 2 ) 一个事务实际上就是一个项集。但这个项集不是一个随意的组合，而是有一 定意义或与某实际事件相符的项的组合。全体的事务就构成了事务数据库( 也称为事 务集) 。 ( 3 ) 项集的支持度计数是指在事务集内包含该项集的事务的数量n ，而项集的支 持度则是指该数量n 与事物集内所有事务的数量的比值。 ( 4 ) 假设x 和y 是两个不相交的项集，则形如x 专y 的式子就是一个规则，规 则x 称为前件项集，y 称为后件项集。假设前件项集与后件项集的并集是z ，所谓规 则的支持度计数是指项集z 的支持度计数，所谓规则的支持度是指项集z 的支持度。 规则的支持度计数与支持度其实就是项集的支持度计数与支持度的一种特例。所谓规 则的置信度，是指包含项集z 的事务的数量与包含项集x 的事务的数量的比值。 西南交通大学硕士研究生学位论文第5 页 ( 5 ) 最小支持度阈值是满足要求的支持度的最小值。而最小支持度计数阈值就是 在事务总数一定的情况下，支持度取“最小支持度阈值”时的支持度计数。支持度大 于等于最小支持度闽值的项集称为频繁项集，反之，称为非频繁项集。长度为k 的频 繁项集被称为k 阶频繁项集。一般来讲，为了简化计算( 乘法比除法方便) ，在实际操 作中我们会采用“比较最小支持度计数阈值和项集的支持度计数”的方法来确定频繁 项集【l0 | 。最小支持度计数阈值的计算公式如下： m i n s u p p o r t c o u n t = t r a n s c o u n t m i n s u p p o r t( 2 一1 ) 式中m i n i s u p p o r t c o u n t 一最小支持度计数阈值 t r a n s c o u n t 一事务数据表中的事务总数 m i n i s u p p o r t 喝t j 、支持度阈值 ( 6 ) 最小置信度阈值是也就是满足要求的置信度的最小值。关联规则是满足这样 两个条件的规则：一是它的支持度计数不小于最小支持度计数阈值，二是它的置信度 不小于最小置信度阈值。显然，第一个条件等价于“前件配集与后件配集的并集的支 持度计数不小于最小支持度计数阈值”，也就是说前件配集与后件配集的并集必须是频 繁项集。所以关联规则也可以这样来定义：从频繁项集中提取的，置信度不小于最小 置信度阈值的规则。注意，关联规则在一些资料中也被称为关联模式【1 1 1 。作为关联挖 掘的重要结果，只有很好的理解关联规则，才能去其糟粕，取其精华，充分发挥关联 规则的价值u 川。 这里就频繁项集与关联规则的关系做一个简要介绍。由规则支持度计数的定义和 关联规则的定义可知，关联规则的前件项集和后件项集的并集必然是频繁项集，由之 后即将介绍的先验原理还可以得出，前件项集和后件项集都必须是频繁项集。所以得 出结论：只有频繁项集才能组成关联规则，关联规则所涉及的项集必然都是频繁项集。 2 2 先验原理( 基于支持度的剪枝定理) 本文的关联挖掘用到了一个十分重要的原理先验原理。该原理是候选项集进 行剪枝( 即频繁项集的产生) 的一个重要理论基础【1 3 】。下面将对该原理做一简单介绍。 先验原理：如果一个项集是频繁的，则它的所有子集一定也是频繁的。 为了解释先验原理的基本思想，考虑图2 - 1 所示的项集格。已知 c ，d ，e ) 是频繁项 集。显然，如果一个事务包含项集 c ，d ，e ) ，则该事务一定包含它的子集 c ，d ) ， c ，e ) ， d ，e ) ， c ) ， d ) 和 e ) 。这样，如果 c ，d ，e ) 是频繁的，则它的所有子集( 图2 1 中的 阴影项集) 一定也是频繁的【1 4 】。 西南交通大学硕士研究生学位论文第6 页 图2 一l 先验原理的图不 相反，如果一个项集 a ，b 是非频繁的，则它的所有超集也一定非频繁的。如图2 2 项集格所示，一旦发现 a ，b ) 非频繁的，则整个包含 a ，b 超集的子图( 图2 2 中的阴影 项集) 可以被立即剪枝。这种基于支持度度量修剪指数搜索空间的策略称为基于支持 度的剪枝，这种剪枝策略依赖于支持度度量的一个关键性质，即一个项集的支持度决 不会超过它的子集的支持度引。这个性质也称支持度度量的反单调性。 图2 - 2 基于支持度的剪枝的图示。 西南交通大学硕士研究生学位论文第7 页 2 3 概念分层 在本次挖掘中，概念分层是在预处理阶段对家具配件销售数据进行调整和优化的 一个重要理论基础。是否采用概念分层处理销售数据，如何实施这种处理将会对挖掘 结果的优劣有极大的影响。下面简单介绍一下概念分层。 概念分层是定义在一个特定的域中的各种实体或概念的多层组织【14 | 。它是本次关 联挖掘中非常重要的一个概念，这个概念主要是用于在预处理阶段对销售数据的字段 进行扩展或收缩处理即处理概念分层。经过处理概念分层后，字段的组成会变得更加 合理，进而对之后的挖掘过程产生积极的影响。下面用一个简单的例子解释一下概念 分层的原理。例如，在超市购物分析中，概念分层具有如下形式：项的分类法描述了 商店销售的商品之间的“是一种”的关系。例如，牛奶是一种食品，而d v d 是一种电 子产品( 见图2 3 ) 。通常，概念分层根据领域知识，或者基于特定组织的标准分类方 案来定义。 图2 3 商品分类的例子 概念分层可以用有向无环图( d i r e c t e da c y c l i cg r a p h ) 表示，如图2 3 所示。如果 图2 3 存在一条从结点p 到另一个结点c 的边，则称p 是c 的父母，c 是p 的子 女。例如，牛奶是脱脂牛奶的父母，因为从结点牛奶到结点脱脂牛奶存在一条有向边。 在图2 3 中食品是脱脂牛奶的祖先，而a c 适配器是电子产品的后代。 将概念分层纳入关联挖掘的主要优点如下： 位于层次结构较低层的项可能没有足够的支持度，从而不在任何频繁项集中出 现。也就是说，由于数据的稀疏性，可能在底层的项之间很难找出关联规则i l5 | 。例如， 尽管a c 适配器和连接配件的销售量可能很低，但作为它们的父母结点，便携机配件 的销售量可能很高。不使用概念分层就可能丢失涉及便携式配件的有趣模式和规则。 在概念分层的较低层发现的规则倾向过于特殊，可能不如高层的规则令人感兴 趣。例如，诸如牛奶和面包等大宗商品趋向于产生许多底层规则，如，脱脂牛奶专普 通面包，脱脂牛奶专白面包。使用概念分层结构，它们可以汇总为一条规则：牛奶专 面包。仅考虑分层结构顶部的商品可能也不好，因为这样的规则可能没有任何实际应 西南交通大学硕士研究生学位论文第8 页 用价值。例如，尽管规则电子产品专食品可能满足支持度和置信度阈值，但是它 不提供什么信息，因为顾客经常一起购买电子产品和食品是已知的事实。如果牛奶和 电视才是经常同时销售的商品，则模式 食品，电子产品) 可能过分泛化了这种情况。 2 4 关联挖掘的过程简介 挖掘关联规则的一种原始方法是：计算每个可能规则的支持度和置信度。这种方 法的过高代价令人望而却步，因为可以从数据集提取的规则的数目达指数级。 提高关联规则挖掘算法性能的第一步是拆分支持度和置信度要求【16 1 。大多数关联 规则挖掘算法通常采用的一种策略是，将关联规则挖掘任务分解为如下两个子任务： i 、频繁项集产生：其目标是发现满足最小支持度阈值的所有项集，这些项集称 作频繁项集( f r e q u e n ti t e m s e t ) 。 i i 、规则的产生：其目标是从上一步发现的频繁项集中提取所有高置信度的规则， 这些规则称作关联规则。 本次关联规则挖掘的过程充分考虑了上述挖掘过程的子任务模式，根据行业数据 特点和自身的设计思想，将挖掘过程大体分为三个步骤：预处理、挖掘、后处理。预 处理阶段分为两个子过程：数据分析和数据处理；挖掘阶段也分为两个子过程：项集 挖掘和规则挖掘；而后处理阶段实际上就是规则精炼的过程。为了将结构清晰显示， 总体过程罗列如下： 预处理 数据分析 数据处理 挖掘 项集挖掘 规则挖掘 后处理( 即规则精炼) 2 5 候选项集的产生和剪枝的实现方法 项集挖掘过程其实就是候选项集的产生和剪枝的过程。这个过程是本次关联挖掘 过程中一个需要重点设计和分析的过程，其中候选项集的剪枝操作是以支持度作为裁 剪标准的，所以也可以称为基于支持度的剪枝。在这里，先介绍一下这个过程的基本 方法。根据关联挖掘的基本理论和人工的总结筛选，该过程大体有以下三类方法： 蛮力方法 f k 1 x f l 方法 f k 1 x f k i 方法 西南交通大学硕士研究生学位论文第9 页 这三类方法各有自己的优点和缺点，方法的重点和不同之处主要在于候选项集的 产生，而候选项集的剪枝则都是采用基于支持度的剪枝的方法。下面将从原理上简单 介绍这三类方法，本次挖掘就是选择其中的一类方法进行该步处理的。 ( 1 ) 蛮力方法 蛮力方法把所有的k 阶项集都看作可能的候选项集，然后使用候选剪枝除去不必 要的候选项集。第k 层产生的候选项集的数目为口，其中d 是项的总数。虽然候选 项集的产生是相当简单的，但是候选剪枝的开销极大，因为必须考察的项集数量太大。 设每一个候选项集所需的计算量为o ( k ) ，这种方法的总复杂度为 d ( 罗：，配! ) = o ( d 2 如1 ) 。图2 4 显示了“在已知候选项共有6 个( a 、b 、c 、d 、e 、f ) _ 2 1 一 的情况下，产生所有的3 阶候选项集，最后经过候选剪枝得到一个3 阶频繁项集 b ，d ，e ) 的整个过程。图中的3 阶候选项集的数量是随着候选项的数量的增长而成倍 数级增长的，如果候选项的数量比较多，则产生的3 阶候选项集的数量将是非常巨大 的( 其中相当一部分是不必要的候选项集) ，这样会极大地增加后续的候选剪枝的工作 量。一般来说，该方法算是性能比较差的，但在一些特殊情况下，使用这种笨拙的方 法反而能获取较好的性能。 候选产生 露t 捧集淘 a ，b ，c a ，b ，d a ，b ，e a ，b ，f a ，c ，d a ，c 。e a ，c ，f a ，d e a ，d ，f a ，e ，f b ，c d b ，c ，e b ，c ，f b ，d ，e b ，d ，f b ，e ，f c ，d ，e c ，d ，f c ，e ，f d ，e ，f 候选剪枝 隧蒌墓囵 空：璺! 竺 图2 - 4 产生3 阶候选项集的蛮力方法 ( 2 ) f k 1 f 1 方法 f k 1 f 】方法的思想是用其他频繁项来扩展每个( k 1 ) 阶频繁项集。图2 5 显示了 如何用频繁项( 如b ) 扩展频繁2 阶项集( 如 a ，d ) ) ，产生3 阶候选项集( 如 a ，d ，b ) ) 。 这种方法将产生o ( i f k i i i f l l ) 个k 阶候选项集，其中吲表示j 阶频繁项集的个数。 这种方法总复杂度是o ( ek k l f k 1 i i f l l ) 。 西南交通大学硕士研究生学位论文第1 0 页 2 阶频繁项集 频繁项 匿娶盈 a b d e 候选产生 匿湮囵 a ，d ，b a ，d ，e b ，d ，e b ，e ，a 候选剪枝 医鎏囵 垒! 璺! ! 图2 - 5 通过合并( 1 ( - 1 ) 阶频繁项集和1 阶频繁项集生成和剪枝k 阶候选项集 这种方法是完全的，因为每一个k 阶频繁项集从最开始来说都是由一个俅1 ) 阶 频繁项集和一个频繁项组成的。因此，所有的k 阶频繁项集是这种方法所产生的k 阶 候选项集的一部分。然而，这种方法很难避免重复地产生候选项集。例如，项集 b ，d ，e 不仅可以由合并项集 b ，d ) 和 e ) 得到，而且还可以由合并 b ，e ) 和 d ) 得到，或者 由合并 d ，e ) 和 b ) 得到。避免产生重复地候选项集的一种方法是确保每个频繁项 集中的项以字典序存储，每个( k 1 ) 阶频繁项集x 只用字典序比x 中所有的项都大 的频繁项进行扩展。例如，项集 b ，d 可以用项集 e 扩展，因为“e 在字典序下 比“b ”和“d ”都大。然而，不应当用 b ) 扩展 d ，e 或用 d ) 扩展 b ，e ) ，因为他 们违反了字典序条件。 尽管这种方法比蛮力方法有明显的改进，但是仍然产生大量不必要的候选。例如， 通过合并 a ，d ) 和 e 而得到的候选是不必要的，因为它的一个子集 a ，e 是非频 繁的。有几种启发式方法能够减少不必要的候选数量。例如，对于每一个幸免于剪枝 的k 阶候选项集，它的每一个项必须至少在k - 1 个( k 。1 ) 阶频繁项集中出现，否则， 该候选就是非频繁的。例如，对于候选项集 a ，d ，e 而言，只有当它的每一个项( 包 括“a ”) 都至少在两个2 阶频繁项集中出现时，它才是一个3 阶频繁项集。由于只有 一个2 阶频繁项集包含“a ”，因此所有包含“a ”的候选项集都是非频繁的。 ( 3 ) f k 1 f k 1 方法 在该方法中，候选项集产生过程是合并一对满足“前k 2 个项都相同”的仪1 ) 阶 频繁项集的过程。设a = a 1 ，a 2 ，a k 1 ) 和b = b 1 ，b 2 ，b k 1 ) 是一对( k 1 ) 阶频繁 项集，合并a 和b ，如果它们满足如下条件： f l i = b i ( i = 1 ，2 ，k - 2 ) 并且a k - 1 b k - i 在图2 - 6 中，频繁项集 b ，d ) 和 b ，e ) 合并，形成了3 阶候选项集 b ，d ，e ) 。 西南交通大学硕士研究生学位论文第11 页 算法不会合并项集 如d ) 和 d ，e ) ，因为它们的第一个项不相同。实际上，如果 a ，d ， e ) 是可行的候选，则它应当由 a ，d ) 和 a ，e ) 合并而得到。这个例子表明了候选项集 产生过程的完全性和使用字典序避免重复候选项集的优点。然而，由于每个k 阶候选 项集都由一对( k 1 ) 阶频繁项集合并而成，因此若想判定该候选项集是频繁项集，还 需要附加候选项集剪枝步骤来确保该候选项集的其余k - 2 个( k 1 ) 阶子集是频繁的。 2 阶频繁项集 隧霪魏顾祭蕊翥圈 a d b d b e d e 2 阶频繁项集 匿釉集润 a d b d b e d e 图2 6 通过合并一对1 ) 阶频繁项集生成和剪枝k 阶候选项集 2 6 关联规则的剪枝定理 在本次关联挖掘中，该定理是在关联规则产生和剪枝阶段，以置信度作为标准进 行剪枝操作( 也称为基于置信度的剪枝操作) 的一个重要理论基础【13 1 ，该定理也称为 基于置信度的剪枝定理。下面将简单介绍一下该定理的内容。 当比较由频繁项集y 产生的规则时，下面的定理对置信度度量成立： 定理：如果规则x 专y x 不满足置信度阈值，则形如x - - ) y x 的规则一 定也不满足置信度阈值，其中x 是x 的子集。 为了证明该定理，考虑如下两个规则x 专y - x 和x 专y x ，其中x 是x 的子集。这两个规则的置信度分别为 s u p p o r t c o u n t ( y ) s u p p o r t c o u n t ( x ) 和 s u p p o r t c o u n t ( y ) s u p p o r t c o u n t ( x ) 。由于x 是x 的子集，所以s u p p o r t c o u n t ( x ) s u p p o r t c o u n t ( x ) 。因此，前一个规则的置信度不可能大于后一个规则。 西南交通大学硕士研究生学位论文第12 页 第3 章需求分析 在本次挖掘中，客户提供了他们近一段时间的销售数据，为的就是获得准确的销 售关联规则，以便制定相应的销售和进货策略。图3 1 是介绍客户与关联挖掘系统之 间需求关系的用例图。本章将从销售数据的特点、功能需求、方法需求、其他需求四 个方面对本次关联挖掘的需求做出详细分析【1 7 】。 3 1 销售数据的特点 图3 1 本次关联挖掘的u m l 用例图 客户提供的家具配件销售数据是三元表示形式的，以一个自然周作为外层分隔条 件( 每个月分为四周，超出的几天算入第四周) ，以配件名作为内层分隔条件，包括单 价、数量，总价，利润等详细描述列，大体形式如表3 1 ： 表3 1 销售数据的形式 自然周 配件名 单价数量单位总价利润 计算机键盘架 木牙螺丝 2 0 0 8 年1 月第1 周 6 2 0 内六角 计算机键盘架 计算机键盘架滑道 ： 2 0 0 8 年1 月第2 周 木托 销售数据的内容是客户将其每周的实际销售情况录入规定好的格式的表中形成 的，每一列的内容代表一个销售字段的情况。表3 1 中阴影部分就是销售数据的内容 西南交通大学硕士研究生学位论文第13 页 部分。根据各个字段的特点，销售数据中大部分的数据内容都是数值型的，比如“单 价 字段、“数量 字段等，但也有一些其他类型的值，比如“配件名”字段、“单位” 字段等。 客户提供的销售数据在形式和内容上都比较复杂，这种相对复杂的数据形式和数 据内容，能够比较完整地体现出日常销售的情况，方便客户对销售情况进行深入地了 解和分析。为了某个特定的目的，客户可能需要对这些数据进行处理并获取结果，但 数据形式和内容的复杂肯定会使这些处理变得更复杂。可以想见，有一类操作的复杂 性是纯由于数据的复杂造成的，这类操作穿插于整个处理的过程中，但对处理过程和 结果都没有什么积极意义，只是单纯为了使复杂模糊的数据变得清晰，易于访问。从 根本上来说，这类不必要的操作复杂性是由于源数据的形式和内容不符合处理的要求。 本次挖掘中，客户提供的销售数据就存在着这样的问题。如果将销售数据直接作为源 数据使用，就会极大地增加关联挖掘过程中不必要的复杂性。所以在“预处理”过程 中，要考虑好如何对销售数据进行调整，才能在不改变原有意义的情况下更贴合关联 挖掘对源数据的要求，并尽量地简化数据的形式和内容。 3 2 功能需求 在市场竞争日益激烈的今天，家具配件销售商们会想尽一切方法来保持并增加其 销售利润。但传统的质量、价格、售后等方面的方法肯定已经为人烂熟于胸了，也就 是说单纯靠这些传统的方法已经很难对现有业绩有比较大的提高了。这个时候，谁能 够用科学的方法把握市场和客户的特点，谁就能够在竞争中占据主动，获取更高的利 润。 如图3 2 所示，客户将销售数据提供出来，并构建这个挖掘系统，直接目的就是 为了获取配件和配件间的销售关联关系，即客户想要知道：哪几种配件被一起购买的 几率比较大，购买了几种配件的背后是否隐藏着对其他配件的潜在需要，购买了的具 体是哪几种，潜在需要的又是哪几种等。从专业的角度来说，客户真正需要的是配件 的销售关联规则，也就是本次关联挖掘的直接结果。举一个例子，一个消费者购买了f 木 肖，扁衣托，1 4 寸r t 二节滑道，1 8 寸r t 二节滑道 ，实际上他还需要购买d t c 合页， 但由于一些主观或客观的原因，他可能将这个需求遗忘了。经过本次关联挖掘后，配 件销售商就拥有了 木肖，扁衣托，1 4 寸r t 二节滑道，1 8 寸r t 二节滑道) d t c 合 页 这个基于消费者消费习惯的关联规则，如果遇到上述情况，就可以提醒消费者是否 对d t c 合页配件有需要，这样既可以提高利润，一些情况下还可以极大地降低成本。 输入 处理输出 图3 2 本次关联挖掘i p o 图 西南交通大学硕士研究生学位论文第14 页 除了直接目的之外，客户还希望能给出一个针对挖掘出的关联规则的简要分析和 应用方案。挖掘结果的简要分析可以给客户几个分析方向上的基础性提示，这样他们 以后每次的对挖掘结果进行深入分析时就可以以这几个方向为基础拓展自己的分析方 向。而挖掘结