Граф дерево в питоне

Напишем и поймем Decision Tree на Python с нуля! Часть 4. Структуры данных

Структура данных — это представление того, как организованы отдельные данные.

Массив

Отдельные данные представлены одним рядом. Чтобы идентифицировать один фрагмент данных, например, каким по порядку является этот отдельный фрагмент массива, необходим его идентификатор.

#Пример реализации массива в Python a = [2,6,4,5,1,8]

Таблица, двумерный массив

Данные выстроены в несколько столбцов, отдельные элементы двумерного массива также образуют строки.

Чтобы идентифицировать фрагмент данных в этом случае, требуются два идентификатора: например, номер столбца и номер элемента.

#Пример реализации таблицы в Python a = [ [2,6,4,5,1,8], [4,4,1,3,4,2], [5,3,6,6,5,3], [7,8,0,9,5,3], ]

Tree, древовидная структура

Это структура данных, где отдельные данные как будто связаны линией.

Эти линии являются маршрутом, напрямую соединяющим одни данные с другими. И один такой маршрут, например, и будет являтся древовидной структурой данных.

Часто такую структуру изображают как схему, напоминающую растущее сверху вниз дерево. Линии называются ребрами или ветвями, данные — узлами (node), данные, после которых линия не продолжается, называются листьями(leaf), а данные, располагающиеся на самом верху — корневым узлом или просто корнем.

# Пример реализации Tree в Python, содержащий список дочерних узлов. # Записывается в формате [Значение,список дочерних массивов]. Например, дерево с картинки выше будет записываться в порядке сверху вниз, слева направо. # Помимо подобной записи, существуют варианты с использованием классов, родительских нодов и другие. tree = \ [2,[ [6,[]], [4,[ [5,[ [6,[]], ]], [8,[]], [1,[]], ]], ]] # Функция для преобразования древовидной структуры в символьную def tstr(node,indent=""): s = indent+str(node[0])+"\n" for c in node[1]: # Цикл на дочернем ноде s += tstr(c,indent+"+-") pass return s print(tstr(tree)) # Вывод # 2 # +-6 # +-4 # +-+-5 # +-+-+-6 # +-+-8 # +-+-1 # Можно не создавать все дерево сразу, а создать несколько переменных для нодов # Создаем все ноды-листья. Цифра в переменной указывает на строку нода и его порядковый номер в этой строке слева направо. n10 = [6,[]] n21 = [8,[]] n22 = [1,[]] n40 = [6,[]] # Создаем родительские ноды для уже созданных дочерних. n20 = [5,[n40]] n11 = [4,[n20,n21,n22]] n00 = [2,[n10,n11]] # Выводим получившееся Древо, указав нод, который необходимо считать корневым. print(tstr(n11)) # Вывод # 4 # +-5 # +-+-6 # +-8 # +-1

Network или графы

Это структура, в которой у одного нода может быть несколько ребер. Отдельные данные также называются узлами, а линии — ребрами. Зачастую в графах нет корневого узла, как в древовидной структуре.

# Реализация графа на Python import pandas as pd # В нашем случае имя узла и его значение совпадают. # Если имя нода и его значение не совпадают, необходимо будет достать значение нода. nodes = [2,6,4,5,8,1] # Указываем связи между нодами в виде матрицы. Если от нода 2 (первая строка)к ноду 6 (вторая строка) исходит ребро, # Значение 1-ой строки 2-ого столбца матрицы будет 1, а если ребро не проходит, то - 0. Такая матрица называется матрица смежности. df = pd.DataFrame( [ # 2,6,4,5,8,1 [ 0,1,1,0,0,0], # от нода 2 [ 1,0,0,1,0,0], # от нода 6 [ 1,0,0,1,1,1], # от нода 4 [ 0,1,1,0,0,0], # от нода 5 [ 0,0,1,0,0,0], # от нода 8 [ 0,0,1,0,0,0], # от нода 1 ],columns=nodes,index=nodes) print(df) # Вывод # 2 6 4 5 8 1 # 2 0 1 1 0 0 0 # 6 1 0 0 1 0 0 # 4 1 0 0 1 1 1 # 5 0 1 1 0 0 0 # 8 0 0 1 0 0 0 # 1 0 0 1 0 0 0 # С помощью библиотек matplotlib и networkx рисуем граф. import matplotlib.pyplot as plt import networkx as nx plt.figure(figsize=(4,4)) plt.axis("off") nx.draw_networkx(nx.from_pandas_adjacency(df)) plt.show()

4.2 Пример реализации Decision Tree в Python

Decision Tree, как понятно из названия, может быть представлен в виде древовидной структуры.
В нодах хранятся следующие данные: список дочерних нодов, правила ветвления, путь от одного нода к другому в рамках Decision Tree.

Как показано ниже, корневой узел соединяет все данные. Числовое значение [. ], прикрепленное к узлу, представляет собой номер исходных данных, из которых создается это дерево решений. Из корневого узла “спускаются” вниз только те данные, которые удовлетворяют условиям дочерних узлов. Например, это видно, если посмотреть на узлы “иду на гольф” и “не иду на гольф” в первом дереве решений.

Реализация в python-е происходит, например, следующим образом. Делаем один узел ассоциативным массивом, name — это символьное представление состояния этого узла, df — это данные, связанные с этим узлом, а ребра — это список дочерних узлов.

# Данные древовидной структуры tree =

Функция tstr, текстифицирующая данную древовидную структуру, будет выглядеть следующим образом.

# Лямбда-выражение для распределения значений, аргумент - pandas.Series, возвращаемое значение - массив с количеством каждого из значений # Из вводных данных s с помощью value_counts() находим частоту каждого из значений, и пока в нашем словаре есть элементы, будет работать цикл, запускаемый items(). # Чтобы выходные данные не менялись с каждым запуском цикла, мы используем sorted, который меняет порядок от большего к меньшему # В итоге, генерируется массив, содержащий строку из следующих компонентов: ключ (k) и значение (v). cstr = lambda s:[k+":"+str(v) for k,v in sorted(s.value_counts().items())] # Метод текстификации дерева: аргумент - tree (структура данных дерева), indent (отступ дочерних узлов), # А возвращаемое значение будет текстовым отображением tree. Данный метод вызывается рекурсивно для преобразования всего в дереве в символы. def tstr(tree,indent=""): # Создаем символьное представление этого узла. # Если этот узел является листовым узлом (количество элементов в массиве ребер равно 0), # Частотное распределение последнего столбца данных df, связанных с деревом, преобразуется в символы. s = indent+tree["name"]+str(cstr(tree["df"].iloc[:,-1]) if len(tree["edges"])==0 else "")+"\n" # Зацикливаем все ветви этого узла. for e in tree["edges"]: # Добавляем символьное представление дочернего узла к символьному представлению родительского узла. # Добавляем еще больше символов к indent этого узла. s += tstr(e,indent+" ") pass return s

Decision Tree, текстифицированное функцией tstr, будет выглядеть следующим образом. В корневом узле отображается текст (decision tree Гольф), который мы задали в самом начале при создании переменной tree, а также частотное распределение «иду / не иду на гольф» со всех данных. Каждый узел представленный ниже, отображает правила ветвления, и в случае, если узел оказывается листовым, отображается частотное распределение «иду / не иду на гольф» на основе данных, связанных с этим узлом.

decision tree Гольф ['×:5', '○:9'] Погода=Ясно Влажность=Нормальная['○:2'] Влажность=Высокая['×:3'] Погода=Облачно['○:4'] Погода=Дождь Ветер=Есть['×:2'] Ветер=Нет['○:3']

Мы будем очень рады, если вы расскажете нам, понравилась ли вам данная статья, понятен ли перевод, была ли она вам полезна?

Источник

Граф дерево в питоне

Поиск значения в BST занимает O(log n) времени. Это означает, что можно очень быстро найти требуемое значение среди миллионов или даже миллиардов записей.

Предположим, мы ищем узел со значением x. Чтобы быстро найти его в BST, воспользуемся следующим алгоритмом:

1. Начать с корня дерева.
2. Если x = значению узла: остановиться.
3. Если x < значения узла: перейти к левому дочернему узлу.
4. Если x > значения узла: перейти к правому дочернему узлу.
5. Перейти к шагу 2.

При отсутствии уверенности в существовании искомого узла, необходимо изменить шаги 3 и 4 для остановки поиска.

Если хочешь подтянуть свои знания по алгоритмам, загляни на наш курс «Алгоритмы и структуры данных», на котором ты:

• углубишься в теорию структур данных;
• научишься решать сложные алгоритмические задачи;
• научишься применять алгоритмы и структуры данных при разработке программ.

Реализация

Создание узла TreeNode идентично созданию узла ListNode . Единственное отличие в том, что вместо одного атрибута у нас два: left и right , которые ссылаются на левые и правые дочерние узлы.

Эти три типа обхода могут быть реализованы следующими методами:

• с итерацией – использование цикла while и стека. В этом случае удаление данных возможно только с конца.
• с рекурсией – использование функции, которая вызывает сама себя.

Есть четвертый тип обхода – порядок уровней (level-order traversal). Этот способ использует очередь (queue). Удаление данных здесь возможно только с начала.

Для первых трех типов обработки узлов паттерны практически идентичны. Просто выберем обход в порядке возрастания. Ниже разберем итеративный и рекурсивный методы для LC 94: Binary Tree Inorder Traversal, начиная с итеративной версии:

Как правило, графы представлены в виде матриц смежности (adjacency matrix). Так, у приведенного выше графа будет следующая матрица.

Каждая строка и столбец представляют собой узел. Единица в строке i и столбце j , или A_=1 , означает связь между узлом i и узлом j .

A_=0 означает, что узлы i и j не связаны.

Ни один из узлов в этом графе не связан с самим собой. Следовательно, диагональ матрицы равна нулю. Аналогично, A_ = A_ , потому что связи ненаправленны. То есть если узел A связан с узлом B , то B связан с A . В результате матрица смежности симметрична по диагонали.

Рассмотрим пример, который поможет нам понять описанную выше теорию.

На представленных рисунках мы видим взвешенный граф с направленными ребрами. Обратите внимание, что связи больше не симметричны – вторая строка матрицы смежности пуста, потому что у B нет исходящих связей. Числа от 0 до 1 отражают силу связи. Например, граф C влияет на граф A сильнее, чем A на C .

Реализация

Реализуем невзвешенный и неориентированный граф. Основной структурой класса является список списков Python. Каждый из них – это строка. Индексы в списке представляют собой столбцы. При создании объекта Graph необходимо указать количество узлов n, чтобы создать список списков. Затем мы можем получить доступ к соединению между узлами a и b с помощью self.graph[a][b] .

Чтобы ответить на вопрос LC 323: Количество связных компонентов, изучим каждый узел графа. Далее «посетим» соседние графы. Повторяем операцию до тех пор, пока не встретим только те узлы, которые уже были замечены программой. После этого проверим наличие в графе узлов, которые еще не были замечены. Если такие узлы присутствуют, то существует еще как минимум один кластер, поэтому нужно взять новый узел и повторить процесс.

def get_n_components(self, mat: List[List[int]]) -> int: """ Учитывая матрицу смежности, возвращает количество связанных компонентов """ q = [] unseen = [*range(len(mat))] answer = 0 while q or unseen: # Если все соседние узлы прошли через цикл, переходим к новому кластеру if not q: q.append(unseen.pop(0)) answer += 1 # Выбираем узел из текущего кластера focal = q.pop(0) i = 0 # Поиск связей во всех оставшихся узлах while i < len(unseen): node = unseen[i] # Если узел подключен к центру, добавляем его в очередь # чтобы перебрать его соседей # из невидимых узлов и избежать бесконечного цикла if mat[focal][node] == 1: q.append(node) unseen.remove(node) else: i += 1 return answer

1. Строки 5-8: Создаем очередь ( q ), список узлов ( unseen ) и количество компонентов ( answer ).
2. Строка 10: Запускаем цикл while , который выполняем до тех пор, пока в очереди есть узлы, которые нужно обработать или узлы, которые не были замечены.
3. Строки 13-15: Если очередь пуста, удаляем первый узел из непросмотренных и увеличиваем количество компонентов.
4. Строки 18-19: Выбираем следующий доступный узел в очереди ( focal ).
5. Строка 22: Запускаем цикл while , который выполняем до тех пор, пока не обработаем все оставшиеся узлы.
6. Строка 23: Даем имя текущему узлу для оптимизации кода.
7. Строки 28-30: Если текущий узел подключен к центру, добавляем его в очередь узлов текущего кластера. Удаляем его из списка тех узлов, которые могут находиться в невидимом кластере. Благодаря этому действию, мы избегаем бесконечного цикла.
8. Строки 31-32: Если текущий узел не подключен к focal (центру), переходим к следующему узлу.

Заключение

Графы и деревья – основные структуры данных. Спектр их применения огромен. Например, графы используются там, где необходим алгоритм поиска решений. Реальный пример их использования – sea-of-nodes JIT-компилятора.

Деревья используются тогда, когда мы должны произвести быстрое добавление/удаление объекта с поиском по ключу. Например, в различных словарях и индексах БД (Баз данных). Кроме того, деревья являются неотъемлемой частью случайного леса – алгоритма машинного обучения.

В следующей части материала мы приступим к изучению хэш-таблиц.

Базовый и продвинутый курс «Алгоритмы и структуры данных» включает в себя:

1. Живые вебинары 2 раза в неделю.
2. 47 видеолекций и 150 практических заданий.
3. Консультации с преподавателями курса.

Материалы по теме

Источник