基于矩陣約簡(jiǎn)的Apriori 算法改進(jìn)

任偉建，于博文

(東北石油大學(xué)電氣信息工程學(xué)院，黑龍江 大慶 163318)

0 引言

關(guān)聯(lián)規(guī)則的挖掘是數(shù)據(jù)挖掘領(lǐng)域中的一個(gè)重要研究方向，旨在從海量數(shù)據(jù)中發(fā)現(xiàn)隱藏的關(guān)聯(lián)關(guān)系、人們感興趣的數(shù)據(jù)集合和與指定數(shù)據(jù)相關(guān)聯(lián)的數(shù)據(jù)，來(lái)輔助人們快速做出決策。Apriori 算法則是挖掘關(guān)聯(lián)規(guī)則的經(jīng)典算法，其核心思想是通過(guò)掃描數(shù)據(jù)來(lái)獲取頻繁項(xiàng)集，然后根據(jù)得到的頻繁項(xiàng)集生成關(guān)聯(lián)規(guī)則。但Apriori 算法自身存在2 個(gè)主要缺陷［1］:1)Apriori 算法需要多次地重復(fù)掃描數(shù)據(jù)庫(kù)，當(dāng)有海量數(shù)據(jù)信息時(shí)會(huì)造成嚴(yán)重的輸入輸出負(fù)載;2)在查找頻繁項(xiàng)集時(shí)會(huì)生成很多無(wú)實(shí)際操作價(jià)值的候選項(xiàng)集，占據(jù)大量存儲(chǔ)空間。

許多學(xué)者針對(duì)Apriori 算法的現(xiàn)有缺陷提出了諸多改進(jìn)思路，以提高Apriori 算法的執(zhí)行效率。在文獻(xiàn)［1］中，提出了基于數(shù)組的挖掘方法，降低了掃描數(shù)據(jù)庫(kù)的次數(shù)，將多維數(shù)據(jù)存儲(chǔ)在與之對(duì)應(yīng)的數(shù)組中，在查找k-項(xiàng)集時(shí)，只需對(duì)數(shù)組維數(shù)不小于k 的數(shù)組進(jìn)行掃描，但其依舊有大量的重復(fù)掃描操作，效率較低。在文獻(xiàn)［2］中，提出基于向量的挖掘算法，該算法需要將數(shù)據(jù)中的事物和項(xiàng)目采用向量表示，通過(guò)遍歷獲取頻繁k-項(xiàng)集，但所轉(zhuǎn)換的向量占據(jù)了大量的存儲(chǔ)空間。在文獻(xiàn)［3］中，提出基于矩陣的挖掘算法，算法將數(shù)據(jù)信息轉(zhuǎn)換成矩陣形式，其原事務(wù)轉(zhuǎn)換為行，原項(xiàng)集轉(zhuǎn)換為列，在矩陣中可以一次性生成所有頻繁集或者候選集，但該算法同時(shí)也會(huì)生成大量沒(méi)有操作價(jià)值的候選集。

綜合上述算法，本文提出一種基于矩陣約簡(jiǎn)的Apriori 改進(jìn)算法，通過(guò)對(duì)數(shù)據(jù)庫(kù)進(jìn)行一次掃描，建立與數(shù)據(jù)庫(kù)對(duì)應(yīng)的事務(wù)布爾矩陣，無(wú)需再對(duì)數(shù)據(jù)庫(kù)進(jìn)行掃描，降低原Apriori 算法對(duì)數(shù)據(jù)庫(kù)掃描的次數(shù)，以及數(shù)據(jù)庫(kù)的輸入輸出負(fù)載;用計(jì)算速度較快的向量間“與”運(yùn)算和對(duì)矩陣的約簡(jiǎn)，簡(jiǎn)化原算法中的連接和剪枝步驟，減少候選項(xiàng)集的生成個(gè)數(shù);隨著頻繁k-項(xiàng)集的生成，k 值越大其所對(duì)應(yīng)的矩陣結(jié)構(gòu)越簡(jiǎn)單，從而提高算法的執(zhí)行效率。

1 關(guān)聯(lián)規(guī)則Apriori 算法分析

Apriori 采用傳統(tǒng)的迭代算法，通過(guò)頻繁k-項(xiàng)來(lái)生成頻繁(k +1)-項(xiàng)集。算法首先需要確定頻繁1-項(xiàng)集，利用生成的頻繁1-項(xiàng)集去找尋頻繁2-項(xiàng)集，再利用生成的頻繁2-項(xiàng)集去找尋頻繁3-項(xiàng)集，以此類(lèi)推，直到無(wú)法找到頻繁k-項(xiàng)集，在算法執(zhí)行的過(guò)程中查找每個(gè)頻繁項(xiàng)集都會(huì)對(duì)數(shù)據(jù)庫(kù)進(jìn)行一次掃描。

Apriori 算法中，頻繁項(xiàng)集中所有的非空子集都為頻繁項(xiàng)集，算法根據(jù)這一特性查找頻繁項(xiàng)集。在算法的連接步驟中將2 個(gè)頻繁(k-1)-項(xiàng)集連接產(chǎn)生大量的候選項(xiàng)集，在算法的剪枝步驟中利用頻繁項(xiàng)集的特性除去那些包含非頻繁項(xiàng)集的候選項(xiàng)集，生成頻繁k-項(xiàng)集。算法在每次連接和剪枝的過(guò)程中都會(huì)掃描多次數(shù)據(jù)庫(kù)，假設(shè)生成的頻繁項(xiàng)集中包含m-項(xiàng)集，在此過(guò)程中則需要對(duì)數(shù)據(jù)庫(kù)進(jìn)行m 次掃描，大大增加了輸入輸出負(fù)載。在隨后的算法迭代過(guò)程中候選項(xiàng)集的個(gè)數(shù)成指數(shù)級(jí)增長(zhǎng)，將會(huì)生成大量無(wú)實(shí)際操作價(jià)值的候選項(xiàng)集，很大程度影響了Apriori 算法的執(zhí)行效率。

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

2.1 定理證明

項(xiàng)目數(shù)和支持?jǐn)?shù):在數(shù)據(jù)庫(kù)DB 對(duì)應(yīng)的“0”、“1”矩陣中，每一行代表一個(gè)事務(wù)，所以該行中“1”出現(xiàn)的次數(shù)即為該事務(wù)中的項(xiàng)目數(shù)。每一列代表一個(gè)項(xiàng)目，所以該列中“1”出現(xiàn)的次數(shù)即為該項(xiàng)目的支持?jǐn)?shù)。通過(guò)對(duì)矩陣中的列向量進(jìn)行與運(yùn)算即可求得該項(xiàng)目的支持?jǐn)?shù)。

1)DB 中的項(xiàng)集Ij為:

2)項(xiàng)集Ij的支持?jǐn)?shù)為:

3)2-項(xiàng)集{Ii，Ij}的內(nèi)積為:

4)2-項(xiàng)集{Ii，Ij}支持?jǐn)?shù)為:

5)k-項(xiàng)集{Ii，Ij，...，Ik}的內(nèi)積為:

6)k-項(xiàng)集支持?jǐn)?shù)為:

筆者根據(jù)項(xiàng)目數(shù)和支持?jǐn)?shù)的概念及Apriori 算法的性質(zhì)，給出如下定理:

定理1 矩陣中項(xiàng)Ij在頻繁(k-1)-項(xiàng)集出現(xiàn)的重復(fù)次數(shù)若小于k-1，則可以直接從矩陣中去除與該項(xiàng)所對(duì)應(yīng)的列。

證明:如果頻繁(k-1)-項(xiàng)集中包含的候選(k-1)-項(xiàng)集子集的個(gè)數(shù)小于k，則k-項(xiàng)集不是最大頻繁項(xiàng)集。由此得出頻繁k-項(xiàng)集的集合元素在k-1 維數(shù)的頻繁集出現(xiàn)的次數(shù)大于等于k-1。通過(guò)除去Ij所對(duì)應(yīng)列的矩陣驗(yàn)證，在頻繁(k-1)-項(xiàng)集中每個(gè)項(xiàng)集Ij出現(xiàn)的累積數(shù)都為k，從而說(shuō)明含有Ij的k-1 候選項(xiàng)集都包含在頻繁(k-1)-項(xiàng)集中，所以刪除該列對(duì)挖掘結(jié)果沒(méi)有影響。

定理2 在矩陣中若某一行的項(xiàng)目數(shù)小于k，則在求頻繁k-項(xiàng)集時(shí)，可以直接刪除該行。

證明:因?yàn)樵谇箢l繁k-項(xiàng)集的支持度時(shí)需要進(jìn)行矩陣內(nèi)列之間的與運(yùn)算，計(jì)算與運(yùn)算時(shí)只有所有元素均為“1”時(shí)，輸出結(jié)果才為“1”。如果某行的項(xiàng)目數(shù)小于k，則該行中對(duì)應(yīng)“1”的元素?cái)?shù)必定小于k，在與其他行計(jì)算與運(yùn)算項(xiàng)集的項(xiàng)目數(shù)必定小于k，因此可以直接刪除該行。

定理3 當(dāng)頻繁k-項(xiàng)集集合中項(xiàng)集的個(gè)數(shù)小于(k+1)，則稱(chēng)頻繁k-項(xiàng)集為最大頻繁項(xiàng)集。

證明:在候選項(xiàng)集中的非空子集的支持?jǐn)?shù)大于等于最小支持?jǐn)?shù)的項(xiàng)集即為頻繁項(xiàng)集，頻繁項(xiàng)集中不在被其他項(xiàng)集包括在內(nèi)的即為最大頻繁項(xiàng)集。根據(jù)頻繁項(xiàng)集的子集一定為頻繁項(xiàng)集這一性質(zhì)，頻繁(k +1)-項(xiàng)集的一定有頻繁k-項(xiàng)子集，而頻繁(k+1)-項(xiàng)集的頻繁k-項(xiàng)子集一定不少于=k +1)個(gè)。如果頻繁k-項(xiàng)子集的個(gè)數(shù)小于k +1，則該事務(wù)數(shù)據(jù)庫(kù)的最大頻繁項(xiàng)集為頻繁k-項(xiàng)集。

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

由于Apriori 算法存在重復(fù)掃描數(shù)據(jù)庫(kù)和產(chǎn)生大量無(wú)實(shí)際操作價(jià)值的候選項(xiàng)集的明顯缺陷，提出基于矩陣約簡(jiǎn)對(duì)Apriori 算法進(jìn)行改進(jìn)，用矩陣Rm×n代替原數(shù)據(jù)庫(kù)DB，根據(jù)上述項(xiàng)目數(shù)和支持?jǐn)?shù)進(jìn)行向量間運(yùn)算求取候選項(xiàng)集的支持?jǐn)?shù)，以此為依據(jù)確定頻繁項(xiàng)集;根據(jù)上述定理對(duì)矩陣進(jìn)行約簡(jiǎn)，簡(jiǎn)化原算法中的連接和剪枝步驟，降低數(shù)據(jù)庫(kù)的輸入輸出負(fù)載，提高生成頻繁項(xiàng)集的速度;為了提高算法效率，將矩陣中的各項(xiàng)按其支持?jǐn)?shù)降序排列。

2.2.1 頻繁k-項(xiàng)集的生成

根據(jù)上述改進(jìn)思路制定如下頻繁k-項(xiàng)集(k ＞2)的生成步驟:

1)首先掃描數(shù)據(jù)庫(kù)生成與數(shù)據(jù)庫(kù)對(duì)應(yīng)的“0”、“1”矩陣R，為了方便后續(xù)計(jì)算，矩陣行為事務(wù)，列為項(xiàng)集。將包含m 條事物和n 個(gè)項(xiàng)目的事物數(shù)據(jù)庫(kù)DB 轉(zhuǎn)換成事物矩陣Rm×n。

事物矩陣Rm×n中行代表事物，列代表項(xiàng)目，當(dāng)事物Wi中包含項(xiàng)目Ij時(shí)，矩陣中對(duì)應(yīng)的dij=1，否則dij=0。由于要對(duì)矩陣進(jìn)行化簡(jiǎn)，在矩陣后方添加一列用來(lái)計(jì)算行合計(jì)(sum_hang)，即事務(wù)項(xiàng)目數(shù);在矩陣下方添加一行用來(lái)計(jì)算列合計(jì)(lie_hang)，即項(xiàng)目支持?jǐn)?shù)。

2)根據(jù)所給支持度確定最小支持?jǐn)?shù)min_sup，通過(guò)向量間的“與”運(yùn)算計(jì)算各項(xiàng)的支持?jǐn)?shù)sup，對(duì)比矩陣的合計(jì)列數(shù)值，如果某項(xiàng)合計(jì)值小于min_sup，則刪除該項(xiàng)所對(duì)應(yīng)的矩陣列，余下的各項(xiàng)則是頻繁1-項(xiàng)集。重新計(jì)算矩陣的行合計(jì)，若某事務(wù)的合計(jì)值為0，可直接刪除該事務(wù)在矩陣中所對(duì)應(yīng)的行，重新排序得到矩陣D1。

3)對(duì)矩陣D1進(jìn)行結(jié)構(gòu)約簡(jiǎn)，以便生成新的頻繁k-項(xiàng)集。在生成頻繁k-項(xiàng)集時(shí)，根據(jù)定理1 從矩陣中除去頻繁(k-1)-項(xiàng)集中重復(fù)次數(shù)小于k 的項(xiàng)Ij所對(duì)應(yīng)的矩陣列。重新計(jì)算矩陣的行合計(jì)，根據(jù)定理2，若事務(wù)數(shù)目的合計(jì)值小于k，則刪除該事務(wù)在矩陣中所對(duì)應(yīng)的行。重新計(jì)算矩陣的列合計(jì)，某個(gè)列合計(jì)小于min_sup 則刪除矩陣中該元素所對(duì)應(yīng)的列;按上述步驟重復(fù)化簡(jiǎn)矩陣結(jié)構(gòu)，直到不能化簡(jiǎn)為止，得到矩陣Dk。

4)為了方便記錄生成頻繁k-項(xiàng)集的結(jié)果，為矩陣Dk設(shè)置一個(gè)輔助存儲(chǔ)矩陣(設(shè)計(jì)成N×3 的矩陣，第1 列用來(lái)存儲(chǔ)頻繁k-項(xiàng)集的組合，第2 列用來(lái)存儲(chǔ)事務(wù)支持?jǐn)?shù)，第3 列用來(lái)存儲(chǔ)項(xiàng)集個(gè)數(shù))，主要存儲(chǔ)頻繁項(xiàng)集的組合和其出現(xiàn)的次數(shù)。按照k-項(xiàng)集來(lái)組合所對(duì)應(yīng)的矩陣列，并一一對(duì)各個(gè)組合中的k 個(gè)向量進(jìn)行“與”運(yùn)算，然后統(tǒng)計(jì)“1”的個(gè)數(shù)，確定k-項(xiàng)集的支持?jǐn)?shù)。根據(jù)計(jì)算結(jié)果，若k-項(xiàng)集的支持?jǐn)?shù)大于等于min_sup，則該k-項(xiàng)集為頻繁k-項(xiàng)集。將結(jié)果存在輔助存儲(chǔ)矩陣中，按照其設(shè)計(jì)的方式存儲(chǔ)信息。

5)根據(jù)定理3，當(dāng)頻繁k-項(xiàng)集集合中項(xiàng)集的個(gè)數(shù)小于(k+1)，則稱(chēng)頻繁k-項(xiàng)集為最大頻繁項(xiàng)集，終止此查找頻繁項(xiàng)集的過(guò)程;若頻繁k-項(xiàng)集集合中項(xiàng)集的個(gè)數(shù)不小于(k+1)，則重復(fù)步驟3)～步驟4)直至滿足定理3 的條件。

通過(guò)上述步驟得到頻繁k-項(xiàng)集，有效降低了原Apriori 算法對(duì)數(shù)據(jù)庫(kù)的掃描次數(shù)，對(duì)矩陣的約簡(jiǎn)也避免了生成較多沒(méi)有操作價(jià)值的候選集。

2.2.2 算法流程

輸入:事務(wù)數(shù)據(jù)庫(kù)DB;最小支持?jǐn)?shù)min_sup

輸出:數(shù)據(jù)庫(kù)內(nèi)事物的關(guān)聯(lián)規(guī)則S

1)掃描事務(wù)數(shù)據(jù)庫(kù)DB，生成與原數(shù)據(jù)對(duì)應(yīng)的“0”、“1”矩陣R，計(jì)算矩陣R 的每一行及每一列中“1”的合計(jì)值，以此作為事務(wù)和項(xiàng)目的支持?jǐn)?shù)求取頻繁項(xiàng)集。刪除列合計(jì)小于最小支持?jǐn)?shù)的矩陣列，余下的即為頻繁1-項(xiàng)集所對(duì)應(yīng)的矩陣列，將矩陣列按支持?jǐn)?shù)降序排列組成矩陣R1。

2)從R1矩陣中抽取任意矩陣列進(jìn)行兩兩組合，通過(guò)向量間的“與”運(yùn)算求取該組合的支持?jǐn)?shù)，以此作為依據(jù)確定頻繁2-項(xiàng)集。然后根據(jù)定理1 和定理2 對(duì)矩陣R1進(jìn)行約簡(jiǎn)，重新排序后得到矩陣R2。

3)在確定頻繁k-項(xiàng)集時(shí)(k ＞2)，按照2.2.1 節(jié)中敘述的頻繁k-項(xiàng)集生成步驟3)～步驟5)執(zhí)行，直到算法生成的頻繁k-項(xiàng)集結(jié)果符合定理3，則此頻繁k-項(xiàng)集即為最大頻繁項(xiàng)集。

4)由頻繁項(xiàng)集L 所生成的其所有非空集S，若某個(gè)集合S 和頻繁集L 的支持?jǐn)?shù)比值大于預(yù)設(shè)定的最小置信度，則可以生成強(qiáng)關(guān)聯(lián)規(guī)則，即“S→L-S”。

2.3 算法分析

與傳統(tǒng)Apriori 算法進(jìn)行對(duì)比，改進(jìn)的Apriori 算法優(yōu)點(diǎn)如下:

1)通過(guò)上述算法的描述可以看出，改進(jìn)的Apriori 算法只需對(duì)數(shù)據(jù)庫(kù)進(jìn)行一次掃描，生成與原數(shù)據(jù)庫(kù)對(duì)應(yīng)的事物矩陣(Rm×n)，之后的操作都是基于矩陣完成的;在生成頻繁項(xiàng)集時(shí)，通過(guò)矩陣中列向量間的“與”運(yùn)算求取候選項(xiàng)集的支持?jǐn)?shù)，向量間計(jì)算的效率非常高的。根據(jù)項(xiàng)集組合的支持?jǐn)?shù)確定頻繁項(xiàng)集，生成頻繁k-項(xiàng)集的時(shí)間復(fù)雜度為O(mkn);傳統(tǒng)Apriori 算法在挖掘頻繁k-項(xiàng)集時(shí)需要掃描k 次數(shù)據(jù)庫(kù)，在“連接”和“剪枝”的過(guò)程中也需要重復(fù)掃描數(shù)據(jù)庫(kù)，增加了數(shù)據(jù)庫(kù)輸入輸出的負(fù)擔(dān)，這一過(guò)程浪費(fèi)了大量的系統(tǒng)資源，其生成頻繁k-項(xiàng)集的時(shí)間復(fù)雜度為O(Wk+1)，在實(shí)際應(yīng)用中w 的數(shù)值遠(yuǎn)遠(yuǎn)大于m;隨著頻繁k-項(xiàng)集的生成，k 值的增加使得與其對(duì)應(yīng)的矩陣Dk結(jié)構(gòu)越來(lái)越簡(jiǎn)單，減少相對(duì)不必要的計(jì)算量。

2)改進(jìn)的Apriori 算法采用“0”、“1”矩陣代表對(duì)應(yīng)的數(shù)據(jù)庫(kù)信息，算法中的布爾變量占用的存儲(chǔ)空間相對(duì)較少，大大減少數(shù)據(jù)信息所占用的存儲(chǔ)空間。傳統(tǒng)Apriori 算法在“連接”和“剪枝”的過(guò)程中產(chǎn)生大量的候選項(xiàng)集，造成了一定的存儲(chǔ)空間浪費(fèi)，而改進(jìn)的Apriori 算法在生成頻繁k-項(xiàng)集時(shí)，只需根據(jù)定理1和定理2 掃描行合計(jì)值大于等于k 的矩陣元素和矩陣中項(xiàng)在頻繁(k-1)-項(xiàng)集出現(xiàn)的重復(fù)次數(shù)大于等于k-1 的矩陣元素，其他不符合條件的矩陣元素可以直接刪除，對(duì)事務(wù)矩陣進(jìn)行了約簡(jiǎn)，縮小了候選項(xiàng)集的生成規(guī)模，比原有算法占據(jù)更少的存儲(chǔ)空間。

3)改進(jìn)的算法將原有的數(shù)據(jù)庫(kù)掃描過(guò)程轉(zhuǎn)換成對(duì)內(nèi)存的掃描，使數(shù)據(jù)掃描的效率得到了提高，并充分利用矩陣的結(jié)構(gòu)信息簡(jiǎn)單易于操作的特點(diǎn)，根據(jù)上述定理對(duì)矩陣結(jié)構(gòu)進(jìn)行約簡(jiǎn)，查找頻繁項(xiàng)集。

3 算法實(shí)驗(yàn)結(jié)果

3.1 實(shí)例分析

從UCI 數(shù)據(jù)集中的Thyroid+Disease 數(shù)據(jù)集選取若干條數(shù)據(jù)，對(duì)基于矩陣約簡(jiǎn)的Apriori 改進(jìn)算法進(jìn)行實(shí)例分析，通過(guò)數(shù)據(jù)預(yù)處理獲得適合數(shù)據(jù)挖掘格式要求的目標(biāo)數(shù)據(jù)，數(shù)據(jù)庫(kù)如表1 所示，TID 為T(mén)hyroid+Disease 的分類(lèi)，ITEM SET 為T(mén)hyroid+Disease 屬性信息，設(shè)最小支持度為0.3。

表1 Thyroid+Disease 分類(lèi)明細(xì)

1)構(gòu)造事物矩陣R，計(jì)算每個(gè)項(xiàng)集的支持?jǐn)?shù)及項(xiàng)目個(gè)數(shù)，按照支持項(xiàng)目數(shù)對(duì)其進(jìn)行降序排序，如下所示。

計(jì)算最小支持?jǐn)?shù)為:

則最小支持?jǐn)?shù)為3。

2)根據(jù)矩陣R 求頻繁1-項(xiàng)集，重新布置矩陣R1。

由矩陣R 知，項(xiàng)F，C 的支持?jǐn)?shù)為1、2 均小于最小支持?jǐn)?shù)3，所以為非頻繁集。刪除第1 列和第2 列得到矩陣R1，如下所示。

由矩陣得出頻繁1-項(xiàng)集為L(zhǎng)1={{A}，{B}，{D}，{E}}。

3)根據(jù)矩陣R1求頻繁2-項(xiàng)集。

根據(jù)定理1 得到矩陣R2。

分別選取A 和D 進(jìn)行與運(yùn)算:

sup_count(A∧D)=minsup_count=3，所以頻繁{A，D}為頻繁2-項(xiàng)集，存儲(chǔ)在L2中。根據(jù)上述計(jì)算步驟算出其它候選項(xiàng)集，得到L2={{AD}，{AE}，{BD}，{BE}，{DE}}。

4)利用3)的流程，求取3-頻繁項(xiàng)集。

根據(jù)定理1 得到矩陣R2。

則余下的項(xiàng)組合 C3={{ABD}，{ABE}，{ADE}，{BDE}}，并進(jìn)行與運(yùn)算求出各個(gè)組合的支持?jǐn)?shù):count(ABE)=2，count(ADE)=3，count(ABD)=2，count(BDE)=5，由此看出只有{ADE}和{BDE}的支持?jǐn)?shù)大于最小支持?jǐn)?shù)，所以頻繁3-項(xiàng)集為:L3{{ADE}，{BDE}}。根據(jù)定理3 可知頻繁3-項(xiàng)集為此數(shù)據(jù)集的最大頻繁集。由輔助矩陣Rf得出頻繁項(xiàng)集:L=L1∪L2∪L3。由此證明了算法的可行性。

3.2 挖掘結(jié)果分析

為了驗(yàn)證改進(jìn)算法的執(zhí)行效率，在Intel(R)Core(TM)2 Duo CPU，內(nèi)存為2 GB，系統(tǒng)為Windows7 的計(jì)算機(jī)上，用C#語(yǔ)言實(shí)現(xiàn)基于矩陣約簡(jiǎn)的Apriori 改進(jìn)算法和傳統(tǒng)的Apriori 算法，數(shù)據(jù)來(lái)自UCI 數(shù)據(jù)集中的Thyroid+Disease 樣本數(shù)據(jù)集(http://archive.ics.uci.edu/ml/datasets/Thyroid+Disease)，該數(shù)據(jù)庫(kù)中含有7 200 記條數(shù)據(jù)，連同一個(gè)22 個(gè)屬性類(lèi)別，在實(shí)驗(yàn)進(jìn)行前對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，使其符合算法對(duì)數(shù)據(jù)的要求。做如下2 個(gè)實(shí)驗(yàn):

實(shí)驗(yàn)1 在不同最小支持度的情況下對(duì)這2 種算法進(jìn)行執(zhí)行效率比較，結(jié)果如圖1 所示，橫坐標(biāo)為支持度，縱坐標(biāo)為時(shí)間(s)。在相同最小支持度的條件下，基于矩陣約簡(jiǎn)的Apriori 改進(jìn)算法所用的時(shí)間明顯較少，在支持度較小時(shí)改進(jìn)的Apriori 算法處理效率更高。

圖1 改進(jìn)的Apriori 算法與原Apriori 算法在執(zhí)行時(shí)間上的對(duì)比

實(shí)驗(yàn)2 在不同最小支持度的情況下對(duì)這2 種算法進(jìn)行生成頻繁項(xiàng)集個(gè)數(shù)的比較，結(jié)果如圖2 所示，橫坐標(biāo)為支持度，縱坐標(biāo)為頻繁項(xiàng)集的個(gè)數(shù)。在相同最小支持度的條件下，隨著最小支持度的增加基于矩陣約簡(jiǎn)的Apriori 改進(jìn)算法所生成的頻繁項(xiàng)集個(gè)數(shù)與傳統(tǒng)Apriori 算法的頻繁項(xiàng)集個(gè)數(shù)趨近相等。

圖2 改進(jìn)的Apriori 算法與傳統(tǒng)的Apriori 算法在生成候選項(xiàng)集個(gè)數(shù)上的對(duì)比

傳統(tǒng)的Apriori 算法的執(zhí)行效率與算法生成的候選項(xiàng)集個(gè)數(shù)和掃描數(shù)據(jù)庫(kù)次數(shù)密切相關(guān)，改進(jìn)的Apriori 算法很好地降低了這2 個(gè)指標(biāo)，執(zhí)行效率大幅度提高。

4 結(jié)束語(yǔ)

基于矩陣約簡(jiǎn)的Apriori 改進(jìn)算法只需掃描事物數(shù)據(jù)庫(kù)一次，有效地避免了相同候選集的生成，隨著k-項(xiàng)集的k 值增加，矩陣變得越來(lái)越簡(jiǎn)單，求候選k-項(xiàng)集的支持?jǐn)?shù)的時(shí)間也就越少;該算法將對(duì)數(shù)據(jù)庫(kù)的掃描轉(zhuǎn)換成對(duì)內(nèi)存的掃描，大大提高挖掘關(guān)聯(lián)規(guī)則算法的執(zhí)行效率。綜上所述，基于矩陣約簡(jiǎn)的Apriori改進(jìn)算法克服了傳統(tǒng)的Apriori 算法重復(fù)多遍掃描數(shù)據(jù)庫(kù)的缺陷，節(jié)約了系統(tǒng)資源，提高了算法執(zhí)行效率。

［1］孟祥萍，錢(qián)進(jìn)，劉大有.基于數(shù)組的關(guān)聯(lián)規(guī)則挖掘算法［J］.計(jì)算機(jī)工程，2003，29(15):98-99，109.

［2］張文東，劉新恩.一種基于向量的關(guān)聯(lián)規(guī)則挖掘算法改進(jìn)［J］.微計(jì)算機(jī)應(yīng)用，2009，30(2):74-75.

［3］張忠平，李巖，楊靜.基于矩陣的頻繁項(xiàng)集挖掘算法［J］.計(jì)算機(jī)工程，2009，35(1):84-85.

［4］許曉東，李柯，朱士瑞.Web 使用挖掘中Apriori 算法的改進(jìn)研究［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2010，31(3):539-541.

［5］孫逢嘯，倪世宏，謝川.一種基于矩陣的Apriori 改進(jìn)算法［J］.計(jì)算機(jī)仿真，2013，30(83):245-249.

［6］黃治國(guó)，王淼.基于決策矩陣的可信關(guān)聯(lián)規(guī)則挖掘方法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2014，35(8):2890-2895.

［7］苗苗苗，王玉英.基于矩陣壓縮的Apriori 算法改進(jìn)的研究［J］.計(jì)算機(jī)工程與應(yīng)用，2014，49(1):159-162.

［8］Han Jiawei，Kamber Micheline.數(shù)據(jù)挖掘:概念與技術(shù)［M］.北京:機(jī)械工業(yè)出版社，2001.

［9］劉敏嫻，馬強(qiáng)，寧以風(fēng).基于頻繁矩陣的Apriori 算法改進(jìn)［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2012，33(11):4235-4239.

［10］胡維華，馮偉.基于分解事務(wù)矩陣的關(guān)聯(lián)規(guī)則挖掘算法［J］.計(jì)算機(jī)應(yīng)用，2014，34(S2):113-116.

［11］羅森林，馬俊，潘麗敏.數(shù)據(jù)挖掘理論與技術(shù)［M］.北京:電子工業(yè)出版社，2013:16-19.

［12］崔貫勛，李梁.關(guān)聯(lián)規(guī)則挖掘中Apriori 算法的研究與改進(jìn)［J］.計(jì)算機(jī)應(yīng)用，2010，30(11):2952-2955.

［13］邵峰晶，于忠清.數(shù)據(jù)挖掘原理與算法［M］.北京:科學(xué)出版社，2009.

［14］路松峰，盧正鼎.快速開(kāi)采最大頻繁項(xiàng)目集［J］.軟件學(xué)報(bào)，2001，12(2):293-297.