Knowledge base: Warsaw University of Technology

Settings and your account

Back

Discovery of graph patterns, association rules and theirs concise representations

Marcin Wyrzykowski

Abstract

Discovering patterns in the form of graphs frequently occurring in the data is a very important data mining task and have many applications, including chemistry, bioinformatics, software engineering, Web, etc. In this work, the efficient frequent graphs discovery algorithm gSpan and frequent closed graphs discovery algorithm CloseGraph were implemented. In addition, an algorithm for restoring all frequent graphs based on closed frequent graphs was designed and implemented. The resulting frequent graphs and representing them frequent closed graphs were used for discovery of graph association rules and representations of such rules. Algorithms for discovering of graph association rules and their concise representations MNR and RR were designed and implemented. All algorithms implemented in the diploma work were verified experimentally.
Record ID
WUT307796
Diploma type
Master of Science
Author
Marcin Wyrzykowski (FEIT/ICS) Marcin Wyrzykowski,, The Institute of Computer Science (FEIT/ICS)Faculty of Electronics and Information Technology (FEIT)
Title in Polish
Odkrywanie grafowych wzorców, reguł asocjacyjnych i ich reprezentacji
Supervisor
Marzena Kryszkiewicz (FEIT/ICS) Marzena Kryszkiewicz,, The Institute of Computer Science (FEIT/ICS)Faculty of Electronics and Information Technology (FEIT)
Certifying unit
Faculty of Electronics and Information Technology (FEIT)
Affiliation unit
The Institute of Computer Science (FEIT/ICS)
Language
(pl) Polish
Status
Finished
Issue date (year)
2012
Internal identifier
ENII-PM.001663
Keywords in Polish
częste grafy, zamknięte częste grafy, reguły asocjacyjne, zwięzłe reprezentacje reguł asocjacyjnych
Keywords in English
frequent graphs, closed frequent graphs, association rules, concise representations of association rules
Abstract in Polish
Odkrywanie wzorców grafowych w postaci grafów często występujących w danych należy do bardzo istotnych zadań eksploracji danych i znajduje wiele zastosowań, m.in. w chemii, bioinformatyce, inżynierii oprogramowania, sieci WWW itd. W ramach niniejszej pracy dyplomowej zaimplementowano skuteczny algorytm odkrywania grafów częstych – gSpan i algorytm odkrywania zamkniętych grafów częstych – CloseGraph. Zaprojektowano i zaimplementowano także algorytm odtwarzania zbioru grafów częstych na podstawie zbioru częstych grafów zamkniętych. Otrzymane grafy częste i reprezentujące je zamknięte grafy częste wykorzystano w celu odkrywania grafowych reguł asocjacyjnych i reprezentacji takich reguł w grafach. Zaprojektowano i zaimplementowano algorytmy odkrywania grafowych reguł asocjacyjnych oraz ich zwięzłych reprezentacji MNR i RR. Wszystkie zaimplementowane w ramach pracy algorytmy zostały eksperymentalnie zweryfikowane.
File
Request a WCAG compliant version

Uniform Resource Identifier
https://repo.pw.edu.pl/info/master/WUT307796/
URN
urn:pw-repo:WUT307796

Confirmation
Are you sure?
Report incorrect data on this page