Đỗ Thanh Nghị * Phạm Nguyên Khang

* Tác giả liên hệ (dtnghi@ctu.edu.vn)

Abstract

Our investigation aims at constructing random oblique decision trees to recognize handwritten digits. At the pre-processing step, we propose to use the GIST descriptors to represent digit images in large number of dimensions datasets. And then we propose a multi-class version of random oblique decision trees based on the linear discriminant analysis that is suited for classifying high dimensional datasets. The experimental results on MNIST dataset show that our proposal has very high accuracy compared to state-of-the-art algorithms.
Keywords: Handwritten Digit Recognition, GIST Descriptor, Random Oblique Decision Trees, Linear Discriminant Analysis

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 rừng ngẫu nhiên xiên phân (rODT) cho nhận dạng ký tự số viết tay. Chúng tôi đề xuất sử dụng đặc trưng toàn cục (GIST) cho biểu diễn ảnh ký tự số trong không gian có số chiều lớn. Tiếp theo, chúng tôi đề xuất giải thuật học tự động rừng xiên phân ngẫu đa lớp, 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 (LDA). 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 sinh ra từ bước tiền xử lý. Kết quả thử nghiệm trên tập dữ liệu thực MNIST cho thấy rằng giải thuật rODT do chúng tôi đề xuất nhận dạng rất chính xác khi so sánh với các phương pháp nhận dạng hiện nay.
Từ khóa: Nhận dạng ký tự viết tay, Đặc trưng GIST, Cây ngẫu nhiên xiên phân, Phân tích biệt lập tuyến tính

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. Random forests. Machine Learning 45(1):5–32, 2001.

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.

M. Douze, M., H. Jégou, H. Sandhawalia, L. Amsaleg, and C. Schmid. Evaluation of GIST descriptors for web-scale image search. In Proceedings of the ACM International Conference on Image and Video Retrieval, 2009, pp. 1–8.

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.

B. Kégl and R. Busa-Fekete. Boosting products of base classifiers. In Proceedings of the 26th Annual International Conference on Machine Learning, 2009, pp. 497–504.

Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. In Proceedings of the IEEE, 1998, pp. 2278–2324.

LeCun, Y. and C. Cortes. The MNIST database of handwritten digits. 1989.

D. Lowe. Distinctive image features from scale invariant keypoints. International Journal of Computer Vision, 2004, pp. 91–110.

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.

A. Oliva and A. Torralba. Modeling the shape of the scene : A holistic representation of the spatial envelope. International Journal of Computer Vision 42, 145–175, 2001.

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

Y. Simard, D. Steinkraus, J. Platt. Best Pratices for Convolutional Neural Network Applied to Visual Document Analysis. in Intl Conference on Document Analysis and Recogntion, 2003, pp. 958-962.

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

H. Witten and E. Frank. Data Mining : Practical Machine Learning Tools and Techniques. Morgan Kaufmann, San Francisco, 2nd edition, 2005.