发布时间 : 星期日 文章基于群体智能的关联规则挖掘及应用更新完毕开始阅读
山东师范大学硕士学位论文
源代价。算法改进实现如下[31]： (1)Ｌ1={频繁的1-项集};
(2) Ｃ1=数据库Ｄ； Ｃ0=￠；Apriorifist=ture； (3)for（k=2；Lk-1 ≠￠；k++）
{ //考虑别的内存开销,我们用内存容量的2/3来做比
较。
(4)if（Apriorifirst==ture）
(5){ＣＫ=apriori-gen（Lk-1）； //新候选项 (6)for all 事务t∈Ｄ
(7){Ct=subset（Ck，t）； //t中包含的候选项 (8)for all候选项c∈Ct (9)c.count++
}
(10)Lk={c∈Ck|c.cpumt≥最小支持度} (11)if(((
?候选c?CK支持度（c） +事务数)>2/3*sizeof（memory）and（count（频
??
繁的候选Ck） } //跳转执行Aprioritid算法思想 (13)else{ (14) if(第一次跳转) (15) {Ck+1=apriori-gen（Lk）；//新候选项 (16) Ck+1=gen（Ck+1）;//生成当前步的 ＣＫ+1 (17) LK+1={c∈Ck+1｜c.count≥最小支持度} (18) Ck+2=apriori-gen（Lk+1）; //新候选项 } (19) for all执行入口ｔ∈ Ck?1 (20) {//决定包含在事务中(该事务以t.TID标识)的Ck中的候选项集 ???? 41 山东师范大学硕士学位论文 (21) Ct=={ｃ∈ＣＫ+2|(ｃ-ｃ[ｋ+2])∈ｔ.项集的集合∧(ｃ-ｃ[ｋ+1])∈ｔ.项集的 集合}; (22) for all候选项ｃ∈Ct (23) c.count++ (24) if(Ct≠￠) (25) Ck+2 += } (26) Lk+2={ｃ∈Ck+2c.count≥最小支持度} } } (27)return（YkLk）; 算法改进后，为了验证上述算法的有效性,我们在电力发电方式数据中进行了有效性验证。在该数据集中,每个发电厂有一个布尔变量,表示该发电厂的是否被调度选中发电。每个调度指令则可用一个布尔向量来表示。可以分析布尔向量,得到反映发电厂频繁关联或同时被选中发电的调度模式。这些模式可以用关联规则的形式表示。我们分别提取了2001年第一季度、上半年和全年的发电方式数据来测试Apriori和Apriorisuper两种算法的执行效率。: 三种算法执行时间比较表 执行时间 （秒） 算法 Apriori 2 4 7 AprioriTid 2.5 3.5 6.75 Apriorisuper 1.5 2 3 从图3我们可看出三种算法的执行时间随着数据量的增大,效率区别越来越明显。 42 数据量 第一季度 上半年数据 全年数据 山东师范大学硕士学位论文 第四章 基于微粒群的抽样算法在关联规则中 的应用 4.1问题的提出 关联规则是数据挖掘模式发现中一种重要的探索性数据分析方法。从应用来看，关联规则发现是从交易数据库中找出统计关联较大的商品，从而发现有价值的购买行为模式，这些模式的提取可为商品货架布局、存货控制、多目标客户营销和交叉配售等业务管理提供决策支持①。然而，关联规则引起研究的兴趣不仅限于是因为规则本身可以作为知识产生商业价值，对关联规则计算算法的探索在机器学习计算复杂性问题中具有普遍意义。关联规则算法效率的评价分析，也是目前数据挖掘中亟待突破的难点问题之一。 最初的关联规则发现算法多为静态一次性抽样算法，其中较有权威性的算法是Agrawal、Imielinski和Swami②于1993年提出的算法Apriori。H.Toivonon③提出将一次性抽样算法BSAR与Apriori算法结合训练关联规则，并根据PAC学习理论计算训练样本的最小样本量为 m?1(ln|H|?ln(1?))，其中|H|表示待挖掘规则的条数，?表示错误率，而?表22?示出错率。根据一次性抽样理论，R的支持度为sup(R)= ?=fr(R,I)= #(Xi?r,Xj?s)ns , 其中ns表示抽取的样本量，#（Xi=r，Xj=s）表示二元规则R{ Xi=r }{ Xj=s }同时成立的总的样本量。同样可以定义置信度，关联规则发现是寻找满足支持度和置信度分别由于二者算法完全一致，因此关联规则的关键技术是确定找到在给定最小支持度?的最优规则搜索路径，即满足fr(R,I)>?的所有规则R因此，这里所指的规则并不考虑方向性，如果R满足这一条件，则称R是?频繁的，反之，称R为?非频繁。 43 山东师范大学硕士学位论文 传统的一次性抽样算法至少存在两方面的问题：1、一次性抽样算法虽然在理论上保证了结果的高精度，然而当用于商品种类过多，交易量非常大的关联发现，则计算时间是相当可观的，甚至是不可在有限年内解决；2、一次性抽样算法很难应用于联机分析，这些问题将限制 Apriori算法的使用。Carlos Domingo ④ 提出了基于序贯抽样理论设计的可升级性算法ASAR，证明了ASAR算法可以有效地产生频繁集，并且比一次性抽样算法需要更少的样本。序贯抽样算法事先不固定样本容量，通过序列抽取样本的方式，不断缩小备选规则集的选择范围，逐步淘汰候选规则集，从而降低算法对样本量的实际的运行时间，提高算法的执行效率。该算法的提出为用更少的样本得到更重要的规则提出了新的思路。这种算法与最初的Apriori算法没有本质性的结合，这使得ASAR并没有充分利用事务型数据库的特点进行设计，因而仍然会出现理论样本量过高的表现。后来提出了Apriori和ASAR相结合的APASAR算法。 本文提出一种群体智能技术中的微粒群算法（PSO）与Apriori算法相结合的算法，称之为PSASAR算法。利用群体智能技术加快挖掘过程，增加智能性，在数据库扫描时，利用群体智能技术，替代全数据库扫描，提高效率，这种扫描比随机选样要有效。 下面给出该算法的理论停止时间的结果和证明，第二部分给出部分通过模拟实验比较PSASAR，ASAR，BSAR和ApASAR四种不同算法的运行效果。 4.2基于微粒群抽样的关联规则算法（PSASAR） 4.2.1 PSASAR算法的基本思想 关联规则发现的效率主要由频集计算效率体现。提高频集计算效率的最主要的方法是将候选集组织成树状结构，树的根节点表示成一个候选规则，它的子树则是该候选规则的从属规则。Apriori算法是其中的典型，它利用了频繁集组合的向下封闭性，将所有可能的规则组合按照k-项集依次排列，构成搜索空间，这样当k-项集中的某个k-项规则组合成为大项集中的一员，则它的k-i-项规则组合(i=1,?,k-1)都会成为大项集中的一员。因为有很多规则组合不会出现在候选集中，所以我们也采用了ApASAR算法的设计思想，在设计的时候，将候选规则集的规模不固定，候选规则集里面的规则组合随着微粒群抽样的进行，不满足最小范围下界的规则将会不断被淘汰，甚至不能进入候选集， 44