一種從偏好數(shù)據(jù)庫中學習CP-nets結構的并行算法

劉 素， 劉驚雷

(煙臺大學 計算機與控制工程學院 山東 煙臺 264005)

0 引言

作為描述多屬性之間定性條件偏好的圖模型，CP-nets[1]的理論研究已經(jīng)成為人工智能領域的一大熱點問題[2]，其中CP-nets結構學習問題研究起著至關重要的作用。并行算法是在并行機上利用很多個處理器聯(lián)合求解問題和處理數(shù)據(jù)。作為一種處理大規(guī)模數(shù)據(jù)的分布式計算系統(tǒng)，Hadoop具有優(yōu)秀的可移植性，其核心是由NameNode分布式文件系統(tǒng)和MapReduce分布式計算框架組成，解決了大規(guī)模數(shù)據(jù)的存儲和算法的并行設計問題。目前，國內對CP-nets結構學習的主要思想是在屬性驗證基礎上窮舉每個屬性的可行父親集[3]，得到的都是CP-nets的近似結構。不同于傳統(tǒng)的CP-nets結構學習方法，本文設計了一種基于MapReduce框架的相關系數(shù)并行算法，首次將傳統(tǒng)的“評分+搜索”方法[4]應用到Hadoop平臺上，利用信息論中的相關系數(shù)建立在偏好數(shù)據(jù)庫上的目標函數(shù)，提高屬性間的依賴性和降低冗余性；在電影推薦數(shù)據(jù)集上分析用戶對電影的評分，找出用戶和電影之間的相互關系，快速高效地從大規(guī)模數(shù)據(jù)中進行CP-nets結構學習。

1 相關工作

近年來對CP-nets結構學習的研究方法眾多，然而由于結構的多樣性，進行學習是非常困難的。文獻[5]基于精確P值計算學習CP-nets的拓撲結構，首先選擇一個頂點Xi，Xi的可行父親集是全集V減去頂點Xi之后剩余集合中的任意子集組合，根據(jù)Dijkstra原理比較每個頂點與其對應的可行父親集之間的P值，循環(huán)學習得到CP-nets的無環(huán)結構，但存在時間復雜度不樂觀等諸多問題。文獻[6]為了學習CP-nets結構，利用假設檢驗方法從噪聲數(shù)據(jù)中進行學習，但僅僅給出了全序關系下的CP-nets結構學習方法。對CP-nets結構學習的已有研究都是在基于關系數(shù)據(jù)庫基礎上進行的，并不具有代表性。在此背景下，本文提出了一種從偏好數(shù)據(jù)庫中學習CP-nets結構的并行算法。

在機器學習領域，“評分+搜索”是目前使用較為廣泛的圖模型結構學習方法。這類方法將CP-nets結構學習問題看作是結構最優(yōu)化問題，包括了評分函數(shù)和搜索空間兩部分。評分函數(shù)可以靈活地將專家經(jīng)驗知識以結構先驗概率分布的形式融入結構學習過程中，主要分為貝葉斯評分函數(shù)和基于信息論的評分函數(shù)。搜索空間包括序空間搜索和基于DAG的空間搜索，其中序空間搜索依靠動態(tài)規(guī)劃法來實現(xiàn)。本文考慮到屬性之間的相關性、冗余性和算法的執(zhí)行效率，提出了一種利用相關系數(shù)評分函數(shù)[7]和序空間搜索從偏好數(shù)據(jù)庫中學習CP-nets結構的算法，并行地對偏好數(shù)據(jù)庫進行數(shù)據(jù)挖掘，利用評分函數(shù)表達屬性間的依賴關系，序空間搜索在改變屬性間邊的情況下求得屬性間依賴冗余關系，可以從不同類型的電影推薦數(shù)據(jù)集中挖掘出偏好依賴關系，該算法基于MapReduce框架進行設計，在處理大規(guī)模數(shù)據(jù)時展現(xiàn)出了良好的性能。

2 CP-nets結構學習相關概念

2.1 CP-nets

如果兩個屬性之間存在依賴關系，即屬性Xi的偏好取決于Xj，則Xj被稱為Xi的父親，用Pare(Xi)表示；Dom(Xi)表示屬性Xi的定義域；CPT(Xi)表示可行父親集Pare(Xi)在不同情況下屬性Xi對Dom(Xi)的偏好排序。

定義1[1](條件偏好網(wǎng)) CP-nets是一個用N=〈V,CE,CPT〉表示的有向圖，其中：V={X1,X2,…,Xn}表示CP-nets所有屬性的頂點集合；CE={(Xi,Xj)|Xj∈Pare(Xi),Xi∈V}為CP-nets結構中有向邊的集合，表示各個頂點屬性之間的依賴關系；每個屬性Xi對應于一個用來表示偏好關系的條件偏好表CPT(Xi)。

2.2 偏好數(shù)據(jù)庫

定義2(偏好數(shù)據(jù)庫) 設P(a1,a2,…,an)是一個關系模式，Tuple(P)表示屬于P的所有元組，Tuple(P)上的偏序集合B=Tuple(P)×Tuple(P)稱為偏好數(shù)據(jù)庫。例如，(o1,o2)∈B被稱為一個二元組，表示比較偏好數(shù)據(jù)庫B里的o1與o2，如果更偏好于o1，則用o1?o2表示[8]。

定義3(劃分屬性) 設偏好數(shù)據(jù)庫B，屬性為X，則在偏好數(shù)據(jù)庫B中關于X的劃分屬性為

Divide(X)={(xi,xj)|(o[xi]=x1,o[xj]=x2∪o[xi]=x2,o[xj]=x1),

(oi,oj)∈B,(xi,xj)∈Dom(X)}，

(1)

式中：o[xi]表示xi在偏好數(shù)據(jù)庫B上的映射；Dom(X)表示屬性X的定義域。

2.3 “評分+搜索”方法

“評分+搜索”方法學習CP-nets結構的主要思想，是利用某種評分思路對CP-nets的每個組合(頂點及其他的可行父親集)構造一個評分，然后在所有可能的結構中，搜索尋找一組全局最優(yōu)的結構。“評分+搜索”方法眾多，本文采用特征選擇中的相關系數(shù)評分函數(shù)學習CP-nets結構。統(tǒng)計學中使用協(xié)方差來度量兩個屬性之間的總體誤差，隨機變量X和Y之間的協(xié)方差表示為

(2)

方差用于衡量隨機變量與其數(shù)學期望之間的偏離程度，隨機離散變量X的方差表示為

(3)

式中：α、β表示當前偏好數(shù)據(jù)庫中，通過劃分屬性計算具有相同屬性偏好的個數(shù)。

2.3.1評分函數(shù)

定義4(相關性評分函數(shù)) 使用線性相關系數(shù)來衡量屬性之間的線性相關度，表示為

(4)

式中：|V|表示初始特征子集中成對比較的個數(shù)；cov(Xi,Y)表示屬性Xi和屬性Y之間的協(xié)方差；var(Y)表示屬性Y的方差。好的評分函數(shù)具有可分解性、易解性等優(yōu)秀特征，其中可分解性可以幫助算法進行搜索，允許其獨立于其他因素的影響。

2.3.2搜索空間 屬性之間的父親關系，從全集到空集可以構成n!條不同的序搜索路徑，同樣的一條路徑對應一個CP-nets可行結構[9]。假設最優(yōu)路徑為{A,B,C,D,E}→{A,B,C,D}→{A,B,C}→{A,B}→{A}→?，代表最優(yōu)路徑為A，B，C，D，E，從而也得到了CP-nets的最優(yōu)路徑結構。

3 基于MapReduce的算法設計

作為MapReduce最流行的開源實現(xiàn)，Hadoop使用塊級調度和排序合并技術來實現(xiàn)并行處理的分組功能[10]。本文提出的基于MapReduce的“評分+搜索”的相關系數(shù)算法，可以把原來龐大且無序的電影推薦數(shù)據(jù)集進行數(shù)據(jù)規(guī)整，并從中提取來自不同類型電影的評論熱點，從而得到用戶對電影的不同偏好，進而為電影的生產(chǎn)者、銷售者與消費者提供建議。

算法的基本思想是根據(jù)原始數(shù)據(jù)集M生成對應的初始特征子集V，分別在節(jié)點上求取每個特征子集之間的依賴關系，對給定的所有候選父親結構并行地進行統(tǒng)計，對CP-nets結構中每個節(jié)點的候選結構進行評分，選取候選結構中相關系數(shù)評分最高的局部最優(yōu)結構，將具有最高評分的候選結構作為下一次搜索的基礎迭代進行，直至選取到最高的評分，繼而得到全局最優(yōu)結構。算法1的具體步驟如下。

算法1Learn_CP-netsstructure

輸入:M，V，R()，U；

輸出: CP-netsN，N=〈V,CE,CPT(X)X∈V〉；

Step 1CE=?；FirstS=R(X,U)；∥FirstS表示對初始特征子集V中U的初始評分，U為V中的各個頂點。

Step 2 ForeachXi∈Vdo

NowS=maxR(Xi,U)；

∥依據(jù)偏好數(shù)據(jù)庫中數(shù)據(jù)集的數(shù)據(jù)，通過式(1)可知，劃分屬性代表了屬性X在偏好數(shù)據(jù)庫中有限定義域的排列組合，計算劃分屬性，繼而并行計算相關性系數(shù)評分，得到各頂點之間的依賴關系(偽代碼步驟見算法2)。

Step 3 IfFirstS

thenNowS=FirstS；CE=CE∪(Xi,Pare(Xi))；

elseFirstS=NowS；CE=CE∪(Xi,Pare(Xi))；

End for

Step 4N=〈V,CE,CPT(X)X∈V〉；

ReturnN；

局部評分Map階段，利用數(shù)據(jù)處理階段生成的候選結構D及其對應的CPT，動態(tài)分配到多個Map任務當中，每個Map任務調用Map函數(shù)對其進行評分，將結果以對應的子節(jié)點為鍵，候選結構、CPT以及打分結果為該節(jié)點所對應的值，將結果輸出至Reduce函數(shù)。Reduce階段接收Map階段的輸出，首先查找到具有相同子節(jié)點中評分最高的一項候選結構作為局部最優(yōu)結構并輸出，將對應于該項的候選結構作為key值，相對應的CPT作為value值進行輸出。偽代碼在算法2中進行詳細描述。

算法2Compute_Score

輸入: Map(Stringkey，Stringvalue)；候選結構〈D, maxR()〉及其對應的CPT；

輸出: 〈各節(jié)點最優(yōu)結構，CPT〉；

∥key為一個候選結構，value為候選結構進行相關性評分函數(shù)maxR()設置參數(shù)。

ForeachXi∈Vdo

Node=Dom(key)；∥Node為key所對應的候選結構的子節(jié)點；

S=maxR(key,value)；∥依據(jù)key和value的值調用評分函數(shù)求取相應的評分S。

End for

Return 〈Node,〈key,S,CPT〉〉；

輸入: Reduce (Stringkey，iteratorvalues)；候選結構〈Node, 〈key,S,CPT〉〉及其對應的CPT；

輸出: 〈各節(jié)點最優(yōu)結構，CPT〉；

∥key為候選結構對應的子節(jié)點，iteratorvalues包含該子節(jié)點中對應的候選結構、評分數(shù)值和相應的CPT。

Foreachvaluedo

search max(value.S)；∥找尋每一子節(jié)點中最大評分函數(shù)所對應的項。

End for

Return 〈value.key,value.CPT〉；

基于MapReduce的“評分+搜索”方法對CP-nets結構并行學習，首先并行從數(shù)據(jù)集學習得到的評分函數(shù)中所需要的參數(shù)，在對候選結構并行評分過程中利用已得到的參數(shù)，對全部節(jié)點的候選父親結構并行地完成相關系數(shù)評分，最終得到各節(jié)點的局部最優(yōu)結構以及對應屬性的CPT，通過簡單合并得到全局最優(yōu)CP-nets結構和對應結構的CPT，即完成對CP-nets結構的并行學習[10]。

4 實驗結果分析

在兩類電影數(shù)據(jù)集上進行實驗驗證：一類是由電影公司Netflix提供的電影推薦數(shù)據(jù)集，該數(shù)據(jù)集包含480 189個用戶、17 770部電影、100 480 507條評分記錄，包括動作片、冒險片等18種類型的電影；另一類是由GroupLens Research收集的MovieLens網(wǎng)站，包括了943個用戶對1 682部電影的1 000 000條評分記錄。每一種類型的電影都可以看作是CP-nets的一個屬性。

為了驗證算法的性能，將學習得到的CP-netsN與原模型CP-netsN0的主要要素進行對比，評價標準使用圖模型結構相似度和加速比。

4.1 相似度分析

CP-nets學習包括參數(shù)和結構學習，本文著重關注結構學習，選擇相似度作為評價結構學習結果的標準。相似度是指學習得到的CP-netsN與原模型CP-netsN0之間的結構相似性。由于CP-nets是描述偏好關系的圖模型，很難判斷圖模型之間的相似性。因此，可以將結構相似度轉換為邊的相似度，用邊的相似度來描述結構的相似度。相似度越高，算法的性能越好。邊的相似度公式表示為

(5)

式中：分母表示兩個CP-nets結構中邊的總數(shù)；分子表示兩個CP-nets結構中具有相同起點、終點和相同方向的邊的總數(shù)?；诰_P值方法學習CP-nets結構，是根據(jù)Dijkstra原理對可行父親集Pare(Xi)的對應值進行排序以獲得CP-nets結構。將相關系數(shù)算法和基于精確P值方法分別在Netflix數(shù)據(jù)集和MovieLens數(shù)據(jù)集下進行相似度比較，結果如圖1、圖2所示?？梢钥闯?，在不同數(shù)據(jù)集中，相關系數(shù)算法的相似度均高于精確P值方法，這表明相關系數(shù)算法在CP-nets結構學習方面具有更好的效果。

4.2 加速比分析

加速比通常被用來評估一個算法并行化的效果，可以很好地衡量節(jié)點數(shù)增加時算法效率提高的程度。設一臺計算機完成一個串行算法所需要的時間為Ts，多臺計算機并行完成一個算法所需要的時間為Tp，那么加速比為S=Ts/Tp。

為了衡量相關系數(shù)算法在不同規(guī)模數(shù)據(jù)集下的并行效果，分別使用1個節(jié)點、2個節(jié)點和3個節(jié)點的Netflix和MovieLens數(shù)據(jù)集學習CP-nets結構，記錄不同節(jié)點數(shù)時算法的運行時間，結果如表1所示?？梢钥闯?，在數(shù)據(jù)集大小保持不變的情況下，隨著節(jié)點數(shù)的增加，算法的運行時間逐漸減少，數(shù)據(jù)集的總體性能得到提高。此外，隨著數(shù)據(jù)集記錄條數(shù)的增大，算法的運行時間增加。

Netflix數(shù)據(jù)集和MovieLens數(shù)據(jù)集下算法的加速比結果如圖3、圖4所示?？梢钥闯觯跀?shù)據(jù)集大小保持不變的情況下，增大節(jié)點數(shù)，算法總體性能隨之增強；當節(jié)點數(shù)恒定時，隨著數(shù)據(jù)集記錄條數(shù)的增大，加速比也增加。在數(shù)據(jù)集較小時，加速比隨著節(jié)點數(shù)的不同變化幅度較小。隨著數(shù)據(jù)集的增大，加速比曲線更接近于線性，表明加速比不僅取決于節(jié)點數(shù)，還取決于數(shù)據(jù)集的大小。

圖1 Netflix數(shù)據(jù)集下不同算法的相似度Figure 1 The similarity of the different algorithms on the Netflix dataset

表1 Netflix和MovieLens數(shù)據(jù)集下算法的運行時間Table 1 Algorithm running time on the Netflix and MovieLens dataset

圖3 Netflix數(shù)據(jù)集下算法的加速比Figure 3 The speedup of the algorithm on the Netflix dataset

圖4 MovieLens數(shù)據(jù)集下算法的加速比Figure 4 The speedup of the algorithm on the MovieLens dataset

5 結束語

本文提出了一種從偏好數(shù)據(jù)庫中基于MapReduce框架學習CP-nets結構的相關系數(shù)并行算法，在兩類電影推薦數(shù)據(jù)集下對算法進行了評估。實驗結果表明，該算法具有較高的準確性，可以學習獲得與原模型具有較高相似度的CP-nets結構,與本文后續(xù)目標的性能接近。本文設計的算法具有較高的延展性，為今后的研究工作奠定了基礎。下一階段的工作主要包括以下2個方面：運用特征選擇中的方法，考慮樹形等特殊結構的CP-nets結構學習；借鑒貝葉斯網(wǎng)絡結構學習的方法，繼續(xù)探索其他更適合于在大規(guī)模數(shù)據(jù)集下進行CP-nets結構學習的方法。