Relief (algorisme)

Algorisme d'alleujament: selecció de l'impacte més proper i els veïns de la instància de error més propera abans de la puntuació.

Relief és un algorisme desenvolupat per Kira i Rendell el 1992 que adopta un enfocament de mètode de filtre per a la selecció de característiques que és notablement sensible a les interaccions de les característiques. Va ser dissenyat originalment per a l'aplicació a problemes de classificació binària amb característiques numèriques o discretes. El relleu calcula una puntuació de funció per a cada característica que després es pot aplicar per classificar i seleccionar les funcions de millor puntuació per a la selecció de funcions. Alternativament, aquestes puntuacions es poden aplicar com a pesos de característiques per guiar el modelatge aigües avall. La puntuació de les característiques de relleu es basa en la identificació de les diferències de valors entre els parells d'instàncies veïnes més properes. Si s'observa una diferència de valor de característiques en un parell d'instàncies veïnes amb la mateixa classe (un "èxit"), la puntuació de la característica disminueix. Alternativament, si s'observa una diferència de valors de característica en un parell d'instàncies veïnes amb valors de classe diferents (un "falta"), la puntuació de la característica augmenta. L'algoritme original de Relief ha inspirat des d'aleshores una família d'algoritmes de selecció de característiques (RBA) basats en Relief, inclòs l'algoritme ReliefF. Més enllà de l'algoritme de relleu original, els RBA s'han adaptat per (1) funcionar de manera més fiable en problemes sorollosos, (2) generalitzar a problemes multiclasse (3) generalitzar a problemes de resultats numèrics (és a dir, regressió), i (4) per fer-los robusts a dades incompletes (és a dir, que falten).

Fins ara, el desenvolupament de variants i extensions RBA s'ha centrat en quatre àmbits; (1) la millora del rendiment de l'algoritme de relleu "núclic", és a dir, l'examen d'estratègies per a la selecció de veïns i la ponderació d'instàncies, (2) la millora de l'escalabilitat de l'algoritme de relleu "núclic" a espais de característiques més grans mitjançant enfocaments iteratius, (3) mètodes per adaptar-se de manera flexible Relleu a diferents tipus de dades i (4) millorar l'eficiència de l'execució de Relief.

Els seus punts forts són que no depenen de l'heurística, s'executen en temps polinomial d'ordre baix, i són tolerants al soroll i robustos per incloure interaccions, a més de ser aplicables a dades binàries o contínues; tanmateix, no discrimina entre característiques redundants i un nombre baix d'instàncies d'entrenament enganya l'algorisme.

Algorisme Relief

Preneu un conjunt de dades amb n instàncies de p característiques, pertanyents a dues classes conegudes. Dins del conjunt de dades, cada característica s'hauria d'escalar a l'interval [0 1] (les dades binàries haurien de romandre com a 0 i 1). L'algorisme es repetirà m vegades. Comenceu amb un vector de pes p -long (W) de zeros.

A cada iteració, agafeu el vector de característiques (X) que pertany a una instància aleatòria i els vectors de característiques de la instància més propera a X (per distància euclidiana) de cada classe. La instància de la mateixa classe més propera s'anomena 'near-hit', i la instància de classe diferent més propera s'anomena 'near-miss'. Actualitzeu el vector de pes de manera que

$W_{i}=W_{i}-(x_{i}-\mathrm {nearHit} _{i})^{2}+(x_{i}-\mathrm {nearMiss} _{i})^{2}$

Així, el pes de qualsevol característica donada disminueix si difereix d'aquesta característica en instàncies properes de la mateixa classe més que en instàncies properes de l'altra classe, i augmenta en el cas invers.Després de m iteracions, divideix cada element del vector de pes per m . Aquest es converteix en el vector de rellevància. Les característiques es seleccionen si la seva rellevància és superior a un llindar τ.