Methods and algorithms for optimal correspondences and assignments in data exploration

QC 2025-02-07

Abstract

När objekt inte är direkt jämförbara med varandra behövs sätt att hitta korrespondenser mellan detaljer i objekten givet att man har ett sätt att värdera interna relationer inom objekten. Patienters resor genom en behandling och organismers olika morfologi är exempel på sådana objekt. Om man har gjort det möjligt att jämföra objekt med varandra är det sedan möjligt att förstå  hur dessa variationer ter sig. Klustring, dvs gruppering av information för att förenkla en stor datamängd till en mindre mängd grupper och hur dessa förhåller sig till varandra är ett sätt att skapa sig en uppfattning om hela fördelningen.

Denna avhandling behandlar kognitiva modeller för att avgöra diskreptanser mellan metriska måttrum, optimala korrespondenser mellan detaljer i objekt samt gruppering och klustring av data. Dessa tillhör en klass av optimeringsproblem som kallas icke-konvexa tilldelningsproblem. Syftet med avhandlingen är att  möjliggöra att lösa dessa typer av problem exakt och skapa algoritmer som gör det möjligt att lösa dessa problem effektivt. Detta får konsekvenser i ökad korrekthet när metoderna används i naturvetenskaperna för att analysera tillstånd, t.ex. vid läkemedelsutveckling. 

Den första artikeln behandlar jämförelser mellan punktmoln. Punktmoln som är en diskretisering av metriska måttrum kan anses isometriska, vilket för vektorrum betyder att det finns en translation och rotation så att de blir identiska. Om detta inte kan ske vill man skapa sig en diskreptans som beskriver hur skilt från isometriska två punktmoln är från varandra. På detta sätt kan data som är deformerat eller saknar information ändå bli jämfört med andra datamoln. Med utgångspunkt i Gromov-Hausdorff distansen och Gromov-Wasserstein distansen presenteras en metod att beräkna denna diskreptans för mångdimensionella moln som effektivt konvergerar till den exakta lösningen och blir praktiskt användbar för t.ex. mikroskopidata. Metoden grundar sig på en halv-plansmetod som approximerar rummet av godkända lösningar effektivt i närheten av de lokalt optimala lösningarna, och bevisar konvergens för konkava kvadratiska problem.

I den andra artikeln återkommer vi till Gromov-Wasserstein problemet, formulerar en lågdimensionell variant för diskreta metriska måttrum och utvecklar konceptet för problem där all information ej är tillgänglig samt för multi-marginala problem. Med detta kan man lösa tyngdpunkter, dvs bästa mellanting mellan olika metriska mått-rum. Detta har applikationer för 3d-rekonstuktion av t.ex. proteiner i elektronmikroskop och en möjlighet att med väldigt lite struktur kunna avgöra morfologiska skillnader och isomerismer, t.ex. kiraliteter. Metoden används också för att lösa det sk dimensionsreduceringsproblement till global optimalitet för några enkla problem. Halvplansmetoden utvidgas till att hantera en mix av konvexa och konkava objektfunktioner.

I den tredje artikeln behandlas problemet kring gruppering av data, där en metod presenteras för hitta den globalt optimala minsta kvadratsumman av avstånd mellan en mängd datapunkter i ett lågdimensionellt rum till en begränsad uppsättning centroider, som skalar väl med antalet datapunkter. Metoden är relaterad till det även på svenska kallade k-means problemet. Metoden utvecklar den sk halv-plansmetoden för generella konkava problem, och inkluderar tekniker för att minska antalet globala lösningar om det existerar symmetrier.

Den fjärde artikeln behandlar gruppering av data där datat är jämförd med någon vald distans. När datat innehåller stora mängder brus och grupperingarna har komplicerade geometrier behöver dessa varsamt separeras från varandra. Artikeln introducerar en metod som förstärker den sk. diffusionsdistansen mellan datapunkterna och bevisar att detta kan ske unikt för små förstärkningar.

urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-359682