Estimation of min_samples for DBSCAN
Since the elements in each row grows, sorting the row only to take the k smallest is a bit wasteful. Using numpy.partition should always be faster:

sorted_row_t = np.partition(row_nonzero, k)[:k]


This is not needed with the examples you give, the row is already an array and flattened:

flat_row = np.squeeze(np.asarray(row))


Similarly, you can just use numpy.nonzero, no need to flatten the flattened row again:

row_nonzero = flat_row[np.nonzero(frow)]




However, this whole for loop can be done entirely in numpy:


First, mask all zeros by setting them to numpy.nan:

D = np.where(D == 0, np.nan, D)

Get the k smallest elements of each row. Since numpy.nan is not smaller than any number it will only appear at the beginning if (almost) the whole row was zeros:

k_smallest = np.partition(D, k, axis=1)[:, :k]

Compute the median of each row, and then the median of the median, ignoring numpy.nan values using numpy.nanmedian:

kmedian_dist = np.nanmedian(np.nanmedian(k_smallest, axis=1))



The first two steps can even be pulled outside of the for k in ... loop, which will save some more time. In that case we have to sort the whole array, though, because numpy.partition does not guarantee that the values are sorted, only that the k smallest values are in the slice up to k. Since K seems to be max(D_sym.shape) in all cases anyway, this should not make such a big difference. It will if the k at which the for loops stops is small enough, though, so you will have to test this.

There's no need to break and then immediately return afterwards, just return directly.

Python has an official style-guide, PEP8. It recommends using 4 spaces as indentation (not 3) and spaces after commas.



In summary, this should do the same as your code:

def autoselect_minsamps_graipher(D_sym, eps, K, kmedian_thresh):
    D = np.sort(np.where(D_sym == 0, np.nan, D_sym), axis=1)
    kmedian_dist_prev = 0
    for k in range(2, K):
        kmedian_dist = np.nanmedian(np.nanmedian(D[:,:k], axis=1))
        if abs(kmedian_dist - kmedian_dist_prev) &lt;= kmedian_thresh:
            return k
        kmedian_dist_prev = kmedian_dist
    return 10 # fall back value


This is faster than your implementation, but suffers from similar scaling behaviour:

n       autoselect_minsamps_orig    autoselect_minsamps_graipher
100     0.028 s                     0.0088 s
1000    0.32 s                      0.064 s
10000   9.5 s                       3.6 s




You could also make timing your code easier by using a decorator:

from time import perf_counter

class Timer:
    def __init__(self, name=""):
        self.name = ""
        self.start = None

    def __enter__(self):
        self.start = perf_counter()

    def __exit__(self, *args, **kwargs):
        delta = perf_counter() - self.start
        print(f"{self.name} finished in {delta:.2f} seconds")


Or, if you are stuck on Python 2:

from time import time

class Timer:
    def __init__(self, name=""):
        self.name = ""
        self.start = None

    def __enter__(self):
        self.start = time()

    def __exit__(self, *args, **kwargs):
        delta = time() - self.start
        print "{} finished in {:.2f} seconds".format(self.name, delta)


Which you can use like this:

D = euclidean_distances(X,X)
eps = 0.25
kmedian_thresh = 0.005
K = num_training_examples

with Timer(f"autoselect_minsamps_orig, K = {K}"):
    min_samples = autoselect_minsamps_orig(D, eps, K, kmedian_thresh)


Note that I used time.perf_counter, which is better suited for timing, but which is Python 3 only.