INPUT ($D$, $K$):
I have a symmetrical "distance" matrix $D$ of size $N \times N$ which tells me how distant one object is from another. Function used for calculating the distances is not a metric (doesn't satisfy triangle inequality). The values in $D$ are from $[0,1]$ where 0 means 2 objects are identical, and 1 means they are the furthest possible.
I also know that I would like to obtain $K$ clusters.
I would like to obtain $K$ clusters, where every clustroid has a small average distance to every other guy within the same cluster. Ideally with no silly clusters with 1-2 elements.
Which clustering method would you use? K-means requires feature vectors, which I don't have, Spectral Clustering assumes that the distance function is a metric. I thought of using DBSCAN, but it doesn't allow $K$ as input. I could tune the hyperparams to get the $K$ I want, but I was wondering if there is a clear better choice. $N$ can range from 5 000 to 20 000, and $K$ is smaller than 1 000, so I assume there will be no issues with CPU or MEM.