Apriori關(guān)聯(lián)規(guī)則算法的 C語言實(shí)現(xiàn)

李 楠,寧燕子,楊存志

（遼寧師范大學(xué) a.計(jì)算機(jī)與信息技術(shù)學(xué)院；b.檔案館 ；c.教務(wù)處,遼寧 大連 116029）

Apriori關(guān)聯(lián)規(guī)則算法的 C語言實(shí)現(xiàn)

李 楠a,寧燕子b,楊存志c

（遼寧師范大學(xué) a.計(jì)算機(jī)與信息技術(shù)學(xué)院；b.檔案館 ；c.教務(wù)處,遼寧 大連 116029）

在分析 Apriori算法的基礎(chǔ)上,介紹了該算法的 C語言實(shí)現(xiàn),包括頻繁集的發(fā)現(xiàn)和關(guān)聯(lián)規(guī)則的生成,為進(jìn)一步研究關(guān)聯(lián)規(guī)則提供了基礎(chǔ)。

數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則；Apriori算法；C語言

數(shù)據(jù)挖掘 （Data Mining,DM）是指從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的實(shí)際數(shù)據(jù)中,提取隱含在其中的、人們不知道的、但又是潛在有用的信息和知識的過程[1],是數(shù)據(jù)庫知識發(fā)現(xiàn)（Know ledge Discovery in Database,KDD）過程中對數(shù)據(jù)真正應(yīng)用算法抽取知識的一個步驟,是 KDD過程中的重要環(huán)節(jié)[2]。數(shù)據(jù)挖掘的方法主要包括:分類、回歸分析、聚類、關(guān)聯(lián)分析等。其中,關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘研究的一個重要分支,是眾多知識類型中最為典型的一種。

關(guān)聯(lián)規(guī)則挖掘最早是由 Agrawal等人于 1993年提出的[3],其形式化的描述如下:設(shè) I={i1,i2,…,im}是 m個不同項(xiàng)的集合,事務(wù) T為 I的子集,不同的事務(wù)的集合構(gòu)成事務(wù)集D。關(guān)聯(lián)規(guī)則就是形如X→Y的蘊(yùn)涵式,其中 X? I,Y? I,且 X∩Y=Φ。

關(guān)聯(lián)規(guī)則的實(shí)用性由支持度衡量,描述了 X和 Y兩個項(xiàng)集同時出現(xiàn)的概率,定義為:Suppo rt（X→Y）=|{T:X∪Y? T,T∈D}|/|D|。關(guān)聯(lián)規(guī)則的準(zhǔn)確性由可信度衡量,描述了出現(xiàn) X的事務(wù)集 D同時也出現(xiàn) Y的概率,定義為:Confidence（X→Y）=|{T:X∪Y? T,T∈D}|/|{T:X? T,T∈D}|。

關(guān)聯(lián)規(guī)則挖掘就是在事務(wù)集D中找到滿足最小支持度 m in-support和最小可信度 m in-confidence的關(guān)聯(lián)規(guī)則。該問題一般分為兩步驟完成:

（1）找出滿足最小支持度 m in-support的所有頻繁集；

（2）根據(jù)找到的頻繁集,產(chǎn)生所有可信度大于m in-confidence的規(guī)則。其中,步驟 （1）是制約Apriori算法運(yùn)行效率的關(guān)鍵所在,因?yàn)樾枰啻螔呙钄?shù)據(jù)集,需要消耗大量的時間和空間,眾多文獻(xiàn)中都對 Apriori算法的改進(jìn)進(jìn)行了多種研究[4-7]。

1 Apriori算法

在眾多關(guān)聯(lián)規(guī)則的算法中,Apriori是最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)目集的算法,同時也是其他大部分關(guān)聯(lián)規(guī)則算法的基礎(chǔ)。Apriori算法的最主要的概念,就是從候選項(xiàng)目集合 Ck-1中通過掃描事務(wù)集 D,找出大于或者等于最小支持度的項(xiàng)目集,稱為頻繁項(xiàng)目集 Lk-1；再以頻繁項(xiàng)目集Lk-1通過自連接和剪枝操作產(chǎn)生候選項(xiàng)目集Ck,候選項(xiàng)目集 Ck再通過掃描事務(wù)集找出頻繁項(xiàng)目集 Lk,如此重復(fù)直到無法找到頻繁項(xiàng)目集為止。

為了生成所有頻集,使用了遞推的方法。其核心思想簡要描述如下:

第一步

輸入:數(shù)據(jù)集 D；最小支持度 m in_sup

輸出:頻繁項(xiàng)目集 L

has_infrequent_subset（c,Lk-1）是為了判斷 c是否需要加入到 k-候選集中。按 A graw al的項(xiàng)目集格空間理論,含有非頻繁項(xiàng)目自己的元素不可能是頻繁項(xiàng)目集,因此應(yīng)該及時裁掉那些含有非頻繁項(xiàng)目子集的項(xiàng)目集,以提高效率。例如 L2={AB,AD,AC,BD},對于新產(chǎn)生的元素 ABC不需要加入到 C3中,因?yàn)樗淖蛹?BC不在 L2中,而 ABD應(yīng)該加入到 C3中,因?yàn)樗乃械?2-項(xiàng)子集都在 L2中。

2 算法的實(shí)現(xiàn)流程和主要源代碼

2.1 算法的實(shí)現(xiàn)流程

算法的流程如圖 1。

圖1 Apriori算法實(shí)現(xiàn)流程圖

2.2 數(shù)據(jù)庫、數(shù)據(jù)項(xiàng)的結(jié)構(gòu)體

下面用 C語言實(shí)現(xiàn)上述算法,首先要定義結(jié)構(gòu)體,分別存放數(shù)據(jù)項(xiàng)。

2.3 主要的程序源代碼

2.4 實(shí)驗(yàn)結(jié)果及分析

采用如圖 2的數(shù)據(jù)庫。

圖2 數(shù)據(jù)庫中的項(xiàng)目集

本程序執(zhí)行以后,切實(shí)的可以自由設(shè)置最小支持度,并且在確定支持度的前提下,可以輸入實(shí)際的交易集大小,以及交易集中項(xiàng)目的個數(shù),并且選擇實(shí)際的數(shù)據(jù)庫,在以上 3項(xiàng)確定的情況下可以得到的運(yùn)行結(jié)果如圖 3。

圖3 連續(xù)輸入 3條項(xiàng)目并且顯示運(yùn)行結(jié)果

Apriori算法作為經(jīng)典的頻繁項(xiàng)目集生成算法,在數(shù)據(jù)挖掘中具有里程碑作用。但是隨著研究的深入,缺點(diǎn)也暴露出來。Apriori算法有兩個致命的性能瓶頸:

（1）多次掃描事務(wù)數(shù)據(jù)庫,需要很大的 I/O負(fù)載。

對每次 k循環(huán),候選集 Ck中的每個元素都必須通過掃描數(shù)據(jù)庫一次來驗(yàn)證其是否加入Lk。加入一個頻繁大項(xiàng)目集包含 10個項(xiàng),那么至少需要掃描事務(wù)數(shù)據(jù)庫 10遍。

（2）可能產(chǎn)生龐大的候選集。由 Lk-1產(chǎn)生 k-候選集 Ck是指數(shù)增長的,如此大的候選集對時間和主存空間是一種挑戰(zhàn)。

本文用 C語言實(shí)現(xiàn)之算法,對所輸入數(shù)據(jù)庫有嚴(yán)格的限制,循環(huán)語句太多,并且每一次掃描數(shù)據(jù)庫都要進(jìn)行多層循環(huán),浪費(fèi)了程序運(yùn)行的時間和空間,因此有進(jìn)一步研究改進(jìn)的空間。

3 結(jié) 語

Apriori算法是關(guān)聯(lián)規(guī)則中的經(jīng)典算法,文中主要對 Apriori算法進(jìn)行研究分析之后,采用 C語言對算法進(jìn)行了實(shí)現(xiàn),為進(jìn)一步的關(guān)聯(lián)規(guī)則改進(jìn)等方面的實(shí)現(xiàn)都奠定了一個良好的基礎(chǔ)。

[1]陳京民.數(shù)據(jù)倉庫與數(shù)據(jù)挖掘技術(shù)[M].北京:電子工業(yè)出版社,2002.

[2]王麗珍,周麗華,陳紅梅,等.數(shù)據(jù)倉庫與數(shù)據(jù)挖掘原理及應(yīng)用[M].北京:科學(xué)出版社,2005.

[3]AGRAWAL R,IM IL IENSK IT,SWAM IA.Mining association ru les between sets of item s in large datasets[C].GIGMOD,1993:207-216.

[4]柴華昕,王勇.Apriori挖掘頻繁項(xiàng)目集的算法的改進(jìn)[J].計(jì)算機(jī)工程與應(yīng)用,2007（43）:24.

[5]錢少華,蔡勇,錢雪忠.基于數(shù)組的 Apriori算法的改進(jìn)[J].計(jì)算機(jī)應(yīng)用與軟件,2006,23（2）:44-46.

[6]謝宗毅.關(guān)聯(lián)規(guī)則挖掘 Apriori算法的研究與改進(jìn)[J].杭州電子科技大學(xué)學(xué)報,2006,23（3）:78-82.

[7]程玉勝,鄧小光,江效堯.Apriori算法中頻繁項(xiàng)集挖掘?qū)崿F(xiàn)研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,2006,16（3）:58-60.

（責(zé)任編輯 劉敏）

Research and Implementation of Apriori Rules Algorithm Based on C

LI Nana,NING Yan-zib,YANG Cun-zhic
（a.College of Computer and Information Technology；b.Archives；c.Academic Affairs Division Liaoning Normal University,Dalian Liaoning 116029,China）

A ssociation rule is an effective way for know ledge discovery in datamining,where in algorithms.The Apriori is a classical algorithm.Based on the analysis of the algorithm Apriori,we introduced the algorithm’s realization of discovery of frequent item sets and generation of association rules by using C,and at last it perform s a validation to discover the frequent item sets from the traditional market basket,and also the rules satisfying with the minimum support and confidence.Which provide a so lid foundation for further research of association rules.

datamining；association rules；Apriorialgorithm；Clanuage

TP312 < class="emphasis_bold">文獻(xiàn)標(biāo)志碼:A

A

1009-315X（2011）01-0052-04

2010-09- 07；

2010-09-17

國家自然科學(xué)基金項(xiàng)目 （20873055）。

李楠 （1977-）,女,遼寧丹東人,講師,主要從事分布式數(shù)據(jù)庫、數(shù)據(jù)挖掘算法研究。