Bài thu hoạch môn KPDL và kho dữ liệu GVHD: PGS.TS. Đỗ Phúc
LỜI MỞ ĐẦU
Trong thời đại ngày nay, việc tìm kiếm thông tin trên cơ sở dữ liệu khổng lồ,
việc xử lý các thông tin rời rạc, không đầy đủ đang được rất nhiều người quan tâm.
Có nhiều phương pháp để giải quyết các vấn đề trên, nhưng có một phương pháp
đang được nhiều người nghiên cứu, đó là phương pháp tìm kiếm trên tập thô. Rất
nhiều ứng dụng dựa trên ý 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 hàng không, xử lý ảnh, nhận dạng, …
Chính vì lý do trên nên sau khi học xong môn Khai phá dữ liệu và kho dữ
liệu, em đã chọn đề tài “Xây dựng chương trình tự động rút gọn Reducts từ hệ
quyết định trong tập thô”. Trong phạm vi bài thu hoạch này em xin trình bày tóm
tắt những kiến thức đã học được về lý thuyết tập thô và viết một chương trình tự
động rút gọn Reducts từ hệ quyết định trong tập thô bằng ngôn ngữ C#.
Qua đây, em xin chân thành cảm ơn PGS.TS. Đỗ Phúc đã tận tình hướng
dẫn em môn học bổ ích và đầy ý nghĩa này. Em xin cảm ơn các bạn cùng khoá và
các anh chị khoá trước đã giúp đỡ em tìm tài liệu và góp ư cho em hoàn thành tốt
bài thu hoạch này!
Cao Thị Thuỳ Linh – MSHV: CH1101099 Trang 1
Bài thu hoạch môn KPDL và kho dữ liệu GVHD: PGS.TS. Đỗ Phúc
NHẬN XÉT CỦA GIẢNG VIÊN HƯỚNG DẪN
của tập thô như sau:
• Hệ thông tin / quyết định
Cao Thị Thuỳ Linh – MSHV: CH1101099 Trang 3
Bài thu hoạch môn KPDL và kho dữ liệu GVHD: PGS.TS. Đỗ Phúc
• Quan hệ bất khả phân biệt
• Xấp xỉ tập hợp
• Rút gọn và lơi
• Thành viên thô
• Phụ thuộc thuộc tính
I.2. Hệ thông tin / quyết định
Một tập dữ liệu có thể biểu diễn dưới dạng một bảng, trên đó mỗi dòng biểu
diễn thông tin ứng với một đối tượng, mỗi cột biểu diễn một thuộc tính có thể đo
được của mỗi đối tượng (do các chuyên gia hay người sử dụng cung cấp). Bảng
này được gọi là một hệ thông tin.
Hình thức hơn, hệ thông tin là một cặp S = (U, A)
• Trong đó U là một tập hữu hạn khác rỗng các đối tượng gọi là tập vũ trụ hay là tập
phổ dụng, A là một 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 I
a
là tập tất cả giá trị của thuộc tính a, thì u( a) ∈ I
a
với mọi u ∈ U. Bây
giờ, nếu B = {b
1
, b
2
, ,b
k
} ⊆ A, ta ký hiệu bộ các giá trị u(b

x1 16-30 50 có
x2 16-30 0 không
x3 31-45 1-25 không
x4 31-45 1-25 có
x5 46-60 26-49 không
x6 16-30 26-49 có
x7 46-60 26-49 không
Bài thu hoạch môn KPDL và kho dữ liệu GVHD: PGS.TS. Đỗ Phúc
• Trong bảng này, các bộ x3 và x4 cũng như x5 và x7 có cùng giá trị của các thuộc
tính điều kiện (độ tuổi và số buổi) nhưng cặp x3 và x4 có kết quả thi đậu khác nhau
trong khi cặp x5 và x7 có cùng kết quả thi đậu.
I.3. Quan hệ bất khả phân biệt
Một hệ quyết định thể hiện tri thức về các đối tượng trong thế giới thực. Tuy
nhiên trong nhiều trường hợp bảng này có thể được tinh giảm do tồn tại ít nhất hai
khả năng dư thừa thông tin sau đây:
Nhiều đối tượng giống nhau hay không thể phân biệt với nhau lại được thể
hiện lặp lại nhiều lần
Một số thuộc tính có thể là dư thừa, theo nghĩa khi bỏ đi các thuộc tính này thì
thông tin do hệ quyết định cung cấp mà chúng tâm sẽ không bị mất mát
Một quan hệ nhị phân R ⊆ X x X được gọi là quan hệ tương đương khi có các
tính chất sao:
• Tính phản xạ (xRX với mọi x)
• Tính đối xứng (nếu xRy thì yRx)
• Tính bắc cầu (nếu xRy và yRz thì xRz)
Một quan hệ tương đương R sẽ phân hoạch tập đối tượng thành các lớp
tương đương, trong đó lớp tương đương của một đối tượng x là tập tất cả các đối
tượng có quan hệ R với x.
Xét hệ thông tin S = (U, A), với mỗi tập thuộc tính B
⊆
A tạo ra một quan hệ

đương và bất khả phân biệt. Tương tự cho các bộ x5, x6 và x7 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}, {độ tuổi, số buổi} cho ta phân hoạch tập U như sau:
IND({độ tuổi}) ={{x1,x2,x6}; {x3,x4}; {x5,x7}}
IND({số buổi}) ={{x1}; {x2}; {x3,x4}; {x5,x6,x7}}
IND({độ tuổi, số buổi }) ={{x1}; {x2}; {x3,x4}; {x5,x7}; {x6}}
Ví dụ 2: Xét hệ quyết định sau:

Cao Thị Thuỳ Linh – MSHV: CH1101099 Trang 7
U Đau đầu Đau cơ Nhiệt độ Cúm
x1 Không Có Cao Có
x2 Có Không Cao Có
x3 Có Có Rất cao Có
x4 Không Có Bình thường Không
x5 Có Không Cao Không
x6 Không Có Rất cao Có
Bài thu hoạch môn KPDL và kho dữ liệu GVHD: PGS.TS. Đỗ Phúc
Trong đó:
U = {x1, x2, x3, x4, x5, x6}.
A = {Đau đầu, Đau cơ, Nhiệt độ, Cúm}.
Trong bảng, các bệnh nhân x2, x3 và x5 không phân biệt được đối với
thuộc tính Đau đầu, bệnh nhân x3 và x6 không phân biệt được đối với thuộc tính
Đau cơ, Cúm và bệnh nhân x2, x5 không phân biệt được đối với thuộc tính Đau
đầu, Đau cơ và Nhiệt độ.
Do đó:
IND( {Đau đầu}) = {{x1, x4, x6},{x2, x3, x5}}
IND( {Đau cơ}) = {{x1, x3, x4, x6}, {x2, x5}}
IND( {Nhiệt độ}) = {{x1, x2, x5}, {x3, x6}, {x4}}
IND( {Cúm}) = {{x1, x2, x3, x6}, {x4, x5}}
IND( {Đau đầu, Đau cơ}) = {{x1, x4, x6}, {x2, x5}, {x3}}

B
(X) ≠ ∅, X được gọi là tập thô, ngược lại X được gọi
là tập rõ.
Các tính chất của xấp xỉ
• B (X) ⊆ X ⊆ (X)
• B (∅) = (∅) = ∅, B (U) = (U) = U
• (X ∪ Y) = (X) ∪ (Y)
• B (X ∩ Y) = B(X) ∩ B (Y)
• X ⊆ Y ⇒ (X) ⊆ (X) và B(X) ⊆ B(Y)
• B(X ∪ Y) ⊇ B(X) ∪ B(Y)
• (X ∩ Y) ⊆ (X) ∩ (Y)
Cao Thị Thuỳ Linh – MSHV: CH1101099 Trang 9
Bài thu hoạch môn KPDL và kho dữ liệu GVHD: PGS.TS. Đỗ Phúc
• B(- X) = - (X)
• (- X) = - B(X)
• B ( B(X)) = ( B(X)) = B(X)
• ( (X)) = B( (X)) = (X)
• Trong đó –X là ký hiệu của U-X
Độ chính xác của xấp xỉ
Cho một hệ thống thông tin S = (U, A), với mỗi tập con X ⊆ U và B ⊆ A,
đặt R = IND(B), đại lượng đo sự chính xác của tập xấp xỉ X đối với phân hoạch
trên B là giá trị
Trong đó card(X) = |X| là lực lượng (số phần tử) của tập X.
Rõ ràng 0 ≤ α
R
(X) ≤ 1 . Nếu α
R
(X) = 1, ta nói X là chính xác đối với R,
còn α
R

Bước 5 : Kết thúc
Ví dụ 1: Xét hệ quyết định trên ví dụ 2 phần hệ thông tin / quyết định
Gọi tập đối tượng X = {x | Thi đậu(x) = có} = {x1, x4, x6}
và B={độ tuổi, số buổi}
Ta có các lớp tương đương :
IND({độ tuổi, số buổi }) ={{x1}; {x2}; {x3,x4}; {x5,x7}; {x6}}
Ta có các vùng xấp xỉ :
Cao Thị Thuỳ Linh – MSHV: CH1101099 Trang 11
Bài thu hoạch môn KPDL và kho dữ liệu GVHD: PGS.TS. Đỗ Phúc
BX = {x1,x6}
X = {x1, x6, x3, x4}
BN
B
(X) = X – BX = {x1, x6, x3, x4} - {x1,x6} = {x3, x4}
NEG
B
(X) = U - X = {x1, x2, x3, x4, x5,x6} - {x1, x6, x3, x4}
= {x2,x5,x7}
Như vậy lớp quyết định thi đậu là thô vì vùng biên khác rỗng
Ví dụ 2: Xét hệ quyết định trên ví dụ 2 phần quan hệ bất khả phân biệt
Gọi tập đối tượng X = {x | Cúm(x) = có} = {x1, x2, x3, x6}
và B={ Đau đầu, Đau cơ }
Ta có các lớp tương đương :
IND( {Đau đầu, Đau cơ}) = {{x1, x4, x6}, {x2, x5}, {x3}}
Ta có các vùng xấp xỉ :
BX = {x3}
X = {x3, x1, x4, x6, x2, x5}
BN
B
(X) = X – BX = {x3, x1, x4, x6, x2, x5}- {x3}

Xét hệ thông tin A = (U,A) và hai tập thuộc tính P, Q ⊆ A. Thuộc tính a ∈ P
được gọi là có thể bỏ được trong P nếu IND(P) = IND(P – {a}), ngược lại ta nói a
là không thể bỏ được trong P. Rõ ràng thuộc tính có thể bỏ được không là tăng
hoặc giảm khả năng phân loại khi có hoặc không có mặt thuộc tính đó trong P. Tập
tất cả các thuộc tính không thể bỏ được trong P được gọi là lõi (core) của P, ký
hiệu là CORE(P). Lưu ý rằng lõi có thể là tập rỗng, khi đó tập con của P với lực
lượng bằng card(P) – 1 đều giữ nguyên khả năng phân loại của P
Khi loại ra khỏi P một số thuộc tính có thể bỏ được thì ta được một tập rút
gọn của P. Nói cách khác, rút gọn của một tập thuộc tính P là tập thuộc tính B ⊆ P
giữ nguyên khả năng phân loại của P, hay IND(B) = IND(P). Dễ dàng thấy rằng, vì
lõi của P là tập các thuộc tính không thể bỏ được của P nên tất cả các rút gọn của P
đều chứa tập thuộc tính lõi
Cao Thị Thuỳ Linh – MSHV: CH1101099 Trang 13
Bài thu hoạch môn KPDL và kho dữ liệu GVHD: PGS.TS. Đỗ Phúc
Một rút gọn B của tập thuộc tính P được gọi là rút gọn hoàn toàn nếu với mọi
tập thuộc tính B’ ⊂ B, B’ không là rút gọn của P. Như vậy rút gọn hoàn toàn là tập
thuộc tính nhỏ nhất trong tất cả các rút gọn có thể có của P và được ký hiệu là
RED(P)
Tính chất: Tập thuộc tính lõi của P là giao của tất cả các rút gọn hoàn toàn
của P, tức là CORE(P)= ∩ RED(P)
I.5.2. Ma trận phân biệt
Với S là một hệ thông tin với n đối tượng, ma trận phân biệt của S là một ma
trận đối xứng n x n với các giá trị c
ij
được định nghĩa như sau:
c
ij
= {a A | a(x
i
) a(x

i
và X
j
hay có thể nói c
ij
là tập các thuộc
tính phân biệt
Cao Thị Thuỳ Linh – MSHV: CH1101099 Trang 14
Bài thu hoạch môn KPDL và kho dữ liệu GVHD: PGS.TS. Đỗ Phúc
Ví dụ 1: Cho hệ quyết định như sau :
N0 a b c d
u1 a0 b1 c1 y
u2 a1 b1 c0 n
u3 a0 b2 c1 n
u4 a1 b1 c1 y
Khi đó, ma trận phân biệt sẽ được tính như sau :
Ví dụ 2: Cho hệ quyết định như sau :
a b c d e
u1 1 0 2 1 1
u2 1 0 2 0 1
u3 1 2 0 0 2
u4 1 2 2 1 0
u5 2 1 0 0 2
u6 2 1 1 0 2
u7 2 1 2 1 1
Khi đó, ma trận phân biệt sẽ được tính như sau :
u1 u2 u3 u4 u5 u6
u2
λ
u3 a,b,c b,c

u4 Trong Bắc Thấp Không mưa
u5 Mây Bắc Thấp Mưa
u6 Mây Bắc Cao Mưa
u7 Mây Nam Thấp Không mưa
Cao Thị Thuỳ Linh – MSHV: CH1101099 Trang 16
Headache Muscle pain Temp Flu
u1 Yes Yes Normal No
u2 Yes Yes High Yes
u3 Yes Yes Very-High Yes
u4 No Yes Normal No
u5 No No High No
u6 No Yes Very-High Yes
u1 u2 u3 u4 u5
u2 Temp
u3 Temp
λ
u4
λ
Headache ,
Temp
Headache ,
Temp
u5
λ
Headache ,
Muscle
Headache ,
Muscle, Temp
λ
u6 Headache ,

λ
Gió Gió,
Áp suất
u8
λ
Trời Trời, Gió,
Áp suất
λ
Trời, Gió,
Áp suất
Trời,
Gió
λ
Khi đó, ma trận phân biệt sẽ được tính như sau :
Ví dụ 5: Cho hệ quyết định như sau :
Cao Thị Thuỳ Linh – MSHV: CH1101099 Trang 17
Vóc dáng Quốc tịch Gia cảnh Nhóm
u1 Nhỏ Đức Độc thân A
u2 Lớn Pháp Độc thân A
u3 Lớn Đức Độc thân A
u4 Nhỏ Ý Độc thân B
u5 Lớn Đức Có gia đình B
u6 Lớn Ý Độc thân B
u7 Lớn Ý Có gia đình B
u8 Nhỏ Đức Có gia đình B
Bài thu hoạch môn KPDL và kho dữ liệu GVHD: PGS.TS. Đỗ Phúc
Khi đó, ma trận phân biệt sẽ được tính như sau :
u1 u2 u3 u4 u5 u6 u7
u2
λ

Ví dụ 6: Cho hệ quyết định như sau :
Kích thước Màu sắc Hình dạng Lớp
u1 Vừa Xanh Viên gạch A
u2 Nhỏ Đỏ Hình nêm B
u3 Nhỏ Đỏ Hình cầu A
u4 Lớn Đỏ Hình nêm B
u5 Lớn Lục Hình trụ A
u6 Lớn Đỏ Hình trụ B
u7 Lớn Lục Hình cầu A
Khi đó, ma trận phân biệt sẽ được tính như sau :
u1 u2 u3 u4 u5 u6
u2 Kích thước,
Màu sắc,
Cao Thị Thuỳ Linh – MSHV: CH1101099 Trang 18
Bài thu hoạch môn KPDL và kho dữ liệu GVHD: PGS.TS. Đỗ Phúc
Hình dạng
u3
λ
Hình dạng
u4 Kích thước,
Màu sắc,
Hình dạng
λ
Kích thước,
Hình dạng
u5
λ
Kích thước,
Màu sắc,
Hình dạng

u7 6 8 3 4 1
Cao Thị Thuỳ Linh – MSHV: CH1101099 Trang 19
Bài thu hoạch môn KPDL và kho dữ liệu GVHD: PGS.TS. Đỗ Phúc
Khi đó, ma trận phân biệt sẽ được tính như sau :
u1 u2 u3 u4 u5 u6 u7
u2 a,b,c,d
u3 a,c,d a,b,c
u4 b,c
λ
a,b,d
u5 d a,b,c,d
λ
b,c,d
u6 a,b,c,d a,b,c
λ
a,b,d
λ
u7 a,b,c,d
λ
b,c
λ
a,b,c,d b,c
u8 a,b,c,d d
λ
a,c,d
λ λ
a,d
I.5.3. Hàm phân biệt
Hàm phân biệt f
s

*
| 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.
Lưu ý :
• Các toán tử ∧ và ∨ sử dụng trong hàm phân biệt không phải là các toán tử Boolean
vì chúng không nhận các giá trị true hoặc false mà thể hiện cho ngữ nghĩa có mặt
hay không có mặt của một thuộc tính nào đó
• Hàm phân biệt có thể xem như một tập các tập hợp. Và cũng giống như với ma
trận phân biệt, tập nhỏ nhất có giao với tất cả các phần tử chính là các rút gọn của
hệ thông tin tương ứng
Ví dụ 1: Dựa vào ma trận phân biệt trong ví dụ 1 phần ma trận phân biệt, ta
tính được hàm phân biệt như sau :
Hàm phân biệt F(a,b,c) = (a ∨ c) ∧ b ∧ c ∧ (a ∨ b)
Cao Thị Thuỳ Linh – MSHV: CH1101099 Trang 20
Bài thu hoạch môn KPDL và kho dữ liệu GVHD: PGS.TS. Đỗ Phúc
Ví dụ 2: Dựa vào ma trận phân biệt trong ví dụ 2 phần ma trận phân biệt, ta
tính được hàm phân biệt như sau :
Hàm phân biệt F(a,b,c,d) = (b ∨ c ∨ d ) ∧ (b ∨ c) ∧ b ∧ (b ∨ d) ∧ (c ∨
d) ∧ (a ∨ b ∨ c ∨ d ) ∧ (a ∨ b ∨ c ) ∧ (a ∨ b ∨ c ∨ d ) ∧ (a ∨ b ∨ c ∨ d ) ∧ (a ∨ b ∨
c) ∧ (a ∨ b ∨ c ∨ d ) ∧ (a ∨ b ∨ c ∨ d ) ∧ (a ∨ b) ∧ (c ∨ d ) ∧ (c ∨ d )
Ví dụ 3: Dựa vào ma trận phân biệt trong ví dụ 3 phần ma trận phân biệt, ta
tính được hàm phân biệt như sau :
Hàm phân biệt F(Headache, Muscle pain, Temp) = Temp ∧ Temp ∧
(Headache ∨ Temp) ∧ (Headache ∨ Temp) ∧ (Headache ∨ Muscle pain) ∧
(Headache ∨ Muscle pain ∨ Temp) ∧ (Headache ∨ Temp) ∧ Temp ∧ (Muscle pain
∨ Temp)

I.5.4. Tính Reducts từ hàm phân biệt
Các luật được sử dụng để rút gọn hàm phân biệt:
• Luật giao hoán
a ∨ b = b ∨ a
a ∧ b = b ∧ a
• Luật hấp thụ:
(a ∨ b) ∧ a = a
(a ∧ b) ∨ a = a
• Luật lũy đẳng
a ∨ a = a
a ∧ a = a
• Luật phân bố:
Cao Thị Thuỳ Linh – MSHV: CH1101099 Trang 22
Bài thu hoạch môn KPDL và kho dữ liệu GVHD: PGS.TS. Đỗ Phúc
a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)
• Luật kết hợp:
(a ∧ b) ∨ (a ∧ c) = a ∧ (b ∨ c)
(a ∨ b) ∧ (a ∨ c) = a ∨ (b ∧ c)
Thuật toán tìm Reducts:
Gọi A = (U, C ∪ D) là hệ thông tin
Gọi R là tập rút gọn
Thuật toán:
Bước 1: Tính POS
R
(D) và đặt m=| POS
R
(D) |
Bước 2: Với mọi a ∈ A
Tính POS

= (b ∧ c) ∨ (b ∧ d) (luật phân bố)
Vậy Reducts1 = {b, c} và Reducts2 = {b, d}
Ví dụ 3: Dựa vào hàm phân biệt trong ví dụ 3 phần hàm phân biệt, ta tính
được Reducts như sau :
Hàm phân biệt F(Headache, Muscle pain, Temp )
= Temp ∧ Temp ∧ (Headache ∨ Temp) ∧ (Headache ∨ Temp) ∧
(Headache ∨ Muscle pain) ∧ (Headache ∨ Muscle pain ∨ Temp) ∧ (Headache ∨
Temp) ∧ Temp ∧ (Muscle pain ∨ Temp)
= Temp ∧ (Headache ∨ Temp) ∧ (Headache ∨ Muscle pain)
∧ (Headache ∨ Muscle pain ∨ Temp)
∧ (Muscle pain ∨ Temp)
(luật lũy đẳng)
= Temp ∧ (Headache ∨ Muscle pain) ∧ (Muscle pain ∨ Temp)
(luật hấp thụ)
= Temp ∧ (Muscle pain ∨ Temp) ∧ (Headache ∨ Muscle pain)
(luật giao hoán)
= Temp ∧ (Headache ∨ Muscle pain) (luật hấp thụ)
= (Temp ∧ Headache) ∨ (Temp ∧ Muscle pain ) (luật phân bố)
Vậy Reducts 1 = { Temp, Headache } và Reducts 1 ={ Temp, Muscle pain }
Cao Thị Thuỳ Linh – MSHV: CH1101099 Trang 24
Bài thu hoạch môn KPDL và kho dữ liệu GVHD: PGS.TS. Đỗ Phúc
Ví dụ 4: Dựa vào hàm phân biệt trong ví dụ 4 phần hàm phân biệt, ta tính
được Reducts như sau :
Hàm phân biệt F(Trời, Gió, Áp suất)
= (Trời ∨ Gió) ∧ (Trời ∨ Áp suất) ∧ (Trời ∨ Gió ∨ Áp suất) ∧
(Trời ∨ Áp suất) ∧ (Trời ∨ Áp suất) ∧ Trời ∧ Trời ∧ (Trời ∨ Áp suất) ∧ Áp
suất ∧ (Gió ∨ Áp suất) ∧ Gió ∧ (Gió ∨ Áp suất) ∧ Trời ∧ (Trời ∨ Gió ∨ Áp
suất) ∧ (Trời ∨ Gió ∨ Áp suất) ∧ (Trời ∨ Gió)
= (Trời ∨ Gió) ∧ (Trời ∨ Áp suất) ∧ (Trời ∨ Gió ∨ Áp suất) ∧
Trời ∧ Áp suất ∧ (Gió ∨ Áp suất) ∧ Gió (luật lũy đẳng)