Методи за метрична класификация

В много приложни задачи е много по-лесно да се измери степента на сходство на обектите, отколкото да се формират примерни описания. Например сложни обекти като снимки на лица, подписи, времеви серии или първични структури на протеини се сравняват по-естествено директно един с друг чрез някакво „наслагване с подравняване“, отколкото да се измислят характеристики и да се сравняват описания на характеристиките. Ако мярката за сходство на обектите се въведе достатъчно успешно, тогава, като правило, се оказва, че подобни обекти много често отговарят на подобни отговори. В задачата

По отношение на класификацията това означава, че класовете образуват компактно локализирани подмножества. Това предположение се нарича хипотеза за компактност 5 .

За формализиране на концепцията за „подобие“ се въвежда функция за разстояние в пространството на обектите X. Ще бъдат методи за обучение, базирани на анализа на сходството на обектите

се нарича метрика, дори ако функцията за разстояние не удовлетворява всички аксиоми на метриката (по-специално аксиомата на триъгълника). В англоезичната литература се използват термините обучение или обучение.

§3.1 Метод на най-близкия съсед и неговите обобщения

Нека функцията на разстоянието ρ е дадена на множеството от обекти X: X ×X → [0, ∞) . Има целева зависимост y : X → Y, чиито стойности са само известни

върху обектите от обучителната извадка X ℓ = (x i , y i ) ℓ i =1 , y i = y (x i ) . Множеството от класове Y е крайно. Изисква се да се изгради класификационен алгоритъм a: X → Y , апроксимиращ

съдържащ целевата зависимост y (x) от цялото множество X .

3.1.1 Обобщен метричен класификатор

За произволен обект u X, нека поставим елементите на обучаващото множество x 1 , . . . , x ℓ във възходящ ред на разстоянията до u :

ρ(u, x (1) u ) 6 ρ(u, x (2) u )6 6 ρ(u, x ( u l ) ),

където x (u i) означава съсед на обекта u. Съответно реакцията на изпомпвания обект u е y u ( i ) = y (x ( u i ) ) . Така всеки обект u X генерира свой собствен

Деф. 3.1. Алгоритъмът за метрична класификация с набор за обучение X ℓ присвоява обекта u на класа y Y, за който общото тегло на най-близките обекти за обучение y (u, X ℓ ) е максимално:

a(u; X l ) = arg max y (u, X l );

y (u, X ℓ ) = [y u ( i ) = y] w(i, u);

където тегловната функция w(i, u) оценява степента на важност на съседа за класификацията на обекта u. Функцията y (u, X ℓ ) се нарича оценка на близостта на обекта u до класа y.

5 В математиката ограничените затворени множества обикновено се наричат ​​компактни. Хипотезата за компактността няма нищо общо с тази концепция и по-скоро трябва да се разбира в "ежедневния" смисъл на думата.

Метричният класификатор е дефиниран до тегловната функция w(i, u). Обикновено се избира неотрицателно, не нарастващо по i. Това съответства на хипотезата за компактност, според която колкото по-близо са обектите u и x ( u i ), толкова по-високи са

има вероятност да принадлежат към един и същи клас.

Обучаващият набор X ℓ играе ролята на параметър на алгоритъма a . Персонализиране

необходимо е да запомните селекцията и евентуално да оптимизирате параметрите на функцията за тегло, но самите обекти не се обработват и се запазват ¾както е¿. Алгоритъмът a(u; X ℓ ) изгражда локално приближение на извадката X ℓ и изчисленията се отлагат, докато обектът u стане известен. Според това

Метричните алгоритми се класифицират като методи за мързеливо учене, за разлика от нетърпеливото учене, когато функция, приближаваща извадката, се изгражда на етапа на обучение.

Метрикакласификационните алгоритми се наричат ​​също така разсъждения, базирани на казуси (CBR). Тук наистина можем да говорим за ¾разсъждение¿, тъй като въпросът ¾защо обектът u беше присвоен на класа y?¿

алгоритъмът може да даде обяснение, разбираемо за експертите: ¾ защото има прецеденти от клас y ¿ подобни на него и да представи списък на тези прецеденти.

Избирайки тегловна функция w(i, u), може да се получи различна метрика

класификатори, които са разгледани подробно по-долу.

3.1.2 Метод на най-близкия съсед

Алгоритъмът за най-близък съсед (NN) присвоява обекта на класа u X ℓ на класа, към който принадлежи най-близкият обект за обучение:

w(i, u) = [i = 1]; a(u; X ℓ ) = y u (1) .

Този алгоритъм изглежда е най-простият класификатор. Научаването на NN се свежда до запаметяване на пробата X ℓ. Единствената заслуга на това

лекота на изпълнение на алгоритъма. Има още много недостатъци:

• Нестабилност към грешки. Ако сред обучителните обекти има извънредно положение, обект, който е заобиколен от обекти от чужд клас, тогава не само той ще бъде класифициран неправилно, но и онези околни обекти, за които ще бъде най-близо.

• Липса на параметри, които могат да бъдат коригирани на извадкова основа. Алгоритъмът зависи изцяло от това колко добре е избран показателят ρ.

• В резултат на това качеството на класификацията е лошо.

Алгоритъм на k най-близки съседи (k най-близки съседи, k NN). За да изгладим влиянието на отклоненията, ще припишем обекта u на класа, чиито елементи са по-големи сред k най-близките съседи x ( u i ), i = 1, . . . ,k :

w(i, u) = [i 6 k]; a(u; X ℓ, k) = arg max

За k = 1 този алгоритъм съвпада с предишния, следователно,шумоустойчив. За k = ℓ, напротив, той е прекалено стабилен и се изражда в константа.

44 К. В. Воронцов. Изчислителни методи за обучение, базирано на казуси

Следователно екстремните стойности на k са нежелателни. На практика оптималната стойност на параметъра k се определя от критерия за плъзгащо управление с изключване на обекти с един LOO). За всеки обект x i X ℓ се проверява дали е класифициран правилно от неговите k най-близки съседи.

Обърнете внимание, че ако обектът x i, който трябва да бъде класифициран, не е изключен от обучителната извадка, тогава най-близкият съсед на x i винаги ще бъде самият x i и минималната (нулева) стойност на LOO (k) функционала ще бъде постигната при k = 1.

Съществува и алтернативна версия на метода k NN: във всеки клас се избират k най-близки обекта до u и обект u принадлежи към класа, за който средното разстояние до k най-близки съседи е минимално.

Алгоритъм на k претеглени най-близки съседи. Недостатъкът на k NN е, че

Simum може да се постигне в няколко класа наведнъж. При задачи с два класа това може да се избегне, като се вземе нечетно k. По-обща тактика, която работи-

За случая на много класове, въведете строго намаляваща последователност от реални тегла w i, които определят приноса на съседа към класификацията:

w(i, u) = [i 6 k] w i ; a(u; X ℓ, k) = arg max

Изборът на последователност w i е евристичен. Ако вземем линейно намаляващи тегла w i = k +1 k − i , тогава също могат да възникнат неясноти, макар и по-рядко (за

мерки: два класа; първият и четвъртият съсед гласуват за клас 1, вторият и третият гласуват за клас 2; гласовете са еднакви). Неяснотата най-накрая се елиминира, ако вземем нелинейно намаляваща последователност, да речем, геометрична прогресия: w i = q i , където знаменателятпрогресията q(0, 1) е параметър на алгоритъма. Той може да бъде избран според критерия LOO, подобно на броя на съседите k.

Недостатъци на най-простите метрични алгоритми от тип k NN.

• Трябва да съхранявате целия тренировъчен комплект. Това води до неефективно потребление на памет и прекомерна сложност на правилото за вземане на решения. При наличие на грешки (както в оригиналните данни, така и в модела на подобие ρ )

това може да доведе до намаляване на точността на класификация близо до границата на класа. Има смисъл да изберете минималното подмножество от референтни обекти, които наистина са необходими за класификация.

• Намирането на най-близкия съсед включва сравняване на класифицирания обект с всички обекти в извадката в O(ℓ) операции. За задачи с голям избор -

kami или висока честота на заявките, това може да бъде скъпо. Проблемът се решава с помощта на ефективни алгоритми за намиране на най-близки съседи, които изискват средно O(ln ℓ) операции.

• В най-простите случаи метричните алгоритми имат изключително беден набор от параметри, което изключва възможността за коригиране на алгоритъма според данните.

3.1.3 Метод на прозореца Parzen

Друг начин за присвояване на тегла на съседите е да се дефинира w i като функция на разстоянието

ρ(u, x u ( i ) ) , а не върху ранга на съсед i . Нека въведем ядрена функция K(z), която е ненарастваща

на [0,∞) . Настройка на w(i, u) = ℓ K

формула ( 3.1 ), получаваме алгоритъма

Параметърът h се нарича ширина на прозореца и играе приблизително същата роля като броя на съседите k. ¾Прозорец¿ е сферична околност на обекта u с радиус h, при влизането в която обучаващият обект x i ¾гласува¿ за класифициране на обекта u в клас y i .

Стигнахме до този алгоритъм по чисто евристичен начин, но той има по-строга обосновка в теорията на Байесовата класификация и всъщност,съвпада с метода на прозореца на Парзен.

Параметърът h може да бъде зададен предварително или определен от плъзгащо управление. Зависимостта LOO (h) , като правило, има характерен минимум, т.к

твърде тесните прозорци водят до нестабилна класификация; и твърде широк, за да изроди алгоритъма в константа.

Фиксирането на ширината на прозореца h не е подходящо за тези проблеми, при които обучителните обекти са значително неравномерно разпределени в пространството X . В околностите

Някои обекти могат да имат много съседи, докато други могат да нямат нито един. В тези случаи се използва прозорец с променлива ширина. Вземете крайна ядрена ненарастваща функция K(z), положителна на сегмента [0, 1] и равна на нула извън него. Нека дефинираме h като най-голямото число, така че точно k най-близки съседи на обект u да получат ненулеви тегла: h(u) = ρ(u, x ( u k +1) ) . Тогава

алгоритъмът приема формата

a(u; X ℓ, k) = arg max

Обърнете внимание, че при крайно ядро ​​класификацията на обект се свежда до намиране на неговите съседи, докато при неограничено ядро ​​(например гаусово) се изисква да се изброи цялата обучителна извадка. Изборът на ядро ​​също се обсъжда в раздел 2.2.2.

3.1.4 Метод на потенциалните функции

В метода на прозореца на Парзен центърът на радиалното ядро ​​K h (u, x) = K h 1 ρ(u, x) се поставя в обекта u, който трябва да бъде класифициран. Поради симетрията на функцията на разстоянието ρ(u, x), е възможен и друг, двоен изглед на метричната класификация. Да приемем, че ядрото е поставено във всеки обучаващ обект x i и „дърпа“ обекта u към класа y i, ако попадне в неговия околност с радиус h i :

Всъщност тази формула се различава от (3.3) само по това, че тук ширината на прозореца h i зависи от обучаващия обект x i , а не от класифицирания обект u.

46 K.V.Воронцов. Изчислителни методи за обучение, базирано на казуси

Алгоритъм 3.1. Метод на потенциалните функции

X ℓ обучителна проба;

Коефициенти γ i , i = 1, . . . , l in (3.4);

1: Инициализация: γ i = 0 ; i = 1, . . . , l;

3: изберете обект x i X ℓ ;

4: ако a(x i ) 6= y i тогава

6: докато броят на грешките в извадката стане достатъчно малък

Тази идея е в основата на метода на потенциалните функции [3] и има пряка физическа аналогия с електрическия потенциал. С Y = обучение

зареждащите се обекти могат да се разбират като положителни и отрицателни електрически заряди; коефициенти γ i като абсолютна стойност на тези такси; ядро K(z)

като зависимост на потенциала от разстоянието до заряда; а самата класификационна задача като отговор на въпроса: какъв е знакът на електростатичния потенциал в дадена точка от пространството u. Забележете обаче, че в електростатиката K(z) = z 1 или z + 1 a

за нашите цели абсолютно не е необходимо да вземем точно такова ядро.

Алгоритъмът (3.4) има доста богат набор от 2ℓ параметъра γ i , h i . про-

най-простият и исторически първи метод за настройката им е представен в Алгоритъм 3.1. Той коригира само теглата γ i , като се приема, че радиусите на потенциалите h i и ядрото K са предварително избрани. Идеята е много проста: ако обектът на обучение x i е класифициран неправилно, тогава потенциалът на класа y i е недостатъчен в точката x i и теглото γ i се увеличава

разделено на едно. Изборът на обекти в стъпка 3 е най-добре да се прави не в ред, а в произволен ред. Този метод не е толкова лош, колкото може да се мисли. Условията за неговата конвергенция и множество вариации са изследвани в [3].

Предимството на алгоритъм 3.1 е, че е много ефективен, когато учебните обекти идват в поток и се съхраняват впаметта не е възможна или необходима. В годините, когато беше изобретен методът на потенциалните функции, съхранението на проби наистина беше голям проблем. В момента няма такъв проблем и Алгоритъм 3.1 е от по-скоро исторически интерес.

Алгоритъм 3.1 има доста недостатъци: конвергира бавно; резултатът от обучението зависи от реда, в който са представени обектите; твърде грубо (със стъпка 1) се коригират теглата γ i; потенциалните центрове се поставят само в учебни обекти; проблемът за минимизиране на броя на потенциалите (различни от нула γ i ) изобщо не е поставен; Параметрите h i изобщо не са конфигурирани. В резултат на това този алгоритъм

не може да се похвали с висококачествена класификация.

По-модерен метод за настройка на линейни комбинации от потенциални функции, базиран на, е разгледан в §2.4. Позволява ви да оптимизирате ширината на всеки потенциал и позицията на центровете и дори броя на потенциалите. Името на метода също се промени: вече потенциални функции

---