package jsat.classifiers.trees;

import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.concurrent.ExecutorService;
import java.util.logging.Level;
import java.util.logging.Logger;

import jsat.classifiers.CategoricalData;
import jsat.classifiers.CategoricalResults;
import jsat.classifiers.ClassificationDataSet;
import jsat.classifiers.Classifier;
import jsat.classifiers.DataPoint;
import jsat.classifiers.DataPointPair;
import jsat.utils.FakeExecutor;
import jsat.utils.IntSet;
import jsat.utils.ModifiableCountDownLatch;
import jsat.utils.concurrent.ParallelUtils;

/**
 *
 * @author Edward Raff
 */
public class ID3 implements Classifier
{

    private static final long serialVersionUID = -8473683139353205898L;
    private CategoricalData predicting;
    private CategoricalData[] attributes;
    private ID3Node root;
    private ModifiableCountDownLatch latch;

    public CategoricalResults classify(DataPoint data)
    {
        return walkTree(root, data);
    }
    
    static private CategoricalResults walkTree(ID3Node node, DataPoint data)
    {
        if(node.isLeaf())
            return node.getResult();
        
        return walkTree(node.getNode(data.getCategoricalValue(node.getAttributeId())), data);
    }

    @Override
    public void train(ClassificationDataSet dataSet, boolean parallel)
    {
        if(dataSet.getNumNumericalVars() != 0)
            throw new RuntimeException("ID3 only supports categorical data");
        
        predicting = dataSet.getPredicting();
        attributes = dataSet.getCategories();
        List> dataPoints = dataSet.getAsDPPList();
        
        Set availableAttributes = new IntSet(dataSet.getNumCategoricalVars());
        for(int i = 0; i < dataSet.getNumCategoricalVars(); i++)
            availableAttributes.add(i);
        latch = new ModifiableCountDownLatch(1);
        ExecutorService threadPool = parallel ? ParallelUtils.CACHED_THREAD_POOL : new FakeExecutor();
        root = buildTree(dataPoints, availableAttributes, threadPool);    
        try
        {
            latch.await();
        }
        catch (InterruptedException ex)
        {
            Logger.getLogger(ID3.class.getName()).log(Level.SEVERE, null, ex);
        }
    }
    
    private ID3Node buildTree( List> dataPoints, Set 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 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>> bestSplit = null;
        
        for(int attribute : remainingAtribues)
        {
            List>> newSplit = new ArrayList<>(attributes[attribute].getNumOfCategories());
            for( int i = 0; i < attributes[attribute].getNumOfCategories(); i++)
                newSplit.add( new ArrayList<>());
            
            //Putting the datapoints in their respective bins by attribute value
            for(DataPointPair 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 newRemaining = new IntSet(remainingAtribues);
        newRemaining.remove(bestAttribute);
        for(int i = 0; i < bestSplit.size(); i++)
        {
            final int ii = i;
            final List> bestSplitII = bestSplit.get(ii);
            latch.countUp();
            threadPool.submit(() ->
            {
                node.setNode(ii, buildTree(bestSplitII, newRemaining, threadPool));
            });
            
        }
        
        latch.countDown();
        return node;
    }
    
    static private class ID3Node
    {
        ID3Node[] children;
        CategoricalResults cr;
        int attributeId;

        private ID3Node()
        {
        }

        /**
         * Constructs a parent
         * @param atributes the number of possible values for the attribute this node should split on
         */
        public ID3Node(int atributes, int attributeId)
        {
            cr = null;
            children = new ID3Node[atributes];
            this.attributeId = attributeId;
        }

        /**
         * Constructs a leaf
         * @param cr the result to return for reaching this leaf node
         */
        public ID3Node( CategoricalResults cr)
        {
            this.children = null;
            this.cr = cr;
        }
        
        public boolean isLeaf()
        {
            return cr != null;
        }
        
        public void setNode(int i, ID3Node node)
        {
            children[i] = node;
        }
        
        public ID3Node getNode(int i)
        {
            return children[i];
        }

        public int getAttributeId()
        {
            return attributeId;
        }

        public CategoricalResults getResult()
        {
            return cr;
        }
        
        public ID3Node copy()
        {
            ID3Node copy = new ID3Node();
            copy.cr = this.cr;
            copy.attributeId = this.attributeId;
            if(this.children != null)
            {
                copy.children = new ID3Node[this.children.length];
                for(int i = 0; i < children.length; i++)
                    copy.children[i] = this.children[i].copy();
                    
            }
            return copy;
        }
        
    }
    
    
    private double entropy( List> s)
    {
        if(s.isEmpty())
            return 0;
        double[] probs = new double[predicting.getNumOfCategories()];
        for(DataPointPair dpp : s)
            probs[dpp.getPair()] += 1;
        for(int i = 0; i < probs.length; i++)
            probs[i] /= s.size();
        
        double entr = 0;
        
        for(int i = 0; i < probs.length; i++)
            if(probs[i] != 0)
                entr += probs[i] * (Math.log(probs[i])/Math.log(2));
        //The entr will be negative unless it is zero, this way we dont return negative zero
        return Math.abs(entr);
    }
    

    @Override
    public boolean supportsWeightedData()
    {
        return false;
    }

    @Override
    public Classifier clone()
    {
        ID3 copy = new ID3();
        
        copy.attributes = this.attributes;
        copy.latch = null;
        copy.predicting = this.predicting;
        copy.root = this.root.copy();
        
        return copy;
    }
    
}

 

Ads help maintain this website.