Non hierarchical clustering
PortfolioOptimisers.KMeansAlgorithm — Type
struct KMeansAlgorithm{__T_rng, __T_seed, __T_kwargs} <: AbstractNonHierarchicalClusteringAlgorithmPartitions 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 ofrngseeded with it, sorngdoes not advance and every call draws the same values. Ifnothing, the draws come fromrngitself.
kwargs: Keyword arguments forClustering.kmeans.
Constructors
KMeansAlgorithm(; rng::Random.AbstractRNG = Random.default_rng(), seed::Option{<:Integer} = nothing, kwargs::NamedTuple = (;)) -> KMeansAlgorithmKeywords correspond to the struct's fields.
Validation
- If
kwargsholdsweights, it must be a non-emptyAbstractVector. The constructor does not check its length.Clustering.kmeansraises aDimensionMismatchfor a wrong length when it runs.
Examples
julia> KMeansAlgorithm()KMeansAlgorithm rng ┼ Random.TaskLocalRNG: Random.TaskLocalRNG() seed ┼ nothing kwargs ┴ @NamedTuple{}: NamedTuple()Related
AbstractNonHierarchicalClusteringAlgorithmClustersEstimatorclusteriseget_k_clusters_from_algresolve_rngClustering.kmeans
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.
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
- Estimate the similarity matrix
Sand the distance matrixDfromXwithcor_and_dist, undercle.deandcle.ce. Refuse each asset that the reader could not estimate withassert_distance_reader_rows. Then refuse any otherNaNinDwithassert_no_nan_distance. - Pass
Dand the algorithmcle.algtooptimal_number_clusters(cle.onc, cle.alg, D), which returns the partitionresand its countk. No other clustering runs, becauseresis the partition at the selected count. - Return
Clusters(; res = res, S = S, D = D, k = k). The fieldPkeeps its default,nothing, because the clustering ran onDitself.
Arguments
cle: The clustering estimator, with a non-hierarchical algorithm.X: The data matrix, with one row per observation and one column per asset whendims = 1.dims: Dimension along which the computation runs.kwargs...: Keyword arguments forcor_and_dist.
Validation
- No diagonal entry of
DisNaN. Raises aDistanceReaderRefusalErrorthat names the columns of the assets that the reader could not estimate. A fit catches it and drops those assets. Dholds no otherNaN. Raises aDomainErrorthat names the firstNaNcell, a pair, throughassert_no_nan_distance. An undetermined pair gives it, and an asset with zero variance does not, because the first check refuses itsNaNrow. Without the check,Clustering.kmeansrefuses theNaNas 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
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.