Khai thác d
ữ

li
ệ
u

Bayes và Tập thô

Gi
ớ
i thi
ệ
u

v
ề

xu h
ư
ớ
ng nghiên c
ứ
u Khai thác d
ữ

li
ệ
u,

d) Gom cụm dữ liệu (Data Clustering) 9
e) Phân tích những biến đổi và độ lệch (Evolution and deviation analysis) 10
6) Một số hệ thống Khai thác dữ liệu: 10
7) Ứng dụng của Khai thác dữ liệu: 11
8) Những thách thức trong Khai thác dữ liệu: 11
III) Phân lớp và dự đoán dữ liệu (Classification and Prediction): 12
1) Phân lớp dữ liệu (data classification): 12
2) Một số phương pháp phân lớp dữ liệu: 13
a) Phân lớp quy nạp trên cây quyết định (Classification by decision tree induction): 13
b) Phân lớp sử dụng mạng neural lan truyền ngược (Classification by backpropagation) 13
c) Phương thức phân lớp khác 14
3) Dự đoán dữ liệu (data prediction): 14
4) Mức độ chính xác của phân lớp dữ liệu 15
a) Tính toán độ chính xác của bộ phân lớp: 15
b) Gia tăng độ chính xác: 15
IV) Phân lớp Bayes (Bayesian Classification) 16
2

1) Công thức Bayes (Bayes Theorem) 16
2) Bộ phân lớp Naïve Bayes 16
3) Ví dụ minh họa: 17
4) Giải thuật huấn luyện Bộ phân lớp Naïve Bayes: 19
5) Giải thuật phân lớp Naïve Bayes: 20
6) Mạng Bayes (Bayesian belief networks) 20
7) Huấn luyện Mạng Bayes 22
V) Lý thuyết tập thô (Rough Set Theory) 23
1) Lý thuyết tập hợp 23
2) Hệ thông tin và hệ quyết định 24
3) Xấp xỉ tập hợp 24
4) Ma trận phân biệt và thuật toán quyết định 26

Sự phát triển của Công Nghệ Thông Tin và việc ứng dụng Công Nghệ Thông Tin
trong nhiều lĩnh vực của đời sống, kinh tế xã hội trong nhiều năm qua cũng đồng nghĩa
với lượng dữ liệu đã được các cơ quan thu thập và lưu trữ ngày một tích luỹ nhiều lên.
Họ lưu trữ các dữ liệu này vì cho rằng trong nó ẩn chứa những giá trị nhất định nào đó.
Tuy nhiên, theo thống kê thì chỉ có một lượng nhỏ của những dữ liệu này (khoảng từ 5%
đến 10%) là luôn được phân tích, số còn lại họ không biết sẽ phải làm gì hoặc có thể làm
gì với chúng nhưng họ vẫn tiếp tục thu thập rất tốn kém với ý nghĩ lo sợ rằng sẽ có cái gì
đó quan trọng đã bị bỏ qua sau này có lúc cần đến nó. Mặt khác, trong môi trường cạnh
tranh, người ta ngày càng cần có nhiều thông tin với tốc độ nhanh để trợ giúp việc ra
quyết định và ngày càng có nhiều câu hỏi mang tính chất định tính cần phải trả lời dựa
trên một khối lượng dữ liệu khổng lồ đã có. Với những lý do như vậy, các phương pháp
quản trị và khai thác cơ sở dữ liệu truyền thống ngày càng không đáp ứng được thực tế đã
làm phát triển một khuynh hướng kỹ thuật mới đó là Kỹ thuật Khai thác dữ liệu (Data
Mining)
Khai thác dữ liệu (Data Mining) ra đời chính là sự phát triển tự nhiên và tất yếu
của ngành Công Nghệ Thông Tin. Đó là một tiến trình khám phá tri thức hữu ích tiềm ẩn
trong các Cơ sở dữ liệu
4 Hình 2.1: Vị trí của Khai thác dữ liệu trong Hệ thống thong tin

2) Lịch sử phát triển của Khai thác dữ liệu:
Những năm 1960: Cơ sở dữ liệu và Công Nghệ Thông Tin đã dần phát triển từ hệ
thống xử lý các tập tin cơ bản thành những hệ Cơ sở dữ liệu phức tạp.
Trong những năm 1970: đây là giai đoạn phát triển mạng của công nghệ Cơ sở dữ
liệu. Nền tảng lý thuyết về Cơ sở dữ liệu quan hệ được hình thành, ra đời các công cụ mô
hình hóa dữ liệu, các kỹ thuật tổ chức dữ liệu, phát triển các ngôn ngữ truy vấn dữ liệu,
xử lý dữ liệu
Từ giữa thập niên 1980: Lý thuyết về Cơ sở dữ liệu dần hoàn thiện. Xuất hiện các

Khai thác dữ liệu là tiến trình quan trọng nhất trong KDD. Một hệ Khai thác dữ
liệu thông thường có các thành phần sau:
- Cơ sở dữ liệu (Database), Kho dữ liệu (Data Warehouse) hay một kho chứa thông
tin: là nguồn dữ liệu, thông tin sẽ được khai thác. Trong những tình huống cụ thể,
thành phần này là nguồn nhập (input) của các kỹ thuật tích hợp và làm sạch dữ
liệu.
- Database hay Data Warehouse server: chịu trách nhiệm chuẩn bị dữ liệu phù hợp
với quá trình Khai thác dữ liệu.
- Hệ Cơ sở tri thức (Knowledge base): chứa các tri thức miền (domain knowledge)
được dùng để hướng dẫn quá trình tìm kiếm, đánh giá các mẫu kết quả tìm được.
Tri thức miền có thể là các phân cấp khái niệm (concept hierarchies), niềm tin của
người sử dụng (user beliefs), các ràng buộc (constraints) hay các ngưỡng giá trị
(thresholds), siêu dữ liệu (metadata) …

Hình 2.3: Cấu trúc một hệ Khai thác dữ liệu

- Bộ Khai thác dữ liệu (Data mining engine): chứa các khối chức năng thực hiện các
tác vụ Khai thác dữ liệu.
- Pattern evaluation module: làm việc với các độ đo (và các ngưỡng giá trị) hỗ trợ
tìm kiếm và đánh giá các mẫu sao cho các mẫu được tìm thấy là những mẫu được
quan tâm bởi người sử dụng; có thể được tích hợp vào thành phần Bộ Khai thác dữ
liệu.
- Giao diện người dùng (Graphical user interface): hỗ trợ sự tương tác giữa người sử
dụng và hệ thống Khai thác dữ liệu:
7

o Người sử dụng có thể chỉ định câu truy vấn hay tác vụ Khai thác dữ liệu.
o Người sử dụng có thể được cung cấp thông tin hỗ trợ việc tìm kiếm, thực
hiện Khai thác dữ liệu sâu hơn thông qua các kết quả khai phá trung gian.
o Người sử dụng cũng có thể xem các lược đồ cơ sở dữ liệu/kho dữ liệu, các


c) Cơ sở dữ liệu giao tác (Transactional Database):
Một Cơ sở dữ liệu giao tác có một tập tin mà mỗi bảng ghi của nó là một phiên
giao tác.

d) Các cơ sở dữ liệu cao cấp và Cơ sở dữ liệu hướng ứng dụng:
Nhu cầu xử lý các loại dữ liệu ngày càng tăng cao. Các ứng dụng Cơ sở dữ liệu
không gian, Cơ sở dữ liệu đa phương tiện, siêu văn bản, World – Wide – Web …. yêu
cầu các cấu trúc dữ liệu thật tốt và các phương thức xử lý các đối tượng có cấu trúc phức
tạp, rất nhiều bảng ghi (record), những dữ liệu không có cấu trúc, dữ liệu đa phương
tiện….
Để đáp ứng được những nhu cầu này, các Cơ sở dữ liệu hướng ứng dụng, hướng
đối tượng và các Cơ sở dữ liệu cao cấp được ra đời và phát triển.

9

5) Các kỹ thuật Khai thác dữ liệu:
a) Diễn tả ý niệm: Mô tả tính chất và so sánh (Concept/Class description:
characterization and discrimination)
Diễn tả ý niệm: mô tả những khái niệm thành những hình thái khác tóm lược, ngắn
gọn và chính xác. Diễn tả ý niệm chia làm hai loại Mô tả tính chất dữ liệu (data
characterization) và So sánh dữ liệu (data discrimination)
Mô tả tính chất dữ liệu: cung cấp những tóm lược ngắn gọn về dữ liệu đưa vào
So sánh dữ liệu: cung cấp các mô tả về hai hay nhiều tập dữ liệu.

b) Phân tích luật kết hợp (Association analysis)
Phân tích luật kết hợp chính là khám phá ra các luật kết hợp (Association rules) –
các giá trị, các thuộc tính thường xuất hiện chung với nhau trong một tập dữ liệu. Luật
kết hớp được ứng dụng rộng rãi trong các Cơ sở dữ liệu giao tác, Cơ sở dữ liệu quan hệ
và một số Cơ sở dữ liệu khác.

và đạt được nhiều thành tựu đáng kể. Một số hệ thống Khai thác dữ liệu nổi tiếng như:
- Intelligent Miner (IBM)

Hình 2.5: Giao diện Intelligent Miner

- Microsoft data mining tools (Microsoft SQL Server 2000/2005/2008)
- Oracle Data Mining (Oracle 9i/10g/11g)
- Enterprise Miner (SAS Institute)
11

- Weka (the University of Waikato, New Zealand, www.cs.waikato.ac.nz/ml/weka)

Hình 2.6: Giao diện của Weka

7) Ứng dụng của Khai thác dữ liệu:
Khai thác dữ liệu được ứng dụng rộng rãi trong rất nhiều lĩnh vực như:
- Tài chính – Ngân hàng: xây dựng mô hình dự báo rủi ro tín dụng; tìm kiếm các
quy luật thị trường chứng khoán và đầu tư bất động sản…
- Thương mại điện tử và maketing: phân tích khách hàng duyệt web; phân tích hành
vi mua sắm ở một phân khu thị trường nhất định; xác định sở thích khách hàng…
- Công nghệ Sinh học và dược phẩm: phân tích dữ liệu di truyền; xác định sự hiện
diện của dược phẩm…
- An ninh – bảo mật: phát hiện giả mạo thẻ trong giao dịch trực tuyến; quản lý rủi ro
trong viễn thông, thương mại diện tử; phát hiện các hành vi trốn thuế…

8) Những thách thức trong Khai thác dữ liệu:
Khai thác dữ liệu ngày nay luôn phải làm việc với một lượng dữ liệu khổng lồ từ
nhiều nguồn khác nhau nên có rất nhiều vấn đề và thách thức đặt ra cho ngành khoa học
về Khai thác dữ liệu
- Phương pháp Khai thác dữ liệu và vấn đề về tương tác người dùng: Khai thác

nhau.

13

2) Một số phương pháp phân lớp dữ liệu:
a) Phân lớp quy nạp trên cây quyết định (Classification by decision tree induction):
Cây quyết định (decision tree) là một cấu trúc gồm các nút trong (internal node)
biểu diễn giá trị thuộc tính, các nhánh (branch) biểu diễn đầu ra của kiểm tra, và nút lá
(leaf node) biểu diễn các nhãn lớp (class label).

Hình 3.1: Mô hình một cây quyết định

Cây quyết định được tạo theo hai giai đoạn: tạo cây (Tree Contruction) và tỉa
nhánh (Tree pruning)
- Tạo cây: lúc đầu, tất cả các mẫu học đều nằm ở nút gốc (root node). Sau đó, các
mẫu học được phân chia một cách đệ quy dựa trên thuộc tính được chọn
- Tỉa nhánh: tìm và xóa các nhánh có phần tử không thuộc về lớp nào cả

b) Phân lớp sử dụng mạng neural lan truyền ngược (Classification by
backpropagation)
Lan truyền ngược (backpropagation) là một giải thuật huấn luyện mạng neural
(neural network learning).
Mạng neural là một họ các quá trình xử lý thông tin dựa trên mô hình các neural
thần kinh của con người. Mạng neural kết hợp một số lượng lớn các thành phần đơn giản
14

(neural) thành các cấu trúc phức tạp nhằm giải quyết một vấn đề cụ thể nào đó. Giống


4) Mức độ chính xác của phân lớp dữ liệu
Tính toán độ chính xác của bộ phân lớp là rất quan trọng, nó cho phép đánh giá
xem một bộ phân lớp sẽ dán nhãn cho các dữ liệu tương lai chính xác hay không, các dữ
liệu nào bộ phân lớp chưa được huấn luyện… và so sánh giữa các bộ phân lớp
(classifiers)
a) Tính toán độ chính xác của bộ phân lớp:
Có ba phương pháp dùng để tính toán độ chính xác của bộ phân lớp:
- Phân hạch (holdout): chia tập dữ liệu đã cho thành hai tập dữ liệu độc lập: tập
huấn luyện (training set) – chiếm 2/3 dữ liệu – và tập kiểm tra (test set) – chiếm
1/3 dữ liệu. Tập huấn luyện dùng để tạo ra bộ phân lớp, tập kiểm tra dùng để kiểm
tra các bộ phân lớp do Tập huấn luyện tạo ra. Phương pháp này thường áp dụng
với những tập dữ liệu lớn.
- Kiểm tra chéo (k-fold cross validation): chia tập dữ liệu thành k tập con có kích
thước như nhau: S1, S2…Sk. Huấn luyện và kiểm tra được thực hiện k lần. Lấy k-
1 tập con làm tập huấn luyện và một tập con làm tập kiểm tra. Phương pháp này
thường áp dụng với những tập dữ liệu vừa
- Bootstrapping: Phương pháp này thường áp dụng với những tập dữ liệu nhỏ.

b) Gia tăng độ chính xác:
Bagging và Boosting là hai kỹ thuật giúp gia tăng độ chính xác của bộ phân lớp.
Cả hai đều có thể kết hợp một loạt T bộ phân lớp C1, C2… CT để tạo ra một bộ phân lớp
phức hợp, cải tiến C*

Hình 3.2: Kết hợp các bộ phân lớp để cải tiến hiệu quả

16

IV) Phân lớp Bayes (Bayesian Classification)
Phân lớp Bayes là kỹ thuật phân lớp dựa trên xác suất – thống kê (cụ thể là Công

)
(4.1)2) Bộ phân lớp Naïve Bayes
i) Cho m lớp C
1
, C
2
, …, C
m

ii) X là một mẫu dữ liệu cần phân lớp được mô tả bởi tập thuộc tính A
1
, A
2
, …,
A
n
. X = (x
1
, x
2
, …, x
n
). Bộ phân lớp sẽ dựa trên các giá trị của X để xuất ra giá
trị hàm phân lớp f(X) là một trong các C
i
(1 <= i <= m)
iii) Tính giá trị hàm phân lớp f(X):



, 

, … , 

|


)
(

, 

, … , 

)
= max


(


)

(


, 


,x
2
,…,x
n
|C
i
):
Do các thuộc tính là độc lập với nhau nên xác suất để quan sát được X =
(x
1
,x
2
,…,x
n
) trên lớp C
i
là tích các khả năng của từng thuộc tính riêng biệt trên
C
i


(


, 

, … , 

|


i




: số lần xuất hiện của C
i
trong tập học
vi) Như vậy, bộ phân lớp Naïve Bayes có thể áp dụng công thức:
() = max

((

)  





)
f(X) tìm được chính là lớp mà X thuộc về.
Nói cách khác:
() = max


(

|



P
mưa
ấm áp
cao
không
P
mưa
mát
vừa
không
P
mưa
mát
vừa
có
N
u ám
mát
vừa
có
P
nắng
ấm áp
cao
không
N
nắng
mát
vừa
không

Thuộc tính Nhiệt độ – Miền giá trị {Nóng, Mát, Ấm áp}
Thuộc tính Độ ẩm – Miền giá tri {Cao, Vừa}
Thuộc tính Gió – Miền giá trị {Có, Không}
Thuộc tính Lớp – Miền giá trị {P, N} //P: chơi tennis; N: không chơi
tennis
Ta có thể dễ dàng tính ra các giá trị P(xj|Ci) theo bảng xác suất sau:
Thời tiết
P(Nắng|P) = 2/9 P(Nắng|N) = 3/5
P(U ám|P) = 4/9 P(U ám|N) = 0
P(Mưa|P) = 3/9 P(Mưa|N) = 2/5
Nhiệt độ
P(Nóng|P) = 2/9 P(Nóng|N) = 2/5
P(Ấm áp|P) = 4/9 P(Ấm áp|N) = 2/5
P(Mát|P) = 3/9 P(Mát|N) = 1/5
19

Độ ẩm
P(Cao|P) = 3/9 P(Cao|N) = 4/5
P(Vừa|P) = 6/9 P(Vừa|N) = 1/5
Gió
P(Có|P) = 3/9 P(Có|N) = 3/5
P(Không|P) = 6/9

P(Không|N) = 2/5
Bảng 4.2: Các xác suất

Ta cũng có thể tính được P(P) = 9/14 và P(N) = 5/14
Xét mẫu X = (mưa, nóng, cao, không)
 X là một mẫu không có trong tập huấn luyện phải phân lớp cho mẫu X
 Tìm lớp thích hợp bằng công thức:

2.2. For each 

//Với mỗi thuộc tính 

của mẫu ví dụ 


2.3. Do Tính xác suất





5) Giải thuật phân lớp Naïve Bayes:
Input: bảng xác suất (mô hình đã được huấn luyện), mẫu dữ liệu mới x = (

, 

, … , 

)
Output: lớp C mà mẫu dữ liệu x thuộc về.
CLASSIFY_NEW_INSTANCE(x)
1. return max

((

)
∏


Hình 4.1: Một Mạng Bayes đơn giản Bảng 4.3: Bảng phân bố xác suất có điều kiện cho giá trị của biến LungCancer (LC).

Theo mô hình Mạng Bayes ở trên, ta có thể xác định:
 Parents (LungCancer) = FamilyHistory ^ Smoker
 P (LungCancer = Yes | FamilyHistory = Yes , Smoker = Yes) = 0.8
 P (LungCancer = Yes | FamilyHistory = Yes , Smoker = No) = 0.5
 P (LungCancer = Yes | FamilyHistory = No , Smoker = Yes) = 0.7
 P (LungCancer = Yes | FamilyHistory = No , Smoker = No) = 0.1
 P (LungCancer = No | FamilyHistory = Yes , Smoker = Yes) = 0.2
 P (LungCancer = No | FamilyHistory = Yes , Smoker = No) = 0.5
 P (LungCancer = No | FamilyHistory = No , Smoker = Yes) = 0.3
 P (LungCancer = No | FamilyHistory = No , Smoker = No) = 0.9
22

Nếu xét một bộ (z

, z

, … , z

) . Xác suất xảy ra của bộ này trong tập học là:

(


Tập dữ liệu huấn luyện  = {

, 

, … , 

};


là một ô trong bảng phân bố xác suất CPT cho biến 

= 

có cha là


= 

. Ở ví dụ phần trên, nếu 

là ô phía trên bên trái của bảng CPT thì: 

là
LungCancer và 

= Yes là giá trị của nó; 

= {FamilyHistory, Smoker} là danh sách
các node cha của 


bằng tập dữ liệu huấn luyện S


←

+ 
(|)




3: gọi là learning rate, là một hằng số và có giá trị nhỏ. 23

4. Bình thường hóa lại (Renormalize) 


 


= 1
0 ≤

≤ 1

V) Lý thuyết tập thô (Rough Set Theory)
Hầu hết cơ sở dữ liệu sử dụng cho việc Khai thác dữ liệu đều không hoàn thiện về
dữ liệu do nhiễu, các giá trị không xác định hoặc lỗi do các thiết bị đo đạc không chính

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.
Hệ thông tin thường được ký hiệu là cặp (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.
Một hệ thông tin có dạng (U; A⋃{d}), trong đó d∉A là thuộc tính quyết định và A
là các thuộc tính điều kiện, gọi là hệ quyết định.
Bệnh nhân

Đau đầu

Đau cơ

Nhiệt độ Cảm cúm

p1 không có cao có
p2 có không cao có
p3 có có rất cao có
p4 không có bình thường

không
p5 có không cao không
p6 không có rất cao có
Bảng 5.1: Một hệ quyết định trong “chuẩn đoán bệnh Cảm cúm”

Trong Bảng 5.1, U = {p1; p2; p3; p4; p5; p6}, A = {Đau đầu, Đau cơ, Nhiệt độ}
và d = Cảm cúm.

3) Xấp xỉ tập hợp
Trong lý thuyết tập thô, để biểu diễn một tập hợp bằng tri thức được cho xác định
bởi một tập thuộc tính, người ta định nghĩa hai phép xấp xỉ: xấp xỉ dưới (lower
approximation) và xấp xỉ trên (upper approximation).