Thuận toán nhanh tính toán lập thuộc tính lõi của bảng quyết định đưa vào vùng dương

52(4): 41 - 46 Tạp chí KHOA HỌC & CÔNG NGHỆ 4 - 2009

1

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à

2

O C U

. 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à

'

os ax O C / , m U U C O C U p

.

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 độ phức tạp là

2

O C U .

Trong bài này, để giảm thiểu độ phức tạp của

thuật toán tính toán tập lõi, trước tiên chúng tôi

đưa ra định nghĩa về ma trận phân biệt đơn giản

hóa và định nghĩa 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à bước

chính trong quá trình 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, 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 xuống là

'

os ax O C / , m U U C O C U p

,

trong đó

'

Upos

là tập các đại diện của các lớp

tương đương sinh bởi phân hoạch U/C.

I.Ma trận phân biệt đơn giản hóa dựa vào vùng

dƣơng.

Định nghĩa 2.1. [1]. Bảng quyết định là một bộ tứ

S U C D V f , , , ,

, trong đó

1 2 , ,..., U x x xn

là tập các đối tượng,

1 2 , ,..., C c c cr

là tập các

thuộc tính điều kiện, D là tập các thuộc tính quyết

định,

C D

;

a

a C D

V V 

, trong đó

Va

là

miền giá trị của thuộc tính a;

f U C D V : ( )

là hàm thông tin cho biết

giá trị của mỗi thuộc tính tại mỗi đối tượng, nghĩa

là

, , ,

a

a C D x U f x a V .

Mỗi tập con thuộc tính

P C D

xác định

một quan hệ nhị phân, gọi là quan hệ không phân

biệt

IND P

:

IND P x y U U a P f x a f y a , | , , ,

(1)