Pattern Mining Gemakkelijk Gemaakt

Datum: 12 september 2014

Locatie: UAntwerpen - Stadscampus - Promotiezaal van de Grauwzusters - Lange Sint-Annastraat 7 - 2000 Antwerpen

Tijdstip: 16 uur

Organisatie / co-organisatie: Faculteit Wetenschappen - Departement Wiskunde-Informatica

Promovendus: Sandy Moens

Promotor: Prof. dr. Bart Goethals

Korte beschrijving: Doctoraatsverdediging Sandy Moens - Faculteit Wetenschappen, Departement Wiskunde-Informatica


Abstract: Als gevolg van de vele recente technologische ontwikkelingen wordt het steeds goedkoper en makkelijker om grote hoeveelheden data te genereren en op te slaan. Deze data kan gebruikt worden om nieuwe, op data beruste kennis te vergaren die gebruikt kan worden voor allerhande doeleinden. Enkele voorbeelden: stel dat we beschikken over gegevens van producten die samen gekocht worden in een supermarkten, dan kunnen we seizoensgebonden producten vinden die vaak samen gekocht worden. Op deze manier kan koppelverkoop gestimuleerd worden bij de klanten. Een concrete patroon kan dan zijn dat mensen tijdens het wildseizoen vaak fazant, spruitjes en savooikool aankopen om deze in één gerecht te verwerken. Als ander voorbeeld, stel dat we beschikken over trajectgegevens alsook doorkomstgegevens van alle treinen op het spoorwegennetwerk, dan kunnen we vinden wat de oorzaak is van de grootste vertragingen. Deze informatie kan gebruikt worden om de verschillende trajecten te optimaliseren en vertragingen in de toekomst te vermijden.

Bestaande technieken voor het vergaren van dit soort van kennis in de vorm van patronen, doen meestal beroep op objectieve kwaliteitscriteria, bv. hoe vaker een patroon voorkomt in de data, hoe beter. Zulke informatie is helaas voor praktische doeleinden net minder interessant, omdat deze patronen mogelijk al goed gekend zijn. Daarbovenop komt dat door bestaande technieken meestal veel te veel patronen gevonden worden die gelijkaardige informatie dragen of zelfs niet interessant zijn. Dit bemoeilijkt enkel de analyse van de data en de zoektocht naar écht interessante info.
In het eerste deel van dit onderzoek nemen wij een vernieuwde aanpak om subjectieve kennis te vergaren voor specifieke personen. Dit doen we door een stevige koppeling tussen een gebruiker en pure rekenkracht tot stand te brengen, aan de hand van een interactieve tool voor data analyse. Deze tool heet MIME of Making Interactive Mining Easy. Met behulp van MIME, kan een gebruiker de data en haar patronen gaan exploreren, door zelf patronen samen te stellen, te verbeteren en on-the-fly te analyseren. Zodoende willen we het mogelijk maken om snel interessante patronen te vinden voor specifieke gebruikers.

Naast de mogelijkheid om zelf patronen te creëren is het ook interessant om geautomatiseerde algoritmes een beperkte verzameling van potentieel interessante patronen te laten genereren. Deze kunnen dan door een expert onderzocht worden in MIME, om de echte waarde te achterhalen. Echter, huidige pattern mining technieken zijn niet geschikt om in een interactief process als MIME ingebouwd te worden. Dit komt omdat ze vaak lange looptijden vereisen en veel te veel patronen genereren. Bijgevolg bestaat het tweede deel van het onderzoek uit de ontwikkeling van algoritmes die kleine collecties van verschillende types patronen kunnen genereren in zeer korte tijdbestekken – hooguit enkele seconden. De ontwikkelde methodes maken hiervoor intensief gebruik van bemonsteringsmethodes (ook wel bekend als sampling). Zulke methodes zijn waardevol in de setting van pattern mining omdat er net enorm veel redundantie in de patronen schuil gaat. Daardoor zijn benaderende resultaten gebaseerd op bemonstering, vaak goed genoeg in de praktijk als eerste exploratiefase. Deze resultaten kunnen dan door de expert verder geoptimaliseerd worden in analyse tools als MIME.