Module onc 

Optimal Number of Clusters (ONC): partition a correlation matrix with k-means, choosing the number of clusters by silhouette quality.

Not from AFML. References: López de Prado, Machine Learning for Asset Managers (2020), Chapter 4, §4.4 (Snippet 4.1, base clustering; Snippet 4.2, higher-level clustering); López de Prado and Lewis (2019), Detection of false investment strategies using unsupervised learning methods; Rousseeuw (1987) for the silhouette.

The algorithm:

1. Convert correlations to distances d_ij = sqrt((1 - rho_ij) / 2) (inputs clamped to [-1, 1]) and represent each item by its row of that distance matrix.
2. Run k-means for every k from 2 to max(N - 1, 2), repeat times each, and keep the partition with the highest t-statistic of the silhouettes, mean(S) / std(S); equal t-statistics go to the higher mean silhouette. Each run is one k-means++ initialisation (the greedy variant scikit-learn uses) followed by Lloyd’s algorithm, as Snippet 4.1 runs scikit-learn’s KMeans(n_init=1) n_init times.
3. Compute that t-statistic per cluster. If more than two clusters score below the average, pool their members, re-run the whole procedure on them, and keep the result only if its mean cluster t-statistic beats that of the clusters it replaced (check_improve_clusters).

Conventions:

• The input is an N x N correlation matrix, N >= 2; rows and columns are items in the same order. Symmetry and a unit diagonal are not checked.
• Negative correlation is distance, not similarity: rho = -1 is maximally far apart. Take absolute correlations first if a series and its mirror image should cluster together.
• Member indices in OncResult::clusters and the order of OncResult::silhouette_scores refer to the original row order.
• The result has at least two clusters unless every row of the matrix is the same (for example all ones), which gives one cluster of every item.
• One random stream, seeded with DEFAULT_SEED (or the seed given to get_onc_clusters_with_seed), drives every initialisation, so results are deterministic.
• ONC is a random search: the partition kept is the best of repeat k-means runs per k, and a partition with a high t-statistic may be a k-means local optimum that few initialisations reach. On clean structure any seed finds the same answer. On real data it need not: on the 30 breast-cancer features of tests/fixtures/onc, repeat = 50 returns one of a handful of partitions depending on the seed, all of them coarsenings of the same eight groups. Compare a few seeds, and raise repeat, before reading much into a particular partition. Cost grows at least as N^3 (every k, repeat times, quadratic silhouettes), plus the recursion.

use nalgebra::DMatrix;
use openquant::onc::{get_onc_clusters, OncError};

// Two blocks of three: 0.8 within a block, 0.1 across.
let block = |i: usize| i / 3;
let corr = DMatrix::from_fn(6, 6, |i, j| {
    if i == j {
        1.0
    } else if block(i) == block(j) {
        0.8
    } else {
        0.1
    }
});

let result = get_onc_clusters(&corr, 3)?;
let mut found: Vec<Vec<usize>> = result.clusters.values().cloned().collect();
found.sort();
assert_eq!(found, vec![vec![0, 1, 2], vec![3, 4, 5]]);
assert_eq!(result.silhouette_scores.len(), 6);
assert!(result.silhouette_scores.iter().all(|s| *s > 0.5));

Structs

OncResult

Partition found by get_onc_clusters.

Enums

OncError

Errors returned by get_onc_clusters.

Constants

DEFAULT_SEED

Seed of the random stream get_onc_clusters uses.

Functions

check_improve_clusters

Keep the re-clustered partition only if its mean cluster t-stat beats the mean t-stat of the clusters that were re-clustered (MLAM Snippet 4.2); otherwise keep the old partition.

get_onc_clusters

Partition the items of a correlation matrix with ONC (MLAM §4.4, Snippets 4.1–4.2).

get_onc_clusters_with_seed

get_onc_clusters with the seed of its random stream given explicitly.