Problema Cluster

[mauro1388]

salve a tutti
devo fare un progetto e ho un problema:
ho delle città con coordinate (latitudine,longitudine)

mi è stato chiesto di raggrupparle in cluster (per vicinanza). In pratica vari gruppi, contenenti le città "vicine". Posso passare un parametro (es. 10 km, in ogni gruppo ci sono le città vicine 10 km)

mi è stato consigliato di usare il clustering gerarchico http://it.wikipedia.org/wiki/Clustering

e per fare questa cosa devo usare viste materializzate (o tabelle)

solo che non ho idea, non so nemmeno da dove iniziare.

è un progetto che ho praticamente finito, mi manca solo quest'ultima parte

grazie dell'aiuto

 

[borgo italia]

ciao se non ho capito male
credo che per prima cosa sia da calcolare la distanza tra i punti.
prova questa funzione (l'ho buttata giù al volo anche scopiazzando, è un pezzo che non uso la trigonometria) mettendo delle coordinate reali e verificando se (salvo arrotondamenti) di da la distanza giusta.
cioè calcolando la distanza su una cartina tra due punti ed inserendo le loro coordinate

<?php
//latA, lonA, latB, lonB = latitudine e longitudine espressa in gradi decimali
function trova_distanza($latA, $lonA, $latB, $lonB){
	define("RAGGIO", 6371);// raggio terrestre in km
	define("PIGRECO", 3.1415927);
	//conversione degli angoli decimali in radianti
	$latA= PIGRECO * $latA /180;
	$lonA= PIGRECO * $lonA /180;
	$latB= PIGRECO * $latB /180;
	$lonB= PIGRECO * $lonB /180;
	//calcolo l'angolo compreso
	$phi=abs($lonA-$lonB);
	//calcolo lato trinagolo
	$lato=acos(sin($latA)*sin($latB) + cos($latA)*cos($latB)*cos($phi));//questo può essere il punto da riguardare
	//calcolo la distanza sulla superficie
	$d=$lato*RAGGIO;
	return number_format($d, 3);//distanza in km con tre cifre decimali
}
?>

poi proveremo (se riesco) il raggruppamento

 

[mauro1388]

ciao se non ho capito male
credo che per prima cosa sia da calcolare la distanza tra i punti.
prova questa funzione (l'ho buttata giù al volo anche scopiazzando, è un pezzo che non uso la trigonometria) mettendo delle coordinate reali e verificando se (salvo arrotondamenti) di da la distanza giusta.
cioè calcolando la distanza su una cartina tra due punti ed inserendo le loro coordinate

<?php
//latA, lonA, latB, lonB = latitudine e longitudine espressa in gradi decimali
function trova_distanza($latA, $lonA, $latB, $lonB){
	define("RAGGIO", 6371);// raggio terrestre in km
	define("PIGRECO", 3.1415927);
	//conversione degli angoli decimali in radianti
	$latA= PIGRECO * $latA /180;
	$lonA= PIGRECO * $lonA /180;
	$latB= PIGRECO * $latB /180;
	$lonB= PIGRECO * $lonB /180;
	//calcolo l'angolo compreso
	$phi=abs($lonA-$lonB);
	//calcolo lato trinagolo
	$lato=acos(sin($latA)*sin($latB) + cos($latA)*cos($latB)*cos($phi));//questo può essere il punto da riguardare
	//calcolo la distanza sulla superficie
	$d=$lato*RAGGIO;
	return number_format($d, 3);//distanza in km con tre cifre decimali
}
?>

poi proveremo (se riesco) il raggruppamento

Si questa funzione già l'ho implementata e funziona

il problema è raggruppamento. Ho N città,ho un paramentro (es 10 km) e devo creare gruppi con città che stan vicino al massimo di 10 km.

ho pensato a k-means però li gli passo il numero di gruppi che voglio e lui me li suddivide, ma nn voglio questo. voglio appunto che mi crei lui i gruppi in base alle distanze

 

[alessandro1997]

L'algoritmo dovrebbe essere simile a questo. Creerà un gruppo per ogni città:

<?php
// http://snipplr.com/view/2531/
function distance($lat1, $lng1, $lat2, $lng2, $miles = true)
{
    $pi80 = M_PI / 180;
    $lat1 *= $pi80;
    $lng1 *= $pi80;
    $lat2 *= $pi80;
    $lng2 *= $pi80;
     
    $r = 6372.797;
    $dlat = $lat2 - $lat1;
    $dlng = $lng2 - $lng1;
    $a = sin($dlat / 2) * sin($dlat / 2) + cos($lat1) * cos($lat2) * sin($dlng / 2) * sin($dlng / 2);
    $c = 2 * atan2(sqrt($a), sqrt(1 - $a));
    $km = $r * $c;
     
    return ($miles ? ($km * 0.621371192) : $km);
}

$groups = array();

// supponendo che $cities contenga le città

foreach ($cities as $city) {
    $groups[$city['id']] = array();
    $cities2 = $cities;

    foreach ($cities2 as $city2) {
        if ($city2['id'] == $city['id']) {
            continue;
        }

        if (distance($city['latitudine'], $city['longitudine'], $city2['latitudine'], $city2['longitudine'], false) <= 10) {
            $groups[$city['id']][] = $city2['id'];
        }
    }
}

return $groups;
?>

Il problema è che richiede una discreta potenza di calcolo: se le città sono tante lo script potrebbe venire eseguito per minuti interi. Se davvero vuoi fare una cosa del genere devi implementare un sistema di cache, ed eseguire i calcoli in background, magari con un cronjob.

 

[borgo italia]

pignolo

$r = 6372.797

non sai che la terra è schiacciata (e si schiaccia sempre di più)

 

[alessandro1997]

Non è mia la funzione. Comunque: http://it.wikipedia.org/wiki/Raggio_terrestre.

 

[borgo italia]

ciao
http://www.spadamar.com/2007/12/cal...ica-tra-due-punti-della-superficie-terrestre/
wiki delle volte esagera usare il dato al 3 decimale o senza decimali è lo stesso. l'errore che si commette è sempre superiore alla precisione del dato del raggio, quindi ininfluente

 

[alessandro1997]

ciao
http://www.spadamar.com/2007/12/cal...ica-tra-due-punti-della-superficie-terrestre/
wiki delle volte esagera usare il dato al 3 decimale o senza decimali è lo stesso. l'errore che si commette è sempre superiore alla precisione del dato del raggio, quindi ininfluente

Adesso non ci mettiamo a fare i sapientini: hai iniziato tu. ernacchi

 

[mauro1388]

Grazie a tutti per avere risposto!!!!!!!!

Alla fine ho risolto modificando questo algoritmo jonisalonen.com/2012/k-means-clustering-in-mysql/

Non fa proprio la stessa cosa ma con qualche (moltissime) modifica ho risolto


grazie ancora

 

[mauro1388]

cioa a tutti
ho risposto anche ieri sera ma non so perchè mi han cancellato il messaggio

ho un altro problema simile:

ho dei prezzi e li devo raggruppare dato un parametro.
Es parametro = 200€, i gruppi saranno formati dai prezzi con differenza <=100€

es 200, 250, 5000, 5020, 100, 8000

gruppo1: 100,200,250
gruppo2: 5000,5020
gruppo3: 8000

Come posso fare? il problema del primo post l'ho risolto incasinando un algoritmo, e diventa infattibile adattarlo.
Idee?

grazie

 

[borgo italia]

ciao
non uppare, il tuo post sul raggruppamento è
http://forum.mrwebmaster.it/mysql/31178-algoritmo-raggruppamento.html
eventualmente specificalo meglio li

 

[mauro1388]

ah ok, mi avete creato voi un altro topic... ( forse sono stordito io che ieri sera anziche rispondere ne ho creato un altro...)

ok vado li :byebye: