sjwhitworth/golearn — pull request #61 by Sentimentron (2014-08-03 15:17:00+00:00)
Title: Instances v2

Another giant patch which adds:
* The foundations for Attributes of variable length and lengths other than 8 bytes.
* The foundations for a mmap'd file format to allow comfortable processing of datasets larger than available memory.
* A new `BinaryAttribute` type (which can't be natively stored yet)
* Lazily filtering and manipulation of data
* Revisions to each algorithm with test coverage to support these new features.

The individual commits have squashed for ease of review.

`base/edf` is the start of a file format which can be mapped to virtual memory. It provides byte-level storage for the renamed DenseInstances type. It can be used without a physical file (anonymous mapping) or with one, but the format can't yet capture everything necessary to be a serialisation format. Being mapped in virtual memory should allow golearn to process more data than can physically fit in memory or within the system page file, but the mapping will need some optimisation before this can happen. [I've written some more about it if you're interested.](https://github.com/Sentimentron/golearn/wiki/EDF%20Format)

Pretty much all of the API functions supported by Instances have been refactored to use a series of interfaces (`DataGrid`, `FixedDataGrid`, `UpdatableDataGrid`), as there are several new types that provide the kind of data storage that `Instances` did. `DenseInstances` is the equivalent of the original `Instances` type, `LazilyFilteredInstances` applies filtering to the data stored in `DenseInstances` and `InstancesView` allows certain Attributes and rows to be hidden or moved around. Instead of storing everything as `float64` internally, everything is now stored as `[]byte` slices.

[I got interested in whether we could be as fast at KNN as rust](http://huonw.github.io/2014/06/10/knn-rust.html) (we're currently about an order of magnitude slower). I've concluded that the only way to realistically do this is to store identical Attributes together. By precisely controlling the memory layout, it should allow us to vectorise certain numerically intensive operations when conversion to a `mat64.Dense` isn't practical, and fall back to a pure go implementation otherwise. The data-structure for doing this is currently called `Pond` (I hope to rename it `FixedAttributeGroup` once I've implemented native storage of binary Attributes), and my prototypes did get comparable performance with rust. If ponding is in use, Attributes may be conceptually reordered, and so the `AttributeSpec` type replaces integer indexing. Because rows can now be re-ordered and hidden, `MapOverRows` is the preferred way to iterate over data.

The new `BinaryAttribute` type can't yet be natively represented, but there is a new `BinaryConvertFilter` to transform `FixedDataGrid` implementations to ones which have some or all of their Attributes replaced with binary versions. The Naive Bayes implementation has been modified to only accept BinaryAttributes as training and test data.

Everything with test coverage has been refactored to use these new capabilities as well as the example applications and everything should be working (here's hoping, Travis!)

As always, I'd appreciate your comments and suggestions and [feel free to browse the docs](https://godoc.org/github.com/Sentimentron/golearn). I think golearn's got the beginnings of a really awesome product: we've already accomplished everything we set out to do in v0.1, and I think the direction we're headed in is pretty excellent too.