梁 潘

(成都航空職業(yè)技術學院 機電工程學院，四川 成都 610100)

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

梁 潘

(成都航空職業(yè)技術學院 機電工程學院，四川 成都 610100)

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

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

0 引言

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

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

1 MOC問題界定和公式化

1.1 MOC問題的定義

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

將MOC問題定義為如下所示公式(1)-(5)，其含義分別為：公式(1)為適應度函數(shù)優(yōu)化公式；公式(2)確保頁面S里的每個目錄k均含有n個產(chǎn)品；公式(3)保證目錄k∈Ks覆蓋到每一個客戶，假設當它對目錄里至少t個產(chǎn)品感興趣；公式(4)確保一個客戶只被一個目錄所覆蓋；公式(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。對它進行適應度值評估得到9*2+2*1=20(假設閾值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 遺傳算法

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

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

表3 樣本目錄

表4 受眾度和適應度樣本

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

2.1.1 初始操作

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

2.1.2 交叉操作

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

2.1.3 變異操作

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

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

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

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

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

(6)

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

將LDA和GA進行組合解決MOC問題，設計了新算法LDA-GA。LDA-GA的步驟如下。

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

(7)

表5 尋找顧客偏好的說明

3 實驗與討論

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

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

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

表6 實驗原始數(shù)據(jù)(部分)

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

3.2 實驗對比

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

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

Gap=(fitnessLDA_GA-fitnessGA)/fotmessGA

(8)

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

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

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

(a)淘寶商品展示

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

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

4 結(jié)語

針對移動設備向用戶推薦產(chǎn)品時受限于尺寸的問題，目前普遍采用個性化協(xié)作推薦算法來實現(xiàn)開發(fā)面向移動目錄(MOC)，但是傳統(tǒng)的方法存在大數(shù)據(jù)環(huán)境下適應度不高、協(xié)作能力差等不足。為解決此問題，本文首先將主題建模算法與遺傳算法相結(jié)合開發(fā)出LDA-GA算法，在此基礎上做了實驗分析，實驗結(jié)果表明：LDA-GA算法在解決MOC的產(chǎn)品多和客戶量大的情況下，適應度更高，受眾客戶更廣，產(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] 朱彥廷.自適應遺傳算法[J].重慶三峽學院學報,2014,30(3):41-44.

[責任編輯、校對：周 千]

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

四川省教育廳重點項目(17ZA0520)

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

TP393

A

1008-9233(2017)01-0077-06