AuToMATo: An Out-Of-The-Box Persistence-Based Clustering Algorithm

Deze paper introduceert AuToMATo, een uit het doosje werkend clustering-algoritme op basis van persistente homologie dat door middel van een bootstrapping-procedure significante pieken in dichtheidsfuncties isoleert en in tests vaak beter presteert dan bestaande state-of-the-art methoden, inclusief de optimale parameterinstellingen daarvan.

De kern

Stel je voor dat je een enorme, rommelige kist vol met verschillende soorten objecten hebt: knikkers, Lego-blokjes, schelpen, oude sleutels en stukjes fruit. Je doel is om deze kist te sorteren in groepjes: alle knikkers bij elkaar, alle Lego-blokjes bij elkaar, enzovoort. Dit noemen we clustering (groeperen).

In de wereld van data (bijvoorbeeld in de medische wetenschap of bij het analyseren van klanten) is dit vaak veel lastiger. De "objecten" zijn dan niet zichtbaar, maar bestaan uit cijfers en patronen.

Deze paper introduceert een nieuwe tool genaamd AuToMATo. Hier is een uitleg in simpele taal, met een paar creatieve vergelijkingen.

1. Het Probleem: De "Gouden Standaard" is vaak lastig

Bestaande methoden om data te groeperen werken vaak als een koekjesautomaat. Je moet de machine instellen: "Hoe groot moet de afstand zijn tussen koekjes?" of "Hoe zacht moet het deeg zijn?".

• Als je de knop te ver draait, krijg je één grote, onbruikbare klomp.
• Draai je hem te ver weg, dan krijg je duizenden kleine, losse kruimels.
• Het probleem is: je weet vaak niet welke stand de "juiste" is voordat je de machine hebt aangezet. Je moet veel proberen (tunen), en dat kost tijd en energie.

2. De Oplossing: AuToMATo (De Slimme Zoektocht)

AuToMATo is een nieuwe manier om te groeperen die niet vraagt om ingewikkelde instellingen. Het is "out-of-the-box", wat betekent dat je het eruit haalt en het werkt, net als een goede koffiezetapparaat dat je alleen maar water en bonen hoeft te doen.

Het werkt in drie stappen, die we kunnen vergelijken met het zoeken naar de hoogste bergen in een mistig landschap:

Stap 1: De Kaart Tekenen (ToMATo)

Stel je voor dat je een landschap hebt met heuvels en dalen. De "heuvels" zijn plekken waar veel data bij elkaar zit (dichte groepen), en de "dalen" zijn de lege plekken.
De oude methode (ToMATo) tekent deze kaart en kijkt naar de pieken. Maar hoe weet je welke pieken echte bergen zijn en welke slechts kleine heuveltjes zijn die door de mist (ruis) zijn ontstaan? De gebruiker moest daar zelf een lijn trekken: "Alles boven deze lijn is een berg." Dat was de lastige knop die je moest draaien.

Stap 2: De "Bootstap" (De Bootstrapping)

Hier komt AuToMATo slim in beeld. In plaats van dat jij een lijn trekt, doet AuToMATo het volgende:
Het neemt je data en maakt 1000 kopieën ervan, maar elke kopie is een beetje anders (alsof je de data een beetje schudt en weer neerzet).

• De Analogie: Stel je voor dat je een groep vrienden hebt en je vraagt ze allemaal om een tekening te maken van hetzelfde landschap, maar ze mogen niet naar elkaar kijken.
• Als 950 van die vrienden dezelfde grote berg tekenen, is het een echte berg.
• Als slechts 50 vrienden een kleine heuvel tekenen, is dat waarschijnlijk een foutje of een toevalstreffer.

AuToMATo gebruikt deze "menigte van tekenaars" om te bepalen welke bergen echt bestaan en welke niet. Het berekent een vertrouwensmarge. Alleen de bergen die in bijna alle tekeningen terugkomen, worden als echte groepen erkend.

Stap 3: Het Resultaat

Omdat AuToMATo zelf heeft uitgerekend welke bergen belangrijk zijn, heb jij geen knoppen meer om te draaien. Het algoritme kiest de perfecte grens voor jou.

3. Waarom is dit zo cool?

De auteurs hebben AuToMATo getest tegen de beste andere methoden (zoals DBSCAN, een heel bekende tool).

• Het resultaat: AuToMATo deed het vaak beter, zelfs dan wanneer de andere methoden werden gebruikt door een expert die urenlang had geprobeerd om de perfecte instellingen te vinden.
• De "Mapper" Toepassing: Er is een andere techniek genaamd "Mapper" die complexe data in een net van lijnen en knopen omzet (een soort skelet van je data). Voor Mapper heb je een groepeer-tool nodig die altijd goed werkt, ongeacht welk stukje data je bekijkt. AuToMATo is hier perfect voor, omdat het niet "vastloopt" op slechte instellingen.

4. Samenvatting in één zin

AuToMATo is als een slimme tuinman die niet vraagt welke bloemen je wilt, maar die zelf door de tuin loopt, de bloemen bekijkt, en op basis van honderden kleine observaties zelf beslist welke bloemen bij elkaar horen, zonder dat jij ook maar één knop hoeft te draaien.

Kortom: Het is een krachtige, automatische manier om data te ordenen die werkt "zoals het zou moeten werken": zonder gedoe, zonder gissen, en met uitstekende resultaten.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "AuToMATo: An Out-Of-The-Box Persistence-Based Clustering Algorithm" in het Nederlands.

Probleemstelling

Clustering is een fundamentele techniek in data-analyse om objecten in groepen in te delen op basis van gelijkenis. Veel bestaande algoritmen (zoals DBSCAN, HDBSCAN, hiërarchisch clustering) vereisen echter de selectie van hyperparameters (bijv. afstandsdrempels of het aantal buren). Het kiezen van de juiste parameters is vaak een uitdaging in de praktijk, omdat de optimale instellingen kunnen variëren per dataset en zelfs per subset van de data.

Specifiek binnen het domein van Topological Data Analysis (TDA), en meer bepaald bij het Mapper-algoritme, is dit een kritiek probleem. Mapper bouwt een grafische weergave van de topologische structuur van data door de data te verdelen in overlappende stukken en op elk stuk een clustering toe te passen. Als het gebruikte clustering-algoritme gevoelig is voor parameterkeuze, kunnen verschillende stukken van de data verschillende (suboptimale) resultaten opleveren, wat leidt tot een vervormde of onbetrouwbare Mapper-grafiek. Er is dus behoefte aan een "out-of-the-box" clustering-algoritme dat robuust presteert zonder handmatige parameter-tuning.

Methodologie: AuToMATo

AuToMATo (Automated Topological Mode Analysis Tool) is een nieuw clustering-algoritme dat voortbouwt op het bestaande ToMATo-algoritme (Chazal et al., 2013), maar dit automatiseert door een bootstrapping-procedure te integreren.

De kern van de methode bestaat uit de volgende stappen:

1. Schatting van Dichtheid en Persistentie:

   • Het algoritme schat eerst een dichtheidsfunctie $\hat{f}$ over de datapunten (standaard gebruikmakend van een $k$-nabijheidsgraaf en een 'distance-to-measure' dichtheidsschatter).
   • Vervolgens wordt een persistentie-diagram (persistence diagram) gegenereerd. Dit diagram visualiseert de "prominentie" (levensduur) van lokale maxima in de dichtheidsfunctie. Een punt in dit diagram $(b, d)$ vertegenwoordigt een lokaal maximum dat "geboren" wordt op niveau $b$ en "sterft" op niveau $d$ wanneer de superlevel sets samensmelten. De prominentie is $d - b$.

2. Het Bottleneck Bootstrap-proces:

   • In plaats van dat de gebruiker een drempelwaarde $\tau$ kiest om te bepalen welke maxima significant zijn (zoals bij ToMATo), gebruikt AuToMATo een bottleneck bootstrap.
   • Het trekt $B$ steekproeven met teruglegging (bootstrap samples) uit de originele dataset.
   • Voor elke steekproef wordt een persistentie-diagram berekend.
   • De bottleneck-afstand (een maat voor de afstand tussen twee persistentie-diagrammen) wordt berekend tussen het diagram van de originele data en die van de bootstrap-steekproeven.

3. Bepaling van de Drempelwaarde:

   • Op basis van de verdeling van deze bottleneck-afstanden wordt een betrouwbaarheidsinterval bepaald.
   • De drempelwaarde $\tau$ wordt automatisch ingesteld op een waarde die zorgt dat alleen de significante pieken (die verder van de diagonaal in het diagram liggen dan de berekende foutmarge) behouden blijven.
   • Formeel wordt $\tau$ bepaald als $2 \cdot \hat{q}\alpha / \sqrt{n}$, waarbij$\hat{q}\alpha$de geschatte kritieke waarde is voor een betrouwbaarheidsniveau$\alpha$.

4. Implementatie:

   • Het algoritme is geïmplementeerd in Python en is volledig compatibel met de scikit-learn architectuur.
   • Het biedt standaardwaarden (defaults) voor alle parameters (bijv. $k=10$ voor de nabijheidsgraaf, $\alpha=0.35$, $B=1000$ bootstraps), waardoor het direct inzetbaar is zonder tuning.

Belangrijkste Bijdragen

• Automatisering van ToMATo: AuToMATo transformeert ToMATo van een semi-automatisch algoritme (dat visuele inspectie van het persistentie-diagram vereist) naar een volledig geautomatiseerd, "out-of-the-box" algoritme.
• Robuustheid via Bootstrapping: Door gebruik te maken van de bottleneck bootstrap wordt de keuze van de drempelwaarde statistisch onderbouwd en minder gevoelig voor kleine variaties in de data dan heuristische methoden (zoals het zoeken naar het grootste gat in de prominentiewaarden).
• Open Source Implementatie: De auteurs hebben een Python-pakket ontwikkeld dat makkelijk te integreren is in bestaande workflows en compatibel is met Mapper.
• Uitgebreide Vergelijking: Een grondige experimentele evaluatie tegen state-of-the-art algoritmen.

Resultaten

De auteurs hebben AuToMATo getest op een breed scala aan datasets uit de Clustering Benchmarks suite (Gagolewski, 2022) en vergeleken met:

• DBSCAN en HDBSCAN
• Hiërarchisch clustering (Ward, Single, Complete, Average linkage)
• FINCH
• Een ander ToMATo-gebaseerd algoritme uit de TTK-suite (Topology ToolKit)

Kernbevindingen:

1. Superieure Gemiddelde Prestaties: AuToMATo behaalde de hoogste gemiddelde Fowlkes-Mallows score (FMS) over alle datasets (0.8554), wat beter was dan DBSCAN (0.8457), HDBSCAN (0.8209) en alle andere geteste methoden.
2. Vergelijking met Geoptimaliseerde Parameters: Opmerkelijk is dat AuToMATo (met vaste defaults) vaak beter presteerde dan de beste parameterkeuze van andere algoritmen (zoals DBSCAN met variërende drempelwaarden). Dit toont aan dat het vermijden van parameter-tuning niet ten koste gaat van de kwaliteit; integendeel, het voorkomt dat gebruikers in suboptimale lokale optima belanden.
3. Toepassing in Mapper: In tests met het Mapper-algoritme op synthetische data (twee concentrische cirkels) en de Miller-Reaven diabetes-dataset, produceerde AuToMATo de meest accurate topologische weergave (de Reeb-grafiek). DBSCAN en HDBSCAN leverden hier vaak ongewenste extra randen of verkeerde cycli op door hun gevoeligheid voor parameters.

Significantie en Toekomstperspectief

AuToMATo is een belangrijke stap voorwaarts in het veld van topologische data-analyse en machine learning. Het lost het praktische probleem op van parameter-tuning voor complexe, niet-lineaire datastructuren.

• Voor TDA: Het maakt het Mapper-algoritme veel praktischer en betrouwbaarder voor onderzoekers die de topologische structuur van data willen visualiseren zonder diepgaande expertise in parameterselectie te hebben.
• Voor Algemene Clustering: Het bewijst dat persistentie-based methoden, wanneer goed geautomatiseerd, concurrerend of superieur kunnen zijn aan traditionele methoden, zelfs zonder dat de gebruiker de parameters hoeft te begrijpen.

De auteurs wijzen op beperkingen, zoals de keuze van de standaarddichtheidsschatter en de nabijheidsgraaf, en plannen om deze in toekomstig werk te optimaliseren. Ze onderzoeken ook of de resultaten van AuToMATo kunnen worden gebruikt om de parameters van Mapper zelf verder te optimaliseren.