Axis/Scale Boundaries

When charting unknown data, we would like to set the axis scale such that the details in the data are clear and the end points on the scale are aesthetically pleasing.

D3 and Protovis use the "nice" algorithm for linear scales (and a modification for logarithmic scales). The pull request implementing the algorithm in JavaScript is on github, but, mathematically, for an array of data containing a \(min\) and \(max\) value:

Let $$step = 10^{round(log_{10}(max - min)) - 1}$$

then,

$$scale_{min} = \lfloor\frac{min}{step}\rfloor \times step$$
$$scale_{max} = \lceil\frac{max}{step}\rceil \times step$$

If the data has a range of 0.002454 to 0.1455, the scale will extend from 0.002 to 0.015. Visually, the bounding boxes (tan and green) will look like:

Minimizing Autocorrelation of a List

As part of a graph rendering algorithm, I needed to take a list of y-values and disperse the points within a xy-range. (Within the list, the x coordinate has no meaning. I'm not re-ordering a time series.) To model the dispersion, I decided to use the autocorrelation metric. Autocorrelation measures the correlation of a list to itself. Put another way, autocorrelation measures how much the prior value can be used to predict the next value. (For this discussion, I'm using 1 as the lag parameter. Additionally, minimizing the autocorrelation is the same as minimizing the covariance.)

For example, the figure below shows a sinusoid (sampled at a regular interval). The autocorrelation of the figure is 0.994705 --- almost the maximum value of 1.

In contrast, the figure below has been modified by the autocorrelation minimization algorithm. The two figures have the same y-values, but the x-values have been changed resulting in a new correlation of -0.999955.

The Algorithm

The formula for calculating autocorrelation includes a number of terms, but the only terms that are impacted by changing the order of the list can be reduced to the sum:

$$ \Sigma(x_i - \mu)(x_{i+1} - \mu) $$

where \(\mu\) is the arithmetic mean of the list.

The approach is to maximize occurrences of large negative values.

1. Create a list terms with the values of the list minus the mean of the list.
2. Sort the list terms.
3. Initialize the merged list with the head and tail of terms.
4. While elements remain in terms,
1. Take an element from terms (either the head or tail) such that the element minus the mean multiplied by the head or tail of merged has minimal value.
5. Add the mean to each element of merged. Return that list.

I've uploaded a Python implementation of the algorithm to Gist.

Updated: Algorithm simplified

Dateinfer Updated

The dateinfer package has been updated to version 0.20.

You can get it from PyPi, Github, or install it via pip.

Release of dateinfer: v0.1.1

I have released the first version of a new Python library called dateinfer. dateinfer makes a "best guess" date format given a list of example date strings. For example:

>>> import dateinfer
>>> dateinfer.infer(['Mon Jan 13 09:52:52 MST 2014', 'Tue Jan 21 15:30:00 EST 2014'])
'%a %b %d %H:%M:%S %Z %Y'
>>>

The library is available through pypi and is hosted on github.

Access denied checking streaming input path

When I started launching my Elastic Map Reduce (EMR) jobs from within a Elastic Beanstalk EC2 instance, I was stymied by the error message:

Terminated with errors Access denied checking streaming input path: s3://bucket/key

I first opened up permissions on my S3 bucket and file, but that didn't work. I then explicitly set the IAM role for EMR and assigned a policy for full read/write rights to S3. That also did not work.

After conversing with Amazon Web Services technical support, they noted that I was making requests using temporary credentials. EMR does not support temporary credentials, so the actual request was being performed by something with no authority to access any resources.

I solved the problem by explicitly setting my credentials (AWS access key, secret access key) in my job creation code. Since I am using mrjob,  this was a matter of:

runner = EMRJobRunner(
            aws_access_key_id='xxxxx',
            aws_secret_access_key='xxxxxxx',
            ...)

Before, I was not explicitly setting the access keys, so mrjob was using the keys boto was using, which are apparently temporary credentials passed in via Elastic Beanstalk.

Hadoop Processing Model

Note: These are preliminary results.

I've begun work on a application to perform various automatic statistical analyses of a large dataset (millions of records or more). It is implemented as a group of one-pass (or online) algorithms operating in a map-reduce topology. Technologically, the back-end uses Hadoop and the mrjob library. I haven't made technology choices for the front-end, but I'm leaning towards Django, Bootstrap, and D3.

One of the system engineering challenges for distributed processing is to scale the number of nodes to the workload. Eventually, I have to perform actual performance tests but for now I can approximate the resource requirements using an abstract model.

Abstract Model of Hadoop I/O Processing

The abstract model is a better approximation of a map-reduce conceptual model than Hadoop's actual architecture, but I hypothesize that it's sufficiently accurate for my purposes (and will later use test data to validate the model).

Input to the overall process is provided as a series of N records, with each record containing M columns or fields. (The M columns represent the number of columns processed/generated by the application; for simplicity we will assume the input's number of columns is one-to-one with the number of columns processed by the application.) Normally, N will be much greater than M. The input is divided between P map nodes and becomes the A datasets within each map node. The map process converts A into B. Likewise, the combine process converts B into C. At this point, the individual C records are merged, sorted by key, and transferred to Q reduce nodes where the records become D. The interim data is denoted as S. The D datasets are consumed by the reduce process and converted into E. Finally, E is merged into the final results of F.

Based on the algorithms, I can estimate the number of records in A through F and based on the current implementation estimate the size of records in each stage. Thus, I can calculate the total number of bytes that pass through the job from the origin to F. Setting M=10, I plotted the bytes (in terabytes) as a contour plot with N and P as the axes:



The plot is in Log2-Log2 form. The x-axis measures the number of records from a gigabyte (roughly a billion) to a terabyte (roughly a trillion). The y-axis varies from a single processor (2^0) to 128 processors (2^7). The ridges show that I/O is constant with doubling input and doubling the number of processors, so we are making effective use of the map-reduce framework. However, since the contour scale is measured in terabytes, the linear complexity has a large constant factor.

In the model, the I/O costs are concentrated in the B stage. Although the individual output of the Map process is small (when measured on a per-record level), the number of records in B is MN/P. The Combine process is necessary to immediately aggregate the results together and rid the N term from the later I/O steps. For comparison, F is proportional to M and, although each record will be in the 100s of kilobyte to megabyte range, the total size consumed can be a thousandth of B.

Confusion Matrix in Mathematica

A confusion matrix is an effective visualization technique to diagnose how a classification algorithm is behaving. You can create one easily in Mathematica given a list of 2-tuples, where the 2-tuple is of the form {ground truth category, predicted category}.

ConfusionMatrix[gndpre_List] :=
 With[
  {categories = Union[Flatten[gndpre]]},
  Partition[
   Flatten[
    Table[
     Count[gndpre, {row, col}],
     {row, categories},
     {col, categories}
     ]
    ],
   Length[categories]
   ]
  ]