Создание дерева решений рекурсивно превышает глубину рекурсии. Сделать хвост рекурсивным? - PullRequest
Новая
       34

Создание дерева решений рекурсивно превышает глубину рекурсии. Сделать хвост рекурсивным?

0 голосов
/ 12 апреля 2020

Итак, я пытаюсь создать дерево решений из некоторых данных (Pandas DataFrame). Данные имеют некоторые атрибуты и метку. вот пример: 

Outlook   Temp  Humidity Wind    label
Sunny     Hot   High     Weak    No
Sunny     Hot   High     Strong  No
Overcast  Hot   High     Weak    Yes
Rain      Mild  High     Weak    Yes
Rain      Cool  Normal   Weak    Yes
Rain      Cool  Normal   Strong  No
Overcast  Cool  Normal   Strong  Yes
Sunny     Mild  High     Weak    No
Sunny     Cool  Normal   Weak    Yes
Rain      Mild  Normal   Weak    Yes
Sunny     Mild  Normal   Strong  Yes
Overcast  Mild  High     Strong  Yes
Overcast  Hot   Normal   Weak    Yes
Rain      Mild  High     Strong  No

Теперь вот мой код. 

def createTree(dataF):
    posibleLabels = (set(dataF['label'].to_list()))
    if len(posibleLabels) == 1:
        return decisionTree(posibleLabels.pop(), []) #This is a leaf node
    else:
        root = bestGain(dataF) #This function determines the root of the sub tree(For testing, return 
        posibleVals = set(dataF[root].to_list())            # any of the column names except "label")                
        newTree = decisionTree(root, posibleVals)
        for v in posibleVals:
            subDataF = dataF.loc[dataF[root] == v] 
            subTree = createTree(subDataF)  #This is the problematic Recursive Call
            newTree.append(subTree, v)
        return newTree

Для небольшого примера, который я привел выше, этот код работает отлично. Но когда я пытаюсь увеличить размер данных, он достигает максимальной глубины рекурсии. У кого-нибудь есть идея сделать этот хвост рекурсивным или, может быть, сделать его итеративным?

PD. Вот класс дерева решений: 

class decisionTree:

    def __init__(self, root, posibleVals):

        self.root = root
        self.posibleVals = posibleVals
        self.childs = {}
        for v in posibleVals:
            self.childs.update({v: None})

    def append(self, subTree, val):
        self.childs.update({val: subTree})

    def __str__(self):
        s = str(self.root) + "( "
        s1 = ""
        for k, v in self.childs.items():
            s1 = s1 + ", " + k
        s = s + s1.lstrip(", ") + " )\n"
        for k, v in self.childs.items():
            s = s + k + "->" +  str(v)
        return s
...