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數據倉庫平台，對來自移動增值業務方面的調查數據進行了相關的挖掘處理，從而獲得了關于用戶行為特征和需求的間接反映市場動态的有用信息，這些信息在指導運營商的業務運營和輔助業務提供商的決策制定等方面具有十分重要的參考價值。