摘要 本文介绍关联规则挖掘研究情况提关联规则类些典型算进行析评[1]价指传统关联规则衡量标准足归纳关联规则价值衡量展望关联规则挖掘未研究向
关键词 数据挖掘关联规则频集OLAP
1引言
数据挖掘（Data Mining）称数据库知识发现（Knowledge Discovery in Database）近几已数据库界所广泛研究其关联规则（Association Rules）挖掘重要问题
关联规则发现交易数据库同商品（项）间联系些规则找顾客购买行模式购买某商品购买其商品影响发现规则应用于商品货架设计、货存安排及根据购买模式用户进行类
Agrawal等于1993[1]首先提挖掘顾客交易数据库项集间关联规则问题诸研究员关联规则挖掘问题进行量研究工作包括原算进行优化引入随机采、并行思想等提高算挖掘规则效率；关联规则应用进行推广
近独立于Agrawal频集工作[18,19]避免频集些缺陷探索挖掘关联规则新同随着OLAP技术熟应用OLAP关联规则结合[20,21]重要向些工作[6]注重于挖掘模式价值进行评估提模型建议些值考虑研究向
本文第二部关联规则基本概念介绍提关联规则类；第三部挖掘算介绍经典apriori始描述该算优化拓展接着讲述脱离apriori算层、维关联规则挖掘；第四部归纳关联规则价值衡量主要两面进行考虑：系统客观层面用户主观层面；展望关联规则挖掘未研究向
2关联规则基本概念
2.1基本概念问题描述
设I={i1, i2,…, im}二进制文字集合其元素称项(item)记D交易(transaction)T集合交易T项集合并且TíI 应每交易唯标识交易号记作TID设XI项集合XíT称交易T包含X
关联规则形XTY蕴涵式XìI, YìI并且X?Y=F规则XTY交易数据库D支持度（support）交易集包含XY交易数与所交易数比记support(XTY)即
support(XTY)=|{T:XèYíTT?D}|/|D|
规则XTY交易集信度（confidence）指包含XY交易数与包含X交易数比记confidence(XTY)即
confidence(XTY)=|{T: XèYíTT?D}|/|{T:XíTT?D}|
给定交易集D挖掘关联规则问题产支持度信度别于用户给定支持度(minsupp)信度(minconf)关联规则
2.2 关联规则种类
我关联规则按同情况进行类：
1. 基于规则处理变量类别关联规则布尔型数值型
布尔型关联规则处理值都离散、种类化显示些变量间关系；数值型关联规则维关联或层关联规则结合起数值型字段进行处理其进行态割或者直接原始数据进行处理数值型关联规则包含种类变量
例：性别==>职业=秘书 布尔型关联规则；性别==>avg（收入）=2300涉及收入数值类型所数值型关联规则
2. 基于规则数据抽象层单层关联规则层关联规则
单层关联规则所变量都没考虑现实数据具同层；层关联规则数据层性已经进行充考虑
例：IBM台式机=>Sony打印机细节数据单层关联规则；台式机=>Sony打印机较高层细节层间层关联规则
3. 基于规则涉及数据维数关联规则单维维
单维关联规则我涉及数据维用户购买物品；维关联规则要处理数据涉及维换另句单维关联规则处理单属性些关系；维关联规则处理各属性间某些关系
例：啤酒=>尿布条规则涉及用户购买物品；性别==>职业=秘书条规则涉及两字段信息两维条关联规则
给关联规则类面析程我考虑某具体适用于哪类规则挖掘某类规则用哪些同进行处理
3.关联规则挖掘算
3.1经典频集
Agrawal等于1993[1]首先提挖掘顾客交易数据库项集间关联规则问题其核基于频集理论递推诸研究员关联规则挖掘问题进行量研究工作包括原算进行优化引入随机采、并行思想等提高算挖掘规则效率；提各种变体泛化关联规则、周期关联规则等关联规则应用进行推广
3.1.1核算
Agrawal等[1]1993设计基本算提挖掘关联规则重要 — 基于两阶段频集思想关联规则挖掘算设计解两问题：
1) 找所支持度于支持度项集（Itemset）些项集称频集（Frequent Itemset)
2) 使用第1步找频集产期望规则
第2步相简单点给定频集Y=I1I2...Ikk32Ij∈I产包含集合{I1I2...Ik}项所规则(k条)其每条规则右部项(即形[Y-Ii]TIi"1￡i￡k)采用[4]规则定义旦些规则些于用户给定信度规则才留于规则右部含两项规则其工作进行研究本文面考虑种情况
所频集使用递推其核思想：
(1) L1 = {large 1-itemsets};
(2) for (k=2; Lk-11F; k++) do begin
(3) Ck=apriori-gen(Lk-1); //新候选集
(4) for all transactions t?D do begin
(5) Ct=subset(Ck,t); //事务t包含候选集
(6) for all candidates c? Ct do
(7) c.count++;
(8) end
(9) Lk={c? Ck |c.count3minsup}
(10) end
(11) Answer=èkLk;
首先产频繁1-项集L1频繁2-项集L2直某r值使Lr空算停止第k循环程先产候选k-项集集合CkCk每项集两项同属于Lk-1频集做(k-2)-连接产Ck项集用产频集候选集频集Lk必须Ck集Ck每元素需交易数据库进行验证决定其否加入Lk验证程算性能瓶颈要求扫描能交易数据库即频集包含10项需要扫描交易数据库10遍需要I/O负载
论文[6]Agrawal等引入修剪技术（Pruning）减候选集Ck由显著改进所频集算性能算引入修剪策略基于性质：项集频集且仅所集都频集Ck某候选项集(k-1)-集属于Lk-1则项集修剪掉再考虑修剪程降低计算所候选集支持度代价文[6]引入杂凑树（Hash Tree）效计算每项集支持度
3.1.2频集算几种优化
虽Apriori算自身已经进行定优化实际应用存令满意于相继提些优化
1. 基于划Savasere等[14]设计基于划(partition)算算先数据库逻辑几互相交块每单独考虑块并所频集产频集合并用所能频集计算些项集支持度块选择要使每块放入主存每阶段需扫描算确性由每能频集至少某块频集保证面所讨论算高度并行每块别配给某处理器频集产频集每循环结束处理器间进行通信产全局候选k-项集通通信程算执行间主要瓶颈；另面每独立处理器频集间瓶颈其处理器间共享杂凑树产频集更关于频集并行化[2,11,17]找
2. 基于hash高效产频集基于杂凑(hash)算由Park等[10]提通实验我发现寻找频集主要计算频繁2-项集LkPark等利用性质引入杂凑技术改进产频繁2-项集
3. 基于采基于前遍扫描信息仔细作组合析改进算Mannila等[8]先考虑点认采发现规则效途径随由Toivonen[16]进步发展思想先使用数据库抽取采些整数据库能立规则数据库剩余部验证结Toivonen算相简单并显著减少I/O代价缺点产结精确即存所谓数据扭曲(data skew)布同页面数据高度相关能能表示整数据库模式布由导致采5%交易数据所花费代价能同扫描遍数据库相近LinDunham[7]讨论反扭曲(Anti-skew)算挖掘关联规则引入技术使扫描数据库数少于2算使用采处理收集关数据数减少扫描遍数
Brin等[4]提算使用比传统算少扫描遍数发现频集同比基于采使用更少候选集些改进算低层效率具体考虑计算k-项集旦我认某(k+1)-项集能频集并行计算(k+1)-项集支持度算需要总扫描数通少于频集项数使用杂凑技术并提产相关规则（Correlation Rules）新基于[3]工作基础
4. 减少交易数减少用于未扫描事务集基本原理事务包含度k项集则必包含度k+1项集我些事务移遍扫描要进行扫描事务集数AprioriTid基本思想
3.2其频集挖掘
面我介绍都基于Apriori频集即使进行优化Apriori些固缺陷克服：
1) 能产量候选集度1频集10000候度2候选集数超10M要规则候要产间元素巨量
2) 稀信息进行析由于频集使用参数minsup所于minsup事件进行析；minsup设低值算效率难处理问题
面介绍两种别用于解决两问题
[18]提解决问题1种采用种FP-growth采用治策略：经第扫描数据库频集压缩进棵频繁模式树（FP-tree）同依保留其关联信息随我再FP-tree化些条件库每库度1频集相关再些条件库别进行挖掘原始数据量候结合划,使FP-tree放入主存实验表明FP-growth同度规则都适应性同效率较apriori算巨提高
第二问题基于想：apriori算关系都频繁现实际应用我能需要寻找些高度相关元素即使些元素频繁现apriori算起决定作用支持度我现信度放第位挖掘些具非高信度规则[19]介绍于问题解决整算基本三步骤：计算特征、候选集、滤候选集三步骤关键计算特征Hash使用考虑候几衡量坏指数：空效率、错误率遗漏率基本两类：Min_Hashing(MH)Locality_Sensitive_Hashing(LSH)Min_Hashing基本想：条记录k1字段位置作Hash函数Locality_Sentitive_Hashing基本想：整数据库用种基于概率进行类使相似列起能性更相似列起能性较我再两比较MH遗漏率零错误率由k严格控制空效率相较差LSH遗漏率错误率同降低空效率却相所应该视具体情况定实验数据说明种确能产些用规则
3.3层维关联规则挖掘
随着数据仓库OLAP技术研究深入预见量数据经整合、预处理存入数据仓库前数数据仓库应用都进行统计、建立维及OLAP析工作随着数据挖掘研究深入已经OLAP数据挖掘相结合[20,21]
首先效数据挖掘应该进行探索性数据析用户往往希望能数据库穿行选择各种相关数据同细节层进行析各种同形式呈现知识基于OLAP挖掘提供同数据集、同细节挖掘进行切片、切块、展、滤等各种规则操作再加些视化工具能提高数据挖掘灵性能力接着我看层维关联规则定义
层关联规则：
于应用说由于数据布散性所难数据细节层发现些强关联规则我引入概念层较高层进行挖掘虽较高层规则能更普通信息于用户说普通信息于另用户却未必所数据挖掘应该提供种层进行挖掘功能
层关联规则类：根据规则涉及层层关联规则同层关联规则层间关联规则
层关联规则挖掘基本沿用支持度-信度框架支持度设置问题些要考虑东西
同层关联规则采用两种支持度策略：
1) 统支持度于同层都使用同支持度于用户算实现说都比较容易弊端显
2) 递减支持度每层都同支持度较低层支持度相较同利用层挖掘信息进行些滤工作
层间关联规则考虑支持度候应该根据较低层支持度定
维关联规则：
我研究基本都同字段值间关系比用户购买物品用维数据库语言单维或者叫维内关联规则些规则般都交易数据库挖掘于维数据库言类维关联规则例：
龄（X20...30）ù职业（X,）==> 购买(X笔记本电脑)
我涉及三维数据：龄、职业、购买
根据否允许同维重复现细维间关联规则（允许维重复现）混合维关联规则（允许维规则左右同现）
龄（X20...30）ù购买(X笔记本电脑) ==> 购买(X打印机)
规则混合维关联规则
挖掘维间关联规则混合维关联规则候要考虑同字段种类：种类型数值型
于种类型字段原先算都处理于数值型字段需要进行定处理才进行处理数值型字段基本几种：
1) 数值字段些预定义层结构些区间都由用户预先定义规则叫做静态数量关联规则
2) 数值字段根据数据布些布尔字段每布尔字段都表示数值字段区间落其则1反0种态规则叫布尔数量关联规则
3) 数值字段些能体现含义区间考虑数据间距离素规则叫基于距离关联规则
4) 直接用数值字段原始数据进行析使用些统计数值字段值进行析并且结合层关联规则概念层间进行比较些用规则规则叫层数量关联规则
OLAP挖掘层、维关联规则自程OLAP本身基础层维析工具没使用数据挖掘技术前OLAP能做些简单统计能发现其些深层关系规则我OLAPDataMining技术结合起形新体系OLAM（On-Line Analytical Mining）[20]
4关联规则价值衡量
我用数据挖掘算些结数据挖掘系统何知道哪些规则于用户说用、价值两层面：用户主观层面系统客观层面
4.1系统客观层面：
算都使用支持度-信度框架结构产些错误结看例：
假设提供早餐零售商调查4000名早晨进行运结2200名打篮球2750名晨跑1800名打篮球、晨跑设minsup40%minconf60%我关联规则：
打篮球T晨跑 （1）
条规则其实错误晨跑比例68%甚至于60%打篮球晨跑能否定关联即我考虑关联：
打篮球T（）晨跑 （2）
虽条规则支持度信度都比条蕴涵向关联规则（1）低更精确 我支持度信度设足够低我两条矛盾规则另面我些参数设足够高我能精确规则总没支持度信度组合产完全确关联
于引入兴趣度用修剪趣规则即避免错觉关联规则般条规则兴趣度基于统计独立性假设真强度与期望强度比许应用已发现要仍支持度作初项集产主要决定素要支持度设足够低使丢失任何意义规则或者冒丢失些重要规则风险；前种情形计算效率问题种情形则能丢失用户观点看意义规则问题
[12]作者给兴趣规则定义（R-interesting）[13]作改进[10]事件依赖性统计定义扩展兴趣度定义；[15]定义否定关联规则兴趣度
除兴趣度作修剪价值规则工具现已许其工作重新认识项集Brin等[3]考虑相关规则[4]讨论蕴涵规则(implication rule)规则蕴涵强度[0,￥]间变化其蕴涵强度1表示完全关规则￥表示完备规则蕴涵强度于1则表示更期望存性
另度量值——收集强度(collective strength)[22]定义设想使用于期望值发现意义关联规则项集收集强度[0,￥]间数值其0表示完备否定相关性值￥表示完备相关性详细讨论[10]找
4.2用户主观层面：
面讨论基于系统面考虑规则用与否终取决于用户觉用户决定规则效性、行性所我应该用户需求系统更加紧密结合起
采用种基于约束(consraint-based)[21]挖掘具体约束内容：
1) 数据约束用户指定哪些数据进行挖掘定全部数据
2) 指定挖掘维层用户指定数据哪些维及些维哪些层进行挖掘
3) 规则约束指定哪些类型规则我所需要引入模板（template）概念用户使用确定哪些规则令兴趣哪些则：条规则匹配包含模板（inclusive template）则令兴趣条规则匹配限制模板（rextrictive template）则认缺乏兴趣
其些条件算紧密结合即提高效率使挖掘目更加明确化其：
Kleinberg等工作希望建立套理论判断所模式价值认问题仅能微观经济框架解决模型提发展向引入并研究新优化问题——段(Segmentation)问题框架包含些标准组合类问题模型根据基本目标函数挖掘数据价值提供特殊算视角显示面导具体优化问题广泛应用领域
[5]Korn等利用猜测误差(使用均根定义)作些给定数据集所发现规则处(goodness)度量所定义比例规则规则：
顾客数别花费 1 : 2 : 5钱面包:牛奶:奶油
通确定未知(等价隐藏丢失)值比例规则用作决策支持
转载
-
内容全部来源于网络收集，如有侵权，请联系网站删除：QQ：24596024