Bài báo này nhằm trình bày một thuật toán mới cho phép làm giảm độ phức tạp của thuật toán. Dựa vào vùng dương, chúng tôi định nghĩa ma trận phân biệt đơn giản hóa và tập lõi tương ứng. | Tạp chí KHOA HỌC & CÔNG NGHỆ 52(4): 41 - 46 4 - 2009 THUẬT TOÁN NHANH TÍNH TOÁN TẬP THUỘC TÍNH LÕI CỦA BẢNG QUYẾT ĐỊNH DỰA VÀO VÙNG DƢƠNG – ) Phạm Quang Dũng (Trường Cao đẳng Giao thông vận tải) Tóm tắt Tính toán tập (thuộc tính) lõi của bảng quyết định là một nội dung nghiên cứu quan trọng của lý thuyết tập thô. Một số học giả đã xây dựng thuật toán tính toán tập lõi dựa vào vùng dương và sử dụng ma trận phân biệt. Độ phức tạp của thuật toán này là O C U 2 . Bài báo này nhằm trình bày một thuật toán mới cho phép làm giảm độ phức tạp của thuật toán. Dựa vào vùng dương, chúng tôi định nghĩa ma trận phân biệt đơn giản hóa và tập lõi tương ứng. Chúng tôi chứng minh rằng tập lõi này tương đương với tập lõi xác định thông qua ma trận phân biệt nguyên thủy. Vì việc xác định phân hoạch U/C là chìa khóa để tính toán ma trận phân biệt đơn giản hóa, một thuật toán nhanh tính U/C được thiết kế sử dụng thuật sắp thứ tự theo cơ số. Độ phức tạp của thuật toán là O C U . Sử dụng thuật toán nhanh xác định U/C và ma trận phân biệt đơn giản hóa, một thuật toán mới xác định tập lõi dựa vào vùng dương được xây dựng. Độ phức tạp của thuật toán mới này được giảm thiểu và là max O C U p' os U / C , O C U . Từ khóa: Tập thô, Vùng dương, Ma trận phân biệt đơn giản hóa, Tập lõi, Độ phức tạp. Mở đầu Lý thuyết tập thô [1], do Pawlak đề xuất năm 1982, là một công cụ toán học mới để xử lý thông tin không chính xác, không chắc chắn hay tri thức mờ. Đến nay, lý thuyết tập thô đã và đang được ứng dụng rộng rãi trong nhiều lĩnh vực: trí tuệ nhân tạo, nhận dạng mẫu, khai phá tri thức và khám phá thông minh các luật quyết định. Tính toán tập (thuộc tính) lõi của bảng quyết định là một nội dung nghiên cứu quan trọng của lý thuyết tập thô. Cho đến nay, nhiều tác giả đã nghiên cứu đưa ra các thuật toán khác nhau tính toán tập lõi, trong đó có các thuật toán dựa vào vùng dương và sử dụng ma trận phân biệt. Trong [3], Hu đã đề xuất một thuật toán tính toán tập lõi dựa vào ma trận phân biệt với
