（计算机应用技术专业论文）数值型多维关联规则挖掘研究.pdf

中文摘要 数值型多维关联规则挖掘研究 学科专业：计算机应用技术 指导老师：丁晓明副教授 研究方向：数据挖掘 研究生：张学斌( 2 0 0 2 5 0 5 ) 中文摘要 近年来，数据挖掘引起了信息产业界的极大关注。其主要原因是存在大量数 据。可以广泛使用，并且迫切需要将这些数据转换成有用的信息和知识。 关联规则是数据挖掘研究中的一个重要课题。它是从数据集中提取出有趣频 繁模式的过程。现在，已经提出很多经典的关联规则挖掘算法，如a p r i o r i 算法。 这些经典的算法绝大多数适用于布尔型数据。由于数据库中的数据类型是多样 的，因此如何在布尔型之外的其他类型上进行关联规则挖掘是当前关联规则研究 中的热点。 常见的数据类型有布尔型、类别型、数值型。其中数值型关联规则挖掘是当 前关注较多的领域。对于数值型数据，首要的是将其在值域上划分为区间。本文 将聚类思想引入到关联规则挖掘中。提出了区间阈值的概念，在该阈值的指导下 对属性进行划分，以解决现有算法不能解决的问题。 本文首先对数据挖掘进行介绍。然后将主要经典关联规则挖掘算法逐一介 绍。这些算法是多维关联规则挖掘算法的基础。论文重点对数值型多维关联规则 进行研究。分别介绍了区间合并算法和聚类算法。在聚类算法中，论文提出了 c a r b 算法。该算法是一个单趟扫描算法。当用户指定区间距离阙值i n t e r v a l 后， 算法自动将属性划分为区间。 本文的研究对于数值型多维关联规则和数据预处理的使用有积极意义。 关键词：数据挖掘关联规则多维关联规则聚类 英文摘要 r e s e a r c ho fm u l t i d i m e n s i o n a ln u m e r i c a s s o c i a t i o nr u l e s m a j o r ：c o m p u t e ra p p l i c a t i o nt e c h n o l o g y s u p e r v i s o r ：d i n gx i a o m i n g d i r e c t i o n ：d a t am i n i n g a u t h o r ：z h a n g x u e b i n ( 2 0 0 2 5 0 5 ) a b s t r a c t i nr e c e n ty e a r s ，d a t am i n i n gc a t c h e sag r e a td e a lo fa t t e n t i o ni nt h ei n f o r m a t i o n i n d u s t r y t h em a i nr e a s o no f i ti sd u e t ot h ew i d e a v a i l a b i l i t yo f h u g ea m o u n t so f d a t a a n dt h ei m m i n e n tn e e df o r t u r n i n g s u c hd a t ai n t ou s e f u li n f o r m a t i o na n d k n 0 、v l e d g e m i n i n g a s s o c i a t i o nr u l e si so n eo f t h eb e s ti m p o r t a n ta r e a so f d a t a m i n i n g ，w h i c h i sa p r o c e s so f e x t r a c t i n gi n t e r e s t i n ga n df r e q u e n tp a t t e r n sf r o m t h ed a t as c tt h e r ea f e m a n y c l a s s i c a l g o r i t h m s o n m i n i n g a s s o c i a t i o n r u l e s ，s u c h a s a p r i o r i t h e s e a l g o r i t h m sm o s n yi m p l yi nd a t a , w h i c hi sat y p eo fb o o l e a n b c c a n s ed a t at y p ei n d a t a b a s ei sr i c h e r , m i n i n go nd a t at y p ee x c e p tf o rb o o l e a ni so n eo f m a j o rt o p i ci n a s s o c i a t i o nr u l e sm i n i n g g e n e r a l l y ，d a t at y p e i nd a t a b a s ec a rb e q u a n t i t a t i v eo rc a t e g o r i c a l 。t h ef o r m e ri s m o r ei m p o r t a n tt h a nl a t t e r f o rn u m e r i cd a t a , t h ek e ys t e pi s d i v i d i n gt h ev a l u e d o m a i ni n t oi n t e r v a l s i nt h i s p a p e r , w ec o m b i n ec l u s t e rm e t h o dw i t hm i n i n g a s s o c i a t i o nr u l e s w ep r o p o s eac o n c e p ti n t e r v a l sw h i c hd e s c r i b et h es c o p eo f i n t e r v a l b a s e do nt h ec o n c e p t ，w ed i v i d e dt h ev a l u ed o m a i ni n t oi n t e r v a l s t h i sp a p e ri s o r g a n i z e da sf o l l o w f i r s tw ei n t r o d u c ed a t am i n i n g t h e nw e s y s t e m a t i cr e s e a r c ho nc l a s s i ca s s o c i a t i o nr u l e sm i n i n ga l g o r i t h m s t h e s e sa l g o r i t h m s a r eb a s eo fm u l t i d i m e n s i o na s s o c i a t i o nr u l e sm i n i n g t h e r ea r et w ok i n da l g o r i t h m s o nm u l t i d i m e n s i o na s s o c i a t i o nr u l e sm i n i n g ，m e r g i n gi n t e r v a l sa n dc l u s t e r i n g w e i n t r o d u c et h o s e r e s p e c t i v e l y i nt h i sp a p e r , w ep r o p o s ea na l g o r i t h m c a r b 哥h i c hi sa o n e - p a s sa l g o r i t h r a w h i l eu s e rs p e c i f yi n t e r v a l s ，t h ea l g o r i t h mc a r bc a n d i v i d e dv a l u e si n t oi n t e r v a l s o u rr e s e a r c hc 锄c o n t r i b u t e0 1 1 m u l t i d i m e n s i o na s s o c i a t i o nr u l e sa n dd a t a p r e - p r o c e s s 1 i 第一章绪论 第一章绪论 近年来，随着信息产业的迅速发展，人们积累的信息越来越多。激增的数据 背后隐藏着许多的重要的信息，人们希望能够对其进行更高层次的分析，以便更 好的利用这些数据。传统的数据管理方法可以高效的实现数据的录入、查询、统 计等功能，但无法发现数据中存在的知识和规则。因此出现了“数据丰富知识贫 乏”( d a t ar i c h ，i n f o r m a t i o np o o r ) 的现象。 1 1 数据挖掘的定义 数据挖掘就是从大量的数据中发现潜在规律、提取有用知识的方法和技术。 又称为数据库中的知识发现( k n o w l e d g e d i s c o v e r y i n d a m b 硒e ，k d d ) 。k d d 一词 首先出现在1 9 8 9 年8 月美国底特律举行的第1 l 界国际联合人工智能学术会议 上。从1 9 8 9 年到现在，k d d 的定义随着人们研究的不断深入也在不断完善，一 个比较广泛数据挖掘定义是：数据挖掘是从存放在数据库、数据仓库或其他信息 库中的大量数据中挖掘有趣知识的过程。数据挖掘的主要功能包括，聚类 ( c l u s t e r i n g ) 、分类( c l a s s i f i c a t i o n ) 、预测( p r e d i c t i o n ) 、关联分析 ( a s s o c i a t i o na n a l y s i s ) 、时间序列分析( t i m es e r i e sa n a l y s i s ) 等。 1 2 数据挖掘研究现状 1 9 9 5 年数据挖掘界召开了第一届知识发现与数据挖掘国际学术会议 1 。 1 9 9 8 年数据挖掘研究界建立起一个新的学术组织a c m - s i g m o d ( s p e c i a li n t e r e s t g r o u po f fk n o w l e d g ed i s c o v e r yi nd a t a b a s e s ) 1 9 9 9 年a c m s i g m o d 组织了第 五届知识发现与数据挖掘国际学术会议( k d d 9 9 ) 。专题杂志d a t am i n i n ga n d k n o w l e d g ed i s c o v e r y 自1 9 9 7 年起由k l u w e r s 出版社出版。涉及数据挖掘研究 的论文集有“a c m s i g m o d 数据管理国际会议( s i g m o d ) ”，“超大型数据库国际 会议( v l d b ) ”，“a c m s i g m o d s i g a r t 数据库原理研讨会( p o d s ) ”，“数据工程 国际会议( i c d e ) ”，“扩展数据库技术国际会议( e d b t ) ”涉及数据挖掘的杂志 有：( i e e e 知识与数据工程汇刊( t k d e ) ，c a c m 数据库系统汇刊( t o d s ) ，信 息系统，c v l d b 杂志，数据与知识工程，智能信息系统国际杂志( j i i s ) l 。 与国外相比。国内对数据挖掘的研究稍晚。1 9 9 3 年国家自然科学基金开始 对数据挖掘研究进行支持。1 9 9 9 年在北京召开的第三界亚太地区k d d 国际会议 第一章绪论 ( p a k d d 9 9 ) 推动了数据挖掘在我国的发展。 目前国内有许多高校和科研单位正在从事数据挖掘的基础理论和应用研究， 如清华大学利用概念格对数据挖掘的研究、北京大学对数据立方体的研究、中国 科技大学对序贯模式的研究以及系统工程研究所、上海交通大学、华中理工大学、 复旦大学、浙江大学等对关联规则的研究。 数据挖掘是当今许多研究领域的热点，许多数据挖掘系统己问世，并获得成 功。s a s 公司的e n t e r p r i s e m i n e r ，i b m 公司的i n t e l l i g e n t m i n e r 已在军事、工业、 商业、电信等部门获得了较好的经济效益。1 9 9 9 年s a s 宣布全球5 0 0 家大型企 业中有9 8 的企业是使用该公司的数据挖掘产品进行分析、运筹、和决策，提高 了企业的效益。目前实现数据挖掘的产品或原型系统主要有； q u e s t ：由i b m 公司的a l m a d e n 研究中心开发，用于发现关联规则、序 列模式、分类规则等。 d b m i n e r ：由加拿大s i m o nf r a s t e r 大学开发，用于多层次的规则挖掘。 i n t e l l i g e n t m i n e r ：由m m 公司开发，采用多种技术，是目前最流行的实 用挖掘工具之一。 a c 2 ：运行于w i n d o w s 或m o t i f 环境下的k d d 软件，提供了c + + 开发 工具箱和接口。 d i s c o v e r y ：独立工作于客户，服务器模式，通过分析历史数据，自动生成 规则，建立预测模型。 k d w + ：g t e 开发，采用多策略的统计方法。 s k i c a t ：分析大规模的宇宙数据。 i m a c s ：由a t & t 开发，用于知识库的构建。 i n l e n ：多学习策略组成的系统。 d m s k n o w l e d g em i n e r ：利用元模式技术指导数据挖掘。 f e d a ：由a t & t 研制，实现交互式挖掘。 j a m ：哥伦比亚大学开发的分布式挖掘系统，发现金融机构的欺诈行为。 d a t w i n ：采用神经网络和遗传算法 d a t a e n g i n e ：使用神经网络、模糊逻辑、信号处理等方法。 k n o w l e d g es e e k e r ：主要使用了规则发现和决策数方法。 2 第一章绪论 1 3 数据挖掘中采用的方法： 1 决策树方法：利用信息论中的信息增益寻找数据库中具有最大信息量的字 段，建立决策树的一个节点，再根据字段的不同取值建立树的分支：在每个分 支子集中重复建树的下层节点和分支的过程，即可建立决策树。国际上最有影 响和最早的决策树是q u i u l a n 研制的i d 3 方法。 2 神经网络方法：它模拟人脑神经元结构，以m p 模型和h e b b 规则为基础， 建立了三大类多种神经网络模型。 前馈式网络它已感知机、反向传播模型、函数网络为代表可以 用于预测、模式识别等方面 反馈式网络它以h o p f i e l d 的离散模型和连续模型为代表，分别用 于联想和优化计算 自组织网络它以a r t 模型、k o h o l o n 模型为代表，用于聚类 神经网络的知识体现在网络连接的权值上是一个分布式矩阵结构；神经 网络的学习体现在神经网络权值的逐步计算上( 包括反复迭代和累加计算) 。 运用神经网络的方法产生许多分类器。 3 覆盖正例排斥反例方法 它是利用覆盖所有的正例、排斥所有的反例的思想来寻找规则。比较典型的 有m i c h a l s k i 的a q l l 方法。a q l l 的主要思想是，在正例集中选择一个种子， 到反例集中逐个比较，对字段值构成的选择子相容则舍去，相斥则保留。按 此思想循环所有的正例种子将得到正例集的按则( 选择子的合取式) 4 粗糙集方法 在数据库中将每个元组看成一个对象，列元素看成属性( 分为条件属性和 决策属性) 等价关系r 定义为不同对象在某个( 或几个) 属性上取值相同，这些 满足等价关系的对象组成的集合称为该等价关系r 的等价类。条件属性上的等价 类e 与决策属性上的等价类y 之间有三种情况：l 下近似：y 包含e2 上近似： y 与e 的交非空 3 无关：y 与e 的交空。对下近似建立确定性规则，对上近 似建立不确定性规则( 含可信度) ，对无关的情况则不存在规则。 5 概念树方法 对数据库记录的属性字段按归类方式迸行抽象，建立起来的层次结构称为概念 第一章绪论 树。利用概念树提升的方法可以大大地浓缩数据库中地记录。对多个属性字段地 概念树进行提升，将得到高度概括地知识基表，然后再将知识基表转换为规则。 6 遗传算法 这是模拟生物进化过程的算法，有三个算子组成： 繁殖( 选择) 是从一个旧种群( 父代) 选出生命力强的个体，产生新种 群( 后代) 的过程。 交叉( 重组) 选择两个不同个体( 染色体) 的部分( 基因) 进行交换， 形成新个体。 变异( 突变) 对某些个体的某些差异进行变异。 这种遗传算法可起到产生优良后代的作用。这些后代需满足适应值，经过若 干代的遗传，将得到满足要求的后代( 问题的解) 。遗传算法已经在优化计算和 分类机器学习方法方面发挥了显著的作用。 7 。公式发现 在工程和科学数据库( 由试验数据组成) 中，对若干数据项( 交量) 进行 定的数学计算，求得相应数学公式。比较典型的b a c o n 发现系统完成了对物理 学中大量定律的重新发现。其基本思想是，对数据项进行初等数学运算，形成组 合数据项，若它的值为常数项，就得到了组合数据项等于常数得公式。 8 统计分析方法 在数据库字段项之间存在两种关系：函数关系( 能用函数公式表示得确定 性关系) 相关关系( 不能用函数公式表示。但仍能是相关确定关系) 。对它 们碍分橱采用如下方法：回归分析、相关分析、主成分分析，从中可以发现有用 的关联规则。 9 模糊论方法 利用模糊集合论对实际问题进行模糊评判、梗糊决策、模糊模式识别和模糊 聚类分析。模糊性是客观存在的。系统的复杂性越高，精确化能力就越低，即模 糊性越强 l o 可视化技术 可视化数据公析技术拓宽了传统的图表功能，使用户对数据的剖析更清晰。 例如：把数据库中的多维数据变成多种图形，这对揭示数据的内涵、内在本质及 4 第一章绪论 规律起了很大的作用。 1 。4 数据挖掘的应用 1 4 1 数据挖掘在零售业的应用 零售业存储了客户购买商品的大量信息，通过这些信息分析客户的行为，才 能体现出收集信息的真正价值。零售业中广泛是使用的p o s 系统所收集的数据 能够回答供应商( 如：c o c a - c o l a ，p e p s i ) 非常希望得到的回答：谁在购买这种品牌? 谁正在买什么? 这种只是使得零售商有能力成为信息中介商。p o s 机最初用途是 纯粹的基于操作上的方便，它的优点是可以集中设置价格，即当价格改变时，不 用对货架上每个商品进行修改。但是，客户对不明确标价的商品一般不会购买， 所以最初集中设置价格的方便没有实现。然而，在增加付账速度，精确定价，库 存控制方面，p o s 机起到很大的作用。p o s 机另外一个重要的作用，开始并没 有被注意到，那就是产生了大量的数据，数量级达到g b t b 。利用这些数据， 建立数据仓库，并利用数据挖掘分析客户的行为时很有意义的。 生活中，我们在超市消费中可以有这样的经验。即超市总是更喜欢消费者持 用超市发行的用户卡结账。原因是这样的，直接用现金消费，则超市p o s 程序 记录的是匿名交易数据；刷卡消费后，超市可以记录有卡的客户信息。 传统的超市发卡记录客户的行为，并不是用来进行数据挖掘的，主要是为了 统计的。比如对于每月花费超过2 0 0 0 元的客户，超市提供一次免费的聚餐。这 种方法有一个缺陷，主要是不针对客户，只针对其在超市固定的花费。对于客户 的月花费有三种类型：一类是客户不管超市如何促销，他们的花费都不超过2 0 0 0 元。第二类是日常月花费总超过2 0 0 0 元，对于这一类客户，免费的聚餐不会构 成吸引。最后一类是客户确实因为此促销活动。使得消费超过2 0 0 0 元。最后一 类客户才是这种策略的真正目的。解决方案是给每一个客户不同的消费目标，这 点统计不能做到。需要使用数据挖掘技术。数据挖掘技术可以对每个客户在花 费的价格和购买的商品上，进行相应的个性化的促销手段。 i b m 公司已采用数据挖掘技术对一些零售商的p o s 数据进行分析，以期发 现一些店内的购物模式。例如。他们对一家年收入2 0 亿，有3 0 0 0 0 0 个u p c 码， 在1 5 个州开设1 2 9 个分店的零售公司的销售信息进行分析后发现了一些有趣的 结果。一位商店总经理解释说，“我们发现人们进入商店后，往往被商店左边的 第一章绪论 促销商品所吸引，实际上并没有在整个店内购物。”这些信息可以用于优化促销 活动，以及优化商店布置参考方案。 1 4 2 数据挖掘在商业银行中的应用 数据挖掘已广泛的应用于银行和金融市场。在银行业。数据挖掘重要用于信 用欺诈的建模与预测、风险评估、趋势分析、收益分析以及辅助直销活动。在金 融市场，已将神经网络用于股票价格预测、购买权交易、债券等级评价、资产组 合管理、商品价格预测、合并和买进以及金融危机预测等方面。 美国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 n m e 能读取8 0 0 - - 1 0 0 0 个变量并且给它们赋值，根据消费者是否 有家庭财产贷款、赊账卡、存款证或其他储蓄、投资产品，将他们分成若干组， 然后使用数据挖掘工具预测何时向每位消费者提供哪种产品。 在银行业，数据挖掘技术应用最为广泛的领域是识别欺诈。h n c 公司的数 据挖掘工具f a l c o n 就是这一应用的代表。他们已宣称从这一领域获得丰厚的回 报。 1 4 3 数据挖掘在电信业的应用 电信业的发展是有目共睹的。从早期提供简单的市话和长话服务。到现在提 供语音、传真、寻呼、移动电话、电子邮件、计算机和w e b 数据传输。电信业 的高速发展和激烈竞争需要使用数据挖掘来辅助商业行为。如：盗用行为每年使 得运行商损失数百万美元。发现潜在的盗用者和他们的使用模式，检测侵入用户 帐户的企图，以及发现需要引起注意的异常模式，这都是非常重要的。这些模式 包括：老是占线无法接入，转化和路由阻塞，从被恶意篡改过的自动拨出设备发 出的周期性呼叫。通过多维分析、聚类分析和孤立点分析，可以发现这些模式。 1 4 4 数据挖掘在生物医学和d n a 数据分析中的应用 过去的几十年，生物医学有了突飞猛进的发展。目前生物医学已经到了分子 的水平，集中于对d n a 数据的分析。d n a 序列表示了生物体的基因代码的基础。 6 第一章绪论 所有的d n a 序列由四个基本模块( 成为核苷) 组成：腺嘌呤( a ) ，胞嘧啶( c ) ， 鸟嘌呤( g ) ，胸腺嘧啶( t ) 。这四个核苷组成很长的序列或链，通常是一个双 螺旋结构。 人体大约有1 0 0 0 0 0 个基因。一个基因通常由成百个核苷按一定次序组织而 成。核苷按不同的次序和序列可以形成不同的基因，基因数目是难以计数的。完 全由人工来找出有意义的基因是几乎不可能完成的。数据挖掘中已经有许多有意 义的序列模式分析和相似检索技术，因此数据挖掘成为d n a 分析中的强有力工 具。例如，比较带病基因和健康基因，找出主要差异。先从两类基因中检索出基 因序列，然后找出并比较每一类中频繁出现的模式。在带病样本中出现频度超过 健康样本的序列被看作是致病因素。反之，被看作是治病因素；大部分疾病不 是单一基因引起的，而是许多基因的共同作用。关联分析方法可以用于找出在目 标样本中同时出现的基因种类。 第二章关联规则的概念 第二章关联规则的概念 关联规则挖掘( a s s o c i a t i o nr u l em i n i n g ) 是数据挖掘研究的一个重要分 支，关联规则是数据挖掘的众多知识类型中最为典型的一种，该问题于1 9 9 3 年 由a g r a w a l 2 等人在对市场购物篮问题( m a r k e tb a s k e ta n a l y s i s ) 进行分析 时首先提出。用以发现商品销售中的顾客购买模式。关联规则挖掘可以发现存在 于数据库中的项目( i t e m s ) 或属性( a t t r i b u t e s ) 间的有趣关系，这些关系是 预先未知的和被隐藏的，也就是说不能通过数据库的逻辑操作( 如：表的连接) 或 统计的方法得出。这说明他们不是基于数据自身的固有属性( 如函数依赖关系， f u n c t i o n d e p e n d e n c yr e l a t i o n ) 。面是基于数据项目的同时出现特征 ( c h a r a c t e r i s t i c so fc o o c c u r r e n c eo fd a t ai t e m s ) 。所发现的关联规则可 以辅助人们进行市场运作( m a r k e t i n g ) 、决策支持( d e c i s i o ns u p p o r t ) 及商业 管理( b u s i n e s sm a n a g e m e n t ) ，网站设计( w e bs i t ed e s i g n ) 。 由于关联规则挖掘形式简洁、易于理解和解释并可以有效的捕捉数据间的重 要关系，因此从大型数据库中挖掘关联规则的问题已经成为近年来数据挖掘研究 领域的一个热点。 2 1 关联规则基本模型 关联规则的基本模型是：设i - - t j ， 2 i 。 是由m 个不同的项目组成的集台。 给定一事务数据库d ，其中每一个事务t 是i 中组项目的集合，即t e l ，t 有 一个唯一的标识符t i d 。若项目集窿l 且x 三t ，则称事务t 包含项目集x 。一 条关联规则的是形如x 等y 的蕴涵式，其中x c i ，y r - i 且x f l y = 巾。如果事务 数据库中有s 的事务包含x 同时也包含y ，那么我们说关联规则的支持度为s ， 如果事务数据库d 中包含x 的事务有c 的事务同时包含y ，那么我们说关联规 则的信任度为c 。例如： c o m p u t e rj f i n a n c i a l _ m a n a g e m e n ts o f t w a r e 【s u p p o n = 2 ，c o n f i d e n c e = 6 0 】 上一规贝| j 的支持度2 意味者分析中的全部事务的2 同时购买计算机和财 务管理软件。置信度6 0 意味购买计算机的顾客6 0 也购买财务管理软件。 关联规则挖掘问题是指从数据库中挖掘出那些支持度和信任度都大于用户 第二章关联规则的概念 指定的最小支持度和最小信任度的关联规则。它可以分为两步：第一步是识别出 所有的频繁集，即支持度不低于最小支持度的项目集，第二步是从频繁集中产生 其信任度不低于最小信任度的规则。第一步的工作最艰巨，因为它需要大量的y o 操作。第二步中规则的生成相对较容易。目前大多数的研究均集中在第一步上。 2 - 2 关联规则与其它学科的关系 与关联规则最相关的三个重要的研究领域是：统计学( s t a t i s t i c s ) 、人工智能 ( a r t i f i c i a li n t e l l i g e n t ) 、数据库( d a m b 船e ) 。关联规则挖掘与统计学和机器学习 的共同特点是：都是从数据集中发现知识。不同点主要是： 统计学的主要任务是用模型匹配数据，描述的是数据自身的固有属性。关联 规则挖掘是找出隐藏在数据中的特性。而且规则的数量大，形式简单。 人工智能( 主要是机器学习的) 的主要任务是发现输入和输出之间的规律和 模型。而关联规则挖掘通常并不硬性的规定哪些项目一定为输入，哪些项目为输 出属性，其作用是发现所有属性闯可能存在的规律。 数据库和关联规则的联系最为密切。因为数据挖掘的对象是数据库或数据仓 库。使用数据库的目的是尽量合理的存储数据，所以它的查询和修改操作不可能 太复杂。使用关联规则的目的是发现数据间隐藏的知识，规律。 2 2 关联规则分类 根据不同的标准关联规则可以有多种分类方法； 根据规则中所处理的值类型：如果规则考虑的关联是项的在与不在，则它 是布尔关联规则( b o o l e a na s s o c i a t i o nr u l e ) 。如： c o m p u t e 漕f i n a c i a | _ m a n a g e m e n t _ _ s o f t w a r e l s u p p o r t = 2 ，c o n 疗d n c e = 6 0 】 如果规则描述的是量化的项或属性之间的关联。则它是置化关联规则 ( 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 ) 。在这种规则中，项或属性的量化值划分为区间。 如： a g e ( x , 3 0 3 9 ”) a i n c o m e ( x ，4 2 k 4 8 k ) 等b u y s ( x , h i g e _ r e s o l u t i o n t v ) 根据规则中涉及的数据维1 ；如果关联规贝j 中的项或属性每个只涉及一个 维，如：b u y s ，则它是单维关联规则( s i n g l e - d i m e n s i o n a s s o c i a t i o nr u l e ) 。如： 按照多维数据库使用的术语规则中的每个不同谓词称为维 9 第二章关联规则的概念 b u y s ( x ， c o m p u t e r ) j b u y s ( x ，”f i n a c i a 一m a n a g e m e n t _ s o f t w a r e ”) 如果规则涉及两个或多个维，如：b u y s ，i n c o m e ，a g 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 s ) 。如： a g e x , 3 0 3 9 ”) 八i n e o m e c x , 4 2 k 4 8 k ) ：，b u y s ( x ， h i g e r e s o l u t i o n j v ) 根据规则集所涉及的抽象层：有些挖掘关联规则的方法可以在不同的抽象 层发现规则，例如挖掘的关联规则集包含下列规则： a g e ( x ，”3 0 3 9 ”) = ，b u y s ( x ，”l a p t o pc o m p u t e r ) a g e ( x ， 3 0 3 9 ”) = ，b u y s ( x ， c o m p u t e r ”) 在上面的两条规则中，购买的商品涉及不同的抽象层( 即”c o m p u t e r 在 比”l a p t o pc o m p u t e r 高的抽象层) 。我们称所挖掘的规贝i j 集由多层关联规则 ( m u l t i l e v e la s s o c i a t i o nr u l e s ) 组成。反之，如果在给定的规贝o 集中，规则不涉 及不同的项或属性，则该集合包含单层关联规则( s i n g l e 1 e v e la s s o c i a t i o nr u l e ) 。 根据关联挖掘的各种扩充：关联挖掘可以扩充到相关分析，那里，可以识 别项是否相关。还可以扩充至n 挖掘最大模式和频繁闭项集。 此外还有许多其它的分类法：如根据数据痒的应用分为：事务数据挖掘( 一 般意义上的关联规则挖掘) ，序列模式挖掘，文本挖掘，w e b 挖掘，多媒体数据 挖掘。生物信息挖掘等。 1 0 第三章经典关联规则算法及变种 第三章经典关联规则算法及变种 3 1a p r i o r i 算法 关联规则最早由r a k e s ha g r a w a l 等人首先提出【2 】，并给出了一个开采关联 规则的算a i s 。比较早的算法还有面向s q l 的变体s e t m 3 。他们在读入交易 时产生候选集，这两种算法的缺点是产生许多不必要的候选项目集，计算量大。 1 9 9 4 年r a s k e s ha g r a w a l 等人提出了最有影响力的a p r i o r i 算法【4 】。a p r i o r i 算法是一种宽度优先的算法，第步扫描数据库时，计算数据库中所有单个项目 的支持度并把大于最小支持度的项目组成1 维频繁项目集，即l l 。然后重复扫 描数据集第k 次扫描时产生长度为k 的频繁项目集即l k ，第( k + 1 ) 次扫 描时，首先从l k 中生成长度为( k + 1 ) 的候选集c k + l ，再在c k + l 中扫描 生成长度为( k + 1 ) 的频繁项目集，即l k + i 。知道无频繁项目集生成为止。最 后的频繁项目集集合为uk ，a p r i o r i 算法的优点在于利用a p r i o r i 性质有效地 剪枝项目集，尽可能不生成和不计算那些不可能生成频繁项目集的候选项目集， 从而生成了较小的候选项目集集合。 a p r i o r i 算法使用如下约定：l k ：k 维频繁项目集的集合，该集合中的每个元素 包含两部分：1 ) 项目集本身，2 ) 项目集的支持度。c k ：k 维候选项目集集台， 是k 维频繁项目集集合的超集，也就是潜在的频繁项目集集合，该集合中的每个 元素也包含两部分：1 ) 项目集本身，2 ) 项目集的支持度。任何项目集的元素都 按照某个标准( 例如字典顺序) 进行排序。包含k 个项目( k 个项目为：e 1 ， “2 ，c k ) 的项目集c 用如下形式来表示：c 1 c 2 - c k ，由于c 已经 排序，所以按照排序准则有：c 1 c 2 c k 。如果c = x y ，y 是一个m 维 项目集，也称y 是x 的m 维扩展。相应地x 为( k m ) 维。 算法a p r i o r i 使用根据候选生成地逐层迭代找出频繁项集 输入：事务数据库d ；最小支持度阈值m i n s u p 输出：d 中的频繁项集 方法： 1 ) l 1 2 f i n d f e q u e n t 一1 i t e m s e t s ( d ) ： 2 ) f o r ( k = 2 ：l 西；k + + ) f 3 ) c k = a p r i o r i g e n ( l k - l 。m i ns u p ) ： 第三章经典关联规则算法及变种 4 )f o re a c ht r a n s a c t i o nte d 5 ) c k ：s u b s e t ( c k ，t ) ： 6 )f o re a c hc a n d i d a t ec c 。 7 )c c o u n t + + ： 8 )l 9 )k = c e c x c c o u n t m i & s u p 1 0 ) 1 1 ) r e t u r n 乙- u l l k ： p r o ca p r i o r i g e n ( l ：f r e q u e n t ( k - 1 ) 一i t e m s e t s ；m i n _ s u p ：m i n i m u ms u p p o r t t h r e s h o l d ) 1 ) f o re a c hi t e m s e t1 tel i - i 2 1f o re a c hi t e m s e t s1 z l 3 )i f ( t 。 1 = l ：( 1 】) a ( 1 。 2 = 1 2 ) a a ( 1 。 k - 2 = 1 k - 2 ) a ( 1 。 k - 1 ； 1 1 )， 1 2 ) l k = c c k | c c o u n t m i n _ s u p ： 1 3 ) ) 1 4 ) a n s w c r = u tl l ： 第三章经典关联规则算法及变种 3 2d h p 算法 a p r i o r i 算法使用l 一的自连接来生成c 。，丽c z 的维数可达到c ：矿当l 很大时， 则c ：的维数将会很大。j s p a r k 等人提出了d h p 5 算法。该算法利用h a s h 技 术来减少l c 。l ，在进行第k 次搜索时生成一个h a s h 表hm 十h a s h 表的每个桶中 保存有桶中包含的项目集的数量以及项目集本身。同时建立一个位向量( b i t v e c t o r ) 对h a s h 表进行过滤，在位向量中只有与至对应的h a s h 表的地址中的项 目数量大于或等于r a i ns u p 的位被设置为1 ，其他位设置为0 ，从而把h a s h 表中 的非频繁集尽可能早地剪掉。d t t p 算法描述如下： 1 ) 把h 2 中的所有桶初始化为0 ； 2 ) f o ra l lt df 3 )i n s e r ta n dc o u n t1 - i t e m so c c u r r e n c e si nah a s ht r e e 4 )f o ra l l2 - s u b s e t sxo f t 5 ) h 2 【h 2 ( x ) 】+ + ； 6 )l 7 ) l i = c c o u n t 一m i n _ s u p ，e 是h a s h 树中的一个叶节点) ； 8 )k = 2 ： 9)dk=d： 1 0 ) w h i l e ( 1 xi h k x 】一 m i n s u p i l a r g e 1 1 ) g e nc a n d i d a t e ( k l ，h k ，c o ； 1 2 ) 把h k + i 的所有桶初始化为0 1 3 ) d k + l = 中： 1 4 ) f o r a l l t d k 1 5 ) c o u n t _ s u p p o r t ( t ，c k ，k ，) ； 1 6 ) i f ( i ，j k ) 1 7 ) m a k e _ h a s h t ( t ，hk ，k ，h k + 1 ，f ) ； 18 ) i f ( i t i k ) t h e n d k + l = d “lu ，) 1 9 ) ) 2 0 ) l k 。 c c kic c o u n t m i n _ s u p 1 4 第三章经典关联规则算法及变种 2 1 )k + + ： 2 2 ) 算法中