基于樸素貝葉斯降噪的協(xié)同過濾算法

鄧立國, 何明訓(xùn)

(沈陽師范大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院, 沈陽 110034)

0 引 言

隨著互聯(lián)網(wǎng)技術(shù)與電子商務(wù)的高速發(fā)展,個(gè)性化、精準(zhǔn)化的信息推薦形式慢慢取代了依靠“廣撒網(wǎng),多撈魚”的傳統(tǒng)高成本、低效率的推薦形式,成為了各大行業(yè)目光聚集的焦點(diǎn)。個(gè)性化推薦系統(tǒng)出現(xiàn)于上世紀(jì)九十年代,并在近年在電子商務(wù)網(wǎng)站如當(dāng)當(dāng)網(wǎng)、亞馬遜、電影視頻網(wǎng)站和信息交互網(wǎng)站,均得到了廣泛的應(yīng)用。依托于現(xiàn)今大數(shù)據(jù)時(shí)代規(guī)模龐大的數(shù)據(jù)信息,推薦算法能夠通過其中蘊(yùn)含的具體用戶的行為特征或購買偏好,找到真正吸引用戶眼球的信息或產(chǎn)品,同時(shí)可以側(cè)面屏蔽掉許多用戶不感興趣卻又深受其害的流氓廣告,提高用戶的整體瀏覽體驗(yàn)。協(xié)同過濾推薦算法(CF)是最早出現(xiàn)同時(shí)也應(yīng)用最廣的一種推薦算法[1]。它通過計(jì)算收集的數(shù)據(jù)之間的相似性來找到最相似的集合,推薦給用戶。但收集到的用戶數(shù)據(jù),作為用戶在使用網(wǎng)絡(luò)過程中產(chǎn)生的痕跡,錯(cuò)綜復(fù)雜,良莠不齊,其中存在著大量的垃圾數(shù)據(jù)和用戶的誤操作。據(jù)2017年統(tǒng)計(jì)顯示,在點(diǎn)評(píng)分享類網(wǎng)站“大眾點(diǎn)評(píng)”和電商網(wǎng)站“淘寶網(wǎng)”上,用戶根據(jù)所購買商品情況或服務(wù)體驗(yàn)對(duì)店家和商品進(jìn)行評(píng)論與打分[2],可識(shí)別出的無效和垃圾評(píng)論比率均高達(dá)40%。大量的無意義單純湊字?jǐn)?shù)的垃圾信息或者“水軍”留下的或褒或貶的干擾信息充斥于這些評(píng)論之中,將這些數(shù)據(jù)直接拿來進(jìn)行推薦會(huì)產(chǎn)生巨大的誤差和不必要的額外損耗,極大的影響推薦結(jié)果的精準(zhǔn)性和時(shí)效性。因此,如何準(zhǔn)確地篩選出無效信息,更好地對(duì)初始數(shù)據(jù)集進(jìn)行降噪處理,減少垃圾信息對(duì)推薦結(jié)果的干擾這一課題一直是推薦算法研究者心中的重中之重。

經(jīng)過多年的發(fā)展,對(duì)于如何給用戶文本型數(shù)據(jù)進(jìn)行降噪處理,研究者們已經(jīng)有了一些相對(duì)成熟的方法:基于規(guī)則的方式常見于很多社交網(wǎng)站,這種方法強(qiáng)制用戶在發(fā)表評(píng)論之前輸入驗(yàn)證碼,通過驗(yàn)證才可以正常發(fā)表評(píng)論,但這種做法極大地影響了用戶的操作體驗(yàn),也不能區(qū)分那些水軍和用戶的無關(guān)隨意評(píng)論;基于黑白名單方式檢驗(yàn)用戶Ip是否存在于黑名單,大多使用ISCBL對(duì)IP進(jìn)行實(shí)時(shí)監(jiān)控[3],若用戶在某時(shí)間段內(nèi)重復(fù)提交有相同數(shù)字或者相同域名的外網(wǎng)地址,則將此用戶IP列入黑名單之中。此種方法準(zhǔn)確率較高,但網(wǎng)站的監(jiān)控規(guī)則被獲知后,非法者可針對(duì)此規(guī)則改變文本的廣告形式或使用軟件形式[4]。其他一些方法如Jindal和Liu[5-6]將此類垃圾信息分成非評(píng)論信息、不相關(guān)評(píng)論和欺騙性評(píng)論,通過對(duì)選取評(píng)論文本、評(píng)論者和商品3個(gè)方面36個(gè)特征建立邏輯回歸模型ACU來應(yīng)對(duì)這種問題;Peng等[7]以評(píng)論內(nèi)容和文本情感分析的方法將其分為3類,確立了3條垃圾評(píng)論規(guī)則;Savage等[8]通過計(jì)算垃圾評(píng)論的評(píng)分與正常評(píng)分平均分的差異,篩選出不符常態(tài)的評(píng)分項(xiàng)加以排除;Lai[9]通過模型計(jì)算2個(gè)不同評(píng)論之間的相似性,找出是否有一條評(píng)論出自于另一條評(píng)論,最后使用向量積來進(jìn)行區(qū)分。這些方法都有著各自的優(yōu)勢,但均有著自身成本太高、局限性太強(qiáng)等缺陷。

本文擬采用樸素貝葉斯分類來對(duì)推薦系統(tǒng)數(shù)據(jù)集進(jìn)行前期降噪處理,再運(yùn)用協(xié)同過濾的方法進(jìn)行推薦。樸素貝葉斯分類算法是貝葉斯分類中最具代表性的一種分類方法,它穩(wěn)定高效,適合處理多分類數(shù)據(jù),對(duì)缺失數(shù)據(jù)也不敏感,通過這種方法對(duì)獲取到的用戶行為數(shù)據(jù)集進(jìn)行篩選,降噪處理之后再進(jìn)行推薦會(huì)得到更精準(zhǔn)的推薦結(jié)果,用戶滿意度也會(huì)更高。

1 樸素貝葉斯分類

1.1 樸素貝葉斯算法

貝葉斯定理是英國數(shù)學(xué)家貝葉斯提出的一種計(jì)算概率的方法,其原理是通過對(duì)過去事物發(fā)生的概率(先驗(yàn)概率)計(jì)算出事物當(dāng)前出現(xiàn)的概率(后驗(yàn)概率),然后選擇當(dāng)前出現(xiàn)概率最大的類作為該事物的所屬的類。貝葉斯定理如下:

(1)

其中:P(A)是A的先驗(yàn)概率,即不考慮B情況發(fā)生與否時(shí)A發(fā)生的概率;P(A|B)是已知B發(fā)生后A的概率,即A的后驗(yàn)概率;P(B|A)是B的后驗(yàn)概率,P(B)是B的先驗(yàn)概率。

貝葉斯定理在機(jī)器學(xué)習(xí)領(lǐng)域衍生出了很多種分類方法,其中最為基本的、應(yīng)用最為廣泛的分類方法是樸素貝葉斯算法[10]。樸素貝葉斯算法是在貝葉斯算法的基礎(chǔ)之上進(jìn)行條件獨(dú)立假設(shè),先找到一個(gè)已分類的樣本組成訓(xùn)練樣本集,設(shè)待分類項(xiàng)x(a1,a2,…,am),其中每個(gè)a為x的一個(gè)特征屬性,并假設(shè)特征之間相互獨(dú)立;類別集合C(y1,y2,…,yn),需計(jì)算特征屬性屬于各個(gè)類別的概率P(yi|aj),因?yàn)槊總€(gè)特征之間是相互獨(dú)立的,所以根據(jù)貝葉斯定理:

(2)

因?yàn)楦魈卣髦g是相互獨(dú)立的,所以可得該樣本屬于yi類的概率為樣本中各屬性出現(xiàn)時(shí)屬于yi類的值之積。公式為

(3)

所得所有概率中最大值對(duì)應(yīng)的類別就是該待分類項(xiàng)所屬的類別。公式如下:

P(yk|x)=max{P(y1|x),P(y2|x),…,P(yn|x)},則x∈yk

(4)

1.2 構(gòu)建貝葉斯分類器的訓(xùn)練模型

1.2.1 分解語句并提取關(guān)鍵詞

本節(jié)對(duì)淘寶中的評(píng)論進(jìn)行樸素貝葉斯分類,試找出其中的垃圾評(píng)論。因?yàn)槭菂^(qū)分評(píng)論是否屬于垃圾評(píng)論,所以可以把它視為簡單的二分類問題,即C(y1,y2)。C=y1,評(píng)論為垃圾評(píng)論,C=y2則為非垃圾評(píng)論。使用爬蟲軟件從淘寶中爬取商品評(píng)論,整理之后選取一下6條主題為“外套”的評(píng)論作為訓(xùn)練樣本進(jìn)行分析與建模。

1) 質(zhì)量不錯(cuò),款式很好看,尺碼標(biāo)準(zhǔn),穿著很舒服,很滿意！

2) 衣服太薄了,質(zhì)量也不好,不值這個(gè)價(jià)格。

3) 衣服性價(jià)比太低,鄰居買的別家的價(jià)格好便宜才80還送長袖,他家的貴好多,衣服很薄而且不送的長袖質(zhì)量不好,下回我也去狼途買了。

4) 質(zhì)量感覺一般吧。衣服薄,天稍微涼一點(diǎn)這衣服就不適合了。

5) 給老公買的,款式很好看,顯年輕,而且款式質(zhì)量也很不錯(cuò),非常滿意！

6) 月末了,該確認(rèn)收貨的商品記得確認(rèn)收貨。記得寫評(píng)價(jià)的時(shí)候多湊點(diǎn)字?jǐn)?shù),最好附上曬圖,加積分。 淘寶有個(gè)88會(huì)員,積分1 000以上的淘寶用戶可以每年88元的價(jià)格購買,淘寶買東西打88折！很快就能回本！

其中1)、2)、4)、5)條評(píng)論為非垃圾評(píng)論,3)、6)兩條評(píng)論為垃圾評(píng)論。依次提取幾條文本中的關(guān)鍵詞:Item1[“質(zhì)量”“款式”“尺碼”];Item2[“量”“薄”“值”]等特征數(shù)據(jù),取它們并集得到的特征數(shù)據(jù)為[“質(zhì)量”“款式”“尺碼”“薄”“別家”“值”“評(píng)價(jià)”“曬圖”“會(huì)員”“字?jǐn)?shù)”“積分”“回本”]。

1.2.2 構(gòu)建矩陣

利用得到的特征數(shù)據(jù)構(gòu)建矩陣,矩陣的列為樣本編號(hào),矩陣的行為關(guān)鍵詞特征屬樣本包含此特征屬性,則在對(duì)應(yīng)處標(biāo)1;樣本不包含此屬性,則標(biāo)0。最后一列為本評(píng)論文本是否屬于垃圾評(píng)論,是為y1,否為y2。

表1 樣本特征矩陣Tab.1 Characteristic matrix

其中評(píng)論樣本1所對(duì)應(yīng)的特征屬性向量為[1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]。

1.2.3 樸素貝葉斯分類

首先計(jì)算出每一個(gè)特征屬性出現(xiàn)時(shí)分別為垃圾評(píng)論和非垃圾評(píng)論的具體概率。根據(jù)貝葉斯定理可求:P(y1丨質(zhì)量)=2/5,P(y2丨質(zhì)量)=3/5;P(y1丨款式)=0,P(y2丨款式)=1;P(y1丨尺碼)=0,P(y2丨尺碼)=1;P(y1丨薄)=1/3,P(y2丨薄)=2/3;P(y1丨別家)=1,P(y2丨別家)=0;P(y1丨值)=2/3,P(y2丨值)=1/3;P(y1丨評(píng)價(jià))=1,P(y2丨評(píng)價(jià))=0;P(y1丨曬圖)=1,P(y2丨曬圖)=0;P(y1丨會(huì)員)=1,P(y2丨會(huì)員)=0;P(y1丨字?jǐn)?shù))=1,P(y2丨字?jǐn)?shù))=0;P(y1丨積分)=1,P(y2丨積分)=0;P(y1丨回本)=1,P(y2丨回本)=0。

當(dāng)一個(gè)新的樣本例如“質(zhì)量一般吧。衣服薄,天稍微涼一點(diǎn)這衣服就不值了?！背霈F(xiàn)時(shí),先初始化一個(gè)和詞庫等長的特征數(shù)據(jù)[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],之后按上面步驟對(duì)特征屬性進(jìn)行遍歷得到新的特征數(shù)據(jù)為[1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0],假設(shè)關(guān)鍵詞特征值之間是相互獨(dú)立的,用樸素貝葉斯公式計(jì)算出新樣屬于垃圾評(píng)論的概率P(y1丨x)和屬于非垃圾評(píng)論的概率P(y2丨x)。

P(y1丨x)=0.088 888 889

2 協(xié)同過濾推薦算法

2.1 算法概述

協(xié)同過濾是一種基于一組最相似用戶或項(xiàng)目的集合進(jìn)行推薦的方法,在現(xiàn)今各大推薦算法之中,它的推薦效率非常高,并且應(yīng)用范圍最為廣泛。協(xié)同過濾的中心思想是“物以類聚,人以群分?！眳f(xié)同過濾推薦算法一般分為2種,一種是基于User(用戶)的協(xié)同過濾推薦算法,另一種是基于Item(項(xiàng)目)的協(xié)同過濾推薦算法[11]?；谟脩舻膮f(xié)同過濾推薦算法通過探究用戶的行為特征和偏好來發(fā)掘出用戶和用戶之間的聯(lián)系,找到用戶的最近鄰集合,將相似用戶喜歡的物品互相推薦給別的用戶;而基于項(xiàng)目的協(xié)同過濾則通過用戶的行為特征和偏好信息,計(jì)算出物品與物品之間的相似度,然后找到物品的最近鄰集合,最后根據(jù)用戶的歷史偏好信息,將此集合中的其他物品推薦給用戶[12]。本文采用基于Item(項(xiàng)目)的協(xié)同過濾推薦算法。基于項(xiàng)目的協(xié)同過濾算法假設(shè)用戶A喜歡電影1和電影3,用戶B喜歡電影1、電影2和電影3,用戶C喜歡電影1,從這些用戶的歷史喜好可以分析出電影1和電影3是比較類似的,喜歡看電影的人都喜歡看電影3,基于這個(gè)數(shù)據(jù)可以推斷用戶C很有可能也喜歡電影3,所以系統(tǒng)會(huì)將電影3推薦給用戶C[13]。

2.2 用戶評(píng)分矩陣

協(xié)同推薦系統(tǒng)首先要獲取用戶以前的消費(fèi)、評(píng)價(jià)、瀏覽信息以及項(xiàng)目屬性信息,并對(duì)這些數(shù)據(jù)進(jìn)行數(shù)據(jù)預(yù)處理得到一個(gè)User-Item-Rating(用戶-項(xiàng)目-評(píng)分)用戶項(xiàng)目評(píng)分。如圖:其中,m表示用戶數(shù),n表示項(xiàng)目數(shù),rui,j則表示用戶ui對(duì)項(xiàng)目j的評(píng)分值,通常情況下這個(gè)評(píng)分值的范圍為1～5,其中1代表不喜歡,數(shù)值變大好感度依次遞增,數(shù)值5代表非常喜歡,如果沒有對(duì)該項(xiàng)目進(jìn)行評(píng)分的話,評(píng)分值取0。評(píng)分矩陣中的行表示用戶的評(píng)分向量,列表示物品的評(píng)分向量。

表2 用戶評(píng)分矩陣Tab.2 User-rating-data matrix

2.3 計(jì)算項(xiàng)目相似性

2.3.1 余弦相似性

余弦相似性把用戶評(píng)分矩陣看作n維項(xiàng)目空間中的向量,如果用戶對(duì)項(xiàng)目沒有評(píng)分,則將該評(píng)分值設(shè)為0。余弦相似性方法通常被應(yīng)用于文本對(duì)象,使用向量所指的夾角值來表示相似性,計(jì)算用戶之間的相似性時(shí),把評(píng)分矩陣中的數(shù)據(jù)看成向量,二向量之間的夾角余弦值則為2個(gè)用戶之間的相似值,并且與用戶的相似值成正比,

計(jì)算兩向量x,y之間的夾角余弦值為

(5)

則余弦相似性計(jì)算的公式如下:

(6)

其中:cos(a,b)表示用戶a與b的余弦相似度;Ra,j和Rb,j分別代表用戶a和b對(duì)j項(xiàng)的評(píng)分;Iab表示用戶a和b共同評(píng)價(jià)過的所有項(xiàng)目。

余弦相似性的特點(diǎn)是將0賦值給用戶未評(píng)分的所有項(xiàng),這么做有優(yōu)有劣:優(yōu)點(diǎn)是一般情況下有效地提高了計(jì)算效率,缺點(diǎn)是未充分考慮到數(shù)據(jù)稀疏性的問題,即用戶對(duì)未評(píng)分項(xiàng)目的評(píng)分不可能都為0。而且,有的用戶普遍給的高一些,有的用戶普遍給的低一些,沒有一個(gè)統(tǒng)一的尺度來對(duì)用戶評(píng)分進(jìn)行把控。在這些情況下,單純的使用余弦相似性就不太適宜了,應(yīng)該采用修正的余弦相似性來計(jì)算[14]。

2.3.2 修正余弦相似性

余弦相似性認(rèn)為所有用戶的評(píng)分習(xí)慣都一樣,但考慮到上文說到的評(píng)價(jià)尺度不同的原因,應(yīng)該對(duì)其進(jìn)行區(qū)別處理。修正余弦相似性度量方法通過減去用戶對(duì)項(xiàng)目的平均評(píng)分,改善了余弦相似性度量方法的這個(gè)缺陷。公式如下:

(7)

2.4 最終推薦

(8)

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

本文采用的數(shù)據(jù)集為2018年2月從豆瓣電影網(wǎng)站上爬取下來的豆瓣電影短評(píng)數(shù)據(jù)集,豆瓣電影具有國內(nèi)最權(quán)威的電影評(píng)分和精彩影評(píng),包含著中國千萬影迷的真實(shí)觀影感受和體驗(yàn)。目前豆瓣電影用戶規(guī)模已超過億人,用戶評(píng)分的電影已超過8 000部。該豆瓣電影短評(píng)數(shù)據(jù)集包括電影ID(MOVIEID)、用戶信息(ID/IP)、評(píng)論時(shí)間(TIME)、用戶評(píng)分(RATING)和用戶短評(píng)(CONTENT)5個(gè)部分,數(shù)據(jù)存儲(chǔ)使用的是SQLite數(shù)據(jù)庫,其中用戶評(píng)分為1～5分,總計(jì)差評(píng)1～2分評(píng)論177 714條,中評(píng)3分評(píng)論107 687條,好評(píng)4～5評(píng)論224 229條。

選擇其中的3 000條評(píng)論信息測試集進(jìn)行實(shí)驗(yàn),首先采用樸素貝葉斯算法和基于規(guī)則的方法對(duì)該集合進(jìn)行降噪處理, 然后將得到的有效數(shù)據(jù)集重新劃分為訓(xùn)練集和測試集2個(gè)部分。其中80%為訓(xùn)練集,剩下的20%為測試集。

評(píng)價(jià)推薦系統(tǒng)推薦質(zhì)量的度量標(biāo)準(zhǔn)一般有2種:統(tǒng)計(jì)精度度量方法和決策支持精度度量方法,其中應(yīng)用最為廣泛的是出自于統(tǒng)計(jì)精度度量方法中的平均絕對(duì)誤差MAE(mean absolute error),公式如下:

(9)

MAE通過計(jì)算預(yù)測的用戶評(píng)分與實(shí)際的用戶評(píng)分之間的偏差來度量預(yù)測的準(zhǔn)確性,MAE越小,推薦質(zhì)量越高。預(yù)測的評(píng)分集合表示為{p1,p2,…,pn}實(shí)際的評(píng)分集合表示為{q1,q2,…,qn}。

圖1 MAE表Fig.1 MAE Table

為了檢驗(yàn)本文提出方法的有效性,以通過樸素貝葉斯算法進(jìn)行降噪處理再通過基于項(xiàng)目的協(xié)同過濾算法與基于規(guī)則的協(xié)同過濾推薦算法和常見的通過黑白名單方法降噪處理再進(jìn)行推薦的方法作以比較,計(jì)算其MAE,實(shí)驗(yàn)結(jié)果如圖1所示。

由圖1可知,基于樸素貝葉斯降噪再進(jìn)行推薦的方法得到的MAE最小,因此,與單純通過協(xié)同過濾推薦算法的結(jié)果和經(jīng)過基于黑白名單和其他規(guī)則的方式降噪再進(jìn)行推薦相比,本文所采用的方法可以顯著地提高推薦的精度和質(zhì)量。基于這種更優(yōu)的結(jié)果進(jìn)行廣告投放,會(huì)起到更加良好的效果。

4 結(jié) 論

通過在進(jìn)行基于項(xiàng)目的協(xié)同過濾推薦算法前,用樸素貝葉斯算法對(duì)數(shù)據(jù)集進(jìn)行降噪預(yù)處理,可以有效減少垃圾評(píng)論和無效評(píng)分對(duì)其的干擾,更優(yōu)化協(xié)同過濾的推薦質(zhì)量,再進(jìn)行廣告投放可以顯著地提高投放的精度,達(dá)到更優(yōu)的效果。