David

Transcription

1 第一部分基础技术 第二章推荐系统中的数据挖掘方法 Xavier Amatriain, Alejandro Jaimes, Nuria Oliver, and Josep M. Pujol i 摘要 : 本章概述了推荐系统中用到的一些重要的数据挖掘技术 首先描述的是常见的数据预 处理方法, 如抽样和降维 其次, 回顾推荐系统中最重要的分类技术, 包括贝叶斯网络和支持向量 机 我们对 K-means 聚类算法进行描述并讨论其几个替代算法 我们也会介绍有效训练过程中的关 联规则和相关算法 除了介绍这些技术外, 我们也会考察它们在推荐系统中的使用情况, 同时介绍 它们成功应用的案例 2.1 引言 推荐系统典型地运用了其它相邻领域的技术和方法, 诸如人机交互和信息检索 但是, 大多数 系统的核心算法都可以理解成数据挖掘技术的一个特例 数据挖掘的过程一般由三个连续执行的步骤组成 : 数据预处理, 数据分析, 结果解释 ( 见图 2.1) 我们将在 2.2 节中分析一些最重要的数据预处理方法 鉴于数据抽样, 数据降维, 距离函数 在推荐系统中的意义及所担任的重要角色, 我们将特别地关注这些内容 从 2.3 节到 2.5 节, 我们将 总体介绍在推荐系统中最常使用的数据挖掘方法 : 分类, 聚类, 关联规则发现 ( 图 2.1 详细的显示 了本章中包含的不同主题 ) Xavier Amatriain Telefonica Research, Via Augusta, 122, Barcelona 08021, Spain xar@tid.es Alejandro Jaimes Yahoo! Research, Av.Diagonal, 177, Barcelona 08018, Spain. Work on the chapter was performed while the author was at Telefonica Research. ajaimes@yahoo-inc.com Nuria Oliver Telefonica Research, Via Augusta, 122, Barcelona 08021, Spain nuriao@tid.es Josep M. Pujol Telefonica Research, Via Augusta, 122, Barcelona 08021, Spain jmps@tid.es F. Ricci et al. (eds.), Recommender Systems Handbook, DOI / _2, Springer Science+Business Media, LLC

2 图 2.1 数据挖掘中主要的步骤和方法及其对应的章节 本章不会完整回顾数据挖掘方法, 而是强调数据挖掘算法在推荐系统领域中的影响, 并概述已 经成功应用的主要数据挖掘技术 感兴趣的读者可以进一步参考数据挖掘课本 ( 例如, 见 28,73 ), 或参考贯穿全章的引文 2.2 数据预处理 我们把数据定义为一组对象及其属性的集合, 其中属性定义为性质或者是对象的特征 对象的 其它名称包括记录, 物品, 得分, 样本, 观察值, 或者实例 属性也可以被称为变量, 字段, 特性, 或者特征 真实数据通常需要经过预处理, 以便于机器学习技术在分析阶段所使用 本节紧紧围绕推荐系 统设计三个尤为重要的问题展开 首先, 我们回顾不同的相似度, 或者是距离度量方式 其次, 我 们需要讨论抽样问题, 一种可以减少大数据集中物品数量并保持其主要特征的方法 最后, 我们将 阐述降维方法中最常用的技术 相似度度量方法 协同过滤推荐倍受青睐方法之一是使用 knn 分类, 我们将在 章节中讨论 这种分类技术, 2

3 如同大多数的分类和聚类技术, 主要取决于定义合适的相似度或者是距离度量方法 最简单 最常用的距离度量是欧几里得距离 : n 2 k k (2.1) k1 d( x, y) ( x y ) 其中 n 是维数 ( 属性数 ), 闵可夫斯基距离是欧几里得距离的推广 : d( x, y) x k 和 y k 分别是数据对象 x 和 y 的第 K 个属性值 ( 分量 ) n r 1 r ( ) (2.2) k 1 x k y k 其中,r 是距离的度 ( 参数 ) 取决于 r 值的不同, 一般的闵可夫斯基距离有专用的名称 : r=1, 城市街区 ( 也叫曼哈顿 出租车 L1 范数 ) 距离 r=2, 欧几里得距离 (L2 范数 ) r=, 上确界 ( L max 马氏距离定义如下 : 或 L 范数 ), 这是任意维度对象属性间的最大距离 d ( x, y) ( x y) ) 其中,σ 是数据的协方差矩阵 1 T ( x y (2.3) 另一个常用的方法是把物品看做 N 维空间的文档向量, 并且计算它们相似度作为形成夹角的余弦值, 其公式如下 : cos( x, y) ( x y) x y (2.4) 其中 表示向量的点积, x 是向量 x 的长度 这个相似度被称之为余弦相似度或者是 L2 范数 物品之间的相似度还可以用他们的相关度计算, 用以度量对象间的线性关系 尽管有几个相关 系数可能被应用, 但皮尔逊相关性系数是最常用的 给出点 x 和 yσ 协方差, 和它们的标准差 σ, 我们 用以下公式计算皮尔逊相关性 : ( x, y) Peason( x, y) x y (2.5) 推荐系统一般会使用余弦相似度 (Eq. 2.4) 或者是皮尔逊相关性 ( 或者它们的许多变种方法中的一种, 例如加权方案 ) 第四和五章详述在协同过滤中不同距离函数的使用 但是, 前面提到的大部分其它距离度量方法都可能用到 Spertus et al. [69] 在 Orkut 社交网络的环境中做了大规 3

4 模的研究来评估六种不同的相似度度量方法 尽管由于实验的特殊设置, 结果会有偏差, 但有趣的 是余弦相似度是其中效果最好的度量方法 Lathia et al. [48] 也做了一些相似度度量的研究, 其 总结, 在一般的案例中, 推荐系统的预测精确性不受相似度度量方法选择的影响 事实上, 在他们 的工作中, 使用随机的相似度度量有时会产生比使用已知任何众所周知的方法更好的结果 最后, 在一些只有二进制属性的物品案例中, 几个相似度度量方法被提出来 首先, 计算 M01, M10, M11, 和 M00 数量, 其中 M01 代表 X 是 0 同时 Y 是 1 这个属性的数量,M10 代表 X 是 1 同时 Y 是 0 这个属 性的数量, 以此类推 根据这些数值我们可以计算得到 number of matches M : 简单匹配系数 11M00 SMC number of attributes M01M10 M00M11 ;Jaccard 系数 M JC 11 M 01 M M 的一个变型, 计算为 抽样 广义 Jaccard(Tanimoto) 系数, 是 JC 关于连续值属性或计数属性 抽样是数据挖掘从大数据集中选择相关数据子集的主要技术 它在数据预处理和最终解释步骤 中都需要用到 抽样被使用是因为处理全部的数据集计算开销太大 它也可以被用来创建训练和测 试数据集 这个情况下, 训练集被用于分析阶段学习参数或配置算法, 而测试集被用来评估训练阶 段获得的模型或者配置, 确保它在将来产生的未知数据上运行良好 抽样的关键是发现具有整个原始数据集代表性的子集, 也就是说, 其具有与整个数据集大概类 似的兴趣属性 最简单的抽样技术是随机抽样, 任意物品被选中的概率相同 但也有更复杂的方法 例如, 在分层抽样中数据基于特殊特征被分成几个部分, 之后对每个部分独立进行随机抽样 最常用的抽样方法包含使用无取代的抽样 : 当物品被选择的时候, 物品被从整体中取走 但是, 执行取代抽样也是可以的, 物品即使被选择也不用从整体中去除, 允许同样的样本被选择多次 在分离训练集和测试集时, 通常做法是使用 80/20 的训练集和测试集比例, 并使用无替代的标 准随机抽样 这意味着我们使用无替代随机抽样方法去选择 20% 的实例为测试集, 把剩下的 80% 进行 训练 80/20 的比例应该作为一个经验规则, 一般来说, 超过 2/3 的任何值作为训练集是合适的 抽样可能导致过特殊化划分的训练和测试数据集 因此, 训练过程可以重复好几次 从原始数 据集中创建训练集和测试集, 使用训练数据进行模型训练并且使用测试集中的样例进行测试 接下 来, 选择不同的训练 / 测试集进行训练 / 测试过程, 这个过程会重复 K 次 最后,K 次学习模型的平均 性能被给出 这个过程是著名的交叉验证 交叉验证技术有很多种 在重复随机样本中, 标准的随 机抽样过程要执行 K 次 在 n 折交叉校验中, 数据集被分成 n 份 其中一份被用来测试模型, 剩下 n-1 份被用来进行训练 交叉验证过程重复 n 次,n 个子样本中每一个子样本都只使用一次作为验证数据 最后, 留一法 (LOO) 可以看作是 n 折交叉验证的极端例子, 其中 n 被设置为数据集中物品的数量 因此, 算法运行许多次而每次数据点只使用其中一个作为测试 我们需要注意的是, 正如 Isaksson et al. 讨论的那样, 除非数据集足够的大, 否则交叉验证可能不可信 4

5 在推荐系统中常用的方法是从用户中抽取可用的反馈以用户评分的形式来划分训练和测试 交 叉验证的方法同样也很常见 尽管在一般的案例中标准随机抽样是可接受的, 但是在其它场景中我 们需要用不同的方法定向调整抽样出来的测试集 例如, 我们可能决定只抽样最近的评分数据, 因 为这些是现实情况下我们需要预测的 我们可能还有兴趣确保每个用户的评分比例被保存在测试集, 因此需要对每一个用户使用随机抽样 然而, 所有这些涉及到评估推荐的问题仍是一个探讨和研究 点 降维 推荐系统中不仅有定义高维空间特征的数据集, 而且在空间中信息非常稀疏, 比如 : 每个对象 就那么几个有限的特征有值 密度, 以及点之间的距离, 这些对于聚类和孤立点检测非常重要, 但 在高维空间中的意义并不大 这就是著名的维度灾难 降维技术通过把原始高维空间转化成低维有 助于克服这类问题 稀疏和维度灾难是推荐系统中反复出现的问题 即使在最简单的背景下, 我们很可能都会有成 千上万行的行和列稀疏矩阵, 其中大部分值是零 因此, 降低维度就自然而然了 应用降维技术带 来这样的结果, 其也可以直接适用于计算推荐的预测值, 即它可以作为推荐系统设计的方法, 而不 仅仅是数据预处理技术 接下来, 我们概述两个在推荐系统中最相关的降维算法 : 主成分分析 (PCA) 和奇异值分解 (SVD) 这些技术可以单独作为推荐方法使用, 或作为在本章提到的其它任何技术的预处理步骤 主成分分析 主成分分析 (PCA) 是一种经典统计方法, 被用来发现高维数据集中的模式 主成分分析可以 获得一组有序的成分列表, 其根据最小平方误差计算出变化最大的值 列表中第一个成分所代表的 变化量要比第二个成分所代表的变化量大, 以此类推 我们可以通过忽略这些对变化贡献较小的成 分来降低维度 图 2.2 显示了通过高斯合并产生的二维点云中的 PCA 分析结果 数据集中之后, 主要成分由 u1 和 u 2 来表示 考虑到新坐标轴的长度所涉及的能量被包含在它们的特征向量中 因此, 对于图 2.2 中列举的特殊例子, 第一个成分 u 1占能量的 83.5%, 这意味着移除第二个成分 u 2 暗示将只失去 16.5% 的信息 根据经验规则选择 m 以便于累计能量超过一定的阈值, 一般是 90% PCA 允许我们把数据 投影到新的坐标系中来重新表示原始数据矩阵 : X X 了 m m 维度并保证包含大部分的原始数据 X 的信息 Wm m n m nm 新的数据矩阵 ' X 降低 5

6 图 2.2 PCA 分析基于高斯合并的二维点云 使用 PCA 得到的主成分是 u 1 和 u 2, 其长度与到包含在所有成分的能量相关 PCA 是一种强大的技术, 但也有重要的限制 PCA 依赖于以线性合并为基础的经验数据集, 尽管 一般的非线性 PCA 方法已经提出 PCA 的另一个重要假设是原始数据集是从高斯分布中抽取出来的 当这个假设不正确时, 就无法保证主要成分的有效性 尽管目前的趋势似乎表明其它的矩阵分解技术更受欢迎, 诸如 SVD 或者是非负矩阵分解, 但是 早期用得最多还是 PCA Goldberg et al. 在在线笑话推荐的内容中提出使用 PCA 方法 他们的系统, 著名的 Eigentaste, 开始于标准的用户评分矩阵 然后从所有用户都评分过的 item 里选出一个子集 作为测试集 这个新矩阵被用来计算全局相关矩阵, 这些矩阵使用了标准的二维 PCA 奇异值分解 奇异值分解是一个强大的降维工具 它是矩阵分解方法的特殊实现, 因此它也和 PCA 相关 在 SVD 分解中的关键问题是发现低维特征空间, 这些新特征代表概念以及在集合内容中的每一个概念 强度都是可计算的 因为 SVD 可以自动获取到低维空间上的语义概念, 它可以被用来当作潜在语义 分析的基础, 潜在语义分析是一种在信息检索中非常受欢迎的文本分类技术 SVD 的核心算法基于以下的理论 : 把矩阵 A 分解成 A= UV T 是可行的 给出 n m 矩阵的数 据 A(n 个物品,m 个特征 ), 我们可以获得一个 n r 的矩阵 U(n 个物品,r 个概念 ), 一个 r r 的对 角矩阵 R( 概念的长度 ), 以及 m r的矩阵 V(m 特征,r 概念 ) 图 2.3 阐述了这个想法 R 的对角 矩阵包含奇异值, 其总是为正并且是降序排列 U 矩阵可以解释成物品概念相似矩阵, 矩阵 V 是特 征概念相似性矩阵 6

7 图 2.3 阐述了最基本的 SVD: 物品 特征矩阵可以分解成三个不同的部分 : 物品 概念, 概念强度, 概念 特征 为了计算矩形矩阵 A 的 SVD, 我们考虑如下公式 AA T 和 A T A U 的列是 AA T 的特征向量,V 的列是 A T A 的 特征向量 矩阵对角线上的奇异值是 AA T 和 A T A 非零特征值的平方根 因此, 为了计算矩阵 A 的 SVD 我 们首先计算 AA T (T) 以及 A T A(D), 然后计算 T 和 D 的特征向量和特征值 在 λ 中的特征值 r 是有序递减的 因此, 初始矩阵 A 可以通过截取前 k 个特征值来近似构造 截 取的 SVD 构造了一个近似矩阵 A 的 k 秩矩阵 Ak=UkλkVT A k 是最近似原始矩阵的 K 秩矩阵 最近似表达 的是最小化 A 与 A k 元素之间的平方差之和 被截取的 SVD 代表降维成 k 维空间后的潜在结构, 这一般 意味着特征向量中的噪音被降低 使用 SVD 作为工具来提高协同过滤已经有一段时间了 Sarwar et al. [66] 在论文中描述了使 用 SVD 的两种不同方法 首先,SVD 可以用来发现用户与产品之间的潜在关系 为了完成这个目的, 他们首先用物品平均评分值去填充用户 - 物品矩阵的 0 值项, 然后通过减去用户对所有物品平均评分 来正规化这些矩阵 这些矩阵用 SVD 来分解, 其分解结果在一些细微的操作之后可以直接用来计算 预测值 其它方法是使用从 SVD 中提取出的低维空间中的结果来提高在 knn 方法的邻居信息 正如 Sarwar et al.[65] 描述的那样,SVD 的一大优势是有增量算法来计算近似的分解 这使得 我们在接收到新用户或者是评分的时候, 没有必要重新计算用先前存在的数据构建的模型 同样的 想法后来被 Brand[14] 的在线 SVD 模型扩充和正式采纳 在成功应用到 Netflix Prize 2 之后, 增量 SVD 方法的使用最近已经成为常用的方法 Simon Funk 的简单增量 SVD 方法的发表被标志为竞赛中的 转折点 [35] 自从它的发表之后, 在该领域已经发表了几篇改进的 SVD( 详细信息可以参考 Paterek 的全部 SVD 的算法 [56], 或者是 Kurucz et al. 的 SVD 参数评估 [47]) 最后, 应该注意到是矩阵分解 (MF) 的不同变化方法, 诸如非负的矩阵分解 (NNMF) 已经被使 用 本质上来说, 这些算法类似于 SVD. 最基本的想法是把评分矩阵分解成两个部分, 一个部分包含 描述用户的特征, 另一个部分包含描述物品的特征 矩阵分解通过引入偏项到模型中来处理缺失数 据比 SVD 方法要好 但是,SVD 方法中也可以在预处理阶段通过用物品的平均值来取代零值来处理 需要注意的是 SVD 和 MF 都可能产生过拟合的问题 但是已存在改进的 MF, 诸如 : 正规化内核矩阵分 解, 能有效地避免这个问题 MF 和 SVD 方法的主要问题是, 由于计算的复杂性每次数据升级更新时 7

8 重新计算分解是不现实的 但是,Rendle and Schmidt-Thieme [62] 提出一种在线的方法允许不用 重新计算所有整个模型来更新分解近似值 第五章会详细介绍在 Netflix Prize 的环境中 SVD 和 MF 的使用, 是对本章简介的详细补充 去噪 数据挖掘中采集的数据可能会有各种噪音, 诸如 : 缺失数据, 或者是异常数据 去噪是非常重 要的预处理步骤, 其目的是在最大化信息量时去除掉不必要的影响 在一般意义上我们把噪音定义为在数据收集阶段收集到的一些可能影响数据分析和解释结果的 伪造数据 在推荐系统的环境中, 我们区分自然的和恶意的噪音 [55] 前者提到的噪音是用户在选 择偏好反馈时无意产生的 后者是为了偏离结果在系统中故意引入的 很显然恶意的噪音能够影响推荐的输出 但是, 我们的研究推断正常的噪音对推荐系统性能的 影响是不可忽略的 [4] 为了解决这个问题, 我们设计了一个去噪方法, 能够通过要求用户重新评 价一些物品来提高精确度 [5] 我们推断通过预处理步骤来提高精确度能够比复杂的算法优化效果 要好的多 2.3 分类 分类器是从特征空间到标签空间的映射, 其中特征代表需要分类的元素的属性, 标签代表类别 例如, 餐厅推荐系统能够通过分类器来实现, 其分类器基于许多特征描述把餐厅分成两类中的一类 ( 好的, 不好的 ) 有许多种类型的分类器, 但是一般情况下我们谈的有监督分类器和无监督分类器 在有监督分 类器中, 我们预先知道一组标签或是类别, 并且我们有一组带有标签的数据, 用来组成训练集 在 无监督分类中, 类别都是提前未知的, 其任务是恰当的组织好我们手中的元素 ( 按照一些规则 ) 在本节中我们描述几个算法来学习有监督分类, 无监督分类 ( 例如聚类 ) 将在 2.4 节中进行描述 最近邻 基于样本的分类 (Instance-based classifiers) 通过存储训练记录并使用它们来预测未知样本 的标签类别 一个常见的例子是所谓的死记硬背学习 (rote-learner) 这种分类器记住了所有的训 练集, 并且只有在新纪录的属性与训练集中样本完全匹配时才会分类 一个更加精确和通用的基于 样本的分类是近邻分类 (knn) 给出一个要分类的点,kNN 分类器能够从训练记录中发现 K 个最近 的点 然后按照它最近邻的类标签来确定所属类标签 算法的基本思想是, 如果一个样本落入到由 一个类标签主导的领域, 是因为这个样本可能属于这个类 假设我们需要确定样本 q 的类别 l, 定义训练集是 x={{x1, l1}...{xn}}, 其中 xj 是第 j 个元素, lj 是它的类标签,k 的最近邻可以找到子集 Y = {{y1, l1}...{yk}}, 使得 Y X 且 Σk1 d(q,yk) 是 最下限 Y 包含 X 中的 k 个离 q 最近的样本点 那么,q 的类标签是 l = f ({l1...lk}) 8

9 图 2.4k 近邻的例子 左边的子图显示带有两个类标签的训练点 ( 圆形和正方形 ) 和查询点 ( 三角形 ) 右边的子图阐述 k=1 和 k=7 时的最近邻 查询点按照简单多数规则, 当 k=1 时被分类为正方形, 当 k=5 时被分类为圆形 注意查询点正好在两个类别之间的边界线上 也许在 knn 中最具有挑战的问题是如何的选择 k 的值 如果 k 太小的话, 分类可能对噪音点太敏感 但是如果 K 太大的话, 近邻范围可能会包含其它类中太多的点 图 2.4 右图展示了不同的 k 值下最终确定不同的类标签 k=1 时类标签可能是圆形的, 而 k=7 时类标签是正方形 注意到例子中的查询点正好处于两个类别中的边界上, 因此, 分类很困难 knn 分类器在所有的机器学习的算法中是最简单的 因为 knn 不要建立一个显示的模型, 因此被认为是一个懒的学习者 不像饥饿学习者, 比如决策树或是基于规则的系统 ( 分别参见 和 2.3.3),KNN 分类器把许多的决策留给了分类的步骤 因此, 分类未知记录的花费相当大 近邻算法是 CF 最常用的一种方法, 因而被用来设计推荐系统 事实上, 任何的推荐系统综述, 诸如 Adomavicius and Tuzhilin 的那篇 [1], 都会包含本文所提到的近邻使用的简介 这种分类的优点之一是它的概念和 CF 很相关 : 发现志趣相投的用户 ( 或者是类似的物品 ) 实质上等价于发现给定用户或者是物品的邻居 其它的优势是 : 作为 knn 分类器这样一个懒惰学习者, 它不需要学习和维持一个给定的模型 因此, 在原则上, 系统能够适应用户评分矩阵的急速变化 不幸的是, 这是以重新计算邻居和相似矩阵为代价的 这也是为什么我们要提出一种用精简后的专家集合来挑选邻居的邻居模型的原因 尽管 knn 方法简单和直观, 但是它结果精确, 非常易于提升 事实上, 它对于协同推荐的实际标准的主导地位最近才被基于降维的方法所挑战, 比如 :2.2.3 章节所叙述的 也就说 : 针对协同过滤方法的传统的 knn 方法已经在几个方向上得到了提升 例如 : 在 Netflix Prize 的实验环境中, Bell and Koren 建议一种方法来移除全局的影响, 比如一些物品可能会吸引用户一致给低分 他们提出邻居建立时立即计算插入权值的优化算法 详见第五章和第四章基于邻居使用改进 CF 技术的更多细节 9

10 2.3.2 决策树决策树 [61, 63] 是以树结构形式对目标属性 ( 或是类 ) 进行分类的分类器 要分类的观察数据 ( 或物品 ) 是由属性及其目标值组成 树的节点可以是 :a) 决策节点, 在这些节点中一个简单属性值被测试来决定应用哪一个子树, 或者是 b) 叶子节点指示目标属性的值 对于决策树归纳有许多的算法 : 最常提到是搜索算法, 包括 :CART,ID3, C4.5, SLIQ, SPRINT 递归搜索算法, 这是最早的也是最容易理解的算法, 依赖作用于给定属性的测试条件, 通过它们的目标值来区别这些观察值 算法一旦找到测试条件推导出的划分区域, 就会反复迭代, 直到划分区域为空, 或者观察数据都有相同的目标值 拆分可以通过最大的信息增益来决定, 定义如下 : i I k i N( v ) I( v j j ( parent ) (2.6) j1 N ) 其中,ki 是属性 i 的值,N 是观察数据的数量,Vj 是根据属性 i 的值得到的观察值的第 j 个划分 最后,I 是衡量不纯节点的函数 有各种不同的不纯衡量方法 :Gini 指标, 熵, 非分类错误是在文献中最常用的 一旦所有的观察值属于同一个类 ( 或者是在连续属性中的相同范围 ), 决策树的推导就结束了 这表明着叶子节点的非纯度是零 然而, 因为实际的原因, 大部分的决策树通过剪枝技术实现, 如果结点的非纯度或者观察值的数量低于某个阈值, 结点不再进行分裂 使用决策树建立一个分类器的主要优点是, 构建代价比较小并且在分类未知的对象方面速度比较快 与其它基础的分类技术相比, 决策树另一个好的方面是在维持精度的同时, 它产生的一系列规则容易被解释 ( 见 2.3.3) 推荐系统中决策树可以被用在基于模型的方法里 一种可能是用内容特征建立决策树模型, 对描述用户偏好的所有变量建模 Bouza et al. [12] 利用这种想法, 使用物品可用的语义信息构建一个决策树 用户只评价两个物品之后就能构造决策树 每个物品的特征被用来建立一个解释用户评分的模型 他们使用每一个特征的信息增益作为分裂准则 需要注意的是, 尽管这种方法从理论视角看很有趣, 但是在他们系统上报告的精确性比推荐平均评分的方法要差 正如可以预料到的那样, 建立一个试图解释决策过程中所有参数的决策树是非常困难以及不现实的 但是, 决策树可以被用来模拟系统的一个特殊部分 例如 :Cho et al. 提出一个结合关联规则 ( 见 2.5 节 ) 和决策树的在线购物推荐系统 决策树被用来作为一个过滤器来选择哪些用户可以作为推荐的目标 为了建立这个模型, 他们创建了一个候选用户集, 用户集是在给定的时间帧内从一个给定的目录下选了商品的这些用户 在他们的案例中, 选择作为构造决策树的因变量是用户是否会在相同的分类下再买新的产品 Nikovski and Kulev [54] 随后提出一个与之类似的结合决策 10

11 树和关联规则的方法 在他们的方法中, 先是在购买的数据集中发现频繁物品集, 然后应用标准的 树学习算法来简化推荐规则 在推荐系统中另一个使用决策树的选择是使用它们作为物品排序的工具 使用决策树来排序已 经在一些环境下被研究, 而且很明确都是为了这个目的 基于规则的分类 基于规则分类器是通过一组 if... then... 的规则集合划分数据 规则的前提或是 条件是属性连词的表达式 规则的结论是一个正或者负的分类 如果对象的属性满足规则的条件, 我们可以说规则 R 覆盖对象 x 我们定义规则的覆盖性为满 足前提的部分记录 另一方面, 我们定义准确性为既满足前提又满足结论的部分记录 如果规则彼 此之间是独立的, 我们说分类器包含互斥的规则, 例如 : 每一个记录最多被一个规则覆盖 最后, 如果属性值得所有可能组合都被覆盖的话, 例如 : 一个记录至少被一个规则覆盖, 我们认为分类器 具有详尽规则 (exhausitive rules) 为了建立一个基于规则的分类器, 我们可以用从数据中直接抽取规则的直接方法 这种方法的 例子是 RIPPER, 或 CN2 另一方面, 使用间接的方法从其它分类模型中抽取规则很常见, 例如 : 决 策树模型或是神经模型 基于规则分类器的优点是它们表示很明确, 因为它们是符号化的并且可以在没有任何转化的情 况下操作数据的属性 基于规则的分类器, 由决策树扩充, 容易解释, 容易生成, 并且它们能有 效地分类新的对象 但是, 与决策树方法类似, 建立一个完整基于规则的推荐模型是很难的 事实上, 这种方法在 推荐的环境中不是很流行, 因为得到一个基于规则的系统意味着我们要么具有一些决策过程中的显 式的先验知识, 要么我们从另一个模型中提取规则, 例如决策树 但是基于规则的系统通过注入一 些领域知识或者是商业规则来提高推荐系统的性能 例如 :Anderson et al. [6], 实现了一个协 同音乐推荐系统, 这个系统通过应用一个基于规则的系统在协同过滤的结果中提高性能 例如, 如 果用户给某个音乐家的专辑评分很高, 那么这个音乐家的其它专辑的预测评分也会提高 Gutta et al. [29] 实现了一个关于电视内容的基于规则的推荐系统 为此, 他们首先使用 C4.5 决策树, 然后分解成规则来分类电视节目 Basu et al. [9] 利用归纳的方法使用 Ripper [20] 系统从数据中学习规则 在他们的报告中, 使用混合内容和协同数据来学习规则的结果明显好于单 纯的 CF 方法 贝叶斯分类器 贝叶斯分类器是解决分类问题的一个概率框架 它基于条件概率定义和贝叶斯理论 贝叶斯统 计学派使用概率来代表从数据中学习到的关系的不确定性 此外, 先验的概念非常重要, 因为它们 代表了我们的期望值, 或者真正关系可能是什么的先验知识 特别的是, 给定数据后, 模型的概率 ( 后验概率 ) 是和似然值乘以先验概率的乘积成比例的 似然值部分包含了数据的影响, 而先验概 11

12 率则表明观测数据之前模型的可信度 贝叶斯分类器把每一个属性和类标签当作随机变量 ( 连续或者离散 ) 给定一个带有 N 个属性 的记录 ( A 1, A 2,, A N ), 目标是预测类 Ck, 方法是在给定数据 P(C k A1, A2,, A N) 下, 找到 能够最大化该类后验概率的 Ck 的值 应用贝叶斯理论 P( Ck A1, A2,, AN) 1 2 P( A, A,, A C ) PC ( ) 一个特殊但是最常用的分类器是朴素贝叶斯分类器 为了估计条件概率, 1 2 N P( A, A,, A C ). 假设属性的概率独立, 比如 : 一个特殊属性的存在与否和其它任何的属性 N k 的存在与否没有关系 这种假设导致 1 2 k k P( A, A,, AN C k) = P( A1 Ck ) P( A2 Ck ) P( AN C k ) 朴素贝叶斯的主要好处是, 受孤立噪音点和不相关的属性的影响小, 并且在概率估算期间可以 通过忽略实例来处理缺失值 但是, 独立性假设对一些相互关联的属性来说可能不成立 在这种情 况下, 通常的方法是使用所谓的贝叶斯信念网络 ( 或是简称贝叶斯网络 ) BBN 使用非循环图表示 属性之间的依赖性, 并使用概率表表示结点与直接父亲之间的联系 和朴素贝叶斯分类器方法类似, BBN 可以很好地处理不完整的数据, 对于模型的过拟合有相当的健壮性 贝叶斯分类器在基于模型的推荐系统中特别受欢迎 它们经常被用来为基于内容的推荐生成模 型 当然, 它们也被用于协同环境中 例如,Ghani and Fano [36], 使用朴素贝叶斯实现了一个基 于内容的推荐系统 使用这个模型允许在百货商店环境中从不相关的目录中推荐产品 Miyahara and Pazzani [52] 实现了一个基于朴素贝叶斯分类器的推荐系统 为了达到这个目 的定义了两个类 : 喜欢和不喜欢 在这种的环境中他们提出两个方法来使用朴素贝叶斯分类器 : 数 据转化模型假设所有的特征都是完全的独立的, 特征选择作为一个预处理步骤来实施 另一方面, 稀疏数据模型假设只有已知的特征是对分类有益的信息 此外, 当估算概率的时候, 只使用用户都 共同评价的数据 实验显示两种模型性能好于基于相关性的 CF Pronk et al. [58] 用贝叶斯朴素聚类器作为基础来合并用户组件并且提高性能, 特别是冷启 动环境 为了做到这一点, 他们提出给每个用户维持两个属性文件, 一个从历史评分中学习得到, 另一个由用户显式地创建 两种分类器的混合可以通过这样的方式来控制, 在早期阶段没有太多历 史评分时采用用户定义属性文件, 然后在随后的阶段再用学习型分类器取而代之 在前一章节中我们提到 Gutta et al. [29] 在电视内容上实现了一个基于规则方法的推荐系统 此外他们还实验了贝叶斯分类器 首先定义一个两类分类器, 类别包括 : 看过和没看过 用户配置 文件是属性的集合, 以及他们作为正样本和负样本出现的次数 这会被用来计算节目属于某个特定 分类的先验概率, 以及当节目是正向或负向时, 某个给定特征会出现的条件概率 在这样案例中, 必须注意到的是特征涉及到内容 ( 类型 ) 和环境 ( 时间 ) 新节目的后验概率是从这些 ( 环境和内 容 ) 中计算得来 Breese et al. [15] 实现了将每个节点关联到每个物品的贝叶斯网络 状态与每个可能的投票 12

13 值相关 在网络中, 每一个物品将有一组父亲节点作为它最好的预测器 条件概率表被决策树取代 作者报告显示在几组数据集上这种模型的结果比几种近邻算法的结果要好 分层的贝叶斯网络也在一些环境下被使用, 它用来作为信息过滤添加领域知识的方法 但是分 层的贝叶斯网络的问题之一是, 当其中的用户过多时, 学习和升级模型的代价非常大 Zhang and Koren [79] 提出一个标准期望最大化模型的变种, 能够在基于内容推荐系统中的环境中加速这种过 程 人工神经网络 人工神经网络 (ANN) 由一组内连接点和带权链接组成, 其想法来自于生物大脑的结构 ANN 中 的节点被称为神经元, 类似于生物神经 这些简单的功能单元组成网络, 网络在用有效数据训练之 后能够学习分类问题 图 2.5: 感知器模型 ANN 的最简单模型是感知器模型, 如图 2.5 所示 如果我们把激活函数 特指为简单的阈值函 数, 则输出就是根据每条链接的权重将输入值累加, 然后和某个阈值 相比较 输出函数可以由 公式 2.7 来表达 感知模型是具有简单和有效学习算法的线性聚类器 但是, 除了使用在感知模型中的阈值函数之外, 还有几种其它对于激活函数通用的选择, 比如 : 多层感知机, 正切双曲, 或者 是阶梯函数 y k 1, if 0, if x i x i w w ki ki k k (2.7) ANN 可以有许多的层 在 ANN 中的层被分成三种类型 : 输入, 隐藏, 输出 输入层的单元响应进入网络的数据 隐藏层接受从输入单元中的带权输出 输出层响应隐藏层中的带权输出并且产生最终的网络输出 使用神经元作为原子功能单元, 在网络中有许多种可能的架构来把它们结合在一起 k 13

14 但是, 最常用的方法是使用前馈 ANN 在这个例子中, 信号严格在一个方向传播 : 从输入到输出 ANN 最主要的优点是 ( 取决于激活函数 ) 能做非线性的分类任务, 并且由于并行属性, 它们高 效甚至能够在部分网络受损的情况下操作 主要的缺点是, 它很难对于给定的问题给出理想的网络 拓扑, 并且一旦拓扑被决定它的表现水平就会位于分类错误率的下限 ANN 属于一种次符号分类器, 也就是说, 在推理知识的时候不提供任何语义知识, 说白了这是一种黑盒方法 ANN 能够以类似于贝叶斯网络的方法被用来构建基于模型的推荐系统 但是, 没有令人信服的 研究表明 ANN 是否会有性能的提升 事实上,Pazzani and Billsus [57] 做了一个综合的实验, 使 用几种机器学习算法进行网页推荐 他们的主要目标是比较朴素贝叶斯分类器与计算开销更大的候 选方法, 诸如决策树和神经网络 他们的实验结果显示决策树的效果明显不好 他们推断似乎没有 必要用非线性分类器, 诸如 :ANN Berka et al. [31] 使用 ANN 为网页导航建立 URL 推荐系统 他们 实现了专门基于访问路径而与内容无关的系统, 比如 : 把域名和访问它们的人数关联起来 为此, 他们使用了用后向传播算法训练的前馈多层感知器 ANN 可以被用来结合 ( 或是混合 ) 几个推荐模块或者数据源中的输入 例如 :Hsu etal. [30] 建立一个电视推荐模型, 通过四个不同的源导入数据 : 用户的配置文件和自身看法 ; 观看社区 ; 节 目元数据 ; 观看环境 他们用后向传播算法来训练三层神经网络 Christakou 和 Stafylopatis [19] 也建立了一个混合的基于内容的协同过滤推荐系统 基于内容的推荐系统在实现时对每个用户采用 了三种神经网络, 其中每一个对应如下的一个特征 : 种类, 星级, 摘要 他们使用弹性反向传播方 法来训练 ANN 支持向量机 支持向量机分类的目标是发现数据的线性超平面 ( 决策边界 ), 以边界最大化的方式分离数据 例如, 如果我们在二维平面上看两类分离的问题, 像图 2.6 阐述的那样, 很容易观察到分成两个类 有许多种可能的边界线 每一个边界线都有一个相关的边缘 SVM 后面的理论支持是, 如果我们选 择边缘最大化的那一个, 我们将来对未知的物品分类出错的可能性就越小 14

15 图 2.6 在二维上不同的边界决定可能分成不同的类 每一个边界有一个相关的边缘 两个类中的线性分离是通过函数 w x b 0 来实现的 我们定义能够划分物品类 +1 或是 -1 的函数, 只要这些物品是被来自类划分函数的某个最小距离分开的 2.8 给出了相应的公式 1, ifw x b 1 f ( x) 1, fw x b 1 M arg in 2 w 2 (2.9) (2.8) 根据 SVM 的主要原理, 我们想要最大化两个类之间的边缘, 由公式 2.9 给出 事实上这等价于在 给定 f(x)de 约束条件下, 最小化数学方法可以解决它 ( 例如 : 二次规划 ) 的倒数 这其实是带约束最优化的问题, 有许多 如果物品不是线性分离的, 我们可以通过引入一个松弛变量来把 SVM 转变为软边缘分类器 在这种情况下, 公式 2.10 的最小化受限于公式 2.11 新的 f(x) 定义. 另一方面, 如果决策边界是非线性的, 我们需要转换数据到高维的空间 这个转换的完成得益于名为内核技巧的数学变换 最基本的想法是通过内核函数取代在公式 2.8 中的点积 对于内核函数有许多不同的可行的选择, 比如 : 多项式或者是多层感知器 但是最常用的内核函数是径向基函数系列 (RBF) 2 N w L( w) C 2 (2.10) i1 15

16 1, ifw x b 1 f ( x) 1, fw x b 1 (2.11) 支持向量机最近已经在许多的环境中获得较好的性能和效率 在推荐系统里,SVM 最近也显示 出了显著效果 比如,Kang and Yoo [46] 报告了一个实验研究, 其目的在于为基于 SVM 的推荐系统 选择最好的预处理技术预测缺失值 他们特别使用了 SVD 和支持向量回归 (SVR) 支持向量机推荐 系统首先通过二进制化可用用户偏好数据的 80 个等级来建立 他们设置了几组实验, 并且报告了阈 值为 32 时的最好结果, 例如 32 和更小的值被分为喜欢, 较高值被分为不喜欢 用户的 ID 被用来做分 类的标签, 正负值被表达成偏好值 1 和 2. Xu and Araki [76] 用 SVM 建立一个电视节目推荐系统 他们用电子节目向导 (Electronic Program Guide,EPG) 的信息作为特征 但是为了减少特征, 他们移除了最低频次的单词 此外, 为了评价不同的方法, 他们用布尔值和词频率 - 逆文档频率 (TFIDF) 来衡量特征结构的权重 在前 者,0 和 1 被用来代表在内容中物品的缺失或是出现 在后者则变成词频率 - 逆文档频率数值 Xia et al.[75] 提出用不同的方法来使用 SVM 在 CF 环境中来做推荐 他们探索使用平滑 SVM(SSVM) 的使用 他们也介绍了一个基于 SSVM 的启发式方法, 来迭代估算在用户物品矩阵中的缺 失元素 他们通过为每一个用户创建一个分类器来计算预测值 实验结果显示, 与 SSVM 以及传统的 基于用户和基于物品的 CF 相比,SSVMBH 实验结果最好 最后,Oku et al. [27] 为情景感知推荐系 统提出情景感知 SVM(C-SVM) 的使用方法 他们比较了标准 SVM C-SVM 和一种既使用 CF 又使用 C- SVM 的扩展算法 结果显示了在餐厅推荐中情景感知方法的有效性 分类器的集成 使用分类器集成背后的最基本的思想是, 从训练数据构造一系列的分类器, 并通过聚集预测值来 预测类标签 只要我们能假设这些分类器都是独立的, 分类器集成就有效 在这种情况下, 我们可 以确定分类器产生的最糟糕的结果与在集成中的最坏分类是一样的 因此, 结合具有相似的分类错 误的独立分类器将只会提升结果 为了产生集成, 有几种可能的方法 最常用的两个技术是 Bagging 和 Boosting 在 Bagging 方法中, 我们采用带替换的抽样, 在每一个自举样本 (bootstrap sample) 上建立分类 每一个样 本被选择的概率是 1 (1 ) N N, 考虑到如果 N 足够大, 那么其值会趋近于 在 e Boosting 方法中, 我们通过更加关注之前错误分类的记录, 使用迭代过程自适应地改变训练数据的分布 一开始, 所有的记录都被分配相同的权值 但是, 不像 Bagging 方法, 在每一轮的提升中权值是可以变化的 : 被错误分类的记录权值将会增加, 同时正确分配的记录的权值将会降低 Boosting 方法的例子是 AdaBoost 算法 分类器集成使用的例子在推荐领域里面非常的实用 事实上, 任何一个混合技术都可以理解成 以一种方式集成或另外几个分类器的集成 Tiemann and Pauws 的音乐推荐系统就是一个明显的实 例, 他们用集成学习方法来结合基于社交的和基于内容的推荐系统 16

17 实验结果显示, 集成器能产生比其它任何孤立的分类器更好的结果 例如,Bell et al. [11], 在他们解决 Netflix 挑战, 赢得大奖的方案中使用结合了 107 中不同的方法 他们的发现显示, 本质 上不同的方法比提升一种单一特殊技术的回报要好 为了从集合器中混合结果, 他们采用线性规划 方法 为了给每一个分类器生成权值, 他们把测试数据集分成 15 个不同的部分, 并且为每一个备份 生成唯一的系数 在 Netflix 环境中的不同的集成方法可以追溯到其它的方法, 诸如 :Schclar etal. s [67] 或 Toescher et al. s [71]. 自举方法也已经在推荐系统被使用, 例如,Freund et al. 提出一个被称为 RankBoost 的算法来 结合用户的偏好 他们应用这个算法在 CF 环境中来产生电影推荐 评估分类器 推荐系统中被接受最常用的指标是预测兴趣 ( 评分 ) 和测量值的均方差 (MAE) 或均方根误差 (RMSE) 这些指标在计算精度时对推荐系统的目标没有任何假设 但是, 正如 McNee et al. 指出 的那样, 除了精确度之外还有许多指标来决定物品是否要被推荐 Herlocker et al. 发表了推荐系 统算法指标方法的综述 他们建议某些指标对于某些推荐任务可能更加合适 但是, 如果在一类推 荐算法和单个数据集上要根据经验来评估不同方法时, 他们不能验证这些指标 下一步是考虑的是, 现实 中推荐系统的目的是产生一个 top-n 推荐列表, 以及依赖于能多 好地分辨出值得推荐的物品来评估这个推荐系统 如果把推荐看作分类问题, 就可以使用评估分类 器的著名指标, 诸如 : 准确度和召回率 在如下的段落中, 我们将概述一部分这些指标及其在推荐 评价中的应用 但是值得注意的是学习算法和分类能够被多个准测来评估 这包含执行分类的准确 率, 训练数据的计算复杂度, 分类的复杂度, 噪音数据的敏感度, 可扩展性等等 但是在本章中我 们将只关注分类性能 为了评估一个模型, 我们一般考虑以下的指标 : 真正 (TP): 分到类 A 且真的属于类 A 的实例数 量 ; 真负 (TN): 没有分到类 A 且真的不属于类 A 的实例数量 ; 假正 (FP): 分到类 A 但不属于类 A 的 实例数量 ; 假负 (FN): 没有分到类 A 但属于类 A 的实例数量 最常用来衡量模型性能是定义正确分类的 ( 属于或不属于给定的类 ) 实例和总的实例数量之间 的比率 : 精确度 =(TP +TN)/(TP +TN +FP +FN) 但是, 精确度在许多的例子中有误导 想象一个带 有 个类 A 的样本和 100 个类 B 的样本的两类分类问题 如果分类器简单地预测一切属于类 A, 计 算精度可能是 99.9%, 但是模型性能值得怀疑, 因为它从没有发现类 B 中的样本 改进这种估值的一 种方法是定义代价矩阵, 定义将类 B 的样本分给类 A 的代价 在真实的应用环境中, 不同类型的错误 可能的确有不同的代价 例如, 如果 100 个样本对应一个组装线上有缺陷的飞机部分, 不正确地拒 绝一个没有缺陷的部分 (99900 分之一的样本 ) 相比于错误地把缺陷的部分当作好的这个代价是微 不足道的 模型性能的其它常用指标, 特别是在信息检索中, 是准确率和召回率 准确率, 定义为 P = TP/(TP+FP), 是一种在分样本到类 A 中犯多少错误的指标 另一方面, 召回率,R = TP/(TP+FN), 17

18 衡量没有留下本应该划分到类中的样本的程度 注意在大部分的例子中, 当我们单独使用这两种指标时是有误导的 通过不分给任何的样本到类 A 可以建立有完美预测准确性的分类器 ( 因此 TP 为零但 FF 也为零 ) 相反的, 通过分配所有的样本到类 A 中可以建立完美召回率的分类器 事实上, 有一种结合了预测和召回率到一个单一指标中被称之为 F1 的指标 : 2RP 2TP F 1 R P 2TP FN FP 有时我们会比较几个相互竞争的模型, 而不是单独评估它们的性能 为此, 我们使用在 1950 年 代开发的用来分析噪音信号的技术 : 接受特征曲线 (ROC) ROC 曲线描述了正确击中和假警告之间 的特征 每一个分类的性能用曲线上的点表示 ( 见图 2.7) 图 2.7ROC 曲线的例子 模式 1 表现好于低假正比率, 同时模式 2 是整体相当的一致, 并且模式的假正比率优于模式 2 的 2.5 Ziegler et al. 表示通过 top-n 列表指标评估推荐算法不能直接映射出用户的效率函数 但是, 它的确解决了一些普遍接受的精确指标的限制, 诸如 :MAE 例如,Basu et al. [10], 通过分析在 评价规模中前四分之一被预测的物品哪些确实被用户评价为前四分之一 McLaughlin and Herlocker [50] 提出一种修改后的精确指标, 认为没有评价的物品计为不推荐 这个预测指标事实 上代表了真实精确性的下限 尽管能够从准确率和召回率上直接得出 F- 测量法, 但是在推荐系统评 估中很少有人用到 Huang et al. [43] 和 Bozzonet al. [13], 和 Miyahara 和 Pazzani [52] 是使 用这些指标的少数几个例子 ROC 曲线也已经在评估推荐系统时使用 当在受到攻击下比较不同算法的性能时,Zhang etal. [64] 使用 ROC 曲线下的面积作为评估的指标 Banerjee 和 Ramanathan [8] 也使用 ROC 曲线来比较不同 18

19 模型的性能 必须指出的是, 好的评估指标的选择, 即使是在 Top-N 推荐系统中, 仍是一个研究点 许多作 者提出了只用间接相关到这些传统的评估模式的指标 例如 :Deshpande 和 Karypis [25] 提出了命 中率和平均互命中等级的使用 另一方面,Breese et al. [15] 将排序列表中推荐结果的效用指标 定义成中立投票的函数 注意, 第八章会详细描述在推荐系统内容中这些评估指标的使用, 因此如果你对这个问题感兴 趣的话你可以从那一章节继续学习 2.4 聚类分析 扩展 CF 分类器的最大问题是计算距离时的操作量, 例如发现最好的 K 近邻 如我们在 节中 所看到那样, 一种可能的解决是降维 但是, 即使我们降低了特征维度, 仍有许多的对象要计算距 离, 这就是聚类算法的用武之地 基于内容的推荐系统也是这样, 检索相似对象也需要计算距离 由于操作量的减少, 聚类可以提高效率 但是, 不像降维方法, 它不太可能提高精确度 因此, 在 设计推荐系统时必须谨慎使用聚类, 必须小心地衡量提高效率和降低精度之间的平衡 聚类, 也被称作为无监督的学习, 分配物品到一个组中使得在同一组中的物品比不同组中的物 品更加类似 : 目的是发现存在数据中的自然 ( 或者说是有意义 ) 的组 相似度是由距离衡量来决定, 诸如在 中叙述的 聚类算法的目标是在最小化群内距离的同时最大化群间距离 聚类算法有两个主要的类别 : 分层和划分 划分聚类算法把数据划分成非重合的聚类, 使得每 一个数据项确切在一个聚类中 分层聚类算法在已知聚类上继续聚合物品, 生成聚类的嵌套集合, 组成一个层级树 许多聚类算法试图最小化一个函数来衡量聚类的质量 这样的质量函数一般被称为目标函数, 因此聚类可以看作最优化的问题 : 理想聚类算法考虑所有可能数据划分, 并且输出最小化质量函数 的划分 但相应的最优化问题是 NP 困难问题, 因此许多算法采用启发式方法 ( 例如 :k-means 算法 中局部最优化过程最可能结束于局部最小 ) 主要问题还是聚类问题太难了, 很多情况下要想找到 最优解就是不可能的 同样的原因, 特殊聚类算法的选择和它的参数 ( 比如相似度测量 ) 取决于许 多的因素, 包括数据的特征 在下面的章节我们描述 k-means 聚类算法和其它的候选算法 2.4.1k-means j k-means 聚类是一种分块方法 函数划分 N 个物品的数据集到 k 个不相关的子集 S, 其中包含 N 物品, 以便于它们按照给定的距离指标尽可能的靠近 在分块中每一个聚类通过它的 N 个成 员和它的中心点 来定义 每一个聚类的中心点是聚类中所有其它物品到它的距离之和最小的那 j 个点 因此, 我们定义 k-means 算法作为迭代来最小化 , 其中 n e j x 是向量代表第 n 个 物品, 在 S 中物品的中心点, 并且 d 是距离尺度 k-means 算法移动聚类间的物品直到 E 不再进一 步降低 j j 算法一开始会随机选择 k 个中心点 所有物品都会被分配到它们最靠近的中心节点的类中 由 j

20 于聚类新添加或是移出物品, 新聚类的中心节点需要更新, 聚类的成员关系也需要更新 这个操作 会持续下去, 直到再没有物品改变它们的聚类成员关系 算法的第一次迭代的时候, 大部分的聚类 的最终位置就会发生, 因此, 跳出迭代的条件一般改变成 直到相对少的点改变聚类 来提高效率 基础的 k-means 是极其简单和有效的算法 但是, 它有几个缺陷 :(1) 为了选择合适的 k 值, 假定有先验的数据知识 (2) 最终的聚类对于初始的中心点非常敏感 (3) 它会产生空聚类 k- means 也有几个关于数据的缺陷 : 当聚类是不同的大小, 密度, 非球状形状时, 就会有问题, 并且 当数据包含异常值时它也会有问题 Xue et al. [77] 提出一种在推荐环境中典型的聚类用法, 通过使用 k-means 算法来作为预处理 步骤来帮助构造邻居 他们没有将邻居限制在用户所属的聚类内, 相反是使用从用户到不同聚类中 心点的距离作为预选阶段发现邻居 他们实现了基于聚类平滑技术, 其技术是对于用户在聚类中的 缺失值被典型聚类取代 他们的方法据称比标准的基于 knn 的 CF 效果要好 类似的,Sarwar et al. [26] 描述了一个方法来实现了可扩展的 knn 分类器 他们通过平分 K-means 算法来划分用户空间, 然 后用这些聚类作为邻居的形成的基础 据称与标准的 knn 的 CF 相比准确率降低了大约 5% 但是, 他 们的方法显著地提高了效率 Connor and Herlocker [21] 提出不同的方法, 他们聚类物品而不是用户 使用 Pearson 相关相 似度指标, 他们尝试四种不同算法 : 平均链接分层聚集 [39], 对于分类属性的健壮聚类算法 (ROCK) [40],kMetis 和 hmetis 3 尽管聚类的确提高了效率, 但是所有的聚类技术的确比非分类基线精确 度和覆盖度要差 最后,Li et al.[60] 和 Ungar 和 Foster[72] 提出一种非常类似的方法, 使用 k- means 聚类来解决推荐问题的概率模型解释 改进的 k-means 基于密度的聚类算法, 诸如 :DBSCAN 通过建立密度定义作为在一定范围内的点的数量 例如 : DBSCAN 定义了三种点 : 核心点是在给定距离内拥有超过一定数量邻居的点 ; 边界点没有超过指定数 量的邻居但属于核心点邻居 ; 噪音点是既不是核心点也不是边界点 算法迭代移除掉噪音数据并且 在剩下的点上进行聚类 消息传递聚类算法是最近基于图聚类方法的系列之一 消息传递算法没有一开始就将节点的初 始子集作为中心点, 然后逐渐调适, 而是一开始就将所有节点都看作中心点, 一般称为标本 在 算法执行时, 这些点, 现在已经是网络中的节点了, 会交换消息直到聚类逐渐出现 相似传播是这 种系列算法的代表, 通过定义节点之间的两种信息来起作用 : 责任, 反映了在考虑到其它潜在 标本的情况下, 接收点有多适合作为发送点的标本 ; 可用性, 从候选标本发送到节点, 它反映 了在考虑到其它选择相同标本的节点支持的情况下, 这个节点选择候选标本作为其标本的合适程度 相似传播已经被应用到 DNA 序列聚类, 在图形中人脸聚类, 或者是文本摘要的等不同问题, 并且 效果很好 20

21 最后, 分层聚类按照层级树 ( 树枝形结构联系图 ) 的结构产生一系列嵌套聚类 分层聚类不会 预先假设聚类的既定数量 同样, 任何数量的聚类都能够通过选择合适等级的树来获得 分层聚类 有时也与有意义的分类学相关 传统的分层算法使用一个相似度或者是距离矩阵来合并或者是分裂 一个聚类 有两种主要方法来分层聚类 在聚集分层聚类中, 我们以点作为个体聚类, 并且每一个 步合并最近的聚类对, 直到只有一个 ( 或是 k 个聚类 ) 聚类剩下 分裂分层聚类从一个包含所有物 品的聚类开始,, 并且每一个分裂每一聚类, 直到每一聚类包含一个点 ( 或是有 K 个聚类 ) 就我们所知, 诸如前面提到 k-means 的替代方法没有应用在推荐系统中 k-means 算法的简单和 效率优于它的替代算法 基于密度或者是分层聚类方法在推荐系统领域能起多大作用还不是很清楚 另一方面, 消息传递算法已经显示了其高效的特点, 并且基于图的范例很容易转换成推荐问题 在 未来一段时间内我们看到这些算法的应用是可能的 2.5 关联规则挖掘 关联规则挖掘关注于规则的发现, 其它能够根据事务中出现其它物品来预测出现某个物品 两 个物品被发现相关只意味着共同出现, 但是没有因果关系 注意不要将这种技术与在 节中提 到的基于规则的分类混淆 我们定义物品集为一个或多个物品的集合 ( 例如 ( 牛奶, 啤酒, 尿布 )) k- 物品集是包含 k 个物品的集合 给定物品的频繁度被称之为支持量 ( 比如 :( 牛奶, 啤酒, 尿布 )=131) 并且物 品集的支持度是包含它的事务的比例 ( 例如 :( 牛奶, 啤酒, 尿布 )=0.12) 频繁物品集是支持度 大于或等于最小支持度阈值的物品集 关联规则是公式 X Y 公式的表达式, 其中 X 和 Y 是物品集 ( 例如 : 牛奶, 尿布 啤酒 ) 在这个案例中, 关联规则的支持度是同时拥有 X 和 Y 的事务的比例 另一方面, 规则的置信度是 Y 中的物品有多经常出现在包含 X 的事务中 给定一组事务集合 T, 关联规则挖掘的目标是发现具有支持度 最小支持度阈值以及置信度 最小置信度阈值的所有规则 暴力法将会列出所有可能的关联规则, 为每一个规则计算支持度和置 信度, 然后删除不满足两个条件的规则 但是, 这样的计算开销太大 因为这个原因, 我们采用两 步方法 :(1) 产生了所有支持度 最小支持度的物品集 ( 频繁项集生成 ) (2) 从每一频繁物品集中 产生高置信规则 ( 规则产生 ) 有几个技术来优化频繁物品集的产生 在一个广泛的意义上, 它们可以被分成这些 : 尝试最小 化候选集数量 (M), 降低事务量 (N), 降低比较量数量 (NM) 但是最常用的方法是使用先验规 则来降低候选数量 这个原则表明如果物品集是频繁的, 那么所有的子集也是频繁的 支持度的衡 量标准已经验证了这一点, 因为一个物品集的支持度永远不会超过它子集的支持度 Apriori 算法 是这个规则实际的实现 L 给定一个频繁集 L, 产生规则时的目的是发现所有满足最小的置信度需求的非空子集 如果 k, 那么有 2k2 条候选关联规则 因此, 在生成频繁物品集时, 需要找到高效的方法来生成规 21

22 则 对于 Apriori 算法, 我们能通过合并规则结果中共用相同前缀的两个规则来产生候选规则 关联规则在发现模式和推动个性化市场营销方面的显著效果闻名已久了 但是, 尽管这些方法 和推荐系统的目标之间有明显的关联, 但是它们还是没有成为主流 主要原因是这种方法类似于基 于物品的 CF 但缺少灵活性, 因为它需要事务这个明确的概念 -- 事件共同出现在某个给定的会话中 在下一章中我们将举一些有意义的例子, 其中一些表明关联规则仍有潜力 Mobasher et al. [53] 提出一种基于关联规则的个性化网页系统 他们的系统基于用户的导航 模式, 从共同出现的浏览页面来识别关联规则 他们在精确度和覆盖率指标方面优于基于 knn 的推 荐系统 Smyth et al. [68] 提出给推荐系统使用关联规则的两种不同的研究案例 在第一种的案 例中, 为了生成较好的物品 - 物品相似度指标, 他们从用户属性中使用先验算法来抽离物品关联规 则 在第二个案例中, 他们应用关联规则到会话推荐中 这里的目标是发现共同发生的评论, 比如 用户通过一个推荐物品的特定特征表明偏好 Lin et al. [49] 提出一种新的关联规则挖掘算法, 为了获得一个合适的有意义规则数量, 在挖掘期间调整规则的最小支持度, 因此解决了先前像 Apriori 这样算法的某些缺陷 他们挖掘在用户之间和物品之间的关联规则 测量出的精确度优于 基于相关度推荐的报告值, 并且接近于更精巧的方法, 诸如 :SVD 和 ANN 的结合 最后, 如在 节中提到的那样,Cho et al. [18] 在一个网页商店推荐系统中结合了决策树 和关联规则挖掘 在他们的系统, 关联规则的导入是为了链接相关的物品集 然后通过连结用户偏 好和关联规则来计算得出推荐结果 他们在不同的事务集中寻找关联规则, 诸如 : 商品, 购物车, 点击率 他们用启发式学习给每一个事务集中规则附加权重 例如 : 商品关联规则权重大于点击关 联规则 2.6 总结 本章介绍了在设计推荐系统中可能用到的主要的数据挖掘方法和技术 我们也总结了在文献中 提到的用法, 提供了如何以及在哪用到它们一些粗略指导 我们从综述在预处理步骤可能用到的技术开始 首先,2.2.1 节回顾了如何选择合适的距离衡 量指标 在后面的步骤中大部分的方法需要它 余弦相似度和皮尔逊相关度是一般可接受最好的选 择 尽管付出了许多的努力来提高这些距离指标, 但是最近的工作似乎表明距离函数的选择不是这 么的重要 然后, 在 节回顾了最基础的抽样, 其应用是为了选择原始大数据集的子集, 或者 是划分训练和测试集 最后, 我们讨论降维技术的使用, 诸如 : 在 节中主成份分析 (PCA) 和 奇异值分解 (SVD) 作为一种方法来解决维度灾难问题 我们解释了一些使用降维技术的成功案例, 特别是在 Netflix 大奖的环境中 在 2.3 节中, 我们回顾了主要的分类方法 : 即 : 近邻, 决策树, 基于规则分类, 贝叶斯网络, 人工神经网络, 支持向量机 我们看到, 尽管 knn( 见 2.3.1) 的 CF 是首选的方法, 但是所有这些方 法都可以应用在不同的环境中 决策树 ( 见 2.3.2) 可以被用来导出基于物品内容的模型或者是模 22

23 拟系统的特殊部分 决策规则 ( 见 2.3.3) 可以从预先存在的决策树中推导出, 或者是被用来引入商业或者是领域知识 贝叶斯网络 ( 见 2.3.4) 是基于内容的推荐中一个流行的方法, 但它也可以用来生成一个基于模型的协同过滤系统 类似的方法, 人工神经网络能够被用来导出基于模型的推荐, 也可以用来结合 / 混合其它几种算法 最后, 支持向量机 ( 见 2.3.6) 作为一种方法来推断出基于内容的分类或者是导出 CF 模型而流行 对于推荐系统来说, 选择合适的分类器不容易, 尤其是一些感知判断任务和数据依赖的情况下 在 CF 的案例中, 一些结果似乎表明基于模型方法, 使用诸如 SVM 或者是贝叶斯网络, 能够稍微提高标准 knn 分类的性能 但是, 这些结果不显著并且很难推广 在基于内容的推荐系统的例子中有些证据表明, 在一些例子中贝叶斯网络执行效果比简单方法要好, 诸如决策树 但是, 更加复杂的非线性分类, 诸如 :ANN 或者是 SVM, 执行效果是否更好还不是很清楚 因此, 给特定的推荐任务选择合适分类器在今天仍有许多探索的地方 实际的经验规则是从最简单的方法做起, 并且只有在性能的提升值得时才采用复杂方法 性能增益应该平衡不同的维度, 诸如 : 预测精确度或者是计算效率 我们在 2.4 章中回顾了聚类算法 聚类在推荐系统中一般被用来提高性能 不管是在用户空间还是物品空间, 较早进行聚类步骤都能减少随后要做的计算距离的操作数量 但是, 这一般以较低的精确度为代价, 所以处理时要慎重 事实上, 通过使用降维技术 ( 比如 :SVD) 提高效率在一般的例子中是好的选择 与分类相反, 没有那么多的聚类算法在推荐系统的环境中使用 k-means ( 见 2.4.1) 算法由于简单和相对有效, 很难找到实用的替代者 我们在 章节中综述了它们中一些算法, 诸如分层聚类或者是消息传递算法 尽管这些技术还没有应用在推荐系统中, 但为将来的研究提供了有希望的出路 最后, 在 2.5 章中, 我们描述了关联规则并总结了它们在推荐系统的使用 关联规则为推荐物品提供了直观的框架, 只要有一个显式或隐式的事务 尽管存在有效的算法来计算关联规则, 而且已经被证明比标准 knn 的 CF 准确率好, 但是他们仍不是受青睐的方法 在设计推荐系统中选择正确的数据挖掘技术是一个复杂的任务, 其一定受许多特殊问题约束 但是, 我们希望本章中技术和经验的简短综述能够帮助读者做出更加合理的决定 除此之外, 我们也发现了有待进一步提高的领域和令人兴奋的研究点, 以及接下来有待研究的相关研究点 致谢本章的完成受到来自 Generalitat de Catalunya 的 ICREA 部分基金支持 23