Can you use nearest neighbors with a KD tree to build a distance matrix that is sparse, in that distances to all but the nearest neighbors of a point are (near-)infinite? Yes, this again has an additional parameter (neighborhood size), just as BIRCH has its threshold. I suspect you will not be able to improve on having another, approximating, parameter. You do not need to set n_clusters to a fixed value for BIRCH. You only need to provide another clusterer, which has its own parameters, although you should be able to experiment with different "global clusterers".