Come riconoscere un nodo interno che ha tutti i suoi punti di contenimento in un cluster in un albero a sfere quando si esegue l'algoritmo k-means?

Question

Sto ora leggendo il libro Data mining: strumenti e tecniche di apprendimento pratico della macchina terza edizione. Nella sezione 4.8 clustering, viene illustrato come utilizzare k-d trees o ball trees per migliorare le prestazioni per k-means algorithm.

Dopo aver costruito l'albero della palla con tutti i punti dati, cerca tutti i nodi foglia per vedere quale centro di raggruppamento preselezionato centrale i punti in esso sono vicini. A volte, la regione rappresentata dal nodo interno superiore rientra interamente nel dominio di un singolo centro di cluster. Quindi non è necessario attraversare i nodi figlio e tutti i punti data possono essere elaborati in un colpo solo.

La domanda è, quando si implementa la struttura dati e l'algoritmo, come possiamo decidere se la regione che fa riferimento a un nodo interno cade in un singolo centro di cluster?

In uno spazio bidimensionale o tridimensionale, questo non è difficile. Possiamo vedere se tutte le midperpendicolari di ogni coppia nei centri del cluster attraversano la regione facendo riferimento al nodo interno.

Ma negli spazi dimensionali superiori, come riconoscerlo? Esiste una metodologia generale per questo?

Answer 1

È necessario considerare le distanze massime e minime.

Se la distanza minima di un oggetto spaziale (ad esempio, una sfera di raggio r) in tutti gli altri mezzi è maggiore della distanza massima da uno, tutti gli oggetti all'interno del contenitore apparterranno a tale media. Perché se

maxdist(mean_i, container) < min of all j != i mindist(mean_j, container) 

quindi in particolare per qualsiasi oggetto nel contenitore

dist(mean_i, obj_in_container) < min of all j != i dist(mean_j, obj_in_container) 

Vale a dire l'oggetto apparterrà a significare io

Le distanze minime e massime per sfere e rettangoli possono essere calcolate in modo semplice in dimensioni arbitrarie. Tuttavia, nelle dimensioni superiori, il mindist e il maxdist diventano abbastanza simili e la condizione sarà raramente valida. Inoltre, fa una grande differenza se il tuo albero è ben strutturato (vale a dire piccoli contenitori) o mal strutturato (contenitori sovrapposti).

k-d-trees sono utili per le operazioni di sola lettura in memoria. Per gli inserimenti si comportano piuttosto male. R * -trees sono qui molto meglio. Inoltre, la strategia di divisione migliorata di R * -trees ripaga, perché genera più caselle rettangolari rispetto alle altre strategie.

Answer 2

Ho una soluzione da solo, ma non è una buona opinione secondo me.
Per gli spazi k-dimensionale, la metà -perpendicolare di due punti è un iperpiano. Calcoliamo ogni coppia di midperpendicolare di tutto il centro di raggruppamento.
Quando si affronta il problema precedente, vediamo un nodo. Può specificare una regione ---- un'ipersfera nello spazio. Per prima cosa troviamo il centro di raggruppamento più vicino al punto centrale dell'ipersfera P. Poi, in modo iterativo per ogni midperpendicolare (un iperpiano) di ogni coppia di centri con uno dei due è il precedente, calcoliamo la distanza euclidea tra il punto P e la midperpendicolare. Se la distanza è minore del raggio dell'ipersfera, essa subisce l'incrocio dell'ipersfera con la midperpendicolare. Quindi questo nodo interno può contenere punti dati che potrebbero non appartenere al centro di raggruppamento sopra, le interruzioni di iterazione. Se l'iterazione termina senza break, possiamo dire che è giusto mettere tutti i punti dati contenuti in questo nodo al centro di raggruppamento sopra in un colpo senza dubbio.