BFS обход дерева решений sklearn - PullRequest
Новая
       100

BFS обход дерева решений sklearn

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

Как мне выполнить первый обход в поиске дерева решений sklearn?

В своем коде я попробовал библиотеку sklearn.tree_ и использовал различные функции, такие как tree_.feature и tree_.threshold, чтобы понять структура дерева. Но эти функции выполняют обход дерева dfs, если я хочу сделать bfs, как мне это сделать?

Предположим, 

clf1 = DecisionTreeClassifier( max_depth = 2 )
clf1 = clf1.fit(x_train, y_train)

, это мой классификатор, и полученное дерево решений

Decision tree

Затем я прошел по дереву, используя следующую функцию 

def encoding(clf, features):
l1 = list()
l2 = list()

for i in range(len(clf.tree_.feature)):
    if(clf.tree_.feature[i]>=0):
        l1.append( features[clf.tree_.feature[i]])
        l2.append(clf.tree_.threshold[i])
    else:
        l1.append(None)
        print(np.max(clf.tree_.value))
        l2.append(np.argmax(clf.tree_.value[i]))

l = [l1 , l2]

return np.array(l)

, и в результате получился массив

( [['address', 'age', None, None, 'age', None, None], [0.5, 17.5, 2, 1, 15.5, 1, 1]], dtype = object), где 1-й массив является признаком узел или если это конечный узел, то он помечается как none и 2-й массив является порогом для узла признаков, а для узла класса это класс, но это обход dfs дерева. Я хочу сделать обход bfs, что мне делать? Ответ на вышеуказанную часть получен.

Я хотел бы знать, можем ли мы сохранить дерево в массиве таким образом, чтобы оно представляло собой полное двоичное дерево, чтобы дочерние элементы i-го узла сохранялись в 2i + 1-й и 2i +2-й индекс?

enter image description here

Для вышеприведенного дерева выводится массив ([['address', 'age', None, None], [ 0,5, 15,5, 1, 1]], dtype = object)

, но желаемым выводом является массив

([['address', None, 'age', None, None, None , None], [0.5, -1, 15,5, -1, -1, 1, 1]], dtype = object)

Если значения отсутствуют в 1-м массиве и -1 во 2-м массиве, это будет означать этот узел не существует. Таким образом, здесь возраст, являющийся правым потомком адреса, находится в 2 * 0 + 2 = 2 индекса в массиве, и аналогично левый и правый ребенок возраста находится в 2 * 2 + 1 = 5-й индекс и 2 * 2 + 2 = 6-й индекс массива соответственно.

1 Ответ

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

Что-то вроде этого? 

def reformat_tree(clf):
    tree = clf.tree_

    feature_out = np.full((2 ** tree.max_depth), -1, dtype=tree.feature.dtype)
    threshold_out = np.zeros((2 ** tree.max_depth), dtype=tree.threshold.dtype)

    stack = []
    stack.append((0, 0))

    while stack:
        current_node, new_node = stack.pop()

        feature_out[new_node] = tree.feature[current_node]
        threshold_out[new_node] = tree.threshold[current_node]

        left_child = tree.children_left[current_node]
        if left_child >= 0:
            stack.append((left_child, 2 * current_node + 1))

        right_child = tree.children_right[current_node]
        if right_child >= 0:
            stack.append((right_child, 2 * current_node + 2))

    return feature_out, threshold_out

Я не могу проверить это на вашем дереве, так как у вас еще нет способа воспроизвести его, но оно должно работать.

Функция возвращает функции и пороговые значения в нужном формате. Значение свойства равно -1, если узел не существует, и -2, если узел является листом.

Это работает путем обхода дерева и отслеживания текущей позиции.

...