Hispanopedia Wiki
Articulo de referencia

Relieve (selección de características)

Relief es un algoritmo desarrollado por Kenji Kira y Larry Rendell en 1992 que emplea un método de filtrado para la selección de características , notablemente sensible a las in...

Hispanopedia WikiContenido en espanolLectura gratuita

Relief es un algoritmo desarrollado por Kenji Kira y Larry Rendell en 1992 que emplea un método de filtrado para la selección de características , notablemente sensible a las interacciones entre ellas. [ 1 ] [ 2 ] Originalmente, fue diseñado para su aplicación a problemas de clasificación binaria con características discretas o numéricas. Relief calcula una puntuación para cada característica, la cual puede utilizarse para clasificar y seleccionar las características con mayor puntuación. Alternativamente, estas puntuaciones pueden aplicarse como ponderaciones para guiar el modelado posterior. La puntuación de Relief se basa en la identificación de diferencias en los valores de las características entre pares de instancias vecinas más cercanas . Si se observa una diferencia en el valor de una característica en un par de instancias vecinas con la misma clase (un "acierto"), la puntuación disminuye. Por el contrario, si se observa una diferencia en el valor de una característica en un par de instancias vecinas con diferentes clases (un "fallo"), la puntuación aumenta. El algoritmo Relief original ha inspirado una familia de algoritmos de selección de características basados ​​en Relief (RBA), incluido el algoritmo ReliefF [ 3 ] . Más allá del algoritmo Relief original, los RBA se han adaptado para (1) funcionar de manera más confiable en problemas con ruido, [ 4 ] (2) generalizarse a problemas de múltiples clases [ 4 ] (3) generalizarse a problemas de resultados numéricos (es decir, regresión), [ 5 ] y (4) hacerlos robustos a datos incompletos (es decir, faltantes). [ 4 ]

Hasta la fecha, el desarrollo de variantes y extensiones de RBA se ha centrado en cuatro áreas: (1) mejorar el rendimiento del algoritmo Relief "núcleo", es decir, examinar estrategias para la selección de vecinos y la ponderación de instancias, (2) mejorar la escalabilidad del algoritmo Relief "núcleo" a espacios de características más grandes mediante enfoques iterativos, (3) métodos para adaptar Relief de forma flexible a diferentes tipos de datos, y (4) mejorar la eficiencia de ejecución de Relief. [ 6 ]

Sus ventajas radican en que no dependen de heurísticas, se ejecutan en tiempo polinomial de bajo orden, son tolerantes al ruido y robustos ante las interacciones entre características, además de ser aplicables a datos binarios o continuos; sin embargo, no discriminan entre características redundantes y un número reducido de instancias de entrenamiento puede engañar al algoritmo.

Algoritmo de alivio

Algoritmo de alivio: Selección de los vecinos de instancia de acierto más cercano y de fallo más cercano antes de la puntuación.

Consideremos un conjunto de datos con n instancias de p características, pertenecientes a dos clases conocidas. Dentro del conjunto de datos, cada característica debe escalarse al intervalo [0, 1] (los datos binarios deben permanecer como 0 y 1). El algoritmo se repetirá m veces. Comencemos con un vector de pesos (W) de longitud p compuesto por ceros.

En cada iteración, tome el vector de características (X) perteneciente a una instancia aleatoria y los vectores de características de la instancia más cercana a X (por distancia euclidiana ) de cada clase. La instancia más cercana de la misma clase se llama 'casi acierto', y la instancia más cercana de clase diferente se llama 'casi error'. Actualice el vector de pesos de tal manera que

Wi=Wi−(incógnitai−nortemiarHiti)2+(incógnitai−nortemiarMETROissi)2,{\displaystyle W_{i}=W_{i}-(x_{i}-\mathrm {nearHit} _{i})^{2}+(x_{i}-\mathrm {nearMiss} _{i})^{2},}

dóndei{\displaystyle i}indexa los componentes y va del 1 al p.

Por lo tanto, el peso de cualquier característica dada disminuye si difiere de esa característica en instancias cercanas de la misma clase más que en instancias cercanas de la otra clase, y aumenta en el caso contrario.

Después de m iteraciones, divide cada elemento del vector de pesos por m . Esto se convierte en el vector de relevancia. Las características se seleccionan si su relevancia es mayor que un umbral τ .

Los experimentos de Kira y Rendell [ 2 ] mostraron un claro contraste entre características relevantes e irrelevantes, lo que permitió determinar τ por simple inspección. Sin embargo, también se puede determinar mediante la desigualdad de Chebyshev para un nivel de confianza dado ( α ) que un τ de 1/sqrt(α*m) es suficiente para que la probabilidad de un error de tipo I sea menor que α , aunque se afirma que τ puede ser mucho menor que eso.

También se describió que Relief era generalizable a la clasificación multinomial mediante la descomposición en una serie de problemas binarios.

Algoritmo ReliefF

Kononenko et al. proponen varias actualizaciones para Relief. [ 3 ] En primer lugar, encuentran las instancias de casi acierto y casi error utilizando la norma de Manhattan (L1) en lugar de la norma euclidiana (L2) , aunque no especifican la justificación. Además, encontraron que tomar las diferencias absolutas entre x i y casi acierto i , y x i y casi error i es suficiente al actualizar el vector de pesos (en lugar del cuadrado de esas diferencias).

Estimación de probabilidad fiable

En lugar de repetir el algoritmo m veces, se implementa de forma exhaustiva (es decir, n veces, una vez por cada instancia) para valores de n relativamente pequeños (hasta mil). Además, en lugar de encontrar el único acierto y el único fallo más cercanos, lo que podría provocar que atributos redundantes y ruidosos afecten la selección de los vecinos más cercanos, ReliefF busca k aciertos y fallos más cercanos y promedia su contribución a los pesos de cada característica. El valor de k se puede ajustar para cada problema individual.

Datos incompletos

En ReliefF, la contribución de los valores faltantes al peso de las características se determina mediante la probabilidad condicional de que dos valores sean iguales o diferentes, aproximada con frecuencias relativas del conjunto de datos. Esto se puede calcular si falta una o ambas características.

Problemas multiclase

En lugar de utilizar la descomposición propuesta por Kira y Rendell de una clasificación multinomial en varios problemas binomiales, ReliefF busca k coincidencias cercanas de cada clase diferente y promedia sus contribuciones para actualizar W, ponderadas con la probabilidad previa de cada clase.

Otras extensiones/derivados de algoritmos basados ​​en el alivio

Las siguientes RBA están ordenadas cronológicamente de la más antigua a la más reciente. [ 6 ] Incluyen métodos para mejorar (1) el concepto central del algoritmo Relief, (2) enfoques iterativos para la escalabilidad, (3) adaptaciones a diferentes tipos de datos, (4) estrategias para la eficiencia computacional o (5) alguna combinación de estos objetivos. Para más información sobre las RBA, consulte estos capítulos de libros [ 7 ] [ 8 ] [ 9 ] o este artículo de revisión más reciente. [ 6 ]

RRELIEFF

Robnik-Šikonja y Kononenko proponen actualizaciones adicionales a ReliefF, haciéndola apropiada para la regresión. [ 5 ]

Aliviado-F

Se introdujo un enfoque de selección de vecinos determinista y un nuevo enfoque para el manejo de datos incompletos. [ 10 ]

Alivio iterativo

Método implementado para abordar el sesgo contra características no monótonas. Se introdujo el primer enfoque iterativo Relief. Por primera vez, los vecinos se determinaron de forma única mediante un umbral de radio y las instancias se ponderaron según su distancia a la instancia objetivo. [ 11 ]

I-RELIEV

Introdujo ponderación sigmoidal basada en la distancia a la instancia objetivo. [ 12 ] [ 13 ] Todos los pares de instancias (no solo un subconjunto definido de vecinos) contribuyeron a las actualizaciones de puntuación. Propuso una variante de aprendizaje en línea de Relief. Extendió el concepto iterativo de Relief. Introdujo actualizaciones de aprendizaje local entre iteraciones para una mejor convergencia. [ 14 ]

TuRF (también conocido como Tuned ReliefF)

Se buscó específicamente abordar el ruido en grandes espacios de características mediante la eliminación recursiva de características y la aplicación iterativa de ReliefF. [ 15 ]

Alivio de enfriamiento evaporativoF

De manera similar, se busca abordar el ruido en grandes espacios de características. Se utilizó una eliminación iterativa "evaporativa" de las características de menor calidad utilizando puntuaciones ReliefF en asociación con información mutua . [ 16 ]

EReliefF (también conocido como Alivio Extendido)

Abordar problemas relacionados con datos incompletos y de múltiples clases. [ 17 ]

VLSReliefF (también conocido como Very Large Scale ReliefF)

Mejora drásticamente la eficiencia de detección de interacciones de características bidireccionales en espacios de características muy grandes al puntuar subconjuntos de características aleatorias en lugar de todo el espacio de características. [ 18 ]

ReliefMSS

Se introdujo el cálculo de pesos de características en relación con la 'diferencia' promedio de características entre pares de instancias. [ 19 ]

NAVEGAR

SURF identifica los vecinos más cercanos (tanto aciertos como errores) basándose en un umbral de distancia desde la instancia objetivo definido por la distancia promedio entre todos los pares de instancias en los datos de entrenamiento. [ 20 ] Los resultados sugieren una mayor potencia para detectar interacciones epistáticas de dos vías en comparación con ReliefF.

SURF* (también conocido como SURFStar)

SURF* [ 21 ] extiende el algoritmo SURF [ 20 ] para utilizar no solo vecinos 'cercanos' en las actualizaciones de puntuación, sino también instancias 'lejanas', empleando actualizaciones de puntuación invertidas para pares de instancias 'lejanas'. Los resultados sugieren una mayor capacidad para detectar interacciones epistáticas de dos vías que SURF, pero una incapacidad para detectar efectos principales simples (es decir, asociaciones univariadas). [ 22 ]

SWRF*

SWRF* extiende el algoritmo SURF* adoptando ponderación sigmoide para tener en cuenta la distancia al umbral. También introdujo un marco modular para el desarrollo posterior de RBA llamado MoRF. [ 23 ]

MultiSURF* (también conocido como MultiSURFStar)

MultiSURF* [ 24 ] extiende el algoritmo SURF* [ 21 ] adaptando los límites de vecindad cercana/lejana en función del promedio y la desviación estándar de las distancias desde la instancia objetivo a todas las demás. MultiSURF* utiliza la desviación estándar para definir una zona muerta donde las instancias de "distancia media" no contribuyen a la puntuación. La evidencia sugiere que MultiSURF* funciona mejor en la detección de interacciones de características bidireccionales puras. [ 22 ]

ReliefSeq

Introduce un parámetro k adaptativo por características para detectar de forma más flexible los efectos univariados y los efectos de interacción. [ 25 ]

MultiSURF

MultiSURF [ 22 ] simplifica el algoritmo MultiSURF* [ 24 ] al preservar la zona de banda muerta y la determinación de vecindario centrada en la instancia objetivo, pero eliminando la puntuación de "lejos". La evidencia sugiere que MultiSURF es una opción completa, capaz de detectar interacciones de 2 y 3 vías, así como asociaciones univariadas simples. [ 22 ] También introdujo el paquete de software RBA llamado ReBATE que incluye implementaciones de (Relief, ReliefF, SURF, SURF*, MultiSURF*, MultiSURF y TuRF).

REMOVER

STIR [ 26 ] [ 27 ] reformula y ajusta ligeramente la fórmula original de Relief al incorporar la varianza muestral de las distancias al vecino más cercano en la estimación de la importancia de los atributos. Esta varianza permite calcular la significancia estadística de las características y ajustar las puntuaciones basadas en Relief para realizar pruebas múltiples. Actualmente, STIR admite variables de resultado binarias, pero pronto se extenderá a resultados continuos y multiestado.

Aplicaciones del RBA

Se han aplicado diferentes algoritmos basados ​​en riesgos a la selección de características en diversos ámbitos problemáticos.

Véase también

Referencias

  1. ↑ Kira, Kenji y Rendell, Larry (1992). El problema de la selección de características: métodos tradicionales y un nuevo algoritmo . Actas de AAAI-92.
  2. 1 2 Kira, Kenji y Rendell, Larry (1992) Un enfoque práctico para la selección de características , Actas del Noveno Taller Internacional sobre Aprendizaje Automático, págs. 249-256
  3. 1 2 Kononenko, Igor et al. Superando la miopía de los algoritmos de aprendizaje inductivo con RELIEFF (1997), Applied Intelligence, 7(1), p39-55
  4. 1 2 3 Kononenko, Igor (1994-04-06). "Estimación de atributos: Análisis y extensiones de RELIEF". Aprendizaje automático: ECML-94 . Notas de clase en ciencias de la computación. Vol.  784. Springer, Berlín, Heidelberg. págs. 171–182 . doi : 10.1007/3-540-57868-4_57 . ISBN  978-3-540-57868-0. S2CID 8190856 . 
  5. 1 2 Robnik-Šikonja, Marko y Kononenko, Igor (1997). Una adaptación de Relief para la estimación de atributos en regresión. Machine Learning: Proceedings of the Fourteenth International Conference (ICML'97) (p296-304)
  6. 1 2 3 Urbanowicz, Ryan J.; Meeker, Melissa; LaCava, William; Olson, Randal S.; Moore, Jason H. (2018). "Selección de características basada en el relieve: introducción y revisión" . Journal of Biomedical Informatics . 85 : 189–203 . arXiv : 1711.08421 . Bibcode : 2017arXiv171108421U . doi : 10.1016/j.jbi.2018.07.014 . PMC 6299836. PMID 30031057 .  
  7. ↑ Kononenko, Igor, Robnik-Sikonja, Marko (29 de octubre de 2007). Evaluación de la calidad de las características no miopes con (R)ReliefF . Chapman and Hall/CRC. págs. 169–192 . doi : 10.1201/9781584888796-9 . ISBN  978-0-429-15041-8.{{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )
  8. ↑ Moore, Jason H. (2015). "Análisis de epistasis mediante ReliefF". Epistasis . Métodos en biología molecular. Vol. 1253. Humana Press, Nueva York, NY. págs. 315–325 . doi : 10.1007/978-1-4939-2155-3_17 . ISBN   978-1-4939-2154-6. PMID 25403540 . 
  9. ↑ Todorov, Alexandre (2016-07-08). Una visión general del algoritmo RELIEF y sus avances . MIT Press. ISBN 978-0-262-03468-5.
  10. ↑ Kohavi, Ron; John, George H (1997-12-01). "Envoltorios para la selección de subconjuntos de características" . Inteligencia Artificial . 97 ( 1– 2): 273– 324. doi : 10.1016/S0004-3702(97)00043-X . ISSN 0004-3702 . 
  11. ↑ Draper, B.; Kaito, C.; Bins, J. (junio de 2003). "Alivio iterativo". Taller de la Conferencia de 2003 sobre Visión por Computadora y Reconocimiento de Patrones . Vol. 6. pág. 62. doi : 10.1109/CVPRW.2003.10065 . S2CID 17599624 .   
  12. ↑ Sun, Yijun; Li, Jian (25 de junio de 2006). "RELIEV iterativo para la ponderación de características". Actas de la 23.ª conferencia internacional sobre aprendizaje automático - ICML '06 . ACM. págs. 913–920 . CiteSeerX 10.1.1.387.7424 . doi : 10.1145/1143844.1143959 . ISBN   978-1-59593-383-6. S2CID 1102692 . 
  13. ↑ Sun, Y. (junio de 2007). "RELIEF iterativo para ponderación de características: algoritmos, teorías y aplicaciones". IEEE Transactions on Pattern Analysis and Machine Intelligence . 29 (6): 1035– 1051. doi : 10.1109/TPAMI.2007.1093 . ISSN 0162-8828 . PMID 17431301. S2CID 14087053 .   
  14. ↑ Sun, Y.; Todorovic, S.; Goodison, S. (septiembre de 2010). "Selección de características basada en aprendizaje local para el análisis de datos de alta dimensión" . IEEE Transactions on Pattern Analysis and Machine Intelligence . 32 (9): 1610– 1626. doi : 10.1109/TPAMI.2009.190 . ISSN 0162-8828 . PMC 3445441. PMID 20634556 .   
  15. ↑ Moore, Jason H.; White, Bill C. (11 de abril de 2007). "Ajuste de ReliefF para análisis genético a escala genómica". Computación evolutiva, aprendizaje automático y minería de datos en bioinformática . Notas de clase en ciencias de la computación. Vol. 4447. Springer, Berlín, Heidelberg. págs. 166–175 . doi : 10.1007/978-3-540-71783-6_16 . ISBN   978-3-540-71782-9.
  16. ↑ McKinney, BA; Reif, DM; White, BC; Crowe, JE; Moore, JH (2007-08-15). "Selección de características de enfriamiento evaporativo para datos genotípicos que involucran interacciones" . Bioinformatics . 23 ( 16): 2113– 2120. doi : 10.1093/bioinformatics/btm317 . ISSN 1367-4803 . PMC 3988427. PMID 17586549 .   
  17. ↑ Park, H.; Kwon, HC (agosto de 2007). «Algoritmos de alivio extendido en el filtrado de características basado en instancias». Sexta Conferencia Internacional sobre Procesamiento Avanzado del Lenguaje y Tecnología de la Información Web (ALPIT 2007) . págs. 123–128 . doi : 10.1109/ALPIT.2007.16 . ISBN  978-0-7695-2930-1. S2CID 15296546 . 
  18. ↑ Eppstein, MJ; Haake, P. (septiembre de 2008). "ReliefF a gran escala para el análisis de asociación de genoma completo". Simposio IEEE de 2008 sobre Inteligencia Computacional en Bioinformática y Biología Computacional . págs. 112–119 . doi : 10.1109/CIBCB.2008.4675767 . ISBN  978-1-4244-1778-0. S2CID 9296768 . 
  19. ↑ Chikhi, Salim; Benhammada, Sadek (2009-11-04). "ReliefMSS: una variación de un algoritmo de clasificación de características ReliefF". International Journal of Business Intelligence and Data Mining . 4 (3/4): 375. doi : 10.1504/ijbidm.2009.029085 . S2CID 15242788 . 
  20. 1 2 Greene, Casey S.; Penrod, Nadia M.; Kiralis, Jeff; Moore, Jason H. (2009-09-22). "Spatially Uniform ReliefF (SURF) for computationally-efficient filtering of gene-gene interactions" . BioData Mining . 2 (1): 5. doi : 10.1186/1756-0381-2-5 . ISSN 1756-0381 . PMC 2761303. PMID 19772641 .   
  21. 1 2 Greene, Casey S.; Himmelstein, Daniel S.; Kiralis, Jeff; Moore, Jason H. (2010-04-07). "Los extremos informativos: el uso de individuos tanto cercanos como lejanos puede mejorar los algoritmos de alivio en el dominio de la genética humana". Computación evolutiva, aprendizaje automático y minería de datos en bioinformática . Notas de clase en ciencias de la computación. Vol. 6023. Springer, Berlín, Heidelberg. págs. 182–193 . doi : 10.1007/978-3-642-12211-8_16 . ISBN   978-3-642-12210-1.
  22. 1 2 3 4 Urbanowicz, Ryan J.; Olson, Randal S.; Schmitt, Peter; Meeker, Melissa; Moore, Jason H. (2017-11-22). "Benchmarking Relief-Based Feature Selection Methods for Bioinformatics Data Mining". arXiv : 1711.08477 . Bibcode : 2017arXiv171108477U . PMID 30030120 . 
  23. ↑ Stokes, Matthew E.; Visweswaran, Shyam (2012-12-03). "Aplicación de un algoritmo Relief ponderado espacialmente para clasificar predictores genéticos de enfermedades" . BioData Mining . 5 (1): 20. doi : 10.1186/1756-0381-5-20 . ISSN 1756-0381 . PMC 3554553. PMID 23198930 .   
  24. 1 2 Granizo-Mackenzie, Delaney; Moore, Jason H. (2013-04-03). "Multiple Threshold Spatially Uniform ReliefF for the Genetic Analysis of Complex Human Diseases". Evolutionary Computation, Machine Learning and Data Mining in Bioinformatics . Lecture Notes in Computer Science. Vol. 7833. Springer, Berlín, Heidelberg. pp. 1–10 . doi : 10.1007/978-3-642-37189-9_1 . ISBN   978-3-642-37188-2.
  25. ↑ McKinney, Brett A.; White, Bill C.; Grill, Diane E.; Li, Peter W.; Kennedy, Richard B.; Poland, Gregory A.; Oberg, Ann L. (2013-12-10). "ReliefSeq: una herramienta de selección de características adaptativa de K vecinos más cercanos a nivel genético para encontrar interacciones gen-gen y efectos principales en datos de expresión génica de mRNA-Seq" . PLOS ONE . 8 (12) e81527. Bibcode : 2013PLoSO...881527M . doi : 10.1371/journal.pone.0081527 . ISSN 1932-6203 . PMC 3858248. PMID 24339943 .   
  26. ↑ Le, Trang; Urbanowicz, Ryan; Moore, Jason; McKinney, Brett (18 de septiembre de 2018). "Selección de características STatistical Inference Relief (STIR)" . Bioinformatics . 35 ( 8): 1358– 1365. doi : 10.1093/bioinformatics/bty788 . PMC 6477983. PMID 30239600 .  
  27. ↑ Le, Trang (1 de noviembre de 2018). "Póster STIR" . Figshare . doi : 10.6084/m9.figshare.7241417 . Recuperado el 24 de enero de 2019 .