薛潔 劉希玉
山東師范大學(xué)管理與經(jīng)濟(jì)學(xué)院 山東 250014
隨著信息時(shí)代的到來(lái),網(wǎng)上購(gòu)物也已經(jīng)成為人們主要的購(gòu)物方式之一。我們只需聯(lián)網(wǎng)操作不出家門即可獲得較為滿意的商品。然而,隨著信息數(shù)量的激增,使得網(wǎng)上購(gòu)物變得復(fù)雜,耗時(shí)。那么消費(fèi)者如何才能更便捷更滿意地從海量推銷產(chǎn)品中買到所需商品;銷售者如何才能吸引更多的客戶前來(lái)購(gòu)買自家產(chǎn)品,已成為一個(gè)亟待解決的問題。本文介紹了網(wǎng)上購(gòu)物推薦技術(shù)以及構(gòu)成此技術(shù)的數(shù)據(jù)挖掘相關(guān)內(nèi)容,可以有效地幫助供需雙方更好地進(jìn)行網(wǎng)上商品交易。
網(wǎng)上購(gòu)物推薦系統(tǒng)(ReComnlendatinoSystem)就是通過分析用戶瀏覽過的網(wǎng)頁(yè)、網(wǎng)購(gòu)過的商品等來(lái)得出其喜好、習(xí)慣的結(jié)論,然后向其推薦信息、商品的程序。網(wǎng)上購(gòu)物推薦系統(tǒng)能夠很好地向用戶推薦所需產(chǎn)品,幫助用戶方便準(zhǔn)確地買到物美價(jià)廉的商品,也能夠幫助銷售商促進(jìn)產(chǎn)品的銷售量以及商品貨架的安排,進(jìn)貨的配比等。
(1)數(shù)據(jù)挖掘的概念
數(shù)據(jù)挖掘就是從海量數(shù)據(jù)中提取或“挖掘”有用信息,也就是從大量信息中找到那些有用的,自己所需的信息。也有人將數(shù)據(jù)挖掘看做數(shù)據(jù)中的知識(shí)發(fā)現(xiàn)或是從存放在數(shù)據(jù)庫(kù)、數(shù)據(jù)倉(cāng)庫(kù)等信息庫(kù)中的大量書籍中發(fā)現(xiàn)有趣知識(shí)的過程。
(2)數(shù)據(jù)挖掘的任務(wù)
數(shù)據(jù)挖掘涵蓋范圍很廣的數(shù)據(jù)分析和知識(shí)發(fā)現(xiàn)任務(wù),包括:數(shù)據(jù)特征化、區(qū)分、關(guān)聯(lián)、相關(guān)分析、分類、預(yù)測(cè)、聚類、離群點(diǎn)分析、演變分析等。
網(wǎng)上購(gòu)物推薦系統(tǒng)主要用到數(shù)據(jù)挖掘中的數(shù)據(jù)預(yù)處理技術(shù),關(guān)聯(lián)規(guī)則挖掘,分類分析,聚類分析等技術(shù),本文主要介紹關(guān)聯(lián)規(guī)則挖掘技術(shù)與聚類分析技術(shù)的應(yīng)用。
挖掘關(guān)聯(lián)規(guī)則應(yīng)用于網(wǎng)上購(gòu)物推薦系統(tǒng)可以:(1)向用戶推薦相關(guān)產(chǎn)品,提高相關(guān)產(chǎn)品的銷售額,即促進(jìn)產(chǎn)品的捆綁銷售;(2)安排商品銷售的搭配;(3)準(zhǔn)確進(jìn)行進(jìn)貨配比;(4)根據(jù)購(gòu)買模式對(duì)用戶進(jìn)行分類。從而動(dòng)態(tài)調(diào)整網(wǎng)頁(yè),給各類用戶提供更為滿意的購(gòu)物選擇。
例 1:在圖書網(wǎng)站上,消費(fèi)者想購(gòu)買數(shù)據(jù)挖掘概念與技術(shù)叢書。
商家根據(jù)對(duì)關(guān)聯(lián)規(guī)則的挖掘結(jié)果將數(shù)據(jù)挖掘概念與技術(shù)叢書與數(shù)據(jù)倉(cāng)庫(kù)叢書放到一起銷售的策略,通過向客戶推薦額外的商品來(lái)提高交叉銷售量。
根據(jù)商家進(jìn)行數(shù)據(jù)挖掘得到的信息:購(gòu)買數(shù)據(jù)挖掘概念與技術(shù)的用戶有69%還購(gòu)買了數(shù)據(jù)倉(cāng)庫(kù)。經(jīng)調(diào)查許多顧客都會(huì)受到這種導(dǎo)向的影響,已經(jīng)購(gòu)買數(shù)據(jù)挖掘概念與技術(shù)的顧客很有可能向購(gòu)買此書的前輩一樣也隨之購(gòu)買其本不打算買的數(shù)據(jù)倉(cāng)庫(kù)。
例2:更進(jìn)一步,根據(jù)對(duì)若干個(gè)例1中購(gòu)買數(shù)據(jù)挖掘概念與技術(shù)的顧客進(jìn)行關(guān)聯(lián)規(guī)則挖掘,便可得到購(gòu)買數(shù)據(jù)挖掘概念與技術(shù)的顧客也同時(shí)購(gòu)買了DW2.0:下一代數(shù)據(jù)倉(cāng)庫(kù)的構(gòu)造與數(shù)據(jù)倉(cāng)庫(kù)生命周期工具箱。這樣可增加顧客對(duì)于此類叢書的購(gòu)買欲望;也使得商家在進(jìn)書時(shí),可以更好地配比有關(guān)數(shù)據(jù)挖掘類叢書。但是較之例1,例2沒有列出數(shù)據(jù)的支持,可信度較低。
例3:為某個(gè)用戶推薦N種商品通過關(guān)聯(lián)規(guī)則來(lái)實(shí)現(xiàn)。首先為每個(gè)用戶產(chǎn)生一條記錄,包括該用戶所有曾經(jīng)購(gòu)買過的商品,運(yùn)用關(guān)聯(lián)規(guī)則的挖掘算法從這個(gè)數(shù)據(jù)庫(kù)中找出所有滿足最小支持度閾值和最小置信度閾值的關(guān)聯(lián)規(guī)則。然后從這些規(guī)則中找出被目標(biāo)用戶支持的那些(即用戶購(gòu)買了所有出現(xiàn)在規(guī)則左邊的商品),列出用戶尚未購(gòu)買的產(chǎn)品,根據(jù)規(guī)則的置信度對(duì)產(chǎn)品進(jìn)行排序,向用戶推薦前N種。
1993年Agrawal首先提出關(guān)聯(lián)規(guī)則概念,關(guān)聯(lián)規(guī)則挖掘的對(duì)象是事務(wù)數(shù)據(jù)庫(kù)。關(guān)聯(lián)規(guī)則挖掘是指從數(shù)據(jù)集中識(shí)別出頻繁項(xiàng)集,再利用頻繁項(xiàng)集創(chuàng)建描述關(guān)聯(lián)關(guān)系的規(guī)則的過程。
設(shè)I={I1,I2,…,Im}是項(xiàng)的集合。D是由若干條事務(wù)記錄構(gòu)成的事務(wù)數(shù)據(jù)庫(kù),其中每個(gè)事物T是項(xiàng)的集合,使得TI,對(duì)應(yīng)每一個(gè)事務(wù)T有惟一的標(biāo)識(shí),記作TID。設(shè)A是一個(gè)項(xiàng)集,事務(wù)T包含A當(dāng)且僅當(dāng)AI。關(guān)聯(lián)規(guī)則的一般形式為:A=>B的蘊(yùn)涵式,其中AI,BI,AB=。
規(guī)則通過置信度與支持度來(lái)衡量其確定性和可用性,典型情況下,如果同時(shí)滿足最小置信度與支持度,則規(guī)則是有用的Support(A=>B)=P(AυB);confidence(A=>B)=P(BIA)
因?yàn)槿绻?xiàng)集滿足最小支持度閾值,則稱項(xiàng)集為頻繁項(xiàng)集,又因?yàn)閏onfidence(A=>B)=P(BIA)= Support(AB)/Support(A),所以置信度可以輕易從支持度中求出,進(jìn)而挖掘關(guān)聯(lián)規(guī)則的問題就變?yōu)橥诰蝾l繁項(xiàng)集的問題。
兩種經(jīng)典的頻繁項(xiàng)集挖掘算法:
目前,已經(jīng)有許多種對(duì)于頻繁項(xiàng)集的挖掘算法,如Apriori,F(xiàn)P T ree,使用垂直數(shù)據(jù)格式挖掘,挖掘閉頻繁項(xiàng)集等,本文只簡(jiǎn)單介紹兩種最經(jīng)典的頻繁項(xiàng)集挖掘算法。
使用候選產(chǎn)生頻繁項(xiàng)集-----Apriori
Apriori算法整個(gè)過程基于其頻繁項(xiàng)集的所有非空子集也必須是頻繁的這一性質(zhì),按以下步驟進(jìn)行:
(1)選定最小支持度閾值min_support。
(2)初始掃描事物數(shù)據(jù)庫(kù)一次,對(duì)每項(xiàng)即 L1(為候選項(xiàng)集C1的成員)的出現(xiàn)次數(shù)計(jì)數(shù),將計(jì)數(shù)小于min_support的項(xiàng)進(jìn)行剪枝。
(3)使用留下的L1∞L1自連接產(chǎn)生候選項(xiàng)集L2,掃描數(shù)據(jù)庫(kù),對(duì)L2的出現(xiàn)次數(shù)計(jì)數(shù),將計(jì)數(shù)小于min_support的項(xiàng)進(jìn)行剪枝。
(4)重復(fù)上述操作,直至找出所有的頻繁項(xiàng)集,算法結(jié)束。
其實(shí)Apriori算法只進(jìn)行連接和剪枝兩個(gè)步驟,操作簡(jiǎn)單易懂,但是由于算法的每次迭代都需掃描數(shù)據(jù)庫(kù)一次,致使時(shí)間復(fù)雜度極大,且對(duì)于大型數(shù)據(jù)庫(kù)也不易操作。
不候選產(chǎn)生頻繁項(xiàng)集----FP Tree
FP Tree是一種樹形結(jié)構(gòu),F(xiàn)P Tree算法過程如下:
(1)初始掃描事物數(shù)據(jù)庫(kù)一次,對(duì)每項(xiàng)的出現(xiàn)次數(shù)計(jì)數(shù),頻繁項(xiàng)按降序排列,結(jié)果記為L(zhǎng)。
(2)構(gòu)造FP Tree首先,創(chuàng)建樹的根節(jié)點(diǎn),用“null”標(biāo)記;第二次掃描數(shù)據(jù)庫(kù),每個(gè)事務(wù)的項(xiàng)按L中的次序處理并對(duì)每個(gè)事務(wù)創(chuàng)建一個(gè)分枝。
(3)為tree創(chuàng)建一個(gè)項(xiàng)表頭,使每項(xiàng)通過一個(gè)節(jié)點(diǎn)鏈指向它在樹中的位置,此舉可方便樹的遍歷。
(4)挖掘FP Tree,由每個(gè)長(zhǎng)度為1的頻繁模式開始,構(gòu)造它的條件模式基,然后構(gòu)造其FP Tree。
(5)遞歸地進(jìn)行e過程,F(xiàn)P Tree算法較之Apriori算法而言,其只需掃描事務(wù)數(shù)據(jù)庫(kù)兩次,大量減少了掃描數(shù)據(jù)庫(kù)所需的時(shí)間,簡(jiǎn)化了操作過程,但是若數(shù)據(jù)庫(kù)很大,構(gòu)造FP Tree也是不現(xiàn)實(shí)的。
通過用戶瀏覽過的網(wǎng)頁(yè)或消費(fèi)記錄,對(duì)用戶進(jìn)行聚類分析,可將具有相同喜好,相似習(xí)慣的用戶劃分到同一個(gè)簇中,然后根據(jù)同一個(gè)簇中用戶的意見向其更好更準(zhǔn)確到位地推薦商品,也可動(dòng)態(tài)地進(jìn)行某類產(chǎn)品銷售網(wǎng)頁(yè)的調(diào)整,從而提供更合適,更令顧客滿意的服務(wù)。對(duì)于商家,可根據(jù)不同簇中用戶的特征,制作不同的銷售網(wǎng)頁(yè),制定不同的銷售策略,例如自動(dòng)給一個(gè)特定的顧客聚類發(fā)送銷售郵件,為一個(gè)顧客聚類動(dòng)態(tài)地改變一個(gè)特殊的站點(diǎn)等,便于開發(fā)和執(zhí)行未來(lái)的市場(chǎng)戰(zhàn)略。
例:顧客A先前在網(wǎng)上購(gòu)買了數(shù)據(jù)挖掘概念與技術(shù)和算法分析兩本書,同時(shí)瀏覽了一些關(guān)于計(jì)算機(jī)類的商品,當(dāng)A再次打開商品網(wǎng)頁(yè)時(shí),頁(yè)面下方提示與A興趣相似的顧客所關(guān)注的產(chǎn)品。這就是商家進(jìn)行聚類分析的結(jié)果,通過A的瀏覽與購(gòu)買記錄,將與A有相似行為的顧客群分到同一個(gè)簇中,當(dāng)滿足此簇特征的用戶進(jìn)入網(wǎng)站時(shí),站點(diǎn)便會(huì)動(dòng)態(tài)給出其感興趣的相關(guān)產(chǎn)品。用戶必定受到這個(gè)提示的影響,瀏覽->購(gòu)買此類產(chǎn)品。
將物理或抽象對(duì)象的集合分成相似的對(duì)象類的過程稱為聚類。簇是數(shù)據(jù)對(duì)象的集合,同一個(gè)簇中的對(duì)象彼此相似,而與其他簇中的對(duì)象相異。
聚類方法主要有:劃分方法(k均值,k中心點(diǎn)),層次方法(凝聚,分裂),基于密度的方法(DBSCAN,OPTICS),基于網(wǎng)格的方法(STING),基于模糊的方法(EM)等。本文簡(jiǎn)單介紹兩種較為常用的聚類方法。
劃分方法中的k均值方法:
K均值算法以k為輸入?yún)?shù),把n個(gè)對(duì)象的集合分為k個(gè)簇,使得簇內(nèi)的相似度高,簇間的相似度低,簇的相似度是根據(jù)簇中對(duì)象的均值度量,可以看作簇的質(zhì)心。
K均值算法的過程如下:
(1)隨機(jī)地選擇k個(gè)對(duì)象,每個(gè)對(duì)象代表一個(gè)簇的初始均值。
(2)根據(jù)剩余對(duì)象與各個(gè)簇均值的距離,將它們指派到與各自最相似的簇中。
(3)重復(fù)上述過程,直至準(zhǔn)則函數(shù)收斂,通常選擇平方誤差準(zhǔn)則:
其中,E是所有對(duì)象的平方誤差和,p是空間中的點(diǎn),表示給定對(duì)象,Mi是簇Ci的均值。此算法的時(shí)間復(fù)雜度是O(nkt)。
K均值法對(duì)于處理結(jié)果緊湊,并且簇與簇之間分離明顯的對(duì)象集合時(shí)效果較好,但是這種聚類方法必須事先給出要生成的簇的數(shù)目,在多數(shù)情況下,面對(duì)龐大的用戶對(duì)象的消費(fèi)記錄和瀏覽過的網(wǎng)頁(yè)的Web日志,銷售商很難判定到底將它們分成幾個(gè)簇較好,所以k均值算法在此有一定的局限性。
基于密度的DBSCAN算法:
DBSCAN是一種基于高密度連通區(qū)域的基于密度的聚類方法,它將具有足夠高密度的區(qū)域劃分為簇,將簇定義為密度相連的點(diǎn)的最大集合。
DBSCAN的操作過程:
(1)確定對(duì)象半徑ε和對(duì)象的ε鄰域內(nèi)至少包含的對(duì)象的最小數(shù)目MinPts。
(2)檢查數(shù)據(jù)庫(kù)中每個(gè)點(diǎn)的ε領(lǐng)域。
(3)如果點(diǎn)p的ε領(lǐng)域包含的點(diǎn)多于MinPts個(gè),則創(chuàng)建一個(gè)以p為核心對(duì)象的新簇。
(4)迭代聚集從上述核心對(duì)象直接密度可達(dá)(給定一個(gè)對(duì)象集合D,如果p在q的ε領(lǐng)域內(nèi),同時(shí)q是一個(gè)核心對(duì)象,則我們說對(duì)象p從對(duì)象q出發(fā)是直接密度可達(dá)的)的對(duì)象。
(5)至沒有新的點(diǎn)添加,操作結(jié)束。
DBSCAN算法的時(shí)間復(fù)雜度是O(n2)。
此算法需要用戶給出ε和MinPts,無(wú)需給出所劃分簇的數(shù)目,只要ε和MinPt s得當(dāng),便可有效找出任意形狀的簇。
當(dāng)然,還有許多其他聚類算法,如貝葉斯聚類算法,WaveCluster算法,遺傳算法等,也有許多學(xué)者致力于新的聚類算法的研究,相信聚類技術(shù)會(huì)更加快速,有效。
網(wǎng)上購(gòu)物推薦系統(tǒng)現(xiàn)已在卓越亞馬遜,當(dāng)當(dāng)?shù)榷鄠€(gè)購(gòu)物網(wǎng)站成功使用。當(dāng)然其所包含與使用的技術(shù)并不僅僅包括文中所述的關(guān)聯(lián)規(guī)則與聚類分析技術(shù),還需對(duì)不同數(shù)據(jù)進(jìn)行預(yù)處理,協(xié)同過濾等相關(guān)操作。本文僅簡(jiǎn)單介紹其中的關(guān)聯(lián)規(guī)則挖掘與聚類分析的幾種方法。網(wǎng)上購(gòu)物推薦系統(tǒng)雖然應(yīng)用廣泛,能夠使用戶和商家產(chǎn)生雙贏局面,但是它也存在許多不足,此為未來(lái)需要研究的主要方向。隨著網(wǎng)絡(luò)與電子商務(wù)的普及,相信網(wǎng)上購(gòu)物推薦系統(tǒng)也會(huì)越來(lái)越完善!
[1]JiaWei Han.數(shù)據(jù)挖掘概念與技術(shù)(原書第二版).機(jī)械工業(yè)出版社.2010.
[2]劉旭東.B2C網(wǎng)上購(gòu)物推薦系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn).煙臺(tái):計(jì)算機(jī)應(yīng)用于軟件.2009.
[3]宋紅芳.Web數(shù)據(jù)挖掘在電子商務(wù)中的應(yīng)用研究.山東科技大學(xué).2005.
[4]耿曉中.超市管理系統(tǒng)及數(shù)據(jù)挖掘技術(shù)在其上的應(yīng)用.吉林大學(xué).2004.
[5]張晶.基于 FP 關(guān)聯(lián)規(guī)則的購(gòu)物推薦系統(tǒng)的開發(fā).復(fù)旦大學(xué). 2009.