Java Code to Calculate I P N Decision Tree Algorithm

Java Code Example

import java.util.*;

public class IPNDecisionTree {
    private Node root;

    public void train(List<double[]> features, List<Integer> labels) {
        root = buildTree(features, labels, 0);
    }

    private Node buildTree(List<double[]> features, List<Integer> labels, int depth) {
        // Base case: if all labels are the same or max depth reached
        if (allSame(labels) || depth >= 10) {
            return new Node(getMajorityLabel(labels));
        }

        // Find best split
        Split bestSplit = findBestSplit(features, labels);

        // If no split improves information gain
        if (bestSplit.gain == 0) {
            return new Node(getMajorityLabel(labels));
        }

        // Split the data
        List<double[]> leftFeatures = new ArrayList<>();
        List<Integer> leftLabels = new ArrayList<>();
        List<double[]> rightFeatures = new ArrayList<>();
        List<Integer> rightLabels = new ArrayList<>();

        for (int i = 0; i < features.size(); i++) {
            if (features.get(i)[bestSplit.featureIndex] < bestSplit.threshold) {
                leftFeatures.add(features.get(i));
                leftLabels.add(labels.get(i));
            } else {
                rightFeatures.add(features.get(i));
                rightLabels.add(labels.get(i));
            }
        }

        // Recursively build subtrees
        Node leftChild = buildTree(leftFeatures, leftLabels, depth + 1);
        Node rightChild = buildTree(rightFeatures, rightLabels, depth + 1);

        return new Node(bestSplit.featureIndex, bestSplit.threshold, leftChild, rightChild);
    }

    private Split findBestSplit(List<double[]> features, List<Integer> labels) {
        double bestGain = 0;
        int bestFeature = -1;
        double bestThreshold = 0;

        for (int featureIndex = 0; featureIndex < features.get(0).length; featureIndex++) {
            // Get all unique values for this feature
            Set<Double> uniqueValues = new HashSet<>();
            for (double[] feature : features) {
                uniqueValues.add(feature[featureIndex]);
            }

            // Try all possible thresholds
            for (double threshold : uniqueValues) {
                double gain = calculateInformationGain(features, labels, featureIndex, threshold);
                if (gain > bestGain) {
                    bestGain = gain;
                    bestFeature = featureIndex;
                    bestThreshold = threshold;
                }
            }
        }

        return new Split(bestFeature, bestThreshold, bestGain);
    }

    private double calculateInformationGain(List<double[]> features, List<Integer> labels,
                                           int featureIndex, double threshold) {
        // Calculate parent entropy
        double parentEntropy = calculateEntropy(labels);

        // Split the data
        List<Integer> leftLabels = new ArrayList<>();
        List<Integer> rightLabels = new ArrayList<>();

        for (int i = 0; i < features.size(); i++) {
            if (features.get(i)[featureIndex] < threshold) {
                leftLabels.add(labels.get(i));
            } else {
                rightLabels.add(labels.get(i));
            }
        }

        // Calculate weighted child entropy
        double leftWeight = (double)leftLabels.size() / labels.size();
        double rightWeight = (double)rightLabels.size() / labels.size();

        double childEntropy = leftWeight * calculateEntropy(leftLabels) +
                             rightWeight * calculateEntropy(rightLabels);

        // Information gain
        return parentEntropy - childEntropy;
    }

    private double calculateEntropy(List<Integer> labels) {
        Map<Integer, Integer> labelCounts = new HashMap<>();
        for (int label : labels) {
            labelCounts.put(label, labelCounts.getOrDefault(label, 0) + 1);
        }

        double entropy = 0;
        for (int count : labelCounts.values()) {
            double probability = (double)count / labels.size();
            entropy -= probability * (Math.log(probability) / Math.log(2));
        }

        return entropy;
    }

    private boolean allSame(List<Integer> labels) {
        if (labels.isEmpty()) return true;
        int first = labels.get(0);
        for (int label : labels) {
            if (label != first) return false;
        }
        return true;
    }

    private int getMajorityLabel(List<Integer> labels) {
        Map<Integer, Integer> labelCounts = new HashMap<>();
        for (int label : labels) {
            labelCounts.put(label, labelCounts.getOrDefault(label, 0) + 1);
        }

        int majorityLabel = -1;
        int maxCount = 0;
        for (Map.Entry<Integer, Integer> entry : labelCounts.entrySet()) {
            if (entry.getValue() > maxCount) {
                majorityLabel = entry.getKey();
                maxCount = entry.getValue();
            }
        }

        return majorityLabel;
    }

    public int predict(double[] features) {
        return predict(root, features);
    }

    private int predict(Node node, double[] features) {
        if (node.isLeaf()) {
            return node.label;
        }

        if (features[node.featureIndex] < node.threshold) {
            return predict(node.left, features);
        } else {
            return predict(node.right, features);
        }
    }

    private static class Node {
        int featureIndex;
        double threshold;
        Node left;
        Node right;
        int label;

        // Leaf node constructor
        Node(int label) {
            this.label = label;
        }

        // Internal node constructor
        Node(int featureIndex, double threshold, Node left, Node right) {
            this.featureIndex = featureIndex;
            this.threshold = threshold;
            this.left = left;
            this.right = right;
        }

        boolean isLeaf() {
            return left == null && right == null;
        }
    }

    private static class Split {
        int featureIndex;
        double threshold;
        double gain;

        Split(int featureIndex, double threshold, double gain) {
            this.featureIndex = featureIndex;
            this.threshold = threshold;
            this.gain = gain;
        }
    }
}