基於關係數據庫的Apriori改進算法

    行業科技

    作者：王萌

    【摘要】本文根據Apriori算法的不足，提出了一種針對關係數據庫關聯規則挖掘的Apriori改進算法，可以提高數據挖掘的效率。

    【關鍵詞】數據挖掘；關聯規則；Apriori算法

    1.引言

    關聯規則挖掘是數據挖掘中最活躍的研究方法之一。最早是由Agrawal等人於1993年提出了挖掘交易數據庫中項目集之間的關聯規則問題。Agrawal等人於1994年提出了關聯規則挖掘的經典算法—Apriori算法。雖然Apriori算法自身已經進行了一定的優化，但是在實際的應用中，還是存在不令人滿意的地方：多次掃描事物數據庫，需要很大的I/0負載；可能產生龐大的候選集。

    挖掘關聯規則時，考慮不同字段的種類是必要的。對於事務數據庫，字段對應的項目是有限可數的離散問題。但是，一般的關係型數據庫，其中包含了大量的分類屬性和數值屬性。對於分類屬性和數值屬性，通過進行離散化處理，把關係數據庫轉換成事務數據庫，然後再利用目前討論比較多的和相對成熟的布爾關聯規則及其理論進行挖掘。

    （1）對於分類屬性，根據它的分類值的個數n映射到n個字符串集，記為{X1，X2，…，Xn}；

    （2）對於數值型屬性，使用某種離散化技術對該屬性離散化，離散化的數值屬性具有區間值，可以像分類屬性一樣（每個區間看作一類）映射到m個字符串集，記為{Y1，Y2，…，Ym}。

    把經過處理後的字符串看成項目，關係數據庫就映射成了僅包含項目的事務數據庫。

    2.基於關係數據庫的Apriori改進算法

    （1）關係數據庫中關聯規則具有多維性，並且是維間關聯規則，維內不可能出現關聯。在對候選項目集進行“剪枝”時，隻要判斷出是維內關聯的項目（數據處理後的字符串第一個字母相同就代表它屬於同一屬性值），直接將該項目刪除。

    （2）根據推論：如果某一事務不包含Ck中的任何項目集，那刪除該事務對Lj（j >=k）的計算沒有影響。在連接初步生成Ck時，將不包含Ck中的任何項目集的事務刪除。

    改進算法描述：

    算法①

    輸入：事物數據庫D，最小支持度minsupport

    輸出：頻繁項目集L

    L1={large 1itemsets（D）}；/*生成支持度不小於minsupport的1頻繁項目集*/

    For（k=2；Lk1≠？；k++）

    {Ck= apriori_gen（Lk1）；

    C=0；/*用來判斷t是否包含任何候選項*/

    For all tD

    {Ct=subset（Ck，t）；/*產生事務t中包含的候選集元素Ct*/

    For all cCt /* Ct是所有t包含的候選集元素*/

    {if（ti包含了Ck中的任何項）

    {c.count=c.count+1；/*計數*/

    C=C+1；}

    }

    if（C==0）

    {delete t from D；/*刪除D中不包含任何候選項集的記錄*/

    }

    }

    Lk={cCk | c.count minsupport}

    }

    Return L=∪Lk；