- PHÂN LOẠI DỮ LIỆU GIEN VỚI GIẢI THUẬT MÁY HỌC ARCX4-RODT. - 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. - Phân lớp dữ liệu cĩ số chiều lớn cĩ nhiễu như dữ liệu gien được biết là một trong 10 vấn đề khĩ của cộng đồng khai mỏ dữ liệu (Yang &. - Mơ hình học phân lớp thường cho kết quả tốt trong khi học nhưng lại cho kết quả rất thấp trong tập thử. - Vấn đề khĩ khăn thường gặp chính là số chiều quá lớn lên đến hàng nghìn chiều thậm chí đến cả triệu và dữ liệu thường tách rời nhau trong khơng gian cĩ số chiều lớn việc tìm mơ hình phân lớp tốt cĩ khả năng làm việc với dữ liệu cĩ số chiều lớn là khĩ khăn do cĩ quá nhiều khả năng lựa chọn mơ hình. - mơ hình phân lớp hiệu quả (phân lớp dữ liệu tốt trong tập thử) trong khơng gian giả thiết lớn là vấn đề khĩ. - Đã cĩ hai lớp giải thuật tiêu biểu là máy học véc tơ hỗ trợ của Vapnik (SVM [Vapnik, 1995]) và rừng ngẫu nhiên của [Breiman, 2001]. - được biết đến như là những giải thuật phân lớp hiệu quả các tập dữ liệu cĩ số chiều lớn như dữ liệu gien.. - Từ những năm 1990, cộng đồng máy học đã nghiên cứu cách để kết hợp nhiều mơ hình phân loại thành tập hợp các mơ hình phân loại để cho tính chính xác cao hơn so với chỉ một mơ hình phân loại. - Mục đích của các mơ hình tập hợp là làm giảm variance và/hoặc bias của các giải thuật học. - Bias là khái niệm về lỗi của mơ hình học (khơng liên quan đến dữ liệu học) và variance là lỗi do tính biến thiên của mơ hình so với tính ngẫu nhiên của các mẫu dữ liệu học. - Phương pháp xếp chồng (Wolpert, 1992) hướng tới việc cực tiểu hĩa bias của các giải thuật học.. - Schapire, 1995) đưa ra Boosting, (Breiman, 1998) đề nghị ArcX4 để cùng giảm bias và variance, cịn Bagging (Breiman, 1996) thì giảm variance của giải thuật học nhưng khơng làm tăng bias quá nhiều. - Tiếp cận rừng ngẫu nhiên (Breiman, 2001) là một trong những phương pháp tập hợp mơ hình thành cơng nhất. - Giải thuật rừng ngẫu nhiên xây dựng cây khơng cắt nhánh nhằm giữ cho bias thấp và dùng tính ngẫu nhiên để điều khiển tính tương quan thấp giữa các cây trong rừng. - Tiếp cận rừng ngẫu nhiên cho độ chính xác cao khi so sánh với các thuật tốn học cĩ giám sát hiện nay, bao gồm cả AdaBoost, ArcX4 và SVM.. - Khi xử lý dữ liệu cho cĩ số chiều lớn và cĩ số phần tử ít như dữ liệu gien thì rừng ngẫu nhiên và SVM là hai giải thuật học nhanh, chịu đựng nhiễu tốt và khơng bị tình trạng học vẹt, điều này ngược lại với AdaBoost, ArcX4 rất dễ bị học vẹt và ảnh hưởng lớn với nhiễu (Grove &. - Việc xây dựng cây quyết định thơng thường như giải thuật C4.5 (Quinlan, 1993) và CART (Breiman et al., 1984) trong rừng ngẫu nhiên và của AdaBoost, ArcX4 chỉ chọn một thuộc tính dùng để phân hoạch tại mỗi nút. - Vì thế, cá nhân mỗi cây kém hiệu quả khi làm việc với dữ liệu cĩ sự phụ thuộc nhau giữa các thuộc tính, thường gặp ở những dữ liệu cĩ số chiều rất lớn. - Để nâng cao hiệu quả xử lý dữ liệu cĩ số chiều lớn như dữ liệu gien, chúng tơi đề nghị thay thế cây quyết định thơng thường trong ArcX4 bằng cây quyết định ngẫu nhiên xiên phân (rODT). - Cây ngẫu nhiên xiên phâ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ương pháp phân tích biệt lập tuyến tính LDA (Fisher, 1936) (khác với chiến lược heuristics của OC1 (Murthy et al., 1993. - 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 ArcX4 cây quyết định ngẫu nhiên xiên phân (ArcX4-rODT) 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. - Các kết quả kiểm thử trên 10 tập dữ liệu gien cĩ số chiều lớn (Jinyan. - Huiqing, 2002) đã cho thấy ArcX4 cây quyết định ngẫu nhiên xiên phân mà chúng tơi đề xuất cho độ chính xác cao hơn rừng ngẫu nhiên thơng thường của C4.5 (RF-C4.5) và LibSVM (Chang &. - Phần tiếp theo của bài viết này được trình bày như sau: phần 2 trình bày ngắn gọn về giải thuật ArcX4-rODT của chúng tơi đề xuất. - 2 GIẢI THUẬT ARCX4-RODT. - Hiệu quả của một giải thuật học như đã nghiên cứu của (Breiman dựa trên cơ sở của 2 thành phần lỗi là bias và variance mà ở đĩ, thành phần lỗi bias là lỗi của mơ hình học và variance là lỗi do tính biến thiên của mơ hình so với tính ngẫu nhiên của các mẫu dữ liệu học. - Trong nghiên cứu kết hợp nhiều mơ hình phân loại thành tập hợp các mơ hình phân loại để cho tính chính xác cao hơn so với chỉ một mơ hình đơn.. - Giải thuật 1: ArcX4 cây quyết định ngẫu nhiên xiên phân. - Đây là một phương pháp áp dụng một tập các bộ phân lớp yếu (weak learner) để nâng cao hiệu quả của các bộ phân lớp này bằng cách giảm bias và variance. - Trong cùng thời điểm Breiman cũng đề xuất lớp các giải thuật Arcing [Breiman, 1998]. - Theo Breiman, Boosting là một dạng trong lớp giải thuật Arcing. - Trong đĩ cĩ giải thuật ArcX4 cho kết quả tương tự như AdaBoost (Freund &. - Ý tưởng chính của giải thuật ArcX4 (như mơ tả trong giải thuật 1) lặp lại quá trình học của một bộ phân lớp yếu nhiều lần. - Sau mỗi bước lặp, bộ phân lớp yếu (ví dụ như: Nạve Bayes, cây quyết định. - m phần tử dữ liệu : {(x i , y i )}i=1,m với x i ϵ R n và y i ϵ {1, -1}. - khởi động phân phối của m phần tử dữ liệu Dist 1 (j) cho j = 1 tới m thực hiện. - học mơ hình cây xiên phân ngẫu nhiên h i từ tập mẫu S i h i = rODT(S i. - tính lại lỗi dự đốn của từng phần tử x j khi sử dụng các bộ phân lớp được xây dựng trước đĩ. - cập nhật lại phân phối của m phần tử dữ liệu cho j = 1 tới m thực hiện. - trả về tập T mơ hình cây xiên phân {h i }i=1,T Phân lớp:. - phân lớp phần tử x: bình chọn số đơng của {h i (x)}i=1,T. - Ở bước thứ i, ta lấy tập mẫu S i trên tập dữ liệu và xây dựng mơ hình h i từ tập mẫu S i . - Lặp lại quá trình này sau T bước, ta sẽ được T mơ hình cơ sở, kết hợp các mơ hình cơ sở này lại ta sẽ cĩ được một bộ phân lớp mạnh. - ArcX4 thường dùng giải thuật cơ sở yếu là cây quyết định CART (Breiman, 1984]) hay C4.5 (Quinlan, 1993). - Để khắc phục nhược điểm này, Friedman và các cộng sự (Friedman et al., 2008) đề xuất sử dụng mơ hình cơ sở cây quyết định phải đơn giản (cây cĩ kích thước khơng quá 8 nút), khi đĩ số bước lặp tăng cao vẫn đảm bảo rằng Boosting và Arcing khơng bị tình trạng học vẹt.. - Chúng tơi đề xuất xây dựng mơ hình cơ sở dùng trong ArcX4 là cây ngẫu nhiên xiên phân (gọi là rODT) thay vì sử dụng cây quyết định thơng thường như C4.5 hay CART. - Ngồi việc giới hạn kích thước, tại mỗi nút trong của cây, xây dựng phân hoạch xiên phân (siêu phẳng phân hoạch hiệu quả thu được từ phân tích biệt lập tuyến tính FDA) dựa trên tập ngẫu nhiên các thuộc tính. - Việc xây dựng phân hoạch xiên phân giúp cải thiện tính mạnh mẽ của cây khi làm việc với các tập dữ liệu cĩ số chiều lớn và phụ thuộc lẫn nhau.. - Ví dụ như trong hình 1, bất kỳ việc phân hoạch đơn thuộc tính nào (song song với trục tọa độ như giải thuật C4.5 hay CART) đều khơng thể tách dữ liệu một lần duy nhất thành hai lớp một cách hồn tồn mà phải thực hiện nhiều lần phân hoạch, nhưng việc phân hoạch đa chiều (xiên phân, kết hợp 2 thuộc tính) cĩ thể thực hiện một cách hồn hảo với duy nhất một lần. - Để khắc phục nhược điểm trên, nhiều giải thuật xây dựng cây quyết định sử dụng phân hoạch đa thuộc tính (xiên phân) tại các nút được đề nghị. - Nghiên cứu tiên phong của (Murthy et al., 1993) đã đưa ra giải thuật OC1, một hệ thống dùng để xây dựng các cây quyết định xiên trong đĩ dùng leo đồi để tìm một phân hoạch xiên tốt dưới dạng một siêu phẳng.. - ArcX4 cây ngẫu nhiên xiên phân (ArcX4-rODT) của chúng tơi xây dựng các cây xiên phân ngẫu nhiên dựa trên siêu phẳng hiệu quả (phân hoạch hiệu quả cao, khả. - Ý tưởng chính của LDA là tìm véctơ sao cho khi chiếu dữ liệu lên đĩ thì độ biệt lập giữa trung bình dữ liệu của 2 lớp là lớn nhất và độ chồng lấp giữa 2 lớp là nhỏ nhất.. - Một cách ngắn gọn, xét một ví dụ phân lớp nhị phân tuyến tính (hình trịn, vuơng) như trong hình 2, với m điểm dữ liệu x i (i=1,m) trong khơng gian n chiều (thuộc tính). - Tập dữ liệu phân làm 2 lớp R 1 (cĩ N 1 phần tử), và R 2 (cĩ N 2 phần tử). - Mật độ phân bố (scatter) của dữ liệu 2 lớp sau khi chiếu : w. - Mục đích của bài tốn phân lớp là cần xác định siêu phẳng phân chia dữ liệu.. - Siêu phẳng do LDA tìm được sẽ khơng tốt khi mà độ biệt lập tuyến tính của dữ liệu khơng dựa vào hai trọng tâm m 1 và m 2 (trường hợp dữ liệu phi tuyến). - Vấn đề trên sẽ khơng ảnh hưởng lớn đến kết quả vì mơ hình cây quyết định thực hiện nhiều phân hoạch xiên phân LDA cho đến nút lá chứ khơng phải chỉ thực hiện duy nhất một lần phân hoạch.. - Việc sử dụng mơ hình cơ sở là các cây quyết định ngẫu nhiên xiên phân thay vì là phân hoạch 1 chiều như C4.5 hay CART giúp cho ArcX4-rODT trở nên hiệu quả, cĩ khả năng chịu đựng nhiễu cao, tránh học vẹt khi xử lý dữ liệu cĩ số phần tử nhỏ nhưng số chiều rất lớn và lại cĩ nhiễu như dữ liệu gien.. - 3 KẾT QUẢ THỰC NGHIỆM. - Để cĩ thể đánh giá hiệu quả của giải thuật, chúng tơi cài đặt giải thuật ArcX4 cây quyết định ngẫu nhiên xiên phân (ArcX4-rODT) bằng ngơn ngữ lập trình C/C++.. - Dữ liệu gien chúng tơi chạy thử nghiệm, cĩ số chiều rất lớn, được lấy tại (Jinyan &. - Bên cạnh đĩ, chúng tơi quan sát kết quả của ArcX4 cây quyết định ngẫu nhiên xiên phân trong thực nghiệm bằng cách so sánh với rừng ngẫu nhiên của cây quyết định C4.5 và SVM. - Chúng tơi cũng sử dụng mã nguồn của C4.5 được cung cấp bởi (Quinlan, 1993) để tạo ra giải thuật rừng ngẫu nhiên cây quyết định C4.5 (RF-C4.5 (Do et al., 2009. - Sau cùng chúng tơi cũng sử dụng giải thuật SVM chuẩn LibSVM (Chang &. - Chúng tơi tiến hành thực nghiệm trên 10 tập dữ liệu gien cĩ số chiều rất lớn từ kho dữ liệu sinh-y học. - Mơ tả các tập dữ liệu được tìm thấy trong bảng 1. - những tập dữ liệu cĩ sẵn tập học và tập thử, chúng tơi dùng tập học để thử điều chỉnh các tham số ở đầu vào của các giải thuật nhằm thu được độ chính xác tốt khi học. - Sau đĩ, dùng mơ hình thu được để phân lớp tập thử. - Do các tập dữ liệu cĩ ít hơn 300 phần tử, chúng tơi dùng giao thức kiểm tra chéo leave-one-out (loo). - Tức là dùng một phần tử trong tập dữ liệu để thử, các phần tử khác dùng để học. - Bảng 1: Mơ tả các tập dữ liệu gien. - ID Tập dữ liệu Số phần. - Để thấy rõ hơn tính hiệu quả của ArcX4-rODT so với RF-C4.5 và LibSVM, chúng tơi tiến hành phân tích hiệu quả của các thuật tốn phân lớp dựa trên các tiêu chí như precision, recall, F1-measure và accuracy [van Rijsbergen, 1979]. - Precision của một lớp là số điểm dữ liệu được phân lớp đúng về lớp này chia cho tổng số điểm dữ liệu được phân về lớp này. - Recall của một lớp là số điểm dữ liệu được phân lớp đúng về lớp này chia cho tổng số điểm dữ liệu của lớp. - Độ chính xác accuracy là số điểm dữ liệu được phân lớp đúng của tất cả các lớp chia cho tổng số điểm dữ liệu. - Chúng tơi thu được kết quả như trình bày trong bảng 2. - Từ bảng kết quả phân lớp thu được của các giải thuật khi xử lý 10 tập dữ liệu gien cho thấy giải thuật của chúng tơi, ArcX4 cây quyết định ngẫu nhiên xiên phân (ArcX4-rODT) cho kết quả tốt hơn so với các giải thuật rừng ngẫu nhiên thơng thường RF-C4.5 và SVM chuẩn LibSVM. - Dựa trên tiêu chí precision, ArcX4- rODT thắng 8 trong 10 tập dữ liệu. - Với tiêu chí recall và cả F1, ArcX4-rODT thắng 9 trong 10 tập dữ liệu.. - Bảng 2: Kết quả phân lớp của LibSVM, RF-C4.5 và ArcX4-rODT ID. - ArcX4- rODT. - ArcX4- rODT . - Quan sát đồ thị 1 trình bày kết quả với tiêu chí F1 của cả 3 giải thuật, giải thuật ArcX4-rODT của chúng tơi đề xuất luơn ở cận trên.. - Đồ thị 1: So sánh tiêu chí F1 của 3 giải thuật trên 10 tập dữ liệu. - Đồ thị 2 trình bày kết quả với tiêu chí accuracy cho thấy ArcX4-rODT của chúng tơi luơn tốt hơn LibSVM và RF-C4.5. - Những kết quả đạt được cho phép chúng tơi tin rằng giải thuật ArcX4 cây quyết định ngẫu nhiên xiên phân của chúng tơi đề nghị phân lớp hiệu quả trên dữ liệu gien cĩ số chiều rất lớn.. - Đồ thị 2: So sánh tiêu chí accuracy của 3 giải thuật trên 10 tập dữ liệu. - Chúng tơi vừa 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) cho phép phân lớp hiệu quả dữ liệu gien cĩ số chiều lớn và nhiễu. - 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. - Ý tưởng chính là 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 bộ phân lớp mạnh 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. - Các kết quả thử nghiệm trên các tập dữ liệu gien cho thấy rằng giải thuật ArcX4 cây quyết định ngẫu nhiên xiên phân chính xác hơn dựa trên tiêu chí về precision, recall, F1-measure và độ chính xác accuracy khi so sánh với rừng ngẫu nhiên của cây quyết định C4.5 và cả giải thuật SVM.