A Deterministic Information Bottleneck Method for Clustering Mixed-Type Data

Technische Samenvatting: Een Deterministische Information Bottleneck Methode voor Clustering van Mixed-Type Data

Probleemstelling
Het clusteren van mixed-type data—datasets bestaande uit zowel continue als categorische (nominale en ordinale) variabelen—brengt aanzienlijke uitdagingen met zich mee vanwege de heterogeniteit van de variabelen. Traditionele clusteringalgoritmen hebben vaak moeite om de bijdragen van deze uiteenlopende variabelen te balanceren, wat leidt tot suboptimale clusterstructuren. Hoewel bestaande methoden zoals K-Prototypes, KAMILA en afstandgebaseerde benaderingen (bijv. PAM met Gower's dissimilariteit) oplossingen bieden, vertrouwen ze vaak op centroid-gebaseerde aannames of specifieke afstandsmaten die de onderliggende informatiestructuur van heterogene data mogelijk niet volledig kunnen vatten. Bovendien missen veel bestaande benaderingen een verenigd theoretisch kader dat continu, nominaal en ordinaal van nature kan afhandelen zonder uitgebreide voorbewerking zoals one-hot encoding, wat de clusterstructuren kan vertroebelen en de dimensionaliteit kan verhogen.

Methodologie: DIBmix
Het artikel stelt DIBmix voor, een clusteringalgoritme gebaseerd op het Deterministic Information Bottleneck (DIB) kader, uitgebreid om mixed-type data te verwerken. Het kerndoel is het vinden van een gecomprimeerde representatie $T$ (clusters) van de inputdata $X$ die de wederzijdse informatie maximaliseert met de locatie $Y$ van de data in de mixed-attribute ruimte, onderworpen aan een compressiebeperking.

Belangrijke methodologische componenten zijn:

1. Gegeneraliseerde Productkernels: Om de gezamenlijke dichtheid $p(x, y)$ voor mixed data te schatten, gebruiken de auteurs een gegeneraliseerde productkernel. Deze integreert:

   • Gaussiaanse kernels voor continue variabelen.
   • Aitchison & Aitken kernels voor nominale (ongeordende categorische) variabelen.
   • Li & Racine kernels voor ordinale (geordende categorische) variabelen.
     Deze aanpak vermijdt de aanname van variabele onafhankelijkheid door de kernelproduct als een wegingsmechanisme te gebruiken voor robuuste dichtheidsschatting.

2. Optimalisatiekader: Het algoritme streeft naar het minimaliseren van de objectieve functie $H(T) - \beta I(Y; T)$, waarbij $H(T)$ de entropie van de clustertoewijzingen is (als regularisator voor clustergroottes) en $I(Y; T)$ de wederzijdse informatie is tussen de clusters en de datalocaties. De parameter $\beta$ regelt de afweging tussen compressie en relevantie.

3. Adaptieve Hyperparameterselectie:

   • Bandbreedte Selectie: Een systematische strategie wordt voorgesteld om de bijdragen van continue en categorische variabelen gelijk te trekken. Dit omvat het definiëren van kernelratio's (bijv. de gemiddelde 'furthest-neighbour' kernelratio voor continue variabelen en disagreement ratio's voor categorische variabelen) en het afstemmen van bandbreedtes om ervoor te zorgen dat geen enkele variabeletype de dissimilariteitsmatrix domineert.
   • Adaptieve $\beta$: In tegen tegenstelling tot standaard DIB-implementaties waar $\beta$ vaststaat, gebruikt DIBmix een adaptief update-schema voor de regularisatieparameter $\beta$ bij elke iteratie. Dit zorgt ervoor dat het algoritme convergeert naar een oplossing met exact $C$ niet-lege clusters, zelfs wanneer de data ongebalanceerde clustergroottes bevat, door te voorkomen dat de kleinste cluster verdwijnt.

4. Schaalbaarheid: Voor grote datasets maakt de methode gebruik van de Nyström-approximatie om de computationele complexiteit van het construeren van de volledige dissimilariteitsmatrix te reduceren van $O(n^2)$ naar $O(n\sqrt{n})$, waardoor de aanpak haalbaar is voor grootschalige toepassingen.

Belangrijkste Bijdragen
Het artikel schetst drie primaire bijdragen:

1. Framework Extensie: Het aanpassen van het DIB-kader om van nature mixed-type data (continu, nominaal en ordinaal) te verwerken zonder dimensionaliteitsreductie of one-hot encoding te vereisen.
2. Systematische Hyperparameterstrategie: Het voorstellen van een methode voor het selecteren van bandbreedtes en de regularisatieparameter $\beta$ die de bijdragen van variabelen balanceert en een geldige partitie garandeert in een vooraf bepaald aantal clusters, waarmee het probleem van ongebalanceerde clustergroottes wordt aangepakt.
3. Uitgebreide Evaluatie: Het benchmarken van DIBmix tegen vier gevestigde methoden (KAMILA, K-Prototypes, FAMD met K-Means en PAM met Gower's dissimilariteit) over uitgebreide simulaties en real-world datasets.

Resultaten
De prestaties van DIBmix werden geëvalueerd via:

• Simulaties: 28.800 synthetische datasets werden gegenereerd met variaties in steekproefomvang, aantal clusters, proporties van variabelen, overlapniveaus en cluster vormen.
  • DIBmix behaalde de hoogste mediane Adjusted Rand Index (ARI) en Adjusted Mutual Information (AMI) vergeleken met alle concurrenten.
  • Het demonstreerde bijzondere robuustheid in scenario's met ongebalanceerde clustergroottes en lage tot matige clusteroverlap.
  • Effectgroottes (partiële $\eta^2$) gaven aan dat DIBmix consequent beter presteerde dan concurrenten, met waarden variërend van 0,32 tot 0,99.
• Real-World Benchmarks: De methode werd getest op tien publiekelijk beschikbare UCI-datasets.
  • DIBmix behaalde de beste ARI in vier van de tien datasets.
  • Het presteerde het best wanneer datasets een gebalanceerde mix van variabelen bevatten.
  • De prestaties waren competitief maar iets lager dan FAMD of K-Prototypes in datasets die bijna uitsluitend worden gedomineerd door ofwel categorische ofwel continue variabelen.
  • Een Friedman-test op de tien datasets toonde aan dat DIBmix de beste gemiddelde rang (2,45) had, hoewel statistische significantie niet werd bereikt vanwege het kleine aantal datasets en de kritieke verschildrempel.

Betekenis en Claims
De auteurs beweren dat DIBmix een theoretisch gefundeerd alternatief vormt voor clustering van mixed-type data. De betekenis ligt in:

• Afhandeling van Imbalans: In tegen tegenstelling tot traditionele centroid-gebaseerde algoritmen die vaak de voorkeur geven aan even grote clusters, staat het entropie-gebaseerde doel van DIBmix toe en handelt het zeer effectief ongebalanceerde clustergroottes af.
• Theoretische Rigor: Door gebruik te maken van het Information Bottleneck-principe, biedt de methode een geprincipeerde manier om relevante informatie te extraheren terwijl data wordt gecomprimeerd, wat een ander perspectief biedt dan afstandgebaseerde of modelgebaseerde benaderingen.
• Interpreteerbaarheid: Het framework maakt het mogelijk om de belangrijkheid van variabelen te kwantificeren via wederzijdse informatie, wat helpt bij het identificeren van welke kenmerken de clusteringstructuur aansturen (bijv. het identificeren van klinisch relevante biomarkers in een prostaatkankerdataset).

Het artikel concludeert dat hoewel DIBmix zeer competitief en robuust is, met name voor werkelijk gemengde data, het mogelijk niet de optimale keuze is voor datasets waarbij één type variabele overweldigend domineert. De auteurs erkennen beperkingen met betrekking tot bandbreedte selectie in extreme scenario's en de aanname van cluster homogeniteit, en suggereren dat toekomstig werk lokale bandbreedtes en robuustheid tegen uitschieters zou kunnen verkennen.