陳功平,王 紅

六安職業(yè)技術(shù)學(xué)院 信息與電子工程學(xué)院,安徽 六安 237158

概率粗糙集模型在推薦算法中的應(yīng)用

陳功平,王 紅

六安職業(yè)技術(shù)學(xué)院 信息與電子工程學(xué)院,安徽 六安 237158

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

概率粗糙集;推薦算法;參數(shù)學(xué)習(xí)

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

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

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

實驗表明，推薦模型在100 k Movie Lens數(shù)據(jù)集上的準(zhǔn)確率和覆蓋率最高達(dá)到92.80%和100%，比Pawlak粗糙集模型的性能更優(yōu)。

1 概率粗糙集模型

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

1.1 Pawlak粗糙集模型

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

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

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

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

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

圖1 正、負(fù)和邊界區(qū)域的關(guān)系Fig.1 The relation of positive、negative and boundary regions

1.2 概率粗糙集模型

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

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

當(dāng)參數(shù)α=1，β=0時，概率粗糙集等價于Pawlak粗糙集，當(dāng)α＜1、β＞0時，Pawlak粗糙集的部分邊界域?qū)澐值秸蚝拓?fù)域中，當(dāng)參數(shù)α=β時，邊界域?qū)⑷縿澐值秸蚧蜇?fù)域中。

2 基于粗糙集的推薦模型

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

表1 滿意度調(diào)查表Table 1 Table of satisfaction survey

2.1 構(gòu)造等價類

將表1條件屬性（評價1～3）取值相同的用戶歸類到同一個關(guān)系（等價類），等價類結(jié)果如表2的第1列所示，R1～R4表示等價類的名稱，花括號中的阿拉伯?dāng)?shù)字表示用戶編號。

表2 基于表1的等價類構(gòu)造及條件概率計算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%。以“總體評價”為+作為條件，每個等價類決策屬性為+的概率值結(jié)果見表2的第2列。

經(jīng)過等價類構(gòu)造和決策概率計算，總體評價屬性的決策表如表3所示。

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

2.3 評價指標(biāo)

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

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

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

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

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

3 決策表構(gòu)造和參數(shù)學(xué)習(xí)算法

將評分矩陣中的積極評分（+）標(biāo)記為1，消極評分（-）標(biāo)記為-1，無關(guān)項標(biāo)記為0，將Precision、Coverage作為評價標(biāo)準(zhǔn)，使用訓(xùn)練數(shù)據(jù)集Train構(gòu)造基于概率粗糙集推薦模型的決策表、學(xué)習(xí)最優(yōu)的參數(shù)α、β，然后通過測試數(shù)據(jù)集Test驗證推薦模型的推薦效果。

3.1 屬性約簡

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

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

3.2 決策表構(gòu)造和參數(shù)學(xué)習(xí)

基于全數(shù)據(jù)集的決策表構(gòu)造和參數(shù)學(xué)習(xí)算法見算法1所示。

算法1決策表構(gòu)造和參數(shù)學(xué)習(xí)

輸入：訓(xùn)練集評分矩陣Train，N，α'，β'

輸出：等價類Equi_Class及對應(yīng)參數(shù)α、β

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

2.從Train(i)中提取除項目i外、有效評價數(shù)量最多的前N個項目的評價數(shù)據(jù)及項目i的評價數(shù)據(jù)，存入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 實驗結(jié)果分析

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

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

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

4.1 N值的訓(xùn)練

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

表5 N與等價類數(shù)量的關(guān)系Table 5 Relationship between N and the number of equivalent classes

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

4.2 參數(shù)學(xué)習(xí)結(jié)果

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

當(dāng)α'=β'=0.5（后文無特別說明，α'、β'均設(shè)置為0.5）、γ=2時，參數(shù)學(xué)習(xí)后，α、β、準(zhǔn)確率、覆蓋率、F-Score的平均值如表6所示。

表6 訓(xùn)練集訓(xùn)練指標(biāo)Table 6 Training index of Train

從表6可見，訓(xùn)練集的平均準(zhǔn)確率和覆蓋率指標(biāo)都在90%以上。

4.3 測試結(jié)果與分析

4.3.1 測試結(jié)果分析 表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值越大，找不到等價類的記錄越多，當(dāng)N=5時，Test集合的總體評價值最優(yōu)，經(jīng)驗證，對其他劃分值N取5時評價值都是最優(yōu)，后文無特別說明N值取5。

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

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

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

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

Model列中A表示“Pawlak粗糙集模型”，B表示“概率粗糙集模型”，由數(shù)據(jù)可見，在劃分值相同時，準(zhǔn)確率差值較小，Test集合的最大差值不到3%，覆蓋率差值較大，Test集合的最大差值達(dá)到35%，可見，概率粗糙集模型和綜合指標(biāo)優(yōu)于Pawlak粗糙集模型。

圖3是Test集合不同劃分值的各項指標(biāo)比較。

圖3 Test集合不同N的評價指標(biāo)比較Fig.3RecommendedeffectcomparisonofTestunderdifferentN

圖4 Train集合不同N值的評價指標(biāo)比較Fig.4RecommendedeffectcomparisonofTrainunderdifferentN

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

4.3.3 α'和β'對結(jié)果的影響 為了提高推薦準(zhǔn)確率，應(yīng)提高參數(shù)α的值，從表8可以看出，整個推薦的覆蓋率指標(biāo)較好，即參數(shù)β可以不調(diào)整。將α'和β'的值平滑變化，經(jīng)實驗驗證，即使將β'的值設(shè)置較高，實際得到的β都不會超過0.5，而α'的值對α影響較大，最后得到的α與α'接近。

劃分值取2，Test集合的預(yù)測結(jié)果如表9所示。

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

當(dāng)α'取1、β'取0時，邊界域的數(shù)量最多；α'和β'都取0.5時，邊界域數(shù)量最少，所以推薦的覆蓋率指標(biāo)較高。

5 結(jié)語

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

[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]孫光福,吳 樂,劉 淇,等.基于時序行為的協(xié)同過濾推薦算法[J].軟件學(xué)報,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]陳 昊,楊俊安,莊鎮(zhèn)泉.變精度粗糙集的屬性核和最小屬性約簡算法[J].計算機學(xué)報,2012,35(5):1011-1017

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

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

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

[12]田謙益,王小北.基于Memetic框架混合群智能算法的NARMAX模型參數(shù)辨識[J].山東科技大學(xué)學(xué)報:自然科學(xué)版,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年度安徽高校自然科學(xué)研究重點項目(KJ2015A435);安徽省2016年高校優(yōu)秀青年人才支持計劃重點項目(gxyqZD2016570);安徽省2014年高校優(yōu)秀青年人才支持計劃

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

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