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

哈登喆 袁偉涵 袁偉珵/衡水第一中學(xué)

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

哈登喆 袁偉涵 袁偉珵/衡水第一中學(xué)

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

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

當(dāng)前，云服務(wù)已經(jīng)深入人們的日常生活，并有很多用途，如：云相冊、云郵件、云盤等。以百度的云服務(wù)帳戶為例，可以將自己手機(jī)里的照片備份到云盤，并能夠隨時(shí)拍照、隨時(shí)同步的便利——百度云服務(wù)使得我們不用擔(dān)心照片會(huì)丟失，也不用擔(dān)心手機(jī)的存儲(chǔ)空間不夠。云計(jì)算架構(gòu)能夠整合網(wǎng)絡(luò)上的各類資源，能夠?yàn)樵朴脩籼峁┌葱璺?wù)。其中“云服務(wù)代理”技術(shù)更是受到普通用戶的歡迎。由于大多數(shù)普通用戶需求不高，可通過云代理把來自用戶的服務(wù)請求整合在一起，向云服務(wù)提供商統(tǒng)一購買服務(wù)，這樣可以降低云服務(wù)的使用成本，使普通用戶能夠享受“團(tuán)購價(jià)”。云服務(wù)代理為了提高服務(wù)質(zhì)量，通常會(huì)租用一些多余的資源作為預(yù)留資源，以幫助長期使用云服務(wù)的用戶節(jié)省開支，而云資源預(yù)留方法的好壞，將直接影響到云代理的服務(wù)質(zhì)量。

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

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

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

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

鑒于云服務(wù)的多維屬性，如：價(jià)格、質(zhì)量、及時(shí)性等，我們對每個(gè)云服務(wù)給出了其各個(gè)維度上的信任值，建立了如下信任評估模型：

假設(shè)有m個(gè)云服務(wù)，每個(gè)云服務(wù)有n個(gè)屬性，則這m個(gè)云服務(wù)的信任值可表示如下：

其中m表示云服務(wù)的個(gè)數(shù)，n表示云服務(wù)的屬性個(gè)數(shù)，aij表示第i個(gè)云服務(wù)第j個(gè)屬性的信任值。

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

2.面向用戶偏好的云服務(wù)綜合信任值計(jì)算方法

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

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

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

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

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

云服務(wù)每個(gè)屬性的信任值，經(jīng)過公式（5）的標(biāo)準(zhǔn)化處理以后，不同屬性的信任值就具有了可比性。

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

云服務(wù)的各個(gè)屬性信任值標(biāo)準(zhǔn)化使得各屬性具有了可比性，因而進(jìn)一步以用戶偏好作為權(quán)重，計(jì)算云服務(wù)針對特定用戶的綜合信任值，從而選擇綜合信任值最高的云服務(wù)作為該用戶的預(yù)留云資源。

但云平臺(tái)上預(yù)留云服務(wù)具有以下特點(diǎn)：

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

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

考慮到上述兩個(gè)特性，本文按照用戶偏好，基于K-means聚類算法對云平臺(tái)上的云服務(wù)進(jìn)行聚類。算法的流程圖如圖1所示。

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

圖1所示的流程為：

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

（2）對每個(gè)服務(wù)：以用戶偏好（見公式（3））為權(quán)重，計(jì)算經(jīng)過標(biāo)準(zhǔn)化處理后的各屬性的信任值（見公式（5））的加權(quán)和（見公式（4）），以該加權(quán)和作為該服務(wù)針對該用戶的綜合信任值；

（3）輸入要聚類的類別數(shù)；

（4）調(diào)用K-means聚類算法，對經(jīng)過第（2）步處理后的各服務(wù)的綜合信任值進(jìn)行聚類，將其聚成第（3）指定的類別數(shù)；

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

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

算法偽代碼如下所示：

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

5.仿真實(shí)驗(yàn)

本文用Eclipse實(shí)現(xiàn)第4節(jié)所構(gòu)建的算法，并用仿真數(shù)據(jù)來驗(yàn)證基于用戶偏好和K-means算法的可信云資源選擇算法的有效性。

5.1 仿真實(shí)驗(yàn)數(shù)據(jù)

本文用Python的隨機(jī)數(shù)生成API來生成實(shí)驗(yàn)的仿真數(shù)據(jù)，每個(gè)云服務(wù)有兩個(gè)屬性的信任值，仿真了1006個(gè)云服務(wù)、每個(gè)云服務(wù)兩個(gè)屬性（質(zhì)量和及時(shí)性）的信任值。由于篇幅所限，整理其中的40條數(shù)據(jù)如表1所示。

表1 40個(gè)云服務(wù)的信任值仿真數(shù)據(jù)

表1中的每個(gè)云服務(wù)的信任值，是由兩個(gè)屬性信任值構(gòu)成的二維向量。本實(shí)驗(yàn)將兩個(gè)屬性信任值的用戶偏好分別設(shè)為0.6和0.4。

5.2 聚類結(jié)果及分析

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

圖2 聚類結(jié)果

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

將這些分類結(jié)果與人工分類結(jié)果比對發(fā)現(xiàn)，該方法的分類結(jié)果與人工分類結(jié)果相符。這說明：本項(xiàng)目給出的基于用戶偏好的云資源分類方法能夠有效依據(jù)用戶偏好對云資源進(jìn)行分類。

6.結(jié)論

本文針對如何為用戶選擇個(gè)性化云服務(wù)資源的問題，采用線性極差標(biāo)準(zhǔn)化方法對云資源屬性的可信值進(jìn)行歸一化處理，并采用K-means方法對云資源進(jìn)行聚類，并從最貼近用戶偏好的云資源中選擇信任值最高的云資源作為預(yù)留資源。實(shí)驗(yàn)結(jié)果表明，本文所提方法有效。此外，該方法在實(shí)際應(yīng)用中的模糊用戶偏好的表征問題，還有待進(jìn)一步研究。

注：本文為第三十二屆河北省青少年科技創(chuàng)新大賽一等獎(jiǎng)（基于用戶偏好的可信云資源預(yù)留方法，未公開發(fā)表）的部分內(nèi)容經(jīng)修改完善而成。

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

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

[3] 孟順梅. 云計(jì)算環(huán)境下可信服務(wù)組合及其關(guān)鍵技術(shù)研究[D].南京大學(xué), 2016.

[4] 董娜. 基于信譽(yù)屬性的動(dòng)態(tài)云資源預(yù)留[D]. 河北大學(xué),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.

哈登喆，男，衡水第一中學(xué)，在讀高二學(xué)生，研究興趣：云代理相關(guān)技術(shù)。

袁偉涵，女，衡水第一中學(xué)，在讀高二學(xué)生，研究興趣：云代理相關(guān)技術(shù)。

袁偉珵，男，衡水第一中學(xué)，在讀高二學(xué)生，研究興趣：云代理相關(guān)技術(shù)。

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