Flattening Hierarchical Clusters

I have code written against the Python hcluster package, which uses this approach to find the smallest flat-clustering. I can share this code, if you would like. You may not want the smallest flat-clustering, though. Perhaps you want a sample of flat clusters at various thresholds.

Here is how I find the smallest flat-clustering. I do a line-search against the flattening threshold t. The minimum of the interval is t small enough to have every cluster included. The maximum of the interval is t large enough to have only one cluster. You then do a line search to find the value of t that has more than one cluster, but the minimum number of clusters. I do a line search with a maximum of 15 steps.

Here is the code:

def fcluster_with_count(Z, t):
    clusters = hcluster.fcluster(Z, t)
    clustercnt = len(frozenset(clusters))
    return clusters, clustercnt

def narrowest_fcluster(docs, Z):
    """
    Try to find the t that gives the smallest number of flat clusters.
    We do this using a line search.
    """

    tlow = 0.
    thigh = 2.
    cnt = 0

    cnt_to_clusters = {}

    clusters, clustercnt = fcluster_with_count(Z, thigh)
    cnt_to_clusters[clustercnt] = clusters
    print >> sys.stderr, thigh, clustercnt
    assert clustercnt == 1

    clusters, clustercnt = fcluster_with_count(Z, tlow)
    cnt_to_clusters[clustercnt] = clusters
    print >> sys.stderr, tlow, clustercnt
    assert clustercnt > 1

    while cnt < 15:
        tmid = (tlow + thigh) / 2.
        clusters, clustercnt = fcluster_with_count(Z, tmid)
        cnt_to_clusters[clustercnt] = clusters
        print >> sys.stderr, tmid, clustercnt

        if clustercnt == 1:
            thigh = tmid
        else:
            tlow = tmid

        cnt += 1