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

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

中圖分類號：TP301

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

1 經(jīng)典Apriori算法

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

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

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

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

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

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

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

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

2 Apriori的改進

2.1 SQL語言簡介

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

2.2 改進算法描述

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

改進算法描述如下：

算法：基于SQL的Apriori改進算法

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

輸出：頻繁項集

方法：

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

（2）k++；

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

（4）如果 ，goto（8）；

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

（6）如果 ，goto（8）；

（7）否則goto（2）；

（8）輸出Lk-1；

3 算法驗證

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

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

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

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

4 結(jié)束語

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

參考文獻：

[1]付沙，宋丹.基于矩陣的Apriori改進算法研究[J].微電子學(xué)與計算機，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