Olemasolevate mustrituvastusmeetodite ülevaade. Mustri äratundmine

Saada oma head tööd teadmistebaasi on lihtne. Kasutage allolevat vormi

Üliõpilased, magistrandid, noored teadlased, kes kasutavad teadmistebaasi oma õpingutes ja töös, on teile väga tänulikud.

postitatud http://www.allbest.ru/

Vene Föderatsiooni haridus- ja teadusministeerium

Novosibirsk Riiklik Ülikool Majandus ja juhtimine "NINH"

Infotehnoloogia teaduskond

Rakenduslike infotehnoloogiate osakond

distsipliinis Hägusloogika ja närvivõrgud

Mustri äratundmine

Suund: Äriinformaatika (elektrooniline äri)

Õpilase täisnimi: Mazur Ekaterina Vitalievna

Kontrollis: Pavlova Anna Illarionovna

Novosibirsk 2016

• Sissejuhatus
• 1. Tunnustamise mõiste
• 1.1 Arengu ajalugu
• 1.2 Mustrituvastusmeetodite klassifikatsioon
• 2. Mustri tuvastamise meetodid
• 3. üldised omadused mustrituvastuse ülesanded ja nende liigid
• 4. Mustrituvastuse arendamise probleemid ja väljavaated
• 4.1 Mustrituvastuse rakendamine praktikas
• Järeldus

Sissejuhatus

Päris pikka aega käsitleti mustrituvastuse probleemi ainult bioloogilisest vaatenurgast. Sel juhul täheldati ainult kvalitatiivseid omadusi, mis ei võimaldanud kirjeldada toimimismehhanismi.

N. Wieneri poolt 20. sajandi alguses kasutusele võetud mõiste küberneetika(teadus masinate, elusorganismide ja ühiskonna juhtimisprotsesside ja infoedastuse üldistest seaduspäradest), võimaldas kasutusele võtta kvantitatiivseid meetodeid tunnustamise küsimustes. See tähendab, et kujutage ette seda protsessi (sisuliselt - loodusnähtus) kasutades matemaatilisi meetodeid.

Mustrituvastuse teooria on üks peamisi küberneetika harusid nii teoreetilises kui ka rakenduslikus mõttes. Seega hõlmab mõne protsessi automatiseerimine seadmete loomist, mis on võimelised reageerima muutuvatele omadustele väliskeskkond mõned positiivsed reaktsioonid.

Selle taseme probleemide lahendamise aluseks on tulemused klassikaline teooria statistilised lahendused. Selle raames ehitati algoritmid, et määrata klass, kuhu saab tuvastatud objekti klassifitseerida.

Käesoleva töö eesmärk on tutvuda mustrituvastuse teooria mõistetega: paljastada peamised definitsioonid, uurida selle esinemise ajalugu ning tuua välja teooria peamised meetodid ja põhimõtted.

Teema aktuaalsus seisneb selles, et hetkel on mustrituvastus küberneetika üks juhtivaid valdkondi. Nii on see viimastel aastatel leidnud üha enam kasutust: lihtsustab inimeste suhtlemist arvutiga ja loob eeldused erinevate süsteemide kasutamiseks tehisintellekt.

pildituvastusrakendus

1. Tunnustamise mõiste

Tunnustamise probleem köitis pikka aega vaid selle valdkonna teadlaste tähelepanu. rakendusmatemaatika. Selle tulemusena ilmusid aastal loodud R. Fischeri teosed 20ndad, viis diskriminantanalüüsi kujunemiseni – mustrite tuvastamise teooria ja praktika ühe haruni. IN 40ndad A. N. Kolmogorov ja A. Ya. Khinchin seadsid eesmärgiks eraldada kahe jaotuse segu. Ja sisse 50-60ndad aastate kahekümnenda sajandi põhjal suur kogus teoseid, ilmus statistiliste otsuste teooria. Küberneetika raames on hakanud tekkima uus suund, mis on seotud teoreetiliste aluste väljatöötamise ja mehhanismide praktilise rakendamisega, samuti objektide ja protsesside äratundmiseks loodud süsteemidega. Uut distsipliini nimetatakse "mustri äratundmiseks".

Mustri äratundmine(objektid) on ülesanne tuvastada objekt selle kujutise (optiline tuvastamine), helisalvestuse (akustiline äratundmine) või muude tunnuste järgi. Pilt on klassifikatsiooni rühmitus, mis võimaldab kombineerida objektide rühma teatud kriteeriumide järgi. Pildid on olemas iseloomulik tunnus, mis väljendub selles, et ühest komplektist piiratud arvu nähtustega tutvumine võimaldab ära tunda suure hulga selle esindajaid. Tunnustusprobleemi klassikalises sõnastuses on komplekt jagatud osadeks.

Üks põhimääratlusi on ka mõiste paljusid. Arvutis on komplekt sama tüüpi mittekorduvate elementide kogum. "Mittekorduv" tähendab, et element komplektis on olemas või mitte. Universaalne komplekt sisaldab kõiki võimalikke elemente, tühi komplekt ei sisalda ühtegi.

Tehnikat, kuidas mõnele pildile elemendi omistamine toimub, nimetatakse otsustav reegel. Teine oluline mõiste on mõõdikud- määrab komplekti elementide vahelise kauguse. Mida väiksem on see kaugus, seda sarnasemad on objektid (sümbolid, helid jne), mida me ära tunneme. Tavaliselt määratakse elemendid arvude kogumina ja mõõdik on määratud mingi funktsioonina. Programmi efektiivsus sõltub pildi esituse valikust ja meetrika teostusest: sama tuvastusalgoritm erinevate mõõdikutega teeb erineva sagedusega vigu.

Koolitus Tavaliselt nimetatakse protsessiks teatud süsteemis ühe või teise reaktsiooni väljatöötamine väliste sarnaste signaalide teguritele nende korduva mõju kaudu süsteemile. Iseseisev õppimine erineb koolitusest selle poolest, et siin ei anta süsteemile lisainfot reaktsiooni kohta.

Mustrituvastusülesannete näited on järgmised:

Kirjade äratundmine;

Vöötkoodituvastus;

Numbrimärgituvastus;

Nägude ja muude biomeetriliste andmete tuvastamine;

Kõnetuvastus jne.

1.1 Lugu arengut

50. aastate keskpaigaks seadis R. Penrose kahtluse alla aju närvivõrgu mudeli, osutades kvantmehaaniliste mõjude olulisele rollile selle toimimises. Sellest lähtuvalt töötas F. Rosenblatt välja tunnustamisõppe mudeli visuaalsed pildid, mida nimetatakse pertseptroniks.

Joonistamine1 - Perceptroni ahel

Lisaks leiutati erinevaid pertseptroni üldistusi ja neuronite funktsioon oli keeruline: neuronid ei saanud mitte ainult sisendnumbreid korrutada ja tulemust läviväärtustega võrrelda, vaid ka rohkem rakendada. keerukad funktsioonid. Joonis 2 näitab ühte sellist komplikatsiooni:

Riis. 2 Närvivõrgu skeem.

Lisaks võib närvivõrgu topoloogia olla veelgi keerulisem. Näiteks nii:

Joonis 3 – Rosenblatti närvivõrgu skeem.

Närvivõrgud, mis on keeruline objekt matemaatiline analüüs, õigel kasutamisel võimaldas leida väga lihtsad seadused andmeid. Kuid see eelis on ka võimalike vigade allikas. Analüüsi keerukust seletab üldiselt ainult keeruline struktuur, kuid sellest tulenevalt praktiliselt ammendamatud võimalused väga erinevate mustrite üldistamiseks.

1.2 Klassifikatsioonmeetodidtunnustustpilte

Nagu me juba märkisime, viitab mustrituvastus ülesandele luua samaväärsussuhted objektide teatud kujutiste mudelite vahel reaalses või ideaalses maailmas.

Need seosed määravad ära tunnustatud objektide kuulumise mis tahes klassidesse, mida peetakse iseseisvateks üksusteks.

Tuvastamisalgoritmide koostamisel saab neid klasse täpsustada uurija, kes kasutab oma ideid või kasutab antud ülesande kontekstis lisainfot objektide sarnasuse või erinevuse kohta. Sel juhul räägime "tunnustamisest koos õpetajaga". Teises, s.o. Kui automatiseeritud süsteem lahendab klassifitseerimisprobleemi ilma täiendavat teavet kaasamata, räägivad nad "järelevalveta tuvastamisest".

Töödes V.A. Duke annab akadeemilise ülevaate tunnustamismeetoditest ja kasutab teadmiste esitamiseks kahte peamist viisi:

Intensionaalne (atribuutide vaheliste seoste diagrammi kujul);

Laiendus, kasutades konkreetseid fakte (objektid, näited).

Intensionaalne esitus kajastab mustreid, mis selgitavad andmete struktuuri. Seoses diagnostiliste probleemidega seisneb selline fikseerimine soovitud tulemuseni viivate objektide omadustega seotud toimingute määramises. Intensionaalseid esitusi rakendatakse väärtustega seotud toimingute kaudu ja need ei hõlma toiminguid konkreetsete objektidega.

Teadmiste ekstensiivsed esitused on omakorda seotud konkreetsete ainevaldkonna objektide kirjeldamise ja fikseerimisega ning realiseeritakse operatsioonides, mille elementideks on objektid iseseisvate süsteemidena.

Seega on V.A. välja pakutud tunnustamismeetodite klassifitseerimise alus. Hertsog, on kehtestatud põhiseadused, mis on põhimõtteliselt aluseks inimese tunnetusviisile. See seab selle klassideks jaotuse erilisele positsioonile võrreldes teiste vähemtuntud klassifikaatoritega, mis sellel taustal tunduvad kunstlikud ja puudulikud.

2. meetodidmustrituvastus

Toore jõu meetod. Selle meetodi puhul tehakse võrdlus teatud andmebaasiga, kus iga objekti kohta erinevad variandid kuva muudatused. Näiteks optilise mustrituvastuse jaoks saate kasutada erinevate nurkade või mõõtkavade, nihkete, deformatsioonide jms loendamise meetodit. Tähtede puhul saate loetleda fondi või selle omadused. Häälikumustri tuvastamise puhul võrreldakse mõningate teadaolevate mustritega (paljude inimeste räägitud sõna). Järgmisena tehakse pildi omaduste põhjalikum analüüs. Optilise tuvastamise puhul võib selleks olla geomeetriliste karakteristikute määramine. Sel juhul tehakse helinäidis sageduse ja amplituudi analüüsi.

Järgmine meetod - kunstliku kasutamine närvivõrgud (INS). See nõuab kumbagi tohutu hulkäratundmisülesande näited või närvivõrgu eristruktuur, mis arvestab antud ülesande spetsiifikat. Kuid sellest hoolimata on see meetod väga tõhus ja produktiivne.

Meetodid, mis põhinevad tunnuste väärtuste jaotustiheduse hinnangutel. Laenatud klassikalisest statistiliste otsuste teooriast, milles uuritavaid objekte käsitletakse mitmemõõtmelise teooriana. juhuslik muutuja, mis on jaotatud tunnusruumis mõne seaduse järgi. Need põhinevad Bayesi otsustusskeemil, mis apelleeritakse teatud klassi kuuluvate objektide esialgsetele tõenäosustele ja tunnuste tingimuslikele jaotustihedustele.

Tunnuste väärtuste jaotustiheduse hindamisel põhinev meetodite rühm on otseselt seotud diskriminantanalüüsi meetoditega. Bayesi lähenemine otsuste tegemisele on kaasaegse statistika üks arenenumaid parameetrilisi meetodeid, mille puhul eeldatakse, et jaotusseaduse (normaalseaduse) analüütiline väljendus on teada ja ainult väike arv parameetreid (keskmiste vektorid ja kovariatsioonimaatriksid) ) tuleb hinnata. Selle meetodi kasutamise peamisteks raskusteks peetakse vajadust meeles pidada kogu treeningvalimi tiheduse hinnangute arvutamiseks ja suurt tundlikkust treeningvalimi suhtes.

Meetodid, mis põhinevad oletustel otsustusfunktsioonide klassi kohta. Selles rühmas peetakse seda tuntud liigid määrava funktsiooni ja selle kvaliteedi funktsionaalsust. Selle funktsiooni põhjal leitakse treeningjärjestuse abil optimaalne lähendus otsustusfunktsioonile. Otsustusreegli kvaliteedifunktsioon on tavaliselt seotud veaga. Meetodi peamiseks eeliseks on äratundmisprobleemi matemaatilise sõnastuse selgus.Võime ammutada uusi teadmisi objekti olemuse kohta, eelkõige teadmisi atribuutide interaktsiooni mehhanismide kohta, on siinkohal antud struktuuriga põhimõtteliselt piiratud. interaktsiooni, fikseeritud otsustusfunktsioonide valitud vormis.

Prototüübiga võrdlemise meetod. See on praktikas lihtsaim laiendustuvastusmeetod. Seda kasutatakse siis, kui tunnustatud klassid on näidatud kompaktsete geomeetriliste klassidena. Seejärel valitakse prototüübipunktiks geomeetrilise rühmituse keskpunkt (või keskpunktile kõige lähemal asuv objekt).

Määratlemata objekti klassifitseerimiseks leitakse sellele lähim prototüüp ja objekt kuulub temaga samasse klassi. Ilmselgelt ei teki selle meetodi puhul üldistatud kujundeid. Mõõdikuna saab kasutada erinevat tüüpi kaugusi.

k lähimate naabrite meetod. Meetod seisneb selles, et tundmatu objekti klassifitseerimisel leitakse etteantud arv (k) geomeetriliselt kõige lähemaid tunnuseid teiste lähimate naabrite ruumist, kelle kuuluvus mis tahes klassi juba on teada. Otsus tundmatu objekti klassifitseerimise kohta tehakse selle lähimate naabrite kohta infot analüüsides. Selle meetodi puuduseks on vajadus vähendada õppevalimis olevate objektide arvu (diagnostilised pretsedendid), kuna see vähendab koolitusvalimi esinduslikkust.

Lähtudes sellest, et erinevad tuvastusalgoritmid käituvad samal valimil erinevalt, tekib küsimus sünteetilisest otsustusreeglist, mis kasutaks ära kõikide algoritmide tugevused. Selleks on sünteetiline meetod või otsustusreeglite rühmad, mis ühendavad iga meetodi kõige positiivsemad küljed.

Tuvastamismeetodite ülevaate lõpetuseks esitame ülaltoodu olemuse pöördetabel, lisades ka mõned teised praktikas kasutatavad meetodid.

Tabel 1. Tuvastamismeetodite klassifikatsiooni tabel, nende kasutusalade ja piirangute võrdlus

3. Mustrituvastusprobleemide üldtunnused ja nende liigid

Tuvastamissüsteemi üldine struktuur ja selle etapid on näidatud joonisel 4:

Joonis 4 - Tunnustussüsteemi struktuur

Tuvastamisülesannetel on järgmised iseloomulikud etapid:

Lähteandmete teisendamine mugavale tuvastamise vormile;

Äratundmine (näitab, et objekt kuulub teatud klassi).

Nendes ülesannetes saab tutvustada objektide sarnasuse mõistet ja sõnastada reeglistiku, mille alusel objekt kuulub ühte või erinevatesse klassidesse.

Samuti saab opereerida näidete komplektiga, mille klassifikatsioon on teada ja mida saab etteantud kirjelduste kujul deklareerida tuvastusalgoritmile õppeprotsessi käigus ülesandega kohandamiseks.

Raskused äratundmisprobleemide lahendamisel on seotud suutmatusega rakendada klassikalisi matemaatilisi meetodeid ilma parandusteta (sageli pole täpse matemaatilise mudeli teave saadaval)

Eristatakse järgmist tüüpi tuvastusülesandeid:

Tuvastamisülesandeks on esitletava objekti määramine selle kirjelduse järgi ühte etteantud klassist (juhendatud õpe);

Automaatse klassifitseerimise ülesanne on jaotada hulk disjunktsete klasside süsteemiks (taksonoomia, klasteranalüüs, iseõppimine);

Ülesanne valida äratundmisel informatiivne atribuutide komplekt;

Lähteandmete mugavasse vormi viimise ülesanne;

Dünaamiline tuvastamine ja klassifitseerimine;

Prognoosiprobleem – see tähendab, et otsus peab olema seotud konkreetse tulevikupunktiga.

Olemasolevates tunnustamissüsteemides on kaks kõige raskemat probleemi:

Probleem “1001 klass” - 1 klassi lisamine 1000 olemasolevale põhjustab raskusi süsteemi ümberõppel ja varem saadud andmete kontrollimisel;

Sõnastiku ja allikate vahelise korrelatsiooni probleem on kõnetuvastuses kõige selgem. Praegused süsteemid suudavad ära tunda kas suure hulga sõnu väikeselt isikute rühmalt või väikese arvu sõnu suurelt isikute rühmalt. Samuti on raske ära tunda suurt hulka meigi või grimassidega nägusid.

Närvivõrgud neid probleeme otseselt ei lahenda, kuid oma olemuse tõttu kohanduvad sisendjadade muutustega palju kergemini.

4. Probleemid ja väljavaatedarengutmustrituvastus

4.1 Mustrituvastuse rakendamine praktikas

Üldiselt koosneb mustrituvastuse probleem kahest osast: koolitusest ja äratundmisest. Õppimine toimub iseseisvate objektide näitamise ja ühte või teise klassi määramise teel. Treeningu tulemusena peaks äratundmissüsteem omandama oskuse reageerida samade reaktsioonidega ühe pildi kõikidele objektidele ja erinevatele teistele. Oluline on, et õppeprotsessi käigus märgitaks ainult objektid ise ja nende seotus pildiga. Koolitusele järgneb äratundmisprotsess, mis iseloomustab juba koolitatud süsteemi tegevust. Probleemiks on nende protseduuride automatiseerimine.

Enne mis tahes objekti analüüsi alustamist peate hankima selle kohta kindlat, järjestatud ja täpset teavet. Selline teave on objektide omaduste kogum, nende kuvamine tuvastussüsteemi mitmesugustel tajuorganitel.

Kuid iga vaatlusobjekt võib sõltuvalt tajutingimustest mõjutada erinevalt. Lisaks võivad sama pildi objektid üksteisest oluliselt erineda.

Iga objekti kaardistamist tuvastussüsteemi tajuorganitele, olenemata selle asukohast nende organite suhtes, nimetatakse tavaliselt objekti kujutiseks ja selliste kujutiste kogumiks, mida ühendavad mõned üldised omadused, kujutavad pilte. Esialgse kirjelduse (tunnuse ruumi) eduka valiku korral võib äratundmisülesanne osutuda üsna lihtsaks ja vastupidi, ebaõnnestunud valik võib viia väga keerulise info edasise töötlemiseni või lahenduse puudumiseni.

Objektide, signaalide, olukordade, nähtuste äratundmine on kõige tavalisem ülesanne, mida inimene peab iga sekund lahendama. Selleks kasutatakse tohutuid ajuressursse, mida hinnatakse sellise näitajaga nagu neuronite arv, mis on võrdne 10 10-ga.

Samuti kohtab tehnoloogias pidevalt äratundmist. Arvutused formaalsete neuronite võrkudes on paljuski sarnased ajus toimuva teabetöötlusega. Viimasel kümnendil on neuroarvuti saavutanud äärmise populaarsuse ja sellest on saanud kommertstoodete tootmisega seotud inseneriteadus. Neuroarvutitele elementaarse baasi loomiseks on käimas suur töö.

Nende peamine iseloomulik tunnus on võime lahendada vormistamata probleeme, mille jaoks ühel või teisel põhjusel lahendusalgoritme välja ei pakuta. Neuroarvutid pakuvad suhteliselt lihtsat tehnoloogiat algoritmide tuletamiseks õppimise kaudu. See on nende peamine eelis. Seetõttu osutub neuroarvuti aktuaalseks just praegu – multimeedia hiilgeajal, mil globaalne areng nõuab uute, pildituvastusega tihedalt seotud tehnoloogiate väljatöötamist.

Üks peamisi probleeme tehisintellekti arendamisel ja rakendamisel on endiselt heli- ja visuaalsete kujutiste äratundmise probleem. Kõik muud tehnoloogiad on juba valmis leidma rakendust meditsiinis, bioloogias ja turvasüsteemides. Meditsiinis aitab mustrituvastus arstidel täpsemaid diagnoose panna, tehastes kasutatakse seda kaubapartiide defektide ennustamiseks. Biomeetrilised isikutuvastussüsteemid põhinevad ka tuvastustulemustel kui nende algoritmilisel tuumal. Inimestega loomulikes keeltes ja kõne kaudu inimestega vahetumalt suhtlevate arvutite edasiarendamist ja disainimist ei saa lahendada ilma äratundmiseta. Siin tekib küsimus robootika ja tehisjuhtimissüsteemide arendamise kohta, mis sisaldavad tuvastussüsteeme kui olulisi alamsüsteeme.

Järeldus

Töö tulemusena tehti lühiülevaade sellise küberneetika haru nagu mustrituvastus mõistete peamistest definitsioonidest, toodi välja äratundmismeetodid, sõnastati ülesanded.

Loomulikult on selle teaduse arendamiseks palju suundi. Lisaks, nagu ühes peatükis öeldud, on tunnustamine hetkel üks võtmetähtsusega arenguvaldkondi. Niisiis, tarkvara lähikümnenditel võib see muutuda kasutajale veelgi atraktiivsemaks ja kaasaegsel turul konkurentsivõimelisemaks, kui see omandab kommertsformaadi ja hakkab levima suure hulga tarbijate seas.

Edasised uuringud võivad olla suunatud järgmistele aspektidele: peamiste töötlemismeetodite süvaanalüüs ja uute kombineeritud või modifitseeritud tuvastamismeetodite väljatöötamine. Läbiviidud uuringute põhjal on võimalik välja töötada funktsionaalne äratundmissüsteem, mille abil on võimalik valitud tuvastusmeetodite efektiivsust testida.

Bibliograafia

1. David Formais, Jean Pons Arvutinägemine. Kaasaegne lähenemine, 2004

2. Aizerman M.A., Braverman E.M., Rozonoer L.I. Potentsiaalsete funktsioonide meetod masinõppe teoorias. - M.: Nauka, 2004.

3. Zhuravlev Yu.I. Algebralisest lähenemisest äratundmis- või klassifitseerimisprobleemide lahendamisele // Küberneetika probleemid. M.: Nauka, 2005. - Väljaanne. 33.

4. Mazurov V.D. Ebavõrdsussüsteemide komiteed ja äratundmisprobleem // Küberneetika, 2004, nr 2.

5. Potapov A.S. Mustri tuvastamine ja masina tajumine. - Peterburi: Politehnika, 2007.

6. Minsky M., Papert S. Perceptrons. - M.: Mir, 2007.

7. Rastrigin L. A., Erenshtein R. Kh. Kollektiivse tunnustamise meetod. M. Energoizdat, 2006.

8. Rudakov K.V. Klassifitseerimisprobleemide universaalsete ja lokaalsete piirangute algebralisest teooriast // Tuvastamine, klassifitseerimine, prognoos. Matemaatilised meetodid ja nende rakendamine. Vol. 1. - M.: Nauka, 2007.

9. Fu K. Struktuursed meetodid mustrituvastuses. - M.: Mir, 2005.

Postitatud saidile Allbest.ru

Sarnased dokumendid

Mustrituvastuse teooria põhimõisted ja selle tähendus. Essents matemaatiline teooria mustrituvastus. Peamised ülesanded, mis tekivad pildituvastussüsteemide väljatöötamisel. Reaalajas mustrituvastussüsteemide klassifikatsioon.

kursusetöö, lisatud 15.01.2014


Mustrituvastusalgoritmide konstrueerimise kontseptsioon ja omadused. Erinevad lähenemised äratundmismeetodite tüpoloogiale. Põhiliste teadmiste esitamise viiside uurimine. Intensiooni- ja ekstensioonimeetodite tunnused, nende kvaliteedi hindamine.

esitlus, lisatud 01.06.2014


Mustrituvastuse teoreetilised alused. Tuvastamissüsteemi funktsionaalne diagramm. Bayesi meetodite rakendamine mustrituvastuse probleemi lahendamisel. Bayesi kujutise segmenteerimine. TAN mudel kujutiste klassifitseerimise probleemi lahendamiseks.

lõputöö, lisatud 13.10.2017


Ülevaade mustrituvastussüsteemide arendamisel tekkivatest probleemidest. Koolitatavad pildi klassifikaatorid. Pertseptroni algoritm ja selle modifikatsioonid. Programmi loomine, mis on mõeldud piltide klassifitseerimiseks väikseima keskmise vea meetodil.

kursusetöö, lisatud 04.05.2015


Mustri tuvastamise meetodid (klassifikaatorid): Bayesi, lineaarne, potentsiaalse funktsiooni meetod. Programmi väljatöötamine inimese äratundmiseks tema fotode järgi. Näiteid klassifikaatorite tööst, katsetulemused meetodite täpsuse kohta.

kursusetöö, lisatud 15.08.2011


Tehisnärvivõrkudel põhineva visuaalse pildituvastuse teostava tarkvara tööriista loomine. Mustri tuvastamiseks kasutatavad meetodid. Selfridge's Pandemonium. Rosenblatt Perceptron. Ahelkoodi moodustamise reegel.

lõputöö, lisatud 04.06.2014


Mustri tuvastamine on ülesanne tuvastada objekt või määrata selle omadused selle pildi või helisalvestuse põhjal. Selle valdkonna teoreetiliste ja tehniliste muutuste ajalugu. Arvutitehnoloogias kasutatavad meetodid ja põhimõtted äratundmiseks.

abstraktne, lisatud 10.04.2010


Mustrituvastussüsteemi kontseptsioon. Tunnistussüsteemide klassifikatsioon. Mikroobjektide kuju äratundmise süsteemi väljatöötamine. Algoritm mikroobjektide tuvastamise süsteemi loomiseks kristallogrammil, selle rakendamise tunnused tarkvarakeskkonnas.

kursusetöö, lisatud 21.06.2014


Närvivõrgu tüübi ja struktuuri valimine. Tuvastamismeetodi valik, Hopfieldi võrgu plokkskeem. Mustrituvastussüsteemi koolitamine. Programmiga töötamise omadused, selle eelised ja puudused. Kasutajaliidese ja ekraanivormide kirjeldus.

kursusetöö, lisatud 14.11.2013


Tehniliste automaatsete tuvastussüsteemide tekkimine. Inimene kui kompleksi element või lüli automaatsed süsteemid. Automaattuvastusseadmete võimalused. Mustrituvastussüsteemi loomise etapid. Mõõtmis- ja kodeerimisprotsessid.

Ja märgid. Sellised probleemid lahenevad üsna sageli näiteks fooritulede järgi tänava ületamisel või möödumisel. Põletatud foori värvi äratundmine ja reeglite tundmine liiklust võimaldab teil teha õige otsuse selle kohta, kas saate hetkel tänavat ületada või mitte.

Bioloogilise evolutsiooni käigus lahendasid paljud loomad probleeme oma nägemis- ja kuulmisaparaadi abil. mustrituvastus piisavalt hea. Tehissüsteemide loomine mustrituvastus on endiselt keeruline teoreetiline ja tehniline probleem. Vajadus sellise tunnustamise järele tekib erinevates valdkondades – alates sõjalistest asjadest ja turvasüsteemidest kuni kõikvõimalike analoogsignaalide digiteerimiseni.

Traditsiooniliselt kuuluvad mustrituvastuse ülesanded tehisintellekti ülesannete hulka.

Juhised mustrituvastuses

Eristada saab kahte peamist suunda:

• Elusolendite äratundmisvõimete uurimine, nende selgitamine ja modelleerimine;
• Rakenduslike rakenduste üksikprobleemide lahendamiseks mõeldud seadmete konstrueerimise teooria ja meetodite väljatöötamine.

Probleemi ametlik avaldus

Mustrituvastus on lähteandmete määramine teatud klassi, tuvastades olulisi tunnuseid, mis iseloomustavad neid andmeid ebaoluliste andmete kogumassist.

Tuvastamisprobleemide püstitamisel püütakse kasutada matemaatilist keelt, üritades erinevalt tehisnärvivõrkude teooriast, kus aluseks on tulemuse saamine eksperimendi teel, asendada eksperiment loogilise arutluskäigu ja matemaatilise tõestusega.

Mustrituvastusprobleemides käsitletakse kõige sagedamini ühevärvilisi pilte, mis võimaldab vaadelda pilti kui funktsiooni tasapinnal. Kui arvestada tasapinnal seatud punkti T, kus funktsioon x(x,y) väljendab oma omadusi pildi igas punktis - heledus, läbipaistvus, optiline tihedus, siis on selliseks funktsiooniks pildi formaalne salvestamine.

Kõikide võimalike funktsioonide komplekt x(x,y) pinnal T- on olemas kõigi piltide komplekti mudel X. Kontseptsiooni tutvustamine sarnasused piltide vahel saate esitada tuvastusülesande. Sellise väite konkreetne tüüp sõltub tugevalt järgmistest tunnustamise etappidest vastavalt ühele või teisele lähenemisviisile.

Mustri tuvastamise meetodid

Optiliseks mustrituvastuseks saab kasutada meetodit, mille abil otsitakse läbi objekti vaate erinevate nurkade, mõõtkavade, nihkete jms all. Tähtede puhul tuleb sorteerida fonti, fondi atribuute jne.

Teine lähenemisviis on leida objekti kontuurid ja uurida selle omadusi (ühenduvus, nurkade olemasolu jne).

Teine lähenemisviis on kunstlike närvivõrkude kasutamine. See meetod nõuab kas suurt hulka tuvastusülesande näiteid (õigete vastustega) või spetsiaalset närvivõrgu struktuuri, mis arvestab selle ülesande eripäraga.

Perceptron kui mustrituvastusmeetod

F. Rosenblatt, tutvustades ajumudeli kontseptsiooni, mille ülesandeks on näidata, kuidas mõnes füüsilises süsteemis, mille struktuur ja funktsionaalsed omadused on teada, võivad tekkida psühholoogilised nähtused – kirjeldas ta kõige lihtsamat. diskrimineerimise katsed. Need katsed on täielikult seotud mustrituvastusmeetoditega, kuid erinevad selle poolest, et lahendusalgoritm ei ole deterministlik.

Lihtsaim eksperiment, millest saab teatud süsteemi kohta psühholoogiliselt olulist teavet, taandub sellele, et mudelile esitatakse kaks erinevat stiimulit ja see peab neile erineval viisil reageerima. Sellise eksperimendi eesmärk võib olla uurida nende spontaanse diskrimineerimise võimalust süsteemi poolt, kui eksperimenteerija ei sekku, või vastupidi, uurida sunniviisilist diskrimineerimist, mille käigus katsetaja püüab süsteemi koolitada. viima läbi nõutud klassifikatsiooni.

Pertseptronitreeningu katses esitatakse tavaliselt teatud piltide jada, mis hõlmab iga eristatava klassi esindajaid. Mõne mälu muutmise reegli kohaselt tugevdatakse vastuse õiget valikut. Seejärel esitatakse pertseptronile kontrollstiimul ja määratakse õige vastuse saamise tõenäosus antud klassi stiimulitele. Sõltuvalt sellest, kas valitud kontrollstiimul ühtib või ei ühti ühe treeningjärjestuses kasutatud kujutisega, saadakse erinevad tulemused:

• 1. Kui kontrollstiimul ei ühti ühegi treeningstiimuliga, siis ei seostata eksperimenti ainult puhas diskrimineerimine, vaid sisaldab ka elemente üldistused.
• 2. Kui kontrollstiimul ergastab teatud hulga sensoorseid elemente, mis on täiesti erinevad nendest elementidest, mis aktiveerusid varem esitatud sama klassi stiimulite mõjul, siis on katse uurimus. puhas üldistus .

Pertseptronidel puudub puhta üldistusvõime, kuid nad toimivad diskrimineerimiskatsetes üsna rahuldavalt, eriti kui kontrollstiimul sobib piisavalt täpselt ühe kujutisega, millega pertseptronil on juba kogemusi.

Näiteid mustrituvastusprobleemidest

• Kirja äratundmine.
• Vöötkoodi tuvastamine.
• Numbrimärgituvastus.
• Näotuvastus.
• Kõnetuvastus.
• Pildituvastus.
• Maakoore kohalike alade äratundmine, kus asuvad maavaramaardlad.

Mustri tuvastamise programmid

Vaata ka

Märkmed

Lingid

• Juri Lifshits. Kursus “Teoreetilise arvutiteaduse kaasaegsed probleemid” - loengud mustrituvastuse statistilistest meetoditest, näotuvastusest, tekstide klassifitseerimisest
• Mustri tuvastamise uuringute ajakiri

Kirjandus

• David A. Forsythe, Jean Pons Arvutinägemine. Kaasaegne lähenemine = Computer Vision: A Modern Approach. - M.: "Williams", 2004. - Lk 928. - ISBN 0-13-085198-1
• George Stockman, Linda Shapiro Arvutinägemine = Computer Vision. - M.: Binom. Teadmiste labor, 2006. - Lk 752. - ISBN 5947743841

• A.L.Gorelik, V.A.Skripkin, Tuvastamismeetodid, M.: lõpetanud kool, 1989.
• Sh.-K. Cheng, Visuaalsete infosüsteemide kujundamise põhimõtted, M.: Mir, 1994.

Wikimedia sihtasutus. 2010. aasta.

Üks uutest piirkondadest küberneetika. R. o. teooria sisu. on mitmesse klassi kuuluvate objektide (kujutiste) omaduste ekstrapoleerimine neile mõnes mõttes lähedastele objektidele. Tavaliselt on automaadi R. o. saadaval...... Geoloogiline entsüklopeedia

Inglise äratundmine, kuvand; saksa keel Gestalt alterkennung. Matemaatilise küberneetika haru, mis töötab välja põhimõtted ja meetodid objektide klassifitseerimiseks ja identifitseerimiseks, mida kirjeldatakse piiratud hulga neid iseloomustavate tunnuste abil. Antinazi. Entsüklopeedia...... Sotsioloogia entsüklopeedia

Mustri äratundmine- meetod keerukate objektide uurimiseks arvuti abil; seisneb funktsioonide valimises ning algoritmide ja programmide väljatöötamises, mis võimaldavad arvutitel nende funktsioonide alusel objekte automaatselt klassifitseerida. Näiteks määrake, milline ... ... Majandus- ja matemaatikasõnastik

- (tehniline), teaduslik ja tehniline suund, mis on seotud meetodite väljatöötamise ja süsteemide (sealhulgas arvutipõhiste) väljatöötamisega, et tuvastada teatud objekti (objekti, protsessi, nähtuse, olukorra, signaali) kuuluvus ühte edusammudest. ... ... entsüklopeediline sõnaraamat

MUSTRI TUNNISTAMINE- matemaatilise küberneetika osa, mis arendab klassifitseerimismeetodeid, samuti objektide, nähtuste, protsesside, signaalide, kõigi nende objektide olukordade tuvastamist, mida saab kirjeldada teatud märkide või omaduste lõpliku hulgaga,... ... Vene sotsioloogiline entsüklopeedia

mustrituvastus- 160 mustrituvastus: esitusvormide ja konfiguratsioonide tuvastamine automaatsete vahenditega

Kaasaegsed nägemissüsteemidega varustatud robotid näevad hästi, et töötada reaalse maailmaga. Nad saavad teha järeldusi selle kohta, mis tüüpi objektid on olemas, millised suhted neil omavahel on ja milliseid rühmi nad moodustavad.

Tuvastamisülesande olemus seisneb selles, et teha kindlaks, kas uuritavatel objektidel on kindel lõplik tunnuste kogum, mis võimaldab neid teatud klassi liigitada.

Mustrituvastuse teaduse eesmärgid:

Inimeksperdi või kompleksse ekspertsüsteemi asendamine lihtsama süsteemiga (inimtegevuse automatiseerimine või keeruliste süsteemide lihtsustamine);

Õppesüsteemide konstrueerimine, mis suudavad teha otsuseid ilma selgeid reegleid määramata, nimelt süsteemid, mis suudavad ise sünteesida otsustusreegleid, tuginedes teatud lõplikule arvule süsteemile “demonstreeritud” õigete otsuste näidetele.

Tunnustamise ülesanded saab iseloomustada järgmiselt.

1. Need on teabeülesanded, mis koosnevad kahest põhietapist: lähteandmete taandamine äratundmiseks mugavasse vormi ja äratundmine ise.

2. Nendes ülesannetes saate tutvustada objektide analoogia ja sarnasuse mõistet ning sõnastada objektide läheduse mõiste, mis on aluseks objekti kaasamisel teatud klassi.

3. Nendes ülesannetes saab opereerida näidete komplektiga, mille klassifikatsioon on teada ja mida saab formaliseeritud kirjelduste kujul esitada tuvastusalgoritmile, et õppeprotsessi käigus ülesandega kohaneda.

4. Nende ülesannete jaoks on keeruline koostada formaalseid teooriaid ja rakendada klassikalisi matemaatilisi meetodeid.

5. Nende probleemide puhul on võimalik "halb" teave.

Tuvastamisülesannete tüübid:

Esitletava objekti määramine ühte klassi (koolitus koos õpetajaga);

Automaatne klassifitseerimine – objektide (olukordade) komplekti jagamine vastavalt nende kirjeldusele mittekattuvate klasside süsteemiks;

Infotunnuste komplekti valimine lagunemise ajal;

Lähteandmete toomine äratundmiseks mugavale vormile;

Dünaamiline tuvastamine ja dünaamiline klassifikatsioon;

Prognoosimisprobleemid.

Põhimääratlused

Pilt– see on objekti või nähtuse struktureeritud kirjeldus, mida kujutab tunnuste vektor, mille iga element tähistab ühe seda objekti iseloomustava tunnuse arvväärtust. Teisisõnu: kujutis on mis tahes objekt, mille puhul saab mõõta teatud arvuliste karakteristikute kogumit. Pildi näide: kiri, pilt, kardiogramm jne.

Numbrimärk(või lihtsalt märk). on kindla numbrilise tunnusega objekti sobitamise meetodi valem või muu kirjeldus, mis toimib konkreetse mustrituvastusülesande raames. Iga objekti jaoks saab defineerida mitu erinevat karakteristikku, see tähendab mitu numbrilist tunnust.

Funktsiooniruum.N-mõõtmeline ruum, mis on määratletud antud tuvastamisülesande jaoks, kus N on mis tahes objektide mõõdetud tunnuste fikseeritud arv. Tuvastamisülesande objektile vastav tunnusruumi vektor on N-mõõtmeline vektor komponentidega (x1, x2, ..., xN), mis on selle objekti tunnuste väärtused.

OBJEKT->Ntunnused->M-mõõtmeline tunnusvektor

Klass- vormistamata (reeglina) idee võimalusest määrata tuvastusülesande objektide hulgast suvaline objekt teatud objektide rühmale. Sama klassi objektide puhul eeldatakse “sarnasuse” olemasolu. Mustrituvastuse ülesande jaoks saab määratleda suvalise arvu klasse, mis on suuremad kui 1. Klasside arv on tähistatud numbriga S.

Üldiselt koosneb mustrituvastuse probleem kahest osast: äratundmisest ja koolitusest.

Mustrituvastus seisneb teatud objektide rühma klassifitseerimises teatud nõuete alusel. Samasse kujutiste klassi kuuluvatel objektidel on ühised omadused. Klassifikatsiooni määratlevad nõuded võivad erineda, kuna erinevad olukorrad nõuavad erinevat tüüpi klassifikatsioone.

Näiteks ingliskeelsete tähtede äratundmisel moodustub 26 pildiklassi. Ingliskeelsete tähtede eristamiseks hiina tähtedest tuvastamise ajal on aga vaja ainult kahte tüüpi kujutisi.

Lihtsaim viis mustrite tuvastamiseks on mustrite sobitamine. Sel juhul salvestatakse masina mällu teatud komplekt pilte, üks igast pildiklassist. Sisend (tuvastatud) pilti (tundmatu klassi kohta) võrreldakse iga klassi standardiga. Klassifikatsioon põhineb eelnevalt valitud sobituskriteeriumil või sarnasuse kriteeriumil. Teisisõnu, kui sisendpilt vastab i-nda mustriklassi standardile paremini kui mis tahes muu standard, siis klassifitseeritakse sisendpilt i-nda mustriklassi kuuluvaks.

Selle lähenemisviisi, s.o standardiga võrdlemise, puuduseks on see, et mõnel juhul on raske igast pildiklassist sobivat standardit valida ja vajalikku sobituskriteeriumi paika panna.

Täiustatud lähenemisviis on see, et klassifitseerimine põhineb teatud sisendkujutistel tehtud valitud mõõtmiste komplektil. Eeldatakse, et need valitud meetmed, mida nimetatakse "funktsioonideks", on muutumatud või mittetundlikud sageli esinevate variatsioonide ja moonutuste suhtes ning neil on vähe üleliigsust.

"Omaduse mõõtmise" teise lähenemisviisi erijuhtum, kus standardid salvestatakse mõõdetud tunnuste kujul ja klassifikaatoris kasutatakse spetsiaalset klassifitseerimiskriteeriumi (võrdlus).

Funktsioonid on määratlenud arendajad ja need peavad olema muutumatud objektide orientatsiooni, suuruse ja kuju variatsioonide suhtes.

Motivatsioon

Loogiline lähenemine

Nimetused

Tõenäosuslik lähenemine

Seda väljendit võib tõlgendada eeldusena, tagajärjena, kuid üleminek eelduselt tagajärjele järgib tõenäosusseadusi, mitte loogilisi. Need. Klassi Boole'i ​​väärtustega 0 ja 1 tõeväärtustabeli asemel on tõenäosusväärtused vahemikus 0 kuni 1. Rakendage Bayesi valem ja hankige järgmine avaldis:

Vaatame selle väljendi paremat külge üksikasjalikumalt. Kordajat nimetatakse eeltõenäosuseks ja see tähendab tõenäosust leida kõigi võimalike õunte hulgast maitsev õun. On a priori tõenäosus kohata maitsetut õuna. See tõenäosus võib peegeldada meie isiklikke teadmisi selle kohta, kuidas maitsvad ja ebameeldivad õunad looduses levivad. Näiteks teame oma varasemast kogemusest, et 80% kõikidest õuntest on maitsvad. Või saame seda väärtust hinnata lihtsalt maitsvate õunte osakaalu arvutamisel meie loendis ajalooliste andmetega S. Järgmine tegur näitab, kui tõenäoline on saada 1. klassi õuna jaoks konkreetne värvus ja suurus. Seda väljendit nimetatakse ka tõenäosusfunktsiooni ja see võib välja näha selline: mingi konkreetne jaotus, näiteks normaalne. Me kasutame nimetajat normaliseeriva konstannana, nii et soovitud tõenäosus varieerub vahemikus 0 kuni 1. Meie lõppeesmärk ei ole otsida tõenäosusi, vaid otsida otsustavat reeglit, mis annaks meile kohe klassi. Otsustusreegli lõplik vorm sõltub sellest, millised väärtused ja parameetrid on meile teada. Näiteks saame teada ainult eelneva tõenäosuse väärtusi ja ülejäänud väärtusi ei saa hinnata. Siis on otsustavaks reegliks see – määrake kõikidele õuntele selle klassi väärtus, mille a priori tõenäosus on suurim. Need. kui teame, et 80% õuntest looduses on maitsvad, siis anname igale õunale klassi 1. Siis on meie viga 20%. Kui saame hinnata ka tõenäosusfunktsiooni $p(X=x_m | Y=1)$ väärtusi, siis leiame soovitud tõenäosuse väärtuse Bayesi valemi abil, nagu ülalpool kirjutatud. Otsustav reegel on siin: pane silt klassile, mille tõenäosus on maksimaalne:

Nimetagem seda reeglit Bayesi klassifikaatoriks. Kuna tegemist on tõenäosustega, siis isegi suur tõenäosusväärtus ei garanteeri, et õun ei kuulu klassi 0. Hinnakem õuna vea tõenäosust järgmiselt: kui otsustusreegel tagastas klassi väärtuse, mis on võrdne 1-ga. , siis on vea tõenäosus ja vastupidi:

Meid huvitab klassifikaatori vea tõenäosus mitte ainult selles konkreetses näites, vaid üldiselt kõigi võimalike õunte puhul:

See avaldis on vea eeldatav väärtus. Niisiis, algse probleemi lahendamisel jõudsime Bayesi klassifikaatorini, kuid millised on selle puudused? Peamine probleem on tingliku tõenäosuse hindamine andmete põhjal. Meie puhul kujutame objekti numbripaariga - värvus ja suurus, kuid keerukamate ülesannete korral võib tunnuste mõõde olla kordades suurem ja meie loendi vaatluste arv koos ajalooliste andmetega ei pruugi olla piisav, et hinnata mitmemõõtmelise juhusliku suuruse tõenäosus. Järgmisena proovime üldistada oma klassifikaatori vea kontseptsiooni ja vaadata, kas probleemi lahendamiseks on võimalik valida mõni muu klassifikaator.

Klassifikaatori veakaod

Tingimuslik ja Bayesi risk

Meie binaarse klassifikatsiooni puhul, kui selgub:

Ülalpool kirjeldasime otsustusreeglit, mis määrab objekti kõrgeima tõenäosusväärtusega klassile, mis annab meie keskmiste kahjude miinimumi (Bayesi risk), mistõttu on Bayesi klassifikaator riskifunktsionaalselt optimaalne. tutvustasime. See tähendab, et Bayesi klassifikaatoril on väikseim võimalik klassifitseerimisviga.

Mõned tüüpilised kadufunktsioonid

Siis on tingimuslik risk a(x) = 1 korral lihtsalt objekti klassi 0 saamise tõenäosuse väärtus:

Samamoodi, kui a(x) = 0:

Kaofunktsioon 1-0 võtab väärtuse 1, kui klassifikaator teeb objektil vea, ja 0, kui ta seda ei tee. Nüüd veendume, et vea väärtus pole võrdne 1-ga, vaid mõne teise funktsiooniga Q, olenevalt otsustusreeglist ja reaalklassi sildist:

Siis saab tingimusliku riski kirjutada järgmiselt:

Märkused noodikirja kohta

Kus on funktsioon, millega me proovime tundmatut sõltuvust lähendada, on reaalväärtuse ja meie funktsiooni väärtuse kadufunktsioon. See märge on selgem, et tutvustada järgmist mõistet – empiiriline risk.

Empiiriline risk

Näide: olgu vormi kõigi funktsioonide hulk

Kõik selle hulga funktsioonid erinevad üksteisest ainult koefitsientide poolest. Sellise perekonna valimisel eeldasime, et klassi 1 punktide ja klassi 0 punktide vahelises värvisuuruses koordinaatides saame tõmmata koefitsientidega sirge sellises nii, et erinevate klassidega punktid paiknevad piki sirge eri külgesid. On teada, et seda tüüpi joone puhul on koefitsiendi vektor joone suhtes normaalne. Nüüd teeme nii – võtame oma õuna, mõõdame selle värvi ja suuruse ning kanname saadud koordinaatidega punkti graafikule värvisuuruse telgedele. Järgmisena mõõdame selle punkti ja vektori $w$ vahelist nurka. Märkame, et meie punkt võib asuda kas ühel või teisel pool sirget. Siis on punkti ja vaheline nurk terav või nüri ja skalaarkorrutis kas positiivne või negatiivne. See viib otsustava reeglini:

Pärast seda, kui oleme funktsioonide klassi $H$ fikseerinud, tekib küsimus - kuidas sealt valida vajalike koefitsientidega funktsioon? Vastus on – valime funktsiooni, mis minimeerib meie Bayesi riski $R()$. Jällegi on probleem selles, et Bayesi riskiväärtuste arvutamiseks on vaja teada jaotust $p(x,y)$, kuid seda meile ei anta ja seda pole alati võimalik taastada. Teine idee on minimeerida riski mitte kõigil võimalikel objektidel, vaid ainult näidisel. Need. minimeerimisfunktsioon:

Seda funktsiooni nimetatakse empiiriliseks riskiks. Järgmine küsimus on, miks me otsustasime, et minimeerides empiirilist riski, minimeerime ka Bayesi riski? Tuletan meelde, et meie praktiline ülesanne on teha võimalikult vähe klassifitseerimisvigu. Mida vähem vigu, seda väiksem on Bayesi risk. Õiguse empiirilise riski konvergentsile Bayesi riskile andmemahu suurenemisega leidsid 70ndatel kaks teadlast - V. N. Vapnik ja A. Ya. Chervonenkis.

Lähenemistagatised. Lihtsaim juhtum

Teoreem

Mida tähendavad “väike väärtus” ja “piisav suurus”, vaata allolevast kirjandusest.

Tõestuse idee

Praktilised tulemused

Ja sõltuvalt lahendatavast probleemist asendame erinevad kadufunktsioonid. Lineaarse regressiooni jaoks:

Logistilise regressiooni jaoks:

Kuigi tugivektori masinatel on peamiselt geomeetriline motivatsioon, võib neid pidada ka empiiriliseks riskide minimeerimise probleemiks.

Järeldus

Kasutatud Raamatud

• Statistilise õppimisteooria olemus, Vladimir N. Vapnik
• Mustri klassifikatsioon, 2. väljaanne, Richard O. Duda, Peter E. Hart, David G. Stork
• Masinõppe mõistmine: teooriast algoritmideni, Shai Shalev-Shwartz, Shai Ben-David

Sildid: lisa sildid

Loeng nr 17.MUSTRI TUNNISTAMISE MEETODID

Eristatakse järgmisi tunnustamismeetodite rühmi:

Lähedusfunktsiooni meetodid

Diskrimineeriva funktsiooni meetodid

Statistilised tuvastamismeetodid.

Keelelised meetodid

Heuristilised meetodid.

Esimesed kolm meetodite rühma on keskendunud numbriliste komponentidega arvude või vektoritena väljendatud tunnuste analüüsile.

Rühm keelelisi meetodeid pakub mustrite äratundmist, mis põhineb nende struktuuri analüüsil, mida kirjeldavad vastavad struktuuritunnused ja nendevahelised seosed.

Heuristiliste meetodite rühm ühendab iseloomulikud tehnikad ja loogilised protseduurid, mida inimesed kasutavad mustrite tuvastamisel.

Lähedusfunktsiooni meetodid

Selle rühma meetodid põhinevad funktsioonide kasutamisel, mis hindavad tuvastatud kujutise ja vektori lähedust x* = (x* 1 ,….,x*n) ja erinevate klasside võrdluspildid, mis on esitatud vektoritega x i = (x i 1 ,…, x i n), i= 1,…,N, Kus mina – pildi klassi number.

Tunnustamise kord vastavalt seda meetodit seisneb tuvastatud kujutise punkti ja iga võrdluspilti esindava punkti vahelise kauguse arvutamises, s.o. kõigi väärtuste arvutamisel d i , i= 1,…,N. Pilt kuulub klassi, mille väärtus d i Sellel on väikseim väärtus kõigi seas i= 1,…,N .

Funktsioon, mis määrab iga vektoripaari x i, x* reaalarv kui nende läheduse mõõt, st. nendevahelise kauguse määramine võib olla üsna meelevaldne. Matemaatikas nimetatakse sellist funktsiooni ruumi meetrikaks. See peab vastama järgmistele aksioomidele:

r(x,y)=r(y,x);

r(x,y) > 0, kui x pole võrdne y Ja r(x,y)=0 kui x=y;

r(x,y) <=r(x,z)+r(z,y)

Loetletud aksioomid on täidetud eelkõige järgmiste funktsioonidega

a i= 1/2 , j=1,2,…n.

b i=summa, j=1,2,…n.

c i= max abs ( x i‑ x j *), j=1,2,…n.

Esimest neist nimetatakse vektorruumi eukleidiliseks normiks. Sellest lähtuvalt nimetatakse ruume, milles määratud funktsiooni kasutatakse mõõdikuna, eukleidiliseks ruumiks.

Sageli valitakse lähedusfunktsiooniks tuvastatud kujutise koordinaatide ruutkeskmine erinevus x* ja standardne x i, st. funktsiooni

d i = (1/n) summa( x i j‑ x j *) 2 , j=1,2,…n.

Suurusjärk d i geomeetriliselt tõlgendatud tunnusruumi punktide vahelise kauguse ruuduna, mis on seotud ruumi mõõtmega.

Sageli selgub, et erinevad tunnused pole äratundmisel võrdselt olulised. Et seda asjaolu lähedusfunktsioonide arvutamisel arvesse võtta, korrutatakse olulisematele tunnustele vastavad koordinaatide erinevused suurte koefitsientidega, vähemolulistele - väiksematega.

Sel juhul d i = (1/n) summa w j (x i j‑ x j *) 2 , j=1,2,…n,

Kus w j– kaalukoefitsiendid.

Kaalukoefitsientide kasutuselevõtt on samaväärne tunnusruumi telgede skaleerimisega ja vastavalt ruumi venitamisel või kokkusurumisel teatud suundades.

Näidatud tunnusruumi deformatsioonid taotlevad eesmärki paigutada võrdluspiltide punktid nii, et see vastaks kõige usaldusväärsemale äratundmisele iga klassi kujutiste olulise hajumise tingimustes võrdluskujutise punkti läheduses. .

Funktsiooniruumis üksteisele lähedal asuvate pildipunktide rühmi (piltide klastreid) nimetatakse klastriteks ja selliste rühmade tuvastamise ülesannet klastriprobleemiks.

Klastrite tuvastamise ülesanne liigitatakse järelevalveta mustrituvastusülesandeks, s.t. äratundmisprobleemidele õige äratundmise näite puudumisel.

Diskrimineeriva funktsiooni meetodid

Selle rühma meetodite idee on konstrueerida funktsioone, mis määravad kujutiste ruumis piirid, mis jagavad ruumi kujutiste klassidele vastavateks aladeks. Seda tüüpi lihtsaimad ja sagedamini kasutatavad funktsioonid on funktsioonid, mis sõltuvad lineaarselt funktsioonide väärtustest. Tunnusruumis vastavad need poolituspindadele hüpertasandite kujul. Kahemõõtmelise tunnusruumi puhul toimib sirgjoon eraldava funktsioonina.

Lineaarse otsustusfunktsiooni üldkuju annab valemiga

d(x)=w 1 x 1 + w 2 x 2 +…+w n x n +w n +1 = Wx+w n

Kus x- pildivektor, w=(w 1 ,w 2 ,…w n) – kaalukoefitsientide vektor.

Kaheks klassiks jagunemise korral X 1 ja X 2 diskrimineeriv funktsioon d x) võimaldab tunnustamist vastavalt reeglile:

x kuulub X 1 kui d(x)>0;

x kuulub X 2 kui d(x)<0.

Kui d(x)=0, siis on tegemist määramatusega.

Mitmeks klassiks jagamise korral tutvustatakse mitmeid funktsioone. Sel juhul on igale kujutiste klassile määratud teatud kombinatsioon eristavate funktsioonide märkidest.

Näiteks kui tuuakse sisse kolm diskrimineerivat funktsiooni, on pildiklasside tuvastamiseks võimalik järgmine valik:

x kuulub X 1 kui d 1 (x)>0,d 2 (x)<0,d 3 (x)<0;

x kuulub X 2 kui d(x)<0,d 2 (x)>0,d 3 (x)<0;

x kuulub X 3 kui d(x)<0,d 2 (x)<0,d 3 (x)>0.

Eeldatakse, et teiste väärtuste kombinatsioonide puhul d 1 (x),d 2 (x),d 3 (x) on ebakindlus.

Diskrimineeriva funktsiooni meetodi variatsioon on otsustusfunktsiooni meetod. Selles, kui see on saadaval m klasside olemasolu eeldatakse m funktsioonid d i(x), nimetatakse määravaks, nii et kui x kuulub X i, See d i(x) > dj(x) kõigi jaoks j ebavõrdne i, need. otsustav funktsioon d i(x) on kõigi funktsioonide hulgas suurim väärtus dj(x), j=1,...,n..

Selle meetodi näide võib olla klassifikaator, mis põhineb minimaalse eukleidilise kauguse hindamisel kujutise punkti ja standardi vahelises tunnusruumis. Näitame seda.

Eukleidiline kaugus tuvastatud kujutise tunnusvektori vahel x ja võrdluskujutise vektor määratakse valemiga || x i ‑ x|| = 1/2 , j=1,2,…n.

Vektor x määratakse klassi i, mille väärtus || x i ‑ x*|| minimaalne.

Kauguse asemel saab võrrelda kauguse ruutu, s.t.

||x i ‑ x|| 2 = (x i ‑ x)(x i ‑ x) t = x x- 2x x i +x i x i

Alates väärtusest x x kõigile sama i, minimaalne funktsioon || x i ‑ x|| 2 langeb kokku otsustusfunktsiooni maksimumiga

d i(x) = 2x x i -x i x i.

see on x kuulub X i, Kui d i(x) > dj(x) kõigi jaoks j ebavõrdne i.

See. minimaalse vahemaa klassifitseerimise masin põhineb lineaarsetel otsustusfunktsioonidel. Sellise masina üldine struktuur kasutab vormi määravaid funktsioone

d i (x)=w i 1 x 1 + w i 2 x 2 +…+w x n-s +w i n +1

Seda saab visuaalselt kujutada vastava plokkskeemiga.

Masina puhul, mis klassifitseerib minimaalse vahemaa alusel, kehtivad järgmised võrdsused: w ij = -2x i j , w i n +1 = x i x i.

Diskrimineeriva funktsiooni meetodiga samaväärse äratundmise saab läbi viia, defineerides diskrimineerivad funktsioonid erinevustena d ij (x)=d i (x)‑dj (x).

Diskriminantfunktsiooni meetodi eeliseks on tuvastusmasina lihtne struktuur, samuti selle realiseerimise võimalus peamiselt läbi valdavalt lineaarsete otsustusplokkide.

Diskrimineeriva funktsiooni meetodi teine ​​oluline eelis on võimalus õpetada masinat automaatselt õigeks tuvastamiseks etteantud (koolitus) kujutiste näidise põhjal.

Samas osutub automaatne õppealgoritm võrreldes teiste tuvastusmeetoditega väga lihtsaks.

Nendel põhjustel on diskrimineeriva funktsiooni meetod saavutanud laialdase populaarsuse ja seda kasutatakse praktikas väga sageli.

Enesetreeningud mustrite tuvastamiseks

Vaatleme meetodeid diskrimineeriva funktsiooni konstrueerimiseks antud (koolitus) valimi jaoks seoses kujutiste kahte klassi jagamise probleemiga. Kui on antud kaks kujutiste komplekti, mis kuuluvad vastavalt klassidesse A ja B, siis otsitakse lineaarse diskrimineeriva funktsiooni konstrueerimise probleemile lahendust kaalukoefitsientide vektori kujul. W=(w 1 ,w 2 ,...,w n,w n+1), millel on omadus, et mis tahes kujutise jaoks on täidetud järgmised tingimused:

x kuulub A-klassi, kui >0, j=1,2,…n.

x kuulub B-klassi, kui<0, j=1,2,…n.

Kui treeningkomplekt koosneb N mõlema klassi kujutised, taandub ülesanne vektori w leidmiseks, mis tagab võrratuste süsteemi kehtivuse Kui treeningvalim koosneb N mõlema klassi pildid, taandub ülesanne vektori leidmisele w, tagades ebavõrdsuse süsteemi kehtivuse

x 1 1 w i+x 21 w 2 +...+x n 1 w n+w n +1 >0;

x 1 2 w i+x 22 w 2 +...+x n 2 w n+w n +1 <0;

x 1 iw i+x 2i w 2 +...+x ni w n+w n +1 >0;

................................................

x 1 Nw i +x 2N w 2 +...+x nN w n +w n + 1>0;

Siin x i=(x i 1 ,x i 2 ,...,x i n ,x i n+ 1 ) - pildifunktsiooni väärtuste vektor treeningproovist, märk > vastab pildivektoritele x, klassi kuuluv A, märk< - векторам x, mis kuulub B-klassi.

Nõutav vektor w eksisteerib, kui klassid A ja B on eraldatavad ja seda muidu ei eksisteeri. Vektorkomponentide väärtused w võib leida kas eelnevalt, SRO riistvaralisele juurutamisele eelnevas etapis või otse SRO enda poolt selle töötamise ajal. Viimane neist lähenemisviisidest tagab SRO suurema paindlikkuse ja autonoomia. Vaatleme seda protsentironi nimelise seadme näitel. leiutas 1957. aastal Ameerika teadlane Rosenblatt. Protsentroni skemaatiline esitus, mis tagab kujutise määramise ühte kahest klassist, on esitatud järgmisel joonisel.

Võrkkesta S Võrkkesta A Võrkkesta R

oh oh x 1

oh oh x 2

oh oh x 3

o (summa)-------> R(reaktsioon)

oh oh x i

oh oh x n

oh oh x n +1

Seade koosneb võrkkesta sensoorsetest elementidest S, mis on juhuslikult ühendatud võrkkesta assotsiatiivsete elementidega A. Teise võrkkesta iga element toodab väljundsignaali ainult siis, kui piisav arv selle sisendiga ühendatud sensoorseid elemente on ergastatud olekus. Kogu süsteemi reaktsioon R on võrdeline teatud kaaludega võetud assotsiatiivse võrkkesta elementide reaktsioonide summaga.

Määratud x i reaktsioon i th assotsiatiivne element ja läbi w i- reaktsiooni kaalukoefitsient i assotsiatiivse elemendina saab süsteemi reaktsiooni kirjutada järgmiselt R=summa( w j x j), j=1,..,n. Kui R>0, siis süsteemile esitatav pilt kuulub A-klassi ja kui R<0, то образ относится к классу B. Описание этой процедуры классификации соответствует рассмотренным нами раньше принципам классификации, и, очевидно, перцентронная модель распознавания образов представляет собой, за исключением сенсорной сетчатки, реализацию линейной дискриминантной функции. Принятый в перцентроне принцип формирования значений x 1 , x 2 ,...,x n vastab mõnele algoritmile primaarsete andurite signaalide põhjal funktsioonide genereerimiseks.

Üldiselt võib elemente olla mitu R, moodustades pertseptroni reaktsiooni. Sel juhul räägivad nad võrkkesta olemasolust pertseptronis R reageerivad elemendid.

Protsentroni skeemi saab laiendada juhul, kui klasside arv on üle kahe, suurendades võrkkesta elementide arvu R kuni eristatavate klasside arvuni ja maksimaalse reaktsiooni määramise ploki kasutuselevõtt vastavalt ülaltoodud joonisel toodud diagrammile. Sel juhul määratakse pilt numbriga klassile i, Kui R i>R j, kõigi jaoks j.

Protsentroni treeningprotsess koosneb kaalukoefitsientide väärtuste valimisest w j et väljundsignaal vastaks klassile, millesse tuvastatud kujutis kuulub.

Vaatleme protsentironi tegevusalgoritmi kahe klassi A ja B objektide äratundmise näitel. Klassi A objektidel peab olema vastav väärtus R= +1 ja klass B - väärtus R= -1.

Õppimisalgoritm on järgmine.

Kui järgmine pilt x kuulub A-klassi, kuid R<0 (имеет место ошибка распознавания), тогда коэффициенты w j indeksitega, millele väärtused vastavad x j>0, suurendage mõne summa võrra dw ja ülejäänud koefitsiendid w j võrra vähendatud dw. Sel juhul reaktsiooni väärtus R saab selle suunas juurdekasvu positiivsed väärtused, mis vastab õigele klassifikatsioonile.

Kui x kuulub B-klassi, kuid R>0 (tekib äratundmisviga), siis koefitsiendid w j indeksitega, mis vastavad x j<0, увеличивают на dw ja ülejäänud koefitsiendid w j sama summa võrra vähendatud. Sel juhul reaktsiooni väärtus R saab juurdekasvu negatiivsete väärtuste suunas, mis vastavad õigele klassifikatsioonile.

Algoritm muudab seega kaalude vektorit w siis ja ainult siis, kui pilt esitatakse k-th treeningsamm, klassifitseeriti selle sammu sooritamisel valesti ja jätab raskuste vektori w ei muutu, kui klassifitseeritakse õigesti. Selle algoritmi konvergentsi tõestus on esitatud artiklis [Tu, Gonzalez]. Selline koolitus lõpuks (õige valiku korral dw ja pildiklasside lineaarne eraldatavus) viib vektorini w, tagades õige klassifikatsiooni.

Statistilised tuvastamismeetodid.

Statistilised meetodid põhinevad klassifitseerimisvea tõenäosuse minimeerimisel. Tunnustamiseks esitatud kujutise vale klassifikatsiooni tõenäosus P, mida kirjeldatakse tunnusvektoriga x, määratakse valemiga

P = summa[ lk(i)probleem( D(x)+i | x klass i)]

Kus m- klasside arv,

lk(i) = sond ( x kuulub klassi i) - a priori tõenäosus kuuluda meelevaldsele kujutisele x To i klass (piltide ilmumise sagedus i- klass),

D(x) - funktsioon, mis teeb klassifitseerimisotsuse (tunnuste vektor x sobib klassi numbriga i komplektist (1,2,..., m}),

prob( D(x) pole võrdne i| x kuulub klassi i) - sündmuse tõenäosus" D(x) pole võrdne i"Kui liikmelisuse tingimus on täidetud x klass i, st. tõenäosus, et funktsioon teeb eksliku otsuse D(x) antud väärtuse jaoks x, omandis i- klass.

Võib näidata, et valesti klassifitseerimise tõenäosus jõuab miinimumini, kui D(x)=i kui ja ainult kui lk(x|i)· lk(i)>lk(x|j)· lk(j), kõigi jaoks i+j, Kus lk(x|i) - kujutise jaotustihedus i-klass funktsiooniruumis.

Eeltoodud reegli kohaselt punkt x kuulub klassi, millele vastab maksimaalne väärtus lk(i) lk(x|i), st. piltide ilmumise eelneva tõenäosuse (sageduse) korrutis i-klassi ja kujutise leviku tihedus i-klass funktsiooniruumis. Esitatud klassifikatsioonireeglit nimetatakse Bayesi, kuna see tuleneb tõenäosusteoorias tuntud Bayesi valemist.

Näide. Olgu vaja ära tunda diskreetsed signaalid mürale alluva infokanali väljundis.

Iga sisendsignaal tähistab 0 või 1. Signaali edastamise tulemusena kuvatakse väärtus kanali väljundis x, mis kattub Gaussi müraga nullkeskmise ja dispersiooniga b.

Signaalituvastust teostava klassifikaatori sünteesimiseks kasutame Bayesi klassifikatsioonireeglit.

Kombineerime ühtesid tähistavad signaalid klassi nr 1 ja nulli tähistavad signaalid klassi nr 2. Etteruttavalt olgu öeldud, et keskmiselt igast 1000 signaalist a signaalid tähistavad ühikuid ja b signaalid - null. Siis võib 1. ja 2. klassi signaalide (vastavalt ühed ja nullid) ilmumise a priori tõenäosuste väärtused võtta võrdseks

p(1)=a/1000, p(2)=b/1000.

Sest müra on Gaussilik, st. järgib normaaljaotuse (Gaussi) seadust, siis esimese klassi kujutiste jaotustihedus sõltuvalt väärtusest x, või, mis on sama, väljundväärtuse saamise tõenäosus x kui sisendis rakendatakse signaali 1, määratakse see avaldisega

lk(x¦1) =(2pib) -1/2 exp(-( x-1) 2 / (2b 2)),

ja jaotustihedus sõltuvalt väärtusest x teise klassi kujutised, s.o. väljundväärtuse saamise tõenäosus x kui sisendisse rakendatakse signaal 0, määratakse see avaldisega

lk(x¦2)= (2pib) -1/2 eksp(- x 2 /(2b 2)),

Bayesi otsustusreegli rakendamine viib järeldusele, et edastatud on 2. klassi signaal, s.o. null on läbitud, kui

lk(2) lk(x¦2) > lk(1) lk(x¦1)

või täpsemalt, kui

b exp (- x 2 /(2b 2)) > a exp (-( x-1) 2 / (2b 2)),

Jagades ebavõrdsuse vasaku külje paremaga, saame

(b/a) exp((1-2 x)/(2b 2)) >1,

kus pärast logaritmide võtmist leiame

1-2x> 2b 2 ln(a/b)

x< 0.5 - б 2 ln(a/b)

Saadud ebavõrdsusest järeldub, et millal a=b, st. kui signaalide 0 ja 1 esinemise a priori tõenäosused on võrdsed, omistatakse pildile väärtus 0, kui x<0.5, а значение 1, когда x>0.5.

Kui on ette teada, et üks signaalidest ilmub sagedamini ja teine ​​harvem, s.o. ebavõrdsete väärtuste korral a Ja b, nihkub klassifikaatori reageerimislävi ühes või teises suunas.

Nii et millal a/b=2,71 (mis vastab 2,71 korda sagedasemale ühikute edastamisele) ja b 2 =0,1, omistatakse pildile väärtus 0, kui x<0.4, и значение 1, если x>0.4. Kui eelnevate jaotuse tõenäosuste kohta informatsioon puudub, võib kasutada statistilisi tuvastamismeetodeid, mis põhinevad muudel kui Bayesi klassifitseerimisreeglitel.

Praktikas on aga enim levinud Bayesi reeglitel põhinevad meetodid nende suurema efektiivsuse tõttu, aga ka tänu sellele, et enamiku mustrituvastusprobleemide puhul on võimalik määrata iga klassi kujutiste ilmumise a priori tõenäosused.

Mustri tuvastamise keelelised meetodid.

Mustrituvastuse keelelised meetodid põhinevad idealiseeritud kujutise kirjelduse analüüsil, mis esitatakse graafiku või tähemärkide ahela kujul, mis on teatud keele fraas või lause.

Mõelge ülalkirjeldatud keelelise äratundmise esimese etapi tulemusena saadud tähtede idealiseeritud kujutistele. Neid idealiseeritud pilte saab täpsustada graafikute kirjeldustega, mis on esitatud näiteks ühendusmaatriksitena, nagu tehti ülalpool käsitletud näites. Sama kirjeldust saab esitada formaalse keele fraasiga (väljendiga).

Näide. Olgu antud kolm A-tähe kujutist, mis on saadud pildi eeltöötluse tulemusena. Tähistame neid pilte identifikaatoritega A1, A2 ja A3.

Esitatud piltide keeleliseks kirjeldamiseks kasutame PDL-i (Picture Description Language). PDL-i sõnavara sisaldab järgmisi sümboleid:

1. Lihtsamate kujundite (primitiivide) nimetused. Vaadeldaval juhul on primitiivid ja neile vastavad nimed järgmised.

Pildid suunatud joone kujul:

üles ja vasakule (le F t), põhja (põhja), üles ja paremale (paremale), ida).

Nimed: L, N, R, E.

2. Kahendtehte sümbolid. (+,*,-) Nende tähendus vastab primitiivide järjestikusele seosele (+), primitiivi alguste ja lõppude seosele (*), ainult primitiivide lõppude seosele (-).

3. Parem- ja vasakpoolsed sulud. ((,)) Sulud võimaldavad määrata avaldises olevate toimingute jada.

Vaadeldavaid pilte A1, A2 ja A3 kirjeldatakse vastavalt PDL-keeles järgmiste avaldistega.

T(1)=R+((R-(L+N))*E-L

T(2)=(R+N)+((N+R)-L)*E-L

T(3)=(N+R)+(R-L)*E-(L+N)

Pärast kujutise keelelise kirjelduse konstrueerimist on vaja mõnda äratundmisprotseduuri kasutades analüüsida, kas see kujutis kuulub meile huvipakkuvasse klassi (tähtede klass A), s.o. Olenemata sellest, kas sellel pildil on mingi struktuur või mitte. Selleks on kõigepealt vaja kirjeldada piltide klassi, millel on meid huvitava struktuur.

Ilmselt sisaldab täht A alati järgmisi konstruktsioonielemente: vasak jalg, parem jalg ja pea. Nimetagem neid elemente vastavalt STL, STR, TR.

Siis kirjeldatakse PDL-keeles avaldisega märgiklassi A - SIMB A

SIMB A = STL + TR - STR

STL-i vasak "jalg" on alati elementide R ja N ahel, mille saab kirjutada nii

STL -> R ¦ N ¦ (STL + R)¦ (STL + N)

(STL on märk R või N või string, mis saadakse märkide R või N lisamisel lähte STL stringile)

STR-i parem “jalg” on alati elementide L ja N ahel, mida saab kirjutada nii, st.

STR -> L¦N¦ (STR + L)¦ (STR + N)

Tähe peaosa – TR on suletud kontuur, mis koosneb elemendist E ja ahelatest nagu STL ja STR.

PDL-is kirjeldatakse TR-struktuuri avaldisega

TR -> (STL - STR) * E

Lõpuks saame järgmise täheklassi A kirjelduse:

SIMB A -> (STL + TR - STR),

STL -> R¦N¦ (STL + R)¦ (STL + N)

STR -> L¦N¦ (STR + L)¦ (STR + N)

TR -> (STL - STR) * E

Tunnustusprotseduuri saab sel juhul rakendada järgmiselt.

1. Pildile vastavat avaldist võrreldakse võrdlusstruktuuriga STL + TR - STR.

2. Struktuuri STL, TR, STR iga element võimaluse korral, s.o. kui pildi kirjeldus on võrreldav standardiga, sobitatakse mõni avaldis avaldisest T(A). Näiteks,

A1 jaoks: STL=R, STR=L, TR=(R-(L+N))*E

A2 jaoks: STL = R + N, STR = L, TR = ((N + R) - L) * E

A3 jaoks: STL = N + R, STR = L + N, TR = (R - L) * E 3.

Väljendeid STL, STR, TR võrreldakse nende vastavate referentsstruktuuridega.

4. Kui iga avaldise STL, STR, TR struktuur vastab standardile, tehakse järeldus, et kujutis kuulub täheklassi A. Kui mõnel etapil 2, 3, 4 esineb lahknevus analüüsitava struktuuri vahel. avaldis ja standard tuvastatakse, tehakse järeldus, et pilt ei kuulu SIMB klassi A. Väljendusstruktuuride võrdlemiseks saab kasutada algoritmkeeli LISP, PLANER, PROLOG ja muid sarnaseid tehisintellekti keeli.

Vaadeldavas näites koosnevad kõik STL ahelad sümbolitest N ja R ning STR ahelad sümbolitest L ja N, mis vastab nende ahelate antud struktuurile. Vaadeldavate piltide TR-i struktuur vastab samuti võrdlusalusele, kuna koosneb ahelate "erinevusest" nagu STL, STR, "korrutatud" sümboliga E.

Seega jõuame järeldusele, et vaadeldavad kujutised kuuluvad klassi SIMB A.

Alalisvoolu elektriajami häguse kontrolleri sünteesMatLabi keskkonnas

Ühe sisendi ja väljundiga fuzzy kontrolleri süntees.

Väljakutse on panna ajam järgima täpselt erinevaid sisendsignaale. Juhttoimingu väljatöötamist teostab fuzzy kontroller, milles saab struktuurselt eristada järgmisi funktsionaalplokke: fuzzifier, reeglite plokk ja defuzzifier.

Joon.4 Kahe keelelise muutujaga süsteemi üldistatud funktsionaalskeem.

Joonis 5 Skemaatiline diagramm hägune kontroller kahe keelelise muutujaga.

Hägujuhtimisalgoritm on üldjuhul häguse kontrolleri sisendmuutujate teisendamine selle väljundmuutujateks, kasutades järgmisi omavahel seotud protseduure:

1. juhtobjektilt mõõteanduritelt saadud sisendfüüsikaliste muutujate teisendamine häguskontrolleri sisendlingvistilisteks muutujateks;

2. loogiliste lausete, mida nimetatakse keelelisteks reegliteks, töötlemine kontrolleri sisend- ja väljundkeelemuutujate kohta;

3. fuzzy kontrolleri väljundkeeleliste muutujate teisendamine füüsilisteks juhtmuutujateks.

Vaatleme kõigepealt kõige lihtsamat juhtumit, kui servoajami juhtimiseks sisestatakse ainult kaks keelelist muutujat:

"nurk" on sisendmuutuja;

"Control action" on väljundmuutuja.

Sünteesime kontrolleri MatLabi keskkonnas Fuzzy Logic tööriistakasti abil. See võimaldab teil MatLabi keskkonnas luua hägusaid järeldusi ja hägusaid klassifitseerimissüsteeme koos võimalusega integreerida need Simulinki. Fuzzy Logic Toolboxi põhikontseptsioon on FIS-i struktuur – Fuzzy Inference System. FIS-i struktuur sisaldab kõiki vajalikke andmeid, et rakendada funktsionaalset vastendamist "sisendid-väljundid", mis põhinevad fuzzy loogilisel järeldusel vastavalt joonisel fig. 6.

Joonis 6. Hägune järeldus.

X - sisend terav vektor; - sisendvektorile X vastavate häguste hulkade vektor;
- loogilise järelduse tulemus häguste hulkade vektori kujul; Y - väljundi puhas vektor.

Hägune moodul võimaldab teil ehitada kahte tüüpi häguseid süsteeme - Mamdani ja Sugeno. Sellistes süsteemides nagu Mamdani koosneb teadmistebaas vormireeglitest "Kui x 1 = madal ja x 2 = keskmine, siis y = kõrge". Sugeno-tüüpi süsteemides koosneb teadmistebaas vormireeglitest "Kui x 1 = madal ja x 2 = keskmine, siis y = a 0 + a 1 x 1 + a 2 x 2 ". Seega on Mamdani ja Sugeno süsteemide peamine erinevus erinevatel viisidel väljundmuutuja väärtuste määramine teadmistebaasi moodustavates reeglites. Mamdani tüüpi süsteemides määratakse väljundmuutuja väärtused fuzzy terminitega, Sugeno tüüpi süsteemides - sisendmuutujate lineaarse kombinatsioonina. Meie puhul kasutame Sugeno süsteemi, sest see sobib paremini optimeerimiseks.

Servoajami juhtimiseks võetakse kasutusele kaks keelelist muutujat: "viga" (positsiooni järgi) ja "juhtimine". Esimene neist on sisend, teine ​​on väljund. Määratleme määratud muutujate jaoks terminikomplekti.

Hägusloogilise järelduse põhikomponendid. Fuzzifier.

Iga keelelise muutuja jaoks määratleme vormi põhiterminite hulga, mis sisaldab hägusaid komplekte, mida saab määrata: negatiivne kõrge, negatiivne madal, null, positiivne madal, positiivne kõrge.

Kõigepealt defineerime subjektiivselt, mida mõeldakse terminite “suur viga”, “väike viga” jne all, defineerides vastavate häguste hulkade liikmelisuse funktsioonid. Siin saate praegu juhinduda ainult nõutavast täpsusest, sisendsignaalide klassi teadaolevatest parameetritest ja tervest mõistusest. Keegi pole veel suutnud välja pakkuda ühtegi ranget algoritmi liikmelisuse funktsioonide parameetrite valimiseks. Meie puhul näeb keeleline muutuja “error” välja selline.

Joonis 7. Keeleline muutuja "viga".

Keelelist muutujat “kontroll” on mugavam esitada tabeli kujul:

Tabel 1

Reegliplokk.

Vaatleme mitme reegli määratlemise järjestust, mis kirjeldavad mõnda olukorda:

Oletame näiteks, et väljundnurk on võrdne sisendsignaaliga (st viga on null). Ilmselgelt on see soovitud olukord ja seetõttu ei pea me midagi tegema (juhtimine on null).

Mõelge nüüd teisele juhtumile: asukohaviga on palju suurem kui null. Loomulikult peame selle kompenseerima suure positiivse juhtsignaali genereerimisega.

See. on koostatud kaks reeglit, mida saab ametlikult määratleda järgmiselt:

Kui viga = null, See juhttoiming = null.

Kui viga = suur positiivne, See kontrolli mõju = suur positiivne.

Joonis 8. Kontrolli moodustumine väikese positiivse asendiveaga.

Joonis 9. Null-asendi veaga juhtimise moodustamine.

Allolevas tabelis on toodud kõik reeglid, mis vastavad selle lihtsa juhtumi kõikidele olukordadele.

tabel 2

Kokku saab n sisendi ja 1 väljundiga häguse kontrolleri jaoks defineerida juhtimisreeglid, kus on i-nda sisendi jaoks hägusate komplektide arv, kuid kontrolleri normaalseks toimimiseks ei ole vaja kasutada kõiki võimalikke reeglid, kuid saate hakkama ka vähemate reeglitega. Meie puhul kasutatakse häguse juhtsignaali genereerimiseks kõiki 5 võimalikku reeglit.

Defuzzifier.

Seega määratakse saadud mõju U mõne reegli täitmise järgi. Kui tekib olukord, kus korraga täidetakse mitu reeglit, leitakse sellest tulenev mõju U järgmise seose järgi:

, kus n on käivitatud reeglite arv (defuzzifikatsioon piirkonnakeskuse meetodil), u n– igale hägustele komplektidele vastava juhtsignaali füüsiline väärtus UBO, UMo, UZ, UMp, UBP. mUn(u)– juhtsignaali u kuuluvusaste vastavasse hägusesse hulka Un=( UBO, UMo, UZ, UMp, UBP). On ka teisi defuzzifikatsioonimeetodeid, mille puhul väljundkeeleline muutuja on võrdeline "tugevaima" või "nõrgeima" reegliga.

Modelleerime elektriajami juhtimise protsessi ülalkirjeldatud fuzzy kontrolleri abil.

Joonis 10. Süsteemi plokkskeem keskkonnasMatlab.

Joonis 11. Hägukontrolleri plokkskeem keskkonnasMatlab.

Joonis 12. Mööduv protsess üheastmelise toimingu all.

Riis. 13. Ühte sisendlingvistilist muutujat sisaldava fuzzy-kontrolleriga mudeli üleminekuprotsess harmoonilise sisendiga.

Ajami karakteristikute analüüs sünteesitud juhtimisalgoritmiga näitab, et need pole kaugeltki optimaalsed ja halvemad kui muude meetoditega juhtimise sünteesimisel (ka suuresti reguleerimine üheastmelise efektiga ja viga harmoonilisega). Seda seletatakse asjaoluga, et liikmelisuse funktsioonide parameetrid valiti üsna meelevaldselt ning kontrolleri sisenditena kasutati ainult asukohavea väärtust. Saadud regulaatori optimaalsusest ei saa loomulikult juttugi olla. Seetõttu muutub fuzzy kontrolleri optimeerimise ülesanne aktuaalseks, et saavutada võimalikult kõrged juhtimiskvaliteedi näitajad. Need. Ülesandeks on optimeerida sihtfunktsiooni f(a 1 ,a 2 …a n), kus a 1 ,a 2 …a n on koefitsiendid, mis määravad hägusregulaatori tüübi ja omadused. Häguse kontrolleri optimeerimiseks kasutame ANFIS-i plokki Matlabi keskkonnast. Samuti võib üks viise kontrolleri omaduste parandamiseks olla selle sisendite arvu suurendamine. See muudab regulaatori paindlikumaks ja parandab selle jõudlust. Lisame veel ühe sisendlingvistilise muutuja – sisendsignaali (selle tuletise) muutumise kiiruse. Reeglite arv suureneb vastavalt. Siis on regulaatori skeem järgmine:

Joonis 14 Kolme keelelise muutujaga fuzzy kontrolleri skemaatiline diagramm.

Laskma on sisendsignaali kiiruse väärtus. Põhimõistete hulga Tn määratleme järgmiselt:

Tn=("negatiivne (BO)", "null (Z)", "positiivne (BP)").

Kõikide keelemuutujate liikmelisuse funktsioonide asukoht on näidatud joonisel.

Joonis 15. Keelemuutuja “error” liikmelisuse funktsioonid.

Joonis 16. Keelemuutuja "sisendsignaali kiirus" liikmelisuse funktsioonid.

Seoses veel ühe keelelise muutuja lisamisega suureneb reeglite arv 3x5=15-ni. Nende koostamise põhimõte on täiesti sarnane eespool käsitletuga. Kõik need on näidatud järgmises tabelis:

Tabel 3

Näiteks kui Kui viga = null ja sisendsignaali tuletis = suur positiivne, See kontrolli mõju = väike negatiivne.

Joonis 17. Juhtimise kujunemine kolme keelelise muutuja all.

Sisendite arvu suurenemise ja vastavalt ka reeglite endi tõttu muutub fuzzy kontrolleri struktuur keerukamaks.

Joonis 18. Kahe sisendiga fuzzy kontrolleri plokkskeem.

Lisa pilt

Joonis 20. Kahte sisendlingvistilist muutujat sisaldava häguse kontrolleriga mudeli harmoonilise sisendiga mööduv protsess.

Riis. 21. Kahte sisendlingvistilist muutujat sisaldava häguse kontrolleriga mudeli veasignaal harmoonilise sisendi all.

Simuleerime kahe sisendiga fuzzy kontrolleri tööd Matlabi keskkonnas. Mudeli plokkskeem on täpselt sama, mis joonisel fig. 19. Harmoonilise sisendefekti siirdeprotsessi graafikult on näha, et süsteemi täpsus on oluliselt suurenenud, kuid samas on suurenenud selle võnkumine, eriti kohtades, kus väljundkoordinaadi tuletis kipub nullini. Ilmselgelt on selle põhjused, nagu eespool mainitud, nii sisend- kui ka väljundkeelemuutujate liikmelisuse funktsiooni parameetrite mitteoptimaalne valik. Seetõttu optimeerime fuzzy kontrollerit ANFISedit ploki abil Matlabi keskkonnas.

Häguse kontrolleri optimeerimine.

Vaatleme geneetiliste algoritmide kasutamist häguse kontrolleri optimeerimiseks. Geneetilised algoritmid on adaptiivsed otsingumeetodid, mida on viimasel ajal sageli kasutatud funktsionaalsete optimeerimisprobleemide lahendamiseks. Need põhinevad sarnasusel geneetiliste protsessidega bioloogilised organismid: bioloogilised populatsioonid arenevad mitme põlvkonna jooksul, järgides seadusi looduslik valik ja vastavalt Charles Darwini avastanud "kõige tugevama ellujäämise" põhimõttele. Seda protsessi jäljendades suudavad geneetilised algoritmid "välja töötada" lahendusi reaalsetele probleemidele, kui need on asjakohaselt kodeeritud.

Geneetilised algoritmid töötavad "indiviidide" kogumiga - populatsiooniga, millest igaüks esindab Võimalik lahendus see probleem. Iga indiviidi “kohanemisvõime” mõõdupuuga hinnatakse selle järgi, kui “hea” on talle vastav probleemilahendus. Kõige vormis olevad isendid suudavad järglasi "paljundada" teiste populatsiooni isenditega "ristumisel". See toob kaasa uute indiviidide esilekerkimise, kes ühendavad mõningaid omadusi, mille nad pärivad oma vanematelt. Kõige vähem sobivad isendid paljunevad väiksema tõenäosusega, nii et mis tahes tunnused, mis neil olid, kaovad järk-järgult populatsioonist.

Nii reprodutseeritakse kogu uus teostatavate lahenduste populatsioon, valides parimad esindajad eelmine põlvkond, ületades neid ja hankides palju uusi isikuid. See uus põlvkond sisaldab rohkem omadusi, mis on eelmise põlvkonna headel liikmetel. Seega põlvest põlve, head omadused levinud üle kogu elanikkonna. Lõppkokkuvõttes läheneb elanikkond probleemi optimaalsele lahendusele.

Bioloogilise evolutsiooni idee elluviimiseks geneetiliste algoritmide raames on palju võimalusi. Traditsiooniline, võib kujutada järgmise plokkskeemina, mis on näidatud joonisel 22, kus:

1. Algpopulatsiooni initsialiseerimine – probleemile etteantud arvu lahenduste genereerimine, millega algab optimeerimisprotsess;

2. Crossover- ja mutatsioonioperaatorite rakendamine;

3. Peatustingimused – tavaliselt jätkub optimeerimisprotsess seni, kuni probleemile leitakse lahendus etteantud täpsusega või kuni tehakse kindlaks, et protsess on lähenenud (st ülesande lahendus ei ole viimase N põlvkonna jooksul paranenud).

Matlabi keskkonnas esindab geneetilisi algoritme eraldi tööriistakast, samuti pakett ANFIS. ANFIS on lühend sõnadest Adaptive-Network-Based Fuzzy Inference System – adaptiivne fuzzy Inference Network. ANFIS on üks esimesi hübriid-neuro-fuzzy-võrkude variante – edasisuunatud närvivõrgu eritüüpi. Neuro-häguse võrgu arhitektuur on hägusate teadmistebaasi suhtes isomorfne. Neurohägused võrgud kasutavad kolmnurksete normide diferentseeritavaid rakendusi (korrutamine ja tõenäosuslik VÕI), samuti sujuvaid liikmelisuse funktsioone. See võimaldab kasutada närvivõrkude treenimiseks kiireid ja geneetilisi algoritme, mis põhinevad neuro-fuzzy-võrkude seadistamise backpropagation meetodil. Allpool kirjeldatakse ANFIS-võrgu iga kihi arhitektuuri ja tööreegleid.

ANFIS rakendab Sugeno fuzzy järeldussüsteemi viiekihilise edasisuunalise närvivõrguna. Kihtide eesmärk on järgmine: esimene kiht on sisendmuutujate terminid; teine ​​kiht - hägusate reeglite eelkäijad (eeldused); kolmas kiht on reeglitele vastavuse astmete normaliseerimine; neljas kiht on reeglite sõlmimine; viies kiht on erinevate reeglite järgi saadud tulemuse liitmine.

Võrgu sisendeid ei eraldata eraldi kihile. Joonisel 23 on kujutatud ANFIS-võrku, millel on üks sisendmuutuja ("viga") ja viis ebamäärast reeglit. Sisendmuutuja “error” keeleliseks hindamiseks kasutatakse 5 terminit.

Joonis 23. StruktuurANFIS- võrgud

Tutvustame edasiseks esitamiseks vajalikku tähistust:

Laskma olla võrgu sisendid;

y - võrgu väljund;

Hägune reegel järjenumbriga r;

m - reeglite arv;

Liikmefunktsiooniga hägune termin, mida kasutatakse r-nda reegli muutuja keeleliseks hindamiseks (,);

Reaalarvud r-nda reegli (,) järelduses.

ANFIS-võrk töötab järgmiselt.

1. kiht. Iga sõlm esimeses kihis esindab ühte kellakujulise liikmefunktsiooniga terminit. Võrgu sisendid on ühendatud ainult nende tingimustega. Sõlmede arv esimeses kihis võrdub sisendmuutujate terminihulkade kardinaalsuste summaga. Sõlme väljund on määr, mil määral sisendmuutuja väärtus kuulub vastavale häguse liikmele:

,

kus a, b ja c on liikmefunktsiooni konfigureeritavad parameetrid.

2. kiht. Teise kihi sõlmede arv on m. Selle kihi iga sõlm vastab ühele häguse reeglile. Teise kihi sõlm on ühendatud nende esimese kihi sõlmedega, mis moodustavad vastava reegli eelkäijad. Seetõttu saab iga teise kihi sõlm vastu võtta 1 kuni n sisendsignaali. Sõlme väljund on reegli täitmise aste, mis arvutatakse sisendsignaalide korrutisena. Tähistame selle kihi sõlmede väljundid , .

3. kiht. Kolmanda kihi sõlmede arv on samuti m. Selle kihi iga sõlm arvutab häguse reegli suhtelise täitmise astme:

4. kiht. Neljanda kihi sõlmede arv on samuti m. Iga sõlm on ühendatud nii kolmanda kihi ühe sõlmega kui ka kõigi võrgusisenditega (ühendusi sisenditega joonisel 18 ei kujuta). Neljanda kihi sõlm arvutab ühe häguse reegli panuse võrguväljundisse:

5. kiht. Selle kihi üks sõlm võtab kokku kõigi reeglite panuse:

.

ANFIS-võrgu konfigureerimiseks saab kasutada tüüpilisi närvivõrkude treenimise protseduure, kuna see kasutab ainult eristatavaid funktsioone. Tavaliselt kasutatakse gradiendi laskumise kombinatsiooni tagasilevimise algoritmi ja meetodi kujul vähimruudud. Tagasilevimise algoritm korrigeerib reeglite eelkäija parameetreid, st. liikmelisuse funktsioonid. Reegli järelduste koefitsiente hinnatakse vähimruutude meetodil, kuna need on lineaarselt seotud võrgu väljundiga. Iga seadistusprotseduuri iteratsioon viiakse läbi kahes etapis. Esimeses etapis antakse sisenditele treeningnäidis ning kasutades lahknevust võrgu soovitud ja tegeliku käitumise vahel, kasutatakse iteratiivset vähimruutude meetodit. optimaalsed parameetrid neljanda kihi sõlmed. Teises etapis kantakse jääkjääk võrguväljundist sisenditesse ja esimese kihi sõlmede parameetreid muudetakse tagasilevimise meetodil. Sellisel juhul ei muutu esimeses etapis leitud reegli järelduskoefitsiendid. Iteratiivne häälestusprotseduur jätkub, kuni lahknevus ületab etteantud väärtuse. Liikmefunktsioonide seadistamiseks saab lisaks backpropagation meetodile kasutada ka teisi optimeerimisalgoritme, näiteks Levenberg-Marquardti meetodit.

Joonis 24. ANFIMuuda tööpiirkonda.

Proovime nüüd optimeerida fuzzy kontrollerit ühe sammu toimingu jaoks. Soovitaval üleminekuprotsessil on ligikaudu järgmine vorm:

Joonis 25. Soovitud üleminekuprotsess.

Joonisel fig näidatud graafikult. järgib seda enamus aja jooksul peab mootor töötama täisvõimsusel, et tagada maksimaalne jõudlus ning soovitud väärtusele lähenedes sujuvalt pidurdama. Nendest lihtsatest argumentidest juhindudes võtame koolitusnäidisena järgmise väärtuste näidise, mis on esitatud allpool tabeli kujul:

Tabel 4

Joonis 26. Treeningu näidise tüüp.

Koolituse viime läbi 100 sammuga. See on kasutatud meetodi ühtlustamiseks enam kui piisav.

Joonis 27. Närvivõrgu treenimise protsess.

Õppeprotsessi käigus moodustatakse liikmelisuse funktsioonide parameetrid selliselt, et kontroller loob etteantud veaväärtuse jaoks vajaliku kontrolli. Sõlmepunktide vahelisel alal on kontrollisõltuvus veast tabeli andmete interpolatsioon. Interpolatsioonimeetod sõltub sellest, kuidas närvivõrku treenitakse. Tegelikult saab fuzzy kontrolleri mudelit pärast treenimist esitada ühe muutuja mittelineaarse funktsioonina, mille graafik on toodud allpool.

Joonis 28. Juhtimise ja asendi vea graafik kontrolleri sees.

Olles salvestanud leitud liikmelisuse funktsioonide parameetrid, simuleerime süsteemi optimeeritud fuzzy kontrolleriga.

Riis. 29. Transientprotsess harmoonilise sisendiga mudeli jaoks optimeeritud häguse kontrolleriga, mis sisaldab üht sisendlingvistilist muutujat.

Joonis 30. Kahte sisendlingvistilist muutujat sisaldava häguse kontrolleriga mudeli harmoonilise sisendi toimingu veasignaal.

Graafikutest järeldub, et fuzzy kontrolleri optimeerimine närvivõrgu koolituse abil oli edukas. Vea varieeruvus ja ulatus vähenesid oluliselt. Seetõttu on hägusloogikal põhinevate regulaatorite optimeerimiseks närvivõrgu kasutamine igati õigustatud. Kuid isegi optimeeritud kontroller ei suuda täita täpsuse nõudeid, mistõttu on soovitatav kaaluda mõnda muud juhtimismeetodit, kui häguskontroller ei juhi objekti otseselt, vaid kombineerib mitu juhtimisseadust olenevalt hetkeolukorrast.