基于LDA-GA算法的移動(dòng)目錄優(yōu)化研究

梁 潘

(成都航空職業(yè)技術(shù)學(xué)院 機(jī)電工程學(xué)院，四川 成都 610100)

基于LDA-GA算法的移動(dòng)目錄優(yōu)化研究

梁 潘

(成都航空職業(yè)技術(shù)學(xué)院 機(jī)電工程學(xué)院，四川 成都 610100)

針對(duì)移動(dòng)設(shè)備向用戶推薦產(chǎn)品時(shí)受限于尺寸的問題，目前普遍采用個(gè)性化協(xié)作推薦算法來實(shí)現(xiàn)開發(fā)面向移動(dòng)目錄(MOC)，但是傳統(tǒng)的方法存在大數(shù)據(jù)環(huán)境下適應(yīng)度不高、協(xié)作能力差等不足。為解決此問題，首先將主題建模算法與遺傳算法相結(jié)合開發(fā)出LDA-GA算法，然后設(shè)計(jì)富有吸引力和協(xié)作性的產(chǎn)品推薦目錄，最后將MOC應(yīng)用在亞馬遜APP和淘寶網(wǎng)APP進(jìn)行實(shí)驗(yàn)比對(duì)分析并進(jìn)行優(yōu)化。實(shí)驗(yàn)結(jié)果表明：LDA-GA算法面對(duì)大量用戶和產(chǎn)品數(shù)據(jù)時(shí)移動(dòng)目錄適應(yīng)度更高、協(xié)作性更強(qiáng)，客戶受眾面大，推介效果更好。

移動(dòng)目錄；潛在狄利克雷分配；主題建模；遺傳算法

0 引言

在電子商務(wù)中，移動(dòng)目錄(Mobile-Oriented Catalog)是一種有效的產(chǎn)品推薦方式[1-2]，它能有效解決頁面尺寸受限的問題。每個(gè)APP或移動(dòng)頁面均可根據(jù)產(chǎn)品呈現(xiàn)的不同而進(jìn)行不同的移動(dòng)目錄設(shè)計(jì)，通過移動(dòng)目錄來優(yōu)化線上銷售產(chǎn)品目錄可能覆蓋的大多數(shù)用戶人群，從而擴(kuò)大電商銷售人員的收入[3]。

面向移動(dòng)目錄主題建模對(duì)語義分析影響重大，應(yīng)用也多，如文本分類和基于內(nèi)容的推薦系統(tǒng)，主題建模用來根據(jù)文檔中關(guān)鍵詞的分布從語庫中發(fā)現(xiàn)一組“主題”。目前主要的主題建模算法是潛在狄利克雷分布(LDA)法[4]，用它來解決移動(dòng)目錄問題。移動(dòng)目錄問題起源于克萊因伯格等人提出的目錄分割思想[5]，其理念主要是設(shè)計(jì)出針對(duì)客戶細(xì)分而非個(gè)人的目錄；克萊因伯格等人認(rèn)為基于抽樣的算法不適用于移動(dòng)目錄的真實(shí)案例[6]，因?yàn)樗爸挥性谝欢ǖ淖址芏燃僭O(shè)環(huán)境下才有效”；D.Xu等人[7]將目錄分割問題簡(jiǎn)化為2-catalog目錄問題，再利用半正定規(guī)劃方法來設(shè)計(jì)主題建模算法；斯坦巴克等人[8]提出了三種方法來創(chuàng)建推廣目錄，首先，通過K均值聚類算法創(chuàng)建間接目錄來聚集客戶，其次，基于EM算法采用直接目錄創(chuàng)建法(DCC)來設(shè)計(jì)k個(gè)目錄，最后采用混合算法(HCC)；埃斯泰等人首先對(duì)客戶導(dǎo)向的目錄分割問題進(jìn)行界定，再通過貪婪和隨機(jī)算法對(duì)其予以解決；阿米里[9]提出貪婪算法和關(guān)聯(lián)算法來創(chuàng)建客戶興趣目錄；而馬達(dá)維等人采用遺傳算法來將客戶聚集再分成目錄，即所謂的“電子客戶導(dǎo)向目錄(e-COC)”，并證實(shí)了該方法用在e-COC方面要比貪婪法優(yōu)越。本文在已有研究的基礎(chǔ)上，利用主題建模概念來設(shè)計(jì)面向移動(dòng)目錄，將主題建模算法與遺傳算法相結(jié)合開發(fā)出LDA-GA算法，在此基礎(chǔ)上搭建了試驗(yàn)床并做了現(xiàn)場(chǎng)實(shí)驗(yàn)，實(shí)驗(yàn)相關(guān)數(shù)據(jù)表明LDA-GA算法具有更高的適應(yīng)度。

1 MOC問題界定和公式化

1.1 MOC問題的定義

MOC問題：假設(shè)存在一組客戶C和一組產(chǎn)品P；存在一組頁面S，S頁面的尺寸是z，每個(gè)頁面存在一定的權(quán)重Ws，Ks是頁面S上的一組目錄，表示為k，Ks的大小是n。MOC存在一個(gè)明顯的限制就是客戶興趣最小閾值t，即一個(gè)客戶至少購買t個(gè)產(chǎn)品，然后這個(gè)客戶可被視為是被覆蓋到的客戶，每一個(gè)被覆蓋的客戶只能被一個(gè)目錄覆蓋到。

將MOC問題定義為如下所示公式(1)-(5)，其含義分別為：公式(1)為適應(yīng)度函數(shù)優(yōu)化公式；公式(2)確保頁面S里的每個(gè)目錄k均含有n個(gè)產(chǎn)品；公式(3)保證目錄k∈Ks覆蓋到每一個(gè)客戶，假設(shè)當(dāng)它對(duì)目錄里至少t個(gè)產(chǎn)品感興趣；公式(4)確保一個(gè)客戶只被一個(gè)目錄所覆蓋；公式(5)是決策變量的整體性要求。C組客戶，表示為c，P組產(chǎn)品，表示為p，Ks組目錄，表示為k，S組頁面，表示為s，目錄大小，表示為n，客戶最小興趣閾值為t，一組頁面的權(quán)重為Ws。

(1)

(2)

(3)

(4)

Xs,k,c,Ys,k,c∈{0,1},?c∈C,p∈P,k∈Ks,s∈S

(5)

決策變量是：

1.2MOC問題舉例

某家公司的顧客交易數(shù)據(jù)庫，如表1所示；表2是產(chǎn)品展示，若頁面取值S=2、目錄K2=7以及目錄大小n=2。對(duì)它進(jìn)行適應(yīng)度值評(píng)估得到9*2+2*1=20(假設(shè)閾值t=2)。

續(xù)表1

客戶產(chǎn)品利益61,2,4,6,973,585,6,7,891,4,5,6,7,8,9102111,2,6,8,9125132,6,8142,3,4,6,7,8,9,10153,4,5162,3,8174,6181,2,5,7,8191,2,3,4,5,7,9203,4,5,6,10

表2 商品展示

2 遺傳算法和主題模型

2.1 遺傳算法

為了更好地實(shí)現(xiàn)協(xié)作推薦，采用遺傳算法(GA)解決以客戶為導(dǎo)向的目錄分割問題(COC)，GA在操作過程中會(huì)根據(jù)觀察到的情況對(duì)變異參數(shù)m進(jìn)行調(diào)整。通過對(duì)COC染色體進(jìn)行轉(zhuǎn)換，將一系列的面向移動(dòng)目錄編碼成一個(gè)單獨(dú)的染色體，如圖1所示。

通過GA來解決COC問題之前，說明2個(gè)重要的術(shù)語，受眾度和適應(yīng)度。受眾度是指對(duì)其中產(chǎn)品感興趣的目錄所覆蓋的客戶數(shù)，以表3和表4為例，假設(shè)有一個(gè)目錄下有3個(gè)產(chǎn)品，如果表3的閾值是2，所覆蓋到的客戶數(shù)會(huì)是4，即客戶4、9、14和19。產(chǎn)品10的受眾度是2，因?yàn)橛锌蛻?和14購買了它，適應(yīng)度指的是對(duì)產(chǎn)品感興趣但未被覆蓋到的客戶數(shù)，在這個(gè)例子里，產(chǎn)品2的適應(yīng)度最高為8。

表3 樣本目錄

表4 受眾度和適應(yīng)度樣本

染色體的大小等于目錄數(shù)與目錄大小之積，每條染色體代表一組目錄單元，通過以COC方式表現(xiàn)出來，可以很容易清除多余的客戶和產(chǎn)品。在隨機(jī)生成產(chǎn)品的初始種群后，GA通過3個(gè)求解過程來獲取最佳目錄：

2.1.1 初始操作

隨機(jī)選兩條染色體，從中選擇一條適應(yīng)度較好的作為一個(gè)父代，另一個(gè)父代以同樣的方式產(chǎn)生，預(yù)留最佳適應(yīng)度值為r的染色體r條進(jìn)行復(fù)制操作。

2.1.2 交叉操作

每個(gè)目錄生成隨機(jī)取自1至n-1里的一個(gè)數(shù)字x；將產(chǎn)品從0位置轉(zhuǎn)移到x位置對(duì)兩條染色體進(jìn)行交叉操作。

2.1.3 變異操作

在這一步，每次迭代時(shí)，從單個(gè)目錄里刪除m個(gè)產(chǎn)品，然后從幾組隨機(jī)產(chǎn)品中選出m個(gè)適應(yīng)度最佳的產(chǎn)品來替換它們。如果這些變異染色體的最新適應(yīng)度比此前的還低，這些染色體就會(huì)恢復(fù)到最初狀態(tài)。變異參數(shù)m會(huì)減少一個(gè)然后再對(duì)染色體進(jìn)行變異操作。如果變異參數(shù)減少至1時(shí)，適應(yīng)度值沒有產(chǎn)生最新最佳數(shù)值，則m會(huì)回歸到初始值。

2.2 創(chuàng)建主題模型

本文通過主題建模概念來改進(jìn)GA，采用LDA來創(chuàng)建主題模型，其主要思路在于分析哪些單詞屬于哪些主題范疇，然后進(jìn)行對(duì)應(yīng)分配。為降低復(fù)雜度，LDA并不考慮單詞順序，它涵蓋了3個(gè)等級(jí)即主題、文檔和單詞。而本文所研究的 LDA模型是一種生成模型，也就是說，與直接根據(jù)觀察到的文檔來進(jìn)行預(yù)測(cè)不同，LDA首先假設(shè)了產(chǎn)生文檔的一個(gè)過程，然后根據(jù)觀察到的文檔，來預(yù)測(cè)背后的產(chǎn)生過程是怎樣的。LDA 假設(shè)所有的文檔存在K個(gè)主題，要生成一篇文檔，首先生成該文檔的一個(gè)主題分布，然后再生成詞的集合；要生成一個(gè)詞，需要根據(jù)文檔的主題分布隨機(jī)選擇一個(gè)主題，然后根據(jù)主題中詞的分布隨機(jī)選擇一個(gè)詞。

假設(shè)K維向量θ是主題的先驗(yàn)分布的參數(shù)，K×V的矩陣β是主題中詞的分布的參數(shù)(V為詞的總數(shù))，即βij=p(wj|zi)=第i個(gè)主題中出現(xiàn)詞Wj的概率，那么生成一個(gè)文檔的主題分布，再生成N個(gè)主題，進(jìn)而得到這篇文檔的N個(gè)詞的概率可以表示為：

p=(θ,z,w|α,β)=p(θ|α)

(6)

在單文檔中N是一個(gè)單詞數(shù)，α是V的參數(shù)，θ是文檔中每個(gè)主題發(fā)生的概率，β是在單個(gè)主題中一個(gè)固定的詞匯分配，Zn是第nth個(gè)主題。

將LDA和GA進(jìn)行組合解決MOC問題，設(shè)計(jì)了新算法LDA-GA。LDA-GA的步驟如下。

首先，隨機(jī)產(chǎn)生的幾個(gè)染色體使它們的適應(yīng)度分開。然后，保留適應(yīng)度前50%的染色體并將其余染色體強(qiáng)制淘汰。其次，將客戶的GA偏好，采用隨機(jī)從最相似的偏好選擇替代產(chǎn)品(主題)。最后，算法的停止條件是當(dāng)?shù)_(dá)到了特定的時(shí)間。

(7)

表5 尋找顧客偏好的說明

3 實(shí)驗(yàn)與討論

為了測(cè)試LDA-GA算法的有效性，搭建了試驗(yàn)床，硬件環(huán)境是主頻雙核2.13GHz，內(nèi)存為4GB，軟件采用matlab2008a編程語言，對(duì)設(shè)計(jì)的MOC采用LDA-GA和GA兩個(gè)算法進(jìn)行性能比較， 實(shí)驗(yàn)數(shù)據(jù)采用電子商務(wù)下的真實(shí)數(shù)據(jù)。

3.1 數(shù)據(jù)預(yù)處理

本文的數(shù)據(jù)來自一家匿名零售超市，該數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)，實(shí)驗(yàn)的交易數(shù)據(jù)近10萬條，其中包含大約16469個(gè)商品和88162位顧客，平均每位顧客對(duì)10.3個(gè)產(chǎn)品感興趣。獲取的原始數(shù)據(jù)(部分)，如表6所示。

表6 實(shí)驗(yàn)原始數(shù)據(jù)(部分)

鑒于目前MOC問題還沒得到解決，本文將LDA-GA算法與GA算法進(jìn)行MOC設(shè)計(jì)問題對(duì)比研究，進(jìn)行30次生成操作。本文選取初始種群為N/10=100，交叉率pc=0.5，變異率pm=0.01。算法停止條件：(1)達(dá)到最大迭代次數(shù)Stop_iter=10000；(2)相同最優(yōu)值保持輪數(shù)Stop_interval=10。由圖2可知LDA-GA較GA具有更好的適應(yīng)度。

3.2 實(shí)驗(yàn)對(duì)比

本文分別應(yīng)用LDA-GA和GA算法來解決MOC問題?；谀M經(jīng)濟(jì)交易原理，它能證實(shí)這些方法在解決MOC問題的優(yōu)劣。此外還對(duì)MOC的許多特征進(jìn)行分析，根據(jù)表6實(shí)驗(yàn)原始數(shù)據(jù)(部分)，目錄數(shù)、目錄大小和閥值等參數(shù)來評(píng)估算法的有效性。

MOC的標(biāo)準(zhǔn)檢測(cè)見公式(8)。這些表格體現(xiàn)了LDA-GA性能優(yōu)越，但顧客數(shù)和產(chǎn)品數(shù)均要維持較大，那是因?yàn)長(zhǎng)DA是一個(gè)概率模型。如果沒有足夠的交易量來評(píng)估顧客的喜好，LDA的效果就不那么理想。

Gap=(fitnessLDA_GA-fitnessGA)/fotmessGA

(8)

根據(jù)產(chǎn)品的銷售額，對(duì)限制在300及無限制這兩種情況做了比較。銷售額在300以上的產(chǎn)品所在的目錄可以有高適應(yīng)度，LDA-GA在解決大體積的目錄問題時(shí)比GA更有優(yōu)勢(shì)。反之在閾值較小時(shí)，如果產(chǎn)品的銷售額超出300，GA的性能更佳。圖3-5提供了兩種算法在目錄數(shù)、目錄大小及適應(yīng)度的閾值變化方面的不同結(jié)果。

對(duì)淘寶網(wǎng)和亞馬遜的APP設(shè)計(jì)進(jìn)行分析，如表7所示。根據(jù)它們對(duì)產(chǎn)品呈現(xiàn)的設(shè)計(jì)結(jié)構(gòu)不同，分別來檢測(cè)兩種算法的效果。圖6說明淘寶網(wǎng)展示方式具有更高的適應(yīng)度，由于用戶界面設(shè)計(jì)風(fēng)格的不同，所得到的適應(yīng)度值也不同，適應(yīng)度值高說明可以以少數(shù)頁面覆蓋到更多客戶而增加銷售額。反之，適應(yīng)度值低說明其市場(chǎng)策略面向的是一些特定的客戶群，以此來提升銷售額。

表7 淘寶網(wǎng)和亞馬遜設(shè)計(jì)

(a)淘寶商品展示

表8是這兩種算法對(duì)兩家公司分別進(jìn)行10輪實(shí)驗(yàn)后得出的適應(yīng)度平均值。然后，利用閾值T測(cè)試來發(fā)現(xiàn)這兩種算法在R程序上的不同。對(duì)每個(gè)公司，用這兩種算法的10次實(shí)驗(yàn)結(jié)果作為樣品。淘寶網(wǎng)和亞馬遜的p值都偏小，所以不做無效假設(shè)。統(tǒng)計(jì)實(shí)驗(yàn)得出這兩種算法的適應(yīng)度值不同，LDA-GA對(duì)MOC問題有更好的適應(yīng)度值。

表8 淘寶網(wǎng)和亞馬遜的統(tǒng)計(jì)測(cè)試

4 結(jié)語

針對(duì)移動(dòng)設(shè)備向用戶推薦產(chǎn)品時(shí)受限于尺寸的問題，目前普遍采用個(gè)性化協(xié)作推薦算法來實(shí)現(xiàn)開發(fā)面向移動(dòng)目錄(MOC)，但是傳統(tǒng)的方法存在大數(shù)據(jù)環(huán)境下適應(yīng)度不高、協(xié)作能力差等不足。為解決此問題，本文首先將主題建模算法與遺傳算法相結(jié)合開發(fā)出LDA-GA算法，在此基礎(chǔ)上做了實(shí)驗(yàn)分析，實(shí)驗(yàn)結(jié)果表明：LDA-GA算法在解決MOC的產(chǎn)品多和客戶量大的情況下，適應(yīng)度更高，受眾客戶更廣，產(chǎn)品推介效果更好。

[1] MAGRATH V,MCCORMICK H.Marketing design elements of mobile fashion retail apps[J].Journal of Fashion Marketing and Management,2013,17(1):115-134.

[2] ESTER M,GE R,JIN W,et al.A microeconomic data mining problem:customer-oriented catalog segmentation[C]∥Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining,Aug 22-25,2004,New York,N Y.SIGKDD,2004:557-562.

[3] BLEI D M,NG A Y,JORDAN M I.Latent dirichlet allocation[J].Journal of Machine Learning Research,2003,3(1): 993-1022.

[4] MAHDAVI I,MOVAHEDNEJAD M,ADBESH F.Designing customer-oriented catalogs in e-CRM using an effective self-adaptive genetic algorithm[J].Expert Systems with Applications,2011,38(1):631-639.

[5] KLEINBERG J,PAPADIMITRIOU C,RAGHAVAN P.Segmentation problems[C]∥Proceedings of the thirtieth annual ACM symposium on Theory of computing,May 24-26,1998,Dallas,Texas:473-482.

[6] KLEINBERG J,PAPADIMITRIOU C,RAGHAVAN P.A microeconomic view of data mining[J].Data Mining and Knowledge Discovery,1998,2(4):311-324.

[7] XU D C,YE Y Y.Approximating the 2-catalog segmentation problem using semidefinite programming relaxations[J].Optimization Methods and Software,2002,18(6):705-719.

[8] AMIRI A.Customer-oriented catalog segmentation:effective solution approaches[J].Decision Support Systems,2006,42(3):1860-1871.

[9] 朱彥廷.自適應(yīng)遺傳算法[J].重慶三峽學(xué)院學(xué)報(bào),2014,30(3):41-44.

[責(zé)任編輯、校對(duì)：周 千]

Research on Mobile-oriented Catalog Optimization Based on LDA-GA Algorithm

LIANGPan

(School of Mechanical and Electrical Engineering,Chengdu Aeronautic Polytechnic,Chengdu 610100,China)

To solve the problem that mobile devices are subject to the limitation of sizes when recommending products to users,the individualized collaboration is recommended to realize the development of mobile-oriented catalog (MOC).However,traditional methods are of low adaptability and poor collaboration under the environment of big data.To solve the problem,the topic modeling algorithm and genetic algorithm are firstly combined to develop a LDA-GA algorithm;secondly,the attractive and collaborative recommendation catalog is designed;finally,MOC is applied in Amazon APP and Taobao.com APP for comparative analysis and optimization.The experimental results show that the LDA-GA algorithm is more adaptive,more cooperative and more effective in the environments of a large number of users and product data.

mobile-oriented catalog;Latent Dirichlet allocation;topic modeling;genetic algorithm

2016-10-26

四川省教育廳重點(diǎn)項(xiàng)目(17ZA0520)

梁潘(1978-),男，四川廣漢人，副教授，主要從事計(jì)算機(jī)軟件與網(wǎng)絡(luò)安全研究。

TP393

A

1008-9233(2017)01-0077-06