concept k - d tree in category algorithms

This is an excerpt from Manning's book Algorithms and Data Structures in Action MEAP V14. Login to get full access to this book.

Figure 9.1 Our example map, showing cities (real and imaginaries) and warehouses (all imaginary!) on the East coast. In a typical application for k-d trees, given a point on the map, we would like to find the closest warehouse, or the closest city, to that point. Map source: ArcGis.

A k-d tree is a binary search tree whose elements are points taken from a k-dimensional space, i.e. tuples with k elements, whose coordinates can be compared (to simplify, let’s assume each coordinate’s values can be translated into real numbers). In addition to that, in a k-d tree, at each level i we only compare the i-th (modulo k) coordinate of points, to decide which branch of the tree will be traversed.

Tk(n) = 2 * Tk(n/2) + O(n)

copy

Not-linearly separable clusters can’t be approximated with spherical clusters, and as such k-means can’t separate non-convex clusters like (clusters shaped as) two concentric rings; moreover, in all those situations where the clusters’ shape is not spherical and the points can’t be separated correctly using minimum distance from a centroid, k-means will struggle to find good solutions.