Técnicas cuantitativas para la extracción de términos en ...T´ecnicas cuantitativas para la...
-
Upload
vuongtuyen -
Category
Documents
-
view
222 -
download
1
Transcript of Técnicas cuantitativas para la extracción de términos en ...T´ecnicas cuantitativas para la...
Tecnicas cuantitativas para laextraccion de terminos en un corpus
Jordi Porta Zamorano
Escuela PolitecnicaUniversidad Autonoma de Madrid
12 de julio de 2006
Definicion de termino
Norma ISO 1087 (1990):
“La designacion de un concepto definido en un lenguajeespecializado mediante una expresion linguıstica. Nota: Un terminopuede estar compuesto por una sola palabra o por dos o mas.”
Problemas (para la extraccion automatica):
I no proporciona criterios operacionales
I se necesita conocimiento de mundo y de dominio
Solucion:combinar su estructura (morfologica, sintactica, . . . ) con susdistribuciones estadısticas en distintas dimensiones:
I unidad (unithood)
I pertenencia a un dominio (domainhood)
I uso especializado (specialized usage)
Contenidos
I descripcion de los materiales usados
I metodologıa para la evaluacion de un sistema de extraccionI medidas para la extraccion en distintas dimensiones:
I unidad (unithood)I pertenencia a un dominio (domainhood)I uso especializado (specialized usage)
I combinacion de medidas con aprendizaje automatico
I evaluacion final
Descripcion del corpus de trabajoy
otros materiales empleados
Corpus especializado
I Journal of Computational Linguistics (JCL)1980–2003
I proviene del archivo digital ACL Anthology(http://acl.ldc.upenn.edu)
I 1.179 documentos: artıculos, resenas, editorialesy anuncios
I 7.949.153 palabras
Anotacion del JCL (1/2)
I PDF → OCR → texto → preprocesamiento → anotacion
I anotador TnT con etiquetario Penn Treebank(http://www.cis.upenn.edu/∼treebank/)
I Thorsten Brants. TnT – A Statistical Part-of-Speech Tagger.Proceedings of the Sixth Applied Natural LanguageProcessing, 2000
I preprocesamiento:I segmentacion de palabrasI reconstruccion heurıstica de palabras partidas a final de lınea
(segun frecuencia con y sin “-”)I conversion heurıstica a minusculas de palabras a principio de
oracion (segun frecuencia con distintas cajas tipograficas)
Anotacion del JCL (2/2)
back-of-indices or for document-collection navigation, and also for compilingcontrolled vocabulary terminologies such as are used in, for example, medical cod-ing applications. Several papers address this topic. Most generically, a review paperby M. Teresa Cabre CastellvI, Rosa Estopa Bagot, and Jordi Vivaldi Palatresi reviewstwelve current term extraction systems, including well-known systems such as LEX-
for IN
compiling VBG
controlled VBN
vocabulary JJ
terminologies NNS
such JJ
as IN
are VBP
used VBN
in IN
, ,
for IN
example NN
, ,
medical JJ
coding JJ
applications NNS
. .
several JJ
papers NNS
address VB
this DT
topic NN
. .
most RBS
generically RB
, ,
a DT
review NN
paper NN
by IN
M NNP
. .
Teresa NNP
Cabre NNP
CastellvI NNP
, ,
Rosa NNP
Estopa NNP
Bagot NNP
, ,
and CC
Jordi NNP
Vivaldi NNP
Palatresi NNP
reviews VBZ
twelve CD
current JJ
term NN
extraction NN
systems NNS
Corpus de referencia
I British National Corpus (BNC)I 100 millones de palabras de ingles britanicoI sincronicoI diseno equilibradoI 90 % de material escrito y 10 % oralI anotadoI http://www.natcorp.ox.ac.uk
I reanotado con TnT
Estructura de los terminos
I designaciones =⇒ SSNN
I . . . | JJ NN | JJ NN IN NN | JJ NN IN NNP | JJ NN IN NNS| JJ NN JJ NN | JJ NN JJ NNP | JJ NN JJ NNS | JJ NNJJR NN | JJ NN NN | JJ NN NN NN | JJ NN NN NNP | JJNN NN NNS | JJ NN NNP | JJ NN NNP NN | JJ NN NNPNNP | JJ NN NNP NNS | JJ NN NNS | JJ NN NNS NN | JJNN NNS NNP | JJ NN NNS NNS | JJ NNP | JJ NNP INNNP | . . .
Distribucion de palabras en un corpus: La Ley de Zipf
I si ordenamos las palabras de un texto de la mas comun a lamas rara, la frecuencia decrece exponencialmente
I la frecuencia de una palabra (f ) y su posicion en el ranking de(r) estan relacionadas:
f =k
r
k ≈ 1 (depende del corpus) 1
10
100
1000
10000
100000
1e+06
1 10 100 1000 10000lo
g(fre
c)
log(rank)I es una caracterıstica del lenguaje humanoI George K. Zipf. Human Behavior and the Principle of Least
Effort. Addison-Wesley, 1949I Ramon Ferrer i Cancho. Language: universals, principles and
origins. PhD thesis, Universitat Politecnica de Catalunya,Barcelona, 2003
Origenes de la Recuperacion de la Informacion
I los terminos ındice o las palabras clave son elementos concontenido que permiten recuperar documentos relevantes
I Luhn: las palabras interesantes para la indexacion son aquellasque f · r ≈ k
I Luhn establece dos umbrales dentro de los cuales las palabrasahı contenidas contribuirıan al contenido del documento
Hans Peter Luhn. A Statistical Approach to Mechanized Encodingand Searching of Literary Information. IBM Journal of Researchand Development, 2(2), 1958
Evaluacion de un sistema de extraccion de terminos
Evaluacion de un sistema de extraccion de terminos
Evaluar la actuacion de un sistema nos interesa para:
I valorarlo
I mejorarlo
I compararlo
I cambiarlo
Para una correcta evaluacion se necesitaran a priori ejemplos de:
I terminos
I no terminos
Ejemplos de terminos y no terminos
I fuentes:
I glosario de Robert Dale, H. L. Somers, andHermann Moisl, editors. Handbook of NaturalLanguage Processing: Techniques andApplications for the Processing of Languageas Text. 2000
I ındice de Christopher D. Manning andHinrich Schutze. Foundations of StatisticalNatural Language Processing. 1999
I muestreo aleatorio del JCL: palabras ybigramas clasificados manualmente
Simples Complejos Total
Terminos 296 447 743No terminos 124 581 705
Total 420 1028 1448
Predicciones de un sistema: matriz de confusionLa comparacion de las predicciones del sistema con las clases realesda lugar a distintos grupos:
I verdaderos positivos (VP):terminos correctamente reconocidos por el sistema
I falsos negativos (FN):terminos que el sistema dice que no lo son
I falsos positivos (FP):no terminos que el sistema dice que son terminos
I verdaderos negativos (VN):no terminos correctamente reconocidos como tales
se disponen en una matriz de confusion:
Clase predicha
Clase real Termino No termino
Termino verdaderos positivos falsos negativos
No termino falsos positivos verdaderos negativos
Tasas de acierto y error
Tasa de acierto:porcentaje de ejemplos bien clasificados
tasa de acierto =VP + VN
N
Tasa de error:porcentaje de ejemplos mal clasificados
tasa de error =FP + FN
N
(N = VP + FN + FP + VN)
Incorporacion de costes y beneficios
I los fallos pueden tener costes
I los aciertos pueden tener beneficios
I se expresan en una matriz de costes y beneficios
Clase predicha
Clase real Termino No termino
Termino BVP CFN
No termino CFP BVN
I su combinacion con la matriz de confusion darıa las siguientesevaluaciones:
beneficio = VP · BVP + VN · BVN
coste = FP · CFP + FN · CFN
Cobertura y precision (RI) (1/2)
Cobertura (recall):
¿estan todos los que son?
cobertura =terminos correctamente reconocidos
total de terminos reales=
VP
VP + FN
Precision:¿son todos los que estan?
precision =terminos correctamente reconocidos
total de terminos predichos=
VP
VP + FP
F -measure:
F =2 · cobertura · precision
cobertura + precision
Cobertura y precision (RI) (2/2)
La cobertura y la precision mantienen, por lo general, una relacioninversa:
I aumenta la cobertura =⇒ disminuye la precisionI se reconocen mas terminosI y cosas que no lo son
I aumenta la precision =⇒ disminuye la coberturaI disminuyen los falsos terminosI dejandose de reconocer algunos verdaderos
I cobertura total =⇒ precision nulaI todos son terminosI incluso los que no lo son
Sensibilidad y especificidad
I originadas en la Teorıa de la Deteccion de la Senal
I usados en diagnostico medico (70s) y Aprendizaje Automatico(90s)
Sensibilidad (tasa de verdaderos positivos) (= cobertura):
cuantos terminos son reconocidos como tales
sensibilidad =terminos correctamente reconocidos
total de terminos reales=
VP
VP + FN
Especificidad (1− tasa de falsas alarmas):
cuantos no terminos se han clasificado como tales
especificidad =no term. correct. recon.
total de no term. reales=
VN
VN + FP= 1− FP
FP + VN
Silencio y ruido
Ruido (= 1− precision):
ruido =falsos terminos
terminos predichos=
FP
VP + FP
Silencio (= 1− cobertura):
silencio =terminos no reconocidos
terminos reales=
FN
VP + FN
I usados en extraccion de terminologıaI estan relacionados de manera inversa
I disminuir el silencio provoca ruidoI disminuir el ruido aumenta el silencio
Curvas ROC (Receiver Operating Characteristic)
I desarrolladas dentro de la Teorıa de la Deteccion de la SenalI permite evaluar y comparar clasif. con independencia de:
I la distribucion de las clases (proporcion terms./no terms.)I el coste de los errores
I y: tasa VP = VP/(VP +FN)I x: tasa FP = FP/(FP +VN)
0
0.2
0.4
0.6
0.8
1
0 0.2 0.4 0.6 0.8 1
TP ra
te
FP rate
M1
M3
M4
M6
M2
M5
Analisis de curvas ROC
I los clasificadores mas proximos a la esquina superior izquierdase consideran buenos clasificadores:
I tasa VP elevadaI tasa FP baja
I los clasificadores situados en la envolvente convexa (M1, M3,M4 y M6) son optimos para alguna relacion coste-beneficio,no los que quedan por debajo de esta curva (M2 y M5)
I el clasificador que mejor opera es aquel que estando situadosobre la envolvente convexa tiene como tangente una rectacon pendiente:
numero de no terminos
numero de terminos· CFP
CFN
I 45◦ =⇒ M3I 75◦ =⇒ M1I 25◦ =⇒ M4
Rankers
I algunos clasificadores asignan un valor numerico
I es necesario un parametro (umbral) para determinar la clase
I ejemplo: ranker basado en la frecuencia:
Frec. VP FP VP-rate FP-rate
19157 1 0 0,003 010333 2 0 0,007 08609 3 0 0,010 0
. . .814 69 11 0,251 0,096812 69 12 0,251 0,105809 70 12 0,255 0,105790 70 13 0,255 0,114766 71 13 0,259 0,114
. . .11 269 110 0,981 0,96410 272 114 0,992 13 273 114 0,996 12 274 114 1 1
Analisis de curva ROC para rankers: la AUC
I punto de operacion optimo: con la tangenteI el area bajo la curva ROC (AUCs) permite:
I valorar rankers
regular 0,50–0,75bueno 0,75–0,92muy bueno 0,92–0,97excelente 0,97–1
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
1
0 0.2 0.4 0.6 0.8 1
TP ra
te
FP rate
AUC = 0,677I comparar rankers
I tambien puede usarse otro tipo de curvas:I curvas de cobertura-precisionI curvas liftI curvas de coste
Uso especializado
Uso especializado
Hipotesis de trabajo:
las palabras y expresiones relativamente mas frecuentes en textosde especialidad seran probablemente parte del vocabularioespecıfico de ese corpus
Comparacion entre frecuencias relativas
I ratio entre frecuencias relativas
RFR(w) =fG (w)
fS(w)
Fred J. Damerau. Generating and EvaluatingDomain-Oriented Multi-Word Terms from Text. InformationProcessing & Management, 29(4), 1993
I diferencia entre frecuencias relativas
DFR(w) = fS(w)− fG (w)
I ındice de Yule
Y (w) =fS(w)− fG (w)
fG (w) + fS(w)
George U. Yule. Statistical Study of Literary Vocabulary.Cambridge University Press, 1944
Interpretacion de RFR (1/2): zonas de un grafico RFR
0
0.2
0.4
0.6
0.8
1
0 0.2 0.4 0.6 0.8 1
Frec
. en
A
Frec. en B
A
B
Interpretacion de RFR (2/2): terminos y no terminossimples
0
2e-05
4e-05
6e-05
8e-05
0.0001
0 2e-05 4e-05 6e-05 8e-05 0.0001
Frec
. en
el J
CL
Frec. en el BNC
tØrminosno tØrminos
Contrastes de hipotesis
I se formula una hipotesis nula (H0) que mantiene que ladiferencia entre O y E es debida al azar. Implıcitamente existeuna hipotesis alternativa (H1).
I se elige un estadıstico con el que calcular una cantidad Cα
denominada el valor crıtico. Con ese valor se decide si serechaza o no H0. La eleccion del estadıstico del test dependede la distribucion estadıstica del fenomeno y del tipo dehipotesis formulada.
I se calcula el nivel de significacion del test, la probabilidad derechazar erroneamente H0, consultando las tablas de ladistribucion de referencia del test con el valor Cα.
I si el nivel de significacion no es lo suficientemente alto (lohabitual es un 10, 5 o 1 % dependiendo de la exigencia delresultado) se rechaza H0 a favor de H1.
Contrastes: el test t de Student
I version para contrastar las medias de dos muestras paradeterminar si se trata de la misma poblacion
I las variables que se miden deben seguir distribucionesnormales (no es el caso)
t(w) ≈ fS(w)− fG (w)√fS(w)/NS + fG (w)/NG
Contrastes: el test de χ2
I es un test de independencia estadıstica
I no asume normalidad
I apropiado cuando las frecuencias son altas
X 2 =∑i ,j
(Oij − Eij)2
Eij, Eij =
∑j Oij∑i Ni
aplicacion: Adam Kilgarriff and Tony Rose Measures for corpussimilarity and homogeneity Proceedings of the 3rd Conference onEmpirical Methods in Natural Language Processing. 1999
Contrastes: la ratio de verosimilitud (G 2)
I χ2 no es fiable cuando para frecuencias pequenas
I sobreestima palabras de alta frecuencia cuando se comparancorpus de tamanos distintos
G 2 = 2∑ij
Oij · lnOij
Eij, Eij =
Nj ·∑
k Oik∑k Nk
Ted Dunning. Accurate Methods for the Statistics of Surpriseand Coincidence. Computational Linguistics, 19(1), 1993
I en Robert C Moore. On Log-likelihood-Ratios and theSignificance of Rare Events. Proceedings of the Conference onEmpirical Methods in Natural Language Processing, 2004 secuestiona la superioridad absoluta del test
Evaluacion de medidas para la extraccion de terminossimples basadas en la comparacion de frecuencias
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
0 0.2 0.4 0.6 0.8 1
TP ra
te
FP rate
YULERFR
G2X2
TTF
Metodo AUC
RFR 0,874Y 0,874t 0,825
G 2 0,785X 2 0,737f 0,600
(a) Curvas ROC (b) AUCs
RFR con el BNC y en varios de sus subcorpus para laextraccion de terminos simples del JCL: curvas ROC
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
0 0.2 0.4 0.6 0.8 1
TP ra
te
FP rate
BNCdomain=W_leisure
domain=W_artsdomain=W_belief_thought
domain=W_soc_sciencedomain=W_imaginative
domain=W_app_sciencedomain=W_world_affairsdomain=W_nat_science
domain=W_commerce
RFR con el BNC y en varios de sus subcorpus para laextraccion de terminos simples del JCL: AUCs
Dominio AUC Palabras
BNC 0,874 100.615.847W arts 0,870 7.254.473
W world affairs 0,868 17.647.749W commerce 0,867 7.478.464W imaginative 0,861 21.829.929W soc science 0,859 15.240.118
W leisure 0,855 11.050.014W app science 0,845 7.745.784
W belief thought 0,844 3.357.964W nat science 0,838 4.050.941
Pertenencia a un dominio
Pertenencia a un dominio
Hipotesis de trabajo:
I algo que aparecen en todos los documentos no parece tenermucha probabilidad de ser termino
I si el corpus contiene varios dominios es esperable que losterminos aparezcan en varios documentos
I las medidas presentadas estan tomadas del campo de la RI
La frecuencia inversa de documento (IDF)
I Karen Sparck Jones A statistical interpretation of termspecificity and its application in retrieval Journal ofDocumentation, 28, 1972
IDF(w) = − log2DF(w)
D
I TF*IDF: Gerald Salton Automatic Text Processing: TheTransformation, Analysis and Retrieval of Information byComputer Addison-Wesley, 1989
La frecuencia inversa de documento residual (RIDF)
I la ley de Zipf describe la frecs. de palabras en un corpus
I la distribucion de Poisson ajusta bien la distribucion de laspalabras sin contenido (predice su numero de ocurrencias enfuncion la longitud del documento)
IDF(w) = log2 1− eTF(w)
D
RIDF(w) = IDF(w)− IDF(w)
Kenneth W. Church and William Gale Inverse DocumentFrequency (IDF): A Measure of Deviation from PoissonProceedings of the Third Workshop on Very Large Corpora. 1995
Evaluacion de medidas para la extraccion de palabras ybigramas
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
0 0.2 0.4 0.6 0.8 1
TP ra
te
FP rate
fIDF
RIDFTF*IDF
Medida AUC
RIDF 0,856TF*IDF 0,731
f 0,695IDF 0,463
(a) Curvas ROC (b) AUCs
Unidad
Unidad
Hipotesis de trabajo:
I muchos terminos son complejos
I dichos terminos son colocaciones en un corpus de especialidad
I se pueden usar todas las tecnicas de extraccion de asoc. lexicas
I problemas: pueden mostrar variacion formal o discontinuidad
I solo nos ocuparemos de bigramas
Evert, Stefan, The Statistics of Word Cooccurrences: Word Pairsand Collocations, PhD thesis, University of Stuttgart. 2004http://www.collocations.de
Contrastes de hipotesis
I hasta que punto la probabilidad de coocurrencia de dospalabras es superior a la esperada cuando esas dos palabrasson independientes y forman una combinacion libre
I H0: w1w2 son combinacion libre
I bajo H0 la probabilidad de coocurrencia es:
Pr(w1w2) = Pr(w1) · Pr(w2)
I el modelo es tachado de simple y empıricamente inadecuado
Contrastes
I el test t de Studentversion para un test de independencia
t =Pr(w1w2)− Pr(w1) · Pr(w2)√
Pr(w1w2)N
Church, Kenneth W. and Gale, William and Hanks, Patrickand Hindle, Donald Using statistics in lexical analysis. LexicalAcquisition: Using On-line Resources to Build a Lexicon, 1991
I el test de χ2
la misma formulacion de (X 2) se usa como medida deasociacion lexica en las mismas condiciones
I la ratio de verosimilitud (G 2)
G2 = O11 ln O11 + O12 ln O12 + O21 ln O21 + O22 ln O22 + N ln N− (O11 + O21) ln(O11 + O21)− (O11 + O12) ln(O11 + O12)− (O21 + O22) ln(O21 + O22)− (O22 + O12) ln(O22 + O12)
Informacion mutua (MI)
I fundamentada en la Teorıa de la Informacion
I usada para calcular el grado de asociacion lexica
I Kenneth W. Church and Patrick Hanks. Word AssociationNorms, Mutual Information and Lexicography. ComputationalLinguistics 16(1). 1990.
MI(w1w2) = − log2Pr(w1w2)
Pr(w1) · Pr(w2)
I interpretacion:I MI > 0: asociacion interesanteI MI = 0: asociacion poco interesanteI MI < 0: combinacion libre
I problemas: sobreestimacion de bigramas con baja frecuencia
I soluciones: corrigir este sesgo heurısticamente
Heurısticas basadas en la MI
I informacion mutua al cuadrado
MI2(w1w2) = − log2Pr(w1w2)
2
Pr(w1) · Pr(w2)
I informacion mutua
MI3(w1w2) = − log2Pr(w1w2)
3
Pr(w1) · Pr(w2)
Beatrice Daille, Eric Gaussier, and Jean Marc Lange. AnEvaluation of Statistical Scores for Word Association.J. Ginzburg, Z. Khasidashvili, C. Vogel, J. J. Levy, andE. Vallduvı, editors, The Tbilisi Symposium on Logic,Language and Computation: Selected Papers, 1998.
Extensiones de la MI a n-gramas
I problemas: la MI es que solo es aplicable a bigramasI soluciones:
I informacion mutua generalizada
GMI(t) =Pr(aφb) · Pr(φ)
Pr(aφ) · Pr(φb)
Mikio Yamamoto and Kenneth W. Church. Using Suffix Arraysto Compute Term Frequency and Document Frequency for AllSubstrings in a Corpus. Computational Linguistics, 27(1), 2001
I entropıa contextualI C-value y NC-value: Katerina Frantzi, Sophia Ananiadou and
Hideki Mima. Automatic recognition of multi-word terms: theC-value/NC-value method. Journal on Digital Libraries, 3(2),2000
Medidas asociativas para la extraccion de bigramasterminologicos
0
0.2
0.4
0.6
0.8
1
0 0.2 0.4 0.6 0.8 1
TP ra
te
FP rate
fMI
MI2T
G2X2
Medida AUC
MI2 0,767−G 2 0,753MI 0,741t 0,700f 0,672
X 2 0,618
(a) Curvas ROC (b) AUCs
Combinacion de medidas
Combinacion de medidas
I las dimensiones vistas no parecen estar correlacionadas
I existen medidas capaces de extraer terminos aun con errores
I casi todas funcionan mejor que la frecuencia
I se pueden combinar con tecnicas de reconocimiento depatrones o con algoritmos de aprendizaje automatico
I el modelo obtenido servira para extraer nuevos terminos
Ejemplos y atributos usados para la construccion declasificadores
todos los algoritmos usados son supervisados y necesitan deejemplos previamente clasificados
n-grama POS n f MI2 RIDF RFR clasedifferent areas JJ NNS 2 1,509 −14,55 −0,007 0,517 −
motion NN 1 11,071 - 0,678 0,263 −structural descriptions JJ NNS 2 5,913 −9,825 0,825 1514,770 +
measures NNS 1 56,113 - 1,279 0,955 +other node JJ NN 2 1,635 −17,357 0,885 118,341 −
special type JJ NN 2 1,383 −15,666 −0,006 3,244 −exhaustive search JJ NN 2 1,761 −9,856 0,476 72,027 +
structural complexity JJ NN 2 1,635 −12,947 0,692 28,957 +syntax NN 1 236,533 - 0,772 48,146 +
epenthesis NN 1 2,516 - 1,725 84,019 +overgeneration NN 1 5,032 - 1,210 171,180 +
classification problem NN NN 2 1,887 −14,728 0,575 9478815,497 +nominalization NN 1 8,681 - 1,607 103,294 +
different features JJ NNS 2 2,516 −15,467 −0,012 15,993 −appropriate type JJ NN 2 2,138 −14,515 0,170 24,415 +
explanation NN 1 110,843 - 1,334 2,440 +belief NN 1 132,987 - 2,257 2,713 +
complexity NN 1 163,686 - 1,082 9,695 +
Clasificadores 1/6
IBk (k Instance-Based Classifier):
I usa una funcion de similitud entre ejemplos
I asigna la clase predominante de los k vecinos mas similares
David W. Aha, Dennis Kibler, y Marc K. Albert. Instance-basedlearning algorithms. Machine Learning, 6, 1991
Clasificadores 2/6
J48 (C4.5):
I genera arboles de decision
I ejemplo:
ridf <= 0.456951| rfr <= 21.748107: n (458.0/23.0)| rfr > 21.748107| | ridf > 0.099599| | | mi2 <= -15.2969| | | | rfr > 91.929478| | | | | rfr <= 493.150004: y (5.0/1.0)| | | | | rfr > 493.150004: n (8.0/1.0)| | | | rfr <= 91.929478: n (13.0)...
J. Ross Quinlan. C4.5: Programs for Machine Learning. MorganKaufmann, 1993.
Clasificadores 3/6
PART:
I genera listas de decision a partir de C4.5
I ejemplo:
ridf <= 0.456951 AND rfr <= 21.748107 AND n > 1: n (421.0/18.0)rfr > 2.018956 AND ridf > 0.644812 AND f > 1.88723AND ridf > 0.898164 AND rfr > 5.451567: y (353.0/16.0)
Eibe Frank y Ian H. Witten. Generating Accurate Rule SetsWithout Global Optimization. Proceedings of the FifteenthInternational Conference on Machine Learning, 1998
Clasificadores 4/6
Bagging:
I metametodo de aprendizaje
I cada clasificador vota
I asigna la clase mas votada
Leo Breiman. Bagging predictors. Machine Learning, 23(2), 1996
Clasificadores 5/6
AdaBoost:
I metametodo de aprendizaje
I voto de cada clasificador ponderado segun el acierto estimadodurante el aprendizaje
Robert E. Schapire. Theoretical views of boosting and applications.Tenth International Conference on Algorithmic Learning Theory,1999
Clasificadores 6/6
Naıve Bayes:
I usa el teorema de Bayes:
Pr(H|E ) =Pr(E |H) · Pr(H)
Pr(E )
I asigna la clase mas verosımil en funcion de los valores de susatributos
I base para la comparacion de otros metodos de aprendizaje
I supone independencia entre atributos
Richard O. Duda, Peter E. Hart, y David G. Stork. PatternClassification. Wiley Interscience, 2 Ed, 2000
Evaluacion: error de resustitucion
I error medido sobre el conjunto de entrenamiento
I acostumbra a ser demasiado optimista
I se pueden detectar errores en los conjuntos de entrenamiento
Matriz de confusion % %Metodo VP VN FP FN Acierto Error
IB5 628 583 121 86 85,40 14,59J48 658 604 100 56 88,99 11,00
AdaBoost 641 537 167 73 83,07 16,92Bagging 662 613 91 52 89,91 10,08
Naıve Bayes 338 646 376 58 69,39 30,60PART 637 612 92 77 88,08 11,91
Evaluacion: validacion cruzada
I hold-out:I reservar una parte para test y el resto para entrenarI factible cuando se tienen muchos datos
I validacion cruzada:I los datos se dividen m veces para hacer hold-out:
I una particion se usa para entrenarI la otra se usa para test
I ejemplo m = 3:
I es estratificada cuando las particiones conservan lasdistribuciones de las clases
I validacion estandar: 10 stratified 10-fold cross-validation
Error con validaciones cruzadas y espacio ROC con losclasificadores
Matriz de confusion % Acierto Cobertura Ruido TP-rateMetodo VP VN FP FN / Error / Precision / Silencio FP-rate
IB5 61,50 52,81 17,59 9,90 80,61/19,39 0,86/0,78 0,22/0,14 0,86/0,25J48 63,04 57,25 13,15 8,36 84,83/15,17 0,88/0,83 0,17/0,12 0,88/0,19
AdaBoost 59,81 56,49 13,91 11,59 82,02/17,98 0,84/0,81 0,19/0,16 0,84/0,20Bagging 63,07 58,86 11,54 8,33 85,99/14,01 0,88/0,85 0,15/0,12 0,88/0,16
Naıve Bayes 33,69 64,16 6,21 37,71 69,03/30,97 0,47/0,85 0,15/0,53 0,47/0,09PART 63,14 56,52 13,88 8,26 84,39/15,61 0,88/0,82 0,18/0,12 0,88/0,20
0
0.2
0.4
0.6
0.8
1
0 0.2 0.4 0.6 0.8 1
TP ra
te
FP rate
IB5J48
BoostBagg
Bayes
PART
Clasificador final
la validacion nos sirve para elegir el modelo del clasificador:
I se estiman sus parametros con todos los ejemplos disponibles
I se usara para clasificar el resto de ejemplos del corpusI se puede hacer bootstrapping:
I especialistas validan/corrigen los nuevos ejemplos clasificadosI se incorporan al conjunto de entrenamientoI se vuelve al primer punto