徐澤兵　王忠

摘要：在如今這個(gè)信息爆炸的時(shí)代，我們要面對(duì)“信息過(guò)載”這一難題；以個(gè)性化推薦技術(shù)為核心的推薦系統(tǒng)有效的解決這一問(wèn)題，其中協(xié)同過(guò)濾算法是目前應(yīng)用最廣泛也是最成熟的個(gè)性化推薦技術(shù)?；诖?，本文提出一種基于SVD與層次聚類(lèi)中的BIRCH算法來(lái)實(shí)現(xiàn)協(xié)同過(guò)濾算法。該算法在MovieLens數(shù)據(jù)集上的實(shí)驗(yàn)數(shù)據(jù)表明該算法有效的提高了推薦的質(zhì)量。

關(guān)鍵詞：個(gè)性化推薦；SVD；BIRCH算法

中圖分類(lèi)號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2018）01-0130-02

最近幾年，協(xié)同過(guò)濾算法[1]是比較成功并具有代表性的推薦算法，目前協(xié)同過(guò)濾算法大致分為兩類(lèi)：一是基于內(nèi)存的協(xié)同過(guò)濾算法；二是基于模型的協(xié)同過(guò)濾算法。

本文針對(duì)數(shù)據(jù)的稀疏性、可擴(kuò)展性等問(wèn)題提出了基于奇異值分解與BIRCH層次聚類(lèi)算法[2]的協(xié)同過(guò)濾算法。并且使用物理學(xué)上的能量守恒定律來(lái)確定SVD在降維時(shí)保存盡可能多的信息。使用BIRCH聚類(lèi)算法縮小查詢(xún)最近鄰時(shí)的范圍。實(shí)驗(yàn)表明，本文算法能夠提高推薦質(zhì)量。

1 傳統(tǒng)的基于用戶(hù)的協(xié)同過(guò)濾算法

在傳統(tǒng)的基于用戶(hù)的協(xié)同過(guò)濾算法中，我們完成推薦的過(guò)程一般分為下面幾個(gè)步驟：第一：構(gòu)建評(píng)分矩陣：第二：計(jì)算相似度，確定K個(gè)最近鄰；第三：完成預(yù)測(cè)評(píng)分，實(shí)現(xiàn)推薦。因此我們完成的推薦的第一步就是對(duì)數(shù)據(jù)進(jìn)行初始化，構(gòu)建評(píng)分矩陣。

1.1 數(shù)據(jù)初始化

將用戶(hù)集及評(píng)分項(xiàng)目集合構(gòu)造出一個(gè)評(píng)分矩陣，其中代表有m個(gè)用戶(hù)，代表有n個(gè)項(xiàng)目，表示用戶(hù)對(duì)項(xiàng)目的評(píng)分值。

1.2 獲取最近鄰集合

基于用戶(hù)的協(xié)同過(guò)濾算法完成推薦功能的第二步是為目標(biāo)用戶(hù)找到最近鄰的集合，最近鄰集合的確定是通過(guò)計(jì)算相似度來(lái)確認(rèn)的，皮爾森相關(guān)系數(shù)在計(jì)算相似度時(shí)更加的準(zhǔn)確，設(shè)來(lái)表示用戶(hù)u與v之間的相似度，公式如下：

2 基于SVD與BIRCH層次聚類(lèi)的協(xié)同過(guò)濾算法

在本節(jié)中將對(duì)本文提出的改進(jìn)算法進(jìn)行詳細(xì)敘述，本算法的主要思想為：首先，通過(guò)奇異值分解對(duì)原始的用戶(hù)評(píng)分矩陣進(jìn)行預(yù)處理：構(gòu)造出用戶(hù)相關(guān)矩陣；其次，利用BIRCH算法進(jìn)行歸類(lèi)，形成K個(gè)用戶(hù)簇；之后根據(jù)目標(biāo)用戶(hù)確定目標(biāo)簇并確定最近鄰；最后實(shí)現(xiàn)top-N推薦。以下將詳細(xì)敘述該算法的過(guò)程：

2.1 構(gòu)造用戶(hù)相關(guān)矩陣

在利用SVD進(jìn)行降維時(shí)，所選擇的降維維數(shù)k很重要，在本文中我們將保存原始矩陣的多少能量定義為能量閾值s。我們確定了s的值之后，就可以反向確定維度值k。此能量閾值的值為對(duì)角矩陣的前k個(gè)奇異值的能量除以全部奇異值的能量的結(jié)果。

確定k值之后，我們就可以將對(duì)角矩陣只保留前k個(gè)奇異值形成新的對(duì)角矩陣，從中取前k列變成，從中取前k行變成，其中k遠(yuǎn)遠(yuǎn)小于m和n的值，這樣就達(dá)到了降維的目的。

經(jīng)過(guò)上面的一系列矩陣分解降維處理之后，我們得到了用戶(hù)特征矩陣，后面的分析都是基于此矩陣。

2.2 使用BIRCH算法對(duì)用戶(hù)矩陣進(jìn)行分類(lèi)

在經(jīng)過(guò)上一節(jié)的SVD處理之后我們得到用戶(hù)特征矩陣，為了更加高效的獲取到目標(biāo)用戶(hù)的最近鄰，使用BIRCH算法對(duì)該矩陣進(jìn)行聚類(lèi)。主要思想是：利用樹(shù)結(jié)構(gòu)幫助我們進(jìn)行快速的聚類(lèi)，一般把其稱(chēng)作聚類(lèi)特征樹(shù)（CFTree）。該樹(shù)的任一節(jié)點(diǎn)都是由若干個(gè)聚類(lèi)特征（CF）組成的。流程如下為：

（1）在內(nèi)存中構(gòu)建CF樹(shù)；

（2）以CF樹(shù)葉元項(xiàng)對(duì)應(yīng)的子簇為基礎(chǔ)，實(shí)現(xiàn)數(shù)據(jù)點(diǎn)的聚類(lèi)；

2.3 改進(jìn)算法的描述

綜合第二節(jié)的傳統(tǒng)協(xié)同過(guò)濾算法以及本節(jié)前面對(duì)SVD以及BIRCH算法的描述，我們可以對(duì)本文改進(jìn)算法進(jìn)行簡(jiǎn)要描述：

輸入：用戶(hù)-項(xiàng)目評(píng)分矩陣，目標(biāo)用戶(hù)；輸出：對(duì)目標(biāo)用戶(hù)進(jìn)行Top-N推薦。

（1）對(duì)用戶(hù)-項(xiàng)目矩陣進(jìn)行SVD降維處理，根據(jù)公式得到用戶(hù)特征矩陣；

（2）對(duì)用戶(hù)特征矩陣進(jìn)行BIRCH聚類(lèi)，然后確定和目標(biāo)用戶(hù)相似的簇；

（3）根據(jù)皮爾森相關(guān)系數(shù)確定最近鄰集合；

（4）對(duì)目標(biāo)用戶(hù)未評(píng)分的項(xiàng)目進(jìn)行評(píng)分；

（5）根據(jù)預(yù)測(cè)評(píng)分結(jié)果實(shí)現(xiàn)Top-N推薦。

3 實(shí)驗(yàn)結(jié)果及分析

本文采用的數(shù)據(jù)實(shí)驗(yàn)集為MovieLens數(shù)據(jù)集。該數(shù)據(jù)集中的信息包含了一共943個(gè)用戶(hù)對(duì)于1682部電影的十萬(wàn)條評(píng)分。評(píng)分值是1至5的整數(shù)，數(shù)字越高代表評(píng)分越高。

3.1 算法推薦質(zhì)量度量標(biāo)準(zhǔn)

平均絕對(duì)誤差（MAE）是常用的評(píng)判標(biāo)準(zhǔn)，其原理是計(jì)算用戶(hù)對(duì)項(xiàng)目的預(yù)測(cè)評(píng)分值與實(shí)際評(píng)分值之間的偏差。MAE的值越小，代表推薦的質(zhì)量越高。設(shè)預(yù)測(cè)評(píng)分集合為，實(shí)際評(píng)分集合為，公式如4-2所示：

3.2 實(shí)驗(yàn)結(jié)果及分析

在對(duì)用戶(hù)-項(xiàng)目矩陣進(jìn)行奇異值分解時(shí)，選擇適當(dāng)?shù)慕稻S維數(shù)很重要，過(guò)低會(huì)損失過(guò)多的信息量，過(guò)高的話(huà)失去降維的意義。通過(guò)實(shí)驗(yàn)當(dāng)選擇k為17時(shí)，MAE的值最低，推薦的性能最好。

為了驗(yàn)證改進(jìn)算法的性能，我們將該算法與knn算法以及基于SVD的推薦算法進(jìn)行比較，在取不同的近鄰個(gè)數(shù)的情況下各算法的推薦性能：

由圖1所示，當(dāng)我們的近鄰個(gè)數(shù)達(dá)到一定數(shù)目后，我們的改進(jìn)算法推薦效果更加高效。

4 結(jié)語(yǔ)

本文提出的基于SVD與BIRCH層次聚類(lèi)的協(xié)同過(guò)濾算法的優(yōu)勢(shì)有：第一，SVD對(duì)原始矩陣進(jìn)行降維處理，有效的解決了數(shù)據(jù)稀疏性的問(wèn)題；第二，BIRCH算法在求目標(biāo)用戶(hù)的最近鄰時(shí)，縮小了搜索范圍，有效提高算法運(yùn)行時(shí)間。當(dāng)然算法也有不足之處，例如當(dāng)數(shù)據(jù)量過(guò)大時(shí)，SVD算法的效率會(huì)有所降低，這也是之后論文的研究改進(jìn)方向。

參考文獻(xiàn)

[1]楊陽(yáng)，向陽(yáng)，熊磊.基于矩陣分解與用戶(hù)近鄰模型的協(xié)同過(guò)濾推薦算法[J].計(jì)算機(jī)應(yīng)用，2012，32（2）：395-398.

[2]蔣盛益，李霞.一種改進(jìn)的BIRCH聚類(lèi)算法[J].計(jì)算機(jī)應(yīng)用，2009，29（1）：293-296.