Нужна помощь в создании бинарного дерева с заданной таблицей правды

Question

Во-первых, чтобы обеспечить полное раскрытие, я хочу отметить, что это связано с домашней работой в классе машинного обучения. Этот вопрос не является вопросом домашней работы, и мне нужно разобраться с ним, чтобы решить более сложную задачу создания алгоритма дерева решений ID3.

Мне нужно сгенерировать дерево, похожее на следующее, когда дана таблица истинности

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

learnTree имеет тип BinaryTree, который я определил следующим образом:

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

Алгоритмы ID3 учитывают различные уравнения, чтобы определить, где разбить дерево, и я понял все, что у меня возникло, просто у меня возникают проблемы при создании изученного дерева из моей таблицы истинности. Например, если у меня есть следующая таблица

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

И я решу разделить атрибут A1, в результате я получу следующее:

              (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

Затем я разделил бы левую сторону и разделил правую сторону и продолжил рекурсивный шаблон, пока узлы листа не стали бы чистыми, и в результате я получил дерево, похожее на следующее, основанное на разбиении.

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

Вот то, что я вроде как "взломал" вместе до сих пор, но я думаю, что я могу быть далеко:

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"

Должен ли я вместо этого использовать сопоставление с образцом? Любые советы / идеи / помощь? Спасибо большое!

Answer 1

Редактировать : с тех пор я разместил реализацию ID3 в своем блоге по адресу: http://blogs.msdn.com/chrsmith

Привет, Джим, я давно хотел написать сообщение в блоге, в котором реализован ID3 на F # - спасибо, что дал мне выполнить. Хотя этот код не реализует алгоритм полностью (или правильно), этого должно быть достаточно для начала работы.

В целом у вас правильный подход - хорошо представлять каждую ветвь в качестве дискриминационного случая объединения. И, как сказал Брайан, List.partition - определенно удобная функция. Хитрость в том, чтобы заставить эту работу работать правильно, заключается в определении оптимальной пары атрибут / значение для разделения - и для этого вам нужно рассчитать прирост информации посредством энтропии и т.д.

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

Вы можете использовать List.partition вместо двух вызовов List.choose.

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

(или сейчас http://msdn.microsoft.com/en-us/library/ee353738(VS.100).aspx)

Мне не ясно, что сопоставление с образцом здесь много вам даст; тип ввода (список списков) и обработка (проверка разбиения и «чистоты») на самом деле не подходят для этого.

И, конечно, когда вы, наконец, получите «конец» (чистый список), вам нужно создать дерево, а затем, предположительно, эта функция создаст лист, когда вход имеет только одну «сторону» и он «чистый» но создайте Узел из результатов левой и правой сторон для каждого другого входа. Может быть. Я не совсем понял алгоритм полностью.

Надеюсь, это поможет вам немного помочь. Может быть полезно составить несколько небольших выборочных входов и выходов, чтобы помочь разобраться в различных случаях тела функции.

Answer 3

Спасибо, Брайан и Крис! Я был в состоянии понять это, и я получил следующее. Это рассчитывает выигрыш информации для определения лучшего места для разделения. Я уверен, что, возможно, есть лучшие способы для достижения этого решения, особенно в отношении выбранных структур данных, но это только начало. Я планирую уточнить вещи позже.

#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)"