內容
概述
1. 關(guān)聯(lián)規則
2. Apriori 算法
3. FP-成長(cháng)算法
結束語(yǔ)
參考文獻列表
概述
分析數據量的成長(cháng)導致對無(wú)監督學(xué)習方法的興趣增長(cháng)。 在最近幾篇文章中，我們已經(jīng)看到了屬于無(wú)監督學(xué)習方法的聚類(lèi)和降維算法。 在本文中，我們繼續研究無(wú)監督學(xué)習方法。 這一次，我們將研究可用這些方法定位的另一類(lèi)問(wèn)題：關(guān)聯(lián)規則挖掘。 這種問(wèn)題類(lèi)型起源于超市購物營(yíng)銷(xiāo)，用于分析市場(chǎng)籃子，目的是找到最熱銷(xiāo)的產(chǎn)品集。 今日，解決這些問(wèn)題的算法廣泛應用于各個(gè)領(lǐng)域。 我們將查看如何在交易中運用這些算法。
1. 關(guān)聯(lián)規則
關(guān)聯(lián)規則分析問(wèn)題屬于數據挖掘應用問(wèn)題。 甚或，它是最基本的方法之一，因為它能夠識別大型數據庫中數據之間的有趣關(guān)系。
這類(lèi)問(wèn)題最初是在零售購物過(guò)程中形成和定義的。 市場(chǎng)營(yíng)銷(xiāo)人員面臨的問(wèn)題是，通過(guò)分析銷(xiāo)售網(wǎng)點(diǎn)系統在冊的交易數據的大型數據庫，可以獲取哪些商業(yè)利益。 以前只會(huì )分析總銷(xiāo)售量。 對客戶(hù)購物行為的分析開(kāi)辟了新的領(lǐng)域，因為它能夠分析客戶(hù)購買(mǎi)的特定產(chǎn)品集。
第一個(gè)算法是由 IBM 的一組開(kāi)發(fā)人員于 1993 年創(chuàng )建的。 當主要原則形成時(shí)，之后就會(huì )形成一整套算法的基礎。
首先，由算法檢測到的規則必須是經(jīng)常會(huì )遇到。 這意味著(zhù)它們不能是純隨機的，并且必須在分析的數據庫中至少重復了一定次數。 意即，它們必須能夠得到確認。 從統計學(xué)的角度來(lái)看，包含此類(lèi)規則的業(yè)務(wù)樣本應具有代表性。 為了滿(mǎn)足這一要求，所有用來(lái)判定關(guān)聯(lián)規則的算法都有一個(gè)最少支持率參數 MinSup，該參數以 “1” 為底表示規則出現頻率與分析樣本中業(yè)務(wù)總數的比率。
根據組合的規則，如果我們有一組 3 項：a，B 和 C，在不考慮元素位置的情況下，我們可以得到 7 個(gè)不同的集合，這些項包含從 1 到 3。 隨著(zhù)項數的增加，可能的組合數量也增加。 考慮到給定數據庫的容量，直接重新計算每個(gè)集合的頻率變?yōu)橐豁椣喈斚馁Y源的任務(wù)。 經(jīng)常性地重新計算是不可能的。 因此，作者使用了抗單調屬性。
如果在數據庫中，A 項只是所有可能項其中一組，其出現頻率將等于 A 本身的頻率。 如果遇到的集合次數越多，則它們的頻率只能越少，因為它們在所分析樣本中出現的總數將等于 A 的出現次數。 因此，如果任何項的出現頻率小于 MinSup，則包含該項的集合的所有可能變體的頻率就會(huì )小于 MinSup。 如此，我們計算每項的出現頻率就足夠了，從而剔除對我們沒(méi)有實(shí)際價(jià)值的隨機集合的絕大部分。
正如您所看到的，關(guān)聯(lián)規則搜索算法與之前研究過(guò)的所有算法區別很大。 之前，我們嘗試充分利用所有可用數據。 與其鮮明對比，關(guān)聯(lián)規則挖掘的算法可以立即消除隨機（噪聲）項。
所有關(guān)聯(lián)規則算法中用到的第二個(gè)參數是最小置信度 MinConf。 它也用以 1 為底的分數表示。 為了解釋這個(gè)參數，我們應該知道每個(gè)規則都由兩部分組成：前因和后果。 前因和后果都可由一項或整套項組成。 在一般情況下，規則聽(tīng)起來(lái)如下：如果前因為真，那么通常會(huì )有一個(gè)后果。
注意，在前因發(fā)生之后，后果發(fā)生的概率并非 100%。 而后果發(fā)生的最小概率由 MinConf 參數設定。 滿(mǎn)足此參數時(shí)，規則被視為有效，并保存到規則數組中。 它定義為規則執行頻率與前因頻率的比率。
2. Apriori 算法
尋找關(guān)聯(lián)規則最著(zhù)名的算法之一可能就是 Apriori 算法，它由 Rakesh Agrawal 和 Ramakrishnan Srikant 于 1994 年提出。 該算法基于搜索數據庫中最頻繁形態(tài)的迭代過(guò)程。 之后，從所選形態(tài)中提取規則。
為了更好地理解它，我們看一下算法在 10 筆業(yè)務(wù)和 5 項的小示例上的操作。
業(yè)務(wù) ID
內容
T1
BCDE
T2
BCD
T3
B
T4
BCD
T5
D
T6
ACD
T7
BCDE
T8
BCE
T9
CDE
T10
AD
我們在問(wèn)題中引入最小支持率 0.3 和最小置信度 0.7 的常數（分別為 30% 和 70%）。
請注意，所有關(guān)聯(lián)規則算法都使用二元數組。 因此，從一開(kāi)始，我們就把上述數據表示為二元表格。
業(yè)務(wù) ID
A
B
C
D
E
T1
0
1
1
1
1
T2
0
1
1
1
0
T3
0
1
0
0
0
T4
0
1
1
1
0
T5
0
0
0
1
0
T6
1
0
1
1
0
T7
0
1
1
1
1
T8
0
1
1
1
0
T9
0
0
1
1
1
T10
1
0
0
1
0
根據該表格，很容易計算出項 A 僅出現兩次，其支持率等于 0.2 或 20%。 類(lèi)似地，我們計算對其它項的支持率：B — 0.6, C — 0.7, D — 0.8, E — 0.4。 如您所見(jiàn)，只有 A 不滿(mǎn)足最低支持率要求。 如此，我們根據抗單調性，將其排除在進(jìn)一步處理之外。
從剩余的元素中，我們?yōu)轭l繁出現的形態(tài)創(chuàng )建候選者。 我們在上一步中已判定了頻繁發(fā)生項。 根據該算法，我們判定候選者為兩個(gè)項的集合：BC、BD、BE、CD、CE、DE。
現在，我們需要處理整個(gè)數據庫，并判定每個(gè)選定候選者的支持率。
業(yè)務(wù) ID
BC
BD
BE
CD
CE
DE
T1
1
1
1
1
1
1
T2
1
1
0
1
0
0
T3
0
0
0
0
0
0
T4
1
1
0
1
0
0
T5
0
0
0
0
0
0
T6
0
0
0
1
0
0
T7
1
1
1
1
1
1
T8
1
0
1
0
1
0
T9
0
0
0
1
1
1
T10
0
0
0
0
0
0
這一次，我們所有候選者的支持率都滿(mǎn)足最低支持率條件： BC — 0.5, BD — 0.4, BE — 0.3, CD — 0.6, CE — 0.4, DE — 0.3。 但這并非始終發(fā)生。 在解決實(shí)際問(wèn)題時(shí)，一些候選者更有可能被淘汰。
接下來(lái)，我們繼續迭代過(guò)程。 這次，我們創(chuàng )建三個(gè)項的候選者集合。 為此，我們從上一次迭代中提取選出的頻繁形態(tài)，并組合配對，其中僅有一個(gè)元素不同。 我們可以判定 4 個(gè)候選者：BCD、BCE、BDE 和 CDE。
根據 Apriori 算法，我們必須再次遍歷整個(gè)數據庫，從而判定所有新候選者的支持率。
業(yè)務(wù) ID
BCD
BCE
BDE
CDE
T1
1
1
1
1
T2
1
0
0
0
T3
0
0
0
0
T4
1
0
0
0
T5
0
0
0
0
T6
0
0
0
0
T7
1
1
1
1
T8
0
1
0
0
T9
0
0
0
1
T10
0
0
0
0
結果就是，我們得到以下我們的候選者的支持率： BCD — 0.4, BCE — 0.3, BDE — 0.2, CDE — 0.3。 在本次迭代中，對 BDE 項的支持率不滿(mǎn)足最低支持率要求，因此我們將其剔除在外。 其它候選者都被認定為頻繁形態(tài)。
在下一次迭代中，我們編譯 4 項的候選者集合。 基于來(lái)自上一次迭代中選擇的形態(tài)，我們只能生成一個(gè)候選者 BCDE。 但在計算這個(gè)候選者支持率之前，我們先要關(guān)注其組成部分 BDE。 該候選項在上一次迭代后被刪除，因為它的支持率僅為 0.2，而最低支持率要求為 0.3。 因此，根據抗單調性規則，BCDE 候選者的支持率不能大于 0.2。 但這低于最低支持率。
鑒于我們沒(méi)有任何其它候選者，我們停止搜索頻繁形態(tài)的過(guò)程，并繼續下一個(gè)子過(guò)程 — 基于選定的頻繁形態(tài)判定規則。 為此，我們把所選擇的形態(tài)切分為前因和后果。 之后，我們可以判定每個(gè)規則的置信等級，并將其與所需的最小置信等級進(jìn)行比較。
我們將為集合中的每項依次構建規則。 由于在開(kāi)始第一階段，我們通過(guò) A 剔除了所有形態(tài)（它的支持率低于 MinSup），因此我們開(kāi)始依據 B 判定規則。
從所選的形態(tài)中，我們判定包含分析項的所有形態(tài)。 從形態(tài)中提取項 B 作為后果備用，而其余部分將作為前因項。 我們還將判定每個(gè)所創(chuàng )建規則的置信度。
規則置信度表示當形成前因時(shí)，后果出現的概率。 為了判定它，我們不需要重新迭代整個(gè)數據庫。 我們只需要把全部形態(tài)的支持率切分為前因的支持率，其數值在頻繁形態(tài)選擇階段已計算得出。
形態(tài)
前因
支持率
規則
BC (0.5)
C (0.7)
0.71
C -> B
BD (0.4)
D (0.8)
0.50
D -> B
BE (0.3)
E (0.4)
0.75
E -> B
BCD (0.4)
CD (0.6)
0.67
CD -> B
BCE (0.3)
CE (0.4)
0.75
CE -> B
規則 D -> B 和 CD -> B 不滿(mǎn)足 0.7 的最低支持率要求，因此我們將其排除在外。
按照類(lèi)似的方式判定其它規則。
形態(tài)
前因
支持率
規則
BC (0.5)
B (0.6)
0.83
B -> C
CD (0.6)
D (0.8)
0.75
D -> C
CE (0.4)
E (0.4)
1.00
E -> C
BCD (0.4)
BD (0.4)
1.00
BD -> C
BCE (0.3)
BE (0.3)
1.00
BE -> C
CDE (0.3)
DE (0.3)
1.00
DE -> C
CD (0.6)
C (0.7)
0.86
C -> D
DE (0.3)
E (0.4)
0.75
E -> D
BCD (0.4)
BC (0.5)
0.80
BC -> D
CDE (0.3)
CE (0.4)
0.75
CE -> D
我們已經(jīng)見(jiàn)識過(guò)關(guān)聯(lián)規則挖掘最著(zhù)名的算法之一 Apriori。 然而，盡管它即簡(jiǎn)單且受歡迎，但在實(shí)踐中卻很少使用。 這是因為所研究方法的瓶頸在于，為評估候選者針對頻繁形態(tài)的支持率，所需的遍歷數據庫的迭代次數。 隨著(zhù)需分析的數據庫數量的增長(cháng)，這一問(wèn)題變得越來(lái)越嚴重。 該問(wèn)題在下一算法中得到有效解決。 它只需要對任何容量和任何數量的分析項的數據庫進(jìn)行迭代。
3. FP-成長(cháng)算法
我們用一個(gè)尋找關(guān)聯(lián)規則的最快算法的示例來(lái)研究上述問(wèn)題的解決方案：FP-成長(cháng)（頻繁形態(tài)增長(cháng)）。 由于算法構造的特殊性，在其執行過(guò)程中，訓練樣本所有元素的徹底迭代僅執行 2 遍。 除了這兩遍次之外，該算法不調用訓練樣本。
與之前研究的關(guān)聯(lián)規則挖掘算法類(lèi)似，FP-成長(cháng)可以有條件地化分為兩個(gè)子問(wèn)題：
尋找頻繁出現的形態(tài)。 在本示例中，此階段稱(chēng)為 FP 樹(shù)的構建。
判定規則。
該算法從消除隨機項開(kāi)始。 為了做到這一點(diǎn)，與前面的算法一樣，我們對整個(gè)訓練集合執行第一遍，并計算每項的支持率。 之后，刪除頻率小于 MinSup 的所有項。
其余項按其支持率的降序排列。 上述示例產(chǎn)生以下序列：
D (0.8) -> C (0.7) -> B (0.6) -> E(0.4)
接下來(lái)，我們將拔高 FP 樹(shù)。 為此，針對訓練樣本執行第二次驗算。 在每筆業(yè)務(wù)中，我們只獲取按支持率降序排列的頻繁項，并在樹(shù)中構建路徑。 因此，支持率最高的節點(diǎn)將位于樹(shù)根處，而支持率最低的節點(diǎn)將為葉片。 我們還為每個(gè)節點(diǎn)創(chuàng )建一個(gè)計數器。 在第一遍迭代中，我們將計數器值設置為 1（或 1/N，其中 N 是訓練樣本的尺寸）。
然后我們從數據庫中獲取下一筆業(yè)務(wù)。 以同樣的方式為其構建路徑。 加到我們的樹(shù)中。 為此，從樹(shù)根開(kāi)始，我們檢查已有分支的路徑。 當從根重復路徑時(shí)，我們只需增加現有節點(diǎn)的計數器。 對于新部分，創(chuàng )建一個(gè)分支。
重復迭代循環(huán)，直到整個(gè)訓練集的完全迭代。 對于上述示例，我們將得到以下 FP-樹(shù)。
依據高概率，我們可以找到與根本身不同的路徑。 有兩種可能的選擇：
構造一片森林
創(chuàng )建一個(gè)特定根節點(diǎn)，來(lái)統一整個(gè)選擇。
顯然，在 FP-樹(shù)成長(cháng)過(guò)程開(kāi)始時(shí)，大多數部分下將創(chuàng )建新節點(diǎn)。 但在沿著(zhù)訓練樣本移動(dòng)的過(guò)程中，我們在不創(chuàng )建新分支的情況下增加現有節點(diǎn)的計數器。 該算法的具體特點(diǎn)是，在構建樹(shù)的過(guò)程中，我們可以將訓練樣本壓縮到這樣的尺寸，即我們可以在計算機的 RAM 中輕松操作，而無(wú)需訪(fǎng)問(wèn)數據庫。
與規則定義相關(guān)的深入工作僅依據 FP-樹(shù)執行，無(wú)需用到原始數據庫。
所有項的規則均已考慮到，并按支持率升序排列。
在第一階段，我們已經(jīng)消除了頻率低于指定頻率的所有項，現在我們的樹(shù)只包含頻繁出現的項。 此外，在構建樹(shù)時(shí)，我們針對所有項按降序排序。 這意味著(zhù)支持率最低的項是樹(shù)葉。
因此，為了判定從最低支持率項開(kāi)始的規則，我們從葉行進(jìn)到根。 在此，我們可以追溯尚未明確的因果關(guān)系。 該算法假設擁有較低支持率的項作為擁有更多支持率的特征組合的結果。
但是，我們返回到我們的規則定義算法。 獲取最低支持項，并判定 FP-樹(shù)中指向該項的所有路徑。 在選擇路徑時(shí)，我們首先注意所需項的出現頻率，它來(lái)自路徑項形態(tài)成型時(shí)。 路徑選擇準則是每項支持率與前一節點(diǎn)支持率的比值。 比率不得小于規則的最小置信度。
在上面的示例中，最低支持率由 E 表示。 在 FP-樹(shù)中有三條路徑通往它：DCBE（0.2），DCE（0.1），CBE（0.1）。 所有路徑均不滿(mǎn)足最低支持率要求。 其中兩個(gè)不符合最低置信度要求。 因此，我們無(wú)法依據 E 創(chuàng )建規則。 注意，通過(guò) Apriori 算法獲得的結果證實(shí)了這一點(diǎn)。
從樹(shù)中刪除 E 葉片，并得到以下 FP-樹(shù)視圖。
下一個(gè)要分析的元素是 B。 它在這些葉片中的支持率最低。 它有三條路徑：DCB (0.4), B (0.1), CB (0.1)。
在選定的支持路徑中，已分析項之前的每一項，都賦值為給定路徑中已分析項的支持率。
基于選擇的路徑，我們形成一個(gè)參與項的列表，并確定每項的支持率。 請注意，支持率被判定為所選路徑中該項出現次數與原始訓練數據集中記錄總數的比率。 因此，每項的新支持率不能超過(guò)初始項的支持率，或已分析項的支持率（正在判定規則的那個(gè)）。
同樣，我們也刪除了低于最小支持率的項。 按支持率降序排列其余項。
在本示例中，我們有 C（0.5），D（0.4）。
請注意，由于我們僅用所選路徑計算每項的支持率，因此結果可能與初始路徑有很大不同。 作為這個(gè)因素的結果，一些項可以被刪除，它們在新的層次結構中的順序也會(huì )改變。
進(jìn)而，根據新的層次結構，我們采用選定的路徑構建一個(gè)新的私有樹(shù)。 該樹(shù)構造算法與 FP-樹(shù)的構造沒(méi)有區別。
構造的私有樹(shù)的分支將是規則的前因，其后果將是我們所分析的項。
在構造私有樹(shù)之后，我們從原始 FP-樹(shù)中移除所分析項的節點(diǎn)。 訣竅在于，我們所分析項的支持率最小。 這意味著(zhù)包含這些項的所有節點(diǎn)都是 FP-樹(shù)的葉片。 因此，移除它們不會(huì )影響其它項的路徑（我們提到的因果關(guān)系稍微高一點(diǎn)）。
此外，通過(guò)逐漸刪除已分析特征，我們逐漸縮減了FP 樹(shù)。 因此，我們減少了在其它項分析中進(jìn)一步搜索的數據量。 這會(huì )影響算法的整體性能。
類(lèi)似地，我們?yōu)?FP 樹(shù) 的原始層次結構中的每一項構建規則。
注意，我們只能為 FP 樹(shù)中至少有一個(gè)根節點(diǎn)的項構建規則。 我們無(wú)法為根節點(diǎn)項創(chuàng )建規則，因為我們沒(méi)有任何可參考的前因項。 當然，除了潛在顧客去超市參觀(guān)之外。 如果顧客來(lái)到超市，他們會(huì )買(mǎi)些東西。 這很可能是最暢銷(xiāo)的商品之一。 但這超出了所研究算法的范疇。
結束語(yǔ)
在本文中，我們研究了非監督學(xué)習方法解決的另一類(lèi)問(wèn)題：關(guān)聯(lián)規則挖掘。 我們討論了兩種關(guān)聯(lián)規則挖掘算法：Apriori 和 FP-成長(cháng)。 但還有許多其它算法。 不幸的是，我無(wú)法在一篇文章中涵蓋整個(gè)主題。 甚至，它只提供了理論方面的內容。 在下一篇文章中，我們將研究利用 MQL5 實(shí)際構造關(guān)聯(lián)規則挖掘算法。 我們還將評估其應用于實(shí)際交易任務(wù)的績(jì)效效率。
