一種基于SQL的Apriori改進(jìn)算法

摘 要：針對關(guān)聯(lián)規(guī)則經(jīng)典算法Apriori的不足，這篇文章提出了一種基于SQL的改進(jìn)算法。該算法只需要1次掃描數(shù)據(jù)庫即可判斷候選集是否頻繁，減少了對候選數(shù)據(jù)庫的掃描次數(shù)。實(shí)驗(yàn)證明該方法的執(zhí)行效率比原方法要快。

關(guān)鍵詞：關(guān)聯(lián)規(guī)則；Apriori；SQL

中圖分類號：TP301

關(guān)聯(lián)規(guī)則（Association rules）是數(shù)據(jù)挖掘的一個(gè)重要研究方向，其目的是發(fā)現(xiàn)大量數(shù)據(jù)中項(xiàng)集之間有趣的關(guān)聯(lián)或相關(guān)聯(lián)系[1]。挖掘關(guān)聯(lián)規(guī)則就是在大量事務(wù)數(shù)據(jù)（比如顧客消費(fèi)記錄）中找出用戶感興趣的關(guān)聯(lián)性（比如購買面包的顧客有多少同時(shí)又購買了牛奶，并且符合這一關(guān)聯(lián)性的顧客又在總的消費(fèi)記錄中占了多少比例），也就是事務(wù)數(shù)據(jù)庫中滿足用戶給定條件（最小支持度和最小置信度）的項(xiàng)目集合，我們把這個(gè)項(xiàng)目集合稱作頻繁項(xiàng)目集，又稱為頻繁集。我們可以將以上挖掘過程分解成2個(gè)步驟：一是掃描事務(wù)數(shù)據(jù)庫D，從中找出所有滿足用戶指定最小支持度的頻繁項(xiàng)集；二是利用頻繁項(xiàng)集生成所需要的關(guān)聯(lián)規(guī)則，分析項(xiàng)目之間的關(guān)聯(lián)性。在這兩步中，第二步比第一步更為容易實(shí)現(xiàn)，因此目前大量的研究工作主要都集中在如何進(jìn)一步提高第一步中頻繁集的查找效率。

1 經(jīng)典Apriori算法

Apriori算法是挖掘關(guān)聯(lián)規(guī)則的經(jīng)典算法，由Agrawal等人于1994年提出[2]，是一種具有重要影響的挖掘關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法，其核心是基于兩階段頻繁項(xiàng)集的遞推算法，通過候選項(xiàng)集找到頻繁項(xiàng)集[3]。Apriori算法使用一種稱作逐層搜索的迭代方法，k項(xiàng)集用于探索生成（k+1）項(xiàng)集。每個(gè)頻繁集Lk的查找生成都需要掃描一次數(shù)據(jù)庫。

為了提高頻繁項(xiàng)集產(chǎn)生的效率，可以用一種稱作Apriori性質(zhì)的重要性質(zhì)來壓縮搜索空間。Apriori性質(zhì)是這樣的：頻繁項(xiàng)集的所有非空子集都必須也是頻繁項(xiàng)集。將Apriori性質(zhì)用于查找頻繁項(xiàng)集的時(shí)候，只要發(fā)現(xiàn)一個(gè)候選集的非空子集不頻繁，則可以判斷這個(gè)候選集不頻繁?？梢詫⑦@個(gè)過程分成兩個(gè)步驟：連接和剪枝。

（1）連接步：產(chǎn)生候選項(xiàng)集Ck；

（2）剪枝步：掃描數(shù)據(jù)庫，計(jì)算候選項(xiàng)集Ck中每個(gè)候選的計(jì)數(shù)是否滿足最小支持度來確定Lk。然而Ck可能很大，為了減少對數(shù)據(jù)庫的掃描次數(shù)，可以利用前面所提的Apriori性質(zhì)來將候選集從Ck中刪除。

通過上面對算法的描述我們可以看出，盡管利用Apriori性質(zhì)來減少了部分對數(shù)據(jù)庫的掃描。但是，依然存在以下不足：

（1）它可能需要產(chǎn)生大量候選項(xiàng)集；

（2）它可能需要重復(fù)地掃描數(shù)據(jù)庫，以計(jì)算每個(gè)候選集的頻繁程度。

所以對Apriori算法的改進(jìn)主要集中在降低候選集的數(shù)量和減少對數(shù)據(jù)庫的掃描次數(shù)兩個(gè)方面。

2 Apriori的改進(jìn)

2.1 SQL語言簡介

SQL（Structured Query Language，結(jié)構(gòu)化查詢語言）語言是一種用于關(guān)系數(shù)據(jù)庫操作的通用計(jì)算機(jī)編程語言，用來存取數(shù)據(jù)以及查詢、更新和管理關(guān)系數(shù)據(jù)庫系統(tǒng)。它用select、insert、update等語句實(shí)現(xiàn)對數(shù)據(jù)表格的查詢、插入、更新等操作。select語句用以從表中獲得數(shù)據(jù)，確定數(shù)據(jù)怎樣在應(yīng)用程序給出。它擁有很多可用于計(jì)數(shù)和計(jì)算的內(nèi)建函數(shù)，計(jì)算從列中取得的值，返回一個(gè)單一的值。其中count函數(shù)的作用是返回滿足查詢條件的記錄的數(shù)量，通常用來計(jì)數(shù)。

2.2 改進(jìn)算法描述

為了實(shí)現(xiàn)減少對數(shù)據(jù)庫的掃描次數(shù)來提高算法效率的目的，本改進(jìn)算法采用結(jié)構(gòu)化查詢語言SQL的select查詢語句通過and運(yùn)算符來連接Ck中各項(xiàng)，用count函數(shù)直接計(jì)算候選項(xiàng)集Ck在事務(wù)數(shù)據(jù)庫中出現(xiàn)的次數(shù)，然后將這個(gè)計(jì)算出來的次數(shù)和用戶指定的最小支持度作比較，實(shí)現(xiàn)只需要1次掃描數(shù)據(jù)庫來判斷Ck是否頻繁，從而減少對數(shù)據(jù)庫的掃描次數(shù)。

改進(jìn)算法描述如下：

算法：基于SQL的Apriori改進(jìn)算法

輸入：事務(wù)數(shù)據(jù)庫，最小支持度

輸出：頻繁項(xiàng)集

方法：

（1）根據(jù)每個(gè)項(xiàng)的出現(xiàn)次數(shù)得到頻繁1-項(xiàng)集L1；

（2）k++；

（3）連接Lk-1生成Lk；

（4）如果 ，goto（8）；

（5）否則采用SQL語句的and運(yùn)算連接Ck中的各項(xiàng)，使用count函數(shù)計(jì)算Ck的頻度和給定的最小支持度相比較，得到Lk；

（6）如果 ，goto（8）；

（7）否則goto（2）；

（8）輸出Lk-1；

3 算法驗(yàn)證

我們使用相同的軟硬件環(huán)境分別將經(jīng)典的Apriori原算法和本文提出的改進(jìn)算法實(shí)現(xiàn)頻繁集的挖掘過程。經(jīng)過編程調(diào)試，挖掘結(jié)果如下：

（1）分析5918條事務(wù)數(shù)據(jù)，2種算法結(jié)果一致。原算法運(yùn)行時(shí)間4秒，改進(jìn)算法需要3秒；

（2）分析9412條事務(wù)數(shù)據(jù)，2種算法結(jié)果一致。原算法運(yùn)行時(shí)間14秒，改進(jìn)算法只需要10秒。

從以上實(shí)驗(yàn)結(jié)果我們可以知道，基于SQL的Apriori改進(jìn)算法在執(zhí)行速度上比原算法有一定的提高。在數(shù)據(jù)量較小的時(shí)候，改進(jìn)效果不是很明顯。而在挖掘數(shù)據(jù)量為9412條事務(wù)數(shù)據(jù)時(shí)，改進(jìn)算法比原算法提高了4秒的挖掘速度，證明在事務(wù)數(shù)據(jù)庫規(guī)模越大的時(shí)候改進(jìn)效率越高。

4 結(jié)束語

本文在經(jīng)典Apriori算法的基礎(chǔ)上，分析總結(jié)了經(jīng)典算法的不足，提出了一種利用數(shù)據(jù)庫結(jié)構(gòu)化查詢語言SQL的count函數(shù)計(jì)算事務(wù)數(shù)據(jù)庫中候選集出現(xiàn)的次數(shù)，從而判斷該候選集是否頻繁。實(shí)踐證明，該方法是有效的，減少了對數(shù)據(jù)庫的掃描次數(shù)，提高了Apriori算法的執(zhí)行效率。

參考文獻(xiàn)：

[1]付沙，宋丹.基于矩陣的Apriori改進(jìn)算法研究[J].微電子學(xué)與計(jì)算機(jī)，2012（05）：156-160.

[2]R.Agrawal，T.Imielinski.Mining association rules between sets of items in large databases[A].In Proceedings of 1993 ACM SIGMOD International Conference Management of Data[C].Washington，D.C，May，1993：207-216.

[3]R.Agrwal，R.Srikant.Fast algorithms for mining association rules in large databases[R].In Research Report RJ 9839，IBM Almaden Research Center，San Jose，Canada，June，1994.

作者簡介：隆功倫（1983-），男，重慶石柱人，碩士，研究方向：數(shù)據(jù)挖掘。

作者單位：重慶師范大學(xué) 后勤與公共資源管理處，重慶 401331