徐文庭 等 ：基于 ＣＡＲＴ 与 ＳｌｏｐｅＯｎｅ的服务质量预测算法到满足功能需求的最佳服务，成为目前服务计算领域的研究热点。目前，已有国内外研究者提出了不少服务质量预测方法，其中协同过滤方法是服务质量预测的主流方法［１－４］。基于协同过滤的服务质量（Ｑｕａｌｉｔｙ　ｏｆＳｅｒｖｉｃｅ，ＱｏＳ）预测方法主要分为基于近邻的 方 法（如基于用户的方法［４］、基于服务的方法［４］等）和基于模型的方法 （如支持向量机［２１］、矩阵分解［２２］等）两类。基于近邻的方法通常包括相似邻居的选择和基于相似邻居的历史信息进行缺失 ＱｏＳ预测两个步骤。其中相似邻 居的选择是基于近邻方法的关键，通常基于用户或者服务的历史信息，使用某种相似度计算方法为用户或者服务选择若干个最相似的用户或者服务。常用的相似度计算方法有欧式距离、皮尔逊稀疏、余弦相似度等。基于模型的方法利用已存在的历史 ＱｏＳ学习构建一个预测模型，然后利用该预测模型进行缺失值的预测。模型的训练基于不同的假设，通常训练的开销十分巨大，因此常在离线情况下进行，在线预测时使用已完成训练的模型。这些方法的优点在于能够充分利用用户—服务的历史信息预测缺失值，且不要求其他外部信息，从而使协同过滤算法具有较好的预测准确度和较强的适用性。然而，上述协同过滤方法在预测 ＱｏＳ值时存在以下问题：（１）基于模型的方法不能利用新增的用户—服务调用记录来提高预测准确度，每次新增 ＱｏＳ信息时必须重新构建预测模型，而预测模型的构建非常耗时。（２）协同过滤算法筛选相似邻居时需要假定大部分 ＱｏＳ值是稳定和可靠的。然而，ＱｏＳ依赖于用户和服务的网络环境状况，由于网络环境状况充满随机性，用户调用服务得到的 ＱｏＳ值同样充满随机性。另一方面，随着数据稀疏度的升高，协同过滤算法筛选相似邻居的准确度大幅度降低。高稀疏度情况下，一个用户调用过的服务很少，两个用户共同调用过的服务则更加稀少，因此基于很少量的共同调用记录筛选的相似邻居并不准确。特别是若两个用户没有共同调用过相同的服务，则这两个用户将没有机会成为彼此的相似邻居。（３）协 同 过 滤 算 法 预 测 当 前 用 户 调 用 目 标 服务的 ＱｏＳ值时，仅 使 用 当 前 用 户 相 似 用 户 群 对 目标服务的历史调用 ＱｏＳ值。数据稀疏度高的情况下，该 ＱｏＳ值非常稀少，由此得到的预测结果并不可靠。ＳｌｏｐｅＯｎｅ预 测 方 法［２］可 认 为 是 应 对 上 述 问题的一种较 好 的 解 决 方 案。 首 先，ＳｌｏｐｅＯｎｅ方 法是基于服务偏 差 进 行 回 归 预 测，当 新 增 用 户—服务对调用信息 时，仅 需 要 更 新 该 用 户—服 务 对 关联的服务偏差，因此 该 方 法 能 够 快 速 有 效 地 利 用新增信息提高预测 准 确 度 ，从 而 克 服 了 基 于 模 型推荐算法不能处理动 态 数 据 的 问 题 ；其 次，Ｓｌｏｐｅ－Ｏｎｅ为当前用户进行 ＱｏＳ预 测 时，并 不 需 要 为 当前用户筛选相似邻 居，因 此 避 免 了 协 同 过 滤 算 法筛选相 似 邻 居 时 遇 到 的 问 题；最 后，ＳｌｏｐｅＯｎｅ使用的是全部历史 ＱｏＳ信息，而不是 仅 使 用 相 似 邻居的历史 ＱｏＳ信息进行回归预测，避 免 了 协 同 过滤算法在 高 数 据 稀 疏 情 况 下 预 测 结 果 不 可 靠 的问题。尽管如此，直接使用基本的ＳｌｏｐｅＯｎｅ方法仍然存在一些问题：一方面提高了在线预测的时间复杂度，另一方面不可避免地使用了一部分噪声数据用于缺失值预测而降低了预测准确度。因此，本文对基本的 ＳｌｏｐｅＯｎｅ方法进 行 了改 进，以 解 决 上 述 缺陷。本文的主要贡献如下：（１）考虑到其他模型，如位置感知的混合协同过滤 （Ｈｙｂｒｉｄ　Ｌｏｃａｔｉｏｎ－Ａｗａｒｅ　Ｃｏｌｌａｂｏｒａｔｉｖｅ　Ｆｉｌｔｅ－ｒｉｎｇ，ＨＬＡＣＦ）［１１］，只是对用户或者对服务进行分类，提 出 一 个 基 于 分 类 回 归 树 （Ｃｌａｓｓｉｆｉｃａｔｉｏｎ　ＡｎｄＲｅｇｒｅｓｓｉｏｎ　Ｔｒｅｅ，ＣＡＲＴ）的分类模型，对用户—服务对进行分类。（２）针对基本ＳｌｏｐｅＯｎｅ算法存在使用噪声数据进行预测的问题，提出一个基于 ＣＡＲＴ 分类结果的加权ＳｌｏｐｅＯｎｅ预测方法，仅使用待预测用户—服务对所属分类集合的历史 ＱｏＳ值，降低了预测时间复杂度，实现了噪声过滤，从而提高了预测准确度。（３）在一个真实数据集上进行了大量实验，实验结果表明本文方法在数据稀疏情况下具有较好的预测精度。１　相关工作服务推荐技术用于为用户推荐 ＱｏＳ 最优或者较优的服务，对缺失的 ＱｏＳ值进行预测是当前服务推荐过程的关键。协同过滤方法已被广泛用于服务预测，该方法由 Ｒｉｃｈ［５］最早提出，已成功应用于各种商业推荐系统［６－９］。近年来，一些基于近邻的协同过滤方法被用于 ＱｏＳ值预测［１０－１１］。Ｓｕｎ等［１０］提出８０１１计算机集成制造系统 第２３卷一种新的相似度计算方法，以更准确地筛选相似用户和相似服务：首先，根据用户 ＱｏＳ向量中的最大值和最小值归一化 ＱｏＳ 向量，将每个用户的 ＱｏＳ向量的取值范围调整到０～１之间；然后，基于平均欧式距离，使用归一化后的 ＱｏＳ计算相似度，平均欧式距离越小、相似度越大。Ｌｉｕ等［１１］提出一种基于地理位置信息的协同过滤方法 ＨＬＡＣＦ，认为地理位置接近的用户具有相近的网络环境，可以得到相近的 ＱｏＳ值。因此在为目标用户和目标服务筛选相似用户和相似服务时，应考虑地理位置的影响。与基于近邻的协同过滤方法直接使用已有数据进行预测不同，基于模型的方法使用已存在的历史调用 ＱｏＳ信息来学习预 测模型［２０］，其主要思想是使用属性来构建用户和服务之间的关联，通过综合用户和服务在相同属性上的偏好实现用户调用服务的 ＱｏＳ预测，通过历史数据进行训练得到预测器。Ｈｅ等［１２］提出一种基于地 理位 置的层次矩阵 分 解（Ｈｉｅｒａｒｃｈｉｃａｌ　Ｍａｔｒｉｘ　Ｆａｃｔｏｒｉｚａｔｉｏｎ，ＨＭＦ）模型，根据用户和服务的地理位置信息，使用 ｋ－Ｍｅａｎｓ方法将全局矩阵划分为多个局部矩阵，其中每个局部矩阵包含部分用户和部分服务；最终的预测结果综合考虑局部矩阵和全局矩阵的预测结果。Ｘｕ等［１３］进一步 扩 展 了 概 率 矩 阵 分 解 （Ｐｒｏｂａｂｉｌｉｓｔｉｃ　ＭａｔｒｉｘＦａｃｔｏｒｉｚａｔｉｏｎ，ＰＭＦ）模型，提高了预测准确度，在训练用户隐含特征向量时考虑用户邻居隐含特征向量的影响。然而，上述方法大多仍未能较好地解决数据动态更新和有效筛选相似邻居的问题。特别是高数据稀疏度下，这些方法 的预测 准确度会大幅度下降。Ｍａｃｌａｃｈｌａｎ等［２］提出的 ＳｌｏｐｅＯｎｅ预测方法以其易于实现、良好的推荐质量受到众多研究者的关注，可以较好地解决上述问题。许多基于 ＳｌｏｐｅＯｎｅ的预测方法被提出并用于传统推荐领域，取得了很好的效果。例 如：Ｚｈａｎｇ 等［１４］提 出 一 种 利 用 ＳｌｏｐｅＯｎｅ填充的基于物品的协同过滤算法；Ｍｉ等［１５］提出首先将物品按照用户评分进行聚类，然后基于目标物品聚类成员的被评分记录，使用ＳｌｏｐｅＯｎｅ算法为目标服务进行评分预测。ＳｌｏｐｅＯｎｅ方法具有的上述良好特性使之可以用于 ＱｏＳ值的预测。然而，基本的 ＳｌｏｐｅＯｎｅ方法存在使用噪声数据进行回归预测的问题。为此，本文提出改进的基本ＳｌｏｐｅＯｎｅ方法，以提高预测准确度。２　服务推荐系统服务推荐系统的重要步骤是，首先为目标用户预测未调用服务的 ＱｏＳ，然后为目标用户推荐 ＱｏＳ最优或者较优的服务。图１所示为本文提出的服务推荐系统的整体框架，具体阐述如下：（１）用 户—ＱｏＳ 矩 阵 　 存 储 了 所 有 历 史 调 用ＱｏＳ值，其中缺省值标记为 Ｎｏｎｅ。（２）抽取训练集和测试集　从原始评分矩阵中随机抽 取 一部分 ＱｏＳ 值，构建训 练 矩阵和测试 矩阵，其中缺省值标记为 Ｎｏｎｅ。（３）分类回归树生成模块　利用训练集数据，使用信息增益（Ｉｎｆｏｒｍａｔｉｏｎ　Ｇａｉｎ，ＩＧ）算法创建分类回归树。（４）用户—服务对的分类预测模块　预测目标用 户—服 务 对 的 ＱｏＳ 时，使 用 ＣＡＲＴ 预 测 该 用户—服务对的分类。（５）基于分类集合的加权ＳｌｏｐｅＯｎｅ预测算法模块　 预 测 目 标 用 户—服 务 对 的 ＱｏＳ 时，ＳｌｏｐｅＯｎｅ仅使用与该目标用户—服务对分类结果一致的用户—服务对的历史 ＱｏＳ值进行回归预测。（６）推荐模块　为目标用户推荐 ＱｏＳ最优或者较优的未调用服务。３　基于 ＣＡＲＴ与ＳｌｏｐｅＯｎｅ的ＱｏＳ预测方法下面具体阐述缺失 ＱｏＳ值的预测方法。首先通过挖掘用户和服务的潜在特征提取出用户和服务的特征向量，并提出一种用户—服务对的类别划分方法。通 过 上 述 两 个 步 骤，成 功 地 在 本 文 中 引 入ＣＡＲＴ 方法。其 次，在基本的 ＳｌｏｐｅＯｎｅ方 法 中 加入基于 ＣＡＲＴ 分类的过 滤机制，从 而 提 高 预 测 准确度。３．１　ＣＡＲＴ生成方法本文所采用的数据集的 ＱｏＳ值来源于现实环８０１２ 徐文庭 等：基于 ＣＡＲＴ 与 ＳｌｏｐｅＯｎｅ的服务质量预测算法境下的实际测量，其使用的响应时间 ＱｏＳ值属于不适用于分类的连续型浮点数值，其取值范围为［－１，２０］。同时，该数据集没有 提供 用 户—服 务 对 生 成ＣＡＲＴ 所必需的有效特征，因此 ＣＡＲＴ 并不适用于原始的 ＱｏＳ数据集。通过将连续型浮点数值转化为离散型整数数值来满足有限 分类类别标签的需求，同时通过挖掘目标用户—服务对的历史信息，提取出用户和服务的个性特征（用户和服务的 ＱｏＳ均值与方差），来满足生成 ＣＡＲＴ 的特征需求，从而实现将 ＣＡＲＴ 应用于 ＱｏＳ数据集的目标。下面依次介绍生成 ＣＡＲＴ 的各个步骤。３．１．１　特征提取用户和服务具有一些固定的属性，其历史信息能够用来预测用户和服务的当前行为，因此本文从用户和服务的历史调用 ＱｏＳ信息中提取出用户和服务的个性特征，这些个性特征表现了用户和服务的某种潜在个性属性。对于一个特定的用户—服务对，可提取出ｕｓｅｒＭｅａｎ，ｕｓｅｒＳｔｄ，ｗｓＭｅａｎ，ｗｓＳｔｄ 四个特征。其中：ｕｓｅｒＭｅａｎ和ｗｓＭｅａｎ 是用户和服务历史调用 ＱｏＳ的均值；ｕｓｅｒＳｔｄ 和ｗｓＳｔｄ 是用户和服务历史调用 ＱｏＳ的标准差。因此，对于每一个特定的用户—服务对，均能得到一个唯一的用户—服务对特征向量。３．１．２　类别标签划分本文采用的数据集来自真实环境下的实际测量，且为连续型浮点数值，然而 ＣＡＲＴ 的生成需要使用离散型数值。因此，将连续型浮点数值向下取整，转化为生成 ＣＡＲＴ 所需要的离散型整数数值，从而得到２１个分类标签，将构建 ＣＡＲＴ 树的过程转换为一个多分类的问题。３．１．３　特征选择ＣＡＲＴ 使用ＩＧ 算法选择最优划分特征和最优划分特征值，以划分当前节点、生成孩子节点。为了便于说明ＩＧ 算法，下面首先给出熵、条件熵和信息增益的概念。熵是表明随机变量不确定性的度量，熵越大，随机变量的不确定性就越大，即样本集合的熵越大，样本的类别标签越分散，方差越大。设 Ｘ 是一个取有限个值的随机变量，其概率分布为Ｐ（Ｘ ＝ｘｉ）＝ｐｉ，ｉ＝１，２，…，ｎ。 （１）则随机变量 Ｘ 的熵定义为Ｈ（Ｘ）＝－∑ｎｉ＝１ｐｉｌｏｇｅｐｉ。 （２）条件熵 Ｈ（Ｙ｜Ｘ）表示在已知随机变量 Ｘ 的条件下随机变量Ｙ 的不确定性，定义为给定 Ｘ 的条件下Ｙ 的条件概率分布熵对Ｘ 的数学期望：Ｈ（Ｙ｜Ｘ）＝∑ｎｉ＝１ｐｉＨ （Ｙ｜Ｘ ＝ｘｉ）。 （３）令上述 Ｘ 表示特征、Ｙ 表示类，则对于训练数据集 Ｄ，其信息增益ｇ（Ｄ，Ｘ）定义为集合 Ｄ 的经验熵 Ｈ （Ｄ）与特征 Ｘ 给定条件下Ｄ 的经验条件熵 Ｈ（Ｙ｜Ｘ）之差，即ｇ（Ｄ，Ｘ）＝ Ｈ（Ｄ）－Ｈ（Ｄ｜Ｘ）。 （４）上述公式表明，信息增益表示由于特征 Ｘ 而使对数据集Ｄ 的分类不确定性减少的程度。对于数据集 Ｄ 而言，信息增益依赖于特征，信息增益大的特征具有更强的分类能力。因此特征选择就是选择信息增益最大的特征。下面给出ＩＧ 算法。算法１　ＩＧ 算法。输入：训练数据集 Ｄ 和特征Ｘ。输出：特征 Ｘ 对 训 练 数 据 集 Ｄ 的 信 息 增 益ｇ（Ｄ，Ｘ）。（１）计算数据集 Ｄ 的经验熵 Ｈ （Ｄ）：Ｈ（Ｄ）＝－∑Ｋｋ＝１｜Ｃｋ｜｜Ｄ｜ｌｏｇｅ｜Ｃｋ｜｜Ｄ｜。 （５）式中：｜Ｄ｜为样本容量；ｋ 为类的数目，ｋ＝１，２，…，Ｋ；｜Ｃｋ｜为属于类Ｃｋ的样本个数。（２）计算特征 Ｘ 对数据集Ｄ 的经验条件熵 Ｈ（Ｄ｜Ｘ）：Ｈ（Ｄ｜Ｘ）＝∑ｎｉ＝１｜Ｄｉ｜｜Ｄ｜Ｈ（Ｄｉ）。 （６）式中：根据特征 Ｘ 将数据集Ｄ 划分为ｎ 个子集Ｄ１，Ｄ２，…，Ｄｎ，｜Ｄｉ｜为子集 Ｄｉ的样本个数。（３）计算信息增益ｇ（Ｄ，Ｘ）＝ Ｈ（Ｄ）－Ｈ（Ｄ｜Ｘ）。 （７）３．１．４　ＣＡＲＴ 过拟合处理ＣＡＲＴ 在建树过程中过多 地考 虑 对 训 练 数 据的正确分类，容易创建过于复杂的决策树，从而造成过 拟 合 现 象。 过 拟 合 会 降 低 ＣＡＲＴ 的 泛 化 能力，使 得 对 测 试 集 的 分 类 能 力 变 弱。 通 过 降 低ＣＡＲＴ 决策树的复杂度来 避 免过拟合的 过程称为剪枝。本文通过综合使用预剪枝 和后剪枝 技术来避免过拟合。一方面，通过设置 ＣＡＲＴ 建树过程中的提前终止划分条 件 来降低 ＣＡＲＴ 决策树 的 深 度，实 现 对ＣＡＲＴ 决策树的预剪枝。即为 当 前待划分 节点设８０１３０１６－０６－２８；修订日期：２０１６－０８－２８。Ｒｅｃｅｉｖｅｄ　２８Ｊｕｎｅ　２０１６；ａｃｃｅｐｔｅｄ　２８Ａｕｇ．２０１６．基金项目：国家科技 支 撑 计 划 资 助 项 目 （２０１４ＢＡＫ１４Ｂ０４）；浙 江 省 自 然 科 学 基 金 资 助 项 目 （ＬＹ１２Ｆ０２００３）；中 国 博 士 后 科 学 基 金 资 助 项 目（２０１３Ｍ５４０４９２）。 Ｆｏｕｎｄａｔｉｏｎ　ｉｔｅｍｓ：Ｐｒｏｊｅｃｔ　ｓｕｐｐｏｒｔｅｄ　ｂｙ　ｔｈｅ　Ｎａｔｉｏｎａｌ　Ｋｅｙ　Ｔｅｃｈｎｏｌｏｇｙ　Ｒ＆Ｄ　Ｐｒｏｇｒａｍ， Ｃｈｉｎａ （Ｎｏ．２０１４ＢＡＫ１４Ｂ０４），ｔｈｅ　Ｚｈｅｊｉａｎｇ　Ｐｒｏｖｉｎｃｉａｌ　Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ，Ｃｈｉｎａ（Ｎｏ．ＬＹ１２Ｆ０２００３），ａｎｄ　ｔｈｅ　Ｃｈｉｎｅｓｅ　Ｐｏｓｔｄｏｃｔｏｒａｌ　Ｓｃｉ－ｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ，Ｃｈｉｎａ（Ｎｏ．２０１３Ｍ５４０４９２）．基于 ＣＡＲＴ 与ＳｌｏｐｅＯｎｅ的服务质量预测算法徐文庭１，殷昱煜１，２，３＋，王菊仙１，王兴菲１，余方正１（１．杭州电子科技大学 计算机学院，浙江　杭州　３１００１８；２．浙江大学 电气工程学院，浙江　杭州　３１００２７；３．教育部复杂系统建模与仿真重点实验室，浙江　杭州　３１００１８）摘　要：针对现有的预测算法大多未有效利用用户—服务对的潜在特征问题，提出一种基于分类和 ＳｌｏｐｅＯｎｅ的预测算法，通过用户—服务对的历史服务质量值提取出用户和服务的个性特征（用户和服务的服务质量均值与方差）；基于提取出的特征，使用 ＣＡＲＴ（ｃｌａｓｓｉｆｉｃａｔｉｏｎ　ａｎｄ　ｒｅｇｒｅｓｓｉｏｎ　ｔｒｅｅｓ）对用户—服务对进行分类；使用 Ｓｌｏｐｅ－Ｏｎｅ算法在目标用户和目标 服 务 所 在 的 分 类 集 合 数 据 集 上 进 行 回 归 预 测，提 高 了 预 测 准 确 度；选 用 真 实 数 据 集ＷＳ－Ｄｒｅａｍ 进行实验，实验结果表明该方法在数据稀疏情况下具有较好的预测精度。关键词：Ｗｅｂ服务；服务质量预测；协同过滤；ＳｌｏｐｅＯｎｅ；分类与回归树中图分类号：ＴＰ３１２　　　文献标识码：ＡＱｏＳ　ｐｒｅｄｉｃｔｉｏｎ　ｂａｓｅｄ　ｏｎ　ＣＡＲＴ　ａｎｄ　ＳｌｏｐｅＯｎｅＸＵ　Ｗｅｎｔｉｎｇ１，ＹＩＮ　Ｙｕｙｕ１，２，３＋，ＷＡＮＧ　Ｊｕｘｉａｎ１，ＷＡＮＧ　Ｘｉｎｇｆｅｉ１，ＹＵ　Ｆａｎｇｚｈｅｎｇ１（１．Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｈａｎｇｚｈｏｕ　Ｄｉａｎｚｉ　Ｕｎｉｖｅｒｓｉｔｙ，Ｈａｎｇｚｈｏｕ　３１００１８，Ｃｈｉｎａ；２．Ｃｏｌｌｅｇｅ　ｏｆ　Ｅｌｅｃｔｒｉｃａｌ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｚｈｅｊｉａｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｈａｎｇｚｈｏｕ　３１００１８，Ｃｈｉｎａ；３．Ｋｅｙ　Ｌａｂｏｒａｔｏｒｙ　ｏｆ　Ｍｏｄｅｌｉｎｇ　ａｎｄ　Ｓｉｍｕｌａｔｉｏｎ　ｆｏｒ　Ｃｏｍｐｌｅｘ　Ｓｙｓｔｅｍｓ，Ｈａｎｇｚｈｏｕ　３１００１８，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ａｉｍｉｎｇ　ａｔ　ｔｈｅ　ｐｒｏｂｌｅｍ　ｔｈａｔ　ｔｈｅ　ｅｘｉｓｔｉｎｇ　Ｗｅｂ　ｓｅｒｖｉｃｅ　ＱｏＳ　ｐｒｅｄｉｃｔｉｏｎ　ａｐｐｒｏａｃｈｅｓ　ｄｉｄ　ｎｏｔ　ｔａｋｅ　ｔｈｅ　ｃｈａｒａｃｔｅｒ－ｉｓｔｉｃｓ　ｏｆ　ｕｓｅｒｓ－ｓｅｒｖｉｃｅ　ｉｎｔｏ　ｃｏｎｓｉｄｅｒａｔｉｏｎ，ａｐｒｅｄｉｃｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　Ｃｌａｓｓｉｆｉｃａｔｉｏｎ　ａｎｄ　Ｒｅｇｒｅｓｓｉｏｎ　Ｔｒｅｅｓ（ＣＡＲＴ）ａｎｄ　ＳｌｏｐｅＯｎｅ　ｗａｓ　ｐｒｏｐｏｓｅｄ．Ｔｈｅ　ｈｉｓｔｏｒｙ　ＱｏＳ　ｖａｌｕｅ　ｗａｓ　ｆｉｒｓｔ　ｅｍｐｌｏｙｅｄ　ｔｏ　ｅｘｔｒａｃｔ　ｔｈｅ　ｕｓｅｒｓ　ａｎｄ　ｓｅｒｖｉｃｅｓｆｅａｔｕｒｅｓ　ａｎｄ　ｔｈｅｎ　ｃｌａｓｓｉｆｙ　ｕｓｅｒ－ｓｅｒｖｉｃｅ　ｐａｉｒ　ｗｉｔｈ　ＣＡＲＴ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｅｘｔｒａｃｔｅｄ　ｆｅａｔｕｒｅｓ．Ｔｏ　ｉｍｐｒｏｖｅ　ｔｈｅ　ｐｒｅｄｉｃｔｉｏｎａｃｃｕｒａｃｙ，ＳｌｏｐｅＯｎｅ　ｗａｓ　ｕｓｅｄ　ｔｏ　ｐｒｅｄｉｃｔ　ＱｏＳ　ｏｎ　ｔｈｅ　ｔａｒｇｅｔ　ｕｓｅｒ　ａｎｄ　ｔｈｅ　ｔａｒｇｅｔ　ｓｅｒｖｉｃｅｓ　ｃｌａｓｓｉｆｉｃａｔｉｏｎ　ｒｅｓｕｌｔ．Ｔｈｅ　ｅｘ－ｐｅｒｉｍｅｎｔｓ　ｏｎ　ａ　ｒｅａｌ－ｗｏｒｌｄ　ｄａｔａｓｅｔ　ｗｅｒｅ　ｃｏｎｄｕｃｔｅｄ，ａｎｄ　ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｉｌｌｕｓｔｒａｔｅｄ　ｔｈａｔ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ｍｅｔｈｏｄｈａｄ　ｂｅｔｔｅｒ　ｐｒｅｄｉｃｔｉｏｎ　ａｃｃｕｒａｃｙ　ｔｈａｎ　ｂａｓｅｌｉｎｅ　ｍｏｄｅｌｓ．Ｋｅｙｗｏｒｄｓ：Ｗｅｂ　ｓｅｒｖｉｃｅ；ＱｏＳ　ｐｒｅｄｉｃｔｉｏｎ；ｃｏｌｌａｂｏｒａｔｉｖｅ　ｆｉｌｔｅｒｉｎｇ；ＳｌｏｐｅＯｎｅ；ｃｌａｓｓｉｆｉｃａｔｉｏｎ　ａｎｄ　ｒｅｇｒｅｓｓｉｏｎ　ｔｒｅｅ０　引言随着越来越多的网络服务被开发出来供用户选择使用，用户在选择服务时往往因许多服务功能相同或相近而面临着选择的困境。服务推荐系统的目标是为用户推荐满足用户功能需求的服务中具有最优或者较优服务质量 的 网络服 务。然而现 实环境下，一个用户可能只调用过很少的服务，从而造成服务质量值的大量缺失。如何在服务质量值缺失的情况下，对缺失的服务质量值进行预测，帮助用户选择计算机集成制造系统 第２３卷置最小划分样本数 ｍｉｎ＿ｓａｍｐｌｅｓ＿ｓｐｌｉｔ，若当前节点的训练集样本数少于 ｍｉｎ＿ｓａｍｐｌｅｓ＿ｓｐｌｉｔ，则当前节点停止划分。另一方面，设定叶 节 点 最 小 样 本 数 ｍｉｎ＿ｓａｍ－ｐｌｅｓ＿ｌｅａｆ，若 ＣＡＲＴ 生成树叶节点中的样本数少于ｍｉｎ＿ｓａｍｐｌｅｓ＿ｌｅａｆ，则合并该叶节点所在的子树，实现后剪枝，从而进一步提高模型的泛化能力。３．１．５　ＣＡＲＴ 生成过程ＣＡＲＴ 是在给定特征变量 Ｘ 的条件下输出分类变量Ｙ 的条件概率分布的学习方法。ＣＡＲＴ 是一棵二叉决策树，它根据最优划分特征和最优划分特征值将输入空间二分为两个子空间，并对子空间进 行 递 归 划 分，直 到 满 足 停 止 划 分 条 件 时 终 止。ＣＡＲＴ 树一旦生成，新到达的特征向量只要从根节点出发、从上向下到达叶节点，即可完成类别预测。ＣＡＲＴ 的生成算法具体描述如下：算法２　ＣＡＲＴ 的生成算法。输入：训练数据集 Ｄ 和停止划分的条件。输出：ＣＡＲＴ 决策树使用训练数据集，从根节点开始，递归地对每个节点进行如下分割，构建 ＣＡＲＴ 决策树：（１）设当前节点数据集为 Ｄ。寻找当前数据集Ｄ 的最优划分特征和最优划分特征值。具体如下：１）对于数据集 Ｄ 的所有特征 Ｘ 及其可能取的特征值ｘ，根据样本点对 Ｘ＞ｘ 的测试结果为“是”或者“否”，将 Ｄ 分割成Ｄ１和 Ｄ２两部分。利用ＩＧ算法计算信息增益。２）选取步骤１）中信息增益最大的特征和特征值，作为最优划分特征和最优划分特征值。（２）根据最优划分特征和最优划分特征值，将当前数据集划分为２个子数据集 Ｄ１和 Ｄ２，即当前节点生成２个子节点。（３）对生成的 ２ 个子节点递归调用步骤（１）和（２），直到满足停止条件。（４）基于最小叶节点数 ｍｉｎ＿ｓａｍｐｌｅｓ＿ｌｅａｆ 准则进行后剪枝，合并满足条件的子树为新的叶节点。（５）输出 ＣＡＲＴ 决策树。本文使用的停止划分条件为当前节点中的样本个数小于指定的阈值 ｍｉｎ＿ｓａｍｐｌｅｓ＿ｓｐｌｉｔ。３．２　目标用户—服务对的分类预测对于给定的特征向量，从根节点开始，递归地与当前节点存储的最优划分特征 Ｘ 对应的最优划分特征值ｘ 作比较，若测试特征向量中特征 Ｘ 对应的特征值大于ｘ，则将当前节点更新为当前节点的左孩子节点，否则将当前节点更新为当前节点的右孩子节点，递归直到 当前节点 更 新为叶节 点 时停止。输出测试特征向量的分类为该叶节点中训练样本集合的分类，若该样本集合中的样本不属于同一个类，则 使 用 多 数 表 决 决 定 其 类 别。 同 时 为 了 避 免ＣＡＲＴ 的过拟合，将 输出上 下 浮动一个 单 位，即输出为一个区间分类标签集合。３．３　基于分类集合的加权ＳｌｏｐｅＯｎｅ预测方法ＳｌｏｐｅＯｎｅ是 一 种 基 于 回 归 偏 好 的 协 同 过 滤算 法，它 假 定 服 务 之 间 存 在 某 种 线 性 关 系 ，这 种线性关系可以通过 某 个 函 数 表 示 ，基 于 该 函 数 估计用户 对 服 务 的 ＱｏＳ。 本 文 通 过 以 下 两 个 方 面改进基本的 ＳｌｏｐｅＯｎｅ方法：①考虑同时调用 相 同服务的用户数量对 预 测 结 果 的 影 响 ，给 予 那 些 存在更多历史调用记录的服 务 以 更 大 的 权 重 ；②Ｓｌ－ｏｐｅＯｎｅ进行 回 归 预 测 时，仅 使 用 与 缺 失 ＱｏＳ 值分类结 果 一 致 的 历 史 服 务 质 量 值。 通 过 上 述 两个 改 进，有 可 能 降 低 预 测 的 时 间 复 杂 度、提 高 预测准确度。３．３．１　线性回归预测器ＳｌｏｐｅＯｎｅ使用线性回归预测器ｆ（ｘ）＝ｘ＋ｂ进行回归预测，该线性函数用于表示服务之间的线性关系。 下 面 给 出 该 最 优 线 性 回 归 预 测 器 的 推 导过程。给定两个 向量Ｖ＝ ｛ｖｉ｜ｉ＝１，２，…，ｎ｝和 Ｗ ＝｛ｗｉ｜ｉ＝１，２，…，ｎ｝。使用线性回归预测器ｆ（ｘ）＝ｘ＋ｂ，ｘ＝ｖｉ预 测 ｗｉ，得 到 预 测 模 型 的 最 小 损 失 函数为ｍｉｎ∑ｎｉ＝１（ｖｉ＋ｂ－ｗｉ）。 （８）最小损失函数只存在唯一的未知参数常量ｂ。因此，可以将求解此最优线性回归预测器转换为求解最优常量ｂ。通过求导得到常量ｂ为ｂ＝∑ｎｉ＝１ｗｉ－ｖｉｎ， （９）即最优常量ｂ为向量Ｖ 和Ｗ 的平均偏差。３．３．２　基于 ＣＡＲＴ分类的加权ＳｌｏｐｅＯｎｅ预测方法ＳｌｏｐｅＯｎｅ使用上述ｆ（ｘ）＝ｘ＋ｂ线性回归预测器进行预测。考虑表１所示的一个 ＱｏＳ稀疏矩阵，其中 “？”表 示 待 预 测 的 ＱｏＳ，空 白 处 表 示 该 ＱｏＳ缺失。８０１４ 徐文庭 等：基于 ＣＡＲＴ 与 ＳｌｏｐｅＯｎｅ的服务质量预测算法表１　用户—服务服务质量稀疏矩阵ｓｅｒｖｉｃｅ１　 ｓｅｒｖｉｃｅ２　 ｓｅｒｖｉｃｅ３ｕｓｅｒ１　 １．５　 ２．５？ｕｓｅｒ２　 ２．０　 ３．０　 １．０ｕｓｅｒ３　 ３．０　 ２．０ｕｓｅｒ４　 ３．０　 ２．０通过计算得到ｓｅｒｖｉｃｅ１和ｓｅｒｖｉｃｅ３的平均偏差为１，ｓｅｒｖｉｃｅ２和ｓｅｒｖｉｃｅ３的平均偏差为２。因此基于ｓｅｒｖｉｃｅ１预测ｕｓｅｒ１调用服务ｓｅｒｖｉｃｅ３的 ＱｏＳ为２．５（１．５＋１＝２．５），基于ｓｅｒｖｉｃｅ２ 预测ｕｓｅｒ１ 调用服务ｓｅｒｖｉｃｅ３的 ＱｏＳ为４．５（２．５＋２＝４．５）。注意到计算上述服务对的平均偏差时，不同服务对拥有不同的用户个数（ｓｅｒｖｉｃｅ１和ｓｅｒｖｉｃｅ３有３个用户，ｓｅｒｖｉｃｅ２和ｓｅｒｖｉｃｅ３有１个用户），因此综合各个局部预测结果给出整体预测时，还需要考虑同时调用服务对的用户个数对预测结果的影响，即？＝２．５×３＋４．５×１３＋１＝３。 （１０）将上述过程一般化，得到如下预测模型：ｑｕ，ｊ ＝∑ｉ∈Ｎ（ｕ）（ｄｅｖｉ，ｊ ＋ｑｕ，ｉ）＋｜Ｕｉ，ｊ（ｑ）｜∑ｉ∈Ｎ（ｕ）｜Ｕｉ，ｊ（ｑ）｜。（１１）式中：ｑｕ，ｊ为用户ｕ 调用服务ｊ 的 ＱｏＳ预测值，Ｎ（ｕ）为用户ｕ调用过的服务集合，Ｕｉ，ｊ（ｑ）为同时调用过服务ｉ和服务ｊ 的用户集合，ｄｅｖｉ，ｊ为服务ｉ和服务ｊ的平均偏差，ｑｕ，ｉ为用户ｕ 调用服务ｉ的历史 ＱｏＳ。上述预测过程需要遍历整个 ＱｏＳ矩阵，不但增大了预测的时间复杂度，而且因使用噪声数据而降低了预测准确度。本文通过仅使用与待预测 ＱｏＳ具有相同分类的历史 ＱｏＳ数据进行预测，降低在线预测时间并提高预测准确度。本文将该预测算法命名为 基 于 分 类 的 协 同 过 滤 （Ｃｌａｓｓｉｆｉｃａｔｉｏｎ－ＡｗａｒｅＣｏｌｌａｂｏｒａｔｉｖｅ　Ｆｉｌｔｅｒｉｎｇ，ＣＡＣＦ）。 算 法 具 体 过 程如下：算法３　基于 ＣＡＲＴ 与ＳｌｏｐｅＯｎｅ的 ＱｏＳ预测算法。输入：ＣＡＲＴ 决策树和训练数据集 Ｄ，待预 测的用户—服务对。输出：ＱｏＳ的预测值。（１）预处理训练数据集 Ｄ，将 Ｄ 按 ＱｏＳ分类结果划分为若干个子集合，每个子集合中的历史 ＱｏＳ属于同一个分类集合。（２）创建用户—服务对特征向量（如表１），特征向量由用户ｕ和服务ｊ 的 ＱｏＳ均值和 ＱｏＳ标准差组成。（３）使用 ＣＡＲＴ 决策树，输出特征向量的分类标签ｌａｂｌｅ。（４）选 择 步 骤 （１）中 分 类 结 果 为ｌａｂｅｌ 的 子 集合，在子集合上使用式（１１）计算预测值。（５）输出预测值。４　实验分析４．１　实验数据集实验使 用 ＷＳＤｒｅａｍ 数 据 集［１６］。该 数 据 集 包括３３９个用户和５　８２５个服务，还包含响应时间和吞吐量两个 ＱｏＳ属性，ＱｏＳ由真实环境下实际测量得到。本文在响应时间 ＱｏＳ数据集上进行了大量实验，该数据集被众多研究者用于 ＱｏＳ值预测［１７］，因此基于该数据集的实验结果是可靠的。４．２　评估标准使用平均绝对误差评估预测准确度，平均绝对误差的计算公式为ＭＡＥ ＝１Ｎ∑（ｕ，ｓ）∈ｔｅｓｔＭａｔｒｉｘ｜ｑｕ，ｓ－ｑｕ，ｓ｜。 （１２）同时使用归一化平均绝对误差衡量算法的预测准确度，归一化平均绝对误差的计算公式为ＮＭＡＥ ＝ＭＡＥ（∑（ｕ，ｓ）∈ｔｅｓｔＭａｔｒｉｘｑｕ，ｓ）／Ｎ。 （１３）式中 Ｎ 为测试集中待预测 ＱｏＳ的个数；（ｕ，ｓ）为待预测 ＱｏＳ的用户—服务对。一个小的平均绝对误差和小 的 归 一 化 平 均 绝 对 误 差 表 示 高 的 预 测 准确度。４．３　实验设置现实环境下，用 户—服务 矩阵 通 常 是 稀 疏 的，因此为了 模 拟 实 际 环 境，本 文 从 原 始 数 据 集 中 选择一部分数 据 作 为 训 练 集，将 余 下 的 ＱｏＳ数 据 作为测试集。为了评估算法在不同稀疏情 况下的表现，在４个稀疏度情况下进行预测准确度测试，分别为５％，１０％，１５％，２０％。其中，５％的稀疏度意味着用户—服务矩阵只存在５％的真实 ＱｏＳ，剩余的９５％ ＱｏＳ生成 待 预 测 的 测 试 集。 每 个 稀 疏 度重复进行 １０ 次 实 验，取 １０ 次 结 果 的 平 均 值 作 为最终的结果。该数据集被广泛用于 ＱｏＳ值预测准确度评估，因 此 基 于 该 数 据 集 的 实 验 结 果 是 可 靠和稳定的。８０１５计算机集成制造系统 第２３卷将本文提出的预测算法在响应时间数据集上进行离线测试，实验结果均优于其他一些模型。实验参数设置如下：ｍｉｎ＿ｓａｍｐｌｅｓ＿ｓｐｌｉｔ＝１００，ｍｉｎ＿ｓａｍ－ｐｌｅｓ＿ｌｅａｆ＝２０。４．４　性能比较为了评估预测算法的预测准确度，在本实验数据集上重新实现了一些常见算法，如基于近邻的算法中 基 于 用 户 的 协 调 过 滤 （Ｕｓｅｒ　ｂａｓｅｄ　ＰｅａｒｓｏｎＣｏｒｒｅｌａｔｉｏｎ　Ｃｏｅｆｆｉｃｉｅｎｔ，ＵＰＣＣ）算 法、基 于 服 务 的协调 过 滤 （Ｉｔｅｍ　ｂａｓｅｄ　Ｐｅａｒｓｏｎ　Ｃｏｒｒｅｌａｔｉｏｎ　Ｃｏｅｆｆｉ－ｃｉｅｎｔ，ＩＰＣＣ）算 法、网 络 服 务 推 荐 （Ｗｅｂ　ＳｅｒｖｉｃｅＲｅｃｏｍｍｅｎｄａｔｉｏｎ，ＷＳＲｅｃ），以 及 基 于 模 型 的 方 法ＭＦ和基础ＳｌｏｐｅＯｎｅ算法。其中：（１）ＵＰＣＣ　ＵＰＣＣ 是一 个基于用户的协同过滤算法，其使用皮尔逊相关系数计算用户之间的相似度，ＱｏＳ 缺 失 值 用 目 标 用 户 相 似 用 户 群 的 历 史ＱｏＳ进行预测［１８］。（２）ＩＰＣＣ　ＩＰＣＣ 是一个基于服务的协同过滤算法，其使用皮尔逊相关系数计算服务之间的相似度，ＱｏＳ缺失值用目标服务相似服务群的历史 ＱｏＳ进行预测［４］。（３）ＷＳＲｅｃ　ＷＳＲｅｃ是一种线性聚合协同过滤算法，其使用一个参数平衡 ＵＰＣＣ 和ＩＰＣＣ 的预测结果在最终结果中的比重［１９］。（４）ＭＦ　ＭＦ是 Ｆｕｎｋ提出的一种隐含语义矩阵分解模型［２０］。它假定用户调用服务得到的 ＱｏＳ值是用户和服务在一个潜在属性空间上的偏好的内积和，ＭＦ的关键在于找到一个潜在属性空间。（５）ＳｌｏｐｅＯｎｅ　 ＳｌｏｐｅＯｎｅ 是 由 Ｍａｃｌａｃｈｌａｎ等［２］提出的一种一元一次线性回归预测算法。表２所示为不同数据 稀 疏下不同预 测算法的预测性能。从表２可以看出，相比 其他预 测 模型，本文提出的 ＣＡＣＦ模型在各个稀疏度情况下均能得到更 小 的 ＭＡＥ 和 ＮＭＡＥ，表 明 ＣＡＲＴ 模 型 相比其他模 型 具 有 更 好 的 预 测 准 确 度，能 够 提 高 更好的个性化服务推荐质量；同时在高稀疏度（５％）情 况 下，ＣＡＲＴ 的 预 测 准 确 度 提 升 更 加 明 显（２３％），说明相比其他模型，ＣＡＲＴ 能够在高稀疏性情况下 表 现 良 好，能 够 更 好 地 解 决 现 实 环 境 下的数据稀 疏 问 题。另 外 可 以 看 出，随 着 矩 阵 密 度的增大，ＭＡＥ 和 ＮＭＡＥ 逐渐变小，说明增多训练集中包含的 ＱｏＳ调 用 记 录 可 以 提 高 预 测 准 确 度，因此鼓励用户提供更多的信息有利于提高 服务推荐的质量。表２　响应时间性能比较模型训练矩阵密度５％ １０％ １５％ ２０％ＭＡＥ　 ＮＭＡＥ　 ＭＡＥ　 ＮＭＡＥ　 ＭＡＥ　 ＮＭＡＥ　 ＭＡＥ　 ＮＭＡＥＳｌｏｐｅＯｎｅ　 ０．７１２　６　 ０．８７５　７　 ０．６９２　９　 ０．８５６　０　 ０．６８８　６　 ０．８５４　４　 ０．６８４　３　 ０．８４９　２ＩＰＣＣ　 ０．６８３　３　 ０．８４２　２　 ０．６２４　８　 ０．７７４　１　 ０．６０３　７　 ０．７４６　４　 ０．５８４　９　 ０．７２５　３ＵＰＣＣ　 ０．６７６　３　 ０．８３３　５　 ０．６３０　４　 ０．７８１　１　 ０．６１７　２　 ０．７６３　０　 ０．６０５　３　 ０．７５０　６ＵＩＰＣＣ　 ０．６５４　２　 ０．８０６　３　 ０．６１５　７　 ０．７６２　８　 ０．６０２　６　 ０．７４５　０　 ０．５８２　５　 ０．７２２　３ＭＦ　 ０．６４４　１　 ０．７９３　９　 ０．５４０　５　 ０．６６９　７　 ０．５２０　７　 ０．６４３　８　 ０．５０２　３　 ０．６２２　９ＣＡＣＦ　 ０．４９７　５　 ０．６１０　９　 ０．４６０　５　 ０．５６９　８　 ０．４５３　１　 ０．５６０　０　 ０．４４１　７　 ０．５４８　４４．５　ＣＡＲＴ分类准确率评估ＣＡＲＴ 使用ＩＧ 算法选择最优划分特征和最优划分特征值，以划分当前节点、生成孩子节点。划分过 程 递 归 进 行，直 到 满 足 停 止 划 分 条 件 为 止。ＣＡＲＴ 是一种直观、易于理解的分类方法，但 同 时也存在过拟合的潜在风险，为了最大程度地提高模型的泛化能力，本文同时使用预剪枝和后剪枝来降低生成树的高度，以降低模型的复杂度、提高分类树模型的泛化能力。如图２所示，随着参数 ｍｉｎ＿ｓａｍｐｌｅｓ＿ｌｅａｆ 的增大，分类准确度率开始上升，之后变得平缓，当增大到较大 的 值 （１６０）后 开 始 明 显 地 下 降。 这 说 明 当ｍｉｎ＿ｓａｍｐｌｅｓ＿ｌｅａｆ 较小时，适当增大该值可以降低分类树的高度、降低模型的复杂度、提高模型的泛化能力。但当参数的值设定得较大时，合并过多的子树将导致合并后叶节点的信息熵较大，导致分类树的欠拟合，降低预测 准 确 率。因 此，ｍｉｎ＿ｓａｍｐｌｅｓ＿ｌｅａｆ 最终取值 ４０，且 在 该 值 取 得 了 最 佳 的 预 测 准８０１６ 徐文庭 等：基于 ＣＡＲＴ 与 ＳｌｏｐｅＯｎｅ的服务质量预测算法确度。另一方面，对 于 参 数 ｍｉｎ＿ｓａｍｐｌｅｓ＿ｓｐｌｉｔ，该 参数在值１００ 处 取 得 了 最 佳 的 分 类 准 确 度，与 参 数ｍｉｎ＿ｓａｍｐｌｅｓ＿ｌｅａｆ 类 似，取 值 较 小 或 者 较 大，均 会因为过拟 合 或 者 欠 拟 合 而 降 低 模 型 的 泛 化 能 力，以及 分 类 预 测 准 确 度。 因 此，该 参 数 最 终 取 值为１００。４．６　参数 ｍｉｎ＿ｓａｍｐｌｅｓ＿ｓｐｌｉｔ的敏感性分析图３所示为参数 ｍｉｎ＿ｓａｍｐｌｅｓ＿ｓｐｌｉｔ对预测准确度的影响，参数ｍｉｎ＿ｓａｍｐｌｅｓ＿ｓｐｌｉｔ是当前节点分割所必须拥有的最少样本数，用来控制 ＣＡＲＴ 的深度，实现 ＣＡＲＴ 的预剪 枝而有效 地 缓解 ＣＡＲＴ 的过拟合现象。从图３可以看出，ｍｉｎ＿ｓａｍｐｌｅｓ＿ｓｐｌｉｔ取值较大或者较小时，在不同稀疏度情况下均会降低模型的预测准确度。这是由于当 ｍｉｎ＿ｓａｍｐｌｅｓ＿ｓｐｌｉｔ取值较小时，剪枝不充分导致了 ＣＡＲＴ 的过拟合；当 ｍｉｎ＿ｓａｍｐｌｅｓ＿ｓｐｌｉｔ取值较大时，由于过度剪枝而降低了 ＣＡＲＴ 树的分类能力，从而降低了预测准确度。综合各个稀疏度的实验结果可以看出，ｍｉｎ＿ｓａｍｐｌｅｓ＿ｓｐｌｉｔ取８０～１２０之间时，预测算法取得了最优或者接近最优的预测准确度，因此该参数最终取值为１００。４．７　参数 ｍｉｎ＿ｓａｍｐｌｅｓ＿ｌｅａｆ的敏感性分析图４所示为参数 ｍｉｎ＿ｓａｍｐｌｅｓ＿ｌｅａｆ 对预测准确度的影响，参数 ｍｉｎ＿ｓａｍｐｌｅｓ＿ｌｅａｆ 是叶节点必须拥有的最少样本数，当分类树创建完成后，将叶节点数少于 ｍｉｎ＿ｓａｍｐｌｅｓ＿ｌｅａｆ 的子树合并为新的叶节点，可以降低模型树的复杂度、提高模型树适应新样本的能力。从图４可以看出，ｍｉｎ＿ｓａｍｐｌｅｓ＿ｌｅａｆ 取值较大或者较小时，在不同稀疏度情况下均会降低模型的 预 测 准 确 度。 这 是 由 于 当 ｍｉｎ＿ｓａｍｐｌｅｓ＿ｌｅａｆ 取值较小时，剪枝不充分导致了 ＣＡＲＴ 的过拟合；当 ｍｉｎ＿ｓａｍｐｌｅｓ＿ｌｅａｆ 取值较大时，由于过度剪枝而降低了 ＣＡＲＴ 的分类能力，从而降低了预测准确度。综合各个 稀 疏 度 的 实 验 结 果，最 终 取 ｍｉｎ＿ｓａｍｐｌｅｓ＿ｌｅａｆ 为２０。８０１７计算机集成制造系统 第２３卷４．８　矩阵密度的敏感性分析矩阵密度表示用户—服务历史 调 用 数 量 占 用户数量与 服 务 数 量 乘 积 的 比 例。 矩 阵 密 度 越 小，可用的历 史 数 据 越 少，数 据 稀 疏 性 越 严 重。 为 了研究矩阵 密 度 对 预 测 准 确 性 的 影 响，本 文 将 训 练矩阵密度 设 定 在 ［２％，２０％］区 间，其 中 间 隔 划 分为２％。同时考虑参数 ｍｉｎ＿ｓａｍｐｌｅｓ＿ｓｐｌｉｔ和 ｍｉｎ＿ｓａｍｐｌｅｓ＿ｌｅａｆ 取 不 同 值 对 预 测 准 确 度 的 影 响，将ｍｉｎ＿ｓａｍｐｌｅｓ＿ｓｐｌｉｔ 分 别 设 定 为 ８０，１００，１２０，将ｍｉｎ＿ｓａｍｐｌｅｓ＿ｌｅａｆ 分别设定为１０，２０，３０。实验结果如图５所示，随着矩阵密度的增加，ＮＭＡＥ 迅速减小；当矩阵密度达到较大值后 ＮＭＡＥ 趋向于平稳。这意味 着 矩 阵 密 度 较 小 时，随 着 用 户 和 服 务的历史信息增多，模型的性能得到很大提 高，此时提高预测准确度最好的方法是鼓励用户调 用更多的服务，从 而 增 加 矩 阵 密 度。 当 矩 阵 密 度 达 到 一８０１８