APRIORI

關聯規則挖掘是數據挖掘中最活躍的研究方法之一 。最早是由 Agrawal 等人提出的1993最初提出的動機是針對購物籃分析問題提出的，其目的是為了發現交易數據庫中不同商品之間的聯繫規則。這些規則刻畫了顧客購買行為模式，可以用來指導商家科學地安排進貨，庫存以及貨架設計等。之後諸多的研究人員對關聯規則的挖掘問題進行了大量的研究。他們的工作涉及到關聯規則的挖掘理論的探索，原有的算法的改進和新算法的設計，並行關聯規則挖掘Parallel Association Rule Mining，以及數量關聯規則挖掘Quantitive Association Rule Mining 等問題。在提高挖掘規則算法的效率、適應性、可用性以及應用推廣等方面，許多學者進行了不懈的努力。

Apriori算法是種挖掘關聯規則的頻繁項集算法，一種最有影響的挖掘布爾關聯規則頻繁項集的算法。其核心思想是通過候選集生成和情節的向下封閉檢測兩個階段來挖掘頻繁項集。其核心是基於兩階段頻集思想的遞推算法。該關聯規則在分類上屬於單維、單層、布爾關聯規則。在這裏，所有支持度大於最小支持度的項集稱為頻繁項集，簡稱頻集。Apriori算法已經被廣泛的應用到商業、網絡安全等各個領域。Apriori算法採用了逐層搜索的迭代的方法，算法簡單明瞭，沒有複雜的理論推導，也易於實現。但其有一些難以克服的缺點：

（1）對數據庫的掃描次數過多。

（2）Apriori算法會產生大量的中間項集。

（3）採用唯一支持度。

（4）算法的適應面窄。

該算法的基本思想是：首先找出所有的頻集，這些項集出現的頻繁性至少和預定義的最小支持度一樣。然後由頻集產生強關聯規則，這些規則必須滿足最小支持度和最小可信度。然後使用第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數據倉庫平台，對來自移動增值業務方面的調查數據進行了相關的挖掘處理，從而獲得了關於用户行為特徵和需求的間接反映市場動態的有用信息，這些信息在指導運營商的業務運營和輔助業務提供商的決策制定等方面具有十分重要的參考價值。

在地球科學數據分析中，關聯模式可以揭示海洋、陸地和大氣過程之間的有意義的關係。這些信息能夠幫助地球科學家更好的理解地球系統中不同的自然力之間的相互作用。

支持度（support）：support(A=>B) = P(A∪B)，表示A和B同時出現的概率。

置信度（confidence）：confidence(A=>B)=support(A∪B) / support(A)，表示A和B同時出現的概率佔A出現概率的比值。

頻繁項集：頻繁項集挖掘是數據挖掘研究課題中一個很重要的研究基礎，它可以告訴我們在數據集中經常一起出現的變量，為可能的決策提供一些支持。頻繁項集挖掘是關聯規則、相關性分析、因果關係、序列項集、局部週期性、情節片段等許多重要數據挖掘任務的基礎。因此，頻繁項集有着很廣泛的應用，例如：購物籃數據分析、網頁預取、交叉購物、個性化網站、網絡入侵檢測等。，對頻繁項集挖掘算法進行研究的方向大概可歸納為以下四個方面：一、在遍歷方向上採取自底向上、自頂向下以及混合遍歷的方式；二、在搜索策略上採取深度優先和寬度優先策略；三、在項集的產生上着眼於是否會產生候選項集；四、在數據庫的佈局上，從垂直和水平兩個方向上考慮數據庫的佈局。對於不同的遍歷方式，數據庫的搜索策略和佈局方式將會產生不同的方法，研究表明，沒有什麼挖掘算法能同時對所有的定義域和數據類型都優於其他的挖掘算法，也就是説，對於每一種相對較為優秀的算法，它都有它具體的適用場景和環境。 ^[2] 

強關聯規則：滿足最小支持度和最小置信度的關聯規則。