Bài tiểu luận môn Khai Phá Dữ Liệu PGS.TS Đỗ Phúc
LÔØI CAÛM ÔN
Lời đầu tiên tôi xin chân thành cám ơn thầy PGS.TS Đỗ Phúc đã giảng
dạy cho tôi những kiến thức quan trọng của môn Khai phá dữ liệu và đã
hướng dẫn tôi hoàn thành được đồ án môn học này .
Sau đó tôi chân thành cảm ơn phòng Đào tạo ĐH&SĐH của trường
Đại học CNTT đã tạo điều kiện cho tôi có những thông tin bổ ích, quan trọng
để tôi tham khảo và hoàn thành đồ án này.
Trong quá trình làm đồ án, tôi không thể tránh được những thiếu sót,
mong nhận được những ý kiến đóng góp chân thành và những lời nhận xét
của quý Thầy Cô cùng bạn bè để giúp tôi có thể tiếp tục nghiên cứu sâu hơn,
phát triển và hoàn thiện đề tài này.
HỌC VIÊN THỰC HIỆN

Trần Duy Phong
Trần Duy Phong – CH1101160 Trang 1
Bài tiểu luận môn Khai Phá Dữ Liệu PGS.TS Đỗ Phúc
MỞ ĐẦU
Ngày nay, chúng ta đang sống trong thế kỷ bùng nổ về khoa học công nghệ
mà đặc biệt là sự phát triển vượt bậc về công nghệ tông tin. 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. Bên cạnh đó, các thiết bị thu thập dữ
liệu tự động tương đối phát triển đã tạo ra những kho dữ liệu khổng lồ, như các dữ
liệu ngân hàng, hàng không, giáo dục.…. Cùng với sự phát triển mạnh mẽ của công
nghệ, các thiết bị lưu trữ và các thiết bị thu thập thông tin tự động đã cho phép xây
dựng được những hệ thống thông tin có khả năng tự động hoá ngày càng cao. Vấn
đề đặt ra là làm thế nào để xử lý khối lượng thông tin cực lớn như vậy để phát hiện
ra các tri thức tiềm ẩn trong núi dữ liệu khổng lồ này. Những tri thức thu được như
vậy chúng được chuyên môn hoá, phân chia theo các lĩnh vực ứng dụng như sản
xuất, kinh doanh, tài chính, nghiên cứu… Các cơ sở dữ liệu cần phải đem lại tri

liệu. Lượng thông tin này tuy nhỏ nhưng là những thông tin cốt lõi và cần thiết cho
tiến trinh ra quyết định.
Khai thác dữ liệu – Data Mining (KTDL) là tiến trình khám phá tri thức tiềm
ẩn trong các CSDL. Cụ thể hơn, đó là tiến trình trích lọc, sản sinh ra những tri thức
hoặc các mẫu tiềm ẩn, chưa biết nhưng hữu ích từ các CSDL lớn.
Khai thác dữ liệu là một khái niệm ra đời vào những năm cuối của thập kỷ
80 của thế kỷ trước. Nó bao hàm một loạt các kỹ thuật nhằm phát hiện ra các thông
tin có giá trị tiềm ẩn trong các tập dữ liệu lớn. Thật ra, khai thác dữ liệu liên quan
đến việc phân tích các dữ liệu và sử dụng các kỷ thuật để tìm ra các mẫu hình có
tính chính quy trong tập dữ liệu. Hay nó còn là một quá trình trích xuất thông tin có
mối quan hệ hoặc có mối tương quan nhất định từ một kho dữ liệu lớn nhằm mục
đích dự đoán các xu thế, các hành vi trong tương lai, hoặc tìm kiếm những thông tin
hữu ích mà bình thường không thể nhận diện được.
Trần Duy Phong – CH1101160 Trang 4
Bài tiểu luận môn Khai Phá Dữ Liệu PGS.TS Đỗ Phúc
Ứng dụng của nó rất đa dạng và rộng lớn, từ marketing, chống gian lận, giảm
giá thành sản xuất, tăng doanh thu, phân tích hành vi sử dụng người dùng Internet
để tìm ra nhu cầu, đúng đối tượng hay ứng dụng hỗ trợ ra quyết định, nghiên cứu
khoa học đến việc chống khủng bố …
• Tại sao cần khai phá dữ liệu
Khai phá dữ liệu là cần thiết đối với người dùng vì những lý do sau:
Ngày càng nhiều dữ liệu được lưu trữ trong các CSDL, kho dữ liệu và hình
thành một “mỏ vàng dữ liệu” chứa đầy các thông tin chiến lược mà các hệ quản trị
CSDL thông thường không thể phát hiện và quản trị được chúng
CSDL phát triển nhanh chóng cả về kích thước lẫn số lượng. Không xét những
thông tin mang tính sự kiện được lưu trữ trong CSDL. Những thông tin được suy
diễn từ nó cũng hết sức lý thú. Tuy nhiên với các quan hệ có số lượng khổng lồ các
bản ghi (record) và có quá nhiều trường ghi (field), việc duyệt hàng triệu bản ghi
hay hàng trăm trường ghi để tìm ra các mẫu và các quy luật là một thách thức và trở
ngại thật sự đối với các nhà phân tích dữ liệu

phù hợp với loại khách hàng trong một phân khu thị trượng nhất định
- Công nghệ sinh học và dược phẩm
 Xây dụng công cụ KTDL trực quan cho phép phát hiện sự hiện diện
của dược chất, phân tích dữ liệu truyền đi
- Nhân sự
 Giúp nhà tuyển dingj chọn ứng viên thích hợp nhất theo nhu cầu của
công ty
 Phát hiện giả mạo thẻ trong lĩnh vự viễn thông
 Phát hiện dùng thẻ tín dụng giả trên mạng và là công cụ hữu ích cho
dịch vụ quản lý rủi ro cho thương mại điện tử.
 Phát hiện xâm nhập mạng trái phép
2. Các phương pháp khai phá dữ liệu
Quá trình khai phá dữ liệu là quá trình phát hiện mẫu trong đó giải thuật khai phá
dữ liệu tìm kiếm các mẫu đáng quan tâm theo dạng xác định như các luật, cây phân
lớp, hồi quy, phân nhóm,…
Trần Duy Phong – CH1101160 Trang 6
Nợ >= nNợ < n
Không cho vay
Thu nhập < t Thu nhập >= t
Không cho vay Cho vay
Bài tiểu luận môn Khai Phá Dữ Liệu PGS.TS Đỗ Phúc
a. Phương pháp quy nạp (Induction)
Một cơ sở dữ liệu là một kho thông tin nhưng các thông tin quan trọng hơn cũng có
thể được suy diễn từ kho thông tin đó. Có hai việc chính để thực hiện việc này là
suy diễn và quy nạp.
- Phương pháp suy diễn: Nhằm rút ra thông tin là kết quả logic của các thông
tin trong cơ sở dữ liệu. Ví dụ như toán tử liên kết áp dụng cho hai bảng quan
hệ, bảng đầu chứa thông tin về các nhân viên và các phòng ban, bảng thứ hai
chứa thông tin về các phòng ban và các trưởng phòng. Như vậy sẽ suy ra mối
quan hệ giữa các nhân viên và trưởng phòng. Phương pháp suy diễn dựa trên

chỉ có thể biểu diễn được một số dạng chức năng và vì vậy giới hạn cả về độ chính
xác của mô hình. Cho đến nay, đã có rất nhiều giải thuật suy diên sử dụng các luật
và cây quyết định được áp dụng trong máy học và trong thống kê.
c. Phát hiện các luật kết hợp
Phương pháp này nhằm phát hiện ra các luật kết hợp giữa các thành phần dữ liệu
trong cơ sở dữ liệu. Mẫu đầu ra của giải thuật khai phá dữ liệu là tập luật kết hợp
tìm được. Ta có thể lấy một số ví dụ đơn giản về luật kết hợp như sau: Sự kết hợp
giữa hai thành phần A và B có nghĩa là sự xuất hiện của A trong bản ghi kéo theo
sự xuất hiện của B trong cùng bản ghi đó: A ⇒ B.
Cho một lược đồ R = {A
1
,…A
p
} các thuộc tính với miền giá trị {0,1}, và một
quan hệ r trên R. Một tập luật kết hợp trên r được mô tả dưới dạng X ⇒ B với X ⊆
R và B∈R\X. Về mặt trực giác, ta có thể phát biểu ý nghĩa của luật như sau: nếu
một bản ghi của bảng r có giá trị 1 tại mỗi thuộc tính thuộc X thì giá trị của thuộc
tính B cũng là 1 trong cùng bản ghi đó. Ví dụ như ta có tập cơ sở dữ liệu về các mặt
Trần Duy Phong – CH1101160 Trang 8
Bài tiểu luận môn Khai Phá Dữ Liệu PGS.TS Đỗ Phúc
hàng bán trong siêu thị, các dòng tương ứng với các ngày bán hàng, các cột tương
ứng với các mặt hàng thì giá trị 1 tại ô (20/10, bánh mì) xác định rằng bánh mì đã
được bán ngày hôm đó và cũng kéo theo sự xuất hiện giá trị 1 tại ô (20/10, bơ).
Cho W⊆R, đặt s(W,r) là tần số xuất hiện của W trong r được tính bằng tỷ lệ
của các dòng trong r có giá trị 1 tại mỗi cột thuộc W. Tần số xuất hiện của luật X ⇒
B trong r được định nghĩa là s(X∪{B},r) còn gọi là độ hỗ trợ của luật, độ tin cậy
của luật là s(X∪{B},r)/s(X,r), ở đây X có thể gồm nhiều thuộc tính, B là giá trị
không cố định. Nhờ vậy mà không xảy ra việc tạo ra các luật không mong muốn
trước khi quá trình tìm kiếm bắt đầu. Điều đó cũng cho thấy không gian tìm kiếm
có kích thước tăng theo hàm mũ của số lượng các thuộc tính ở đầu vào. Do vậy cần

các dữ liệu có chung những tính chất nào đó được phân tách từ cơ sở dữ liệu. Khi
các mẫu được thiết lập, chúng có thể được sử dụng để tái tạo các tập dữ liệu ở dạng
dễ hiểu hơn, đồng thời cũng cung cấp các nhóm dữ liệu cho các hoạt động cũng như
công việc phân tích. Đối với cơ sở dữ liệu lớn, việc lấy ra các nhóm này là rất quan
trọng.
e. Mạng neuron
Mạng neuron là một tiếp cận tính toán mới liên quan đến việc phát triển các cấu
trúc toán học với khả năng lọc. Các phương pháp là kết quả của việc nghiên cứu mô
hình học của hệ thống thần kinh con người. Mạng neuron có thể đưa ra ý nghĩa từ
các dữ liệu phức tạp hoặc không chính xác và có thể được sử dụng để chiết xuất các
mẫu và phát hiện ra các xu hướng quá phức tạp mà con người cũng như các kỹ
thuật máy tính khác không thể phát hiện được.
Khi đề cập đến khai thác dữ liệu, người ta thường đề cập nhiều đến mạng neuron.
Tuy mạng neuron có một số hạn chế gây khó khăn trong việc áp dụng và triển khai
nhưng nó cũng có những ưu điểm đáng kể. Một trong số những ưu điểm phải kể đến
của mạng neuron là khả năng tạo ra các mô hình dự đoán có độ chính xác cao, có
thể áp dụng được cho rất nhiều loại bài toán khác nhau đáp ứng được các nhiệm vụ
đặt ra của khai phá dữ liệu như phân lớp, phân nhóm, mô hình hoá, dự báo các sự
kiện phụ thuộc vào thời gian,…
Đặc điểm của mạng neuron là không cần gia công dữ liệu nhiều trước khi bắt đầu
quá trình học như các phương pháp khác. Tuy nhiên, để có thể sử dụng mạng
neuron có hiệu quả cần phải xác định các yếu tố khi thiết kế mạng như:
- Mô hình mạng là gì?
- Mạng cần có bao nhiêu nút?
Trần Duy Phong – CH1101160 Trang 10
Bài tiểu luận môn Khai Phá Dữ Liệu PGS.TS Đỗ Phúc
- Khi nào thì việc học dừng để tránh bị “học quá”?
- …
Ngoài ra còn có rất nhiều bước quan trọng cần phải làm để tiền xử lý dữ liệu trước
khi đưa vào mạng neuron để mạng có thể hiểu được (ví dụ như việc chuẩn hoá dữ

“natural clusters”, “useful” clusters, outlier detection
Kỹ thuật phân cụm có thể áp dụng trong rất nhiều lĩnh vực như:
• Marketing: Xác định các nhóm khách hàng (khách hàng tiềm năng, khách
hàng giá trị, phân loại và dự đoán hành vi khách hàng,…) sử dụng sản phẩm
hay dịch vụ của công ty để giúp công ty có chiến lược kinh doanh hiệu quả
hơn;
• Biology: Phận nhóm động vật và thực vật dựa vào các thuộc tính của chúng;
• Libraries: Theo dõi độc giả, sách, dự đoán nhu cầu của độc giả…;
• Insurance, Finance: Phân nhóm các đối tượng sử dụng bảo hiểm và các dịch
vụ tài chính, dự đoán xu hướng (trend) của khách hàng, phát hiện gian lận tài
chính (identifying frauds);
• WWW: Phân loại tài liệu (document classification); phân loại người dùng
web (clustering weblog);
Trần Duy Phong – CH1101160 Trang 12
Bài tiểu luận môn Khai Phá Dữ Liệu PGS.TS Đỗ Phúc
Các kỹ thuật phân cụm được phân loại như sau (xem hình)
Trần Duy Phong – CH1101160 Trang 13
Mode
Seeking
Misture
Resolving
Graph
Theoretic
Expectation
Maximization
K-Means
Square
Error
Partitional
Hierachical

6
7
8
9
10
0 1 2 3 4 5 6 7 8 9 10
0
1
2
3
4
5
6
7
8
9
10
0 1 2 3 4 5 6 7 8 9 10
0
1
2
3
4
5
6
7
8
9
10
0 1 2 3 4 5 6 7 8 9 10

X1={1,3}
X2={1.5 , 3.2}
X3= {1.3 , 2.8}
X4= {3 , 1}
Dùng k-means để gom cụm với k=2
Bước 1: Khởi tạo ma trận phân hoạch U có bốn cột ứng với bốn điểm và hai dòng ứng với
hai cụm
Bước 2: U=(m
ij
), 1 =< I =< 2 và 1 =< j =< 4
Cho n=0 (số lần lặp), tạo U0
X1 X2 X3 X4
U0= C1 1 0 0 0
C2 0 1 1 1
Bước 3: Tính vector trọng tâm
Do có 2 cụm C1,C2 nên có 2 vecto trọng tâm v1,v2
Các vecto trọng tâm:
Với vector v1 cho cụm 1:
Vậy v1 = (1,3)
Với vector v2 cho cụm 2:
Vậy v2 = (1.93 , 2.33)
Gom các đối tượng vào cụm
Tính khoảng cách Euclide từ từng điểm đến cụm c1, c2 chọn cụm có khoảng cách gần nhất
để đưa đối tượng vào cụm
Trần Duy Phong – CH1101160 Trang 16
Bài tiểu luận môn Khai Phá Dữ Liệu PGS.TS Đỗ Phúc
Gom v1 vào cùm c1 vì d(x1,v1) < d(x1,v2)
Tính toán tương tự ta có
d(x2,v1) = 0.54 < d(x2,v2) = 0.97 xếp v2 vào cụm c1
d(x3,v1) = 0.36 < d(x3,v2) = 0.78 xếp x3 vào cụm c1

 Bước 2:
78
$./!"#9'*
-2./"" 01(
8'0)2* :!"6;'7*
!"6
-2./"" 01(
<8'0)2* 1"
8')2* 0
=&/"
8')2* 
=<
!"6
/%."'>?@A
B>*
/%.""'*
-./"" 01
-2./"" 01(
/%."'8')2**
/%."'>>*
!"6
/%.""'*
!"6
 Bước 3:
C1D"EDFG"
"E@&H
$
1D"I
$4./$%&"')* !"#$%&"')*+,
JKH?"

U'P*15'>0>*U>&>*
/%."'>4>U'P
*15'>0>*U>'>U4')0*U>)>U4')*U
>*>*
/%.""'*
!"6
/%.""'*
Trần Duy Phong – CH1101160 Trang 20
Bài tiểu luận môn Khai Phá Dữ Liệu PGS.TS Đỗ Phúc
'8/)8*
1DFGVWXV
TI&H@
LHSVY
/%."'>1DFGV
X"IW@>*
/%.""'*
-2./"" 01(
 
?9'?5Z'''2)0*(4'0)0**O
''2)0*(4'0)0**P''2)*(
4'0)**O''2)*(4'0)***)C*
7 
?9'?5Z'''2)0*(4')0**O
''2)0*(4')0**P''2)*(
4')**O''2)*(4')***)C*
/%."'>J"6>U'2
P*15'>0>*U>"@)@7[&\&
>UU>>U7*
/%.""'*
5/FG@

Song do thời gian bị hạn chế nên em chưa thể ứng kỹ thuật gom cụm bằng thuật
toán K-Means để ứng dụng trong thực tế. Kính mong Thầy góp ý cho bài viết của
em được hoàn thiện hơn.
Em xin chân thành cảm sự giảng dạy và hướng dẫn của Thầy trong suốt thời gian
qua.
Trần Duy Phong – CH1101160 Trang 24
Bài tiểu luận môn Khai Phá Dữ Liệu PGS.TS Đỗ Phúc
TÀI LIỆU THAM KHẢO
[1] PGS.TS Đỗ Phúc, Giáo trình Khai Thác Dữ Liệu, Đại học quốc gia TP Hồ Chí
Minh, 2006
[2] PGS.TS Đỗ Phúc, Slide bài giảng - Bai_5_GomCum, Đại học Công Nghệ
Thông Tin, 2012
[3] />%205%20-%20Clustering%20-%20Part%201.pdf
Trần Duy Phong – CH1101160 Trang 25