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

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

Метод опорних векторів

Метод опорних векторів (Support Vector Machine – SVM) відноситься до групи граничних методів. Вона визначає класи за допомогою границь областей.

За допомогою даного методу розв'язуються задачі бінарної класифікації.

У основі методу лежить поняття площини рішень.

Площина (plane) рішення розділяє об'єкти з різною класовою приналежністю.

На рис.10.1 наведений приклад, в якому беруть участь об'єкти двох типів. Розділяюча лінія задає межу, праворуч від якого, – всі об'єкти типу brown (коричневий), а зліва –типу yellow (жовтий). Новий об'єкт, що потрапляє направо, класифікується як об'єкт класу brown або – як об'єкт класу yellow, якщо він розташувався ліворуч від розділяючої прямої. В цьому випадку кожен об'єкт характеризується двома вимірами.

Рис. 10.1. Розділення класів прямою лінією

Мета методу опорних векторів – знайти площину, що розділяє дві множини об'єктів; така площина показана на рис. 10.2. На цьому рисунку множина зразків поділена на два класи: жовті об'єкти належать класу А, коричневі – класу В.

Рис. 10.2. До визначення опорних векторів

Метод відшукує зразки, що знаходяться на межах між двома класами, тобто опорні вектора; вони зображені на рис. 10.3.

Рис. 10.3. Опорні вектори

Опорними векторами називаються об'єкти множини, що лежать на межах областей.

Класифікація вважається доброю, якщо область між межами порожня.

На рис. 10.3.показано п'ять векторів, які є опорними для даної множини.

2. Лінійний svm

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

Задачу можна сформулювати як пошук функції f(x), що набуває значень менше нуля для векторів одного класу і більше нуля, – для векторів іншого класу. Як вихідні дані для розв’язку поставленої задачі, тобто пошуку класифікуючої функції f(x), дано тренувальний набір векторів простору, для яких відома їх приналежність до одного з класів. Сімейство класифікуючих функцій можна описати через функцію f(x). Гіперплощина визначена вектором а і значенням b, тобто f(x) = ax + b. Рішення даної задачі проілюстроване на рис. 10.4.

В результаті рішення задачі, тобто побудови SVM-моделі, знайдена функція, що набуває значень менше нуля для векторів одного класу і більше нуля, – для векторів іншого класу. Для кожного нового об'єкту негативне або позитивне значення визначає приналежність об'єкту до одного з класів.

Рис. 10.4. Лінійний SVM

Найкращою функцією класифікації є функція, для якої очікуваний ризик мінімальний. Поняття очікуваного ризику в даному випадку означає очікуваний рівень помилки класифікації.

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

Емпіричний ризик – рівень помилки класифікації на тренувальному наборі.

Таким чином, в результаті рішення задачі методом опорних векторів для даних, що лінійно розділяються, ми отримуємо функцію класифікації, яка мінімізує верхню оцінку очікуваної риски.

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

У таких випадках один з варіантів – збільшення розмірності, тобто перенесення даних з площини в тривимірний простір, де можливо побудувати таку площину, яка ідеально розділить множину зразків на два класи. Опорними векторами в цьому випадку служитимуть об'єкти з обох класів, що є екстремальними.

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

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

Як і будь-який інший метод, метод SVM має свої сильні і слабкі сторони, які слід враховувати при виборі даного методу.

Недолік методу полягає в тому, що для класифікації використовується не вся множина зразків, а лише їх невелика частина, яка знаходиться на межах.

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

Метод опорних векторів дозволяє [37, 38]:

• отримати функцію класифікації з мінімальною верхньою оцінкою очікуваної риски (рівня помилки класифікації);

• використовувати лінійний класифікатор для роботи з даними, що нелінійно розділяються, поєднуючи простоту з ефективністю.