基于子空間聚類的協同過濾推薦算法

王英博，韓國淼，王銘澤

1.遼寧工程技術大學 創新實踐學院，遼寧 阜新 123000

2.遼寧工程技術大學 軟件學院，遼寧 葫蘆島 125105

3.南寧學院 會計學院，南寧 530200

隨著社會信息化進程的加快以及大數據時代的到來，互聯網產生的數據量也在逐漸增多，為了幫助用戶在海量數據中找到自身需要的數據，大量研究者和學者對相關方案進行了探索，由此推動了推薦技術的發展，廣泛成功地應用于電子商務、視頻網站以及社交網絡等各個領域[1]。并且它也逐漸成為了各個網絡平臺必不可少的核心部分，力求為用戶提供最優的決策支撐與信息服務，個性化推薦不需要用戶提供詳細的需求，而是僅僅根據用戶的興趣愛好以及歷史需求來向用戶推薦感興趣的信息和商品。

推薦算法主要有基于協同過濾的推薦、基于內容的推薦以及基于關聯規則的推薦。其中，基于協同過濾的推薦算法是推薦系統中應用最為廣泛和成功的推薦算法，根據用戶項目評分矩陣，尋找與目標用戶有相似偏好的其他用戶，即為目標用戶的最近鄰居，根據最近鄰居進行項目評分預測，進而形成推薦列表。傳統的協同過濾推薦算法是在整個用戶空間中搜索目標用戶的最近鄰居，這明顯非常耗時，以及也存在尋找的鄰居不合理的情況，進而導致推薦質量和效果差等問題[2]。

針對上述情況，很多研究學者提出了改進的協同過濾推薦算法。陳建瑞等[3]提出了基于雙層網絡的動態聚類協同過濾推薦算法，其基于用戶和物品的屬性信息建立用戶層和物品層網絡，并結合層次聚類算法來改進推薦算法，進而提高推薦質量。張文龍等[4]利用用戶歷史的交互學習中學習用戶偏好，提出了基于雙重最相關注意力網絡的協同過濾推薦算法。唐澤坤等[5]考慮用戶模型的數據密度、距離以及用戶活躍度，并結合改進的Canopy聚類來改進推薦算法。顧明星等[6]將KMeans++算法與協同過濾算法相結合，并改進用戶間的相似性計算方法，以此來提高推薦算法的效率和質量。高仰等[7]提出了融合知識圖譜和短期偏好的推薦算法，其將知識圖譜的三元組關系引入到推薦算法中，改善了推薦算法的性能。李維乾等[8]提出了一種多屬性條件受限的波爾茲曼機協同過濾模型，也使推薦效果得到了一定的提升。王永貴等[9]提出一種優化聚類的協同過濾算法，其利用花朵授粉算法來優化K均值聚類算法，以此來增強聚類效果，改善推薦質量。Tsai等[10]提出了一種聚類集成的協同過濾算法，其將K-Means和SOM算法集成在一起來改善推薦算法的性能。綜上所述，由于傳統的基于用戶的協同過濾算法主要存在冷啟動和數據稀疏性兩個主要缺點，所以，所有的改進算法基本都是針對這兩方面進行優化。很多學者都針對數據稀疏性的缺點提出了自己的改進方法，通過對上述文獻的閱讀，針對其改進的方法主要有以下幾種：（1）通過KMeans等聚類算法對其進行聚類，以尋求降低數據的稀疏性。（2）融合用戶偏好以及信任關系來緩解數據稀疏性。（3）利用填充算法緩解數據稀疏性。（4）通過自動編碼器構建神經網絡協同過濾模型。當面對數據高維問題時，目前的改進方法大多數是通過SVD、PCA等算法對數據降維，以此來處理該問題。在利用K-Means等聚類算法來優化推薦算法時，通常都要考慮聚類簇數，不同的類簇數獲得的推薦效果不同。其次，在利用降維算法解決數據的高維問題時，算法的時間復雜度也會隨之增加。

本文針對數據的稀疏性和高維性對推薦算法性能影響的問題，提出了一種基于子空間聚類的協同過濾推薦算法，該算法通過構建用戶在Interested、Uninterested以及NN-interested三種類別下的項目子空間來尋找用戶的最近鄰居，然后利用項目子空間為目標用戶繪制鄰居用戶樹。聚類過程和子空間的構造過程是在用戶離線階段完成，當用戶進入時，就會直接在線為其提供推薦列表，這個是其優勢之一，此外，提出了一種新的用戶相似度計算方法。實驗驗證表明，本文提出的算法在一定程度上能夠提升推薦算法的性能。

1 傳統協同過濾推薦算法

傳統協同過濾算法的基本步驟是：首先利用已有的用戶歷史行為數據信息，構建用戶-項目評分矩陣，然后通過相似度計算公式計算用戶之間的相似度，選取相似度較高的用戶作為目標用戶的近鄰集，最終在進行評分預測后按照TOP-N原則對用戶進行推薦[11]。

1.1 構建用戶項目評分矩陣

構建用戶項目評分矩陣R m×n，在此矩陣行中有m個用戶，用U表示，U={u1,u2,…,u m}，矩陣列中有n個項目，用I表示，I={i1,i2,…,i n}，R ij表示用戶i對項目j的實際評分，若用戶i對用戶j未評分，則Rij為0，用戶項目評分矩陣公式如下所示：

1.2 用戶評分相似性計算

用戶評分的相似性計算以用戶項目評分矩陣為基礎，將評分矩陣中的每一行的評分向量來表示用戶的實際興趣。所以，計算用戶評分的相似性實質上就是計算用戶評分向量之間的距離[12]。傳統的協同過濾算法中通常使用的計算相似性的方法有3種，分別為Pearson相關系數、Jaccard系數以及余弦相似性系數，但是最常用的是皮爾遜相似度計算方法。計算公式如下：

在獲得用戶a與所有用戶的相似度后，將相似度最高的前h個用戶作為其近鄰集，最后應用評分預測公式得出最終的預測評分。預測評分公式為：

其中，P a,j表示用戶a對項目j的預測評分，Q表示項目a的近鄰集。

2 基于子空間聚類的協同過濾推薦算法

基于用戶的協同過濾推薦算法在面對稀疏的數據集時，推薦質量會明顯降低，并且隨著大數據時代的到來，高維數據也越來越多，其也成為推薦算法所面臨的挑戰之一。在協同過濾推薦算法中，由于數據稀疏性，具有相似偏好的用戶被認為是相似用戶或鄰居用戶，反之，沒有相似偏好的用戶則不會被當作鄰居用戶。但是以后其也會有因為其他中間用戶而使其成為鄰居用戶的可能[13]。其次，在傳統或一些其他改進的協同過濾推薦算法中，鄰居的數量或聚類數是變量，是需要通過調整來進行手動確定的。為此，本文提出了基于子空間聚類的協同過濾推薦算法。該算法利用新的數據表示方法，通過將主評分矩陣轉化成三個二進制矩陣，通過處理三個二進制矩陣，進而得到項目列表，最終根據項目列表獲得項目子空間，利用不同的項目子空間為目標用戶生成三棵鄰居用戶樹，進而尋找鄰居用戶。算法的流程如圖1所示。

圖1 推薦算法流程圖Fig.1 Flow chart of recommendation algorithm

提出的算法的第一步就是提出了新的數據表示方法，以此來減少數據維數，并且，這種數據表示方法能夠在很大程度上提升評分預測的計算過程的效率。下面將分別介紹流程中的每個過程。

2.1 數據的表示和轉化

數據的表示和轉化主要包括二進制矩陣的構造和將二進制矩陣轉化為項目列表兩個過程，根據用戶-項目評分矩陣，將其劃分為Interested、Uninterested以及NN-interested項目三個二進制矩陣，根據用戶對項目的評分范圍以及被推薦類別的電影等級，本文選擇將評分為4和5的項目作為用戶的感興趣項目，并設置其值為1，其余設置為0，將其構造成第一個感興趣項目的二進制矩陣[14]。同理，將用戶評分值為3的項目作為用戶的NN-interested項目，設置其值為1，其余設置為0。評分值為1和2的作為Uninterested項目，最終將用戶-項目評分矩陣轉換成三個二進制矩陣。具體二進制矩陣轉化過程如圖2所示。

如圖2所示，用戶-項目評分矩陣被轉化成三個二進制矩陣，其中*代表為未作出評價的項目。提出上述數據表示方法的原因如下：（1）用戶-項目評分矩陣包含了用戶與項目之間的所有信息，并且其中也包含一些無用的信息，由于本文目的是通過尋找項目的子空間來進而找到目標用戶的鄰居用戶，例如當項目數為n時，將會有2n個項目子空間，當面對項目數較多的數據集時，其空間復雜度會很高，所以要尋找到只包含有用信息的數據表示，以此來降低空間復雜度。（2）通過二進制矩陣可以獲得相對應的項目列表，這種數據表示方法可以減少數據維數，并且由于三個二進制矩陣共同構成了用戶項目評分矩陣，它們之間存在著互為包含的數據關系，所以當用戶評分數據增加時，只需根據用戶的評分處理相應的二進制矩陣即可，運算方便。

圖2 二進制矩陣轉化過程Fig.2 Transformation process of binary matrix

下面是將項目的二進制矩陣轉化為項目列表的過程，由于三個二進制矩陣轉化為項目列表的過程相同，所以，將僅以Interested項目為例，描述其轉換過程和結果。Interested的項目列表如圖3所示。

圖3 Interested項目列表Fig.3 List of interested projects

2.2 構造項目子空間

這個過程是將獲得的項目列表轉換成項目子空間，并消除冗余項目，得到最終的項目子空間，用來尋找相似用戶。仍然以感興趣項目列表為例，尋找其項目子空間的方法如下：每個用戶的感興趣的項目子空間通過比較該用戶與其他用戶感興趣的項目來創建，例如，對于用戶ui，需要與用戶(u i+1,ui+2,…,u m)分別進行比較，并且為了保存用戶的局部子集，需要一個局部表，在迭代結束后，每個用戶的數據都將被放入一個全局表中。對于Interested項目列表，如果尋找從用戶u1開始，需要比較u1與用戶u2，尋找兩個用戶的交集，得其交集為i3，然后，將i3加入到局部表中，然后比較用戶u1和u3，交集i2加入到本地表中，用戶u1和u4的交集(i2,i3)也被存入到局部表中[15]。當用戶u1和u5交集(i2,i3)，相同的交集已經出現在表中，則更新計數值。當用戶u1遍歷比較完畢后，此時局部表中存在i2、i3和(i2,i3)3個條目，此時將局部表中的條目放入到全局表中，局部表中的內容被清除，全局表只接收全局表中不存在的條目。所以，當所有用戶遍歷完成時，全局表中不會出現重復的條目。Interested項目列表對應的初始項目子空間如圖4所示。

圖4 Interested項目子空間Fig.4 Interested project subspace

創建項目子空間的算法過程如下：

算法1尋找Interested項目子空間算法偽代碼如下：

輸入：R：二進制矩陣，m：行數

上述的算法是提出的創建子空間的算法過程，目的是通過創建的項目子空間來尋找相似用戶，常用的尋找子空間的方法的時間復雜度為O(2n)，這種方法在面對實際問題時是行不通的。然而，在提出的子空間構造的方法中，每個用戶u i對應的項目列表需要與其他用戶(ui+1,u i+2,…,um)對應的項目列表進行m(m-1)/2次運算，并且該算法需要尋找項目的交集，其時間復雜度為O(k)，其中k代表項目列表的最大長度。綜上，該過程總的時間復雜度為O(km2)，其遠小于O(2n)，并且，在面對高度稀疏的數據時，k值通常很小。

2.3 消除冗余并創建鄰居用戶樹

在所創建的項目子空間表中，存在一些在其他子空間中重復的子空間，稱之為冗余子空間，消除冗余子空間可以提升推薦效率。消除冗余子空間的過程如下：（1）首先將各個子空間按照包含項目條目的數量按由多到少進行排序。（2）將被包含或重疊的冗余子空間從列表中刪除。具體的處理過程如圖5所示。

圖5 消除冗余過程Fig.5 Redundancy elimination process

將子空間消除冗余后，就獲得了最終的感興趣項目的子空間，然后通過項目子空間尋找對每個子空間的用戶集合，以此來構建鄰居的用戶樹。過程圖如圖6所示。例如，當目標用戶對項目i1、i2和i5感興趣，則子空間(i2,i5)具有與目標用戶感興趣的項目重疊最多的項目，根據子空間用戶列表可知，與目標用戶最相似的用戶有用戶u1和u6。因此，這些用戶位于目標用戶鄰居樹的第一層，其中用戶u2和u4與用戶u6相似性最強，所以其位于樹的第二層，以此類推，直到尋找到所有用戶的相似用戶，則鄰居用戶樹構建完成。

圖6 鄰居用戶樹的構建Fig.6 Construction of neighbor user tree

2.4 鄰居用戶相似性計算方法

根據所提出的方法尋找到目標用戶的鄰居用戶樹，通過鄰居用戶樹就可以知道與目標用戶最相似的用戶有哪些。但是，樹本身就是分層的，層數的高低表示與目標用戶的相似性大小，越鄰近樹根的位置與目標用戶的相似性越強，其余次之[15]。傳統協同過濾推薦算法的相似性通常采用經典的Pearson相關系數計算方法，這種計算方法對于距離目標用戶最近的用戶同樣適用，但是與目標用戶間接的鄰居用戶就不適用這種相似性計算方法，由于間接鄰居與目標用戶之間相似的項目條目的多少是不確定的，間接用戶與其鄰居用戶之間相似性計算可以通過Pearson相關系數，所以，針對這種情況本文提出了一種改進的相似性計算方法。

本文將用戶之間相似性的計算分成兩部分，分別為直接鄰居用戶的相似性和間接鄰居用戶的相似性，兩種類型的鄰居用戶之間的相似性計算公式不同。具體的相似性計算公式如下：

（1）由于受歡迎程度較大的項目是每一個用戶所喜愛的，如果將其認作為是體現用戶相似性的項目，明顯是不正確的。其次，在原始的Pearson相似性計算公式中，只考慮用戶消費的一種商品，而沒有考慮用戶消費同一種商品處在不同時期，例如，用戶消費了物品i和j，如果消費的時間間隔越近，那么這次“同現”的權重應該越大，間隔越遠權重越小，所以，要考慮懲罰時間間隔的影響。

基于上述兩點，本文中結合Pearson相關系數提出了帶有懲罰受歡迎程度較大項目和同一項目的時間衰減懲罰兩種懲罰因子的相似性計算方法，將其作為目標用戶與直接鄰居用戶的相似性計算公式，這樣可以降低受歡迎項目以及項目的時間間隔對推薦質量的影響。計算公式為：

其中，sim(a,b)表示用戶a和b的相似度，T表示用戶a與b評分項目的交集，表示用戶a和用戶b的平均評分。t ai和t bi分別表示用戶a和b消費物品i時的時間[17]，α為常數，用于調整時間間隔的效果。

（2）考慮到目標用戶與間接鄰居用戶之間關系的間接性，本文提出了一種新的目標用戶與間接鄰居用戶的相似性計算方法。計算公式為：

其中，sim(a,i)代表目標用戶與間接鄰居用戶之間的相似度。其中用戶ua和ui將通過中間鄰居用戶ub來進行比較。C表示由直接鄰居用戶u a和ub與ua和ui構成的X和Y的組合。

上述公式中的X和Y的計算公式為：

其中，Xij是傳統的Jaccard系數相似性計算方法代表直接鄰居用戶ui和u j共同訪問項目的集合表示直接鄰居用戶ui和u j訪問項目的總和。代表用戶u i和u j共同訪問項目所占比率的絕對值差和[16]，β是為了增加共同訪問項目的效果，是一個常數。

鑒于用戶對項目的評分范圍為1到5，所以本文通過用戶評分將電影分為1至5五個等級，其中等級1代表爛片，等級5代表杰作。推薦的原則是推薦等級較高的電影給用戶，所以本文根據Tsai所提出的54/321推薦方法，將等級4和5的電影作為推薦類別。其余等級作為非推薦類別。

3 實驗分析

為了驗證提出的模型的推薦性能，采用了Python作為實驗的編程語言，在Windows10 64位操作系統，軟件版本為Anaconda4.8.3，Python3.8.5，PyCharm2020。

3.1 實驗數據

本文使用了經典的MovieLens 100K、MovieLens 1M電影評分數據集，MovieLens ML-100K數據集包含了943位用戶對1 682部電影10萬條評分記錄，MovieLens ML-1M數據集較大，其包含6 040和用戶對3 952部電影的評分記錄。兩個數據集包含評分值均分布在[1，5]內，均為正數，并且兩個數據集的稀疏度為分別為93.7%和95.8%，能夠很好地對本文提出的算法進行驗證。

本文將兩個電影評分數據集都分為5個交叉驗證子集，其中80%的數據集作為訓練集，20%數據集作為測試集，在每5個測試過程中，會有4個訓練集和一個測試集，并且每次的訓練子集不會重疊[18]。所以，實驗結果將會取5個不同測試結果的平均值作為最終的實驗結果。

3.2 實驗評估指標

實驗分別采用了推薦的Recall、Precision以及Accuracy作為衡量推薦性能的評價指標[19]，具體的計算公式為：

其中，TP為將正類預測為正類數，TN為將負類預測為負類數，FP為將負類預測為正類數，FN為將正類預測為負類數。

3.3 實驗結果分析

為了驗證所提出的推薦模型的推薦效率和質量，本文將使用不同聚類數的K-Means、不同鄰居數的Pearson相關系數以及基于非負矩陣分解模型（NNMF）的推薦算法與本文所提出模型進行比較。

三種與所提出進行對比的算法，由于其三種算法在進行推薦時，都需要設置相應的參數。參數的不同將導致推薦結果的不同。首先，對于基于K-Means聚類的協同過濾推薦算法，由于該算法模型在不同聚類數下的推薦結果不同，所以，本文選取了聚類數K分別為3、5和7時，算法所展示出的推薦效果。其次，對于僅通過皮爾遜相關系數在全局內尋找相似性用戶的協同過濾推薦算法，選取了其鄰居用戶數N分別為20、30和40時的推薦結果來進行觀察對比。對于NNMF推薦模型，其不同維度得到的推薦結果也不同[20]，文中分別選取了d=3、5、7時的推薦結果作為對比。四種算法模型的具體實驗結果數據如表1所示。

表1 四種算法的具體實驗結果數據Table 1 Specific experimental results of four algorithms%

根據上述四種推薦算法模型在兩種數據集上的實驗結果，得到了四種算法模型的對比結果圖，評估指標Recall、Precision以及Accuracy的實驗結果對比結果分別如圖7~9所示。

圖7 四種推薦算法的召回率對比Fig.7 Recall comparison of four recommendation algorithms

圖8 四種推薦算法的精確性對比Fig.8 Precision comparison of four recommendation algorithms

圖9 四種推薦算法的準確性對比Fig.9 Accuracy comparison of four recommendation algorithms

根據實驗結果可以看出，提出的基于子空間聚類的推薦模型在兩種數據集上的推薦性能都是優于其他幾種推薦模型，在三種評價指標上，都獲得了相對較好的結果，尤其是在推薦的準確性和精確性上，表現得更加明顯，相比于召回率，其余兩種指標更加重要，由于任何推薦算法的目的就是能夠為用戶提供更加準確的推薦，來更好滿足用戶的需求[21]。

為了驗證受歡迎項目和項目時間間隔對推薦質量產生的影響，本文將引入了兩個影響因素的相似性改進方法與標準方法進行了對比，并通過實驗進行了驗證，具體的實驗結果如表2所示。

表2 兩種計算方法的實驗結果比較Table 2 Comparison of experimental results of two calculation methods %

根據上述的實驗結果可知，改進的相似性計算方法較標準的計算方法相比[22]，其使推薦質量得到了提升。表明了項目的受歡迎程度和項目時間間隔對推薦質量產生了一定程度的影響。雖然在引入兩種影響因素后僅使推薦質量得到了較小程度的提升，并因此也會伴隨著實現成本的增加，但是考慮到推薦算法模型的主要目標就是為用戶提供更加準確的推薦來更好地滿足用戶的需要。并且隨著用戶評分數據的增加，兩種影響因素對推薦質量影響會愈發明顯。所以，綜上所述，本文提出的相似性計算的改進方法存在相應的合理性和必要性。

本文提出的推薦算法模型較其他幾種算法模型的優勢主要體現在以下幾個方面：

（1）該算法較傳統的協同過濾推薦算法模型相比，提高了在數據中尋找相似用戶的效率，由于傳統推薦算法在尋找相似用戶時，直接利用相應的相似性計算方法在全局內進行計算，以尋找到目標用戶的相似性用戶，在時間復雜度上本文算法表現出一定的優勢。

（2）與其他改進兩類改進算法相比，本文所提出子空間聚類較K-Means聚類以及非負矩陣分解模型相比。該算法模型不需要確定最佳聚類數、鄰居用戶數等任何可調參數，不僅提高了算法的穩定性，而且也使推薦質量得到了進一步的提升。

（3）傳統以及其他改進的推薦算法模型在尋找目標用戶的鄰居用戶時，通常是完全依賴用戶-項目評分信息來完成，例如，通過聚類算法尋找目標用戶的鄰居用戶，聚類算法易受異?；蛟肼晹祿挠绊懚鴮е戮垲惤Y果出現偏差，間接導致鄰居用戶尋找的不準確，最終也會使推薦質量下降。然而，本文提出的尋找目標用戶最佳鄰居的過程是通過構建項目列表來尋找項目的子空間，通過項目子空間來繪制目標用戶的鄰居用戶樹。當存在缺失或噪聲數據時，由于在尋找項目子空間的過程中，是通過尋找用戶之間項目交集并消除冗余項目條目的方法來確定的，而尋找鄰居用戶的過程是通過尋找與用戶感興趣項目重疊最多的項目條目所對應的用戶來完成的，所以即使出現一些異常數據，也不會對最終推薦結果產生很大的影響。例如，根據圖6所示，當目標用戶對項目i4、i5和i7感興趣，子空間(i4,i5)和(i5,i7)具有與目標用戶感興趣項目重疊最多的項目，則用戶u2、u5和u6均為目標用戶的相似用戶，但當用戶u2和u5對項目i4的評分信息缺失時，這時目標用戶的最佳鄰居為用戶u2和u6，但由于用戶u2和u5仍然存在與目標用戶感興趣重疊的項目i7，其仍然是目標用戶的第二層鄰居用戶，這種情況對最終的推薦結果不會產生明顯的影響。并且該推薦算法模型能夠在不需要確定最佳聚類數、鄰居用戶數等任何可調參數情況下完成推薦。所以，綜上所述，該推薦算法模型與其他幾種算法模型相比，具有更強的魯棒性和穩定性。

4 結束語

鑒于傳統的協同過濾推薦算法易受數據稀疏性而導致推薦質量差、效率低等問題，并且在面對高維數據時，也不能表現出很好的推薦性能。本文提出了基于子空間聚類算法的協同過濾推薦算法模型，該算法利用子空間聚類來構建目標用戶的鄰居用戶樹，以此來更快、更準確地找到目標用戶的相似鄰居用戶，進一步縮小相似用戶的搜索范圍，提高推薦效率。本文針對該算法模型并結合皮爾遜相關系數提出了新的相似性度量方式。通過實驗驗證表明，該推薦算法模型與其他幾種推薦算法模型相比，推薦性能得到了進一步的提升，并且也規避了其他算法所面臨的一些問題。該推薦算法模型在一定程度上提升了推薦性能，并且也改善了一些其他尋找鄰居用戶算法的缺點，但冷啟動問題的解決并沒有在該算法中得到很好的體現，所以，下一步的研究重點是使推薦算法的數據稀疏性和冷啟動問題都能夠在該推薦算法模型中得到很好的改善。