Sistemas de recomendación aplicados a jueces en línea

Sis emas de ecomendación aplicados a jueces en línea T abajo de Fin de G ado Ped o Pablo Doménech A ellano Al onso So ia Muñoz G ado en Ingenie ía In o má ica Facul ad de In o má ica Uni e sidad Complu ense de Mad id Mayo 2019 Documen o maque ado con T EXiS .1.0+. Es e documen o es á p epa ado pa a se imp imido a doble ca a. Sis emas de ecomendación aplicados a jueces en línea Memo ia que p esen an pa a op a al í ulo de G ado en Ingenie ía In o má ica Sis emas de ecomendación aplicados a jueces en línea G ado en Ingenie ía In o má ica Facul ad de In o má ica Uni e sidad Complu ense de Mad id Mayo 2019 Copy igh c Ped o Pablo Doménech A ellano y Al onso So ia Muñoz Resumen Un sis ema de ecomendación aplicado a jueces en línea, como bien mues- a el í ulo de es e documen o, aúna dos concep os que deben en ende se p e iamen e. El p ime concep o de ellos es el de ecomendado . Un ecomendado es un sis ema de il ado de in o mación que busca p edeci la p e e encia de un usua io espec o a un conjun o de elemen os. El obje i o de los eco- mendado es, po lo an o, es acili a las búsquedas del usua io den o de una pla a o ma, de mane a que al usua io se le acili en elemen os pe sona- lizados que ienen elación con el compo amien o que es e gene a bajo la pla a o ma. El segundo concep o es el de juez en línea. Un juez en línea unciona como un eposi o io de eje cicios que un usua io puede hace y en ia , pa a así ob ene un e edic o. Los jueces en línea son, po lo an o, un ipo de pla a o mas o ien adas a la esolución de eje cicios de p og amación, con la inalidad de que los usua ios puedan in en a las p opues as de p oblemas que cada pla a o ma enga y comp oba el es ado de sus en íos. Es e es ado indica si el en ío es co ec o o inco ec o y a su ez inco po a in o mación ex a como el iempo de ejecución o el consumo de memo ia. Es e abajo, po lo an o, consis e en el es udio de ecomendado es y jueces en línea con al o de alle, pa a así pode auna el mundo de los e- comendado es y cen a los en es as pla a o mas, llegando a edac a a ios modelos de ecomendación y e alua los sob e un caso eal de juez en línea, como es el de la pla a o ma ¡Acep a el e o!. Palab as cla e: sis ema de ecomendación, eo ema de bayes, k- ecinos más ce canos, juez en línea, ecomendado es, ¡Acep a el e o!. Abs ac A ecommende sys em applied o online judges, as he i le o his do- cumen says, join wo concep s ha mus be unde s ood p e iously. The i s concep o hem is ecommende . A ecommende is an in o ma- ion il e ing sys em ha seeks o p edic he p e e ence o an use ega ding a se o elemen s. The goal o he eccomende s he e o e, is o acili a e use sea ches wi hin a pla o m, so ha h ough he ecommende , he use is p o ided wi h cus omized elemen s ha a e ela ed o he beha io ha is gene a ed unde he pla o m. The second concep is online judge. An online judge wo ks as a eposi o y o exe cises ha an use can do and send, in o de o ob ain a esul ha is a e dic . Online judges a e he e o e a ype o pla o ms o ien ed o he esolu ion o p og amming exe cises, in o de ha use s can y he p oposals o p oblems ha each pla o m has and check he s a us o hei submissions wi h ex a in o ma ion in many cases like he ime o execu ion and he memo y ha he sen p og am has consumed, as well as he main in o ma ion on whe he he submission is alid o dddoes no wo k co ec ly. This wo k, he e o e, consis s o he s udy o ecommende s and online judges wi h high de ail, so we can b ing oge he he wo ld o ecommende s and cen e hem on hese pla o m, ¡Acep a el e o!. Keywo ds: ecommende sys em, bayes heo em, K-Nea es neighbo s, on- line judges, ecommende s, ¡Acep a el e o!. ii No as de los au o es En el p esen e documen o se pone nues o es ue zo al se icio del conoci- mien o, in en ando auna concep os ap endidos a lo la go de es os años, pa a aplica los sob e un mundo desconocido has a aho a pa a quienes elabo amos es a memo ia. Es e es el mundo de los ecomendado es, cada día más usados en odos los aspec os de nues a ida co idiana, como in e esan es po odo el po encial que ienen y que les queda po ene . Es e abajo de in de g ado es, po lo an o, un in en o de documen a nos y ap ende sob e algo nue o, así como pone lo en p ác ica y lle a lo a cabo en el ámbi o de los jueces en línea, pla a o mas que ienen poca in es igación de as ondo en lo que al mundo de la ecomendación se e ie e. Es además in e esan e pode es udia la mul i ud de modelos de eco- mendación con ideas an di e en es en e ellos, pe o cuyo obje i o siemp e es el mismo: gene a una solución co ec a a las necesidades del usua io. Po o o lado enemos las pla a o mas de jueces en línea, las cuales son cada día más popula es en e ma emá icos, ingenie os, y pe sonas ce canas a es os sec o es, ya que p oponen una se ie de eje cicios que a o ecen y eje ci an la agilidad men al, y mejo an los conocimien os del campo de la algo i mia. Son además des acables los jueces en línea pa a los es udian es de es as á eas, ya que median e es as pla a o mas pueden ap ende cie as amas de sus ca e as de una mane a en e enida y en algunos casos, incluso, compe i- i a, pa a aquellas que son capaces de in eg a concu sos. De es a mane a, un juez en línea a la ez de se una pla a o ma de ocio, a o ece el ap endizaje de los usua ios que se a icionan a es as pla a o mas. Con es e documen o no sólo nos apo amos a noso os mismos nue os conocimien os, aden ándonos en es os dos mundos que no se ocan p ác- icamen e du an e el anscu so de la ca e a, sino que in en amos apo a nues o g ano de a ena an o a la in es igación de nue os modelos de eco- mendación, como a la in es igación de la implemen ación de ecomendado es en es e modelo de pla a o mas, pa a que gene en soluciones óp imas a unas necesidades conc e as. Sin más dilación, le dejamos con nues o abajo, y espe amos que lo ix x i Índice de igu as 7.10. G á ica 2 del Recall pa a el SR K-Vecinos. . . . . . . . . . . . 59 7.11. G á ica 1 del F-Sco e pa a el SR K-Vecinos. . . . . . . . . . . 60 7.12. G á ica 2 del F-Sco e pa a el SR K-Vecinos. . . . . . . . . . . 61 8.1. G á ica de compa ación de p ecision .............. 64 8.2. G á ica de compa ación de one-hi ............... 65 8.3. G á ica de compa ación de ecall ................ 66 8.4. G á ica de compa ación de -sco e ................ 67 9.1. Diag ama de clases ex endido pa a el ecomendado K-Vecinos. 70 9.2. Funcionamien o del ecomendado K-Vecinos con API (Ap- plica ion P og amming In e ace) implemen ada pa a su uso como se icio ex e no. . . . . . . . . . . . . . . . . . . . . . . 71 Índice de Tablas 6.1. Tabla p ecision .......................... 37 6.2. Tabla one-hi ........................... 38 6.3. Tabla Recall ............................ 39 6.4. Tabla F-Sco e ........................... 40 7.1. Tabla de esul ados de P ecision pa a el SR K-Vecinos. . . . . 53 7.2. Tabla de esul ados de one-hi pa a el SR K-Vecinos. . . . . . 56 7.3. Tabla de esul ados de ecall pa a el SR K-Vecinos. . . . . . . 58 7.4. Tabla de esul ados de F-Sco e pa a el SR K-Vecinos. . . . . 59 x ii Capí ulo 1 In oducción La e olución digi al hace cada ez más ácil la ida de los usua ios, pe mi iéndoles gana iempo así como ene in o mación pe sonal y gene al siemp e a mano. Vi imos en un momen o donde hace unos años (y en oca- siones meses) no exis ían pla a o mas y aplicaciones que aho a son usadas de o ma masi a, y cada día su gen nue as ideas que ienen un éxi o de uso inmedia o. Es e p oyec o pa e de la idea de do a con he amien as que acili an la ida del usua io, a pla a o mas eme gen es que son los jueces en línea. Es as he amien as se an a cen a en conc e o en los sis emas de ecomendación o SR, que pe mi en aho a el iempo del usua io haciéndole p opues as y suge encias basadas en el compo amien o que es e gene a bajo la pla a o - ma. Cuando escogimos es e abajo de in de g ado, lo hicimos po que imos una idea p ome edo a pa a do a de es as he amien as a un juez en línea en conc e o que es popula en e la acul ad, y g acias a odo el camino que se ha ealizado a lo la go de es e año, se ha log ado a hace un es udio muy comple o pa a pode llega a aplica dos ecomendado es que se han ealizado bajo la pla a o ma que es ¡Acep a el e o!. 1.1. Obje i os El p esen e abajo de in de g ado iene los siguien es obje i os: Es udia di e en es modelos de ecomendación. Realiza un es udio sob e las pla a o mas de jueces en línea. Es udia casos ya exis en es de implemen aciones de ecomendado es en pla a o mas de jueces en línea. Realiza un es udio sob e mé odos de e aluación pa a analiza la e i- cacia de un ecomendado . 1 2Capí ulo 1. In oducción Analiza modelos de implemen ación como se icio ex e no pa a los sis emas de ecomendación. Implemen a un pa de modelos de ecomendación des acables y que uncionen bien sob e pla a o mas de jueces en línea y p opone una a qui ec u a de comunicación pa a que uncione como se icio ex e no. E alua sob e un juez en línea la e icacia de los modelos implemen ados y pode con as a esul ados pa a e las di e encias de compo amien- o de cada modelo de ecomendación ealizado. 1.2. Plan de abajo La plani icación seguida en es e abajo ha comenzado po documen a - nos en di e en es aspec os. P ime o se ha ealizado el es udio sob e sis emas de ecomendación, empezando a e lo que son, su uncionamien o, sus ob- je i os y acabando po es udia di e en es écnicas exis en es que pueden usa se pa a es os sis emas. De es as écnicas se ocaliza el es udio con mayo p o undidad en es de ellas que han esul ado las más in e esan es. Pos e io men e y pa alelo al es udio en p o undidad de es écnicas de ecomendación conc e as, se ha comenzado a documen a y ecaba in o - mación sob e los jueces en línea, y en conc e o sob e el uncionamien o de ¡Acep a el e o! un juez en línea con el que se ha podido abaja en es e p oyec o. Se ha hecho un análisis de sus da os, desde las en egas has a la can idad de p oblemas y usua ios que es a pla a o ma maneja. Finalmen e, se ha hecho un análisis de jueces en línea exis en es que ya implemen an sis emas de ecomendación, y se han leído a ículos de sis emas de ecomendación p opues os pa a se aplicados a jueces en línea. T as es a p ime a ase de analiza odo lo exis en e y documen a nos de in o mación, se ha en ado en una segunda ase de implemen ación, donde se han ealizado dos modelos de ecomendación y pos e io men e se han op imizado pa a educi los cálculos a iempos insigni ican es. Es os modelos de ecomendación han pasado po una ase de e aluación indi idual sob e la base de da os de ¡Acep a el e o! pa a analiza su compo - amien o y pos e io men e se ha ealizado una e aluación en conjun o pa a con as a esul ados y saca unas conclusiones pa a ambos ecomendado es. Finalmen e se ha ealizado una p opues a de API de comunicación, que pe mi e a es os sis emas de ecomendación pode se usados como un se icio ex e no pa a los jueces en línea. Es a API de comunicación se ha podido pone a p ueba con uno de los modelos implemen ados sob e ¡Acep a el e o!. Todo es e plan de abajo acaba en unas conclusiones in e esan es sob e la mul i ud de análisis que se ha in en ado hace y po o o lado se p oponen las líneas de abajo u u o que puede oma desde es e pun o el p oyec o que se ha ealizado. Capí ulo 2 In oduc ion The Digi al Re olu ion makes li e easie o he public, allowing hem o sa e ime in addi ion o ha e gene al and pe sonal in o ma ion accessible. We li e a a ime whe e a ew yea s ago (o e en only mon hs) we had no pla o ms o applica ions ha a e now ex emely used, and e e y day come new ideas ha ha e an immedia e success. This p ojec a ises om he idea o p o iding ools ha make li e easie o a use o he new pla o ms ha a e he online judges. These ools a e going o ocus on he ecommende sys ems o RS, ha sa e he use ime making him p oposals and sugges ions based on he beha io ha he use gene a es on he pla o m. When we chose his inal hesis, we saw ha i was a p omising idea o p o ide hese ools o a popula online judge a he acul y, and due all he wo k made his yea , we managed o make a ull s udy o be able o apply wo ecommende s unde he ¡Acep a el e o! pla o m. 2.1. Objec i es This hesis has he ollowing objec i es: S udy di e en ecommenda ion models. Pe o m a s udy abou online judge pla o ms. In es iga e exis ing cases o implemen ed ecommende s in online jud- ges. Pe o m ano he s udy abou e alua ion me hods o analyze a ecom- mende e ec i eness. Analyze implemen a ion models as an ex e nal se ice o he ecom- menda ion sys ems. 3 4Capí ulo 2. In oduc ion Implemen a couple o ema kable implemen a ion models ha wo k sa is ac o ily on he online judges pla o ms and p opose a communi- ca ion a chi ec u e o wo k as an ex e nal se ice. E alua e he e ec i eness o implemen ed models on an online judge and compa e esul s o see he beha io di e ences o each ecommen- da ion model. 2.2. Wo k plan The wo k plan ollowed in his disse a ion has begun by ga he ing in o - ma ion on di e en aspec s. Fi s , we ha e done a s udy on ecommenda ion sys ems, s a ing o see wha hey a e, how hey wo k, hei objec i es and inally s udying di e en exis ing echniques ha can be used o hese sys- ems. O hese echniques, ou s udy has ocused in g ea e dep h on h ee o hem ha ha e u ned ou o be he mo e in e es ing ones. Subsequen ly, and pa allel o he in-dep h s udy o he h ee conc e e ecommenda ion echniques, we ha e begun o ga he in o ma ion abou online judges, and speci ically abou how ¡Acep a el e o! wo ks, an online judge wi h which we ha e been able o wo k in his p ojec . We ha e done an analysis o he da a, om he use deli e ies o he numbe o exe cises and use s ha his pla o m manages. Finally, we ha e ca ied ou an analysis o exis ing online judges which al eady implemen ecommenda ion sys ems and we ha e ead a icles om p oposed sys ems o be added o online judges. A e his i s phase o analyzing all he p e ious in o ma ion and co- llec ing da a, we ha e en e ed in o a second phase o implemen a ion, whe e we ha e made wo ecommenda ion models and hen ha e been op imized o educe he calcula ion ime o a minimum. These ecommenda ion models ha e gone h ough an indi idual e alua- ion phase on he ¡Acep a el e o! da abase o analyze hei beha io and hen, we ha e ca ied ou an e alua ion be ween bo h o compa e esul s and ob ain conclusions o he wain ecommende s. Finally, we ha e p oposed a communica ion API, which allows hese e- commenda ion sys ems o be used as an ex e nal se ice o online judges. This communica ion API has been es ed wi h one o he models implemen- ed on ¡Acep a el e o!. All his wo k plan ends in some in iguing conclusions abou he mul i- ude o analysis ha ha e been ied and addi ionally we ha e decided he u u e wo k pa hs ha we can ollow om his poin he p ojec . Capí ulo 3 Sis emas de ecomendación Resumen: En es e capí ulo se in oducen los sis emas de ecomen- dación, en adelan e ambién llamados SR, en ando en de alle en la inalidad de es os, y explicando di e en es écnicas de ecomendación que pueden se aplicadas y se han conside ado como las más des aca- bles pa a es e abajo. Con el a ance de los sis emas in o má icos, se han ido desa ollando sis- emas o ien ados a usua ios que manejan in o mación, como son las pla a- o mas que ges ionan di e en es ipos de con enido. La g an p oblemá ica de o ece al usua io el con enido más indicado a su pe il ue su giendo a medida que el con enido c ecía masi amen e den o de es as pla a o mas. Fue po es o que apa ecie on necesidades de implemen a nue as ecnologías que pe mi ie an p opo ciona al usua io cie as acilida- des, pa a ob ene cómodamen e lo que és e ealmen e necesi aba de en e oda la in o mación exis en e. Es as ecnologías, que acili aban la selección de la in o mación que más le in e esaba al usua io, engloban el mundo de los buscado es, los p edic o es, los clasi icado es de con enido y los sis emas de ecomendación, en e o os. Son es as úl imas ecnologías las que, aplicando unas eglas in e nas o algo i mos, log an, en mayo o meno medida, encon a simili udes en e elemen os o en adelan e, í ems, pa a acili a al usua io el acceso a lo que és e más necesi a o le pueda esul a más in e esan e y ce cano a sus gus os, según las elaciones o el his o ial de in e acciones que el usua io ha ealizado. Como se mues a en la igu a 3.1, un sis ema de ecomendación gene a una ecomendación, basándose en elaciones de in e acción en e usua ios e í ems, y haciendo uso de algo i mos in e nos que asignan alo es a es as elaciones pa a la gene ación de las ecomendaciones. El ecomendado se enca ga po lo an o, de encon a es as elaciones gene adas po el his o ial del usua io sob e la ac i idad de los í ems y hace 5 6Capí ulo 3. Sis emas de ecomendación Figu a 3.1: Funcionamien o en básico de un sis ema de ecomendación. los cálculos pe inen es pa a asocia nue os í ems en conco dancia con es as elaciones y simili udes (Agga wal (2016)). 3.1. Recomendado es Los sis emas de ecomendación p opo cionan la in o mación más adecua- da a pa i de las in e acciones y acciones que el usua io ealiza. Un ecomendado es po lo an o un sis ema capaz de gene a in o mación subje i a y il ada, con cie as ca ac e ís icas, g acias a un algo i mo que analiza la ac i idad del usua io y o os da os (Agga wal (2016)). Es as ecomendaciones gene adas ienen la ca ac e ís ica de se adap- adas al usua io al que se le es á gene ando la ecomendación, ya que el p opósi o gene al de un ecomendado es acili a los da os necesa ios de mane a pe sonalizada. Ac ualmen e un po al web con g an a luencia de usua ios y con enido dispone de sis emas de ecomendación. Como ejemplos de casos popula es y de éxi o, que ienen impo an es y des acables ecomendado es debido a su complejidad y que p es an g an apoyo a las pla a o mas sob e las que ac úan, podemos menciona a Ne lix1(se ies y películas), Amazon2( en a de p oduc os), o YouTube3(con enido audio isual). Son es os sis emas de ecomendación an a anzados los que han a o e- cido la popula idad y el éxi o c ecien e de es as pla a o mas. O os sis emas de ecomendación son usados de mane a menos di ec a pa a asocia a usua ios elemen os especí icos, como se da en el ámbi o de la publicidad en in e ne , cuyo e e en e más ep esen able en es e caso es Google Adwo ds4, que, a a és de la in o mación de un usua io que usa 1h ps://www.ne lix.com 2h ps://www.amazon.es 3h ps://www.you ube.com 4h ps://ads.google.com 3.2. Técnicas de ecomendación in o madas 7 se icios de Google, e ina y clasi ica qué ipos de anuncios son ecomendables pa a el usua io según lo que és e busca na egando po sus se icios. Los sis emas de ecomendación han ido e olucionando a causa de la nece- sidad de pe ecciona las ecomendaciones, ya que un ecomendado que hace mejo es ecomendaciones, implica un aumen o signi ica i o de los ing esos pa a muchas pla a o mas ya sea po que el SR (Sis ema de Recomendación) se aplique en emas de publicidad, en as, e c, o simplemen e la mejo a de imagen de la p opia pla a o ma que la hacen más a ac i a a nue os usua- ios. La e olución ecnológica ha hecho posible pasa de écnicas sencillas basadas en ecomenda í ems con ca ac e ís icas simila es, según a ibu os comunes, a ecomendaciones a anzadas, basadas en écnicas de il os cola- bo a i os. En es as écnicas más a anzadas se aplican conjun os de da os masi os pe mi iendo hace análisis de da os con las in e acciones especí icas de un usua io, an es de gene a la ecomendación. Den o de es as écnicas exis en ambién algunas écnicas de ecomen- dación que usan mé odos de clasi icación y los adap an al obje i o de una ecomendación. Los mé odos de clasi icación se enca gan de coloca elemen- os que no es án aún en un luga de inido pa a si ua los en di e en es g upos exis en es, es deci , los elemen os que no ienen una clasi icación p e ia, son asignados po un algo i mo en un g upo según ca ac e ís icas que se encuen- en de es e. Es as o mas de ecomenda se explican con mayo de alle en las siguien- es secciones de es e capí ulo. 3.2. Técnicas de ecomendación in o madas Las écnicas de ecomendación in o madas engloban aquellos mé odos de ecomendación que no suponen un conocimien o global de in o mación, es deci , mé odos que solo se ijan en la in o mación p opia de un usua io espec o las in e acciones con di e en es elemen os, sin necesidad de conoce la del es o de usua ios. Es as écnicas, u ilizan p opiedades que ienen los p opios í ems con los que el usua io in e ac úa, pa a ag upa los en base a es as p opiedades. El ejemplo más en endible de las écnicas de ecomendación in o madas, es el caso de un ecomendado basado en e ique as y a ibu os. Es e ipo de ecomendado mi a las in e acciones que iene un usua io con cie os í ems, los cuales ienen cie os a ibu os y el ecomendado busca o os í ems con los mismos ipos de a ibu os pa a usa los como opciones a ecomenda . Un ecomendado basado en e ique as y a ibu os necesi a po lo an- o que los í ems sob e los que abaja engan in e namen e p opiedades y e ique as pa a pode se clasi icados de una mane a di ec a po es as p opie- dades. De es a mane a el ecomendado hace uso de las in e acciones que un usua io iene con los dis in os í ems, pa a así selecciona los egis os más 14 Capí ulo 3. Sis emas de ecomendación 3.3.3. Recomendado basado en i ine a ios de ap endizaje Un ecomendado basado en i ine a ios de ap endizaje comp ueba qué línea ha seguido un usua io a la ho a de elegi í ems y analiza el es o de líneas seguidas po o os usua ios pa a encon a las más simila es y gene a una ecomendación basada en í ems que segui ían ese eco ido. Es os algo i mos se pueden usa en pla a o mas donde los usua ios ienen in ención de segui un i ine a io de ap endizaje, como es el caso de los jueces en línea (capí ulo 4), donde exis en eje cicios o p oblemas a esol e . En es e caso se ecomiendan los p oblemas más in e esan es pa a la línea de ap endizaje del indi iduo. De es a mane a, se puede conside a que el ecomendado solo se ija en las líneas más a anzadas que exis en de usua ios que han seguido po la misma ayec o ia del indi iduo a ecomenda , pa a así pode ecomenda líneas más p ecisas (Sánchez-Ruiz e al. (2017)). A modo de ejemplo, en el caso de jueces en línea, es e ecomendado gene a un i ine a io de ap endizaje po cada usua io en base a los p oblemas que ha ido consiguiendo ealiza de o ma sa is ac o ia. Es as secuencias de p oblemas que se les asigna a cada usua io, man ienen un o den que iene dado po la echa desde el p ime p oblema esuel o que ienen, has a el úl imo. Dado un usua io Ui, al que se le asigna un i ine a io Li, pa a gene a la ecomendación, se aplica una consul a en base al Liasociado a Ui. De es a consul a se ob iene una upla indicando la simili ud en e cada i ine a io del es o de usua ios, con Li, ob eniendo los N más simila es. U ilizando es os nue os i ine a ios, el ecomendado puede busca p o- blemas que no ha esuel o el indi iduo a se ecomendado, y clasi ica los de di e en es mane as, pa a gene a la ecomendación. 3.3.4. Recomendado basado en análisis de edes sociales Un ecomendado que aplica écnicas usadas en análisis de edes sociales, a a a los usua ios y a los í ems como un g a o de indi iduos y las elaciones en e ellos. De es a o ma, po ejemplo, en el caso de un sis ema de jueces en línea, los nodos ep esen an p oblemas y usua ios, y las en egas, las elaciones que exis en en e ellos. Es a ep esen ación de la ed de usua ios y p oblemas, pe mi e usa mé- odos y mé icas de inidas en el campo de análisis de edes sociales. Como se mues a en la igu a 3.4, de es e g a o se pueden ob ene po sepa ado dos g a os donde se ienen las elaciones en e usua ios y las ela- ciones en e p oblemas, de al o ma que del g a o bipa i o de usua ios más p oblemas a ados como nodos se ob ienen dos p oyecciones, una que solo man iene como nodo los usua ios y sus elaciones en e sí, y o a que solo man iene a los p oblemas y sus elaciones en e sí (Fu h (2010)). 3.3. Técnicas de ecomendación no in o madas 15 Figu a 3.4: Ilus ación de un g a o bipa i o(a), donde se ex aen las p oyec- ciones de los nodos X (b) e Y(c). U ilizando es as p oyecciones, se pueden aplica algo i mos de “link p e- dic ion”. Es os algo i mos se usan pa a hace p edicciones de nue os enlaces en e nodos, que puedan su gi en un u u o, o pa a hace p edicciones de enlaces en e nodos, que puedan desapa ece en un u u o (Jimenez-Diaz e al. (2017)). 3.3.5. Recomendado Bayesiano Un ecomendado bayesiano es un SR que aplica cálculos p obabilís icos basados en el eo ema de Bayes de la p obabilidad condicionada, con el obje i o de ob ene la p obabilidad de que un í em sea del ag ado de un usua io. Una ez ob enidas odas las p obabilidades se o denan de mayo a meno , pa a así pode ecomenda al usua io aquellos í ems que mejo encajen con su pe il. La eo ía básica de la p obabilidad explica que la p obabilidad de que ocu a un suceso se calcula di idiendo el núme o de casos a o ables en e el núme o de casos posibles (sección 3.1). La p obabilidad de que ocu a el suceso Ase exp esa como P(A). Así en un dado de seis ca as no ca gado, la p obabilidad de que salga el núme o 4 se ía un sex o ya que solo una ca a, la del cua o, es a o able y hay 6 posibles ca as equip obables. P(A) = no a o ables noposibles (3.1) Si aho a se ienen dos dados di e enciados, uno azul y o o ojo, enemos un o al de 36 casos. En onces si que emos calcula la p obabilidad de que i ando los dos dados salga en el azul un 4 y en el ojo un 6, seguimos eniendo un único caso a o able de los 36 posibles, lo que coincide con la p obabilidad de que salga un 4 en el azul mul iplicado po la p obabilidad 16 Capí ulo 3. Sis emas de ecomendación de que salga un 6 en el ojo. Si nos abs aemos de casos conc e os se puede demos a que la p obabilidad de que ocu an dos sucesos independien es simul áneamen e es la mul iplicación de la p obabilidad de que ocu a cada uno po sepa ado ( ó mula 3.2). Cuando esc ibimos P(A, B)nos e e imos a la p obabilidad de que ocu an los sucesos AyBa la ez, P(A, B) = P(A)·P(B)(3.2) Si aho a es ablecemos que sabemos que en el dado azul ha salido el 4, la p obabilidad de que ocu an ambos sucesos se á la mul iplicación de la p obabilidad que salga 6 en el ojo condicionado a que ha salido 4 en el azul, po la p obabilidad de que ocu a 4 en el azul (3.3). La p obabilidad de que ocu a un suceso Acondicionado a que ha ocu ido Bse deno a como P(A|B). P(A, B) = P(A|B)·P(B)(3.3) Y como que ocu an ambos sucesos simul áneamen e es independien e del o den podemos es ablece la igualdad que se mues a en la ó mula 3.4. Sus i uyendo P(A, B)po la pa e de echa de la igualdad de la ó mula 3.3 y análogamen e P(B, A), y despejando P(A|B)ob enemos la ó mula 3.5. Es a úl ima ó mula es lo que se conoce como eo ema de Bayes. P(A, B) = P(B, A)(3.4) P(A|B) = P(B|A)·P(A) P(B)(3.5) Ex endiendo el eo ema, supongamos que sabemos que a ios sucesos han ocu ido y que emos sabe la p obabilidad de que ocu a o o suceso. Pa a ello, en la ó mula 3.5, sus i uimos donde pone B po la his o ia de sucesos que han ocu ido y ob enemos la o mula 3.6. La his o ia de sucesos la esc ibi emos como B0, ..., Bn. El elemen o P(B0, ..., Bn|A)de la ó mula se e ie e a la p obabilidad de que ocu a la his o ia de sucesos en la hipó esis de que sabemos que ha ocu ido el suceso A. P(A|B0, ..., Bn) = P(B0, ..., Bn|A)·P(A) P(B0, ..., Bn)(3.6) Pa a aplica el eo ema de Bayes se á necesa io calcula los elemen os de la pa e de echa de la ecuación 3.6. Calcula P(A), la p obabilidad a p io i de cada uno de los í ems a ecomenda , suele se un cálculo i ial. Sin emba go, P(B0, ..., Bn|A)no lo es an o. Po ello se suele aplica una ap oximación naï e, asumiendo que odos los sucesos B0has a Bnson independien es en e sí. Con lo que aplicando la ó mula 3.2, la exp esión queda ía como Qn i=0 P(Bi|A). En lenguaje na u al es la mul iplicación de las p obabilidades 3.3. Técnicas de ecomendación no in o madas 17 Bicondicionadas a que ha ocu ido A, donde i oma alo es desde 0 has a n, y Bi ep esen a cada í em de la his o ia de sucesos. Así mismo, es a asunción de independencia de sucesos hace que, aplicando una ex ensión de la ó mula 3.2, se ans o me ambién en una mul iplicación de p obabilidades, quedando la ó mula inal como en 3.7:. P(A|B0, ..., Bn) = P(A)·Qn i=0 P(Bi|A) Qn i=0 P(Bi)(3.7) Es as p obabilidades P(Bi|A)pueden calcula se como el núme o de eces que ocu en BiyAa la ez, di idido po el núme o de eces que ocu e A independien emen e de que haya ocu ido Bi. P(Bi|A) = P(Bi, A) P(A)(3.8) Un p oblema que suele apa ece es que P(Bi|A)sea 0 pa a algún i, lo que p o oca que el esul ado inal de aplica la ó mula an e io sea siemp e 0. La azón de que es o ocu a no malmen e es po que no hay su icien e in o mación sob e el dominio pa a de e mina el alo de P(Bi|A). Si se die a el caso, se pod ía es ima un alo de pa ida pa a dicha exp esión. Una o ma de hace lo es aplica la es imación de Laplace (Cla k y Boswell (1991)). Se p opone que pa a soluciona la ausencia de su icien es da os se asuma que exis e un elemen o de cada miemb o del dominio. Es deci , si pa a Aexis en dos es ados, po ejemplo, Aes un aso que puede es a lleno o es a acío, en onces end íamos que asumi que exis en al menos dos asos uno lleno y o o acío. Si aplicamos es a es imación a la ó mula 3.8 nos queda ía la ó mula 3.9, donde x ep esen a el núme o de es ados pa a A, en es e ejemplo 2. En un caso con más es ados, po ejemplo Aes una bola quede se de colo e de, ojo, azul, blanco o neg o, pues como hay 5 colo es x oma ía el alo 5, asumiendo que exis e al menos una bola de cada colo . P(Bi|A) = P(Bi, A)+1 P(A) + x(3.9) Aunque la es imación ayuda siemp e que engamos casos en que P(Bi, A) alga 0, se ha de aplica a odos los casos incluso aquellos en los que P(Bi, A) alga 1. De es a mane a aunque las p obabilidades que den 0 o alo es ce - canos a 0 se bene icien de la es imación, las que no ambién se bene icia án aunque en meno medida. Capí ulo 4 Jueces en línea Resumen: En es e capí ulo se explica á qué son los jueces en línea mencionando algunos ejemplos. También se en a á a ondo en la ex- plicación sob e el juez en línea de ¡Acep a el e o! y ambién en o o juez en línea que además iene inco po ado un SR. 4.1. ¿Qué son los jueces en línea? Los jueces en línea son eposi o ios de p oblemas con un e aluado de soluciones pa a comp oba au omá icamen e si un p og ama es solución a un p oblema dado. Pa a ello el sis ema compila el código del p og ama en iado, lo ejecu a con una se ie de casos de p ueba como en ada y comp ueba si las salidas ob enidas coinciden con las que el sis ema iene asociadas como co ec as. Además suelen medi pa áme os ex a, como pueden se el iempo de ejecución y la memo ia u ilizada. Una ez hecho es o, el juez p opo ciona un e edic o. Dos ejemplos de jueces en línea son UVa Online Judge1y ¡Acep a el e o!2. Es os sis emas se u ilizan p incipalmen e en el ámbi o de los concu sos de p og amación, así como pa a p ac ica pa a es os, aunque ambién se u ilizan en el ámbi o académico pa a pone en p ác ica los conocimien os adqui idos en los aulas. Algunos de ellos, como el UVa Online Judge, además de se eposi o ios de p oblemas son capaces de aloja concu sos, omen ando así la compe i i- idad y el desa ollo de las habilidades de los usua ios. En ocasiones, el eposi o io de p oblemas añade e ique as a los p oble- mas pa a clasi ica los según los concep os de p og amación necesa ios pa a esol e los, po la emá ica del enunciado, po su apa ición en concu sos, e c. 1h ps://u a.onlinejudge.o g 2h ps://www.acep ael e o.com 19 20 Capí ulo 4. Jueces en línea Es una mane a de acili a a los usua ios encon a p oblemas que puedan ajus a se a lo que es án buscando. Po lo an o, en es as pla a o mas exis en usua ios que seleccionan p oble- mas de un ex enso eposi o io y ealizan en íos de código pa a soluciona los. Se pueden es ablece en onces elaciones en e usua ios en unción de los en íos. Los jueces en línea se hacen cada ez más popula es g acias a los concu - sos de p og amación que p omocionan emp esas como Google con el Hash- code3, o como la compañía de mó il Tuen i con el Tuen i Challenge4. 4.2. El juez en línea ¡Acep a el e o! ¡Acep a el e o! es un juez en línea desa ollado po algunos p o eso es de la Facul ad de In o má ica de la Uni e sidad Complu ense de Mad id. Además de se un ex enso eposi o io de p oblemas, ¡Acep a el e o! es un co ec o au omá ico, es deci , se puede subi el código c eado como solución a un p oblema del eposi o io pa a que ¡Acep a el e o! lo compile, ejecu e y p opo cione un e edic o. Los e edic os de ¡Acep a el e o! an más allá de un simple Bien o Mal, es más, exis en has a once e edic os dis in os, de los cuales dos no dependen del esul ado del p oblema, sino que son po e o es in e nos o po que aún no se ha e aluado la solución, y uno es un echazo del código po mo i os de segu idad. Los o os ocho son los siguien es: Accep ed (AC): Acep ado. Es el e edic o más deseado, pues signi ica que la solución es co ec a. P esen a ion e o (PE): E o de p esen ación. Se p oduce cuando la solución al p oblema es co ec a, pe o al mos a la solución, los sal os de línea o espacios en blanco di ie en de los que debe ían se . W ong Answe (WA): Respues a inco ec a. El p og ama no p oduce las salidas espe adas, po an o no es solución al p oblema dado. Compila ion E o (CE): E o de compilación. El sis ema no ha po- dido compila el código po que iene e o es. Run Time E o (RTE): E o du an e la ejecución. Se p oduce cuando la solución al se ejecu ada p oduce algún ipo de excepción, como di isiones po ce o o índices ue a de ango. Time Limi Exceeded (TLE): Tiempo lími e supe ado. Se p oduce cuan- do la solución dada a da en ejecu a se más iempo del espe ado, po ejemplo po culpa de bucles in ini os o soluciones no op imizadas. 3h ps://codingcompe i ions.wi hgoogle.com/hashcode 4h ps://con es . uen i.ne 4.2. El juez en línea ¡Acep a el e o! 21 Memo y Limi Exceeded (MLE): Memo ia lími e supe ada. Se p oduce cuando la solución al p oblema pide más memo ia de la pe mi ida. Ou pu Limi Exceeded (OLE): Salida lími e supe ada. Se p oduce cuando el p og ama solución gene a una salida más amplia de la pe - mi ida. Cuando un usua io ealiza un en ío y ecibe una espues a e ónea es habi ual que e ise el código y en poco iempo ealice un nue o en ío con la espe anza de ob ene el e edic o AC ( Accep ed). Es o no quie e deci que cuando un usua io ya iene un AC en un p oblema no pueda ealiza nue os en íos. ¡Acep a el e o! cuen a con un anking pa a cada p oblema de modo que las soluciones más óp imas se encuen en en posiciones más ele adas. Po ello, a pesa de que un usua io haya ecibido ya un AC pa a un p oblema no es de ex aña que po compe i i idad op imice su solución y ealice o o en ío pa a subi en el anking. Con es o aho a se pueden ca ego iza los p oblemas pa a un usua io en es es ados: Resuel os: el usua io ha ealizado uno o a ios en íos y al menos en uno de ellos ha ob enido AC. In en ados: el usua io ha ealizado uno o a ios en íos, pe o en ninguno de ellos ha ob enido como e edic o un AC. No in en ados: el usua io no ha ealizado ningún en ío, ya sea po que el p oblema le pa ece muy complicado o po que no lo ha leído oda ía. Po o o lado, ¡Acep a el e o! incluye una ca ego ización en sus p o- blemas, una en aja an o pa a algunos modelos de ecomendación, que se basan en e ique as y mé odos di ec os, como ambién pa a los usua ios, que pueden ma ca se i ine a ios en base a las ca ego ías pa a p ac ica una ama especí ica. El juez de ¡Acep a el e o! es capaz de compila soluciones en di e en es lenguajes de p og amación (C, C++ y Ja a) y o ece un conjun o limi ado de uso de lib e ías es ánda pa a limi a a los usua ios el uso de ecu sos pa a que sean ellos los que engan que diseña los al esol e los p oblemas, así como e i a que el usua io pueda ejecu a código que no se quie e que se emplee pa a la esolución de los eje cicios. En la sección de p egun as ecuen es de ¡Acep a el e o! se encuen a con más de alle es e ipo de in o mación además de in o mación ex a, en e la que incluye el compo amien o del Juez, e edic os, las lib e ías acep adas, y más in o mación ú il an o pa a los usua ios pa a aquel que quie a en ende con mayo p o undidad cie os aspec os del juez que aquí se hayan explicado sin en a al de alle. Se puede obse a la apa iecia de ¡Acep a el e o! en la igu a 4.1 22 Capí ulo 4. Jueces en línea Figu a 4.1: Página de inicio de ¡Acep a el e o!. 4.3. El juez en línea Ka is Ka is5es un juez online que al igual que ¡Acep a el e o! iene un amplio eposi o io de p oblemas con su e aluado co espondien e, y que al igual que UVa Online Judge es capaz de ges iona concu sos. Además incluye un SR que ecomienda a ios p oblemas ag upados en cua o ca ego ías en unción de su di icul ad: i ial,easy,medium yha d (Re illa e al. (2008)). Es a di icul ad no es á p ees ablecida, sino que po el con a io a ía en unción del núme o de en íos co ec os y o ales. Pa a calcula dicha di i- cul ad u iliza una a ian e de ELO a ing sys em (Wikipedia (Elo a ing sys em)), que, esumidamen e, lo que hace es da meno di icul ad a los p oblemas que han sido esuel os po muchos usua ios en pocos en íos, y mayo di icul ad a aquellos que han sido esuel os po pocos pe o in en a- dos po muchos. Aquellos p oblemas que ienen pocos en íos se clasi ica ían con di icul ad media, ya que no se dispone de in o mación su icien e pa a de e mina la. Además es e sis ema ambién e alúa al usua io, eniendo en cuen a los p oblemas que ha esuel o, su pun uación o al y la p ecisión de sus en íos. De es a mane a pa a un usua io nue o el p oblema que se le ecomienda como di ícil puede se pa a o o usua io ecomendado como ácil, ob eniendo así una ecomendación más aco de con el ni el del usua io. Se puede obse a la apa iencia de Ka is en la igu a 4.2 5h ps://open.ka is.com/ 4.3. El juez en línea Ka is 23 Figu a 4.2: Página de inicio de Ka is. 30 Capí ulo 5. E aluación de ecomendado es 2014-02 2014-03 2014-04 2014-05 2014-06 2014-07 2014-08 2014-09 2014-10 2014-11 2014-12 2015-01 2015-02 2015-03 2015-04 2015-05 2015-06 2015-07 2015-08 2015-09 2015-10 2015-11 2015-12 2016-01 2016-02 2016-03 2016-04 2016-05 2016-06 2016-07 2016-08 2016-09 2016-10 2016-11 2016-12 2017-01 2017-02 2017-03 2017-04 2017-05 2017-06 2017-07 2017-08 2017-09 2017-10 2017-11 2017-12 2018-01 2018-02 2018-03 2018-04 2018-05 2018-06 2018-07 2018-08 2018-09 2018-10 0 2500 5000 7500 10000 12500 15000 17500 En íos Figu a 5.2: G á ica de en íos desde la c eación de ¡Acep a el e o!. 5.2.1. Análisis del núme o de en íos Es a sección a a de analiza los da os con los que se a a ealiza la e aluación de nues os ecomendado es, pa a así pode en ende de an emano posibles si uaciones que se puedan encon a en las ecomendaciones du an e la ase de en enamien o y ene lo en cuen a a la ho a de ealiza el análisis de los esul ados. En la g á ica de la igu a 5.2, se mues a el núme o de en íos ealizados en ¡Acep a el e o! desde su pues a en ma cha el 17-02-2014 has a el 23-10- 2018. Fecha has a la cual enemos da os pa a la ealización de es e p oyec o. Se han ealizado un o al de 258.967 en íos, donde el 50 % de es os se ealizó an es de inales de ma zo de 2017, lo que signi ica que el o o 50 % ealizados pos e io men e se ha conseguido en la mi ad de iempo. El g an aumen o del núme o de en íos se debe a que con el iempo ¡Acep a el e o! se ha popula- izado más y más, sob e odo en el ámbi o de la Facul ad de In o má ica de la Uni e sidad Complu ense de Mad id, ya que los p o eso es que lo c ea on han sabido llama la a ención de los alumnos median e concu sos de p og a- mación, y la de o os p o eso es p oponiéndolo como una he amien a pa a que los alumnos puedan p ac ica los conocimien os adqui idos en clase. Se obse a en la g á ica que exis en a ios picos. Se epi e siemp e un pico al ededo de ma zo y o o en diciemb e. Es p obable que el núme o de en íos aumen e en esas echas debido a es concu sos de p og amación o ganizados po los undado es, AdaBy on,P og amaMe yLas 12 UVas. El pico que se suele epe i en oc ub e pod ía debe se a que as un mes desde el inicio de cu so en sep iemb e, los p o eso es p oponen p oblemas a sus alumnos y, como es habi ual, la mayo ía empieza a esol e los y luego g an pa e de ellos abandonan la pla a o ma o disminuyen su ac i idad. Capí ulo 6 Recomendado Bayesiano Resumen: Es e capí ulo desc ibe la implemen ación de un ecomen- dado p obabilís ico que aplica el eo ema de Bayes, la e aluación de dicho ecomendado en unción de unas mé icas y el análisis de los esul ados ob enidos con dichas mé icas. En los capí ulos an e io es se han desc i o dis in os ipos de SR, el juez online de ¡Acep a el e o! y di e en es mé icas que nos ayuden a comp oba si un ecomendado es á dando buenos esul ados. En es e, pasamos a de alla el modo en el que se han usado las ideas de los ecomendado es bayesianos pa a aplica es e ipo de ecomendación en ¡Acep a el e o!. Un ecomendado bayesiano es un SR que u iliza el eo ema de Bayes pa- a a e igua la p obabilidad que un elemen o le gus e a un usua io, basándose en el pe il de es e. Ob eniendo las p obabilidades de odos los elemen os se o denan de mayo a meno p obabilidad pa a ecomenda le los mejo es. Dicho pe il del usua io se puede ex ae del his o ial de en íos ealizados en ¡Acep a el e o!, ya que se nos ha p opo cionado una base de da os que con iene es a in o mación. A cada p oblema se le es ablece á un es ado pa a cada usua io. Hemos conside ado dos a ian es a la ho a de es ablece los es ados. Una de ellas oma á como es ados posibles pa a un p oblema: esuel o, in en ado (pe o no esuel o) y no in en ado. La o a a ian e con empla á solo dos es ados: esuel o y no esuel o (la unión de los in en ados y los no in en ados). Es os es ados es án desc i os en la sección 4.2. Den o de cada una de es as dos a ian es se ha decidido ealiza una ap oximación aplicando la es imación de Laplace y o a aplicando una es- imación a bi a ia. En consecuencia ob end emos cua o e siones de eco- mendado es bayesianos, las cuales se analiza án y se decidi á cual ha sido mejo pa a el caso conc e o de ¡Acep a el e o!. 31 32 Capí ulo 6. Recomendado Bayesiano 6.1. Implemen ación Como se eco da á de la sección 3.3.5, los ecomendado es bayesianos se basan en el eo ema de Bayes cuya ó mula, epe ida aquí pa a mayo cla idad, es: P(A|B0, ..., Bn) = P(B0, ..., Bn|A)·P(A) P(B0, ..., Bn)(6.1) También eco damos que el cálculo de P(B0, ..., Bn|A)de la ó mula an e- io es bas an e complejo. Po es e mo i o se ha omado la decisión de asumi que los sucesos B0, ..., Bnson independien es en e sí. En nues o con ex o, asumimos que la p obabilidad de que un usua io esuel a un p oblema Xes independien e de que esuel a el p oblema Y. Es o no es del odo cie o ya que p oblemas pa ecidos end án mayo p obabilidad de es a en el mismo es ado. Po an o, al inal la ó mula que usa emos, ambién epe ida po como- didad, es: P(A|B0, ..., Bn) = P(A)·Qn i=0 P(Bi|A) Qn i=0 P(Bi)(6.2) En el caso de nues o ecomendado : B0, ..., Bnes la in o mación conocida del pe il del usua io. Más con- c e amen e, Bies el es ado de esolución de cada p oblema del sis ema pa a el usua io al que es amos ecomendando. Aes el suceso cuya p obabilidad que emos conoce , en pa icula la p obabilidad de que el usua io con ese pe il sea capaz de esol e el p oblema A. En elación a los Bi, como se con ó en la sección 4.2, un p oblema puede es a , pa a un usua io, en los siguien es es es ados: Resuel os: el usua io ha ealizado uno o a ios en íos y al menos en uno de ellos ha ob enido AC. In en ados: el usua io ha ealizado uno o a ios en íos, pe o en ninguno de ellos ha ob enido como e edic o un AC. No in en ados: el usua io no ha ealizado ningún en ío, ya sea po que el p oblema le pa ece muy complicado o po que no lo ha leído oda ía. Es os es ados se pueden educi a “ esuel o / no esuel o” jun ando los es ados “in en ado / no in en ado” en el es ado “no esuel o”. 6.1. Implemen ación 33 Desde el pun o de is a de un ecomendado , nos hemos plan eado si la in o mación de sabe que un usua io ha acasado al esol e un p oble- ma (es ado “in en ado”) es o no signi ica i a, de modo que hemos hecho dos a ian es dis in as del ecomendado , cada una con un modelo de es ados dis in o. En el p ime o usamos la e sión simpli icada usionando los “in en- ados” con los “no in en ados”, de modo que los es ados son “ esuel o” y “no esuel o”. Llamamos a ese ecomendado “RN” po las siglas de ambos posi- bles es ados. El segundo end á en cuen a los es es ados y lo llama emos “RIN”, ambién po las siglas de los posibles es ados. Po o o lado, como se con ó en el capí ulo 3.3.5, al aplica la ó mula 6.2 nos encon amos con muchos P(Bi|A)que alen 0, causando que el esul ado inal sea ambién 0. Pa a a a es e p oblema hemos op ado po dos mane as dis in as. Una u ilizando la es imación de Laplace y la o a omi iendo los ce os. Si mezclamos las dos o mas de conside a los es ados con las dos mane as de a a los ce os ob enemos 4 posibles combinaciones que son las siguien es: RN: Se á el ecomendado que conside a dos es ados de un p oblema pa a un usua io y que aplica la es imación de Laplace. Las siglas ienen de los es ados “Resuel o” y “No esuel o”. RN-ce os: Es e ecomendado se di e encia á del an e io en la es ima- ción. En ez de aplica la es imación de Laplace, a la ho a de mul iplica igno a á los ce os. RIN: Al con a io que los an e io es, es e ecomendado conside a á los es es ados “Resuel o”, “In en ado” y “No esuel o”, de los que salen las siglas. También implemen a á la es imación de Laplace. RIN-ce os: Es e úl imo ecomendado conside a á los mismos es ados que el RIN, pe o igno a á los ce os en las mul iplicaciones igual que el RN-ce os. Pa a cada e sión dado un usua io con un pe il B0, ..., Bn, que emos calcula la p obabilidad de que es e esuel a cada uno de los eje cicios, es deci los P(A|B0, ..., Bn)pa a odos los p oblemas A, y o dena los de mayo a meno . Po la ecuación 6.2 an e io , es o signi ica que enemos que calcula la p obabilidad simple de cada p oblema y la p obabilidad condicionada de cada p oblema con cada p oblema, P(A)yP(Bi|A) espec i amen e. U iliza emos pa a ello la in o mación del pe il de odos los usua ios. El denominado , Qn i=0 P(Bi), es la p obabilidad de que haya un usua io con ese pe il y se calcula como la mul iplicación de las p obabilidades simples de los p oblemas Bi. 34 Capí ulo 6. Recomendado Bayesiano El denominado de la ecuación no depende en ningún caso del p oblema del que que emos sabe su p obabilidad. Po es e mo i o, pa a un mismo usua io el denominado a a ale siemp e lo mismo. Dado que el in úl imo es o dena las p obabilidades podemos omi i lo, pues no nos in e esa el alo exac o sino el o den ela i o. Si se quisie a ob ene la p obabilidad eal hab ía que calcula lo. Empezamos con la p obabilidad simple. U iliza emos la in o mación a p io i de la base de da os, que ha á las eces de “en enamien o” de nues o ecomendado . Se a a calcula como se mues a en la o mula 6.3, di idiendo la can idad de usua ios que han esuel o el p oblema Aen e el núme o de usua ios o ales. En la ó mula, U ep esen a al conjun o de usua ios, y E(A, u) ep esen a el es ado del p oblema Apa a el usua io ude los es ados desc i os an es. Según la e sión del ecomendado (“RIN” o “RN”) end emos más o menos opciones P(A) = |{u|E(A, u) == “R00}| |U|,∀u∈U(6.3) Po o o lado, la p obabilidad condicionada de Ahabiendo esuel o Bise calcula di idiendo el núme o de usua ios que ienen los dos p oblemas esuel- os, en e el núme o de usua ios que han esuel o Bi, independien emen e de que hayan esuel o o no el A, al como se mues a en la ó mula 6.4. También se ían necesa ias las ablas de p obabilidad condicionada de Ano habien- do esuel o Bi, y en el ecomendado “RIN” ambién es necesa io calcula la p obabilidad condicionada de Ahabiendo in en ado Bi. Es os cálculos se hacen aplicando análogamen e la misma ó mula, sus i uyendo donde pone “R00 en E(B, u) == “R00 po “N00 y po “I00 espec i amen e. P(Bi|A) = |{u|E(A, u) == “R00 ∧E(Bi, u) == “R00}| |{u|E(A, u) == “R00}| ,∀u∈U(6.4) De nue o, es o se calcula a pa i de los da os de en enamien o de la base de da os. En la p ác ica, muchas de las p obabilidades P(Bi|A)que hemos calculado dan como esul ado 0, po que hay pa ejas de p oblemas que no han sido esuel os simul áneamen e po el mismo usua io. Las e siones “RN-ce os” y “RIN-ce os” eliminan esos casos igno ándolos, o lo que es lo mismo, sus i uyendo el 0 po 1. Las o as e siones u ilizan la ap oximación de Laplace, que consis e en asumi que hay al menos un usua io que iene el p oblema Bien el es ado “R00, o o usua io en el es ado “N00, y en el “RIN” 6.2. Análisis de esul ados 35 o o en el “I00. Con es a mejo a la ó mula an e io queda inalmen e: P(Bi|A) =|{u|E(A, u) == “R00 ∧E(Bi, u) == “R00}| + 1 |{u|E(A, u) == “R00}| +x,∀u∈U dondex =(2,si RN 3,si RIN (6.5) Con odo es o, podemos calcula ya la p obabilidad que iene un usua io de esol e cualquie p oblema, que nos si en de base pa a la ecomendación. Pa a lle a a cabo los cálculos de las p obabilidades pa a los di e en es usua ios se á necesa io gene a ablas y ope a sob e ellas. Po ello, se ha omado la decisión de ealiza la implemen ación en Py hon ya que dispone de unas lib e ías llamadas Numpy yPandas McKinney (2011) con la que se op imizan los cálculos g acias a la pa alelización de es os. Dicha op imiza- ción es necesa ia, pues si se hicie a una implemen ación con las es uc u as básicas del lenguaje, hab ía que ealiza las ope aciones de o ma secuencial. Es o p o oca ía que con g andes can idades de da os las ope aciones a den un iempo excesi o. Po ejemplo, con los da os que se nos han p opo ciona- do después de 6h de ejecución aún no se hab ían ob enido esul ados. Sin emba go, u ilizando la lib e ía de Pandas el iempo o al de los cálculos se educe a una media de 7 minu os, pe o pa a ecomendaciones indi iduales el cos e de iempo es de 5 a 7 segundos. 6.2. Análisis de esul ados T as la implemen ación de las cua o a ian es del ecomendado baye- siano desc i as, se p ocede a analiza los esul ados ob enidos pa a cada una de las mé icas. Se compa a án siemp e las di e en es implemen aciones (RN, RIN,RN-ce os yRIN-ce os), a in de es udia cuál de ellas p ome e mejo es esul ados. La e sión ganado a se á la que se u iliza á pa a compe i con la mejo e sión del ecomendado po pesos de los K-Vecinos que se explica á en el p óximo capí ulo. Pa a isualiza mejo los da os los mos a emos en g á icas. El eje ho- izon al ep esen a el núme o de p oblemas ecomendados. El eje e ical indica el alo de la mé ica co espondien e. 6.2.1. P ecision La g á ica 6.1 pe mi e compa a la p ecisión de las cua o a ian es del ecomendado con dis in o núme o de p oblemas ecomendados al usua io. Lo p ime o a des aca es la línea del SR RN-ce os, pues o que es la única que iene una o ma dis in a y empieza en un alo de 0.001 como mues a 36 Capí ulo 6. Recomendado Bayesiano 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 12345678910 P ecision Can idad de p oblemas ecomendados RIN RIN-ce os RN RN-ce os Figu a 6.1: G á ica compa ación de p ecisiones. la abla 6.1 mien as que los o os es ecomendado es empiezan con alo es supe io es a 0.25. An es de explica el po qué es e alo es an bajo, hay que en ende qué signi ica que sea an bajo y luego suba ápidamen e. Según la de inición de p ecision, una subida en la p ecisión signi ica ía que se han ecomendado p oblemas de bajo in e és al usua io an es que los de al o in e és. Y es es o lo que ha ocu ido con el RN-ce os, se ha ecomendado a casi odos los usua ios en p ime luga el p oblema de El p o eso de música, el cual en la ase de en enamien o había sido esuel o po un único usua io, y en la de e aluación po 2. Resul a que es e p oblema es bas an e complicado, pe o como lle aba poco iempo en ¡Acep a el e o! al aba in o mación. Al calcula la p obabilidad de que un usua io con pe il B0, ..., Bn esuel a lo esuel a, enemos: P(Musica|B0, ..., Bn) = n Y i=0 P(Bi|Musica)·P(Musica) = P(Musica) Los posibles alo es pa a P(Bi|Musica)dado que solo un usua io lo ha esuel o son 0 si Bino lo ha esuel o y 1 si lo ha esuel o. Es e usua io en 6.2. Análisis de esul ados 37 12345678910 RN 0.314 0.249 0.202 0.172 0.158 0.147 0.141 0.137 0.131 0.130 RIN 0.288 0.224 0.178 0.156 0.141 0.135 0.124 0.119 0.112 0.107 RN-ce os 0.001 0.155 0.164 0.150 0.136 0.131 0.125 0.122 0.121 0.118 RIN-ce os 0.291 0.224 0.177 0.155 0.140 0.134 0.123 0.118 0.110 0.106 Tabla 6.1: Tabla p ecision conc e o enía casi 300 p oblemas esuel os y solo había in en ado 1 sin éxi o. Po lo an o, la o mula an e io aplicada a es e usua io queda ía: P(Musica|B0, ..., Bn)=1·... ·1·P(Musica) = P(Musica) En los ecomendado es que aplican la es imación de Laplace (RN yRIN ) al conside a que exis e al menos un usua io pa a cada es ado, ya no exis e la posibilidad de que P(Bi)sea ni 1 ni 0, sino que es os se ans o ma ían 0.666 y 0.333 pa a el RN, y en 0.5 y 0.25 pa a el RIN. Es o hace que ya no es é en la p ime a posición. En RIN-ce os no ocu e es e p oblema po que al conside a los p oblemas in en ados se a o ece mucho la p obabilidad de esol e p oblemas áciles pues hay muchos di íciles in en ados habiendo esuel o áciles. Po ello aun- que El p o eso de música ob enga igualmen e p obabilidades al as, los áciles ob ienen mayo es p obabilidades y son ecomendados p ime o. En el ecomendado RN se ha aplicado la ap oximación de Laplace y po eso la es imación ha p o ocado que los ce os que con ie an en o os decimales, educiendo así mucho la p obabilidad de que es e sea esuel o y po an o pasando a se ecomendado bas an e más a de, y dejando en los p ime os luga es los e dade amen e más p obables. Es po eso que el ecomendado RN ob iene unos alo es de p ecision según lo espe ado, con o ma descenden e. Que el alo inicial sea 0.31, apa en emen e bajo, puede debe se al hecho de que en ealidad no se ha ecomendado nada al usua io sino que es una p edicción de su compo amien o (sección 5.2). Así mismo, se obse a que las líneas de p ecision de los ecomendado- es RIN yRIN-ce os, son p ác icamen e coinciden es y que ambas siguen la o ma espe ada, al igual que el ecomendado RN. An es de es udia es a casi coincidencia amos a empeza explicando po qué en el ecomendado RIN-ce os no ocu e igual que en el RN-ce os, donde el p ime p oblema ecomendado no es el más adecuado. Pod íamos pensa que se debe a que la p obabilidad de esol e es e p oblema se educe al conside a los in en ados. Sin emba go no es así. La p obabilidad de esol e lo es exac amen e la mis- ma, pues o que en la ase de en enamien o el único usua io que esol ió dicho p oblema, ambién es el único que ealizó un en ío. En onces, queda pensa que la p obabilidad de esol e o os p oblemas ha aumen ado. En e ec o, 38 Capí ulo 6. Recomendado Bayesiano 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 1 2 3 4 5 6 7 8 9 10 One-Hi Can idad de p oblemas ecomendados RIN RIN-ce os RN RN-ce os Figu a 6.2: G á ica compa ación de one-hi . al ene en cuen a los p oblemas in en ados se ob ienen unas p obabilidades más al as pa a algunos p oblemas. Es ambién po es o que la ap oximación de Laplace hace a ia mínimamen e las p obabilidades inales, y en con- secuencia los ecomendado es RIN yRIN-ce os ealizan ecomendaciones p ác icamen e idén icas. 6.2.2. One-hi Al con a io que en la mé ica p ecision, el one-hi se espe a que enga una endencia ascenden e, dado que es ob io que cuan os más p oblemas sean 12345678910 RN 0.314 0.390 0.427 0.457 0.485 0.509 0.550 0.603 0.620 0.632 RIN 0.288 0.352 0.382 0.420 0.443 0.458 0.466 0.503 0.509 0.525 RN-ce os 0.001 0.311 0.387 0.426 0.457 0.484 0.509 0.550 0.604 0.621 RIN-ce os 0.291 0.352 0.382 0.420 0.442 0.461 0.471 0.506 0.512 0.528 Tabla 6.2: Tabla one-hi 6.2. Análisis de esul ados 39 12345678910 RN 0.039 0.061 0.075 0.085 0.098 0.109 0.122 0.136 0.146 0.161 RIN 0.035 0.055 0.066 0.077 0.087 0.101 0.108 0.118 0.125 0.133 RN-ce os 0.000 0.038 0.061 0.074 0.084 0.097 0.109 0.121 0.136 0.146 RIN-ce os 0.036 0.055 0.066 0.076 0.086 0.099 0.107 0.117 0.123 0.131 Tabla 6.3: Tabla Recall ecomendados más posibilidades hay de que al menos uno sea del ag ado del usua io. En la igu a 6.2 se comp ueba que es o se cumple. P ime amen e se obse a que se cumple que con un p oblema ecomen- dado one-hi yp ecision son iguales. Se des aca el mismo alo p óximo a ce o del ecomendado RN-ce os, cuya explicación es equi alen e a la dada en el apa ado an e io . Del mismo modo, la casi coincidencia del one-hi de RIN yRIN-ce os, se debe a que ealizan p ác icamen e las mismas ecomen- daciones, como se explica al inal del apa ado an e io . El ecomendado encedo uel e a se el RN que alcanza un one-hi del 50 % al ecomenda 6 p oblemas y del 63 % al ecomenda 10 p oblemas. Lo que hace pensa que el hecho de conside a las p obabilidades de esol e un p oblema habiendo in en ado o os, como es el caso de los ecomendado es RIN, en luga de a o ece a la ecomendación como se espe aba que hicie a, la empeo a lige amen e. Si con la p ecisión se espe a que aumen e al inclui el ecomendado en ¡Acep a el e o!, del mismo modo se espe a que aumen e ambién el one-hi , lo cual es espe anzado . 6.2.3. Recall Es de espe a que desde el co e de la base de da os has a el inal los usua- ios hayan esuel o muchos p oblemas, y po ello ob ene alo es de ecall bajos no signi ica habe ealizado malas ecomendaciones, como se explica en la sección 5.1 con la de inición de ecall. En es e caso conc e o es amos e aluando ecomenda has a 10 p oblemas. Pues bien, a pa i del co e hay 720 usua ios que han esuel o más de 10 p oblemas, y en e ellos suman un o al de 18.512 p oblemas esuel os. Si asumié amos que los diez p ime- os p oblemas esuel os de cada uno de ellos ha sido ambién ecomendado, suma ían 11.512 p oblemas esuel os pe o no ecomendados. Una ez más se ob ienen alo es simila es pa a los ecomendado es RIN yRIN-ce os, es de espe a como ya se ha mencionado an e io men e. Igual- men e pasa con el ecomendado RN-ce os que empieza en un alo muy p óximo a ce o. Y de nue o el ecomendado RN es el que ob iene mejo es esul ados. 46 Capí ulo 7. Recomendado de pesos po los K-Vecinos más simila es Figu a 7.3: Relaciones en e usua ios (nodos), según la can idad de p oblemas esuel os en común (g oso de la línea) en ¡Acep a el e o!. caó ico y poco ú il un ejemplo con can idades mayo es. El ecomendado po pesos de los K-Vecinos más simila es, analiza un juez en línea como las dos úl imas igu as mencionadas, calculando ese es ilo de elaciones (en e usua ios) a pa i de da os como los que la igu a 7.1 ep esen a. Po lo gene al, es e algo i mo ecomenda á p oblemas pe sonalizados a un usua io según los p oblemas ealizados po sus ecinos, de al o ma que po un lado el ecomendado asegu a que el usua io a se ecomendado end á buena asa de éxi o al esol e un p oblema de los ecomendados, y po o o lado, se da una ecomendación pe sonalizada basada en el c i e io de usua ios simila es a es e, que han esuel o o os p oblemas que aún no ha ealizado el usua io a ecomenda y es la simili ud en e usua ios la que le da un peso impo an e a esos p oblemas no esuel os aún po el usua io al que se le a a ealiza la ecomendación. Se puede conside a po lo an o, que a pa e de ese éxi o al o, se es á ealizando una ecomendación po gus os de usua ios, ya que si un usua io simila a mí ha que ido hace un p oblema y lo ha conseguido, segu amen e yo ambién enga ganas de in en a el mismo p oblema y ambién pueda 7.1. Funcionamien o del ecomendado po K-Vecinos más simila es 47 consegui lo. 7.1. Funcionamien o del ecomendado po K-Vecinos más simila es Como ya se ha comen ado, es e ecomendado iene simili udes con los Nea es Neighbo hood Hall e al. (2008) mencionado en la sección 3.3.1. La di e encia de es e ecomendado es, que as ob ene los ecinos más ce - canos, es os no se usan pa a clasi ica en clases al usua io y gene a una ecomendación en base a la clase donde se ha clasi icado. Se usa la co ela- ción que de e mina la dis ancia de los ecinos, y se aplica es a co elación pa a asigna pesos a los p oblemas que ienen los ecinos y que el usua io a ecomenda no ha in en ado. El ecomendado in e namen e maneja una ma iz donde sus ilas e- p esen an los usua ios, sus columnas los p oblemas, y el alo ila/columna in o ma del es ado. En es e caso el alo dispone únicamen e de dos es ados: conseguido, o el es o de casos que se conside an como no conseguido. Es e es o de casos incluyen en el mismo conjun o, el caso de un usua io que ha in en ado pe o no esuel o un p oblema, y el caso en el que el usua io ni si quie a ha in en ado ealiza lo. El ecomendado ealiza el siguien e algo i mo: Al usua io a ecomenda se le llama á: Owne = O. Pa a un “O”, ob enemos una lis a de los K usua ios más simila es con su co elación co espondien e. Es a lis a se ob iene calculando la co e- lación pa a cada usua io βide la base de da os, con O. Pos e io men e se o dena de mayo a meno . El cálculo de la co elación en e βiyOse basa en, dados los elemen os: •ρO =Conjun o de p oblemas de Owne •ρβi=Conjun o de p oblemas de usua io βi Aho a se de ine la co elación en e dos usua ios como: Co elacion =|ρβiTρO| |ρO|(7.1) T as es e cálculo pa a cada usua io de la base de da os, ob enemos aquellos Nusua ios (βN) con co elación más al a, que ep esen a án los N ecinos más ce canos y c eamos un Dicciona io(D) cuya cla e sea el id del p oblema y el alo indique el peso de la ecomendación. 48 Capí ulo 7. Recomendado de pesos po los K-Vecinos más simila es Es e dicciona io se usa pa a el cálculo de pesos de los p oblemas, pa a después se o denados po es e peso al c ea la lis a de ecomendación. El peso de la ecomendación se de ine inalmen e de la siguien e mane- a: •ρi=P oblema “i” del conjun o de p oblemas exis en es P. ∀ρi/∈ρO → N X j=0 co elacion(βj, O) Nsii ρi∈ρβj(7.2) Al di idi po N, se asegu a que el esul ado nunca sea mayo que 1. El suma o io se ealiza en cada posición del dicciona io co espondien e a cada ρi. Finalmen e se o dena el dicciona io esul ado po los alo- es, ob eniendo una lis a de ecomendación o denada con unos pesos asignados. Como se puede obse a , la ó mula que de ine la co elación es la que nos si e pa a encon a los ecinos más ce canos según esa no ma, y queda nos con los Kmejo es/más simila es. Po o o lado, pa a ob ene la ecomendación en sí, se buscan los p oble- mas que cada K-Vecino ob enido ha esuel o pe o el usua io a ecomenda no, y se o denan según una combinación en e la co elación de cada usua- io y las eces que ese p oblema se epi e en el es o de ecinos (es o es, el cálculo de los pesos de los p oblemas). 7.2. Op imización y modi icaciones An es de en a di ec amen e en es e pun o, cabe des aca que el es u- dio de la acele ación se ha ealizado siemp e bajo las mismas condiciones de ejecución en es e ecomendado , pe o no pa a ambos ecomendado es eali- zados. Es as condiciones de ejecución son las siguien es: P ocesado : In el(R) Co e(TM) i7 860. •F ecuencia: 2.80GHz •Núme o de núcleos: 4 RAM: 8 GB GPU: NVidia Ge o ce 1050Ti GTX 4GB DRR SO: Windows 10 p o Almacenamien o de in o mación: Disco du o con encional 7.2. Op imización y modi icaciones 49 Habiendo indicado con mayo cla idad las condiciones bajo las que se ha es ado ejecu ando el ecomendado , amos a habla en adelan e de iempos y la acele ación de las mejo as. La p ime a e sión del algo i mo abaja con consul as di ec as sob e la BD de ¡Acep a el e o!. Es a, pa a los casos de usos eales, es una opción len a y no e icaz además de cos osa y puede hace que llegue a sa u a una base de da os que no es á pensada pa a in o ma di ec amen e al ecomendado . Se han ealizado nue as e siones mejo adas pa a log a abs ae es a in o mación y ene la en el ecomendado de mane a local. Es e paso, es necesa io si se quie e ene el ecomendado como se icio ex e no y que si a ambién pa a po a lo a o os jueces en línea sin gene a dependencias de la pla a o ma ¡Acep a el e o!. Po lo an o, pa a es a mejo a, se op a po abaja con una ma iz de da os en local que se ca gue en memo ia al a anca el se icio ealizando las ac ualizaciones pe inen es en memo ia y haciendo sus olcados al sis ema de a chi os donde es é alojado el ecomendado . La ma iz de da os ep esen a los usua ios y p oblemas en base a sus ilas y columnas de al o ma que cada posición ila de la ma iz ep esen a un id de usua io y cada posición columna ep esen a un id de p oblema. Al abaja con Py hon, se ap o echa la e icacia y endimien o que iene Numpy sob e ma ices. A di e encia del ecomendado Bayesiano que como se ha comen ado en el an e io capí ulo, abaja con Pandas pa a pode asigna le una cla e a cada posición de ila y cada posición de columna, como Numpy no pe mi e es o, se han c eado dos a ays de con e sión: Uno pa a las ilas y o os pa a las columnas. Las posiciones de es e a ay se co esponden a las de la ma iz, y el alo de cada posición nos pe mi e conoce el ID de usua io/p oblema asociado a es e. La elección de Numpy en es e ecomendado , espec o al uso de Pandas en el o o, es me amen e la de pode con as a di e encias en el uso de ambas ecnologías, y el in e és o ma i o que equie e in en a desa olla ambos ecomendado es con ecu sos di e en es. Cabe des aca que el con ol de ob ención, ac ualización y man enimien o de la in o mación se abs ae en una clase que se ocupa de es os p ocesos pa a que el ecomendado simplemen e se enca gue de hace lec u as sob e es a ma iz1. Es a implemen ación y los cambios mencionados pa a es a e sión del ecomendado , mejo a el iempo de cálculo po en ega en 5 espec o a la p ime a que se ha comen ado2. (Se pasan de ob ene iempos de 5 minu os po ecomendación a 1 minu o). Aún así es necesa io segui op imizando el iempo de ecomendación, ya que sigue siendo muy al o. Pa a consegui es a mejo a se ap o echa odo lo 1La a qui ec u a y es uc u a del ecomendado se habla á en la sección 7.3 2Es amos hablando de la acele ación 50 Capí ulo 7. Recomendado de pesos po los K-Vecinos más simila es que o ece Numpy en cuan o a pa alelismo. Pa a mejo a cie as ope aciones, sob e la ma iz, que se ealizan de ma- ne a secuencial se ep og aman a eas pa a que uncionen en pa alelo, ob- se ando que a ias ope aciones (p incipalmen e de inse ción, es a de con- jun os, in e sección de conjun os...) mejo an sus ancialmen e median e los ope ado es y mé odos que o ece Numpy. Realizando es as modi icaciones se alcanza la e ce a e sión del eco- mendado , la cual ob iene una mejo a de al ededo de 120, sin ni si quie a ap o echa el endimien o máximo de p ocesamien o que el disposi i o de p uebas o ece. T as la mejo a, en es a úl ima e sión, el ecomendado pasa a ecomen- da en menos de 1 ( iempos en e 0.1 y 0.7 segundos). Es as mejo as se han medido con la base de da os pa cial co ada a 2018. Po lo que con los egis os a día de hoy, el iempo de ecomendación aumen a ía un poco a medida que los usua ios y p oblemas c ecen, pe o de mane a lineal y poco signi ica i a. Con es os nue os esul ados a o ables, a al a de in es iga con más p o undidad qué nue os cuellos de bo ella puedan su gi , la op imización es al amen e sa is ac o ia y no se ha conside ado necesa io, po el momen o, con inua con es a línea de in es igación. 7.3. A qui ec u a y es uc u a in e na Aunque el capí ulo 9 a a á de la a qui ec u a de comunicación y ac- ualización de ambos ecomendado es, se menciona aquí some amen e de la a qui ec u a in e na de es e ecomendado . Es deci , es a sección se cen a en a a con más de alle, cómo unciona in e namen e la comunicación en e clases, de la pa e in e na del ecomendado , dejando de lado la pa e de la API y es uc u as de ni el supe io que pe mi en hace del ecomendado , un se icio ex e no y ac ualizable. Es e ecomendado se ha seccionado en dos clases, mos adas en la igu- a 7.4, las cuales se encuen an sepa adas en dos iche os di e en es. Es as dos clases su gen de la necesidad de abs ae la pa e de ges ión de la BD in e na con la pa e del algo i mo de ecomendación. La lógica elacionada con el almacenamien o de da os, es á ag upada en un iche o que con iene po un lado pa áme os de con igu ación pa a hace la conexión adap a i a de mane a cómoda y ápida a di e en es jueces en línea, y po o o lado, con iene la clase JuezDB, mos ada en la igu a 7.4. Es a clase es á enca gada de los siguien es aspec os: Ca ga la ma iz de ecomendación en memo ia de mane a que si no exis en los iche os en local, los ca ga desde una BD MySQL y los gua da en local pa a ca ga los, a pa i de en onces, desde ese almace- 7.3. A qui ec u a y es uc u a in e na 51 Recomendado K ecinos + Ma izDa os:NumpyMa ix + conexionDB:JuezDB + g ado:in + use IDowne :in + use PosOwne :in + Recomendado K ecinos(db:JuezDB) + ecomenda (use IDowne ,g adoSimili ud):Dic iona y - co elacion(use ): double - calcula TamP oblemasUse (posUse ): in - il a NMasSimila es(can idad):Ma ix - busca P oblemasComunes(use ):Lis - amP oblemasComunes(use ):in - busca P oblemasUse 2MinusOwne (use ):Lis JuezDB +Ma izDa os:NumpyMa ix -Lis aUsua ios:Lis -Lis aP oblemas:Lis -Las Submi ion:in ... -gua da Ma izEnLocal() -ca ga Ma izDesdeLocal() +ob ene Ma iz():NumpyMa ix +ob ene PosUse (idUse ):in +ac ualiza En egas(nue asEn egas,ul imaEn ega) ... Figu a 7.4: Diag ama de clases in e nas del ecomendado K-Vecinos, sim- pli icando a ibu os y mé odos más in e esan es. namien o. En caso de que exis an los iche os en local los ca ga di ec amen e ya que supone meno cos e y es es e el con enedo eal de la in o mación del ecomendado . Es a ca ga ambién incluye in o mación que pa sea las posiciones de ilas/columnas que ep esen an usua ios y p oblemas, a sus espec i os IDs. Aunque pa a el caso de los p oblemas y en el juez en línea de ¡Acep a el e o! se abajan con los Ex e nal ID, que co esponden di ec amen e a la posición en la ma iz más cien. La ca ga desde la BD solo se debe hace pa a ca ga po p ime a ez la in o mación al ecomendado . A pa i de ahí siemp e abaja á desde local sin depende de una BD ex e na. Ac ualiza la BD en memo ia y en local cada ez que se le llame al mé odo “ac ualiza En egas”. Es a ac ualización se llama desde la clase clien ePe iciones y se enca ga de lee lo que clien ePe iciones le pasa po pa áme o pa a hace los cambios en la ma iz y los a ays co espondien es, añadiendo nue as ilas/columnas y elemen os, así como modi ica los alo es de la ma iz 52 Capí ulo 7. Recomendado de pesos po los K-Vecinos más simila es de da os sob esc ibiendo las posiciones en las que haya nue os AC a uno. Pa sea la in o mación de la ma iz de da os a quien se lo solici e, de ol iendo el id de usua io asociado a una posición, y ice e sa. En cuan o a la clase Recomendado Basico del iche o con el mismo nom- b e, se la inicializa con una ins ancia de la clase JuezDB, pa a ob ene de ahí la ma iz asociada. Su p incipal mé odo es “ ecomenda ”, al que se le asocia un id de usua io y el pa áme o de K-Vecinos con el que se quie e ealiza la ecomendación. Es e mé odo llama a o os mé odos, que si bien pueden se in ocados ex e namen e, ienen un in de uso de mé odos p i ados pa a la p opia clase. El mé odo “ ecomenda ” de uel e al solici an e un lis ado de ecomen- dación as ejecu a el algo i mo explicado en la sección 7.1. El es o de mé odos mos ados en la igu a 7.4 pa a la clase ecomendado básico, son p opios del algo i mo explicado y no me ecen p o undiza en ellos en es a sección. 7.4. En enamien o y e aluación En es a sección se habla sob e el en enamien o ealizado en el eco- mendado , haciendo un análisis de los esul ados de es e en enamien o y la e aluación ob enida de las di e en es mé icas desc i as en el capí ulo 5. En pa icula , las mé icas que se han ob enido de la e aluación son el “p ecision”, el “One-Hi ”, el “ ecall” y inalmen e el “F-Sco e”. Pa a cada ipo de mé ica se han gene ado dos modelos de g á icas que ep esen an di e en es con igu aciones del ecomendado y conjun os de N mejo es p oblemas ob enidos. 7.4.1. Resul ados de P ecision Comenzando a analiza los da os del “P ecision” se ob u ie on los esul- ados de e aluación de la abla 7.1 as el en enamien o. En la abla 7.1 mencionada, las ilas ep esen an los pa áme os del eco- mendado , ya que se ealizó el en enamien o pa a di e en es pa áme os de K-Vecinos más simila es. Po o o lado, las columnas ep esen an la can idad de p oblemas que se ob ienen de la lis a de ecomendación, que se han enido en cuen a a la ho a de e alua . Los esul ados del pa áme o de con igu ación del ecomendado pa a “P ecision” se an a analiza mejo a a és de la igu a 7.5. En la g á ica de la igu a 7.5 mencionada, se mues a como cada TOPN 3, 3Top N ep esen a los N mejo es p oblemas que hemos cogido pa a e alua . 7.4. En enamien o y e aluación 53 12345678910 3 0.116 0.114 0.108 0.111 0.111 0.104 0.100 0.097 0.095 0.093 10 0.195 0.163 0.153 0.165 0.156 0.150 0.151 0.144 0.139 0.134 20 0.173 0.164 0.159 0.160 0.156 0.150 0.144 0.142 0.141 0.138 50 0.187 0.179 0.170 0.167 0.161 0.159 0.154 0.149 0.147 0.144 100 0.180 0.183 0.173 0.167 0.161 0.157 0.153 0.151 0.147 0.143 250 0.172 0.154 0.154 0.145 0.145 0.143 0.142 0.139 0.137 0.134 500 0.148 0.149 0.147 0.146 0.148 0.144 0.143 0.138 0.134 0.131 1000 0.142 0.137 0.139 0.143 0.144 0.139 0.137 0.132 0.127 0.125 2000 0.131 0.128 0.138 0.144 0.140 0.135 0.134 0.130 0.127 0.124 5000 0.133 0.129 0.140 0.145 0.140 0.136 0.134 0.130 0.127 0.123 all 0.133 0.129 0.140 0.145 0.141 0.136 0.135 0.130 0.127 0.123 Tabla 7.1: Tabla de esul ados de P ecision pa a el SR K-Vecinos. ma cados con una di e en e línea, a ía según los pa áme os de ecomenda- ción que se le asignen al algo i mo K-Vecinos más simila es. Se obse a cómo la ecomendación pa a cualquie N, a medida que el pa áme o de ecomendación se ap oxima a los 10 ecinos más simila es la p ecisión c ece, po lo que se en iende que el uncionamien o del ecomenda- do iende a mejo a con lige as luc uaciones. Esa mejo a du a has a que se supe an los 100 ecinos más simila es, donde se obse a cómo desciende lige amen e la p ecisión. Po lo an o, el in e alo óp imo pa a K-Vecinos más simila es es á en el ango en e 10 y 100. Es o sucede po que al inclui ecinos menos simi- la es con el usua io a ecomenda se dis o siona lige amen e la in o mación de los p oblemas que ealmen e el usua io necesi a. De mane a que si se iene en cuen a una simili ud baja de un ecino más simila con el usua io, desencadena á en una ecomendación peo . La g á ica 7.6 ep esen a en el eje de abscisas la can idad de ecomen- daciones que pedimos al ecomendado (Mejo es N ecomendaciones), y el eje de o denadas ep esen a el p opio alo de la p ecisión al igual que en la g á ica analizada p e iamen e. Las líneas ep esen an cada pa áme o de con igu ación K-Vecinos4. En es a g á ica (7.6) se puede obse a que la p ecisión disminuye a me- dida que el eje de las “x” c ece. Es o se debe a la na u aleza de la ó mula de p ecisión y la o ma de como se han ob enido los TP,FP yFN, p o oca una endencia a disminui , en nues o caso, a pa i de x > 3. Sin emba go, pa a N = 2 y N = 3 no se obse an en conjun o esos dec emen os apenas. Los alo es se man ienen y en algunos casos incluso se 4Aunque no se ha mencionado an es, se han seleccionado esos pa áme os como más ep esen a i os como una mane a inc emen al in e esan e donde duplicamos el pa áme o en cada con igu ación espec o al an e io , pe mi iéndonos e en di e en es g ados cómo a ec a dicho pa áme o. 54 Capí ulo 7. Recomendado de pesos po los K-Vecinos más simila es 0 0,05 0,1 0,15 0,2 0,25 3 10 20 50 100 250 500 1000 2000 5000 all P ecisión K-Vecinos 1 2 3 4 5 6 7 8 9 10 Figu a 7.5: G á ica de p ecisión 1. ob ienen mayo es p ecisiones. De es a g á ica se ob iene como in o mación concluyen e que un alo óp imo a ene en cuen a a la ho a de ecomenda se ía u iliza los 3 mejo- es p oblemas, ya que, a medida que seguimos incluyendo p oblemas de es a lis a o denada de ecomendación, esos p oblemas nue os que se inco po an, cada ez ienen menos peso: son p oblemas que, aunque se incluyan, el e- comendado conside a que iene menos éxi o de que el usua io sea capaz de in e esa se po ellos y de esol e los. Es o sucede, a pesa de que el conjun o de p oblemas a ecomenda sea mayo y po lo an o engamos más p obabilidades en ecomenda p oblemas exi osos. De odas o mas, como es os dos concep os se con aponen, apenas se no a ese dec emen o que implica ob ene p oblemas con menos peso, ya que como el conjun o de p oblemas que se ecomienda es mayo , el ecomendado puede que acie e más al ene mayo ango de éxi o. Se puede conclui que la o ma en la que se ob iene la p ecisión pa a cada Top N p oblemas, es la in luyen e en los esul ados de es e dec ecimien o, al igual que pasa á de mane a simila en las p óximas g a icas del es o de mé icas. Según lo dicho, es a segunda g á ica pa a e alua independien emen e los p oblemas, no es an in e esan e pa a nues o ecomendado , pe o sí pa a compa a la con o os ecomendado es y con on a los esul ados. 7.4. En enamien o y e aluación 55 0 0,05 0,1 0,15 0,2 0,25 1 2 3 4 5 6 7 8 9 10 P ecisión Can idad de p oblemas ecomendados 3 10 20 50 100 250 500 1000 2000 5000 all Figu a 7.6: G á ica de p ecisión 2. Es o ambién se analiza á mejo más adelan e en un capí ulo pos e io , aunque educiendo el conjun o de da os de es e ecomendado a los que han esul ado más in e esan es du an e el análisis. 7.4.2. Resul ados del One-Hi La abla de esul ados se mues a en la igu a 7.2. De es a abla (7.2), al igual que se ha hecho con la p ecisión, se han gene ado las dos g á icas de las igu as 7.7 y 7.8. Como ya se ha comen ado en o as secciones y capí ulos, el “One-Hi ” ep esen a ene al menos un acie o en el conjun o de p oblemas ecomen- dados. Analizando la g á ica 7.7 pa a el “One-Hi ”, se obse a que el conjun o de TOPN a ía de o ma simila pa a es e concep o a medida que se aplica el algo i mo de ecomendación incluyendo más ecinos simila es. El compo amien o que nos mues a la g á ica es el mismo con el que concluimos el de la p ecisión, y es que pa a unos alo es de K-Vecinos en e 10 y 100 ob enemos los máximos “One-Hi ” p ác icamen e. Se obse a ambién que pa a alo es meno es a 10 la unción g á ica es c ecien e y pa a alo es mayo es a 100 la g á ica empieza a dec ece . Lo que cambia aquí espec o a la p ecisión es que las líneas es án a di e en es ni eles (a pa e de la ob iedad de que los alo es ob enidos son más Capí ulo 8 Compa ación en e ecomendado es Resumen: Una ez seleccionadas las mejo es e siones de los eco- mendado es an e io men e desc i os nos disponemos en es e capí ulo a compa a las con el in de comp oba cuál de las dos se ajus a más al juez online ¡Acep a el e o!. T as habe implemen ado dos ipos de ecomendado es, bayesiano yK- Vecinos, y habe ealizado una e aluación de las di e en es e siones, se ha seleccionado la e sión más p ome edo a de cada uno. El obje i o es com- pa a ambos esul ados en base a las mé icas desc i as con el obje i o de conclui cuál de los dos ipos de ecomendación se ía más iable den o del sis ema de ¡Acep a el e o!. El que mejo es esul ados ob enga se á el p ime candida o a se lle ado a e aluación en un caso eal con usua ios. Las e siones seleccionadas han sido: Bayesiano: se ha seleccionado la e sión RN, que conside a dos es ados y aplica la es imación de Laplace. K-Vecinos: la e sión ganado a de es e SR has sido la que conside a los 100- ecinos más simila es. Al igual que en los capí ulos an e io es los esul ados se mos a án en g á icas. El eje ho izon al se co esponde á con el núme o de p oblemas e- comendados, mien as que el eje e ical ep esen a á el alo de la mé ica co espondien e. 8.1. P ecision En la igu a 8.1 se mues a la g á ica de p ecision. Es muy des acable la di e encia cuando el núme o de p oblemas ecomendados es 1. El eco- 63 64 Capí ulo 8. Compa ación en e ecomendado es 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 1 2 3 4 5 6 7 8 9 10 P ecision Can idad de p oblemas ecomendados Bayesiano K-Vecinos Figu a 8.1: G á ica de compa ación de p ecision mendado bayesiano ob iene un esul ado casi un 60 % supe io al esul ado del ecomendado K-Vecinos. Lo que signi ica que el p ime p oblema que p opone el ecomendado bayesiano es bas an e mejo que la del o o. Sin emba go, al i ecomendando más p oblemas la p ecisión del eco- mendado bayesiano cae ápidamen e, mien as que el ecomendado K- Vecinos es bas an e más es able y cae más len amen e, incluso p esen a alguna subida. Es al la di e encia en la elocidad de caída que cuando se ecomiendan 5 p oblemas el ecomendado que iene mayo p ecisión aunque po poca di e encia es el K-Vecinos. Es o pa ece se debido a que el ecomendado bayesiano ha ecomendado mayo i a iamen e como quin a opción el mismo p oblema a odos los usua- ios, mien as que el ecomendado K-Vecinos ha ecomendado p oblemas di e en es a muchos de ellos. Que sea un p oblema sencillo y muy p obable de se esuel o po odos los usua ios no quie e deci que el p oblema sea in e esan e pa a el usua io. Po ello pa ece se más ace ada una ecomen- dación de p oblemas más dis ibuida y más pe sonalizada a cada usua io. 8.2. One-hi Al con a io que en la mé ica p ecision, el cla o y cons an e encedo en one-hi es el ecomendado bayesiano. Es e ecomienda p oblemas áciles de esol e pa a el usua io y po ello es más p obable que sea esuel o. El 8.3. Recall 65 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 1 2 3 4 5 6 7 8 9 10 One-Hi Can idad de p oblemas ecomendados Bayesiano K-Vecinos Figu a 8.2: G á ica de compa ación de one-hi ecomendado K-Vecinos, al pe sonaliza más la ecomendación no llega a ecomenda los más áciles, sino alguno más in e esan e pa a el usua io, po ello le cues a más ene al menos un acie o. Aun así, como se mues a en la igu a 8.2, la di e encia en el alo de one-hi no es muy g ande, po lo que ambos ecomendado es ienen un g an po cen aje de acie o en al menos una ecomendación. 8.3. Recall Los esul ados ob enidos de ecall se mues an en la igu a 8.3. Al igual que en los esul ados de one-hi , se obse a que el ecomendado bayesiano uel e a es a po encima en odo momen o del ecomendado K-Vecinos. Los alo es de ecall son apa en emen e bajos como ya se explicó an e io men e po el hecho de que hay muchos más p oblemas esuel os que ecomendados. Aunque en la g á ica pa ezca que las líneas es án muy dis an es, si obse - amos los alo es en las ablas co espondien es (39 y 58) la di e encia oscila en e 2 y 5 cen ésimas po lo que en ealidad es án bas an e a la pa aunque si es e dad que el ecomendado bayesiano oma en aja. 66 Capí ulo 8. Compa ación en e ecomendado es 0 0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.16 0.18 1 2 3 4 5 6 7 8 9 10 Recall Can idad de p oblemas ecomendados Bayesiano K-Vecinos Figu a 8.3: G á ica de compa ación de ecall 8.4. F-Sco e No es de ex aña que con la mé ica -sco e se ob enga una g á ica en la que ambién el ecomendado encedo sea el bayesiano. En e ec o así es. En la g á ica de la igu a 8.4 se e cla amen e que el ecomendado K-Vecinos es á siemp e po debajo. Se des aca la di e encia en e la dis ancia inicial en e las líneas y la dis ancia inal. Es a dis ancia se a educiendo a consecuencia de la mé ica p ecision, pues descendía muy ápidamen e, y como ya sabemos -sco e se calcula con una ó mula que u iliza las mé icas p ecision y ecall. 8.5. Conclusiones de la e aluación El en enamien o aplicado a ambos ecomendado es ha sido de u ilidad p incipalmen e a la ho a de es udia el compo amien o de los di e en es pa- áme os de ecomendación con un subconjun o de los mejo es p oblemas de la lis a de ecomendación que los ecomendado es p oponen. De es a compa- ación se pueden obse a po lo gene al mejo es esul ados en las di e en es mé icas po pa e del ecomendado bayesiano. Es cu ioso el caso de la p ecisión donde el compo amien o que iene el ecomendado bayesiano se asemeja a una unción exponencial dec ecien e de la o ma (x) = ax,(0 <a<1), así como el ecomendado K-Vecinos 8.5. Conclusiones de la e aluación 67 0 0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.16 1 2 3 4 5 6 7 8 9 10 F-Sco e Can idad de p oblemas ecomendados Bayesiano K-Vecinos Figu a 8.4: G á ica de compa ación de -sco e a una unción lineal dec ecien e con poca caída, de la o ma (x) = b− mx, pe mi iendo en algunos casos supe a el esul ado de la p ecisión del bayesiano. Se puede en ende que el compo amien o del ecomendado bayesiano haya dado mejo es esul ados de ecomendación, ya que el concep o del eo- ema de bayes aplicado en ecomendaciones esul a más p eciso ya que busca calcula la p obabilidad de que un usua io pueda esol e un p oblema. Po o o lado, el ecomendado po K-Vecinos no ha conside ado de alles que pod ían e ina in o mación como son los casos en los que un usua io ha in en ado esol e un p oblema pe o no ha enido éxi o. El hecho de que el ecomendado bayesiano haya esul ado ic o ioso en es as mé icas, no desca a idea de que sus ecomendaciones engan que se siemp e las más pe sonalizadas pa a un usua io, ya que una ecomendación pe sonalizada no siemp e iene po qué se la opción más ácil pa a es e. Po o o lado, ambién cabe con as a el iempo de ecomendación gene- ado po cada SR. Como se ha comen ado en los co espondien es capí ulos, aunque pa a ambos ecomendado es el iempo de ecomendación po usua io es bas an e bajo, se ap ecia que K-Vecinos es á mejo op imizado y su cos e algo í mico es meno . Es a di e encia es ambién in e esan e de esal a ya que puede me ece la pena empeo a la calidad de ecomendación un poco a cos a de mejo a la elocidad y e iciencia de es a, sob e odo si se es án calculando muchas ecomendaciones a la ez. Capí ulo 9 Implemen ación como se icio ex e no Resumen: Es e capí ulo engloba la a qui ec u a e ingenie ía de im- plemen ación de los dos ecomendado es ealizados, pa a pode se im- plemen ados como se icio ex e no, siguiendo los p incipios de adap- abilidad y po abilidad. La es uc u a in e na de cada ecomendado se expone en los capí ulos e e en es a cada uno de ellos. 9.1. API de comunicación Pa a lle a a cabo un uncionamien o comple o del ecomendado , es necesa io implemen a los algo i mos sob e un diseño e icaz que pe mi a una e oalimen ación, y que a la ez sea capaz de da se icio múl iple a quien le solici e ecomendaciones. Pa a ello se ha implemen ado una a qui ec u a adecuada que soluciona de mane a e icaz es os p oblemas: se ha di idido en es pa es es a a qui- ec u a que sepa an de mane a lógica las di e en es uncionalidades que el ecomendado debe pode ealiza . Los ecomendado es ealizados has a aho a han abajado en un en o no de p uebas local. Pa a hace los o almen e uncionales en casos de usos eales, son necesa ias nue as es uc u as que pe mi an al ecomendado pone al día la in o mación de es e, sob e el juez en línea al que es á dando se icio. También son necesa ias es as nue as es uc u as pa a ene una ía sob e la que el juez en línea pueda hace pe iciones al ecomendado , y ob ene los da os que sean necesa ios y ú iles. En los ecomendado es debe inclui se un nue o módulo lógico pa a que se enca gue de esol e es os p oblemas. Es e nue o bloque lógico debe un- ciona como una API de comunicación en e el ecomendado y el juez en 69 70 Capí ulo 9. Implemen ación como se icio ex e no Ins ancia una clase ecomendado pa a ecomenda Es uc u a in e na del ecomendado (Ejemplo con K-Vecinos ecomende ) se ido de pe iciones Llama a... Recomendado K ecinos + Ma izDa os:NumpyMa ix + conexionDB:JuezDB + g ado:in + use IDowne :in + use PosOwne :in + Recomendado K ecinos(db:JuezDB) + ecomenda (use IDowne ,g adoSimili ud):Dic iona y - co elacion(use ): double - calcula TamP oblemasUse (posUse ): in - il a NMasSimila es(can idad):Ma ix - busca P oblemasComunes(use ):Lis - amP oblemasComunes(use ):in - busca P oblemasUse 2MinusOwne (use ):Lis JuezDB +Ma izDa os:NumpyMa ix -Lis aUsua ios:Lis -Lis aP oblemas:Lis -Las Submi ion:in ... -gua da Ma izEnLocal() -ca ga Ma izDesdeLocal() +ob ene Ma iz():NumpyMa ix +ob ene PosUse (idUse ):in +ac ualiza En egas(nue asEn egas,ul imaEn ega) ... Clien ePe iciones +conexionDB:JuezDB + Clien ePe iciones(db) +Ac ualiza Ul imosEn ios() +ob ene 20en egas(posicion):Json h p_se e +conexionDB:JuezDB +h p_se e (db) myHandle ... + do_GET() Ins ancia con concu encia una clase manejado Figu a 9.1: Diag ama de clases ex endido pa a el ecomendado K-Vecinos. línea. Cada uno de los ecomendado es se ha p og amado con di e en es ecno- logías. Las pa es p opias de cada uno de ellos se explican con mayo de alle en los capí ulos 6 y 7 espec i amen e. Aquí se a a a a la lógica elacionada con la API común a ambos eco- mendado es que ep esen a un ni el supe io en las capas de la a qui ec u a de es a, ya que es a lógica ins ancia á obje os de ecomendación, pa a hace uso de la ecomendación y la ac ualización de la BD. La lógica elacionada con la API, es deci , la pa e que ges iona la comu- nicación con el juez en línea, se encuen a o almen e sepa ada de la lógica del ecomendado . Es e iche o con iene es clases: dos que uncionan como se ido h p y manejado de pe iciones, y una que unciona como clien e que hace pe iciones HTTP al juez en línea sob e el que ope a. De mane a de allada se obse a cómo unciona y se elaciona es e se icio ex e no, aplicado al caso del ecomendado K-Vecinos y el juez en línea ¡Acep a el e o!, como la igu a 9.2 indica. Median e es e mecanismo, es á comple amen e sepa ado el ecomendado del juez en línea pe mi iendo su po abilidad. Haciendo lige as modi icaciones en el conjun o de la API y es a es uc u a 9.1. API de comunicación 71 Escucha nue os en íos Pla a o ma de Juez en línea Base de da os Solici ud / Ac ualización de da os Api de ecomendado Se ido de pe iciones h p Clien e de escucha Juez en linea Ke nel del ecomendado Ges ion de BBDD del ecomendado En ía nue a in o mación indicando que se ac ualice Le pasa la ma iz de da os al ecomendado Ins ancia al ecomendado y lo ejecu a Realiza pe iciones Comunicacion en e pla a o ma/ ecomendado Pa e in e na del ecomendado Recomendado comple o / Se icio ex e no Responde las pe iciones Figu a 9.2: Funcionamien o del ecomendado K-Vecinos con API implemen- ada pa a su uso como se icio ex e no. supe io , se pueden adap a o os ecomendado es a la API, o aplica a ios ecomendado es sob e una misma API y es uc u a supe io . De es a mane a se puede consegui que el juez en línea pida al se icio de ecomendación que ecomendado u iliza , o sea la p opia es uc u a su- pe io se á la que decida qué ecomendado se debe u iliza pa a un usua io conc e o, en unción de los esul ados ob enidos pa a el mismo. La igu a 9.1 mues a el diag ama de clases de lo que nos in e esa en cuan o a la API del ecomendado . En es e se iene un ejemplo aplicado pa a el ecomendado K-Vecinos. Las clases in e nas de es e ecomendado en conc e o, no an a se anali- zadas en las siguien es subsecciones ya que son p opias de es e y no comunes de ambos ecomendado es. Se ha decidido mos a el diag ama de clases ex endido de la API con es e ejemplo, ya que se ha log ado implemen a y p oba con co ec o un- cionamien o es e módulo del que es amos hablando, con es e ecomendado mencionado en el capí ulo an e io . De odas o mas, hay que deja cla o que la API se comunica de mane a simila con ambos ecomendado es, es deci , siemp e a a ene que ins ancia una clase ecomendado , como se e á en las siguien es secciones del capí ulo, 78 Capí ulo 10. Conclusiones y abajo u u o ecomendado K-Vecinos, que in en a busca usua ios simila es al que se es á ecomendado y ija se qué o os p oblemas han seguido haciendo, pa a así selecciona los pa a el usua io a ecomenda . Es a o ma de ecomendación, es más pe sonalizada, aunque sus esul ados no son an buenos como el bayesiano pa a la e aluación que se ha aplicado, pe o in en a selecciona esa pe sonalización que el bayesiano no iene en cuen a, pe mi iendo se un ecomendado in e esan e como p opues a de implemen ación en un juez en línea. Po o o lado, el abajo en un p incipio se plan eó como algo que aba ca- ba más de alles que no se han podido llega a ealiza , po lo que en adelan e, se comen a el abajo u u o y las líneas que puede segui es e p oyec o que se ha lle ado a cabo. Las siguien es secciones, in oducen di e en es líneas a segui de ca a al u u o pa a cua o aspec os undamen ales que iene es e p oyec o. 10.1. Recomendado Bayesiano La implemen ación del ecomendado bayesiano con ada en el capí ulo 6 ha sido op imizada pa a educi el iempo de cálculo. Aún así, si se u ie a que ecalcula odo cada ez que se hace un nue o en ío, pod ía ocu i que en un co o espacio de iempo se ealiza an a ios en íos y en e medias de cada uno aún no haya inalizado el ecálculo an e io . Po es e mo i o se es udia ía a ondo en qué modo a ec a un nue o en ío, con el in de ealiza el meno núme o de cálculos posibles omando como base los esul ados del cálculo an e io . Además se plan ea la posibilidad de acumula los nue os en íos que se p oduzcan y ealiza el ecálculo en de e minados momen os del día. Es o p o oca ía que las ecomendaciones no es u ie an 100 % ac ualizadas, po lo que, habiendo es udiado el e ec o de un nue o en ío, hab ía que analiza si compensa. Eso sí, eniendo cuidado siemp e de no ecomenda a un usua io un p oblema que ya haya esuel o, incluso en el iempo que los cálculos no es én ac ualizados. O a p opues a a ealiza es calcula el po cen aje exac o de p obabili- dad ya que la e sión implemen ada se aho a calcula el denominado pues o que solo in e esaba el o den de p obabilidad en un p incipio. La p obabili- dad básica nos dice que la suma de la p obabilidad de odos los posibles sucesos iene que se 1. Po an o, podemos ap o echa los cálculos ealiza- dos (P(A|B)yP(¬A|B)) a los que les al a el denominado y despeja la siguien e ó mula pa a ob ene lo (de la que esul a que el denominado es an solo suma ambos alo es): P(A|B) denominado +P(¬A|B) denominado = 1 10.2. Recomendado de pesos po los K-Vecinos más simila es 79 10.2. Recomendado de pesos po los K-Vecinos más simila es El ecomendado de pesos po los K-Vecinos más simila es ha sido imple- men ado al como se explica en el capí ulo 7. Cabe la posibilidad de modi ica el algo i mo con la idea de mejo a y puli aspec os de es e, an o a ni el de op imización, como en su uncionamien o in e no. De es e segundo caso (la mejo a de los esul ados de las mé icas), no se puede sabe a ciencia cie a si mejo a ía el algo i mo sin su e aluación pos e io pa a con as a esul ados. Una de las modi icaciones del algo i mo p opues as en cuan o a mane as de ecomenda , es la idea de conside a un nue o caso en los en íos, que ac ualmen e el algo i mo conside a como no ealizado. Es e caso nue o se añade haciendo que el ecomendado ambién enga en cuen a los en íos sin éxi o de los usua ios. Es a modi icación se ía equi alen e a la e sión RIN del ecomendado bayesiano. De es a o ma, a la ho a de calcula la co elación de un usua io con o os, se pod ía ambién añadi a la ó mula los in en os sin éxi o que es e ha enido, pa a ija se en esas simili udes espec o a o os usua ios, jun o con los p oblemas que han log ado esol e en común. G acias a es a nue a mane a de calcula la co elación, se pod ían encon- a nue as simili udes o ace ca ecinos que de la mane a ac ual los man iene más alejados, y de es a o ma, cambia ía en cie o modo su ecomendación. O o momen o donde pode conside a es e nue o es ado en el que se ija ía el ecomendado , se ía a la ho a de calcula los pesos po p oblema. Así, si uno de los ecinos iene un p oblema “in en ado y no esuel o” que el usua io a ecomenda no haya ni in en ado, se le puede baja el peso de ecomendación a ese p oblema en conc e o pa a di icul a que es e escale en el anking de ecomendación. El ac o de in en ado y no esuel o que se puede añadi a conside a en el algo i mo de ecomendación, es un da o más que en iquece la in o mación con la que es e ecomendado puede abaja y gene a la cu iosidad de e si la ecomendación esul an e de es e algo i mo mejo a ía no ablemen e, o incluso si pudiese empeo a . Po o o lado, en el aspec o de la op imización, el ecomendado aún puede se mejo ado encon ando nue os cuellos de bo ella, ya que el pun o de op imización se dejó de abaja en cuan o los iempos de ecomendación se eduje on conside ablemen e. Se pod ía ambién maneja un dicciona io al pa sea el ID de usua io po su posición en la ma iz, en luga de usa un a ay cuya posición ep esen e la posición de la ma iz y su alo el ID, ya que Py hon maneja de mane a óp ima es e ipo de es uc u as y acili a ía la búsqueda de una posición en la ma iz en base a su ID de usua io. Ac ualmen e esa búsqueda aplica bús- 80 Capí ulo 10. Conclusiones y abajo u u o queda bina ia ya que el a ay es á o denado po ID de meno a mayo . Es o ambién acili a ía las inse ciones a la ho a de ac ualiza el ecomendado , cada ez que exis en nue os usua ios, ya que ac ualmen e se debe desplaza el a ay pa a inse a en una posición conc e a y man ene el o den po ID. De odas o mas es e desplazamien o se ealiza median e los mé odos que o ece Numpy, así que su o den de complejidad es á bas an e op imizado. En cuan o a o as o mas de op imización que no implicasen busca cue- llos de bo ella, se ha plan eado la idea de mejo a los esul ados de ecomen- dación p e-cacheando la in o mación pa a ene la disponible en el momen o de la consul a de ecomendación, aunque el p e-cacheado gene a ía la nece- sidad de nue as clases que ges ionen odo es e ema, ya que las consul as de ecomendación ob end ían di ec amen e un esul ado p ecalculado pa a ene lo más accesible y sin necesidad de espe a. Es a idea se desca ó g acias a que mejo a on signi ica i amen e los iempos de cálculo po ecomendación aplicando el mayo pa alelismo posible. 10.3. API de comunicación La API de comunicación que se ha ealizado, no maneja concu encia en e el se ido de ecomendación y las consul as que se hacen a ¡Acep a el e o! pa a ac ualiza la BD del ecomendado . Ac ualmen e su compo amien o es: al ejecu a el se icio de ecomen- dación, la API ac ualiza la BD del ecomendado con los úl imos en íos de ¡Acep a el e o! y pos e io men e lanza el se ido . Una ez se lanza el se ido el ecomendado no man iene una ac ualización pe iódica. La idea en es e pun o de la API es pode añadi concu encia en e el se ido de ecomendaciones y el clien e que hace las ac ualizaciones, pa a pode man ene esa ac ualización de la BD del ecomendado sin ene que einicia el se icio. O a in ención o iginal e a la de llega a consegui una API que se co- nec ase a un se icio que o eciese ¡Acep a el e o! pa a los ecomendado es, de al mane a que no ac uase de “espía” como hace ac ualmen e, si no que ¡Acep a el e o! u iese una pa e que le acili ase es a in o mación de ac ua- lización ya il ada, y con la que se comunicase de una mane a más cómoda. 10.4. Implemen ación en ¡Acep a el e o! La idea de pode implemen a los ecomendado es en ¡Acep a el e o! e a sob e odo pa a pode hace una e aluación de ambos ecomendado es en un en o no de ejecución eal, pe mi iendo analiza con mayo p ecisión los esul ados de ecomendación, ya que bajo un en o no de implemen ación eal, el usua io puede e la ecomendación y decidi si hace el p oblema 10.4. Implemen ación en ¡Acep a el e o! 81 ecomendado o no, y en caso de in en a lo, e si ha enido éxi o o ha aca- sado. Es a implemen ación hab ía sido un g an juego en la e aluación de esul- ados de los ecomendado es, debido a su idelidad con un caso de uso eal, ya que se pod ía en ende mejo si de lo que se ecomienda a un usua io, es igno ado o in en ado, y en es e úl imo caso, si ha habido éxi o o acaso en la esolución del eje cicio. Capí ulo 11 Conclusions and u u e wo k This wo k has been ocused on applying se e al in e es ing ecommen- da ion sys ems in he ield o online judge pla o ms. So, i has been possible o make a de ailed in es iga ion o impo an s ecommenda ions models and wo o hem ha e been selec ed o ca y ou an implemen a ion oge he wi h i s e alua ion o esul s, in a popula online judge pla o m. These wo ecommende s ha e been he Bayesian ecommende and he ecommende o weigh s o he nea es K-Neighbo s ha , hanks o an anonymous da abase o he pla o m ¡Acep a el e o! i has been possible o make a s udy abou he e ec i eness o hese ecommenda ion sys ems o his adap a ion o online judges. In addi ion, a communica ion p oposal ( he API) has been de eloped o hese ecommende s, which would allow hem o be used by an online judge as an ex e nal se ice and i has been possible o p o e o he case o K-Neighbo s in he pla o m acep a el e o! wi hou being implemen ed di ec ly on i . Thanks o his and as i has been obse ed a he end o chap e 8, has come o he conclusion ha he Bayesian ecommende wo ks be e o hese pla o ms ha a e online judges, since hei esul s shown du ing he analysis o he chap e men ioned, ha e p o ed ha a Bayesian ecommen- da ion model is mo e accu a e in he selec ion o he p oblems ha a use would y o pe o m. Howe e , i also emains as ano he idea o he conclusions, ha he Bayesian ecommenda ion s yle is good o selec ing a lis o p oblems ha a use would be mo e likely o sol e, by he own concep o he bayes heo em, bu can no always be conside ed ha is he bes ecommenda ion since he in e es o a use is no limi ed o sol e he p oblem ha is mos likely o be esol ed, bu a he many imes he use s o hese pla o ms look o challenges and he need o some hing mo e di icul and new o hem. He e comes in o play he ecommenda ion s yle o he o he ecommen- 83 84 Capí ulo 11. Conclusions and u u e wo k de , he K-Neighbo s ecommende , who ies o ind use s simila o he one who is being ecommended and no e wha o he p oblems ha e been choosen o be selec ed hem o he use o ecommend. This o m o ecommenda- ion, is mo e pe sonalized, al hough i s esul s a e no as good as Bayesian o he e alua ion ha has been applied, bu y o selec ha cus omiza ion ha he Bayesian does no ake in o accoun , allowing o be a in e es ing ecommenda ion as a p oposal o implemen a ion in a judge in line. On he o he hand, he wo k a i s was p oposed as some hing ha encompassed mo e de ails ha could no be made, so on, he u u e wo k is discussed and he lines ha can be ollowed in o de o con inue his p ojec ha has been ca ied ou . The ollowing sec ions, in oduce di e en lines o ollow in he u u e o ou undamen al aspec s ha his p ojec has. 11.1. Bayesian Recommende The implemen a ion o he Bayesian ecommende , old in chap e 6, has been op imized o educe calcula ion ime. S ill, i you had o ecalcula e e e y hing e e y ime a new shipmen is made, i could happen ha In a sho space o ime se e al shipmen s will be made and in be ween each one has no inished he ecalcula ion ye . Fo his eason we will s udy in dep h how a new shipmen a ec s, in o de o pe o m he leas numbe o possible calcula ions aking as base he esul s o he p e ious calcula ion. I also aises he possibili y o accumula ing new shipmen s ha a e p oduce and pe o m he ecalcula ion a ce ain imes o he day. This would cause he ecommenda ions no o be 100 % up- o-da e, so ha , ha ing s udied he e ec o a new shipmen , i would be necessa y o analyze whe he compensa es o no . O cou se, always aking ca e no o ecommend an use a p oblem ha has al eady been sol ed, e en in he ime ha he calcula ions do no a e upda ed. Ano he p oposal o make is o calcula e he pe cen age o he p obabili y and he e sion implemen ed. The basic p obabili y ells us ha he sum o he p obabili y o all possible e en s mus be 1. The e o e, we can ake ad an age o he calcula ions made (P(A|B)and P(¬A|B)) a The ollowing o mula o ob ain i is he ollowing: P(A|B) denomina o +P(¬A|B) denomina o = 1 11.2. Weigh ecommenda ion by mos Simila K-Neighbo s 85 11.2. Weigh ecommenda ion by mos Simila K- Neighbo s The ecommende o weigh s o he mos simila K-Neighbo s has been implemen ed as explained in chap e 7. I is possible o modi y he algo- i hm wi h he idea o imp o ing and polishing aspec s o his, bo h a he op imiza ion, as in i s in e nal unc ioning. In his second case ( he imp o emen o he esul s o he me ics), we can’ know o su e i i would imp o e he algo i hm wi hou i s subsequen e alua ion o compa e esul s. One o he algo i hm modi ica ions p oposed in e ms o ways o ecom- mend, is he idea o conside ing a new case in he shipmen s, which cu en ly he algo i hm conside s as no pe o med. This new case is adds by ha ing he ecommende also conside shipmen s wi hou success o he use s. This modi ica ion would be equi alen o he RIN e sion o he Bayesian ecom- mende . In his way, when calcula ing he co ela ion o a use wi h o he s, you could also add o he o mula unsuccess ul a emp s ha his has had, o look a hose simila i ies wi h o he use s, oge he wi h he common p oblems hey ha e managed o sol e. Thanks o his new way o calcula ing he co ela ion, you could ind new simila i ies o b ing neighbo s ha in he cu en way keeps hem u he away, and in his way, i would change i s ecommenda ion somewha . Ano he momen whe e we can conside his new s a e in which would ix he ecommende , i would be a he momen o calcula ing he weigh s pe p oblem. So, i one o he neighbo s has a p oblem " ied and no esol- ed" ha he use o ecommend has no ied, you can lowe he weigh o ecommenda ion o ha p oblem in pa icula o make i di icul o i o ise in he ecommenda ion aking. The ac o o a emp ed and un esol ed ha can be added o conside in he ecommenda ion algo i hm, is a da a ha en iches he in o ma ion wi h which his ecommende can wo k and gene a es he cu iosi y o see i he ecommenda ion esul ing om his algo i hm would imp o e signi ican ly o , e en, i i could ge wo se. On he o he hand, in he aspec o op imiza ion, he ecommende s ill can be imp o ed by inding new bo lenecks, since he poin o op imiza- ion was s opped wo king as soon as he ecommenda ion imes hey we e conside ably educed. A dic iona y could also be handle when pa sing he use ID by i s posi ion in he ma ix, ins ead o using an a ay whose posi ion ep esen s he posi ion o he ma ix and i s alue he ID, since py hon handles in a op imal his ype o s uc u es and would acili a e he sea ch o a posi ion in he ma ix based on you use ID. Cu en ly ha sea ch applies sea ch bina y since he 86 Capí ulo 11. Conclusions and u u e wo k a ay is so ed by ID om leas o g ea es . This i would also acili a e he inse ions when upda ing he ecommende , e e y ime he e a e new use s, since cu en ly i is necessa y o mo e he a ay o inse in a speci ic posi ion and main ain he o de by ID. In any case, his displacemen is ca ied ou h ough he me hods ha Numpy o e s, so i s o de o complexi y is qui e op imized. As o he o he o ms o op imiza ion ha did no in ol e looking o co- lla s bo leneck, he idea o imp o ing he ecommenda ion esul s has been p e-caching he in o ma ion o ha e i a ailable a he ime o he ecom- menda ion consul a ion, al hough p e-caching would gene a e he need o new classes ha manage his whole opic, since he que ies o ecommenda- ion would di ec ly ob ain a p ecalcula ed esul o ha e i mo e accessible and wi hou wai ing. This idea was uled ou hanks which signi ican ly im- p o ed calcula ion imes by ecommenda ion applying he g ea es possible pa allelism. 11.3. Communica ion API The communica ion API ha has been made, does no handle concu- ency be ween he ecommenda ion se e and he que ies ha a e made o ¡Acep a el e o! o upda e he ecommende ’s BD. Cu en ly his beha io is: when execu ing he ecommenda ion se ice, he API upda es he ecommende ’s BD wi h he la es shipmen s o Accep he challenge! and hen launch he se e . Once he se e he ecommende does no main ain a pe iodic upda e. The idea a his poin o he API is o be able o add concu ency be ween he se e o ecommenda ions and he clien ha makes he upda es, o able o main ain ha upda e o he ecommende ’s BD wi hou ha ing o es a he se ice. Ano he o iginal in en ion was o ge an API ha connec s o a se ice ha o e s ¡Acep a el e o! o he ecommende s, in such a way ha he did no ac as a “spy” as he does now, bu ha ¡Acep a el e o! had a pa ha would p o ide his upda e in o ma ion al eady il e ed, and wi h which i communica ed in a mo e com o able way. 11.4. Implemen a ion in ¡Acep a el e o! The idea o being able o implemen he ecommende s in ¡Acep a el e o! i was mos ly o be able o make an e alua ion o bo h ecommende s in a eal execu ion en i onmen , allowing o analyze wi h g ea e p ecision he ecommenda ion esul s, since unde an implemen a ion en i onmen eal, he use can see he ecommenda ion and decide whe he o do he p oblem 11.4. Implemen a ion in ¡Acep a el e o! 87 ecommended o no , and i you y, see i i has been success ul o has ailed. This implemen a ion would ha e been a g ea game in he e alua ion o esul s o he ecommende s, due o hei ideli y wi h a case o eal use, since i could be be e unde s ood i wha is ecommended o a use , is igno ed o ied, and in his las case, i he e has been success o ailu e in he esolu ion o he exe cise. 94 Bibliog a ía Re illa, M. A.,Manzoo , S. yLiu, R. Compe i i e lea ning in in o - ma ics: The u a online judge expe ience. Olympiads in In o ma ics, ol. 2(10), páginas 131–148, 2008. Sanz Molina, A. yMa in del B io, B. Redes Neu onales y Sis emas Bo osos.. Ra-Ma edi o ial, 2006. Disponible en h p://www. a-ma. es/lib os/REDES-NEURONALES-Y-SISTEMAS-BORROSOS-3-EDICION/241/ 978-84-7897-743-7. Sánchez-Ruiz, A.,Jimenez-Diaz, G.,Gómez-Ma ín, P. yGómez- Ma ín, M. Case-based ecommenda ion o online judges using lea ning i ine a ies. páginas 315–329. 2017. ISBN 978-3-319-61029-0. Wikipedia (Deep lea ning). Disponible en h ps://es.wikipedia.o g/ wiki/Ap endizaje_p o undo. Wikipedia (Elo a ing sys em). En ada: “Elo a ing sys em”. Disponible en h ps://en.wikipedia.o g/wiki/Elo_ a ing_sys em (úl imo acce- so, Ma zo, 2019). Wikipedia (k-nea es neighbo s). Disponible en h ps://en.wikipedia. o g/wiki/K-nea es _neighbo s_algo i hm. Zheng, Y.,Mobashe , B. yBu ke, R. Con ex ecommenda ion using mul i-label classi ica ion. 2014. Lis a de ac ónimos AC ............ Accep ed API ........... Applica ion P og amming In e ace BD............ Base de da os FN ............ False Nega i e FP ............ False Posi i e RRNN ........ Redes neu onales SR ............ Sis ema de Recomendación TN............ T ue Nega i e TP ............ T ue Posi i e 95