Fare $k$-means, dbscan e clustering gerarchico si basano tutti su metriche (pseudo)?

Question

Mi sembra che i metodi di clustering $k$-means, dbscan e clustering gerarchico funzionano tutti sulle misure di distanza $d$ che sono (pseudo) metriche, ovvero soddisfano i seguenti requisiti: $$ d(x,x)=0 $$ $$ d(x,y) = d(y,x) $$ $$ d(x,z) \leqslant d(x,y) + d(y,z) $$

Mi chiedo se questi algoritmi funzionano anche su misure di distanza tra due datapoint che non soddisfano tali requisiti, ad esempio non soddisfacendo la disuguaglianza del triangolo?

Answer 1

$k$-means nella sua forma standard utilizza la distanza euclidea. Ciò è necessario perché altrimenti i centroidi che rappresentano in modo ottimale i cluster non sarebbero i mezzi e il nome$k$- i mezzi non sarebbero giustificati. Purtroppo oggigiorno molti autori usano il termine$k$-significa qualcosa di più generale che coinvolge altri tipi di distanze, ma questo è un uso fuorviante della terminologia.

In linea di principio è possibile utilizzare metodi basati correttamente sulla distanza come dbscan e clustering gerarchico di collegamento singolo, medio o completo (ma non il metodo di Ward, che come $k$-means si basa sulla distanza euclidea) con differenze generali che non soddisfano la disuguaglianza del triangolo. Se questo è appropriato dipende dalla situazione specifica e dalla diversità. Sospetto che dbscan possa produrre risultati difficili da interpretare, perché si basa sui quartieri vicini e il concetto di quartiere diventa strano se è possibile che$d(x,z)=100$ ma $d(x,y)=d(y,z)=0.1$ così che $x$ e $z$ entrambi sono in un vicino quartiere di $y$ma sono estremamente lontani l'uno dall'altro. Detto questo, alcune differenze che violano la disuguaglianza del triangolo lo fanno solo in modi piuttosto lievi.