西安電子科技大學(xué)經(jīng)濟(jì)管理學(xué)院 田 亮 宋 薇

東軟集團(tuán)大連有限 公司 黃少冰

1.引言

近年來(lái)，隨著移動(dòng)互聯(lián)網(wǎng)的迅速發(fā)展，特別是國(guó)內(nèi)3G牌照發(fā)放后，移動(dòng)互聯(lián)網(wǎng)用戶增長(zhǎng)迅速。根據(jù)中國(guó)互聯(lián)網(wǎng)絡(luò)信息中心(CNNIC)發(fā)布的《第30此中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告》顯示，2012年上半年中國(guó)互聯(lián)網(wǎng)電腦網(wǎng)民規(guī)模達(dá)到5.38億，而手機(jī)網(wǎng) 民數(shù)量將達(dá)到3.88億。據(jù)DDCI互聯(lián)網(wǎng)數(shù)據(jù)中心預(yù)測(cè)，到2013年中國(guó)手機(jī)網(wǎng)民將達(dá)7.2億，首次超越電腦網(wǎng)民[1]。隨之而來(lái)的是移動(dòng)互聯(lián)網(wǎng)上各類信息的爆炸式增長(zhǎng)，使得人們通過(guò)移動(dòng)網(wǎng)絡(luò)獲取信息更加方便的同時(shí)，也使得人們獲取有價(jià)值的信息愈發(fā)的困難。

為解決Internet上信息淹沒(méi)的現(xiàn)狀，個(gè)性化推薦技術(shù)得到了廣泛的應(yīng)用。針對(duì)移動(dòng)互聯(lián)網(wǎng)的特殊性，本文把傳統(tǒng)Internet上個(gè)性化推薦技術(shù)應(yīng)用到移動(dòng)互聯(lián)網(wǎng)上，提出了移動(dòng)個(gè)性化推薦的離 線解決方案，并且設(shè)計(jì)了基于J2ME的移動(dòng)個(gè)性化推薦系統(tǒng)。

2.A TC與CF結(jié)合的推薦模型

2.1 相關(guān)技術(shù)概述

為解決文本分類中人為因素的影響，自動(dòng)文本分類（Automatic Text Categorization）技術(shù)得到了快速的發(fā)展與應(yīng)用。目前比較常用的有KNN，樸素貝葉斯分類，SVM等分類方法。這些方法都是建立在統(tǒng)計(jì)學(xué)的基礎(chǔ)上，通過(guò)特征提取來(lái)標(biāo)注文本文檔，建立文檔模型后不同的方法應(yīng)用不同的分類器來(lái)進(jìn)行文本分來(lái)處理。文本分類建立在大量文檔的基礎(chǔ)之上，從而消除了不同的人對(duì)文檔文類不同的分歧，使得分類過(guò)程不受人為因素的影響。

協(xié)同過(guò)濾（Collaborative Filtering，CF），又稱協(xié)作型過(guò)濾，是在信息過(guò)濾與信息發(fā)現(xiàn)領(lǐng)域非常受歡迎的技術(shù)。一個(gè)協(xié)作型過(guò)濾算法通常的做法是對(duì)一大群人進(jìn)行搜索，從中找出與當(dāng)前用戶喜好相同的一小群人，并且對(duì)這些人的偏好內(nèi)容進(jìn)行考察，將結(jié)果組合起來(lái)構(gòu)造出一個(gè)經(jīng)過(guò)排名的推薦列表[2]。協(xié)同過(guò)濾技術(shù)分為基于用戶相似性的協(xié)同過(guò)濾（User-based），基于推薦項(xiàng)目的協(xié)同過(guò)濾（Item-based）與基于模型的協(xié)同過(guò)濾（Model-based）三種基本方式。Userbased協(xié)同過(guò)濾是發(fā)現(xiàn)相似用戶群體，根據(jù)相似用戶的瀏覽記錄來(lái)進(jìn)行興趣發(fā)現(xiàn)并推薦給用戶；Item-based協(xié)同過(guò)濾計(jì)算推薦項(xiàng)目之間的相似性，把與用戶以前瀏覽的項(xiàng)目相似的項(xiàng)目推薦給用戶；Modelbased協(xié)同過(guò)濾首先建立個(gè)性化推薦的數(shù)學(xué)模型，根據(jù)數(shù)學(xué)模型來(lái)計(jì)算推薦集。

本文主要應(yīng)用樸素貝葉斯分類器與基于項(xiàng)目的協(xié)同過(guò)濾算法來(lái)構(gòu)建移動(dòng)網(wǎng)絡(luò)的個(gè)性化推薦系統(tǒng)。

2.2 個(gè)性化推薦模型

基于J2ME的移動(dòng)網(wǎng)絡(luò)個(gè)性化信息推薦系統(tǒng)整體架構(gòu)如圖1所示，系統(tǒng)模型基于C/S結(jié)構(gòu)設(shè)計(jì)，客戶端采用J2ME技術(shù)實(shí)現(xiàn)手機(jī)客戶端信息瀏覽系統(tǒng)，服務(wù)器端采用Servlet實(shí)現(xiàn)。

由圖1可以看出推薦模型可以分為四個(gè)主要部分：

1）用戶信息采集分為顯性的信息采集與隱性信息采集方式。顯性的信息采集方式為在用戶的終端瀏覽界面設(shè)置信息反饋欄目，在該欄目中用戶可以設(shè)置自己的使用偏好信息；隱性的信息采集方式為根據(jù)用戶對(duì)信息的瀏覽時(shí)間，對(duì)信息是否保存，對(duì)信息是否轉(zhuǎn)發(fā)等情況對(duì)信息內(nèi)容做出隱性的評(píng)價(jià)。本文使用5分制規(guī)則，對(duì)信息保存，轉(zhuǎn)發(fā)評(píng)分為5分，根據(jù)用戶對(duì)信息瀏覽時(shí)間的長(zhǎng)短為信息設(shè)置1-5分的分值。

2）信息發(fā)布系統(tǒng)主要負(fù)責(zé)添加推薦信息，在此過(guò)程中使用樸素貝葉斯文本分類器對(duì)文本類別進(jìn)行劃分。

3）個(gè)性化推薦引擎采用基于用戶背景信息分類與歷史記錄可信度加權(quán)的Item-Based協(xié)同過(guò)濾算法產(chǎn)生推薦信息集。

4）終端系統(tǒng)采用基于J2ME技術(shù)實(shí)現(xiàn)，提供信息瀏覽與用戶偏好采集功能等。

2.3 樸素貝葉斯文本分類

文本分類是將未知的文本類型劃分到規(guī)定好的類別中，從而降低人為因素的影響。樸素貝葉斯分類以古典數(shù)學(xué)理論為基礎(chǔ)，分類效率穩(wěn)定，同時(shí)模型構(gòu)建簡(jiǎn)單，性能優(yōu)越。因此本文選取樸素貝葉斯分類器作為文本分類的工具。

本文使用的基于樸素貝葉斯分類的文本分類過(guò)程如下：

（1）訓(xùn)練文本的向量空間表示

生成向量空間模型的步驟有文本分詞處理，除去停用詞，特征選擇等。經(jīng)過(guò)各個(gè)階段，最終將確定一組特征詞作為特征詞空間W={w1,w2,w3,…,wm}，w表示特征詞。將文本映射到該組特征詞空間，使文本的表示形如T(A)={pA1,pA2,pA3,…,pAm}，pAi為文檔頻率法表示詞wi在文檔A上的權(quán)重。pAi還可以通過(guò)信息增益法，開(kāi)方擬合檢驗(yàn)等其他方法表示[3]。

（2）計(jì)算每個(gè)特征詞所屬類別的概概率分布

計(jì)算每個(gè)特征詞屬于每個(gè)類別的概率，具體計(jì)算方法：分別計(jì)算每類文件的質(zhì)心，并計(jì)算出每個(gè)詞能夠代表每個(gè)類別的概率，最終形成如表1所示的特征詞-文本類別對(duì)應(yīng)矩陣。關(guān)于文件集質(zhì)心的計(jì)算可以

[4][5]。

（3）向量空間模型的形成

根據(jù)已選定的特征詞空間，將待分類文本映射到特征詞空間中，使其表示為向量空間形式：T(X)={pX1,pX2,pX3…pXm}。

（4）根據(jù)特征詞的概率分布情況，計(jì)算待分類文本所屬類別的概率

確定待分類文本T(X)屬于分類Ck（Ck∈{C1,C2,C3…Cn}）的概率R(k)，R(k)的計(jì)算方法如公式1所示。

（5）確定待分類文本的類別

按（4）中所提計(jì)算公式分別計(jì)算待分類文本屬于每個(gè)類別的概率R(k)，具有最大值R(k)的類別即為該待分類文本的最終分類。

2.4 基于用戶分類與記錄可信度加權(quán)的協(xié)同過(guò)濾算法

表1 特征詞——類別對(duì)應(yīng)概率分布

圖1 基于J2ME的移動(dòng)網(wǎng)絡(luò)個(gè)性化推薦模型

圖2 軟件層次模型

圖3 客戶端軟件流程圖

本文提出的改進(jìn)的協(xié)同過(guò)濾算法與傳統(tǒng)的協(xié)同過(guò)濾算法的區(qū)別主要有兩點(diǎn)：依據(jù)用戶的背景信息進(jìn)行分類與用戶的歷史記錄信息加權(quán)。按用戶背景信息進(jìn)行過(guò)濾的想法源于一個(gè)假設(shè)：相同背景信息的用戶具有相似的信息需求，根據(jù)用戶的背景信息去除關(guān)聯(lián)度小的用戶群體記錄，可以降低歷史評(píng)分記錄的維數(shù)，提高程序的運(yùn)行速度；考慮到用戶的偏好可能隨著時(shí)間的推移而變換，歷史的評(píng)分記錄不能真實(shí)反映當(dāng)前的用戶偏好，因此對(duì)用戶的歷史評(píng)分記錄進(jìn)行加權(quán)處理，使得距離當(dāng)前時(shí)間較近的評(píng)分記錄擁有較高的權(quán)限，這樣既考慮歷史記錄的影響，又可以突出最新評(píng)論的真實(shí)性。

（1）用戶分類方法

對(duì)用戶進(jìn)行分類，就是要篩選出影響用戶獲取信息類別的關(guān)鍵背景信息，又稱為關(guān)鍵因素。以獲得的關(guān)鍵因素作為分類標(biāo)準(zhǔn)對(duì)用戶進(jìn)行分類。

用戶分類主要有三個(gè)步驟：

1）統(tǒng)計(jì)用戶最關(guān)注信息的所屬類別，也就是用戶的偏好情況。

2）計(jì)算出用戶信息基本信息集的信息熵。

3）計(jì)算用戶基本信息中每個(gè)屬性的信息增益，從中選擇信息增益最大的屬性作為影響用戶獲取信息的關(guān)鍵因素，并以此關(guān)鍵因素作為用戶背景信息分類標(biāo)準(zhǔn)來(lái)進(jìn)行用戶分類。

圖4 系統(tǒng)運(yùn)行界面

當(dāng)用戶背景信息分類量較大，或者用戶歷史記錄信息量非常大時(shí)，可以采用多個(gè)用戶背景信息組合的方法獲取關(guān)鍵因素。信息增益與信息熵的相關(guān)用法可以參考ID3分類算法[6]，此外還有一些基于信息增益的特征選取方法，文獻(xiàn)[7]給出了一種改進(jìn)的特征選取方法。

（2）信息相似度計(jì)算

研究發(fā)現(xiàn)“用戶的最新評(píng)價(jià)信息擁有最高的權(quán)重，而距離當(dāng)前時(shí)間越遠(yuǎn)的記錄擁有的權(quán)值越小”，項(xiàng)目加權(quán)便是建立在這個(gè)基礎(chǔ)上進(jìn)行的。由此可知項(xiàng)目可信度函數(shù)具有單調(diào)遞增性。另外，為了確保近期不同用戶的評(píng)分信息具有大致相同的權(quán)值，可信度函數(shù)應(yīng)是一個(gè)凸函數(shù)。所以，可信度函數(shù)要綜合考慮長(zhǎng)期情況下數(shù)據(jù)權(quán)重的差別性和短期內(nèi)數(shù)據(jù)權(quán)重的相似性。最終設(shè)定可信度函數(shù)為：以項(xiàng)目排列順序?yàn)樽宰兞康暮瘮?shù)f(Sui)，1≤Sui≤M，M為記錄總數(shù)，并且0＜f(Sui)≤1。根據(jù)以上條件我們選擇對(duì)數(shù)函數(shù)作為可信度函數(shù)，并將函數(shù)進(jìn)行歸一化處理。這里設(shè)置可信度函數(shù)為如公式2所示：

從公式1中可見(jiàn)f(Sui)值域?yàn)閇0,1]，符合上述描述條件。

計(jì)算項(xiàng)目相關(guān)相似度的方法有很多，包括余弦相似度法，Pearson相關(guān)性[8]等。本文采用余弦相似度法來(lái)獲取相似性，公式3為改進(jìn)的余弦相似度公式[9]。

其中，U表示項(xiàng)目Ii,Ij已經(jīng)評(píng)價(jià)的用戶集；Vui為用戶u對(duì)Ii項(xiàng)目的評(píng)價(jià)分?jǐn)?shù)；Sui為用戶u對(duì)Ii項(xiàng)目評(píng)價(jià)記錄的標(biāo)識(shí)序號(hào)；f(Sui)則表示用戶u針對(duì)Ii項(xiàng)目評(píng)價(jià)記錄所占的權(quán)值。

（3）改進(jìn)的協(xié)同過(guò)濾算法描述

輸入：推薦用戶u基本信息，所有用戶背景信息及歷史評(píng)論信息。

輸出：對(duì)用戶u的Top-N推薦

具體步驟：

1）找出影響用戶分類的關(guān)鍵因素

2）以1）中獲得的關(guān)鍵因素為基礎(chǔ)，選取所屬類別相同的用戶群體。根據(jù)分類規(guī)則和個(gè)體用戶的基本資料獲取與該用戶所屬類別相同的用戶群組。

3）獲取用戶群的歷史記錄，按時(shí)間排序。

4）根據(jù)3）所得的記錄順序進(jìn)行記錄可信度加權(quán)，獲得評(píng)分矩陣。

5）在用戶參與評(píng)論的條目中搜尋未經(jīng)用戶評(píng)論條目的最近鄰居集。

6）預(yù)測(cè)用戶對(duì)未瀏覽和未評(píng)論過(guò)的條目的評(píng)價(jià)情況，生成推薦集。獲取評(píng)價(jià)排序的TopN條信息推薦給用戶。

3.移動(dòng)個(gè)性化推薦系統(tǒng)設(shè)計(jì)

3.1 整體架構(gòu)

如圖2給出了基于J2ME的移動(dòng)網(wǎng)絡(luò)個(gè)性化信息推薦系統(tǒng)的層次模型，主要分為客戶端數(shù)據(jù)獲取層，Web層，數(shù)據(jù)操縱層，數(shù)據(jù)存儲(chǔ)層?？蛻舳酥饕?fù)責(zé)向終端用戶顯示推薦信息并且獲取用戶的顯性輸入的信息和用戶隱性輸入的信息；Web層主要由Servlet，JSP實(shí)現(xiàn)，負(fù)責(zé)向系統(tǒng)的數(shù)據(jù)庫(kù)中添加推薦信息，并且提供Servlet訪問(wèn)接口供J2ME客戶端程序以HTTP/HTTPS方式獲取或添加信息；數(shù)據(jù)操縱層主要是一些JAVA BEAN，這些JAVA BEAN封裝了數(shù)據(jù)操縱API，向外界提供統(tǒng)一的訪問(wèn)接口；數(shù)據(jù)存儲(chǔ)層主要應(yīng)用Oracle 10g數(shù)據(jù)庫(kù)管理軟件。

3.2 客戶端程序流程

客戶端通過(guò)一個(gè)主MIDlet程序啟動(dòng)，提供了推薦信息顯示，信息收藏，信息檢索，用戶個(gè)人偏好反饋等主要功能模塊，主要功能的程序流程圖如圖3所示。首次使用客戶端程序需要注冊(cè)用戶名、密碼等信息，以后應(yīng)用可以直接利用保存在J2ME記錄管理系統(tǒng)（RMS）中的個(gè)人信息進(jìn)行登錄，經(jīng)過(guò)驗(yàn)證成功后的用戶可以進(jìn)行相關(guān)操作。

3.3 服務(wù)器端程序結(jié)構(gòu)

服務(wù)器端程序主要模塊為文本分類模塊，個(gè)性化推薦模塊。為降低用戶等待時(shí)間，這兩個(gè)模塊的運(yùn)行均采用離線運(yùn)行的模式執(zhí)行。即設(shè)定固定的運(yùn)行時(shí)間或手動(dòng)運(yùn)行來(lái)更新特征詞空間，概率分布信息，以及用戶的分類屬性，推薦集信息等。

文本分類模塊負(fù)責(zé)將文本分類相關(guān)的數(shù)據(jù)信息保存在文本文件或數(shù)據(jù)庫(kù)中，以便輸入文本時(shí)無(wú)需再次計(jì)算相關(guān)參數(shù)，可以直接進(jìn)行分類運(yùn)算，提高實(shí)時(shí)性。

個(gè)性化信息推薦模塊負(fù)責(zé)產(chǎn)生與維護(hù)用戶對(duì)用戶的推薦信息集，該過(guò)程要保證推薦信息的新穎性，因此需要在后臺(tái)啟動(dòng)一個(gè)運(yùn)行線程，實(shí)時(shí)更新推薦集信息。

3.4 客戶端-服務(wù)器通信方法

JAVA ME API提供了J2ME MIDlet程序與服務(wù)器端通信兩種方法：基于socket連接的方式和基于超文本傳輸協(xié)議的HTTP通信方式，本文使用HTTP方式實(shí)現(xiàn)客戶端-服務(wù)器端通信。客戶端與服務(wù)器通過(guò)HTTP輸入/輸出流的方式進(jìn)行數(shù)據(jù)交換，程序的一端使用特定的編碼格式向輸出流（OutputStream）中寫(xiě)數(shù)據(jù)，在另一端打開(kāi)輸入流(DataInputStream)，并且從流輸入流中讀取數(shù)據(jù)，解碼后完成信息的傳遞。下面給出了一個(gè)Post方式提交信息的Http方式連接服務(wù)器的代碼片段。

4.系統(tǒng)仿真實(shí)驗(yàn)結(jié)果

系統(tǒng)仿真環(huán)境：采用HP Compaq dx7408 PC，開(kāi)發(fā)軟件MyEclipse 7.0，Oracle 10g，Wireless Toolkit 2.5.2。

在上文提出的移動(dòng)個(gè)性化信息推薦模型的基礎(chǔ)上，本文作者在實(shí)驗(yàn)室環(huán)境下設(shè)計(jì)開(kāi)發(fā)了一種基于J2ME的移動(dòng)個(gè)性化信息推薦原型系統(tǒng)，系統(tǒng)運(yùn)行界面如圖4所示。

為測(cè)試系統(tǒng)推薦的正確性，在實(shí)驗(yàn)室六名志愿者的參與下，根據(jù)他們前四天的瀏覽記錄推薦第五天的偏好信息，推薦正確率在80%左右。

5.結(jié)束語(yǔ)

本文為解決移動(dòng)網(wǎng)絡(luò)上的信息過(guò)載狀況提出了一種解決方案，設(shè)計(jì)實(shí)現(xiàn)了基于J2ME的移動(dòng)網(wǎng)絡(luò)個(gè)性化推薦原型系統(tǒng)，并且取得了較好的推薦效果。由于時(shí)間有限，該原型系統(tǒng)在推薦效率和通用性方面仍然有待改進(jìn)。

參考文獻(xiàn)

[1]工業(yè)和信息化部運(yùn)行監(jiān)測(cè)協(xié)調(diào)局[EB/OL].http://yxj.miit.gov.cn/n11293472/n11295057/n11298508/14741971.html.

[2]Toby Segaram.Programming Collaborative Intelligence[M].O’Reilly Media,2007(8).

[3]陸玉昌,魯明羽,李凡,周立柱.向量空間法中單詞權(quán)重函數(shù)的分析和構(gòu)造[J].計(jì)算機(jī)研究與應(yīng)用,2002,10(10):1205-1210.

[4]Lertnattee V,Theeramunkong T.Effect of Term Distributions on Centroid-based Text Categorization[J].Information .ciences,2004,158(1):89-115.

[5]E Han,G Karypis.Centroid-based document classi fi cation:Annlysis & experimental results.In: European Conf on Principles of Data Mining and Knowledge Discovery(PKDD).Berlin:Springer-Verlag,2000:424-431.

[6]J.Han and M.Kamber.Data Mining:Concept and techniques Second Edition[M].北京:機(jī)械工業(yè)出版社,2006(4).

[7]朱顥東,鐘勇.基于改進(jìn)的ID3信息增益的特征選擇方法[J].計(jì)算機(jī)工程,2010,4(8):37-39.

[8]劉枚蓮,從曉琪,楊懷珍.改進(jìn)鄰居集合的個(gè)性化推薦算法[J].計(jì)算機(jī)工程,2009,6(11):196-168.

[9]黃少冰.基于J2ME的移動(dòng)網(wǎng)絡(luò)個(gè)性化信息推薦研究[D].西安電子科技大學(xué)(碩士論文),2010.