Алгоритм k найближчих сусідів

Задано множину об'єктів X, множину допустимих відповідей Y, і існує цільова функція (target function) y∗ : X → Y, значення якої yi = y∗(xi) відомі тільки на скінченній підмножині об'єктів {x1, . . . , xl} ⊂ X. Пари «об'єкт-відповідь» (xi, yi) називаються прецедентами. Сукупність пар Xl = (xi, yi)li=1 називається навчальною вибіркою (training sample).

Задача навчання за прецедентами полягає в тому, щоб за вибіркою Xl відновити залежність y∗, тобто побудувати функцію розв’язку (decision function) a : X → Y яка наближала б цільову функцію y∗(x), причому не тільки на об'єктах навчальної вибірки, але і на всій множині X.

Функція розв’язку a повинна допускати ефективну комп'ютерну реалізацію; з цієї причини будемо називати її алгоритмом.

Ознака (feature) f об'єкта x — це результат виміру певної характеристики об'єкта. Формально ознакою називається відображення f : X → Df, де Df – множина допустимих значень ознаки. Зокрема, будь-який алгоритм a : X → Y також можна розглядати як ознаку.

Залежно від природи множини Df ознаки поділяються на кілька типів.

Якщо Df = {0,1}, то f – бінарна ознака;

Якщо Df – скінченна множина, то f – номінальна ознака;

Якщо Df – скінченна впорядкована множина, то f – порядкова ознака;

Якщо Df = R, то f – кількісна ознака.

Якщо всі ознаки мають однаковий тип, Df1 = . . . = Dfn, то вихідні дані називаються однорідними, в іншому випадку – різнорідними.

Нехай є набір ознак f1, . . . , fn. Вектор (f1(x), . . . , fn(x)) називають ознаковим описом об'єкта x ∈ X.

Залежно від природи множини допустимих відповідей Y задачі навчання за прецедентами поділяються на такі типи.

Якщо Y = {1, . . . , M}, то це завдання класифікації (classification) на M класів, що не перетинаються. У цьому випадку вся множина об'єктів X розбивається на класи          Ky = {x ∈ X : y∗(x) = y}, та алгоритм a(x) має давати відповідь на запитання «якому класу належить x?». У деяких додатках класи називають образами і говорять про задачу розпізнавання образів (pattern recognition).

Якщо Y = {0,1}M, то це задача класифікації на M класів, що перетинаються. У найпростішому випадку ця задача зводиться до розв’язку M незалежних задач класифікації з двома класами, що не перетинаються.

Якщо Y = R, то це задача відновлення регресі (regression estimation).

Задача прогнозування (forecasting) є окремими випадками класифікації або відновлення регресії, коли x ∈ X – опис минулої поведінки об'єкта x, y ∈ Y – опис деяких характеристик його майбутньої поведінки.

Моделлю алгоритмів називається параметричне сімейство відображень                          A = {g(x, θ) | θ ∈ Θ}, де g : X × Θ → Y – деяка фіксована функція, Θ – множина допустимих значень параметра θ, звана простором параметрів або простором пошуку (search space).