%md
# [SDS-2.x, Scalable Data Engineering Science](https://lamastex.github.io/scalable-data-science/sds/2/x/)

%md

## Supervised Clustering with Decision Trees

### Visual Introduction to decision trees and application to hand-written digit recognition

**SOURCE:** This is just a couple of decorations on a notebook published in databricks community edition in 2016.

%md
# Decision Trees for handwritten digit recognition

This notebook demonstrates learning a [Decision Tree](https://en.wikipedia.org/wiki/Decision_tree_learning) using Spark's distributed implementation.  It gives the reader a better understanding of some critical [hyperparameters](https://en.wikipedia.org/wiki/Hyperparameter_optimization) for the tree learning algorithm, using examples to demonstrate how tuning the hyperparameters can improve accuracy.

**Background**: To learn more about Decision Trees, check out the resources at the end of this notebook.  [The visual description of ML and Decision Trees](http://www.r2d3.us/visual-intro-to-machine-learning-part-1/) provides nice intuition helpful to understand this notebook, and [Wikipedia](https://en.wikipedia.org/wiki/Decision_tree_learning) gives lots of details.

**Data**: We use the classic MNIST handwritten digit recognition dataset.  It is from LeCun et al. (1998) and may be found under ["mnist" at the LibSVM dataset page](https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/multiclass.html#mnist).

**Goal**: Our goal for our data is to learn how to recognize digits (0 - 9) from images of handwriting.  However, we will focus on understanding trees, not on this particular learning problem.

**Takeaways**: Decision Trees take several hyperparameters which can affect the accuracy of the learned model.  There is no one "best" setting for these for all datasets.  To get the optimal accuracy, we need to tune these hyperparameters based on our data.

%md
## Let's Build Intuition for Learning with Decision Trees

* Right-click and open the following link in a new Tab:
  * [The visual description of ML and Decision Trees](http://www.r2d3.us/visual-intro-to-machine-learning-part-1/) which was nominated for a [NSF Vizzie award](http://review.wizehive.com/voting/view/nsfvizziesgallery/27428/3236649).

//This allows easy embedding of publicly available information into any other notebook
//when viewing in git-book just ignore this block - you may have to manually chase the URL in frameIt("URL").
//Example usage:
// displayHTML(frameIt("https://en.wikipedia.org/wiki/Latent_Dirichlet_allocation#Topics_in_LDA",250))
def frameIt( u:String, h:Int ) : String = {
      """<iframe 
 src=""""+ u+""""
 width="95%" height="""" + h + """"
 sandbox>
  <p>
    <a href="http://spark.apache.org/docs/latest/index.html">
      Fallback link for browsers that, unlikely, don't support frames
    </a>
  </p>
</iframe>"""
   }
displayHTML(frameIt("https://en.wikipedia.org/wiki/Decision_tree_learning",500))

%md
## Load MNIST training and test datasets

Our datasets are vectors of pixels representing images of handwritten digits.  For example:

![Image of a digit](http://training.databricks.com/databricks_guide/digit.png)
![Image of all 10 digits](http://training.databricks.com/databricks_guide/MNIST-small.png)

%md
These datasets are stored in the popular LibSVM dataset format.  We will load them using MLlib's LibSVM dataset reader utility.

%md 
Display our data.  Each image has the true label (the `label` column) and a vector of `features` which represent pixel intensities (see below for details of what is in `training`).

%md
The pixel intensities are represented in `features` as a sparse vector, for example the first observation, as seen in row 1 of the output to `display(training)` or `training.show(2,false)` above, has `label` as `5`, i.e. the hand-written image is for the number 5.  And this hand-written image is the following sparse vector (just click the triangle to the left of the feature in first row to see the following):
```
type: 0
size: 780
indices: [152,153,155,...,682,683]
values: [3, 18, 18,18,126,...,132,16]
```

Here,

* `type: 0` says we have a sparse vector that only represents non-zero entries (as opposed to a dense vector where every entry is represented).
* `size: 780` says the vector has 780 indices in total 
 * these indices from 0,...,779 are a unidimensional indexing of the two-dimensional array of pixels in the image
* `indices: [152,153,155,...,682,683]` are the indices from the `[0,1,...,779]` possible indices with non-zero values 
  * a value is an integer encoding the gray-level at the pixel index
* `values: [3, 18, 18,18,126,...,132,16]` are the actual gray level values, for example:
  * at pixed index `152` the gray-level value is `3`, 
  * at index `153` the gray-level value is `18`,
  * ..., and finally at
  * at index `683` the gray-level value is `18`

%md
## Train a Decision Tree

We begin by training a decision tree using the default settings.  Before training, we want to tell the algorithm that the labels are categories 0-9, rather than continuous values.  We use the `StringIndexer` class to do this.  We tie this feature preprocessing together with the tree algorithm using a `Pipeline`.  ML Pipelines are tools Spark provides for piecing together Machine Learning algorithms into workflows.  To learn more about Pipelines, check out other ML example notebooks in Databricks and the [ML Pipelines user guide](http://spark.apache.org/docs/latest/ml-guide.html). Also See [mllib-decision-tree.html#basic-algorithm](http://spark.apache.org/docs/latest/mllib-decision-tree.html#basic-algorithm).

%md

See [http://spark.apache.org/docs/latest/mllib-decision-tree.html#basic-algorithm](http://spark.apache.org/docs/latest/mllib-decision-tree.html#basic-algorithm).

%md
Now, let's fit a model to our data.

%md
We can inspect the learned tree by displaying it using Databricks ML visualization.  (Visualization is available for several but not all models.)

%md
Above, we can see how the tree makes predictions.  When classifying a new example, the tree starts at the "root" node (at the top).  Each tree node tests a pixel value and goes either left or right.  At the bottom "leaf" nodes, the tree predicts a digit as the image's label.

%md
## Hyperparameter Tuning
Run the next cell and come back into hyper-parameter tuning for a couple minutes.

displayHTML(frameIt("https://en.wikipedia.org/wiki/Hyperparameter_optimization", 400))

%md
## Exploring "maxDepth": training trees of different sizes

In this section, we test tuning a single hyperparameter `maxDepth`, which determines how deep (and large) the tree can be.  We will train trees at varying depths and see how it affects the accuracy on our held-out test set.

*Note: The next cell can take about 1 minute to run since it is training several trees which get deeper and deeper.*

%md

We will use the default metric to evaluate the performance of our classifier:

 * [https://en.wikipedia.org/wiki/F1_score](https://en.wikipedia.org/wiki/F1_score).

//This allows easy embedding of publicly available information into any other notebook
//when viewing in git-book just ignore this block - you may have to manually chase the URL in frameIt("URL").
//Example usage:
// displayHTML(frameIt("https://en.wikipedia.org/wiki/Latent_Dirichlet_allocation#Topics_in_LDA",250))
def frameIt( u:String, h:Int ) : String = {
      """<iframe 
 src=""""+ u+""""
 width="95%" height="""" + h + """"
 sandbox>
  <p>
    <a href="http://spark.apache.org/docs/latest/index.html">
      Fallback link for browsers that, unlikely, don't support frames
    </a>
  </p>
</iframe>"""
   }
displayHTML(frameIt("https://en.wikipedia.org/wiki/F1_score",400))

%md
We can display our accuracy results and see immediately that deeper, larger trees are more powerful classifiers, achieving higher accuracies.

*Note:* When you run `f1MetricPerformanceMeasures.show()`, you will get a table with f1 score getting better (i.e., approaching 1) with depth.

%md
Even though deeper trees are more powerful, they are not always better (recall from the SF/NYC city classification from house features at  [The visual description of ML and Decision Trees](http://www.r2d3.us/visual-intro-to-machine-learning-part-1/)).  If we kept increasing the depth on a rich enough dataset, training would take longer and longer.  We also might risk [overfitting](https://en.wikipedia.org/wiki/Overfitting) (fitting the training data so well that our predictions get worse on test data); it is important to tune parameters *based on [held-out data](https://en.wikipedia.org/wiki/Test_set)* to prevent overfitting. This will ensure that the fitted model generalizes well to yet unseen data, i.e. minimizes [generalization error](https://en.wikipedia.org/wiki/Generalization_error) in a mathematical statistical sense.

%md
## Exploring "maxBins": discretization for efficient distributed computing

This section explores a more expert-level setting `maxBins`.  For efficient distributed training of Decision Trees, Spark and most other libraries discretize (or "bin") continuous features (such as pixel values) into a finite number of values.  This is an important step for the distributed implementation, but it introduces a tradeoff: Larger `maxBins` mean your data will be more accurately represented, but it will also mean more communication (and slower training).

The default value of `maxBins` generally works, but it is interesting to explore on our handwritten digit dataset.  Remember our digit image from above:

![Image of a digit](http://training.databricks.com/databricks_guide/digit.png)

It is grayscale.  But if we set `maxBins = 2`, then we are effectively making it a black-and-white image, not grayscale.  Will that affect the accuracy of our model?  Let's see!

*Note: The next cell can take about 35 seconds to run since it trains several trees.*
Read the details on `maxBins` at [mllib-decision-tree.html#split-candidates](http://spark.apache.org/docs/latest/mllib-decision-tree.html#split-candidates).

%md

See [http://spark.apache.org/docs/latest/mllib-decision-tree.html#split-candidates](http://spark.apache.org/docs/latest/mllib-decision-tree.html#split-candidates).

%md
We can see that extreme discretization (black and white) hurts performance as measured by F1-error, but only a bit.  Using more bins increases the accuracy (but also makes learning more costly).