Метод пошуку найближчого сусіда з прикладами на R, Про програмування, алгоритми і не тільки
Дружина посилає чоловіка-програміста до магазину та каже, купи батон ковбаси, а якщо будуть яйця – візьми десяток. Він у магазині: У Вас є яйця? -Є -Тоді дайте десять батонів ковбаси.
Thursday, April 14, 2011
Метод пошуку найближчого сусіда з прикладами на R
Простий приклад методу найближчого сусіда
Розглянемо зарплати людей, залежно від їхнього місця проживання. Припустимо, що ви живете в центрі Москви і що поруч із вами живуть люди із зарплатою 150 тис рублів. Тоді можна припустити, що і ваша зарплата близька до цієї величини. Якщо ж ви проживаєте в селищі Новотагілка Челябінської області, і зарплати ваших сусідів близько 3 тис. рублів, то швидше за все і ваша зарплата близька до 3 тис. рублів. Природно, що тут немає 100% точної залежності, хтось може жити в центрі Москви на пенсію в 6 тис, а хтось у Новотагілці зароблятиме 50. Але якщо єдина інформація, якою ми володіємо про людину, є її місце проживання, то ми можемо скористатися наведеним підходом з метою оцінки його доходів.
Аналогічно працює і метод найближчого сусіда, різниця лише в тому, що замість колег шукаються певним чином схожі елементи, причому схожість визначається безліччю різних факторів. Якщо, як і в нашому прикладі, йдеться про зарплати, то можуть бути використані також дані про професію, освіту, стаж роботи, поле та вік. Додаткові дані, з одного боку, ускладнюють завдання, вводячи додаткові вимірювання. З іншого боку, вони дозволяють набагато точніше передбачити результат. Наприклад, якщо ви знаєте, що ця людина програміст, працює і живе в Москві, має досвід близько 10 років, то передбачити її зарплату можна значно точніше.
А в папугахя набагато довша
Об'єкти, які знаходяться близько один до одного схильні мати близькі значення передбачуваних величин — це головна ідея методу найближчих сусідів. Якщо ви знаєте передбачуване значення для одного з елементів, ви можете передбачити його для найближчих сусідів.
Основна складність у застосуванні цього методу полягає в тому, що нам потрібно чітко визначити поняття «близькості». Це, своєю чергою, призводить до поняття відстані між елементами. Насправді можна використовувати різні види відстаней, але найчастіше досить простого евклідова. При виборі мірила відстаней важливо враховувати одиниці виміру. Адже нам, можливо, доведеться включити в одну величину властивості різної природи, наприклад, дохід (гроші), вік (роки), вага (кг) і т.д. Крім того, наприклад, гроші можна міряти в рублях, копійках, доларах, золотих злитках і багато чим ще, залежно від одиниці виміру відстані між елементами будуть виходити різні. Вибір одиниць вимірювання неможливо автоматизувати, це завдання залишається за користувачем алгоритму і залежить від конкретної сфери застосування та наявних даних.
А якщо елемента немає?
Що робити, наприклад, якщо нам дані тимчасові дані, такі як котирування на біржі. І завдання полягає в тому, щоб передбачити зміну ціни через деякий проміжок часу. В цьому випадку ми не можемо визначити навіть поняття елемента, про поняття близькості і говорити не доводиться.
Зазвичай цю проблему вирішується так, вибирається деяке послідовне число котирувань. Наприклад 10, перші 9 їх оголошуються предикторами, а останнє шуканим значенням. Виходить щось на кшталт вікна, що рухається. Наприклад, якщо ми маємо 100 послідовних значень, ми можемо спочатку взяти значення 1-9 длятренування, 10 - як шукане. Потім значення 2-10 для тренування, 11 - шукане. Природно, що при такому розбиття частина даних буде перекриватися, але значення, що шукається, щоразу нове.
Метод k найближчих сусідів
У нас є два класи елементів, червоні та зелені. І є невідомий елемент (відзначений кружальцем), він явно лежить у сфері червоних елементів. Але був класифікований як зелений тільки тому, що знаходиться поряд із викидом (іншим зеленим елементом)
Очевидний спосіб покращити становище – враховувати думку кількох найближчих сусідів замість одного. Це поліпшення призводить до іншого методу: метод k найближчих сусідів. Ідея полягає в тому, щоб взяти не просто найближчого сусіда, а до найближчих сусідів і передбачати значення шуканої величини на основі виваженої оцінки.
Метод k найближчих сусідів, як і, дозволяє оцінити точність прогнозу. Якщо всі k найближчих сусідів мають одне й те саме значення, то шанси, що об'єкт, що перевіряється, матиме таке ж значення, дуже високі. Якщо серед цих об'єктів 40% мають одне, а 60% інше значення, то вірогідність правильного прогнозу істотно знижується. Таким чином, ми можемо використовувати розподіл голосів між сусідами для оцінки точності прогнозу.
Приклад сьогодні буде на основі. біржових котирувань. Що може бути життєвішим? Не рахувати ж нам маточки та тичинки ірисів – до речі, якщо серйозно, за посиланням гарний приклад застосування методу найближчого сусіда.
Отже, завдання: передбачити рух індексу S&P500 щодо його змін за минулі 4 дні. Зміни рахуємо від закриття до закриття. На щастя для нас, нічого крім R та кількох додаткових модулів до нього не потрібно:
Результат роботи: Т.е. прибутковість за 30 днів становила 2.4%.
Осьтакий простий та інтуїтивно зрозумілий метод дозволяє іноді давати досить точні прогнози.