Tóm tắt Luận án Tiến sĩ Hệ thống thông tin: Cải tiến thuật toán phân lớp cho dữ liệu không cân bằng và ứng dụng trong dự đoán đồng tác giả

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:26

Thêm vào BST

Báo xấu

10
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục đích nghiên cứu của tóm tắt luận án "Cải tiến thuật toán phân lớp cho dữ liệu không cân bằng và ứng dụng trong dự đoán đồng tác giả" là đề xuất phương pháp cải tiến thuật toán học kết hợp dựa trên lặp thích nghi AdaBoost giải quyết bài toán phân lớp dữ liệu không cân bằng nói chung và bài toán dự đoán đồng tác giả nói riêng; đề xuất một thuật toán điều chỉnh trọng số mờ thích nghi cho bài toán dự đoán cộng tác đồng tác giả theo dạng học trên dữ liệu không cân bằng hai lớp;... Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt Luận án Tiến sĩ Hệ thống thông tin: Cải tiến thuật toán phân lớp cho dữ liệu không cân bằng và ứng dụng trong dự đoán đồng tác giả

BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC BÁCH KHOA HÀ NỘI VÕ ĐỨC QUANG CẢI TIẾN THUẬT TOÁN PHÂN LỚP CHO DỮ LIỆU KHÔNG CÂN BẰNG VÀ ỨNG DỤNG TRONG DỰ ĐOÁN ĐỒNG TÁC GIẢ Ngành: Hệ thống thông tin Mã số: 9480104 TÓM TẮT LUẬN ÁN TIẾN SĨ HỆ THỐNG THÔNG TIN HÀ NỘI−2024
Công trình được hoàn thành tại: Đại học Bách khoa Hà Nội Người hướng dẫn khoa học: PGS.TS. Trần Đình Khang Phản biện 1: PGS.TS. Nguyễn Việt Anh Phản biện 2: PGS.TS. Nguyễn Hải Châu Phản biện 3: PGS.TS. Nguyễn Văn Long Luận án được bảo vệ tại Hội đồng đánh giá luận án tiến sĩ cấp Đại học Bách khoa Hà Nội họp tại Đại học Bách khoa Hà Nội. Vào hồi 8 giờ 30, ngày 23 tháng 04 năm 2024. Có thể tìm hiểu luận án tại: 1. Thư viện Tạ Quang Bửu - ĐHBK Hà Nội 2. Thư viện Quốc gia Việt Nam.
MỞ ĐẦU 1. Bối cảnh nghiên cứu Khái niệm mạng đồng tác giả dùng để miêu tả mối quan hệ hợp tác cùng nghiên cứu giữa các nhà khoa học. Mạng đồng tác giả có thể xem như một mạng xã hội cộng đồng đặc biệt với các nút là các tác giả, các cạnh thể hiện mối liên kết giữa hai tác giả. Các bài toán phổ biến trong mạng đồng tác giả gồm: (i) các bài toán truy vấn thông tin như: tìm kiếm, tra cứu tạp chí, bài báo, tác giả, tổ chức, trích dẫn,... (ii) các bài toán dẫn xuất thông tin như: phân tích mối quan hệ học thuật, phân tích xu hướng nghiên cứu, đo lường tầm ảnh hưởng học thuật, đánh giá hiệu quả nghiên cứu và phát triển các hệ thống dự đoán (bài báo, tạp chí, đồng tác giả,...). Trong thực tế, muốn có các kết quả nghiên cứu tốt các nhà nghiên cứu phải tìm kiếm được các cộng sự hợp tác phù hợp. Do đó, việc nghiên cứu các phương pháp để xây dựng một hệ thống dự đoán cộng tác cùng nghiên cứu, gọi là bài toán dự đoán cộng tác đồng tác giả, trở nên cần thiết và có nhiều ý nghĩa trong việc thúc đẩy các hoạt động nghiên cứu khoa học. Bài toán dự đoán đồng tác giả được phát biểu như sau: Dựa trên thông tin kết nối của mạng đồng tác giả đến thời điểm hiện tại t, khi đưa thông tin đầu vào là một tác giả vi nào đó, hệ thống sẽ đưa ra một danh sách các tác giả vj , vk , vh , . . . có tiềm năng cộng tác hiệu quả với tác giả vi trong tương lai (tức là có sẽ cộng tác ở một thời điểm t’ nào đó sau t). Để giải quyết bài toán này, có các phương pháp nghiên cứu đề xuất gồm: (i) sử dụng độ đo tương đồng; (ii) xây dựng các mô hình dựa trên xác suất và khả năng tối đa; (iii) khai phá đồ thị (graph mining); (iv) học máy gồm: phân lớp, phân cụm và học sâu giảm chiều dữ liệu. Trong đó, hướng tiếp cận theo dạng phân lớp thu hút nhiều quan tâm nghiên cứu bởi có nhiều ưu điểm như: tích hợp đa dạng thông tin liên kết, khả năng mở rộng linh hoạt trong việc lựa chọn các giải thuật, khả năng điều chỉnh và cải thiện mô hình thông qua quá trình huấn luyện,... Để tiếp cận theo hướng này, sau khi xây dựng mạng đồng tác giả, bộ dữ liệu huấn luyện tạo ra từ mạng được gọi là dữ liệu bảng ứng viên. Trong đó, mỗi cặp tác giả ứng viên tiềm năng (vi , vj ) được xem như là một mẫu dữ liệu. Mức độ liên kết hợp tác của cặp ứng viên được biểu diễn bởi một véc-tơ thuộc tính, được tính bằng các độ đo liên kết. Nhãn lớp được xác định bằng cách khảo sát sự mở rộng liên kết trong mạng theo chiều thời gian. Mạng đồng tác giả được biểu diễn bằng một đồ thị thưa kết nối, do số lượng cặp tác giả có kết nối (cùng đứng tên trong một bài báo) là rất ít, trong khi số lượng cặp ứng viên đồng tác giả chưa cộng tác (cặp ứng viên tiềm năng) là rất nhiều. Vì vậy, dữ liệu bảng ứng viên có rất nhiều mẫu nhãn −1 (không liên kết) và rất ít mẫu có nhãn +1 (không liên kết), gây ra sự không cân bằng về số lượng mẫu giữa các lớp. Điều này gây thách thức cho các giải thuật học máy truyền thống vì các giải thuật này thường xem xét các mẫu bình đẳng nhau, dẫn đến các mô hình phân lớp thường thiên về dự đoán sai các mẫu thiểu số (nhãn +1). Có hai phương pháp thường dùng để giải quyết vấn đề này là: tiếp cận ở mức dữ liệu và tiếp cận ở mức giải thuật. Các phương pháp tiếp cận ở mức dữ liệu thay đổi sự phân bố số lượng mẫu trong bộ dữ liệu (resampling) bằng cách sinh thêm các phần tử cho lớp thiểu số (over sampling) hay giảm bớt các phần tử thuộc lớp đa số (under sampling). Các phương pháp tiếp cận ở mức giải thuật hướng tới việc điều chỉnh các thuật toán phân lớp cơ bản để vẫn có hiệu quả cao trên các tập dữ liệu không cân bằng như: học nhạy cảm chi phí, điều chỉnh xác suất ước lượng, sử dụng các hằng số phạt cho các nhãn lớp khác nhau. Một số nghiên cứu khác sử dụng kết hợp các kỹ thuật sampling và điều chỉnh trọng số chi phí để nâng cao chất lượng mô hình huấn luyện. Gần đây, luận án Tiến sĩ của Phạm Minh Chuẩn (2018) cũng tiếp cận giải quyết bài toán dự đoán đồng tác giả theo hướng phân lớp, trong đó đề xuất các độ đo liên kết mới để bổ sung thêm các đặc trưng của dữ liệu nhằm nâng cao chất lượng phân lớp của mô hình. Bên cạnh đó luận án có nêu ra vấn đề dữ liệu rất không cân bằng về nhãn lớp trong bảng ứng viên. Tiếp nối nghiên cứu này, kết hợp với khảo sát các nghiên cứu gần đây, chúng tôi nhận thấy các công bố nghiên cứu vấn đề học máy trên dữ liệu không cân bằng để khắc phục đặc điểm này của bộ dữ liệu đồng tác giả hầu như rất hạn chế. Điều này mở ra hướng nghiên cứu tiềm năng về các phương pháp cải tiến giải thuật, điều chỉnh các tham số mô hình để cải thiện chất lượng các mô hình dự đoán trong khung cảnh dữ liệu bảng ứng viên đồng tác giả có sự không cân bằng về nhãn lớp. Bên cạnh vấn đề dữ liệu không cân bằng về số lượng mẫu trong các lớp, để nâng cao chất lượng mô hình phân lớp là cần xử lý tốt việc phân loại chính xác trong các 1
vùng không gian nhạy cảm như: mẫu dữ liệu là nhiễu hoặc mẫu dữ liệu phân bố trong không gian ranh giới phân loại của hai lớp. Với những thông tin dữ liệu không đầy đủ, không chắc chắn, phương pháp xử lý mờ dựa trên lý thuyết mờ của Zadeh đưa ra vào năm 1965 tỏ ra hiệu quả. 2. Phạm vi và vấn đề nghiên cứu Luận án tập trung nghiên cứu bài toán dự đoán đồng tác giả, các thuật toán để phân lớp giải quyết vấn đề dữ liệu không cân bằng hai nhãn lớp. Trọng tâm của luận án là nghiên cứu, đề xuất các thuật toán nhằm nâng cao chất lượng phân lớp trên các bộ dữ liệu không cân bằng và ứng dụng trong dự đoán đồng tác giả. Phạm vi các thử nghiệm sử dụng các độ đo liên kết cơ bản và kế thừa bộ dữ liệu tự thu thập. Theo đó, luận án tập trung vào hai mục tiêu nghiên cứu chính: • Thứ nhất, nghiên cứu cải tiến thuật toán học kết hợp AdaBoost cho dữ liệu không cân bằng ứng dụng trong bài toán dự đoán đồng tác giả? Vấn đề nghiên cứu này hướng đến việc cải tiến thuật toán học kết hợp mạnh mẽ như AdaBoost để phù hợp cho dữ liệu không cân bằng thông qua việc thiết kế các tham số điều chỉnh thích nghi với mức độ không cân bằng của dữ liệu. • Thứ hai, nghiên cứu cải tiến thuật toán phân lớp mờ Fuzzy SVM cho dữ liệu không cân bằng và ứng dụng trong bài toán dự đoán đồng tác giả? Vấn đề nghiên cứu này hướng tới việc áp dụng điều chỉnh các trọng số đại lượng mờ kết hợp với giải thuật học dựa trên chi phí, giúp huấn luyện các mô hình phân lớp hiệu quả hơn khi dữ liệu có sự không cân bằng cao về nhãn lớp và các trường hợp dữ liệu trong vùng không gian nhạy cảm như gần đường biên phân lớp hoặc là dữ liệu nhiễu. 3. Đóng góp của luận án Hướng tới xây dựng các giải pháp hiệu quả cho các vấn đề nghiên cứu nói trên, luận án đã đưa đến các đóng góp chính: • Luận án đề xuất phương pháp cải tiến thuật toán học kết hợp dựa trên lặp thích nghi AdaBoost giải quyết bài toán phân lớp dữ liệu không cân bằng nói chung và bài toán dự đoán đồng tác giả nói riêng. Các cải tiến bao gồm: (1) phương pháp khởi tạo trọng số AdaBoost thích nghi với mức độ không cân bằng mẫu trong tập dữ liệu và (2) phương pháp tính trọng số độ tin cậy cho bộ phân lớp thành viên nhạy cảm với tổng lỗi trên mẫu nhãn dương. Các kết quả nghiên cứu này đã được công bố trong 2 bài báo số [CT.1] và [CT.3]. • Luận án đề xuất một thuật toán điều chỉnh trọng số mờ thích nghi cho bài toán dự đoán cộng tác đồng tác giả theo dạng học trên dữ liệu không cân bằng hai lớp. Thuật toán đề xuất có hai cải tiến chính: (1) xây dựng một hàm tính trọng số mờ cho các mẫu dữ liệu giàu ngữ nghĩa hơn dựa trên Fuzzy SVM-CIL khi xem xét khoảng cách từ mỗi mẫu đến tâm của cả hai lớp; (2) phương pháp điều chỉnh thích nghi các giá trị trọng số mờ của mẫu nằm trong không gian phân lớp nhạy cảm như trên đường biên hoặc mẫu là nhiễu dựa trên KNN, Tomek link và SVM. Các kết quả nghiên cứu này đã được công bố các bài báo số [CT.2][CT.4][CT.5]. 4. Bố cục của luận án Với các đóng góp nêu trên, luận án được trình bày trong 3 chương: • Chương 1: Trình bày các kiến thức tổng quan về đề tài: giới thiệu bài toán phân lớp với dữ liệu không cân bằng, bài toán dự đoán đồng tác giả theo dạng bài toán phân lớp, các thuật toán cơ sở, các bộ dữ liệu thử nghiệm, môi trường thử nghiệm làm cơ sở cho các đề xuất và thử nghiệm ở các chương tiếp theo. • Chương 2: Trình bày đề xuất một số phương pháp cải tiến giải thuật AdaBoost cho bài toán dữ liệu không cân bằng, ứng dụng cho dự đoán cộng tác đồng tác giả. • Chương 3: Trình bày đề xuất một giải thuật trọng số mờ thích nghi nhằm giải quyết vấn đề dữ liệu không cân bằng và xử lý vấn đề phân lớp cho các mẫu nhạy cảm ở vùng biên hoặc nhiễu cho bài toán dự đoán cộng tác đồng tác giả. Với các chương này, luận án đã trình bày đầy đủ các kiến thức nền tảng và chi tiết nội dung giải pháp cho các câu hỏi nghiên cứu giúp giải quyết hiệu quả các thách thức nêu ra. 2
Chương 1 TỔNG QUAN VỀ VẤN ĐỀ NGHIÊN CỨU Chương này giới thiệu phương pháp tiếp cận phân lớp để giải quyết bài toán dự đoán đồng tác giả và những kiến thức nền tảng liên quan đến việc giải quyết vấn đề học trên dữ liệu không cân bằng. 1.1. Bài toán phân lớp với dữ liệu không cân bằng Bài toán phân lớp trên dữ liệu không cân bằng là một vấn đề thách thức trong học máy. Để giải quyết vấn đề học trên dữ liệu không cân bằng có hai hướng giải quyết chính: tiếp cận mức dữ liệu và tiếp cận mức giải thuật. Các phương pháp tiếp cận mức dữ liệu sử dụng các kỹ thuật can thiệp vào bộ dữ liệu gốc (ReSampling) để tạo ra bộ dữ liệu huấn luyện có tỷ lệ phân bố mẫu cân bằng hơn, từ đó làm cơ sở cho các giải thuật phân lớp truyền thống hoạt động hiệu quả hơn. Kỹ thuật ReSampling có thể sinh thêm các phần tử cho lớp thiểu số như Random Oversampling, SMOTE, Border-line-SMOTE, ADA-SYN, Cluster Based Sampling-CBO, SMOTEBoost, OSD... hay giảm bớt các mẫu lớp đa số như EasyEnsemble, BalanceCascade, KNN-NearMiss,... Các phương pháp tiếp cận ở mức giải thuật hướng tới việc điều chỉnh các thuật toán phân lớp như: học dựa trên nhạy cảm chi phí, điều chỉnh xác suất ước lượng, sử dụng Boosting như AdaC1, AdaC2, AdaC3, Cây quyết định, sử dụng các hàm kernel SVM, sử dụng kỹ thuật học sâu,... Các phương pháp cải tiến dựa trên AdaBoost, SVMs và học sâu thu hút rất nhiều sự quan tâm bởi khả năng tùy biến cho các bài toán có dữ liệu có tính chất khác nhau, nổi bật như là Weighted-SVM, Kernel-SVM, đặc biệt là Fuzzy SVM, Fuzzy SVM-CIL. Bên cạnh đó, một vấn đề chung để nâng cao chất lượng mô hình phân lớp là cần phân lớp chính xác trong các vùng không gian nhạy cảm như: mẫu dữ liệu là nhiễu hoặc mẫu dữ liệu nằm trong không gian ranh giới phân lớp. Để xác định các vùng không gian chứa các mẫu nhạy cảm, chúng ta cần sử dụng phương pháp đo lường khoảng cách giữa các mẫu hoặc xem xét phân bố các mẫu. Các giải thuật như K-nearest neighbors (KNN) và Tomek link và SVM cho phép định vị các mẫu trong không gian phân bố. Ngoài ra, với những thông tin dữ liệu không đầy đủ, không chắc chắn, phương pháp xử lý mờ dựa trên lý thuyết mờ của Zadeh đưa ra vào năm 1965 tỏ ra hiệu quả. 1.2. Một số thuật toán liên quan 1.2.1. Thuật toán SVM SVM đã được nghiên cứu, thử nghiệm và chứng minh là một phương pháp phân lớp mạnh, đặc biệt hiệu quả đối với các dữ liệu phân biệt tuyến tính. Ngoài ra, giải thuật cũng khá mềm dẻo và có khả năng cải tiến mở rộng để đạt hiệu quả cao trên những bộ dữ liệu có đặc tính khác nhau. Đối với vấn đề phân lớp nhị phân, với tập dữ liệu D = {(xi , yi )|i = 1, 2, · · · , N }, trong đó xi ∈ Rn đại diện cho một điểm dữ liệu n chiều và yi ∈ {−1, +1} là nhãn lớp của xi . Mục tiêu của thuật toán SVM là tìm ra một siêu phẳng phân tách các điểm dữ liệu này thành hai lớp trong không gian đặc trưng Rn . Hàm mục tiêu cần tối ưu cho siêu phẳng phân tách trong không gian đặc trưng Rn được biểu thị bằng: ⟨ω, x⟩ + b = 0, (1.1) trong đó ω là ma trận tham số, b là hệ số. 1.2.2. Thuật toán Weighted-SVM Giải thuật Weighted-SVM (WSVM) là một cải tiến nổi bật của SVM. Với tập dữ liệu D = {(xi , yi )|i = 1, 2, · · · , N }, trong đó xi ∈ Rn là véc-tơ đặc trưng n chiều và yi ∈ {−1, +1} là nhãn lớp của xi . WSVM gán các trọng số cho các mẫu để biểu thị ảnh hưởng của mẫu trong việc huấn luyện mô hình phân lớp. Hàm mục tiêu như sau. N 1 min ∥ω∥2 + C mi ξi , 2 (1.2) i=1 st. yi ∗ (⟨ω, xi ⟩ + b) ≥ 1 − ξi , ξi ≥ 0, with i = 1, 2, . . . , N, 3
trong đó các biến ξi > 0 đại diện cho mức độ “phân loại sai” của các mẫu, N ξi là tổng lỗi trên các i=1 mẫu và C là tham số để kiểm soát sự đánh đổi giữa độ rộng lề tối đa và tổng lỗi tối thiểu trên các mẫu. Lưu ý rằng mi là một trọng số phản ánh tầm quan trọng của việc phân loại chính xác mẫu xi . Giá trị trọng số của một mẫu càng lớn thì mẫu đó càng quan trọng trong việc tự phân loại chính xác. 1.2.3. Fuzzy SVM Batuwita và các cộng sự đã đề xuất thuật toán Fuzzy SVM-CIL (FSVM-CIL) dựa trên thuật toán Fuzzy SVM để cải thiện hiệu quả phân lớp cho dữ liệu không cân bằng. FSVM-CIL gán các giá trị trọng số mờ cao hơn m+ (i = 1, 2, · · · , N ) cho các mẫu thiểu số x+ (nhãn +1) và các giá trị trọng số mờ thấp i i hơn m− (i = 1, 2, · · · , N ) cho các mẫu đa số x− (nhãn -1). Các giá trị trọng số mờ được tính bằng: i i m+ = f x+ × r+ , i i (1.3) m− = f x− × r− , i i trong đó f (xi ) ∈ (0, 1) là một hàm thuộc mờ phản ánh tầm quan trọng của xi trong lớp của chính nó, trong khi r+ và r− biểu thị mức độ ảnh hưởng của tỷ lệ không cân bằng trong tập dữ liệu. FSVM-CIL chỉ định r+ = 1 và r− = r, trong đó r là tỷ lệ không cân bằng giữa lớp +1 và lớp −1, vì vậy r < 1. Theo đó, trọng số mờ trên các mẫu +1 có thuộc khoảng (0, 1), còn trọng số trên mẫu −1 có giá trị trong khoảng (0, r). Hàm thuộc f (xi ) được xác định dựa trên vị trí của mẫu xi trong không gian đặc trưng Rn và xem xét các khoảng cách từ mẫu xi : đến mẫu đại diện cho trung tâm lớp của nó (dcen ); đến i siêu phẳng ước tính (dshp ) được xác định là trung tâm của toàn bộ tập dữ liệu; đến siêu phẳng thực tế i (dhyp ) được hình thành bởi mô hình phân lớp SVM cơ sở. Đối với mỗi phương pháp tính khoảng cách, i FSVM-CIL xây dựng hai hàm thuộc mờ tuyến tính (lin) và hàm mũ mờ (exp) tạo ra sáu hàm thuộc của mẫu xi như sau: cen dcen i flin (xi ) = 1 − , (1.4) max (dcen ) + ∆ i cen 2 fexp (xi ) = . (1.5) 1 + exp (βdcen ) i shp dshp i flin (xi ) = 1 − , (1.6) max dshp + ∆ i shp 2 fexp (xi ) = . (1.7) 1 + exp βdshp i hyp dhyp i flin (xi ) =1− , (1.8) max dhyp + ∆ i hyp 2 fexp (xi ) = , (1.9) 1 + exp βdhyp i cen shp hyp trong đó ∆ là một giá trị dương nhỏ để tránh trường hợp flin (xi ) = 0, flin (xi ) = 0, flin (xi ) = 0 và cen shp hyp β ∈ [0, 1] để kiểm soát độ dốc của các hàm số mũ fexp (xi ), fexp (xi ) và fexp (xi ). 1.2.4. Thuật toán AdaBoost Thuật toán AdaBoost do Freund đề xuất là một bộ phân lớp mạnh dựa trên sửa lỗi, thích nghi qua các vòng lặp. Các bước của thuật toán AdaBoost được trình bày trong Thuật toán 1.1. Cụ thể, AdaBoost có dữ liệu đầu vào bao gồm: (i) X là tập dữ liệu gồm N mẫu (xi , yi ), trong đó xi là vectơ thuộc tính và yi ∈ {−1, +1} là nhãn lớp của xi ; (ii) M là số lần lặp tối đa; và (iii) ht là một bộ phân lớp 1 thành viên. Đầu tiên thuật toán gán một tập các trọng số lỗi bằng nhau D1 = {wi = N } cho mỗi mẫu 1 xi ∈ X . Trong mỗi lần lặp, bộ phân lớp ht sẽ phân loại tập dữ liệu X (dòng 3). Chất lượng phân lớp của ht được đánh giá thông qua tổng lỗi εt (dòng 4) và trọng số tin cậy αt (dòng 5). Sau đó, thuật toán t+1 cập nhật lại phân bố trọng số lỗi ωi (dòng 6). Cuối cùng, một mô hình phân lớp tổng hợp được tính 4
Thuật toán 1.1: Thuật toán AdaBoost Input: Tập dữ liệu X = {(x1 , y1 ), . . . , (xN , yN )} với yi = {−1, +1}; M : số bộ phân lớp thành viên; h1 : bộ phân lớp thành viên. Output: H(x): bộ phân lớp tập hợp. 1 1 Khởi tạo tập trọng số lỗi D1 = {ωi = N } trên mỗi mẫu dữ liệu (xi , yi ) ∈ X (i = 1, · · · , N ); 1 2 for t = 1 to M do 3 Đặt ht ← Training(X) với tập trọng số lỗi Dt ; N t 4 Tính tổng lỗi của ht : εt = i=1 ωi , yi ̸= ht (xi ); 5 Tính trọng số độ tin cậy của ht : αt = 1 ln 1−εt ; 2 εt t t+1 ωi .exp[−αt yi ht (xi )] 6 Cập nhật trọng số lỗi cho vòng lặp tiếp theo: ωi = Lt , với Lt là hệ số chuẩn hóa N t+1 sao cho i=1 ωi = 1; M 7 return H(x) = sign( t=1 αt ht (x)). toán theo công thức H(x) = sign( M αt ht (x)). Nhãn phân lớp của mẫu được xác định dựa vào hàm t=1 ký hiệu: nhãn +1 khi H(x) > 0 và nhãn −1 khi H(x) < 0. Nếu tổng lỗi εt trên tập dữ liệu bằng 0.5, thì αt = 0, nghĩa là bộ phân lớp ht (x) không đóng góp vào quyết định phân lớp của bộ phân lớp tổng hợp H(x). 1.2.5. Thuật toán CNN Mạng nơ-ron nhân chập (Convolutional Neural Networks – CNN) là một mạng điển hình cho mô hình học sâu lấy cảm hứng từ cấu trúc và chức năng của thị giác con người. CNN là một mạng nơ-ron truyền thẳng có nhiều tầng, trong đó tầng nhân chập (Convolutional Layer) và tầng gộp (Pooling Layer) được sắp xếp hoán đổi lẫn nhau, tầng cuối cùng là một tầng kết nối đầy đủ (Dense Layer). Đặc trưng nổi bật của CNN là trong quá trình tích chập nó sử dụng nhiều bộ lọc đặc trưng trượt trên các ma trận điểm dữ liệu để trích xuất các đặc trưng tương ứng của dữ liệu. Trong khi 2D-CNN thường được sử dụng đặc hiệu cho các ứng dụng trong lĩnh vực thị giác máy tính thì 1D-CNN được thiết kế đặc biệt để hoạt động với dữ liệu một chiều. Có thể kể đến một số lợi ích khi sử dụng 1D-CNN so với 2D-CNN như độ phức tạp tính toán được giảm xuống đáng kể, kiến trúc mạng nông dễ hiểu và dễ triển khai hơn và việc huấn luyện 1D-CNN sử dụng ít tài nguyên tính toán hơn so với 2D-CNN. Đã có nhiều nghiên cứu chỉ ra việc áp dụng 1D-CNN trong việc giải quyết các bài toán thực tế có dữ liêu một chiều, điển hình như bài toán phát hiện tấn công mạng, phát hiện lỗi trong các thiết bị công nghiệp, dự báo mức nicotin trong việc xây dựng các ứng dụng cai thuốc lá, phân loại hỗn hợp cá hồi và cá tuyết. 1.2.6. Phương pháp Cây quyết định Cây quyết định hoạt động bằng cách phân chia không gian đặc trưng thành các phần con, mỗi phần được gán một nhãn hoặc giá trị dự đoán. Quá trình này được thực hiện thông qua các quyết định dựa trên các đặc trưng của dữ liệu. Cây quyết định được tạo ra, trong đó mỗi nút trong cây đại diện cho một quyết định dựa trên giá trị của một thuộc tính. Thuật toán bắt đầu bằng việc chọn thuộc tính tốt nhất để phân chia tập dữ liệu. Thuộc tính tốt nhất là thuộc tính có khả năng phân chia tập dữ liệu thành các phần con sao cho sự thuần khiết nhất của mỗi phần con là cao nhất. Quá trình phân chia được lặp lại cho mỗi nhóm con cho đến khi một điều kiện dừng được đáp ứng, chẳng hạn như đạt được một độ sâu cố định của cây hoặc không còn khả năng phân chia tốt hơn. 1.2.7. K-nearest neighbors và Tomek link Thuật toán KNN xem xét nhãn lớp của K điểm gần nhất với dữ liệu cần phân lớp để quyết định nhãn cho mẫu cần phân lớp. Việc tìm khoảng cách giữa hai điểm dữ liệu thường sử dụng các độ đo như: Euclidean, Manhattan, Minkowski, Hamming. Thuật toán Tomek link là một phương pháp trong lĩnh vực xử lý dữ liệu không cân bằng trong học máy và khai phá dữ liệu. Giải thuật Tomek link xác định các cặp gồm hai mẫu thuộc hai lớp khác nhau với khoảng cách ngắn nhất (TLP). Giả sử Smin và Smaj lần lượt là tập hợp các mẫu đa số và thiểu số, và d(xi , xj ) là khoảng cách giữa xi ∈ Smin và xj ∈ Smaj . Cặp (xi , xj ) được gọi là TLP nếu không tồn tại xk sao cho d(xi , xk ) < d(xi , xj ) hoặc d(xj , xk ) < d(xi , xj ). Bằng cách loại bỏ hoặc giảm thiểu 5
Bảng 1.1: Các độ đo liên kết trong mạng đồng tác giả a) Các độ đo liên kết dựa trên hàng xóm CN (vi , vj ) = |Γ(vi ) ∩ Γ(vj )| 1 AA(vi , vj ) = vk ∈Γ(vi )∩Γ(vj ) log(|Γ(vk )|) Γ(vi )∩Γ(vj ) JC(vi , vj ) = Γ(vi )∪Γ(vj ) P A(vi , vj ) = |vi | × |vj | 1 RA(vi , vj ) = vk ∈Γ(vi )∩Γ(vj ) |Γ(vk )| b) Các độ đo liên kết dựa trên đường dẫn 1 SH(vi , vj ) = d(vi ,vj ) Katz(vi , vj ) = ∞ β l |pathl i ,vj | l=1 v c) Các độ đo liên kết dựa trên quan hệ cộng đồng   2, if S (v ) = S (v ) = · · · = S (v ),    1 1 1 2 1 N SW (v1 , v2 , · · · , vN ) = 1, if S2 (v1 ) = S2 (v2 ) = · · · = S2 (vN ),    0, otherwise,  CC(vi , vj ) = SW (vi , vj ) + vk ∈Γ(vi )∩Γ(vj ) SW (vk , vi , vj ) những TLP này, thuật toán cố gắng làm cho không gian đặc trưng trở nên rõ ràng và tăng cường khả năng phân loại của mô hình. 1.3. Bài toán dự đoán đồng tác giả 1.3.1. Mô hình hóa bài toán Mạng đồng tác giả được mô hình hóa dưới dạng đồ thị GT với bốn yếu tố đặc trưng GT = (V T , E T , P T , T ), trong đó (i) T = {t1 , t2 , . . . , tk } là một tập hợp các nhãn thời gian; (ii) V T = {v1 , v2 . . . . , vN } là tập hợp các đỉnh đại diện cho các tác giả xuất hiện trong bài báo tại một thời điểm nào đó trong T ; (iii) P T = {p1 , p2 , . . . , pM } là tập hợp các bài báo tại một thời điểm nào đó trong T ; và (iv ) E T = {vi , vj , pk , th } là tập hợp các liên kết giữa các tác giả tại một thời điểm nào đó trong T , trong đó hai tác giả (vi , vj ) ∈ V T × V T có viết chung một bài báo pk ∈ P T tại thời điểm th ∈ T . Ngoài ra, đỉnh V T có thể chứa các thông tin bổ sung của từng tác giả như thông tin quốc tịch, mối quan hệ cộng đồng, chủ đề nghiên cứu. Tập các thuộc tính này được ký hiệu là AT = {a1 , a2 , . . . , aN }, trong đó ai là một vectơ đặc trưng chứa thông tin về cặp tác giả/đỉnh (vi , vj ) ∈ V T × V T . Các độ đo sự tương đồng giữa hai tác giả chủ yếu được xây dựng dựa trên thông tin của các tập E T và AT . Có hơn 27 độ đo liên kết được xây dựng dựa vào sự xem xét các đặc tính tương đồng cục bộ và tương đồng toàn cục. Trong luận án này chỉ trình bày một số độ đo phổ biến thuộc ba nhóm chính như sau: (i) Độ đo liên kết dựa trên hàng xóm: Common Neighbor (CN ), Adamic Adar (AA), Jaccard Coefficient (JC ), Preferential Attachment (P A) và Resource Allocation (RA); (ii) Các độ đo liên kết dựa trên đường dẫn: Shortest Path và Katz; (iii) Các độ đo liên kết dựa trên thông tin cá nhân bổ sung: độ tương tự về công việc SimWork (SW ) và về địa lý quốc gia CommonCountry (CC ). Các độ độ được xác định bằng các công thức trong Bảng 1.1. ′ Bài toán dự báo dự báo liên kết đồng tác giả được diễn giải như sau: cho hai khoảng thời gian [t0 , t0 ], ′ ′ và [t1 , t1 ] thỏa mãn t0 < t1 . Dựa trên cấu trúc mạng quan sát được tại thời điểm [t0 , t0 ], ta sẽ dự đoán ′ các liên kết mới sẽ xuất hiện trong thời gian [t1 , t1 ] mà chưa xuất hiện trong khoảng thời gian được quan sát. Các liên kết mới được dự đoán tương ứng với việc cặp tác giả của liên kết đó có khả năng hợp tác mới trong tương lai. 1.3.2. Phương pháp phân lớp cho bài toán dự đoán đồng tác giả Bộ dữ liệu học máy cho bài toán dự đoán đồng tác giả được gọi là bảng ứng viên đồng tác giả, gọi tắt là bảng ứng viên. Giả sử chúng ta dùng một lát cắt thời gian t∗ , gọi các nhãn thời gian từ thời điểm t∗ trở về trước là tập T1 , gọi các nhãn thời gian sau thời điểm t∗ là tập T2 . Khi đó t∗ sẽ chia không gian mạng đồng tác giả GT thành hai mạng con là GT1 và GT2 . Xét theo tiến trình thời gian, mạng GT2 chính là các mối liên kết mới chưa từng xuất hiện trong GT1 . Để xây dựng bộ dữ liệu học máy cho 6
Bảng 1.2: Bảng ứng viên đồng tác giả Cặp ứng viên Độ đo liên kết Nhãn lớp TT (vi , vj ) (CN, AA, JC, P A, RA, ShortestP ath, Kazt, CommCountry) (−1/ + 1) 1 (v1 , v2 ) {X1CN , X1AA , X1JC , X1P A , X1RA , X1ShortestP ath , X1Kazt , X1CommCountry } +1 2 (v1 , v3 ) {X2CN , X2AA , X2JC , X2P A , X2RA , X2ShortestP ath , X2Kazt , X2CommCountry } −1 3 (v1 , v4 ) {X3CN , X3AA , X3JC , X3P A , X3RA , X3ShortestP ath , X3Kazt , X3CommCountry } −1 ··· ··· ··· ··· bài toán, chúng ta cần xác định mẫu dữ liệu (cặp ứng viên), tính toán véc-tơ đặc trưng và gán nhãn dữ liệu. Cặp ứng viên (vi , vj ) là cặp tác giả có khả năng cộng tác nghiên cứu trong tương lai. Véc-tơ đặc trưng cho mẫu (vi , vj ) được xác định bởi các độ đo liên kết cho cặp tác giả (vi , vj ) sử dụng thông tin trong GT1 . Xác định nhãn cho mẫu (vi , vj ) sử dụng thông tin trong GT2 để gán nhãn cho mẫu dựa trên việc xem xét việc có sự cộng tác thực sự của vi và vj trong T2 hay không. Nếu vi và vj có viết chung bài báo thì gán nhãn +1 , nếu không cộng tác thì gán nhãn −1. Dữ liệu bảng ứng viên đồng tác giả có cấu trúc được minh họa trong Bảng 1.2 trở thành bộ dữ liệu học máy hai nhãn lớp. Một cách trực quan, chúng ta có thể coi bảng dữ liệu ứng viên là một tập mẫu dữ liệu đồng tác giả với đầy đủ các thuộc tính và nhãn lớp. Do đó, bài toán dự đoán đồng tác giả được chuyển thành bài toán phân lớp trên tập dữ liệu hai nhãn lớp, trong đó một lớp được gắn nhãn là +1 để biểu thị sự hợp tác trong tương lai và lớp còn lại được gắn nhãn là −1 để biểu thị không có sự hợp tác trong tương lai. Lược đồ mô tả các bước thực hiện để xây dựng mô hình gợi ý cộng tác đồng tác giả được trình bày trong Hình 1.1. Hình 1.1: Mô hình gợi ý cộng tác đồng tác giả theo phương pháp phân lớp Trong thực tế, mạng đồng tác giả có sự thưa về kết nối, bởi vì số lượng cặp tác giả có kết nối(cùng đứng tên trong một bài báo) là rất ít hơn nhiều so với số lượng cặp ứng viên đồng tác giả chưa cộng tác (cặp ứng viên tiềm năng). Theo đó, bảng ứng viên sẽ là một bộ dữ liệu có rất nhiều mẫu nhãn −1 và rất ít mẫu có nhãn +1, gây ra sự không cân bằng về số lượng mẫu giữa các lớp. 1.4. Tập dữ liệu thử nghiệm và phương pháp thực nghiệm đánh giá Dữ liệu được thu thập từ ScienceDirect trên 3 tạp chí: Chemical Physics Letters, Journal of Molecular Biology và Biochemical and Biophysical Research Communications từ năm 2000 đến hết năm 2017. Thông tin bao gồm: ID, tiêu đề, tóm tắt, từ khóa và danh sách tác giả. Từ dữ liệu đã thu thập được, chúng tôi lựa chọn các khung thời gian T1 , T2 khác nhau để tiến hành xây dựng dữ liệu bảng ứng viên đồng tác giả bao gồm các độ đo liên kết và gán nhãn. Để đánh giá hiệu suất của thuật toán một cách tổng quát, chúng tôi sử dụng kỹ thuật lấy mẫu ngẫu nghiên trên tập dữ liệu lớn để tạo ra các bộ dữ liệu con có kích thước mẫu và tỷ lệ không cân bằng khác nhau. Các thử nghiệm cũng mở rộng trên các bộ dữ liệu lưu trữ bởi UCI như: Transfusion, Ecoli, Yeast và Abalone. Các kết quả thử nghiệm được đo lường đánh giá bằng các độ đo phổ biến trong học trên dữ liệu không cân 7
bằng như SE, SP, AU C, G − mean, F 1 − Score. Trong đó, tập trung phân tích ở 3 độ đo quan trọng SE, G − mean, AU C khi xem xét bài toán phân lớp với dữ liệu không cân bằng. Số liệu được trình bày đa dạng ở dạng bảng và biểu đồ để phân tích so sánh mô hình với các khía cạnh khác nhau. Tất cả các thử nghiệm cài đặt thuật toán trong luận án được thực hiện trên máy tính xách tay có cấu hình chính như sau CPU Core i7-8550U 1,8 GHz, RAM 16 GB, SSD 256GB chạy trên hệ điều hành Windows 11. Phiên bản phần mềm sử dụng là Anaconda 2022, PyThon 3.11 và các thư viện hỗ trợ. Các kịch bản thử nghiệm được thiết kế phù hợp với mục đích so sánh các phương pháp đa dạng với nhau, nhằm đánh giá một cách công bằng hiệu quả của phương pháp đề xuất trong từng trường hợp cụ thể. 1.5. Kết luận chương 1 Chương 1 đã giới thiệu về bài toán phân lớp dữ liệu không cân bằng và các thuật toán cơ sở thường được áp dụng để giải quyết vấn đề như SVM, WSVM, FSVM, FSVM-CIL, AdaBoost, 1D-CNN, Cây quyết định, KNN, Tomek link. Bên cạnh đó chương cũng trình bày cách mô hình hóa bài toán dự đoán đồng tác giả theo phương pháp phân lớp trên dữ liệu không cân bằng của bảng ứng viên đồng tác giả. Các phương pháp đánh giá thực nghiệm, môi trường thử nghiệm và bộ dữ liệu thử nghiệm cũng được trình bày nhằm phục vụ cho việc đánh giá hiệu quả của các đề xuất cải tiến thuật toán trong Chương 2 và Chương 3. 8
Chương 2 CẢI TIẾN GIẢI THUẬT ADABOOST CHO DỮ LIỆU KHÔNG CÂN BẰNG Trong Chương này, luận án đề xuất một thuật toán cải tiến AdaBoost cho bài toán phân lớp dữ liệu không cân bằng hai lớp gọi là Im.AdaBoost với hai cải tiến chính: (i) phương pháp khởi tạo trọng số AdaBoost thích nghi mức độ không cân bằng và (ii) phương pháp tính trọng số độ tin cậy cho bộ phân lớp thành viên nhạy cảm với tổng lỗi gây ra trên mẫu nhãn dương. Sau đó, thuật toán Im.AdaBoost được đề xuất kết hợp với Weighted-SVM như là bộ phân lớp thành viên tạo thành Im.AdaBoost.WSVM để giải quyết bài toán phân lớp dữ liệu không cân bằng nói chung và bài toán dự đoán đồng tác giả khi tiếp cận theo dạng phân lớp nói riêng. Các thử nghiệm trên bộ dữ liệu đồng tác giả có các kích thước và tỷ lệ không cân bằng khác nhau được thực hiện để đánh giá hiệu suất của thuật toán. 2.1. Đặt vấn đề Nhắc lại thuật toán AdaBoost trong Thuật toán 1.1, chúng ta thấy rằng AdaBoost gán trọng số lỗi t khởi tạo ωi cho mỗi mẫu dữ liệu là bằng nhau. Tức là xem xét mức độ quan trọng của các mẫu trong việc huấn luyện mô hình là như nhau. Tuy nhiên với bài toán dữ liệu không cân bằng cần phải gán trọng số lỗi cho các nhãn dương +1 là cao hơn các mẫu âm −1, để điều chỉnh việc huấn luyện mô hình phân lớp được tốt cho các nhãn dương +1. Hơn nữa, nếu mức độ không cân bằng càng cao (tỷ lệ nhãn dương +1 trong tập mẫu càng nhỏ) thì cần gán trọng số lỗi khởi tạo càng cao, theo hướng tỷ lệ nghịch với mức độ không cân bằng. Ngoài ra, kết quả mô hình phân lớp cuối cùng H(x) được tổng hợp từ kết quả của các bộ phân lớp thành viên ht (x), trong đó sử dụng một trọng số αt mang ý nghĩa là độ tin cậy của mỗi bộ phân lớp thành viên ht (x). Trọng số αt được tính dựa trên một hàm nghịch đảo của tổng lỗi trên toàn bộ tập dữ liệu εt , mà không xem xét chất lượng phân lớp của bộ phân lớp thành viên trên mẫu +1 hay −1. Nghĩa là độ tin cậy αt của bộ phân lớp thành viên ht (x) không phân biệt được việc ht (x) phân lớp sai nhiều trên các mẫu nhãn âm hay sai nhiều trên các mẫu nhãn dương. Trong trường hợp dữ liệu không cân bằng, chúng ta có thể phân tích kỹ hơn các tổng lỗi trên từng mẫu nhãn dương +1 và nhãn âm −1 để đưa ra trọng số độ tin cậy của bộ phân lớp thành viên hợp lý hơn, từ đó gián tiếp tạo ảnh hưởng đến kết quả của mô hình phân lớp tổng hợp H(x). 2.2. Đề xuất thuật toán Im.AdaBoost 2.2.1. Phương pháp khởi tạo trọng số cho AdaBoost thích nghi với mức độ không cân bằng Luận án đề xuất một phương pháp mới để khởi tạo trọng số lỗi nhằm thích nghi tốt hơn với tỷ lệ không cân bằng dữ liệu bằng cách ưu tiên gán trọng số lỗi ban đầu cao hơn cho các mẫu nhãn dương. Giả sử rằng Nmin và Nmaj lần lượt là số lượng mẫu nhãn dương và nhãn âm (nghĩa là số lượng mẫu của nhóm thiểu số và đa số), trong đó Nmin + Nmaj = N và Nmin ≤ Nmaj . Việc điều chỉnh trọng số lỗi bằng cách tăng một lượng ∆min vào trọng số mẫu +1 và giảm một giá trị ∆maj của trọng số lỗi mẫu 1 nhãn −1. Theo đó, trọng số lỗi ωi (i = 1, 2, . . . N )) của mỗi mẫu (xi , yi ) ∈ X được xác định như sau: 1 1 N + ∆min , nếu yi = +1, ωi = 1 (2.1) N − ∆maj , nếu yi = −1, trong đó ∆min và ∆maj phải thỏa mãn hai điều kiện sau: 1 1. Đại lượng điều chỉnh trọng số mẫu ∆min , ∆maj lớn hơn 0 và ∆maj nhỏ hơn N, nghĩa là: 1 0 < ∆min và 0 < ∆maj < . (2.2) N 2. Tổng lỗi trên các mẫu bằng 1, hay: Nmin Nmaj + Nmin × ∆min + − Nmaj × ∆maj = 1. (2.3) N N 9
Xem xét Eq. (2.3) kết hợp với Nmin + Nmaj = N , chúng ta có: Nmin + Nmaj + Nmin × ∆min − Nmaj × ∆maj = 1, (2.4) N hoặc Nmin × ∆min = Nmaj × ∆maj . (2.5) Nmin Gọi tỷ lệ giữa số mẫu nhãn dương với số mẫu nhãn âm là δ = Nmaj , trong đó 0 < δ ≤ 1, từ biểu thức (2.5), ta có: Nmaj ∆maj ∆min = × ∆maj = . (2.6) Nmin δ Từ phương trình. (2.2) và (2.6), chúng ta có các điều kiện sau để ∆min và ∆maj : 1 0 < ∆min , ∆maj < N, ∆maj (2.7) ∆min = δ . Luận án đề xuất chọn ∆maj = 1−δ , do đó ∆min = N 1−δ δ×N . Từ Eq. (2.1), tập hợp các trọng số lỗi được xác định bởi D1 = ωi (i = 1, 2, . . . N ), trong đó 1 1 1 1−δ 1 N + ∆min = N + δ×N , nếu yi = +1, ωi = 1 1 1−δ (2.8) N − ∆maj = N − N , nếu yi = −1. Khi áp dụng phương trình Eq. (2.8) cho các bộ dữ liệu có tỷ lệ không cân bằng khác nhau, trọng số lỗi của các mẫu dương có xu hướng tăng lên, trong khi trọng số lỗi của các mẫu âm có xu hướng giảm Nmin xuống, tùy thuộc vào giá trị của δ = Nmaj . Khi tập dữ liệu được cân bằng, nghĩa là δ = 1, ∆min = 0 và ∆maj = 0, các trọng số khởi tạo D1 trong phương pháp đề xuất trở về như của D1 trong AdaBoos 1 (đều bằng N ). Ngoài ra, để điều khiển mức độ điều chỉnh các giá trị ∆min và ∆maj theo các đặc điểm riêng của bộ dữ liệu, luận án đề xuất một công thức tổng quát hơn sử dụng tham số mũ θ như sau: (1−δ)θ ∆maj = N , (1−δ)θ (2.9) ∆min = δ×N . Đối với mỗi bộ dữ liệu cụ thể, chúng ta có thể tìm thấy giá trị tốt nhất của θ thông qua quá trình thử nghiệm trên một tập hợp các giá trị đã cho. Cải tiến này làm cho AdaBoost trở nên khái quát hơn trên các bộ dữ liệu có tỷ lệ không cân bằng khác nhau. 2.2.2. Phương pháp tính trọng số tin cậy của bộ phân lớp thành viên nhạy cảm với nhãn dương Xem xét dòng 5 của giải thuật AdaBoost, trọng số tin cậy αt của bộ phân lớp thành viên ht được tính bằng một hàm tỷ lệ nghịch với tổng lỗi εt trên các mẫu bị phân lớp sai. Đối với vấn đề phân lớp trên tập dữ liệu không cân bằng, thuật toán cần ưu tiên gán trọng số lỗi cao khi nó phân lớp sai nhiều mẫu nhãn dương. Vì thế luận án đề xuất phân tích tổng lỗi εt được tính theo hai thành phần tổng lỗi của các mẫu +1, được ký hiệu là ε+ và của các mẫu −1, được ký hiệu là bởi ε− , tức là: t t εt = ε− + ε+ , t t (2.10) trong đó N ε+ = t t i=1 ωi , yi ̸= ht (xi ), yi = +1 N (2.11) ε− t = t i=1 ωi , yi ̸= ht (xi ), yi = −1. Rõ ràng, ε∗ phụ thuộc vào ε+ và ε− , và nếu chúng ta muốn bộ phân lớp thành viên ht phân lớp chính t t t xác các mẫu nhãn dương, thì chúng ta cần tăng ε+ và do đó, luận án định nghĩa lại ε∗ như sau: t t ε∗ = ε− + γ ∗ ε+ , với γ > 1. t t t (2.12) 10
Vì 0 < ε− + ε+ < 1 nên luận án chọn γ = 2 − (ε− + ε+ ). Sau đó, trọng số tin cậy αt của bộ phân lớp t t t t thành viên ht trong AdaBoost bằng phương pháp được đề xuất trở thành: ∗ 1 1 − ε∗ αt = ln ∗ t . (2.13) 2 εt Ngoài ra, để hàm ln() trong Công thức (2.13) thỏa mãn điều kiện xác định, thì ε∗ phải thỏa mãn t 0 < ε∗ < 1. Với các điều kiện ràng buộc của hệ số γ như vậy, luận án đề xuất một giá trị hệ số γ như t sau: γ = 2 − (ε− + ε+ ). t t (2.14) Ta dễ dàng chứng minh hệ số γ được chọn thỏa mãn: γ > 1, 0 < ε∗ < 1, với ε∗ = ε− + γ ∗ ε+ . (2.15) t t t t Theo đó, tổng giá trị lỗi ε∗ trong Công thức (2.12) của mô hình tăng cùng với tổng lỗi ε+ của các t t ∗ mẫu nhãn dương, dẫn đến giá trị trọng số tin cậy αt được điều chỉnh giảm tương ứng. Điều này có nghĩa là đề xuất cải tiến đã thiết lập các tham số điều chỉnh sao cho các bộ phân lớp thành viên ht gây ra tổng lỗi ít hơn trên các mẫu nhãn dương, tức là ht cố gắng phân lớp chính xác nhiều nhất các mẫu mẫu nhãn dương. 2.2.3. Mô tả giải thuật Im.AdaBoost luận án gọi giải thuật kết hợp hai phương pháp đề xuất trong phần 2.2.1 và phần 2.2.2 là giải thuật Im.AdaBoost. Ngoài ra luận án cũng đề xuất sử dụng WSVM như là bộ phân lớp thành viên được gọi là Im.AdaBoost.WSVM. Thuật toán Im.AdaBoost.WSVM được trình bày trong Thuật toán 2.1. Cũng lưu ý rằng, ngoài WSVM chúng ta có thể lựa chọn kết hợp Im.AdaBoost với các giải thuật khác như DecisionTree, SVM, KNN,... làm bộ học phân lớp thành viên. Thuật toán 2.1: Thuật toán Im.AdaBoost.WSVM Input: Tập dữ liệu X = {(x1 , y1 ), . . . , (xN , yN )} có N mẫu; M : số bộ phân lớp thành viên; h1 : bộ phân lớp thành viên; C: tham số điều chỉnh WSVM. Output: H(x): Mô hình phân lớp tổng hợp. 1 1 1 Khởi tạo zi = 1 và ωi (i = 1, 2, . . . , N ) sử dụng Công thức (2.8) và (2.9) ; 2 for t = 1 to M do 3 huấn luyện bộ phân lớp ht ← sử dụng WSVM(X) và tập trọng số lỗi Dt và zi ∗ ωi (i = 1, 2, . . . , N ); t t t+1 4 tính lại zi 5 tính tổng lỗi gây ra bởi ht : ε∗ (sử dụng Công thức (2.12)); t ∗ 6 tính trọng số tin cậy của ht : αt (sử dụng Công thức (2.13)); t+1 ωi e−αt yi ht (xi ) t N t+1 7 cập nhật trọng số lỗi ωi = Lt , trong đó Lt là hệ số chuẩn hóa sao cho i=1 ωi = 1; M ∗ 8 return H(x) = sign( t=1 αt ht (x)). 2.3. Thử nghiệm Trong phần này, luận án sẽ trình bày chi tiết hai nhóm thử nghiệm trên dữ liệu không cân bằng, nhằm mục đích đánh giá hiệu quả của phương pháp đề xuất Im.AdaBoost với các phương pháp phân lớp phổ biến như Cây quyết định, SVM, CNN, WSVM, AdaBoost.DecisionTree, AdaBoost.SVM, Ad- aBoost.WSVM; các giải thuật kết hợp Im.AdaBoost.WSVM, Im.AdaBoost.DecisionTree (Im.AdaBoost.DT) và Im.AdaBoost.SVM. Hai nhóm thử nghiệm bao gồm: 1. Thử nghiệm trên các bộ dữ liệu UCI: thực hiện trên 4 bộ dữ liệu có tỉ lệ không cân bằng khác nhau gồm: Transfusion, Ecoli, Yeast và Abalone. 2. Thử nghiệm trên bộ dữ liệu đồng tác giả: thực hiện trên các bộ dữ liệu đồng tác giả tự thu thập và xây dựng cho bài toán dự đoán đồng tác giả. Mô tả chi tiết về các bộ dữ liệu đồng tác giả được trình bày ở Bảng 2.2. 11
Bảng 2.1: Các giá trị tốt nhất của tham số θ cho thuật toán Im.AdaBoost.DecisionTree, Im.AdaBoost.SVM và Im.AdaBoost.WSVM Transfusion Ecoli Yeast Abalone TT Thuật toán 31.23% 29.73% 3.56% 2.53% 1 Im.AdaBoost.DT 1.1 1.7 1.7 1.1 2 Im.AdaBoost.SVM 0.2 0.2 0.2 0.2 3 Im.AdaBoost.WSVM 1.7 1.7 2.0 0.8 2.3.1. Thử nghiệm trên các bộ dữ liệu UCI Trong phần này, luận án mô tả việc thực hiện 2 thử nghiệm với các mục đích như sau: 1. Thử nghiệm UCI-1: xác định giá trị các tham số θ của Im.AdaBoost phù hợp nhất cho các thuật toán Im.AdaBoost.DecisionTree, Im.AdaBoost.SVM và Im.AdaBoost.WSVM thông qua việc khảo sát trên các tập dữ liệu. 2. Thử nghiệm UCI-2: đánh giá so sánh hiệu suất của giải thuật đề xuất Im.AdaBoost.WSVM với các thuật toán phân lớp CNN, Cây quyết định, SVM, WSVM, AdaBoost.DecisionTree, Ad- aBoost.SVM, AdaBoost.WSVM, Im.AdaBoost.DT, Im.AdaBoost.SVM trên các tập dữ liệu Trans- fusion, Ecoli, Yeast và Abalone. Thử nghiệm UCI-1 Chúng tôi đã chạy thử nghiệm để tìm ra các giá trị tham số θ tốt nhất cho Im.AdaBoost.DT, Im.AdaBoost.SVM và Im.AdaBoost.WSVM trên các tập dữ liệu bằng cách khảo sát các giá trị của tham số θ ∈ {0.2, 0.5, 0.8, 1.1, 1.4, 1.7, 2.0}. Đối với mỗi giá trị θ, luận án xem xét các giá trị của Gmean từ đó xác định giá trị tốt nhất của θ trong từng thuật toán sao cho Gmean là tối đa. Lưu ý rằng nếu có nhiều hơn một giá trị của θ mà Gmean là tối đa, thì ta lựa chọn lấy một giá trị θ bất kỳ trong số đó. Bảng 2.1 trình bày các giá trị tốt nhất của tham số θ cho các thuật toán Im.AdaBoost.DT, Im.AdaBoost.SVM và Im.AdaBoost.WSVM chạy trên 4 tập dữ liệu UCI. Rõ ràng, khi mỗi tập dữ liệu được tạo với tỷ lệ phần trăm mẫu dương +1 khác nhau, giá trị của θ cũng khác nhau. Thử nghiệm UCI-2 Kết quả thử nghiệm 2 chỉ ra rằng giải thuật đề xuất Im.AdaBoost.WSVM đều đạt kết quả tốt hơn các giải thuật còn lại ở các độ đo quan trọng là SE, Gmean và AUC trên cả bốn bộ dữ liệu. Đặc biệt là ở hai bộ dữ liệu có độ không cân bằng cao Yeast và Abalone, trong khi hầu hết các giải thuật khác đều không phân loại đúng bất kỳ nhãn dương nào thì giải thuật đề xuất Im.AdaBoost.WSVM luôn cho kết quả phân loại chấp nhận được ở các độ đo quan trọng. Như vậy, có thể khẳng định sự vượt trội của giải thuật đề xuất Im.AdaBoost.WSVM so với các giải thuật còn lại trên các bộ dữ liệu UCI. 2.3.2. Thử nghiệm cho bài toán dự đoán đồng tác giả Trong thử nghiệm này, luận án sử dụng thông tin từ các tạp chí từ năm 2010 đến năm 2014 để tính toán độ đo liên kết giữa các cặp tác giả và xây dựng một bảng dữ liệu về các ứng cử viên đồng tác giả. Còn thông tin từ các tạp chí từ năm 2015 đến năm 2017 để xác định nhãn của các mẫu dữ liệu. Để đánh giá tổng quát hiệu suất của thuật toán, luận án đã sử dụng kỹ thuật bootstrap trên tập dữ liệu đồng tác giả để tạo 21 tập dữ liệu con, trong đó các tập dữ liệu phụ được chia thành ba nhóm có kích thước nhỏ (Nhóm I), trung bình (Nhóm II) và lớn (Nhóm III). Mô tả chi tiết các bộ dữ liệu được trình bày trong Bảng 2.2. Với mỗi bộ dữ liệu, luận án mô tả việc thực hiện bốn thử nghiệm với các mục đích sau: 1. Thử nghiệm ĐTG-1: xác định giá trị các tham số θ của Im.AdaBoost phù hợp nhất cho các thuật toán Im.AdaBoost.DecisionTree, Im.AdaBoost.SVM và Im.AdaBoost.WSVM thông qua việc khảo sát trên các tập dữ liệu. 12
Bảng 2.2: Mô tả các bộ dữ liệu đồng tác giả Bộ dữ liệu Số mẫu Mẫu nhãn Mẫu nhãn % mẫu nhãn dương âm dương (Trung bình số mẫu = 1607) Co-Author 1 1800 360 1440 20% Co-Author 2 1710 270 1440 15% Nhóm I Co-Author 3 1620 180 1440 10% Co-Author 4 1584 144 1440 8% Co-Author 5 1548 108 1440 6% Co-Author 6 1512 72 1440 4% Co-Author 7 1476 36 1440 2% (Trung bình số mẫu = 2678) Co-Author 8 3000 600 2400 20% Co-Author 9 2850 450 2400 15% Nhóm II Co-Author 10 2700 300 2400 10% Co-Author 11 2640 240 2400 8% Co-Author 12 2580 180 2400 6% Co-Author 13 2520 120 2400 4% Co-Author 14 2460 60 2400 2% (Trung bình số mẫu = 4478) Co-Author 15 4800 600 4200 20% Co-Author 16 4650 450 4200 15% Nhóm III Co-Author 17 4500 300 4200 10% Co-Author 18 4440 240 4200 8% Co-Author 19 4380 180 4200 6% Co-Author 20 4320 120 4200 4% Co-Author 21 4260 60 4200 2% 2. Thử nghiệm ĐTG-2: đánh giá so sánh hiệu suất của giải thuật đề xuất Im.AdaBoost.WSVM với các thuật toán phân lớp CNN, Cây quyết định, SVM, WSVM, AdaBoost.DecisionTree, Ad- aBoost.SVM, AdaBoost.WSVM, Im.AdaBoost.DecisionTree, Im.AdaBoost.SVM trên các tập dữ liệu có kích thước nhỏ trong Nhóm I. 3. Thử nghiệm ĐTG-3: đánh giá so sánh hiệu suất của giải thuật đề xuất Im.AdaBoost.WSVM với các thuật toán phân lớp CNN, Cây quyết định, SVM, WSVM, AdaBoost.DecisionTree, Ad- aBoost.SVM, AdaBoost.WSVM, Im.AdaBoost.DecisionTree, Im.AdaBoost.SVM trên các tập dữ liệu có kích thước vừa trong Nhóm II. 4. Thử nghiệm ĐTG-4: đánh giá so sánh hiệu suất của giải thuật đề xuất Im.AdaBoost.WSVM với các thuật toán phân lớp CNN, Cây quyết định, SVM, WSVM, AdaBoost.DecisionTree, Ad- aBoost.SVM, AdaBoost.WSVM, Im.AdaBoost.DecisionTree, Im.AdaBoost.SVM trên các tập dữ liệu có kích thước lớn hơn trong Nhóm III. Thử nghiệm ĐTG-1 Trong thử nghiệm này, chúng tôi đã chạy thử nghiệm để tìm ra các giá trị tham số tốt nhất cho Im.AdaBoost.DecisionTree, Im.AdaBoost.SVM và Im.AdaBoost.WSVM trên các tập dữ liệu đã tạo bằng cách khảo sát các giá trị của tham số θ ∈ {0.2, 0.5, 0.8, 1.1, 1.4, 1.7, 2.0}. Đối với mỗi giá trị θ, luận án xem xét các giá trị của Gmean từ đó xác định giá trị tốt nhất của θ trong từng thuật toán sao cho Gmean là tối đa. Bảng 2.3 trình bày các giá trị tốt nhất của tham số θ cho các thuật toán Im.AdaBoost.DecisionTree (Im.AdaBoost.DT), Im.AdaBoost.SVM và Im.AdaBoost.WSVM chạy trên 21 tập dữ liệu. Rõ ràng, khi mỗi tập dữ liệu được tạo với tỷ lệ phần trăm mẫu dương +1 khác nhau, giá trị của θ cũng khác nhau. 13
Bảng 2.3: Các giá trị tốt nhất của tham số θ cho thuật toán Im.AdaBoost.DecisionTree, Im.AdaBoost.SVM và Im.AdaBoost.WSVM trên các bộ dữ liệu Co-Author Group I Group II Group III ID Algorithms (Co-Author 1 − Co-Author 7) (Co-Author 8 − Co-Author 14) (Co-Author 15 − Co-Author 21) 20% 15% 10% 8% 6% 4% 2% 20% 15% 10% 8% 6% 4% 2% 20% 15% 10% 8% 6% 4% 2% 1 Im.AdaBoost.DecisionTree 1.7 1.1 1.4 0.5 1.4 2 1.1 1.7 2.0 0.2 1.1 0.8 1.4 1.4 2.0 1.4 1.4 0.2 2.0 2.0 1.7 2 Im.AdaBoost.SVM 1.7 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 1.7 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 3 Im.AdaBoost.WSVM 1.4 1.7 2.0 2.0 2.0 0.8 1.7 1.7 1.4 1.7 1.7 2.0 1.1 0.8 1.7 1.7 2.0 2.0 1.1 2.0 2.0 Thử nghiệm ĐTG-2 Trong thử nghiệm này, luận án đã so sánh hiệu suất của Im.AdaBoost.WSVM với hiệu suất của các thuật toán phân lớp được đề cập ở trên trên các tập dữ liệu có kích thước nhỏ trong Nhóm I. Theo đó, chúng ta có thể đưa ra một số quan sát chính dựa trên các giá trị của Gmean, SE , SP và AU C như sau. • Khi tỷ lệ phần trăm mẫu dương +1 trong tập dữ liệu giảm từ 20% xuống 2%, nghĩa là tỷ lệ không cân bằng của mẫu dương +1 tăng lên, chỉ Im.AdaBoost.DecisionTree và Im.AdaBoost.WSVM tìm thấy mức tối đa giá trị của Gmean và AU C . Tuy nhiên, trong ba trường hợp Im.AdaBoost.DecisionTree tìm thấy giá trị tối đa của Gmean, Im.AdaBoost.WSVM tìm thấy giá trị SE cao hơn Im.AdaBoost.DecisionTree, nghĩa là Im.AdaBoost.W- SVM phân lớp các mẫu dương +1 chính xác hơn Im.AdaBoost.DecisionTree. • Khi phần trăm mẫu dương +1 trong tập dữ liệu là 10%, 8%, 6% hoặc 2%, Im.AdaBoost.SVM tìm thấy 100% của SE , 0% của Gmean và 50% của AU C , nghĩa là nó phân lớp chính xác tất cả các mẫu dương +1, trong khi phân lớp sai tất cả các mẫu âm −1. Trong các trường hợp này, Im.AdaBoost.WSVM tốt hơn Im.AdaBoost.SVM trong việc phân lớp cả mẫu dương +1 và mẫu âm −1. • Khi tỷ lệ mẫu dương +1 thấp (e.g., 2%), i.e., tỷ lệ không cân bằng giữa mẫu dương +1 và âm −1 cao, tất cả SVM, CNN, WSVM, Thuật toán AdaBoost.DecisionTree và AdaBoost.WSVM đã phân lớp sai tất cả các mẫu dương +1 vì SE = 0, trong khi Im.AdaBoost.SVM phân lớp sai tất cả các mẫu âm −1 vì SP = 0. Chỉ có ba thuật toán bao gồm Cây quyết định, Im.AdaBoost.DecisionTree và Im.AdaBoost.WSVM có thể phân lớp cả mẫu âm −1 và mẫu dương +1. Tuy nhiên, trong số các thuật toán này, Im.AdaBoost.WSVM là thuật toán tốt nhất để phân lớp chính xác các mẫu dương +1 vì nó cho giá trị SE cao nhất so với Cây quyết định và Im.AdaBoost.DecisionTree. Trong số các thuật toán này, luận án thấy rằng Im.AdaBoost.DecisionTree và Im.AdaBoost.WSVM vượt trội hơn các thuật toán khác trong việc phân lớp mẫu dương +1 và âm −1. Tuy nhiên, vì Im.AdaBoost.WSVM tìm thấy giá trị SE cao hơn Im.AdaBoost.DecisionTree, cho thấy rằng Im.AdaBoost.WSVM đã phân lớp các mẫu dương +1 chính xác hơn Im.AdaBoost.DecisionTree. Thử nghiệm ĐTG-3 Từ kết quả thử nghiệm các giải thuật trên bộ dữ liệu nhóm II, có thể rút ra một số kết luận như sau: • Im.AdaBoost.WSVM không chỉ tìm thấy giá trị tối đa của Gmean và AU C , mà còn tìm thấy giá trị tối đa của SE cho cả bảy tập dữ liệu, nghĩa là nó phân lớp các mẫu dương +1 tốt hơn các thuật toán khác. • Nhìn chung, chúng ta thấy rằng khi tỷ lệ phần trăm mẫu dương +1 trong tập dữ liệu giảm từ 20% xuống 2%, Im đã tìm thấy độ lệch của các giá trị Gmean, AU C và SE . AdaBoost.WSVM so với các giá trị tốt nhất của Gmean, AU C và SE được tìm thấy bởi các thuật toán còn lại sẽ tăng lên. • Khi chúng ta áp dụng các bộ phân lớp thành viên bao gồm Cây quyết định, SVM và WSVM cho Im.AdaBoost tạo thành các giải thuật Im.AdaBoost.DecisionTree, Im.AdaBoost.SVM và Im.AdaBoost.WSVM, các giải thuật này đều cho giá trị Gmean, AU C và SE cao hợn tương ứng so với AdaBoost.DecisionTree, AdaBoost.SVM và AdaBoost.WSVM trên toàn bộ 7 tập dữ liệu. Điều này cho thấy Im.AdaBoost đã cải thiện đáng kể khả năng phân biệt giữa mẫu dương +1 và âm −1 so với AdaBoost ban đầu. 14
Ngoài ra, khi tỷ lệ phần trăm mẫu dương +1 trong tập dữ liệu giảm từ 20% xuống 2%, Im.AdaBoost.WSVM đạt được giá trị Gmean giảm từ 91.58% xuống 87.99%, SE tăng từ 94.67% lên 100% và SP giảm từ 88.60% xuống 77.53%. Điều này có nghĩa là các giá trị của Gmean, SE và SP do Im.AdaBoost.WSVM tìm thấy thay đổi không đáng kể ngay cả khi tỷ lệ phần trăm mẫu dương +1 giảm đáng kể. Nói cách khác, Im.AdaBoost.WSVM có hiệu quả trong việc phân lớp mẫu trong các bộ dữ liệu có mức độ không cân bằng cao trong Nhóm II. Thử nghiệm ĐTG-4 Thử nghiệm các giải thuật trên các bộ dữ liệu trong Nhóm III (có số lượng mẫu lớn hơn nhiều so với dữ liệu Nhóm I và Nhóm II). Dựa vào kết quả thử nghiệm có thể rút ra một số nhận xét như sau: • Im.AdaBoost.WSVM tìm thấy giá trị tối đa của Gmean và AU C cho cả 7 tập dữ liệu và giá trị tối đa SE cho 6 tập dữ liệu. Tuy nhiên, khi tỷ lệ phần trăm mẫu dương +1 trong tập dữ liệu là 2%, Im.AdaBoost.SVM đã tìm thấy 100% của SE và 0% của SP , nghĩa là Im.AdaBoost.SVM đã phân lớp sai tất cả mẫu −1 thành mẫu +1. Do đó, Im.AdaBoost.WSVM hoạt động tốt hơn các thuật toán được so sánh trong việc phân lớp chính xác các mẫu dương +1 trong bộ dữ liệu. • Nhìn chung, khi tỷ lệ phần trăm mẫu dương +1 giảm, độ lệch của các giá trị Gmean, AU C và SE do Im.AdaBoost.WSVM tìm thấy so với các giá trị cao nhất của Gmean và SE được tìm thấy bởi các thuật toán khác sẽ tăng lên. Điều này có nghĩa là Im.AdaBoost.WSVM hiệu quả hơn các thuật toán khác khi tỷ lệ không cân bằng tăng lên. • Như trong kết quả của Thử nghiệm 2, chúng ta thấy rằng khi áp dụng các bộ phân lớp thành viên bao gồm Cây quyết định, SVM và WSVM cho Im.AdaBoost, Im.AdaBoost.DecisionTree, Im.AdaBoost.SVM và Im.AdaBoost.WSVM cho giá trị tương ứng của Gmean, AU C và SE cao hơn so với AdaBoost.DecisionTree, AdaBoost.SVM và AdaBoost.WSVM cho cả bảy tập dữ liệu. Điều này một lần nữa cho thấy Im.AdaBoost có ý nghĩa quan trọng vượt trội hơn AdaBoost ban đầu ở khả năng phân biệt giữa mẫu dương +1 và âm −1. Tóm lại, kết quả của ba thử nghiệm trên cho thấy Im.AdaBoost.WSVM vượt trội hơn các thuật toán được so sánh khi tỷ lệ không cân bằng giữa mẫu dương và mẫu âm tăng lên. Khi số lượng mẫu dữ liệu trong tập dữ liệu nhiều, Im.AdaBoost.WSVM càng thể hiện rõ ràng hơn trong việc phân lớp chính xác các mẫu dương +1 trong tập dữ liệu. 2.4. Kết luận chương 2 Trong Chương 2 luận án đề xuất một giải thuật có tên là Im.AdaBoost cho dữ liệu không cân bằng với hai cải tiến dựa trên AdaBoost. Cụ thể, luận án đã đề xuất hai cải tiến cho AdaBoost là: (i) khởi tạo tập các trọng số lỗi khác nhau thích nghi với tỷ lệ không cân bằng của tập dữ liệu, trong đó sử dụng các tham số điều chỉnh θ; (ii) tính toán trọng số độ tin cậy của các bộ phân lớp thành viên dựa trên độ nhạy đối với tổng lỗi gây ra trên các mẫu nhãn dương. Cụ thể hơn, nếu bộ phân lớp thành viên phân lớp sai mẫu dương nhiều hơn thì trọng số tin cậy của bộ phân lớp sẽ giảm xuống. Chúng tôi cũng sử dụng thuật toán WSVM như là bộ phân lớp thành viên trong Im.AdaBoost.WSVM để phân lớp các tập dữ liệu không cân bằng. Các thử nghiệm trên các bộ dữ liệu UCI và dữ liệu đồng tác giả tự xây dựng với các kích thước và tỷ lệ không cân bằng khác nhau cho thấy thuật toán Im.AdaBoost.WSVM hiệu quả đối với vấn đề phân lớp dữ liệu không cân bằng nói chung và bài toán dự đoán đồng tác giả khi được mô hình hóa theo dạng bài toán phân lớp nói riêng. Kết quả nghiên cứu của chương này đã được công bố trong 2 bài báo [CT.1] và [CT.3] trong danh mục các công trình đã công bố của luận án. 15
Chương 3 ĐỀ XUẤT THUẬT TOÁN ĐIỀU CHỈNH THÍCH NGHI TRỌNG SỐ MỜ DỰA TRÊN FUZZY SVM-CIL Trong chương này luận án đề xuất một thuật toán điều chỉnh trọng số mờ thích nghi dựa trên Fuzzy SVM-CIL gọi là AFW-CIL cho bài toán dự đoán đồng tác giả theo dạng học trên dữ liệu không cân bằng hai lớp. Cụ thể, thuật toán AFW-CIL được xây dựng dựa trên hai đề xuất mới gồm: (i) xây dựng một hàm thuộc mờ mới cho các mẫu dữ liệu dựa trên khoảng cách từ mỗi mẫu đến tâm của cả lớp thiểu số và lớp đa số, và (ii) phương pháp điều chỉnh thích nghi trọng số mờ của các mẫu trong vùng không gian nhạy cảm được định vị dựa trên các cặp Tomek link trong không gian lề phân lớp SVM hoặc mẫu là nhiễu. Bằng cách đó, thuật toán làm tăng ảnh hưởng của các mẫu thiểu số và giảm ảnh hưởng của các mẫu đa số trong việc huấn luyện mô hình phân lớp. Các thử nghiệm được thực hiện trên các bộ dữ liệu chuẩn của UCI và các bộ dữ liệu bảng ứng viên đồng tác giả tự xây dựng với nhiều kích thước và tỷ lệ không cân bằng khác nhau để đánh giá hiệu suất phân lớp của thuật toán đề xuất khi so sánh trực tiếp với thuật toán Fuzzy SVM-CIL. 3.1. Đặt vấn đề Lin và các cộng sự đã đề xuất một thuật toán Fuzzy SVM, trong đó họ sử dụng một trọng số mờ cho từng mẫu để đưa vào SVM. Batuwita và các cộng sự đã đề xuất một thuật toán Fuzzy SVM-CIL dựa trên thuật toán Fuzzy SVM để cải thiện hiệu quả phân lớp cho các tập dữ liệu không cân bằng. Fuzzy SVM-CIL sử dụng các hàm thuộc mờ để ưu tiên gán các giá trị trọng số lớn hơn cho các mẫu thiểu số và các giá trị nhỏ hơn cho các mẫu đa số. Các hàm thuộc mờ được tính toán dựa trên khoảng cách được đo bằng các công thức 1.4–1.9. Sau đây, chúng tôi gọi Fuzzy SVM là FSVM, Weighted-SVM là WSVM và Fuzzy SVM-CIL là FSVM-CIL. luận án thấy rằng trong các công thức (1.4, 1.5) Fuzzy SVM-CIL, các hàm thuộc mờ chỉ xem xét khoảng cách từ các mẫu đến tâm lớp của chúng mà không xét đến tâm của lớp kia. Do đó, Fuzzy SVM-CIL không hiệu quả đối với trường hợp các mẫu có cùng khoảng cách đến tâm lớp của chúng trong khi có khoảng cách khác nhau đến tâm lớp đối lập. Bên cạnh đó, Tomek Links và KNN là hai thuật toán cho phép định vị các mẫu dữ liệu trong không gian phân bố mẫu. Kết hợp với biên lề phân lớp SVM, luận án gán và điều chỉnh trọng số cho từng mẫu để chỉ ra tầm quan trọng của mẫu đối với việc xây dựng mô hình phân lớp. Cụ thể, nếu một mẫu trong một cặp Tomek link (TLP) bị nhiễu, thì sẽ giảm rất mạnh trọng số của nó, nếu một cặp trong TLP nằm trên một ranh giới phân lớp, thì sẽ tăng trọng số của mẫu thiểu số và giảm trọng số của mẫu đa số. Từ đó luận án đề xuất một hàm thuộc mờ mới để xác định trọng số mờ cho mẫu và một phương pháp điều chỉnh thích nghi giá trị trọng số mờ thích nghi cho bài toán học trên dữ liệu không cân bằng dựa trên vị trí của các mẫu trong vùng nhạy cảm (như biên lề, mẫu nhiễu) được xác định bởi TLPs. 3.2. Đề xuất thuật toán trọng số mờ thích nghi 3.2.1. Đề xuất hàm thuộc mờ giàu ngữ nghĩa cho Fuzzy SVM Trong FSVM-CIL, hàm thuộc mờ được tính toán dựa trên khoảng cách từ mẫu đến trung tâm lớp của nó theo các công thức (1.4, 1.5) chỉ ra các mẫu gần trung tâm của lớp được coi là có ảnh hưởng cao hơn và do đó, chúng có giá trị trọng số mờ cao hơn. Ngược lại, các mẫu ở xa trung tâm lớp của chúng có giá trị trọng số mờ thấp hơn. Chúng tôi nhận thấy rằng việc này khá đơn giản và không đầy đủ. Với một ví dụ, giả sử rằng C + và C − là tâm của hai tập mẫu được gán nhãn +1 và −1 tương ứng và xp , xq và xt là các mẫu được gán nhãn +1 có khoảng cách bằng nhau R đến tâm C + , có nghĩa rằng d(xp , C + ) = d(xq , C + ) = d(xt , C + ) = R. Các giá trị trọng số mờ m+ , m+ và m+ của xp , xq và xt được tính toán bởi các hàm thuộc mờ f (xp ), p q t f (xq ), và f (xt ) được đưa ra ở Công thức (1.3), trong đó f (xp ) = f (xq ) = f (xt ) do r+ = 1. Điều này có nghĩa rằng ba mẫu xp , xq , xt đều quan trọng như nhau trong việc góp phần hình thành mô hình phân lớp. Tuy nhiên, chúng tôi thấy rằng vị trí của ba mẫu này đến trung tâm C − của lớp đối diện rõ ràng là khác nhau: d(xp , C − ) > d(xq , C − ) > d(xt , C − ). Xét về mặt ý nghĩa, xt có thể là một mẫu nhạy cảm, 16
bởi vì nó gần trung tâm nhất C − . Mức độ ảnh hưởng trên một mô hình phân lớp của xp phải lớn hơn xq và của xq phải lớn hơn so với xt , tức là m+ > m+ > m+ . Vì vậy, luận án đề xuất một hàm thuộc p q t mờ mới dựa trên việc xem xét khoảng cách từ các mẫu đến trung tâm của hai lớp. Cụ thể, nếu xi là một mẫu dữ liệu, thì hàm thuộc mờ cho các mẫu xi được định nghĩa bởi: cen_opp cen_2c dxi flin (xi ) = cen_own cen_opp , (3.1) dxi + dcen_own + ∆ cen_opp cen_own trong đó dxi là khoảng cách từ xi đến tâm lớp đối diện, dxi là khoảng cách từ xi đến tâm cen_opp lớp của nó, dcen_own là khoảng cách giữa tâm hai lớp và ∆ là một số dương nhỏ. Thuật toán 3.1: AdjFW: Điều chỉnh trọng số mờ dựa trên TLPs Input : D, ht , K, σ1 , σ2 , σ3 , σ4 , m+ , m− , tập chứa các cặp Tomek link T LP s = {} i i Output: {m+ , m− }, i = 1, 2, · · · , N . i i 1 for i = 1 to N do 2 tìm mẫu hàng xóm gần nhất (xj , yj ) của (xi , yi ); 3 if (xi , yi ) cũng là hàng xóm gần nhất của (xj , yj ) then 4 if (xi , xj ) ∈ T LP s và (yi ̸= yj ) then / 5 T LP s = T LP s ∪ {(xi , xj )}; 6 for với mỗi (xi , xj ) ∈ T LP s thỏa mãn yi = 1 và yj = −1 do 7 if ht (xi ) = 1 và ht (xj ) = 1 then 8 m+ = m+ × (1 + σ1 ); i i 9 m− = m− × (1 − σ1 ); j j 10 if hKNN (xjk ) = 1 then 11 m− = m− × σ2 ; j j 12 if ht (xi ) = −1 và ht (xj ) = −1 then 13 m+ = m+ × (1 + σ3 ); i i 14 m− = m− × (1 − σ3 ); j j 15 if hKNN (xik ) = −1 then 16 m+ = m+ × σ4 ; i i 17 return {m+ , m− }, i = 1, 2, · · · , N ; i i Cho tập dữ liệu D = {(x1 , y1 ), . . . , (xN , yN )} of N mẫu, trong đó yi ∈ {−1, +1}, ∀i = 1, 2, · · · , N , chúng tôi đặt r+ = 1 và biểu diễn r− bởi tỷ lệ không cân bằng của số lượng mẫu thiểu số so với số lượng mẫu đa số. Thuật toán của chúng tôi để tìm các giá trị trọng số mờ m+ và m− cho xi ∈ D được i i cen_2c biểu diễn trong Thuật toán 3.1. Tại mỗi lần lặp, thuật toán tính hàm thuộc mờ flin cho mỗi mẫu xi bằng Công thức (3.1) với ∆ = 10(−6) . Nếu mẫu hiện tại xi thuộc về lớp thiểu số, tức là yi = +1, thì m+ là giá trị độ thuộc mờ của xi vì r+ = 1. Ngược lại, m− được giảm bởi r− . Sau đó qua N vòng lặp, i i thuật toán trả về một tập hợp các giá trị trọng số mờ {m+ , m− } cho các mẫu xi ∈ D, (i = 1, 2, . . . , N ). i i 3.2.2. Phương pháp điều chỉnh trọng số mẫu trong vùng không gian nhạy cảm dựa trên KNN và Tomek link luận án đề xuất một giải pháp sử dụng thuật toán Tomek Links kết hợp KNN và SVM để xác định các mẫu trong vùng không gian nhạy cảm và thiết kế bốn quy tắc điều chỉnh trọng số mờ để kiểm soát tác động của chúng đối với việc huấn luyện mô hình phân lớp. Trong đó ưu tiên tầm quan trọng của các mẫu dương, giảm tầm quan trọng của các mẫu âm và giảm đáng kể ảnh hưởng của các mẫu nhiễu. Hình 3.2 minh họa 4 trường hợp trong đó các mẫu trong vùng không gian nhạy cảm được xác định dựa trên vị trí tương đối của các TLP cùng với K -hàng xóm gần nhất của chúng, với K = 4. Các biểu tượng “ +” và “ −” đại diện cho các mẫu lớp dương và âm tương ứng. Một cặp TLP có thể rơi vào một trong bốn trường hợp: (1) trong lề dương, (2) ngoài lề dương nhưng được phân lớp là nhiễu âm, (3) trong lề âm hoặc (4) bên ngoài lề âm nhưng được phân lớp là nhiễu dương. Phương pháp điều chỉnh trọng số mờ được trình bày trong Thuật toán 3.2, trong đó ht là một bộ phân lớp WSVM, hKNN là một bộ phân lớp KNN, K là số lượng hàng xóm gần nhất cho một mẫu nhất định xi , và tập các tham số {σ1 , σ2 , σ3 , σ4 } được sử dụng để điều chỉnh các trọng số mờ. Thuật toán hoạt động như sau: Đầu 17
1 4 2 3 Hình 3.2: Một minh họa về bốn trường hợp cho các mẫu nhạy cảm được tìm thấy bởi TLPs tiên, nó xác định một tập các cặp TLP {(xi , xj )} (các dòng 3-10). Sau đó, đối với mỗi cặp (xi , xj ) ∈ TLPs thỏa mãn điều kiện yi = 1 và yj = −1, thuật toán kiểm tra và điều chỉnh trọng số mờ dựa trên 4 trường hợp được minh họa trong Hình 3.2: 1. Nếu ht phân lớp cả xi và xj vào lớp dương, nghĩa là ht (xi ) = 1 và ht (xj ) = 1, tức là cặp (xi , xj ) nằm trong lề dương (trường hợp 1) thì: trọng số mờ m+ được điều chỉnh tăng bởi σ1 để tăng ảnh i hưởng của xi , trong khi trọng số mờ m− được điều chỉnh giảm bởi σ1 để giảm ảnh hưởng của xj j (các dòng 13-14). Tuy nhiên, nếu K -hàng xóm gần nhất xjk (jk = 1, 2, · · · , K) của xj thuộc về lớp dương, nghĩa là xj là nhiễu âm (trường hợp 2), thì điều chỉnh giảm mạnh m− bởi σ2 (các dòng j 15-17). Vì vậy, điều kiện σ1 và σ2 được chọn sao cho 0 < σ1 < 0.5 và 0 < σ2 < 1. 2. Nếu ht phân lớp cả xi và xj vào lớp âm, nghĩa là ht (xi ) = −1 và ht (xj ) = −1, tức là cặp (xi , xj ) nằm trong lề âm (trường hợp 3), thì: trọng số mờ m+ được điều chỉnh tăng bởi σ3 để tăng ảnh i hưởng của xi , trong khi trọng số mờ m− được điều chỉnh giảm bởi σ3 để giảm ảnh hưởng của xj j (các dòng 20-21). Tuy nhiên, nếu K -hàng xóm gần nhất xik (ik = 1, 2, · · · , K) của xi thuộc về lớp âm, nghĩa là xi là nhiễu dương (trường hợp 4), thì điều chỉnh giảm mạnh m+ bởi σ4 (các dòng i 22-24). Vì vậy, điều kiện σ3 và σ4 được chọn sao cho 0 < σ3 < 0.5 và 0 < σ4 < 1. Thuật toán 3.2: AdjFW: Điều chỉnh trọng số mờ dựa trên TLPs Input : D, ht , K, σ1 , σ2 , σ3 , σ4 , m+ , m− , tập chứa các cặp Tomek link T LP s = {} i i Output: {m+ , m− }, i = 1, 2, · · · , N . i i 1 for i = 1 to N do 2 tìm mẫu hàng xóm gần nhất (xj , yj ) của (xi , yi ); 3 if (xi , yi ) cũng là hàng xóm gần nhất của (xj , yj ) then 4 if (xi , xj ) ∈ T LP s và (yi ̸= yj ) then / 5 T LP s = T LP s ∪ {(xi , xj )}; 6 for với mỗi (xi , xj ) ∈ T LP s thỏa mãn yi = 1 và yj = −1 do 7 if ht (xi ) = 1 và ht (xj ) = 1 then 8 m+ = m+ × (1 + σ1 ); i i 9 m− = m− × (1 − σ1 ); j j 10 if hKNN (xjk ) = 1 then 11 m− = m− × σ2 ; j j 12 if ht (xi ) = −1 và ht (xj ) = −1 then 13 m+ = m+ × (1 + σ3 ); i i 14 m− = m− × (1 − σ3 ); j j 15 if hKNN (xik ) = −1 then 16 m+ = m+ × σ4 ; i i 17 return {m+ , m− }, i = 1, 2, · · · , N ; i i 18