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

Original author: 豊久 中田
  • Translation
Привет, Хабр! Представляю вашему вниманию перевод статьи "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']

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

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

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

Similar posts

Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 8

    +1
    Пролог на питоне?
      0
      Да, весь код в статье на питоне!
        0

        Нет, комментатор выше имел в виду "пролог" не как "начало статьи", а как "язык программирования высокого уровня". Я Пролог только в институте проходил, но описанное в статье очень сильно напоминает программы на Прологе.


        Спасибо за перевод с японского, это было неожиданно. :)

          +1
          О, спасибо, что поправили, не понял вопроса :)

          Вам спасибо за интерес!
          Надеюсь, следующие публикации будут не менее интересными для вас :)
      +1
      Как раз недавно интересовался decision trees, обрадовался, увидев вашу статью, думал — понравится, почитаю остальное в оригинале. А потом долго грустно смотрел на ссылку на оригинал :)
        +1
        Не переживайте, я думаю, мы допереведем цикл этих статей, сможете ознакомиться на русском! :)
        0
        Скажите, а вы не знаете, есть ли перевод этой статьи на английский (или немецкий)?
        Хотел поделиться с русско-неговорящим коллегой, но японского он тоже не знает…
          0
          Добрый день!
          К сожалению, серия этих статей в оригинале написана на японском, на английском-немецком нам не встречались. :(

        Only users with full accounts can post comments. Log in, please.