張 燁,付曉東,2,3,劉 驪,劉利軍,馮 勇,3(昆明理工大學信息工程與自動化學院,昆明650500)
2(昆明理工大學航空學院,昆明650500)
3(云南省計算機技術(shù)應用重點實驗室,昆明650500)
E-mail:xiaodong_fu@hotmail.com
隨著互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展,傳統(tǒng)的消費方式發(fā)生了巨大的變化.在線服務是指利用互聯(lián)網(wǎng)技術(shù)向用戶提供線上服務的方式,因其使用方便、操作簡單、成本低廉等優(yōu)點而受到廣泛的歡迎[1].然而,由于存在大量服務功能相同而服務質(zhì)量(Quality of Service,QoS)不同的在線服務,從而導致用戶對選擇何種服務難以進行決策.此外,由于網(wǎng)絡環(huán)境的虛擬性、開放性、動態(tài)性以及信息的不對稱性,不能保證服務提供者發(fā)布的信息都是客觀、真實、可信的[2],從而導致在線服務中交易欺詐、網(wǎng)絡欺騙等現(xiàn)象頻發(fā).信譽作為對服務QoS的綜合度量,反映服務履行其承諾服務的水平和其他主體對它的總體信任程度[3],因此,研究一種能夠客觀度量在線服務信譽的方法可以有效地幫助用戶應對交易欺詐并支持用戶做出正確的服務選擇.
目前在線服務信譽度量領(lǐng)域的研究工作已經(jīng)取得了很大的進展但依然具有局限.例如,許多在線服務信譽度量模型是單維度的[4],模型僅根據(jù)服務交易中的評分數(shù)據(jù)來度量服務信譽,沒有區(qū)分交易過程中服務的各屬性信息對服務信譽度的影響.而在基于多維度評價信息進行服務信譽度量方法[5,6],僅依據(jù)用戶對服務的各屬性評價信息度量服務信譽,沒有考慮服務自身的屬性,如服務消費者保障、服務規(guī)模等屬性對服務信譽度的影響.因此,一種通過綜合服務多維度評價信息對服務進行信譽度量的方法可以獲得更合理的信譽度量結(jié)果.
為解決以上問題,本文提出了一種基于半監(jiān)督學習的在線服務信譽度量方法.方法以決策樹分類器為理論基礎(chǔ),基于Tri-training算法構(gòu)造服務分類器模型[7],實現(xiàn)綜合服務多維度評價信息對服務進行信譽度量.最后,提出半監(jiān)督隨機森林算法訓練分類器模型來進一步提升模型的分類性能,實現(xiàn)信譽度量.
在傳統(tǒng)的電子商務中以用戶對服務的單維度評分信息來評估在線服務信譽度.常見的信譽度量方法有均值法、累加求和法、概率法等[8,9].Amazon1http://www.amazon.cn/等使用均值法,將所有用戶對服務的評分求平均值作為服務的信譽值.EBay2http://www.ebay.com/等網(wǎng)站則將用戶對服務的反饋評分進行求和運算得出服務信譽值.文獻[10]基于用戶對服務的評價獲得直接信任值,通過推薦用戶獲取服務的間接信任值,最后整合直接信任值和間接信任值來計算出服務的信譽.文獻[11]提出運用貝葉斯概率的方法,描述信任與信譽以及其之間的關(guān)系,并利用歷史交易信息進行信譽的計算.文獻[12]中提出基于事件驅(qū)動和規(guī)則驅(qū)動的信任管理框架,在此框架中,基于規(guī)則確定信譽計算公式和參數(shù).上述研究只是基于服務整體表現(xiàn)做出評價進行信譽度量,沒有考慮服務的各個維度屬性對服務信譽度的影響,導致信譽度量結(jié)果不夠客觀、準確.
為克服基于單維度評分信息的信譽度量模型的缺陷,文獻[13]中從電子商務網(wǎng)站設計的角度對在線服務的影響因素進行研究,指出內(nèi)容設計、社會因素和結(jié)構(gòu)設計等均影響在線信譽.文獻[14]綜合服務多維度屬性信息,提出使用交易評價體系和評價權(quán)重體系體現(xiàn)個人偏好等因素.文獻[15]提出了一種基于用戶屬性的細度化信譽評價體系,在此體系中用戶可以評價其他用戶的屬性,而不對其身份做任何評價,從而避開用戶身份對信譽的影響.上述研究通過用戶對服務的評分進行信譽度量,提高了服務信譽度量的有效性與準確性,但對服務的信譽度量僅考慮用戶對服務各屬性的評價信息,沒有考慮服務自身的屬性信譽,如服務消費者保障、服務規(guī)模屬性等對服務信譽度的影響.
考慮到以上研究中存在的不足,本文提出一種綜合考慮服務的用戶評價信息、服務自身屬性信息、歷史交易信息等多維度信息的在線服務信譽度量模型.模型將服務信譽度量建模成對服務的分類問題,人工標注少量服務樣本作為訓練集,通過半監(jiān)督學習算法利用大量未標注服務樣本訓練服務的分類器模型.該模型以 C4.5 決策樹(Decision Tree,DT)[16]為基礎(chǔ),首先利用人工標注的服務樣本訓練3個不同決策樹分類器模型;然后基于Tri-training協(xié)同訓練算法不斷對未知服務進行預測[7],并將所預測服務連帶預測結(jié)果加入到訓練集重新訓練分類器.為防止Tri-training的過擬合,提出半監(jiān)督隨機森林算法[17],可以有效提升分類器分類性能并用所得分類器對服務進行分類實現(xiàn)信譽度量.最后,本文通過實驗驗證了方法的合理性與有效性.
本文研究如何依據(jù)在線服務的多維度屬性信息實現(xiàn)服務信譽度量,而信譽度量可視為對服務不同信譽類別的劃分,所以將服務信譽度量問題建模成對服務的分類問題.以下先對問題進行形式化描述.
定義 1.(在線服務集)S={s1,s2,…,sm}為服務的有限集.A={a1,a2,…,an}為服務的多維度屬性集,這其中包括用戶評分屬性集Au={描述相符度,售后速度,物流速度,賣家服務態(tài)度,賣家服務},服務自身有關(guān)屬性集 As={銷售量,售后率,糾紛率,懲罰數(shù),物流質(zhì)量,消費者保障}等,則有A=Au∪As.
例如,服務集S中服務樣本實例si可以表示為:
定義2.(在線服務多維度評價信息)是指對服務的各個屬性A={a1,a2,…,an}的評價信息.服務si的多維度評價信息為si(A)={si(a1i),si(a2
i),…,si(an
i)}.
定義3.(服務信譽)信譽是對服務QoS的綜合度量,反映服務履行其承諾的服務水平和其他主體對它的總體信任程度,將服務si的信譽記為R.
為了更容易使用戶區(qū)分服務信譽好壞程度,可依據(jù)服務信譽值的高低程度將R劃分為l個不同的區(qū)間,代表服務之間不同的信譽級別,例如,可以將用戶評分劃分為5個等級,記為 R={r1,r2,r3,r4,r5},則信譽標簽 r1到 r5,分別代表服務信譽的優(yōu)秀、良好、中等、較差、特差.
定義4.(訓練集)服務si及其信譽標簽ri形成一個具有明確信譽標簽的訓練樣本xi={si,ri}.由多個訓練樣本所組成的集合為訓練集記為 X,則有 X={x1,x2,…,xp},其中X(A)為服務的多維度評價信息.
定義5.(服務信譽度量)基于訓練集X訓練分類器模型,并用所得分類器對服務進行分類,得到該服務的信譽標簽,進而實現(xiàn)對服務的信譽度量.
為了解決先前研究中評價粒度過粗和維度考慮不全的問題,本文采用一種綜合服務多維度評價信息的信譽度量方法.方法利用已知服務的多維度評價信息基于決策樹算法訓練對服務的初始分類器,然后基于Tri-training算法利用所得初始分類器對未標注服務集中服務進行分類,并將分類后的服務和標簽加入到訓練集,重新訓練分類器.使用最終訓練所得分類器對服務進行分類進而實現(xiàn)對服務的信譽度量.決策樹是機器學習中一種常用的分類算法,其通過訓練集訓練分類器模型,實現(xiàn)對樣本的分類.將決策樹運用到服務信譽度量中主要有兩個方面的優(yōu)點:首先,決策樹分類算法相較于其他機器學習中的分類算法屬于白盒模型,模型簡單易懂;其次,決策樹模型屬于多分類器模型,相較于SVM、Logistic Regression等算法可以更加方便地實現(xiàn)多分類.
根據(jù)定義4,基于訓練集X,利用C4.5決策樹算法,訓練分類器模型,可得到初始分類器.S={s1,s2,…,sm}為由m個未知標簽的服務所組成的服務集,從S中隨機選擇p個服務進行人工標注,作為訓練集記為X,剩余q個未標注服務集記為 Y={y1,y2,…,yn},則有 m=p+q.
首先計算訓練集X的信息熵(Information Entropy).訓練集X的信息熵是訓練集X中樣本集合純度的指標,如果訓練集X中第g類服務樣本所占的比例為pg={1≤g≤k},則服務集X的信息熵定義為:
計算基于屬性ai所產(chǎn)生的信息增益(Information Gain).屬性ai的可能取值為,若使用ai劃分訓練集X,則產(chǎn)生V個分支結(jié)點,其中第v個分支結(jié)點在訓練集X中所有在屬性ai上取值為的樣本記為Xv,給分支節(jié)點賦予權(quán)重Xv/X,于是可以得到利用屬性ai對訓練集X進行劃分所獲得的信息增益為:
最后計算使用屬性ai對服務集X進行劃分所產(chǎn)生的信息增益率(Gain ratio)為:
利用訓練集X訓練該決策樹模型.將決策樹分類器建模成ri=T(xi,X(A))的形式,其中,X(A)是訓練集X中服務的多維度評價信息,用于訓練決策樹分類器T.xi是基于此分類器要進行分類的服務樣本.輸出是決策樹分類器模型T(xi,X(A)),算法描述如算法1所示,其中max_tag表示訓練集中樣本最多的標簽,max表示取最大值,F(xiàn)ather_Node(n)表示n結(jié)點的父結(jié)點,Xv表示第v個分支節(jié)點包含在X中并且屬性取值為a*的樣本,Leaf_Node為葉結(jié)點,Branch_Node為分支結(jié)點.
算法1.決策樹算法
輸入:訓練集X,服務多維度屬性集A;
輸出:生成的決策樹T(xi,X(A)).
為解決現(xiàn)實環(huán)境中很難獲得大量具有明確信譽標簽的服務,而僅靠少量人工標注的訓練樣本所訓練的分類器難以代表服務的實際數(shù)據(jù)分布規(guī)律的問題,本文采用半監(jiān)督學習算法訓練決策樹模型.利用少量的標注服務數(shù)據(jù)訓練初始分類器,基于所訓練分類器對未知服務進行分類實現(xiàn)服務的信譽度量.半監(jiān)督學習是有監(jiān)督學習與無監(jiān)督學習相結(jié)合的一種常用的方法,使用標記樣本的同時大量使用未標記樣本進行模型的訓練,在盡大可能減少人工標注成本的同時,又可以帶來較高的準確率.為此本文采用距離約束的Tri-training(Con-Tri-training)算法克服訓練樣本不足的問題.首先對訓練集X進行有放回采樣,每次隨機、等概論地從X中抽取一個服務后放回,連續(xù)采樣m次得到訓練集X1.以同樣的方式進行采樣得到訓練集X2、X3,然后基于算法1訓練得到3個決策樹分類器T1、T2、T3,通過不斷地循環(huán)迭代實現(xiàn)對大量未標注服務的預測,并將預測服務加入到訓練集提高模型性能.具體地,利用初始訓練的T1、T2、T3三個分類器對服務集Y中的服務yj的標簽進行預測,首先基于T2、T3兩個分類器對服務yj進行分類得到分類標簽,然后判斷分類結(jié)果是否一致:
對于結(jié)果①計算服務yj與訓練集 X={x1,x2,…,xn}中每個服務屬性評分的歐氏距離D,并求得與yj歐氏距離最小的服務xn,已知服務xn的標簽為rn.比較服務yj的信譽標簽rj和服務xn的信譽標簽rn,作如下決策:
如果rj=rn,則將服務yj連帶所預測的標簽rj一起加入到訓練集X1,并利用X1重新訓練分類器T1,如果rj≠rn,則對服務yj不做任何操作.基于分類器T1、T3對服務yj做預測并重新訓練分類器T2,同樣由T1、T2對服務yj做預測更新分類器T3.最后聚合更新后的分類器T1、T2、T3作為最終分類器,記為G(xi,X(A)),其算法如算法2所示.
算法2.Con-Tri-training算法訓練分類器模型
輸入:決策樹 T1、T2、T3,訓練集 X1、X2、X3;
輸出:分類器 G(xi,X(A)).
通過Con-Tri-training算法可以在減少誤分樣本的同時,將服務集Y中服務加入到訓練集中,從而使得訓練集樣本的信息得到完善,所訓練的分類器分類性能更加可靠.
在機器學習的分類任務中,訓練的分類器往往會出現(xiàn)對訓練樣本有很好的分類性能,但對預測樣本預測精度不夠的問題,稱之為過擬合現(xiàn)象[18].過擬合的原因在于學習時過多地考慮如何提高對訓練數(shù)據(jù)的正確分類,從而構(gòu)建出過于復雜的決策樹.而通過對決策樹進行剪枝處理[19],或者基于決策樹構(gòu)造隨機森林分類器模型[17],可以解決決策樹模型中的過擬合現(xiàn)象,從而達到降低模型過擬合的目的.本文從對決策樹進行剪枝處理和構(gòu)建半監(jiān)督隨機森林兩種思路出發(fā)消除模型的過擬合,并通過實驗比較選出最優(yōu)抗過擬合模型,作為最終的信譽度量模型.
4.3.1 模型的剪枝處理
通過對已經(jīng)生成的決策樹T1、T2、T3上進行剪枝獲得剪枝后分類器.具體地如圖1所示,剪枝從生成的樹上剪掉子樹或者葉節(jié)點,并將其根節(jié)點或父節(jié)點作為新的葉節(jié)點從而簡化決策樹的模型復雜度.
圖1 決策樹的剪枝Fig.1 Pruning of decision trees
決策樹的損失函數(shù)表示決策樹模型對未知服務預測能力的大小,如公式(6)所示:
其中α為參數(shù),Entt(T)為結(jié)點t的信息熵,|T|為葉結(jié)點個數(shù),t為決策樹的葉結(jié)點,Nt為葉結(jié)點的樣本點.假設葉節(jié)點回縮到父節(jié)點前后的整體樹分別為Ta與Tb,其對應的損失函數(shù)分別為Loss(Ta)、Loss(Tb),如算法3所示.
算法3.決策樹剪枝算法
輸入:已生成的決策樹T1、T2、T3;
輸出:修剪后的決策樹 T1'、T2'、T3'.4.3.2 半監(jiān)督隨機森林模型
構(gòu)造隨機森林分類器對抗G(xi,X(A))模型的過擬合.首先增加Con-Tri-training算法中分類器G(xi,X(A))的決策樹個數(shù)至k(k≥3)個,然后對屬性集A中的屬性進行隨機抽樣,使得每個訓練集盡可能的不同,構(gòu)造隨機森林分類器H(xi,X(A)).基于Bootstrap Sampling采樣策略對訓練集X進行采樣,每采樣m次組成一個訓練集,共采樣出k個訓練集記為X1,X2,…,Xk,然后對k個不同訓練集中服務的屬性集A={a1,a2,…,an}分別進行隨機采樣,其中每個訓練集采樣出個屬性作為該訓練集中服務最終的決策屬性集.基于X1,X2,…,Xk個訓練集訓練得到 k 個分類器 T1,T2,…,Tk.對這k個決策樹分類器進行集成構(gòu)造半監(jiān)督隨機森林分類器H(xi,X(A)),如算法 4 所示.
算法4.隨機森林算法
輸入:訓練集 X,服務屬性集合 A={a1,a2,…,an},決策樹分
類器 T(xi,X(A)),訓練輪數(shù) k;輸出:隨機森林模型H(xi,X(A))
將服務yj連帶預測標簽rj加入訓練集X1,X2,…,Xk中并對這k個訓練集中的服務樣本進行更新,得到更新后的訓練集X1,X2,…,Xk.利用更新所得訓練集重新訓練 T1,T2,…,Tk決策樹分類器模型.利用所得分類器對服務進行分類,采用簡單少數(shù)服從多數(shù)的投票法則,得到該服務的信譽標簽,進而實現(xiàn)對服務的信譽度量.
為了驗證本文中方法的有效性,本文爬取網(wǎng)絡零售商淘寶網(wǎng)中1632個完整的在線商家交易統(tǒng)計,數(shù)據(jù)集中包括10個服務種類,每個服務有16個維度屬性信息.其中隨機選出80%大約(1300個服務)的數(shù)據(jù)作為模型的訓練集,剩余的20%(大約332個服務)作為模型的測試集,為了驗證方法的合理性,使得信譽度量的標簽信息與人工標注的標簽信息具有一致性,對測試樣本集中的服務進行人工標注.實驗環(huán)境為PC機、Windows10系統(tǒng)、Corei7處理器、8GB運行內(nèi)存,仿真程序用Matlab編寫.
本實驗的目的是對文中所提出模型有效性的驗證.模型的評價指標為平均準確率P,平均召回率Re和F值.其中平均準確率P反映模型的精準度,平均召回率Re反映召回目標類別的比例,而F值則綜合準確率與召回率反映模型整體性能.公式如下所示:
5.2.1 Tri-training算法改進前后效果對比
本實驗的目的是驗證Tri-training算法與本文中所提基于歐式距離約束Con-Tri-training算法在服務準確率上的比較.實驗中首先隨機對訓練集中20%的數(shù)據(jù)進行人工標注記為X.基于Con-Tri-training算法利用訓練集X,訓練分類器G(xi,X(A)),將沒有歐式距離 Con-Tri-training算法所訓練分類器記為 G'(xi,X(A)).利用分類器 G(xi,X(A))、G'(xi,X(A))對測試集中的樣本進行預測,準確率如圖2所示.
圖2 Tri-training模型與Con-Tri-training模型Fig.2 Tri-training model and Con-Tri-training model
圖3 半監(jiān)督?jīng)Q策樹模型與Con-Tri-training模型Fig.3 Semi-supervised decision tree model and Con-Tri-training model
從圖3可以看出,相較于半監(jiān)督?jīng)Q策樹算法,Con-Tritraining算法在服務標簽1到標簽5上的分類準確率均有明顯的提高.這表明所提出的Con-Tri-training算法相較于半監(jiān)督?jīng)Q策樹算法所訓練的分類器在服務分類任務上有著更高的分類準確率.
5.2.3 Con-Tri-training算法與半監(jiān)督隨機森林算法
本實驗的目的是將Con-Tri-training算法與半監(jiān)督隨機森林算法在服務測試集各標簽上的準確率進行對比.利用訓練集X基于算法4訓練隨機森林分類器H(xi,X(A)),并用該分類器對測試集服務進行預測得到在個標簽上的分類準確率.如圖4所示.
圖4 Con-Tri-training模型與半監(jiān)督隨機森林模型Fig.4 Con-Tri-training model and semi-supervised random forest model
從圖4可以看出,半監(jiān)督隨機森林算法相較于Con-Tritraining算法,有著更高的分類準確率.這表明通過增加決策樹個數(shù),并隨機抽樣訓練集屬性構(gòu)造隨機森林分類器可以防止模型的過擬合,提高模型的泛化能力,進而提高模型的準確率.
5.2.4 半監(jiān)督隨機森林算法與半監(jiān)督SVM算法
考慮到SVM(Support Vector Machine)作為機器學習中的高效分類算法[20],有著廣泛的應用,為此還將文中的方法與SVM進行對比.基于訓練集X訓練SVM分類器,并利用所訓練分類器對測試集中的樣本進行預測,每個標簽上的準確率如圖5所示.
圖5 半監(jiān)督SVM模型與半監(jiān)督隨機森林模型Fig.5 Semi-supervised SVM model and semi-supervised random forest model
從圖5可以看出,隨機森林分類器在分類準確率更高.同時相對于SVM分類器模型,隨機森林分類器模型更加簡單,建模時間更短,可以更加高效地完成對服務的分類,因此證明本文所提出算法更加高效.
根據(jù)以上實驗的結(jié)果,列出上述5種方法的準確率、召回率和F值的具體情況,如表1所示.
表1 決策樹、Tri-training、Con-Tri-training、SVM、隨機森林性能比較Table 1 Decision tree,Tri-training,Con-Tri-training,SVM,Random forest performance comparison
由表1可知,4.3.2所提出的半監(jiān)督隨機森林模型在模型在分類準確率、召回率和F值三個指標上優(yōu)于DT、Tri-training、Con-Tri-training、SVM,證明所提出的構(gòu)造隨機森林分類器模型可以更好地抗過擬合提高分類指標,因此將該隨機森林模型作為最終的信譽度量模型.
本實驗的目的是為了驗證剪枝處理可以對抗模型的過擬合同時提高模型的泛化性能,從模型準確率、建模時間等角度來進行驗證.為了避免半監(jiān)督學習等因素對實驗的影響,在訓練集X中隨機的在選擇250個服務樣本并對其進行標注,選擇300個服務樣本作為測試樣本.
不經(jīng)過剪枝處理,所訓練的分類器的分類準確率P為83.21%,創(chuàng)建模型的開銷為1.31s.而經(jīng)過對所訓練的決策樹分類器模型進行剪枝處理后,模型的準確率P為88.71%,有了明顯的提高,而模型創(chuàng)建的開銷為3.94s,如表2所示.
表2 決策樹剪枝前后的模型比較Table 2 Comparison of models before and after decision tree pruning
從表2結(jié)果可看出,剪枝處理后的分類器模型的準確率有所提高,但相應的建模時間變長.這是由于剪枝處理對建模好的模型進行處理,因此會有額外的時間消耗.模型的準確率的提高是因為剪枝處理可以防止模型的過擬合,提高模型的泛化能力,因此通過剪枝處理可以在犧牲建模時間的同時提高模型的抗泛化能力.
本實驗的目是通過集成決策樹所構(gòu)造的隨機森林分類器模型相對于支持向量機(SVM)模型在時間與分類準確率上的高效性的驗證.從實驗數(shù)據(jù)中隨機選擇250個服務作為訓練樣本,300個服務作為測試樣本.
表3 隨機森林與SVM模型的效率比較Table 3 Comparison of efficiency between random forest and SVM model
實驗結(jié)果表明如表3所示,在模型創(chuàng)建以及分類時間消耗方面:如果使用隨機森林算法模型的時間開銷僅僅為0.62s,而如果使用SVM 則時間開銷為110.40s.在預測準確率方面SVM的準確率達到了94.67%,而隨機森林的預測準確率則為93.33%.由此可見SVM分類器模型在分類精度上比隨機森林略高,而在時間效率方面兩個分類器模型則表現(xiàn)出非常大的差別,隨機森林模型的建模時間開銷非常小,而SVM模型的時間開銷相應的要大得多.這是因為SVM模型在分類中通過高維映射將數(shù)據(jù)劃分開,因此需要花費大量的時間作為代價,而隨機森林直接通過集成服務的屬性信息對服務進行分類.因此在時間效率要求高的分類任務中隨機森林具有絕對的優(yōu)勢.
本文研究了基于半監(jiān)督學習的在線服務信譽度量方法,通過將對服務的信譽度量問題建模成對服務的分類問題,基于服務的多維度屬性信息實現(xiàn)對服務的分類.訓練服務的分類器模型需要大量的標記樣本,但網(wǎng)絡上很難直接獲取到大量標記樣本,因此本文采用半監(jiān)督的學習算法,而為了防止在學習過程中錯誤的預測服務樣本加入到訓練集而對分類器的準確率造成嚴重影響,提出基于距離約束的Con-Tri-training半監(jiān)督學習算法,算法通過加入樣本間距離約束來對預測樣本進行判斷,提高半監(jiān)督學習過程中所訓練模型的準確率,通過將所預測的服務樣本加入到訓練集中不斷地優(yōu)化分類器模型性能.最后通過對Con-Tri-training的抗過擬合處理提出半監(jiān)督隨機森林算法來進一步提高模型對服務的分類性能.
由于人工標注樣本可能存在人為因素導致的偏差和不準確,后續(xù)將進一步研究如何減少人工標注環(huán)節(jié)對模型的影響,進一步提高模型效果.