- THUẬT TOÁN GIA TĂNG LỌC - ĐÓNG GÓI. - TÌM TẬP RÚT GỌN TRONG BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ KHI TẬP ĐỐI TƯỢNG VÀ TẬP THUỘC TÍNH THAY ĐỔI GIÁ TRỊ. - Việc xây dựng các thuật toán gia tăng hiệu quả theo phương pháp tiếp cận lọc - đóng gói nhằm giảm thiểu số thuộc tính tập rút gọn, từ đó nâng cao hiệu quả các mô hình phân lớp, học máy là vấn đề nghiên cứu rất cần thiết. - Trong bài báo này, chúng tôi đề xuất hai thuật toán gia tăng lọc - đóng gói tìm tập rút gọn của bảng quyết định không đầy đủ thay đổi sử dụng khoảng cách: thuật toán IFWA_U_Obj trong trường hợp tập đối tượng thay đổi giá trị và thuật toán IFWA_U_Attr trong trường hợp tập thuộc tính thay đổi giá trị. - Kết quả thực nghiệm trên các tập dữ liệu mẫu cho thấy, các thuật toán gia tăng lọc - đóng gói đề xuất hiệu quả hơn về số lượng thuộc tính tập rút gọn và độ chính xác phân lớp so với các thuật toán lọc đã công bố.. - Bảng quyết định không đầy đủ Rút gọn thuộc tính. - Tập rút gọn Thuật toán gia tăng Lọc - Đóng gói. - Bài toán tìm tập rút gọn trên bảng quyết định không đầy đủ thay đổi ngày càng trở nên quan trọng, các nhà nghiên cứu đã đề xuất nhiều thuật toán gia tăng để giảm thời gian thực thi. - Chẳng hạn như lý thuyết tập thô do Pawlak [1] đề xuất được xem là công cụ hiệu quả giải quyết bài toán rút gọn thuộc tính trên bảng quyết định đầy đủ, đã và đang thu hút sự quan tâm của các nhà nghiên cứu trong suốt bốn thập kỷ qua. - Với dữ liệu cố định, các tác giả trong [3] đã xây dựng công thức tính khoảng cách, từ đó đề xuất thuật toán IDS_F_DAR tìm tập rút gọn sử dụng khoảng cách. - Thuật toán này theo tiếp cận lọc truyền thống, tập rút gọn chưa được tối ưu. - Để khắc phục nhược điểm này, các tác giả trong [4] đã đề xuất thuật toán IDS_FW_DAR theo hướng tiếp cận lai ghép lọc - đóng gói. - Trường hợp bảng quyết định thay đổi và có kích thước lớn, việc thực hiện thuật toán trên toàn bộ bảng quyết định sẽ gặp khó khăn về thời gian thực hiện. - Do đó, các nhà nghiên cứu đề xuất hướng tiếp cận tính toán gia tăng tìm tập rút gọn. - Các thuật toán gia tăng có khả năng giảm thiểu thời gian thực hiện và có khả năng thực hiện trên các bảng quyết định không đầy đủ kích thước lớn bằng giải pháp chia nhỏ bảng quyết định.. - Trong mấy năm gần đây, một số thuật toán gia tăng tìm tập rút gọn của bảng quyết định không đầy đủ đã được đề xuất bởi các nhóm nghiên cứu với các trường hợp: bổ sung và loại bỏ tập đối tượng [5]-[9], bổ sung và loại bỏ tập thuộc tính [10], tập đối tượng và tập thuộc tính thay đổi giá trị [11], [12]. - Các tác giả trong [11] xây dựng công thức cập nhật miền dương trong trường hợp tập đối tượng thay đổi giá trị, trên cơ sở đó đề xuất thuật toán gia tăng FSMV cập nhật tập rút gọn. - Các tác giả trong [12] xây dựng công thức cập nhật độ đo không nhất quán trong trường hợp tập đối tượng, tập thuộc tính thay đổi giá trị, trên cơ sở đó đề xuất hai thuật toán: thuật toán Object-R cập nhật tập rút gọn trong trường hợp tập đối tượng thay đổi giá trị và Attribute-R trong trường hợp tập thuộc tính thay đổi giá trị. - Tuy nhiên, các thuật toán đề xuất nêu trên đều theo hướng tiếp cận lọc truyền thống. - Do đó, bài báo này nghiên cứu, đề xuất các thuật toán gia tăng tìm tập rút gọn theo hướng tiếp cận lọc - đóng gói sử dụng khoảng cách trong trường hợp tập đối tượng, tập thuộc tính thay đổi giá trị nhằm giảm thiểu số lượng thuộc tính tập rút gọn, từ đó nâng cao hiệu quả của mô hình phân lớp. - Kết quả thực nghiệm trên các tập dữ liệu mẫu cho thấy, thuật toán gia tăng lọc - đóng gói đề xuất hiệu quả hơn về số lượng thuộc tính tập rút gọn và độ chính xác phân lớp so với các thuật toán lọc đã công bố.. - là tập hữu hạn các thuộc tính điều kiện. - d là thuộc tính quyết định. - Mỗi thuộc tính a C xác định một ánh xạ: a U. - V a với V a là tập giá trị của thuộc tính a C . - là giá trị thuộc tính a tại đối tượng u.. - khi đó ma trận dung sai trên tập thuộc tính S. - Phương pháp gia tăng rút gọn thuộc tính khi tập đối tượng, tập thuộc tính thay đổi giá trị Trong phần này, chúng tôi xây dựng công thức gia tăng tính khoảng cách và đề xuất hai thuật toán hiệu quả tìm tập rút gọn trong trường hợp tập đối tượng và tập thuộc tính thay đổi giá trị.. - Thuật toán gia tăng lọc - đóng gói tìm tập rút gọn khi tập đối tượng thay đổi giá trị Mệnh đề 1[3]. - Khi đó, khoảng cách giữa hai tập thuộc tính C và C. - 1 bị thay đổi giá trị thành. - 1 s bị thay đổi giá trị thành c i k. - u ,u ,...,u 1 2 n và R C là tập rút gọn dựa trên khoảng cách.. - k n, s 1 bị thay đổi giá trị thành. - và U ' là tập đối tượng sau khi thay đổi giá trị. - bị thay đổi giá trị thành. - j n thì R là tập rút gọn của IDS. - Trong mục này, bài báo đề xuất thuật toán gia tăng tìm tập rút gọn theo tiếp cận lọc - đóng gói. - Thuật toán bao gồm hai giai đoạn: Giai đoạn lọc: Tìm các ứng viên cho tập rút gọn. - Giai đoạn đóng gói: Tìm tập rút gọn có độ chính xác phân lớp lớn nhất. - Thuật toán gia tăng lọc - đóng gói tìm tập rút gọn khi tập đối tượng thay đổi giá trị được mô tả như sau:. - Thuật toán FWIA_U_Obj (Filter-Wrapper Incremental Algorithm for Attribute Reduction in Incomplete Decision Tables when Update Objects).. - Tập rút gọn R C. - U’ là tập đối tượng sau khi thay đổi giá trị.. - Đầu ra: Tìm tập rút gọn R best trên IDS. - //T chứa các ứng viên của tập rút gọn 2. - Bước 2: Tìm tập rút gọn. - //Loại bỏ các thuộc tính dư thừa trong R 6. - Bổ sung các thuộc tính còn lại vào R 8. - Thuật toán gia tăng lọc - đóng gói tìm tập rút gọn khi tập thuộc tính thay đổi giá trị. - Phần này xây dựng công thức gia tăng tính khoảng cách trong trường hợp tập thuộc tính thay đổi giá trị bởi mệnh đề 4 dưới đây.. - Giả sử tập s thuộc tính C. - k n, s 1 bị thay đổi giá trị. - tương ứng là ma trận dung sai của tập thuộc tính C trước và sau khi thay đổi giá trị và M A. - d ij n n tương ứng là ma trận dung sai trên là ma trận dung sai của tập thuộc tính còn lại không thay đổi giá trị. - d ) tương ứng là khoảng cách trước khi và sau khi tập thuộc tính C thay đổi giá trị. - Thuật toán gia tăng lọc - đóng gói tìm tập rút gọn khi tập thuộc tính thay đổi giá trị được mô tả như sau:. - Thuật toán FWIA_U_Attr (Filter-Wrapper Incremental Algorithm for Attribute Reduction in Incomplete Decision Tables when Update Attributes).. - tập rút gọn R C các ma trận dung sai. - 2) Tập thuộc tính C bị thay đổi giá trị, với. - Đầu ra: Tập rút gọn R ' của IDS. - d ) sau khi C bị thay đổi giá trị.. - Chứa các ứng viên tập rút gọn 2. - Loại bỏ các thuộc tính dư thừa trong R;. - Bước 2: Thực hiện thuật toán tìm tập rút gọn. - Giai đoạn lọc, tìm các ứng viên cho tập rút gọn xuất phát từ tập R.. - Trong phần này, chúng tôi tiến hành thực nghiệm để đánh giá hiệu quả của thuật toán FWIA_U_Obj. - Đánh giá tính hiệu quả của thuật toán gia tăng lọc - đóng gói FWIA_U_Obj tìm tập rút gọn khi tập đối tượng thay đổi giá trị dựa trên các tiêu chí: số lượng thuộc tính trong tập rút gọn, độ chính xác phân lớp và thời gian thực hiện. - Thuật toán FWIA_U_Obj được so sánh với hai thuật toán FSMV [11] và Object-R [12].. - FSMV là thuật toán gia tăng tìm tập rút gọn theo tiếp cận lọc trong trường hợp tập đối tượng thay đổi giá trị sử dụng miền dương. - Trong khi đó, Object-R là thuật toán gia tăng tìm tập rút gọn theo tiếp cận lọc trong trường hợp tập đối tượng thay đổi giá trị sử dụng độ đo không nhất quán.. - Chúng tôi tiến hành cài đặt cả 3 thuật toán: FWIA_U_Obj, FSMV và Object-R. - Sau đó chạy 3 thuật toán trên cùng môi trường thực nghiệm đó là trên máy tính cá nhân PC: Bộ xử lý Intel, Core TM i GHz, Windows 7 sử dụng Matlab. - Với tập dữ liệu O chan , chúng tôi thực hiện cập nhật ngẫu nhiên giá trị thuộc tính của các đối tượng bị thay đổi, bảo đảm nguyên tắc các giá trị bị thay đổi thuộc miền giá trị của thuộc tính ban đầu. - Số thuộc tính điều kiện. - Các bộ dữ liệu được sử dụng trong thực nghiệm khi tập đối tượng thay đổi giá trị. - Trước hết, chúng tôi thực hiện thuật toán IDT_FW_DAR [4] để tìm tập rút gọn trên tập đối tượng ban đầu, làm đầu vào cho các thuật toán gia tăng. - Tiếp theo, thực hiện cài đặt và chạy 03 thuật toán FWIA_U_Obj, FSMV và Object-R khi lần lượt đưa vào các tập đối tượng thay đổi giá trị O 1 , O 2. - Sau đó, các giá trị số lượng thuộc tính tập rút gọn, độ chính xác phân lớp và thời gian thực hiện được ghi lại.. - Đánh giá thuật toán FWIA_U_Obj trên hai tiêu chí: số lượng thuộc tính trong tập rút gọn và độ chính xác phân lớp. - Bảng 2 trình bày kết quả về số thuộc tính trong tập rút gọn và độ chính xác phân lớp của các thuật toán FWIA_U_Obj, FSMV và Object-R. - Trong đó, cột |R| và Acc lần lượt là số thuộc tính trong tập. - rút gọn và độ chính xác phân lớp. - Dựa trên kết quả trong bảng 2 ta thấy rằng, độ chính xác phân lớp của thuật toán gia tăng lai ghép lọc - đóng gói FWIA_U_Obj cao hơn một chút so với FSMV và Object-R trên tất cả các tập dữ liệu và trên tất cả các bước lặp khi đưa lần lượt các tập đối tượng thay đổi giá trị O 1 , O 2 O 3 , O 4 , O 5 . - Hơn nữa, số lượng thuộc tính trong tập rút gọn thu được bởi FWIA_U_Obj nhỏ hơn nhiều so với FSMV và Object-R, đặc biệt là trong tập dữ liệu có nhiều thuộc tính như Ad.data. - Do đó, mô hình phân lớp dựa trên tập rút gọn của thuật toán FWIA_U_Obj hiệu quả hơn mô hình phân lớp của thuật toán FSMV và thuật toán Object-R về chất lượng phân lớp và độ phức tạp của mô hình. - Có thể thấy rằng, thuật toán Object-R hiệu quả hơn một chút so với thuật toán FSMV về cả độ chính xác của phân lớp và số lượng thuộc tính trong tập rút gọn.. - Số lượng thuộc tính tập rút gọn và độ chính xác phân lớp của ba thuật toán FWIA_U_Obj, FSMV và Object-R. - Tập dữ liệu thay đổi giá trị. - Đánh giá thời gian thực hiện của thuật toán FWIA_U_Obj. - Thời gian thực hiện của thuật toán FWIA_U_Obj, FSMV và Object-R (tính theo giây) được trình bày như trong bảng 3.. - Trên tất cả các tập dữ liệu trong bảng 3, thuật toán FWIA_U_Obj có thời gian thực hiện cao hơn thuật toán FSMV và thuật toán Object-R vì thuật toán FWIA_U_Obj cần nhiều thời gian hơn để chạy phân lớp trong giai đoạn đóng gói. - Trong khi đó, thời gian thực hiện của thuật toán. - Object-R cao hơn một chút thuật toán FSMV vì thời gian tính độ không nhất quán trong Object- R cao hơn thời gian tính miền dương trong FSMV.. - Thời gian thực hiện của ba thuật toán FWIA_U_Obj, FSMV và Object-R (tính bằng giây). - Tập dữ liệu thay đổi giá. - Trong bài báo này, chúng tôi đã nghiên cứu đề xuất các thuật toán gia tăng lọc - đóng gói tìm tập rút gọn của bảng quyết định không đầy đủ thay đổi, sử dụng độ đo khoảng cách trong các tình huống tập đối tượng và tập thuộc tính thay đổi giá trị. - Kết quả thực nghiệm cho thấy, các thuật toán đề xuất theo tiếp cận lọc - đóng gói giảm thiểu số lượng thuộc tính tập rút gọn và cải thiện độ chính xác của mô hình phân lớp so với các thuật toán gia tăng khác theo tiếp cận lọc đã công bố. - Tuy nhiên, các thuật toán đề xuất có thời gian thực hiện cao hơn, đây là hạn chế của cách tiếp cận này. - Trong thời gian tới, chúng tôi tiếp tục nghiên cứu, cải tiến các thuật toán gia tăng lọc - đóng gói đã công bố nhằm phù hợp với các lớp bài toán khác nhau trong thực tế, nhất là giảm thiểu thời gian thực hiện bằng giải pháp không chạy lặp lại các bộ phân lớp.
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt