负关联规则（精选5篇）
负关联规则 篇1
关联规则最初是由RakeshAgrawal等人于1993年于文献[1]首次提出来的, 它是数据挖掘的重要技术之一。传统的关联规则, 主要用于挖掘顾客事务数据库中项集间的关系, 即形如A≥B的高频率、强相关规则, 我们称之为正关联规则, 是一种强相关的显示模式, 其挖掘算法已有很多[2—7]。实际上数据库中还存在许多采用这些挖掘技术所不能发现的隐式模式, 它具有低频率、强相关的性质, 表现了数据项目集间不易直接发现的强相关性质, 这些隐式规则告诉我们哪些数据项目较少地发生, 但它们之间有着相当强的相关性, 包含了非常有价值的信息。这些隐式模式之一便是负关联规则, 如形如A∪┓B、┓A∪B、┓A∪┓B的规则。发现负关联规则有着十分重要的意义, 如购物篮分析中, 那些被顾客经常一起购买的商品X和Y、那些很少被顾客一起购买的商品X′和Y′, 对于决策人员决定如何摆放商品起着同等重要的作用。
目前用于负关联规则挖掘算法不太多, 如文献[9]提出了一种基于位矩阵的负关联规则挖掘算法, 文献[10]提出了一种基于兴趣度的正负关联规则挖掘算法, 文献[11]提出了一种基于支持度、置信度、关联系数的正负关联规则挖掘算法, 文献[12]提出了一种基于序列模式的正负关联规则。研究负关联规则难度大的主要原因是负关联规则的搜索空间比正关联规则的搜索空间要大得多, 其搜索空间呈指数级增长。因为数据挖掘面对的是海量数据, 而关联规则是在项集中找出各项目出现的规律。如某百货商场有1 000种商品, 事务数据库D中频繁项目集的个数大约为250, 则在D中非频繁项目集个数高达 (21 000—250) , 接近于21 000, 因此想要求出所有这些非频繁项目集的支持数是不现实的, 也是无意义的[8]。本文给出一种负关联规则的算法用以实现事务数据库D中的负关联规则。
1 负关联规则描述
定义1 设I={i1, i2, …, im}是项的集合, 其中的元素称为项 (item) 。记D为事务T的集合, 这里事务T是项的集合, 且T⊆I。对应每一个事务有唯一的标识符 (tid) 。设A是I中项的一个集合, 如果A⊆T, 那么称事务T包含A。
一个关联规则是形如A=>B的蕴涵式, 这里A⊆I, B⊂I, 并且A∩ B=Φ。A称为规则的体 (Body) , B称为规则的头 (Head) 。
规则A≥B在事务数据库D中的支持度 (support) 是事务集中包含A和B的事务数与所有事务数之比, 记为support (A=>B) 或support (A∪B) , 即:
Support (A=>B) = support (A∪B) =∣{T: A∪B⊆T, T∈D}∣/∣D∣。
规则A=>B在事务集中的可信度 (confidence) 是指包含A和B的事务数与包含A的事务数之比, 记为confidence (A=>B) , 即:
Confidence (A=>B) =∣{T: A∪B⊆T, T∈D}∣/∣{T: A⊆T, T∈D}∣。
给定一个事务集D, 挖掘关联规则问题就是产生支持度和可信度分别大于用户给定的最小支持度 (minsupp) 和最小可信度 (minconf) 的关联规则。该问题可划分为两个子问题: (1) 找出存在于事务数据库中的所有支持度大于最小支持度的项集, 这些项集称为频繁项集或大项集, 此步为算法的核心, 挖掘关联规则的总体由它决定。 (2) 利用第 (1) 步找到的频繁项集产生关联规则。
定义2 对于给定的项集A、B, 其中A∩B=Φ, A、B间共有8种关联规则
(1) A=>B, (2) A=>┓B, (3) ┓A=>B,
(4) ┓A=>┓B, (5) B=>A, (6) B=>┓A,
(7) ┓B=>A, (8) ┓B=>┓A。
称 (1) 为正关联规则, (2) ～ (4) 为负关联规则, 它表示项目集中的否定联系, 其中 (5) ～ (8) 是和 (1) ～ (4) 相对应的, 只是将 (1) ～ (4) 中的字母A与B交换, 这里不予讨论。
一个有效的负关联规则必须满足以下三个条件
(1) A∩B=Φ;
(2) supp (A) ≥minsupp且supp (B) ≥minsupp
(3) supp (A∪┓B) ≥minsupp
或supp (┓A∪B) ≥minsupp
或supp (┓A∪┓B) ≥minsupp。
负关联规则中包含有不存在的项集 (如┓A, ┓B) , 直接计算它们的支持度及可信度比较困难, 可利用项集A、B的支持度及可信度来计算, 文献[13]已有相应结论:
定理1 设A, B⊂I, A∩B=Φ, 则有
(1) supp (┓A) =1-supp (A) ;
(2) supp (A∪┓B) =supp (A) -supp (A∪B)
(3) supp (┓A∪B) =supp (B) -supp (A∪B)
(4) supp (┓A∪┓B) =1-supp (A) -supp ( B) +supp (A∪B)
推论1 设A, B⊂I, A∩B=Φ, 则有
(1) conf
(2) conf
若要考虑负关联规则的挖掘问题, 先要解决规则中的一个矛盾问题, 如A表示顾客会买葡萄, B表示顾客会买香蕉, 若规则conf (A=>B) ≥minconf和conf (A=>┓B) ≥minconf同时成立, 这显然是一个矛盾, 即买葡萄=>买香蕉与买葡萄=>不买香蕉同时成立。
对于正负关联规则中的矛盾规则的出现, 可利用关联规则的相关性进行避免。关联规则的相关性在文献[14]中进行了定义, 项集A和B的相关性可由公式:
通过CorrA, B可以判断A, B的相关性情况:
如果CorrA, B>1, 那么A和B正相关;
如果CorrA, B=1, 那么A和B相互独立;
如果CorrA, B<1, 那么A和B负相关。
项集A和B的相关性有这样的关系:如果CorrA, B>1, 则有CorrA, ┓B<1;Corr┓A, B<1;Corr┓A, ┓B>1;反之亦相反。因此在挖掘正负关联规则时只要对项集的相关性进行判断就可避免矛盾规则的出现, 即当CorrA, B>1时仅挖掘A=>B和┓A=>┓B;当CorrA, B<1时仅挖掘┓A=>B和A=>┓B;当CorrA, B=1时不挖掘规则。
2 算法及实现
在本算法中, 事务T所对应的二进制数为:b=b1b2…bm-1bm, 记为Bt, 其中bj∈{0, 1}, 且如果ij∈T, 则bj=1, 否则bj=0, j=1, 2, …, m。
算法:PN_MAR
输入:事务数据库D;最小支持度minsupp;最小可信度minconf。
输出:正关联规则集合PS;负关联规则集合NS
方法:
3 结束语
对于负关联规则的算法, 目前本来就不多, 本文采用链表来实现正负关联规则的挖掘算法, 采用二进制数的方式来表示事务是否包含项集中的元素, 用以提高执行效率。对于负关联规则还有更多的问题待我们去研究: (1) 如何优化其搜索空间; (2) 利用相关度对规则挖掘作更深入地研究; (3) 负关联规则中, Apriori算法的移置及改进问题等等。
摘要：传统的正关联规则主要考虑事务中所列举的项目, 负关联规则不仅要考虑事务中所包含的项目, 还要考虑事务中所不包含的项目, 它包含了非常有价值的信息。本文对负关联规则的相关定义、支持度及置信度的计算方法进行了分析讨论, 并讨论了对负关联规则挖掘中出现的矛盾规则问题及利用规则相关性解决矛盾规则问题, 最后给出了其挖掘算法及其实现。
关键词：数据挖掘,负关联规则,频繁项集
负关联规则 篇2
第一章
总则
第一条 为明确关联交易委员会的工作职责、工作程序和方法，根据公司《关联交易管理办法》和有关规定，特制订本规则。
第二章
组织机构和职责
第二条 组织机构
关联交易委员会为公司董事会下设机构，对公司董事会负责。
关联交易委员会委员设主任1人，委员2人，均由董事会成员担任。其中主任委员由公司独立董事担任；关联交易委员会办公室设在合规风控部。
第三条 主要职责
（一）依照法律、法规和政策的要求制定完善公司的关联交易规则、操作规程和管理办法；
（二）在董事会领导下对关联方进行认定，对关联交易行为进行界定，对其合法性、合规性和公平性进行审核；
（三）组织确定关联交易定价方法、定价标准；
（四）在董事会领导下对涉及关联交易的各类业务进行审批。
第三章
议事规则
第四条 关联交易委员会建立关系人回避制度，凡参与被审查关联交易的前期调查的人员以及与该关联交易的关联方有密切关系的公司高级管理人员及其直系亲属控制的公司的高级管理人员不得在该笔关联交易的审查会议上发表决策意见。
关系人回避分为自行回避和指令回避。自行回避指参与被审查关联交易前期调查的人员主动提出回避。指令回避指参与被审查关联交易前期调查的人员未主动提出回避时，关联交易委员会主任有权做出决定，指令相关人员回避。
第五条 会议召开
关联交易委员会会议由主任召集并主持（主任不能出席时可委派一名委员主持），由关联交易委员会办公室具体负责安排会议场所，并通知各委员。
第六条 会议应由三分之二以上的委员出席方可举行。
第七条 委员因故不能出席会议，可委托一名代表出席。受委托出席会议的代表享有表决权。
第八条 会议程序
会议召开由主任委员主持。委员有权就会议议程提出建议，以书面形式在会议召开前提交。
负责前期调查的人员将项目尽职调查情况向各委员做出汇报，各委员对项目调查报告中的关联方情况、定价原则、定价依据、定价方法、交易金额及与该关联方的交易余额等内容进行审查，对关联交易的公正性、合法合规性研究审核，发表意见并形成决议。
第九条 委员会秘书须将每次会议内容形成会议记录和《关联交易委员会关联交易审批表》，由委员会成员会签后，呈报主任委员签批，秘书负责将相关资料存档。
第十条 委员会可采取信函、传真、电子邮件等非会议形式讨论有关议题并做出决议。
第十一条 表决
每一委员有一表决权。委员会通常以举手的方式进行表决。
第十二条 重大关联交易由关联交易委员会以会议表决的方式审批，非重大关联交易可以采取会议表决或会签方式审批，决议须经出席会议的委员三分之二以上通过。
第十三条 委员会主任对关联交易享有一票否决权。
第十四条 每笔关联交易除进行关联交易审查之外，仍须履行投资决策审查和风险控制审查程序。涉及投资的关联交易还应当由具体业务部门进行项目可行性研究和论证，并经投资决策委员审查批准。
第四章
附则
第十五条 本规则由董事会负责解释和修改。
第十六条
负关联规则 篇3
关键词：精神卫生,行为,成瘾,计算机通信网络,病例对照研究,学生
事件相关电位(ERP)是一种特殊的脑诱发电位,指当人们对某课题进行认知加工时,从头颅表面记录到的脑电位。它反映了认知过程中大脑的神经电生理的变化,也被称为认知电位。失匹配负波(mismatch negativity,MMN)由Naatanen等[1]于1978年首先报道,近年开始研究应用于精神神经疾病,反映了大脑对外界刺激信息的自动加工过程[2]。关联性负变(contingent negative variation,CNV)与情感性精神障碍存在密切关联,与人脑对事件的准备、期待、注意、动机等心理活动密切相关,是研究精神病理学和心理生理功能的可靠工具。本研究观察了互联网成瘾综合征(IAD)患者MMN及CNV 2种ERP的变化,现报道如下。
1 对象与方法
1.1 对象 研究病例来源于2008-2009年成都中医药大学附属医院、华西西区医院物质依赖门诊、西南财经大学、成都中医药大学学生,按照1997年美国心理学年会形成并公认的IAD诊断标准[3]筛选出80名符合纳入标准的IAD患者进入临床试验。在获取知情同意后,按就诊顺序编号,其中男47例,女33例,平均年龄(22.04±2.27)岁,平均网龄(4.58±2.19)a,平均上网时间(6.14±2.15)h。
另设40例健康志愿者作为正常对照组,其中男17例,女23例,平均年龄(21.73±1.32)岁,平均网龄(4.45±1.72)a,平均每天上网时间(3.10±1.61)h。
经统计学分析,IAD患者上网时间与正常组相比差异有统计学意义(P<0.05),年龄、网龄、性别差异均无统计学意义(P值均>0.05)。
1.2 方法
1.2.1 诊断标准 按1997年美国心理学年会形成并公认的IAD诊断标准[3]进行,即患者在1 a内表现出下列7种情况的3种以上症状即可确诊为IAD:(1)耐受性,指符合需要明显增加上网时间才能获得满足或上网时间不变但满足感明显下降中的任意1项;(2)停止上网后,表现出显著的脱瘾综合征或急于使用网络或相似的网上服务来减轻或避免脱瘾症状中的任意1项;(3)上网的次数比计划的多,时间比计划的长;(4)一直希望能努力减少或控制网络的使用,但却没有成功;(5)把大量的时间用在与使用网络有关的事情上,如购买网络书籍、尝试新的浏览器、整理下载的资料;(6)因为使用互联网而放弃或减少重要的社交、工作或娱乐活动;(7)尽管知道上网可能已经导致了持续或复发性的身体、社交、工作或心理问题,但仍不管这些情况而继续使用互联网。
排除:(1)以往患有严重躯体疾病或其他精神疾病;(2)以往经过心理和药物治疗;(3)有药物成瘾病史;(4)左利手或听力、视力异常。
1.2.2 检测方法 采用美国Nicolet Spirit脑电生理仪,按国际10/20脑电记录系统安置电极,记录电极置Cz部位,A1和A2耳电极,前额正中央置接地电极,使用Ag/AgCI电极。测定MMN及CNV的潜伏期及波幅:(1)MMN标准刺激为500 Hz,80 dB的纯音,出现概率为0.8;偏差刺激为2 000 Hz,85 dB的纯音,出现概率为0.2。刺激间隔固定在1 s。1轮试验中2种刺激出现的总数为200次,试验不要求被试默记偏差刺激。脑电活动伪迹由仪器自动排除。(2)CNV诱发刺激模式由S1和S2组合而成,S1为1 000 Hz短音刺激,属于提示信号;S2为红色圆点图片,属于命令信号。受试者接受到S1后,开始期待S2的出现,一旦接受到S2后立即做出按键反应以中断S2。S1与S2之间间隔为15 s,S2与下一个S1之间间隔3~8 s(随机),每一轮叠加18次,共2轮。2轮之间间隔30 s。每个导联ERPs记录被分别叠加,叠加的时间区段S1刺激呈现前500 ms至S2刺激呈现后1 000 ms,并取刺激呈现前200 ms的电压值作为基线。S1至S2之间向上的波形为命令信号前负向期待波,S2至0点为命令信号后负变化。
患者在接受事件相关电位检测前12 h禁饮酒、茶、咖啡,保证足够睡眠。检查时间为9:00-11:00,检测在屏蔽隔音室中进行,受试者平卧于床上,全身放松,保持觉醒状态及注意力集中,由电生理检测室专职医生检测,同一机器进行操作。
1.2.3 分析指标 (1)MMN:潜伏期和波幅。由偏差刺激诱发的认知电位(CP)减去标准刺激诱发的CP,将得到的波形中位于潜伏期100~200 ms范围内的最大负相波确认为MMN。MMN潜伏期指刺激开始到MMN时间范围内的最大峰波幅值点横轴的直线距离;其波幅为基线到波峰的垂直距离[4]。(2)CNV:因CNV波幅在头皮记录时以中央区波幅最高,故以Cz的CNV波形为分析指标。主要观察指标:命令信号前负期待波(Expectancy Wave, EW)。①潜伏期(ms)。EW起点(S1 A)、A-S2'时程;②波幅(μV)。S1后500~600 ms或S2前50~100 ms的Amp(自基线起算);③面积(基线上方曲线的面积,μV×ms):EW面积 ( A-S2', S2'-C);④PINV时程延长或C点不能回到基线出现率。命令信号后负变化(post imperative negative variation, PINV)即S2刺激后偏转至基线的这部分负相电位,唤醒水平过度增高可引起PINV时程延长或C点不能回到基线[5]。
1.3 统计分析 所得数据进行双盲处理后录入计算机,采用SPSS 17.0统计软件包进行统计学处理。计量资料数据均以均数±标准差undefined表示,服从正态分布者采用t检验,非正态分布者采用秩和检验。C点未回到基线出现率采用χ2检验。
2 结果
2组MMN潜伏期差异无统计学意义(P>0 05);IAD组MMN波幅较正常组降低,差异有统计学意义(P<0.01);A潜伏期、A-S2' 潜伏期、B波幅、A-S2' 波面积2组间差异均无统计学意义(P值均>0.05)。正常组PINV时程延迟出现率(7.50%)与IAD组(13.75%)比较,差异无统计学意义(χ2=0.50,P>0.05)。
3 讨论
网络成瘾是在没有致瘾物情况下的行为失控。IAD患者在精神上表现为对网络的无比向往和强烈的、不可遏制的追求,驱使其连续地或周期性地上网,以获得心理上的满足,产生特殊的欣快感和欢愉舒适的内心体验[6]。患者下网后往往因烦躁、焦虑、失眠等戒断症状再度上网。
Donchin等[7,8]对事件相关电位的形成提出如下理论:从环境来的信息被大脑接受后都是以表征的形式存储在大脑的庞大信息库中,成为记忆的内容。接受新的刺激后,新信息在认知加工时将受到与其有关的旧的表征的作用,并整合到原有的表征中去形成新的表征。全部与新信息有关的表征被称为场合。新信息的加工过程同时也修正了原来的场合,更新了信息库,即增加和更新了记忆的内容。在事件相关电位检查中,峰潜伏期代表从刺激→认知加工过程的耗时,峰潜伏期越短,则从刺激→认知加工过程的耗时越短。波幅大小代表场合修正的量,波幅越大,场合修正的量越多,内容被记住的可能性越大。
MMN反映大脑对刺激的物理特征改变所作的认知加工,不受意识控制,对刺激偏离敏感。MMN潜伏期表示大脑对外部刺激进行分类、编码、识别的速度;波幅反映的是大脑在对信息加工时有效资源动员的程度。罗庆华[9]发现,网络成瘾者的认知功能是有明显损害的。笔者研究结果显示,IAD组MMN潜伏期与正常组差异无统计学意义,MMN波幅显著降低。提示IAD患者对信息加工时有效资源动员降低,获取外界信息的有效性下降,需要代偿性处于高度警觉状态以获取足够的信息,从而外现为警惕性增高和焦虑等症状。
CNV是ERP中一种经典方法[10],是目前捕捉、分析与心理活动相关的脑电波的重要手段之一,通过标准化的过程(S1-S2运动反应)所形成的稳定慢电位,在特定刺激的条件下产生的诱发脑电活动,与期待、注意、唤醒、记忆、动机、准备和决定等心理活动关系十分密切,并与被试者的学习和特定警告对其的暗示性、集中程度有关。A点潜伏期为进入准备的时间, B波幅反映对感觉或运动的准备程度。IAD患者存在不同程度的焦虑、抑郁情绪。有研究表明,分心干扰、焦虑状态均可使CNV波幅降低[11,12]。但本次研究结果显示,IAD组的CNV的A点和A-S2' 潜伏期、B点波幅、A-S2' 波面积及C点未回基线出现率等指标,与正常组比较差异均无统计学意义(P值均>0.05)。提示网络成瘾对在校大学生IAD患者认知功能产生的影响并不显著。
本研究虽然发现IAD患者ERP存在一定程度的异常,但由于样本量偏少,且都为在校大中专学生,故结果可能存在一定的局限性。今后对IAD患者ERP改变的研究还有待于扩大样本量,以期进一步了解IAD患者发病的神经电生理机制,从而为IAD的诊断和治疗提供更加客观科学的依据。
参考文献
[1]NATANEN R,PAVILAINEN P,TITINEN H,et al.Attention and mis-match negativity.Psych Physiol,1993,30(6):436-439.
[2]OGURA C,KOGA Y,SHIMOKOCHI M.Recent advances in event-related brain potential research.Amsterdam:Elsevier,1996:1015-1054.
[3]江楠楠,郭培芳.国外对因特网成瘾的研究.心理科学,2003,1(1):178.
[4]李兴启.听觉诱发反应及应用.北京:人民军医出版社,2007:198-200.
[5]潘映福.临床诱发电位学.北京:人民卫生出版社,1998:580-584.
[6]杨容,郑涌,阮昆良.网络成瘾(IAD)实证研究进展.西南师范大学学报:人文社科版,2004,30(5):40-43.
[7]DONCHIN E,HEFFLEY E,HILLYARD S,et al.Cognition and en-vent-related potentialsⅡ.The orienting reflex and P300.Ann N YAcad Sci,1984,425(1):39.
[8]KRAMER AF,DONCHIN E.Bra in potential as indices of orthogo-giaphic and phonological in teraction during word matching.J ExpPsychol Learn Mem Cogn,1987,13(1):76-78.
[9]罗庆华.中学生网络成瘾的研究.重庆:重庆医科大学,2005
[10]沈渔邨.精神病学.长春:长春出版社,2000:78-91.
[11]HIRUMA T,SATO Y,YABE H,et al.Attentional distraction ofCNV depending on the spatial focus.Electroencephalog Nneurophysi-ol,2004,35(3):132-136.
关联规则挖掘研究 篇4
关联规则是发现交易数据库中不同商品(项)之间的联系,这些规则找出顾客购买行为模式,如购买了某一商品对购买其它商品的影响。发现这样的规则可以应用于商品货架设计、货存安排以及根据购买模式对用户进行分类。
关联规则是关联分析中的一种常用技术。关联规则是寻找在同一个事件中出现的不同项的相关性。其形式如下[1]。
设L=邀i1,i2,...im妖是所有项的集合。D是交易集合,其中每个交易T是一个项的集合并且T哿L。每一个交易T都有一个唯一的标识TID。如果项集合X哿L且X哿T,则交易T包含X。一个关联规则就是这样一种形式的关系:X==>Y,其中X奂L,Y奂L,并且X∪Y=φ。
另外两个和关联规则有关的概念是支持度和可信度。
根据文献[1]的定义,对于一个关联规则X==>Y,在交易集合D中,Txy=邀T|(X∪Y)哿T∩T∈D妖,Tx=邀T|X奂T∩T∈D妖,支持度为s,|Txy|/|D|=s%;可信度为c,|Txy|/|Tx|=c%。
举例说明,有一个特定的关联规则,锤子==>钉子,这个规则可能意味着买锤子的人也有倾向买钉子。有10000条交易记录的交易数据库中,若有300条记录既包含了锤子又包含了钉子,则关联规则的支持度为300/10000=3%,这个支持度是比较高的,但并不能就此作出这个关联有意义的结论。但是假如只有600人购买了锤子,则其中有一半的人又去购买了钉子,这个现象就值得关注了。
另一个更详细的例子来自于文献[2]:
总交易笔数:1000;
包含“锤子”:50;
包含“钉子”:80;
包含“钳子”:20;
包含“锤子”和“钉子”:15;
包含“钳子”和“钉子”:10;
包含“锤子”和“钳子”:10;
包含“锤子”,“钳子”和“钉子”:15。
则可以计算出:
“锤子和钉子”的支持度=1.5%(15/1000);
“锤子,钉子和钳子”的支持度=0.5(5/1000);
“锤子==>钉子”的可信度=30%(15/50);
“钉子==>锤子”的可信度=19%(15/80);
“锤子和钉子==>钳子”的可信度=33%(5/15);
“钳子==>锤子和钉子”的可信度=25%(5/20)。
数据挖掘得到的关联规则,只是对数据库中数据之间相关性的一种描述。还没有其它数据来验证规则的正确性。
除了支持度和可信度外关联规则评价标准还有改善度和兴趣度。
2 关联规则的种类
(1)基于规则中处理的变量的类别,分为布尔型和数值型。布尔型关联规则处理的值都是离散的、种类化的,显示了这些变量之间的关系;而数值型关联规则可以和多维关联或多层关联规则结合起来,对数值型字段进行处理,将其进行动态的分割,或者直接对原始的数据进行处理,当然数值型关联规则中也可以包含种类变量。例如:性别=“女”=>职业=“秘书”,是布尔型关联规则;性别=“女”=>avg(收入)=2300,是一个数值型关联规则。
(2)基于规则中数据的抽象层次,分为单层关联规则和多层关联规则。在单层的关联规则中,所有的变量都没有考虑到现实的数据是具有多个不同层次的;而在多层的关联规则中,对数据的多层性已经进行了充分的考虑。例如:IBM台式机=>Sony打印机,是一个细节数据上的单层关联规则;台式机=>Sony打印机,是一个较高层次和细节层次之间的多层关联规则。
(3)基于规则中涉及到的数据维数,分为单维的和多维的。在单维的关联规则中,只涉及到数据的一个维,如用户购买的物品;而在多维的关联规则中,要处理的数据将会涉及多个维。换句话说,单维关联规则是处理单个属性中的一些关系;多维关联规则是处理各个属性之间的某些关系。例如:啤酒=>尿布,这条规则只涉及到用户购买的物品;性别=“女”=>职业=“秘书”,这条规则就涉及到两个字段的信息,是两个维上的一条关联规则。
给出了关联规则的分类之后,在分析过程中,就可以考虑某个具体的方法适用于哪一类规则的挖掘,某类规则又可以用哪些不同的方法进行处理。
3 关联规则挖掘的算法
3.1 经典频集方法
Agrawal等于1993年首先提出了挖掘顾客交易数据库中项集间的关联规则问题[3],其核心方法是基于频集理论的递推方法。以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。其工作包括对原有的算法进行优化,如引入随机采样、并行的思想等,以提高算法挖掘规则的效率;提出各种变体,如泛化的关联规则、周期关联规则等,对关联规则的应用进行推广。
(1)核心算法Agrawal等设计了一个基本算法[3],提出了挖掘关联规则的一个重要方法,将关联规则挖掘算法的设计分解为两个子问题:(1)找到所有支持度大于最小支持度的项集,这些项集称为频集;(2)使用(1)找到的频集产生期望的规则。
(2)频集算法的几种优化方法:(1)基于划分的方法;(2)基于hash的方法;(3)基于采样的方法;(4)减少交易的个数。
3.2 其它的频集挖掘方法
前面介绍的都是基于Apriori的频集方法。即使进行了优化,Apriori方法一些固有的缺陷还是无法克服。
(1)可能产生大量的候选集。当长度为1的频集有1-0000个的时候,长度为2的候选集个数将会超过10M。当要生成一个很长的规则的时候,要产生的中间元素也是巨大量的。
(2)无法对稀有信息进行分析。由于频集使用了参数minsup,因此就无法对小于minsup的事件进行分析;如果将minsup设成一个很低的值,那么算法的效率将很难处理。
4 结束语
关联规则可以在下面一些方向上进行深入研究:在处理极大量的数据时,如何提高算法效率的问题;对于挖掘迅速更新数据的挖掘算法的进一步研究;在挖掘的过程中,提供一种与用户进行交互的方法,将用户的领域知识结合在其中;对于数值型字段在关联规则中的处理问题;生成结果的可视化方面等等。
参考文献
[1]Rakesh Agrawal,Ramakrjshnan Srjkant.Fast Algorithms for Mining Association Rules.[S.l].:Proceedings of the20th VLDB Conference,c19xx/20xx.
[2]朱扬勇.数据挖掘入门.http://datamining.126.com.
关联规则算法综述 篇5
关键词：数据挖掘,关联规则,Apriori算法
0 引言
关联规则是数据挖掘的典型方法, 它是描述在一个交易中物品之间同时出现的规律的知识模式。关联规则的分析方法用于隐藏在大型数据集中令人感兴趣的联系。所发现的联系可以用关联规则或频繁项集的形式表示。关联规则可以揭示事物之间的联系, 也用于购物篮分析, 金融服务和科学数据分析等。
1 关联规则概念
关联规则是Agrawal等人提出的数据挖掘领域中的一个重要课题。关联规则是在交易数据、关系数据或其他信息载体中, 查找存在于项目集合或对象集合之间的频繁模式、关联、相关性或因果结构, 通过分析数据或记录间的关系, 决定哪些事情将一起发生。关联规则的蕴涵表达式形如X→Y, 其中X和Y是不相关的项集, 即X∩Y=Ф。关联规则强度可用它的支持度和置信度度量。支持度确定规则可以用于给定数据集的频繁程度, 而置信度确定Y在包含X的事物中出现的频繁程度。支持度和置信度的形式定义如下:
2 关联规则挖掘的过程
在事务数据库中找出具有用户给定的最小支持度和最小确信度的关联规则, 分解成两个子任务为:①找出事务数据库中所有大于等于用户指定最小支持度的项目集, 即频繁项目集;②利用频繁项目集生成所需要的关联规则。目前有很多产生频繁项目集的算法, 这些算法产生频繁项目集时, 扫描数据库的每个事务, 确定最小支持度, 在第k次迭代出所有频繁项目集, 然而, 由于数据库的规则通常是非常大的, 所以在每次迭代时产生候选项目集以统计其支持度是非常耗时的, 因此, 寻找频繁项目集的有效产生算法是问题的关键。
3 关联规则挖掘算法描述
1993年R.Agrawal等人提出了关联规则的挖掘问题以后, 得到了更广范围的发展, 其挖掘算法包括Agraw等人提出的AIS、Apriori、Apriori Tid算法, Park等人提出DHP、Savasere等人的Partition以及Toivonen提出的抽样算法Sampling等。
3.1 Apriori算法思想
为了生成所有频集, 使用了递推的方法。其算法思想如下:
输入:
Apriori算法是一种布尔型关联规则频繁项集的算法。Apriori算法的实现过程分为两步:一为连接, 二为剪枝。该算法基于一个频繁项集中任一子集也应该是频繁项集的性质, 使用一种逐层搜索的迭代方法, k-项集用于 (k+1) -项集。其算法流程如下:首先遍历目标数据库一次, 记录每个项目或属性的出现次数, 即计算每个项目的支持度, 收集所有支持度不低于用户最小支持度的项目构成频繁1-项集L1, 然后链接L1中所有的元素形成候选2项集C2, 再次遍历事务数据库, 计算C2中每个候选2-项集的支持度, 收集所有支持度不低于用户最小支持度的项目构成频繁2-项集L2, 再链接L2形成C3, 遍历数据库得L3, 反复执行以上过程, 直到没有候选项集为止。
在整个过程中, 多次循环, 产生大量的候选集, 验证环节需要反复扫描可能很大的交易数据库。由上可知, Apriori算法存在产生大量的候选集和需要重复扫描数据库两大缺点。
3.2 Apriori算法的优化方法
因为Apriori算法在实际的应用中, 存在不太令人满意的地方, 所以人们提出了一些优化的方法。
(1) 基于划分的方法。
算法先把数据库从逻辑上分成几个互不相交的块, 每次单独考虑一个分块并对它生成所有的频集, 然后合并产生的频集生成所有可能的频集, 最后计算这些项集的支持度。这里分块的大小选择要使每个分块可放入主存, 每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。
(2) 基于采样的方法。
基于前一遍扫描得到的信息进行组合分析, 得到一个改进的算法, 即在计算k-项集时, 如果认为某个 (k+1) -项集可能是频集时, 就并行地计算这个 (k+1) -项集的支持度, 该算法需要的总的扫描次数通常少于最大的频集的项数。
(3) 动态项集计数。
该技术动态地评估已被计数的所有项集, 不像Apriori算法仅在每次完整的数据库扫描之前确定新的候选, 它可以在任何点添加, 一旦一个项集的所有子集被确定为是频繁的, 就可以启动对该项集支持度的计算。因此, 该算法所需的数据库扫描次数要比Apriori算法少。
此外, 还有事务压缩、基于杂凑等优化方法。
4 关联规则的应用
4.1 购物篮分析
销售商为了取得更多的经济效益, 需要对市场形式进行分析, 了解顾客的购买习惯和偏爱。在买一件物品的同时购买相关物品的概率增加会使商品的销量增加, 获得更高的利润。关联规则采掘可以提供这些信息。在销售行业, 关联规则采掘的最有效的应用就是对销售的物品进行数据分析, 从而得知顾客的购买特性, 进行更有效的销售行动。例如, 人们在购买面包的时候同时购买牛奶, 销售商会把这两种产品放在一起进行销售, 极大的提高了销售额。
4.2 金融服务
金融服务行业广泛地应用了关联规则采掘技术。银行分析家运用关联规则采掘技术去分析大量的数据, 并为投资活动建立起贸易和风险模型。
4.3 科学数据分析
在地球科学数据分析中, 关联模式可以揭示海洋、陆地和大气过程之间的有趣关系。这些信息能够帮助地球科学家更好的理解地球系统中不同的自然力之间的相互作用。
5 结束语
社会信息量不断更新变化, 隐含的规则也在不断变化着, 而算法的研究是一个十分复杂的问题。本文对关联规则的算法进行了一定的分析。提高算法效率并应用于社会各个领域仍是人们关心的问题。
参考文献
[1]R Agrawal.Mining Association Rules Between Sets of Items in Large Databases[C].Washington:Proceedings of the ACM SIGMOD Inter-national Conference Management of Data, 1993.
[2]H.Toivonen.Sampling Large Databases for Association Rules[C].Pr-oceedings of the22nd International Conference on Very Large Data-base, Bombay, India, September1996.
[3]范明, 范宏建.数据挖掘导论[M].北京:人民邮电出版社, 2006.
[4]钱雪忠.关联规则挖掘中对Apriori算法的研究[J].计算机工程与应用, 2008 (17) .
[5]朱慧爽.关联规则挖掘算法初探[J].科技信息, 2008 (3) .