ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
________oOo________
BÀI THU HOẠCH MÔN HỌC
KHAI PHÁ DỮ LIỆU &
KHO DỮ LIỆU

LÝ THUYẾT TẬP THÔ &
ỨNG DỤNG TÌM MA TRẬN PHÂN BIỆT
PGS. TS.: ĐỖ PHÚC
HỌC VIÊN: NGUYỄN HOÀNG HUY
MSHV: CH1101090
< 2012 >
KHAI PHÁ DỮ LIỆU VÀ KHO DỮ LIỆU PGS. TS. ĐỖ PHÚC
MỤC LỤC
BÀI THU HOẠCH MÔN HỌC Trang 2
KHAI PHÁ DỮ LIỆU VÀ KHO DỮ LIỆU PGS. TS. ĐỖ PHÚC
A. LÝ THUYẾT TẬP THÔ
1. Tổng quan
Lý thuyết tập thô được Z. Pawlak phát triển vào đầu thập niên 1980. Lý thuyết tập
thô rất hiệu quả trong khai thác dữ liệu (KTDL), tìm kiếm thông tin, hỗ trợ quyết
định, máy học, các hệ cơ sở tri thức. Rất nhiều ứng dụng sử dụng ý tưởng của lý
thuyết tập thô như phân tích dữ liệu y khoa, lượng giá điều phối hang không, xử lý
ảnh, nhận dạng…
Hầu hết cơ sở dữ liệu (CSDL) được sử dụng cho việc KTDL đều không hoàn
thiện về dữ liệu. Lý thuyết tập thô là công cụ nhằm giải quyết sự gần đúng và các
trường hợp không chắc chắn.
Một ưu điểm của lý thuyết tập thô đối với hướng tiếp cận xác suất Bayes là không
cần giả định về sự độc lập của các thuộc tính cũng như không cần bất kỳ kiến thức
nền nào về dữ liệu.
2. Các hệ thong tin

a. Hệ thông tin
Hệ thông tin là tập hợp dữ liệu được biểu diễn dưới dạng bảng, trong đó mỗi
dòng biểu diễn một trường hợp, một sự kiện, một khác hang… hoặc là một đối
tượng. Mỗi cột biểu diễn một thuộc tính và có thể đo đạc được với từng đối tượng.
Một cách hình thức, hệ thông tin là cặp A = (U, A). Trong đó U là tập hữu hạn
khác rỗng các đối tượng (tập phổ quát) và A là tập hữu hạn khác rỗng các thuộc
tính sao cho a : U → V
a
với mỗi thuộc tính a ∈ A. Tập V
a
được gọi là tập giá trị
của thuộc tính a.
Ví dụ 2.a:
Cho bảng thể hiện một hệ thông tin như sau:
Độ_tuổi Số_buổi
x
1
16-30 50
x
2
16-30 0
x
3
31-45 1-25
x
4
31-45 1-25
x
5
46-60 26-49

x
6
16-30 26-49
x
7
46-60 26-49
Bảng gồm bảy đối tượng (x
1
→ x
7
) và hai thuộc tính (Độ_tuổi, Số_buổi)
Ta thấy các bộ x
3
và x
4
cũng như x
5
và x
7
có cùng giá trị của thuộc tính
Độ_tuổi. Các bộ này – theo từng cặp – là bất khả phân biệt với thuộc tính
Độ_tuổi.
BÀI THU HOẠCH MÔN HỌC Trang 3
KHAI PHÁ DỮ LIỆU VÀ KHO DỮ LIỆU PGS. TS. ĐỖ PHÚC
b. Hệ quyết định
Ta thấy có sự phân loại kết quả trong nhiều ứng dụng – đó là sự mô tả tri thức
bởi một thuộc tính đặc trưng phân biệt được gọi là thuộc tính quyết định. Hệ
thống này là một hình thức học có giám sát. Các hệ thông tin theo loại này được
gọi là các hệ quyết định. Một hệ quyết định là một hệ thông tin có dạng (U ; A ∪
{d}). Trong đó d ∉ A là thuộc tính quyết định. Các thành phần thuộc tính của A

được gọi là các thuộc tính điều kiện hoặc gọi đơn giản là các thuộc tính. Thuộc
tính quyết định có thể có nhiều hơn hai giá trị mặc dù thường gặp là thuộc tính nhị
phân.
Ví dụ 2.b:
Cho bảng quyết định đơn giản như sau:
Độ_tuổi Số_buổi Thi_đậu
x
1
16-30 50 Có
x
2
16-30 0 Không
x
3
31-45 1-25 Không
x
4
31-45 1-25 Có
x
5
46-60 26-49 Không
x
6
16-30 26-49 Có
x
7
46-60 26-49 Không
Bảng này có them thuộc tính quyết định là Thi_đậu với hai khả năng kết quả.
Có thể nhận thấy các bộ x
3

và x
4
cũng như x
5
và x
7
có cùng giá trị của thuộc
tính Độ_tuổi và Số_buổi. Nhưng cặp x
3
, x
4
có kết quả Thi_đậu khác nhau trong
khi cặp x
5
, x
7
có cùng kết quả Thi_đậu.
Có thể rút từ bảng quyết định này ra luật sau:
“Nếu Độ_tuổi là 16-30 và Số_buổi là 50 thì Thi_đậu là Có”.
Trong tiến trình tạo tập luật sau này cần lưu ý đến việc rút gọn vế trái của luật.
3. Quan hệ bất khả phân biệt
Một hệ quyết định (bảng quyết định) biểu diễn tất cả các tri thức về mô hình.
Bảng này có thể có kích thước lớn một cách không cần thiết vì bảng này là dư thừa ít
nhất ở hai mặt. Các đối tượng giống nhau hoặc bất khả phân biệt có thể được biểu
diễn nhiều lần hoặc thừa.
Một quan hệ nhị phân R ⊆ X × X là có tính phản xạ (một đối tượng sẽ có quan hệ
với chính nó xRx), phản xứng (nếu xRy thì yRx) và bắc cầu (nếu xRy và yRz thì xRz)
được gọi là một quan hệ tương đương. Lớp tương đương của một phần tử x ∈ X bao
gồm tất cả các đối tượng y ∈ X sao cho xRy.
BÀI THU HOẠCH MÔN HỌC Trang 4

KHAI PHÁ DỮ LIỆU VÀ KHO DỮ LIỆU PGS. TS. ĐỖ PHÚC
Cho một hệ thông tin S = (U; A), với tập thuộc tính B ⊆ A có quan hệ tương
đương tương ứng IND
S
(B):
IND
S
(B) = {(u; v) ∈ U
2
| ∀a ∈ B, a(u) = a(v)}
IND
S
(B) được gọi là quan hệ bất khả phân biệt theo B. Nếu (u, v) ∈ IND
S
(B) thì
các đối tượng u và v là không thể phân biệt lẫn nhau qua tập thuộc tính B. Các lớp
tương đương của quan hệ bất khả phân biệt theo B được ký hiệu là [x]
B
(ký hiệu S
trong quan hệ bất khả phân biệt thường được lược bỏ vì ta xác định được hệ thông tin
nào đang khảo sát).
Ví dụ 3:
Quan hệ bất khả phân biệt được định nghĩa với bảng quyết định
Độ_tuổi Số_buổi Thi_đậu
x
1
16-30 50 Có
x
2
16-30 0 Không

x
3
31-45 1-25 Không
x
4
31-45 1-25 Có
x
5
46-60 26-49 Không
x
6
16-30 26-49 Có
x
7
46-60 26-49 Không
Các tập con khác rỗng của các thuộc tính điều kiện là {Độ_tuổi}, {Số_buổi} và
{Độ_tuổi, Số_buổi}.
Với tập {Số_buổi}, các bộ x
3
và x
4
thuộc cùng một lớp tương đương và bất khả
phân biệt. Tương tự cho các bộ x
5
, x
6
và x
7
thuộc vào các lớp tương đương. Quan hệ
tương đương IND trên các tập thuộc tính {Độ_tuổi}, {Số_buổi} và {Độ_tuổi,

Số_buổi} cho ta các phân hoạch tập U như sau:
IND({Độ_tuổi}) = {{x
1
; x
2
; x
6
}; {x
3
; x
4
}; {x
5
; x
7
}}
IND({Số_buổi}) = {{x
1
}; {x
2
}; {x
3
; x
4
}; {x
5
; x
6
; x
7

}}
IND({Độ_tuổi, Số_buổi}) = {{x
2
}; {x
2
}; {x
3
; x
4
}; {x
5
; x
7
}; {x
6
}}
4. Xấp xỉ tập hợp
Một quan hệ tương đương dẫn đến một phân hoạch tập phổ quát U (tập các bộ
trong hệ thông tin). Có thể dùng phép phân hoạch để tạo các tập con mới của tập phổ
quát. Các tập con thường được quan tâm là các tập con có cùng giá trị của thuộc tính
quyết định. Tuy nhiên không thể phân định rõ ràng một số khái niệm.
Ví dụ không thể định nghĩa một cách rõ ràng tập các khách hàng có trị dương cho
thuộc tính quyết định (Thi_đậu = Có) bằng các thuộc tính khác trong bảng quyết định
ở ví dụ 3. Những khách hàng “gặp khó khăn” là các bộ x
3
và x
4
. Nói cách khác, không
BÀI THU HOẠCH MÔN HỌC Trang 5
KHAI PHÁ DỮ LIỆU VÀ KHO DỮ LIỆU PGS. TS. ĐỖ PHÚC

thể có một định nghĩa chính xác với những khách hàng như vậy từ bảng này. Từ đây
phát sinh khái niệm tập thô.
Mặc dù ta không thể xác định khách hàng một cách chính xác nhưng có thể chỉ ra
các khách hàng nào chắc chắn có trị dương cho thuộc tính quyết định, các khách hàng
nào chắc chắn không có kết quả dương cho thuộc tính quyết định và cuối cùng là các
khách hàng nào thuộc vào vùng biên giữa các trường hợp chắc chắn. Nếu vùng biên
này là khác rỗng, tập đang xét là tập thô. Các khái niệm trên được biểu diễn một cách
hình thức như sau:
Cho hệ thông tin IS = (U; A) và cho B ⊆ A và X ⊆ U. Ta có thể xấp xỉ tập đối
tượng X chỉ với thông tin chứa trong tậo thuộc tính B bằng cách xây dựng các xấp xỉ
B-dưới và B-trên của tập X, ký hiệu tương ứng là và , trong đó:
= {x | [x]
B
⊆ X} và
= {x | [x]
B
∩ X ≠ ∅}
Các đối tượng trong có thể chắc chắn được phân lớp như là các thành viên của tập
X theo tập thuộc tính B, trong khi các đối tượng trong chỉ có thể phân lớp là các
thành viên có kết quả dương tính của tập X theo tập thuộc tính B.
Tập BN
B
(X) = - được gọi là cùng B-biên của tập X và chứa các đối tượng mà ta
không thể phân lớp chắc chắn vào X dựa theo tập thuộc tính B.
Tập U - được gọi là vùng B-ngoài của X và chứa các đối tượng phấn lớp chắc
chắn là không thuộc về tập X dựa theo tập thuộc tính B.
Một tập hợp được gọi là thô nếu vùng biên là khác rỗng. Ngược lại, một tập hợp
được gọi là rõ nếu vùng biên là rỗng.
Ví dụ 4:
Gọi tập đối tượng W = {x | Thi_đậu(x) = Có} = {x

1
, x
4
, x
6
} và B = {Độ_tuổi,
Số_buổi} theo ví dụ 3. Ta có các vùng xấp xỉ:
= {x
1
; x
6
}
= {x
1
; x
3
; x
4
; x
6
}
BN
B
(W) = {x
3
; x
4
} và U - = {x
2
; x

5
; x
7
}
Như vậy lớp quyết định Thi_đậu là thô vì vùng biên khác rỗng
BÀI THU HOẠCH MÔN HỌC Trang 6
KHAI PHÁ DỮ LIỆU VÀ KHO DỮ LIỆU PGS. TS. ĐỖ PHÚC
Xấp xỉ tập các khách hàng có thuộc tính quyết định Thi_đậu qua hai thuộc tính
điều kiện là Độ_tuổi và Số_buổi. Các lớp tương đương được trình bày theo các vùng
tương ứng.
Có thể chứng minh các tính chất sau của các tập xấp xỉ tập hợp:
(1) (X) ⊆ X ⊆ (X)
(2) (∅) = (∅) = ∅, (U) = (U) = U
(3) (X ∪ Y) = (X) ∪ (Y)
(4) (X ∩ Y) = (X) ∩ (Y)
(5) X ⊆ Y ⇒ (X) ⊆ (Y) và (X) ⊆ (Y)
(6) (X ∪ Y) ⊇ (X) ∪ (Y)
(7) (X ∩ Y) ⊆ (X) ∩ (Y)
(8) (U – X) = – (X)
(9) (U – X) = – (X)
(10) ((X)) = ((X)) = (X)
(11) ((X)) = ((X)) = (X)
Có thể định nghĩa bốn lớp cơn bản của tập thô ứng với bốn loại mập mờ như sau:
1. X là có thể xác định thô theo B
nếu và chỉ nếu (X) ≠ ∅ và (X) ≠ U;
2. X là không thể xác định phía trong theo B
nếu và chỉ nếu (X) = ∅ và (X) ≠ U;
3. X là không thể xác định phía ngoài theo B
nếu và chỉ nếu (X) ≠ ∅ và (X) = U;
4. X là hoàn toàn không thể xác định theo B

nếu và chỉ nếu (X) = ∅ và (X) = U;
Độ chính xác của xấp xỉ: Tập thô còn có thể đặc trưng hóa dưới hình thức số bằng
hệ số phản ánh độ chính xác của xấp xỉ:
Trong đó |X| biểu diễn lực lượng của tập X ≠ ∅
Và ta có 0 ≤ (X) ≤ 1
Nếu (X) = 1, X là rõ theo B (X là chính xác theo B).
Nếu (X) < 1, X là thô theo B (X là gần đúng theo B).
5. Rút gọn
a. Định nghĩa
Một rút gọn của hệ thông tin IS là một tập tối tiểu các thuộc tính B ⊆ A sao
cho IND
S
(B) = IND
S
(A).
BÀI THU HOẠCH MÔN HỌC Trang 7
KHAI PHÁ DỮ LIỆU VÀ KHO DỮ LIỆU PGS. TS. ĐỖ PHÚC
Nói cách khác, một rút gọn là một tập tối tiểu các thuộc tính từ tập thuộc tính
A, mà rút gọn này bảo toàn việc phân hoạch tập phổ quát U và vì thế bảo toàn khả
năng phân lớp thay vì phải thực hiện với toàn bộ tập thuộc tính A.
Ví dụ 5.a:
Cho bảng quyết định :
Bằng_cấp
Kinh_nghiệ
m
Tiếng_An
h
Giới_thiệu
Tuyển_dụn
g

X
1
MBA Vừa Tốt Xuất_sắc Chấp_nhận
X
2
MBA Thấp Tốt
Trung_bìn
h
Từ_chối
X
3
MCE Thấp Tốt Tốt Từ_chối
X
4
MSC Nhiều Tốt
Trung_bìn
h
Chấp_nhận
X
5
MSC Vừa Tốt
Trung_bìn
h
Từ_chối
X
6
MSC Nhiều Tốt Xuất_sắc Chấp_nhận
X
7
MBA Nhiều Không Tốt Chấp_nhận

X
8
MCE Thấp Không Xuất_sắc Từ_chối
Ta có:
S’ = (U;{Bằng_cấp, Kinh_nghiệm, Tiếng_Anh, Giới_thiệu}∪{Tuyển_dụng})
Nếu chỉ xem xét các thuộc tính điều kiện nghĩa là với hệ thông tin:
S = (U;{Bằng_cấp, Kinh_nghiệm, Tiếng_Anh, Giới_thiệu})
Để đơn giản, mỗi lớp tương đương chỉ chứa một phần tử. Theo quan sát cho
thấy tồn tại một tập tối tiểu các thuộc tính là {Kinh_nghiệm, Giới_thiệu} cho phép
phân biệt các đối tượng như là toàn bộ tập thuộc tính của các đối tượng đang xét.
Ngoài ra cũng có thể kiểm chứng là quan hệ tương đương với toàn bộ tập thuộc
tính và quan hệ tương đương với tập {Kinh_nghiệm, Giới_thiệu} là như nhau.
b. Ma trận phân biệt
Với S là một hệ thông tin có n đối tượng, ma trận phân biệt của S là một ma
trận đối xứng n × n với các giá trị c
ij
được định nghĩa như sau :
c
ij
= {a ∈ A | a(x
i
) ≠ a(x
j
)} với i, j = 1 n
Mỗi dòng bao gồm tập giá trị các thuộc tính khác nhau với các đối tượng x
i
, x
j
.
Ví dụ 5.b:

Từ ví dụ 5.a, ta sắp lại thứ tự của bảng quyết định theo thuộc tính Tuyển_dụng
như sau:
Bằng_cấp
(d)
Kinh_nghiệ
m
(e)
Tiếng_An
h
(f)
Giới_thiệu
(r)
Tuyển_dụn
g
BÀI THU HOẠCH MÔN HỌC Trang 8
KHAI PHÁ DỮ LIỆU VÀ KHO DỮ LIỆU PGS. TS. ĐỖ PHÚC
X
1
MBA Vừa Tốt Xuất_sắc Chấp_nhận
X
4
MSC Nhiều Tốt
Trung_bìn
h
Chấp_nhận
X
6
MSC Nhiều Tốt Xuất_sắc Chấp_nhận
X
7

MBA Nhiều Không Tốt Chấp_nhận
X
2
MBA Thấp Tốt
Trung_bìn
h
Từ_chối
X
3
MCE Thấp Tốt Tốt Từ_chối
X
5
MSC Vừa Tốt
Trung_bìn
h
Từ_chối
X
8
MCE Thấp Không Xuất_sắc Từ_chối
Ta có ma trận phân biệt tương ứng là đối xứng và có đường chéo rỗng:
[x
1
] [x
4
] [x
6
] [x
7
] [x
2

] [x
3
] [x
5
] x
8
]
[x
1
]
∅
[x
4
]
∅ ∅
[x
6
]
∅ ∅ ∅
[x
7
]
∅ ∅ ∅ ∅
[x
2
] e, r d, e d, e, r e, f, r
∅
[x
3
] d, e, r d, e, r d, e, r d, e, f

∅ ∅
[x
5
] d, r e e, r d, e, f, r
∅ ∅ ∅
[x
8
] d, e, f d, e, f, r d, e, f d, e, r
∅ ∅ ∅ ∅
c. Hàm phân biệt
Hàm phân biệt f
S
của hệ thông tin S là một hàm bool của m biến bool a
*
1
;
…;a
*
m
(ứng với các thuộc tính a
1
;…;a
m
) và được định nghĩa như sau :
f
IS
(a
*
1
;…;a

*
m
) = ∧{∨ | 1 ≤ j ≤ i ≤ n, c
ij
≠ ∅}
trong đó = {a
*
| a ∈ c
ij
}
Tập các đơn thức của f
IS
xác định tập các rút gọn của IS.
Ví dụ 5.c:
Từ ví dụ 5.b, ta có hàm phân biệt liên quan đến quyết định là
Từ định nghĩa của ma trận phân biệt liên quan đến quyết định, tiến hành chọn
một cột của ma trận bất khả phân biệt (ví dụ như tương ứng với [x
1
]) và đơn giản
hóa nó cho hàm tối tiểu phân biệt [x
1
] với các đối tượng thuộc vào các lớp quyết
định tương ứng từ các đối tượng thuộc về các lớp quyết định khác (ví dụ như cột
thứ nhất cho hàm bool là (e∨r)(d∨e∨r)(d∨r)(d∨e∨f), ta đơn giản hóa trở thành
ed∨rd∨re∨rf.
Ta thấy các trường hợp x
1
và x
6
đúng với luật “Nếu Giới_thiệu là Xuất_sắc và

Tiếng_Anh là Tốt thì Tuyển_dụng là Chấp_nhận”.
Nếu một hàm bool như trường hợp hàm phân biệt k-tương đối được xâu dựng
bằng việc giới hạn chỉ duyệt trên các cột liên quan đến các đối tượng với quyết
BÀI THU HOẠCH MÔN HỌC Trang 9
KHAI PHÁ DỮ LIỆU VÀ KHO DỮ LIỆU PGS. TS. ĐỖ PHÚC
định trên x
k
thì ta thu được hàm phân biệt (k, d) tương đối. Các luật quyết định với
số lượng điều kiện ít nhất ở vế trái có thể được xây dựng từ các đơn thức của các
hàm này.
6. Phụ thuộc thuộc tính
Một vấn đề quan trọng khác trong phân tích dữ liệu là phát hiện sự phụ thuộc giữa
các thuộc tính. Bằng trực giác, một tập thuộc tính D phụ thuộc hoàn toàn vào một tập
thuộc tính C (ký hiệu C ⇒ D), nếu tất cả giá trị của các thuộc tính trong D được xác
định duy nhất bởi các giá trị của C.
Cho D và C là các tập thuộc tính con của A. Ta nó rằng D phụ thuộc vào C ở mức
k (0 ≤ k ≤ 1), ký hiệu C ⇒
k
D nếu :
Trong đó: được gọi là vùng dương của phép phân hoạch U theo tập thuộc tính D.
Với C là tập mọi thành phần của U có thể được phân lớp theo phép phân hoạch U/D.
Hiển nhiên:
Nếu k = 1 ta nói rằng D phụ thuộc hoàn toàn vào C.
Nếu k < 1 ta nói rằng D phụ thuộc một phần (theo mức độ k) vào C.
BÀI THU HOẠCH MÔN HỌC Trang 10
KHAI PHÁ DỮ LIỆU VÀ KHO DỮ LIỆU PGS. TS. ĐỖ PHÚC
B. ỨNG DỤNG TÍNH MA TRẬN PHÂN BIỆT
1. Giới thiệu
Chương được viết bằng ngôn ngữ C# trên bộ Microsoft Visual C# 2010 Express
Input: Bản quyết định từ file Excel

Output: Ma trận phân biệt
2. Cài đặt
Chương trình gồm một số hàm chính như sau:
public static DataTable ReadExcelContents(string fileName)
public static bool BangQuyetDinhHopLe(DataGridView dataGridView)
public static void XuLyBangQuyetDinh(ref DataGridView dataGridView)
public static void TimMaTranPhanBiet(ref DataGridView dataGridView1,
ref DataGridView dataGridView2)
3. Thử nghiệm
BÀI THU HOẠCH MÔN HỌC Trang 11
KHAI PHÁ DỮ LIỆU VÀ KHO DỮ LIỆU PGS. TS. ĐỖ PHÚC
BÀI THU HOẠCH MÔN HỌC Trang 12
KHAI PHÁ DỮ LIỆU VÀ KHO DỮ LIỆU PGS. TS. ĐỖ PHÚC
BÀI THU HOẠCH MÔN HỌC Trang 13
KHAI PHÁ DỮ LIỆU VÀ KHO DỮ LIỆU PGS. TS. ĐỖ PHÚC
TÀI LIỆU THAM KHẢO
1. Giáo trình Khai thác dữ liệu – PGS. TS. Đỗ Phúc.
2. Giáo trình bài giảng Khai thác dữ liệu & Kho dữ liệu – PGS. TS. Đỗ Phúc.
3. Một số tài liệu tham khảo từ internet.
BÀI THU HOẠCH MÔN HỌC Trang 14