Gap Statistic and Davies-Bouldin Index

[BradKML]

Describe the solution you'd like
Borrowing from https://towardsdatascience.com/cheat-sheet-to-implementing-7-methods-for-selecting-optimal-number-of-clusters-in-python-898241e1d6ad
The Clustering Visualizers should also include this two algos
https://www.scikit-yb.org/en/latest/api/cluster/index.html

P.S. There are more algorithms out there that does similar things, but they are less blogged about

• https://www.semanticscholar.org/paper/Comparison-of-Internal-Clustering-Validation-for-H%C3%A4m%C3%A4l%C3%A4inen-Jauhiainen/441b8745311c9a849bd7e41a9bf36d2cfdc133d4/figure/0
• https://www.semanticscholar.org/paper/Understanding-of-Internal-Clustering-Validation-Liu-Li/f504e1c8fd0fb7c19c73a5759a5fa369131c573e/figure/6

Is your feature request related to a problem? Please describe.
It exists for R, but not necessarily for Python https://www.semanticscholar.org/paper/NbClust%3A-An-R-Package-for-Determining-the-Relevant-Charrad-Ghazzali/4c8e0d4b898d34672b2ea426cba380c18a28068c

[bbengfort]

@BrandonKMLee thank you so much for contributing to Yellowbrick; I think your suggestion is a very good one! We'd be very happy to review a PR with an implementation of the algorithms. We have an internal implementation of distortion_score that is part of the KElbow visualizer, but I could see us creating a yellowbrick/cluster/metrics.py package to implement these additional cluster scorers and consolidate them with the distortion score. Are you up for taking a crack at it?

[BradKML]

Would kindly do so, with reference to this picture.

[BradKML]

The index for Dasvi-Bouldin exists for sklearn https://scikit-learn.org/stable/modules/clustering.html#davies-bouldin-index
Xie-Beni Index exists in https://github.com/99991/FuzzyClustering/blob/master/cvi.py
S_Dbw exists in https://github.com/fanfanda/S_Dbw/blob/master/S_Dbw.py

Other indexes exist in

• https://github.com/online-ml/river-extra/tree/main/river_extra/metrics/cluster
• https://github.com/clslabMSU/clustGUI/blob/master/internal_validation.py

Also for more references for later:

• http://www2.uaem.mx/r-mirror/web/packages/clusterCrit/vignettes/clusterCrit.pdf
• http://dx.doi.org/10.3390/w12051372
• http://csjournals.com/IJCSC/PDF6-2/53.%20Kp2.pdf

[pkaf]

I can contribute to this task. It would be great if you can point me to the script where I can update the desired metrics. I can start with a metric you can suggest.

[BradKML]

@pkaf these two will be a good start

• https://github.com/DistrictDataLabs/yellowbrick/tree/develop/yellowbrick/cluster
• https://github.com/DistrictDataLabs/yellowbrick/tree/develop/tests/test_cluster

[pkaf]

Thanks @BrandonKMLee. Shall I do gap statistics first and move slowly through the list?

[pkaf]

@bbengfort newbie here, apologies in advance if I don't fully understand the philosophy of yellowbrick project.

For metrics like gap statistics, or for that matter any metric with a knee, we can use existing KElbowVisualier class (with minimal code change) no?
But metrics like davies-bouldin, which are not exclusively concave or convex rather has a minima will be special case. It would need its own optimizing routine equivalent to KneeLocator.

Would it make sense to break this project into two parts
a. include all concave/convex metrics into KElbowVisualiser
b. tackle remaining individually? Ideally, code can be refactor to have a dedicated class to identify optimal number of clusters of which KneeLocator/KElbow will be a child class?

[pkaf]

Here is a flawed solution to davies-bouldin score

[BradKML]

@pkaf if you are doing Davis-Bouldin, can I also help out with Xie-Beni, SD and S_Dbw?

[pkaf]

Sure. Let's hear @bbengfort et al on my prior points. That will help lay out the plan.

[bbengfort]

@pkaf I think you have the broad strokes correct - Yellowbrick tries to focus on visual diagnostics and model context. The important thing isn't so much the optimization mechanism for detecting the knee (though we do appreciate the kneed algorithm for making it so clear), but that we show what an optimization method would have selected in the context of other values of K.

So it seems that all concave/convex methods would be associated with KElbow for this reason and davies-bouldin would either have to have its own visualizer or we'd have to figure out how to represent it in the context of an elbow based visualization (for example, perhaps it could replace fit-time as an alternative mechanism for understanding distortion score).

[BradKML]

@pkaf how did you make your visualizations, also @bbengfort it would be good to implement something similar to KElbow (the same base layout) but with a different set of indicators instead of the "elbow" (local minima or maximas for hierarchical clustering).

[bbengfort]

@BrandonKMLee that makes sense to me!

[BradKML]

@bbengfort Right now this idea came to mind: https://www.geeksforgeeks.org/find-indices-of-all-local-maxima-and-local-minima-in-an-array/ at the same time I wonder what the progress is for @pkaf so that the local minima detection can be used

[bbengfort]

@BrandonKMLee I think that algorithm seems simple and effective; it might also be cool to use topology plots if you have a third dimension available.

[pkaf]

not much progress on my end @BrandonKMLee. Please feel free to take it away if you or someone more keen

[BradKML]

Sorry to ask @pkaf but can I observe the changes in https://github.com/pkaf/yellowbrick ? I can't seem to find the difference.

def findLocalMaximaMinima(n, arr):
 
    mx, mn = [], []

    if(arr[0] > arr[1]): mx.append(0)
    if(arr[0] < arr[1]): mn.append(0)

    for i in range(1, len(arr)-1):
	
        if(arr[i-1] > arr[i] < arr[i + 1]): mn.append(i)
        if(arr[i-1] < arr[i] > arr[i + 1]): mx.append(i)
 
    if(arr[-1] > arr[-2]): mx.append(len(arr)-1)
    if(arr[-1] < arr[-2]): mn.append(len(arr)-1)
 
    return mx, mn