Як програміст машину купував. Частина II

попередній статті на прикладі покупки Mercedes-Benz E-klasse не старше 2010 року випуску вартістю до 1.5 млн рублів в Москві була розглянута задача пошуку вигідних автомобілів. Під вигідними слід розуміти пропозиції, ціна яких нижча за ринкову у поточний момент серед оголошень, зібраних з усіх найбільш авторитетних сайтів з продажу б/у автомобілів в РФ.

На першому етапі в якості методу машинного навчання була обрана множинна лінійна регресія, були розглянуті правомірність її використання, а також плюси і мінуси. Проста лінійна регресія була обрана в якості ознайомчого алгоритму. Очевидно, що існує ще багато методів машинного навчання для рішення поставленої задачі регресії. У цій статті я хотів би розповісти вам, як саме я вибирав найбільш оптимальний алгоритм машинного навчання для досліджуваної моделі, який в даний час використовується в реалізованому мною сервісі — robasta.ru.



Вибір алгоритму
Претенденти на звання «чемпіона»:
Перш ніж зробити вибір, були досліджені всі вищевикладені алгоритми, тому хотів докладно розповісти вам про кожного з них. Однак, такий шлях перебору «в лоб» не зовсім оптимальний, розумніше спочатку провести додаткові дослідження поставленої задачі.

Крім Mercedes-Benz E-klasse мені імпонувала Audi A5, особливо з дизельним двигуном потужністю 239 к. с., що володіє хорошою динамікою (6 сек. до 100 км/ч) і прийнятним податком. Поглянувши на залежність ціни від потужності двигуна цього творіння німецьких інженерів (візуалізація нижче), багато питання відпадають самі собою.

Про лінійної залежності тут не може йти і мови, тому алгоритми, в основі яких лежить лінійна залежність объясняемой змінної (вартості, в нашому випадку) від регрессоров, можна сміло відкинути. Використання поліноміальних і нелінійних моделей неправомірно з тієї причини, що заздалегідь невідомий вид залежності того чи іншого регрессора від ціни для кожної окремої взятої моделі автомобіля.

Таким чином, прийнявши вищевикладені міркування до уваги, нам залишається розглянути тільки алгоритми, в основі яких лежать дерева прийняття рішеньRandom forest і Xgboost (з двома видами бустинга — xgbDart, xgbTree), і вибрати з них оптимальний.

Слід обмовитися, що оптимальний алгоритм — це той, який покаже себе найкращим чином (min RMSE) при перехресній перевірці (cross-validation) і відкладеної вибірці.
Перш ніж переходити до «сліпому» застосування обраних алгоритмів, в наступному розділі я хотів би більш детально висвітлити питання їх налаштування.

Cross-validation
Для оцінки реальних можливостей моделі і налаштування її параметрів в задачах машинного навчання найчастіше використовують перехресну перевірку (Cross-validation, СV). Виділяється деякий безліч розбиття вихідної вибірки на навчальну і контрольну підвибірки. Для кожного з розбиття алгоритм налаштовується за навчальною подвыборке, потім на контрольній оцінюється його середня помилка.
Оцінкою перехресної перевірки називається середня по всім разбиениям величина помилки на контрольних підвибірках.

незміщеності оцінки ймовірності помилки, отриманої за допомогою крос-валідації, необхідно, щоб навчальна і контрольна вибірки утворювали непересічне підмножина, під уникнення явища переобучения.

Різновиди перехресної перевірки:
  1. k-блокова крос-валідація (k-fold cross-validation). ДокладнішеЦей метод випадковим чином розбиває дані на k непересічних блоків приблизно однакового розміру. По черзі кожен блок розглядається як валидационная вибірка, а решта k-1 блоків — як навчальна вибірка. Модель навчається на k-1 блоках і прогнозує валидационный блок. Прогноз моделі оцінюється з допомогою обраного показника: правильність (accuracy), середньоквадратичне відхилення (СКВ, RMSE) і т. п. Процес повторюється k разів, і ми отримуємо k оцінок, для яких розраховується середнє значення, що є підсумковою оцінкою моделі. Зазвичай k вибирають рівним 10, іноді 5. Якщо k дорівнює кількості елементів у вихідному наборі даних, цей метод називається крос-валідацією по окремим елементам (у цій статті не розглядається).
  2. Багаторазова k-блокова крос-валідація (repeated k-fold cross-validation). ДокладнішеУ рамках цього методу k-блокова крос-валідація виконується кілька разів. Наприклад, 5-кратна 10-блокова крос-валідація дасть 50 оцінок, на основі яких потім буде розрахована середня оцінка. Зверніть увагу, це не те ж саме, що 50-блокова крос-валідація.
  3. Крос-валідація на основі методу Монте-Карло (МККВ, Monte Carlo cross-validation, leave-group-out cross-validation). ДокладнішеДаний метод задану кількість разів випадковим чином розбиває вихідний набір даних на навчальну і валидационную вибірку в заданій пропорції.
Кожен з описаних вище методів крос-валідації, можна охарактеризувати з допомогою зсуву (bias) і дисперсії (variance). Зміщення характеризує правильність (accuracy) оцінки. Дисперсія характеризує точність (precision) оцінки.

У загальному випадку зміщення методу крос-валідації залежить від розміру валідаційної вибірки. Якщо розмір валідаційної вибірки становить 50% вихідних даних (2-блокова крос-валідація), підсумкова оцінка СКО буде зміщеною, ніж у разі, коли цей розмір становить 10% вихідних даних. З іншого боку, менший розмір валідаційної вибірки збільшує дисперсію, оскільки кожна валидационная вибірка містить менше даних для отримання стабільного значення СКВ.

Таким чином, коли мова йде про k-блокової крос-валідації, то для мінімізації зміщення слід вибирати максимальне k, а для зменшення дисперсії застосовувати багаторазовий k-блочний метод, який справляється з цим завданням краще одноразового.
Що ж стосується МККВ, то для цього виду перехресної перевірки розмір валідаційної вибірки має трохи більший вплив на дисперсію, ніж
кількість повторень процесу. Слід також відзначити, що кількість повторень процесу не робить істотного впливу на зсув.
Таким чином, для методу МККВ можна порекомендувати використовувати валидационную вибірку малого розміру (наприклад, 10%) і виконувати велику кількість повторень, щоб зменшити дисперсію.

Однак, при інших рівних, використання багаторазової 10-блокової КВ забезпечує меншу дисперсію, що в першу чергу обумовлено тим, що для цього методу, один і той же елемент даних не може зустрічатися в різних вибірках, на відміну від МККВ.

На завершення наших міркувань, хотілося б зробити застереження, що при великих обсягах даних 10-блокова або навіть 5-блокова одноразова КВ дає цілком прийнятні результати, у нашій задачі, для налаштування моделі ми будемо використовувати багаторазову 10-блокову перехресну перевірку.

Random forest
«Випадковий Ліс» — алгоритм, який для отриманих даних випадковим чином створює безліч дерев прийняття рішень і потім усереднює результати їх прогнозів. Алгоритм побудови дерева дуже швидкий, тому не становить великої праці зробити стільки дерев, скільки буде потрібно.
З практичної точки зору у описаного вище методу є одна величезна перевага: він майже не вимагає конфігурації. Якщо ми візьмемо будь-який інший алгоритм машинного навчання, будь то регресія або нейронна мережа, вони всі мають безліч параметрів, і їх треба вміти підбирати під конкретну задачу. RF, по-суті, має лише один важливий параметр вимагає настройки — mtry (розмір випадкового підмножини, що обирається на кожному кроці побудови дерева). Однак, навіть використовуючи значення за замовчуванням, можна отримати досить прийнятні результати.

Як і в попередній статті, замінимо відсутні значення (N/A) на медіанні для всіх регрессоров, виключимо з вибірки об'єм двигуна (через сильної кореляції параметра з потужністю) і подивимося на можливості цього алгоритму.

dat <- read.csv("dataset.txt") # завантажуємо вибірку в R
 

 
dat$mileage[is.na(dat$mileage)] <- median(na.omit(dat$mileage)) # замінюємо NA на прикладі пробігу
 

 
dat <- dat[-c(1,11)] # виключаємо номер рядка і обсяг двигуна з вибірки 
 

 
set.seed(1) # ініціалізуємо генератор випадкових чисел (для відтворюваності)
 

 
split <- runif(dim(dat)[1]) > 0.2 # розділяємо нашу вибірку
 

 
train <- dat[split,] # вибірка для навчання та налаштування (cross-validation) параметрів
 

 
test <- dat[!split,] # відкладена (hold-out) вибірка
 

Для перехресної перевірки будемо використовувати пакет caret, який має більше можливостей для оцінки якості моделі, ніж rfcv.

library(caret) # підключаємо бібліотеку caret
 

 
fit.control <- trainControl(method = "repeatedcv", number = 10, який repeats = 10) 
 

 
train.rf.model <- train(price~., data=train, method="україна", trControl=fit.control , metric = "RMSE") # застосуємо 10-ти кратну 10-ти блокову крос-валідацію для налаштування моделі
 

 
train.rf.model # подивимося на результати крос-валідації
 
<div class="spoiler"><b class="spoiler_title">Докладніше</b><div class="spoiler_text">Random Forest 
 

 
292 samples
 
15 predictor
 

 
No pre-processing
 
Resampling: Cross-Validated (10 fold, repeated 10 times) 
 
Summary of sample sizes: 262, 262, 262, 263, 263, 263, ... 
 
Resampling results across tuning parameters:
 

 
mtry RMSE Rsquared
 
2 134565.8 0.4318963
 
8 117451.8 0.4378768
 
15 122897.6 0.3956822
 

 
RMSE was used to select the optimal model using the smallest value.
 
The final value used for the model was mtry = 8.
 
</div></div>
 
library("randomForest") # підключаємо бібліотеку random forest
 

 
train.rf.model <- randomForest(price ~ ., train,mtry=8) # побудуємо модель на основі отриманих за допомогою крос-валідації параметрів
 

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

varImpPlot(train.rf.model) # оцінимо важливість предикторів
 



rf.model.predictions <- predict(train.rf.model, test) # перевіримо точність оцінки на відкладеної вибірці
 

 
print(sqrt(sum((as.vector(rf.model.predictions - test$price))^2)/length(rf.model.predictions))) # середня помилка прогнозу ціни (в рублях)
 
[1] 121760.5
 

Отримана середня помилка оцінки вартості автомобіля еквівалентна цієї ж величини отриманої лінійної регресії. Нагадаю, що при побудові лінійної моделі, на відміну від RF, ми позбувалися выбросов, що призводило до додаткових неточностей в оцінках вартості автомобілів. Таким чином, можна стверджувати про робастности «випадкового лісу» до викидів.

XGboost
Ідея градієнтного бустинга полягає в побудові ансамблю послідовно уточнюють один одного елементарних моделей. Кожна наступна елементарна модель навчається на «помилки» ансамблю з попередніх елементарних моделей, відповіді моделей виважено додаються.
«Бустить» можна практично будь-які моделі — загальні лінійні, узагальнені лінійні, дерева рішень, K-найближчих сусідів і багато інші.
До особливостей реалізації алгоритму бустинга xgboost можна віднести, по-перше, використання крім першої ще і другої похідної від функції втрат, що підвищує ефективність алгоритму. По-друге, наявність вбудованої регуляризации, що допомагає боротися з переобучением. І нарешті, можливість задавати власні функції втрат та метрики якості.

Завдяки експериментальному параметру num_parallel_tree можна задати кількість одночасно створюються дерев і уявити Random Forest, як приватний випадок бустинговой моделі з однією ітерацією. А якщо використовувати більше однієї ітерації, то вийде бустинг «випадкових лісів», коли кожен «випадковий ліс» виступає в якості елементарної моделі.

В рамках статті розглянемо тільки один вид бустинга — xgbTree, т. к. xgbDart дає подібні результати.

fit.control <- trainControl(method = "repeatedcv", number = 10, який repeats = 10) 
 

 
train.xgb.model <- train(price ~., data = train, method = "xgbTree", trControl = fit.control, metric = "RMSE") # застосуємо 10-ти кратну 10-ти блокову крос-валідацію
 

 
train.xgb.model # подивимося на результати крос-валідації
 
<div class="spoiler"><b class="spoiler_title">Докладніше</b><div class="spoiler_text">eXtreme Gradient Boosting
 

 
292 samples
 
15 predictor
 

 
No pre-processing
 
Resampling: Cross-Validated (10 fold, repeated 10 times)
 
Summary of sample sizes: 263, 262, 262, 263, 264, 263, ...
 
Resampling results across tuning parameters:
 

 
eta max_depth colsample_bytree nrounds RMSE Rsquared
 
0.3 1 0.6 50 114131.1 0.4705512
 
0.3 1 0.6 100 113639.6 0.4745488
 
0.3 1 0.6 150 113821.3 0.4734121
 
0.3 1 0.8 50 114234.6 0.4694687
 
0.3 1 0.8 100 113960.5 0.4712563
 
0.3 1 0.8 150 114337.1 0.4685121
 
0.3 2 0.6 50 115364.6 0.4604643
 
0.3 2 0.6 100 117576.4 0.4472452
 
0.3 2 0.6 150 119443.6 0.4358365
 
0.3 2 0.8 50 116560.3 0.4494750
 
0.3 2 0.8 100 119054.2 0.4350078
 
0.3 2 0.8 150 121035.4 0.4222440
 
0.3 3 0.6 50 117883.2 0.4422659
 
0.3 3 0.6 100 121916.7 0.4162103
 
0.3 3 0.6 150 125206.7 0.3968248
 
0.3 3 0.8 50 119331.3 0.4296062
 
0.3 3 0.8 100 124385.7 0.3987044
 
0.3 3 0.8 150 128396.6 0.3753334
 
0.4 1 0.6 50 113771.6 0.4727520
 
0.4 1 0.6 100 113951.6 0.4717968
 
0.4 1 0.6 150 114135.0 0.4710503
 
0.4 1 0.8 50 114055.0 0.4700165
 
0.4 1 0.8 100 114345.5 0.4680938
 
0.4 1 0.8 150 114715.8 0.4655844
 
0.4 2 0.6 50 116982.1 0.4499777
 
0.4 2 0.6 100 119511.9 0.4347406
 
0.4 2 0.6 150 122337.9 0.4163611
 
0.4 2 0.8 50 118384.6 0.4379478
 
0.4 2 0.8 100 121302.6 0.4201654
 
0.4 2 0.8 150 124283.7 0.4015380
 
0.4 3 0.6 50 118843.2 0.4356722
 
0.4 3 0.6 100 124315.3 0.4017282
 
0.4 3 0.6 150 128263.0 0.3796033
 
0.4 3 0.8 50 122043.1 0.4135415
 
0.4 3 0.8 100 128164.0 0.3782641
 
0.4 3 0.8 150 132538.2 0.3567702
 

 
Tuning parameter 'gamma' was held at constant a value of 0
 
Tuning parameter 'min_child_weight' was held at constant a value of 1
 
RMSE was used to select the optimal model using the smallest value.
 
The final values used for the model were nrounds = 100, max_depth = 1, eta = 0.3, gamma = 0, colsample_bytree = 0.6 and min_child_weight = 1.
 
</div></div>
 
library("xgboost") # підключаємо бібліотеку xgboost
 

 
xgb_train <- xgb.DMatrix(as.matrix(train[-c(1)] ), label=train$price) # тренувальна вибірка 
 

 
xgb_test <- xgb.DMatrix(as.matrix(test[-c(1)]), label=test$price) # тестова вибірка
 

 
xgb.param <- list(booster = "gbtree", 
 
max.depth = 1, 
 
eta = 0.3, 
 
gamma = 0,
 
colsample_bytree = 0.6, 
 
min_child_weight = 1, 
 
eval_metric = "rmse")
 

 
train.xgb.model <- xgb.train(data = xgb_train, nrounds = 100, params = xgb.param) # побудуємо модель на основі отриманих за допомогою крос-валідації параметрів
 

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

importance.frame <- xgb.importance(colnames(train[-c(1)]), model = train.xgb.model) # оцінимо важливість предикторів
 

 
library("Ckmeans.1d.dp") # підключимо бібліотеку для xgb.plot
 

 
xgb.plot.importance(importance.frame)
 



xgb.model.predictions <- predict(train.xgb.model, xgb_test) # перевіримо точність оцінки на відкладеної вибірці
 

 
print(sqrt(sum((as.vector(xgb.model.predictions - test$price))^2)/length(xgb.model.predictions))) # середня помилка прогнозу ціни (в рублях)
 
[1] 118742.8
 

XGboost для даного конкретного випадку показав трохи більш точні оцінки вартості автомобілів. Викликає побоювання велика кількість гиперпараметров, які вимагають перенастроювання в залежності від обраної марки і моделі авто. У зв'язку з цим, для використання на сервісі robasta.ru перевагу було віддано алгоритмом Random Forest.

Апробація вибраного алгоритму
Тепер, коли за вибором «чемпіона» покінчено, саме час подивитися на нього в справі.

library("randomForest") # підключаємо бібліотеку random forest
 

 
rf.model <- randomForest(price ~ ., dat,mtry=8) # побудуємо модель на основі отриманих за допомогою крос-валідації параметрів
 

 
predicted.price <- predict(rf.model, dat) # предскажем ціну для кожного автомобіля
 

 
real.price <- dat$price # вектор цін на автомобілі отриманий з оголошень
 

 
profit <- predicted.price - real.price # вигода між передбаченої нами ціною і ціною оголошень
 

Як і для лінійної регресії у минулій статті, побудуємо графік залежності вигоди від ціни.

plot(real.price,profit) 
 
abline(0,0)
 



А тепер порахуємо вигоду в процентному співвідношенні.

sorted <- sort(predicted.price /real.price, decreasing = TRUE) 
 
sorted[1:10]
 

 
69 42 122 15 168 248 346 109 231 244
 
1.412597 1.363876 1.354881 1.256323 1.185104 1.182895 1.168575 1.158208 1.157928 1.154557
 

Отримані результати мають вкрай слабке схожість з результатами, отриманими з допомогою лінійної регресії, і виглядають більш правдоподібно, незважаючи на практично ідентичне СКО для обох моделей.

Для порівняння результатів у цій статті ми використовували вибірку минулій публікації, тому давайте подивимося багато вигідних пропозицій Mercedes-Benz E-klasse не старше 2010 року випуску, вартістю до 1.5 млн рублів в Москві на ринку зараз.



Резюмуючи все вище сказане, можу з упевненістю заявити, що для підбору б/у автомобілів ми отримали потужний інструмент, не чутливий до «фейковим» оголошенням, що працює в режимі реального часу. Вам більше не потрібно просиджувати годинами на декількох сайтах з оголошеннями по продажу машин і їздити дивитися потенційно невигідні пропозиції.

Але це ще не все, тепер, використовуючи розглянутий математичний апарат, Робаста може допомогти не тільки тим, хто хоче купити, але і тим, хто хоче продати свій автомобіль.

Продаж автомобіля
При продажу своєї машини ви, звісно, хочете як мінімум не продешевити і продати її в короткий термін. Для швидкої та вигідної продажу вашого автомобіля потрібно розуміти внесок різних характеристик в його вартість.

Для вирішення цього завдання, на основі все того ж «випадкового лісу», був розроблений сервіс для оцінки авто. Ви заповнюєте всі поля форми пошуку, у відповідності з параметрами вашого автомобіля, після чого модель навчається на основі ринкових пропозицій в поточний момент. У разі якщо знайшлося п'ять і більше оголошень на ринку, алгоритм для заповнених вами даних передбачає ціну і видає кілька цікавих особливостях в залежності від загальної картини ринку. Варто підкреслити, що для досягнення найбільшої точності, для аналізу вибираються тільки автомобілі того ж покоління, що і ваш. Результати оцінки вашого автомобіля формуються у вигляді звіту pdf, вартість якого становить 99 ₽.



Наостанок
В даний час опрацьовуються різні напрямки подальшого розвитку, серед яких основними можна назвати наступні:

Відносно нові автомобілі (пробіг-100 тис. км) часто продають перед великими дорогими, ці дані корисно враховувати в моделі. Тому зараз я перебуваю в пошуку надійних партнерів серед середніх і великих автодилерів.
Відкриття оффлайн-центру по підбору і оцінки автомобілів в Москві, який, завдяки реалізованому алгоритмом, буде набагато менш витратним, ніж у конкурентів.
Створення зручного API для надання функціоналу "інтелектуальним перекупникам".

Ви хочете чимось допомогти в реалізації озвучених мною завдань або запропонувати свої ідеї? Пишіть, я завжди готовий розглянути будь-які види співпраці.

Посилання
  • dat (вибірка MB E-klasse)
  • dat_a5 (вибірка Audi A5)
Джерело: Хабрахабр

0 коментарів

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