Trait Cost

Source

pub trait Cost {
    // Required methods
    fn cost(&mut self, cluster: Cluster) -> f64;
    fn num_points(&self) -> usize;

    // Provided methods
    fn total_cost(&mut self, clustering: &Clustering) -> f64 { ... }
    fn approximate_clusterings(&mut self) -> Vec<(f64, Clustering)> { ... }
    fn optimal_clusterings(&mut self) -> Vec<(f64, Clustering)> { ... }
    fn price_of_hierarchy(&mut self) -> (f64, Vec<Clustering>) { ... }
    fn greedy_hierarchy(&mut self) -> Vec<(f64, Clustering)> { ... }
    fn price_of_greedy(&mut self) -> (f64, Vec<Clustering>) { ... }
}

Expand description

A trait for cost-functions for a class of clustering-problems.

TODO: Specify contract for trait-implementors.

Required Methods§

Source

fn cost(&mut self, cluster: Cluster) -> f64

Get the cost of a cluster.

This can be memoized via data in self. The cluster will never contain an index higher than self.num_points()-1 and will never be empty.

Source

fn num_points(&self) -> usize

Get the number of points that must be clustered.

This must never exceed MAX_POINT_COUNT.

Provided Methods§

Source

fn total_cost(&mut self, clustering: &Clustering) -> f64

Get the total cost of a clustering.

Source

fn approximate_clusterings(&mut self) -> Vec<(f64, Clustering)>

Quickly calculate a not-necessarily-optimal clustering.

This can speed up the search for an optimal clustering by pruning the search-tree earlier.

For the returned vector, vec[k] must be a tuple containing the approximate clustering for level k, along with the total_cost of that clustering. Here, vec[0] can have an arbitrary score (usually 0.0) and arbitrary clustering (usually empty).

Source

fn optimal_clusterings(&mut self) -> Vec<(f64, Clustering)>

Calculate an optimal k-clustering for every 0 ≤ k ≤ self.num_points().

For the returned vector, vec[k] must be a tuple containing the optimal clustering for level k, along with the total_cost of that clustering. Here, vec[0] can have an arbitrary score (usually 0.0) and arbitrary clustering (usually empty).

Source

fn price_of_hierarchy(&mut self) -> (f64, Vec<Clustering>)

Calculate the price-of-hierarchy of the clustering-problem, together with an optimal hierarchy.

A hierarchical clustering is a set of nested clusterings, one for each possible value of k. The cost-ratio of level k in the hierarchy is its total cost divided by the cost of an optimal k-clustering.

The cost-ratio of the hierarchy is the maximum of the cost-ratios across all its levels. The price-of-hierarchy is the lowest-possible cost-ratio across all hierarchical clusterings.

For the returned vector, vec[k] is the cluster for level k, defaulting to the empty clustering for k==0. Note that the algorithm constructs this hierarchy in reverse, starting with every point in a singleton-cluster.

Source

fn greedy_hierarchy(&mut self) -> Vec<(f64, Clustering)>

Calculate a greedy hierarchical clustering.

The greedy-hierarchy calculates a hierarchical clustering by starting with each point in a singleton-cluster, and then repeatedly merging those clusters whose merging yields the smallest increase in cost. Ties are broken arbitrarily.

For the returned vector, vec[k] is a tuple containing the greedy clustering for level k, along with the total_cost of that clustering.

Here, vec[0] has a score of 0.0 and an empty clustering. Note that the clusterings are constructed in reverse, as we start with every point in a singleton-cluster.

Source