package jsat.classifiers.bayesian.graphicalmodel;

import java.util.Set;

import jsat.classifiers.ClassificationDataSet;
import jsat.classifiers.DataPoint;
import jsat.utils.IntList;
import jsat.utils.IntSet;
import jsat.utils.ListUtils;
import static java.lang.Math.*;
import static jsat.math.SpecialMath.*;

/**
 * An implementation of the K2 algorithm for learning the structure of a Bayesian Network. When trained, 
 * if no network has been specified, the K2 algorithm will attempt to learn a network structure. The 
 * network structure can also be learned by calling {@link #learnNetwork(jsat.classifiers.ClassificationDataSet) } directly. 
 * 

* Note, that the K2 algorithm attempts to learn a whole network structure, and may learn things that are relevant * for the classification task. K2 often does not provide satisfactory results for classification. *

* See: A bayesian method for the induction of probabilistic networks from data. Gregory F. Cooper and Edward Herskovits. * @author Edward Raff */ public class K2NetworkLearner extends DiscreteBayesNetwork { private static final long serialVersionUID = -9681177007308829L; public K2NetworkLearner() { super(); } /** * list of all possible values of the attribute xi */ private int[] ri; private int maxParents; /** * Sets the maximum number of parents to allow a node when learning the network structure. If a non zero value is supplied, nodes will be allowed any number of parents. * @param maxParents sets the maximum number of parents a node may learn */ public void setMaxParents(int maxParents) { this.maxParents = maxParents; } /** * Returns the maximum number of parents allowed when learning a network structure, or zero if any number of parents are valid. * @return the maximum number of parents a node man learn */ public int getMaxParents() { return max(maxParents, 0); } /** * Learns the network structure from the given data set. * @param D the data set to learn the network from */ public void learnNetwork(ClassificationDataSet D) { IntList varOrder = new IntList(D.getNumCategoricalVars()+1); varOrder.add(D.getNumCategoricalVars());//Classification target will be evaluated first ListUtils.addRange(varOrder, 0, D.getNumCategoricalVars(), 1); ri = new int[varOrder.size()]; for(int i : varOrder) if(i == D.getNumCategoricalVars()) ri[i] = D.getClassSize(); else ri[i] = D.getCategories()[i].getNumOfCategories(); int u = maxParents; if(u <= 0) u = ri.length; /** * Stores the set of variables preceding the current one being evaluated */ Set preceding = new IntSet(); for(int i : varOrder)//Loop of the variables in the intended order { Set pi = new IntSet();//The current parrents of variable i double pOld = f(i, pi, D); boolean OKToProceed = true; Set candidates = new IntSet(preceding); while(OKToProceed && pi.size() < u) { if(candidates.isEmpty()) break;//Break out of the loop, no candidates left. //Best candidate solution double pNew = Double.NEGATIVE_INFINITY; //The best candidate int z = -1; candidates.removeAll(pi); //Find the variable that maximizes our gain for(int candidate : candidates) { pi.add(candidate); double tmp = f(i, pi, D); if(tmp > pNew) { pNew = tmp; z = candidate; } pi.remove(candidate); } if(pNew > pOld) { pOld = pNew; pi.add(z); } else OKToProceed = false; } for(int parrent : pi) depends(parrent, i); preceding.add(i); } ri = null; } @Override public void train(ClassificationDataSet dataSet) { if(dag.getNodes().isEmpty() || dag.getParents(dataSet.getNumCategoricalVars()).isEmpty()) learnNetwork(dataSet); super.train(dataSet); } /** * Queries the data set for the number of instances that have each possible combination of values. * classes and values should have the same length. Each value in classes * corresponds to the target value specified in values. We will return the number * of data points that satisfy all class value pairs * * * @param classes the classes to check * @param values the values to check for * @param D the data set to search * @return the number of times the value constraints are satisfied in the data set */ private double query(int[] classes, int[] values, ClassificationDataSet D) { double count = 1; for(int i = 0; i < D.getSampleSize(); i++) { DataPoint dp = D.getDataPoint(i); //Use j to break early (set value) or indicate success (j == classes.length) int j; for(j = 0; j < classes.length; j++) { if(classes[j] == D.getNumCategoricalVars())//Special case { if(D.getDataPointCategory(i) != values[j]) j = classes.length+1; } else if(dp.getCategoricalValue(j) != values[j]) j = classes.length+1; } if(j == classes.length) count+=dp.getWeight(); } return count; } public double f(int i, Set pi, ClassificationDataSet D) { double term2 = 0.0; double Nijk = 0.0; if(pi.isEmpty())//Special case { int[] classes = new int[] {i}; int[] values = new int[1]; for(int k = 0; k < ri[i]; k++) { values[0] = k; double count = query(classes, values, D); Nijk += count; term2 += lnGamma(count+1); } return ((lnGamma(ri[i]) - lnGamma(Nijk + ri[i])) + term2); } double fullProduct = 0.0; //General case int[] classes = new int[pi.size()+1]; int[] values = new int[pi.size()+1]; int c = 0; for(int clas : pi) classes[c++] = clas; classes[c] = i;//Last one is the one we are currently evaluating //Default all values to zero, which is fine //We need to compute the sum for ever possible combination of class values. //We do this by incrementing the values array and breaking out when we get to an invalid state while(true) { term2 = Nijk = 0.0; for(int k = 0; k < ri[i]; k++) { values[pi.size()] = k; double count = query(classes, values, D); Nijk += count; term2 += lnGamma(count+1); } fullProduct += (lnGamma(ri[i]) - lnGamma(Nijk + ri[i])) + term2; //Increment the variable count int pos = 0; values[pos]++; values[pi.size()] = 0;//We set this to zero. If its value is non zero after this loop, //then all values have been iterated past their max value, they have rolled //over to all zeros, and we are done while(values[pos] >= ri[classes[pos]] && pos < pi.size()) { values[pos++] = 0; values[pos]++; } if(values[pi.size()] != 0) break; } return (fullProduct); } }

Ads help maintain this website.