%matplotlib inline
import numpy as np
import matplotlib.pyplot as plt
from scipy import stats

# use seaborn plotting defaults
import seaborn as sns; sns.set()

from sklearn.datasets import make_blobs

X, y = make_blobs(n_samples=300, centers=4,
                  random_state=0, cluster_std=1.0)
plt.scatter(X[:, 0], X[:, 1], c=y, s=50, cmap='rainbow');

"""
Explanation: <i>Based mainly on the notebook of Jake Vanderplas for PyCon 2015 (GitHub), in addition to "Machine Learning" (chapter 3) by Tom Mitchell, "INTRODUCTORY APPLIED MACHINE LEARNING" lectures by Victor Lavrenko (VL), and Machine Learning  by Andrew Ng.</i>
Supervised Learning In-Depth: Random Forests
Decision Trees
Random forests are an example of a ensemble learner built on decision trees.
For this reason we'll start by discussing decision trees themselves.
Decision trees are extremely intuitive ways to classify or label objects: you simply ask a series of questions designed to zero-in on the classification.
 Data : 
Lets consider a simple example. The question we want to answer is will Mr. X play tennis based on a random's day weather conditions. The data set might look something like this:

Set up a simple classical decision tree:
We can split our data following different attributes to make a decision tree: 

ID3 Algorithm
1- Choose the best attribute A to split the node (starting at root)
2- For each value of A, create a new child node
3- Split for child nodes 
   --> if pure: STOP
   --> else: SPLIT
 Atribute selection 
The binary splitting (yes/No) makes this extremely efficient.
As always, though, the trick is to ask the right questions.
This is where the algorithmic process comes in: in training a decision tree classifier, the algorithm looks at the features and decides which questions (or "splits") contain the most information.
Selecting the right A to split the data is crucial. Algorithms will usually calculate the "Gain" in entropy of a split following A to evaluate its importance. The gain is the entropy of a parent node minus some averaging over the entropies of the child nodes after splitting over A.
Entropy H(S)=-P(+)log_2(P(+)) - P(-)log_2(P(-)) where S is the subset of the training example and P+/P- is the % of + or - examples in S.
Overfitting
Decision trees can continue to split until each node is in a pure state, at worse containing just 1 example. They can always perfectly fit the training data, thus reducing the accuracy on test examples. Decision trees can have a tendancy to overfit. 
Two possible solutions:
1- Stop spliting when the number of examples in a node is not statistically significant.
2- Grow the tree fully then post-pune unecessary nodes.

Few notes on DTs 
1- Decision trees can handle missing data.
2- Good decision trees implementations are immune to noise (irrelevant attributes), because it will have a low entropy gain value.
3- Can split data only parallel to axis (no diagonal splitting)
Creating a Decision Tree
Here's an example of a decision tree classifier in scikit-learn. We'll start by defining some two-dimensional labeled data:
End of explanation
"""


from fig_code import visualize_tree, plot_tree_interactive

"""
Explanation: We have some convenience functions in the repository that help
End of explanation
"""


plot_tree_interactive(X, y);

"""
Explanation: Now using IPython's interact (available in IPython 2.0+, and requires a live kernel) we can view the decision tree splits:
End of explanation
"""


from sklearn.tree import DecisionTreeClassifier
clf = DecisionTreeClassifier()

plt.figure()
visualize_tree(clf, X[:200], y[:200], boundaries=False)
plt.figure()
visualize_tree(clf, X[-200:], y[-200:], boundaries=False)

"""
Explanation: Notice that at each increase in depth, every node is split in two except those nodes which contain only a single class.
The result is a very fast non-parametric classification, and can be extremely useful in practice.
Question: Do you see any problems with this?
Decision Trees and over-fitting
One issue with decision trees is that it is very easy to create trees which over-fit the data. That is, they are flexible enough that they can learn the structure of the noise in the data rather than the signal! For example, take a look at two trees built on two subsets of this dataset:
End of explanation
"""


def fit_randomized_tree(random_state=0):
    X, y = make_blobs(n_samples=300, centers=4,
                      random_state=0, cluster_std=2.0)
    clf = DecisionTreeClassifier(max_depth=15)
    
    rng = np.random.RandomState(random_state)
    i = np.arange(len(y))
    rng.shuffle(i)
    visualize_tree(clf, X[i[:250]], y[i[:250]], boundaries=False,
                   xlim=(X[:, 0].min(), X[:, 0].max()),
                   ylim=(X[:, 1].min(), X[:, 1].max()))
    
from IPython.html.widgets import interact
interact(fit_randomized_tree, random_state=[0, 100]);

"""
Explanation: The details of the classifications are completely different! That is an indication of over-fitting: when you predict the value for a new point, the result is more reflective of the noise in the model rather than the signal.
Random Forests
One possible way to address over-fitting is to use an Ensemble Method: this is a meta-estimator which essentially averages the results of many individual estimators which over-fit the data. Somewhat surprisingly, the resulting estimates are much more robust and accurate than the individual estimates which make them up!
One of the most common ensemble methods is the Random Forest, in which the ensemble is made up of many decision trees which are in some way perturbed.
The basic idea behind a RF is simple :
1- Grow a number "K" of different Decision trees, randomised over both the subset of training examples and the subset of attributes. The DTs should be splitted all the way to the pure state with no punning.
2- Use all of them to make predictions on the test set, and follow the majority vote.
There are volumes of theory and precedent about how to randomize these trees, but as an example, let's imagine an ensemble of estimators fit on subsets of the data. We can get an idea of what these might look like as follows:
End of explanation
"""


from sklearn.ensemble import RandomForestClassifier
clf = RandomForestClassifier(n_estimators=100, random_state=0)
visualize_tree(clf, X, y, boundaries=False);

"""
Explanation: See how the details of the model change as a function of the sample, while the larger characteristics remain the same!
The random forest classifier will do something similar to this, but use a combined version of all these trees to arrive at a final answer:
End of explanation
"""


from sklearn.datasets import load_digits
digits = load_digits()
digits.keys()

X = digits.data
y = digits.target
print(X.shape)
print(y.shape)

"""
Explanation: By averaging over 100 randomly perturbed models, we end up with an overall model which is a much better fit to our data!
(Note: above we randomized the model through sub-sampling... Random Forests use more sophisticated means of randomization, which you can read about in, e.g. the scikit-learn documentation)
As you can see, the non-parametric random forest model is flexible enough to fit the multi-period data, without us even specifying a multi-period model!
Example: Random Forest for Classifying Digits
We previously saw the hand-written digits data. Let's use that here to test the efficacy of the SVM and Random Forest classifiers.
End of explanation
"""


# set up the figure
fig = plt.figure(figsize=(6, 6))  # figure size in inches
fig.subplots_adjust(left=0, right=1, bottom=0, top=1, hspace=0.05, wspace=0.05)

# plot the digits: each image is 8x8 pixels
for i in range(64):
    ax = fig.add_subplot(8, 8, i + 1, xticks=[], yticks=[])
    ax.imshow(digits.images[i], cmap=plt.cm.binary)
    
    # label the image with the target value
    ax.text(0, 7, str(digits.target[i]))

"""
Explanation: To remind us what we're looking at, we'll visualize the first few data points:
End of explanation
"""


from sklearn.cross_validation import train_test_split
from sklearn import metrics

Xtrain, Xtest, ytrain, ytest = train_test_split(X, y, random_state=0)

# Random Forest
RF1=RandomForestClassifier(n_estimators=100, criterion='gini', max_depth=None, min_samples_split=1, 
                              min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features='auto', 
                              max_leaf_nodes=None, bootstrap=True, oob_score=False, n_jobs=-1, random_state=None, 
                              verbose=0, warm_start=False, class_weight=None)
RF1.fit(Xtrain, ytrain)
ypred1 = RF1.predict(Xtest)



# Decision Tree
DT1 = DecisionTreeClassifier(max_depth=None)
DT1.fit(Xtrain, ytrain)
ypred2 = DT1.predict(Xtest)



"""
Explanation: We can quickly classify the digits using a decision tree as follows:
End of explanation
"""


metrics.accuracy_score(ypred1, ytest)

metrics.accuracy_score(ypred2, ytest)

"""
Explanation: We can check the accuracy of these classifiers:
End of explanation
"""


