Деревья python: Реализация графов и деревьев на Python / Хабр

Реализация графов и деревьев на Python / Хабр

Продолжаем публикацию наиболее интересных глав из книги Magnus Lie Hetland «Python Algorithms». Предыдущая статья расположена по адресу habrahabr.ru/blogs/algorithm/111858. Сегодня же речь пойдет об эффективной работе с графами и деревьями и особенностях их реализации в Python. Базовая терминология теории графов уже обсуждалась (например здесь: habrahabr.ru/blogs/algorithm/65367), так что я не включил часть главы о терминах в эту статью.

Реализация графов и деревьев

Многие задачи, например, задача обхода точек по кратчайшему маршруту, могут быть решены с помощью одного из мощнейших инструментов — с помощью графов. Часто, если вы можете определить, что решаете задачу на графы, вы по-крайней мере на полпути к решению. А если ваши данные можно каким-либо образом представить как деревья, у вас есть все шансы построить действительно эффективное решение.
Графами можно представить любую структуру или систему, от транспортной сети до сети передачи данных и от взаимодействия белков в ядре клетки до связей между людьми в Интернете.

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

Деревья — это просто особый вид графов, так что большинство алгоритмов и представлений графов сработают и для них.

Однако, из-за их особых свойств (связность и отсутствие циклов), можно применить специальные (и весьма простые) версии алгоритмов и представлений.

На практике в некоторых случаях встречаются структуры (такие как XML-документы или иерархия каталогов), которые могут быть представлены в виде деревьев (с учетом атрибутов IDREF и символьных ссылок XML-документы и иерархия каталогов становятся собственно графами). На самом деле эти «некоторые» случаи довольно-таки общие.

Описание задачи в терминах графов является довольно абстрактным, так что если вам нужно реализовать решение, вы должны представить графы в виде каких-либо структур данных. (Это придется делать даже при проектировании алгоритма и только, потому что нужно знать, сколько времени будут выполняться различные операции на представлении графа). В некоторых случаях граф будет уже составлен в коде или данных, так что отдельной структуры не потребуется. Например, если вы пишете веб-краулер, собирающий информацию о сайтах по ссылкам, графом будет сама сеть. Если у вас есть класс Person с атрибутом friends, являющимся списком других объектов типа Person, то ваша объектная модель уже будет графом, на котором можно использовать различные алгоритмы. Однако существуют и специальные способы представления графов.

В общих словах, мы ищем способ реализации функции смежности, N(v), так, чтобы N[v] было каким-либо набором (или в отдельных случаях просто итератором) смежных с v вершин. Как и во многих других книгах мы сосредоточимся на двух наиболее известных представлениях: списках смежности и матрицах смежности, потому что они наиболее полезны и обобщены. Альтернативные представления описаны в последнем разделе ниже.

«Черный ящик»: словари и множества

Существует техника, подробно описываемая в большинстве книг об алгоритмах, и неявно используемая программистами на Python, это — <em>хэширование</em>. Хэширование подразумевает вычисление целого числа (часто выглядящего как случайное), основанного на произвольном объекте. Потом это значение можно будет использовать, например, как индекс в массиве (после некоторых преобразований, чтобы не выйти за границы массива).

Стандартный механизм хэширования в Python представлен функцией hash:
>>> hash(42)
42
>>> hash("Hello, world!")
-1886531940
Этот механизм используется в словарях, реализованных как так называемые хэш-таблицы. Множества реализованы тем же способом. Важная особенность в том, что хэш может быть вычислен по существу за константное время (оно постоянно относительно размера хэш-таблицы, но линейно зависит от размера хэшируемого объекта). Если существует достаточно большой массив, то доступ к нему с помощью хэша в среднем занимает Θ(1). (В худшем случае это займет Θ(n), если только мы не знаем значений заранее и не напишем собственную хэш-функцию. Но в любом случае, на практике хэширование очень эффективно). 

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

Списки смежности и тому подобное

Один из наиболее очевидных способов представления графов — это списки смежности. Смысл их в том, что для каждой вершины создается список (или множество, или другой контейнер или итератор) смежных с ней вершин. Разберем простейший способ реализации такого списка, предположив, что имеется n вершин, пронумерованных 0… n-1.

Само собой, вершины могут быть представлены любыми объектами и иметь собственные метки или имена. Однако использование целых чисел в диапазоне 0… n-1 делает реализацию многих представлений проще, потому что в таком случае номера вершин можно использовать как индексы.

Таким образом, каждый список смежности является списком таких номеров, а сами эти списки собраны в главный список размера n, индексированный номерами вершин. Обычно сортировка таких списков случайная, так что речь в действительности идет об использовании списков для реализации множеств смежности. Термин список просто исторически устоялся. Python, к счастью, имеет отдельный тип для множеств, который во многих случаев удобно использовать.

Примерный граф, для которого будут показаны разные представления, изображен на рис. 1. Для начала положим, что все вершины пронумерованы (a=0, b =1, …). С учетом этого граф можно представить очевидным способом, как показано в следующем листинге. Чтобы было удобнее, я присвоил номера вершин переменным, названным в соответствии с метками вершин на рисунке. Но можно работать и прямо с числами. Какой вершине какой список принадлежит указано в комментариях. Если хотите, потратьте несколько минут, чтобы убедиться, что представление соответствует рисунку.

a, b, c, d, e, f, g, h = range(8)
N = [
	{b, c, d, e, f}, # a
	{c, e}, # b
	{d}, # c
	{e}, # d
	{f}, # e
	{c, g, h}, # f
	{f, h}, # g
	{f, g} # h
]

В версиях Python до 2.7 (или 3.0) нужно описывать множества как set([1, 2, 3]) вместо {1, 2, 3}. Но пустое множество в новых версиях по-прежнему записывается как set(), потому что {} объявляет пустой словарь.

Рис. 1. Примерный граф для демонстрации разных видов представления

Имя N из листинга связано с функцией N, описанной выше. В теории графов N(v) представляет множество смежных с v вершин. Так же и в нашем коде N[v] является множеством смежных с v вершин. Предполагая, что N определена как в примере выше, в интерактивном режиме Python можно поизучать это представление:

>>> b in N[a]  # смежная?
True
>>> len(N[f])  # степень
3

Совет:
Если у вас есть определенный код в файле, например, определение графа из листинга выше, и вы хотите запустить этот код в интерактивном режиме, как в предыдущем примере, вам нужно запустить python с ключом -i, например так:
python -i listing_2_1.py
Эта команда запустит код из файла и откроет интерактивный интерпретатор, который продолжит работать в том месте, где закончился код в файле, сохранив таким образом все сделанные раньше объявления.

Другим возможным представлением, которое в некоторых случаях даст меньше накладных расходов, являются собственно списки смежности. Пример такого списка приведен в листинге ниже. Доступны все те же операции, но проверка смежности вершины выполняется за Θ(n). Это дает серьезное снижение скорости, но если вам действительно требуется это представление, то это его единственная проблема. (Если все, что делает ваш алгоритм — это обход соседних вершин, то использование объектов типа множество не просто бессмысленно: накладные расходы могут ухудшить постоянные множители в асимптотике вашей реализации).

a, b, c, d, e, f, g, h = range(8)
N = [
	[b, c, d, e, f], # a
	[c, e], # b
	[d], # c
	[e], # d
	[f], # e
	[c, g, h], # f
	[f, h], # g
	[f, g] # h
]

Можно поспорить, что это представление на самом деле — набор массивов смежности, а не классические списки смежности, т.к. тип список в Python в действительности является динамическим массивом. Если хотите, вы можете реализовать тип связанного списка и использовать его вместо типа list из Python. Это может сделать дешевле в плане производительности произвольные вставки в список, но вам, вероятно, и не понадобится такая операция, потому что с тем же успехом можно добавлять новые вершины к концу списка. Преимущество использования встроенного list в том, что он представляет собой очень быструю и хорошо отлаженную структуру (в отличие от любых структур списков, которые можно реализовать на чистом Python).

При работе с графами постоянно всплывает идея о том, что лучшее представление зависит от того, что именно нужно сделать с графом. Например, используя списки (или массивы) смежности можно сохранить накладные расходы небольшими и обеспечить эффективный обход N(v) для любой вершины v. Однако, проверка, являются ли u и v смежными, потребует времени Θ(N(v)), что может стать проблемой при высокой плотности графа (т.е. при большом числе ребер). В этих случаях на помощь придут множества смежности.

Совет:

Известно, что удаление объектов из середины list в Python довольно затратно. Удаление с конца при этом происходит за константное время. Если вы не заботитесь о порядке вершин, то можете удалять случайную вершину за константное время перезаписывая ее той, что находится в конце списка смежности, и вызывая затем метод pop.

Небольшой вариацией на тему этого представления можно назвать сортированные списки смежных вершин. Если списки нечасто меняются, их можно держать отсортированными и использовать бисекцию для проверки смежности вершины, что приведет к немного меньшим накладным расходам (в плане использования памяти и времени итерации), но увеличит сложность проверки до Θ(log₂ k), где k — количество смежных с данной вершин. (Это все равно очень маленькое значение. На практике, впрочем, использование встроенного типа set доставляет гораздо меньше хлопот).

Еще одна небольшая доработка заключается в использовании словарей вместо множеств или списков. Смежные вершины могут быть ключам словаря, а в качестве значения можно использовать любые дополнительные данные, например, вес ребра. Как это выглядит можно увидеть в листинге ниже (веса выбраны случайно).

a, b, c, d, e, f, g, h = range(8)
N = [
	{b:2, c:1, d:3, e:9, f:4}, # a
	{c:4, e:3}, # b
	{d:8}, # c
	{e:7}, # d
	{f:5}, # e
	{c:2, g:2, h:2}, # f
	{f:1, h:6}, # g
	{f:9, g:8} # h
]

Словарь смежности можно использовать точно так же как и другие представления, с учетом дополнительной информации о весах:

>>> b in N[a]	# смежность
True
>>> len(N[f])	# степень
3
>>> N[a][b]		# вес (a, b)
2

Если хотите, можете использовать словари смежности даже если у вас нет полезных данных вроде весов ребер (используя None или другое значение вместо данных). Это даст вам все преимущества множеств смежности, но при этом будет работать с (очень-очень) старыми версиями Python, не имеющими поддержки типа set(множества были введены в Python 2.3 в виде модуля sets. Встроенный тип set доступен начиная с Python 2.4).

До этого момента сущность, хранящая структуры смежности — списки, множества или словари — была списком, индексированным номерами вершин. Более гибкий вариант (позволяющий использовать произвольные, хэшируемые, имена вершин) строится на базе словаря в качестве основной структуры (такие словари со списками смежности Гвидо ван Россум использовал в своей статье «Python Patterns — Implementing Graphs», выложенной по адресу www.python.org/doc/essays/graphs.html). Листинг ниже показывает пример словаря, содержащего множества смежности. Заметьте, что вершины в нем обозначены символами.

N = {
	'a': set('bcdef'),
	'b': set('ce'),
	'c': set('d'),
	'd': set('e'),
	'e': set('f'),
	'f': set('cgh'),
	'g': set('fh'),
	'h': set('fg')
}

Если из листинга выше выбросить конструктор set, то останутся строки смежности, которые будут работать как списки смежности (неизменяемые) из символов (с чуть меньшими накладными расходами). Казалось бы, далеко не лучшее представление, но, как и было сказано выше, все зависит от вашей программы. Откуда вы получаете данные для графа? (Может быть, они уже в виде текста?) Как вы собираетесь их использовать?

Матрицы смежности

Другая распространенная форма представления графов — это матрицы смежности. Основное отличие их в следующем: вместо перечисления всех смежных с каждой из вершин, мы записываем один ряд значений (массив), каждое из которых соответствует возможной смежной вершине (есть хотя бы одна такая для каждой вершины графа), и сохраняем значение (в виде True или False), показывающее, действительно ли вершина является смежной. И вновь простейшую реализацию можно получить используя вложенные списки, как видно из листинга ниже. Обратите внимание, что это также требует, чтобы вершины были пронумерованы от 0 до V-1. В качестве значений истинности используются 1 и 0 (вместо True и False), чтобы сделать матрицу читабельной.

a, b, c, d, e, f, g, h = range(8)
# a b c d e f g h
N =  [[0,1,1,1,1,1,0,0], # a
	 [0,0,1,0,1,0,0,0], # b
	 [0,0,0,1,0,0,0,0], # c
	 [0,0,0,0,1,0,0,0], # d
	 [0,0,0,0,0,1,0,0], # e
	 [0,0,1,0,0,0,1,1], # f
	 [0,0,0,0,0,1,0,1], # g
	 [0,0,0,0,0,1,1,0]] # h

Способ использования матриц смежности слегка отличается от списков и множеств смежности. Вместо проверки входит ли b в N[a], вы будете проверять, истинно ли значение ячейки матрицы N[a][b]. Кроме того, больше нельзя использовать len(N[a]), чтобы получить количество смежных вершин, потому что все ряды одной и той же длины. Вместо этого можно использовать функцию sum:

>>> N[a][b]
1
>>> sum(N[f])
3

Матрицы смежности имеют ряд полезных свойств, о которых стоит знать. Во-первых, так как мы не рассматриваем графы с петлями (т.е. не работаем с псевдографами), все значения на диагонали ложны. Также, ненаправленные графы обычно описываются парами ребер в обоих направлениях. Это значит, что матрица смежности для ненаправленного графа будет симметричной.

Расширение матрицы смежности для использования весов тривиально: вместо сохранения логических значений, сохраняйте значения весов. В случае с ребром (u, v) N[u][v] будет весом ребра w(u,v) вместо True. Часто в практических целях несуществующим ребрам присваиваются бесконечные веса. (Это гарантирует, что они не будут включены, например, в кратчайшие пути, т. к. мы ищем путь по существующим ребрам). Не всегда очевидно, как представить бесконечность, но совершенно точно есть несколько разных вариантов.

Один из них состоит в том, чтобы использовать некорректное для веса значение, такое как None или -1, если известно, что все веса неотрицательны. Возможно, в ряде случаев полезно использовать действительно большие числа. Для целых весов можно применить sys.maxint, хотя это значение и не обязательно самое большое (длинные целые могут быть больше). Есть и значение, введенное для отражения бесконечности: inf. Оно недоступно в Python напрямую по имени и выражается как float(‘inf’)(гарантируется, что это работает для Python 2.6 и старше. В ранних версиях подобные специальные значения были платформо-зависимы, хотя float(‘inf’) или float(‘Inf’) должны сработать на большинстве платформ).

Листинг ниже показывает, как выглядит матрица весов, реализованная вложенными списками. Использованы те же веса, что и в листинге выше.

a, b, c, d, e, f, g, h = range(8)
_ = float('inf')
		# a b c d e f g h
W = [[0,2,1,3,9,4,_,_], # a
 	 [_,0,4,_,3,_,_,_], # b
	 [_,_,0,8,_,_,_,_], # c
	 [_,_,_,0,7,_,_,_], # d
	 [_,_,_,_,0,5,_,_], # e
	 [_,_,2,_,_,0,2,2], # f
	 [_,_,_,_,_,1,0,6], # g
	 [_,_,_,_,_,9,8,0]] # h

Бесконечное значение обозначено как подчеркивание (_), потому что это коротко и визуально различимо. Естественно, можно использовать любое имя, которое вы предпочтете. Обратите внимание, что значения на диагонали по-прежнему равны нулю, потому что даже без учета петель, веса часто интерпретируются как расстояния, а расстояние от вершины до самой себя равно нулю.

Конечно, матрицы весов дают возможность очень просто получить веса ребер, но, к примеру, проверка смежности и определение степени вершины, или обход всех смежных вершин делаются иначе. Здесь нужно использовать бесконечное значение, примерно так (для большей наглядности определим inf = float(‘inf’)):

>>> W[a][b] < inf # смежность
True
>>> W[c][e] < inf # смежность
False
>>> sum(1 for w in W[a] if w < inf) - 1 # степень
5

Обратите внимание, что из полученной степени вычитается 1, потому что мы не считаем значения на диагонали. Сложность вычисления степени тут Θ(n), в то время как в другом представлении и смежность, и степень вершины можно определить за константное время. Так что вы всегда должны понимать, как именно вы собираетесь использовать ваш граф и выбирать для него соответствующее представление.

Массивы специального назначения из NumPy

Библиотека NumPy содержит много функциональности, связанной с многомерными массивами. Для представления графов большая ее часть не нужна, но массивы из NumPy весьма полезны, например, для реализации матриц весов или смежности.

Вместо создания пустой матрицы весов или смежности из списков для n вершин, вроде такого:
>>> N = [[0]*10 for i in range(10)]

в NumPy можно использовать функцию zeros:
>>> import numpy as np
>>> N = np.zeros([10,10])

Отдельные элементы доступны по индексам, разделенным запятой: A[u,v]. Чтобы получить соседние с данной вершины, используется одиночный индекс: A[u].
Пакет NumPy можно получить по адресу http://numpy.scipy.org.
Имейте ввиду, что вам нужна та версия NumPy, что будет работать с вашей версией Python. Если последний релиз NumPy не поддерживает ту версию Python, что вы используете, вы можете скомпилировать и установить библиотеку прямо из репозитория исходных кодов. Исходный код можно получить с помощью следующих команд (предполагается, что у вас установлена Subversion):
svn co http://svn.scipy.org/svn/numpy/trunk numpy
Больше информации о том, как компилировать и устанавливать NumPy, так же как и подробную документацию, можно найти на сайте библиотеки.

Реализация деревьев

Любое представление графов, естественно, можно использовать для представления деревьев, потому что деревья — это особый вид графов. Однако, деревья играют свою большую роль в алгоритмах, и для них разработано много соответствующих структур и методов. Большинство алгоритмов на деревьях (например, поиск по деревьям) можно рассматривать в терминах теории графов, но специальные структуры данных делают их проще в реализации.
Проще всего описать представление дерева с корнем, в котором ребра спускаются вниз от корня. Такие деревья часто отображают иерархическое ветвление данных, где корень отображает все объекты (которые, возможно, хранятся в листьях), а каждый внутренний узел показывает объекты, содержащиеся в дереве, корень которого — этот узел. Это описание можно использовать, представив каждое поддерево списком, содержащим все его поддеревья-потомки. Рассмотрим простое дерево, показанное на рисунке. 2.
Мы можем представить это дерево как список списков:

>>> T = [["a", "b"], ["c"], ["d", ["e", "f"]]]
>>> T[0][1]
'b'
>>> T[2][1][0]
'e'

Каждый список в сущности является списком потомков каждого из внутренних узлов. Во втором примере мы обращаемся к третьему потомку корня, затем ко второму его потомку и в конце концов — к первому потомку предыдущего узла (этот путь отмечен на рисунке).

Рис. 2. Пример дерева с отмеченным путем от корня к листу

В ряде случаев возможно заранее определить максимальное число потомков каждого узла. (Например, каждый узел бинарного дерева может иметь до двух потомков). Поэтому можно использовать другие представления, скажем, объекты с отдельным атрибутом для каждого из потомков как в листинге ниже.

class Tree:
	def __init__(self, left, right):
		self.left = left
		self.right = right
>>> t = Tree(Tree("a", "b"), Tree("c", "d"))
>>> t.right.left
'c'

Для обозначения отсутствующих потомков можно использовать None (в случае если у узла только один потомок). Само собой, можно комбинировать разные методы (например, использовать списки или множества потомков для каждого узла).

Распространенный способ реализации деревьев, особенно на языках, не имеющих встроенной поддержки списков, это так называемое представление «первый потомок, следующий брат». В нем каждый узел имеет два «указателя» или атрибута, указывающих на другие узлы, как в бинарном дереве. Однако, первый из этих атрибутов ссылается на первого потомка узла, а второй — на его следующего брата (т.е. узел, имеющий того же родителя, но находящийся правее, — прим. перев). Иными словами, каждый узел дерева имеет указатель на связанный список его потомков, а каждый из этих потомков ссылается на свой собственный аналогичный список. Таким образом, небольшая модификация бинарного дерева даст нам многопутевое дерево, показанное в листинге ниже.

class Tree:
	def __init__(self, kids, next=None):
		self.kids = self.val = kids
		self.next = next

Отдельный атрибут val здесь введен просто для того, чтобы получить понятный вывод при указании значения (например, «c») вместо ссылки на узел. Естественно, все это можно изменять. Вот пример того, как можно обращаться с этой структурой:

>>> t = Tree(Tree("a", Tree("b", Tree("c", Tree("d")))))
>>> t.kids.next.next.val
'c'

А вот как выглядит это дерево:

Атрибуты kids и next показаны пунктирными линиями, а сами ребра дерева — сплошными. Я немного схитрил и не стал показывать отдельные узлы для строк «a», «b» и т.д. Вместо этого я трактую их как метки на соответствующих родительских узлах. В более сложном дереве вместо использования одного атрибута и для хранения значения узла и для ссылки на список потомков, для обеих целей могут понадобиться отдельный атрибуты. Обычно для обхода дерева используется более сложный код (включая циклы и рекурсию), чем приведенный здесь с жестко заданным путем.

Шаблон проектирования «Набор»

При проектировании (да и реализации) таких структур данных как деревья может оказаться полезным гибкий класс, позволяющий задавать набор атрибутов через конструктор. Здесь нас может выручить шаблон проектирования «Набор» (названный так Алексом Мартелли в «Python Cookbook»). Есть много способов его реализации, но суть видна из следующего кода:
class Bunch(dict):
	def __init__(self, *args, **kwds):
		super(Bunch, self).__init__(*args, **kwds)
		self.__dict__ = self
Есть несколько полезных способов его применения. Во-первых, он позволяет создать и задать значения атрибутов, передав их как аргументы при создании объекта:
>>> x = Bunch(name="Jayne Cobb", position="PR")
>>> x.name
'Jayne Cobb'
Во-вторых, наследование от dict дает много дополнительного функционала, такого как получение всех ключей (атрибутов) или простая проверка наличия атрибута. Вот пример:
>>> T = Bunch
>>> t = T(left=T(left="a", right="b"), right=T(left="c"))
>>> t.left
{'right': 'b', 'left': 'a'}
>>> t.left.right
'b'
>>> t['left']['right']
'b'
>>> "left" in t.right
True
>>> "right" in t.right
False
Конечно же этот шаблон можно использовать не только для создания деревьев. Он пригодится в любой ситуации, где необходим гибкий объект, умеющий задавать свои атрибуты при создании.

Множество разных представлений

Несмотря на то, что существует масса представлений графов, большинство изучают и используют только два вида (с изменениями), уже описанных в этой главе. Джереми Спинред в своей книге «Effective Graph Representation» пишет, что его, как исследователя компьютерного представления графов, «особенно раздражают» большинство вводных статей. Приводимые в них описания хорошо известных представлений (списков и матриц смежности) обычно адекватны, но более общие объяснения нередко ошибочны. Как пример он показывает следующий ложный вывод о представлении графов, который основывается на неверных положениях из разных статей:
«Существует два метода представления графов в компьютере: списки и матрицы смежности. Работа с матрицами смежности быстрее, но они требуют больше памяти, чем списки смежности, так что вам нужно выбрать один из двух способов, исходя из того, какой ресурс для вас важнее» (стр. 9).

Спинред отмечает, что эти заключения сомнительны по нескольким причинам. Во-первых, есть много интересных способов представления графов, не только два описанных. Например, существуют списки ребер (или множества ребер), являющиеся списком всех ребер в виде пар вершин (или специальных объектов-ребер), существуют матрицы инцидентности, показывающие, какие ребра каким вершинам инцидентны (полезно для мультиграфов). Также существуют специальные методы для особых типов графов, вроде деревьев (описанных выше) и интервальных графов (здесь не рассматриваются). Полистайте книгу Спинреда, чтобы узнать о представлениях графов, которые вам могут когда-нибудь понадобиться.

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

Так что, вместо того, чтобы полагаться на простые обобщенные выводы, подобные описаным, нужно вникнуть в специфику своей задачи. Основным критерием, вероятно, будет асимптотическая сложность того, что вы делаете. Например, поиск ребра (u, v) в матрице смежности выполняется за Θ(1), а обход смежных с v вершин — за Θ(n), в то время как на списке смежности обе операции будут выполнены за Θ(d(v)), т.е. будут зависеть от количества смежных с данной вершин.

Если асимптотическая сложность вашего алгоритма не зависит от типа представления, вы можете провести какие-либо эмпирические тесты, описанные ранее в этой главе. Или, как часто и бывает, можно выбрать то представление, которое лучше сочетается с вашим кодом и проще в поддержке.

Важный способ использования графов, который еще не был затронут, не касается их представления. Дело в том, что во многих задачах данные уже имеют структуру графа, или даже дерева, и мы можем использовать для них соответствующие алгоритмы для графов и деревьев без создания специальных представлений. В ряде случаев это происходит, если представление графа составлено вне нашей программы. Например, при разборе XML-документов или обходе каталогов файловой системы древовидная структура уже создана и для нее существуют определенные API. Иными словами, мы неявно задаем граф. К примеру, чтобы найти наиболее эффективное решение для заданной конфигурации кубика Рубика, можно определить состояние кубика и методы его изменения. Но даже если явно не описывать и не сохранять каждую конфигурацию, возможные состояния сформируют неявный граф (или множество вершин) с ребрами — операторами изменения состояния. Дальше можно использовать такие алгоритмы, как A* или двунаправленный алгоритм Дейкстры, чтобы найти кратчайший путь до состояния решения. В таких случаях функция получения соседних вершин N(v) будет работать «на лету», вероятно, возвращая смежные вершины как коллекцию или другую форму объекта-итератора.

И последний тип графов, которого я коснусь в этой главе, называется графом подзадач. Это глубокая концепция, к которой я еще неоднократно буду обращаться, описывая различные техники построения алгоритмов. Вкратце, большинство задач может быть разложено на подзадачи: меньшие задачи, часто имеющие похожую структуру. Они формируют вершины графа подзадач, а их зависимости (т.е. какая подзадача от какой зависит) выражаются ребрами. И хотя алгоритмы на графы редко применяются на графах подзадач (они используются больше как инструмент анализа), такие графы отлично позволяют понять технику «разделяй и властвуй» и динамическое программирование.

Библиотеки для графов

Основных методов представления графов, описанных в этой главе, вероятно будет достаточно для большинства ваших задач на графы, особенно при некоторых изменениях. Однако, есть операции, реализация которых может быть неочевидной и запутанной, такие как временное скрытие вершин или их совмещение. Существуют сторонние библиотеки, которые реализуют эти методы и часть из них написана как расширения на C, что при использовании может дать прирост производительности. Они весьма удобны в применении, а в некоторых сразу реализовано несколько алгоритмов на графах. Поиск в интернете даст вам список активно разрабатываемых библиотек для графов, вот несколько для начала:
NetworkX: http://networkx.lanl.gov
python-graph: http://code.google.com/p/python-graph
Graphine: http://gitorious.org/projects/graphine/pages/Home

Кроме того, существуют Pygr, база данных графов (http://bioinfo.mbi.ucla.edu/pygr), Gato, набор инструментов для анимации графов (http://gato.sourceforge.net) и PADS, коллекция алгоритмов на графах (http://www.ics.uci.edu/~eppstein/PADS).

Напишем и поймем Decision Tree на Python с нуля! Часть 1. Краткий обзор / Хабр

Привет, Хабр! Представляю вашему вниманию перевод статьи «Pythonで0からディシジョンツリーを作って理解する　（1. 概要編）».

1.1 Что такое Decision Tree?

1.1.1 Пример Decision Tree

Например, у нас есть следующий набор данных (дата сет): погода, температура, влажность, ветер, игра в гольф. В зависимости от погоды и остального, мы ходили (〇) или не ходили (×) играть в гольф. Предположим, что у нас есть 14 сложившихся вариантов.

Из этих данных мы можем составить структуру данных, показывающую, в каких случаях мы шли на гольф. Такая структура из-за своей ветвистой формы называется Decision Tree.

Например, если посмотреть на Decision Tree, изображенный на картинке выше, мы поймем, что сначала проверяли погоду. Если было ясно, мы проверяли влажность: если она высокая, то не шли играть в гольф, если низкая — шли. А если погода была облачная, то шли играть в гольф вне зависимости от других условий.

1.1.2 Об этой статье

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

Эта статья — первая из серии. Следующие статьи:

(Прим. переводчика: “если вас заинтересует продолжение, пожалуйста, сообщите нам в в комментариях”.)

• Основы программирования на Python
• Необходимые основы библиотеки для анализа данных Pandas
• Основы структуры данных (в случае с Decision Tree)
• Основы информационной энтропии
• Учим алгоритм для генерации Decision Tree

1.1.3 Немного о Decision Tree

Генерация Decision Tree связана с машинным обучением с учителем и классификацией. Классификация в машинном обучении — способ, позволяющий создать модель, ведущую к правильному ответу, на основе обучении на дата сете с правильными ответами и ведущими к ним данными. Глубокое обучение (Deep Learning), которое в последние годы очень популярно, особенно в сфере распознавания изображений, тоже является частью машинного обучения на основе классификационного метода. Разница Deep Learning и Decision Tree в том, приводится ли конечный результат к форме, при которой человек понимает принципы генерации конечной структуры данных. Особенность Deep Learning — мы получаем конечный результат, но не понимаем принцип его генерации. В отличие от Deep Learning, принцип построения Decision Tree прост для понимания человеком, что также является его важной особенностью.

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

1.2 Об алгоритме ID3

ID3 — алгоритм генерации Decision Tree, разработанный в 1986 году Россом Куинланом. У него есть две важные особенности:

1. Категориальные данные. Это данные по типу нашего примера выше (пойду на гольф или не пойду), данные с определенным категорийным ярлыком. ID3 не может использовать численные данные.
2. Информационная энтропия — индикатор, который указывает на последовательность данных с наименьшей дисперсией свойств класса значений.

1.2.1 Об использовании численных данных

Алгоритм С4.5, который является более продвинутой версией ID3, может использовать численные данные, но так как базовая идея такая же, в этой серии статей, мы, для начала, будет использовать ID3.

1.3 Среда разработки

Программа, которую я описал ниже, я проверил и запустил в следующих условиях:

• Jupyter Notebooks (с использованием Azure Notebooks)
• Python 3.6
• Библиотеки: math, pandas, functools (не использовал scikit-learn, tensorflow и т.д.)

1.4 Пример программы

1.4.1 Собственно, программа

Для начала, скопируем программу в Jupyter Notebook и запустим.

import math
import pandas as pd
from functools import reduce

# Дата сет
d = {
    "Погода":["ясно","ясно","облачно","дождь","дождь","дождь","облачно","ясно","ясно","дождь","ясно","облачно","облачно","дождь"],
    "Температура":["Жарко","Жарко","Жарко","Тепло","Холодно","Холодно","Холодно","Тепло","Холодно","Тепло","Тепло","Тепло","Жарко","Тепло"], 
    "Влажность":["Высокая","Высокая","Высокая","Высокая","Норм","Норм","Норм","Высокая","Норм","Норм","Норм","Высокая","Норм","Высокая"],
    "Ветер":["Нет","Есть","Нет","Нет","Нет","Есть","Есть","Нет","Нет","Нет","Есть","Есть","Нет","Есть"],
    # Последний массив - это наша целевая переменная, показывающая результат, 
    # основывающийся на предыдущих данных.
    "Гольф":["×","×","○","○","○","×","○","×","○","○","○","○","○","×"],
}
df0 = pd.DataFrame(d)

# Лямбда-выражение для распределения значений, аргумент - pandas.Series, 
# возвращаемое значение - массив с количеством каждого из значений
# Из вводных данных s с помощью value_counts() находим частоту каждого из значений, 
# и пока в нашем словаре есть элементы, будет работать цикл, запускаемый items().
# Чтобы выходные данные не менялись с каждым запуском цикла, мы используем sorted, 
# который меняет порядок от большего к меньшему
# В итоге, генерируется массив, содержащий строку из следующих компонентов: ключ (k) и значение (v).
cstr = lambda s:[k+":"+str(v) for k,v in sorted(s.value_counts().items())]

# Структура данных Decision Tree
tree = {
    # name: Название этого нода (узла)
    "name":"decision tree "+df0.columns[-1]+" "+str(cstr(df0.iloc[:,-1])),
    # df: Данные, связанные с этим нодом (узлом)
    "df":df0,
    # edges: Список ребер (ветвей), выходящих из этого узла, 
    # или пустой массив, если ниже нет листового узла.
    "edges":[],
}

# Генерацию дерева, у узлов которого могут быть ветви, сохраняем в open
open = [tree]

# Лямба-выражение для вычесления энтропии. 
# Аргумент - pandas.Series、возвращаемое значение - число энтропии
entropy = lambda s:-reduce(lambda x,y:x+y,map(lambda x:(x/len(s))*math.log2(x/len(s)),s.value_counts()))

# Зацикливаем, пока open не станет пустым
while(len(open)!=0):
    # Вытаскиваем из массива open первый элемент,
    # и вытаскиваем данные, хранящиеся в этом узле
    n = open.pop(0)
    df_n = n["df"]

    # В случае, если энтропия этого узла равна 0, мы больше не можем вырастить из него новые ветви
    # поэтому прекращаем ветвление от этого узла
    if 0==entropy(df_n.iloc[:,-1]):
        continue
    # Создаем переменную, в которую будем сохранять список значений атрибута с возможностью разветвления
    attrs = {}
    # Исследуем все атрибуты, кроме последнего столбца класса атрибутов
    for attr in df_n.columns[:-1]:
        # Создаем переменную, которая хранит значение энтропии при ветвлении с этим атрибутом,
        # данные после разветвления и значение атрибута, который разветвляется.
        attrs[attr] = {"entropy":0,"dfs":[],"values":[]}
        # Исследуем все возможные значения этого атрибута. 
        # Кроме того, sorted предназначен для предотвращения изменения порядка массива, 
        # из которого были удалены повторяющиеся значения атрибутов, при каждом его выполнении.
        for value in sorted(set(df_n[attr])):
            # Фильтруем данные по значению атрибута
            df_m = df_n.query(attr+"=='"+value+"'")
            # Высчитываем энтропию, данные и значения сохрнаяем
            attrs[attr]["entropy"] += entropy(df_m.iloc[:,-1])*df_m.shape[0]/df_n.shape[0]
            attrs[attr]["dfs"] += [df_m]
            attrs[attr]["values"] += [value]
            pass
        pass
    # Если не осталось ни одного атрибута, значение которого можно разделить, 
    # прерываем исследование этого узла.
    if len(attrs)==0:
        continue
    # Получаем атрибут с наименьшим значением энтропии
    attr = min(attrs,key=lambda x:attrs[x]["entropy"])
    # Добавляем каждое значение разветвленного атрибута
    # и данные, полученные после разветвления, в наше дерево и в open.
    for d,v in zip(attrs[attr]["dfs"],attrs[attr]["values"]):
        m = {"name":attr+"="+v,"edges":[],"df":d.drop(columns=attr)}
        n["edges"].append(m)
        open.append(m)
    pass

# Выводим дата сет
print(df0,"\n-------------")
# Метод преобразования дерева в символы, аргуметы - tree:структура данных древа,
# indent:присоединяймый к дочернему узлу indent,
# Возвращаемое значение - символьное представление древа.
# Этот метод вызывается рекурсивно для преобразования всех данных в дереве в символы.
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
# Выводим древо в его символьном представлении.
print(tstr(tree))

1.4.2 Результат

Если запустить вышеописанную программу, наш Decision Tree будет представлен в виде символьной таблицы, как показано ниже.

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

1.4.3 Меняем атрибуты (массивы данных), которые хотим исследовать

Последний массив в дата сете d — это атрибут класса (массив данных, который хотим классифицировать).

d = {    
"Погода":["ясно","ясно","облачно","дождь","дождь","дождь","облачно","ясно","ясно","дождь","ясно","облачно","облачно","дождь"],    
"Температура":["Жарко","Жарко","Жарко","Тепло","Холодно","Холодно","Холодно","Тепло","Холодно","Тепло","Тепло","Тепло","Жарко","Тепло"],     
"Влажность":["Высокая","Высокая","Высокая","Высокая","Норм","Норм","Норм","Высокая","Норм","Норм","Норм","Высокая","Норм","Высокая"],    
"Гольф":["×","×","○","○","○","×","○","×","○","○","○","○","○","×"],}    
# Последний массив - это наша целевая переменная, показывающая результат, основывающийся на предыдущих данных.    
"Ветер":["Нет","Есть","Нет","Нет","Нет","Есть","Есть","Нет","Нет","Нет","Есть","Есть","Нет","Есть"],
}

Например, если поменять местами массивы “Гольф” и “Ветер”, как указано на примере выше, получится следующий результат:

decision tree Ветер ['Есть:6', 'Нет:8']
  Гольф=×
    Погода=ясно
      Температура=Жарко
        Влажность=Высокая['Есть:1', 'Нет:1']
      Температура=Тепло['Нет:1']
    Погода=Дождь['Есть:2']
  Гольф=○
    Погода=ясно
      Температура=Тепло['Есть:1']
      Температура=Холодно['Нет:1']
    Погода=облачно
      Температура=Жарко['Нет:2']
      Температура=Тепло['Есть:1']
      Температура=Холодно['Есть:1']
    Погода=Дождь['Нет:3']

По сути, мы создаем правило, при котором сообщаем программе, что разветвляться нужно сначала по наличию и отсутствию ветра и по тому, идем играть в гольф или нет.

Спасибо за прочтение!

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

Python — двоичное дерево — CoderLessons.com

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

• Один узел помечен как корневой узел.
• Каждый узел, кроме корневого, связан с одним родительским узлом.
• Каждый узел может иметь произвольный номер узла chid.

Мы создаем древовидную структуру данных в python, используя концептуальный узел os, обсуждавшийся ранее. Мы определяем один узел как корневой узел, а затем добавляем больше узлов как дочерние узлы. Ниже находится программа для создания корневого узла.

Создать Root

Мы просто создаем класс Node и добавляем присвоить значение узлу. Это становится деревом только с корневым узлом.

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data


    def PrintTree(self):
        print(self.data)

root = Node(10)

root.PrintTree()

Когда приведенный выше код выполняется, он дает следующий результат —

10

Вставка в дерево

Для вставки в дерево мы используем тот же класс узлов, созданный выше, и добавляем в него класс вставки. Класс вставки сравнивает значение узла с родительским узлом и решает добавить его в качестве левого узла или правого узла. Наконец, класс PrintTree используется для печати дерева.

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data

    def insert(self, data):
# Compare the new value with the parent node
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

# Print the tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()

# Use the insert method to add nodes
root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)

root.PrintTree()

Когда приведенный выше код выполняется, он дает следующий результат —

3 6 12 14

Обход дерева

Дерево может быть пройдено путем выбора последовательности для посещения каждого узла. Как мы ясно видим, мы можем начать с узла, затем сначала посетить левое поддерево, а затем — правое поддерево. Или мы также можем посетить правое поддерево первым и левое поддерево следующим. Соответственно существуют разные имена для этих методов обхода дерева. Мы изучим их подробно в главе, реализующей алгоритмы обхода дерева здесь. Алгоритмы обхода дерева

Деревья | Algorithms in Python

1. Что такое дерево? Свойства деревьев.
2. Бинарное дерево. Простейшая реализация на Python.

Что такое дерево?

Дерево – это такая структура данных, которая состоит из узлов и соединений между ними, и которая соответствует некоторым обязательным свойствам. Узлами могут быть любые объекты, с которыми связана какая-то информация. Дерево – это иерархическая структура данных, поэтому можно считать, что узлы бывают “родительские” и “дочерние“. Зависимость дочерних узлов от родительских и есть эти самые соединения. Отличительной характеристикой дерева например от графа является то, что в дереве существует только один путь между двумя узлами. Ниже на картинке показано простое дерево.

Сейчас уточню терминологию в такой структуре:

Зеленым показаны узлы дерева, у которых есть еще дочерние узлы
Красные узлы – это конечные узлы дерева, которые мы будем называть “листьями”
Соединения между узлами будем называть ветками.

Бинарное дерево.

Бинарное дерево – это дерево, в котором у каждого узла будет не больше двух дочерних узлов. Если некоторые узлы будут иметь только один дочерний узел, то такое дерево будет называться “неполное бинарное дерево”. На рисунке ниже – (а) – полное бинарное дерево, (б) – неполное бинарное дерево

Реализация бинарного дерева на Python.

class TreeNode:
    def __init__(self):
        self.data = ""
        self.left = -1
        self.right = -1

    #инициализируются связи нода, 
    #так как дерево бинарное, то
    #возможно только 2 дочерних узла
    def initNode(self, left, right):
        self.left = left
        self.right = right
    #устанавливаются какие-то данные ноду
    def set_data(self, data):
        self.data = data

class BinaryTree:
    #инициализация дерева
    #нужно обратить внимание на то
    #что для хранения узлов используется
    #тот же стандартный LIST
    def __init__(self):
        self.storage = []
        self.nodeNum = 0
    #добавление узла. Вся необходимая информация:
    #индексы дочерних узлов и данные
    def add_node(self, left, right, data):
        node = TreeNode()
        node.initNode(left, right)
        node.set_data(data)

В этом листинге показана возможность создавать классы в питоне. Обязательным методом в классе является __init__(self).
Он вызывается для инициализации объекта, который создается например при node = TreeNode

Я старался в этом сообщение дать просто общее понятие о том, что такое дерево для тех, кто никогда не встречал подобной организации данных и никогда с ними не работал. Поэтому я старался не углубляться в долгие объяснения и решил, что краткого описания и небольшого примера кода будет достаточно. В дальнейших сообщениях я еще вернусь к деревьям, так как они будут использоваться во многих местах начиная от Искусственного интеллекта и до проверки пересечения игрового объекта в компьютерной игре с фоном (стенки, пол и.т.д.) Т.е. в ближайшем будущем тема “Деревья” будет раскрыта с более практичной стороны.

Like this:

Like Loading…

Tags: binary tree, class, python, trees

гифа, деревья, повторяющиеся и дифференциальные линии (на Python) / Хабр

Введение

Паттерны всегда меня очаровывали. Даже не важно какие. Я экспериментировал со многими: сети, листья и их переплетения, ветви, молнии, флокирование, очертания фигур, реки, скальный осадок, пейзажи, слизистая плесень, лишайники, взаимодействие и расплавление, клеточные автоматы, некоторые фракталы и другие штуки. Мне кажется, что самое приятное — это то, как сложные и затейливые результаты можно получить от набора простых правил.

В последнее время мне были особенно интересны биологические образы и дифференциальный рост. У меня есть опыт в вычислительной математике, но не в биологии. Поэтому у меня мало знаний в том, как биологические системы работают. И всё же, я экспериментировал довольно много над воссозданием различных биологических закономерностей. Одна из сложностей заключается в том, чтобы попытаться воссоздать некоторые образы или закономерности максимально малым количеством простых правил.

Иногда мне удается воссоздать явление, которое я собирался создать, а иногда — нет. Чаще всего я получаю нечто интересное, даже если это не всегда то, что было задумано.

Признание

Буду честным перед вами, я иногда беру идею для своей работы из работ других художников. Особенно Джареда Тарбелла и Nervous System. К примеру, алгоритм, который я назвал Орбиталь (изображение ниже) сделан с очень сильной опорой на Happy Place Тарбелла.

Я указываю на это, потому что мне всегда было сложно понять, где программа, и в моем конкретном случае — изображения, генерируемые этой программой, достаточно уникальны, чтобы рассматриваться, как отдельная работа.

Inconvergent (несосредоточенный)

Я начал работать с генеративными алгоритмами, когда должен был готовиться к экзаменам в университете. Именно поэтому я купил домен inconvergent.net, насмехаясь над тем, как я уклоняюсь от учёбы. Первое, что я сделал — скопировал несколько алгоритмов Тарбелла с помощью Javascript/Canvas. Через некоторое время ко мне начали приходить уже собственные идеи.

Первым моим работающим алгоритмом, помимо Orbitals, был Hyphae. Он получился, когда я пытался воссоздать поведение гифы, сделанное Nervous System. На тот момент я не понимал, насколько сложный этот алгоритм на самом деле, и я потратил очень много времени, тщетно пытаясь сделать что-то сносное. Я все же смог сделать его, а еще вы можете прочитать работу Зигграфа (ENG) по этой теме, если интересно. Увлекательное чтиво!

Код

Я выкладываю почти весь свой код на Github. Все следующие разделы имеют ссылку на соответствующий репозиторий. К сожалению, не все из них хорошо документированы или обновлены.

HYPHAE (ГИФА) [GITHUB]

Я начал экспериментировать с системой, где я выращивал связанные друг с другом круги, которые не могли накладываться друг на друга. Работает это так: вы где-нибудь помещаете начальный (круг), и задаёте ему радиус и направление движения. Затем пытаетесь добавить новый узел по периметру первого узла в направлении движения. Важно иметь направление движения, чтобы было немного «колебания», и каждый раз угол немного отклонялся. Также обязательно каждый раз при добавление нового делаете радиус новых узлов немного меньше предыдущего.

Чтобы получить ветви, можно выбрать узлы наугад и попытаться вырастить новый узел более-менее перпендикулярно направлению движения ветви. И либо узлы столкнутся, либо вы получите новую ветку. Для более интересных результатов можно сделать углы отклонений пропорциональными ширине (радиусу) ветки. Более толстые ветки, как правило, прямее, чем тонкие. И вы, очевидно, можете сделать ещё много других вещей. Например, вы получите радикально разные результаты, если настроите то, сколько «гибких» ветвей вырастет по мере их утончения.

И ещё одно небольшое примечание: когда ветка откололась от существующей ветви, нужно сделать для нее радиус значительно тоньше ветви-предшественника. Вы можете увидеть это на деревьях в реальной жизни. Суть в том, что масса должна быть примерно одинаковой до и после пересечения ветки. (Я где-то вычитал это, но я не могу найти где).

Деревья [GITHUB]

Когда мы говорили о ветках, я понял, что можно упомянуть и маленький эксперимент с деревьями, ведь они похожи по сути.

Я хотел попробовать вырастить ветви таким же образом, как в Гифе, но только так, чтобы новые ветви появлялись только на «концах» других ветвей. К тому же, я не хотел обращать внимания на столкновения или что-нибудь подобное в этой симуляции. Получились не совсем деревья, но результат выглядит вполне реалистично, если не всматриваться сильно.

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

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

Повторяющиеся линии [GITHUB]

В отличие от Гифы, на которую меня вдохновила биология, и от алгоритмов деревьев, следующий пример основан на картинах, нарисованных рукой Джона Френзена. По большому счёту, Френзен рисует линии, где каждая линия следует по контуру ранее нарисованной линии. Каждая последующая линия будет немножко изменяться, и вскоре появляются интересные узоры.

Рисовать фигуры на компьютере довольно легко. Линия состоит из ряда вершин (точек) с ребром (сегментом) между ними. Для создания треугольника вам нужно взять три ребра и соединить их тремя вершинами. Чтобы нарисовать круг, нужно сделать то же самое, только нужно достаточно много вершин, чтобы было «невозможно» увидеть, что это на самомо деле не круг. Если у вас появилсиь сомнения в подходе, то сразу скажу, что есть более сложные и точные способы рисования форм, но этот достаточно прост и точен.

Это значит, что рисовать эти линии так же, как Френсен, можно путём рисования округлых фигур со множеством вершин. Отслеживание формы немного сложнее, но есть несколько способов, которые можно опробовать. Я хотел, чтобы поведение имитировало то, как в реальности рисуется фигура, мало-помалу, при этом продолжая предыдущие линии. Алгоритм, который я придумал работал не совсем так. То есть, он не избегал столкновений, но результаты все равно выглядели очень хорошо.

Чтобы проследить контур, можно выбрать некоторые из соседних рёбер в предыдущей линии, рассчитать среднее направление этих рёбер и добавить вершину к текущей линии вдоль этого направления. Затем добавить несколько случайных движений для имитации рисунка от руки. Некоторое время такой подход работает довольно хорошо, но есть некоторая «инертность», которую можно увидеть в результатах, форма адаптируется слишком медленно.

Количество шума, которое вы добавляете к каждой вершине, имеет решающее значение. Этот шум является тем, что заставляет всю систему создавать интересные формы, ибо коррекция формы вынуждает в процессе пытаться повторить как общее движение, так и некоторые случайные искажения.

Далее идет несколько более сложная система, которая тоже включает в себя линии.

Дифференциальная линия [GITHUB]

Дифференциал — это тот алгоритм, который я давно хотел сделать. В какой-то момент решение просто само возникло у меня в голове, и мне удалось заставить алгоритм работать. Я хотел создать систему, которая вела бы себя так же, как поверхности в природе, которые разворачиваются друг из друга. Например, как грецкие орехи или слои капусты, (не буду даже рассказывать, сколько времени я провел времени за гуглением изображений красной капусты, разрезанной пополам), наш кишечник и некотороые виды листьев и цветочных лепестков. И, вероятно, многие другие вещи.

Прежде чем я начал прикидывать способы, я видел только Floraform, созданный Nervous System, но вам стоит увидеть ещё Cellular Forms Энди Ломаса. Другой важный документ, который я обнаружил гораздо позже, находится здесь.

Сначала я попытался использовать метод, основанный на фрактальной кривой Коха. Но со случайным ростом, а не симметричным и регулярным, как во фрактале. Я так и не доделал и быстро сдался. Однако, через некоторое время (плюс-минус шесть месяцев), я понял, что мог бы ввести новые узлы, пока кривая Коха «растёт», но нужно заставить эти узлы смещаться относительно друг друга. Таким образом, они могли бы корректировать их позиции динамически, как жемчуг на верёвочке. Так они смогут держать нужное расстояние от других узлов (жемчужин).

Алгоритм выглядит следующим образом. Сначала мы создаем набор узлов, соединённых в какую-нибудь форму (круги или линии подойдут). Затем мы случайным образом вводим новые узлы между парами существующих узлов. В каждой итерации узлы будут пытаться оптимизировать свои позиции. Они будут «хотеть» быть рядом, но не слишком близко к своим двум соседям. В то же время они будут хотеть быть как можно дальше от всех других узлов. Обратите внимание, что здесь нет возможности их столкновения.

Есть ряд факторов, которые могут повлиять на поведение этой системы. Один из них — то, как часто мы вводим новые узлы. Другой — максимальное расстояние, в пределах которого узлы будут избегать друг друга. И самое интересное (на мой взгляд) — то, как мы выбираем, куда вставлять новые узлы. Мы можем сделать это равномерно, как в гифке выше, или мы можем расставить приоритетные места, где изгибы кривой будут более острыми, как в гифке ниже.

Разницу не очень легко заметить на данных примерах, но она становится очень заметной на больших симуляциях. На рисунке ниже использован метод вставки на основе кривизны, а создание заняло около 40 часов.

Еще один способ добиться интересных результатов от этого алгоритма — это покрасить кривую специально под каждый шаг во времени. Визуальные и текстурные результаты заметно отличаются, но легко распознать одни и те же характеристики системы.

А если генеративное искусство и визуализация данных, вас заинтересовали — посмотрите другие посты degenerative_art, вот самые популярные на данный момент:

Python — Дерево поиска — CoderLessons.com

Бинарное дерево поиска (BST) — это дерево, в котором все узлы следуют указанным ниже свойствам. Левое поддерево узла имеет ключ, меньший или равный ключу его родительского узла. Правое поддерево узла имеет ключ больше, чем ключ его родительского узла. Таким образом, BST делит все свои поддеревья на два сегмента; левое поддерево и правое поддерево и может быть определено как —

left_subtree (keys)  ≤  node (key)  ≤  right_subtree (keys)

Поиск значения в B-дереве

Поиск значения в дереве включает сравнение входящего значения со значением, выходящим из узлов. Здесь также мы пересекаем узлы слева направо, а затем, наконец, с родителем. Если искомое значение не совпадает ни с одним из значений выходного значения, то мы возвращаем не найденное сообщение, иначе возвращается найденное сообщение.

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data

# Insert method to create nodes
    def insert(self, data):

        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data
# findval method to compare the value with nodes
    def findval(self, lkpval):
        if lkpval < self.data:
            if self.left is None:
                return str(lkpval)+" Not Found"
            return self.left.findval(lkpval)
        elif lkpval > self.data:
            if self.right is None:
                return str(lkpval)+" Not Found"
            return self.right.findval(lkpval)
        else:
            print(str(self.data) + ' is found')
# Print the tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()


root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)
print(root.findval(7))
print(root.findval(14))

Когда приведенный выше код выполняется, он дает следующий результат —

Реализация дерева решений с использованием Python

import numpy as np

import pandas as pd

from sklearn.metrics import confusion_matrix

from sklearn.cross_validation import train_test_split

from sklearn.tree import DecisionTreeClassifier

from sklearn.metrics import accuracy_score

from sklearn.metrics import classification_report

def importdata():

    balance_data = pd.read_csv(

'https://archive.ics.uci.edu/ml/machine-learning-'+

'databases/balance-scale/balance-scale.data',

    sep= ',', header = None)

    print ("Dataset Length: ", len(balance_data))

    print ("Dataset Shape: ", balance_data.shape)

    print ("Dataset: ",balance_data.head())

    return balance_data

def splitdataset(balance_data):

    X = balance_data.values[:, 1:5]

    Y = balance_data.values[:, 0]

    X_train, X_test, y_train, y_test = train_test_split( 

    X, Y, test_size = 0.3, random_state = 100)

    return X, Y, X_train, X_test, y_train, y_test

def train_using_gini(X_train, X_test, y_train):

    clf_gini = DecisionTreeClassifier(criterion = "gini",

            random_state = 100,max_depth=3, min_samples_leaf=5)

    clf_gini.fit(X_train, y_train)

    return clf_gini

def tarin_using_entropy(X_train, X_test, y_train):

    clf_entropy = DecisionTreeClassifier(

            criterion = "entropy", random_state = 100,

            max_depth = 3, min_samples_leaf = 5)

    clf_entropy.fit(X_train, y_train)

    return clf_entropy

def prediction(X_test, clf_object):

    y_pred = clf_object.predict(X_test)

    print("Predicted values:")

    print(y_pred)

    return y_pred

def cal_accuracy(y_test, y_pred):

    print("Confusion Matrix: ",

        confusion_matrix(y_test, y_pred))

    print ("Accuracy : ",

    accuracy_score(y_test,y_pred)*100)

    print("Report : ",

    classification_report(y_test, y_pred))

def main():

    data = importdata()

    X, Y, X_train, X_test, y_train, y_test = splitdataset(data)

    clf_gini = train_using_gini(X_train, X_test, y_train)

    clf_entropy = tarin_using_entropy(X_train, X_test, y_train)

    print("Results Using Gini Index:")

    y_pred_gini = prediction(X_test, clf_gini)

    cal_accuracy(y_test, y_pred_gini)

    print("Results Using Entropy:")

    y_pred_entropy = prediction(X_test, clf_entropy)

    cal_accuracy(y_test, y_pred_entropy)

if __name__=="__main__":

    main()

1.10. Деревья принятия решений — документация scikit-learn 0.23.2

Деревья решений (DT) — это непараметрический метод обучения с учителем.
для классификации и регрессии. Цель состоит в том, чтобы создать модель, которая предсказывает ценность
целевая переменная путем изучения простых правил принятия решений, выведенных из данных
функции.

Например, в приведенном ниже примере деревья решений обучаются на основе данных
аппроксимировать синусоидальную кривую с набором правил принятия решения «если-то-иначе».Чем глубже
чем выше дерево, тем сложнее решающие правила и тем лучше модель.

Некоторые преимущества деревьев решений:

• Просто для понимания и интерпретации. Деревья можно визуализировать.

• Требуется небольшая подготовка данных. Другие методы часто требуют данных
  нормализации, необходимо создать фиктивные переменные и пустые значения для
  удалить. Однако обратите внимание, что этот модуль не поддерживает отсутствующие
  ценности.

• Стоимость использования дерева (т.е., прогнозирование данных) является логарифмическим по
  количество точек данных, используемых для обучения дерева.

• Может обрабатывать как числовые, так и категориальные данные. Другие техники
  обычно специализируются на анализе наборов данных только одного типа
  переменной. Смотрите алгоритмы для получения дополнительной информации
  Информация.

• Может обрабатывать проблемы с несколькими выходами.

• Использует модель белого ящика. Если данная ситуация наблюдается в модели,
  объяснение условия легко объясняется булевой логикой.Напротив, в модели черного ящика (например, в искусственной нейронной
  сеть), результаты может быть труднее интерпретировать.

• Можно проверить модель с помощью статистических тестов. Это делает это
  Можно учесть надежность модели.

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

К недостаткам деревьев решений можно отнести:

• Обучающиеся дерева решений могут создавать слишком сложные деревья, которые не
  хорошо обобщить данные.Это называется переобучением. Механизмы
  например, обрезка, установка минимального количества требуемых образцов
  на листовом узле или установка максимальной глубины дерева
  необходимо, чтобы избежать этой проблемы.

• Деревья решений могут быть нестабильными из-за небольших вариаций в
  данные могут привести к созданию совершенно другого дерева.
  Эта проблема смягчается за счет использования деревьев решений в
  ансамбль.

• Известно, что задача изучения дерева оптимальных решений
  NP-полная по нескольким аспектам оптимальности и даже для простых
  концепции.Следовательно, практические алгоритмы обучения дереву решений
  основаны на эвристических алгоритмах, таких как жадный алгоритм, где
  локально оптимальные решения принимаются на каждом узле. Такие алгоритмы
  не может гарантировать возврат глобально оптимального дерева решений. Эта
  можно смягчить путем обучения нескольких деревьев в ученике ансамбля,
  где функции и образцы выбираются случайным образом с заменой.

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

• Обучающиеся дерева решений создают предвзятые деревья, если некоторые классы доминируют.
  Поэтому рекомендуется сбалансировать набор данных перед подгонкой.
  с деревом решений.

1.10.1. Классификация

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

Как и другие классификаторы, DecisionTreeClassifier принимает на вход два массива:
массив X, разреженный или плотный, размером [n_samples, n_features] , содержащий
обучающие выборки и массив Y целых значений размером [n_samples] ,
с метками классов для обучающих выборок:

 >>> из дерева импорта sklearn
>>> X = [[0, 0], [1, 1]]
>>> Y = [0, 1]
>>> clf = дерево.DecisionTreeClassifier ()
>>> clf = clf.fit (X, Y)
 

После подбора модель можно использовать для прогнозирования класса образцов:

 >>> clf.predict ([[2., 2.]])
массив ([1])
 

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

 >>> clf.predict_proba ([[2., 2.]])
массив ([[0., 1.]])
 

DecisionTreeClassifier поддерживает как двоичные (где
метки — это [-1, 1]) классификация и мультикласс (где метки
[0,…, K-1]) классификация.

Используя набор данных Iris, мы можем построить дерево следующим образом:

 >>> из sklearn.datasets import load_iris
>>> из дерева импорта sklearn
>>> X, y = load_iris (return_X_y = True)
>>> clf = tree.DecisionTreeClassifier ()
>>> clf = clf.fit (X, y)
 

После обучения вы можете построить дерево с помощью функции plot_tree :

.

sklearn.tree.plot_tree — документация scikit-learn 0.23.2

.

Дерево решений машинного обучения Python

Дерево решений

В этой главе мы покажем вам, как создать «Дерево решений». Решение
Дерево — это блок-схема, которая может помочь вам принимать решения на основе предыдущего опыта.

В этом примере человек попытается решить, пойти ли ему на комедийное шоу или
не.

К счастью, наш примерный человек регистрировался каждый раз, когда комедийное шоу
в городе и зарегистрировали некоторую информацию о комике, а также
зарегистрирован, пошел он / она или нет.

Теперь на основе этого набора данных Python может создать дерево решений, которое можно использовать для принятия решения
стоит ли посетить какие-нибудь новые шоу.

Как это работает?

Сначала импортируйте необходимые модули и прочитайте набор данных с помощью pandas:

Пример

Прочтите и распечатайте набор данных:

импортировать панды
из дерева импорта sklearn
импортировать pydotplus
из
sklearn.tree import DecisionTreeClassifier
import matplotlib.pyplot as plt
импортировать matplotlib.image как pltimg

df = pandas.read_csv («shows.csv»)

print (df)

Пример запуска »

Чтобы построить дерево решений, все данные должны быть числовыми.

Мы должны преобразовать нечисловые столбцы «Национальность» и «Идти» в числовые значения.

Pandas имеет метод map () , который берет словарь с информацией о том, как
преобразовать значения.

{'UK': 0, 'USA': 1, 'N': 2}

Означает преобразование значений UK в 0, USA в 1 и N в 2.

Пример

Преобразование строковых значений в числовые:

d = {‘UK’: 0,
‘USA’: 1, ‘N’: 2}
df [‘Национальность’] = df [‘Национальность’].карта (d)
d =
{‘YES’: 1, ‘NO’: 0}
df [‘Go’] = df [‘Go’]. Map (d)

print (df)

.

Пример запуска »

Затем мы должны отделить столбец объекта от целевого столбца .

Столбцы характеристик — это столбцы, которые мы пытаемся предсказать из , и
целевой столбец — это столбец со значениями, которые мы пытаемся предсказать.

Пример

X — столбцы функций,
y — целевой столбец:

features = [‘Возраст’, ‘Опыт’, ‘Ранг’, ‘Национальность’]

X = df [features]
y = df [‘Go’]

print (X)
print (y)

Пример запуска »

Теперь мы можем создать реальное дерево решений, подогнать его под наши детали и сохранить
а.png на компьютере:

Пример

Создайте дерево решений, сохраните его как изображение и покажите изображение:

dtree = DecisionTreeClassifier ()
dtree = dtree.fit (X, y)
data =
tree.export_graphviz (dtree, out_file = None, feature_names = features)
graph =
pydotplus.graph_from_dot_data (data)
graph.write_png (‘mydecisiontree.png’)

img = pltimg.imread (‘mydecisiontree.png’)
imgplot = plt.imshow (img)
plt.show ()

Пример запуска »

Объяснение результата

Дерево решений использует ваши предыдущие решения для расчета вероятности того, что вы захотите пойти посмотреть.
комик или нет.

Давайте прочитаем различные аспекты дерева решений:

Рейтинг

Ранг <= 6,5 означает, что каждый комик с рейтингом 6,5 или
ниже будет следовать
Истинная стрелка (влево), а остальные будут
следуйте стрелке False (вправо).

джини = 0,497 относится к качеству
разделить и всегда представляет собой число от 0,0 до 0,5, где 0,0 означает все
образцы дали тот же результат, и 0.5 будет означать, что разделение сделано
ровно посередине.

образцов = 13 означает, что существует 13
комедианты остались на этом этапе решения, а это все они, поскольку это
первый шаг.

value = [6, 7] означает, что из этих 13
комедианты, 6 получат ответ "НЕТ", а 7 -
"ИДТИ".

Джини

Есть много способов разбить сэмплы, в этом уроке мы используем метод GINI.

В методе Джини используется эта формула:

Джини = 1 - (x / n) 2 - (y / n) 2

Где x - количество положительных ответов («ИДЕТ»),
n - количество выборок, а
y - количество отрицательных ответов («НЕТ»),
что дает нам такой расчет:

1 - (7/13) 2 - (6/13) 2 = 0.497

Следующий шаг содержит две коробки, одну коробку для комиков с «рангом»
6.5 или ниже, и одна коробка с остальными.

Правда - 5 комиков заканчивают здесь:

gini = 0,0 означает, что все образцы получили
тот же результат.

образцов = 5 означает, что есть 5 комиков
осталось в этой ветке (5 комиков с рейтингом 6.5 и ниже).

значение = [5, 0] означает, что 5 получит ответ «НЕТ»
и 0 получит "GO".

Ложь - 8 Комиков Продолжение:

Гражданство

Национальность <= 0,5 означает, что комики
со значением национальности менее 0,5 будет следовать стрелке влево
(что означает всех из Великобритании), а остальные будут следовать за стрелкой к
право.

джини = 0,219 означает, что около 22%
образцы пойдут в одном направлении.

образцов = 8 означает, что есть 8 комиков
осталось в этой ветке (8 комиков с рангом выше 6.5).

value = [1, 7] означает, что из этих 8
комедианты, 1 получит ответ «НЕТ», а 7 - «Вперед».

Правда - 4 комика Продолжение:

Возраст

Возраст <= 35,5 означает, что комедианты
в возрасте 35,5 лет и младше будут следовать за стрелкой влево, а остальные будут следовать за стрелкой к
право.

джини = 0,375 означает, что около 37,5%
образцы пойдут в одном направлении.

образцов = 4 означает, что есть 4 комика
остались в этой ветке (4 комика из Великобритании).

value = [1, 3] означает, что из этих 4
комедианты, 1 получит ответ «НЕТ», а 3 - «Вперед».

Ложь - 4 комика заканчивают здесь:

gini = 0,0 означает, что все образцы получили
тот же результат.

образцов = 4 означает, что есть 4 комика
остались в этой ветке (4 комика не из Великобритании).

value = [0, 4] означает, что из этих 4
комедианты, 0 получат «НЕТ», а 4 - «Вперед».

Правда - 2 комика здесь заканчиваются:

gini = 0,0 означает, что все образцы получили
тот же результат.

образцов = 2 означает, что есть 2 комика
остались в этом отделении (2 комика в возрасте 35,5 лет и младше).

value = [0, 2] означает, что из этих 2
комедианты, 0 получат «НЕТ», а 2 получат «Вперед».

Ложь - 2 комика Продолжение:

очков опыта

Опыт <= 9,5 означает, что комики
с опытом работы 9,5 или более лет будут следовать по стрелке влево, а остальные пойдут по стрелке в
право.

gini = 0,5 означает, что 50% выборок
пойдет в одном направлении.

образцов = 2 означает, что есть 2 комика
остались в этой ветке (2 комика старше 35.5).

value = [1, 1] означает, что из этих 2
комедианты, 1 получит «НЕТ», а 1 - «Вперед».

правда - 1 комик заканчивается здесь:

gini = 0,0 означает, что все образцы получили
тот же результат.

образцов = 1 означает, что есть 1 комик
осталось в этой ветке (1 комик с опытом работы не более 9,5 лет).

значение = [0, 1] означает, что 0 получит «НЕТ» и
1 получит "GO".

Ложь - 1 комик заканчивается здесь:

gini = 0,0 означает, что все образцы получили
тот же результат.

образцов = 1 означает, что есть 1 комик
ушел в эту ветку (1 комик с опытом работы более 9,5 лет).

значение = [1, 0] означает, что 1 получит «НЕТ» и
0 получит "GO".

Прогнозируемые значения

Мы можем использовать дерево решений для предсказания новых значений.

Пример: стоит ли мне пойти на шоу с участием 40-летнего американского комика с 10-летним опытом,
а комедийный рейтинг 7?

Пример

Используйте метод Forex () для прогнозирования новых значений:

печать (dtree.предсказать ([[40, 10, 7, 1]]))

Пример запуска »

Пример

Что бы вы ответили, если бы рейтинг комедии был 6?

print (dtree.predict ([[40, 10, 6, 1]]))

Пример запуска »

Разные результаты

Вы увидите, что дерево решений дает разные результаты, если вы запустите
это достаточное количество раз, даже если вы кормите его теми же данными.

Это потому, что дерево решений не дает нам 100% -ного ответа.Он основан на
вероятность исхода, и ответ будет разным.

.