Processing multi-dimensional data visually

In an earlier post I discussed the challenges we face currently at CEDL when we look at Big Data (http://blog.camenergydatalab.com/2014/10/big-data-crunching.html). This has been complex already, but we love new challenges here at CEDL. So let’s talk about multi-dimensionality.

If we presume that our data is arranged in a table like this:

ID	location	date	temperature	humidity
1	London	2015/02/12	4	68
2	Cambridge	2015/02/12	2.5	55

then aspects of big data refer loosely to the number of rows and multi-dimensionality of the data refers to the number of columns. Basically, we do not only have a lot of data (rows) but it is also complex due to the high number of features (columns).

Understandably, it is very challenging to extract information from such complex data in particular when we do not know what we are looking for. As part of the data exploration a data scientist will look for patterns or clusters that might tell us more about the processes which shape the data.

Of course, a data scientist wants to use the best tools available to find patterns and clusters in the data and as it turns out the most powerful machine for pattern detection is the visual cortex! The brain is your very personal supercomputer. The challenge in utilising the brain for detecting patterns in multidimensional data sets does not, thankfully, come down to brain surgery. Nevertheless, a problem still remains: how to interface the visual cortex with the data set? The only and best working interface are of course the eyes. All what is required is to transform the data set into a representation suitable for the eyes -> visual cortex interface. You might wonder why this sounds rather like an engineering problem than the typical task of a data scientist.  Unfortunately, the role of a data scientist is commonly misunderstood. In fact, with today’s challenges the task is not so much about calculating statistics but to engineer a way to access and consume data.

Usually, this happens in the form of charts and plots and it is up to the data scientist to find a suitable data representation for the problem at hand:  to explore data, find answers, and to communicate them.

For example, a fantastic way to represent multidimensional data are Parallel Coordinates [1] if you want to utilise the pattern recognition abilities of the brain’s visual cortex.

In a chart with parallel coordinates each column of the table is a vertical axis and each row becomes a line in the chart. Here follows an example:

This type of chart works with both discrete and continuous data. Additionally, colour and line types can be used to add some additional context to the data. Obviously, this chart is very simple but it can help us understand how parallel coordinates work. For example, looking at the location axis we can note that we have three records with location London and three with location Cambridge while looking at the axis data we note that we have two records for each day.

This chart shows you parallel coordinates in full action:

The chart shows the visualization of the mtcars dataset [2]. The data was extracted from the 1974 Motor Trend US magazine, and comprises fuel consumption and 10 aspects of car design and performance for 32 cars (1973–74 models).

A way to explore data in parallel coordinates is called “brushing”: Simply select a range over one or multiple axis and explore how the data segregates.

For example compare the models with better fuel economy versus models with less miles per gallon (mpg):

Whereas the cars with low fuel economy don’t seem to show any specific segregation, the cars with good fuel economy are light cars with 4 cylinders and small displacement.

[1] http://web.cs.ucdavis.edu/~ma/ECS289H/papers/Inselberg1997.pdf

[2] http://stat.ethz.ch/R-manual/R-devel/library/datasets/html/mtcars.html

Big Data Crunching

There has been much talk about Big Data in the last years and the word cloud shows terms commonly related to the definition of Big Data. First and foremost, the most important attribute of Big Data comes as no surprise: its volume! Big Data is, as the name suggests, BIG. What big actually means in regards to bytes or number of records is circumstantial. It becomes big when your traditional way of data processing hits a wall and becomes unfeasible.

The first symptom will be that your data does not fit into memory. In the beginning you might simply beef up your computer with some extra memory. This is commonly called to scale up. A more sophisticated solution would be to load only partial data into memory as disk size is much less of a bottleneck. This is how a database operates. A join operation on two massive tables, e.g. in Postgres, will load and write many chunks of intermediate data but will eventually succeed even though all the data never fit into memory at once. Relational Databases and scaling up to more powerful computers was the gold standard for tackling growing data volumes. Things changed in particular after 2004 with Google's publication of "MapReduce: Simplified Data Processing on Large Clusters"[1].

Instead of running huge databases on expensive supercomputers the trend went to massive parallelisation on clusters of cheap hardware. With this came new challenges which MapReduce successfully addresses:

• parallelisation must be easy
• automatic distribution of data between the workers of the cluster
• fault tolerance

If you process data on a big cluster of cheap hardware the chances are quite high that one of the computers breaks down. In the ACID world of RDBs (all or nothing transactions) this would mean we never get any results.

So what exactly is MapReduce doing differently?

The MapReduce Paradigm

Let's discuss a simple example inspired by a common task in processing genetic data: imagine you have vast amount of strings and you want to trim the last 5 letters of the strings.

In such a task we have to process each single record. This means the task is of linear order:

\[ O(n) \]

where the computational effort grows linearly with the number of records.

However, each record can be processed independently from the other records which allows to scale out the task over multiple processes, cores, or computers.

Let \(k\) be the number of processes, cores, or computers available, the order of our task becomes

\[ O \left ( \frac{n}{k} \right ). \]

This is much better for the case of Big Data when \(n\) is very large as we can control the computational effort easily by increasing \(k\). Additionally, if one subtask fails we only have to rerun that specific subtask. A complete rollback of the transaction is not required as it would be the case in ACID conform RDBs.

Let’s consider a slightly more complex task: the "hello world" program in the world of  MapReduce is the counting of word frequencies in a very big number of documents. As it was the case in the previous task, the word count of a single document is independent from the other documents, this makes the task perfectly suitable for scaling out:

A common pattern is emerging here: we use a function which maps each document to a list of independent word counts. The result of this map is a distributed list of word counts. So far our MapReduce programme comprises the following steps:

1. distribute the documents over multiple computers in a cluster
2. apply a word count function on each computer
3. generate a distributed list of word counts

The next step is to aggregate the distributed list of word counts. However, we want to scale out the aggregation again over multiple computers:

This aggregation step is also called reduce. The steps involved are as follows

1. send the same words to the same computer for aggregation (called shuffle)
2. apply a sum function to generate the word count over the complete set of documents (reduce)

And there we have the complete MapReduce paradigm:

Some tasks might be more difficult to translate into map and reduce steps and can require multiple rounds of mapreduce. However, the mapreduce ecosystem is growing steadily with new libraries implementing now even complex machine learning algorithms in mapreduce [3,4,5].

Last but not least, comparing mapreduce to RDB we see that mapreduce is using schema at read, which is ideal for messy and inconsistent data, and RDB is traditionally using schemas at write. In the world of Big Data the schema at read approach has the following advantages:

• the flexibility to store data of any kind including unstructured or semi-structured data
• it allows flexible data consumption
• it allows the storage of raw data for future processing and changing objectives
• it removes the cost of data formatting at the moment of data creation which results in faster data availability
• it allows you to experiment with the data at low risk as the raw data can be kept to correct mistakes

There is always the elephant in the room when speaking about MapReduce: Hadoop!

Most importantly, Hadoop is not MapReduce it is just one implementation of the mapreduce framework! Hadoop is quite a beast and targets the really BIG Big Data. An alternative implementation we are using here at Cambridge Energy Data Lab is Disco.

The main reason we use Disco over Hadoop: Disco jobs are written in Python and Hadoop jobs are mainly written in Java. (Strictly speaking you can also use other languages with Hadoop). Also Disco is much lighter and easier to administrate. [2]

The word count example in Disco is as simple as the underlying problem itself:

  from disco.core import Job, result_iterator

   def map(line, params):
       for word in line.split():
           yield word, 1

   def reduce(iter, params):
       from disco.util import kvgroup
       for word, counts in kvgroup(sorted(iter)):
           yield word, sum(counts)

   if __name__ == '__main__':
       input = ["http://discoproject.org/media/text/chekhov.txt"]
       job = Job().run(input=input, map=map, reduce=reduce)
       for word, count in result_iterator(job.wait()):
           print word, count

I leave it to you to compare this with the Java version for Hadoop: https://wiki.apache.org/hadoop/WordCount

Artificial Neural Networks

An artificial neural network (ANN) is a computational model inspired by the information processing functionality of the brain. But how does the brain compute?

 Generally, the central elements of computation are processing, transmission, and storage. Within the brain the neuron is the central computing element. Neurons receive signals and produce responses. The transmission of information at the neural level involves electrical signals – so called action potentials – based broadly on ions and semi-permeable membranes, and chemical signals at the synapses. In the brain the storage of information corresponds to learning which occurs at the synapses. These synapses are at the interface between neurons and regulate the transmission of information from neuron to neuron.

 An ANN widely corresponds to the processing paradigm of neural networks with the nodes of the ANN being the central computing element similar to the neuron. In fact, ANNs are nothing but networks of primitive functions where the chain of function compositions transforms an input to an output. The composition of the computational model is contained implicitly in the interconnections of the nodes and is referred to as the network function. Each node comprises a primitive function transforming its input into an output:

Typically, the inputs of a node have an associated weight w by which the input x i is multiplied. The node integrates all its inputs – usually by adding the different inputs – followed by the evaluation of its primitive function f. The primitive function f computed in the node can be any function but common choices are differentiable functions such as the sigmoid function. Models of ANNs mainly differ in their choice of the primitive function, the topology of the network, and rarely in the timing of the evaluation of the primitive function. In feed-forward ANNs the network is composed of distinctive layers where each neuron only receives input from neurons of the previous layer. Accordingly, a feed-forward network has a distinct input and output layer with the intermediate layers being referred to as hidden layers:

(A second class of ANNs are recurrent networks where connections between nodes form directed cycles.)

The network function of an ANN can be understood as a universal function approximation. However, the difference between ANNs and a Taylor or Fourier series is that the function to be approximated is given not  explicitly but implicitly, through a representative set of input-output examples. It will be the task of the learning algorithm to adjust the parameters of the ANN to reflect the input-output examples and to extrapolate to new input patterns in an optimal manner. The learning algorithm is an adaptive method by which the network self-organises to reflect the function to be approximated. The computational effort directly relates to the number of parameters and therefore to the topology of the network and increases substantially for more complicated ANNs. It was not until the proposal of back-propagation as a learning algorithm [Werbos, 1974] that the application of ANNs gained momentum and it has been the most widely used algorithm for neural network learning ever since.

 The back-propagation algorithm uses gradient descent on the error function of an ANN in weight space. Thus, the weights of an ANN which minimise its error function are considered to be the solution of the learning problem. As a precondition for gradient descent the error function of an ANN needs to be continuous and differentiable. Since the ANN is simply the composition of its primitive functions the error function becomes differentiable if the networks primitive functions are differentiable themselves.
In the back-propagation algorithm an ANN is initialised randomly with weights. Next, the gradient of the error function is computed recursively and the weights of the ANN are adjusted accordingly using gradient descent. Because an ANN is a complex chain of a sequential function composition the chain rule plays a most important role in calculating the gradient of the network function's error. The back-propagation algorithm implements the chain rule for  the recursive calculation of the gradient of the error function in weight space in a very efficient manner.

Learning in an ANN with back-propagation consists of two stages: in the first stage – the feed-forward step – the information progresses form the input layer throughout the network towards the output layer.
Each node of the network evaluates its primitive function \(f_j(e)\) and emits the result \(y_j\) to the connected  nodes in the subsequent layer. Additionally, each node calculates and stores the derivative of its primitive function \(df_j(e)/de\).

The second stage -- the back-propagation step -- consists in reversing the flow of information throughout the network whereby a unit input propagates from the output layer towards the input layer with the activation of each neuron now being the back-propagation term \(\delta_j\).
At each node the back-propagation term \(\delta_j\) is multiplied by the stored derivative of the node's primitive function from the previous feed-forward step which gives the gradient in weight space \((d f_j(e)/de) \delta_j\).

Finally, the weights are updated using gradient descent as given by
$$
w'_{i,j} = w_{i,j} + \alpha y_{i} \frac{d f_j(e)}{de} \delta_j
$$
with \(\alpha\) being the learning rate and \(w_{i,j}\) being the weight of the feed-forward connection from neuron \(i\) in the previous layer to neuron \(j\) in the subsequent layer.


[Werbos, 1974] Beyond regression: New tools for prediction and analysis in the behavioural sciences, Pd.D. Thesis, Harvard University (1974).
[Gurney, 1997] An introduction to neural networks, UCL Press (1997).
[Montavon, 1998] Neural Networks: Tricks of the Trade, Springer (1998). 

How Do You Use Electricity ?

Collecting data with smart-meters

Smart-meters, through their ability to communicate data instantly, are re-shaping the electricity market landscape. Indeed, these new-generation meters collect and transmit instantaneous electricity consumption data, which can then be used by various actors ranging from the user (e.g. to monitor its own usage) to the supplier (e.g. to forecast energy demand) via independent companies (like Cambridge Energy Data Lab) which help make more sense of this data.

In this short study, we will focus on identifying generic behaviours of electricity consumption within a dataset of more than 400 users for the February-March 2014 period. Because the raw dataset is impossible to interpret, we will perform what is usually referred to as a "model reduction."


Principal component analysis

The first step in the analysis is to perform a model reduction to define several types of days. Amongst all the unique day time-series, we select few thousands (8000 days exactly, out of the 60 days x 400 users = 24000 total days available) in order to perform a Principal Component Analysis.  PCA is a linear algebra method used in order to find directions of largest variance in a dataset composed of several samples of a given variable. See figure 1 for a visual example.

Figure 1: PCA, 2-dimensional example. PCA finds the orthogonal directions which maximise the variance of the samples. 

After having performed a PCA, we can order the different samples along the first principal component (PC1 in Figure 1). We perform a PCA on the dataset composed of the 8000 different days of electricity consumption and order the different days along the first principal component. The result is presented in Figure 2.

Figure 2: PCA performed on a dataset of 8000 days of electricity consumption. The days are ordered with respect to their coordinate along the first principal component.

We notice that the days are now ordered with respect to a relevant criterion since we can detect a continuous evolution from users consuming electricity during the day and in the evening (top of Figure 2) to users who mostly use electricity in the evening and at night (bottom of Figure 2). From this observation, we can therefore define different types of days.

We then simplified the full dataset thanks to this criterion, creating around 10 different "types of days." It is therefore possible to simplify the 2-month time-series by attributing a value to each day corresponding to its type. This is represented in the left panel of Figure 3.

Figure 3: Left panel: unordered "type of day" time-series. Right panel: ordered "type of day" time-series obtained by ordering along the first principal component. We notice an evolution from users who mostly use electricity during the day (top) to users who mostly use electricity at night (bottom).

By re-applying the concept of first principal component ordering, we can re-order the simplified "type of day" time-series. This is presented in the right hand side panel of Figure 3. This time, more than ordering the time-series of the days, we manage to order the users. Each separate user can therefore be attributed to a category, depending not only on the type of daily consumption, but also on the longer time-scale (weekly, monthly) behaviour. Indeed, at the top of the right side panel are represented the "type of day" time-series for the users consuming electricity mostly during the day and the evenings, whereas the bottom part of this colour plot is associated with users consuming electricity mostly at night time. We can also notice on this figure a longer time-scale behaviour ordering, and the signature of the week-ends where people tend to stay awake (and use more energy) later at night.

Conclusion

The large amount of data collected by smart-meters can only been visualised and interpreted by using advanced mathematical tools, PCA being one of them. This method allowed us to successfully define different types of days in terms of electricity usage and therefore simplify the complete users' electricity time-series. From this model reduction, another PCA was then performed to directly order the users, therefore gaining insight about the different types of electricity consumption behaviour present in the dataset.

Talent over CVs

As a young and dynamic startup, we are continuously looking for great new talent to join our team of data scientists. But talent is hard to find in a pile of CVs and, as a data science company, it seemed logical to use a data-driven approach to asses applicants. That's why we designed three simple data science challenges (which you can find on GitHub). The 3 different tasks target the different objectives of our company:

• Data Analysis and Visualisation
• Data Modelling, Machine Learning, and Prediction
• Web Development

Each of the tasks is designed to see which programming style you use and how well you document and communicate your code. Code that is not only of high-quality, but also is well-documented and easy to understand is our priority. Please take extra care that you push a polished version of your code.
Second, quality comes before quantity. The objective is not to find the best overall method, so please focus on a single approach rather than trying several methodologies. Remember that you work on an unknown dataset, so don't assume too much. Just try to satisfy the requirements of specialised methodologies.
Finally, we are always happy to see people addressing all three challenges at once, but this is certainly not required!
But enough of the instructions and let's showcase some great examples which we have received:

Cluster analysis of energy consumption data

credit: Dimitry Foures

credit: Philip Squires

Predicting energy production using Bayesian networks

credit: Jan Teichmann