Random Forest: прогулянки по зимовому лісі

Random Forest
1. Вступ
Це невелике практичне керівництво по застосуванню алгоритмів машинного навчання. Зрозуміло, існує чимала кількість алгоритмів машинного навчання та способів математичного (статистичного) аналізу інформації, однак, ця замітка присвячена саме Random Forest. У замітці показані приклади використання цього алгоритму для задач класифікації і регресії, а також подані деякі теоретичні пояснення.

2. Кілька слів про деревах
Перш за все, розглянемо деякі базові теоретичні принципи роботи цього алгоритму, а почнемо з такого поняття, як дерева рішень. Наша основна задача — прийняти рішення на основі наявної інформації. У найпростішому випадку у нас є лише одна ознака (метрика, предиктор, регрессор) з добре помітними кордонами між класів (максимальне значення для одного класу явно менше мінімального значення для іншого). Наприклад, знаючи масу тіла потрібно відрізнити кита від бджоли, якщо відомо, що серед усіх спостережень немає ні одного кита, який би мав масу тіла як у бджоли. Отже, досить лише одного показника (предиктора), щоб дати точну відповідь, передбачивши тим самим вірний клас.
Припустимо, що точки одного класу (нехай вони будуть показані червоним кольором) у всіх спостереженнях знаходяться вище точок синього кольору. Людина може провести між ними пряму лінію і сказати, що це і буде кордон класів. Отже, все розташоване вище цієї межі буде належати до одного класу, а все нижче лінії — до іншого.
Random Forest
Зобразимо це у вигляді деревовидної структури. Якщо ми скористаємося одним з алгоритмів (CART) для створення дерева рішень за вказаними раніше даними, то отримаємо наступне умова класифікації:
Conditional inference tree with 2 terminal nodes

Response: class 
Input: a 
Number of observations: 32 

1) a <= 5; criterion = 1, statistic = 31
2)* weights = 16 
1) a > 5
3)* weights = 16 

Отже, його візуальне подання буде таким:
Random Forest
Зрозуміло, кожна ознака має різним ступенем важливості. З наступного набору даних (формат LibSVM) видно, що перша ознака (його індекс 1, оскільки нумерація починається з нуля) абсолютно ідентичний у представників всіх класів. Фактично, цей показник не має ніякої цінності для класифікації, отже, його можна назвати надлишкової інформації, яка не несе ніякої практичної користі. Аналогічна ситуація і з другою ознакою (предиктором). Проте, третій з них відрізняється.
1 1:10 2:20 3:4
0 1:10 2:20 3:5
1 1:10 2:20 3:4
0 1:10 2:20 3:5
1 1:10 2:20 3:4
0 1:10 2:20 3:5
1 1:10 2:20 3:4
0 1:10 2:20 3:5
1 1:10 2:20 3:4
0 1:10 2:20 3:5

Саме третя ознака (feature 2) і буде служити тим самим заповітним відмінністю, за допомогою якого можна передбачати клас по вектору. Логічно припустити, що завдання може бути вирішена одним єдиним умовою (If-Else). Дійсно, кожне дерево в алгоритмі машинного навчання правильно змогло зрозуміти відмінності. Далі показана налагоджувальна інформація (використаний класифікатор Random Forest з фреймворку Apache Spark 2.1.0) для декількох дерев ансамблю випадкового лісу.
Tree 0:
If (feature 2 <= 4.0)
Predict: 1.0
Else (feature 2 > 4.0)
Predict: 0.0
Tree 1:
If (feature 2 <= 4.0)
Predict: 1.0
Else (feature 2 > 4.0)
Predict: 0.0
Tree 2:
If (feature 2 <= 4.0)
Predict: 1.0
Else (feature 2 > 4.0)
Predict: 0.0

Для більш складних завдань необхідні більш складні дерева. У наступному прикладі закономірність перестала бути такою очевидною для людини. Треба більш уважно подивитися набір даних, щоб помітити відмінності. Умова буде трохи більш складним, так як потрібна додаткова перевірка.
1 1:10 2:25
0 1:10 2:20
1 1:15 2:20
0 1:10 2:20
1 1:10 2:25
0 1:10 2:20
1 1:15 2:20
0 1:10 2:20
1 1:10 2:25
0 1:10 2:20
1 1:15 2:20
0 1:10 2:20

Ось такі додаткові перевірки вимагають нових розгалужень (вузлів) дерева. Після кожного розгалуження необхідно буде робити ще перевірки, тобто нові розгалуження. Це видно на налагоджувальної інформації. В цілях економії місця я наводжу лише кілька дерев:
Tree 0:
If (feature 0 <= 10.0)
If (feature 1 <= 20.0)
Predict: 0.0
Else (feature 1 > 20.0)
Predict: 1.0
Else (feature 0 > 10.0)
Predict: 1.0
Tree 1:
If (feature 1 <= 20.0)
If (feature 0 <= 10.0)
Predict: 0.0
Else (feature 0 > 10.0)
Predict: 1.0
Else (feature 1 > 20.0)
Predict: 1.0
Tree 2:
If (feature 1 <= 20.0)
If (feature 0 <= 10.0)
Predict: 0.0
Else (feature 0 > 10.0)
Predict: 1.0
Else (feature 1 > 20.0)
Predict: 1.0

А тепер уявімо собі набір даних з мільйона рядків і з кількох сотень (навіть тисяч) стовпців. Погодьтеся, що простими умовами такі завдання буде складно вирішити. Більш того, при дуже складних умовах (глибоке дерево) воно може бути занадто специфічна для конкретного набору даних (переобучено). Одне дерево стійке до масштабування даних, але не стійко до шумів. Якщо об'єднати велику кількість дерев в одну композицію, то можна отримати значно кращі результати. У підсумку виходить досить ефективна і досить універсальна модель.
3. Random Forest
По суті, Random Forest є композицією (ансамблем) безлічі вирішальних дерев, що дозволяє знизити проблему перенавчання та підвищити точність в порівнянні з одним деревом. Прогноз виходить в результаті агрегування відповідей безлічі дерев. Тренування дерев відбувається незалежно один від одного (на різних подмножествах), що не просто вирішує проблему побудови однакових дерев на одному і тому ж наборі даних, але і робить цей алгоритм дуже зручним для застосування в системах розподілених обчислень. Взагалі, ідея бэггинга, запропонована Лео Брейманом, добре підходить для розподілу обчислень.
Для бэггинга (незалежного навчання алгоритмів класифікації, де результат визначається голосуванням) є сенс використовувати велику кількість дерев рішень з досить великою глибиною. Під час класифікації фінальним результатом буде той клас, за який проголосувало більшість дерев, за умови, що одне дерево володіє одним голосом.
Так, наприклад, якщо в задачі бінарної класифікації була сформована модель з 500 деревами, серед яких 100 вказують на нульовий клас, а решта 400 на перший клас, то в результаті модель буде передбачати саме перший клас. Якщо використовувати Random Forest для завдань регресії, то підхід вибору того рішення, за яке проголосувала більшість дерев буде недоречною. Замість цього відбувається вибір середнього рішення по всім деревам.
Random Forest (через незалежного побудови глибоких дерев) вимагає дуже багато ресурсів, а обмеження на глибину зашкодить точності (для вирішення складних завдань потрібно побудувати багато глибоких дерев). Можна помітити, що час навчання дерев зростає приблизно лінійно їх кількості.
Звісно, збільшення висоти (глибини) дерев не самим кращим чином позначається на продуктивності, але підвищує ефективність цього алгоритму (хоча і разом з цим підвищується схильність до перенавчання). Занадто сильно боятися перенавчання не слід, так як це буде скомпенсоване числом дерев. Але і захоплюватися теж не варто. Скрізь важливі оптимально підібрані параметри (гиперпараметры).
Розглянемо приклад класифікації на мові програмування R. Так як нам зараз потрібна класифікаційна модель, а не регресійна, то в якості першого параметра слід чітко визначити, що клас є саме фактором. Крім кількості дерев приділимо увагу ознак (mtry), яке буде використовувати елементарна модель (дерево) для розгалужень. Фактично, це два основних параметри, які є сенс налаштовувати в першу чергу.
library(randomForest)

dataset <- read.csv(file="/home/kalinin84/data/real.csv", head=TRUE, sep=",")

model <- randomForest(factor(Class) ~ ., data=dataset, ntree=250, mtry=9)

Переконаємося, що це саме модель для класифікації:
model$type

Ознайомимося з результатами confusion matrix:
model$confusion

Цікаво побачити передбачені значення (на основі out-of-bag):
model$predicted

А функції varImpPlot і importance призначені для відображення важливості предикторів (цінності для точності роботи класифікатора).
varImpPlot(model)
importance(model)

Зрозуміло, для отримання вірогідного класу існує спеціальна функція. Вона називається predict. В якості першого аргументу вимагає модель, а в якості другого — набір даних. Результатом буде вектор передбачених класів. Для надійної перевірки необхідно виконувати тренування на одному наборі даних, а перевірку на іншому наборі даних.
Ще один приклад. На цей раз використовуємо Apache Spark 2.1.0 і мова програмування Scala. Інформацію ми прочитаємо з файлу формату LibSVM. Після цього необхідно буде явно розділити набір даних на дві частини. Одна з них навчальна, а друга — перевірочна. Виконувати стандартизацію або нормалізацію немає особливого сенсу. Наша модель стійка до цього, так само як і досить стійка до даних різної природи (вага, вік, дохід).
Повторюся, що навчання необхідно проводити тільки на навчальній вибірці. Кількість класів у цьому прикладі буде дорівнює двом. Кількість дерев хай буде 50. Залишимо індекс Джіні в якості критерію розщеплення, так як теоретично застосування ентропії не буде значно більш ефективним критерієм. Глибину дерева обмежимо дев'ятьма.
import org.apache.spark.mllib.tree.RandomForest
import org.apache.spark.mllib.tree.model.RandomForestModel
import org.apache.spark.mllib.util.MLUtils

val data = MLUtils.loadLibSVMFile(sc, "/home/kalinin84/data/real.data")

val splits = data.randomSplit(Array(0.7, 0.3))
val (trainingData, testData) = (splits(0), splits(1))

val model = RandomForest.trainClassifier(trainingData, 2, Map[Int, Int](), 50, "авто", "gini", 9, 32)

Тепер використовуємо тестовий набір даних, щоб перевірити роботу класифікатора з вказаними параметрами. Слід зауважити, що поріг точності (придатність моделі) визначається індивідуально в кожному конкретному випадку.
import org.apache.spark.mllib.evaluation.BinaryClassificationMetrics

val result = testData.map(p => (p.label, model.predict(p.features)))
val metrics = new BinaryClassificationMetrics(result)

// Результат: 1.0 — тобто весь простір під ROC
metrics.areaUnderROC

// Результат: Array((0.0,0.0), (0.0,1.0), (1.0,1.0), (1.0,1.0))
metrics.roc.collect

Отримавши на вхід вектор предикторів, система повинна вгадати (з допустимою ймовірністю) клас об'єкта. Якщо в результаті кількох перевірок на великому наборі даних це вдалося зробити, то можна стверджувати про точності моделі. Однак, жодна людина і жодна система не зможуть вгадати з дуже високою точністю по зростанню людини його рівень освіти. Отже, без правильно зібраних і підготовлених даних важко (або взагалі неможливо) буде вирішити задачу.
4. Кілька думок про практичне застосування
Бувають такі ситуації, коли простим умовою або методами описової статистики завдання відразу вирішити не виходить. Як раз в задачах підвищення ефективності інтернет-проектів (аналіз клієнтів, виявлення ймовірності покупки, оптимальні стратегії реклами, вибір товарів для показу в блоках популярних, рекомендації та персональні ранжирування, класифікація записів в каталогах і довідниках) і зустрічаються подібні складні набори даних.
Пам'ятаю, кілька років тому вперше зіткнувся з необхідністю застосування ML-технологій. Була ситуація, коли ми з колегами (група розробників) намагалися придумати метод класифікації матеріалів детального довідника на дуже великому порталі. Раніше класифікація виконувалася вручну іншими фахівцями, що вимагало величезної кількості часу. А ось автоматизувати ніяк не виходило (правила і статистичні методи не дали потрібної точності). У нас вже був набір векторів, який раніше розмітили фахівці.
Тоді мене здивувало, що кілька рядків коду (застосування однієї з популярних бібліотек машинного навчання) змогли вирішити проблему буквально відразу. Природно, що вивчалася можливість застосування різних моделей (включаючи нейронні мережі) і продумувались раціональні гиперпараметры. Але так як ця замітка про випадковий ліс, то приклад на мові програмування Python буде присвячений саме йому. Природно, код прикладу написаний з урахуванням нових версій готових класифікаторів, а не використовуваних тоді:
import pandas as pd
from sklearn.metrics import classification_report, accuracy_score
from sklearn.model_selection import train_test_split
from sklearn.ensemble import RandomForestClassifier

#
# Одержання даних
#
dataset = pd.read_csv('/home/kalinin84/data/real.csv')

#
# Поділяємо (тестовий і тренувальний набори)
#
train, test = train_test_split(dataset, test_size = 0.4)

classes = train.pop('Class').values
features = train

testClasses = test.pop('Class').values
testFeatures = test

#
# Тренування моделі
#
model = RandomForestClassifier(n_estimators=500, max_depth=30).fit(features, classes)

#
# Звіти про точності роботи
#
print(classification_report(testClasses, model.predict(testFeatures)))
print(accuracy_score(testClasses, model.predict(testFeatures)))

Таких прикладів дуже багато. Розповім ще одну історію. Було завдання підвищити ефективність величезної системи управління рекламою. Її робота безпосередньо залежала від точності передбачення рейтингу товарів і послуг. У кожного з них був вектор з 64-ти ознак. Стратегічно важливо було заздалегідь дати відносно точний прогноз значення рейтингу для кожного нового вектора ознак. До цього система управлялася нехитрими правилами і описовою статистикою. Але, як відомо, ефективності та точності у таких питаннях багато не буває. Для вирішення задачі підвищення ефективності була застосована регресійна модель, схожа на зазначену в прикладі:
from sklearn.datasets import load_svmlight_files
from sklearn.metrics import mean_squared_error
from sklearn.ensemble import RandomForestRegressor

#
# Одержання даних (тестовий і тренувальний набори)
#
X, y, Xt, yt = load_svmlight_files(("/data/001.data", "/data/001_test.data"))

#
# Тренування моделі та звіт про точність роботи
#
model = RandomForestRegressor(n_estimators=500, max_features=5).fit(X,y)
print(mean_squared_error(yt, model.predict(Xt)))

#
# Порівняємо з алгоритмом на основі ідеї бустинга
# Він повинен бути явно швидше випадкового лісу
#
import xgboost as xgb

modelXGB = xgb.XGBRegressor().fit(X, y)
print(mean_squared_error(yt, modelXGB.predict(Xt)))

У підсумку ми одержуємо досить потужний інструментарій аналізу інформації, який здатний прийти на допомогу в тих завданнях, де інші методи не дають найкращі результати.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.