prolog - manejo - recorrer lista racket

¿Puedes usar clpfd para implementar un algoritmo de cobertura?

Question

Supongamos que quiero encontrar el conjunto de características / atributos que diferencian dos clases de una manera simple, ¿puedo usar clpfd en prolog para hacer esto?

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).

Cada ejemplo está descrito por cuatro características binarias, y hay tres ejemplos positivos (A, B, C) y tres ejemplos negativos (D, E, Q).

Un ejemplo está cubierto por un conjunto de características seleccionadas si coinciden. Entonces, por ejemplo, si Features está unificado con [0,1,0,1] , entonces esto coincidirá con dos positivos y 0 negativos.

Establecí Value para que sea igual a TP (verdaderos positivos) - TN (negativos verdaderos). Quiero maximizar el valor y encontrar el conjunto correspondiente de características.

?-c_s_mining(Features,Value),labelling([max(Value)],[Value]). La respuesta que espero es: Features =[0,1,0,1], Value =2 pero obtengo 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

Reificación de restricciones CLP (FD)

Para razonar sobre qué coincide y qué no, utilice la reificación de restricción: le permite reflejar el valor de verdad de una restricción en una variable CLP (FD) que denota un valor booleano.

Puede realizar aritmética con dichos valores para indicar el número de ejemplos coincidentes, etc.

Por ejemplo, en tu caso, puedes escribir:

:- 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).

Y luego use las opciones de optimización de labeling/2 para obtener primero los valores más grandes:

?- c_s_mining(Fs, Value), labeling([max(Value)], Fs). Fs = [0, 1, 0, 1], Value = 2 ; Fs = [1, 0, 0, 1], Value = 1 ; Fs = [0, 0, 0, 0], Value = 0 ; etc.

Observe también que he eliminado algunas restricciones superfluas, como Value in inf..sup , ya que el solucionador de restricciones puede resolverlas por sí mismo.

CLP (B): una alternativa declarativa para las restricciones booleanas

Para el caso de tales patrones booleanos, también consulte CLP ( B ): Programación lógica de restricción sobre variables booleanas , disponible por ejemplo en SICStus Prolog y SWI. El uso de CLP (B) requiere que formule la búsqueda de forma diferente, ya que carece de las potentes opciones de etiquetado de CLP (FD). Sin embargo, a diferencia de CLP (FD), CLP (B) está completo y puede detectar incoherencias y limitaciones mucho antes.

En el siguiente código, estoy usando CLP (FD) para guiar la búsqueda de valores óptimos, y luego uso CLP (B) para expresar las restricciones reales. Una última llamada de labeling/1 (tenga en cuenta que esto es de la library(clpb) , que no debe confundirse con CLP (FD) ''s labeling/2 ) se utiliza para garantizar los valores de tierra para todas las variables CLP (B). En el punto en que aparece, es solo una formalidad en cierto sentido: ya sabemos que hay una solución en este punto, gracias a la integridad de 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))).