Acta Univ. Agric. Silvic. Mendelianae Brun. 2009, 57(6), 201-208 | DOI: 10.11118/actaun200957060201

POUŽITÍ GENETICKÝCH ALGORITMŮ PRO ANALÝZU NÁVŠTĚVNOSTI WWW PORTÁLU

Ondřej Popelka, Jiří Šťastný
Ústav informatiky, Mendelova zemědělská a lesnická univerzita v Brně, Zemědělská 1, 613 00 Brno, Česká republika

Článek popisuje novou metodu navrženou pro pokročilou analýzu návštěv webového portálu. Jedná se o část procesu získávání informací a znalostí z dat o použití webové prezentace. Tyto informace jsou nezbytné k lepšímu poznání potřeb a požadavků návštěvníka, všeobecně tedy k poznání zákazníka. S využitím těchto informací může organizace optimalizovat svoje webové prezentace a nabídnout tak koncovým uživatelům větší pohodlí a snadnější přístup k informacím. Navrhovaná metoda využívá gramatickou evoluci, což je výpočetní metoda založená na genetickém algoritmu.
Popsaná úloha je řešitelná pomocí statistické analýzy - konkrétně metodami založenými na sekvenční analýze. Cílem této práce je popsat alternativní metodu pro identifikaci vzorů chování.
Tato práce používá reprezentaci s využitím procedurálního programovacího jazyka, která je vhodná pro další použití jako součást obslužné aplikace webového portálu. To je významná motivace pro vývoj alternativní metody a použití právě gramatické evoluce. Výhoda použití gramatické evoluce je v tom, že vyhovořené řešení již není na výpočetním systému nijak závislé.
Gramatická evoluce je genetický algoritmus rozšířený o překládací vrstvu, vloženou mezi chromozom jedince a skutečné řešení úlohy. Tato vrstva je tvořena překladačem bezkontextové gramatiky. Hlavní výhodou tohoto rozšíření je schopnost generovat řešení v dále použitelném formátu v libovolném formálním jazyce.
Algoritmus používá tzv. vektorové fitness, které umožňuje implementaci i velmi složitých podmínek hodnocení řešení. Každá složka vektoru hodnoty kriteriální funkce popisuje jinou kvalitativní složku řešení. Tyto vektory jsou pak porovnávány s využitím definovaných pravidel.
Vstupní data do systému jsou záznamy o jednotlivých HTTP požadavcích na webový server. V těchto záznamech není jednoznačně identifikován konkrétní návštěvník, pro identifikaci je tedy použita kombinace IP adresy a identifikace webového prohlížeče. Jako testovací zdrojová data byly použity záznamy o přístupech na webový server známého IT časopisu. Surová data představují záznamy za jeden konkrétní náhodně vybraný pracovní den. Implementace algoritmu a testování na těchto datech vedlo k získaní mnoha poznatků. Zejména je nutné upravit implementaci tak, aby se zabránilo generování triviálních řešení. Dále bude zřejmě vhodnější použít alternativní postup, kdy je genetickým v rámci jednoho řešení generována pouze jedna podmínka a následně tyto podmínky seskupit až dodatečně.

genetické algoritmy, dolování dat, vzory chování, webový portál

WWW portal usage analysis using genetic algorithms

The article proposes a new method suitable for advanced analysis of web portal visits. This is part of retrieving information and knowledge from web usage data (web usage mining). Such information is necessary in order to gain better insight into visitor's needs and generally consumer behaviour. By leveraging this information a company can optimize the organization of its internet presentations and offer a better end-user experience. The proposed approach is using Grammatical evolution which is computational method based on genetic algorithms. Grammatical evolution is using a context-free grammar in order to generate the solution in arbitrary reusable form. This allows us to describe visitors' behaviour in different manners depending on desired further processing. In this article we use description with a procedural programming language. Web server access log files are used as source data.
The extraction of behaviour patterns can currently be solved using statistical analysis - specifically sequential analysis based methods. Our objective is to develop an alternative algorithm.
The article further describes the basic algorithms of two-level grammatical evolution; this involves basic Grammatical Evolution and Differential Evolution, which forms the second phase of the computation. Grammatical evolution is used to generate the basic structure of the solution - in form of a part of application code. Differential evolution is used to find optimal parameters for this solution - the specific pages visited by a random visitor. The grammar used to conduct experiments is described along with explanations of the links to the actual implementation of the algorithm. Furthermore the fitness function is described and reasons which yield to its' current shape. Finally the process of analyzing and filtering the raw input data is described as it is vital part in obtaining reasonable results.

Keywords: genetic algorithms, data mining, behaviour patterns, www portal
Grants and funding:

Tento článek vznikl v rámci řešení projektu 116/2102/IG190651 - Webové rozhraní pro aplikace genetického algoritmu a výzkumného záměru - MSM 6215648904/03.

Received: July 8, 2009; Published: October 7, 2014  Show citation

ACS AIP APA ASA Harvard Chicago IEEE ISO690 MLA NLM Turabian Vancouver
Popelka, O., & Šťastný, J. (2009). WWW portal usage analysis using genetic algorithms. Acta Universitatis Agriculturae et Silviculturae Mendelianae Brunensis, 57(6), 201-208. doi: 10.11118/actaun200957060201
Share...
Download citation
  • BibTeX (.bib)
  • Bookends (.ris)
  • EasyBib (.ris)
  • EndNote (.enw)
  • EndNote 8 (.xml)
  • ISI WoS (.isi)
  • Medlars (.medlars)
  • Mendeley (.ris)
  • MODS (.xml)
  • Papers (.ris)
  • RefWorks (.txt)
  • RefManager (.ris)
  • RIS (.ris)
  • MS Word (.xml)
  • Zotero (.ris)
    • Open full article

    References

    1. Dempsey, I., O'Neill, M., Brabazon, A., 2007: Constant creation in grammatical evolution, Int. J. Innovative Computing and Applications,Vol. 1, No. 1, pp. 23-38. DOI: 10.1504/IJICA.2007.013399 Go to original source...
    2. Goldberg, D. E., 2002: The Design of Innovation: Lessons from and for Competent Genetic Algorithms. Boston: Kluwer Academic Publishers. 272 p. ISBN 1-4020-7098-5.
    3. Iwata, T., Saito, K., Yamada, T., 2007: Modeling User Behavior in Recommender Systems based on Maximum Entropy. In proceedings of the Sixteenth International World Wide Web Conference (WWW2007), Banff, Alberta, Canada. pp. 1281-1282, ACM Press, ISBN:978-1-59593-654-7. Go to original source...
    4. Mitchell, M., 1999: An Introduction to Genetic Algorithms. MIT Press, Cambridge MA. 162 p. ISBN 0-262-63185-7.
    5. Munk, M., Balogh, Z., 2009: Possibilities of web optimization based on discovered user patterns. In: Žufan, P. Firma a konkurenční prostředí 2009 - 5. část. Brno: MSD, s. r. o., s. 71-78. ISBN 978-80-7392-088-3.
    6. O'Neill, M., Dempsey, I., Brabazon, A., Ryan, C., 2003: Analysis of a Digit Concatenation Approach to Constant Creation In proceedings of the European Conference on Genetic Programming, (EuroGP), Essex, UK. p. 173-182. ISBN 3-540-00971-X. Go to original source...
    7. O'Neill, M., Ryan, C., 2003: Grammatical Evolution: Evolutionary Automatic Programming in an Arbitrary Language, Kluwer Academic publishers. 160 p, ISBN 1-4020-7444-1.
    8. Ošmera, P., Popelka, O., Panáček, 2005: T. Grammatical Evolution with backward processing. In proceedings of 12th Zittau East-West Fuzzy Colloquium. Zittau. p. 235-244. ISBN 3-9808089-6-3.
    9. Ošmera, P., Popelka, O., Pivoňka, P., 2008: Two Level Parallel Grammatical Evolution. In: 2008 IEEE World Congress on Computational Intelligence. 6. vyd. Hong Kong: IEEE Press, ISBN 978-1-4244-1823-7. Go to original source...
    10. Popelka, O., Ošmera P., 2008: Parallel Grammatical Evolution for Circuit Optimization In proceedings of The 8th International Conference on Evolvable Systems: From Biology to Hardware (ICES 2008) September 21-24. Prague, Czech Republic.
    11. Popelka, O., Šťastný, J., 2007: Generation of mathematic models for enviromental data analysis. Management si Inginerie Economica. sv. 6, č. 2A, s. 61-66. ISSN 1583-624X.
    12. Price, K., 1996: Differential evolution: a fast and simple numerical optimizer, In proceedings of 1996 Biennial Conference of the North American Fuzzy Information Processing Society, NAFIPS, pp. 524-527, IEEE Press, New York, NY, 1996. ISBN: 0-7803-3225-3. Go to original source...
    13. Price, K. V., Storn, R. M., Lampinen, J. A., 2005: Differential evolution - a practical approach to Global Optimization. NCS Springer. 543 p., ISBN 3-540-20950-6.

    This is an open access article distributed under the terms of the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License (CC BY NC ND 4.0), which permits non-comercial use, distribution, and reproduction in any medium, provided the original publication is properly cited. No use, distribution or reproduction is permitted which does not comply with these terms.


    Return to the content