高天迎，張志鋼，李國燕，陳亞東

（天津城建大學 a.計算機與信息工程學院；b.信息化建設管理中心，天津 300384）

Web2.0與移動互聯(lián)網(wǎng)的高速發(fā)展使得Web站點的數(shù)量迅速增加，搜索引擎成為快速找到目標網(wǎng)站與信息的有效途徑.然而在某些情況下，用戶需求很難用簡單的關鍵詞表述.相對于搜索引擎的局限性，推薦系統(tǒng)通過分析用戶的興趣愛好，進行個性化推薦，在一定程度上彌補了搜索引擎的不足.目前，高校校園網(wǎng)已經(jīng)實行了實名認證，校園網(wǎng)的網(wǎng)絡服務器中存在大量的實名Web Log數(shù)據(jù).應用相關的聚類和推薦算法，對校園網(wǎng)Web Log數(shù)據(jù)進行分析計算，可以為校園網(wǎng)用戶提供更加個性化的網(wǎng)站推薦服務，減少數(shù)據(jù)資源的浪費.

目前，經(jīng)典的推薦策略主要包括基于內(nèi)容的推薦、協(xié)同過濾推薦、基于模型的推薦、基于網(wǎng)絡結構的推薦和組合推薦等[1-7].其中，協(xié)同過濾推薦在很多大型電子商務網(wǎng)站得到廣泛應用.協(xié)同過濾推薦算法善于發(fā)現(xiàn)用戶新的興趣點，不需要專業(yè)知識即可進行推薦，推薦質量取決于歷史數(shù)據(jù)集[8-12].然而，協(xié)同過濾算法以其他用戶對項目的評價來預測目標用戶對項目的喜好，忽略了用戶和項目的屬性信息，準確率不高；通過遍歷所有用戶去尋找最近鄰，實時性不高；對用戶評分矩陣的稀疏性敏感，當矩陣稀疏性較高時，算法準確率急劇下降[10，13].Sebastiani等[14]提出了基于貝葉斯網(wǎng)絡模型的推薦方法，該方法的性能和精度都不錯，但模型訓練的代價太大，不適用于數(shù)據(jù)更新頻繁的系統(tǒng)；Sarwar等[10]提出了基于近鄰資源項的協(xié)同過濾算法，認為系統(tǒng)中的用戶數(shù)目一般遠大于資源數(shù)目，且資源的變化較小，從而預先建立資源項的近鄰模型，以提高預測時的性能.

Rashid等[15]利用聚類技術，通過將相似的對象聚合成組，計算組內(nèi)對象的相似度，可以提高算法實時性，降低數(shù)據(jù)稀疏性的影響；Adomavicius等[16]提出了一種個性化服務中基于用戶聚類的協(xié)同過濾推薦算法，通過用戶評分的相似性對用戶聚類，根據(jù)聚類中的項目評價生成對應的聚類中心.該算法在一定程度上提高了推薦質量，但在用戶評價數(shù)據(jù)高維稀疏性的情況下，該方法的可靠性不高；曾春等[17]提出了對所有資源進行分類，將用戶對每項資源的打分轉換為用戶對某個資源類別的平均打分.這種方法降低了數(shù)據(jù)稀疏性，但相似度計算不準確.

筆者選取30天服務器WebLog文件作為研究的基礎數(shù)據(jù)，提出了一種基于用戶屬性和網(wǎng)站類型聚類的協(xié)同過濾推薦算法（user website collaborative filtering，簡稱UWCF）.通過將聚類分析與協(xié)同過濾推薦算法相結合，利用用戶-網(wǎng)站類型評分矩陣聚類有共同興趣特征的用戶，將用戶-網(wǎng)站評分矩陣轉化為用戶-網(wǎng)站類型評分矩陣，檢索到當前用戶的最近鄰居用戶集，降低冷啟動和矩陣稀疏性的影響，同時降低網(wǎng)站推薦的時間和空間復雜度，為校園網(wǎng)用戶進行網(wǎng)站推薦服務.最后，通過具體的實驗數(shù)據(jù)與基于網(wǎng)站評分聚類的協(xié)同過濾算法（website rating collaborative filtering，簡稱WRCF）對比，驗證本文算法的有效性.

1 研究方法

1.1 Web Log數(shù)據(jù)獲取

服務器日志文件主要分兩種：Web Log日志和session日志.這些文件中包含了大量的用戶訪問信息，如用戶的IP、用戶的訪問時間、瀏覽過頁面的URL、請求方法（GET或POST）等.本文使用的Web Log文件來源于筆者所在學校的校園網(wǎng)服務器，選取服務器上30天的Web Log文件作為數(shù)據(jù)源.表1列出了本文使用的Web Log日志記錄中的主要信息.

表1 Web Log文件主要信息

在將Web Log信息進行預處理基礎上，對其進行分析挖掘，可以發(fā)現(xiàn)用戶感興趣的Web站點與用戶上網(wǎng)行為偏好，結合相應的個性化推薦算法，可以對不同的用戶進行個性化的網(wǎng)站推薦.因此，首先要對Web Log信息進行數(shù)據(jù)清洗與聚類分析.

1.2 數(shù)據(jù)預處理

由于本地緩存、代理服務器和防火墻的存在，使得直接在Web Log數(shù)據(jù)上進行分析變得十分困難和不準確.在實施數(shù)據(jù)分析之前，需要對Web Log文件進行數(shù)據(jù)預處理，將原始的Web Log數(shù)據(jù)轉換成適合進行分析處理的可靠數(shù)據(jù).本文的研究目的是為不同用戶提供個性化的網(wǎng)站推薦信息，所以對原始的日志數(shù)據(jù)進行的預處理主要包括：

（1）刪除與Web Log日志分析無關的記錄.在數(shù)據(jù)清理時，通過檢查域名和URL的后綴名，刪除認為不相關的文件.

（2）刪除錯誤的訪問記錄.當服務器對用戶發(fā)出的請求響應失敗時，Web Log同樣會記錄，但這對Web日志分析沒有意義.所以在進行數(shù)據(jù)清理的時候，通過日志中的狀態(tài)碼刪除服務器對請求響應失敗的記錄.

（3）合并同一用戶同一域名不同URL的記錄，對記錄條數(shù)進行累加，記為用戶訪問同一站點的次數(shù).

1.3 數(shù)據(jù)分類

協(xié)同過濾算法一般基于用戶-項目評分矩陣進行項目推薦.本文的研究目標為網(wǎng)站推薦，需要基于經(jīng)過預處理的Web Log數(shù)據(jù)構建用戶-網(wǎng)站評分矩陣，矩陣的值可以設置為網(wǎng)站的訪問次數(shù).然而，由于網(wǎng)站數(shù)量巨大，而每個用戶能夠訪問的網(wǎng)站數(shù)量有限，因此構建出的用戶-網(wǎng)站評分矩陣必然是稀疏的.

相對于海量的網(wǎng)站數(shù)量，網(wǎng)站類型相對固定，本文參考hao.qq.com、www.hao123.com和https：//hao.#等網(wǎng)站的分類方法，建立網(wǎng)站類型表，并據(jù)此對Web Log文件中的網(wǎng)站進行類型標記，所構造的主要網(wǎng)站類型信息如表2所示.

基于網(wǎng)站類型信息，可以構建網(wǎng)站-類型矩陣，進而生成用戶-網(wǎng)站類型評分矩陣，替代用戶-網(wǎng)站評分矩陣.在進行聚類的過程中，一定程度上解決了網(wǎng)站訪問數(shù)量巨大和評分矩陣數(shù)據(jù)稀疏的問題.同時，實名認證用戶進入校園網(wǎng)時，需要提供相應的用戶信息，如身份證號、學號等.因此，可以構建用戶-屬性矩陣，將用戶性別、用戶專業(yè)和年級信息融入用戶相似度計算.本文選用的用戶屬性性別、專業(yè)、年級分別對應編號 1、2、3.

表2 網(wǎng)站類型

2 算法描述

2.1 基本思想

基于用戶-網(wǎng)站評分矩陣的聚類推薦算法，計算量大，時間成本高，精度低.本算法基于用戶-網(wǎng)站類型評分矩陣對用戶聚類，算法基本流程如圖1所示.算法主要步驟：①生成用戶-網(wǎng)站類型評分矩陣，用戶-網(wǎng)站類型評分矩陣聚類；②結合用戶屬性尋找目標用戶近鄰；③根據(jù)目標用戶近鄰計算產(chǎn)生推薦結果.

圖1 算法主要流程

2.1.1 用戶-網(wǎng)站類型評分矩陣

根據(jù)表2中的網(wǎng)站分類信息生成網(wǎng)站-類型矩陣，如表3所示.其中：T1表示新聞；T2表示購物；T3表示健康；W1、W2、W3分別表示3個不同的網(wǎng)站.一個網(wǎng)站屬于某種類型，則矩陣取值為1，否則為0，一個網(wǎng)站可以同時具有多種類型.

表3 網(wǎng)站-網(wǎng)站類型矩陣

根據(jù)Web Log文件中的用戶訪問信息，可以構建用戶-網(wǎng)站評分矩陣，如表4所示.其中：W1、W2、W3分別表示3個不同的網(wǎng)站；U1、U2、U3分別表示3個不同的用戶；矩陣取值為網(wǎng)站訪問次數(shù).

表4 用戶-網(wǎng)站評分矩陣

基于網(wǎng)站-類型矩陣和用戶-網(wǎng)站評分矩陣，可以計算用戶對不同網(wǎng)站類型的興趣度，并進一步構造出用戶-網(wǎng)站類型評分矩陣，如表5所示.其中：U1、U2、U3分別表示3個不同的用戶；T1、T2、T3分別表示3個不同的網(wǎng)站類型；矩陣取值為網(wǎng)站類型的評分.

表5 用戶-網(wǎng)站類型評分矩陣

借鑒詞頻-逆文檔頻率（TF-IDF）概念，用戶u對網(wǎng)站類型 t的評分 S（u，t）定義為

其中

式中：N為網(wǎng)站類型的個數(shù)；n為網(wǎng)站的個數(shù)；Nut為用戶u訪問的所有網(wǎng)站包含的類型t的總數(shù)目為用戶u訪問的所有網(wǎng)站包含的類型的總數(shù)目；nt為系統(tǒng)中包含類型t的網(wǎng)站數(shù)目；TF（u，t）為用戶u訪問的網(wǎng)站中含有類型t的數(shù)目占用戶u訪問的網(wǎng)站集合中含有的類型總和的比值，比值越高，則用戶u對網(wǎng)站t越感興趣；IDF（t）是根據(jù)網(wǎng)站類型在所有網(wǎng)站的分布情況，對用戶u對網(wǎng)站類型t的興趣進行調權.

2.1.2 目標用戶近鄰

基于用戶-網(wǎng)站類型評分矩陣的用戶相似度計算，只考慮用戶對網(wǎng)站類型的興趣度，不考慮用戶的屬性特征；而基于用戶-屬性矩陣的用戶相似度計算，則只考慮用戶屬性的相似性，而不考慮用戶對網(wǎng)站類型的興趣.因此，采用單一方法在計算用戶間相似度時，存在相應的缺陷，從而影響推薦精度.本文通過對兩種相似度計算方法進行加權融合來提高推薦精度.

根據(jù)前述的用戶屬性和校園網(wǎng)用戶注冊信息，可以構造用戶-屬性矩陣，如表6所示.性別男取值0，性別女取值1.按照校園網(wǎng)注冊用戶的不同專業(yè)取值1-77；年級取值1-8，分別為本科生1-5，碩士研究生6-8.

表6 用戶-屬性矩陣

設用戶i和j通過用戶-網(wǎng)站類型評分矩陣計算得到的相似度為 Sim（i，j）wt，通過用戶-屬性矩陣計算得到的相似度為 Sim（i，j）ua，融合后的相似度計算公式為

、

其中，λ為調權參數(shù)，針對不同的數(shù)據(jù)集，通過實驗的方法可以得到其最優(yōu)值.Sim（i，j）wt采用修正的余弦相似度計算，公式為

Sim（i，j）ua計算公式為

式中：Iij為用戶i和用戶j共同評分的網(wǎng)站類型集合；Ii、Ij分別為用戶i和用戶j評分的網(wǎng)站類型集合；Ri，c為用戶 i對網(wǎng)站類型 c 的評分；i為用戶 i評分的平均值；Gender（i，j）為用戶i和用戶j的性別相似度，若 i.gender=j.gender，則 Gender（i，j）=1，否則Gender（i，j）=0；Major（i，j）為用戶 i和用戶 j的專業(yè)相似度，若 i.major=j.major，則 Major（i，j）=1，否則Major（i，j）=0；Grade（i，j）為用戶i和用戶j的年級相似度，若|i.grade-j.grade|≤1，則Grade（i，j）=1，否則Grade（i，j）=0；α、β 分別為性別特征、年齡特征所占權重，可根據(jù)具體情況，結合傳統(tǒng)協(xié)同過濾算法，經(jīng)反復實驗可獲得適當?shù)臋嘀?

2.1.3 推薦結果

同一聚類內(nèi)的成員之間具有較高的相似性，可以利用融合后的用戶相似性計算公式計算用戶的相似性，從而確定目標用戶近鄰集合.選取前K個預測評分最高的用戶，進而對網(wǎng)站進行預測評分，前N個預測評分最高的網(wǎng)站即為推薦結果.

設用戶u所屬用戶聚類為Cu，可以通過計算用戶u與Cu中所有其他用戶間的相似值來預測評分.為了進一步提升網(wǎng)站推薦的準確度，本文只計算Cu中對網(wǎng)站w進行評分的用戶間的相似性.對于用戶u，設其需要進行預測的網(wǎng)站集合用Wu表示，用戶u對Wu中未評分網(wǎng)站i的預測評分Pu，i可以通過所有鄰居用戶對網(wǎng)站i評分的加權平均值獲得.Pu，i的計算方法為

式中：Sim（u，j）為目標用戶與最近鄰居的相似度；Rˉu、分別為用戶u和用戶j對網(wǎng)站評分的平均值.根據(jù)用戶對所有網(wǎng)站的預測評分，按照評分由大到小排列，選取其中評分最高的N個網(wǎng)站即可.

2.2 算法流程

步驟1：生成用戶-網(wǎng)站類型評分矩陣.

輸入：網(wǎng)站-類型矩陣WTmh，用戶-網(wǎng)站評分矩陣UWnm

輸出：用戶-網(wǎng)站類型評分矩陣UTnh

初始化：用n維向量表示用戶u，用k維向量表示網(wǎng)站w

end foreach

return用戶-網(wǎng)站類型評分矩陣

步驟2：基于用戶-網(wǎng)站類型評分矩陣的用戶聚類.每個用戶用一個N（網(wǎng)站類型個數(shù)）維向量u表示，在用戶-網(wǎng)站類型評分矩陣上的聚類過程如下：

輸入：用戶-網(wǎng)站類型評分矩陣UTnh，聚類個數(shù)k輸出：k個簇C和k個聚類中心CC

初始化：從用戶集合U中隨機選擇k個用戶向量作為初始聚類中心，記為集合

計算u與聚類中心CCi的相似度Sim（u，CCi）

計算簇cc所有用戶向量空間上的均值，更新聚類中心cc

end foreach

until每個聚類中心不再變化

步驟3：尋找近鄰，產(chǎn)生推薦.

輸入：目標用戶u，近鄰個數(shù)K，k個聚類中心CC，k個簇C

輸出：目標用戶Top K近鄰集合

foreach Cluster Center cc∈CC

結合用戶-屬性矩陣，計算目標用戶與各個簇中心相似度 Sim（u，cc）

/*按照用戶與各簇中心相似度降序排列*/

圖2 兩種推薦算法的性能對比

結合用戶-屬性矩陣，計算目標用戶與其他用戶間相似度Sim（u，ut）

return目標用戶的Top K個近鄰

3 實驗結果

筆者選用所在學校網(wǎng)絡服務器的Web Log日志文件作為實驗基礎數(shù)據(jù)，選取30天的日志記錄，經(jīng)過預處理后得到實驗數(shù)據(jù)集.本實驗的數(shù)據(jù)集包含校園網(wǎng)用戶16 255個，Web Log記錄約1.6億條，其中網(wǎng)站的數(shù)量接近11萬個，網(wǎng)站類型如表2所示.進行反復試驗，確定計算公式中權重估計值：λ＝0.6，α=0.5，β=0.3.

采用平均絕對誤差（mean absolute error，簡稱MAE）指標度量預測準確度，將UWCF算法與WRCF算法進行對比.實驗中最近鄰居數(shù)從10增加到80，間隔為10，聚類k取值為150，實驗獲取的數(shù)據(jù)見表7.

圖2為UWCF算法與WRCF算法的平均絕對誤差的推薦性能比較.WRCF算法同樣采用K-Means算法對用戶進行聚類.與UWCF算法不同，WRCF算法基于用戶-網(wǎng)站評分矩陣（見表4）對用戶進行聚類分析，計算用戶相似度，并預測用戶對目標網(wǎng)站的偏好，不考慮用戶屬性和網(wǎng)站類型信息.由圖2可以看出，當近鄰數(shù)量在10～30之間時，兩種算法預測準確度非常相近；隨著近鄰數(shù)量的增加，UWCF算法的平均絕對誤差較傳統(tǒng)的WRCF算法有一定的降低，相應的推薦精度有了一定的提高.

表7 實驗數(shù)據(jù)對比

4 結語

隨著網(wǎng)絡日志數(shù)據(jù)量、用戶數(shù)量和數(shù)據(jù)需求等的不斷增加，網(wǎng)絡日志分析變得越來越有價值.本文針對傳統(tǒng)的協(xié)同過濾推薦算法面臨的數(shù)據(jù)集稀疏性和冷啟動問題，提出了基于用戶屬性和網(wǎng)站類型聚類的協(xié)同過濾推薦算法，利用不同用戶對于不同類型網(wǎng)站的喜愛程度，構造用戶-網(wǎng)站類型評分矩陣，降低數(shù)據(jù)集的稀疏性，然后結合用戶-屬性矩陣，尋找近鄰用戶，為目標用戶推薦個性化的網(wǎng)站.實驗結果表明，該算法可以有效地降低數(shù)據(jù)集的稀疏性和系統(tǒng)的開銷，一定程度緩解了數(shù)據(jù)冷啟動問題，提高了網(wǎng)站推薦的準確性.

參考文獻：

[1]王國霞，劉賀平.個性化推薦系統(tǒng)綜述[J].計算機工程與應用，2012，48（7）：66-76.

[2]WU Yan，SHEN Jie，GU Tianzhu，et al.Algorithm for sparse problem in collaborative filtering[J].Application Research of Computers，2007，24（6）：94-97.

[3]許海玲，吳 瀟，李曉東，等.互聯(lián)網(wǎng)推薦系統(tǒng)比較研究[J].軟件學報，2009，20（2）：350-362.

[4]PAVLOV D Y，PENNOCK D M.A maximum entropy approach to collaborative filtering in dynamic，sparse，high-dimensional domains[C]//BECKERS，THRUNS，OBERMAYERK.Proceedings of the 15th Annual Conference on Neural Information Processing Systems（NIPS’02）.Vancouver：MIT Press Cambridge，2002：1 465-1 472.

[5]ZHOU T，REN J，MEDO M，et al.Bipartite network projection and personal recommendation[J].Phys Rev E，2007，76（2）：70-80.

[6]ZHOU T，JING L L，SU R Q，et al.Effect of initial configuration on network-based recommendation[J].Europhysics Letters，2007，81（5）：15-18.

[7]WANG Zhimei，YANG Fan.P2P recommendation algorithm based on hebbian consistency learning[J].Computer Engineering and Applications，2006，42（36）：110-113.

[8]WANG Weiping，LIU Ying.Recommendation algorithm based on customer behavior locus[J].Computer Systems&Applications，2006，15（9）：35-38.

[9]KIM B M，LI Q，PARK C S，et al.A new approach for combining content-based and collaborative filters[J].Journal of Intelligent Information System，2006，27（1）：79-91.

[10]SARWAR B，KARYPIS G，KONSTAN J，et al.Item-based collaborative filtering recommendation algorithms[C]//New York Association for Computing Machinery.Proc of the 10th International Conference on World Wide Web.Hong Kong：New York Association for Computing Machinery，2001：285-295.

[11]YOU Wen，YE Shuisheng.A survey of collaborative filtering algorithm applied in E-commerce recommender system[J].Computer Technology and Development，2006，16（9）：70-72.

[12]鄧愛林，朱揚勇，施伯樂.基于項目評分預測的協(xié)同過濾推薦算法[J].軟件學報，2003，14（9）：1 621-1 628.

[13]DESHPANDE M，KARYPIS G.Item-based top-n recommendation algorithms[J].ACM Transaction on Information System，2004，22（1）：143-177.

[14]SEBASTIANI P，RAMONI M，CREA A.Profiling your customers using bayesian networks[J].ACM Sigkdd Explorations Newsletter，2000，1（2）：91-96.

[15]RASHID A M，LAM S K，LAPITZ A，et al.Towards a scalable kNN CF algorithm：exploring effective applications of clustering[C]//NASRAOUI O，SPILIOUPOULOU M，SRIVASTAVA J.Knowledge Discovery on the Web International Conference on Advances in Web Mining&Web Usage Analysis.Philadelphia：Springe，2006：147-166.

[16]ADOMAVICIUS G，TUZHILIN A.Toward the next generation of recommender systems：a survey of the state-of-the-art and possible extensions[J].IEEE Trans on Knowledge and Data Engineering，2005，17（6）：734-749.

[17]曾 春，邢春曉，周立柱.基于內(nèi)容過濾的個性化搜索算法[J].軟件學報，2003，14（5）：999-1 004.