ĐẠ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 KHAI PHÁ DỮ LIỆU & KHO DỮ
LIỆU
Đề tài: Tìm hiểu clustering trong data mining và ứng
dụng K-mean trong xử lý ảnh
Giảng viên hướng dẫn: PGS.TS Đỗ Phúc
Học viên thực hiện: Trịnh Thị Trúc Chi
MSHV: CH1101006
Lớp: CH6

MÔN HỌC: KHAI PHÁ DỮ LIỆU & KHO DỮ LIỆU

Mục lục
I. Giới thiệu 3
I.1. Giới thiệu “Data mining”: 3
I.2. Các phương pháp khai phá dữ liệu: 4
I.2.1. Phân loại (classification): 4
I.2.2. Hồi quy (regression): 4
I.2.3. Gom nhóm (clustering): 4
I.2.4. Tổng hợp (summarization): 4
I.2.5. Mô hình ràng buộc (dependency modeling): 5
I.2.6. Dò tìm biến đổi và độ lệch (change and deviation dectection): 5
I.3. Các ứng dụng của khai phá dữ liệu: 5
I.4. Các bước của quá trình khai phá dữ liệu: 6
II. Bài toán gom nhóm dữ liệu (clustering) 7
II.1. Giới thiệu: 7
II.2. Mục đích gom nhóm: 8
II.2.1. Một số phương pháp gom nhóm điển hình 8
II.3. Phát biểu thuật toán K-mean: 9
II.3.1. Phát biểu bài toán: 9
II.3.2. Khái quát về thuật toán: 9
II.3.3. Các bước của thuật toán: 10
II.3.4. Ví dụ minh họa 11
II.3.5. Đánh giá thuật toán 15
2
ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐÀO TẠO THẠC SĨ CNTT QUA MẠNG

MÔN HỌC: KHAI PHÁ DỮ LIỆU & KHO DỮ LIỆU

- Xác định vấn đề và không gian dữ liệu để giải quyết vấn đề (Problem
understanding and data understanding).
- Chuẩn bị dữ liệu (Data preparation), bao gồm các quá trình làm sạch dữ liệu (data
cleaning), tích hợp dữ liệu (data integration), chọn dữ liệu (data selection), biến
đổi dữ liệu (data transformation).
- Khai thác dữ liệu (Data mining): xác định nhiệm vụ khai phá dữ liệu và lựa chọn
kỹ thuật khai phá dữ liệu. Kết quả cho ta một nguồn tri thức thô.
- Đánh giá (Evaluation): dựa trên một số tiêu chí tiến hành kiểm tra và lọc nguồn tri
thức thu được.
- Triển khai (Deployment).
Quá trình khai thác tri thức không chỉ là một quá trình tuần tự từ bước đầu tiên đến bước
cuối cùng mà là một quá trình lặp và có quay trở lại các bước đã qua.

4
ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐÀO TẠO THẠC SĨ CNTT QUA MẠNG

MÔN HỌC: KHAI PHÁ DỮ LIỆU & KHO DỮ LIỆU

I.2. Các phương pháp khai phá dữ liệu:
I.2.1. Phân loại (classification):
Là việc xác định một hàm ánh xạ từ một mẫu dữ liệu vào một trong số các lớp đã được
biết trước đó. Mục tiêu của thuật toán phân lớp là tìm ra mối quan hệ nào đó giữa thuộc
tính dự báo và thuộc tính phân lớp. Như thế quá trình phân lớp có thể sử dụng mối quan
hệ này để dự báo cho các mục mới.
I.2.2. Hồi quy (regression):
Là việc học một hàm ánh xạ từ một mẫu dữ liệu thành một biến dự đoán có giá trị thực.
Nhiệm vụ của hồi quy tương tự như phân lớp, điểm khác nhau chính là ở chỗ thuộc tính
để dự báo là liên tục chứ không phải rời rạc. Việc dự báo các giá trị số thường được làm
bởi các phương pháp thống kê cổ điển, chẳng hạn như hồi quy tuyến tính. Tuy nhiên,

biết trước hoặc giá trị chuẩn, phát hiện độ lệch đáng kể giữa nội dung của tập con dữ liệu
thực và nội dung mong đợi.
Hai mô hình độ lệch hay dùng là lệch theo thời gian hay lệch theo nhóm. Độ lệch theo
thời gian là sự thay đổi có ý nghĩa của dữ liệu theo thời gian. Độ lệch theo nhóm là sự
khác nhau của giữa dữ liệu trong hai tập con dữ liệu.
I.3. Các ứng dụng của khai phá dữ liệu:
Phát hiện tri thức và khai phá dữ liệu liên quan đến nhiều ngành, nhiều lĩnh vực: thống
kê, trí tuệ nhân tạo, cơ sở dữ liệu, thuật toán, tính toán song song và tốc độ cao, thu thập
tri thức cho các hệ chuyên gia, quan sát dữ liệu Đặc biệt phát hiện tri thức và khai phá
dữ liệu rất gần gũi với lĩnh vực thống kê, sử dụng các phương pháp thống kê để mô hình
dữ liệu và phát hiện các mẫu, luật Ngân hàng dữ liệu (Data Warehousing) và các công
cụ phân tích trực tuyến (OLAP- On Line Analytical Processing) cũng liên quan rất chặt
chẽ với phát hiện tri thức và khai phá dữ liệu.
Các ứng dụng của khai phá dữ liệu trong thực tế:
- Bảo hiểm, tài chính và thị trường chứng khoán: phân tích tình hình tài chính và dự
báo giá của các loại cổ phiếu trong thị trường chứng khoán. Danh mục vốn và giá,
lãi suất, dữ liệu thẻ tín dụng, phát hiện gian lận,
6
ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐÀO TẠO THẠC SĨ CNTT QUA MẠNG

MÔN HỌC: KHAI PHÁ DỮ LIỆU & KHO DỮ LIỆU

- Thống kê, phân tích dữ liệu và hỗ trợ ra quyết định.
- Điều trị y học và chăm sóc y tế: một số thông tin về chuẩn đoán bệnh lưu trong các
hệ thống quản lý bệnh viện. Phân tích mối liên hệ giữa các triệu chứng bệnh,
chuẩn đoán và phương pháp điều trị (chế độ dinh dưỡng, thuốc, )
- Sản xuất và chế biến: Quy trình, phương pháp chế biến và xử lý sự cố.
- Text mining và Web mining: Phân lớp văn bản và các trang Web, tóm tắt văn
bản,

- Các đối tượng khác nhóm thì không tương tự nhau
Gom nhóm dữ liệu giúp giải quyết vấn đề tìm kiếm, phát hiện các cụm, các mẫu dữ liệu
trong một tập hợp ban đầu các dữ liệu không có nhãn.

Hình 1: Mô hình gom nhóm dữ liệu
Với:
 X : 1 tập các điểm dữ liệu
 

: cụm thứ i


 

 








8
ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐÀO TẠO THẠC SĨ CNTT QUA MẠNG

MÔN HỌC: KHAI PHÁ DỮ LIỆU & KHO DỮ LIỆU

Một số độ đo trong gom nhóm:

- Euclidean















- Độ đo tương tự (gần nhau): cosin 2 vector










II.2. Mục đích gom nhóm:
Xác định được bản chất của việc nhóm các đối tượng trong một tập dữ liệu không có
nhãn. Gom nhóm không dựa trên một tiêu chuẩn chung nào, mà dựa vào tiêu chí mà












Số nhóm: K
Đầu ra: Các nhóm 



  

tách rời và hàm tiêu chuẩn E đạt giá trị tối thiểu.
II.3.2. Khái quát về thuật toán:
Thuật toán hoạt động trên 1 tập vector d chiều, tập dữ liệu X gồm N phần tử








K-mean lập lại nhiều lần quá trình:


Hàm trên không âm, giảm khi có 1 sự thay đổi 1 trong 2 bước: gán dữ liệu và định lại vị
trí tâm.
II.3.3. Các bước của thuật toán:
Bước 1: khởi tạo, chọn K trọng tâm






  


Bước 2: tính toán khoảng cách:


















Bước 4: điều kiện dừng là lặp lại bước 2 và 3 cho đến khi không có sự thay đổi trong tâm
của nhóm

11
ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐÀO TẠO THẠC SĨ CNTT QUA MẠNG

MÔN HỌC: KHAI PHÁ DỮ LIỆU & KHO DỮ LIỆU s

II.3.4. Ví dụ minh họa
Đối tượng
Thuộc tính 1 (X)
Thuộc tính 2 (Y)

MÔN HỌC: KHAI PHÁ DỮ LIỆU & KHO DỮ LIỆU Hình 2: Dữ liệu đầu vào K-mean
Bước 1: khởi tạo
Chọn 2 trọng tâm ban đầu 

(1,1)  và 

(2,1) , thuộc 2 nhóm 1 và 2

Hình 3: Chọn A(1, 1) và B(2, 1) làm trọng tâm
Bước 2: tính toán khoảng cách







  




  



13


 C thuộc nhóm 2







  




  










  















Hình 4: Cập nhật lại centroid c1(1, 1) và c2(11/3, 8/3)
Bước 4-1: lặp lại bước 2 – Tính toán khoảng cách










  A thuộc nhóm 1









  D thuộc nhóm 2

Bước 4-2: lặp lại bước 3 - Cập nhật trọng tâm






 







 


Hình 5: Cập nhật lại centroid c1(3/2, 1) và c2(9/2, 7/2)
Bước 4-3: lặp lại bước 2














  D thuộc nhóm 2
15
ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐÀO TẠO THẠC SĨ CNTT QUA MẠNG

MÔN HỌC: KHAI PHÁ DỮ LIỆU & KHO DỮ LIỆU Hình 6: Kết quả sau khi phân nhóm
II.3.5. Đánh giá thuật toán
Ưu điểm:
- Độ phức tạp: O(K.N.L) với L là số lần lặp
- Có khả năng mở rộng, có thể dễ dàng sửa đổi với những dữ liệu mới.
- Bảo đảm hội tụ sau một số lần lặp hữu hạn.
- Luôn có K cụm dữ liệu.
- Luôn có ít nhất 1 điểm dữ liệu trong một nhóm dữ liệu
- Các nhóm không phân cấp và không bị chồng chéo dữ liệu lên nhau.
- Các thành viên của 1 nhóm là gần với chính nhóm đó hơn bất cứ 1 nhóm nào
khác.
Nhược điểm:
- Không có khả năng tìm ra các nhóm không lồi hoặc các nhóm có hình dạng phức

- Tài chính, bảo hiểm: gom nhóm các đối tượng sử dụng bảo hiểm và tài chính, dự
đoán xu hướng của khách hàng, phát hiện gian lận tài chính.
- Gom nhóm tài liệu web
o Tìm kiếm và trích rút dữ liệu
o Tiền xử lý tài liệu: quá trình tách từ và vector hóa tài liệu
o Áp dụng K-mean
- Phân vùng ảnh
17
ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐÀO TẠO THẠC SĨ CNTT QUA MẠNG

MÔN HỌC: KHAI PHÁ DỮ LIỆU & KHO DỮ LIỆU

III. Ứng dụng
III.1. Demo giải bài toán K-mean:
Nhập số điểm và số cụm, chọn tọa độ trọng tâm từ các điểm cho trước ban đầu,
chọn “Bắt đầu” và “Bước tiếp theo” để chạy và xem kết quả bài toán.

18
ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐÀO TẠO THẠC SĨ CNTT QUA MẠNG

MÔN HỌC: KHAI PHÁ DỮ LIỆU & KHO DỮ LIỆU









 




Các thuật toán được sử dụng phổ biến là population algorithm, median cut - Paul
Heckbert hoặc clustering sử dụng octrees.
Trong phạm vi đề tài, bài toán được giải quyết bằng cách sử dụng giải thuật clustering cơ
bản nhất là K-mean.
III.3. Thực hiện
Bước 1: Duyệt ảnh, tìm các màu được sử dụng trong ảnh. Số màu được sử dụng cũng
chính là số samples dùng cho clustering.
Ví dụ dữ liệu đầu vào: Các màu được tìm thấy:
Màu
Mã màu
Blue
0000FF
Red
FF0000
white

Màu
Mã màu
centroid
black
000000
111166
grey
333333
Blue
0000FF
Red
FF0000
AAAAFF
Green
00FF00
Yellow
FFFF00
Aqua
00FFFF
AAAA00
Pink
FF00FF
white
FFFFFF
Bảng 2: Danh sách samples sau khi sắp xếp và k-centroid đầu tiên
Ba màu được chọn làm centroid là 111166, AAAAFF và AAAA00
Bước 2.2:
Hiệu chỉnh các centroid theo thuật toán k-mean
Trong ví dụ trên, kết quả qua các vòng lặp:
Iteration 1:

Yellow
FFFF00
120.21
AAAA00
Aqua
00FFFF
190.07
AAAAFF
Pink
FF00FF
120.21
AAAAFF
white
FFFFFF
120.21
AAAAFF

Iteration 2:
Màu
Mã màu
Distance
Nhóm
black
000000
104.8
111166
grey
333333
70.09
111166

Thay đổi màu hình gốc bằng cách thay thế các giá trị màu gốc bởi giá trị màu trung bình
của nóm mà màu gốc thuộc về. III.4. Kết quả demo
Input: ảnh
22
ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐÀO TẠO THẠC SĨ CNTT QUA MẠNG

MÔN HỌC: KHAI PHÁ DỮ LIỆU & KHO DỮ LIỆU

Số samples: 10881

Origin 24 bit depth
16 colors
Thời gian: 7.32s
64 colors
Thời gian: 31.19 s
128 colors
Thời gian: 268 s
Hạn chế của thuật giải k-mean là thời gian thực thi quá lớn khi số samples và k lớn.
III.5. Thực hiện demo
Yêu cầu:
 Python 2.7:
 PIL 1.1.7:
Demo gồm 2 file img_op.py và pycmd.py, đặt cùng thư mục