Graven in grafen
|
|
Dataminingsysteem
'Bij data mining doorzoeken we allerlei soorten gegevens', vertelt Blockeel. 'In het algemeen proberen we patronen te vinden in grote verzamelingen gegevens. Bijvoorbeeld de database van een bedrijf met gegevens over zijn klanten en producten.' Het verschil met een normale zoekopdracht in een database is dat je bij data mining niet weet naar wat je zoekt. 'Met een gewone zoekopdracht zoek je gericht op een bepaalde term. In de bedrijfsdatabase zou je bijvoorbeeld de verkoopcijfers van een specifiek product in een bepaalde regio kunnen opvragen. Als je dit voor meerdere regio's en producten doet, vind je misschien opvallende afwijkingen voor bepaalde producten en regio's. Maar in de praktijk kan dit betekenen dat je miljoenen vragen moet stellen aan de database, voor er een bij zit waarop je een onverwacht, en dus mogelijk interessant, antwoord krijgt. Een dataminingsysteem doet dat voor je.'
Grafen
Databestanden bevatten vaak niet alleen informatie over de afzonderlijke gegevenselementen, maar ook over de relaties tussen die elementen. Die verbanden kunnen uitgedrukt worden in wat men in vaktermen een graaf (Engels: graph) noemt. Een graaf bestaat uit een verzameling zogenoemde knopen verbonden door lijnen. Voorbeelden van grafen zijn databases of het internet, maar bijvoorbeeld ook een molecuul met zijn structuur van atomen en de verbindingen daartussen. Waar klassieke dataminingsystemen de gegevenselementen als geïsoleerd van elkaar beschouwen, zullen graafgebaseerde dataminingsystemen ook de graafstructuur, de connecties tussen die elementen, analyseren. Dit 'graven in grafen' is de kern van Blockeels onderzoek.
|
|
Webwinkel
Dit klinkt heel abstract, maar volgens Blockeel wordt het concreet voor bijvoorbeeld een webwinkel: 'Zo'n bedrijf heeft de gegevens over zijn klanten en hun aankopen opgeslagen in zijn database. Het kan dan naar een patroon zoeken in de aankopen door klanten van bepaalde producten en hun interesse in bepaalde andere producten. Als je bij Amazon informatie over een bepaald boek vraagt, krijg je ook informatie over andere boeken.' Die gegevens kunnen op verschillende manieren worden gevonden: bij Amazon kunnen ze bijhouden wat de verschillende onderwerpen van de boeken zijn, of ze kunnen het aankoopgedrag van hun klanten onderzoeken door middel van data mining.
Internet
Ook het internet met zijn miljoenen aangesloten servers en miljarden pagina's verbonden door links, is een voorbeeld van een graaf. De algoritmen die zoekmachines als Google gebruiken zijn dataminingalgoritmen. 'Dat is echter een heel specifieke toepassing', zegt Blockeel. 'De zoekmachine kijkt niet alleen naar het aantal keren dat een bepaalde zoekterm op een bepaalde pagina voorkomt, maar ook, of beter juist, naar het aantal verwijzingen op andere pagina's waarin die zoekterm voorkomt.' Hij geeft het voorbeeld van de website van het Leiden Institute of Advanced Computer Science (LIACS), waaraan hij zelf verbonden is. 'Op de hoofdpagina van het LIACS komt de term LIACS zelf niet zo heel vaak voor, maar er zijn wel veel andere sites die bij de term LIACS een link gemaakt hebben naar die pagina. Dat kunnen relevante sites zijn, maar ook minder belangrijke. Een website van een gerenommeerd computerinstituut is relevanter dan die van een computerspelletjesfanaat. Een goede dataminingalgoritme houdt rekening met al die factoren. Daardoor komt de website van het LIACS zelf dan toch bovenaan te staan in de resultatenlijst.'
Molecuul
Een andere soort graaf waarop een algoritme losgelaten kan worden is een molecuul. Blockeel: 'Een bepaalde chemische verbinding is werkzaam als geneesmiddel. De reden daarvoor is dat het molecuul van zo'n verbinding kan binden aan een andere molecuul. In de farmaceutische industrie wordt gezocht naar moleculen die goed binden en liefst niet zoveel bijwerkingen hebben. Als je niet weet welk deel van een molecuul precies de binding veroorzaakt, is het ook moeilijk te voorspellen hoe goed varianten van die molecuul zullen binden. Stel je hebt een aantal moleculen, allemaal voorgesteld als een graaf, en die zijn allemaal in zekere mate werkzaam. Je kunt dan zoeken naar het grootst mogelijke gemeenschappelijk deel van die moleculen. Dat verklaart dan waarschijnlijk ook de eigenschap van die moleculen.'
 |
 |
|
Twee verschillende moleculen die een bepaalde substructuur gemeen hebben. De in het blauw getoonde atomen hebben individueel dezelfde eigenschappen, en komen ook in dezelfde ruimtelijke configuratie ten opzichte van elkaar voor. | |
Fundamentele vraag
Blockeels onderzoek staat echter los van bovengenoemde specifieke toepassingen. Hij houdt zich bezig met de meer fundamentele vraag welk soort grafen geschikt is voor welk soort gegevens en toepassingen, en welke algoritmen daarvoor gebruikt kunnen worden. Als hij nieuwe algoritmen ontwikkeld heeft, zijn er altijd nog een aantal stappen nodig voordat die in concrete situaties toegepast kunnen worden. Blockeel: 'Soms zijn dat niet zo veel extra stappen. We testen sommige algoritmen bijvoorbeeld op een database van moleculen. Maar van daar tot kant-en-klare software voor de bedrijfswereld is nog een hele afstand.'
DNA-onderzoek
Ook voor DNA-onderzoek wordt data mining toegepast, maar daar is het een beetje anders. 'DNA bestaat uit reeksen', vertelt Blockeel. 'Die kun je ook zien als een graaf, maar dan een speciale, waarbij alle punten achter elkaar staan. In zekere zin zijn dat soort grafen eenvoudiger, maar daarmee kun je weer ingewikkeldere dingen gaan doen. Hoe eenvoudiger de soort gegevens die je onderzoekt, hoe meer je ermee kan doen en hoe ingewikkelder het soort patronen dat je erin kunt vinden.'
Computer
Hoewel Blockeel toepassingen voor gebruik op de computer ontwerpt, brengt hij lang niet al zijn tijd achter zo'n ding door. 'In eerste instantie denk ik na over welke soort grafen er zijn en welke algoritmen je daarvoor kunt bedenken. De volgende stap is dan om ze te implementeren en te zien of ze goed werken.' Het vernieuwende aan Blockeels onderzoek is, dat hij op een andere manier gaat kijken naar grafen: 'Traditioneel wordt een graaf beschouwd als een aantal objecten en de verbindingen daartussen. Bij de objecten zelf gaan we er dan vanuit dat die zelf niet veel inhoud hebben. We kijken naar de omgeving van de objecten. Hoe ze in de graaf ingebed zijn. De bestaande algoritmen focussen op de structuur van de knopen of van de graaf. Het object zelf kan echter een webpagina zijn met veel tekst erin. Ik zoek naar een tussenvorm, waarbij zowel de structuur van de graaf als geheel, als de eigenschappen van de knopen op de een of andere manier in de algoritme worden betrokken.'
(22 mei 2007/SH)