Generare punti casuali distribuiti come città? - algoritmo, casuale, analisi dei cluster

Come si può generare dire 1000 punti casuali con una distribuzione come quella di città in es. Ohio?
Temo di non poter definire precisamente "distribuito come le città"; centri distribuiti uniformemente + piccole nuvole gaussiane sono facili ma ad hoc.
Aggiunto: deve esserci una famiglia di distribuzioni 2D con un parametro di clustering che può essere variato per abbinare un determinato set di punti?

risposte:

Forse puoi dare un'occhiata a Walter Christaller "s Teoria dei luoghi centrali. Immagino che ci debba essere un generatore da qualche parte, oppure puoi cucinare da solo.

Inizia con un modello delle caratteristiche dell'acqua nel tuoarea target (o crearne una, se è per un luogo immaginario), quindi raggruppare le città vicino agli incroci fluviali, lungo le sponde del lago, agli incroci lago-fiume. Quindi fare autostrade immaginarie che collegano quelle città principali. Ora cospargere alcune città intermedie lungo quelle autostrade a una distanza ragionevole, preferendo essere vicino a incroci nelle autostrade. Ora cospargere alcune piccole città attraverso gli spazi vuoti.

I cluster gaussiani con cluster di dimensioni di Poisson funzionano abbastanza bene.

Problema: generare punti casuali che si raggruppano più o meno come determinate città, diciamo negli Stati Uniti.

sottoproblemi:
a) descrivere i cluster con righe di numeri, in modo che "il cluster A sia come il cluster B" si semplifica in "clusternumbers (A) è come" clusternumbers (B) ".
Eseguendo N = 100 e 1000 punti attraverso fcluster in basso, con ncluster = 25, si ottiene

N 100 ncluster 25: 22 + 3  r 117
sizes: av 4     10   9   8   7   6   6   5   5   4   4   4 ...
radii: av 117  202 198 140 134  64  62  28 197 144 148 132 ...

N 1000 cluster 25: 22 + 3  r 197
sizes: av 45  144 139 130  85  84  69  63  43  38  33  30  ...
radii: av 197  213 279 118 146 282 154 245 212 243 226 235 ...

b) trovare una combinazione di generatori casuali con 2 o 3 parametri che può essere variato per generare cluster diversi.
I cluster gaussiani con le dimensioni dei cluster di Poisson possono abbinare abbastanza bene i cluster delle città:

def randomclusters( N, ncluster=25,  radius=1, box=box ):
""" -> N 2d points: Gaussian clusters, Poisson cluster sizes """
pts = []
lam = eval( str( N // ncluster ))
clustersize = lambda: np.random.poisson(lam - 1) + 1
# poisson 2:  14  27  27  18   9   4  %
# poisson 3:   5  15  22  22  17  10  %
while len(pts) < N:
u = uniformrandom2(box)
csize = clustersize()
if csize == 1:
pts.append( u )
else:
pts.extend( inbox( gauss2( u, radius, csize )))
return pts[:N]


# Utility functions --

import scipy.cluster.hierarchy as hier

def fcluster( pts, ncluster, method="average", criterion="maxclust" ):
""" -> (pts, Y pdist, Z linkage, T fcluster, clusterlists)
ncluster = n1 + n2 + ... (including n1 singletons)
av cluster size = len(pts) / ncluster
"""
# Clustering is pretty fast:
# sort pdist, then like Kruskal"s MST, O( N^2 ln N )
# Many metrics and parameters are possible; these satisfice.
pts = np.asarray(pts)
Y = scipy.spatial.distance.pdist( pts )  # N*(N-1)/2
Z = hier.linkage( Y, method )  # N-1, like mst
T = hier.fcluster( Z, ncluster, criterion=criterion )
clusters = clusterlists(T)
return (pts, Y, Z, T, clusters)

def clusterlists(T):
""" T = hier.fcluster( Z, t ) e.g. [a b a b c a]
-> [ [0 2 5] [1 3] ] sorted by len, no singletons [4]
"""
clists = [ [] for j in range( max(T) + 1 )]
for j, c in enumerate(T):
clists[c].append( j )
clists.sort( key=len, reverse=True )
n1 = np.searchsorted(  map( len, clists )[::-1], 2 )
return clists[:-n1]

def radius( x ):
""" rms |x - xmid| """
return np.sqrt( np.mean( np.var( x, axis=0 )))
# * 100  # 1 degree lat/long ~ 70 .. 111 km

In java questo è fornito attraverso new Random().nextGaussian(). Poiché la fonte java è disponibile, puoi guardarla:

synchronized public double nextGaussian() {
// See Knuth, ACP, Section 3.4.1 Algorithm C.
if (haveNextNextGaussian) {
haveNextNextGaussian = false;
return nextNextGaussian;
} else {
double v1, v2, s;
do {
v1 = 2 * nextDouble() - 1; // between -1 and 1
v2 = 2 * nextDouble() - 1; // between -1 and 1
s = v1 * v1 + v2 * v2;
} while (s >= 1 || s == 0);
double multiplier = StrictMath.sqrt(-2 * StrictMath.log(s)/s);
nextNextGaussian = v2 * multiplier;
haveNextNextGaussian = true;
return v1 * multiplier;
}
}

Tracciare 30000 case usando

x = r.nextGaussian() * rad/4 + rad;
y = r.nextGaussian() * rad/4 + rad;

cede questa bellissima città: