DOI:
https://doi.org/10.14483/23448350.22578Published:
12/07/2024Issue:
Vol. 51 No. 3 (2024): September-December 2024 (Continuos Publication)Section:
Research ArticlesShuffled Frog-Leaping Algorithm Metaheuristic for Extractive Single- Document Summarization
Algoritmo metaheurístico de saltos de ranas mezcladas para la generación automática de resúmenes extractivos de un solo documento
Keywords:
algorithms, artificial intelligence, automatic text analysis, data processing, information retrieval (en).Keywords:
análisis automático de textos, inteligencia artificial, algoritmo, procesamiento de datos, recuperación de informaci´on (es).Downloads
Abstract (en)
Due to the increasing amount of information available on the Internet, it is important for users to have a summary containing the most important ideas from the documents they find, in order to quickly identify which ones to read. This article addresses this issue through a modified algorithm for the automatic generation of single-document extractive summaries, aiming to produce summaries of a quality comparable to those generated by expert humans. This proposal is based on the shuffled frog-leaping metaheuristic algorithm (SFLA) and includes a global explicit tabu memory. Its goal is to optimize a weighted objective function with characteristics such as length (measured in words), position within the document, similarity to the document's title, cohesion (similarity between the sentences in the summary), and coverage (similarity between the sentences in the summary and the document). To this effect, an iterative research procedure was followed, consisting of four stages (observation, problem identification, development, and solution testing) over two iterative cycles. In the first cycle, the initialization and evolution schemes were analyzed and selected to modify the base algorithm. This, in addition to parameter tuning. In the second cycle, a tabu memory was selected for integration into the proposed algorithm, and the corresponding tuning was performed. To evaluate the quality of the summaries generated by our proposal, ROUGE metrics were used on the DUC datasets. The results are comparable to and surpass those of various methods in the state of th art. The proposed algorithm stands out for its simplicity of implementation and the reduced number of objective function evaluations, which implies lower computation times.
Abstract (es)
Debido a la creciente cantidad de información disponible en Internet, para un usuario es importante contar un resumen con las ideas más importantes delos documentos que encuentra, con el propósito de identificar rápidamente cuáles debe leer. En este artículo se aborda esta problemática mediante un algoritmo modificado para la generación automática de resúmenes extractivos de un solo documento, el cual busca obtener resúmenes de calidad similar a aquellos generados por humanos expertos. Esta propuesta está basada en el algoritmo metaheurístico de saltos de ranas mezcladas e incluye una memoria tabú explícita global. Su propósito es optimizar una función objetivo ponderada con características como longitud (medida en palabras), posición en el documento, similitud con el título del documento, cohesión (similitud entre las oraciones del resumen) y cobertura (similitud entre las oraciones del resumen y el documento). Para ello, se siguió un procedimiento de investigación iterativa compuesto por cuatro etapas (observación, identificación del problema, desarrollo y prueba de la solución) en dos ciclos iterativos. En el primer ciclo se realizó el análisis y selección de los esquemas de inicialización y de evolución, en aras de modificar el algoritmo base. Esto, además del afinamiento de parámetros. Por su parte, en el segundo ciclo se seleccionó una memoria tabú para su integración en el algoritmo propuesto, y se realizó el afinamiento correspondiente. Para evaluar la calidad de los resúmenes obtenidos con nuestra propuesta, se usaron las métricas ROUGE sobre los conjuntos de datos de la DUC. Los resultados se equiparan y superan a diversos métodos del estado del arte. El algoritmo propuesto se diferencia por su simplicidad de implementación y por el reducido número de evaluaciones de la función objetivo, lo que implica un menor tiempo computacional.
References
Alguliyev, R. M., Aliguliyev, R. M., Isazade, N. R., Abdi, A., Idris, N. (2019). COSUM: Text summarization based on clustering and optimization. Expert Systems, 36(1), 1-17. https://doi.org/10.1111/exsy.12340
Aliguliyev, R. M. (2009). A new sentence similarity measure and sentence based extractive technique for automatic text summarization. Expert Systems with Applications, 36(4), 7764-7772. https://doi.org/10.1016/j.eswa.2008.11.022
Bhattacharjee, K. K. K., Sarmah, S. P. P. (2014). Shuffled frog leaping algorithm and its application to 0/1 knapsack problem. Applied Soft Computing, 19, 252-263. https://doi.org/https://doi.org/10.1016/j.asoc.2014.02.010
Debnath, D., Das, R., Pakray, P. (2021). Extractive single document summarization using multi-objective modified cat swarm optimization approach: ESDS-MCSO. Neural Computing and Applications, 4, s00521-021-06337-4. https://doi.org/10.1007/s00521-021-06337-4
Debnath, D., Das, R., Pakray, P. (2023). Single document text summarization addressed with a cat swarm optimization approach. Applied Intelligence, 53(10), 12268-12287. https://doi.org/10.1007/s10489-022-04149-0
Dunlavy, D. M., O’Leary, D. P., Conroy, J. M., Schlesinger, J. D. (2007). QCS: A system for querying, clustering and summarizing documents. Information Processing and Management, 43(6), 1588-1605. https://doi.org/10.1016/j.ipm.2007.01.003
El-Kassas, W. S., Salama, C. R., Rafea, A. A., Mohamed, H. K. (2020). EdgeSumm: Graph-based framework for automatic text summarization. Information Processing & Management, 57(6), e102264. https://doi.org/10.1016/j.ipm.2020.102264
El-Kassas, W. S., Salama, C. R., Rafea, A. A., Mohamed, H. K. (2021). Automatic text summarization: A comprehensive survey. Expert Systems with Applications, 165, e113679. https://doi.org/10.1016/j.eswa.2020.113679
Erkan, G., Radev, D. R. (2004). LexRank: Graph-based lexical centrality as salience in text summarization. Journal of Artificial Intelligence Research, 22(4), 457-479. https://doi.org/10.1613/jair.1523
Gambhir, M., Gupta, V. (2017). Recent automatic text summarization techniques: A survey. Artificial Intelligence Review, 47(1), 1-66. https://doi.org/10.1007/s10462-016-9475-9
Janjanam, P., Reddy, C. H. P. (2019). Text summarization: An essential study [Conference paper]. 2nd International Conference on Computational Intelligence in Data Science. https://doi.org/10.1109/ICCIDS.2019.8862030
Lin, C. (2004). Rouge: A package for automatic evaluation of summaries. Proceedings of the Workshop on Text Summarization Branches out (WAS 2004), 1, 25-26.
Lin, C.-Y., Hovy, E. (1997). Identifying topics by position [Conference paper]. Fifth Conference on Applied Natural Language Processing, San Francisco, CA, USA.
Liu, C., Niu, P., Li, G., Ma, Y., Zhang, W., Chen, K. (2018). Enhanced shuffled frog-leaping algorithm for solving numerical function optimization problems. Journal of Intelligent Manufacturing, 29(5), 1133-1153. https://doi.org/10.1007/s10845-015-1164-z
Mendoza, M., Bonilla, S., Noguera, C., Cobos, C., León, E. (2014). Extractive single-document summarization based on genetic operators and guided local search. Expert Systems with Applications, 41(9), 4158-4169. https://doi.org/10.1016/j.eswa.2013.12.042
Mendoza, M., Cobos, C., León, E. (2015). Extractive single-document summarization based on global-best harmony search and a greedy local optimizer. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 9414, 52-66. https://doi.org/10.1007/978-3-319-27101-9_4
Pratt, K. (2009). Design patterns for research methods: Iterative field research. Association for the Advancement of Artificial Intelligence.
Saini, N., Saha, S., Jangra, A., Bhattacharyya, P. (2019). Extractive single document summarization using multiobjective optimization: Exploring self-organized differential evolution, grey wolf optimizer and water cycle algorithm. Knowledge-Based Systems, 164, 45-67. https://doi.org/10.1016/j.knosys.2018.10.021
Shen, D., Sun, J.-T., Li, H., Yang, Q., Chen, Z. (2007). Document summarization using conditional random fields [Conference paper]. 20th International Joint Conference on Artifical Intelligence.
Song, W., Cheon Choi, L., Cheol Park, S., Feng Ding, X. (2011). Fuzzy evolutionary optimization modeling and its applications to unsupervised categorization and extractive summarization. Expert Systems with Applications, 38(8), 9112-9121. https://doi.org/10.1016/j.eswa.2010.12.102
Svore, K., Vanderwende, L., Burges, C. (2007). Enhancing single-document summarization by combining RankNet and third-party sources [Conference paper]. Conference on Empirical Methods in Natural Language Processing (EMNLP-CoNLL).
Wan, X. (2010). Towards a unified approach to simultaneous single-document and multi-document summarizations [Conference paper]. 23rd International Conference on Computational Linguistics (pp. 1137-1145).
Wan, X., Yang, J., Xiao, J. (2007). CollabSum: Exploiting multiple document clustering for collaborative single document summarizations [Conference paper]. 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR’07. https://doi.org/10.1145/1277741.1277768
Yip-Herrera, J.-D., Mendoza-Becerra, M.-E., Rodríguez, F. (2023). Generación automática de resúmenes extractivos para un solo documento: un mapeo sistemático. Revista Facultad de Ingeniería, 32(63), e15232. https://doi.org/10.19053/01211129.v32.n63.2023.15232
How to Cite
APA
ACM
ACS
ABNT
Chicago
Harvard
IEEE
MLA
Turabian
Vancouver
Download Citation
License
Copyright (c) 2024 Juan-David Yip-Herrera, Martha-Eliana Mendoza-Becerra
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
When submitting their article to the Scientific Journal, the author(s) certifies that their manuscript has not been, nor will it be, presented or published in any other scientific journal.
Within the editorial policies established for the Scientific Journal, costs are not established at any stage of the editorial process, the submission of articles, the editing, publication and subsequent downloading of the contents is free of charge, since the journal is a non-profit academic publication. profit.
