基于滑動窗口的CP-nets增量式學習研究

何新新, 朱 陽

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

0 引 言

在現(xiàn)代社會各專業(yè)領(lǐng)域的發(fā)展中，實時數(shù)據(jù)的研究與處理已經(jīng)比較成熟，其中包括推薦系統(tǒng)中數(shù)據(jù)流的偏好信息挖掘和決策的生成等方面的數(shù)據(jù)處理[1]。多數(shù)的偏好數(shù)據(jù)處理工作都是在靜態(tài)時刻場景中進行，并不能排除隨著時間逐漸推移甚至其他因素的不確定性對用戶的數(shù)據(jù)偏好會產(chǎn)生不容忽視的影響[2]。某個靜態(tài)時刻場景的數(shù)據(jù)庫只能判斷用戶靜態(tài)的偏好信息。并不能有效地處理動態(tài)性比較強的數(shù)據(jù)流挖掘，例如在金融市場的銀行交易[3]。

本篇論文主要集中研究的是時間因素對用戶偏好演化的影響。在現(xiàn)實社會的應用中，用戶偏好大多是動態(tài)性的，也就是說能夠隨著時間的推移而產(chǎn)生偏好的變化[4]。傳感網(wǎng)絡(luò)發(fā)展?jié)摿ο碌木W(wǎng)頁隨時間推移能夠動態(tài)地批量變換，商務(wù)網(wǎng)站提供的產(chǎn)品廣告因為客戶需求和企業(yè)計劃的改變而做出動態(tài)的調(diào)整，這都屬于動態(tài)的數(shù)據(jù)流偏好模式。要得到用戶動態(tài)的偏好信息幫助判斷用戶的購買需要和模擬用戶的購買過程，就要運用動態(tài)的數(shù)據(jù)流處理模型、即CP-nets的增量式學習研究確定偏好信息[5]。這種模型下的推薦系統(tǒng)具有的優(yōu)點就是動態(tài)地獲取用戶的偏好信息，然后根據(jù)用戶的偏好推薦合適的個性化產(chǎn)品信息[6]。

用戶的某個靜態(tài)時刻場景中的偏好在現(xiàn)實社會中的合理性和實用性都是較低的外界環(huán)境中的各種因素隨著時間前進的改變導致用戶的偏好是動態(tài)變動的，例如在頭條的新聞網(wǎng)站或者是社交網(wǎng)站中的熱門新聞和熱門搜索都是隨著時間的變化在不斷地改變，這是因為用戶的偏好在不斷地改變，興趣在不斷地更新，因此數(shù)據(jù)挖掘技術(shù)就要提出新的偏好挖掘模型來應對這種基于時間的動態(tài)數(shù)據(jù)流[7]。

動態(tài)的偏好數(shù)據(jù)挖掘在人工智能領(lǐng)域更具有挑戰(zhàn)性，雖然動態(tài)的偏好數(shù)據(jù)挖掘在數(shù)據(jù)存儲和數(shù)據(jù)流的海量增加兩方面都具有優(yōu)勢[8-9]，但也存在以下兩方面困難：

(1)數(shù)據(jù)沒有儲存，在需要時也無法獲得，每個數(shù)據(jù)元組在到達時必須被接受，一旦被丟棄，不可能再次被檢查。

(2)在靜態(tài)數(shù)據(jù)處理中，連續(xù)增加的數(shù)據(jù)將成為海量數(shù)據(jù)，由于存儲空間的增加使得CPU負荷過高。

在本文中提出的基于滑動窗口的CP-nets增量式學習方法將數(shù)據(jù)流進行動態(tài)挖掘處理，本文的主要貢獻如下：

(1)基于滑動窗口的CP-nets增量式學習方法解決了靜態(tài)數(shù)據(jù)存儲以及運算上存在的存儲空間占用大，算法耗時長等困難。

(2) 基于滑動窗口的CP-nets增量式學習方法不僅可以處理可擴展的累積偏好數(shù)據(jù)，還可以處理不斷增加流式偏好數(shù)據(jù)。

(3)實驗證明,CP-nets增量式學習方法可以學習得到一個準確的CP-net。對于同一個數(shù)據(jù)集，該方法得到的實驗結(jié)果與傳統(tǒng)學習方法得到的結(jié)果大體一致，支持任意的結(jié)果比較。

1 相關(guān)工作

隨著社會的發(fā)展，數(shù)據(jù)的產(chǎn)生逐漸趨于流式化，數(shù)據(jù)流中偏好數(shù)據(jù)挖掘研究在近年得到廣泛發(fā)展。Papini等人[10-11]提出2種從數(shù)據(jù)流中挖掘偏好關(guān)系的算法，允許指定一些特定屬性取值在所有數(shù)據(jù)中優(yōu)先可取，即提前定義不同屬性的重要性，而不是計算屬性之間的依賴關(guān)系。從現(xiàn)實意義上說一個數(shù)據(jù)模式里面屬性的偏好關(guān)系更體現(xiàn)在屬性的依賴關(guān)系，即同一屬性不同取值在約束相同的條件下對其他屬性取值偏好產(chǎn)生的重要影響。本文的工作是從偏好問題的緊湊關(guān)系定義角度看，屬性之間的依賴關(guān)系大于屬性之間的優(yōu)先關(guān)系。 與 Papini 等人的研究不同的是，本文提出的算法不是研究屬性之間的優(yōu)先級，而是主要研究屬性之間的依賴關(guān)系，并且是在動態(tài)的偏好數(shù)據(jù)流中學習CP-nets。

由于偏好信息在推薦系統(tǒng)等方面具有巨大的應用價值，從CP-nets這一偏好模型的提出，一系列學習該模型的算法被先后提出。學習CP-nets方法可以分為: 主動學習、被動學習、啟發(fā)式學習和精確學習。

Koriche等人[12]提出的主動學習算法，引導用戶通過一系列查詢來識別具有二進制值的CP-nets的偏好排序。Aggarawal等人[13]通過啟發(fā)式學習方法提出了一種不確定數(shù)據(jù)流的聚類方法，創(chuàng)建了一個不確定性模型。Liu等人[14-15]通過啟發(fā)式學習方法從含噪聲數(shù)據(jù)樣本中學習CP-nets。大多數(shù)現(xiàn)有的學習方法忽略了對噪聲數(shù)據(jù)樣本的處理，文獻[14]介紹了一種從噪聲樣本中學習CP-nets 的新模型，提出了一種多項式時間內(nèi)求解偏好問題的算法。 研究中還提出了一種從不一致例子中學習CP-nets的被動學習方法[15]，該方法利用分支搜索和界搜索將學習偏好圖形問題轉(zhuǎn)化為一個0-1規(guī)劃問題，然后將得到的偏好圖形等價地轉(zhuǎn)化為CP-nets。 Mengin等人[16-17]通過對依賴結(jié)構(gòu)的假設(shè)來研究解決了多屬性域上的CP-nets學習問題。研究所考慮的假設(shè)是屬性可分離(屬性值之間不依賴，每個屬性值的偏好獨立于其他屬性值)然后采用依賴結(jié)構(gòu)無圈圖的形式，求取一組局部偏好關(guān)系(CP-nets)。 Guerin等人[18]提出了一種不限于交換比較的啟發(fā)式在線算法，該算法是一種新的智能體學習用戶偏好的算法。 通過算法生成一系列在線查詢學習，通過創(chuàng)建節(jié)點和初始化CPT來為用戶構(gòu)建一個CP-net。Liu等人[19]從不一致的例子中得到二元和多值變量上一致的CP-net。該方法不能解決數(shù)據(jù)量增加用戶首選項可能會隨著新數(shù)據(jù)的變化而改變的問題。

以上工作都是針對靜態(tài)時刻場景中的靜態(tài)數(shù)據(jù)提出的CP-nets學習算法，本文主要針對動態(tài)的數(shù)據(jù)流中屬性之間的依賴關(guān)系進行CP-nets學習。

2 CP-nets相關(guān)概念

在本節(jié)中，主要介紹了CP-nets的表示和性質(zhì)，并且舉例說明了CP-nets在表示屬性偏好中的應用。其中，2.1節(jié)給出了CP-nets的基本定義和表示，2.2節(jié)描述了CP-nets的性質(zhì)。

2.1 CP-nets的基本定義

定義1 條件偏好關(guān)系偏好成對存在，共有3種關(guān)系(?、、≈)，用r(v,v')來記錄，r(?v, |v'|)表示屬性v'取值不變的情況下屬性v取值的偏好。在屬性集合Dom(V)中，如果存在關(guān)系v?v'，vv',v≈v'分別表示相對于屬性v用戶更偏好于屬性v'；相對于v用戶更偏好于v'；用戶在v和v'之間沒有偏好。同一屬性取值下的所有偏好對的全序關(guān)系稱為偏好關(guān)系。

定義 2 父子關(guān)系屬性之間的父子關(guān)系即依賴關(guān)系用pare(vi,vj)表示，vi為父屬性，vj為子屬性，記為pa(vj)=vi.Dom(vi)表示vi的有限定義域為Dom(vi)={o1,o2,o3,…,om},(A,B)∈V，(a1,a2)∈Dom(A)，(b1,b2)∈Dom(B),屬性A,B父子關(guān)系程度為：

(1)

定義3 條件偏好網(wǎng)絡(luò)(CP-nets)[17]CP-nets由偏好網(wǎng)絡(luò)結(jié)構(gòu)和條件偏好表(conditional preference table,CPT)兩部分構(gòu)成，CPT是一個集合(V,E)的圖模型G，其中V={v1,v2,v3,...,vn}是構(gòu)成網(wǎng)絡(luò)中節(jié)點的一組屬性變量，而E是一組連接一對屬性變量的有向邊集合E={(vi,vj)|E(vi,vj),vi,vj∈V}。其中，E(vi,vj)表示屬性vi是屬性vj的父親。每個節(jié)點都有一個條件偏好表，表示在其他屬性取值約束下該節(jié)點屬性取值的偏好。在CP-nets中，每個DOM(vi)表示vi的有限定義域。對于每個屬性vi的父屬性集合pa(vi)會影響對vi值的偏好。這定義了一個依賴圖，其中每個節(jié)點vi與pa(vi)中的每個屬性都有一條有向邊。

為了更形象地說明CP-nets結(jié)構(gòu)，圖1是以客人選擇晚宴菜單的CP-net結(jié)構(gòu)圖。集合V={W,M,S}分別代表菜單中的飲品、點心和主菜。DOM(W)={w1,w2}表示飲品，包括紅酒和茶，DOM(M)={m1,m2}表示點心，包括酥餅和蛋糕，DOM(S)={s1,s2}表示主菜，包括牛排和魚。這位客人更喜歡紅酒和蛋糕，而對于主菜的選擇取決于飲品和點心的選擇。

圖1 晚宴菜單的CP-net

2.2 CP-nets的性質(zhì)

設(shè)N為任意一個CP-net，其所能表達的條件偏好關(guān)系為? ，o1,o2,...,om∈O為決策空間O中的任意m個結(jié)果．如果在N的導出圖中，總存在包含一個或多個邊的路徑，從任意頂點oi出發(fā)均能到達oj，則說明oi和oj之間的占優(yōu)測試成立，即oj?oi。若結(jié)果序列(o1,o2,...,om)的如下關(guān)系：o1?o2?o3,oi-1?oi,...,om?o1不成立，即o1,o2,...,om不構(gòu)成環(huán)形序列，則稱CP-nets是一致的。任意一個無環(huán)的CP-net都是一致的。有環(huán)CP-nets的一致性不確定，當導出的結(jié)構(gòu)圖CPT沒有出現(xiàn)環(huán)路時，則其滿足一致性，當導出的結(jié)構(gòu)圖CPT出現(xiàn)環(huán)路時則不滿足一致性。

若結(jié)果集O上任何兩個結(jié)果之間的占優(yōu)關(guān)系都能被?所表達，總有oi?oj或oj?oi成立，則稱 CP-nets滿足完備性條件。如果N的屬性集的大小為n，屬性閾值Dom(Xi)=k，則屬性結(jié)果集O的個數(shù)為kn，若結(jié)果之間的偏好關(guān)系個數(shù)滿足kn-1(kn-1)，則N為完備的CP-net[20]。

3 基于滑動窗口的增量式學習方法

為了提高數(shù)據(jù)處理的效率和速度，本文提出的基于滑動窗口的增量式學習方法主要是將偏好數(shù)據(jù)以部分滑動的形式輸入到數(shù)據(jù)處理窗口中，將數(shù)據(jù)進行一種位序列形式的計數(shù)表示，再進行屬性之間的依賴關(guān)系學習、即CP-nets的學習。

3.1 基本定義

定義4 偏好數(shù)據(jù)流P被稱為偏好數(shù)據(jù)流，表示為P=(p1,p2,p3,...,pv)，偏好數(shù)據(jù)流目前的偏好表達式個數(shù)記為|P|=v。設(shè)屬性V={v1,v2,v3,...,vn}，屬性個數(shù)記為|V|=n。屬性vi取值的有限定義域表示為Dom(vi)={o1,o2,o3,...,om}，屬性vi的一個取值表示為Dom(vi)=oi；屬性vi的取值個數(shù)記為|Oi|=m。偏好表達式表示為:

pi=r(Dom(v1)×Dom(v2)×Dom(v3)×,...,×Dom(vn))，

(2)

定義5 偏好表達項式xj被稱為偏好表達項式，表示為：

xj=r(Dom(v1)×Dom(v1)×,...,Dom(vz)),z≤n，

(3)

偏好表達項式xj與數(shù)據(jù)流中原有的偏好表達式pi存在被包含關(guān)系xj?pi(其中i,j為任意取值)。

定義6 偏好事務(wù)序列TDS被稱為是一個連續(xù)的偏好事務(wù)序列,表示為TDS=(T1,T2,T3,...,Tn)。 其中，n表示最新傳入偏好數(shù)據(jù)流Tn。事務(wù)Ti=(p1,p2,p3,...,pw)包含w個偏好表達式, 事務(wù)Ti表示為|Ti|=w。每窗口TransSWi包含固定的事務(wù)數(shù)量|TransSWi|=m。滑動粒度大小表示為s?；瑒哟翱诒硎緸椋?/p>

TransSWi=[TN-m+s,TN-m+2s,TN-m+3s,...,TN].

(4)

滑動窗口示例如圖2所示。

圖2 滑動窗口示例

舉例說明：偏好數(shù)據(jù)庫見表1，屬性個數(shù)|V|=3，分別為V={A,B,C}，屬性取值|O|=2,分別為:A=(a1,a2),B=(b1,b2),C=(c1,c2)。TDS=T1,T2,T3,T4是當前時間一個連續(xù)的偏好事務(wù)序列，當w=3時Ti表示為Ti=(p1,p2,p3)。窗口大小表示為|m|=3，滑動粒度S=1的滑動窗口表示為：

TransSW1=[T1,T2,T3] ,TransSW2= [T2,T3,T4]。

表1 偏好數(shù)據(jù)庫表

3.2 偏好關(guān)系的位序列表示

在基于滑動窗口的增量式CP-nets學習算法中，對于當前偏好事務(wù)序列TSD的滑動窗口TransSWi中偏好關(guān)系pi的子集xj，構(gòu)造了一個二進制位序列，表示為Bit(xj)。如果偏好表達項式xj在傳輸中對于當前的窗口TransSWn存在，第i位xj被設(shè)置為1，否則，將被設(shè)置為0。

例如根據(jù)表1的偏好數(shù)據(jù)庫可得到事務(wù)T1中偏好關(guān)系p1存在偏好表達項式x:a1b1?a1b2。于是在窗口TransSW1中Bit(a1b1?a1b2)=(100)。采用位序列的表示方法得到屬性A,B的偏好關(guān)系的位序列表見表2。

表2 屬性A,B的偏好關(guān)系的位序列表

3.3 初始窗口和滑動窗口

由表2可知，TransSW1表示初始窗口，TransSW1=[T1,T2,T3]。TransSW1中將偏好關(guān)系xi(xi?p)的二進制位序列相加，計算偏好表達項式xj的支持數(shù)，即窗口TransSWi中偏好表達項式xj的個數(shù)記為sup(xj)。例如表3中:

Bit(a2b2?a1b2)=(100100001)，偏好關(guān)系的計數(shù)值sup(a2b2?a1b2)=3。由TransSW1在滑動粒度s=1時滑動得到TransSW2。根據(jù)表2中每個事務(wù)Ti中偏好表達項式xj的支持數(shù)sup(xj)|Ti將表3 中初始窗口TransSW1中的sup(xj)|T1刪除并加上事務(wù)T4中偏好表達項式xj的支持數(shù)sup(xj)|T4得到滑動窗口TransSW2。屬性A，B偏好關(guān)系的位序列見表4。

表3 初始窗口TransSW1中屬性A, B偏好關(guān)系的位序列表

表4 TransSW2中屬性A, B偏好關(guān)系的位序列表

4 CP-nets學習算法

針對屬性偏好的本質(zhì)，本文提出通過設(shè)置閾值變量對屬性偏好關(guān)系進行定量判斷后近似為定性偏好信息，該定性信息體現(xiàn)在CP-nets中能夠描述屬性之間的偏好關(guān)系。

4.1 基本定理

定理1比較2個屬性之間的偏好關(guān)系時，可以理論上完全產(chǎn)生S=|O||O|×(|O||O|-1)對偏好關(guān)系，只有一個屬性固定取值，另一個屬性取值存在偏好關(guān)系時，即滿足r(?vn|vm=oi)或者r(?vm|vn=oj)才是有效偏好關(guān)系。理論上產(chǎn)生有效偏好關(guān)系的個數(shù)為S'=|O|3×(|O|-1)。在偏好數(shù)據(jù)流中有效偏好關(guān)系的數(shù)量占總數(shù)量一定比例，才能判定屬性之間是否可能存在父子系。公式(5)和公式(6)可分別表示為：

(5)

(6)

公式(5)、(6)中設(shè)置一個用戶自定義的閾值α來約束存在父子關(guān)系的可能性。閾值α的取值根據(jù)窗口數(shù)據(jù)流的大小、偏好數(shù)據(jù)量以及用戶對偏好關(guān)系的精確度確定。

舉例說明：假設(shè)屬性A與B取值分別是(a1,a2)，(b1,b2)，產(chǎn)生22×(22-1)=12對偏好關(guān)系。理論上有效的偏好關(guān)系有|2|3×(|2|-1)=8對。實際數(shù)據(jù)中有效偏好的關(guān)系隨著數(shù)據(jù)的改變而改變。

定理1中假設(shè)S1>α(或者S2>α)成立，說明vn,vm可能存在偏好關(guān)系vn?vm，(或者有偏好關(guān)系vm?vn)即Pa(vn)=vm(Pa(vm)=vn)成立，S(vn|vm)≤α說明vm,vn不可能存在偏好關(guān)系vn?vm(或者偏好關(guān)系vm?vn)，即Pa(vm)≠vn(Pa(vn)≠vm)。如果公式(5)、(6)同時成立則比較S1與S2的取值大小，如果S1>S2≥α，則vn?vm關(guān)系成立存在最大可能性，否則vm?vn。

定理2如果滿足定理1即說明兩屬性之間可能存在一種偏好關(guān)系，確立了子屬性的待定父親屬性，待定父親屬性的不同取值對于子屬性取值偏好關(guān)系產(chǎn)生的影響大體一致，這里設(shè)計一個自定義的閾值β來容納父屬性對子屬性的影響存在一定偏差。閾值變量β可以根據(jù)用戶對于屬性依賴度的需求自行定義。該定理的公式(7)、 (8)可分別表示為：

(7)

(8)

公式(7)、(8)能夠進一步確定偏好關(guān)系，確定定理1中篩選出的父子關(guān)系是否成立。

進一步考慮vn的不同取值對vm取值的偏好關(guān)系產(chǎn)生的影響在允許偏差內(nèi)一致，當定理1滿足表達式S1>α，S1>S2≥α，定理2滿足表達式N1=1±β時屬性vn與屬性vm之間存在偏好關(guān)系vn?vm，vn=pa(vm)成立；同理,當定理1滿足表達式S2>α，S2>S1≥α，定理2滿足表達式N2=1±β時屬性vn與屬性vm之間存在偏好關(guān)系vm?vn，vm=pa(vn)成立。

基于以上定理分析，可以得到算法1所示的偽代碼和圖3所示的算法流程圖。

算法1 基于滑動窗口的CP-nets增量式學習算法

輸入TDS(偏好事務(wù)序列), 閾值α, 閾值β

輸出a CP-net

TransSW= null;

/* TransSW 由m個TDS 組成*/

repeat:

for each incoming transactionTiinTransSW

dobit-sequence(x)

ifbit-sequence(x)≠0, then

doSub(xi)

for

ifS(vn|vm)≥α, then

ifS*(vn|vm)=1±βthen

draw the dependenciesvn?vmin existence

else error

end if

elseS(vm|vn)≥α，then

ifS*(vn|vm)=1±βthen

draw the dependenciesvm?vnin existence

else error

end if

end if

end for

end for

圖3 增量式算法流程圖

算法1的計算復雜度首先從掃描數(shù)據(jù)庫進行單個比較數(shù)據(jù)時算起,單個比較數(shù)據(jù)的屬性個數(shù)為n，這時的算法復雜度為O(n)，一對屬性之間依賴程度的計算復雜性為O(n2)。計算一個偏好事務(wù)序列的長度為w，所以計算每個事務(wù)的計算復雜度是O(n2)w，每滑動窗口的長度為T=m, 所以計算每個窗口中數(shù)據(jù)偏好的計算復雜度是O(n2)wm。

定理3定理1中的S(vn,vm)表示父屬性對子屬性的影響度，Min(S(vn,vm))表示影響度最小的兩屬性之間的邊E(vn,vm)。

為了滿足CP-nets的一致性，CP-nets結(jié)構(gòu)中不允許環(huán)的存在，在一個CP-net中每個屬性都至少有一個父屬性的存在則說明該CP-net是有環(huán)CP-net,即存在環(huán)的CPT結(jié)構(gòu)中不存在邊入度(V-in-degree)為0的屬性。根據(jù)定理3,設(shè)計算法Dedge(C,C')進行去環(huán)。如果C不存在邊入度為0的屬性節(jié)點，則說明C存在環(huán)路；若C中存在邊入度為0的屬性節(jié)點vi，在其副本C'中刪除當前節(jié)點以及與其相連的邊，并重新更新節(jié)點的邊入度值后刪除新的邊入度為0 的節(jié)點。如果所有節(jié)點都被刪除則說明C中不存在環(huán)，如果存在未被刪除的節(jié)點則說明C中存在環(huán)，刪除定理3中影響度最小的兩屬性之間的有向邊E(vn,vm)，重新進行Dedge(C,C')算法直至結(jié)構(gòu)C不存在環(huán)。至此，給出算法2的偽代碼詳見如下。

算法2 無環(huán)CP-nets結(jié)構(gòu)學習算法

輸入增量式學習得到的CP-netC

輸出最優(yōu)CP-net

Dedge(C,C')

/* C'表示記錄結(jié)構(gòu)學習的副本*/

while(existenceV-in-degree=0) do

for eachvi?C

Ifvi-in-degree=0

Deletevi,edgevi->vi,

C'←new in-degree table; /*將新的邊入度信息更新到副本C'*/

end if

end for

end while

ifC' !=null

deleteMin(S(vn,vm))edgefromC;

Dedge(C,C')

end if

ifC'=null

returnC

end if

4.2 算法舉例

圖4 屬性A, B的偏好網(wǎng)絡(luò)結(jié)構(gòu)圖

在得到滑動窗口TransSW1中屬性A與屬性B的依賴關(guān)系后，根據(jù)表1偏好數(shù)據(jù)庫表分別求屬性B與屬性C,屬性A與屬性C之間的偏好關(guān)系。屬性B與屬性C偏好關(guān)系最后的位序列表,即TransSW1中得到的sup(?(Dom(B)×Dom(C)))計數(shù)如下：

根據(jù)定理可得屬性B與屬性C之間存在偏好關(guān)系B?C。屬性A與屬性C偏好關(guān)系最后的位序列表,即TransSW1中得到的sup(?(Dom(A)×Dom(B)))計數(shù)如下：

sup(a1c1?a2c1)=1

sup(a2c2?a1c2)=1

根據(jù)定理可得屬性A與屬性C的關(guān)系為C?A即Pa(A)=C。 屬性之間的偏好關(guān)系是A?B?C?A,每個屬性的入度都不為0，Min(S(A,C))=2,所以刪除edge(A,C)。根據(jù)表1的偏好數(shù)據(jù)庫表可得屬性A,B,C的偏好網(wǎng)絡(luò)結(jié)構(gòu)圖如圖5所示。

圖5 屬性A, B, C的偏好網(wǎng)絡(luò)結(jié)構(gòu)圖

5 實驗與結(jié)果

5.1 數(shù)據(jù)來源

本文在 Matlab上進行實驗測試，實驗數(shù)據(jù)分別是合成的隨機數(shù)據(jù)集和真實數(shù)據(jù)集。對合成的隨機數(shù)據(jù)集進行測試的目的是評估算法處理大數(shù)據(jù)的能力，對真實數(shù)據(jù)集進行測試是為了評估算法在真實數(shù)據(jù)集上的可應用性。其中真實數(shù)據(jù)集來自于Kamishima收集的壽司數(shù)據(jù)集[21]。

5.2 實驗結(jié)果分析

本文在合成數(shù)據(jù)集上的測試目的是將CP-nets增量式學習與CP-nets傳統(tǒng)學習[14-15]的運行時間進行對比。合成數(shù)據(jù)集包含用戶的4 500對偏好關(guān)系，其中數(shù)據(jù)集包含30個屬性。分別將隨機用戶U1,U2做CP-nets增量式學習與CP-nets傳統(tǒng)學習[14-15]運行時間的平均值進行對比。

圖6中水平軸表示成對屬性比較的次數(shù)，垂直軸表示用戶U1,U2運行時間的平均值。 圖6(a)是用戶輸入15個屬性的200對偏好數(shù)據(jù)時CP-nets增量式學習與CP-nets傳統(tǒng)學習[14-15]運行時間的平均值進行對比；圖6(b)是用戶輸入15個屬性的4 500對偏好數(shù)據(jù)時CP-nets增量式學習與CP-nets傳統(tǒng)學習[14-15]運行時間的平均值進行對比；圖6(c)是用戶輸入30個屬性的4 500對偏好數(shù)據(jù)時CP-net增量式學習與CP-net傳統(tǒng)學習[14-15]運行時間的平均值進行對比。實驗結(jié)果表示本文提出的CP-nets增量式學習算法在運行時間上少于CP-net傳統(tǒng)學習的運行時間。

在真實數(shù)據(jù)集的測試目的是將CP-nets增量式學習與CP-nets傳統(tǒng)學習[14-15]的運行結(jié)果和運行時間進行對比。研究考慮2個隨機用戶U1,U2與壽司選擇相關(guān)的偏好數(shù)據(jù)集[21]，壽司的5個屬性分別表示為A1,A2,A3,A4,A5。文中分別求了用戶U1,U2以每次20對偏好數(shù)據(jù)增量從100對數(shù)據(jù)增加到200對數(shù)據(jù)的偏好網(wǎng)絡(luò)結(jié)構(gòu)圖。

(a) 對比結(jié)果1 (b) 對比結(jié)果2 (c) 對比結(jié)果3

圖7表示CP-nets增量式學習算法中用戶U1以每次20對偏好數(shù)據(jù)增量從100對數(shù)據(jù)增加到200對數(shù)據(jù)得到的偏好網(wǎng)絡(luò)結(jié)構(gòu)圖。用戶U1在數(shù)據(jù)增加的每個階段得到偏好網(wǎng)絡(luò)結(jié)構(gòu)圖不同，該結(jié)果表明偏好數(shù)據(jù)增量會對用戶的CP-nets、即用戶偏好產(chǎn)生影響。圖8表示的是傳統(tǒng)學習CP-nets算法中用戶U1以每次20對偏好數(shù)據(jù)增量從100對數(shù)據(jù)增加到200對數(shù)據(jù)得到的偏好網(wǎng)絡(luò)結(jié)構(gòu)圖。對比與圖7所得的結(jié)果圖，圖8展示的所有屬性偏好包含于圖7所示的屬性偏好中，該實驗結(jié)果表示CP-nets增量式學習與CP-nets傳統(tǒng)學習得到的偏好結(jié)果大體一致，本文提到的增量式學習CP-nets算法得到的偏好關(guān)系是準確的。

綜上所述,CP-nets增量式學習算法能夠得到用戶屬性的動態(tài)性偏好網(wǎng)絡(luò)結(jié)構(gòu)圖，并且得到的屬性之間的偏好關(guān)系是準確的。

圖7 CP-nets增量式學習算法中用戶U1的實驗結(jié)果

Fig. 7 Experimental results of userU1in incremental learning algorithm

圖8 傳統(tǒng)學習CP-nets算法中用戶U1的實驗結(jié)果

Fig. 8 Experimental results of userU1in traditional learning algorithm

圖8分別表示用戶U1,U2以每次20對的增量從100對偏好數(shù)據(jù)增加到200偏好數(shù)據(jù)，CP-nets增量式學習與CP-nets傳統(tǒng)學習[14-15]在得到某一時刻的CP-nets所用的確定時間進行了比較。圖9(a)表示用戶U1的增量學習與傳統(tǒng)學習運行時間的比較；圖9(b)表示用戶U2的增量學習與傳統(tǒng)學習運行時間的比較。圖9中，用戶U1，U2做CP-nets增量式學習的運行時間在數(shù)據(jù)增加過程中大致相同并且耗時隨著數(shù)據(jù)增量的逐漸增加大幅度少于同時刻傳統(tǒng)學習CP-nets的運行時間，而CP-nets傳統(tǒng)學習的運行時間隨著數(shù)據(jù)增量的增加逐漸呈線性增加。實驗表明,本文提出的CP-nets增量式學習方法對于隨機用戶都是適用且高效的。

(a) 用戶U1學習CP-nets確定運行時間變化

(b) 用戶U2學習CP-nets確定運行時間對比

Fig. 9 UserU1,U2learning CP-nets determine runtime comparison

6 結(jié)束語

本文主要設(shè)計了一種從偏好數(shù)據(jù)流中學習CP-nets的增量方法。通過在合成數(shù)據(jù)和真實數(shù)據(jù)上進行的一系列廣泛的實驗表明，本文提出的算法可以用于處理大數(shù)據(jù)集，并且可以輸出一個表示對應用戶屬性偏好依賴關(guān)系的無環(huán)CP-nets。對于不同時間段的偏好信息,也可以根據(jù)增量數(shù)據(jù)求出特定時刻用戶的CP-nets，有效利用偏好信息的即時性價值。同時，實驗表明本文的算法相較于其它算法能夠得到一個大致相同的CP-nets，并且該算法可以有效地節(jié)省存儲空間和減少運行時間[22]。

在今后的學習研究中主要有2部分工作。 一方面是，提高CP-nets模型性能的學習方法是進一步研究的主要方向。并計劃研究其他分類的CP-nets學習方法。希望能夠進一步更準確高效地學習CP-nets模型。后續(xù)還考慮將CP-nets模型與模糊集學習相結(jié)合，研究模糊條件偏好網(wǎng)絡(luò)的可行性[23]。另一方面是計劃學習比CP-nets更具有拓展性和研究性的TCP-nets[24]和PCP-nets[25]。