En av de mest populära och allmänt använda metoderna för dataklustring är hierarkisk klusterbildning. Denna klusterteknik har visat sig användbar för att avslöja intressant struktur i data i flera tillämpningar som sträcker sig från beräkningsbiologi till datorseende. Robusthet är ett viktigt inslag i en klusterteknik om vi kräver att klustret ska vara stabilt mot små störningar i indata. I de flesta tillämpningar, att få en klustereffekt som är robust mot motstående avvikelser eller stokastiskt buller är ett nödvändigt villkor för tillämpligheten och effektiviteten av klustertekniken. Detta är ännu mer kritiskt i hierarkisk klusterbildning där en liten förändring längst ner i hierarkin kan sprida sig ända fram till toppen. Trots allt tidigare arbete [2, 3, 6, 8] är vår teoretiska förståelse av robust hierarkisk klusterbildning fortfarande begränsad och flera hierarkiska klusteralgoritmer är inte kända för att tillfredsställa sådana robusthetsegenskaper. I detta dokument studerar vi gränserna för robust hierarkisk k-centerklustring genom att introducera begreppet universell hierarkisk klusterbildning och ge (nästan) snäva nedre och övre gränser för det robusta hierarkiska k-centerklustret problem med outliers och varianter av det stokastiska klusterproblemet. Viktigast av allt presenterar vi en konstant-faktor approximation för optimal hierarkisk k-center med som mest z outliers med hjälp av en universell uppsättning av högst O(z 2 ) uppsättning outliers och visar att detta resultat är tight. Dessutom visar vi nödvändigheten av att använda en universell uppsättning avvikelser för att beräkna en ungefär optimal hierarkisk k-center med olika uppsättning avvikelser för varje k.
Vi nämner Lattanzi et al:s arbete. REF som anser hierarkisk k-center med avvikande värden.
Robust Hierarchical k-Center Clustering
{'venue': "ITCS '15", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}