劉彥戎，楊 云

(1.陜西國際商貿(mào)學(xué)院 信息工程學(xué)院，陜西 西安 712000；2.陜西科技大學(xué) 電子信息與人工智能學(xué)院，陜西 西安 710021)

0 引 言

在互聯(lián)網(wǎng)產(chǎn)業(yè)急速發(fā)展的情況下，信息技術(shù)和信息經(jīng)濟(jì)也發(fā)展迅速，由此在各行各業(yè)中數(shù)據(jù)挖掘技術(shù)的應(yīng)用越來越廣泛。數(shù)據(jù)挖掘技術(shù)從現(xiàn)有的未知數(shù)據(jù)中可以發(fā)現(xiàn)大量具有潛在價(jià)值的信息或模式，當(dāng)這個(gè)理論提出時(shí)，立刻引起了科學(xué)界的廣泛關(guān)注。在數(shù)據(jù)挖掘領(lǐng)域中最重要的研究方向是關(guān)聯(lián)規(guī)則挖掘，關(guān)聯(lián)規(guī)則技術(shù)的實(shí)現(xiàn)是以數(shù)據(jù)之間的聯(lián)系為基礎(chǔ)來實(shí)現(xiàn)其可信度的支持。該算法最初是被P.-G. Cheng[1]作為市場購物籃分析理論提出的，在此過程中通過研究顧客購買行為建立關(guān)聯(lián)知識(shí)，來指導(dǎo)商業(yè)貿(mào)易中交易事項(xiàng)的數(shù)據(jù)集合[2]。由于數(shù)據(jù)具有多樣性的特點(diǎn)，從海量數(shù)據(jù)中通過有效探索和篩選可得到有效數(shù)據(jù)，從而可以為智能人機(jī)交互提供技術(shù)支持。在數(shù)據(jù)挖掘過程中，關(guān)聯(lián)規(guī)則技術(shù)得到了長足發(fā)展，已在銀行風(fēng)險(xiǎn)預(yù)警、金融證券分析和移動(dòng)通信方面深入應(yīng)用，并顯示出較好的應(yīng)用前景和巨大的發(fā)展?jié)摿Α?/p>

許多學(xué)者在數(shù)據(jù)挖掘方面做了大量的研究，為其發(fā)展做出了貢獻(xiàn)。傳統(tǒng)關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘的改進(jìn)大多是基于Apriori[3-5]算法，Apriori算法最大的缺陷是需要對(duì)數(shù)據(jù)庫進(jìn)行多次掃描[6]才能得到頻繁項(xiàng)目集，這就嚴(yán)重影響了數(shù)據(jù)挖掘的運(yùn)行效率。魏玲等人提出了NFUP算法[7]，該算法基于強(qiáng)大項(xiàng)目集的概念，將強(qiáng)大項(xiàng)目集加入到候選項(xiàng)目集的小數(shù)量中，并采用早期裁剪策略來減少掃描數(shù)據(jù)庫的次數(shù)。Dean. J等人[8]提出一種改進(jìn)的基于客戶關(guān)系管理系統(tǒng)的數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則Apriori算法，該算法刪除了大量無效事務(wù)，隨著事務(wù)的減少，數(shù)據(jù)庫的規(guī)模也隨之變小，減少了后續(xù)掃描的記錄，提高了數(shù)據(jù)挖掘的處理效率[9-10]。Rakesh等人[11]針對(duì)候選項(xiàng)集數(shù)量多、掃描數(shù)據(jù)庫耗時(shí)長等問題，提出了一種有效的挖掘候選項(xiàng)集的算法，該算法克服了數(shù)據(jù)庫掃描時(shí)間長的缺陷，減少了候選項(xiàng)集的數(shù)量，提高了執(zhí)行效率。Linden G等人[12]提出了一種基于模糊技術(shù)的數(shù)據(jù)類型統(tǒng)一識(shí)別方法，該技術(shù)可以使所有不同的數(shù)據(jù)類型都能以統(tǒng)一的方式進(jìn)行處理。Borthakur D[13]針對(duì)Apriori算法中對(duì)數(shù)據(jù)庫進(jìn)行多次掃描并生成大量候選項(xiàng)集的性能瓶頸，提出了一種新的算法，該算法通過一個(gè)預(yù)先設(shè)定的過濾器過濾掉與挖掘目標(biāo)無關(guān)的事務(wù)，這種方法大大提高了算法的整體性能。錢光超等人[14]提出了一種新的基于布爾矩陣的Apriori算法，該算法通過關(guān)聯(lián)圖和矩陣裁剪的方法減少了候選項(xiàng)集的數(shù)量，實(shí)驗(yàn)結(jié)果表明，該算法使用一次就降低了系統(tǒng)數(shù)據(jù)采集的性能。S. Anekritmongkol等人[15]提出了一種新的基于布爾模型的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘壓縮算法，主要思想就是通過壓縮數(shù)據(jù)可以大大減少掃描數(shù)據(jù)庫的次數(shù)。J.Pavon等人[16]提出了一種結(jié)合兩者最佳特征算法的矩陣算法，該種組合算法利用矩陣和向量等簡單結(jié)構(gòu)來生成頻繁模式，同時(shí)對(duì)候選集的數(shù)量進(jìn)行了最小化處理，從而實(shí)現(xiàn)比Apriori算法和FP-growth[17]算法更高效的計(jì)算。

基于相似度的Apriori算法是Li X等人[18]所提出的，他們把余弦相似度的閾值作為Apriori算法的改進(jìn)策略。研究調(diào)查發(fā)現(xiàn)Apriori算法主要存在的問題就是在結(jié)束掃描庫之后生成過多的候選項(xiàng)目集，所以改進(jìn)關(guān)聯(lián)規(guī)則的主要方式就是縮短掃描時(shí)間，提高掃描效率。采用矩陣算法對(duì)數(shù)據(jù)庫進(jìn)行掃描，將項(xiàng)目集改變?yōu)椴紶栔悼梢蕴岣咝?，但是無法刪減重復(fù)的事務(wù)和項(xiàng)目集，還會(huì)導(dǎo)致計(jì)算量的增加，所以該文提出了新型的矩陣和排序索引關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法，這種方法可以在一次掃描過程當(dāng)中提高算法的執(zhí)行效率，而且刪除不需要的項(xiàng)目集。

1 一種矩陣和排序索引關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法

該文在深入探討了傳統(tǒng)關(guān)聯(lián)規(guī)則之后，提出一種改進(jìn)的矩陣和排序索引關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法，該算法簡稱為IMSIA。算法的基本思想是：結(jié)合矩陣算法k-頻繁項(xiàng)集生成中的高效率和排序索引的高搜索速度的優(yōu)點(diǎn)，將交易數(shù)據(jù)庫轉(zhuǎn)換為交易矩陣，然后不再掃描和使用交易數(shù)據(jù)庫，直接掃描交易矩陣，刪除之前的初始矩陣，在刪除矩陣之前，將矩陣按標(biāo)記序列放置隨后搜索表，刪除后更新兩個(gè)標(biāo)記序列。將刪除的矩陣與其通過新矩陣獲得的轉(zhuǎn)置矩陣相乘，在矩陣的上三角中分析其數(shù)據(jù)并搜索序列，從而得出兩個(gè)準(zhǔn)確的頻繁項(xiàng)集。利用所計(jì)算出來的頻繁項(xiàng)集，建立排序索引矩陣，矩陣和頻繁項(xiàng)集之間可以使用向下的方式進(jìn)行連接。

1.1 Apriori關(guān)聯(lián)規(guī)則挖掘算法

在關(guān)聯(lián)規(guī)則算法當(dāng)中，I表示項(xiàng)目，D表示事務(wù)數(shù)據(jù)庫，T表示數(shù)據(jù)庫當(dāng)中的一組項(xiàng)目。且元素T?I，TID表示任何一個(gè)事務(wù)的標(biāo)識(shí)符。當(dāng)滿足A∩B=?、A?I、B?I條件時(shí)，A?B的形式稱為關(guān)聯(lián)規(guī)則。A?B的關(guān)聯(lián)規(guī)則是在存在支持度的事務(wù)數(shù)據(jù)庫中D建立的，其中p指概率，s指事務(wù)數(shù)據(jù)庫中所占的百分比。關(guān)聯(lián)規(guī)則在交易數(shù)據(jù)庫中存在置信度c，如式(1)和式(2)：

sup(A?B)=P(A∪B)

(1)

confidence(A?B)=P(B|A)

(2)

一個(gè)項(xiàng)目集即是包含一組項(xiàng)目的集合，包含k個(gè)項(xiàng)目的集合稱為k-項(xiàng)集。在一個(gè)項(xiàng)目集中若是存在頻繁項(xiàng)集，則必定具有最小支持度min_sup，關(guān)聯(lián)規(guī)則中若是存在強(qiáng)關(guān)聯(lián)規(guī)則，該規(guī)則中的隱含條件一定是包含最小支持度閾值和最小置信度閾值。

Apriori算法的思想是先搜索而后逐層迭代搜索項(xiàng)集的過程，在搜索的過程中首先掃描事務(wù)數(shù)據(jù)庫，并計(jì)算每個(gè)數(shù)據(jù)項(xiàng)的支持度，生成候選項(xiàng)集C1，利用支持閾值生成頻繁為1-項(xiàng)集L1。Apriori算法的思想是先搜索而后逐層迭代搜索項(xiàng)集的過程，在搜索的過程中首先掃描事務(wù)數(shù)據(jù)庫，并計(jì)算每個(gè)數(shù)據(jù)項(xiàng)的支持度，生成候選項(xiàng)集C1，利用支持閾值生成頻繁為1-項(xiàng)集L1。將生成的L1項(xiàng)集與L1項(xiàng)集自身進(jìn)行與運(yùn)算得到候選項(xiàng)集C2，完成事務(wù)數(shù)據(jù)庫的再次搜索并將計(jì)算得出的候選項(xiàng)集C2的支持度與最小支持度min_sup相比，取其最小者為2-項(xiàng)集L2，以此類推，若事務(wù)數(shù)據(jù)庫中找不到頻繁項(xiàng)集，則算法結(jié)束。

1.2 矩陣關(guān)聯(lián)規(guī)則挖掘算法

要實(shí)現(xiàn)矩陣關(guān)聯(lián)算法的規(guī)則，首先將事務(wù)數(shù)據(jù)庫集合D轉(zhuǎn)變?yōu)椴紶柧仃嘯19]，然后對(duì)其中所包含的n個(gè)事物和m個(gè)項(xiàng)目進(jìn)行排序，用項(xiàng)目矩陣表示的整個(gè)數(shù)據(jù)庫如下所示：

其中，Aij∈I(0≤i≤m,0≤j≤m)，元素{Aij}在矩陣Amn中的定義方程為:

(3)

在矩陣Amn中包含了表示每一事務(wù)的行m和表示每一項(xiàng)的列n。在定義方程中若任意一個(gè)事務(wù)數(shù)據(jù)庫Di存在項(xiàng)目i的第j項(xiàng)，則{Aij}的值為1，若不存在項(xiàng)目i的第j項(xiàng)，則{Aij}的值為0，當(dāng)矩陣A是一個(gè)事務(wù)向量時(shí)，也可表示為a1,a2,…,am(具有m行向量的矩陣)。

矩陣關(guān)聯(lián)規(guī)則具有屬性1：不包含任何頻繁出現(xiàn)的項(xiàng)目集中，一定也不包含(k-1)頻繁項(xiàng)目集；屬性2：任何非頻繁項(xiàng)集的子集也是非頻繁項(xiàng)集。

1.3 改進(jìn)的事務(wù)矩陣和標(biāo)記序列掃描

Apriori算法在求解的過程中首先需要求出候選項(xiàng)集Ck，然后對(duì)頻繁項(xiàng)集Lk執(zhí)行批處理操作，生成頻繁項(xiàng)集的候選集數(shù)量較大，同時(shí)所有頻繁項(xiàng)集要對(duì)數(shù)據(jù)庫進(jìn)行掃描，該操作占用系統(tǒng)內(nèi)存空間較大和CPU處理時(shí)間較長，因此很難適應(yīng)海量數(shù)據(jù)挖掘。矩陣關(guān)聯(lián)規(guī)則挖掘算法雖然不刪除非頻繁項(xiàng)和事務(wù)，但還需要搜索數(shù)據(jù)以找到頻繁項(xiàng)集，從而增加了計(jì)算量。盡管這些算法已經(jīng)能夠減少候選集的數(shù)量或通過修剪策略來提高挖掘效率，但仍不能完全解決候選集產(chǎn)生的問題。

索引最關(guān)鍵的特征是可以讓檢索信息速度更快，利用索引號(hào)可以完成向搜索項(xiàng)目集跳轉(zhuǎn)，假如該行不滿足下行連接條件，則不需要增加掃描量，從而提高了項(xiàng)目集挖掘的速度。在生成2-頻繁項(xiàng)集的算法過程中有計(jì)算量大的缺點(diǎn)，由此導(dǎo)致算法的效率低下，矩陣算法在得到頻繁項(xiàng)集前先將事務(wù)數(shù)據(jù)庫轉(zhuǎn)換為事務(wù)矩陣，然后通過分析得到上三角矩陣，這個(gè)過程中省略了向下連接和修剪的步驟，這樣就大大減少了計(jì)算步驟，提高了項(xiàng)集的生成效率。該文在分析實(shí)驗(yàn)結(jié)果的基礎(chǔ)上，提出結(jié)合改進(jìn)的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘方法和索引優(yōu)點(diǎn)的IMSIA算法，此算法較好地解決了多個(gè)數(shù)據(jù)庫連接過程中產(chǎn)生大量候選集的問題。

步驟如下：將事務(wù)數(shù)據(jù)庫轉(zhuǎn)換為布爾數(shù)據(jù)庫事務(wù)矩陣D，并將標(biāo)記序列事務(wù)對(duì)應(yīng)的矩陣保存到表中相應(yīng)的項(xiàng)目中，建立一個(gè)事務(wù)數(shù)據(jù)庫，該事務(wù)數(shù)據(jù)庫包含m×n個(gè)項(xiàng)目、對(duì)應(yīng)的標(biāo)記序列為Lr={1,2,…,m}和Lc={1,2,…,n}。在刪除矩陣的屬性時(shí)，必須為刪除的相應(yīng)項(xiàng)目序列進(jìn)行標(biāo)記。刪除矩陣后，可以通過相乘獲得S=A×AT。

1.4 改進(jìn)的自適應(yīng)排序索引矩陣

由于驗(yàn)證算法需要搜索數(shù)據(jù)庫并生成候選項(xiàng)，因此會(huì)占用大量內(nèi)存并增加I/O成本。索引可以提高檢索信息的速度，但是內(nèi)存編號(hào)中保存排列索引所占內(nèi)存較少，并能通過索引號(hào)來跳轉(zhuǎn)搜索序列，如果該行不滿足向下連接的條件，則無需進(jìn)行掃描，在此基礎(chǔ)上減少了搜索時(shí)間、搜索數(shù)量、內(nèi)存占用搜索項(xiàng)集量和I/O開銷。該文在改進(jìn)矩陣算法的基礎(chǔ)上，結(jié)合改進(jìn)的自適應(yīng)排序索引矩陣，僅掃描數(shù)據(jù)庫一次，無需生成候選集，并根據(jù)選擇排序規(guī)則進(jìn)行排序，提高了計(jì)算效率和算法的執(zhí)行效率。具體實(shí)現(xiàn)步驟如下：

(1)當(dāng)頻繁項(xiàng)集滿足k>2時(shí)，使用改進(jìn)的自適應(yīng)排序索引方法以搜索第k個(gè)項(xiàng)集(k≥3)。

(2)使用降序排列的1個(gè)項(xiàng)目集L作為矩陣的列，在建立排序索引的過程中，按照降序(k-1)項(xiàng)進(jìn)行設(shè)置。例如：行項(xiàng)目集I2對(duì)應(yīng)于值1，I4對(duì)應(yīng)的值為1，則該行表示2個(gè)項(xiàng)目集I2I4。其中，每個(gè)項(xiàng)目集的每行(k-1)項(xiàng)目也與安排的編號(hào)遞減順序保持一致。

(3)由于排序規(guī)則對(duì)排序結(jié)果的影響較大，通常是按照自行確定規(guī)則的方法，無法選擇最優(yōu)排序規(guī)則，因此提出了置信度和支持度之間的自適應(yīng)最優(yōu)選擇規(guī)則。通過計(jì)算每個(gè)項(xiàng)目集的支持度和置信度，比較min_sup和min_conf的值，如果匹配的項(xiàng)目集數(shù)量較少，則選擇相應(yīng)的min_sup或min_conf(如果數(shù)據(jù)庫僅給出一個(gè)參數(shù))作為給定參數(shù)默認(rèn)的排序規(guī)則。

(4)依據(jù)每一列當(dāng)中非零元素的行號(hào)順序，將其保存到數(shù)組當(dāng)中，如果最小支持度的閾值大于項(xiàng)目數(shù)，可以將其所對(duì)應(yīng)的頻繁項(xiàng)目集刪除，對(duì)于每一列，使用V(i+j)項(xiàng)集的行號(hào)值來替換第j個(gè)項(xiàng)集的非零元素，用下一個(gè)位置號(hào)作為搜索來替換原始列值1，分配最后一個(gè)非零元素為當(dāng)前列的值。對(duì)頻繁k-項(xiàng)集Lk(k≥3)，在進(jìn)行數(shù)據(jù)挖掘時(shí)采用的是向下連接排序索引矩陣的方式實(shí)現(xiàn)的。

當(dāng)k=3時(shí)，以R1為目標(biāo)開始掃描，此時(shí)完成以索引號(hào)為目標(biāo)的最后一列掃描，之后通過索引號(hào)的導(dǎo)引完成Rx的掃描，將掃描得到的結(jié)果與對(duì)應(yīng)的R1和Rx相連得到3-項(xiàng)集。得到的項(xiàng)目集再與具有最小支持?jǐn)?shù)的項(xiàng)目集連接，對(duì)項(xiàng)集進(jìn)行掃描按照行排列的方式，直到所有的頻繁項(xiàng)集都處于連接轉(zhuǎn)態(tài)，此時(shí)得到新的項(xiàng)集。最后根據(jù)關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘的屬性確定是否繼續(xù)進(jìn)行掃描生成4-項(xiàng)集。當(dāng)k=3時(shí)，按以下步驟生成頻率k-項(xiàng)目集：

①利用向下連接的方法掃描以建立好的排序索引矩陣，如果在掃描的行中不存在“1”，但是具有與k-2相同的索引號(hào)時(shí)，則直接按照對(duì)應(yīng)的索引號(hào)進(jìn)行跳轉(zhuǎn)，跳轉(zhuǎn)到的行與(k-1)Ry連接形成k-項(xiàng)目集。如果沒有在掃描數(shù)據(jù)庫的過程當(dāng)中找到繼續(xù)連續(xù)的條件，則可以跳過該行繼續(xù)進(jìn)行下一行掃描過程。

②使用較小的兩個(gè)(k-1)-項(xiàng)目集支持?jǐn)?shù)作為連接的k-項(xiàng)目集的支持?jǐn)?shù)。

③按行方式，直到掃描最后一行，將所有的頻繁(k-1)-項(xiàng)目集連接，得到所有的頻繁k-項(xiàng)目集。然后根據(jù)關(guān)聯(lián)規(guī)則屬性確定是否繼續(xù)生成頻繁(k+1)-項(xiàng)目集。

2 實(shí)驗(yàn)結(jié)果

2.1 舉例分析

假如存在事務(wù)數(shù)據(jù)庫，設(shè)最低支持度為20%，事務(wù)數(shù)目為10，如表1所示。

表1 事務(wù)數(shù)據(jù)庫D

根據(jù)上述數(shù)據(jù)庫，可以得到矩陣A：

根據(jù)編號(hào)對(duì)形成的6個(gè)頻繁2-項(xiàng)集進(jìn)行排序，在項(xiàng)目I4對(duì)應(yīng)的列中只存在一個(gè)“1”，由此形成的I2I4項(xiàng)目集與其他2個(gè)項(xiàng)目集無法進(jìn)行連接，故刪除事務(wù)數(shù)據(jù)庫中與I4對(duì)應(yīng)的列和行，生成結(jié)果如表2所示。

表2 排序索引矩陣

如表2所示，a，b，c，d和e分別表示序號(hào)，即在表中5個(gè)序號(hào)表示的行號(hào)只具有索引的作用。首先，用I2I1掃描第1行，將I1的搜索列刪除，以索引號(hào)c跳到第三行，即I1I3的行，將第1行和第3行連接起來，獲得頻繁3-項(xiàng)集I2I1I5。I2I1I3的支持度為4，I2I1和I5I1的支持度分別為4和2，因此I2I1I5的支持度為2。繼續(xù)掃描第2行和第3行，直到最后一行，Apriori算法在此步驟中形成候選3個(gè)項(xiàng)集，并且有6個(gè)，故該方法不利于算法效率的提高。頻繁3-項(xiàng)集L3是{I2I1I3(4),I2I1I5(2)}通過使用排序索引關(guān)聯(lián)矩陣得到的，在生成L3后，對(duì)其中的兩個(gè)項(xiàng)集再次建立排序索引，用索引號(hào)a和b進(jìn)行向下連接，在此連接過程中不滿足產(chǎn)生4-頻繁項(xiàng)集的條件，至此算法運(yùn)行結(jié)束，如表3所示。

表3 L3排序索引矩陣

頻繁1-項(xiàng)集L1、頻繁2-項(xiàng)集L2、頻繁3-項(xiàng)集L3、頻繁4-項(xiàng)集L4的取值分別為{I2(7),I1(6),I3(6),I4(2),I5(2)}、{I2I3(4),I2I1(4),I1I3(4),I2I5(2),I2I4(2),I1I5(2)}、{I2I1I3(4),I2I1I5(2)}及空，因此頻繁3-項(xiàng)集L3為最大。

2.2 實(shí)驗(yàn)結(jié)果和數(shù)據(jù)庫分析

依據(jù)算法的時(shí)間復(fù)雜度可以發(fā)現(xiàn)，IMSIA算法和Apriori算法在對(duì)數(shù)據(jù)庫進(jìn)行掃描時(shí)的時(shí)間復(fù)雜度分別是Q(m)和Q(n×m)，對(duì)比后發(fā)現(xiàn)，IMSIA算法掃描數(shù)據(jù)庫的時(shí)間較短。在實(shí)驗(yàn)中，利用隨機(jī)函數(shù)Random()生成所需數(shù)據(jù)集，當(dāng)每次輸入項(xiàng)目集|I|和事務(wù)|T|時(shí)，數(shù)據(jù)庫當(dāng)中的隨機(jī)函數(shù)會(huì)生成數(shù)據(jù)集。在數(shù)據(jù)集的生成過程中不存在外界干擾因素，可以充分反映所提出算法的高效性能。

為了進(jìn)一步深入了解改進(jìn)算法的優(yōu)勢(shì)，對(duì)矩陣算法、Apriori算法和IMSIA算法的內(nèi)存使用情況和算法運(yùn)行時(shí)間進(jìn)行比較。實(shí)驗(yàn)環(huán)境采用Java語言下的Eclipse環(huán)境搭建，操作系統(tǒng)用Windows 7，硬件使用Pentium(R)雙核2.8 GHz/5.0 GB。

分析不同算法在最小支持度和相同數(shù)據(jù)集下的運(yùn)行時(shí)間，IMSIA在k=2時(shí)的運(yùn)行時(shí)間為生成矩陣乘以矩陣。當(dāng)k≥3時(shí)，改進(jìn)后的IMSIA算法所使用的運(yùn)行時(shí)間是矩陣當(dāng)中搜索項(xiàng)目集和將項(xiàng)目進(jìn)行排序時(shí)間的總和。計(jì)算Apriori算法總運(yùn)行時(shí)間時(shí)，需要生成候選項(xiàng)目集時(shí)間、掃描數(shù)據(jù)庫時(shí)間和修剪項(xiàng)目集時(shí)間相加得出。圖1對(duì)比了多種支持度運(yùn)行時(shí)間，分析該圖可得，處于同一個(gè)數(shù)據(jù)集(|T|=1 000，|I|=30)下，改進(jìn)后的IMSIA算法和每種支持度下的運(yùn)行時(shí)間均小于Apriori算法和矩陣算法。這表明在計(jì)算頻繁2-項(xiàng)集之前先刪除了無用的項(xiàng)目和事務(wù)，減少不必要的計(jì)算量，提高了計(jì)算效率，因此改進(jìn)算法在計(jì)算時(shí)間上具有較好的優(yōu)越性。在支持度不同的情況之下，對(duì)比三種算法所使用的計(jì)算時(shí)間，可以發(fā)現(xiàn)IMSIA算法效率較高，消耗時(shí)間較短，因此優(yōu)勢(shì)更為明顯。

圖1 不同算法的運(yùn)行時(shí)間支持度

在數(shù)據(jù)集不同、支持度相同的前提下對(duì)比運(yùn)行時(shí)間，結(jié)果如圖2所示。7個(gè)隨機(jī)生成的長度不同的數(shù)據(jù)集為：D1(|T|=100，|I|=15)，D2(|T|=300，|I|=30)，D3(|T|=500，|I|=40)，D4(|T|=1 000，|I|=50)，D5(|T|=1 500，|I|=60)，D6(|T|=5 000，|I|=80)和D7(|T|=10 000，|I|=120)，將min_sup計(jì)數(shù)設(shè)置為28。當(dāng)設(shè)置參數(shù)不同時(shí)，矩陣算法的運(yùn)行時(shí)間小于Apriori算法、大于IMSIA算法，由此可以得出，改進(jìn)算法具有更好的執(zhí)行效率，此外，當(dāng)數(shù)據(jù)集的數(shù)量成線性增長時(shí)，所提出的IMSIA算法更能體現(xiàn)其高效率和可擴(kuò)展的性能。

圖2 不同數(shù)據(jù)集下不同算法的運(yùn)行時(shí)間比較

考慮到算法成本，提出的IMSIA算法只掃描數(shù)據(jù)庫一次，并將索引和排序放入緩存中，降低了I/O操作的成本。在相同數(shù)據(jù)集(|T|=1 000，|I|=30)的情況下設(shè)置min_sup=28，通過對(duì)比表4中的內(nèi)存使用數(shù)據(jù)，發(fā)現(xiàn)Apriori算法內(nèi)存使用量占15.38%；矩陣算法的內(nèi)存使用量占12.56%；改進(jìn)的IMSIA算法內(nèi)存使用量占8.31%。通過對(duì)比矩陣關(guān)聯(lián)規(guī)則算法與Apriori算法的使用率，前者低于后者2.82%，三種算法中內(nèi)存使用率最低的為IMSIA算法，通過對(duì)比內(nèi)存使用率提高了7.05%，進(jìn)一步驗(yàn)證了該算法效率高，內(nèi)存使用率低，I/O成本低。

表4 不同算法的內(nèi)存使用情況比較

3 結(jié)束語

提出了一種IMSIA關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法，該算法首先通過掃描數(shù)據(jù)庫建立事務(wù)標(biāo)記序列和事務(wù)矩陣，而后對(duì)矩陣中的無用事務(wù)集進(jìn)行刪除操作，并對(duì)標(biāo)記序列進(jìn)行從新標(biāo)記，最后將刪除的矩陣與其轉(zhuǎn)置矩陣相乘，得到頻繁2-項(xiàng)集，再結(jié)合排序索引，得出其余的頻繁k-項(xiàng)集。該算法在運(yùn)行過程中只對(duì)數(shù)據(jù)庫進(jìn)行了一次掃描，且不生成候選項(xiàng)集，從而大大減少了內(nèi)存的使用率并降低了I/O成本，而且還支持?jǐn)?shù)據(jù)挖掘的實(shí)時(shí)更新，提高了數(shù)據(jù)挖掘效率。