一种基于用户聚类的skyline在线计算方法

摘要

本发明公开了一种基于用户聚类的sky line在线计算方法，（1）通过用户聚类，将QoS相似的用户聚集在一起，利用聚类共同特征代替用户个体特征，使得计算数据量有效减少；将对所有用户进行离线处理转化为对各个聚类进行离线处理，提高了离线计算的效率，大幅减少了存储空间消耗，提高了系统的可实施性，（2）将计算过程划分为离线和在线模块，通过将大量复杂运算在离线模块中进行，有效提高在线算法的执行效率，（3）利用群体特征sky line对个体sky line进行预测，一方面在精度要求不高时可以直接作为结果返回；另一方面在需要求解准确sky line时在此预测sky line基础上进行修正，可以简化计算过程。

主权项

一种基于用户聚类的sky line在线计算方法，其特征在于，包括如下步骤：11)基于用户‑服务QoS矩阵对相似用户进行聚类步骤：当为单维度场景时，采用将所有维度的QoS值归一化处理后按照其权重计算为一维数值，用户u对服务s的多维QoS的归一化公式如下：$\tilde{q}\left(s\right)=\underset{i=1}{\overset{R}{\Sigma }}\frac{q_i\left(s\right)-{\min }_{s^{\prime }\in S}{q}_i\left(s^{\prime }\right)}{{\max }_{s^{\prime }\in S}{q}_i\left(s^{\prime }\right)-{\min }_{s^{\prime }\in S}{q}_i\left(s^{\prime }\right)}·w_i$其中q_i(s)为第i个维度上的QoS值，w_i为各维度的QoS权重，且∑w_i＝1，由此一维用户相似度可以由以下Pearson相似度公式计算：$Dist(u_i,u_j)=Sim(u_j,u_j)=\frac{{\Sigma }_{s\in S(i,j)}\left(q_j\right(s)-\overline{q_i})\left(q_j\right(s)-\overline{q_j})}{\sqrt{{\Sigma }_{s\in S(i,j)}{\left(q_i\right(s)-\overline{q_j})}^2}\sqrt{{\Sigma }_{s\in S(i,j)}{\left(q_j\right(s)-\overline{q_j})}^2}}$其中为用户u_i对所有服务调用的平均QoS，用户u_j对所有服务调用的平均QoS，基于此相似度进行聚类操作；当为多维度场景时，首先对每个维度的QoS仍然进行归一化操作，每一个维度上QoS的取值范围都是(0,1)之间，接着采用余弦距离计算两个用户u_i与u_j之间在服务s上的相似度：$sim(u_i,u_j,s)=\frac{\overrightarrow{q_i}\left(s\right)·\overrightarrow{q_j}\left(s\right)}{\left|\overrightarrow{q_i}\left(s\right)\right|\left|\overrightarrow{q_j}\left(s\right)\right|}$其中是用户i对服务s的归一化QoS向量，定义用户u_i与u_j的在服务集S上的多维QoS相似度为：$sim(u_i,u_j,S)=J(u_i,u_j)·\frac{\underset{s\in S}{\Sigma }\mathrm{si}m\left(u_i,u_j,s\right)}{\left|S\right|}$定义S(u)为用户u调用的服务s所构成的集合，那么有：$J(u_i,u_j)=\frac{\left|S\left(u_i\right)\cap S\left(u_j\right)\right|}{|S\left(u_i\right)\cup S(u_j\left)\right|}$基于此相似度进行聚类操作；12)基于用户聚类，计算聚类特征sky line步骤；由一个聚类中服务的QoS均值计算得到的sky line；13)基于离线聚类sky line执行在线sky line修正步骤:输入用户u对于目标等价服务集S中的每一个点，首先在对应类平均sky line的支配表中支配该点的原sky line点集，并逐个判断在预测QoS数值之后的支配关系，若仍存在支配关系，那么该点在预测过QoS的服务集仍然不属于sky line；若原支配该点的sky line点，在预测后的QoS数值上不再支配该点，那么将该点和不被该点支配的原sky line点都加入候选集，最后在候选集中进行最终sky line计算；所述支配表用来存储sky line中支配关系的HashTable，其键为每一个非sky line节点索引，值为支配该节点的sky line点的集合。