摘 要：隨著時代的進(jìn)步和科學(xué)技術(shù)的發(fā)展，數(shù)據(jù)資源越來越多，但是信息貧乏的困境卻依然無法擺脫，于是如今開始大力對新的數(shù)據(jù)分析方法和工具進(jìn)行查找，從海量數(shù)據(jù)中將有用知識給提取出來。針對如今Apriori算法效率的瓶頸，就需要提出策略來改進(jìn)本算法。本文簡要分析了基于數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則Apriori算法的優(yōu)化對策，希望可以提供一些有價值的參考意見。

關(guān)鍵詞：數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則；Apriori算法

中圖分類號：TP311.13

隨著科學(xué)技術(shù)的不斷進(jìn)步，數(shù)據(jù)資源越來越多，但是豐富的數(shù)據(jù)，卻依然沒有解決信息貧乏問題，針對這種情況，就需要對數(shù)據(jù)分析方法和工具進(jìn)行尋找，以便從海量數(shù)據(jù)中將有用的知識給提取出來。在這種背景下，產(chǎn)生了數(shù)據(jù)庫的數(shù)據(jù)挖掘；數(shù)據(jù)挖掘指的是從數(shù)據(jù)庫中將潛在的有用的知識給提取出來，有效結(jié)合了人工智能、數(shù)據(jù)加工以及信息決策等各種學(xué)科的知識，其中在數(shù)據(jù)挖掘研究中，非常重要的一個組成部分就是關(guān)聯(lián)規(guī)則挖掘研究，它的目的是將大規(guī)模數(shù)據(jù)集中項集之間的關(guān)聯(lián)關(guān)系或者模式給找出來。

1 關(guān)聯(lián)規(guī)則的定義及性質(zhì)

我們將一組項目集假設(shè)為I=[i1，i2，i3，，，in]。假設(shè)D為任務(wù)相關(guān)的事務(wù)集，每一個項集用T來表示，并且T屬于L，每一個事務(wù)的標(biāo)識都是唯一的。

定義1：假設(shè)有K個項目存在于項集X中，用k來表示X的長度或者大小，那么就可以將k-項集稱呼這時的項集X。

定義2：假設(shè)在事務(wù)數(shù)據(jù)庫D中，TuY報包含于至少s%的事務(wù)中，那么X≒Y就具有支持度s%。

定義3：假設(shè)X的事務(wù)存在于事務(wù)數(shù)據(jù)庫D中，并且有c%以上的事務(wù)也具有Y，那么c%就為X≒Y的置信度。

定義4：假設(shè)一個k-項集，它的支持度不大于minsup，那么就可以用頻繁k-項集來稱呼這個k-項集，用Lk-來標(biāo)記這些所有頻繁k-項集。

那么關(guān)聯(lián)規(guī)則的挖掘問題就是需要滿足下面兩個公式：

2 Apriori算法

Apriori算法使用的迭代方法是逐層搜索，在探索k+1-項集中應(yīng)用k-項集；首先，將頻繁1-項集給找出來，用L1來記作本集合，利用這個集合，將頻繁2-項集給找出來，記作L2，然后利用第二個集合來取尋找頻繁3-項集，按照這樣的順序循環(huán)下來，如果頻繁k-項集不能夠被找到，就可以停止。本算法存在著一種缺點(diǎn)，那就是每次要尋找一個頻繁項集，就需要對數(shù)據(jù)庫進(jìn)行一次掃描，那么就需要對交易數(shù)據(jù)庫進(jìn)行多次掃描。另外，將模式匹配應(yīng)用到頻繁項目集的識別過程中，那么就沒有較高的效率。

3 Apriori算法的改進(jìn)

一是改進(jìn)算法的思想。本文利用經(jīng)典的Apriori算法，將新的數(shù)據(jù)結(jié)構(gòu)給應(yīng)用過來，將基于鏈表的數(shù)據(jù)結(jié)構(gòu)應(yīng)用到改進(jìn)后的算法中，有集頭結(jié)點(diǎn)、項結(jié)點(diǎn)以及事務(wù)結(jié)點(diǎn)等被鏈表涉及到，只需要一次掃描數(shù)據(jù)庫或者數(shù)據(jù)倉庫，這樣就可以避免Apriori算法多次掃描數(shù)據(jù)庫，促使大量的I/O開銷得到了減少，實現(xiàn)系統(tǒng)性能得到提升的目的。鏈表的一級兄弟節(jié)點(diǎn)從左到右排列方面，是按照子集支持度計數(shù)的遞增順序進(jìn)行的，這樣即使有著很大的1-項集，也只會有較少的候選2-子集產(chǎn)生，3-候選子集就更加的少，促使系統(tǒng)得到較大程度的提升。鏈表結(jié)構(gòu)圖如圖1：

圖1 鏈表結(jié)構(gòu)圖

二是改進(jìn)算法的原理及實現(xiàn)。上文我們已經(jīng)提到，將鏈表的數(shù)據(jù)結(jié)構(gòu)應(yīng)用到改進(jìn)的算法中，假設(shè)k-項集的頭結(jié)點(diǎn)為ITMHEAD，指針數(shù)為量，一個對k-項集的第一個項結(jié)點(diǎn)ITEMNODE指向，另一個則對k+1-項集的頭結(jié)點(diǎn)進(jìn)行指向，每一個項結(jié)點(diǎn)ITEMNODE也分別有兩個指針，分別指向事物集的第一個事務(wù)和下一個項結(jié)點(diǎn)；對于事務(wù)結(jié)點(diǎn)TID來講，指針數(shù)量只有一個，對下一個事務(wù)結(jié)點(diǎn)進(jìn)行指向。

假設(shè)k-項集的一個項結(jié)點(diǎn)為ITEMNODEa和ITEMNODEb，那么項值指的就是它們的item數(shù)組中的k個值，用i1，i2，i3來表示ITEMNODEa的項值，用j1，j2，j3來表示ITEMNODEb的項值，那么與Apriori算法關(guān)于連接的條件正好符合，因此連接ITEMNODEa和ITEMNODEb就為k+1-項集的候選項結(jié)點(diǎn)。如果最小支持度小于本候選項結(jié)點(diǎn)的支持度，就對一個新結(jié)點(diǎn)進(jìn)行構(gòu)建，并且在ITEMHEADk+1指向的結(jié)點(diǎn)中連接。鏈表的構(gòu)建過程是這樣的：

首先，按照1-項子集支持度計數(shù)的遞增順序來從左到右排列ITEMHEAD1指向的項結(jié)點(diǎn)ITEMNODE，并且從左到右的排序不能按照項目字典次序來進(jìn)行，這樣產(chǎn)生的候選項集才比較的少。

其次，對1-項集的所有節(jié)點(diǎn)進(jìn)行掃描，結(jié)合支持度來連接它們，同時，對相同事務(wù)TID進(jìn)行合并，將2-項集的結(jié)點(diǎn)給生成出來。

然后，對2-項集的所有結(jié)點(diǎn)進(jìn)行掃描，結(jié)合支持來連接它們，同時對相同事務(wù)TID進(jìn)行合并，將3-項集的結(jié)點(diǎn)給生成出來。

最后，按照這樣的順序依次循環(huán)，一直到?jīng)]有新的結(jié)點(diǎn)出現(xiàn)。

4 結(jié)束語

通過上文的敘述分析我們可以得知，隨著時代的發(fā)展，出現(xiàn)了越來越多的數(shù)據(jù)資源，但是目前信息貧乏的問題依然沒有得到解決。要想在海量的數(shù)據(jù)中獲得需求的信息，就需要進(jìn)行研究。傳統(tǒng)的Apriori算法在實踐過程中逐漸顯露出來了一系列的弊端，需要對交易數(shù)據(jù)庫進(jìn)行多次掃描，浪費(fèi)了大量的資源。針對這種情況，就需要對其進(jìn)行改進(jìn)。通過研究，本文提出了一種基于鏈表的數(shù)據(jù)結(jié)構(gòu)改進(jìn)算法，因為只需要一次掃描數(shù)據(jù)庫，就可以動態(tài)減少數(shù)據(jù)，促使挖掘效率得到有效提高。

參考文獻(xiàn)：

[1]楊曉萍.關(guān)聯(lián)規(guī)則Apriori算法的改進(jìn)[J].浙江海洋學(xué)院學(xué)報，2006（02）：123-125.

[2]楊建兵.數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則的改進(jìn)算法及實現(xiàn)[J].微計算機(jī)信息，2006（07）：555-556.

[3]朱氣相，徐勇，張林.基于改進(jìn)Apriori算法的關(guān)聯(lián)規(guī)則挖掘研究[J].計算機(jī)技術(shù)與發(fā)展，2006（07）：66-68.

作者簡介：張小軍（1980.01-），男，河南人，講師，研究方向：云計算，數(shù)據(jù)挖掘，通信技術(shù)。

作者單位：河南教育學(xué)院信息技術(shù)系，鄭州 450000；河南省人民廣播電臺 鄭州 450000；鄭州市回民中學(xué)鄭州 450000