基于用戶評價的鐵路旅客信息服務(wù)推薦方法研究

李宗凱，李洪研，肖 坦，呂曉鵬，劉 禹

（1.通號通信信息集團有限公司 北京 100071；2.北京航空航天大學 計算機學院，北京 100083）

基于用戶評價的鐵路旅客信息服務(wù)推薦方法研究

李宗凱1，李洪研1，肖 坦1，呂曉鵬1，劉 禹2

（1.通號通信信息集團有限公司 北京 100071；2.北京航空航天大學 計算機學院，北京 100083）

對用戶提供個性化的服務(wù)推薦是鐵路信息服務(wù)系統(tǒng)提高服務(wù)質(zhì)量的手段之一，傳統(tǒng)的協(xié)同過濾推薦算法的應(yīng)用過程中，當用戶和項目數(shù)目較大時，用戶-項目矩陣極度稀疏且用戶評價向量的維度不同，傳統(tǒng)的相似性比較方法無法很好地處理此類問題，降低了推薦算法的推薦質(zhì)量。本文提出基于云模型的相似性度量方法，使用云模型霧化特征對逆向云算法進行補充，對于給定的數(shù)據(jù)向量，可以將其轉(zhuǎn)換成云，使用云模型數(shù)字特征進行數(shù)據(jù)表示。云模型的期望和熵決定數(shù)據(jù)對應(yīng)概念的內(nèi)涵相似度，熵和超熵可以反映其外延相似度，比較云之間的相似度可得到數(shù)據(jù)本身的相似程度。應(yīng)用MovieLens標準測試數(shù)據(jù)集，與傳統(tǒng)的相似性度量方法比較，實驗結(jié)果表明，基于云模型相似性度量的協(xié)同過濾推薦算法推薦質(zhì)量高，可為鐵路信息化服務(wù)推薦提供技術(shù)積累與指導。

鐵路運輸；旅客服務(wù)；云模型；逆向云算法；協(xié)同過濾推薦

先進的旅客信息系統(tǒng)是智能交通系統(tǒng)中的一個重要組成部分。信息發(fā)布是其中直接和出行者相聯(lián)系的一個環(huán)節(jié)，在最主要的幾種信息發(fā)布技術(shù)中，互聯(lián)網(wǎng)和移動終端無疑是最現(xiàn)代也是最能提供個性化功能的兩種方式[11]。軟件服務(wù)的應(yīng)用過程形成了大量的用戶行為與評價數(shù)據(jù)，如何從中挖掘和發(fā)現(xiàn)有用的知識以提供個性化服務(wù)成為一個有意義的研究課題。服務(wù)使用者希望服務(wù)系統(tǒng)能夠自動地把用戶最感興趣的服務(wù)推薦出來[1]。軟件應(yīng)用的發(fā)展過程中，SOA、SaaS等理念的提出，將軟件作為服務(wù)進行展現(xiàn)，云計算更是強調(diào)對終端用戶按需服務(wù)[2]。為了給用戶提供滿足個體需求的產(chǎn)品與服務(wù)，推薦系統(tǒng)需要提供精確而又快速的推薦，研究者提出了多種推薦算法[3～6]。

最近鄰協(xié)同過濾推薦是當前最成功的推薦技術(shù)[7]，相似性計算是協(xié)同過濾推薦算法中最關(guān)鍵步驟，而用戶數(shù)目和項目數(shù)據(jù)急劇增加，導致用戶評分數(shù)據(jù)的極端稀疏性[7]，由于用戶的流動性，面向鐵路的信息化服務(wù)中評價數(shù)據(jù)稀疏的問題更加突出。不同用戶對不同的項目提供了不同維度的評價向量，傳統(tǒng)相似性度量方法均存在各自的弊端。使得計算得到的目標用戶的最近鄰居不準確，推薦系統(tǒng)的推薦質(zhì)量下降。文獻[8]提出通過奇異值分解（SVD）減少項目空間維數(shù)的方法，但降維會導致信息損失，使得該方法在項目空間維數(shù)較高的情況下難以保證推薦效果[9]。

本文以云模型[13]為基礎(chǔ)，提出了一個新的相似性度量方法，解決兩個方面的問題：

（1）將定量的評分數(shù)據(jù)映射為云，通過本文提出的改進逆向云算法，使用云模型的3個數(shù)字特征表示定量數(shù)據(jù)，克服數(shù)據(jù)缺失、稀少、不同維度等因素對相似性比較帶來的負面影響；

（2）定義云模型的相似性比較規(guī)則，通過云模型數(shù)字特征比較云相似性，從而得到原始數(shù)據(jù)的相似性度量值。最后，給出使用云模型相似性進行軟件服務(wù)的協(xié)同過濾推薦的方法和實驗結(jié)果。

1 定量數(shù)據(jù)云映射

李德毅院士在傳統(tǒng)模糊集理論和概率統(tǒng)計的基礎(chǔ)上提出了定性定量不確定性轉(zhuǎn)換模型—云模型。與云模型理論相關(guān)的兩個重要算法[12]是：正態(tài)云發(fā)生器算法解決定性至定量的轉(zhuǎn)換；逆向云算法實現(xiàn)了由定量數(shù)據(jù)到定性知識的轉(zhuǎn)換。本文將逆向云算法所實現(xiàn)的定量數(shù)據(jù)到定性知識的轉(zhuǎn)換稱為云映射。

逆向云算法完成了定量數(shù)據(jù)到定性概念之間的轉(zhuǎn)換，算法如下[12]。

對由n個樣本值所組成的樣本空間{x1, x2,…, xn}，可以使用Cloud（Ex, En, He）描述其定性概念，其中：（1）根據(jù)xi計算定量數(shù)據(jù)的樣本均值一階樣本絕對中心矩樣本方差計算期望：計算熵：（4）計算超熵：

2 云相似性度量

云模型的3個數(shù)字特征中Ex體現(xiàn)了定性概念的核心，而En是對其不確定性的衡量，He又是對En的不確定性度量。所以，對兩個云的相似性進行度量時，其它數(shù)字特征等同的情況下，Ex對相似性的影響最大，En次之，而He對云相似性的影響最小。

從認知的角度，云模型所表示概念的相似性由2個方面組成：Ex和En的聯(lián)合作用決定了概念的內(nèi)涵相似性，代表概念的本質(zhì)區(qū)別；En與He決定了概念的外延相似性，表示概念的不確定程度的異同。本文中使用α表示概念的內(nèi)涵相似性，β表示外延相似性。

為了表示概念內(nèi)涵相似性α，首先給出云距離的定義，對于兩個云C1(Ex1, En1, He1)與C2(Ex2, En2, He2) ，其距離Dis(C1, C2)定義為：

|Ex1–Ex2|表示C1(Ex1, En1, He1)與C2(Ex2, En2, He2)之間的概念核心距離，3En表示云的論域?qū)挾?。當|Ex1–Ex2|＞3(En1+En2)時，兩個云完全分離，沒有交集，此時云距離為1；|Ex1–Ex2|≤3(En1+En2) 時，此公式表示兩個概念的交疊程度；如果Ex1=Ex2，云距離為0，但此時并不意味著兩個云完全重疊，而是表示兩個概念核心相同。超熵He表示沿正態(tài)曲線切線放心的云滴厚度，與概念核心無關(guān)，故不參與云距離的計算。

對于給定的云C1與C2，其內(nèi)涵相似性表示為：

外延相似性與En和He相關(guān)，定義 β為：

He/En代表概念外延的離散程度，當云模型趨近于正態(tài)分布時，He/En趨向于0且概念外延趨于穩(wěn)定；相反，若一方概念使用云模型霧化特征表述的概念，He/En= 0.98且 β取得最小值0.375，此時兩個概念的外延存在最大差異[13]。

α與 β的聯(lián)合作用決定了云相似度，且前者對相似度的貢獻遠大于后者。許多數(shù)學解析式可以表示此類關(guān)系，本文中選用：

當概念內(nèi)涵相似性為0時，云相似性為0且與參數(shù)b無關(guān)，而當內(nèi)涵相似性與外延相似性相同時，兩個云的相似性為1，同樣無關(guān)參數(shù)b。參數(shù)b的大小決定了概念內(nèi)涵相似性與外延相似性對云相似性的貢獻比例，數(shù)據(jù)擬合結(jié)果表明，當b取值大于10之后，其變化對整個表達式結(jié)果影響已經(jīng)十分微弱。針對不同實際問題，可以選擇不同的參數(shù)b來決定α與 β在云相似性中的比重，若問題對概念內(nèi)涵相似性要求比較苛刻，可以增大b的取值，保證α的變化對云相似性具有足夠大的影響，反之可降低b的取值。

圖1 β對SIM（C1, C2）的影響

圖1 給出了外延相似性β對云相似性的影響曲線，本例中 b= 5。對于云C1(1, 0.1, 0.01)與C2(1.1, 0.1, He2) ，隨著He2的變化，β取得最大值1 且此時云相似性等于內(nèi)涵相似性α；而β的最大取值為0.375，此時代表外延相似性對云相似性的影響最大。計算表明當b = 5時β對于云相似的最大貢獻占SIM(C1, C2)的10%左右。

3 云相似性在協(xié)同過濾推薦中的應(yīng)用

相似性比較方法是決定最近鄰協(xié)同過濾推薦算法優(yōu)劣的關(guān)鍵因素，算法中，需要考慮2個方面的相似性：項目相似性與用戶相似性。單純的考慮用戶相似性而忽略項目之間的相似性，會對算法效能產(chǎn)生不利的影響。文獻[14]中提出了一種基于項目評分預(yù)測的協(xié)同過濾推薦算法，其核心思想是通過計算訓練集中用戶評價項目的并集，以并集為基礎(chǔ)衡量用戶間的相似性；在計算用戶并集過程中，對于未評價項目，采用項目相似性來估算用戶對項目的評分，從而實現(xiàn)兼顧項目相似性與用戶相似性。在相似性計算時，文獻[14]算法采用了余弦相似性、相關(guān)相似性與修正余弦相似性。為驗證本文提出的云相似性度量方法，本文提出了基于云模型相似性比較的協(xié)同過濾推薦算法。

3.1 算法設(shè)計

算法輸入：用戶-項目訓練集Ubase，用戶-項目測試集Utest。其中：Ubase和Utest均包含用戶UID、項目IID，評分SCORE這3個數(shù)據(jù)字段；Ubase與Utest的合集共包含M個用戶對N各項目的k項評分，且任意n∈N或m∈M，Ubase中至少包含一項相關(guān)評價記錄；算法輸出：訓練集項目推薦評分向量R。

算法過程：

（1）遍歷Ubase，對任意項目p，獲取其所有項目評分，生產(chǎn)向量Sp，通過本文的改進逆向云算法，計算項目評分云Cloudp(Exp, Enp, Hep)；對所有項目p、q （p≠q），計算 SIM(Cloudp, Cloudq)，從而得到項目相似性矩陣SimItemN?N，顯然，SimItemN?N是主對角線元素為1的對稱陣；

（2）根據(jù)Ubase，獲取用戶i評價項目集合Ui與用戶j評價項目集合Uj，取Uij=Ui∪Uj；

（3）對項目p∈Uij且p∈/Ui，由SimItemN?N獲取p與Ui中所有項目相似性集合Up–i，通過項目相似性評估用戶i對項目p的評分Si–p：

（4）重復(fù)步驟（3），估計用戶i、j在Uij上所有未評價項目的評分，將用戶i、j的評分數(shù)據(jù)分別應(yīng)用改進逆向云算法，獲取Cloudi,與Cloudj,，計算Sim(Cloudi, Cloudj)，得到用戶i與j的相似性；

（5）重復(fù)步驟（4），獲取所有用戶的基于Ubase的相似性矩陣SimUserM?M；

（6）遍歷Utest，對于用戶i對項目p的評價問題：

a.依據(jù)Ubase，獲取所有對項目p進行評分的用戶集合Up；

b.根據(jù)SimUserM?M，獲取用戶i與Up內(nèi)各用戶最近鄰向量Top={simi1, simi2,…, simih}，并進行降序排序；

c.選用Top–N最近鄰用戶作為推薦依據(jù)，仍采用加權(quán)平均的方式計算推薦值Si–p：

（7）重復(fù)步驟（6），獲取Utest內(nèi)所有待測試推薦的預(yù)測評分，輸出R。

3.2 算法評價

推薦性能的評價取決于算法性能。本文提及的算法中，步驟（1）～（6）屬于機器學習階段，本階段可以離線運行，實際應(yīng)用中，服務(wù)后臺進程可以完成增量式機器學習，獲取當前系統(tǒng)用戶的相似性矩陣。推薦過程的時間復(fù)雜度為O(N)，其中N為系統(tǒng)擁有的用戶數(shù)，可見算法時間復(fù)雜度較低，可滿足實際在線應(yīng)用。

為驗證本文提出的推薦算法的推薦質(zhì)量，進而確定云模型相似度度量方法相比傳統(tǒng)算法的優(yōu)勢，采用MovieLens 站點提供的數(shù)據(jù)集（http:// movielens.umn.edu/）進行實驗分析。MovieLens是一個基于Web 的研究型推薦系統(tǒng)，用于統(tǒng)計用戶對電影的評分并提供電影推薦。MovieLens對研究人員提供3種規(guī)模標準推薦測試數(shù)據(jù)集：（1）943名用戶對1 682部電影的10萬條評分記錄；（2）6 040名用戶對3 900部電影的100萬條評分記錄；（3）71 567名用戶對10 681部電影的1000萬條評分記錄。本文采用數(shù)據(jù)集1作為實驗數(shù)據(jù)集，其中每個用戶至少對20 部電影進行了評分。訓練集與測試集數(shù)據(jù)劃分方式采用MovieLens提供的標準劃分方式，劃分所產(chǎn)生的文件u1.base包含8萬條訓練樣本，文件u1.test包含2萬條測試樣本。其數(shù)據(jù)集的稀疏等級[13]為1-100000/(943×1 682)= 0.9370。

采用相同的推薦策略，我們構(gòu)造3種對比方法：（1）項目相似性采用余弦相似性進行度量，用戶相似性采用相關(guān)相似性進行度量；（2）項目相似性與用戶相似性均采用余弦相似性進行度量（文獻[14]采用此方法）；（3）本文提出的推薦方法，采用云模型相似性度量項目與用戶的相似性。3種方法均在上述數(shù)據(jù)集1上進行實驗。

采用Top-2作為推薦依據(jù)時，推薦質(zhì)量最低，此時MAE=0.908；當最近鄰居選取超過8之后，推薦質(zhì)量趨于穩(wěn)定， 維持在0.8左右；雖然隨著最近鄰居選擇數(shù)量的增多，推薦質(zhì)量呈現(xiàn)更好的趨勢，但對于實際應(yīng)用，不可能找到無窮多的最近鄰居，所以對于MovieLens數(shù)據(jù)集，我們認為選用8～20個推薦鄰居，即可得到最佳的推薦質(zhì)量。

3種推薦方法的對比如圖2所示。圖中給出了最近推薦鄰居為4、8、12、20的4種情況。在4種情況下，本文提出的方法3均取得了較小的值，說明推薦結(jié)果更加接近實際用戶評分。同時，3種算法的比較，實際是基于云模型的相似性比較方法與傳統(tǒng)余弦相似性、修正余弦相似性（相關(guān)相似性）方法的比較，結(jié)果表明，對待推薦問題云模型相似性度量方法更加適用，可取得更好的推薦結(jié)果。

圖2 3種方法推薦質(zhì)量比較

4 結(jié)束語

逆向云算法可以完成定量知識到定性概念的轉(zhuǎn)換，但對于分布偏離正態(tài)分布的定量數(shù)據(jù)的轉(zhuǎn)換能力不足。將云模型霧化性質(zhì)與逆向云算法相結(jié)合，可以擴展云模型的知識表示范圍。對于給定的數(shù)據(jù)向量，可以將其轉(zhuǎn)換成兩個云，使用云模型數(shù)字特征進行數(shù)據(jù)表示。云模型的期望和熵決定數(shù)據(jù)對應(yīng)概念的內(nèi)涵相似度，熵和超熵可以反映其外延相似度，度量云之間的相似度可得到數(shù)據(jù)本身的相似程度，而此方法與數(shù)據(jù)之間的對應(yīng)關(guān)系、是否稀疏無關(guān)。

對于旅客分析服務(wù)的推薦問題，使用云模型可以表示項目的評分與用戶的評分數(shù)據(jù)，進而衡量用戶-用戶、項目-項目之間的相似程度，從而對未知的用戶-項目進行評分估計。通過實驗可知，基于云模型的相似性度量方法較傳統(tǒng)方法在解決推薦問題時更加優(yōu)秀，可以為旅客提供個性化、定制化服務(wù)，增強服務(wù)水平，提高旅客乘車體驗。

[1] Arwar B, Karypis G, Konstan J, et a1. Analysis of recommendation algorithms for E-commerce[C]. Processing of 2nd ACM Conference on Electronic Commerce, 2000, 158-167.

[2] Wikipedia. Cloud computing[EB/OL]. http://en. wikipedia. org/wiki/Cloud_comp-uting, 2009-07.

[3] You Weng, Ye Shui-sheng. A survey of collaborative filtering algorithm applied in E-commerce recommender system. Computer Technology and Development[J]. 2006, 16(9): 70-72.

[4] Wang Zhi-meig, Yang Fan. P2P recommendation algorithm based on hebbian consistency learning. Computer Engineering and Applicationsg, 2006g, 42(36): 110-113.

[5] Wang Wei-pingg, Liu Ying. Recommendation algorithm based on customer behavior locus. Computer Systems＆Applicationsg[J]. 2006, 15(9): 35-38.

[6] Gao Jingg, Ying Ji-kang. A recommendation system based on attificial immune system. Computer Technology and Developmentg[J]. 2007, 17(5): 180-183.

[7] Breese Jg, Hecherman Dg, Kadie C. Empirical analysis of predictive algorithms for collaborative filtering. Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence[C]. 1998, 43-52.

[8] Sarwar BMg, Karypis Gg, Konstan JAg, Riedl J. Application of dimensionality reduction in recommender system-A case study[C]. ACM WebKDD 2000 Workshop, 2000.

[9] Aggarwal CC. On the effects of dimensionality reduction on high dimensional similarity search[C]. In: ACM PODS Conferenceg, 2001.

[10] Li De-yi. Uncertainty in Knowledge Representation Engineering Scienceg[J]. 2000, 2(10): 73-79.

[11] 涂穎菲，陳小鴻. 法國城市旅客手機信息服務(wù)系統(tǒng)[J].城市交通，2007（2）： 92-96.

[12] 張飛舟，范躍祖，沈程智，李德毅. 基于隸屬云發(fā)生器的智能控制[J]. 航空學報，1999，20（1）：89-92.

[13] 劉 禹，李德毅，張光衛(wèi).云模型霧化特征及在進化算法中的應(yīng)用[J].電子學，2009，8（37）：1651-1658.

[14] 鄧愛林，朱揚勇，施伯樂. 基于項目評分預(yù)測的協(xié)同過濾推薦算法[J].軟件學報， 2003，14（9）：1621-1628.

責任編輯 方 圓

Recommendation method of railway passenger information service based on user ranking

LI Zongkai1, LI Hongyan1, XIAO Tan1, LV Xiaopeng1, LIU YU2
( 1.CRSC Communication & Information Corporation, Beijing 100071, China; 2. School of Computer Science and Engineering, Beihang University, Beijing 100083, China )

Personalized service recommendation was one of important directions of China railway information service system. In collaborative fi ltering recommendation algorithm, the traditional similarity measurement methods could not deal with large number of users and items which formed a sparse User-Item matrix. This article proposed the similarity measure method based on Cloud Model, applied atomized feature of the Cloud Model to the reverse cloud algorithm. A given data vector could be converted into a cloud. Quantitative data was represented with the numerical characters of the Cloud Model. Cloud similarity was depended on two aspects, such as the concept of connotation similarity and extension similarity. The connotation similarity of data in the corresponding concept was depended on the entropy and expectation of the Cloud Model and extension similarity was reflected by the entropy and excess entropy. A new collaborative filtering recommendation algorithm based on the Cloud Model similarity measurement method was constructed and the experiment result showed that the new algorithm was with reliable and accurate performance.

railway transportation; passenger service; Cloud Model; Reverse Cloud Algorithm; collaborative fi ltering recommendation

U293.3∶TP39

A

1005-8451（2014）11-0005-05

2014-05-06

李宗凱，工程師；李洪研，工程師。