基于Dandelion編碼生成有界樹寬CP-nets

李叢叢，劉驚雷

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

0 引言

條件偏好網(wǎng)絡(luò)（Conditional Preference networks，CP-nets）是常見的圖模型之一，它以一種緊湊簡潔的方式有效地表示了復(fù)雜的多元域中隨機(jī)變量的條件偏好。該網(wǎng)絡(luò)由兩部分組成：編碼生成了模型中變量間依賴或獨(dú)立關(guān)系的有向無環(huán)圖（Directed Acyclic Graph，DAG）以及能夠重構(gòu)條件偏好的條件偏好表（Conditional Preference Table，CPT）。隨著模型中變量數(shù)的增多，從數(shù)據(jù)中對CP-nets網(wǎng)絡(luò)的推理學(xué)習(xí)是NP-hard。

樹寬為k的樹結(jié)構(gòu)（k-tree）是對樹結(jié)構(gòu)最自然、最有趣的概括之一［1-2］，國內(nèi)外的研究者通過k-tree 來學(xué)習(xí)約束CP-nets的有界樹寬結(jié)構(gòu)，且越來越多的研究者對開發(fā)有效的工具來操作這類圖非常感興趣。事實(shí)上，每個(gè)樹寬為k的圖都是ktree的子圖，利用此特征，用k-tree來約束CP-nets的樹寬，并實(shí)現(xiàn)其生成問題［3］。有界樹寬的CP-nets 在進(jìn)行推理運(yùn)算時(shí)可提高推理算法的效率并且有許多NP-hard 問題在有界樹寬的圖模型中已經(jīng)被證明是多項(xiàng)式可解的［4］。由此可知，有界樹寬的CP-nets 提高了圖模型推理的效率且保障了推理計(jì)算的有效性。

本文利用k-tree 生成有界樹寬的CP-nets，主要研究的是由Dandelion 編碼與k-tree 雙向映射的過程，并且利用k-tree 完成對CP-nets樹寬的約束。由k-tree編碼形成標(biāo)記序列的過程中，要經(jīng)過以下步驟：首先由k-tree 轉(zhuǎn)換為Renyik-tree；再者由Renyi tree 轉(zhuǎn)換為特征樹［2］；最后由對應(yīng)的特征樹編碼成Dandelion編碼序列。相反在Dandelion解碼生成k-tree的過程中，經(jīng)過以下步驟：首先由Dandelion 編碼生成特征樹；由特征樹生成Renyi tree；最后由Renyitree轉(zhuǎn)換生成對應(yīng)的k-tree。

本文有如下的特點(diǎn)和貢獻(xiàn)：

1）針對特殊結(jié)構(gòu)（有界樹寬）的CP-nets 的生成問題提出了一種基于Dandelion 編碼的算法框架，其核心思想是通過Dandelion編碼來生成有界樹寬的CP-nets結(jié)構(gòu)，建立了編碼與結(jié)構(gòu)的一對一關(guān)系；完整實(shí)現(xiàn)了k-tree的生成過程。由此隨機(jī)均勻地生成限定樹k的CP-nets。

2）與傳統(tǒng)的生成方法不同，所提出的算法由Dandelion編碼生成有界樹寬的CP-nets（Generating CP-nets with Bounded Tree Width based on Dandelion code，BTW-CP-nets Gen）的完整過程是在線性時(shí)間內(nèi)完成。在線性時(shí)間內(nèi)生成高質(zhì)量的有界樹寬CP-nets來提高推理算法的效率有更高的應(yīng)用價(jià)值。

3）將生成的圖結(jié)構(gòu)用于常見的CP-nets 推理算法——占優(yōu)查詢。以此推理算法來檢測生成結(jié)構(gòu)更均勻，且驗(yàn)證推理算法難度的影響因素。基于實(shí)例數(shù)據(jù)集樣本進(jìn)行測試，生成多樣式有界樹寬的圖模型，通過對特殊結(jié)構(gòu)圖模型進(jìn)行推理運(yùn)算證明其推理算法其時(shí)間消耗嚴(yán)重依賴于圖的樹寬結(jié)構(gòu)。

1 相關(guān)工作

近年來，有界樹寬圖模型的生成已受到國內(nèi)外眾多領(lǐng)域研究者們的關(guān)注。標(biāo)記樹的編碼問題在文獻(xiàn)中得到了廣泛的研究。

CP-nets首先由Boutilier等［4］在2004年提出。他們利用條件性的其他條件不變的偏好規(guī)則，以實(shí)現(xiàn)偏好關(guān)系的緊湊表示。近年來，在國內(nèi)，研究者們大多數(shù)都通過圖來表示隨機(jī)變量間的依賴關(guān)系，為多變量統(tǒng)計(jì)建模提供了有力的表示框架［5］。圖模型理論的基礎(chǔ)是問題域中不同屬性集之間的條件獨(dú)立性與結(jié)構(gòu)的多樣性其中結(jié)構(gòu)的多樣性［6］，可根據(jù)標(biāo)記編碼生成［7］。Robinson［7］研究了標(biāo)記和未標(biāo)記的DAG計(jì)數(shù)問題，推導(dǎo)了生成DAG結(jié)構(gòu)的編碼中的遞歸式。

以往的研究工作提出了幾種實(shí)現(xiàn)標(biāo)記樹與標(biāo)記序列之間關(guān)聯(lián)的雙射碼［8-9］。1970年，Renyi［10］推廣了Pruffer關(guān)于Cayley定理編碼標(biāo)記k-tree 子集的雙射證明，并命名有根的k-tree 為Renyik-tree。他們在Renyik-tree 中引入了一個(gè)冗余的Pruffer碼，并對有效碼字進(jìn)行了特征描述。隨后，產(chǎn)生了k-tree（或Renyik-tree）與一組定義良好的字符串之間的雙射的非冗余碼［11-12］并結(jié)合編碼和解碼算法。Caminiti 等［13］提出了利用冗余Pruffer 碼對Renyik-tree 進(jìn)行編碼和解碼算法；但是此算法的時(shí)間復(fù)雜度非線性時(shí)間［14-17］，并且所提出的解碼算法在非有效碼字的字符串上失敗。算法以這些結(jié)果為基礎(chǔ)來研究基于Dandelion編碼生成有界樹寬CP-nets的情況。

以往研究工作提出了幾種學(xué)習(xí)有界樹寬圖結(jié)構(gòu)的算法。文獻(xiàn)［18］設(shè)計(jì)了一種近似算法，結(jié)合多種啟發(fā)式算法計(jì)算樹寬并學(xué)習(xí)圖結(jié)構(gòu)。Korhonen等［19］提出了一種基于動態(tài)規(guī)劃的學(xué)習(xí)算法，學(xué)習(xí)最多k個(gè)樹寬的n個(gè)節(jié)點(diǎn)貝葉斯網(wǎng)絡(luò)。他們的算法保證在復(fù)雜度為O(3nnk+O()1)的樹寬約束下，在n個(gè)節(jié)點(diǎn)上尋找給定評分函數(shù)的最優(yōu)結(jié)構(gòu)。2018 年，王慧玲等［17］就目前有界樹寬的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)近似學(xué)習(xí)技術(shù)做了深入的探討并且歸納了有界樹寬的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)亟待解決的兩個(gè)問題，雖然該算法能找到期望樹寬的最高分網(wǎng)絡(luò)，但是由于其時(shí)間復(fù)雜性隨著變量數(shù)呈指數(shù)級增加。文獻(xiàn)［18］給定一個(gè)圖G和G的成對的不同頂點(diǎn)的集合，找到G的最小邊集。即使將輸入圖限制為樹，算法也被認(rèn)為是NP-hard。Parviainen 等［20］開發(fā)了一種整數(shù)規(guī)劃方法解決這個(gè)問題。它迭代地在當(dāng)前解決方案上創(chuàng)建一個(gè)切割平面，以避免指數(shù)級的許多約束。然而，所有精確的算法只適用于小的網(wǎng)絡(luò)和小的樹寬。為了解決這個(gè)問題，引入了復(fù)雜度與輸入量呈線性關(guān)系的精確算法和基于k-tree生成有界樹寬CP-nets的實(shí)現(xiàn)步驟［21］。

2 關(guān)于圖模型的基本符號與定義

2.1 條件偏好圖CP-nets

定義1設(shè)CPT（Xi）為屬性Xi的條件偏好表，它表示Xi在其父屬性Pare（Xi）的不同取值下，對集合Dom（Xi）的排序，在Pare（Xi）的所有取值下，對Xi取值的排序構(gòu)成CPT（Xi）。

定義2CP-nets 是一個(gè)有向圖N=其中V是頂點(diǎn)集；CE是有向邊集，代表所有屬性之間的依賴關(guān)系，每個(gè)頂點(diǎn)Xi都有CPT（Xi）與其關(guān)聯(lián)。

例1 某人一天飲品搭配主要考慮咖啡、茶和牛奶，分別用A、B、C表示，其中早上的咖啡種類與中午的茶種類決定晚上的牛奶種類。對于早上的咖啡，他喜歡黑咖啡勝過白咖啡。對于中午的茶，他喜歡紅茶勝過綠茶。對于晚上的牛奶，若白天選了黑咖啡紅茶或白咖啡綠茶，則選純牛奶而不是酸牛奶；其他情況，則選酸牛奶而不是純牛奶。該實(shí)例的CP-nets 圖其中：a0表示黑咖啡，a1表示白咖啡，c0表示紅茶，c1表示綠茶，b0表示純牛奶，b1表示酸牛奶。如圖1 所示，其中，V={A，B，C}，Dom(A)={a0，a1}，Dom(C)={c0，c1}，Dom(B)={b0，b1}，CE=

圖1 例1中的CP-nets結(jié)構(gòu)示意圖Fig.1 Schematic diagram of CP-nets in example 1

2.2 有界樹寬的CP-nets

在圖論中，無向圖的樹寬與圖的樹分解有關(guān)。樹分解是從無向圖到樹的映射。無向圖的樹寬是圖的所有可能樹分解的最小寬度。

現(xiàn)有的精確推理算法和具有理論保證的近似推理算法在最壞情況下的復(fù)雜度是樹寬的指數(shù)形式或者NP-hard。事實(shí)，Kwisthout 等［22］證明了在多項(xiàng)式時(shí)間下，沒有算法可以解決任意圖結(jié)構(gòu)的推理問題。此外，如果假設(shè)指數(shù)時(shí)間成立且存在一個(gè)對于任意推理問題都有效的樹寬值k，那么此推理算法的時(shí)間復(fù)雜度為(O(klbk))且認(rèn)為(O(klbk))是精確推理復(fù)雜度的一個(gè)下界。因此，有必要生成有界樹寬的CP-nets，以提高推理算法的效率。通過對圖的樹寬進(jìn)行約束，簡化了模型，在表示能力和推理效率之間進(jìn)行了權(quán)衡。

直接計(jì)算圖的樹寬是一個(gè)棘手的問題。實(shí)施樹寬約束的一種方法是使用k-tree。所以在本文中，利用隨機(jī)生成k-tree來實(shí)現(xiàn)有界樹寬CP-nets的生成。

定義3k-tree的歸納定義如下：

1）一個(gè)（k+1）的團(tuán)是一個(gè)k-tree。

2）用G=(V，E)表示一個(gè)k-tree，并且C?V是包含k個(gè)頂點(diǎn)的集合。如果歸納出的子圖G(C)是k-團(tuán)，那么對于每個(gè)u∈C，添加一個(gè)新的頂點(diǎn)v和一條邊u-v得到的圖結(jié)構(gòu)就是ktree。

k-tree 是樹寬為k的最大圖，如果不增加樹寬，就不可以添加更多的邊。因此，樹寬不超過k的每個(gè)圖都是k-tree 的子圖［23］。如果確保所生成的CP-nets 的DAG 結(jié)構(gòu)圖是k-tree 的子圖，則從k-tree 學(xué)習(xí)CP-nets 自動滿足樹寬約束。k-tree 用Tk表示，n個(gè)節(jié)點(diǎn)上所有k-tree 的集合用表示，n個(gè)變量上的k-tree總數(shù)為

在k-tree 中，入度為k的節(jié)點(diǎn)稱為k-leaf。每個(gè)k-leaf 的鄰域形成一個(gè)團(tuán)，然后k-leaf是單純節(jié)點(diǎn)。

定義4Dandelion 編碼定義為一對(Q，S)，其中Q?{1，2，…，n}是包含k個(gè)整數(shù)的集合，S是一個(gè)(n-k-2)× 2 矩陣，其行是(i，j)，其中1 ≤i≤n-k，1 ≤j≤k或者是(0，ε)，其中ε是一個(gè)不在{1，2，…，n}的任意數(shù)。并且的基數(shù)可表示為(k×(n-k)+1)n-k-2。

例2 Dandelion 編碼的一個(gè)例子是：12 個(gè)節(jié)點(diǎn)的3-tree（n=12，k=3）的Q=［1，2，3］，S=此編碼所對應(yīng)的k-tree如圖2所示。

圖2 例2中的3-tree結(jié)構(gòu)Fig.2 3-tree structure in example 2

3 Dandelion編碼與k-tree的雙向映射

本章介紹一種隨機(jī)均勻生成有界樹寬CP-nets的方法，這種方法的一個(gè)關(guān)鍵思想是有界樹寬CP-nets的結(jié)構(gòu)由k-tree進(jìn)行約束。第3.1 節(jié)介紹了k-tree 與有界樹寬CP-nets 的中間變量特征樹；第3.2 節(jié)介紹了Dandelion 編碼與k-tree 之間的編碼算法；第3.3 節(jié)介紹了Dandelion 編碼與k-tree 之間的解碼算法。

3.1 特征樹

在本節(jié)著重介紹有根k-tree 的特征樹，是k-tree 與有界樹寬CP-nets 的中間變量，因?yàn)閷⒃诰幋a過程中使用有根的ktree（即Renyik-tree）的特征樹。首先本節(jié)先介紹一個(gè)有根的k-tree的骨架。

定義5給定一個(gè)根為R的k-treeTk，通過添加一個(gè)連接到k-clique 的新節(jié)點(diǎn)v，可以得到根為R的Tk′，骨架S(Tk，R)由在S(Tk′，R)上添加一個(gè)新節(jié)點(diǎn)X=(v∪k)和一條新邊得到。Y是S(Tk′，R)的節(jié)點(diǎn)，它包含了k-leaf 到根的最小距離。如果Tk是一個(gè)k-tree就是一個(gè)節(jié)點(diǎn)為R的樹。

定義6通過標(biāo)記S(Tk，R)的節(jié)點(diǎn)和邊，得到根為R的ktreeTk(Tk′，R)的特征樹T(Tk，R)：

1）根節(jié)點(diǎn)R標(biāo)記為0，各節(jié)點(diǎn){v}∪K標(biāo)記為v；

2）從節(jié)點(diǎn){v}∪K到它的父節(jié)點(diǎn){v′}∪K的每條都用K′中沒有出現(xiàn)的節(jié)點(diǎn)（一個(gè)有序集）的索引標(biāo)記。當(dāng)某節(jié)點(diǎn)的父節(jié)點(diǎn)為R時(shí)，其索引邊用ε標(biāo)記。

在本文所提出的代碼中，將使用Renyik-treeRk的特征樹作為有界樹CP-nets的DAG結(jié)構(gòu)。下文中，將骨架稱為S(Rk)，將特征樹稱為T(Rk)。

例3 在圖3 舉例顯示了一棵有12 個(gè)節(jié)點(diǎn)的Ranyi 3-tree、它的骨架和特征樹。

圖3 n=12時(shí)3-tree的骨架與特征樹舉例Fig.3 Examples of 3-tree skeleton and feature tree when n=12

定理1對于任意一個(gè)具有n個(gè)節(jié)點(diǎn)的Renyik-tree，其基數(shù)與它的特征樹基數(shù)的關(guān)系為：|Zkn|=|Rkn|，且Ranyik-tree 與其特征樹T(Rk)之間的聯(lián)系是雙射關(guān)系。

3.2 Dandelion編碼與樹之間的編碼實(shí)現(xiàn)

本節(jié)著重介紹了Dandelion 編碼與k-tree 之間的編碼實(shí)現(xiàn)過程，本文算法首先對Renyik-tree 中的k-tree 進(jìn)行轉(zhuǎn)換：在特定的團(tuán)Q處將k-tree 的Tk根化，然后執(zhí)行重新標(biāo)記方法以獲得Renyik-treeRk。這個(gè)過程中要求最高的步驟是從Rk開始計(jì)算T(Rk)，將證明即使這一步也可以在線性時(shí)間內(nèi)完成。將Tk轉(zhuǎn)換為Rk的重新標(biāo)記的信息。

編碼得到的代碼是雙射的：可通過解碼過程證明，此解碼過程能夠?qū)⒅械拿總€(gè)代碼與相應(yīng)的k-tree 相關(guān)聯(lián)，并且其基數(shù)關(guān)系如下：|Akn|=|Tkn|。由k-tree 到Dandelion 編碼的編碼算法可分為以下步驟。

3.2.1 將k-treeTk轉(zhuǎn)換成有根的Renyik-treeRk

計(jì)算每個(gè)節(jié)點(diǎn)v的度d(v)并找到lM，即度為k的最大節(jié)點(diǎn)v，則節(jié)點(diǎn)集Q為adj(lM)。為得到相應(yīng)的Renyik-treeRk，Q中的節(jié)點(diǎn)應(yīng)該重新標(biāo)記為{n-k+1，n-k+2，…，n}。通過以下方法來定義重新標(biāo)記規(guī)則?：

1）如果qi是Q中的第i個(gè)最小節(jié)點(diǎn)，則分配?(qi)=n-k+i；

2）每個(gè)q?Q∪{n-k+1，n-k+2，…，n}，則指定?(q)=q；

3）未分配的值用閉環(huán)周期重新標(biāo)記，形式上表示為：對于每個(gè)q∈{n-k+1，n-k+2，…，n}-Q，?(q)=i使得?j(i)=i并且j被最大化。

例4 以下用一個(gè)實(shí)例來演示上述由k-treeTk轉(zhuǎn)換成有根的Renyik-treeRk的實(shí)現(xiàn)步驟，以圖2 所示的3-tree 為例，圖2 中Q={1，2，3}取為lM=12 的鄰域。正向箭頭對應(yīng)于規(guī)則1）分配的值，小的循環(huán)是規(guī)則2）派生的循環(huán)，而向后箭頭的閉合循環(huán)是根據(jù)規(guī)則3）。

圖4（a）重新獲得的Renyi 3-treeR3。通過? 方法重新標(biāo)記后R3的根是{10，11，12}。

圖4 3-tree的重新標(biāo)記規(guī)則Fig.4 3-tree relabeling rules

3.2.2 生成Ranyik-treeRk的特征樹T

在此步驟中，通過過渡骨架的方法生成Rk對應(yīng)的特征樹T，但為了保證線性時(shí)間復(fù)雜度，避免骨架的顯式構(gòu)造，且分別構(gòu)建了T的節(jié)點(diǎn)集和邊集。計(jì)算節(jié)點(diǎn)集以標(biāo)識Rk中的所有最大團(tuán)，此過程可以通過從k葉節(jié)點(diǎn)修剪Rk來完成。接而將v從Rk中刪除，因此將其每個(gè)相鄰節(jié)點(diǎn)的度數(shù)減1。將v的鄰接表的這個(gè)子集存儲為Kv，邊緣集由標(biāo)識父級的向量p表示。0是所有節(jié)點(diǎn)父節(jié)點(diǎn)。

例5 以下用一個(gè)實(shí)例來演示上述根據(jù)已知的Renyik-treeRk生成特征樹T的實(shí)現(xiàn)步驟，以圖3（a）所示的3-tree 為例，圖3（c）就是其對應(yīng)的特征樹。為了實(shí)現(xiàn)此步驟，算法仍然需要標(biāo)記每個(gè)邊(v，p(v))。當(dāng)p(v)=0 時(shí)，當(dāng)前邊標(biāo)記為ε；邊l(v，p(v))由中不屬于Kv的唯一元素的序來索引。

3.2.3 應(yīng)用與參數(shù)結(jié)合的Dandelion編碼

在這一步驟中，應(yīng)用參數(shù)r=0 且x=?(q) 的廣義Dandelion 編碼，其中q=min{v?Q}，編譯得到的編碼串S由n-k-1 對組成。對于每個(gè)v∈{1，2，…，n-k}都有一對(p(v)，l(v，p(v)))取自Akn。在運(yùn)算中，與?(lM)相關(guān)的對必須為(0，ε)，且此代碼對可以省略［24］。

例6 使用參數(shù)r=0 和x=1 從圖3（c）的特征樹獲得的Dandelion 編碼串為：[(0，ε)，(0，ε)，(6，1)，(5，3)，(5，2)，(7，1)，(8，2)，(1，3)] ∈R312，在圖2 中所示的3-treeT3相對應(yīng)的Dandelion 編碼為 [(1，2，3)(6，1)，(5，3)，(5，2)，(7，1)，(8，2)，

3.3 Dandelion編碼與樹之間的解碼實(shí)現(xiàn)

Dandelion編碼與k-tree之間的解碼過程分4個(gè)步驟：

1）從Q開始計(jì)算?并找到lM和-q；

2）在骨架S(Rk)中插入與?(lM)相關(guān)的對(0，ε)并對其進(jìn)行解碼以獲得T；

3）通過遍歷k-treeT重新獲得Rk；將Rk初始化為{n-k+1，n-k+2，…，n}上的k團(tuán)R；

4）應(yīng)用?-1方法從Rk獲得Tk。

在實(shí)現(xiàn)過程中，一旦已知Q根集合，就可以如編碼算法一樣計(jì)算q=min{v∈[1，n]：v?Q}和?；由于T的所有節(jié)點(diǎn)都出現(xiàn)在骨架中，因此通過簡單掃描骨架即可較容易得出T的所有葉子的集合L。在此，T中的葉子與Rk中的k-leaf 重合。將?-1應(yīng)用于節(jié)點(diǎn)集合L中的所有節(jié)點(diǎn)，就可以重構(gòu)原始Tk的有k-leaf點(diǎn)的集合，從而找到lM，即Tk中度為k的最大標(biāo)簽節(jié)點(diǎn)。

例7 以下用一個(gè)實(shí)例來演示解碼過程。以圖3（c）的Dandelion code 為例：已知Dandelion code 是以下序列：[(0，ε)，(0，ε)，(6，1)，(5，3)，(5，2)，(7，1)，(8，2)，(1，3)]按照解碼步驟第1）步可以計(jì)算出Q={1，2，3}，lM=12 且qˉ=4；第2）步在現(xiàn)有的特征樹上添加一條邊即節(jié)點(diǎn)4 到節(jié)點(diǎn)0 的邊標(biāo)記為ε，即得到圖3（b）所示的骨架；第3）步通過掃描骨架找到原始Tk的所有葉子節(jié)點(diǎn)L={11，12，4，9}，根據(jù)圖示可知Tk的所有葉子節(jié)點(diǎn)與Rk的所有葉子節(jié)點(diǎn)相同，接著對每一個(gè)葉子節(jié)點(diǎn)進(jìn)行?-1運(yùn)算，找到原始Tk中所有k-leaf，從而得到圖3（a）所示的Tk；第4）步根據(jù)得到的Tk重建Rk，最終得到圖2 所示的原始Rk。

定理2Dandelion 編碼與樹之間編碼算法的時(shí)間復(fù)雜度為O(nk)，其中n為節(jié)點(diǎn)個(gè)數(shù)，k為圖結(jié)構(gòu)樹寬。

證明 可以通過掃描Tk的所有鄰接表來實(shí)現(xiàn)每個(gè)節(jié)點(diǎn)v的d(v)的計(jì)算。由于具有n個(gè)節(jié)點(diǎn)的k-tree 具有k(n-k)條邊，故算法的時(shí)間復(fù)雜度與輸入樹寬k的大小呈線性關(guān)系。通過例子可以發(fā)現(xiàn)，步驟1的總時(shí)間復(fù)雜度為O(nk)。

4 隨機(jī)生成有界樹寬CP-nets算法的設(shè)計(jì)

4.1 基本算法

4.1.1k-tree到Dandelion編碼的映射算法

算法1 Encoding Algorithm。

輸入 一個(gè)有n個(gè)節(jié)點(diǎn)的k-treeTk；

輸出 相應(yīng)Akn的編碼。

1）定義集合Q，將k-treeTk轉(zhuǎn)換成有根Renyik-treeRk；

2）為Rk生成特征樹T

3）計(jì)算r=0和x=的T的代碼對。

在此過程中，當(dāng)v被刪除時(shí)，其相鄰節(jié)點(diǎn)中的最多一個(gè)成為k-leaf。如果發(fā)生這種情況，修剪過程將在鄰接列表掃描中選擇新的k-leaf和下一個(gè)k-leaf之間的最小值。在此過程結(jié)束時(shí)，得到的Renyik-treeRk其根為R={n-k+1，n-k+2，…，n}。該算法的總體時(shí)間復(fù)雜度為O(nk)。在實(shí)現(xiàn)過程中，算法刪除了n-k個(gè)節(jié)點(diǎn)，每次刪除都需要O(k)時(shí)間。

4.1.2 生成k-tree算法

本算法功能 可以對任意一對(Q，S)∈Akn進(jìn)行解碼以獲得代碼為(Q，S)的k-tree。使用以下算法執(zhí)行過程。

算法2 Decoding Algorithm。

輸出 生成相應(yīng)的k-treeTk。

1）從Q開始計(jì)算?并找到lM和

2）在S中插入與?(lM)相對應(yīng)的對(0，ε)并對其進(jìn)行解碼以獲得T；

3）通過遍歷k-treeT重新構(gòu)建Rk；將Rk初始化為{n-k+1，n-k+2，…，n}上的R；

4）應(yīng)用?-1方法從Rk獲得Tk

從編碼串中刪除冗余對完成了步驟3）。由于可以在線性時(shí)間內(nèi)計(jì)算出Dandelion 編碼，因此編碼算法的總體時(shí)間復(fù)雜度為O(nk)。為了對骨架進(jìn)行解碼，需要添加與?(lM)對應(yīng)的一對(0，ε)，所獲得的樹T由其父向量表示。解碼過程的最后一步在于用?-1將得到的有根Rk轉(zhuǎn)換為無根的Tk。解碼算法的總體復(fù)雜度為O(nk)。

4.1.3 生成有界樹寬CP-nets算法

具有完整語義的CP-nets由兩部分組成：DAG結(jié)構(gòu)與表示語義的條件偏好表。

在本文中，利用迭代方法生成相應(yīng)的CPT。在本文中CPT 的生成可借助帶有離散多值函數(shù)的雙射（一個(gè)一對一的映射）來實(shí)現(xiàn)。此函數(shù)可以將每個(gè)CPT(Xi)建模為函數(shù)其中d=2 是指變量的域大小，m=|Pa(Xi)|指各個(gè)節(jié)點(diǎn)其父節(jié)點(diǎn)的個(gè)數(shù)。

針對于二值的變量，函數(shù)f是一個(gè)布爾函數(shù)。在布爾值的情況下，每個(gè)父節(jié)點(diǎn)Xh的值Xh1和Xh2可以分別映射到0和1。兩個(gè)可能的線性階數(shù)可以對應(yīng)于輸出0和1。所以，可以將任何CPT編碼成長度為dm的等效函數(shù)向量F（CPT code），可以使用表1 中的真值表對例1 中節(jié)點(diǎn)B的CPT進(jìn)行建模。

表1 CPT取值與對應(yīng)的布爾函數(shù)值Tab.1 CPT values and corresponding Boolean function values

根據(jù)建模得到CPT 編碼序列，由CPT 編碼隨機(jī)生成各個(gè)節(jié)點(diǎn)的CPT。

以下的生成算法分為兩步：第一步，由算法2 提到的解碼算法得到Dandelion 編碼相應(yīng)的k-tree，并以此得到對應(yīng)的特征樹T，特征樹便是相應(yīng)有界樹寬CP-nets 的DAG 結(jié)構(gòu)；第二步，由隨機(jī)的CPT 編碼生成各個(gè)節(jié)點(diǎn)的條件偏好表。最終結(jié)構(gòu)與CPT一一對應(yīng)，以矩陣的形式存儲。

算法3 BTW-CP-nets Gen。

輸出 生成相應(yīng)樹寬為k的CP-netsNk。

1）調(diào)用算法2生成Dandelion編碼所對應(yīng)的k-tree的特征樹T；

Fj=的隨機(jī)函數(shù)輸入

由F0構(gòu)造CPT（Xi）；

ReturnNk

例7 以下利用該算法生成圖2所示3-tree所對應(yīng)的樹寬為3 的CP-nets，由于特征樹T已經(jīng)提供相應(yīng)的DAG 結(jié)構(gòu)，故CP-nets的生成如圖5所示。

圖5 對應(yīng)于圖3所生成樹寬為3的CP-netsFig.5 CP-nets with tree width of 3 corresponding to Fig.3

4.2 算法的性能尺度

1）計(jì)算時(shí)間。算法的時(shí)間消耗主要有兩方面：一個(gè)是對隨機(jī)k-tree 模型的生成，即求隨機(jī)編碼與結(jié)構(gòu)特征，復(fù)雜度為O(nk)，第二個(gè)對所生成k-tree圖結(jié)構(gòu)的存儲與推理，它需要消耗O(nk)，因此整個(gè)算法實(shí)現(xiàn)的時(shí)間復(fù)雜度為線性時(shí)間O(nk)。

2）存儲空間。隨機(jī)生成算法的空間復(fù)雜度為：O(k(n-k))，k是CP-nets 圖結(jié)構(gòu)的樹寬，n是CP-nets 圖結(jié)構(gòu)的頂點(diǎn)數(shù)。相對于其他算法，該算法不用存儲原始數(shù)據(jù)，節(jié)省了很多空間。

5 算法的實(shí)驗(yàn)分析

在本章中，通過實(shí)驗(yàn)顯示BTW-CP-nets Gen 算法的準(zhǔn)確性與性能。進(jìn)行了多次實(shí)驗(yàn)，通過測驗(yàn)6 個(gè)不同的數(shù)據(jù)集得出最終結(jié)論。實(shí)驗(yàn)分為4個(gè)部分。

1）首先證明了編碼與解碼算法的有效性，通過建立編碼與k-tree 與有界樹寬CP-nets 的關(guān)系，完成編碼與圖結(jié)構(gòu)之間的雙向映射。參照6 個(gè)數(shù)據(jù)集數(shù)據(jù)生成有界樹寬的CP-nets，并測試其質(zhì)量。

2）其次，把已有的生成算法與BTW-CP-nets Gen 算法進(jìn)行了對比，在算法性能方面（運(yùn)行時(shí)間、遍歷節(jié)點(diǎn)與樹寬質(zhì)量評分）進(jìn)行比較，結(jié)果如圖6～8所示。

3）再者，研究占優(yōu)查詢算法在不同生成算法所生成的圖模型上的運(yùn)行時(shí)間，準(zhǔn)確性與樹寬之間的權(quán)衡，如圖9所示。

4）最后，根據(jù)樹寬評分與占優(yōu)查詢節(jié)點(diǎn)遍歷比的相關(guān)系數(shù)的變化分析CP-nets 結(jié)構(gòu)與推理算法對參數(shù)的依賴。證明樹寬影響推理算法的運(yùn)行效率與難度，實(shí)驗(yàn)數(shù)據(jù)如圖10所示。

5.1 樹寬質(zhì)量評分

給定一個(gè)k-tree，定義樹寬質(zhì)量評分（T-score）來評估k-tree生成CP-nets 的質(zhì)量；T-score值越大，證明所生成的有界樹寬CP-nets質(zhì)量越高。k-treeTk的T-score定義為：

在分子上，Smi(Tk)指通過使用k-tree表示數(shù)據(jù)來衡量廢棄了多少冗余結(jié)構(gòu)。令eij表示連接節(jié)點(diǎn)i和j的邊，并讓Sij表示節(jié)點(diǎn)i和j的結(jié)構(gòu)信息。從而：

Smi(Tk)是k-tree 和有界樹寬CP-nets 一致性的度量，可以解釋為k-tree覆蓋的結(jié)構(gòu)信息的總和，也可以解釋為全結(jié)構(gòu)的CP-nets剪枝k-tree結(jié)構(gòu)的總和。

在分母上，將Sl(Tk)定義為k-tree 的最佳子圖的評分。其中m(G)是每個(gè)DAG 結(jié)構(gòu)G的導(dǎo)出圖，其同為k-tree的子圖，Si(Xpai)指給定父節(jié)點(diǎn)數(shù)量總和。

可針對任何給定的k-tree非常有效地評估T-score，因?yàn)橛?jì)算Smi(Tk)只需要各節(jié)點(diǎn)的結(jié)構(gòu)信息（它們都可以預(yù)先計(jì)算，因此時(shí)間復(fù)雜度最多為O(n2)）。

5.2 占優(yōu)查詢節(jié)點(diǎn)遍歷比

給定一個(gè)CP-netsN，在此結(jié)構(gòu)上進(jìn)行占優(yōu)查詢時(shí)，若配置o與o′的取值一定，算法過程中所遍歷到的節(jié)點(diǎn)數(shù)是一定的。若判定結(jié)果相同，遍歷越多節(jié)點(diǎn)則代表此結(jié)構(gòu)的占優(yōu)查詢算法效率越高。因此，在本文中定義節(jié)點(diǎn)遍歷比N-trave來判定不同結(jié)構(gòu)上占優(yōu)查詢的效率。N-trave定義如下：

其中：分子上nt(N)代表算法運(yùn)行中所遍歷到的節(jié)點(diǎn)，分母上n(N)代表全結(jié)構(gòu)CP-nets 中的所有節(jié)點(diǎn)。在實(shí)驗(yàn)中，比較了T-score與N-trave的相關(guān)系數(shù)，以此相關(guān)系數(shù)來判定k-tree所生成的有界樹寬CP-nets與占優(yōu)查詢效率之間的關(guān)系。

5.3 實(shí)驗(yàn)環(huán)境

本文實(shí)驗(yàn)是在一臺計(jì)算機(jī)上進(jìn)行的，計(jì)算機(jī)操作系統(tǒng)是Windows7 32 bit，配有8 GB 內(nèi)存，主頻為3.2 GHz 的Intel Core i5-3470 CPU。使用的軟件是Matlab，每個(gè)實(shí)驗(yàn)重復(fù)5 次，取5次實(shí)驗(yàn)的平均值作為最后的結(jié)果。

5.4 實(shí)驗(yàn)分析

在本節(jié)中，衡量k-tree產(chǎn)生有界樹寬CP-nets結(jié)構(gòu)的質(zhì)量，為了保證實(shí)驗(yàn)結(jié)果的準(zhǔn)確性及說服力，實(shí)驗(yàn)使用了6 個(gè)不同類型的數(shù)據(jù)集進(jìn)行測試，每個(gè)數(shù)據(jù)集的樣本數(shù)與樣本量如表2 所示。每個(gè)數(shù)據(jù)集中非二元變量在中位數(shù)上二值化，丟棄缺少變量值的實(shí)例。假設(shè)在以下所有實(shí)驗(yàn)中，產(chǎn)生的CP-nets是二值的。

在算法對比方面，本文選擇了文獻(xiàn)［25］在1998 年提出的用于生成隨機(jī)標(biāo)記樹的并行算法（簡稱PHC 算法），此算法基于Cayley 公式的證明，該算法早先用于從n-2個(gè)元素序列生成n個(gè)節(jié)點(diǎn)的標(biāo)記樹。是一種修改了用于樹生成的原始順序算法；在2005年，文獻(xiàn)［26］提出了一種針對k樹的新編碼方案（簡稱Pruffer code 算法），不需要計(jì)算轉(zhuǎn)換結(jié)構(gòu)。實(shí)驗(yàn)分別在算法運(yùn)行時(shí)間、節(jié)點(diǎn)遍歷比與樹寬評分等方面比較了3 種算法的性能。

表2 實(shí)驗(yàn)中使用的數(shù)據(jù)集的大小Tab.2 Size of the datasets used in the experiment

首先本文通過3 種算法分別生成相同結(jié)構(gòu)難度的CPnets，針對不同的節(jié)點(diǎn)數(shù)n與樹寬的算法運(yùn)行時(shí)間如圖6 所示。當(dāng)生成結(jié)構(gòu)較小的圖模型時(shí)，例如n=10，k=3，3種生成算法的運(yùn)行時(shí)間相差無幾；但當(dāng)k＞5 時(shí)，其時(shí)間差距逐漸明朗，例如當(dāng)n=10，k=10 時(shí)，Pruffer code 生成算法花費(fèi)4.29 ms，PHC 生成算法花費(fèi)3.07 ms，BTW-CP-nets Gen 算法花費(fèi)2.16 ms。這說明BTW-CP-nets Gen 算法在生成圖模型時(shí)相較于其他兩個(gè)算法時(shí)間較快，效率更高。除此之外本文所提出的生成方法的運(yùn)行時(shí)間與樹寬之間存在更強(qiáng)的線性正相關(guān)。

圖6 不同生成算法的運(yùn)行時(shí)間Fig.6 Running time of different generation algorithms

圖7 表示的是隨著CP-nets 樹寬逐漸增加，不同的生成算法生成有界樹寬的CP-nets 的質(zhì)量變化趨勢。由圖7 可以看出，隨樹寬k值增加，所生成的CP-nets 質(zhì)量提高。當(dāng)節(jié)點(diǎn)數(shù)n=10，k=8 時(shí)，Pruffer code 生成算法的T-score=0.315，PHC生成算法T-score=0.356，BTW-CP-nets Gen 算法的T-score=0.386。3 種算法的樹寬質(zhì)量分?jǐn)?shù)較相近，當(dāng)k取較小值時(shí)，3種算法所生成的圖模型質(zhì)量相似。然而，當(dāng)n=10，k=20時(shí)，其樹寬質(zhì)量分?jǐn)?shù)分別是0.585，0.719，0.921。其中BTW-CPnets Gen 算法的T-score最大，這說明生成結(jié)構(gòu)較大的圖結(jié)構(gòu)時(shí)，通過BTW-CP-nets Gen 算法生成的有界樹寬CP-nets 質(zhì)量更好，結(jié)構(gòu)更加均勻。

實(shí)驗(yàn)基于Dandelion code 生成有界樹寬的CP-nets 圖模型，并對存儲在數(shù)據(jù)庫中的圖模型進(jìn)行推理。在實(shí)驗(yàn)中，首先引用了文獻(xiàn)［27］提出的DFS（Dominance testing via model FlipS checking）占優(yōu)查詢算法［27］，此算法是一種基于動態(tài)規(guī)劃的占優(yōu)查詢算法，深度遍歷優(yōu)先。由于該算法的復(fù)雜性，它只適用于一些結(jié)構(gòu)較小的數(shù)據(jù)集，因此在進(jìn)行實(shí)驗(yàn)時(shí)規(guī)定所使用的CP-nets 樹寬小于20 且父節(jié)點(diǎn)的最大數(shù)目為20。在實(shí)驗(yàn)中，本實(shí)驗(yàn)分別對3 種算法生成的圖模型進(jìn)行了占優(yōu)查詢，其節(jié)點(diǎn)遍歷比如圖8 所示，當(dāng)節(jié)點(diǎn)數(shù)n=20 時(shí)，Pruffer code 生成算法的N-trave=0.598，PHC 生成算法的N-trave=0.719，BTWCP-nets Gen 算法的N-trave=0.927。由此可見，在結(jié)構(gòu)復(fù)雜的圖模型上進(jìn)行占優(yōu)查詢時(shí)，BTW-CP-nets Gen算法的節(jié)點(diǎn)遍歷比要大于其他兩種算法，這代表著BTW-CP-netsGen 生成的圖模型更加均勻，使得占優(yōu)查詢算法效率更高。

圖7 不同算法的樹寬質(zhì)量評分變化情況Fig.7 Changing trend of tree width quality score for different algorithms

圖8 不同生成算法生成圖模型的節(jié)點(diǎn)遍歷比Fig.8 Node traversal ratio of graph models generated by different generation algorithms

本文引用了DFS占優(yōu)查詢算法［27］對不同生成算法生成的有界樹寬CP-nets進(jìn)行占優(yōu)查詢，并記錄了該算法相應(yīng)的運(yùn)行時(shí)間，實(shí)驗(yàn)結(jié)果如圖9 所示，根據(jù)圖9 可知：整體分析，當(dāng)樹寬n=20不變時(shí)，占優(yōu)查詢DFS算法的運(yùn)行時(shí)間隨著樹寬k的增加而增加，這說明圖模型的樹寬影響其占優(yōu)查詢的運(yùn)行時(shí)間。當(dāng)k取得最大值k=20時(shí)，DFS算法在Pruffer code生成算法所生成的圖模型的運(yùn)行時(shí)間為4.95× 103ms，在PHC 生成算法所生成的圖模型的運(yùn)行時(shí)間為3.97× 103ms，在BTW-CP-nets Gen生成算法所生成的圖模型的運(yùn)行時(shí)間為1.98× 103ms，分別比前者減少了2.97× 103ms 與1.99 × 103ms，這代表著BTW-CP-nets Gen生成算法所生成的圖模型結(jié)構(gòu)更加均勻，使得DFS算法效率更高。

圖9 DFS算法的運(yùn)行時(shí)間Fig.9 Running time of DFS algorithm

在實(shí)驗(yàn)最后一部分，本文比較了不同數(shù)據(jù)集上T-score與N-trave的相關(guān)系數(shù)。T-score代表的是k-tree生成有界樹寬CPnets 的質(zhì)量，故其值越大則質(zhì)量越高；N-trave代表的是推理算法在某給定的圖結(jié)構(gòu)上進(jìn)行推理計(jì)算時(shí)所遍歷到的節(jié)點(diǎn)比，其取值越大則推理算法效率越高；T-score與N-trave的相關(guān)系數(shù)用來判定k-tree所生成的有界樹寬CP-nets與占優(yōu)查詢效率之間的關(guān)系。圖10是在audio與adult數(shù)據(jù)集上相關(guān)系數(shù)的圖示，表3 是在不同數(shù)據(jù)集上相關(guān)系數(shù)的值，由圖10 與表3 可發(fā)現(xiàn)，當(dāng)樣本數(shù)增大時(shí)，相關(guān)系數(shù)的值也逐漸增加，當(dāng)樣本量足夠大時(shí)，可將相關(guān)系數(shù)近似擬合為1，這代表著樹寬質(zhì)量評分近似100%影響占優(yōu)查詢的節(jié)點(diǎn)遍歷比。由此可得出結(jié)論，CP-nets的樹寬嚴(yán)重影響占優(yōu)查詢算法的效率與難度。

圖10 不同數(shù)據(jù)集上k-tree的T-score與N-trave的關(guān)系Fig.10 Relationship between T-score and N-trave of k-trees on different datasets

就所花費(fèi)的時(shí)間與遍歷節(jié)點(diǎn)而言，占優(yōu)查詢算法的性能隨圖模型的樹寬結(jié)構(gòu)而變化，且占優(yōu)查詢算法過程因圖結(jié)構(gòu)復(fù)雜而復(fù)雜。在多值情況下，對于較小的樹寬的CP-nets，占優(yōu)查詢算法可以更加高效運(yùn)行［28］。

6 結(jié)語

本文提出了一種標(biāo)記k-tree雙射碼，并在理論上證明了該編碼與解碼算法的運(yùn)行時(shí)間與所輸入的樹寬大小呈線性關(guān)系。在本文中為了開發(fā)k-tree 的雙射編碼，利用到了Renyik-tree 與無根k-tree 的轉(zhuǎn)換，并基于Dandelion 編碼的泛化開發(fā)了標(biāo)記Ranyik-tree 的新編碼。提出了線性時(shí)間算法BTWCP-nets Gen 算法，解決了對k-tree 進(jìn)行有效編碼和解碼的問題。經(jīng)多次實(shí)驗(yàn)得出結(jié)論：

1）BTW-CP-nets Gen 算法在生成有界樹寬方面有較高的效率，且所生成的圖模型結(jié)構(gòu)更加均勻。

2）用DFS 占優(yōu)查詢算法在不同樹寬的CP-nets 上進(jìn)行實(shí)驗(yàn)，驗(yàn)證了CP-net是的樹寬嚴(yán)重影響占優(yōu)查詢的難度。

3）BTW-CP-nets Gen算法雖然能在線性時(shí)間內(nèi)完成生成，但其運(yùn)行時(shí)間仍然依賴于圖模型的結(jié)構(gòu)。

本文中的結(jié)論證實(shí)了樹寬因素并且可擴(kuò)展到更一般的CP-nets，例如具有異構(gòu)域或不完整表的循環(huán)的CP-nets。

在未來的工作中將繼續(xù)探索各種推理算法（次優(yōu)查詢、一致性查詢等）和CP-nets結(jié)構(gòu)之間的關(guān)系：

1）圖模型的表示方面，仍然需要針對具體問題設(shè)計(jì)生成特定的圖模型。在設(shè)計(jì)中既要對所生成圖模型變量的依賴關(guān)系做出合理抽象，又要權(quán)衡所生成圖模型在進(jìn)行推理或?qū)W習(xí)所面臨的難度與代價(jià)，下一步將改進(jìn)生成算法的局限性，面對不同需求生成特殊結(jié)構(gòu)的圖模型［29］。

2）圖模型推理算法方面進(jìn)一步研究提高其效率，包括利用分布式推理［30］、針對查詢的推理、啟發(fā)式推理等。各個(gè)推理算法在圖模型研究效率方面還有很大的改善空間。接下來研究一種啟發(fā)式推理算法，根據(jù)評分函數(shù)的值簡化推理步驟提高其推理效率。