[發(fā)明專(zhuān)利]一種基于用戶(hù)聚類(lèi)的sky line在線計(jì)算方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310043441.5
• 申請(qǐng)日: 2013-02-04
• 公開(kāi)（公告）號(hào): CN103150336A
• 公開(kāi)（公告）日: 2013-06-12
• 發(fā)明（設(shè)計(jì)）人: 吳健;陳克寒;吉利川;尹建偉;李瑩;鄧水光;吳朝暉
• 申請(qǐng)（專(zhuān)利權(quán)）人: 浙江大學(xué)
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30
• 代理公司: 杭州裕陽(yáng)專(zhuān)利事務(wù)所(普通合伙) 33221
• 代理人: 江助菊

1.一種基于用戶(hù)聚類(lèi)的sky?line在線計(jì)算方法，其特征在于，包括如下步驟：

11）基于用戶(hù)-服務(wù)QoS矩陣對(duì)相似用戶(hù)進(jìn)行聚類(lèi)步驟：

當(dāng)為單維度場(chǎng)景時(shí)，采用將所有維度的QoS值歸一化處理后按照其權(quán)重計(jì)算為一維數(shù)值，用戶(hù)u對(duì)服務(wù)s的多維QoS的歸一化公式如下：

q~(s)=Σi=1Rqi(s)-mins′∈Sqi(s′)maxs′∈Sqi(s′)-mins′∈Sqi(s′)·wi]]>

其中q_i(s)為第i個(gè)維度上的QoS值，w_i為各維度的QoS權(quán)重，且∑w_i＝1，由此一維用戶(hù)相似度可以由以下Pearson相似度公式計(jì)算：

Dist(ui,uj)=Sim(ui,uj)=Σs∈S(i,j)(qi(s)-q‾i)(qj(s)-q‾j)Σs∈S(i,j)(qi(s)-q‾i)2Σs∈S(i,j)(qj(s)-q‾j)2]]>

其中為用戶(hù)u_i對(duì)所有服務(wù)調(diào)用的平均QoS，為用戶(hù)u_j對(duì)所有服務(wù)調(diào)用的評(píng)均QoS，基于此相似度進(jìn)行聚類(lèi)操作；

當(dāng)為多維度場(chǎng)景時(shí)，首先對(duì)每個(gè)維度的QoS仍然進(jìn)行歸一化操作，是每一個(gè)維度上QoS的取值范圍都是(0,1)之間，接著采用余弦距離計(jì)算兩個(gè)用戶(hù)u_i與u_j之間在服務(wù)s上的相似度：

sim(ui,uj,s)=q→i(s)·q→j(s)|q→i(s)||q→j(s)|]]>

其中是用戶(hù)i對(duì)服務(wù)s的歸一化QoS向量，定義用戶(hù)u_i與u_j的在服務(wù)集S上的多維QoS相似度為：

sim(ui,uj,S)J(ui,uj)·Σs∈Ssim(ui,uj,s)|S|]]>

定義S(u)為用戶(hù)u調(diào)用的服務(wù)s所構(gòu)成的集合，那么有：

J(ui,uj)=|S(ui)∩S(uj)||S(ui)∪S(uj)|]]>

基于此相似度進(jìn)行聚類(lèi)操作；

12）基于用戶(hù)聚類(lèi)，計(jì)算聚類(lèi)特征sky?line步驟；

由一個(gè)聚類(lèi)中服務(wù)的QoS均值計(jì)算得到的sky?line；

13）基于離線聚類(lèi)sky?line執(zhí)行在線sky?line修正步驟:

首先在對(duì)應(yīng)類(lèi)平均sky?line的支配表中支配該點(diǎn)的原sky?line點(diǎn)集，并逐個(gè)判斷在預(yù)測(cè)QoS數(shù)值之后的支配關(guān)系，若仍存在支配關(guān)系，那么該點(diǎn)在預(yù)測(cè)過(guò)QoS的服務(wù)集仍然不屬于sky?line；若原支配該點(diǎn)的sky?line點(diǎn)，在預(yù)測(cè)后的QoS數(shù)值上不再支配該點(diǎn)，那么將該點(diǎn)和不被該點(diǎn)支配的原sky?line點(diǎn)都加入候選集。最后在候選集中進(jìn)行最終sky?line計(jì)算;

所述支配表用來(lái)存儲(chǔ)sky?line中支配關(guān)系的HashTable，其鍵為每一個(gè)非sky?line節(jié)點(diǎn)索引，值為支配該節(jié)點(diǎn)的sky?line點(diǎn)的集合。

2.根據(jù)權(quán)利要求1所述的一種基于用戶(hù)聚類(lèi)的sky?line在線計(jì)算方法，其特征在于，所述步驟12）和步驟13）可采用如下步驟替代：

首先定義sky?line合并；如果SK(S₁),SK(S₂)分別是集合S₁,S₂上的sky?line，SK(S′)是這兩條sky?line的并，即SK(S′)=merge(SK(S₁),SK(S₂))，那么SK(S′)是這樣一個(gè)集合：s∈SK(S₁)∨s∈SK(S₂)，且在SK(S₁),SK(S₂)中不存在的服務(wù)s′，使得s′＞s，且merge(SK(S₂),SK(S₂))=SK(S₁∪S₂)，即并集的sky?line等于各自sky?line的并對(duì)聚類(lèi)C上的等價(jià)服務(wù)集S的最優(yōu)sky?line的計(jì)算，可以由聚類(lèi)C上各用戶(hù)u的歷史sky?line記錄合并獲得。