結(jié)合反向矩陣和頻繁模式樹(shù)方法的CP-nets結(jié)構(gòu)學(xué)習(xí)

王衛(wèi)星，劉兆偉

(煙臺(tái)大學(xué) 計(jì)算機(jī)與控制工程學(xué)院，山東 煙臺(tái) 264005)

在很多應(yīng)用中，偏好數(shù)據(jù)通常都是以數(shù)據(jù)流的形式快速出現(xiàn)并連續(xù)生成的。數(shù)據(jù)流是一個(gè)潛在的無(wú)限有序序列，其中的數(shù)據(jù)項(xiàng)會(huì)隨著時(shí)間的推移不斷更新。這些數(shù)據(jù)項(xiàng)可以是簡(jiǎn)單的屬性對(duì)，如關(guān)系數(shù)據(jù)庫(kù)元組，也可以是更復(fù)雜的結(jié)構(gòu)。這些數(shù)據(jù)項(xiàng)之間到達(dá)的間隔可能不同。其典型應(yīng)用場(chǎng)景包括推薦系統(tǒng)[1]、數(shù)據(jù)預(yù)測(cè)[2]、傳感器[3]和移動(dòng)設(shè)備[4]等。傳統(tǒng)的處理數(shù)據(jù)流方法是針對(duì)靜態(tài)數(shù)據(jù)庫(kù)設(shè)計(jì)的，而靜態(tài)數(shù)據(jù)庫(kù)[5]存在以下不足：

1) 無(wú)法控制數(shù)據(jù)項(xiàng)到達(dá)的順序，系統(tǒng)無(wú)法做好即時(shí)反應(yīng)；

2) 由于內(nèi)存資源有限，當(dāng)數(shù)據(jù)量較大時(shí)，很難將數(shù)據(jù)流中的所有數(shù)據(jù)存儲(chǔ)在內(nèi)存中；

3) 由于數(shù)據(jù)項(xiàng)到達(dá)速率很快，項(xiàng)目標(biāo)記可能會(huì)延遲甚至遺漏，這在一定程度上會(huì)降低模型的性能；

4) 在某些應(yīng)用程序中易出現(xiàn)數(shù)據(jù)分布變化，無(wú)法有效地分析快速增長(zhǎng)的數(shù)據(jù)量。

由于受到以上限制，傳統(tǒng)的學(xué)習(xí)CP-nets結(jié)構(gòu)方法無(wú)法有效處理動(dòng)態(tài)場(chǎng)景中的數(shù)據(jù)流[6]。而關(guān)于數(shù)據(jù)流上學(xué)習(xí)條件偏好的研究工作很多都集中在頻繁項(xiàng)集的挖掘方法中，基于數(shù)據(jù)庫(kù)的增量性和CP-nets結(jié)構(gòu)的普適性，本文主要進(jìn)行以下工作：

1) 提出了一種基于反向矩陣的結(jié)構(gòu)在數(shù)據(jù)流上挖掘條件偏好并學(xué)習(xí)得到CP-nets結(jié)構(gòu)的方法；

2) 通過(guò)為偏好項(xiàng)建立頻繁模式樹(shù)FP-Tree，減少了候選項(xiàng)的生成，并且可以對(duì)事務(wù)進(jìn)行隨機(jī)訪問(wèn)，減少了數(shù)據(jù)庫(kù)掃描次數(shù)；

3) 在模擬數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，與其他學(xué)習(xí)CP-nets結(jié)構(gòu)的方法相比，該方法減少了內(nèi)存需求，可以更快獲得準(zhǔn)確的CP-nets結(jié)構(gòu)。

1 相關(guān)工作

作為數(shù)據(jù)流上重要的操作，挖掘頻繁項(xiàng)集是數(shù)據(jù)挖掘領(lǐng)域的重要任務(wù)之一，主要包括在事務(wù)數(shù)據(jù)庫(kù)中挖掘相關(guān)的模式規(guī)則，如關(guān)聯(lián)規(guī)則、序列規(guī)則、分類(lèi)器規(guī)則和聚類(lèi)規(guī)則等。此外，學(xué)習(xí)CP-nets結(jié)構(gòu)中的條件偏好是流式數(shù)據(jù)上的重要操作，本文利用反向矩陣挖掘頻繁項(xiàng)集的方法對(duì)動(dòng)態(tài)的條件偏好進(jìn)行了相關(guān)研究。

1.1 頻繁項(xiàng)集的挖掘

近年來(lái)，數(shù)據(jù)挖掘[7]已經(jīng)成為世界范圍內(nèi)的研究熱點(diǎn)。而頻繁項(xiàng)集的挖掘[8]是其中一項(xiàng)重要技術(shù)。對(duì)于頻繁項(xiàng)集的挖掘主要分為兩類(lèi)，一類(lèi)是傳統(tǒng)的靜態(tài)數(shù)據(jù)庫(kù)挖掘，第二類(lèi)是動(dòng)態(tài)的流式數(shù)據(jù)挖掘。

在早期的頻繁項(xiàng)集挖掘中，USHARANI et al[9]提出一種快速且可擴(kuò)展的算法：Apriori和AprioriTID算法，用于挖掘大型數(shù)據(jù)庫(kù)的重要關(guān)聯(lián)規(guī)則，在保持?jǐn)?shù)據(jù)庫(kù)大小不變的情況下，隨著平均事務(wù)的增加，執(zhí)行時(shí)間隨之增加，證明了該算法在實(shí)際應(yīng)用中的可行性。早期學(xué)者在事務(wù)數(shù)據(jù)庫(kù)、時(shí)間序列數(shù)據(jù)庫(kù)和其他類(lèi)型數(shù)據(jù)庫(kù)中進(jìn)行了廣泛挖掘頻繁模式的研究。其中大多數(shù)采用的是類(lèi)Apriori的候選項(xiàng)集生成和測(cè)試方法。但是當(dāng)數(shù)據(jù)量增大時(shí)，該方法的執(zhí)行效率有所降低。針對(duì)該問(wèn)題，HAN et al[10]提出一種新型的FP-Tree結(jié)構(gòu)，對(duì)頻繁模式的信息進(jìn)行壓縮，通過(guò)模式片段的增長(zhǎng)來(lái)挖掘完整的頻繁項(xiàng)集。該方法避免了對(duì)數(shù)據(jù)庫(kù)進(jìn)行多次掃描和生成大量候選項(xiàng)集，極大地減小了搜索空間。

與傳統(tǒng)的頻繁項(xiàng)集挖掘不同，近年來(lái)加權(quán)頻繁項(xiàng)集的挖掘被多次研究。在許多實(shí)際應(yīng)用中，事務(wù)中的項(xiàng)可能具有不同程度的重要性，而加權(quán)頻繁項(xiàng)集關(guān)注項(xiàng)在數(shù)據(jù)庫(kù)中出現(xiàn)次數(shù)的同時(shí)更注重項(xiàng)的權(quán)重，因此該方法在實(shí)際應(yīng)用中發(fā)揮了更大的作用。YOUNGHEE et al[11]提出加權(quán)頻繁項(xiàng)集挖掘的WSFI算法，并引入項(xiàng)集加權(quán)支持度的概念，定義為支持度與項(xiàng)的平均權(quán)重的乘積，該算法可以在短時(shí)間內(nèi)提高挖掘帶權(quán)項(xiàng)集的準(zhǔn)確性。

此外，AHMED et al[12]提出了一種自適應(yīng)加權(quán)頻繁模式挖掘算法(AWFPM算法)。由于在數(shù)據(jù)庫(kù)中任何批次的事務(wù)都可能會(huì)更改項(xiàng)的權(quán)重，該方法可以更好地適應(yīng)權(quán)重的變化。如果模式的自適應(yīng)加權(quán)支持度大于或等于最小閾值，則該模式稱(chēng)為自適應(yīng)加權(quán)頻繁模式。該方法利用模式增長(zhǎng)挖掘技術(shù)來(lái)避免逐級(jí)候選項(xiàng)生成的問(wèn)題，并使用全局最大權(quán)重和局部最大權(quán)重保持向下閉合性。

近年來(lái)，流式數(shù)據(jù)挖掘也一直是一個(gè)重要的研究課題。對(duì)于數(shù)據(jù)流上的頻繁項(xiàng)集，已有許多研究使用了諸如界標(biāo)模型[13]、時(shí)間衰減模型[14]和滑動(dòng)窗口模型[15]等。其中，界標(biāo)模型可以挖掘系統(tǒng)啟動(dòng)時(shí)間和當(dāng)前時(shí)間之間的所有數(shù)據(jù)，該模型的局限性在于隨著時(shí)間推移，舊項(xiàng)的權(quán)重可能會(huì)發(fā)生變化，因此之前建立的舊模型無(wú)法很好地指導(dǎo)當(dāng)前的事務(wù)。

為了對(duì)界標(biāo)模型進(jìn)行優(yōu)化，CHEN et al[14]提出時(shí)間衰減模型，該模型使用時(shí)間衰減因子表示近期事務(wù)項(xiàng)的重要程度，并引入哈希函數(shù)來(lái)估計(jì)數(shù)據(jù)項(xiàng)的密度值。此外，為處理過(guò)期事務(wù)并對(duì)項(xiàng)集支持度進(jìn)行計(jì)數(shù)，LEE et al[15]提出滑動(dòng)窗口模型，該模型將固定時(shí)間段作為流式挖掘的基本單元，減少了存儲(chǔ)空間。圖1-3展示了以上3種模型圖。

圖1 界標(biāo)模型

圖2 時(shí)間衰減模型

圖3 滑動(dòng)窗口模型

1.2 CP-nets學(xué)習(xí)

條件偏好網(wǎng)絡(luò)(CP-nets)[16]是一種表示順序偏好關(guān)系的圖形化模型。其中偏好廣泛應(yīng)用于推薦系統(tǒng)、軟件配置、群體決策等人工智能領(lǐng)域。而結(jié)構(gòu)學(xué)習(xí)在CP-nets的研究中占有重要地位。國(guó)內(nèi)外已有很多學(xué)者對(duì)于其結(jié)構(gòu)的學(xué)習(xí)進(jìn)行了多維度的研究。

KORICHE et al[17]研究了在等價(jià)查詢(xún)和占優(yōu)查詢(xún)的模型中學(xué)習(xí)CP-nets結(jié)構(gòu)的問(wèn)題，該模型通過(guò)與用戶(hù)進(jìn)行交互，從而確定具有二進(jìn)制值CP-nets的目標(biāo)偏好排序。另外，對(duì)類(lèi)似樹(shù)結(jié)構(gòu)的CP-nets的相似性也進(jìn)行了推導(dǎo)，并實(shí)驗(yàn)證明了在多屬性域中學(xué)習(xí)CP-nets的有效性。

LIU et al[18]提出在數(shù)據(jù)流中進(jìn)行CP-nets結(jié)構(gòu)學(xué)習(xí)的增量方法。對(duì)于不斷增加的偏好數(shù)據(jù)，該方法可以更好地處理累計(jì)數(shù)據(jù)。分別在仿真數(shù)據(jù)和實(shí)際數(shù)據(jù)上進(jìn)行了驗(yàn)證，即使有數(shù)據(jù)量非常大的情況下，也可以學(xué)習(xí)得到準(zhǔn)確的CP-nets結(jié)構(gòu)。在實(shí)際的樣本中，由于用戶(hù)的行為或觀察錯(cuò)誤，往往存在一些噪聲數(shù)據(jù)。文獻(xiàn)[19]介紹了一種從噪聲樣本中學(xué)習(xí)CP-nets的新模型，并提出一種在多項(xiàng)式時(shí)間內(nèi)解決該問(wèn)題的算法。實(shí)驗(yàn)證明，隨著樣本數(shù)量的增加，該方法獲得的CP-nets均收斂于初始的CP-nets.

2 相關(guān)概念

在詳細(xì)描述算法之前，本節(jié)先給出一些基本的符號(hào)解釋和定義。

定義1 偏好項(xiàng)支持度。在Ti時(shí)刻數(shù)據(jù)流DS上偏好項(xiàng)X的權(quán)重支持為sup(X)，即：

(1)

定義2 數(shù)據(jù)流DS在Ti時(shí)具有最小權(quán)重的支持計(jì)算為：

(2)

其中Tran(Bij)是在時(shí)間Ti第j組事務(wù)的數(shù)量，μ(0<μ<1)是用戶(hù)定義的最小支持度閾值。

定義3給定偏好項(xiàng)集X?I，其最小權(quán)重為γ，如果滿(mǎn)足以下條件：

sup(X)≥γ.

(3)

X稱(chēng)為在數(shù)據(jù)流DS上頻繁的偏好項(xiàng)集，即X滿(mǎn)足γ.

定義4Ti時(shí)刻，在數(shù)據(jù)流上挖掘頻繁偏好項(xiàng)即找到一組包括所有頻繁偏好項(xiàng)的集合FPI，其中：

FPI={X|X?I,sup(X)≥γ} .

(4)

定義5條件偏好網(wǎng)CP-nets(conditional preference nets)

CP-nets是一個(gè)有向圖模型G=〈V,E〉，其中V={X1,X2,…,Xn}是頂點(diǎn)集，包含所有的屬性；E={(X1,Xj)Xi∈V,Xj∈Pa(Xi)}是一組連接頂點(diǎn)對(duì)之間的有向邊集，代表屬性之間的依賴(lài)關(guān)系，即每一條有向邊起點(diǎn)的取值都影響著終點(diǎn)取值之間的偏好。對(duì)于每一個(gè)頂點(diǎn)Xi，都有一個(gè)條件偏好表CPT(Xi)與其關(guān)聯(lián)，表示其雙親節(jié)點(diǎn)Pa(Xi)對(duì)它的影響取值。DOM(Xi)是指屬性Xi的定義域，若定義域?yàn)槎?，則所得到的結(jié)構(gòu)為二值CP-nets.

CP-nets的圖G可以是有向無(wú)環(huán)的或有向循環(huán)的。本文主要研究其結(jié)構(gòu)的學(xué)習(xí)，因此工作主要集中在二值無(wú)環(huán)CP-nets上。

Cathy對(duì)于晚禮服的偏好選擇如下：對(duì)于夾克和褲子顏色的選擇，Cathy無(wú)條件的偏好黑色；而對(duì)于襯衫顏色的選擇則取決于夾克和褲子的顏色搭配，如果夾克和褲子都是相同顏色，Cathy更喜歡紅色的襯衫，相反她更喜歡白色的襯衫。

圖4 一個(gè)晚禮服選擇的CP-net

定理1條件偏好判定定理

(5)

假設(shè)X，Y兩個(gè)變量存在如下條件關(guān)系：x1y1?x2y1，x2y2?x1y2，其中，(x1,x2)∈Dom(X)，(y1,y2)∈Dom(Y).通過(guò)定理1得到，在o[Y]=y的條件下，屬性X的對(duì)象之間存在一種偏序關(guān)系，當(dāng)o[Y]=y′時(shí)，屬性X對(duì)象之間的偏序關(guān)系也隨之變化。因此，對(duì)于屬性X的偏好取決于屬性Y，即屬性Y是屬性X的父親。同理，當(dāng)存在X，Y，Z三個(gè)變量時(shí)，若滿(mǎn)足x1y1y1?x2y1y1且x2y2y2?x1y2y2，則認(rèn)為Y和Z是X的父親。

定義6頻繁模式樹(shù)FP-Tree(frequent pattern tree)

該結(jié)構(gòu)中包括水平鏈接和雙向垂直鏈接。其中水平鏈接指向樹(shù)中包含相同頻繁項(xiàng)的下一個(gè)節(jié)點(diǎn)；雙向垂直鏈接將子節(jié)點(diǎn)與其父節(jié)點(diǎn)鏈接起來(lái)，通過(guò)自下而上的掃描，提高了樹(shù)的遍歷效率，簡(jiǎn)化了挖掘過(guò)程。此外，前綴樹(shù)包含表示子事務(wù)的路徑。樹(shù)中的節(jié)點(diǎn)包含項(xiàng)、該項(xiàng)的頻繁度計(jì)數(shù)以及參與計(jì)數(shù)。給定頻繁項(xiàng)x的FP-Tree只包含與x相同頻繁度或更頻繁的節(jié)點(diǎn)。

圖5顯示了在設(shè)定支持閾值為2的情況下挖掘得到關(guān)于屬性C的頻繁模式樹(shù)，假設(shè)與C相關(guān)的子事務(wù)是由反向矩陣生成的。其中，所有比C更頻繁并且與C有共同事務(wù)的頻繁項(xiàng)都參與到樹(shù)的構(gòu)建中。如果多個(gè)頻繁項(xiàng)具有同一前綴，則將它們合并為一個(gè)分支，并相應(yīng)地調(diào)整樹(shù)中每個(gè)節(jié)點(diǎn)的信息。圖中圓形節(jié)點(diǎn)是樹(shù)中的節(jié)點(diǎn)，從樹(shù)的每個(gè)分支，使用支持計(jì)數(shù)和參與計(jì)數(shù)，識(shí)別候選頻繁模式并將其存儲(chǔ)在節(jié)點(diǎn)中。節(jié)點(diǎn)中每一項(xiàng)都包含項(xiàng)名和指向樹(shù)中具有相同項(xiàng)的第一個(gè)節(jié)點(diǎn)的指針。

圖5 C的頻繁模式樹(shù)

挖掘FP-Tree的詳細(xì)過(guò)程如下：首先選擇最頻繁的節(jié)點(diǎn)，按照節(jié)點(diǎn)指針指向下一個(gè)較不頻繁項(xiàng)的節(jié)點(diǎn)，直到到達(dá)列表中最不頻繁的項(xiàng)為止。設(shè)D為所有屬性A的偏好項(xiàng)到根節(jié)點(diǎn)的集合，F(xiàn)作為偏好項(xiàng)的頻率計(jì)數(shù)和參與計(jì)數(shù)。接下來(lái)由D生成所有候選模式X，并且刪除不具有屬性A的偏好項(xiàng)。對(duì)于候選列表中不存在的候選模式將頻繁度添加到F中，并更新D中所有項(xiàng)的參與計(jì)數(shù)。最后根據(jù)支持閾值，從候選列表中刪除非頻繁的偏好模式。

3 偏好關(guān)系挖掘

在本節(jié)中提出了挖掘偏好關(guān)系算法，該算法包括兩個(gè)階段：第一階段將偏好數(shù)據(jù)庫(kù)中的事務(wù)傳輸?shù)椒聪蚓仃嘯20]，建立相應(yīng)的反向矩陣；第二階段是對(duì)反向矩陣進(jìn)行挖掘，將挖掘的偏好關(guān)系通過(guò)條件偏好定理學(xué)習(xí)得到CP-nets結(jié)構(gòu)。

3.1 建立反向矩陣

反向矩陣是一種基于磁盤(pán)的數(shù)據(jù)布局，由兩部分組成：索引和事務(wù)數(shù)組。索引包含偏好項(xiàng)及各自的頻率。事務(wù)數(shù)組的每一行都與索引中的偏好項(xiàng)互相關(guān)聯(lián)。每一行由指針對(duì)組成，包含2部分：同一事務(wù)中下一項(xiàng)索引的行(rnext)與列(cnext)的物理地址，表示形式為(rnext,cnext).

在預(yù)處理階段，需要遍歷兩次數(shù)據(jù)庫(kù)完成對(duì)反向矩陣的構(gòu)建。首次遍歷，掃描整個(gè)數(shù)據(jù)庫(kù)，計(jì)算每個(gè)偏好項(xiàng)的頻率，然后根據(jù)頻率對(duì)項(xiàng)目列表按升序進(jìn)行排列；第二次遍歷，讀取數(shù)據(jù)庫(kù)中每個(gè)事務(wù)，并根據(jù)每個(gè)項(xiàng)的頻率按升序進(jìn)行排列。在索引部分，將數(shù)據(jù)庫(kù)中第一個(gè)項(xiàng)的位置添加到事務(wù)數(shù)組中，并保存該事務(wù)中下一個(gè)項(xiàng)的位置。接下來(lái)對(duì)數(shù)據(jù)庫(kù)中的所有事務(wù)重復(fù)此過(guò)程。建立反向矩陣算法如表1所示。

設(shè)存在屬性集V={A,B,C},每個(gè)屬性各有兩個(gè)取值A(chǔ):a1,a2;B:b1,b2;C:c1,c2.o1和o2表示屬性A的偏好關(guān)系，即o1∶a1?a2,o2∶a2?a1;o3和

表1 建立反向矩陣

o4表示屬性B的偏好關(guān)系，即o3∶b1?b2,o4∶b2?b1;o5和o6表示屬性C的偏好關(guān)系，即o5∶c1?c2,o6∶c2?c1,條件偏好表示為：o31代表b1∶a1?a2,o41表示b2∶a2?a1……偏好數(shù)據(jù)庫(kù)如表2所示。首次遍歷，掃描整個(gè)數(shù)據(jù)庫(kù)，計(jì)算每個(gè)偏好項(xiàng)的頻繁度，然后根據(jù)頻繁度對(duì)項(xiàng)目列表按升序進(jìn)行排列，結(jié)果如表3所示。第二次遍歷，讀取數(shù)據(jù)庫(kù)中每個(gè)事務(wù)，并根據(jù)每個(gè)項(xiàng)的頻率按升序進(jìn)行排列，并更新事務(wù)數(shù)組。最終得到的反向矩陣如表4所示?？梢钥闯?，如果查找支持度大于2的所有偏好項(xiàng)，從第4行開(kāi)始挖掘便可得到，因?yàn)橹挥谐霈F(xiàn)在第4行之后的偏好項(xiàng)才是頻繁的，其他項(xiàng)與支持閾值無(wú)關(guān)。

表2 偏好數(shù)據(jù)庫(kù)P

表3 偏好項(xiàng)的頻繁度

3.2 挖掘反向矩陣

建立反向矩陣是對(duì)偏好事務(wù)數(shù)據(jù)庫(kù)的預(yù)處理。對(duì)于一個(gè)給定的數(shù)據(jù)庫(kù)，反向矩陣是一次性構(gòu)建完成的。

表4 反向矩陣

本節(jié)將介紹如何從建立的反向矩陣中挖掘頻繁偏好項(xiàng)并得到CP-nets結(jié)構(gòu)。挖掘反向矩陣算法如表5所示。該算法的步驟如下：首先從反向矩陣中根據(jù)支持度閾值獲取頻繁項(xiàng)，通過(guò)跟蹤當(dāng)前的頻繁項(xiàng)，對(duì)包含當(dāng)前頻繁項(xiàng)的子事務(wù)進(jìn)行重建。該算法利用頻繁模式樹(shù)(FP-Tree)結(jié)構(gòu)，對(duì)子事務(wù)進(jìn)行存儲(chǔ)，并進(jìn)行挖掘。這樣可以最大限度地減少候選生成，不需要遞歸構(gòu)建子樹(shù)，提高了處理效率。

通過(guò)頻繁模式樹(shù)結(jié)構(gòu)挖掘得到頻繁的偏好項(xiàng)，對(duì)其進(jìn)行條件偏好判定，進(jìn)而得到每個(gè)子事務(wù)對(duì)應(yīng)的CP-nets結(jié)構(gòu)，最終對(duì)所有子事務(wù)得到的CP-nets結(jié)構(gòu)進(jìn)行整合，得到整個(gè)偏好數(shù)據(jù)庫(kù)通過(guò)反向矩陣挖掘得到的CP-nets結(jié)構(gòu)。表6和表7所示分別為根據(jù)表4得到的屬性C和屬性B的子偏好事務(wù)。

表6 屬性C的子偏好事務(wù)

表7 屬性B的子偏好事務(wù)

以表6的子事務(wù)為例，執(zhí)行算法過(guò)程：首先對(duì)屬性C即與c1,c2相關(guān)的條件偏好進(jìn)行挖掘。屬性C的頻繁模式樹(shù)如圖6所示。挖掘?qū)傩訡的FP-Tree從最頻繁的項(xiàng)o15開(kāi)始，o15存在于FP-Tree的兩個(gè)分支中，分別是(o15∶4，o26∶5和o1∶8)和(o15∶1，o35∶3和o1∶8).首先考慮第一個(gè)分支o15∶4，o26∶5和o1∶8.

圖6 頻繁模式樹(shù)FP-Tree(C)

每個(gè)分支的頻率是分支中第一個(gè)項(xiàng)的頻率減去同一節(jié)點(diǎn)的參與計(jì)數(shù)。因此，由于第一個(gè)分支中的項(xiàng)o15的頻率值為4，參與計(jì)數(shù)為0，所以第一個(gè)分支o1,o26,o15的頻率為4，此分支中所有節(jié)點(diǎn)的參與計(jì)數(shù)也將增加4.在該分支中，生成所有與o15相關(guān)的子模式，即o1,o15∶4和o1,o26∶4.

因此，該分支所有的候選偏好項(xiàng)及其計(jì)數(shù)有：o1,o26,o15∶4;o1,o15∶4;o1,o26∶4,挖掘過(guò)程如圖7所示。

考慮第二個(gè)分支：o15∶1，o35∶3和o1∶8.具有o15的第二個(gè)分支生成模式o15,o35,o1∶1，因?yàn)榇朔种蟧15的頻率為1，其參與計(jì)數(shù)為0，因此這些節(jié)點(diǎn)的參與計(jì)數(shù)都將增加1.子模式也由o15,o35,o1生成，即o35,o1∶1和o15,o1∶1.由于第二個(gè)模式已經(jīng)存在，支持計(jì)數(shù)等于4，所以只需對(duì)其進(jìn)行更新即可，更新以后支持度為5.所以得到的候選偏好項(xiàng)及其計(jì)數(shù)為：o1,o26,o15∶4,o1,o15∶5;o1,o26∶4;o1,o35,o15∶1;o1,o35∶1，挖掘過(guò)程如圖8所示。

圖7 挖掘o1,o26,o15之后的頻繁模式樹(shù)

圖8 挖掘o15,o35,o1之后的頻繁模式樹(shù)

接下來(lái)對(duì)o26進(jìn)行操作。樹(shù)中的第二個(gè)頻繁偏好項(xiàng)o26存在于分支(o26∶5和o1∶5)中，o26節(jié)點(diǎn)的參與計(jì)數(shù)為4.o1,o26∶1是從這個(gè)分支產(chǎn)生的，由于o1,o26模式已經(jīng)存在，其頻率值等于4，所以將其頻率更新為5.

該分支所有的候選偏好項(xiàng)有：o1,o26,o15∶4;o1,o15∶5,o1,o26∶5;o1,o35,o15∶1;o1,o35∶1，挖掘過(guò)程如圖9所示。

圖9 挖掘o1,o26之后的頻繁模式樹(shù)

o35存在于分支(o35∶3，o1∶8)中，o35節(jié)點(diǎn)的參與計(jì)數(shù)為1.生成模式o1,o35∶2，并將其值添加到現(xiàn)有的模式o1,o35∶1中，使其成為o1,o35∶3.

最后，所有非頻繁模式都被省略了，只剩下o1參與的頻繁模式。此時(shí)可以刪除項(xiàng)o1的FP-Tree，并生成與根節(jié)點(diǎn)相關(guān)的所有頻繁模式。

候選偏好項(xiàng)有：o1,o26,o15∶4;o1,o15∶5;o1,o26∶5;o1,o35,o15∶1;o1,o35∶3，挖掘過(guò)程如圖10所示。

圖10 挖掘o1,o35之后的頻繁模式樹(shù)

通過(guò)挖掘，由于支持閾值為3，所以得到屬性C即c1,c2頻繁的條件偏好項(xiàng)有o1,o26和o15，對(duì)偏好項(xiàng)通過(guò)定理1學(xué)習(xí)得到的CP-net結(jié)構(gòu)如圖11所示：

圖11 子事務(wù)C得到的CP-net結(jié)構(gòu)

同理，對(duì)表7的子事務(wù)B執(zhí)行同樣的操作，最終得到頻繁的偏好項(xiàng)有o5,o53和o64，即c1?c2，c1∶b1?b2和c2∶b2?b1.對(duì)其同樣進(jìn)行定理1的判定，學(xué)習(xí)得到B，C之間的條件偏好結(jié)構(gòu)如圖12所示：

圖12 子事務(wù)B得到的CP-net結(jié)構(gòu)

所以，通過(guò)對(duì)屬性B和C的子事務(wù)進(jìn)行挖掘，分別得到圖11、圖12兩個(gè)CP-nets結(jié)構(gòu)，對(duì)其進(jìn)行組合整理，最終得出包括三個(gè)屬性A,B和C的CP-net如圖13所示。

圖13 偏好數(shù)據(jù)庫(kù)P的CP-net

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

本節(jié)利用個(gè)人計(jì)算機(jī)分別在模擬數(shù)據(jù)、SUSHI偏好數(shù)據(jù)集和MovieLens數(shù)據(jù)集上分別驗(yàn)證結(jié)構(gòu)相似度(Similarity)[21]、相容度(Agreement)[19]和計(jì)算時(shí)間。計(jì)算機(jī)操作系統(tǒng)為64位Windows10,CPU型號(hào)為i5、主頻為3.2 GHz,內(nèi)存為8GB DDR3,編程語(yǔ)言為C++和Matlab,集成開(kāi)發(fā)環(huán)境為Visual Studio 2010和Matlab2014.

4.1 模擬數(shù)據(jù)結(jié)果及分析

在模擬數(shù)據(jù)實(shí)驗(yàn)中，隨機(jī)生成5個(gè)偏好數(shù)據(jù)庫(kù)P1，P2，P3，P4，P5作為測(cè)試數(shù)據(jù)集。將所學(xué)CP-nets的相似度和相容度作為評(píng)估指標(biāo)。由于圖之間的相似度很難判斷，因此評(píng)價(jià)CP-nets的相似度便轉(zhuǎn)化為邊集的相似度，相似度越高，所學(xué)結(jié)構(gòu)性能越好。公式如式(6)所示。其中，分子為所學(xué)CP-nets與偏好數(shù)據(jù)庫(kù)P中相同邊集的個(gè)數(shù)，分母為偏好數(shù)據(jù)庫(kù)中總的邊集數(shù)量。

(6)

相容度表示偏好的一致度，公式如式(7)所示。其中，分子為所學(xué)CP-nets與偏好數(shù)據(jù)庫(kù)P中條件偏好關(guān)系的相同個(gè)數(shù)，分母為偏好數(shù)據(jù)庫(kù)P中的偏好總數(shù)。

(7)

模擬實(shí)驗(yàn)設(shè)計(jì)了含有6個(gè)屬性的CP-nets.隨機(jī)生成5個(gè)偏好數(shù)據(jù)庫(kù)P1，P2，P3，P4，P5，并以700條數(shù)據(jù)為一個(gè)時(shí)間單位的偏好數(shù)據(jù)流。測(cè)定在不同時(shí)間點(diǎn)下不同偏好數(shù)據(jù)庫(kù)所學(xué)CP-nets的相似度和相容度。具體結(jié)果如圖14和15所示，并在圖16中給出了算法的運(yùn)行時(shí)間與正常學(xué)習(xí)的時(shí)間比較。

從圖14與圖15中可以看出，在模擬數(shù)據(jù)集中，學(xué)習(xí)CP-nets的相似度會(huì)隨著樣本數(shù)量增加而增加，且會(huì)迅速增加到較高值，并始終保持在較高水平。

圖14 不同樣本數(shù)量下學(xué)習(xí)CP-nets的相似度

相容度也會(huì)隨著時(shí)間的增多而增加，并且在數(shù)據(jù)量達(dá)到一定規(guī)模之后，穩(wěn)定在較高的數(shù)值。在數(shù)據(jù)量較大時(shí)，相容度和相似度均會(huì)達(dá)到較高水平，且保持穩(wěn)定。

圖15 不同樣本數(shù)量下學(xué)習(xí)CP-nets的相容度

此外，對(duì)于不同樣本數(shù)量下學(xué)習(xí)CP-nets的運(yùn)行時(shí)間如圖16所示，可以看出，運(yùn)行時(shí)間會(huì)在最初的時(shí)間單位內(nèi)不斷增加，由于只計(jì)算固定時(shí)間段內(nèi)的新數(shù)據(jù)，所以之后趨于平穩(wěn)，并始終保持在較低水平。

圖16 不同樣本數(shù)量下學(xué)習(xí)CP-nets的運(yùn)行時(shí)間

4.2 真實(shí)數(shù)據(jù)結(jié)果及分析

本實(shí)驗(yàn)從MovieLens數(shù)據(jù)集中隨機(jī)選擇某位用戶(hù)的偏好數(shù)據(jù)，任意選擇其中7個(gè)屬性作為偏好數(shù)據(jù)庫(kù)P的屬性。每次獲得900對(duì)新的偏好數(shù)據(jù)，學(xué)習(xí)得到的CP-nets結(jié)構(gòu)變化如圖17所示。其中圖17(a)顯示用戶(hù)第一個(gè)900對(duì)偏好數(shù)據(jù)所得到的CP-net.圖17(b)、17(c)和17(d)分別給出用戶(hù)獲得第二個(gè)、第三個(gè)、第四個(gè)900對(duì)偏好數(shù)據(jù)后所得到的CP-net.

圖17 CP-nets動(dòng)態(tài)學(xué)習(xí)過(guò)程1

為了驗(yàn)證偏好學(xué)習(xí)的隨機(jī)性，本次隨機(jī)選取某位用戶(hù)的前6個(gè)屬性進(jìn)行實(shí)驗(yàn)。其中，圖18(a)顯示user的前6個(gè)屬性時(shí)第一個(gè)900對(duì)偏好數(shù)據(jù)所得到的CP-net.圖18(b)顯示獲得第二個(gè)900對(duì)偏好數(shù)據(jù)所得到的CP-net.圖18(c)顯示獲得第三個(gè)800對(duì)偏好數(shù)據(jù)所得到的CP-net.圖18(d)顯示獲得第四個(gè)800對(duì)偏好數(shù)據(jù)所得到的CP-net.

圖18 CP-nets動(dòng)態(tài)學(xué)習(xí)過(guò)程2

為了驗(yàn)證算法學(xué)習(xí)CP-nets的準(zhǔn)確性，采用MovieLens數(shù)據(jù)集和SUSHI數(shù)據(jù)集，分別計(jì)算屬性個(gè)數(shù)為5，6和7時(shí)CP-nets結(jié)構(gòu)學(xué)習(xí)過(guò)程中所對(duì)應(yīng)的相容度Agreement，結(jié)果分別如圖19-20所示。

從圖19和20可以看出，在屬性個(gè)數(shù)確定時(shí)，隨算法運(yùn)行，相容度持續(xù)增加。在流式數(shù)據(jù)中，數(shù)據(jù)量的增加以及算法的持續(xù)運(yùn)行過(guò)程是不斷學(xué)習(xí)準(zhǔn)確性更高的CP-nets的過(guò)程。

圖19 算法運(yùn)行過(guò)程中的相容度1

圖20 算法運(yùn)行過(guò)程中的相容度2

4.3 算法比較

表8是本文方法在SUSHI數(shù)據(jù)集6個(gè)屬性條件下選擇200，400，800，1 600條數(shù)據(jù)時(shí)，與其他算法(卡方檢驗(yàn)、G方檢驗(yàn)、精確P值計(jì)算)的相容度比較。表9是本文方法在MovieLens數(shù)據(jù)集6個(gè)屬性條件下選擇200，400，800，1 600條數(shù)據(jù)時(shí)，與其他算法(卡方檢驗(yàn)、G方檢驗(yàn)、精確P值計(jì)算)的相容度比較?？梢缘贸觯号c其他算法相比，本文的算法相對(duì)于其他算法,在數(shù)據(jù)量較少時(shí)，相容度基本不變。在數(shù)據(jù)量較多時(shí)，要優(yōu)于其他的算法，原因是隨著數(shù)據(jù)的增多，CP-nets結(jié)構(gòu)的數(shù)量急劇增加，其他算法搜索到最優(yōu)解需要更長(zhǎng)的時(shí)間。

表8 SUSHI數(shù)據(jù)集上與其他CP-nets學(xué)習(xí)方法相容度的比較

表9 MovieLens數(shù)據(jù)集上與其他CP-nets學(xué)習(xí)方法相容度的比較

5 總結(jié)

本文提出了一種在數(shù)據(jù)流上用反向矩陣和FP-Tree進(jìn)行挖掘偏好關(guān)系的方法，利用反向矩陣的事務(wù)布局，減少了數(shù)據(jù)庫(kù)的掃描次數(shù)。為了驗(yàn)證該算法的有效性，本文使用來(lái)自SUSHI和MovieLens的數(shù)據(jù)集，將該算法與其他學(xué)習(xí)CP-nets的方法進(jìn)行了比較，理論分析和實(shí)驗(yàn)結(jié)果表明，該算法在數(shù)據(jù)量較大時(shí)，表現(xiàn)出良好的性能。