Relief es un algoritmo desarrollado por Kira y Rendell en 1992 que adopta un enfoque de método de filtro para la selección de características que es notablemente sensible a las interacciones de características. [1] [2] Fue diseñado originalmente para su aplicación a problemas de clasificación binaria con características discretas o numéricas. Relief calcula una puntuación de función para cada función que luego se puede aplicar para clasificar y seleccionar las funciones de puntuación más alta para la selección de funciones. Alternativamente, estas puntuaciones se pueden aplicar como ponderaciones de características para guiar el modelado posterior. La puntuación de las características de relieve se basa en la identificación de las diferencias de valor de las características entre el vecino más cercanopares de instancias. Si se observa una diferencia de valor de característica en un par de instancias vecinas con la misma clase (un 'acierto'), la puntuación de la característica disminuye. Alternativamente, si se observa una diferencia de valor de característica en un par de instancias vecinas con diferentes valores de clase (un 'error'), la puntuación de característica aumenta. Desde entonces, el algoritmo Relief original ha inspirado una familia de algoritmos de selección de características (RBA) basados en Relief, 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 ruidosos, [4] (2) generalizar a problemas de varias clases [4] (3) generalizar a problemas de resultado numérico (es decir, regresión), [ 5] y (4) para 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 de Relief 'central', es decir, examinar las estrategias para la selección de vecinos y la ponderación de instancias, (2) mejorar la escalabilidad del algoritmo de Relief 'central' a espacios de características más grandes a través de enfoques iterativos, (3) métodos de adaptación flexible Relevación para diferentes tipos de datos y (4) mejora de la eficiencia de ejecución de Relevación. [6]
Sus puntos fuertes son que no dependen de la heurística, se ejecutan en tiempo polinomial de bajo orden, son tolerantes al ruido y robustos a las interacciones de características, además de ser aplicables para datos binarios o continuos; sin embargo, no discrimina entre características redundantes y el bajo número de instancias de entrenamiento engaña al algoritmo.
Algoritmo de alivio
Tome un conjunto de datos con n instancias de p características, que pertenecen a dos clases conocidas. Dentro del conjunto de datos, cada característica se debe escalar al intervalo [0 1] (los datos binarios deben permanecer como 0 y 1). El algoritmo se repetirá m veces. Comience con un vector de peso p -long (W) de ceros.
En cada iteración, tome el vector de características (X) que pertenece 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 de la misma clase más cercana se llama 'near-hit', y la instancia de clase diferente más cercana se llama 'near-miss'. Actualice el vector de peso de manera que
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 instancias cercanas de la otra clase, y aumenta en el caso inverso.
Después de m iteraciones, divida cada elemento del vector de peso por m . Este 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 τ mediante 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 lo suficientemente bueno como para hacer que la probabilidad de un error de Tipo I sea menor que α , aunque se establece que τ puede ser mucho más pequeño que eso.
El alivio también se describió como generalizable a la clasificación multinomial por descomposición en una serie de problemas binarios.
Algoritmo ReliefF
Kononenko y col. proponer una serie de actualizaciones para Relief. [3] En primer lugar, encuentran las instancias de cuasi impacto y cuasi accidente utilizando la norma de Manhattan (L1) en lugar de la norma euclidiana (L2) , aunque no se especifica la justificación. Además, encontraron que tomar las diferencias absolutas entre x i y cuasi impacto i , y x i y cuasi accidente i era suficiente al actualizar el vector de peso (en lugar del cuadrado de esas diferencias).
Estimación de probabilidad confiable
En lugar de repetir el algoritmo m veces, impleméntelo de manera exhaustiva (es decir, n veces, una vez para cada instancia) para n relativamente pequeños (hasta mil). Además, en lugar de encontrar el único acierto más cercano y el único error más cercano, lo que puede causar que los atributos redundantes y ruidosos afecten la selección de los vecinos más cercanos, ReliefF busca k aciertos y errores más cercanos y promedia su contribución a los pesos de cada característica. k se puede ajustar para cualquier problema individual.
Datos incompletos
En ReliefF, la contribución de los valores perdidos al peso de la característica se determina usando la probabilidad condicional de que dos valores sean iguales o diferentes, aproximados con frecuencias relativas del conjunto de datos. Esto se puede calcular si falta una o ambas características.
Problemas de varias clases
En lugar de utilizar la descomposición propuesta por Kira y Rendell de una clasificación multinomial en varios problemas binomiales, ReliefF busca k casi accidentes de cada clase diferente y promedia sus contribuciones para actualizar W, ponderado con la probabilidad previa de cada clase.
Otras extensiones / derivados de algoritmos basados en relieves
Los siguientes RBA están ordenados cronológicamente del más antiguo al 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 metas. Para obtener más información sobre los RBA, consulte los capítulos de estos libros [7] [8] [9] o este artículo de revisión más reciente. [6]
RRELIEFF
Robnik-Šikonja y Kononenko proponen más actualizaciones de ReliefF, haciéndolo apropiado 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. Introdujo el primer enfoque de relevo iterativo. 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 de destino. [11]
I-ALIVIO
Se introdujo la ponderación sigmoidea basada en la distancia desde la instancia objetivo. [12] [13] Todos los pares de instancias (no solo un subconjunto definido de vecinos) contribuyeron a las actualizaciones de puntuación. Se propuso una variante de aprendizaje en línea de Relief. Ampliación del concepto de relevo iterativo. Se introdujeron actualizaciones de aprendizaje local entre iteraciones para mejorar la convergencia. [14]
TuRF (también conocido como Tuned ReliefF)
Se buscó específicamente abordar el ruido en grandes espacios de funciones mediante la eliminación recursiva de funciones y la aplicación iterativa de ReliefF. [15]
Alivio de enfriamiento evaporativo F
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 de ReliefF en asociación con información mutua. [dieciséis]
EReliefF (también conocido como Extended ReliefF)
Abordar problemas relacionados con datos incompletos y de varias clases. [17]
VLSReliefF (también conocido como Very Large Scale ReliefF)
Mejora drásticamente la eficiencia de la detección de interacciones de características bidireccionales en espacios de características muy grandes al calificar subconjuntos de características aleatorios en lugar de todo el espacio de características. [18]
AlivioMSS
Se introdujo el cálculo de ponderaciones de características en relación con la diferencia de características promedio entre pares de instancias [19]
NAVEGAR
SURF identifica a los vecinos más cercanos (tanto aciertos como fallidos) en función de un umbral de distancia desde la instancia de destino definida por la distancia promedio entre todos los pares de instancias en los datos de entrenamiento. [20] Los resultados sugieren una potencia mejorada para detectar interacciones epistáticas bidireccionales sobre ReliefF.
SURF * (también conocido como SURFStar)
SURF * [21] extiende el algoritmo SURF [20] no solo a los vecinos "cercanos" utilizados en las actualizaciones de puntuación, sino también a las instancias "lejanas", sino también a las actualizaciones de puntuación invertidas para los "pares de instancias lejanas". Los resultados sugieren una potencia mejorada para detectar interacciones epistáticas bidireccionales sobre SURF, pero una incapacidad para detectar efectos principales simples (es decir, asociaciones univariadas). [22]
SWRF *
SWRF * amplía el algoritmo SURF * adoptando una ponderación sigmoidea para tener en cuenta la distancia desde el umbral. También introdujo un marco modular para seguir desarrollando RBA llamado MoRF. [23]
MultiSURF * (también conocido como MultiSURFStar)
MultiSURF * [24] amplía el algoritmo SURF * [21] adaptando los límites del vecindario cercano / lejano en función de la desviación promedio y estándar de las distancias desde la instancia de destino a todas las demás. MultiSURF * utiliza la desviación estándar para definir una zona de banda 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 puramente bidireccionales. [22]
ReliefSeq
Introduce un parámetro k adaptativo en función de las características para detectar de manera 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 vecindad centrada en la instancia de destino, pero eliminando la puntuación 'lejana'. La evidencia sugiere que MultiSURF es una opción completa, capaz de detectar interacciones bidireccionales y tridireccionales, así como asociaciones univariadas simples. [22] También presentó el paquete de software RBA llamado ReBATE que incluye implementaciones de (Relief, ReliefF, SURF, SURF *, MultiSURF *, MultiSURF y TuRF).
REVOLVER
STIR [26] [27] reformula y ajusta ligeramente la fórmula de Relief original incorporando la varianza de la muestra de las distancias del vecino más cercano en la estimación de la importancia del atributo. Esta varianza permite el cálculo de la significancia estadística de las características y el ajuste para múltiples pruebas de puntajes basados en Relief. Actualmente, STIR admite variables de resultado binarias, pero pronto se extenderá a resultados continuos y de varios estados.
Aplicaciones de RBA
Se han aplicado diferentes RBA a la selección de características en una variedad de dominios de problemas.
Ver también
Referencias
- ^ Kira, Kenji y Rendell, Larry (1992). El problema de la selección de características: métodos tradicionales y un nuevo algoritmo . Procedimientos AAAI-92.
- ↑ a b Kira, Kenji and Rendell, Larry (1992) A Practical Approach to Feature Selection , Proceedings of the Ninth International Workshop on Machine Learning, p249-256
- ^ a b Kononenko, Igor et al. Superando la miopía de los algoritmos de aprendizaje inductivo con RELIEFF (1997), Applied Intelligence, 7 (1), p39-55
- ↑ a b c Kononenko, Igor (6 de abril de 1994). "Estimación de atributos: Análisis y ampliaciones de RELIEF". Aprendizaje automático: ECML-94 . Apuntes de conferencias en Ciencias de la Computación. 784 . Springer, Berlín, Heidelberg. págs. 171-182. doi : 10.1007 / 3-540-57868-4_57 . ISBN 978-3540578680. Falta o vacío
|title=
( ayuda ) - ↑ a b Robnik-Šikonja, Marko y Kononenko, Igor (1997). Una adaptación de Relief para la estimación de atributos en regresión. Aprendizaje automático: actas de la decimocuarta conferencia internacional (ICML'97) (p296-304)
- ^ a b c Urbanowicz, Ryan J .; Meeker, Melissa; LaCava, William; Olson, Randal S .; Moore, Jason H. (2018). "Selección de características basadas en relieve: introducción y revisión" . Revista de Informática Biomédica . 85 : 189-203. arXiv : 1711.08421 . Código bibliográfico : 2017arXiv171108421U . doi : 10.1016 / j.jbi.2018.07.014 . PMC 6299836 . PMID 30031057 .
- ^ Kononenko, Igor, Robnik-Sikonja, Marko (29 de octubre de 2007). No miope Característica Evaluación de la Calidad con (R) ReliefF . págs. 169-192. doi : 10.1201 / 9781584888796-9 .
- ^ Moore, Jason H. (2015). "Análisis de la epistasis con ReliefF". Epistasis . Métodos en Biología Molecular. 1253 . Humana Press, Nueva York, NY. págs. 315–325. doi : 10.1007 / 978-1-4939-2155-3_17 . ISBN 9781493921546. PMID 25403540 .
- ^ Todorov, Alexandre (8 de julio de 2016). Una descripción general del algoritmo RELIEF y sus avances . Prensa del MIT. ISBN 9780262034685.
- ^ Kohavi, Ron; John, George H (1 de diciembre de 1997). "Envoltorios para 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 .
- ^ Draper, B .; Kaito, C .; Bins, J. (junio de 2003). "Alivio iterativo". 2003 Jornada sobre Visión por Computador y Taller de Reconocimiento de Patrones . 6 : 62. doi : 10.1109 / CVPRW.2003.10065 . S2CID 17599624 .
- ^ Sun, Yijun; Li, Jian (25 de junio de 2006). "RELIEVE iterativo para ponderación de características". Actas de la 23a 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-1595933836. S2CID 1102692 .
- ^ Sun, Y. (junio de 2007). "RELIEVE iterativo para la ponderación de características: algoritmos, teorías y aplicaciones". Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas . 29 (6): 1035-1051. doi : 10.1109 / TPAMI.2007.1093 . ISSN 0162-8828 . PMID 17431301 . S2CID 14087053 .
- ^ Sun, Y .; Todorovic, S .; Goodison, S. (septiembre de 2010). "Selección de características basadas en aprendizaje local para análisis de datos de alta dimensión" . Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas . 32 (9): 1610–1626. doi : 10.1109 / TPAMI.2009.190 . ISSN 0162-8828 . PMC 3445441 . PMID 20634556 .
- ^ Moore, Jason H .; White, Bill C. (11 de abril de 2007). Tuning ReliefF para análisis genético de todo el genoma . Computación evolutiva, aprendizaje automático y minería de datos en bioinformática . Apuntes de conferencias en Ciencias de la Computación. 4447 . Springer, Berlín, Heidelberg. págs. 166-175. doi : 10.1007 / 978-3-540-71783-6_16 . ISBN 9783540717829.
- ^ McKinney, BA; Reif, DM; White, BC; Crowe, JE; Moore, JH (15 de agosto de 2007). "Selección de características de enfriamiento evaporativo para datos genotípicos que involucran interacciones" . Bioinformática . 23 (16): 2113–2120. doi : 10.1093 / bioinformatics / btm317 . ISSN 1367-4803 . PMC 3988427 . PMID 17586549 .
- ^ 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 .
- ^ Eppstein, MJ; Haake, P. (septiembre de 2008). ReliefF a gran escala para el análisis de asociación de todo el genoma . Simposio IEEE 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 .
- ^ Chikhi, Salim; Benhammada, Sadek (4 de noviembre de 2009). "ReliefMSS: una variación de un algoritmo ReliefF de clasificación de características" . Revista internacional de inteligencia empresarial y minería de datos . 4 (3/4): 375. doi : 10.1504 / ijbidm.2009.029085 . S2CID 15242788 .
- ^ a b Greene, Casey S .; Penrod, Nadia M .; Kiralis, Jeff; Moore, Jason H. (22 de septiembre de 2009). "Spatially Uniform ReliefF (SURF) para filtrado computacionalmente eficiente de interacciones gen-gen" . Minería de Biodatos . 2 (1): 5. doi : 10.1186 / 1756-0381-2-5 . ISSN 1756-0381 . PMC 2761303 . PMID 19772641 .
- ^ a b Greene, Casey S .; Himmelstein, Daniel S .; Kiralis, Jeff; Moore, Jason H. (7 de abril de 2010). Los extremos informativos: el uso de individuos más cercanos y más 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 . Apuntes de conferencias en Ciencias de la Computación. 6023 . Springer, Berlín, Heidelberg. págs. 182-193. doi : 10.1007 / 978-3-642-12211-8_16 . ISBN 9783642122101.
- ^ a b c d Urbanowicz, Ryan J .; Olson, Randal S .; Schmitt, Peter; Meeker, Melissa; Moore, Jason H. (22 de noviembre de 2017). "Métodos de selección de características basadas en relieve de evaluación comparativa para la minería de datos bioinformáticos". arXiv : 1711.08477 . Código bibliográfico : 2017arXiv171108477U . PMID 30030120 .
- ^ Stokes, Matthew E .; Visweswaran, Shyam (3 de diciembre de 2012). "Aplicación de un algoritmo de alivio ponderado espacialmente para clasificar los predictores genéticos de la enfermedad" . Minería de Biodatos . 5 (1): 20. doi : 10.1186 / 1756-0381-5-20 . ISSN 1756-0381 . PMC 3554553 . PMID 23198930 .
- ^ a b Granizo-Mackenzie, Delaney; Moore, Jason H. (3 de abril de 2013). Alivio uniforme espacialmente de varios umbrales para el análisis genético de enfermedades humanas complejas . Computación evolutiva, aprendizaje automático y minería de datos en bioinformática . Apuntes de conferencias en Ciencias de la Computación. 7833 . Springer, Berlín, Heidelberg. págs. 1-10. doi : 10.1007 / 978-3-642-37189-9_1 . ISBN 9783642371882.
- ^ McKinney, Brett A .; White, Bill C .; Grill, Diane E .; Li, Peter W .; Kennedy, Richard B .; Polonia, Gregory A .; Oberg, Ann L. (10 de diciembre de 2013). "ReliefSeq: una herramienta de selección de características del vecino más cercano Adaptive-K gen-sabio para encontrar interacciones gen-gen y efectos principales en datos de expresión génica mRNA-Seq" . PLOS ONE . 8 (12): e81527. Código Bibliográfico : 2013PLoSO ... 881527M . doi : 10.1371 / journal.pone.0081527 . ISSN 1932-6203 . PMC 3858248 . PMID 24339943 .
- ^ Le, Trang; Urbanowicz, Ryan; Moore, Jason; McKinney, Brett (18 de septiembre de 2018). "Selección de función de alivio de inferencia estadística (STIR)" . Bioinformática . 35 (8): 1358-1365. doi : 10.1093 / bioinformatics / bty788 . PMC 6477983 . PMID 30239600 .
- ^ Le, Trang (1 de noviembre de 2018). "Póster STIR" . Figshare . doi : 10.6084 / m9.figshare.7241417 . Consultado el 24 de enero de 2019 .