周張?zhí)m

摘 要：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是數(shù)據(jù)的一種存儲(chǔ)方式，它具有插入、刪除操作靈活的特性，可以很好地適應(yīng)數(shù)據(jù)變化。在分析協(xié)同過(guò)濾推薦算法數(shù)據(jù)對(duì)象特點(diǎn)及實(shí)現(xiàn)原理的基礎(chǔ)上，以十字鏈表、鄰接表為存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)了基于內(nèi)存的鏈?zhǔn)綌?shù)據(jù)存儲(chǔ)方法，并在此基礎(chǔ)上實(shí)現(xiàn)了一組操作，這些操作可以完成評(píng)分?jǐn)?shù)據(jù)創(chuàng)建、相似度計(jì)算、評(píng)分預(yù)測(cè)和推薦列表生成等功能。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及相關(guān)操作能方便地進(jìn)行功能擴(kuò)展，并可根據(jù)需要實(shí)現(xiàn)更為復(fù)雜的操作。

關(guān)鍵詞關(guān)鍵詞：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；協(xié)同過(guò)濾；興趣模型；個(gè)性化推薦

DOIDOI：10.11907/rjdk.162119

中圖分類(lèi)號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)文章編號(hào)：16727800（2016）011005904

1 協(xié)同過(guò)濾推薦算法

面對(duì)海量的數(shù)據(jù)信息，個(gè)性化推薦已成為用戶在互聯(lián)網(wǎng)中獲取感興趣內(nèi)容的一種重要途徑。通常，個(gè)性化推薦首先需從已知的用戶行為中獲得用戶興趣模型，然后預(yù)測(cè)用戶可能感興趣的其它行為，最后向用戶提供推薦。協(xié)同過(guò)濾推薦是個(gè)性化推薦中的一種重要方法，它依據(jù)用戶對(duì)項(xiàng)目的評(píng)分信息，而不依賴于推薦內(nèi)容本身，因而對(duì)復(fù)雜對(duì)象的推薦具有重要意義。

傳統(tǒng)的協(xié)同過(guò)濾推薦算法有基于用戶（Userbased）的協(xié)同過(guò)濾推薦[1]和基于項(xiàng)目（Itembased）的協(xié)同過(guò)濾推薦[2]?；谟脩舻膮f(xié)同過(guò)濾推薦算法的主要步驟為：首先，計(jì)算用戶和用戶之間的相似度；其次，利用相似度為目標(biāo)用戶尋找近鄰；然后，根據(jù)近鄰的評(píng)分來(lái)預(yù)測(cè)目標(biāo)用戶評(píng)分；最后，依據(jù)預(yù)測(cè)評(píng)分的高低產(chǎn)生推薦。基于項(xiàng)目的協(xié)同過(guò)濾推薦算法與之類(lèi)似，其計(jì)算項(xiàng)目與項(xiàng)目之間的相似性，尋找項(xiàng)目近鄰，并利用相似項(xiàng)目的評(píng)分來(lái)預(yù)測(cè)目標(biāo)用戶評(píng)分。從實(shí)現(xiàn)角度上看，兩者操作步驟相似。

通常，協(xié)同過(guò)濾推薦的數(shù)據(jù)集分為訓(xùn)練集和測(cè)試集兩部分。其中，訓(xùn)練集用來(lái)獲取用戶興趣模型，測(cè)試集用來(lái)預(yù)測(cè)。一般情況下，數(shù)據(jù)集來(lái)自用戶的評(píng)分行為，經(jīng)過(guò)預(yù)處理后按照一定格式生成一個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集。比如MovieLens數(shù)據(jù)集[3]即采用四元組形式存儲(chǔ)用戶對(duì)電影的評(píng)分，四元組的組成元素分別是user_id、item_id，rating和timestamp。MovieLens提供的數(shù)據(jù)集是常用的推薦算法測(cè)試數(shù)據(jù)集，本文也以此數(shù)據(jù)集作為數(shù)據(jù)對(duì)象。由于用戶對(duì)項(xiàng)目的評(píng)分常常是稀疏的，比如用戶能瀏覽并評(píng)分的商品往往十分有限。因此，在實(shí)現(xiàn)算法時(shí)要合理地考慮數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)。

2 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

在協(xié)同過(guò)濾推薦算法中需要存儲(chǔ)的數(shù)據(jù)對(duì)象包括：從訓(xùn)練集和測(cè)試集中讀取的用戶評(píng)分?jǐn)?shù)據(jù)、計(jì)算得到的用戶或項(xiàng)目的相似度數(shù)據(jù)、向用戶產(chǎn)生推薦的預(yù)測(cè)數(shù)據(jù)。

2.1 評(píng)分?jǐn)?shù)據(jù)存儲(chǔ)結(jié)構(gòu)

協(xié)同過(guò)濾推薦中，處理的數(shù)據(jù)對(duì)象是用戶對(duì)項(xiàng)目的評(píng)分。當(dāng)然，這些數(shù)據(jù)是經(jīng)過(guò)預(yù)處理的，比如去掉無(wú)效評(píng)分、采用統(tǒng)一的數(shù)據(jù)格式等。用戶評(píng)分?jǐn)?shù)據(jù)可看成一個(gè)評(píng)分矩陣，其中，行代表用戶，列代表項(xiàng)目，第i行第j列的元素aij代表用戶i對(duì)項(xiàng)目j的評(píng)分。評(píng)分?jǐn)?shù)據(jù)有兩種存儲(chǔ)方法，順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)。若采用順序的二維數(shù)組存儲(chǔ)，可以實(shí)現(xiàn)對(duì)數(shù)據(jù)元素aij的隨機(jī)存取。但對(duì)數(shù)組而言，主要的操作是查找和修改，不易進(jìn)行插入、刪除操作。另外，由于用戶對(duì)項(xiàng)目的評(píng)分是一個(gè)稀疏矩陣，最好對(duì)數(shù)據(jù)進(jìn)行壓縮處理。因此，采用十字鏈表作為數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)不僅可以實(shí)現(xiàn)數(shù)據(jù)壓縮，還能利用指針[4]靈活地進(jìn)行結(jié)點(diǎn)的插入、刪除操作?；谑宙湵韀5]存儲(chǔ)的數(shù)據(jù)類(lèi)型定義如下：

（1）評(píng)分結(jié)點(diǎn)類(lèi)型定義：

typedef struct rateNode{

int user_id； //用戶id

int item_id； //項(xiàng)目id

int rating； //評(píng)分

struct rateNode *rownext； //行指針

struct rateNode *colnext； //列指針

}rNode，*rNodeLink；

（2）用戶項(xiàng)目類(lèi)型定義：

typedef struct UserItemRateList{

int id； //用戶id或項(xiàng)目id

float rAvg；//用戶或項(xiàng)目平均評(píng)分

struct rateNode *first；

}UIRate；

（3）U個(gè)用戶的用戶表，I個(gè)項(xiàng)目的項(xiàng)目表可定義為：

UIRate User[U]，Item[I]；

2.2 相似度存儲(chǔ)結(jié)構(gòu)

首先，分析用戶（或項(xiàng)目）之間的相似度特點(diǎn)。在協(xié)同過(guò)濾推薦算法中，計(jì)算用戶（或項(xiàng)目）的相似度有很多方法，方法不同得到的相似度值也不同。常見(jiàn)的相似度計(jì)算方法有余弦相似性、調(diào)整的余弦相似性和相關(guān)相似性。余弦相似性的取值范圍為[0，1]，調(diào)整的余弦相似性和相關(guān)相似性的取值范圍為[-1，1]。因此，用戶（或項(xiàng)目）的相似度值為一個(gè)實(shí)數(shù)，一般定義為float即可。為了滿足應(yīng)用需求，以用戶相似度為例，假設(shè)用戶數(shù)量為U，若計(jì)算出所有用戶之間的相似度，則相似度矩陣大小為U*U。然而，不是每個(gè)用戶之間都能計(jì)算出相似度值，若兩個(gè)用戶之間沒(méi)有共同評(píng)分項(xiàng)目，無(wú)論采用以上哪一種相似度計(jì)算方法都無(wú)法計(jì)算。因此，用戶相似度矩陣也可能是稀疏的。更重要的是，為了能依據(jù)相似度快速地查找到用戶（或項(xiàng)目）的近鄰，最好為每個(gè)用戶（或項(xiàng)目）建立一個(gè)相似度表，并按相似度值從大到小降序排列?？刹捎妙?lèi)似圖的鄰接表的存儲(chǔ)方式，為每一個(gè)用戶（或項(xiàng)目）建立一個(gè)鏈表，鏈表中的結(jié)點(diǎn)包含近鄰用戶（或項(xiàng)目）號(hào)id、相似度值data以及指向下一個(gè)結(jié)點(diǎn)的指針next。其中，結(jié)點(diǎn)按相似度值降序排列。

（1）用戶（或項(xiàng)目）相似度結(jié)點(diǎn)定義如下：

typedef struct Node{

int id； //用戶或項(xiàng)目id

float data； //用戶或項(xiàng)目相似度值

struct Node *next； //指向下一個(gè)相似度結(jié)點(diǎn)的指針

}Node；

（2）用戶或項(xiàng)目相似度表定義如下：

typedef struct List{

int id； //用戶或項(xiàng)目id

struct Node *first； //用戶或項(xiàng)目相似度鏈表的頭指針

}List；

（3）U個(gè)用戶，I個(gè)項(xiàng)目的相似度表定義為：

List UserSim [U]， ItemSim [I]；

2.3 用戶推薦存儲(chǔ)結(jié)構(gòu)

為了實(shí)現(xiàn)推薦，需生成一個(gè)用戶推薦表，推薦表中包含向用戶推薦的項(xiàng)目以及對(duì)該項(xiàng)目的預(yù)測(cè)評(píng)分。同樣，為方便查找，在存儲(chǔ)時(shí)最好也按預(yù)測(cè)評(píng)分的高低排序。因此，推薦表的存儲(chǔ)方式可以和相似度表相同，都為L(zhǎng)ist類(lèi)型。其中，每個(gè)用戶有一個(gè)按預(yù)測(cè)評(píng)分降序排列的推薦鏈表，鏈表結(jié)點(diǎn)包含項(xiàng)目號(hào)id、預(yù)測(cè)評(píng)分值data以及指向下一個(gè)結(jié)點(diǎn)的指針next，結(jié)點(diǎn)類(lèi)型與相似度結(jié)點(diǎn)類(lèi)型相同，為Node類(lèi)型。另外，推薦表中的用戶和對(duì)應(yīng)的項(xiàng)目信息來(lái)自于測(cè)試集中的數(shù)據(jù)，因此還需一個(gè)測(cè)試表來(lái)存儲(chǔ)從測(cè)試集中讀取的用戶和待測(cè)項(xiàng)目信息。由于測(cè)試表存儲(chǔ)的數(shù)據(jù)是產(chǎn)生推薦表時(shí)要讀取的內(nèi)容，因此測(cè)試表也定義為L(zhǎng)ist類(lèi)型。U個(gè)用戶的推薦表和測(cè)試表可定義為：

List PreRem[U]， TestRem[U]；

2.4 協(xié)同過(guò)濾推薦類(lèi)型定義

為實(shí)現(xiàn)協(xié)同過(guò)濾推薦，需要包含的數(shù)據(jù)信息有：用戶數(shù)、項(xiàng)目數(shù)、記錄數(shù)、用戶表、項(xiàng)目表、用戶或項(xiàng)目相似度表、測(cè)試表和推薦表。因此，定義協(xié)同過(guò)濾推薦類(lèi)型CFR如下：

typedef struct CFR{

int UserNum； //用戶數(shù)

int ItemNum； //項(xiàng)目數(shù)

int RecordNum；//訓(xùn)練集記錄數(shù)

int RecordNum_t； //測(cè)試集記錄數(shù)

UIRate *User； // 用戶表

UIRate *Item； // 項(xiàng)目表

List *Sim； // 用戶或項(xiàng)目相似度表

List *TestRem； //測(cè)試表

List *PreRem； //推薦表

}CFR；

3 算法設(shè)計(jì)

協(xié)同過(guò)濾推薦算法3個(gè)主要步驟分別是計(jì)算相似度、尋找近鄰和預(yù)測(cè)評(píng)分。獲取用戶近鄰的方法有多種[6]，如基于前k個(gè)近鄰的計(jì)算方法、基于閾值的計(jì)算方法等。

在分析協(xié)同過(guò)濾推薦的數(shù)據(jù)特點(diǎn)并確定相應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)后，設(shè)計(jì)算法詳細(xì)實(shí)現(xiàn)步驟如下：首先，讀入已格式化的用戶評(píng)分訓(xùn)練集，生成以十字鏈表形式存儲(chǔ)的用戶項(xiàng)目評(píng)分矩陣；然后，利用某種相似度計(jì)算方法（如余弦相似性）計(jì)算用戶（或項(xiàng)目）之間的相似度，為用戶（或項(xiàng)目）創(chuàng)建一個(gè)按相似度值從高到低排序的最近鄰表，以便快速找到與用戶（或項(xiàng)目）相似的近鄰（如前k個(gè)近鄰）；再次，讀入測(cè)試集用戶數(shù)據(jù)，創(chuàng)建測(cè)試表；最后，預(yù)測(cè)測(cè)試表中用戶對(duì)項(xiàng)目的評(píng)分，并按預(yù)測(cè)評(píng)分的高低生成用戶推薦表。算法流程如圖1所示。

4 算法實(shí)現(xiàn)

在實(shí)現(xiàn)中，由于采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，因此多數(shù)為基于指針的查找、插入和刪除操作。其中，主要操作的算法用C語(yǔ)言描述如下：

（1） CreateCrossLink（）：創(chuàng)建十字鏈表。讀入用戶評(píng)分訓(xùn)練集，創(chuàng)建以十字鏈表形式存儲(chǔ)的用戶項(xiàng)目評(píng)分矩陣。算法描述如下：

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

FILE *fp；

rNode *p，*q；

if（?。╢p=fopen（str，"r"））） {printf（"Cant open the base file！n"）；exit（-1）；} //讀入訓(xùn)練集

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中插入一個(gè)結(jié)點(diǎn)。在指定表L中，以降序方式向L[i]元素所在鏈表中插入一個(gè)Node類(lèi)型的結(jié)點(diǎn)。其中，結(jié)點(diǎn)id號(hào)為j，值data為val。例如，若List為用戶相似度表，則表示在用戶i所在的相似度鏈表中插入一個(gè)編號(hào)為j（即用戶j）且值為val的結(jié)點(diǎn)。算法描述如下：

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

//將結(jié)點(diǎn)（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 （）：創(chuàng)建用戶或項(xiàng)目的相似度表。相似度計(jì)算方法有多種，一般只要兩個(gè)用戶或項(xiàng)目之間有共同評(píng)分即可計(jì)算出相似度值。這里給出采用余弦相似性計(jì)算用戶之間相似度的算法，算法描述如下：

int CreateUINeiLink_Consin（CFR &R）{

//以余弦相似性計(jì)算用戶與用戶之間的相似度，并以降序方式插入用戶的相似度表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）； //將計(jì)算出的相似度值suv插入用戶i所在的相似度鏈表R.Sim[i]中

InsertNodeDesc（j+1，i+1，suv，R.Sim）；} }}//將計(jì)算出的相似度值suv插入用戶j所在的相似度鏈表R.Sim[j]中

return 1；}

由于用戶和項(xiàng)目相似度計(jì)算方法類(lèi)似，若計(jì)算項(xiàng)目之間的相似度，只需在以上操作中將若干成員變量由用戶改為項(xiàng)目即可，如將UserNum改為ItemNum，User[i]改為Item[i]，指針p->rownext改為p->colnext等。

（4）CreateRemList（）：讀入測(cè)試數(shù)據(jù)集，創(chuàng)建測(cè)試表R.TestRem。讀入測(cè)試數(shù)據(jù)集，將所需預(yù)測(cè)的用戶及其對(duì)應(yīng)項(xiàng)目插入到測(cè)試列表R.TestRem中。例如，若要向用戶i推薦，在R.TestRem[i]中創(chuàng)建一個(gè)測(cè)試鏈表，其中結(jié)點(diǎn)包含讀入的項(xiàng)目號(hào)和評(píng)分。若未評(píng)分，則初始評(píng)分值為0。若要檢測(cè)推薦效果，則在此讀入用戶的真實(shí)評(píng)分，可以方便地實(shí)現(xiàn)同預(yù)測(cè)評(píng)分的比較。

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

FILE *fp；

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

for（int k=0；k

fscanf（fp，"%d %d %d"，&i，&j，&r）；//若沒(méi)有評(píng)分，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對(duì)項(xiàng)目j的預(yù)測(cè)評(píng)分。利用用戶（或項(xiàng)目）的相似度表R.Sim預(yù)測(cè)用戶i對(duì)項(xiàng)目j的評(píng)分。在R.Sim[i]的相似度鏈表中取前n個(gè)結(jié)點(diǎn)，讀取這些結(jié)點(diǎn)中的用戶評(píng)分并進(jìn)行計(jì)算，如求平均值。當(dāng)然，也可以根據(jù)需要采用其它計(jì)算方法，只需在取值后的計(jì)算部分稍作修改即可。這里給出采用用戶前n個(gè)最近鄰的平均值計(jì)算評(píng)分的算法。算法描述如下：

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（）：生成用戶推薦表。調(diào)用某種近鄰計(jì)算方法預(yù)測(cè)用戶評(píng)分，然后將預(yù)測(cè)評(píng)分按降序方式插入相應(yīng)的推薦表R.PreRem中，輸出R.RreRem，即可得到用戶的推薦項(xiàng)目及其對(duì)應(yīng)的預(yù)測(cè)評(píng)分。這里給出為用戶生成推薦表的算法，其中，以用戶前n個(gè)最近鄰對(duì)項(xiàng)目的平均評(píng)分計(jì)算預(yù)測(cè)評(píng)分，即調(diào)用PreUI_Average（）方法。算法描述如下：

int PreRemList（int n，CFR &R）{

//取用戶前n個(gè)近鄰來(lái)預(yù)測(cè)評(píng)分

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）；//預(yù)測(cè)用戶i對(duì)項(xiàng)目j的評(píng)分

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

return 1；}

在上述基于鏈?zhǔn)降拇鎯?chǔ)結(jié)構(gòu)中，用十字鏈表存儲(chǔ)用戶項(xiàng)目評(píng)分矩陣，以鄰接表形式存儲(chǔ)用戶表、項(xiàng)目表、測(cè)試表和推薦表，此存儲(chǔ)結(jié)構(gòu)使一系列相關(guān)操作的實(shí)現(xiàn)和擴(kuò)展變得相對(duì)容易。另外，在用戶表和項(xiàng)目表的類(lèi)型定義中，預(yù)留了用戶或項(xiàng)目的平均分UIRate.rAvg，可以在需要時(shí)計(jì)算并存入以便能直接使用，如當(dāng)采用調(diào)整的余弦相似性計(jì)算相似度時(shí)即可用到?；阪?zhǔn)降拇鎯?chǔ)結(jié)構(gòu)具有插入、刪除操作簡(jiǎn)單靈活的特點(diǎn)，可以很好地適應(yīng)數(shù)據(jù)變化。

參考文獻(xiàn)：

[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] 譚浩強(qiáng). C語(yǔ)言程序設(shè)計(jì)[M]. 第2版.北京：清華大學(xué)出版社， 1999.

[5] 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）[M]. 北京：清華大學(xué)出版社， 2007.

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

（責(zé)任編輯：黃 健）