利用項編碼方法改進ａＰｒｉｏｒｉ算法

摘要：在眾多的關聯規則挖掘算法中Apriori算法是最為經典的一個，但Apfiofi算法有兩個缺陷，即：需要掃描多次數據庫以及生成大量的侯選集。文中對該算法進行改進提出了一種對項進行編碼的方法，通過對項編碼來減少掃描數據庫次數并通過刪除項來減少生成候選集的數量，從而提高算法的效率。實驗結果表明，優化后的算法能有效地提高關聯規則挖掘的效率。

關鍵詞：數據挖掘；關聯規則；Apfiofi算法；編碼

0 引言

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

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

1 關聯規則描述

設I＝{i₁，i₂，…，i_n}是項集，其中的元素稱為項(item)。記DB為交易T(transaction)的集合，這里交易T是項的集合，并且T∈I。對應每一個交易有唯一的標識，如交易號，記作TID。設x是—個I中項的集合，如果x∈T，那么稱交易T包含x。

一個關聯規則是形如x＝＞Y的蘊含式，這里x∈I，Y∈I并且X∩Y＝φ。

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

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

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

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

Apfiofi算法把挖掘關聯規則的過程分為兩個階段：

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

(2)由頻繁集產生關聯規則。這些規則必須滿足最小可信度。

第一階段的任務是迅速高效地找出DB中全部頻繁項目集，這是關聯規則挖掘的中心問題，也是衡量關聯規則挖掘算法的標準，一旦找到了頻繁集，就可以用文獻[4]提供的算法快速生成相應的關聯規則。

2 對項編碼算法描述

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

2.1 編碼規則

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

2.2 挖掘原理

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

2.3 算法描述

輸入：事物數據庫D，最小支持度閾值Vmin_sup。

輸出：D中的頻繁項集L。

現假設count(I₁∩I₂∩…∩I₂)為計算某個項的編碼或某幾個項做完與運算后的編碼中有多少個‘1’的函數。則算法可描述為：

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 舉例描述

從上述過程看，算法在第一步就掃描數據庫并對每個項完成編碼，以后的過程都是針對編碼進行與運算，不需要重復掃描數據庫，而且提高了挖掘的效率。

4 性能比較

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

圖2給出了當數據庫中事務記錄數不同時兩種算法執行時間的差別。由圖2可知，當事務記錄適當大時，優化后的算法的效率比經典Apriori算法的效率要高一些，這說明優化后的算法在所給數據庫中記錄比較大時具有較高的執行效率。

5 結束語

本文對挖掘關聯算法中的Apriori算法進行了優化和改進，提出了一種對項進行編碼并通過對不同項的編碼之間進行“與”運算來完成關聯規則挖掘的算法。該算法改善了Apriori算法需要多次掃描數據庫以及生成大量后選集的缺陷，也因此提高了發現頻繁集的效率。