ЎҚув материаллари

Минимал масофа критерияси бўйича синфга ажратувчини қуриш

Икки гуруҳ нуқталарини (турли синфларга тегишли) ажратувчи гипертекислик кўринишида қарор функциясини қуриш учун гипертекисликда иккита ҳар бири бутун бир кластерни ифодаловчи иккита нуқтани топиш талаб қилинади. Прототип нуқта, ёки та нуқтадан иборат кластер маркази

формуласи орқали топилади.
Энди берилган образни прототип билан мос қўйиш воситасини топиш керак бўлади. Бундай воситаслардан бири – евклид масофасидир, яъни йўналтирилган масофанинг абсолют қийматидир. Синфланувчи нуқта учун бу нуқтага энг яқин прототип маъқул ҳисобланади ва шу прототип қайси синфга тегишли бўлса, у ҳам шу синфга тегишли ҳисобланади. Ушбу ёндошувга асосланган синфга ажратишни минимал масофа критерияси бўйича қурилган дейилади.
Берилган нуқтасидан прототипгача бўлган масофа қуйидаги формула билан ҳисобланади:

Икки ўлчамли фазо учун (масофалар квавдрати олинади) масофа қуйидагича ҳисобланади:

Умуман олганда, синфлар тўплами учун –синф прототипигача бўлган масофа



Бу формулага эга бўлган ҳолда минимал масофага асосланган синфга ажратувчи қарор функциясини қуриш мумкин. Ифодадаги синфга боғлиқ эмас ва шу сабабли уни ташлаб юбориш мумкин. Қолган ифода қисмини га кўпайтириш орқали қуйидаги қарор функциясига эга бўламиз

қийматини га кўпайтириш орқали қиймати қанча катта бўлса, тўлиқ аналогияга (қичик масофага) бўлишига эришилади.
Энди компонента ҳисоблаш мумкин. Маълумки,

у ҳолда

ва

Қуйидаги расмда функциясининг геометрик интерпретацияси кўрсатилган.



























½

Функциянинг биринчи терми векторнинг векторига проекцияси бўлиб, иккинчиси вектори узунлигининг ярмига тенг. Агар векторнинг векторига проекцияси векторининг ярмидан катта бўлса, қарор функцияси қиймати мусбат бўлади.

Агар минимал масофали синфга ажратувчининг учинчи тоифаси бўлса, қарор функцияси иккита синф прототипларини тутуштирувчи чизиғига ўртсаидан перпендикуляр ўтувчи чизиқ кўринишида бўлади. Шундай қилиб, қарор функция кластерлар прототиплари ўртасидан ўтади ва минимал масофа бўйича синфга ажратишни амалга оширади.
Чизиқли қобиқлар берилган яқинлик (масофа) ўлчови асосида ўргатувчи танловдаги синфлар чегаравий объектларининг қисм тўплами бўлиб, уларни аниқлайдиган усул оптимизацион қидирув усуллар синфига тегишлидир.
Классификация масаласини ечиш учун чизиқли қобиқ усули ёрдамида аниқланган чегаравий объектлар тўплами синфлар эталонлари дейилади. Объектларни коррект ажратиш учун ўргатишда “энг яқин қўшни” қоидасидан фойдаланилади.
Чизиқли қобиқ объектлари ёрдамида минимал сонли синф эталонлари билан минимум масофа бўйича коррект англайдиган самарали “чекли-силжувчи” (конечно-сходящиеся) алгоритмларни қуриш мумкин, параллел ҳисоблаш тизимларида англаш жараёнини реализация қилиш учун ўргатувчи танловни гиперсфера билан минимал қопламани танлаш мумкин. Синф эталонларининг сони синф объектларининг тузилиши ҳақида маълум ахборотни ташийди.
Классификацияланувчи танлов объектларининг чизиқли қобиқлари. Ўзаро кесишмайдиган синфлардан ташкил топган ўргатувчи E₀ танлов қаралади. E₀ танловда минимум масофа бўйича англаш учун эталон сифатида фойдаланиш мумкин бўлган та объектлар бўлсин. E₀ ўргатувчи объектлар тўпламини хатосиз (коррект) синфларга ажратиш учун керак бўладиган минимал сонли эталонларни топиш талаб қилинади.
Rⁿ да рухсат этилган объектлар тўплами учун метрикани киритамиз. Қулайлик учун бундан кейин бу метрикани Евклид метрикаси деб ҳисоблаймиз. Ҳар бир , объект учун метрика ёрдамида ўсиш тартибда тартибланган кетма-кетлик қурамиз, бу ерда - K_j синфга кирмайдиган объектга энг яқин объект бўлсин. , учун барча объектларни ичига олувчи, маркази ва радиуси бўлган атрофни O(S_i) орқали белгилаймиз.
O(S_i) дан шундай объектни топамизки, бунда:
(2.1)
(2.1) бўйича аниқланадиган объектлар тўпламини E₀ объектлар тўпламининг чизиқли қобиғи деб атаймиз. Қулайлик учун чизиқли қобиққа кирувчи L(E₀)={ объектлар индексларини юқорида кўрсатамиз.
Минимум масофа бўйича классификация учун L(E₀) чизиқли қобиқ объектларини эталонлар сифатида қабул қиламиз. Кесик-чизиқли классификатор учун евклид метрикаси G₁,..., гипертекисликлар қуриш шаклида ифодаланади, бу ерда G_i - эталондан олинадиган гипертекислик.
Ихтиёрий рухсат этилган S объект эталон синфига яқинлашади, агар бўлса.