人工智能之Apriori算法
人工智能機(jī)器學(xué)習(xí)有關(guān)算法內(nèi)容,請(qǐng)參見公眾號(hào)“科技優(yōu)化生活”之前相關(guān)文章。人工智能之機(jī)器學(xué)習(xí)主要有三大類:1)分類;2)回歸;3)聚類。今天我們重點(diǎn)探討一下Apriori算法。 ^_^
Apriori算法是經(jīng)典的挖掘頻繁項(xiàng)集和關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法,也是十大經(jīng)典機(jī)器學(xué)習(xí)算法之一。
Agrawal和Srikant兩位博士在1994年提出了Apriori算法,主要用于做快速的關(guān)聯(lián)規(guī)則分析。
A priori在拉丁語(yǔ)中指"來(lái)自以前"。當(dāng)定義問(wèn)題時(shí),通常會(huì)使用先驗(yàn)知識(shí)或者假設(shè),這被稱作"一個(gè)先驗(yàn)"(a priori)。Apriori算法正是基于這樣的事實(shí):算法使用頻繁項(xiàng)集性質(zhì)的先驗(yàn)性質(zhì),即頻繁項(xiàng)集的所有非空子集也一定是頻繁的。
Apriori算法概念:
Apriori算法使用一種稱為逐層搜索的迭代方法,其中k項(xiàng)集用于探索(k+1)項(xiàng)集。首先,通過(guò)掃描數(shù)據(jù)庫(kù),累計(jì)每個(gè)項(xiàng)的計(jì)數(shù),并收集滿足最小支持度的項(xiàng),找出頻繁1項(xiàng)集的集合。該集合記為L(zhǎng)1。然后,使用L1找出頻繁2項(xiàng)集的集合L2,使用L2找出L3,如此下去,直到不能再找到頻繁k項(xiàng)集。每找出一個(gè)Lk需要一次數(shù)據(jù)庫(kù)的完整掃描。Apriori算法使用頻繁項(xiàng)集的先驗(yàn)性質(zhì)來(lái)壓縮搜索空間。
注:數(shù)據(jù)庫(kù)中的數(shù)據(jù)可以是結(jié)構(gòu)化的,也可以是半結(jié)構(gòu)化的,甚至還可以是分布在網(wǎng)絡(luò)上的異構(gòu)型數(shù)據(jù)。
Apriori算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法。其核心是基于兩階段頻集思想的遞推算法。該關(guān)聯(lián)規(guī)則在分類上屬于單維、單層、布爾關(guān)聯(lián)規(guī)則。在這里,所有支持度大于最小支持度的項(xiàng)集稱為頻繁項(xiàng)集,簡(jiǎn)稱頻集。
Apriori算法中術(shù)語(yǔ):
1、項(xiàng)集和K-項(xiàng)集
令I(lǐng)={i1,i2,i3……id}是數(shù)據(jù)中所有項(xiàng)的集合,而T={t1,t2,t3….tN}是所有事務(wù)的集合,每個(gè)事務(wù)ti包含的項(xiàng)集都是I的子集。在關(guān)聯(lián)分析中,包含0個(gè)或多個(gè)項(xiàng)的集合稱為項(xiàng)集。如果一個(gè)項(xiàng)集包含K個(gè)項(xiàng),則稱它為K-項(xiàng)集?占侵覆话魏雾(xiàng)的項(xiàng)集。
2、支持度計(jì)數(shù)
項(xiàng)集的一個(gè)重要性質(zhì)是它的支持度計(jì)數(shù),即包含特定項(xiàng)集的事務(wù)個(gè)數(shù),數(shù)學(xué)上,項(xiàng)集X的支持度計(jì)數(shù)σ(X)可以表示為 :
σ(X)=|{ti|X?ti,ti∈T}|
其中,符號(hào)|*|表示集合中元素的個(gè)數(shù)。
3、關(guān)聯(lián)規(guī)則
關(guān)聯(lián)規(guī)則是形如X→Y的蘊(yùn)含表達(dá)式,其中X和Y是不相交的項(xiàng)集,即X∩Y=空。
關(guān)聯(lián)規(guī)則的強(qiáng)度可以用它的支持度(support)和置信度(confidence)來(lái)度量。
支持度確定規(guī)則可以用于給定數(shù)據(jù)集的頻繁程度,而置信度確定Y在包含X的事務(wù)中出現(xiàn)的頻繁程度。
支持度(s)和置信度(c)這兩種度量的形式定義如下:
s(X→Y)=σ(X∪Y)/N
c(X→Y)=σ(X∪Y)/σ(X)
其中, σ(X∪Y)是(X∪Y)的支持度計(jì)數(shù),N為事務(wù)總數(shù),σ(X)是X的支持度計(jì)數(shù)。
對(duì)于靠譜的關(guān)聯(lián)規(guī)則,其支持度與置信度均應(yīng)大于設(shè)定的閾值。那么,關(guān)聯(lián)分析問(wèn)題即等價(jià)于:對(duì)給定的支持度閾值min_sup、置信度閾值min_conf,找出所有的滿足下列條件的關(guān)聯(lián)規(guī)則:
支持度>=min_sup
置信度>=min_conf
把支持度大于閾值的項(xiàng)集稱為頻繁項(xiàng)集(frequent itemset)。因此,關(guān)聯(lián)規(guī)則分析可分為下列兩個(gè)步驟:
1)生成頻繁項(xiàng)集F=X∪Y;
2)在頻繁項(xiàng)集F中,找出所有置信度大于最小置信度的關(guān)聯(lián)規(guī)則X->Y
Apriori算法思想:
1)找出所有的頻集,這些項(xiàng)集出現(xiàn)的頻繁性至少和預(yù)定義的最小支持度一樣。
2)由頻集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則,這些規(guī)則必須滿足最小支持度和最小可信度。
3)使用第1)步找到的頻集產(chǎn)生期望的規(guī)則,產(chǎn)生只包含集合的項(xiàng)的所有規(guī)則,其中每一條規(guī)則的右部只有一項(xiàng),這里采用的是中規(guī)則的定義。
4)一旦這些規(guī)則被生成,那么只有那些大于用戶給定的最小可信度的規(guī)則才被留下來(lái)。為了生成所有頻集,使用了遞歸的方法。
Aprior算法程序如下:
Apriori算法優(yōu)點(diǎn):
1)使用先驗(yàn)性質(zhì),大大提高了頻繁項(xiàng)集逐層產(chǎn)生的效率;
2)簡(jiǎn)單易理解;
3)數(shù)據(jù)集要求低;
4)擴(kuò)展性較好,可以并行計(jì)算。
Apriori算法缺點(diǎn):
1) 可能產(chǎn)生大量的候選集;
2) 可能需要重復(fù)掃描整個(gè)數(shù)據(jù)庫(kù),非常耗時(shí)。
Apriori算法改進(jìn):
定理:如果規(guī)則X->Y?X 不滿足置信度閾值, 則對(duì)于X的子集X′->Y?X′也不滿足置信度閾值。
根據(jù)此定理,可對(duì)規(guī)則樹進(jìn)行剪枝,其具體改進(jìn)的算法如下:
Apriori算法應(yīng)用:
通過(guò)對(duì)數(shù)據(jù)的關(guān)聯(lián)性進(jìn)行了分析和挖掘,挖掘出的這些信息在決策制定過(guò)程中具有重要的參考價(jià)值。Apriori 算法被廣泛應(yīng)用于各種領(lǐng)域:
1)應(yīng)用于商業(yè)活動(dòng)領(lǐng)域,應(yīng)用于消費(fèi)市場(chǎng)價(jià)格分析中,它能夠很快的求出各種產(chǎn)品之間的價(jià)格關(guān)系和它們之間的影響。
2)應(yīng)用于網(wǎng)絡(luò)安全領(lǐng)域,通過(guò)模式的學(xué)習(xí)和訓(xùn)練可以發(fā)現(xiàn)網(wǎng)絡(luò)用戶的異常行為模式,能夠快速的鎖定攻擊者,提高了基于關(guān)聯(lián)規(guī)則的入侵檢測(cè)系統(tǒng)的檢測(cè)性。
3)應(yīng)用于高校管理中。隨著高校貧困生人數(shù)的不斷增加,學(xué)校管理部門資助工作難度也越加增大。針對(duì)這一現(xiàn)象,將關(guān)聯(lián)規(guī)則的Apriori算法應(yīng)用到貧困助學(xué)體系中,挖掘出的規(guī)則也可以有效地輔助學(xué)校管理部門有針對(duì)性的開展貧困助學(xué)工作。
4)應(yīng)用于移動(dòng)通信領(lǐng)域;谝苿(dòng)通信運(yùn)營(yíng)商正在建設(shè)的增值業(yè)務(wù)Web數(shù)據(jù)倉(cāng)庫(kù)平臺(tái),對(duì)來(lái)自移動(dòng)增值業(yè)務(wù)方面的調(diào)查數(shù)據(jù)進(jìn)行了相關(guān)的挖掘處理,從而獲得了關(guān)于用戶行為特征和需求的間接反映市場(chǎng)動(dòng)態(tài)的有用信息,這些信息在指導(dǎo)運(yùn)營(yíng)商的業(yè)務(wù)運(yùn)營(yíng)和輔助業(yè)務(wù)提供商的決策制定等方面具有十分重要的參考價(jià)值。
結(jié)語(yǔ):
Apriori算法是一種挖掘關(guān)聯(lián)規(guī)則的頻繁項(xiàng)集算法,其核心思想是通過(guò)候選集生成和情節(jié)的向下封閉檢測(cè)兩個(gè)階段來(lái)挖掘頻繁項(xiàng)集。主要用于做快速的關(guān)聯(lián)規(guī)則分析。Apriori算法在世界上廣為流傳,得到極大的關(guān)注。Apriori算法已經(jīng)被廣泛的應(yīng)用到商業(yè)、網(wǎng)絡(luò)安全、高校管理和移動(dòng)通信等領(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ò)
長(zhǎng)短時(shí)記憶神經(jīng)網(wǎng)絡(luò)
Adaboost算法
ID3算法
C4.5算法
CART算法
K-Means算法
發(fā)表評(píng)論
請(qǐng)輸入評(píng)論內(nèi)容...
請(qǐng)輸入評(píng)論/評(píng)論長(zhǎng)度6~500個(gè)字
最新活動(dòng)更多
-
即日-10.29立即報(bào)名>> 2024德州儀器嵌入式技術(shù)創(chuàng)新發(fā)展研討會(huì)
-
10月31日立即下載>> 【限時(shí)免費(fèi)下載】TE暖通空調(diào)系統(tǒng)高效可靠的組件解決方案
-
即日-11.13立即報(bào)名>>> 【在線會(huì)議】多物理場(chǎng)仿真助跑新能源汽車
-
11月14日立即報(bào)名>> 2024工程師系列—工業(yè)電子技術(shù)在線會(huì)議
-
12月19日立即報(bào)名>> 【線下會(huì)議】OFweek 2024(第九屆)物聯(lián)網(wǎng)產(chǎn)業(yè)大會(huì)
-
即日-12.26火熱報(bào)名中>> OFweek2024中國(guó)智造CIO在線峰會(huì)
推薦專題
- 1 Intel宣布40年來(lái)最重大轉(zhuǎn)型:年底前裁員15000人、拋掉2/3房產(chǎn)
- 2 因美封殺TikTok,字節(jié)股價(jià)骨折!估值僅Meta1/5
- 3 宏山激光重磅發(fā)布行業(yè)解決方案,助力智能制造產(chǎn)業(yè)新飛躍
- 4 國(guó)產(chǎn)AI芯片公司破產(chǎn)!白菜價(jià)拍賣
- 5 具身智能火了,但規(guī)模落地還需時(shí)間
- 6 國(guó)產(chǎn)英偉達(dá)們,抓緊沖刺A股
- 7 三次錯(cuò)失風(fēng)口!OpenAI前員工殺回AI編程賽道,老東家捧金相助
- 8 英特爾賦能智慧醫(yī)療,共創(chuàng)數(shù)字化未來(lái)
- 9 英偉達(dá)的麻煩在后頭?
- 10 將“網(wǎng)紅”變成“商品”,AI“爆改”實(shí)力拉滿
- 高級(jí)軟件工程師 廣東省/深圳市
- 自動(dòng)化高級(jí)工程師 廣東省/深圳市
- 光器件研發(fā)工程師 福建省/福州市
- 銷售總監(jiān)(光器件) 北京市/海淀區(qū)
- 激光器高級(jí)銷售經(jīng)理 上海市/虹口區(qū)
- 光器件物理工程師 北京市/海淀區(qū)
- 激光研發(fā)工程師 北京市/昌平區(qū)
- 技術(shù)專家 廣東省/江門市
- 封裝工程師 北京市/海淀區(qū)
- 結(jié)構(gòu)工程師 廣東省/深圳市