Oberseminar "Mathematik des Maschinellen Lernens und Angewandte Analysis" - M.Sc. Maximilian Fleissner

Despite the growing popularity of explainable and interpretable machine learning, there is still surprisingly limited work on inherently interpretable clustering methods. Recently, there has been a surge of interest in explaining classic k-means or k-medians clustering using axis-aligned decision trees. While this has led to algorithms with provable guarantees on the performance of the interpretable model, there are two key shortcomings. First, the guarantees are data-agnostic and therefore loose in practical settings, failing to capture the intuition that well-clustered data should also be easy to explain. Second, k-means has limited applicability in practice, where more flexible clustering methods are often needed to obtain useful partitions of the data. This talk develops explainable clustering algorithms that address these shortcomings, with new data-dependent guarantees and extensions to kernel k-means.