可以使用clpfd实现覆盖算法吗?

Question

假设我想以一种简单的匹配方式找到区分两个类的特征/属性集，我可以在prolog中使用clpfd来做到这一点吗?

c_s_mining(Features,Value):-
 Features = [F1,F2,F3,F4],
 Features ins 0..1,
 ExampleA = [A1,A2,A3,A4],
 ExampleB =[B1,B2,B3,B4],
 ExampleC =[C1,C2,C3,C4],
 A1 #=0, A2#=1,A3#=0,A4#=1,
 B1 #=0, B2#=1,B3#=0,B4#=1,
 C1 #=1, C2#=0,C3#=0,C4#=1,
 ExampleD =[D1,D2,D3,D4],
 ExampleE =[E1,E2,E3,E4],
 ExampleQ =[Q1,Q2,Q3,Q4],
 D1#=1,D2#=0,D3#=1,D4#=0,
 E1#=1,E2#=0,E3#=1,E4#=0,
 Q1#=0,Q2#=1,Q3#=1,Q4#=0,
 Positives =[ExampleA,ExampleB,ExampleC],
 Negatives = [ExampleD,ExampleE,ExampleQ],
 TP in 0..sup,
 FP in 0..sup,
 covers(Features,Positives,TP),
 covers(Features,Negatives,FP),
 Value  in inf..sup,
 Value #= TP-FP.

covers(Features,Examples,Number_covered):-
   findall(*,(member(E,Examples),E=Features),Covers), length(Covers,Number_covered).

每个例子由四个二元特征描述，有三个正例(A,B,C)和三个负例(D,E,Q)。

如果一个示例匹配，则由一组选定的特性覆盖。例如，如果Features和[0,1,0,1]统一，那么这将匹配两个正的和0个负的。

我设置Value等于TP(真阳性)- TN(真阴性)。我想最大化Value并找到相应的特征集。

查询?-c_s_mining(Features,Value),labelling([max(Value)],[Value]).我期望的答案是:Features =[0,1,0,1], Value =2，但我得到Features =[_G1,_G2,_G3,G4],Value =0, G1 in 0..1, G2 in 0..1, G3 in 0..1, G4 in 0..1.

Answer 1

CLP(FD)约束具体化

要推断什么匹配，什么不匹配，使用约束具体化:它允许您将约束的真值反映到表示布尔值的CLP(FD)变量中。

您可以使用这些值执行算术，以表示匹配示例的数量等。

例如，你可以这样写:

:- use_module(library(clpfd)).
c_s_mining(Features, Value) :-
    ExampleA = [0,1,0,1],
    ExampleB = [0,1,0,1],
    ExampleC = [1,0,0,1],
    ExampleD = [1,0,1,0],
    ExampleE = [1,0,1,0],
    ExampleQ = [0,1,1,0],
    same_length(Features, ExampleA),
    Features ins 0..1,
    Positives = [ExampleA,ExampleB,ExampleC],
    Negatives = [ExampleD,ExampleE,ExampleQ],
    covers_number(Features, Positives, TP),
    covers_number(Features, Negatives, FP),
    Value #= TP-FP.

covers_number(Features, Examples, Number):-
    maplist(covers_(Features), Examples, Numbers),
    sum(Numbers, #=, Number).
covers_([F1,F2,F3,F4], [E1,E2,E3,E4], Covered) :-
    Covered #<==> (F1#=E1 #/ F2#=E2 #/ F3#=E3 #/ F4#=E4).

然后使用labeling/2的优化选项首先获得最大值:

<>之前? - c_s_mining (Fs值),标签(max(值),Fs)。Fs = [0,1,0,1]，Value = 2 ;Fs = [1,0,0,1]，Value = 1;Fs = [0,0,0,0]，值= 0;等。之前

还请注意，我已经删除了一些多余的约束，例如Value in inf..sup，因为约束求解器可以自己计算出它们。

---

CLP(B):布尔约束的声明性替代

对于这种布尔模式的情况，还可以查看CLP(B):在布尔变量上的约束逻辑编程，例如在SICStus Prolog和SWI中可用。使用CLP(B)需要以稍微不同的方式表述搜索，因为它缺乏CLP(FD)的强大标记选项。然而，与CLP(FD)相比，CLP(B)是完整的，可以更早地发现不一致以及所涉及的约束。

在下面的代码中，我使用CLP(FD)来指导搜索最优值，然后使用CLP(B)来声明实际约束。最后调用labeling/1(请注意，这来自library(clpb)，不要与CLP(FD)的labeling/2混淆)用于确保所有CLP(B)变量的接地值。在这一点上，它似乎只是一种形式:我们已经知道，在这一点上有一个解决方案，感谢CLP(B)的完整性。

:- use_module(library(clpb)).
:- use_module(library(clpfd)).
c_s_mining(Features, Value):-
    ExampleA = [0,1,0,1],
    ExampleB = [0,1,0,1],
    ExampleC = [1,0,0,1],
    ExampleD = [1,0,1,0],
    ExampleE = [1,0,1,0],
    ExampleQ = [0,1,1,0],
    same_length(Features, ExampleA),
    Positives = [ExampleA,ExampleB,ExampleC],
    Negatives = [ExampleD,ExampleE,ExampleQ],
    [TP,FP] ins 0..3, % (in this case)
    Value #= TP-FP,
    labeling([max(Value)], [TP,FP]),
    covers_number(Features, Positives, TP),
    covers_number(Features, Negatives, FP),
    labeling(Features).
covers_number(Features, Examples, Number):-
    maplist(covers_(Features), Examples, Numbers),
    sat(card([Number], Numbers)).
covers_([F1,F2,F3,F4], [E1,E2,E3,E4], Covered) :-
    sat(Covered =:= ((F1=:=E1)*(F2=:=E2)*(F3=:=E3)*(F4=:=E4))).