考虑Mean Shift用户聚类的云服务推荐
2022-04-24王著鑫耿秀丽王龙羽王婉婷
王著鑫，耿秀丽，王龙羽，王婉婷
（上海理工大学管理学院，上海 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
表示。由于不同用户的评分标准不同，因此本文采用修正的余弦相似度公式来计算用户的兴趣特征相似度：
φ
与云服务用户兴趣相似度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算法将近邻用户的云服务方案予以推荐。最后在不同数据量下将本文算法和其他算法比较执行时间。实验结果表明，本文算法不仅保证了一定的推荐精度，还有效提高了推荐效率，并且数据量越大优势越明显。但是，本文信任云匹配过程较为繁琐，因此后续将对信任云匹配进行优化研究。
