Decision tree

Привет, Хабр! Представляю вашему вниманию перевод статьи "Python01. ".

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 mathimport pandas as pdfrom 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 Treetree = {    # name: Название этого нода (узла)    "name":"decision tree "+df0.columns[-1]+" "+str(cstr(df0.iloc[:,-1])),    # df: Данные, связанные с этим нодом (узлом)    "df":df0,    # edges: Список ребер (ветвей), выходящих из этого узла,     # или пустой массив, если ниже нет листового узла.    "edges":[],}# Генерацию дерева, у узлов которого могут быть ветви, сохраняем в openopen = [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']

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

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

Привет, Хабр! Представляю вашему вниманию перевод статьи "Python02. Python".

Данная статья вторая в серии. Первую вы можете найти здесь.

2.1 Комментарии обозначаются # или ''' (три одинарные кавычки)

# Комментарийa = 1 # Комментарий ''' Это тоже комментарийb = cc = d'''

2.2 Использование динамической типизации (тип определяется автоматически)

# динамическая типизация переменных# = копирование значения справа налевоi = 1 #  целое число (int)f = 2.1 # число с плавающей запятой (float)s = "a" # строковый тип (string)b = True # логический тип (boolean)l = [0,1,2] # массив,список (array) t = (0,1,2) # кортеж (tuple)d = {"a":0, "b":1} # словарь, ассоциативный массивprint(i,f,s,b,l,t,d)# 1 2.1 a True [0, 1, 2] (0, 1, 2) {'a': 0, 'b': 1}# Когда хотим определить тип, используем typeprint(type(i)) # Вывод <class 'int'># Переменная не сохраняет, а содержит фактическое значение# Это, своего рода, переменная-ссылка, указывающая на местоположение значения# Можно получить идентификатор актуального значения через idprint(id(l)) # 00000000000000 (меняется от исполнения к исполнениюц)l2 = l # Приведу в пример копию массива, где ссылаюсь на 2 его элемента, а фактический массив - 1. print(id(l2)) # 00000000000000 (то же значение, что у вышеуказанного id(l))# Поскольку существует только один фактический массив, кажется, что он был добавлен в массив l, даже если вы добавили элемент со ссылкой на l2.l2.append(1)

2.3 Арифметические операторы (Вычисление и присвоение значений. Результат вычисления, как правило, помещается в переменную)

a = 1 # переменная а соответствует значению 1b = a # b так же соответствует 1 a = 2 # теперь а соответствует 2, но b не изменяетсяa += 1 # значение а увеличивается на 1 (на данном этапе а равно 3)a -= 1 # значение а уменьшается на 1 (на данном этапе а равно 2)a *= 2 # значение а увеличивается в два раза (на данном этапе а равно 4)a /= 3 # значение а составляет  предыдущего значения (на данном этапе а равно 1.3333333333333333)a = 1+2-3*4/5 # Вычисление в следующем порядке: умножение, деление, сложение, вычитание  a равно 0,6. (Однако, если учитывать погрешность, а равно 0.6000000000000001)

2.4 Создание группы программ через отступ

a = 0# Указываем условие выполнения группы программ, обозначенной отступом.# Далее прописываются условия, циклы, функционализация и т.д.if a == 1:    # Строка, которая смещена вправо на такую же величину в левой части строки от этой строки, составляет одну группу программ.    print(1)    print(2)    pass # Указание на конец группы с отступом    # при выполнении условия if выполняется группа программ до строки вышеprint(3) # вывод независимо от значения а, не подпадающий под условие if# вывод 3

2.4.1 Сгруппированным программам даётся контроль над выполнением операций

# Условие, позволяющее программе понять, запускаться или нетif условие :    # program group# Выполнение повторяется только для элементов массива# Элементы массива присваиваются переменной v в прямом порядкеfor v in массив    # program group# Выполнение продолжается только при соблюдении условийwhile условие:    # program group# Тайминг выполнение группы программ определяется позже# (в первую очередь нужно создать группу программ и дать им имена)def имя группы():    # program group    # После выполнения группы программ, возвращаем результат с помощью return    # Или можно вернуться к началу    return# Ниже описан пример с ошибкой# print(2) с измененным отступом будет относиться к другой группе программ# однако, program group 2 не имеет под собой никакого объясненияif a == 1:    # выполнение группы program group 1 регулируется условием if a==1:    print(1)        # в program group 2 нет регулирующей части, поэтому компилятор выдает ошибку.        print(2)

2.4.2 Формулировка условий

a = 1b = 2c = 2# переменные a и b одинаковы, но a и c разныеif a==b and a!=c:    print("отличается только с")# а больше или равно b (включает а=b) или а>c (не включает а=с)elif a>=b or a>c:    print("а больше или равно b или больше с")# не подходит под условия if и elifelse:    print("кроме этого")# выводит "кроме этого"

2.4.2.1 Другой пример написания условий

a = 1b = 2# если а=b, то v=0, если нет, то v=1v = 0 if a==b else 1print(v)# вывод 1 

2.4.3 Формирование циклов (for)

for v in [0,1,2,3]: # Следующая обработка повторяется для элементов [0,1,2,3]в массиве.    # Проходимся по массиву. Элементы массива выводятся через переменную v в прямом поряке   print(v)   pass # Обозначаем конец отступа# вывод 0 1 2 3# Используя enumerate, можно получить индекс и значение массива в итеративном процессе.for i,v in enumerate([5,3,7,8]):    # i - индекс, v - значение элемента    print("(",i,v,")")# вывод ( 0 5 ) ( 1 3 ) ( 2 7 ) ( 3 8 )# С помощью zip два массива могут быть объединены в один и обработаны итеративно.for v0,v1 in zip([1,2,3,4],[5,6,7,8]):    # v0 содержит элементы массива первого аргумента zip, а v1 содержит элементы второго аргумента.    print("(",v0,v1,")")# вывод ( 1 5 ) ( 2 6 ) ( 3 7 ) ( 4 8 )

2.4.4 Цикл while

a = 3# Пока a больше либо равно 0while a>=0:    print(a)    # Уменьшаем значение a на 1    a -= 1# вывод 3 2 1 0

2.4.5 Функции и методы

# Определение функции: Название - function_name, аргументы: param1 и param2, param2 - аргумент по умолчанию# В случае, если аргумент не установлен, при вызове функции его значение будет равно 1 (значению по умолчанию)def function_name(param1,param2=1):    print("p1:",param1,"p2",param2)    # Эта функция возращает сумму аргументов param1 и param2    return param1 + param2# вызов функции (на данном этапе впервые запускается function_name)# значение param1 = 5,  param2 не устанавливается (используется аргумент по умолчанию)v = function_name(5)# вывод (вывод с помощью оператора print в функции function_name) p1: 5 p2 1print("возвращаемое значение",v)()# вывод "возвращаемое значение 6"

2.4.5.1 Лямба-выражение, пример написания функции

# название функции = lambda (входные аргументы) : (возвращаемое значение) - по такому принципу описывается функция.f = lambda x: x*x# Вызов функции происходит так же, как и в примере с defv = f(2)print(v) # отобразится 4

2.5 Преобразование строки в число

si = "1"   #Строкаsf = "2.3" #Строкаi = 4      #Целое число# Преобразовываем целое число i в строку, происходит конкатенация строкprint(str(i)+si)# 41# Обратная ситуация - преобразовываем строку si в целое число(int), происходит арифметическое сложениеprint(i+int(si))# 5# Преобразовываем строку в число с плавающей запятой (float), опять же происходит сложение (число при выводе автоматически заменяется на float)print(i+float(sf))# 6.3

2.6 Массив, список

# Создание массиваa = [1,1,2,3,2]              # a=[1,1,2,3,2]b = [n for n in range(8)]  # b=[0, 1, 2, 3, 4, 5, 6, 7]# Ссылка# Отрицательные значения становятся индексами, которые выссчитываются с -1 в качестве последнего элементаv = a[0]  # v=1v = a[-1] # v=2# Добавлениеa += [4]     # a=[1, 1, 2, 3, 2, 4]a.append(5)  # a=[1, 1, 2, 3, 2, 4, 5]# Извлечение (перед выполнением a=[1, 1, 2, 3, 2, 4, 5])v = a.pop(0) # v=1, a=[1, 2, 3, 2, 4, 5]# Вырезание (перед выполнением a=[1, 2, 3, 2, 4, 5])# a[первый индекс: предпоследний индекс]# если индексы не прописывать, а оставить просто a[:], первоначальный индекс автоматически станет  равен 0, последний - количество элементов)c = a[1:3] # c=[2, 3]# Максимумминимум (перед выполнением а= [1, 2, 3, 2, 4, 5])mx,mi = max(a),min(a) # mx=5, mi=1# Среднее значение(mean)Медианное значение(median)Наиболее частое значение(mode)Стандартное отклонение(stdev)Дисперсия(variance)# (перед выполнением a=[1, 2, 3, 2, 4, 5])from statistics import mean,median,mode,stdev,variancev = mean(a) # v=2.8333333333333335v = median(a) # v=2.5v = mode(a) # v=2v = stdev(a) # v=1.4719601443879744v = variance(a) #v=2.1666666666666665# Удаление повторений(перед выполнением a=[1, 2, 3, 2, 4, 5])c = set(a) # c={1, 2, 3, 4, 5}# SortedСоздается новый упорядоченный массив(перед выполнением a=[1, 2, 3, 2, 4, 5])c = sorted(a) # c=[1, 2, 2, 3, 4, 5] (массив a остается без изменений)# Sortупорядочивает элементы массива(перед выполнением a=[1, 2, 3, 2, 4, 5])a.sort()      # a=[1, 2, 2, 3, 4, 5]# Одинаково преобразует все элементы массиваmapping (перед выполнением a=[1, 2, 2, 3, 4, 5])# используем лямбда-выражение x: x+2.Значение элемента x меняется на x+2.# list преобразует вывод функции map в массивc = list(map(lambda x:x+2,a)) #c=[3, 4, 4, 5, 6, 7]# Фильтр(перед выполнением a=[1, 2, 2, 3, 4, 5])# используем лямбда-выражение x: x%2==0# Ищется элемент xкоторый делится на два без остатка. Подходящие элементы образуют новый массивc = list(filter(lambda x:x%2==0,a)) #c=[2, 2, 4]# Из всех элементов массива создается одно значение по заданным условиям# x - изначальное значениеесли запускаем цикл, х - значение первого элемента массива# xi - объект текущей операцииfrom functools import reduce# задаем x+xi, получаем сумму всех элементов массиваперед выполнением a=[1, 2, 2, 3, 4, 5]c = reduce(lambda x,xi:x+xi,a) #c=17# задаем max(xi,x), получаем наибольшее значение среди элементов массиваперед выполнением a=[1, 2, 2, 3, 4, 5]c = reduce(lambda x,xi:max(x,xi),a) #c=5

2.7 Словарь (dictionary)ассоциативный массив

# Создание. Ключи - Родной язык, Математика, Английский язык, а значения - массивыd = {    "Родной язык" : [81, 60, 97, 96],    "Математика" : [80, 78, 75, 96],    "Английский язык" : [76, 85, 65, 88],}print(d)# вывод {'Родной язык': [81, 60, 97, 96], 'Математика': [80, 78, 75, 96], 'Английский язык': [76, 85, 65, 88]}# Инициализация с использованием ford1 = {name:[0,1] for name in ["Родной язык","Математика","Английский язык"]}# вывод {'Родной язык': [0, 1], 'Математика': [0, 1], 'Английский язык': [0, 1]}# Получение значений через указание ключаa = d["Математика"] # a=[80, 78, 75, 96]# Замена значений через укзание ключаПерезаписьd["Английский язык"] = [77, 61, 91, 87] # d["Английский язык"]=[77, 61, 91, 87]# Цикл данныхfor k,v in d.items():    print(k,v)# вывод Родной язык [81, 60, 97, 96] Математика [80, 78, 75, 96] Английский язык [77, 61, 91, 87]# Максимальное значениеМинимальное значениев случае с ключом Родной языкjmx,jmi = max(d["Родной язык"]),min(d["Родной язык"])#print(jmx,jmi)# Находим название предмета с наивысшим средним значениемfrom statistics import mean# В массивах типа словарь при использовании max можно в качестве ключевого аргумента указать функцию, определяющую, среди чего искать максимальное значение# В этом случае лямбда-выражение используется для вычисления среднего значения из аргумента k(значение ключа в словаре)kmx = max(d,key=lambda k:mean(d[k])) # kmx="Родной язык"

2.8 Файловая операция with open

# with, файловая операция# with автоматизирует завершение процессов, требующих запуска и завершения.# Например, файл, открытый с помощью open, необходимо закрыть с помощью вызова функции close # Если использовать with и открыть файл с помощью open, при выходе из диапазона with функция close вызовется автоматически.# mode - r: чтениеw: записьa: дополнительная запись# Возвращаемое значение, которое мы получаем с помощью open, назовем fwith open("09_memo.txt",mode="a") as f:    # Записываем в файл    f.write("\n")# Чтение файлаwith open("09_memo.txt","r") as r:    print(r.read())

2.9 Случайное число random

# Использование случайных чиселimport random# Инициализация генерации случайных чисел# Случайные числа позволяют генерировать одну и ту же последовательность случайных чисел несколько раз для экспериментальной воспроизводимости.# Если аргумент seed указать численно, всегда будет выводиться одно и то же число.random.seed(0)# Генерация случайных чисел больше или равных 0 и меньше 1.print(random.random()) # Вывод 0.8444218515250481# Создает случайные целые числа больше первого аргумента и меньше второго аргумента.print(random.randint(1,3)) # Вывод одного числа из 1,2,3# Произвольно выбирает число из массиваprint(random.choice([0,1,2])) # Вывод одного числа из 0,1,2# Извлечение нескольких данных из массива# Вторым аргументом указывается количества выводимых данныхprint(random.sample([0,1,2],2)) # Выводимый массив [1, 2]# Перемешиваем данные в массиве# Новый массив не создается - данные перемешиваются непосредственно в массиве аa = [0,1,2]random.shuffle(a)print(a) # вывод [0, 2, 1]print(random.sample(a,len(a))) # Для создания нового массива можно использовать sample

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

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

Данная статья четвертая в серии. Ссылки на предыдущие статьи: первая, вторая, третья

4.1 Структуры данных

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

Массив

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

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

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

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

#Пример реализации таблицы в Pythona = [   [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 sprint(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 или графы

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

# Реализация графа на Pythonimport 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 pltimport networkx as nxplt.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 = {      # name: название этого узла      "name":"decision tree "+df0.columns[-1]+" "+str(cstr(df0.iloc[:,-1])),      # df: данные, связанные с данным узлом      "df":df0,# edges: список ребер (ветвей), выходящих из данного узла. Если узел листовой, то есть если ребер у него нет, массив остается пустым.    "edges":[],}

Функция 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+"  ")passreturn s

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

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

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

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

Данная статья пятая в серии. Ссылки на предыдущие статьи: первая, вторая, третья, четвертая

5.1 Информационная энтропия (Средний объем информации)

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

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

5.1.1 Определяем понятие объем информации

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

Например, знание правильного ответа из пяти предложенных вариантов, по объему информации больше, чем знание правильного ответа из двух вариантов.

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



Когда вероятность того, что событие E произойдет, равна P (E), объем информации I (E), который знает, что событие E произошло, определяется следующим образом.

I(E)=log2(1/P(E))=log2P(E)

5.1.2 Что такое информационная энтропия (средний объем информации)

У любого атрибута есть несколько значений. Например атрибут Погода представлен в 3 вариантах: Ясно, Облачно, Дождь. Среднее значение атрибутов того объема информации, который был получен из каждой вероятности появления события и называется энтропией (средним объемом информации).

В следующей формуле она представления буквой Н.

H=EP(E)log2P(E)

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



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

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



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

5.2 Вычисление информационной энтропии

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

entropy = lambda df:-reduce(lambda x,y:x+y,map(lambda x:(x/len(df))*math.log2(x/len(df)),df.iloc[:,-1].value_counts()))

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

entropy = lambda df:-reduce( #4.reduce создает одно значение из всех элементов массива.    lambda x,y:x+y,#5.Складываем значения энтропии, полученные из индивидуальных значений (9,5).    map( #2.Преобразовываем число (9,5) частотного массива (["": 9, "": 5]) в энтропию согласно следующему лямбда-выражению        lambda x:(x/len(df))*math.log2(x/len(df)),#3.Вычисляем P(E)log2(P(E))        df.iloc[:,-1].value_counts() #1.Частота последнего столбца DataFrameнапример:["":9,"":5]    ))

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

1. df.iloc[:,-1]извлекает последний столбец DataFrame, а value_counts дает его частотное распределение (пример частотного распределения: ["": 9, "": 5])
2. map преобразует каждое из значений частотного распределения (например, 9,5) в значения энтропии.
3. (x / len (df)) * math.log2 (x / len (df)) вычисляет формулу P (E) log2P (E) для одного значения энтропии.
4. reduce используется для создания единого значения из всех элементов массива. Например, его можно использовать для расчета сумм, средних значений и т. д.
5. Лямбда-выражение x, y: x + y дает сумму двух аргументов (x, y), то есть сумму массивов. Это часть с сигмой в формуле энтропии (EP(E)log2P(E)). Так как выражение имеет минус в начале, оно также имеет минус перед reduce в программе.

5.2.1 Вычисление информационной энтропии

Информационная энтропия для следующих данных составляет 0,9402859586706309.

d = {"Гольф":["","","","","","","","","","","","","",""]}# Энтропия равна 0.9402859586706309

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

d = {"Гольф":["","","","","","","","","","","","","",""]}# Энтропия равна 0.74959525725948

Ниже приведен список всех программ, вычисляющих информационную энтропию.

import pandas as pdfrom functools import reduceimport mathd = {"Гольф":["","","","","","","","","","","","","",""]}df0 = pd.DataFrame(d)entropy = lambda df:-reduce(    lambda x,y:x+y,    map(        lambda x:(x/len(df))*math.log2(x/len(df)),        df.iloc[:,-1].value_counts()    ))print(entropy(df0)) # Вывод 0.9402859586706309

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

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