朱惠

摘要：隨著科學(xué)技術(shù)的發(fā)展，人們可以更快、更方便地獲取數(shù)據(jù)、保存數(shù)據(jù)，數(shù)據(jù)的量和復(fù)雜程度都是前所未見。該文對(duì)數(shù)據(jù)挖掘技術(shù)中的關(guān)聯(lián)規(guī)則挖掘進(jìn)行了系統(tǒng)的分析和研究，并在經(jīng)典的Apriori算法的基礎(chǔ)上改進(jìn)了一個(gè)算法。該算法是一種基于矩陣的關(guān)聯(lián)規(guī)則挖掘算法，通過掃描將數(shù)據(jù)庫映射為0-1矩陣，直接在矩陣上進(jìn)行運(yùn)算，避免了反復(fù)掃描的過程，還對(duì)Apriori性質(zhì)進(jìn)行了引申和利用，對(duì)矩陣進(jìn)行徹底的壓縮。理論分析和實(shí)驗(yàn)證明了改進(jìn)算法在效率上的提高。

關(guān)鍵詞：關(guān)聯(lián)規(guī)則；0-1矩陣

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）12-2697-05

Research and Improvement of Apriori Algorithm in Association Rules

ZHU Hui

（Dept. of Computer Science and Technology， Anhui University of Science and Technology， Huainan 232001， China）

Abstract： With the rapid development of information technologies， people can get data and store data quickly and conveniently， which results in the unprecedented rising of the quantity and complexity of the data. This thesis presents the systematic analysis and research on the data mining and association rule mining. The algorithm is an algorithm of mining association rules based on matrix.The new algorithm maps the database into a 0-1matrix， computing directly on the matrix and avoiding scanning the database repeatedly. And also extended and utilization the properties of the Apriori， the matrix will be compressed more thoroughly. At the end of the paper， a theoretical analysis and experiment will been given.

Key words： association rules； 0-1 matrix

數(shù)據(jù)挖掘的一種比較常見的理解是：從大量的、不完整的、操作的大型數(shù)據(jù)庫中，查找潛在的、有價(jià)值的、有趣的知識(shí)發(fā)現(xiàn)（ KDD，Knowledge Discovery in Database ）過程。數(shù)據(jù)挖掘過程如圖1所示。關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘中，應(yīng)用最廣泛、研究最深入的一個(gè)方法。它最早是由 Agrawal 等人提出的（ 1993 ）。最初的提出是針對(duì)購物籃分析問題（ Market Basket Analysi ）提出的，其最初目的是為了發(fā)現(xiàn)交易數(shù)據(jù)庫中售出的不同商品之間的聯(lián)系規(guī)則。這些聯(lián)系規(guī)則反應(yīng)了顧客的購買行為模式，為銷售者提供銷售知識(shí)，指導(dǎo)商家科學(xué)地安排進(jìn)貨、人性化地設(shè)計(jì)貨架以及科學(xué)地設(shè)計(jì)庫存等。關(guān)聯(lián)規(guī)則的挖掘應(yīng)用領(lǐng)域非常廣泛，比如電信業(yè)、醫(yī)藥業(yè)、制造業(yè)、政府?dāng)?shù)據(jù)庫、公安破案、安全交易、交通數(shù)據(jù)處理、保險(xiǎn)業(yè)等等?？梢园l(fā)現(xiàn)，關(guān)聯(lián)規(guī)則挖掘?qū)τ谥T多領(lǐng)域都有很好的應(yīng)用，所以對(duì)于它的研究意義重大。

1 Apriori算法概述

Apriori算法是所有算法中最有代表性的，它的應(yīng)用也是最為的廣泛。該算法的主要思路是首先，找出頻繁 1-項(xiàng)集的集合。該集合記作 L1。然后用 L2 找候選 2-項(xiàng)集的集合 C2，再根據(jù)支持度刪除不滿足條件的項(xiàng)，找到頻繁2-項(xiàng)集。而 L2 用于找 C3，C3 用于找 L3，以此類推，直到?jīng)]有頻繁 k-項(xiàng)集為止。然后用找出的頻繁集通過公式計(jì)算得到最后的強(qiáng)關(guān)聯(lián)規(guī)則。從這個(gè)算法的大致思路就可以看出，每計(jì)算一個(gè)候選項(xiàng)集的支持度的時(shí)候，都要對(duì)整個(gè)數(shù)據(jù)庫進(jìn)行一次掃描，當(dāng)候選項(xiàng)集比較大的時(shí)候，掃描次數(shù)將變得非常的多，這樣就會(huì)驗(yàn)證影響算法的效率。

Apriori 性質(zhì)[1]：頻繁項(xiàng)集的所有非空子集也都是頻繁的。

證明：假設(shè)一個(gè)項(xiàng)集 M，不是頻繁項(xiàng)集，那么久說明他的支持度是小雨最小支持度的。當(dāng)將任意一個(gè)項(xiàng) m 加入到項(xiàng)集 M 中，項(xiàng)集 M 就變成了 M∪m，長度為 |M|+1，而長度為 |M|+1 的項(xiàng)集出現(xiàn)的次數(shù)不可能比長度為 |M| 的出現(xiàn)次數(shù)要多，既然 M 不是頻繁集，那么 M∪m 就更不可能是頻繁項(xiàng)集了。所以 M 的任意超級(jí)都不可能是頻繁項(xiàng)集。這樣也即能得出，頻繁項(xiàng)集的所有子集都肯定是頻繁項(xiàng)集。

這一性質(zhì)還有另外一個(gè)名詞，叫做反單調(diào)性，即如果一個(gè)項(xiàng)不是頻繁的，那么它的所有超集都不可能是頻繁的。

2 算法改進(jìn)的概述

本改進(jìn)算法主要是針對(duì) Apriori 算法的幾個(gè)性質(zhì)進(jìn)行的。首先對(duì) Apriori 的幾個(gè)算法的性質(zhì)進(jìn)行簡單介紹：

1）如果設(shè) Lk-1 是頻繁 （k-1）-項(xiàng)集項(xiàng)集，Ik 是頻繁 k-項(xiàng)集。那么 Ik-1 中包含的 Ik 的 （k-1）-項(xiàng)子集的個(gè)數(shù)一定不大于或等于 k。如果不大于，那么 Ik 就肯定不是頻繁項(xiàng)集。

2）當(dāng)要挖掘頻繁 （k+1）-項(xiàng)集時(shí)，就可以將數(shù)據(jù)庫中長度小于等于 k 的項(xiàng)進(jìn)行刪除。endprint

3）如果當(dāng)頻繁 k-項(xiàng)集的長度不大于 k+1 時(shí)，那么源數(shù)據(jù)庫中最大頻繁項(xiàng)集的長度為 k。

改進(jìn)的Apriori具體的算法

1）掃描數(shù)據(jù)庫 D，建立矩陣 R

首先給出數(shù)據(jù)庫的幾個(gè)集合：

事務(wù)數(shù)據(jù)庫 D={T1，T2，...，Tm}，這里，數(shù)據(jù)庫中事務(wù)的個(gè)數(shù)有 m 個(gè)；

項(xiàng)目集 I={I1，I2，...，In}，這里，項(xiàng)目集中項(xiàng)目的個(gè)數(shù)有 n 個(gè)。

首先，根據(jù)事物數(shù)據(jù)庫建立布爾矩陣 R。由布爾矩陣定義可知，該矩陣中的元素只有“0”和“1”。這里的“0”和“1”設(shè)置方法如下：

將行向量設(shè)為事務(wù) T，將列向量設(shè)為項(xiàng)i。當(dāng)一個(gè)項(xiàng)出現(xiàn)在某一事務(wù) T 中，那么就將該項(xiàng)所在的行與改事務(wù)所在的列所指向的位置設(shè)為1，若不出現(xiàn)，則設(shè)為0。然后再在建立的矩陣后面分別在加一行一列，行來寫入每個(gè)鄉(xiāng)的支持度，而列用來寫入每個(gè)項(xiàng)的編碼。

生成布爾矩陣R（m+2）·（n+1）具體算法如下：

for（j=1；j

{

R[0][j]=j； //填充項(xiàng)編號(hào)行

R[m+1][j] =0； //填充 sum_c 行，初值為 0

}

for（i=1；i<=m；i++）

{ sum_r=0； //項(xiàng)支持度初值為 0

for（j=1；j<=n；j++） //將 j 從1到 n 進(jìn)行循環(huán)

if （ij in Ti） //若 ij 在事務(wù) Ti 中

{ R[i][j]=1； // 將矩陣中的元素設(shè)為“1”

sum_r++； //統(tǒng)計(jì)支持度

R[m+1][j]++； //統(tǒng)計(jì)行的項(xiàng)數(shù)

}

else R[i][j]=0； // 若ij不在事務(wù)Ti中

R[i][0]=sum_r； //則將布爾矩陣中元素設(shè)為“0”

}

2）用函數(shù) min_supsh=ceiling（min_sup*m）（ ceilong 的作用是計(jì)算大于或等于 min_sup*m 的整數(shù)）來計(jì)算項(xiàng)的支持?jǐn)?shù)。刪除 sum_c 中比最小支持?jǐn)?shù) min_supsh 小的項(xiàng)，經(jīng)刪除后的項(xiàng)目集就是頻繁項(xiàng)集。此時(shí)得出 sum_r 的結(jié)果，然后再對(duì)表中元素等于 0 的項(xiàng)進(jìn)行篩選。

3）k=2；

4）應(yīng)用 Apriori 算法的性質(zhì)，對(duì)上面所得到的表進(jìn)行壓縮。壓縮方式如下：掃描列 sum_r，找出其中小于 k 的元素，因?yàn)樗豢赡艹蔀轭l繁項(xiàng)集，所以可以將其刪除；再掃描行sum_c，找出其中小于最小支持?jǐn)?shù) min_supsh 的元素，因?yàn)樗膊豢赡艹蔀轭l繁項(xiàng)集，所以可以及將其進(jìn)行刪除；然后再先掃描列 sum_r，再掃描行 sum_c，再進(jìn)行刪除操作，這樣反復(fù)的操作，一直刪除，知道不能再刪除為止。

5）求頻繁k-項(xiàng)集。將頻繁 （k-1）-項(xiàng)集經(jīng)過自連接，生成 [P=Ck-1c_num-1]個(gè)候選項(xiàng)集，然后再將這些候選項(xiàng)集中的每個(gè)元素的列向量進(jìn)行與運(yùn)算，得出的向量中“1”的個(gè)數(shù)，就是該項(xiàng)集的支持度。最后刪除支持度小與于小支持度的項(xiàng)集，剩余的就是頻繁項(xiàng)集。

求頻繁 k-項(xiàng)集的主要代碼如下：

// R 為壓縮后的事物矩

// r_num 為 R 的行數(shù)，c-num 為 R 的列數(shù)

// L：頻繁k-項(xiàng)集

// W 數(shù)組存放 p 個(gè) k 維項(xiàng)組合對(duì)

for （a=0；a

{ sup_n=0； // k-項(xiàng)集支持度初值為 0

for（i=1；i

{

cj=1；

for（m=1；m<=k；m++）

{ cm=cm*R[i][W[p][j]]； //“與”運(yùn)算

if（cm==o） break；

}

Sup_n=suo_n+cj； //統(tǒng)計(jì) k-項(xiàng)集支持度

}

if sup_n>=min_supsh //為頻繁集

{ for（m=0；m

L[m]=R[0][W[p][m]]； //求 k維數(shù)組合的項(xiàng)數(shù)

Lk=Lk∪L；

}}

6）計(jì)算出|Kk|，若|Lk|>=k+1，k=k+1，跳轉(zhuǎn)到 4）；否則停止算法。

3 改進(jìn)的Apriori算法在用戶行為分析中的應(yīng)用

用戶行為分析是網(wǎng)絡(luò)信息檢索技術(shù)得以前進(jìn)的重要基石，也是能夠在商用搜索引擎中發(fā)揮重要作用的各種算法的基本出發(fā)點(diǎn)之一。為了更好的理解用戶的點(diǎn)擊行為，該文對(duì)亞馬遜某一段時(shí)間內(nèi)的70萬多條訪問記錄進(jìn)行了分析。該數(shù)據(jù)主要包含了在一段特定的時(shí)間內(nèi)，不同的用戶所訪問的網(wǎng)站代碼以及訪問的時(shí)間等。原始的部分?jǐn)?shù)據(jù)如圖2所示。

系統(tǒng)的硬件要求環(huán)境并不是很高，需要1臺(tái)性能一般的電腦便可以了。本系統(tǒng)的開發(fā)環(huán)境如下：

操作系統(tǒng)： window7；處理器：pentium r dualcore cpu T4200 ；主頻、內(nèi)存：2.00GHz，2G；數(shù)據(jù)源：亞馬遜訪問記錄；開發(fā)語言：c＼Java；開發(fā)平臺(tái)：Eclipse。

根據(jù)上一章節(jié)的算法設(shè)計(jì)，將使用新的關(guān)聯(lián)規(guī)則改進(jìn)算法對(duì)用戶網(wǎng)站訪問記錄進(jìn)行分析。首先是要對(duì)源數(shù)據(jù)進(jìn)行預(yù)處理，將沒有用的信息刪除，提取出要處理的有用信息，然后對(duì)提取出來的信息進(jìn)行規(guī)整，為下一步數(shù)據(jù)挖掘做好準(zhǔn)備。

亞馬遜用戶行為分析日志數(shù)據(jù)為 716064 條，經(jīng)過清理后的數(shù)據(jù)為 4254 條。

掃描數(shù)據(jù)庫 D，建立矩陣 R：

首先，根據(jù)事物數(shù)據(jù)庫建立布爾矩陣R。由布爾矩陣定義可知，該矩陣中的元素只有“0”和“1”。這里的“0”和“1”設(shè)置方法為：將行向量設(shè)為事務(wù) T，將列向量設(shè)為項(xiàng) i。當(dāng)一個(gè)項(xiàng)出現(xiàn)在某一事務(wù) T 中，那么就將該項(xiàng)所在的行與改事務(wù)所在的列所指向的位置設(shè)為1，若不出現(xiàn)，則設(shè)為0。然后再在建立的矩陣后面分別在加一行一列，行來寫入每個(gè)鄉(xiāng)的支持度，而列用來寫入每個(gè)項(xiàng)的編碼。

然后，計(jì)算出每個(gè)項(xiàng)集的支持度。計(jì)算最小支持度是通過用函數(shù) ceiling 來進(jìn)行。該函數(shù)是通過計(jì)算每個(gè)列中“1”的個(gè)數(shù)來進(jìn)行對(duì)支持度的計(jì)算的。

最后應(yīng)用 Apriori 算法的性質(zhì)，對(duì)上面所得到的表進(jìn)行壓縮。壓縮方式如下：掃描列 sum_r，找出其中小于 k 的元素，因?yàn)樗豢赡艹蔀轭l繁項(xiàng)集，所以可以將其刪除；再掃描行 sum_c，找出其中小于最小支持?jǐn)?shù) min_supsh 的元素，因?yàn)樗膊豢赡艹蔀轭l繁項(xiàng)集，所以可以及將其進(jìn)行刪除；然后再先掃描列sum_r，再掃描行 sum_c，再進(jìn)行刪除操作，這樣反復(fù)的操作，一直刪除，知道不能再刪除為止。最后計(jì)算出|Lk|，若|Lk|>=k+1，K=K+1，繼續(xù)掃描；否則停止算法。

經(jīng)挖掘后的規(guī)則如表 1 與表 2 所示。其中表 5.1中，第一列為序號(hào)，第二列為頁面代碼，這張表所表示的是每個(gè)頁面代碼所對(duì)應(yīng)的序號(hào)，即頁面“11044”所對(duì)應(yīng)的序號(hào)為 1。

表 2 中，第一列為強(qiáng)規(guī)則，第二列為強(qiáng)規(guī)則所對(duì)應(yīng)的權(quán)值。在這里，設(shè)定當(dāng)權(quán)值大于 1 時(shí)，所對(duì)應(yīng)的規(guī)則為強(qiáng)規(guī)則。

當(dāng)支持度取不同值（sup=0.1%、sup=0.5%、sup=1%、sup=2%）時(shí)，強(qiáng)關(guān)聯(lián)規(guī)則輸出有向圖如圖 3 所示。

從圖 3 可以看出，隨著設(shè)定的最小支持度的不斷變大，得到的規(guī)則越來越少。而不管最小支持度怎么變化，得出的總體趨勢(shì)不變，都是以固定幾個(gè)主要的點(diǎn)向外出發(fā)。從實(shí)際情況出發(fā)，就可以知道，這幾個(gè)網(wǎng)址之間的點(diǎn)擊就是用戶點(diǎn)擊行為做頻繁的。在調(diào)整頁面設(shè)置時(shí)，就可以將這些網(wǎng)址鏈接放在一起，這樣就能夠很好地提高用戶的點(diǎn)擊率。

4 性能分析

對(duì)時(shí)間復(fù)雜度的分析：本改進(jìn)算法通過掃描一次數(shù)據(jù)庫，將數(shù)據(jù)庫中信息映射到布爾型數(shù)據(jù)表中，以后的所有操作都不在需要掃描數(shù)據(jù)庫，只要對(duì)布爾輸幾把進(jìn)行分析，極大地降低了掃描數(shù)據(jù)庫時(shí)所需的時(shí)間。而且在需找頻繁集時(shí)，只要對(duì)表中的“0”和“1”進(jìn)行操作，而不產(chǎn)生 Apriori 算法中所必須產(chǎn)生的候選項(xiàng)集，這樣就避免了 Apriori 算法中的最大瓶頸，降低了時(shí)間復(fù)雜度。

對(duì)空間復(fù)雜度的分析：由于本算法在一開始就將數(shù)據(jù)映射到布爾數(shù)據(jù)表中，所以，往后的操作都是對(duì)“0”和“1”進(jìn)行的，所以的源數(shù)據(jù)庫中的數(shù)據(jù)都是有“0”和“1”表示的，而存儲(chǔ)“0”和“1”所需要的空間遠(yuǎn)比原始數(shù)據(jù)要來的少，這樣就減少了空間的占有量。

5 結(jié)束語

雖然改進(jìn)的基于用戶行為分析的興趣數(shù)據(jù)挖掘系統(tǒng)在工作效率上有所提高，但是還是存在一些問題需要解決：

1） 通過改進(jìn)系統(tǒng)算法，提升了基于用戶行為分析的興趣數(shù)據(jù)挖掘系統(tǒng)的工作效率，但是提升幅度有限，算法和系統(tǒng)性能仍有進(jìn)一步優(yōu)化和改進(jìn)的空間。

2） 改進(jìn)的基于用戶行為分析的興趣數(shù)據(jù)挖掘系統(tǒng)處理所得到結(jié)果只可以為 Boolean 型（即真假），不能為用戶產(chǎn)生量化的結(jié)果，也就是說無法在“真”的基礎(chǔ)上給出程度的表示。

3） 系統(tǒng)相關(guān)的初始數(shù)據(jù)需要更新與豐富。系統(tǒng)中用來得到用戶興趣信息的用戶訓(xùn)練數(shù)據(jù)和用戶興趣表都需要進(jìn)一步的豐富和完善，從而使得訓(xùn)練完成后，系統(tǒng)能給出更加準(zhǔn)確的處理結(jié)果。

參考文獻(xiàn)：

[1] 陸楠.關(guān)聯(lián)規(guī)則的挖掘及其算法的研究[D].長春：吉林大學(xué)， 2007.

[2] 伊衛(wèi)國.基于關(guān)聯(lián)規(guī)則與決策樹的預(yù)測(cè)方法研究及其應(yīng)用[D].大連：大連海事大學(xué)， 2012.

[3] Fayyad U M， Piatetsky-Shapiro G， Smyth P， et al.Advances in knowledge discovery and data mining[J].1996.

[4] Agrawal R，Srikant R.Fast algorithms for mining association rules[C].Proc. 20th int. conf. very large data bases， VLDB，1994，1215： 487-499.

[5] 魏茂林. Apriori 算法的改進(jìn)及其在教育決策系統(tǒng)中的應(yīng)用[D].長春：吉林大學(xué)，2010.

[6] Agrawal R， Srikant R. Fast algorithms for mining association rules[C].Proc. 20th int. conf. very large data bases， VLDB，1994， 1215： 487-499.

[7] 李超，余昭平.基于矩陣的 Apriori 算法改進(jìn)[J].計(jì)算機(jī)工程，2006，32（23）：68-69.

[8] 曾萬聃，周緒波，戴勃，等.關(guān)聯(lián)規(guī)則挖掘的矩陣算法[J].計(jì)算機(jī)工程，2006，32（2）：45-47.endprint

亞馬遜用戶行為分析日志數(shù)據(jù)為 716064 條，經(jīng)過清理后的數(shù)據(jù)為 4254 條。

掃描數(shù)據(jù)庫 D，建立矩陣 R：

首先，根據(jù)事物數(shù)據(jù)庫建立布爾矩陣R。由布爾矩陣定義可知，該矩陣中的元素只有“0”和“1”。這里的“0”和“1”設(shè)置方法為：將行向量設(shè)為事務(wù) T，將列向量設(shè)為項(xiàng) i。當(dāng)一個(gè)項(xiàng)出現(xiàn)在某一事務(wù) T 中，那么就將該項(xiàng)所在的行與改事務(wù)所在的列所指向的位置設(shè)為1，若不出現(xiàn)，則設(shè)為0。然后再在建立的矩陣后面分別在加一行一列，行來寫入每個(gè)鄉(xiāng)的支持度，而列用來寫入每個(gè)項(xiàng)的編碼。

然后，計(jì)算出每個(gè)項(xiàng)集的支持度。計(jì)算最小支持度是通過用函數(shù) ceiling 來進(jìn)行。該函數(shù)是通過計(jì)算每個(gè)列中“1”的個(gè)數(shù)來進(jìn)行對(duì)支持度的計(jì)算的。

最后應(yīng)用 Apriori 算法的性質(zhì)，對(duì)上面所得到的表進(jìn)行壓縮。壓縮方式如下：掃描列 sum_r，找出其中小于 k 的元素，因?yàn)樗豢赡艹蔀轭l繁項(xiàng)集，所以可以將其刪除；再掃描行 sum_c，找出其中小于最小支持?jǐn)?shù) min_supsh 的元素，因?yàn)樗膊豢赡艹蔀轭l繁項(xiàng)集，所以可以及將其進(jìn)行刪除；然后再先掃描列sum_r，再掃描行 sum_c，再進(jìn)行刪除操作，這樣反復(fù)的操作，一直刪除，知道不能再刪除為止。最后計(jì)算出|Lk|，若|Lk|>=k+1，K=K+1，繼續(xù)掃描；否則停止算法。

經(jīng)挖掘后的規(guī)則如表 1 與表 2 所示。其中表 5.1中，第一列為序號(hào)，第二列為頁面代碼，這張表所表示的是每個(gè)頁面代碼所對(duì)應(yīng)的序號(hào)，即頁面“11044”所對(duì)應(yīng)的序號(hào)為 1。

表 2 中，第一列為強(qiáng)規(guī)則，第二列為強(qiáng)規(guī)則所對(duì)應(yīng)的權(quán)值。在這里，設(shè)定當(dāng)權(quán)值大于 1 時(shí)，所對(duì)應(yīng)的規(guī)則為強(qiáng)規(guī)則。

當(dāng)支持度取不同值（sup=0.1%、sup=0.5%、sup=1%、sup=2%）時(shí)，強(qiáng)關(guān)聯(lián)規(guī)則輸出有向圖如圖 3 所示。

從圖 3 可以看出，隨著設(shè)定的最小支持度的不斷變大，得到的規(guī)則越來越少。而不管最小支持度怎么變化，得出的總體趨勢(shì)不變，都是以固定幾個(gè)主要的點(diǎn)向外出發(fā)。從實(shí)際情況出發(fā)，就可以知道，這幾個(gè)網(wǎng)址之間的點(diǎn)擊就是用戶點(diǎn)擊行為做頻繁的。在調(diào)整頁面設(shè)置時(shí)，就可以將這些網(wǎng)址鏈接放在一起，這樣就能夠很好地提高用戶的點(diǎn)擊率。

4 性能分析

對(duì)時(shí)間復(fù)雜度的分析：本改進(jìn)算法通過掃描一次數(shù)據(jù)庫，將數(shù)據(jù)庫中信息映射到布爾型數(shù)據(jù)表中，以后的所有操作都不在需要掃描數(shù)據(jù)庫，只要對(duì)布爾輸幾把進(jìn)行分析，極大地降低了掃描數(shù)據(jù)庫時(shí)所需的時(shí)間。而且在需找頻繁集時(shí)，只要對(duì)表中的“0”和“1”進(jìn)行操作，而不產(chǎn)生 Apriori 算法中所必須產(chǎn)生的候選項(xiàng)集，這樣就避免了 Apriori 算法中的最大瓶頸，降低了時(shí)間復(fù)雜度。

對(duì)空間復(fù)雜度的分析：由于本算法在一開始就將數(shù)據(jù)映射到布爾數(shù)據(jù)表中，所以，往后的操作都是對(duì)“0”和“1”進(jìn)行的，所以的源數(shù)據(jù)庫中的數(shù)據(jù)都是有“0”和“1”表示的，而存儲(chǔ)“0”和“1”所需要的空間遠(yuǎn)比原始數(shù)據(jù)要來的少，這樣就減少了空間的占有量。

5 結(jié)束語

雖然改進(jìn)的基于用戶行為分析的興趣數(shù)據(jù)挖掘系統(tǒng)在工作效率上有所提高，但是還是存在一些問題需要解決：

1） 通過改進(jìn)系統(tǒng)算法，提升了基于用戶行為分析的興趣數(shù)據(jù)挖掘系統(tǒng)的工作效率，但是提升幅度有限，算法和系統(tǒng)性能仍有進(jìn)一步優(yōu)化和改進(jìn)的空間。

2） 改進(jìn)的基于用戶行為分析的興趣數(shù)據(jù)挖掘系統(tǒng)處理所得到結(jié)果只可以為 Boolean 型（即真假），不能為用戶產(chǎn)生量化的結(jié)果，也就是說無法在“真”的基礎(chǔ)上給出程度的表示。

3） 系統(tǒng)相關(guān)的初始數(shù)據(jù)需要更新與豐富。系統(tǒng)中用來得到用戶興趣信息的用戶訓(xùn)練數(shù)據(jù)和用戶興趣表都需要進(jìn)一步的豐富和完善，從而使得訓(xùn)練完成后，系統(tǒng)能給出更加準(zhǔn)確的處理結(jié)果。

參考文獻(xiàn)：

[1] 陸楠.關(guān)聯(lián)規(guī)則的挖掘及其算法的研究[D].長春：吉林大學(xué)， 2007.

[2] 伊衛(wèi)國.基于關(guān)聯(lián)規(guī)則與決策樹的預(yù)測(cè)方法研究及其應(yīng)用[D].大連：大連海事大學(xué)， 2012.

[3] Fayyad U M， Piatetsky-Shapiro G， Smyth P， et al.Advances in knowledge discovery and data mining[J].1996.

[4] Agrawal R，Srikant R.Fast algorithms for mining association rules[C].Proc. 20th int. conf. very large data bases， VLDB，1994，1215： 487-499.

[5] 魏茂林. Apriori 算法的改進(jìn)及其在教育決策系統(tǒng)中的應(yīng)用[D].長春：吉林大學(xué)，2010.

[6] Agrawal R， Srikant R. Fast algorithms for mining association rules[C].Proc. 20th int. conf. very large data bases， VLDB，1994， 1215： 487-499.

[7] 李超，余昭平.基于矩陣的 Apriori 算法改進(jìn)[J].計(jì)算機(jī)工程，2006，32（23）：68-69.

[8] 曾萬聃，周緒波，戴勃，等.關(guān)聯(lián)規(guī)則挖掘的矩陣算法[J].計(jì)算機(jī)工程，2006，32（2）：45-47.endprint

亞馬遜用戶行為分析日志數(shù)據(jù)為 716064 條，經(jīng)過清理后的數(shù)據(jù)為 4254 條。

掃描數(shù)據(jù)庫 D，建立矩陣 R：

首先，根據(jù)事物數(shù)據(jù)庫建立布爾矩陣R。由布爾矩陣定義可知，該矩陣中的元素只有“0”和“1”。這里的“0”和“1”設(shè)置方法為：將行向量設(shè)為事務(wù) T，將列向量設(shè)為項(xiàng) i。當(dāng)一個(gè)項(xiàng)出現(xiàn)在某一事務(wù) T 中，那么就將該項(xiàng)所在的行與改事務(wù)所在的列所指向的位置設(shè)為1，若不出現(xiàn)，則設(shè)為0。然后再在建立的矩陣后面分別在加一行一列，行來寫入每個(gè)鄉(xiāng)的支持度，而列用來寫入每個(gè)項(xiàng)的編碼。

然后，計(jì)算出每個(gè)項(xiàng)集的支持度。計(jì)算最小支持度是通過用函數(shù) ceiling 來進(jìn)行。該函數(shù)是通過計(jì)算每個(gè)列中“1”的個(gè)數(shù)來進(jìn)行對(duì)支持度的計(jì)算的。

最后應(yīng)用 Apriori 算法的性質(zhì)，對(duì)上面所得到的表進(jìn)行壓縮。壓縮方式如下：掃描列 sum_r，找出其中小于 k 的元素，因?yàn)樗豢赡艹蔀轭l繁項(xiàng)集，所以可以將其刪除；再掃描行 sum_c，找出其中小于最小支持?jǐn)?shù) min_supsh 的元素，因?yàn)樗膊豢赡艹蔀轭l繁項(xiàng)集，所以可以及將其進(jìn)行刪除；然后再先掃描列sum_r，再掃描行 sum_c，再進(jìn)行刪除操作，這樣反復(fù)的操作，一直刪除，知道不能再刪除為止。最后計(jì)算出|Lk|，若|Lk|>=k+1，K=K+1，繼續(xù)掃描；否則停止算法。

經(jīng)挖掘后的規(guī)則如表 1 與表 2 所示。其中表 5.1中，第一列為序號(hào)，第二列為頁面代碼，這張表所表示的是每個(gè)頁面代碼所對(duì)應(yīng)的序號(hào)，即頁面“11044”所對(duì)應(yīng)的序號(hào)為 1。

表 2 中，第一列為強(qiáng)規(guī)則，第二列為強(qiáng)規(guī)則所對(duì)應(yīng)的權(quán)值。在這里，設(shè)定當(dāng)權(quán)值大于 1 時(shí)，所對(duì)應(yīng)的規(guī)則為強(qiáng)規(guī)則。

當(dāng)支持度取不同值（sup=0.1%、sup=0.5%、sup=1%、sup=2%）時(shí)，強(qiáng)關(guān)聯(lián)規(guī)則輸出有向圖如圖 3 所示。

從圖 3 可以看出，隨著設(shè)定的最小支持度的不斷變大，得到的規(guī)則越來越少。而不管最小支持度怎么變化，得出的總體趨勢(shì)不變，都是以固定幾個(gè)主要的點(diǎn)向外出發(fā)。從實(shí)際情況出發(fā)，就可以知道，這幾個(gè)網(wǎng)址之間的點(diǎn)擊就是用戶點(diǎn)擊行為做頻繁的。在調(diào)整頁面設(shè)置時(shí)，就可以將這些網(wǎng)址鏈接放在一起，這樣就能夠很好地提高用戶的點(diǎn)擊率。

4 性能分析

對(duì)時(shí)間復(fù)雜度的分析：本改進(jìn)算法通過掃描一次數(shù)據(jù)庫，將數(shù)據(jù)庫中信息映射到布爾型數(shù)據(jù)表中，以后的所有操作都不在需要掃描數(shù)據(jù)庫，只要對(duì)布爾輸幾把進(jìn)行分析，極大地降低了掃描數(shù)據(jù)庫時(shí)所需的時(shí)間。而且在需找頻繁集時(shí)，只要對(duì)表中的“0”和“1”進(jìn)行操作，而不產(chǎn)生 Apriori 算法中所必須產(chǎn)生的候選項(xiàng)集，這樣就避免了 Apriori 算法中的最大瓶頸，降低了時(shí)間復(fù)雜度。

對(duì)空間復(fù)雜度的分析：由于本算法在一開始就將數(shù)據(jù)映射到布爾數(shù)據(jù)表中，所以，往后的操作都是對(duì)“0”和“1”進(jìn)行的，所以的源數(shù)據(jù)庫中的數(shù)據(jù)都是有“0”和“1”表示的，而存儲(chǔ)“0”和“1”所需要的空間遠(yuǎn)比原始數(shù)據(jù)要來的少，這樣就減少了空間的占有量。

5 結(jié)束語

雖然改進(jìn)的基于用戶行為分析的興趣數(shù)據(jù)挖掘系統(tǒng)在工作效率上有所提高，但是還是存在一些問題需要解決：

1） 通過改進(jìn)系統(tǒng)算法，提升了基于用戶行為分析的興趣數(shù)據(jù)挖掘系統(tǒng)的工作效率，但是提升幅度有限，算法和系統(tǒng)性能仍有進(jìn)一步優(yōu)化和改進(jìn)的空間。

2） 改進(jìn)的基于用戶行為分析的興趣數(shù)據(jù)挖掘系統(tǒng)處理所得到結(jié)果只可以為 Boolean 型（即真假），不能為用戶產(chǎn)生量化的結(jié)果，也就是說無法在“真”的基礎(chǔ)上給出程度的表示。

3） 系統(tǒng)相關(guān)的初始數(shù)據(jù)需要更新與豐富。系統(tǒng)中用來得到用戶興趣信息的用戶訓(xùn)練數(shù)據(jù)和用戶興趣表都需要進(jìn)一步的豐富和完善，從而使得訓(xùn)練完成后，系統(tǒng)能給出更加準(zhǔn)確的處理結(jié)果。

參考文獻(xiàn)：

[1] 陸楠.關(guān)聯(lián)規(guī)則的挖掘及其算法的研究[D].長春：吉林大學(xué)， 2007.

[2] 伊衛(wèi)國.基于關(guān)聯(lián)規(guī)則與決策樹的預(yù)測(cè)方法研究及其應(yīng)用[D].大連：大連海事大學(xué)， 2012.

[3] Fayyad U M， Piatetsky-Shapiro G， Smyth P， et al.Advances in knowledge discovery and data mining[J].1996.

[4] Agrawal R，Srikant R.Fast algorithms for mining association rules[C].Proc. 20th int. conf. very large data bases， VLDB，1994，1215： 487-499.

[5] 魏茂林. Apriori 算法的改進(jìn)及其在教育決策系統(tǒng)中的應(yīng)用[D].長春：吉林大學(xué)，2010.

[6] Agrawal R， Srikant R. Fast algorithms for mining association rules[C].Proc. 20th int. conf. very large data bases， VLDB，1994， 1215： 487-499.

[7] 李超，余昭平.基于矩陣的 Apriori 算法改進(jìn)[J].計(jì)算機(jī)工程，2006，32（23）：68-69.

[8] 曾萬聃，周緒波，戴勃，等.關(guān)聯(lián)規(guī)則挖掘的矩陣算法[J].計(jì)算機(jī)工程，2006，32（2）：45-47.endprint