基于數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則Apriori算法的優(yōu)化對(duì)策分析

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

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

中圖分類號(hào)：TP311.13

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

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

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

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

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

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

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

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

2 Apriori算法

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

參考文獻(xiàn)：

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

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

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

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

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