I'm building a maritime navigation graph based on trajectory data came from AIS.
So there are a lot of points on the map (hundreds of gigabytes) and what I need is to reduce the amount of points in order to build a graph. But I need to do it preserving relative density, assuming that the points with higher density have more significance than lower density points. Moreover, I want to preserve higher density near the coastline. So, each point has the following attributes as input:
- coordinates
- density
- desired min and max density
My first idea was to randomly remove the points whose density doesn't fit [min, max] range, but the quality was quite poor. A smart approach should have preserved the points lying on density peaks, but this one didn't.
I have also tried to apply HDBSCAN clustering to the points and use cluster centroids as vertices instead, but the problem with this approach is that HDBSCAN algorithm collapses lines into distinct clusters, which makes the results even worse than they were in the previous approach.
So I wondering if there is a better way to reduce the density of points on a map?
You can use this:
Gaussian Mixture Models (GMM): Apply GMM to model the distribution of your data. GMM is a probabilistic model that represents a mixture of Gaussian distributions. This can help identify clusters and their densities in a more flexible way than traditional clustering algorithms. Once you have the GMM, you can sample points from the distribution, giving more weight to areas with higher density.
Density-Based Spatial Clustering of Applications with Noise (DBSCAN): DBSCAN is a density-based clustering algorithm that groups together points that are close to each other and have a sufficient number of neighbors. It may be better suited for your task than HDBSCAN. Adjust the parameters to find the right balance between identifying clusters and preserving the density peaks.
Kernel Density Estimation (KDE): KDE estimates the probability density function of your data. You can use KDE to create a continuous density surface, and then sample points from this surface. KDE can be useful for preserving the density information while reducing the number of points.