Program badawczy

Wybrane zagadnienia uczenia się systemów z wysokowymiarowych źródeł informacjiobarczonych niepełnością

Learning In Giant Sets of InformationAttrubutes (LIGIA - Project)

Docent dr hab. inż. Mieczyslaw Alojzy Kłopotek, IPI PAN, Warszawa

Zarys problemu

W praktyce drążenia danych (data mining) częstym problemem jest zbyt wysoka wymiarowość danych.Oznacza ona, że:

• mamy do czynienia ze zbyt dużą ilością danych,
• mamy do czynienia ze zbyt dużą ilością zmiennych,
• i/lub liczba zmiennych jest zbyt duża w porównaniu z ilością danych,

• zbyt duży czas przetwarzania,
• zbyt duży stopień dopasowania uzyskanego modelu do danych
• duża szansa na wejście do modelu zmiennych niezwiązanych z modelowanym zagadnienem.
• duża szansa na występowanie braków danych oraz szumu.

• proste ale za to szybkie algorytmy uczące się,
• sprawne techniki redukcji wymiarów
  • poprzez selekcję cech
  • poprzez transformację przestrzeni cech
  • poprzez próbkowanie danych
• techniki uzupełniania braków danych
• algorytmy uczące się odporne na szum w danych

Metodologie, które wydają się być obiecujące przynajmniej do rozwiązania części tych zagadnieńto metody oparte na drzewiastych strukturach przestrzeni informacyjnej: drzewa decyzyjne oraz sieci bayesowskie o strukturze drzewiastej.

Stąd w ramach niniejszego projektu nacisk będzie położony na eksplorację oferowanych przez nie możliwości oraz rozważenie sposobów osiągnięcia efektów synergicznych.

Zainteresowanych zapraszam do współpracyw następujących tematach:

• Wielkie binarne drzewiaste sieci bayesowskie(cel: sieć o 1,000,000 węzłów)
• Hierarchiczne sieci bayesowskie oparte o szkielet drzewiastej sieci bayesowskiej
• Selekcja cech za pomocą inteligentnych algorytmów ewolucyjnych odtwarzających rozkład pradopodobieństwa obiecujących osobników za pomocą sieci bayesowskiej
• Odtwarzanie łącznego rozkładu prawdopodobieństwa cech ciągłych i dyskretnych za pomocą sieci bayesowskich z rozkładem warunkowym modelowanym probabilistyczną siecią neuronową.

Problem outline

In the data mining practice we often encounter the problem of a too high dimensionality in data. This means that either

• we have to deal with a too large number of variables, or
• the number of variables is too high compared to the number of data units

As a consequence we are faced with

• a too long processing time,
• a too high degree of fitting the model to data
• a high chance of incorporating into the model variables not related to the modelled problem .
• a high chance of missing data and noise problems

Therefore there is a growing importance of

• simple but speedy learning algorithms
• efficient techniques of reduction of dimensionality
  • via feature selection
  • via feature space transformation
  • via data sampling
• missing data handling techniques
• noise-resistent learning algorithms

Methodologies, that seem to promise to solvbe at least part of these problems, are methods based on tree-structured representation of the information space: decision trees and tree-structured Bayesian networks.

Hence this project stresses the exploration of advantages of both technologies and on search of synergic effects between them.

Those intereseted are invited to cooperate on investigations of:

• giant binary tree-like Bayesian networks (goal: a network with 1,000,000 nodes)
• hierarchical Bayesian networks based on tree-like Bayesian network skeleton
• feature selection in intelligent evolutionary algorithms with mutation/crossover based on Bayesian networks
• joint probability distribution for continuous and discrete features modelled by Bayewsian networks with neural local probability distribution engine.

Experiments demonstrated feasibility of tree-like Bayesian network construction from data for dozens of thousands of variables. Currently we investigate suitability of the obtained networks for classification of textual data (e.g. news-groups, sets of HTML documents), and also we target at 1,000,000 node networks (which would then cover vocabulary of most natural languages). Construction of networks of that size does not appear to be a simple extrapolation of the EdgeTreeConstructor algorithm and we are currently considering several possible promising extensions.

Literatura (publikacje własne związane z projektem)/ Project related publications

1. [MKP:00d] M.A.Klopotek, S.T.Wierzchon: Discovery of Bayesian Networks from Data with Maintenance of Partially Oriented Graphs. In: M.Kl`opotek, M.Michalewicz, S.Wierzchon` eds: Intelligent Infoprmation Systems. . Advances in Soft Computing Series of Physica-Verlag/Springer Verlag, Heidelberg/New York 2000, pp. 277- 288.
2. [MKP:00g] M. Klopotek, S. Wierzchon, A. Jodlowski, K. Skowronski,M. Michalewicz, M. Bednarczyk, W.Pawlowski: An Application of Dynamic AI Metods in the Integration of Computer Credit Scoring Systems. IN H.Larsen, J.Kasprzyk, S.Zadrozny, T. Andreasen, H. Christiansen eds.: Flexible Query Answering Systems. Advances in Soft Computing Series. Physica/Springer Verlag. Heidelberg New York 2000. pp. 560-569
3. [MKP:01] M.A.KłopotekA New Space-Saving Bayesian Tree Construction Method for High Dimensional SpacesICS PAS Reports Nr 925 Warszawa, May 2001
   - draft available as winzipped Postscriptfile (80 kb)
4. [MKP:01b] M.A.KłopotekA New Bayesian Tree Construction Method with Decreased Time ComplexityICS PAS Reports Nr 927 Warszawa, May 2001
5. [MKP:01c] M.A.Klopotek :"Taxonomy Building: Cases or Attributes ?"In: M.A.Klopotek, S.T.Wierzchon, M.Michalewicz(eds):Intelligent Information Systems 2001.Advances in Soft Computing. Physica/Springer Verlag, Heidelberg New York 2001.ISBN-3-7908-1407-5.pp. 97-110
6. [MKP:01d] M.A.Klopotek, S.T.Wierzcho\'{n}, Maciej Michalewicz, Marek Bednarczyk, Wiesław Pawłowski, Andrzej Wąsowski"Bayesian Network Mining System".In: M.A.Klopotek, S.T.Wierzchon, M.Michalewicz (eds):Intelligent Information Systems 2001.Advances in Soft Computing. Physica/Springer Verlag, Heidelberg New York 2001.ISBN-3-7908-1407-5.pp. 179-193
7. [MKP:01f] M.A. Kłopotek, M. Paliwoda: System ekspercki bazujący na automatycznej konstrukcji drzew decyzyjnych z danych. W [MKP:01proc3], pp. 197-209
8. [MKP:Paliwoda:01g] M. Paliwoda, M.A. Kłopotek: Metody dyskretyzacji w odkrywaniu wiedzy w bazach danych. W [MKP:01proc3] pp. 115-127
9. [MKP:01i] M.A. Kłopotek, J. Rau: Badania porównawcze metod uczenia się sieci bayesowskich z danych. W tomie referatów z Ogólnopolskiego Konwersatorium AI'15 „Sztuczna Inteligencja 2001”, Siedlce, 28.11.2001.
10. [MKP:01:mono] M.A.Klopotek:Inteligentne wyszukiwarki internetowe.Akademicka Oficyna Wydawnicza Exit, Warszawa 2001, 332 strony,ISBN 83-87674-31-1
11. [MKA:02c] M.A.Klopotek:A New Space-Saving Bayesian Tree Construction Method for High Dimensional DataDemonstratio Mathematica, Vol. 35, No. 3 (2002)
12. [MKP:02d] M.A.Klopotek: A New Bayesian Tree Learning Method with Reduced Time and Space Complexity.Fundamenta Informaticae, 49(no 4)2002, IOS Press, pp. 349-367.
13. [MKP:02f] M.A.Klopotek: Minig Bayesian Networks Structure for Large Sets of Variables.inM.S.Hacid, Z.W.Ras, D.A. Zighed, Y. Kodratoff (eds): Foundations of Intelligent Systems Lecture Notes in Artificial Intelligence 2366,Springer-Verlag, pp.114-122
14. [MKP:02h] M.A.Klopotek: Space Saving Approach to Fitting Tree Distributions to High-Dimensional Sparse Data. In [MKP:02proc1], pp.13-18
15. [MKP:02k] M.A.Klopotek, T. Grzeszczak, P. Lorens: Metody prezentacji dokumentów w postaci mapyIn [MKP:02proc1],pp. 143-160
16. [MKP:02l] M.A.Klopotek, D. Czerski: Dynamiczne mapy dokumentów.In [MKP:02proc1],pp.161-172
17. [MAT:02b]Lizely Abitia Nino de Rivera , Guillermo Bali Chávez, Joselín Espitia Espitia, Andrzej Matuszewski, “Analysis of the relations between groups at management level”, First Interchange of education experiences of the South Zone Rectorate.Electronic Memories in CD, ITESM Campus Mexico City, December 2001,Mexico.
18. [MAT:02c] Sobolewska M., Matuszewski A., „Test czytania glosnego”, Centrum Metodyczne Pomocy Psychologiczno-Pedagogicznej, 72 strony, 2002.
19. [MAT:02d]Katarzyna Juda-Rezler, A. Matuszewski, “Critical levels of sulphur dioxide in Poland and their exeedances” Referat wygloszony na kongresie Inzynierii Srodowiska (Lublin IX, 2002) . Ukaze sie w 2003 w materialach konferencyjnych w wydawnictwie Klouver
20. [MAT:02a] A. Matuszewski, „Double clustering: A data mining methodology for discovery of causality”, in: M. A. Klopotek, S. T. Wierzchon, M. Michalewicz (ed.) “Intelligent Information Systems 2002”, Physica-Verlag, 2002, ss. 227-236.
21. {TRO:02a] Trojanowski, K., ``Analiza cech iteracyjnego algorytmu optymalizacyjnego zastosowanego do optymalizacji parametrów dynamicznego systemu uczacego sie", BOS 2002: VII Konferencja Polskiego Towarzystwa Badan Operacyjnych i Systemowych - Badania Operacyjne i Systemowe Wobec Wyzwan XXI Wieku, Warszawa, 26-28 wrzesnia 2002, Akademicka Oficyna Wydawnicza EXIT, Warszawa 2002, str. IV-27 - IV-34.
22. [TRO:02b] Trojanowski, K., Jodlowski, A., Skowronski K., ``Storing Data in KDD Systems /from Inlen 3.0 to InlenStar. Evolution of Database/", IIS 2002: The Eleventh International Symposium on Intelligent Information Systems, June 3-6, 2002, Sopot, Poland.
23. [MKP:03] M.A. Klopotek: On the Distance Hypothesis in Tree-like Bayesian Networks. ICS PAS Report 952, Warszawa, January 2003.
24. [MKP:03b] M.A.Klopotek: Intelligent information retrieval on the Web. in: Szczepaniak, Piotr S.; Segovia, Javier; Kacprzyk, Janusz; Zadeh, Lotfi A. (Eds.): (2003) Intelligent Exploration of the Web Springer-Verlag ISBN 3-7908-1529-2, pp. 57-73. M.A.Kłopotek, S.T.Wierzchoń, K.Trojanowski(eds): Intelligent Information Processing and Web Mining. Advances in Soft Computing. Springer Verlag, Heidelberg New York 2003. ISBN-3-540-00843-8. M.A. Kłopotek, S.T.Wierzchon: Bayesian Nets for Recommender Systems. In , pp. 87-96 Guillermo Bali Ch, Andrzej Matuszewski, Mieczyslaw Klopotek: Dependence of two multiresponse variables – definition of the null hypothesis is crucial In 3, pp. 251-260 M.A. Kłopotek: Reasoning methods in general and structured Bayesian networks. Zeszyty Naukowe AP - Studia Informatica. Technologie i Systemy informacyjne, Nr1, 2003, pp. 1-26 M.A. Kłopotek, Marcin Woch: Very Large Bayesian Networks in Text Classification. In: Sloot, P. M.A.; Abramson, D.; Bogdanov, A. V.; Dongarra, J. J.; Zomaya, A. Y.; Gorbachev, Y. E. (Eds.): (2003) Computational Science - ICCS 2003 · International Conference, Melbourne, Australia and St. Petersburg, Russia, June 2-4, 2003. Proceedings, ISBN 3-540-40194-6, LNCS 2657, LNCS 2658, LNCS 2659, and LNCS 2660 Springer Verlag 2003, pp. 397-406, vol 1. M.A. Kłopotek, A. Sosnowski: Mixnet a wnioskowanie w sieciach bayesowskich swobodnie dyskretno-ciaglych. Z. Bubnicki, A. Grzech eds: Proc. V KRAJOWA KONFERENCJA NAUKOWA Inżynieria Wiedzy i Systemy Ekspertowe, Wrocław 11-13.6.2003 Oficyna Wydawnicza Politechniki Wrocławskiej, Wrocław 2003 Tom 1, 30-37

Prezentacje ( własne związane z projektem)/ Project related presentations

• Space Saving Approach to Fitting Tree Distributions to High-Dimensional Sparse Data5th National AI Conference, Siedlce, September 2002
• Dynamiczne mapy dokumentów.(Dynamic maps of documents, in Polish)5th National AI Conference, Siedlce, September 2002
• Metody prezentacji dokumentów w postaci mapy(Methods of presentation of documents as maps, in Polish)
• 2002 reportInstitute of Computer Sciences, PAS, December 2002
• "Metody i algorytmy sieci bayesowskich w systemach rekomendujacych" ("Bayesian networks in recommender systems" - in Polish) presentationat the National Conference on Decision Support Systems in Zakopane, December 3-5, 2002
• Impact of Structuring on Bayesian Network Learning and Reasoning presentationat the First Warsaw International Seminar on Soft Computing, September 8th, 2003
• Bayesian Networks. A Seminar held at the Fraunhofer Institute for Autonomous Intelligent Systems (AIS) Schloss Birlinghoven, Sankt Augustin, Germany, January 8th, 2004 presentation

This page is maintained by Mieczyslaw A. Klopotek .
Please e-mail any comments on this page to
<klopotek@ipipan.waw.pl>
Created: 8th February, 2001

Back

• 2002: Wybrane zagadnienia uczenia sie z wysokowymiarowych danych obarczonych niepewnoscia (participants: A.Matuszewski, K.Trojanowski)
• 2003: Wybrane zagadnienia eksploracji wysokowymiarowych nieprecyzynych i niepelnych danych (participants: A.Matuszewski)