ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
Tiểu luận:
LÝ THUYẾT TẬP THÔ VÀ ỨNG DỤNG TRONG PHÁT HIỆN TRI
THỨC

HVTH: Võ Thành Nhân
MSHV: CH1301103
GVPT: TS. Dương Tôn Đảm
Thành phố Hồ Chí Minh 11 – 2014.
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
Tiểu luận môn học: Toán cho Công nghệ thông n
Tiểu luận:
LÝ THUYẾT TẬP THÔ VÀ ỨNG DỤNG TRONG PHÁT
HIỆN TRI THỨC

HVTH: Võ Thành Nhân
MSHV: CH1301103
GVPT: TS. Dương Tôn Đảm
Thành phố Hồ Chí Minh 11 – 2014.
Mục lục
2
Tiểu luận môn học: Toán cho Công nghệ thông n
3
Tiểu luận môn học: Toán cho Công nghệ thông n
1. Mở đầu
Có lẽ ai trong chúng ta cũng biết rằng lý thuyết tập hợp là một trong những lý thuyết
toán học được sử dụng rông rãi nhất, sớm nhất trong công nghệ thông tin. Vì lý thuyết tập
hợp là nền móng xây dựng nên lý thuyết cơ sở dữ liệu quan hệ, một lĩnh vực mà số lượng
ứng dụng chiếm đến 80% các ứng dụng của công nghệ thông tin và tồn tại chủ yếu trong

nhiên ta thấy rằng quan hệ này chia tách vũ trụ ban đầu thành các lớp rời nhau mà các đối
tượng trong mỗi lớp là không thể phân biệt được. Vì vậy về mặt trực giác, ta thấy rằng đó
là một quan hệ tương đương và đó là cơ sở toán học của tập thô. Tập thô gọi các lớp tương
đương đó là các tập cơ bản hay các hạt(nguyên tử) tri thức trong vũ trụ (granule(atom) of
knowledge).
Trong thế giới của tập thô, một tập hợp bất kì được biểu diễn bằng cặp xấp xỉ trên/xấp xỉ
dưới(upper approximation/lower approximation). Xấp xỉ dưới là những phần tử mà chắc
chắn là thuộc về tập đang quan tâm(ví dụ tập các bệnh nhân có bệnh), xấp xỉ trên gồm các
phần tử có thể thuộc hay không thuộc về tập đang quan tâm. Vậy tại sao không mô tả tập
hợp với các phần tử chắc chắn thuộc về nó mà lại còn thêm các phần tử có thể thuộc hoặc
không ? Ý nghĩa của tập thô là ở chỗ thay vì dùng một số lớn các tính chất để mô hình hóa,
phân loại các đối tượng thì sử dụng tập thô ta có thể sử dụng một số ít các tính chất, thông
tin mà vẫn xấp xỉ được một tập ban đầu. Để đơn giản, ta cứ hình dung, bác sĩ “rõ”(đại diện
cho tập rõ) phải hỏi 10 câu mới biết là người bệnh có bệnh hay không. Còn bác sĩ “thô”(đại
diện cho tập thô) chỉ cần hỏi 3 câu là phân loại được 90% người có bệnh hay không. Như
vây bác sĩ “thô” chỉ sữ dụng có 3 “tính chất” để phân loại 100 người, dẫu rằng còn khoảng
10 người là cần hỏi kĩ hơn. Về mặt hiệu suất, tính hiệu quả, tính tiết kiệm chi phí thì bác sĩ
“thô” làm việc tốt hơn bác sĩ “rõ”. Quan hệ bất khả phân biệt và khái niệm xấp xỉ trên/xấp
xỉ dưới là hai hòn đá tảng của lý thuyết tập thô.
1.2. Ví dụ minh họa trong tiểu luận
Để dễ dàng mô tả các khái niệm của lý thuyết tập thô, sau đây ta sẽ xét một ví dụ minh
họa. Đây là bảng dữ liệu về các triệu chứng bệnh của các bệnh nhân và kết luận là có bị
5
Tiểu luận môn học: Toán cho Công nghệ thông n
cảm cúm hay không. Các ví dụ trong các phần lý thuyết sau đây đều dựa trên bảng dữ liệu
này và ta thống nhất gọi bảng này là Bảng triệu chứng cúm.
Bệnh nhân Thân nhiệt Đau đầu Mệt mỏi Buồn nôn Cảm cúm
B1 rất cao có có không có
B2 cao có không có có
B3 bình thường không không không không

Ví dụ: Bảng triệu chứng cúm là một hệ thông tin với:
U = { B1, B2, B3, B4, B5, B6, B7, B8 }
C = { Thân Nhiệt, Đau đầu, Mệt mỏi, Buồn nôn }, D = { Cảm cúm },
V
Thân nhiệt
= {bình thường, cao, rất cao}, V
Đau đầu
= {có, không}, V
Mệt mỏi
= { có, không },
V
Buồn nôn
= { có, không }, V
Cảm cúm
= { có, không }
f(B1, Thân nhiệt) = rất cao, f(B2, Cảm cúm) = có,…
- Nếu và lúc đó hệ thông tin được gọi là bảng quyết định. Khi đó hệ thông tin sẽ được
kí hiệu là . Một bảng quyết định gọi là có tính quyết định nếu: ngược lại thì nó không có
tính quyết định.
Ví dụ: Xét các bảng dữ liệu trong cơ sở dữ liệu quan hệ có thuộc tính khóa
chính(primary keys). Trong đó các cột biểu diễn cho các thuộc tính, các hàng biểu diễn cho
các đối tượng. Đặt A = {các thuộc tính của bảng dữ liệu}, C = {các thuộc tính khóa chính
chính}, D = { các thuộc tính còn lại }. Ta có: và . Vậy bảng dữ liệu này là một bảng quyết
định. Mặt khác, theo định nghĩa vể thuộc tính khóa chính thì ta có 1 phụ thuộc hàm ,
7
Tiểu luận môn học: Toán cho Công nghệ thông n
nghĩa là : . Vậy bảng dữ liệu trong các cơ sở dữ liệu quan hệ là bảng quyết định có tính
quyết định.
Ví dụ: Bảng triệu chứng cúm là một bảng quyết định vì và . Tuy nhiên nó là bảng
không có tính quyết định do B7 và B8 giống nhau trên C nhưng khác nhau trên D.

B2 {T ,M, B }
B3 {T, Đ, M, C} {T, Đ, B, C}
B4 {T, B} {T, M} {Đ, M, B , C}
B5 {T, Đ, M} {Đ, M, B} {T, M, C} {T, Đ, B}
B6 {T, Đ, M, C} {Đ, B, C} {T} {T, Đ, M, B, C} {M, C}
B7 {T, Đ, C} {T, Đ, M, B, C} {M} {Đ, B, C} {T, C} {T, M}
B8 {T, Đ} {T, Đ, M, B} {M, C} {Đ, B} {T} {T, M, C} {C}
(T: Thân nhiệt, Đ: Đau đầu, M: Mệt mỏi, C: Cảm cúm)
2.3. Xấp xỉ một tập hợp
- Ý tưởng cơ bản của tập thô là mô tả hay xấp xỉ một tập hợp rõ bằng cặp xấp xỉ
trên/xấp xỉ dưới. Với một tập thuộc tính P bất kì(P ⊆ A), nếu không thể dùng nó để mô tả
chính xác một tập hợp X, thì cặp xấp xỉ trên/xấp xỉ dưới được dùng đến. Cho hệ thông tin ,
P A, X U. Bây giờ chúng ta muốn sử dụng tập thuộc tính P để mô tả tập các đối tượng
X(được đặc trưng bằng một số tính chất nào đó), khi đó X được sinh ra bởi cặp xấp xỉ
trên/xấp xỉ dưới kí hiệu bởi như định nghĩa dưới đây:
và gọi là P – xấp xỉ dưới của X
gọi là P – xấp xỉ trên của X
Theo định nghĩa trên ta thấy rằng:
• là tập các đối tượng mà sử dụng tập thuộc tính mô tả P ta chắc chắn chúng là
thành viên của X.
• là tập các đối tượng mà sử dụng tập thuộc tính mô tả P ta chỉ có thể nói rằng các
đối tượng đó có thể là thành viện của X.
9
Tiểu luận môn học: Toán cho Công nghệ thông n
•
- Nếu thì X là tập rõ hay tập P - chính xác(P – exact), ngược lại thì X là tập P –
thô(P – though). Đặt , ta gọi là vùng P – biên(P – boundary) gồm các đối tượng mà sử
dụng tập thuộc tính P ta không thể xác định chúng có thuộc X hay không. Tập hợp U gọi
là vùng P – ngoài của X(P – outside region of X) gồm các đối tượng mà sử dụng tập thuộc
tính mô tả P chắc chắn chúng không là thành viên của X. Một hình ảnh trực quan về các

số : U {0,1} (X gọi là hàm đặc trưng hay hàm thuộc của tập X, sao cho ∀ u , = 1 thì u X,
ngược lại = 0 thì u ∉ X. Một cách tương ứng, trong lý thuyết tập thô ta cũng định nghĩa
một hàm thuộc thô như sau:
Cho hệ thông tin , X U, P A, hàm U , ∀ x :
Khi đó hàm được gọi là hàm thuộc thô của tập P – thô X.
- Từ định nghĩa của hàm thuộc thô, ta rút ra một số tính chất sau:
1)
2)
3) 0
X
11
Tiểu luận môn học: Toán cho Công nghệ thông n
4) Nếu
5)
= 1 - ,
6) 7)
2.5. Rút gọn các thuộc tính
Cho hệ thông tin ; P, Q .
2.5.1. Sự phụ thuộc các thuộc tính
- Ta nói rằng tập thuộc tính Q phụ thuộc hoàn toàn vào tập thuộc tính P và kí hiệu là
P → Q ⇔ IND(P) IND(Q) hay nói cách khác:
x, y : f(x, p) = f(y, p) f(x, q) = f(y, q) Q
12
Tiểu luận môn học: Toán cho Công nghệ thông n
Việc tìm ra sự phụ thuộc giữa các thuộc tính là vấn đề rất quan trọng trong việc tìm các luật
quyết định(decision rules), một trong những ứng dụng quan trọng nhất của tập thô trong
Data mining.

- Cho a P, P’ = P – {a}, nếu IND(P) = IND(P’) thì thuộc tính a gọi là bỏ qua
được(dispensable) ngược lại thì a gọi là không bỏ qua được(indispensable). Trong thực
hành cũng như trong lý thuyết ta luôn mong muốn tìm tập P với ít thuộc tính nhất mà vẫn
không giảm khả năng phân loại. Tập tất cả các thuộc tính không bỏ qua được của P gọi là
lõi(core) của P, kí hiệu là CORE(P).
13
Tiểu luận môn học: Toán cho Công nghệ thông n
- Một thuộc tính a P gọi là Q – bỏ qua được trong P nếu POS
P
(Q) = POS
P-{a}
(Q)
ngược lại thì a là Q – không thể bỏ được trong P. Tập tất cả thuộc tính Q – không bỏ qua
được trong P gọi là Q – lõi tương đối, kí hiệu là CORE
Q
(P)
- Nếu a P, a là không bỏ qua được thì P gọi là trực giao(orthogonal). Cho P’ ⊆ P và
P’ là trực giao, nếu IND(P’) = IND(P) thì P’ gọi là một rút gọn(reduct) của P, kí hiệu là P’
= RED(P). Từ đây ta suy ra CORE(P) =
- P gọi là Q – trực giao nếu tất cả thuộc tính của P là Q – không bỏ được. Cho P’⊆ P
là Q – trực giao, nếu POS
P’
(Q) = POS
P
(Q) thì B gọi là một Q – rút gọn (Q – reduct) của P
và kí hiệu P’ = RED
Q
(P). Từ định nghĩa Q – rút gọn ta có CORE
Q
(P) =

bên trong các dữ liệu. Trong lý thuyết tập thô, dạng tri thức này được giới hạn trong các
bảng quyết định và các luật này gọi là các luật quyết định có dạng sau đây:
IF conditions THEN decision class.
Nghĩa là nếu đối tượng thỏa mãn điều kiện của luật thì sẽ phân lớp đối tượng đó vào một
lớp quyết định. Tìm kiếm các luật quyết định là một trong những ứng dụng cơ bản, quan
trọng nhất của tập thô trong Data mining.
Cho bảng quyết định T. Trong đó C là tập thuộc tính điều kiện và {d} là một thuộc
tính quyết định. V
d
= {d
1
, d
2
,…, d
n
}
- Cho x ∈ U, a ∈ , kí hiệu a(x) = f(x, a).
- Một luật quyết định r trong T là một luật có dạng: IF (c
1
= v
1
) ˄ (c
2
= v
2
) ˄… ˄ (c
m
=
v
m

) ˄… ˄ (c
m
= v
m
) THEN d
= d
k
, r gọi là phủ(cover) x hay x thỏa mãn điều kiện của luật r nếu { (c
1
, c
1
(x)) , {(c
2
, c
2
(x)) ,
…, {(c
m
, c
m
(x)) }. ∀x ∈ U, nếu luật r phủ x và f(x, d) = d
k
thì ta gọi r là luật chắc chắn.
Tuy nhiên trong thực tế, xuất hiện những trường hợp mà r phủ x nhưng f(x, d) ≠ d
k
.
15
Tiểu luận môn học: Toán cho Công nghệ thông n
- Cho X ∈ U|IND({d}) = { D
1

) coverage(r, D
i
)
r1: IF (Đau đầu=không)˄(Mệt mỏi=không) THEN Cảm cúm=không 0.25 1 0.67
r2: IF (Đau đầu=có) THEN Cảm cúm=có 0.38 1 0.6
r3: IF (Thân nhiệt=cao)˄(Mệt mỏi=có) THEN Cảm cúm=có 0.13 1 0.2
3. Ứng dụng tập thô trong phát hiện tri thức
3.1. Khai phá dữ liệu (Data mining)
Ngày nay, lượng thông tin mà xã hội loài người tạo ra không ngừng tăng lên với một
tốc độ chóng mặt. Người ta ước đoán rằng lượng thông tin trên toàn cầu tăng gấp đôi sau
khoảng hai năm và theo đó số lượng cũng như kích cỡ của các cơ sở dữ liệu (CSDL) cũng
tăng lên một cách nhanh chóng. Thông tin tràn ngập khắp mọi nơi nhất là trong các mạng
xã hội(social network), các giao dịch thương mại điện tử, các phương tiện truyền thông đa
phương tiện(multimedia), các dự án nghiên cứu trên khắp thế giới…Nếu như trước đây,
trong các hệ thống thông tin quản lý(Management Information System), người ta đã có
kinh nghiệm rằng: từ những dữ liệu giao dịch, mua bán hàng ngày luôn chứa đựng những
thông tin quý giá, bổ ích cho vấn đề phát triển, kiểm soát, điều chỉnh kế hoạch kinh doanh
16
Tiểu luận môn học: Toán cho Công nghệ thông n
cho tổ chức, xí nghiệp, thì bây giờ người ta cũng tự hỏi là liệu trong lượng dữ liệu đồ sộ kia
có tiềm ẩn những thông tin có ích nào hay không ?
Trước khi Data mining ra đời thì các công cụ, phân tích và xử lý dữ liệu không thể nào
đáp ứng được nhu cầu phân tích một lượng dữ liệu đồ sộ và ngày càng phình to như thế.
Trước tình hình đó, các nhà khoa học máy tính mới lao vào nghiên cứu, tìm tòi và sáng tạo
ra các công cụ phân tích dữ liệu mới mà có khả năng xử lý được một lượng dữ liệu đồ sộ.
Và thuật ngữ Data mining ra đời từ đó. Nói một cách hình thức thì Data mining là: Tập
hợp các kĩ thuật xử lý dữ liệu một cách tự động được sử dụng nhằm phát hiện ra các thông
tin ẩn chứa trong dữ liệu mà có thể chưa biết và có tiềm năng hữu ích. Cụ thể hơn Data
Mining như là một công cụ giúp khám phá những mối liên hệ ẩn, những hình mẫu(pattern)
dữ liệu chung từ những kho dữ liệu được tích lũy trong suốt quá trình hoạt động của một tổ

liệu theo trình tự thời gian. Ví dụ: một công ty bán hàng điện máy có thể phát
hiện ra rằng khi một khách hàng mua một tủ lạnh thì có đến 60% khả năng 1
tháng sau anh ta sẽ mua một lò vi sóng.
• Bài toán dự báo(Forecasting): dự báo ở đây là dựa vào một số giá trị hiện hành
của một số đối tượng dữ liệu và dự báo giá trị của các đối tượng dữa liệu. Ví dụ:
công cụ Data mining có thể tìm ra một số hình mẫu dữ liệu để giúp các nhà quản
lý dự báo giá trị giá trị tương lai của một số đối tượng dữ liệu quan tâm chẳng
hạn như doanh thu bán hàng.
3.2. Phát hiện tri thức trong cơ sở dữ liệu (Knowledge Discovery in Database – KDD)
Phát hiện tri thức trong cơ sở dữ liệu(hay nói vắn tắt là phát hiện tri thức) là lĩnh vực
nghiên cứu và ứng dụng tập trung vào dữ liệu, thông tin và tri thức. Về mặt hình thức thì có
thể định nghĩa phát hiện tri thức là: Một quá trình có nhiều pha, mang tính tương tác và
lặp nhằm phát hiện ra những hình mẫu hay những mô hình dữ liệu có thể hiểu được, hợp
lệ và mới lạ có tiềm năng mang lại giá trị sử dụng từ một nguồn dữ liệu lớn. Phát hiện tri
thức là một lĩnh vực rộng lớn liên quan đến nhiều ngành khác nhau của khoa học máy tính
và hệ thống thông tin như: Trí tuệ nhân tạo, Cơ sở dữ liệu, Tính toán hiệu năng cao, Tính
toán mềm, Thống kê…như minh họa trong hình sau đây:
18
Tiểu luận môn học: Toán cho Công nghệ thông n
Như vậy chúng ta thấy ngay là trong KDD đã bao hàm luôn Data mining. Thật vậy,
Data mining là một pha then chốt quá trình phát hiện tri thức bởi hệ thống có thu được tri
thức mới hay không là phục thuộc vào kết quả của pha này. Từ kết quả của pha này hệ
thống tiến hành biểu diễn tri thức vừa thu nhận được và sau đó đưa vào đánh giá, sử dụng.
Một quá trình phát hiện tri thức có thể bao gồm các pha sau đây:
• khảo sát miền ứng dụng và xác định, phát biểu vấn đề.
• thu thập và tiền xử lý dữ liệu(Selection and Preprocessing).
• biến đổi dữ liệu sao cho phù hợp với các thao tác của Data
mining(Transformation)
• sử dụng các phương pháp Data mining để trích rút ra các dạng và các mô hình
ẩn trong dữ liệu(Data mining).

THEN b
1
=w
1
, , b
k
=w
k
với một độ support và độ tin cậy cho trước, A =
{a
1
, , a
m
}, B={b
1
, , b
k
} là những tập thuộc tính không biết trước. Để giải bài toán này ta
20
Tiểu luận môn học: Toán cho Công nghệ thông n
chỉ cần giải bài toán tìm A – vùng dương của B POS
A
(B) không rỗng mà thực chất là tìm
luật quyết định với tập thuộc tính điều kiện A và tập thuộc tính quyết định B thỏa mãn một
số tiêu chí về độ mạnh và độ chính xác của luật.
4. Kết luận
Tiểu luận đã tập trung làm những việc sau đây:
• Nêu một cái nhìn tổng quan về ý nghĩa, vai trò của tập thô trong công nghệ
thông tin.
• Cố gắng làm rõ một số khái niệm căn bản của tập thô thông qua các định nghĩa,