Ayuda necesaria Crear un árbol binario con la tabla de verdad

Question

Primero, para proporcionar una divulgación completa, quiero señalar que esto está relacionado con la tarea en una clase de Aprendizaje automático. Esta pregunta no es la pregunta de la tarea y, en cambio, es algo que tengo que resolver para completar el problema más grande de la creación de un Algoritmo del Árbol de Decisión ID3.

necesito para generar el árbol similar al siguiente cuando se le da una tabla de verdad

let learnedTree = Node(0,"A0", Node(2,"A2", Leaf(0), Leaf(1)), Node(1,"A1", Node(2,"A2", Leaf(0), Leaf(1)), Leaf(0))) 

learnedTree es de BinaryTree tipo que he definido como sigue:

type BinaryTree = 
    | Leaf of int 
    | Node of int * string * BinaryTree * BinaryTree 

algoritmos ID3 tienen en cuenta varias ecuaciones para determinar dónde dividir el árbol, y tengo todo eso resuelto, solo estoy teniendo problemas para crear el árbol aprendido de mi tabla de verdad. Por ejemplo, si tengo la siguiente tabla

A1 | A2 | A3 | Class 
1  0 0  1 
0  1 0  1 
0  0 0  0 
1  0 1  0 
0  0 0  0 
1  1 0  1 
0  1 1  0 

Y decido dividir el atributo A1 iba a terminar con lo siguiente:

   (A1 = 1) A1 (A1 = 0) 
    A2 | A3 | Class    A2 | A3 | Class 
    0  0  1    1  0  1 
    0  1  0    0  0  0 
    1  0  1    0  0  0 
           0  1  1 

continuación, me gustaría dividir el lado izquierdo y dividir el lado derecho y continúe el patrón recursivo hasta que los nodos de las hojas sean puros y termine con un árbol similar al siguiente basado en la división.

let learnedTree = Node(0,"A0", Node(2,"A2", Leaf(0), Leaf(1)), Node(1,"A1", Node(2,"A2", Leaf(0), Leaf(1)), Leaf(0))) 

Esto es lo que he especie de "hackeado" juntos hasta ahora, pero creo que podría ser muy lejos:

let rec createTree (listToSplit : list<list<float>>) index = 
    let leftSideSplit = 
     listToSplit |> List.choose (fun x -> if x.Item(index) = 1. then Some(x) else None) 
    let rightSideSplit = 
     listToSplit |> List.choose (fun x -> if x.Item(index) = 0. then Some(x) else None) 
    if leftSideSplit.Length > 0 then 
     let pureCheck = isListPure leftSideSplit 
     if pureCheck = 0 then 
      printfn "%s" "Pure left node class 0" 
      createTree leftSideSplit (index + 1) 
     else if pureCheck = 1 then 
      printfn "%s" "Pure left node class 1" 
      createTree leftSideSplit (index + 1) 
     else 
      printfn "%s - %A" "Recursing Left" leftSideSplit 
      createTree leftSideSplit (index + 1) 
    else printfn "%s" "Pure left node class 0" 

¿Debo utilizar coincidencia de patrones en su lugar? ¿Algún consejo/ideas/ayuda? ¡Gracias un montón!

Answer 1

Edición: Desde entonces, he publicado una implementación de ID3 en mi blog en: http://blogs.msdn.com/chrsmith

Hey Jim, he estado queriendo escribir una entrada de blog en la implementación de ID3 F # por un tiempo - gracias por darme una ejecución. Si bien este código no implementa el algoritmo completo (o correctamente), debería ser suficiente para comenzar.

En general, tiene el enfoque correcto: representar cada sucursal como un caso de sindicato discriminado es bueno. Y como dijo Brian, List.partition es definitivamente una función práctica. El truco para hacer este trabajo correctamente es todo en la determinación del par de atributo/valor óptimo para dividir - y hacer que necesitará para calcular la ganancia de información a través de la entropía, etc.

type Attribute = string 
type Value = string 

type Record = 
    { 
     Weather : string 
     Temperature : string 
     PlayTennis : bool 
    } 
    override this.ToString() = 
     sprintf 
      "{Weather = %s, Temp = %s, PlayTennis = %b}" 
      this.Weather 
      this.Temperature 
      this.PlayTennis 

type Decision = Attribute * Value 

type DecisionTreeNode = 
    | Branch of Decision * DecisionTreeNode * DecisionTreeNode 
    | Leaf of Record list 

// ------------------------------------ 

// Splits a record list into an optimal split and the left/right branches. 
// (This is where you use the entropy function to maxamize information gain.) 
// Record list -> Decision * Record list * Record list 
let bestSplit data = 
    // Just group by weather, then by temperature 
    let uniqueWeathers = 
     List.fold 
      (fun acc item -> Set.add item.Weather acc) 
      Set.empty 
      data 

    let uniqueTemperatures = 
     List.fold 
      (fun acc item -> Set.add item.Temperature acc) 
      Set.empty 
      data 

    if uniqueWeathers.Count = 1 then 
     let bestSplit = ("Temperature", uniqueTemperatures.MinimumElement) 
     let left, right = 
      List.partition 
       (fun item -> item.Temperature = uniqueTemperatures.MinimumElement) 
       data 
     (bestSplit, left, right) 
    else 
     let bestSplit = ("Weather", uniqueWeathers.MinimumElement) 
     let left, right = 
      List.partition 
       (fun item -> item.Weather = uniqueWeathers.MinimumElement) 
       data 
     (bestSplit, left, right) 

let rec determineBranch data = 
    if List.length data < 4 then 
     Leaf(data) 
    else 
     // Use the entropy function to break the dataset on 
     // the category/value that best splits the data 
     let bestDecision, leftBranch, rightBranch = bestSplit data 
     Branch(
      bestDecision, 
      determineBranch leftBranch, 
      determineBranch rightBranch) 

// ------------------------------------  

let rec printID3Result indent branch = 
    let padding = new System.String(' ', indent) 
    match branch with 
    | Leaf(data) -> 
     data |> List.iter (fun item -> printfn "%s%s" padding <| item.ToString()) 
    | Branch(decision, lhs, rhs) -> 
     printfn "%sBranch predicate [%A]" padding decision 
     printfn "%sWhere predicate is true:" padding 
     printID3Result (indent + 4) lhs 
     printfn "%sWhere predicate is false:" padding 
     printID3Result (indent + 4) rhs 


// ------------------------------------  

let dataset = 
    [ 
     { Weather = "windy"; Temperature = "hot"; PlayTennis = false } 
     { Weather = "windy"; Temperature = "cool"; PlayTennis = false } 
     { Weather = "nice"; Temperature = "cool"; PlayTennis = true } 
     { Weather = "nice"; Temperature = "cold"; PlayTennis = true } 
     { Weather = "humid"; Temperature = "hot"; PlayTennis = false } 
    ] 

printfn "Given input list:" 
dataset |> List.iter (printfn "%A") 

printfn "ID3 split resulted in:" 
let id3Result = determineBranch dataset 
printID3Result 0 id3Result 

Answer 2

Puede usar List.partition en lugar de sus dos llamadas List.choose.

http://research.microsoft.com/en-us/um/cambridge/projects/fsharp/manual/FSharp.Core/Microsoft.FSharp.Collections.List.html

(o ahora http://msdn.microsoft.com/en-us/library/ee353738(VS.100).aspx)

No está claro para mí que la coincidencia de patrones que va a comprar mucho aquí; el tipo de entrada (lista de listas) y el procesamiento (partición y verificación de "pureza") no se presta realmente a eso.

Y por supuesto cuando finalmente obtienes el 'final' (una lista pura) necesitas crear un árbol, y presumiblemente esta función creará una hoja cuando la entrada solo tiene un 'lado' y es 'pura' , pero crea un nodo de los resultados del lado izquierdo y derecho para cada otra entrada. Tal vez. No acerté completamente con el algoritmo.

Espero que eso te ayude a guiarte un poco. Puede ser útil para elaborar algunas entradas y salidas de muestra más pequeñas para ayudar a resolver los diversos casos del cuerpo de la función.

Answer 3

Gracias Brian & Chris! De hecho, fui capaz de resolver esto y terminé con lo siguiente. Esto calcula la ganancia de información para determinar el mejor lugar para dividir. Estoy seguro de que probablemente haya mejores formas de llegar a esta solución, especialmente en torno a las estructuras de datos elegidas, pero esto es un comienzo. Planeo refinar las cosas más tarde.

#light 
open System 

let trainList = 
    [ 
    [1.;0.;0.;1.;]; 
    [0.;1.;0.;1.;]; 
    [0.;0.;0.;0.;]; 
    [1.;0.;1.;0.;]; 
    [0.;0.;0.;0.;]; 
    [1.;1.;0.;1.;]; 
    [0.;1.;1.;0.;]; 
    [1.;0.;0.;1.;]; 
    [0.;0.;0.;0.;]; 
    [1.;0.;0.;1.;]; 
    ] 

type BinaryTree = 
    | Leaf of int 
    | Node of int * string * BinaryTree * BinaryTree 

let entropyList nums = 
    let sumOfnums = 
     nums 
     |> Seq.sum 
    nums 
    |> Seq.map (fun x -> if x=0.00 then x else (-((x/sumOfnums) * Math.Log(x/sumOfnums, 2.)))) 
    |> Seq.sum 

let entropyBinaryList (dataListOfLists:list<list<float>>) = 
    let classList = 
     dataListOfLists 
     |> List.map (fun x -> x.Item(x.Length - 1)) 
    let ListOfNo = 
     classList 
     |> List.choose (fun x -> if x = 0. then Some(x) else None) 
    let ListOfYes = 
     classList 
     |> List.choose (fun x -> if x = 1. then Some(x) else None) 
    let numberOfYes : float = float ListOfYes.Length 
    let numberOfNo : float = float ListOfNo.Length 
    let ListOfNumYesAndSumNo = [numberOfYes; numberOfNo] 
    entropyList ListOfNumYesAndSumNo 

let conditionalEntropy (dataListOfLists:list<list<float>>) attributeNumber = 
    let NoAttributeList = 
     dataListOfLists 
     |> List.choose (fun x -> if x.Item(attributeNumber) = 0. then Some(x) else None) 
    let YesAttributeList = 
     dataListOfLists 
     |> List.choose (fun x -> if x.Item(attributeNumber) = 1. then Some(x) else None) 
    let numberOfYes : float = float YesAttributeList.Length 
    let numberOfNo : float = float NoAttributeList.Length 
    let noConditionalEntropy = (entropyBinaryList NoAttributeList) * (numberOfNo/(numberOfNo + numberOfYes)) 
    let yesConditionalEntropy = (entropyBinaryList YesAttributeList) * (numberOfYes/(numberOfNo + numberOfYes)) 
    [noConditionalEntropy; yesConditionalEntropy] 

let findBestSplitIndex(listOfInstances : list<list<float>>) = 
    let IGList = 
     [0..(listOfInstances.Item(0).Length - 2)] 
     |> List.mapi (fun i x -> (i, (entropyBinaryList listOfInstances) - (List.sum (conditionalEntropy listOfInstances x)))) 
    IGList 
    |> List.maxBy snd 
    |> fst 

let isListPure (listToCheck : list<list<float>>) = 
    let splitList = listToCheck |> List.choose (fun x -> if x.Item(x.Length - 1) = 1. then Some(x) else None) 
    if splitList.Length = listToCheck.Length then 1 
    else if splitList.Length = 0 then 0 
    else -1 

let rec createTree (listToSplit : list<list<float>>) = 
     let pureCheck = isListPure listToSplit 
     if pureCheck = 0 then 
      printfn "%s" "Pure - Leaf(0)" 
     else if pureCheck = 1 then 
      printfn "%s" "Pure - Leaf(1)" 
     else 
      printfn "%A - is not pure" listToSplit 
      if listToSplit.Length > 1 then // There are attributes we can split on 
       // Chose best place to split list 
       let splitIndex = findBestSplitIndex(listToSplit) 
       printfn "spliting at index %A" splitIndex 
       let leftSideSplit = 
        listToSplit |> List.choose (fun x -> if x.Item(splitIndex) = 1. then Some(x) else None) 
       let rightSideSplit = 
        listToSplit |> List.choose (fun x -> if x.Item(splitIndex) = 0. then Some(x) else None) 
       createTree leftSideSplit 
       createTree rightSideSplit 
      else 
       printfn "%s" "Not Pure, but can't split choose based on heuristics - Leaf(0 or 1)"