Статьи

Coding Quickie: Классификация дерева обучения

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


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

 

В коде я пишу это так: 
dataset = {
  "headers"=>["Number of Wheels","Number of Doors","Miles/Gallon", "Type of Auto"],
  "data" => [
    [4, 4,'21-40', 'Car'],
    [2, 0,'41-60', 'Motorcycle'],
    [4, 2,'11-20', 'Truck'],
    [16, 2,'1-10', 'Big Rig'],
    [4, 2,'21-40', 'Car'],
    [8, 2,'1-10', 'Big Rig'],
    [4, 4,'41-60', 'Hybrid Car'],
  ]
}

Как бы вы организовали данные, чтобы сделать их более понятными?

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

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

Вот код, который я перенес с Python на Ruby:
 
def calculate_shannon_entropy data, header_index
  number_of_entries = data.length
  label_counts = {}
  data.each do |row|
    current_label = row[header_index]
    label_counts[current_label] = 0 if not label_counts.has_key? current_label
    label_counts[current_label] += 1
  end
  shannon_entropy = 0.0
  label_counts.each do |key, value|
    frequency = value.to_f / number_of_entries.to_f
    shannon_entropy -= frequency * Math.log(frequency,2)
  end
  shannon_entropy
end

С помощью созданного мной алгоритма получается следующая иерархия:
{
  "Number of Doors"=>{
    4=>{
      "Number of Wheels"=>{
        4=>{
          "Miles/Gallon"=>{
            "21-40"=>{
              "Type of Auto"=>[["Car"]]
            },
            "41-60"=>{
              "Type of Auto"=>[["Hybrid Car"]]
            }
          }
        }
      }
    },
    0=>{
      "Number of Wheels"=>{
        2=>{
          "Miles/Gallon"=>{
            "41-60"=>{
              "Type of Auto"=>[["Motorcycle"]]
            }
          }
        }
      }
    },
    2=>{
      "Number of Wheels"=>{
        4=>{
          "Miles/Gallon"=>{
            "11-20"=>{
              "Type of Auto"=>[["Truck"]]
            },
            "21-40"=>{
              "Type of Auto"=>[["Car"]]
            }
          }
        },
        16=>{
          "Miles/Gallon"=>{
            "1-10"=>{
              "Type of Auto"=>[["Big Rig"]]
            }
          }
        },
        8=>{
          "Miles/Gallon"=>{
            "1-10"=>{
              "Type of Auto"=>[["Big Rig"]]
            }
          }
        }
      }
    }
  }
}

Это одна из немногих проблем, которая очень хорошо подходит для рекурсивного решения.
Почему этот? Ну пара причин:
  1. Вы заметите, что мы строим дерево из этой иерархии. Деревья и многие связанные с ними решения имеют схожий смысл, что бы вы ни делали на одном уровне дерева, вам нужно будет делать на каждом уровне. В этом случае это разделит наш набор данных на множество наборов данных.
  2. Глубина рекурсии довольно хорошо ограничена контекстом проблемы. Вы можете столкнуться с этим только в наборах данных с числом столбцов в тысячах. Если это вы, вам нужно развернуть рекурсию в стек, основанный на дизайне. Повеселись! ?

Этот код довольно липкий для Ruby, но я все равно его выкладываю.
Подскажите, как я могу это почистить!
 
def categorize_dataset dataset
  column_count = dataset["headers"].length
  if column_count == 1
    return {dataset["headers"].first => dataset["data"]}
  end

  min_entropy_value = 99
  best_index_to_split = 0
  
  (0..column_count-1).each do |column_index|
    entropy_value = calculate_shannon_entropy dataset["data"], column_index
    if entropy_value < min_entropy_value
      min_entropy_value = entropy_value
      best_index_to_split = column_index
    end
  end

  puts "Splitting on column index #{dataset["headers"][best_index_to_split]} with entropy of #{min_entropy_value}"
  the_split_dataset = split_the_dataset dataset, best_index_to_split

  split_header = dataset["headers"][best_index_to_split]
  tree = {
    split_header => the_split_dataset
  }

  the_split_dataset.each do |value_key, value_dataset|
    tree[split_header][value_key] = categorize_dataset value_dataset
  end

  tree
end

Чтобы отдать должное, где это должно быть,
 сегодня вечером я сел на « 
Машинное обучение в действии» , и хотя я не копировал алгоритм слово в слово, он был чрезвычайно полезен. Это одна из немногих книг по продвинутой теме, которая, кажется, способна очень хорошо передать знания автора. Некоторые из более опытных из вас могут заметить, что способ, которым я справился с оценкой правильного способа нарезки данных, отличается от стандартного способа (по крайней мере, по сравнению с моей книгой). Я в порядке с этим, но я мог бы очистить это и выправить это, если настроение поражает меня.