scikit-landmark 0.0.4

No project description provided

landmark

landmark is a Python package that constructs landmarks $L^\ast \subset X$ from a point set $X \subset \mathbb{R}^d$ or a metric space $(X, d_X)$ that approximate the metric k-center problem (also known k-center clustering problem):

$$ L^\ast \triangleq \mathop{\mathrm{argmin}}\limits_{\substack{L \subseteq X : \lvert L \rvert = k}} \ \max_{x \in X} d_X(x, L)$$

Metric $k$-center is a classic NP-hard problem intrinsically similar to other classical problems, such as geometric set cover and facility location; its output is also related to other geometric constructions, like r-nets and well-separated pair decompositions.

Below is an example a data set $X$ (blue points), some sample landmarks $L$ (red), along with the coverage (yellow) and packing (orange) properties they obey.

Installation

Clone and use:

python -m pip install < landmark-py location >

Warning: this package is very early-stage, e.g. does not offer wheels on PyPI. Use with care.

Usage

Given a point cloud $X \in \mathbb{R}^{n \times d}$ represented as a numpy matrix with $n$ points in $d$ dimensions, the indices of the landmarks can be found with the landmarks function:

from landmark import landmarks
ind = landmarks(X, k = 25) ## Finds the indices of 25 landmarks
print(ind)
# [0, 32, 45, 16, ...]

The first $k$-indices of ind are equivalent to the $k$-th prefix of the greedy permutation. You can get their covering radii by specifying radii = True:

from landmark import landmarks
ind, radii = landmarks(X, k = 25, radii = True) ## Finds the indices of 25 landmarks
print(ind, radii)
# [0, 32, 45, 16, ...]
# [inf 31.6024 28.4495 20.3045 ...]

For more examples, see notebook example.