Luận văn Phụ thuộc hàm xấp xỉ và ứng dụng trong khai phá dữ liệu
1
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
NGUYỄN MINH HUY
PHỤ THUỘC HÀM XẤP XỈ VÀ ỨNG DỤNG
TRONG KHAI PHÁ DỮ LIỆU
LUẬN VĂN THẠC SĨ
Hà Nội – 2011
2
MỤC LỤC
Lời cam đoan
Mục lục
Danh mục các từ viết tắt
Danh mục các bảng biểu
Danh mục phụ lục
MỞ ĐẦU................................................................................................ 5
Chương 1 - Phụ thuộc hàm và phụ thuộc hàm xấp xỉ ................................6
1.1 Khai phá dữ liệu.............................................................................6
1.1.1 Phát hiện tri thức và khai phá dữ liệu ......................................6
1.1.2 Các phương pháp khai phá dữ liệu ..........................................7
1.2 Phụ thuộc hàm ...............................................................................7
1.2.1 Định nghĩa...............................................................................7
1.2.2 Hệ tiên đề Armstrong..............................................................8
1.2.3 Định nghĩa hai tập phụ thuộc hàm tương đương....................10
1.2.4 Định nghĩa phủ tối thiểu........................................................11
1.2.5 Khoá của quan hệ..................................................................13
1.3 Phụ thuộc hàm xấp xỉ...................................................................14
1.3.1 Phụ thuộc hàm xấp xỉ loại 1 ..................................................14
1.3.2 Phụ thuộc hàm xấp xỉ loại 2 ..................................................16
1.3.3 Bao đóng xấp xỉ ....................................................................20
1.3.4 Khoá xấp xỉ...........................................................................21
Chương 2 - Xây dựng cây quyết định........................................................24
3
2.1 Đặt vấn đề....................................................................................24
2.2 Bảng quyết định ...........................................................................24
2.2.1 Hệ thống thông tin.................................................................24
2.2.2 Bảng quyết định ....................................................................27
2.3 Cây quyết định .............................................................................30
2.4 Ảnh hưởng của phụ thuộc hàm, phụ thuộc hàm xấp xỉ khi xây dựng
cây quyết định ..............................................................................36
Chương 3 - Thử nghiệm và đánh giá.........................................................37
3.1 Thuật toán TANE.......................................................................37
3.1.1 Mô tả thuật toán ...............................................................37
3.1.2 Độ phức tạp......................................................................38
3.2 Thuật toán AFDMCEC .............................................................38
3.2.1 Phân tích thử nghiệm........................................................39
3.2.2 Những so sánh về độ phức tạp thời gian...........................40
KẾT LUẬN .......................................................................................... 41
TÀI LIỆU THAM KHẢO .................................................................... 42
PHỤ LỤC............................................................................................. 43
a) Giao diện chương trình
b) Thủ tục tính phụ thuộc hàm xấp xỉ
c) Thủ tục phân hoạch
4
‘
DANH MỤC CÁC CHỮ VIẾT TẮT
CSDL
FDs
: Cơ sở dữ liệu
: Các phụ thuộc hàm
: Các phụ thuộc hàm xấp xỉ
AFDs
AFDMCEC
: Khai phá phụ thuộc hàm xấp xỉ sử dụng phủ tối thiểu
và lớp tương đương
5
DANH MỤC CÁC BẢNG BIỂU
Bảng 1.1 Quy trình phát hiện tri thức
Bảng 1.2 Bảng cơ sở dữ liệu quan hệ
Bảng 1.3 Cây khai phá các AFDs(ví dụ với 5 thuộc tính)
Bảng 1.4 Bảng cơ sở dữ liệu quan hệ số
Bảng 1.5 Bảng cơ sở dữ liệu kiểm toán(ví dụ trong 5 tháng)
Bảng 2.1 Bảng dữ liệu các đồ chơi
Bảng 2.2 Bảng các triệu chứng của bệnh nhân
Bảng 2.3 Bảng quyết định về cúm
Bảng 2.4 Bảng rút gọn thứ nhất của bảng quyết định về cúm
Bảng 2.5 Bảng rút gọn thứ hai của bảng quyết định về cúm
Bảng 2.6 Bảng chọn ứng cử viên vào ngạch giảng dạy
Bảng 2.7 Bảng dữ liệu điều tra khách hàng mua ôtô
Bảng 2.8 Cây quyết định tại bước 1 trên thuộc tính phụ cấp
Bảng 2.9 Cây quyết định tại bước 2
6
MỞ ĐẦU
Cơ sở dữ liệu (CSDL) là một trong lĩnh vực được tập trung nghiên cứu và phát
triển công nghệ thông tin, nhằm giải quyết các bài toán quản lý, tìm kiếm thông tin
trong những hệ thống lớn, đa dạng, phức tạp cho nhiều người sử dụng trên máy tính
điện tử. Mô hình dữ liệu quan hệ đặt trọng điểm hàng đầu không phải là khác thác
các tiềm năng của máy mà sự mô tả trực quan dữ liệu theo quan điểm của người
dùng, cung cấp một mô hình dữ liệu đơn giản, trong sáng, chặt chẽ, dễ hiểu và tạo
khả năng tự động hoá thiết kế CSDL quan hệ. Có thể nói lý thuyết thiết kế và cài
đặt CSDL, nhất là mô hình dữ liệu quan hệ đã phát triển ở mức độ cao và đạt được
những kết quả sâu sắc.
Ngày nay việc khai phá dữ liệu còn được coi như việc khai phá tri thức từ dữ
liệu (knowlegde mining from databases), trích lọc tri thức(knowlegde extraction),
phân tích dữ liệu mẫu (data-partent analysis), khảo cứu dữ liệu(data archaeology),
đào xới và nạo vét dữ liệu(data dredging).
Với các ngành khoa học, kinh tế - xã hội nơi có những kho dữ liệu khổng lồ
thì việc tìm kiếm, truy xuất và đưa ra thông tin cần thiết phù hợp với thời gian và
yêu cầu là không dễ dàng và chính vì thế một hế hệ mới các phương pháp tiếp cận,
phương pháp nghiên cứu, và các kỹ thuật, công cụ cho phép phân tích, tổng hợp,
khai phá tri thức từ dữ liệu một cách thông minh và hiệu quả đã được các nhà khoa
học quan tâm và nghiên cứu.
Trong những năm gần đây, việc tìm kiếm các thuật toán cho phép khai phá
phụ thuộc hàm xấp xỉ đang được quan tâm nghiên cứu, một trong hững thuật toán
đó là TANE - một thuật toán tương đối hiệu quả trong khai phá phụ thuộc hàm xấp
xỉ.
7
CHƯƠNG 1:
PHỤ THUỘC HÀM VÀ PHỤ THUỘC HÀM XẤP XỈ
1.1Khai phá dữ liệu
1.1.1 Phát hiện tri thức và khai phá dữ liệu
Phát hiện tri thức trong các cơ sở dữ liệu là một qui trình nhận biết các mẫu
hoặc các mô hình trong dữ liệu với các tính năng: hợp thức, mới, khả ích, và có thể
hiểu được. Còn khai thác dữ liệu là một bước trong qui trình phát hiện tri thức gồm
có các thuật toán khai thác dữ liệu chuyên dùng dưới một số qui định về hiệu quả
tính toán chấp nhận được để tìm ra các mẫu hoặc các mô hình trong dữ liệu. Nói
một cách khác, mục đích của phát hiện tri thức và khai phá dữ liệu chính là tìm ra
các mẫu và/hoặc các mô hình đang tồn tại trong các cơ sở dữ liệu nhưng vẫn còn bị
che khuất bởi hàng núi dữ liệu.
Qui trình phát hiện tri thức
Qui trình phát hiện tri thức được mô tả tóm tắt :
Bảng 1.1 Quy trình phát hiện tri thức
- Bước thứ nhất là tìm hiểu lĩnh vực ứng dụng và hình thành bài toán, bước
này sẽ quyết định cho việc rút ra được các tri thức hữu ích và cho phép chọn các
phương pháp khai phá dữ liệu thích hợp với mục đích ứng dụng và bản chất của dữ
liệu.
8
- Bước thứ hai là thu thập và xử lý thô, còn được gọi là tiền xử lý dữ liệu nhằm
loại bỏ nhiễu, xử lý việc thiếu dữ liệu, biến đổi dữ liệu và rút gọn dữ liệu nếu cần
thiết, bước này thường chiếm nhiều thời gian nhất trong toàn bộ qui trình phát hiện
tri thức.
- Bước thứ ba là khai phá dữ liệu, hay nói cách khác là trích ra các mẫu
hoặc/và các mô hình ẩn dưới các dữ liệu.
- Bước thứ tư là hiểu tri thức đã tìm được, đặc biệt là làm sáng tỏ các mô tả và
dự đoán. Các bước trên có thể lặp đi lặp lại một số lần, kết quả thu được có thể
được lấy trung bình trên tất cả các lần thực hiện.
1.1.2 Các phương pháp khai phá dữ liệu
Với hai đích chính của khai phá dữ liệu là Dự đoán và Mô tả , người ta thường
sử dụng các phương pháp sau cho khai phá dữ liệu:
- Phương pháp quy nạp
- Phát hiện các luật kết hợp
- Sử dụng cây quyết định
- Các phương pháp phân lớp và hồi quy phi tuyến:
- Phân nhóm và phân đoạn
- Các phương pháp dự trên mẫu
- Mô hình phụ thuộc dựa trên đồ thị xác suất
- Mô hình học quan hệ
- Mạng neuron
- Thuật giải di truyền
1.2 Phụ thuộc hàm
1.2.1 Định nghĩa
Trong mỗi CSDL luôn tồn tại nhiều mối liên hệ giữa các thuộc tính, giữa các
bộ; sự liên hệ này có thể xảy ra trong cùng một quan hệ hoặc trong các quan hệ của
một lược đồ CSDL. Các mối liên hệ này là những điều kiện bất biến mà tất cả các
bộ của những quan hệ có liên quan trong CSDL đều phải thoả mãn ở mọi thời
điểm. Những điều kiện bất biến đó được gọi là rằng buộc toàn vẹn.
Phụ thuộc hàm là 1 công cụ dùng để biểu diễn 1 cách hình thức 1 số rằng
buộc toàn vẹn.
9
Các phụ thuộc hàm là các tương quan giữa các thuộc tính của một quan hệ:
Một phụ thuộc hàm chỉ ra rằng giá trị của một thuộc tính được xác định duy nhất
bởi một số các thuộc tính khác. Vấn đề phát hiện các phụ thuộc hàm từ các quan hệ
đã nhận được các mối quan tâm đáng kể. Việc phân tích CSDL tự động, đương
nhiên, rất thú vị cho các mục tiêu khai phá tri thức và khai phá dữ liệu , và các phụ
thuộc hàm có nhiều ứng dụng trong các lĩnh vực quản lý CSDL, tối ưu hóa truy
vấn…
Một cách hình thức, một phụ thuộc hàm trên một lược đồ quan hệ R là một
biểu diễn XA với X R và A
R.Phụ thuộc này đúng trong một quan hệ r trên
R, ta có nếu t[B] = u[B] mọi B X thì
R cho trước nếu với mọi cặp hàng t,u
t[A] = u[A] (ta cũng nói rằng t và u thoả trên X và A).
Ví dụ :
Mã Sinh viên Họ và tên
Số chứng minh
1247237
Năm sinh Quê quán
1987 Hà Nội
00001
00002
Nguyễn Văn A
Nguyễn Văn B
1211445
1988 Lạng Sơn
Ta có các phụ thuộc hàm sau
AB, AC, AD, AE,CB,CD, CE
Phụ thuộc hàm X A là tối thiểu trong r nếu A không phụ thuộc hàm vào bất
kỳ một tập con thực sự nào của X. Ví dụ nếu Y A không thoả trong r với bất kỳ
Y X.
Phụ thuộc hàm X A là tầm thường nếu A X.
1.2.2 Hệ tiên đề Armstrong
Gọi F là tập tất cả các phụ thuộc hàm đối với lược đồ quan hệ r(U) và
X -> Y là một phụ thuộc hàm với X, Y U, ta nói rằng X -> Y được suy diễn
logic từ F nếu quan hệ trên r(U) đều thỏa mãn các phụ thuộc hàm của F thì cũng
thỏa X -> Y. Sau đây là tập quy tắc của hệ tiên đề được Armstrong đề xuất vào năm
1974, được gọi là hệ tiên đề Armstrong.
Hệ tiên đề Armstrong
10
Gọi R(U) là lược đồ quan hệ với U = (A1, A2,..., An) là tập các thuộc tính: giả
sử X, Y, Z U, hệ tiên đề Armstrong bao gồm:
* Tính phản xạ: Nếu Y X thì X -> Y
* Tính tăng trưởng: Nếu Z U, X->Y thì ZX -> ZY. Trong đó
ZX=Z
U
* Tính bắc cầu: Nếu X -> Y và Y -> Zthì X -> Z.
Ví dụ:
Cho AB -> C, C -> A, chứng minh BC -> ABC
(1) C -> A (theo giả thiết)
(2) BC -> AB (áp dụng luật tăng trưởng tăng (1) lên B)
(3) AB -> C (theo giả thiết)
(4) AB -> ABC (tăng (3)AB)
(5) BC -> ABC (bắc cầu (1), (2)).
Bổ đề 1:
Hệ tiên đề Armstrong là đầy đủ, có nghĩa là nếu F là tập phụ thuộc hàm đúng
trên quan hệ r và f : X -> Y là một phụ thuộc hàm được suy dẫn từ F nhờ hệ tiên đề
Armstrong thì f đúng trên r
Bổ đề 2:
Tính hợp : nếu X -> Y và X -> Z thì X -> YZ .
Tính tựa bắc cầu : Nếu X -> Y và WY -> Z thì XW -> Z.
Tính tách: Nếu X -> Y và Z Y thì X -> Z.
Bao đóng của F được kí hiệu là F+, là tập tất cả các phụ thuộc hàm được suy
diễn logic nhờ tiên đề Armstrong, 3 bổ đề trên từ F, nếu F = F+ thì F là họ đầy đủ
của các phụ thuộc hàm. Bao đóng của tập thuộc tính (X+)
X -> Y là một phụ thuộc hàm suy ra từ F. Khi đó X+ được gọi là bao đóng của
tập thuộc tính X nếu X+ là tập tất cả các thuộc tính U được suy dẫn bắt đầu từ tập
X.
X+ = { A | X -> A F+ }
F
Thuật toán tìm bao đóng của tập thuộc tính:
INPUT: X, F,U
OUTPUT: X+
11
S : = X
WHILE có (Z -> Y) thuộc F với Z S và Y⊄S
DO S:= SY
ENDWHILE
X+ = S
Phương pháp: Tính liên tiếp các tập thuộc tính X0, X1, X2,..., Xi
BC0: Đặt X0 = X
BC1: Nếu tồn tại phụ thuộc hàm f: Y->Z F sao cho Y X0, Z
U thì X1=X0Z
BC2: Tương tư.
Until Xi = Xi+1.
Kết luận X+ = Xi.
Ví dụ:
Cho lược đồ quan hê R(U)=(ABCDEM), với U là tập thuộc tính, tập phụ thuộc
hàm
F={AB -> C, C ->D, A -> E, BC ->EM}
Tính bao đóng của (AB)+
BC0: Đặt X0 = AB
BC1: Tồn tại A -> E F, mà A X0, E U vậy X1=X0E = ABE
BC2: Tồn tại AB ->C F, mà AB X1, C U vậy X2=X1C = ABCE
BC3: Tồn tại C -> D F, mà C X2, D U vậy X3=X2D= ABCDE
BC4: Tồn tại BC -> EM F, mà BC X3, EM U vậy X4=X3M =
ABCDEM
BC5: Xét toàn bộ các phụ thuộc hàm thuộc F, thì X5 =X4
Vậy kết luận (AB)+ = X4 = ABCDEM
1.2.3 Định nghĩa hai tập phụ thuộc hàm tương đương:
Để khám phá ra một tập hợp các FDs, sử dụng phương pháp phân vùng chia
bản ghi của trường hợp này thành các nhóm dựa trên các giá trị khác nhau cho mỗi
cột (thuộc tính). Đối với mỗi thuộc tính, số lượng các nhóm là bằng với số các giá
12
trị khác nhau cho các thuộc tính đó. Mỗi nhóm được gọi là một lớp tương đương.
Ví dụ, hãy xem xét ví dụ liên quan được hiển thị trong bảng 1, trong trường hợp
này, thuộc tính A có giá trị "1" chỉ trong bản ghi số một và hai, do đó, chúng tạo
thành một lớp tương đương [1] (A) = [2] (A) = (1,2). Tương tự như vậy, thuộc tính
A có giá trị của "2" trong bản ghi 3,4,5 và có giá trị "3" trong bản ghi 6,7,8. Do đó
toàn bộ các lớp học tương đương đối với các thuộc tính A là bao gồm ba lớp tương
đương như sau:
∏
{A} = {{1, 2}, {3, 4, 5}, {6, 7, 8}}.
Các lớp tương đương đối với các thuộc tính kết hợp (B, C), ví dụ:
{B, C} r = {{1}, {2}, {3, 4}, {5}, {6}, {7}, {8}}.
∏
Tuple ID
A
1
1
2
2
2
3
3
3
B
A
A
A
A
B
B
C
C
C
$
D
E
2
2
0
0
0
1
1
1
1
2
3
4
5
6
7
8
Flower
Tulip
$
$
Daffodil
Flower
Lily
$
#
Orchid
Flower
Rose
Bảng 1.2 : Bảng cơ sở dữ liệu quan hệ
FD X → Y được suy ra khi và chỉ khi Π (x) lọc Π (Y).
Trong ví dụ : thuộc tính A có các bộ sau đây của lớp tương đương: ((T1, T2),
(T3, T4, T5), (T6, T7, T8)), và thuộc tính E có các tập sau của lớp tương đương:
((T1, T2), (T3, T4, T5), (T6, T7, T8)). Các lớp tương đương trong thuộc tính E
được lọc bởi các lớp tương đương trong thuộc tính A, chúng ta có thể khám phá ra
rằng A → E .
1.2.4 Định nghĩa phủ cực tiểu (tối thiểu)
13
Cho tập thuộc tính U và tập phụ thuộc hàm F. Nguời ta nói F là tối thiểu khi và
chỉ khi:
Vế phải của mỗi phụ thuộc hàm trong F chỉ có một thuộc tính độc nhất.
! X -> A F tập F - {X -> A} tương đương với F (loại bỏ các phụ thuộc dư
thừa).
! X -> A F, Z X | F - {X−A}{Z−A} tương đương với F (loại bỏ thuộc
tính dư thừa vế trái)
Thuật toán: tìm phủ tối thiểu của tập phụ thuộc hàm F, với tập thuộc tính U:
INPUT: F, U
OUTPUT: G (G là phủ tối thiểu của F).
BC1: G = ϕ. Tách tất cả các phụ thuộc hàm f của F thành phụ
thuộc hàm mà vế phải chỉ có một t thuộc tính:
FOR f F, f = X -> DO G=G{X−A,AY}
BC2: Loại bỏ những phụ thuộc hàm không đầy đủ:
WHILE Z X, Z ≠ X, G ≅ G \ {f}{Z−A}
DO G = G \ {f}{Z−A}
BC3: Loại bỏ những phụ thuộc hàm dư thừa:
FOR f G DO
IF G \ {f} ≅ THEN G = G \ {f}
BC4:RETURN (G).
Ta có thể diễn giải lại thuật giải như sau:
BC1: Tách tất cả các phụ thuộc hàm của F thành phụ thuộc hàm mà vế phải
chỉ có một thuộc tính, Ví dụ:
AB –> CD được tách thành AB ->C, AB -> D (luật tách)
BC2: Loại bỏ những phụ thuộc hàm không đầy đủ. Khi loại bỏ, ta phân bịêt
hai loại phụ thuộc hàm không đầy đủ sau:
Loại1: Phụ thuộc hàm mà vế phải là tập con của vế trái
( loại AB -> B)
Loai 2: Hai phụ thuộc hàm có vế phải giống nhau, nếu vế trái của phụ thuộc
hàm này chứa vế trái của phụ thuộc hàm kia thì ta loại ra khỏi F.
14
Ví dụ: Nếu có ABC -> D và BC - >D thì ta loại ABC -> D khỏi F.
BC3: Loại bỏ những phụ thuộc hàm dư thừa:
Giả sử hai phụ thuộc hàm có vế phải giống nhau: f1 = X -> A và f2 = Y -> A,
lúc đó nếu có A X+ \ {f1} thì loại f1 ra khỏi F:
F
1.2.5 Khoá của quan hệ
a) Khoá của tập thực thể
Là một hoặc một tập các thuộc tính xác định duy nhất một thực thể trong một
tập thực thể.
b) Khoá của quan hệ
Tập các thuộc tính X của một quan hệ R là một khoá nếu. Không tồn tại 2 bộ
khác nhau nhưng tất cả các phần tử của X đều giống nhau, và không có tập con
thực sự nào của X có tính chất này.
Định nghĩa: Cho lược đồ quan hệ R(A1, A2,...,An) và tập phụ thuộc hàm F, X
A1, A2,...,An . Ta nói X là một khoá của R khi và chỉ khi X -> A1, A2,...,An F+ (tất
cả các thuộc tính phụ thuộc vào tập thuộc tính X),
YX | X-> A1A2...An F+.
Sau đây là một số định nghĩa về khoá của quan hệ:
Khoá dự tuyển : là khoá của quan hệ. Một quan hệ có thể có nhiều khóa dự
tuyển.
Khoá chính : là khoá dự tuyển được chọn làm khoá chính của quan hệ. Khoá
chính không thể rỗng ( NOT NULL).
Siêu khoá : một khoá gọi là siêu khoá nếu như ta bỏ đi một hay nhiều thuộc
tính bất kỳ, thì không đảm bảo phần còn lại là khóa.
Khoá ngoại : (khoá liên kết ) là một hoặc một tập thuộc tính trong quan hệ R1
nhưng là khoá chính trong quan hệ R2.
Một thuộc tính trong lược đồ quan hệ R(U) được gọi là thuộc tính khoá nếu nó
là một thành phần của một khoá nào đó của R. Ngược lại người ta gọi là thuộc tính
không khoá (thuộc tính thứ cấp).
Ví dụ: Cho lược đồ quan hệ R = (ABCD) và tập phụ thuộc hàm
F = { A → C, AB → DC}, khoá là {AB}. Khi đó thuộc tính A, B gọi là thuộc
tính khoá, còn thuộc tính D, C gọi là thuộc tính không khóa.
15
- Thuật toán tìm tất cả các khoá của một lược đồ quan hệ
Bước 1: Tạo tập thuộc tính nguồn TN, tập thuộc tính trung gian TG
Bước 2: if TG = ∅ then lược đồ quan hệ chỉ có một khoá K
K = TN
Kết thúc
Ngược lại
Qua bước 3
Bước 3: Tìm tất cả các tập con Xi của tập trung gian TG
Bước 4; Tìm các siêu khoá Si băng cách :
Xi
if ( TNXi )+ = Q+ then
Si = TNXi
Bước 5: Tìm kháo bằng cách loại bỏ các siêu khoá không tối tiểu
Si, Sj S
if Si Sj then Loại Sj ra khỏi tệp siêu khóa S
S còn lại chính là tập khoá cần tìm.
1.3 Phụ thuộc hàm xấp xỉ
1.3.1 Phụ thuộc hàm xấp xỉ loại 1
Đối với một số quan hệ, một số FDs có thể không đúng cho tất cả các bản ghi.
Ví dụ đối với hãng ô tô. Được xác định bởi Model thông qua một kỳ vọng phụ
thuộc: như Model = 323, chúng ta biết rằng của hãng Mazda với xác suất cao,
nhưng có cũng là một cơ hội nhỏ của hãng BMW. Tính xấp xỉ FD được quy định
bởi Model →Make.
Một phụ thuộc hàm X → A được suy diễn trong r với độ lỗi g3 (X → A) = 1 -
(max{|s| | s r và X → A được suy diễn })/|r|. Với 1 số ε, 0 ≤ ε ≤ 1, chúng ta nói
X->A là một phụ thuộc hàm xấp xỉ khi và chỉ khi g3(XA) nhỏ hơn ε.
- Biểu diễn hình thức g3 (X → A) = 1 - ∑ c πX max{ |c’| | c’ πx
{A} and c’ c} / |r|
- πX: Phân hoạch X
16
Ví dụ:
Tuple ID
A
1
1
2
2
2
3
1
3
B
A
A
A
A
B
B
C
C
C
$
D
E
2
2
0
0
0
1
1
1
1
2
3
4
5
6
7
8
Flower
Tulip
$
$
Daffodil
Flower
Lily
$
#
Orchid
Flower
Rose
Bảng 1.2 : Bảng cơ sở dữ liệu quan hệ
Trong bảng cơ sở dữ liệu bên trên. Kiểm tra phụ thuộc hàm AB không
được suy diễn. Chúng ta tìm thấy các lớp tương đương:
∏
∏
{A} = {{1, 2,7}, {3, 4, 5}, {6, 8}}.
{B} = {{1}, {2, 3, 4,}, {5, 6}, {7,8}}.
A không lọc được B ở các lớp khác nhau. Suy ra AB không đúng.
Tuy nhiên A B có thể đúng ở trong ví dụ, với độ đo là g3. Nếu chúng ta
loại bỏ 1 vài bản ghi từ các mối quan hệ, bằng phương pháp loại trừ nhau cho việc
tính toán g3.
∏
∏
{A} = {{1, 2}, {3, 4, 5}, {6, 7, 8}}.
{B} = {{1}, {2, 3, 4,}, {5, 6}, {7,8}}.
Chúng ta tìm được ∏ {A} {B} = {{1}, {2}, {3,4}, {5}, {6}, {7.8}}. Lớp tương
đương trong thuộc tính A {1,2} có kích thước 2 phần tử thành {1}, {2} từ ∏ {A} {B}
.
Do đó kích thước phần tử lớn nhất của {1}, {2} là 1.
Với lớp tương đương {3, 4, 5} trong ∏ {A} thành {3, 4} và {5} từ
∏
{A} {B} . Do đó kích thước phần tử lớn nhất của {3, 4} và {5} là 2.
Bổ sung công thức
17
Cuối cùng ở lớp tương đương của { 6, 7, 8} trong ∏A bằng với {6} {7, 8}
trong ∏ {A} {B}. Từ đó hàm g3 ( AB) = 1-(1+2+2)/8=0.375. Như
AB = 0.375
vậy có thể nói phụ thuộc hàm AB với độ lỗi 0.375.
Quá trình xử lý để khai phá ra tất cả các AFDs là quá trình xử lý tất cả các
thuộc tính cho tất cả các tổ hợp. Với 5 thuộc tính {A, B, C, D, E} các tổ hợp được
xác lập {, A, B, C, D, E, AB, AC, AD, AE, BC, BD, DE, CD, CE, DE, ABC,
ABD, ABE, ACD, ACE, ADE, BCD,BCE, BDE, CDE, ABCD, ABCE, ABDE,
ACDE, BCDE, ABCDE} tổng số 25
Bảng 1.3 : Cây khai phá tất cả các AFD.
1.3.2 Phụ thuộc hàm xấp xỉ loại 2
Cho r là một quan hệ trên tập thuộc tính R= {A1, A2...,An} trong đó các thuộc
tính A1, A2,...An có thể là thuộc tính định danh(categorical), rời rạc hoặc liên
tục(trường số). Đối với những thuộc tính định danh, ta tiến hành thực hiện ánh xạ
tất cả các giá trị có thể tới một tập các số nguyên dương liên kề.
Định nghĩa: (khoảng cách giữa 2 bộ giá trị trên tập thuộc tính)
Với 2 bộ t1, t2 r, ta kí hiệu (t1(X), t2(X)) là khoảng cách giữa t1 và t2 trên tập
thuộc tính X R được xác định như sau:
(t1(X), t2(X)) = max(|t1(Ai)- t2(Ai)| / max(|t1(Ai)|,|t2(Ai)|), Ai X):
18
Hàm max(x, y) là hàm chọn ra số lớn nhất trong 2 số x và y;
Trường hợp max(|t1(Ai)|- |t2(Ai)|)= 0, tức t1(Ai) = t2(Ai) = 0 thì ta qui ước:
|t1(Ai)- t2(Ai)|/ max(|t1(Ai)|, |t2(Ai)|) = 0
Khoảng cách giữa 2 bộ giá trị trên tập thuộc tính có thể coi là hàm số cả các
đối số là các bộ giá trị của quan hệ và tập các thuộc tính.
Một số tính chất của hàm khoảng cách p(t1(X), t2(X))
Định nghĩa khoảng cách p(t1(X), t2(X)) nêu trên thoả mãn các tính chất của
hàm khoảng cách:
A1. p(t1(X), t2(X)) >=0 với t1, t2, X tuỳ ý ;
A2. p(t1(X), t2(X)) = 0 t1(X) = t2(X)
p(t1(X),t2(X)) p(t1(X),t3(X)) + p(t3(X),t2(X))
Và ngoài ra cũng dễ chứng minh các tính chất:
Nếu X Y thì p(t1(X), t2(X)) p(t1(Y), t2(Y))
p(t1(XY), t2(XY)) = max(p(t1(X), t2(X)), p(t1(Y), t2(Y)))
Định nghĩa 2 : Phụ thuộc hàm xấp xỉ loại 2
Giả sử X,Y R và với một số cho trước, 0 <1, ta nói rằng X xác định
hàm Y mức (hoặc nói rằng giữa X và Y có phụ thuộc hàm xấp xỉ loại 2 mức ),
ký hiệu là X Y nếu với mọi cặp bộ t1, t2 r, mà p(t1(X), t2(X)) thì ta cũng có
p(t1(Y), t2(Y))
Ví dụ:
A
B
C
D
E
2.5
18
18
20
20
25
160
160.5
320
323
641
25
15
30
45
60
12
13
16
28
19
2.51
3.6
3.65
4.25
Bảng 1.4 : Bảng dữ liệu quan hệ số
Ta thấy giữa bộ A, B có mối tương quan với cột C với = 0.05 ta kiểm tra
điều kiện phụ thuộc hàm xấp xỉ
19
với cặp hàng 1,2
ta có p(t1(AB), t2(AB)) = max (|t1(A) - t2(A)|/max(|t1(A)|, |t2(A)|), |t1(B) -
t2(B)|/max(|t1(B)|, |t2(B)|) = 0.00394 < 0.05
Tương tự kiểm tra với cặp hàng 3,4 và 5,6
Vậy ta có AB > 0.05C(AB xác định C mức 0.05)
Một số tính chất:
- Tính chất 1 : Cho r là một qua hệ trên tập thuộc tính R. Một phụ thuộc hàm
đúng trên r cũng là phụ thuộc hàm xấp xỉ loại 2 với mức tuỳ ý (0 <1) đúng
trên r
Tính chất này dễ dàng suy theo định nghĩa của phụ thuộc hàm xấp xỉ loại 2
- Tính chất 2 : Cho r là một quan hệ trên R; X, Y R, 1, 2, là 2 số sao cho 0
1 2 <1. Kí hiêu X > 1Y và X > 2Y là 2 phụ thuộc hàm xấp xỉ loại 2 mức
1 và mức 2 giữa X và Y trên r, khi đó nếu X > Y đúng trên r thì X > Y
1
2
cũng đúng trên r
- Tính chất 3 : Tính phản xạ
Nếu Y X khi đó X > Y là phụ thuộc hàm xấp xỉ loại 2 với mức tuỳ ý (0
<1)
- Tính chất 4 : Tính bắc cầu
Nếu X > Y và Y > Z thì X > Z
- Tính chất 5 : Tính gia tăng
Với mọi X, Y, Z R và mức nào đó, nếu X > Y thì XZ > YZ.
1.3.2.1 Xây dựng thuật toán kiểm tra phụ thuộc hàm xấp xỉ loại 2
Giả sử cho r = {t1, t2,.....,tn } là một quan hệ trên tập thuộc tính R và X, Y R,
với một số cho trước ( 0 <1). Ta sẽ xây dựng thuật toán để xác định xem quan
hệ r có thoả phụ thuộc hàm xấp xỉ loại 2 mức : X > Y hay không ?
Ta xét hệ xấp xỉ Er được xây dựng như sau :
Er = { E()i,j = { a:| ti(a) - tj(a)| /max(|ti(a)|, |tj(a)|) ; a R}; ti, tj r; 1 i <
j m}
Ta gọi tập Er là một hệ xấp xỉ mức của r
Ta có mệnh đề sau:
Mệnh đề 1 (Điều kiện để quan hệ thoả phụ thuộc hàm xấp xỉ loại 2)
20
Giả sử cho r = {t1, t2,...,tn} là một quan hệ trên tập thuộc tính R và X, Y R
với một số cho trước ( 0 <1); Er là một hệ xấp xỉ mức thoả phụ thuộc hàm
xấp xỉ loại 2 mức :X > Y khi và chỉ khi :
E()i,j Er : ( X E()i,j Y E()i,j )
1.3.2.2 Ứng dụng trong thực tế hoạt động kiểm toán
Hoạt động kiểm toán của kiểm toán nhà nước gắn liền với việc phát hiện ra
những hiện tượng bất thường hoặc ngoại lai trong tập dữ liệu thông tin của doanh
nghiệp hoặc đơn vị được kiểm toán. Trên cơ sở các hiện tượng bất thường nay,
kiểm toán viên sẽ tiến hành các biện pháp nghiệp vụ để xem xét liệu có sự gian lận
hoặc sai sót hay không và tiến hành xử lý.
Ví dụ :
THANG
TONG_CP
CHI_NVL
TIENLUONG
507,823,562
513,291,500
525,419,000
528,928,450
530,718,000
VAT
1
2
3
4
5
1,450,267,320 580,271,928
1,465,890,000 586,521,000
1,500,540,000 600,381,000
1,510,567,000 604,391,800
1,515,680,000 680,437,000
41,019,035
41,456,470
42,426,670
42,707,426
48,030,590
Bảng 1.5: Bảng cơ sở dữ liệu kiểm toán
Trong trường hợp này áp dụng thuật toán xấp xỉ loại 2 chọn = 0.01 (việc
chọn giá trị tuỳ thuộc vào điều kiện thực tế và ý kiến của các chuyên gia kinh tế)
Xây dựng tập bằng nhau Er cho bảng trên ta được:
E()1,2 = TONG_CP, CHI_NVL, TIENLUONG,VAT
E()1,3 = E()1,4 = E()1,5 = E()2,3 = E()2,4 = E()2,5 =
E()3,4 = TONG_CP, CHI_NVL, TIENLUONG,VAT
E()3,5 = TONG_CP,TIENLUONG
E()4,5 = TONG_CP,TIENLUONG
21
Chúng ta thấy rằng trong E()3,5 và E()4,5 có chứa TONG_CP nhưng không
chứa các thuộc tính CHI_NVL, VAT. Như vậy giữa tháng 3 và tháng 5 có sự bất
thường giữa TONG_CP và CHI_NVL.; giữa TONG_CP và VAT
Tương tự giữa tháng 4 và tháng 5:
Khi kiểm tra kỹ chúng ta nhận thấy rằng trong tháng 5 có sự kê khai sai về
chi phí nguyên vật liệu, cũng như thuế VAT (so với tháng 3, tháng 4 cùng tổng chi
phí xấp xỉ như nhau(chênh lệch nhỏ hơn 1%) nhưng mức chênh lệch giữa chi phí
NVL và thuế VAT lớn hơn nhiều(chênh lệch hơn 5%). Có thể đã có sự gian lận
hoặc sai xót xảy ra.
1.3.3 Bao đóng xấp xỉ
Đặt A+ = { a: A {a} F+ } được gọi là bao đóng xấp xỉ của A trên s. Có
thể thấy rằng A B F+ nếu và chỉ nếu B A+ .
1.3.3.1 Thuật toán tìm bao đóng xấp xỉ
Thuật toán 1:
Vào: sz = <R, Fz>, ở đây R={ a1,..., an} tập hữu hạn các thuộc tính, Fz tập các
phụ thuộc hàm xấp xỉ, A R.
Ra: Az+ bao đóng của A đối với Fz
Thuật toán thực hiện như sau:
Tính các tập thuộc tính A0, A1,... theo qui tắc:
A0 = A
Ai = Ai-1 {a} sao cho ( C D) F, {a} Y và C Ai-1
Vì A = A0 ... Ai R, và R hữu hạn nên tồn tại một chỉ số i nào đó mà Ai
= Ai+1, khi đó thuật toán dừng và Az+ = Ai
Chứng minh:
Ta có thể thấy rằng, R la hữu hạn các phần tử, F, là hữu hạn nên tồn tại chỉ số i
sao cho Ai = Ai+1. Do vậy chúng ta có thể thấy độ phức tạp thời gian của thuật toán
này là đa thức theo kích thước của sz.
22
Ví dụ:
Cho bảng quan hệ sau:
A
B
C
D
E
2.5
2.51
3.6
3.65
18
18
20
20
160
19
21
22
20
18
20
20
18
160.5
320
323
Ta xây dựng được một sơ đồ quan hệ <R,F> với tập thuộc tính là R=
<A,B,C,D,E> và tập phụ thuộc xấp xỉ F={AB >0.05 C, AB >0.05 E, E >0.05
D} với mức xấp xỉ của = 0.05.
Áp dụng thuật toán tính bao đóng xấp xỉ trên ta dễ dàng thu được bao đóng
xấp xỉ của AB = {ABCDE}
1.3.4 Khoá xấp xỉ
Giả sử s = < R, F> là một sơ đồ quan hệ xấp xỉ. Khi đó A là một khoá xấp
xỉ của s nếu A R F+ . Chúng ta gọi A là một khoá tối tiểu xấp xỉ của s nếu:
A là một khoá xấp xỉ của s.
Bất kì một tập con thực sự của A không là khoá xấp xỉ của s.
1.3.4.1 Thuật toán tìm khoá xấp xỉ của sơ đồ quan hệ
Thuật toán 2:
Vào: Sơ đồ quan hệ s =<F, R> trong đó:
F là tập phụ thuộc hàm xấp xỉ và
R = { a1,..., an} là tập các thuộc tính
Ra: K là một khoá xấp xỉ của s
Thuật toán thực hiện như sau:
Tính liên tiếp các tập thuộc tính K0, K1....,Kn như sau:
K0 = R = { a1,..., an}
23
Ki = Ki-1, nếu Ki-1 - {ai} R F+, và Ki-1- {ai},
ngược lại...
K = Kn là khoá tối tiểu xấp xỉ của s
Chứng minh:
Ta có thể thấy rằng R là hữu hạn các thuộc tính, F là hữu hạn nên sau n
bước liên tiếp sẽ tồn tại Ki = Ki+1. Khi đó tồn tại một tập Ki sao cho: Ki R F+
và bất kì một tập con nào của Ki đều không xác định R.
Ví dụ:
Cho sơ dồ quan hệ < R, F> với tập thuộc tính là R= {A, B, C, D, E} và tập
phụ thuộc xâp xỉ F={AB >0.05 C, AB >0.05 E, E >0.05 D} với mức xấp xỉ
của = 0.05.
Áp dụng thuật toán trên ta có:
Bước 1: Đặt K0 = R= {A, B, C, D, E}
Bước 2: Tính K1
Xét K0\A = {B, C, D, E}
Tính bao đóng xấp xỉ mức 0.05 của {B, C, D, E}.{B, C, D, E}+0.05 = {B, C,
D, E} <>R, do vậy K1 =K0= {A, B, C, D}
Bước 3: Tương tự ta tính được K2= K0; K3 = {A, B, D, E}; K4= {A, B, E};
K5= {A, B}.
Do vậy, khoá xấp xỉ K của sơ đồ quan hệ s= <R, F> là K= K5= {A, B}
Dạng chuẩn 2 - NF
Một quan hệ ở dạng chuẩn 2NF nếu quan hệ đó
+ Là 1 NF
+ Các thuộc tính không khoá phải phụ thuộc hàm xấp xỉ đầy đủ vào khoá
chính.
Dạng chuẩn 3 - NF
+ Là 2 NF
+ Các thuộc tính không khoá phải phụ thuộc xấp xỉ trực tiếp vào khoá chính.
24
Dạng chuẩn BCNF
+ Là 3NF
+ Không có thuộc tính khoá mà phụ thuộc hàm xấp xỉ vào thuộc tính không
khoá.
Thuật toán kiểm tra BCNF
Bước 1 : Xác định khoá
Bước 2 : Kiểm tra thuộc tính không khoá phải phụ thuộc hàm xấp xỉ đầy đủ
vào khoá chính
Bước 3 : Kiểm tra các thuộc tính không khoá phải phụ thuộc xấp xỉ trực tiếp
vào khoá chính.
Bước 4 : Với mỗi thuộc tính khoá kiểm tra có phụ thuộc hàm xâp xỉ vào
thuộc tính khoá không. Nếu phụ thuộc thì luợc đồ quan hệ không thuộc dạng chuẩn
BCNF
Ví dụ 1: Cho lược đồ quan hệ U = {A, B, C, D} và tập các phụ thuộc hàm
xấp xỉ với mức xấp xỉ (A~>B, B~> A, AC ~>D)
Xác định : AC hoặc BC là khoá
Nếu AC là khoá ta có B~> A(thuộc tính khoá phụ thuộc hàm xấp xỉ và
thuộc tính không khoá).
Nếu BC là khoá ta có A~>B(thuộc tính khoá phụ thuộc hàm xấp xỉ và thuộc
tính không khoá).
Như vậy : Lược đồ U thuộc dạng chuẩn 3NF
25
CHƯƠNG 2 :
XÂY DỰNG CÂY QUYẾT ĐỊNH
2.1 Đặt vấn đề
Một trong những đích khai phá dữ liệu trong thực tế nhằm đạt đến là mô tả
các mẫu dữ liệu, mỗi một sự mô tả là thể hiện những tri thức được khai phá. Sự
phân lớp là quá trình nhằm đến một trong những mục đích ấy. Cây quyết định là
một trong những giải pháp trực quan và hữu hiệu để mô tả quá trình phân lớp dữ
liệu. Do cây quyết định rất hữu dụng nên đã có nhiều nghiên cứu để xây dựng nó
mà nổi bật là các thuật toán học quy nạp như CATD, ID3, C45,....
Xây dựng cây quyết định có khả năng dự đoán cao, là một trong những mục
tiêu quan trọng của khai phá dữ liệu. Để xây dựng được một cây quyết định có
hiệu quả thì ngoài các thuật toán học quy n
ạ
p tốt, việc chọn mẫu huấn luyện
c t nhiên giữa
đóng một vai trò đáng kể. Khi chọn mẫu huấn luyện, sự phụ thu
ộ
ự
các thuộc tính dữ liệu trong mẫu cần phải được đề cập và ứng dụng để loại trừ
nó, nhằm nâng cao hiệu quả cho cây được xây dựng [3, 5, 8, 9]. Hơn nữa, có
nhiều trường hợp trong thực tế, các nhóm thuộc tính mặc dầu giữa chúng không
có sự phụ thuộc theo định nghĩa của phụ thuộc hàm thông thường mà lại phụ
thuộc theo kiểu tương quan hàm số nào đó, ta gọi là phụ thuộc hàm xấp xỉ. Các
nhóm thuộc tính này làm phức tạp việc xác định mẫu nên tăng chi phí cho quá
trình huấn luyện, quan trọng hơn là chúng gây nhiễu nên cây được xây dựng
không có hiệu quả cao. Ở đây, chúng ta sẽ xét đến các phụ thuộc dữ liệu loại này
nhằm xây dựng cây quyết định có khả năng dự đoán cao.
2.2 Bảng quyết định
2.2.1 Hệ thống thông tin
2.2.1.1 Định nghĩa
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á 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 giá 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ẽ viết
u(B) = v(B) nếu u(bi) = v(bi) với mọi i = 1,…,k.
26
2.2.1.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. Để kiểm chứng được
rằng đây là 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)U×U 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 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ụ
U / {Màu sắc} = {{u1, u2, u6}, {u3, u5}, {u4, u7}}
U / {Kích thước} = {{u1, u5}, {u3, u4}, {u2, u6, u7}}
U / {Hình dáng} = {{u1, u2, u6}, {u3, u4}, {u5, u7}}
U / {Màu sắc, Hình dáng} = {{u1, u2, u6}, {u3}, {u4}, {u5}, {u7}}
Màu sắc
Xanh
Xanh
Vàng
Đỏ
Kích thước
To
Hình dáng
Tròn
Nhỏ
Tròn
Vừa
Vuông
Vuông
Tam giác
Tròn
Vừa
Vàng
Xanh
Đỏ
To
Nhỏ
Nhỏ
Tam giác
Hình 2.1:
Bảng dữ liệu các đồ chơi
27
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…
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ách thứ nhất là cho tương ứng bởi “miền trong”
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 là tương ứng là B-xấp xỉ dưới và B-xấp xỉ trên
BV
BV
của V, ký hiệu là lượt là
và
cụ thể các tập xấp xỉ này được xác định như
sau:
BV u U u V ,
B
BV u U u V ,
B
BN V BV \ BV,
B
Với các xấp xỉ trên, ta gọi B-miền biên của V là tập
và B-
U \ BV
miền ngoài của V là tập
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 ngoài 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}
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:
POSB D
BV
U
VU /D
POSB
D
Rõ rằng
là tập tất cả đối tượng u sao cho với mọi v U mà u(B) =
POSB
D
v(B) ta đều có u(D) = v(D). Nói cách khác,
= {u U / [u]B [u]D}
28
Ví dụ :
U
Đau đầu
Có
Thân nhiệt
Bình thường
Cao
Cảm cúm
Không
Có
u1
u2
u3
u4
u5
u6
u7
u8
Có
Có
Rất cao
Bình thường
Cao
Có
Không
Không
Không
Không
Không
Không
Không
Có
Rất cao
Cao
Có
Rất cao
Không
Bảng 2.2: Bảng 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}.
BV
BV
Lúc đó,
= {u2, u3} và
= {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},
POSB D
BV u ,u ,u ,u
4
U
1
2
3
VU /D
2.2.2 Bảng quyết định
2.2.2.1 Định nghĩa
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ín 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 có điều kiện có thể cung cấp cho ta thong 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
29
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) chính là tập con cực đại của U sao
cho phụ thuộc hàm CD đúng.
2.2.2.2 Rút gọn thuộc tính
Trong bảng quyết định, các thuộc tính điều kiện được phân thành ba nhóm:
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 là 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.
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 POS C(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 POS C(D) phụ thuộc hàm C\{c}
D 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. Trong
trường hợp không sợ bị nhầm lẫn ta có thể viết Core thay cho Core(C).
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 T = (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 thiể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ả 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.
Core C
R
I
RRed C
Mệnh đề 1.1 [2, 9, 11]
Ví dụ 1.3 Xét bảng quyết định về bệnh cúm cho ở Bảng 2.3. Bảng này có hai
tập rút gọn là R1 = {Đau cơ, Thân nhiệt} (xem Bảng 2.4) và R2 = {Đau đầu, Thân
nhiệt} (xem Bảng 2.5). Như vậy tập lõi là Core = {Thân nhiệt} và Thân nhiệt là
30
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
chuẩn đoán đúng bệnh. Tức là
POS{Đau cơ, than nhiệt}({Cảm cúm}) = POSC({Cảm cúm}),
POS{Đau đầu, than nhiệt}({Cảm cúm}) = POSC({Cảm cúm}),
U Đau đầu
Đau cơ Thân nhiệt
Cảm cúm
Không
Có
u1
u2
u3
u4
u5
u6
Có
Có
Bình thường
Cao
Có
Có
Có
Có
Rất cao
Có
Không
Không
Không
Có
Bình thường
Không
Không
Có
Không
Có
Cao
Rất cao
Bảng 2.3: Bảng quyết định về cúm
U
Đau cơ
Có
Thân nhiệt
Bình thường
Cao
Cảm cúm
u1, u4
u2
Không
Có
Có
u3, u6
u5
Có
Rất cao
Cao
Có
Không
Không
Hình 2.4: Bảng rút gọn thứ nhất của hệ thống bệnh cúm (R1)
Tải về để xem bản đầy đủ
50 trang
25/04/2025
50
Bạn đang xem 30 trang mẫu của tài liệu "Luận văn Phụ thuộc hàm xấp xỉ và ứng dụng trong khai phá dữ liệu", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.
File đính kèm:
- luan_van_phu_thuoc_ham_xap_xi_va_ung_dung_trong_khai_pha_du.pdf
