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