基于贝叶斯⁃遗传算法的多值无环CP⁃nets学习

图1 一种出行方式的CP⁃net

Fig.1 A CP⁃net of travel mode

其偏好网络结构 $G = 〈V, D E〉$ ， $V = \{T, W, O\}$ ，

D E = \{(W ⋃ O)| P a r e (W ⋃ O,

T) = 0.81\}

C P T = \{W_{f} ≻ W_{r} ≻ W_{w}, O_{c} ≻ O_{m},

W_{f} O_{m} : T_{c} ≻ T_{t} ≻ T_{w}, W_{f} O_{c} : T_{c} ≻ T_{w} ≻ T_{t},

W_{r} O_{m} : T_{c} ≻ T_{t} ≻ T_{w}, W_{r} O_{c} : T_{c} ≻ T_{t} ≻ T_{w},

W_{w} O_{c} : T_{t} ≻ T_{c} ≻ T_{w}, W_{w} O_{m} : T_{c} ≻ T_{w} ≻ T_{l}\}

2.2　贝叶斯方法

贝叶斯方法给出了先验概率和后验概率的概念，对给定样本在属性B_i $∈$ B的条件下，属性A取值为A_j的概率 $P (A_{j}| B_{i})$ 是先验概率.对于已确定的属性A取值A_j，其取值以B_i为条件的概率 $P (B_{i}| A_{j})$ 为后验概率.后验概率是基于先验概率的概率推算，根据贝叶斯方法可实现先验概率与后验概率的相互转换.具体公式为：

P (B_{i}| A_{j}) = \frac{P (B_{i}) P (A_{j}| B_{i})}{\overset{n}{∑_{i = 1}} P (B_{i}) P (A| B_{i})}

在条件偏好挖掘中，对于多属性下的条件偏好 $P (B_{i}| A_{j} C_{k})$ ，可得：

P (B_{i}| A_{j} C_{k}) = \frac{P (A_{j} C_{k}| B_{i}) × P (B_{i})}{\overset{n}{∑_{i = 1}} P (B_{i}) P (A_{j} C_{k}| B_{i})}

CP⁃nets中为了求出多父属性下的条件偏好概率，需多次扫描偏好数据库.本文通过构建单一父属性条件偏好概率数据库cell，存储单一父属性条件下的条件偏好 $P (C_{k}| B_{i})$ 与 $P (A_{j}| B_{i})$ ，参与多父属性求解，减少运算时间.

2.3　遗传算法

模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程计算模型称为遗传算法.随机产生种群大小为M的初代种群，借助自然遗传学的遗传算子进行组合、交叉和变异操作，产生代表新解集的种群，并以自然选择的方式逐代演化产生更优的近似解，每代根据问题域的个体适应度进行选择，在进化代数足够大时，遗传算法收敛于局部最优解.

本文通过遗传算法进行CP⁃nets结构学习，以结构评分函数fit(I)作为个体适应度参与遗传过程，并在遗传过程中加入交叉和变异操作，产生新CP⁃nets结构，逐渐演化更优解，直到最大进化代数完成CP⁃nets结构学习，可在有限时间内求得最优解.

3 多值无环CP⁃nets学习

3.1　多值属性下的偏好关系

多值无环CP⁃nets的学习中，以pr(u,c)作为条件偏好.偏好数据库中，偏好成对存在，即 $o (c_{1}, c_{2})$ ， $o (c_{3}, c_{4})$ 等.以选择排序的方式对偏好进行排序，得出偏好关系 $p r (u, c) = \{c_{1}, ⋯, c_{n}\}$ .

例如，存在属性集合 $V = \{X_{1} = A, X_{2} = B,$

$X_{3} = C, X_{4} = D, X_{5} = E\}$ ，A条件下属性D的偏好对如表1所示，则其相应的条件偏好关系如表2所示.

表1 A条件下属性D的偏好对

Table 1 Preference pairs of attribute D under A

Value of X₁	Value of X₂		Preference Pair
a₁	d₁	d₂	a₁d₁ $≻$ a₁d₂
a₁	d₁	d₃	a₁d₁ $≺$ a₁d₃
a₁	d₁	d₄	a₁d₁ $≺$ a₁d₄
a₁	d₂	d₃	a₁d₂ $≺$ a₁d₃
a₁	d₂	d₄	a₁d₂ $≺$ a₁d₄
a₁	d₃	d₄	a₁d₃ $≺$ a₁d₄
a₂	d₁	d₂	a₂d₁ $≺$ a₂d₂
a₂	d₁	d₃	a₂d₁ $≺$ a₂d₃
a₂	d₁	d₄	a₂d₁ $≺$ a₂d₄
a₂	d₂	d₃	a₂d₂ $≺$ a₂d₃
a₂	d₂	d₄	a₂d₂ $≺$ a₂d₄
a₂	d₃	d₄	a₂d₃ $≺$ a₂d₄

表2 A条件下属性D的偏好关系

Table 2 Preference relations of attribute D under A

Value of X₁	Preference Relationship
a₁	a₁d₄ $≻$ a₁d₃ $≻$ a₁d₁ $≻$ a₁d₂
a₂	a₁d₄ $≻$ a₁d₃ $≻$ a₁d₂ $≻$ a₁d₁

偏好对与偏好关系并非始终保持一致.若存在不一致情况，以偏好对在偏好数据库中的数据量为权重，删除权重较低的偏好对，力求保留具有较多评价的数据.例如，存在偏好关系a₁d₁ $≻$ a₁d₂，a₁d₂ $≻$ a₁d₃和a₁d₃ $≻$ a₁d₁，其不满足一致性，统计偏好对o(a₁d₁,a₁d₂)，o(a₁d₂,a₁d₃)和

o(a₁d₃,a₁d₁)在偏好数据库中的占比weight

$(o (a_{1} d_{1}, a_{1} d_{2}))$ =0.27, $w e i g h t (o (a_{1} d_{2}, a_{1} d_{3})) =$ 0.19, $w e i g h t (o (a_{1} d_{3}, a_{1} d_{1}))$ =0.09,删除权重较低的偏好对，所得偏好关系为a₁d₁ $≻$ a₁d₂ $≻$ a₁d₃.

3.2　基于贝叶斯方法的父属性求解

基于贝叶斯方法的父属性求解分为单一父属性求解和多父属性求解两部分，多父属性求解可通过单一父属性的相关性关系推理得到.

单一父属性的相关性关系计算中，根据式(1)，以相反父属性取值下存在不同条件偏好为满足条件，计算属性间的相关性关系.对于单一父属性P_i，其属性取值为 $p_{i}^{k}$ ，则条件偏好关系为 $p_{i}^{k} : p r (p_{i}^{k}, c)$ .同理，父属性取值为 $\bar{p_{i}^{k}}$ 条件下，存在条件偏好关系 $\bar{p_{i}^{k}} : p r (\bar{p_{i}^{k}}, c)$ ，不同父属性取值下条件偏好关系不同，即 $p_{i}^{k} : p r (p_{i}^{k}, c) ≠ \bar{p_{i}^{k}} : p r (\bar{p_{i}^{k}}, c)$ ，则此属性值对 $(p_{i}^{k}, \bar{p_{i}^{k}})$ 为一组满足条件，可根据所有属性值对中满足条件的比例得出相关性关系Pare(U,C).

本文基于贝叶斯方法，根据单一父属性概率及关系推出多父属性的相关性关系，这要求在进行多父属性计算前需要计算单一父属性相关关系，并构建单一父属性条件偏好概率数据库.如算法1所示.

算法1 单一父属性条件概率学习算法CPLS (P,V)

Input：评分数据库P，属性集合V

Output：单一父属性条件偏好概率数据库cell

For each single parent attribute $P_{i} ∈ V$

For each subattribute $C ∈ V & |C| = 1, C ≠ P_{i}$

For each parent attribute value $(p_{i}^{k}, \bar{p_{i}^{k}}) ∈ P_{i}$ ,subattribute value $c ∈ C$

cell $←$ $P (p_{i}^{k}| p r (p_{i}^{k}, c))$ , store conditional preference probability in cell

cell $←$ $P (p r (p_{i}^{k}, c))$ ,store preference probability in

cell End for

P a r e (P, C) = \frac{s u m (p_{i}^{k} : p r (p_{i}^{k}, c) ≠ \bar{p_{i}^{k}} : p r (\bar{p_{i}^{k}}, c'))}{n u m (p a i r (p_{i}^{k}, \bar{p_{i}^{k}}))}

End for

Return $P a r e (U, C)$ ,cell;

根据贝叶斯方法计算单一父属性相关性关系：

P (p r (p_{i}^{k}, c) |p_{i}^{k}) = \frac{P (p_{i}^{k}| p r (p_{i}^{k}, c)) × P (p r (p_{i}^{k}, c))}{P (p_{i}^{k})}

可推出：

P (p_{i}^{k}| p r (p_{i}^{k}, c)) = \frac{P (p r (p_{i}^{k}, c) |p_{i}^{k}) × P (p_{i}^{k})}{P (p r (p_{i}^{k}, c))}

如果需要计算多父属性下的条件偏好概率 $P a r e (P_{i} ⋃ P_{j}, C)$ ，则需要对 $p_{i}^{k}$ 与 $p_{j}^{l}$ 条件下的偏好对 $P (p r (p_{i}^{k} ⋃ p_{j}^{l}, c) |p_{i}^{k} ⋃ p_{j}^{l})$ , $P (p r (\bar{p_{i}^{k} ⋃ p_{j}^{l}}, c)|$

$\bar{p_{i}^{k} ⋃ p_{j}^{l}})$ 进行计算确定满足条件.多父属性条件下的偏好概率可通过单一父属性的条件偏好概率求得，如式(2)所示:

\begin{array}{l} P (p r (p_{i}^{k} ⋃ p_{j}^{l}, c)| p_{i}^{k} ⋃ p_{j}^{l}) = \\ \frac{P (p_{i}^{k} \cup p_{j}^{l}| p r (p_{i}^{k} ⋃ p_{j}^{l}, c)) × P (p r (p_{i}^{k} ⋃ p_{j}^{l}, c))}{P (p_{i}^{k} ⋃ p_{j}^{l})} = \\ \frac{P (p_{i}^{k}| p r (p_{i}^{k}, c)) × P (p_{j}^{l}| p r (p_{j}^{l}, c)) × P (p r (p_{i}^{k} ⋃ p_{j}^{l}, c))}{P (p_{i}^{k} ⋃ p_{j}^{l})} \end{array}

(2)

多父属性下的满足条件为:

p_{i}^{k} ⋃ p_{j}^{l} : p r (p_{i}^{k} ⋃ p_{j}^{l}, c) ≠ \bar{p_{i}^{k} ⋃ p_{j}^{l}} : p r (\bar{p_{i}^{k} ⋃ p_{j}^{l}}, c)

以多父属性下具有满足条件的偏好个数比例作为相关性关系取值 $P a r e (p_{i}^{k} ⋃ p_{j}^{l}, C)$ .将 $P_{i} ⋃ P_{j}$ 条件下概率最大的偏好关系存入CPT中，作为CP⁃nets的条件偏好表.算法2为基于贝叶斯方法的多父属性学习算法.

算法2 基于贝叶斯方法的多父属性学习MFAL (U,C, $α$ ,cell)

Input：父属性集U，子属性C，阈值 $α$ ，单一父属性条件偏好概率数据库cell

Output：相关性关系 $P a r e (U, C)$ ，条件偏好表CPT（U,C）

For each $P_{i}, P_{j} ∈ U$ ,U is a set of multi⁃attribute fathers

For each $p_{i}^{k} ∈ P_{i}, p_{j}^{l} ∈ P_{j}$

P (p r (p_{i}^{k} ⋃ p_{j}^{l}, c)| p_{i}^{k} ⋃ p_{j}^{l})

← \frac{P (p_{i}^{k}| p r (p_{i}^{k}, c)) × P (p_{j}^{l}| p r (p_{j}^{l}, c)) × P (p r (p_{i}^{k} ⋃ p_{j}^{l}, c))}{\overset{n}{∑_{i = 1}} P (p r (c)) P (p_{i}^{k} \cup p_{j}^{l}| p r (c))}

If $p r (p_{i}^{k} ⋃ p_{j}^{l}, c)$ is max probability under the condition

that father attribute is $p_{i}^{k} ⋃ p_{j}^{l}$

$p_{i}^{k} ⋃ p_{j}^{l} : p r (p_{i}^{k} ⋃ p_{j}^{l}, c)$ deposit in $C P T (U, C)$

End if

End for

For each $p r (p_{i}^{k} ⋃ p_{j}^{l}, c), p r (\bar{p_{i}^{k} ⋃ p_{j}^{l}}, c') ∈ C P T (U, C)$

If $p r (p_{i}^{k} ⋃ p_{j}^{l}, c) ≠ p r (\bar{p_{i}^{k} ⋃ p_{j}^{l}}, c')$

num++;

End if End for

$P a r e (U, C) ← \frac{n u m}{n u m b e r o f (p_{i}^{k} ⋃ p_{j}^{l}, \bar{p_{i}^{k} ⋃ p_{j}^{l}})}$ End for

Return $P a r e (U, C)$ , $C P T (U, C)$ ;

例2 存在属性集V= $\{A, B, C, D\}$ ，现根据单一属性关系A,B属性及C,B属性的相关性关系推出AC，B属性的相关性关系，CPLS算法计算得出单一父属性条件偏好概率数据库cell，部分数据如下：

P (a_{1}| b_{1} ≻ b_{2} ≻ b_{3}) = 0.3

，

P (a_{1}| b_{1} ≻ b_{3} ≻ b_{2}) = 0.6

P (a_{1}| b_{2} ≻ b_{1} ≻ b_{3}) = 0.1

，

P (a_{1}| b_{2} ≻ b_{3} ≻ b_{1}) = 0.4

P (a_{1}| b_{3} ≻ b_{1} ≻ b_{2}) = 0.3

，

P (a_{1}| b_{3} ≻ b_{2} ≻ b_{1}) = 0.2

P (a_{2}| b_{1} ≻ b_{2} ≻ b_{3}) = 0.4

，

P (a_{2}| b_{1} ≻ b_{3} ≻ b_{2}) = 0.2

P (a_{2}| b_{2} ≻ b_{1} ≻ b_{3}) = 0.5

，

P (a_{2}| b_{2} ≻ b_{3} ≻ b_{1}) = 0.3

P (a_{2}| b_{3} ≻ b_{1} ≻ b_{2}) = 0.5

，

P (a_{2}| b_{3} ≻ b_{2} ≻ b_{1}) = 0.3

P (a_{3}| b_{1} ≻ b_{2} ≻ b_{3}) = 0.3

，

P (a_{3}| b_{1} ≻ b_{3} ≻ b_{2}) = 0.2

P (a_{3}| b_{2} ≻ b_{1} ≻ b_{3}) = 0.4

，

P (a_{3}| b_{2} ≻ b_{3} ≻ b_{1}) = 0.3

P (a_{3}| b_{3} ≻ b_{1} ≻ b_{2}) = 0.2

，

P (a_{3}| b_{3} ≻ b_{2} ≻ b_{1}) = 0.5

P (c_{1}| b_{1} ≻ b_{2} ≻ b_{3}) = 0.4

，

P (c_{1}| b_{1} ≻ b_{3} ≻ b_{2}) = 0.2

P (c_{1}| b_{2} ≻ b_{1} ≻ b_{3}) = 0.5

，

P (c_{1}| b_{2} ≻ b_{3} ≻ b_{1}) = 0.7

P (c_{1}| b_{3} ≻ b_{1} ≻ b_{1}) = 0.8

，

P (c_{1}| b_{3} ≻ b_{2} ≻ b_{2}) = 0.3

P (c_{2}| b_{1} ≻ b_{2} ≻ b_{3}) = 0.6

，

P (c_{2}| b_{1} ≻ b_{3} ≻ b_{2}) = 0.8

P (c_{2}| b_{2} ≻ b_{1} ≻ b_{3}) = 0.5

，

P (c_{2}| b_{2} ≻ b_{3} ≻ b_{1}) = 0.3

P (c_{2}| b_{3} ≻ b_{1} ≻ b_{1}) = 0.2

，

P (c_{2}| b_{3} ≻ b_{2} ≻ b_{2}) = 0.7

P (b_{1} ≻ b_{2} ≻ b_{3}) = 0.2

，

P (b_{1} ≻ b_{3} ≻ b_{2}) = 0.1

P (b_{2} ≻ b_{1} ≻ b_{3}) = 0.2

，

P (b_{2} ≻ b_{3} ≻ b_{1}) = 0.2

P (b_{3} ≻ b_{1} ≻ b_{2}) = 0.1

，

P (b_{3} ≻ b_{2} ≻ b_{1}) = 0.2

根据贝叶斯公式，可得：

\begin{array}{l} P (b_{1} ≻ b_{2} ≻ b_{3}| a_{1}, c_{1}) = \\ \frac{P (a_{1}, c_{1}| b_{1} ≻ b_{2} ≻ b_{3}) × P (b_{1} ≻ b_{2} ≻ b_{3})}{\overset{n}{∑_{i = 1}} P (p r (B_{i})) P (a_{1}, c_{1}| p r (B_{i}))} = \\ \frac{0.3 × 0.4 × 0.2}{0.138} = 0.174 \end{array}

同理可得：

P (b_{1} ≻ b_{3} ≻ b_{2}| a_{1}, c_{1}) =

0.087

P (b_{2} ≻ b_{1} ≻ b_{3}| a_{1}, c_{1}) =

0.072

P (b_{2} ≻ b_{3} ≻ b_{1}| a_{1}, c_{1}) =

0.41

P (b_{3} ≻ b_{1} ≻ b_{2}| a_{1}, c_{1}) =

0.174

P (b_{3} ≻ b_{2} ≻ b_{1}| a_{1}, c_{1}) =

0.087

存在关系：

$b_{2} ≻ b_{3} ≻ b_{1}| a_{1}, c_{1}$ 且 $P (b_{2} ≻ b_{3} ≻ b_{1}| a_{1}, c_{1}) = 0.41$

同理可得所有关系：

b_{2} ≻ b_{3} ≻ b_{1}| a_{1}, c_{1}

，

b_{1} ≻ b_{3} ≻ b_{2}| a_{1}, c_{2}

b_{2} ≻ b_{1} ≻ b_{3}| a_{2}, c_{1}

，

b_{2} ≻ b_{1} ≻ b_{3}| a_{2}, c_{2}

b_{2} ≻ b_{3} ≻ b_{1}| a_{3}, c_{1}

，

b_{2} ≻ b_{1} ≻ b_{3}| a_{3}, c_{2}

根据式(1)得 $P a r e (A C, B)$ =0.83.大于阈值 $α = 0.6$ ，满足父子关系条件，确定其相关性关系为 $A C → B$ .且其条件偏好表 $C P T (A C, B)$ 为：

a_{1}, c_{1} : b_{2} ≻ b_{3} ≻ b_{1}

，

a_{1}, c_{2} : b_{1} ≻ b_{3} ≻ b_{2}

a_{2}, c_{1} : b_{2} ≻ b_{1} ≻ b_{3}

，

a_{2}, c_{2} : b_{2} ≻ b_{1} ≻ b_{3}

a_{3}, c_{1} : b_{2} ≻ b_{3} ≻ b_{1}

，

a_{3}, c_{2} : b_{2} ≻ b_{1} ≻ b_{3}

3.3　基于遗传算法的CP⁃nets学习

CP⁃nets结构以矩阵形式存储，矩阵行代表父属性，列代表子属性.若存在属性集合 $V = \{X_{1}, X_{2}, ⋯, X_{i}, ⋯,$

$X_{n}\}$ ，使CP⁃nets结构矩阵K中存在元素K(i,j)=1，则代表第i个属性X_i是第j个属性X_j的父亲；若为0则表示不存在父子关系.以当前子属性的相关性关系取值为权重，存储到结构权值矩阵中，代表当前子属性与父属性的相关性关系重要程度.对于结构权值W，其第i个元素代表CP⁃nets中第i个元素的父子关系程度 $P a r e (U, C_{i})$ .例如，属性集合 $V = \{A, B,$ $C\}$ ，所学CP⁃nets及其结构矩阵K和结构权值矩阵W如图2所示.

图2

图2 CP⁃nets及其结构矩阵

Fig.2 CP⁃nets and structural matrix

对于CP⁃nets结构I，所有子属性的相关性关系均值为结构I的适应度，适应度如式(3)所示.例如，图2所示的CP⁃nets的适应度 $f i t (I) = 0.85$ .计算公式如式（3）所示：

f i t (I) = \frac{\overset{| V |}{∑_{i = 1}} P a r e (U_{i}, C_{i})}{n u m b e r o f c h i l d r e n}

(3)

通过结构I中各属性相关性关系 $P a r e (U_{i}, C_{i})$ 推断其适应度取值fit(I)，并通过基于遗传算法的CP⁃nets学习算法学习具有最高适应度的结构I.

对于存在n个属性的种群，在第t代进行交叉操作，其种群大小为M，随机组合M/2对个体作为双亲，对双亲的1~n²中随机位置进行基因互换，进行基因交叉操作，交叉后得到两个子个体，通过适应度函数重新评估子个体的适应度并参与双亲的适应度比较.为保证种群大小始终为M并完成进化，保留四个个体中适应度最高的两个个体参与下一代遗传计算.具体过程如算法3所示.

算法3 基于遗传算法的CP⁃nets学习算法GCPL (P,V,M,T, $α$ )

Input：评分数据库P，属性集V，种群大小M，进化代数T，阈值 $α$

Ouput：CP⁃nets种群G(T)

cell $←$ CPLS(P,V);

initialize G (0),Random Generation of CP⁃nets Structure G (0)

t $←$ 0;

while (t≤T) do

For each I $←$ 1 to M,M is individual number of

population

For each $i ← 1 ∶ |V|$

$P a r e (U_{i}, C_{j})$ , $C P T (U, C)$ $←$ MFAL

(U_i,C_j, $α$ ,cell);

fitness=fitness+ $P a r e (U_{i}, C_{j})$ ;

End for

fit(I)=fitness/ $n u m b e r o f c h i l d r e n$ ;

End for

Individuals in G (t) are crossed as parents to get two offspring,and two individuals with the highest fitness are selected from four individuals to form the next generation G (t+1)

The individuals in G (t+1) were randomly mutated and the mutated individuals were reassessessed to form a new G (t+1)

t=t+1;

End while

Return G (T);

算法GCPL中的交叉运算如图3，若随机选取双亲个体K₁，K₂，适应度分别为0.85和0.74，随机选择位置4，5进行基因交叉操作得到子个体K₃，K₄.重新进行适应度评估，分别为0.68和0.915，保留两个适应度最高的个体K₁和K₄作为下一代种群个体继续进行遗传操作.

图3

图3 交叉算法

Fig.3 Crossover algorithm

为尽可能模拟真实遗传，增加种群基因多样性，加入变异操作，对第t代中随机个体的随机基因以较小概率进行0,1互换，并重新评估突变个体适应度.若突变后适应度增高，则保留突变基因，反之则放弃突变基因.突变可以加速种群的进化速度，但因属性不能做自己属性的父亲节点，所以矩阵对角线元素被排除在变异操作之外.

3.4　CP⁃nets去环算法

CP⁃nets结构不允许环的存在，但根据遗传算法所学的个体却极可能存在环路，所以如何去环成为重中之重.若在个体的适应度评估过程中去环，实验准确性会更高，但时间复杂度也会大幅增加.而且，即便每一代中所有个体均为无环结构，但交叉、变异后的新生代个体依然会产生新的环路.为了解决环路问题，对最后一代种群G(T)中的所有结构进行去环操作，并重新评估适应度，选取适应度最高的结构I作为最终CP⁃nets结构，即所学结构为I.

如图4所示，结构不存在入度为0的节点即为环路.对于G(T)中的CP⁃nets结构I，通过Delink (I,I')算法去环.若I存在入度为0的节点X_i，在副本I'中删除当前节点，并删除其相连边 $〈X_{i}, X_{i}〉$ ，更新入度值，寻找新的入度为0的节点进行删除.若最终所有节点都被删除，表明此结构I中没有环的存在；若存在未被删除的节点，代表存在环路.删除环路中权值最小的有向边，即删除取值最小的相关性关系，重新进行Delink ()算法直至所有环路被删除，可得无环CP⁃nets.无环结构学习算法如算法4所示.

图4

图4 有环结构及其入度值

Fig.4 Ring structure and input value

算法4 无环CP⁃nets结构学习算法GCPL

Input：遗传算法所学结构种群G (T)

Ouput：CP⁃nets结构I

Delink (I,I')

{

while (existence in⁃degree of vertex is 0) do

For each X_i $∈$ I'

If X_i in⁃degree=0

Delete X_i from I';

Delete edge X_i→X_i.next from I';

update in⁃degree information;

End if

End for

End while

If I'!=NULL

Delete Min $P a r e (U, C)$ edge from I;

Delink (I);

If I'=NULL

return I;

End if

}

G(T)=EWCPL(P,V,M,T, $α$ );

For each I $∈$ G (T)

Delink (I)

End for

find Max I $∈$ G (T);

Return I;

最终所学的无环CP⁃nets如图5所示，包含条件偏好结构和条件偏好表CPT两部分.

图5

图5 无环CP⁃nets

Fig.5 Acyclic CP⁃nets

4 结果验证

4.1　模拟数据实验

随机生成CP⁃nets结构，通过随机结构得出导出图^[14]，用Warshall^[14]算法对导出图中条件偏好关系进行扩充，得出存储全部条件偏好的传递闭包矩阵，即CPT，共同构成模拟CP⁃nets.模拟CP⁃nets包含条件偏好结构G及条件偏好表GT两部分，通过传递闭包矩阵构成偏好数据库P进行CP⁃nets学习，所学CP⁃nets由条件偏好结构G'及其条件偏好表GT'构成.

下文从两方面验证实验结果的正确性：结构正确性和偏好正确性(偏好正确性也称相似性).

通过式(4)对结构正确性进行评价.e⁃arc表示G与G'中相同有向边的数目，d⁃arc表示不同有向边的数目.Correct表示G和G'的结构正确性关系，随d⁃arc的增大，正确性逐渐降低.

C o r r e c t = \frac{e - a r c}{e - a r c + d - a r c}

(4)

通过式(5)对偏好正确性进行评价.Similar表示GT与GT'中偏好相同的概率.

S i m i l a r = \frac{|p r_{G} (u, c) = p r_{G'} (u, c)|}{|(p r_{G} (u, c), p r_{G'} (u, c))|}

(5)

在不同属性集 $|V| = 6,8, 10$ 下构建六组模拟数据，以种群大小M=50、进化代数T=100、阈值 $α$ =0.6作为参数，进行CP⁃nets学习.以相同属性个数下不同模拟数据的正确性评价均值为结果，构建结构正确性分析，如表3所示.实验证明，所学结构随属性个数增多，正确性逐渐降低，但整体处于较高水平，且在属性个数 $|V|$ 增大到一定程度时仍能保持较高的结构正确性.

表3 不同属性个数下的结构正确性

Table 3 Structural correctness under different number of attributes

$\|V\|$	Correct
6	0.9453
8	0.8915
10	0.8590

以属性集 $|V|$ =6、种群大小M=50、进化代数T=100、阈值 $α$ =0.6为参数，进行CP⁃nets学习.验证不同数据量100,400,800,1500,2000下的偏好正确性.实验结果如图6所示.实验证明，数据量较低时，相似度也处于较低水平，且随着数据量的增大逐渐增高，在数据量为1500时达到较高水平且趋于最大值.在数据量较大时，本文算法能保证偏好学习正确性.

图6

图6 不同数据大小下的相似度

Fig.6 Similarity under different data sizes

对不同属性个数下CP⁃nets学习时间进行统计，结果如图7所示.实验证明，在数据量较小时，运行时间微乎其微，随数据量增大，运行时间呈线性增长，对于不同属性个数 $|V|$ ，运行时间随属性个数增加呈指数增长.

图7

图7 不同属性个数下CP⁃nets学习时间

Fig.7 Learning time of CP⁃nets under different numbers of attributes

4.2　真实数据实验

真实实验的数据是来自Kamishima收集的寿司数据集，此数据集包含一万名用户对10种寿司的评分.每种寿司有七种属性：类型、是否添加海鲜、其他食材、油性大小、使用次数、价格、卖出量，属性取值各不相同.共有五种评分，-1分和0分为不喜欢，1分为未评分或无偏好，2分和3分为喜欢.去除未评分或无偏好的数据，根据喜好程度对数据进行偏好数据库划分.实验选择同一个地区、同一个区域、受同一种文化影响的人群(共得数据2300条)建立偏好数据库进行实验，以确保实验结果具有实际意义.

对不同偏好数据库中不同数据量的数据进行实验.从多组偏好数据库P₁,P₂,P₃,P₄,P₅中选取数据量为100,400,800,1500,2000的数据计算相似度，结果如图8所示.证明在数据量较小时，数据波动较大，且部分数据库所学CP⁃nets结构正确性处于较低水平，随数据量增加，偏好正确性逐渐趋于稳定，且处于较高水平.

图8

图8 不同偏好数据库与数据大小下的相似度

Fig.8 Similarity under different preference data⁃bases and data sizes

以添加噪声数据的方式模拟数据误差.在数据量为100，400，800，1500，2000的数据集中分别添加噪声水平0，0.01，0.05，0.1的噪声数据，并通过五组偏好数据库所学Similar的均值作为不同噪声水平下的相似度，结果如图9所示.实验证明，数据量较低时未能完全计算所有条件偏好，Similar整体处于较低水平；数据量较大时Similar处于较高水平且保持稳定.在各噪声水平下Similar不存在明显差异，抗噪能力较强，适用于存在部分误差的真实数据.

图9

图9 不同噪声水平下的相似度

Fig.9 Similarity at different noise levels

4.3　实验对比

在众多CP⁃nets学习算法中，性能存在较大差异.选取应用较为广泛的学习算法与本文算法进行比较，显示本文算法具备的优越性.早期Dimopouols et al^[21]的方法无法完成数据噪声处理，且不能进行全父属性集的相关性关系判定，不能学习无环CP⁃nets结构.之后，卡方检验^[22]对数据中存在的噪声进行了处理，但仍存在父属性选取单一、忽略其他可行性和无法进行无环CP⁃nets学习的问题.G方检验^[8]进行了相应的噪声处理并充分考虑多父属性的可行性，但采用穷举法的方式进行候选父亲集的搜索，大大增加了算法的时间复杂度，而且无法学习无环CP⁃nets的问题依旧存在.

本文针对以上问题，在程序运行之初加入数据预处理进行噪声数据处理，并采用遗传算法进行多候选父亲集的搜索，降低时间复杂度，得到精简CP⁃nets拓扑结构，通过结构权值的方式保持CP⁃nets的结构正确性，最终通过Delink算法进行无环CP⁃nets学习.表4为贝叶斯⁃遗传CP⁃nets学习算法与其他算法的比较，前三种算法均为二值属性下的CP⁃nets求解算法，本文算法可进行多值属性CP⁃nets求解.其中贝叶斯⁃遗传的学习父属性个数为属性取值个数n的 $|V|$ -1次方.

表4 贝叶斯⁃遗传CP⁃nets学习算法与其他算法的比较

Table 4 Comparison of Bayesian⁃genetic CP⁃nets learning algorithm with other algorithms

实验方法	噪声处理	父属性	结构环路
Dimopouols	不可处理	1	有环
卡方检验	可处理	1	有环
G方检验	可处理	2^\|V\|^-1	有环
贝叶斯⁃遗传方法	可处理	n^\|V\|^-1	无环

5 总结

本文提出基于贝叶斯⁃遗传方法的CP⁃nets学习算法.通过贝叶斯方法，以单一父属性求解多父属性的相关性关系，并进行条件偏好表的学习.根据适应度函数fit(I)，通过遗传算法在CP⁃nets结构搜索空间中搜索局部最优解，在有限代T中得出局部最优CP⁃nets结构.以Delink算法进行去环，CP⁃nets结构与贝叶斯方法所学CPT共同构成CP⁃nets，完成CP⁃nets学习.实验表明，本文算法具有稳定多值无环CP⁃nets学习能力.

本文算法有延展性，为未来工作奠定基础：

(1)采用其他结构学习方法(如K2算法、爬山算法)进行CP⁃nets结构学习，并与本文方法进行对比.

(2)通过剪枝算法，缩减CP⁃nets结构搜索空间，进一步降低挖掘算法的时间复杂度.

(3)对于大规模数据，采用并行的方式进行CP⁃nets学习.

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

Banawan

，Ulukus

Multi⁃message private information retrieval：capacity results and near⁃optimal schemes

IEEE Transactions on Information Theory，2018，64(10)：6842-6862.

[2]

L Y

，Xu

Q L

，Gan

，et al.

A probabilistic model of social working memory for information retrieval in social interactions

IEEE Transactions on Cybernetics，2018，48(5)：1540-1552.

[3]

Chung

，Kogelmann

Diversity and rights：a social choice⁃theoretic analysis of the possibility of public reason

Synthese，2018，doi：0.1007/s11229⁃018⁃1737⁃4.

[4]

Han

，Li

J Q

，LI

W T

，et al.

An app usage recommender system：improving prediction accuracy for both warm and cold start users

Multimedia Systems，2019，doi：10.1007/s00530⁃018⁃0601⁃1.

[5]

，Su

，Tian

Z H

，et al.

A novel search engine for internet of everything based on dynamic prediction

China Communications，2019，16(3)：42-52.

[6]

Lui

，Au

C H

I. S. educational game：adoption in teaching search engine optimization (SEO)

Journal of Computer Information Systems，2018，doi：10.1080/08874417.2018.1461034.

[7]

辛冠琳，刘惊雷.

基于精确P值计算学习无环CP⁃nets

南京大学学报(自然科学)，2017，53(3)：450-461.

Xin G L，Liu J L

Learning acyclic CP⁃nets based on exact P⁃value computation

Journal of Nanjing University (Natural Science)，2017，53(3)：450-461.

[8]

辛冠琳，刘惊雷.

基于G方检验的CP⁃nets学习

南京大学学报(自然科学)，2015，51(4)：781-795.

Xin G L，Liu J L

Learning CP⁃nets based on G² test

Journal of Nanjing University (Natural Science)，2015，51(4)：781-795.

[9]

刘兆伟，仲兆琳，王磊等.

机器人的CP⁃nets优化类人轨迹规划

控制理论与应用，2018，35(12)：1772-1778.

Liu

Z W

，Zhong

Z L

，Wang

，et al.

Optimal human⁃like trajectory planning of CP⁃nets for robot

Control Theory and Application，2018，35(12)：1772-1778.

[10]

刘兆伟

基于偏好数据库的无环CP⁃nets结构学习方法研究

博士学位论文. 泰安：山东大学，2018.

Liu Z W.

R Research on structure learning methods of acyclic CP⁃nets based on preference database

Ph.D Dissertation. Taian：Shandong University，2018.

[11]

刘惊雷，廖士中.

CP⁃nets学习的复杂度

计算机科学，2018，45(6)：211-215.

Liu J L，Liao S Z

Complexity of CP⁃nets learning

Computer Science，2018，45(6)：211-215.

[12]

辛冠琳，刘惊雷.

从偏好数据库中挖掘Ceteris Paribus偏好

计算机应用，2016，36(8)：2092-2098，2108.

Xin G L，Liu J L

Mining ceteris paribus preference from preference database

Journal of Computer Application，2016，36(8)：2092-2098，2108.

[13]

De Amo

，Bueno

M L P

，Alves

，et al.

CPrefMiner：An algorithm for mining user contextual preferences based on Bayesian networks

∥IEEE International Conference on Tools with Artificial Intelligence. Athens，Greece：IEEE Computer Society，2012：114-121.

[14]

刘惊雷

CP⁃nets及其表达能力研究

自动化学报，2011，37(3)：290-302.

Liu J L

CP⁃nets and its expressive ability research

Acta automatica sinica，2011，37(3)：290-302.

[15]

Gao

X G

，Yang

，Guo

Z G

，et al.

Bayesian approach to learn Bayesian networks using data and constraints

∥Proceedings of the 23^rd International Conference on Pattern Recognition. Cancun，Mexico：IEEE，2017：3667-3672.

[16]

Foley

B R

，Marjoram

Sure enough：efficient Bayesian learning and choice

Animal Cognition，2017，20(5)：867-880.

[17]

Kordestani

，Samadi

M F

，Saif

，et al.

A new fault prognosis of MFS system using integrated extended Kalman filter and Bayesian method

IEEE Transactions on Industrial Informatics，2015，doi：10.1109/TII.2018.2815036.

[18]

Larranaga

，Kuijper

C M H

，Murga

R H

，et al.

Learning bayesian network structures by searching for the best ordering with genetic algorithms

IEEE Transactions on Systems，Man，and Cybernetics⁃Part A：Systems and Humans，1996，26(4)：487-493.

[19]

Contaldi

，Vafaee

，Nelson

P C

Bayesian network hybrid learning using an elite⁃guided genetic algorithm

Artificial Intelligence Review，2019，52(1)：245-272.

[20]

T Z

，Li

Y X

，Yang

X L

Rock burst prediction based on genetic algorithms and extreme learning machine

Journal of Central South University，2017，24(9)：2105-2113.

[21]

Dimopoulos

，Michael

，Athienitou

Ceteris Paribus preference elicitation with predictive guarantees

∥Proceedings of the 21^st International Joint Conference on Artifical Intelligence. Pasadena，CA，USA：Morgan Kaufmann Publishers Inc，2009：1890-1895.

[22]

Liu

J T

，Yao

Z J

，Xiong

，et al.

Learning conditional preference network from noisy samples using hypothesis testing

Knowledge⁃Based Systems，2013，40：7-16.