PEAC · Provably-Correct Efficient Algorithms for Clustering
Horizon 2020 — Marie Skłodowska-Curie Actions
- Duration
- 2017-03-01 → 2019-02-28
- EU contribution
- €200,195
- Participants
- 1
- Scheme
- MSCA-IF
Lines connect the coordinator with its partners.
Results in brief
Provably-Correct Efficient Algorithms for Clustering
Machine learning and data analysis are taking an increasingly high role in the decisions made in our everyday life. Yet, we still understand very little about some of the basic tools used to process and extract information the data that lead to the decisions. For example, a keystone problem in machine learning is to cluster a dataset into groups such that data elements in the same group have common features. This is a fundamental problem as it allows to identify data elements that might not at first appear very similar, and so it is used to detect communities in social network, classify genes according to their expression pattern or divide a digital image into distinct regions. While there is a large body of experimental work on heuristics for solving clustering problems, a lot less is known from a theoretical perspective but how can we trust machine learning or data analysis approaches if we do not understand the behavior of some of the basic tools that are used to extract information from the data? Furthermore, how can we rely on the decision made by machine learning algorithms if we do not understand which data they were based on. In this project, we have made significant progress towards analyzing and providing performance guarantees on popular clustering heuristics by focusing on specific inputs arising in machine learning and data analysis scenarios. We have analysed very simple heuristics such as local search on these types of inputs. Moreover, we have designed new algorithms that are nearly as fast as widely-used heuristics while outputting solution with provable properties. For example, we have shown how to speed-up local search techniques while preserving the quality of the solution output. We have also shown why some of the popular heuristics are much more efficient than others. Finally, we have made progress on the understanding of the complexity of some important clustering problems.
Data: CORDIS, © European Union
Project objective
Clustering data according to similarity is ubiquitous in computer and data sciences. Similarity between data is often modeled by a distance function: two data points are close if they are similar. This induces a metric space in which each data point is associated to a point of the space. Thus, a clustering according to similarity is a partition of the points such that the distance between two points in the same part is small. Therefore, clustering problems play a crucial role in extracting information from massive datasets in various research areas. However, this problem is hard to formalise: the soundness of a particular clustering often depends on the structure of the data. This induces a gap between theory and practice: on the one hand no guarantee on the practical algorithms can be proven, on the other hand the best theoretical algorithms turn out to be noncompetitive in practice.By focusing on both the algorithms and inputs that are relevant in practice, the PEAC project aims at rigorously analysing the cutting-edge heuristics and designing more efficient algorithms that are provably-correct for both clustering and hierarchical clustering (HC), bridging a gap between theory and practice.Very recently, it was shown that a widely-used local search (LS) algorithm achieves the best approximation guarantees for some specific inputs. We plan to design a faster LS-based algorithm for those types of inputs to achieve both better running time and approximation guarantees than the best heuristics. We will design a non-oblivious LS algorithm to obtain a better than the current 2.675 approximation for k-median.Dasgupta recently introduced a cost function for HC. Using this cost function, we plan to analyse the performances of widely-used heuristics for HC (e.g.: average-linkage, bisection k-means). We will characterize the real-world inputs and use the cost function to design more efficient provably-correct algorithms for HC.
Original text from CORDIS.
Participants
- KOBENHAVNS UNIVERSITET · KOBENHAVNCoordinatorDenmark
Links
Data: CORDIS, © European Union