001/*
002 * Copyright (c) 2015, 2022, Oracle and/or its affiliates. All rights reserved.
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 *     http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package org.tribuo.classification.dtree.impurity;
018
019import com.oracle.labs.mlrg.olcut.config.Configurable;
020import com.oracle.labs.mlrg.olcut.provenance.ConfiguredObjectProvenance;
021import com.oracle.labs.mlrg.olcut.provenance.Provenancable;
022
023import java.util.Map;
024
025/**
026 * Calculates a tree impurity score based on label counts, weighted label counts or a probability distribution.
027 * <p>
028 * Impurity scores should be non-negative, with a zero signifying that the node is pure (i.e., contains
029 * only a single label), and increasing values indicating an increasingly uniform distribution over possible labels.
030 */
031public interface LabelImpurity extends Configurable, Provenancable<ConfiguredObjectProvenance> {
032
033    /**
034     * Calculates the impurity, assuming it's input is a normalized probability distribution.
035     * @param input The input probability distribution.
036     * @return The impurity.
037     */
038    public double impurityNormed(double[] input);
039
040    /**
041     * Calculates the impurity assuming the inputs are weighted counts normalizing by their sum.
042     * @param input The input counts.
043     * @return The impurity.
044     */
045    default public double impurityWeighted(double[] input) {
046        double[] prob = new double[input.length];
047
048        double sum = 0.0;
049        for (double i : input) {
050            sum += i;
051        }
052
053        for (int i = 0; i < input.length; i++) {
054            prob[i] = input[i] / sum;
055        }
056
057        return sum*impurityNormed(prob);
058    }
059
060    /**
061     * Calculates the impurity assuming the inputs are counts.
062     * @param input The input counts.
063     * @return The impurity.
064     */
065    default public double impurity(double[] input) {
066        double[] prob = new double[input.length];
067
068        double sum = 0.0;
069        for (double i : input) {
070            sum += i;
071        }
072
073        for (int i = 0; i < input.length; i++) {
074            prob[i] = input[i] / sum;
075        }
076
077        return impurityNormed(prob);
078    }
079
080    /**
081     * Calculates the impurity by assuming the input are weighted counts and converting them into a probability
082     * distribution by dividing by their sum. The resulting impurity is then rescaled by multiplying by the sum.
083     * @param input The input counts.
084     * @return The impurity.
085     */
086    default public double impurityWeighted(float[] input) {
087        double[] prob = new double[input.length];
088
089        double sum = 0.0;
090        for (int i = 0; i < input.length; i++) {
091            float f = input[i];
092            sum += f;
093        }
094
095        for (int i = 0; i < input.length; i++) {
096            prob[i] = input[i] / sum;
097        }
098
099        return sum*impurityNormed(prob);
100    }
101
102    /**
103     * Calculates the impurity assuming the input are fractional counts.
104     * @param input The input counts.
105     * @return The impurity.
106     */
107    default public double impurity(float[] input) {
108        double[] prob = new double[input.length];
109
110        double sum = 0.0;
111        for (double i : input) {
112            sum += i;
113        }
114
115        for (int i = 0; i < input.length; i++) {
116            prob[i] = input[i] / sum;
117        }
118
119        return impurityNormed(prob);
120    }
121
122    /**
123     * Calculates the impurity assuming the input are counts.
124     * @param input The input counts.
125     * @return The impurity.
126     */
127    default public double impurity(int[] input) {
128        double[] prob = new double[input.length];
129
130        int sum = 0;
131        for (int i : input) {
132            sum += i;
133        }
134
135        double sumFloat = sum;
136        for (int i = 0; i < input.length; i++) {
137            prob[i] = input[i] / sumFloat;
138        }
139
140        return impurityNormed(prob);
141    }
142
143    /**
144     * Takes a {@link Map} for weighted counts. Normalizes into a probability distribution before calling impurityNormed(double[]).
145     * @param counts A map from instances to weighted counts.
146     * @return The impurity score.
147     */
148    default public double impurity(Map<String,Double> counts) {
149        double[] prob = new double[counts.size()];
150
151        double sum = 0.0;
152        int i = 0;
153        for (Map.Entry<String,Double> e : counts.entrySet()) {
154            sum += e.getValue();
155            prob[i] = e.getValue();
156            i++;
157        }
158
159        for (int j = 0; j < prob.length; j++) {
160            prob[j] /= sum;
161        }
162
163        return impurityNormed(prob);
164    }
165
166}