Tối ưu mô hình phân lớp dữ liệu dựa trên thuật toán K Nearest Neighbor

Nguyễn Thanh, Trần Đình Sơn Tối Ưu Mô Hình Phân Lớp Dữ Liệu Dựa Trên Thuật Toán K Nearest Neighbor Nguyễn Thanh1 và Trần Đình Sơn2 1,2 Trường Đại học Công nghệ Thông tin và Truyền thông Việt-Hàn, Đà Nẵng, Việt Nam {thanhn, tdson}@vku.udn.vn Tóm tắt. Trong những năm gần đây, việc sử dụng trí tuệ nhân tạo để xử lý dữ liệu lớn là rất phổ biến. Các mô hình xử lý dữ liệu được xây dựng dựa trên các thuật toán học máy để giải quyết các bài toán cụ thể đã được phát triển rộng rãi. Thuật toán K Nearest Neighbor là một trong các thuật toán được đánh giá đơn giản, hiệu quả và được sử dụng rộng rãi trong lĩnh vực học máy. Nó có thể thực hiện trên cả dữ liệu có cấu trúc hoặc không có cấu trúc, nhằm phân loại dữ liệu và xây dựng các mô hình dự báo, nhận dạng vv... Tuy nhiên, kết quả của mô hình phụ thuộc rất lớn vào việc chọn tham số k (số láng giềng gần nhất). Trong bài báo này chúng tôi trình bày giải pháp xác định tham số k tốt nhất, nhằm tối ưu mô hình phân loại dữ liệu dựa trên thuật toán K Nearest Neighbor. Từ khóa: Học máy, khai phá dữ liệu, phân lớp, K Nearest Neighbor, mô hình, tối ưu. Abstract. In recent years, the artificial intelligence it's very common to use to process big data. Data processing models built on machine learning algorithms to solve specific problems have been widely developed. The K Nearest Neighbor algorithm is one of the simplest, effective and widely used algo- rithms in machine learning field. It can be performed on both structured or unstructured data, in order to classify the data and build predictive, identity, etc. models. large on the selection of parameter k (number of nearest neighbors). In this paper we present the best solution to determine the parameter k, to optimize the data classification model based on the K Nearest Neighbor algorithm. Keywords: Machine learning, Data mining, Classification, K Nearest Neighbor, Modeling, Optimiza- tion. 1 Giới thiệu Khai thác dữ liệu được xem là một công nghệ tạo nên sự đột phá mang tính cách mạng trong lĩnh vực thông tin. Thuật ngữ khai phá dữ liệu (khám phá tri thức) đề cập đến quá trình phân tích dữ liệu từ các khía cạnh khác nhau và tóm tắt dữ liệu thành những thông tin hữu ích bằng một số công cụ và kỹ thuật phân tích. Về mặt kỹ thuật, khai thác dữ liệu là quá trình tìm kiếm các mối tương quan giữa các trường (biến) trong dữ liệu. Khai thác dữ liệu bao gồm các chức năng: chuyển đổi, chuẩn hóa, thống kê và tạo các mô hình phân tích và dự đoán để trích xuất những thông tin hữu ích từ tập dữ liệu lớn, nhằm hỗ trợ cho việc ra quyết định. Đặc biệt có thể phân lớp dữ liệu và xây dựng các mô hình dự báo trong tương lai. Tuy nhiên, các mô hình có độ chính xác khác nhau và không cao, do vậy việc tìm giải pháp nâng cao hiệu năng của mô hình là rất cần thiết. Trong bài báo này chúng tôi tập trung nghiên cứu và đề xuất giải pháp tối ưu hóa mô hình phân loại dữ liệu dựa trên thuật toán K-Near. Phần còn lại của bài báo được trình bày như sau: phần 2 giới thiệu về phân lớp dữ liệu, phần 3 trình bày thuật toán KNN, phần 4 xây dựng mô hình phân lớp dữ liệu, phần 5 trình bày giải pháp tối ưu mô hình phân lớp dữ liệu dựa trên thuật toán K Nearest Neighbor, phần 6 so sánh hiệu năng của các mô hình, phần 7 kết luận và hướng nghiên cứu trong tương lai. 2 Phân lớp dữ liệu Các thuật toán phân lớp được tiến hành gồm 2 bước: 227 KỶ YẾU HỘI THẢO KHOA HỌC QUỐC GIA CITA 2020 “CNTT VÀ ỨNG DỤNG TRONG CÁC LĨNH VỰC” Xây dựng mô hình: là mô tả một tập những lớp được định nghĩa trước, trong đó: mỗi bộ hoặc mẫu được gán thuộc về một lớp được định nghĩa trước như là được xác định bởi thuộc tính nhãn lớp, tập hợp của những bộ dữ liệu (observation) được sử dụng trong việc mô hình được gọi là tập huấn luyện (train). Mô hình được biểu diễn bởi những luật phân lớp, cây quyết định và những công thức toán học. Sử dụng mô hình: Việc sử dụng mô hình phục vụ cho mục đích phân lớp dữ liệu trong tương lai hoặc phân lớp cho những đối tượng chưa biết. Trước khi sử dụng mô hình cần phải đánh giá tính chính xác của mô hình, trong đó: nhãn của mẫu kiểm tra được so sánh với kết quả phân lớp của mô hình, độ chính xác của mô hình là tỷ lệ phần trăm mà mô hình phân loại đúng dựa trên tập dữ liệu kiểm thử (test), tập kiểm thử là độc lập với tập huấn luyện. Có rất nhiều thuật toán dùng để phân lớp dữ liệu. Trong bài báo này chúng tôi sử dụng mô hình phân lớp dựa trên thuật toán K Nearest Neighbor để triển khai và tối ưu. 3 Thuật toán K Nearest Neighbor Thuật toán K Nearest Neighbor (K-NN) [1] [2] là một thuật toán máy học có giám sát dùng để phân loại một điểm dữ liệu mới vào lớp đích, tùy thuộc vào các tính năng của các điểm dữ liệu lân cận của nó, K-NN là nền tảng của phương pháp học phi tham số. Do tính đơn giản và linh hoạt của nó, thuật toán này đã trở thành phương pháp được lựa chọn trong nhiều tình huống học máy [3]. Đặc biệt là trong các cài đặt mô hình phức tạp. Các ứng dụng hiện đại của thuật toán K-NN bao gồm hệ thống khuyến nghị [4], phân loại văn bản [5], phân loại bệnh tim [6], và dự đoán thị trường tài chính [7] và một số lĩnh vực khác. Ứng dụng thành công thuật toán K-NN đòi hỏi phải có sự lựa chọn cẩn thận của ba thành phần: số lân cận gần nhất k, vectơ trọng số α và khoảng cách giữa các điểm dữ liệu. Tuy nhiên, vấn đề chọn k và α tối ưu vẫn chưa được hiểu đầy đủ và đã được nghiên cứu rộng rãi từ những năm 1950 với nhiều cách tiếp cận khác nhau. Hầu hết các công trình nghiên cứu về lý thuyết đều tập trung vào phương pháp tiệm cận, trong đó số mẫu n dần đến vô cùng [8], và bỏ qua trường hợp thực tế (n là hữu hạn). Phần lớn các nghiên cứu ứng dụng thuật toán K-NN để tìm giá trị tối ưu của k trên mỗi tập dữ liệu dường như bỏ qua cấu trúc cụ thể của tập dữ liệu và các thuộc tính của các điểm dữ liệu có nhãn mà chúng ta muốn ước tính. Thuật toán phân loại K- Nearest Neighbor có thể dự đoán nhãn đích bằng cách tìm lớp láng giềng gần nhất. Lớp gần nhất sẽ được xác định bằng cách sử dụng khoảng cách Euclidean [9] (, ) = ( − ) Chọn giá trị của k trong K-Nearest Neighbor là vấn đề quyết định hiệu quả của thuật toán ứng với bộ dữ liệu. Nếu chọn giá trị của k nhỏ sẽ có ảnh hưởng lớn đến kết quả, mô hình không chính xác, ngược lại nếu chọn giá trị của k lớn sẽ tốn kém về mặt tính toán. Cách tiếp cận phổ biến là chọn = √ . Trong bài báo này, chúng tôi đưa ra một cách tiếp cận nhất quán và có nguyên tắc để lựa chọn k một cách thích ứng trên mỗi điểm dữ liệu. Với mỗi điểm dữ liệu, chúng tôi mong muốn tìm ra trọng số cục bộ tốt nhất, theo cách tiếp cận giảm thiểu khoảng cách giữa giá tri dự đoán và giá trị thật. Chúng tôi sử dụng kỹ thuật học máy để tìm k tốt nhất nhằm tối ưu hóa mô hình. 228 Nguyễn Thanh, Trần Đình Sơn 4 Xây dựng mô hình Hình 1. Các bước xây dựng mô hình 4.1 Nạp dữ liệu (chọn dữ liệu) Để tiến hành thực nghiệm chúng tôi chọn dữ liệu tại địa chỉ link https://archive.ics.uci.edu/ml/datasets/Statlog+%28German+Credit+Data%29. Đây là bộ dữ liệu tín dụng ngân hàng chứa 1000 hồ sơ xin vay vốn, gồm 21 thuộc tính (biến) số dư tài khoản, số tiền tín dụng, tuổi, nghề nghiệp, hồ sơ khoản vay, v.v. Hình 2. Cấu trúc của dữ liệu Chúng tôi chỉ trích xuất các thuộc tính cần thiết phục vụ cho nghiên cứu, trong trường hợp này chúng tôi chọn 8 biến: Hình 3. Các biến được trích xuất 229 KỶ YẾU HỘI THẢO KHOA HỌC QUỐC GIA CITA 2020 “CNTT VÀ ỨNG DỤNG TRONG CÁC LĨNH VỰC” 4.2 Chuẩn hóa dữ liệu Để hạn chế sai số trong quá trình phân tích và xây dựng mô hình, chúng tôi chuẩn hóa dữ liệu trước khi thực hiện mô hình bằng cách tạo hàm normalize với mục đích chuyển đổi dữ liệu về thang đo từ 0 đến 1. Tạo hàm chuẩn hóa normalize normalize = function(x) { return ((x - min(x)) / (max(x) - min(x)))} Chuẩn hóa dữ liệu data_normalize = normalize(data)) 4.3 Tách dữ liệu và xây dựng mô hình Để nhất quán trong quá trình thực nghiệm, chúng tôi tiến hành mô hình hóa và kiểm tra mô hình trên cùng một cấu trúc dữ liệu, nghĩa là chúng tôi chia dữ liệu thành 2 phần theo tỷ lệ 7:3 (7 phần dùng để xây dựng mô hình và 3 phần dùng để kiểm tra mô hình). Các mẫu trong mỗi phần được trích chọn ngẫu nhiên từ dữ liệu gốc. data_train = random(data, 0.7) data_test = random(data, 0.3) model <- knn(data_train, data_test, cl=train_labels, = √ ) 5 Tối ưu mô hình Hình 4. Thuật toán tối ưu mô hình Để tối ưu mô hình, chúng tôi dùng kỹ thuật máy học, cho mô hình tự động nhận lần lượt các giá trị của k ( = 1, − 1 ). ứng với mỗi giá trị của k, mô hình sẽ tính và lưu lại giá trị trong một véc tơ, sau đó tìm vị trí của phần tử có giá trị lớn nhất, xuất hiện đầu tiên trong véc tơ (giá trị k_opt tối ưu). Sau đó truyền giá trị k_opt cho mô hình, chúng ta sẽ có được mô hình tối ưu. Phương pháp tối ưu mô hình i <- 1 k.optm <- 0 result <- c() for (i in 1:n-1){ model <- knn(train=data_train, test=data_test, cl=train_labels, k=i) k.optm[i] <- sum(test_labels == model)/NROW(test_labels) k=i result <- append(result,k.optm[i]) } k_opt <- which.max(result) model_opt <- knn(train=data_train, test=data_test, cl=train_labels, k=k_opt) 230 Nguyễn Thanh, Trần Đình Sơn Hình 5b. Kết quả của mô hình tối ưu 6 So sánh hiệu năng của hai mô hình trước và sau khi tối ưu Chúng tôi tiến hành kiểm tra 2 mô hình trên cùng tập dữ liệu và kết quả tính toán như hình 5a và hình 5b Hình 5a. Kết quả của mô hình trước khi tối ưu Dựa vào các giá trị của các mô hình cung cấp, chúng tôi tính được các giá trị đánh giá hiệu năng của mô hình như: Accuracy, Error, True Positive Rate, True Negative Rate, Precision (bảng 1) Bng 1. Bảng so sánh hiệu năng của 2 mô hình Accu- racy Error Rate True Posi- tive Rate False Posi- tive Rate True Nega- tive Rate Preci- sion model 0,6900 0,3100 0,6958 0,4286 0,5714 0,9707 model_opt 0,7000 0,3000 0,6976 0,2222 0,7778 0,9902 Dựa vào bảng so sánh hiệu năng của hai mô hình, chúng ta thấy mô hình tối ưu có độ chính xác (Accuracy) cao hơn và tỷ lệ sai số (Error rate) thấp hơn so với mô hình chưa được tối ưu. 7 Kết luận và hướng nghiên cứu trong tương lai Trong bài báo này, chúng tôi đã tìm được giải pháp tối ưu mô hình phân lớp dữ liệu dựa trên thuật toán K Nearest Neighbor, với độ chính xác cao hơn so với mô hình truyền thống. Tuy nhiên, việc tìm giá trị k tốt nhất cho mô hình tối ưu, chúng tôi phải thực hiện việc thử mô hình một cách tự động nhiều lần (n-1 lần), điều này tốn nhiều thời gian tính toán đối với dữ liệu lớn. Trong tương lai chúng tôi sẽ tiếp tục nghiên cứu để xác định ngưỡng trên và ngưỡng dưới nhằm rút gắn thời gian tính toán. Tài liệu tham kho 1. T. M. Cover and P. E. Hart. Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 13(1):21–27, 1967. 2. E. Fix and J. L. Hodges Jr. Discriminatory analysis-nonparametric discrimination: consistency properties. Tech- nical report, DTIC Document, 1951. 3. X. Wu, V. Kumar, J. R. Quinlan, J. Ghosh, Q. Yang, H. Motoda, G. J. McLachlan, A. Ng, B. Liu, S. Y. Philip, et al. Top 10 algorithms in data mining. Knowledge and information systems, 14(1):1–37, 2008. 231 KỶ YẾU HỘI THẢO KHOA HỌC QUỐC GIA CITA 2020 “CNTT VÀ ỨNG DỤNG TRONG CÁC LĨNH VỰC” 4. D. Adeniyi, Z. Wei, and Y. Yongquan. Automated web usage data mining and recommendation system using k- nearest neighbor (knn) classification method. Applied Computing and Informatics, 12(1):90–108, 2016. 5. B. Trstenjak, S. Mikac, and D. Donko. Knn with tf-idf based framework for text categorization. Procedia Engi- neering, 69:1356–1364, 2014. 6. B. Deekshatulu, P. Chandra, et al. Classification of heart disease using k-nearest neighbor and genetic algorithm. Procedia Technology, 10:85–94, 2013. 7. S. B. Imandoust and M. Bolandraftar. Application of k-nearest neighbor (knn) approach for predicting economic events: Theoretical background. International Journal of Engineering Research and Applications, 3(5):605–610, 2013. 8. L. Devroye, L. Gy¨orfi, and G. Lugosi. A probabilistic theory of pattern recognition, volume 31. Springer Science & Business Media, 2013. 9. Tabak, John (2014), Geometry: The Language of Space and Form, Facts on File math library, Infobase Publishing, p. 150, ISBN 9780816068760 232