Luận văn tốt nghiệp: Tiếp cận lý thuyết tập thô do Z.Pawlak



Luận văn tốt nghiệp Tiếp cận lý thuyết tập thô do Z.Pawlak

Mục lục

Danh mục các thuật ngữ 2

Danh sách bảng

Phần mở đầu

Chương 1. Các khái niệm cơ bản

1.1. Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.2. Hệ thống thông tin và tập thô . . . . . . . . . . . . . . . . . . . . . . 11

1.2.1. Hệ thống thông tin . . . . . . . . . . . . . . . . . . . . . . . . 11

1.2.2. Quan hệ không phân biệt được

. . . . . . . . . . . . . . . . . 12

1.2.3. Các tập xấp xỉ

. . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.2.4. Các tính chất của xấp xỉ . . . . . . . . . . . . . . . . . . . . . 15

Bảng các ký hiệu 3

1.2.5. Độ chính xác của xấp xỉ . . . . . . . . . . . . . . . . . . . . . 16

1.3. Bảng quyết định . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.3.1. Rút gọn và lõi . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1.3.2. Ma trận và hàm phân biệt được . . . . . . . . . . . . . . . . . 18

1.3.3. Luật quyết định . . . . . . . . . . . . . . . . . . . . . . . . . . 23

1.4. Phụ thuộc xấp xỉ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

1.4.1. Hàm thành viên thô . . . . . . . . . . . . . . . . . . . . . . . 24

1.4.2. Phụ thuộc hàm xấp xỉ . . . . . . . . . . . . . . . . . . . . . . 25

1.4.3. Rút gọn xấp xỉ . . . . . . . . . . . . . . . . . . . . . . . . . . 28

Chương 2. Một số thuật toán tìm tập rút gọn 31

2.1. Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.2. Thuật toán sử dụng các phép toán đại số . . . . . . . . . . . . . . . . 32

2.2.2. Đặc trưng của tập rút gọn . . . . . . . . . . . . . . . . . . . . 36

2.2.3. Các thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . 39

2.3. Thuật toán dựa vào số cặp phân biệt được . . . . . . . . . . . . . . . 43

2.3.1. Một số ký hiệu . . . . . . . . . . . . . . . . . . . . . . . . . . 43

2.3.2. Cơ sở toán học . . . . . . . . . . . . . . . . . . . . . . . . . . 45

2.3.3. Thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

2.4. Thuật toán tìm rút gọn xấp xỉ . . . . . . . . . . . . . . . . . . . . . . 52

2.4.1. Đặt vấn đề

. . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

2.4.2. Sai số của rút gọn xấp xỉ . . . . . . . . . . . . . . . . . . . . . 52

2.4.3. Các thuật toán tìm rút gọn xấp xỉ

. . . . . . . . . . . . . . . 54

2.2.1. Tập lõi trong bảng quyết định . . . . . . . . . . . . . . . . . . 32

Chương 3. Khám phá phụ thuộc đa trị 58

3.1. Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

3.2. Khảo sát phụ thuộc bằng Ma trận phụ thuộc . . . . . . . . . . . . . . 60

3.2.1. Phụ thuộc và phụ thuộc xấp xỉ . . . . . . . . . . . . . . . . . 60

3.2.2. Đặc trưng phụ thuộc bằng ma trận phụ thuộc . . . . . . . . . 63

3.3. Thuật toán kiểm định và tìm kiếm phụ thuộc . . . . . . . . . . . . . 69

3.3.1. Thuật toán tính độ dầy đặc của dãy ma trận . . . . . . . . . . 69

3.3.2. Thuật toán kiểm định phụ thuộc xấp xỉ . . . . . . . . . . . . 73

3.3.3. Thuật toán tìm kiếm phụ thuộc tối tiểu vế phải . . . . . . . . 75

3.4. Mở rộng phụ thuộc hàm và phụ thuộc đa trị . . . . . . . . . . . . . . 77

3.4.1. Quan hệ tương tự . . . . . . . . . . . . . . . . . . . . . . . . . 78

3.4.3. Đặc trưng β−phụ thuộc bằng ma trận phụ thuộc . . . . . . . 84

3.4.4. Thuật toán kiểm định β−phụ thuộc đa trị

. . . . . . . . . . . 88

3.5. Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

Phần Kết luận

Tài liệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

3.4.2. Phụ thuộc mở rộng và các tính chất . . . . . . . . . . . . . . . 81

Chương

DANH MỤC CÁC THUẬT NGỮ

Hệ thống thông tin ()

Tập thô (Rough Set)

Quan hệ không phân biệt được

Tập xấp xỉ dưới

Tập xấp xỉ trên

Bảng quyết định

Rút gọn

Lõi

Ma trận phân biệt được

Hàm phân biệt được

Luật quyết định

Phụ thuộc hàm

Phụ thuộc đa trị

Phụ thuộc xấp xỉ

Chương

BẢNG CÁC KÝ HIỆU

u(a): Giá trị của đối tượng u tại thuộc tính a.

IND(B): Quan hệ B−không phân biệt được.

IND(B|V ): Quan hệ B−không phân biệt được cảm sinh trên tập V .

[u]B: Lớp tương đương chứa u của quan hệ IND(B).

U/B: Tập hợp thương của quan hệ IND(B).

V /B: Tập hợp thương của quan hệ IND(B|V ).

BV : B−xấp xỉ dưới của V .

A = (U, A): Hệ thống thông tin.

BV : B−xấp xỉ trên của V .

T = (U, C ∪ D): Bảng quyết định.

POSB(D) : B−miền khẳng định của D.

Lower[B]/[D]: B−xấp xỉ dưới tương ứng với D của U .

Upper[B]/[D]: B−xấp xỉ trên tương ứng với D của U .

Boundary[B]/[D]: B−biên tương ứng với D của U .

k(R, D): Độ phụ thuộc của tập thuộc tính quyết định D vào tập con các thuộc

tính điều kiện R.

m(cj, R): Khả năng đóng góp của thuộc tính cj vào R.

B (cj): Số cặp đối tượng của V bằng nhau trên tập thuộc tính B nhưng khác

ωV

nhau tại thuộc tính cj.

B (D): Số cặp đối tượng của V bằng nhau trên tập thuộc tính B nhưng khác

ωV

nhau trên tập thuộc tính D.

ωV (cj): Số cặp đối tượng của V khác nhau tại thuộc tính cj.

ωB(cj): Số cặp đối tượng của U bằng nhau trên tập thuộc tính B nhưng khác

nhau tại thuộc tính cj.

ωB(D): Số cặp đối tượng của U bằng nhau trên tập thuộc tính B nhưng khác

nhau trên tập thuộc tính D.

: Y không phụ thuộc hàm vào X trên U .

X 6→ Y

X →/→ Y : Y không phụ thuộc đa trị vào X trên U .

X→V Y : Y phụ thuộc hàm vào X đúng trên tập con V ⊆ U .

X→→V Y : Y phụ thuộc đa trị vào X đúng trên tập con V ⊆ U .

α,β −→ Y : Y là (α, β)− phụ thuộc hàm vào X trên U .

α,β →→ Y : Y là (α, β)− phụ thuộc đa trị vào X trên U .

ωV (D): Số cặp đối tượng của V khác nhau trên tập thuộc tính D.

Danh sách bảng

1.2 Các triệu chứng của bệnh nhân. . . . . . . . . . . . . . . . . . . . . . 14

1.3 Bảng quyết định về bệnh cúm.

. . . . . . . . . . . . . . . . . . . . . 18

. . . . . . . . . 19

1.4 Bảng rút gọn thứ nhất của hệ thống bệnh cúm (R1).

. . . . . . . . . . 19

1.5 Bảng rút gọn thứ hai của hệ thống bệnh cúm (R2).

1.6 Dữ liệu bảng quyết định. . . . . . . . . . . . . . . . . . . . . . . . . . 20

1.7 Ma trận phân biệt được M.

. . . . . . . . . . . . . . . . . . . . . . . 21

1.8 Bảng chọn ứng cử viên vào ngạch giảng dạy.

. . . . . . . . . . . . . . 24

1.9 Bảng dữ liệu.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.1 Bảng thông tin về các xe hơi.

. . . . . . . . . . . . . . . . . . . . . . 35

1.1 Bảng dữ liệu các đồ chơi. . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.2 Bảng dữ liệu các đồ chơi. . . . . . . . . . . . . . . . . . . . . . . . . . 45

2.3 Bảng chọn lựa giáo viên. . . . . . . . . . . . . . . . . . . . . . . . . . 49

2.4 Bảng dữ liệu cho ví dụ rút gọn xấp xỉ. . . . . . . . . . . . . . . . . . 54

3.1 Bảng dữ liệu sinh viên. . . . . . . . . . . . . . . . . . . . . . . . . . . 62

3.2 Dữ liệu của hệ thống. . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

3.3 Bảng dữ liệu về các lập trình viên . . . . . . . . . . . . . . . . . . . . 80

3.4 Quan hệ tương tự trên Ib . . . . . . . . . . . . . . . . . . . . . . . . . 80

3.5 Quan hệ tương tự trên Ic . . . . . . . . . . . . . . . . . . . . . . . . . 80

3.6 Dữ liệu của hệ thống. . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

. . . . . . . . . . . . . . . . 83 3.7 Các quan hệ tương tự trên IX, IY và IZ.

3.8 Bảng dữ liệu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

. . . . . . . . . . . . . . . . . . 86 3.9 Các quan hệ tương tự trên IY và IZ.

Chương

PHẦN MỞ ĐẦU

Lý thuyết tập thô do Zdzisaw Pawlak [24] đề xuất vào những năm đầu thập

niên tám mươi của thế kỷ hai mươi đã được áp dụng ngày càng rộng rãi trong nhiều

lĩnh vực của khoa học máy tính. Lý thuyết tập thô được phát triển trên một nền

tảng toán học vững chắc và cung cấp những công cụ hữu ích để giải quyết các bài

toán phân lớp dữ liệu, phát hiện luật v.v... đặc biệt thích hợp đối với những bài

toán chứa dữ liệu mơ hồ không chắc chắn.

Mười lăm năm trở lại đây đã đánh dấu sự phát triển mạnh mẽ của lĩnh vực

khai phá dữ liệu và phát hiện tri thức trong cơ sở dữ liệu. Trong xu thế đó, nhiều

nhóm khoa học trên thế giới đã nghiên cứu, phát triển lý thuyết tập thô vào lĩnh vực

nghiên cứu và ứng dụng nổi bật này. Về phương diện nghiên cứu phát triển ứng dụng

lý thuyết tập thô vào các lĩnh vực như ngân hàng, tài chính, sinh học (biểu thị gen),

... có thể kể đến các công trình nghiên cứu [7, 8, 9, 10, 11, 12, 13, 18, 19, 20, 23, 27].

Về phương diện nghiên cứu phát triển mô hình và giải pháp theo tiếp cận tập thô

có thể kể đến các công trình [14, 26] quan tâm đến các bài toán tính toán lõi và rút

gọn, hoặc các công trình [15, 16, 17, 25, 31, 32] nghiên cứu tìm kiếm các ràng buộc

trong dữ liệu.

Lý thuyết tập thô cho phép trình diễn một mô hình hình thức về tri thức từ

bảng dữ liệu đơn thuần. Mô hình này được xác định như họ các mối quan hệ "không

phân biệt được", nhờ đó tri thức được định nghĩa một cách rõ ràng dưới dạng toán

học và có thể được phân tích và xử lý bằng những công cụ mạnh mẽ và hiệu quả

của toán học.

Trong lý thuyết tập thô, mô hình biểu diễn dữ liệu được trình bày thông qua hệ

thông tin hay bảng quyết định và ý tưởng chính trong việc phân tích dữ liệu xuất

phát từ khái niệm "không phân biệt được". Với cách tiếp cận như vậy, lý thuyết tập

thô cho phép phát hiện tri thức từ những bảng dữ liệu lớn với dữ liệu đa dạng, phức

Tri thức được biểu diễn dưới dạng các mẫu mô tả mối quan hệ bị che dấu trong

dữ liệu. Trong lý thuyết tập thô, chất lượng của thông tin được đo thông qua các

khái niệm xấp xỉ trên và xấp xỉ dưới. Nhằm thu hẹp nhiều nhất kích thước dữ liệu

đến miền thông tin chính xác, ý tưởng rút gọn được sử dụng để cho phép loại bỏ

những thông tin dư thừa, không cần thiết mà vẫn giữ được các tính chất xấp xỉ

cơ bản của hệ thống. Nếu tìm được những quy luật chung nhất biểu diễn dữ liệu,

người ta có thể tính toán độ mạnh của các thuộc tính hoặc độ phụ thuộc giữa chúng

trong hệ thông tin. Vì vâỵ vấn đề phát hiện luật theo tiếp cận tập thô được đặt ra

là hoàn toàn tự nhiên.

Mục tiêu của đề tài luận án là nghiên cứu khía cạnh đại số và logic của bài

toán phát hiện luật theo tiếp cận tập thô. Đây là một hướng nghiên cứu rất rộng,

bao gồm nhiều vấn đề đang được các nhà khoa học nghiên cứu xem xét. Luận án

tạp, chưa tinh lọc nhằm phát hiện ra những quy luật tiềm ẩn từ khối dữ liệu này.

chỉ tập trung vào hai vấn đề, một là tìm các tập rút gọn của bảng quyết định, hai

là vấn đề phát hiện các mối ràng buộc có trong dữ liệu. Cả hai vấn đề này đều được

phân tích và xem xét dựa vào các công cụ của lý thuyết tập thô mà nền tảng là

quan hệ "không phân biệt được".

Với mục tiêu đó, nội dung luận án được trình bày trong ba chương. Chương

Một trình bày một cách tổng quan về các khái niệm cơ bản trong lý thuyết tập thô

như là hệ thống thông tin, quan hệ không phân biệt được, xấp xỉ dưới, xấp xỉ trên,

bảng quyết định, rút gọn, lõi, ma trận phân biệt được. Các khái niệm liên quan tới

xấp xỉ cũng được giới thiệu sơ bộ trong chương này như hàm thành viên thô, phụ

thuộc hàm xấp xỉ, rút gọn xấp xỉ.

Chương Hai trình bày các thuật toán tìm tập rút gọn của bảng quyết định.

Các thuật toán này được chia làm hai nhóm. Nhóm thứ nhất bao gồm hai thuật

toán (Thuật toán 2.2 và Thuật toán 2.3) dựa vào khái niệm độ phụ thuộc của tập

thuộc tính quyết định vào tập con các thuộc tính điều kiện; và với khái niệm mới

này, chúng tôi đã đưa ra đánh giá về khả năng đóng góp của một thuộc tính khi

tham gia đóng vai trò thành viên của tập rút gọn. Nhóm thứ hai chỉ bao gồm một

phân biệt được, tuy nhiên ở đây, các phần tử của ma trận (là các tập hợp) không

hề được tính toán. Thay vào đó, chúng tôi phân tích các đối tượng có giá trị quyết

định khác nhau có mối tương quan như thế nào đối với các giá trị trên tập thuộc

tính điều kiện. Trên cơ sở đó, chúng tôi đã đưa ra tiêu chuẩn của tập rút gọn dựa

vào số cặp đối tượng phân biệt được bởi một tập các thuộc tính. Cả ba thuật toán

được xây dựng trong chương này đều là các thuật toán heuristic và có độ phức tạp

tính toán theo thời gian là đa thức, do đó có thể áp dụng được trên bảng dữ liệu

với kích thước lớn.

Nội dung của Chương Ba tập trung vào vấn đề thứ hai liên quan tới khái niệm

phụ thuộc trong lý thuyết cơ sở dữ liệu quan hệ. Cụ thể là, trong chương này chúng

tôi khảo sát các phụ thuộc hàm và phụ thuộc đa trị tiềm ẩn trong bảng dữ liệu có

thuật toán (Thuật toán 2.4) tìm tập rút gọn dựa theo ý tưởng xây dựng ma trận

sẵn. Để kiểm chứng phụ thuộc đa trị đúng trên tập các đối tượng, chúng tôi đã mô

tả đặc trưng của phụ thuộc đa trị bằng một họ các ma trận phụ thuộc. Do dữ liệu

trong thực tế thường rất lớn và có thể bị nhiễu, nên các phụ thuộc đúng tiềm ẩn

trong dữ liệu có thể khó phát hiện. Vì vậy chúng tôi đã nghiên cứu các phụ thuộc đa

trị đúng trên hầu hết các đối tượng trong bảng, gọi là phụ thuộc xấp xỉ, đồng thời

ma trận phụ thuộc. Phần cuối của Chương Ba, chúng tôi xây dựng các phụ thuộc

đưa ra đánh giá về sai số của phụ thuộc dựa vào khái niệm độ dầy đặc của họ các

hàm và phụ thuộc đa trị mở rộng bằng cách thay quan hệ bằng nhau trên các giá

trị thuộc tính bởi quan hệ tương tự. Một điều khá thú vị là các phụ thuộc mở rộng

này cũng được đặc trưng bởi họ các ma trận phụ thuộc tương ứng.

Chương Chương 1.

CÁC KHÁI NIỆM CƠ BẢN

1.1. Giới thiệu

Ngay từ khi xuất hiện, lý thuyết tập thô do Zdzisaw Pawlak [24] khởi xướng

vào những năm đầu thập niên tám mươi của thế kỷ hai mươi đã ngay lập tức thu

hút sự quan tâm của nhiều nhà nghiên cứu và thực nghiệm trên toàn thế giới. Khả

năng ứng dụng trong nhiều lĩnh vực khác nhau cho thấy vai trò quan trọng của lý

thuyết này trong việc nghiên cứu và ứng dụng công nghệ thông tin trong thời đại

mới.

Lý thuyết tập thô có thể được xem xét theo hai phương diện là mô hình và thực

hành. Theo phương diện mô hình, lý thuyết tập thô cho một cách tiếp cận mới cho

tính mơ hồ. Các khái niệm mơ hồ được đặc trưng bởi một "miền biên" chứa tất cả

các phần tử mà không thể gộp vào miền các đối tượng quan sát hoặc phần bù của

miền này. Lý thuyết tập thô được nghiên cứu và phát triển nhằm hiểu tốt hơn ý

tưởng của tính mơ hồ. Nó cũng xét đến một vài ý tưởng của Gottfried Leibniz (tính

(các logic đa trị) và Thomas Bayes (suy luận quy nạp). Về phương diện thực hành,

không phân biệt được), George Boole (các phương pháp suy luận), Jan Lukasiewicz

lý thuyết tập thô là ý tưởng nền tảng cho trí tuệ nhân tạo và khoa học nhận thức,

đặc biệt cho học máy, phát hiện tri thức, phân tích quyết định, suy luận quy nạp

và nhận dạng mẫu. Nó là rất quan trọng cho các nghiên cứu về hệ trợ giúp quyết

định và khai phá dữ liệu. Thực tế tiếp cận lý thuyết tập thô là một cách tiếp cận

mới cho việc phân tích dữ liệu.

Bản chất toán học chặt chẽ làm cho các nội dung cơ sở của lý thuyết tập thô có

thể được nắm bắt và ứng dụng một cách dễ dàng. Các hệ thống phần mềm sử dụng

lý thuyết tập thô (điển hình như ROSETTA) đã được cài đặt và nhiều ứng dụng

quan trọng trong đời sống của phương pháp luận này đã được xây dựng, chẳng hạn

Bản chất toán học chặt chẽ làm cho lý thuyết này không mâu thuẫn mà còn

bổ sung cho các phương pháp đã có và dĩ nhiên cũng có thể được sử dụng đồng thời

với các cách tiếp cận khác.

Mục đích chính của sự phân tích tập thô là đưa ra các tập xấp xỉ để biểu diễn

các đối tượng không thể được phân lớp một cách chắc chắn bằng cách dùng tri thức

có sẵn. Theo cách tiếp cận của lý thuyết tập thô, mọi tập thô được liên kết với hai

tập "rõ" là xấp xỉ dưới và xấp xỉ trên của nó. Xấp xỉ dưới bao gồm các đối tượng

chắc chắn thuộc, còn xấp xỉ trên chứa tất cả các đối tượng có khả năng thuộc về

tập đó. Các tập xấp xỉ là cơ sở để đưa ra các kết luận từ dữ liệu.

1.2. Hệ thống thông tin và tập thô

1.2.1. Hệ thống thông tin

trong y học, dược học, kỹ thuật, ngân hàng, nhận dạng mẫu, biểu thị gien v.v...

Hệ thống thông tin là một cặp A = (U , A), với U là tập hữu hạn, khác rỗng,

được gọi là tập vũ trụ các đối tượng và A là tập hữu hạn khác rỗng các thuộc tính.

Với mỗi u ∈ U và a ∈ A, ta ký hiệu u(a) là giá trị của đối tượng u tại thuộc tính a.

Nếu gọi Ia là tập tất cả các gía trị của thuộc tính a, thì u(a) ∈ Ia với mọi u ∈ U .

Bây giờ, nếu B = {b1, b2, · · · , bk} ⊆ A là một tập con các thuộc tính thì ta sẽ ký

hiệu bộ các giá trị u(bi) bởi u(B). Như vậy, nếu u và v là hai đối tượng, thì ta sẽ

1.2.2. Quan hệ không phân biệt được

viết u(B) = v(B) nếu u(bi) = v(bi), với mọi i = 1, · · · , k.

Cho hệ thống thông tin A = (U, A). Với mỗi tập con các thuộc tính B ⊆ A,

tồn tại một quan hệ hai ngôi trên U , ký hiệu IND(B), xác định bởi:

IND(B) = {(u, v) ∈ U × U | u(B) = v(B)}.

IND(B) được gọi là quan hệ B−không phân biệt được. Dễ kiểm chứng được rằng

hệ tương đương trên V , cảm sinh bởi IND(B), tức là:

IND(B|V ) = {(u, v) ∈ V × V | u(B) = v(B)}.

Nếu (u, v) ∈ IND(B) thì hai đối tượng u và v không phân biệt được bởi các

thuộc tính trong B. Lớp tương đương chứa phần tử u được ký hiệu [u]B. Khi đó

quan hệ IND(B) được xác định hoàn toàn bởi các lớp tương đương [u]B, u ∈ U . Tập

hợp thương của quan hệ IND(B) được ký hiệu [IND(B)] hay đơn giản là U/B, tức

là [IND(B)] = U/B = {[u]B | u ∈ U } và tập hợp thương của quan hệ IND(B|V ) là

[IND(B|V )] hay V /B.

Ví dụ 1.1. Xét tập 10 đồ chơi với các thuộc tính: Màu sắc, Kích thước, Hình dáng

được cho trong Bảng 1.1. Lúc đó

đây là một quan hệ tương đương trên U . Với V ⊆ U , ta ký hiệu IND(B|V ) là quan

U /{Màu sắc} = {{u1, u2, u6, u10}, {u3, u5, u9}, {u4, u7, u8}}

U /{Kích thước} = {{u1, u5, u8, u9}, {u3, u4, u10}, {u2, u6, u7}}

U /{Hình dáng} = {{u1, u2, u6, u10}, {u3, u4, u9}, {u5, u7, u8}}

U /{Màu sắc, Hình dáng} = {{u1, u2, u6, u10}, {u3, u9}, {u4}, {u5}, {u7, u8}}

Như vậy các đồ chơi u1, u2 không phân biệt được về màu sắc và hình dáng,

nhưng phân biệt được về kích thước. Tương tự, các đồ chơi u3, u4 không phân biệt

nhau về kích thước và hình dáng, nhưng phân biệt được về màu sắc, v.v...

U Màu sắc Kích thước Hình dáng

To Tròn Xanh u1

Nhỏ Tròn Xanh u2

Vừa Vuông Vàng u3

Vừa Vuông Đỏ u4

To Tam giác Vàng u5

Nhỏ Tròn Xanh u6

Nhỏ Tam giác Đỏ u7

Vuông

Vàng

Vừa

Tròn

Xanh

u10

Bảng 1.1: Bảng dữ liệu các đồ chơi.

1.2.3. Các tập xấp xỉ

Cho hệ thống thông tin A = (U, A), B ⊆ A và V ⊆ U . Với các tri thức được

cho bởi tập thuộc tính B, liệu chúng ta có thể biểu diễn tập đối tượng V bằng các

tri thức có sẵn này hay không? Hay nói cách khác, với một tập thuộc tính B cho

trước, chúng ta có các lớp tương đương của quan hệ IND(B), thế thì một tập đối

tượng V có thể diễn đạt thông qua các lớp tương đương này như thế nào? Trong lý

To Tam giác Đỏ u8

thuyết tập thô, để biểu diễn V bằng tri thức có sẵn B người ta xấp xỉ chúng bởi

hợp của một số hữu hạn các lớp tương đương của IND(B). Có hai cách xấp xỉ: Cách

thứ nhất là cho tương ứng bởi "miền trong" và cách thứ hai có thể xấp xỉ bởi "bao

đóng" của V . Hai giá trị xấp xỉ này được gọi tương ứng là B−xấp xỉ dưới và B−xấp

xỉ trên của V , ký hiệu lần lượt là BV và BV , cụ thể các tập xấp xỉ này được xác

định như sau

BV = {u ∈ U | [u]B ⊆ V },

BV = {u ∈ U | [u]B ∩ V 6= ∅}.

Với các xấp xỉ trên, ta gọi B−miền biên của V là tập BNB(V ) = BV \ BV

và B−miền ngòai của V là tập U \ BV . Dễ thấy B−miền biên của V là tập chứa

các đối tượng không chắc chắn thuộc hay không thuộc V , còn B−miền ngòai của V

chứa các đối tượng chắc chắn không thuộc V . Với ký hiệu tập thương của quan hệ

tương đương IND(B) trên U là U/B, các xấp xỉ trên và dưới của V có thể viết lại:

BV = ∪{W ∈ U/B | W ⊆ V },

Bây giờ nếu B, D ⊆ A, ta sẽ gọi B−miền khẳng định của D là tập được xác

định như sau

BV = ∪{W ∈ U/B | W ∩ V 6= ∅}.

(BV ).

POSB(D) =

V ∈U/D

Rõ ràng POSB(D) là tập tất cả đối tượng u sao cho với mọi v ∈ U mà u(B) =

v(B) ta đều có u(D) = v(D). Nói cách khác, POSB(D) = {u ∈ U | [u]B ⊆ [u]D}.

Ví dụ 1.2. Xét hệ thống thông tin biểu diễn các triệu chứng cúm của các bệnh

nhân cho ở Bảng 1.2.

U Đau đầu Thân nhiệt Cảm cúm

Bình thường

Không

Có

Cao

Có

[

Có Rất cao Có u3

Không Bình thường Không u4

Không Cao Không u5

Không Rất cao Có u6

Không Cao Có u7

Không Rất cao Không u8

Bảng 1.2: Các triệu chứng của bệnh nhân.

Các lớp không phân biệt được bởi B = {Đau đầu, Thân nhiệt } là: {u1}, {u2}, {u3},

{u4}, {u5, u7}, {u6, u8}. Đặt V = {u | u(Cảm cúm) = Có} = {u2, u3, u6, u7}. Lúc

đó,

BV = {u2, u3} và BV = {u2, u3, u6, u7, u5, u8}. Như vậy, B−miền biên của V

là tập hợp BNB(V ) = {u5, u6, u7, u8}. Nếu đặt D = {Cảm cúm} thì

U/D = {V1 = {u1, u4, u5, u8} ; V2 = {u2, u3, u6, u7}},

[

BV1 = {u1, u4} ; BV2 = {u2, u3},

V ∈U/D

1.2.4. Các tính chất của xấp xỉ

Định lý 1.1. [24] Cho V ⊆ U và B ⊆ A. Khi đó:

a) BV ⊆ V ⊆ BV.

b) B∅ = B∅ = ∅, BU = BU = U.

c) B(V ∪ W ) = BV ∪ BW.

d) B(V ∪ W ) ⊇ BV ∪ BW.

e) V ⊆ W ⇒ BV ⊆ BW và BV ⊆ BW.

(BV ) = {u1, u2, u3, u4}. POSB(D) =

f) B(V ∩ W ) = BV ∩ BW.

g) B(V ∩ W ) ⊆ BV ∩ BW.

h) B(U \ V ) = U \ BV.

i) B(U \ V ) = U \ BV.

j) B(BV ) = B(BV ) = BV.

k) B(BV ) = B(B(V ) = BV.

Với các khái niệm của tập xấp xỉ đối với phân hoạch IND(B), các tập thô được

chia thành bốn lớp cơ bản:

1) Tập V là B−xác định thô nếu BV 6= ∅ và BV 6= U.

2) Tập V là B−không xác định trong nếu BV = ∅ và BV 6= U.

3) Tập V là B−không xác định ngòai nếu BV 6= ∅ và BV = U.

1.2.5. Độ chính xác của xấp xỉ

Với mỗi B ⊆ A và V ⊆ U , đại lượng đo lường sự chính xác của xấp xỉ tập V

đối với phân hoạch trên B là giá trị

αB(V ) =

Card(BV ) Card(BV )

Rõ ràng 0 ≤ αB(V ) ≤ 1. Nếu αB(V ) = 1, ta nói V là chính xác đối với B, còn

nếu αB(V ) < 1, V được gọi là thô đối với B.

1.3. Bảng quyết định

4) Tập V là B− không xác định hoàn tòan nếu BV = ∅ và BV = U.

Một lớp đặc biệt của các hệ thống thông tin có vai trò quan trọng trong nhiều

ứng dụng là bảng quyết định. Bảng quyết định là một hệ thống thông tin T với tập

thuộc tính A được chia thành hai tập khác rỗng rời nhau C và D, lần lượt được gọi

là tập thuộc tính điều kiện và tập thuộc tính quyết định. Tức là T = (U, C ∪ D) với

C ∩ D = ∅. Trong trường hợp không sợ bị nhầm lẫn, người ta ký hiệu T = (C, D).

Bảng quyết định là mô hình thường gặp trong thực tế, khi mà giá trị dữ liệu tại

các thuộc tính điều kiện có thể cung cấp cho ta thông tin về giá trị của thuộc tính

quyết định. Bảng quyết định được gọi là nhất quán nếu D phụ thuộc hàm vào C,

tức là với mọi u, v ∈ U , u(C) = v(C) kéo theo u(D) = v(D). Ngược lại thì gọi là

không nhất quán hay mâu thuẫn.

Dễ thấy bảng quyết định là nhất quán khi và chỉ khi POSC(D) = U . Trong

trường hợp bảng không nhất quán thì POSC(D) chính là tập hợp con cực đại của

1.3.1. Rút gọn và lõi

U sao cho phụ thuộc hàm C → D đúng.

Thuộc tính lõi, thuộc tính rút gọn và thuộc tính không cần thiết. Thuộc tính lõi là

thuộc tính cốt yếu, không thể thiếu trong việc phân hoạch chính xác tập dữ liệu.

Thuộc tính không cần thiết là những thuộc tính dư thừa; nghĩa là có thể loại bỏ

một thuộc tính như vậy (không phải tất cả!) mà không ảnh hưởng đến việc phân

lớp dữ liệu. Thuộc tính của tập rút gọn nằm giữa hai tập thuộc tính trên, với một

tổ hợp thuộc tính nào đó, nó là thuộc tính dư thừa và với một tổ hợp các thuộc tính

khác nó có thể là cốt yếu.

Chúng ta sẽ đưa ra các định nghĩa chính xác trong phần tiếp theo.

Cho T = (U, C ∪D) là một bảng quyết định, thuộc tính c ∈ C được gọi là không cần thiết trong bảng quyết định T nếu POSC(D) = POS(C\{c})(D). Nói cách khác,

c ∈ C là không cần thiết khi và chỉ khi trên POSC(D) phụ thuộc hàm C \ {c} → D

Trong bảng quyết định, các thuộc tính điều kiện được phân thành ba nhóm:

nghiệm đúng; ngược lại, c được gọi là cần thiết.

Bảng quyết định T được gọi là độc lập nếu mọi thuộc tính c ∈ C đều cần thiết.

Tập tất cả các thuộc tính cần thiết trong T được gọi là lõi và được ký hiệu Core(C).

Lúc đó, một thuộc tính cần thiết còn được gọi là thuộc tính lõi.

Tập các thuộc tính R ⊆ C được gọi là một rút gọn của tập thuộc tính điều kiện C nếu T0 = (U, R ∪ D) là độc lập và POSR(D) = POSC(D). Nói cách khác, R

là tập rút gọn nếu nó là tập tối tiểu thỏa mãn POSR(D) = POSC(D). Rõ ràng là

có thể có nhiều tập rút gọn của C. Ta ký hiệu Red(C) là tập tất cả các rút gọn của

C trong T. Một thuộc tính là cần thiết khi và chỉ khi nó thuộc vào mọi tập rút gọn

của C. Điều đó được thể hiện trong mệnh đề sau.

R∈ Red(C)

Mệnh đề 1.2. [11, 26, 28] Core(C) = R.

Ví dụ 1.3. Xét bảng quyết định về bệnh cúm cho ở Bảng 1.3. Bảng này có hai

tập rút gọn là R1 ={Đau cơ, Thân nhiệt} và R2= {Đau đầu, Thân nhiệt}. Như vậy

tập lõi là Core= {Thân nhiệt} và Thân nhiệt là thuộc tính cần thiết duy nhất. Các

thuộc tính Đau đầu, Đau cơ đều không cần thiết theo nghĩa là, từ bảng dữ liệu, có

POS{Đau cơ, Thân nhiệt}({Cảm cúm}) = POSC({Cảm cúm}),

POS{ Đau đầu, Thân nhiệt}({Cảm cúm}) = POSC({Cảm cúm}).

U Đau đầu Đau cơ Thân nhiệt Cảm cúm

Có

Bình thường

Không

Có

Cao

Có

Rất cao

Có

Không

Bình thường

Không

Cao

Không

Có

Rất cao

Có

thể loại bỏ một trong hai thuộc tính này mà vẫn chẩn đoán đúng bệnh. Tức là

1.3.2. Ma trận và hàm phân biệt được

Bảng 1.3: Bảng quyết định về bệnh cúm.

Xét bảng quyết đinh T = (U, C ∪ D) với U = {u1, u2, · · · , un}. Ma trận phân biệt được của T, ký hiệu M (T) = (mij)n×n, là một ma trận đối xứng mà mỗi phần

U Đau cơ Thân nhiệt Cảm cúm

Có

Cao

Có

Rất cao

Có

u3, u6 Có

Không Cao

Không

Bảng 1.4: Bảng rút gọn thứ nhất của hệ thống bệnh cúm (R1).

U Đau đầu Thân nhiệt

Cảm cúm

Bình thường Không

u1 Có

Cao

Có

u2 Có

Rất cao

Có

u3 Có

Bình thường Không

u4 Không

Cao

Không

u5 Không

Rất cao

Có

u6 Không

Bình thường Không u1, u4 Có

Bảng 1.5: Bảng rút gọn thứ hai của hệ thống bệnh cúm (R2).

d U c1 c2 c3 c4

0 2 1 1 1 u1

0 2 1 0 1 u2

2 0 2 0 1 u3

2 2 0 1 1 u4

1 0 2 0 2 u5

1 1 2 0 2 u6

1 2 1 1 2 u7

tử của nó là một tập hợp các thuộc tính được xác định như sau [24, 26, 27, 28]

nếu ui(D) = uj(D),

Bảng 1.6: Dữ liệu bảng quyết định.

mij =

  ∅

{c ∈ C | ui(c) 6= uj(c)} nếu ui(D) 6= uj(D).

Như vậy, mij là tập hợp gồm tất cả thuộc tính điều kiện có thể xếp các đối tượng

ui và uj vào các lớp tương đương khác nhau đối với quan hệ không phân biệt được

trên mỗi thuộc tính của tập thuộc tính này. Hay nói cách khác hai đối tượng ui và

uj mà ui(D) 6= uj(D) có thể phân biệt với nhau bởi một thuộc tính bất kỳ trong tập

mij. Nếu mij = ∅ thì ui và uj bằng nhau trên tập thuộc tính D hoặc, trong trường

hợp bảng quyết định đã cho là không nhất quán, hai đối tượng ui và uj có cùng giá



trị trên tập thuộc tính điều kiện nhưng khác nhau trên tập thuộc tính quyết định.

Ví dụ 1.4. Cho bảng quyết định như trong Bảng 1.6 với tập thuộc tính điều kiện

C = {c1, c2, c3, c4} và tập thuộc tính quyết định D = {d}. Ta có ma trận phân biệt

được tương ứng cho trong Bảng 1.7. Chú ý rằng, đây là ma trận đối xứng nên chúng

ta chỉ trình bày ma trận tam giác dưới.

Do bảng quyết định trong ví dụ này là nhất quán, nên m12 = ∅ trong Bảng 1.7

cho thấy hai đối tượng u1 và u2 có cùng giá trị quyết định (u1(d) = u2(d) = 1) hay

U u4 u5 u6 u7 u1 u2 u3

∅ u1

∅ ∅ u2

∅ {c2, c3, c4} {c2, c3} u3

∅ {c2} {c2, c4} u4 {c3, c4}

∅ ∅ {c1, c2, c3, c4} {c1, c2, c3} u5 {c1, c2, c3, c4}

∅ ∅ ∅ {c1, c2, c3, c4} {c1, c2, c3} u6 {c1, c2, c3, c4}

Bảng 1.7: Ma trận phân biệt được M.

nói cách khác u1 và u2 cùng thuộc một lớp tương đương của phân hoạch IND(D).

Trong khi đó m32 = {c2, c3}, điều này nói lên rằng hai đối tượng u2 và u3 có

giá trị quyết định khác nhau và chúng có thể phân biệt với nhau bởi các thuộc

tính c2 hoặc c3 nhưng không phân biệt được bởi các thuộc tính c1, c4. Thật vậy,

u2(d) = 1 6= 2 = u3(d) và u2(c2) = 0 6= 2 = u3(c2), u2(c3) = 2 6= 0 = u3(c3),

u2(c1) = u3(c1) = 1, u2(c4) = u3(c4) = 0.

Để tìm tập rút gọn dựa vào ma trận phân biệt được, người ta đưa vào khái

niệm hàm phân biệt được fT [18, 27] được xác định như sau

∅ ∅ ∅ u7 {c1, c2, c3, c4} {c1, c2} {c3, c4} {c3, c4}

fT(ui) =

mij , với mỗi ui ∈ U ,

j6=i

^ _

trong đó, mỗi thuộc tính cho tương ứng một biến logic cùng tên và

(1) W mij là biểu thức tuyển của tất cả các biến c ∈ mij, nếu mij 6= ∅.

(2) W mij = true nếu mij = ∅ và ui(D) = uj(D).

(3) W mij = f alse nếu mij = ∅ và ui(D) 6= uj(D).

Như vậy fT(ui) chứa những bộ thuộc tính có thể phân biệt ui với các đối tượng khác trong T. Do đó, V fT(ui) sẽ xác định tất cả các rút gọn của bảng quyết định.

Trong ví dụ trên ta có

j6=1

W m12 = T rue;

W m13 = c2 ∨ c3 ∨ c4;

W m14 = c2;

W m15 = c1 ∨ c2 ∨ c3 ∨ c4;

W m16 = c1 ∨ c2 ∨ c3 ∨ c4;

W m17 = T rue. Vì vậy,

fT(u1) = m1j, trong đó

T rue

(c1 ∨ c2 ∨ c3 ∨ c4)

fT(u1) = T rue

(c2 ∨ c3 ∨ c4) ^ ^

(c1 ∨ c2 ∨ c3 ∨ c4)

= (c2 ∨ c3 ∨ c4)

= c2.

Tính toán tương tự ta có

fT(u2) = c2

^ ^ ^ ^ ^

fT(u3) = c3

W(c3 ∧ c4),

fT(u4) = (c2 ∧ c3) W(c2 ∧ c4),

fT(u5) = c3

W(c2 ∧ c4),

fT(u6) = c3

W(c1 ∧ c4) W(c2 ∧ c4),

fT(u7) = (c1 ∧ c3) W(c1 ∧ c4) W(c2 ∧ c3) W(c2 ∧ c4), ^ fT(ui) = (c2 ∧ c3) (c2 ∧ c4).

Từ đây chúng ta nhận được hai tập rút gọn của bảng quyết định trên là R1 =

{c2, c3}; R2 = {c2, c4} và tập lõi là Core = {c2}.

1.3.3. Luật quyết định

Một công cụ cũng thường được sử dụng để nghiên cứu bảng quyết định là luật

quyết định. Cụ thể, cho T = (U, C ∪ D) là một bảng quyết định, với mỗi u ∈ U ,

chúng ta cho tương ứng một hàm du : C ∪ D → V xác định bởi du(a) = u(a), với mỗi a ∈ C ∪ D. Hàm du được gọi là một luật quyết định (trong T) và u được xem

như là nhãn của luật quyết định đó [20].

Nếu du là một luật quyết định thì thu hẹp của du trên C, ký hiệu du|C, và thu

luật du.

Rõ ràng, bảng quyết định T là nhất quán khi và chỉ khi, với mọi cặp đối tượng

u 6= v, du|C = dv|C kéo theo du|D = dv|D.

Ví dụ 1.5. Xét bảng quyết định chọn các ứng cử viên vào ngạch giảng viên của

một trường đại học dựa vào các thông tin của họ với các thuộc tính điều kiện: c1

(Trình độ chuyên môn), c2 (Yêu thích nghề giảng viên), c3 (Khả năng giảng dạy) và

thuộc tính quyết định d được cho trong Bảng 1.8.

Các luật quyết định có thể có:

du1: Trình độ chuyên môn Tốt, Yêu nghề Có, Khả năng giảng dạy Có thể thì

có được quyết định Chấp nhận

du2: Trình độ chuyên môn Trung bình, Yêu nghề Có, Khả năng giảng dạy

hẹp của du trên D, ký hiệu du|D, được gọi tương ứng là điều kiện và quyết định của

Bình thường thì có được quyết định Có thể Chấp nhận

· · ·

du9: Trình độ chuyên môn Tốt, Yêu nghề Không, Khả năng giảng dạy Không

thể thì có được quyết định Có thể Từ chối

Dễ thấy bảng quyết định trên là không nhất quán vì có hai đối tượng u1 và u4

có du1|C = du4|C nhưng du1|D 6= du4|D.

Từ định nghĩa ta thấy ngay rằng một bảng quyết định có thể được đặc trưng

d U c3 c2 c1

Có thể Chấp nhận Có u1 Tốt

Bình thường Có thể chấp nhận u2 Trung bình Có

Không Bình thường Từ chối u3 Kém

Có Có thể Có thể chấp nhận u4 Tốt

Có thể từ chối u5 Trung bình Không Không thể

Có Bình thường Chấp nhận u6 Xuất sắc

Có Không thể Có thể từ chối u7 Xuất sắc

Không Không thể

Có thể từ chối

u9 Tốt

Bảng 1.8: Bảng chọn ứng cử viên vào ngạch giảng dạy.

hoàn toàn bởi hệ các luật quyết định của nó. Tuy vậy, các bảng quyết định trong

thực tế thường lưu trữ một khối lượng lớn các đối tượng, và do đó hệ luật quyết

định tương ứng cũng sẽ rất lớn. Vấn đề đặt ra là làm thế nào có thể đặc trưng được

bảng quyết định bằng một hệ con các luật quyết định. Việc rút gọn dữ liệu, tức

là tìm tập rút gọn của tập thuộc tính điều kịên chính là một trong những cách để

giải quyết vấn đề này. Các đối tượng trong cùng một lớp tương đương của quan hệ

IND(R), với R là một rút gọn của tập thuộc tính điều kiện C sẽ có cùng quyết định

như nhau. Vì vậy, chúng ta chỉ sử dụng các luật du, tương ứng với các đối tượng u thoả mãn [u]R ∈ IND(R), là đủ để quan sát bảng quyết định T.

1.4. Phụ thuộc xấp xỉ

1.4.1. Hàm thành viên thô

Không Không thể Từ chối u8 Kém

Cho hệ thống thông tin A = (U, A), tập con các thuộc tính B ⊆ A và tập con

các đối tượng V ⊆ U . Với mỗi đối tượng u ∈ U , người ta cần xác định mức độ giao

nhau giữa lớp tương đương chứa u trong phân hoạch IND(B) với V . Giá trị này

V (u) và được định

được gọi là giá trị của hàm thành viên thô của V tại u, ký hiệu µB

nghĩa như sau

; ∀u ∈ U. µB V (u) = µB V : U → [0, 1], Card([u]B ∩ V ) Card([u]B)

Hàm thành viên thô có thể được giải thích như là xác suất có điều kiện của đối

tượng u thuộc vào tập V khi các thông tin của đối tượng u liên quan đến tập thuộc

Một cách hình thức, người ta có thể mở rộng các khái niệm xấp xỉ trên và xấp

xỉ dưới tương ứng với một độ chính xác α ∈ (0.5, 1] bằng cách sử dụng hàm thành

viên thô:

BαV = {u ∈ U | µB

V (u) ≥ α},

BαV = {u ∈ U | µB

V (u) > 1 − α}.

Rõ ràng các khái niệm xấp xỉ trên và xấp xỉ dưới nguyên thủy là trường hợp

đặc biệt của định nghĩa này ứng với giá trị α = 1.

1.4.2. Phụ thuộc hàm xấp xỉ

Dữ liệu trong thực tế thường rất lớn và đa dạng, vì vậy, để nắm bắt được các

tính B đã biết. Hàm này cũng phản ảnh độ chắc chắn của quan hệ u ∈ V.

quy luật biến đổi trong dữ liệu, chúng ta thường phải phân tích một cách tường

tận quan hệ giữa các dữ liệu với nhau. Một trong những quan hệ đóng vai trò quan

trọng cho bài toán khai phá dữ liệu là sự phụ thuộc giữa các thuộc tính của dữ liệu.

Trong phần này chúng ta sẽ đề cập đến sự phụ thuộc này một cách tổng quát.

Cho X và Y là các tập con của tập thuộc tính của A. Ta nói rằng độ phụ thuộc

của Y vào X là k và ký hiệu X →k Y , nếu:

k = γ(X, Y ) := Card(POSX(Y )) Card(U )

Hay

V ∈ U/Y

k = Card(X(V )) Card(U )

Khi k < 1, ta nói rằng Y phụ thuộc một phần vào X (với độ phụ thuộc k). Khi

k = 1, Y được gọi là phụ thuộc hoàn toàn vào X, và ký hiệu đơn giản X → Y . Rõ

ràng, Y phụ thuộc hoàn toàn vào X nếu phụ thuộc hàm X xác định Y đúng trên

bảng dữ liệu đã cho, tức là, với mọi cặp đối tượng u, v ∈ U, u(X) = v(X) suy ra

u(Y ) = v(Y ). Vì vậy trong trường hợp k < 1, chúng ta cũng nói rằng tồn tại phụ

Ví dụ 1.6. Xét hệ thống thông tin với tập thuộc tính A = {a, b, c} và U gồm chín

đối tượng cho bởi Bảng 1.9.

a b

thuộc hàm xấp xỉ X xác định Y trên U với sai số (cid:15) = 1 − k.

3 2 2 u9

Bảng 1.9: Bảng dữ liệu.

Đặt X = {a, b}; Y = {c}; Z = {b}. Ta có:

U/X = {{u1}, {u2}, {u3}, {u4}, {u5}, {u6}, {u7}, {u8}, {u9}}

U/Y = {V1, V2, V3}; V1 = {u1, u3}; V2 = {u2, u4, u9}; V3 = {u5, u6, u7, u8};

U/Z = {W1, W2, W3}; W1 = {u1, u3, u6}; W2 = {u2, u4, u9}; W3 = {u5, u7, u8}.

Vì XV1 = V1, XV2 = V2, XV3 = V3, nên γ(X, Y ) = 1, và do đó, Y phụ thuộc

hòan tòan vào X.

Tính toán tương tự, ta được ZV1 = ∅; ZV2 = {u2, u4, u9} và ZV3 = {u5, u7, u8}.

Từ đó suy ra γ(Z, Y ) = = hay Y phụ thuộc vào Z với độ phụ thuộc là . 6 9 2 3 2 3

Định lý sau cho ta mối quan hệ giữa tính chất của phụ thuộc với các tập xấp

xỉ

a) X → Y .

b) U/(X ∪ Y ) = U/X.

c) POSX(Y ) = U .

d) XV = V, với mọi V ∈ U/Y .

Chứng minh.

(a ⇒ b) Với mỗi V ∈ U/(X ∪ Y ), tồn tại W ∈ U/X sao cho V ⊆ W . Ta sẽ

chứng minh W = V . Thật vậy, giả sử tồn tại u ∈ W và u 6∈ V . Lấy v ∈ V ⇒ v ∈

W ⇒ u(X) = v(X). Vì X → Y nên u(Y ) = v(Y ) suy ra u(X ∪ Y ) = v(X ∪ Y ) :

vô lý vì u 6∈ V . Vậy V = W ∈ U/X. Vì điều này đúng với mọi V ∈ U/(X ∪ Y ) nên

Định lý 1.3. [24] Những mệnh đề sau là tương đương

U/(X ∪ Y ) = U/X.

(b ⇒ c) Rõ ràng POSX(Y ) ⊆ U . Vì vậy chỉ cần chứng minh U ⊆ POSX(Y ).

Với mỗi u ∈ U , đặt V = [u]Y ⊇ [u]X∪Y = [u]X suy ra [u]X ⊆ XV ⊆ POSX(Y ) hay

u ∈ POSX(Y ).

[

(c ⇒ d) Ta có XV ⊆ V . Bây giờ ta chứng minh V ⊆ XV với mọi V ∈ U/Y .

W ∈ U/Y

XW do đó tồn tại W ∈ Thật vậy, với mọi u ∈ V ⊆ U ⇒ u ∈ POSX(Y ) =

U/Y sao cho u ∈ XW . Rõ ràng V = [u]Y = W , vậy u ∈ XV. Suy ra V ⊆ XV.

(d ⇒ a) Với mọi cặp đối tượng u, v ∈ V ∈ U/X, đặt W1 = [u]Y và W2 = [v]Y .

Khi đó, XW1 = W1 và XW2 = W2. Vì u ∈ XW1 = W1 nên [u]X ⊆ W1, tương tự

[v]X ⊆ W2. Suy ra W1 = W2 hay u(Y ) = v(Y ). Vậy X → Y .

Bằng kỹ thuật chứng minh tương tự, chúng ta cũng dễ dàng kiểm chứng định

lý sau

Định lý 1.4. [24] Cho X, X 0, Y, Y 0, Z và Z 0 là các tập con các thuộc tính. Khi đó:

b) Nếu X → Y và Y 0 ⊆ Y thì X → Y 0.

c) Nếu X → Y và Y → Z thì X → Z.

d) Nếu X → Z và Y → Z thì X ∪ Y → Z.

e) Nếu X → Y ∪ Z và X → Y thì X → Z.

f) Nếu X → Y và Y ∪ Z → Z 0 thì X ∪ Z → Z 0.

g) Nếu X → Y và Z → Z 0 thì X ∪ Z → Y ∪ Z 0.

1.4.3. Rút gọn xấp xỉ

Cơ sở dữ liệu thường chứa một số thuộc tính dư thừa, là những thuộc tính

a) Nếu X → Y và X 0 ⊇ X thì X 0 → Y.

không cần thiết đối với sự khai phá luật. Sự có mặt của các thuộc tính dư thừa làm

cho độ phức tạp tính toán của bài toán khai phá luật rất lớn và số lượng luật được

phát hiện sẽ bị hạn chế.

Việc loại bỏ các thuộc tính dư thừa cũng tương đương với việc chọn những

thuộc tính nào để lại là phù hợp nhất. Đây là một trong những vấn đề quan trọng

trong học máy và nhận dạng mẫu. Nhiều chuyên gia đã giải quyết bài toán này với

những công cụ khác nhau, gần đây có một số nhà nghiên cứu đã dựa vào lý thuyết

tập thô để chọn lọc các thuộc tính, chẳng hạn như sử dụng bảng phân phối tổng

quát, rời rạc hóa dữ liệu dựa vào tập thô và lập luận xấp xỉ v.v...

Tuy nhiên dữ liệu trong thực tế thường rất lớn và đa dạng. Các dữ liệu này có

thể không chắc chắn, không đầy đủ và biến động. Vì vậy, một rút gọn đúng nghĩa

có thể tồn tại nhưng không chắc tìm được, hoặc chúng ta phải tốn rất nhiều công

sức để tìm ra được nó mà đôi khi kết quả đem lại không thực sự hữu ích. Thay vào

đó, người ta tìm một rút gọn "chấp nhận được" là một rút gọn xấp xỉ, đúng với

"phần lớn" dữ liệu có được. Với bài toán này, công sức tìm kiếm có thể sẽ giảm đi

Như phần trước đã trình bày, một rút gọn của bảng quyết định không thể thiếu

các thuộc tính lõi. Vì vậy, để tìm các rút gọn xấp xỉ người ta thường xuất phát từ

tập lõi và bổ sung dần các thuộc tính cho đến khi đạt được yêu cầu đánh giá một

rút gọn xấp xỉ. Vấn đề còn lại là chọn thuộc tính nào đây để đưa vào tập rút gọn.

Điều này dẫn đến việc cần có sự đánh giá các thuộc tính theo yêu cầu nào đó để

chọn các thuộc tính có "chất lượng" đưa vào tập rút gọn, khái niệm ý nghĩa của

thuộc tính xuất phát từ đó.

Mỗi thuộc tính được gán tương ứng với một giá trị thực trong khỏang đóng

[0,1] biểu diễn mức độ quan trọng của thuộc tính trong bảng thông tin. Trong phần

trước, chúng ta đã được biết đến độ phụ thuộc của tập thuộc tính Y vào tập thuộc

tính X là γ(X, Y ). Ở đây chúng ta cũng sẽ xét bảng quyết đinh T = (U, C ∪ D) với

nhiều, đặc biệt là khi sử dụng các thuật toán heuristic.

C là tập thuộc tính điều kiện và D là tập thuộc tính quyết định. Khi đó chúng ta

sẽ xem xét giá trị của γ(C, D) sẽ thay đổi như thế nào khi chúng ta loại bỏ một

thuộc tính trong C, nghĩa là hai hệ số γ(C, D) và γ(C \ {a}, D) sẽ khác nhau như

thế nào? Sự khác nhau đó được dùng trong biểu diễn ý nghĩa của thuộc tính a, ký

= 1 −

hiệu σ(C,D)(a) và được định nghĩa cụ thể như sau

σ(C,D)(a) = γ(C, D) − γ(C \ {a}, D) γ(C, D) γ(C \ {a}, D) γ(C, D)

Hệ số σ(C,D)(a) có thể được hiểu như là độ sai lệch giữa các phân hoạch IND(C)

và IND(C \ {a}). Hệ số ý nghĩa này có thể mở rộng đối với tập các thuộc tính

= 1 − , σ(C,D)(B) = γ(C, D) − γ(C \ B, D) γ(C, D) γ(C \ B, D) γ(C, D)

ở đây B là một tập con của C. Trong trường hợp C và D đã xác định rõ, chúng ta

ký hiệu các giá trị trên đơn giản là σ(a) và σ(B).

Nếu B là một rút gọn của C thì σ(C \ B) = 1 − = 0 điều này có nghĩa γ(B, D) γ(C, D) là các thuộc tính C \ B không có ý nghĩa, hay nói cách khác, các thuộc tính này có

Một tập con B của C được gọi là một rút gọn xấp xỉ của C với sai số (cid:15)(B) nếu:

(cid:15)(B) =

= 1 −

γ(C, D) − γ(B, D) γ(C, D)

γ(B, D) γ(C, D)

Vì (cid:15)(B) = 1 − σ(B) nên khái niệm rút gọn xấp xỉ (tương ứng miền khẳng định)

là sự tổng quát hóa của khái niệm rút gọn. Thật vậy, một tập con cực tiểu B thỏa

mãn (cid:15)(B) = 0 chính là rút gọn theo nghĩa nguyên thủy.

thể không được xét đến trong khi xây dựng các luật.

Chương Chương 2.

MỘT SỐ THUẬT TOÁN

TÌM TẬP RÚT GỌN

2.1. Mở đầu

Như đã được trình bày, phát hiện luật theo tiếp cận của lý thuyết tập thô là

một trong những phương pháp đang được nhiều nhà khoa học nghiên cứu và sử

dụng trong quá trình khai phá tri thức từ dữ liệu. Do dữ liệu thực tế thường đa

dạng, không đầy đủ, thiếu chính xác mà lại dư thừa nên việc chọn lọc thuộc tính

được đặt ra nhằm loại bỏ các thuộc tính dư thừa mà vẫn giữ được đầy đủ ý nghĩa

của tập dữ liệu đang xét. Mục tiêu của việc chọn lọc thuộc tính là tìm ra các thuộc

tính cốt yếu và cần thiết trong cơ sở dữ liệu. Dựa vào đó, việc sinh luật và phân lớp

có thể đạt hiệu quả cao nhất mà chỉ dựa vào một tập con các thuộc tính đã được

lựa chọn.

Có nhiều thuật toán tìm tập rút gọn đã được đề nghị, chẳng hạn như thuật

toán dựa vào khái niệm ma trận phân biệt được, thuật toán rời rạc hoá và lập luận

logic, thuật toán dựa vào bảng phân bố tổng quát và tập thô v.v... Tuy nhiên, số

lượng các tập rút gọn có thể là 2k − 1, với k là số các thuộc tính. Ngoài ra, trong

thực tế thường không đòi hỏi tìm tất cả các tập rút gọn mà chỉ cần tìm được một

tập rút gọn "tốt nhất" là đủ. Vì vậy, các thuật toán heuristic là rất đáng được quan

tâm, các thuật toán này nhằm làm giảm khối lượng tính toán, nhờ đó có thể áp

dụng đối với các bài toán có khối lượng dữ liệu lớn. Không ngoài mục đích đó, trong

chương này chúng tôi cũng đề nghị một số thuật toán heuristic tìm tập rút gọn của

bảng quyết định. Các thuật toán này đều có độ phức tạp tính toán theo thời gian

là O(k2n log n), với k là số thuộc tính và n là số các đối tượng trong hệ thống. Hai

thuật toán đầu dựa vào mô hình tập thô mới được đề nghị bởi các tác giả Xiaohua

phân biêt được do A. Skowron và C. Rauser đề xướng [26].

2.2. Thuật toán sử dụng các phép toán đại số

2.2.1. Tập lõi trong bảng quyết định

Cho bảng quyết định T = (U, C ∪ D). Khi đó trên U có quan hệ tương

đương IND(D). Giả sử các lớp tương đương ứng với quan hệ này là U/D =

{W1, W2, · · · , Wk} và các tập B−xấp xỉ dưới, B−xấp xỉ trên của của các tập Wi

tương ứng là BWi và BWi. Dựa trên các khái niệm xấp xỉ này, các tác giả Xiao-

hua Hu, Jianchao Han và T.Y. Lin [14] đã đưa ra các khái niệm B−xấp xỉ dưới và

Hu, Jianchao Han và T.Y.Lin [14], thuật toán còn lại dựa vào ý nghĩa của ma trận

B−xấp xỉ trên tương ứng với tập quyết định D của tập đối tượng U . Từ đó đưa ra

các khái niệm tương đương về tập lõi và rút gọn dựa vào các phép toán đại số quan

hệ. Chúng ta sẽ lần lượt tiếp cận các khái niệm này thông qua các định nghĩa một

cách chính xác như sau

Định nghĩa 2.1. Cho bảng quyết định T = (U, C∪D) và U/D = {W1, W2, · · · , Wk}.

Giả sử B ⊆ C, B−xấp xỉ dưới tương ứng với D của U, ký hiệu Lower[B]/[D], là tập

k [

xác định bởi

j=1

(2.1) BWj. Lower[B]/[D] :=

Định nghĩa 2.2. Với các giả thiết như trong Định nghĩa 2.1, B−xấp xỉ trên tương

k [

ứng với D của U, ký hiệu Upper[B]/[D], là tập xác định bởi

j=1

(2.2) BWj. Upper[B]/[D] :=

Thực ra khái niệm Lower[B]/[D] chính là B−miền khẳng định của D còn Upper[B]/[D]

lúc nào cũng bằng chính tập U . Điều này được suy ra từ định nghĩa của bảng quyết

định nhất quán và các tính chất của quan hệ tương đương, cụ thể chúng ta có mệnh

Mệnh đề 2.1. Cho T = (U, C ∪ D) là một bảng quyết định. Khi đó:

a) B0 ⊆ B ⊆ C ⇒ ∀ Vi ∈ U/B, ∃V 0

j ∈ U/B0 : Vi ⊆ V 0 j .

b) Upper[B]/[D] = U với mọi tập B ⊆ C.

c) T nhất quán ⇔ Lower[C]/[D] = U .

Chứng minh. Xét B, B0 ⊆ C. Khi đó,

a) B0 ⊆ B ⇒ ∀u, v ∈ U, u(B) = v(B) thì u(B0) = v(B0) do đó [u]B ⊆ [u]B0.

k [

BWj =

{u ∈ U | [u]B ∩ Wj 6= ∅} = U vì với mọi đối tượng

b) Upper[B]/[D] =

j=1

u ∈ U đều thuộc một lớp tương đương Wj nào đó.

đề sau

c) Rõ ràng T nhất quán khi và chỉ khi POSC(D) = U . Hơn nữa, từ định nghĩa của Lower ta có Lower[C]/[D] = POSC(D). Do đó T nhất quán khi và chỉ khi (cid:3) Lower[C]/[D] = POSC(D) = U.

Từ các định nghĩa xấp xỉ trên bảng quyết định các tác giả trong [14] đã đưa

ra định nghĩa mới về tập lõi dựa vào các phép toán của đại số quan hệ, đó là phép

đếm và phép chiếu.

Định nghĩa 2.3. Với các xấp xỉ được định nghĩa trong (2.1) và (2.2), ta gọi B−biên

của U là tập

(2.3) Boundary[B]/[D] := Upper[B]/[D] \ Lower[B]/[D] = U \ Lower[B]/[D] .

Định nghĩa 2.4. Cho T = (C, D) là một bảng quyết định nhất quán. Thuộc tính

cj ∈ C được gọi là thuộc tính lõi (hay không cần thiết) nếu

Định nghĩa này mang lại một ý nghĩa thực tiễn rất lớn, cho phép xác định các

thuộc tính lõi chỉ với những thao tác đơn giản mà không cần tìm tất cả các tập rút

gọn, thậm chí chưa biết đến một tập rút gọn nào cả. Hơn nữa, định nghĩa này hoàn

toàn tương đương với định nghĩa theo lý thuyết tập thô truyền thống đã được trình

bày trong Mục 1.3.1.

Thật vậy, nếu cj là thuộc tính cần thiết thì POSC(D) % POSC\{cj }(D) suy ra ∃u ∈ POSC(D) mà u 6∈ POSC\{cj }(D). Do đó [u]C ⊆ [u]D mà [u]C\{cj } * [u]D hay nói cách khác, ∃v ∈ [u]C\{cj } sao cho v 6∈ [u]D tức là v(C \ {cj}) = u(C \ {cj}) và v(D) 6= u(D). Vậy Card(Q(C \ {cj})) < Card(Q(C \ {cj} ∪ D)). Ngược lại, giả sử

(2.4) thoả mãn. Lúc đó, tồn tại V ∈ U/(C \ {cj}) và V 6∈ U/(C \ {cj} ∪ D). Tức là V * Lower[C\{cj }]/[D] trong khi V ⊆ U = Lower[C]/[D] vì T là nhất quán. Vậy cj là thuộc tính cần thiết.

Card( (2.4) (C \ {cj})) < Card( (C \ {cj} ∪ D)).

Từ định nghĩa này, cũng trong [14], các tác giả đã đề nghị thuật toán sau tìm

lõi của bảng quyết định

Thuật toán 2.1. Tìm lõi.

Input: T = (C, D).

Output: Tập lõi Core.

Method:

1. Core := ∅;

2. For cj ∈ C do

3. If Card(Q(C \ {cj})) < Card(Q(C \ {cj} ∪ D)) then

4. Core := Core ∪{cj};

Độ phức tạp tính toán của thuật toán này là O(kn log n), trong đó k = Card(C)

và n = Card(U ).

Ví dụ 2.1. Ta xét bảng quyết định trong [14] được cho bởi Bảng 2.1, lưu thông tin về

8 chiếc xe hơi nhận được thông qua các thuộc tính điều kiện C = {c1 = W eight, c2 =

c4 d

low

compact

high

low

sub

low

compact

high

u3 medium 4

high

compact

low

high

compact

low

compact

high

sub

low

sub

low

Door, c3 = Size, c4 = Cylinder} và thuộc tính quyết định D = {d = M ileage}.

Bảng 2.1: Bảng thông tin về các xe hơi.

Trong bảng này ta có:

Card(Q({c1, c2, c3})) = 8 = Card(Q({c1, c2, c3, d})).

Như vậy, c4= Cylinder không phải là thuộc tính lõi. Tương tự c2 = Door, c3= Size

cũng không phải là thuộc tính lõi vì

Card(Q({c1, c2, c4})) = 8 = Card(Q({c1, c2, c4, d})),

Card(Q(c1, c3, c4)) = 6 = Card(Q(c1, c3, c4, d)).

Trong khi đó

Card(Q({c2, c3, c4})) = 5 < Card(Q({c2, c3, c4, d})) = 6.

2.2.2. Đặc trưng của tập rút gọn

Vậy bảng chỉ có một thuộc tính lõi là c1= Weight.

Cũng trong nổ lực xây dựng thuật toán cải tiến tìm tập rút gọn dựa vào đại số

Định nghĩa 2.5. [14]

a) Cho R là một tập con các thuộc tính điều kiện: R ⊆ C. Độ phụ thuộc giữa

R và tập thuộc tính quyết định D trong bảng quyết định T = (U, C ∪ D), ký

hiệu K(R, D), là giá trị được định nghĩa bởi

K(R, D) =

(2.5)

Card(Q(R ∪ D)) Card(Q(C ∪ D))

b) Tập con R ⊆ C được gọi là một rút gọn của tập thuộc tính điều kiện tương

ứng với tập thuộc tính quyết định D nếu

K(R, D) = K(C, D)

(2.6)

và

quan hệ, trong [14] các tác giả đã đưa ra một định nghĩa rút gọn mới.

K(R, D) > K(R0, D), ∀R0 ⊂ R. (2.7)

Rất tiếc, không như định nghĩa về lõi (Định nghĩa 2.4), định nghĩa này không

tương đương với định nghĩa của tập rút gọn trong lý thuyết tập thô truyền thống

ngay cả khi bảng là nhất quán. Vì vậy thuật toán rút gọn mà các tác giả đã đề nghị

trong [14] là không chuẩn xác. Chúng ta có thể dễ dàng nhận thấy điều này qua ví

dụ sau.

Ví dụ 2.2. Ta vẫn xét bảng quyết định cho ở Ví dụ 2.1. Trong bảng này có hai rút

gọn là R1 ={Weight, Size} và R2 = {Weight, Cylinder} nhưng

= 6= K(C, D) = 1. K(R1, D) = Card(Q(R1 ∪ D)) Card(Q(C ∪ D)) 5 8

Cũng vậy ta có

= 6= K(C, D) = 1. K(R2, D) = Card(Q(R2 ∪ D)) Card(Q(C ∪ D)) 5 8

Như chúng ta đã biết, bài toán tìm tập rút gọn của một tập thuộc tính điều

bảng. Hay nói cách khác, ta tìm cách loại bỏ (tối đa) các thuộc tính thừa mà phần

còn lại cũng chứa đầy đủ thông tin của bảng. Đối với một bảng quyết định có thể

có nhiều tập rút gọn khác nhau. Việc tìm tất cả các tập rút gọn từ bảng quyết định

là bài toán NP-khó, hơn nữa, trong nhiều ứng dụng thực tế, thường không cần phải

tìm tất cả các tập rút gọn, mà chỉ cần một tập rút gọn tốt nhất. Một câu hỏi khá

tự nhiên là dựa vào tiêu chuẩn nào để đánh giá một tập rút gọn là tốt? Và như vậy,

nói chung, việc chọn các thuộc tính trong tập rút gọn còn phụ thuộc vào tiêu chuẩn

tối ưu đặt ra.

Ở đây chúng tôi sẽ đưa ra một định nghĩa tương đương của tập rút gọn dựa

trên các phép toán đại số quan hệ. Trên cơ sở đó, chúng tôi đề nghị một số thuật

toán tìm rút gọn hợp lý và do đó khả thi hơn các thuật toán được đề nghị trong

[14].

kiện chính là việc chọn lựa các đặc trưng thiết yếu và đủ để biểu diễn dữ liệu trong

Định nghĩa 2.6. Cho R là một tập con của tập thuộc tính điều kiện C. Độ phụ

thuộc của tập thuộc tính quyết định D vào R, ký hiệu k(R, D), là giá trị

k(R, D) = . (2.8) Card(Q(R)) Card(Q(R ∪ D))

Độ phụ thuộc này phản ánh khả năng phân hoạch trên R ∪ D bằng cách chỉ

dựa vào tập thuộc tính R. Tính hợp lý của định nghĩa này được thể hiện qua mệnh

đề dưới đây mà việc chứng minh nó là không có gì khó khăn.

Mệnh đề 2.2. Với mọi tập R ⊆ C, ta có

a) k(R, D) ≤ 1.

b) k(R, D) = 1 ⇔ phụ thuộc hàm R → D đúng trên U.

c) T nhất quán ⇔ k(C, D) = 1.

d) Nếu k(R, D) = 1, thì k(R0, D) = 1 với mọi R ⊆ R0 ⊆ C.

chọn làm đặc trưng cho tập thuộc tính điều kiện. Vì vậy ta đi đến định nghĩa về tập

rút gọn như sau.

Định nghĩa 2.7. Tập con các thuộc tính điều kiện R ⊆ C được gọi là một tập rút

gọn của tập thuộc tính điều kiện C đối với D nếu

k(R, D) = k(C, D)

(2.9)

và

k(R0, D) < k(C, D), ∀ R0 ⊂ R.

(2.10)

Trong trường hợp T là bảng nhất quán ta có thể chứng minh được định nghĩa

này là hoàn toàn tương đương với định nghĩa trong lý thuyết tập thô truyền thống

(trang 17). Thật vậy, giả sử U/R = {V1, V2, · · · , Vp} và U/D = {W1, W2, · · · , Wq},

Khi phân hoạch trên R trùng với phân hoạch trên R ∪ D thì tập R có thể được

ta có:

k(R, D) = k(C, D) = 1 ⇔ Card( (R)) = Card( (R ∪ D))

⇔ U/R = U/(R ∪ D)

q [

⇔ ∀ Vi ∈ U/R, ∃Wj ∈ U/D sao cho Vi ⊆ Wj

i=1

RWj = U = Lower[C]/[D] ⇔ Lower[R]/[D] =

⇔ POSR(D) = POSC(D).

2.2.3. Các thuật toán

Giả sử T là bảng nhất quán, trong mục này ta sẽ tìm cách xây dựng các thuật

toán tìm rút gọn của bảng sử dụng Định nghĩa 2.7. Nếu R là một tập rút gọn thì R

chứa mọi thuộc tính lõi. Nhận xét này gợi ý cho chúng ta xây dựng hai cách tiếp cận

khác nhau đến tập rút gọn. Thuật toán thứ nhất theo kiểu xấp xỉ ngoài, tức là xuất

phát từ R := C chúng ta tìm cách loại bỏ tối đa các thuộc tính cj ∈ R \ Core trong

khi mà k(R \ {cj}, D) vẫn còn bằng 1. Thuật toán thứ hai theo kiểu xấp xỉ trong,

bằng cách khởi tạo R := Core và bổ sung thêm tối thiểu các thuộc tính cj ∈ C \ R

Thuật toán thứ nhất thích hợp đối với những bài toán mà các thuộc tính có

thể được sắp xếp theo một tiêu chuẩn ưu tiên nào đó. Trong trường hợp như vậy,

các thuộc tính được xem xét để loại bỏ là các thuộc tính có độ ưu tiên thấp. Cụ

thể, thuật toán được trình bày như sau

Thuật toán 2.2. Tìm tập rút gọn theo xấp xỉ ngoài.

Input: T = (C, D).

Output: Tập rút gọn R.

Method:

1. Tìm Core theo Thuật toán 2.1;

2. Sắp xếp tập C \ Core theo thứ tự ưu tiên tăng dần;

cho đến khi nhận được k(R, D) = 1.

3. Đặt R := C;

4. For cj ∈ C \ Core do

5. If k(R \ {cj}, D) = 1 then

6. R := R \ {cj};

Như vậy, xuất phát từ R = C, thuật toán thực hiện tối đa k vòng lặp để thực

hiện loại bỏ R := R \ {cj}. Trong mỗi vòng lặp này, chúng ta phải kiểm tra điều

kiện k(R \ {cj}, D) = 1. Điều đó đòi hỏi sắp xếp lại các đối tượng trong U theo thứ

tự tăng/giảm giá trị của các thuộc tính trong R \ {cj} và D. Vậy, độ phức tạp tính

toán của thuật toán này sẽ là O(kn log n), với n = Card(U ) và k = Card(C).

Ví dụ 2.3. Xét bảng quyết định cho trong Bảng 2.1 lưu thông tin về các xe hơi,

giả sử các thuộc tính được sắp theo thứ tự chỉ số thuộc tính tương ứng ta có:

Core = {c1}.

Xuất phát R := C; Card(Q(R)) = 8.

Card(Q(R \ {c2})) = 8 = Card(Q(R \ {c2} ∪ D)).

Do đó, k(R \ {c2}, D) = 1.

Như vậy có thể loại c2 khỏi R. Lúc này R = {c1, c3, c4}.

Xét c3 ta có:

Card(Q(R \ {c3})) = 5 = Card(Q(R \ {c3} ∪ D)),

do đó k(R \ {c3}, D) = 1,

và c3 cũng được loại ra khỏi R. Bây giờ R = {c1, c4}.

Xét c4 ta có:

Card(Q(R \ {c4})) = 3.

trong khi Card(Q(R \ {c4} ∪ D)) = 4,

Xét c2 ∈ C \ Core, ta có:

< 1. do đó k(R \ {c3}, D) = 3 4

Vậy R = {c1, c4} là một tập rút gọn.

Thực ra bảng có hai rút gọn (trong thuật toán sau chúng ta sẽ thấy), nhưng

do chúng ta sắp thứ tự ưu tiên tăng dần theo chỉ số thuộc tính nên thuộc tính c4

có độ ưu tiên xét đưa vào tập rút gọn cao hơn.

Thuật toán thứ hai xuất phát từ R := Core. Vấn đề là ta cần bổ sung thêm

các thuộc tính nào để R thực sự là tập rút gọn? Chúng ta sẽ thảo luận về điều đó

ngay dưới đây.

Cho V ⊆ U , với mỗi tập con B ⊆ C, quan hệ tương đương cảm sinh của

IND(B) lên V là IND(B|V ) và các lớp tương đương của IND(B|V ) là V /B =

m }. Tương tự, quan hệ tương đương cảm sinh bởi IND(D) lên V là

2 , · · · , V B

1 , V B

{V B

1 , V D

2 , · · · , V D

k }.

IND(D|V ) và các lớp tương đương của quan hệ này là V /D = {V D

Lúc này ta cũng có các khái niệm B−xấp xỉ dưới và B−biên của V , ký hiệu lần

k [

(2.11)

Lower[BV ]/[DV ] :=

j ], Lower[BV ]/[V D

j=1

(2.12)

Boundary[BV ]/[DV ] := V \ Lower[BV ]/[DV ],

trong đó,

m [

| V B

Lower[BV ]/[V D

{V B i

i ⊆ V D

j }.

j ] :=

i=1

Từ các định nghĩa trên ta có thể dễ dàng kiểm chứng được khẳng định sau

Mệnh đề 2.3. Giả sử T là nhất quán. Lúc đó,

a) R là tập rút gọn khi và chỉ khi nó là tập con tối tiểu của C thoả mãn

Boundary[R]/[D] = ∅.

lượt là Lower[BV ]/[DV ] và Boundary[BV ]/[DV ], xác định như sau

b) Nếu R1 ⊆ R2 ⊆ C, thì bằng cách đặt V = Boundary[R1]/[D] ta có:

2 ]/[DV ] .

Boundary[R2]/[D] = Boundary[RV

Bây giờ giả sử R ⊆ C và cj ∈ C \ R. Đặt V = Boundary[R]/[D] và ký hiệu QV (B) là chiếu của V lên tập thuộc tính B. Ta gọi khả năng đóng góp của cj vào

R là tỷ số sau

. (2.13) m(cj, R) := Card(QV ({cj})) Card(QV ({cj} ∪ D))

Dễ thấy m(cj, R) ∈ (0, 1]. Tỷ số này thể hiện khả năng phân lớp V theo thuộc

tính D mà chỉ dựa vào thuộc tính cj. Nếu hệ số này càng lớn thì (R ∪ {cj})−xấp

xỉ dưới của V càng lớn và, do đó, (R ∪ {cj})−biên của V càng bé. Mà theo Mệnh

đề 2.3 ta có

Boundary[R∪{cj }]/[D] = Boundary[(R∪{cj })V ]/[DV ],

nên R ∪ {cj}−biên của U càng bé. Trên cơ sở phân tích đó, ta sẽ ưu tiên bổ sung

vào R các thuộc tính có khả năng đóng góp vào R mạnh nhất. Việc bổ sung như

vậy sẽ lặp lại cho đến khi R là một tập rút gọn thực sự. Tóm lại, ta có thuật toán

Thuật toán 2.3. Tìm tập rút gọn theo xấp xỉ trong.

Input: T = (C, D).

Output: Tập rút gọn R.

Method:

1. Tìm Core theo Thuật toán 2.1;

2. R := Core;

3. Chọn cr ∈ C \ R sao cho

m(cr, R) = max{m(cj, R) | cj ∈ C \ R};

4. R := R ∪ {cr};

5. Nếu Boundary[R]/[D] = ∅ thì dừng. Ngược lại, quay về 3.

Như vậy, xuất phát từ R = Core, thuật toán thực hiện tối đa k vòng lặp để

bổ sung R = R ∪ {cr}. Trong mỗi vòng lặp này, chúng ta phải tính lại tất cả các

m(cj, R) chúng ta cần sắp xếp các đối tượng trong V = Boundary[R]/[D] theo thứ tự

m(cj, R) và chọn ra thuộc tính có khả năng đóng góp cao nhất. Nhưng để tính được

tăng/giảm giá trị của các thuộc tính trong cj và D. Tóm lại, độ phức tạp tính toán

của giải thuật này sẽ là O(k2n log n), với n = Card(U ) và k = Card(C). Thực ra thì

cứ sau mỗi vòng lặp, tập các đối tượng làm việc là V sẽ giảm đi nhiều so với tập U

ban đầu.

Sử dụng thuật toán này để tìm rút gọn tương ứng trong bảng ở Ví dụ 2.1 ta

lần lượt nhận được:

R := Core = {c1} = {W eight},

V = Boundary[{c1}]/[{d}] = {t1, t2, t6, t8},

= 1,

m({c3}, R) =

= 1.

m({c4}, R) =

, m({c2}, R) =

Như vậy, ta có thể bổ sung c3 hoặc c4 vào R. Trong cả hai trường hợp ta đều

có Boundary[R∪{cr}]/[D] = ∅ và thuật toán dừng.

Cuối cùng ta có hai tập rút gọn là R = {c1, c3} hay R = {c1, c4}.

2.3. Thuật toán dựa vào số cặp phân biệt được

2.3.1. Một số ký hiệu

Như trong Chương 1. đã trình bày, việc tìm tập rút gọn của bảng quyết định có

2 4 2 2 2 2

thể dựa vào ma trận phân biệt được của bảng quyết định đó. Tuy vậy, thuật toán

này thường đòi hỏi một độ phức tạp rất lớn cả về thời gian lẫn không gian lưu trữ.

Để khắc phục nhược điểm đó, ở đây chúng tôi đề nghị một thuật toán cũng dựa vào

ý nghĩa của ma trận phân biệt được nhưng không cần phải lưu trữ ma trận. Thay

vào đó, chúng ta phải xác định số cặp đối tượng phân biệt được đối với từng thuộc

mục này.

tính điều kiện. Trước hết chúng ta hãy làm quen một số ký hiệu được sử dụng trong

Xét bảng quyết định T = (U, C ∪ D), với C là tập thuộc tính điều kiện và D là

tập thuộc tính quyết định.

B (cj) là số cặp đối tượng của V

Cho B ⊆ C, V ⊆ U và cj ∈ C \ B. Ký hiệu ωV

bằng nhau trên B nhưng khác nhau tại thuộc tính cj, tức là:

B (cj) = Card({(u, v) | u, v ∈ V ; u(B) = v(B) và u(cj) 6= v(cj)}).

ωV

B (D):

Ta cũng có định nghĩa tương tự cho ωV

B (D) = Card({(u, v) | u, v ∈ V ; u(B) = v(B) và u(D) 6= v(D)}).

ωV

khi V = U , ta lại viết là ωB(cj) và ωB(D). Cuối cùng, nếu V = U và B = ∅ ta chỉ

ký hiệu một cách đơn giản bởi ω(cj) và ω(D). Tóm lại,

ωV (cj) = Card({(u, v) | u, v ∈ V ; u(cj) 6= v(cj)}),

ωV (D) = Card({(u, v) | u, v ∈ V ; u(D) 6= v(D)}),

ωB(cj) = Card({(u, v) | u, v ∈ U ; u(B) = v(B) và u(cj) 6= v(cj)}),

ωB(D) = Card({(u, v) | u, v ∈ U ; u(B) = v(B) và u(D) 6= v(D)}),

ω(cj) = Card({(u, v) | u, v ∈ U ; u(cj) 6= v(cj)}),

ω(D) = Card({(u, v) | u, v ∈ U ; u(D) 6= v(D)}).

Ví dụ 2.4. Xét tập 10 đồ chơi với tập thuộc tính điều kiện C= {Màu sắc, Kích

thước, Hình dáng} và thuộc tính quyết định D = {Phù hợp lứa tuổi} được cho trong

Khi B = ∅, hai đại lượng trên được viết một cách đơn giản là ωV (cj) và ωV (D), còn

Bảng 2.2.

Cho B = {Màu sắc, Hình dáng}; c = "Kích thước" và V = {u1, u2, u3, u8, u9, u10}.

Khi đó:

B (c) = Card({(u1, u2); (u1, u10); (u2, u10); (u3, u9)}) = 4;

ωV

B (D) = Card({(u1, u2); (u1, u10); (u3, u9)}) = 3;

ωV

ωV (c) = Card({(u1, u2); (u1, u3); (u1, u10); (u2, u3); (u2, u8); (u2, u9); (u2, u10);

(u3, u8); (u3, u9); (u8, u10); (u9, u10)}) = 11;

Màu sắc Kích thước Hình dáng Phù hợp lứa tuổi U

Xanh To Tròn 4-10 u1

Xanh Nhỏ Tròn 1-3 u2

Vàng Vừa Vuông 4-10 u3

Đỏ Vừa Vuông 4-10 u4

Vàng To Tam giác 11-15 u5

Xanh Nhỏ Tròn 1-3 u6

Đỏ Nhỏ Tam giác 11-15 u7

Vàng

Vuông

11-15

Vừa

Tròn

1-3

u10 Xanh

Bảng 2.2: Bảng dữ liệu các đồ chơi.

ωV (D) = Card({(u1, u2); (u1, u9); (u1, u10); (u2, u3); (u2, u8); (u2, u9); (u3, u9);

(u3, u10); (u8, u9); (u8, u10); (u9, u10)}) = 11.

2.3.2. Cơ sở toán học

Như chúng ta đã biết, nếu bảng quyết định nhất quán thì tập thuộc tính quyết

định D phụ thuộc hoàn toàn vào tập thuộc tính điều kiện C. Khi đó một tập R ⊆ C

Đỏ To Tam giác 4-10 u8

là một rút gọn của C khi D phụ thuộc hoàn toàn vào R, nói cách khác, mọi cặp

đối tượng bằng nhau trên R cũng bằng nhau trên D, tức là ωR(D) = 0. Dựa vào ý

tưởng này, chúng ta xây dựng thuật toán tìm tập rút gọn xuất phát từ tập R = ∅

và bổ sung dần các thuộc tính vào R cho đến khi nhận được ωR(D) = 0. Tính hợp

lý của thuật toán này dựa trên cơ sở các khẳng định sau.

Mệnh đề 2.4. [12] Cho V ⊆ U . Giả sử V /D = {V1, V2, · · · , Vm}, với Card(V ) = x;

m X

Card(Vi) = xi. Khi đó,

i=1

m X

x = xi,

i=1

(x2 − ωV (D) = xixj = x2 i ). 1 2

Mệnh đề 2.5. Giả sử V ⊆ U , B ⊆ C và V /B = {V1, V2, · · · , Vk}. Khi đó,

B (D) = ωV1

B (D) + ωV2

B (D) + · · · + ωVk

B (D),

b) Với cj ∈ C \ B, ta có:

V /(B ∪ {cj}) = V1/{cj} ∪ V2/{cj} ∪ · · · ∪ Vk/{cj}.

}, thì

c) Nếu cj ∈ C \ B và Vi/{cj} = {W i

1, W i

2, · · · , W i pi

1(D) + ωW i

2(D) + · · · + ωW i

pi (D).

B∪{cj }(D) = ωW i ωVi

Chứng minh. Phần a) và b) có thể xem chứng minh ở [12], bây giờ chúng ta sẽ

chứng minh phần c). Vì V /B = {V1, V2, · · · , Vk} nên Vi/B = {Vi} và theo b) ta có:

}

Vi/(B ∪ {cj}) = Vi/{cj} = {W i

1, W i

2, · · · , W i pi

Mặt khác, từ a) ta lại có:

1(D) + ωW i

2(D) + · · · + ωW i

pi (D).

B∪{cj }(D) = ωW i ωVi

(cid:3)

a) ωV

Ví dụ 2.5. Xét bảng quyết định cho bởi Bảng 2.2, với các tập V, B và c được chọn

như trong Ví dụ 2.4. Ta có:

V /D = {V1, V2, V3}, với V1 = {u1, u3, u8}; V2 = {u2, u10}; V3 = {u9},

V /B = {W1, W2, W3}, với W1 = {u1, u8, u9}; W2 = {u2}; W3 = {u3, u10}.

3 X

Khi đó: x = 6; x1 = 3; x2 = 2; x3 = 1 và theo Mệnh đề 2.5,

i=1

(x2 − x2) = 11, ωV (D) = xixj = 1 2

(9 − (4 + 1)) = 2, ωW1(D) = 1 2

ωW2(D) = (1 − 1) = 0, 1 2

ωW3(D) = (4 − (1 + 1)) = 1, 1 2

chúng ta nhận được đúng kết quả tính toán ở Ví dụ 2.4.

Mệnh đề 2.6. R là một rút gọn của tập thuộc tính điều kiện C khi và chỉ khi R là

tập tối tiểu thỏa ωR(D) = 0.

Chứng minh. Rõ ràng theo nhận xét trong phần trên, nếu R là một rút gọn của C

thì R là tập tối tiểu thỏa tính chất: Mọi cặp đối tượng bằng nhau trên R cũng bằng

nhau trên D hay ωR(D) = 0.

Ngược lại, giả sử R là tập tối tiểu thỏa ωR(D) = 0, lúc đó R xác định D hay

POSR(D) = POSC(D), hơn nữa, mọi tập con thực sự của R không thỏa tính chất hay T0 = (U, R ∪ D) là độc lập. Vậy R là một rút gọn của C.

2.3.3. Thuật toán

ωV (D) = ωW1(D) + ωW2(D) + ωW3(D) = 2 + 0 + 1 = 3,

Như trên đã đề cập, trong phần này chúng tôi sẽ đưa ra thuật toán tìm tập rút

gọn dựa vào kết luận của Mệnh đề 2.6 và các giá trị trung gian được tính toán theo

kết quả của Mệnh đề 2.5. Thoạt tiên, ta chọn R := ∅ và sẽ bổ sung dần các thuộc

R. Một cách tự nhiên, ta chọn thuộc tính mà khi tham gia vào tập rút gọn sẽ làm

tính vào R. Vấn đề đặt ra là tại mỗi bước chọn lựa, thuộc tính nào sẽ được đưa vào

cho số cặp đối tượng bằng nhau trên R nhưng khác nhau trên D là ít nhất. Với cách

chọn lựa heuristic này, thuật toán có khả năng cho ta một tập rút gọn với số thuộc

tính tối thiểu.

Tại mỗi bước, ta luôn ký hiệu L = U/R. Ban đầu R = ∅ nên L = {U }.

Thuật toán 2.4. Tìm tập rút gọn dựa vào số cặp phân biệt được.

Input: T = (C, D).

Output: Tập rút gọn R.

1. R = ∅; L := {U };

2. Repeat

For cj ∈ C \ R do

Begin{1}

For Vi ∈ L do

Begin{2}

Tìm Vi/{cj} = {W1, W2, · · · , Wm};

For l := 1 to m do

Begin{3}

10.

Tìm Wl/D = {W l

1, W l

2, · · · , W l

(cid:16)

k X

Method:

k}; i)2(cid:17) (xl

(xl)2 − ; 11. Tính ωWl(D) = 1 2

i=1 {trong đó xl = Card(Wl) và xl

i = Card(W l

i )}

12.

13. End{3}

R∪{cj }(D) := ωW1(D) + ωW2(D) + · · · +

ωWm(D);

14. := ωVi Tính γi j

15. End{2}

Vi∈ L

16. Tính αj := γi j;

End{1} 17.

18. Chọn thuộc tính cr sao cho αr là bé nhất;

[

19. R := R ∪ {cr};

Vi∈ L

M := 20. Vi/{cr} (= U/R);

L := M ; 21.

Ví dụ 2.6. Xét bảng quyết định chọn giáo viên [8] gồm chín đối tượng với tập thuộc

tính điều kiện C = {c1, c2, c3, c4} tương ứng là "trình độ chuyên môn", "yêu nghề",

"khả năng sư phạm", "kinh nghiệm giảng dạy" (tính bằng năm) và thuộc tính quyết

định d có hai giá trị: 1 ("chấp nhận"), 0 ("từ chối"), được cho trong Bảng 2.3.

Có

Tốt

u1 Giỏi

Tốt

u2 Trung bình Có

Không Trung bình 3

u3 Kém

Có

Tốt

u4 Giỏi

u5 Trung bình Không Tốt

Có

Trung bình 3

u6 Xuất sắc

22. Until (αr = 0) or (R = C);

Có Khá 0 0 u7 Xuất sắc

Không Khá 3 0 u8 Kém

Không Trung bình 2 0 u9 Giỏi

Bảng 2.3: Bảng chọn lựa giáo viên.

Thực hiện thuật toán trên, ta nhận được kết quả từng bước như sau:

R = ∅; L = {U } (V1 = U ),

V1/{c1} = {W1 = {u1, u4, u9}, W2 = {u2, u5}, W3 = {u3, u8}, W4 = {u6, u7}},

(32 − 22 − 12) = 2, ωW1(D) =

ωW2(D) = (22 − 12 − 12) = 1,

ωW3(D) = (22 − 22) = 0,

1 = ωW1(D) + ωW2(D) + ωW3(D) + ωW4(D) = 4. γ1

ωW4(D) = (22 − 12 − 12) = 1, 1 2 1 2 1 2 1 2

V1/{c2} = {W1 = {u1, u2, u4, u6, u7}, W2 = {u3, u5, u8, u9}},

2 = ωW1(D) + ωW2(D) = 4 + 0 = 4, γ1

V1/{c3} = {W1 = {u1, u2, u4, u5}, W2 = {u3, u6, u9}, W3 = {u7, u8}},

3 = ωW1(D) + ωW2(D) + ωW3(D) = 3 + 2 + 0 = 5, γ1

V1/{c4} = {W1 = {u1, u4}, W2 = {u2, u9}, W3 = {u3, u6, u8}, W4 = {u5},

W5 = {u7}},

4 = ωW1(D) + ωW2(D) + ωW3(D) + ωW4(D) + ωW5(D) = 0 + 1 + 2 + 0 + 0 = 3, γ1

α1 = γ1

1 = 4; α2 = γ1

2 = 4; α3 = γ1

3 = 5; α4 = γ1

4 = 3 ⇒ r = 4,

R = R ∪ {c4} = {c4},

Tương tự ta có:

L = {V1 = {u1, u4}, V2 = {u2, u9}, V3 = {u3, u6, u8}, V4 = {u5}, V5 = {u7}},

1 = 0,

V1/{c1} = {W1 = {u1, u4}} ⇒ γ1

1 = 0,

V2/{c1} = {W1 = {u2}, W2 = {u9}} ⇒ γ2

1 = 0,

V3/{c1} = {W1 = {u3, u8}, W2 = {u6}} ⇒ γ3

1 = 0,

V4/{c1} = {W1 = {u5}} ⇒ γ4

1 = 0,

V5/{c1} = {W1 = {u7}} ⇒ γ5

1 + γ2

1 + γ3

1 + γ4

1 + γ5

1 = 0,

α1 = γ1

2 = 0,

V1/{c2} = {W1 = {u1, u4}} ⇒ γ1

2 = 0,

V2/{c2} = {W1 = {u2}, W2 = {u9}} ⇒ γ2

2 = 0,

V3/{c2} = {W1 = {u3, u8}, W2 = {u6}} ⇒ γ3

2 = 0,

V4/{c2} = {W1 = {u5}} ⇒ γ4

2 = 0,

V5/{c2} = {W1 = {u7}} ⇒ γ5

2 + γ2

2 + γ3

2 + γ4

2 + γ5

2 = 0,

α2 = γ1

3 = 0,

V2/{c3} = {W1 = {u2}W2 = {u9}} ⇒ γ2

3 = 0,

V3/{c3} = {W1 = {u3, u6}, W2 = {u8}} ⇒ γ3

3 = 1,

V4/{c3} = {W1 = {u5}} ⇒ γ4

3 = 0,

V5/{c3} = {W1 = {u7}} ⇒ γ5

3 = 0,

α3 = γ1

3 = 1.

3 + γ5

3γ4

3 + γ3

3 + γ2

Đến đây chúng ta có thể chọn r = 1 hoặc r = 2 vì α1 = α2 = 0. Thuật toán

dừng và chúng ta nhận được hai rút gọn tương ứng là R1 = {c1, c4} và R2 = {c2, c4},

như vậy tập lõi là Core = {c4}.

Để đánh giá độ phức tạp tính toán của thuật toán này ta gọi k là số thuộc tính

điều kiện và n là số đối tượng trong bảng quyết định. Hai vòng lặp Repeat (2.) và

V1/{c3} = {W1 = {u1, u4}} ⇒ γ1

For (3.) lồng nhau, mỗi vòng thưc hiện tối đa k lần, nên ta có số lần thực hiện Vòng

lặp (1.) là O(k2). Trong mỗi vòng lặp đó, ta có hai lần sắp xếp tập đối tượng U , một

lần theo giá trị thuộc tính cj (7.) và một lần theo giá trị thuộc tính D (10.) nên độ

phức tạp của mỗi vòng lặp này là O(n log n). Tóm lại, thuật toán có độ phức tạp là

O(k2n log n).

2.4. Thuật toán tìm rút gọn xấp xỉ

2.4.1. Đặt vấn đề

Trong hai phần trước, chúng ta đã làm quen với các thuật toán tìm tập rút

gọn của bảng quyết định. Đó là một trong những phương pháp loại bỏ các dư thừa

trong dữ liệu. Tuy nhiên, trong thực tế dữ liệu thường rất lớn, đa dạng và có thể

bị nhiễu. Vì vậy bài toán tìm tập rút gọn chính xác đôi khi không cho ra kết quả

quyết định. Trong khi thực tế là tồn tại các rút gọn, nhưng vì một lý do nào đó dữ

liệu nhận được không như nó vốn có. Trong những trường hợp như thế, việc tìm

tập thuộc tính có thể đặc trưng cho tập thuộc tính điều kiện với "hầu hết" các đối

tượng trong bảng thay cho một rút gọn chính xác là rất cần thiết. Tập các thuộc

tính điều kiện đó được xem như những rút gọn "xấp xỉ". Trong phần này chúng ta

sẽ đưa ra những thuật toán tìm tập rút gọn xấp xỉ với những đánh giá về sai số

tương ứng.

Có nhiều cách đánh giá tính "gần đúng" của một tập rút gọn xấp xỉ, tương

tự như đánh giá sai số của một phụ thuộc hàm. Sai số của phụ thuộc hàm thông

thường biểu diễn tỷ số giữa số lượng các đối tượng vi phạm phụ thuộc hàm đó với

số lượng các đối tượng trong hệ thống (U ).

2.4.2. Sai số của rút gọn xấp xỉ

theo nghĩa là không thể rút gọn tập thuộc tính điều kiện mà có thể bảo toàn các

Như chúng ta đã biết, tập R là một rút gọn của bảng quyết định T = (U, C ∪D)

nếu D phụ thuộc hoàn toàn vào R tức là phụ thuộc hàm R → D đúng trên U . Vì

vậy sai số của tập rút gọn xấp xỉ cũng sẽ biểu diễn tương quan giữa các đối tượng có

cùng giá trị trên tập rút gọn xấp xỉ nhưng có những quyết định khác nhau (không

chấp nhận phụ thuộc hàm R → D) với số các đối tượng trong bảng. Trong [17] các

tác giả đã đề nghị ba đại lượng biểu thị sai số của phụ thuộc hàm X → Y như sau

, g1(X → Y ) = Card({(u, v) | u, v ∈ U, u(X) = v(X) và u(Y ) 6= v(Y )}) Card(U )2

, g2(X → Y ) =

. g3(X → Y ) = Card({u | u ∈ U, ∃v ∈ U : u(X) = v(X) và u(Y ) 6= v(Y )}) Card(U ) Card(U ) − max{Card(V ) | V ⊆ U, X → Y đúng trên V } Card(U )

Các giá trị g1, g2, g3 với các tập thuộc tính X, Y cho trước có thể được tính dễ

dàng bằng cách sắp xếp các đối tượng trong U theo thứ tự giá trị của các thuộc

bằng cách nào chúng ta có thể tìm được các tập rút gọn xấp xỉ với sai số được tính

theo quy định và không vượt quá một giá trị ngưỡng (cid:15) cho trước. Trong phần này,

chúng tôi đề nghị các thuật toán tìm các tập xấp xỉ với sai số được tính như trên.

Trước hết chúng ta cần chú ý rằng, một tập R có thể là một rút gọn xấp xỉ chấp

nhận được (sai số bé hơn hoặc bằng giá trị ngưỡng) đối với sai số được tính theo

cách này không nhất thiết phải là tập rút gọn xấp xỉ đối với sai số được tính theo

cách khác. Điều này là do các đánh giá sai số khác nhau thường cho ra các giá trị

khác nhau. Để minh hoạ ta thử xét ví dụ sau

Ví dụ 2.7. [17] Cho p và q là hai số nguyên dương thoả p > 2 ∗ q. Xét bảng quyết

định T gồm p đối tượng, với tập thuộc tính điều kiện C = B ∪ R và tập thuộc tính

quyết định D = {d}. Trong đó, p − q đối tượng đầu tiên (u1, · · · , up−q) có giá trị trên

tính và do đó có độ phức tạp là O(n log n) (n = Card(U )). Vấn đề đặt ra ở đây là

tập thuộc tính R là thứ tự của đối tương tương ứng trong bảng, và giá trị của thuộc

tính quyết định là 0, q đối tượng cuối có giá trị tại R lần lượt là p−2∗q +1, · · · , p−q,

còn giá trị quyết định là 1.

. cách khác nhau là g1(R → D) = và g3(R → D) = Nếu xem R là một rút gọn xấp xỉ thì sai số của rút gọn này được tính theo các 2q p2 , g2(R → D) = 2q p q p

R U B d

1 α 0 u1

· · · · · · · · · · · ·

p − 2 ∗ q α 0 up−2∗q

p − 2 ∗ q + 1 α 0 up−2∗q+1

· · · · · · · · · · · ·

p − q α 0 up−q

α p − 2 ∗ q + 1 1 up−q+1

p − q

Bảng 2.4: Bảng dữ liệu cho ví dụ rút gọn xấp xỉ.

2.4.3. Các thuật toán tìm rút gọn xấp xỉ

Trong [15] các tác giả đã đưa ra một thuật toán tìm tất cả các phụ thuộc hàm

cực tiểu và phụ thuộc hàm xấp xỉ với sai số g3. Trong phần này chúng tôi sẽ tìm

cách xây dựng các thuật toán tìm rút gọn xấp xỉ sử dụng các đánh giá g1 và g2 bằng

cách cải tiến các Thuật toán 2.3, 2.4.

Trước hết, từ định nghĩa của giá trị sai số g1, g2, chúng ta có mối liên hệ với

các giá trị ωR(D) và Boundary[R]/[D] thông qua mệnh đề sau

· · · · · · · · · · · ·

Mệnh đề 2.7. Cho bảng quyết định T = (U, C ∪ D), R ⊆ C. Khi đó:

a) g1(R → D) = ωR(D) Card(U )2 ,

= 1 − . b) g2(R → D) = Card(Boundary[R]/[D]) Card(U ) Card(Lower[R]/[D]) Card(U )

Chứng minh.

a) Suy ra trực tiếp từ định nghĩa của ωR(D).

b) Đẳng thức thứ hai là hiển nhiên, ta sẽ chứng minh đẳng thức thứ nhất. Đặt

. Bây giờ chúng ta chỉ cần chứng minh V = Boundary[R]/[D]. Thật

V = {u ∈ U | ∃v ∈ U, u(R) = v(R), u(D) 6= v(D)}. Thế thì g2(R → D) = Card(V ) Card(U ) vậy, với mọi u ∈ V , tồn tại v ∈ U sao cho u(R) = v(R) và u(D) 6= v(D). Như

vậy u ∈ [v]R và u 6∈ [v]D hay nói cách khác [v]R 6⊆ [v]D suy ra [u]R = [v]R 6⊆

POSR(D) hay u ∈ Boundary[R]/[D]. Ngược lại, lấy tuỳ ý u ∈ Boundary[R]/[D] ta

có u 6∈ POSR(D) hay [u]R 6⊆ [u]D. Do đó, tồn tại v ∈ [u]R ⊆ U nhưng v 6∈ [u]D.

Tóm lại, với mọi u ∈ Boundary[R]/[D], tồn tại v ∈ U sao cho u(R) = v(R)

chứng minh.

Từ Mệnh đề 2.7 chúng ta có thể xây dựng các thuật toán tìm tập rút gọn xấp

xỉ theo đánh giá g1 và g2 tương ứng dựa vào các Thuật toán 2.3, 2.4.

Thuật toán 2.5. Tìm tập rút gọn xấp xỉ theo đánh giá sai số g1.

Input: T = (U, C ∪ D) và giá trị ngưỡng (cid:15) ∈ [0, 1].

Output: Tập rút gọn R với đánh giá sai số g1(R → D) ≤ (cid:15).

Method:

1. R = ∅; L := {U };

2. Repeat

nhưng u(D) 6= v(D), tức là u ∈ V . Vậy V = Boundary[R]/[D] và mệnh đề được (cid:3)

3. For cj ∈ C \ R do

Begin{1} 4.

5. For Vi ∈ L do

Begin{2} 6.

7. Tìm Vi/{cj} = {W1, W2, · · · , Wm};

8. For l := 1 to m do

9. Begin{3}

2, · · · , W l

1, W l

(cid:16)

k X

10. Tìm Wl/D = {W l

k}; i)2(cid:17) (xl

11. Tính ωWl(D) = (xl)2 − ; 1 2

i=1 {trong đó xl = Card(Wl) và xl

i )}

i = Card(W l

12.

13. End{3}

R∪{cj }(D) := ωW1(D) + ωW2(D) + · · · +

14. := ωVi Tính γi j

ωWm(D);

16.

Tính αj :=

γi j;

Vi∈ L

17.

End{1}

18.

Chọn thuộc tính cr sao cho αr là bé nhất;

19.

R := R ∪ {cr};

15. End{2}

20.

M :=

Vi/{cr} (= U/R);

Vi∈ L

21.

L := M ;

22. Until (αr ≤ (cid:15) ∗ Card(U )2) ;

Thuật toán 2.6. Thuật toán tìm rút gọn xấp xỉ theo đánh giá sai số g2.

Input: Bảng quyết định T = (U, C ∪ D) và giá trị ngưỡng (cid:15) ∈ [0, 1].

[

Output: Tập rút gọn xấp xỉ R với sai số g2(R → D) ≤ (cid:15).

Method:

1. Khởi tạo R = ∅;

2. Chọn cr ∈ C \ R sao cho

m(cr, R) = max{m(cj, R) | cj ∈ C \ R}.

3. R := R ∪ {cr}.

4. Nếu Card(Lower[R]/[D]) ≥ Card(U )(1 − (cid:15)) thì dừng. Ngược lại, quay về 2.

Tóm lại, trong chương này chúng tôi đã đưa ra các tiêu chuẩn đại số để đánh

giá độ phụ thuộc của tập thuộc tính quyết định vào tập con R của tập thuộc tính

điều kiện C (k(R, D)) và khả năng đóng góp của một thuộc tính khi tham gia như

là một thành viên của tập rút gọn (m(cj, R)). Trên cơ sở đó xây dựng các thuật

toán dựa vào các phép toán của đại số quan hệ. Trong thuật toán thứ ba, chúng tôi

xây dựng trên cơ sở đưa ra giá trị ωR(D) là số cặp đối tượng bằng nhau trên tập

thuộc tính R ⊆ C nhưng khác nhau trên tập thuộc tính quyết định D và tập R là

một rút gọn nếu giá trị này bằng không. Với các kết qủa trên, chúng ta có thể thu

định sẽ được đưa ra chỉ dựa vào các giá trị của các thuộc tính trong R. Các thuật

toán này khả thi đối với các bảng dữ liệu lớn do độ phức tạp tính toán theo thời

gian là đa thức.

gọn bảng quyết định chỉ trên tập thuộc tính R ∪ D. Trên cơ sở đó, các luật quyết

Chương Chương 3.

KHÁM PHÁ PHỤ THUỘC ĐA TRỊ

DỰA VÀO MA TRẬN PHỤ THUỘC

3.1. Mở đầu

Sự khám phá những phụ thuộc và phụ thuộc xấp xỉ từ cơ sở dữ liệu rất cần

thiết cho mục đích khám phá tri thức và khai phá dữ liệu. Vì vậy việc tìm kiếm các

quan hệ phụ thuộc bên trong dữ liệu luôn luôn thu hút được sự quan tâm nghiên

cứu của nhiều người. Có thể đơn cử một số nhóm tác giả như: Hong Yao, Howard

J. Hamilton & Cory J. Butz [32], Mannila, H., Toivonen, H. & Verkamo, A.I. [22]

và Yka Huhtala, Juha Karkkainen, Pasi Porkka & Hannu Toivonen [15, 16]. Các

nghiên cứu của chúng tôi cũng nhằm vào hai loại phụ thuộc khá quen thuộc trong

cơ sở dữ liệu quan hệ, đó là phụ thuộc hàm và phụ thuộc đa trị. Ngoài việc đề xuất

các thuật toán phát hiện và kiểm chứng các phụ thuộc trong dữ liệu, chúng tôi còn

mở rộng các khái niệm này bằng cách sử dụng các công cụ của lý thuyết tập thô.

Như chúng ta đã biết, sự phụ thuộc giữa các thuộc tính của cơ sở dữ liệu quan

hệ biểu diễn hình dạng của cấu trúc trong quan hệ đó. Chẳng hạn như một phụ

thuộc hàm X → Y biểu diễn sự phụ thuộc của giá trị thuộc tính Y theo giá trị

thuộc tính X: Những giá trị của thuộc tính X xác định duy nhất giá trị của thuộc

tính Y . Hay phụ thuộc đa trị X →→ Y là sự phụ thuộc của Y vào X độc lập với

các thuộc tính còn lại.

Nhắc lại rằng, nếu X, Y là các tập thuộc tính, thì Y được gọi là phụ thuộc hàm

[21, 29, 30] vào X trên U và ký hiệu X → Y nếu

∀u, v ∈ U : u(X) = v(X) ⇒ u(Y ) = v(Y ). (3.1)

Hơn nữa, với các điều kiện X∩Y = ∅, X∪Y A, bằng cách đặt Z = A\(X∪Y ),

X →→ Y nếu

ta nói Y là phụ thuộc đa trị [15, 16, 21, 22, 25, 29, 30] vào X trên U và ký hiệu

t(X) = u(X),

(3.2)

∀u, v ∈ U : u(X) = v(X) ⇒ ∃t ∈ U :

t(Y ) = u(Y ),

t(Z) = v(Z).



Tuy nhiên, dữ liệu trong thực tế thường không thoả các điều kiện trong (3.1)

và (3.2) của những phụ thuộc hàm và phụ thuộc đa trị một cách thực sự nghiêm

ngặt trên cả tập đối tượng U . Vì vậy, trong chương này chúng tôi đề nghị các phụ

thuộc mở rộng theo hai nghĩa khác nhau. Một là các phụ thuộc chỉ đúng trên tập

con V các đối tượng của U . Trong trường hợp này, chúng ta sẽ có đánh gía về sai

số của phụ thuộc và phụ thuộc tương ứng được gọi là "phụ thuộc xấp xỉ". Loại thứ

 

hai chúng tôi xét khi giá trị của các thuộc tính nhận được có thể bị sai lệch và phụ

thuộc được chấp nhận khi sai số của các giá trị thuộc tính ở mức độ "cho phép",

phụ thuộc này chúng tôi gọi là "phụ thuộc mở rộng". Các khái niệm phụ thuộc xấp

xỉ và phụ thuộc mở rộng sẽ được trình bày chi tiết trong các phần tiếp theo.

được thực hiện trên cơ sở xây dựng ma trận phụ thuộc và dựa vào sự phân hoạch

Các thuật toán kiểm tra phụ thuộc và phụ thuộc xấp xỉ theo hai nghĩa trên

của quan hệ tương đương ứng với giá trị của các thuộc tính.

3.2. Khảo sát phụ thuộc bằng Ma trận phụ thuộc

3.2.1. Phụ thuộc và phụ thuộc xấp xỉ

Trong phần này ta luôn xét A = (U, A) là một hệ thống thông tin với U là tập

các đối tượng và A là tập các thuộc tính. Với mỗi u ∈ U và a ∈ A ta ký hiệu u(a)

là giá trị thuộc tính a của đối tượng u. Nếu X ⊆ A là một tập các thuộc tính ta ký

hiệu u(X) là bộ gồm các giá trị u(a) với a ∈ X. Vì vậy, nếu u và v là hai đối tượng

Trong nhiều trường hợp ta không nhận được X →→ Y nhưng tồn tại một tập

con V ⊂ U sao cho X →→ Y trên V , lúc đó ta ký hiệu X→→V Y . Nếu tập V như

vậy nhận được bằng cách loại bỏ một số rất ít các đối tượng trong U , thì ta nói Y

“phụ thuộc đa trị xấp xỉ“ vào X trên U . Rõ ràng ta cần chọn tập V như vậy càng

lớn càng tốt và điều này sẽ gợi ý cho chúng ta cách đánh giá sai số của phụ thuộc

hàm g3 (xem Mục 2.4.2.) lên phụ thuộc đa trị, cụ thể ta có định nghĩa như sau

Định nghĩa 3.1. Cho X, Y ⊆ A. Ta gọi giá trị sau là sai số của phụ thuộc đa trị

X →→ Y

g3(X →→ Y ) := 1 −

max{Card(V ) | V ⊆ U, X→→V Y } Card(U )

Rõ ràng, X →→ Y đúng khi và chỉ khi g3(X →→ Y ) = 0. Trong nhiều trường

thuộc U , ta sẽ nói u(X) = v(X) nếu u(a) = v(a) với mọi thuộc tính a ∈ X.

hợp, ngoài các phụ thuộc đa trị, chúng ta cũng cần xác định các phụ thuộc xấp xỉ

có sai số không vượt quá một giá trị ngưỡng (cid:15) ∈ [0, 1) cho trước.

Cho V ⊆ U và X ⊆ A. Ta gọi tập hợp sau

dom(V, X) = {u(X) | u ∈ V }

là miền giá trị của V trên X. Nhắc lại rằng, trên V tồn tại quan hệ tương đương

IND(X|V ) xác định bởi

∀u, v ∈ V : (u, v) ∈ IND(X|V ) ⇔ u(X) = v(X).

Họ các lớp tương đương trên V , tương ứng với IND(X|V ), được ký hiệu là V /X.

Bây giờ cho X, Y ⊆ A là hai tập con các thuộc tính. Giả sử

1 , V i

2 , · · · , V i ni

}; 1 ≤ i ≤ m. U/X = {V1, V2, · · · , Vm}; Vi/Y = {V i

(cid:17)

(cid:16)

Nghĩa là, với mọi đối tượng u, v ∈ U , ta có

(cid:16)

(cid:17)

u(X) = v(X) ⇔ (3.3) ∃i : u, v ∈ Vi

u(X ∪ Y ) = v(X ∪ Y ) ⇔ . (3.4) ∃i, j : u, v ∈ V i j

Định lý 3.1. Cho X, Y ⊆ A. Đặt Z = A \ (X ∪ Y ). Khi đó,

a) X → Y ⇔ Vi/Y = {Vi} (hay ni = 1), với mọi 1 ≤ i ≤ m.

b) X →→ Y ⇔ dom(Vi, Z) = dom(V i

j , Z), với mọi 1 ≤ i ≤ m, 1 ≤ j ≤ ni.

Chứng minh.

a) Hiển nhiên đúng xuất phát từ định nghĩa của phụ thuộc hàm và (3.3)-(3.4).

b) (⇒) Giả sử X →→ Y . Vì bao hàm thức dom(Vi, Z) ⊃ dom(V i

j , Z) là hiển

nhiên, nên ta chỉ cần chứng minh dom(Vi, Z) ⊂ dom(V i

j , Z), với mọi i, j. Thật vậy,

nếu α ∈ dom(Vi, Z) thì ∃v ∈ Vi sao cho v(Z) = α. Lấy u ∈ V i

j suy ra u ∈ Vi hay

u(X) = v(X). Vì X →→ Y nên tồn tại t ∈ Vi sao cho t(Y ) = u(Y ) (nên t ∈ V i

j ) và

t(Z) = v(Z) = α. Vậy α ∈ dom(V i

j , Z).

Định lý sau cho ta các đặc trưng của phụ thuộc hàm và phụ thuộc đa trị.

j , Z), với mọi i, j. Lấy hai đối tượng bất kỳ

(⇐) Giả sử dom(Vi, Z) = dom(V i

u, v ∈ U mà u(X) = v(X), gọi i và j là các chỉ số sao cho u, v ∈ Vi và u ∈ V i

v ∈ Vi nên α = v(Z) ∈ dom(V i, Z) = dom(V i

j . Vì j , Z). Nghĩa là tồn tại đối tượng t ∈ V i j j nên t(X) = u(X) = v(X) và t(Y ) = u(Y ). Hơn nữa

sao cho t(Z) = α. Vì t, u ∈ V i

Ví dụ 3.1. Cho hệ thống quản lý các môn học của sinh viên với tập thuộc tính

t(Z) = v(Z). Vậy X →→ Y .

A = {a1, a2, a3, a4} trong đó a1, a2, a3, a4 lần lượt lưu môn học, mã sinh viên, tên

sinh viên, lớp.

U a1 a2 a3 a4

T01 101 G K1 u1

T01 102 H K1 u2

T01 103 I K1 u3

T01 104 J K1 u4

T02 101 G K1 u5

T02 102 H K1 u6

T02 103 I K1 u7

T05

201 E K2

202 F K2

u10 T05

203 K K2

u11 T05

201 E K2

u12 T06

202 F K2

u13 T06

203 K K2

u14 T06

Bảng 3.1: Bảng dữ liệu sinh viên.

Từ hệ thống trên, đặt X = {a2}; Y = {a3} ta có:

U/X = {V1 = {u1, u5}; V2 = {u2, u6}; V3 = {u3, u7}; V4 = {u4, u8}; V5 =

{u9, u12};

T02 104 J K1 u8

V6 = {u10, u13}; V7 = {u11, u14}}.

Mặt khác, Vi/Y = {Vi}, với mọi 1 ≤ i ≤ 7. Do đó X → Y

Bây giờ ta xét X = {a4} và Y = {a1}. Rõ ràng X →→ Y . Chúng ta sẽ kiểm

tra điều này theo kết quả của Định lý 3.1.

Đặt Z = A \ (X ∪ Y ) = {a2, a3}, ta có

U/X = {V1 = {u1, u2, u3, u4, u5, u6, u7, u8}; V2 = {u9, u10, u11, u12, u13, u14}}

2 = {u5, u6, u7, u8}}

1 = {u1, u2, u3, u4}; V 1

V1/Y = {V 1

2 = {u12, u13, u14}}

1 = {u9, u10, u11}; V 2

V2/Y = {V 2

dom(V1, Z) = {(101, G), (102, H), (103, I), (104, J)}

1 , Z) = {(101, G), (102, H), (103, I), (104, J)} = dom(V1, Z)

dom(V 1

2 , Z) = {(101, G), (102, H), (103, I), (104, J)} = dom(V1, Z)

dom(V 1

dom(V2, Z) = {(201, E), (201, F ), (201, G)}

1 , Z) = {(201, E), (201, F ), (201, G)} = dom(V2, Z)

dom(V 2

2 , Z) = {(201, E), (201, F ), (201, G)} = dom(V2, Z)

Vậy X →→ Y.

3.2.2. Đặc trưng phụ thuộc bằng ma trận phụ thuộc

Trong phần này chúng tôi trình bày thuật toán tìm tất cả vế phải của phụ

thuộc đa trị X →→ Y và thuật toán kiểm tra phụ thuộc đa trị xấp xỉ chấp nhận

được với sai số bé hơn hoặc bằng một giá trị ngưỡng không âm cho trước. Trước

tiên, chúng tôi đưa vào khái niệm ma trận phụ thuộc nhằm cung cấp một công cụ

mới cho việc kiểm định phụ thuộc đa trị một cách dễ dàng đồng thời mở ra một

cách tiếp cận mới với phụ thuộc xấp xỉ. Trong mục trước, chúng ta đã đưa ra điều

kiện cần và đủ để X →→ Y đúng. Dựa vào kết quả đó, chúng ta sẽ xây dựng thuật

dom(V 2

toán khả thi để kiểm tra một phụ thuộc đúng bằng sự phân hoạch trên các giá trị

thuộc tính.

Vẫn ký hiệu U/X = {V1, V2, · · · , Vm}. Với mỗi i cố định, ta ký hiệu dom(Vi, Z) =

1 , V i

2 , · · · , V i

q } (tức là q = ni), chúng ta sẽ thiết lập một

{α1, α2, · · · , αp}, Vi/Y = {V i

ma trận phụ thuộc Di = (drs)p×q được định nghĩa bởi

 

s , Z),



1 nếu αr ∈ dom(V i drs =

s , Z),

0 nếu αr 6∈ dom(V i

q X

p X

q X

và ký hiệu

r=1

s=1

r=1 Từ định nghĩa suy ra drs = 1 khi và chỉ khi có một đối tượng t ∈ V i

s mà t(Z) = αr.

q X

kDik = drs. drs =

s=1

Do đó tổng các số trên hàng thứ r của ma trận: drs chính là số các đối tượng

s ) có giá trị tại thuộc tính Z bằng αr, còn tổng các số

p X

trên cột thứ s:

drs lại chính là Card(V i

s ). Hiển nhiên kDik = Card(Vi). Nói cách

r=1

khác, số đối tượng của Vi chính là số các số 1 xuất hiện trong ma trận Di. Ta nói

ma trận Di là dầy đặc nếu drs = 1, với mọi r, s. Một điều thú vị là phụ thuộc đa

trị X →→ Y có thể được đặc trưng hoàn toàn bởi các ma trận Di. Điều đó được

khẳng định trong định lý sau

Định lý 3.2. X →→ Y ⇔ Di là ma trận dầy đặc với mọi i ∈ {1, 2, · · · , m}.

Chứng minh.

Giả sử X →→ Y . Theo Định lý 3.1, với mọi i ta có

dom(V i

1 ≤ s ≤ q = ni.

s , Z) = dom(Vi, Z) = {α1, α2, · · · , αp},

(nằm rãi rác trong các V i

Do đó, drs = 1 với mọi r, s, nên Di là ma trận dầy đặc.

s , Z). Vậy, dom(Vi, Z) = dom(V i

s , Z).

s (1 ≤ s ≤ q) ta có drs = 1 nên αr ∈ dom(V i V i Tức là X →→ Y .

Ngược lại, giả sử các Di đều là ma trận dầy đặc. Với mọi αr ∈ dom(Vi, Z) và

Dễ thấy X →→ Y khi và chỉ khi X →→Vi Y , ∀i = 1..m. Định lý 3.2 thực ra khẳng định rằng X →→Vi Y nếu và chỉ nếu Di là ma trận dầy đặc. Từ đó, nếu X →/→ Y thì có ít nhất một ma trận Di không dầy đặc hay nói cách khác, tồn tại

Vi mà X →/→Vi Y . Một câu hỏi khá tự nhiên là nếu các Di "gần dầy đặc" thì Y có

phụ thuộc xấp xỉ X hay không? Để đánh giá khả năng "gần dầy đặc" của họ ma

trận phụ thuộc, dưới đây chúng tôi sẽ đưa ra khái niệm về độ dầy đặc của một họ

ma trận.

Cho C và D là các ma trận chỉ chứa các giá trị 0 hoặc 1. Ta nói C là ma trận

con của D và ký hiệu là C ≺ D nếu C có thể thu được từ D bằng cách xoá đi một

số hàng và cột nào đó. Nếu D không phải là ma trận dầy đặc, ta cần tìm ma trận

k(D) := max (cid:8)kCk | C ≺ D và C dầy đặc(cid:9).

với kCk là tổng giá trị các phần tử của ma trận C. Bây giờ tương ứng với họ các

ma trận {D1, D2, · · · , Dm}, ta gọi độ dầy đặc của họ ma trận này là giá trị sau

m X

k(Di)

s(D1, D2, · · · , Dm) :=

i=1 m X

kDik

i=1

Rõ ràng, s(D1, D2, · · · , Dm) ≤ 1 và, từ Định nghĩa 3.1 và Định lý 3.1 ta có

s(D1, D2, · · · , Dm) = 1 ⇔ X →→ Y ⇔ g3(X →→ Y ) = 0.

Tổng quát hơn, ta có kết quả sau

con dầy đặc lớn nhất của D. Cụ thể, ta ký hiệu

Định lý 3.3.

s(D1, D2, · · · , Dm) = 1 − e(X →→ Y ).

Trước khi chứng minh định lý này, chúng ta cần làm rõ ý nghĩa của các ma

trận con C i ≺ Di. Như nhận xét sau Định lý 3.2, Di không dầy đặc khi và chỉ

khi X →/→Vi Y . Lúc đó, ta cần xoá một số đối tượng trong Vi để thu được tập

s , Z), với một s nào đó. Như vậy, để thu được tập hợp Wi ⊂ Vi có khả

Wi ⊂ Vi mà X →→Wi Y . Theo Định lý 3.1, tồn tại giá trị αr ∈ dom(Vi, Z) mà αr 6∈ dom(V i

năng thoả mãn phụ thuộc X →→Wi Y ta cần thực hiện một trong hai thao tác cơ

bản:

(A): Xoá tất các cả đối tượng t trong lớp V i s

(B): Xoá tất cả các đối tượng t ∈ Vi mà t(Z) = αr

Nếu thực hiện thao tác (A) thì tập Wi ⊂ Vi thu được sẽ tương ứng với ma trận

con C i nhận được từ Di bằng cách xoá đi cột s. Còn nếu thực hiện thao tác (B) thì

tập Wi ⊂ Vi thu được sẽ tương ứng với ma trận con C i nhận được từ Di bằng cách

C i. Số đối tượng phải xoá chính là tổng số phần tử có giá trị 1 trên các dòng và cột

của Di bị xoá. Tức là Card(Vi \ Wi) = kDik − kC ik, hay Card(Wi) = kC ik. Tóm

lại, việc tìm tập con Wi lớn nhất của Vi thoả mãn X →→Wi Y tương đương với việc tìm ma trận dầy đặc C i ≺ Di có kC ik cực đại (tức là kC ik = k(Di)).

Chứng minh Định lý 3.3. Từ những phân tích trên ta thấy, nếu gọi Wi là tập con

có số phần tử lớn nhất của Vi, thoả mãn X →→Wi Y , thì Card(Wi) = k(Di). Mặt

m X

khác, để ý rằng Card(U ) =

kDik. Nên từ Định nghĩa 3.1 ta có

i=1

m X

Card(Wi)

i=1

= 1 − s(D1, D2, · · · , Dm).

g3(X →→ Y ) = 1 −

m X

xoá đi hàng r. Như vậy, để có được phụ thuộc đúng X →→Wi Y chúng ta cần phải xoá đi các dòng và cột trên ma trận phụ thuộc Di để có được ma trận con dầy đặc

i=1

kDik

Định lý được chứng minh.

Để minh hoạ cho kết quả định lý trên, chúng ta xét hệ thống cho trong Bảng 3.2.

Trong đó,

U/X = {V1, V2}; V1 = {t1, t2, t3, t4, t5, t6, t7, t8, t9, t10}; V2 = {t11, t12},

1 , V 1

2 , V 1

3 };

1 = {t1, t2, t3, t4}; V 1 V 1

2 = {t5, t6, t7}; V 1

3 = {t8, t9, t10},

V1/Y = {V 1

dom(V1, Z) = {α1, α2, α3, α4, α5}

1 , Z) = {α1, α2, α3, α4}

dom(V 1

2 , Z) = {α3, α4, α5}

dom(V 1

3 , Z) = {α1, α2, α4}

dom(V 1

1 , V 2

2 }; V 2

1 = {t11}; V 2

2 = {t12},

V2/Y = {V 2

1 , Z) = dom(V 2

2 , Z) = {α5}.

dom(V2, Z) = dom(V 2

1 A α1

1 A α2

1 A α3

1 A α4

1 B α3

1 B α4

1 B α5

1 C α1

1 C α2

t10

1 C α4

t11

2 B α5

t12

2 C α5

U X Y Z

Bảng 3.2: Dữ liệu của hệ thống.





1 V 1 V 1

2 V 1 3

Hai ma trận D1 và D2 lần lượt được thiết lập như sau





1 1 0 α1

1 V 2 V 2 2



 .

1 1 0 α2 D1 = ; D2 = 0 1 1 1 1 α3 α5

            

            

1 1 1 α4

0 0 1 α5

kiểm chứng được các ma trận con dầy đặc lớn nhất của D1 và D2 là

Rõ ràng, D2 dầy đặc. Tuy vậy, D1 không dầy đặc nên X →/→ Y trên U . Có thể

1 V 1 V 1 3

 

α1

1 V 2 V 2 2

; C 2 =

C 1 =

 

α5

α2

  .

α4

Điều đó tương ứng với việc xoá hoàn toàn lớp V 1

2 = {t5, t6, t7}, các đối tượng

trong V1 có t(Z) = α3 là {t3, t5}, có t(Z) = α5 là {t7} (tổng số có 4 đối tượng cần

xoá). Độ dầy đặc của {D1, D2} là

s(D1, D2) =

kC 1k + kC 2k kD1k + kD2k

8 12

2 3

             

Do đó, ta có sai số phụ thuộc g3(X →→ Y ) = 1 −

1 3

2 3

. =

Từ Định lý 3.3 và ví dụ trên ta thấy, chỉ cần làm việc trên các ma trận phụ

thuộc, cụ thể là từ giá trị độ dầy đặc của họ ma trận phụ thuộc, chúng ta có thể

tính được sai số phụ thuộc và từ đó khẳng định phụ thuộc có chấp nhận được hay

không. Trong phần sau chúng ta sẽ bàn chi tiết vấn đề này.

3.3. Thuật toán kiểm định và tìm kiếm phụ thuộc

3.3.1. Thuật toán tính độ dầy đặc của dãy ma trận

Bài toán đặt ra đầu tiên là với dãy ma trận {D1, D2, · · · , Dm} cho trước, hãy xác

định độ dầy đặc của chúng. Từ định nghĩa ta thấy việc xác định s(D1, D2, · · · , Dm)

chủ yếu dựa vào việc tính giá trị k(Di). Vì vậy, chúng tôi sẽ tập trung xây dựng

thuật toán tìm kiếm các ma trận dầy đặc C i ≺ Di sao cho kC ik = k(Di).

dụ cụ thể. Chúng ta hãy khảo sát lại hệ thống được cho trong Bảng 3.2. Ta cần

phải xác định các ma trận dầy đặc C 1 và C 2, lớn nhất có thể, sao cho C 1 ≺ D1 và

C 2 ≺ D2. Trong ma trận D1, chúng ta cần cân nhắc xem nên giữ lại số drs nào cho

ma trận C 1. Rõ ràng, các giá trị drs = 0 (như d1,2, d2,2...) bắt buộc phải được loại

bỏ. Đối với các drs = 1 chúng ta thử tính toán xem cần loại bỏ tối thiểu bao nhiêu

số 1 khác trong ma trận nếu quyết định giữ lại vị trí này. Chẳng hạn, đối với d1,1.

Nếu cho phép d1,1 ∈ C 1 thì bắt buộc phải loại đi cột 2 (V 1

2 ) và dòng 5 (α5) (vì nếu

đã giữ lại d1,1 mà còn giữ lại dòng 5 hoặc cột 2 thì ma trận thu được không dầy

đặc), do đó số giá trị 1 cần xoá ít nhất là 3. Ta đặt g1,1 = 3 và gọi đó là hệ số loại

bỏ của d1,1. Tương tự, đối với d5,2, nếu muốn giữ lại vị trí này cho C 1 ta cần xoá các

cột 1, 3 và các dòng 1, 2, nên phải xoá ít nhất là g5,2 = 7 số 1. Rõ ràng là những vị

trí có hệ số loại bỏ càng bé càng cần được ưu tiên giữ lại cho ma trận C 1. Một cách

Để dễ hình dung, chúng tôi trình bày ý tưởng thuật toán thông qua một ví

tự nhiên, ta gán grs = ∞ cho các vị trí drs = 0. Cuối cùng ta nhận được ma trận





2 V 1 3

G1, gọi là ma trận hệ số loại bỏ của D1:   V 1 1 V 1 V 1 1 V 1

1 1 0 3 ∞ 4 α1 α1

5 ∞

α3

1 1 0 3 ∞ 4 α2 α2 D1 = → G1 =

            

            

            

1 1 1 1 4 3 α4 α4

0 0 1 α5 α5 ∞ 7 ∞

Nhìn vào ma trận này ta thấy vị trí (4, 1) có hệ số loại bỏ bé nhất (g4,1 = 1) nên

quyết định giữ lại vị trí này. Điều đó dẫn đến việc phải xoá đi dòng 5, ma trận D1





1 V 1 V 1

2 V 1 3

trở thành (số 0 in đậm cho biết vị trí mới bị xoá).

1 0 1 α1

1 0 1 α2 D1 = 1 1 0 α3

            

            

α5

Từ đây, tính lại ma trận hệ số G1, chọn giữ lại vị trí có hệ số (dương) bé nhất, xoá

các dòng cột thích hợp rồi viết lại ma trận D1, tính ma trận G1... Quá trình lặp này

kết thúc khi ta nhận được ma trận G1 chỉ chứa các giá trị 0 và ∞. Cụ thể, tiếp tục

thao tác đối với ma trận trên ta được

1 1 1 α4

2 V 1 3

1 V 1 V 1

2 ∞ 3

α1

2 ∞ 3

α2

,→ G1 =

→ D1 =

→

5 ∞

α3

α4

   

α5 ∞ ∞ ∞

α5







1 V 1 V 1

2 V 1 3

1 V 1 V 1

2 V 1 3

                                                   

0 ∞ 1 1 1 0 α1 α1

0 ∞ 1 1 1 0 α2 α2 ,→ G1 = → D1 = → 3 ∞ ∞ 0 0 0 α3 α3

            

            

            

α5 ∞ ∞ ∞

α5

0 ∞ 1 1 1 0 α4 α4





2 V 1 3

1 V 1 V 1

0 ∞ 0 α1

0 ∞ 0 α2 ,→ G1 = . α3 ∞ ∞ ∞

            

            

0 ∞ 0 α4

α5 ∞ ∞ ∞

Cuối cùng ta nhận được ma trận con dầy đặc C 1 gồm sáu số 1. Đó cũng chính

D2 thì cũng bằng kỹ thuật như trên ta thu được G2 = (0 0). Nên C 2 = D2 và

k(D2) = kC 2k = 2.

Bây giờ chúng tôi sẽ đưa ra thuật toán tìm các k(Di). Trước hết, đối với mỗi

ma trận phụ thuộc Di, chúng ta cần xây dựng ma trận hệ số phụ thuộc Gi (thủ tục

Compute_Gi). Một cách tổng quát, ma trận Gi = (grs) được xây dựng như sau:

Nếu drs = 0 thì đặt grs = ∞, ngược lại, nếu drs = 1 thì grs là tổng số các số 1

tối thiểu cần phải loại để giữ lại số 1rs trong ma trận phụ thuộc Di, những số 1

chắc chắn bị loại là những số nằm trên dòng u mà dus = 0 hoặc nằm trên cột v mà

drv = 0. Nói cách khác, khi giữ lại số 1rs thì phải loại các số 1uv nếu dus ∗ drv = 0.

Tóm lại, ta có

∞

nếu drs = 0,

là số các giá trị 0 còn lại trong ma trận G1. Lúc đó, k(D1) = kC 1k = 6. Đối với

grs =

dus×drv=0

  X duv nếu drs = 1. 

Rõ ràng, grs = ∞ nếu drs = 0, grs = 0 nếu drs = 1 và việc giữ lại vị trí này

không đòi hỏi phải xoá đi bất kỳ số 1 nào. Cuối cùng, grs = l > 0 nếu drs = 1 và

việc giữ lại vị trí này đòi hỏi phải xoá đi ít nhất l số 1 khác.

0 sẽ xác định một ma trận con dầy đặc của Di, thuật toán dừng. Trong trường hợp

Nếu ma trận Gi chỉ gồm các giá trị 0 và ∞ thì các vị trí tương ứng với giá trị

ngược lại, chúng ta cần xác định vị trí 1hv với ghv > 0 đáng được giữ lại nhất. Với ý

nghĩa của các grs như đã phân tích trên, rõ ràng vị trí này cần thoả mãn điều kiện

ghv = min{grs | grs > 0}.

Với quyết định giữ lại giá trị 1hv ta phải xoá đi các số 1rs liên quan (tức là thoả

mãn dhs ∗ drv = 0) và nhận được ma trận Di mới (thủ tục Modify_Di). Quá trình

tiếp tục cho đến khi nhận được ma trận Gi chỉ gồm các giá trị 0 và ∞. Thuật toán

được trình bày chi tiết như sau:

Thuật toán 3.1. Xác định k(Di)

Output: k(Di).

Method:

1. k := kDik;

2. Compute_Gi;

3. Xác định ghv = min{grs | grs > 0};

4. Nếu ghv = ∞ thì Output k và dừng; Ngược lại, sang 5;

5. k := k − ghv;

6. Modify_Di;

7. Quay lại 2;

Proc Compute_Gi

Input: Di.

1. For r ∈ {1..pi}; s ∈ {1..qi} do

2. If drs = 0 then grs := ∞

Else 3.

Begin 4.

5. grs := 0;

6. For u ∈ {1..pi}; v := {1..qi} do

7. If dus ∗ drv = 0 then

8. grs := grs + duv;

9. End

EndProc Compute_Gi;

Proc Modify_Di

1. For r ∈ {1..pi}; s ∈ {1..qi} do

drs := 0.

EndProc Modify_Di

độ phức tạp tính toán O(p2

i q2 O(piqi). Do đó, độ phức tạp của mỗi vòng lặp là O(p2

Giả sử ma trận Di có kích thước pi × qi. Lúc đó, thủ tục Compute_Gi có i ), còn thủ tục Modify_Di có độ phức tạp tính toán i q2 i ) và thuật toán xác định

k(Di) có độ phức tạp tính toán trong trường hợp xấu nhất là O(p3

i ). Chú ý rằng,

i q3 nếu ký hiệu xi = Card(Vi) = kDik thì ta có ước lượng: xi ≤ piqi ≤ x2 i .

3.3.2. Thuật toán kiểm định phụ thuộc xấp xỉ

Trong phần này, chúng ta sẽ đánh giá xem với hai tập thuộc tính đã cho

2. If drv ∗ dhs = 0 then

X, Y ⊆ A, phụ thuộc X →→ Y có chấp nhận được với một sai số (cid:15) hay không.

Từ Định lý 3.2 và Định lý 3.3, chúng ta thấy rằng, phụ thuộc X →→ Y là chấp

m X

nhận được nếu s(D1, D2, · · · , Dm) ≥ 1 − (cid:15). Tức là

i=1

k(Di) ≥ (1 − (cid:15)) Card(U ).

Thuật toán được xây dựng như sau

Thuật toán 3.2. Kiểm tra phụ thuộc chấp nhận được

Input: Hệ thống thông tin A = (U, A),

Các tập X, Y ⊆ A; Giá trị ngưỡng (cid:15) ≥ 0.

Output: g3(X →→ Y ) ≤ (cid:15) ?

Method:

1. s := 0;

2. OK:= TRUE;

4. Begin

Xây dựng Di;

s := s + k(Di);

If s ≥ (1 − (cid:15)) × Card(U ) then Exit;

8. End;

9. OK:= FALSE;

Trong thuật toán trên, m chính là số lớp tương đương của IN D(X). Giả sử

Card(U ) = n và mỗi ma trận Di có kích thước pi × qi. Khi đó việc xây dựng các

ma trận Di có thể thực hiện bằng cách sắp xếp các đối tượng trong U , vì vậy độ

phức tạp của thuật toán xây dựng dãy các ma trận Di là O(nlogn) và độ phức tạp

của thuật toán kiểm chứng phụ thuộc xấp xỉ được xác định bởi vòng lặp For ở 3.

3. For i ∈ {1..m} do

Thực chất ở đây chúng ta thực hiện hai vòng lặp, một vòng lặp xây dựng các Di và

m X

một vòng lặp tính sai số phụ thuộc. Vòng lặp tính sai số phụ thuộc có độ phức tạp

i q3 p3

i ). Vì piqi ≤ x2

i , nên độ phức tạp tính toán

i=1

m X

trong trường hợp xấu nhất là O(

i=1

của Thuật toán 3.2 không vượt quá O(nlogn + x6 i ).

3.3.3. Thuật toán tìm kiếm phụ thuộc tối tiểu vế phải

Một phụ thuộc X →→ Y được gọi là tối tiểu vế phải và ký hiệu X→→minY nếu

với mọi Y 0 ⊂ Y , X →/→ Y 0. Ta đã biết rằng, nếu X →→ Y thì Y = Y1 ∪ Y2 ∪ · · · ∪ Yn

với X→→minYi với mọi 1 ≤ i ≤ n. Vì vậy, trong phần này chúng tôi chỉ đặt vấn

đề tìm kiếm tất cả các phụ thuộc tối tiểu vế phải với vế trái X là một tập con cho

trước các thuộc tính.

Thuật toán chúng tôi sắp đề nghị sử dụng một phần ý tưởng của Thuật toán

thường dạng X \ {c} → c. Cụ thể, chúng tôi sẽ tìm các tập con Y ⊆ A thoả mãn

X→→minY theo thứ tự tăng dần của Card(Y ). Nghĩa là, việc tìm kiếm vế phải của

phụ thuộc xuất phát từ họ các tập có một phần tử, tập có hai phần tử ...

Gọi Li là họ các tập thuộc tính Y có kích thước i và có khả năng thoả X →→ Y .

Vì X→→minY thì X ∩ Y = ∅ nên chúng ta khởi tạo L1 := {{a} | a ∈ A \ X}. Hơn

nữa, nếu Y ∈ Li và X→→minY thì Y không thể là tập con của tập Y 0 ∈ Lj với

j > i mà X→→minY 0, nói cách khác, Y sẽ không tham gia vào việc xây dựng họ

Lj, với mọi j > i. Vì vậy ở đây chúng tôi dùng thêm họ Mi lưu các tập Z ∈ Li mà

X →/→ Z và xây dựng họ Li+1 dựa vào Mi. Cụ thể, sau khi tìm tất cả các phụ thuộc

X→→minY với Y ∈ Li, chúng ta xây dựng Li+1 bằng cách lấy hợp hai tập bất kỳ

Y1, Y2 ∈ Mi, nếu hợp này cho ta một tập có i + 1 phần tử thì đưa nó vào Li+1. Rõ

ràng, ban đầu chúng ta cần khởi tạo Mi bằng Li, và sau đó mỗi khi có một phụ

Tane [25] được các tác giả này thiết kế nhằm tìm các phụ thuộc hàm không tầm

thuộc X →→ Y đúng với Y ∈ Li thì loại Y khỏi Mi.

Cuối cùng, nếu Z = A \ (X ∪ Y ) thì từ X →→ Y ta cũng có X →→ Z và

Card(Y ) + Card(Z) = Card(A \ X). Vì vậy quá trình tìm kiếm của chúng tôi chỉ

diễn ra trong các họ Li với i ≤ Card(A \ X)/2.

Thuật toán 3.3. Tìm kiếm tất cả phụ thuộc tối tiểu.

Input: Hệ thống thông tin A = (U, A),

Tập con X ⊆ A.

Output: Tất cả phụ thuộc X→→minY.

Method:

1. i := 1;

2. L1 := {{a} | a ∈ A \ X};

3. While i ≤ Card(A \ X)/2 do

4. Mi := Li;

If X →→ Y then

Output X→→minY ;

Mi := Mi \ {Y };

EndIf;

EndFor;

10.

11.

Compute_Li+1;

i := i + 1;

12.

13. EndWhile;

Proc Compute_Li+1

Li+1 := ∅;

5. For Y ∈ Mi do

2. For X, Y ∈ Mi, X 6= Y do

Z := X ∪ Y ; 3.

If Card(Z) = i + 1 then 4.

5. Li+1 := Li+1 ∪ {Z};

EndIf; 6.

EndFor; 7.

EndProc Compute_Li+1;

Độ phức tạp tính toán của thuật toán này được xác định bởi vòng lặp While ở

3. Tại mỗi bước của vòng lặp, chúng ta xét tất cả các phần tử của Mi và kiểm tra

k là tổ hợp k

k (C i

phụ thuộc, sau đó tính Li+1 theo Mi. Chú ý rằng Card(Mi) ≤ C i

m X

chập i phần tử, với k = Card(A \ X)). Mặt khác, độ phức tạp của thuật toán kiểm

i=1

tra phụ thuộc là O(nlogn + x6 i ), còn độ phức tạp của thủ tục Compute_Li+1

Card(Mi)) = O(Card(Mi)2). Vì vậy độ phức tạp tính toán của Thuật toán 3.3

k/2 X

m X

trong trường hợp xấu nhất là O(

C i

k × (nlogn +

i )) = O(2k/2 × (nlogn + x6

i=1

m X

x6 i )). Trong đó, k = Card(A \ X), n = Card(U ), m là số lớp tương đương của

i=1 IN D(X) và xi là lực lượng của lớp tương đương Vi, 1 ≤ i ≤ m.

3.4. Mở rộng phụ thuộc hàm và phụ thuộc đa trị

Trong ví dụ về dữ liệu sinh viên cho trong Bảng 3.1, các thuộc tính mã sinh

viên, họ tên là phụ thuộc đa trị vào thuộc tính lớp, nghĩa là mọi sinh viên trong

cùng một lớp sẽ phải học các môn như nhau. Đó là theo cách đào tạo niên chế. Bây

giờ, nếu nhà trường đào tạo theo tín chỉ, trong đó có một số học phần tự chọn, và

với mỗi học phần như vậy các sinh viên trong một lớp có thể học các môn khác

là O(C 2

nhau (nhưng được xem là tương đương), thì chúng ta vẫn có lý do để nói rằng các

thuộc tính mã sinh viên, họ tên phụ thuộc đa trị vào thuộc tính lớp, mặc dù lúc

này điều kiện (3.2) không còn đúng nữa. Rõ ràng là trong trường hợp này các định

nghĩa như trên không còn phù hợp. Mặt khác, trong thực tế không hiếm khi những

dữ liệu thu nhận được không còn chính xác như vốn có. Điều này chắc chắn cũng

làm cho chúng ta không phát hiện hết mọi phụ thuộc từ cơ sở dữ liệu.

Để góp phần phát hiện các phụ thuộc tiềm ẩn trong dữ liệu, trong phần này

chúng tôi sẽ cố gắng đưa ra một cách tiếp cận mở rộng của các khái niệm phụ thuộc

hàm và phụ thuộc đa trị. Các khái niệm mở rộng này được thiết lập dựa trên một

hàm đánh giá độ tương tự giữa các giá trị trong bảng dữ liệu, cũng gần như nhát cắt

được trình bày trong [9]. Tuy nhiên các tác giả trong [9] xây dựng các nhát cắt như

một quan hệ tương đương, do đó hai giá trị có quan hệ với nhau có thể khác biệt

rất lớn vì tính chất bắc cầu suy dẫn sẽ dẫn đến điều đó, trong khi nhiều ứng dụng

thực tế không đòi hỏi điều này, thậm chí khó có thể đáp ứng được. Trong cách xây

dựng của chúng tôi, khi sự tương tự giữa hai giá trị đạt đến một mức độ nhất định,

chúng ta có thể xem hai giá trị này là “đồng nhất“. Với cách tiếp cận này, các phụ

mở rộng nào đó, chúng tôi cũng sẽ sử dụng một kiểu ma trận phụ thuộc tương tự

như đã làm để kiểm tra phụ thuộc trong Mục 3.2. trong phần phụ thuộc xấp xỉ.

3.4.1. Quan hệ tương tự

Cho hệ thống thông tin A = (U, A). Với mỗi V ⊆ U và X ⊆ A, ta gọi miền giá

trị của V trên X là tập hợp

dom(V, X) := {u(X) | u ∈ V }.

Khi V = U ta viết dom(X) thay cho dom(U, X) và hơn nữa, nếu X = {a}, ta chỉ

viết một cách đơn giản: Ia = dom({a}).

Để mở rộng các khái niệm phụ thuộc, trên các tập giá trị Ia, ngoài quan hệ

thuộc thực ra cũng là một kiểu phụ thuộc xấp xỉ. Để kiểm chứng một phụ thuộc

bằng nhau thông thường ta giả định là tồn tại một quan hệ tương tự, phản ánh độ

gần nhau giữa các giá trị. Một cách chính xác, một ánh xạ s : Ia × Ia → [0, 1] được

gọi là quan hệ tương tự trên tập Ia nếu hai điều kiện sau thỏa mãn:

a) s(a1, a2) = s(a2, a1), với mọi a1, a2 ∈ Ia,

b) s(a1, a2) = 1 ⇔ a1 = a2.

s(a1, a2) được gọi là độ tương tự giữa hai giá trị a1 và a2. Cho α ∈ [0, 1], hai giá trị

a1 và a2 được gọi là α−tương tự, và ký hiệu a1 =α a2, nếu s(a1, a2) ≥ α. Rõ ràng

khi hàm s chỉ nhận hai giá trị 0 và 1, thì với mọi α > 0, a1 =α a2 khi và chỉ khi

a1 = a2.

Cho tập thuộc tính B = {b1, b2, · · · , bm} ⊆ A và ξ, η ∈ dom(B). Khi đó ξ và η

có thể xem là hai dãy (ξ1, ξ2, · · · , ξm) và (η1, η2, · · · , ηm), với ξi, ηi ∈ Ibi, 1 ≤ i ≤ m.

Độ tương tự giữa ξ và η được định nghĩa là giá trị:

(3.5) S(ξ, η) = min{s(ξi, ηi) | 1 ≤ i ≤ m}.

Bây giờ, giả sử ξ ∈ dom(B) và E ⊆ dom(B), ta gọi độ thuộc của ξ vào E là độ

bởi:

S(ξ, η).

µ(ξ, E) = max η∈E

Một cách tự nhiên, ta tiếp tục dùng ký hiệu ξ =α η nếu S(ξ, η) ≥ α và nói rằng

ξ và η là α−tương tự. Cũng vậy, ta nói ξ thuộc vào tập E với mức α, và ký hiệu

ξ ∈α E, nếu µ(ξ, E) ≥ α. Mệnh đề dưới đây cho ta một số tính chất cơ bản của các

khái niệm này mà việc chứng minh có thể được suy ra trực tiếp từ định nghĩa.

Mệnh đề 3.4. Cho B ⊆ A, E ⊆ dom(B), ξ, η ∈ dom(B), ta có

a) S(ξ, η) = S(η, ξ); S(ξ, η) = 1 ⇔ ξ = η.

b) 0 ≤ µ(ξ, E) ≤ 1; µ(ξ, E) = 1 ⇔ ξ ∈ E.

tương tự lớn nhất giữa ξ với các giá trị trong E. Cụ thể, giá trị này được xác định

c) Nếu E ⊆ E0 ⊆ dom(B), thì µ(ξ, E) ≤ µ(ξ, E0).

d) ξ ∈α E ⇔ ∃η ∈ E, ξ =α η.

Ví dụ 3.2. Xét hệ thống với ba thuộc tính: a (tên lập trình viên), b (trình độ chuyên

tự giữa các giá trị trong từng thuộc tính được cho bởi Bảng 3.4 và Bảng 3.5.

môn), c (ngôn ngữ lập trình sử dụng) được cho trong Bảng 3.3, còn quan hệ tương

a b c

A Đại học PASCAL

A Đại học FORTRAN

A Đại học COBOL

A Trung cấp PASCAL

A Trung cấp C

A Thạc sĩ

COBOL

A Thạc sĩ

PASCAL

B Đại học

PASCAL

Bảng 3.3: Bảng dữ liệu về các lập trình viên

Đại học Trung cấp Thạc sĩ

Đại học

0.8

0.6

Trung cấp

0.6

0.3

Thạc sĩ

0.8

0.3

Bảng 3.4: Quan hệ tương tự trên Ib

A Trung cấp FORTRAN

FORTRAN COBOL PASCAL C c

FORTRAN 1 0.7 0.8 0.9

COBOL 0.9 0.7 0.6 1

PASCAL 0.7 1 0.8 0.7

C 0.8 0.6 1 0.6

Bảng 3.5: Quan hệ tương tự trên Ic

Đặt B = {b, c}, ξ= (Đại học, FORTRAN), η= (Thạc sĩ, COBOL), với ξ, η ∈

dom(B), ta có

S(ξ, η) = min{s(Đại học, Thạc sĩ), s(FORTRAN, COBOL)}

= min{0.8, 0.9} = 0.8.

Mặt khác, với E ={Đại học,Trung cấp} ⊆ Ib và Thạc sĩ ∈ Ib, ta có

µ(Thạc sĩ, E) = max{s(Thạc sĩ, Đại học), s(Thạc sĩ, Trung cấp)}

Như vậy, ξ =0.8 η và Thạc sĩ ∈0.8 E.

3.4.2. Phụ thuộc mở rộng và các tính chất

Dựa trên quan hệ α−tương tự trên các tập giá trị, chúng ta sẽ đưa ra các khái

niệm phụ thuộc hàm và phụ thuộc đa trị mở rộng. Một cách chính xác, chúng ta có

các định nghĩa sau

Định nghĩa 3.2. Cho X, Y ⊆ A và α, β ∈ [0, 1]. Ta nói Y là (α, β)−phụ thuộc hàm

vào X trên U và ký hiệu X

α,β −→ Y nếu

∀u, v ∈ U : u(X) =α v(X) ⇒ u(Y ) =β v(Y ).

= max{0.8, 0.3} = 0.8.

Khi α = β = 1 ta nhận được định nghĩa phụ thuộc hàm kinh điển.

Định nghĩa 3.3. Cho X, Y ⊆ A (với X ∩ Y = ∅, X ∪ Y A) và α, β ∈ [0, 1]. Đặt

Z = A \ (X ∪ Y ). Ta nói Y là (α, β)−phụ thuộc đa trị vào X trên U , và ký hiệu

α,β →→ Y , nếu với mọi cặp đối tượng u, v ∈ U sao cho u(X) =α v(X), tồn tại đối

tượng t ∈ U sao cho t(X) =α u(X), đồng thời thỏa mãn một trong hai điều kiện

a) t(Y ) = u(Y ) và t(Z) =β v(Z),

b) t(Y ) =β u(Y ) và t(Z) = v(Z).

Rõ ràng, khi α = β = 1 hai điều kiện trên là đồng nhất và trùng với (3.2), nên

1,β −→ Y , ta gọi Y là β−phụ thuộc hàm vào X. Tương tự,

ta cũng nhận được khái niệm phụ thuộc đa trị kinh điển.

Khi α = 1, nếu X 1,β →→ Y thì Y được gọi là β−phụ thuộc đa trị vào X. X

Từ các định nghĩa mở rộng trên dễ kiểm tra được rằng, nếu 0 ≤ α ≤ α0 ≤ 1,

α,β −→ Y (X

α,β →→ Y ) kéo theo X

α0,β0 −→ Y (X

α0,β0 →→ Y ). Ngoài

và 0 ≤ β0 ≤ β ≤ 1 thì X

ra, một số tính chất của phụ thuộc hàm và phụ thuộc đa trị vẫn còn đúng đối với

Mệnh đề 3.5. Cho X, Y, Z ⊆ A, α, β ∈ [0, 1]. Khi đó

a) Nếu Y ⊆ X thì X

α,β −→ Y, với mọi 0 ≤ β ≤ α ≤ 1.

b) Nếu X

α,β −→ Y thì X ∪ Z

α,γ −→ Y ∪ Z, với γ = min{α, β}.

c) Nếu X

α,β −→ Y và Y

β,γ −→ Z, thì X

α,γ −→ Z.

d) Nếu X

α,β →→ Y và A \ (X ∪ Y ) 6= ∅ thì X

α,β →→ A \ (X ∪ Y ).

e) Nếu X

α,β −→ Y thì X

α,β →→ Y.

Chứng minh.

a) Hiển nhiên đúng vì nếu Y ⊆ X thì với mọi đối tượng u, v ∈ U , u(X) =α v(X)

kéo theo u(Y ) =β v(Y ).

các phụ thuộc mở rộng. Điều đó được khẳng định trong mệnh đề dưới đây

b) Với mọi cặp đối tượng u, v ∈ U nếu u(X∪Z) =α v(X∪Z) thì u(Z) =α v(Z) và

α,β −→ Y nên u(Y ) =β v(Y ). Do đó u(Y ∪ Z) =min{α,β} v(Y ∪ Z).

u(X) =α v(X). Vì X

α,γ −→ Y ∪ Z, với γ = min{α, β}.

Vậy X ∪ Z

α,γ −→ Z.

β,γ −→ Z, nên u(Z) =γ v(Z). Vậy X

c) Với mọi cặp đối tượng u, v ∈ U nếu u(X) =α v(X) thì u(Y ) =β v(Y ) do α,β −→ Y . Mặt khác, vì Y X

d) Không mất tính tổng quát, giả sử X ∩ Y = ∅. Khi đó, đặt Z = A \ (X ∪ Y ),

α,β →→ Y suy ra với mọi cặp đối tượng u, v ∈ U

thì Y = A \ (X ∪ Z). Từ X

α,β →→ Z.

mà u(X) =α v(X) thì tồn tại đối tượng t ∈ U sao cho t(X) =α u(X) và t(Y ) =

u(Y ), t(Z) =β v(Z) hoặc t(Y ) =β u(Y ), t(Z) = v(Z). Do đó X

α,β −→ Y nên với mọi cặp đối tượng u, v ∈ U

e) Đặt Z = A \ (X ∪ Y ). Do X

α,β →→ Y .

mà u(X) =α v(X) ta có v(Y ) =β u(Y ). Bằng cách chọn t = v ta nhận được

t(X) =α u(X), t(Z) = v(Z) và t(Y ) =β u(Y ). Vậy X

Ví dụ 3.3. Xét hệ thống A = (U, {X, Y, Z}) được cho trong Bảng 3.6, các quan hệ

tương tự trên VX, VY và VZ được cho trên Bảng 3.7.

(0.8,0.9) →→ Y .

U X Y Z

Bảng 3.6: Dữ liệu của hệ thống.

X x1

Khi đó, dễ thấy X →/→ Y . Nhưng X

Z Y y1 y2 y3 z1 z2 z3 1 0.8 0.6 0.3 x1 1 0.5 0.7 1 0.6 0.7 y1 z1 0.8 1 0.9 0.4 x2 05 1 0.9 06 1 0.8 y2 z2 0.6 0.9 1 0.4 x3 0.7 0.9 1 0.7 0.8 1 y3 z3 0.3 0.4 0.4 1 x4

Bảng 3.7: Các quan hệ tương tự trên IX, IY và IZ.

3.4.3. Đặc trưng β−phụ thuộc bằng ma trận phụ thuộc

Trong Mục 3.2. để nghiên cứu phụ thuộc đa trị, chúng ta đã thiết lập ma trận

phụ thuộc dựa vào phân hoạch trên các giá trị thuộc tính và đã chứng minh được

rằng, X →→ Y đúng khi và chỉ khi ma trận phụ thuộc là dầy đặc, tức là mọi phần

tử của ma trận đều có giá trị 1. Trong trường hợp ma trận phụ thuộc là gần đặc

(tức là chứa phần lớn các số 1), thì ta cũng nhận được một phụ thuộc đa trị xấp xỉ

(tức là bỏ đi một số ít đối tượng nào đó của bảng dữ liệu thì nhận được phụ thuộc

đúng). Trên cơ sở các kết quả này, một thuật toán kiểm chứng phụ thuộc và phụ

đó, ở đây chúng ta sẽ xây dựng một ma trận có vai trò tương tự trong việc xác định

β−phụ thuộc đa trị.

1,β →→ Y đúng

Giả sử X, Y ⊆ A và U/X = {U1, U2, · · · , Um}. Rõ ràng, X

trên U khi và chỉ khi X

1,β →→ Y đúng trên mọi Ui. Do đó, ở đây ta chỉ hạn chế

việc kiểm tra phụ thuộc trên mỗi Ui cố định. Ký hiệu Z = A \ (X ∪ Y ). Giả sử

dom(Ui, Y ) = {ξ1, ξ2, · · · , ξp(i)} và dom(Ui, Z) = {η1, η2, · · · , ηq(i)}. Với mỗi ξj, ηk ta

ký hiệu

Ej := {t(Z) | t ∈ Ui; t(Y ) = ξj} ⊆ dom(Ui, Z);

Fk := {t(Y ) | t ∈ Ui; t(Z) = ηk} ⊆ dom(Ui, Y ).

Ta gọi ma trận phụ thuộc mở rộng, tương ứng với lớp Ui, là Di = (djk)p(i)×q(i), với

thuộc xấp xỉ dựa vào ma trận phụ thuộc cũng đã được thiết lập. Phát triển ý tưởng

các thành phần djk được xác định bởi:

djk := max{µ(ξj, Fk), µ(ηk, Ej)}.

Ma trận Di được gọi là β−dầy đặc nếu với mọi j, k ta đều có djk ≥ β, hay, một

cách tương đương: hoặc ξj ∈β Fk hoặc ηk ∈β Ej.

Tương tự như phụ thuộc đa trị kinh điển, β−phụ thuộc đa trị cũng có thể được

đặc trưng hoàn toàn bằng họ các ma trận phụ thuộc mở rộng Di. Điều đó được

khẳng định trong định lý sau

Định lý 3.6. Y là β−phụ thuộc đa trị vào X khi và chỉ khi Di là β−dầy đặc, với

mọi 1 ≤ i ≤ m.

Chứng minh.

1,β →→ Y . Chúng ta sẽ chứng minh mọi Di đều là ma trận β−dầy đặc.

Giả sử X

Thật vậy, với mọi 1 ≤ j ≤ p(i) và 1 ≤ k ≤ q(i), tồn tại hai đối tượng u, v ∈ Ui sao

cho u(Y ) = ξj và v(Z) = ηk. Vì u và v cùng thuộc lớp Ui nên u(X) = v(X). Theo

định nghĩa của β−phụ thuộc đa trị, tồn tại đối tượng t ∈ Ui thoả mãn một trong

a) t(Y ) = u(Y ) = ξj và t(Z) =β v(Z) = ηk,

b) t(Y ) =β u(Y ) = ξj và t(Z) = v(Z) = ηk.

Nếu trường hợp a) xãy ra thì t(Z) ∈ Ej và ηk =β t(Z). Do đó, µ(ηk, Ej) ≥ β. Tương

tự, nếu b) xãy ra thì µ(ξj, Fk) ≥ β. Cả hai trường hợp đó đều dẫn đến djk ≥ β. Vì

điều này đúng với mọi djk nên Di là ma trận β−dầy đặc.

Ngược lại, giả sử mọi Di đều là ma trận β− dầy đặc. Cho hai đối tượng tuỳ

ý u, v ∈ U thoả mãn u(X) = v(X). Lúc đó, u và v phải thuộc cùng một lớp tương

đương Ui nào đó. Đặt ξj = u(Y ) và ηk = v(Z). Do djk ≥ β nên ta có

i) hoặc µ(ξj, Fk) ≥ β,

hai điều kiện sau

ii) hoặc µ(ηk, Ej) ≥ β.

Nếu i) đúng thì tồn tại t ∈ Ui sao cho t(Z) = ηk = v(Z) và t(Y ) =β ξj = u(Y ), còn

nếu ii) đúng thì tồn tại t ∈ Ui sao cho t(Y ) = ξj = u(Y ) và t(Z) =β ηk = v(Z).

1,β →→ Y

Trong cả hai trường hợp, t đều thoả mãn điều kiện của Định nghĩa 3.3. Vậy X

và định lý đã được chứng minh.

Ví dụ 3.4. Xét hệ thống A = (U, {X, Y, Z}) được cho trong Bảng 3.8, các quan hệ

tương tự trên VY và VZ được cho trên Bảng 3.9.

U X Y Z

t1 x1 y1 z1

Bảng 3.8: Bảng dữ liệu.

Y y1

0.5

0.7

0.6

0.7

0.9

0.8

0.7

0.9

0.7

0.8

t2 x1 y2 z1

Bảng 3.9: Các quan hệ tương tự trên IY và IZ.

1, 0.8 →→ Y .

Khi đó, ta có X

U/X = {U1, U2}, với U1 = {t1, t2, t3, t4, t5, t6} và U2 = {t7, t8}.

Trên lớp U1 ta có dom(U1, Y ) = {y1, y2, y3}, dom(U1, Z) = {z1, z2, z3} và

E1 = {t(Z) | t ∈ U1, t(Y ) = y1} = {z1, z2};

E2 = {t(Z) | t ∈ U1, t(Y ) = y2} = {z1, z3};

E3 = {t(Z) | t ∈ U1, t(Y ) = y3} = {z2, z3};

F2 = {t(Y ) | t ∈ U1, t(Z) = z2} = {y1, y3};

F3 = {t(Y ) | t ∈ U1, t(Z) = z3} = {y2, y3}.

Từ đó các phần tử của ma trận D1 được xác định bởi:

d11 = max{µ(y1, F1), µ(z1, E1)} = max{1; 1} = 1;

d12 = max{µ(y1, F2), µ(z2, E1)} = max{1; 1} = 1;

d13 = max{µ(y1, F3), µ(z3, E1)} = max{0.7; 0.8} = 0.8;

d21 = max{µ(y2, F1), µ(z1, E2)} = max{1; 1} = 1;

d22 = max{µ(y2, F2), µ(z2, E2)} = max{0.9; 0.8} = 0.9;

d23 = max{µ(y2, F3), µ(z3, E2)} = max{1; 1} = 1;

d31 = max{µ(y3, F1), µ(z1, E3)} = max{0.9; 0.7} = 0.9;

F1 = {t(Y ) | t ∈ U1, t(Z) = z1} = {y1, y2};

d32 = max{µ(y3, F2), µ(z2, E3)} = max{1; 1} = 1;

d33 = max{µ(y3, F3), µ(z3, E3)} = max{1; 1} = 1.

Tương tự, trên lớp U2 ta có dom(U2, Y ) = {y1}, dom(U2, Z) = {z1, z2} và bằng

tính toán đơn giản ta thu được các phần tử của ma trận D2 là d11 = d12 = 1. Tóm

lại, ta được





(cid:16)

(cid:17)

1 0.8 1

   

   

, D1 = D2 = . 1 1 0.9 1 1

1 0.9 1

3.4.4. Thuật toán kiểm định β−phụ thuộc đa trị

Từ Định lý 3.6, chúng ta thấy việc kiểm tra phụ thuộc dạng X

1,β →→ Y thực

chất là kiểm tra tính β−dầy đặc của tất cả các ma trân phụ thuộc mở rộng Di. Vì

vậy trước hết chúng ta cần xây dựng thuật toán tính các ma trận Di và sau đó sẽ

thiết lập thuật toán kiểm định β−phụ thuộc. Cũng cần lưu ý là họ các lớp tương

đương U/X = {U1, U2, · · · , Um} có thể nhận được sau một phép sắp xếp các đối

tượng trong U theo thứ tự các giá trị trong dom(X). Vì vậy, thuật toán sau chỉ tính

Di đối với một Ui cho trước.

Thuật toán 3.4. Tính Di.

Input:

Tập thuộc tính A, các tập con X, Y ⊆ A,

Rõ ràng với β ≤ 0.8 thì cả hai ma trận D1 và D2 đều β−dầy đặc. Do đó 1,β →→ Y , với mọi β ≤ 0.8. Trong khi đó, nếu β > 0.8 thì D1 không β−dầy đặc nên 1,β →/→ Y . X

Lớp tương đương thứ i của quan hệ IND(X): Ui,

Các quan hệ tương tự trên các thuộc tính.

Output: Di = (djk)p(i)×q(i).

Method:

1. Tính dom(Ui, Y ) = {ξ1, ξ2, · · · , ξp(i)}; dom(Ui, Z) = {η1, · · · , ηq(i)};

2. For j := 1 to p(i) do

3. For k := 1 to q(i) do

Begin 4.

5. d1 := 1; { µ(ξj, Fk)}

6. d2 := 1; { µ(ηk, Ej)}

7. For t ∈ Ui do

Begin 8.

9. If (t(Z) = ηk) and (S(ξj, t(Y )) < d1) then

11.

If (t(Y ) = ξj) and (S(ηk, t(Z)) < d2) then

12.

d2 := S(ηk, t(Z));

End.

13.

14.

djk := max{d1, d2};

End.

15.

Để tính dom(Ui, Y ) = {ξ1, ξ2, · · · , ξp(i)}; dom(Ui, Z) = {η1, · · · , ηq(i)}; chúng ta

có thể lần lượt thực hiện các thao tác sau:

1. Khởi tạo p(i) = q(i) = 0; dom(Ui, Y ) = dom(Ui, Z) = {};

2. For t ∈ Ui do

3. Begin

10. d1 := S(ξj, t(Y ));

4. If t(Y ) 6∈ dom(Ui, Y ) then

5. Begin

inc(p(i)); 6.

7. ξp(i) := t(Y );

8. dom(Ui, Y ) := dom(Ui, Y ) ∪ {ξp(i)};

9. End;

10. If t(Z) 6∈ dom(Ui, Z) then

Begin 11.

inc(q(i)); 12.

13. ηq(i) := t(Z);

14. dom(Ui, Z) := dom(Ui, Z) ∪ {ηq(i)};

15. End;

Sử dụng Thuật toán 3.4 ta nhận được thuật toán kiểm định β−phụ thuộc đa

trị như sau:

Thuật toán 3.5. Kiểm định β−phụ thuộc đa trị.

Input:

Tập đối tượng U ,

Tập thuộc tính A, các tập con X, Y ⊆ A,

Các quan hệ tương tự trên các thuộc tính,

Mức β ∈ [0, 1].

Output: X

1,β →→ Y ?

Method:

16. End.

1. Phân hoạch U/X = {U1, U2, · · · , Um};

2. OK:=True; i:=0;

3. Repeat

inc(i); 4.

Tính Di; 5.

6. If Di không β−dầy đặc then

7. OK:=False;

3.5. Kết luận

8. Until (Not OK) or (i = m).

Như vậy, bằng hai cách tiếp cận khác nhau, trong chương này chúng ta đã mở

rộng các khái niệm phụ thuộc hàm và phụ thuộc đa trị là những định nghĩa mở rộng

của các khái niệm phụ thuộc kinh điển. Các phụ thuộc này nói chung là các phụ

thuộc xấp xỉ của hệ thống. Cách thứ nhất, chúng ta thu hẹp miền tác động của phụ

được chấp nhận kèm theo đánh giá "sai số". Cách thứ hai, sử dụng quan hệ tương

tự giữa các giá trị của những thuộc tính, theo cách tiếp cận này, chúng ta đã đưa

ra các khái niệm (α, β)− phụ thuộc hàm và phụ thuộc đa trị, Việc đưa ra các khái

niệm mới này là thực sự có ý nghĩa trong thực tế bởi nhiều lý do khác nhau. Ngoài

việc chứng minh một số tính chất cơ bản của các phụ thuộc mở rộng, dựa vào ma

trận phụ thuộc, chúng tôi còn đưa ra được một tiêu chuẩn đại số để xác định một

phụ thuộc hàm, một phụ thuộc đa trị đồng thời đưa ra thuật toán tìm tất cả phụ

thuộc tối tiểu. Đối với các phụ thuộc theo nghĩa mở rộng, cũng bằng cách sử dụng

họ các ma trận phụ thuộc, chúng tôi đã đưa ra thuật toán kiểm định phụ thuộc

xấp xỉ và (1, β)− phụ thuộc đa trị. Đối với trường hợp α < 1, việc kiểm chứng phụ

thuộc đa trị sẽ phức tạp hơn và không thể dùng họ các ma trận phụ thuộc. Bởi vì

thuộc hàm và phụ thuộc đa trị, nếu miền này "đủ lớn" thì phụ thuộc tương ứng sẽ

họ này được xây dựng dựa trên các lớp tương đương của quan hệ không phân biệt

trên X, trong khi với α < 1 thì quan hệ α−tương tự không còn là quan hệ tương

đương nữa. Vì vậy trong vấn đề nghiên cứu mở rộng phụ thuộc đa trị, việc xây dựng

tiêu chuẩn kiểm định (α, β)−phụ thuộc với α và β tuỳ ý là một bài toán còn có thể

được tiếp tục nghiên cứu.

Chương

PHẦN KẾT LUẬN

Phát hiện luật theo tiếp cận của lý thuyết tập thô do Z. Pawlak [24] đề xuất

là một trong những phương pháp đang được nhiều nhà khoa học nghiên cứu và sử

dụng trong quá trình khai phá tri thức từ dữ liệu. Do dữ liệu thực tế thường đa

dạng, không đầy đủ, thiếu chính xác mà lại dư thừa nên việc chọn lọc thuộc tính

được đặt ra nhằm loại bỏ các thuộc tính dư thừa mà vẫn giữ được đầy đủ ý nghĩa

của bảng dữ liệu đang xét. Ngoài ra, việc phát hiện các mối ràng buộc vốn có trong

dữ liệu cũng cho các nhà nghiên cứu và quản lý có một cái nhìn đầy đủ hơn với dữ

liệu họ đang có. Đó là những vấn đề chính luận án nghiên cứu. Kết quả của luận án

có thể trình bày tóm lược như sau:

1. Xây dựng các thuật toán heuristic tìm tập rút gọn của bảng quyết định với độ

phức tạp theo thời gian là đa thức. Các thuật toán này được xây dựng trên cơ

sở đưa ra tiêu chuẩn đánh giá một tập con các thuộc tính điều kiện là tập rút

gọn. Hai thuật toán đầu dựa trên độ phụ thuộc của tập thuộc tính điều kiện và

khả năng đóng góp của một thuộc tính được tính toán chỉ trên các phép toán

được trên một tập thuộc tính cho trước. Ý tưởng của thuật toán này dựa trên

của đại số quan hệ. Thuật toán thứ ba dựa vào số cặp đối tượng phân biệt

ma trận phân biệt được. Tuy nhiên, kích thước của ma trận này rất lớn đối

với bảng dữ liệu lớn, vì vậy việc tìm kiếm tập rút gọn theo ma trận này như

phương pháp trình bày trong [26, 27] khó thực hiện. Thuật toán trong luận án

đề nghị không hề tính toán các phần tử của ma trận.

2. Xây dựng các thuật toán tìm tập rút gọn xấp xỉ dựa vào các thuật toán trong

Phần 1.

3. Thiết lập đặc trưng của phụ thuộc hàm và phụ thuộc đa trị bằng ma trận phụ

thuộc.

4. Đưa ra điều kiện cần và đủ cho phụ thuộc đa trị dựa vào quan hệ “không phân

trị xấp xỉ.

5. Xây dựng thuật toán tìm kiếm phụ thuộc đa trị tối tiểu vế phải.

6. Mở rộng phụ thuộc hàm và phụ thuộc đa trị dựa vào quan hệ tương tự trên

tập giá trị của các thuộc tính và đưa ra các tính chất của phụ thuộc mở rộng.

7. Đặc trưng β−phụ thuộc bằng ma trận phụ thuộc và đưa ra thuật toán kiểm

định β−phụ thuộc đa trị.

Các hướng có thể tiếp tục nghiên cứu

1. Đưa ra giải pháp rút gọn trên bảng dữ liệu thiếu thông tin.

biệt được“, từ đó xây dựng thuật toán kiểm định phụ thuộc và phụ thuộc đa

2. Xây dựng tiêu chuẩn đại số kiểm định phụ thuộc đa trị mở rộng trong trường

hợp tổng quát.

Tài liệu tham khảo

[1] Hoàng Thị Lan Giao (2005), “Một số thuật toán tìm tập rút gọn của bảng quyết

Tự nhiên và Công nghệ, Đại học Quốc gia Hà Nội, T.XXI (2PT), 41-48.

[2] Hồ Thuần, Hoàng Thị Lan Giao (2005), “Một thuật toán tìm tập rút gọn sử

dụng ma trận phân biệt được“, Chuyên san Các công trình nghiên cứu triển khai

Viễn thông và CNTT, (15), tr. 83-87.

[3] Hồ Thuần, Hoàng Thị Lan Giao (2006), “Khám phá phụ thuộc đa trị dựa vào

ma trận phụ thuộc“, Tin học và điều khiển(1), tr. .

[4] Hồ Thuần, Hoàng Thị Lan Giao (2006), “Mở rộng phụ thuộc hàm và phụ thuộc

đa trị“, Tin học và điều khiển (đã gửi đăng).

[5] Hoàng Thị Lan Giao (2006), “Khai phá luật theo tiếp cận tập thô“, Đề tài NCKH

định sử dụng các phép toán của đại số quan hệ“, Tạp chí Khoa học, Khoa học

cấp Bộ trọng điểm B2005-07-02 , nghiệm thu tháng 3/2006.

[6] Hà Quang Thuỵ (1996), Tập thô và đánh giá hệ thông tin nền, Tạp chí Khoa

học Đại học Quốc gia Hà Nội, KHTN, XII (3).

Tài liệu tiếng Anh

[7] Ho Tu Bao (1996), Introduction to Knowledge Discovery and Data Mining, Insti-

tude of Information Technology National Center for Natural Science and Tech-

nology.

[8] Shrabonti Ghosh, S.S.Alam (2003), “Generalized Rough Approach to Reduction

of a Decíion Table“, International Journal of Intelligent Systems Vol. 18, 499-508.

[9] Shrabonti Ghosh, Ranjit Biswas, S.S. Alam (2004), “Reduction of the Decision

Table: A Roughset Approach“, International Journal of Intelligent Systems, Vol

19.

[10] Paolo Guidici (2003), Applied Data Mining, Statistical Methods for Business

[11] Jiawei Han, Micheline Kamber (2001), Data Mining: Concepts and Techniques,

Morgan Kaupmann Publishers.

[12] Nguyen S. Hoa, Nguyen H. Son (1996), “Some Efficient Algorithms for Rough

Set Methods" Proceedings of the sixth International Conference on Information

Processing Management of Uncertainty in Knowledge-Based Systems, 1451-1456.

[13] Nguyen S. Hoa, Andrzej Skowron, Piotr Synak (1997), “Knowledge Discovery in

Databases: Rough Set Approach“ Proc. of the Seventh International Fuzzy Sys-

tems Association World Congress, Vol II, pp. 204-209, IFSA’97, Prague, Czech

Republic.

[14] Xiaohua Hu, Jianchao Han, T.Y.Lin (2004), “A New Rough Sets Model Based

on Database Systems" Fundamenta Informaticae XX 1-18.

and Industry, Faculty of Economics, University of Pavia, Italy.

[15] Yka Huhtala, Juha Karkkainen, Pasi Porkka and Hannu Toivonen (1999), “Tane:

An Efficient Algorithm for Discovering Functional and Approximate Dependen-

cies“ The Computer Journal, Vol 42, No 2.

[16] Yka Huhtala, Juha Karkkainen, Pasi Porkka and Hannu Toivonen (1998), “Ef-

ficient Discovery of Functional and Approximate Dependencies using Partitions“

In Proc, 14th Int. Conf. on Data Engineering, IFFE Computer Society Press.

[17] Jyrki Kivinen, Heikki Mannila (1995), “Approximate Inference of Functional

Dependencies from Relation“, Theoretical Computer Science 149(1), 129-149.

[18] Jan Komorowski, Zdzislaw Pawlak, Lech Polkowski, Andrzej Skowron (1999),

Rough Sets: A Tutorial.

[19] Boris Kovalerchuk, Evgenii Vityaev (2001), Data Mining in Finance: Advances

in Relational and Hybrid Methods, Kluwer Academic Publishers, The 2nd Print-

ing.

Synthesis in Hanbook of Aplicatión and Advances of the Rough Sets Theory:

Intelligent Decision Support Edited by Roman Slowinski, 181-199.

[21] David Maier (1983), The Theory of Relational Databases (Computer Science

Press, Rockville, Maryland.

[22] Mannila, H., Toivonen, H. and Verkamo, A.I. (1997) , “Discovery of frequency

episodes in event sequences“ Data Mining and Knowledge Discovery, I, 259 - 289.

[23] Tetsuya Murai, Yoshiharu Sato (2000), Association Rules from the Point of

View of madal Logic and Rough Set, The 4th Asian Fuzzy Systems Symposium.

[24] Pawlak Z. (1991), Rough Sets- Theoretical Aspects of Reasoning about Data,

Kluwer Academic Publishers, Dordrecht.

[20] Tadeusz Luba, Janusz Rybnik (1992), Rought Sets and Some Aspects of Logic

[25] Iztok Savnik and Peter A. Flash (2000), “Discovery of multivalued dependencies

from ralations“ Intelligent data Analysis, 4(3,4) 195 - 211.

[26] Andrzej Skowron, Rauszer C. (1992), “ The Discernibility Matrices and Func-

tions in Information Systems" Intelligent Decision Support. Handbook of Appli-

cations and Advances of the Rough Sets Theory, Kluwer, Dordrecht, 331–362.

[27] AndrzejSkowron, Ning Zong (2000), Rought Sets in KDD, Tutorial Notes, Copy-

right 2000.

100

[28] Nguyen Hung Son, Marcin Szczuka (2005), Rough Set in KDD, Tutorial Notes

of The Ninth Pacific-Asia Conference on Knowledge Discovery and Data Mining,

Ha Noi.

[29] Ho Thuan (1986), “Contribution to the theory of relational databases“, Tanul-

manyok 184/1986, Studies 184/1986. Budapest, Hungary.

[30] Jeffrey D. Ullman (1988), Principles of Database and Knowledge-Base Systems,

[31] Jakub Wro’blewski (2000), “Analyzing relational databases using rough set

based methods“ Proc. of IPMU 2000, Madrid, Spain. Universidad Politecnica

de Madrid 2000, Vol 1, pp. 256 - 262.

[32] Hong Yao, Howard J. Hamilton and Cory J. Butz (2002), “FD_Mine: Discov-

ering Functional Dependencies in a Database Using Equivalences“ University

of Regina Computer Sciences Department Technical Report CS-02-04, ISBN 0-

7731-0441-0.

Volume I, Computer Science Press, Rockville, Maryland.

101

Các công trình đã công bố liên quan đến luận án

1. Hoàng Thị Lan Giao (2005), “Một số thuật toán tìm tập rút gọn của bảng

quyết định sử dụng các phép toán của đại số quan hệ“, Tạp chí Khoa học,

Khoa học Tự nhiên và Công nghệ, Đại học Quốc gia Hà Nội, T.XXI (2PT),

41-48.

2. Hồ Thuần, Hoàng Thị Lan Giao (2005), “Một thuật toán tìm tập rút gọn sử

dụng ma trận phân biệt được“, Chuyên san Các công trình nghiên cứu triển

3. Hồ Thuần, Hoàng Thị Lan Giao (2006), “Khám phá phụ thuộc đa trị dựa vào

ma trận phụ thuộc“, Tin học và điều khiển(1), tr

4. Hồ Thuần, Hoàng Thị Lan Giao (2006), “Mở rộng phụ thuộc hàm và phụ thuộc

đa trị“, Tin học và điều khiển (đã gửi đăng).

5. Hoàng Thị Lan Giao (2006), “Khai phá luật theo tiếp cận tập thô“, Đề tài

NCKH cấp Bộ trọng điểm B2005-07-02 , nghiệm thu tháng 3/2006.

Các báo cáo khoa học đã tham gia

1. Hội nghị Khoa học Trường Đại học Công nghệ kỷ niệm 5 năm thành lập Khoa

Công nghệ.

khai Viễn thông và CNTT, (15), tr. 83-87.

2. Hội thảo Tin học Toàn quốc, Hải Phòng tháng 8/2005.

3. Hội thảo Khoa học quốc gia "Nghiên cứu phát triển và ứng dụng Công nghệ

Thông tin và Truyền thông" (ICT.Rda), 5/2006.

Luận văn tốt nghiệp: Tiếp cận lý thuyết tập thô do Z.Pawlak

