楊體東，付曉東,2，劉 驪，岳 昆，劉利軍，馮 勇

1(昆明理工大學(xué) 信息工程與自動化學(xué)院， 昆明 650500)2(昆明理工大學(xué) 航空學(xué)院， 昆明 650500)3(云南大學(xué) 信息學(xué)院， 昆明 650091)

1 引 言

隨著互聯(lián)網(wǎng)和普適計算技術(shù)的不斷發(fā)展，在線服務(wù)因獲取便利、操作簡單、成本低廉而得到廣泛應(yīng)用，并成為當(dāng)今服務(wù)產(chǎn)業(yè)發(fā)展的主要驅(qū)動力[1].然而在面對大量相同功能的服務(wù)時如何做出合理選擇，使得用戶不僅要考慮功能方面的需求，而且還要考慮到非功能屬性服務(wù)質(zhì)量(Quality of Service, QoS)的需求[2,3].信譽作為衡量QoS的一個重要指標(biāo)，在服務(wù)選擇時已成為用戶參考的主要信息之一.但由于網(wǎng)絡(luò)環(huán)境的開放性、動態(tài)性和時空上分離等特征，不能保證所有在線發(fā)布的服務(wù)都是客觀、真實、可信的[4,5].因此，研究一種客觀的在線服務(wù)信譽度量方法來反映服務(wù)的實際信譽狀況，受到行業(yè)許多研究者的廣泛關(guān)注.

雖然目前提出的許多解決方案在信譽度量的準(zhǔn)確性和客觀性上已有很大的提升，但大多數(shù)在線服務(wù)信譽度量模型是單維度的[6,7]，信譽度量只對歷史交易給出單一的評價，并不區(qū)分服務(wù)的各維度屬性質(zhì)量，評價粒度較粗，難以客觀反映服務(wù)的實際綜合表現(xiàn).其次，單維度信譽度量模型可識別的屬性信息結(jié)構(gòu)單一，對于屬性質(zhì)量描述方式不同，使其對數(shù)據(jù)異構(gòu)的服務(wù)環(huán)境缺乏適應(yīng)性.因此，綜合服務(wù)的多維度評價信息進(jìn)行信譽度量，可以獲得更為客觀、合理的信譽度量結(jié)果，增強信譽度量模型的適應(yīng)性.

本質(zhì)上，信譽度量可視為一個對不同信譽類別的服務(wù)分類，而機器學(xué)習(xí)的優(yōu)勢是可以利用訓(xùn)練樣本，在多維空間中構(gòu)造最優(yōu)分類器模型，既可以綜合服務(wù)的多維度評價信息做出信譽決策，又可以提高信譽度量模型在屬性信息異構(gòu)的服務(wù)環(huán)境中的適應(yīng)性.由于在構(gòu)造服務(wù)分類器模型時，假設(shè)事先已經(jīng)存在一定數(shù)量的訓(xùn)練樣本(具有明確信譽類標(biāo)簽的樣本)，但在實際網(wǎng)絡(luò)環(huán)境中，很難獲得大量的訓(xùn)練樣本，人工標(biāo)注數(shù)量有限，僅依靠少量的訓(xùn)練樣本數(shù)據(jù)難以準(zhǔn)確描述實際的數(shù)據(jù)分布規(guī)律，因而無法建立有效的信譽度量模型.而獲取大量的未標(biāo)注樣本則相對容易，但它們不能體現(xiàn)數(shù)據(jù)的分布規(guī)律而且隱藏著服務(wù)的判別信息.因此，使用半監(jiān)督機器學(xué)習(xí)方法，同時利用少量人工標(biāo)注樣本和大量未標(biāo)注樣本來訓(xùn)練分類器模型，可有效解決較少訓(xùn)練樣本情況下分類器模型欠學(xué)習(xí)的問題.

根據(jù)以上分析，本文提出一種基于多分類SVM的在線服務(wù)信譽度量方法.該方法以支持向量機(Support Vector Machine, SVM)理論為基礎(chǔ)，建立服務(wù)的SVM多分類器模型，通過半監(jiān)督機器學(xué)習(xí)訓(xùn)練SVM分類器，同時，為提高模型的泛化能力對屬性特征進(jìn)行降維，最終獲得具有較高分類性能的SVM多分類器模型對服務(wù)進(jìn)行分類，以實現(xiàn)信譽度量綜合多維度評價信息.最后，通過實驗驗證本文信譽度量方法的有效性和高效性.

2 相關(guān)工作

用戶的反饋信息是用戶對服務(wù)體驗的直觀表達(dá)，基于用戶評價的信譽度量成為在線服務(wù)信譽評估的主要研究方向.常見的基于用戶評價的信譽度量方式有簡單/平均模型、貝葉斯模型、模糊模型和離散信任模型等，文獻(xiàn)[8]對這些方法進(jìn)行了全面的綜述.例如，eBay 使用求和法，將用戶反饋的評分進(jìn)行求和運算計算服務(wù)信譽.Amazon 使用平均法，根據(jù)用戶反饋評分進(jìn)行平均值運算計算服務(wù)信譽.此外，文獻(xiàn)[9]參考社會學(xué)的信任模型，利用量化主體能力屬性提升信任評估的準(zhǔn)確性.在此基礎(chǔ)上，設(shè)計了Web服務(wù)信任評估模型(ServTrust)，且提出了ServTrust的一種基于多代理的解決策略.文獻(xiàn)[10]提出一種事件驅(qū)動和規(guī)則驅(qū)動的信譽管理框架.根據(jù)事物中發(fā)生的事件，利用規(guī)則確定使用的公式和參數(shù).此外，還通過模糊邏輯確定信譽排序.文獻(xiàn)[11]通過用戶對服務(wù)評價獲得直接信任值，由推薦用戶得到間接信任值，最后整合直接信任值和間接信任值得到服務(wù)信譽.上述研究均只針對服務(wù)主體做出單一的評價，并不區(qū)分服務(wù)的各維度屬性質(zhì)量，得到的信譽度量結(jié)果不夠客觀.

為解決信譽度量評價維度單一的問題，文獻(xiàn)[12]在計算直接信任度時，綜合服務(wù)的多維度屬性評價進(jìn)行信譽度量，使用交易評體系和評價權(quán)重體系較好地體現(xiàn)了個人主觀偏好、風(fēng)險態(tài)度等因素.文獻(xiàn)[13]提出了一種基于用戶屬性的細(xì)度化聲譽的評價體系，使得用戶可以對其他用戶的屬性進(jìn)行評價，而不對用戶身份進(jìn)行評價，避開了身份的影響，提高了評價的可信度.文獻(xiàn)[14]將服務(wù)不同方面的反饋評價作為推理證據(jù)，基于證據(jù)推理的方法計算服務(wù)的直接信譽度和服務(wù)聲譽的間接信譽度，綜合直接信譽度和間接信譽度對服務(wù)的信譽值進(jìn)行整合計算.上述研究在信譽度量的客觀性和合理性上獲得一定的提高，但信譽度量方法只針對用戶評分進(jìn)行信譽計算，不能對反饋信息中其他形式的評價進(jìn)行識別和處理，使得可考慮的屬性特征受到一定的限制.

基于服務(wù)QoS歷史表現(xiàn)的信譽度量，是服務(wù)信譽評估的另一個方向.文獻(xiàn)[15]認(rèn)為在線服務(wù)信譽是由用戶評分、QoS依從性和真實性組成的向量，其中依從性反映服務(wù)提供者履行其服務(wù)協(xié)議的能力，真實性反映服務(wù)提供者持續(xù)提供一定QoS的能力.文獻(xiàn)[16]在服務(wù)選擇中提出一種結(jié)合服務(wù)提供者承諾QoS值、用戶反饋QoS值以及可信代理監(jiān)控到QoS值的信譽模型.文獻(xiàn)[17]基于QoS屬性在服務(wù)管理中的角色，將信譽度劃分為領(lǐng)域無關(guān)QoS屬性的配置管理類型，同時給出信譽度的計算方式.上述方法基于服務(wù)QoS質(zhì)量進(jìn)行信譽評價，而均未考慮服務(wù)功能方面的屬性特征，評價粒度較粗，信譽度量不夠合理.

綜上所述，已有在線服務(wù)信譽度量方法的局限性，使得信譽度量評價維度單一，粒度較粗，不能客觀地反映服務(wù)的實際信譽狀況.由于機器學(xué)習(xí)可利用訓(xùn)練樣本，在多維空間中構(gòu)造最優(yōu)分類器模型，通過考慮服務(wù)的多維度屬性特征而不是特定的屬性維度進(jìn)行信譽度量，為此，本文提出的基于多分類SVM的在線服務(wù)信譽度量方法可有效彌補已有研究中的不足.

3 問題描述

本文研究的主要問題是：如何根據(jù)服務(wù)的多維度評價信息度量服務(wù)的實際信譽狀況.而信譽度量可視為一個對不同信譽類別的服務(wù)分類問題，所以本文將基于多維度評價信息的信譽度量問題轉(zhuǎn)化為在多維空間中的服務(wù)分類.通過機器學(xué)習(xí)方法利用訓(xùn)練樣本，在多維空間中構(gòu)造最優(yōu)分類器模型對服務(wù)分類，以實現(xiàn)信譽度量綜合多維度評價信息，相關(guān)定義如下：

定義1.服務(wù)樣本.在線服務(wù)數(shù)據(jù)可表示為Service=〈X,A,Y〉，X={x1,x2,…,xi,…,xm}(1≤i≤m)為服務(wù)的有限集；A={a1,a2,…,ad,…,an}(1≤d≤n)為屬性的有限集；Y={y1,y2,…,yj,…,yq}(1≤j≤q)為類標(biāo)簽的有限集.其中，一個服務(wù)樣本實例可表示為：xi={a1,a2,…,ad,…,an}.

定義2.多維度評價信息.是指用戶通過服務(wù)體驗后，對服務(wù)各維度屬性A={a1,a2,…,ad,…,an}作出的評價，可表示為xi(A)={xi(a1),xi(a2),…,xi(ad),…,xi(an)}，其中xi(ad)代表用戶對服務(wù)xi的第d個屬性的評價.

定義3. 信譽.信譽是眾多服務(wù)QoS屬性中的一種屬性，它是對服務(wù)表現(xiàn)的綜合度量，通過綜合服務(wù)的多維度評價信息xi(A)={xi(a1),xi(a2),…,xi(ad),…,xi(an)}對所提供服務(wù)xi可信賴程度較為全面的一個量化表達(dá)，記為Y.

其中，可將信譽Y按需要劃分為q個區(qū)間來代表不同的信譽類別.例如：當(dāng)q=5時，表示將信譽劃分為5個類別，信譽類標(biāo)簽1～5分別表示信譽很差、差、一般、好和很好.因此，q個區(qū)間的劃分可得到q個不同的信譽類標(biāo)簽，記為Y={y1,y2,…,yj,…,yq}(1≤j≤q).

定義4.訓(xùn)練樣本.為服務(wù)樣本xi指定一個信譽類標(biāo)簽yj∈Y，形成一個具有明確信譽類標(biāo)簽的樣本實例s={xi,yj}，該樣本實例可作為訓(xùn)練樣本加入到訓(xùn)練樣本集中，所有訓(xùn)練樣本的集合記為S.

定義5.服務(wù)分類.對于所有的服務(wù)xi都有一個唯一確定的信譽類標(biāo)簽yj，根據(jù)不同的信譽類標(biāo)簽可以將服務(wù)分為不同的類別，進(jìn)而實現(xiàn)信譽度量.

機器學(xué)習(xí)可以利用訓(xùn)練樣本{xi,yj}，在多維空間中構(gòu)造最優(yōu)分類器模型，實現(xiàn)對服務(wù)的最優(yōu)分類.考慮到獲取訓(xùn)練樣本比較有限，當(dāng)訓(xùn)練樣本較少時，樣本不足以反映數(shù)據(jù)的實際分布，訓(xùn)練出的分類器性能將受到較大的影響.本文使用半監(jiān)督機器學(xué)習(xí)，從大量未標(biāo)注樣本中獲取新的訓(xùn)練樣本來擴充訓(xùn)練集，進(jìn)一步提高分類器模型性能.

根據(jù)定義，由訓(xùn)練樣本集訓(xùn)練出的分類器模型對服務(wù)進(jìn)行分類時，所考慮的是整個服務(wù)的屬性信息而不是某個選定的屬性特征，從而能較好地進(jìn)行服務(wù)分類.因此，在線服務(wù)信譽度量問題描述為：給定服務(wù)樣本集和機器學(xué)習(xí)方法構(gòu)建服務(wù)的多分類器模型，通過半監(jiān)督機器學(xué)習(xí)訓(xùn)練分類器模型，根據(jù)最終得到的服務(wù)多分類器模型對服務(wù)進(jìn)行分類，獲得服務(wù)的信譽類標(biāo)簽.

4 基于多分類SVM的在線服務(wù)信譽度量

由于單維度信譽度量方法的局限性，不能客觀反映服務(wù)的實際信譽狀況，綜合多維度評價信息進(jìn)行信譽度量，可有效提高信譽度量的客觀性和合理性.為此，本文提出一種基于多分類SVM的在線服務(wù)信譽度量方法，將基于多維度評價信息的信譽度量轉(zhuǎn)換為在多維空間中對不同信譽類別的服務(wù)分類.基于機器學(xué)習(xí)的方式，利用訓(xùn)練樣本在多維空間中構(gòu)造服務(wù)的SVM分類器模型對服務(wù)分類，以實現(xiàn)信譽度量綜合多維度評價信息.

圖1 基于多分類SVM的信譽度量框圖Fig.1 Framework of reputation measurement based on multi-classification SVM

SVM作為機器學(xué)習(xí)中一種常用的構(gòu)造分類器算法，其通過結(jié)構(gòu)風(fēng)險最小化原理提高泛化能力.引入核函數(shù)將樣本映射到線性可分的高維空間，最終可以轉(zhuǎn)化為凸優(yōu)化問題，獲得全局最優(yōu)解[18]，成為解決分類問題的有效方法.將SVM應(yīng)用于在線服務(wù)信譽度量中，較之常規(guī)的信譽度量方法主要有兩方面的優(yōu)勢：首先是易于增加更多的信譽判別特征，獲得更多包含重要信譽決策信息的支持向量，使得信譽度量結(jié)果更加客觀、合理.其次，由于服務(wù)樣本往往具有維數(shù)高、樣本數(shù)小和數(shù)據(jù)多源異構(gòu)等特點，與常規(guī)信譽度量算法相比，SVM可以更好地解決小樣本、非線性、信譽數(shù)據(jù)多源異構(gòu)等問題，實現(xiàn)對服務(wù)的最優(yōu)分類，更適合被應(yīng)用于信譽度量中.

本文提出的基于多分類SVM的在線服務(wù)信譽度量總流程如圖1所示.方法分為離線訓(xùn)練和服務(wù)信譽在線度量兩個階段.在離線訓(xùn)練過程中，首先基于SVM的服務(wù)多分類問題建模；然后，使用半監(jiān)督機器學(xué)習(xí)訓(xùn)練SVM分類器模型，提高SVM分類器模型的分類性能.而服務(wù)信譽在線度量過程利用前者離線訓(xùn)練的結(jié)果，計算量小，保證了在線服務(wù)信譽實時度量的快速性.

4.1 基于SVM的服務(wù)多分類問題建模

由于服務(wù)信譽標(biāo)簽不止兩種(Y>2)，所以本文中的服務(wù)分類是一個多分類問題，而SVM分類算法是針對二分類問題提出的，因此，需要將服務(wù)多分類問題轉(zhuǎn)化為二分類問題.

根據(jù)定義4，可知訓(xùn)練樣本集為S，假設(shè)訓(xùn)練樣本集中有i個訓(xùn)練樣本實例，則S={s1,s2,…,si}.對于一個訓(xùn)練樣本實例s={xi,yj}，xi={a1,a2,…,ad,…,an}為n維的特征向量，yj∈{y1,y2,…,yq}.

SVM在解決多分類問題時需要構(gòu)造多個二分類器，常采用的方法有：一對一分類(One Versus One，OVO)、一對多分類(One Versus All，OVA)[19].由于OVA方法會導(dǎo)致樣本集中不同類標(biāo)簽分布的非均衡性，本文采用OVO方法實現(xiàn)多分類.對于本文中服務(wù)q分類(q>2)問題，按下式構(gòu)造服務(wù)二分類訓(xùn)練樣本集D.

D[k,l]={(xi,yj′=2yi=k-1)|yi=k或yj=l}

(1)

式(1)中：k,l=1,2,…,q.算子·根據(jù)等式是否成立返回1或0.因此，對于服務(wù)的q分類問題需要構(gòu)造q(q-1)/2個二分類訓(xùn)練樣本集.例如，用于信譽標(biāo)簽為1和2的二分類訓(xùn)練樣本集D[1,2]是從訓(xùn)練樣本集S中剔除信譽標(biāo)簽為3,4,…,q的樣本，保留信譽標(biāo)簽為1,2的樣本組成.另外其他信譽標(biāo)簽組的二分類訓(xùn)練樣本集D[k,l](k,l=1,2,…,q)以同樣的方式形成.

根據(jù)以上所述，對于服務(wù)q分類訓(xùn)練樣本集將訓(xùn)練生成q(q-1)/2個二分類器，記為C[k,l](k,l=1,2,…,q).針對每個未知服務(wù)樣本，每個二分類器都將得到一個預(yù)測類標(biāo)簽.通過投票法組合這些二分類器預(yù)測結(jié)果，即累積次數(shù)最多的類標(biāo)簽就是該未知服務(wù)的最終預(yù)測類標(biāo)簽，從而得到該服務(wù)的信譽度量結(jié)果.

4.2 半監(jiān)督機器學(xué)習(xí)訓(xùn)練SVM分類器模型

由于在實際運用中，獲取大量具有明確信譽類標(biāo)簽的訓(xùn)練樣本比較困難，考慮到當(dāng)訓(xùn)練樣本較少時，樣本不足以反映服務(wù)數(shù)據(jù)的實際分布，并且訓(xùn)練出的SVM的決策函數(shù)在多維空間中容易產(chǎn)生過擬合，使得SVM分類器性能受到較大的影響，為解決該問題本文基于半監(jiān)督機器學(xué)習(xí)訓(xùn)練SVM分類器模型.首先由人工標(biāo)注獲取少量的初始訓(xùn)練樣本訓(xùn)練SVM分類器模型，然后通過自學(xué)習(xí)方法在大量未標(biāo)注樣本中進(jìn)一步獲取新的訓(xùn)練樣本來擴充訓(xùn)練樣本集，重新訓(xùn)練SVM分類器模型，并對整個自學(xué)習(xí)過程進(jìn)行循環(huán)迭代，不斷提高SVM分類器模型性能.為盡可能減少錯誤訓(xùn)練樣本的加入影響分類器模型性能，本文對自學(xué)習(xí)方法加以改進(jìn)，提出一種帶距離約束條件的自學(xué)習(xí)方法DST(Distance Self-Training，DST).

4.2.1 初始訓(xùn)練樣本選擇及分類器模型訓(xùn)練

已知訓(xùn)練樣本集為S(S=?)，假設(shè)未標(biāo)注樣本集為U，在初始分類時從U中隨機選擇z個服務(wù)樣本，由用戶對其進(jìn)行人工標(biāo)注，將該服務(wù)樣本集合記為L={(xi,yj)}(i=1,2,…,z，yj∈Y).更新訓(xùn)練樣本集S和未標(biāo)注樣本集U：S=L，U=U-L，得到初始訓(xùn)練樣本集S=L={(xi,yj)}(i=1,2,…,z，yj∈Y).使用初始訓(xùn)練樣本集S訓(xùn)練SVM分類器模型.同時，對未標(biāo)注樣本集U中的樣本類標(biāo)簽進(jìn)行預(yù)測.

在少量訓(xùn)練樣本的情況下，直接學(xué)習(xí)SVM分類器屬于欠學(xué)習(xí)問題[20]，得到的分類器模型性能較差.因此，通過自學(xué)習(xí)進(jìn)一步在大量未標(biāo)注樣本下訓(xùn)練SVM分類器提高分類器性能.

4.2.2 DST半監(jiān)督學(xué)習(xí)

自學(xué)習(xí)是半監(jiān)督學(xué)習(xí)中一種常見的技術(shù)，首先由人工標(biāo)注少量的初始訓(xùn)練樣本訓(xùn)練得到分類器，然后，通過這個分類器對未標(biāo)注樣本信譽類標(biāo)簽進(jìn)行判斷，將分類結(jié)果最確定的未標(biāo)注樣本，連帶其對應(yīng)的由分類器預(yù)測得到的類標(biāo)簽一起，加入到當(dāng)前的訓(xùn)練集中.用擴充后的訓(xùn)練樣本集重新訓(xùn)練分類器，并對分類結(jié)果進(jìn)行更新[21].

由于添加到訓(xùn)練樣本集中的樣本類標(biāo)簽是由分類器預(yù)測得到的，因此得到的預(yù)測樣本類標(biāo)簽與真實類標(biāo)簽就有不一致的風(fēng)險，即預(yù)測錯誤風(fēng)險，那么該錯誤會在迭代的過程中不斷累積增加，對分類器準(zhǔn)確預(yù)測樣本類標(biāo)簽造成嚴(yán)重影響.為了盡可能減少自學(xué)習(xí)過程中錯誤樣本的加入，提高分類器的分類性能，本文對自學(xué)習(xí)方法進(jìn)行改進(jìn)，提出一種帶距離約束條件的自學(xué)習(xí)方法DST.在分類器預(yù)測樣本類標(biāo)簽的同時加入樣本間距離的約束條件來共同判斷，提高自學(xué)習(xí)選出的訓(xùn)練樣本類標(biāo)簽的準(zhǔn)確性.對于當(dāng)前的每個未標(biāo)注樣本xu(xu∈U)作如下判斷：

1) 使用當(dāng)前的SVM分類器對樣本xu的信譽類標(biāo)簽判斷，得到樣本xu的信譽類標(biāo)簽yu，即yu/xu.

2) 基于歐式距離計算xu與訓(xùn)練樣本集S中所有樣本的距離D(xu,xi)，尋找與xu最鄰近的點記為N：

N=argminxi∈SD(xu,xi)

(2)

將該臨近點N的信譽類標(biāo)簽記為yn，即yn/N.

3) 比較未標(biāo)注樣本xu的信譽類標(biāo)簽yu和最臨近點N的信譽類標(biāo)簽yn，對樣本xu做出決策：

(3)

如果yu=yn時，將樣本xu連帶信譽類標(biāo)號一起添加到訓(xùn)練樣本集合S中；如果yu≠yn時，將樣本xu返回到未標(biāo)注樣本集U.

從距離相關(guān)性的自學(xué)習(xí)過程中可以看出，未知樣本的信譽類標(biāo)簽不僅由分類器預(yù)測得到，還通過樣本間距離的約束條件來共同判斷，從而保證了自學(xué)習(xí)添加到訓(xùn)練集里的樣本類標(biāo)簽具有較高的準(zhǔn)確率.

4.2.3 訓(xùn)練樣本集及分類器模型更新

用新選出來的訓(xùn)練樣本xu對訓(xùn)練樣本集S和未標(biāo)注樣本集U進(jìn)行更新，即S=S∪xu，U=U-xu.用更新后的訓(xùn)練樣本集S重新訓(xùn)練SVM分類器模型，并對整個距離相關(guān)性的自學(xué)習(xí)過程進(jìn)行循環(huán)迭代.

直觀上來說，雖然帶距離約束條件的自學(xué)習(xí)選擇出的訓(xùn)練樣本所包含的信息量可能不高，但能有效降低引入錯誤類標(biāo)簽的概率，提高分類器模型的分類性能.同時，隨著循環(huán)迭代過程不斷從未知樣本中獲取新的樣本加入到訓(xùn)練樣本集中，樣本的信息量也將不斷得到完善，因此，帶距離約束條件的自學(xué)習(xí)可有效提高分類器性能.

基于以上分析，得到半監(jiān)督機器學(xué)習(xí)訓(xùn)練SVM分類器模型的算法如下：

算法1.半監(jiān)督機器學(xué)習(xí)訓(xùn)練SVM分類器模型算法

輸入：L：人工標(biāo)注樣本集；U：未標(biāo)注樣本集；

輸出：SVM分類器模型model.

1.S=?;

2.S.add(L);

//選擇初始訓(xùn)練樣本選擇

3.WHILEU≠?DO

4.model=Learn(S); //初始SVM分類器訓(xùn)練

5.FORxu∈UDO

6.yu=mdoel(xu);

7.FOReveryxi∈SDO

8.D(xu,xi)=EuclideanDistance(xu,xi)

//公式(2)

9.ENDFOR

10.N=argminD(xu,xi);

//公式(2)

11.yn=examplelabelofN;

12.IF(yu==yn)THEN//距離約束條件(3)成立

13.S.insert(xu);

14.ELSEU.back(xu);

15.ENDIF

16.ENDFOR

17.ENDWHILE

18.RETURNmodel;

4.3 提高SVM分類器的泛化能力

提高服務(wù)多分類器模型的分類精度和泛化能力是機器學(xué)習(xí)原理能夠在信譽度量中得以應(yīng)用的關(guān)鍵.文獻(xiàn)[22]指出，SVM中的VC(Vapnik-Chervonenkis)維越小，模型的泛化能力越強，減少特征數(shù)量是降維的有效方法，并通過實驗證明了，使用主成分分析法(Principal Components Analysis，PCA)降低特征維數(shù)和交叉驗證聯(lián)合優(yōu)化的方式，可有效提高分類器模型的泛化能力.因此，本文應(yīng)用PCA進(jìn)行特征提取實現(xiàn)降維，結(jié)合交叉驗證來提高分類器模型的泛化能力.

4.3.1 特征提取

由定義1可知，已知服務(wù)xi的屬性有限集為A={a1,a2,…,ad,…,an}(1≤d≤n)，為n維特征向量，然后使用PCA方法對屬性特征A={a1,a2,…,ad,…,an}進(jìn)行降維.從得到的各主成分子集中選擇影響信譽變化的主成分，剔除與信譽變化無關(guān)的主成分達(dá)到降維的目的.

PCA是一種經(jīng)典的數(shù)據(jù)降維算法，用盡可能少的相互獨立的數(shù)據(jù)表示原始數(shù)據(jù)的主要信息.通過PCA降維后不僅可以提高SVM分類器模型的泛化能力，同時還可以降低服務(wù)樣本的特征維數(shù)、簡化數(shù)據(jù)結(jié)構(gòu)、有效降低分類器模型創(chuàng)建的時間復(fù)雜度和空間復(fù)雜度，進(jìn)而提高SVM分類器模型的效率.

4.3.2 交叉驗證

如果分類和測試都來自同一數(shù)據(jù)集，會出現(xiàn)過于樂觀的訓(xùn)練誤差.為了提高服務(wù)多分類器模型的泛化能力，交叉驗證將服務(wù)樣本集分為訓(xùn)練集和測試集，分別用作模型的生成和測試，以此作為評價SVM分類器性能的指標(biāo).

核函數(shù)參數(shù)以及懲罰系數(shù)對SVM分類器模型的泛化精度有著很大的影響.交叉驗證的核心思想是從原始數(shù)據(jù)集中尋找優(yōu)化核函數(shù)參數(shù)的有用信息.本文采用的SVM核函數(shù)為徑向基核函數(shù)：K(xi,x)=e-γ‖x-xi ‖2.利用網(wǎng)格搜索法[23]，結(jié)合10折交叉驗證對RBF核函數(shù)中的懲罰參數(shù)C和核函數(shù)參數(shù)g進(jìn)行尋優(yōu).

5 實驗與分析

為驗證本文提出的基于多分類SVM的在線服務(wù)信譽度量方法的有效性，對測試樣本集進(jìn)行信譽度量實驗，分別從測試集每個類別各自的度量準(zhǔn)確率、總體度量準(zhǔn)確率、特征提取有效性3個方面對本方法的性能進(jìn)行評估，并將本文方法SVM+DST與單維度信譽度量方法TMMRN(Trust Management Model Based Reputation Nodes)[11]、多維度信譽度量方法RMDT(Reputation-Based Multi-Dimensional Trust)[12]以及本文方法自學(xué)習(xí)時不考慮距離約束條件的方法SVM+ST這3種方法的性能進(jìn)行比較.

5.1 實驗環(huán)境及數(shù)據(jù)集

本實驗爬取了中國最大的網(wǎng)購零售平臺淘寶網(wǎng)中1632個在線商家最近6個月交易的評價統(tǒng)計量，整個數(shù)據(jù)集包括10個商品種類商家的16維屬性特征評價.為了準(zhǔn)確評估機器學(xué)習(xí)算法的有效性，測試樣本獨立于訓(xùn)練樣本.其中，從數(shù)據(jù)集中隨機抽取80%的數(shù)據(jù)作為未標(biāo)注樣本集，20%的數(shù)據(jù)作為測試樣本集.需要說明的是，為保證實驗方案的合理性，測試樣本的信譽類標(biāo)簽與人工標(biāo)注的類標(biāo)簽應(yīng)具有一致的主觀偏好性，因此對測試樣本集進(jìn)行人工標(biāo)注，實驗數(shù)據(jù)如表1所示.

表1 訓(xùn)練樣本集和測試樣本集Table 1 Training sample set and test sample set

實驗采用MATLAB 2014a+LibSVM工具包實現(xiàn)，在一臺配置為Inter(R) Core(TM) i3-2120 3.3 GHz CPU、8 GB RAM的PC機上運行，操作系統(tǒng)為Windows 10專業(yè)版.LibSVM作為實現(xiàn)SVM的一種常用工具包，采用OVO的方式來解決多分類問題，并提供多種核函數(shù)選擇和交叉驗證參數(shù)尋優(yōu)[24]，能快速、有效地實現(xiàn)所設(shè)實驗方案.針對實驗數(shù)據(jù)存在噪聲的問題，本文通過剔除數(shù)據(jù)不完全的樣本、對樣本進(jìn)行PCA降維、均衡各類別樣本數(shù)目等方法進(jìn)行數(shù)據(jù)預(yù)處理.

5.2 評價標(biāo)準(zhǔn)

本文將基于多維度評價信息的在線服務(wù)信譽度量問題建模為對不同信譽類別的服務(wù)分類，通過機器學(xué)習(xí)方法利用訓(xùn)練樣本，在多維空間中構(gòu)造最優(yōu)SVM分類器模型對服務(wù)分類，以實現(xiàn)信譽度量綜合多維度評價信息.因此分別使用平均準(zhǔn)確率P、平均召回率R、平均綜合指標(biāo)F值來衡量方法的有效性.其中，平均準(zhǔn)確率P反映模型精度，平均召回率R反映召回目標(biāo)類別的比率、而F值則綜合準(zhǔn)確率和召回率反映SVM+DST整體的性能，具體定義如下：

設(shè)測試樣本集為T={x1,x2,…,xn}，信譽類標(biāo)簽yj∈{y1,y2,…,yq}為q個類別，TPj表示第j類被分類正確的個數(shù)，F(xiàn)Pj為第j類分類錯誤的個數(shù)，則3個指標(biāo)的計算公式如下：整個算法的平均準(zhǔn)確率：

(4)

整個算法的平均召回率：

(5)

整個算法的平均綜合指標(biāo)：

(6)

5.3 信譽度量準(zhǔn)確率

本文首先對測試樣本集中每個類別各自的度量準(zhǔn)確率進(jìn)行實驗.圖2～圖4分別給出了采用本文方法SVM+DST和其他3種方法，在測試集上各類別樣本(1～5個類別)獲得準(zhǔn)確度量的樣本數(shù)比較.圖中，橫軸表示樣本類別，縱軸表示信譽度量正確的樣本數(shù)量，柱狀代表采用SVM+DST方法與對比方法在各個類別上的度量準(zhǔn)確樣本數(shù)的差，正數(shù)代表SVM+DST在該類別上的度量準(zhǔn)確樣本數(shù)多于該對比方法.

2824201612840樣本數(shù)量樣本類別12345圖2 SVM+DST與RMDT在各類別上度量準(zhǔn)確數(shù)量的比較Fig.2 Compare SVM+DST and RMDT to measure the exact number of each type2824201612840樣本數(shù)量樣本類別12345圖3 SVM+DST與SVM+ST在各類別上度量準(zhǔn)確數(shù)量的比較Fig.3 Compare SVM+DST and SVM+ST to measure the exact number of each type2824201612840樣本數(shù)量樣本類別12345圖4 SVM+DST與TMMRN在各類別上度量準(zhǔn)確樣本數(shù)的比較Fig.4 Compare SVM+DST and TMMRN to measure the exact number of each type

從圖2～圖4中可以看出，SVM+DST方法與其他三種方法相比，在所有類別上的度量準(zhǔn)確數(shù)量都有一定程度的提升.其中，SVM+DST相對于TMMRN和SVM+ST兩種方法的度量準(zhǔn)確數(shù)量提升幅度較大，證明SVM+DST方法通過考慮服務(wù)的多維度屬性特征而不是特定的屬性維度進(jìn)行信譽度量，能有效提高信譽度量的準(zhǔn)確率.同時證明SVM+DST方法，在自學(xué)習(xí)時加入距離約束條件選擇出的訓(xùn)練樣本能夠有效地提高當(dāng)前分類器模型的分類性能.此外較之RMDT方法，SVM+DST獲得準(zhǔn)確度量的樣本數(shù)量也有少量的提升，證明SVM+DST方法在信譽度量準(zhǔn)確率上優(yōu)于RMDT方法.

根據(jù)以上實驗結(jié)果，對4種方法的總體信譽度量準(zhǔn)確率進(jìn)行分析比較，如表2所示.

表2 SVM+DST和TMMRN、RMDT、SVM+ST的準(zhǔn)確性比較Table 2 Comparison of Accuracy of SVM+DST,RMDT and SVM+ST

由表2可知，本文方法SVM+DST在準(zhǔn)確率P、召回率R、綜合指標(biāo)F值方面都要優(yōu)于RMDT、SVM+ST和TMMRN.經(jīng)過分析，主要是因為TMMRN評價維度單一，只針對服務(wù)屬性中的某一特征進(jìn)行評價，因此計算出的信譽僅局限于該屬性的質(zhì)量，而忽略了其他屬性對信譽的影響，導(dǎo)致信譽度量不夠客觀、全面.而SVM+ST在選擇訓(xùn)練樣本時，由于未考慮預(yù)測錯誤風(fēng)險，使得自學(xué)習(xí)過程中加入了大量的錯誤訓(xùn)練樣本，造成分類器分類性能下降.而RMDT方法主要適用于用戶的反饋評分，不能對服務(wù)屬性中包含的數(shù)字信息、標(biāo)簽信息等進(jìn)行識別、處理，相對SVM+DST信譽判別特征較少，因此準(zhǔn)確率和召回率有所下降.

5.4 特征選擇有效性驗證

實驗?zāi)康脑谟隍炞CPCA特征提取可提高服務(wù)SVM多分類器模型的效率，分別從SVM分類器模型的分類準(zhǔn)確率和模型創(chuàng)建的開銷時間兩方面進(jìn)行驗證.為避免半監(jiān)督自學(xué)習(xí)加入后影響實驗效果，從訓(xùn)練樣本集中選擇250個樣本作為訓(xùn)練樣本集，并對其進(jìn)行人工標(biāo)注，其中每個類別樣本各50個.通過對測試樣本集進(jìn)行分類預(yù)測，對比分析特征提取前后的分類準(zhǔn)確率和分類器模型的開銷時間，證明特征提取可有效提高模型的效率，實驗數(shù)據(jù)如表3所示.

表3 特征選擇有效性實驗數(shù)據(jù)集Table 3 Feature selection effectiveness experimental set

依據(jù)表3中訓(xùn)練集的16維屬性特征，采用SPSS19.0軟件實現(xiàn)PCA主成分分析，從16個屬性特征集中提取10個主成分，累積貢獻(xiàn)率達(dá)到87.5%.分別使用PCA特征提取前后的數(shù)據(jù)集進(jìn)行分類預(yù)測.在分類準(zhǔn)確率方面：如果不進(jìn)行特征提取，利用16維屬性特征的數(shù)據(jù)集進(jìn)行分類，分類準(zhǔn)確率為91.4%，經(jīng)過PCA特征提取后，使用10維屬性特征的數(shù)據(jù)集進(jìn)行分類，得到的分類準(zhǔn)確率為90.6%.而在模型的時間開銷方面，如果不進(jìn)行特征提取，模型創(chuàng)建的時間開銷為254.77s，經(jīng)過PCA特征提取后，模型創(chuàng)建的時間開銷為92.68s.

從上述實驗結(jié)果可以看出，特征提取后分類器的分類準(zhǔn)確率有所下降，但所下降的幅度并不大.這是因為PCA進(jìn)行特征提取后，找到一組最能描述服務(wù)樣本數(shù)據(jù)且特征維數(shù)較少的正交潛在變量，簡化了樣本內(nèi)在統(tǒng)計結(jié)構(gòu)特征，勢必會丟失原始特征空間中可以區(qū)分不同類標(biāo)簽的微弱信息，造成SVM分類器分類精度下降.然而，特征提取后分類器模型創(chuàng)建的時間開銷被極大地縮短，由此可見，PCA+SVM是通過犧牲一定的分類準(zhǔn)確率來縮短開銷時間的，在小樣本數(shù)據(jù)分類的時候可能PCA+SVM的效率不是很明顯，但在大樣本分類的環(huán)境下這種代價交易就會變得非?？捎^，能極大的縮短運算時間，減少成本.考慮到本文中信譽度量所面對的在線服務(wù)環(huán)境，綜合考慮PCA降維后的分類準(zhǔn)確率和模型的時間開銷，PCA降維可有效提高服務(wù)SVM多分類器模型的效率.

6 總結(jié)與展望

基于多維度信息的信譽度量模型對提高信譽度量的準(zhǔn)確性和合理性有重要影響.本文將信譽度量問題轉(zhuǎn)換為信譽多分類問題，使用支持向量機進(jìn)行服務(wù)多分類.由于獲取大量的訓(xùn)練樣本比較困難.我們將自學(xué)習(xí)方法引入到支持向量機分類器的服務(wù)分類中，并對自學(xué)習(xí)方法進(jìn)行改進(jìn)，確保自學(xué)習(xí)過程獲得準(zhǔn)確的訓(xùn)練樣本，通過循環(huán)迭代整個自學(xué)習(xí)過程，不斷優(yōu)化分類器模型，并由該分類器模型對服務(wù)進(jìn)行多分類，實現(xiàn)信譽度量綜合多維度屬性信息.實驗驗證該方法在服務(wù)分類時具有較高的準(zhǔn)確度.

由于自學(xué)習(xí)中的初始訓(xùn)練樣本由人工標(biāo)注獲得，因此得到的訓(xùn)練樣本可能不是最優(yōu)的，如何確保獲得高質(zhì)量的初始訓(xùn)練樣本成為下一步工作中需要考慮的問題.其次，使用PCA主成分分析法雖然可以有效降低樣本數(shù)據(jù)維數(shù)和模型開銷時間，但是會造成分類器分類精度的損失，考慮引入其他降維方法來有效減少樣本數(shù)據(jù)維數(shù)的同時，可優(yōu)化分類模型的開銷時間和分類準(zhǔn)確率將是今后工作的一個重要方向.