 Luận văn tốt nghiệp

Tiếp cận lý thuyết tập thô do Z.Pawlak 1
Mục lục
Danh mục các thuật ngữ 2
Bảng các ký hiệu 3
Danh sách bảng 4
Phần mở đầu 6
Chương 1. Các khái niệm cơ bản 10
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

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.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.2. Phụ thuộc mở rộng và các tính chất . . . . . . . . . . . . . . . 81
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 92
Tài liệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
4
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

6
tính điều kiện R.
m(c
j
, R): Khả năng đóng góp của thuộc tính c
j
vào R.
ω
V
B
(c
j
): 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
nhau tại thuộc tính c
j
.
ω
V
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
nhau trên tập thuộc tính D.
ω
V
(c
j
): Số cặp đối tượng của V khác nhau tại thuộc tính c
j
.
ω
V

Danh sách bảng
1.1 Bảng dữ liệu các đồ chơi. . . . . . . . . . . . . . . . . . . . . . . . . . 13
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
1.4 Bảng rút gọn thứ nhất của hệ thống bệnh cúm (R
1
). . . . . . . . . . 19
1.5 Bảng rút gọn thứ hai của hệ thống bệnh cúm (R
2
). . . . . . . . . . . 19
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
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
8
3.4 Quan hệ tương tự trên I
b
. . . . . . . . . . . . . . . . . . . . . . . . . 80
3.5 Quan hệ tương tự trên I
c
. . . . . . . . . . . . . . . . . . . . . . . . . 80
3.6 Dữ liệu của hệ thống. . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
3.7 Các quan hệ tương tự trên I

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
10
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
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.
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
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ô

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á
12
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
không phân biệt được), George Boole (các phương pháp suy luận), Jan Lukasiewicz
(các logic đa trị) và Thomas Bayes (suy luận quy nạp). Về phương diện thực hành,
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
14
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

) bở i u(B). Như vậy, nếu u và v là hai đối tượng, thì ta sẽ
15
viết u(B) = v(B) nếu u(b
i
) = v(b
i
), với mọi i = 1, · · · , k.
1.2.2. Quan hệ không phân biệt được
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
đâ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
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 đó
U/{Màu sắc} = {{u

, u
4
, u
10
}, {u
2
, u
6
, u
7
}}
U/{Hình dáng} = {{u
1
, u
2
, u
6
, u
10
}, {u
3
, u
4
, u
9
}, {u
5
, u
7
, u

, u
4
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
16
U Màu sắc Kích thước Hình dáng
u
1
Xanh To Tròn
u
2
Xanh Nhỏ Tròn
u
3
Vàng Vừa Vuông
u
4
Đỏ Vừa Vuông
u
5
Vàng To Tam giác
u
6
Xanh Nhỏ Tròn
u
7
Đỏ Nhỏ Tam giác
u
8
Đỏ To Tam giác

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:
B
V = ∪{W ∈ U/B | W ⊆ V },
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
POS
B
(D) =

V ∈U/D
(BV ).
Rõ ràng POS
B
(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, POS
B
(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
u
1
Có Bình thường Không

{u
4
}, {u
5
, u
7
}, {u
6
, u
8
}. Đặt V = {u | u(Cảm cúm) = Có } = {u
2
, u
3
, u
6
, u
7
}. Lúc
đó,
BV = {u
2
, u
3
} và BV = {u
2
, u
3
, u
6

= {u
2
, u
3
, u
6
, u
7
}},
B
V
1
= {u
1
, u
4
} ; BV
2
= {u
2
, u
3
},
POS
B
(D) =

V ∈U/D
(BV ) = {u
1

α
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
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,
20
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 POS
C
(D) = U. Trong
trường hợp bảng không nhất quán thì POS
C

(D) = POS
C
(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 POS
R
(D) = POS
C
(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
21
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.
Mệnh đề 1.2. [11, 26, 28] Core(C) =

R∈ Red(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à R
1
={Đau cơ, Thân nhiệt} và R
2
= {Đ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ó
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à
POS
{Đau cơ, Thân nhiệt}
({Cảm cúm}) = POS
C
({Cảm cúm}),

, · · · , u
n
}. Ma trận phân
biệt được của T, ký hiệu M(T) = (m
ij
)
n×n
, là một ma trận đố i xứng mà mỗi phần
22
U Đau cơ Thân nhiệt Cảm cúm
u
1
, u
4
Có Bình thường Không
u
2
Có Cao Có
u
3
, u
6
Có Rất cao Có
u
5
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 (R
1
).
U Đau đầu Thân nhiệt Cảm cúm

d
u
1
1 0 2 1 1
u
2
1 0 2 0 1
u
3
1 2 0 0 2
u
4
1 2 2 1 0
u
5
2 1 0 0 2
u
6
2 1 1 0 2
u
7
2 1 2 1 1
Bảng 1.6: Dữ liệu bảng quyết định.
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]
m
ij
=




i
(D) = u
j
(D) có thể phân biệt với nhau bởi một thuộc tính bất kỳ trong tập
m
ij
. Nếu m
ij
= ∅ thì u
i
và u
j
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 u
i
và u
j
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 = {c
1
, c
2
, c
3
, c
4
} 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

∅
u
2
∅ ∅
u
3
{c
2
, c
3
, c
4
} {c
2
, c
3
} ∅
u
4
{c
2
} {c
2
, c
4
} {c
3
, c
4
} ∅

2
, c
3
, c
4
} {c
1
, c
2
, c
3
} ∅ {c
1
, c
2
, c
3
, c
4
} ∅ ∅
u
7
∅ ∅ {c
1
, c
2
, c
3
, c
4

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 c
2
hoặc c
3
nhưng không phân biệt được bởi các thuộc tính c
1
, c
4
. Thật vậy,
u
2
(d) = 1 = 2 = u
3
(d) và u
2
(c
2
) = 0 = 2 = u
3
(c
2
), u
2
(c
3
) = 2 = 0 = u
3
(c
3

m
ij
, với mỗi u
i
∈ U,
trong đó, mỗi thuộc tính cho tương ứng một biến logic cùng tên và
(1)

m
ij
là biểu thức tuyển của tất cả các biến c ∈ m
ij
, nếu m
ij
= ∅.
(2)

m
ij
= tr ue nếu m
ij
= ∅ và u
i
(D) = u
j
(D).
(3)

m
ij