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

李叢叢，劉驚雷

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

0 引言

條件偏好網絡（Conditional Preference networks，CP-nets）是常見的圖模型之一，它以一種緊湊簡潔的方式有效地表示了復雜的多元域中隨機變量的條件偏好。該網絡由兩部分組成：編碼生成了模型中變量間依賴或獨立關系的有向無環圖（Directed Acyclic Graph，DAG）以及能夠重構條件偏好的條件偏好表（Conditional Preference Table，CPT）。隨著模型中變量數的增多，從數據中對CP-nets網絡的推理學習是NP-hard。

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

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

本文有如下的特點和貢獻：

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

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

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

1 相關工作

近年來，有界樹寬圖模型的生成已受到國內外眾多領域研究者們的關注。標記樹的編碼問題在文獻中得到了廣泛的研究。

CP-nets首先由Boutilier等［4］在2004年提出。他們利用條件性的其他條件不變的偏好規則，以實現偏好關系的緊湊表示。近年來，在國內，研究者們大多數都通過圖來表示隨機變量間的依賴關系，為多變量統計建模提供了有力的表示框架［5］。圖模型理論的基礎是問題域中不同屬性集之間的條件獨立性與結構的多樣性其中結構的多樣性［6］，可根據標記編碼生成［7］。Robinson［7］研究了標記和未標記的DAG計數問題，推導了生成DAG結構的編碼中的遞歸式。

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

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

2 關于圖模型的基本符號與定義

2.1 條件偏好圖CP-nets

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

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

例1 某人一天飲品搭配主要考慮咖啡、茶和牛奶，分別用A、B、C表示，其中早上的咖啡種類與中午的茶種類決定晚上的牛奶種類。對于早上的咖啡，他喜歡黑咖啡勝過白咖啡。對于中午的茶，他喜歡紅茶勝過綠茶。對于晚上的牛奶，若白天選了黑咖啡紅茶或白咖啡綠茶，則選純牛奶而不是酸牛奶；其他情況，則選酸牛奶而不是純牛奶。該實例的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結構示意圖Fig.1 Schematic diagram of CP-nets in example 1

2.2 有界樹寬的CP-nets

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

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

直接計算圖的樹寬是一個棘手的問題。實施樹寬約束的一種方法是使用k-tree。所以在本文中，利用隨機生成k-tree來實現有界樹寬CP-nets的生成。

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

1）一個（k+1）的團是一個k-tree。

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

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

在k-tree 中，入度為k的節點稱為k-leaf。每個k-leaf 的鄰域形成一個團，然后k-leaf是單純節點。

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

例2 Dandelion 編碼的一個例子是：12 個節點的3-tree（n=12，k=3）的Q=［1，2，3］，S=此編碼所對應的k-tree如圖2所示。

圖2 例2中的3-tree結構Fig.2 3-tree structure in example 2

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

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

3.1 特征樹

在本節著重介紹有根k-tree 的特征樹，是k-tree 與有界樹寬CP-nets 的中間變量，因為將在編碼過程中使用有根的ktree（即Renyik-tree）的特征樹。首先本節先介紹一個有根的k-tree的骨架。

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

定義6通過標記S(Tk，R)的節點和邊，得到根為R的ktreeTk(Tk′，R)的特征樹T(Tk，R)：

1）根節點R標記為0，各節點{v}∪K標記為v；

2）從節點{v}∪K到它的父節點{v′}∪K的每條都用K′中沒有出現的節點（一個有序集）的索引標記。當某節點的父節點為R時，其索引邊用ε標記。

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

例3 在圖3 舉例顯示了一棵有12 個節點的Ranyi 3-tree、它的骨架和特征樹。

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

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

3.2 Dandelion編碼與樹之間的編碼實現

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

編碼得到的代碼是雙射的：可通過解碼過程證明，此解碼過程能夠將中的每個代碼與相應的k-tree 相關聯，并且其基數關系如下：|Akn|=|Tkn|。由k-tree 到Dandelion 編碼的編碼算法可分為以下步驟。

3.2.1 將k-treeTk轉換成有根的Renyik-treeRk

計算每個節點v的度d(v)并找到lM，即度為k的最大節點v，則節點集Q為adj(lM)。為得到相應的Renyik-treeRk，Q中的節點應該重新標記為{n-k+1，n-k+2，…，n}。通過以下方法來定義重新標記規則?：

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

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

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

例4 以下用一個實例來演示上述由k-treeTk轉換成有根的Renyik-treeRk的實現步驟，以圖2 所示的3-tree 為例，圖2 中Q={1，2，3}取為lM=12 的鄰域。正向箭頭對應于規則1）分配的值，小的循環是規則2）派生的循環，而向后箭頭的閉合循環是根據規則3）。

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

圖4 3-tree的重新標記規則Fig.4 3-tree relabeling rules

3.2.2 生成Ranyik-treeRk的特征樹T

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

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

3.2.3 應用與參數結合的Dandelion編碼

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

例6 使用參數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相對應的Dandelion 編碼為 [(1，2，3)(6，1)，(5，3)，(5，2)，(7，1)，(8，2)，

3.3 Dandelion編碼與樹之間的解碼實現

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

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

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

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

4）應用?-1方法從Rk獲得Tk。

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

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

定理2Dandelion 編碼與樹之間編碼算法的時間復雜度為O(nk)，其中n為節點個數，k為圖結構樹寬。

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

4 隨機生成有界樹寬CP-nets算法的設計

4.1 基本算法

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

算法1 Encoding Algorithm。

輸入 一個有n個節點的k-treeTk；

輸出 相應Akn的編碼。

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

2）為Rk生成特征樹T

3）計算r=0和x=的T的代碼對。

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

4.1.2 生成k-tree算法

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

算法2 Decoding Algorithm。

輸出 生成相應的k-treeTk。

1）從Q開始計算?并找到lM和

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

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

4）應用?-1方法從Rk獲得Tk

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

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

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

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

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

表1 CPT取值與對應的布爾函數值Tab.1 CPT values and corresponding Boolean function values

根據建模得到CPT 編碼序列，由CPT 編碼隨機生成各個節點的CPT。

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

算法3 BTW-CP-nets Gen。

輸出 生成相應樹寬為k的CP-netsNk。

1）調用算法2生成Dandelion編碼所對應的k-tree的特征樹T；

Fj=的隨機函數輸入

由F0構造CPT（Xi）；

ReturnNk

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

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

4.2 算法的性能尺度

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

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

5 算法的實驗分析

在本章中，通過實驗顯示BTW-CP-nets Gen 算法的準確性與性能。進行了多次實驗，通過測驗6 個不同的數據集得出最終結論。實驗分為4個部分。

1）首先證明了編碼與解碼算法的有效性，通過建立編碼與k-tree 與有界樹寬CP-nets 的關系，完成編碼與圖結構之間的雙向映射。參照6 個數據集數據生成有界樹寬的CP-nets，并測試其質量。

2）其次，把已有的生成算法與BTW-CP-nets Gen 算法進行了對比，在算法性能方面（運行時間、遍歷節點與樹寬質量評分）進行比較，結果如圖6～8所示。

3）再者，研究占優查詢算法在不同生成算法所生成的圖模型上的運行時間，準確性與樹寬之間的權衡，如圖9所示。

4）最后，根據樹寬評分與占優查詢節點遍歷比的相關系數的變化分析CP-nets 結構與推理算法對參數的依賴。證明樹寬影響推理算法的運行效率與難度，實驗數據如圖10所示。

5.1 樹寬質量評分

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

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

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

在分母上，將Sl(Tk)定義為k-tree 的最佳子圖的評分。其中m(G)是每個DAG 結構G的導出圖，其同為k-tree的子圖，Si(Xpai)指給定父節點數量總和。

可針對任何給定的k-tree非常有效地評估T-score，因為計算Smi(Tk)只需要各節點的結構信息（它們都可以預先計算，因此時間復雜度最多為O(n2)）。

5.2 占優查詢節點遍歷比

給定一個CP-netsN，在此結構上進行占優查詢時，若配置o與o′的取值一定，算法過程中所遍歷到的節點數是一定的。若判定結果相同，遍歷越多節點則代表此結構的占優查詢算法效率越高。因此，在本文中定義節點遍歷比N-trave來判定不同結構上占優查詢的效率。N-trave定義如下：

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

5.3 實驗環境

本文實驗是在一臺計算機上進行的，計算機操作系統是Windows7 32 bit，配有8 GB 內存，主頻為3.2 GHz 的Intel Core i5-3470 CPU。使用的軟件是Matlab，每個實驗重復5 次，取5次實驗的平均值作為最后的結果。

5.4 實驗分析

在本節中，衡量k-tree產生有界樹寬CP-nets結構的質量，為了保證實驗結果的準確性及說服力，實驗使用了6 個不同類型的數據集進行測試，每個數據集的樣本數與樣本量如表2 所示。每個數據集中非二元變量在中位數上二值化，丟棄缺少變量值的實例。假設在以下所有實驗中，產生的CP-nets是二值的。

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

表2 實驗中使用的數據集的大小Tab.2 Size of the datasets used in the experiment

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

圖6 不同生成算法的運行時間Fig.6 Running time of different generation algorithms

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

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

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

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

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

圖9 DFS算法的運行時間Fig.9 Running time of DFS algorithm

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

圖10 不同數據集上k-tree的T-score與N-trave的關系Fig.10 Relationship between T-score and N-trave of k-trees on different datasets

就所花費的時間與遍歷節點而言，占優查詢算法的性能隨圖模型的樹寬結構而變化，且占優查詢算法過程因圖結構復雜而復雜。在多值情況下，對于較小的樹寬的CP-nets，占優查詢算法可以更加高效運行［28］。

6 結語

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

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

2）用DFS 占優查詢算法在不同樹寬的CP-nets 上進行實驗，驗證了CP-net是的樹寬嚴重影響占優查詢的難度。

3）BTW-CP-nets Gen算法雖然能在線性時間內完成生成，但其運行時間仍然依賴于圖模型的結構。

本文中的結論證實了樹寬因素并且可擴展到更一般的CP-nets，例如具有異構域或不完整表的循環的CP-nets。

在未來的工作中將繼續探索各種推理算法（次優查詢、一致性查詢等）和CP-nets結構之間的關系：

1）圖模型的表示方面，仍然需要針對具體問題設計生成特定的圖模型。在設計中既要對所生成圖模型變量的依賴關系做出合理抽象，又要權衡所生成圖模型在進行推理或學習所面臨的難度與代價，下一步將改進生成算法的局限性，面對不同需求生成特殊結構的圖模型［29］。

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