## Thursday, September 10, 2015

### Histogram-based Approximation in Scala

Target audience: Beginner

Introduction to a simple function approximation algorithm using a dynamically resizable histogram in Scala.

Overview
A typical function approximation consists of finding a model that fit a given data set. Let's consider the following data set {x, y} for which a simple model f: y = f(x) has to be approximated.

The black dots represent the data set and the red line the model y = f(x)
There are multiple approaches to approximate a model or a function to fit a given data set. The list includes

• Splines
• Least square regression
• Levenberg-Marquardt
• K-nearest neighbors
• Histogram
• Polynomial interpolation
• Logistic regression
• Neural Networks
• Tensor productgs
• ... and many more
Interpolation using dynamically resizable histograms is a very simple and effective method to approximate a data set.

Histogram
An histogram consists of array or sequence of bins. A bin is defined with three parameters:
• _x Center of the bin
• _y Average value for the bin
• count Number of data points in the bin
The distribution of histogram bins is illustrated in the following chart

Let's look at an implementation of the Bin class. The constructor takes two values:
• _x mid point of the bin (or bucket)
• _y current frequency for this bin
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Bin( var _x: Double, var _y: Double =0.0) extends Serializable { var count: Int = 0 def += (y: Double): Unit = { val newCount = count + 1 _y = if(count == 0) y else (_y*count + y)/newCount count = newCount } def + (next: Bin): this.type = { val newCount = count + next.count if(newCount > 0) _y = (_y*count + next._y*next.count)/newCount this } def + (next: Array[Bin]): this.type = { val newCount = next.aggregate(count)( (s,nxt) => s +nxt.count, _ + _ ) if( newCount > 0) { _y = next./:(_y*count)( (s, nxt) => s + nxt._y*nxt.count)/newCount count = newCount } this } } 

The method += (y: Double): Unit adds a new value y for this bin (line 6). It recomputes the average frequency _y (line 8). The method + (next: Bin): this.type (line 12) adds the content of another bin, next to this bin (line 15). Finally, the method + (next: Array[Bin]): this.type (line 19) merges an array of bins into this bin (line 23-26).
Next let's create a class, Histogram (line 1) to manage the array of bins. The constructor for the histogram has four parameters
• maxNumBins maximum number of bin (line 2)
• min expected minimum value in the data set (line 3)
• max expected maximum value in the data set (line 4)
• optional smoothing weights (line 5)

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 final class Histogram( maxNumBins: Long, var min: Double = -1.0, var max: Double = 1.0, weights: Array[Float] = Array.empty[Float]) { val initNumBins: Int = (maxNumBins>>RADIX).toInt private var step = (max-min)/initNumBins private[this] var values = Range(0, initNumBins-1) .scanLeft(min + 0.5*step)((s, n) => s + step) ./:(new ArrayBuffer[Bin])( (vals, x) => vals += (new Bin(x)) ) def train(x: Double, y: Double): Unit = { <<(x) values(index(x)) += y if( values.size >= maxNumBins) >> } final def predict(x: Double): Double = { if( x < min || x > max) Double.NaN else if(weights.length > 0) smoothPredict(x) else values(index(x))._y } // ... ancillary methods } 

The two main methods are
• train (line 16) which updates a model (histogram) with each new data point from the training set. The histogram expands when a new data point exceeds the current boundary (min, max) of the histogram (line 19).
• predict (line 22) which predicts the value y of the new observation x. The prediction relies on an interpolation (weighted moving average) (line 24) in the case the user specifies an array of weights in the histogram constructor.
The method Histogram.index extracts the index of the bin containing a data point (x, y).

 1 2 3 4 5 6 private def index(x: Double): Int = { val idx = ((x - min)/step).floor.toInt if( idx < 1) 0 else if (idx >= values.size) values.size -1 else idx } 

This implementation of the dynamically resizable histogram, the array of bins expends by adding new bins if the new data point from the training set has a x value that is either greater that the current maximum value or lower than the current minimum value. The width of the bins, step does not change, only the current number of bins. The number of bins expanded until the maximum number of bins, maxNumBins. The method Histogram.<< Implements the expansion of the histogram for a constant bin width.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 private def >>(x: Double): Unit = if(x > max) { values.appendAll(generate(max, x)) max = values.last._x + step*0.5 } else if(x < min) { values.prependAll(generate(min, x)) min = values.head._x - step*0.5 } final def generate(limit: Double, x: Double): Array[Bin] = if( x > limit) { val nBins = ((x-limit)/step).ceil.toInt var z = limit - step*0.5 Array.tabulate(nBins)(_ => {z += step; new Bin(z) }) } else { val nBins = ((limit-x)/step).ceil.toInt var z = limit + step*0.5 Array.tabulate(nBins)(_ => {z -= step; new Bin(z) }) } 

Once the maximum number of bins maxNumBins is reached, the histogram is resized by halving the current width of the bin step. The consolidation of the histogram bins is implemented by the method Histogram.>>

 1 2 3 4 private def -- : Unit = values = (0 until values.size-1 by 2) ./:(new ArrayBuffer[Bin])( (ab, n) => ab += (values(n) + values(n+1))) 

Testing
Finally, the predictive method is used to compute the accuracy of the model, through the validate method. The histogram class is tested by loading a data set from file.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 def validate( hist: Histogram, fileName: String, eps: Double): Try[Double] = Try { val src = Source.fromFile(fileName) val fields = src.getLines.map( _.split(DELIM)) val counts = fields./:((0L, 0L))((s, xy) => if( Math.abs(hist.predict(xy(0).trim.toFloat)-xy(1).toFloat) < eps) (s._1 + 1L, s._2 + 1L) else (s._1, s._2 + 1L) ) val accuracy = counts._1.toDouble/counts._2 src.close accuracy } 

References
• Introduction to Machine Learning Chap 8 Nonparametric methods / Nonparametric density estimation E. Alpaydin- MIT press 2004
• Scala Cookbook A. Alexander O'Reilly 2013
• Histogram-based approximation using Apache Spark
• Introduction to Machine Learning Chap 8 Nonparametric methods / Nonparametric density estimation E. Alpaydin- MIT press 2004

#### 1 comment:

1. تعد الاول افضل شركة تنظيف خزانات بالمدينة المنورة تعمل على استخدام افضل ادوات تنظيف وتعقيم خزانات المياه