Extensión del concepto de utopía para el problema de la agregación de rankings sin empates

Palabras clave: Agregación de rankings, programación lineal entera, minería de datos, algoritmos de optimización

Resumen

El uso de los rankings y la forma de agregarlos o resumirlos ha recibido una atención creciente en diversos campos: bibliometría, búsquedas web, minería de datos, estadística, calidad educativa y biología computacional. Para el Problema de Ordenamiento Óptimo con empates fue introducido recientemente el concepto de Matriz Utópica: una solución ideal y no necesariamente factible con una calidad insuperable para las soluciones factibles del problema. Este trabajo propone una extensión de la noción de Matriz Utópica para el Problema de Agregación de Rankings en que no se permiten empates entre elementos en el ranking de salida. Más allá de la extensión que es directa, el trabajo se centra en estudiar su valor como idealización o solución súper óptima. Como el Problema de Agregación de Rankings puede resolverse de forma exacta a partir de su definición como Problema de Programación Lineal Entera, se presenta un estudio experimental donde se analiza la relación que existe entre los valores utópicos (y anti utópicos) y la solución óptima en instancias resueltas con la ayuda del software de código abierto SCIP. Entre las 47 instancias analizadas, en 19 el Valor Utópico resultó ser igual al valor óptimo (40,43 % de factibilidad) y en 18 el Valor Anti Utópico también resultó ser factible (38,00 %). Este estudio experimental demuestra la utilidad de los valores utópicos y anti utópicos para ser considerados como valores extremos en el Problema de Agregación de Rankings, pudiendo así encontrase muy rápidamente cotas superiores e inferiores para la optimización.

Biografía del autor/a

Randy Reyna-Hernández*, Universidad de Matanzas, Cuba

Universidad de Matanzas, Matanzas-Cuba, randyrh91@gmail.com

Alejandro Rosete, Universidad Tecnológica de La Habana “José Antonio Echeverría”, Cuba

Universidad Tecnológica de La Habana “José Antonio Echeverría”, La Habana-Cuba, rosete@ceis.cujae.cu

Referencias bibliográficas

H. Ramírez-Murillo; C. A. Torres-Pinzón; E. F. Forero-García, “Photovoltaic Potential Estimation by Means of Data Mining in Four Colombian Cities,” TecnoLógicas, vol. 22, no. 46, pp. 65–85, Sep. 2019. https://doi.org/10.22430/22565337.1345

F. Ganga-Contreras; J. López-Nunez; W. Sáez, “Portal de ranking de universidades iberoamericanas: una propuesta para facilitar procesos decisionales,” Rev. Ibérica Sist. e Tecnol. Informação, no. E25, pp. 472–488, Jan. 2020. https://search.proquest.com/docview/2350120514/fulltextPDF/5AB1DDD5F6D34FFDPQ/1

C. Dwork; R. Kumar; M. Naor; D. Sivakumar, “Rank Aggregation Methods for the Web,” in Proceedings of the 10th International Conference on World Wide Web, New York, 2001, pp. 613–622. https://doi.org/10.1145/371920.372165

L. J. Pérez Lugo, “Método para la agregación de rankings a partir de dos grupos con intereses contrapuestos,” (Tesis Doctorado), Facultad de Matemática, Física y Computación. Departamento de Ciencias de la Computación, Universidad Central “Marta Abreu” de Las Villas, 2015. https://dspace.uclv.edu.cu/handle/123456789/7315

D. Sculley, “Rank Aggregation for Similar Items,” in Proceedings of the Seventh SIAM International Conference on Data Mining, April 2007, Minneapolis, Minnesota, USA, 2007, pp. 587–592. https://doi.org/10.1137/1.9781611972771.66

S. Chaudhuri; G. Das; V. Hristidis; G. Weikum, “Probabilistic Ranking of Database Query Results,” in Proceedings of the Thirtieth International Conference on Very Large Data Bases, VLDB 2004, Toronto, Canada 2004, pp. 888–899. https://doi.org/10.1016/B978-012088469-8.50078-4

G. Dahl; H. Minken, “A note on permutations and rank aggregation,” Math. Comput. Model., vol. 52, no. 1–2, pp. 380–385, Jul. 2010. https://doi.org/10.1016/j.mcm.2010.02.052

H. L. Turner; J. van Etten; D. Firth; I. Kosmidis, “Modelling rankings in R: the PlackettLuce package,” Comput. Stat., vol. 35, no. 3, pp. 1027–1057, Feb. 2020. https://doi.org/10.1007/s00180-020-00959-3

V. Pihur; S. Datta; S. Datta, “RankAggreg, an R package for weighted rank aggregation,” BMC Bioinform., vol. 10, no. 62, Feb. 2009. https://doi.org/10.1186/1471-2105-10-62

A. Ali; M. Meila, “Experiments with Kemeny ranking: What works when?,” Math. Soc. Sci., vol. 64, no. 1, pp. 28–40, Jul. 2012. https://doi.org/10.1016/j.mathsocsci.2011.08.008

A. Rosete, “Reformulación eficiente del problema de programación lineal de agregación de rankings.,” Ing. Ind., vol. 39, no. 3, Dic. 2018. http://scielo.sld.cu/scielo.php?script=sci_arttext&pid=S1815-59362018000300250

J. Feng; Q. Fang; W. Ng, “Discovering bucket orders from full rankings,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2008, Vancouver 2008, pp. 55–66. https://doi.org/10.1145/1376616.1376625

A. Gionis; H. Mannila; K. Puolamäki; A. Ukkonen, “Algorithms for discovering bucket orders from data,” in Proceedings of the Twelfth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Philadelphia, PA, USA, August, 2006, pp. 561–566. https://doi.org/10.1145/1150402.1150468

J. A. Aledo; J. A. Gámez; A. Rosete, “Utopia in the solution of the Bucket Order Problem,” Decis. Support Syst., vol. 97, pp. 69–80, May. 2017. https://doi.org/10.1016/j.dss.2017.03.006

J. A. Aledo; J. A. Gámez; A. Rosete, “Approaching rank aggregation problems by using evolution strategies: the case of the optimal bucket order problem,” Eur. J. Oper. Res., vol. 270, no. 3, pp. 982–998, Nov. 2018. https://doi.org/10.1016/j.ejor.2018.04.031

J. A. Aledo; J. A. Gámez; D. Molina, “Approaching the rank aggregation problem by local search-based metaheuristics,” J. Comput. Appl. Math., vol. 354, pp. 445–456, Jul. 2019. https://doi.org/10.1016/j.cam.2018.03.014

C. Dwork; R. Kumar; M. Naor; D. Sivakumar, “Rank aggregation revisited.” Manuscript, 2001. http://web.cse.msu.edu/~cse960/Papers/games/rank.pdf

J. A. Aledo; J. A. Gámez; D. Molina; A. Rosete, “Consensus-based journal rankings: A complementary tool for bibliometric evaluation,” J. Assoc. Inf. Sci. Technol., vol. 69, no. 7, pp. 936–948, 2018. https://doi.org/10.1002/asi.24040

J. A. Aledo; J. A. Gámez; D. Molina, “Tackling the rank aggregation problem with evolutionary algorithms,” Appl. Math. Comput., vol. 222, pp. 632–644, Oct. 2013. https://doi.org/10.1016/j.amc.2013.07.081

D. Molina García, “Contribuciones al problema de agregación de rankings. Aplicaciones al aprendizaje automático.,” (Tesis Doctorales), Departamento de Matemáticas, Universidad de Castilla-La Mancha, 2015. https://ruidera.uclm.es/xmlui/handle/10578/7191

E. M. García Nové, “Nuevos problemas de agregación de rankings: Modelos y algoritmos,” (Tesis Doctorales), Departamento de Estadística, Matemáticas e Informática, Universidad Miguel Hernández de Elche, 2018. http://dspace.umh.es/bitstream/11000/4816/1/TD%20Garc%C3%ADa%20Nov%C3%A9%2C%20Eva%20Mar%C3%ADa%20.pdf

W. D. Cook; M. Kress; L. M. Seiford, “An axiomatic approach to distance on partial orderings,” RAIRO-Operations Res., vol. 20, no. 2, pp. 115–122, 1986. http://www.numdam.org/item/?id=RO_1986__20_2_115_0

T. Achterberg, “SCIP: solving constraint integer programs,” Math. Program. Comput., vol. 1, no. 1, pp. 1–41, 2009. https://doi.org/10.1007/s12532-008-0001-1

Z. I. Berlin, “SCIP: solving constraint integer programs,” 2017. https://www.scipopt.org/

N. Mattei; T. Walsh, “PrefLib: A Library for Preferences www.preflib.org,” in Algorithmic Decision Theory - Third International Conference, ADT 2013, Bruxelles, 2013, vol. 8176, pp. 259–270. https://doi.org/10.1007/978-3-642-41575-3_20

R. Reyna-Hernández, “Herramientas y ficheros para replicar y analizar los experimentos.” 2021. https://drive.google.com/drive/folders/18WoyFQaipbpblZs4P7yo_YOZ1m6L5r53?usp=sharing

Cómo citar
[1]
R. Reyna-Hernández y A. Rosete, «Extensión del concepto de utopía para el problema de la agregación de rankings sin empates», TecnoL., vol. 24, n.º 51, p. e1788, feb. 2021.

Descargas

Los datos de descargas todavía no están disponibles.
Publicado
2021-02-26
Sección
Artículos de investigación

Métricas

Crossref Cited-by logo