Flerklassklassificering

I maskininlärning och statistisk klassificering är multiklassklassificering eller multinomialklassificering problemet med att klassificera instanser i en av tre eller flera klasser (att klassificera instanser i en av två klasser kallas binär klassificering ).

Medan många klassificeringsalgoritmer (särskilt multinomial logistisk regression ) naturligt tillåter användning av mer än två klasser, är vissa av naturen binära algoritmer; dessa kan dock omvandlas till multinomialklassificerare genom en mängd olika strategier.

Multiclass-klassificering ska inte förväxlas med multi-label-klassificering , där flera etiketter ska förutsägas för varje instans.

Allmänna strategier

De befintliga flerklassklassificeringsteknikerna kan kategoriseras i (i) transformation till binär (ii) förlängning från binär och (iii) hierarkisk klassificering.

Transformation till binär

Det här avsnittet diskuterar strategier för att reducera problemet med multiklassklassificering till multipla binära klassificeringsproblem. Det kan kategoriseras i en mot vila och en mot en . De tekniker som utvecklats baserat på att reducera multiklassproblemet till multipla binära problem kan också kallas problemtransformationstekniker.

En-mot-vila

En-mot-vila (OvR eller en-mot-alla , OvA eller en-mot-alla , OAA)-strategi innebär att man tränar en enda klassificerare per klass, med proverna från den klassen som positiva prover och alla andra prover som negativa . Denna strategi kräver att basklassificerarna producerar ett verkligt värderat konfidenspoäng för sitt beslut, snarare än bara en klassetikett; Enbart diskreta klassetiketter kan leda till oklarheter, där flera klasser förutsägs för ett enda prov.

I pseudokod är träningsalgoritmen för en OvR-lärare konstruerad från en binär klassificeringsinlärare $L$ som följer:

Ingångar:

$L$ , en inlärare (träningsalgoritm för binära klassificerare)
prover $X$
etiketter $y$ där $y i$ ∈ {1, … $K$ } är etiketten för provet $X i$

Utdata:

en lista med klassificerare $f k$ för $k$ ∈ {1, …, $K$ }

Procedur:

För varje k i {1, …, K }
- Konstruera en ny etikettvektor $z$ där $z i$ = $y i$ om $y i = k$ och $z i = 0$ annars
- Applicera $L$ på $X$ , $z$ för att få $f k$

Att fatta beslut innebär att tillämpa alla klassificerare på ett osynligt prov $x$ och förutsäga etiketten $k$ för vilken motsvarande klassificerare rapporterar högsta konfidenspoäng:

{\hat {y}}={\underset {k\in \{1\ldots K\}}{\arg \!\ max }}\;f_{k}(x)

Även om denna strategi är populär är det en heuristik som lider av flera problem. För det första kan skalan på konfidensvärdena skilja sig åt mellan de binära klassificerarna. För det andra, även om klassfördelningen är balanserad i träningsuppsättningen, ser eleverna med binär klassificering obalanserade fördelningar eftersom uppsättningen av negativa som de ser vanligtvis är mycket större än uppsättningen positiva.

En-mot-en

I en-mot-en- reduktionen (OvO) tränar man $K (K - 1) / 2$ binära klassificerare för ett $K$ -vägs multiklassproblem; var och en får proverna av ett par klasser från den ursprungliga träningsuppsättningen och måste lära sig att skilja dessa två klasser åt. Vid prediktionstidpunkten tillämpas ett röstningsschema: alla $K (K - 1) / 2$ klassificerare appliceras på ett osynligt urval och den klass som fick det högsta antalet "+1" förutsägelser förutsägs av den kombinerade klassificeraren.

Liksom OvR lider OvO av oklarheter i det att vissa regioner i dess inmatningsutrymme kan få samma antal röster.

Förlängning från binär

Det här avsnittet diskuterar strategier för att utöka de befintliga binära klassificerarna för att lösa klassificeringsproblem med flera klasser. Flera algoritmer har utvecklats baserade på neurala nätverk , beslutsträd , k-närmaste grannar , naiva Bayes , stödvektormaskiner och extrema inlärningsmaskiner för att lösa klassificeringsproblem i flera klasser. Dessa typer av tekniker kan också kallas algoritmanpassningstekniker.

Neurala nätverk

Flerklassperceptroner ger en naturlig förlängning av multiklassproblemet. Istället för att bara ha en neuron i utgångsskiktet, med binär utsignal, skulle man kunna ha N binära neuroner som leder till flerklassklassificering. I praktiken är det sista lagret i ett neuralt nätverk vanligtvis ett softmax-funktionslager , vilket är den algebraiska förenklingen av N logistiska klassificerare, normaliserad per klass med summan av N-1 andra logistiska klassificerare.

Extrema inlärningsmaskiner

Extrema inlärningsmaskiner (ELM) är ett specialfall av enkla dolda skikt av feed-forward neurala nätverk (SLFN) där ingångsvikterna och de dolda nodförspänningarna kan väljas slumpmässigt. Många varianter och utvecklingar görs av ELM för klassificering i flera klasser.

k-närmaste grannar

k-närmaste grannar kNN anses vara bland de äldsta icke-parametriska klassificeringsalgoritmerna. För att klassificera ett okänt exempel mäts avståndet från det exemplet till vartannat träningsexempel. De k minsta avstånden identifieras, och den mest representerade klassen av dessa k närmaste grannar anses vara utdataklassetiketten.

Naiv Bayes

Naive Bayes är en framgångsrik klassificerare baserad på principen om maximum a posteriori (MAP). Detta tillvägagångssätt kan naturligtvis utökas till att ha mer än två klasser och visade sig fungera bra trots det underliggande förenklade antagandet om villkorligt oberoende .

Beslutsträd

Beslutsträdsinlärning är en kraftfull klassificeringsteknik. Trädet försöker härleda en uppdelning av träningsdata baserat på värdena för de tillgängliga funktionerna för att ge en bra generalisering. Algoritmen kan naturligtvis hantera binära eller multiklassklassificeringsproblem. Bladnoderna kan referera till vilken som helst av de berörda K-klasserna.

Stöd vektor maskiner

Stödvektormaskiner är baserade på idén att maximera marginalen, dvs maximera minimiavståndet från det separerande hyperplanet till närmaste exempel. Den grundläggande SVM stöder endast binär klassificering, men tillägg har föreslagits för att hantera flerklassklassificeringsfallet också. I dessa tillägg läggs ytterligare parametrar och begränsningar till optimeringsproblemet för att hantera separationen av de olika klasserna.

Multi expression programmering

Multi expression programmering (MEP) är en evolutionär algoritm för att generera datorprogram (som också kan användas för klassificeringsuppgifter). MEP har en unik funktion: den kodar flera program till en enda kromosom. Vart och ett av dessa program kan användas för att generera utdata för en klass, vilket gör MEP naturligt lämplig för att lösa klassificeringsproblem i flera klasser.

Hierarkisk klassificering

Hierarkisk klassificering tar itu med flerklassklassificeringsproblemet genom att dela upp utgångsutrymmet, dvs. i ett träd . Varje föräldernod är uppdelad i flera underordnade noder och processen fortsätter tills varje underordnad nod endast representerar en klass. Flera metoder har föreslagits baserat på hierarkisk klassificering.

Lärande paradigm

Baserat på inlärningsparadigm kan de befintliga klassificeringsteknikerna i flera klasser klassificeras i batchinlärning och onlineinlärning . Algoritmer för batchinlärning kräver att alla dataprover är tillgängliga i förväg. Den tränar modellen med hjälp av hela träningsdata och förutsäger sedan testprovet med hjälp av det hittade sambandet. Online-inlärningsalgoritmerna bygger å andra sidan stegvis sina modeller i sekventiella iterationer. I iteration t tar en onlinealgoritm emot ett sampel, x _t och förutsäger dess etikett ŷ _t med den aktuella modellen; Algoritmen tar sedan emot y _t , den sanna etiketten för x _t och uppdaterar sin modell baserat på sampel-etikett-paret: (x _t , y _t ). Nyligen har ett nytt inlärningsparadigm som kallas progressiv inlärningsteknik utvecklats. Den progressiva inlärningstekniken är kapabel att inte bara lära sig från nya prov utan också att lära sig nya klasser av data och ändå behålla den kunskap som lärts hittills.

Se även

Anteckningar