欢迎访问一起赢论文辅导网
本站动态
联系我们

手机:153 2730 2358
邮箱:910330594@QQ.COM

Q Q:
910330594
网址:http://www.17winner.com
工作时间:
9:00-24:00  

博士论文
当前位置:首页 > 博士论文
基于CART 与SLOPEONE 的服务质量预测算法
来源:一起赢论文网     日期:2017-12-12     浏览数:493     【 字体:

  徐文庭  :基于 CART SlopeOne的服务质量预测算法到满足功能需求的最佳服务,成为目前服务计算领域的研究热点。目前,已有国内外研究者提出了不少服务质量预测方法,其中协同过滤方法是服务质量预测的主流方法[1-4]。基于协同过滤的服务质量(Quality ofService,QoS)预测方法主要分为基于近邻的 法(如基于用户的方法[4]、基于服务的方法[4]等)和基于模型的方法 (如支持向量机[21]、矩阵分解[22]等)两类。基于近邻的方法通常包括相似邻居的选择和基于相似邻居的历史信息进行缺失 QoS预测两个步骤。其中相似邻 居的选择是基于近邻方法的关键,通常基于用户或者服务的历史信息,使用某种相似度计算方法为用户或者服务选择若干个最相似的用户或者服务。常用的相似度计算方法有欧式距离、皮尔逊稀疏、余弦相似度等。基于模型的方法利用已存在的历史 QoS学习构建一个预测模型,然后利用该预测模型进行缺失值的预测。模型的训练基于不同的假设,通常训练的开销十分巨大,因此常在离线情况下进行,在线预测时使用已完成训练的模型。这些方法的优点在于能够充分利用用户—服务的历史信息预测缺失值,且不要求其他外部信息,从而使协同过滤算法具有较好的预测准确度和较强的适用性。然而,上述协同过滤方法在预测 QoS值时存在以下问题:(1)基于模型的方法不能利用新增的用户—服务调用记录来提高预测准确度,每次新增 QoS信息时必须重新构建预测模型,而预测模型的构建非常耗时。(2)协同过滤算法筛选相似邻居时需要假定大部分 QoS值是稳定和可靠的。然而,QoS依赖于用户和服务的网络环境状况,由于网络环境状况充满随机性,用户调用服务得到的 QoS值同样充满随机性。另一方面,随着数据稀疏度的升高,协同过滤算法筛选相似邻居的准确度大幅度降低。高稀疏度情况下,一个用户调用过的服务很少,两个用户共同调用过的服务则更加稀少,因此基于很少量的共同调用记录筛选的相似邻居并不准确。特别是若两个用户没有共同调用过相同的服务,则这两个用户将没有机会成为彼此的相似邻居。(3)协 同 过 滤 算 法 预 测 当 前 用 户 调 用 目 标 服务的 QoS值时,仅 使 用 当 前 用 户 相 似 用 户 群 对 目标服务的历史调用 QoS值。数据稀疏度高的情况下,该 QoS值非常稀少,由此得到的预测结果并不可靠。SlopeOne预 测 方 法[2]可 认 为 是 应 对 上 述 问题的一种较 好 的 解 决 方 案。 首 先,SlopeOne方 法是基于服务偏 差 进 行 回 归 预 测,当 新 增 用 户—服务对调用信息 时,仅 需 要 更 新 该 用 户—服 务 对 关联的服务偏差,因此 该 方 法 能 够 快 速 有 效 地 利 用新增信息提高预测 准 确 度 ,从 而 克 服 了 基 于 模 型推荐算法不能处理动 态 数 据 的 问 题 ;其 次,Slope-One为当前用户进行 QoS预 测 时,并 不 需 要 为 当前用户筛选相似邻 居,因 此 避 免 了 协 同 过 滤 算 法筛选相 似 邻 居 时 遇 到 的 问 题;最 后,SlopeOne使用的是全部历史 QoS信息,而不是 仅 使 用 相 似 邻居的历史 QoS信息进行回归预测,避 免 了 协 同 过滤算法在 高 数 据 稀 疏 情 况 下 预 测 结 果 不 可 靠 的问题。尽管如此,直接使用基本的SlopeOne方法仍然存在一些问题:一方面提高了在线预测的时间复杂度,另一方面不可避免地使用了一部分噪声数据用于缺失值预测而降低了预测准确度。因此,本文对基本的 SlopeOne方法进 行 了改 进,以 解 决 上 述 缺陷。本文的主要贡献如下:(1)考虑到其他模型,如位置感知的混合协同过滤 (Hybrid Location-Aware Collaborative Filte-ring,HLACF)[11],只是对用户或者对服务进行分类,提 出 一 个 基 于 分 类 回 归 树 (Classification AndRegression Tree,CART)的分类模型,对用户—服务对进行分类。(2)针对基本SlopeOne算法存在使用噪声数据进行预测的问题,提出一个基于 CART 分类结果的加权SlopeOne预测方法,仅使用待预测用户—服务对所属分类集合的历史 QoS值,降低了预测时间复杂度,实现了噪声过滤,从而提高了预测准确度。(3)在一个真实数据集上进行了大量实验,实验结果表明本文方法在数据稀疏情况下具有较好的预测精度。1 相关工作服务推荐技术用于为用户推荐 QoS 最优或者较优的服务,对缺失的 QoS值进行预测是当前服务推荐过程的关键。协同过滤方法已被广泛用于服务预测,该方法由 Rich[5]最早提出,已成功应用于各种商业推荐系统[6-9]。近年来,一些基于近邻的协同过滤方法被用于 QoS值预测[10-11]。Sun等[10]提出8011计算机集成制造系统 第23卷一种新的相似度计算方法,以更准确地筛选相似用户和相似服务:首先,根据用户 QoS向量中的最大值和最小值归一化 QoS 向量,将每个用户的 QoS向量的取值范围调整到0~1之间;然后,基于平均欧式距离,使用归一化后的 QoS计算相似度,平均欧式距离越小、相似度越大。Liu等[11]提出一种基于地理位置信息的协同过滤方法 HLACF,认为地理位置接近的用户具有相近的网络环境,可以得到相近的 QoS值。因此在为目标用户和目标服务筛选相似用户和相似服务时,应考虑地理位置的影响。与基于近邻的协同过滤方法直接使用已有数据进行预测不同,基于模型的方法使用已存在的历史调用 QoS信息来学习预 测模型[20],其主要思想是使用属性来构建用户和服务之间的关联,通过综合用户和服务在相同属性上的偏好实现用户调用服务的 QoS预测,通过历史数据进行训练得到预测器。He等[12]提出一种基于地 理位 置的层次矩阵 分 解(Hierarchical Matrix Factorization,HMF)模型,根据用户和服务的地理位置信息,使用 k-Means方法将全局矩阵划分为多个局部矩阵,其中每个局部矩阵包含部分用户和部分服务;最终的预测结果综合考虑局部矩阵和全局矩阵的预测结果。Xu等[13]进一步 扩 展 了 概 率 矩 阵 分 解 (Probabilistic MatrixFactorization,PMF)模型,提高了预测准确度,在训练用户隐含特征向量时考虑用户邻居隐含特征向量的影响。然而,上述方法大多仍未能较好地解决数据动态更新和有效筛选相似邻居的问题。特别是高数据稀疏度下,这些方法 的预测 准确度会大幅度下降。Maclachlan等[2]提出的 SlopeOne预测方法以其易于实现、良好的推荐质量受到众多研究者的关注,可以较好地解决上述问题。许多基于 SlopeOne的预测方法被提出并用于传统推荐领域,取得了很好的效果。例 如:Zhang 等[14]提 出 一 种 利 用 SlopeOne填充的基于物品的协同过滤算法;Mi等[15]提出首先将物品按照用户评分进行聚类,然后基于目标物品聚类成员的被评分记录,使用SlopeOne算法为目标服务进行评分预测。SlopeOne方法具有的上述良好特性使之可以用于 QoS值的预测。然而,基本的 SlopeOne方法存在使用噪声数据进行回归预测的问题。为此,本文提出改进的基本SlopeOne方法,以提高预测准确度。2 服务推荐系统服务推荐系统的重要步骤是,首先为目标用户预测未调用服务的 QoS,然后为目标用户推荐 QoS最优或者较优的服务。图1所示为本文提出的服务推荐系统的整体框架,具体阐述如下:(1)用 户—QoS 矩 阵   存 储 了 所 有 历 史 调 用QoS值,其中缺省值标记为 None。(2)抽取训练集和测试集 从原始评分矩阵中随机抽 取 一部分 QoS 值,构建训 练 矩阵和测试 矩阵,其中缺省值标记为 None。(3)分类回归树生成模块 利用训练集数据,使用信息增益(Information Gain,IG)算法创建分类回归树。(4)用户—服务对的分类预测模块 预测目标用 户—服 务 对 的 QoS 时,使 用 CART 预 测 该 用户—服务对的分类。(5)基于分类集合的加权SlopeOne预测算法模块  预 测 目 标 用 户—服 务 对 的 QoS 时,SlopeOne仅使用与该目标用户—服务对分类结果一致的用户—服务对的历史 QoS值进行回归预测。(6)推荐模块 为目标用户推荐 QoS最优或者较优的未调用服务。3 基于 CART与SlopeOne的QoS预测方法下面具体阐述缺失 QoS值的预测方法。首先通过挖掘用户和服务的潜在特征提取出用户和服务的特征向量,并提出一种用户—服务对的类别划分方法。通 过 上 述 两 个 步 骤,成 功 地 在 本 文 中 引 入CART 方法。其 次,在基本的 SlopeOne方 法 中 加入基于 CART 分类的过 滤机制,从 而 提 高 预 测 准确度。3.1 CART生成方法本文所采用的数据集的 QoS值来源于现实环8012 徐文庭 等:基于 CART 与 SlopeOne的服务质量预测算法境下的实际测量,其使用的响应时间 QoS值属于不适用于分类的连续型浮点数值,其取值范围为[-1,20]。同时,该数据集没有 提供 用 户—服 务 对 生 成CART 所必需的有效特征,因此 CART 并不适用于原始的 QoS数据集。通过将连续型浮点数值转化为离散型整数数值来满足有限 分类类别标签的需求,同时通过挖掘目标用户—服务对的历史信息,提取出用户和服务的个性特征(用户和服务的 QoS均值与方差),来满足生成 CART 的特征需求,从而实现将 CART 应用于 QoS数据集的目标。下面依次介绍生成 CART 的各个步骤。3.1.1 特征提取用户和服务具有一些固定的属性,其历史信息能够用来预测用户和服务的当前行为,因此本文从用户和服务的历史调用 QoS信息中提取出用户和服务的个性特征,这些个性特征表现了用户和服务的某种潜在个性属性。对于一个特定的用户—服务对,可提取出userMean,userStd,wsMean,wsStd 四个特征。其中:userMean和wsMean 是用户和服务历史调用 QoS的均值;userStd 和wsStd 是用户和服务历史调用 QoS的标准差。因此,对于每一个特定的用户—服务对,均能得到一个唯一的用户—服务对特征向量。3.1.2 类别标签划分本文采用的数据集来自真实环境下的实际测量,且为连续型浮点数值,然而 CART 的生成需要使用离散型数值。因此,将连续型浮点数值向下取整,转化为生成 CART 所需要的离散型整数数值,从而得到21个分类标签,将构建 CART 树的过程转换为一个多分类的问题。3.1.3 特征选择CART 使用IG 算法选择最优划分特征和最优划分特征值,以划分当前节点、生成孩子节点。为了便于说明IG 算法,下面首先给出熵、条件熵和信息增益的概念。熵是表明随机变量不确定性的度量,熵越大,随机变量的不确定性就越大,即样本集合的熵越大,样本的类别标签越分散,方差越大。设 X 是一个取有限个值的随机变量,其概率分布为P(X =xi)=pi,i=1,2,…,n。 (1)则随机变量 X 的熵定义为H(X)=-∑ni=1pilogepi。 (2)条件熵 H(Y|X)表示在已知随机变量 X 的条件下随机变量Y 的不确定性,定义为给定 X 的条件下Y 的条件概率分布熵对X 的数学期望:H(Y|X)=∑ni=1piH (Y|X =xi)。 (3)令上述 X 表示特征、Y 表示类,则对于训练数据集 D,其信息增益g(D,X)定义为集合 D 的经验熵 H (D)与特征 X 给定条件下D 的经验条件熵 H(Y|X)之差,即g(D,X)= H(D)-H(D|X)。 (4)上述公式表明,信息增益表示由于特征 X 而使对数据集D 的分类不确定性减少的程度。对于数据集 D 而言,信息增益依赖于特征,信息增益大的特征具有更强的分类能力。因此特征选择就是选择信息增益最大的特征。下面给出IG 算法。算法1 IG 算法。输入:训练数据集 D 和特征X。输出:特征 X 对 训 练 数 据 集 D 的 信 息 增 益g(D,X)。(1)计算数据集 D 的经验熵 H (D):H(D)=-∑Kk=1|Ck||D|loge|Ck||D|。 (5)式中:|D|为样本容量;k 为类的数目,k=1,2,…,K;|Ck|为属于类Ck的样本个数。(2)计算特征 X 对数据集D 的经验条件熵 H(D|X):H(D|X)=∑ni=1|Di||D|H(Di)。 (6)式中:根据特征 X 将数据集D 划分为n 个子集D1,D2,…,Dn,|Di|为子集 Di的样本个数。(3)计算信息增益g(D,X)= H(D)-H(D|X)。 (7)3.1.4 CART 过拟合处理CART 在建树过程中过多 地考 虑 对 训 练 数 据的正确分类,容易创建过于复杂的决策树,从而造成过 拟 合 现 象。 过 拟 合 会 降 低 CART 的 泛 化 能力,使 得 对 测 试 集 的 分 类 能 力 变 弱。 通 过 降 低CART 决策树的复杂度来 避 免过拟合的 过程称为剪枝。本文通过综合使用预剪枝 和后剪枝 技术来避免过拟合。一方面,通过设置 CART 建树过程中的提前终止划分条 件 来降低 CART 决策树 的 深 度,实 现 对CART 决策树的预剪枝。即为 当 前待划分 节点设8013016-06-28;修订日期:2016-08-28。Received 28June 2016;accepted 28Aug.2016.基金项目:国家科技 支 撑 计 划 资 助 项 目 (2014BAK14B04);浙 江 省 自 然 科 学 基 金 资 助 项 目 (LY12F02003);中 国 博 士 后 科 学 基 金 资 助 项 目(2013M540492)。 Foundation items:Project supported by the National Key Technology R&D Program, China (No.2014BAK14B04),the Zhejiang Provincial Natural Science Foundation,China(No.LY12F02003),and the Chinese Postdoctoral Sci-ence Foundation,China(No.2013M540492).基于 CART 与SlopeOne的服务质量预测算法徐文庭1,殷昱煜1,2,3+,王菊仙1,王兴菲1,余方正1(1.杭州电子科技大学 计算机学院,浙江 杭州 310018;2.浙江大学 电气工程学院,浙江 杭州 310027;3.教育部复杂系统建模与仿真重点实验室,浙江 杭州 310018)摘 要:针对现有的预测算法大多未有效利用用户—服务对的潜在特征问题,提出一种基于分类和 SlopeOne的预测算法,通过用户—服务对的历史服务质量值提取出用户和服务的个性特征(用户和服务的服务质量均值与方差);基于提取出的特征,使用 CART(classification and regression trees)对用户—服务对进行分类;使用 Slope-One算法在目标用户和目标 服 务 所 在 的 分 类 集 合 数 据 集 上 进 行 回 归 预 测,提 高 了 预 测 准 确 度;选 用 真 实 数 据 集WS-Dream 进行实验,实验结果表明该方法在数据稀疏情况下具有较好的预测精度。关键词:Web服务;服务质量预测;协同过滤;SlopeOne;分类与回归树中图分类号:TP312   文献标识码:AQoS prediction based on CART and SlopeOneXU Wenting1,YIN Yuyu1,2,3+,WANG Juxian1,WANG Xingfei1,YU Fangzheng1(1.School of Computer Science and Technology,Hangzhou Dianzi University,Hangzhou 310018,China;2.College of Electrical Engineering,Zhejiang University,Hangzhou 310018,China;3.Key Laboratory of Modeling and Simulation for Complex Systems,Hangzhou 310018,China)Abstract:Aiming at the problem that the existing Web service QoS prediction approaches did not take the character-istics of users-service into consideration,aprediction algorithm based on Classification and Regression Trees(CART)and SlopeOne was proposed.The history QoS value was first employed to extract the users and servicesfeatures and then classify user-service pair with CART based on the extracted features.To improve the predictionaccuracy,SlopeOne was used to predict QoS on the target user and the target services classification result.The ex-periments on a real-world dataset were conducted,and the experimental results illustrated that the proposed methodhad better prediction accuracy than baseline models.Keywords:Web service;QoS prediction;collaborative filtering;SlopeOne;classification and regression tree0 引言随着越来越多的网络服务被开发出来供用户选择使用,用户在选择服务时往往因许多服务功能相同或相近而面临着选择的困境。服务推荐系统的目标是为用户推荐满足用户功能需求的服务中具有最优或者较优服务质量 的 网络服 务。然而现 实环境下,一个用户可能只调用过很少的服务,从而造成服务质量值的大量缺失。如何在服务质量值缺失的情况下,对缺失的服务质量值进行预测,帮助用户选择计算机集成制造系统 第23卷置最小划分样本数 min_samples_split,若当前节点的训练集样本数少于 min_samples_split,则当前节点停止划分。另一方面,设定叶 节 点 最 小 样 本 数 min_sam-ples_leaf,若 CART 生成树叶节点中的样本数少于min_samples_leaf,则合并该叶节点所在的子树,实现后剪枝,从而进一步提高模型的泛化能力。3.1.5 CART 生成过程CART 是在给定特征变量 X 的条件下输出分类变量Y 的条件概率分布的学习方法。CART 是一棵二叉决策树,它根据最优划分特征和最优划分特征值将输入空间二分为两个子空间,并对子空间进 行 递 归 划 分,直 到 满 足 停 止 划 分 条 件 时 终 止。CART 树一旦生成,新到达的特征向量只要从根节点出发、从上向下到达叶节点,即可完成类别预测。CART 的生成算法具体描述如下:算法2 CART 的生成算法。输入:训练数据集 D 和停止划分的条件。输出:CART 决策树使用训练数据集,从根节点开始,递归地对每个节点进行如下分割,构建 CART 决策树:(1)设当前节点数据集为 D。寻找当前数据集D 的最优划分特征和最优划分特征值。具体如下:1)对于数据集 D 的所有特征 X 及其可能取的特征值x,根据样本点对 X>x 的测试结果为“是”或者“否”,将 D 分割成D1和 D2两部分。利用IG算法计算信息增益。2)选取步骤1)中信息增益最大的特征和特征值,作为最优划分特征和最优划分特征值。(2)根据最优划分特征和最优划分特征值,将当前数据集划分为2个子数据集 D1和 D2,即当前节点生成2个子节点。(3)对生成的 2 个子节点递归调用步骤(1)和(2),直到满足停止条件。(4)基于最小叶节点数 min_samples_leaf 准则进行后剪枝,合并满足条件的子树为新的叶节点。(5)输出 CART 决策树。本文使用的停止划分条件为当前节点中的样本个数小于指定的阈值 min_samples_split。3.2 目标用户—服务对的分类预测对于给定的特征向量,从根节点开始,递归地与当前节点存储的最优划分特征 X 对应的最优划分特征值x 作比较,若测试特征向量中特征 X 对应的特征值大于x,则将当前节点更新为当前节点的左孩子节点,否则将当前节点更新为当前节点的右孩子节点,递归直到 当前节点 更 新为叶节 点 时停止。输出测试特征向量的分类为该叶节点中训练样本集合的分类,若该样本集合中的样本不属于同一个类,则 使 用 多 数 表 决 决 定 其 类 别。 同 时 为 了 避 免CART 的过拟合,将 输出上 下 浮动一个 单 位,即输出为一个区间分类标签集合。3.3 基于分类集合的加权SlopeOne预测方法SlopeOne是 一 种 基 于 回 归 偏 好 的 协 同 过 滤算 法,它 假 定 服 务 之 间 存 在 某 种 线 性 关 系 ,这 种线性关系可以通过 某 个 函 数 表 示 ,基 于 该 函 数 估计用户 对 服 务 的 QoS。 本 文 通 过 以 下 两 个 方 面改进基本的 SlopeOne方法:①考虑同时调用 相 同服务的用户数量对 预 测 结 果 的 影 响 ,给 予 那 些 存在更多历史调用记录的服 务 以 更 大 的 权 重 ;②Sl-opeOne进行 回 归 预 测 时,仅 使 用 与 缺 失 QoS 值分类结 果 一 致 的 历 史 服 务 质 量 值。 通 过 上 述 两个 改 进,有 可 能 降 低 预 测 的 时 间 复 杂 度、提 高 预测准确度。3.3.1 线性回归预测器SlopeOne使用线性回归预测器f(x)=x+b进行回归预测,该线性函数用于表示服务之间的线性关系。 下 面 给 出 该 最 优 线 性 回 归 预 测 器 的 推 导过程。给定两个 向量V= {vi|i=1,2,…,n}和 W ={wi|i=1,2,…,n}。使用线性回归预测器f(x)=x+b,x=vi预 测 wi,得 到 预 测 模 型 的 最 小 损 失 函数为min∑ni=1(vi+b-wi)。 (8)最小损失函数只存在唯一的未知参数常量b。因此,可以将求解此最优线性回归预测器转换为求解最优常量b。通过求导得到常量b为b=∑ni=1wi-vin, (9)即最优常量b为向量V 和W 的平均偏差。3.3.2 基于 CART分类的加权SlopeOne预测方法SlopeOne使用上述f(x)=x+b线性回归预测器进行预测。考虑表1所示的一个 QoS稀疏矩阵,其中 “?”表 示 待 预 测 的 QoS,空 白 处 表 示 该 QoS缺失。8014 徐文庭 等:基于 CART 与 SlopeOne的服务质量预测算法表1 用户—服务服务质量稀疏矩阵service1  service2  service3user1  1.5  2.5?user2  2.0  3.0  1.0user3  3.0  2.0user4  3.0  2.0通过计算得到service1和service3的平均偏差为1,service2和service3的平均偏差为2。因此基于service1预测user1调用服务service3的 QoS为2.5(1.5+1=2.5),基于service2 预测user1 调用服务service3的 QoS为4.5(2.5+2=4.5)。注意到计算上述服务对的平均偏差时,不同服务对拥有不同的用户个数(service1和service3有3个用户,service2和service3有1个用户),因此综合各个局部预测结果给出整体预测时,还需要考虑同时调用服务对的用户个数对预测结果的影响,即?=2.5×3+4.5×13+1=3。 (10)将上述过程一般化,得到如下预测模型:qu,j =∑i∈N(u)(devi,j +qu,i)+|Ui,j(q)|∑i∈N(u)|Ui,j(q)|。(11)式中:qu,j为用户u 调用服务j 的 QoS预测值,N(u)为用户u调用过的服务集合,Ui,j(q)为同时调用过服务i和服务j 的用户集合,devi,j为服务i和服务j的平均偏差,qu,i为用户u 调用服务i的历史 QoS。上述预测过程需要遍历整个 QoS矩阵,不但增大了预测的时间复杂度,而且因使用噪声数据而降低了预测准确度。本文通过仅使用与待预测 QoS具有相同分类的历史 QoS数据进行预测,降低在线预测时间并提高预测准确度。本文将该预测算法命名为 基 于 分 类 的 协 同 过 滤 (Classification-AwareCollaborative Filtering,CACF)。 算 法 具 体 过 程如下:算法3 基于 CART 与SlopeOne的 QoS预测算法。输入:CART 决策树和训练数据集 D,待预 测的用户—服务对。输出:QoS的预测值。(1)预处理训练数据集 D,将 D 按 QoS分类结果划分为若干个子集合,每个子集合中的历史 QoS属于同一个分类集合。(2)创建用户—服务对特征向量(如表1),特征向量由用户u和服务j 的 QoS均值和 QoS标准差组成。(3)使用 CART 决策树,输出特征向量的分类标签lable。(4)选 择 步 骤 (1)中 分 类 结 果 为label 的 子 集合,在子集合上使用式(11)计算预测值。(5)输出预测值。4 实验分析4.1 实验数据集实验使 用 WSDream 数 据 集[16]。该 数 据 集 包括339个用户和5 825个服务,还包含响应时间和吞吐量两个 QoS属性,QoS由真实环境下实际测量得到。本文在响应时间 QoS数据集上进行了大量实验,该数据集被众多研究者用于 QoS值预测[17],因此基于该数据集的实验结果是可靠的。4.2 评估标准使用平均绝对误差评估预测准确度,平均绝对误差的计算公式为MAE =1N∑(u,s)∈testMatrix|qu,s-qu,s|。 (12)同时使用归一化平均绝对误差衡量算法的预测准确度,归一化平均绝对误差的计算公式为NMAE =MAE(∑(u,s)∈testMatrixqu,s)/N。 (13)式中 N 为测试集中待预测 QoS的个数;(u,s)为待预测 QoS的用户—服务对。一个小的平均绝对误差和小 的 归 一 化 平 均 绝 对 误 差 表 示 高 的 预 测 准确度。4.3 实验设置现实环境下,用 户—服务 矩阵 通 常 是 稀 疏 的,因此为了 模 拟 实 际 环 境,本 文 从 原 始 数 据 集 中 选择一部分数 据 作 为 训 练 集,将 余 下 的 QoS数 据 作为测试集。为了评估算法在不同稀疏情 况下的表现,在4个稀疏度情况下进行预测准确度测试,分别为5%,10%,15%,20%。其中,5%的稀疏度意味着用户—服务矩阵只存在5%的真实 QoS,剩余的95% QoS生成 待 预 测 的 测 试 集。 每 个 稀 疏 度重复进行 10 次 实 验,取 10 次 结 果 的 平 均 值 作 为最终的结果。该数据集被广泛用于 QoS值预测准确度评估,因 此 基 于 该 数 据 集 的 实 验 结 果 是 可 靠和稳定的。8015计算机集成制造系统 第23卷将本文提出的预测算法在响应时间数据集上进行离线测试,实验结果均优于其他一些模型。实验参数设置如下:min_samples_split=100,min_sam-ples_leaf=20。4.4 性能比较为了评估预测算法的预测准确度,在本实验数据集上重新实现了一些常见算法,如基于近邻的算法中 基 于 用 户 的 协 调 过 滤 (User based PearsonCorrelation Coefficient,UPCC)算 法、基 于 服 务 的协调 过 滤 (Item based Pearson Correlation Coeffi-cient,IPCC)算 法、网 络 服 务 推 荐 (Web ServiceRecommendation,WSRec),以 及 基 于 模 型 的 方 法MF和基础SlopeOne算法。其中:(1)UPCC UPCC 是一 个基于用户的协同过滤算法,其使用皮尔逊相关系数计算用户之间的相似度,QoS 缺 失 值 用 目 标 用 户 相 似 用 户 群 的 历 史QoS进行预测[18]。(2)IPCC IPCC 是一个基于服务的协同过滤算法,其使用皮尔逊相关系数计算服务之间的相似度,QoS缺失值用目标服务相似服务群的历史 QoS进行预测[4]。(3)WSRec WSRec是一种线性聚合协同过滤算法,其使用一个参数平衡 UPCC 和IPCC 的预测结果在最终结果中的比重[19]。(4)MF MF是 Funk提出的一种隐含语义矩阵分解模型[20]。它假定用户调用服务得到的 QoS值是用户和服务在一个潜在属性空间上的偏好的内积和,MF的关键在于找到一个潜在属性空间。(5)SlopeOne  SlopeOne 是 由 Maclachlan等[2]提出的一种一元一次线性回归预测算法。表2所示为不同数据 稀 疏下不同预 测算法的预测性能。从表2可以看出,相比 其他预 测 模型,本文提出的 CACF模型在各个稀疏度情况下均能得到更 小 的 MAE 和 NMAE,表 明 CART 模 型 相比其他模 型 具 有 更 好 的 预 测 准 确 度,能 够 提 高 更好的个性化服务推荐质量;同时在高稀疏度(5%)情 况 下,CART 的 预 测 准 确 度 提 升 更 加 明 显(23%),说明相比其他模型,CART 能够在高稀疏性情况下 表 现 良 好,能 够 更 好 地 解 决 现 实 环 境 下的数据稀 疏 问 题。另 外 可 以 看 出,随 着 矩 阵 密 度的增大,MAE 和 NMAE 逐渐变小,说明增多训练集中包含的 QoS调 用 记 录 可 以 提 高 预 测 准 确 度,因此鼓励用户提供更多的信息有利于提高 服务推荐的质量。表2 响应时间性能比较模型训练矩阵密度5% 10% 15% 20%MAE  NMAE  MAE  NMAE  MAE  NMAE  MAE  NMAESlopeOne  0.712 6  0.875 7  0.692 9  0.856 0  0.688 6  0.854 4  0.684 3  0.849 2IPCC  0.683 3  0.842 2  0.624 8  0.774 1  0.603 7  0.746 4  0.584 9  0.725 3UPCC  0.676 3  0.833 5  0.630 4  0.781 1  0.617 2  0.763 0  0.605 3  0.750 6UIPCC  0.654 2  0.806 3  0.615 7  0.762 8  0.602 6  0.745 0  0.582 5  0.722 3MF  0.644 1  0.793 9  0.540 5  0.669 7  0.520 7  0.643 8  0.502 3  0.622 9CACF  0.497 5  0.610 9  0.460 5  0.569 8  0.453 1  0.560 0  0.441 7  0.548 44.5 CART分类准确率评估CART 使用IG 算法选择最优划分特征和最优划分特征值,以划分当前节点、生成孩子节点。划分过 程 递 归 进 行,直 到 满 足 停 止 划 分 条 件 为 止。CART 是一种直观、易于理解的分类方法,但 同 时也存在过拟合的潜在风险,为了最大程度地提高模型的泛化能力,本文同时使用预剪枝和后剪枝来降低生成树的高度,以降低模型的复杂度、提高分类树模型的泛化能力。如图2所示,随着参数 min_samples_leaf 的增大,分类准确度率开始上升,之后变得平缓,当增大到较大 的 值 (160)后 开 始 明 显 地 下 降。 这 说 明 当min_samples_leaf 较小时,适当增大该值可以降低分类树的高度、降低模型的复杂度、提高模型的泛化能力。但当参数的值设定得较大时,合并过多的子树将导致合并后叶节点的信息熵较大,导致分类树的欠拟合,降低预测 准 确 率。因 此,min_samples_leaf 最终取值 40,且 在 该 值 取 得 了 最 佳 的 预 测 准8016 徐文庭 等:基于 CART 与 SlopeOne的服务质量预测算法确度。另一方面,对 于 参 数 min_samples_split,该 参数在值100 处 取 得 了 最 佳 的 分 类 准 确 度,与 参 数min_samples_leaf 类 似,取 值 较 小 或 者 较 大,均 会因为过拟 合 或 者 欠 拟 合 而 降 低 模 型 的 泛 化 能 力,以及 分 类 预 测 准 确 度。 因 此,该 参 数 最 终 取 值为100。4.6 参数 min_samples_split的敏感性分析图3所示为参数 min_samples_split对预测准确度的影响,参数min_samples_split是当前节点分割所必须拥有的最少样本数,用来控制 CART 的深度,实现 CART 的预剪 枝而有效 地 缓解 CART 的过拟合现象。从图3可以看出,min_samples_split取值较大或者较小时,在不同稀疏度情况下均会降低模型的预测准确度。这是由于当 min_samples_split取值较小时,剪枝不充分导致了 CART 的过拟合;当 min_samples_split取值较大时,由于过度剪枝而降低了 CART 树的分类能力,从而降低了预测准确度。综合各个稀疏度的实验结果可以看出,min_samples_split取80~120之间时,预测算法取得了最优或者接近最优的预测准确度,因此该参数最终取值为100。4.7 参数 min_samples_leaf的敏感性分析图4所示为参数 min_samples_leaf 对预测准确度的影响,参数 min_samples_leaf 是叶节点必须拥有的最少样本数,当分类树创建完成后,将叶节点数少于 min_samples_leaf 的子树合并为新的叶节点,可以降低模型树的复杂度、提高模型树适应新样本的能力。从图4可以看出,min_samples_leaf 取值较大或者较小时,在不同稀疏度情况下均会降低模型的 预 测 准 确 度。 这 是 由 于 当 min_samples_leaf 取值较小时,剪枝不充分导致了 CART 的过拟合;当 min_samples_leaf 取值较大时,由于过度剪枝而降低了 CART 的分类能力,从而降低了预测准确度。综合各个 稀 疏 度 的 实 验 结 果,最 终 取 min_samples_leaf 为20。8017计算机集成制造系统 第23卷4.8 矩阵密度的敏感性分析矩阵密度表示用户—服务历史 调 用 数 量 占 用户数量与 服 务 数 量 乘 积 的 比 例。 矩 阵 密 度 越 小,可用的历 史 数 据 越 少,数 据 稀 疏 性 越 严 重。 为 了研究矩阵 密 度 对 预 测 准 确 性 的 影 响,本 文 将 训 练矩阵密度 设 定 在 [2%,20%]区 间,其 中 间 隔 划 分为2%。同时考虑参数 min_samples_split和 min_samples_leaf 取 不 同 值 对 预 测 准 确 度 的 影 响,将min_samples_split 分 别 设 定 为 80,100,120,将min_samples_leaf 分别设定为10,20,30。实验结果如图5所示,随着矩阵密度的增加,NMAE 迅速减小;当矩阵密度达到较大值后 NMAE 趋向于平稳。这意味 着 矩 阵 密 度 较 小 时,随 着 用 户 和 服 务的历史信息增多,模型的性能得到很大提 高,此时提高预测准确度最好的方法是鼓励用户调 用更多的服务,从 而 增 加 矩 阵 密 度。 当 矩 阵 密 度 达 到 一8018

[返回]
上一篇:基于博弈的业务流程动态任务分配方法
下一篇:海量不完整数据的核心数据选择问题的研究