デシジョンツリー生成時の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 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; 
    } 

例外：

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; 
    } 

者は、他の機能です

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)));

は、スタックオーバーフローにつながるたびにメソッドの再帰、呼び出されています。つまり、あなたのロジックには、再帰を終わらせる "基本ケース"、すなわちルートを返すものに到達していないものがあるということが分かります。何がうまくいかないのかを正確に知るために必要な動作や開始データについては十分に分かっていませんが、デバッガでコードをステップ実行し、メソッド内のロジックが期待通りの動作をしていることを確認します。私はそれが素晴らしい答えではないことを知っていますが、これは出発点です。うまくいけば助けになるか、他の誰かがより具体的な解決策を提案してくれるでしょう。