0
$\begingroup$

Let's say we have a taxi hailing application and we have history of passenger rides including pickup position, destination position, time and date. Now the passenger is going to order next ride and I'd like to recommend him destination based on his current position and time. Basically, the algorithm should pick a destination from the list of previous destinations (and maybe pickups) based on a "similarity".

One possible approach is to pick the nearest history point in the space of features (pickup coordinates, day of week, hour of day, ..) but intuitively it feels that some of the features are more important than the others so it would be nice to learn some weights. I have no idea how.

$\endgroup$
1
0
$\begingroup$

One way to approach this problem would be with association rule learning.

An association rule is a rule of the form $X \implies Y$ which associates a set $X$ with a set $Y$. $X$ contains feature realizations on which the association is based, while $Y$ contains a target realization that the association maps to.

Example

\begin{align}X&=\{pickup=A,sex=0,age=30-39,...\}\\Y&=\{destination=G\}\end{align}

note that I encoded the locations for $pickup$ and $destination$, these should be discrete values, how granular this information should be is a design decision.

These rules are learned based on a data base $D$, in your case the history of past taxi rides. The single entries are often referred to as transaction $t$, forming the set of all transactions $T$. Each transaction in $D$ needs to contain values for the features you're regarding, so leaning on the example a ride definitely has a pickup and destination location as well as information on the passenger like the sex and the age.

Based on $D$ we can now form a big collection of association rules which can differ in length. Our most basic rules can be of length 1, meaning that the size of $X$ is 1. \begin{align}\{pickup=A\}&\implies\{destination=B\}\\ \{pickup=A\}&\implies\{destination=C\}\\ \{pickup=A\}&\implies\{destination=D\}\\ \vdots\end{align}

Analogously, rules of length 2 could additionally contain either $age$ or $sex$ realizations, rules of length 3 can contain both etc. .

But how do we know which rules to apply?

Two basic concepts are those of support of a set and the confidence in a rule.
The support of a set gives an impression how well it is supported by $D$, that is how frequently it appears in our data. The support of a set $X$ is defined as the proportion of transactions it occurs in

$$supp(X)=\frac{|\{t\in T; X \subseteq t\}|}{|T|}$$

Using the concept of support, we can now compute the confidence in a given rule $X\implies Y$ as follows

$$conf(X\implies Y)=\frac{supp(X \cup Y)}{supp(X)}. $$

This gives us an indication of how often the association $X \implies Y$ has been true given our data in $D$.

Finally, given a passenger with the feature vector $X^*$ we can consult such an association rule system by querying it for rules of arbitrary length matching $X^*$ and recommend destinations based on highest confidence.

Generating a rule system

As you might already suspect, the devil lies in the details here. For example how to tackle the exhaustive task of generating rules and evaluating them. There are many algorithms for this and there's still research being done in this setting, you might have to do some reading on your own. When I first learned about association rules, I think we were only taught the apriori algorithm , but there might be better approaches for your individual problem.

Further reading

Friedman, J., Hastie, T., & Tibshirani, R. (2001). The elements of statistical learning (Vol. 1, No. 10), Chapter 14.2 (p.485). New York: Springer series in statistics. [Michael Hahsler, Annotated

Annotated Bibliography on Association Rule Mining

$\endgroup$

Your Answer

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

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