Anonimización de Bases de Da os Médicas
Shahad Naji Ja a y Bea iz Manjón Co ales
GRADO EN INGENIERÍA INFORMÁTICA
FACULTAD DE INFORMÁTICA
UNIVERSIDAD COMPLUTENSE DE MADRID
TRABAJO FIN DE GRADO EN INGENIERÍA INFORMÁTICA
Mad id, 6 de junio del 2016
Di ec o : Ra ael Caballe o Roldán
2
AUTORIZACIÓN PARA LA DIFUSIÓN DEL TRABAJO FIN DE GRADO Y SU DEPÓSITO EN
EL REPOSITORIO INSTITUCIONAL E-PRINTS COMPLUTENSE
Los abajo i man es, alumno/s y u o /es del T abajo Fin de G ado (TFG) en el G ado
en INGENIERÍA INFORMÁTICA de la Facul ad de INFORMÁTICA, au o izan a la Uni e sidad
Complu ense de Mad id (UCM) a di undi y u iliza con ines académicos, no come ciales y
mencionando exp esamen e a su au o el T abajo Fin de G ado (TF) cuyos da os se de allan a
con inuación. Así mismo au o izan a la Uni e sidad Complu ense de Mad id a que sea
deposi ado en acceso abie o en el eposi o io ins i ucional con el obje o de inc emen a la
di usión, uso e impac o del TFG en In e ne y ga an iza su p ese ación y acceso a la go plazo.
Pe iodo de emba go (opcional):
 6 meses
 12meses
TÍTULO del TFG: ANONIMIZACIÓN DE BASES DE DATOS MÉDICAS
Cu so académico: 2015 / 2016
Nomb e del Alumno/s:
SHAHAD NAJI JAFFAR
BEATRIZ MANJÓN CORRALES
Tu o /es del TFG y depa amen o al que pe enece:
RAFAEL CABALLERO ROLDÁN
Depa amen o: SISTEMAS INFORMÁTICOS Y COMPUTACIÓN
Fi ma del alumno/s Fi ma del u o /es
3
Índice
Índice de igu as ............................................................................................................................ IV
Índice de ablas .............................................................................................................................. V
Resumen ...................................................................................................................................... VI
Abs ac ..................................................................................................................................... VII
Con ibuciones de Shahad Naji Ja a ......................................................................................... VIII
Con ibuciones de Bea iz Manjón Co ales ................................................................................... X
1 | In oducción ................................................................................................................. 12
1.1 An eceden es 12
1.2 Nociones de anonima o 12
1.3 Nues o Obje i o 13
2 | Simulación de Da os ...................................................................................................... 15
2.1 Población y ecu sos 16
2.2 Gene ación alea o ia de ci as 18
3 | Vec o es de Anonima o ................................................................................................. 19
3.1 Insu iciencia del k-anonima o 19
3.2 De inición de ec o de anonima o 21
4 | Anonima o como P oblema de op imización en P og amación con Res icciones .......... 23
4.1 P og amación con Res icciones 23
4.2 El modelo 25
4.3 Posibles mejo as 29
5 | Expe imen os ................................................................................................................ 30
5.1 Mejo a de anonima o 30
5.2 Desc ipción de los expe imen os 31
6 | Implemen ación ............................................................................................................ 36
7 | Conclusiones y abajo u u o ....................................................................................... 40
8 | Conclusions and u u e wo k ........................................................................................ 42
9 | Bibliog a ía ................................................................................................................... 44
4
Índice de igu as
Imagen 1: Ejemplo de con enido del iche o .dzn 25
Imagen 2: P ime le el 27
Imagen 3: Segundo le el 27
Imagen 4: Te ce le el 27
Imagen 5: Cua o le el 28
Imagen 6: Resul ado inal del p og ama 38
5
Índice de ablas
Tabla 1: Tabla de población 15
Tabla 2: Tabla de ecu sos 15
Tabla 3: Tabla de población con asignación de ecu sos alea o ios 16
Tabla 4: Tabla de población sin asignación de ci as alea o ias y mejo adas 17
Tabla 5: Tabla de población con asignación de ci as alea o ias 18
Tabla 6: P ime ejemplo de abla de población con asignación de ecu sos alea o ios 19
Tabla 7: Segundo ejemplo de abla de población con asignación de ecu sos alea o io 20
Tabla 8: Te ce ejemplo de abla de población con asignación de ecu sos alea o ios 20
Tabla 9: Tabla de cuasi-iden i icado es de los es ejemplos 21
Tabla 10: Tabla de ec o es de anonima o 21
Tabla 11: P ime expe imen o con población amaño 10 32
Tabla 12: Segundo expe imen o con población amaño 20 33
Tabla 13: Te ce expe imen o con población amaño 30 34

6
Resumen
La publicación de los esul ados de p og amas de sc eening (exámenes médicos o ien ados a un
g upo gené ico de la población) es de sumo in e és pa a la comunidad cien í ica. A pesa de
elimina da os pe sonales como DNI, nomb e, e c. el es o de la in o mación, los llamados cuasi-
iden i icado es (código pos al, géne o, edad, p o esión, o in o mación de la ci a médica
incluyendo el cen o y la ho a) pueden se u ilizados pa a des ela la iden idad de los pa icipan es
en el p og ama. En pa icula , la in o mación de la ci a médica puede esul a comp ome edo a
si, ya sea in encionadamen e o po casualidad, se descub e que una pe sona de e minada ha
acudido a un de e minado cen o en una echa conc e a. Bas a ía en onces con consul a los
esul ados del es pa a sabe si el indi iduo cuyos cuasi-iden i icado es conocemos padece la
en e medad. El obje i o de es e abajo es p og ama la asignación de ci as, de mane a que se
aumen e el ni el de anonima o de las bases de da os inales. Pa a ello, se p e ende que pe sonas
con ca ac e ís icas comunes (edad, e c.) acudan a la misma ci a (ho a y cen o), di icul ando la
iden i icación de los esul ados médicos de un indi iduo aunque se conozcan sus da os pe sonales,
ya que se encon a án con a ias pe sonas con los que compa e los mismos cuasi-iden i icado es.
Palab as Cla e: Bases de da os, Cuasi-iden i icado es, Da os pe sonales, Gene ación de
ci as, Ni el de anonima o, Sc eening
7
Abs ac
The publica ion o sc eening p og ammes’ esul s (examina ion o es ing o a g oup o
indi iduals o sepa a e hose who a e well om hose who ha e an undiagnosed disease o de ec
o who a e a high isk [11]) is an impo an ac o o he scien i ic communi y. In spi e o dele ing
pe sonal da a such as ID, name, e c. he es o he in o ma ion, which is called quasi-iden i ie s
(P.O. Box, gende , age, p o ession o he in o ma ion o he appoin men including he medical
cen e and he ime) could be used o e eal he iden i y o he pa icipan s o he sc eening
p og amme. Pa icula ly, he in o ma ion o he medical appoin men may be inc imina ing, ei he
in en ionally o by acciden , ha disclose a speci ic pe son a ends a pa icula cen e a a known
da e. Then, i will be enough wi h consul ing he es s esul s o know i he indi idual wi h he
quasi-iden i ie s, which we know, su e s om illness. The objec i e o his p ojec is o
p og amme he assignmen o he appoin men s, in o de o inc ease he anonymi y le el o he
inal da abase. Then, he plan is ha people wi h he same cha ac e is ics (age, e c) a end he
same appoin men ( ime and cen e), hinde he iden i ica ion o he medical esul s o a speci ic
indi idual e en i his o he pe sonal da a a e known, because, he in o ma ion o he same quasi-
iden i ie s o mo e han one pe son will be ound.
Keywo ds: Anonymi y le el, Assignmen o he appoin men s, Da abase, Pe sonal da a,
Quasi-iden i ie , Sc eening
8
Con ibuciones de Shahad Naji Ja a
Como Bea iz y yo no solamen e somos compañe as que se eunie on pa a lle a a cabo el abajo
in de g ado, sino ambién amigas, ambas nos coo dinamos de al mane a que podemos deci que
el abajo ue ealizado o almen e en conjun o median e la compa ición, el usionamien o de
nues as ideas y es ue zo.
Después de cada eunión con el u o del p oyec o cada una p epa aba un posible a ance sob e lo
discu ido en dicha eunión, pa a pos e io men e escoge la mejo idea, o elegi la mejo pa e de
la misma, e ec uando un usionamien o de ideas, po lo que se log aba una mejo con la ayuda
de nues o u o .
En un p ime momen o, ambas leímos a ios a ículos sob e cómo mejo a el anonima o de una
abla, haciendo un g an hincapié sob e el k-anonima o.
La implemen ación de es e p oyec o se ha di idido en e cinco p og amas, cuyo lenguaje de
p og amación es Ja a, que son in ocados median e un p og ama en Bash.
Pa a la ins alación de la base de da os elacional que con iene los da os de pe sonas y ecu sos.
En pa icula hemos elegido Pos g eSQL en su e sión 1.22.0 Be a 1.
En el p ime p og ama mi labo des aca en la c eación de una unción esc i a Pos g eSQL que
asegu a que los ecu sos pueden a ende a oda la población po lo que se aumen a la capacidad
de cada ecu so has a la máxima capacidad es ablecida po el usua io inal. Si no se consigue que
los ecu sos cub an a oda la población, el p og ama se de end á in ocando a una excepción.
Pa a asigna las ci as a la población an o mi compañe a Bea iz como yo nos eunimos pa a
p og ama el segundo p og ama, usando la unción Random del paque e ja a.u il.Random.
Du an e el desa ollo del p oyec o se ha que ido sabe cuál es el alo del k-anonima o de las
ablas eligiendo cie os a ibu os que ep esen an a los cuasi-iden i icado es. Pa a ello, Bea iz y
yo; y bajo la supe isión de nues o u o c eamos el e ce p og ama.
Cabe des aca que es e e ce p og ama nos apo ó an o a mi compañe a como a mí un mejo
en endimien o de es e T abajo Fin de G ado e inando los concep os.
Ambas implemen amos unciones necesa ias del cua o p og ama pa a calcula : Q, , R y c.
Pa a ob ene los alo es de los da os an e io es, c eamos a ias unciones que acceden a las ablas
de la base de da os Pos g eSQL as comp oba la exis encia de las mismas.
En es e p og ama, des aca la labo de mi compañe a Bea iz po la co ec a colocación de los
pa áme os Q, , R y c; y sus espec i os alo es en el iche o con ex ensión .dzn pa a que es os
sean co ec amen e leídos po el p og ama de MiniZinc, de aquí en adelan e appoin men .mzn.
Pa a la ob ención del ec o anonima o, es deci pa a consegui una mejo a de anonima o se ha
p ocedido a p og ama el quin o p og ama.
9
Debemos des aca la labo de nues o u o con espec o a la implemen ación de appoin men .mzn
y además del cálculo de dis ancia en e los dis in os ec o es gene ados, es deci , la medida de
mejo a de anonima o ob enida.
An es de p ocede a ejecu a appoin men .mzn se debe ealiza una lec u a del iche o con
ex ensión .dzn gua dando los alo es Q, , R y c de en a iables según su ipo ap opiado pa a su
pos e io uso en es e mismo p og ama. Aquí des aca mi labo jun o con la supe isión de mi
compañe a Bea iz que an es de la ejecución de appoin men .mzn ealizó a ias unciones que
calculan el ec o de anonima o base y el ec o de anonima o alea o io esc ibiéndolos en el
iche o .dzn pa a su pos e io compa ación con el ec o que se gene a á a con inuación po
MiniZinc.
Después de es a lec u a, además mi labo se ha cen ado en la llamada a MiniZinc a pa i de Ja a,
y ac ualiza los alo es del iche o .dzn con los alo es de uel os po appoin men .mzn.
Debemos menciona que g acias a es e T abajo Fin de G ado hemos expandido nues os
conocimien os u ilizando Pos g eSQL po p ime a ez, así como la p og amación con
es icciones (MiniZinc) y la implemen ación de un p og ama en Bash Shell.
Pa a la elabo ación del p og ama Bash Shell, nos eunimos pa a ealiza dos e siones, una en
español y o a en inglés, e inándolos du an e el desa ollo de los expe imen os.
Cabe des aca , la g an labo de mi compañe a Bea iz en la ealización de los expe imen os a
pa i de los pa áme os es ablecidos po odo el equipo de es e T abajo Fin de G ado (el u o y
noso as dos).
Pa a el pos e io análisis de los expe imen os, elabo amos a ias ablas pa a compa a los dis in os
alo es que se gene a on a pa i de oda la implemen ación an e io y pode llega a cie as
conclusiones.
Finalmen e, la esc i u a de es a memo ia se ha ealizado o almen e en conjun o en e los
componen es del equipo que ha desa ollado es e T abajo Fin de G ado.
16
Edad
CP
Géne o
Núme o de
P o esiones
Recu so
Alea o io
16
2
0
1
3
17
1
0
1
3
16
1
1
1
1
16
2
1
1
5
17
2
0
1
1
16
2
1
1
4
17
2
1
1
3
16
1
1
1
4
16
2
0
1
5
16
2
0
1
2
18
1
1
1
4
16
2
1
1
2
16
1
0
1
2
18
2
0
1
2
18
1
1
1
5
Tabla 3
Como se puede obse a en la abla 1, los campos que son: ID, que ep esen a el nomb e y
apellidos del indi iduo; su edad; su Código Pos al (CP) y su p o esión.
La abla 2 se compone de dos campos; ecu so, que es una ep esen ación del hospi al y la ho a
de la ci a, y la capacidad de cada ecu so, es deci , cuan os indi iduos pueden acudi a un ecu so
conc e o.
En la abla 3, se elimina el campo ID, que iden i ica el nomb e y apellidos del indi iduo pa a
ga an iza cie o anonima o. Es os son los da os iniciales de los que se pa e. Se puede comp oba
que el anonima o base es: (5, 2, 2).
Así mismo se añade un nue o campo, Recu so Alea o io, que hace e e encia a uno de los ecu sos
de la abla 2. Pa a el in e és de la comunidad cien í ica, se p e ende publica no sólo los da os de
la población, sino ambién las ci as gene adas expues as en la abla 3, conse ando cie o
anonima o.
El siguien e apa ado explica el mecanismo que pe mi e gene a de o ma alea o ia an o la
población como sus ecu sos. Pos e io men e, se explica á de qué mane a se asignan los ecu sos
a cada indi iduo de la población, simulando así una gene ación alea o ia de ci as.
2.1 Población y ecu sos
Pa a la ep esen ación de un segmen o de población especí ico, se es ablecen los siguien es
campos:
En p ime luga , se indica la po ción de población que se quie e es udia , así como el ango de
edades, es deci , edad mínima y máxima de los pacien es que se an a examina ; ambién se
incluye la can idad de códigos pos ales pa a de e mina la zona en la que i e la población, el
géne o de la población, ep esen ados po : 0 pa a muje , 1 pa a homb e y 2 e i iéndose a ambos

17
géne os. Finalmen e, ambién pa ame izamos la población con el núme o de p o esiones, que
ep esen a la ac i idad que desempeña cada indi iduo.
Así mismo, se debe de alla la can idad de ecu sos disponibles, indicando la capacidad mínima
y máxima que puede ene cada ecu so, asegu ando que es os ecu sos pueden cub i a oda la
población c eada.
Todos es os da os, an o los de la población como los de los ecu sos, son indicados po el usua io
de nues a aplicación, lo que nos pe mi e ealiza simulaciones de di e sas si uaciones.
Edad
CP
Géne o
Recu so
No mal
Recu so
Alea o io
16
2
0
17
1
0
16
1
1
16
2
1
17
2
0
16
2
1
17
2
1
16
1
1
16
2
0
16
2
0
18
1
1
16
2
1
16
1
0
18
2
0
18
1
1
Tabla 4*
Pa a almacena la población gene ada a pa i de los pa áme os desc i os an e io men e, se hace
uso de Pos g eSQL, un sis ema de ges ión de bases de da os elacional. Un ejemplo de abla de
población gene ada puede e se en la abla 4. Nó ese la exis encia de dos columnas acías,
ecu so alea o io y ecu so no mal. El p ime o simula á la asignación de ci as alea o ia, como
e emos en es e mismo capí ulo. El segundo se gene a á u ilizando p og amación con
es icciones, de es a o ma pod emos es ablece una compa a i a en e ambos mé odos.
Igualmen e, se gene a á una abla de allando la in o mación de los ecu sos, como se puede
obse a en la abla 2. Todos es os da os se ob ienen gene ando núme os alea o ios a pa i de los
pa áme os iniciales ijados po el usua io, siemp e asegu ando a que los ecu sos gene ados
cub en a odos los indi iduos maximizando la capacidad de cada ecu so has a que se asegu e que
se a ende á a odo el segmen o de población.
*Se ha eliminado el campo “Núme o de p o esiones” ya que iene el mismo alo pa a odos los indi iduos.
18
2.2 Gene ación alea o ia de ci as
T as gene a la in o mación del segmen o de población a examina , y de alla los ecu sos de los
que se dispone, se p ocede a asigna un ecu so a cada indi iduo de la población de o ma
alea o ia; además de que no se supe e la capacidad máxima de cada ecu so y que se asegu e una
ci a pa a cada indi iduo.
ID
Edad
CP
Géne o
Núme o de
P o esiones
Recu so
No mal
Recu so
Alea o io
1
16
2
0
1
3
2
17
1
0
1
3
3
16
1
1
1
1
4
16
2
1
1
5
5
17
2
0
1
1
6
16
2
1
1
4
7
17
2
1
1
3
8
16
1
1
1
4
9
16
2
0
1
5
10
16
2
0
1
2
11
18
1
1
1
4
12
16
2
1
1
2
13
16
1
0
1
2
14
18
2
0
1
2
15
18
1
1
1
5
Tabla 5
En la abla 5 se mues a la asignación de los ecu sos de o ma alea o ia a cada uno de los
indi iduos. Obsé ese que se espe an los lími es de las capacidades máximas de los ecu sos
iniciales.
19
3 | Vec o es de Anonima o
3.1 Insu iciencia del k-anonima o
Como se ha explicado en el capí ulo 1, en pa icula den o del apa ado Nociones de Anonima o,
exis en a ibu os a los que denominamos cuasi-iden i icado es; median e los cuales se puede
llega a e ela la iden idad de un indi iduo, o incluso su diagnós ico.
Po ejemplo, en las ablas del capí ulo an e io se han conside ado como cuasi-iden i icado es a
los a ibu os edad, código pos al y géne o. En es e capí ulo de momen o no conside amos como
cuasi-iden i icado la ci a (la asignación de un indi iduo a un ecu so).
El obje i o de es e capí ulo es mos a que el concep o de k-anonima o no e leja de o ma
su icien emen e p ecisa el anonima o de una población.
Pa a ejempli ica es o, se exponen a con inuación es ejemplos de poblaciones ob enidos a pa i
de los mismos pa áme os iniciales:
Edad
CP
Géne o
Núme o de
P o esiones
Recu so
Alea o io
16
2
0
1
3
17
1
0
1
3
16
1
1
1
1
16
2
1
1
5
17
2
0
1
1
16
2
1
1
4
17
2
1
1
3
16
1
1
1
4
16
2
0
1
5
16
2
0
1
2
18
1
1
1
4
16
2
1
1
2
16
1
0
1
2
18
2
0
1
2
18
1
1
1
5
Tabla 6
20
Edad
CP
Géne o
Núme o de
P o esiones
Recu so
Alea o io
17
2
1
1
5
18
2
1
1
3
16
2
1
1
1
18
2
0
1
3
17
1
1
1
3
17
1
0
1
2
18
1
1
1
4
17
2
1
1
4
17
1
1
1
2
18
2
0
1
5
17
2
1
1
5
18
1
0
1
5
17
1
0
1
1
18
2
1
1
1
18
1
0
1
1
Tabla 7
Edad
CP
Géne o
Núme o de
P o esiones
Recu so
Alea o io
18
2
1
1
2
16
2
0
1
2
17
1
0
1
5
16
1
0
1
5
18
2
1
1
3
18
1
1
1
4
16
1
0
1
5
17
2
0
1
2
16
1
0
1
3
16
2
0
1
1
18
2
1
1
1
18
2
1
1
1
17
2
0
1
4
18
1
0
1
4
18
2
1
1
4
Tabla 8
Analizando las ablas se comp ueba que:
 En la abla 6 se e i ica que el cuasi-iden i icado (edad=17, código pos al=2,
géne o=1) (que a pa i de aho a se esc ibe de o ma ab e iada con la upla (17, 2, 1)),
solo apa ece una ez.
 En la abla 7 el cuasi-iden i icado (18, 1, 1) apa ece igualmen e una sola ez.
 Análogamen e, en la abla 8 el cuasi-iden i icado (18, 1, 1) apa ece una sola ez.
De aquí se deduce que, en las es p uebas ealizadas, se e i ica un ni el de 1-anonima o. Sin
emba go, no se puede asumi que las es ablas ienen el mismo ni el de anonima o. Es e dad
que en las es hay al menos un indi iduo cuyo cuasi-iden i icado se epi e solo una ez, pe o en
la abla 6 se pueden iden i ica o as a cinco pe sonas en la misma si uación, mien as que en las
ablas 7 y 8 se pueden iden i ica a dos y es pe sonas espec i amen e.
21
Po consiguien e, pa ece lógico conclui que la abla 7 iene mayo ni el de anonima o, po que
iene “solo” a dos pe sonas en iesgo, en e a las es o cinco pe sonas cuya iden idad pod ía se
des elada en los o os casos.
Se necesi a po an o una mejo de inición, que enga en cuen a no solo el ni el de k-anonima o
sino cuán as pe sonas es án en ese ni el. Es a idea nos lle a á al concep o de ec o de anonima o.
3.2 De inición de ec o de anonima o
El ec o de anonima o cuen a el núme o eces que se epi e cada alo que oma el cuasi-
iden i icado en la abla. Es a in o mación se ep esen a en o ma de ec o , de al mane a que po
ejemplo la posición 1 del ec o con iene el núme o de cuasi-iden i icado es que se epi en una
sola ez. Análogamen e, la posición 2 cuen a el núme o de cuasi-iden i icado es con dos
epe iciones, y así sucesi amen e.
En la siguien e abla se lis an los dis in os alo es de cuasi-iden i icado es que apa ecen en las
es ablas del ejemplo, además de las eces que apa ecen epe ido cada cuasi-iden i icado en
cada abla:
Q
Tabla 6 (=9)
Tabla 7(=8)
Tabla 8(=7)
q1 = (16,2,0)
3
0
2
q2 = (17,1,0)
1
2
1
q3 = (16,1,1)
2
0
0
q4 = (16,2,1)
3
1
0
q5 = (17,2,0)
1
0
2
q6 = (17,2,1)
1
3
0
q7 = (18,1,1)
2
1
1
q8 = (16,1,0)
1
0
3
q9 = (18,2,0)
1
2
0
q10 = (18,2,1)
0
2
5
q11= (17,1,1)
0
2
0
q12 = (18,1,0)
0
2
1
Tabla 9
Po ejemplo, nó ese que en la abla 6 iene, como se ha dicho an e io men e, 5 cuasi-
iden i icado es con una sola epe ición, conc e amen e q2, q5, q6, q8 y q9. A pa i de es a idea,
la abla 9 se puede ep esen a de o ma ab e iada mos ando cuán as eces apa ece cada
epe ición del cuasi-iden i icado en cada p ueba:
Tabla k
1
2
3
4
5
Tabla 6
5
2
2
0
0
Tabla 7
2
5
1
0
0
Tabla 8
3
2
1
0
1
Tabla 10

22
La ilas de la abla co esponden di ec amen e con los ec o es de anonima o: (5,2,2,0,0) pa a la
Tabla 6, (2,5,1,0,0) pa a la Tabla 7, y (3,2,1,0,1) pa a la Tabla 8.
Algunas p opiedades de es os ec o es:
P1. El k-anonima o co esponde a la posición del p ime alo dis in o de 0 empezando po la
izquie da. En el ejemplo las es ablas e i ican k=1.
P2. Los ce os a la de echa no cuen an, es deci se puede conside a (5, 2, 2, 0, 0) y (5, 2, 2) el
mismo ec o de anonima o. En gene al llamamos longi ud l de un ec o de anonima o a la
posición más a la de echa que enga un alo dis in o de 0. En el ejemplo = (5, 2, 2, 0, 0)
habla íamos de una longi ud l = 3.
P3. Dada una población de amaño n, con un ec o de longi ud l, se cumple que:
 sum (i = 1, i = l) [i] * i = n.
Po ejemplo, el ec o = (5, 2, 2, 0, 0) co esponde a una población de 5*1+2*2+2*3 = 15 (en
o as palab as 5 alo es del cuasi-iden i icado se epi en una ez, dos alo es se epi en dos eces,
y o os dos alo es del cuasi-iden i icado apa ecen es eces).
Aho a esul a ácil compa a ec o es de anonima o, siguiendo el o den lexicog á ico que se
ep esen a po < . En es e caso se iene:
(2,5,1,0,0) < (3,2,1,0,1) < (5,2,2,0,0)
P4. Un ec o meno signi ica más anonima o y po an o aho a podemos deci que la abla 7
ep esen a un mejo (mayo ) anonima o. La cua a p opiedad indica que nues os ec o es son un
e inamien o del concep o de k-anonima o.
P5. Sean 1, 2 dos ec o es de anonima o pa a dos ablas T1, T2 de amaño n, ales que T1
e i ica k1-anonima o y T2 k2-anonima o. En onces, si 1< 2, se cumple k1 >= k2.
Así mismo, median e la columna de ecu sos alea o ios, se gene an nue os ec o es de anonima o
que in o man del epa o alea o io de las ci as, de aquí en adelan e llamados “ ec o alea o io”.
Los ec o es alea o ios de las ablas 6, 7 y 8 son espec i amen e (15), (13,1) y (11,2).
A pa i de dichos ec o es, los ec o es iniciales de la abla 10 y eniendo en cuen a lo expues o
en la p opiedad 3 (P3), se obse a que el anonima o empeo a signi ica i amen e.
Nó ese, po ejemplo, que en el ec o inicial co espondien e a la abla 6 (5, 2, 2) se pasa de
iden i ica 5 pe sonas a pode iden i ica has a 15 pe sonas lo que conlle a a una g an pé dida de
anonima o.
También se gene a una pé dida de anonima o a la ho a de inclui nue os a ibu os que iden i ican
a los cuasi-iden i icado es, ya que aumen a á su a iación, es deci que se e ía la abla 9 más
ex endida.
23
4 | Anonima o como P oblema de op imización en
P og amación con Res icciones
4.1 P og amación con Res icciones
Pa a ob ene el mejo ec o de anonima o posible se u iliza el pa adigma de p og amación
conocido como p og amación con es icciones.
La p og amación con es icciones es un es ilo de p og amación que ag upa a muchos lenguajes.
Se puede encuad a den o del pa adigma de la p og amación decla a i a, donde el p og amado
indica qué quie e consegui sin de alla los pasos que hay que segui pa a log a lo pues o que el
sis ema es el que dispone de o ma in e na de los mé odos que u iliza án pa a log a el obje i o
p opues o po el p og amado . Además, la p og amación con es icciones y la p og amación
lógica se combinan de o ma na u al en la llamada p og amación lógica con es icciones
(Cons ain Logic P og amming o pa adigma CLP) [3].
En p og amación con es icciones se de inen a iables sob e un cie o dominio (po ejemplo,
en e os, booleanos, eales, e c.), y se indican las elaciones que deben cumpli las a iables en e
sí. El esul ado es un p og ama al que se le suele llama modelo.
Po ejemplo, usando no ación del lenguaje de es icciones MiniZinc [9] podemos de ini modelos
como el siguien e:
El p og ama, en es e caso MiniZinc, usa esolu o es adecuados pa a encon a alo es de las
a iables que sa is agan el modelo. En es e caso encuen a la solución:
x = 10;
y = 2;
24
En p og amación con es icciones no solo se plan ean p oblemas de sa is acción como el an e io ;
ambién se pueden de ini p oblemas de op imización:
En es e caso buscamos el mayo alo de x que sa is ace el modelo, y el esolu o nos de uel e
las siguien es posibles soluciones:
x = 10;
y = 1;
----------
Se a a modela el p oblema de anonima o como un p oblema de op imización en el lenguaje
MiniZinc.
25
4.2 El modelo
Vamos a ob ene el ec o de anonima o de o ma i e a i a; cada ez que se aplique el modelo se
ob end án un nue o componen e del ec o . Pa a ello de inimos un modelo que cons a de dos
pa es:
 El modelo en sí, que busca minimiza la posición l del ec o .
 Un iche o de pa áme os con ex ensión .dzn que a a iando, indicando el alo
de l, y los alo es an e io es ya encon ados.
Las i e aciones son con oladas desde un p og ama Ja a, que a modi icando el iche o de
pa áme os has a comple a un ec o de anonima o óp imo que cub a oda la población.
Pa a explica el modelo el p ime paso es de ini los pa áme os que se an a usa :
 Q: núme o de cuasi-iden i icado es di e en es.
 : ec o que ep esen a la ecuencia de cada cuasi-iden i icado , es deci , el
núme o de eces que se epi e cada cuasi-iden i icado .
 R: su alo ep esen a el núme o de ecu sos de los que se dispone.
 c: ec o de capacidades de cada ecu so.
Un ejemplo de dzn inicial al que se i án añadiendo alo es cada ez que se ob enga un esul ado
del p og ama MiniZinc, de aquí en adelan e appoin men .mzn, se mues a en la siguien e imagen:
Imagen 1
32
A con inuación se mos a án los de alles de 5 p uebas de las 20 gene adas pa a cada uno de los
casos an e io es, habiendo sido elegidas po su dispa idad en e sus da os.
Población
N = 10
Caso
Vec o
alea o io
Vec o
anonima o
Mejo a de
anonima o
Tiempo de
ejecución
P ueba 1
P ime caso
(8, 1)
(5,1,1)
0,7999
2´35
segundos
Segundo caso
(6,2)
(2,2,0,1)
0,8125
2´35
segundos
P ueba 2
P ime caso
(8,1)
(2,1,2)
0,9411
2´35
segundos
Segundo caso
(8,1)
(1,3,1)
0,9545
2´35
segundos
P ueba 3
P ime caso
(10)
(3,2,1)
0,9999
2´35
segundos
Segundo caso
(4,3)
(2,2,0,1)
0,5625
2´35
segundos
P ueba 4
P ime caso
(6,2)
(3,2,1)
0,7272
2´35
segundos
Segundo caso
(5,1,1)
(3,2,1)
0,5
2´35
segundos
P ueba 5
P ime caso
(10)
(4,3)
1
2´35
segundos
Segundo caso
(2,4)
(0,0,2,1)
0,5946
2´35
segundos
Tabla 11
Al se una población an pequeña no hay di e encia en el iempo de ejecución en ambos casos, en
cambio sí que se puede ap ecia la mejo a de anonima o al ealiza la compa ación en e los
ec o es alea o io y anonima o.
Como se ha explicado en el apa ado 3.2 y omando en cuen a los da os de las columnas ec o
alea o io y ec o anonima o, se concluye que el ec o anonima o gene ado g acias a MiniZinc
es mejo que el ec o alea o io debido a que, cogiendo po ejemplo el segundo caso de la p ime a
p ueba, se iden i ican a 4 pe sonas menos que si se oma a en cuen a el ec o alea o io.
Así mismo, u ilizando o a ez el ejemplo an e io , se obse a una mejo a del anonima o de
0,8125 (81’25%) con espec o al ec o alea o io.
Nó ese que en el p ime caso de la quin a p ueba, compa ando el ec o alea o io con el ec o
anonima o se ha conseguido una mejo a del 100% (1), es deci , se pasa de des ela la iden idad

33
de oda la población, a des ela solo al 40% de la población, eniendo en cuen a que el ec o
alea o io es el peo ec o posible que se puede consegui .
34
Población
N = 20
Caso
Vec o
alea o io
Vec o de
anonima o
Mejo a de
anonima o
Tiempo de
ejecución
P ueba 1
P ime caso
(14,3)
(3,4,3)
0,7331
80 segundos
Segundo
caso
(14,3)
(0,2,1,2,1)
0,9868
3 segundos
P ueba 2
P ime caso
(12,4)
(4,5,2)
0,5208
62 segundos
Segundo
caso
(5,3,3)
(0,3,2,2)
0,7051
2’85
segundos
P ueba 3
P ime caso
(16,2)
(4,5,2)
0,9210
224
segundos
Segundo
caso
(4,8)
(0,3,3,0,1)
0,6505
2’85
segundos
P ueba 4
P ime caso
(20)
(4,5,2)
0,9999
300
segundos
Segundo
caso
(4,8)
(1,2,2,1,1)
0,5465
3 segundos
P ueba 5
P ime caso
(15,1,1)
(5,6,1)
0,9489
247
segundos
Segundo
caso
(13,2,1)
(1,0,2,2,1)
0,9759
2’85
segundos
Tabla 12
Al aumen a la población, se inc emen a el iempo de ejecución, y así mismo se obse a una g an
di e encia en e los iempos del p ime caso y del segundo caso, mos ados en la Tabla 12, debido
a, no sólo que el p ime caso iene o o a ibu o más como ep esen an e del cuasi-iden i icado ,
sino ambién se disponen de más ecu sos, pe o con menos capacidades que en el segundo caso.
Todo es o conlle a a que las poblaciones de los p ime os casos de las p uebas es én más
dispe sadas con espec o a las poblaciones de los segundos casos en cuan o a la asignación de
ci as.
Tomando como ejemplo la p ueba 4, debido a la g an di e encia en e los da os de sus casos, se
obse a una di e encia de mejo a espec o a los ec o es de alea o io y anonima o; en el p ime
caso del 0,9999 (99,99%) y en el segundo caso del 0,5465 (54,65%) además de un iempo de
ejecución muy dispa , que pasa de los 5 minu os que a dó el p ime caso, a los escasos 3 segundos
que a dó el segundo.
35
Población
N = 30
Caso
Vec o
alea o io
Vec o de
anonima o
Mejo a de
anonima o
Tiempo de
ejecución
P ueba 1
P ime caso
(28,1)
(3,1,3,4)
0,9996
360
segundos
Segundo
caso
(10,7,2)
(1,0,1,1,3,0,1)
0,8714
3,95
segundos
P ueba 2
P ime caso
(26,2)
(0,7,4,1)
0,9862
120
segundos
Segundo
caso
(10,10)
(0,0,2,2,2,1)
0,8992
3,95
segundos
P ueba 3
P ime caso
(24,3)
(3,5,3,2)
0,9963
148
segundos
Segundo
caso
(12,9)
(0,0,4,2,2)
0,9383
4 segundos
P ueba 4
P ime caso
(20,5)
(0,5,4,2)
0,9935
324
segundos
Segundo
caso
(18,3,2)
(0,1,1,0,1,1,2)
0,9887
3,86
segundos
P ueba 5
P ime caso
(22,4)
(2,4,4,2)
0,9784
227
segundos
Segundo
caso
(14,8)
(0,1,0,2,0,1,2)
0,9661
4 segundos
Tabla 13
En el caso de la población de amaño 30 se consigue una g an mejo a de anonima o, pues o que
en casi odas las p uebas se ha mejo ado an o el k-anonima o como el ec o de anonima o, pe o
el iempo de ejecución se ha inc emen ado de una mane a d ás ica con espec o a las o as
poblaciones.
A pa i de los da os del p ime caso de la p ueba 1, se puede conclui que, a pesa de que el ec o
anonima o sigue eniendo un 1-anonima o, igual al k-anonima o del ec o alea o io, la mejo a es
del 0,9996 (99,96%) debido a la g an di e encia en e ambos ec o es de anonima o, pasando de
des ela la iden idad de has a 28 pe sonas, a iden i ica solo 3.
En el p ime caso de la p ueba 4, no solo se mejo a el ec o de anonima o un 0,9935 (99,35%)
sino que ambién se mejo a el k-anonima o, pasando de 1-anonima o a 3-anonima o.
36
6 | Implemen ación
Pa a almacena la in o mación gene ada sob e la población, se hace uso de una base de da os
elacional Pos g eSQL [8].
Pos g eSQL es g a ui o y lib e que pe mi e desa olla bases de da os elacionales obus as y
e icien es, además de que o ece una g an can idad de opciones a anzadas. De hecho, es
conside ado el mo o de base de da os más a anzado en la ac ualidad, además de apo a mucha
lexibilidad a di e en es p oyec os. Po ejemplo, pe mi e de ini unciones pe sonalizadas po
medio de a ios lenguajes, en es e caso u ilizando PL/Ja a.
O a en aja de Pos g eSQL es que es á disponible pa a muchas pla a o mas y o ece el código
uen e desde el si io o icial como Mac OS X. Windows y Ubun u.
Así mismo, Pos g eSQL o ece la he amien a o icial pgAdmin pa a adminis a sus bases de
da os, dando la opción ambién de adminis a las bases de da os median e línea de comandos.
Pa a el desa ollo so wa e de es e p oyec o se ha empleado Ja a como lenguaje de p og amación
p incipal u ilizando el en o no de p og amación Eclipse.
Se ha op ado po Eclipse po se uno de los p incipales en o nos de p og amación que se ha
u ilizado du an e la ca e a, debido a se código abie o y mul ipla a o ma además de su in e az
in ui i a y sencilla.
Así mismo, se ha empleado ambién MiniZinc, explicado en el ema 4, y se ha hecho uso de Bash
Shell pa a uni ica odos los p og amas que o man es e p oyec o y calcula cuán o iempo a da
en ejecu a se el p oyec o comple o.
La implemen ación de es e p oyec o se di idido en dis in os p oyec os de Ja a, cada uno con una
o a ias unciones asignadas.
Pa a la co ec a ejecución del p ime p og ama, se debe asigna un alo a odos los campos
eque idos. Sin emba go, si no se han ellenado co ec amen e los campos, se in e umpi á el
p og ama mos ando un mensaje de e o in o mando sob e la causa del p oblema.
Pa a la conexión con la base de da os Pos g eSQL del usua io median e el conec o JDBC, los
p ime os campos que se solici an son la u l de la base de da os, el usua io y la con aseña de la
misma.
Pa a la c eación de los da os ic icios, se debe especi ica p ime o el nomb e de la abla en la que
se gua da á la in o mación, el núme o de pe sonas que se quie e es udia , así como el ango de
edades, es deci , edad mínima y máxima de los pacien es que se an a examina ; ambién se
incluye la can idad de códigos pos ales pa a de e mina la zona en la que i e la población el
géne o de la población, ep esen ados po : 0 es muje , 1 es homb e y 2 se e ie e a ambos; y el
núme o de p o esiones, que ep esen a la ac i idad que desempeña cada indi iduo. Además, el
usua io debe indica la can idad de ecu so, que ep esen a la ho a, día y hospi al de la ci a s de
los que dispone y especi ica el ango de capacidad de cada uno, pa a que se asigne alea o iamen e
una capacidad pa a cada ecu so, es ando den o de los lími es del ango in oducido.
37
Así mismo el p og ama au omá icamen e gene a á o a abla en la que se e lejan el núme o de
ecu sos y la capacidad de cada uno, a pa i del nomb e de la abla indicado.
Si la capacidad máxima o al de odos los ecu sos es meno que el núme o de pacien es
in oducidos, se ajus a án las capacidades de los ecu sos necesa ios pa a cub i a odos los
pacien es has a el máximo indicado.
Cabe des aca , que, si el nomb e de las ablas a c ea ya exis ía con an e io idad, se elimina án de
la base de da os pa a e i a la sob e esc i u a.
En el segundo p og ama se ealiza un nue o acceso a la base de da os del usua io comp obando
que las ablas ya se han c eado y que con ienen in o mación. El obje i o de es e p oyec o es
ealiza una asignación alea o ia de los ecu sos eniendo en cuen a sus capacidades, ac ualizando
el campo ecu so alea o io de la abla de la población.
Du an e el lujo de abajo de es e p oyec o se ha que ido sabe el alo de k-anonima o de la
población c eada, que depende á de los a ibu os indicados po el usua io que ep esen an los
cuasi-iden i icado es. Pa a ello se ha lle ado a cabo la c eación del e ce p og ama que mues a
po pan alla dicho ni el de anonima o.
En el cua o p og ama, se p ocede a c ea el iche o con ex ensión dzn pa a la pos e io ejecución
del código MiniZinc.
Pa a ello se eu iliza á los a ibu os asignados po el usua io en el p og ama es. Además, se
econec a á a la base de da os de Pos g eSQL pa a ealiza los cálculos necesa ios pa a esc ibi
los siguien es da os en el iche o:
 Q: núme o de cuasi-iden i icado es di e en es.
 : ec o que ep esen a la ecuencia de cada cuasi-iden i icado , es deci , el
núme o de eces que se epi e cada cuasi-iden i icado .
 R: su alo ep esen a el núme o de ecu sos de los que se dispone.
 c: ec o de capacidades de cada ecu so.
A con inuación, se p ocede a la ejecución del quin o p og ama que incluye las siguien es
unciones:
o Accede a MiniZinc median e una llamada a la línea de comandos (cmd),
u ilizando el iche o con ex ensión mzn, explicado en el ema 4 y el iche o .dzn
gene ado an e io men e. Pa a gene a una nue a asignación de ci as.
Un ejemplo de iche o .dzn se puede obse a en la imagen 1 en el apa ado 4.2
El Modelado.

38
El p og ama accede á a MiniZinc has a que se hayan asignado ci as a oda la
población. Es o se consigue median e la decla ación de las siguien es a iables:
 p = ∑ [i]
𝑄
𝑖=1 Es la población o al a examina .
 l = 1 El siguien e ni el del ec o de anonima o a
esol e .
 = [] Vec o de anonima o, inicialmen e con 0
componen es.
o Lee los esul ados gene ados po MiniZinc y esc ibi los en el iche o dzn de al
mane a que se pueden e los dis in os ec o es de anonima o gene ados.
Imagen 2
La asignación de ci as se da po inalizada una ez que la suma de los alo es del
ec o mul iplicados po su índice es igual a la población o al ( ∑ [n]
𝑙−1
𝑛=1 ∗
𝑛 < 𝑃 ), mien as que no se cumpla es a condición, el p og ama aumen a á el
ec o además de inse a en la úl ima posición de ( [l]), el anonima o
gene ado po appoin men .mzn. Así mismo, se inc emen a á el siguien e alo de
l a esol e .
o U ilizando los da os gene ados po el p og ama MiniZinc, se calcula la dis ancia
en e los ec o es pa a demos a si se ha p ocedido a mejo a o empeo a el ni el
de anonima o.
39
Imagen 6
Como se ha mencionado al p incipio de es e ema, se ha implemen ado un pequeño p og ama en
Shell pa a ejecu a los p og amas an e io es en se ie. De es a mane a, se pueden c ea a ios
modelos de población con los mismos da os in oducidos po el usua io inal, ob eniendo
di e en es esul ados.
Pa a la c eación de los modelos de población se pide al usua io in oduci el núme o de p uebas
que desea ealiza además de odos los pa áme os eque idos pa a la co ec a ejecución de los
p og amas explicados an e io men e.
Si se quie e calcula el iempo que se a da en gene a cada expe imen o, se puede u iliza a la
ez el comando ime [10], que mos a á al inaliza la ejecución los siguien es iempos:
 el iempo eal anscu ido en e la llamada y la inalización de o den.
 el iempo de usua io del p ocesado ( ms_u ime + ms_cu ime).
 el iempo de sis ema del p ocesado ( ms_s ime + ms_cs ime.)
40
7 | Conclusiones y abajo u u o
Hemos ealizado un sis ema de ci as que ga an iza el mejo anonima o posible u ilizando el
concep o de k-anonima o.
Du an e el p oyec o hemos comp obado que el concep o de k-anonima o no es su icien e y po
eso u ilizamos un concep o ampliado, el ec o de anonima o.
Como se ha mencionado an e io men e, pa a consegui el k-anonima o u ilizamos en un p ime
momen o el esolu o base minizinc, pe o como el iempo de ejecución e a demasiado al o,
op amos po el esolu o mzn-gecode, que disminuyó no ablemen e dicho iempo. Aun así, al
aumen a el amaño de la población, el iempo de ejecución ambién se inc emen a de o ma
signi ica i a.
Po el mo i o an e io , podemos conclui que el cuello de bo ella de nues o p oyec o es MiniZinc.
Dicha he amien a es el cuello de bo ella de nues o p oyec o, es deci , cada ez que la población
es mayo , el esolu o inc emen a á el iempo de ejecución, po lo que, como se obse a en el
apa ado 5.2, el iempo aumen a de o ma signi ica i a.
La p og amación con es icciones solo es álida pa a poblaciones pequeñas, sin emba go, da una
medida del meno ec o de anonima o que se puede emplea pa a comp oba la bondad de o os
mé odos de asignación aplicables a poblaciones de amaño eal.
Du an e los expe imen os ealizados, hemos llegado a las siguien es conclusiones:
 Ve i icamos que al compa a el ec o de anonima o alea o io y el gene ado po
P og amación con Res icciones, no siemp e se ob iene una mejo a desde el pun o de
is a del k-anonima o, ya que es o depende no solo del núme o de alo es de cuasi-
iden i icado es, sino ambién del núme o de ecu sos de los que se dispone.
 Aunque el k-anonima o no a íe, eso no signi ica que el ec o alea o io y el ec o
anonima o sean iguales, es deci , se puedan iden i ica menos pe sonas en el ec o
anonima o en e al ec o alea o io.
 Se puede consegui casi el 100% de mejo a compa ando los ec o es alea o io y
anonima o sin que a íe el k-anonima o, en el caso de que ambos ec o es co espondan
con el mismo k.
 Una mane a de aumen a la dis ancia en e el ec o alea o io y el ec o anonima o, es
aumen ando la longi ud del ec o de anonima o, es deci , dispe sa más la población a la
ho a de asigna las ci as.
41
Hay que no a que o os concep os de anonima o como l-Di e si y [5] y -Closeness [6] no son
aplicables en el momen o de la asignación de ci as po que dependen del alo inal de los
esul ados del es de sc eening, mien as que noso os es amos en el con ex o de las ci as, cuando
aún no es isible el esul ado inal. Sin emba go, es os concep os sí se án aplicables una ez
acabado el es , y se bene icia án de la asignación de ci as inicial.
Como abajo u u o es a ía desa olla una nue a écnica de asignación de ci as que sopo e
poblaciones más g andes, y que, sin alcanza el mejo anonima o sí que mejo e la asignación
alea o ia ealizada en la ac ualidad.