Introduction
Related work
The proposed DMRF algorithm
Classification DMRF
Training sample sampling
Split point training process
Leaf node label determination
Strong consistency proof of classification DMRF
Regression DMRF
Regression DMRF Algorithm
Strong consistency proof of regression DMRF
Experiment
Dataset selection
Data sets | Samples | Features | Classes |
---|---|---|---|
Blogger | 100 | 6 | 2 |
Bone marrow | 187 | 39 | 2 |
Algerian forest fires | 244 | 12 | 2 |
Vertebral | 310 | 6 | 3 |
Chronic kidney disease | 400 | 25 | 2 |
Cvr | 435 | 16 | 2 |
House-votes | 453 | 16 | 2 |
Wdbc | 569 | 39 | 2 |
Breast original | 699 | 10 | 2 |
Balance scale | 625 | 4 | 3 |
Raisin | 900 | 8 | 2 |
Vehicle | 946 | 18 | 4 |
Tic-tac-toe | 958 | 9 | 2 |
HCV | 1385 | 28 | 4 |
Winequality (red) | 1599 | 11 | 7 |
Wireless | 2000 | 7 | 4 |
Obesity | 2111 | 17 | 7 |
Ad | 3279 | 1558 | 2 |
Spambase | 4601 | 57 | 2 |
Winequality (white) | 4898 | 11 | 7 |
Page blocks | 5473 | 10 | 5 |
MFCCs | 7195 | 22 | 4 |
Mushroom | 8124 | 22 | 7 |
Ai4i | 10000 | 14 | 3 |
Letter | 20000 | 16 | 26 |
Adult | 48842 | 14 | 2 |
Connect-4 | 67557 | 42 | 3 |
Datasets | Samples | Features |
---|---|---|
ALE | 107 | 6 |
Alcohol | 125 | 8 |
Servo | 167 | 4 |
CSM | 217 | 12 |
Real estate | 414 | 7 |
Facebook | 500 | 19 |
Las Vegas Strip | 504 | 20 |
Forest fire | 517 | 13 |
ISTANBUL STOCK | 536 | 8 |
Qsar fish toxicity | 908 | 7 |
Concrete | 1030 | 9 |
Qsar BCF Kow | 1056 | 7 |
Flare | 1389 | 10 |
Communities | 1994 | 128 |
Skillcraft | 3395 | 20 |
Winequality (white) | 4898 | 11 |
Parkinsons | 5875 | 26 |
SeoulBikeData | 8760 | 14 |
Insurance | 9000 | 86 |
Combined | 9568 | 4 |
Cbm | 11934 | 16 |
Baselines
Performance test experimental settings
Standard deviation analysis
Parameter test experimental settings
Results and discussion
Performance analysis
Classification
-
In the majority of cases, the (b)-type models show higher accuracy compared to their corresponding (SE)-type models (for example, MRF(b) achieves a 9% higher accuracy than MRF(SE) on the Winequality (white) dataset). This suggests that when the splitting criterion and leaf node label determination process are independent, a significant amount of information may be lost. Determining the leaf node labels based on the samples used to compute the splitting point helps reduce information loss.
-
In all datasets, DMRF generally outperforms other RF variations, and the advantage of DMRF over MRF(b) is particularly evident with an improvement of 1% observed on some datasets (such as Obesity and Ai4i).
-
In most cases, the accuracy of DMRF is higher than BreimanRF. This can be attributed to the use of the multinomial distribution for randomly sampling splitting values can be seen as a weakened version of optimal splitting, which enhances robustness. It indicates that introducing some randomness in classification tasks can enhance performance.
Datasets | DMRF | MRF(SE) | MRF(b) | BRF(SE) | BRF(b) | Denil14(SE) | Denil14(b) | BreimanRF |
---|---|---|---|---|---|---|---|---|
Blogger | 81.8* | 76.2 | 79.9 | 78.3 | 81.2 | 75.8 | 80.5 | 81.4 |
Bone marrow | 93.96* | 93.56 | 93.71 | 93.53 | 93.86 | 93.92 | 93.45 | 93.42 |
Algerian Forest Fires | 93.03* | 92.25 | 92.16 | 92.71 | 93.71 | 92.45 | 92.46 | 93 |
Vertebral | 84.39 | 83.19 | 83.58 | 83.74 | 84.35 | 82.74 | 82.74 | 84.64* |
Chronic kidney disease | 98.80* | 98.13 | 98.6 | 98.23 | 98.65 | 98.23 | 98.48 | 98.77 |
Cvr | 96.19* | 95.49 | 95.61 | 95.91 | 96.16 | 95.63 | 95.74 | 95.84 |
House-votes | 96.17* | 95.67 | 95.49 | 95.58 | 95.89 | 95.66 | 95.67 | 95.87 |
Wdbc | 96.25* | 95.58 | 96.22 | 95.12 | 95.96 | 95.55 | 96.08 | 94.18 |
Breast original | 95.88 | 95.29 | 95.48 | 95.48 | 95.72 | 94.45 | 94.69 | 96.71* |
Balance scale | 83.45 | 80.58 | 77.64 | 81.83 | 83.46 | 80.15 | 77.02 | 86.19* |
Raisin | 86.22* | 85.47 | 85.94 | 85.60 | 86.02 | 86.16 | 85.53 | 84.98 |
Vehicle | 75.63* | 73.24 | 75.60 | 72.79 | 74.44 | 73.04 | 74.55 | 74.46 |
Tic-tac-toe | 98.27* | 98.47 | 98.85 | 98.18 | 98.08 | 97.82 | 98.38 | 94.37 |
HCV | 23.84 | 23.55 | 23.66 | 23.25 | 23.28 | 23.28 | 23.22 | 24.88* |
Winequality (red) | 69.83* | 62.47 | 69.57 | 62.48 | 69.75 | 62.08 | 69.49 | 64.70 |
Wireless | 98.36* | 98.28 | 98.33 | 98.2 | 98.18 | 97.78 | 97.97 | 98.33 |
Obesity | 78.54 | 24.41 | 77.34 | 71.35 | 78.51 | 73.28 | 77.20 | 94.42* |
Ad | 97.66* | 96.76 | 97.95 | 94.43 | 97.46 | 94.16 | 96.98 | 97.02 |
Spambase | 95.18* | 93.6 | 95.01 | 93.93 | 95.02 | 91.48 | 95.1 | 91.82 |
Winequality (white) | 69.21* | 59.93 | 69.20 | 60.65 | 69.44 | 60.07 | 68.71 | 64.02 |
Page blocks | 97.59* | 97.44 | 97.56 | 97.17 | 97.45 | 97.28 | 97.44 | 97.06 |
MFCCs | 98.53* | 98.02 | 98.5 | 98.02 | 98.47 | 97.83 | 98.36 | 63.57 |
Mushroom | 57.24* | 59.98 | 47.42 | 62.10 | 58.67 | 58.99 | 48.54 | 47.28 |
Ai4i | 59.96* | 59.5 | 57.01 | 59.4 | 59.95 | 59.6 | 56.66 | 56.15 |
Letter | 89.79 | 89.55 | 89.58 | 83.05 | 89.00 | 81.78 | 87.50 | 96.32* |
Adult | 86.45* | 86.28 | 86.13 | 57.57 | 86.44 | 86.19 | 85.57 | 85.98 |
Connect-4 | 82.18* | 81.96 | 84.08 | 78.86 | 80.77 | 81.28 | 83.44 | 81.46 |
Regression
-
Similar to the classification case, in the majority of cases, the (b)-type models outperform their corresponding (SE)-type models (for example, there is an 48% reduction in MSE on the Real estate dataset). This suggests that determining the leaf node labels based on the samples used to compute the splitting point can better utilize information compared to the independent processes.
-
In all datasets, DMRF generally shows the best performance among RF variations, but the advantage of DMRF over MRF(b) is not significant.
-
In most cases, the MSE of DMRF is larger than that of BreimanRF. This is because MSE amplifies the impact of noise, and the randomness introduced by the multinomial distribution makes DMRF perform worse in regression compared to BreimanRF. In contrast, DMRF is better suited for classification tasks.
Datasets | DMRF | MRF(SE) | MRF(b) | BRF(SE) | BRF(b) | Denil14(SE) | Denil14(b) | BreimanRF |
---|---|---|---|---|---|---|---|---|
ALE | 0.0474 | 0.0758 | 0.0494 | 0.0921 | 0.4890 | 0.0931 | 0.0516 | 0.0423* |
Alcohol | 0.0023* | 0.0068 | 0.0025 | 0.0049 | 0.0025 | 0.0033 | 0.0024 | 0.0028 |
Servo | 0.3644 | 0.4248 | 0.2543 | 0.6864 | 0.4247 | 0.7832 | 0.2538 | 0.3114* |
CSM | 0.0204* | 0.0711 | 0.0206 | 0.1681 | 0.0209 | 0.0495 | 0.0244 | 0.0239 |
Real estate | 55.060 | 106.919 | 55.628 | 118.417 | 61.783 | 110.264 | 93.836 | 53.699* |
Facebook | 0.0510 | 0.7594 | 0.0637 | 1.0288 | 0.0546 | 0.8786 | 0.0546 | 0.0465* |
Las Vegas Strip | 0.9942 | 1.001 | 1.016 | 1.015 | 1.014 | 1.167 | 1.072 | 0.9826* |
Forest fire | 2.073* | 2.159 | 2.191 | 2.166 | 2.164 | 2.166 | 2.156 | 2.232 |
ISTANBUL STOCK | 2.14E-04* | 3.88E-04 | 2.21E-04 | 4.15E-04 | 4.14E-04 | 4.40E-04 | 3.33E-04 | 2.20E-04 |
Qsar fish toxicity | 0.7794* | 1.047 | 0.7592 | 2.0185 | 0.9218 | 1.9508 | 0.9441 | 1.241 |
Concrete | 40.080 | 128.167 | 27.749 | 256.478 | 36.889 | 259.715 | 42.966 | 23.869* |
Qsar BCF Kow | 0.7401 | 1.5096 | 0.7695 | 1.4094 | 0.7514 | 1.4111 | 1.1961 | 0.5152* |
Flare | 0.5219* | 0.5222 | 0.5937 | 0.5426 | 0.5227 | 0.5684 | 0.6013 | 0.5981 |
Communities | 0.0203 | 0.0372 | 0.0205 | 0.0521 | 0.2049 | 0.0499 | 0.0244 | 0.0182* |
Skillcraft | 4.37E-08 | 6.54E-08 | 4.39E-08 | 6.95E-08 | 5.34E-08 | 7.02E-08 | 5.64E-08 | 4.23E-08* |
Winequality (white) | 0.3562* | 0.6177 | 0.3601 | 0.7749 | 0.3815 | 0.7311 | 0.3949 | 0.3640 |
Parkinsons | 0.0013* | 0.0029 | 0.0014 | 0.0078 | 0.0016 | 0.0045 | 0.0016 | 0.0013* |
SeoulBikeData | 0.2059 | 0.6722 | 0.207 | 1.4543 | 0.3664 | 1.2996 | 0.8322 | 0.1782* |
Insurance | 0.0585 | 0.0559 | 0.0596 | 0.0561 | 0.0549 | 0.0561 | 0.0601 | 0.0554* |
Combined | 11.700 | 15.371 | 11.716 | 48.995 | 12.445 | 26.054 | 14.445 | 10.819* |
Cbm | 1.00E-06 | 8.00E-06 | 1.00E-06 | 5.55E-05 | 1.50E-05 | 5.61E-05 | 2.00E-06 | 7.95E-07* |
Standard deviation analysis
Task | Datasets | DMRF | MRF(SE) | MRF(b) | BRF(SE) | BRF(b) | Denil14(SE) | Denil14(b) | BreimanRF |
---|---|---|---|---|---|---|---|---|---|
Classification | Blogger | 0.9189 | 1.4757 | 2.0789 | 2.3593 | 2.0439 | 1.3984 | 2.0138 | 2.1832 |
Algerian Forest Fires | 0.2907 | 0.4842 | 0.7431 | 0.5495 | 0.4650 | 0.3465 | 0.8440 | 0.5922 | |
Wdbc | 0.2153 | 0.3031 | 0.3751 | 0.4283 | 0.3108 | 0.1860 | 0.2476 | 0.4878 | |
Tic-tac-toe | 0.1494 | 0.1980 | 0.2642 | 0.1492 | 0.3619 | 0.1690 | 0.2748 | 0.2433 | |
Winequality (Red) | 0.3718 | 0.4873 | 0.6304 | 0.5572 | 0.4748 | 0.4111 | 0.5347 | 0.4871 | |
Wireless | 0.1054 | 0.0919 | 0.1061 | 0.0422 | 0.1752 | 0.0577 | 0.1414 | 0.1006 | |
Winequality (white) | 0.3107 | 0.2374 | 0.2595 | 0.3072 | 0.2987 | 0.1558 | 0.2839 | 0.2856 | |
Connect-4 | 0.0629 | 0.0349 | 0.0627 | 0.0594 | 0.0591 | 0.0262 | 0.0745 | 0.0556 | |
Regression | ALE | 0.002513 | 0.002303 | 0.002802 | 0.002485 | 0.002053 | 0.001867 | 0.003254 | 0.002637 |
Servo | 0.0477 | 0.0158 | 0.0200 | 0.0568 | 0.0846 | 0.0201 | 0.0790 | 0.0601 | |
Las Vegas Strip | 0.0094 | 0.0038 | 0.0162 | 0.0021 | 0.3846 | 0.0011 | 0.0333 | 0.0173 | |
Qsar fish toxicity | 0.0105 | 0.0117 | 0.0081 | 0.0116 | 0.0205 | 0.0087 | 0.0131 | 0.0247 | |
Flare | 0.003023 | 0.004029 | 0.011366 | 0.001570 | 0.004659 | 0.000626 | 0.0101 | 0.005616 | |
Winequality (white) | 0.003234 | 0.002213 | 0.003777 | 0.001211 | 0.002729 | 0.001602 | 0.005282 | 0.003536 | |
Insurance | 1.91E-04 | 1.64E-04 | 2.27E-04 | 9.17E-06 | 1.18E-04 | 7.57E-06 | 4.22E-04 | 1.85E-04 | |
Combined | 0.0738 | 0.0353 | 0.0595 | 0.4213 | 0.0636 | 0.1011 | 0.0709 | 0.0689 |
Parameter analysis
The effect of \(p\), \(q\)
Classification
Regression
The effect of \(B_{1}\), \(B_{2}\)
Classification
Regression
The effect of Μ
The effect of \(k_{n}\)
Cross-validation
Task | Dataset | Algorithm | Performance | Optimal parameters |
---|---|---|---|---|
Classification | Blogger | DMRF | 84.8 |
\(B_{1} = 5,B_{2} = 8,p = 0.3,q = 0.8\)
|
MRF(b) | 84 |
\(B_{1} = 8,B_{2} = 5,q = 0.8\)
| ||
BRF(b) | 84.2 |
\(p_{1} = 0.05,p_{2} = 0.35,q = 0.8\)
| ||
Denil14(b) | 83.2 |
\(\lambda = 10,m = 500,q = 0.8\)
| ||
Vertebral | DMRF | 84.76 |
\(B_{1} = 2,B_{2} = 2,p = 0.5,q = 0.8\)
| |
MRF(b) | 84.58 |
\(B_{1} = 2,B_{2} = 10,q = 1 - 1/e\)
| ||
BRF(b) | 84.6 |
\(p_{1} = 0.05,p_{2} = 0.35,q = 1 - 1/e\)
| ||
Denil14(b) | 84.45 |
\(\lambda = 10,m = 200,q = 0.4\)
| ||
House votes | DMRF | 96.26 |
\(B_{1} = 2,B_{2} = 8,p = 0.3,q = 0.8\)
| |
MRF(b) | 96.16 |
\(B_{1} = 2,B_{2} = 2,q = 0.4\)
| ||
BRF(b) | 96.14 |
\(p_{1} = 0.05,p_{2} = 0.65,q = 1 - 1/e\)
| ||
Denil14(b) | 95.85 |
\(\lambda = 10,m = 50,q = 0.4\)
| ||
Regression | ALE | DMRF | 0.0436 |
\(B_{1} = 8,B_{2} = 10,p = 0.5,q = 0.4\)
|
MRF(b) | 0.0443 |
\(B_{1} = 8,B_{2} = 2,q = 1 - 1/e\)
| ||
BRF(b) | 0.0451 |
\(p_{1} = 0.01,p_{2} = 0.01,q = 0.4\)
| ||
Denil14(b) | 0.0443 |
\(\lambda = 5,m = 50,q = 0.4\)
| ||
Real estate | DMRF | 51.54 |
\(B_{1} = 5,B_{2} = 2,p = 0.3,q = 0.8\)
| |
MRF(b) | 52.83 |
\(B_{1} = 5,B_{2} = 2,q = 0.8\)
| ||
BRF(b) | 52.49 |
\(p_{1} = 0.01,p_{2} = 0.65,q = 0.8\)
| ||
Denil14(b) | 58.56 |
\(\lambda = 1,m = 50,q = 0.8\)
| ||
Flare | DMRF | 0.5099 |
\(B_{1} = 5,B_{2} = 5,p = 0.5,q = 0.2\)
| |
MRF(b) | 0.5227 |
\(B_{1} = 2,B_{2} = 2,q = 0.2\)
| ||
BRF(b) | 0.5102 |
\(p_{1} = 0.01,p_{2} = 0.01,q_{n} = 0.2\)
| ||
Denil14(b) | 0.5156 |
\(\lambda = 1,m = 100,q = 0.2\)
|
RF variants | Complexity |
---|---|
BreimanRF |
\({\mathcal{O}}(\sqrt D nM\log n)\)
|
BRF |
\({\mathcal{O}}((p_{1} + (1 - p_{1} )\sqrt D )(1 - p_{2} )nM\log n)\)
|
DMRF |
\({\mathcal{O}}(\sqrt D nM\log n\)
|
Denil14 |
\({\mathcal{O}}(\min (1 + Poisson(\lambda ),D) \cdot mM\log n)\)
|
MRF |
\({\mathcal{O}}(DnM\log n)\)
|