基于十字鏈表與三元組表的稀疏矩陣壓縮存儲(chǔ)實(shí)例研究

周張?zhí)m

摘要：十字鏈表和帶行鏈接信息的三元組表是稀疏矩陣的兩種壓縮存儲(chǔ)方法。十字鏈表為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，帶行鏈接信息的三元組表為順序存儲(chǔ)結(jié)構(gòu)。在MovieLens數(shù)據(jù)集上設(shè)計(jì)了分別采用十字鏈表和帶行鏈接信息的三元組表對(duì)以用戶為行、項(xiàng)目為列、用戶評(píng)分為矩陣元的稀疏矩陣進(jìn)行壓縮存儲(chǔ)，并在這兩種存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)用戶相似度計(jì)算算法。通過測(cè)試分析和比較了兩種不同的壓縮存儲(chǔ)方法在創(chuàng)建及相似度計(jì)算上的執(zhí)行效率，并探討了各自的特點(diǎn)及適用條件。

關(guān)鍵詞關(guān)鍵詞：稀疏矩陣；十字鏈表；三元組表；壓縮存儲(chǔ)

DOIDOI：10.11907/rjdk.171845

中圖分類號(hào)：TP302

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

0引言

矩陣是科學(xué)與工程計(jì)算問題中研究的數(shù)學(xué)對(duì)象。在高階矩陣中，可能存在很多相同值或零值的矩陣元，對(duì)這些矩陣元的存儲(chǔ)造成存儲(chǔ)空間的浪費(fèi)。因此，可以對(duì)矩陣進(jìn)行壓縮存儲(chǔ)，以節(jié)省存儲(chǔ)空間，達(dá)到提高存儲(chǔ)利用率的目的。在算法實(shí)現(xiàn)中，選擇的存儲(chǔ)結(jié)構(gòu)不同，執(zhí)行效率也將不同。對(duì)不同矩陣存儲(chǔ)方法的特點(diǎn)進(jìn)行分析和比較，有助于根據(jù)不同的實(shí)際應(yīng)用，有針對(duì)性地選擇更為合適的存儲(chǔ)結(jié)構(gòu)，以此提高矩陣運(yùn)算及其它相關(guān)操作的運(yùn)行效率。

1稀疏矩陣及存儲(chǔ)

若一個(gè)m行n列矩陣中的零元素有t個(gè)，零元素個(gè)數(shù)t與矩陣元總數(shù)m×n的比值稱為稀疏因子，一般認(rèn)為若稀疏因子不大于0.05，則此矩陣為稀疏矩陣。設(shè)矩陣有10行10列，即總共100個(gè)元素，若其中零元素有95個(gè)，而非零元素僅有5個(gè)，則此矩陣為稀疏矩陣。在存儲(chǔ)稀疏矩陣時(shí)，可以采用非壓縮存儲(chǔ)和壓縮存儲(chǔ)兩種方式。非壓縮存儲(chǔ)使用二維數(shù)組，比如，設(shè)10行10列的稀疏矩陣M的矩陣元均為整數(shù)，則可以使用二維數(shù)組存儲(chǔ)該矩陣M，數(shù)組的定義用C語言[1]描述如下：

int a[10][10]；

其中，a[0][0]代表稀疏矩陣M第1行第1列元素，a[i][j]代表第i+1行第j+1列元素。由于數(shù)組是從下標(biāo)0開始，因此使用二維數(shù)組時(shí)下標(biāo)與邏輯上的行號(hào)和列號(hào)相差1。為了操作方便，也可以從a[1][1]開始存儲(chǔ)第1行第1列元素，即定義為：

int a[11][11]；

這種定義方式可以使邏輯上的行、列號(hào)與二維數(shù)組的下標(biāo)保持一致，采用這種方式存儲(chǔ)矩陣時(shí)所需存儲(chǔ)空間要求更大。

從操作上看，二維數(shù)組的非壓縮存儲(chǔ)方式按行和列存取數(shù)據(jù)元素非常方便。然而，在稀疏矩陣中，大量零元素的存儲(chǔ)不僅會(huì)浪費(fèi)存儲(chǔ)空間，而且與零元素相關(guān)的運(yùn)算也會(huì)在一定程度上降低計(jì)算總體效率。因此，在實(shí)際應(yīng)用中，對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)很有必要。壓縮存儲(chǔ)只存儲(chǔ)非零矩陣元，有順序存儲(chǔ)和非順序存儲(chǔ)兩種。其中，順序存儲(chǔ)可使用帶行鏈接信息的三元組表，而非順序存儲(chǔ)可采用十字鏈表。

2壓縮存儲(chǔ)

2.1三元組及表示

壓縮存儲(chǔ)只存儲(chǔ)矩陣中的非零元。在矩陣中，除了存儲(chǔ)非零元素的值，還要存儲(chǔ)該元素所在的行號(hào)和列號(hào)。三元組表示法以（行號(hào)，列號(hào)，值）形式存儲(chǔ)矩陣中的一個(gè)非零元素，比如，（1，1，5）表示第1行第1列元素值為5。設(shè)矩陣元素值的類型為ElemType，則存儲(chǔ)一個(gè)非零元三元組的結(jié)構(gòu)體類型定義用C語言描述如下：

struct Triple{

int i，j；

ElemType e；

}；

三元組可存儲(chǔ)稀疏矩陣中所有非零元的值及其行、列號(hào)。但是，從三元組中不能得到整個(gè)稀疏矩陣行數(shù)、列數(shù)及非零元個(gè)數(shù)等信息。因此，還要對(duì)存儲(chǔ)整個(gè)稀疏矩陣的三元組表進(jìn)行定義。帶行鏈接信息的三元組表又稱為行邏輯鏈接順序表[2]，其結(jié)構(gòu)體類型定義用C語言描述如下：

struct TripleMatrix{

struct Triple *data；

int *rops；

int m，n，t；

}；

其中，以三元組形式表示的非零元存儲(chǔ)在數(shù)組data[]中，每行的第1個(gè)非零元在三元組表中的起始位置存放在數(shù)組rops[]中，兩個(gè)數(shù)組的存儲(chǔ)空間在初始化時(shí)分配。m、n、t分別代表稀疏矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù)。

2.2十字鏈表及表示

十字鏈表是稀疏矩陣的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。十字鏈表對(duì)矩陣的每一行建立一個(gè)鏈表，行鏈表的頭指針存放在其對(duì)應(yīng)行的一維數(shù)組中。同樣，為矩陣的每一列建立一個(gè)鏈表，列鏈表的頭指針也存放在其對(duì)應(yīng)列的一維數(shù)組中。為了實(shí)現(xiàn)十字鏈表，首先將需要存儲(chǔ)的非零元素封裝成一個(gè)結(jié)點(diǎn)。其中，結(jié)點(diǎn)包含5個(gè)域，除了行號(hào)、列號(hào)和值3個(gè)數(shù)據(jù)域外，還有兩個(gè)指針域，分別指向該元素所在行及所在列的下一個(gè)非零元素。設(shè)稀疏矩陣的數(shù)據(jù)元素類型為ElemType，則十字鏈表中存儲(chǔ)非零元素結(jié)點(diǎn)的結(jié)構(gòu)體類型定義如下：

struct CrossLNode{

int i，j；

ElemType e；

struct CrossLNode *rownext， *colnext；

}；

其中，rownext和colnext指針分別指向該元素所在行和所在列的下一個(gè)非零元素。對(duì)整個(gè)稀疏矩陣而言，除了存儲(chǔ)非零元，還要記錄整個(gè)矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù)以及兩個(gè)分別存儲(chǔ)所有行鏈表和列鏈表頭指針的一維數(shù)組。因此，十字鏈表的結(jié)構(gòu)體類型定義如下：

struct CrossLinkList{

struct CrossLNode *rowhead， *columnhead；

int m， n， t；

}；

在十字鏈表定義中，m、n、t分別代表稀疏矩陣的行數(shù)、列數(shù)和非零元素個(gè)數(shù)。rowhead和columnhead指針分別指向存儲(chǔ)所有行鏈表頭指針和所有列鏈表頭指針的一維數(shù)組的首地址。endprint

3實(shí)例測(cè)試

3.1數(shù)據(jù)集

協(xié)同過濾推薦[36]是一種廣泛使用的推薦方法，傳統(tǒng)的協(xié)同過濾推薦算法不依賴于推薦內(nèi)容本身，而根據(jù)用戶對(duì)項(xiàng)目的評(píng)分產(chǎn)生推薦。其中，用戶對(duì)項(xiàng)目的評(píng)分可以看作是一個(gè)以用戶為行、項(xiàng)目為列的矩陣，矩陣元aij表示用戶i對(duì)項(xiàng)目j的評(píng)分。在實(shí)際應(yīng)用中，用戶有興趣并且產(chǎn)生評(píng)分的項(xiàng)目相對(duì)于所有項(xiàng)目而言極其有限。因此，用戶項(xiàng)目評(píng)分矩陣往往是一個(gè)稀疏矩陣。借助協(xié)同過濾推薦中常用的MovieLens[7]數(shù)據(jù)集作為數(shù)據(jù)對(duì)象，通過計(jì)算用戶相似度，分析、對(duì)比分別采用帶行鏈接信息的三元組表和十字鏈表對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)時(shí)各自的執(zhí)行效率。

本文使用的MovieLens數(shù)據(jù)集中，用戶數(shù)943個(gè)、項(xiàng)目數(shù)1 682個(gè)。用戶評(píng)分記錄包括：用戶號(hào)、項(xiàng)目號(hào)、評(píng)分和時(shí)間戳。其中，訓(xùn)練集有u1.base、u2.base、u3.base、u4.base和u5.base 5個(gè)數(shù)據(jù)文件，每個(gè)文件中評(píng)分記錄為80 000條，每一條評(píng)分記錄以（user_id，item_id，rating，timestamp）的形式存儲(chǔ)。分析此數(shù)據(jù)可以得出，以用戶對(duì)項(xiàng)目評(píng)分為矩陣元的矩陣稀疏因子為80 000/（943×1 682）≈0.05，即此矩陣可認(rèn)為是一個(gè)稀疏矩陣。

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

在基于用戶的協(xié)同過濾推薦中，首先利用評(píng)分矩陣計(jì)算用戶與用戶之間的相似度，從而產(chǎn)生目標(biāo)用戶的近鄰，再利用這些用戶近鄰對(duì)目標(biāo)用戶未評(píng)分項(xiàng)目進(jìn)行評(píng)分預(yù)測(cè)，最后根據(jù)預(yù)測(cè)評(píng)分的高低向目標(biāo)用戶推薦。用戶相似度計(jì)算是基于用戶的協(xié)同過濾推薦算法的重要步驟，本文采用余弦相似度計(jì)算用戶之間的相似度值。為了比較帶行鏈接信息的三元組表和十字鏈表壓縮存儲(chǔ)效率，分別在這兩種存儲(chǔ)結(jié)構(gòu)上設(shè)計(jì)和實(shí)現(xiàn)用戶相似度計(jì)算算法并進(jìn)行了測(cè)試。

（1）帶行鏈接信息的三元組表測(cè)試算法。采用帶行鏈接信息的三元組表壓縮存儲(chǔ)評(píng)分矩陣并計(jì)算用戶相似度的算法步驟如下：首先，初始化TripleMatrix類型的帶行鏈接信息的三元組表M；然后，創(chuàng)建帶行鏈接信息的三元組表M。讀入評(píng)分記錄文件u1.base，將其中每一條評(píng)分記錄的行號(hào)、列號(hào)和值依次存儲(chǔ)到M.data中；再計(jì)算用戶之間的相似度，根據(jù)余弦相似度計(jì)算公式利用行鏈接信息M.rpos在三元組表中讀取所需用戶評(píng)分，并計(jì)算有共同評(píng)分的用戶之間的相似度值；最后，重復(fù)以上步驟分別測(cè)試u2.base、u3.base、u4.base和u5.base 4個(gè)數(shù)據(jù)文件。

（2）十字鏈表測(cè)試算法。采用十字鏈表存儲(chǔ)評(píng)分矩陣并計(jì)算用戶相似度的算法步驟與帶行鏈接信息的三元組表類似，但由于該方法采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，因此在算法實(shí)現(xiàn)上主要是指針操作。首先，初始化并創(chuàng)建CrossLinkList類型的十字鏈表T；然后，讀入評(píng)分記錄文件u1.base，每讀取一條記錄，用malloc動(dòng)態(tài)申請(qǐng)一個(gè)CrossLNode類型的節(jié)點(diǎn)，并存儲(chǔ)相應(yīng)的行、列和值，同時(shí)將該結(jié)點(diǎn)掛到其行所在的鏈表及其列所在的鏈表中；接著，計(jì)算用戶之間的相似度，根據(jù)余弦相似度計(jì)算公式在創(chuàng)建的十字鏈表中讀取所需節(jié)點(diǎn)的用戶評(píng)分，并計(jì)算有共同評(píng)分的用戶之間的相似度值；最后，重復(fù)以上步驟分別測(cè)試u2.base、u3.base、u4.base和u5.base 4個(gè)數(shù)據(jù)文件。

3.3運(yùn)行測(cè)試

在配置為處理器Inter（R） Core（TM） i54210，內(nèi)存4G，64位操作系統(tǒng)的電腦上使用visual C++6.0編程并運(yùn)行測(cè)試。測(cè)試中，使用計(jì)時(shí)函數(shù)clock（）計(jì)算運(yùn)行時(shí)間。由于在不同時(shí)刻運(yùn)行程序，計(jì)算的運(yùn)行時(shí)間會(huì)有所偏差，為此將每個(gè)數(shù)據(jù)文件連續(xù)運(yùn)行5次，取平均值作為最終執(zhí)行時(shí)間。用訓(xùn)練數(shù)據(jù)集u1至u5分別測(cè)試兩種存儲(chǔ)結(jié)構(gòu)。其中，創(chuàng)建十字鏈表和帶行鏈接信息的三元組表所需時(shí)間如圖1所示，計(jì)算用戶相似度的運(yùn)行時(shí)間如圖2所示，創(chuàng)建并計(jì)算總執(zhí)行時(shí)間如圖3所示。

3.4結(jié)果分析

由圖1可知，創(chuàng)建十字鏈表所用時(shí)間大于帶行鏈接信息的三元組表用時(shí)。分析十字鏈表創(chuàng)建過程可知，每讀入一條評(píng)分記錄，動(dòng)態(tài)申請(qǐng)一個(gè)結(jié)點(diǎn)的存儲(chǔ)單元，不僅要將評(píng)分存儲(chǔ)到結(jié)點(diǎn)中，還需要將該節(jié)點(diǎn)插入到其所在行和所在列的鏈表中。相對(duì)于直接加到表尾的三元組表存儲(chǔ)的順序存儲(chǔ)而言所需時(shí)間要多。當(dāng)然，由于在MovieLens數(shù)據(jù)集中，所有評(píng)分記錄已按行和列從小到大順序排序，因此當(dāng)結(jié)點(diǎn)插入時(shí)只需要插入到所在行和列鏈表的表尾即可。但是若輸入的評(píng)分記錄沒有按行和列排序，在創(chuàng)建十字鏈表時(shí)還需要從行或列的第一個(gè)結(jié)點(diǎn)開始查找合適的插入位置，再實(shí)現(xiàn)節(jié)點(diǎn)插入。這樣所需運(yùn)行時(shí)間更多，實(shí)際測(cè)試發(fā)現(xiàn)，其平均運(yùn)行時(shí)間要多近3倍。若采用三元組表存儲(chǔ)，在創(chuàng)建時(shí)需對(duì)記錄進(jìn)行按行和列排序，插入節(jié)點(diǎn)時(shí)還要為空出插入位置而移動(dòng)元素，則所需創(chuàng)建時(shí)間會(huì)更多。

當(dāng)非零元素分別以十字鏈表和三元組表存儲(chǔ)，采用余弦相似度計(jì)算方法計(jì)算所有用戶之間的相似度。其中，三元組表采用行邏輯連接的順序表，可按行訪問。從圖2中得到，使用十字鏈表計(jì)算相似度所需時(shí)間小于采用三元組表存儲(chǔ)用時(shí)。這說明，當(dāng)十字鏈表和帶行鏈接信息的三元組表創(chuàng)建后，在同等條件下計(jì)算用戶相似度時(shí)，十字鏈表訪問數(shù)據(jù)元素并實(shí)現(xiàn)計(jì)算的效率要比三元組表高。從總運(yùn)行時(shí)間看，十字鏈表雖然在創(chuàng)建用時(shí)比三元組表要多，但由于計(jì)算相似度所用時(shí)間少，因此總執(zhí)行時(shí)間要比三元組表少，兩者總運(yùn)行時(shí)間對(duì)比如圖3所示。

將十字鏈表、帶行鏈接信息的三元組表和非壓縮的二維數(shù)組的創(chuàng)建和計(jì)算相似度的總運(yùn)行時(shí)間進(jìn)行比較，三者的總運(yùn)行時(shí)間如表1所示?？梢钥闯?，無論是十字鏈表還是帶行鏈接信息的三元組表，在壓縮后由于去掉了大量零元素運(yùn)算，因此所需運(yùn)行時(shí)間均大幅減少，運(yùn)行效率明顯提高。

在存儲(chǔ)空間方面，使用非壓縮的二維數(shù)組、壓縮的十字鏈表和帶行鏈接信息的三元組表所需存儲(chǔ)空間如表2所示。表中數(shù)據(jù)以943個(gè)用戶、1 682個(gè)項(xiàng)目，形成943行1 682列的稀疏矩陣的數(shù)據(jù)集為例，其中，評(píng)分記錄為80 000條。從表中結(jié)果可知，二維數(shù)組所需存儲(chǔ)空間最多，總共需要943*1 682*4=6 344 504個(gè)字節(jié)，而且必須是連續(xù)的存儲(chǔ)單元。十字鏈表所需存儲(chǔ)空間其次，其中包含存儲(chǔ)非零元的非連續(xù)存儲(chǔ)空間80 000*20=1 600 000個(gè)字節(jié)，存儲(chǔ)十字鏈表所有行鏈表頭指針的連續(xù)存儲(chǔ)空間943*4=3 772個(gè)字節(jié)和存儲(chǔ)所有列鏈表頭指針的連續(xù)存儲(chǔ)空間1 682*4=6 728個(gè)字節(jié)，即十字鏈表總存儲(chǔ)空間為1 610 500個(gè)字節(jié)。帶行鏈接信息的三元組表所需存儲(chǔ)空間最少，其中存儲(chǔ)矩陣非零元的連續(xù)存儲(chǔ)空間80 000*12=960 000個(gè)字節(jié)，存儲(chǔ)每行在三元組表中起始位置的連續(xù)的存儲(chǔ)空間943*4=3 772個(gè)字節(jié)，即總共需要963 772個(gè)字節(jié)的存儲(chǔ)空間。另外，在三元組表和十字鏈表中還需要存儲(chǔ)矩陣行數(shù)、列數(shù)和非零元個(gè)數(shù)等其它少量的輔助存儲(chǔ)空間。endprint

測(cè)試發(fā)現(xiàn)，無論使用十字鏈表還是帶行鏈接信息的三元組表對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，由于只需存儲(chǔ)非零元素，因此對(duì)存儲(chǔ)空間的壓縮效果明顯，尤其是帶行鏈接信息的三元組表，所需存儲(chǔ)空間較少。然而，由于三元組是順序存儲(chǔ)的，因此，存儲(chǔ)空間必須是連續(xù)的存儲(chǔ)單元。相對(duì)于帶行鏈接信息的三元組表，十字鏈表所需存儲(chǔ)空間更多，但所需連續(xù)存儲(chǔ)空間少，因?yàn)榇鎯?chǔ)非零元素的存儲(chǔ)空間是動(dòng)態(tài)申請(qǐng)的，因此不必是連續(xù)的存儲(chǔ)單元。

從用戶相似度的運(yùn)行時(shí)間上看，相比非壓縮的二維數(shù)組存儲(chǔ)方法，利用十字鏈表和帶行鏈接信息的三元組表壓縮存儲(chǔ)后計(jì)算所需運(yùn)行時(shí)間較少。這是因?yàn)槭÷粤藢?duì)大量零元素的存儲(chǔ)，同時(shí)也就免除了大量有關(guān)零元素的運(yùn)算，而這些針對(duì)零元素的運(yùn)算在余弦相似度計(jì)算中并無必要。因此，經(jīng)過壓縮存儲(chǔ)后，對(duì)程序運(yùn)行時(shí)間的提高也有很大幫助。在本例測(cè)試中，十字鏈表比帶行鏈接信息的三元組表的創(chuàng)建所用時(shí)間多，但是在計(jì)算相似度時(shí)所用時(shí)間要少，而總運(yùn)行時(shí)間優(yōu)于三元組表存儲(chǔ)方法。這是由于十字鏈表雖然采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，但可以按行和列訪問矩陣元，而在行邏輯鏈接的三元組順序表中，雖然每行的第一個(gè)非零元素的起始位置已存儲(chǔ)，也可以實(shí)現(xiàn)按行訪問，但在本例中所用時(shí)間還是比十字鏈表略多。

4結(jié)語

測(cè)試分析表明，十字鏈表和帶行鏈接信息的三元組表都可以較好地實(shí)現(xiàn)對(duì)稀疏矩陣的壓縮存儲(chǔ)，并且在運(yùn)行時(shí)間和存儲(chǔ)空間上比非壓縮存儲(chǔ)效率均有明顯提高。在運(yùn)行時(shí)間方面，若輸入數(shù)據(jù)已按行和列排序，在創(chuàng)建時(shí)只需在表尾插入，則三元組表的順序存儲(chǔ)結(jié)構(gòu)所用創(chuàng)建時(shí)間比十字鏈表少。然而，創(chuàng)建時(shí)若輸入數(shù)據(jù)沒有經(jīng)過排序處理，則十字鏈表的結(jié)點(diǎn)插入需要先找到插入位置。同樣，帶行鏈接信息的三元組表需為待插入元素空出位置而移動(dòng)元素，兩者在創(chuàng)建上的運(yùn)行時(shí)間都將比非壓縮的二維數(shù)組多。運(yùn)算時(shí)間上，本例中十字鏈表按行訪問并完成相似度計(jì)算的運(yùn)行時(shí)間比帶行鏈接信息的三元組表要少。由于十字鏈表順序存儲(chǔ)了行鏈表和列鏈表的頭指針，相比僅按行訪問的帶行鏈接信息的三元組表，十字鏈表不僅可以按行訪問，還可以根據(jù)需要按列訪問，使用更加靈活。在存儲(chǔ)空間方面，三元組表的順序存儲(chǔ)結(jié)構(gòu)所需存儲(chǔ)空間較少，但要求存儲(chǔ)單元必須連續(xù)，而且容量固定，不易擴(kuò)充。十字鏈表中非零元的存儲(chǔ)單元是動(dòng)態(tài)申請(qǐng)的，需要的連續(xù)存儲(chǔ)空間較少，同時(shí)插入、刪除操作靈活，可以很好地適應(yīng)數(shù)據(jù)變化。

基于十字鏈表和三元組表的稀疏矩陣壓縮存儲(chǔ)特點(diǎn)及用戶相似度計(jì)算效率的對(duì)比與分析表明，這兩種對(duì)稀疏矩陣壓縮存儲(chǔ)的方法各有所長(zhǎng)，在實(shí)際應(yīng)用中可依據(jù)對(duì)數(shù)據(jù)的存儲(chǔ)容量和操作特點(diǎn)選擇更為合適的存儲(chǔ)結(jié)構(gòu)，從而實(shí)現(xiàn)計(jì)算效率最優(yōu)化。

參考文獻(xiàn)參考文獻(xiàn)：

[1]譚浩強(qiáng).C語言程序設(shè)計(jì)[M].第2版.北京：清華大學(xué)出版社，1999.

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

[3]GOLDBERG D，NICHOLS D，OKI B M，et al. Using collaborative filtering to weave an information tapestry[J]. Comm ACM，1992，35（12）：6170.

[4]KONSTAN J A，MILLER B N，MALTZ D，et al.GroupLens： applying collaborative filtering to usenet news[J]. Comm ACM，1997，40（3）：7787.

[5]LINDEN G，SMITH B，YORK J.Amazon.com recommendations： itemtoitem collaborative filtering[J]. IEEE Internet Computing，2003，7（l）：7680.

[6]SCHAFER J，KONSTAN J，RIEDLL J.Recommender systems in Ecommerce[C].Proc ACM ECommerce，1999：158166.

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

責(zé)任編輯（責(zé)任編輯：孫娟）endprint