Het vinden van subspace clusters met lokale buurten

Datum: 19 oktober 2015

Locatie: UAntwerpen - Campus Middelheim - gebouw A, A.143 - Middelheimlaan 1 - 2020 Antwerpen

Tijdstip: 16 uur

Promovendus: Mehmet Emin Aksehirli

Promotor: Bart Goethals

Korte beschrijving: Doctoraatsverdediging Mehmet Emin Aksehirli - Faculteit Wetenschappen, Departement Wiskunde-Informatica



Abstract

Data is al een paar jaar belangrijker dan ooit tevoren. Gezien hoe het de wereld om ons heen vormt, is het duidelijk dat het belang van data niet snel zal afnemen. Organisaties van over de hele wereld hebben het grote belang van data begrepen en geprobeerd alle informatie waartoe ze toegang hebben op te slaan. Omdat het niet triviaal is grote hoeveelheden data te annoteren, zijn unsupervised methodes zeer geschikt om grote hoeveelheden data te analyseren. Terwijl cluster analyse kan gebruikt worden als een pre-processing stap om gegevens samen te vatten en voor te bereiden voor supervised technieken, kunnen frequent pattern mining methoden gebruikt worden om interessante verbanden te vinden in de data.

Een van de kenmerken van de BigData is de hoeveelheid data die gekoppeld is aan een enkel dataobject. Hoewel meer data voor een beter en nauwkeuriger begrip zorgt, is het ook mogelijk dat de redundantie in de data het ontdekken van interessante relaties hindert. Bovendien, is het mathematisch aangetoond dat wanneer het aantal dimensies verhoogt, dataobjecten steeds meer op elkaar lijken. Dit fenomeen staat bekend als de curse of dimensionality.
 
Omdat het concept gelijkaardigheid vervormd is in hoog dimensionale ruimtes, kunnen traditionele clustering methoden, die sterk afhankelijk zijn van similarity measures, niet effectief zijn. Anderzijds, is de gelijkaardigheid aan de hand van subsets van attributen nog steeds zinvol en kan dit worden gebruikt om interessante verbanden te ontdekken. Subspace clustering algoritmen pakken het probleem van hoge dimensionaliteit aan door een cluster te definiëren als  als een paar van sets: de dataobjecten die op elkaar lijken en de dimensies waarin zij vergelijkbaar zijn. Bijgevolg degradeert het beperken van de relevante dimensies de gevolgen van de curse of dimensionality en benadrukt de gelijkenis van objecten door het produceren van compacte clusters. Maar het zoeken naar de relevante dimensies maakt het  NP-hard probleem  van cluster analyse nog ingewikkelder.
 
In deze thesis hebben we het probleem van hogedimensionaliteit benaderd vanuit een ``neighborhood-oriented'' oogpunt. We onderzoeken verschillende manieren om een relationele database te transformeren, zodat we meer instrumenten hebben, die we kunnen gebruiken om kennis te extraheren. Na het toepassen van de cartification transformatie kunnen frequent itemset mining methoden gebruikt worden op relationele databases en dankzij de neighborhood-based vertegenwoordiging zijn er nieuwe mogelijkheden voor visualisatie en interactiviteit.

De thesis is als volgt georganiseerd:

  • Hoodstuk 2 introduceert het hoofdthema van deze thesis: de Cartification transformatie. Cartification transformeert een relationele database naar een transactie database door het behoud van localities van individuele data-objecten als neighborhoods. Door het transformeren van de gegevensruimte, maakt cartification het gehele domein van frequent itemset mining methoden toepasbaar op het gebied van relationele gegevensanalyse. We laten zien dat de curse of dimensionality kan verminderd worden door het gebruik van de localities en dat zelfs het toepassen van de meest elementaire FIM methoden op gecartificeerde gegevens resultaten oplevert die de state-of-the-art cluster analysemethoden verslaan.
     
  • Hoofdstuk 3 introduceert CLON algoritme. Cartification is een algemene transformatie die kan toegepast worden op elk type data zolang een similariteitsmaat tussen data objecten is gedefinieerd. Wanneer een totale ordening van de objecten mogelijk is, d.w.z het bestudeerde attribute is univariaat, dan krijgt de getransformeerde database sommige intrinsieke eigenschappen. Deze eigenschappen kunnen gebruikt worden om het computationele duur proces van frequente itemset mining te elimineren. CLON is ordegroottes sneller dan de originele cartification en geeft betere resultaten op synthetische en echte datasets.
     
  • Hoofdtuck 4 benadert cartification vanuit een verfijnder perspectief. In plaats van een binaire transactie database te creëren, creëert CartiRank ranked neighborhood matrices. We bestuderen de eigenschappen van deze ranked neighborhood matrices en stellen een algoritme voor dat deze eigenschappen uitbuit om efficiënt tiles, die clusters vertegenwoordigen, te vinden. We laten zien dat het behoud van de werkelijke volgorde van de objecten meer robuuste resultaten oplevert.
     
  • Hoofdstuk 5 gaat over onze tool VINeM, die het vinden van neighborhoods beschikbaar voor een breder publiek. VINeM, waarvan de naam staat voor Visual Interactive Neighborhood Miner, biedt een gebruiksvriendelijke interface die een intuïtieve voorstelling van neighborhoods met unsupervised algoritmes combineert. Belangrijkste focus van VINeM is om de relaties tussen objecten onder verschillende attributen te tonen, zodat een gebruiker snel greep op de data kan krijgen. Dankzij de interactiviteit kan de gebruiker fundamentele manipulaties van de gegevens uitvoeren en verschillende oogpunten op de data creëren.
     
  • Hoofdstuk 6 introduceert twee frequent itemset mining algoritmes die worden uitgevoerd op het Hadoop framework. Een van de belangrijkste beperkingen van interactieve data exploratie is de reactietijd. Gelukkig, kunnen zware mining algoritmes uitbesteed worden aan cloud services, zodat de beperkte resources van de klant beter kunnen benut worden. Op deze manier, zijn DistEclat en BigFIM twee parallelle algoritmen die kunnen uitgevoerd worden op cloud services. We tonen aan dat de prestaties van de mining algoritmes in een MapReduce paradigma afhankelijk zijn van een evenwichtige verdeling van de data tussen de berekeningsnodes. We deden exhaustieve experimenten en onderzochtten manieren om de data en de computationele belasting optimaal te verdelen.