Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front Comput Sci Chin    2011, Vol. 5 Issue (1) : 79-86    https://doi.org/10.1007/s11704-010-0388-5
RESEARCH ARTICLE
Learning random forests for ranking
Liangxiao JIANG()
Department of Computer Science, China University of Geosciences, Wuhan 430074, China
 Download: PDF(113 KB)   HTML
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
Abstract

The random forests (RF) algorithm, which combines the predictions from an ensemble of random trees, has achieved significant improvements in terms of classification accuracy. In many real-world applications, however, ranking is often required in order to make optimal decisions. Thus, we focus our attention on the ranking performance of RF in this paper. Our experimental results based on the entire 36 UC Irvine Machine Learning Repository (UCI) data sets published on the main website of Weka platform show that RF doesn’t perform well in ranking, and is even about the same as a single C4.4 tree. This fact raises the question of whether several improvements to RF can scale up its ranking performance. To answer this question, we single out an improved random forests (IRF) algorithm. Instead of the information gain measure and the maximum-likelihood estimate, the average gain measure and the similarity-weighted estimate are used in IRF. Our experiments show that IRF significantly outperforms all the other algorithms used to compare in terms of ranking while maintains the high classification accuracy characterizing RF.

Keywords random forests (RF)      decision tree      random selection      class probability estimation      ranking      the area under the receiver operating characteristics curve (AUC)     
Corresponding Author(s): JIANG Liangxiao,Email:ljiang@cug.edu.cn   
Issue Date: 05 March 2011
 Cite this article:   
Liangxiao JIANG. Learning random forests for ranking[J]. Front Comput Sci Chin, 2011, 5(1): 79-86.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-010-0388-5
https://academic.hep.com.cn/fcs/EN/Y2011/V5/I1/79
Fig.1  An example of a tree for class probability estimation
Fig.1  An example of a tree for class probability estimation
Data setIRFC4.5C4.4RF
Anneal96.2185.74 ●94.33 ●89.18 ●
Anneal.ORIG94.7986.08 ●94.1788.12 ●
Audiology71.1269.40 ●70.33 ●70.23 ●
Autos95.1784.84 ●91.82 ●92.15 ●
Balance-scale69.9253.47 ●64.11 ●62.55 ●
Breast-cancer65.0656.55 ●59.0363.08
Breast-w99.0996.32 ●98.04 ●98.75
Colic85.0880.9581.6986.88
Colic.ORIG80.3366.82 ●74.3375.28
Credit-a89.0388.4386.71 ●88.79
Credit-g73.2868.94 ●68.37 ●73.37
Diabetes78.2676.2674.31 ●78.53
Glass84.9479.44 ●78.49 ●83.46
Heart-c83.5683.1783.04 ●83.42
Heart-h83.7582.58 ●83.20 ●83.56
Heart-statlog84.6082.3279.4884.36
Hepatitis82.4261.24 ●75.8282.53
Hypothyroid85.1575.70 ●83.19 ●83.60
Ionosphere96.1688.45 ●91.62 ●95.95
Iris98.9290.80 ●97.22 ●91.85 ●
Kr-vs-kp99.7799.8299.96 ○99.83
Labor95.9264.29 ●84.8390.88
Letter99.2993.03 ●96.58 ●99.02 ●
Lymph89.6882.47 ●86.15 ●85.73
Mushroom100.0099.88100.0099.95
primary-tumor77.5772.97 ●74.75 ●73.94 ●
Segment99.5697.16 ●99.04 ●98.99 ●
Sick98.7893.30 ●99.1497.63
Sonar80.6869.90 ●76.2279.86
Soybean99.7583.83 ●91.38 ●87.20 ●
Splice98.9696.80 ●97.57 ●97.58 ●
Vehicle86.1782.25 ●84.3386.21
Vote98.6596.29 ●97.27 ●97.99
Vowel98.6788.43 ●91.93 ●98.76
Waveform-500092.3384.42 ●80.64 ●92.00
Zoo89.4888.33 ●88.33 ●88.42 ●
Average88.9881.9685.4986.93
Tab.1  AUC comparisons for IRF versus C4.5, C4.4, and RF
C4.5C4.4RF
C4.418/17/1
RF23/13/09/21/6
IRF29/7/024/11/112/24/0
Tab.2  Compared results of each pair of algorithms
Data setIRFC4.4-bagging
Anneal96.3694.93
Anneal.ORIG94.7694.92
Audiology71.1571.09
Autos96.6295.67
Balance-scale69.4871.26
Breast-cancer64.0962.75
Breast-w99.1198.76
Colic85.3486.98
Colic.ORIG80.4677.01
Credit-a88.8289.55
Credit-g73.5573.32
Diabetes78.0378.27
Glass85.7382.50
Heart-c83.6183.60
Heart-h83.7383.63
Heart-statlog83.3184.80
Hepatitis82.4981.62
Hypothyroid85.0383.03 ●
Ionosphere96.5295.22
Iris98.7698.59
Kr-vs-kp99.7899.97 ○
Labor96.9287.67
Letter99.2998.22 ●
Lymph89.6389.15
Mushroom100.00100.00
Primary-tumor77.6977.72
Segment99.5699.31 ●
Sick98.6899.20
Sonar80.8083.03
Soybean99.7792.70 ●
Splice98.9498.70
Vehicle86.0188.61 ○
Vote98.7098.26
Vowel98.7495.98 ●
Waveform-500092.3089.81 ●
Zoo89.4888.36 ●
Average88.9888.17
w/t/l-2/27/7
Tab.3  AUC comparisons for IRF versus C4.4-bagging
Data setC4.4-SWC4.4
Anneal96.1694.33 ●
Anneal.ORIG94.6794.17
Audiology71.0970.33 ●
Autos94.5592.09 ●
Balance-scale63.9564.11
Breast-cancer59.8859.03
Breast-w98.4198.04
Colic82.4181.69
Colic.ORIG74.8774.33
Credit-a86.9786.71
Credit-g68.6668.37
Diabetes75.0274.31
Glass79.7278.49
Heart-c83.1083.04
Heart-h83.1783.20
Heart-statlog80.0879.48
Hepatitis77.4375.82
Hypothyroid83.1883.19
Ionosphere92.5491.62
Iris98.1997.22
Kr-vs-kp99.9699.96
Labor90.2984.83
Letter96.7996.58 ●
Lymph86.8686.15
Mushroom100.00100.00
Primary-tumor76.1774.75 ●
Segment99.2699.04 ●
Sick99.1799.14
Sonar77.2476.22
Soybean98.8091.38 ●
Splice97.6797.57 ●
Vehicle84.5084.33
Vote98.0797.27
Vowel93.5591.93 ●
Waveform-500080.6580.64
Zoo89.3688.33 ●
Average86.4685.49
w/t/l-0/26/10
Tab.4  AUC comparisons for C4.4-SW versus C4.4
Data setIRFRF
Anneal98.6698.80
Anneal.ORIG90.7691.27
Audiology76.5975.90
Autos83.7883.27
Balance-scale80.8276.64 ●
Breast-cancer69.9869.07
Breast-w96.2795.92
Colic81.5082.97
Colic.ORIG76.6273.03
Credit-a83.2983.74
Credit-g73.0673.30
Diabetes72.6872.59
Glass60.9059.48
Heart-c79.5177.49
Heart-h81.4079.53
Heart-statlog78.1978.30
Hepatitis82.3281.83
Hypothyroid92.9092.38 ●
Ionosphere90.1790.40
Iris94.6794.87
Kr-vs-kp98.4698.89
Labor91.8788.53
Letter89.0489.74 ○
Lymph82.9780.02
Mushroom100.00100.00
Primary-tumor40.8339.77
Segment94.7795.56
Sick98.1798.09
Sonar73.9872.97
Soybean93.9592.84
Splice93.7788.16 ●
Vehicle69.8570.47
Vote94.9495.90
Vowel87.6190.35 ○
Waveform-500078.3877.52
Zoo94.5691.35
Average84.0983.36
w/t/l-2/31/3
Tab.5  Accuracy comparisons for IRF versus RF
1 Provost F, Domingos P. Tree induction for probability-based ranking. Machine Learning , 2003, 52(3): 199-215
doi: 10.1023/A:1024099825458
2 Ling C X, Yan R J. Decision tree with better ranking. In: Proceedings of 20th International Conference on Machine Learning . 2003, 480-487
3 Jiang L X, Li C QCaiZ H. Learning decision tree for ranking. Knowledge and Information Systems , 2009, 20(1): 123-135
doi: 10.1007/s10115-008-0173-z
4 Jiang L X, Wang D H, Zhang H, Cai Z H, Huang B. Using instance cloning to improve naive Bayes for ranking. International Journal of Pattern Recognition and Artificial Intelligence , 2008, 22(6): 1121-1140
doi: 10.1142/S0218001408006703
5 Bradley A P. The use of the area under the roc curve in the evaluation of machine learning algorithms. Pattern Recognition , 1997, 30(7): 1145-1159
doi: 10.1016/S0031-3203(96)00142-2
6 Hand D J, Till R J. A simple generalisation of the area under the roc curve for multiple class classification problems. Machine Learning , 2001, 45(2): 171-186
doi: 10.1023/A:1010920819831
7 Ling C X, Huang J, Zhang H. Auc: a statistically consistent and more discriminating measure than accuracy. In: Proceedings of 18th International Joint Conference on Artificial Intelligence . 2003, 519-526
8 Quinlan J R. C4.5: Programs for Machine Learning. San Francisco: Morgan Kaufmann, 1992
9 Mitchell T M. Machine Learning. New York: McGraw-Hill, 1997
10 Breiman L. Random forests. Machine Learning , 2001, 45(1): 5-32
doi: 10.1023/A:1010933404324
11 Dietterich T G. An experimental comparison of three methods for constructing ensembles of decision trees: Bagging, boosting and randomization. Machine Learning , 2000, 40(2): 139-157
doi: 10.1023/A:1007607513941
12 Breiman L. Bagging Predictors. Machine Learning , 1996, 24(2): 123-140
doi: 10.1007/BF00058655
13 Bauer E, Kohavi R. An empirical comparison of voting classification algorithms: bagging, boosting and variants. Machine Learning , 1999, 36(1-2): 105-139
doi: 10.1023/A:1007515423169
14 Witten I H, Frank E. Data Mining: Practical Machine Learning Tools and Techniques. 2nd ed. San Francisco: Morgan Kaufmann, 2005
15 Quinlan J R. Induction of decision trees. Machine Learning , 1986, 1(1): 81-106
doi: 10.1007/BF00116251
16 Wang D H, Jiang L X. An improved attribute selection measure for decision tree induction. In: Proceedings of 4th International Conference on Fuzzy Systems and Knowledge Discovery . 2007, 654-658
doi: 10.1109/FSKD.2007.161
17 De Mántaras R L. A distance-based attribute selection measure for decision tree induction. Machine Learning , 1991, 6(1): 81-92
doi: 10.1007/BF00153761
18 Pazzani M J, Merz C J, Murphy P M, Ali K. Hume T, Brunk C. Reducing misclassification costs. In: Proceedings of 11th International Conference on Machine Learning . 1994, 217-225
19 Bradford J P, Kunz C, Kohavi R, Brunk C, Brodley C E. Pruning decision trees with misclassification costs. In: Proceedings of 10th European Conference on Machine Learning . 1998, 131-136
20 Provost F J, Fawcett T, Kohavi R. The case against accuracy estimation for comparing induction algorithms. In: Proceedings of 15th International Conference on Machine Learning . 1998, 445-453
21 Jiang L X, Wang D H, Cai Z H. Scaling up the accuracy of bayesian network classifiers by m-estimate. In: Proceedings of 3rd International Conference on Intelligent Computing . 2007, 475-484
22 Smyth P, Gray A, Fayyad U M. Retrofitting decision tree classifiers using kernel density estimation. In: Proceedings of 12th International Conference on Machine Learning . 1995, 506-514
23 Nadeau C, Bengio Y. Inference for the generalization error. Machine Learning , 2003, 52(3): 239-281
doi: 10.1023/A:1024068626366
[1] Ying LI, Xiangwei KONG, Haiyan FU, Qi TIAN. Contextual modeling on auxiliary points for robust image reranking[J]. Front. Comput. Sci., 2019, 13(5): 1010-1022.
[2] Yu HONG, Kai WANG, Weiyi GE, Yingying QIU, Guodong ZHOU. Cursor momentum for fascination measurement[J]. Front. Comput. Sci., 2019, 13(2): 396-412.
[3] Xiaohui TAN, Yachun FAN, Ruiliang GUO. Local features and manifold ranking coupled method for sketch-based 3D model retrieval[J]. Front. Comput. Sci., 2018, 12(5): 1000-1012.
[4] Tao SUN, Zhi-Hua ZHOU. Structural diversity for decision tree ensemble learning[J]. Front. Comput. Sci., 2018, 12(3): 560-570.
[5] Chengyu WANG, Guomin ZHOU, Xiaofeng HE, Aoying ZHOU. NERank+: a graph-based approach for entity ranking in document collections[J]. Front. Comput. Sci., 2018, 12(3): 504-517.
[6] Wayne Xin ZHAO, Chen LIU, Ji-Rong WEN, Xiaoming LI. Ranking and tagging bursty features in text streams with context language models[J]. Front. Comput. Sci., 2017, 11(5): 852-862.
[7] Rui LIU, Wenge RONG, Yuanxin OUYANG, Zhang XIONG. A hierarchical similarity based job recommendation service framework for university students[J]. Front. Comput. Sci., 2017, 11(5): 912-922.
[8] Pushpinder SINGH. Some new distance measures for type-2 fuzzy sets and distance measure based ranking for group decision making problems[J]. Front. Comput. Sci., 2014, 8(5): 741-752.
[9] Zengchang QIN, Tao WAN. Hybrid Bayesian estimation tree learning with discrete and fuzzy labels[J]. Front Comput Sci, 2013, 7(6): 852-863.
[10] Yongqing WANG, Wenji MAO, Daniel ZENG, Fen XIA. Listwise approaches based on feature ranking discovery[J]. Front Comput Sci, 2012, 6(6): 647-659.
[11] Cheqing JIN, Jingwei ZHANG, Aoying ZHOU. Continuous ranking on uncertain streams[J]. Front Comput Sci, 2012, 6(6): 686-699.
[12] Anca Maria IVANESCU, Marc WICHTERICH, Christian BEECKS, Thomas SEIDL. The ClasSi coefficient for the evaluation of ranking quality in the presence of class similarities[J]. Front Comput Sci, 2012, 6(5): 568-580.
[13] Lu YANG, Chaochen ZHOU, Naijun ZHAN, Bican XIA, . Recent advances in program verification through computer algebra[J]. Front. Comput. Sci., 2010, 4(1): 1-16.
[14] Yufeng WANG, Akihiro NAKAO, Jianhua MA, . Socially inspired search and ranking in mobile social networking: concepts and challenges[J]. Front. Comput. Sci., 2009, 3(4): 435-444.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed