Apriori算法.docx

Apriori算法Apriori算法48最早是由Agrawa等人提出。算法通過對(duì)數(shù)據(jù)庫的多次掃描來計(jì)算項(xiàng)集的支持度，發(fā)現(xiàn)所有的頻繁項(xiàng)集后，進(jìn)一步生成關(guān)聯(lián)規(guī)則。算法利用的核心思想是頻繁項(xiàng)集的任何非空真子集必定也是頻繁的，非頻繁項(xiàng)集的任何超集必定不是頻繁的。表5-1 Apriori算法步驟Table 5-1 Steps of Apriori AlgorithmApriori算法步驟：(1) 掃描整個(gè)數(shù)據(jù)庫，產(chǎn)生候選1-項(xiàng)集的集合C1(2) 根據(jù)最小支持度min_sup，從C1中產(chǎn)生頻繁1-項(xiàng)集的集合L1(3) 對(duì)k1，重復(fù)執(zhí)行步驟(4)、(5)、(6)(4)對(duì)Lk執(zhí)行連接和剪枝操作，產(chǎn)生候選(k+l)-項(xiàng)集的集合Ck+1，(5)根據(jù)最小支持度min_sup，從Ck+1中產(chǎn)生頻繁 (k+1)-項(xiàng)集的集合Lk+1(6) 若Lk，則k=k+1，跳往步驟(4); 否則，跳往步驟(7);(7) 根據(jù)最小置信度min_con，由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則（8）結(jié)束。 其中對(duì)產(chǎn)生頻繁項(xiàng)集的連接和剪枝操作解釋如下：a) 連接(join)采用遞推的連接方法求，用與自身作連接產(chǎn)生候選k-項(xiàng)集的集合。具體來說，設(shè) 和 是中的項(xiàng)集且各項(xiàng)按統(tǒng)一標(biāo)準(zhǔn)排序。當(dāng)滿足條件時(shí)，則和 是可連接的，產(chǎn)生新的項(xiàng)集為：，將該項(xiàng)集加入集合，直到不能產(chǎn)生新的項(xiàng)集。b) 剪枝(prune)頻繁k-項(xiàng)集的任何子集必須是頻繁項(xiàng)集。由連接生成的集合需要進(jìn)行驗(yàn)證，去除小于支持度閾值的非頻繁k-項(xiàng)集。5.2.2.2 Apriori 算法描述Apriori算法主要由4個(gè)函數(shù)構(gòu)成，分別如表5-2-表5-5所示。表5-2 Apriori由頻繁項(xiàng)集產(chǎn)生候選集Table5-2 Apriori from Frequent Set to Candidate SetApriori_gen (Lk-1) / 通過(k-1)-頻繁項(xiàng)集產(chǎn)生k-候選集begin for al1 itemset I1 in Lk-1 do for al1itemset I2 in Lk-1 doif (Il1=I2l)(I12=I22) (I1k-1=I2k-1) c=I1 join I2 ;/ 連接產(chǎn)生候選集 if has_infrequent_subset(c，Lk-1) delete c; else add c to Ck;end forend forendreturn Ck;表5-3 Apriori發(fā)現(xiàn)頻繁項(xiàng)集Table 5-3 Apriori Find Frequent SetApriori_genfreItems（D，min_sup）輸入:數(shù)據(jù)庫D，最小支持度閥值min_sup輸出: D中的頻繁集LBeginL1=1-頻繁項(xiàng)集;for (k=2; Lk-1; k+) doCk=Apriori_gen(Lk-l); /構(gòu)造候選集for all 事務(wù) t in D do Ct=subset(Ck，t); / 搜索t包含的候選集for all CCt do C.sup=C.sup+1; end for; /計(jì)算支持?jǐn)?shù) end for;Lk= CCt | C.sup min_sup; /得到k階頻繁項(xiàng)集end forEndReturn Lk=;表5-4 判斷集合是否含非頻繁子集 表5-5由頻繁項(xiàng)集生成規(guī)則Table 5-4 Determine Set is Frequent or Not Table 5-5 Produce Rules from Frequent Sethas-infrequent-subset(c，Lk-1) /判斷c是否含有非頻繁子集Beginfor all (k-1)- subset s of c do if s Lk-1 return true; return false; End generateRule (Lk，min_con)Beginfor each I Lk dofor XI and X doif support(L)/support(X