結(jié)合半監(jiān)督AP聚類和改進(jìn)相似度的推薦算法

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

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

1 引 言

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

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

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

2 相關(guān)工作

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

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

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

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

3 基于k近鄰密度估計(jì)的半監(jiān)督AP聚類

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

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

k近鄰密度估計(jì)法不斷擴(kuò)大體積Vi直到區(qū)域內(nèi)包含k個(gè)樣本點(diǎn)，進(jìn)而對(duì)數(shù)據(jù)集進(jìn)行密度結(jié)構(gòu)分析.則樣本xi的局部密度估計(jì)值如式(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

利用上述傳遞關(guān)系可以進(jìn)一步擴(kuò)大M集和C集.

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

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

吸引度r(i，j)代表點(diǎn)j適合作為i的類代表點(diǎn)的代表程度；歸屬度a(i，j)代表點(diǎn)i選擇點(diǎn)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)

再根據(jù)吸引度矩陣R更新歸屬度矩陣A：

(4)

(5)

引入阻尼因子λ，默認(rèn)值為0.5消除可能出現(xiàn)的震蕩：

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

(6)

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

(7)

假設(shè)第t次迭代后簇中心集合為Etold，如果Et=Et-1，則穩(wěn)定次數(shù)δ加1，若此時(shí)δ=stableNum則完成迭代，最后計(jì)算A+R的值得到AP過程的簇中心點(diǎn)：

(8)

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

(9)

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

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

算法1.基于k近鄰密度估計(jì)的半監(jiān)督AP聚類算法

輸入：數(shù)據(jù)集X，kN，p，δ，stableNum，m.

輸出：簇中心集合為Etnew，m個(gè)類簇.

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

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

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

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

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

4 改進(jìn)用戶相似性度量

針對(duì)傳統(tǒng)用戶相似度存在的問題.

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

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

(10)

(11)

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

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

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

(12)

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

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

(13)

4.2 本文用戶相似性度量

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

(14)

(15)

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

(16)

其中，Sim2(x，y)為Tanimoto系數(shù)，x′、y′代表經(jīng)過數(shù)據(jù)處理的用戶評(píng)分向量；N(u)代表活躍用戶u的活躍度，這里的活躍度是指用戶對(duì)19個(gè)種類的評(píng)價(jià)狀況；?為權(quán)重因子，取值范圍是[0，1].

5 基于半監(jiān)督AP聚類和改進(jìn)用戶相似度的協(xié)同過濾算法

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

算法2. 本文算法

輸入：評(píng)分矩陣R，近鄰個(gè)數(shù)N.

輸出：預(yù)測(cè)評(píng)分矩陣R*，MAE值.

Step1.加載數(shù)據(jù)集，得到評(píng)分矩陣R和電影特證矩陣M.

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

Step3.聚類結(jié)果結(jié)合評(píng)分矩陣R，得到每個(gè)用戶對(duì)19個(gè)電影種類的平均分，生成矩陣U1，且U1中還有大量缺失值.

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

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

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

Step7.加載測(cè)試集數(shù)據(jù)，使用評(píng)分矩陣R*計(jì)算MAE.

其中，評(píng)分預(yù)測(cè)公式見式(17)：

(17)

6 實(shí)驗(yàn)與分析

6.1 實(shí)驗(yàn)環(huán)境及數(shù)據(jù)集介紹

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

本文采用的聚類實(shí)驗(yàn)數(shù)據(jù)是從 UCI 機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中選出2個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集：vowel和glass.采用5重交叉驗(yàn)證(cross validation)，每次從原始數(shù)據(jù)集中抽取80%作為訓(xùn)練數(shù)據(jù)集，剩余的20%作為測(cè)試數(shù)據(jù)集.相關(guān)信息見表1所示.

表1 數(shù)據(jù)集相關(guān)信息Table 1 Data set

6.2 評(píng)價(jià)指標(biāo)

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

(18)

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

(19)

其中pi表示系統(tǒng)對(duì)用戶的預(yù)測(cè)評(píng)分，qi表示用戶實(shí)際的評(píng)分.

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

6.3.1 聚類算法分析

6.3.1.1 不同密度估計(jì)參數(shù)kN值對(duì)t、MAE的影響

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

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

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

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

6.3.1.2 不同聚類算法在不同數(shù)據(jù)集下的對(duì)比

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

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

表2的實(shí)驗(yàn)結(jié)果得到了以下結(jié)論：1) SAP-KND算法相較于傳統(tǒng)AP算法得到了一定的提高，相較于K-Means具有明顯的優(yōu)勢(shì)；2) K-Means算法適合處理小規(guī)模復(fù)雜度較低的數(shù)據(jù)；3) 觀察AP算法及其改進(jìn)算法SAP-KND，AP系列算法適用于不同規(guī)模的數(shù)據(jù)，其穩(wěn)定性較高；4) 對(duì)比兩種AP算法，驗(yàn)證了近鄰密度標(biāo)記規(guī)則的有效性，使不同類簇的樣本點(diǎn)更好的分割開來.

6.3.2 本文算法在不同相似度參數(shù)下的對(duì)比

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

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

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

首先，觀察MAE值的變化情況可以得出，β值對(duì)預(yù)測(cè)精度的影響大于?值產(chǎn)生的影響.當(dāng)?=0.4時(shí)節(jié)點(diǎn)處在最低處，所以此處為最優(yōu)權(quán)值，進(jìn)而說明用戶的軌跡相似性對(duì)相似度的準(zhǔn)確性影響更大.其次從總體的折線走勢(shì)中可以看出，4條曲線總體走勢(shì)基本相似，說明β值對(duì)預(yù)測(cè)精度的相對(duì)影響不隨著其他因素的變化而變化.最后，觀察β在6至12的區(qū)間時(shí)變化緩慢，在β為14時(shí)到達(dá)了最低點(diǎn)，隨后β為16時(shí)出現(xiàn)了一個(gè)大幅度增加.結(jié)果說明當(dāng)用戶的活躍度為14時(shí)啟動(dòng)活躍因子為最佳時(shí)間，如果對(duì)活躍度過于敏感會(huì)得到適得其反的效果.

6.3.3 本文相似度有效性驗(yàn)證

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

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

圖5 4種算法在不同近鄰個(gè)數(shù)N下的對(duì)比Fig.5 Comparison of four algorithms under different N neighbors

6.3.4 不同算法在不同近鄰個(gè)數(shù)N下的對(duì)比

為了驗(yàn)證本文算法的有效性，這里選擇了4種算法作為對(duì)比進(jìn)行實(shí)驗(yàn)：

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

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

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

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

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

圖6 不同算法在不同近鄰個(gè)數(shù)N下的對(duì)比Fig.6 Comparison of different algorithms under different numbers of neighbors N

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

本文算法在近鄰個(gè)數(shù)相同的幾種情況下比UBCF 、IVAWCF和IVAWCF在預(yù)測(cè)精度上具有明顯的提高；IVAWCF具有較高的近鄰用戶需求量，本文算法在低近鄰用戶需求量時(shí)更具有優(yōu)勢(shì).通過與ICWSCF算法的對(duì)比可以證明：同時(shí)利用用戶和項(xiàng)目?jī)蓚?cè)信息尋找近鄰用戶的方法明顯優(yōu)于僅憑單一側(cè)尋找近鄰項(xiàng)目的方法.與UP-HCF算法相比，本文算法在穩(wěn)定性上得到了明顯的提高，在推薦精度方面也得到了一定提高，說明SAP-KND算法在一定程度上克服了無監(jiān)督聚類算法的局限性.

7 總 結(jié)

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