CN104933143A - 获取推荐对象的方法及装置 - Google Patents

Abstract

本发明提供一种获取推荐对象的方法及装置，具有搜索速度快，适用范围广等优点。该方法包括：构建原始用户矩阵和原始对象矩阵，其中，原始用户矩阵中的每一行为原始用户向量，每个原始用户向量表示一个用户的多重属性特征，原始对象矩阵中的每一行为原始对象向量，每个原始对象向量表示一个对象的多重属性特征；对原始用户矩阵和原始对象矩阵进行保序变换，得到新用户矩阵和新对象矩阵；对新对象矩阵中的新对象向量构建对象高维索引结构；对新用户矩阵中的各个新用户向量在对象高维索引结构中进行最近邻搜索，得到新用户向量对应的最近邻新对象向量；根据各个新用户向量及其对应的最近邻新对象向量，输出用户与推荐对象的映射。

Description

获取推荐对象的方法及装置

技术领域

本发明涉及计算机技术领域，尤其涉及一种获取推荐对象的方法及装置。

背景技术

随着互联网技术的发展，人们进入了信息过载的时代。在用户访问网站的过程中，大量的新闻、商品、视频、音乐等等对象呈现在了用户面前。怎样筛选出用户真正感兴趣的内容对提高网站的访问量及收益有着非常重要的意义。推荐系统相关的技术在这样的背景下得到了越来越广泛的使用。

近几年来矩阵分解算法成为了推荐系统领域研究的主流，研究表明在个性化推荐中使用矩阵分解技术可以得到比传统基于邻域的协同过滤更好的结果。矩阵分解算法将用户对对象的评分矩阵进行分解，生成用户矩阵U和对象矩阵V，这样就将用户和对象映射到了高维的潜语义空间。用户矩阵及对象矩阵的每一行都是一个向量，表示相应的用户和对象。用户向量与一个对象向量的内积就是该用户对对象的评分，内积越大，评分越高，表示越是推荐。每个用户的推荐对象可以取所有对象中K个内积最大的对象向量对应的对象作为推荐结果。

在实际应用场景中，用户和对象的数量往往庞大，相当于多达千万的用户都需要在千万级对象构成的高维空间中搜索K个最大的内积，该计算过程非常耗时。因此需要一种方案能够快速地完成用户和对象向量间最大内积的Top K计算。

若采用最基本的线性搜索方法进行最近邻搜索，则时间复杂度较高，无法满足海量数据下的需求。常用的解决方案是建立高维索引，利用高效的数据结构和算法完成搜索。但是，由于内积不满足三角不等性且无法衡量向量间的相似性，导致常用的聚类、高维索引树、局部感知哈希等建立高维索引的方案均无法直接适用于内积空间的搜索。

发明内容

有鉴于此，本发明提供一种获取推荐对象的方法及装置，具有搜索速度快，适用范围广等优点。

为实现上述目的，根据本发明的一个方面，提供了一种获取推荐对象的方法，包括：构建原始用户矩阵和原始对象矩阵，其中，所述原始用户矩阵中的每一行为原始用户向量，每个所述原始用户向量表示一个用户的多重属性特征，所述原始对象矩阵中的每一行为原始对象向量，每个所述原始对象向量表示一个对象的多重属性特征；对原始用户矩阵和原始对象矩阵进行保序变换，得到新用户矩阵和新对象矩阵；对所述新对象矩阵中的新对象向量构建对象高维索引结构；对所述新用户矩阵中的各个新用户向量在所述对象高维索引结构中进行最近邻搜索，得到所述新用户向量对应的最近邻新对象向量；根据各个所述新用户向量及其对应的所述最近邻新对象向量，输出用户与推荐对象的映射。

可选地，所述对原始用户矩阵和原始对象矩阵进行保序变换，得到新用户矩阵和新对象矩阵的步骤包括：对所述原始用户矩阵的第i行向量x_i添加数值0作为一个新的维度，得到新用户向量从而得到所述新用户矩阵；计算所述原始对象矩阵的第j行向量y_j的2-范数以及该2-范数的最大值对所述y_j添加作为一个新的维度，得到新对象向量从而得到所述新对象矩阵。

可选地，所述对所述新对象矩阵中的新对象向量构建对象高维索引结构的步骤包括：将所述新对象矩阵中的新对象向量聚类得到多个对象子类，每个对象子类具有一个对象聚类中心；为每个所述对象子类建立vp-tree树结构。

可选地，所述对所述新用户矩阵中的各个新用户向量在所述对象高维索引结构中进行最近邻搜索，得到所述新用户向量对应的最近邻新对象向量的步骤包括：将所述对象高维索引结构序列化地保存为对象索引文件并发送给多个节点；在每个所述节点上，根据所述新对象矩阵和所述对象索引文件重建出所述对象高维索引结构；采用map-reduce技术，通过hadoop框架在所述多个节点中对所述新用户矩阵中的各个新用户向量进行最近邻搜索，得到所述新用户向量对应的最近邻新对象向量。

可选地，所述采用map-reduce技术，通过hadoop框架在所述多个节点中对所述新用户矩阵中的各个新用户向量进行最近邻搜索，得到所述新用户向量对应的所述最近邻新对象向量的步骤包括：将所述新用户矩阵均分成多个新用户向量组并分发到所述多个节点，所述hadoop为分发到各个节点的所述新用户向量组分别建立mapper；在各个所述mapper内为对应的所述新用户向量组中各个新用户向量执行以下操作：计算所述新用户向量与各个所述对象聚类中心的欧氏距离，找到欧氏距离最近的所述对象聚类中心，进入该欧氏距离最近的对象聚类中心对应的vp-tree，通过递归遍历树完成该vp-tree的最近邻搜索，得到所述新用户向量对应的最近邻新对象向量；在reducer中汇总并保存所述新用户向量与对应的所述最近邻新向量对象的映射关系。

为实现上述目的，根据本发明的另一方面，提供了一种获取推荐对象的装置，包括：矩阵构建模块，用于构建原始用户矩阵和原始对象矩阵，其中，所述原始用户矩阵中的每一行为原始用户向量，每个所述原始用户向量表示一个用户的多重属性特征，所述原始对象矩阵中的每一行为原始对象向量，每个所述原始对象向量表示一个对象的多重属性特征；保序变换模块，用于对原始用户矩阵和原始对象矩阵进行保序变换，得到新用户矩阵和新对象矩阵；索引构建模块，用于对所述新对象矩阵中的新对象向量构建对象高维索引结构；搜索模块，用于对所述新用户矩阵中的各个新用户向量在所述对象高维索引结构中进行最近邻搜索，得到所述新用户向量对应的最近邻新对象向量；输出模块，用于根据各个所述新用户向量及其对应的所述最近邻新对象向量，输出用户与推荐对象的映射。

可选地，所述矩阵构建模块还用于：对所述原始用户矩阵的第i行向量x_i添加数值0作为一个新的维度，得到所述新用户向量从而得到所述新用户矩阵；计算所述原始对象矩阵的第j行向量y_j的2-范数以及该2-范数的最大值对所述y_j添加作为一个新的维度，得到所述新对象向量从而得到所述新对象矩阵。

可选地，所述索引构建模块还用于：将所述新对象矩阵中的新对象向量聚类，得到多个对象子类，每个对象子类具有一个对象聚类中心；为每个所述对象子类建立vp-tree树结构。

可选地，所述搜索模块还用于：将所述对象高维索引结构序列化地保存为对象索引文件并发送给多个节点；在每个所述节点上，根据所述新对象矩阵和所述对象索引文件重建出所述对象高维索引结构；采用map-reduce技术，通过hadoop框架在所述多个节点中对所述新用户矩阵中的各个新用户向量进行最近邻搜索，得到所述新用户向量对应的所述最近邻新对象向量。

可选地，所述搜索模块还用于：将所述新用户矩阵均分成多个新用户向量组并分发到所述多个节点，所述hadoop为分发到各个节点的所述新用户向量组分别建立mapper；在各个所述mapper内为对应的所述新用户向量组中各个新用户向量执行以下操作：计算所述新用户向量与各个所述对象聚类中心的欧氏距离，找到欧氏距离最近的所述对象聚类中心，进入该欧氏距离最近的对象聚类中心对应的vp-tree，通过递归遍历树完成该vp-tree的最近邻搜索，得到所述新用户向量对应的最近邻新对象向量；在reducer中汇总并保存所述新用户向量与对应的所述最近邻新向量对象的映射关系。

根据本发明的技术方案，提出对原始用户矩阵和原始对象矩阵进行保序变换生成新数据。由于在新数据上进行欧氏空间的最近邻搜索与在原数据上做最大内积搜索有相同的结果，因此可以利用适用于欧式空间的对象高维索引结构等价地完成最大内积的搜索。因此，本发明的技术方案与传统的线性搜索技术相比具有更高计算效率，并且克服了现有技术中各种高维索引结构无法适用于最大内积搜索的问题，具有搜索速度快，适用范围广等优点。

附图说明

附图用于更好地理解本发明，不构成对本发明的不当限定。其中：

图1是根据本发明实施例的获取推荐对象的方法的主要步骤的示意图；

图2是根据本发明实施例的获取推荐对象的装置的主要部件的示意图。

具体实施方式

以下结合附图对本发明的示范性实施例做出说明，其中包括本发明实施例的各种细节以助于理解，应当将它们认为仅仅是示范性的。因此，本领域普通技术人员应当认识到，可以对这里描述的实施例做出各种改变和修改，而不会背离本发明的范围和精神。同样，为了清楚和简明，以下的描述中省略了对公知功能和结构的描述。

图1是根据本发明实施例的获取推荐对象的方法的主要步骤的示意图。如图1所示，该方法主要包括如下步骤S1至步骤S5。

步骤S1：构建原始用户矩阵和原始对象矩阵。其中，原始用户矩阵中的每一行为原始用户向量，每个原始用户向量表示一个用户的多重属性特征。原始对象矩阵中的每一行为原始对象向量，每个原始对象向量表示一个对象的多重属性特征。

步骤S2：对原始用户矩阵和原始对象矩阵进行保序变换，得到新用户矩阵和新对象矩阵。保序变换的目的是将最大内积搜索问题转换为欧式空间的最近邻问题。保序变换的具体方式可以有多种，本发明不做限定。

步骤S3：对新对象矩阵中的新对象向量构建对象高维索引结构。构建对象高维索引结构的具体方式可以有多种，本发明不做限定。

步骤S4：对新用户矩阵中的各个新用户向量在对象高维索引结构中进行最近邻搜索，得到新用户向量对应的最近邻新对象向量。

步骤S5：根据各个新用户向量及其对应的最近邻新对象向量，输出用户与推荐对象的映射。其中，每个新用户向量代表一个用户，最近邻新对象向量代表匹配度最高的、最为推荐的对象。因此，可以根据“新用户向量-最近邻新对象向量”对应关系，输出“用户-推荐对象”的映射。

由上可知，根据本发明实施例的获取推荐对象的方法，提出对原始用户矩阵和原始对象矩阵进行保序变换生成新数据。由于在新数据上进行欧氏空间的最近邻搜索与在原数据上做最大内积搜索有相同的结果，因此可以利用适用于欧式空间的对象高维索引结构等价地完成最大内积的搜索。因此，本发明的技术方案与传统的线性搜索技术相比具有更高计算效率，并且克服了现有技术中各种高维索引结构无法适用于最大内积搜索的问题，具有搜索速度快，适用范围广等优点。

在本发明的实施方式中，步骤S2的保序变换过程可以具体包括如下的步骤S21至步骤S22。

步骤S21：对原始用户矩阵的第i行向量x_i添加数值0作为一个新的维度，得到新用户向量从而得到新用户矩阵。其中，i为自然数且1≤i≤A，A表示原始用户矩阵的行数，也就是用户的数目。

步骤S22：计算原始对象矩阵的第j行向量y_j的2-范数以及该2-范数的最大值对y_j添加作为一个新的维度，得到新对象向量从而得到新对象矩阵。其中，j为自然数且1≤j≤B，B表示原始对象矩阵的行数，也就是对象的数目。

上述实施方式的保序变换方法具有算法简单，处理速度快的优点。通过上述保序变换，用户向量在新对象矩阵中计算欧式空间的最近邻，就与在变换前的原始对象矩阵中进行最大内积搜索有着相同的结果。假设找到的最近邻是新对象矩阵的第j行向量，那么变换前搜索到的最大内积结果是原始对象矩阵的第j行向量。

在本发明的实施方式中，步骤S3的构建对象高维索引结构过程可以具体包括如下的步骤S31至步骤S32。

步骤S31：将新对象矩阵中的新对象向量聚类，得到多个对象子类，每个对象子类具有一个对象聚类中心。由于每个对象子类内部的数据具有相似性，因此在搜索时可以先找到与查询用户向量欧式距离最近的对象聚类中心，之后直接在属于该对象聚类中心的对象向量中寻找最近邻而忽略掉其它所有数据。假设指定有n个子类，在查询时只需要搜索大约1/n的数据，成n倍加快了最近邻的搜索速度。进行聚类之后，虽然此时在每一个对象子类内部可以直接进行线性搜索，但更高效的方式是进一步为每个对象子类中进一步建立vp-tree树结构。

步骤S32：为每个对象子类建立vp-tree树结构。vp-tree树结构的具体构建过程为：(1)选择当前对象数据集中的一个数据作为制高点(vantage-point，vp)。制高点可以随机选取。当制高点处于根节点时制高点对应的数据集包含子类中的全部数据。但通常制高点并不处于根节点，制高点对应的数据集为子类的部分数据。(2)计算数据集中其他所有数据与制高点的欧氏距离，将距离的中值保存在当前树节点中。距离的中值可用于数据划分及搜索时的条件判断。(3)将距离小于中值的数据划分到左子树，距离大于中值的数据划分到右子树。通过这样的划分将当前数据集划分为了两个部分。(4)利用步骤(3)划分成的两部分数据集分别构建左右子树。如果这两部分数据集包含的数据个数小于预定数目阈值(例如“1”)，则这部分建树过程结束。否则返回步骤(1)继续递归建树过程。

上述实施方式中，通过结合聚类和vp-tree技术来构建对象高维索引结构，可以节约搜索空间，提高搜索效率。

在本发明的实施方式中，步骤S4的最近邻搜索过程可以在单机上实现，但为了加快搜索速度，优选采用分布式技术在多个节点上实现。本发明并不限定分布式技术的具体形式，可以根据需要灵活选择，均可以实现加快搜索速度，提高搜索效率的目的。map-reduce技术与hadoop框架是最成熟最常见的分布式技术之一。采用map-reduce技术与hadoop框架实现最近邻搜索时，步骤S4的具体过程可以如下步骤S41至步骤S43所示。

步骤S41：将对象高维索引结构序列化地保存为对象索引文件并发送给多个节点。对象索引文件的保存的顺序和具体方式不限，只要保证通过读取对象索引文件可以在内存中恢复对象高维索引结构即可。例如，对象索引文件可以包括：每个聚类和vp-tree的映射、各个对象聚类中心向量，vp-tree树结构中各个节点距离中值、制高点向量在新对象矩阵中的索引以及左右子节点位置信息等等。此处为本领域技术人员的已知知识，不做赘述。

步骤S42：在每个节点上，根据新对象矩阵和对象索引文件重建出对象高维索引结构。具体过程为：读取完整的对象矩阵到内存中，反序列化对象索引文件，读取各个聚类中心向量，按顺序读取与每个聚类中心分别对应的vp-tree各节点的制高点、距离中值等数据，在内存中恢复vp-tree树结构。

步骤S43：采用map-reduce技术，通过hadoop框架在多个节点中对新用户矩阵中的各个新用户向量进行最近邻搜索，得到新用户向量对应的最近邻新对象向量。其中，步骤S43的具体过程可以如下步骤S431至步骤S433所示。

步骤S431：将新用户矩阵均分成多个新用户向量组并分发到多个节点，hadoop为分发到各个节点的新用户向量组分别建立mapper。

步骤S432：在各个mapper内为对应的新用户向量组中各个新用户向量执行以下操作：计算新用户向量与各个对象聚类中心的欧氏距离，找到欧氏距离最近的对象聚类中心。进入该欧氏距离最近的对象聚类中心对应的vp-tree，通过递归遍历树完成该vp-tree的最近邻搜索，得到新用户向量对应的最近邻新对象向量。

步骤S433：在reducer中汇总并保存新用户向量与对应的最近邻新向量对象的映射关系。

需要说明的是，步骤S431中设定的mapper个数越多，并行度越高，整体搜索速度越快。但每个mapper中都需要一份完整的对象高维索引结构，这将耗费大量内存资源，很容易出现内存瓶颈。因此mapper的个数需要合理设置。

还需要说明的是，尽管在步骤S431中为了节约内存资源限制了mapper个数，但是在执行步骤S432的过程中，可以在单个mapper内部使用多线程并行搜索多个新用户向量对应的最近邻新对象向量。这样，实现了mapper与mapper之间、线程与线程之间两个级别的并行，进一步提高计算效率。

还需要说明的是，步骤S432中“最近邻搜索”可以广义地理解为“K近邻搜索”，即“寻找出距离最近的前K(K为大于1的自然数)个向量”。这时，搜索过程中可以维护一个先序队列用于保存K近邻，变量tau记录队列中当前K近邻的最远距离。具体过程是：计算用户向量与当前节点中制高点的距离d；如果d小于tau，则将距离最远的邻居从队列中弹出，同时将当前结点的制高点放入队列，用d更新tau；如果d-tau小于等于当前节点的距离中值则进入左子树搜索，如果d+tau大于等于距离中值进入右子树搜索；搜索结束后，先序队列中保存的数据就是最终的K近邻。

图2是根据本发明实施例的获取推荐对象的装置的主要部件的示意图。如图2所示，该获取推荐对象的装置20主要包括矩阵构建模块21、保序变换模块22、索引构建模块23、搜索模块24以及输出模块25。

矩阵构建模块21用于构建原始用户矩阵和原始对象矩阵。原始用户矩阵中的每一行为原始用户向量，每个原始用户向量表示一个用户的多重属性特征。原始对象矩阵中的每一行为原始对象向量，每个原始对象向量表示一个对象的多重属性特征。

保序变换模块22用于对原始用户矩阵和原始对象矩阵进行保序变换，得到新用户矩阵和新对象矩阵。

索引构建模块23用于对新对象矩阵中的新对象向量构建对象高维索引结构。

搜索模块24用于对新用户矩阵中的各个新用户向量在对象高维索引结构中进行最近邻搜索，得到新用户向量对应的最近邻新对象向量。

输出模块25用于根据各个新用户向量及其对应的最近邻新对象向量，输出用户与推荐对象的映射。

由上可知，根据本发明实施例的获取推荐对象的装置，提出对原始用户矩阵和原始对象矩阵进行保序变换生成新数据。由于在新数据上进行欧氏空间的最近邻搜索与在原数据上做最大内积搜索有相同的结果，因此可以利用适用于欧式空间的对象高维索引结构等价地完成最大内积的搜索。因此，本发明的技术方案与传统的线性搜索技术相比具有更高计算效率，并且克服了现有技术中各种高维索引结构无法适用于最大内积搜索的问题，具有搜索速度快，适用范围广等优点。

在本发明的实施方式中，矩阵构建模块22还可以用于：对原始用户矩阵的第i行向量x_i添加数值0作为一个新的维度，得到新用户向量从而得到新用户矩阵。其中，i为自然数且1≤i≤A，A表示原始用户矩阵的行数，也就是用户的数目。矩阵构建模块22还可以用于：计算原始对象矩阵的第j行向量y_j的2-范数以及该2-范数的最大值对y_j添加作为一个新的维度，得到新对象向量从而得到新对象矩阵。其中，j为自然数且1≤j≤B，B表示原始对象矩阵的行数，也就是对象的数目。这样的保序变换方法具有算法简单，处理速度快的优点。

在本发明的实施方式中，索引构建模块23还可以用于：将新对象矩阵中的新对象向量聚类，得到多个对象子类，每个对象子类具有一个对象聚类中心；为每个对象子类建立vp-tree树结构。通过结合聚类和vp-tree技术来构建对象高维索引结构，可以节约搜索空间，提高搜索效率。

在本发明的实施方式中，搜索模块24还可以用于：将对象高维索引结构序列化地保存为对象索引文件并发送给多个节点；在每个节点上，根据新对象矩阵和对象索引文件重建出对象高维索引结构；采用map-reduce技术，通过hadoop框架在多个节点中对新用户矩阵中的各个新用户向量进行最近邻搜索，得到新用户向量对应的最近邻新对象向量。map-reduce技术与hadoop框架是最成熟最常见的分布式技术之一。

在本发明的实施方式中，搜索模块24还可以用于：将新用户矩阵均分成多个新用户向量组并分发到多个节点，hadoop为分发到各个节点的新用户向量组分别建立mapper；在各个mapper内为对应的新用户向量组中各个新用户向量执行以下操作：计算新用户向量与各个对象聚类中心的欧氏距离，找到欧氏距离最近的对象聚类中心，进入该欧氏距离最近的对象聚类中心对应的vp-tree，通过递归遍历树完成该vp-tree的最近邻搜索，得到新用户向量对应的最近邻新对象向量；在reducer中汇总并保存新用户向量与对应的最近邻新向量对象的映射关系。

综上，本发明的获取推荐对象的方法和装置，解决了推荐系统中矩阵分解的最大内积搜索在海量数据下因计算效率而无法实际应用的问题。本发明通过保序变换将内积搜索转化为欧式空间的K近邻搜索，结合聚类及高维索引树提出了一种高效的索引结构，并利用分布式及多线程技术突破了搜索计算的单机瓶颈，可以将整体的性能提高几个数量级，具有速度快，效率高等优点。

上述具体实施方式，并不构成对本发明保护范围的限制。本领域技术人员应该明白的是，取决于设计要求和其他因素，可以发生各种各样的修改、组合、子组合和替代。任何在本发明的精神和原则之内所作的修改、等同替换和改进等，均应包含在本发明保护范围之内。

Claims (10)

1.一种获取推荐对象的方法，其特征在于，包括：

构建原始用户矩阵和原始对象矩阵，其中，所述原始用户矩阵中的每一行为原始用户向量，每个所述原始用户向量表示一个用户的多重属性特征，所述原始对象矩阵中的每一行为原始对象向量，每个所述原始对象向量表示一个对象的多重属性特征；

对原始用户矩阵和原始对象矩阵进行保序变换，得到新用户矩阵和新对象矩阵；

对所述新对象矩阵中的新对象向量构建对象高维索引结构；

对所述新用户矩阵中的各个新用户向量在所述对象高维索引结构中进行最近邻搜索，得到所述新用户向量对应的最近邻新对象向量；

根据各个所述新用户向量及其对应的所述最近邻新对象向量，输出用户与推荐对象的映射。

2.根据权利要求1所述的获取推荐对象的方法，其特征在于，所述对原始用户矩阵和原始对象矩阵进行保序变换，得到新用户矩阵和新对象矩阵的步骤包括：

对所述原始用户矩阵的第i行向量x_i添加数值0作为一个新的维度，得到所述新用户向量从而得到所述新用户矩阵；

计算所述原始对象矩阵的第j行向量y_j的2-范数以及该2-范数的最大值对所述y_j添加作为一个新的维度，得到所述新对象向量从而得到所述新对象矩阵。

3.根据权利要求1或2所述的获取推荐对象的方法，其特征在于，所述对所述新对象矩阵中的新对象向量构建对象高维索引结构的步骤包括：

将所述新对象矩阵中的新对象向量聚类得到多个对象子类，每个对象子类具有一个对象聚类中心；

为每个所述对象子类建立vp-tree树结构。

4.根据权利要求3所述的获取推荐对象的方法，其特征在于，所述对所述新用户矩阵中的各个新用户向量在所述对象高维索引结构中进行最近邻搜索，得到所述新用户向量对应的最近邻新对象向量的步骤包括：

将所述对象高维索引结构序列化地保存为对象索引文件并发送给多个节点；

在每个所述节点上，根据所述新对象矩阵和所述对象索引文件重建出所述对象高维索引结构；

采用map-reduce技术，通过hadoop框架在所述多个节点中对所述新用户矩阵中的各个新用户向量进行最近邻搜索，得到所述新用户向量对应的最近邻新对象向量。

5.根据权利要求4所述的获取推荐对象的方法，其特征在于，所述采用map-reduce技术，通过hadoop框架在所述多个节点中对所述新用户矩阵中的各个新用户向量进行最近邻搜索，得到所述新用户向量对应的所述最近邻新对象向量的步骤包括：

将所述新用户矩阵均分成多个新用户向量组并分发到所述多个节点，所述hadoop为分发到各个节点的所述新用户向量组分别建立mapper；

在各个所述mapper内为对应的所述新用户向量组中各个新用户向量执行以下操作：计算所述新用户向量与各个所述对象聚类中心的欧氏距离，找到欧氏距离最近的所述对象聚类中心，进入该欧氏距离最近的对象聚类中心对应的vp-tree，通过递归遍历树完成该vp-tree的最近邻搜索，得到所述新用户向量对应的最近邻新对象向量；

在reducer中汇总并保存所述新用户向量与对应的所述最近邻新向量对象的映射关系。

6.一种获取推荐对象的装置，其特征在于，包括：

矩阵构建模块，用于构建原始用户矩阵和原始对象矩阵，其中，所述原始用户矩阵中的每一行为原始用户向量，每个所述原始用户向量表示一个用户的多重属性特征，所述原始对象矩阵中的每一行为原始对象向量，每个所述原始对象向量表示一个对象的多重属性特征；

保序变换模块，用于对原始用户矩阵和原始对象矩阵进行保序变换，得到新用户矩阵和新对象矩阵；

索引构建模块，用于对所述新对象矩阵中的新对象向量构建对象高维索引结构；

搜索模块，用于对所述新用户矩阵中的各个新用户向量在所述对象高维索引结构中进行最近邻搜索，得到所述新用户向量对应的最近邻新对象向量；

输出模块，用于根据各个所述新用户向量及其对应的所述最近邻新对象向量，输出用户与推荐对象的映射。

7.根据权利要求6所述的获取推荐对象的装置，其特征在于，所述矩阵构建模块还用于：

对所述原始用户矩阵的第i行向量x_i添加数值0作为一个新的维度，得到所述新用户向量从而得到所述新用户矩阵；

计算所述原始对象矩阵的第j行向量y_j的2-范数以及该2-范数的最大值对所述y_j添加作为一个新的维度，得到所述新对象向量从而得到所述新对象矩阵。

8.根据权利要求6或7所述的获取推荐对象的装置，其特征在于，所述索引构建模块还用于：

将所述新对象矩阵中的新对象向量聚类，得到多个对象子类，每个对象子类具有一个对象聚类中心；

为每个所述对象子类建立vp-tree树结构。

9.根据权利要求8所述的获取推荐对象的装置，其特征在于，所述搜索模块还用于：

将所述对象高维索引结构序列化地保存为对象索引文件并发送给多个节点；

在每个所述节点上，根据所述新对象矩阵和所述对象索引文件重建出所述对象高维索引结构；

采用map-reduce技术，通过hadoop框架在所述多个节点中对所述新用户矩阵中的各个新用户向量进行最近邻搜索，得到所述新用户向量对应的所述最近邻新对象向量。

10.根据权利要求9所述的获取推荐对象的装置，其特征在于，所述搜索模块还用于：

将所述新用户矩阵均分成多个新用户向量组并分发到所述多个节点，所述hadoop为分发到各个节点的所述新用户向量组分别建立mapper；

在各个所述mapper内为对应的所述新用户向量组中各个新用户向量执行以下操作：计算所述新用户向量与各个所述对象聚类中心的欧氏距离，找到欧氏距离最近的所述对象聚类中心，进入该欧氏距离最近的对象聚类中心对应的vp-tree，通过递归遍历树完成该vp-tree的最近邻搜索，得到所述新用户向量对应的最近邻新对象向量；

在reducer中汇总并保存所述新用户向量与对应的所述最近邻新向量对象的映射关系。