Places k seed points at k-means cluster centres of the observed
coordinates, so seeds (and the Voronoi cells built from them) follow the
sampling density: clusters of observations attract seeds, empty ground gets
none. Use it when the cells should follow the data. With the default
density kind the cells hold similar numbers of observations once there
are more cells than clusters of points, which keeps per-cell aggregates in
summarize_by_cell() from resting on one or two observations. Plain
k-means (partition = "kmeans") minimises the spread of points around
each centre and does not even out the counts. Use
voronoi_seeds_random() instead when you want coverage of the study area
rather than of the data, and get_voronoi_seeds() to pick between them by
name.
Usage
voronoi_seeds_kmeans(
points_sf,
k,
set_seed = 456,
nstart = NULL,
partition = c("density", "kmeans"),
init = NULL,
density_power = 1,
density_k = 8,
iter_max = NULL
)Arguments
- points_sf
An sf object with POINT geometries. Points that mix XY and XYZ (or XYM) are read without Z and M before they are projected or clustered, since sf reads a layer in the dimension of its first geometry.
- k
Integer; requested number of clusters, treated as an upper bound only. It is clamped, with a warning, to whichever is smaller of the number of distinct point positions and one fewer than the number of points with a location (rows without one are dropped first), and not below 1, because k-means can produce neither more centres than there are distinct points nor as many centres as there are rows. Check
nrow()on the result. Aselect_resolution()result or aresolution_profile()is also accepted: its scored centres are returned when it carries them, whateverpartition,initand density settings the call names (seeninget_voronoi_seeds()for which arguments a call is taken to name), and otherwise its count is used. A profile is read asget_voronoi_seeds()reads one passed asn: bycpwhen it was built without anestimate, and byselect_resolution(criterion = "auto")when it was built with one (a size for pooled values, the lowest leave-one-out error for plain means). Such a count raises the warnings and the error described underninget_voronoi_seeds()(classes"spatialkit_bound_chosen","spatialkit_no_structure"and"spatialkit_no_default_criterion").- set_seed
Optional integer RNG seed. Default 456, so a call gives the same seeds every time whatever the session's random-number state; an outer
set.seed()does not change them, and the caller's random-number stream is left as it was. PassNULLto draw the k-means starts from the session's stream instead (the default ofget_voronoi_seeds()).- nstart
The number of starts, of which the best is kept.
NULL(default) uses 3 starts forpartition = "density"and 10 forpartition = "kmeans". A number is run under either kind and eitherinit.- partition
What the seeds minimise.
"density"(default): the sum of squared distances from the points to their nearest seed, each point weighted by its local density to the powerdensity_power; compact cells that, at the default power, hold about the same number of points each oncekis above the number of dense places, and counts about as uneven as"kmeans"gives below that."kmeans": the same sum unweighted; compact cells whose counts are several times higher in dense places than in sparse ones. It isstats::kmeans()from 10 random starts on the rows as they come, with the coordinates centred, divided by the diagonal of their bounding box and rounded to 2^-30 of it, so that the seeds do not move with the unit or the origin; where the locations span less than a kilometre a change of unit or origin can still move them (see "The partition" inresolution_profile()). Without the FNN package the density kind finds its weights by comparing every pair of distinct locations, so its time grows with the square of their number; the seeds are the same, and nothing stops the call. See "Details".- init
How each start is drawn:
"random"(kdistinct locations at random, asstats::kmeans()draws them) or"kmeans++"(the seeds one at a time, each in proportion to its squared distance from those already drawn, times its weight underpartition = "density").NULL(default) is each kind's own rule:"random"forpartition = "kmeans"and"kmeans++"forpartition = "density". Underpartition = "kmeans"from random starts the points are clustered in the order their rows come in; withinit = "kmeans++", and underpartition = "density", the rows are put in coordinate order first, so the seeds do not depend on their order.- density_power
For
partition = "density": the power the local density is raised to for a point's weight, from 0 to 2. Default 1, which evens out the cell counts once the cells outnumber the dense places; 0 weights every point alike, and values above 1 give the cells of dense places fewer points than those of sparse places. Setting it underpartition = "kmeans"is a warning.- density_k
For
partition = "density": the number of nearest neighbours the local density is read from. Default 8.- iter_max
The most iterations a start runs for: a single positive whole number, or
NULL(default) for the kind's own limit, 50 forpartition = "kmeans"and 100 steps of Lloyd's iteration forpartition = "density". Underpartition = "density", and withinit = "kmeans++", a kept start that was cut off at the limit is a warning of class"spatialkit_not_converged";partition = "kmeans"from random starts keeps the warningstats::kmeans()gives.
Value
An sf object of at most k cluster-centre POINTs (fewer when
k is clamped, see k), with seed_id and
method = "kmeans" columns matching get_voronoi_seeds(), and
attr(, "cover"), the convex hull of the coordinates of points_sf
(an sfc in its CRS): for lon/lat points, the hull in degrees, with the
longitudes of points on both sides of 180 degrees taken from 0 to 360
(-170 as 190).
Seeds placed with partition = "density" or init = "kmeans++", and
the scored centres of a profile of the density kind or from random
starts, also carry attr(, "partition"): a list with
kind, init, density_power and density_k, and for seeds this
call placed iter, iter_max and converged (the iterations the kept
start took, the limit, and whether it stopped before the limit).
build_tessellation() returns the list as params$partition. Seeds
with no such record are plain k-means: from random starts when this call
placed them, or the scored centres of a k-means profile from k-means++
starts. When k is a
select_resolution() result that carries count_rule, or a profile
built with an estimate or read by cp, the seeds carry that record as
attr(, "count_rule"), with scored_cells TRUE for the scored
centres and FALSE for refitted centres and for centres this call fits
itself at that count (see get_voronoi_seeds()).
Details
Lon/lat input is projected first so the k-means distances are metric and not
degrees; so is input with no CRS whose coordinates look like lon/lat (the
heuristic ensure_projected() applies, with its warning), and the seeds
come back in the input's own coordinates. Rows without a location (an
empty point, a coordinate that is not finite or lies beyond 1e150, or in
a geographic CRS a latitude beyond 90 degrees, read as given before the
projection) are dropped with a warning, and k is
clamped to the number of distinct positions or one fewer than the number
of points, whichever is smaller, and not below 1.
A count given as a number gets a fresh partition, which is not the
partition resolution_profile() or determine_optimal_levels() scored
that count on: those fit their own run, the profile to every row or to a
subsample, and keep the best of their own starts. Pass the
select_resolution() result or the profile itself as k to get the
scored one: the centres of the scored partition are then returned (in
the CRS of points_sf, with attr(, "n_from")), and no k-means is run.
On a profile without an estimate whose centres were fitted to a
subsample, they are those centres refitted to every point by
select_resolution(), with attr(, "refit").
partition says what the seeds minimise. "kmeans" is the sum of
squared distances from the points to their nearest seed, from nstart
random starts by stats::kmeans() (Hartigan-Wong) unless init says
otherwise. The seeds
follow the square root of the point density, so the cells are compact,
smaller where the points are dense, and a cell in a dense place still
holds several times the points of a cell in a sparse place. "density"
weights each point by its local density (the number of points in the disc
that reaches its density_k-th nearest neighbour, over the disc's area)
to the power density_power, and is the default. At the default power
of 1 the seeds follow the point density itself, and the cells are
compact: many small cells where the points are dense, a few large ones
where they are sparse. They
hold about the same number of points each once k is above the number
of dense places (clusters of points). With fewer cells than that a cell
takes in whole clusters, large and small, and the counts are about as
uneven as under "kmeans". The density kind is the best of
nstart starts, each refined by at most 100 steps of Lloyd's iteration
(iter_max sets another limit, and a kept start that was cut off at the
limit is a warning of class "spatialkit_not_converged");
it does not depend on the order of the rows or on the unit of the
coordinates, and points at one location share a cell. A seed can end
with no point at counts from about a fifth of the points up, mostly from
init = "random"; that is a warning of class "spatialkit_empty_cells".
"The partition" in
resolution_profile() gives the details and a comparison of the two
kinds.
The centres lie inside the points, so their own hull is smaller than the
data's. The result carries the convex hull of points_sf as
attr(, "cover"), and build_tessellation() clips the cells to that hull
(grown by 2 percent of its diagonal) when no boundary is passed, so every
point of points_sf falls in a cell.
Examples
library(sf)
set.seed(1)
pts <- st_as_sf(
data.frame(x = 5e5 + runif(100, 0, 1000), y = 5e6 + runif(100, 0, 1000)),
coords = c("x", "y"), crs = 32632
)
seeds <- voronoi_seeds_kmeans(pts, k = 8) # density-weighted, 3 starts
nrow(seeds) # at most 8: one seed per non-empty cluster
#> [1] 8
seeds # the cluster centres, as an sf POINT layer in the points' CRS
#> Simple feature collection with 8 features and 2 fields
#> Geometry type: POINT
#> Dimension: XY
#> Bounding box: xmin: 500197.6 ymin: 5000135 xmax: 500802.6 ymax: 5000911
#> Projected CRS: WGS 84 / UTM zone 32N
#> geometry seed_id method
#> 1 POINT (500596.5 5000605) 1 kmeans
#> 2 POINT (500371.1 5000409) 2 kmeans
#> 3 POINT (500802.6 5000255) 3 kmeans
#> 4 POINT (500316.8 5000797) 4 kmeans
#> 5 POINT (500197.6 5000577) 5 kmeans
#> 6 POINT (500799 5000911) 6 kmeans
#> 7 POINT (500785.6 5000620) 7 kmeans
#> 8 POINT (500513.3 5000135) 8 kmeans
# Plain k-means from 10 random starts.
voronoi_seeds_kmeans(pts, k = 8, partition = "kmeans")
#> Simple feature collection with 8 features and 2 fields
#> Geometry type: POINT
#> Dimension: XY
#> Bounding box: xmin: 500102 ymin: 5000143 xmax: 500813 ymax: 5000897
#> Projected CRS: WGS 84 / UTM zone 32N
#> geometry seed_id method
#> 1 POINT (500145 5000616) 1 kmeans
#> 2 POINT (500813 5000237) 2 kmeans
#> 3 POINT (500786.3 5000897) 3 kmeans
#> 4 POINT (500102 5000222) 4 kmeans
#> 5 POINT (500354.4 5000832) 5 kmeans
#> 6 POINT (500377.9 5000474) 6 kmeans
#> 7 POINT (500502.9 5000143) 7 kmeans
#> 8 POINT (500756 5000585) 8 kmeans