ارائه دکتر محمد صلواتی‌پور با موضوع "Clustering: outliers and stable instances"

دکتر محمد صلواتی‌پور
دکتر محمد صلواتی‌پورDr Mohammad Salavatipour
Associate Professor, University of Alberta

Clustering: outliers and stable instances

برگزار کنندگان ایونت :‌ انجمن علمی دانشکده مهندسی کامپیوتر پلی تکنیک

توضیح محتوای ایونت:

Clustering problems are well-studied in a variety of fields such as data science, operations
research, and computer science. Such problems include variants of centre location problems,
k-median, and k-means to name a few. In some cases, not all data points need to be
clustered; some may be discarded for various reasons. For instance, some points may arise
from noise in a data set or one might be willing to discard a certain fraction of the points to
avoid incurring unnecessary overhead in the cost of a clustering solution. We study clustering
problems with outliers. More specifically, we look at facility location, k-median, and k-means.
Our main focus is on cases where the metric space is a doubling metric (this includes fixed
dimensional Euclidean metrics as a special case) or is the shortest path metrics of graphs from
a minor-closed family of graphs. For all of these, we show that a multi-swap simple local
search heuristic yields a PTAS (polynomial time approximation scheme)with small violation on
the number of clusters. We also investigate the complexity of solving stable or
perturbation-resilientinstances of k-means and k-median clustering in fixed dimension
Euclidean metrics (or more generally doubling metrics).The notion of stable or perturbation
resilient instances was introduced by Bilu and Linial [2010] and Awasthi, Blum, and Sheffet[2012]. In our context, we say a k-means instance is alpha-stable if there is a unique optimum
solution which remains unchanged if distances are (non-uniformly)stretched by a factor of at
most alpha. Stable clustering instances have been studied to explain why heuristics such as
Lloyd’s algorithm perform well in practice. We show that for any fixed epsilon>0,
(1+epsilon)-stable instances of k-means in doubling metrics can be solved in polynomial time.
Using the same simple local search heuristic.

تاریخ ایونت

۱۵ اردیبهشت ماه ۱۳۹۸، ساعت ۱۵

مکان ایونت

آمفی تئاتر دانشکده مهندسی کامپیوتر

قیمت ایونت

رایگان

عکس های رویداد