Модель Random Forest для класифікації, реалізація на c#
Бінарне дерево рішень
Давайте поглянемо на деякі приклади заходів неоднорідності (векторpскладається зmймовірностей міток, що зустрічаються в деякому підмножиніAнавчальної множини):
- Most commonly occurring />
Алгоритм побудови бінарного дерева рішень працює за схемою жадібного алгоритму: на кожній ітерації для вхідної підмножини навчальної множини будується таке розбиття простору гіперплощиною (ортогональною однією з осей координат), яке мінімізувало б середню міру неоднорідності двох отриманих підмножин. Дана процедура виконується рекурсивно для кожного отриманого підмножини доти, доки не будуть досягнуті критерії зупинки. Запишемо це більш формально, для вхідної множиниAзнайдемо пару, що міра неоднорідності буде мінімальна: де - вектор ймовірностей отриманий за вищеописаною процедурою від підмножини множиниA, що складається із тих елементів для яких виконується умоваf Код візуалізації
Перелічимо можливі критерії зупинки: досягнуто максимальної глибини вузла; ймовірність домінуючого класу у розбитті перевищує деякий поріг (я використовую 0.95); кількість елементів у підмножині менше деякого порога. У результаті в нас вийде розбиття всієї множини на (гіпер) прямокутники, і кожне таке підмножина множини навчання буде асоційовано з одним листом дерева, а всі внутрішні вузли являють собою одну з умов розбиття; або іншими словами, певний предикат. У поточного вузла, лівий нащадок асоційований з тими елементами множини, для яких предикат вірний, а правий відповідно до теми для яких предикат повертає брехню. Виглядає це приблизно так:
До речі щодо завданнярегресії. Описаний спосіб побудови дерева легко змінюється із завдання класифікації на задачу регресії. Для цього необхідно замінити міру неоднорідності деякою мірою помилки прогнозування, наприклад на середньоквадратичне відхилення. А при ухваленні рішення замість домінуючого класу використовується середнє значення цільової змінної.
Начебто з деревами все вирішили. Ми не будемо зупинятись на плюсах та мінусах цього методу, у вікіпедії є хороший список. Але насамкінець хочеться додати ілюстрацію з книги An Introduction to Statistical Learning про різницю лінійних моделей та дерев.
Bootstrap aggregating або bagging
Перейдемо до наступної ідейної складової random forest'а. Отже назваBAGging, утворена відBootstrapAGgregating. У статистиці під бутстрепом розуміють як спосіб оцінки стандартної помилки статистик вибіркового імовірнісного розподілу, і спосіб семплювання вибірок з набору даних заснований методі Монте-Карло.
Бутстреп семплінг простий за своєю ідеєю, і застосовується тоді, коли ми не маємо можливості отримати велику кількість вибірок з реальногорозподілу, а це майже завжди так. Допустимо ми хочемо отримати множини спостережень розміру n 4 , але у нас в розпорядженні тільки одна множина з n 4 спостережень. Тоді ми генеруємоmмножин рівноймовірним виборомnелементів вихідної множини з поверненням обраного елемента (вибірка з повторенням або поверненням). При великих значенняхnкількість унікальних елементів отриманого бутстреп семплінгом множини буде становити(1 — 1/e) ≈ 63.2%від загального числа унікальних спостережень вихідної множини. ПозначимоD i—i-е безліч отримане бутстреп семплюванням, ми оцінюємо на ньому деякий параметрa i, і повторюємо цю процедуруmразів . Стандартна помилка бутстреп оцінки параметра записується наступним чином: Отже,статистичний бутстрепдозволяє оцінити помилку оцінки деякого параметра розподілу. Але це так відволікання від теми, нам цікавий метод бутстреп семплювання.
А тепер розглянемо набір зmнезалежних випадково вибраних елементівxз одного ймовірнісного розподілу, з деяким математичним очікуванням та дисперсієюσ 2. Тоді вибіркове середнє дорівнюватиме: Вибіркове середнє — це параметр розподілу, на відміну від матожидания і дисперсії, а функція від випадкових змінних, тобто. теж є випадковою змінною, з деякого ймовірнісного розподілу вибіркових середніх. А воно в свою чергу має параметр дисперсія, який виражається таким чином: Виходить, щосереднення безлічі значень випадкової змінної зменшує варіативність. На цьому і будується ідея агрегування бутстрепів вибірок. Згенеруємоmбутстреп вибірок розміруnз навчальної множиниD(теж розміруn): На кожній бутстреп вибірці навчимо модельfі введемо наступну функцію, такий підхід і називається bootstrap aggregating або bagging: Bagging можна проілюструвати наступним графіком з вікіпедії, де bag-модель зображена червоною лінією і є усередненням багатьох інших моделей.
Декореляція
Такий метод називається Random subspace method і застосовується не тільки для дерев рішень, але і для інших моделей, таких як нейромережі.
Загалом як так виглядав би звичайний рівний ліс, і декорельований.
Перейдемо до реалізації. Ще раз хочу нагадати, що наведений мною приклад не є швидкою реалізацією random forest'а, а має навчальний лише характер, покликаний допомогти зрозуміти основні ідеї моделі. Наприклад тут ви знайдете приклад придатної та спритної імплементації, але на жаль менш зрозумілою.
Коментарі я вставлятиму там де необхідно прямо в коді, щоб не розбивати класи на шматки.
Одиниця спостереження у разі представляється наступним класом.