Abstrakt. I detta dokument studerar vi klusterbildning med avseende på k-modes objektiva funktion, en naturlig formulering av klusterbildning för kategoriska data. Ett av de viktigaste bidragen i detta dokument är att fastställa kopplingen mellan kmodes och k-median, dvs. det optimala av k-median är som mest det dubbla det optimala av k-modes för samma kategoriska datakluster problem. Baserat på denna observation, härleder vi en deterministisk algoritm som uppnår en approximationsfaktor på 2. Dessutom bevisar vi att avståndsmåttet i k-läge definierar ett mått. Därför kan vi utöka befintliga approximationsalgoritmer för metriska k-median till k-lägen. Empiriska resultat bekräftar vår metods överlägsenhet.
I REF undersöks likheten och effektiviteten hos k-mode och relateras till k-medianmetoden.
Approximation Algorithms for K-Modes Clustering
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}