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

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

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

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

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

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

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

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

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

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

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

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

1 相關(guān)工作

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

1.1 頻繁項集的挖掘

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

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

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

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

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

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

圖1 界標模型

圖2 時間衰減模型

圖3 滑動窗口模型

1.2 CP-nets學習

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

KORICHE et al[17]研究了在等價查詢和占優(yōu)查詢的模型中學習CP-nets結(jié)構(gòu)的問題，該模型通過與用戶進行交互，從而確定具有二進制值CP-nets的目標偏好排序。另外，對類似樹結(jié)構(gòu)的CP-nets的相似性也進行了推導，并實驗證明了在多屬性域中學習CP-nets的有效性。

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

2 相關(guān)概念

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

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

(1)

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

(2)

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

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

sup(X)≥γ.

(3)

X稱為在數(shù)據(jù)流DS上頻繁的偏好項集，即X滿足γ.

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

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

(4)

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

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

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

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

圖4 一個晚禮服選擇的CP-net

定理1條件偏好判定定理

(5)

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

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

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

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

圖5 C的頻繁模式樹

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

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

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

3.1 建立反向矩陣

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

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

設(shè)存在屬性集V={A,B,C},每個屬性各有兩個取值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ù)庫如表2所示。首次遍歷，掃描整個數(shù)據(jù)庫，計算每個偏好項的頻繁度，然后根據(jù)頻繁度對項目列表按升序進行排列，結(jié)果如表3所示。第二次遍歷，讀取數(shù)據(jù)庫中每個事務(wù)，并根據(jù)每個項的頻率按升序進行排列，并更新事務(wù)數(shù)組。最終得到的反向矩陣如表4所示。可以看出，如果查找支持度大于2的所有偏好項，從第4行開始挖掘便可得到，因為只有出現(xiàn)在第4行之后的偏好項才是頻繁的，其他項與支持閾值無關(guān)。

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

表3 偏好項的頻繁度

3.2 挖掘反向矩陣

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

表4 反向矩陣

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

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

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

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

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

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

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

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

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

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

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

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

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

圖9 挖掘o1,o26之后的頻繁模式樹

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

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

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

圖10 挖掘o1,o35之后的頻繁模式樹

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

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

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

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

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

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

4 實驗結(jié)果與分析

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

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

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

(6)

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

(7)

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

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

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

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

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

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

圖16 不同樣本數(shù)量下學習CP-nets的運行時間

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

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

圖17 CP-nets動態(tài)學習過程1

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

圖18 CP-nets動態(tài)學習過程2

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

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

圖19 算法運行過程中的相容度1

圖20 算法運行過程中的相容度2

4.3 算法比較

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

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

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

5 總結(jié)

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