Notes from reading the below paper.
A framework to discover place of interests (POIs).
Two levels of clustering are used.
First, user location points are grouped using a time-based clustering
technique which discovers stay points while dealing with missing
location data. The second level performs clustering on the stay
points to obtain stay regions. A grid-based clustering algorithm
has been used for this purpose.
1. Location Point – GPS coordinates along with time.eg. [46.6N, 6.5E], [16:34:57]
2. Stay Point – cluster of location points. Represented using the coordinates of the centroid of the cluster and the time moments when the user arrived and left the stay point.eg. [46.6N, 6.5E], [16:34:57], [17:50:12]
3. Stay Region – a cluster of stay points (from several days) with the same semantic meaning. Represented using the coordinates of the centroid of the cluster and the minimum and maximum coordinates of the stay points in the cluster. [46.6N, 6.5E], [46.595N, 46.599N], [6.498E, 6.502E]. Hence this can be represented by a rectangle centered at the centroid of the cluster whose size depends on the min and max coordinates.
(In this paper, stay region and place of interest are synonymous.)
Finger print based methods for location point detection:
These use data from GSM and Wifi sensors as opposed to geometry based methods that use GPS sensors. But exact location cannot be obtained.
Time based method for stay points:
Dmax – 200 to 300 metresTmin – time at a location – 20 to 40 minutesTmax – time between locations
Clustering algorithms for stay regions:
To estimate stay regions from stay points, couple of clustering algorithms are used.
1. k-means or variants
2. density based method (DBSCAN) – disadvantage: merges stay points with different semantic meaning in the same clusters.
3. grid based method (this performs the best)