Luận án tiến sĩ máy tính và công nghệ thông tin một số phƣơng pháp lai ghép tron

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ …….***………… NGUYỄN VĂN THIỆN MỘT SỐ PHƢƠNG PHÁP LAI GHÉP TRONG RÚT GỌN THUỘC TÍNH THEO TIẾP CẬN TẬP THÔ MỜ LUẬN ÁN TIẾN SĨ MÁY TÍNH VÀ CÔNG NGHỆ THÔNG TIN Hà Nội – 2018 VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ …….***………… NGUYỄN VĂN THIỆN MỘT SỐ PHƢƠNG PHÁP LAI GHÉP TRONG RÚT GỌN THUỘC TÍNH THEO TIẾP CẬN TẬP THÔ MỜ LUẬN ÁN TIẾN SĨ MÁY TÍNH VÀ CÔNG NGHỆ THÔNG TIN Chuyên ngành : Hệ thống thông tin Mã số: 9 48 01 04 Ngƣời hƣớng dẫn khoa học: 1. Nguyễn Long Giang 2. Nguyễn Nhƣ Sơn Hà Nội – 2018 i MỤC LỤC MỤC LỤC.i Danh mục các thuật ngữ.iii Bảng các ký hiệu, từ viết tắt.iv Danh sách bảng.v Danh sách hình vẽ.vi MỞ ĐẦU. TỔNG QUAN VỀ RÚT GỌN THUỘC TÍNH THEO TIẾP CẬN TẬP THÔ MỜ.

Một số khái niệm trong lý thuyết tập thô. Hệ thông tin và bảng quyết định. Quan hệ tương đương. Các tập xấp xỉ và tập thô.

Một số khái niệm trong lý thuyết tập thô mờ. Quan hệ tương đương mờ. Ma trận tương đương mờ. Phân hoạch mờ.

Các tập xấp xỉ mờ và tập thô mờ. Tổng quan về rút gọn thuộc tính. Rút gọn thuộc tính. Tiếp cận filter, wrapper trong rút gọn thuộc tính.

Các nghiên cứu liên quan đến rút gọn thuộc tính theo tiếp cận tập thô mờ. Rút gọn thuộc tính trên bảng quyết định mờ theo tiếp cận tập thô mờ. Rút gọn thuộc tính trực tiếp trên bảng quyết định theo tiếp cận tập thô mờ. Phương pháp gia tăng rút gọn thuộc tính trong bảng quyết định thay đổi theo tiếp cận tập thô mờ.

Tóm tắt các đóng góp của luận án. RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH SỬ DỤNG ĐỘ PHỤ THUỘC MỜ VÀ KHOẢNG CÁCH MỜ ii. Rút gọn thuộc tính sử dụng độ phụ thuộc mờ. Rút gọn thuộc tính sử dụng độ phụ thuộc theo tiếp cận filter.

Rút gọn thuộc tính sử dụng độ phụ thuộc mờ theo tiếp cận filter. Rút gọn thuộc tính sử dụng độ phụ thuộc mờ theo tiếp cận filter-wrapper. Thực nghiệm các thuật toán. Rút gọn thuộc tính sử dụng khoảng cách mờ.

Xây dựng khoảng cách mờ giữa hai tập mờ. Xây dựng khoảng cách mờ giữa hai phân hoạch mờ. Rút gọn thuộc tính sử dụng khoảng cách mờ theo tiếp cận filter. Rút gọn thuộc tính sử dụng khoảng cách mờ theo tiếp cận filter-wrapper.

Thực nghiệm các thuật toán. Kết luận chương 2. RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH THAY ĐỔI SỬ DỤNG KHOẢNG CÁCH MỜ. Thuật toán gia tăng filter-wrapper tìm tập rút gọn xấp xỉ khi bổ sung tập đối tượng 75 3.

Công thức gia tăng tính khoảng cách mờ khi bổ sung tập đối tượng. Thuật toán gia tăng filter-wrapper tìm tập rút gọn khi bổ sung tập đối tượng 78 3. Thực nghiệm thuật toán. Thuật toán filter-wrapper tìm tập rút gọn khi loại bỏ tập đối tượng.

Công thức cập nhật khoảng cách mờ khi loại bỏ tập đối tượng. Thuật toán filter-wrapper tìm tập rút gọn khi loại bỏ tập đối tượng. Kết luận chương 3.97 iii Danh mục các công trình của tác giả.98 Tài liệu tham khảo.99 iv Danh mục các thuật ngữ Thuật ngữ tiếng Việt Thuật ngữ tiếng Anh Tập thô Rough Set Tập thô mờ Fuzzy Rough Set Hệ thông tin Information System Bảng quyết định Decision Tables Bảng quyết định mờ Fuzzy Decision Tables Quan hệ tương đương Equivalence Relation Quan hệ tương đương mờ Fuzzy Equivalence Relation Phân hoạch mờ Fuzzy Partition Ma trận tương đương mờ Fuzzy Equivalence Matrix Lớp tương đương mờ Fuzzy equivalence Classes Xấp xỉ dưới mờ Fuzzy Lower Approximation Xấp xỉ trên mờ Fuzzy Upper Approximation Miền dương mờ Fuzzy Positive Region Độ phụ thuộc mờ của thuộc tính Fuzzy Dependency Degree Rút gọn thuộc tính Attribute Reduction Tập rút gọn Reduct Phương pháp gia tăng Incremental Methods Khoảng cách mờ Fuzzy Distance Lọc Filter Đóng gói Wrapper v Bảng các ký hiệu, từ viết tắt Ký hiệu, từ viết tắt Diễn giải IS  U, A Hệ thông tin DS  U,C D Bảng quyết định U Số đối tượng C Số thuộc tính điều kiện trong bảng quyết định u a Giá trị của đối tượng u tại thuộc tính a IND  B Quan hệ tương đương trên B U/P Phân hoạch của U trên P  u B Lớp tương đương chứa u của phân hoạch U / P R Quan hệ tương đương mờ R. RP Quan hệ tương đương mờ R trên tập thuộc tính P M RP  Ma trận tương đương mờ của RP  R P Phân hoạch mờ trên RP xi P Lớp tương đương mờ của xi thuộc phân hoạch mờ  R P  xi  Lực lượng lớp tương đương mờ  xi  P P RP X Tập xấp xỉ dưới mờ của X đối với RP RP X Tập xấp xỉ trên mờ của X đối với RP POS RP R  Q Miền dương mờ của RQ đối với RP  D Độ phụ thuộc mờ của P đối với D dựa trên quan hệ RP RP     D R P , RQ Khoảng cách mờ giữa hai phân hoạch mờ R P và   RQ vi Danh sách bảng Bảng 1.

Bảng quyết định Ví dụ 1.14 ản ảng quyết định mờ. Bảng quyết định Ví dụ 2. Bộ dữ liệu thử nghiệm thuật toán F_FRSAR, FW_FRSAR. Độ chính xác phân lớp của F_FRSAR và RSAR.

Độ chính xác phân lớp của GAIN_RATIO_AS_FRS và F_FRSAR. Độ chính xác phân lớp FW_FRSAR, F_FRSAR, GAIN_RATIO_AS_FRS. Thời gian thực hiện FW_FRSAR, F_FRSAR, GAIN_RATIO_AS_FRS. Bảng quyết định Ví dụ 2.

Bộ dữ liệu thử nghiệm thuật toán FW_FDAR. Độ chính xác phân lớp FW_FDAR, FEBAR, FPDAR. Thời gian thực hiện FW_FDAR, FEBAR, FPDAR. Bộ dữ liệu thử nghiệm thuật toán IFW_FDAR_AdObj.

Thời gian thực hiện IFW_FDAR_AdObj, FW_FDAR, FEBAR (s). Độ chính xác phân lớp IFW_FDAR_AdObj, FW_FDAR, FEBAR. Thời gian thực hiện IFW_FDAR_AdObj, IV-FS-FRS-2, IARM. Độ chính xác phân lớp IFW_FDAR_AdObj, IV-FS-FRS-2, IARM.88 vii Danh sách hình vẽ Hình 1.

Quy trình rút gọn thuộc tính. Cách tiếp cận filter và wrapper trong rút gọn thuộc tính. Độ chính xác phân lớp của F_FRSAR và RSAR. Độ chính xác phân lớp của GAIN_RATIO_AS_FRS và F_FRSAR.51 1 MỞ ĐẦU Với sự phát triển mạnh mẽ của công nghệ thông tin, các cơ sở dữ liệu ngày càng gia tăng về dung lượng dữ liệu cũng như số lượng thuộc tính, gây rất nhiều khó khăn cho việc thực thi các thuật toán khai phá dữ liệu.

Vấn đề đặt ra là phải tìm cách rút gọn số lượng thuộc tính mà không làm mất mát những thông tin cần thiết phục vụ nhiệm vụ khai phá dữ liệu. Do đó, rút gọn thuộc tính (còn gọi là rút gọn chiều hay rút gọn đặc trưng) là đề tài thu hút sự quan tâm của nhiều nhà nghiên cứu thuộc các lĩnh vực nhận dạng thống kê, học máy, khai phá dữ liệu. Rút gọn thuộc tính là bài toán quan trọng trong bước tiền xử lý dữ liệu với mục tiêu là loại bỏ các thuộc tính dư thừa, không liên quan nhằm tăng tính hiệu quả của các thuật toán khai phá dữ liệu. Hiện nay có hai cách tiếp cận chính đối với bài toán rút gọn thuộc tính [43, 44]: filter (lọc) và wrapper (đóng gói).

Cách tiếp cận filter thực hiện việc rút gọn thuộc tính độc lập với thuật khai phá dữ liệu sử dụng sau này. Các thuộc tính được chọn chỉ dựa trên độ quan trọng của chúng trong việc phân lớp dữ liệu. Trong khi đó, cách tiếp cận wrapper tiến hành việc lựa chọn bằng cách áp dụng ngay thuật khai phá, độ chính xác của kết quả được lấy làm tiêu chuẩn để lựa chọn các tập con thuộc tính. Lý thuyết tập thô (Rough set) do Pawlak đề xuất [101] là công cụ hiệu quả giải quyết bài toán rút gọn thuộc tính và được cộng đồng nghiên cứu về tập thô thực hiện lâu nay.

Các phương pháp rút gọn thuộc tính theo tiếp cận tập thô truyền thống và tập thô dung sai được nghiên cứu khá đầy đủ trong các luận án tiến sĩ [4, 5, 6, 11, 13], bao gồm các phương pháp cơ bản như: phương pháp dựa trên miền dương, phương pháp sử dụng ma trận không phân biệt được, phương pháp sử dụng entropy thông tin, phương pháp sử dụng các độ đo trong tinh toán hạt, phương pháp sử dụng metric (khoảng cách). Gần đây, luận án tiến sĩ [7] nghiên cứu các phương pháp gia tăng tìm tập rút gọn của bảng quyết định thay đổi theo tiếp cận tập thô truyền thống. Tuy nhiên, các phương pháp rút gọn thuộc tính theo tiếp cận tập thô truyền thống, tập thô dung sai trong các luận án tiến sĩ nêu trên và các nghiên cứu liên quan đều 2 theo hướng tiếp cận filter và thực hiện trên các bảng quyết định có miền giá trị rời rạc (bảng quyết định sau khi thực hiện các phương pháp rời rạc hóa dữ liệu). Các phương pháp rời rạc hóa dữ liệu không bảo toàn sự khác nhau ban đầu giữa các đối tượng trong dữ liệu gốc.

Do đó, các phương pháp rút gọn thuộc tính theo tiếp cận tập thô, tập thô dung sai được trình bày ở trên giảm thiểu độ chính xác của mô hình phân lớp trên dữ liệu gốc. Nhằm nâng cao độ chính xác của mô hình phân lớp, các nhà nghiên cứu đề xuất các phương pháp rút gọn thuộc tính theo tiếp cận tập thô mờ. Lý thuyết tập thô mờ (Fuzzy rough set) do Dubois và các cộng sự [22, 23] đề xuất là sự kết hợp của lý thuyết tập thô và lý thuyết tập mờ nhằm xấp xỉ các tập mờ dựa trên một quan hệ tương đương mờ (fuzzy equivalent relation) được xác định trên miền giá trị thuộc tính. Ban đầu, tập thô mờ là công cụ giải quyết bài toán rút gọn thuộc tính trên bảng quyết định mờ [40, 41, 76, 77, 78, 79, 81].

Về sau, các nhà nghiên cứu tập trung giải quyết bài toán rút gọn thuộc tính trực tiếp trên bảng quyết định gốc (bảng quyết định không qua bước rời rạc hóa dữ liệu) theo tiếp cận tập thô mờ nhằm nâng cao độ chính xác của mô hình phân lớp. Các phương pháp rút gọn thuộc tính trong bảng quyết định gốc theo tiếp cận tập thô mờ là các nghiên cứu mở rộng của các phương pháp rút gọn thuộc tính theo tiếp cận tập thô truyền thống đã được nghiên cứu lâu nay. Đây là các phương pháp heuristic theo tiếp cận filter, bao gồm các bước xây dựng độ đo, định nghĩa tập rút gọn và độ quan trọng của thuộc tính sử dụng độ đo được xây dựng, trên cơ sở đó xây dựng thuật toán heuristic tìm tập rút gọn theo tiêu chuẩn là độ quan trọng của thuộc tính. Việc đánh giá độ chính xác của mô hình phân lớp được thực hiện sau khi tìm được tập rút gọn.