英语原文共 9 页，剩余内容已隐藏，支付完成后下载完整资料

Almaolegi M, Arkok B. An Improved Apriori Algorithm for Association Rules[J]. 2014, 3(1).

部分内容翻译：

题目：一种改进的Apriori关联规则算法

摘要

有几种关联规则的挖掘算法。 Apriori算法是最流行的算法之一，用于从大型数据库中提取频繁项目集，并获取关联规则以发现知识。 在此算法的基础上，本文指出原始Apriori缺陷在于算法浪费时间，这会对扫描整个数据库搜索频繁项目集产生局限性，并通过减少扫描事务数来对Apriori进行改进。 本文通过实验结果显示了几组交易，并且在最初的Apriori上应用了几个最小支持值，并且我们实施了改进的Apriori，我们改进的Apriori与原始Apriori相比减少了67.38％的时间消耗，并且使得 Apriori算法效率更高，耗时更少。

关键词

Apriori，改进的Apriori，频繁项目集，支持，候选项目集，耗时。

1介绍

随着信息技术的进步以及从数据集中为商业人士提取有用信息的需求，数据挖掘及其技术似乎能够实现这些目标。 数据挖掘是从数据仓库，OLAP（在线分析过程），数据库和其他信息库中存储的大量数据中发现隐藏和有趣模式的重要过程。 这些数据可能会超过TB。 数据挖掘在数据库中也被称为（KDD）知识发现。 它包括来自多个学科（如统计学，神经网络，数据库技术，机器学习和信息检索等）的技术集成。 KDD的技术在合理的时间提取了有趣的模型。 KDD过程有几个步骤用于从用户提取模式，如数据清理，数据选择，数据转换，数据预处理，数据挖掘和模式评估。

数据挖掘系统的体系结构主要有以下几个部分：数据仓库，数据库或其他信息库，根据用户请求从库中提取相关数据的服务器，根据定义的约束将知识库用作搜索引导， 数据挖掘引擎包括一组基本模块，如表征，分类，聚类，关联，回归和演化分析。 模式评估模块与数据挖掘模块进行交互，以争取有兴趣的模式。 最后，通过它的图形用户界面用户可以与数据挖掘系统进行通信并允许用户进行交互。

2.关联规则挖掘

关联挖掘是最重要的数据挖掘功能之一。它是研究人员学习研究的最受欢迎的技术。提取关联规则是数据挖掘的核心。它是在数据收集研究的重要领域之间的销售交易数据库中挖掘关联规则。这些规则的好处是预测未知的关系，产生结果，并作出决定和预测。关联规则的发现分为两个阶段：频繁项集的检测和关联规则的生成。在第一阶段，每组物品被称为物品集合。如果它们一起出现大于最小支持阈值，则该项目集称为频繁项目集。找到频繁的项目集很容易，但代价很高，所以这个阶段比第二个阶段更重要。在第二阶段，如果项集{I1，I2，I3}的规则是{I1→I2，I3}，{I2→I1，I3}，{I3→I1，I2}，{I1，I2→ I3}，{I1，I3→I1}，{I2，I3→ I1}，这些规则的数量是n2 -1，其中n =项目的数量。为了验证规则（例如X→Y），其中X和Y是项目，基于置信度阈值，置信度阈值是包含X和Y的交易与包含X的交易的A％的比值，这意味着A包含X 交易还包含Y.最小支持度和置信度由用户定义并表示出规则的约束条件。因此，应该对所有规则应用支持度和置信度阈值来修剪其值小于阈值的规则。 解决关联挖掘的问题是从大型交易效率中找出不同项目之间的相关性

关联规则的研究受到电信，银行，医疗保健和制造等更多应用的推动。

3.相关工作

频繁项集的挖掘是关联挖掘中的一个重要阶段，它在事务数据库中发现频繁项目集。 它是数据挖掘的许多任务的核心，试图从数据集中找到有趣的模式，如关联规则，分类，聚类和关联等。许多算法被提出用来寻找频繁项目集，但它们都可以分为两类：候选生成或模式增长

apriori是候选生成方法的代表。 它根据长度（k）频繁项目集生成长度（k 1）个候选项目集。 项目集的频率是通过计算事务中发生的事件来定义的。 FP-增长，是由Han于2000年提出的，代表了模式增长方法，它使用了特定的数据结构（FP-tree），FP-growth通过在条件模式库中找到所有频繁的项目集来发现频繁项目集,基于与FP-树关联的节点结构的链接，有效地构造了条件模式库。FP增长不会显式生成候选项目集。

4. APRIORI算法

Apriori算法易于执行且非常简单，用于挖掘所有频繁项目集的数据库。 该算法在数据库中进行了许多搜索以找到频繁项目集，其中使用k项目集来生成k 1项目集。 每个k项目集必须大于或等于最小支持阈值才是频率。 否则，它被称为候选项目集。 首先，算法扫描数据库以通过计算数据库中的每个项目来查找仅包含一个项目的1项目集的频率。1-项目集的频率用于找到2-项目集中的项目集，而后者又用于查找3-项目集等，直到没有更多的k项目集。如果一个项目集不频繁，那么它的任何大的子集也是不频繁的; 出现这种情况的数据从数据库的搜索空间中删除（剪枝）。

5. APRIORI算法的局限性

尽管Apriori算法清晰简单，但仍存在一些缺陷。 主要的局限性在于耗费大量时间来容纳大量频繁项集，低最小支持或大项目集的候选集。 例如，如果频繁1-项目集中有10⁴个，那么它需要生成超过10⁷个候选项到二项集，而这又将被测试和积累。 此外，为了检测大小为100（例如）v1，v2 ... v100的频繁模式，它必须产生2¹⁰⁰个候选项目集，其产生代价高且浪费候选时间。 因此，它将从候选项目集中检查多个集合，并且它将多次重复扫描数据库以找到候选项目集。 当存储容量受限且有大量交易时，Apriori将会非常低并且效率低下。

在本文中，我们提出了减少频繁项目集在数据库事务中搜索的时间的方法。

6.APRIORI算法的改进

本节将介绍改进的Apriori思想，改进的Apriori，改进的Apriori的一个例子，改进的Apriori和实验的分析和评估。

6.1.改进Apriori算法的策略

在Apriori的过程中，需要以下定义：

定义1：假设T = {T1，T2，...，Tm}，（mge;1）是一组事务，Ti = {I1，I2，...，In}，（nge;1）是项目的集合，k-itemset = {i1，i2，...，ik}，（kge;1）也是k项的集合，而k-itemsetsube;I.

定义2：假设sigma;（itemset）是项目集的支持计数或交易中项目集的出现频率。

定义3：假设C^k是大小为k的候选项集，L^k是大小为k的频繁项集。

在我们提出的方法中，我们增强Apriori算法以减少候选项集生成的时间消耗。我们首先扫描所有事务以生成包含项目、支持计数和事务ID的L1。然后用L1作为辅助器来生成L2、L3hellip;LK当我们要生成C₂时，我们构造一个自连接L1*L1构造2-ITEMSET C（x，y），其中x和y是C₂的项。在扫描所有事务记录以计算每个候选的支持计数之前，使用L1获取X和Y之间的最小支持计数的事务ID，从而仅在这些特定事务中扫描C₂。

同样的事情对于C₃，构造3-ITEMSET C（x，y，z），其中x，y和z是C₃的项目，使用L1得到最小支持数在x，y和z之间的事务ID，然后只在这些特定事务中扫描C₃，并重复这些步骤，直到没有新的频繁项集被标识。整个过程如上图所示。

6.2.改进的Apriori算法

//生成项、项支持度、事务ID

(1) L1 = find_frequent_1_itemsets (T);

(2) For (k = 2; Lk-1 ne;Phi;; k ) {

//从L_K-1生成C_K

(3) C_k = candidates generated from L_k-1;

//使用L1在Ck中获得最小支持度的项目Iw，（1le;wle;k）。

(4) x = Get _item_min_sup(Ck, L1);

// 获取包含项X的目标事务ID。

(5) Tgt = get_Transaction_ID(x);

(6) For each transaction t in Tgt Do

(7) Increment the count of all items in Ck that are found in Tgt;

(8) Lk= items in Ck ge; min_support;

(9) End;

(10) }

6.3。改进的Apriori的一个实例

假设我们有事务集D有9个事务，最小支持＝3。这个事务集如下表所示。

首先，扫描所有事务以获得包含项目和它们的支持计数的频繁1-项集L1和包含这些项的事务ID，然后消除不频繁或其支持小于MIN SUP的候选。表3中示出频繁的1项集。

下一步是从L1生成候选2项集。若要获得每个项目集的支持计数，请将2个项目集中的每个项目集拆分为两个元素，然后使用L1表来确定可以在其中查找项目集的事务，而不是在所有事务中搜索它们。例如，让我们在表4中的第一个项目（I1，I2），在原来的Apriori中，我们扫描所有9个事务来找到项目（I1，I2）；但是在我们提出的改进算法中，我们将项目（I1，I2）拆分为I1和I2，并使用L1在它们之间获得最小支持，这里I1具有最小的支持度值。之后，我们只在事务T1、T4、T5、T7、T8和T9中搜索项目集（I1，I2）。

如表5所示，根据L1表生成3项目集也是一样。

对于给定的频繁项集LK，找到满足最小置信度的所有非空子集，然后生成所有候选关联规则。

在前面的例子中，如果我们使用原始Apriori和我们改进的Apriori来计算扫描事务的数量以获得（1，2，3）-itemset，从表6中我们将观察到我们改进的Apriori和 原始Apriori中1-项目集中的项目数量在两侧都是相同的，并且每当k项目集的k增加时，从消耗时间的角度来看，我们改进的Apriori和原始Apriori之间的差距也增加，因此这将减少生成候选满足支持度的项所耗费的时间。

.

.

.

.

.

.

.

.

.

.

.总结：

本文提出了一种改进的Apriori算法，通过减少待扫描事务的数量，减少了对候选项集的事务扫描所花费的时间。每当k项集的k增加时，我们改进的Apriori与原始Apriori之间的差距从时间消耗的角度增加，并且每当最小支持的值增加时，我们改进的Apriori和原始Apriori之间的差距从所消耗的时间来看减少。在我们改进的Apriori中生成候选支持计数所花费的时间小于原始Apriori中所花费的时间；改进的Apriori将时间消耗减少了67.38%。

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[21327]，资料为PDF文档或Word文档，PDF文档可免费转换为Word