張振海，張湘婷

蘭州交通大學(xué) 自動化與電氣工程學(xué)院，蘭州730070

隨著移動互聯(lián)網(wǎng)和5G技術(shù)的發(fā)展，通過移動終端或手機為旅客提供便捷的信息服務(wù)是“智慧鐵路”研究的重點領(lǐng)域之一[1-2]。為了響應(yīng)“互聯(lián)網(wǎng)+”的國家號召，高鐵站在12306的售票系統(tǒng)基礎(chǔ)上增加了一系列與旅客出行相關(guān)的拓展服務(wù)如酒店預(yù)訂、美食團購、旅游簡介等，其目的是提升旅客服務(wù)質(zhì)量的同時使鐵路運營效益達到最大化。在高鐵站，旅客獲取的移動信息服務(wù)主要采用以業(yè)務(wù)為中心的靜態(tài)服務(wù)組合方法，以業(yè)務(wù)流程模型構(gòu)建為基礎(chǔ)實現(xiàn)服務(wù)間的交互與協(xié)作。該方式雖然描述了服務(wù)之間的控制和數(shù)據(jù)依賴關(guān)系，但未充分對用戶訪問的大數(shù)據(jù)進行挖掘，以用戶為中心服務(wù)功能未能充分體現(xiàn)，過多冗余的應(yīng)用服務(wù)必然會降低用戶的使用效率，導(dǎo)致用戶體驗性較差。因此，需要以用戶為中心研究，通過對用戶上下文信息的分析與挖掘，發(fā)現(xiàn)用戶的操作行為之間蘊含的關(guān)聯(lián)關(guān)系，研究更加智能的服務(wù)推薦方法，提高高鐵信息服務(wù)質(zhì)量。

目前，眾多國內(nèi)外學(xué)者在服務(wù)推薦方面展開研究，從多個角度提出了數(shù)據(jù)挖掘的模型與方法，傳統(tǒng)推薦算法如協(xié)同過濾、基于內(nèi)容的推薦、混合推薦等。如文獻[3]根據(jù)用戶對學(xué)習(xí)資源的個性化需求，提出基于內(nèi)容過濾的推薦方法。文獻[4]對用戶進行聚類，建立推薦服務(wù)庫，從而實現(xiàn)服務(wù)推薦。文獻[5]利用關(guān)聯(lián)規(guī)則考慮用戶需求設(shè)計智能旅游景點推薦系統(tǒng)。上述方法是“用戶-項目”之間關(guān)聯(lián)關(guān)系占據(jù)推薦重要位置，但隨著移動應(yīng)用的興起，用戶周邊環(huán)境也開始影響用戶服務(wù)選擇，針對此問題，一些學(xué)者將“移動用戶-移動應(yīng)用-上下文”關(guān)聯(lián)關(guān)系引入推薦系統(tǒng)中。文獻[6]利用用戶所在位置，挖掘出此位置頻繁使用的服務(wù)功能推薦給用戶，該方法只考慮一種上下文的推薦，會導(dǎo)致數(shù)據(jù)稀疏，從而推薦精度不高。文獻[7]設(shè)計一種融合上下文信息與社交網(wǎng)絡(luò)信息的個性化推薦系統(tǒng)，通過隨機決策建立原始用戶-商品評分矩陣對上下文信息處理，最后采用矩陣因式分解進行預(yù)測，但此方法未考慮上下文與用戶行為之間的關(guān)系。相似的，文獻[8]提出一種基于上下文感知的個性化度量嵌入推薦算法，考慮上下文情景信息，進一步研究了上下文與用戶操作行為之間存在規(guī)律信息。文獻[9]提出一種基于用戶聚類和移動上下文的矩陣分解推薦算法，采用kmeans對用戶聚類找到相似用戶簇。關(guān)于高鐵信息服務(wù)方面，文獻[2]分析推薦系統(tǒng)在鐵路延伸服務(wù)中的應(yīng)用前景，證明向用戶即時推薦所需服務(wù)或產(chǎn)品，在發(fā)揮鐵路資源優(yōu)勢的同時提升用戶滿意度。文獻[10]提出基于云模型相似性度量的協(xié)同過濾推薦算法應(yīng)用在旅客服務(wù)推薦中，使用云模型表示項目評分和用戶評分，衡量用戶-用戶、項目-項目之間的相似度，從而對未知用戶進行評分，但只對MovieLens數(shù)據(jù)集進行實驗沒有實際結(jié)合鐵路客運情況。對于高效的高鐵移動信息服務(wù)，旅客當(dāng)前的應(yīng)用場景對服務(wù)功能的選擇影響較大，因此如何對上下文信息預(yù)處理和挖掘上下文信息與服務(wù)間的規(guī)則考慮為高鐵站旅客量身定做一個專屬的服務(wù)集合是十分重要的[11-12]。

為此，本文分析當(dāng)前高鐵站旅客出行需求，結(jié)合高鐵運輸特點構(gòu)造上下文模型，采用改進FP-Growth算法，賦予不同類型上下文項單獨最小支持度，以上下文項與服務(wù)間的關(guān)聯(lián)規(guī)則作為匹配依據(jù)，對獲取當(dāng)前上下文信息進行相似度計算，最終精準(zhǔn)定位旅客需求，為多樣化、個性化的客運服務(wù)奠定基礎(chǔ)。

1 高鐵信息服務(wù)推薦模型框架

上下文是表述實體狀態(tài)特征的所有信息，例如地點、天氣、時間等[13-14]。上下文的感知是將上下文的變化融入到模型中向用戶推送信息或服務(wù)，協(xié)助完成具體的任務(wù)?；谏舷挛母兄姆?wù)推薦方法是利用上下文信息作為服務(wù)推薦主要依據(jù)，建立上下文與服務(wù)功能之間的關(guān)系，獲得符合當(dāng)前應(yīng)用場景下的服務(wù)集合并且動態(tài)加載到用戶界面中，如圖1所示。

圖1 上下文感知的服務(wù)推薦方法

在基于上下文感知的高鐵信息服務(wù)推薦模型中，由用戶基本信息、第三方提供的信息和移動設(shè)備感知信息所構(gòu)成的上下文信息庫以及高鐵站內(nèi)、站外的延伸服務(wù)構(gòu)成的服務(wù)信息庫是作為推薦主要依據(jù)，根據(jù)顯式信息與隱式信息對用戶信息服務(wù)進行建模[15]。用戶使用系統(tǒng)時，服務(wù)系統(tǒng)自動獲取當(dāng)前上下文，通過對應(yīng)推薦算法進行服務(wù)匹配，構(gòu)造個性化服務(wù)推薦集合，最終發(fā)布到移動客戶端，具體框架如圖2所示。本文采用改進FP-Growth推薦算法挖掘上下文與服務(wù)之間的關(guān)聯(lián)規(guī)則，對有價值的用戶歷史記錄信息進行統(tǒng)計與分析，通過用戶行為預(yù)測實現(xiàn)信息服務(wù)的精準(zhǔn)推薦。

圖2 基于上下文的高鐵推薦模型框架

2 FP-Growth算法及相關(guān)概念

（1）相關(guān)概念

關(guān)聯(lián)分析是發(fā)現(xiàn)隱含于大數(shù)據(jù)中具有實際意義的規(guī)律信息，這些規(guī)律可描述為關(guān)聯(lián)規(guī)則或是頻繁項集[16]。假設(shè)I={I1,I2,…,I m}為項的集合，同時在事務(wù)數(shù)據(jù)庫D中每一條事務(wù)T均為I的非空子集，即T?I，而且每一條事務(wù)T獨有與之對應(yīng)的標(biāo)識符TID(Transaction ID)。

定義1（項集）項的集合，包含k個項的項集稱為k項集。

定義2（支持度）在數(shù)據(jù)挖掘的關(guān)聯(lián)分析中，支持度是所有事務(wù)T中同時出現(xiàn)A項（或項集）的概率，計算公式如下：

支持度也可表示為A項（或項集）在數(shù)據(jù)庫D中出現(xiàn)的頻數(shù)，稱為支持度計數(shù)。設(shè)置最小支持度min_sup，若sup(A)≥min_sup，稱項集A是頻繁項集[16]。

定義3（關(guān)聯(lián)規(guī)則）是蘊含關(guān)聯(lián)的規(guī)則，形如X→Y,其中X為前件(antecedent),為Y后件(consequent)。

（2）算法描述

①遍歷事務(wù)數(shù)據(jù)庫D，計算每項支持度并過濾不符合的項，獲得頻繁1項集L，按照支持度大小降序排列得到有序頻繁1項集P，然后對事務(wù)數(shù)據(jù)庫D重新調(diào)整。

②創(chuàng)建根節(jié)點root和頻繁項目頭表，再一次遍歷事務(wù)數(shù)據(jù)庫D，將依據(jù)P的排序?qū)γ織l事務(wù)進行處理，掃描每條事務(wù)開始建立分支生成FP-tree。

③根據(jù)FP-tree樹找到單項的條件模式基，遞歸挖掘條件FP-tree，最終依據(jù)頻繁項集從中得出關(guān)聯(lián)規(guī)則。

3 高鐵信息服務(wù)推薦方法

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

為滿足當(dāng)前實際應(yīng)用場景，以UML關(guān)系圖為基礎(chǔ)建立高鐵移動應(yīng)用上下文模型結(jié)構(gòu)，如圖3所示。該模型說明各元素之間的關(guān)系，分為時間、空間、用戶和應(yīng)用四類，其中ISO 8601和UTC為當(dāng)前日期和時間。

圖3 高鐵移動服務(wù)應(yīng)用的上下文模型

為更規(guī)范表達的例子事務(wù)，本文定義數(shù)據(jù)操作符，如表1所示，根據(jù)此操作符列出事務(wù)示例，如表2所示。其中，T.c,T.d和T.l分別表示當(dāng)前時間、發(fā)車時間和剩余時間，該信息可從用戶訪問移動應(yīng)用獲??；L.d分別表示用戶所在地A與目標(biāo)位置B的距離，該數(shù)據(jù)可從手機GPS定位中獲取；L.w代表當(dāng)前天氣情況，可通過手機自帶軟件獲??；U.a、U.g、U.p、U.i分別表示用戶的年齡、性別、職業(yè)以及興趣愛好，可從用戶基本信息中獲?。粯I(yè)務(wù)狀態(tài)B.s可由應(yīng)用軟件與用戶進行交互獲取[17]。

3.2 構(gòu)建高鐵移動信息服務(wù)FP-tree

傳統(tǒng)FP-Growth算法只針對一維數(shù)據(jù)項設(shè)置單一支持度，進行規(guī)則提取實現(xiàn)推薦。對實際應(yīng)用而言，每個上下文項都是屬性和數(shù)值組成的鍵值對，如果設(shè)置單一最小支持度會造成關(guān)鍵上下文項丟失，例如U.g只有male和female兩種選擇，而T.c分為六個時間段，因此兩類上下文項中的值出現(xiàn)概率不同，前者遠大于后者。因此，根據(jù)每類上下文項出現(xiàn)概率分別設(shè)置最小支持度（服務(wù)功能項最小支持度設(shè)為0，排在最后），即多最小支持度Min_sup={MinSup1,MinSup2,…,MinSup n}。若項A的支持度Sup(A)≥Min_sup A，則A為二維頻繁項集?；舅枷胧牵涸谑聞?wù)數(shù)據(jù)庫D中，設(shè)置多最小支持度Min_sup確定有序二維頻繁1項集L，根據(jù)L對每條事務(wù)重新調(diào)整建立分支，構(gòu)建FP-tree。

表1 數(shù)據(jù)操作符

表2 事務(wù)示例

具體算法描述如下所示：

輸入：事務(wù)數(shù)據(jù)庫D；

最小支持度Min_sup

Min_sup={MinSup1,MinSup2,…,MinSup n}；

輸出：FP-tree；

遍歷事務(wù)數(shù)據(jù)庫D，計算每一個項的支持度計數(shù)并與Min_sup比較，獲得二維頻繁1項集L，依照最小支持度的值降序排序得到有序二維頻繁1項列表L′。

創(chuàng)建一個FP-tree的根節(jié)點，記為Null；

for事務(wù)中每條事務(wù)Tdo按照L′的順序調(diào)整次序；

將每條經(jīng)過排序得到二維頻繁項集合[p|P]，其中p為首個元素，P為剩余元素集合；

調(diào)用函數(shù)insert_tree([p|P],T)，創(chuàng)建FP-tree；

end for

inser t_tree([p|P],root)

ifiis kind ofNandN.item-name=p.

item-name//i是已有分支的一項

N.count++；

else

創(chuàng)建新節(jié)點N；

N.count=1；

p.parent=r oot；

將此節(jié)點加入到項表頭相同item-name節(jié)點上；

end if

insert（i，node）；

3.3 上下文信息及相似度計算

上下文信息獲得途徑有手機內(nèi)置傳感器、用戶注冊信息或者系統(tǒng)軟件本身等。上下文信息分為：離散型上下文信息（職業(yè)、天氣等）；連續(xù)型上下文信息（年齡、剩余時間等）[18]。假設(shè)系統(tǒng)內(nèi)有F種類型的上下文信息，記，即歷史記錄中用戶u x在使用服務(wù)S y時全部上下文信息，其中為第k種類型的上下文。記Ccurrent=是目標(biāo)用戶U c在使用當(dāng)前系統(tǒng)時的所有上下文信息，其中為第k種類型的上下文，計算相似度公式如下：

如果第k種類型的上下文信息是屬于離散型，則分為相關(guān)性和非相關(guān)性。當(dāng)上下文信息具有相關(guān)性，計算公式如下：

數(shù)據(jù)預(yù)處理中天氣可分成晴天、陰天、霧天、雨天和雪天五種，設(shè)置等級為1～5，如simk(晴天,陰天)=1-simk(晴天,雪天)simk(晴天,陰天)＞simk(晴天,雪天),晴天與陰天相似度更高。

當(dāng)離散型上下文信息值具有無相關(guān)性，計算式如下：

在數(shù)據(jù)預(yù)處理中對旅客職業(yè)按照國家職業(yè)分類大全分成8類，這些職業(yè)之間并沒有相關(guān)性，例如技術(shù)性職業(yè)與商業(yè)性職業(yè)相似度就為0。

如果第k種類型上下文信息是連續(xù)型數(shù)據(jù)，則先將連續(xù)型轉(zhuǎn)變成離散型，然后用離散型上下文信息的相似度算法，將連續(xù)型數(shù)據(jù)轉(zhuǎn)化為離散型的計算公式如下：

式中，Tn(1≤n＜N)是分界點，當(dāng)轉(zhuǎn)化成離散化之后求相似度的計算方法如式（3）所示。

3.4 基于關(guān)聯(lián)規(guī)則的服務(wù)匹配

在FP-tree中每條路徑均包含類似于C→S的關(guān)聯(lián)關(guān)系，C是除根節(jié)點之外的自上向下構(gòu)成序列集合，S是每一條路徑中包含的服務(wù)功能集合。在當(dāng)前應(yīng)用場景時，可根據(jù)上下文C′構(gòu)造適合該場景的服務(wù)集合，將上下文C′與FP-tree每個分支中的C做相似度計算，即sim(C,C′)，綜合排序取Top-k，得到服務(wù)推薦集合。

具體算法描述如下所示：

輸入：FP-tree；用戶當(dāng)前上下文信息Current；最小相似度MinCount；推薦服務(wù)個數(shù)K。

輸出：服務(wù)集合S。

4 實驗結(jié)果與分析

4.1 數(shù)據(jù)集

因為目前高鐵旅客信息服務(wù)推薦領(lǐng)域積累不足，為了采集旅客相關(guān)信息，在蘭州站征集了50個志愿者的智能手機，職業(yè)有教師、學(xué)生、工人等，在高鐵站使用的“鐵路12306”“智行”“美團”等相關(guān)類型APP上采集約15萬條數(shù)據(jù)。隨機選取10 000條用戶歷史數(shù)據(jù)，以9∶1的方式分成訓(xùn)練集和測試集，訓(xùn)練集是采用本文算法挖掘出上下文信息和服務(wù)功能之間的關(guān)聯(lián)規(guī)則，測試集是根據(jù)訓(xùn)練集進行服務(wù)匹配。

本文使用的硬件為Intel?酷睿I5-42210U，2.70 GHz處理器，8 GB內(nèi)存，操作系統(tǒng)是Windows 7旗艦版64位；軟件為eclipse3.4-jee-ganymede開發(fā)運行平臺，JDK7.0版本。

4.2 指標(biāo)選擇

評價一個服務(wù)推薦算法往往從命中率(Recall)、準(zhǔn)確率(Precision)和綜合評價(Comprehensive evaluation)3個方面進行考慮，命中率主要用于衡量算法得出推薦服務(wù)集合Ure與實際可推薦服務(wù)集合Ureal的交集與實際可推薦服務(wù)數(shù)量的比值，計算公式如下：

準(zhǔn)確率主要衡量算法所得出的服務(wù)集合Ure與實際上可推薦的服務(wù)集合Ureal的交集與算法得出服務(wù)數(shù)量的比值，計算公式如下：

綜合評價指標(biāo)，可以很好地考量推薦算法的整體性能，計算公式如下：

4.3 結(jié)果分析

在事務(wù)數(shù)據(jù)集中，根據(jù)上下文項的出現(xiàn)頻率和重要程度設(shè)置本算法的多最小支持度Min_Su p={U.g=0.3,T.c=0.2,T.d=0.15,L.w=0.13,U.a=0.15,U.p=0.1,U.i=0.1,T.l=0.1,B.s=0.4}，圖4顯示出實驗參數(shù)對推薦系統(tǒng)產(chǎn)生的影響。Top-k的取值可直接影響實驗的有效性，k值過小即算法推薦數(shù)量過少，會導(dǎo)致命中率過低，由圖可知，k增加時命中率也隨之增加。k≤5時命中率要低于準(zhǔn)確率，是因為用戶期望的服務(wù)個數(shù)大于算法推薦個數(shù)。從圖中也可看出隨著k增加準(zhǔn)確率會降低，雖然k增加命中服務(wù)的概率也會增大，但是這種增加是具有概率性的。特別是在命中率很高的情況下，k的增加反而會使準(zhǔn)確率降低，因此整體呈下降趨勢。當(dāng)k≥11時，命中率和準(zhǔn)確率不再改變，原因是用戶所需服務(wù)已達到飽和同時Top-k的所取個數(shù)為整個候選服務(wù)集合。從圖中可看出Top-k的較理想取值k=8。

圖4 Top-k對實驗影響

圖5 實驗對比結(jié)果

圖5 是在圖4得出的Top-k(k=8)的基礎(chǔ)上進行實驗所得結(jié)果。實驗將本文算法、傳統(tǒng)FP-Growth算法和文獻[10]提出基于云模型相似性度量的協(xié)同過濾推薦算法（即CFBOCMSM），進行命中率、準(zhǔn)確率和綜合評價三方面比較。傳統(tǒng)FP-Growth算法的最小支持度設(shè)為0.2。為了更好地分析對比這三種方法，本文將設(shè)置10個不同高鐵應(yīng)用場景下的用戶所需服務(wù)。由圖可知，本文算法產(chǎn)生結(jié)果均高于其他兩種算法，這是由于設(shè)置多最小支持度對FP-tree進行擴展，將頻率較高的項設(shè)置較大的最小支持度，避免關(guān)鍵項丟失的同時控制規(guī)則數(shù)量，使得平均準(zhǔn)確率從47.94%提高到57.05%，平均命中率從76.74%提高到91.02%。

在事務(wù)數(shù)據(jù)集上，隨機選擇3 000、6 000、9 000條事務(wù)對其挖掘，求得準(zhǔn)確率與命中率結(jié)果，如圖6所示。

圖6 事務(wù)數(shù)對結(jié)果的影響

由圖可知，歷史事務(wù)數(shù)與服務(wù)應(yīng)用的命中率和準(zhǔn)確率成正比，因為歷史事務(wù)數(shù)量直接影響關(guān)聯(lián)規(guī)則數(shù)，事務(wù)數(shù)據(jù)越多對挖掘越有幫助。

5 結(jié)論

服務(wù)推薦是當(dāng)前服務(wù)計算領(lǐng)域中的熱點，隨著高鐵站旅客對出行效率和出行質(zhì)量要求的不斷提高，追求高質(zhì)量服務(wù)組合的難度也隨之增加。分析傳統(tǒng)FP-Growth算法在實際高鐵應(yīng)用場景所存在的局限性和挖掘不足的問題，提出基于上下文感知的服務(wù)推薦方法，根據(jù)不同類型上下文項設(shè)置多最小支持度，得到上下文和服務(wù)之間的關(guān)聯(lián)關(guān)系，采取上下文項相似度的計算方法進行服務(wù)匹配，最后獲得推薦的服務(wù)集合。此方式可以縮短用戶與高鐵信息服務(wù)之間的距離，進一步落實“以人為本”的服務(wù)理念，提升現(xiàn)階段的高鐵信息服務(wù)水平。實驗證明改進后的算法顯著提高了服務(wù)匹配的準(zhǔn)確率和命中率，該方法可以有效利用上下文信息并獲得滿足用戶需求的推薦結(jié)果。隨著歷史數(shù)據(jù)量的不斷增大，F(xiàn)PGrowth改進算法產(chǎn)生的FP-tree過于龐大，因此需在海量數(shù)據(jù)環(huán)境中實現(xiàn)并行化，提高運行效率是下一步的研究重點。