1

I'm writing an app that continuously monitors user location 24 hours a day using a mobile phone with readings every 5-30 mins (about 50-300 readings a day).

How do I cluster readings and extract user significant locations taking in account the following requirements:

  • The output must be a chronological list of visited places. I.e if the user is at home at morning and evening this are two reported locations. And I don't need to find a correlation between this "two locations"
  • Location readings accuracy can be variable and not very good. Some readings can be from GPS and others from triangulated cell towers or wifi networks.
  • Not too complex in terms of CPU/Memory
  • Not complex to implement or existing basis in Java is a plus.
Thomas Owens
  • 79,623
  • 18
  • 192
  • 283
lujop
  • 111
  • 2
  • How would you want treat travel between these locations? Is all travel to be filtered out? – NiklasJ Mar 01 '16 at 10:28
  • @NiklasJ Points that are considered traveling between locations (and not accuracy errors) ideally had to be preserved as minor points – lujop Mar 01 '16 at 14:16
  • 1
    [K-Means](https://en.wikipedia.org/wiki/K-means_clustering) is a commonly used clustering algorithm. It is also quite easy to implement by yourself without having dependencies on libraries. Not posting as an answer because it's too short and I have nothing to add. – rwong Mar 05 '16 at 21:44
  • 1
    @rwong - k-means involves knowing how many clusters you expect. I've suggested hierarchical clustering as it builds clusters without having to guess the number of clusters beforehand. – user62575 May 15 '16 at 08:37

2 Answers2

1

What really matter is time, coordinate (longitude & latitude), and places details. If you get the coordinate and places location in JSON format, then you'll need to parse the JSON data using JSONObject class. See tutorial on JSON parsing at http://www.tutorialspoint.com/android/android_json_parser.htm.

Each time your app retrieved user data, extract coordinates and places details. Then, write them to database of related user. For time, you'll need to write script that will know what time is morning or evening.

Adam Zuckerman
  • 3,715
  • 1
  • 19
  • 27
Thor Dan
  • 19
  • 2
1

How about this.

You have a series of data points as [x,y,t] triples - where and when.

Lots of the (x,y) points will be close to each other. If they are, it generally means that the user's at a place and their GPS is generating noise. So you need to classify readings as being part of a larger group. If they are far apart, that indicates travel.

Check out dendrograms and hierarchical clustering for info on how to group x-y data into trees. Complete Linkage Clustering might be a good choice. The low points on the tree are closer to street addresses; the higher points cluster by neighbourhoods, the top clusters to cities, etc.

You walk your tree looking for a threshold of separation. Eg, if two nodes are 100 miles apart, then you definitely want to count that as two locations. If they are 10 feet apart, then that's one location. So you use your tree to get your distinct set of locations.

You might want to consider the size of the group. One reading with no neighbours is probably taken while travelling -- say, half-way along a motorway -- so might not count for your application. Many close locations indicates the user staying on one spot.

Lastly, why not ask foursquare what is at the centre of the cluster, and get a nice user-friendly description?

user62575
  • 285
  • 2
  • 6