Arbolesdedecisi
onAplicacionesdeCienciasdelaComputacionHugoAlatrista-SalasPUCP,[email protected]://hugo.alatristasalas.free.fr/4demayode2015InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangeAgenda1InformaciongeneralAcercadel
cursoMotivacion2ArbolesdedecisionkNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclase3ArbolesdedecisionenWekayOrangeWEKAOrangePUCP,GRPIAALabs.
Arbolesdedecision 2 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangeAcercadel
cursoMotivacionAgenda1InformaciongeneralAcercadel
cursoMotivacion2ArbolesdedecisionkNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclase3ArbolesdedecisionenWekayOrangeWEKAOrangePUCP,GRPIAALabs.
Arbolesdedecision 3 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangeAcercadel
cursoMotivacionOrganizaci
ondelcursoTeora:3horassemanales(losmiercolesde10h00a13h00)Laboratorio:2horassemanales(losmiercolesde15h00a17h00)Dosobjetivosenestapartedelcurso:ConocerunadelastecnicasdeaprendizajesupervisadollamadoArbolesdedecisionVerunpoquitodeWekayOrangeEstecursoestabasadoenloscursosde:Cursodeanalisisdedatos-UniversidaddeParis1RiccoRakotomalala-UniversidaddeLyon2CursosobrearbolesdedecisiondeFrancoisParadis,entreotrosAlgunaspalabrasestaneninglesparapreservarelsentidodelapalabraPUCP,GRPIAALabs.
Arbolesdedecision 4 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangeAcercadel
cursoMotivacionMotivaci
onPorciertosdominiosdeaplicacion,esesencialproducirprediccionescomprensiblesparaelutilizadorEnlosmetodosclasicos(k-means,jerarquico,perceptron,etc.)lainformacionpuedeperderseenlaclasicacionPUCP,GRPIAALabs.
Arbolesdedecision 5 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangeAcercadel
cursoMotivacionEjemploDecidirsiunpacienteestaenfermoosano,enfunciondelatemperaturaylagargantairritada2clases(enfermo,sano)2atributos(temperatura,gargantairritada)PUCP,GRPIAALabs.
Arbolesdedecision 6 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangeAcercadel
cursoMotivacionEjemploDecidirsiunpacienteestaenfermoosano,enfunciondelatemperaturaylagargantairritada2clases(enfermo,sano)2atributos(temperatura,gargantairritada)PUCP,GRPIAALabs.
Arbolesdedecision 6 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangeAcercadel
cursoMotivacionEjemploDecidirsiunpacienteestaenfermoosano,enfunciondelatemperaturaylagargantairritada2clases(enfermo,sano)2atributos(temperatura,gargantairritada)PUCP,GRPIAALabs.
Arbolesdedecision 6 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseAgenda1InformaciongeneralAcercadel
cursoMotivacion2ArbolesdedecisionkNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclase3ArbolesdedecisionenWekayOrangeWEKAOrangePUCP,GRPIAALabs.
Arbolesdedecision 7 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseParacalentarse:kNN:-)Enlagurasiguiente,lospuntosrepresentanunconjuntodevectoresdedimension2.EstospertenecenadosclasesdenominadasAyB.Elordendeselecciondelosvectoresestaindicadoporlos
ndicessituadosalladodecadapunto.Lospuntos1al4yahansidoclasicados(enrojo),porconsiguiente,elinteresesdeclasicarlospuntossiguientes(apartirdel5,enazul).AplicarelmetodokNNparak=
3.PUCP,GRPIAALabs. Arbolesdedecision 8 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseParacalentarse:kNN:-)PUCP,GRPIAALabs.
Arbolesdedecision 9 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseParacalentarse:solucion5B6A7B8A9A10A11B12A13B14APUCP,GRPIAALabs.
Arbolesdedecision 10 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseParalosmasfrios:-pEnlaguraanterior(uotra),demuestreconunejemploqueelresultadodelaclasicaciondependedelordendecomosonledoslosdatos.Quepuedepasarsikespar?Muestreestecasoespecialconunejemploenlaguraanterior(uotra)PUCP,GRPIAALabs.
Arbolesdedecision 11 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseParalosmasfrios:-pPUCP,GRPIAALabs.
Arbolesdedecision 12 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseParacalentarse:solucionEnelgracoanterior,sielvectorlanzadoenlaposicion10hubierasidolanzadoen8,entonces
estehubierasidoclasicado como By no como A, puesto que los 3
vecinos masproximosyahabransidoclasicadoscomo5(B),6(A)y7(B)Sik=
2yelpunto9habrasidotiradoenlaposicion4,estetendracomovecinosa4(A)y3(B).Cualclaseelegir?elalgoritmoelegiraunodelosdosaazarPUCP,GRPIAALabs.
Arbolesdedecision 13 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseArbolesdedecisi
on:generalidadesTambienllamadometododesegmentacionOrgenes:losarbolesdedecisionpertenecenalosalgoritmosde
AprendizajeAutomatico (MachineLearning)
enInteligenciaArticialParticularidades(convivialylegible)Salidadelosresultadosenformasdereglaslogicasdeclasicacion,e.g.,SItalconjuntodecondicionessobretalesvariablessecumplen,ENTONCESelsujetoperteneceatalclaseResultadosfacilmenteinterpretables(entonces,explotables)ComunicacionmasfacilconlosexpertosdeltematratadoPUCP,GRPIAALabs.
Arbolesdedecision 14 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseArbolesdedecisi
onAlgoritmodeaprendizajesupervisadoMetodoestadsticonoparametricoPermiteclasicarunconjuntodeindividuosdescritosporvariablescualitativasycuantitativasProduceclasesbastantehomogeneasAlgoritmos:ID3(Inductivedecisiontree)ysusucesorC4.5,CART(ClassicationandRegressionTree),CHAID(Chi-SquareAutomaticInteractionDetection),QUEST(Quick,Unbiased,EcientStaticalTrees),etc.PUCP,GRPIAALabs.
Arbolesdedecision 15 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseArbolesdedecisi
onPUCP,GRPIAALabs. Arbolesdedecision 16 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseAlgoritmoCARTEsunalgoritmodeaprendizajesupervisadoEntradanindividuospvariablescontnuasodiscretasunavariablesuplementariaconteniendolaclasealacualpertenecenlosindividuoscSalidaUnarboldedecisionTPUCP,GRPIAALabs.
Arbolesdedecision 17 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseCART:notacionesN(p)
n umerodeindividuosasociadosalaposicion(nodo)pN(k|p) n
umerodeindividuosquepertenecenalaclasek,sabiendoqueellosestanasociadosalaposicionpP(k|p)
=N(k|p)N(p)proporciondeindividuosquepertenecenalaclasekdeentrelosqueestanenlaposicionpNota:Unnodo
es puro si todos los individuos asociados
pertenecenalamismaclasePUCP,GRPIAALabs. Arbolesdedecision 18 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseCART:notacionesN(p)
n umerodeindividuosasociadosalaposicion(nodo)pN(k|p) n
umerodeindividuosquepertenecenalaclasek,sabiendoqueellosestanasociadosalaposicionpP(k|p)
=N(k|p)N(p)proporciondeindividuosquepertenecenalaclasekdeentrelosqueestanenlaposicionpNota:Unnodo
es puro si todos los individuos asociados
pertenecenalamismaclasePUCP,GRPIAALabs. Arbolesdedecision 18 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseCART:ejemploNospidenconstruirunarboldedecisionqueclasicaydeterminalascaractersticasdelosclientesqueconsultansuscuentasdeahorroeninternetVariablesM
promediodelosmontosahorradosentodaslascuentasO ocupaciondelclienteR
regiondondehabitadelclienteE elclientetieneestudiosuniversitarios?I
elclienteconsultasuscuentaseninternet?PUCP,GRPIAALabs.
Arbolesdedecision 19 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseCART:ejemploNospidenconstruirunarboldedecisionqueclasicaydeterminalascaractersticasdelosclientesqueconsultansuscuentasdeahorroeninternetVariablesM
promediodelosmontosahorradosentodaslascuentasO ocupaciondelclienteR
regiondondehabitadelclienteE elclientetieneestudiosuniversitarios?I
elclienteconsultasuscuentaseninternet?PUCP,GRPIAALabs.
Arbolesdedecision 19 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseCART:ejemploCliente
M O R E I1 medio profesional Lince si si2 alto profesional Lima no
no3 bajo jubilado Lima no no4 bajo profesional Lima si si5 medio
estudiante Callao si si6 alto jubilado Callao si no7 medio jubilado
Callao si no8 bajo profesional Lince no noPUCP,GRPIAALabs.
Arbolesdedecision 20 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseCART:construcciondelalgoritmoLaideaessimple(sinformalizacion):LaconstruccionesdescendenteAlprincipio,losindividuossonagrupadosExistencuatroposiblesconstruccionesapartirdelasvariablesmonto(M),ocupacion(O),region(R)yeducacion(E)Enlacolumnadelaclase,tenemostresvaloresSIycincodatosquerepresentanNO
elprimernodo(raiz)esel(3,5)Elnodoinicial(3,
5)esunnodoterminalopodemosconstruiruntest
sobreunavariablequepermitadiscriminardemejormaneralosindividuosutilizandolosgruposcreadosanteriormente?PUCP,GRPIAALabs.
Arbolesdedecision 21 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseCART:construcciondelalgoritmoCliente
M I1 medio si2 alto no3 bajo no4 bajo si5 medio si6 alto no7 medio
no8 bajo noPUCP,GRPIAALabs. Arbolesdedecision 22 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseCART:construcciondelalgoritmoCliente
O I1 profesional si2 profesional no3 jubilado no4 profesional si5
estudiante si6 jubilado no7 jubilado no8 profesional
noPUCP,GRPIAALabs. Arbolesdedecision 23 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseCART:construcciondelalgoritmoCliente
O I1 profesional si2 profesional no3 jubilado no4 profesional si5
estudiante si6 jubilado no7 jubilado no8 profesional
noPUCP,GRPIAALabs. Arbolesdedecision 24 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseCART:construcciondelalgoritmoCliente
R I1 Lince si2 Lima no3 Lima no4 Lima si5 Callao si6 Callao no7
Callao no8 Lince noPUCP,GRPIAALabs. Arbolesdedecision 25 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseCART:construcciondelalgoritmoCliente
R I1 Lince si2 Lima no3 Lima no4 Lima si5 Callao si6 Callao no7
Callao no8 Lince noPUCP,GRPIAALabs. Arbolesdedecision 26 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseCART:construcciondelalgoritmoCliente
E I1 si si2 no no3 no no4 si si5 si si6 si no7 si no8 no
noPUCP,GRPIAALabs. Arbolesdedecision 27 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseCART:construcciondelalgoritmoCliente
E I1 si si2 no no3 no no4 si si5 si si6 si no7 si no8 no
noPUCP,GRPIAALabs. Arbolesdedecision 28 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseCART:construcciondelalgoritmoCualtestelegir?Variable(test)
ComposiciondenodosMonto(M) (1,2),(2,1),(0,2)Ocupacion(O)
(1,0),(2,2),(0,3)Region(R) (1,2),(1,2),(1,1)Estudios(E)
(3,2),(0,3)SobreelatributoR,ningunadiscriminacionsobreningunarama
noganamosnadaconestetestSobreelatributoO,dosdetresnodossonpuros(todoslosindividuospertenecenaunasolaclase)Comoescribirtodoestomatematicamente?PUCP,GRPIAALabs.
Arbolesdedecision 29 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseCART:construcciondelalgoritmoCualtestelegir?Variable(test)
ComposiciondenodosMonto(M) (1,2),(2,1),(0,2)Ocupacion(O)
(1,0),(2,2),(0,3)Region(R) (1,2),(1,2),(1,1)Estudios(E)
(3,2),(0,3)SobreelatributoR,ningunadiscriminacionsobreningunarama
noganamosnadaconestetestSobreelatributoO,dosdetresnodossonpuros(todoslosindividuospertenecenaunasolaclase)Comoescribirtodoestomatematicamente?PUCP,GRPIAALabs.
Arbolesdedecision 29 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseCART:construcciondelalgoritmoCualtestelegir?Variable(test)
ComposiciondenodosMonto(M) (1,2),(2,1),(0,2)Ocupacion(O)
(1,0),(2,2),(0,3)Region(R) (1,2),(1,2),(1,1)Estudios(E)
(3,2),(0,3)SobreelatributoR,ningunadiscriminacionsobreningunarama
noganamosnadaconestetestSobreelatributoO,dosdetresnodossonpuros(todoslosindividuospertenecenaunasolaclase)Comoescribirtodoestomatematicamente?PUCP,GRPIAALabs.
Arbolesdedecision 29 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseCART:construcciondelalgoritmoCualtestelegir?Variable(test)
ComposiciondenodosMonto(M) (1,2),(2,1),(0,2)Ocupacion(O)
(1,0),(2,2),(0,3)Region(R) (1,2),(1,2),(1,1)Estudios(E)
(3,2),(0,3)SobreelatributoR,ningunadiscriminacionsobreningunarama
noganamosnadaconestetestSobreelatributoO,dosdetresnodossonpuros(todoslosindividuospertenecenaunasolaclase)Comoescribirtodoestomatematicamente?PUCP,GRPIAALabs.
Arbolesdedecision 29 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseCART:gradodemezclaDebemoscompararlasdiferentesopcionesposiblesIntroducirlasfuncionesquepermitenmedirelgradodemezclaenlasdiferentesclasesPropiedaddedosfuncionesElmnimoesalcanzadocuandolosnodossonpuros,e.g.,O(0,3)Elmaximoesalcanzadocuandolosindividuossonequipartidosentrelasclases,e.g.,R(1,1)PUCP,GRPIAALabs.
Arbolesdedecision 30 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseCART:gradodemezclaDebemoscompararlasdiferentesopcionesposiblesIntroducirlasfuncionesquepermitenmedirelgradodemezclaenlasdiferentesclasesPropiedaddedosfuncionesElmnimoesalcanzadocuandolosnodossonpuros,e.g.,O(0,3)Elmaximoesalcanzadocuandolosindividuossonequipartidosentrelasclases,e.g.,R(1,1)PUCP,GRPIAALabs.
Arbolesdedecision 30 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseCART:gradodemezclaDebemoscompararlasdiferentesopcionesposiblesIntroducirlasfuncionesquepermitenmedirelgradodemezclaenlasdiferentesclasesPropiedaddedosfuncionesElmnimoesalcanzadocuandolosnodossonpuros,e.g.,O(0,3)Elmaximoesalcanzadocuandolosindividuossonequipartidosentrelasclases,e.g.,R(1,1)PUCP,GRPIAALabs.
Arbolesdedecision 30 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseCART:gradodemezclaDebemoscompararlasdiferentesopcionesposiblesIntroducirlasfuncionesquepermitenmedirelgradodemezclaenlasdiferentesclasesPropiedaddedosfuncionesElmnimoesalcanzadocuandolosnodossonpuros,e.g.,O(0,3)Elmaximoesalcanzadocuandolosindividuossonequipartidosentrelasclases,e.g.,R(1,1)PUCP,GRPIAALabs.
Arbolesdedecision 30 /
63InformaciongeneralArbolesdedecisionArbolesdedecisionenWekayOrangekNN?ArbolesdedecisionAlgoritmoCARTTrabajoenclaseCART:gradodemezclaEjemplosdefuncionesEntropiaEntropia(p)
= C
k=1P(k|p)lnP(k|p)GiniGini (p) = 1 C
k=1P2(k|p) = 2
k
