《基于链式存储结构的协同过滤推荐算法设计与实现.pdf》由会员分享，可在线阅读，更多相关《基于链式存储结构的协同过滤推荐算法设计与实现.pdf（3页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、基于链式存储结构的协同过滤推荐算法设计与实现摘摘 要：链式存储结构是数据的一种存储方式，它具有插入、删要：链式存储结构是数据的一种存储方式，它具有插入、删除操作灵活的特性，可以很好地适应数据变化。在分析协同过滤推除操作灵活的特性，可以很好地适应数据变化。在分析协同过滤推荐算法数据对象特点及实现原理的基础上，以十字链表、邻接表为荐算法数据对象特点及实现原理的基础上，以十字链表、邻接表为存储结构设计了基于内存的链式数据存储方法，并在此基础上实现存储结构设计了基于内存的链式数据存储方法，并在此基础上实现了一组操作，这些操作可以完成评分数据创建、相似度计算、评分了一组操作，这些操作可以完成评分数据创建
2、、相似度计算、评分预测和推荐列表生成等功能。链式存储结构及相关操作能方便地进预测和推荐列表生成等功能。链式存储结构及相关操作能方便地进行功能扩展，并可根据需要实现更为复杂的操作。行功能扩展，并可根据需要实现更为复杂的操作。关键词关键词：链式存储结构；协同过滤；兴趣模型；个性化关键词关键词：链式存储结构；协同过滤；兴趣模型；个性化推荐推荐doidoidoidoi：10.11907/rjdk.16211910.11907/rjdk.162119文献标识码：文献标识码：a a 文章编号文章编号：文章编号文章编号：1672780016727800（20162016）011005904011005904
3、1 1 协同过滤推荐算法协同过滤推荐算法面对海量的数据信息，个性化推荐已成为用户在互联网中获取面对海量的数据信息，个性化推荐已成为用户在互联网中获取感兴趣内容的一种重要途径。通常，个性化推荐首先需从已知的用感兴趣内容的一种重要途径。通常，个性化推荐首先需从已知的用户行为中获得用户兴趣模型，然后预测用户可能感兴趣的其它行为，户行为中获得用户兴趣模型，然后预测用户可能感兴趣的其它行为，最后向用户提供推荐。协同过滤推荐是个性化推荐中的一种重要方最后向用户提供推荐。协同过滤推荐是个性化推荐中的一种重要方法，它依据用户对项目的评分信息，而不依赖于推荐内容本身，因法，它依据用户对项目的评分信息，而不依赖于
4、推荐内容本身，因而对复杂对象的推荐具有重要意义。而对复杂对象的推荐具有重要意义。传统的协同过滤推荐算法有基于用户（传统的协同过滤推荐算法有基于用户（userbaseduserbased）的协同过）的协同过滤推荐滤推荐11 和基于项目（和基于项目（itembaseditembased）的协同过滤推荐）的协同过滤推荐22。基于用户。基于用户的协同过滤推荐算法的主要步骤为：首先，计算用户和用户之间的的协同过滤推荐算法的主要步骤为：首先，计算用户和用户之间的相似度；其次，利用相似度为目标用户寻找近邻；然后，根据近邻相似度；其次，利用相似度为目标用户寻找近邻；然后，根据近邻的评分来预测目标用户评分；最后
5、，依据预测评分的高低产生推荐。的评分来预测目标用户评分；最后，依据预测评分的高低产生推荐。基于项目的协同过滤推荐算法与之类似，其计算项目与项目之间的基于项目的协同过滤推荐算法与之类似，其计算项目与项目之间的相似性，寻找项目近邻，并利用相似项目的评分来预测目标用户评相似性，寻找项目近邻，并利用相似项目的评分来预测目标用户评分。从实现角度上看，两者操作步骤相似。分。从实现角度上看，两者操作步骤相似。通常，协同过滤推荐的数据集分为训练集和测试集两部分。其通常，协同过滤推荐的数据集分为训练集和测试集两部分。其中，训练集用来获取用户兴趣模型，测试集用来预测。一般情况下，中，训练集用来获取用户兴趣模型，测
6、试集用来预测。一般情况下，数据集来自用户的评分行为，经过预处理后按照一定格式生成一个数据集来自用户的评分行为，经过预处理后按照一定格式生成一个标准数据集。比如标准数据集。比如 movielensmovielens 数据集数据集33 即采用四元组形式存储用户即采用四元组形式存储用户对电影的评分，四元组的组成元素分别是对电影的评分，四元组的组成元素分别是 user_iduser_id、item_iditem_id，ratingrating和和 timestamptimestamp。movielensmovielens 提供的数据集是常用的推荐算法提供的数据集是常用的推荐算法测试数据集，本文也以此数
7、据集作为数据对象。由于用户对项目的测试数据集，本文也以此数据集作为数据对象。由于用户对项目的评分常常是稀疏的，比如用户能浏览并评分的商品往往十分有限。评分常常是稀疏的，比如用户能浏览并评分的商品往往十分有限。因此，在实现算法时要合理地考虑数据存储结构。因此，在实现算法时要合理地考虑数据存储结构。2 2 数据结构设计数据结构设计在协同过滤推荐算法中需要存储的数据对象包括：从训练集和在协同过滤推荐算法中需要存储的数据对象包括：从训练集和测试集中读取的用户评分数据、计算得到的用户或项目的相似度数测试集中读取的用户评分数据、计算得到的用户或项目的相似度数据、向用户产生推荐的预测数据。据、向用户产生推荐
8、的预测数据。2.12.1评分数据存储结构评分数据存储结构协同过滤推荐中，处理的数据对象是用户对项目的评分。当然，协同过滤推荐中，处理的数据对象是用户对项目的评分。当然，这些数据是经过预处理的，比如去掉无效评分、采用统一的数据格这些数据是经过预处理的，比如去掉无效评分、采用统一的数据格式等。用户评分数据可看成一个评分矩阵，其中，行代表用户，列式等。用户评分数据可看成一个评分矩阵，其中，行代表用户，列代表项目，第代表项目，第 i i行第行第 j j列的元素列的元素 aijaij代表用户代表用户 i i对项目对项目 j j的评分。评分的评分。评分数据有两种存储方法，顺序存储或链式存储。若采用顺序的二
9、维数数据有两种存储方法，顺序存储或链式存储。若采用顺序的二维数组存储，可以实现对数据元素组存储，可以实现对数据元素 aijaij的随机存取。但对数组而言，主要的随机存取。但对数组而言，主要的操作是查找和修改，不易进行插入、删除操作。另外，由于用户的操作是查找和修改，不易进行插入、删除操作。另外，由于用户对项目的评分是一个稀疏矩阵，最好对数据进行压缩处理。因此，对项目的评分是一个稀疏矩阵，最好对数据进行压缩处理。因此，采用十字链表作为数据存储结构不仅可以实现数据压缩，还能利用采用十字链表作为数据存储结构不仅可以实现数据压缩，还能利用指针指针44 灵活地进行结点的插入、删除操作。基于十字链表灵活地
10、进行结点的插入、删除操作。基于十字链表55 存储的存储的数据类型定义如下：数据类型定义如下：（1 1）评分结点类型定义：）评分结点类型定义：typedef struct ratenodetypedef struct ratenodeint user_idint user_id；/用户用户 ididint item_idint item_id；/项目项目 ididint ratingint rating；/评分评分struct ratenode*rownextstruct ratenode*rownext；/行指针行指针struct ratenode*colnextstruct ratenode
11、*colnext；/列指针列指针rnodernode，*rnodelink*rnodelink；（2 2）用户项目类型定义：）用户项目类型定义：typedef struct useritemratelisttypedef struct useritemratelistint idint id；/用户用户 idid或项目或项目 ididfloat ravgfloat ravg；/用户或项目平均评分用户或项目平均评分struct ratenode*firststruct ratenode*first；uirateuirate；（3 3）u u 个用户的用户表，个用户的用户表，i i个项目的项目表可
12、定义为：个项目的项目表可定义为：uirate useruuirate useru，itemiitemi；2.22.2相似度存储结构相似度存储结构首先，分析用户（或项目）之间的相似度特点。在协同过滤推首先，分析用户（或项目）之间的相似度特点。在协同过滤推荐算法中，计算用户（或项目）的相似度有很多方法，方法不同得荐算法中，计算用户（或项目）的相似度有很多方法，方法不同得到的相似度值也不同。常见的相似度计算方法有余弦相似性、调整到的相似度值也不同。常见的相似度计算方法有余弦相似性、调整的余弦相似性和相关相似性。余弦相似性的取值范围为的余弦相似性和相关相似性。余弦相似性的取值范围为00，11，调整，调
13、整的余弦相似性和相关相似性的取值范围为的余弦相似性和相关相似性的取值范围为-1-1，11。因此，用户（或。因此，用户（或项目）的相似度值为一个实数，一般定义为项目）的相似度值为一个实数，一般定义为 floatfloat即可。为了满足应即可。为了满足应用需求，以用户相似度为例，假设用户数量为用需求，以用户相似度为例，假设用户数量为 u u，若计算出所有用户，若计算出所有用户之间的相似度，则相似度矩阵大小为之间的相似度，则相似度矩阵大小为 u*uu*u。然而，不是每个用户之间。然而，不是每个用户之间都能计算出相似度值，若两个用户之间没有共同评分项目，无论采都能计算出相似度值，若两个用户之间没有共同
14、评分项目，无论采用以上哪一种相似度计算方法都无法计算。因此，用户相似度矩阵用以上哪一种相似度计算方法都无法计算。因此，用户相似度矩阵也可能是稀疏的。更重要的是，为了能依据相似度快速地查找到用也可能是稀疏的。更重要的是，为了能依据相似度快速地查找到用户（或项目）的近邻，最好为每个用户（或项目）建立一个相似度户（或项目）的近邻，最好为每个用户（或项目）建立一个相似度表，并按相似度值从大到小降序排列。可采用类似图的邻接表的存表，并按相似度值从大到小降序排列。可采用类似图的邻接表的存储方式，为每一个用户（或项目）建立一个链表，链表中的结点包储方式，为每一个用户（或项目）建立一个链表，链表中的结点包含近邻用户（或项目）号含近邻用户（或项目）号 idid、相似度值、相似度值 datadata 以及指向下一个结点的以及指向下一个结点的指针指针 nextnext。其中，结点按相似度值降序排列。其中，结点按相似度值降序排列。