Låt P vara en uppsättning (kallade poäng), Q vara en uppsättning (kallade frågor) och en funktion f : P ×Q → [0, ∞) (kallas kostnad). För en felparameter > 0, en uppsättning S  på P med viktfunktion w : P → [0, ∞) är en ε-coreset om s på S w(s)f (s, q) approximerar p på P f (p, q) upp till en multiplikativ faktor på 1 ± ε för varje given fråga Q. Coresets används för att lösa grundläggande problem vid maskininlärning av strömmande och distribuerade data. Vi konstruerar kärnuppsättningar för k-means klustring av n ingångspunkter, både i ett godtyckligt metriska utrymme och d-dimensionellt Euclidean utrymme. För Euclidean utrymme, presenterar vi den första coreset vars storlek är samtidigt oberoende av både d och n. I synnerhet är detta den första coreset av storlek o(n) för en ström av n glesa punkter i en d ≥ n dimensional utrymme (t.ex. adjacencymatriser för grafer). Vi tillhandahåller också de första generaliseringarna av sådana kärnor för att hantera avvikelser. För godtyckliga metriska mellanslag förbättrar vi beroendet av k to k log k och presenterar en matchande nedre gräns. För M-estimator klustring (särskilda fall inkluderar den välkända k-median och k-medel klustring), introducerar vi en ny teknik för att omvandla en offline coreset konstruktion till streaming inställning. Vår metod ger streaming coreset algoritmer som kräver lagring av O(S + k log n) punkter, där S är storleken på offline coreset. Som jämförelse, den tidigare state-of-the-art var den sammanfogning-och-reduce teknik som krävde O(S log 2a+1 n) punkter, där a är exponenten i offline konstruktionens beroende av −1. Till exempel, genom att kombinera våra offline- och streamingresultat, producerar vi en streamingmetrisk k-means coreset-algoritm med O( −2 k log k log n) platser för lagring. Den tidigare tekniken krävde O( −4 k log k log 6 n) poäng.
För specialfallet av k-means, Braverman et al. REF förbättrade storleken till Õ(kε −2 · min {k/ε, d}) genom en dimensionsreduktionsmetod.
New Frameworks for Offline and Streaming Coreset Constructions
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}