Rank-Order Distance based clustering - normalized distance

Question

Recently I have implemented the algorithm proposed in https://pdfs.semanticscholar.org/efd6/4b7641bea8ca536f4e179be6e2dd25d519d6.pdf (if there is a problem in access to that, I can rewrite the main ideas here). I'm in no way sure, that my implementation is correct, but let's assume it is. The authors propose Cluster-level normalized distance as $$ D^N(C_i,C_j) = \frac{1}{\phi (C_i,C_j)} d(C_i,C_j), $$ where $$ \phi (C_i,C_j)= \frac{1}{|C_i|+|C_j|} \sum \limits_{a \in C_i \cup C_j} \frac{1}{K} \sum \limits_{k=1}^K d(a,f_a(k)). $$ Now the main idea of this part is that $\frac{1}{\phi (C_i,C_j)}$ should normalize the proposed distance, such that we should merge clusters $C_i$ and $C_j$ if $D^N(C_i,C_j) < 1$ (there are other conditions, I have no trouble with). I don't have access to the algorithm used for their face representation so I'm using different ones. I have tried it on my personal database of faces while using face representation I got from PCA, HOG, LBP, some deep networks and others. I have then calculated adjusted rand index and was a bit disappointed by the results. However, after choosing the criteria for normalized distance to be 2, the results were significantly better on all face representations(from around 0.3 ARI to 0.89 ARI). Is this approach justifiable? I'm aware that this is an "engineering" approach, but the normalization isn't perhaps the best one there can be? Should I rather try to come up with better normalization, than randomly choosing parameters?

Answer 1

If I understand correctly, you're concerned how the threshold for clustering should be chosen. You are already experimenting with different face representations, each of which entails different quantification of the similarity between faces. Varying the threshold is the same as introducing a scaling factor in these similarity measures, so the choice of threshold is already arbitrary at least insofar as the choice of face representation is arbitrary. If you wish to define something less arbitrary, you could look at the distribution of similarities between each face and all the other faces and compute a cut-off based on the shape of that distribution.