function [ig, te] = infogain(data)

%Assume 'data' is an array, where data(i,j) gives the value of feature j
%from record i. (i.e., each row is a record.)

%Compute total number of records
nrecords = length(data(:,1));

%Entropy of the label distribution *before splitting*
[ rootentropy, rooterror ] = entropy(data(:,1));
%'rooterror' isn't used for anything; it would be the error we got if we
%didn't split, but just labeled the whole dataset with the majority class.
%(i.e. democrat.)

%For each different feature... (first column is the class label)
for i = 2:length(data(1,:))
    %Start with entropy and training error at zero.
    splitentropy = 0;
    spliterror = 0;
    
    %For each unique feature value...
    for v = unique(data(:,i))';
        %...in this case, for each of 'y', 'n', '?'
        subset = find(data(:,i) == v);
 
        %Find the proportion of records that match
        prop_that_match = length(subset)/nrecords;

        %Compute the entropy and training error
        %of the subset of the data that matches
        [ sentropy serror ] = entropy(data(subset,1));

        %Add this to our running total. NOTE that we weight the results by
        %the proportion of records that match.
        splitentropy = splitentropy + prop_that_match*sentropy;
        spliterror = spliterror + prop_that_match*serror;
    end

    %Information gain is just the difference between the 'before' and
    %'after' entropy
    infogain = rootentropy - splitentropy;

    %Print this out
    fprintf(1,'Info gain for %d: %f  Training error: %f\n', ...
        i-1, infogain, spliterror);
    %Put it in return variables.
    ig(i-1,:) = infogain;
    te(i-1,:) = spliterror;
end
end

function [ent, err] = entropy(labels)
    %How many data items in this set
    nlabels = length(labels);

    %Entropy starts at zero
    ent = 0;
    %Size of the biggest proportion of labels starts at zero
    maxprop = 0;

    %For each different label (ex. "democrat", "republican")
    for l = unique(labels)'

       %prop is number that match l divided by total number of labels
        prop = length(find(labels == l)) / nlabels;

        %update maxprop if appropriate
        if(prop > maxprop)
            maxprop = prop;
        end

        %increase our entropy by P(class = label)*log_2(P(class = label))
        ent = ent + prop * log2(prop);
    end
    
    %We usually negate entropy
    ent = -ent;
    %And this would be the training error
    err = 1 - maxprop;
end
