सहायता की आवश्यकता एक बाइनरी वृक्ष को देखते हुए सत्य तालिका

Question

सबसे पहले, पूर्ण प्रकटीकरण प्रदान करने के लिए, मैं यह इंगित करना चाहता हूं कि यह मशीन लर्निंग क्लास में होमवर्क से संबंधित है। यह प्रश्न होमवर्क प्रश्न नहीं है और इसके बजाय आईडी 3 निर्णय ट्री एल्गोरिदम बनाने की बड़ी समस्या को पूरा करने के लिए मुझे कुछ पता लगाने की आवश्यकता है।

मैं के समान पेड़ उत्पन्न करने के लिए की जरूरत है निम्नलिखित जब एक सच तालिका

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 प्रकार 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 को लागू करने में लिखने के लिए चाहता था - धन्यवाद मुझे निष्पादन देने के लिए। हालांकि यह कोड एल्गोरिदम को पूर्ण (या सही ढंग से) लागू नहीं करता है, यह आपको प्रारंभ करने के लिए पर्याप्त होना चाहिए।

आम तौर पर आपके पास सही दृष्टिकोण है - प्रत्येक शाखा का प्रतिनिधित्व एक भेदभावपूर्ण संघ के मामले के रूप में अच्छा है। और ब्रायन की तरह कहा, 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 का उपयोग कर सकते हैं। कॉल कॉल करें।

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