（计算机软件与理论专业论文）零售业中olap和数据挖掘若干算法的研究与实现.pdfVIP

摘要 摘要 “数掘挖掘”( 包括o l a p ) 是- i 7 与实践紧密相连的具有较强技术性的学科。蕊对 着国内各个鞭域，包括零售、金融、萃茸学、蘸学等每年都在积累下海藿的数嚣的 现实状况，数据挖掘越来越需要把它的对数搬内在模式和规樟的深入分析和发现 静思想贯穿到实际瘦糟当孛。 遗憾的是，尽管每年都产生大量的论文和文章探讨数据挖掘技术，大部分是 讨数攒挖箍檄念和理论靛探讨，报难看妥吴髂静实戮和应焉。本文佟者在实习粥 州，参与并完成了基于微软分析服务器的销售分析与报表系统：并程公司即将开 始豹数据挖掇颈嚣中，完戒了多个耋鬃算法豹设诗耧c + + 程净实凌：萋于多瑟分 类商品树的商品关联规则算滋，会员顾客的购物频繁序列模式产生算法；基于信 惠璃壤论器条串概率捞匏会爨矮客分黉f 决繁褥) 算法，并分鞠镬霜数据进行了溺 试，取得了较好的结聚。其中第一个和第三个算法具有相当的可扩展性，第二个 算法崧小援模以及中簿援模瓣数攥量下是毒效翡。 关键诵：数据挖箍联祝分析楚理燕联麓剿序列模式决策拇 a b s t r a c t d a t am i n i n g ( i n c l u d i n go l a p 、i sa ns u b j e c tw h i c ha s s o c i a t e sw i t hp r a c t i c ec l o s e l y f a c e dw i t hm o r ea n dm o r ed a t as t o r i n ge v e r yy e a ri na l m o s ta l lk i n d so fd o m a i n s ，s u c h a sr e t a i l ，f i n a n c e ，s c i e n c ea n dm e d i c a l , t h e r ei sa nu r g e n tn e e df o rd a t am i n i n gt ou s ei t s k e r n e lt h o u g h t - h a v ea r ti n s i g h tt od a t aa n dm a k ed i s c o v e r y - t or e a la p p l i c a t i o n i t sap i t yt h a ta l t h o u g ht h e r ea r em a n yp a p e r sa n da r t i c l e sf o c u s e do nd a t am i n i n g p u b l i s h e de v e r yy e a r , m o s to ft h e md e a l w i t hd a t am i n i n gc o n c e p ta n da b s t r a c t a l g o r i t h mt h e o r y , i ti sh a r d l yt os e et h e i rr e a li m p l e m e n t a t i o na n da p p l i c a t i o n i nt h i s c o n t e x t ，w h e n1w a si nm yg r a d u a t ee x e r c i t a t i o ni nac o m p a n yi nb e i j i n g ，w h i c hf o c u s o nd e v e l o p i n gs u p e r m a r k e ts o f t w a r e ，ij o i n e da n dc o m p l e t e da no l a p ( 0 n l i n e a n a l y t i c a lp r o c e s s i n g ) p r o j e c t ，m e r c h a n d i s ea n a l y s i sa n d s a l er e p o r ts y s t e m ，w h i c h b a s e do nm i c r o s o f ta n a l y s i ss e r v i c ea n dm i c r o s o rs q ls e r v e r ia l s od e s i g na n d i m p l e m e n tt h r e ei m p o r t a n ta l g o r i t h m s ：m e r c h a n d i s ea s s o c i a t i o nr u l ea l g o r i t h mb a s e d o nm u l t i l e v e lm e r c h a n d i s ec a t e g o r y , s u p e r m a r k e tm e m b e rc u s t o m e rs h o p p i n gf r e q u e n t s e q u e n c eg e n e r a t i n ga l g o r i t h m ，c u s t o m e rc l a s s i f i c a t i o n ( d e c i s i o nt r e e ) a l g o r i t h mw h i c h b a s e do ni n f o r m a t i o ne n t r o p ya n dc o n d i t i o n a lp r o b a b i l i t yt r e e ，a n dt h e ya l la c h i e v e e x p e c t e dr e s u l t t h ef i r s ta n dt h et h i r da c h i e v eg o o dp e r f o r m a n c ea n ds c a l a b i l i t y , t h e s e c e n di se f f e c t i v ew h e nu s e di ns m a l la n dm e d i u md a t a s e t s k e y w o r d s ：d a t am i n i n g ，o l a p ，a s s o c i a t i o nr u l e ，s e q u e n c em o d e l ，d e c i s i o nt r e e 创新性声明 y 5 8 3 4 0 9 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名 键锰轧 日期 兰! ! 芏上2 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定即：研究 生在校攻读学位期问论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文：学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密，在年解密后适用本授权书。 本人签名 签缝纽、 导师躲籍每h导师签名：彳d - 矿i 。j 日期鲨! 望! ! 1 日期仁融t 第一章绪论 第一章绪论 1 1 研究背景 数据采集和存储技术的进步导致庞大的数据库日益增多。这已经发生在人类 耕耘的几乎所有领域，从普通的( 比如超市日常业务数据，信用卡使用记录，电话 呼叫清单以及政府统计数据) 到不太普通的( 比如天体图像，d n a 分子数据库和医 疗记录1 。那么，能否从这些数据中提取出有价值的信息呢? 毫无疑问，人们对这 个问题的兴趣度在不断增长，而且已经形成了致力于这个任务的一门学科，即” 数据挖掘( d a t am i n i n g ) ”。 数据挖掘经常被置于更广阔的数据库知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s e ) ，也就是k d d 的大背景下。k d d 这个术语来源于人工智能( a i ) 领域。 k d d 过程包括几个阶段：选择目标数据，数据预处理，数据转换( 如果需要) ，数 掘挖掘以及提取模式和关系解释并评价发现的结构。 一个典型的商业公司每年产生g b 级的数据。组织需要对大量的数据进行分 析，以获得有价值的信息，比如顾客的行为模式等，以期制定商业决策等。数据 挖掘是对大量的数据处理以发现隐藏的模式和结构的过程。已经有很多成功的数 据挖掘应用在各个领域，比如顾客的细分( p r o f i l e ) ，欺诈检测，电信网络检测，市 场购物熊分析。其中的关联规则挖掘算法找到如下形式的规则，i f t h e n 规则 个 f i 型的例子是”( 周术，尿布) 专( 啤酒) ”，这类信息可能会帮助商店进行货架的摆 放，即把尿布和啤酒摆放在一起由可能增加啤酒的销售。在信用卡交易中，一条 如下形式的规则：i f ( 条件) t h e n ( f 欺诈交易) 帮助确定一笔可能的欺诈行为。 1 2 数据挖掘的任务 数折：挖掘的任务主要包括以下几种： 1 探索性数据分析( e x p l o r a t o r yd a t a a n a l y s i s ，e d a l 正如名字所暗示的，这种方法的宗旨就是对数据进行探索，在探索时并一定 要有什么目的。通常e d a 技术是交互式的( i n t e r a c t i v e ) 年l l 可视化( v i s u a l ) l 拘。比如【8 】 描述了使用复杂的立体显示来可视化随时间变化的长途电话网络模式。o l a p 技 术可以包含在探索性数据分析中。 2 描述建模 描述模型的目标是描述数据的所有特征。这样的例子包括为数据的总体概率 分布建模( 密度估计d e n s i t ye s t i m a t i o n ) ；聚类分析和区隔( c l u s t e ra n a l y s i sa n d s e g m e n t a t i o n ) , 以及描述变量间的关系( 依赖建模d e p e n d e n c ym o d e l i n g ) 。例如在区 隔分析中，目标是把相似的记录分成一组，这样可以使广告商或者销售者把它们 的促销策略指向最可能相应的人群，以提高回馈率和节省资源。这与聚类分析不 零售业中o l a p 硐】数据挖掘若干算法的研究与实现 同，在聚类分析中是发现数据( 例如科研数据库) 中的”自然”群体( 在不需要严格加 以区分的情况下，这两种也可统称聚类1 。区隔已经被成功地应用于市场营销领域， 愀据购买模式和年龄，收入等人口统计数据，把客户分成均匀同质的小组_ 】。 3 预测建模( 分类和回归) 预测建模的目的是建立一个模型，这个模型允许我们根据已知的变量值来预 测其它某个变量值。在分类中，被预测的变量是范畴型的，而在回归中被预测的 变量是数值型的。预测模型的例子如下【9 】：s k i c a t 系统使用树结构建立了一个 分类牛j f ，这个分类树可以根据4 0 维的特征向量分类星体和星系。这个系统常年被 用束对天空数字图像中的上百万星体和星系进行自动分类。分类技术在第五章中 f | 业为弹细的介缁。 4 寻找模式和规则 上面列出的三类任务都致力于建立模型，寻找模式和规则致力于模式探测。 一个例1 ，是欺诈检测，寻找明显不同于其他点的数据点，以检测可能出现的欺诈 行为( 也叫孤j ：点检测) 。还有一个例了是超市交易数据库中发现频繁出现的商品 组合( 比如同常用品经常被一起购买) ，这个问题在第二章中得到了较好的解决。 其它实例包括：美国的职业篮球比赛( n b a ) 会常规性的提供每场比赛的详细记录， 包括命中率，持球时间，传球次数，犯规次数等。 1 0 3 的超级侦察系统从这些记录 中搜索类似规则的模式，目的是发现职业教练可能注意不到的有用信息片断( 例 如，当选手x 在场时选手y 的投篮准确率从7 5 下降到3 0 ) 。 5根捌内容检索 这种任务对于文本和图像数据集合应用最为普遍。对于文本，模式可能是一 系列关键字，用户希望在庞大的文档集合中搜索相关的文档( 类似搜索引擎) 。对 j 二图像用户可能有一幅样本图像，或一幅图像的描述等，从庞大的图像集合中 搜索类似的图像。这种情况下，相似性的定义非常关键。比如g o o g l e 系统中使用 被称为”p a g e r a n k ”的数学方法估计各个网页的相对重要性。 1 。3 统计和数据挖掘的关系 数掘挖掘技术本身是对大量数掘集的分析，因此传统的统计学在数据挖掘中 起着非常重要的作用( 这一点在以后的几章中被不断的证明) 。例如在一个天体数 掘库中，我们可能希望得到这样一个结论：类似这个天体的所有对象的行为是这 样的”，并且附带一个概率值( 置信度，或叫正确度) 。 概率本身是入们处理不确定性的一种方法。对不确定性建模几乎是所有数据 分析工作的一部分。迄今为止，应用最广的是概率理论模糊逻辑是另一个应用 很广的理论但这个领域，以及与之相关的一些领域，比如可能性理论( p o s s i b i l i t y 第一章绪论 t h e o r y ) 和粗糙集( r o u g hs e t s ) ，缺少概率理论所具备的完整理论框架，目前的应用 还非常有限。 1 4 零售企业的信息化现状 当信息时代到来之际，零售企业同其它传统商业一样，都面临着信息化的巨 大挑战，需要将信息化设备和技术将广泛应用在商业贸易活动中。 零售企业信息化一般经历电算化( 以p o s 设备使用为标志) 、系统网络化( 以 商业企业中重要业务部门，如财务、人事进入电算化范围并逐步形成信息联网为 标志) 及应用全方位化( 以部门环节化、网络流程化为基础，商业企业全面应用 信息化手段为标志) 的三个阶段。 抓训查结果显示：目前我国大多数零售企业f 处于第一、二阶段，这些被访 单位p o s 设备应用、计算机硬件数量、联网比例及站点丌通状况等硬性指标完成 状况良好但是却缺乏信息化手段的深入、全面应用。他们在销售、库存、财务、 人事等方面实施了信息化管理，但是在更具行业特色的供应链管理、配送管理、 客户关系管理和决策支持系统上实施效果不明显或者还根本没有实施。 特别是随着我国加入w t o 步伐的加快，政府将取消外国零售业进入中国的 一切限制，国外零售巨头纷纷抢滩中国零售市场，零售行业的竞争办愈来愈激烈。 为了加快超市现代化管理，提升核心竞争力，国内很多的零售企业都在想方设法 进一步增强企业的信息化含量，比如华联超市最近推出的“第三方物流系统“和 “自动补货系统”，使企业的信息化程度到达了新的层次。但是在和企业长远利益 休戚相关的决策支持系统和客户关系管理方面，据笔者所知，绝大多数零售企业 都未起步或刚刚起步。 在这方面，零售之王沃尔玛的成功经验可带给我们不少的启示。2 0 0 2 年1 月 2 2 同，美国第二大连锁零售商凯尔特以1 6 3 亿美元的巨额负债申请破产保护，同 一天，凯尔特几十年的老对手，沃尔玛则宣布，2 0 0 1 财政年度公司销售收入超过 2 2 0 0 亿美元，成为全球销售额最大的公司。凯尔特为何与沃尔玛有如此大的差 距? 主要原因就在对信息技术的把握有极大不同。凯尔特的技术总监始终未能拿 出一套切合公司实际的信息管理系统有效管理库存、运输和储藏等商品供应链问 题。祆尔玛专门建立了世晃上一流的信息管理系统，包括卫星定位系统和电视调 度系统，全球4 1 0 0 个店铺的销售、订货、库存情况可以随时调度查阅，以及完善 的物流管理系统，先进的供应链体系。 零售业是与最终消费者打交道的行业，如果不以满足顾客为中心是无法生存 下去的。这一点沃尔玛笔谁都清楚。”让顾客满意”始终被沃尔玛排在第一位。比 如在客户关系管理( c 蹦) 上，沃尔玛每周都对顾客期望和反映进行调查，管理人 零售业中o l a p 羽i 数据挖掘若干算法的研究与实现 砒迎j 蔓x , j u 脑f 信息系统收集信息，或者通过直接调查收集到的顾客期望及时更新 崩lu j 组合和组织采购，改进商品陈列摆放，营造舒适的购物环境。顾客不但得到 称，l i 、_ ：。= 的商几i ，而n 得到全方面的购物享受。 2 0 0 1 年血月沃尔玛把3 0 0 0 台n c r 网络自助服务亭部署在沃尔玛全球的每 客商场及超市。这种用于礼品注册的自动客户服务机将放置在沃尔玛珠宝柜台 刚压，顺窖。j j ：咒把婚宴、婴儿出生纪念所需物品清单输入服务机，以便为亲朋好 友购买礼品时参考。沃尔玛高级副总裁兼首席执行官k t u r n e r 先生说这项客户 服务技术简单易用，给我们的客户提供了更多的购买选择。 在我们第四章、第血章中讲述的内容中，基本上都是面向会员顾客的。因此 仃必嘤介纠会员制零售企业在中国的发展现状。这方面的一个很好的实例就是来 n1 9 9 6f 1 ：进入r p 圈的荷兰零售业巨头万客隆。力。客隆的会员制曾一度受到挫败： 卜篮蟓l 套i 舀：于中幽人似乎还未接受“先要成为会员，然后才能消费“的模式。通 过结合中国市场消费特点和中国人的心理特点力客隆逐渐在调整经营模式，丌 蚧。会寻求细分的客户市场；并努力通过营运管理、信息技术不断提高服务效率， 培夼和j _ r 人稳定、忠实的专业顾客群。在客户关系管理( c r m ) 理论中有一个经 越的2 8 原则，即8 0 利润来自2 0 客户。万客隆在北京的两家店萨在从面向最 终j j t | j 旧刘人客户转型，争墩辟快实岘7 0 垒8 0 的销售由集f ； 客户来完成的 f 常比例相信通过实施企业的更高层次的信息化措施，即c r m 和数据挖掘技 术，能够赢得更为广大和忠实的客户群。 1 5 自动推荐系统 | 1 f = 柠系统被i | l 水向它( 电子商务网站，零售业的收款机) 的顾客( 用户) 做出推荐。 推 孙0 而m l 叮以按照实际销量大小，按照商品间存在的自然的关联，还可以基于 顺客的特征分析结果，或者对一个顾客的过去购物行为分析从而对未来行为做出 预j l ：| 。这些技术可以帮助使用者更好的建立自己部门的个人化的风格，从而更好 的h k 务顾客。 自动推荐系统中宅要包含两种技术：信息过滤( 也称为基于内容的推荐) ；协同 过滤。i j u 占根掘刚、的必趣或用户的行为对用户兴趣建模，获取用户感兴趣的内 容项，应用于不同领域的智能a g e n t 就是典型的信息过滤系统。出于信息过滤系 统加入了用户的个人信息，相对于信息检索的通用性来讲，信息过滤是一种重要 而有效的个性化技术。关联规则的挖掘特别适合这一任务( 虽然关联规则未曾考虑 到用户，但也可基于商品本身的关联做出推荐) 。在超市业务中，不存在像在网站 中需要用户( 顾客) 对网站提供内容的兴趣度评分( 用户对这一点经常是反感的) ，因 为颇客的实际购买行为已经隐减着顾客的兴趣度趋向，所以有更大的可能发现隐 第一章绪论 减着的感兴趣的商品之间的关联。信息过滤的局限在于它处理的对象多是文本的 内容，必须要对对象定义特征向量空间，要推荐的每一项内容都必须能使用具有 特征的向量来表示，但诸如声音，图像等多媒体内容的特征抽取难度较大，增加 了信息过滤技术进行推荐的难度。 协同过滤技术避免了信息过滤的不足，无需考虑内容的形式，通过其他用户 对内容项的评价进行推荐。基本思想是根据用户以往对内容项的评价，比较用户 剐的兴趣相似度，然而根据与目标用户具有较大相似度的其他用户的观点向该用 户做出推荐。比如g r o u p l e n s f 6 】系统：基于评价的自动系统过滤，利用与一个目 标用，o 的相似团体内( 也叫邻居) 的多个用户对多个文档，u s e n e t 新闻，电影等做出 评价，从而为陔目标用户推荐得分较高的评价结果。而在实际的零售业中的研究 比较少。不过就自动推荐系统的关键技术来说，两者没有多大差别。比如可以将” 文档”变成”商品”，将顾客的购买看成是隐式的评价，在找到一个顾客( 目标顾客) 的相似群体后，即可达到为目标顾客推荐得分较高的商品的目的。其缺点包括： 1 ) 用户对内容的评价矩阵非常稀疏； 2 ) 如粜从来没有用户对某一项内容加以评价，则该对象不可能被推荐。 本文第二章的商品销售分析报表( 可以看出一段时间内受到顾客欢迎的商品) 、 以及第三章商品关联规则算法、第四章购物序列算法都可用于超市自动推荐系统 的任务，特别是在第四章详述了顾客购物频繁序列模式在自动推荐系统中的应用。 1 6 本文的研究内容 面对零售业中的决策支持系统和客户关系管理系统的具体设计、实现较为缺 乏的现实状况，本文作者在实习期间参与并完成了基于微软分析服务器和 o w c ( o f f i c ew e bc o m p o n e n t ) 控件的商品销售分析与报表系统，较好的完成了大量 商品销售数据的提取，加载，聚集计算、销售分析等任务，并建立了最终的图形 化输出界面；在广泛参阅国外，国内多篇学术性论文的基础上，面向超市业中的 自动推荐系统，使用c c + + 完成了与自动推荐系统和客户关系管理( c r m ) 相关的三 个算法的设计与实现：a ) 基于多层商品分类树的商品关联规则算法；b ) 会员顾客 的购物频繁序列模式的产生算法：c ) 基于信息熵理论和条件概率树的顾客分类f 决 策树) 算法：其中商品关联规则算法使用实际的超市销售数据进行了检验，得出了 一部分有价值有意义的规则，并和其它两种较早的著名算法做了比较，取得了最 优的时间效率。第二种算法使用人工合成的中、小规模数据集进行了测试，得出 了正确的结果序列集合，虽然由于算法在产生候选序列阶段存在着一定的缺陷， 致使结果不完整。第三种算法使用m sa n a l y s i ss e r v i c e 中自带的f o o t m a r t 2 0 0 0 数 零竹业- l ，o l a p 和数据挖掘若干算法的研究与实现 掘库进行了测试，取得了和微软提供的决策树( m i c r o s o f t 算法基_ d e c i s i o nt r e e ) 奉一致的分类结果。其中第一和第三种算法时间效率都是相当好的，具有可扩展 件：第一个算法m 于计算过程较为复杂，比较适合小规模数据的挖掘。同时在实 脱的过程巾，聚丌= 】了动念分配内存的技术和其他优化技术，最大限度的节约了内 存的使用。作肯的狂序丌发环境足p 4 ，w i n d o w s 2 0 0 0p r o f e s s i o n a l 操作系统，内存 1 2 8 兆，丌发工具是v c + + 6 0 。所有算法结果的图表均真实有效，具有再现性。 在此作者作一点点声明，在第三、四、五章中，j l 是由作者自己提出或实现 了的算法，都进行了编号：反之，对其他文献中的相关算法，没有编号但给出了 m 处。 1 7 论文的组织结构 第章讲述了笔者实习期f r j 在公司协助开发的基于微软分析服务器和o w c 控 件的商品销售与分析报表系统：第三章主要介绍了基于多层商品分类树的商品关 联规则翁法及咫奂验结果：第四章讲述了会员顾客的购物频繁序列模式产生算法 硬j c 实验结燃：销fl0 吲 ：述了基于信息熵理论的顾客分类算法及其实验结果；第 ? 、章为结沦和腻坐。 第一二章基予微软分折服务器的商品销售分析与报表系统 第二章基于微软分析服务器的商品销售分析与报表系统 2 1 数据仓库 宽松的讲，数据仓库是一个更大范围的数据库，它与操作数掘库分别维护。 许多组织收集了各种与业务相关的数据，并由多个异种的，自治的，分布的信息 员分别存储。数据仓库是对这些异种数据源的集成。按照w h i n m o n 这位数据仓 库系统构造方面的领头设计师的说法，”数据仓库是面向主题的，集成的，不可更 新的( 稳定性) ，随时间变化的( 不同时间) 的数据集合，用以支持经营管理中的决策 指定过程”。 让我们分别看看这些关键特征： 面向主题的( s u b j e c to r i e n t e d ) ：数据仓库围绕一些主题，比如商品销售分析， 人力资源分析，雇员业绩分析等。 集成的( i n t e g r a t e d ) ：数据仓库将多个不同数据源的数据集成在一起，如一家拥 有很多分店的连锁零售企业，每个分店都有一台数据库服务器。 时变的( t i m e v a r i a n t l ：数据仓库的数据随时间而不断增长。 稳定的( n o n v o l a t i l e ) ：数据仓库的数据往往是很长时间的数据积累。 2 2o l a p 基本概念和原理 2 2 1o l a p 的基本概念 联机分析处理( o l a p ) 的概念最早是由关系数据库之父e e c o d d 于1 9 9 3 年 提出的，他同时提出了关于o l a p 的1 2 条准则凹l 。o l a p 是使分析人员、管理 人员或执行人员能够从多角度对信息进行快速、一致、交互地存取，从而获得对数 据的更深入了解的一类软件技术。o l a p 的目标是满足决策支持或者满足在多维 环境下特定的查询和报表需求。 o l a p 的技术核心是”维”。“维”是人们观察客观世界的角度，是一种高层次的 类型划分。“维”一般包含着层次关系，这种层次关系有时会相当复杂。通过把一个 实体的多项重要的属性定义为多个维( d i m e n s i o n ) ，使用户能对不同维上的数据进 行比较。因此o l a p 也可以说是多维数据分析工具的集合 o l a p 的基本多维分析操作有钻取、切片、切块、以及旋转等。钻取是改变 维的层次，变换分析的粒度。它包括向上钻取和向下钻取。上钻是在某一维上将 低层次的细节数据概括到高层次的汇总数据，或者减少维数；下钻则相反，它从 汇总数据深入到细节数据进行观察。切片和切块是在一部分维上选定值后，关心 度量数据在剩余维上的分布。如果剩余的维只有两个。则是切片：如果有三个， 则是切块。旋转是变换维韵方向，即在表格中重新安排维的放置( 例如行列互换) 。 零传、| j ：中o l a p 和数据挖捌若干斧法的研究与实现 2 2 2o l a p 的三种实现方法 根据存储数据的方式不同可以分为r o 乙心、m o l a p 、h o l a p 。r o l a p 表 示鉴 ：关系数拙阵的o l a p 实现，以关系数据库为核心，以关系型结构进行多维 数据的表示和存储m o l a p 。m o l a p 表示基于多维数据组织的o l a p 实现。 m o l a p 使用多维数组存储数据。多维数据在存储中将形成”立方块c u b e ”的结构， m o l a p 是产生多维数据报表的主要技术。h o l a p 表示基于混合数据组织的 o l a p 实现，它足将低层数据存储在r o l a p 中，而高层数据存放在多维立方体 中。微软的分析服务器就提供了这种实现。 2 2 3o l a p 和数据挖掘的比较 o l a p 是数捌汇总、聚集工具，支持上钻、下钻、旋转、切片等操作，主要 是从宏删刈数抛进j j ：分析；数据挖掘不限于分析数据仓库中的数据，它也可以分 析文奉的，出务的，空m 的和多媒体数据，这些数据很难用多维数据库技术建模。 在这种意义下，数据挖掘提供的功能和处理的数据复杂性要大的多。 2 3 m o l a p 的多维聚集计算原理 | j “州j 见1 no l a p 实现为m o l a p 。在笔者所在公司的销售分析与报表系统 。n 也采用的赴m o l a p 方式。我们对m o l a p 的基本原理作一些介绍，因为着 眼于o l a p 的具体应用，不准备做更深入的分析。企业在考虑产品的销售情况时， 通常从时间、地区和产品的不同角度来深入观察产品的销售情况。比如2 0 0 3 年 东城区的5 家分店的总销售额是多少? 销售额在所有分店的排名情况? ”等问题。 _ _ js q i 语句完成这样的任务显然过于复杂。m o l a p 的( 超) 立方体结构提供了巨大 的力使。 h 时州、地区和产品代表矸i 同的维度( 相当于多维空问的坐标值) ，可形 化表示为( 维l ，维2 ，维n 。度量指标) ，如( 地区、时间、产品、销售 额) 。可以山浚数据立方体计算的方体总数为2 3 = 8 个，可能的分组为 ( 时问，店铺， 商品) ，( 对矧店锚) ，( 时测，商品) ，( 店铺，商品) ，( 时间) ，( 店铺) ，( 商品) ，( ) 共八 个，其中( ) 折审分组，即不对任何维分组。这些分组构成了该数据立方体的方体 格，如图所示。基本方体包含所有的维，时间，店铺。商品，它可以返回这三为的 任意组合。顶点方体或0 - d 方体表示分组为空的情况，它包含所有销售额，销 售量的和。 在【4 l 中，g r a y 提出了数据立方计算问题并给出了c u b e b y 算子( 该算子已在m s s q ls e n r e r 平式得到应用) 。c u b e b y 算予是对g r o u p b y 算子的扩充，用于计算c u b e b yr 句 1 各属性的所有可能组合( g r o u pb y ) 。对于含n 个属性的c u b eb y ，将计算 第一二章基 j 微软分析服务器的商品销售分析与报表系统 2 ”个不同的g r o u pb y 一个g r o u pb y 可被看成一个数据子方体( c u b o i d ) c u b o i d 满 足”格”的继承关系，即一个( k 1 ) c u b o i d 可从k - c u b o i d 计算出来。 ( s t o r e ，p r o d u c t ，t i m e ) 幽2 3 i ：三维方体格 对于不同的查询，o l a p 可能要访问不同的方体。大多数o l a p 产品都采用 预先计算多维聚集的方法，带来快速的响应时间。并且，在计算高层次的聚集时， j 以借助已经计算好的低层次的聚集结果，而不必由基本事实表计算。 m o l a p 在内存中使用的是多维数缀的存储方式。数组是由称为”块( c h u n k ) ” 的单元组成，n 维数组分成n 块。每个块作为一个压缩后的对象存放在磁盘上， 不存储空单元。可以使用”块+ 偏移量”作为在块内寻找单元的寻址机制。这种压缩 技术功能强大，足以处理磁盘和内存中的稀疏立方体。通过访问立方体单元，计 算聚集值。可以优化访问单元的次序，使得每个单元必须重复访问的次数最小化， 从而避免重复访问某些单元。出于分块技术涉及聚集计算的重叠，该技术被称为 数抛立方体计算的多路数组聚集。在微软分析服务器中使用了种复杂的算法来 选择要预先进行计算的聚合，这样其他聚合就可以很快通过其他已经计算好的值 计算出来3 0 5 引。 2 4o l a p 系统架构及前端展现工具的实现 在这一节将主要介绍笔者所在公司o l a p 项目的整体体系结构和o w c ( o 珩c e w e bc o m p o n e n t ) 控件的使用。在商务智能的体系结构中，源数据经过 e t l ( e x t r a c t i o n 、t r a n s f o r m a t i o n 、l o a d ) 过程( 通过d t s 数据转换服务的定时上传) 将从多个不同数据源提取的数据进行清洗、合并、加载到数据仓库或数据中心中， 最终用户想要获得的结果，是想通过某种工具将这些数据以各种形式( 报表、图 形) ，从各种角度向用户形象地表达分析的结果和趋势，以达到为使用者提供管理 或者决策依据的目的。因此，数据展示工具是整个商业智能解决方案中一个非常 重要的组成部分。 零伴、l i ，中o l a p 平fj 数据挖捌若干算法的研究与实现 堑j ：微软分析服务器的o l a p 解决方案是一个完全支持w e b 应用的方案。用 户可以通过的w e b 浏览器，向一个应用代理服务器发送访问多维数据的请求，代 理服务器根据请求，从分析服务器中将需要的图文结果返回到用户的w e b 浏览器 卜 o w c ( o f f i c ew e b 组件) 包含在o 硒c e2 0 0 0 中，其行为类似于其他o f f i c e 应用 种f j ：，”则荣竹：足存i n t e m e t i n t r a n e t 环境。其组成部件包括：电子表格组件 ( s p r e a d s h e e t ) 、数掘透视表组件( p i v o t t a b l e ) 、图组件( c h a r t ) 、数据源组件( d a t a s o u i c e ) 。我们使用的主要是数据透视表组件和图组件。数据透视表组件可以方便 的胜j i 数扒仓库- 扣每一个概念分层的汇总和细节数据。它通过o l ed b 从数掘库 l i ，捩取数j 1 i 1 把它绑定到o l a p 立方体后，它提供一个灵活、高效的分析界面。 c h a r t 炎似j e x c e l 一| j f j 0 图表制作功能，提供了直观，方便的界面显示技术。它支 持e x c e l 中火多数的二维图表。 o w c 控件的使用并不困难。由于它本身也是可以嵌入到多种应用程序( 例如 j e ) 的a e t i v e x 控件，因此同样也有公共属性。各种方法可供用户调用。一般来说， 部会有如卜世! 属性： ( o n n e c t i o n s t r i n g ：数拚 溺 连接字符帛 c o m m a n d t e x t ：s q l 语句，适用于表格数据源 d a t a m e m b e r ：数据源卜待绑定的面向某个主题的立方体 d a t a s o u r c e ：此属性设置为数据源组件( d s c ) 的一个实例，即使使用内置的 c o n n e c t i o n s t r i n g 属性时，d a t a s o u r c e 也将返回d s c ； 州时还支持如下常用事件： q u e r y c o m p l e t e ：响应用户对数据源的查询操作： c l i c k ：啪应川，2 在报袁的任何位置单击； d b l c t i c k ：显示聚合项的详细数据( p i v o t t a b l e 控件) ： 将一个o w c 控件插入到i e 中，设置它的如上属性，无需编写任何代码就可以 荇到立方体中的数据。对以上事件的自动响应也是由o w e 控件自动完成的。 存客户浏览器端，客户端系统安装网络浏览器与w e b 站点进行交互，服务器 端川样安装相成的数据库管理系统和软件，其常见的操作过程是：用户首先登陆 客户端系统并打j 1 ：w e b 浏览器，通过w e b 浏览器访闯w e b 站点，用户发出请求， w e b 涨务器将请求递交应用程序服务器；安装有m s a n a l y s i sm a n a g e r 的应用服务 器对数据仓库服务器上的数据进行处理，处理结果返回w e b 站点服务器，链接服 务器再返回给用户测览器。链接服务器具各高速缓存功能，可以将用户频繁查询 的页面保留在高速缓存中，加快对查询的响应。 数据仓库服务器中存储的是企业日常事务数据，一般都在上百g b 级( 笔者所 在的超市系统中的数据最大约为6 0 g b ) ，应用服务器的配置相当的高，要求很高 第二章基于微软分析服务器的商品销售分析与报表系统 的处理速度，比如在笔者所在的企业中应用服务器是1 g 内存。 我们的销售分析与报表系统采用的体系结构是四层客户n 务器结构，如下图 所示。 应 取数据 刚 服 务 送数据 器 图2 4 1 o l a p 系统配置图 发出请求 客 户 浏 览 饭同钴耍 器 这种结构的优点在于将应用逻辑( 或业务逻辑) 、g u i 及d b m s 严格区分开来， 复杂的应用逻辑不是分布在网络上的众多p c 机上，而是集中存放在应用服务器 【j ，由服务器提供高效的数据存取，安排后台处理以及报表的预处理。显然，o l a p 应用服务器的构建基础是基础仓库或基层数掘库，数据仓库主要包括细节数据， 应用服务器主要功能之一是对细节数据进行汇总，产生更高层次的，通常也是决 策人员更关心的综合数掘。 每天各个店铺的销售数据在微软的自动d t s ( 数据转换服务) 下通过网络定时 l 传到企业的数据仓库服务器中( 经过e t l 的数据清洗、转换、合并等过程) ，数 据仓库服务器中同样运行的s q ls e r v e r ，保存的是细节数据，比如每一笔销售的情 况( 在实际数掘库中，每一笔销售中的每个商品都是作为一个记录插入到数据库中 的) 。应用服务器中运行的是m s a n a l y s i s m a n a g e r ，它通过局域网内的高速网络与 数据仓库服务器相连，保证了数据流的高速传输，在a n a l y s i sm a n a g e r 中建立了 面向不同主题的o l a p 立方体模型，如图2 4 2 的系统模型只是面向商品销售分析 】：题的。 冈引 毒 零售、l k 中o l a p 和数据挖掘若干算法的研究与实现 蚓2 4 2 一个基本的销售多维立方体波计模型 上图每个方框在数据仓库的d b m s 中都被设计为一个表，这是个良好的数 掂库改训所要求的，通过主键和外键的关系增加表之间的耦合度减少表内冗余 度。有些维度，比如同期，店铺，商品等具有较多的层次关系，需要在表结构中 包括表示赢属l 层i d 的宇段。比如在”店铺”表中，需要有店铺i d ( 也就是编号) ，店 铡名称，店铺所在区县的j d 等属性。其中店铺所在区县的i d 就与另一张”区县” 表刈应起来。还有，时间维表进一步划分为年表，季度表，月表等，这样在”星” 的角上又出现了分支，从而形成所谓的”雪片模式”。 在多维分析中，数捌是按维来表示的，例如时间，地理，商品等。我们采取 的维度丰要有如卜些：财务同期、自然同期、各个分店、商品、商品管理属性、 管理方式等( 在图巾末全画出) 。财务f | 期是指企业内部的销售业绩结算，与自然 h 期不i 司：商品管理属性是指商品在库存中的不同状态，包括正常品、次品、过 期品等：采用的度量值包括销售量、销售额、折扣、商品来客数、促销来客数、 毛利、毛利率等。商品来客数指购买该商品的人数；促销来客数指购买该促销商 品的人数。 建模结果见附录a 第二章基丁多层次分类商品树的关联规则产生算法 第三章基于多层次分类商品树的关联规则算法 3 1 关联规则的概念及定义 考察一些涉及许多物品的事务：事务1 中出现了物品甲，事务2 中出现了物 品乙，事务3 中则同时出现了物品甲和乙。那么，物品甲和乙在事务中的出现相 互之问是否有规律可循呢? 在数据库的数据挖掘中，关联规则就是描述这种在一 个事务 物品之f b j i 司h , j 出现的规律的知识模式。更确切的说。关联规则通过量化 的数字描述物品甲的出现对物品乙的出现有多大的影响。 现实中，这样的例子很多。例如超级市场利用前端收款机收集存储了大量的 售货数据，这些数据是一条条的购买事务记录，每条记录存储了事务处理时间， 顾客购买的物品、物品的数量及金额等。这些数据中常常隐含形式如下的关联规 则：在购买铁锤的顾客当中，有7 0 的人同时购买了铁钉。这些关联规则很有 价值，商场管理人员可以根据这些关联规则更好地规划商场，如把铁锤和铁钉这 样的商品摆放在一起，能够促进销售。 有些数据不像售货数据那样很容易就能看出一个事务是许多物品的集合，但 稍微转换一下思考角度，仍然可以像售货数据一样处理。比如人寿保险，一份保 单就是个事务。保险公司在接受保险前，往往需要记录投保人详尽的信息，有 时还要到医院做身体检查。保单上记录有投保人的年龄、性别、健康状况、工作 单位、工作地址、工资水平等。这些投保人的个人信息就可以看作事务中的物品。 通过分析这些数据，可以得到类似以下这样的关联规则：年龄在4 0 岁以上，工 作在a 区的投保人当中，有4 5 的人曾经向保险公司索蜡过。在这条规则中， “年龄在4 0 岁以上”是物品甲，“工作在a 区”是物品乙，“向保险公司索赔过” 则足物品丙。可以看出来，a 区可能污染比较严重，环境比较差，导致工作在浚 区的人健康：恢况不好，索赔率也相对比较高。 下面我们给出关联规则的形式化描述 设i = i l ，i 2 ，是一组物品集( 一个商场的物品可能有上万种) ，d 是一 组事务集( 称之为事务数据库) 。d 中的每个事务t 是一组物品，显然满足t 互i 。 称事务t 支持物品集x ，如果x c t 。关联规则是如下形式的一种蕴含：x y ，其 巾x _ c i ，y c ，且x n y = 6 。 ( 1 ) 称物品集x 具有大小为s 的支持度，如果d 中有5 的事务支持物品集x ： ( 2 ) 称关联规则x y 在事务数据库d 中具有大小为s 的支持度，如果物品集x u y 的支持度为j ： ( 3 ) 称规则x y 在事务数据库d 中具有大小为c 的可信度，如果d 中支持物品 集x 的事务中有c 的事务同时也支持物品集y 。 零售业中o l a p 和数据挖掘若干算法的研究与实现 如果不考虑关联规则的支持度和可信度，那么在事务数据库中存在无穷多的 _ x j 联觇| l ! j 。事。典h 人们一般只列满足一定的支持度和可信度的关联规则感兴趣。 在文献中，一般称满足一定要求的( 如较大的支持度和可信度) 的规则为强规则。 因此，为了发现出有意义的关联规则，需要给定两个阚值：最小支持度和最小可信 度。前者即用户规定的关联规则必须满足的最小支持度，它表示了一组物品集在 统计意义上的需满足的最低程度