需要帮助根据真值表创建二叉树

首先，为了充分披露，我想指出这与机器学习课程中的作业有关。这个问题不是家庭作业问题，而是我需要解决的问题，以便完成创建 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"

我应该使用模式匹配吗？有什么建议/想法/帮助吗？非常感谢！

Edit：我已经在我的博客上发布了 ID3 的实现：http://blogs.msdn.com/chrsmith http://blogs.msdn.com/chrsmith/archive/2009/11/02/awesome-f-decision-trees-part-ii.aspx

嘿 Jim，我一直想写一篇在 F# 中实现 ID3 的博客文章 - 感谢您给我一个执行机会。虽然此代码未完整（或正确）实现算法，但它应该足以让您入门。

一般来说，您有正确的方法 - 将每个分支表示为受歧视的联合案例是好的。正如 Brian 所说，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