Klusterproblem studeras väl inom en rad olika områden, såsom datavetenskap, verksamhetsforskning och datavetenskap. Sådana problem inkluderar varianter av center lokaliseringsproblem, k-median och k-medel för att nämna några. I vissa fall behöver inte alla datapunkter samlas; vissa kan förkastas av olika skäl. Till exempel kan vissa punkter uppstå från buller i en datauppsättning eller man kan vara villig att kasta en viss del av de punkter för att undvika att ådra sig onödiga overhead i kostnaden för en klusterlösning. Vi studerar klusterproblem med outliers. Mer specifikt, vi tittar på okapacitet anläggning plats (UFL), k-median, och k-medel. I dessa problem får vi en uppsättning X av datapunkter i ett metriska utrymme δ (.,.), en uppsättning C av möjliga centra (var och en kanske med en öppningskostnad), kanske ett heltal parameter k, plus en ytterligare parameter z som antalet utliers. I okapacitet anläggning plats med outliers, måste vi öppna vissa centra, kasta upp till z punkter X, och tilldela varje annan punkt till närmaste öppna centrum, minimera den totala tilldelningskostnaden plus centrum öppningskostnader. På k-median och k-medel måste vi öppna upp till k-centra, men det finns inga öppningskostnader. I k-means, kostnaden för att tilldela j till i är δ 2 (j, i). Vi presenterar flera resultat. Vårt huvudsakliga fokus är på fall där δ är en dubblering metrisk (detta inkluderar fast dimensional Euclidean metrics som ett specialfall) eller är den kortaste vägmått för grafer från en mindre sluten familj av grafer. För uniform-kostnad UFL med avvikelser på sådana mätvärden, visar vi att en multiswap enkel lokal sökning heuristic ger en PTAS. Med lite mer arbete, vi utökar detta till bicriteria approximationer för k-median och k-medel problem i samma mått där, för alla konstant ε > 0, vi kan hitta en lösning med (1 + ε )k centra vars kostnad är som mest en (1 + ε )-faktor för den optimala och använder på de flesta z utliers. Våra algoritmer är alla baserade på naturliga multiswap lokala sökheuristics. Vi visar också att naturliga lokala sökheuristiker som inte bryter mot antalet kluster och avvikelser för k-median (eller k-medel) kommer att ha obegränsad gap även i Euclidean mätvärden. Dessutom visar vi hur vår analys kan utvidgas till allmänna mätvärden för k-medel med avvikande värden för att erhålla en (25 + ε, 1 + ε )-uppskattning: en algoritm som använder högst (1 + ε )k kluster och vars kostnad är högst 25 + ε av optimal och inte använder mer än z utliers. En preliminär version av denna artikel dök upp Clustering är uppgiften att dela upp en viss uppsättning datapunkter i kluster baserat på en specificerad likhetsmått mellan datapunkterna så att de punkter inom samma kluster är mer lik varandra än de i olika kluster. I ett typiskt klusterproblem får vi en uppsättning n datapunkter i ett metriska utrymme och ett heltal k som anger önskat antal kluster. Vi vill hitta en uppsättning k-poäng för att fungera som centra och sedan tilldela varje punkt till sitt närmaste centrum, vilket bildar k-kluster. Klusterlösningens kvalitet kan mätas med hjälp av olika mål. Till exempel, i k-means klusterbildning (som är den mest använda klustermodellen), är målet (objektiv funktion) att minimera summan av kvadratavstånd för varje datapunkt till sitt centrum, medan i k-median, målet är att minimera summan av avstånden för varje datapunkt till sitt centrum. Den okapacitet anläggning plats problem är samma som k-median utom att i stället för en kardinality begränsning begränsa antalet centra, det finns en extra kostnad för varje centrum som ingår i lösningen. Minimera dessa objektiva funktioner exakt är NP-hård [3, 19, 24, 32, 42, 46], så det har varit betydande arbete på att få bevisbara övre gränser (tillnärmelsevis) och nedre gränser (otillnärmelsevis) för dessa mål; se Referenser [1, 11, 24, 32, 38, 39] för de för närvarande bästa gränserna. Även om oprecisa resultat [24, 32, 38] förhindra att få polynom tid approximation system (PTAS) för dessa problem i allmänna mätvärden, är PTAS kända för dessa problem i fast dimension Euclidean mätvärden [5, 17, 22]. I själva verket har PTAS för k-median och okapacitet anläggningsplacering i fast dimension Euclidean utrymme [5] varit känt i nästan två decennier, men att få en PTAS för k-medel i fast dimension Euclidean utrymme hade varit ett öppet problem tills nyligen resultat i Referenser [17, 22]. Trots att dessa populära (centerbaserade) klustermodeller är tämligen bra för bullerfria datauppsättningar, är deras objektiva funktioner (särskilt k-means objektiv funktion) extremt känsliga för förekomsten av punkter långt från klustercenter. Därför kan ett litet antal mycket avlägsna datapunkter, så kallade outliers-om inte kasserade-kan dramatiskt påverka klusterkostnaden och även kvaliteten på den slutliga klusterlösningen. Att ta itu med sådana avvikelser är verkligen den här artikelns huvudfokus. Kluster med outliers har en naturlig motivation i tillämpningar där outliers och oväntade data som finns i data kan utöva ett starkt inflytande över klusterkvaliteten. I vissa specifika tillämpningar måste vi ta reda på anomalimönster (ytterligare) i uppgifterna för ytterligare utredning [29]. Här finner man till exempel tillämpningar för att upptäcka bedräglig användning av kreditkort-genom att övervaka transaktioner data för att upptäcka exceptionella fall kanske i typ av inköp, plats, tidsram, och så vidare för att upptäcka misstänkta affärer på aktiemarknaderna eller för att övervaka medicinska tillstånd eller mer; se hänvisning [29] för mer information. Vi begränsar vår uppmärksamhet till den avvikande versionen av de tre välstuderade klusterproblemen: kmeans with outliers (k-means-out), k-median with outliers (k-median-out) och oduglig anläggningsplats med utliers (UFL-out). Formellt sett, i dessa problem, får vi en uppsättning X av
En polynom tid bicriteria (1 + ) - approximation med som mest k (1 + ) centra för alla > 0 är känd i lågdimensionella Euclidean utrymmen, och metriska utrymmen med konstant dubblering dimension REF.
Approximation Schemes for Clustering with Outliers
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}