郭心宇，岳 昆+，李 勁，武 浩，張彬彬

1.云南大學(xué) 信息學(xué)院，昆明 650504

2.云南大學(xué) 軟件學(xué)院，昆明 650504

面向評(píng)價(jià)數(shù)據(jù)中用戶偏好發(fā)現(xiàn)的證據(jù)理論方法*

郭心宇1，岳 昆1+，李 勁2，武 浩1，張彬彬1

1.云南大學(xué) 信息學(xué)院，昆明 650504

2.云南大學(xué) 軟件學(xué)院，昆明 650504

海量評(píng)價(jià)數(shù)據(jù)；用戶偏好；D-S證據(jù)理論；證據(jù)融合；MapReduce

1 引言

隨著Web2.0技術(shù)的普及與發(fā)展，越來(lái)越多的用戶通過(guò)各種Web平臺(tái)（例如電子商務(wù)網(wǎng)站、評(píng)論網(wǎng)站和微博等）瀏覽、發(fā)布和轉(zhuǎn)發(fā)消息。淘寶和亞馬遜等電子商務(wù)應(yīng)用中用戶對(duì)商品的評(píng)價(jià)，信息服務(wù)應(yīng)用中用戶對(duì)旅游和金融等服務(wù)的評(píng)價(jià)，都是典型的例子。2011年美國(guó)Cone公司的調(diào)查指出，64%的用戶會(huì)通過(guò)閱讀商品的相關(guān)評(píng)論來(lái)了解商品信息，87%的用戶閱讀了肯定的評(píng)論后做出購(gòu)買(mǎi)的決定，而80%的用戶閱讀了否定的評(píng)論后放棄購(gòu)買(mǎi)的意向[1]。這些評(píng)價(jià)數(shù)據(jù)通常包括用戶ID、文本形式的評(píng)論內(nèi)容（review），以及數(shù)值（例如分?jǐn)?shù)）或非數(shù)值（例如星級(jí)）形式的評(píng)分（score）等，富含了用戶的興趣、觀點(diǎn)和偏好等行為信息。對(duì)用戶產(chǎn)生的海量評(píng)價(jià)數(shù)據(jù)進(jìn)行分析和挖掘，可發(fā)現(xiàn)用戶的偏好和興趣，以及社會(huì)個(gè)體或群體的行為和心理傾向，識(shí)別行為的目標(biāo)和意圖，進(jìn)而更好地分析用戶行為的產(chǎn)生機(jī)制，并對(duì)用戶行為進(jìn)行預(yù)測(cè)，為電子商務(wù)、社交網(wǎng)絡(luò)、網(wǎng)絡(luò)輿情監(jiān)控和信息服務(wù)等各類典型的Web應(yīng)用提供理論基礎(chǔ)和支撐技術(shù)[2-3]。從評(píng)價(jià)數(shù)據(jù)對(duì)用戶偏好的影響看，其中文本形式的評(píng)論內(nèi)容，以及數(shù)值或非數(shù)值形式的評(píng)分都體現(xiàn)了用戶的偏好；同時(shí)，作為對(duì)于商品選擇傾向性的刻畫(huà)，用戶偏好也決定了用戶對(duì)商品給出的評(píng)論及評(píng)分。因此，本文同時(shí)考慮用戶評(píng)價(jià)中評(píng)論數(shù)據(jù)和評(píng)分?jǐn)?shù)據(jù)中所蘊(yùn)含的用戶偏好，旨在得到綜合全面的用戶偏好信息。

多年來(lái)，國(guó)內(nèi)外研究人員基于不同的理論框架或從不同的角度，提出了許多用戶偏好的提取或建模方法。這些方法為用戶偏好發(fā)現(xiàn)的研究提供了許多可供借鑒的思路，但仍存在一些不足之處。例如，Hong等人[3]提出一種基于Agent和決策規(guī)則的上下文感知的偏好計(jì)算，并提供相應(yīng)的個(gè)性化服務(wù)或商品的方法，但規(guī)則的確定具有一定的主觀性；Skillen等人[4]提出基于本體的偏好建模方法，但本體的設(shè)計(jì)很大程度上依賴于人的經(jīng)驗(yàn)；Yao等人[5]提出基于關(guān)聯(lián)規(guī)則的方法，但需要根據(jù)用戶反饋信息來(lái)更新用戶偏好，且計(jì)算復(fù)雜度較高；Zhang等人[6]討論了社交媒體對(duì)用戶購(gòu)買(mǎi)行為的影響，基于樸素貝葉斯和支持向量機(jī)等算法，從社交媒體學(xué)習(xí)分類器來(lái)預(yù)測(cè)用戶可能購(gòu)買(mǎi)的商品，但不能細(xì)致地描述用戶行為影響因素之間的依賴關(guān)系，且通用性較差；Tang等人[7]提出基于神經(jīng)網(wǎng)絡(luò)的用戶偏好發(fā)現(xiàn)方法，但存在局部極小點(diǎn)，且對(duì)學(xué)習(xí)、結(jié)構(gòu)和類型的選擇過(guò)分依賴于經(jīng)驗(yàn)；Harvey等人[8]針對(duì)協(xié)同過(guò)濾中的評(píng)分預(yù)測(cè)問(wèn)題，用隱變量刻畫(huà)用戶興趣和商品主題，基于圖模型和概率推理技術(shù)來(lái)預(yù)測(cè)用戶對(duì)商品的評(píng)分。

一方面，將考慮用戶評(píng)價(jià)數(shù)據(jù)中評(píng)論和評(píng)分對(duì)用戶偏好的綜合影響，而如何有效地綜合考慮多個(gè)影響因素，是近年來(lái)影響用戶偏好因素多元化背景下保證用戶偏好準(zhǔn)確性的前提。目前的方法首先給定各因素的權(quán)重，進(jìn)而以各因素及其權(quán)重的加權(quán)平均作為度量標(biāo)準(zhǔn)[9]。然而人們預(yù)先給定的權(quán)重帶有一定的主觀性，未必能客觀地反映實(shí)際情況，也忽略了各因素之間的相互聯(lián)系，當(dāng)權(quán)重未知的情況下難以度量最終的用戶偏好。

另一方面，用戶的評(píng)論數(shù)據(jù)中不同詞匯對(duì)其偏好的影響，用戶評(píng)論和評(píng)分?jǐn)?shù)據(jù)對(duì)其偏好的綜合影響，面向單個(gè)商品的偏好對(duì)面向商品類別的偏好的影響，都具有不確定性，并且詞匯、評(píng)論和評(píng)分等不同影響因素可能來(lái)自不同的觀測(cè)空間，其不確定性也從某種意義上反映了它對(duì)用戶偏好影響的權(quán)重[10]。針對(duì)實(shí)際中不同的需求，可能需要得到不同層面的用戶偏好，例如，有時(shí)可能只需要得到用戶對(duì)某類商品的偏好就可滿足應(yīng)用的需求。因此，本文考慮各層面因素的不確定性和它們之間的相互聯(lián)系，也考慮這些因素對(duì)用戶偏好影響的不確定性，研究支持以上3個(gè)層面用戶偏好發(fā)現(xiàn)的方法。

從用戶評(píng)價(jià)數(shù)據(jù)本身的特點(diǎn)看，以電子商務(wù)應(yīng)用為例，根據(jù)Alexa統(tǒng)計(jì)及數(shù)據(jù)計(jì)算，淘寶網(wǎng)的日均訪問(wèn)量達(dá)到了3.53億，除了用戶的日志記錄，也包含了用戶對(duì)商品的海量評(píng)價(jià)數(shù)據(jù)，即用戶的評(píng)價(jià)數(shù)據(jù)具有海量和非結(jié)構(gòu)化的特征[2,11]。因此，本文利用現(xiàn)有的數(shù)據(jù)密集型計(jì)算技術(shù)對(duì)海量的評(píng)價(jià)數(shù)據(jù)進(jìn)行分析計(jì)算。

具體而言，本文的主要研究工作概括如下：

（1）由Dempster提出，Shafer進(jìn)一步發(fā)展起來(lái)的D-S證據(jù)理論[12-14]，利用證據(jù)組合來(lái)計(jì)算不確定性，通過(guò)不確定性推理從不精確和不完整信息中得到可能性最大的結(jié)論，被廣泛用于信息融合、專家系統(tǒng)、情報(bào)與法律案件分析和多屬性決策分析等領(lǐng)域[15-16]。根據(jù)前述用戶偏好的影響因素的特點(diǎn)，用戶給出正面評(píng)論時(shí)未必就不會(huì)給出負(fù)面評(píng)論，因此本文基于D-S證據(jù)理論的基本思想，無(wú)需假設(shè)各影響因素不確定性的完備性，以評(píng)論中的各詞匯作為用戶評(píng)論對(duì)商品偏好的“證據(jù)”，以評(píng)論和評(píng)分作為用戶對(duì)商品偏好的“證據(jù)”，以用戶對(duì)一個(gè)類別中各商品的偏好作為對(duì)商品類別偏好的“證據(jù)”，討論用戶在以上3個(gè)層面的用戶偏好發(fā)現(xiàn)的關(guān)鍵技術(shù)。本文以第一個(gè)層面的偏好發(fā)現(xiàn)問(wèn)題為代表，定義了相應(yīng)的概率賦值函數(shù)和證據(jù)組合規(guī)則，得到不同證據(jù)對(duì)最終用戶偏好的聯(lián)合影響。

（2）Hadoop平臺(tái)下的MapReduce是支持?jǐn)?shù)據(jù)密集型計(jì)算的并行編程模型[17]，被廣泛用于云計(jì)算、數(shù)據(jù)挖掘等眾多領(lǐng)域[2,18]。因此，為了高效地從海量評(píng)價(jià)數(shù)據(jù)中發(fā)現(xiàn)用戶偏好，本文基于MapReduce編程模型對(duì)用戶評(píng)價(jià)數(shù)據(jù)進(jìn)行分析處理，提出了實(shí)現(xiàn)從用戶評(píng)價(jià)信息發(fā)現(xiàn)用戶偏好的兩趟MapReduce算法。第一趟算法得到一條評(píng)論數(shù)據(jù)中各詞匯的統(tǒng)計(jì)結(jié)果，第二趟算法得到用戶對(duì)各商品的偏好。

（3）采用MovieLens[19]的用戶評(píng)價(jià)信息作為測(cè)試數(shù)據(jù)集，對(duì)本文所提出方法的正確性、加速比和并行效率進(jìn)行了測(cè)試，實(shí)驗(yàn)結(jié)果驗(yàn)證了本文方法的有效性。

本文組織結(jié)構(gòu)如下：第2章給出用戶偏好的表示；第3章給出基于D-S證據(jù)理論從海量評(píng)價(jià)數(shù)據(jù)中發(fā)現(xiàn)用戶偏好的方法；第4章給出實(shí)驗(yàn)結(jié)果；第5章總結(jié)全文并展望將來(lái)的工作。

2 用戶偏好表示

2.1 用戶偏好定義

假設(shè)用戶對(duì)一個(gè)商品只有1條評(píng)價(jià)，表1中的示例給出了兩個(gè)用戶對(duì)4個(gè)類別中8個(gè)商品的評(píng)價(jià)信息。其中，“評(píng)論”是從用戶評(píng)論文本中所抽取的詞匯的集合。不難看出：

（1）由用戶1的評(píng)論“舒適，掉色”可知，用戶評(píng)論中的各詞匯可能反映的是相反的偏好，需要綜合考慮各詞匯對(duì)偏好的影響。

（2）綜合考慮用戶1的評(píng)論和評(píng)分可知，在服裝類商品中，用戶1更傾向于“長(zhǎng)裙”；但用戶1比用戶2更傾向于服裝類商品，還是用戶2比用戶1更傾向于服裝類商品，需要綜合考慮這兩個(gè)用戶對(duì)服裝類中各商品的偏好。

Table 1 Ratings of users on products表1 用戶對(duì)商品的評(píng)價(jià)信息

根據(jù)以上觀察，下面給出用戶偏好的定義。

定義1（用戶偏好）若u表示一個(gè)用戶，給定商品集合P={p1,p2,…,pn}和商品類別集合C=(c1,c2,…,cm)（其中，n和m分別為商品數(shù)和商品類別數(shù)，m〈n），任意商品pi(1≤i≤n)只屬于類別cj(1≤j≤m)而不屬于C中其他類別。用戶u對(duì)商品的偏好定義為一個(gè)n維向量D=(d1,d2,…,dn)，其中di(0≤di≤1)表示用戶u對(duì)商品pi的喜好程度；用戶u對(duì)商品類別的偏好定義為一個(gè)m維向量，其中(0≤≤1,1≤j≤m)表示用戶u對(duì)商品類別cj的喜好程度。

2.2 基于邊際效用的用戶偏好表示

利用信息檢索領(lǐng)域已有的關(guān)鍵詞抽取方法[20]，可以從用戶的評(píng)論文本中抽取表征用戶喜好或態(tài)度的標(biāo)識(shí)性詞匯，作為衡量評(píng)論數(shù)據(jù)對(duì)用戶偏好影響的依據(jù)，例如表1中的“舒適”和“漂亮”等正面詞匯，以及“不好”和“難看”等負(fù)面詞匯。關(guān)鍵詞的抽取不是本文研究的重點(diǎn)，在此不做贅述。

直觀地，在用戶對(duì)一個(gè)商品的評(píng)論中，正面詞匯出現(xiàn)頻度越高，負(fù)面詞匯出現(xiàn)頻度越低，說(shuō)明用戶對(duì)該商品的喜好程度越高。根據(jù)社會(huì)學(xué)及經(jīng)濟(jì)學(xué)領(lǐng)域的結(jié)論[21]，可以基于效用（utility）來(lái)描述用戶通過(guò)消費(fèi)行為使其欲望得到滿足的程度；而邊際效用（marginal utility）是指在一定時(shí)間內(nèi)用戶增加商品或服務(wù)所帶來(lái)的新增效用，與消費(fèi)的商品數(shù)量成反比，而與消費(fèi)的欲望成正比。對(duì)于一個(gè)用戶而言，把用戶評(píng)論中的正面詞匯與消費(fèi)的欲望進(jìn)行類比，正面詞匯越多，對(duì)該商品的購(gòu)買(mǎi)欲望越強(qiáng)（即喜好程度越高）；用邊際效用刻畫(huà)評(píng)論數(shù)據(jù)對(duì)用戶偏好的貢獻(xiàn)。根據(jù)上述思想，下面定義用戶評(píng)論中正面詞匯/負(fù)面詞匯對(duì)用戶偏好的影響。

定義2（邊際效用函數(shù)）設(shè)r表示用戶的一條評(píng)價(jià)，r中評(píng)論數(shù)據(jù)所包含的詞匯集合為W，用T和F分別表示W(wǎng)中正面詞匯和負(fù)面詞匯的集合，W=T∪F。正面詞匯和負(fù)面詞匯對(duì)于r的邊際效用函數(shù)分別定義為fT(T)和fF(F)，0≤fT(T)，fF(F)≤1。

根據(jù)前述邊際效用的基本思想以及消費(fèi)欲望與正面詞匯的類比關(guān)系，針對(duì)一條評(píng)價(jià)信息，定義2中邊際效用函數(shù)應(yīng)該滿足如下性質(zhì)：

（1）fT(T)的值隨著評(píng)論中正面詞匯數(shù)量的增加而增加，但增加的趨勢(shì)逐漸變緩；

（2）fF(F)的值隨著評(píng)論中負(fù)面詞匯數(shù)量的增加而減小，但減小的趨勢(shì)逐漸變緩；

（3）若評(píng)論中既有正面詞匯，又有負(fù)面詞匯，最終的效用函數(shù)值應(yīng)為fT(T)和fF(F)的折衷，且小于fT(T)和fF(F)中的較大者。

結(jié)合邊際效用的“遞減”性和以上性質(zhì)（1）～（3），下面基于指數(shù)函數(shù)來(lái)刻畫(huà)邊際效用函數(shù)值隨著評(píng)論中詞匯數(shù)量增加的變化趨勢(shì)：

其中，|T|和|F|分別表示正面詞匯和負(fù)面詞匯數(shù)量，0≤fT(T),fF(F)≤1。

基于此，可以得到fT(T)和fF(F)，即用戶的一條評(píng)論中正面詞匯和負(fù)面詞匯對(duì)用戶偏好的貢獻(xiàn)。那么，如何進(jìn)一步得到這條評(píng)論對(duì)用戶偏好的聯(lián)合貢獻(xiàn)（問(wèn)題1）？如何將一條用戶評(píng)價(jià)中的評(píng)論與評(píng)分對(duì)其偏好的貢獻(xiàn)綜合起來(lái)考慮，得到這條評(píng)價(jià)信息對(duì)用戶偏好的綜合貢獻(xiàn)（問(wèn)題2）？如何將用戶的多條評(píng)價(jià)對(duì)偏好的綜合貢獻(xiàn)綜合起來(lái)考慮，得到該用戶對(duì)各商品的偏好（問(wèn)題3）？

（1）針對(duì)問(wèn)題1，給出聯(lián)合算子⊕d，并在第3章給出基于D-S證據(jù)理論的計(jì)算方法。針對(duì)一條用戶評(píng)價(jià)r，以fT(T)和fF(F)作為r中評(píng)論數(shù)據(jù)對(duì)用戶偏好貢獻(xiàn)的“證據(jù)”，使用如下公式計(jì)算評(píng)論數(shù)據(jù)對(duì)用戶偏好的聯(lián)合貢獻(xiàn)（記為f(W)）：

（2）針對(duì)問(wèn)題2，用戶對(duì)商品的評(píng)分實(shí)際上已經(jīng)給出了一個(gè)量化的偏好值，因此首先將評(píng)價(jià)r中的評(píng)分信息進(jìn)行歸一化處理。若所有用戶評(píng)價(jià)中評(píng)分的最大值為S，則評(píng)分sr對(duì)用戶偏好的貢獻(xiàn)為sr/S(0≤sr/S≤1)。進(jìn)而，可利用聯(lián)合算子⊕d計(jì)算f(W)⊕dsr/S，從而得到評(píng)價(jià)r中所蘊(yùn)含的用戶偏好，記為pre(r) (0≤pre(r)≤1)。

（3）針對(duì)問(wèn)題3，仍使用聯(lián)合算子⊕d，將用戶各條評(píng)價(jià)中所蘊(yùn)含的偏好綜合考慮，得到定義1中描述的偏好向量D。進(jìn)一步，以用戶評(píng)價(jià)中所涉及商品的偏好為“證據(jù)”，使用聯(lián)合算子⊕d將一類商品的各個(gè)偏好進(jìn)行綜合考慮，得到用戶對(duì)商品類別的偏好。

因此，如何從給定的用戶評(píng)價(jià)數(shù)據(jù)計(jì)算聯(lián)合算子⊕d，是解決以上3個(gè)問(wèn)題，得到3個(gè)層面的用戶偏好的基本任務(wù)，也是從評(píng)價(jià)數(shù)據(jù)發(fā)現(xiàn)用戶偏好的關(guān)鍵和本文研究的重點(diǎn)。

3 數(shù)據(jù)密集型的用戶偏好發(fā)現(xiàn)

如前所述，基于D-S證據(jù)理論，通過(guò)證據(jù)融合規(guī)則計(jì)算用戶偏好。下面以第2章中陳述的問(wèn)題1為代表，分別討論聯(lián)合算子的定義及相應(yīng)的計(jì)算方法。

3.1 基于D-S證據(jù)理論的聯(lián)合算子

下面基于D-S證據(jù)理論[11]給出辨識(shí)框架和基本概率分配函數(shù)（簡(jiǎn)稱mass函數(shù)）的定義。

定義3（辨識(shí)框架）將一條用戶評(píng)價(jià)r的評(píng)論數(shù)據(jù)中正面詞匯(T)和負(fù)面詞匯(F)構(gòu)成的集合定義為辨識(shí)框架，記為Θ={T,F}，Θ的冪集2θ={{?},{T},{F}, {T,F}}對(duì)應(yīng)于Θ的所有可能評(píng)論對(duì)用戶偏好的影響。

定義4（mass函數(shù)）函數(shù)m:2Θ→[0,1]稱為Θ上的mass函數(shù)，函數(shù)m1和m2分別為T(mén)和F對(duì)用戶偏好影響的mass函數(shù)，且滿足：

根據(jù)D-S證據(jù)理論，m稱為m1和m2的正交和，也稱為證據(jù)融合，記為m=m1(T)⊕m2(F)，其中⊕為融合算子。進(jìn)而，基于m討論式（2）中的聯(lián)合算子⊕d。事實(shí)上，用戶對(duì)商品給出正面評(píng)論的同時(shí)也會(huì)給出負(fù)面評(píng)論，給出正面評(píng)論，未必就不會(huì)給出負(fù)面評(píng)論。因此，針對(duì)正面評(píng)論T，用m1(Θ)表示該評(píng)論中除了T之外的可能評(píng)論的mass函數(shù)，且

同理，僅針對(duì)負(fù)面評(píng)論F，用m2(Θ)表示該評(píng)論中除了F之外的可能評(píng)論的mass函數(shù)，且

D-S證據(jù)理論中，Dempster證據(jù)組合規(guī)則[12-14]組合兩個(gè)mass函數(shù)，以產(chǎn)生一個(gè)新的mass函數(shù)，表示初始可能沖突的證據(jù)間的一致意見(jiàn)，通過(guò)僅僅對(duì)交集的mass函數(shù)值求和匯集一致意見(jiàn)，集合的交集表達(dá)了公共證據(jù)元素。根據(jù)Dempster證據(jù)組合規(guī)則的基本思想，基于式（3）～（5），得到：

進(jìn)而，基于證據(jù)融合后的mass函數(shù)，⊕d可定義為包含T或F的mass函數(shù)值之和，即：

下面通過(guò)一個(gè)簡(jiǎn)單的例子說(shuō)明基于D-S證據(jù)理論的聯(lián)合算子的基本思想。對(duì)于表1中用戶2對(duì)“面包”的評(píng)論，T={味香}，F(xiàn)={油膩,價(jià)高}，根據(jù)式（1）、（3）、（4）和（5），可以得到m1(T)=0.6，m1(Θ)=1-m1(T)= 0.4，m2(F)=0.1，m2(Θ)=1-m2(F)=0.9。

基于式（6），以T和F作為該評(píng)論對(duì)用戶偏好影響的證據(jù)，組合結(jié)果如表2所示。

Table 2 Evidence combination ofTandF表2 T和F證據(jù)組合

基于式（7），可以得到：

基于式（8），式（2）的具體計(jì)算如下：

也就是說(shuō)，用戶2的偏好向量中，商品“面包”維度的偏好值為0.61。

3.2 基于MapReduce的用戶偏好發(fā)現(xiàn)算法

針對(duì)海量的用戶評(píng)價(jià)信息，基于3.1節(jié)中給出的方法計(jì)算用戶評(píng)論數(shù)據(jù)對(duì)其偏好的聯(lián)合影響，本文設(shè)計(jì)了兩趟執(zhí)行的MapReduce算法。第一趟算法（算法1）針對(duì)每一條評(píng)論數(shù)據(jù)，通過(guò)Map函數(shù)得到這條評(píng)論中正面詞匯及負(fù)面詞匯出現(xiàn)的次數(shù)，通過(guò)Reduce函數(shù)對(duì)這條評(píng)論中正面詞匯及負(fù)面詞匯的出現(xiàn)次數(shù)進(jìn)行求和；第二趟算法（算法2）針對(duì)用戶對(duì)各商品的評(píng)論數(shù)據(jù)，通過(guò)Map函數(shù)得到用戶對(duì)一個(gè)商品（針對(duì)一條評(píng)論）的偏好，通過(guò)Reduce函數(shù)得到該用戶對(duì)所有商品的偏好向量。

算法1 Count_|T|_|F|

對(duì)于每條評(píng)論，將算法1的執(zhí)行結(jié)果以〈key，value〉的形式存儲(chǔ)到中間結(jié)果文件W中，即用|T|和|F|來(lái)表示用戶的一條評(píng)論，以之作為用戶偏好計(jì)算的基礎(chǔ)。不難看出，算法1的執(zhí)行代價(jià)主要取決于遍歷評(píng)論信息，并與已知標(biāo)示性詞語(yǔ)集合匹配，若標(biāo)示性詞語(yǔ)集合中有n個(gè)詞語(yǔ)，則算法1在最壞情況下時(shí)間復(fù)雜度為O(n2)。根據(jù)算法1，可以得到每一條用戶評(píng)論中關(guān)鍵詞的數(shù)量，方便對(duì)評(píng)論進(jìn)行量化處理。下面給出從每一條評(píng)論發(fā)現(xiàn)其中所蘊(yùn)含用戶偏好的算法，體現(xiàn)3.1節(jié)中的各個(gè)計(jì)算步驟。

算法2 Compute_Preference

不難看出，算法2的執(zhí)行代價(jià)主要取決于遍歷每一條用戶評(píng)價(jià)信息的統(tǒng)計(jì)結(jié)果，利用算法1的統(tǒng)計(jì)結(jié)果，由算法2將用戶的評(píng)分和評(píng)論進(jìn)行量化處理，從而得到最終的用戶偏好。若有n條評(píng)價(jià)信息，算法2的時(shí)間復(fù)雜度為O(n)。本文采用MapReduce算法通過(guò)并行計(jì)算的方式保證了算法較高的執(zhí)行效率。

4 實(shí)驗(yàn)結(jié)果

4.1 實(shí)驗(yàn)設(shè)置

本文使用MovieLens[19]上用戶的真實(shí)評(píng)價(jià)數(shù)據(jù)作為測(cè)試數(shù)據(jù)集，包括229 060位用戶對(duì)27 303部電影的21 063 128條記錄。每個(gè)用戶至少為20部電影評(píng)分，平均每1 GB數(shù)據(jù)包含37 886 000條用戶記錄。數(shù)據(jù)集格式為UserId：：MovieId：：Rating：：Tags，依次為用戶Id、電影Id、用戶評(píng)分和用戶對(duì)這部電影的評(píng)論標(biāo)簽。實(shí)驗(yàn)環(huán)境如下：運(yùn)行Linux CentOs7系統(tǒng)和Hadoop-2.5.1平臺(tái)的6臺(tái)機(jī)器，Inter Core i3 3240處理器、3.4 GHz主頻和2 GB內(nèi)存，每臺(tái)機(jī)器作為一個(gè)DataNode。為了測(cè)試本文方法的可行性，測(cè)試了從評(píng)論數(shù)據(jù)發(fā)現(xiàn)用戶偏好方法的有效性、執(zhí)行時(shí)間、加速比和并行效率。

4.2 有效性測(cè)試

為了測(cè)試本文從用戶評(píng)價(jià)數(shù)據(jù)發(fā)現(xiàn)其偏好的方法的有效性，首先假設(shè)用戶評(píng)價(jià)中的評(píng)分?jǐn)?shù)據(jù)反映了其真實(shí)的偏好，并以之作為衡量從評(píng)論數(shù)據(jù)發(fā)現(xiàn)用戶偏好的正確性標(biāo)準(zhǔn)。直觀地，若評(píng)分的最大值為5，則評(píng)分為4和5即為高分，相應(yīng)地，評(píng)論中的正面詞匯數(shù)量應(yīng)不少于負(fù)面詞匯數(shù)量。對(duì)此，針對(duì)評(píng)分為4或5的評(píng)價(jià)，通過(guò)多次實(shí)驗(yàn)確定偏好閾值為0.63，可保證評(píng)分與評(píng)論具有上述的對(duì)應(yīng)關(guān)系。對(duì)于各條評(píng)分為4或5的用戶評(píng)價(jià)，若基于本文方法從評(píng)論數(shù)據(jù)計(jì)算得到的用戶偏好值不低于該閾值，則說(shuō)明基于本文方法得到的用戶偏好是正確的。從測(cè)試數(shù)據(jù)中隨機(jī)選擇10條評(píng)價(jià)，考慮從評(píng)論數(shù)據(jù)計(jì)算得到的用戶偏好與評(píng)分之間是否一致，如表3所示。不難看出，值為4或5的高評(píng)分所對(duì)應(yīng)的用戶偏好大于0.63的占70%，即正確率為70%，這與人們的直觀理解基本相符，從一定程度上說(shuō)明了本文方法的正確性。

Table 3 Comparisons between scores and user preference derived from reviews表3 評(píng)分與從評(píng)論得到的用戶偏好對(duì)比

進(jìn)一步，對(duì)評(píng)分進(jìn)行歸一化處理，對(duì)評(píng)論按照第3章給出的方法，分別得到從評(píng)分和評(píng)論數(shù)據(jù)中發(fā)現(xiàn)的用戶偏好（分別記為ds和dr），基于2.2節(jié)的基本思路，將評(píng)分和評(píng)論看作最終用戶偏好的證據(jù)，無(wú)需評(píng)分與評(píng)論的權(quán)重，得到綜合考慮評(píng)分和評(píng)論的最終結(jié)果（記為d）。隨機(jī)選擇10條評(píng)價(jià)數(shù)據(jù)，將d與基于ds和dr算術(shù)平均（記為da）的結(jié)果進(jìn)行比較，如表4所示。通過(guò)前3條評(píng)價(jià)數(shù)據(jù)的結(jié)果對(duì)比可以看出，當(dāng)ds不變時(shí)，d隨著dr的增加而增加，當(dāng)dr不變時(shí)，d隨著ds的增加而增加，這一趨勢(shì)符合實(shí)際情況。對(duì)于第10條缺失評(píng)論的評(píng)價(jià)數(shù)據(jù)，基于本文方法得到的用戶偏好即為ds，基于算術(shù)平均方法得到的結(jié)果與實(shí)際不符。對(duì)這10條評(píng)價(jià)對(duì)應(yīng)的d與da排序，除了第3條和第8條外，d與da趨勢(shì)一致，說(shuō)明基于本文方法得到的用戶偏好可有效用于商品投放和用戶定向等基于用戶偏好的實(shí)際應(yīng)用中。因此，基于本文方法，可在各影響因素權(quán)重未知的情況下考慮它們之間的內(nèi)在聯(lián)系而得出符合實(shí)際情況的偏好排序，能以更符合人們直觀理解的方式，更合理地反映用戶對(duì)于商品的喜好程度。

Table 4 Comparisons between user preference by this paper method and that by arithmetic mean表4 基于本文方法與算術(shù)平均方法結(jié)果對(duì)比

接下來(lái)，再?gòu)牧硪粋€(gè)角度來(lái)說(shuō)明本文方法的有效性。隨機(jī)選取3名用戶（記為A、B和C），同時(shí)隨機(jī)選取20部他們都評(píng)價(jià)過(guò)的電影作為測(cè)試數(shù)據(jù)，其中10部電影的評(píng)價(jià)信息作為訓(xùn)練數(shù)據(jù)，剩下10部電影的評(píng)價(jià)信息作為對(duì)比數(shù)據(jù)。表5給出了3名用戶對(duì)10部電影的評(píng)分?jǐn)?shù)據(jù)。

對(duì)比基于協(xié)同過(guò)濾算法[8]和基于本文方法得到的用戶偏好，以測(cè)試本文方法的有效性。實(shí)驗(yàn)選定用戶B為目標(biāo)用戶。首先假設(shè)用戶A和C只對(duì)ID為1～10的電影進(jìn)行了評(píng)價(jià)，而用戶B對(duì)全部電影進(jìn)行了評(píng)價(jià)；然后基于余弦相似度找出與用戶B相似的用戶集；將ID為11～20的電影按照B的喜好推薦給A或C。對(duì)比以上兩個(gè)結(jié)果，若用戶評(píng)分不小于4，則表示用戶喜歡此電影；基于余弦相似度可得到用戶A和用戶B相似度最高。表6給出了他們對(duì)后10部電影的評(píng)價(jià)信息。用戶A的評(píng)分?jǐn)?shù)據(jù)通過(guò)協(xié)同過(guò)濾方法預(yù)測(cè)得到，通過(guò)與基于本文方法從評(píng)論中獲取的用戶偏好進(jìn)行比較，可以看出，除了ID為13、15和19的電影，通過(guò)基于協(xié)同過(guò)濾方法預(yù)測(cè)得到的電影評(píng)分與使用本文方法從評(píng)論中得到用戶偏好結(jié)果基本一致，進(jìn)而可得到用戶對(duì)電影的傾向性選擇，這在一定程度上說(shuō)明了本文方法的正確性。

Table 5 Ratings of users on movies表5 用戶對(duì)電影的評(píng)分信息

Table 6 Comparions between userAand user B evaluation information表6 用戶A和用戶B評(píng)價(jià)信息對(duì)比

4.3 效率測(cè)試

為了測(cè)試本文方法的執(zhí)行效率，選取了規(guī)模為2.5 GB、5 GB、10 GB、15 GB和20 GB的5組MovieLens數(shù)據(jù)，分別測(cè)試了不同DataNode數(shù)量情況下的執(zhí)行時(shí)間、加速比和并行效率。其中執(zhí)行時(shí)間包括對(duì)測(cè)試數(shù)據(jù)集中所有評(píng)價(jià)執(zhí)行算法1的時(shí)間以及執(zhí)行算法2的時(shí)間，每個(gè)測(cè)試結(jié)果取3次執(zhí)行時(shí)間的平均值。

圖1給出了隨著評(píng)價(jià)數(shù)據(jù)規(guī)模增加，不同Data-Node數(shù)量時(shí)的執(zhí)行時(shí)間?？梢钥闯?，隨著評(píng)價(jià)數(shù)據(jù)規(guī)模增加，DataNode數(shù)量越多，執(zhí)行時(shí)間增加越慢；當(dāng)評(píng)價(jià)數(shù)據(jù)規(guī)模達(dá)到20 GB時(shí)，本文方法在當(dāng)前實(shí)驗(yàn)環(huán)境下仍能高效地得到用戶偏好。圖2給出了隨著DataNode數(shù)量增加，不同評(píng)價(jià)數(shù)據(jù)規(guī)模時(shí)的執(zhí)行時(shí)間?？梢钥闯觯S著DataNode增加，執(zhí)行時(shí)間減少，且數(shù)據(jù)量越大這一趨勢(shì)越顯著，說(shuō)明本文方法對(duì)于海量評(píng)價(jià)數(shù)據(jù)分析具有較好的可擴(kuò)展性。

Fig.1 Execution time with the increase of rating data size圖1 隨著評(píng)價(jià)數(shù)據(jù)規(guī)模增加的執(zhí)行時(shí)間

Fig.2 Execution time with the increase of DataNodes圖2 隨著DataNode增加的執(zhí)行時(shí)間

并行算法的加速比是單節(jié)點(diǎn)情形下執(zhí)行時(shí)間與多節(jié)點(diǎn)情形下執(zhí)行時(shí)間的比值。圖3給出了隨著評(píng)價(jià)數(shù)據(jù)規(guī)模增加，不同DataNode數(shù)量時(shí)的加速比。圖4給出了隨著DataNode數(shù)量增加，不同評(píng)價(jià)數(shù)據(jù)規(guī)模時(shí)的加速比。可以看出，隨著評(píng)價(jià)數(shù)據(jù)量增加，Data-Node數(shù)量越多，加速比增加越快。

Fig.3 Speedup with the increase of rating data size圖3 隨著評(píng)價(jià)數(shù)據(jù)規(guī)模增加的加速比

Fig.4 Speedup with the increase of DataNodes圖4 隨著DataNode增加的加速比

并行算法的并行效率是加速比與節(jié)點(diǎn)數(shù)的比值。圖5給出了隨著評(píng)價(jià)數(shù)據(jù)規(guī)模增加，不同DataNode數(shù)量時(shí)的并行效率?？梢钥闯?，隨著評(píng)價(jià)數(shù)據(jù)規(guī)模增加，不同DataNode數(shù)量時(shí)并行效率都逐漸增加，但DataNode越多，并行效率越低。圖6給出了隨著DataNode數(shù)量增加，不同評(píng)價(jià)數(shù)據(jù)規(guī)模時(shí)的并行效率?？梢钥闯?，隨著DataNode數(shù)量增加，不同評(píng)價(jià)數(shù)據(jù)規(guī)模時(shí)的并行效率都逐漸下降，同一Data-Node數(shù)量時(shí)數(shù)據(jù)量越大，并行效率越高，說(shuō)明了本文方法對(duì)于海量評(píng)價(jià)數(shù)據(jù)規(guī)模具有較好的可擴(kuò)展性。

Fig.5 Parallel efficiency with the increase of rating data size圖5 隨著評(píng)價(jià)數(shù)據(jù)規(guī)模增加的并行效率

Fig.6 Parallel efficiency with the increase of DataNodes圖6 隨著DataNode增加的并行效率

5 總結(jié)與展望

本文基于D-S證據(jù)理論和MapReduce編程模型，提出了從海量的用戶評(píng)價(jià)數(shù)據(jù)中發(fā)現(xiàn)用戶偏好的方法。本文提出的方法和思路：利用影響用戶偏好的各因素的不確定性和它們之間的相互關(guān)系，可得到基于用戶評(píng)論中正面詞匯和負(fù)面詞匯、基于用戶評(píng)論和評(píng)分、面向商品類別的3個(gè)層次的用戶偏好。本文方法可準(zhǔn)確、快速地發(fā)現(xiàn)用戶偏好，可支持實(shí)際中商品推薦和用戶定向等應(yīng)用。然而，作為一種初步的嘗試，本文從評(píng)論數(shù)據(jù)中抽取正面詞匯和負(fù)面詞匯時(shí)，未考慮評(píng)論中詞匯的語(yǔ)義，具有一定的主觀性；針對(duì)每個(gè)商品計(jì)算用戶的偏好，而實(shí)際中商品的數(shù)量較多，需要引入降維技術(shù)來(lái)提高計(jì)算的效率，也更符合實(shí)際情形，這些是將要開(kāi)展的工作。

References:

[1]Lin Yuming,Zhu Tao,Wang Xiaoling,et al.Assembling and optimizing multiple classifiers for user opinion analysis[J]. Chinese Journal of Computers,2013,36(8):1650-1658.

[2]Wang Yuanzhuo,Jin Xiaolong,Cheng Xueqi.Network big data:present and future[J].Chinese Journal of Computers, 2013,36(6):1125-1138.

[3]Hong Jongyi,Suh E,Kim J,et al.Context-aware system for proactive personalized service based on context history[J]. Expert Systems withApplications,2009,36(4):7448-7457.

[4]Skillen K L,Chen Liming,Nugent C,et al.Ontological user profile modeling for context-aware application personalization[C]//LNCS 7656:Proceedings of the 6th International Conference on Ubiquitous Computing and Ambient Intelligence,Vitoria-Gasteiz,Spain,Dec 3-5,2012.Berlin,Heidelberg:Springer,2012:261-268.

[5]Yao Xiuli,Shu Huaying.Study on value-added service in mobile telecom based on association rules[C]//Proceedings of the 2009 10th ACIS International Conference on Software Engineering,Artificial Intelligences,Networking and Parallel/Distributed Computing,Daegu,Korea,May 27-29, 2009.Washington:IEEE Computer Society,2009:116-119.

[6]Zhang Yongzheng,Pennacchiotti M.Predicting purchase behaviors from social media[C]//Proceedings of the 22nd International Conference on World Wide Web,Rio,Brazil,May 13-17,2013.New York:ACM,2013:1521-1532.

[7]Tang Duyu,Qin Bing,Liu Ting,et al.User modeling with neural network for review rating prediction[C]//Proceedings of the 24th International Conference on Artificial Intelligence,Buenos Aires,Argentina,Jul 25-31,2015.Palo Alto, USA:AAAI Press,2015:1340-1346.

[8]Harvey M,Carman M J,Ruthven I,et al.Bayesian latent variable models for collaborative item rating prediction[C]// Proceedings of the 20th ACM Conference on Information and Knowledge Management,Glasgow,UK,Oct 24-28, 2011.New York:ACM,2011:699-708.

[9]Ma You,Wang Shangguang,Sun Qibo,et al.Web services QoS measure based on subjective and objective weight[C]// Proceedings of the 2013 IEEE International Conference on Services Computing,Santa Clara,USA,Jun 28-Jul 3,2013. Piscataway,USA:IEEE,2013:543-550.

[10]Yue Kun,Liu Weiyi,Wang Xiaoling,et al.An approach for measuring quality of Web services based on the superposition of uncertain factors[J].Journal of Computer Research and Development,2009,46(5):841-849.

[11]Shmueli-Scheuer M,Roitman H,Carmel D,et al.Extracting user profiles from large scale data[C]//Proceedings of the 2010 Workshop on Massive DataAnalytics on the Cloud,Raleigh,USA,Apr 26,2010.New York:ACM,2010:4.

[12]Dempster A.Upper and lower probabilities induced by a multivalued mapping[J].Annals of Mathematical Statistics, 1967,38(2):325-339.

[13]Shafer G.Mathematical theory of evidence[M].Princeton, USA:Princeton University Press,1976.

[14]Pearl J.Probabilistic reasoning in intelligent systems:networks of plausible inference[M].San Mateo,USA:Morgan Kaufmann Publishers,Inc,1988.

[15]Yang Jianping,Huang Hongzhong,Miao Qiang,et al.A novel information fusion method based on Dempster-Shafer evidence theory for conflict resolution[J].Intelligent Data Analysis,2011,15(3):399-411.

[16]Qiu Peiyuan,Lu Feng,Zhang Hengcai.Extracting traffic information from Web texts with a D-S evidence theory based approach[C]//Proceedings of the 21st International Conference on Geoinformatics,Kaifeng,China,Jun 20-22,2013. Piscataway,USA:IEEE,2013:1-5.

[17]Dean J,Ghemawat S.MapReduce:a flexible data processing tool[J].Communications of theACM,2010,53(1):72-77.

[18]Yue Kun,Fang Qiyu,Wang Xiaoling,et al.A parallel and incremental approach for data-intensive learning of Bayesian networks[J].IEEE Transactions on Cybernetics,2005,45 (12):2890-2904.

[19]MovieLens[EB/OL].(2015)[2015-09-28].http://grouplens. org/datasets/movielens/.

[20]Yue Kun,Liu Weiyi,Zhou Liping.Automatic keyword extraction from documents based on multi-perspective semantic measures[J].International Journal of Computer Systems Science and Engineering,2011,26(2):133-145.

[21]Gao Hongye.Mocroeconomics[M].5th ed.Beijing:China Renmin University Press,2010.

附中文參考文獻(xiàn)：

[1]林煜明,朱濤,王曉玲,等.面向用戶觀點(diǎn)分析的多分類器集成和優(yōu)化技術(shù)[J].計(jì)算機(jī)學(xué)報(bào),2013,36(8):1650-1658.

[2]王元卓,靳小龍,程學(xué)旗.網(wǎng)絡(luò)大數(shù)據(jù):現(xiàn)狀與展望[J].計(jì)算機(jī)學(xué)報(bào),2013,36(6):1125-1138.

[10]岳昆,劉惟一,王曉玲,等.一種基于不確定性因素疊加的Web服務(wù)質(zhì)量度量方法[J].計(jì)算機(jī)研究與發(fā)展,2009,46 (5):841-849.

[21]高鴻業(yè).西方經(jīng)濟(jì)學(xué)（微觀部分）[M].5版.北京:中國(guó)人民大學(xué)出版社，2010.

GUO Xinyu was born in 1990.He is an M.S.candidate at School of Information Science and Engineering,Yunnan University.His research interests include massive data analysis and services.

郭心宇（1990—），男，河北石家莊人，云南大學(xué)信息學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)楹Ａ繑?shù)據(jù)分析與服務(wù)。

YUE Kun was born in 1979.He received the M.S degree in computer science from Fudan University in 2004,and received the Ph.D.degree in computer science from Yunnan University in 2009.Now he is a professor and Ph.D.supervisor at Yunnan University,and the member of CCF.His research interests include massive data analysis and services.

岳昆（1979—），男，云南曲靖人，2004年于復(fù)旦大學(xué)獲得計(jì)算機(jī)碩士學(xué)位，2009年于云南大學(xué)獲得計(jì)算機(jī)博士學(xué)位，現(xiàn)為云南大學(xué)教授、博士生導(dǎo)師，CCF會(huì)員，主要研究領(lǐng)域?yàn)楹Ａ繑?shù)據(jù)分析與服務(wù)。

LI Jin was born in 1975.He received the Ph.D.degree in computer science from Yunnan University in 2012.Now he is an associate professor at Yunnan University,and the member of CCF.His research interests include massive data analysis and artificial intelligence.

李勁（1975—），男，云南大理人，2012年于云南大學(xué)獲得計(jì)算機(jī)博士學(xué)位，現(xiàn)為云南大學(xué)副教授，CCF會(huì)員，主要研究領(lǐng)域?yàn)楹Ａ繑?shù)據(jù)分析與人工智能。

WU Hao was born in 1979.He received the Ph.D.degree in computer science from Huazhong University of Science and Technology in 2007.Now he is an associate professor at Yunnan University.His research interests include information retrieval,recommendation system and service computing.

武浩（1979—），男，河南平頂山人，2007年于華中科技大學(xué)獲得計(jì)算機(jī)博士學(xué)位，現(xiàn)為云南大學(xué)副教授，主要研究領(lǐng)域?yàn)樾畔z索，推薦系統(tǒng)，服務(wù)計(jì)算。

ZHANG Binbin was born in 1982.She received the Ph.D.degree in computer science from Peking University in 2011.Now she is a lecturer at Yunnan University.Her research interests include virtualization and cloud computing.張彬彬（1982—），女，云南大理人，2011年于北京大學(xué)獲得計(jì)算機(jī)博士學(xué)位，現(xiàn)為云南大學(xué)講師，主要研究領(lǐng)域?yàn)樘摂M化，云計(jì)算。

Evidence-TheoryApproach for Discovering User Preferences in Rating Data*

GUO Xinyu1,YUE Kun1+,LI Jin2,WU Hao1,ZHANG Binbin1
1.School of Information Science and Engineering,Yunnan University,Kunming 650504,China
2.School of Software,Yunnan University,Kunming 650504,China
+Corresponding author:E-mail:kyue@ynu.edu.cn

User rating on products or information services includes reviews and scores,and reflects user behavior information,such as interest,opinions and preferences.In order to represent the degrees of user preferences on products inherently and quantitatively,starting from the massive rating data,this paper defines user preference based on the idea of marginal utility.Then,this paper describes the uncertainties of relevant influence factors on user preferences and the mutual relationships among these factors based on the D-S evidence theory.Taking the vocabulary in a review, the vocabulary including positive/negative words and the score as the evidence of user preference respectively,this paper gives the operator for combining the relevant factors jointly,as well as the computation method and mechanism for discovering user preferences based on MapReduce.The experimental results on correctness,execution time,speedup and parallel efficiency verify the effectiveness of the method proposed in this paper.

massive rating data;user preference;D-S evidence theory;evidence fusion;MapReduce

10.3778/j.issn.1673-9418.1511023

A

TP311

*The National Natural Science Foundation of China under Grant Nos.61472345,61402398,61562090,61562091(國(guó)家自然科學(xué)基金);the Applied Basic Research Project of Yunnan Province under Grant Nos.2014FA023,2016FB110(云南省應(yīng)用基礎(chǔ)研究計(jì)劃); the Program for the Second Batch of Yunling Scholar of Yunnan Province under Grant No.C6153001(第二批“云嶺學(xué)者”培養(yǎng)項(xiàng)目);the Program for Excellent Young Talents of Yunnan University under Grant No.XT412003(云南大學(xué)青年英才培養(yǎng)計(jì)劃).

Received 2015-11,Accepted 2016-04.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-04-01,http://www.cnki.net/kcms/detail/11.5602.TP.20160401.1614.002.html

GUO Xinyu,YUE Kun,LI Jin,et al.Evidence-theory approach for discovering user preferences in rating data. Journal of Frontiers of Computer Science and Technology,2017,11(2)：231-241.

摘 要：用戶對(duì)商品和信息服務(wù)的評(píng)價(jià)包含評(píng)論和評(píng)分，富含了用戶的興趣、觀點(diǎn)和偏好等行為信息。以真實(shí)和量化地反映用戶對(duì)商品的喜好程度為目標(biāo)，從海量的用戶評(píng)價(jià)數(shù)據(jù)出發(fā)，基于邊際效用定義用戶偏好，基于D-S證據(jù)理論描述影響用戶偏好的各影響因素的不確定性以及各因素之間的相互關(guān)系；以評(píng)論中的各詞匯、包含正面/負(fù)面詞匯的評(píng)論和評(píng)分作為用戶對(duì)商品偏好的“證據(jù)”，給出了綜合考慮各影響因素的聯(lián)合算子，以及基于MapReduce的計(jì)算方法和用戶偏好發(fā)現(xiàn)機(jī)制。針對(duì)正確性、執(zhí)行時(shí)間、加速比和并行效率等指標(biāo)進(jìn)行實(shí)驗(yàn)，結(jié)果驗(yàn)證了所提出方法的有效性。