機(jī)器學(xué)習(xí)講義spark-mllib第三節(jié)ver1

1、法律聲明本課件包括：演示文稿，示例，代碼，題庫(kù)，視頻和聲音等，小象學(xué)院擁有完全知識(shí)產(chǎn)權(quán)的權(quán)利；只限于善意學(xué)習(xí)者在本課程使用，不得在課程范圍外向任何第三方散播。任何其他人或機(jī)構(gòu)不得盜版、復(fù)制、仿造其中的創(chuàng)意，我們將保留一切通過(guò)法律手段追究違反者的權(quán)利。課程詳情請(qǐng)咨詢(xún)微信公眾號(hào)：小象新浪微博：ChinaHadoop基于SPARK的機(jī)器學(xué)習(xí)FP-GROWTH美團(tuán)網(wǎng) 顧立宏序列模式挖掘簡(jiǎn)介序列模式的概念最早是由Agrawal和Srikant 提出的。動(dòng)機(jī)：大型連鎖超市的交易數(shù)據(jù)有一系列的用戶(hù)事務(wù)數(shù)據(jù)庫(kù)，每一條記錄包括用戶(hù)的ID，事務(wù)發(fā)生的時(shí)間和事務(wù)涉及的項(xiàng)目。如果能在其中挖掘涉及事務(wù)間關(guān)聯(lián)關(guān)系的模式，

2、即用戶(hù)幾次購(gòu)買(mǎi)行為間的聯(lián)系，可以采取更有針對(duì)性的營(yíng)銷(xiāo)措施。事務(wù)數(shù)據(jù)庫(kù)實(shí)例例：一個(gè)事務(wù)數(shù)據(jù)庫(kù)，一個(gè)事務(wù)代表一筆交易，一個(gè)單項(xiàng)代表交易的商品，單項(xiàng)屬性中的數(shù)字記錄的是商品ID序列數(shù)據(jù)庫(kù)一般為了方便處理，需要把數(shù)據(jù)庫(kù)轉(zhuǎn)化為序列數(shù)據(jù)庫(kù)。方法是把用戶(hù)ID相同的記錄合并，有時(shí)每個(gè)事務(wù)的發(fā)生時(shí)間可以忽略，僅保持事務(wù)間的偏序關(guān)系問(wèn)題定義項(xiàng)集(Itemset)是所有在序列數(shù)據(jù)庫(kù)出現(xiàn)過(guò)的單項(xiàng)組成的集合例：對(duì)一個(gè)用戶(hù)購(gòu)買(mǎi)記錄的序列數(shù)據(jù)庫(kù)來(lái)說(shuō)，項(xiàng)集包含用戶(hù)購(gòu)買(mǎi)的所有商品，一種商品就是一個(gè)單項(xiàng)。通常每個(gè)單項(xiàng)有一個(gè)唯一的ID，在數(shù)據(jù)庫(kù)中記錄的是單項(xiàng)的ID問(wèn)題定義元素(Element)可表示為(x1x2xm)， xk(1

3、= k = m)為不同的單項(xiàng)。元素內(nèi)的單項(xiàng)不考慮順序關(guān)系，一般默認(rèn)按照ID的字典序排列在用戶(hù)事務(wù)數(shù)據(jù)庫(kù)里，一個(gè)事務(wù)就是一個(gè)元素。問(wèn)題定義序列(Sequence)是不同元素(Element)的有序排列，序列s可以表示為s = ，sj(1 = j = l)為序列s的元素一個(gè)序列包含的所有單項(xiàng)的個(gè)數(shù)稱(chēng)為序列的長(zhǎng)度。長(zhǎng)度為l的序列記為l-序列問(wèn)題定義例：一條序列有3個(gè)元素，分別是（10 20），30，（40 60 70 ）；3個(gè)事務(wù)的發(fā)生時(shí)間是由前到后。這條序列是一個(gè)6-序列。問(wèn)題定義數(shù)據(jù)庫(kù)是由一個(gè)個(gè)交易組成，一個(gè)交易是一個(gè)item的set；支持度(共現(xiàn)頻次)是出現(xiàn)該patter的交易個(gè)數(shù)頻繁集合 F

4、P：其支持度超過(guò)門(mén)限 類(lèi)Apriori算法該類(lèi)算法基于Apriori理論，即序列模式的任一子序列也是序列模式。算法首先自底向上的根據(jù)較短的序列模式生成較長(zhǎng)的候選序列模式，然后計(jì)算候選序列模式的支持度。典型的代表有GSP算法, spade算法等。FP-tree：出發(fā)點(diǎn)只關(guān)心頻繁集合，所以需要一次遍歷進(jìn)行第一次篩選為了避免頻繁去遍歷數(shù)據(jù)庫(kù)，需要對(duì)頻繁數(shù)據(jù)進(jìn)行壓縮對(duì)于有交集的交易數(shù)據(jù)，是否可以充分前綴信息FP-tree1、數(shù)據(jù)預(yù)處理FP-tree1、成成樹(shù)NullF : 1C : 1a : 1m : 1p : 1FP-tree1、成成樹(shù)NullF : 2C : 2a : 2m : 1p : 1b :

5、 1m : 1FP-tree1、成成樹(shù)NullF : 3C : 2a : 2m : 1p : 1b : 1m : 1b : 1FP-tree1、成成樹(shù)NullF : 3C : 2a : 2m : 1p : 1b : 1m : 1b : 1c : 1b : 1p : 1FP-tree1、成成樹(shù)NullF : 4C : 3a : 3m : 2p : 2b : 1m : 1b : 1c : 1b : 1p : 1FP-treeheader table。每個(gè)鏈表包含相同item節(jié)點(diǎn)FP-tree 建樹(shù)方法1、遍歷一遍數(shù)據(jù)庫(kù)，篩選頻繁item并計(jì)算他們的支持度， 按序排列每個(gè)交接setFP-tree 建

6、樹(shù)方法2、創(chuàng)建根節(jié)點(diǎn)null的樹(shù)T； 遍歷每個(gè)交易數(shù)據(jù)，記為p|P,調(diào)用insert_tree（p|P, T）; 如果T的孩子N與p item一致：N的cnt+1， 否則創(chuàng)建node N，cnt=1, 父節(jié)點(diǎn)是T； 如果P非空，調(diào)用 insert_tree(P,N)FP-tree 建樹(shù)方法算法需要遍歷兩邊數(shù)據(jù)庫(kù)：1、篩選頻繁item2、構(gòu)建fp-tree插入交易數(shù)據(jù)的復(fù)雜度是O（|交易|）FP-tree 建樹(shù)方法Lemma 2.1： 給定交易數(shù)據(jù)庫(kù)DB和支持度s， FP-tree包含了頻繁模式挖掘的全部信息FP-tree 建樹(shù)方法Lemma 2.1： 給定交易數(shù)據(jù)庫(kù)DB和支持度s， FP-tr

7、ee包含了頻繁模式挖掘的全部信息Lemma 2.2: 樹(shù)的size bounded 頻繁item數(shù)量 樹(shù)的高度bounded 頻繁集合的最大長(zhǎng)度FP-tree 建樹(shù)方法需要注意第一點(diǎn)并不是說(shuō)樹(shù)的size等于頻繁Item數(shù)量：每個(gè)交易里的item最多貢獻(xiàn)樹(shù)里的一個(gè)node，最差的情況是交易set沒(méi)有交集，樹(shù)的size等于數(shù)據(jù)庫(kù)size，但這種情況幾乎不會(huì)出現(xiàn)，否則不存在頻繁集合挖掘FP-tree的局限FP-tree保證了Mining數(shù)據(jù)的壓縮性， 但是能保證挖掘過(guò)程的效率嗎？頻繁集的組合問(wèn)題如何解決？FP-tree in miningProperty 3.1： 所有包含item i的Patter

8、n都能通過(guò)i的headerTable 獲得FP-tree in miningNode P:條件模式基：Mining結(jié)果FP-tree in miningNode m:條件模式基：Mining結(jié)果條件FP-tree:FP-tree in miningFP-tree in miningNode b:條件模式基：Mining結(jié)果條件FP-tree:FP-tree in miningNode a:條件模式基：Mining結(jié)果序列數(shù)據(jù)庫(kù)FP-tree in miningLamma 3.1： a的條件模式基中 b的支持度等于a,b的支持度Corollary 3.1 a,b是頻繁模式，等價(jià)于b在條件模式基上是頻繁模式根據(jù)這條性質(zhì)，可以吧k-長(zhǎng)頻繁模式的挖掘轉(zhuǎn)換成k個(gè)1-長(zhǎng)頻繁模式的挖掘，從而不需要產(chǎn)生任何候選set的組合FP-tree in miningLemma 3.1： a的條件模式基中 b的支持度等于a,b的支持