Метад бліжэйшага суседа: прыклад працы

Метад бліжэйшага суседа ўяўляе сабой самы просты метрычны класіфікатар, які грунтуецца на ацэньванні падабенства розных аб'ектаў.

Аналізуемы аб'ект адносяць да класа, да якога належаць прадметы навучальнай выбаркі. Высветлім, што ўяўляе сабой метад бліжэйшага суседа. Паспрабуем разабрацца ў гэтым складаным пытанні, прывесці прыклады розных методык.

гіпотэза метаду

Метад бліжэйшага суседа можна лічыць самым распаўсюджаным алгарытмам, выкарыстоўваным для класіфікацыі. Аб'ект, які падвяргаецца класіфікацыі належыць да таго класу y_i, да якога належыць самы блізкі аб'ект навучальнай выбаркі x_i.

Спецыфіка методыкі бліжэйшых суседзяў

Метад k бліжэйшых суседзяў дазваляе павышаць дакладнасць класіфікацыі. Аналізуемы аб'ект належыць да таго ж класу, што і асноўная маса яго суседзяў, то ёсць k блізкіх да яго аб'ектаў аналізаванай выбаркі x_i. Пры вырашэнні задач з двума класамі колькасць суседзяў будзе няцотных, каб выключыць сітуацыю неадназначнасці, калі адно і тое ж лік суседзяў будзе належаць розных класах.

Методыка ўзважаных суседзяў

Аналізуемы postgresql-метад бліжэйшых суседзяў tsvector выкарыстоўваецца, калі колькасць класаў не менш за тры, і нельга скарыстацца няцотныя. Але неадназначнасць ўзнікае нават у гэтых выпадках. Тады i-й сусед атрымлівае вага w_i, які меншае з павелічэннем рангу суседа i. Адносіцца аб'ект да класа, які будзе мець максімальны сумарны вага сярод блізкіх суседзяў.

гіпотэза кампактнасці

У аснове ўсіх вышэйзгаданых метадаў знаходзіцца гіпотэза кампактнасці. Яна мяркуе сувязь паміж мерай падабенства аб'ектаў і прыналежнасцю іх да аднаго класа. У падобнай сітуацыі мяжа паміж рознымі відамі мае нескладаную форму, а класы ствараюць у прасторы аб'ектаў кампактныя мабільныя вобласці. Пад такімі абласцямі ў матэматычным аналізе прынята разумець замкнёныя абмежаваныя мноства. Дадзеная гіпотэза не звязаная з паўсядзённым успрыманнем гэтага слова.

Асноўная формула

Разбяром падрабязней метад бліжэйшага суседа. Калі прапанаваная навучалая выбарка выгляду «аб'ект-адказ» X ^ m = \ {(x_1, y_1), \ dots, (x_m, y_m) \}; калі для мноства аб'ектаў задаюць функцыю адлегласці \ rho (x, x '), якая прадстаўлена ў выглядзе адэкватнай мадэлі падабенства аб'ектаў, пры павелічэнні значэння дадзенай функцыі паніжаецца падабенства паміж аб'ектамі x, x'.

Для любога аб'екта u выбудуем аб'екты навучальнай выбаркі x_i па меры ўзрастання адлегласцяў да u:

\ Rho (u, x_ {1; u}) \ leq \ rho (u, x_ {2; u}) \ leq \ cdots \ leq \ rho (u, x_ {m; u}),

дзе x_ {i; u} характарызуе аб'ект навучальнай выбаркі, які з'яўляецца i-м суседам зыходнага аб'екта u. Падобнае пазначэнне выкарыстоўваем і для адказу на i-м суседзе: y_ {i; u}. У выніку атрымліваем, што адвольны аб'ект u правакуе змена нумарацыі уласнай выбаркі.

Азначэнне ліку суседзяў k

Метад бліжэйшага суседа пры k = 1 здольны даваць памылковую класіфікацыю, прычым не толькі на аб'ектах-выкідах, але і для іншых класаў, якія размешчаны паблізу.

Калі ўзяць k = m, алгарытм будзе максімальна устойлівым і звядзецца ў пастаянную велічыню. Менавіта таму для пэўнасці важна не дапускаць крайніх паказчыкаў k.

На практыцы ў якасці аптымальнага паказчыка k ўжываюць крытэрый слізгальнага кантролю.

адсеў выкідаў

Аб'екты навучання ў асноўным з'яўляюцца неравноценны, але сярод іх ёсць такія, якія валодаюць характэрнымі прыкметамі класа і называюцца эталонамі. Пры блізкасці разгляданага прадмета да ідэальнага ўзору высокая верагоднасць яго прыналежнасці да дадзенага класа.

Наколькі выніковы метад бліжэйшых суседзяў? Прыклад можна паглядзець на аснове перыферыйных і неінфарматыўныя катэгорый аб'ектаў. Мяркуецца шчыльнае асяроддзе разгляданага аб'екта іншымі прадстаўнікамі дадзенага класа. Пры выдаленні іх з ўзятай выбаркі якасць класіфікацыі не пацерпіць.

Трапіць у такую выбарку можа вызначаны лік шумавых выкідаў, якія знаходзяцца «у гушчы» іншага класа. Выдаленне ў асноўным станоўча адбіваецца на якасці якая праводзіцца класіфікацыі.

Калі з ўзятай выбаркі ліквідуюць неінфарматыўныя і шумавыя аб'екты, можна разлічваць на некалькі станоўчых вынікаў адначасова.

У першую чаргу інтэрпаляцыя метадам бліжэйшага суседа дазваляе павышаць якасць класіфікацыі, скарачаць аб'ём захоўваюцца дадзеных, памяншаць час класіфікацыі, якое затрачваецца на выбар бліжэйшых эталонаў.

Прымяненне звышвялікіх выбарак

Метад бліжэйшых суседзяў грунтуецца на рэальным захоўванні навучальных аб'ектаў. Для стварэння звышвялікіх выбарак выкарыстоўваюць тэхнічныя праблемы. Ставіцца задача не проста захаваць істотны аб'ём інфармацыі, але і ў мінімальны часовай прамежак паспяваць знаходзіць адвольны аб'ект u сярод бліжэйшых k суседзяў.

Для таго каб справіцца з пастаўленай задачай, ужываюць два спосабу:

• прарэжваюць выбарку з дапамогай выкідання неинформационных аб'ектаў;
• ўжываюць спецыяльныя эфектыўныя структуры і індэксы дадзеных для маментальнага пошуку бліжэйшых суседзяў.

Правілы падбору методыкі

Вышэй была разгледжана класіфікацыя. Метад бліжэйшага суседа ўжываюць пры вырашэнні практычных задач, у якіх вядомая загадзя функцыя адлегласці \ rho (x, x '). Пры апісанні аб'ектаў лікавымі вектарамі выкарыстоўваюць эўклідавай метрыку. Падобны выбар не мае спецыяльнага абгрунтавання, але мае на ўвазе вымярэнне ўсіх прыкмет «ў адзіным маштабе». Калі не ўлічыць гэты фактар, то ў метрыцы будзе пераважаць прыкмета, які мае найбольшыя лікавыя значэння.

Пры наяўнасці істотнага колькасці прыкмет, вылічэнні адлегласці ў выглядзе сумы адхіленняў па канкрэтных прыкметах з'яўляецца сур'ёзная праблема памернасці.

У прасторы высокай памернасці далёкімі адзін ад аднаго апынуцца ўсе аб'екты. У канчатковым выніку адвольнай будзе выбарка бліжэйшых для вывучаемай аб'екта k суседзяў. Для ліквідацыі падобнай праблемы адбіраецца невялікі лік інфарматыўных прыкмет. Алгарытмы разліку адзнак выбудоўваюць на аснове розных набораў прыкмет, прычым для кожнага асобнага выбудоўваюць сваю функцыю блізкасці.

заключэнне

Матэматычныя вылічэнні даволі часта мяркуюць прымяненне разнастайных методык, якія маюць свае адметныя характарыстыкі, перавагі і недахопы. Разгляданы метад бліжэйшых суседзяў дазваляе вырашаць досыць сур'ёзныя праблемы, звязаныя з характарыстыкай матэматычных аб'ектаў. Эксперыментальныя канцэпцыі, якія базуюцца на прааналізавалі методыцы, у цяперашні час актыўна выкарыстоўваюць у сродках штучнага інтэлекту.

У экспертных сістэмах неабходна не проста класіфікаваць аб'екты, але і паказваць карыстачу тлумачэнне разгляданай класіфікацыі. У дадзеным метадзе тлумачэнні падобнай з'явы выяўляюцца стаўленнем аб'екта да вызначанага класа, а таксама размяшчэннем яго адносна выкарыстоўванай выбаркі. Спецыялісты юрыдычнай галіны, геолагі, медыкі, прымаюць гэтую «прэцэдэнтнага» логіку, актыўна карыстаюцца ёю ў сваіх даследаваннях.

Для таго каб аналізуемы метад быў максімальна пэўным, эфектыўным, даваў жаданы вынік, неабходна браць мінімальны паказчык k, а таксама не дапускаць выкідаў сярод аналізаваных аб'ектаў. Менавіта таму і ўжываюць методыку выбару эталонаў, а таксама праводзяць аптымізацыю метрык.