文章基本信息

标题：Temporal Clustering
本地全文：下载
作者：Tamal K. Dey ; Alfred Rossi ; Anastasios Sidiropoulos 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：87
页码：34:1-34:14
DOI：10.4230/LIPIcs.ESA.2017.34
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We study the problem of clustering sequences of unlabeled point sets taken from a common metric space. Such scenarios arise naturally in applications where a system or process is observed in distinct time intervals, such as biological surveys and contagious disease surveillance. In this more general setting existing algorithms for classical (i.e. static) clustering problems are not applicable anymore. We propose a set of optimization problems which we collectively refer to as temporal clustering. The quality of a solution to a temporal clustering instance can be quantified using three parameters: the number of clusters k, the spatial clustering cost r, and the maximum cluster displacement delta between consecutive time steps. We consider spatial clustering costs which generalize the well-studied k-center, discrete k-median, and discrete k-means objectives of classical clustering problems. We develop new algorithms that achieve trade-offs between the three objectives k, r, and delta. Our upper bounds are complemented by inapproximability results.
关键词：clustering; multi-objective optimization; dynamic metric spaces; moving point sets; approximation algorithms; hardness of approximation