Вы когда-нибудь видели большую таблицу данных и думали: «Кто-то просто вырвал цифры на моем мониторе?» Иногда бывает трудно понять смысл таблиц, подобных этой, и даже более того, когда таблицы большие. Есть по крайней мере одна техника машинного обучения, которая поможет вам разобраться в данных: деревья классификации.
Деревья классификации работают, проливая столбец данных за столбцом, а затем иерархически группируют данные по уникальным значениям в каждом столбце. В качестве примера представьте, что у вас есть таблица данных, подобная этой:
В коде я пишу это так:
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"]]
}
}
}
}
}
}
}
Это одна из немногих проблем, которая очень хорошо подходит для рекурсивного решения. Почему этот? Ну пара причин:
- Вы заметите, что мы строим дерево из этой иерархии. Деревья и многие связанные с ними решения имеют схожий смысл, что бы вы ни делали на одном уровне дерева, вам нужно будет делать на каждом уровне. В этом случае это разделит наш набор данных на множество наборов данных.
- Глубина рекурсии довольно хорошо ограничена контекстом проблемы. Вы можете столкнуться с этим только в наборах данных с числом столбцов в тысячах. Если это вы, вам нужно развернуть рекурсию в стек, основанный на дизайне. Повеселись! ?
Этот код довольно липкий для 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
Чтобы отдать должное, где это должно быть, сегодня вечером я сел на «
Машинное обучение в действии» , и хотя я не копировал алгоритм слово в слово, он был чрезвычайно полезен. Это одна из немногих книг по продвинутой теме, которая, кажется, способна очень хорошо передать знания автора. Некоторые из более опытных из вас могут заметить, что способ, которым я справился с оценкой правильного способа нарезки данных, отличается от стандартного способа (по крайней мере, по сравнению с моей книгой). Я в порядке с этим, но я мог бы очистить это и выправить это, если настроение поражает меня.