Image Clustering by date and location

Question

I have Latitude ,longitude and timestamp of image. I want to cluster these image according to detect events. For instance I went to Paris for 4 days then london 3 days and so on. So I want to detect cluster of Paris data and after london.I want each event to be seperated. How can I use this Latitude ,longitude and timestamp together to make cluster? I have done with DBSCAN algorithm but could note merge the time in it.Look at popular Gboeing code if it helps to understand problem.

I have CSV file in my code which contain following thing ,lon,date,city,country 51.4812916,-0.4510112,05/14/2014 09:07,West Drayton,United Kingdom

Answer 1

This problem allows for a deterministic approach, because you know which places you went to and they're cleanly separated in space and time.

• For each area you visited, choose a pair of geographic coordinates, such as the coordinates of a major landmark or the center of the city.
• For each time you visited an area, choose a timestamp, such as the time midway between when you arrived and left.

Now loop through the images and assign each image to the area with the closest coordinates, using a simple measure of geographic distance such as great-circle distance. To disambiguate between multiple visits to the same area, assign the image to the visit with the nearest time; you can measure temporal distance by just counting the number of seconds between times.

Answer 2

A straightforward approach:

1. Cluster the data by haversine, as you already do.

2. For each cluster, cluster only this subset by time only.

3. Merge noise of all clusters.

Answer 3

Use 3 dimensional points say $(x;y;t$) with $x$ and $y$ being latitude and longitude and $t$ is time. For example, if you use the Haversine distance $h$ on Earth, then you can combine it with time by a formula such as

$$d((x,y,t),(x',y',t'))=\sqrt{\left(\frac{h((x;y),(y,y')}{h_0}\right)^2+\left(\frac{t-t'}{t_0}\right)^2}$$

$h_0$ and $t_0$ are the scaling coefficients. You must choose them carefully. Assume 1 day is the average duration for a stay, and 10 kilometres is the average geographical range of a stay (and $h$ is expressed in kilometres). Then it makes sense using $t_0=1$ day and $h_0=10$ km.

A note about the choice of the clustering algorithms :

You want to use DBSCAN which is ok. KMeans wouldn't be a great choice since you don't know the number of clusters $K$.

I would recommend a density based algorithm (DBSCAN is one of them). Generally density based algorithms work as long as the dimensionality is small (3 is small) and the clusters look like "grapes".

My favourite is the mean shift : the complexity is a bit more than KMeans : $\log(N)N^2$ instead of $\log(N)KN$ but still reasonable. There are variants that will make it more or less clever, more or less fast... (I know DENCLUE is an advanced mean shift for example).