A new evolutionary algorithm combining simulated annealing and genetic programming for relevance feedback in fuzzy information retrieval systems
Inhaltsverzeichnis
Referenz
O. Cordón, F. Moya, C. Zarco: A new evolutionary algorithm combining simulated annealing and genetic programming for relevance feedback in fuzzy information retrieval systems. Soft Computing, 6 (5) (2002), pp. 308–319
DOI
Abstract
Relevance feedback techniques have demonstrated to be a powerful means to improve the results obtained when a user submits a query to an information retrieval system as the world wide web search engines. These kinds of techniques modify the user original query taking into account the relevance judgements provided by him on the retrieved documents, making it more similar to those he judged as relevant. This way, the new generated query permits to get new relevant documents thus improving the retrieval process by increasing recall. However, although powerful relevance feedback techniques have been developed for the vector space information retrieval model and some of them have been translated to the classical Boolean model, there is a lack of these tools in more advanced and powerful information retrieval models such as the fuzzy one. In this contribution we introduce a relevance feedback process for extended Boolean (fuzzy) information retrieval systems based on a hybrid evolutionary algorithm combining simulated annealing and genetic programming components. The performance of the proposed technique will be compared with the only previous existing approach to perform this task, Kraft et al.’s method, showing how our proposal outperforms the latter in terms of accuracy and sometimes also in time consumption. Moreover, it will be showed how the adaptation of the retrieval threshold by the relevance feedback mechanism allows the system effectiveness to be increased.
Extended Abstract
Bibtex
@article{ author = {O. Cordón, F. Moya, C. Zarco}, title = {A new evolutionary algorithm combining simulated annealing and genetic programming for relevance feedback in fuzzy information retrieval systems}, journal = {Soft Computing}, volume = {6}, number = {5}, pages = {308–319}, year = {2002}, keywords={} doi={}, url={http://scimago1.ugr.es/publications/softc-02.pdf http://de.evo-art.org/index.php?title=A_new_evolutionary_algorithm_combining_simulated_annealing_and_genetic_programming_for_relevance_feedback_in_fuzzy_information_retrieval_systems}, }
Used References
1. Aarts EHL (1989) Simulated annealing and boltzman machines: a stochastic approach to combinatorial optimization and neural computing, Wiley
2. Ba¨ck T (1996) Evolutionary Algorithms in Theory and Practice, Oxford University Press, Oxford
3. Baker JE (1987) Reducing bias and inefficiency in the selection algorithm, Proc. Second International Conference on Genetic Algorithms (ICGA’87), Hillsdale, pp. 14–21
4. Bordogna G, Carrara P, Pasi G (1995) Fuzzy approaches to extend Boolean information retrieval. In: Bosc P, Kacprzyk J (eds), Fuzziness in DatabaseManagement Systems, pp. 231–274
5. Chen H (1998) A machine learning approach to inductive query by examples: an experiment using relevance feedback, ID3, genetic algorithms, and simulated annealing, J Amer Soc Information Sci 49(8): 693–705
6. Cross V (1994) Fuzzy information retrieval, J Intelligent Information Syst 3: 29–56
7. Cordo´n O, Moya F, Zarco C (1999) A brief study on the application of genetic algorithms to information retrieval (in spanish), Proc Fourth International Society for Knowledge Organization (ISKO) Conference (EOCONSID’99), Granada, Spain, pp. 179–186 8. Cordo´n O, Moya F, Zarco C (1999) Learning queries for a fuzzy information retrieval system by means of GA-P techniques, Proc EUSFLAT-ESTYLF Joint Conference, Palma de Mallorca, Spain, pp. 335–338 9. Cordo´n O, Moya F, Zarco C (2000) A GA-P algorithm to automatically formulate extended Boolean queries for a fuzzy information retrieval system, Mathware & Soft Computing 7(2–3) 309–322 10. Dillon M, Desper J (1980) Automatic relevance feedback in Boolean retrieval systems, J Documentation 36: 197–208 11. Dillon M, Ulmschneider J, Desper J (1983) A prevalence formula for automatic relevance feedback in Boolean systems, Information Processing and Management 19(1): 27–36 12. Fan W, Gordon M, Pathak P (2000) Personalization of search engine services for effective retrieval and knowledge management, Proc 2000 International Conference on Information Systems (ICIS) 13. Fan W, Gordon M, Pathak P, Radev D (2001) Automatic term weighting for effective retrieval: a genetic programming approach, submitted to SIGIR 14. Fogel DB (1991) System identification trough simulated evolution. A Machine Learning Approach, Ginn Press, USA 15. Gordon M (1988) Probabilistic and genetic algorithms for document retrieval, Commun ACM 31(10): 1208–1218
16. Gordon M (1991) User-based document clustering by redescribing subject descriptions with a genetic algorithm, J Amer Soc Information Sci 42(5): 311–322
17. Gordon M, Pathak P (1999) Finding information on the world wide web: the retrieval effectiveness of search engines, Information Processing and Management 35(2): 141–180
18. Herrera-Viedma E (2001) Modelling the retrieval process of an information retrieval system using an ordinal fuzzy linguistic approach, J Amer Soc Information Sci 52(6): 460–475
19. Howard L, D’Angelo D (1995) The GA-P: a genetic algorithm and genetic programming hybrid, IEEE Expert 11–15
20. Ide E (1971) New experiments in relevance feedback. In: Salton G (ed.), The SMART Retrieval System, Prentice Hall, pp. 337–354 21. Koza J (1992) Genetic programming. On the Programming of Computers by Means of Natural Selection, The MIT Press
22. Kraft DH, Petry FE, Buckles BP, Sadasivan T (1997) Genetic algorithms for query optimization in information retrieval: relevance feedback. In: Sanchez E, Shibata T, Zadeh LA (eds), Genetic Algorithms and Fuzzy Logic Systems, World Scientific, 155–173.
23. Lo´pez-Pujalte C, Guerrero VP, Moya F (2002) A test of genetic algorithms in relevance feedback, Information Processing & Management. (to appear).
24. Martı´n-Bautista MJ, Vila MA, Larsen HL (1999) A fuzzy genetic algorithm approach to an adaptive information retrieval agent, J Amer Soc Information Sci 50(9): 760–771
25. Michalewicz Z (1996) Genetic Algorithms + Data Structures = Evolution Programs, Springer-Verlag
26. Mu¨hlenbein H, Schlierkamp-Voosen D (1993) Predictive models for the breeder genetic algorithm: I. Continuous parameter optimization, Evolut Comput 1(1): 25–49
27. Raghavan VV, Agarwal B (1987) Optimal determination of user-oriented clusters: an application for the reproductive plan, Proc Second International Conference on Genetic Algorithms and Their Applications (ICGA’87), Hillsdale, NJ, USA pp. 241–246
28. Robertson AM, Willet P (1994) Generation of equifrequent groups of words using a genetic algorithm, J Documentation 50(3): 213–232
29. Robertson AM, Willet P (1996) An upperbound to the performance of ranked-output searching: optimal weighting of query terms using a genetic algorithm, J Documentation 52(4): 405–420
30. Salton G, McGill MJ (1989) Introduction to Modern Information Retrieval, McGraw-Hill, New York
31. Sanchez E (1989) Importance in knowledge systems, Information Syst 14(6): 455–464
32. Sanchez E, Miyano H, Brachet JP (1995) Optimization of fuzzy queries with genetic algorithms. Application to a data base of patents in biomechanical engineering, Proc Sixth IFSA World Congress, Sao Paulo, Brazil, vol. II, pp. 293–296
33. Sa´nchez L, Couso I, Corrales JA (2001) Combining GP operators with SA search to evolve fuzzy rule based classifiers, Information Sci 136(1–4): 175–191
34. Schwefel H-P (1995) Evolution and optimum seeking. Sixth- Generation Computer Technology Series, John Wiley and Sons
35. Smith MP, Smith M (1997) The use of genetic programming to build Boolean queries for text retrieval through relevance feedback, J Information Sci 23(6): 423–431
36. van Rijsbergen CJ (1979) Information Retrieval (2nd edition), Butterworth, London
37. Vrajitoru D (1998) Crossover improvement for the genetic algorithm in information retrieval, Information Processing and Management 34(4): 405–415
38. Yen JJ, Korfhage RR (1994) Query modification using genetic algorithms in vector spacemodels, Int J Expert Syst 7(2): 165–191 39. Zadeh LA (1965) Fuzzy sets, Information and Control 8: 338– 353
Links
Full Text
http://scimago1.ugr.es/publications/softc-02.pdf