結合半監督AP聚類和改進相似度的推薦算法

李昆侖，趙佳耀，王萌萌，于志波

(河北大學 電子信息工程學院，河北 保定 071002)

1 引 言

推薦算法可以分為基于內容的推薦、基于協同過濾的推薦、基于關聯規則的推薦、基于知識的推薦等類別，其中協同過濾推薦是應用最廣泛的推薦算法之一，但它也存在數據稀疏性、冷啟動問題、可擴展性等問題[1].目前針對稀疏性問題的優化可以分為兩大類，第一類是通過聚類或引入優化因子的方式提高相似性度量精度；第二類是按照某種方法對部分缺失值進行填充[2].本文采用第一類優化方法，以提高相似性度量精度.

一方面，由于傳統的大多數聚類算法的聚類精度難以滿足要求，因而可以從聚類方式的角度進行改進.H.Koohi等人使用Fuzzy C-Means聚類對用戶分組，精確了最近鄰用戶搜索范圍，解決了近鄰用戶尋找不準確問題[3]；為了解決H.Koohi的算法中用戶聚類結果不理想問題，S.Fremal等人根據屬性進行項目聚類，在多個集群中對目標項目進行評分預測，然后使用加權策略將這些預測評分合并[4].為了進一步提高協同過濾算法中聚類模型的性能，以提升推薦質量和推薦效率，本文提出了一種基于k近鄰密度估計的半監督AP聚類(Semi-supervised AP clustering based onk-nearest neighbor density estimation，SAP-KND)：使用基于近鄰密度選擇的成對約束信息與上層推舉思想改進AP聚類.另一方面，也可以考慮從相似性度量的角度進行改進.M.Shamr等人考慮到并非所有評分對用戶都有相同的重要性，將評分權重融入到Pearson相關系數中[5]；S.Bag為了將用戶的總評價向量融入相似度計算，將相關Jaccard相似度和均方距離相似度進行了融合[6]；孫紅等人在Pearson相似度原理上添加物品熱門因子，一定程度上提高了推薦的精確度[7].

根據上述分析，本文提出了一種基于半監督AP聚類和改進用戶相似度的協同過濾算法：首先使用基于近鄰密度選擇的成對約束信息與上層推舉思想改進的AP聚類(SAP-KND)得到項目類簇；然后利用初始評分矩陣構造用戶對項目類簇的偏好矩陣；最后使用改進后的用戶相似性度量得到近鄰用戶集，通過具有相似偏好的用戶評分預測評分值.本文實驗部分使用vowel、glass 及Movielens這3種數據集，采用FMI值和平均絕對誤差(MAE)評價本文算法，并得到實驗結果.

2 相關工作

由上文可知，傳統協同過濾算法中相似性度量對象較為單一，無法同時利用項目側和用戶側的近鄰項信息.近年來為了解決此問題，研究人員提出了一種基于項目類別偏好的混合協同過濾算法(Hybrid Collaborative filtering algorithm based on user preference model，UP-HCF)：K.Shinde等人對穩定的項目特征進行聚類，構建用戶對項目類別的偏好模型，并結合傳統協同過濾算法預測評分，尋找近鄰用戶得到推薦結果[8]；J.Li等人根據電影屬性形成電影特征向量，并結合用戶評價矩陣生成用戶興趣向量，通過迭代的方式對電影特征向量和用戶興趣向量進行相互更新，然后根據用戶興趣向量構造用戶相似度矩陣[9].

在傳統的UP-HCF算法中使用的K-Means、K-medoids、DBSCAN、BIRCH等無監督聚類算法在面對噪音數據和大規模數據時，存在一定的局限性，進而導致聚類算法無法在稀疏的數據集中完成推薦任務.近鄰傳播聚類(Affinity Propagation，AP)與以往的無監督聚類方法相比，此方法可以更快的處理大規模數據，不受限于選擇初始類代表點的選擇，且能夠得到高精度聚類結果，其最大的優點在于，AP算法的輸入矩陣沒有規定相似度矩陣的對稱性，因此提高了AP算法的泛化能力[10].AP算法假設所有的樣本點都為聚類中心；在各個節點(樣本點)之間，存在被稱為吸引度(Responsibility)和歸屬度(Availability)的兩種消息在不斷地進行迭代傳遞；直到找到距離最近的類代表點的相似度之和最大的數據點，作為最優的類代表點集合[10].

現有的半監督聚類算法大致可分為兩類：基于約束的半監督聚類、基于距離的半監督聚類.其中基于約束的(constraint-based)半監督聚類：在聚類過程中遵循約束條件，使聚類結果滿足所有約束信息，must-link約束表示兩個樣本必須被聚到同一類簇中，cannot-link約束表示兩個樣本必須被聚到不同類簇中[11].由于成對約束具有弱監督特性，在實際問題中往往更容易獲取先驗信息.但是，對于復雜結構的數據集，AP聚類通常不能得到合理的聚類結果.AP聚類的相似度矩陣S包含數據對之間的信息，因此，利用先驗信息約束數據對，更容易達到提高聚類精度的目的.基于以上啟發，本文考慮將半監督AP聚類算法應用到推薦系統，旨在進一步提高推薦性能.

傳統UP-HCF算法的相似性度量方式仍然存在以下問題：1)計算用戶相似度時往往只依賴評分數值的大小；2)將所有用戶或物品對計算相似度的貢獻視為一致的；3)沒有考慮到用戶評分行為的相似性帶來的影響.為了全面客觀地評價用戶相似度，本文使用用戶活躍度和用戶行為軌跡對相似度進行改進.

3 基于k近鄰密度估計的半監督AP聚類

利用先驗信息改進相似度矩陣，可以有效優化AP算法.但是在實際問題中，數據本身沒有任何先驗信息；無論是球型數據結構還是流形結構，同一類簇的樣本主要分布于一個密度較高的區域，類簇之間通常存在于一個低密度區域，且簇中心只是部分存在于高密度區域.為了避免Parzen算法中窗函數h的選擇問題，本文采用了k近鄰思想估計局部密度，然后假設處于高密度極值點的樣本的k個最近鄰樣本必定與該樣本屬于同一類別，并且在極為稀疏的幾個區域的大部分樣本存在cannot-link關系.基于此極端假設對數據集進行少量標記，可以使靠近的點更近，遠離的點更遠，同時避免must-link約束信息過于集中而產生違反問題.

雖然針對較復雜的數據傾向于產生更多的類，說明算法具有較高的聚類精度，但是往往無法滿足實際需求，無法得到合理的聚類結果.為了避免增加算法復雜度同時可以保障理想的聚類結果，首先使用傳統歐式距離計算相似度矩陣，然后使用馬氏距離處理AP聚類結果.因此SAP-KND使用馬氏距離(Mahalanobis distance)并融合上層推舉思想，得到期望的簇數.SAP-KND算法詳細過程如下.

k近鄰密度估計法不斷擴大體積Vi直到區域內包含k個樣本點，進而對數據集進行密度結構分析.則樣本xi的局部密度估計值如式(1)[12]：

(1)

(xi，xj)∈must-link&&(xj，xk)∈must-link?(xi，xk)∈must-link

(xi，xj)∈must-link&&(xj，xk)∈cannot-link?(xi，xk)∈cannot-link

利用上述傳遞關系可以進一步擴大M集和C集.

本文采用歐式距離構建相似度矩陣S[s(i，j) ]Z×Z，使用成對約束信息可將數據集分為3種集合，這里的集合M又稱為高密度集，設置集合D{D∈X&D?M∪C}為中密度集，集合C又稱稀疏集.按如下方法調整相似度矩陣：

s(k，k)為偏向參數(Preference)，AP算法假設所有點成為簇中心的可能性相同，即s(k，k)=p，一般將p值設置為相似度矩陣的均值p=median(s)，且p越大簇數越大.在SAP-KND算法中，需要對AP聚類結果進行再聚類，所以這里將p值設置稍大.

吸引度r(i，j)代表點j適合作為i的類代表點的代表程度；歸屬度a(i，j)代表點i選擇點j作為其類代表的適合程度.利用相似度矩陣S和歸屬度矩陣A=[a(i，k)]，更新吸引度矩陣R=[r(i，k)]：

r(i,k)←s(i,k)-max{a(i,k′)+s(i,k′)},i≠k

(2)

r(k,k)←p(k)-max{a(k,k′)+s(k,k′)},i=k

(3)

再根據吸引度矩陣R更新歸屬度矩陣A：

(4)

(5)

引入阻尼因子λ，默認值為0.5消除可能出現的震蕩：

rnew(i,k)=λ×rold(i,k)+(1-λ)×r(i,k)

(6)

anew(i,k)=λ×aold(i,k)+(1-λ)×a(i,k)

(7)

假設第t次迭代后簇中心集合為Etold，如果Et=Et-1，則穩定次數δ加1，若此時δ=stableNum則完成迭代，最后計算A+R的值得到AP過程的簇中心點：

(8)

由于AP算法容易產生較多的類，無法滿足本文推薦模型的聚類目標，所以需要對簇中心進行再聚類，使聚類算法輸出一個固定的類簇數m.這里考慮融入上層推舉思想：計算簇中心點間的距離，選出距離最近的一對簇中心，將所代表的類簇合并，并計算新類簇的簇中心；重新計算新簇中心和其他簇中心的距離，重復上述過程直至得到期望類簇數目m和最終簇中心集合Etnew.鑒于推薦算法所使用的數據集中各類別的占比具有很大的差異性且簇中心具有較強的代表性，所以此過程要考慮到簇中心各分量的差別以及樣本各特征之間的聯系，因此這里使用馬氏距離度量簇中心間的相似性：

(9)

其中Σ-1為矩陣[ci，cj]的協方差矩陣的逆矩陣[14].

本文聚類算法步驟如算法1所示.

算法1.基于k近鄰密度估計的半監督AP聚類算法

輸入：數據集X，kN，p，δ，stableNum，m.

輸出：簇中心集合為Etnew，m個類簇.

Step1.使用k近鄰密度估計法得到p1，…，pZ，使用kd-tree選擇出集合H、集合L;

Step2.分別將集合H和集合L通過特定方式標記為must-link和cannot-link，生成M約束集和C約束集；

Step3.使用成對約束對相似度矩陣進行3段式處理，并進行AP聚類；

Step4.不斷交替更新矩陣A和矩陣R，迭代完成得到Etold；

Step5.利用上層推舉思想進行再聚類，簇中心間距離使用馬氏距離，得到Etnew，m個類簇.

4 改進用戶相似性度量

針對傳統用戶相似度存在的問題.

問題1.假設A用戶與B用戶只有兩個共同評分項目且分值大小相近，而A用戶與C用戶擁有30個共同評分項但是A的評分均值大于C，則得到的相似度結果就是：AB之間的相似程度遠遠大于AC之間的相似度.而事實卻恰恰相反，這就造成了極大的誤差.

問題2.如果一個愛好廣泛的用戶對所有的類型都有評分記錄，那么這個用戶就沒有其利用的價值，共同評分項的數量也不能完全成為決定相似度的因素.為了全面客觀地評價用戶相似度，本節基于Jaccard相似度(軌跡相似度)[6]的思想和皮爾遜相關系數法(Pearson)[15]改進用戶相似度.兩種傳統相似度公式分別如式(10)、(11)所示：

(10)

(11)

4.1 活躍用戶懲罰因子與軌跡相似度

在稀疏矩陣中，用戶間評論項目的軌跡信息對降低推薦所產生的誤差尤為重要.針對問題一可以考慮結合Jaccard相似度，但是Jaccard相似度只考慮了用戶間共同評分項的數量，沒有利用共同評分項的評分等級.Tanimoto系數(廣義Jaccard相似度)的元素的取值可以是實數，所以也同時將評分等級的影響融入了計算結果，因此本文使用了Tanimoto系數，計算方式如式(12)：

Ej(A,B)=(A*B)/(‖A‖2+‖B‖2-A*B)

(12)

其中，其中A、B分別表示為兩個向量，向量中每個元素表示為向量中的一個維度，在每個維度上，取值為非二值性的，A*B表示向量乘積，‖A‖2表示向量的模.

針對問題二本文加入了活躍用戶懲罰因子.本文的活躍用戶懲罰因子根據用戶對19類電影類型的評分記錄的數量來衡量.根據函數的特性，本文使用y=1/ln(2x-1)(ln─以e為底的對數)作為懲罰函數，N(u)代表活躍用戶u的活躍度，當活躍度到達閾值β時，則啟動懲罰因子，表達式如(13)：

(13)

4.2 本文用戶相似性度量

在計算相似度時，本文綜合考慮了活躍用戶懲罰因子f、軌跡相似度E以及實際評分對結果的影響，將活躍用戶懲罰因子融入Pearson相似度并于軌跡相似度相結合，旨在為相似性度量提供更多的信息，緩解數據稀疏性帶來的影響.與傳統Pearson相似度不同的是，式(14)中的i表示用戶x和y的共同評分項目類別，并且融入了懲罰因子f.本文相似性度量具體公式見式(14)：

(14)

(15)

newSim=?Sim1(u,v)+(1-?)Sim2(u′,v′)

(16)

其中，Sim2(x，y)為Tanimoto系數，x′、y′代表經過數據處理的用戶評分向量；N(u)代表活躍用戶u的活躍度，這里的活躍度是指用戶對19個種類的評價狀況；?為權重因子，取值范圍是[0，1].

5 基于半監督AP聚類和改進用戶相似度的協同過濾算法

對于本文算法有以下兩點論述：1)相似性度量依據具有相似偏好的用戶生成相似度矩陣，所以本文算法相似性度量結果的有效性極大依賴于用戶對電影類別的偏好；2)一個電影標簽可能同時存在于多個電影中，每個電影還有多個特征向量，因此數據集的復雜結構增加了聚類的難度.使用近鄰密度尋找成對約束的方法可以初步標記各個類別的初始位置和分類間隔的位置，最后使用SAP-KND算法可以得到一個更加精確的電影分類結果，進而可以更準確的得出用戶對電影類別的偏好.具體實現過如算法2所示.

算法2. 本文算法

輸入：評分矩陣R，近鄰個數N.

輸出：預測評分矩陣R*，MAE值.

Step1.加載數據集，得到評分矩陣R和電影特證矩陣M.

Step2.使用SAP-KND對電影特征矩陣M進行聚類，將全部電影分為19類(電影的全部類別).

Step3.聚類結果結合評分矩陣R，得到每個用戶對19個電影種類的平均分，生成矩陣U1，且U1中還有大量缺失值.

Step4.使用本文提出的相似度newSim(x，y)，基于U1構造用戶相似矩陣U2.

Step5.根據用戶相似矩陣U2生成近鄰用戶集(top-n)，使用式(17)對U1進行缺失值填充，得到矩陣U3.

Step6.觀察缺失值所屬電影種類，根據U3將評分矩陣R中的缺失值填充，生成新的評分矩陣R*.

Step7.加載測試集數據，使用評分矩陣R*計算MAE.

其中，評分預測公式見式(17)：

(17)

6 實驗與分析

6.1 實驗環境及數據集介紹

本實驗在CPU為 Intel(R) Core(TM)i5-7200U，運行內存為4GB內存的計算機上運行，使用python3.6中的sklearn等程序包進行實驗.本文的推薦算法實驗數據集采用的是Minnesota大學Grouplens項目組制作的Movielens100k版本的數據集[3].訓練集和測試集分別使用ua.base文件和ua.text文件.

本文采用的聚類實驗數據是從 UCI 機器學習數據庫中選出2個標準數據集：vowel和glass.采用5重交叉驗證(cross validation)，每次從原始數據集中抽取80%作為訓練數據集，剩余的20%作為測試數據集.相關信息見表1所示.

表1 數據集相關信息Table 1 Data set

6.2 評價指標

本文所采用的聚類評價指標是FMI指標，其將準確率和召回率結合在一起來評價聚類結果.對于實際類別w和簇類Cm的準確率和召回率分別是：pre(w，Cm)=Nwm/Nm，Rec(w，Cm)=Nwm/Nw其中：Nwm代表簇類m中實際類別為w的樣本數；Nm代表簇類m中的樣本數；Nw代表實際類別w中的樣本數[16].對于整劃分的FMI值為：

(18)

其中FMI的取值越大則算法越準確.本文所采用的推薦質量度量標準是平均絕對誤差MAE (Mean Absolute Error)，表達式如式(19)所示：

(19)

其中pi表示系統對用戶的預測評分，qi表示用戶實際的評分.

6.3 實驗結果及分析

6.3.1 聚類算法分析

6.3.1.1 不同密度估計參數kN值對t、MAE的影響

首先，針對SAP-KND中簇中心的迭代次數t設置對比試驗，以體現算法在不同kN值下的收斂速度.其次，為了得到算法在不同kN值下的預測準確度，這里設置了針對MAE值的對比試驗.控制其他參數不變的情況下，將kN設置為24，28，32，36，40，44，48，依據7個數值進行實驗從而獲取迭代次數t和MAE值，依據這兩個變量可以更好的確定最佳kN值.在尋找最近kN值的同時，將傳統AP算法的迭代次數t和F值與SAP-KND算法進行對比.

圖1 不同kN值對迭代次數t的影響Fig.1 Influence of different kN values on iteration times t圖2 不同kN值對MAE的影響Fig.2 Influence of different kN values on MAE

針對SAP-KND算法的曲線.考慮到實驗中的偶然性因素，每組均通過多次實驗取平均值的方式得到上述結果.結果顯示，圖1中可以清晰的得到折線圖總體呈現一種低凹形狀，因此kN范圍在[28，40]區間時的迭代次數t較少，意味著迭代次數較快達到了穩定次數stableNum；圖2中顯示折線圖總體趨勢與圖1表現相類似，但也有細微差別，可以得到在本文算法中迭代次數的大小對MAE值具有相對較大的影響而且呈正相關.因此，當kN取28與32時推薦精度相對較高，綜合觀察兩組實驗可以得到SAP-KND算法在kN的取值在32附近時算法綜合性能最好.

針對AP算法的曲線.圖1的實驗結果表明，成對約束的引入使數據集得到了稀疏化，進而降低數據復雜度，使得算法較快滿足類簇中心集{ci}的穩定條件.兩組實驗表明SAP-KND算法提高了聚類精度，加快了收斂速度.

6.3.1.2 不同聚類算法在不同數據集下的對比

為了更好的體現本文聚類算法的優越性.在其他參數不變的情況下，SAP-KND算法針對3個數據集設置不同的m值，在最佳kN值的情況下計算FMI值.其他兩種算法取10次5重交叉驗證的最優值作為FMI值，并設計以下對比實驗，見表2所示.

表2 不同算法在數據集下的FMI值Table 2 FMI values of different algorithms in data sets

表2的實驗結果得到了以下結論：1) SAP-KND算法相較于傳統AP算法得到了一定的提高，相較于K-Means具有明顯的優勢；2) K-Means算法適合處理小規模復雜度較低的數據；3) 觀察AP算法及其改進算法SAP-KND，AP系列算法適用于不同規模的數據，其穩定性較高；4) 對比兩種AP算法，驗證了近鄰密度標記規則的有效性，使不同類簇的樣本點更好的分割開來.

6.3.2 本文算法在不同相似度參數下的對比

活躍因子與活躍程度的函數關系如圖3所示，縱坐標是活躍因子f，橫坐標是活躍度N(u).在計算相似度時，由于f作為相似度公式分子的一部分并作為一種限制因素，所以其取值不能大于1.原始圖像縱坐標的取值范圍(0，+∞)不能應用于實際的算法計算，因此本文規定取值范圍為0

本節旨在直觀的表現出不同活躍度閾值β在不同權值?下的MAE值的變化情況，同時得到MAE到達最小值時兩參數的最佳取值.?值的意義可以描述為：計算相似度時更偏重用戶可靠度(行為軌跡因素)或者更偏重分值的差異因素.當近鄰個數設置為12時，將β初始值設為6，以1為間隔逐步增至16；權值?選取0.2、0.4、0.6、0.8，實驗結果如圖4所示.

圖3 f的函數圖像Fig.3 Function image of f圖4 不同相似度參數下的對比Fig.4 Comparison of different similarity parameters

首先，觀察MAE值的變化情況可以得出，β值對預測精度的影響大于?值產生的影響.當?=0.4時節點處在最低處，所以此處為最優權值，進而說明用戶的軌跡相似性對相似度的準確性影響更大.其次從總體的折線走勢中可以看出，4條曲線總體走勢基本相似，說明β值對預測精度的相對影響不隨著其他因素的變化而變化.最后，觀察β在6至12的區間時變化緩慢，在β為14時到達了最低點，隨后β為16時出現了一個大幅度增加.結果說明當用戶的活躍度為14時啟動活躍因子為最佳時間，如果對活躍度過于敏感會得到適得其反的效果.

6.3.3 本文相似度有效性驗證

為了驗證本文相似度的有效性，將沒有考慮融入用戶活躍度的算法( algorithm1)、沒有考慮軌跡相似度的算法( algorithm 2)、只考慮軌跡相似度的算法( algorithm3)作為3種對比算法，與本文算法(The new algorithm)在不同近鄰個數N的情況下進行對比.選取的目標用戶最近鄰居數初始化為4，并以2為間隔逐步增至20.

從圖5中首先可以看出，algorithm3的MAE值明顯高于其它3個算法，并與algorithm2相比較可以得出：只考慮用戶之間的評分軌跡相似性而不考慮評分的數值最終會導致相似度的有效性極低，并且Pearson相似度的有效性要高于Tanimoto系數；其次觀察到 algorithm2隨著近鄰數的增加，MAE值下降的趨勢較為明顯，這說明：近鄰用戶越多，活躍用戶因子f的懲罰功能對算法精度的影響越明顯.最后綜合觀察4種相似度所對應的4條曲線可以得出：綜合考慮用戶的活躍度、可靠度以及用戶實際評分3種因素的協同過濾推薦算法有效性明顯高于單獨考慮一種因素的算法，同時也驗證了本文算法的有效性.

圖5 4種算法在不同近鄰個數N下的對比Fig.5 Comparison of four algorithms under different N neighbors

6.3.4 不同算法在不同近鄰個數N下的對比

為了驗證本文算法的有效性，這里選擇了4種算法作為對比進行實驗：

1)基于用戶聚類協同過濾算法(Collaborative filtering algorithm based on user clustering，UBCF)[3]；

2)基于項目聚類和加權策略的協同過濾算法(Collaborative filtering algorithm based on item clustering and weighting strategy，ICWSCF)[4]；

3) 基于用戶偏好的混合協同過濾算法(Hybrid Collaborative filtering algorithm based on user preference model，UP-HCF)[5]；

4) 融合混合興趣向量和評級自適應權重的推薦算法(A recommendation algorithm that hybrid interest vectors and rating adaptive weights，IVAWCF)[6].

最近鄰居數目的選定對推薦質量有著重要的影響，為了對不同鄰域條件下的實驗結果進行評價和比較，本節將4種算法與本文算法(The proposed algorithm)在不同近鄰個數N下進行對比.將選取的目標用戶最近鄰居數初始化為4，并以2為間隔逐步增至20，在kN、?、β為最優值的情況下進行實驗，實驗結果如圖6所示.

圖6 不同算法在不同近鄰個數N下的對比Fig.6 Comparison of different algorithms under different numbers of neighbors N

結果顯示，IVAWCF的MAE值隨著近鄰數的增加呈下降趨勢并逐漸趨于平緩；本文算法與UP-HCF的算法相比曲線走勢明顯較為平緩且在N為10時MAE值最小，剩余兩種算法在N為12時MAE值最小，通過綜合觀察近鄰個數為10-12時推薦效果最佳.

本文算法在近鄰個數相同的幾種情況下比UBCF 、IVAWCF和IVAWCF在預測精度上具有明顯的提高；IVAWCF具有較高的近鄰用戶需求量，本文算法在低近鄰用戶需求量時更具有優勢.通過與ICWSCF算法的對比可以證明：同時利用用戶和項目兩側信息尋找近鄰用戶的方法明顯優于僅憑單一側尋找近鄰項目的方法.與UP-HCF算法相比，本文算法在穩定性上得到了明顯的提高，在推薦精度方面也得到了一定提高，說明SAP-KND算法在一定程度上克服了無監督聚類算法的局限性.

7 總 結

傳統的基于項目類別偏好的混合協同過濾算法存在相似性度量精度較低的問題，為此本文首先提出一種半監督聚類算法-SAP-KND算法，并用于項目聚類，然后對相似度計算方式進行了改進.理論分析和實驗結果均表明：與傳統算法相比，本文算法可以保證近鄰用戶與目標用戶具有更高的相似度進而提高了推薦的準確性與穩定性.本文的下一步工作考慮將上述半監督聚類與遷移學習相融合，希望可以利用更豐富的偏好信息為用戶推薦項目.