Efficient way to determine dense regions in a dataset For a dataset of 3-dimensional points like in the image below, what is the most efficient way to determine the dense regions? 
I want to sample points form the dataset, extracting more points from the dense regions. 
I will use the sampled points as anchors, around which I'll cluster the dataset.

 A: Why not directly use cluster analysis like k-means and see which samples are dense? Identify the optimal number of clusters using WSS and elbow technique.
You can also reduce it to low dimensional space using Principal Component Analysis and identify the dense regions. 
A: Here is a simple solution: 


*

*Define a global distance $r$.

*For each of your point $x_i$, put a ball centering at $x_i$, the ball is with radius $r$, then find the number of points inside the ball, denote it as $n_i$.

*After you obtain all $n_i$, sample each point $x_i$  with probability $\propto  n_i^\alpha$, where $\alpha>0$.
The essential idea here is that $n_i$ measures the local density of $x_i$, because it is the number of local neighbors of $x_i$. So, the bias of the sampling is: the point with larger $n_i$ has a higher probability being sampled, i.e., denser regions are more likely to be sampled.
As a final note, if you want to further exaggerate the sampling bias, increase the parameter $\alpha$. 
PS: when you set $\alpha=0$, it degenerates to uniform random sampling.
