ĐẠ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 CÔNG NGHỆ TRI THỨC VÀ
ỨNG DỤNG
Đề 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: GS.TSKH Hoàng Văn Kiếm
Học viên thực hiện: Trịnh Thị Trúc Chi
MSHV: CH1101006
Lớp: CH6

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 mỏ 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 mỏ dữ liệu: 5
I.4. Các bước của quá trình khai mỏ 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: CÔNG NGHỆ TRI THỨC VÀ ỨNG DỤNG

II.3.6. Các biến thể 16

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 mỏ dữ liệu và lựa chọn kỹ
thuật khai mỏ 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: CÔNG NGHỆ TRI THỨC VÀ ỨNG DỤNG

I.2. Các phương pháp khai mỏ 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,
phương pháp mô hình hoá cũng được sử dụng, ví dụ: cây quyết định.
I.2.3. Gom nhóm (clustering):
Là việc mô tả chung để tìm ra các tập hay các nhóm, loại mô tả dữ liệu. Các nhóm có thể

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 mỏ dữ liệu:
Phát hiện tri thức và khai mỏ 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 mỏ 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 mỏ dữ liệu.
Các ứng dụng của khai mỏ 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: CÔNG NGHỆ TRI THỨC VÀ ỨNG DỤNG

- 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,
- Lĩnh vực khoa học: Quan sát thiên văn, dữ liệu gene, dữ liệu sinh vật học, tìm
kiếm, so sánh các hệ gene và thông tin di truyền, mối liên hệ gene và một số bệnh
di truyề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: CÔNG NGHỆ TRI THỨC VÀ ỨNG DỤNG

Một số độ đo trong gom nhóm:
- Minkowski
















- Độ đ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à
người dùng cung cấp trong từng trường hợp.
II.2.1. Một số phương pháp gom nhóm điển hình
- Gom nhóm phân hoạch

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

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:
- Gán dữ liệu
10
ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH

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:



















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: CÔNG NGHỆ TRI THỨC VÀ ỨNG DỤNG s

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

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
ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐÀO TẠO THẠC SĨ CNTT QUA MẠNG








  




  










  




  










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











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: CÔNG NGHỆ TRI THỨC VÀ ỨNG DỤNG 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ạp.
- Thời gian thực thi lớn khi K, N lớn
- Khó khăn trong việc xác định trọng tâm ban đầu:

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: CÔNG NGHỆ TRI THỨC VÀ ỨNG DỤNG

III. Ứng dụng
III.1. Giới thiệu
Ý tưởng ứng dụng thuật toán K-mean phân đoạn ảnh để giảm không gian màu (color
quantization)
Ý nghĩa thực tế, trong nhiều trường hợp thực tế, để giảm không gian lưu trữ ảnh, giải
pháp thường được áp dụng là chuyển các ảnh 24-bits vào về ảnh index color (256, 128,
64, 32, 16, 8, 4, 2). Thường thấy nhất là trong các ứng dụng mobile vốn dĩ có bộ nhớ nhỏ,
băng thông nhỏ và dung lượng giới hạn.
Bài toán được giải quyết thông thường bằng các giải thuật 3D-clustering (dựa trên
khoảng cách Euclidean ba kênh màu red, green, blue)





 





0000FF
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: CÔNG NGHỆ TRI THỨC VÀ ỨNG DỤNG

Red
FF0000
white
FFFFFF
black
000000
Green
00FF00
Yellow
FFFF00
Pink
FF00FF
Aqua
00FFFF
grey
333333
Bảng 1: Danh sách các màu samples
Bước 2: Áp dụng thuật toán K-mean, phân nhóm các samples ở bước 1. Số nhóm tương
ứng với số màu mong muốn có được (256, 128, 64, …)
Bước 2.1:
Chọn k phần tử centroid ngẫu nhiên đầu tiên. Việc chọn ngẫu nhiên này làm cho tốc độ
hội tụ bài toán không ổn định. Thay vào đó, k-centroid đầu tiên sẽ được chọn như sau:
- Sắp xếp không gian màu theo thứ tự tăng dần, tính theo khoảng cách từ màu

MÔN HỌC: CÔNG NGHỆ TRI THỨC VÀ ỨNG DỤNG

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:
Màu
Mã màu
Distance
Nhóm
black
000000
104.8
111166
grey
333333
70.09
111166
Blue
0000FF
154.88
111166
Red
FF0000
190.07
AAAA00

grey
333333
70.09
111166
Blue
0000FF
154.88
111166
Red
FF0000
190.07
AAAA00
Green
00FF00
190.07
AAAA00
Yellow
FFFF00
120.21
AAAA00
Aqua
00FFFF
190.07
AAAAFF
20
ĐẠ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: CÔNG NGHỆ TRI THỨC VÀ ỨNG DỤNG


Yêu cầu:
 Python 2.7:
 PIL 1.1.7:
21
ĐẠ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: CÔNG NGHỆ TRI THỨC VÀ ỨNG DỤNG

Demo gồm 2 file img_op.py và pycmd.py, đặt cùng thư mục
Thực thi:
>python img_op.py <image> <k>
 <image> file hình sử dụng
 <k>: số màu output

E:\demo>python img_op.py Rosa_Gold_Glow_2_small_noblue.png
64
Processing K-means
+ samples: 10881
+ K: 64
Finalize
Elapsed 30.75 sec.
[Done] Tài liệu tham khảo
1. Bài giảng môn học “Công nghệ tri thức và ứng dụng” .
Giảng viên : GS.TSKH Hoàng Văn Kiếm
Chương trình đào tạo thac sĩ CNTT qua mạng.
Trung tâm phát triển CNTT ĐH Quốc gia TP.HCM - 2005.