Python decision tree algorithm

Напишем и поймем 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] = # Исследуем все возможные значения этого атрибута. # Кроме того, 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']

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

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

Источник