數據挖掘技術與網上購物推薦系統

薛潔 劉希玉

山東師范大學管理與經濟學院 山東 250014

0 引言

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

1 網上購物推薦系統

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

2 數據挖掘

（1）數據挖掘的概念

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

（2）數據挖掘的任務

數據挖掘涵蓋范圍很廣的數據分析和知識發現任務，包括：數據特征化、區分、關聯、相關分析、分類、預測、聚類、離群點分析、演變分析等。

3 數據挖掘在網上購物推薦系統中的主要應用

網上購物推薦系統主要用到數據挖掘中的數據預處理技術，關聯規則挖掘，分類分析，聚類分析等技術，本文主要介紹關聯規則挖掘技術與聚類分析技術的應用。

3.1 挖掘關聯規則的應用

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

例 1：在圖書網站上，消費者想購買數據挖掘概念與技術叢書。

商家根據對關聯規則的挖掘結果將數據挖掘概念與技術叢書與數據倉庫叢書放到一起銷售的策略，通過向客戶推薦額外的商品來提高交叉銷售量。

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

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

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

1993年Agrawal首先提出關聯規則概念，關聯規則挖掘的對象是事務數據庫。關聯規則挖掘是指從數據集中識別出頻繁項集，再利用頻繁項集創建描述關聯關系的規則的過程。

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

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

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

兩種經典的頻繁項集挖掘算法：

目前，已經有許多種對于頻繁項集的挖掘算法，如Apriori，FP T ree，使用垂直數據格式挖掘，挖掘閉頻繁項集等，本文只簡單介紹兩種最經典的頻繁項集挖掘算法。

使用候選產生頻繁項集-----Apriori

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

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

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

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

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

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

不候選產生頻繁項集----FP Tree

FP Tree是一種樹形結構，FP Tree算法過程如下：

（1）初始掃描事物數據庫一次，對每項的出現次數計數，頻繁項按降序排列，結果記為L。

（2）構造FP Tree首先，創建樹的根節點，用“null”標記；第二次掃描數據庫，每個事務的項按L中的次序處理并對每個事務創建一個分枝。

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

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

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

3.2 聚類分析的應用

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

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

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

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

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

K均值算法以k為輸入參數，把n個對象的集合分為k個簇，使得簇內的相似度高，簇間的相似度低，簇的相似度是根據簇中對象的均值度量，可以看作簇的質心。

K均值算法的過程如下：

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

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

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

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

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

基于密度的DBSCAN算法：

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

DBSCAN的操作過程：

（1）確定對象半徑ε和對象的ε鄰域內至少包含的對象的最小數目MinPts。

（2）檢查數據庫中每個點的ε領域。

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

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

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

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

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

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

4 總結

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

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

[2]劉旭東.B2C網上購物推薦系統的設計與實現.煙臺:計算機應用于軟件.2009.

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

[4]耿曉中.超市管理系統及數據挖掘技術在其上的應用.吉林大學.2004.

[5]張晶.基于 FP 關聯規則的購物推薦系統的開發.復旦大學. 2009.