概率粗糙集模型在推薦算法中的應用

陳功平,王 紅

六安職業技術學院 信息與電子工程學院,安徽 六安 237158

概率粗糙集模型在推薦算法中的應用

陳功平,王 紅

六安職業技術學院 信息與電子工程學院,安徽 六安 237158

推薦算法能夠挖掘用戶的潛在興趣將項目自動地推薦給客戶，是解決信息過載的智能手段之一。由于網絡中的用戶數和項目數較多，評分矩陣的稀疏性嚴重影響了推薦效果，推薦的先驗知識缺失嚴重。粗糙集是一種可以使用不完備的知識實施推理的有效方法，使用概率粗糙集的α、β閾值合理劃分邊界域，生成推薦策略，降低評分矩陣稀疏性對推薦結果的影響。實驗結果表明：概率粗糙集模型能夠有效提高在評分矩陣非常稀疏的情況下的推薦準確率，其在Movie Lens數據集上的推薦準確率最高達到92.80%，覆蓋率最高達100%。

概率粗糙集;推薦算法;參數學習

網絡的普及應用讓人們習慣于從網絡上獲取信息，而隨著網絡資源的爆炸式增長，使得用戶耗費在無用信息上的時間和精力越來越多。推薦系統[1]能夠從用戶的歷史行為中挖掘用戶興趣，將和用戶興趣相關的項目主動的推薦給用戶，減少檢索時間。近年推薦算法得到了學者的廣泛關注和研究，其應用也得到各大網站的支持。

基于內容的推薦[2]（Content-Based Recommendation）、基于知識的推薦[3]（Knowledge-Based recommendation）、基于協同過濾的推薦[4]（Collaborative Filtering-Based Recommendation）等是常用的推薦算法，協同過濾推薦算法是一種簡單且常用的算法，能夠很好的與其他算法融合，是亞馬遜等商業網站推薦系統的核心算法。協同過濾推薦算法從用戶的歷史行為中學習規律，挖掘用戶喜好，然后預測用戶對未關聯的項目的喜好程度，將用戶最喜愛的Top-n項目生成推薦列表提供給用戶。

用戶對項目的評分能很好的反映用戶對項目的感興趣程度，由于網絡中的用戶和項目數量非常多，導致評分矩陣十分稀疏，降低推薦效果。粗糙集[5]是一種可以利用不完備知識實施推理的有效方法，將稀疏的評分矩陣作為粗糙集的屬性庫，使用粗糙集思想合理劃分等價類，從評分矩陣中挖掘規則實施推薦，提高推薦的效果。

實驗表明，推薦模型在100 k Movie Lens數據集上的準確率和覆蓋率最高達到92.80%和100%，比Pawlak粗糙集模型的性能更優。

1 概率粗糙集模型

概率粗糙集模型是Pawlak粗糙集模型的擴展，使用α、β參數細化Pawlak粗糙集模型的正域、負域和邊界區域而得到的一種粗糙集模型[6]。

1.1 Pawlak粗糙集模型

Pawlak模型定義了上、下近似集合，設U表示論域，R是U的一個等價關系，即將U劃分為多個不相交的R子集，可表示為U/R=｛R1,R2,…,Rn｝，現有X集合為U的子集，即，X?U，使用等價關系R來近似X，X的上近似和下近似[7]被定義如公式（1）～（2）。

其中，[x]是X的一個劃分，Ri是R集合中的一個子集，即，Ri?R。X集合下近似與上近似的比值稱為集合X的粗糙程度。

顯然0≤P(X|R)≤1，當P(X|R)=1時，集合X相對于等價關系R是精確的，當P(X|R)＜1時，集合X相對于等價關系R是粗糙的。

根據X的上下近似，可以將U劃分為不相交的正域、負域和邊界域，定義公式[8]見（4）～（6）。

正域、負域和邊界域的關系如圖1所示。整個區域表示論域U，圓表示要近似的集合X，矩形表示等價關系R，粗線實心矩形區域是X的下近似，即正域，虛線區域（去掉正域）是X的邊界域，虛線外的區域是X的負域。

圖1 正、負和邊界區域的關系Fig.1 The relation of positive、negative and boundary regions

1.2 概率粗糙集模型

從圖1可以看出，正域、負域是相互獨立的，而邊界域中，有的相交部分多，有的相交部分少，定義P(X/Ri)表示集合X與Ri等價關系的重疊程度[9]。

因此，可以使用P(X/Ri)來進一步細化X的上下近似以及正域、負域和邊界域，設置兩個參數α、β作為細化指標，定義[10]如公式（8）～（12）所示。

當參數α=1，β=0時，概率粗糙集等價于Pawlak粗糙集，當α＜1、β＞0時，Pawlak粗糙集的部分邊界域將劃分到正域和負域中，當參數α=β時，邊界域將全部劃分到正域或負域中。

2 基于粗糙集的推薦模型

基于粗糙集的推理需要從信息表中學習推理策略，表1可以看成一個基于評價矩陣的信息表，這里將評價1～3作為條件屬性，總體評價作為決策屬性，即，通過分析評價1、評價2、評價3和總體評價之間的關系，預測新用戶對總體評價的結果。

表1 滿意度調查表Table 1 Table of satisfaction survey

2.1 構造等價類

將表1條件屬性（評價1～3）取值相同的用戶歸類到同一個關系（等價類），等價類結果如表2的第1列所示，R1～R4表示等價類的名稱，花括號中的阿拉伯數字表示用戶編號。

表2 基于表1的等價類構造及條件概率計算Table 2 Equivalence class construction and conditional probability calculation on Table 1

2.2 計算決策概率

從表1～2可以得到，R1等價類的總體評價均為+，按照粗糙集推理策略，若有新用戶劃分到R1類，新用戶總體評價為+的概率為100%；R2類中，總體評價全部為-，因此R2類總體評價為+的概率為0；R3類中3、7、9用戶的總體評價為+，10用戶的總體評價為-，所以R3類的總體評價為+的概率為3/4=75%。以“總體評價”為+作為條件，每個等價類決策屬性為+的概率值結果見表2的第2列。

經過等價類構造和決策概率計算，總體評價屬性的決策表如表3所示。

表3 總體評價的決策表Table 3 Decision of overall assessment

2.3 評價指標

推薦時，找不到等價類的樣本，即無先驗知識的樣本無法完成推薦；概率粗糙集推薦模型中的邊界域樣本雖然能夠找到等價類，但因位于邊界域所以也無法完成推薦。使用準確率Precision、覆蓋率Coverage和二者的F-Score值作為推薦效果的評價指標，三個評價指標的計算公式如（13）～（15）所示。

Precision是正域樣本推薦為+、負域樣本推薦為-的數量之和與正域、負域樣本總數量的比值，即推薦正確樣本數和能夠完成推薦的樣本數的比值；Coverage是正域、負域樣本數之和與總樣本數的比值，即能夠完成推薦的樣本數與參加推薦的總樣本數的比值；通常情況下這兩個比值是互相制約的，因此使用F-Score值考察推薦結果的優劣。

按照粗糙集推理規則，將劃分到正域中的等價類的總體評價預測為+，劃分到負域中的等價類的總體評價預測為-，當α=1，β=0時，由表3的決策表可得到概率粗糙集的三個區域分別為：POS1,0(X)=R1，NEG1,0(X)=R2，BND1,0(X)=R3∪R4，邊界域無法預測，即可以為R1和R2等價類預測，無法為R3和R4等價類預測，R1類預測為+、R2類預測為-，所以預測的準確率Precision=100%，但只能為1、2、4、6號共4個用戶預測，預測的覆蓋率Coverage=4/10=40%，F-Score=57.1%。

當α=0.6，β=0時，三個區域分別為：POS0.6,0(X)=R1∪R3，NEG0.6,0(X)=R2，BND0.6,0(X)=R4，此時預測的準確率Precision=7/8=87.5%，覆蓋率Coverage=8/10=80%，犧牲了12.5%的準確率，提高了40%的覆蓋率，F-Score=83.6%。

若α、β都取0.5，則邊界域為空，即Coverage=100%，Precision=8/10=80%，F-Score=88.9%。在實際應用中，α、β參數通過學習獲得具體取值。第3節介紹概率粗糙集模型中決策表訓練和參數學習算法。

3 決策表構造和參數學習算法

將評分矩陣中的積極評分（+）標記為1，消極評分（-）標記為-1，無關項標記為0，將Precision、Coverage作為評價標準，使用訓練數據集Train構造基于概率粗糙集推薦模型的決策表、學習最優的參數α、β，然后通過測試數據集Test驗證推薦模型的推薦效果。

3.1 屬性約簡

定義U={ui|i=1,…n}表示用戶集，I={ij|j=1,…m}表示項目集，項目可以是商品、電影、新聞等，評分矩陣R={rij|i=1,…n,j=1,…m}表示用戶與項目之間的歷史行為。為了使得算法能夠適用于全數據集的推薦，因此要為所有的項目都構造出一份有用的決策表，當學習項目ij的決策表時，項目ij的有效評分作為決策屬性，項目ij以外的項目評分作為條件屬性，由于評分矩陣中的項目數量多，因此初始時條件屬性有m-1個，條件屬性數量過多不利于等價類的構造和測試時的匹配搜索，因此要減少條件屬性的數量，即屬性約簡。

將初始的m-1個條件屬性中有效評分最多的前N項屬性作為條件屬性，對于不同的數據集，N的取值不同，需要通過訓練學習得到。

3.2 決策表構造和參數學習

基于全數據集的決策表構造和參數學習算法見算法1所示。

算法1決策表構造和參數學習

輸入：訓練集評分矩陣Train，N，α'，β'

輸出：等價類Equi_Class及對應參數α、β

1.從Train中提取項目i的非0評價矩陣Train(i)

2.從Train(i)中提取除項目i外、有效評價數量最多的前N個項目的評價數據及項目i的評價數據，存入Info_Table(i)

3.從Info_Table(i)中提取項目i的等價類表Equi_Class(i)

4.α（i）=1，β（i）=0

5.α（i）-=0.01，直到α（i）＜α'或Precision(i)＜88%和Coverage(i)＜88%

6.β（i）+=0.01，直到β（i）＞β'或Precision(i)＜88%和Coverage(i)＜88%

4 實驗結果分析

使用100 k的Movie Lens[11,12]數據集驗證文中提出的推薦算法，數據集中存儲電影評分記錄10萬條，每條記錄由用戶id、電影id和評分值三項構成，評分值為1～5的整數，評分記錄情況如表4。

表4 評分表簡介Table 4 Introduction of rating

將100 k的數據按照8:2的比例劃分為訓練集Train和測試集Test，因部分電影的評分記錄較少，所以有些電影只出現在Train或Test中。

4.1 N值的訓練

以Train中有效評分較多的1號和50號電影為例，表5列出的是當N值分別設置為5、8、10、15時，得到的等價類數量與條件屬性N值的關系。

表5 N與等價類數量的關系Table 5 Relationship between N and the number of equivalent classes

N=15時，等價類個數與Train(i)的行數差值很小，即能夠被劃分到同一等價類的用戶量非常少，則劃分的集合粗糙度小，失去粗糙集推薦的意義；N=10，等價類個數降低不明顯；N=5，等價類數量減少迅速，用來劃分集合，粗糙度相對較高；若N值再降低，將導致粗糙程度加大，不利于推薦，因此N可設置為5到10之間的整數。

4.2 參數學習結果

評分表中的實際評分值為1～5的整數，為了適應粗糙集推薦模型，將5級評分簡化為2級評分，設置劃分值γ，γ=1，表示評分值1標記為-1，其余有效評分值標記為1；γ=2，表示1、2分標記為-1，其余有效評分值標記為1，以此類推。

當α'=β'=0.5（后文無特別說明，α'、β'均設置為0.5）、γ=2時，參數學習后，α、β、準確率、覆蓋率、F-Score的平均值如表6所示。

表6 訓練集訓練指標Table 6 Training index of Train

從表6可見，訓練集的平均準確率和覆蓋率指標都在90%以上。

4.3 測試結果與分析

4.3.1 測試結果分析 表7是劃分值為1時概率粗糙集模型的推薦效果。

表7 N=1時的推薦效果Table 7 Recommended effect of N=1

表中Precision=CCI/(CCI+ECI)，Coverage=(CCI+ECI)/(NF+CCI+BI+ECI)。由表7可見，N值越大，找不到等價類的記錄越多，當N=5時，Test集合的總體評價值最優，經驗證，對其他劃分值N取5時評價值都是最優，后文無特別說明N值取5。

圖2是劃分值分別取1、2、3、4，Test集合推薦效果比較，當劃分值取1時效果最優，取3時效果最差，準確率只有58.77%，整個模型的覆蓋率指標都非常高，為了提高推薦精確度，可以犧牲一定數量的覆蓋率指標值。

圖2 不同N的推薦效果比較Fig.2 Recommended effect comparison of different N

4.3.2 與Pawlak粗糙集推薦模型的比較 Pawlak粗糙集模型可以使訓練集的推薦準確率達到100%，表8是Test和Train集合劃分值分別取1、2、3、4時的三項指標值。

表8 Pawlak粗糙集模型與概率粗糙集模型性能比較Table 8 Recommended effect comparison between Pawlak and probabilistic rough set

Model列中A表示“Pawlak粗糙集模型”，B表示“概率粗糙集模型”，由數據可見，在劃分值相同時，準確率差值較小，Test集合的最大差值不到3%，覆蓋率差值較大，Test集合的最大差值達到35%，可見，概率粗糙集模型和綜合指標優于Pawlak粗糙集模型。

圖3是Test集合不同劃分值的各項指標比較。

圖3 Test集合不同N的評價指標比較Fig.3RecommendedeffectcomparisonofTestunderdifferentN

圖4 Train集合不同N值的評價指標比較Fig.4RecommendedeffectcomparisonofTrainunderdifferentN

P1、C1、F1和P2、C2、F2分別表示Pawlak模型和概率粗糙集模型下Precision、Coverage、F-Score指標的值。Train集合不同劃分值的各項指標比較(圖4)。

4.3.3 α'和β'對結果的影響 為了提高推薦準確率，應提高參數α的值，從表8可以看出，整個推薦的覆蓋率指標較好，即參數β可以不調整。將α'和β'的值平滑變化，經實驗驗證，即使將β'的值設置較高，實際得到的β都不會超過0.5，而α'的值對α影響較大，最后得到的α與α'接近。

劃分值取2，Test集合的預測結果如表9所示。

表9 α'和β'對結果的影響Table 9 Recommended effect of α'and β'

當α'取1、β'取0時，邊界域的數量最多；α'和β'都取0.5時，邊界域數量最少，所以推薦的覆蓋率指標較高。

5 結語

使用概率粗糙集理論中的α、β參數將粗糙集中的邊界域分配到正域和負域中，可以降低評分矩陣稀疏性對推薦精度的影響，采用α、β參數逐步逼近、保證推薦準確率和覆蓋率指標的參數學習算法，有效的提高了推薦效果，比Pawlak粗糙集模型的性能更優。粗糙集推薦模型的邊界域是無法實施推薦的，可以結合其他推薦算法，進一步提高推薦效果。

[1]Guan Y,Cai SM,Shang MS.Recommendation algorithm based on item quality and user rating preferences[J].Frontiers of Computer Science,2014,8(2):289-297

[2]Lops P,Gemmis MD,Semeraro G,et al.Content-based and collaborative techniques for tag recommendation:an empirical evaluation[J].Journal of Intelligent Information Systems,2013,40(1):41-61

[3]Liu XC,Zhou JC.Research on Knowledge-based Personalized Recommendation Service System Retrieval Service[J]. Energy Procedia,2011,13(4):10103-10108

[4]孫光福,吳 樂,劉 淇,等.基于時序行為的協同過濾推薦算法[J].軟件學報,2013,24(11):2721-2733

[5]Liu D,Li TR,Zhang JB.Incremental updating approximations in probabilistic rough sets under the variation of attributes[J].Knowledge-Based Systems,2015,73(1):81-96

[6]Ma XA,Wang GY,Yu H,et al.Decision region distribution preservation reduction in decision-theoretic rough set model[J].Information Sciences,2014,278(10):614-640

[7]Azam N,Yao JT.Game-theoretic rough sets for recommender systems[J].Knowledge-Based Systems,2014,72(1):96-107

[8]陳 昊,楊俊安,莊鎮泉.變精度粗糙集的屬性核和最小屬性約簡算法[J].計算機學報,2012,35(5):1011-1017

[9]徐久成,李曉艷,孫林.一種基于概率粗糙集模型的圖像語義檢索方法[J].南京大學學報:自然科學版,2011,47(4):438-445

[10]王兆浩,舒 蘭,丁修勇.幾種粗糙集模型的推廣研究[J].計算機工程與應用,2011,47(36):68-72

[11]袁漢寧,周 彤,韓言妮,等.基于MI聚類的協同推薦算法[J].武漢大學學報:信息科學版,2015,40(2):253-257

[12]田謙益,王小北.基于Memetic框架混合群智能算法的NARMAX模型參數辨識[J].山東科技大學學報:自然科學版,2013,32(1):88-94

Application of Probabilistic Rough Set Model in Recommendation Algorithm

CHEN Gong-ping,WANG Hong
College of information and Electronic Engineering/Lu’an Vocation Technology College,Lu’an 237158,China

Recommendation algorithm can dig into the potential interest of users and then automatically recommends the project to the users.It is one of the intellectual approaches solving the information overload.As the number of users and number of items are more,the sparseness of rating matrix has a strong impact on the effect of recommendation.The priori knowledge of recommendation is missing seriously.Rough set is an effective method which can adopt an incomplete knowledge to carry out ratiocination.It proposes dividing the boundary region by using probabilistic rough set threshold α and β,creating recommendation strategy and reducing the effect of the sparseness of score matrix to the recommendation result.The experimental results indicated that the model of probabilistic rough set could improve the recommendation accuracy rate under the circumstance of the high sparseness of score matrix.The recommendation accuracy rate could be up to 92.80%in the Movie Lens data sets and the highest fraction of coverage could be up to 100%.

Probabilistic Rough Set;recommendation algorithm;parameter learning

TP301

:A

:1000-2324(2017)02-0192-07

10.3969/j.issn.1000-2324.2017.02.006

2015-05-22

:2015-11-20

2015年度安徽高校自然科學研究重點項目(KJ2015A435);安徽省2016年高校優秀青年人才支持計劃重點項目(gxyqZD2016570);安徽省2014年高校優秀青年人才支持計劃

陳功平(1980-),男,碩士研究生,講師.研究方向:個性化推薦，網絡技術.E-mail:chgp06@126.com

*通訊作者:Author for correspondence.E-mail:wh0115140@126.com