Multi-label klassificering

I maskininlärning är klassificering med flera etiketter eller klassificering med flera utgångar en variant av klassificeringsproblemet där flera icke-exklusiva etiketter kan tilldelas varje instans. Multi-label classification är en generalisering av multiclass classification , vilket är problemet med en etikett med att kategorisera instanser i exakt en av flera (fler än två) klasser. I fleretikettsproblemet är etiketterna icke-exklusiva och det finns ingen begränsning för hur många av klasserna instansen kan tilldelas.

Formellt är fleretikettsklassificering problemet med att hitta en modell som mappar ingångar x till binära vektorer y ; det vill säga den tilldelar ett värde på 0 eller 1 för varje element (etikett) i y .

Metoder för problemomvandling

Det finns flera problemomvandlingsmetoder för klassificering av flera etiketter och kan grovt delas upp i:

Transformation till binära klassificeringsproblem : baslinjemetoden, kallad den binära relevansmetoden , går ut på att självständigt träna en binär klassificerare för varje etikett. Givet ett osynligt prov förutsäger den kombinerade modellen sedan alla etiketter för detta prov för vilka respektive klassificerare förutsäger ett positivt resultat. Även om denna metod för att dela upp uppgiften i flera binära uppgifter ytligt kan likna metoderna en-mot-alla (OvA) och en-mot-vila (OvR) för flerklassklassificering, är den väsentligt skild från båda, eftersom en enda klassificerare under binär relevans handlar om en enda etikett, utan någon som helst hänsyn till andra etiketter. En klassificeringskedja är en alternativ metod för att omvandla ett klassificeringsproblem med flera etiketter till flera binära klassificeringsproblem. Den skiljer sig från binär relevans genom att etiketter förutsägs sekventiellt, och utdata från alla tidigare klassificerare (dvs. positiva eller negativa för en viss etikett) matas in som funktioner till efterföljande klassificerare. Klassificeringskedjor har använts, till exempel, i HIV- läkemedelsresistens. Bayesiskt nätverk har också använts för att optimalt beställa klassificerare i klassificerareskedjor .
Transformation till flerklassklassificeringsproblem : Label Powerset (LP)-transformationen skapar en binär klassificerare för varje etikettkombination som finns i träningsuppsättningen. Till exempel, om möjliga etiketter för ett exempel var A, B och C, är etikettens powerset-representation av detta problem ett klassificeringsproblem med flera klasser med klasserna [0 0 0], [1 0 0], [0 1 0 ], [0 0 1], [1 1 0], [1 0 1], [0 1 1]. [1 1 1] där till exempel [1 0 1] betecknar ett exempel där etiketter A och C finns och etikett B saknas.
Ensemblemetoder : En uppsättning flerklassklassificerare kan användas för att skapa en ensembleklassificerare för flera etiketter. För ett givet exempel matar varje klassificerare ut en enda klass (motsvarande en enda etikett i fleretikettsproblemet). Dessa förutsägelser kombineras sedan med en ensemblemetod, vanligtvis ett röstningsschema där varje klass som får en erforderlig procentandel av röster från individuella klassificerare (ofta kallad diskrimineringströskeln) förutsägs som en aktuell etikett i multietikettutmatningen. Det finns dock mer komplexa ensemblemetoder, såsom kommittémaskiner . En annan variant är algoritmen för slumpmässiga $k$ -etiketter (RAKEL), som använder flera LP-klassificerare, var och en tränad på en slumpmässig delmängd av de faktiska etiketterna; Förutsägelse av etiketter utförs sedan genom ett röstsystem. En uppsättning klassificerare för flera etiketter kan användas på liknande sätt för att skapa en klassificerare för flera etiketter. I det här fallet röstar varje klassificerare en gång för varje etikett som den förutsäger snarare än för en enda etikett.

Anpassade algoritmer

Vissa klassificeringsalgoritmer/modeller har anpassats till multi-label-uppgiften, utan att kräva problemtransformationer. Exempel på dessa inklusive för multi-label data är

k-närmaste grannar : ML-kNN-algoritmen utökar k-NN-klassificeraren till fleretikettsdata.
beslutsträd : "Clare" är en anpassad C4.5-algoritm för klassificering av flera etiketter; modifieringen involverar entropiberäkningar. MMC-, MMDT- och SSC-förfinade MMDT kan klassificera flermärkta data baserat på attribut med flera värden utan att omvandla attributen till enstaka värden. De kallas också klassificeringsmetoder med flera värden och flera märkta beslutsträd.
kärnmetoder för vektorutdata
neurala nätverk : BP-MLL är en anpassning av den populära back-propagation-algoritmen för multi-label learning.

Lärande paradigm

Baserat på inlärningsparadigm kan de befintliga klassificeringsteknikerna för flera etiketter klassificeras i batchinlärning och online maskininlä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(er) ŷ _t med den aktuella modellen; Algoritmen tar sedan emot y _t , den eller de sanna etiketterna för x _t och uppdaterar sin modell baserat på sampel-etikett-paret: (x _t , y _t ).

Multi-label strömklassificering

Dataströmmar är möjligen oändliga sekvenser av data som kontinuerligt och snabbt växer över tiden. Multi-label stream classification (MLSC) är versionen av multi-label klassificeringsuppgift som äger rum i dataströmmar. Det kallas ibland även online-multi-label-klassificering. Svårigheterna med klassificering av flera etiketter (exponentiellt antal möjliga etikettuppsättningar, fånga beroenden mellan etiketter) kombineras med svårigheter med dataströmmar (tids- och minnesbegränsningar, adressering av oändlig ström med ändliga medel, konceptdrift ) .

Många MLSC-metoder tar till ensemblemetoder för att öka sin prediktiva prestanda och hantera konceptdrifter. Nedan är de mest använda ensemblemetoderna i litteraturen:

Online Bagging (OzaBagging)-baserade metoder : Att observera sannolikheten för att ha K många av en viss datapunkt i ett bootstrap-prov är ungefär Poisson(1) för stora datamängder, varje inkommande datainstans i en dataström kan viktas proportionellt mot Poisson( 1) distribution för att efterlikna bootstrapping i en onlinemiljö. Detta kallas Online Bagging (OzaBagging). Många fleretikettsmetoder som använder Online Bagging föreslås i litteraturen, som var och en använder olika problemomvandlingsmetoder. EBR, ECC, EPS, E _B RT, E _B MT, ML-Random Rules är exempel på sådana metoder.
ADWIN Bagging-baserade metoder: Online Bagging-metoder för MLSC kombineras ibland med explicita konceptdriftsdetekteringsmekanismer som ADWIN (Adaptive Window). ADWIN behåller ett fönster i variabel storlek för att upptäcka förändringar i distributionen av data, och förbättrar ensemblen genom att återställa de komponenter som fungerar dåligt när det finns en drift i inkommande data. I allmänhet används bokstaven 'a' som en sänkning i namnet på sådana ensembler för att indikera användningen av ADWIN-ändringsdetektor. E _a BR, E _a CC, E _a HT _PS är exempel på sådana multi-label-ensembler.
GOOWE-ML -baserade metoder : Tolka relevanspoängen för varje komponent i ensemblen som vektorer i etikettutrymmet och lösa ett minsta kvadratproblem i slutet av varje batch, Geometrically-Optimum Online-Weighted Ensemble for Multi-label Classification (GOOWE -ML) föreslås. Ensemblen försöker minimera avståndet mellan den viktade förutsägelsen av dess komponenter och marksanningsvektorn för varje instans över en batch. Till skillnad från Online Bagging och ADWIN Bagging, använder GOOWE-ML ett viktat röstningsschema där bättre presterande komponenter i ensemblen får mer vikt. GOOWE-ML-ensemblen växer med tiden, och den lägsta viktkomponenten ersätts av en ny komponent när den är full i slutet av en batch. GOBR, GOCC, GOPS, GORT är de föreslagna GOOWE-ML-baserade multi-label-ensemblerna.
Flera fönster : Här ersätts BR-modeller som använder ett skjutfönster med två fönster för varje etikett, ett för relevanta och ett för icke-relevanta exempel. Förekomster översamplas eller undersamplas enligt en belastningsfaktor som hålls mellan dessa två fönster. Detta gör att konceptdrifter som är oberoende för varje etikett kan detekteras och klassobalans (skevhet i de relevanta och icke-relevanta exemplen) kan hanteras.

Statistik och utvärderingsmått

Anser att $Y_{i}$ är en uppsättning etiketter för $i^{th}$ dataprovet (förväxla det inte med en envarm vektor; det är helt enkelt en samling av alla etiketter som tillhör detta prov), i vilken utsträckning en datauppsättning är multi-label kan fångas i två statistik:

Etikettkardinalitet är det genomsnittliga antalet etiketter per exempel i uppsättningen: ${\frac {1}{N}}\sum _{i=1}^{N}|Y_{i}|$ där $N$ är det totala antalet dataprover;
Etikettdensitet är antalet etiketter per prov dividerat med det totala antalet etiketter, i medeltal över proverna: ${\frac {1}{N}}\sum _{i=1}^{N}{\frac {|Y_{i}|}{|L|}}$ där ${\displaystyle L=\bigcup _{i=1}^{N}Y_{i}} ,$ det totala antalet tillgängliga klasser (vilket är det maximala antalet element som kan utgöra $Y_ {i}$ ).

Utvärderingsmått för klassificeringsprestanda för flera etiketter skiljer sig i sig från de som används i flerklass- (eller binär) klassificering, på grund av de inneboende skillnaderna i klassificeringsproblemet. Om $T$ betecknar den sanna uppsättningen etiketter för ett givet prov och $P$ den förutsagda uppsättningen etiketter, kan följande mätvärden definieras för det urvalet:

Hammingförlust : bråkdelen av fel etiketter av det totala antalet etiketter, dvs ${\displaystyle {\frac {1}{|N|\cdot |L|}}\summa _{i=1}^{|N|}\summa _ {j=1}^{|L|}\operatörsnamn {xor} (y_{i,j},z_{i,j})} , där y i, j {\displaystyle y_$ { $}$ är target, $z_{i,j}$ är förutsägelsen, och $\operatorname {xor} (\cdot )$ är operatorn "Exklusiv, eller" som returnerar noll när målet och förutsägelsen är identiska och ett annat. Detta är en förlustfunktion , så det optimala värdet är noll och dess övre gräns är ett.
Det närbesläktade Jaccard-indexet , även kallat Intersection over Union i multi-label-inställningen, definieras som antalet korrekt förutsagda etiketter dividerat med föreningen av predikterade och sanna etiketter, ${\frac {|T\cap P|}{|T\cup P|}}$ , där $P$ och $T$ är uppsättningar av predikterade etiketter respektive sanna etiketter.
Precision, återkallelse och $F_{1}$ poäng : precision är ${\displaystyle {\frac {|T\cap P|}{|P|}}} ,$ återkallelse är ${\frac {|T\cap P|}{|T|}}$ , och $F_{1}$ är deras harmoniska medelvärde .
Exakt matchning (även kallad Delmängdsnoggrannhet): är det mest strikta måttet, som anger procentandelen av prover som har alla sina etiketter klassificerade korrekt.

Korsvalidering i inställningar för flera etiketter kompliceras av det faktum att det vanliga (binära/flerklassiga) sättet för stratifierad sampling inte kommer att fungera; alternativa sätt för ungefärlig stratifierad provtagning har föreslagits.

Implementeringar och dataset

Java-implementationer av algoritmer för flera etiketter är tillgängliga i mjukvarupaketen Mulan och Meka , båda baserade på Weka .

Scikit -learn Python-paketet implementerar några algoritmer och mätvärden för flera etiketter .

Scikit -multilearn Python-paketet vänder sig specifikt till multi-label-klassificeringen. Det tillhandahåller multi-label implementering av flera välkända tekniker inklusive SVM, kNN och många fler . Paketet är byggt ovanpå scikit-learn- ekosystemet.

Den binära relevansmetoden, klassificeringskedjor och andra multietikettalgoritmer med många olika basinlärare är implementerade i R-paketet mlr

En lista över vanliga datauppsättningar med flera etiketter finns på Mulans webbplats .

Se även

Vidare läsning

Madjarov, Gjorgji; Kocev, Dragi; Gjorgjevikj, Dejan; Džeroski, Sašo (2012). "En omfattande experimentell jämförelse av metoder för multi-label learning". Mönsterigenkänning . 45 (9): 3084–3104. doi : 10.1016/j.patcog.2012.03.004 .