# 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.

• DBSCAN is pretty much defined around solving this problem.
– Sycorax
Feb 8, 2018 at 23:10
• @Sycorax DBSCAN was my first tought, but since I use the dense regions to cluster the image (choosing more anchors from the dense regions), I want to determine the dense regions without clustering. Feb 9, 2018 at 7:32
• I guess I don't understand how DBSCAN isn't a solution. The DBSCAN core points are your anchors, and the neighbors to core points are the points clustered using the anchors. It exactly solves your problem in a single step.
– Sycorax
Feb 9, 2018 at 15:27

Here is a simple solution:

1. Define a global distance $r$.

2. 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$.

3. 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.

• +1. Note that you will bias the samples towards the denser points even for $0\lt\alpha\le 1$. The case $\alpha=0$ is uniform sampling.
– whuber
Feb 10, 2018 at 13:57
• @whuber, sure, I am aware of that and I will modify my answer per your comment. Feb 10, 2018 at 15:44

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.

• I thought about k-means and dbscan, but I want to determine the dense regions in order to cluster the points in the data set - so I want to determine the dense regions before clustering. Otherwise the whole process becomes unnecessary. Feb 9, 2018 at 7:34
• Normalize your data and plot histogram. This should help you determine dense region(s). Feb 9, 2018 at 12:01