МАТЕМАТИЧНА ОСНОВА КЛАСИФІКАЦІЇ KNN В ЕКОНОМІЦІ

Анотація

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

Постановка задачі. Дана вибірка з генеральної сукупності оформлена у вигляді таблиці, що містить reточок даних (записів) (див. табл. 1). Кожна точка даних складається з n значень f ознак Fi (feature) та мітки с класу С (class) до якого вона належить. На вхід поступає нова точка даних з певними значеннями ознак (fi)i=1n, визначити найбільш ймовірну мітку. 

Таблиця 1. Вибірка.

Вибірка

№

F1

F2

…

Fn

С

1

f11

f21

…

fn1

c1

2

f12

f22

…

fn2

c2

…

…

…

…

…

…

re

f1re

f2re

…

fnre

cre

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

Дискримінантний аналіз. Розділ математики, який вивчає методи дискримінації (класифікації) об’єктів на основі їхніх ознак. Ціль дискримінантного аналізу: на основі ознак об'єктів провести їх дискримінацію, тобто віднести їх до одного з відомих класів. Робиться припущення, що об’єкти одного класу мають схожі ознаки [1].

Дискримінантна функція gc(x) - функція за допомогою якої на основі ознак оцінюють схожість об’єкта на об’єкти класу c. Об’єкту присвоюється мітка класу з найбільшою оцінкою дискримінантної функції (найбільшою схожістю), тобто:

yx=argmaxxgc(x)

(1)

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

Метричний простір - пара (M,d), де M - множина, d:MMR - функція відстані.

1. d(x,y)=0x=y (аксіома тотожності)
2. d(x,y)0 (аксіома невід'ємності)
3. d(x,y)=d(y,x) (аксіома симетричності)
4. d(x,y)d(x,y)+d(y,z) (аксіома трикутника)

Аксіоми 1, 2, 3 інтуїтивно відповідають людському уявлення про відстань, аксіома 4 потребує додаткових пояснень. Вона постулює, що відстань є найкоротший шлях з усіх можливих. Візьмемо 3 точки: A,Б, та В (елементи множини M). Розглянемо наступні 3 шляхи:

1. d(A, Б) (прямий шлях)
2. d(A, В) (частина 1 транзитного шляху через В)
3. d(В, Б) (частина 2 транзитного шляху через В)

Очевидно, що існує 2 варіанти як дістатися від A до Б: прямий шлях та транзитний шлях. Людське уявлення про відстань каже нам, що найкоротший варіант - прямий. В той же час, якщо транзитна точка (В) лежить на прямому шляху, то прямий шлях по довжині дорівнює транзитному. Якщо ж транзитна точка не лежить на прямому шляху, то довжина транзитного шляху буде більшою за прямий. Саме це людське уявлення і описує 4-а аксіома. 

Приклади поширених функцій відстані.

Евклідова відстань.

d(x,y)=||x-y||=(i=1n(xi-yi)2)1/2

(2)

Косинус подібності.

d(x,y)=cos(<(x,y))=xy|x||y|

(3)

Нормалізація. На практиці часто доводиться мати справу з двома і більше ознаками. Ці ознаки можуть мати різні діапазони можливих значень. Це в свою чергу може призвести до проблеми, коли одна ознака має значно менший діапазон можливих значень ніж інша, і через це при підрахунку відстані ознака з меншим діапазоном майже не враховується, хоча вона може бути важливою ознакою для дискримінації. Для усунення цієї проблеми використовується нормалізація - приведення усіх ознак до одного діапазону можливихи значень. Таким чином, кожна ознака враховується незалежно від свого діапазону можливих значень [2]. 

Приклади поширених нормалізацій.

Мінімаксна-нормалізація.

f'=f-min[F]max[F] - min[F]

(4)

Z-нормалізація.

f'=f-M[F][F]

(5)

KNN з незваженим голосуванням. На вхід подається вектор x. Обирається k найближчих до x векторів - сусідів . Вектору z присвоюється мітка класу більшості сусідів, тобто:

gc(x)=xc cIc(x)

(6)

Ic(x)-індикаторна функція, Ic(x)=1xC;Ic(x)=0xC

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

Вагова функція w:AR+ - функція, яка використовується для того, щоб при сумі або інтегровані зробити внесок елементів множини A в результат неоднаковим. Прикладом є обернена відстань.

Обернена відстань. 

w(x,y)=1d(x,y)+

(7)

 - мала додатня константа, що дозволяє уникнути ділення на 0 коли d(x,y)=0.

KNN із зваженим голосуванням. На вхід подається вектор x. Обирається k найближчих до x векторів - сусідів. Обраховується внесок кожного з сусідів. x присвоюється мітка сусідів одного класу, зробивших найбільший внесок.

gc(x)=xc cIc(x)w(x,xc)

(8)

Висновок. Таким чином, представлено метод KNN як один із варіантів розв’язання задачі класифікації. Питання визначення оптимального значення параметра k залишилось відкритим.