基于链式存储结构的协同过滤推荐算法设计与实现

周张兰

摘 要：链式存储结构是数据的一种存储方式，它具有插入、删除操作灵活的特性，可以很好地适应数据变化。在分析协同过滤推荐算法数据对象特点及实现原理的基础上，以十字链表、邻接表为存储结构设计了基于内存的链式数据存储方法，并在此基础上实现了一组操作，这些操作可以完成评分数据创建、相似度计算、评分预测和推荐列表生成等功能。链式存储结构及相关操作能方便地进行功能扩展，并可根据需要实现更为复杂的操作。

关键词关键词：链式存储结构；协同过滤；兴趣模型；个性化推荐

DOIDOI：10.11907/rjdk.162119

中图分类号：TP312

文献标识码：A 文章编号文章编号：16727800（2016）011005904

1 协同过滤推荐算法

面对海量的数据信息，个性化推荐已成为用户在互联网中获取感兴趣内容的一种重要途径。通常，个性化推荐首先需从已知的用户行为中获得用户兴趣模型，然后预测用户可能感兴趣的其它行为，最后向用户提供推荐。协同过滤推荐是个性化推荐中的一种重要方法，它依据用户对项目的评分信息，而不依赖于推荐内容本身，因而对复杂对象的推荐具有重要意义。

传统的协同过滤推荐算法有基于用户（Userbased）的协同过滤推荐[1]和基于项目（Itembased）的协同过滤推荐[2]。基于用户的协同过滤推荐算法的主要步骤为：首先，计算用户和用户之间的相似度；其次，利用相似度为目标用户寻找近邻；然后，根据近邻的评分来预测目标用户评分；最后，依据预测评分的高低产生推荐。基于项目的协同过滤推荐算法与之类似，其计算项目与项目之间的相似性，寻找项目近邻，并利用相似项目的评分来预测目标用户评分。从实现角度上看，两者操作步骤相似。

通常，协同过滤推荐的数据集分为训练集和测试集两部分。其中，训练集用来获取用户兴趣模型，测试集用来预测。一般情况下，数据集来自用户的评分行为，经过预处理后按照一定格式生成一个标准数据集。比如MovieLens数据集[3]即采用四元组形式存储用户对电影的评分，四元组的组成元素分别是user_id、item_id，rating和timestamp。MovieLens提供的数据集是常用的推荐算法测试数据集，本文也以此数据集作为数据对象。由于用户对项目的评分常常是稀疏的，比如用户能浏览并评分的商品往往十分有限。因此，在实现算法时要合理地考虑数据存储结构。

2 数据结构设计

在协同过滤推荐算法中需要存储的数据对象包括：从训练集和测试集中读取的用户评分数据、计算得到的用户或项目的相似度数据、向用户产生推荐的预测数据。

2.1 评分数据存储结构

协同过滤推荐中，处理的数据对象是用户对项目的评分。当然，这些数据是经过预处理的，比如去掉无效评分、采用统一的数据格式等。用户评分数据可看成一个评分矩阵，其中，行代表用户，列代表项目，第i行第j列的元素aij代表用户i对项目j的评分。评分数据有两种存储方法，顺序存储或链式存储。若采用顺序的二维数组存储，可以实现对数据元素aij的随机存取。但对数组而言，主要的操作是查找和修改，不易进行插入、删除操作。另外，由于用户对项目的评分是一个稀疏矩阵，最好对数据进行压缩处理。因此，采用十字链表作为数据存储结构不仅可以实现数据压缩，还能利用指针[4]灵活地进行结点的插入、删除操作。基于十字链表[5]存储的数据类型定义如下：

（1）评分结点类型定义：

typedef struct rateNode{

int user_id； //用户id

int item_id； //项目id

int rating； //评分

struct rateNode *rownext； //行指针

struct rateNode *colnext； //列指针

}rNode，*rNodeLink；

（2）用户项目类型定义：

typedef struct UserItemRateList{

int id； //用户id或项目id

float rAvg；//用户或项目平均评分

struct rateNode *first；

}UIRate；

（3）U个用户的用户表，I个项目的项目表可定义为：

UIRate User[U]，Item[I]；

2.2 相似度存储结构

首先，分析用户（或项目）之间的相似度特点。在协同过滤推荐算法中，计算用户（或项目）的相似度有很多方法，方法不同得到的相似度值也不同。常见的相似度计算方法有余弦相似性、调整的余弦相似性和相关相似性。余弦相似性的取值范围为[0，1]，调整的余弦相似性和相关相似性的取值范围为[-1，1]。因此，用户（或项目）的相似度值为一个实数，一般定义为float即可。为了满足应用需求，以用户相似度为例，假设用户数量为U，若计算出所有用户之间的相似度，则相似度矩阵大小为U*U。然而，不是每个用户之间都能计算出相似度值，若两个用户之间没有共同评分项目，无论采用以上哪一种相似度计算方法都无法计算。因此，用户相似度矩阵也可能是稀疏的。更重要的是，为了能依据相似度快速地查找到用户（或项目）的近邻，最好为每个用户（或项目）建立一个相似度表，并按相似度值从大到小降序排列。可采用类似图的邻接表的存储方式，为每一个用户（或项目）建立一个链表，链表中的结点包含近邻用户（或项目）号id、相似度值data以及指向下一个结点的指针next。其中，结点按相似度值降序排列。

（1）用户（或项目）相似度结点定义如下：

typedef struct Node{

int id； //用户或项目id

float data； //用户或项目相似度值

struct Node *next； //指向下一个相似度结点的指针

}Node；

（2）用户或项目相似度表定义如下：

typedef struct List{

int id； //用户或项目id

struct Node *first； //用户或项目相似度链表的头指针

}List；

（3）U个用户，I个项目的相似度表定义为：

List UserSim [U]， ItemSim [I]；

2.3 用户推荐存储结构

为了实现推荐，需生成一个用户推荐表，推荐表中包含向用户推荐的项目以及对该项目的预测评分。同样，为方便查找，在存储时最好也按预测评分的高低排序。因此，推荐表的存储方式可以和相似度表相同，都为List类型。其中，每个用户有一个按预测评分降序排列的推荐链表，链表结点包含项目号id、预测评分值data以及指向下一个结点的指针next，结点类型与相似度结点类型相同，为Node类型。另外，推荐表中的用户和对应的项目信息来自于测试集中的数据，因此还需一个测试表来存储从测试集中读取的用户和待测项目信息。由于测试表存储的数据是产生推荐表时要读取的内容，因此测试表也定义为List类型。U个用户的推荐表和测试表可定义为：

List PreRem[U]， TestRem[U]；

2.4 协同过滤推荐类型定义

为实现协同过滤推荐，需要包含的数据信息有：用户数、项目数、记录数、用户表、项目表、用户或项目相似度表、测试表和推荐表。因此，定义协同过滤推荐类型CFR如下：

typedef struct CFR{

int UserNum； //用户数

int ItemNum； //项目数

int RecordNum；//训练集记录数

int RecordNum_t； //测试集记录数

UIRate *User； // 用户表

UIRate *Item； // 项目表

List *Sim； // 用户或项目相似度表

List *TestRem； //测试表

List *PreRem； //推荐表

}CFR；

3 算法设计

协同过滤推荐算法3个主要步骤分别是计算相似度、寻找近邻和预测评分。获取用户近邻的方法有多种[6]，如基于前k个近邻的计算方法、基于阈值的计算方法等。

在分析协同过滤推荐的数据特点并确定相应的链式存储结构后，设计算法详细实现步骤如下：首先，读入已格式化的用户评分训练集，生成以十字链表形式存储的用户项目评分矩阵；然后，利用某种相似度计算方法（如余弦相似性）计算用户（或项目）之间的相似度，为用户（或项目）创建一个按相似度值从高到低排序的最近邻表，以便快速找到与用户（或项目）相似的近邻（如前k个近邻）；再次，读入测试集用户数据，创建测试表；最后，预测测试表中用户对项目的评分，并按预测评分的高低生成用户推荐表。算法流程如图1所示。

4 算法实现

在实现中，由于采用链式存储结构，因此多数为基于指针的查找、插入和删除操作。其中，主要操作的算法用C语言描述如下：

（1） CreateCrossLink（）：创建十字链表。读入用户评分训练集，创建以十字链表形式存储的用户项目评分矩阵。算法描述如下：

int CreateCrossLink（char str[20]，CFR &R）{

FILE *fp；

rNode *p，*q；

if（！（fp=fopen（str，"r"））） {printf（"Cant open the base file！n"）；exit（-1）；} //读入训练集

for（k=0；k

fscanf（fp，"%d %d %d"，&i，&j，&r）；

if（i<1||i>R.UserNum||j<1||j>R.ItemNum） return 0；

p=（rNode*）malloc（sizeof（rNode））；

if（！p） exit（-1）；

p->user_id=i；p->item_id=j；p->rating=r；

if（R.User[i-1].first==NULL||R.User[i-1].first->item_id>j）{

p->rownext=R.User[i-1].first；R.User[i-1].first=p；}

else{ for（q=R.User[i-1].first；q->rownext&&q->rownext->item_idrownext）；

p->rownext=q->rownext；q->rownext=p；}

if（R.Item[j-1].first==NULL||R.Item[j-1].first->item_id>j）{

p->colnext=R.Item[j-1].first；R.Item[j-1].first=p；}

else { for（q=R.Item[j-1].first；q->colnext&&q->colnext->user_idcolnext）；

p->colnext=q->colnext；q->colnext=p；} }

return 1；}

（2）InsertNodeDesc（）：按降序在指定表List中插入一个结点。在指定表L中，以降序方式向L[i]元素所在链表中插入一个Node类型的结点。其中，结点id号为j，值data为val。例如，若List为用户相似度表，则表示在用户i所在的相似度链表中插入一个编号为j（即用户j）且值为val的结点。算法描述如下：

int InsertNodeDesc（int i，int j，float val，List *L）{

//将结点（j，val）按val值降序插入L[i]的链表中

Node *p，*q；

p=（Node *）malloc（sizeof（Node））；

if（！p） exit（-1）；

p->id=j；p->data=val；

if（L[i-1].first==NULL||L[i-1].first->data

p->next=L[i-1].first；L[i-1].first=p；}

else {for（q=L[i-1].first；q->next&&q->next->data>=val；q=q->next）；

p->next=q->next；q->next=p；}

return 1；}

（3）CreateUINeiLink （）：创建用户或项目的相似度表。相似度计算方法有多种，一般只要两个用户或项目之间有共同评分即可计算出相似度值。这里给出采用余弦相似性计算用户之间相似度的算法，算法描述如下：

int CreateUINeiLink_Consin（CFR &R）{

//以余弦相似性计算用户与用户之间的相似度，并以降序方式插入用户的相似度表R.Sim中

float suv，su，sv；

rNode *p，*q；

for（i=0；i

for（j=i+1；j

suv=0；su=0；sv=0； p=R.User[i].first； q=R.User[j].first；

while（p&&q）{

if（p->item_id==q->item_id）{

suv=suv+p->rating*q->rating；

su=su+p->rating*p->rating；sv=sv+q->rating*q->rating；

p=p->rownext；q=q->rownext；}

else if（p->item_iditem_id）{

su=su+p->rating*p->rating； p=p->rownext；}

else{ sv=sv+q->rating*q->rating； q=q->rownext；}}

while（p）{su=su+p->rating*p->rating； p=p->rownext；}

while（q）{sv=sv+q->rating*q->rating； q=q->rownext；}

if（su&&sv&&suv） {

suv=suv/（sqrt（su）*sqrt（sv））；

InsertNodeDesc（i+1，j+1，suv，R.Sim）； //将计算出的相似度值suv插入用户i所在的相似度链表R.Sim[i]中

InsertNodeDesc（j+1，i+1，suv，R.Sim）；} }}//将计算出的相似度值suv插入用户j所在的相似度链表R.Sim[j]中

return 1；}

由于用户和项目相似度计算方法类似，若计算项目之间的相似度，只需在以上操作中将若干成员变量由用户改为项目即可，如将UserNum改为ItemNum，User[i]改为Item[i]，指针p->rownext改为p->colnext等。

（4）CreateRemList（）：读入测试数据集，创建测试表R.TestRem。读入测试数据集，将所需预测的用户及其对应项目插入到测试列表R.TestRem中。例如，若要向用户i推荐，在R.TestRem[i]中创建一个测试链表，其中结点包含读入的项目号和评分。若未评分，则初始评分值为0。若要检测推荐效果，则在此读入用户的真实评分，可以方便地实现同预测评分的比较。

int CreateRemList（char str[20]，CFR &R）{

FILE *fp；

if（！（fp=fopen（str，"r"））） {printf（"Cant open the file！n"）；exit（-1）；}

for（int k=0；k

fscanf（fp，"%d %d %d"，&i，&j，&r）；//若没有评分，r值为0

if（i<1||i>R.UserNum||j<1||j>R.ItemNum） return 0；

InsertUNodeDesc（i，j，r，R.TestRem）；}

return 1；}

（5）PreUI_Average（）：返回用户i对项目j的预测评分。利用用户（或项目）的相似度表R.Sim预测用户i对项目j的评分。在R.Sim[i]的相似度链表中取前n个结点，读取这些结点中的用户评分并进行计算，如求平均值。当然，也可以根据需要采用其它计算方法，只需在取值后的计算部分稍作修改即可。这里给出采用用户前n个最近邻的平均值计算评分的算法。算法描述如下：

float PreUI_Average（int i，int j，int n，CFR &R）{

Node *p； rNode *q；

p=R.Sim[i-1].first；

if（！p） return 0；

for（；p&&countnext）{

for（k=p->id，q=R.User[k-1].first；q！=NULL；q=q->rownext）{

if（q->item_id==j）{

sum=sum+q->rating；

count++；}}}

if（count==n） return sum/count；

else return 0； }

（6）PreRemList（）：生成用户推荐表。调用某种近邻计算方法预测用户评分，然后将预测评分按降序方式插入相应的推荐表R.PreRem中，输出R.RreRem，即可得到用户的推荐项目及其对应的预测评分。这里给出为用户生成推荐表的算法，其中，以用户前n个最近邻对项目的平均评分计算预测评分，即调用PreUI_Average（）方法。算法描述如下：

int PreRemList（int n，CFR &R）{

//取用户前n个近邻来预测评分

Node *p； float rp；

for（i=0；i

for（p=R.TestRem[i].first；p！=NULL；p=p->next） {

j=p->id；

rp=PreUI_Average（i+1，j，n，R）；//预测用户i对项目j的评分

if（rp）{ InsertNodeDesc（i+1，j，rp，R.PreRem）；}}}

return 1；}

在上述基于链式的存储结构中，用十字链表存储用户项目评分矩阵，以邻接表形式存储用户表、项目表、测试表和推荐表，此存储结构使一系列相关操作的实现和扩展变得相对容易。另外，在用户表和项目表的类型定义中，预留了用户或项目的平均分UIRate.rAvg，可以在需要时计算并存入以便能直接使用，如当采用调整的余弦相似性计算相似度时即可用到。基于链式的存储结构具有插入、删除操作简单灵活的特点，可以很好地适应数据变化。

参考文献：

[1] SEHAFER J，KONSTAN J，REDLL J. Recomrnender systems in E-commerce[C]. Proc ACM E-Commerce，1999：158166.

[2] SARWAR B，KARYPIS G，KONSTAN J，et al. Itembased collaborative filtering recommendation algorithms[C]. Proc 10th Conf International World Wide Web， 2001：285295.

[3] MovieLens[EB/OL].http：//grouplens.org/datasets/.

[4] 谭浩强. C语言程序设计[M]. 第2版.北京：清华大学出版社， 1999.

[5] 严蔚敏，吴伟民. 数据结构（C语言版）[M]. 北京：清华大学出版社， 2007.

[6] HERLOCKER J L，KONSTAN J A，BOREHERS A， et al. An algorithmic framework for performing collaborative filtering[C].Proc ACM SIGIR， 1999.

（责任编辑：黄 健）