助けを必要とする真理を与えられた2進木の作成表

Question

最初に、完全な開示を提供するために、これは機械学習クラスの宿題に関連していることを指摘したいと思います。この質問は宿題に関する質問ではなく、代わりにID3決定木アルゴリズムを作成する大きな問題を完了するために把握する必要があるものです。

私はlearnedTreeは次のように私が定義したどのタイプのBinaryTreeのある

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

真理値表が与えられたときに、次のようなツリーを生成する必要が

：

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

ねえジムは、私はしばらくの間、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 

Answer 2

2つのList.choose呼び出しの代わりにList.partitionを使用できます。

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）それは私には明確ではない

そのパターンマッチングはずっとここにあなたを購入します。入力タイプ（リストのリスト）と処理（パーティショニングと「純粋さ」のチェック）は、実際にそれに役立たない。

もちろん、最終的に「終わり」（純粋なリスト）を取得すると、ツリーを作成する必要があります。入力が「側」と「純粋」である場合、この関数はリーフを作成します。それ以外の入力ごとに左側と右側の結果からノードを作成します。多分。私は完全にアルゴリズムをgrokしなかった。

うまくいけば、それはあなたを少し助けてくれるでしょう。関数本体のさまざまなケースを理解するのに役立つ少数のサンプル入力と出力を作成すると便利です。

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