One of the issues data scientists run into the most frequently is the classification issue. We can separate the available data into discrete values with the use of classification. Numerous algorithms exist that enable us to solve this issue efectively. This article focuses on tree-based algorithms: Decision Tree Algorithm, and Random Forest Algorithm. The problem that is going to be approached with these algorithms is cardiovascular disease prediction, using the kaggle dataset containing records of patients data [1].
These numbers might go even higher in incoming
years. The ongoing COVID pandemic, widespread
lockArtificial intelligence methods [
American statistician Leo Breiman was born in New York, USA, in 1928. At the University of California, Leo Breiman pursued his education. Breiman is primarily recognized for his work on CART, Bootstrap Aggregation, which owes its name to him and is now known as Bagging. Leo Breiman is also the inventor of Random Forest method.
The CART algorithm builds decision trees utilizing the Gini’s Impurity Index to create best possible splits of data.
The Gini’s Ratio is a statistical dispersion metric that is frequently used to assess income disparity between countries. Gini’s Impurity is a measure of the likelihood of choosing a certain feature that is incorrectly classified in decision trees. If all element in a dataset are of a single class, then Gini’s Index takes the value of 0, meaning that that the dataset is pure. Similarly, if all elements of dataset are of diferent classes, then Gini’s Index takes the value of 1, which indicates that the dataset is fully impure. If Gini’s Index is of value 0.5, then the dataset is shows an equal distribution of elements over available classes.
Gini Index can be represented as:
Gini Index = 1 − ∑︁ ()2, =1
Where represents the probability of each element being classified for its distinct class.
In CART decision trees Gini’s Index is used to calculate the best possible split at each level of the tree.
The process of classifying the components of a set made up of only two classes is known as binary classification.
The main applications of binary classification are in quality control and medical testing to check if a patient is ill or not, and to assess whether a produced thing fulfills the specification.
Some of the most common methods used for solving the binary classification problems are Decision Trees, Random Forests and Logistic Regression.
The Decision Tree Algorithm makes use of a binary tree data structure, where each node is either a decision node that is divided based on the best potential Gini Index, or a terminal node which does not further split, and decide about the predictions made by the decision tree. Decision Trees are often described using flowcharts.
The best possible split is calculated for each node individually, by checking all the possible values in each available feature. The pair of value + feature for which the best Gini’s Index gain was achieved is used for split2. Proposed Classifiers ting the dataset further into two parts. Decision Tree is built and read recursively, thanks to 2.1. Decision Tree the underlying data structure. Building the entire tree for a classifier involves using the training data that has Decision Trees are among the most commonly used mod- been provided to determine the appropriate splits. It is els for classification and regression tasks. They can be important to adequately adjust the classifier parameters, described as a model whose purpose is to ask a dataset a such as maximum depth, or the minimum number of list of if/else questions, and based on the responses the samples required for performing a split. decision can be then made. The maximum depth parameter specifies how deep
Decision Trees are often divided into two categories: the decision tree can get - it is the number of nodes from classification and regression trees. Regression Trees pro- the root down to the furthest leaf node - the height of duce numeric output, and classification trees produce underlying tree structure. categorical output. The latter is the main interest of this Theoretically the maximum depth of the decision tree article, more specifically the CART implementation of could be almost as high as the number of training samples, decision trees. however it is not recommended to let the Decision Tree
Input TR: Training Samples, MaxDepth: Maximum Depth of the Decision Tree
Output Decision Tree built based on provided training samples Building Decision Tree 1: if stopping conditions are met then 2: a leaf node with adequate class assigned
to it 3: else 4: = best possible Gini Gain 5: if > 0 then 6: recursively build left side of the current node 7: recursively build right side of the current node ber of decision trees. Random Forests rely on a lot of relatively unrelated - thanks to the randomly choosing of samples - trees, classifying the provided sample using each one and performing a majority vote to get the best possible result.
The evaluation of the sample provided by ensemble algorithms typically requires more computing resources than it would for a single model, but the ’Wisdom of Crowds’ obtained by using multiple models leads to increased accuracy. 8:
current node with both sides as- 2.2.2. Bagging signed to it
Bagging, also known as bootstrap aggregation, is an enPredicting sample labels semble learning technique that is used to improve stabilInput xTest: testing samples ity and accuracy, and to reduce variance within a dataset Output Predicted labels - decreasing the chance of overfitting models. Using bagging, Random Forests produce a variety of 1: for do trees by letting each one randomly select a sample from a 2: if currently checked node has a class value as- given dataset. Creating a large number of decision trees signed to it then helps in reducing overfitting. 3: assigned class value
5: if currently tested node has key feature value greater than checked sample then 6: recursively check left child of node 7: recursively check right side of node Building a Random Forest Input Training Samples, Number of trees
Output Random Forest built based on provided samples classifier grow to depth that high, because then it will overfit.
Data scientists use the term "overfitting" to indicate when the results of an analysis fit a set of data too closely. Such algorithm can perform very well on training data, but when exposed to an unknown sample, it will attempt to categorize it using highly specific criteria that may not be appropriate for classifying the unknown samples. The depth parameter should not be set too high because a model that has been trained too precisely on a given dataset will be fitted to that dataset exactly, which means it will learn not only how to make decisions based on the important features and their values but also how to take into account the existing "noise" - irrelevant information.
If there is more then a single sample present at a leaf node, then the outcome is predicted using the Majority Voting technique, where the class which has the highest number of representing samples is chosen.
Random Forest is an ensemble classification algorithm that performs classification using a predetermined num1: for range(Number of trees) do 2: choose random subsample 3: create a Decision Tree using the chosen subsample Classifying using Random Forest Input Test Samples
Output Classified sample labels 1: for Every test sample do 2: for Every built tree do 3: Classify sample using currently checked Decision Tree 4: Perform majority voting based on results of classifying the chosen sample using all decision trees 5: Classified samples
Each tree in Random Forest is built using randomly chosen data from dataset. When predicting the outcome of provided sample, the sample is provided to every available tree, and then the results from all the classifications are subjected to the Majority Voting technique, where the
The Cardiovascular Disease Dataset consists of 70000 records of patients data, consisting of 11 features each: 1. Age 2. Height 3. Weight 4. Gender 5. Systolic blood pressure 6. Diastolic blood pressure 7. Cholesterol 8. Glucose 9. Smoking 10. Alcohol intake 11. Physical activity
The process of detecting and fixing even removing, corrupted, duplicate, or incomplete data is known as data cleaning.
In the used dataset there is a number of invalid records, such as records of patients with systolic blood pressure that is negative or exceding 16000. Removal of such records allowed for reducing the total number of samples by 1413 records.
Dimensionality reduction is the process of minimizing the number of dimensions - features present in a dataset, while preserving the greatest amount of variety. Reducing the number of features accessible can increase performance, eliminate redundancy, and reduce overfitting.
Dimensionality reduction works by identifying and deleting elements that have little to no impact on the outcomes.
Dataset needs to be split into the training data, and testing data. Most of the data should be used for training purposes.
After a model has been trained using the training set, it’s accuracy can then be validated using data from testing set. Because class values in testing set are already known, the accuracy of classifiers can be correctly calculated.
5.1.1. P P is the number of real positive conditions
N is the number of real negative conditions 5.1.2. N 5.1.3. TP 5.1.4. TN 5.1.5. FP 5.1.6. FN TP is the number of correctly predicted presence of a condition.
TN is the number of correctly predicted absence of a condition FP is the number of wrongly predicted presence of a condition FN is the number of wrongly predicted absence of a condition
These four correctness measure metrics are the parameters of confusion matrix, they are used to evaluate specificity, sensitivity and accuracy of classifiers.
The simplest evaluation metric is accuracy. It measures how accurately projected classes compare to the whole testing dataset size. The number of labels that were successfully assigned is known as accuracy.
ACC = + +
Precision is defined as the ratio of true positives to the sum of true positives and false positives. Precision describes how efectively the model predicts the positive cases out of all the cases it predicts as being true.
PPV =
+ 5.1.9. Recall The proportion of genuine positives to the total of true positives and false negatives is known as recall. Recall demonstrates how well the model separates out the positive cases from all the positive cases in the dataset.
TPR =
+ 5.1.10. F1 The harmonic mean of recall and precision is the 1 score.
* * +
Confusion Matrix is a performance measurement technique, as the name suggests - it is a matrix, representing four diferent combinations of predicted and actual values. Its name comes from the fact that using this matrix makes it easier to determine whether the model is incorrectly classifying classes.
︂( )︂
Single Decision Trees quickly began to overfit, increasing the maximum depth not only decreased the correctness of it’s predictions, but also increased the total time needed for building the tree. The problem of overfitting can be ifxed by utilizing the bagging technique.
The main parameters in Random Forest Classifier that needs to be adjusted are the total number of trees, as well as the maximum depth of every single tree. 42–51
Increasing the total number of trees increased the correctness of Random Forest classifier. Even with low total amount of trees Random Forest classifier has better correctness than a single Decision Tree, bagging helps with overfitting, the choosing of random samples helps the classifier to learn the training dataset better.
Correctness measured for Random Forest Classifier with total number of trees equal to 25, and the maximum depth of trees equal to 2 were: = 0.66 = 0.74 = 0.64
Correctness measured for Random Forest Classifier with total number of trees equal to 25, and the maximum depth of trees equal to 4 were: = 0.67 = 0.79 = 0.63 Correctness measured for Random Forest Classifier with total number of trees equal to 25, and the maximum depth of trees equal to 16 were: = 0.6 = 0.61 = 0.59
Correctness measured for Random Forest Classifier with total number of trees equal to 25, and the maximum depth of trees equal to 128 were: = 0.62 = 0.61 = 0.61
Changes in the maximum depth of individual trees did not afect the Random Forest classifier as much as the total amount of trees.
The nature of disease prediction problem makes it suitable to use tree-based algorithms for patient classification. The proposed algorithms show good correctness. The presented tests have shown that the proper selection of classifiers has a great efect on the classification results. Decision Trees alone can predict reasonably well, however utilizing bagging algorithms such as Random Forest can increase the correctness of acquired results, sacrificing a little execution speed.