Построить дерево зависимостей python

Построить дерево зависимостей из csv файла

Некоторые библиотеки просто воспринимают узлы (такие как root/log и log_info/log) как дубли. Может файл должен быть другого формата?

на Stack Overflow на русском вопросы принято задавать только на русском языке. Пожалуйста, переведите ваш вопрос на русский язык или воспользуйтесь Stack Overflow на английском.

Вот ошибки примерно такие anytree.search.CountError: Expecting 1 elements at maximum, but found 2. (Node(‘/root/log_info/log’), Node(‘/root/log’))

1 ответ 1

Зачем тратить время на библиотеки если можно самим накидать простенькое решение:

import csv def build_tree(data, parent): tree = <> for item in data: if item['parent'] == parent: child = item['child'] tree[child] = subtree = build_tree(data, child) if subtree: tree[child]['subtree'] = subtree return tree def print_tree(tree, indent=0): if indent == 0: print('root') for key, value in tree.items(): print(f'| <"|" if indent >0 else "">') print(f'| <"|" if indent >0 else "">--- [count=, lines=]') if value.get('subtree'): print_tree(value['subtree'], indent + 1) with open('test.csv', newline='') as csvfile: reader = csv.DictReader(csvfile) data = [row for row in reader] tree = build_tree(data, 'root') print_tree(tree) 

root | |--- log_info [count=1, lines=15] | | | |--- log [count=2, lines=154] | | | |--- log_format_msg [count=1, lines=86] | |--- log [count=1, lines=154] | | | |--- log_format_msg [count=1, lines=86] | |--- log_format_msg [count=1, lines=86] 

Источник

Реализация дерева зависимостей

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

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

Кроме того, поможет ли изучение теории графов? И есть ли какие-нибудь учебники по этому вопросу, предпочтительно с использованием Python в качестве языка?

5 ответов

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

Итак, теперь у вас есть куча модулей, которые становятся вашими вершинами. Допустим, у нас есть A и B, и мы знаем, что B зависит от A, поэтому есть направленный край — «дорога в один конец» — от A до B.

Если C зависит от B, то у вас есть A → B → C.

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

Я написал инструмент для поиска и отрисовки зависимостей между пакетами Python на PyPi. Это обжорство

И я использовал для анализа зависимостей какой-то библиотеки, которую я использую. Вот некоторые из диаграмм:

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

Говоря о том, как я это реализую, для поиска зависимостей пакетов я использую pip в качестве бэкенда , Для рисования диаграмм я использую Networkx.

1. Пройдите по старому дереву зависимостей. Создайте set из всех элементов в нем.
2. Пройдите по новому дереву зависимостей. Сделайте так же, как и раньше.
3. Вычтите последнее set из первого. Результатом является ваш ответ.

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

Первое проще в реализации, но менее эффективно. Последнее эффективно, но сложнее в реализации.

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

Это может представлять определенный интерес:

def dep(arg): ''' Dependency resolver "arg" is a dependency dictionary in which the values are the dependencies of their respective keys. ''' d=dict((k, set(arg[k])) for k in arg) r=[] while d: # values not in keys (items without dep) t=set(i for v in d.values() for i in v)-set(d.keys()) # and keys without value (items without dep) t.update(k for k, v in d.items() if not v) # can be done right away r.append(t) # and cleaned up d=dict(((k, v-t) for k, v in d.items() if v)) return r if __name__=='__main__': d=dict( a=('b','c'), b=('c','d'), e=(), f=('c','e'), g=('h','f'), i=('f',) ) print dep(d) 

Источник

Как разобраться в дереве принятия решений и сделать его на Python

Совсем скоро, 20 ноября, у нас стартует новый поток «Математика и Machine Learning для Data Science», и в преддверии этого мы делимся с вами полезным переводом с подробным, иллюстрированным объяснением дерева решений, разъяснением энтропии дерева решений с формулами и простыми примерами, вводом понятия «информационный выигрыш», которое игнорируется большинством умозрительно-простых туториалов. Статья рассчитана на любящих математику новичков, которые хотят больше разобраться в работе дерева принятия решений. Для полной ясности взят совсем маленький набор данных. В конце статьи — ссылка на код на Github.

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

Корневой узел — самый верхний узел в дереве решений называется корневой узел.
Узел принятия решения — подузел, который разделяется на дополнительные подузлы, известен как узел принятия решения.

Лист/терминальный узел — узел, который не разделяется на другие узлы, называется терминальный узел, или лист.

Набор данных

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

Представление набора данных

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

Вот так в дереве решений происходит разбиение.

Важные теоретические определения

Энтропия

Энтропия — это мера случайности или неопределенности. Уровень энтропии колеблется от 0 до 1 . Когда энтропия равна 0, это означает, что подмножество чистое, то есть в нем нет случайных элементов. Когда энтропия равна 1, это означает высокую степень случайности. Энтропия обозначается символами H(S).

Формула энтропии

Энтропия вычисляется так: -(p(0) * log(P(0)) + p(1) * log(P(1)))

Связь между энтропией и вероятностью

Когда энтропия равна 0, это означает, что подмножество «чистое», то есть в нем нет энтропии: либо все «да», либо все голоса «нет». Когда она равна 1, то это означает высокую степень случайности. Построим график вероятности P(1) вероятности принадлежности к классу 1 в зависимости от энтропии. Из объяснения выше мы знаем, что:

Если P(1) равно 0, то энтропия равна 0
Если P(1) равно 1, то энтропия равна 0
Если P(1) равно 0,5, то энтропия равна 1

Уровень энтропии всегда находится в диапазоне от 0 до 1.

Информационный выигрыш

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

Как работает дерево решений

В нашем наборе данных два атрибута, BMI и Age. В базе данных семь записей. Построим дерево решений для нашего набора данных.

1. Корневой узел

В дереве решений начнем с корневого узла. Возьмем все записи (в нашем наборе данных их семь) в качестве обучающих выборок.

В корневом узле наблюдаем три голоса за и четыре против.
Вероятность принадлежности к классу 0 равна 4/7. Четыре из семи записей принадлежат к классу 0.
P(0) = 4/7
Вероятность принадлежности к классу 1 равна 3/7. То есть три из семи записей принадлежат классу 1.
P(1) = 3/7.

Вычисляем энтропию корневого узла:

2. Как происходит разбиение?

У нас есть два атрибута — BMI и Age. Как на основе этих атрибутов происходит разбиение? Как проверить эффективность разбиения?

1. При выборе атрибута BMI в качестве переменной разделения и ≤30 в качестве точки разделения мы получим одно чистое подмножество.

Точки разбиения рассматриваются для каждой точки набора данных. Таким образом, если точки данных уникальны, то для n точек данных будет n-1 точек разбиения. То есть в зависимости от выбранных точки и переменной разбиения мы получаем высокий информационный выигрыш и выбираем разделение с этим выигрышем. В большом наборе данных принято считать только точки разделения при определенных процентах распределения значений: 10, 20, 30%. У нас набор данных небольшой, поэтому, видя все точки разделения данных, я выбрала в качестве точки разделения значения ≤30.

Энтропия чистого подмножества равна нулю. Теперь рассчитаем энтропию другого подмножества. Здесь у нас три голоса за и один против.

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

2. Выберем атрибут Age в качестве переменной разбиения и ≤45 в качестве точки разбиения.

Давайте сначала вычислим энтропию подмножества True. У него есть одно да и одно нет. Это высокий уровень неопределенности. Энтропия равна 1. Теперь рассчитаем энтропию подмножества False. В нем два голоса за и три против.

3. Рассчитаем информационный выигрыш.

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

Итак, мы создали дерево решений с чистыми подмножествами.

Напишем это на Python с помощью sklearn

1. Импортируем библиотеки.

import numpy as np import pandas as pd import matplotlib.pyplot as plt import seaborn as sns 

2. Загрузим данные.

df=pd.read_csv("Diabetes1.csv") df.head() 

3. Разделим переменные на x и y.

Атрибуты BMI и Age принимаются за x.
Атрибут Diabetes (целевая переменная) принимается за y.

x=df.iloc[. 2] y=df.iloc[:,2:] x.head(3) 

4. Построим модель с помощью sklearn

from sklearn import tree model=tree.DecisionTreeClassifier(criterion="entropy") model.fit(x,y) 

Вывод: DecisionTreeClassifier (criterion=«entropy»)

5. Оценка модели

Вывод: 1.0 . Мы взяли очень маленький набор данных, поэтому оценка равна 1.

6. Прогнозирование с помощью модели

Давайте предскажем, будет ли диабет у человека 47 лет с ИМТ 29. Напомню, что эти данные есть в нашем наборе данных.

Вывод: array([‘no’], dtype=object)
Прогноз — нет, такой же, как и в наборе данных. Теперь спрогнозируем, будет ли диабет у человека 47 лет с индексом массы тела 45. Отмечу, что этих данных в нашем наборе нет.

Вывод: array([‘yes’], dtype=object)

7. Визуализация модели:

Код и набор данных из этой статьи доступны на GitHub.

Приходите изучать математику к нам на курс «Математика и Machine Learning для Data Science» а промокод HABR, добавит 10 % к скидке на баннере.

Рекомендуемые статьи

Источник