Đặng Quốc Bảo * , Trần Huỳnh Lê Đỗ Thanh Nghị

* Tác giả liên hệĐặng Quốc Bảo

Abstract

In this paper, we propose a new algorithm, called ArcX4-rODT (ArcX4 of random oblique decision trees) to classify gene data which have very small amount of samples in very high dimensions and noise. Our ArcX4-rODT algorithm constructs sequentially k random oblique trees so that each tree concentrates mostly on the errors produced by the previous ones. Furthermore, the hyper-plane obtained by Fisher's linear discriminant analysis is also used to perform multivariate splitting data at each internal node of the decision tree. Thus, the ArcX4-rODT can deal with very-high-dimensional data and noise. The experimental results on gene datasets from datam.i2r.a-star.edu.sg/datasets/krbd/ showed that our ArcX4-rODT algorithm outperforms randomforestofC4.5(RF-C4.5) and SVM (LibSVM).
Keywords: Random oblique decision tree, Linear discriminant analysis, gene classification

Tóm tắt

Trong bài viết này, chúng tôi trình bày giải thuật máy học mới ArcX4 của cây quyết định ngẫu nhiên xiên phân (ArcX4-rODT). Giải thuật ArcX4-rODT xây dựng tuần tự tập hợp cây xiên phân ngẫu nhiên, cây xây dựng sau sẽ tập trung lên các mẫu bị phân lớp sai bởi các cây trước, mỗi cây thành viên sử dụng siêu phẳng phân chia dữ liệu hiệu quả tại mỗi nút của cây dựa trên phân tích biệt lập tuyến tính. Việc xây dựng cây xiên phân ngẫu nhiên vì thế tạo cho giải thuật có khả năng làm việc tốt trên dữ liệu có số chiều lớn và nhiễu như dữ liệu gien. Kết quả thử nghiệm trên các tập dữ liệu gien từ site datam.i2r.a-star.edu.sg/datasets/krbd/ cho thấy rằng giải thuật ArcX4-rODT mới do chúng tôi đề xuất phân loại tốt hơn khi so sánh với rừng ngẫu nhiên của cây quyết định C4.5 và máy học véctơ hỗ trợ.
Từ khóa: Giải thuật ArcX4, Cây ngẫu nhiên xiên phân, Phương pháp phân tích biệt lập tuyến tính, Phân loại dữ liệu gien

Article Details

Tài liệu tham khảo

L. Breiman, J.H. Friedman, R.A. Olshen and C. Stone. Classification and Regression Trees. Wadsworth International, 1984.

L. Breiman. Bagging predictors. Machine Learning 24(2):123–140, 1996.

L. Breiman. Arcing classifiers. The annals of statistics, 26(3): 801–849, 1998.

L. Breiman. Random forests. Machine Learning 45(1):5–32, 2001.

W. Buntine. Learning classification trees. Statistics and Computing 2, 1992, pp. 63–73.

C.C. Chang and C.J. Lin. Libsvm – a library for support vector machines. 2001. http://www.csie.ntu.edu.tw/cjlin/libsvm.

T.N. Do, S. Lallich, N.K. Pham and P. Lenca. Classifying very-high-dimensional data with random forests of oblique decision trees. in Advances in Knowledge Discovery and Management Vol. 292, Springer-Verlag, 2009, pp. 39-55.

R.A. Fisher. The Use of Multiple Measurements in Taxonomic Problems. in Annals of Eugenics, No 7, 1936, pp. 179-188.

Y. Freund and R. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Computational Learning Theory, 1995, pp. 23–37.

J. Friedman, T. Hastie and R. Tibshirani. Response to Mease and Wyner, Evidence Contrary to the Statistical View of Boosting. Journal Machine Learning Research Vol. 9, 2008, pp. 175-180.

A.J. Grove and D. Schuurmans. Boosting in the limit: Maximizing the margin of learned ensembles. In Proceedings of the Fifteenth National Conference on Artificial Intelligence (AAAI-98), 1998, pp. 692–699.

L. Jinyan and L. Huiqing. Kent ridge bio-medical dataset repository. 2002, http://datam.i2r.a-star.edu.sg/datasets/krbd/.

S. Murthy, S. Kasif, S. Salzberg and R. Beigel. Oc1: Randomized induction of oblique decision trees. In Proceedings of the Eleventh National Conference on Artificial Intelligence, 1993, pp. 322–327.

J.R. Quinlan. C4.5: Programs for Machine Learning. Morgan Kaufmann, 1993.

C.V. van Rijsbergen. Information Retrieval. Butterworth, 1979.

V. Vapnik. The Nature of Statistical Learning Theory. Springer-Verlag, 1995.

D. Wolpert. Stacked generalization. Neural Networks 5, 1992, pp. 241–259.

Q. Yang and X. Wu. 10 Challenging Problems in Data Mining Research. Journal of Information Technology & Decision Making 5(4):597-604, 2006.