• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

    2020-04-29 10:55:12何新新
    智能計算機與應用 2020年2期
    關(guān)鍵詞:數(shù)據(jù)流增量滑動

    何新新, 朱 陽

    (煙臺大學 計算機與控制工程學院, 山東 煙臺 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]。

    猜你喜歡
    數(shù)據(jù)流增量滑動
    提質(zhì)和增量之間的“辯證”
    當代陜西(2022年6期)2022-04-19 12:12:22
    汽車維修數(shù)據(jù)流基礎(chǔ)(下)
    “價增量減”型應用題點撥
    一種新型滑動叉拉花鍵夾具
    Big Little lies: No One Is Perfect
    一種提高TCP與UDP數(shù)據(jù)流公平性的擁塞控制機制
    基于均衡增量近鄰查詢的位置隱私保護方法
    電信科學(2016年9期)2016-06-15 20:27:25
    基于數(shù)據(jù)流聚類的多目標跟蹤算法
    德州儀器(TI)發(fā)布了一對32位增量-累加模數(shù)轉(zhuǎn)換器(ADC):ADS1262和ADS126
    滑動供電系統(tǒng)在城市軌道交通中的應用
    海南省| 明星| 蒲城县| 慈溪市| 滁州市| 卓资县| 台州市| 定襄县| 瓦房店市| 阜南县| 三门峡市| 冀州市| 万载县| 黄龙县| 正蓝旗| 四会市| 淮安市| 鲁山县| 垫江县| 南康市| 正宁县| 泸溪县| 永宁县| 上栗县| 山丹县| 宁国市| 镇平县| 新建县| 广元市| 若尔盖县| 秦安县| 岱山县| 岳阳县| 遂昌县| 辽源市| 盘锦市| 女性| 安顺市| 铜鼓县| 苏尼特右旗| 平远县|