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

（1.通號通信信息集團(tuán)有限公司 北京 100071；2.北京航空航天大學(xué) 計(jì)算機(jī)學(xué)院，北京 100083）

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

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

（1.通號通信信息集團(tuán)有限公司 北京 100071；2.北京航空航天大學(xué) 計(jì)算機(jī)學(xué)院，北京 100083）

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

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

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

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

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

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

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

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

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

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

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

2 云相似性度量

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

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

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

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

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

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

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

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

當(dāng)概念內(nèi)涵相似性為0時(shí)，云相似性為0且與參數(shù)b無關(guān)，而當(dāng)內(nèi)涵相似性與外延相似性相同時(shí)，兩個(gè)云的相似性為1，同樣無關(guān)參數(shù)b。參數(shù)b的大小決定了概念內(nèi)涵相似性與外延相似性對云相似性的貢獻(xiàn)比例，數(shù)據(jù)擬合結(jié)果表明，當(dāng)b取值大于10之后，其變化對整個(gè)表達(dá)式結(jié)果影響已經(jīng)十分微弱。針對不同實(shí)際問題，可以選擇不同的參數(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 且此時(shí)云相似性等于內(nèi)涵相似性α；而β的最大取值為0.375，此時(shí)代表外延相似性對云相似性的影響最大。計(jì)算表明當(dāng)b = 5時(shí)β對于云相似的最大貢獻(xiàn)占SIM(C1, C2)的10%左右。

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

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

3.1 算法設(shè)計(jì)

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

算法過程：

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

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

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

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

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

（6）遍歷Utest，對于用戶i對項(xiàng)目p的評價(jià)問題：

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

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

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

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

3.2 算法評價(jià)

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

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

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

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

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

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

4 結(jié)束語

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

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

[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ī)信息服務(wù)系統(tǒng)[J].城市交通，2007（2）： 92-96.

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

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

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

責(zé)任編輯 方 圓

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

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