Skip to main content
Uber logo

Schedule rides in advance

Reserve a rideReserve a ride

Schedule rides in advance

Reserve a rideReserve a ride
Data / ML

Gleaning Insights from Uber’s Partner Activity Matrix with Genomic Biclustering and Machine Learning

December 7, 2017 / Global
Featured image for Gleaning Insights from Uber’s Partner Activity Matrix with Genomic Biclustering and Machine Learning

At Uber, machine learning plays a central role in improving user experiences across our apps. Given the scale and scope of our business, we often need to think creatively about how we design these systems. For instance, when developing our partner activity matrix, a new tool for personalizing driver experiences based on aggregate usage trends, we found inspiration in a biomedical technique for visualizing genomes (genomic biclustering).

Using biclustering, we can visualize diversity in driver partner patterns by expressing each partner’s choice of times to drive: for example, one driver might prefer weekday commute hours and take a midday break; another might prefer weekend nights, leaving time for their job during the week; and yet another might prefer weekday afternoons when their children are in school. The universe of possible driving patterns is limitless, and so describing this diversity in a compact but rich way helps us improve the Uber experience with all driver partner preferences in mind, not just an average use case.

In this article, we introduce our partner activity matrix, a new tool that leverages biclustering and machine learning to better understand the diversity of driver experiences on the app to help us tailor our products for their preferences.  

 

Introducing Uber’s Partner Activity Matrix

One way to visualize these patterns is through what we call a “partner gene expression matrix” or more specifically, a partner activity matrix. Inspired by an analogy of genomics in which gene expression is visualized by a matrix with each gene corresponding to a column and each individual to a row, the partner activity matrix is a matrix in which each column corresponds to a minute of the week and each row to a driver partner, with each entry in the matrix indicating whether the partner was online (1) or offline (0).  Figure 1, below, shows a partner activity matrix for one city during one week, where online times are displayed in white and offline times are displayed in black:

Image
Figure 1: In an example Partner Activity Matrix, each row represents one partner, and each column represents one minute of the week ordered by day of week (Monday-Sunday). The top X-axis shows day of week and the bottom hour of day, with white indicating the partner was online and black offline.

While a city’s partner activity matrix represents partner driving patterns, it lacks interpretability and is hard to directly use. To make using this tool easier, we needed a simpler way to describe these patterns and the users they represent.

 

Organizing the Partner Activity Matrix with biclustering

One way to organize activity matrices and make them more interpretable is to use a machine learning technique called spectral biclustering. In genomics, biclustering clusters both the rows and columns of the gene expression matrix, identifying clusters of genes and individuals that behave similarly. Individuals in each cluster tend to express the same clusters of genes, and genes in each cluster tend to be expressed by the same clusters of individuals. If we shuffle the rows of the gene expression matrix so that individuals in the same cluster are adjacent, and shuffle the columns in this same manner, then the shuffled matrix has a checkerboard pattern in which the squares in the checkerboard are blocks of approximately constant value.

We use this method to simultaneously cluster rows (partners) and columns (times of week) of the partner activity matrix to identify clusters of partners with common preferences about when to drive and clusters of times of the week that are preferred simultaneously by the same partners. We use the clusters of partners to quickly understand how proposed changes to the Uber platform will affect drivers who use the platform in different ways, and to design changes that will be beneficial across the spectrum of usage. Rather than looking at the estimated impact of a change on each individual driver partner, which is a very noisy and time-consuming process, we can look at the impact on each cluster. This is our primary use for biclustering, though clusters of hours are also useful for improving the computational and statistical efficiency of some of our other algorithms by providing meaningful time aggregations that can be used instead of treating each hour separately.

Spectral biclustering tends to create more accurate clusters of driver partners than a traditional one-way clustering method like k-means because grouping times of week and measuring driver partners’ similarity on aggregate behavior over these multi-hour periods rather than individual hours tends to make the clusters more robust to noise and more interpretable. Spectral biclustering projects the high-dimensional vectors describing the hours when each partner drives to succinct low-dimensional driving patterns and then clusters drivers using these mined patterns. In contrast, k-means clusters the high-dimensional vectors directly and can be misled by irrelevant differences.

In our next section, we introduce the algorithm used to implement this powerful technique.

 

Applying a spectral biclustering algorithm

The spectral biclustering algorithm is based on a technique from linear algebra called singular value decomposition (SVD). This technique decomposes a matrix, A, which for us will be our partner activity expression matrix with n partners and d hours of week (we will have n > d), into a sum of min(n,d)=d special matrices. These special matrices, indexed by k, are each written as Image where Image and Image are column vectors of unit length (i.e., they describe line segments with length one) with d and n components respectively, and Image  is a non-negative number.  Also, Image is orthogonal to Image (they describe perpendicular line segments) and Image is orthogonal to Image when k is different from Image.  Summarizing this with an equation, we define our partner activity matrix as Equation 1, below:

Image

Spectral biclustering considers k as indexing some underlying “driving pattern.”  The vector Image, which has one component for each hour of the week, describes how often a driver following pattern k would drive in each hour. The number Image scales the number of hours up or down for the whole pattern, which is needed because Image is constrained to have length one.

Figure 2, below, illustrates driving patterns via matrix Image, where times with more driving are highlighted in dark grey:  

Image
Figure 2: In the matrix above, times with more driver activity are highlighted in dark grey. For example, the first pattern shows drivers driving during weekday morning hours, the second pattern in the middle of the day throughout the week, and the third pattern in evenings Thursday through Saturday.

For instance, the first pattern corresponds to driving during morning rush hour on weekdays; the third pattern corresponds to driving in the afternoon and evening Thursday through Saturday. Figure 2 also shows that we can summarize the driving patterns by combining the Image vectors into a larger matrix Image, with pattern IDs (k) indexing the rows and hours of week indexing the columns so that each Image consumes one row.

The vector Image, which has one component for each driver partner, describes the extent to which each driver follows driving pattern k. If Image has a large value for the component corresponding to a driver, then that driver drives at all of the hours specified by driving pattern k, and may also drive at hours given by other driving patterns. If Image has a value close to 0, that driver does not drive according to that driving pattern.  

We combine the Image vectors together into a matrix U, with partners indexing the rows and pattern IDs indexing the columns, and each Image consuming one column. We call the entries in this matrix “weights” because they indicate how much of a driver’s driving hours are determined by a particular driving pattern. It is helpful to consider a single row in this matrix, which corresponds to a partner: this row vector describes the patterns followed by this driver.  Figure 3 illustrates this with two examples. The hours driven by partner j mix patterns 2 and 3 from Figure 2, indicating that this partner drives in the middle of the day during the whole week, and also in the evening on Thursdays, Fridays, and Saturdays.

Image
Figure 3: In matrix U, the hours driven by partner j combine patterns 2 and 3, and so include the middle of the day on all days of week and the evenings on Thursday, Friday, and Saturday. The hours driven by partner i are those from driving pattern 1: weekday mornings.

To summarize, SVD allows us to write the partner activity matrix A as a sum of matricesImage, each of which describes how a single driving pattern is expressed by driver partners across the week.

When understood in this way, Image indicates the importance of a driving pattern. Since Image and Image are unit vectors, each component of these vectors cannot have absolute value larger than one and the contribution of a driving pattern Image to the activity matrix cannot be significant unless Image is large.

To capitalize on this insight, spectral biclustering orders the pattern IDs k in decreasing order of Image so that more important driving patterns have smaller pattern IDs.  We then choose a number of patterns K much smaller than the full number d created by SVD so that we include only the important patterns.  This gives us an approximation Image to the activity matrix (Equation 2):

Image

This is a “low rank” approximation because it approximates A, which is a rank-d matrix, by a matrix that has rank K < d.  

Figure 4, below, describes this process of decomposing the activity matrix and then approximating it with a matrix that includes only the most important patterns:

Image
Figure 4: We use SVD to calculate the decomposition and approximation of the partner activity matrix.

In Figure 4, SVD decomposes the partner activity matrix into three matrices, U,Image, andImage. The matrix U describes which driving patterns each driver partner follows, i.e. the pattern weights. The diagonal matrix ∑ indicates the importance of each detected pattern. The patterns are stored in the matrix Image. By keeping the first most important patterns (highlighted in dark grey), we obtain a low rank approximation of the original activity matrix that captures its essential signal.

Figure 4 writes Equation 1 in the first line in a more compact form, Image, using matrix multiplication with the matrices U and Image introduced above and one additional rectangular diagonal matrixImage, which has the Image values along the diagonal and zeros elsewhere. It then writes Equation 2 in a similar form Imagewhere Image is the first K columns of Image,  is the first K columns and rows of Image, and Image is the first K rows of  Image.

Spectral biclustering incorporates one additional step to simplify this low-rank partner activity matrix Image. This additional step considers the rows of the matrix Image: each row corresponds to a driver partner and contains, for each important pattern, a weight indicating how much that partner drives according to that pattern. We group the driver partners together with k-means clustering so that within each group, or cluster, drivers have similar sequences of weights.

We can then shuffle the rows of Image so that drivers in the same group are in adjacent rows, as depicted in Figure 5, below:  

Image
Figure 5: We can visualize the reshuffling the pattern weights to place partners in the same cluster adjacent to each other. In Figure 5, above, there are five clusters, each of which follows a distinct collection of driving patterns.

We may also perform a similar k-means clustering of the columns of Image to produce groups of hours preferred simultaneously by the same partners. Reshuffling these columns (hours of the week) to make hours in the same cluster adjacent reveals patterns similar to Figure 5.  If we wish, we may then take the Cartesian product of the shuffled Image and Image matrices along with Image to reconstruct a version of Image with shuffled rows and columns. This shuffled Image matrix exhibits a checkerboard structure with blocks of approximately constant entries.

Spectral biclustering is one of a larger number of SVD-based biclustering methods. For example, methods such as RoBic and Sparse-SVD extract patterns sequentially: they start by finding a checkerboard pattern using the best rank-1 SVD approximation; they then extract subsequent patterns sequentially from the residual matrix obtained by removing previously identified patterns. Thus, while spectral biclustering works well for clustering driver partners as described below, a great deal of additional innovation is possible.

Next, we describe our results from applying spectral biclustering to understand driver partners in one major city, thereby enabling us to customize and improve user experiences based on these patterns.

 

Results

Examining driving patterns closely using spectral biclustering highlights a difference between weekdays and weekend activity. Figures 6 and 7, below, visualize one prominent cluster of driver partners provided by spectral biclustering. These partners drive regularly between the hours of 6:00 a.m. and 6:00 p.m. during weekdays and less regularly during the same hours on the weekend, with more hours driven on Saturday and fewer on Sunday. We call this cluster of partners “daytime drivers.”  Figure 6, below, shows these partners’ rows in the partner activity matrix, where white indicates an hour when a partner was online:  

Image
Figure 6: Our daytime drivers’ partner activity matrix, which includes only those rows from the partner activity matrix corresponding to drivers in the daytime driver cluster, shows that online time, colored as white, occurs mainly from 6:00 a.m. to 6:00 p.m. on both weekdays and weekends, with fewer partners going online during weekends.

Figure 7, below, shows peaks on weekdays corresponding to morning and evening rush hour, with morning rush hour being more prominent, and smoother and smaller peaks at noon on weekends:

Image
Figure 7: Partners in the above daytime driver cluster typically drive between 6:00 a.m. and 6:00 p.m., with more drivers online during weekdays, especially morning and evening rush hour, and fewer during weekends.

Figures 8 and 9, below, depict another prominent cluster of driver partners. These partners drive at night, typically starting around 6:00 p.m. and stopping between midnight and 3:00 a.m.:

Image
Figure 8: On our nighttime driver partner activity matrix, online time (in white) occurs mainly from 6:00 p.m. to midnight on weekdays and extends to roughly 3:00 a.m. on Friday and Saturday nights.
Image
Figure 9: The ratio of nighttime drivers online per hour of the day indicate that some partners drive between 6:00 p.m. and 1:00 a.m. on weekdays, extending to 2:00 a.m. on Friday and Saturday nights.

As evidenced by the figures above, our partner activity matrix makes it easy to determine driver preferences among certain cohorts. For instance, between Monday and Friday nighttime drivers start promptly at 6:00 p.m. as they drive riders home from work, exhibited by a first peak in fraction of drivers online at this time; on Saturday and Sunday, this first peak occurs 7:00 p.m., corresponding to riders going out for the evening. On Sunday through Thursday evenings, the fraction of drivers online falls off sharply after midnight as most riders have already gone home for the evening, while on Friday and Saturday nights activity does not decrease until between 2:00 a.m. and 3:00 a.m.  

This contrast between weekdays and weekend driver partner activity reveals how Uber’s driver partners support riders and cities by providing convenient and safe transportation from work in the early evening and home from restaurants and bars later at night.

 

The potential of our partner activity matrix

The partner activity matrix use case depicted above is only a snapshot of what our machine learning teams are doing to improve app efficiency, performance, and, most importantly, user experiences.

Using our partner activity matrix, spectral biclustering also reveals other prominent partner clusters:

  • Partners that drive during the morning rush hour
  • Partners that drive primarily during Tuesday, Wednesday, and Friday morning rush hours
  • Partners that start driving at noon
  • Partners that most commonly drive weekday evening rush hour (from 4:00 p.m. onward), and into the evening

These clusters give Uber more insight into how driver partners use the platform by offering an easy-to-understand categorization of these different kinds of usage, in turn making it easier for us to improve our products for both drivers and riders alike.

If using data science to engineer more magical Uber experiences for drivers interests you, consider applying for a role on our team!

Qing Feng and Peter Frazier are data scientists on Uber’s Marketplace Optimization Data Science team.  Peter is also an Associate Professor of Operations Research and Information Engineering at Cornell University.

References

[1] Kluger, Y., Basri, R., Chang, J. T., & Gerstein, M. (2003).  Spectral biclustering of microarray data: coclustering genes and conditions. Genome research, 13(4), 703-716.

[2] Asgarian, N., & Greiner, R. (2006). Using rank-1 biclusters to classify microarray data. Department of Computing Science, University of Alberta, Edmonton, AB, Canada.

[3] Lee, M., Shen, H., Huang, J. Z., & Marron, J. S. (2010). Biclustering via sparse singular value decomposition. Biometrics, 66(4), 1087-1095.

Peter Frazier

Peter Frazier

Peter Frazier is a staff data scientist on Uber's Marketplace Pricing team.

Posted by Qing Feng, Peter Frazier

Category: