packages feed

DecisionTree (empty) → 0.0

raw patch · 16 files changed

+1046/−0 lines, 16 filesdep +basedep +containerssetup-changedbinary-added

Dependencies added: base, containers

Files

+ Data/DecisionTree.hs view
@@ -0,0 +1,134 @@+-- | This module provides a very simple implementation of a decisiontree. It is \"optimized\" for readability, not so much for performance. I doubt it can be used for real (=huge) datasets, but it should be ok for a couple of hundred (thousand?) items.+-- +-- You are encouraged to have a look at the source+-- +-- It is build (for now) using the ID3 algorithm (or at least something closely resembling that). That means the attributes you choose must have a finite set of possible values.+module Data.DecisionTree (+    build,+    decide,+    Datum(D, dName, attributes),+    PreLabeled,+    Attribute(A, aName, possibleValues),+    DecisionTree) where++import Data.Maybe (fromJust)+import Data.List hiding (partition)+import Data.Map (Map)+import qualified Data.Map as Map+import Data.Function (on)++type PreLabeled a b= (b, Datum a)++-- | The type for our DecisionTree+data DecisionTree a b= Leaf b -- ^ Leafs have labels+    | Node { +        att ::Attribute a, -- ^ a node asks for this attribute+        child :: a -> (DecisionTree a b) -- ^ and has children which can be found with a value of the attribute+        }++-- | A Datum has Attributes+data Attribute a = A {+    aName :: String, -- ^ Attributes have a name+    possibleValues ::  [a] -- ^ and a set of possible values+    } ++-- | Things we want to find labels for+data Datum a= D {+    dName :: String, -- ^ They have names+    attributes :: [(Attribute a,a)] -- ^ and attributes+    } deriving Show++instance (Show a, Show b) => Show (DecisionTree a b) where+    show x = showTree x ""++showTree :: (Show a, Show b) => DecisionTree a b -> ShowS+showTree (Leaf x) = shows x+showTree (Node att child) = ('<':).shows att.("|\n"++).showList [child a | a <- possibleValues att].('>':)++instance Eq (Attribute a) where+    (==) = (==) `on` aName+    +instance Show (Attribute a) where+    show = aName+    +-- | Build a DecisionTree from the given Trainingset+build :: (Ord a, Ord b) => [Attribute a] -> [PreLabeled a b] -> DecisionTree a b+build atts dataset =  case inf of+    0 -> Leaf dominantLabel -- even the best Attribute doesn't gain any information. We're done+    _ -> Node { +        att = bAtt,+        child = safeLookup+        } +    where+            (inf,bAtt) = bestAttribute dataset atts -- get the best attribute+            p =  partition dataset bAtt -- use it to partition the set+            children = Map.map (build atts) p -- recursivly build the children+            dominantLabel = fst $ Map.findMax $ groupLabels (map label dataset) -- in case we are done, get the label+            safeLookup a= fromJust $ Map.lookup a children+            +                 +-- | Which value does this Datum have for the given Attribute?+getValue :: Datum a-> Attribute a ->  a+getValue d att = fromJust $ lookup att (attributes d)++-- | Extract a label +label :: PreLabeled a b -> b+label = fst++-- | Decide which label belongs to this Datum+decide :: Eq a => DecisionTree a b -> Datum a -> b+decide (Leaf b) _ = b -- we reached a Leaf, done+decide (Node att child) d = decide (child v) d where -- we're in a node, walk down+    v = getValue d att+    +-- | Partitions the Dataset according to the possible values of the attribute+partition :: (Ord a) =>[PreLabeled a b] -> Attribute a -> Map a [PreLabeled a b]+partition set att= foldl (\m k -> Map.insertWith (++) k [] m) grouped (possibleValues att)  where+    grouped = groupWith (flip getValue att.snd) (:[]) (++) set++-- | Computes the entropy of a Dataset+--+-- the Entropy is defined as: sum (p_i * log_2 p_i)+-- where p_i = |{ x | x has Label i}|/|Dataset|+entropy :: (Ord b) => [b] -> Double+entropy set= (-1)*(  Map.fold help 0 $ groupLabels set )+    where +        n = fromIntegral $ length set+        help s acc | s/=0 = let p = fromIntegral s / n in acc+p*log p/log 2+        help _ _ = error "entropy: we are not supposed to get p=0"++-- we want to count how many Data we have for each label. Thus we group it with 1 as +-- singleton value and add 1 whenever we find another Datum with the same label       +groupLabels :: Ord b => [b] -> Map b Int +groupLabels = groupWith id (const (1::Int)) (const succ)++-- | How much information does this Attribute give us for the given Dataset+-- it is defined as +--+-- entropy(set) - sum p_i * entropy {dat_i | dat has value i for attribute a}+information :: (Ord b, Ord a) =>  [PreLabeled a b] -- ^ the data+    -> Attribute a -- ^ the Attribute +    -> Double -- ^ the Information+information dat att= entropy (map label dat) - sum (zipWith (*) pi (map entropy ps)) where+    ps = map (map label) $ Map.elems $ partition dat att -- the partitions, we're only interested in the labels+    pi = map ((/ n).fromIntegral.length) ps -- the size of the partition/size dataset+    n = fromIntegral $ length dat+    +-- | Return the attribute which gives us greatest gain in information+bestAttribute :: (Ord b, Ord a) => [PreLabeled a b] -> [Attribute a] -> (Double,Attribute a)+bestAttribute dat = head.sortBy (compare `on` negatedInf).computeInformation where+    negatedInf (inf,_) = -inf+    computeInformation = map (\x -> (information dat x,x))++-- | groups a Dataset using a Map. According to #haskell \"efficient\" grouping needs Ord. I agree with that+groupWith :: Ord k => (a -> k) -- ^ how to extract a key from a Datum+    -> (a -> v) -- ^ how to make a Datum into a value for the map+    -> (v -> v -> v) -- ^ how to fuse two values (should we have > 1 Data for this key)+    -> [a] -- ^ the list we want to group+    -> Map k v +groupWith getKey singleton fuse = +    foldl (\m x -> Map.insertWith fuse (getKey x) (singleton x) m) Map.empty+    ++    +
+ DecisionTree.cabal view
@@ -0,0 +1,21 @@+Name:                DecisionTree+Version:             0.0+Cabal-Version: >= 1.2+Synopsis:            A very simple implementation of decision trees for discrete attributes.+Description:         A very simple implementation of decision trees, built with ID3. You can use it to classify data with a set of discrete attributes.+License:             LGPL+License-file:        LICENSE+Author:              Adrian Neumann+Homepage:            http://page.mi.fu-berlin.de/~aneumann/decisiontree.html+Category:            Algorithms, Pattern Classification+Maintainer:          aneumann@inf.fu-berlin.de+stability:           alpha+build-type:          Simple+extra-source-files:  README, test.hs, lgpl-3.0.txt++Library+    exposed-modules:     Data.DecisionTree+    build-depends: +         base, +         containers >=0.2.0.0+    GHC-Options:    -O2
+ LICENSE view
@@ -0,0 +1,3 @@+Copyright 2009 Adrian Neumann++You may use this library under the terms of the LGPL, which is included in the file lgpl-3.0.txt
+ README view
@@ -0,0 +1,4 @@+This is the DecisionTree library. +Build it as you would build any cabal package. Have a look at the Haskellwiki (haskell.org) if you don't know how.++Feel free to send me patches, comments, suggestions.
+ Setup.lhs view
@@ -0,0 +1,4 @@+#! /usr/bin/env runhaskell+ +> import Distribution.Simple+> main = defaultMain
+ dist/doc/html/DecisionTree/Data-DecisionTree.html view

binary file changed (absent → 20738 bytes)

+ dist/doc/html/DecisionTree/DecisionTree.haddock view

binary file changed (absent → 5224 bytes)

+ dist/doc/html/DecisionTree/doc-index.html view
@@ -0,0 +1,150 @@+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">+<!--Rendered using the Haskell Html Library v0.2-->+<HTML+><HEAD+><META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=UTF-8"+><TITLE+>DecisionTree-0.0: A very simple implementation of decision trees for discrete attributes. (internal documentation) (Index)</TITLE+><LINK HREF="haddock.css" REL="stylesheet" TYPE="text/css"+><SCRIPT SRC="haddock-util.js" TYPE="text/javascript"+></SCRIPT+></HEAD+><BODY+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD CLASS="topbar"+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD+><IMG SRC="haskell_icon.gif" WIDTH="16" HEIGHT="16" ALT=" "+></TD+><TD CLASS="title"+>DecisionTree-0.0: A very simple implementation of decision trees for discrete attributes. (internal documentation)</TD+><TD CLASS="topbut"+><A HREF="index.html"+>Contents</A+></TD+><TD CLASS="topbut"+><A HREF="doc-index.html"+>Index</A+></TD+></TR+></TABLE+></TD+></TR+><TR+><TD COLSPAN="2" STYLE="padding-top:5px;"+><FORM onsubmit="full_search(); return false;" ACTION=""+>Search: <INPUT ID="searchbox" onkeyup="quick_search()"+> <INPUT VALUE="Search" TYPE="submit"+> <SPAN ID="searchmsg"+> </SPAN+></FORM+></TD+></TR+><TR+><TD+><TABLE ID="indexlist" CELLPADDING="0" CELLSPACING="5"+><TR CLASS="indexrow"+><TD CLASS="indexentry"+>A</TD+><TD CLASS="indexlinks"+><A HREF="Data-DecisionTree.html#v%3AA"+>Data.DecisionTree</A+></TD+></TR+><TR CLASS="indexrow"+><TD CLASS="indexentry"+>aName</TD+><TD CLASS="indexlinks"+><A HREF="Data-DecisionTree.html#v%3AaName"+>Data.DecisionTree</A+></TD+></TR+><TR CLASS="indexrow"+><TD CLASS="indexentry"+>Attribute</TD+><TD CLASS="indexlinks"+><A HREF="Data-DecisionTree.html#t%3AAttribute"+>Data.DecisionTree</A+></TD+></TR+><TR CLASS="indexrow"+><TD CLASS="indexentry"+>attributes</TD+><TD CLASS="indexlinks"+><A HREF="Data-DecisionTree.html#v%3Aattributes"+>Data.DecisionTree</A+></TD+></TR+><TR CLASS="indexrow"+><TD CLASS="indexentry"+>build</TD+><TD CLASS="indexlinks"+><A HREF="Data-DecisionTree.html#v%3Abuild"+>Data.DecisionTree</A+></TD+></TR+><TR CLASS="indexrow"+><TD CLASS="indexentry"+>D</TD+><TD CLASS="indexlinks"+><A HREF="Data-DecisionTree.html#v%3AD"+>Data.DecisionTree</A+></TD+></TR+><TR CLASS="indexrow"+><TD CLASS="indexentry"+>Datum</TD+><TD CLASS="indexlinks"+><A HREF="Data-DecisionTree.html#t%3ADatum"+>Data.DecisionTree</A+></TD+></TR+><TR CLASS="indexrow"+><TD CLASS="indexentry"+>decide</TD+><TD CLASS="indexlinks"+><A HREF="Data-DecisionTree.html#v%3Adecide"+>Data.DecisionTree</A+></TD+></TR+><TR CLASS="indexrow"+><TD CLASS="indexentry"+>DecisionTree</TD+><TD CLASS="indexlinks"+><A HREF="Data-DecisionTree.html#t%3ADecisionTree"+>Data.DecisionTree</A+></TD+></TR+><TR CLASS="indexrow"+><TD CLASS="indexentry"+>dName</TD+><TD CLASS="indexlinks"+><A HREF="Data-DecisionTree.html#v%3AdName"+>Data.DecisionTree</A+></TD+></TR+><TR CLASS="indexrow"+><TD CLASS="indexentry"+>possibleValues</TD+><TD CLASS="indexlinks"+><A HREF="Data-DecisionTree.html#v%3ApossibleValues"+>Data.DecisionTree</A+></TD+></TR+><TR CLASS="indexrow"+><TD CLASS="indexentry"+>PreLabeled</TD+><TD CLASS="indexlinks"+><A HREF="Data-DecisionTree.html#t%3APreLabeled"+>Data.DecisionTree</A+></TD+></TR+></TABLE+></TD+></TR+></TABLE+></BODY+></HTML+>
+ dist/doc/html/DecisionTree/haddock-util.js view
@@ -0,0 +1,133 @@+// Haddock JavaScript utilities+function toggle(button,id)+{+   var n = document.getElementById(id).style;+   if (n.display == "none")+   {+    button.src = "minus.gif";+    n.display = "block";+   }+   else+   {+    button.src = "plus.gif";+    n.display = "none";+   }+}+++var max_results = 75; // 50 is not enough to search for map in the base libraries+var shown_range = null;+var last_search = null;++function quick_search()+{+    perform_search(false);+}++function full_search()+{+    perform_search(true);+}+++function perform_search(full)+{+    var text = document.getElementById("searchbox").value.toLowerCase();+    if (text == last_search && !full) return;+    last_search = text;+    +    var table = document.getElementById("indexlist");+    var status = document.getElementById("searchmsg");+    var children = table.firstChild.childNodes;+    +    // first figure out the first node with the prefix+    var first = bisect(-1);+    var last = (first == -1 ? -1 : bisect(1));++    if (first == -1)+    {+        table.className = "";+        status.innerHTML = "No results found, displaying all";+    }+    else if (first == 0 && last == children.length - 1)+    {+        table.className = "";+        status.innerHTML = "";+    }+    else if (last - first >= max_results && !full)+    {+        table.className = "";+        status.innerHTML = "More than " + max_results + ", press Search to display";+    }+    else+    {+        // decide what you need to clear/show+        if (shown_range)+            setclass(shown_range[0], shown_range[1], "indexrow");+        setclass(first, last, "indexshow");+        shown_range = [first, last];+        table.className = "indexsearch";+        status.innerHTML = "";+    }++    +    function setclass(first, last, status)+    {+        for (var i = first; i <= last; i++)+        {+            children[i].className = status;+        }+    }+    +    +    // do a binary search, treating 0 as ...+    // return either -1 (no 0's found) or location of most far match+    function bisect(dir)+    {+        var first = 0, finish = children.length - 1;+        var mid, success = false;++        while (finish - first > 3)+        {+            mid = Math.floor((finish + first) / 2);++            var i = checkitem(mid);+            if (i == 0) i = dir;+            if (i == -1)+                finish = mid;+            else+                first = mid;+        }+        var a = (dir == 1 ? first : finish);+        var b = (dir == 1 ? finish : first);+        for (var i = b; i != a - dir; i -= dir)+        {+            if (checkitem(i) == 0) return i;+        }+        return -1;+    }    +    +    +    // from an index, decide what the result is+    // 0 = match, -1 is lower, 1 is higher+    function checkitem(i)+    {+        var s = getitem(i).toLowerCase().substr(0, text.length);+        if (s == text) return 0;+        else return (s > text ? -1 : 1);+    }+    +    +    // from an index, get its string+    // this abstracts over alternates+    function getitem(i)+    {+        for ( ; i >= 0; i--)+        {+            var s = children[i].firstChild.firstChild.data;+            if (s.indexOf(' ') == -1)+                return s;+        }+        return ""; // should never be reached+    }+}
+ dist/doc/html/DecisionTree/haddock.css view
@@ -0,0 +1,267 @@+/* -------- Global things --------- */++BODY { +  background-color: #ffffff;+  color: #000000;+  font-family: sans-serif;+  } ++A:link    { color: #0000e0; text-decoration: none }+A:visited { color: #0000a0; text-decoration: none }+A:hover   { background-color: #e0e0ff; text-decoration: none }++TABLE.vanilla {+  width: 100%;+  border-width: 0px;+  /* I can't seem to specify cellspacing or cellpadding properly using CSS... */+}++TABLE.vanilla2 {+  border-width: 0px;+}++/* <TT> font is a little too small in MSIE */+TT  { font-size: 100%; }+PRE { font-size: 100%; }++LI P { margin: 0pt } ++TD {+  border-width: 0px;+}++TABLE.narrow {+  border-width: 0px;+}++TD.s8  {  height: 8px;  }+TD.s15 {  height: 15px; }++SPAN.keyword { text-decoration: underline; }++/* Resize the buttom image to match the text size */+IMG.coll { width : 0.75em; height: 0.75em; margin-bottom: 0; margin-right: 0.5em }++/* --------- Contents page ---------- */++DIV.node {+  padding-left: 3em;+}++DIV.cnode {+  padding-left: 1.75em;+}++SPAN.pkg {+  position: absolute;+  left: 50em;+}++/* --------- Documentation elements ---------- */++TD.children {+  padding-left: 25px;+  }++TD.synopsis {+  padding: 2px;+  background-color: #f0f0f0;+  font-family: monospace+ }++TD.decl { +  padding: 2px;+  background-color: #f0f0f0; +  font-family: monospace;+  vertical-align: top;+  }++TD.topdecl {+  padding: 2px;+  background-color: #f0f0f0;+  font-family: monospace;+  vertical-align: top;+}++TABLE.declbar {+  border-spacing: 0px;+ }++TD.declname {+  width: 100%;+ }++TD.declbut {+  padding-left: 5px;+  padding-right: 5px;+  border-left-width: 1px;+  border-left-color: #000099;+  border-left-style: solid;+  white-space: nowrap;+  font-size: small;+ }++/* +  arg is just like decl, except that wrapping is not allowed.  It is+  used for function and constructor arguments which have a text box+  to the right, where if wrapping is allowed the text box squashes up+  the declaration by wrapping it.+*/+TD.arg { +  padding: 2px;+  background-color: #f0f0f0; +  font-family: monospace;+  vertical-align: top;+  white-space: nowrap;+  }++TD.recfield { padding-left: 20px }++TD.doc  { +  padding-top: 2px;+  padding-left: 10px;+  }++TD.ndoc  { +  padding: 2px;+  }++TD.rdoc  { +  padding: 2px;+  padding-left: 10px;+  width: 100%;+  }++TD.body  { +  padding-left: 10px+  }++TD.pkg {+  width: 100%;+  padding-left: 10px+}++TABLE.indexsearch TR.indexrow {+  display: none;+}+TABLE.indexsearch TR.indexshow {+  display: table-row;+}++TD.indexentry {+  vertical-align: top;+  padding-right: 10px+  }++TD.indexannot {+  vertical-align: top;+  padding-left: 20px;+  white-space: nowrap+  }++TD.indexlinks {+  width: 100%+  }++/* ------- Section Headings ------- */++TD.section1 {+  padding-top: 15px;+  font-weight: bold;+  font-size: 150%+  }++TD.section2 {+  padding-top: 10px;+  font-weight: bold;+  font-size: 130%+  }++TD.section3 {+  padding-top: 5px;+  font-weight: bold;+  font-size: 110%+  }++TD.section4 {+  font-weight: bold;+  font-size: 100%+  }++/* -------------- The title bar at the top of the page */++TD.infohead {+  color: #ffffff;+  font-weight: bold;+  padding-right: 10px;+  text-align: left;+}++TD.infoval {+  color: #ffffff;+  padding-right: 10px;+  text-align: left;+}++TD.topbar {+  background-color: #000099;+  padding: 5px;+}++TD.title {+  color: #ffffff;+  padding-left: 10px;+  width: 100%+  }++TD.topbut {+  padding-left: 5px;+  padding-right: 5px;+  border-left-width: 1px;+  border-left-color: #ffffff;+  border-left-style: solid;+  white-space: nowrap;+  }++TD.topbut A:link {+  color: #ffffff+  }++TD.topbut A:visited {+  color: #ffff00+  }++TD.topbut A:hover {+  background-color: #6060ff;+  }++TD.topbut:hover {+  background-color: #6060ff+  }++TD.modulebar { +  background-color: #0077dd;+  padding: 5px;+  border-top-width: 1px;+  border-top-color: #ffffff;+  border-top-style: solid;+  }++/* --------- The page footer --------- */++TD.botbar {+  background-color: #000099;+  color: #ffffff;+  padding: 5px+  }+TD.botbar A:link {+  color: #ffffff;+  text-decoration: underline+  }+TD.botbar A:visited {+  color: #ffff00+  }+TD.botbar A:hover {+  background-color: #6060ff+  }+
+ dist/doc/html/DecisionTree/haskell_icon.gif view

binary file changed (absent → 911 bytes)

+ dist/doc/html/DecisionTree/index.html view
@@ -0,0 +1,92 @@+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">+<!--Rendered using the Haskell Html Library v0.2-->+<HTML+><HEAD+><META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=UTF-8"+><TITLE+>DecisionTree-0.0: A very simple implementation of decision trees for discrete attributes. (internal documentation)</TITLE+><LINK HREF="haddock.css" REL="stylesheet" TYPE="text/css"+><SCRIPT SRC="haddock-util.js" TYPE="text/javascript"+></SCRIPT+></HEAD+><BODY+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD CLASS="topbar"+><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0"+><TR+><TD+><IMG SRC="haskell_icon.gif" WIDTH="16" HEIGHT="16" ALT=" "+></TD+><TD CLASS="title"+>DecisionTree-0.0: A very simple implementation of decision trees for discrete attributes. (internal documentation)</TD+><TD CLASS="topbut"+><A HREF="index.html"+>Contents</A+></TD+><TD CLASS="topbut"+><A HREF="doc-index.html"+>Index</A+></TD+></TR+></TABLE+></TD+></TR+><TR+><TD CLASS="section1"+>DecisionTree-0.0: A very simple implementation of decision trees for discrete attributes. (internal documentation)</TD+></TR+><TR+><TD CLASS="doc"+>A very simple implementation of decision trees, built with ID3. You can use it to classify data with a set of discrete attributes.+</TD+></TR+><TR+><TD CLASS="section1"+>Modules</TD+></TR+><TR+><TD+><TABLE CLASS="vanilla2" CELLSPACING="0" CELLPADDING="0"+><TR+><TD STYLE="width: 50em"+><IMG SRC="minus.gif" CLASS="coll" ONCLICK="toggle(this,'n:0')" ALT="show/hide"+>Data</TD+><TD+></TD+><TD+></TD+></TR+><TR+><TD STYLE="padding: 0; padding-left: 2em" COLSPAN="3"+><TABLE CLASS="vanilla2" CELLSPACING="0" CELLPADDING="0" ID="n:0" STYLE="display:block;"+><TR+><TD STYLE="padding-left: 1.25em;width: 48em"+><A HREF="Data-DecisionTree.html"+>Data.DecisionTree</A+></TD+><TD+></TD+><TD+></TD+></TR+></TABLE+></TD+></TR+></TABLE+></TD+></TR+><TR+><TD CLASS="s15"+></TD+></TR+><TR+><TD CLASS="botbar"+>Produced by <A HREF="http://www.haskell.org/haddock/"+>Haddock</A+> version 2.3.0</TD+></TR+></TABLE+></BODY+></HTML+>
+ dist/doc/html/DecisionTree/minus.gif view

binary file changed (absent → 56 bytes)

+ dist/doc/html/DecisionTree/plus.gif view

binary file changed (absent → 59 bytes)

+ lgpl-3.0.txt view
@@ -0,0 +1,165 @@+		   GNU LESSER GENERAL PUBLIC LICENSE+                       Version 3, 29 June 2007++ Copyright (C) 2007 Free Software Foundation, Inc. <http://fsf.org/>+ Everyone is permitted to copy and distribute verbatim copies+ of this license document, but changing it is not allowed.+++  This version of the GNU Lesser General Public License incorporates+the terms and conditions of version 3 of the GNU General Public+License, supplemented by the additional permissions listed below.++  0. Additional Definitions. ++  As used herein, "this License" refers to version 3 of the GNU Lesser+General Public License, and the "GNU GPL" refers to version 3 of the GNU+General Public License.++  "The Library" refers to a covered work governed by this License,+other than an Application or a Combined Work as defined below.++  An "Application" is any work that makes use of an interface provided+by the Library, but which is not otherwise based on the Library.+Defining a subclass of a class defined by the Library is deemed a mode+of using an interface provided by the Library.++  A "Combined Work" is a work produced by combining or linking an+Application with the Library.  The particular version of the Library+with which the Combined Work was made is also called the "Linked+Version".++  The "Minimal Corresponding Source" for a Combined Work means the+Corresponding Source for the Combined Work, excluding any source code+for portions of the Combined Work that, considered in isolation, are+based on the Application, and not on the Linked Version.++  The "Corresponding Application Code" for a Combined Work means the+object code and/or source code for the Application, including any data+and utility programs needed for reproducing the Combined Work from the+Application, but excluding the System Libraries of the Combined Work.++  1. Exception to Section 3 of the GNU GPL.++  You may convey a covered work under sections 3 and 4 of this License+without being bound by section 3 of the GNU GPL.++  2. Conveying Modified Versions.++  If you modify a copy of the Library, and, in your modifications, a+facility refers to a function or data to be supplied by an Application+that uses the facility (other than as an argument passed when the+facility is invoked), then you may convey a copy of the modified+version:++   a) under this License, provided that you make a good faith effort to+   ensure that, in the event an Application does not supply the+   function or data, the facility still operates, and performs+   whatever part of its purpose remains meaningful, or++   b) under the GNU GPL, with none of the additional permissions of+   this License applicable to that copy.++  3. Object Code Incorporating Material from Library Header Files.++  The object code form of an Application may incorporate material from+a header file that is part of the Library.  You may convey such object+code under terms of your choice, provided that, if the incorporated+material is not limited to numerical parameters, data structure+layouts and accessors, or small macros, inline functions and templates+(ten or fewer lines in length), you do both of the following:++   a) Give prominent notice with each copy of the object code that the+   Library is used in it and that the Library and its use are+   covered by this License.++   b) Accompany the object code with a copy of the GNU GPL and this license+   document.++  4. Combined Works.++  You may convey a Combined Work under terms of your choice that,+taken together, effectively do not restrict modification of the+portions of the Library contained in the Combined Work and reverse+engineering for debugging such modifications, if you also do each of+the following:++   a) Give prominent notice with each copy of the Combined Work that+   the Library is used in it and that the Library and its use are+   covered by this License.++   b) Accompany the Combined Work with a copy of the GNU GPL and this license+   document.++   c) For a Combined Work that displays copyright notices during+   execution, include the copyright notice for the Library among+   these notices, as well as a reference directing the user to the+   copies of the GNU GPL and this license document.++   d) Do one of the following:++       0) Convey the Minimal Corresponding Source under the terms of this+       License, and the Corresponding Application Code in a form+       suitable for, and under terms that permit, the user to+       recombine or relink the Application with a modified version of+       the Linked Version to produce a modified Combined Work, in the+       manner specified by section 6 of the GNU GPL for conveying+       Corresponding Source.++       1) Use a suitable shared library mechanism for linking with the+       Library.  A suitable mechanism is one that (a) uses at run time+       a copy of the Library already present on the user's computer+       system, and (b) will operate properly with a modified version+       of the Library that is interface-compatible with the Linked+       Version. ++   e) Provide Installation Information, but only if you would otherwise+   be required to provide such information under section 6 of the+   GNU GPL, and only to the extent that such information is+   necessary to install and execute a modified version of the+   Combined Work produced by recombining or relinking the+   Application with a modified version of the Linked Version. (If+   you use option 4d0, the Installation Information must accompany+   the Minimal Corresponding Source and Corresponding Application+   Code. If you use option 4d1, you must provide the Installation+   Information in the manner specified by section 6 of the GNU GPL+   for conveying Corresponding Source.)++  5. Combined Libraries.++  You may place library facilities that are a work based on the+Library side by side in a single library together with other library+facilities that are not Applications and are not covered by this+License, and convey such a combined library under terms of your+choice, if you do both of the following:++   a) Accompany the combined library with a copy of the same work based+   on the Library, uncombined with any other library facilities,+   conveyed under the terms of this License.++   b) Give prominent notice with the combined library that part of it+   is a work based on the Library, and explaining where to find the+   accompanying uncombined form of the same work.++  6. Revised Versions of the GNU Lesser General Public License.++  The Free Software Foundation may publish revised and/or new versions+of the GNU Lesser General Public License from time to time. Such new+versions will be similar in spirit to the present version, but may+differ in detail to address new problems or concerns.++  Each version is given a distinguishing version number. If the+Library as you received it specifies that a certain numbered version+of the GNU Lesser General Public License "or any later version"+applies to it, you have the option of following the terms and+conditions either of that published version or of any later version+published by the Free Software Foundation. If the Library as you+received it does not specify a version number of the GNU Lesser+General Public License, you may choose any version of the GNU Lesser+General Public License ever published by the Free Software Foundation.++  If the Library as you received it specifies that a proxy can decide+whether future versions of the GNU Lesser General Public License shall+apply, that proxy's public statement of acceptance of any version is+permanent authorization for you to choose that version for the+Library.
+ test.hs view
@@ -0,0 +1,73 @@+import Data.DecisionTree++decideProp = (map (decide tree) unlabeled) == labels where+    tree = build atts dataset+++outlook = A { aName = "outlook", possibleValues=["sunny", "overcast", "rainy"] }+temperature = A { aName ="temperature", possibleValues=["hot","mild", "cool"] }+humidity = A { aName ="humidity", possibleValues=["high","normal"] }+windy = A { aName ="windy", possibleValues=["true","false"]}++atts = [outlook,temperature,humidity,windy]++dataset = zip labels unlabeled+labels = ["no","no","yes","yes","yes","no","yes","no","yes","yes","yes","yes","yes","no"]+unlabeled = +    [D { dName = "", attributes = [(outlook,"sunny"), +            (temperature,"hot"), +            (humidity,"high"),+            (windy,"false")]},+    D { dName = "", attributes = [(outlook,"sunny"), +        (temperature,"hot"), +        (humidity, "high"), +        (windy,"true")]},+    D { dName = "", attributes = [(outlook,"overcast"),+        (temperature,"hot"), +        (humidity, "high"), +        (windy, "false")]},+    D { dName = "", attributes = [(outlook,"rainy"), +        (temperature,"mild"), +        (humidity, "high"), +        (windy,"false")]},+    D { dName = "", attributes = [(outlook,"rainy"), +        (temperature, "cool"), +        (humidity, "normal"), +        (windy,"false")]},+    D { dName = "", attributes = [(outlook, "rainy"), +        (temperature,"cool"), +        (humidity, "normal"), +        (windy, "true")]},+    D { dName = "", attributes = [(outlook, "overcast"), +        (temperature, "cool"), +        (humidity, "normal"), +        (windy,"true")]},+    D { dName = "", attributes = [(outlook, "sunny"), +        (temperature, "mild"), +        (humidity, "high"), +        (windy, "false")]},+    D { dName = "", attributes = [(outlook, "sunny"), +        (temperature, "cool"), +        (humidity, "normal"), +        (windy, "false")]},+    D { dName = "", attributes = [(outlook, "rainy"), +        (temperature, "mild"), +        (humidity, "normal"), +        (windy, "false")]},+    D { dName = "", attributes = [(outlook, "sunny"), +        (temperature, "mild"), +        (humidity, "normal"), +        (windy, "true")]},+    D { dName = "", attributes = [(outlook, "overcast"), +        (temperature, "mild"), +        (humidity, "high"), +        (windy, "true")]},+    D { dName = "", attributes = [(outlook, "overcast"), +        (temperature, "hot"), +        (humidity, "normal"), +        (windy, "false")]},+    D { dName = "", attributes = [(outlook, "rainy"), +        (temperature, "mild"), +        (humidity, "high"), +        (windy,"true")]}]+