1
$\begingroup$

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.

enter image description here

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

$\endgroup$
3
  • 1
    $\begingroup$ I know that this code comes from a very popular blog post. But that doesn't mean this is good code... (min_samples=1 means that you aren't doing DBSCAN, but it's effectively single-linkage clustering, why use geopy.distance when you have haversine in sklearn already, etc.) but because you copied the code, you should at least attribute it correctly... $\endgroup$ Jul 14, 2017 at 8:27
  • $\begingroup$ @Viral If your question has been answered to your satisfaction, you can accept an answer by clicking the check mark under the voting arrows. $\endgroup$ Jul 18, 2017 at 16:06
  • $\begingroup$ @kadiologist Thank you for your answer. It was helpfull $\endgroup$
    – Viral
    Jul 18, 2017 at 16:38

3 Answers 3

0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ I want each event to be separated. What if I went to same location after 30 days?This will then show my previous event and these event together. That is why time is important. $\endgroup$
    – Viral
    Jul 11, 2017 at 16:57
  • $\begingroup$ @Viral Please edit your question accordingly, then. $\endgroup$ Jul 11, 2017 at 17:00
  • $\begingroup$ @kadiologist I apologise. I have now included full description. If it helps with code $\endgroup$
    – Viral
    Jul 11, 2017 at 17:25
  • $\begingroup$ @Viral I've updated my answer. $\endgroup$ Jul 11, 2017 at 21:05
1
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ @benoitScanchez I have used DBCAN algorithm. I have now included photo of my code. I was trying to include the third dimention that is time but I am not sure how to include and use it. $\endgroup$
    – Viral
    Jul 11, 2017 at 17:28
  • 1
    $\begingroup$ Don't compute distance like that. On latitude, longitude, time this is utter nonsense to do. On latitude and longitude you need to use Haversine distance (because Earth is not flat, you know), and 1 mile is not the same as one second. So your units will be completely messed up this way. $\endgroup$ Jul 14, 2017 at 8:19
  • $\begingroup$ I've rephrased my answer using the Haversine distance. It requires that your implementation of DBScan allows using a custom metric. $\endgroup$ Jul 14, 2017 at 16:41
  • $\begingroup$ @Anony I suspect everyone can agree that such calculations might be "nonsense" when interpreted as Euclidean distances--but in some cases they might actually be useful in statistical analyses. That's really the question to address. $\endgroup$
    – whuber
    Jul 14, 2017 at 17:09
  • $\begingroup$ @whuber by now, it can be sometimes useful, but the first version did not, lacking any normalization or haversine. $\endgroup$ Jul 16, 2017 at 7:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.