---
title: "Computing Place Centroids"
author: "Kumar Mankala"
date: "June 20, 2016"
output:
  html_document:
    fig_height: 5
    fig_width: 7
    highlight: tango
    theme: readable
---
I would like to share an approach on how, given a test checkin coordinates (x,y), we can narrow down the possible places  the checkin could belong to (to about 400 places with 85+% accuracy). As I don't know how to write a report, I am re-using some content from Alexandru Papiu's report.

### Read and Clean:

Let's load the required packages and read in the data:

```{r, message = FALSE, warning = FALSE}
library(readr) #reading in the data
library(dplyr) #dataframe manipulation
fb<-readr::read_csv("../input/train.csv")
```

Let's take a sample of 5000 places and related events. Split this into 90% training set and 10% validation/test set

```{r}
fb[fb$place_id %in% sample(fb$place_id,5000),]-> s.fbp
s.fbp[s.fbp$time > 700000,]->s.fbp.tst
s.fbp[s.fbp$time <= 700000,]->s.fbp.trn

#Clean up the training dataset
#Remove places that sneaked into val/test data but are not in training data
#Basically, ensuring test data contains only places present in the training data
s.fbp.tst[(s.fbp.tst$place_id %in% s.fbp.trn$place_id),]->s.fbp.tst

#Take some samples from the test set; Obviously, we are not going to test all the test data
s.fbp.tst[s.fbp.tst$row_id %in% sample(s.fbp.tst$row_id,100),] -> sample
```

Now here is the important step. How can we determine the centroids from checkins with varying accuracy. It is not quite clear whether higher accuracy number means greater accuracy or lower accuracy. Here is where we can take a leaf from Center of Mass. Treating accuracies as mass, the formula becomes quite simple. BAsically, it becomes a weighted average of the x and y where weights are accuracies.  

```{r}
#Compute place centroids using Center of Mass approach
s.fbp.trn %>% 
  group_by(place_id) %>% 
  mutate(
    x.c=(sum(x/accuracy)/sum(1/accuracy)+sum(x*accuracy)/sum(accuracy))/2, 
    y.c=(sum(y/accuracy)/sum(1/accuracy)+sum(y*accuracy)/sum(accuracy))/2) -> s.fbp.trn
    
#Extract the places with centroids and number of checkins (the checkins are only for just-in-case)
s.fbp.trn %>% 
  group_by(place_id,x.c,y.c) %>% 
  summarise(checkins=n()) -> places
```

Now that we have computed approxmiate place centroids, we can do some testing on how to narrow down the possible place ids for a given checkin
```{r}
#Let's define some variables. I took the std devs of x and y from the base data. std is the number of standard deviations  
correct=0;
for (rec in sample$row_id)
  {
    sample[sample$row_id==rec,]->tst
    places %>% filter(x.c<tst$x+1 & x.c>tst$x-1 & y.c<tst$y+0.15 & y.c>tst$y-0.15) -> s.places
    
    if (tst$place_id %in% s.places$place_id) 
    {
      correct=correct+1 
    }
  }
  #Print the number of places (amongst the sampled) that were correctly 'sub-setted' for places. 
  #This number tests how good is our Center of Mass approximation
  print(correct)
```

### Further Directions:

The accuracy seems to be 85+% on an average. Let's calculate the benefit of doing this. We are on an average narrowing down from 100K places to about 400. From these 400, we can do a quick KDE lookup for Accuracy and time (week, weekend and hour).

The below approach seems promising...

1. Compute (rough) place_id coordinates using any classical mechanical approach (I used the center of mass concept for example - in this case I treated accuracy as the mass or 'weightage' for the point (x,y))

2. Next, given a test check-in event, find the subset of places the check-in can possibly fall in. I used the centroids from step 1 with some std. dev. for this, assuming the spread is normal. This turns out to be a good assumption. I was getting about 85+ accuracy on this. I was getting about 400 places the check-in possibly falls under.

3. From that list of ~400 places, compute KDEs on (x,y,accuracy -> call this accuracy_kde) and (week, week day and hour -> call this time_kde) separately. For some reason combining them into single KDE is yielding a lower accuracy.

4. Derive the probabilities (you get two probabilities - one for accuracy and the other for time KDE). You can be creative here on how to order the probabilities. The places associated with top three probabilities give you the answer...
 
Feel free to fork this script and explore these ideas more.

Thanks for reading!