Method buildTree

JSAT/src/jsat/classifiers/trees/ID3.java:77–141

( List<DataPointPair<Integer>> dataPoints, Set<Integer> remainingAtribues, final ExecutorService threadPool)

    }
    
    private ID3Node buildTree( List<DataPointPair<Integer>> dataPoints, Set<Integer> remainingAtribues, final ExecutorService threadPool)
    {
        double curEntropy = entropy(dataPoints);
        double size = dataPoints.size();
        
        if(remainingAtribues.isEmpty() || curEntropy == 0)
        {
            CategoricalResults cr = new CategoricalResults(predicting.getNumOfCategories());
            for(DataPointPair<Integer> dpp : dataPoints)
                cr.setProb(dpp.getPair(), cr.getProb(dpp.getPair()) + 1);
            cr.divideConst(size);

            latch.countDown();
            return new ID3Node(cr);
        }
        
        int bestAttribute = -1;
        double bestInfoGain = Double.MIN_VALUE;
        List<List<DataPointPair<Integer>>> bestSplit = null;
        
        for(int attribute : remainingAtribues)
        {
            List<List<DataPointPair<Integer>>> newSplit = new ArrayList<List<DataPointPair<Integer>>>(attributes[attribute].getNumOfCategories());
            for( int i = 0; i < attributes[attribute].getNumOfCategories(); i++)
                newSplit.add( new ArrayList<DataPointPair<Integer>>());
            
            //Putting the datapoints in their respective bins by attribute value
            for(DataPointPair<Integer> dpp : dataPoints)
                newSplit.get(dpp.getDataPoint().getCategoricalValue(attribute)).add(dpp);
            
            double splitEntrop = 0;
            for(int i = 0; i < newSplit.size(); i++)
                splitEntrop += entropy(newSplit.get(i))*newSplit.get(i).size()/size;
            
            double infoGain = curEntropy - splitEntrop;
            if(infoGain > bestInfoGain)
            {
                bestAttribute = attribute;
                bestInfoGain = infoGain;
                bestSplit = newSplit;
            }
                
        }
        
        final ID3Node node = new ID3Node(attributes[bestAttribute].getNumOfCategories(), bestAttribute);
        final Set<Integer> newRemaining = new IntSet(remainingAtribues);
        newRemaining.remove(bestAttribute);
        for(int i = 0; i < bestSplit.size(); i++)
        {
            final int ii = i;
            final List<DataPointPair<Integer>> bestSplitII = bestSplit.get(ii);
            latch.countUp();
            threadPool.submit(new Runnable() {

                public void run()
                {
                    node.setNode(ii, buildTree(bestSplitII, newRemaining, threadPool));
                }