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

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

1 引 言

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

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

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

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

2 相關(guān)工作

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

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

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

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

3 問題描述

本文研究的主要問題是：如何根據(jù)服務(wù)的多維度評(píng)價(jià)信息度量服務(wù)的實(shí)際信譽(yù)狀況.而信譽(yù)度量可視為一個(gè)對(duì)不同信譽(yù)類別的服務(wù)分類問題，所以本文將基于多維度評(píng)價(jià)信息的信譽(yù)度量問題轉(zhuǎn)化為在多維空間中的服務(wù)分類.通過機(jī)器學(xué)習(xí)方法利用訓(xùn)練樣本，在多維空間中構(gòu)造最優(yōu)分類器模型對(duì)服務(wù)分類，以實(shí)現(xiàn)信譽(yù)度量綜合多維度評(píng)價(jià)信息，相關(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)簽的有限集.其中，一個(gè)服務(wù)樣本實(shí)例可表示為：xi={a1,a2,…,ad,…,an}.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

SVM在解決多分類問題時(shí)需要構(gòu)造多個(gè)二分類器，常采用的方法有：一對(duì)一分類(One Versus One，OVO)、一對(duì)多分類(One Versus All，OVA)[19].由于OVA方法會(huì)導(dǎo)致樣本集中不同類標(biāo)簽分布的非均衡性，本文采用OVO方法實(shí)現(xiàn)多分類.對(duì)于本文中服務(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.因此，對(duì)于服務(wù)的q分類問題需要構(gòu)造q(q-1)/2個(gè)二分類訓(xùn)練樣本集.例如，用于信譽(yù)標(biāo)簽為1和2的二分類訓(xùn)練樣本集D[1,2]是從訓(xùn)練樣本集S中剔除信譽(yù)標(biāo)簽為3,4,…,q的樣本，保留信譽(yù)標(biāo)簽為1,2的樣本組成.另外其他信譽(yù)標(biāo)簽組的二分類訓(xùn)練樣本集D[k,l](k,l=1,2,…,q)以同樣的方式形成.

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

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

由于在實(shí)際運(yùn)用中，獲取大量具有明確信譽(yù)類標(biāo)簽的訓(xùn)練樣本比較困難，考慮到當(dāng)訓(xùn)練樣本較少時(shí)，樣本不足以反映服務(wù)數(shù)據(jù)的實(shí)際分布，并且訓(xùn)練出的SVM的決策函數(shù)在多維空間中容易產(chǎn)生過擬合，使得SVM分類器性能受到較大的影響，為解決該問題本文基于半監(jiān)督機(jī)器學(xué)習(xí)訓(xùn)練SVM分類器模型.首先由人工標(biāo)注獲取少量的初始訓(xùn)練樣本訓(xùn)練SVM分類器模型，然后通過自學(xué)習(xí)方法在大量未標(biāo)注樣本中進(jìn)一步獲取新的訓(xùn)練樣本來擴(kuò)充訓(xùn)練樣本集，重新訓(xùn)練SVM分類器模型，并對(duì)整個(gè)自學(xué)習(xí)過程進(jìn)行循環(huán)迭代，不斷提高SVM分類器模型性能.為盡可能減少錯(cuò)誤訓(xùn)練樣本的加入影響分類器模型性能，本文對(duì)自學(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，在初始分類時(shí)從U中隨機(jī)選擇z個(gè)服務(wù)樣本，由用戶對(duì)其進(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分類器模型.同時(shí)，對(duì)未標(biāo)注樣本集U中的樣本類標(biāo)簽進(jìn)行預(yù)測(cè).

在少量訓(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)練得到分類器，然后，通過這個(gè)分類器對(duì)未標(biāo)注樣本信譽(yù)類標(biāo)簽進(jìn)行判斷，將分類結(jié)果最確定的未標(biāo)注樣本，連帶其對(duì)應(yīng)的由分類器預(yù)測(cè)得到的類標(biāo)簽一起，加入到當(dāng)前的訓(xùn)練集中.用擴(kuò)充后的訓(xùn)練樣本集重新訓(xùn)練分類器，并對(duì)分類結(jié)果進(jìn)行更新[21].

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

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

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

N=argminxi∈SD(xu,xi)

(2)

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

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

(3)

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

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

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

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

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

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

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

4.3.1 特征提取

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

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

4.3.2 交叉驗(yàn)證

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

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

5 實(shí)驗(yàn)與分析

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

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

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

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

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

5.2 評(píng)價(jià)標(biāo)準(zhǔn)

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

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

(4)

整個(gè)算法的平均召回率：

(5)

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

(6)

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

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

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

根據(jù)以上實(shí)驗(yàn)結(jié)果，對(duì)4種方法的總體信譽(yù)度量準(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)過分析，主要是因?yàn)門MMRN評(píng)價(jià)維度單一，只針對(duì)服務(wù)屬性中的某一特征進(jìn)行評(píng)價(jià)，因此計(jì)算出的信譽(yù)僅局限于該屬性的質(zhì)量，而忽略了其他屬性對(duì)信譽(yù)的影響，導(dǎo)致信譽(yù)度量不夠客觀、全面.而SVM+ST在選擇訓(xùn)練樣本時(shí)，由于未考慮預(yù)測(cè)錯(cuò)誤風(fēng)險(xiǎn)，使得自學(xué)習(xí)過程中加入了大量的錯(cuò)誤訓(xùn)練樣本，造成分類器分類性能下降.而RMDT方法主要適用于用戶的反饋評(píng)分，不能對(duì)服務(wù)屬性中包含的數(shù)字信息、標(biāo)簽信息等進(jìn)行識(shí)別、處理，相對(duì)SVM+DST信譽(yù)判別特征較少，因此準(zhǔn)確率和召回率有所下降.

5.4 特征選擇有效性驗(yàn)證

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

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

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

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

6 總結(jié)與展望

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

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