【基于模型的协同过滤2】决策树模型

今天我们集中主要讨论如何将决策树模型抽象到协同过滤问题，在讨论之前，首先回顾一下决策树模型在传统分类问题上的作用。

决策树算法回顾

决策树模型根据所解决问题的种类可分为分类问题和回归问题。为了简化讨论，我们先以分类问题进行具体说明。假设我们有一个m×n矩阵R的情况。第一（n-1）列是自变量，而最后一列是因变量。所有的自变量和因变量均为二进制变量。

决策树的工作过程通过运用一系列分层标准（split criteria）对数据进行分层分离。每一次我们选用一个特征来讲分支中的属于不同类的大多数分离出来。换句话说，两个分支之一将主要包含一个类，而另一个分支将主要包含另一个类。当以这种方式选择特征变量以使其与类变量相关联时，每个分支内的数据记录将趋于纯净。当决策树中的每个节点都有两个子代时，结果决策树被称为二进制决策树。

数据分离的质量可以通过叶子节点的加权平均基尼系数来衡量。假设 $p_{1}$ ， $p_{2}$ ，...， $p_{r}$ 是母节点中分别属于 $r$ 个不同类别的观测，这个节点的基尼系数定义如下：

$G(S) = 1-\sum_{i=1}^{r}{p_{i}}^2$

基尼系数一般在0到1之间，母节点的基尼系数等于所有子节点的基尼系数加权平均值。假设 $S_{1}$ ， $S_{2}$ 分别为母节点的两个子节点，分别含有 $n_{1}$ ， $n_{2}$ 个观测。那么从母节点分割到子节点的公式为
$Gini(S\Rightarrow [S_{1}, S_{2}]) = \frac{n_{1}*G(S_{1})+n_{2}*G(S_{2})}{n_{1}+n_{2}}$ 。我们可以根据基尼系数来选择合适的特征对树的某个节点进行分割。每一次从上往下（母节点到子节点）分割我们都会选择基尼系数最小的特征进行分割，直到每个节点仅包含属于特定类的观测。我们也可以提前结束树的叶子节点的生长，直到某个节点中至少某阈值观测属于某个特定类类别。这样的节点称为叶节点，并用该节点通过节点中的记主要类进行标记。

如果我们想通过决策树测试某一个位置观测的分类，我们可以通过自变量来映射决策树中从根到叶的路径。因为决策树的本质就是对数据空间的分层分区，所以测试实例将严格遵循从根到叶的一条路径。最终到达的叶子节点的的标签就被预测为测试实例的相关标签/分类。

以上就是对于二进制特征的分类，只需稍作修改，该方法就可以扩展到数值特征变量和独立变量。要处理数字独立（特征）变量，可以将属性值划分为间隔以执行拆分。数据分割的质量可以从基尼系数更改为更适合数值变量的方差来表达。方差的值越低，说明待分割节可以通过因变量更好的区别地映射的训练实例。我们一般会使用叶子节点的平均数值来进行预测。

将决策树延伸到协同过滤上

将决策树扩展到协同过滤问题的的主要挑战主要来自以下三个方面

问题一：需要被预测的条目和观察到的条目没有按行列方式清晰地分离为自变量和应变量变量。协同过滤中没有明确划分因变量和独立变量（项目），因此决策树应预测哪些项目是一个需要单独定义的问题。
问题二：评分矩阵非常稀疏，其中大多数条目都缺失。这在树构建阶段对训练数据进行分层划分时提出了挑战。

下面探探如何解决这个问题

问题一解决思路
考虑一个具有m个用户和n个项目的m×n个评级矩阵R。我么可以先固定每个属性（项目）作为独立变量，剩下的属性（项目）作为因变量单独构造决策树。因此，最终构造决策树的数量等于属性（项目）的数量n。在为相应用户预测特定项目的评分时，我们可以提取特定项目的决策树用于预测。
问题二解决思路
评分矩阵的稀疏，尤其是当确实因变量特征使得问题更为棘手。假设我们使用某一特定项目（例如特定电影）作为节点中用于分割的特征。那么这个决策树中评分小于某一阈值的所有用户都分配给树的一个分支，而评分大于这一阈值的用户则分配给另一分支。由于评分矩阵稀疏，因此大多数用户可能没有为此商品给出评分。那么这类，用户应分配到哪个分支呢？逻辑告诉我们指此类用户应该都给两个分支。但是，在这种情况下，决策树不再保留对于训练集的严格分区。此外，根据这种方法，测试实例将映射到决策树中的多个路径，并且各个路径的可能带来冲突的预测，我们最后需要将这些冲突的预测进行汇总为单个预测。

另一种对于问题二的解决思路是给数据降维。考虑一下这种情况，假设我们需要预测第j个项目的评分。从一开始，我们可以将第j从评分矩阵中剔除，得到一个 $m×(n−1)$ 个评分矩阵矩阵。接下来我们可将这个评分菊展转换为较低维的矩阵用 $m×d$ 表示形式，其中 $d\ll n− 1$ , 其它所有所有属性均已完全指定。我们可以估计 $m×(n-1)$ 个评分矩阵中每对项目之间的协方差。前d个特征向量 $\overline{e}_{1}$ , ... , $\overline{e}_{d}$
可以通过估计的 $（n-1）×（n-1）$ 协方差矩阵来决定。每个特征向量都是包含 $(n-1)$ 个元素。我们可以将每个用户的评分投射到特征向量上。这样每个用户可以得到一个 $d$ 维度的评分，这个评分稠密的。通过姜维，我们可以为项目j 创建一个标准的决策树。我们可以重复这个过程将j的值从1迭代到n重复此方法，以便构造总共n个决策树。因此，第j个决策树仅对预测第j个项目的评分有用。 n个项目中每个项目的特征向量和树都存储为模型的一部分。

为了预测用户i的项目j的评分，我们将 $m×d$ 矩阵的第i行用作测试实例并且我们使用第j个决策树模型以预测组中的评分。我们的第一步将除第j个项目使用剩余的n − 1个项降维到d维进行简化表示。其中我们会使用第j个特征向量集用于投影和降维过程。然后这个降维的d维特征将直接应用第j各项目相应决策树或回归树一起使用以执行预测。

实际上，这种将降维与分类模型结合起来的方法并不局限于决策树。它适用于几乎所有分类模型。

喜欢请点赞，转载请注明出处！

参考文献
[1] Aggarwal, Charu C.Recommender systems. Vol. 1. Cham: Springer International Publishing, 2016.