APRIORI

挖掘關聯規則的頻繁項集演演算法

Apriori演演算法是一種挖掘關聯規則的頻繁項集演演算法,其核心思想是通過候選集生成和情節的向下封閉檢測兩個階段來挖掘頻繁項集。而且演演算法已經被廣泛的應用到商業、網路安全等各個領域。

演演算法簡介


Apriori演演算法 是一種最有影響的挖掘布爾關聯規則頻繁項集的演演算法。其核心是基於兩階段頻集思想的遞推演演算法。該關聯規則在分類上屬於單維、單層、布爾關聯規則。在這裡,所有支持度大於最小支持度的項集稱為頻繁項集,簡稱頻集。

演演算法思想


該演演算法的基本思想是:首先找出所有的頻集,這些項集出現的頻繁性至少和預定義的最小支持度一樣。然後由頻集產生強關聯規則,這些規則必須滿足最小支持度和最小可信度。然後使用第1步找到的頻集產生期望的規則,產生只包含集合的項的所有規則,其中每一條規則的右部只有一項,這裡採用的是中規則的定義。一旦這些規則被生成,那麼只有那些大於用戶給定的最小可信度的規則才被留下來。為了生成所有頻集,使用了遞歸的方法。
(1) L1 = find_frequent_1-itemsets(D);
(2) for (k=2;Lk-1 ≠Φ ;k++) {
(3) Ck = apriori_gen(Lk-1 ,min_sup);
(4) for each transaction t ∈ D {//scan D for counts
(5) Ct = subset(Ck,t);//get the subsets of t that are candidates
(6) for each candidate c ∈ Ct
(7) c.count++;
(8) }
(9) Lk ={c ∈ Ck|c.count≥min_sup}
(10) }
(11) return L= ∪ k Lk;
可能產生大量的候選集,以及可能需要重複掃描資料庫,是Apriori演演算法的兩大缺點。
流程圖如下:

演演算法應用


經典的關聯規則數據挖掘演演算法Apriori 演演算法廣泛應用於各種領域,通過對數據的關聯性進行了分析和挖掘,挖掘出的這些信息在決策制定過程中具有重要的參考價值。
Apriori演演算法廣泛應用於商業中,應用於消費市場價格分析中,它能夠很快的求出各種產品之間的價格關係和它們之間的影響。通過數據挖掘,市場商人可以瞄準目標客戶,採用個人股票行市、最新信息、特殊的市場推廣活動或其他一些特殊的信息手段,從而極大地減少廣告預算和增加收入。百貨商場、超市和一些老字型大小的零售店也在進行數據挖掘,以便猜測這些年來顧客的消費習慣。
Apriori演演算法應用於網路安全領域,比如網路入侵檢測技術中。早期中大型的電腦系統中都收集審計信息來建立跟蹤檔,這些審計跟蹤的目的多是為了性能測試或計費,因此對攻擊檢測提供的有用信息比較少。它通過模式的學習和訓練可以發現網路用戶的異常行為模式。採用作用度的Apriori演演算法削弱了Apriori演演算法的挖掘結果規則,是網路入侵檢測系統可以快速的發現用戶的行為模式,能夠快速的鎖定攻擊者,提高了基於關聯規則的入侵檢測系統的檢測性。
Apriori演演算法應用於高校管理中。隨著高校貧困生人數的不斷增加,學校管理部門資助工作難度也越加增大。針對這一現象,提出一種基於數據挖掘演演算法的解決方法。將關聯規則的Apriori演演算法應用到貧困助學體系中,並且針對經典Apriori挖掘演演算法存在的不足進行改進,先將事務資料庫映射為一個布爾矩陣,用一種逐層遞增的思想來動態的分配內存進行存儲,再利用向量求"與"運算,尋找頻繁項集。實驗結果表明,改進后的Apriori演演算法在運行效率上有了很大的提升,挖掘出的規則也可以有效地輔助學校管理部門有針對性的開展貧困助學工作。
Apriori演演算法被廣泛應用於移動通信領域。移動增值業務逐漸成為移動通信市場上最有活力、最具潛力、最受矚目的業務。隨著產業的復甦,越來越多的增值業務表現出強勁的發展勢頭,呈現出應用多元化、營銷品牌化、管理集中化、合作縱深化的特點。針對這種趨勢,在關聯規則數據挖掘中廣泛應用的Apriori演演算法被很多公司應用。依託某電信運營商正在建設的增值業務Web數據倉庫平台,對來自移動增值業務方面的調查數據進行了相關的挖掘處理,從而獲得了關於用戶行為特徵和需求的間接反映市場動態的有用信息,這些信息在指導運營商的業務運營和輔助業務提供商的決策制定等方面具有十分重要的參考價值。