Multivariat analyse av klyngeproblemer

I databehandling er det ofte behov for å utvikle metoder som kan klassifisere og gruppere datapunkter som ligner hverandre. Disse problemene kalles vanligvis for "klyngingsproblemer". Et eksempel er innen maskinlæring, der man kanskje ønsker å identifisere bilder med en spesifikk type innhold.

K-median-problemet er et slikt klyngingsproblem. Målet her er å dele inndataene inn i et gitt antall grupper slik at avstanden mellom hvert datapunkt i en gruppe og dets respektive senter er så liten som mulig. Avstanden og senteret kan måles på ulike måter. Dette er generelt et utfordrende problem, og man kan ikke alltid forvente å finne en rask, generell tilnærming for å løse det. Derfor er det ønskelig å fastslå i hvilke tilfeller det er mulig å finne en optimal løsning og når det ikke er det.

En løsning på K-median-problemet må ta hensyn til flere faktorer, inkludert antallet klynger å dele dataene inn i, antallet dataelementer som skal klassifiseres, og egenskapene til hvert dataelement.

Denne avhandlingen utfører en omfattende analyse av problemet, og vurderer hvordan det kan løses for ulike antall klynger, ulike datatyper og hvordan man kan bestemme senteret for hver klynge. Forskningen har som mål å gi innsikt i effektive løsningsstrategier under ulike forhold og bidra til en bredere forståelse av problemet.

Personalia

Nidhi Purohit har vært doktorgradsstudent i algoritmegruppen ved Institutt for informatikk siden januar 2020, hvor hun har blitt veiledet av Prof. Petr A. Golovach og Prof. Fedor V. Fomin. Hun oppnådde en mastergrad i informatikk ved ENS Lyon, Frankrike.