The Shape of a Week¶

Part I: problem statement¶

Some time ago, I was discussing some data analysis for the Business Analytics project at the Illinois Geometry Lab with the other members of the team. We were predicting several business-relevant quantities using straightforward linear regression. One of the independent variables was the month in which certain transactions took place. The question we started discussing was simple: how can we best encode this categorical variable for our regression?

A standard approach to encoding categorical features is to use one-hot encoding, in which the $n$ categories are encoded using $n$ columns, and an observation where the categorical value takes the $i$'th value is encoded as a 1 in the $i$'th column (and zeroes elsewhere). For example, January might be encoded as $(1,0,0,...,0)$, February as $(0,1,0,...,0)$, and so on, with December encoded as $(0,...,0,1)$.

A disadvantage of this method is that the number of dimensions increases a lot (namely by the number of categories). The question we can then ask is: how can we best encode this categorical variable for our regression, if we limit ourselves to a given number of dimension?

Suppose we restrict ourselves to a single dimension. One way one could encode months using one real number is as follows:

This way of encoding months, though, is far from perfect. The biggest problem is that December is far away from January on this picture, even though they are close together in time. Suppose that you want to predict outdoor temperatures using the month as an independent variable. The warm months are those in the middle of the line segment, and the cold ones are at the ends (I'm writing this from the northern hemisphere). Linear regression will therefore perform very poorly for these predictions. For predicting temperature, it's best to put the warm months on one end of the line, and the cold months on the other. Of course, we only know this from our experience with seasons. In other situations, what would be a sensible way of encoding the categories to maximize regression effectiveness?

Let us find an automated way of finding an encoding of a categorical feature, in a way that makes linear regression maximally effective if we use this encoding. In order to determine this encoding, we will use measurements from similar problems where the variable to be predicted is known.

Mathematically, we want to do the following. Suppose that we have several datasets $D_1, ..., D_k$, and that there is a categorical variable that shows up as a column in each of them. (We'll assume that there are no other categorical variables in them, or that they have been encoded as real numbers somehow.) Suppose that there are $n$ different categories. Given points $p_1, ..., p_n$ in $\mathbb{R}^m$, we can encode the categorical variable using $m$ columns, and then perform linear regression on each of the datasets. For each regression, we get an $R^2$-value that measures how much of the variance is explained by the regression. Find points $p_1, ..., p_n$ in $\mathbb{R}^m$ such that the sum of the $R^2$-values is maximal.

In the example that we will study, the categorical variable is the weekday (so that there are seven categories), and we want to encode it using two dimensions. In non-mathematical phrasing, we are asking: if you had to put seven points on a plane, each corresponding to a day of the week, what would be a sensible way of doing that? What is the shape of a week?

A reasonable suggestion might be to put the points on a circle, like so:

While this reflects the cyclic nature of a week well, it's probably not the best way to embed weekdays in a plane. For example, for many purposes, the weekend is a special part of the week. It may therefore be natural to put Saturday and Sunday a little closer together, and farther away from the other days. Of course, the correct positioning heavily depends on the problem you're studying.

Part II: principal component analysis¶

We will consider a special case of the above situation. This will make the calculations much more tractable. The categorical variable is a weekday (so we have seven categories). Each of the datasets will be particularly simple: the categorical variable is the only variable, and each dataset has precisely seven observation, namely one in each category. In this case, we can summarize the entire collection of $k$ datasets as a $(7\times k)$-matrix $Y$. We will assume the columns of $Y_i$ are normalized to have mean 0 and variance 1.

Suppose we decide to embed the weekdays into the plane as $(x_1, y_1), ..., (x_7, y_7)$. We will put these coordinates into a matrix $$ A = \begin{pmatrix} x_1 & y_1 \\ x_2 & y_2 \\ \vdots \\ x_7 & y_7 \end{pmatrix} .$$

Let us write $Y_i$ for the $i$'th column of $Y$ (i.e. the data of the $i$'th dataset). The sum of residuals when regressing this column on the weekdays is then $$ \lVert Y_i - A(A^TA)^{-1}A^T Y_i \rVert^2 .$$ Summing over $i$, we want to minimize $$ \sum_{i=1}^k \lVert Y_i - A(A^TA)^{-1}A^T Y_i \rVert^2 .$$

But we recognize this minimization problem from... principal component analysis! The minimal total residuals are achieved when the columns of $A$ span the same plane in $\mathbb{R}^7$ as the first two axes of the hyperellipsoid determined by the points $Y_i \in \mathbb{R}^7$.

In other words, the shape of a week that yields optimal regression can be calculated by applying principal component analysis to the datasets. This is perhaps not very surprising, since principal component analysis is designed to explain as much of the variance in data as possible. Nevertheless, I wanted to make this quick detour to show how I went from "optimize the encoding of a categorical variable for regression" to the principal component analysis we'll be doing in the next sections.

Part III: GitHub commit histories¶

We will study the shape of a week in the case of GitHub commit histories. Each of our miniature dataset will consist of commit counts for the weekdays for a given GitHub repo. We will use the GitHub API for retrieving this information.

If you want to use the GitHub API, it's best to get your own token. Without user authentication, you can only make a very limited number of requests. This code will ask you for your token. You can also just replace getpass.getpass() by your token (e.g. API_TOKEN = '0123456789abcdef0123456789abcdef01234567').

We'll access the GitHub REST API using the python requests library. We will also need some tools for dates, since we'll be determining weekdays.

Check rate limit of Github API¶

Just to make sure that the API requests are getting through successfully, and to keep an eye on how many API requests we have remaining, let's check the rate limit.

Weekday distribution of a repository¶

Let's start by getting the commit times of a given repository. We will limit ourselves to the last 1000 commits by default, so that we don't use hundreds of API requests to get information about a single repo. It's more interesting to spread out our requests (and time) over more repositories. Note that we are only looking at commits on the default branch.

Let's test this out to get the commit times for the repository daanmichiels/hypermesh.

Now let's tally how many of the commits were on a given weekday.

You can ignore the offset parameter for now. We will only use it at the very end, in the bonus section.

As you can see, I mostly work on the hypermesh repository in the weekend.

Sampling repositories¶

We want to apply the above procedure to a sample of randomly selected GitHub repositories. The following function selects a repository at random. The distribution is not precisely uniform, for two reasons:

• we uniformly select an index, but we return the first repo with index at least this number; this means that repo's right after a long run of missing indices are more likely to be chosen
• we have a fixed maximal repository index, which does not precisely reflect the most recent state of GitHub; because the API makes it very difficult to discover the maximal index, we don't fix this

Nevertheless, we have every reason to expect that the sampling is good enough for our purposes, because it seems unlikely that there is a relationship between having many unused indices right before a repository, and this repository, say, committing only in the weekend.

Here's a randomly selected repository:

For our purposes, we will need a large number of repositories. Let's select 1000 of them. This will take a while.

Note: the code below is more naturally written as repos = [random_repo() for i in range(1000)]. However, if we then lose our network connection, the entire statement will fail, and we won't have any repositories. If we write the code with a loop, a timeout on a network connection breaks the loop, but we will still have all the repositories collected up to that point.

Note that this took many API calls:

Because fetching this data is not something we want to have to do again, we will store it using IPython's storemagic. That way, we can load the data from disk after restarting our session.

Fetching commit times¶

For each of these repositories, we now fetch the list of commit times. Again, this is heavy on the network, and we store the results.

Let's take a look at how many commits a typical repository has.

Note that there is a bump on the right because we listed at most 1000 commits for a given repository. All the repo's with more than 1000 commits show up as having 1000. As you can see, most repositories have fewer than 100 commits. Let's zoom in a bit.

We only want to take into account repositories that have a long enough history, to not have the results be influenced too much by created-but-never-done-anything-with-it repositories. Let us filter out those repositories that have fewer than 10 commits.

Performing the analysis¶

We now tally the commit times by weekday.

We put these numbers in a matrix $Y$.

We perform the principal component analysis by computing the singular value decomposition of our matrix.

Let's take a look at the singular values:

We see that the first two components explain some of the variance, but certainly not all of it.

Let's build the projection matrix that takes the first two principal components of an observation.

We now project our observations. This gives us the optimal embedding of the days of the week into a plane, as measured by our test data.

Let's also plot just the first principal component (this is the same as projecting the above points to the horizontal axis).

Observations.

• We see that Monday seems to be the most special day, since it is embedded far away from the rest.
• Tuesday is also relatively isolated from the rest.
• Saturday and Sunday are relatively close together. It suggests that project with a lot of commits on Saturdays also have a lot of commits on Sundays, and vice versa. This makes sense, since one would expect to have weekend projects on GitHub, as well as professionally developed products that have most commits during business hours.
• Note that the days of the week are not merely embedded as a circle, like one might spontaneously try. There is more to weekdays on GitHub than merely their cyclic order.

Bonus: drawing the loop¶

Just as an experiment, I would like to show you how you could connect the seven weekdays with an actual curve in the plane. This might be fun to see, since we think of weeks as cyclic. We change the grouping for our tallies by increments of 15 minutes, and plot the principal components of the resulting tallies. I'll let you figure out the details.

As you can see, the curve is still a bit jittery. We would probably get cleaner results by using more data, but we can't go much higher than 1000 before we run into the GitHub API's rate limiting.