基于模糊C均值聚類有效性的協同過濾算法

葛林濤，徐桂瓊

(上海大學 管理學院，上海 200444)

基于模糊C均值聚類有效性的協同過濾算法

葛林濤，徐桂瓊

(上海大學 管理學院，上海 200444)

針對電子商務系統中傳統協同過濾算法普遍存在的稀疏性和擴展性問題，文中提出了基于模糊C均值聚類有效性的協同過濾算法。首先依據四種不同的聚類有效性函數確定合理的聚類數區間，并在合理聚類數區間中根據Xie-Beni方法搜尋得到最佳的聚類數，然后使用最佳聚類數對項目進行模糊C均值聚類，將用戶對單個項目的偏好轉化為對相似群組的偏好，將稀疏的用戶-項目偏好信息構造成密集的用戶-模糊類的偏好信息，最后在項目所屬類別中尋找目標用戶的最近鄰并產生推薦。在數據集MovieLens上與傳統推薦算法相比的實驗結果表明，新算法在平均絕對偏差、召回率、準確覆蓋率等方面都有了較大改善，提高了推薦質量。

協同過濾；模糊C均值聚類算法；聚類有效性函數；最佳聚類簇數

1 概 述

互聯網已成為當下人們獲取信息的一個重要途徑。然而，隨著互聯網信息的不斷增加，用戶很難從中挑選出自己真正需要的信息。針對互聯網中的“信息過載”問題，推薦系統作為一種有效的解決手段被廣泛應用在電子商務領域，它能主動為用戶推薦需要但無法輕易獲取的信息，在提供更具針對性的個性化服務的同時也提高了電子商務網站的銷售量。因此，推薦系統已成為當下電子商務應用領域中的研究熱點。其中，協同過濾推薦算法是目前最流行和最成熟的推薦技術[1]。

然而在實際應用中，推薦系統存在兩個問題：一是稀疏性，由于用戶評價過的物品只占所有物品的一小部分，因此，用戶-項目評分矩陣非常稀疏，從而影響推薦質量；二是可擴展性，隨著系統中用戶和資源的增多，性能越來越低。

針對以上問題，許多學者進行了深入研究并取得了一系列的研究成果[2-14]。其中，將聚類算法應用到推薦系統中有助于緩解數據的稀疏性問題。如文獻[5-7]使用硬聚類算法K-means方法對用戶進行聚類，減少了尋找最近鄰的計算量，然而硬聚類算法很難符合一個項目可能同時屬于幾個類的實際情況，同時，為了確定最佳的聚類數目，要計算不同聚類數目下的MAE值，增加了計算復雜度。文獻[8]綜合考慮用戶對項目的關注和用戶評價的影響，提出了改進的用戶聚類的協同過濾推薦方法，使用了用戶對項目關注相似度來替代傳統的相似度。文獻[9]提出了基于用戶譜聚類的協同過濾推薦算法，并使用組合相似度[10]在用戶所屬類中尋找最近鄰并產生推薦，提高了推薦質量。文獻[11-12]提出了基于模糊聚類的協同過濾算法，通過傳遞閉包法計算模糊相似關系，然后對項目進行聚類，緩解了由于用戶項目評價數據稀疏而導致傳統協同過濾中尋找最近鄰居用戶不準確的問題，然而在求解項目相似矩陣的過程中需要進行矩陣冪運算，當矩陣的階數n較大時，工作量較大。文獻[13-14]中將模糊C均值聚類應用到協同過濾算法中，有效緩解了數據稀疏性問題。文獻[13]通過比較不同聚類數下的RMSE值，確定最佳聚類數，計算復雜度有待提高。文獻[14]將用戶數量的一半作為最佳聚類數，降低計算量，準確度有待提高。文獻[15]對Xie-Beni方法[16]進行了證明與改進，提出了一種優化的最佳聚類數選擇策略，在提高了算法的準確性的同時也減少了計算量。

基于以上研究工作，文中提出了一種基于模糊C均值聚類有效性的協同過濾算法(FCMCCF)。在使用模糊C均值聚類算法解決數據稀疏性問題的同時，引入聚類有效性判別函數，降低了尋找最佳聚類數的計算復雜度。在MovieLens公開數據集上的實驗結果表明，提出的改進算法與傳統協同過濾算法相比，較好地改善了平均絕對偏差、覆蓋率、召回率指標，提高了推薦質量。

2 概念定義

2.1 協同過濾算法概述

協同過濾算法是推薦系統中應用最廣、效果最好的算法之一。典型的協同過濾算法是基于用戶的，其基本思想是通過用戶-項目評分矩陣計算出用戶之間的相似度，從中選出與用戶最相似的前k個用戶，根據這k個用戶對當前用戶的未評分項目的評分，預測當前用戶對其未評分項目的評分，選出前n個推薦。協同過濾推薦算法的實現過程主要分為三步：

(1)建立推薦模型。

協同過濾算法的輸入是一個m×n的用戶評價矩陣R的數據，Rui表示第u個用戶對第i項的評價值。一般把評分分成5個等級，評分越高說明這個用戶對物品的評價越高。

(2)查找最近鄰居。

通過計算目標用戶與其他用戶之間的相似度，找出與目標用戶最相似的“最近鄰居”集，即對目標用戶u，Nu={N1,N2,…,Ni}。首先計算用戶之間的相似度，可采用Pearson相關系數、Cosine相似性等度量方法。然后，對目標用戶u產生一個以相似度sim(u,v)遞減排列的“鄰居集合”。由于修正余弦相似度的準確性較高，因此文中采用的是修正的余弦相似性，見式(1)。

(1)

(3)進行推薦。

最后，根據目標用戶的m個最近鄰居對項目的評分，可以進行該用戶對其未評分項目的評分預測。計算方法如下：

(2)

其中，Pui代表目標用戶u對任意項目i的預測評分；S(u)表示鄰居用戶集合。

在預測出目標用戶對未評價項目的評分后，使用TOP-N方法挑選出預測評分最高的N項，并對用戶進行推薦。

2.2 模糊C均值聚類算法簡介

聚類算法往往分為硬聚類算法和軟聚類算法。將每個數據對象歸到一個類被稱為硬聚類算法，然而數據對象經常可以被歸到幾個類中，屬于每個類的程度也不相同。因此，Ruspini和Bezdek于1981年提出了C均值的改進算法—模糊C均值聚類算法(FCMC)[17]。模糊C均值聚類算法相比于其他算法，具有簡單、高效等特點，因此應用在很多領域。模糊C均值聚類算法屬于一種有效的軟聚類算法，根據每個樣本隸屬于某個類的程度(即隸屬度)來對樣本進行聚類，所以模糊C均值聚類算法在復雜的樣本上也可以得到比較好的聚類效果[18-19]。

對于論域中的有限個對象集合{X1,X2,…,Xn}，對于每個數據樣本屬于某個類別的程度，在模糊C聚類算法中，使用隸屬度來定義。例如對于n個向量Xi(i=1,2,…,n)來說，FCMC首先將它們分成c個模糊組，然后求出每個類別的聚類中心，同時，要最優化價值函數(見式(3))，也就是將非相似性指標值達到最小。

(3)

使式(3)達到最小的必要條件為：

(4)

(5)

FCMC算法包括以下四個步驟：

步驟1：隨機生成0到1之間的數，并用來隨機化隸屬度矩陣U。

步驟2：用表示價值函數最優化條件(見式(4))計算出c個聚類中心ci,i=1,2,…,c。

步驟3：用式(3)計算價值函數。如果它相對上次價值函數值的改變量小于某個閾值，或者大于某個閾值，那么算法停止。

步驟4：用隸屬度(見式(5))重新計算隸屬度矩陣U，然后重復步驟2。

盡管FCMC算法能快捷地判定數據集中樣本的類別，但是該算法屬于無監督學習，必須先確定一個聚類簇數。如何確定最佳的聚類簇數以達到最好的聚類效果便是聚類有效性問題。

3 基于模糊C均值聚類有效性的協同過濾算法

在協同過濾推薦算法中，影響推薦精度的關鍵問題在于用戶評分數據的極度稀疏性。事實上，由于協同過濾是在有相似愛好的用戶間進行的，用戶更可能選擇有相似特征的項目。因此，可以用FCMC算法將屬性特征上相似的項目聚成一類，然后在一類項目中尋找用戶的最近鄰居，以提高協同過濾算法的精度。

基于FCMC的協同過濾算法的關鍵在于確定最佳聚類數cmax。因此，文中首先計算不同聚類的有效性函數值，然后采用改進的Xie-Beni方法[15]選擇cmax。

3.1 四類有效性函數

模糊C均值聚類算法屬于無監督學習，為了確定FCMC算法的最佳聚類數，國內外學者提出了一些有效性判別函數，主要分為兩類：

一類是基于模糊劃分的方法，認為好的聚類對應于數據集是較分明較清晰的，代表函數如Bezdek提出的分割系數VPC和分割熵VPE[20]；

另一類是基于幾何結構的方法，認為每個子類應當是緊致的子類與子類相互間盡可能分離，代表函數有Xie和Beni的VXB[16]、Fukuyama和Sugeno的VFC[21]、Kwon的VK[22]等。

(6)

(7)

(8)

(9)

事實上在評價聚類結果時這四個有效性函數不一定同時達到最優，FCMC算法中最優的聚類數的確定至今沒有一個最優準則，只能結合多個有效性判別函數對最優聚類數進行判斷。然而，通常這樣認為：在多個有效性函數取得較優值對應的聚類數為最佳聚類數。

3.2 算法描述

基于模糊C均值聚類有效性的協同過濾算法(FCMC CF)的具體步驟如下：

步驟1：最佳聚類數的確定。

步驟2：構造用戶-模糊簇評價偏好矩陣。

用cmax對項目進行FCMC聚類，產生相應的模糊簇，并用式(10)計算每個項目對應某個模糊簇中的隸屬度。

(10)

其中，xi為每個項目的屬性特征向量；mj代表每個模糊簇中心的屬性特征向量；‖xi-mj‖為項目i與模糊簇j的相近程度(即歐幾里德距離)；c代表模糊簇的數目。

通過原始稀疏用戶-項目評價矩陣中的評分值和隸屬度矩陣中項目屬于某個模糊簇的隸屬度，可以通過式(11)來計算得到用戶對某個模糊簇的偏好值，并構造出如表1所示的用戶-模糊簇的偏好矩陣UC，相對來說該矩陣比原始矩陣的稀疏性較低。

表1 用戶-模糊簇評價矩陣

其中，偏好值的計算如式(11)所示：

(11)

其中，PCu,j為用戶u對模糊簇j的評價值；Ru,i為用戶u對模糊簇j中的項目i的評價值；Iu為所有用戶u已經評價的項目集合。

步驟3：計算用戶的最近鄰居集合。

使用上一步計算出來的稀疏性較低的用戶-模糊簇偏好矩陣來計算并形成目標用戶的最近鄰集合。用戶u和v之間的相似度按式(1)計算。

步驟4：為目標用戶形成推薦。

從用戶最近鄰集合中選出目標用戶的K個近鄰，并根據式(2)來預測目標用戶對沒有評分過的項目的評分。然后，對預測評分進行排序，使用TOP-N策略進行推薦，即篩選出最高的N項推薦給目標用戶。

4 實驗與結果分析

4.1 數據集和度量標準

文中在實驗中使用的數據是美國Minnesota大學GroupLens項目組提供的Movielens數據集ml-100k中的u2數據。該數據集包含了943名用戶對1 682部電影的評價(評分值為數字1到5，如果數值越高則用戶喜愛該電影的程度越高)，并含有電影項目的分類特征。該數據集僅包含評價過20部以上電影的用戶評價數據，沒有評分的電影數據占所有數據的比重(稀疏度)為93.7%。

文中使用平均絕對偏差(MAE)、召回率(Recall)和覆蓋率(Coverage)來度量算法的推薦質量。其中，MAE表示推薦算法對目標用戶的預測評分與目標用戶的實際評分的偏差值，這個指標可以用來評價推薦算法做出預測的誤差，如果推薦質量越高，那么MAE的值越小。MAE定義為：

(12)

一般來說，Recall和Coverage可以較好地評價某個網站對目標用戶做出推薦的預測準確率。

推薦結果的召回率定義為：

(13)

推薦結果的覆蓋率定義為：

(14)

4.2 實驗結果

通過選取電影所屬的類型作為項目的屬性特征，文中做了以下幾個實驗來驗證提出推薦算法的有效性。

(1)確定最佳聚類數。

首先，通過比較不同聚類數相應的聚類有效性函數值來選出最佳聚類數cmax。實驗結果如圖1所示，具體的函數值如表2所示。

圖1 不同聚類數對應的聚類有效性函數值 表2 不同聚類數對應的有效性函數值

cVPEVXBVFCVK20.80770.0000797.170.000031.12630.0000403.520.000141.35640.0001221.330.000151.54060.0001114.060.000261.69720.000243.6780.000571.83360.0003-5.81130.000781.95410.0005-42.4140.000992.06180.0005-70.5520.0010102.15900.0007-92.8450.0014112.24750.0189-110.930.0493122.32870.0001-125.910.0001……403.48670.5651-407.830.2306

表3 Xie-Beni方法確定的cmax

(2)MAE比較。

使用上面得到的最優聚類數cmax對訓練數據集合進行模糊C均值聚類，并比較了傳統的協同過濾推薦方法(CF)和K-means聚類協同過濾推薦方法(KmeansCF)的結果，如圖2所示，取最優聚類數cmax為12的實驗結果。

圖2 不同算法MAE的比較

實驗結果表明，FCMC得到的MAE值要優于CF算法和KmeansCF。

(3)召回率和覆蓋率的比較。

在接下來的TOP-N實驗中，選擇FCMCCF算法與CF和KmeansCF在召回率、覆蓋率指標上進行比較。結果如圖3和圖4所示。

圖3 不同算法召回率的比較

4.3 實驗結果分析

如圖2～4所示，FCMC CF算法在不同的最近鄰水平下比CF算法以及Kmeans CF算法具有較小的MAE值，即新算法在推薦精度上有所改善；同時，FCMC CF算法在不同的最近鄰水平下比CF算法以及Kmeans CF算法具有更高的召回率和覆蓋率，有效地改進了推薦精度。

圖4 不同算法覆蓋率的比較

5 結束語

當下，電子商務的流行導致了電商網站的規模越來越大，與此同時，網站上的用戶和物品數據也隨之增長，推薦系統面臨著數據稀疏與可擴展性問題。

針對以上問題，文中提出基于模糊C均值聚類有效性的協同過濾算法。首先通過聚類有效性函數和改進的Xie-Beni方法[15]確定了FCMC算法的最佳聚類數。其次根據屬性特征對項目進行FCMC聚類，緩解了數據的稀疏問題，通過與Kmeans CF實驗進行比較，更符合一個項目可能同屬于幾個類的實際情況。最后，對密集的用戶-模糊簇的評價偏好矩陣進行協同過濾，由于簇的數目遠遠小于項目的數目，降低了推薦算法在時間上的計算復雜度。

該算法在MovieLens數據集上的實驗結果表明，它可以較好地提高推薦系統的MAE、召回率和覆蓋率。然而，該算法在不同數據集上評價標準下的表現還需要進一步的研究才能證實。此外，社交媒體的流行為推薦系統提供了更多的用戶社會信息，因此，如何將其應用到推薦系統中也值得進一步研究。

[1] Resnick P,Varian H R.Recommender systems[J].Communications of the ACM,1997,40(3):56-58.

[2] Sarwar B,Karypis G,Konstan J,et al.Analysis of recommendation algorithms for e-commerce[C]//Proceedings of the 2nd ACM conference on electronic commerce.[s.l.]:ACM,2000:158-167.

[3] Konstan J A,Miller B N,Maltz D,et al.GroupLens:applying collaborative filtering to Usenet news[J].Communications of the ACM,1997,40(3):77-87.

[4] 鄧愛林,朱揚勇,施伯樂.基于項目評分預測的協同過濾推薦算法[J].軟件學報,2003,14(9):1621-1628.

[5] 鄧愛林,左子葉,朱揚勇.基于項目聚類的協同過濾推薦算法[J].小型微型計算機系統,2004,25(9):1665-1770.

[6] Acilar A M,Arslan A.A collaborative filtering method based on artificial immune network[J].Expert Systems with Applications,2009,36(4):8324-8332.

[7] Tsi C F,Hung C.Cluster ensembles in collaborative filtering recommendation[J].Applied Soft Computing,2012,12(4):1417-1425.

[8] 查文琴,梁昌勇,曹 鐳.基于用戶聚類的協同過濾推薦方法[J].計算機技術與發展,2009,19(6):69-71.

[9] 李振博,徐桂瓊,査 九.基于用戶譜聚類的協同過濾推薦算法[J].計算機技術與發展,2014,24(9):59-62.

[10] 查 九,李振博,徐桂瓊.基于組合相似度的優化協同過濾算法[J].計算機應用與軟件,2014,31(12):323-328.

[11] 張海燕,顧 峰,姜麗紅.基于模糊簇的個性化推薦方法[J].計算機工程,2006,32(12):65-67.

[12] 李 華,張 宇,孫俊華.基于用戶模糊聚類的協同過濾推薦研究[J].計算機科學,2012,39(12):83-86.

[13] Birtolo C,Ronca D,Armenise R,et al.Personalized suggestions by means of collaborative filtering:a comparison of two different model-based techniques[C]//Proceedings of 2011 third world congress on nature and biologically inspired computing.[s.l.]:[s.n.],2011:444-450.

[14] 張付志,常俊風,周全強.基于模糊C均值聚類的環境感知推薦算法[J].計算機研究與發展,2013,50(10):2185-2194.

[15] 于 劍,程乾生.模糊聚類方法中的最佳聚類數的搜索范圍[J].中國科學:E輯,2002,32(2):274-280.

[16] Xie X L,Beni G.A validity measure for fuzzy clustering[J].IEEE Trans on Pattern Analysis and Machine Intelligence,1991,13(8):841-847.

[17] Bezdek J C.Pattern recognition with fuzzy objective function algorithms[M].New York:Plenum Press,1981.

[18] Berget L,Mevik B H,Nis T.New modifications and applications of fuzzy C-means methodology[J].Computational Statistics & Data Analysis,2008,52(5):2403-2418.

[19] 馬 軍,邵 陸.模糊聚類計算的最佳算法[J].軟件學報,2001,12(4):578-581.

[20] Bedzek J C.Cluster validity with fuzzy sets[J].Journal of Cybernetics,1973,3(3):58-72.

[21] Fukuyama Y,Sugeno M.A new method of choosing the number of clusters for the fuzzy c-means method[C]//Proceedings of the fifth fuzzy systems symposium.[s.l.]:[s.n.],1989:247-250.

[22] Kwon S H.Cluster validity index for fuzzy clustering[J].Electronics Letters,1998,34(22):2176-2177.

A Collaborative Filtering Algorithm Based on Fuzzy C-means Clustering Validity

GE Lin-tao,XU Gui-qiong

(School of Management,Shanghai University,Shanghai 200444,China)

Considering the sparsity and the scalability of traditional collaborative filtering recommendation algorithms in electronic commerce system,a new collaborative filtering algorithm is presented based on fuzzy C-means clustering validity.Firstly,a reasonable cluster number range is presetted,and then an optimal cluster number is determined based on some representative fuzzy clustering validity functions and Xie-Beni method.Secondly,using the optimal number of cluster,this algorithm transforms the users’ preferences of single item to similar groups with fuzzy C-means clustering,and sparse user-item preferences is established to dense user-fuzzy preferences.Finally,according to the item’s cluster it finds the nearest neighbors of the object user and generates recommendations.The experimental results in MovieLens show that the new algorithm improves recommendation quality in MAE,recall and coverage.

collaborative filtering;fuzzy C-means clustering;clustering validity;optimal number of clustering

2015-04-30

2015-08-06

時間：2016-01-04

國家自然科學基金資助項目(11201290，61104042)

葛林濤(1990-)，男，碩士研究生，研究方向為數據挖掘、個性化推薦；徐桂瓊，博士，教授，博士生導師，研究方向為數據挖掘與人工智能、復雜系統建模。

http://www.cnki.net/kcms/detail/61.1450.TP.20160104.1505.028.html

TP391

A

1673-629X(2016)01-0022-05

10.3969/j.issn.1673-629X.2016.01.005