python - 麻烦递归地构建二元决策树python

Question

我正在尝试递归构建一个二元决策树，用于在 python 3 中诊断疾病。 构建器获取一个记录列表(每个记录都是一种疾病及其症状列表)和一个症状列表，如下所示:

class Node:
    def __init__(self, data = "", pos = None, neg = None):
        self.data = data
        self.positive_child = pos
        self.negative_child = neg
class Record:
    def __init__(self, illness, symptoms):
        self.illness = illness
        self.symptoms = symptoms

records= [Record('A',['1','3']),
          Record('B',['1','2']),
          Record('C',['2','3']),
          ]
symptoms = ['1','2','3']

然后构建一个二叉树，每一级检查症状是真还是假，每个级别都有一个子节点。右边的 child 总是意味着症状不存在，而左边的 child 则意味着它存在。对于示例数据，树应该如下所示:

                       1
               2                    2
          3        3          3            3
    None   B     A   None   C  None   None     Healthy

例如，通过询问到达叶子A: 1:真 2:错误 3:真 它的路径是 [1,3](真值)

这是我正在使用但无法正常工作的代码:

def builder(records, symptoms, path):
    #Chekl if we are in a leaf node that matches an illness
    for record in records:
        if path == record.symptoms:
            return Node(record.illness,None,None)

     #No more symptoms means an empty leaf node
    if len(symptoms) == 0:
        return Node(None,None,None)

    #create subtree
    else:
        symptom = symptoms.pop(0)
        right_child = builder(records,symptoms,path)
        path.append(symptom)
        left_child = builder(records,symptoms,path)
        return  Node(symptom,right_child,left_child)

我尝试了冷运行，在论文中它运行良好。我不确定我遗漏了什么，但是生成的树有很多空节点，而不是有病的节点。也许我弄乱了路径，但我现在不确定如何修复它。

Answer 1

您的symptoms.pop(0) 正在影响 一个 symptoms 列表，该列表由对 builder 的所有调用共享.这在下降过程中很好，因为您只想考虑后续症状。但是当递归调用返回时，您的列表缺少元素。 (如果没有找到匹配就返回，它是空的!)同样，共享的 path 会永远增长。

简单但低效的答案是在递归时创建新列表:

symptom=symptoms[0]
symptoms=symptoms[1:]
path=path+[symptom]  # not +=