FP—Growth算法在電子商務(wù)中的應(yīng)用

【摘要】針對(duì)電子商務(wù)推薦銷(xiāo)售的需求和FP-Growth算法不產(chǎn)生候選集的特性，提出利用FP-Growth算法，運(yùn)用VC++程序開(kāi)發(fā)工具，對(duì)某一電商賣(mài)家的數(shù)據(jù)進(jìn)行頻繁項(xiàng)集挖掘，針對(duì)挖掘得到的頻繁K項(xiàng)集，指導(dǎo)賣(mài)家如何組合商品銷(xiāo)售。試驗(yàn)結(jié)果表明利用FP-Growth算法在電商組合銷(xiāo)售中是有效的。

【關(guān)鍵詞】候選集；頻繁項(xiàng)集；電子商務(wù)；FP-Growth FP-Tree

引言

在過(guò)去的數(shù)十年中，經(jīng)濟(jì)發(fā)展迅猛，信息化水平不斷提高，網(wǎng)絡(luò)購(gòu)物成為人們購(gòu)物的新趨勢(shì)，各大電子商務(wù)平臺(tái)方便快捷的收集了海量數(shù)據(jù)，利用好這些數(shù)據(jù)就可以為網(wǎng)絡(luò)銷(xiāo)售提供豐富的、有用的商業(yè)信息。頻繁項(xiàng)集挖掘就是利用這些數(shù)據(jù)的一個(gè)典型算法，很早之前就開(kāi)始應(yīng)用到傳統(tǒng)零售行業(yè)的購(gòu)物籃分析[1，2]，把這種數(shù)據(jù)挖掘算法應(yīng)用在電子商務(wù)中就是購(gòu)物車(chē)分析[3]。其核心思想是通過(guò)頻繁項(xiàng)集的分析處理，發(fā)現(xiàn)買(mǎi)家“購(gòu)物車(chē)”中所有商品之間的關(guān)聯(lián)，獲悉顧客的購(gòu)買(mǎi)習(xí)慣。這種關(guān)聯(lián)的發(fā)現(xiàn)可以幫助電商賣(mài)家了解哪些商品會(huì)被顧客同時(shí)購(gòu)買(mǎi)，幫助他們?cè)O(shè)計(jì)更好的組合銷(xiāo)售營(yíng)銷(xiāo)策略。例如，如果顧客在當(dāng)當(dāng)網(wǎng)購(gòu)買(mǎi)點(diǎn)讀筆的同時(shí)，他們有多大可能也同時(shí)購(gòu)買(mǎi)點(diǎn)讀材料（以及何種點(diǎn)讀材料），這種信息可以幫助電商合理組合商品優(yōu)惠，吸引消費(fèi)者購(gòu)買(mǎi)更多產(chǎn)品，從而增加銷(xiāo)售量。購(gòu)物車(chē)分析的目標(biāo)是在顧客的購(gòu)買(mǎi)交易中分析出同時(shí)購(gòu)買(mǎi)一類(lèi)產(chǎn)品或一組產(chǎn)品的可能性（相互關(guān)聯(lián)），從購(gòu)物車(chē)分析中獲得的知識(shí)是很有價(jià)值的。關(guān)聯(lián)規(guī)則挖掘在數(shù)據(jù)挖掘是一個(gè)活躍的研究?jī)?nèi)容。其中比較常用的算法有早期的Apriori[5]的算法，F(xiàn)P-Growth算法，以及這兩種算法的各種改進(jìn)版本。本文旨在為中小電商賣(mài)家（如淘寶、天貓上的店鋪）提供一些有效的數(shù)據(jù)分析，因此在算法上選擇比較經(jīng)典FP-Growth算法，這種算法主要通過(guò)FP-Tree來(lái)構(gòu)造頻繁集。

FP-Tree是一個(gè)數(shù)據(jù)庫(kù)里跟產(chǎn)生頻繁項(xiàng)集有關(guān)的信的壓縮表示。在具體的實(shí)現(xiàn)中，我們通過(guò)了一系列的信息的從低到高的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)它，并進(jìn)而實(shí)現(xiàn)整個(gè)算法。

1、關(guān)聯(lián)規(guī)則挖掘基本概念

FP-Growth算法的優(yōu)點(diǎn)是節(jié)省時(shí)間和空間，對(duì)大規(guī)模數(shù)據(jù)采用分治的辦法以避免規(guī)模巨大難以接受。FP-Growth算法主要通過(guò)FP-Tree來(lái)構(gòu)造頻繁集。這里僅介紹與FP增長(zhǎng)算法有關(guān)的基礎(chǔ)概念。

定義一：設(shè) I = { I1 ， I 2 ，...， I n }是n個(gè)不同項(xiàng)的集合，稱(chēng)Ik為一個(gè)項(xiàng)目，項(xiàng)目的集合I稱(chēng)為項(xiàng)集，其中元素的個(gè)數(shù)稱(chēng)為項(xiàng)集的長(zhǎng)度k。

定義二：每個(gè)事務(wù)T是項(xiàng)集I的一個(gè)子集，即TI。每個(gè)事務(wù)有一個(gè)唯一的標(biāo)識(shí)符，記作TID。事務(wù)全體構(gòu)成了事務(wù)數(shù)據(jù)庫(kù)D。

定義三：設(shè)項(xiàng)集X，有XT。關(guān)聯(lián)規(guī)則是形如XY的蘊(yùn)涵式，其中XI，YI，并且。表示項(xiàng)集X在某一交易中出現(xiàn)，則導(dǎo)致Y以某一概率也會(huì)出現(xiàn)。用戶(hù)關(guān)心的關(guān)聯(lián)規(guī)則，可以用兩個(gè)標(biāo)準(zhǔn)來(lái)衡量：支持度（support）和可信度（confidence）。

定義四：支持度是項(xiàng)集同時(shí)包含X和Y的項(xiàng)集個(gè)數(shù)與項(xiàng)集個(gè)數(shù)之比。它是概率P（XY）?？尚哦仁侵赴琗和Y的項(xiàng)集個(gè)數(shù)與包含X的項(xiàng)集個(gè)數(shù)之比，它是條件概率P（Y|X）。即

定義五：設(shè)關(guān)聯(lián)規(guī)則的最小支持度和最小可信度分別為sup_min和conf_min，支持度小于sup_min且置信度小于conf_min的規(guī)則記作強(qiáng)關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則挖掘的目的就是找出這種強(qiáng)關(guān)聯(lián)規(guī)則。

定義六：支持度不小于sup_min的項(xiàng)集稱(chēng)為頻繁集，長(zhǎng)度為k的頻繁集稱(chēng)為k-頻繁集。

通過(guò)以上定義，我們知道關(guān)聯(lián)規(guī)則挖掘的兩個(gè)主要問(wèn)題是：

（1）找出項(xiàng)集數(shù)據(jù)庫(kù)中所有大于或者等于sup_min的頻繁項(xiàng)集。

（2）根據(jù)conf_min篩選出強(qiáng)關(guān)聯(lián)規(guī)則。

在這兩個(gè)問(wèn)題中，找出頻繁集是比較困難，所以目前所有的關(guān)聯(lián)規(guī)則算法主要是針對(duì)第一個(gè)問(wèn)題進(jìn)行研究，而有了頻繁集再生成強(qiáng)關(guān)聯(lián)規(guī)則就相對(duì)容易了。

2、FP增長(zhǎng)算法應(yīng)用

FP-Growth算法是一種不產(chǎn)生候選集的挖掘頻繁項(xiàng)集算法。它通過(guò)構(gòu)造一個(gè)數(shù)據(jù)結(jié)構(gòu)（FP-tree），高度壓縮原來(lái)的事務(wù)數(shù)據(jù)庫(kù)。FP-Growth的算法共掃描兩次數(shù)據(jù)庫(kù)[3]：第1次掃描數(shù)據(jù)庫(kù)，得到頻繁1-項(xiàng)集；第2次掃描數(shù)據(jù)庫(kù)，利用頻繁1-項(xiàng)集過(guò)濾數(shù)據(jù)庫(kù)中的非頻繁項(xiàng)，同時(shí)生成FP-Tree。最后通過(guò)這棵樹(shù)生成關(guān)聯(lián)規(guī)則。

2.1建立原始樣本數(shù)據(jù)庫(kù)

設(shè)事務(wù)數(shù)據(jù)庫(kù)中有5個(gè)事務(wù)，見(jiàn)下表1所示。

2.2建立頻繁項(xiàng)集頭表

假定最小事務(wù)支持計(jì)數(shù)為3（即min_sup=3/5=60%）。掃描數(shù)據(jù)庫(kù)一次，得到頻繁1-項(xiàng)集，把項(xiàng)集按支持度遞減排序，確定頻繁項(xiàng)集頭表Head。它由具有最小支持度的候選1-項(xiàng)集組成，見(jiàn)表2所示。

2.3建立FP-Tree

2.4從FP-Tree到條件模式庫(kù)

按每個(gè)頻繁項(xiàng)的連接遍歷FP-Tree，列出能夠到達(dá)此項(xiàng)的所有前綴路徑，得到條件模式庫(kù)，如表4所示。

2.5從條件模式庫(kù)得到頻繁項(xiàng)集

從條件模式庫(kù)的p項(xiàng)開(kāi)始，遍歷其條件模式庫(kù)中的每一項(xiàng)，列出公共部分，包括單項(xiàng)及多項(xiàng)之間的組合，并進(jìn)行相應(yīng)的計(jì)數(shù)，得到條件FP-Tree，再將條件FP-Tree與相應(yīng)的頭表項(xiàng)進(jìn)行連接，最終生成頻繁項(xiàng)集。如表5所示。

3、FP增長(zhǎng)算法應(yīng)用實(shí)例和程序?qū)崿F(xiàn)

3.1應(yīng)用實(shí)例

我們隨機(jī)的從淘寶某賣(mài)家的實(shí)驗(yàn)樣本中抽取了一部分?jǐn)?shù)據(jù)（如表6所示）模擬FP增長(zhǎng)算法的過(guò)程。表格中的數(shù)據(jù)表示不同的顧客購(gòu)買(mǎi)不同的商品種類(lèi)，表格開(kāi)頭一列是顧客的編號(hào)，每一行表示的是顧客購(gòu)物車(chē)中的商品名稱(chēng)編號(hào)，對(duì)這個(gè)原始購(gòu)物車(chē)數(shù)據(jù)可以挖掘出商品間的關(guān)聯(lián)關(guān)系。

3.2程序模塊設(shè)計(jì)和代碼實(shí)現(xiàn)

3.2.1程序模塊設(shè)計(jì)

在進(jìn)行程序設(shè)計(jì)時(shí)，我們采用三層處理模塊（如圖3所示）。底層為數(shù)據(jù)處理模塊，采用UltraEdit等工具來(lái)提供原始數(shù)據(jù)并進(jìn)行數(shù)據(jù)處理；中間層為業(yè)務(wù)邏輯處理模塊，按照論文所用到的FP增長(zhǎng)算法計(jì)算顧客購(gòu)物車(chē)中商品的關(guān)聯(lián)關(guān)系，具體過(guò)程在Visual C++開(kāi)發(fā)工具環(huán)境中實(shí)現(xiàn)的；上層為輸出模塊，用戶(hù)可以觀看到頻繁項(xiàng)集挖掘結(jié)果。

3.2.2部分代碼實(shí)現(xiàn)

4、結(jié)束語(yǔ)

本文利用程序把以上分析的FP-Growth算法實(shí)現(xiàn)，并挑選了一些中小電商賣(mài)家的銷(xiāo)售數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。試驗(yàn)結(jié)果表明，這些挖掘算法在電子商務(wù)的購(gòu)物車(chē)分析中有相當(dāng)大的優(yōu)勢(shì)，為電商賣(mài)家提供了非常有說(shuō)服力的銷(xiāo)售策略數(shù)據(jù)。但是當(dāng)數(shù)據(jù)量巨大是，我們選擇的挖掘算法就難以順利進(jìn)行。因此需要針對(duì)大數(shù)據(jù)量背景下的挖掘算法改進(jìn)，其中思路之一就是利用Hadhoop框架實(shí)現(xiàn)并行化且負(fù)載均衡的FP-Growth算法，以解決原有FP-Growth算法在內(nèi)存和計(jì)算能力上的問(wèn)題，為當(dāng)當(dāng)、京東、亞馬遜等大型電商平臺(tái)提供組合推薦銷(xiāo)售的理論依據(jù)。