DBSCAN & Hierarchical Clustering

    Machine Learning · Advanced

    Definition

    DBSCAN groups dense regions and marks outliers; hierarchical clustering builds a tree of merges.

    Find clusters of any shape without fixing k.

    Diagram

    dense ●●●dense ●●noise ○

    Flowchart

    Pick eps and minPtsCore points have ≥ minPts neighborsExpand clusters from coresRest are noise

    Example: Neighbor count

    pts, eps = [1, 1.2, 1.4, 5, 9], 0.5
print([sum(abs(p - q) <= eps for q in pts) - 1 for p in pts])

    Output: [2, 2, 2, 0, 0]

    Complexity

    DBSCAN ~O(n log n) with an index

    Key points

    • No need to choose k
    • Struggles with varying densities

    Interview questions

    K-Means vs DBSCAN?

    K-Means needs k and finds round clusters; DBSCAN finds arbitrary shapes and noise.

    More Machine Learning topics

    What is Machine LearningLinear RegressionLogistic RegressionDecision Trees & Random Forest