Apriori關聯規則算法的 C語言實現

李 楠,寧燕子,楊存志

（遼寧師范大學 a.計算機與信息技術學院；b.檔案館 ；c.教務處,遼寧 大連 116029）

Apriori關聯規則算法的 C語言實現

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

（遼寧師范大學 a.計算機與信息技術學院；b.檔案館 ；c.教務處,遼寧 大連 116029）

在分析 Apriori算法的基礎上,介紹了該算法的 C語言實現,包括頻繁集的發現和關聯規則的生成,為進一步研究關聯規則提供了基礎。

數據挖掘；關聯規則；Apriori算法；C語言

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

關聯規則挖掘最早是由 Agrawal等人于 1993年提出的[3],其形式化的描述如下:設 I={i1,i2,…,im}是 m個不同項的集合,事務 T為 I的子集,不同的事務的集合構成事務集D。關聯規則就是形如X→Y的蘊涵式,其中 X? I,Y? I,且 X∩Y=Φ。

關聯規則的實用性由支持度衡量,描述了 X和 Y兩個項集同時出現的概率,定義為:Suppo rt（X→Y）=|{T:X∪Y? T,T∈D}|/|D|。關聯規則的準確性由可信度衡量,描述了出現 X的事務集 D同時也出現 Y的概率,定義為:Confidence（X→Y）=|{T:X∪Y? T,T∈D}|/|{T:X? T,T∈D}|。

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

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

（2）根據找到的頻繁集,產生所有可信度大于m in-confidence的規則。其中,步驟 （1）是制約Apriori算法運行效率的關鍵所在,因為需要多次掃描數據集,需要消耗大量的時間和空間,眾多文獻中都對 Apriori算法的改進進行了多種研究[4-7]。

1 Apriori算法

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

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

第一步

輸入:數據集 D；最小支持度 m in_sup

輸出:頻繁項目集 L

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

2 算法的實現流程和主要源代碼

2.1 算法的實現流程

算法的流程如圖 1。

圖1 Apriori算法實現流程圖

2.2 數據庫、數據項的結構體

下面用 C語言實現上述算法,首先要定義結構體,分別存放數據項。

2.3 主要的程序源代碼

2.4 實驗結果及分析

采用如圖 2的數據庫。

圖2 數據庫中的項目集

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

圖3 連續輸入 3條項目并且顯示運行結果

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

（1）多次掃描事務數據庫,需要很大的 I/O負載。

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

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

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

3 結 語

Apriori算法是關聯規則中的經典算法,文中主要對 Apriori算法進行研究分析之后,采用 C語言對算法進行了實現,為進一步的關聯規則改進等方面的實現都奠定了一個良好的基礎。

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

[2]王麗珍,周麗華,陳紅梅,等.數據倉庫與數據挖掘原理及應用[M].北京:科學出版社,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].計算機工程與應用,2007（43）:24.

[5]錢少華,蔡勇,錢雪忠.基于數組的 Apriori算法的改進[J].計算機應用與軟件,2006,23（2）:44-46.

[6]謝宗毅.關聯規則挖掘 Apriori算法的研究與改進[J].杭州電子科技大學學報,2006,23（3）:78-82.

[7]程玉勝,鄧小光,江效堯.Apriori算法中頻繁項集挖掘實現研究[J].計算機技術與發展,2006,16（3）:58-60.

（責任編輯 劉敏）

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">文獻標志碼:A

A

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

2010-09- 07；

2010-09-17

國家自然科學基金項目 （20873055）。

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