基于Apriori算法的关联规则挖掘研究

关联规则Apriori算法1. 算法概述在关联规则挖掘研究中，Apriori算法是目前许多串行算法中最著名的，其他大多数算法都是基于Apriori算法的不断改进。

这些算法都运用了一个共同的性质，即频繁项目集的任一子集必定也是频繁项目集。

Apriori算法通过不断增加候选项目集的长度来逐步发现最大频繁项目集。

首先搜索1-频繁项目集，然后搜索2-频繁项目集，直到不能再增加频繁项目集的长度为止。

在每次循环过程中，产生k-候选频繁项目集的集合C k，然后计算支持度来搜索k-频繁项目集L k。

Apriori算法主要有三个步骤：第一步：连接(k-1)-频繁项目集产生k-候选频繁项目集C k(k > 1)。

第二步：从C k中修剪所有(k-1)-子集不属于L k-1的项，即包含非频繁项目的候选项目集。

第三步：扫描事务数据库来计算候选项目集的支持度，获得频繁项目集。

2. 算法Apriori的挖掘过程Apriori算法用伪代码描述如下：Input: Database, D, of transaction; Minimum support threshold, min-sup;Output: L, frequent itemsets in D.(1) L1＝{large 1 - itemsets};(2) For (k＝2; L k-1≠ ; k++) do begin(3) C k＝Apriori-gen (L k-1); // C k是长度为k的候选频繁项目集的集合(4) For each transaction t∈D do begin(5) C t＝subset (C k, t); //C t是transactions t包含的候选频繁项目集(6) For each candidate c∈C t do(7) c. count++;(8) End(9) L k＝{c∈C k| c. count ≥ min-sup}(10) End(11) Answer＝∪k L k;Apriori算法调用了Apriori-gen(L k-1)是为了通过(k-1)-频繁项目集，连接产生k-候选频繁项目集。

精心整理Apriori算法研究Apriori算法是一个挖掘关联规则的算法，是Agrawal等设计的一个基本算法。

它采用两阶段挖掘的思想，并且基于多次扫描事务数据库来执行。

1.关联规则1.1.Y ，其中BA 满1.2.第一，找出所有的频繁项集；其目标是发现满足最小支持度阈值的所有项集，这些项集称作频繁项集。

第二，由频繁项集产生强规则。

其目标是从上一步发现的频繁项集中提取所有高置信度的规则，这些规则称为强规则。

通常，频繁项集产生的计算开销远大于产生规则所需的计算开销。

2.Apriori算法思想Apriori 算法使用频繁项集的先验知识，使用一种称作逐层搜索的迭代方法，k 项集用于探索(k+1) 项集。

首先，通过扫描事务（交易）记录，找出所有的频繁 1 项集，该集合记做L1 ，然后利用L1 找频繁 2 项集的集合L2 ，L2 找L3 ，如此下去，直到不能再找到任何频繁k 项集。

最后再在所有的频繁集中找出强规则，即（3.1.1.从事务数据库（D）中挖掘出所有频繁项集。

支持度大于最小支持度minSup的项集（Itemset）称为频集（Frequent Itemset)。

首先需要挖掘出频繁1-项集；然后，继续采用递推的方式来挖掘频繁k-项集（k>1），具体做法是：在挖掘出候选频繁k-项集（Ck）之后，根据最小置信度minSup 来筛选，得到频繁k-项集。

最后合并全部的频繁k-项集（k>0）。

挖掘频繁项集的算法描述如下：算法Apriori算法的频繁集产生1:L1 = find_frequent_1-itemsets(D); // 挖掘频繁1-项集，比较容易2:f or (k=2;Lk-1 ≠Φ;k++) {3:Ck = apriori_gen(Lk-1 ,min_sup); // 调用apriori_gen方法生成候选频繁k-项集4:for each transaction t ∈D { // 扫描事务数据库D5:Ct = subset(Ck,t);6:for each candidate c ∈Ct7: c.count++; // 统计候选频繁k-项集的计数8:}9:Lk ={c ∈Ck|c.count≥min_sup} // 满足最小支持度的k-项集即为频繁k-项集10:}11:r eturn L= ∪k Lk; // 合并频繁k-项集（k>0）Apriori算法的频繁项集产生的部分有两个重要的特点：第一，它是一个逐层算法，即从频繁1-项集到最长的频繁项集，它每次遍历项集格中的一层；第二，它使用产生-测试策略来发现频繁项集。

第1篇一、实验概述本次数据挖掘实验以Apriori算法为核心，通过对GutenBerg和DBLP两个数据集进行关联规则挖掘，旨在探讨数据挖掘技术在知识发现中的应用。

实验过程中，我们遵循数据挖掘的一般流程，包括数据预处理、关联规则挖掘、结果分析和可视化等步骤。

二、实验结果分析1. 数据预处理在实验开始之前，我们对GutenBerg和DBLP数据集进行了预处理，包括数据清洗、数据集成和数据变换等。

通过对数据集的分析，我们发现了以下问题：（1）数据缺失：部分数据集存在缺失值，需要通过插补或删除缺失数据的方法进行处理。

（2）数据不一致：数据集中存在不同格式的数据，需要进行统一处理。

（3）数据噪声：数据集中存在一些异常值，需要通过滤波或聚类等方法进行处理。

2. 关联规则挖掘在数据预处理完成后，我们使用Apriori算法对数据集进行关联规则挖掘。

实验中，我们设置了不同的最小支持度和最小置信度阈值，以挖掘出不同粒度的关联规则。

以下是实验结果分析：（1）GutenBerg数据集在GutenBerg数据集中，我们以句子为篮子粒度，挖掘了林肯演讲集的关联规则。

通过分析挖掘结果，我们发现：- 单词“the”和“of”在句子中频繁出现，表明这两个词在林肯演讲中具有较高的出现频率。

- “and”和“to”等连接词也具有较高的出现频率，说明林肯演讲中句子结构较为复杂。

- 部分单词组合具有较高的置信度，如“war”和“soldier”，表明在林肯演讲中提到“war”时，很可能同时提到“soldier”。

（2）DBLP数据集在DBLP数据集中，我们以作者为单位，挖掘了作者之间的合作关系。

实验结果表明：- 部分作者之间存在较强的合作关系，如同一研究领域内的作者。

- 部分作者在多个研究领域均有合作关系，表明他们在不同领域具有一定的学术影响力。

3. 结果分析和可视化为了更好地展示实验结果，我们对挖掘出的关联规则进行了可视化处理。

通过可视化，我们可以直观地看出以下信息：（1）频繁项集的分布情况：通过柱状图展示频繁项集的分布情况，便于分析不同项集的出现频率。

收稿日期:2010-05-17;修回日期:2010-07-17。

基金项目:教育部科学研究项目(09yj c870032);重庆市科技攻关计划项目(CSTC2008AC2126;CSTC2009AC2034);重庆市自然科学基金资助项目(CSTC2008BB2065);重庆理工大学科研青年基金资助项目(2010ZQ22)。

作者简介:崔贯勋(1978-),男,河南鄢陵人,实验师,硕士,主要研究方向:数据库; 李梁(1964-),男,重庆人,副教授,主要研究方向:软件工程; 王柯柯(1977-),女,四川南充人,讲师,硕士,主要研究方向:软件工程; 苟光磊(1980-),男,重庆人,实验师,硕士,主要研究方向:人工智能; 邹航(1979-),男,重庆人,实验师,硕士,主要研究方向:数据挖掘。

文章编号:1001-9081(2010)11-2952-04关联规则挖掘中Apri ori 算法的研究与改进崔贯勋,李 梁,王柯柯,苟光磊,邹 航(重庆理工大学计算机科学与工程学院,重庆400054)(cgxy @vi p .qq .co m )摘 要:经典的产生频繁项目集的Apr i o ri 算法存在多次扫描数据库可能产生大量候选及反复对候选项集和事务进行模式匹配的缺陷,导致了算法的效率较低。

为此,对A prior i 算法进行以下3方面的改进:改进由k 阶频繁项集生成k +1阶候选频繁项集时的连接和剪枝策略;改进对事务的处理方式,减少A pr i or i 算法中的模式匹配所需的时间开销;改进首次对数据库的处理方法,使得整个算法只扫描一次数据库,并由此提出了改进算法。

实验结果表明,改进算法在性能上得到了明显提高。

关键词:数据挖掘;关联规则;A pr i or i 算法;频繁项集;候选项集中图分类号:T P311.13 文献标志码:AR esearch and i m prove m ent on Apriori algorith m of associ ati on rule m i ni ngC U I Guan -xun ,L I L iang ,WANG Ke -ke ,GOU Guang -le,i ZOU H ang(S c h ool of C o mpu ter S cience and Eng i n e ering,Chongqing Un i v e rsit y of T ec hnolo gy,Ch ong qi ng 400054,Ch i na )Abstract :T he c lassic Apr i o ri algor it h m for discovering frequent ite m sets scans the database m any ti m es and the pa ttern m atch i ng bet w een cand i date ite m sets and transacti ons is used repea ted l y ,so a large nu m ber of candida te ite m sets w ere produced ,w hich results i n l ow e fficiency o f the a l gor ith m.The i m proved A prior i a l gor it hm i m proved it from t hree aspects :firstly ,the strategy o f the jo i n step and the prune step w as i m proved when cand i da te frequent (k +1)-i te m setsw ere generated from frequent k -ite m se ts ;second l y ,t he m ethod of dea li ng w it h transacti on w as i m proved to reduce the ti m e of pattern m atch i ng to be used i n the Apr i o ri a l gor it hm ;i n the end ,t he me t hod o f deali ng w ith da tabase w as i m proved ,wh ich lead to only once scann i ng o f t he da tabase dur i ng the w ho le course of the a l go rith m.A cco rding to these i m prove m ents ,an i m proved algor it h m was i ntroduced .The effic i ency of A pri o ri algor it h m got i m prove m ent both i n ti m e and i n space .T he experi m ental results o f the i m proved a l gor ith m show that t he i m proved a l go rith m is mo re e fficient than the orig i na.lK ey words :data m i ning ;asso ciati on ru le ;A priori a l go rith m;frequent ite m sets ;candida te i te m se t0 引言关联规则挖掘作为数据挖掘的重要研究内容之一,主要研究事务数据库、关系数据库和其他信息存储中的大量数据项之间隐藏的、有趣的规律。