利用項(xiàng)編碼方法改進(jìn)ａＰｒｉｏｒｉ算法

摘要：在眾多的關(guān)聯(lián)規(guī)則挖掘算法中Apriori算法是最為經(jīng)典的一個(gè)，但Apfiofi算法有兩個(gè)缺陷，即：需要掃描多次數(shù)據(jù)庫以及生成大量的侯選集。文中對(duì)該算法進(jìn)行改進(jìn)提出了一種對(duì)項(xiàng)進(jìn)行編碼的方法，通過對(duì)項(xiàng)編碼來減少掃描數(shù)據(jù)庫次數(shù)并通過刪除項(xiàng)來減少生成候選集的數(shù)量，從而提高算法的效率。實(shí)驗(yàn)結(jié)果表明，優(yōu)化后的算法能有效地提高關(guān)聯(lián)規(guī)則挖掘的效率。

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

0 引言

數(shù)據(jù)挖掘的關(guān)聯(lián)規(guī)則挖掘算法用于尋找數(shù)據(jù)項(xiàng)中的有趣聯(lián)系，決定哪些事情將一起發(fā)生。例如：事務(wù)1中出現(xiàn)了物品A，事務(wù)2中出現(xiàn)了物品B，事務(wù)3中則同時(shí)出現(xiàn)了物品A和B，那么物品A和B在事務(wù)中的出現(xiàn)是否有規(guī)則可循呢?在數(shù)據(jù)挖掘中，關(guān)聯(lián)規(guī)則就是描述這種在一個(gè)事務(wù)中物品之間同時(shí)出現(xiàn)的規(guī)律的知識(shí)模式。更確切地說，關(guān)聯(lián)規(guī)則就是通過量化的數(shù)字描述物品A的出現(xiàn)對(duì)物品B的出現(xiàn)有多大的影響。

在眾多的關(guān)聯(lián)規(guī)則挖掘算法中，Agrawal提出的Apriori算法是最為著名的關(guān)聯(lián)規(guī)則算法，已經(jīng)為大部分商業(yè)產(chǎn)品所使用。該算法利用大項(xiàng)目集性質(zhì)來生成規(guī)則，其基本思想是生成特定規(guī)模的候選項(xiàng)目集，然后掃描數(shù)據(jù)庫，并進(jìn)行計(jì)數(shù)，以確定這些侯選項(xiàng)目集是否是大的。該算法思想簡單，實(shí)用，但是，在實(shí)現(xiàn)過程中會(huì)出現(xiàn)兩個(gè)缺點(diǎn)：一個(gè)是會(huì)產(chǎn)生大量的侯選集；另一個(gè)是需要多次的掃描數(shù)據(jù)庫。因此針對(duì)Apriori算法的這兩個(gè)缺點(diǎn)有人提出了利用HASH表和布爾矩陣的方法。而本文提出一種通過對(duì)項(xiàng)進(jìn)行編碼的算法來改進(jìn)Apfiofi算法可能更簡單實(shí)用，本算法可以大量減少侯選項(xiàng)目集數(shù)和數(shù)據(jù)庫掃描次數(shù)，在一定程度上優(yōu)化Apfiofi算法。為了使介紹的條理更為清晰，本文首先引入相關(guān)概念，具體介紹一下關(guān)聯(lián)規(guī)則；然后在此基礎(chǔ)上介紹通過對(duì)項(xiàng)編碼的方法來優(yōu)化Apnofi算法的改進(jìn)算法；接著舉例描述改進(jìn)算法挖掘關(guān)聯(lián)規(guī)則的過程；最后將實(shí)驗(yàn)結(jié)果繪制成曲線圖來直觀地對(duì)比兩個(gè)算法的執(zhí)行效率。

1 關(guān)聯(lián)規(guī)則描述

設(shè)I＝{i₁，i₂，…，i_n}是項(xiàng)集，其中的元素稱為項(xiàng)(item)。記DB為交易T(transaction)的集合，這里交易T是項(xiàng)的集合，并且T∈I。對(duì)應(yīng)每一個(gè)交易有唯一的標(biāo)識(shí)，如交易號(hào)，記作TID。設(shè)x是—個(gè)I中項(xiàng)的集合，如果x∈T，那么稱交易T包含x。

一個(gè)關(guān)聯(lián)規(guī)則是形如x＝＞Y的蘊(yùn)含式，這里x∈I，Y∈I并且X∩Y＝φ。

規(guī)則x＝＞Y在交易數(shù)據(jù)庫DB中的支持度(support)是交易集中包含x和Y的交易數(shù)與所有交易數(shù)之比，記為Support(X＝>Y)＝P(X∩Y)；

規(guī)則x＝＞Y在交易集中的可信度(Confidence)是指包含x和Y的交易數(shù)與包含x的交易數(shù)之比，記為：

Confidence(X＝＞Y)＝P(Ylx)

給定一個(gè)交易集DB，挖掘關(guān)聯(lián)規(guī)則問題就是產(chǎn)生支持度和可信度分別大于用戶給定的最小支持度(min—sup)和最小可信度(min--conf)的關(guān)聯(lián)規(guī)則。

Apfiofi算法把挖掘關(guān)聯(lián)規(guī)則的過程分為兩個(gè)階段：

(1)獲取頻繁集。這些項(xiàng)集出現(xiàn)的頻繁度至少和預(yù)定義的最小支持度一樣。

(2)由頻繁集產(chǎn)生關(guān)聯(lián)規(guī)則。這些規(guī)則必須滿足最小可信度。

第一階段的任務(wù)是迅速高效地找出DB中全部頻繁項(xiàng)目集，這是關(guān)聯(lián)規(guī)則挖掘的中心問題，也是衡量關(guān)聯(lián)規(guī)則挖掘算法的標(biāo)準(zhǔn)，一旦找到了頻繁集，就可以用文獻(xiàn)[4]提供的算法快速生成相應(yīng)的關(guān)聯(lián)規(guī)則。

2 對(duì)項(xiàng)編碼算法描述

本算法的主要思想是對(duì)所有的項(xiàng)，根據(jù)它在交易中出現(xiàn)的記錄進(jìn)行編碼，在編碼的同時(shí)就可以統(tǒng)計(jì)出項(xiàng)的支持度并生成頻繁1一項(xiàng)集。然后通過對(duì)不同編碼進(jìn)行“與”的運(yùn)算來得到頻繁二項(xiàng)集，并根據(jù)Apriori算法的大項(xiàng)目集性質(zhì)修改簡化編碼。如此循環(huán)最終得到符合關(guān)聯(lián)規(guī)則的頻繁項(xiàng)集。從以上描述可以看出本算法只需要掃描一遍數(shù)據(jù)庫，并且大幅減少了侯選集數(shù)量。下面詳細(xì)介紹該算法。

2.1 編碼規(guī)則

對(duì)項(xiàng)編碼在算法中起著極其重要的作用。編碼原則為：首先根據(jù)數(shù)據(jù)庫中存在的交易個(gè)數(shù)決定編碼長度，然后對(duì)這些交易順序進(jìn)行排序，每一個(gè)交易對(duì)應(yīng)編碼中的一個(gè)位置，如果某個(gè)項(xiàng)出現(xiàn)在第一個(gè)交易記錄中，就相應(yīng)的將編碼的一個(gè)位置設(shè)為‘l’，否則設(shè)為‘0’。假設(shè)某事務(wù)數(shù)據(jù)庫中有10條交易記錄(T₁，T₂，…T₁₀)，而某一個(gè)項(xiàng)出現(xiàn)在交易記錄T₁，T₃，T₄，T₉，T₁₀中，那么根據(jù)編碼規(guī)則可以得到該項(xiàng)的代碼為(1011000011)。

2.2 挖掘原理

當(dāng)每個(gè)項(xiàng)都有自己的編碼的同時(shí)也可以得到該項(xiàng)的編碼中‘1’的個(gè)數(shù)，也就是該項(xiàng)在所有事務(wù)記錄中出現(xiàn)的次數(shù)，在所有的編碼中‘1’的個(gè)數(shù)大于或等于最小支持度與總事務(wù)數(shù)的乘積的編碼所代表的項(xiàng)的集合就是頻繁1一項(xiàng)集。將頻繁1一項(xiàng)集中的項(xiàng)的編碼兩兩進(jìn)行“與”運(yùn)算，例如項(xiàng)i₁的編碼為1011000011，項(xiàng)i₂的編碼為1111000010，那么i_1∩2i₁∩i₂＝(1011000011)∩(1111000010)＝1011000010；新的編碼在生成的同時(shí)也可以得到新編碼中‘1’的個(gè)數(shù)，并根據(jù)‘1’的個(gè)數(shù)判斷其是否大于或等于最小支持度和置信度，如果大于或等于則被認(rèn)為是一條規(guī)則，并將參與運(yùn)算的兩個(gè)項(xiàng)放入待與項(xiàng)集(即大項(xiàng)集中包含在每一個(gè)大項(xiàng)中的單一項(xiàng)的集合)，當(dāng)所有項(xiàng)都完成運(yùn)算后，未出現(xiàn)在待與項(xiàng)集中的項(xiàng)將被刪除。以此類推，直到待與項(xiàng)集為空，則得到規(guī)則和頻繁n-項(xiàng)集。

2.3 算法描述

輸入：事物數(shù)據(jù)庫D，最小支持度閾值Vmin_sup。

輸出：D中的頻繁項(xiàng)集L。

現(xiàn)假設(shè)count(I₁∩I₂∩…∩I₂)為計(jì)算某個(gè)項(xiàng)的編碼或某幾個(gè)項(xiàng)做完與運(yùn)算后的編碼中有多少個(gè)‘1’的函數(shù)。則算法可描述為：

Ll＝frequent_1-itemsets(D)：

For(i＝2；Li-1≠ψ：i＋＋)

{Ci＝ψ；

Li＝ψ：

for each J1∈Ci-1 dO for each J2≠J1 ∈Ci-1 dO

if count(J1 NJ2n…nJi)≥Vmin_sup；

Lj＝LjU(J1∪J2∪…∪Ji)；

Ci＝Ci∪J1∪J2∪…∪Ji；

｝

3 舉例描述

從上述過程看，算法在第一步就掃描數(shù)據(jù)庫并對(duì)每個(gè)項(xiàng)完成編碼，以后的過程都是針對(duì)編碼進(jìn)行與運(yùn)算，不需要重復(fù)掃描數(shù)據(jù)庫，而且提高了挖掘的效率。

4 性能比較

最后，為了驗(yàn)證算法的先進(jìn)性，在同樣的實(shí)驗(yàn)條件下，將本文所述的優(yōu)化算法與Apfiori算法進(jìn)行了比較。圖1給出了當(dāng)所給支持度不同時(shí)兩種算法執(zhí)行時(shí)間的差別。由圖1可知，最小支持度越小，優(yōu)化后的算法的執(zhí)行時(shí)間比經(jīng)典Apriori算法的執(zhí)行時(shí)間少得越多，這說明優(yōu)化后的算法在給出支持度較小時(shí)具有較高的執(zhí)行效率。

圖2給出了當(dāng)數(shù)據(jù)庫中事務(wù)記錄數(shù)不同時(shí)兩種算法執(zhí)行時(shí)間的差別。由圖2可知，當(dāng)事務(wù)記錄適當(dāng)大時(shí)，優(yōu)化后的算法的效率比經(jīng)典Apriori算法的效率要高一些，這說明優(yōu)化后的算法在所給數(shù)據(jù)庫中記錄比較大時(shí)具有較高的執(zhí)行效率。

5 結(jié)束語

本文對(duì)挖掘關(guān)聯(lián)算法中的Apriori算法進(jìn)行了優(yōu)化和改進(jìn)，提出了一種對(duì)項(xiàng)進(jìn)行編碼并通過對(duì)不同項(xiàng)的編碼之間進(jìn)行“與”運(yùn)算來完成關(guān)聯(lián)規(guī)則挖掘的算法。該算法改善了Apriori算法需要多次掃描數(shù)據(jù)庫以及生成大量后選集的缺陷，也因此提高了發(fā)現(xiàn)頻繁集的效率。