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

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

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

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

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

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

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

鐵路運輸；旅客服務；云模型；逆向云算法；協同過濾推薦

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

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

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

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

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

1 定量數據云映射

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

逆向云算法完成了定量數據到定性概念之間的轉換，算法如下[12]。

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

2 云相似性度量

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

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

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

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

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

外延相似性與En和He相關，定義 β為：

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

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

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

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

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

3 云相似性在協同過濾推薦中的應用

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

3.1 算法設計

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

算法過程：

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

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

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

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

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

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

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

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

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

（7）重復步驟（6），獲取Utest內所有待測試推薦的預測評分，輸出R。

3.2 算法評價

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

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

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

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

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

圖2 3種方法推薦質量比較

4 結束語

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

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

[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] 涂穎菲，陳小鴻. 法國城市旅客手機信息服務系統[J].城市交通，2007（2）： 92-96.

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

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

[14] 鄧愛林，朱揚勇，施伯樂. 基于項目評分預測的協同過濾推薦算法[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

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