人工智能機(jī)器學(xué)習(xí)有關(guān)算法內(nèi)容，請參見公眾號“科技優(yōu)化生活”之前相關(guān)文章。人工智能之機(jī)器學(xué)習(xí)主要有三大類:1)分類;2)回歸;3)聚類。今天我們重點探討一下Apriori算法。^_^
Apriori算法是經(jīng)典的挖掘頻繁項集和關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法，也是十大經(jīng)典機(jī)器學(xué)習(xí)算法之一。
Agrawal和Srikant兩位博士在1994年提出了Apriori算法，主要用于做快速的關(guān)聯(lián)規(guī)則分析。
A priori在拉丁語中指"來自以前"。當(dāng)定義問題時，通常會使用先驗知識或者假設(shè)，這被稱作"一個先驗"（a priori）。Apriori算法正是基于這樣的事實：算法使用頻繁項集性質(zhì)的先驗性質(zhì)，即頻繁項集的所有非空子集也一定是頻繁的。
Apriori算法概念：
Apriori算法使用一種稱為逐層搜索的迭代方法，其中k項集用于探索(k+1)項集。首先，通過掃描數(shù)據(jù)庫，累計每個項的計數(shù)，并收集滿足最小支持度的項，找出頻繁1項集的集合。該集合記為L1。然后，使用L1找出頻繁2項集的集合L2，使用L2找出L3，如此下去，直到不能再找到頻繁k項集。每找出一個Lk需要一次數(shù)據(jù)庫的完整掃描。Apriori算法使用頻繁項集的先驗性質(zhì)來壓縮搜索空間。
注：數(shù)據(jù)庫中的數(shù)據(jù)可以是結(jié)構(gòu)化的，也可以是半結(jié)構(gòu)化的，甚至還可以是分布在網(wǎng)絡(luò)上的異構(gòu)型數(shù)據(jù)。
Apriori算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的算法。其核心是基于兩階段頻集思想的遞推算法。該關(guān)聯(lián)規(guī)則在分類上屬于單維、單層、布爾關(guān)聯(lián)規(guī)則。在這里，所有支持度大于最小支持度的項集稱為頻繁項集，簡稱頻集。
Apriori算法中術(shù)語：
1、項集和K-項集
令I(lǐng)={i1,i2,i3……id}是數(shù)據(jù)中所有項的集合，而T={t1,t2,t3….tN}是所有事務(wù)的集合，每個事務(wù)ti包含的項集都是I的子集。在關(guān)聯(lián)分析中，包含0個或多個項的集合稱為項集。如果一個項集包含K個項，則稱它為K-項集。空集是指不包含任何項的項集。
2、支持度計數(shù)
項集的一個重要性質(zhì)是它的支持度計數(shù)，即包含特定項集的事務(wù)個數(shù)，數(shù)學(xué)上，項集X的支持度計數(shù)σ(X)可以表示為：
σ(X)=|{ti|X?ti,ti∈T}|其中，符號|*|表示集合中元素的個數(shù)。
3、關(guān)聯(lián)規(guī)則
關(guān)聯(lián)規(guī)則是形如X→Y的蘊(yùn)含表達(dá)式，其中X和Y是不相交的項集，即X∩Y=空。
關(guān)聯(lián)規(guī)則的強(qiáng)度可以用它的支持度(support)和置信度(confidence)來度量。
支持度確定規(guī)則可以用于給定數(shù)據(jù)集的頻繁程度，而置信度確定Y在包含X的事務(wù)中出現(xiàn)的頻繁程度。支持度(s)和置信度(c)這兩種度量的形式定義如下：s(X→Y)=σ(X∪Y)/Nc(X→Y)=σ(X∪Y)/σ(X)其中， σ(X∪Y)是(X∪Y)的支持度計數(shù)，N為事務(wù)總數(shù)，σ(X)是X的支持度計數(shù)。
對于靠譜的關(guān)聯(lián)規(guī)則，其支持度與置信度均應(yīng)大于設(shè)定的閾值。那么，關(guān)聯(lián)分析問題即等價于：對給定的支持度閾值min_sup、置信度閾值min_conf，找出所有的滿足下列條件的關(guān)聯(lián)規(guī)則：
支持度>=min_sup
置信度>=min_conf
把支持度大于閾值的項集稱為頻繁項集（frequent itemset）。因此，關(guān)聯(lián)規(guī)則分析可分為下列兩個步驟：
1）生成頻繁項集F=X∪Y；
2）在頻繁項集F中，找出所有置信度大于最小置信度的關(guān)聯(lián)規(guī)則X->Y
Apriori算法思想：
1）找出所有的頻集，這些項集出現(xiàn)的頻繁性至少和預(yù)定義的最小支持度一樣。
2）由頻集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則，這些規(guī)則必須滿足最小支持度和最小可信度。
3）使用第1）步找到的頻集產(chǎn)生期望的規(guī)則，產(chǎn)生只包含集合的項的所有規(guī)則，其中每一條規(guī)則的右部只有一項，這里采用的是中規(guī)則的定義。
4）一旦這些規(guī)則被生成，那么只有那些大于用戶給定的最小可信度的規(guī)則才被留下來。為了生成所有頻集，使用了遞歸的方法。
Aprior算法程序如下：
Apriori算法優(yōu)點：
1）使用先驗性質(zhì)，大大提高了頻繁項集逐層產(chǎn)生的效率；
2）簡單易理解；
3）數(shù)據(jù)集要求低；
4）擴(kuò)展性較好，可以并行計算。
Apriori算法缺點：
1)可能產(chǎn)生大量的候選集；
2)可能需要重復(fù)掃描整個數(shù)據(jù)庫，非常耗時。
Apriori算法改進(jìn)：
定理：如果規(guī)則X->Y?X 不滿足置信度閾值, 則對于X的子集X′->Y?X′也不滿足置信度閾值。
根據(jù)此定理，可對規(guī)則樹進(jìn)行剪枝，其具體改進(jìn)的算法如下：
Apriori算法應(yīng)用：
通過對數(shù)據(jù)的關(guān)聯(lián)性進(jìn)行了分析和挖掘，挖掘出的這些信息在決策制定過程中具有重要的參考價值。Apriori 算法被廣泛應(yīng)用于各種領(lǐng)域：
1）應(yīng)用于商業(yè)活動領(lǐng)域，應(yīng)用于消費市場價格分析中，它能夠很快的求出各種產(chǎn)品之間的價格關(guān)系和它們之間的影響。
2）應(yīng)用于網(wǎng)絡(luò)安全領(lǐng)域，通過模式的學(xué)習(xí)和訓(xùn)練可以發(fā)現(xiàn)網(wǎng)絡(luò)用戶的異常行為模式，能夠快速的鎖定攻擊者，提高了基于關(guān)聯(lián)規(guī)則的入侵檢測系統(tǒng)的檢測性。
3）應(yīng)用于高校管理中。隨著高校貧困生人數(shù)的不斷增加，學(xué)校管理部門資助工作難度也越加增大。針對這一現(xiàn)象，將關(guān)聯(lián)規(guī)則的Apriori算法應(yīng)用到貧困助學(xué)體系中，挖掘出的規(guī)則也可以有效地輔助學(xué)校管理部門有針對性的開展貧困助學(xué)工作。
4）應(yīng)用于移動通信領(lǐng)域。基于移動通信運營商正在建設(shè)的增值業(yè)務(wù)Web數(shù)據(jù)倉庫平臺，對來自移動增值業(yè)務(wù)方面的調(diào)查數(shù)據(jù)進(jìn)行了相關(guān)的挖掘處理，從而獲得了關(guān)于用戶行為特征和需求的間接反映市場動態(tài)的有用信息，這些信息在指導(dǎo)運營商的業(yè)務(wù)運營和輔助業(yè)務(wù)提供商的決策制定等方面具有十分重要的參考價值。
結(jié)語:
Apriori算法是一種挖掘關(guān)聯(lián)規(guī)則的頻繁項集算法，其核心思想是通過候選集生成和情節(jié)的向下封閉檢測兩個階段來挖掘頻繁項集。主要用于做快速的關(guān)聯(lián)規(guī)則分析。Apriori算法在世界上廣為流傳，得到極大的關(guān)注。Apriori算法已經(jīng)被廣泛的應(yīng)用到商業(yè)、網(wǎng)絡(luò)安全、高校管理和移動通信等領(lǐng)域。
------以往文章推薦------
機(jī)器學(xué)習(xí)
深度學(xué)習(xí)
人工神經(jīng)網(wǎng)絡(luò)
決策樹
隨機(jī)森林
強(qiáng)化學(xué)習(xí)
遷移學(xué)習(xí)
遺傳算法
樸素貝葉斯
支持向量機(jī)
蒙特卡羅方法
馬爾科夫模型
Hopfield神經(jīng)網(wǎng)絡(luò)
回歸模型
K鄰近算法
卷積神經(jīng)網(wǎng)絡(luò)
受限玻爾茲曼機(jī)
循環(huán)神經(jīng)網(wǎng)絡(luò)
長短時記憶神經(jīng)網(wǎng)絡(luò)
Adaboost算法
ID3算法
C4.5算法
CART算法
K-Means算法
（免責(zé)聲明：本網(wǎng)站內(nèi)容主要來自原創(chuàng)、合作伙伴供稿和第三方自媒體作者投稿，凡在本網(wǎng)站出現(xiàn)的信息，均僅供參考。本網(wǎng)站將盡力確保所提供信息的準(zhǔn)確性及可靠性，但不保證有關(guān)資料的準(zhǔn)確性及可靠性，讀者在使用前請進(jìn)一步核實，并對任何自主決定的行為負(fù)責(zé)。本網(wǎng)站對有關(guān)資料所引致的錯誤、不確或遺漏，概不負(fù)任何法律責(zé)任。
任何單位或個人認(rèn)為本網(wǎng)站中的網(wǎng)頁或鏈接內(nèi)容可能涉嫌侵犯其知識產(chǎn)權(quán)或存在不實內(nèi)容時，應(yīng)及時向本網(wǎng)站提出書面權(quán)利通知或不實情況說明，并提供身份證明、權(quán)屬證明及詳細(xì)侵權(quán)或不實情況證明。本網(wǎng)站在收到上述法律文件后，將會依法盡快聯(lián)系相關(guān)文章源頭核實，溝通刪除相關(guān)內(nèi)容或斷開相關(guān)鏈接。 ）
