← Back to Documentations

Signature Description Parameters 
include <DataFrame/DataFrameMLVisitors.h>

template<typename T, typename I = unsigned long,
         std::size_t A = 0>
struct  DaviesBouldinIndexVisitor;

// -----------------------------------------

template<typename T, typename I = unsigned long,
         std::size_t A = 0>
using db_index_v = DaviesBouldinIndexVisitor<T, I, A>;
Davies-Bouldin Cluster Validity Index
The Davies-Bouldin index (DB) measures the average similarity between each cluster and its most similar neighbour, where similarity is the ratio of intra-cluster scatter to inter-cluster centroid separation:

For each cluster i:
s(i) = (1/ni) . Σi∈Ci dist(xi, µi) [mean intra-cluster distance]
R(i, j) = (s(i) + s(j)) / d(μi, μi) [cluster similarity ratio]
Di = max_{j != i} R(i, j) [worst-case similarity for i]

DB = (1/k) . Σi Di [index = mean of worst cases]
DB ∈ [0, ∞):
DB = 0: perfect separation (never reached in practice)
Lower: tighter, better-separated clusters — better result
Higher: diffuse or poorly separated clusters — worse result

Unlike Silhouette (which is O(n2)), DB is O(n.k) once centroids are known, making it practical for large datasets or many clusters.

Special cases:
Noise points (label −1 or −2, DBSCAN convention) are excluded from all centroid and scatter calculations.
Singleton clusters: s(i) = 0. The ratio R(i, j) = s(j) / d(µi, µj), which is well-defined as long as the two centroids differ.
Coincident centroids (d(µi, µi) = 0): R(i, j) is set to a large sentinel (std::numeric_limits::max() / 2) so the pathological case dominates Dᵢ and drives DB up — a correct penalty.
Fewer than 2 non-noise clusters: DB = 0 (undefined, same as Silhouette).

The visitor uses the same two-column operator() pattern as SilhouetteScoreVisitor:
column 1 (T): data values (scalar or MD container)
column 2 (long): cluster label per point (−1/−2 = noise)

The distance function (dist) is used for BOTH:
(a) intra-cluster scatter: dist(xi, µi)
(b) centroid separation: dist(µi, µj)
so the metric is consistent throughout. The default matches SilhouetteScoreVisitor: squared Euclidean for scalar T, Euclidean for MD T.

Per-cluster results (scatter si, worst-case ratio Di, centroid μi) are available via accessors for diagnostic use.
References:
  Davies, D.L. and Bouldin, D.W. (1979). "A cluster separation measure",
  IEEE Transactions on Pattern Analysis and Machine Intelligence
  PAMI-1(2): 224–227.
          
explicit
SilhouetteScoreVisitor(distance_func f = default_dist_());

using distance_func =
    std::function<double(const value_type &, const value_type &)>;

inline static distance_func
default_dist_()  {

    if constexpr (! is_md_)
        return ([](const T &x, const T &y) -> double  {
                    const double    d { static_cast<double>(x - y) };

                    return (d * d);
                });
     else
        return ([](const T &x, const T &y) -> double  {
                    double  sum { 0.0 };

                    for (size_type i { 0 }; i < size_type(x.size()); ++i)  {
                        const double    diff {
                            static_cast<double>(x[i]) -
                            static_cast<double>(y[i])
                        };

                        sum += diff * diff;
                    }
                    return (std::sqrt(sum));
                });
}
get_results() The Davies-Bouldin index ∈ [0, ∞). Lower is better.
get_scatter() Per-cluster intra-cluster scatter s(i) = mean dist(point, centroid). Size == number of non-noise clusters.
get_worst_ratio() Per-cluster worst-case similarity ratio Dᵢ = max_{j != i} R(i, j). Size == number of non-noise clusters.
get_centroids() Per-cluster centroids μi. Type is double for scalar T, std::vector for MD T. Size == number of non-noise clusters.
 T: Column data type
I: Index type
A: Memory alignment boundary for vectors. Default is system default alignment
 
static void test_DaviesBouldinIndexVisitor()  {

    std::cout << "\nTesting DaviesBouldinIndexVisitor{ } ..." << std::endl;

    using MyDataFrame = StdDataFrame<unsigned long>;

    constexpr std::size_t   col_s { 100 };

    std::vector<unsigned long>  idx(col_s);

    std::iota(idx.begin(), idx.end(), 0UL);

    MyDataFrame df;

    df.load_index(std::move(idx));

    // Analytics
    //
    {
        df.load_column("x1", std::vector<double>{ 0.0, 2.0, 10.0, 12.0 }, nan_policy::dont_pad_with_nans);
        df.load_column("lbl1", std::vector<long>{ 0, 0, 1, 1 }, nan_policy::dont_pad_with_nans);

        db_index_v<double>  db;

        df.single_act_visit<double, long>("x1", "lbl1", db);

        // DB index
        //
        assert(std::abs(db.get_result() - 0.02) < 1e-9);

        assert(db.get_scatter().size() == 2);
        assert(std::abs(db.get_scatter()[0] - 1.0) < 1e-9);
        assert(std::abs(db.get_scatter()[1] - 1.0) < 1e-9);

        assert(db.get_worst_ratio().size() == 2);
        assert(std::abs(db.get_worst_ratio()[0] - 0.02) < 1e-9);
        assert(std::abs(db.get_worst_ratio()[1] - 0.02) < 1e-9);

        assert(db.get_centroids().size() == 2);
        assert(std::abs(db.get_centroids()[0] - 1.0)  < 1e-9);
        assert(std::abs(db.get_centroids()[1] - 11.0) < 1e-9);
    }

    // Well separated
    //
    {
        df.load_column("x2", std::vector<double>{ 0.0, 0.1, 0.2, 100.0, 100.1, 100.2, 200.0, 200.1, 200.2 }, nan_policy::dont_pad_with_nans);
        df.load_column("lbl2", std::vector<long>{ 0, 0, 0, 1, 1, 1, 2, 2, 2 }, nan_policy::dont_pad_with_nans);

        db_index_v<double>  db;

        df.single_act_visit<double, long>("x2", "lbl2", db);

        // Three clusters very far apart, each tight -> DB close to 0
        //
        assert(std::abs(db.get_result() - 1.33333e-06) < 1e-9);

        assert(db.get_scatter().size() == 3);
        assert(std::abs(db.get_scatter()[0] - 0.00666667) < 1e-8);
        assert(std::abs(db.get_scatter()[2] - 0.00666667) < 1e-8);

        assert(db.get_worst_ratio().size() == 3);
        assert(std::abs(db.get_worst_ratio()[0] - 1.33333e-06) < 1e-9);
        assert(std::abs(db.get_worst_ratio()[2] - 1.33333e-06) < 1e-9);

        assert(db.get_centroids().size() == 3);
        assert(std::abs(db.get_centroids()[0] - 0.1)  < 1e-6);
        assert(std::abs(db.get_centroids()[1] - 100.1) < 1e-6);
        assert(std::abs(db.get_centroids()[2] - 200.1) < 1e-6);
    }

    // Poor separation
    //
    {
        df.load_column("x3", std::vector<double>{ 0, 10, 20, 30, 1, 11, 21, 31 }, nan_policy::dont_pad_with_nans);
        df.load_column("lbl3", std::vector<long>{ 0, 0, 0, 0, 1, 1, 1, 1 }, nan_policy::dont_pad_with_nans);

        db_index_v<double>  db;

        df.single_act_visit<double, long>("x3", "lbl3", db);

        // Centroids: u0=15, u1=16 -> very close, large scatter -> large DB
        //
        assert(std::abs(db.get_result() - 250.0) < 1e-6);

        assert(db.get_scatter().size() == 2);
        assert(std::abs(db.get_scatter()[0] - 125.0) < 1e-6);
        assert(std::abs(db.get_scatter()[1] - 125.0) < 1e-6);

        assert(db.get_worst_ratio().size() == 2);
        assert(std::abs(db.get_worst_ratio()[0] - 250.0) < 1e-6);
        assert(std::abs(db.get_worst_ratio()[1] - 250.0) < 1e-6);

        assert(db.get_centroids().size() == 2);
        assert(std::abs(db.get_centroids()[0] - 15.0)  < 1e-6);
        assert(std::abs(db.get_centroids()[1] - 16.0) < 1e-6);
    }

    // Singleton
    //
    {
        df.load_column("x4", std::vector<double>{ 5.0, 10.0, 12.0 }, nan_policy::dont_pad_with_nans);
        df.load_column("lbl4", std::vector<long>{ 0, 1, 1 }, nan_policy::dont_pad_with_nans);

        db_index_v<double>  db;

        df.single_act_visit<double, long>("x4", "lbl4", db);

        assert(std::abs(db.get_result() - 0.0277778) < 1e-7);

        assert(db.get_scatter().size() == 2);
        assert(std::abs(db.get_scatter()[0] - 0.0) < 1e-9);
        assert(std::abs(db.get_scatter()[1] - 1.0) < 1e-9);

        assert(db.get_worst_ratio().size() == 2);
        assert(std::abs(db.get_worst_ratio()[0] - 0.0277778) < 1e-7);
        assert(std::abs(db.get_worst_ratio()[1] - 0.0277778) < 1e-7);

        assert(db.get_centroids().size() == 2);
        assert(std::abs(db.get_centroids()[0] - 5.0)  < 1e-6);
        assert(std::abs(db.get_centroids()[1] - 11.0) < 1e-6);
    }

    // Noise points
    //
    {
        df.load_column("x5_noise", std::vector<double>{ 5.0, 0.0, 2.0, 10.0, 12.0 }, nan_policy::dont_pad_with_nans);
        df.load_column("lbl5_noise", std::vector<long>{ -1, 0, 0, 1, 1 }, nan_policy::dont_pad_with_nans);
        df.load_column("x5_clean", std::vector<double>{ 0.0, 2.0, 10.0, 12.0 }, nan_policy::dont_pad_with_nans);
        df.load_column("lbl5_clean", std::vector<long>{ 0, 0, 1, 1 }, nan_policy::dont_pad_with_nans);

        db_index_v<double>  db_noise;
        db_index_v<double>  db_clean;

        df.single_act_visit<double, long>("x5_noise", "lbl5_noise", db_noise);
        df.single_act_visit<double, long>("x5_clean", "lbl5_clean", db_clean);

        assert(std::abs(db_noise.get_result() - db_clean.get_result()) < 1e-9);
        assert(std::abs(db_noise.get_centroids()[0] - db_clean.get_centroids()[0]) < 1e-9);
        assert(std::abs(db_noise.get_centroids()[1] - db_clean.get_centroids()[1]) < 1e-9);
        assert(std::abs(db_noise.get_worst_ratio()[0] - db_clean.get_worst_ratio()[0]) < 1e-9);
        assert(std::abs(db_noise.get_worst_ratio()[1] - db_clean.get_worst_ratio()[1]) < 1e-9);
    }

    // Custom distance
    //
    {
        df.load_column("x6", std::vector<double>{ 0.0, 2.0, 10.0, 12.0 }, nan_policy::dont_pad_with_nans);
        df.load_column("lbl6", std::vector<long>{ 0, 0, 1, 1 }, nan_policy::dont_pad_with_nans);

        // Absolute difference: dist(x, y) = |x - y|
        //
        auto                                abs_dist =
            [](const double &x, const double &y) -> double  {
                return (std::abs(x - y));
            };
        DaviesBouldinIndexVisitor<double>   db_def;
        DaviesBouldinIndexVisitor<double>   db_abs { abs_dist };

        df.single_act_visit<double, long>("x6", "lbl6", db_def);
        df.single_act_visit<double, long>("x6", "lbl6", db_abs);

        assert(std::abs(db_def.get_result() - 0.02) < 1e-6);
        assert(std::abs(db_abs.get_result() - 0.2) < 1e-6);

        assert(std::abs(db_def.get_scatter()[0] - 1.0) < 1e-6);
        assert(std::abs(db_def.get_scatter()[1] - 1.0) < 1e-6);
        assert(std::abs(db_abs.get_scatter()[0] - 1.0) < 1e-6);
        assert(std::abs(db_abs.get_scatter()[1] - 1.0) < 1e-6);

        assert(std::abs(db_def.get_worst_ratio()[0] - 0.02) < 1e-6);
        assert(std::abs(db_def.get_worst_ratio()[1] - 0.02) < 1e-6);
        assert(std::abs(db_abs.get_worst_ratio()[0] - 0.2) < 1e-6);
        assert(std::abs(db_abs.get_worst_ratio()[1] - 0.2) < 1e-6);

        assert(std::abs(db_def.get_centroids()[0] - 1.0) < 1e-6);
        assert(std::abs(db_def.get_centroids()[1] - 11.0) < 1e-6);
        assert(std::abs(db_abs.get_centroids()[0] - 1.0) < 1e-6);
        assert(std::abs(db_abs.get_centroids()[1] - 11.0) < 1e-6);
    }
}

C++ DataFrame