基因表达数据关联规则挖掘算法研究

VIP免费

3.0 李佳 2024-09-23 5 4 1.94MB 24 页 150积分

侵权投诉

第3章一种结合完全连接的改进 Apriori 算法

基于 Apriori 算法原理，提出一种有效的完全连接条件，在频繁 2k-项集的

集合进行自身 Apriori 连接得频繁项集的同时，自身完全连接产

生未剪枝的候选项集；对频繁项集的集合，直接对其项

集进行自身完全连接产生未剪枝的候选项集。改进的算法减少了连接

的比较次数、迭代运算次数。实验表明该算法在保证无遗漏的情况下有效地提高

了算法的挖掘速度。

3.1 引言

关联规则是 KDD 研究中一个重要的研究课题，用于发现大量数据中项集之

间有趣的关联或相关联系。目前已提出许多挖掘关联规则的算法，其中最为经典

的是 Apriori 算法，它是 Agrawal 等人提出的，算法思想是使用逐层搜索的迭代

方法。算法主要包括三个步骤：连接步、剪枝步和扫描数据库，其中连接步是算

法的关键步骤。其它大部分关联规则挖掘算法都是在该算法的基础上加以改进或

扩展得来的，有基于划分(partition)的、基于杂凑(hash)的、基于采样的、基于事务

压缩的 Apriori 算法；也有很多在这些算法的基础上做了更细致的工作。这些算

法主要是在减少扫描数据库的运算量上所做的改进，通过减少访问数据库的次

数或减少数据库中的数据量来提高运行效率。

本文根据 Apriori 算法原理，从连接步着手，提出一种结合完全连接的算法：

对频繁项集的集合进行自身连接得频繁项集的同时，产生

未剪枝的候选项集；对频繁项集的集合，直接对其

项集进行完全连接得未剪枝的候选项集。该算法根据两个连接

条件的相斥性以及项集之间的有序性，在减少连接运算量的情况下，得到正确

的、更丰富的所需信息量；同时根据算法的原理优化了结束的步骤，减少了部分

频繁奇数项集集合的迭代运算。通过减少连接运算量、迭代运算次数而有效地提

高了算法的挖掘速度。该算法是基于 Apriori 算法的连接步所做的改进，与基于

划分、杂凑、采样以及事务压缩等改进算法的思想是独立且互不相斥的，故该算

法具有高度可扩展性，可与划分、杂凑、采样以及事务压缩等优化技术同时使用

提高算法的效率。

3.2 相关知识

Apriori 算法是一种最有影响的挖掘布尔关联规则频繁项集的算法，采用了

一种称作逐层搜索的迭代方法，项集用于探索项集。首先，找出频

繁1-项集的集合，记为。用于找频繁 2-项集的集合，而用于找

如此下去，直到不能找到频繁项集。找每个需要一次数据库扫描。(本文

采用符号表示连接)

其生成频集所使用了递推的方法核心思想描述如下：

(1)L1，={large1-itemsets}；

(2)for(k=2；Lk≠φ；k++)dobegin

(3)Ck=Apriori-gen(Lk-1)；//新的候选集

(4)foralltransactionst∈Ddobegin

(5)Ct=subset(Ck，t)；//事务 t中包含的候选集

(6)forallcandidatesc∈Ctdo

(7)c.count++；

(8)end

(g)Lk={c∈Ck|c.count≥minsup}

(10)end

(11)Answer=UkLk；

Apriori 算法主要包括三个步骤：

（1）连接步：为找，通过 Lk与自己连接产生候选(k+1)一项集的集合。

该候选项集的集合记作 Ck+1。设 li和lj是Lk的项集，记 li[k]表示 li的第 k项。如果

Lk的元素是可连接的，则执行连接。Lk的两元素 li和lj是可连接的条件为

其中条件是简

单的保证不产生重复。连接产生的结果项集是。

（2）剪枝步：Ck是Lk的超集；利用 Apriori'h}质：任何非频繁的(k-1)-项集

都不可能是频繁 k-项集的子集。因此，如果一个候选 k-项集的(k-1)-子集不在 Lk

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

150 积分 4人已下载

立即下载 VIP免费下载

摘要：

第3章一种结合完全连接的改进Apriori算法基于Apriori算法原理，提出一种有效的完全连接条件，在频繁2k-项集的集合进行自身Apriori连接得频繁项集的同时，自身完全连接产生未剪枝的候选项集；对频繁项集的集合，直接对其项集进行自身完全连接产生未剪枝的候选项集。改进的算法减少了连接的比较次数、迭代运算次数。实验表明该算法在保证无遗漏的情况下有效地提高了算法的挖掘速度。3.1引言关联规则是KDD研究中一个重要的研究课题，用于发现大量数据中项集之间有趣的关联或相关联系。目前已提出许多挖掘关联规则的算法，其中最为经典的是Apriori算法，它是Agrawal等人提出的，算法思想是使用逐层搜索...

展开>> 收起<<

基因表达数据关联规则挖掘算法研究.doc

共24页,预览2页

还剩页未读，继续阅读

基因表达数据关联规则挖掘算法研究

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: