考慮Mean Shift用戶聚類的云服務推薦

王著鑫，耿秀麗，王龍羽，王婉婷

（上海理工大學管理學院，上海 200093）

0 引言

云計算是并行處理、網絡計算和分布式計算等技術發展融合的產物。云服務以云計算為基礎，向用戶提供按需、可計量的服務。由于云服務成本低、效率高，受到了越來越多企業和個人的青睞。云服務市場的迅速發展使得云服務種類呈現多元化趨勢。雖然用戶有了更多的選擇，但也增加了用戶選擇符合自身需求的難度，這影響的不僅僅是用戶，對云服務提供商的切身利益也造成很大影響。云服務市場規模的不斷擴大必然導致競爭者變得愈來愈多，云服務提供商為了提高自身競爭力，除了要改善云服務質量，還要將云服務高效而精準地推薦給用戶。因此，快速推薦用戶所需的云服務具有重要研究意義。

云服務推薦研究不斷深入，模糊TOPSIS時變權重二次量化云服務推薦、CSRA云服務推薦算法、基于偏好信息和信任的云服務推薦模型等方法不斷提出，在一定程度上滿足了用戶和云服務提供商需求。但是現有的云服務推薦方法依然在推薦效率、數據稀疏性、用戶評分主觀性等方面存在問題。如文獻［6］通過綜合考慮云服務的信譽度和穩定性方法來提高推薦精度，但是忽略了算法的執行時間。當用戶數量較大時，該算法效率低的劣勢就會突顯；文獻［7］采用結合信任的混雜社會網絡來緩解矩陣稀疏性問題。可是該方法計算過程復雜，不適合用來處理大數據；文獻［8］側重于處理數據稀疏性和冷啟動問題，卻沒有考慮到用戶評分的主觀性會降低推薦精度。

針對推薦效率問題，文獻［9］通過并行化Spark上CAQGS的分區操作來縮短算法的執行時間。該方法不是在算法本身上進行優化，而是通過調用平臺的方式提高推薦效率，所以不具有普適性；文獻［10］采用加權的SK-means聚類方法有效降低了算法的時間復雜度，但是SK-means聚類中心的數量和初始聚類中心的位置選取對聚類效果影響很大。而基于密度的聚類算法Mean Shift不需要人為地確定聚類中心的數量和初始聚類中心位置，它可根據數據的密度分布自動選擇聚類的數量。同時Mean Shift聚類算法計算量小、執行速度快且較穩定，因此本文使用Mean Shift聚類算法來提高推薦效率。面對龐大的項目數量，不可能每個用戶對每個項目都進行評價，由此產生的稀疏數據會降低推薦精度。針對數據稀疏性問題，文獻［12］使用HOSVD對數據進行降維，以緩解稀疏性，但是降維的方法會導致數據不可解釋；文獻［13］認為MF-LOD可以有效解決數據稀疏問題，但該方法過程較為繁瑣，增加了一定的時間復雜度。灰色關聯預測不會改變數據的原有屬性，而且計算量小，不受數據量的約束，因此本文采用灰色關聯預測計算用戶間的灰色關聯度以預測空缺數據；由于用戶對項目打分存在一定的主觀性，文獻［14］提出一種基于云模型的主觀信任量化評價方法，使用主觀信任云的期望和超熵對信任客體信用度進行定量評價；文獻［15］提出一種基于信任鏈的信任評價模型，通過評價模型識別惡意節點，減少不必要的損失。但文獻［14］和文獻［15］都只解決了用戶主觀信任的模糊性問題，忽略了用戶興趣差異問題。而信任云混合算法是一種信任云和興趣特征相結合的方法，它既處理了用戶主觀信任的模糊性問題，又解決了用戶偏好不一的問題，因此本文采用信任云混合算法來處理用戶評分的主觀性。

上述方法中，灰色關聯預測和信任云混合算法都只考慮了如何提高推薦精度，卻忽略了推薦效率的重要性，在處理大規模數據時這些方法就會顯得捉襟見肘。因此，本文提出基于Mean Shift聚類算法的云服務推薦。該方法在灰色關聯預測和信任云混合算法基礎上融入聚類算法MeanShift。通過采用MeanShift算法將灰色關聯預測處理后的數據進行聚類，然后計算類簇內目標用戶與其他用戶間興趣特征相似度與信任相似度加權得到的綜合相似度，并采用top-N算法將近鄰用戶的云服務方案推薦給目標用戶。由于聚類后只需要考慮與目標用戶同類簇的用戶數據即可，因此很大程度上縮短了算法的執行時間，提高了云服務的推薦效率。本文算法主要有3點貢獻，具體如下：

（1）在數據預處理階段通過灰色關聯預測彌補數據稀疏性。

（2）為目標用戶推薦云服務前采用Mean Shift算法將用戶進行聚類，只保留與目標用戶同類簇的數據，以提高算法推薦效率。

（3）采用信任云混合算法消除用戶評分的主觀性影響，更精確地為目標用戶推薦適合的云服務。

1 研究框架

由于云服務市場的迅猛發展，云服務提供商和用戶數量眾多，各種各樣的云服務質量也參差不齊。面對海量的數據，現有的云服務推薦算法不能及時有效地為用戶匹配適合的云服務。而本文提出的基于Mean Shift的云服務推薦可在保證一定推薦精度的基礎上大大提高推薦效率，并且數據量越大效果越明顯。首先采用灰色關聯預測彌補數據空缺值，然后利用Mean Shift算法將用戶進行聚類。流程是先根據數據密度分布對所有用戶進行訪問，而后計算用戶在各個類簇中出現的累計頻數，并將其劃分到累計頻數最大的類簇中。因為在接下來尋找近鄰用戶時只需考慮目標用戶所在類簇的數據即可，所以大大縮短了算法的執行時間。最后計算類簇內目標用戶與其他用戶的綜合相似度，并采用top-N算法將最佳云服務方案推薦給目標用戶。本文思路架構如圖1所示。

2 采用灰色關聯預測填充稀疏數據

一般收集到的數據都是不完整的，存在一定量的空值，但這樣的數據并不是無效數據，只是信息不夠完整，可以采用灰色關聯預測進行填充，以彌補數據稀疏性。灰色關聯分析是灰色關聯預測的核心，其基本原理是依據數列曲線幾何形狀的相似程度判斷其聯系是否緊密。曲線越相似，對應數列間的關聯度就越大。不論數據量多還是少，數據有規律還是無規律，灰色關聯分析都同樣有效，其流程如下：先將原始數據區分為待估數列和比較數列并無綱量化處理，之后計算待估數列和比較數列的關聯系數和關聯度，最后依據關聯度大小將比較序列排序并進行分析。而灰色關聯預測則是利用灰色關聯分析得到的灰色關聯度預測用戶對云服務的評分，其計算過程如下：

將每個使用過云服務的用戶

U

對云服務方案

F

={

F

，

F

，

F

，...，

F

}的評分

r

表示為一個數列，其中

i

=1，2，3，…，

m

，

j

=1，2，3，…，

n

，則待估數列和比較數列分別表示如下：

Fig.1 block diagram of this paper圖1 本文框架

由于存在量綱的影響，需要在計算灰色關聯系數之前對數據進行標準化，其計算公式如下：

其中，

Y

是由評分

r

標準化后得到的標準值，

X

(

i

)表示第

i

個云服務用戶對云服務方案的評分均值。將標準值

Y

表示為一個數列，則待估數列和比較數列分別如式（5）和式（6）所示：

Y

(

k

)和

Y

(

k

)都是所對應數列的第

k

個元素的值，則待估數列和比較數列的灰色關聯系數表示為：

在灰色關聯預測中，評分矩陣為

R

=(

r

)，則云服務用戶間所對應的灰色關聯度為：

根據目標用戶

U

的近鄰集，預測用戶

U

對云服務

F

的評分，計算公式如下：

3 基于聚類的用戶信任云和用戶興趣的綜合方案匹配

通過灰色關聯度預測法對空缺數據進行彌補后得到完整的云服務評分數據。為提高算法執行速度，采用均值漂移算法MeanShift將云服務用戶進行聚類，之后在計算目標用戶的相關數據時只考慮目標用戶所在類簇中云服務用戶的數據即可。在推薦云服務過程中，一方面存在用戶主觀信任的模糊性，另一方面用戶的偏好不一可能導致打分過高或者過低。本文綜合考慮基于信任云的用戶相似度和用戶興趣特征相似度來保證推薦結果的準確性。

3.1 均值漂移算法Mean Shift

聚類算法和傳統云服務推薦算法的結合有助于提高云服務推薦效率，而且數據量越大效果越明顯。本文采用的聚類算法Mean Shift可以自動選擇聚類數量，并且計算量小、運算速度快、比較穩定。其基本原理是先計算出當前質心的漂移向量，根據漂移向量將質心移動到新的位置，然后以此為新的起始點繼續計算漂移向量并移動直到收斂。從每個數據點出發都可以進行該操作，在這個過程中統計出現在領域內的數據次數，最后將該參數作為分類依據。均值漂移向量

M

(

X

)計算公式如下：

其中，

X

表示空間中的數據點，

S

表示半徑為

h

的球狀領域，在這

m

個數據點

X

中有

K

個點落入

S

區域中，數據點

X

位于

S

領域的中心位置。

Fig.2 Mean Shift algorithm clustering process圖2 Mean Shift算法聚類過程

均值漂移算法Mean Shift聚類過程及迭代過程如圖2所示。

Mean Shift聚類算法如下：

輸入：數據集N，球狀領域半徑h。

輸出：K個聚類中心，樣本點所屬類簇。

（1）隨機選擇一個沒有被分類的點作為初始質心點

X

。（2）標定以

X

為中心半徑為

h

的球狀領域中的點

X

屬于類簇C，并且更新這些點在該類簇中出現的累計頻數加1。（3）根據式（11）求漂移向量

M

(

X

)。

（6）重復步驟（1）、（2）、（3）、（4）（5）直到所有的點都被分類。

（7）獲取每個點在各個類簇中出現的累計頻數，將累計頻數最大的點劃分到對應類簇中。如果迭代收斂時有兩個類簇的質心距離小于h，就將它們合并成一個類簇，并且類簇內點的累計頻數也進行合并。否則，把他們看作不同的類簇。

聚類算法Mean Shift可以自動遍歷每個用戶，并記錄每個用戶在各個類簇中出現的累計頻數，依據累計頻數最大原則將用戶分類。據此，可以找到目標用戶所屬類簇，以及獲取類簇中所有用戶的數據。后續在尋找近鄰集并為目標用戶推薦云服務時可以摒棄冗余信息，只考慮目標用戶所屬類簇的數據即可，從而有效提高推薦效率。

3.2 信任云構建

推薦信任和直接信任是信任關系的重要組成部分，不論哪一種都存在著主觀性和不確定性，但可以依據經驗將其拆成多個信任等級。因為正向云是一種將定性概念轉化為定量描述的模型，所以本文考慮通過正向云將用戶對云服務的評分轉換成云滴，進而生成信任云。正向云、信任云、信任等級劃分以及信任云匹配的定義如下：

定義2

信任云是通過正向云將定性概念轉化成云滴，將信任度空間

T

=[0，1]表示為云的定量論域，

x

∈

T

是定性概念上的定量信任評價，也是對應隸屬度

μ

(

x

)約束的隨機數。信任云的定性概念可以用

C

(

E

，

E

，

He

)表示，其中

E

是信任云的期望，

E

是信任云的熵，反映了云滴的離散程度，

He

是超熵，描述了信任云的厚度。

定義3

信任度空間是由信任等級組合而成，根據專家經驗和問卷調查可以將信任度空間設置成如下模型：

獲取信任云定性表示的方法有很多，本文采用綜合評價法，即專家經驗和問卷結合的方法。該方法可以有效獲取信任空間中定性概念的信任云、信任等級的劃分以及信任依賴度

θ

，其中信任依賴度

θ

用信任等級區間的平均值表示。

Fig.3 Trust cloud matching圖3 信任云匹配

計算某云服務用戶的信任云相似度時，首先計算它與其它用戶的信任云相似度，然后求取均值并將其作為該云服務用戶的最終相似度，記為

φ

。而

φ

所在

f

(

x

)中區間的均值即為該區間信任度的權重即信任依賴度

θ

。

3.3 匹配模型

如果只考慮信任云，推薦結果會受主觀因素的干擾而與實際不符。為了提高算法質量，還要將用戶興趣納入模型中。根據專家意見，確定云服務用戶興趣程度以及相應權重，其結果如表1所示。

Table1 Interest similarity weight表1 興趣相似度權重

本文將云服務用戶興趣特征用

T

={

T

，

T

，

T

，...，

T

}表示，其中

T

，

k

=1，2，3，...，

q

表示第

k

個興趣特征；云服務用戶用

U

={

U

，

U

，

U

，...，

U

}表示，其中

U

，

t

=1，2，3，...，

p

表示第

t

個用戶，

U

，

s

=1，2，3，...，

p

表示第

s

個用戶；

U

和

U

對興趣特征的評分分別用

r

和

r

表示。由于不同用戶的評分標準不同，因此本文采用修正的余弦相似度公式來計算用戶的興趣特征相似度：

為提高推薦效率，考慮先采用Mean Shift將用戶進行聚類，然后在類簇中將基于信任云的相似度

φ

與云服務用戶興趣相似度

sim

(

U

，

U

)加權求和，得到綜合相似度，并采用top-N算法將近鄰用戶相應的云服務方案進行推薦。

綜合相似度計算公式如下：

其中，

w

是興趣相似度權重，

θ

是信任依賴度。

4 案例分析

近年云服務行業發展迅猛，云服務的功能愈加完善，種類也逐漸增多，呈現出多元化趨勢，為用戶提供了更多選擇，但還存在一些問題，這些問題不僅損壞用戶利益，還對云服務提供商的利益產生一定影響。

某云服務提供商為提高其競爭力，希望迅速地為用戶推薦滿足其自身需求的云服務方案。通過收集以往企業用戶購買的云服務信息，本文隨機選取20個企業用戶

U

=｛

U

，

U

，…，

U

｝以及相應的云服務：

F

、

F

、

F

、

F

、

F

、

F

、

F

；用戶對云服務的興趣特征包括以下5種：可靠性（

T

）、靈活性（

T

）、性能（

T

）、價格（

T

）、安全性（

T

）。表2是這20個用戶對云服務的評價，其中分值1～6代表用戶對方案的滿意程度，分別為非常不滿意、不滿意、一般、還行、滿意、非常滿意。使用本文算法將適合的云服務推薦給用戶還需要將用戶與興趣特征建立聯系。將云服務特征進行量化，如表3所示。表4是云服務用戶對興趣特征的需求數據，其中

U

是新用戶。采用灰色關聯預測，填充表2和表4。首先采用式（3）、式（4）將數據標準化處理，然后采用式（7）、式（8）分別計算參考用戶與比較用戶的關聯度，最后結合預測公式將表2和表4的空缺數據填充。如表2中用戶

U

對

F

的評分采用式（7）計算相關系數，其中

ρ

取值為0.5，得出

U

與

U

的灰色關聯系數

ζ

=0.491，0.977，0.663，0.723，0.796，0.810，根據式（8）得到關聯度

γ

≈0.743。同理，

U

與

U

、

U

、U

、

…

、U

的灰色關聯度依次為0.773、0.544、0.741、0.660、0.750、0.645、0.790、0.703、0.660、0.568、0.614、0.598、0.628、0.557、0.582、0.447、0.606、0.483。因此，選擇

U

與

U

灰色關聯度，然后由預測公式得出預測的分值，

pred

(

U

，

F

)≈5.371；同理，

U

對

F

的預測評分通過式（7）和式（8）得出

U

和

U

的關聯度最大，為0.786，預測值

pred

(

U

，

F

)≈1.642。表2填充后的結果如表5所示。

Table 2 Users'ratings of cloud services表2 用戶對云服務的評分

Table3 Cloud service characteristics and quantified scores表3 云服務特征及量化分值

Table4 User's requirements for interest characteristics表4 用戶對興趣特征的需求

Table5 User'srating of cloud services（filled）表5 用戶對云服務的評分（已填充）

表4的填充方式也是采用式（7）、式（8）和式（10）進行計算，得到

U

與

U

的灰色關聯度最大，為0.789，預測值

pred

(

U

，

T

)≈2.947；同理，

U

與

U

的灰色關聯度最大，為0.8，預測值

pred

(

U

，

T

)≈1.250。表4填充后的結果如表6所示。接著，使用MeanShift算法將表6中的用戶進行聚類，得到圖4，可知新用戶

U

和用戶

U

、

U

、

U

、

U

、U

、U

、U

屬于同一類簇。因此，在為新用戶

U

推薦云服務時，只需關注與其同類簇的用戶數據。根據專家經驗和問卷方式建立信任云，本文將用戶

U

、

U

、

U

、

U

、U

、U

、U

的信任云進行相互匹配，得出各用戶的最終相似度

φ

，

φ

值決定了信任依賴度

θ

的大小和所在區間。將表5中的數據縮小10倍，通過正向云發生器和信任云匹配，求出用戶信任云的相似度，其結果如表7所示。方案信任云和用戶的評分存在一定的主觀性，為了解決這一問題以及冷啟動問題，本文引入了用戶興趣特征需求，將舊用戶

U

、

U

、

U

、

U

、U

、U

、U

與新用戶

U

的興趣特征進行匹配，可以得到興趣特征相似度

sim

，然后將其與表7中的信任云相似度加權求和，得出綜合相似度

sim’

并依此進行云服務方案推薦。其中權重

w

的值參考表1，新用戶

U

與同類簇中其他用戶的綜合相似度如表8所示。

Table6 User'sre quire ments for interest characteristics（filled）表6 用戶對興趣特征的需求（已填充）

Fig.4 Clustering results圖4 聚類結果

Table 7 Trust cloud eigenvalues表7 信任云特征值

由表8可知，新用戶

U

與同類簇中其他用戶的綜合相似度，將其由大到小排列后得到與

U

近鄰的用戶依次是

U

、

U

、

U

、

U

、

U

、

U

、

U

，其中新用戶

U

明顯與

U

、

U

、

U

、

U

的相似度高，因此采用top-N算法，將用戶

U

、

U

、

U

、

U

對應的云服務方案給予推薦。

Table8 Comprehen sive similarity表8 綜合相似度

5 驗證結果比較分析

為了驗證本文算法的合理性，以數據庫中50～500個等量樣本數據作為訓練集，既考慮算法的執行時間又考慮算法的推薦精度，將本文算法與信任云推薦算法、信任云混合推薦算法、基于灰色關聯與信任云混合算法的推薦方法進行比較分析，結果如圖5-圖7所示。

5.1 推薦精度

采用平均絕對誤差（Mean Absolute Error，MAE）和均方根誤差（Root Mean Square Error，RMSE）作為精確度評測指標來分析本文算法的推薦效果，MAE和RMSE越小表示推薦算法的精確度越高。

Fig.5 MAE value changing carve圖5 MAE值變化曲線

如圖5和圖6所示，從整體上看，信任云混合推薦算法、基于灰色關聯與信任云混合算法的推薦方法與本文算法的精確度較為接近，但本文算法的MAE和RMSE值最低，精確度最高。基于灰色關聯與信任云混合算法的推薦方法僅次于本文算法，而數據的缺失會對推薦精度造成一定的影響，所以信任云混合推薦算法精確度較低。信任云推薦算法的精確度最低是因為數據的稀疏性和用戶興趣不一所致。

Fig.6 Variation carve of RMSE value圖6 RMSE值變化曲線

5.2 推薦效率

從圖7可以看出，隨著數據量的增多，算法的執行時間也在逐漸增加，但本文算法的執行時間呈平穩、緩慢上升趨勢。而信任云推薦算法、信任云混合推薦算法、基于灰色關聯與信任云混合算法的推薦方法執行時間增長較快，呈急劇增長趨勢。當訓練集數據量超過200時，本文算法的高效率優勢逐漸突顯出來，并且隨著數據量的增多，本文算法的優勢愈加明顯，執行效率越來越高。

Fig.7 Efficiency comparison diagram圖7 效率比較

綜上所述，本文算法在保證一定精確度的基礎上大大提高了推薦效率，并且隨著數據量的增加，本文算法的高效率優勢更加突出。因此，本文算法適用于大數據推薦系統。

6 結語

云服務擁有諸多優點，如降低企業經營成本、提高工作效率和保障數據安全等，受到越來越多的企業和個人青睞。在云服務提供商為目標用戶科學高效地推薦云服務過程中，推薦方法尤為重要。現有云服務推薦方法注重如何提高推薦精度而忽略了推薦效率低下的問題。本文提出基于MeanShift的云服務推薦，在灰色關聯預測和信任云混合算法基礎上融入了聚類算法Mean Shift。首先采用Mean Shift算法將灰色關聯預測填充后的數據進行聚類，然后計算類簇內目標用戶與其他用戶間興趣特征相似度與信任相似度，加權得到綜合相似度，并采用top-N算法將近鄰用戶的云服務方案予以推薦。最后在不同數據量下將本文算法和其他算法比較執行時間。實驗結果表明，本文算法不僅保證了一定的推薦精度，還有效提高了推薦效率，并且數據量越大優勢越明顯。但是，本文信任云匹配過程較為繁瑣，因此后續將對信任云匹配進行優化研究。