Timezone: »
Poster
k-Means Clustering of Lines for Big Data
Yair Marom · Dan Feldman
Tue Dec 10 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #34
The input to the \emph{$k$-mean for lines} problem is a set $L$ of $n$ lines in $\mathbb{R}^d$, and the goal is to compute
a set of $k$ centers (points) in $\mathbb{R}^d$ that minimizes the sum of squared distances over every line in $L$ and its nearest center. This is a straightforward generalization of the $k$-mean problem where the input is a set of $n$ points instead of lines.
We suggest the first PTAS that computes a $(1+\epsilon)$-approximation to this problem in time $O(n \log n)$ for any constant approximation error $\epsilon \in (0, 1)$, and constant integers $k, d \geq 1$. This is by proving that there is always a weighted subset (called coreset) of $dk^{O(k)}\log (n)/\epsilon^2$ lines in $L$ that approximates the sum of squared distances from $L$ to \emph{any} given set of $k$ points.
Using traditional merge-and-reduce technique, this coreset implies results for a streaming set (possibly infinite) of lines to $M$ machines in one pass (e.g. cloud) using memory, update time and communication that is near-logarithmic in $n$, as well as deletion of any line but using linear space. These results generalized for other distance functions such as $k$-median (sum of distances) or ignoring farthest $m$ lines from the given centers to handle outliers.
Experimental results on 10 machines on Amazon EC2 cloud show that the algorithm performs well in practice.
Open source code for all the algorithms and experiments is also provided.
Author Information
Yair Marom (University of Haifa)
Data-reduction (core-sets) for AI & Big Data researcher at the Robotics & Big Data Laboratory, Computer Sciences Department, University of Haifa. Specialized in the fields of Unsupervised Learning, Computer Vision and IOT.
Dan Feldman (University of Haifa)
More from the Same Authors
-
2021 Spotlight: Coresets for Decision Trees of Signals »
Ibrahim Jubran · Ernesto Evgeniy Sanches Shayda · Ilan I Newman · Dan Feldman -
2021 Poster: Compressing Neural Networks: Towards Determining the Optimal Layer-wise Decomposition »
Lucas Liebenwein · Alaa Maalouf · Dan Feldman · Daniela Rus -
2021 Poster: Coresets for Decision Trees of Signals »
Ibrahim Jubran · Ernesto Evgeniy Sanches Shayda · Ilan I Newman · Dan Feldman -
2020 Poster: Coresets for Near-Convex Functions »
Murad Tukan · Alaa Maalouf · Dan Feldman -
2019 Poster: Fast and Accurate Least-Mean-Squares Solvers »
Ibrahim Jubran · Alaa Maalouf · Dan Feldman -
2019 Oral: Fast and Accurate Least-Mean-Squares Solvers »
Ibrahim Jubran · Alaa Maalouf · Dan Feldman -
2016 Poster: Dimensionality Reduction of Massive Sparse Datasets Using Coresets »
Dan Feldman · Mikhail Volkov · Daniela Rus