Clustering under mest populära objektiva funktioner är NP-hård, även att approximera väl, och så osannolikt att vara effektivt lösbar i värsta fall. Nyligen föreslog Bilu och Linial [11] ett tillvägagångssätt som syftar till att kringgå denna beräkningsbarriär genom att använda egenskaper hos fall som man kan hoppas kunna hålla i praktiken. I synnerhet hävdar de att fall i praktiken bör vara stabila till små perturbationer i det metriska utrymmet och ge en effektiv algoritm för kluster fall av Max-Cut problem som är stabila till perturbationer av storlek O(n 1/2 ). Dessutom antar de att fall stabila till så lite som O(1) perturbationer bör vara lösliga i polynom tid. I detta papper bevisar vi att detta antagande är sant för alla center-baserade klustering mål (såsom k-median, k-medel, och k-center). Specifikt visar vi att vi effektivt kan hitta den optimala klusterbildningen förutsatt att endast stabilitet till faktor-3 perturbationer av den underliggande metriska i utrymmen utan Steiner punkter, och stabilitet till faktor 2 + 3 perturbationer för allmänna mätvärden. I synnerhet visar vi för sådana fall att den populära Single-Linkage algoritmen i kombination med dynamisk programmering kommer att hitta den optimala klusterbildningen. Vi presenterar även NP-hårdhet resultat under ett svagare men relaterat tillstånd.
Studien av klusterbildning under perturbationsresiliens initierades av Awasthi et al. REF, som gav en optimal algoritm för center-baserade klustermål (som inkluderar k-median, k-medel, och k-center kluster, samt andra mål) under 3-perturbation motståndskraft.
Center-based Clustering under Perturbation Stability
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}