Förmågan att identifiera intressanta och repetitiva understrukturer är en viktig komponent för att upptäcka kunskap i strukturdata. Vi beskriver en ny version av vårt system för subdue substructure discovery baserat på principen om minsta beskrivningslängd. Subdue-systemet upptäcker understrukturer som komprimerar de ursprungliga uppgifterna och representerar strukturella begrepp i datan. Genom att ersätta tidigare upptäckta understrukturer i data, flera passager av Subdue producera en hierarkisk beskrivning av de strukturella regulariteterna i data. Subdue använder en beräkningsbart bunden inexakt graf matcha att identi es liknande, men inte identiska, fall av en understruktur och NDs ett ungefärligt mått på närhet av två understrukturer vid beräkningsbegränsningar. Utöver principen om minsta beskrivningslängd kan annan bakgrundskunskap användas av Subdue för att vägleda sökandet mot lämpligare understrukturer. Experiment i en mängd olika domäner visar Subdues förmåga att ND substructures som kan komprimera de ursprungliga data och att upptäcka strukturella begrepp som är viktiga för domänen.
BIDRAG REF är en gren-och-bundet teknik som minrerar subgrafer som kan användas för att komprimera den ursprungliga grafen.
Substructure Discovery Using Minimum Description Length and Background Knowledge
{'venue': 'Journal of Artificial Intelligence Research, Vol 1, (1994), 231-255', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}