Vi studerar kostnadsfunktionen för hierarkiska kluster som infördes av [Dasgupta, 2016] där hierarkier behandlas som förstklassiga objekt snarare än att härleda deras kostnader från projektioner till platta kluster. Det visades också i [Dasgupta, 2016] att en uppifrån-och-ned-algoritm returnerar en hierarkisk klustring av kostnaden som mest O (α n log n) gånger kostnaden för den optimala hierarkiska klustringen, där α n är approximationsförhållandet för den sparest cut subrutinin som används. Med hjälp av den mest kända approximationsalgoritmen för Sparsest Cut på grund av Arora-Rao-Vazirani, returnerar topp-down algoritmen en hierarkisk klustring av kostnader på högst O log 3/2 n gånger kostnaden för den optimala lösningen. Vi förbättrar detta genom att ge en O(log n)-tillnärmning algoritm för detta problem. Våra viktigaste tekniska ingredienser är en kombinatorisk karakterisering av ultrametrics inducerad av denna kostnadsfunktion, härleda en Integer Linear Programmering (ILP) formulering för denna familj av ultrametrics, och visar hur man iterativt runda en LP avkoppling av denna formulering genom att använda idén om sfärodling som har använts i stor utsträckning i samband med graf partitionering. Vi bevisar också att vår algoritm returnerar en O(log n)-ungefärlig hierarkisk klusterbildning för en generalisering av denna kostnadsfunktion också studeras i [Dasgupta, 2016]. Experiment visar att de hierarkier som hittas genom att använda ILP-formuleringen samt vår avrundningsalgoritm ofta har bättre projektioner i platta kluster än standardkopplingsbaserade algoritmer. Vi avslutar med konstant faktor i approximabilitet resultat för detta problem: 1) ingen polynom storlek LP eller SDP kan uppnå en konstant faktor approximation för detta problem och 2) ingen polynom tid algoritm kan uppnå en konstant faktor approximation under antagandet av Small Set Expansion hypotes.
REF skrev ett heltal program för hierarkiska kluster problem med hjälp av en kombinatorisk karakterisering av ultrametrics induceras av Dasgupta kostnadsfunktion.
Hierarchical Clustering via Spreading Metrics
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}