基于相似用户索引和ALS矩阵分解的推荐算法研究

２０１６年１２月　第３２卷第６期　陕西理工学院学报（自然科学版）　Ｊｏｕｒｎａｌ　ｏｆ　Ｓｈａａｎｘｉ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ）　ＤｅＣ．２０１６　Ｖｏ１．３２　Ｎｏ．６　［文章编号］１６７３—２９４４（２０１６）０６—００４７—０６　基于相似用户索引和ＡＬＳ矩阵分解　的推荐算法研究　盛伟，　余英，　王保云　（云南师范大学信息学院，云南昆明６５０５００）　［摘要］　针对交替最小二乘法（ＡＬｓ）在处理大数据集时所面临的处理速度和计算资源问　题，提出了基于相似用户索引的分布式矩阵分解推荐算法。首先算法基于用户的评分行为找　到用户之间的最近邻，然后使用Ｓｐａｒｋ平台运行提出的算法，并产生推荐。在ＧｒｏｕｐＬｅｎｓ网站　上提供的ＭｏｖｉｅＬｅｎｓ数据集上进行仿真实验，实验结果表明，提出的算法能够有效解决ＡＬＳ对　于大数据集运行效率低及在云环境中可扩展性较差的问题。　［关键词］　交替最小二乘法；　最近邻；推荐算法；Ｓｐａｒｋ　［文献标识码］Ａ　［中图分类号］ＴＰ３９１．３　个性化推荐系统如同一个信息过滤器，只把有用的信息提供给用户，有效解决了信息过载的问题。　协同过滤算法…是最成功的个性化推荐技术之一，被广泛应用于很多领域。然而，在现实生活中用户　和物品的数量庞大，而消费者通常只对一小部分物品进行评分，造成了评分矩阵严重稀疏，这导致传统　协同过滤算法可以利用的数据非常有限，推荐精度较差。在用户和物品不断增加的同时，评分矩阵的维　度也变得极高，这使得传统协同过滤算法的计算复杂度急剧增加，由此产生了可扩展性较差的问题。针　对数据稀疏性问题，李红梅等　提出利用ＬＳＨ快速获取目标用户的近邻用户集合，然后采用加权方法　来预测用户评分并产生推荐；ＬＩＫＡ　Ｂ等　提出了分类算法与相似度技术相结合的模型。针对可扩展性　较差的问题，孙天昊等　在分布式平台下，提出改进聚类协同过滤推荐算法。近年来，隐语义模型（Ｌａ—　ｔｅｎｔ　Ｆａｃｔｏｒ　Ｍｏｄｅｌ，ＬＦＭ）　受到越来越多的关注，矩阵分解技术是其中最常用的一种方法，这是一类有效　解决数据稀疏性问题的推荐算法，基于它的推荐模型获得了Ｎｅｔｌｆｉｘ　Ｐｒｉｚｅ推荐比赛冠军。此后，该方法　被应用于更多的推荐系统研究中　ｊ。在众多基于矩阵分解的方法中，交替最小二乘（Ａｈｅｒｎａｔｉｎｇ　Ｌｅａｓｔ　Ｓｑｕａｒｅｓ，ＡＬｓ）算法最为流行，它非常容易实现并行化计算。可是，随着用户数量的增加，ＡＬＳ需要计算　更多用户的评分集信息，计算量会迅速增大，ＡＬＳ在大数据集下的可扩展性更加不理想。　大数据计算平台的更新及数据的增长进一步促进了推荐系统的快速发展。Ｓｐａｒｋ是一个高效的分　布式计算平台，不同于需要过多的文件读取操作的ＭａｐＲｅｄｕｃｅ，可以将任务中间输出结果保存在内存　中，因此Ｓｐａｒｋ能更好地适用于数据挖掘、矩阵分解等需要迭代的算法。　本文提出一种基于相似用户索引的分布式矩阵分解推荐算法，结合分布式计算特点，利用位置敏感　收稿日期：２０１６－０５－０６　修回日期：２０１６－０６－１３　基金项目：云南省教育厅科学研究基金资助项目（２０１４Ｙ１４５）　作者简介：盛伟（１９８８一），男，江苏省丰县人，云南师范大学硕士研究生，主要研究方向为推荐系统；［通信作者］余英　（１９６５一），女，云南省昆明市人，云南师范大学副教授，硕士生导师，硕士，主要研究方向为网络通信；王保云（１９７７一），　男，云南省玉溪市人，云南师范大学讲师，博士，主要研究方向为机器学习。　陕西理工学院学报（自然科学版）　第３２卷　哈希（Ｌｏｃａｌｉｔｙ　Ｓｅｎｓｉｔｉｖｅ　Ｈａｓｈｉｎｇ，ＬＳＨ）处理高维数据的良好特性来快速寻找用户之间的近邻集合，并将　其植入到ＡＬＳ矩阵分解推荐技术中，降低了计算复杂度，改善了算法可扩展性较差的问题并且在一定　程度上提高了推荐精度。　１　基于相似用户索引和ＡＬＳ矩阵分解的推荐算法　首先将己知用户一物品评分数据集分为训练集　和测试集　，训练集用来学习矩阵特征并构建　ＬＳＨ模型，测试集用来评价推荐结果。本文提出的算法分为两个阶段进行，分别是ＬＳＨ的相似用户索　引构建和基于ＡＬＳ的矩阵分解推荐。以上阶段均在Ｓｐａｒｋ集群下进行分布式计算，算法流程如图１所　示。　图１　基于相似用户索引和ＡＬＳ矩阵分解的推荐算法流程图　Ｓｐａｒｋ是ＵＣ　Ｂｅｒｋｅｌｅｙ　ＡＭＰ　Ｌａｂ开源的通用并行计算框架。Ｓｐａｒｋ立足于内存计算，提供了批处理、　实时数据处理、机器学习以及图算法等一站式服务，非常适合于各种迭代算法和交互式数据挖掘。　Ｓｐａｒｋ中使用了弹性分布式数据集（Ｒｅｓｉｌｉｅｎｔ　Ｄｉｓｔｉｒｂｕｔｅｄ　Ｄａｔａｓｅｔｓ，ＲＤＤ）Ｉｓ］抽象分布式计算，即使用ＲＤＤ　以及对应的相关操作来执行分布式计算；并且基于ＲＤＤ之间的依赖关系组成Ｌｉｎｅａｇｅ以及ＣｈｅｃｋＰｏｉｎｔ　等机制来保证整个分布式计算的容错性。　Ｓｐａｒｋ运行架构如图２所示，用户将任务提交给Ｄｒｉｖｅｒ，Ｄｒｉｖｅｒ将任务分发到所有的Ｗｏｒｋｅｒ节点。　Ｗｏｒｋｅｒ节点根据Ｄｒｉｖｅｒ提交过来的任务，算出位于本地的那部分数据，将数据以ＲＤＤ的形式保存到内　存中，然后对ＲＤＤ进行接下来的计算。用户提交的任务一般在Ｃｌｕｓｔｅｒ　Ｍａｎａｇｅｒ中运行，目前Ｓｐａｒｋ支持　Ｓｔａｎｄａｌｏｎｅ、Ｍｅｓｏｓ和ＹＡＲＮ等不同的Ｃｌｕｓｔｅｒ　Ｍａｎａｇｅｒ，本文选择的是Ｓｔａｎｄａ｜ｏｎｅ模式。　图２　Ｓｐａｒｋ运行架构图　１．１基于ＬＳＨ的相似用户索引构建　建立相似用户索引，不仅可以过滤掉与目标用户不相关的评分信息，还降低了推荐算法需要计算的　评分矩阵维度。因此，基于相似用户索引的推荐算法能够快速为用户产生推荐。　针对上述问题，本文引入ＬＳＨ　９。。。对相似用户建立索引。ＬＳＨ是当前最流行的近似最近邻快速查　找技术之一，它使用哈希的方法把数据从原空间哈希到一个新的空间中，如果数据在原空间中相似，那　．４８・　第６期　盛伟，余英，王保云　基于相似用户索引和ＡＬＳ矩阵分解的推荐算法研究　么哈希到新的空间中的数据也保持一定的相似性。ＬＳＨ通过原始评分矩阵，能够将评分行为相似的用　户以一定的概率散列到同一个桶中。　定义（位置敏感哈希）存在函数族Ｈ＝｛ｈ：　一　｝，对于任意的数据点Ｐ，ｑ∈Ｊｓ，都有：　若Ｐ∈Ｂ（ｇ，ｒ１），则Ｐｒ［ｈ　（Ｐ）＝ｈ　（ｇ）］＞ｐ　；　若Ｐ∈Ｂ（ｑ，ｒ２），贝０　Ｐ，［ｈ　（Ｐ）＝ｈ　（ｇ）］＞ｐ２；　如果满足条件Ｐ　＞ｐ　和ｒ。＜ｒ：，就称此函数族是（ｒ。，ｒ：，Ｐ。，Ｐ：）敏感的函数族。　对评分数据处理之前，首先需要将评分数据向量化。通常评分数据向量化是对用户评分行为的提　取，通过相关计算将评分数据转化成对应的高维向量。常用的向量度量方式有：欧式距离、杰卡德距离　以及余弦距离等。在这些度量方式中余弦距离在实际应用中有较好的效果。　在余弦距离的度量下，Ｃｈａｉｒｋａｒ　Ｍ　Ｓ＿】　于２００２年提出了超平面的思想，通过随机的超平面将原始　数据空间进行划分，其中每一个空间构成一个散列桶，而位于每个桶内的数据被认为具有很大的相似　性。因此我们选用超平面的思想方法对评分数据进行哈希。Ｃｈａｉｒｋａｒ　Ｍ　Ｓ设计了一族哈希函数，使得　落人平面一侧的向量被哈希为１，另一侧被哈希成为０，哈希函数如公式（１）所示：　ｈ　（１，）：ｆ　，　其中ｌ，是待哈希的向量，Ｈ是随机生成的向量。　【Ｏ，　ｌ，・　≥【Ｊ，　＜０，　（１）　当数据量变得很大时，用户评分行为向量的维度也变得很高，单机模式的ＬＳＨ构建会因为内存的　限制而变得很慢，甚至无法继续运行。本文利用Ｓｐａｒｋ平台将ＬＳＨ构建过程分布化和并行化，以适应海　量高维数据的计算需求。基于Ｓｐａｒｋ的ＬＳＨ索引模型构造算法描述如下：　输入：评分数据　，哈希函数数目Ｋ，哈希表数Ｌ；　输出：ＬＳＨ索引模型，　①ｖａｒ　ｓｅ＝ｎｅｗ　ｓｐａｒｋＣｏｎｔｅｘｔ（），　②ｖａｌ　ｄａｔａ＝ｓｃ．ｔｅｘｔＦｉｌｅ（”…”，ｎｕｍＰａ￣ｉｏｎ），　③数据经过ｍａｐ生成ｓｐａｒｓｅＶｅｃｔｏｒＤａｔａ：ＲＤＤ［ｕｓｅｒ—ｉｄ，ＳｐａｒｓｅＶｅｃｔｏｒ］，ＳｐａｒｓｅＶｅｃｔｏｒ是序列＜Ｉｔｅｍ：　Ｉｎｔ，ｒａｔｉｎｇ：Ｄｏｕｂｌｅ＞，　④Ｈａｓｈｅｒ（Ｋ　Ｌ，ｓｅｅｄ）随机生成Ｋ　Ｌ个哈希函数Ｈａｓｈ（Ｕ：ＳｐａｒｓｅＶｅｃｔｏｒ）利用随机生成的哈希函数　和公式（１）对每个向量生成ｈａｓｈ　ｓｉｇｎａｔｕｒｅ（ｅ．ｇ．１１１１００１０），　⑤保存哈希过的向量ｈａｓｈＴａｂｌｅｓ：ＲＤＤ［（（ｈａｓｈＴａｂｌｅｌｄ，ｈａｓｈＶａｌｕｅ），ｕｓｅｒ＿ｉｄ）］，　⑥输出ＬＳＨ模型。　代码中：第①一②行初始化ＳｐａｒｋＣｏｎｔｅｘｔ，从ＨＤＦＳ中读人数据；第③行根据原始评分数据生成每个　用户对所有已评分项目的评分记录向量；第④一⑤行利用随机超平面的思想对原始数据进行划分。　１．２基于ＡＬＳ的矩阵分解推荐算法　在协同过滤推荐系统中，输人数据可以用一个ｍ行ｎ列的评分矩阵　来表示，本文称之为Ｕｓｅｒ—Ｉ—　ｔｅｍ矩阵，其中ｍ表示用户数目，ｎ表示物品数目。真实生活中消费者产生的评分数据非常少，造成ｕｓ—　ｅｒ．Ｉｔｅｍ矩阵极为稀疏。矩阵分解的核心思想是把稀疏的Ｕｓｅｒ．Ｉｔｅｍ评分矩阵分解为两个低维度的矩阵　Ｐ和Ｑ，用一个重构的低秩预测矩阵　＝ＰＱＴ来逼近原来的评分矩阵，逼近的目标是使预测矩阵和原始　矩阵之间误差的平方最小，其中Ｐ为ｍ　ｘｄ（ｄ表示特征个数，也即为低维度矩阵的维度）的用户特征向　量矩阵，Ｑ为ｎ×ｄ的物品特征向量矩阵。预测方法如公式（２）所示：　，　＝ｐ　ｑ　，　（２）　其中ｐ　和垡　分别为用户／Ｚ和物品ｉ的特征向量，ｒ　为用户　对物品　的预测评分。当矩阵中含有大量　空值时，此模型容易导致过拟合问题。许多研究者建议采用一个正则化　。　模型来避免过拟合问题。其　需要优化的函数如式（３）：　Ｐ’，ｑ’（ｕ．ｉ）ＥＫ　ｍｉｎ∑（ｒ　一ｐ　ｇ　）　＋Ａ（Ｉ　ｌ　＋　ｌｌ　），ｌ　（３）　・４９．　陕西理工学院学报（自然科学版）　第３２卷　其中Ａ是正则化系数，Ｋ代表已有评分记录，ｒ　为用户ｕ对项目ｉ的真实评分。ＡＬＳ算法是求解上述模　型最常用的方法。　ＡＬＳ算法基本求解思想是固定Ｐ求解Ｑ，然后固定Ｑ求解Ｐ，重复交替上述两步直到算法收敛。　ＡＬＳ算法易于实现并行化，然而随着评分数据的增加，它需要更多的计算时间，大数据集下推荐效率不　高。因此本文采用ＬＳＨ和ＡＬＳ相结合的算法。对于评分矩阵　，可以利用ＬＳＨ算法对具有相似评分记　录的用户进行粗略划分，得到相应的相似用户评分数据。然后为了产生项目推荐结果，可以利用相似用　户的评分数据进行ＡＬｓ推荐。这样不仅减少了ＡＬＳ算法的计算量，改善了算法可扩展性较差的问题，　也提高了推荐精度。算法描述如下：　输入：原始评分矩阵　，评分测试集　，ＬＳＨ索引模型ＬＳＨＭｏｄｅｌ；　输出：推荐列表，　①ｖａｔ　ｓｅ＝ｎｅｗ　ｓｐａｒｋＣｏｎｔｅｘｔ（），　②ｖａｌ　ｄａｔａ＝ｓｅ．ｔｅｘｔＦｉｌｅ（”…”，ｎｕｍＰａｒｔｉｏｎ），　③读入　生成ＴｅｓｔＲａｔｉｎｇｓ：ＲＤＤ［Ｒａｔｉｎｇ］，Ｒａｔｉｎｇ是序列＜ｕｓｅｒ：Ｉｎｔ，ｉｔｅｍ：Ｉｎｔ，ｒａｔｉｎｇ：Ｄｏｕｂｌｅ＞，　④ＬＳＨＭｏｄｅ１．ｇｅｔＣａｎｄｉｄａｔｅｓ（ＴｅｓｔＲａｔｉｎｇｓ：ＲＤＤ［（Ｉｎｔ，Ｉｎｔ，Ｄｏｕｂｌｅ）］）生成相似用户集合　，　⑤读人　根据　生成候选集Ｈｒａｔｉｎｇｓ：ＲＤＤ［Ｒａｔｉｎｇ］，　⑥ＡＬＳ．ｔｒａｉｎ（Ｈｒａｔｉｎｇｓ，ｒａｎｋ，ｎｕｍｈｅｒ，ｌａｍｂｄａ）对评分数据Ｈｒａｔｉｎｇｓ进行ｎｕｍｌｔｅｒ次训练，ｒａｎｋ是用户　因子矩阵和项目因子矩阵的维度，ｌａｍｂｄａ是正则化因子，　⑦ｒｅｃｏｍｍｅｎｄＰｒｏｄｕｃｔｓ（ｒ，　）为用户ｒ产生ｉ个初始推荐，　⑧输出推荐列表。　代码中：第①一②行初始化ＳｐａｒｋＣｏｎｔｅｘｔ，从ＨＤＦＳ中读人数据；第③行读取并生成评分测试集；第　④一⑤行评分测试数据集通过算法１的ＬＳＨ模型的ＬＳＨ映射获得相似用户集合，最后生成评分数据候　选集合。第⑥～⑦行ＡＬＳ算法训练候选集合生成ＡＬＳ推荐模型，完成测试数据集的用户ＴＯＰ－Ｎ推荐。　２实验及结果分析　根据上述研究，利用４台计算机搭建Ｓｐａｒｋ分布式集群，其中一台计算机作为Ｍａｓｔｅｒ节点，另外３　台作为Ｓｌａｖｅ节点负责运算。每个节点内存为２　ＧＢ，２核，安装ＣｅｎｔＯＳ　６．７操作系统和Ｓｐａｒｋ　１．４．１。程　序采用ＩｎｔｅｌｌｉＪ　ＩＤＥＡ集成开发环境完成。从ＧｒｏｕｐＬｅｎｓ网站（ｈｔｔｐ：／／ｗｗｗ．ｇｏｕｐｌｅｎｓ．ｏｒｇ）下载ＭｏｖｉｅＬｅｎｓ　１００　ＫＢ和１　ＭＢ两个不同大小的数据集作为本文的数据源，其中１００　ＫＢ数据集包含了９４３个用户对　１　６８２部电影的评分，共１００　０００条评分记录；１　ＭＢ数据集包含６　０４０个用户对３　９００部电影的评分，共　１　０００　２０９条评分记录。　实验采用加速比Ｓ＝Ｌ　／Ｌ　衡量同一数据集下增加节点时本文算法的运行效率，其中￡　为单个节　点完成任务所需的时间，￡　为ｎ个节点完成任务所需的时间。实验过程中，从１个节点增加到４个节　点，分别测试１００　ＫＢ和１　ＭＢ数据集在单机模式下的运行时间以及在不同规模Ｓｐａｒｋ集群下的运行时　间，获取其完成运算所需时间　—　，绘制加速比曲线图如图３所示。　从图３可以看出，随着Ｓｐａｒｋ集群节点数目的增加，两组数据集的加速比值都在增大，因此增加节　点数目可以提高算法执行效率。１００　ＫＢ数据集的加速比值较小，加速比曲线增长缓慢，１　ＭＢ数据集的　加速比值较大。针对同一节点，数据量很小的情况下加速比不明显，随着数据量增加，加速比曲线提升　明显，可以预期处理更大规模数据集时，本文算法执行效率会进一步提升。　实验采用均平方根差ＲＭＳＥ　Ｌｌ　作为本文算法推荐质量的评价指标。ＲＭＳＥ的值越小，表明算法的　推荐准确率越高，其公式为　ＲＭＳＥ＝　．　（４）　其中Ⅳ为物品数量，　为真实的评分，Ｐ　为预测的分数。从１００　ＫＢ数据集中分别选取用户数量为１００、　３００、７００和９４３作为４组实验数据（表１）。本文实现的算法与传统矩阵分解算法的比较如图４所示。　第６期　盛伟，余英，王保云　基于相似用户索引和ＡＬｓ矩阵分解的推荐算法研究　表１　４组实验数据量　２－４　２＿２　２．Ｏ　筮１．８　・．６　ｌ－４　１．２　１．Ｏ　∞善ｒ　４　０　３　Ｏ　２ｏＯ　４００　６ｏｏ　８ｏｏ　ｌ　０００　节点数目　５　２　９　６　用户数目　图３加速比曲线图　图４　ＲＭＳＥ值　从图４可看出，随着用户数据逐渐增大，ＡＬＳ推荐算法的推荐精度也在逐渐提高，所以ＡＬＳ算法在　处理大规模数据集时在推荐精度上有显著优势。然而，由于数据量巨大，ＡＬＳ算法需要计算很多不相关　信息，推荐精度还有进一步提升的空间。本文算法利用ＬＳＨ技术找到用户最近邻，过滤掉不相似用户　的评分信息，在此数据集的基础上再进行推荐，在改善ＡＬｓ算法复杂度的同时，推荐结果也更加精确。　３　结语　本文针对ＡＬＳ矩阵分解算法存在的计算开销大及可扩展性较差的问题，结合Ｓｐａｒｋ分布式计算和　ＬＳＨ快速处理高维数据的特点，提出了基于相似用户索引的分布式矩阵分解推荐算法。利用ＬＳＨ找到　用户之间的最近邻集合，ＡＬｓ通过这些用户的评分数据重新排列用户的喜好列表，形成最后的推荐，降　低了时间复杂度。同时，算法在大数据环境下具有良好的可扩展性。后续研究将结合其他用户信息或　者项目信息进行更准确地推荐。　［　参考文献］　［１］ＬＩＵ　Ｚｈａｏ—ｂｉｎ，ＱＵ　Ｗｅｎ－ｙｕ，ＬＩ　Ｈａｉ－ｔａｏ，ｅｔ　ａ１．Ａ　ｈｙｂｒｉｄ　ｃｏｌｌａｂｏｒａｔｉｖｅ　ｆｉｌｔｅｒｉｎｇ　ｒｅｃｏｍｍｅｎｄａｔｉｏｎ　ｍｅｃｈａｎｉｓｍ　ｆｏｒ　Ｐ２Ｐ　ｎｅｔｗｏｒｋｓ　［Ｊ］．Ｆｕｔｕｒｅ　ｇｅｎｅｒａｔｉｏｎ　ｃｏｍｐｕｔｅｒ　ｓｙｓｔｅｍｓ，２０１０，２６（８）：１４０９—１４１７．　［２］　李红梅，郝文宁，陈刚．基于改进ＬＳＨ的协同过滤推荐算法［Ｊ］．计算机科学，２０１５，４２（１０）：２５６－２６１．　［３］ＬＩＫＡ　Ｂ，ＫＯＬＯＭＶＡＴＳＯＳ　Ｋ，ＨＡＤＪＩＥＦｒＨＹＭＩＡＤＥＳ　Ｓ．Ｆａｃｉｎｇ　ｔｈｅ　ｃｏｌｄ　ｓｔａｒｔ　ｐｒｏｂｌｅｍ　ｉｎ　ｒｅｃｏｍｍｅｎｄｅｒ　ｓｙｓｔｅｍｓ［Ｊ］．Ｅｘｐｅ￣　Ｓｙｓｔｅｍｓ　ｗｉｔｈ　Ａｐｐｌｉｃａｔｉｏｎｓ，２０１４，４１（４）：２０６５－２０７３．　［４］孙天吴，黎安能，李明，等．基于Ｈａｄｏｏｐ分布式改进聚类协同过滤推荐算法研究［Ｊ］．计算机工程与应用，２０１５，　５１（１５）：１２４—１２８．　［５］ＫＯＲＥＮ　Ｙ，ＢＥＬＬ　Ｒ，ＶＯＬＩＮＳＫＹ　Ｃ．Ｍａｔｉｒｘ　ｆａｃｔｏｒｉｚａｔｉｏｎ　ｔｅｃｈｎｉｑｕｅｓ　ｏｆｒ　ｒｅｃｏｍｍｅｎｄｅｒ　ｓｙｓｔｅｍｓ［Ｊ］．Ｃｏｍｐｕｔｅｒ，２００９，４２（８）：　３０－３７．　［６］ＪＡＭＡＬＩ　Ｍ，ＥＳＴＥＲ　Ｍ．Ａ　ｍａｔｉｒｘ　ｆａｃｔｏｒｉｚａｔｉｏｎ　ｔｅｃｈｎｉｑｕｅ　ｗｉｔｈ　ｔｒｕｓｔ　ｐｒｏｐａｇａｔｉｏｎ　ｆｏｒ　ｒｅｃｏｍｍｅｎｄａｔｉｏｎ　ｉｎ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋｓ［ｃ　３／／　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ｆｏｕｒｔｈ　ＡＣＭ　ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｒｅｃｏｍｍｅｎｄｅｒ　ｓｙｓｔｅｍｓ．ＡＣＭ，２０１０：１３５—１４２．　［７］ＴＡＫＡＣＳ　Ｇ，ＰＩＬ￣ＳＺＹ　Ｉ，Ｎｌ￣ＭＥＴＨ　Ｂ，ｅｔ　１．Ｉａｎｖｅｓｔｉｇａｔｉｏｎ　ｏｆ　ｖａｒｉｏｕｓ　ｍａｔｉｒｘ　ｆａｃｔｏｒｉｚａｔｉｏｎ　ｍｅｔｈｏｄｓ　ｆｏｒ　ｌａｒｇｅ　ｒｅｃｏｍｍｅｎｄｅｒ　ｓｙｓ－　ｔｅｒｎｓ［Ｃ］／／２００８　ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｄａｔａ　Ｍｉｎｉｎｇ　Ｗｏｒｋｓｈｏｐｓ．ＩＥＥＥ，２００８：５５３－５６２．　［８］　ＺＡＨＡＲＩＡ　Ｍ，ＣＨＯＷＤＨＵＲＹ　Ｍ，ＤＡＳ　Ｔ，ｅｔ　ａ１．Ｒｅｓｉｌｉｅｎｔ　ｄｉｓｔｉｒｂｕｔｅｄ　ｄａｔａｓｅｔｓ：Ａ　ｆａｕｌｔ—ｔｏｌｅｒａｎｔ　ａｂｓｔｒａｃｔｉｏｎ　ｆｏｒ　ｉｎ—ｍｅｍｏｒｙ　ｃｌｕｓｔｅｒ　ｃｏｍｐｕｔｉｎｇ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　９ｔｈ　ＵＳＥＮＩＸ　ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｎｅｔｗｏｒｋｅｄ　Ｓｙｓｔｅｍｓ　Ｄｅｓｉｇｎ　ａｎｄ　Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ．　・５１．　陕西理工学院学报（自然科学版）　ＵＳＥＮＩＸ　Ａｓｓｏｃｉａｔｉｏｎ．２０１２：２．　第３２卷　『９］ＡＮＤＯＮＩ　Ａ，ＩＮＤＹＫ　Ｐ．Ｎｅａｒ－ｏｐｔｉｍａｌ　ｈａｓｈｉｎｇ　ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ｎｅａｒ　ｎｅｉｇｈｂｏｒ　ｐｒｏｂｌｅｍ　ｉｎ　ｈｉｇｈ　ｄｉｍｅｎｓｉｏｎｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　ｔｈｅ　Ｆｏｕｎｄ￣ｉｏｎｓ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，２００６：４５９－４６８．　『１０］ＳＬＡＮＥＹ　Ｍ，ＣＡＳＥＹ　Ｍ．Ｌｏｃａｌｉｔｙ－ｓｅｎｓｉｔｉｖｅ　ｈａｓｈｉｎｇ　ｏｆｒ　ｉｆｎｄｉｎｇ　ｎｅａｒｅｓｔ　ｎｅｉｇｈｂｏｒｓ［１ｅｃｔｕｒｅ　ｎｏｔｅｓ］…．ＩＥＥＥ　Ｓｉｇｎａｌ　Ｐｒ０ｃｅｓｓ—　ｉｎｇ　Ｍａｇａｚｉｎｅ，２００８，２５（２）：１２８—１３１．　［１１　１　ＣＨＡＲＩＫＡＲ　Ｍ　Ｓ．Ｓｉｍｉｌａｒｉｔｙ　ｅｓｔｉｍａｔｉｏｎ　ｔｅｃｈｎｉｑｕｅｓ　ｆｒｏｍ　ｒｏｕｎｄｉｎｇ　ａｌｇｏｒｉｔｈｍｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ｔｈｉｒｙ。ｆｏｕｒｔｈ　ａｎｎｕａｌ　ＡＣＭ　ｓｖｍｐｏｓｉｕｍ　ｏｎ　Ｔｈｅｏｒｙ　ｏｆ　ｃｏｍｐｕｔｉｎｇ．ＡＣＭ，２００２：３８０－３８８．　ＰＡＴＥＲＥＫ　Ａ．Ｉｍｐｒｏｖｉｎｇ　ｒｅｇｕｌａｒｉｚｅｄ　ｓｉｎｇｕｌａｒ　ｖａｌｕｅ　ｄｅｃｏｍｐ。ｓｉｔｉ。ｎ　ｆｏｒ　ｃｏｌｌａｂｏｒａｔｉＶｅ　ｉｆｌｔｅｒｉｎｇ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ＫＤＤ　ｃ“ｐ　ａｎｄ　ｗｏｒｋｓｈｏｐ，２００７：５－８．　ＲＩＣＣＩ　Ｆ，ＲＯＫＡＣＨ　Ｌ，ＳＨＡＰＩＲＡ　Ｂ，ｅｔ　ａ１．Ｒｅｃｏｍｍｅｎｄｅｒ　ｓｙｓｔｅｍｓ　Ｈａｎｄｂ０ｏｋ［Ｍ］．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅ卜Ｖｅｆｌａｇ，２０１１：１０９・　［责任编辑：魏强］　ＡＬＳ．ｂａｓｅｄ　ｍａｔｒｉｘ　ｆａｃｔｏｒｉｚａｔｉｏｎ　ｒｅｃｏｍｍｅｎｄａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｗｉｔｈ　ｓｉｍｉｌａｒ　ｕｓｅｒ　ｉｎｄｅｘ　ＳＨＥＮＧ　Ｗｅｉ，　ＹＵ　Ｙｉｎｇ，　ＷＡＮＧ　Ｂａｏ—ｙｕｎ　ｆ　Ｓｃｈ。。ｌ。ｆ　Ｉｎｆ０ｒｒｎａｔｉ。ｎ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎ。１。ｇＹ，Ｙｕｎｎａｎ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｋｕｎｍｉｎｇ　６５０５００，Ｃｈｉｎａ）　ｓｐｅｅｄ　ａｎｄ　ｒｅｓｏｕｒｃｅ　ａｌｌｏｃａｔｉｏｎ　ｏｆ　Ａ１－　ｔｌｅｎｅｃｋ　ｐｒｏｂｌｅｍｓ　ｏｆ　ｐｒｏｃｅｓｓｉｎｇ　Ａｂｓｔｒａｃｔ：　Ｉｎ　ｏｒｄｅｒ　ｔｏ　ｓｏｌｖｅ　ｔｈｅ　ｂｏｔｒｅｃｏｍｍｅｎｄａｔｉｏｎ　ａｐｐｒｏａｃｈ　ｗｉｔｈ　ｓｉｍｉ—　ｔｅｒｎａｔｉｎｇ　Ｌｅａｓｔ　Ｓｑｕａｒｅｓ（ＡＬＳ），　ａ　ｄｉｓｔｉｒｂｕｔｅｄ　ｐａｒａｌｌｅｌ　ｍａｔｉｒｘ　ｆａｃｔｏｒｉｚａｔｉｏｎ　ｌａｒ　ｕｓｅｒ　ｉｎｄｅｘ　ｗａｓ　ｐｒｏｐｏｓｅｄ．　Ｆｉｒｓｔ，ｔｈｅ　ａｐｐｒｏａｃｈ　ｆｏｕｎｄ　ｎｅａｒｅｓｔ　ｎｅｉｇｈｂｏｒｓ　ａｍｏｎｇ　ｔｈｅ　ｕｓｅｒｓ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｒ　ｒａｔ—　ｉｎｇｓ；Ｔｈｅｎ，Ｓｐａｒｋ　ｗａｓ　ｅｍｐｌｏｙｅｄ　ｔｏ　ｉｍｐｌｅｍｅｎｔ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ａｐｐｒｏａｃｈ，ａｎｄ　ｔｈｅ　ｒｅｃｏｍｍｅｎｄａｔｉｏｎ　ｔｏ　ｔｈ　ｕｓｅｒ　ｐｒｏｄｕｃｅｄ．　Ｓｉｍｕｌａｔｅ　ｅｘｐｅｒｉｍｅｎｔｓ　ｉｎ　ＭｏｖｉｅＬｅｎｓ　ｄａｔａｓｅｔｓ　ｐｒｏｖｉｄｅｄ　ｂｙ　ＧｒｏｕｐＬｅｎｓ　ｗｅｂｓｉｔｅ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ａｌｇｏｒｉｔｈｍ　ｃａｎ　ｒｅｓｏｌｖｅ　ｔｈｅ　ｉｓｓｕｅ　ｏｆ　ｌｏｗ　ｅｘｅｃｕｔｉｏｎ　ｅｆｆｉｃｉｅｎｃｙ　ｏｆ　ＡＬＳ　ｆｏｒ　ｌａｒｇｅ。ｓｃａｌｅ　ｄａｔａｓｅｔｓ　ａｎｄ　ｔｈｅ　ｗｏｒｓｅ　ｓｃａｌ’　ａｂｉｌｉｔｙ　ｉｎ　ｃｌｏｕｄｓ．　ＫｅＶ　ｗｏｒｄｓ：　ａｈｅｒｎａｔｉｎｇ　ｌｅａｓｔ　ｓｑｕａｒｅｓ；　ｎｅａｒｅｓｔ　ｎｅｉｇｈｂｏｒｓ；　ｒｅｃｏｍｍｅｎｄａｔｉｏｎ　ａｌｇｏｒｉｔｈ；　Ｓｐａｒｋ　（上接第１８页）　Ｓｏｆｔｗａｒｅ　ｄｅｖｅｌｏｐｍｅｎｔ　ｏｎ　ｌｉｔｆｉｎｇ　ｃａｐａｃｉｔｙ　ｆｏｒ　ｂｉｇ　ｔｏｎｎａｇｅ　ｍｏｂｉｌｅ　ｃｒａｎｅ　ＮＩＮＧ　Ｗｅｉ，ＰＥＮＧ　Ｆｅｎｇ・ｓｈｅｎｇ　ｆ　Ｓｃｈｏｏ１　ｏｆ　Ｍｅｃｈａｎｉｃａｌ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｓｈａａｎｘｉ　Ｓｃｉ—Ｔｅｃｈ　Ｕｎｉｖｅｒｓｉｔｙ，Ｈａｎｚｈｏｎｇ　７２３０００，Ｃｈｉｎａ）　ｏｒｆ　ｌｉｆｔｉｎｇ　ｃａｐａｃｉｔｙ　ｏｆ　ｍｏｂｉｌｅ　ｃｒａｎｅ，ｔｈｅ　ｌｉｔｆｉｎｇ　ｃａｐａｃｉｔｙ　Ａｂｓｔｒａｃｔ：　Ｉｎ　ｔｅｒｍｓ　ｏｆ　ｔｈｅ　ｃａｌｃｕｌａｔｉｏｎ　ｐｒｏｂｌｅｍ　ｔｈｅ　ＡＮＳＹＳ　ｐｌａｔｆｏｒｍ　ｂａｓｅｄ　ｏｎ　ｒｅｌａｔｅｄ　ｔｈｅｏｒｙ　ａｌｇｏｒｉｔｈｍｓ．　ｃａ１ｃｕｌａｔｉＯｎ　ｓｏｆｔｗａｒｅ　ｆｏｒ　ｍｏｂｉｌｅ　ｃｒａｎｅ　ｉｓ　ｄｅｖｅｌｏｐｅｄ　ｏｎ　Ｆｉｒｓｔｌｙ，ｔｈｅ　ｓｔｍｃｔｕｒｅ　ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ　ｆｏｒ　ｃｒａｎｅ　ｂｏｏｍ　ａｎｄ　ｔｈｅ　ｗｈ。１ｅ　ｍａｃｈｉｎｅ　ａｒｅ　ｐａｒａｍｅｔｅｒｉｚｅｄ・Ｓｅｃｏｎｄｌｙ，ｔｈｅ　ｆｉｎｉｔｅ　ｅｌｅｍｅｎｔ　ｐａｒａｍｅｔｒｉｃ　ｍ。ｄｅｌ　ｏｆ　ｃｒａｎｅ　ｂｏｏｍ　ｉｓ　ｅｓｔａｂｌｉｓｈｅｄ．Ｔｈｅ　ｎｏｎｌｉｎｅａｒ　ｓｔａｔｉｃ　ａｎａｌｙｓｉｓ　ｉｓ　ｅｘｅｃｕｔｅｄ　ｂｙ　ｃａ１ｌ。　ｉｎｇ　ＡＮＳＹＳ　ｓ０１ｖｅｒ．Ｆｉｎａｌｌｙ，ｔｈｅ　ｃａｌｃｕｌａｔｉｏｎ　ｒｅｓｕｌｔｓ　ａｒｅ　ａｐｐｒａｉｓｅｄ　ｂｙ　Ｖｉｒｔｕｅ　ｏｆ　ｓａｆｅｔｙ　ｅｖａｌｕａｔｉｏｎ　ｓｙｓｔｅｍ　Ｌｉｔｆｉｎｇ　ｃａｐａｃｉｔｙ　ｒｅｓｕｌｔｓ　ａｒｅ　ｏｂｔａｉｎｅｄ　ｔｈｒｏｕｇｈ　ｉｔｅｒａｔｉｖｅ　ｃａｌｃｕｌａｔｉｏｎ．　Ｓｏｆｔｗａｒｅ　ｉｎｔｅｒｆａｃｅ　ｍｏｄｕｌｅ　ｕｓｅｓ　ｔｈｅ　ＴＣＬ／ＴＫ　ｌａｎ　ｇｕａｇｅ　ａｎｄ　ｔｈｅ　０ｔｈｅｒ　ｍｏｄｕｌｅｓ　ｕｓｅ　ｔｈｅ　ＡＰＤＬ　ｌａｎｇｕａｇｅ．Ｔｈｅ　ｃｒａｎｅ　ｌｏａｄ　ｔｅｓｔ　ｉｎ　ｍｏｂｉｌｅ　ｃｒａｎｅ　ｉｓ　ｃａｒｒｉｅｄ　ｏｕｔ・　Ｅｘ—　Ｄｅｒｉｍｅｎｔａｌ　ｒｅｓｕＩｔｓ　ｓｈ０ｗ　ｔｈａｔ　ｔｈｅｒｅ　ｉｓ　ａ　ｇｏｏｄ　ａｇｒｅｅｍｅｎｔ　ｂｅｔｗｅｅｎ　ｃａｌｃｕｌａｔｉｏｎ　ｖａｌｕｅ　ａｎｄ　ｅｘｐｅｒｉｍｅｎｔｌ　ｖａａｌｕｅ・Ｔｈｅ　ｄ　ｅｌｏＤｅｄ　ｓｏｆｌｗａｒｅ　ｈａｓ　ｈｉｇｈ　ｃｏｍｐｕｔａｔｉｏｎａｌ　ｅｆｆｉｃｉｅｎｃｙ　ａｎｄ　ｃｏｖｅｒｓ　ａｌｌ　ｍｏｂｉｌｅ　ｃｒａｎｅ’ｓ　ｏｐｅｒａｔｉｎｇ　ｃａｓｅｓ・　ＫｅＹ　ｗｏｒｄｓ：ｍｏｂｉｌｅ　ｃｒａｎｅ；ｌｉｔｆｉｎｇ　ｐｅｒｆｏｒｍａｎｃｅ；ｐａｒａｍｅｔｅｒｉｚａｔｉｏｎ；ｆｉｎｉｔｅ　ｅｌｅｍｅｎｔ　ｍｅｔｈｏｄ；　ｗａｒｅ　ｄｅｖｅｌｏｐｍｅｎｔ　．　ｓｏｆｔ—　２．