TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CHƯƠNG TRÌNH ĐÀO TẠC THẠC SĨ CNTT QUA MẠNG
TẬP THÔ TRONG KHAI PHÁ DỮ LIỆU
TÌM TẬP RÚT GỌN SỬ DỤNG MA TRẬN PHÂN BIỆT ĐƯỢC
Bộ môn: Khai phá dữ liệu và kho dữ liệu
Giáo viên hướng dẫn: PGS.TS. Đỗ Phúc
Sinh viên: Trần Hoài Phong
MSSV: CH1101027
Niên khóa 2011 - 2013
Mục lục
Lời mở đầu
Việc khám phá tri thức trong cơ sở dữ liệu đã được phát triển như là một trong
những lĩnh vực quan trọng và năng động nhất vì những thách thức gặp phải trong lý
thuyết cũng như các ứng dụng thực tế có liên quan đến vấn đề khám phá hoặc rút trích
ra những thông tin thú vị và kiến thức chưa biết từ một tập cơ sở dữ liệu rất lớn của thế
giới thực. Lý thuyết Tập thô là một hình thức toán học để biểu diễn các thông tin
không chắc chắn. Nó được xem như là một công cụ để giảm số chiều đầu vào và xử lý
các dữ liệu mơ hồ không chắc chắn. Trong những năm trở lại đây, đã có những sự phát
triển nhanh chóng trong lý thuyết tập thô và các ứng dụng của nó trong nhiều lĩnh vực
nghiên cứu khách nhau bao gồm các vấn đề liên quan đến máy học theo quy nạp và rút
trích tri thức trong các hệ thống tri thức. Mục tiêu chính của bài báo cáo này sẽ đưa ra
một số khái niệm cơ bản về tập thô. Trong đó tập trung phần lớn vào bài toán tìm ma
trận tập rút gọn sử dụng ma trận phân biệt được để quá đó cho chúng ta thấy rõ tại sao
việc phân tích tập thô lại có thể được sử dụng hiệu quả để rút trích ra kiến thức từ một
tập lớn cơ sở dữ liệu.
Trong bài báo cáo em sẽ đưa ra một thuật toán cũng như một ứng dụng áp dụng
thuật toán được nêu ra để giúp hiểu rõ hơn về quá trình rút trích tri thức từ tập dữ liệu
thực tế. Việc cài đặt thuật toán hoàn toàn là do cá nhân lập trình, do tính phức tạp của
Niên khóa 2011 - 2013
2
thuật toán cũng như một số hạn chế về thời gian cài đặt cũng như kiến thức nên phần
được của đối tượng trong khi thuộc tính quyết định là một thuộc tính dùng để phân lớp.
Một ví dụ của bảng thông tin:
Các cột của bảng được đánh nhãn bởi các thuộc tính Outlook, Temperature,
Humidity, Windy và Play. Các dòng được đánh nhãn bởi các đối tượng p1, p2, p3,
…,p5.
Mỗi dòng trong bảng có thể được xem là thông tin về một đối tượng cụ thể. Ví
dụ đối tượng p3 có thể được đặc trưng trong bảng bởi các tập giá trị thuộc tính sau đây
{(Outlook,overcast),(Temperature,83),(Humidity,86), (Windy, False),(Play, Yes)}
Outlook Temperature Humidity Windy Play
P1 sunny 85 85 FALSE no
P2 sunny 80 90 TRUE no
P3 overcast 83 86 FALSE yes
P4 rainy 70 96 FALSE yes
P5 rainy 68 80 FALSE yes
P6 overcast 64 65 TRUE yes
P7 overcast 81 75 FALSE yes
1.2. Quan hệ bất khả phân biệt
Đây là điểm khởi đầu của lý thuyết tập thô, nó thể hiện thực tế do thiếu một số
tri thức làm cho chúng ta không thể phân biệt được vài đối tượng với những thông tin
sẵn có. Đây là một dạng của sự dư thừa trong dữ liệu. Cho hệ thông tin IS = (U, A) đối
với mỗi tập thuộc tính B
⊆
A một quan hệ bất khả phân biệt được ký hiệu là IND
B
được định nghĩa như sau:
IND
B
(U) = {(x,y)
∈
được xác định thông qua xấp xỉ trên và xấp xỉ dưới của nó. Gọi X
⊆
U là một xấp xỉ
bằng cách chỉ sử dụng các thông tin chứa trong B bằng cách khởi tạo ra các xấp xỉ B-
trên và xấp xỉ B-dưới của X:
B
X = {x
∈
U: [x]
B
⊆
X}
B
X = {x
∈
U: [x]
B
∩
X
≠ ∅
}
BN
B
=
B
X -
B
X
Trong đó BN
B
cấu trúc của lớp.
Cho C,D
⊆
A là một tập các thuộc tính điều kiện và quyết định. Chúng ta sẽ gọi
C’
⊆
C là D-Rút gọn của C (rút gọn tương ứng của D), nếu C’ là một tập con nhỏ nhất
của C thỏa
γ
(C,D) =
γ
(C’,D)
Giao của tất cả D-Rút gọn được gọi là D-Lõi (Lõi tương ứng của D). Vì lõi là
giao của tất cả rút gọn nên nó là một tập các thuộc tính của các rút gọn hợp lệ và do đó
nó bao gồm tất cả các thuộc tính không thể gở ra khỏi hệ thông tin mà không gây ra sự
sụp đổ trong cấu trúc của lớp tương đương.
1.5. Ma trận bất khả phân biệt
Cho hệ thông tin T = (U, C, D) với U={u1, u2, …., un}, ma trận phân biệt của
nó M là một ma trận n x n, trong đó mỗi phần tử m cho một cặp (x,y) được định nghĩa
như sau.
m
ij
=
λ
, u
i
(D) = u
j
(D)
={c
2. Các thuật toán tìm rút gọn
Từ các khái niệm và thuật ngữ đã được tìm hiểu ở trên chúng ta đi vào một số
thuật toán để thấy được bản chất của vấn đề rút gọn các tập thuộc tính và đây là cơ sở
để hiểu được phần nào các thuật toán tìm tập rút gọn trong một hệ thông tin
1.6. Tìm rút gọn dựa trên hàm phân biệt
Niên khóa 2011 - 2013
7
Cho hệ thông tin T = (U, C, D) với U={u1, u2, …., un} có ma trận phân biệt M
= “m
ij
”, hàm phân biệt f
t
của T được xây dựng như sau
f
t
=
, , ,
{ | }
ij
i j i j m ij ij ij
m m c
< ≠∅
∧ ∨ ∈
Ví dụ từ ma trận M
Ta có hàm phân biệt sau:
f
t
=
( ) ( )a c b c a b∨ ∧ ∧ ∧ ∨
Sử dụng các tính chất trong đại số Boolean ta có thể đưa về các dạng chuẩn tắc,
1
, X
2
, …., X
m
}. Đặt x = |X| và x
i
= |X
i
|, i = 1,…, m. Số W
x
(a) các cặp đối tượng trong X phân biệt nhau tại thuộc tính a
được tính từ công thức:
2 2
1
W ( )
2 2
m
i j
i
i j
x
i
x x
x x
a
≠
=
−
∈
L
Tìm [IND
i
x
(c
j
)]
Tìm W
i
x
(c
j
)
End
Tính W
U
R
(c
j
) = W
1
x
(c
j
) + … + W
m
x
(c
j
)]
7. Nếu W
U
R
(c
j
) = 0 hoặc R = C
Dừng
Ngược lại thực hiện lại bước 2.
Ví dụ
Cho hệ thông tin sau:
Đặt c
1
= Đau đầu, c
2
= Đau cơ, c
3
= Thân nhiệt
1. R =
∅
; L = {U}
2. Repeat
3.
[IND
1
x
(c
1
)] = {{u1, u2, u3}, {u4, u5, u6}}
W
R
(c
2
) = W
1
x
(c
2
) = 6 + 0 = 6
[IND
1
x
(c
3
)] = {{u1, u4}, {u2, u5}{u3, u6}}
W
L
R
(c
3
) = W
1
x
(c
2
) = 1 + 0 + 0 = 1
4. Chọn c
3
do W
L
3.
[IND
1
x
(c
1
)] = {{u1}, {u4}} W
1
x
(c
1
) = 0
[IND
2
x
(c
1
)] = {{u2}, {u5}} W
2
x
(c
1
) = 0
[IND
3
x
(c
1
)] = {{u3}, {u6}} W
3
2
) = 0
[IND
3
x
(c
2
)] = {{u3, u6}} W
3
x
(c
2
) = 0
W
L
R
(c
2
) = 0 + 0 + 0 = 0
4. Chọn c
1
hoặc c
2
do W
L
R
(c
1
) = W
L
2
}
3. Cài đặt thuật toán Johnson
Ứng dụng minh họa được lập trình trên nền .net. Ngôn ngữ lập trình c# được
viết trên bộ công cụ visual studio 2008.
Niên khóa 2011 - 2013
11
1.8. Các hàm để nhập, xuất dữ liệu phục vụ cho bài toán
- Hàm này để thay đổi số thuộc tính đầu vào, từ thuộc tính đầu vào sẽ tạo ra giao
diện nhập hệ thông tin
!
"#
""
$!%"&'"!%
(
)"*+,
(
(
- Hàm này thêm vào một gridview để người dùng nhập các thông tin của hệ thông
tin làm đầu vào cho bài toán.
$!%"&'"!%
!
$8'""!91!9
:;
-1"<= ./ <<
!91!9167
1>
-<= ./ <<
??$@@AB2CD
-:;67.:;67
110
:;10
<<
(
-:;673:;67
110
:;10
<<
(
??@E0FGHI
!91!9167
1>
>0"
-1"J1"
R
(c
j
) phục vụ cho việc kiểm tra
xem có bằng 0 hay không cũng như để loại các trường hợp có W
U
R
(c
j
) không phải là
nhỏ nhất.
Tập R sẽ có nhiều trường hợp vì đôi khi thuật toán chạy sẽ cho ra hai giá trị W
U
R
(c
j
) bằng nhau và đều nhỏ nhất, do đó sẽ có trường hợp R = “{c1, c2}” hoặc R = “{c1,
c3}”. Do đó ta phải lặp trong R trước tiên lấy ra mọi trường hợp để tiến hành tính toán
W
U
R
(c
j
) trên các trường hợp khác nhau.
Với mỗi trường hợp trong R ta có các L tương ứng, từ R với L tương ứng đó ta
đưa vào hàm “GetMinY”. Hàm “GetMinY” mô tả lại các bước thực hiện trong 2 và 3.
Sau khi đã chạy hàm GetMinY ta sẽ được các giá trị sau đây: giá trị W
U
R
(c
12!9
!9$02!9
!992!9
-/ 3'"!%12"<= 44
$0
(
!9:902!9
:90$0
9:90
!9:;2!9
2"
0;O)"
!90;P
!9O
!9:P
!910!91
!990!99
!9:;0!9:;
1
:;
9
-/ 310" 44
!9:1!91067
!9:9!99067
MO;:1:9"0;"0;P
"O":P":;0
-/ 3O" 44
(
-0;/
K
(
&K-
-!911
Niên khóa 2011 - 2013
16
-1""
&K"
K
(
(
-&K
K
(
$8'""1:;
:8'"1:;
(
(
- Hàm “GetMinY” thực hiện các bước 2, 3 trong thuật toán
Mô tả hàm
Ban đầu hàm nhận giá trị R, L vào. Lặp tất cả thuộc tính c
j
, nếu thuộc tính đó
đã có trong R thì ta sẽ không xét nữa. Tiếp theo lặp các X thuộc L.
02!9
-/ 3" 44
-1
"
(
!9P2!9
!/
-!9$9
!9"Q2!9
!9P$2!9
-/ 3$" 44
-J"Q$67
??0;
!9;2!9
;$67
"Q$67
-K4= K3$" K44
-
'"!%126$67767)">L"'"
!%126$6K7767)">
;$6K7
"Q$6K7
(
(
22?E
!!42
(
(
PP$
(
-0;O)"SS!30;
0;!
Niên khóa 2011 - 2013
19
0;P
0
0;P:;"
0
(
-!0;
0;P:;"
0
(
:;!
:PP
(
(
1.10. Chạy và thực thi kết quả:
Người dùng nhập số lượng thuộc tính C của hệ thông tin. Sau đó nhập các giá trị
c tương ứng trong từng ô. Sau khi nhập xong nhấn nút tìm rút gọn. Chương trình sẽ
đưa ra tập rút gọn tìm được.
x
(c
j
) giống nhau. Tương ứng với mỗi trường hợp ta lại có các R khách nhau.
Chính vì điều này là gia tăng mức độ khó khăn trong việc cài đặt thuật toán.
- Từ các trường hợp khác nhau trong R đã nêu trên sau khi đã cài đặt và xử lý
được, ta lại gặp trường hợp một số R lại cho ra kết quả đi hết các thuộc tính
nhưng W
i
x
(c
j
) lại không bằng không và không giống nhau. Đòi hỏi chúng ta
phải qua một bước xử lý kết quả đối với các trường hợp như vậy để có thể nhận
được kết quả chính xác nhất.
- Một số khuyết điểm nhỏ như thực hiện việc lặp hết các thuộc tính sẽ tạo ra các
kết quả ví dụ R = {{c1, c2}, {c2, c1}} nghĩa là hai cặp trên thực tế là giống
nhau nhưng lại có trong kết quả cũng đã được xử lý.
- Cũng vì thời gian thực tế có hạn nên chưa thể test được nhiều trường hợp, có thể
trong quá trình lập trình các trường hợp phức tạp kể trên sẽ gây một số sai sót có
thể gây ra lỗi chương trình đồng thời phần lập trình chưa được tối ưu và gọn nhẹ
nhất có thể mong thầy có thể thông cảm.
Niên khóa 2011 - 2013
24
4. Kết luận
Tập thô chủ yếu dùng để phân loại các thông tin không chính xác, không chắc
chắn, không đầy đủ hoặc các kiến thức được thể hiện trong các dữ liệu thu được từ
kinh nghiệm. Nó chủ yếu phân biệt sự khác nhau giữa các đối tượng từ đó xếp chúng
vào các lớp cụ thể từ đó có thể phát sinh ra các thuật toán như tìm tập rút gọn, đưa ra
các luật và phân loại đối tượng…
Copyright: Tài liệu đại học ©