基于用戶偏好和K-means聚類的可信云資源選擇算法

哈登喆 袁偉涵 袁偉珵/衡水第一中學

基于用戶偏好和K-means聚類的可信云資源選擇算法

哈登喆 袁偉涵 袁偉珵/衡水第一中學

當前云平臺上豐富的云資源和各類云服務吸引了大量的云用戶。在云資源可信程度參差不齊的情況下，可信云資源能夠量化顯示云資源的可信程度，但用戶的偏好各異。如何針對不同的用戶偏好選擇符合用戶偏好的云資源是一個亟待解決的問題。首先采用極差標準化方法對多維屬性的云資源集合進行歸一化處理，然后在用戶偏好基礎上利用K-means算法對云資源進行聚類，從最貼近用戶偏好的一類中選擇最貼近的資源，為用戶選擇出最貼近其偏好的可信云資源。最后用仿真實驗驗證了該方法的有效性。

云資源選擇；可信云資源；用戶偏好；K-means聚類

當前，云服務已經深入人們的日常生活，并有很多用途，如：云相冊、云郵件、云盤等。以百度的云服務帳戶為例，可以將自己手機里的照片備份到云盤，并能夠隨時拍照、隨時同步的便利——百度云服務使得我們不用擔心照片會丟失，也不用擔心手機的存儲空間不夠。云計算架構能夠整合網絡上的各類資源，能夠為云用戶提供按需服務。其中“云服務代理”技術更是受到普通用戶的歡迎。由于大多數普通用戶需求不高，可通過云代理把來自用戶的服務請求整合在一起，向云服務提供商統一購買服務，這樣可以降低云服務的使用成本，使普通用戶能夠享受“團購價”。云服務代理為了提高服務質量，通常會租用一些多余的資源作為預留資源，以幫助長期使用云服務的用戶節省開支，而云資源預留方法的好壞，將直接影響到云代理的服務質量。

云資源預留是目前云服務代理中的研究熱點，其目的是在節約成本的同時提高預留質量。當前的方法主要有兩類：（1）基于統計學的方法，利用隨機過程研究如何租用預留資源和按需預留資源使得花費最少；（2）基于預測的方法，對用戶的需求進行預測，基于預測的結果，對云資源進行動態預留。文獻[1,2]提出了云計算環境下提供符合用戶個性化需求的可信服務推薦的方法。其中，提出了兩種偏好相似度計算方法，后利用用戶間的偏好相似度為目標用戶找到可信任的歷史用戶。文獻[3,4,5,6]研究了用戶偏好或資源預留方法。其中，文獻[4]提出了一種基于信譽屬性的動態云資源預留方法，文獻[5]給出了一種云服務提供商的信任評估框架，文獻[6]提出了一種云服務中基于偏好的云服務預留方法。但是，未見文獻研究基于用戶偏好的云資源選擇選擇算法。

我們在前期完成了將信任評估引入到云服務代理中的工作，為平臺中的云服務給出了信任值。但云資源可從價格、質量、及時性等多個維度進行描述，不同的用戶對擬使用的資源具有不同的偏好。例如，有的用戶偏好質量好的服務，有的用戶偏好價格低的服務，有的用戶偏好及時性高的服務等。因此，需要結合用戶特定的、主觀的偏好，為云服務代理研究更符合用戶需求的云服務資源選擇方法。為此，依據用戶偏好和云資源的信任值，利用K-means方法對可供預留的云資源進行聚類，從最貼近用戶偏好的云資源中選擇信任值最高的云資源作為預留資源。

本文的結構是：第1部分給出作者已經完成的云服務的可信評估模型和用戶偏好的定義；第2部分給出面向用戶偏好的云服務綜合信任值計算方法；第3部分給出基于線性極差變換的云服務信任值歸一化方法；第4部分給出基于用戶偏好和K-means算法的可信云資源選擇算法；第5部分為仿真實驗；第6部分是結論。

1.云服務的可信評估模型和用戶偏好

鑒于云服務的多維屬性，如：價格、質量、及時性等，我們對每個云服務給出了其各個維度上的信任值，建立了如下信任評估模型：

假設有m個云服務，每個云服務有n個屬性，則這m個云服務的信任值可表示如下：

其中m表示云服務的個數，n表示云服務的屬性個數，aij表示第i個云服務第j個屬性的信任值。

定義2. 用戶偏好. 用戶偏好指用戶對云服務的各屬性的偏好程度，可形式化表示為如下的n維向量：

2.面向用戶偏好的云服務綜合信任值計算方法

公式（1）給出的是一段時間后云服務各屬性的信任值。然而，由于用戶所偏好的屬性不同，不同偏好的用戶利用公式（1）得到的對該云服務的綜合信任值是不同的。因此，我們給出面向用戶偏好的云服務綜合信任值計算公式如下：

其中，trustij表示用戶j對依據云服務i的n維屬性評估值，結合用戶j的用戶偏好，得出的對服務i的綜合信任值；tik表示用戶j對服務i的第k個屬性的信任評價值；pjk表示用戶j對第k個屬性的偏好值。

當學生具備了一定的發現和提出問題的能力之后，教師應減少引導，不要直接將學生引入教師預設好的問題，應讓學生自主思考，探究自己想探究的問題。在提出問題階段，可以先不考慮實施的可行性，鼓勵學生發散思維，天馬行空，提出盡量多的豐富多樣的探究問題。之后，再考慮實際情況，評估確定幾個在學校條件下可行性高的探究課題，組建課題小組。

3.基于線性極差變換的云服務信任值歸一化方法

通過公式（1）可知，云服務的信任值是一個n維向量， 向量中的每個元素表示的是云服務特定屬性的信任值。但是各個屬性的信任值可能取值差異很大。例如，存在某云服務，用戶對其質量屬性的信任值評價普遍較高（如0.9）；而用戶對其價格屬性的信任值評價普遍比較低（如0.4）。這樣，由于云服務個屬性的單位和量綱可能不一樣，從而導致絕對值大的屬性占主導作用，而絕對值小的屬性不起作用。為了避免這種情況的發生，采用線性極差變換對公式（1）中的原始數據進行標準化，標準化公式為：

云服務每個屬性的信任值，經過公式（5）的標準化處理以后，不同屬性的信任值就具有了可比性。

4.基于用戶偏好和K-means聚類的可信云資源選擇算法

云服務的各個屬性信任值標準化使得各屬性具有了可比性，因而進一步以用戶偏好作為權重，計算云服務針對特定用戶的綜合信任值，從而選擇綜合信任值最高的云服務作為該用戶的預留云資源。

但云平臺上預留云服務具有以下特點：

（1）云服務的規模通常很大，從中選擇信任值最高的云服務，需要比較n-1次；

（2）由于存在大量的云用戶，使得為某用戶選擇出的云服務可能被其他用戶預留成功，因此經常會發生需要重新選擇資源的情況。

考慮到上述兩個特性，本文按照用戶偏好，基于K-means聚類算法對云平臺上的云服務進行聚類。算法的流程圖如圖1所示。

圖1 基于用戶偏好和K-means聚類的可信云資源選擇算法

圖1所示的流程為：

（1）由用戶輸入個性化偏好，其中用戶偏好的定義參見定義2；

（2）對每個服務：以用戶偏好（見公式（3））為權重，計算經過標準化處理后的各屬性的信任值（見公式（5））的加權和（見公式（4）），以該加權和作為該服務針對該用戶的綜合信任值；

（3）輸入要聚類的類別數；

（4）調用K-means聚類算法，對經過第（2）步處理后的各服務的綜合信任值進行聚類，將其聚成第（3）指定的類別數；

（5）依據聚類算法算出的各個類別的距離值，選取距離最小的一類，作為要為用戶選擇預留云資源的一類，將該類別記為A；

（6）從A中選擇綜合信任值最高的一個云服務作為要預留的云資源。

算法偽代碼如下所示：

其中，從A中選擇最大值的算法如下：

5.仿真實驗

本文用Eclipse實現第4節所構建的算法，并用仿真數據來驗證基于用戶偏好和K-means算法的可信云資源選擇算法的有效性。

5.1 仿真實驗數據

本文用Python的隨機數生成API來生成實驗的仿真數據，每個云服務有兩個屬性的信任值，仿真了1006個云服務、每個云服務兩個屬性（質量和及時性）的信任值。由于篇幅所限，整理其中的40條數據如表1所示。

表1 40個云服務的信任值仿真數據

表1中的每個云服務的信任值，是由兩個屬性信任值構成的二維向量。本實驗將兩個屬性信任值的用戶偏好分別設為0.6和0.4。

5.2 聚類結果及分析

結合用戶偏好，采用第4節建立的基于用戶偏好和K-means聚類的可信云資源選擇算法對1006條數據進行聚類，結果如圖2所示。

圖2 聚類結果

圖2的橫軸表示資源的質量屬性的可信值，縱軸表示及時性屬性的可信值，每個點表示一個云資源，曲線圈起的范圍為本文所給的分類方法的分類結果。可以看到，共分成了3類。六個離群點也被分到了這3個類別中。注意，圖中有些點重合在了一起，因此顯示起來沒有1006個云資源那么多。

將這些分類結果與人工分類結果比對發現，該方法的分類結果與人工分類結果相符。這說明：本項目給出的基于用戶偏好的云資源分類方法能夠有效依據用戶偏好對云資源進行分類。

6.結論

本文針對如何為用戶選擇個性化云服務資源的問題，采用線性極差標準化方法對云資源屬性的可信值進行歸一化處理，并采用K-means方法對云資源進行聚類，并從最貼近用戶偏好的云資源中選擇信任值最高的云資源作為預留資源。實驗結果表明，本文所提方法有效。此外，該方法在實際應用中的模糊用戶偏好的表征問題，還有待進一步研究。

注：本文為第三十二屆河北省青少年科技創新大賽一等獎（基于用戶偏好的可信云資源預留方法，未公開發表）的部分內容經修改完善而成。

[1] 杜瑞忠,田俊峰,張煥國. 基于信任和個性偏好的云服務選擇模型[J]. 浙江大學學報(工學版), 2013,01:53-61.

[2] 侯震. 基于多等級方案成對比較的云服務提供商選擇研究[D]. 合肥工業大學, 2015.

[3] 孟順梅. 云計算環境下可信服務組合及其關鍵技術研究[D].南京大學, 2016.

[4] 董娜. 基于信譽屬性的動態云資源預留[D]. 河北大學,2013.

[5] Habib S. M., Varadharajan V., Muhlhauser M., et al. A framework for evaluating trust of service providers in cloud marketplaces[C]. Acm Symposium on Applied Computing, 2013: 1963-1965.

[6] Ioannis P.,Yiannis V.,Gregoris M. Preference-based cloud service recommendation as a brokerage service [C]. CCB’ 14 Proceedings of the 2nd International Workshop on Cross Cloud Systems,2014, 8.

哈登喆，男，衡水第一中學，在讀高二學生，研究興趣：云代理相關技術。

袁偉涵，女，衡水第一中學，在讀高二學生，研究興趣：云代理相關技術。

袁偉珵，男，衡水第一中學，在讀高二學生，研究興趣：云代理相關技術。

Cloud resources and various types of cloud services are attracting a large number of cloud users. A wide range of cloud resources whose trustiness is uneven, the trusted cloud resources can quantify the credibility of cloud resources. However, the user preference is various. This paper solves the problem that how to choose the most suitable cloud resources for different user preference. In this paper, the K-means algorithm is used to cluster the cloud resources on the basis of user preference, and choose the closest to the user preference. The simulation experiment is used to verify the effectiveness of this method.

Cloud resources selection; Trusted Cloud Resources; User preference; K-means clustering