0
$\begingroup$

I have a dataset that contains initial and ending points of car trips:

|driver_id|latitude_init|longitude_init|latitude_end|longitude_end|time | 
|---------|-------------|--------------|------------|-------------|---- |
|    1    |     ...     |      ...     |     ...    |     ...     | ... |
|    1    |     ...     |      ...     |     ...    |     ...     | ... |
|    2    |     ...     |      ...     |     ...    |     ...     | ... |
|    3    |     ...     |      ...     |     ...    |     ...     | ... |
|    3    |     ...     |      ...     |     ...    |     ...     | ... |
|    3    |     ...     |      ...     |     ...    |     ...     | ... |

I would like to cluster or find similar drivers. By similar drivers I mean they take similar time to finish similar trips.

I can't just look at the speeds because the data is for real cars in cities so initial and final points influence a lot.

In the following example points x_n are latitude/longitude pairs and ~x_n means lat/long close to x_n.

  • driver 1 goes from point a_1 to a_2 in 1h
  • driver 2 goes from point ~a_1 to ~a_2 in ~1h and b_1 to b_2 in 2h
  • driver 3 goes from point ~b_1 to ~b_2 in ~2h

I would like to infer that, like in recommender systems:

===> driver 1, driver 2 and driver 3 are similar.

===> sim(driver_1, driver_2) is high.

Of course the example above is oversimplified and in reality a driver could have anywhere from 1 or infinite examples in the dataset.

So far I thought about two ways to approach this problem:

  • Create a similarity function that takes a pair of drivers. For each pair of rides from (one from each driver), checks how similar the init/end points are. For similar trips, calculate the mean time difference weighted by init/end similarity.

This method is not good because it is computationally intensive, a lot of times drivers will not have similar init/end points and no there is no transitivity (a~b b~c -> a~c).

  • Separate lat/lon in bins and compute a sparse matrix where each row is a driver_id and columns are combinations of lat/lon bins for init and end, filled with the mean times:
|driver_id|a_1_to_a_1|a_1_to_a_2| ... |b_1_to_b_1|b_1_to_b_2|b_2_to_a_1| ... |
|---------|----------|----------| ... |----------|----------|----------| ... |
|    1    |     0    |    1h    | ... |     0    |     0    |     0    | ... |
|    2    |     0    |   ~1h    | ... |     0    |    2h    |     0    | ... |
|    3    |     0    |     -    | ... |     0    |   ~2h    |     0    | ... |

Then, perform SVD or calculate cosine similarity on this matrix. This method is not optimal because it introduces some unnecessary discretization and therefore loss of information. Also, I don't know how to treat the unexistent combinations (zeroes in my example).

One top of that, I don't know how I can add other potential features to this, such as vehicle type (motorcycles might be best for some types of trips), hour of the day (traffic impacts), day of the week etc.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.