关联规挖掘算法研究
[口·资源环境学院 理信息系统0501 雄伟 200501440108]
摘：文介绍数挖掘概念发展现状研究方重点介绍数仓库核心技术关联规挖掘基概念般步骤常算法算法中介绍典Apriori算法种改进方法数挖掘发展方提出法
关键词数挖掘关联规挖掘Apriori算法
0前言
着计算机网络技术代表信息技术发展越越企业政府组织教育机构科研单位实现信息数字化处理数仓库已广泛应企业理产品销售科学计算信息服务等领域引起数量快速增长数库存储理分析提出更高求方面面庞飞速增长数量需新处理工具便动化搜集数转化价值信息知识方面剧增数中隐藏着许重信息希够已占信息进行更高层次分析便更利数目前数库系统然较实现数录入查询统计等功尚支持海量数背重信息挖掘导致数丰富知识贫乏现象数挖掘(DataMining简称DM)技术正述应求产生
1 数挖掘概述
11数挖掘定义
1技术角度：量完全模糊噪声机实际应数中提取隐含中事先知道潜信息知识程
2商业角度：企业定业务目标量企业数进行探索分析揭示隐藏未知验证已知规律性进步模型化先进效方法
12数挖掘研究现状发展方
国外已召开次国际性研讨会仅1999年例20国际会议列数挖掘知识发现专题创办电子刊物KnowledgeDiscoveryNugge外国外知名数挖掘系统SAS公司文SimonFraser学DBMinerSPSS公司ClementineSYBASE公司rehousestudiRuleQuestReseareh公司SeesIBM公司Almaden研究中心QUEST等等
国起步较晚没形成整体力量1993年国家然科学基金首次支持该领域研究项目目前国许科研单位高等院校竞相开展知识发现基础理应研究单位包括清华学中科院计算技术研究空军第三研究海军装备证中心等中北京系统工程研究模糊方法知识发现中应进行较深入研究北京学开展数立方体代数研究华中理工学复旦学浙江学中国科技学中科院数学研究**学等单位开展关联规开采算法优化改造**学四川联合学海交通学等单位探讨研究非结构化数知识发现Web数挖掘
目前国外数挖掘发展趋势研究方面知识发现方法研究进步发展年注重Bayes(贝叶斯)方法Boosting方法研究提高传统统计学回法KDD中应KDD数库紧密结合应方面包括KDD商业软件工具断产生完善注重建立解决问题整体系统孤立程软件户集中型银行保险公司电信公司销售业数挖掘技术研究成熟应存局限性数挖掘技术需解决问题发展方
1数输入形式样性
2数挖掘算法效性测性伸缩性
3技术集成扩展性
4数挖掘系统交互性
5数挖掘中隐私保护信息安全
6复杂数类型挖掘新方法
7知识表示解释
13关联规概述
关联分析称关联规挖掘市场营销事务分析等领域成功应成数挖掘中重活跃研究容数挖掘核心技术
关联规挖掘务事务数库D中找出满足户定支持度minsup信度minconf户感兴趣关联规挖掘关联规时解决面两问题
1算法复杂性目前挖掘关联规算法针问题提出
2必须产生规集中选择户感兴趣规信度支持度确保挖掘出关联规户感兴趣中包含许冗余意义规支持度信度较高关联规常识性知识称信息制定关联规兴趣度计算标准挖掘出关联规更满足户需求
通关联规研究发现数库项目间定联系效提高应系统决策支持力市场策略商业营目标设计仓储规划等现实意义
文介绍关联规挖掘研究应
2 关联规挖掘
关联规数挖掘(简称关联规挖掘)量数中挖掘出价值描述数项间相互联系关知识
21关联规描述
211基概念
项目(Item)交易数库中属性字段字段定取值范围超级市场讲项目般指次交易中物品
交易(Transaction)某客户次交易中发生项目集合
项目集(Itemset)包含干项目集合
项目集维数项目集包含项目数称项目集维数项目集长度长度k项目集称作k维项目集
支持度(SuPPort)假定X项目集D交易集合交易数库称D中包含X交易数D中总交易数XD中支持度X支持度记作suP(X)关联规X→Y支持度记作suP(xUY)
信度(Confidence)形X→Y关联规中XY项目集定义规信度交易集合D中包含X包含Y交易数D中仅包含X包含Y交易数者说项目集XUY支持度x支持度suP(XUY)sup(X)规X→Y信度记作conf(X→Y)
支持度(MinimumSuPPort)户定义衡量支持度阂值表示项目集统计意义低重性记作minsuP
信度(MinimumConfidence)户定义衡量信度阂值表示规低性记作minconf
频繁项目集(FrequentItemset)项目集x果X支持度户定义支持度阂值sup(X)>minsuP称X频繁项目集项集(LargeItemset)频繁k项集集合记Lk
非频繁项目集(NotFrequentItemset)项目集x果X支持度户定义支持度闭值suP(X)212关联规分类
1基规中处理变量类
分布尔型关联规量化型关联规
2基规中数抽象层次
分单层关联规挖掘层关联规挖掘
3基规中涉数维度
分单维关联规挖掘维关联规挖掘
213关联规挖掘程
关联规挖掘事务数库D中找出满足户定支持度minsup信度minconf求关联规整挖掘程分解两步
1找出事务数库D中支持度等户指定支持度项目集支持度支持度项目集称频繁项目集某频繁项目集超集支持度支持度阂值称该项目集频繁项目集
2利频繁项目集生成需关联规频繁项目集A找A非空子集a果率support(A)support(a)>mineonf生成关联规a→(Aa)support(A) support(a)规a→(Aa)信度
22关联规Apriori算法
221Apriori算法基思想
Apriori算法种影响力挖掘单维布尔关联规频繁项集算法逐层搜索迭代算法利频繁（K1）项集生成频繁K项集首先通扫描数集基预先定支持度生成频繁1项集集合L1然基L1数集中数生成频繁2项集集合L2样方法直生成频繁n项集集合Ln（已生成满足支持度（n+1）项集）频繁项集导出关联规
222关联规算法描述
输入事务数库D支持度阂值min_suP
输出D中频繁项集L
算法描述：
(1)L1find_frequentes_litemset(D)
(2)for(k2Lk1Φk++)
(3) {
(4) Ckariorigen(Lk1min_sup)
(5) for each transaetions t € D
(6) {
(7) Ctsubset(Ckt)
(8) for each candidate c € Ck
(9) ccount++
(10) }
(11) Lk{c€Ck|ceount>min_suP}
(12) }
(13) return LUk Lk
(14)Procedure apriori_gen(Lk1min_sup)
(15){
(16)For each itemset l1 € Lk1
(17)For eachitemset l2 € Lk1
(18)if(l1[1]12[l])and(11[2]12[2])and…(l1[k2]l2[k2])and(l1[k1}<12[k1])
(19){
(20) cl1&l2
(21) if has_infrenquen_subset(cLk1)
(22) delete c
(23) else
(24) add c to Cr
(25) }
(26)Return Cr
(27)Proceduce has_infrenquent_subset(cLk1)
(28) {
(29) For each (k1)_subsets of c
(30) If s € Lk1
(31) Return TURE
(32) else
(33) Return FALSE
(34) }
(35)}
根面算法描述出APriori算法中两关键步骤候选项目集生成二候选项目集计数
223例题分析
例设数库D表2l示D中包含9条事务|D|9支持数mincount2支持度minsuP290222挖掘频繁项目集具体程述
表21 数库D
Tid
itemset
T100
abe
T200
bd
T300
bc
T400
abd
T500
ac
T600
bc
T700
ac
T800
abce
T900
abc
第步算法第次迭代事务数库进行次扫描计算出包含项目出现次数生成候选1项集集合C1
第二步设定支持数求C1中确定出频繁1项集L1时项目满足mincount求L1C1相
第三步产生频繁2项目集执行Apriorigen中第七步生成候选2项目集集合C2然扫描事务数库C2中项目集进行计数
第四步根mincountC2中确定L2C1中满足mincount求候选项目集放入L2中
第五步产生频繁3项目集执行Apriorigen中第七步生成候选3项目集集合
C3{{abc}{abe}{bcd}{bce}{bde}}{bcd}{bce}
{bde}子集中包含非频繁2项目集根Apriorigen剪枝步骤(第89步)剪掉然扫描事务数库C3中进行计数
第六步根mincountC3中确定L3C3中满足mincount候选项目集放入L3中
第七步产生频繁4项目集执行L3&L3生成候选4项目集集合C4{{abce}}{abce}子集中包含非频繁3项目集{bce}剪掉时c4ΦAPriori算法整执行程结束
找事务数库中频繁项集利频繁项集产生关联规产生关联规步骤
(1)频繁项目集l产生l非空子集
(2)L非空子集m果support(l) support(m)>minconf输出规m→（lm）
例例中产生频繁项目集l{abe}l非空子集{ab}{ae}{be}{a}{b}{e}运述产生关联规方法关联规
a∧b→e confidenee(29)(49)05
a∧e→b confidence(29)(29)l
b∧e→a confidenee(29)(29)1
a∧b→e confidenee(29)(69)033
b∧a→e confidence(29)(79)029
e∧a→b onfidenee(29)(29)l
分析出许情况APriori算法侯选产生检查方法幅度压缩侯选项集导致性该算法存足处
1阶段Ck特CZ
2扫描事务数库次数
3频繁项长度变情况运算时间显著增加
4直接关系数库关联规挖掘
5适海量数环境关联规挖掘
23基Apriori算法改进方法
减APriori算法中存问题带影响提高APriori算法执行性许学者基础进行量研究提出改进算法通常APriori基础改进算法称类APriori算法面分种典型改进方法进行介绍：
1基Hash优化方法
该算法利散列表(hashtable)产生候选集APriori算法直接改进遍历次数库候选k项目集支持数频繁k项目集DHP算法事务(k+1)项目集通hash规形成散列表散列表栏包括通散列规映射该栏中项目集数目根结果散列表生成位量散列表中应该栏中数字者等支持数时应位置1否O该量滤掉次生成候选时必项目集某候选量中应位值0舍弃候选2项目集产生尤效第二趟减候选集规模
2基划分优化方法
该算法先数库逻辑分成互相交块次单独考虑分块生成频繁集然产生频繁项目集合生成频繁项目集计算项目集支持度里分块选择分块放入存阶段需扫描次算法正确性频繁项目集少某分块中频繁项目集保证面讨算法高度行分块分分配某处理器生成频繁项目集产生频繁项目集循环结束处理器间进行通信产生全局候选k项目集
3基采样优化方法
4基事务压缩优化方法
3 结束语
然数挖掘技术提出目前止十年时间吸引众领域科研员企业理者高度关注作数挖掘重容—关联规更研究热点成数挖掘技术中先成功应企业企业带巨利润技术数挖掘样关联规挖掘目海量数中发现知识提高挖掘效率便研究方
面目前数挖掘关联规挖掘技术火爆研究热潮广阔市场应前景文做工作沧海粟许问题进步研究例目前研究偏重算法角度进行研究型数库系统高效结合实现实应系统等工作需完善空间数进行高效精确空间关联规挖掘挖掘结果视化表达等等进步研究方
参考文献：
[1]吴际黄传河基数挖掘入侵检测系统研究计算机工程应2003(4)166168
[2]邹力鹃王丽珍空间数挖掘发展研究计算机工程应2003(n)186188
[3]胡军涛武德峰李国辉媒体数挖掘体系结构方法计算机工程
[4]郭学军等粗集方法数挖掘中应**学学步陡(然科学版)19998276279
[5]周欣沙锋朱扬勇等兴趣度关联规阂值计算机研究发展2000(05)
[6]侯兵关联规挖掘算法研究[硕士文]西南交通学20066
[7]张瑞雪数挖掘中关联规算法研究应[硕士文]**工程学20066
[8]贾俊杰基关联规数挖掘算法研究[硕士文]西北师范学20056
[9]李长源关联规挖掘算法研究[硕士文]**工程学20056
[10]饶天贵杨燕关联规中Apiori算法改进彭丹2006年全国理计算机科学学术年会文集[C]2006
[注]：摘董春玲老师课讲义具体出处明没标出
4
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
[口·资源环境学院 理信息系统0501 雄伟 200501440108]
摘：文介绍数挖掘概念发展现状研究方重点介绍数仓库核心技术关联规挖掘基概念般步骤常算法算法中介绍典Apriori算法种改进方法数挖掘发展方提出法
关键词数挖掘关联规挖掘Apriori算法
0前言
着计算机网络技术代表信息技术发展越越企业政府组织教育机构科研单位实现信息数字化处理数仓库已广泛应企业理产品销售科学计算信息服务等领域引起数量快速增长数库存储理分析提出更高求方面面庞飞速增长数量需新处理工具便动化搜集数转化价值信息知识方面剧增数中隐藏着许重信息希够已占信息进行更高层次分析便更利数目前数库系统然较实现数录入查询统计等功尚支持海量数背重信息挖掘导致数丰富知识贫乏现象数挖掘(DataMining简称DM)技术正述应求产生
1 数挖掘概述
11数挖掘定义
1技术角度：量完全模糊噪声机实际应数中提取隐含中事先知道潜信息知识程
2商业角度：企业定业务目标量企业数进行探索分析揭示隐藏未知验证已知规律性进步模型化先进效方法
12数挖掘研究现状发展方
国外已召开次国际性研讨会仅1999年例20国际会议列数挖掘知识发现专题创办电子刊物KnowledgeDiscoveryNugge外国外知名数挖掘系统SAS公司文SimonFraser学DBMinerSPSS公司ClementineSYBASE公司rehousestudiRuleQuestReseareh公司SeesIBM公司Almaden研究中心QUEST等等
国起步较晚没形成整体力量1993年国家然科学基金首次支持该领域研究项目目前国许科研单位高等院校竞相开展知识发现基础理应研究单位包括清华学中科院计算技术研究空军第三研究海军装备证中心等中北京系统工程研究模糊方法知识发现中应进行较深入研究北京学开展数立方体代数研究华中理工学复旦学浙江学中国科技学中科院数学研究**学等单位开展关联规开采算法优化改造**学四川联合学海交通学等单位探讨研究非结构化数知识发现Web数挖掘
目前国外数挖掘发展趋势研究方面知识发现方法研究进步发展年注重Bayes(贝叶斯)方法Boosting方法研究提高传统统计学回法KDD中应KDD数库紧密结合应方面包括KDD商业软件工具断产生完善注重建立解决问题整体系统孤立程软件户集中型银行保险公司电信公司销售业数挖掘技术研究成熟应存局限性数挖掘技术需解决问题发展方
1数输入形式样性
2数挖掘算法效性测性伸缩性
3技术集成扩展性
4数挖掘系统交互性
5数挖掘中隐私保护信息安全
6复杂数类型挖掘新方法
7知识表示解释
13关联规概述
关联分析称关联规挖掘市场营销事务分析等领域成功应成数挖掘中重活跃研究容数挖掘核心技术
关联规挖掘务事务数库D中找出满足户定支持度minsup信度minconf户感兴趣关联规挖掘关联规时解决面两问题
1算法复杂性目前挖掘关联规算法针问题提出
2必须产生规集中选择户感兴趣规信度支持度确保挖掘出关联规户感兴趣中包含许冗余意义规支持度信度较高关联规常识性知识称信息制定关联规兴趣度计算标准挖掘出关联规更满足户需求
通关联规研究发现数库项目间定联系效提高应系统决策支持力市场策略商业营目标设计仓储规划等现实意义
文介绍关联规挖掘研究应
2 关联规挖掘
关联规数挖掘(简称关联规挖掘)量数中挖掘出价值描述数项间相互联系关知识
21关联规描述
211基概念
项目(Item)交易数库中属性字段字段定取值范围超级市场讲项目般指次交易中物品
交易(Transaction)某客户次交易中发生项目集合
项目集(Itemset)包含干项目集合
项目集维数项目集包含项目数称项目集维数项目集长度长度k项目集称作k维项目集
支持度(SuPPort)假定X项目集D交易集合交易数库称D中包含X交易数D中总交易数XD中支持度X支持度记作suP(X)关联规X→Y支持度记作suP(xUY)
信度(Confidence)形X→Y关联规中XY项目集定义规信度交易集合D中包含X包含Y交易数D中仅包含X包含Y交易数者说项目集XUY支持度x支持度suP(XUY)sup(X)规X→Y信度记作conf(X→Y)
支持度(MinimumSuPPort)户定义衡量支持度阂值表示项目集统计意义低重性记作minsuP
信度(MinimumConfidence)户定义衡量信度阂值表示规低性记作minconf
频繁项目集(FrequentItemset)项目集x果X支持度户定义支持度阂值sup(X)>minsuP称X频繁项目集项集(LargeItemset)频繁k项集集合记Lk
非频繁项目集(NotFrequentItemset)项目集x果X支持度户定义支持度闭值suP(X)
1基规中处理变量类
分布尔型关联规量化型关联规
2基规中数抽象层次
分单层关联规挖掘层关联规挖掘
3基规中涉数维度
分单维关联规挖掘维关联规挖掘
213关联规挖掘程
关联规挖掘事务数库D中找出满足户定支持度minsup信度minconf求关联规整挖掘程分解两步
1找出事务数库D中支持度等户指定支持度项目集支持度支持度项目集称频繁项目集某频繁项目集超集支持度支持度阂值称该项目集频繁项目集
2利频繁项目集生成需关联规频繁项目集A找A非空子集a果率support(A)support(a)>mineonf生成关联规a→(Aa)support(A) support(a)规a→(Aa)信度
22关联规Apriori算法
221Apriori算法基思想
Apriori算法种影响力挖掘单维布尔关联规频繁项集算法逐层搜索迭代算法利频繁（K1）项集生成频繁K项集首先通扫描数集基预先定支持度生成频繁1项集集合L1然基L1数集中数生成频繁2项集集合L2样方法直生成频繁n项集集合Ln（已生成满足支持度（n+1）项集）频繁项集导出关联规
222关联规算法描述
输入事务数库D支持度阂值min_suP
输出D中频繁项集L
算法描述：
(1)L1find_frequentes_litemset(D)
(2)for(k2Lk1Φk++)
(3) {
(4) Ckariorigen(Lk1min_sup)
(5) for each transaetions t € D
(6) {
(7) Ctsubset(Ckt)
(8) for each candidate c € Ck
(9) ccount++
(10) }
(11) Lk{c€Ck|ceount>min_suP}
(12) }
(13) return LUk Lk
(14)Procedure apriori_gen(Lk1min_sup)
(15){
(16)For each itemset l1 € Lk1
(17)For eachitemset l2 € Lk1
(18)if(l1[1]12[l])and(11[2]12[2])and…(l1[k2]l2[k2])and(l1[k1}<12[k1])
(19){
(20) cl1&l2
(21) if has_infrenquen_subset(cLk1)
(22) delete c
(23) else
(24) add c to Cr
(25) }
(26)Return Cr
(27)Proceduce has_infrenquent_subset(cLk1)
(28) {
(29) For each (k1)_subsets of c
(30) If s € Lk1
(31) Return TURE
(32) else
(33) Return FALSE
(34) }
(35)}
根面算法描述出APriori算法中两关键步骤候选项目集生成二候选项目集计数
223例题分析
例设数库D表2l示D中包含9条事务|D|9支持数mincount2支持度minsuP290222挖掘频繁项目集具体程述
表21 数库D
Tid
itemset
T100
abe
T200
bd
T300
bc
T400
abd
T500
ac
T600
bc
T700
ac
T800
abce
T900
abc
第步算法第次迭代事务数库进行次扫描计算出包含项目出现次数生成候选1项集集合C1
第二步设定支持数求C1中确定出频繁1项集L1时项目满足mincount求L1C1相
第三步产生频繁2项目集执行Apriorigen中第七步生成候选2项目集集合C2然扫描事务数库C2中项目集进行计数
第四步根mincountC2中确定L2C1中满足mincount求候选项目集放入L2中
第五步产生频繁3项目集执行Apriorigen中第七步生成候选3项目集集合
C3{{abc}{abe}{bcd}{bce}{bde}}{bcd}{bce}
{bde}子集中包含非频繁2项目集根Apriorigen剪枝步骤(第89步)剪掉然扫描事务数库C3中进行计数
第六步根mincountC3中确定L3C3中满足mincount候选项目集放入L3中
第七步产生频繁4项目集执行L3&L3生成候选4项目集集合C4{{abce}}{abce}子集中包含非频繁3项目集{bce}剪掉时c4ΦAPriori算法整执行程结束
找事务数库中频繁项集利频繁项集产生关联规产生关联规步骤
(1)频繁项目集l产生l非空子集
(2)L非空子集m果support(l) support(m)>minconf输出规m→（lm）
例例中产生频繁项目集l{abe}l非空子集{ab}{ae}{be}{a}{b}{e}运述产生关联规方法关联规
a∧b→e confidenee(29)(49)05
a∧e→b confidence(29)(29)l
b∧e→a confidenee(29)(29)1
a∧b→e confidenee(29)(69)033
b∧a→e confidence(29)(79)029
e∧a→b onfidenee(29)(29)l
分析出许情况APriori算法侯选产生检查方法幅度压缩侯选项集导致性该算法存足处
1阶段Ck特CZ
2扫描事务数库次数
3频繁项长度变情况运算时间显著增加
4直接关系数库关联规挖掘
5适海量数环境关联规挖掘
23基Apriori算法改进方法
减APriori算法中存问题带影响提高APriori算法执行性许学者基础进行量研究提出改进算法通常APriori基础改进算法称类APriori算法面分种典型改进方法进行介绍：
1基Hash优化方法
该算法利散列表(hashtable)产生候选集APriori算法直接改进遍历次数库候选k项目集支持数频繁k项目集DHP算法事务(k+1)项目集通hash规形成散列表散列表栏包括通散列规映射该栏中项目集数目根结果散列表生成位量散列表中应该栏中数字者等支持数时应位置1否O该量滤掉次生成候选时必项目集某候选量中应位值0舍弃候选2项目集产生尤效第二趟减候选集规模
2基划分优化方法
该算法先数库逻辑分成互相交块次单独考虑分块生成频繁集然产生频繁项目集合生成频繁项目集计算项目集支持度里分块选择分块放入存阶段需扫描次算法正确性频繁项目集少某分块中频繁项目集保证面讨算法高度行分块分分配某处理器生成频繁项目集产生频繁项目集循环结束处理器间进行通信产生全局候选k项目集
3基采样优化方法
4基事务压缩优化方法
3 结束语
然数挖掘技术提出目前止十年时间吸引众领域科研员企业理者高度关注作数挖掘重容—关联规更研究热点成数挖掘技术中先成功应企业企业带巨利润技术数挖掘样关联规挖掘目海量数中发现知识提高挖掘效率便研究方
面目前数挖掘关联规挖掘技术火爆研究热潮广阔市场应前景文做工作沧海粟许问题进步研究例目前研究偏重算法角度进行研究型数库系统高效结合实现实应系统等工作需完善空间数进行高效精确空间关联规挖掘挖掘结果视化表达等等进步研究方
参考文献：
[1]吴际黄传河基数挖掘入侵检测系统研究计算机工程应2003(4)166168
[2]邹力鹃王丽珍空间数挖掘发展研究计算机工程应2003(n)186188
[3]胡军涛武德峰李国辉媒体数挖掘体系结构方法计算机工程
[4]郭学军等粗集方法数挖掘中应**学学步陡(然科学版)19998276279
[5]周欣沙锋朱扬勇等兴趣度关联规阂值计算机研究发展2000(05)
[6]侯兵关联规挖掘算法研究[硕士文]西南交通学20066
[7]张瑞雪数挖掘中关联规算法研究应[硕士文]**工程学20066
[8]贾俊杰基关联规数挖掘算法研究[硕士文]西北师范学20056
[9]李长源关联规挖掘算法研究[硕士文]**工程学20056
[10]饶天贵杨燕关联规中Apiori算法改进彭丹2006年全国理计算机科学学术年会文集[C]2006
[注]：摘董春玲老师课讲义具体出处明没标出
4
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档