數(shù)據(jù)庫關(guān)聯(lián)規(guī)則挖掘算法研究

劉曉慧

摘要：該文介紹了數(shù)據(jù)挖掘、關(guān)聯(lián)規(guī)則相關(guān)概念，分析了經(jīng)典的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的算法-Apriori算法，闡述了關(guān)聯(lián)規(guī)則的生成過程，并通過實例進行驗證。針對Apriori算法的缺陷進行了分析并列舉了幾種算法優(yōu)化方法。

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

中圖分類號：TP311 文獻標(biāo)識碼：A 文章編號：1009-3044（2014）16-3721-03

Abstract： This article describes the conception of data mining and association rules， Analyzes apriori algorithm，Its the classic algorithm in frequent itemsets mining base on boolean association rules， Describes the generation process of association rules and verified by examples. Analysis of the defects of apriori algorithm and several improved algorithms.

Key words： data mining； association rules； Apriori algorithm； threshold

1 數(shù)據(jù)挖掘

隨著計算機、網(wǎng)絡(luò)和信息技術(shù)的發(fā)展，采集和保存數(shù)據(jù)的能力也大大提高，信息大量涌現(xiàn)，如何從海量信息中找出所需的、有用的知識，成為了一個重要研究課題。數(shù)據(jù)挖掘一般是指從大量的實際數(shù)據(jù)中，通過算法搜索提取隱藏于其中的、有用的信息和知識的過程，同時通過分析大量數(shù)據(jù)來揭示有意義的新的關(guān)系和趨勢。數(shù)據(jù)挖掘融合了人工智能、機器學(xué)習(xí)、模式識別、統(tǒng)計學(xué)、數(shù)據(jù)庫、可視化技術(shù)等多個領(lǐng)域的理論和技術(shù)，是數(shù)據(jù)庫研究中的一個很重要且有應(yīng)用價值的領(lǐng)域。

2 關(guān)聯(lián)規(guī)則

數(shù)據(jù)關(guān)聯(lián)是數(shù)據(jù)庫中存在的可被發(fā)現(xiàn)的知識，若多個變量的取值存在某種規(guī)律性，就稱為關(guān)聯(lián)。關(guān)聯(lián)分析在數(shù)據(jù)挖掘中用于揭示數(shù)據(jù)項集之間的相互關(guān)系，生成關(guān)聯(lián)規(guī)則，形如[X?Y]的蘊含式。關(guān)聯(lián)規(guī)則挖掘要先從數(shù)據(jù)集合中找出所有的頻繁項目組（Frequent Itemsets），然后從頻繁項目組中產(chǎn)生強關(guān)聯(lián)規(guī)則（Association Rules）。具體描述如下：

假設(shè)[I={i1，i2，…，im}]是一個項目集合。給定一個事務(wù)數(shù)據(jù)庫[D={t1，t2，…，tn}]，其中每個事務(wù)[ti（i=1，2，…，n）]具有唯一標(biāo)識TID，且都對應(yīng)I上的一個非空子集。設(shè)[X?I]，項目集[X]在數(shù)據(jù)庫D上的支持度（support）指包含[X]的事務(wù)在D中的百分比，即：

[support（X）={t∈D|X∈I}D] （1）

對于項目集I和事務(wù)數(shù)據(jù)庫D，I中所有滿足用戶指定的最小支持度min_sup的項目集，稱為頻繁項目集。在頻繁項目集中選出所有不被其他元素包含的項目集稱為最大頻繁項目集。

如果有[X?I，Y?I，X?Y=φ]，則一個定義在I和D上的關(guān)聯(lián)規(guī)則形如“[X?Y]”，其置信度（Confidence）指包含[X]和[Y]的事務(wù)數(shù)與包含[X]的事務(wù)數(shù)的比值，即：

[Confidence（X?Y）=support（X?Y）support（X）] （2）

關(guān)聯(lián)規(guī)則挖掘就是用戶根據(jù)需要設(shè)定最小支持度和最小置信度min_conf閾值，搜索滿足這兩個閾值的關(guān)聯(lián)規(guī)則的過程，滿足條件的關(guān)聯(lián)規(guī)則稱為強關(guān)聯(lián)規(guī)則。

根據(jù)規(guī)則中處理的變量的類別，關(guān)聯(lián)規(guī)則可以分為布爾型和數(shù)值型。布爾型關(guān)聯(lián)規(guī)則處理的是離散的、種類化的值，揭示這些變量之間的關(guān)系；數(shù)值型關(guān)聯(lián)規(guī)則對數(shù)值型字段進行處理，可以將其進行動態(tài)分割，或直接對原始數(shù)據(jù)進行處理。

3 Apriori算法

3.1 算法描述

關(guān)聯(lián)規(guī)則由Agrawal等人于1993年首次提出之后，研究人員對數(shù)據(jù)庫關(guān)聯(lián)規(guī)則挖掘方法進行了大量研究，提出了多種算法，如Apriori算法、基于劃分的算法、FP-樹頻集算法等，其中最有影響的是Apriori算法。

Apriori算法是挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的經(jīng)典算法，該算法首先使用逐層搜索的迭代法，根據(jù)最小支持度閾值，找出所有的頻繁項集。然后由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則：給出最小置信度閾值，針對每個頻繁項集，生成其所有非空子集，計算每個非空子集的置信度，置信度滿足最小置信度閾值，則相應(yīng)關(guān)聯(lián)規(guī)則成立。算法核心思想描述如下：

1） [L1=find_frequent_1_itemsets（D）；]

2） [for（k=2；Lk-1≠φ；k++）{]

3） [Ck=apriori_gen（Lk-1，min_sup）；]

4） [foreachtransactiont∈D{//scanDforcounts]

5） [Ct=subset（Ck，t）；//getthesubsetsoftthatarecandidates]

6） [foreachcandidatec∈Ct]

7） [c.count++；]

8） [}]

9） [Lk={c∈Ck|c.count≥min_sup}]

10）[}]

11）[returnL=UkLk；]

利用該算法挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集時，首先找出頻繁1-項集[L1]，然后用[L1]找到頻繁2-項集[L2]，依此類推，直到找不到頻繁k-項集[Lk]為止。算法中找每個頻繁項集時需要掃描一次數(shù)據(jù)庫。endprint

該算法由連接和剪枝兩個步驟組成，為了找到[Lk]，通過[Lk-1]與自身連接產(chǎn)生候選k-項集的集合，該候選項集的集合記作[Ck]； [Ck]是[Lk]的超集，它的成員不一定都是頻繁項集，但所有頻繁k-項集都在[Ck]中，通過計算每個k-項集的支持度來得到[Lk]。

3.2 算法舉例

例：以下關(guān)系（credit_bill）是模擬銀行對某單位年度個人信用卡賬單的統(tǒng)計數(shù)據(jù)：

關(guān)系中“Sex”、“Wedded” 和“Title”字段是布爾型，“Age”、“Income”和“Bill”字段是數(shù)值型，使用Apriori算法對關(guān)系中布爾型數(shù)據(jù)集進行關(guān)聯(lián)規(guī)則挖掘，先對相應(yīng)屬性值時行離散化處理，將“Sex”屬性的兩種取值“男”和“女”離散化為屬性s1和s2，“Wedded”屬性取值“已婚”和“未婚”離散化為屬性w1和w2，“Title”屬性取值“高級”、“中級”和“初級”離散化為屬性t1、t2和t3。設(shè)最小支持度和最小置信度閾值均為50%，則挖掘過程如圖1所示。

通過上述搜索過程得到頻繁項集[L2]，其中支持度由公式（1）計算得出，由頻繁項集生成的關(guān)聯(lián)規(guī)則及由公式（2）計算得出的規(guī)則置信度如下：

1） { w1} [?]{ t2}（Confidence（w1[?]t2）=70%）

2） { t2} [?]{ w1}（Confidence（t2[?]w1）=70%）

規(guī)則置信度大于最小置信度閾值，說明所得規(guī)則有效。此規(guī)則說明關(guān)系所列數(shù)據(jù)中信用卡持有者男性過半數(shù)，而且持卡人中男性一定是已婚或已婚一定是男性的可能性均為70%。

3.3 算法優(yōu)化

Apriori算法雖然經(jīng)典，但有兩個性能上的瓶頸：在搜索k-頻繁項集時，侯選集[Ck]中每個元素都必須通過掃描數(shù)據(jù)庫來確認(rèn)其是否放入頻繁項集中，因此需要對數(shù)據(jù)庫進行k次掃描，數(shù)據(jù)庫中數(shù)據(jù)量越大，搜索效率越低；由[Lk-1]生成k-侯選項集[Ck]時，[Ck]中元素個數(shù)是指數(shù)增長的，因此數(shù)據(jù)量越大，生成的侯選集也就越龐大，既耗費時間，也需要大量的存儲空間。

針對Apriori算法中的缺陷，不同學(xué)者提出了多種不同的改進方法，如Park等人提出的引入散列技術(shù)改進產(chǎn)生頻繁2-項集的方法，或高效產(chǎn)生頻繁項目集的基于雜湊的算法；Agrawal等人提出的壓縮進一步迭代掃描的事務(wù)數(shù)的方法；Savasere等人提出的基于劃分的方法；Mannila等人提出的通過對數(shù)據(jù)庫采樣發(fā)現(xiàn)規(guī)則的方法；Brin等人提出的動態(tài)項集計數(shù)方法等。這些方法雖然對Apriori算法進行了優(yōu)化，但沒能克服Apriori算法中的固有缺陷：可以產(chǎn)生龐大的侯選集；最小支持度閾值設(shè)定值較低時，算法執(zhí)行效率會降低，而閾值設(shè)定較高時，會影響規(guī)則產(chǎn)生。

針對上述算法缺陷中的前一種情況，[4]提出采用FP-growth方法，第一次掃描數(shù)據(jù)庫后，將得到的頻繁項集放進一棵頻繁模式樹FP-tree，再將這棵樹分解成多個條件庫，對這些條件庫分別進行挖掘，該方法能適應(yīng)不同長度的規(guī)則，而且執(zhí)行效率也大大提高。

4 結(jié)束語

對于數(shù)據(jù)庫關(guān)聯(lián)規(guī)則挖掘方法，該文只針對布爾型值進行了介紹，分析了經(jīng)典的Apriori算法挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的過程及關(guān)聯(lián)規(guī)則的得出，并針對Apriori算法的缺陷進行了分析，對多種優(yōu)化算法進行了闡述。對于數(shù)據(jù)庫來說，數(shù)值型字段也是其主要組成部分，而關(guān)聯(lián)規(guī)則挖掘也同樣可以針對數(shù)據(jù)值字段，并和多層關(guān)聯(lián)規(guī)則結(jié)合，或同模糊理論相聯(lián)系，分析并找出數(shù)據(jù)間聯(lián)系，具有重要現(xiàn)實意義。

參考文獻：

[1] 杜玉蘭.基于模糊理論的關(guān)聯(lián)規(guī)則挖掘算法研究[D].保定：華北電力大學(xué)，2008.

[2] 梁循. 數(shù)據(jù)挖掘算法與應(yīng)用[M].北京：北京大學(xué)出版社，2006.

[3] http：//www.chinaai.org/pr/pattern-recognition/association-rules-mining.html

[4] Han J，Pei J，Yin Y.Mining frequent patterns without candidate generation[C].Proc.2000 ACM-SIGMOD Int.Conf.Management of Data，Dalas，TX，2000.endprint

該算法由連接和剪枝兩個步驟組成，為了找到[Lk]，通過[Lk-1]與自身連接產(chǎn)生候選k-項集的集合，該候選項集的集合記作[Ck]； [Ck]是[Lk]的超集，它的成員不一定都是頻繁項集，但所有頻繁k-項集都在[Ck]中，通過計算每個k-項集的支持度來得到[Lk]。

3.2 算法舉例

例：以下關(guān)系（credit_bill）是模擬銀行對某單位年度個人信用卡賬單的統(tǒng)計數(shù)據(jù)：

關(guān)系中“Sex”、“Wedded” 和“Title”字段是布爾型，“Age”、“Income”和“Bill”字段是數(shù)值型，使用Apriori算法對關(guān)系中布爾型數(shù)據(jù)集進行關(guān)聯(lián)規(guī)則挖掘，先對相應(yīng)屬性值時行離散化處理，將“Sex”屬性的兩種取值“男”和“女”離散化為屬性s1和s2，“Wedded”屬性取值“已婚”和“未婚”離散化為屬性w1和w2，“Title”屬性取值“高級”、“中級”和“初級”離散化為屬性t1、t2和t3。設(shè)最小支持度和最小置信度閾值均為50%，則挖掘過程如圖1所示。

通過上述搜索過程得到頻繁項集[L2]，其中支持度由公式（1）計算得出，由頻繁項集生成的關(guān)聯(lián)規(guī)則及由公式（2）計算得出的規(guī)則置信度如下：

1） { w1} [?]{ t2}（Confidence（w1[?]t2）=70%）

2） { t2} [?]{ w1}（Confidence（t2[?]w1）=70%）

規(guī)則置信度大于最小置信度閾值，說明所得規(guī)則有效。此規(guī)則說明關(guān)系所列數(shù)據(jù)中信用卡持有者男性過半數(shù)，而且持卡人中男性一定是已婚或已婚一定是男性的可能性均為70%。

3.3 算法優(yōu)化

Apriori算法雖然經(jīng)典，但有兩個性能上的瓶頸：在搜索k-頻繁項集時，侯選集[Ck]中每個元素都必須通過掃描數(shù)據(jù)庫來確認(rèn)其是否放入頻繁項集中，因此需要對數(shù)據(jù)庫進行k次掃描，數(shù)據(jù)庫中數(shù)據(jù)量越大，搜索效率越低；由[Lk-1]生成k-侯選項集[Ck]時，[Ck]中元素個數(shù)是指數(shù)增長的，因此數(shù)據(jù)量越大，生成的侯選集也就越龐大，既耗費時間，也需要大量的存儲空間。

針對Apriori算法中的缺陷，不同學(xué)者提出了多種不同的改進方法，如Park等人提出的引入散列技術(shù)改進產(chǎn)生頻繁2-項集的方法，或高效產(chǎn)生頻繁項目集的基于雜湊的算法；Agrawal等人提出的壓縮進一步迭代掃描的事務(wù)數(shù)的方法；Savasere等人提出的基于劃分的方法；Mannila等人提出的通過對數(shù)據(jù)庫采樣發(fā)現(xiàn)規(guī)則的方法；Brin等人提出的動態(tài)項集計數(shù)方法等。這些方法雖然對Apriori算法進行了優(yōu)化，但沒能克服Apriori算法中的固有缺陷：可以產(chǎn)生龐大的侯選集；最小支持度閾值設(shè)定值較低時，算法執(zhí)行效率會降低，而閾值設(shè)定較高時，會影響規(guī)則產(chǎn)生。

針對上述算法缺陷中的前一種情況，[4]提出采用FP-growth方法，第一次掃描數(shù)據(jù)庫后，將得到的頻繁項集放進一棵頻繁模式樹FP-tree，再將這棵樹分解成多個條件庫，對這些條件庫分別進行挖掘，該方法能適應(yīng)不同長度的規(guī)則，而且執(zhí)行效率也大大提高。

4 結(jié)束語

對于數(shù)據(jù)庫關(guān)聯(lián)規(guī)則挖掘方法，該文只針對布爾型值進行了介紹，分析了經(jīng)典的Apriori算法挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的過程及關(guān)聯(lián)規(guī)則的得出，并針對Apriori算法的缺陷進行了分析，對多種優(yōu)化算法進行了闡述。對于數(shù)據(jù)庫來說，數(shù)值型字段也是其主要組成部分，而關(guān)聯(lián)規(guī)則挖掘也同樣可以針對數(shù)據(jù)值字段，并和多層關(guān)聯(lián)規(guī)則結(jié)合，或同模糊理論相聯(lián)系，分析并找出數(shù)據(jù)間聯(lián)系，具有重要現(xiàn)實意義。

參考文獻：

[1] 杜玉蘭.基于模糊理論的關(guān)聯(lián)規(guī)則挖掘算法研究[D].保定：華北電力大學(xué)，2008.

[2] 梁循. 數(shù)據(jù)挖掘算法與應(yīng)用[M].北京：北京大學(xué)出版社，2006.

[3] http：//www.chinaai.org/pr/pattern-recognition/association-rules-mining.html

[4] Han J，Pei J，Yin Y.Mining frequent patterns without candidate generation[C].Proc.2000 ACM-SIGMOD Int.Conf.Management of Data，Dalas，TX，2000.endprint

該算法由連接和剪枝兩個步驟組成，為了找到[Lk]，通過[Lk-1]與自身連接產(chǎn)生候選k-項集的集合，該候選項集的集合記作[Ck]； [Ck]是[Lk]的超集，它的成員不一定都是頻繁項集，但所有頻繁k-項集都在[Ck]中，通過計算每個k-項集的支持度來得到[Lk]。

3.2 算法舉例

例：以下關(guān)系（credit_bill）是模擬銀行對某單位年度個人信用卡賬單的統(tǒng)計數(shù)據(jù)：

關(guān)系中“Sex”、“Wedded” 和“Title”字段是布爾型，“Age”、“Income”和“Bill”字段是數(shù)值型，使用Apriori算法對關(guān)系中布爾型數(shù)據(jù)集進行關(guān)聯(lián)規(guī)則挖掘，先對相應(yīng)屬性值時行離散化處理，將“Sex”屬性的兩種取值“男”和“女”離散化為屬性s1和s2，“Wedded”屬性取值“已婚”和“未婚”離散化為屬性w1和w2，“Title”屬性取值“高級”、“中級”和“初級”離散化為屬性t1、t2和t3。設(shè)最小支持度和最小置信度閾值均為50%，則挖掘過程如圖1所示。

通過上述搜索過程得到頻繁項集[L2]，其中支持度由公式（1）計算得出，由頻繁項集生成的關(guān)聯(lián)規(guī)則及由公式（2）計算得出的規(guī)則置信度如下：

1） { w1} [?]{ t2}（Confidence（w1[?]t2）=70%）

2） { t2} [?]{ w1}（Confidence（t2[?]w1）=70%）

規(guī)則置信度大于最小置信度閾值，說明所得規(guī)則有效。此規(guī)則說明關(guān)系所列數(shù)據(jù)中信用卡持有者男性過半數(shù)，而且持卡人中男性一定是已婚或已婚一定是男性的可能性均為70%。

3.3 算法優(yōu)化

Apriori算法雖然經(jīng)典，但有兩個性能上的瓶頸：在搜索k-頻繁項集時，侯選集[Ck]中每個元素都必須通過掃描數(shù)據(jù)庫來確認(rèn)其是否放入頻繁項集中，因此需要對數(shù)據(jù)庫進行k次掃描，數(shù)據(jù)庫中數(shù)據(jù)量越大，搜索效率越低；由[Lk-1]生成k-侯選項集[Ck]時，[Ck]中元素個數(shù)是指數(shù)增長的，因此數(shù)據(jù)量越大，生成的侯選集也就越龐大，既耗費時間，也需要大量的存儲空間。

針對Apriori算法中的缺陷，不同學(xué)者提出了多種不同的改進方法，如Park等人提出的引入散列技術(shù)改進產(chǎn)生頻繁2-項集的方法，或高效產(chǎn)生頻繁項目集的基于雜湊的算法；Agrawal等人提出的壓縮進一步迭代掃描的事務(wù)數(shù)的方法；Savasere等人提出的基于劃分的方法；Mannila等人提出的通過對數(shù)據(jù)庫采樣發(fā)現(xiàn)規(guī)則的方法；Brin等人提出的動態(tài)項集計數(shù)方法等。這些方法雖然對Apriori算法進行了優(yōu)化，但沒能克服Apriori算法中的固有缺陷：可以產(chǎn)生龐大的侯選集；最小支持度閾值設(shè)定值較低時，算法執(zhí)行效率會降低，而閾值設(shè)定較高時，會影響規(guī)則產(chǎn)生。

針對上述算法缺陷中的前一種情況，[4]提出采用FP-growth方法，第一次掃描數(shù)據(jù)庫后，將得到的頻繁項集放進一棵頻繁模式樹FP-tree，再將這棵樹分解成多個條件庫，對這些條件庫分別進行挖掘，該方法能適應(yīng)不同長度的規(guī)則，而且執(zhí)行效率也大大提高。

4 結(jié)束語

對于數(shù)據(jù)庫關(guān)聯(lián)規(guī)則挖掘方法，該文只針對布爾型值進行了介紹，分析了經(jīng)典的Apriori算法挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的過程及關(guān)聯(lián)規(guī)則的得出，并針對Apriori算法的缺陷進行了分析，對多種優(yōu)化算法進行了闡述。對于數(shù)據(jù)庫來說，數(shù)值型字段也是其主要組成部分，而關(guān)聯(lián)規(guī)則挖掘也同樣可以針對數(shù)據(jù)值字段，并和多層關(guān)聯(lián)規(guī)則結(jié)合，或同模糊理論相聯(lián)系，分析并找出數(shù)據(jù)間聯(lián)系，具有重要現(xiàn)實意義。

參考文獻：

[1] 杜玉蘭.基于模糊理論的關(guān)聯(lián)規(guī)則挖掘算法研究[D].保定：華北電力大學(xué)，2008.

[2] 梁循. 數(shù)據(jù)挖掘算法與應(yīng)用[M].北京：北京大學(xué)出版社，2006.

[3] http：//www.chinaai.org/pr/pattern-recognition/association-rules-mining.html

[4] Han J，Pei J，Yin Y.Mining frequent patterns without candidate generation[C].Proc.2000 ACM-SIGMOD Int.Conf.Management of Data，Dalas，TX，2000.endprint