Đại Học Quốc Gia TP.HCM
Trường Đại Học Công Nghệ Thông Tin
BÁO CÁO MÔN HỌC
Khai phá dữ liệu và kho dữ liệu
ĐỀ TÀI:
Ứng dụng tập thô để tìm xấp xỉ tập hợp,
rút gọn thuộc tính và độ phụ thuộc tính
GVHD: PGS.TS. Đỗ Phúc
Người thực hiện: Trần Duy Hùng
Mã số: CH1001105
Lớp: Cao học khóa 5
TP.HCM – 10/2012
Báo cáo môn Cơ sở dữ liệu nâng cao
MỤC LỤC

MỤC LỤC 1
DANH MỤC HÌNH ẢNH 2
LỜI MỞ ĐẦU 3
Phần I. Giới thiệu về Tập thô 4
Phần II. Chương trình ứng dụng tập thô tìm xấp xỉ tập hợp và rút gọn thuộc tính11
KẾT LUẬN 17
TÀI LIỆU THAM KHẢO 18
HVTH: Trần Duy Hùng – CH1001105 Trang 1/20
Báo cáo môn Cơ sở dữ liệu nâng cao
DANH MỤC HÌNH ẢNH

Hình I.1. Bảng hệ thống thông tin 4
Hình I.2. Bảng quyết định 5
Hình II.1. Giao diện khởi động chương trình 11
Hình II.2. Tạo bảng dữ liệu quyết định 12
Hình II.3. Chọn tập tin dữ liệu để xử lý 12

tính đó. Dù đã có nhiều cố gắng tìm tòi tài liệu nhưng do vấn đề thời gian và kiến thức
nên trong bài thu hoạch chắc chắn sẽ còn có những điều thiếu sót. Em kính mong nhận
được sự thông cảm cũng như những nội dung góp ý từ Thầy.
Xin chân thành cảm ơn Thầy!
Học viên thực hiện
Trần Duy Hùng
HVTH: Trần Duy Hùng – CH1001105 Trang 3/20
Báo cáo môn Cơ sở dữ liệu nâng cao
Phần I. Giới thiệu về Tập thô

I. Lý thuyết Tập thô
1. Hệ thống thông tin:
Một hệ thống thông tin là một biểu diễn của tập hợp dữ liệu đo lường các hiện
tượng vật lý như: giọng nói, văn bản, chuổi ảnh, các tín hiệu xử lý trong công nghiệp,
v.v
Một hệ thống thông tin bao gồm bốn thành phần:
S = <U,Q,V,f>
Trong đó:
- S: là hệ thống thông tin
- U: là tập vũ trụ đóng, tập xác định N đối tượng {x
1
,x
2
, x
3
, ,x
N
}, U không là
tập rỗng.
- Q: là tập xác định n thuộc tính {q

X6 Other High Yes Low
X7 Bank High No Medium
X8 None Low No Low
Hình I.1. Bảng hệ thống thông tin
2. Bảng quyết định
Bảng quyết định gồm cặp A = (U, A U {d}), trong đó:
• U là tập hữu hạn các đối tượng khác rỗng.
• A là tập các thuộc tính điều kiện.
• D là tập các thuộc tính quyết định (A ∩ D =
φ
).
ACCOUNT BALANCE EMPLOYED MONTHLY GOING DECISION
X1 Bank Medium Yes Low Accept
X2 Bank Low Yes High Reject
HVTH: Trần Duy Hùng – CH1001105 Trang 4/20
Báo cáo môn Cơ sở dữ liệu nâng cao
X3 None Low Yes Medium Reject
X4 Other High Yes High Accept
X5 Other Medium Yes High Reject
X6 Other High Yes Low Accept
X7 Bank High No Medium Accept
X8 None Low No Low Reject
Hình I.2. Bảng quyết định
3. Quan hệ bất khả phân biệt
Gọi S = <U,Q,V,f> là một hệ thống thông tin, A
⊆
Q là tập con của tập thuộc
tính Q; x,y ∈ U là các đối tượng trong hệ thống thông tin S. Hai đối tượng x và y được
gọi là có quan hệ tương đương trên tập thuộc tính A trong S nếu như: f(x,a) = f(y,a)
mọi a ∈A.

{X7} {X8}
+IND{BALANCE}: {X1,X5} {X2,X3,X8} {X4,X6,X7}
+IND{BALANCE,MONTHLY OUTGOING}: {X1,X3,X8} {X2,X4,X6,X8}
{X5,X7}
+IND{BALANCE, EMPLOYED}: {X1,X5} {X2,X3} {X4,X6} {X7} {X8}
+IND{BALANCE, EMPLOYED, MONTHLY OUTGOING}: {X1,X3}
{X2,X4,X6} {X5} {X7} {X8}
+IND{ACCOUNT}: {X1,X2,X7} {X3,X8} {X4,X5,X6}
+IND{ACCOUNT,MONTHLY OUTGOING}: {X1} {X2} {X3} {X4,X5}
{X6} {X7} {X8}
+IND{ACCOUNT,EMPLOYED}: {X1,X2} {X3} {X4,X5,X6} {X7} {X8}
HVTH: Trần Duy Hùng – CH1001105 Trang 5/20
Báo cáo môn Cơ sở dữ liệu nâng cao
+IND{ACCOUNT,EMPLOYED,MONTHLY OUTGOING}: {X1} {X2} {X3}
{X4,X5} {X6} {X7} {X8}
+IND{ACCOUNT,BALANCE}: {X1} {X2} {X3,X8} {X4,X6} {X5} {X7}
+IND{ACCOUNT,BALANCE,MONTHLY OUTGOING}: {X1} {X2}
{X3,X8} {X4} {X5} {X6} {X7}
+IND{ACCOUNT,BALANCE,EMPLOYED}: {X1} {X2} {X3} {X4,X6} {X5}
{X7} {X8}
+IND{ACCOUNT,BALANCE,EMPLOYED,MONTHLY OUTGOING}: {X1}
{X2} {X3} {X4} {X5} {X6} {X7} {X8}
4. Xấp xỉ tập hợp
Gọi T = (U , A) là bảng thông tin và B
⊆
A và X
⊆
U. Ta có thể xấp xỉ X dùng
các thông tin chứa trong B bằng cách tạo các xấp xỉ B dưới và B trên của X, kí hiệu
lần lượt là BX và

___
B
X / BX được gọi là B - vùng biên của X. Tập U \
___
B
X được gọi
là vùng B - vùng ngoài của X bao gồm các đối tượng chắc chắn không thuộc X. Một
tập được gọi là thô hoàn toàn nếu vùng biên của nó khác rỗng.
Tìm xấp xỉ trên và xấp xỉ dưới của từ hệ thông tin trên
+ B{MONTHLY OUTGOING} có các lớp tương đương: {{X1,X6,X8,}
{X2,X4,X5,} {X3,X7,}
- B lower = {}
- B upper = {X1,X6,X8,X2,X4,X5,X3,X7,}
+ B{EMPLOYED} có các lớp tương đương: {{X1,X2,X3,X4,X5,X6,}
{X7,X8,}
- B lower = {}
- B upper = {X1,X2,X3,X4,X5,X6,X7,X8,}
+ B{EMPLOYED,MONTHLY OUTGOING} có các lớp tương đương:
{{X1,X6,} {X2,X4,X5,} {X3,} {X7,} {X8,}
- B lower = {X1,X6,X7,}
- B upper = {X1,X6,X2,X4,X5,X7,}
HVTH: Trần Duy Hùng – CH1001105 Trang 6/20
Báo cáo môn Cơ sở dữ liệu nâng cao
+ B{BALANCE} có các lớp tương đương: {{X1,X5,} {X2,X3,X8,}
{X4,X6,X7,}
- B lower = {X4,X6,X7,}
- B upper = {X1,X5,X4,X6,X7,}
+ B{BALANCE,MONTHLY OUTGOING} có các lớp tương đương:
{{X1,X3,X8,} {X2,X4,X6,X8,} {X5,X7,}
- B lower = {}

đương: {{X1,} {X2,} {X3,X8,} {X4,} {X5,} {X6,} {X7,}
HVTH: Trần Duy Hùng – CH1001105 Trang 7/20
Báo cáo môn Cơ sở dữ liệu nâng cao
- B lower = {X1,X4,X6,X7,}
- B upper = {X1,X4,X6,X7,}
+ B{ACCOUNT,BALANCE,EMPLOYED} có các lớp tương đương: {{X1,}
{X2,} {X3,} {X4,X6,} {X5,} {X7,} {X8,}
- B lower = {X1,X4,X6,X7,}
- B upper = {X1,X4,X6,X7,}
+ B{ACCOUNT,BALANCE,EMPLOYED,MONTHLY OUTGOING} có các
lớp tương đương: {{X1,} {X2,} {X3,} {X4,} {X5,} {X6,} {X7,} {X8,}
- B lower = {X1,X4,X6,X7,}
- B upper = {X1,X4,X6,X7,}
5. Độ chính xác của xấp xỉ tập hợp
|)(|
|)(|
)(
___
XB
XB
X
B
−−−
=
α
Với |X| là lực lượng của X ≠ 0
Ta thấy rõ ràng 0 ≤ α ≤ 1
Nếu α
B
(X) = 1, X là rõ so với B.

=
DUx /∈
∑
||
|)(|
U
XC
−−−
Nếu k = 1 ta nói là D phụ thuộc hoàn toàn vào C và nếu k < 1, ta nói là D phụ
thuộc một phần vào C.
Hệ số k diễn tả tỷ lệ của các thành phần trong tập tổng thể, với sự phân loại thành
khối của phân hoạch U/D, các thuộc tính sử dụng trong C gọi là mức phụ thuộc.
7. Tập thuộc tính rút gọn và tập thuộc tính lõi
Reduct là tập nhỏ nhất trong tập các thuộc tính điều kiện nhưng có khả năng phân
lớp như toàn bộ thuộc tính. Điều đó có nghĩa là: thay vì ta phải xét tất cả các thuộc tính
HVTH: Trần Duy Hùng – CH1001105 Trang 8/20
Báo cáo môn Cơ sở dữ liệu nâng cao
điều kiện để có thể rút ra được quyết định, thì ta chỉ xét các thuộc tính điều kiện đặc
trưng nhất mà không làm ảnh hưởng gì đến quyết định cuối cùng.
Điều này làm giảm khối lượng xem xét thuộc tính điều kiện và ta sẽ phát hiện ra
các thuộc tính điều kiện dư thừa.
7.1. Ma trận phân biệt
Cho T = (U,C,D) là bảng quyết định với U là các đối tượng trong bảng
Ma trận bất khả phân biệt của T được kí hiệu là M(T) là ma trận đối xứng nn
với các phần tử M
ij
được định nghĩa như sau:




Y4
λ
X4
λ
Y1 Y2 Y1 Y2
Y4
X5 Y1 Y4
λ
λ
Y2
X6
λ
Y1 Y2
Y4
Y1 Y2
Y4
λ
Y2 Y4
X7
λ
Y2 Y3
Y4
Y1 Y2
Y3
λ
Y1 Y2 Y3
Y4
λ
X8 Y1 Y2
Y3

, u
m
) được xác định như sau
với m
ij
= {u
*
\u ∈m
ij
}
f
T
(u
*
1
, u
*
2
, u
*
m
) =
∧
{∨ m
ij
| 1 ≤ j ≤ i ≤ n, m
ij

≠


)(
Ta sẽ có được các rút gọn thuộc tính sau:
F= (Y2 ٧ Y4) ٨ (Y1 ٧ Y2 ٧ Y4) ٨ (Y1 ٧ Y2) ٨ (Y1 ٧ Y2 ٧ Y4) ٨ (Y1 ٧ Y4) ٨
(Y2) ٨ (Y1 ٧ Y2 ٧ Y4) ٨ (Y1 ٧ Y2 ٧ Y4) ٨ (Y2 ٧ Y4) ٨ (Y2 ٧ Y3 ٧ Y4) ٨ (Y1 ٧ Y2 ٧
Y3) ٨ (Y1 ٧ Y2 ٧ Y3 ٧ Y4) ٨ (Y1 ٧ Y2 ٧ Y3) ٨ (Y1 ٧ Y2 ٧ Y3 ٧ Y4) ٨ (Y1 ٧ Y2 ٧
Y3) ٨ (Y1 ٧ Y2 ٧ Y4)
= (Y2 ٧ Y4) ٨ (Y1 ٧ Y2 ٧ Y4) ٨ (Y1 ٧ Y2) ٨ (Y1 ٧ Y4) ٨ (Y2) ٨ (Y2 ٧ Y3 ٧
Y4) ٨ (Y1 ٧ Y2 ٧ Y3) ٨ (Y1 ٧ Y2 ٧ Y3 ٧ Y4)
= (Y2) ٨ (Y1 ٧ Y4) ٨ (Y1 ٧ Y2) ٨ (Y2 ٧ Y4) ٨ (Y1 ٧ Y2 ٧ Y3) ٨ (Y2 ٧ Y3 ٧
Y4) ٨ (Y1 ٧ Y2 ٧ Y4) ٨ (Y1 ٧ Y2 ٧ Y3 ٧ Y4)
= (Y2) ٨ (Y1 ٧ Y4) = (Y2 ٨ Y4) ٧ (Y1 ٨ Y2)
HVTH: Trần Duy Hùng – CH1001105 Trang 10/20
Báo cáo môn Cơ sở dữ liệu nâng cao
Phần II. Chương trình ứng dụng tập thô tìm xấp
xỉ tập hợp và rút gọn thuộc tính

II. Giới thiệu chương trình
Hình II.1. Giao diện khởi động chương trình
Trong đó bao gồm các chức năng:
- Tạo mới bảng dữ liệu: cho phép nhập tay để khởi tạo bảng dữ liệu.
- Mở tập tin dữ liệu
- Xử lý tính toán ma trận phân biệt, hàm phân biệt, rút gọn thuộc tính và tính xấp
xỉ tập hợp.
1. Tính toán ma trận phân biệt, hàm phân biệt và rút gọn thuộc tính
a. Trường hợp tự tạo mới bảng dữ liệu
- Nhấp chọn nút "TẠO MỚI"
- Nhập vào Danh sách thuộc tính (mỗi tên thuộc tính nằm trên một dòng riêng
biệt) và nhập tên thuộc tính quyết định.
- Nhấp chọn "LƯU" để chương trình ghi tên cột vào Bảng dữ liệu quyết định.
- Sau đó nhập từng dòng dữ liệu vào bảng.

Báo cáo môn Cơ sở dữ liệu nâng cao
- Tại đây, sẽ xuất hiện danh sách thuộc tính điều kiện trong khung "Các thuộc
tính điều kiện". Ta chọn thuộc tính cho tập con P và tập con Q.
- Tập con P là tập con thuộc tính cơ sở. Tập con Q là tập con thuộc tính cần tính
độ phụ thuộc vào P. Để tính được độ phụ thuộc thuộc tính P=>
k
Q. Em áp dụng công
thức tính sau:
k =
)(Q
P
γ
=
||
||
1
U
QP
N
i
∑
−−−
(với Q
i
là các phân hoạch trong lớp tương đương của tập con Q)
Hình II.8. Giao diện tính độ phụ thuộc thuộc tính
- Nhấp chọn nút "Tính độ phụ thuộc thuộc tính", kết quả của việc tính toán sẽ
xuất hiện trong khung "Tính độ phụ thuộc thuộc tính P==>Q".
Trong ví dụ này, em tính kết quả độ phụ thuộc thuộc tính của thuộc tính
"MONTHLY OUTGOING" so với tập con thuộc tính "ACCOUNT" và "BALANCE".

khái niệm rất thích hợp trong khai phá dữ liệu. Tập thô tạo nên cơ sở toán học vững
chắc để áp dụng vào khai phá dữ liệu.
Thông qua bài tiểu luận, em đã đạt được những mục tiêu sau:
+ Hiểu rõ các vấn đề quan trọng trong lý thuyết tập thô.
+ Xây dựng được chương trình để trực quan hóa từng bước trong nội dung lý
thuyết tập thô (tìm MT và hàm phân biệt, rút gọn thuộc tính, tính xấp xỉ tập hợp, tính
độ phụ thuộc thuộc tính).
+ Tìm hiểu tổng quát mối quan hệ giữa lý thuyết tập mờ và lý thuyết tập thô.
Hàm thuộc thô được xem như là một kiểu đặc biệt của hàm thuộc mờ. Mối quan hệ
giữa những hàm thuộc mờ và những hàm thuộc thô, giữa lõi và giá của lý thuyết tập
mờ và xấp xỉ trên, xấp xỉ dưới của lý thuyết tập thô.

HVTH: Trần Duy Hùng – CH1001105 Trang 17/20
Báo cáo môn Cơ sở dữ liệu nâng cao
TÀI LIỆU THAM KHẢO

[1] <PGS.TS. Đỗ Phúc>Tài liệu bài giảng Tập thô và Khai phá dữ liệu;
[2] <Ths. Nguyễn Khánh Luân> Luận văn ThS - Áp dụng kỹ thuật tập thô và tập mờ
trong phân tích dữ liệu bảo hiểm;
[3] <Jan Komrowski, Lech Polkowski, Andrzej Skowron> Rough set: A Tutorial;
[4] <Yiyu Yao and Yan Zhao> Discernibility Matrix Simplification for Constructing
Attribute Reducts;
[5] <Keyun Hu, Yuchang Lu and Chunyi Shi> Feature Ranking in Rough Set.
HVTH: Trần Duy Hùng – CH1001105 Trang 18/20