面向零售业的关联规则动态挖掘算法研究

1、面向零售业的关联规则动态挖掘算法研究南京航空航天大学硕士学位论文面向零售业的关联规则动态挖掘算法研究姓名：闫珍申请学位级别：硕士专业：计算机科学与技术指导教师：皮德常2010-12南京航空航天大学硕士学位论文随着条形码技术的发展和pos point of sells系统的普及，零售企业 中的日常交易数据被大量收集，这些数据背后蕴藏着巨大的商机。作为数据挖掘屮最活跃的研究方 法之一，关联规则挖掘技术已被应用到零售行业。然而，零售数据具有结构复杂、海量、随时 间动态更新的特性，传统的关联分析技术无法高效地处理这类数据。因此，迫切需要设计具有针 对性的数据挖掘算法用以分析零售数据。木文从复杂数据类型

2、的处理、模式的评估以及挖掘结 果的解释等问题出发，对交易数据的关联分析中亟待解决的问题进行了研究。本文主要工作如 下：1针对apriori算法能够有效处理含有较多短模式的稀疏数据集但运行效率不高的问题,在其设计框架的基础上引入新的数据结构存储频繁项集，提出了一种高维稀 疏数据频繁项集挖掘算法fihs。该算法只需扫描一次数据集，通过优化连接剪枝操作避免产 生非频繁的候选项集。理论分析和实验表明，fths用于高维稀疏数据集上具有挖掘速度快、存储 空间少等优点。2针对现有频繁项集挖掘算法不能完全解决数据集动态更新和挖掘 参数变化后项集的高效维护问题，提出了一种频繁项集快速更新算法swfluao该算法

3、引入滑动 时间窗口概念，在充分利用业已发现的频繁项集的基础上，尽量减少数据集的扫描次数和候选 项集的产生个数。实验结果表明，swfiua算法在提高更新效率的同时还具有简单、易于维护 的特点。3为了提高挖掘规则的有趣性，在传统的“支持度-置信度”框架中 引入兴趣度量consinc,提出了一种基于兴趣度的关联规则挖掘算法imar。该算法对生 成规则的形式进行了限制，对强关联规则的概念进行了重新定义，并将挖掘规则分为止强规则、 正弱规则和反规贝鸚同时为了更好的利用关联规则优化业务，提出了“竞争商品模型”和“利 润最大化销售模型”。在真实的交易数据集上的实验结果表明，imar算法和两个分析模型是 有效

4、的。关键词：零售业，频繁项集，关联规则，动态更新，兴趣度量面向零售业的关联规则动态挖掘算法研究abstractwith the development of barcode technology and the popularityof pos point of sells systems,tremendous business opportunities hold in daily transactions of theretail business. as one of the mostactive research methodabout data mining,association

5、rule miningtechnique has been applied to thefieldof retailing.however,the tradi ti onalefficiently handleassociation analysis algorithms cannotthese ret ail data for its fca tu res such as complex struc tu re, mass storage and dynamic update with thetime. therefore, it urgently needs to design a tar

6、geted data mining algorithms to analyze retail dataset.in thispaper,weresearch the processing ofanalyzing of mining resuits，thus solved the problems in transaction data. the main contributions ofthisdissertationareas follows:firstly,todealwiththeproblemthattheapriorialgorithmcanhandle sparseitcmsctw

7、hichcontain huge short models but runtime is not efficiency, a frequent itemsets mining algorithm basedon high-dimensional sparse dataset named f1hs is proposed and meantime derive a new structure tostore frequent itemsets based on apriori algorithm. fihs only scan the dataset once and can avoi dgen

8、erating infrequent candidate itemsets through optimizing the opcration of conncction and pruning.according to theoretical analysis and experiments, fihs algorithm enjoys many advantages aiming athigh-dimensional sparse dataset, such as quick mining, less memory space, etc.secondly, to solve the prob

9、lem of efficiently mainlenance frequent itemsets wh i1e the datadynamically update and the parameters have changed, a quick update algorithm named swfiua isproposed. the algorithm uses the concept of sliding time window to minimize the times of scanningdataset and reduce the numberofcam didatcitemse

10、t.experimentalresults show that, swfiuaalgorithm improve the efficiency and also is simple, easy to maintain>thirdly, the intorestingness measure of consinc is introduccdto improve the interest of miningrules based onthetraditionalframework ofsupport-conf idenee.the n, mining algorithm imarbased

11、on theassociationrules ofinterestingnessmeasuresisproposed.the algorithm limits theformatof thegeneratedrules,redefinestheconceptionof strongrule anddivides the rules intopositive strong rules,positive weak rules and anti-rules- atthe same time, to make better use ofassociation rules to optimize bus

12、iness,“competitems model” and"profit model” are proposed.experiments show that imar algorithm andthe two models are valid inreal transaction dataset.key words: retai ling,frequent itemset, association rule, dynamicupdate, intcrcstingncss measureii南京航空航天大学硕士学位论文图表清图11零售数据分析 系 统框架6图 2. 1搜索空间的有向图表

13、刀、 10图2.2数据集d的垂直数据表示和水平数据表示11图 2.3兴 趣 度 量 的 方法图2.4兴趣度计算在数据挖掘过程中的作用16图 2.5对 m 进行矩阵转置操作17图 2.6对 m 进行行列缩放操作17图 2.7对 m 进行列转换操作18图 2.8对 m 所有变量取反操作作图2.9对m 进.18行元素加法操图3. 1算法在t10i4d100k上的执行效率比较28图3.2算法在retail上的执行效率比较.28图3.3算法在mushroom上的执行效率比28图4. 1原始窗口数据集和更新窗口数据集.图324.2窗口数据集图4.3扫描p、p 、p记录2项集信息38123图4.4扫描pl、

14、 p 4 更新 2 项集信息39图4.5算法在 t10-i4-d100-d5上的执行效率比较40图4.6算法在 ms 0. 1%时的执行效率比较40图 5. 1竞 争 商 品 模 型competlterns 图 5.2利润最大化销售模型profit 51表 2.1关于规则前后件的概率分布16表 2.2关联规则的兴趣度度里19表 3. 1 apriori、fp-growth、partition 和 declat 算法的 特征描述21表 3.2 apriori > fp-growth、partition 和 declat 算法的性能分析22表 3.3交易记录 ti二进制数关系表3.41频繁项

15、集fi 124表3. 52频繁项集ft 225v面向零售业的关联规则动态挖掘算法研究表3.6数 据 集 属 性 对比28表4. 1挖掘参数符号对照表表 4.2算法 swf 和 swfiua 运行结果比39表5. 11000 个 顾 客 的 购 买 选择41表 5.238 兴趣度量指标的属性取值43表 5.3交易集中所有可能的关联规44表 5.4引入兴趣度指标的关联规则分类表 5.5 imar算法在不同参数设置下的运行结果比 52表 5.6 imar 算法挖掘出的-部分则52表 5.7 imar 算法挖掘出的部分则52vt南京航空航天大学硕上学位论文注释表美国计算acmassociation f

16、or computing machinery机学会ieeethe institute of electrical and electronics engineers 美国电气与电子工程师学会vldbvery large dateibase超大型数据库kddknowledge discovery in database数据库屮知识发现dmkddata mining and knowledge discovery数据挖掘和知识发现bibusiness intelligence商业智能bfsbreadth-first search广度优先搜索dfsdepth-first search深度优先搜索i/

17、oin / out输入/输出fifrequent itemset频繁项集arassociation rule关联规则simsubjective interestingness measure主观兴趣度量oimobjective interestingness measure客观兴趣度量msminimum support度最小支持mcminimum confidence最小置信miminimum intcrest度最小兴趣承诺书木人声明所呈交的博士学位论文是木人在导师指导下进行的研究工作及取得的研究成果。除了文中特别加以标注和致谢的地方外，论文屮不包含其他人已经发表或撰写过的研究成果，也不包含为

18、获得南京航空航天大学或其他教育机构的学位或证书而使用过的材料。本人授权南京航空航天大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。（保密的学位论文在解密后适用本承诺书）作者签名:日 期:南京航空航天大学硕上学位论文第一章绪论随着计算机科学的快速发展，多个行业都纷纷引入了信息化技术，这使 得人与人之间交流变容易的同时也形成了企业间的相互竞争态势。一方而，由于数据库管理技 术和数据采集技术的飞速发展，各个领域都收集了海量数据。研究表明，全世界的信息量每 20个月就会翻倍，在这些庞大的数据系统里可能包含着指导企业管理者进行决策分析的丰富

19、知 识。另一方面，随着1一个企业或行业业务数据的不断积累，现有信息系统屮的分析工具己无法适 应新的商业需求。因为无论是数据查询、业务统计还是报表制作，其处理方式都只是针对数据 集进行简单的数字表面分析，这种处理方式不仅存在着分析效率低和分析实时性差等问题，而 且不能对数据屮隐含的、有价值的知识进行有效提取。在这种情况下，人们对能够从大型数据 集中发现潜在知识的“工具”的需求越来越迫切。在强大的商业需求的驱动下，商家开始注意 海量数据中蕴含的巨大商机，学者也开始思考可以从大容量数据中提取有用知识的理论和方 法。因此,20世纪80年代后期，数据仓库和数据挖掘等信息处理的理论和方法应运而生。1.1数

20、据挖掘的研究概述数据挖掘data mining, dm可以从随机的、多种存储形式的、不确定的、模糊的、大型数据集中提取或“挖掘”隐藏的、不为人所知的、对管理者决策分析有价值的 知识。数据挖掘是数据仓库技术、统计方法、人工智能、数学分析以及模糊计算等众多学科交 叉发展而形成的新兴学科2。按照挖掘任务不同，可以将数据挖掘分为分类分析、聚类分析、 关联分析、序列分析、孤立点分析、偏差分析以及依赖关系分析等几大任务。数据挖掘技术的发展与现状1989年，第-届国际人工智能artificial intelligence, ai会议 上首次提岀了数据库屮知识发现kdd的概念3 o 1995年，数据挖掘dm这

21、一-术语在第一届数据挖 掘与知识发现dmkd国际学术会议fc95上被正式提出，该会议由1989年、1991年、1993年以 及1994年举行的四次kdd国际研讨会演变而来。1998年，美国计算机学会acm成立了一个新的 学术组织，即数据库中的知识发现与数据挖掘专业组 acm-sigkdd special interest group on knowledgediscovery and data mining 。1999 年，acm 数据管理专业委员会 sigmod special interest groupon management of data发起了第五届知识发现与数据挖掘国际学术会议

22、kdd'99。另外，该领域还有一些其他学术会议，如亚太平洋地区年会一一pakdd、欧洲地区会 议一一pkdd、数据仓库与知识发现国际会议一一dawak等2。现有的数据挖掘相关的国际期 刊主要包括vidb而向零售业的关联规则动态挖掘算法研究journal、knowledge and infonnation systems、informeition systems、transactions on knowledge anddata engineering tkde 、 ieee sigkdd explorations 和 intelligentdata analysis 等4。随着越来越多

23、的顶级国际会议和期刊的出现，数据挖掘理论和技术的研究已经引起了国内外学术界的广泛关注，逐渐成为了计算机领域的一个热门课题。1相对于国外，国内在数据挖掘与知识发现技术方面的研究起步较晚且没有形成整体力量。随着国家自然科学基金在1993年对数据挖掘研究项目的首次支持，国内的 多所高等院校展开了关于dmkd理论、方法及其应用等多方而的研究。这些单位主要包括复旦大 学、中国科技大学、浙江大学、东南大学和哈尔滨工业大学等。其中复旦大学的朱扬勇和施伯乐 教授开展了规则兴趣度量方面的研究56,取得了不错的成果；浙江大学、中国科技大学 等高校的专家针对关联分析算法的改进和优化等方面展开了研究；东南大学的孙志挥

24、教授领导的课 题组在关联规则挖掘21 23 26 32和聚类分析等研究方向发表了大量的论文，宋爱波教授 提岀了一个带约束的关联规1则挖掘算法模型；2000年，哈尔滨工业大学的刘挺教授创立了信息检索研 究中心hit-cir ,该研究中心分为语言分析、语言生产、文本检索和文本挖掘四个研究方向,fl前在国内外知名学报上已发表多篇学术论文，在该领域做出了一定的贡献。随着数据挖掘概念在学术界的影响越来越大，数据挖掘的研究也逐渐深 入到更实际的应用方面并开发出了许多成功的产品，得到了业界的广泛关注。目前，多家高校 和公司开发出的代表性数据挖掘平台主要有：kansas大学开发的lers、regina大学开发

25、的 kdd-r 、 simonfraser大学开发的dbminer、waikato大学开发的weka以及ibm公司开发的 intelligent miner2 系统、spss公司开发的数据挖掘工具箱clementine oracle公司开发的oracle data mining odm、sas 公司开发的sas em enterprise miner系统、中国科学院计算技术研究所的msminer 等。经过十几年的研究和实践，数据挖掘领域形成了多个独立的研究分支并 取得了丰硕的成果。人们已经认识到利用数据挖掘技术能从海量数据中提取潜在的科学知识及 其蕴含的商业价值，从中获取的信息可以及时指导管理

26、者进行决策分析。目前，数据挖掘的部分 成果已经被广泛地应用于市场营销、购物篮分析basket analysis 欺诈甄别、金融投资和 客户管理等领域3。随着数据挖掘技术在更多的应用领域产生不错的经济效益和社会效益，将更人 程度地激发商家和学者对数据挖掘技术的研究热情，进一步推动数据挖掘理论和方法的发展。数据挖掘应用领域任何技术的产牛和发展都是有其商业背景的，是为了处理某些亟待解决的问题而提出的,是社会进步的必然结果。作为一个新兴的研究学科，数据挖掘技术已经运用到了许多领域。尽4管某些应用可能还处在初级阶段，但它们已经反映了数据挖掘技术的发展趋势。122 南京航空航天大学硕士学位论文1. 金融业

27、方面大部分银行和金融机构提供了丰富多样的信用卡服务、投资服务、保险服务和股票交易服务等业务。金融机构收集到的数据相对完整、可靠，冃前，将数据挖掘技术 用于对这些高质量的数据进行系统化分析已经取得了较好的经济效益和社会效益。例如，在进 行投资服务前，可以对客户的收入水平、偿述与收入比率以及受教育程度等信息进行贷款偿还 预测和客户信用的评估分析，对信誉度不同的客户制定不同的贷款发放政策，尽量降低银行的 贷款风险；在对新客户定制服务前，可以利用分类和聚类技术分析客户的信息并将其归类到合 适的客户群；为了甄别诈骗行为，可以利用异常检测技术发现客户恶意透支、洗黑钱等其他金 融犯罪活动。2. 零售业方面商

28、家在口常交易的过程屮收集了关于商品退订、顾客购买记录、客户资料等方面的海量数据，并且随着电子商务的日益方便和流行，商家获取的交易数据量也在迅速 膨胀。零售业是数据挖掘技术的主要应用领域之一，例如，对商品、顾客、时间以及利润等方 面的信息建立多维数据立方体，运用关联分析技术基于该立方体从多个角度分析交易数据，可 以发现顾客的购买模式以及商品的销售趋势，商家可以依据这些信息采取有效的促销策略达到 利润最大化的目的；采用序列模式挖掘技术分析顾客的会员卡信息，可以获取客户的消费喜好和 信誉变化，据此不仅可以对顾客进行定时的组合商品促销活动，还可以用于顾客的忠诚度分 析。3. 电信业方面电信业己经迅速地

29、从单纯地提供通话服务发展为提供综合电信服务，如图像、e-diq订、web数据传输以及其他数据通信服务2。随着电信、因特网以及各种通信手段 与计算工具的融合，电信行业收集了大量的通信数据。数据挖掘技术在电信行业也得到了广泛的 应用，例如，通过分析电信网络运行中截获的告警数据可以发现有助于故障定位和故障预测 的信息，用以高效地管理电信网络；通过分析客户群的消费特点可以帮助企业更好地利用资源以 便制定合理的收费、服务标准和具有针对性的优惠政策，提高服务质量的同时还可以预防费用欺 诈行为等。4. 生物学方面近年来，数据挖掘技术开始应用到尖端的牛物科学硏究中。随着基因组学、蛋口质组学和生物医学研究的迅猛

30、发展，生物学数据挖掘已经成为新兴生物信息学研究领 域中不可或缺的一部分3 o数据挖掘在生物学上的研究主要集中在基因工程方而，例如，通 过对dna序列的分析可以发现疑难杂症所蕴含的基因排列信息，为人类征服顽疾提供新的解决方 案；利用分类、聚类和关联分析技术，通过对牛物体的dna信息进行清洗和归类可以发现目标 样本屮同时出现的基因串，有助于研究基因组群间的交互作用和相关联系。5. 入侵检测方面随着网络上需要进行存储和处理的敏感信息日益增多，安全问题逐渐成为计算机网络和体而向零售业的关联规则动态挖掘算法研究4系结构中需要解决的首要问题。为了发现任何威胁网络资源的安全性、机 密性或可用性的行为，可以运

31、用分类分析或关联分析技术首先从大量网络信息中发现用户的行 为特征，然后再根据这些特征行为建立安全事件的分类模型同时提取数据系统属性间的相关 联系，从而发现网络中的异常访问模式和潜在入侵行为。数据挖掘技术具有智能性，在该项技术 的基础上选用自动的方法建立一套具备良好扩展性的自适应入侵检测系统4,可以解决传统 入侵检测系统适应性和概括性差的问题，从而减轻了人工监测的工作量、提高了异常检测精确度 和响应速度。6. 其他科技应用方而数据收集和存储技术的进步使得以更快的速度和更低的代价获取海量 复杂的信息变得极为简单，大量数据的枳累导致科学应用不再是“假设一检验”方式，而是转向 “获取并存储数据-挖掘新

32、假设一通过数据或实验证实”的过程。这种转变推动了数据挖掘技 术在科研领域的应用发展，也给信息量极为庞大的制造业、天文、更疗等领域的研究带来了新 的挑战。1.2选题依据及研究意义如何将数据挖掘技术合理应用在零售业数据分析中是商家十分重视的 问题，相关领域也已经提出了一些理论和方法。零售企业的数据仓库中积累了海量的日常交易记 录，其屮包括店铺前端设备如扫描仪、pos机等采集到的销售数据以及统计人员收集的库存 数据、退订货数据和物流数据等1 o然而，现有的数据挖掘技术主要用于处理简单的、结构化 的数据集，交易数据的结构复杂性使得传统数据挖掘技术不再适用于对其进行分析。因此，设计 高效可行的数据挖掘算

33、法从海量的零售数据中提取有用的知识己迫在眉睫并具有现实意义。零 售领域的数据挖掘技术研究不仅是专家学者的兴趣所在，还受到了企业和政府部门的密切关 注，其研究进展将不仅促进计算机科学技术的进步，还对其它学科甚至生产力产生重要的影响。选题依据数据挖掘之所以能够引起专家学者的研究兴趣和企业厂家的广泛关注，主要是因为商家已经注意到海量数据中蕴含着的巨大商机4 o在过去的几十年里，信息化在 零售企业做大做强的过程中起着至关重要的作用。从数据中挖掘隐含知识、发现有用信息、获取 决策依据是信息化对商家的直接贡献也是数据挖掘技术价值的重要体现。与国外相比，国内的 零售数据挖掘工作还处于探索阶段，许多零售企业收

34、集的交易信息都没有被充分利用，这些信 息原本可以帮助商家创造更大的商业价值却被企业忽略了。这样一来，信息化的价值没有完全 显现且信息化的建设推动零售企业的发展也没有想彖屮完美。在这种情况下，对交易数据的充 分利用引起了商家的高度关注，越来越多的学者开始注重将数据挖掘技术运用在零售领域中。面对销售市场规模的不断扩大，商品种类和交易量的口益庞大，以获得最大销售利润为目的商家都在考虑如下问题：销售什么样的产品才能满足顾客的需求？采用什 么样的销售策略才4南京航空航天大学硕士学位论文能产生更大的利润？如何摆放商品才能达到促销的冃的？数据挖掘中的关 联规则分析技术可以帮助商家解决上述问题。pos系统的广

35、泛应用使得客户的购买记录可以完全 自动化地以电子数据的形式存储在数据仓库中，这些交易记录主要包括消费时间、地点、金额 以及购买商品名称、数量，以这些数据为主，同吋结合网站日志、客服记录和其他电子商务数据 进行关联规则智能分析可以发现商品间的相关性、商品销售的趋势以及顾客的购买行为模式等 有价值的信息。这些信息是商家在市场定位、商品定价、商品采购问题上的决策依据，在帮助 企业管理者合理地设计商品摆放、安排促销活动、控制销存比例上具有重要意义。也就是说， 运用关联分析技术发现零售数据中的隐含知识，有助于商家准确及时地把握销售过程中各种影 响因素的总体特征和发展趋势，从而有效地改善了企业的运营状况并

36、提高了白身的竞争力。因此，将关联规则挖掘技术应用到零售领域中，建立基于关联分析的零 售业管理系统并将从海量数据屮挖掘出的有价值信息运用在业务优化和企业管理上，是有必要 深入研究的课题。研究目的和意义从海量交易记录屮发现有趣的规则可以帮助商家制定决策，零售数据中蕴含大量有价值信息，使得更多专家学者和商业人士越发意识到从海量交易数据中发现知识的 重要性。在对交易数据关联分析时，需要考虑三个关键的问题：首先，如何降低从庞大数据集 屮发现知识所付出的计算代价；其次，如何确保挖掘规则令用户感兴趣；最后，如何帮助商家 运用规则优化业务。为了利用关联规则挖掘技术高效地分析处理零售数据，必须了解其数据 结构的

37、特点。正是由于零售企业的交易数据具有以下四个性质，使得传统的关联分析方法已不 能高效的从中提取知识，因而必须设计针对交易数据集固有特点的算法进行数据挖掘。1流数据：交易行为发生的同时交易信息也在产生，销售数据记录会 不断的更新；2数据维数高：一条交易记录通常含有数十甚至上百个数据项;3数据量极大：像wai. mart这样的超市每天都会产生将近2亿条交易记录;4数据项稀疏：一个大型超市的商品种类一般会有上万甚至更多种， 但是顾客的一次购买行为最多包含上百个，相对于总的商品种类来说顾客的购买项是稀疏的。关联规则挖掘的任务是发现潜藏的事件间的依赖或关联，这些关联是事 先不可知的，是需要通过数据分析获

38、取的。关联分析的最终结果是以规则的形式呈现岀来的， 这些规则在挖掘过程屮经过了阈值的筛选和过滤。然而，现有的关联分析算法不仅需要耗费很 长的时间生成规则，而且产生规则的实用性和有趣性并没有达到预期的效果，有些规则甚至是虚 假的、对用户毫无意义的。在以往的研究中，专家学者针对这些问题提出了很多解决方案，如引入匹配度、影响度、相关度等指标评价规则的价值，但根据这些度量标准得出的结论均具有 一定局限性，很难比较哪种指标最好。因此，寻找一种适用于零售领域关联分析的度量准则是 亟需解决的难题。5面向零售业的关联规则动态挖掘算法研究零售领域的关联规则直观的解释是购买规则前件时很有可能引起连同 对规则后件的

39、购买，然而，企业管理者进行决策时不是仅仅考察规则前后件的相关程度，还需要 考虑商品的功效以及商品带来的利润等多种因素。过去数据挖掘对这方面的硏究并不多，传统 的关联分析技术仅能反映商品间的相关性，没能考虑到商品的利润带给商家的彫响。为了使得 挖掘出的规则更具有实际意义，可以在关联规则挖掘的过程中引入商家感兴趣的元素，同时建 立模型对规则进行分类分析并给出合理解释。这样就解决了用户不知道如何利用规则优化业务 的问题，真正做到管理者可以根据挖掘结果直接获取决策信息，更好的实现商业智能 business intelligence， bi 。因此，针对零售业数据的固有特点同时结合商家关注知识的角度，合

40、理 地将关联规则分析技术应用在零售交易数据集屮，用以发现有价值的知识并将其作为管理者进 行决策时的参考信息，使得企业利润最大化且具有更强的竞争优势，这将会是一项有重耍意义 并富有挑战的工作。1. 3本文的主要工作和组织结构木文针对数据挖掘技术的发展现状，全面分析了现有的国内外数据挖掘 理论和方法。在针对零售企业交易数据的关联规则分析方面，重点研究了高效的、可伸缩的、 实用的数据挖掘技术。从提高算法的计算速度、减少算法运行所需的存储空间、动态的零售数 据和多变的分析角度对挖掘结果带来的影响、关联规则的有趣性等研究难点出发，着重在设计 高效的频繁项集挖掘算法、快速更新维护算法以及引入兴趣度量的关联

41、规则生成算法等方面做 了相关研究。论文研究的零售数据分析系统框架如图1.1所示。整个系统框架分为五 大部分：数据预处理、频繁项集的牛成、频繁项集的动态更新、关联规则的挖掘和销售模型的分析。交易数据数据预处理数据频繁项集生成更新频繁项集更新关联规则挖掘引入“兴趣度”销售模型分析分析结果图1.1零售数据分析系统框架南京航空航天大学硕士学位论文围绕上述数据分析系统框架中的各个模块，本文分六章展开研究:第一章首先介绍了数据挖掘的发展与现状，分析了数据挖掘技术的应用 领域。然后说明了本文的选题依据，研究目的、内容、意义以及文章的组织结构。第二章首先给出了关联规则挖掘技术的基本概念，并将其分解为项集的 生

42、成和规则的发现两个任务，然后针对不同的任务对国内外现有的代表性频繁项集生成算法、 更新维护算法进行分类分析并介绍了兴趣度的相关知识。这些研究内容为后续各个章节的工作 打下基础。第三章首先分析了现有的代表性频繁项集挖掘算法的设计原理，从中得 出了高效的挖掘算法应具备的几点特征，总结出改进算法的设计思想，然后提出了一种针对零 售数据特点的高维稀疏数据频繁项集挖掘算法fihs o fihs算法中引入了新的数据结构存储频 繁项集，利用该结构不仅可以降低算法运行时的内存占有量，还可以避免冗余候选项集的产生。 理论分析和实验结果表明，f1hs运用在高维稀疏数据集上具有挖掘速度快，占用空间少等优 点。第四章

43、首先分析了现有的大多数频繁项集牛成算法没有考虑到数据集 更新以及参数改变时的动态维护问题，为了更好地解决这个问题，提出了-种基于滑动窗口的频 繁项集快速更新算法swfiua。该算法屮运用的滑动时间窗口机制不仅符合交易数据的更新特 点，还可以处理多种更新维护问题。swf1ua算法充分地利用了业己发现的频繁项集，有效地 减少了候选项集的产生数目和数据集的扫描次数，在更新效率有所提高的基础上还具有简单且易于维护的特点。第五章首先从现有的38种兴趣度量屮筛选出适用于零售数据关联分析 的兴趣度量consinc,并对生成规则的形式进行了限制、对强规则的概念进行了重新定义、对挖掘 规则进行了分类。然后提出了

44、一种基于兴趣度的关联规则挖掘算法imar ,为了使得发现的规 则更具有实际应用价值，该算法在“支持度-置信度”框架的基础上引入了兴趣度的概念。最 后为了更好地对挖掘规则进行解释，设计了竞争商品模型和利润最大化销售模型。实验结果表明, imar算法挖掘岀的规则经销售模型分析后，不仅能够找出令商家感兴趣的或者可以给企业 带来最大利润的商品组合，还可以用于安排商品的货架摆放。第六章是全文的总结。重点概括了本文在零售业关联规则挖掘方而所做 的工作，说明了所做研究存在的不足之处，同时也结合论文指出了可以在本文基础上进行改善 和拓展的部分。7面向零售业的关联规则动态挖掘算法研究第二章关联规则挖掘技术关联规

45、则associationrule, ar挖掘技术可以从大型的数据集dataset中提取项目间的有趣关系，它是一个先从数据集中发现频繁出现的项目集，再利用这些频繁项 集建立关联关系的过程。关联规则分析是数据挖掘领域中的一项重要任务，最早由agrawal等 人为了解决购物篮分析问题于1994年提出7。本章主要介绍了关联规则的基本概念以及国 内外的研究现状，为后续工作的开展奠定基础。2. 1节介绍了关联规则挖掘的有关性质和定义,2. 2 节分析了几种代表性的频繁项集生成算法，2. 3节介绍了更新维护问题的分类以及相关算法的 研究现状，2.4节概述了兴趣度量准则以及38种度量方法，2.5节为木章小结。

46、2.1关联规则挖掘的定义为了方便理解，我们首先给岀交易数据库又称事务数据库 中的关联 规则挖掘的一些基木概念，具体描述如下：定义2.1设i i,i,，i,，i 是一个项集，其中i jl,2,m 表示一个项又称项目，多个项目item构成的集合简称项集itemset 。设交易数据库d t,t,t,t是由一系列具有唯1 2j, n一标识tid的记录 事务 组成，每条记录tj j 1, 2,n对应项集i上的 一个子集。如果一个项集由k个项目构成，那么该项集就称为k项集。空集是指不包含任何项目的集合。定义2. 2设?t,项集i在数据集0上的支持度support是指包 含1的记录在整个交易数据1 11集中

47、所占的百分比，即ti | ti ed, il ?ti |，其屮isupport i2. 1定义2. 3对于给定项集t和交易数据库d ,d中所有满足用户指定的 最小支持度minimumsupport, ms阈值的项集，即项集i的非空子集屮支持度大于或等于ms的 项集，称为频繁项集frequent itemset, fl或者大项目集large itemset ,长度为k的频繁 项集的集合记做lk o在所有的频繁项集里挑选岀不被其他项集包含在其中的频繁项集称之为最大频繁 项集imumfrequent itemset或最大大项集imum large itemset 。待计算支持度的 项集通常称为候选项

48、集candidate itemset ，长度为k的候选项集的集合记做ck。i的关联规的记录数之比,定义2. 4 个定义在项集i和交易数据集d上形如i则的置信度confidence是指数据集中同时包含项集i和i的记录数与包含项集i即1 2 1support t1 u1ii, 12 ?i, il ni2 ?o2.2confidence t ftsupport i其中i 为规则前件antecedent iteinset , i 为规则后件consequentitemset 。1 28南京航空航天大学硕士学位论文定义2. 5从交易数据集d屮发现的在项集i上满足最小支持度和最小 置信度阈值minimum

49、confidence, mc 的规则称为强关联规则 strong association rule 。一 般地，从数据集中挖掘的规则是指强关联规则。对于给定的数据集和项集，关联规则挖掘就是根据用 户指定的最小支持度和置信度阈值提取全部强规则的过程，整个关联规则挖掘过程可以分解为 如下两个子过程:1发现频繁项集首先根据定义2. 2计算每个项集的支持度support,然后依据用户给定 的最小支持度阈值ms ,生成满足support 2 ms的所有频繁项集。发现所有的频繁项集为关联规 则的产生奠定了基础。2产生关联规则首先根据定义2.4计算出由每一个频繁项集组合成的规则的置信度 confidence

50、,然后依据用户给定的最小置信度阈值mc ,保留满足confidence 2 mc的关联规则。2. 2频繁项集生成算法分析关联规则挖掘任务可以分为发现频繁项集和产生关联规则两个子任务， 前者产生的计算代价远远大于后者。频繁项集的生成工作是关联规则挖掘算法设计的核心部 分，该部分工作是否高效直接影响整个算法的执行效率。关联规则的牛成工作只是根据牛成的频 繁项集创建相应规则的枚举过程，不需要太多复杂计算且该步骤在内存占用、i/o开销以及算 法效率上改进余地不大。因此，找到能够高效的完成任务一的方法是近年来关联规则挖掘算法的 研究重点，大多的算法设计问题都是围绕如何高效的发现频繁项集展开的。相关工作根

51、据算法的特性不同，可以将现己提出的频繁项集挖掘算法分为候选集 -计数类算法和模式增长类算法。hipp等人8于2000年提出了根据算法的搜索方式和计数方 式对频繁项集挖掘算法分类的方法，分类时涉及的计数方式和搜索方式的思想起源于候选集-计数 类算法，后来也逐渐将该思想引入到模式增长类算法中。算法遍历候选项集的搜索方式可以分为 广度优先搜索breadth-first search, bfs 和深度优先搜索 depth-first search, dfs 两 种，统计候选项集支持度的计数方式可以分为直接计数counting和交叉计数intersecting两 种8 o bfs类方法发展较早，研究相对

52、成熟，该类方法屮采用的循环迭代和逐步查找机制更符合人们 解决问题的直观思路。dfs类方法是后期发展的，该类方法通过引入复杂的数据结构和理论概 念来提高算法的运行效率。算法设计时选用的计数方式和搜索方式是决定算法效率及其适用范 围的重要因素，而算法实现时使用的存储结构以及检索技术是用来辅助核心工作完成的。为了更好地解释hipp提出的分类方法，下面给岀其中涉及到的儿个基本术语:1. 搜索空间搜索空间包含所有项目的一切组合，即指定数据集中全部项集构成的集 合。如果交易数据9面向零售业的关联规则动态挖掘算法研究集中包含项目的个数为n，则搜索空间中包含2n个不同的项集。也就是说, 搜索空间中项集的个数与

53、数据集屮项冃的个数是成指数增长关系的。所以当n比较大时，如 果直接生成所有的项集并按照扫描数据集记录累加的方法对各项集支持度计数的话，所需的计算 代价是非常庞大的。为了便于后续术语的理解，可以将搜索空间采用有向图的方式进行描述。以集合i x, y, z为例，根据搜索空间的定义，可以得出8个项集，即，x, y, z, x,y,x,z , y,z , x, y, z o则，集合i x, y,z构成的搜索空间的有向图表示如图2. 1所示。x, yx, zy, zx, y,z图2. 1搜索空间的有向图表示2. bfs 和 dfs根据上述搜索空间的有向图描述，可以很容易理解算法遍历候选项集时的搜索方式一一广度优先搜索方式bfs以及深度优先搜索方