Non hierarchical clustering

PortfolioOptimisers.KMeansAlgorithm — Type
struct KMeansAlgorithm{__T_rng, __T_seed, __T_kwargs} <: AbstractNonHierarchicalClusteringAlgorithm

Partitions assets into k groups by Lloyd's algorithm, with no dendrogram.

Runs Clustering.kmeans over the columns of the distance matrix. Each asset is the point of its distances to every asset, so two assets fall in one cluster when their distances to the rest of the universe are similar. The result is a flat partition with no tree, so no later step can cut it at a different k.

Clustering.kmeans alternates two steps over all the points: it assigns each point to its nearest centre, and it moves each centre to the mean of its points. [124] states that alternation for a quantiser of one real variable, in Method I of Section VI. [125] names k-means and states the problem for points in $N$ dimensions, but it moves a mean after each point, one point at a time. The work that first states the alternation over all the points in $N$ dimensions was not read.

The algorithm draws random starting centres, so the type has the fields rng and seed. resolve_rng combines them when the algorithm runs, so a stated seed makes a run reproducible and the caller does not make a generator.

kwargs reaches Clustering.kmeans unchanged

The call splats kwargs as it is. The constructor checks only that a weights entry is a non-empty AbstractVector, and it does not check the length. Clustering.kmeans needs one weight per point, which here is one weight per asset.

factory never writes observation weights into kwargs. An observation weight has no meaning here, because every step after ce reads an assets x assets matrix.

Fields

  • rng: Random number generator.
  • seed: Optional seed. If set, the draws come from a copy of rng seeded with it, so rng does not advance and every call draws the same values. If nothing, the draws come from rng itself.

Constructors

KMeansAlgorithm(;    rng::Random.AbstractRNG = Random.default_rng(),    seed::Option{<:Integer} = nothing,    kwargs::NamedTuple = (;)) -> KMeansAlgorithm

Keywords correspond to the struct's fields.

Validation

  • If kwargs holds weights, it must be a non-empty AbstractVector. The constructor does not check its length. Clustering.kmeans raises a DimensionMismatch for a wrong length when it runs.

Examples

julia> KMeansAlgorithm()KMeansAlgorithm     rng ┼ Random.TaskLocalRNG: Random.TaskLocalRNG()    seed ┼ nothing  kwargs ┴ @NamedTuple{}: NamedTuple()

Related

References

  • [124] S. P. Lloyd. Least squares quantization in PCM. IEEE Transactions on Information Theory 28, 129–137 (1982). Section VI, Method I. The original source of this formulation was not found. The formulation follows this work and is not checked against the original.
  • [125] J. MacQueen. Some methods for classification and analysis of multivariate observations. In: Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Statistics (1967); pp. 281–297. Sections 1 and 2.1, for the name and the problem in $N$ dimensions.
source
PortfolioOptimisers.clusterise — Method
clusterise(cle::ClustersEstimator{<:Any, <:Any,
                                  <:AbstractNonHierarchicalClusteringAlgorithm, <:Any},
           X::MatNum; dims::Int = 1, kwargs...)

Cluster assets with a non-hierarchical algorithm and return a Clusters result.

Estimates the similarity and distance matrices from X, then passes D to optimal_number_clusters, which selects k and returns the partition at k.

Algorithm

  1. Estimate the similarity matrix S and the distance matrix D from X with cor_and_dist, under cle.de and cle.ce. Refuse each asset that the reader could not estimate with assert_distance_reader_rows. Then refuse any other NaN in D with assert_no_nan_distance.
  2. Pass D and the algorithm cle.alg to optimal_number_clusters(cle.onc, cle.alg, D), which returns the partition res and its count k. No other clustering runs, because res is the partition at the selected count.
  3. Return Clusters(; res = res, S = S, D = D, k = k). The field P keeps its default, nothing, because the clustering ran on D itself.

Arguments

  • cle: The clustering estimator, with a non-hierarchical algorithm.
  • X: The data matrix, with one row per observation and one column per asset when dims = 1.
  • dims: Dimension along which the computation runs.
  • kwargs...: Keyword arguments for cor_and_dist.

Validation

  • No diagonal entry of D is NaN. Raises a DistanceReaderRefusalError that names the columns of the assets that the reader could not estimate. A fit catches it and drops those assets.
  • D holds no other NaN. Raises a DomainError that names the first NaN cell, a pair, through assert_no_nan_distance. An undetermined pair gives it, and an asset with zero variance does not, because the first check refuses its NaN row. Without the check, Clustering.kmeans refuses the NaN as a weight, and names neither the cell nor the cause.

Returns

  • res::Clusters: The partition, the similarity matrix, the distance matrix and the number of clusters.

Related

source

References

[124]
S. P. Lloyd. Least squares quantization in PCM. IEEE Transactions on Information Theory 28, 129–137 (1982).
[125]
J. MacQueen. Some methods for classification and analysis of multivariate observations. In: Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Statistics (1967); pp. 281–297.