數(shù)據(jù)挖掘技術(shù)與網(wǎng)上購物推薦系統(tǒng)

薛潔 劉希玉

山東師范大學管理與經(jīng)濟學院 山東 250014

0 引言

隨著信息時代的到來，網(wǎng)上購物也已經(jīng)成為人們主要的購物方式之一。我們只需聯(lián)網(wǎng)操作不出家門即可獲得較為滿意的商品。然而，隨著信息數(shù)量的激增，使得網(wǎng)上購物變得復雜，耗時。那么消費者如何才能更便捷更滿意地從海量推銷產(chǎn)品中買到所需商品；銷售者如何才能吸引更多的客戶前來購買自家產(chǎn)品，已成為一個亟待解決的問題。本文介紹了網(wǎng)上購物推薦技術(shù)以及構(gòu)成此技術(shù)的數(shù)據(jù)挖掘相關(guān)內(nèi)容，可以有效地幫助供需雙方更好地進行網(wǎng)上商品交易。

1 網(wǎng)上購物推薦系統(tǒng)

網(wǎng)上購物推薦系統(tǒng)(ReComnlendatinoSystem)就是通過分析用戶瀏覽過的網(wǎng)頁、網(wǎng)購過的商品等來得出其喜好、習慣的結(jié)論，然后向其推薦信息、商品的程序。網(wǎng)上購物推薦系統(tǒng)能夠很好地向用戶推薦所需產(chǎn)品，幫助用戶方便準確地買到物美價廉的商品，也能夠幫助銷售商促進產(chǎn)品的銷售量以及商品貨架的安排，進貨的配比等。

2 數(shù)據(jù)挖掘

（1）數(shù)據(jù)挖掘的概念

數(shù)據(jù)挖掘就是從海量數(shù)據(jù)中提取或“挖掘”有用信息，也就是從大量信息中找到那些有用的，自己所需的信息。也有人將數(shù)據(jù)挖掘看做數(shù)據(jù)中的知識發(fā)現(xiàn)或是從存放在數(shù)據(jù)庫、數(shù)據(jù)倉庫等信息庫中的大量書籍中發(fā)現(xiàn)有趣知識的過程。

（2）數(shù)據(jù)挖掘的任務

數(shù)據(jù)挖掘涵蓋范圍很廣的數(shù)據(jù)分析和知識發(fā)現(xiàn)任務，包括：數(shù)據(jù)特征化、區(qū)分、關(guān)聯(lián)、相關(guān)分析、分類、預測、聚類、離群點分析、演變分析等。

3 數(shù)據(jù)挖掘在網(wǎng)上購物推薦系統(tǒng)中的主要應用

網(wǎng)上購物推薦系統(tǒng)主要用到數(shù)據(jù)挖掘中的數(shù)據(jù)預處理技術(shù)，關(guān)聯(lián)規(guī)則挖掘，分類分析，聚類分析等技術(shù)，本文主要介紹關(guān)聯(lián)規(guī)則挖掘技術(shù)與聚類分析技術(shù)的應用。

3.1 挖掘關(guān)聯(lián)規(guī)則的應用

挖掘關(guān)聯(lián)規(guī)則應用于網(wǎng)上購物推薦系統(tǒng)可以：(1)向用戶推薦相關(guān)產(chǎn)品，提高相關(guān)產(chǎn)品的銷售額，即促進產(chǎn)品的捆綁銷售；(2)安排商品銷售的搭配；(3)準確進行進貨配比；(4)根據(jù)購買模式對用戶進行分類。從而動態(tài)調(diào)整網(wǎng)頁，給各類用戶提供更為滿意的購物選擇。

例 1：在圖書網(wǎng)站上，消費者想購買數(shù)據(jù)挖掘概念與技術(shù)叢書。

商家根據(jù)對關(guān)聯(lián)規(guī)則的挖掘結(jié)果將數(shù)據(jù)挖掘概念與技術(shù)叢書與數(shù)據(jù)倉庫叢書放到一起銷售的策略，通過向客戶推薦額外的商品來提高交叉銷售量。

根據(jù)商家進行數(shù)據(jù)挖掘得到的信息：購買數(shù)據(jù)挖掘概念與技術(shù)的用戶有69%還購買了數(shù)據(jù)倉庫。經(jīng)調(diào)查許多顧客都會受到這種導向的影響，已經(jīng)購買數(shù)據(jù)挖掘概念與技術(shù)的顧客很有可能向購買此書的前輩一樣也隨之購買其本不打算買的數(shù)據(jù)倉庫。

例2：更進一步，根據(jù)對若干個例1中購買數(shù)據(jù)挖掘概念與技術(shù)的顧客進行關(guān)聯(lián)規(guī)則挖掘，便可得到購買數(shù)據(jù)挖掘概念與技術(shù)的顧客也同時購買了DW2.0：下一代數(shù)據(jù)倉庫的構(gòu)造與數(shù)據(jù)倉庫生命周期工具箱。這樣可增加顧客對于此類叢書的購買欲望；也使得商家在進書時，可以更好地配比有關(guān)數(shù)據(jù)挖掘類叢書。但是較之例1，例2沒有列出數(shù)據(jù)的支持，可信度較低。

例3：為某個用戶推薦N種商品通過關(guān)聯(lián)規(guī)則來實現(xiàn)。首先為每個用戶產(chǎn)生一條記錄，包括該用戶所有曾經(jīng)購買過的商品，運用關(guān)聯(lián)規(guī)則的挖掘算法從這個數(shù)據(jù)庫中找出所有滿足最小支持度閾值和最小置信度閾值的關(guān)聯(lián)規(guī)則。然后從這些規(guī)則中找出被目標用戶支持的那些(即用戶購買了所有出現(xiàn)在規(guī)則左邊的商品)，列出用戶尚未購買的產(chǎn)品，根據(jù)規(guī)則的置信度對產(chǎn)品進行排序，向用戶推薦前N種。

1993年Agrawal首先提出關(guān)聯(lián)規(guī)則概念，關(guān)聯(lián)規(guī)則挖掘的對象是事務數(shù)據(jù)庫。關(guān)聯(lián)規(guī)則挖掘是指從數(shù)據(jù)集中識別出頻繁項集，再利用頻繁項集創(chuàng)建描述關(guān)聯(lián)關(guān)系的規(guī)則的過程。

設I={I1，I2，…,Im}是項的集合。D是由若干條事務記錄構(gòu)成的事務數(shù)據(jù)庫，其中每個事物T是項的集合，使得TI，對應每一個事務T有惟一的標識，記作TID。設A是一個項集，事務T包含A當且僅當AI。關(guān)聯(lián)規(guī)則的一般形式為:A=＞B的蘊涵式，其中AI,BI，AB=。

規(guī)則通過置信度與支持度來衡量其確定性和可用性，典型情況下，如果同時滿足最小置信度與支持度，則規(guī)則是有用的Support(A=＞B)=P(AυB);confidence(A=＞B)=P(BIA)

因為如果項集滿足最小支持度閾值，則稱項集為頻繁項集，又因為confidence(A=＞B)=P(BIA)= Support(AB)/Support(A)，所以置信度可以輕易從支持度中求出，進而挖掘關(guān)聯(lián)規(guī)則的問題就變?yōu)橥诰蝾l繁項集的問題。

兩種經(jīng)典的頻繁項集挖掘算法：

目前，已經(jīng)有許多種對于頻繁項集的挖掘算法，如Apriori，F(xiàn)P T ree，使用垂直數(shù)據(jù)格式挖掘，挖掘閉頻繁項集等，本文只簡單介紹兩種最經(jīng)典的頻繁項集挖掘算法。

使用候選產(chǎn)生頻繁項集-----Apriori

Apriori算法整個過程基于其頻繁項集的所有非空子集也必須是頻繁的這一性質(zhì)，按以下步驟進行：

（1）選定最小支持度閾值min_support。

（2）初始掃描事物數(shù)據(jù)庫一次，對每項即 L1(為候選項集C1的成員)的出現(xiàn)次數(shù)計數(shù)，將計數(shù)小于min_support的項進行剪枝。

（3）使用留下的L1∞L1自連接產(chǎn)生候選項集L2，掃描數(shù)據(jù)庫，對L2的出現(xiàn)次數(shù)計數(shù)，將計數(shù)小于min_support的項進行剪枝。

（4）重復上述操作，直至找出所有的頻繁項集，算法結(jié)束。

其實Apriori算法只進行連接和剪枝兩個步驟，操作簡單易懂，但是由于算法的每次迭代都需掃描數(shù)據(jù)庫一次，致使時間復雜度極大，且對于大型數(shù)據(jù)庫也不易操作。

不候選產(chǎn)生頻繁項集----FP Tree

FP Tree是一種樹形結(jié)構(gòu)，F(xiàn)P Tree算法過程如下：

（1）初始掃描事物數(shù)據(jù)庫一次，對每項的出現(xiàn)次數(shù)計數(shù)，頻繁項按降序排列，結(jié)果記為L。

（2）構(gòu)造FP Tree首先，創(chuàng)建樹的根節(jié)點，用“null”標記；第二次掃描數(shù)據(jù)庫，每個事務的項按L中的次序處理并對每個事務創(chuàng)建一個分枝。

（3）為tree創(chuàng)建一個項表頭，使每項通過一個節(jié)點鏈指向它在樹中的位置，此舉可方便樹的遍歷。

（4）挖掘FP Tree，由每個長度為1的頻繁模式開始，構(gòu)造它的條件模式基，然后構(gòu)造其FP Tree。

（5）遞歸地進行e過程，F(xiàn)P Tree算法較之Apriori算法而言，其只需掃描事務數(shù)據(jù)庫兩次，大量減少了掃描數(shù)據(jù)庫所需的時間，簡化了操作過程，但是若數(shù)據(jù)庫很大，構(gòu)造FP Tree也是不現(xiàn)實的。

3.2 聚類分析的應用

通過用戶瀏覽過的網(wǎng)頁或消費記錄，對用戶進行聚類分析，可將具有相同喜好，相似習慣的用戶劃分到同一個簇中，然后根據(jù)同一個簇中用戶的意見向其更好更準確到位地推薦商品，也可動態(tài)地進行某類產(chǎn)品銷售網(wǎng)頁的調(diào)整，從而提供更合適，更令顧客滿意的服務。對于商家，可根據(jù)不同簇中用戶的特征，制作不同的銷售網(wǎng)頁，制定不同的銷售策略，例如自動給一個特定的顧客聚類發(fā)送銷售郵件，為一個顧客聚類動態(tài)地改變一個特殊的站點等，便于開發(fā)和執(zhí)行未來的市場戰(zhàn)略。

例：顧客A先前在網(wǎng)上購買了數(shù)據(jù)挖掘概念與技術(shù)和算法分析兩本書，同時瀏覽了一些關(guān)于計算機類的商品，當A再次打開商品網(wǎng)頁時，頁面下方提示與A興趣相似的顧客所關(guān)注的產(chǎn)品。這就是商家進行聚類分析的結(jié)果，通過A的瀏覽與購買記錄，將與A有相似行為的顧客群分到同一個簇中，當滿足此簇特征的用戶進入網(wǎng)站時，站點便會動態(tài)給出其感興趣的相關(guān)產(chǎn)品。用戶必定受到這個提示的影響，瀏覽-＞購買此類產(chǎn)品。

將物理或抽象對象的集合分成相似的對象類的過程稱為聚類。簇是數(shù)據(jù)對象的集合，同一個簇中的對象彼此相似，而與其他簇中的對象相異。

聚類方法主要有：劃分方法(k均值，k中心點)，層次方法(凝聚，分裂)，基于密度的方法(DBSCAN,OPTICS)，基于網(wǎng)格的方法(STING)，基于模糊的方法(EM)等。本文簡單介紹兩種較為常用的聚類方法。

劃分方法中的k均值方法：

K均值算法以k為輸入?yún)?shù)，把n個對象的集合分為k個簇，使得簇內(nèi)的相似度高，簇間的相似度低，簇的相似度是根據(jù)簇中對象的均值度量，可以看作簇的質(zhì)心。

K均值算法的過程如下：

（1）隨機地選擇k個對象，每個對象代表一個簇的初始均值。

（2）根據(jù)剩余對象與各個簇均值的距離，將它們指派到與各自最相似的簇中。

（3）重復上述過程，直至準則函數(shù)收斂，通常選擇平方誤差準則：

其中，E是所有對象的平方誤差和，p是空間中的點，表示給定對象，Mi是簇Ci的均值。此算法的時間復雜度是O(nkt)。

K均值法對于處理結(jié)果緊湊，并且簇與簇之間分離明顯的對象集合時效果較好，但是這種聚類方法必須事先給出要生成的簇的數(shù)目，在多數(shù)情況下，面對龐大的用戶對象的消費記錄和瀏覽過的網(wǎng)頁的Web日志，銷售商很難判定到底將它們分成幾個簇較好，所以k均值算法在此有一定的局限性。

基于密度的DBSCAN算法：

DBSCAN是一種基于高密度連通區(qū)域的基于密度的聚類方法，它將具有足夠高密度的區(qū)域劃分為簇，將簇定義為密度相連的點的最大集合。

DBSCAN的操作過程：

（1）確定對象半徑ε和對象的ε鄰域內(nèi)至少包含的對象的最小數(shù)目MinPts。

（2）檢查數(shù)據(jù)庫中每個點的ε領(lǐng)域。

（3）如果點p的ε領(lǐng)域包含的點多于MinPts個，則創(chuàng)建一個以p為核心對象的新簇。

（4）迭代聚集從上述核心對象直接密度可達(給定一個對象集合D，如果p在q的ε領(lǐng)域內(nèi)，同時q是一個核心對象，則我們說對象p從對象q出發(fā)是直接密度可達的)的對象。

（5）至沒有新的點添加，操作結(jié)束。

DBSCAN算法的時間復雜度是O(n2)。

此算法需要用戶給出ε和MinPts，無需給出所劃分簇的數(shù)目，只要ε和MinPt s得當，便可有效找出任意形狀的簇。

當然，還有許多其他聚類算法，如貝葉斯聚類算法，WaveCluster算法，遺傳算法等，也有許多學者致力于新的聚類算法的研究，相信聚類技術(shù)會更加快速，有效。

4 總結(jié)

網(wǎng)上購物推薦系統(tǒng)現(xiàn)已在卓越亞馬遜，當當?shù)榷鄠€購物網(wǎng)站成功使用。當然其所包含與使用的技術(shù)并不僅僅包括文中所述的關(guān)聯(lián)規(guī)則與聚類分析技術(shù)，還需對不同數(shù)據(jù)進行預處理，協(xié)同過濾等相關(guān)操作。本文僅簡單介紹其中的關(guān)聯(lián)規(guī)則挖掘與聚類分析的幾種方法。網(wǎng)上購物推薦系統(tǒng)雖然應用廣泛，能夠使用戶和商家產(chǎn)生雙贏局面，但是它也存在許多不足，此為未來需要研究的主要方向。隨著網(wǎng)絡與電子商務的普及，相信網(wǎng)上購物推薦系統(tǒng)也會越來越完善！

[1]JiaWei Han.數(shù)據(jù)挖掘概念與技術(shù)(原書第二版).機械工業(yè)出版社.2010.

[2]劉旭東.B2C網(wǎng)上購物推薦系統(tǒng)的設計與實現(xiàn).煙臺:計算機應用于軟件.2009.

[3]宋紅芳.Web數(shù)據(jù)挖掘在電子商務中的應用研究.山東科技大學.2005.

[4]耿曉中.超市管理系統(tǒng)及數(shù)據(jù)挖掘技術(shù)在其上的應用.吉林大學.2004.

[5]張晶.基于 FP 關(guān)聯(lián)規(guī)則的購物推薦系統(tǒng)的開發(fā).復旦大學. 2009.