lojix/learning/src/main/com/thesett/aima/learning/decisiontree/prototype/ProtoDTLearningMethod.java
public ClassifyingMachine learn() throws LearningFailureException
    {
        /*log.fine("public ClassifyingMachine learn(): called");*/

        // Call the initialize method to ensure that input and output properties are correctly set up.
        initialize();

        // Check that there is only one output property to learn for. Decision trees can only output a single
        // property classification (although mutliple trees could be built for multiple properties).
        if (outputProperties.size() != 1)
        {
            throw new LearningFailureException(
                "Decision trees can only learn a classification for a single property, " + "but " +
                outputProperties.size() + " have been set as outputs.", null);
        }

        // Extract the single output property to learn for.
        String outputProperty = outputProperties.iterator().next();

        // Check that the output property to be learnt is one with a finite number of values. Decision trees
        // cannot learn infinite valued attributes, such as real numbers etc.
        int numValues =
            inputExamples.iterator().next().getComponentType().getPropertyType(outputProperty).getNumPossibleValues();

        if (numValues < 1)
        {
            throw new LearningFailureException("Decision trees can only learn a classification for a " +
                "property with a finite number of values. The property, " + outputProperty +
                " can have an infinite number of values and should be " +
                "discretized prior to being learned by decision trees.", null);
        }

        // Used to queue nodes that are pending construction.
        Queue<DecisionTree> pendingNodes = new LinkedList<DecisionTree>();

        // Create a pending node,(an empty tree, the examples, the attributes, the default classification).
        Pending startNode =
            new Pending(inputExamples, inputProperties, getMajorityClassification(outputProperty, inputExamples), null);

        // Create the root of the decision tree out of this start pending node.
        DecisionTree decisionTree = new DecisionTree(startNode);

        // Push this new pending node onto the construction queue.
        pendingNodes.offer(decisionTree);

        // Loop until the queue of nodes pending construction is empty.
        while (!pendingNodes.isEmpty())
        {
            /*log.fine("Got next pending node.");*/

            // Get the tree fragment for the next pending node. The data element should always be safe to cast to a
            // Pending node as this algorithm only pushes pending nodes onto the queue.
            DecisionTree currentTreePendingNode = pendingNodes.remove();
            DecisionTreeElement currentTreePendingNodeElement = currentTreePendingNode.getElement();
            Pending currentNode = (Pending) currentTreePendingNodeElement;

            // Extract the examples, the attributes, the default classification, and the attribute to be matched,
            // for this pending node.
            Collection<State> examples = currentNode.getExamples();
            Collection<String> undecidedProperties = currentNode.getUndecidedProperties();
            OrdinalAttribute defaultAttribute = currentNode.getDefault();
            OrdinalAttribute matchingAttribute = currentNode.getAttributeValue();

            /*log.fine("Pending node corresponds to " + examples.size() + " examples.");*/
            /*log.fine("Pending node has " + undecidedProperties.size() + " undecided properties left.");*/

            // Used to hold the decision tree fragment (decision node, pending node or assignment leaf) that will
            // be inserted into the decision tree to replace the current pending node.
            DecisionTree newTreeFragment = null;

            // If the set of examples is empty then set the default as the leaf.
            if (examples.isEmpty())
            {
                /*log.fine("Examples is empty.");*/
                newTreeFragment = new DecisionTree(new Assignment(outputProperty, defaultAttribute, matchingAttribute));
            }

            // Else if undecided properties is empty then set the majority value of the classification of
            // examples as the leaf.
            else if (undecidedProperties.isEmpty())
            {
                /*log.fine("No undecided properties left.");*/

                // Work out what the majority classification is and create a leaf with that assignment.
                OrdinalAttribute majority = getMajorityClassification(outputProperty, inputExamples);

                newTreeFragment = new DecisionTree(new Assignment(outputProperty, majority, matchingAttribute));
            }

            // Else if all the examples have the same classification then set that classification as the leaf.
            else if (allHaveSameClassification(outputProperty, examples))
            {
                /*log.fine("All examples have the same classification.");*/
                newTreeFragment =
                    new DecisionTree(new Assignment(outputProperty, allClassification, matchingAttribute));
            }

            // Else choose the best attribute (with the largest estimated information gain) on the classification.
            else
            {
                /*log.fine("Choosing the best property to split on.");*/

                String bestProperty = chooseBestPropertyToDecideOn(outputProperty, examples, inputProperties);

                // Check if a best property could not be found, in which case behave as if there are no
                // input properties left to work with.
                if (bestProperty == null)
                {
                    /*log.fine("Couldn't find a best property to split on.");*/

                    // Put the pending node back onto the construction queue but with zero input properties.
                    Pending newPendingNode =
                        new Pending(examples, new ArrayList<String>(), defaultAttribute, matchingAttribute);

                    newTreeFragment = new DecisionTree(newPendingNode);
                    pendingNodes.offer(newTreeFragment);
                }
                else
                {
                    // Extract an attribute with this property name from the first example and use this to get
                    // a listing of all the possible values of that attribute.
                    Attribute bestAttribute =
                        (OrdinalAttribute) examples.iterator().next().getProperty(bestProperty);

                    /*log.fine("bestProperty = " + bestProperty);*/
                    /*log.fine("bestAttribute = " + bestAttribute);*/

                    // Create a decision node that decides on the best property. New pending nodes will be created
                    // as children of this node and added to it.
                    newTreeFragment =
                        new DecisionTree(new Decision(bestProperty, bestAttribute.getType().getNumPossibleValues(),
                                matchingAttribute));

                    // Produce a cut down input property set equal to the old one but with the selected best property
                    // removed as a decision node is to be created for it.
                    Set<String> newInputProperties = new HashSet<String>(inputProperties);

                    newInputProperties.remove(bestProperty);

                    // For each possible value of the best attribute.
                    for (Iterator<? extends Attribute> i = bestAttribute.getType().getAllPossibleValuesIterator();
                            i.hasNext();)
                    {
                        OrdinalAttribute nextAttribute = (OrdinalAttribute) i.next();

                        // Extract just those examples with the current value. To implement this efficiently first sort
                        // the examples by their attribute value for the best property to split on using a range sort
                        // (O(n) time as num possible values is limited and they are already indexed by their order).
                        // Create the new example collection as simply a pair of indexes into the sorted list.

                        Collection<State> matchingExamples = new ArrayList<State>();

                        for (State example : examples)
                        {
                            // Extract the attribute value for the property to decide on.
                            OrdinalAttribute testAttribute = (OrdinalAttribute) example.getProperty(bestProperty);

                            // Check if it matches the current value being extracted and add it to the collection of
                            // extracted examples if so.
                            if (nextAttribute.equals(testAttribute))
                            {
                                matchingExamples.add(example);
                            }
                        }

                        // Push onto the queue, a child node for this value, the subset of examples (or the value to
                        // select that subset on), attributes without the best one (or an exclusion list of attributes
                        // used so far), default majority-value of classification of these examples.
                        Pending newPendingNode =
                            new Pending(matchingExamples, newInputProperties,
                                getMajorityClassification(outputProperty, matchingExamples), nextAttribute);

                        DecisionTree newPendingNodeTreeFragment = new DecisionTree(newPendingNode);

                        pendingNodes.offer(newPendingNodeTreeFragment);

                        /*log.fine("Created new pending node below the split, for " + matchingExamples.size() +
                            " examples and " + newInputProperties.size() + " undecided properties.");*/

                        // Add the new pending node as a child of the parent decision node for the best property.
                        newTreeFragment.addChild(newPendingNodeTreeFragment);
                    }
                }
            }

            // Remove the current pending node from the decision tree and replace it with the new element that the
            // algorithm has selected.
            Tree.Node parentTree = (DecisionTree) currentTreePendingNode.getParent();

            // Check if the current pending node has a parent (if not it is the real tree root and the first pending
            // node created).
            if (parentTree != null)
            {
                // Remove the pending node from its parents child list.
                parentTree.getChildren().remove(currentTreePendingNode);

                // Replace the pending node with the newly built tree fragment in its parent child list.
                parentTree.addChild(newTreeFragment);
            }
            else
            {
                // Update the root tree pointer to point to the newly built tree fragment.
                decisionTree = newTreeFragment;
            }

            /*log.fine("There are now " + pendingNodes.size() + " pending nodes on the construction queue.");*/
        }

        // Loop over the whole decision tree initializing its quick lookup tables for all the decisions it contains.
        for (Iterator<SimpleTree<DecisionTreeElement>> i = decisionTree.iterator(Tree.IterationOrder.PreOrder);
                i.hasNext();)
        {
            DecisionTree nextTreeFragment = (DecisionTree) i.next();
            DecisionTreeElement nextElement = nextTreeFragment.getElement();

            // Check if it is a decision and build its lookup table if so.
            if (nextElement instanceof Decision)
            {
                Decision decision = (Decision) nextElement;

                decision.initializeLookups(nextTreeFragment);
            }
        }

        // Create a new decisition tree machine out of the fully constructed decision tree.
        ProtoDTMachine dtMachine = new ProtoDTMachine();

        dtMachine.setDecisionTree(decisionTree);

        // Return the trained decision tree classifying machine.
        return dtMachine;
    }
public ClassifyingMachine learn() throws LearningFailureException
    {
        /*log.fine("public ClassifyingMachine learn(): called");*/

        // Call the initialize method to ensure that input and output properties are correctly set up.
        initialize();

        // Check that there is only one output property to learn for. Decision trees can only output a single
        // property classification (although mutliple trees could be built for multiple properties).
        if (outputProperties.size() != 1)
        {
            throw new LearningFailureException(
                "Decision trees can only learn a classification for a single property, " + "but " +
                outputProperties.size() + " have been set as outputs.", null);
        }

        // Extract the single output property to learn for.
        String outputProperty = outputProperties.iterator().next();

        // Check that the output property to be learnt is one with a finite number of values. Decision trees
        // cannot learn infinite valued attributes, such as real numbers etc.
        int numValues =
            inputExamples.iterator().next().getComponentType().getPropertyType(outputProperty).getNumPossibleValues();

        if (numValues < 1)
        {
            throw new LearningFailureException("Decision trees can only learn a classification for a " +
                "property with a finite number of values. The property, " + outputProperty +
                " can have an infinite number of values and should be " +
                "discretized prior to being learned by decision trees.", null);
        }

        // Used to queue nodes that are pending construction.
        Queue<DecisionTree> pendingNodes = new LinkedList<DecisionTree>();

        // Create a pending node,(an empty tree, the examples, the attributes, the default classification).
        Pending startNode =
            new Pending(inputExamples, inputProperties, getMajorityClassification(outputProperty, inputExamples), null);

        // Create the root of the decision tree out of this start pending node.
        DecisionTree decisionTree = new DecisionTree(startNode);

        // Push this new pending node onto the construction queue.
        pendingNodes.offer(decisionTree);

        // Loop until the queue of nodes pending construction is empty.
        while (!pendingNodes.isEmpty())
        {
            /*log.fine("Got next pending node.");*/

            // Get the tree fragment for the next pending node. The data element should always be safe to cast to a
            // Pending node as this algorithm only pushes pending nodes onto the queue.
            DecisionTree currentTreePendingNode = pendingNodes.remove();
            DecisionTreeElement currentTreePendingNodeElement = currentTreePendingNode.getElement();
            Pending currentNode = (Pending) currentTreePendingNodeElement;

            // Extract the examples, the attributes, the default classification, and the attribute to be matched,
            // for this pending node.
            Collection<State> examples = currentNode.getExamples();
            Collection<String> undecidedProperties = currentNode.getUndecidedProperties();
            OrdinalAttribute defaultAttribute = currentNode.getDefault();
            OrdinalAttribute matchingAttribute = currentNode.getAttributeValue();

            /*log.fine("Pending node corresponds to " + examples.size() + " examples.");*/
            /*log.fine("Pending node has " + undecidedProperties.size() + " undecided properties left.");*/

            // Used to hold the decision tree fragment (decision node, pending node or assignment leaf) that will
            // be inserted into the decision tree to replace the current pending node.
            DecisionTree newTreeFragment = null;

            // If the set of examples is empty then set the default as the leaf.
            if (examples.isEmpty())
            {
                /*log.fine("Examples is empty.");*/
                newTreeFragment = new DecisionTree(new Assignment(outputProperty, defaultAttribute, matchingAttribute));
            }

            // Else if undecided properties is empty then set the majority value of the classification of
            // examples as the leaf.
            else if (undecidedProperties.isEmpty())
            {
                /*log.fine("No undecided properties left.");*/

                // Work out what the majority classification is and create a leaf with that assignment.
                OrdinalAttribute majority = getMajorityClassification(outputProperty, inputExamples);

                newTreeFragment = new DecisionTree(new Assignment(outputProperty, majority, matchingAttribute));
            }

            // Else if all the examples have the same classification then set that classification as the leaf.
            else if (allHaveSameClassification(outputProperty, examples))
            {
                /*log.fine("All examples have the same classification.");*/
                newTreeFragment =
                    new DecisionTree(new Assignment(outputProperty, allClassification, matchingAttribute));
            }

            // Else choose the best attribute (with the largest estimated information gain) on the classification.
            else
            {
                /*log.fine("Choosing the best property to split on.");*/

                String bestProperty = chooseBestPropertyToDecideOn(outputProperty, examples, inputProperties);

                // Check if a best property could not be found, in which case behave as if there are no
                // input properties left to work with.
                if (bestProperty == null)
                {
                    /*log.fine("Couldn't find a best property to split on.");*/

                    // Put the pending node back onto the construction queue but with zero input properties.
                    Pending newPendingNode =
                        new Pending(examples, new ArrayList<String>(), defaultAttribute, matchingAttribute);

                    newTreeFragment = new DecisionTree(newPendingNode);
                    pendingNodes.offer(newTreeFragment);
                }
                else
                {
                    // Extract an attribute with this property name from the first example and use this to get
                    // a listing of all the possible values of that attribute.
                    Attribute bestAttribute =
                        (OrdinalAttribute) examples.iterator().next().getProperty(bestProperty);

                    /*log.fine("bestProperty = " + bestProperty);*/
                    /*log.fine("bestAttribute = " + bestAttribute);*/

                    // Create a decision node that decides on the best property. New pending nodes will be created
                    // as children of this node and added to it.
                    newTreeFragment =
                        new DecisionTree(new Decision(bestProperty, bestAttribute.getType().getNumPossibleValues(),
                                matchingAttribute));

                    // Produce a cut down input property set equal to the old one but with the selected best property
                    // removed as a decision node is to be created for it.
                    Set<String> newInputProperties = new HashSet<String>(inputProperties);

                    newInputProperties.remove(bestProperty);

                    // For each possible value of the best attribute.
                    for (Iterator<? extends Attribute> i = bestAttribute.getType().getAllPossibleValuesIterator();
                            i.hasNext();)
                    {
                        OrdinalAttribute nextAttribute = (OrdinalAttribute) i.next();

                        // Extract just those examples with the current value. To implement this efficiently first sort
                        // the examples by their attribute value for the best property to split on using a range sort
                        // (O(n) time as num possible values is limited and they are already indexed by their order).
                        // Create the new example collection as simply a pair of indexes into the sorted list.

                        Collection<State> matchingExamples = new ArrayList<State>();

                        for (State example : examples)
                        {
                            // Extract the attribute value for the property to decide on.
                            OrdinalAttribute testAttribute = (OrdinalAttribute) example.getProperty(bestProperty);

                            // Check if it matches the current value being extracted and add it to the collection of
                            // extracted examples if so.
                            if (nextAttribute.equals(testAttribute))
                            {
                                matchingExamples.add(example);
                            }
                        }

                        // Push onto the queue, a child node for this value, the subset of examples (or the value to
                        // select that subset on), attributes without the best one (or an exclusion list of attributes
                        // used so far), default majority-value of classification of these examples.
                        Pending newPendingNode =
                            new Pending(matchingExamples, newInputProperties,
                                getMajorityClassification(outputProperty, matchingExamples), nextAttribute);

                        DecisionTree newPendingNodeTreeFragment = new DecisionTree(newPendingNode);

                        pendingNodes.offer(newPendingNodeTreeFragment);

                        /*log.fine("Created new pending node below the split, for " + matchingExamples.size() +
                            " examples and " + newInputProperties.size() + " undecided properties.");*/

                        // Add the new pending node as a child of the parent decision node for the best property.
                        newTreeFragment.addChild(newPendingNodeTreeFragment);
                    }
                }
            }

            // Remove the current pending node from the decision tree and replace it with the new element that the
            // algorithm has selected.
            Tree.Node parentTree = (DecisionTree) currentTreePendingNode.getParent();

            // Check if the current pending node has a parent (if not it is the real tree root and the first pending
            // node created).
            if (parentTree != null)
            {
                // Remove the pending node from its parents child list.
                parentTree.getChildren().remove(currentTreePendingNode);

                // Replace the pending node with the newly built tree fragment in its parent child list.
                parentTree.addChild(newTreeFragment);
            }
            else
            {
                // Update the root tree pointer to point to the newly built tree fragment.
                decisionTree = newTreeFragment;
            }

            /*log.fine("There are now " + pendingNodes.size() + " pending nodes on the construction queue.");*/
        }

        // Loop over the whole decision tree initializing its quick lookup tables for all the decisions it contains.
        for (Iterator<SimpleTree<DecisionTreeElement>> i = decisionTree.iterator(Tree.IterationOrder.PreOrder);
                i.hasNext();)
        {
            DecisionTree nextTreeFragment = (DecisionTree) i.next();
            DecisionTreeElement nextElement = nextTreeFragment.getElement();

            // Check if it is a decision and build its lookup table if so.
            if (nextElement instanceof Decision)
            {
                Decision decision = (Decision) nextElement;

                decision.initializeLookups(nextTreeFragment);
            }
        }

        // Create a new decisition tree machine out of the fully constructed decision tree.
        ProtoDTMachine dtMachine = new ProtoDTMachine();

        dtMachine.setDecisionTree(decisionTree);

        // Return the trained decision tree classifying machine.
        return dtMachine;
    }
Builds a decision tree by repeatedly selecting the best property of the data examples to split on. The best
property is chosen to be the one that reveals the most information about the target property to learn.

<p>The constructed decision tree is then used to create a classifying machine for that tree which is returned.

@return A classifying machine built from the learned decision tree.

@throws LearningFailureException If there is not exactly one output property to learn for. This algorithm can
only handle a single output property.