StackOverflowError при генерации дерева генерации JAVA

Question

Я пытаюсь написать алгоритм ID3, который генерирует дерево принятия решений, но я получаю StackOverflowError при запуске моего кода. При отладке я заметил, что цикл начинается, когда атрибуты спускаются до 4 (изначально 9). Код для генерации деревьев приведен ниже. Все функции, которые я вызываю, работают правильно, они были протестированы. Однако код ошибки указывает на то, что проблема связана с другой функцией, использующей потоки, но она была протестирована отдельно , и я знаю, что она работает правильно. Имейте в виду, что я работаю со случайными данными, поэтому функция иногда вызывает ошибку , а иногда нет. Я размещаю код ошибки под ним, но функция энтропии и информация работают.

Это структура TreeNode:

public class TreeNode { 
    List<Patient> samples; 
    List<TreeNode> children; 
    TreeNode parent; 
    Integer attribute; 
    String attributeValue; 
    String className; 

    public TreeNode(List<Patient> samples, List<TreeNode> children, TreeNode parent, Integer attribute, 
      String attributeValue, String className) { 
     this.samples = samples; 
     this.children = children; 
     this.parent = parent; 
     this.attribute = attribute; 
     this.attributeValue = attributeValue; 
     this.className = className; 
    } 
} 

И вот код, который бросает ошибки:

public TreeNode id3(List<Patient> patients, List<Integer> attributes, TreeNode root) { 
     boolean isLeaf = patients.stream().collect(Collectors.groupingBy(i -> i.className)).keySet().size() == 1; 
     if (isLeaf) { 
      root.setClassName(patients.get(0).className); 
      return root; 
     } 
     if (attributes.size() == 0) { 
      root.setClassName(mostCommonClass(patients)); 
      return root; 
     } 
     int bestAttribute = maxInformationGainAttribute(patients, attributes); 
     Set<String> attributeValues = attributeValues(patients, bestAttribute); 
     for (String value : attributeValues) { 
      List<Patient> branch = patients.stream().filter(i -> i.patientData[bestAttribute].equals(value)) 
        .collect(Collectors.toList()); 

      TreeNode child = new TreeNode(branch, new ArrayList<>(), root, bestAttribute, value, null); 

      if (branch.isEmpty()) { 
       child.setClassName(mostCommonClass(patients)); 
       root.addChild(new TreeNode(child)); 
      } else { 
       List<Integer> newAttributes = new ArrayList<>(); 
       newAttributes.addAll(attributes); 
       newAttributes.remove(new Integer(bestAttribute)); 
       root.addChild(new TreeNode(id3(branch, newAttributes, child))); 
      } 
     } 
     return root; 
    } 

Те и другие функции:

public static double entropy(List<Patient> patients) { 
     double entropy = 0.0; 
     double recurP = (double) patients.stream().filter(i -> i.className.equals("recurrence-events")).count() 
       /(double) patients.size(); 
     double noRecurP = (double) patients.stream().filter(i -> i.className.equals("no-recurrence-events")).count() 
       /(double) patients.size(); 
     entropy -= (recurP * (recurP > 0 ? Math.log(recurP) : 0/Math.log(2)) 
       + noRecurP * (noRecurP > 0 ? Math.log(noRecurP) : 0/Math.log(2))); 
     return entropy; 
    } 



public static double informationGain(List<Patient> patients, int attribute) { 
     double informationGain = entropy(patients); 
     Map<String, List<Patient>> patientsGroupedByAttribute = patients.stream() 
       .collect(Collectors.groupingBy(i -> i.patientData[attribute])); 
     List<List<Patient>> subsets = new ArrayList<>(); 
     for (String i : patientsGroupedByAttribute.keySet()) { 
      subsets.add(patientsGroupedByAttribute.get(i)); 
     } 

     for (List<Patient> lp : subsets) { 
      informationGain -= proportion(lp, patients) * entropy(lp); 
     } 
     return informationGain; 
    } 


private static int maxInformationGainAttribute(List<Patient> patients, List<Integer> attributes) { 
     int maxAttribute = 0; 
     double maxInformationGain = 0; 
     for (int i : attributes) { 
      if (informationGain(patients, i) > maxInformationGain) { 
       maxAttribute = i; 
       maxInformationGain = informationGain(patients, i); 
      } 
     } 
     return maxAttribute; 
    } 

Исключения:

Exception in thread "main" java.lang.StackOverflowError 
    at java.util.stream.ReferencePipeline$2$1.accept(Unknown Source) 
    at java.util.ArrayList$ArrayListSpliterator.forEachRemaining(Unknown Source) 
    at java.util.stream.AbstractPipeline.copyInto(Unknown Source) 
    at java.util.stream.AbstractPipeline.wrapAndCopyInto(Unknown Source) 
    at java.util.stream.ReduceOps$ReduceOp.evaluateSequential(Unknown Source) 
    at java.util.stream.AbstractPipeline.evaluate(Unknown Source) 
    at java.util.stream.LongPipeline.reduce(Unknown Source) 
    at java.util.stream.LongPipeline.sum(Unknown Source) 
    at java.util.stream.ReferencePipeline.count(Unknown Source) 
    at Patient.entropy(Patient.java:39) 
    at Patient.informationGain(Patient.java:67) 
    at Patient.maxInformationGainAttribute(Patient.java:85) 
    at Patient.id3(Patient.java:109) 

Answer 1

Линия:

root.addChild(new TreeNode(id3(branch, newAttributes, child)));

вызывается каждый раз, когда метод рекурсивно, что приводит к переполнению стека. Это говорит мне, что в вашей логике есть что-то неправильное, когда ни один из «базовых случаев», которые заканчиваются рекурсией, т.е. Я не знаю достаточно о желаемом поведении или исходных данных, чтобы определить, что происходит не так, но я бы начал, перейдя через код с помощью отладчика и убедившись, что логика в методе ведет себя так, как вы ожидаете. Я знаю, что это не отличный ответ, но это отправная точка, надеюсь, что это поможет, или кто-то другой перезвонит с более конкретным решением.