李 楠,寧燕子,楊存志

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

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

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

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

在分析 Apriori算法的基礎(chǔ)上,介紹了該算法的 C語言實現(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ù)據(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個不同項的集合,事務(wù) T為 I的子集,不同的事務(wù)的集合構(gòu)成事務(wù)集D。關(guān)聯(lián)規(guī)則就是形如X→Y的蘊涵式,其中 X? I,Y? I,且 X∩Y=Φ。

關(guān)聯(lián)規(guī)則的實用性由支持度衡量,描述了 X和 Y兩個項集同時出現(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算法運行效率的關(guā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ī)則頻繁項目集的算法,同時也是其他大部分關(guān)聯(lián)規(guī)則算法的基礎(chǔ)。Apriori算法的最主要的概念,就是從候選項目集合 Ck-1中通過掃描事務(wù)集 D,找出大于或者等于最小支持度的項目集,稱為頻繁項目集 Lk-1；再以頻繁項目集Lk-1通過自連接和剪枝操作產(chǎn)生候選項目集Ck,候選項目集 Ck再通過掃描事務(wù)集找出頻繁項目集 Lk,如此重復(fù)直到無法找到頻繁項目集為止。

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

第一步

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

輸出:頻繁項目集 L

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

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

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

算法的流程如圖 1。

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

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

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

2.3 主要的程序源代碼

2.4 實驗結(jié)果及分析

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

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

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

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

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

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

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

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

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

3 結(jié) 語

Apriori算法是關(guān)聯(lián)規(guī)則中的經(jīng)典算法,文中主要對 Apriori算法進(jìn)行研究分析之后,采用 C語言對算法進(jìn)行了實現(xiàn),為進(jìn)一步的關(guān)聯(lián)規(guī)則改進(jìn)等方面的實現(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挖掘頻繁項目集的算法的改進(jìn)[J].計算機(jī)工程與應(yīng)用,2007（43）:24.

[5]錢少華,蔡勇,錢雪忠.基于數(shù)組的 Apriori算法的改進(jìn)[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算法中頻繁項集挖掘?qū)崿F(xiàn)研究[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é)基金項目 （20873055）。

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