scikit-landmark 0.1.2

No project description provided

Landmark

landmark is a Python package that constructs a sequence of landmarks $L_k = ({x_1, x_2, \dots, x_k })$ from a point set $X \subset \mathbb{R}^d$ or metric space $(X, d_X)$ via furthest-first traversal:

$$ x_i = \mathop{\mathrm{arg min}}\limits_{x \in X} \mathop{} d_X(x, L_{i − 1}) $$

The resulting landmarks satisfy a number of convenient coverage and packing properties. 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.

The sequence formed by resulting landmarks, also called the greedy permutation, can be used to approximate a number of classical problems, such as the traveling saleman problem, the metric k-center clustering problem, and various proximity / range searching problems.

Installation

The package can be installed with pip:

python -m pip install scikit-landmark

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
X = np.random.uniform(size=(50,2))
ind = landmarks(X, k = 10) ## Finds the indices of 25 landmarks

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

ind, info = landmarks(X, k = 10, full_output = True)
print(ind)                  ## prefix indices
print(info['radii'])        ## insertion radii 
print(info['predecessors']) ## predecessor map 

For other usages, see the documentation.