大家恐怕都聽(tīng)說(shuō)過(guò)著名的啤酒與尿布, 這是典型的購(gòu)物籃問(wèn)題, 在數(shù)據(jù)挖掘界叫做頻繁項(xiàng)集(Frequent Itemsets).
note: 數(shù)據(jù)類型寫(xiě)法按照Python的格式.

一. 目標(biāo)與定義

1. 問(wèn)題背景

超市中購(gòu)物清單中總是有一些項(xiàng)目是被消費(fèi)者一同購(gòu)買(mǎi)的. 如果我們能夠發(fā)現(xiàn)這些關(guān)聯(lián)規(guī)則(association rules), 并合理地加以利用, 我們就能取得一定成果. 比如我們發(fā)現(xiàn)熱狗和芥末存在這種關(guān)系, 我們對(duì)熱狗降價(jià)促銷, 而對(duì)芥末適當(dāng)提價(jià), 結(jié)果能顯著提高超市的銷售額.

2. 目標(biāo)

找到頻繁地共同出現(xiàn)在消費(fèi)者結(jié)賬小票中項(xiàng)目(比如啤酒和尿布), 來(lái)一同促銷, 相互拉動(dòng), 提高銷售額.

3. 定義

支持度support: 其實(shí)就是概率論中的頻次frequency

支持度閾值support threshhold: 記為s, 指分辨頻繁項(xiàng)集的臨界值.

頻繁項(xiàng)集: 如果I是一個(gè)項(xiàng)集(Itemset), 且I的出現(xiàn)頻次(i.e.支持度)大于等于s, 那么我們說(shuō)I是頻繁項(xiàng)集.

一元項(xiàng), 二元項(xiàng), 三元項(xiàng): 包含有一種商品, 兩種, 三種商品的項(xiàng)集.

4. 關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則: 形式為I->j, 含義是如果I種所有項(xiàng)都出現(xiàn)在某個(gè)購(gòu)物籃的話, 那么j很有可能也出現(xiàn)在這個(gè)購(gòu)物籃中. 我們可以給出相應(yīng)的confidence值(可信度, 即概率論中的置信度).

其中, 這個(gè)關(guān)聯(lián)規(guī)則的可信度計(jì)算為Confidence = I∪{j} / I, 本身是非常符合直覺(jué)和常識(shí)的. 比如我們說(shuō)關(guān)聯(lián)規(guī)則{dog, cat} -> and 的可信度為0.6, 因?yàn)閧dog, cat}出現(xiàn)在了1, 2, 3, 6, 7五個(gè)購(gòu)物籃中, 而and出現(xiàn)在了1,2,7中, 因此我們可以算出Confidence = freq[{dog, cat, and}] / freq[{dog, cat}] = 3/5 = 0.6

注意到, 分子部分的頻次總是比分母低, 這是因?yàn)閧dog, cat} 出現(xiàn)的次數(shù)總是大于等于{dog, cat, and}的出現(xiàn)次數(shù).

二. 購(gòu)物籃與A-Priori算法

1. 購(gòu)物籃數(shù)據(jù)表示

我們將有一個(gè)文本文件輸入, 比如allBills.txt, 或者allBills.csv. 里面每行是一個(gè)購(gòu)物籃.
文件的頭兩行可能是這樣(df.show(2)):
{23, 456, 1001}
{3, 18, 92, 145}

我們假定這是一家大型連鎖超市, 比如沃爾瑪, 因此這個(gè)文本文件是非常大的, 比如20GB. 因此我們無(wú)法一次將該文件讀入內(nèi)存. 因此, 算法的主要時(shí)間開(kāi)銷都是磁盤(pán)IO.
我們同時(shí)還假定, 所有購(gòu)物籃的平均規(guī)模是較小的, 因此在內(nèi)存中產(chǎn)生所有大小項(xiàng)集的時(shí)間開(kāi)銷會(huì)比讀入購(gòu)物籃的時(shí)間少很多.
我們可以計(jì)算, 對(duì)于有n個(gè)項(xiàng)目組成的購(gòu)物籃而言, 大小為k的所有子集的生成時(shí)間約為(n, k) = n! / ((n-k)!k!) = O(n^k/ k!), 其中我們只關(guān)注較小的頻繁項(xiàng)集, 因此我們約定k=2或者k=3. 因此所有子集生成時(shí)間T = O(n^3).

Again, 我們認(rèn)為在內(nèi)存中產(chǎn)生所有大小項(xiàng)集的時(shí)間開(kāi)銷會(huì)比讀入購(gòu)物籃的時(shí)間少很多.

2. Itemset計(jì)數(shù)過(guò)程中的內(nèi)存使用

我們必須要把整個(gè)k,v字典放在內(nèi)存中, 否則來(lái)一個(gè)Itemset就去硬盤(pán)讀取一次字典將十分十分地慢.
此處, 字典是k=(18, 145), v=15這種形式. 此處, 應(yīng)當(dāng)注意到, 如果有{bread, milk, orange}這樣的String類型輸入, 應(yīng)當(dāng)預(yù)先用一個(gè)字典映射成對(duì)應(yīng)的整數(shù)值編碼, 比如1920, 4453, 9101這樣.

那么, 我們最多能用字典存儲(chǔ)多少種商品?

先看下我們存儲(chǔ)多少個(gè)count值.
我們假定項(xiàng)的總數(shù)目是n, 即超市有n種商品, 每個(gè)商品都有一個(gè)數(shù)字編號(hào), 那么我們需要(n, 2) = n^2/2 的大小來(lái)存儲(chǔ)所有的二元組合的count, 假設(shè)int是占4個(gè)byte, 那么需要(2·n^2)Byte內(nèi)存. 已知2GB內(nèi)存 = 2^31 Byte, 即2^31/2 = 2^30 >= n^2 --> n <= 2^15. 也就是說(shuō)n<33 000, 因此我們說(shuō)商品種類的最多是33k種.

但是, 這種計(jì)算方法存在一個(gè)問(wèn)題, 并不是有10種商品, 那么這10種商品的任意二元組合都會(huì)出現(xiàn)的. 對(duì)于那些沒(méi)出現(xiàn)的組合, 我們?cè)谧值渲型耆梢圆淮鎯?chǔ), 從而節(jié)省空間.

同時(shí), 別忘了我們同樣也得存儲(chǔ)key = (i, j), 這是至少額外的兩個(gè)整數(shù).

那么我們到底具體怎么存儲(chǔ)這些計(jì)數(shù)值?
可以采用三元組的方式來(lái)構(gòu)造字典. 我們采用[i, j, count]形式來(lái)存儲(chǔ), 其中i代表商品種類1, j代表商品種類2, 前兩個(gè)值代表key, 后面的value就是count, 是這個(gè)二元組合下的計(jì)數(shù).

現(xiàn)在, 讓我們注意到我們(1)假定購(gòu)物籃平均大小較小, 并(2)利用三元組(2個(gè)key的)字典和(3)不存儲(chǔ)沒(méi)出現(xiàn)組合優(yōu)勢(shì). 假設(shè)有100k = 10^5種商品, 有10million=10^7個(gè)購(gòu)物籃, 每個(gè)購(gòu)物籃有10個(gè)項(xiàng), 那么這種字典空間開(kāi)銷是(10, 2) · 10^7 = 45 x 10^7 x 3= 4.5x10^8x3 = 1.35x10^9 個(gè)整數(shù). 這算出來(lái)約為4x10^8 Byte = 400MB, 處于正常計(jì)算機(jī)內(nèi)存范圍內(nèi).

3. 項(xiàng)集的單調(diào)性

如果項(xiàng)集I是頻繁的, 那么它的所有子集也都是頻繁的. 這個(gè)道理很符合常識(shí), 因?yàn)閧dog, cat} 出現(xiàn)的次數(shù)總是大于等于{dog, cat, and}的出現(xiàn)次數(shù).

這個(gè)規(guī)律的推論, 就是嚴(yán)格地, 我們頻繁一元組的個(gè)數(shù)> 頻繁二元組的個(gè)數(shù) > 頻繁三元組的個(gè)數(shù).

4. A-Priori算法

我們通過(guò)Itemset計(jì)數(shù)中內(nèi)存使用的部門(mén), 已經(jīng)明確了我們總是有足夠的內(nèi)存用于所有存在的二元項(xiàng)集(比如{cat, dog})的計(jì)數(shù). 這里, 我們的字典不存放不存在于購(gòu)物籃中的任何二元項(xiàng)集合, 而且頻繁二元組的數(shù)目將會(huì)大于三元頻繁三元組> ...

我們可以通過(guò)單邊掃描購(gòu)物籃文件, 對(duì)于每個(gè)購(gòu)物籃, 我們使用一個(gè)雙重循環(huán)就可以生成所有的項(xiàng)對(duì)(即二元組). 每當(dāng)我們生成一個(gè)項(xiàng)對(duì), 就給其對(duì)應(yīng)的字典中的value +1(也稱為計(jì)數(shù)器). 最后, 我們會(huì)檢查所有項(xiàng)對(duì)的計(jì)數(shù)結(jié)果,并且找出那些>=閾值s的項(xiàng)對(duì), 他們就是頻繁項(xiàng)對(duì).

1) A-Priori算法的第一遍掃描

在第一遍掃描中, 我們將建立兩個(gè)表. 第一張表將項(xiàng)的名稱轉(zhuǎn)換為1到n之間的整數(shù), 從而把String類型這樣的key轉(zhuǎn)為空間大小更小的int類型. 第二張表將記錄從1~n每個(gè)項(xiàng)在所有購(gòu)物籃中出現(xiàn)的次數(shù). 形式上類似
table 0(name table): {'dolphin': 7019, 'cat': 7020} //dict形式, 其實(shí)也可以做成list形式 [['dolphin', 7019], ['cat', 7020]]
table 1(single-item counter table): {7019: 15, 7020: 18} //dict形式, 其實(shí)也可以做成數(shù)組形式A[7019] = 2, A[7020] = 18

2) 第一遍掃描完的處理

第一遍掃描完后, 我們會(huì)按照自己設(shè)定的閾值s, 對(duì)整個(gè)table 1再進(jìn)行一次mapping, 因?yàn)槲覀冎魂P(guān)注最后counter值大于等于閾值的項(xiàng)目, 而且不關(guān)心其counter值具體多少. 因此, mapping策略是:

對(duì)凡是counter<s的, 一律把counter設(shè)成0; 對(duì)于counter>=s的, 按照次序, 把其設(shè)置成1~m的值(總共有m個(gè)滿足要求的項(xiàng))

3) 第二遍掃描

第二遍掃描所做的事有三:
(1) 對(duì)每個(gè)購(gòu)物籃, 在table 1中檢查其所有的商品項(xiàng)目, 把所有為頻繁項(xiàng)的留下來(lái)建立一個(gè)list.
(2) 通過(guò)一個(gè)雙重循環(huán)生成該list中的所有項(xiàng)對(duì).
(3) 再走一次循環(huán), 在新的數(shù)據(jù)結(jié)構(gòu)table 2(dict或者list)中相應(yīng)的位置+1. 此時(shí)的效果是dicta = {48: {13: 5}, 49: {71, 16}} 或者 lista [ [48, 13, 5],[49, 71, 16], ... ]

注意此時(shí)內(nèi)存塊上存儲(chǔ)的結(jié)構(gòu): table1(name table), table2(single-item counter table), table3(double-item counter table)

5. 推廣: 任意大小頻繁項(xiàng)集上的A-Priori算法

我們對(duì)上面這個(gè)算法進(jìn)行推廣.
從任意集合大小k到下一個(gè)大小k+1的轉(zhuǎn)移模式可以這么說(shuō):
(1) 對(duì)每個(gè)購(gòu)物籃, 在table 1中檢查其所有的商品項(xiàng)目, 把所有為頻繁項(xiàng)的留下來(lái)建立一個(gè)list.
(2) 我們通過(guò)一個(gè)k+1重循環(huán)來(lái)生成該list中的所有(k+1)元組
(3) 對(duì)每個(gè)k+1元組, 我們生成其的(k+1 choose k)個(gè)k元組, 并檢查這些k元組是否都在之前的table k中. (注意到k=1的時(shí)候, 這步與(1)是重復(fù)的, 可以省略)
(4)再走一次循環(huán), 在新的數(shù)據(jù)結(jié)構(gòu)table k+1(dict或者list)中相應(yīng)的位置+1. 此時(shí)的效果是k=2, k+1=3, 生成dicta = {48: {13: {19: 4}}, 49: {71: {51: 10}}, ... } 或者 生成lista [ [48, 13, 19, 4],[49, 71, 51, 10], ... ]

注意, 在進(jìn)入下一次掃描前, 我們還需要額外把counter中值小于s的元組的計(jì)數(shù)值都記為0.

模式總體是:　C1 過(guò)濾后 L1 計(jì)數(shù)后 C2 置零后 C2' 過(guò)濾后 L2 計(jì)數(shù)后 C3 置零后 C3' ......

END.