Random Forests, Decision Trees và Ensemble Methods là gì?

Khái niệm Random forest lần đầu tiên được Breimen và đồng nghiệp đưa ra năm 2001, đây là một cách tiếp cận tổng thể để xây dựng các mô hình dự đoán. "Forest" trong phương pháp tiếp cận này là một chuỗi các cây quyết định (decision trees) đóng vai trò các phân loại "yếu" (weak) là những cá nhân dự đoán kém nhưng tổng hợp lại thành một dự đoán mạnh mẽ. Do tính chất đơn giản của chúng, thiếu các giả thuyết và nói chung có hiệu suất cao nên chúng được sử dụng trong mọi lĩnh vực áp dụng của Machine Lerning.

Random forests không đưa ra bất kỳ giả định nào về quy mô và tính quy tắc của dữ liệu input. Chúng hoạt động tốt với dữ liệu số hỗn hợp và phân loại, không cần đòi hỏi nhiều để có được phiên bản hợp lý đầu tiên của mô hình dự đoán, train nhanh, trực quan dễ hiểu, cung cấp tính năng quan trọng của mô hình, có khả năng để xử lý dữ liệu bị thiếu và được thực hiện trong mọi ngôn ngữ máy tính. Những đặc điểm này làm cho Random forests trở thành điểm khởi đầu tuyệt vời cho bất kỳ dự án nào mà bạn đang xây dựng mô hình dự đoán hoặc khám phá tính khả thi của việc áp dụng Machine learning vào một lĩnh vực mới.

1. Cây quyết định (a decision tree) là gì?

Để hiểu được Random forest, chúng ta cần biết được background về decision tree.

Các mô hình cây phân loại và hồi quy (classification and regression tree models) đã được Breimen và đồng nghiệp giới thiệu. Trong những mô hình này, cách tiếp cận top - down được áp dụng cho các dữ liệu quan trắc. Ý tưởng chung là đưa ra một tập hợp các quan trắc, câu hỏi sau đây được đặt ra: liệu có phải mọi biến mục tiêu trong tập hợp đều giống nhau (hoặc gần giống nhau) không? Nếu CÓ, gắn nhãn tập hợp các quan trắc với lớp tần suất cao nhất; nếu KHÔNG, tìm quy tắc tốt nhất để phân chia chúng thành hợp quan trắc thuần túy nhất.

2. Hoạt động như thế nào?

Dưới đây là một ví dụ để apply cho dữ liệu hoa iris .

Hoa Iris

from sklearn.datasets import load_iris from sklearn.tree import DecisionTreeClassifier,export_graphviz import graphviz iris_data = load_iris() model = DecisionTreeClassifier() model.fit(iris_data.data, iris_data.target) dot = export_graphviz(model, out_file=None, feature_names=iris_data.feature_names, class_names=iris_data.target_names, filled=True, impurity=None, ) graph = graphviz.Source(dot) graph.render("iris_decision_tree")

Trong cây này, quyết định xác định là một loài iris như sau:

Để đọc cây này, bắt đầu từ điểm cao nhất, sử dụng dòng đầu tiên để xác định cách quyết định phân chia các dữ liệu quan trắc thành 2 nodes mới như thế nào. Bây giờ chúng ta sử dụng decision tree này để phân loại các quan trắc mới.

Quan trắc 1

Một bông hoa có chiều rộng cánh hoa (petal width) là 0.7, chiều dài cánh hoa (petal length) là 1.0 và chiều dài vùng cuống (sepal width) là 3.0

Từ node gốc:

    * Is the petal width < 0.8 ?
                Yes -> go left.

Hoa này là loài setosa

Quan trắc 2

Một bông hoa có petal width of 0.9 , petal length of 1.0, and a sepal width of 3.0.

 Giải pháp

 Từ note gốc:

• Is the petal width less than or equal to 0.8 ?
  No -> go right.
• Is the petal width less than or equal to 1.75 ?
  Yes -> go left.
• Is the petal length less than or equal to 4.95 ?
  Yes -> go left.
• Is the petal width less than or equal to 1.65 ?
  Yes -> go left 
Hoa này là loài versicolor.

3. Hạn chế của decision trees

Mặc dù là tuyệt vời để tạo ra các mô hình dễ hiểu và thực hiện, các decision trees cũng có xu hướng phù hợp với dữ liệu training của chúng. Điều này làm cho chúng hoạt động kém nếu dữ liệu hiển thị sau đó không phù hợp với những gì chúng được training

Trong trường hợp đặc biệt của cây hồi quy (Regression trees), chúng cũng có thể chỉ dự đoán trong phạm vi gắn nhãn mà chúng quan sát trước đó, nghĩa là chúng có giới hạn  trên và dưới rõ ràng về số lượng chúng có thể tạo ra.

4. Ensemble Methods: Phương pháp tập hợp

Ensemble methods là các thuật toán kết hợp nhiều thuật toán lại thành một mô hình dự đoán duy nhất để giảm phương sai, giảm sai lệch hoặc cải thiện dự đoán.

Ensemble methods thường được chia thành 2 thể loại:

      1. Song song: Một ensemble method mà mô hình tạo nên các khối xây dựng của các phương thức lớn hơn được tạo ra độc lập với nhau (nghĩa là chúng có thể được training/ tạo ra các vấn đề song song áp dụng cho tập dữ liệu)

      2. Tuần tự: Một ensemble method trong đó phần learners được tạo theo thứ tự tuần tự và phụ thuộc vào nhau (nghĩa là, chúng chỉ có thể được training một lần, vì mô hình tiếp theo sẽ yêu cầu thông tin từ việc training ngược dòng của nó)

Thuật toán random forest dựa trên một phương pháp tập hợp song song gọi là "đóng gói" (Bagging) để tạo ra các phân loại yếu của nó.

Bagging (đóng gói)

Bagging là một thuật ngữ thông dụng để tổng hợp Bootstrap. Tổng hợp Bootstrap là một phương pháp cho phép chúng ta giảm phương sai của các ước tính bằng cách lấy trung bình nhiều ước tính được đo từ các mẫu con ngẫu nhiêu của tổng thể

Bootstrap sampling

Phần đầu tiên trong việc bagging là ứng dụng lấy mẫu bootstrap để ấy các tập hợp con của dữ liệu. Các tập hợp con này sau đó được đưa vào một mô hình bao gồm phương thức tập hợp cuối cùng. Đây là một quá trình đơn giản, được cung cấp một tập hợp dữ liệu quan trắc, n quan trắc được chọn ngẫu nhiêu và thay thế để tạo thành mẫu phụ (Subsample). Mẫu phụ này sau đó được đưa vào thuật toán Machine learning để lựa chọn mô hình training.

Aggregation

Sau khi tất cả các mô hình được xây dựng, các kết quả outputs phải được tổng hợp thành một dự đoán mạch lạc duy nhất cho mô hình lớn hơn. Trong trường hợp của một mô hình phân loại, đây thường chỉ một winners lấy mọi chiến lược mà bất cứ hạng mục nào nhật được nhiều votes nhất là kết quả cuối cùng được dự đoán. Trong trường hợp của một vấn đề hồi quy, sử dụng trung bình đơn giản các kết quả của các giá trị dự đoán.

------------

Feature Bagging

Feature bagging (or the random subspace method) is a type of ensemble method that is applied to the features (columns) of a dataset instead of to the observations (rows). It is used as a method of reducing the correlation between features by training base predictors on random subsets of features instead of the complete feature space each time.

How It Looks

A complete set of observations might be graphed as a joy plot and look like this:

The bagging method might then sample this observation repeatedly, creating a series of observations that look like these:

Each of the above distributions would then be fed into a distinct model for training.

The code to generate these plots is available here.

The Random Forest

Based on what was previously covered in decision trees and ensemble methods, it should come as little surprise as to where the random forest gets its name or how they’re constructed at a high-level, but let’s go over it anyways.

A random forest is comprised of a set of decision trees, each of which is trained on a random subset of the training data. These trees predictions can then be aggregated to provide a single prediction from a series of predictions.

Building A Random Forest

A random forest is built using the following procedure:

• Choose the number of trees you’d like in your forest (M)
• Choose the number of samples you’d like for each tree (n)
• Choose the number of features you’d like in each tree (f)
• For each tree in M:

• Select n samples with replacement from all observations
• Select f features at random
• Train a decision tree using the data set of n samples with f features
• Save the decision tree

How It Looks

First, lets remind ourselves what our data looks like as one entity:

Full Data

And now once we’ve applied the bagging methods to this dataset:

Subsamples of Observations

As you can see, the bootstrapping and feature bagging process produces wildly different decision trees than just the single decision tree applied to all of the data.

These multiple classifiers give us a number of things:

• A set of models that were trained without some features, meaning that in aggregate they’re able to make predictions even with missing data.
• A set of models that viewed different subsets of data, meaning that they’ve all gotten slightly different ideas of how to make decisions based on different ideas of what the population looks like. This means that in aggregate they’re able to make predictions even when the training data doesn’t look exactly like what we’re trying to predict.

How A Random Forest Makes A Prediction

• Given an observation (o).
• For each tree (t) in the model:
  • predict the outcome (p) using t applied to o
  • store p in list P
• If the model is a classifier:
  • return max_count(p)
• If the model is a regressor:
  • return avg(p)

Training a Random Forest

While you might be able to implement your own random forest from the ground up after going through this material, we will instead be using the scikit-learn implementation to go over how to train, make a prediction, and compare our random forest to a decision tree.

Note: The iris dataset doesn’t have enough variance to make a random forest a better model than just a simple decision tree so for this example we’ll be using the breast cancer dataset instead. 

from sklearn.tree     import DecisionTreeClassifier
from sklearn.ensemble import RandomForestClassifier
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.metrics import classification_report, confusion_matrix


bc = load_breast_cancer()
X = bc.data
y = bc.target

# Create our test/train split
X_train, X_test, y_train, y_test = train_test_split(X,y, random_state=42)


## build our models
decision_tree = DecisionTreeClassifier()
random_forest = RandomForestClassifier(n_estimators=100)

## Train the classifiers
decision_tree.fit(X_train, y_train)
random_forest.fit(X_train, y_train)

# Create Predictions
dt_pred = decision_tree.predict(X_test)
rf_pred = random_forest.predict(X_test)

# Check the performance of each model
print('Decision Tree Model')
print(classification_report(y_test, dt_pred, target_names=bc.target_names))

print('Random Forest Model')
print(classification_report(y_test, rf_pred, target_names=bc.target_names))

#Graph our confusion matrix
dt_cm = confusion_matrix(y_test, dt_pred)
rf_cm = confusion_matrix(y_test, rf_pred)

Decision Tree Model
             precision    recall  f1-score   support
          0       0.91      0.94      0.93        54
          1       0.97      0.94      0.95        89
avg / total       0.94      0.94      0.94       143
Random Forest Model
             precision    recall  f1-score   support
          0       0.96      0.94      0.95        54
          1       0.97      0.98      0.97        89
avg / total       0.97      0.97      0.96       143

It appears that based on common metrics of classification model performance, the random forest outperforms the decision tree.

Let’s see what the performance increase actually looks like (code here):

As you can see, we’re able to increase the number of correctly predicted benign tumors and decrease the number of benign tumors that are predicted as malignant. By using a random forest, we can more accurately predict the state of a tumor, potentially decreasing the amount of unneeded procedures performed on patients and decreasing patient stress about their diagnosis.

At this point, you’d usually start investigating hyperparameter tuning. This is a crucial part of the modeling process in order to ensure that your model is optimal. However, it is outside the scope of this article.

Feature Importance

Feature importance is used to describe how much impact a feature (column) has on how the model makes decisions. They’re used in order to help guide future work by concentrating on things we are certain will have impact and perhaps ignoring things that don’t, for simplifying models and preventing overfitting by removing columns that aren’t impactful enough to be generalized, and for helping explain why a model is making the decisions it does.

There are multiple methods for determining feature importance from a model. We’ll be covering how its calculated in the scikit-learn implementation. This method is popular because it's cheap to compute, does a reasonably good job of determining importance, and is already implemented.

Unsurprisingly, in order to calculate the feature importance of the forest, we need to calculate the feature importance of the individual trees and then find a way to combine them.

Gini Impurity

Gini impurity is a measure of the chance that a new observation when randomly classified would be incorrect. It is bounded between 0 and 1 (0 being impossible to be wrong and 1 being guaranteed to be wrong).

Gini impurity of a node is calculated with the following equation :

 

where ii is a predicted category and P(i)P(i) is the probability of a record being assigned to class ii at random.

Example Calculation

Based on our first decision tree :

The gini impurity for the top node is :

50/150 * (1 - 50/150) + 50/150 * (1 - 50/150) + 50/150 * (1 - 50/150) = .667

What would the Gini impurity of next node to the left be?

Solution

50/50 * 1 - (50/50)

+ 0/50 * 1 - ( 0/ 50 )

+ 0/50 * 1 - ( 0/ 50 )

= 0

Gini Importance

The Gini importance is the total reduction of the Gini Impurity that comes from a feature. It is calculated as the weighted sum of the difference in Gini Impurity between a node and its antecedents. It is calculated using the below equation:

 

Example Calculation

 

Based on our first decision tree:

The Gini importance of sepal width is :

3×0.44−(0+0)

 

What would the importance of petal length be?

Solution

54 * 0.168 - (48 * 0.041 + 6 * 0.444)

+ 46 * 0.043 - (0 + 3 * 0.444)

+ 3 * 0.444 - (0 + 0)

= 6.418

Once you have the Gini importance of each feature, you simply divide by the sum of each importance to get the normalized feature importance for the model.

What's the normalized feature importances from this model?

 

Solution

 

Sum of Gini Importances = 100.05

sepal length = 0 / 100.05 = 0

sepal width = 1.332 / 100.05 = 0.0133

petal length = 6.418 / 100.05 = 0.064

petal width = 92.30 / 100.05 = 0.922

Expanding To The Random Forest

Now that we can calculate feature importance for the weak learners, expanding it to the ensembled model is as simple as calculating the average importance for a feature from the trees as the importance of the random forest.

Getting Feature Importance Via Sklearn 

from sklearn.ensemble import RandomForestClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

iris = load_iris()
X = iris.data
y = iris.target

# Create our test/train split
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=42)

# build our model
random_forest = RandomForestClassifier(n_estimators=100)

# Train the classifier
random_forest.fit(X_train, y_train)

# Get our features and weights
feature_list = sorted(zip(map(lambda x: round(x, 2), random_forest.feature_importances_), iris.feature_names),
             reverse=True)

# Print them out
print('feature\t\timportance')
print("\n".join(['{}\t\t{}'.format(f,i) for i,f in feature_list]))
print('total_importance\t\t',  sum([i for i,f in feature_list]))

feature  importance
petal length (cm)  0.47
petal width (cm)  0.39
sepal length (cm)  0.1
sepal width (cm)  0.04
total_importance   1.0

Based on these weights, it's pretty clear that petal shape plays a big role in determining iris species. This might allow us to make recommendations about how we go about collecting data in the future (or not collecting data) or might give us some ideas about engineering new features around petal morphology to make our model better in the future.