Lưu Tuấn Lâm

Thuật toán Phân cụm dữ liệu nửa giám sát

LỜI CẢM ƠN
Em xin gửi lời cảm ơn chân thành và sâu sắc đến cô giáo ThS.Nguyễn Thị Xuân
Hương , người đã tận tình hướng dẫn và tạo mọi điều kiện cho em trong quá trình làm tốt
nghiệp.
Em xin chân thành cảm ơn các thầy cô giáo trong khoa Công Nghệ Thông Tin
Trường Đại Học Dân Lập Hải Phòng đã quan tâm dạy dỗ và giúp đỡ em trong suốt bốn
năm học vừa qua và trong quá trình làm tốt nghiệp.
Em xin trân trọng cảm ơn thầy Trần Hữu Nghị - Hiệu trưởng trường Đại Học
Dân Lập Hải Phòng đã ủng hộ, động viên, và tạo mọi điều kiện tốt nhất để em có thể
hoàn thành khoá học tại trường.
Cuối cùng em xin gửi lời cảm ơn tới tất cả người thân cùng bạn bè đã động viên,
giúp đỡ và đóng góp nhiều ý kiến quý báu cho em trong quá trình học tập cũng như khi
làm tốt nghiệp.

Hải Phòng, tháng7 năm 2007
Sinh viên

Lưu Tuấn Lâm

Trang 1


Lưu Tuấn Lâm

Thuật toán Phân cụm dữ liệu nửa giám sát

GIỚI THIỆU

sát.
Trong những năm trở lại đây, do phương pháp phân cụm dữ liệu không giám sát
còn nhiều nhược điểm vì vậy dựa trên học không giám sát và học có giám sát đã ra đời
một phương pháp phân cụm dữ liệu mới đó là phương pháp phân cụm dữ liệu nửa giám
Trang 2


Lưu Tuấn Lâm

Thuật toán Phân cụm dữ liệu nửa giám sát

sát. Phương pháp phân cụm nửa giám sát không phải là một phương pháp phân cụm hoàn
thiện nhưng nó đã phần nào khắc phục được những hạn chế và phát huy ưu điểm của
phương pháp phân cụm không giám sát.
Do những ưu điểm, tầm quan trọng cũng như xu hướng phát triển của khám phá
tri thức trong Cơ sở dữ liệu(Knowlegde Discovery in Databases – KDD). Và đây còn là
một lĩnh vực mới lạ đồi với em, vì vậy em đã chọn đề tài Phân cụm dữ liệu nửa giám sát
làm đề tài tốt nghiệp của mình. Em mong muốn có thể học hỏi và tìm hiểu sâu hơn về kỹ
thuật khai phá dữ liệu, từ đó tạo cho bản thân những kiến thức cơ bản để sau này có thể
đi sâu nghiên cứu và tìm hiểu về lĩnh vực KDD.
Nội dung bài đồ án tốt nghiệp ngoài phần giới thiệu, kết luận, và tìa liệu than khảo
gồm có 5 chương :
Chương 1 : Giới thiệu tổng quan về Datamining
Chương 2 : Giời thiệu về phân cụm dữ liệu và các kỹ thuật tiếp cận trong phân cụm
dữ liệu.
Chương 3 : Trình bày về một số phương pháp và thuật toán Phân cụm dữ liệu không
giám sát
Chương 4 : Trình bày một số thuật toán phân cụm dữ liệu nửa giám sát
Chương 5 : Bài toán ứng dụng


2.3.3 Phân cụm dữ liệu dựa trên mật độ...................................................................11
2.3.4

Phân cụm dữ liệu dựa trên lưới.......................................................................11

2.3.5

Phân cụm dữ liệu dựa trên mô hình................................................................11

2.3.6 Phân cụm dữ liệu có ràng buộc.......................................................................11
Chương 3 : PHÂN CỤM DỮ LIỆU KHÔNG GIÁM SÁT.......................................12
3.1

Phương pháp phân hoạch................................................................................12

3.1.1

Thuật toán K-Means .......................................................................................12

3.1.2 Thuật toán K-Prototypes..................................................................................13
3.1.3 Thuật toán k-tâm...............................................................................................14
Chương 4 : PHÂN CỤM DỮ LIỆU NỬA GIÁM SÁT..............................................17
4.1

Thuật toán Seeded-KMeans............................................................................17

4.2

Thuật toán Constrained-KMeans ...................................................................18


vừa khám phá trong công đoạn trước được biểu diễn dưới các dạng trực quan
đồng thời được đánh giá theo những tiêu chí nhất định.

Dữ liệu thô

Tri thức

Trích chọn
dữ liệu

Đánh giá và
biểu diễn

Dữ liệu

Mẫu

Tiền xử lý
dữ liệu

Dữ liệu
tiền xử lý

Biến đổi dữ
liệu

Hình 1: Quá trình khám phá tri thức trong CSDL
Trang 5

Data mining

2.1 Khái quát về phân cụm dữ liệu
Phân cụm dữ liệu là một kỹ thuật trong Data mining nhằm tìm kiếm, phát hiện
các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn và quan trọng trong tập dữ liệu lớn để từ đó
cung cấp thông tin, tri thức cho việc ra quyết định.
Các bước của một bài toán phân cụm dữ liệu gồm:
• Xây dựng hàm tính độ tương tự
• Xây dựng các tiêu chuẩn phân cụm
• Xây dựng mô hình cho cấu trúc dữ liệu
• Xây dựng thuật toán phân cụm và xác lập các điều kiện khởi tạo
• Xây dựng các thủ tục biểu diễn và đánh giá kết quả phân cụm

2.2 Các kiểu dữ liệu và độ đo tương tự
• Kiểu thuộc tính nhị phân:
Thuộc tính nhị phân chỉ có hai giá trị là 0 va 1. Trong đó 0 có nghĩa là
sai và 1 có nghĩa là đúng

Trang 7


Lưu Tuấn Lâm

Thuật toán Phân cụm dữ liệu nửa giám sát
y:1

y:0

x: 1

α


2. Hệ số Jacard: d ( x, y ) =

α
, công thức này được áp dụng
α +γ +δ

trong trường hợp mà trọng số của các thuộc tính có giá trị 1 lớn
hơn rất nhiều các thuộc tính có giá trị 0, như vậy các thuộc tính
nhị phân ở đây không đối xứng.

Trang 8


Lưu Tuấn Lâm

Thuật toán Phân cụm dữ liệu nửa giám sát

• Kiểu thuộc tính khoảng (Interval)
Dùng để đo các giá trị theo xấp xỉ tuyến tính. Độ đo phi tương tự của x
và y được tính bằng các metric khoảng cách sau
n

1/ q
*
1. Khoảng cách Minkowski: d ( x, y ) = (∑ xi − yi ) , q ∈ N
q

i =1

n

ta cần làm cho rif thuộc khoảng [0.0,1.0] để mỗi thuộc tính đều có cùng
r −1

if
trọng số. Do đó rif được thay thế bởi zif = M − 1
f

Trang 9


Lưu Tuấn Lâm

Thuật toán Phân cụm dữ liệu nửa giám sát

3. Cuối cùng ta sử dụng công thức tính độ phi tương tự của thuộc tính
khoảng với zif đại diện cho giá trị thuộc tính f của đối tượng thứ i
• Kiểu thuộc tính tỷ lệ (Ratio)
Đây là thuộc tính khoảng nhưng được xác định một cách tương đối so
với điểm mốc
Có nhiều cách để tính độ tương tự giữa các thuộc tính tỉ lệ. Một
trong số đó là việc sử dụng công thức tính logarit để chuyển mỗi thuộc tính
tỉ lệ xi về dạng thuộc tính khoảng ψi = log(xi).

2.3 Những kỹ thuật tiếp cận trong phân cụm dữ liệu
Các kỹ phân cụm dữ liệu có thể phân loại theo các cách tiếp cận chính sau :
2.3.1 Phân cụm phân hoạch
Phương pháp phân cụm phân hoạch nhằm phân một tập dữ liệu có n phần tử cho
trước thành k nhóm dữ liệu sao cho : mỗi phần tử dữ liệu chỉ thuộc về một nhóm dữ liệu
và mỗi nhóm dữ liệu có tối thiểu ít nhất một phần tử dữ liệu. Các thuật toán phân hoạch
dữ liệu có độ phức tạp rất lớn khi xác định nghiệm tối ưu toàn cục cho vấn đề PCDL.

phân hoạch hoặc chiến lược phân cụm phân cấp, dựa trên cấu trúc hoặc mô hình mà
chúng giả định về tập dữ liệu và cách mà chúng tinh chỉnh các mô hình này để nhận dạng
ra các phân hoạch.
2.3.6 Phân cụm dữ liệu có ràng buộc
Sự phát triển của phân cụm dữ liệu không gian trên CSDL lớn đã cung cấp nhiều công cụ
tiện lợi cho việc phân tích thông tin địa lý, tuy nhiên hầu hết các thuật toán này cung cấp
rất ít cách thức cho người dùng để xác định các ràng buộc trong thế giới thực cần phải
được thoả mãn trong quá trình PCDL.

Trang 11


Lưu Tuấn Lâm

Thuật toán Phân cụm dữ liệu nửa giám sát

Chương 3 : PHÂN CỤM DỮ LIỆU KHÔNG GIÁM SÁT
3.1 Phương pháp phân hoạch
3.1.1 Thuật toán K-Means
K-Means lặp lại nhiều lần quá trình bố trí lại vị trí của đối tượng dữ liệu để phân
hoạch một tập dữ liệu thành K cụm và cực tiểu địa phương giá trị bình phương trung
Thuật toán: K-Means.
bình khoảng cách giữa các các đối tượng tới tâm cụm của nó. Cụ thể hơn, với tập dữ liệu
X = { x1 ,...,hoạch
xN } , xi{ ∈
X = { xi } i =1Input:
Xℜ
, xi ∈ℜ-d Tập
thuật
h } h =1 của X sao cho nếu

h

h =1 được chọn
1. Khởi tạo các cụm: các tâm ban đầu
ngẫu nhiên
2. Lặp cho tới khi hội tụ
Gán cụm: Gán mỗi đối tượng dữ liệu x vào cụm h* (tức là tập

{X }

K
( t +1)
h*
h =1

(t ) 2
) với h* = argmin || x − µh ||

Ước lượng tâm:
t ¬ t+1

µh(t +1) ¬

1

∑

( t +1)

( t +1)

3. Sau khi tất cả các đối tượng đã được phân phối hết cho các cụm,
kiểm tra lại độ tương tự của các đối tượng trong mỗi cụm với các đối
tượng mẫu, nếu có một đối mẫu tương tự nhất với nó mà khác với đối
tượng mẫu của cụm hiện thời thì di chuyển đối tượng đang xét này
sang cụm tương ứng với đối tượng mẫu mà nó gần nhất và đồng thời
cập nhật các đối tượng mẫu cho hai cụm này.
4. Lặp bước 3 cho đến khi không có đối tượng nào thay đối sau khi đã
kiểm tra toàn bộ các đối
tượng.13
Trang
End.


Lưu Tuấn Lâm

Thuật toán Phân cụm dữ liệu nửa giám sát

3.1.3 Thuật toán k-tâm
Thuật toán k-tâm mở rộng thuật toán k –means để làm việc với tập dữ liệu hỗn
hợp gồm: thuộc tính số, thuộc tính định danh và thuộc tính có thứ tự.
 Độ đo tương tự
Giả sử DOM(Aj) là miền giá trị của thuộc tính Aj ta có các khái niệm:
Thuộc tính đinh danh: Aj được gọi là thuộc tính định danh nếu DOM(A j) là tập
không có thứ tự tức là ∀a,b ∈ DOM(Aj) hoặc a=b hay a≠b.
Thuộc tính số: Aj là thuộc tính số nếu DOM(Aj) là tập số thực.
Thuộc tính có thứ tự: nếu DOM(Aj) là tập hữu hạn và có thứ tự hoàn toàn.
 Công thức tính khoảng cách giữa hai đối tượng
Giả sử ta có x,y∈DOM(Aj), hàm dj(x,y) được xác định như sau:
• Nếu Aj là thuộc tính số thì dj được dj(x,y)=x-y (9)
• Nếu Aj là thuộc tính thứ tự và DOM(Aj) =


Vậy khoảng cách d(x,y) giữa hai đối tượng x = (x1,...,xn) và y = (y1,...,yn) được
tính bởi công thức:

Trang 14


Lưu Tuấn Lâm

Thuật toán Phân cụm dữ liệu nửa giám sát
d ( x, y ) =

n

∑ρ
j =1

2
j

d 2j ( x j , y j )

(12)

trong đó các dj(xj,yj) được tính theo các công thức (9-11) và ρj là các trọng số dương
cho bởi các chuyên gia.
Với định nghĩa trên, ta luôn có thể xem các thuộc tính thứ tự có miền giá trị là đoạn
[0,1] (các giá trị trên thuộc tính này của D là tập con) và nó cũng được xem là thuộc tính
số khi không xảy ra nhầm lẫn.
 Tìm mode của tập dữ liệu

Chọn k phần tử ban đầu { z j } j =1 của D làm tâm các cụm
k

Xếp mỗi x ∈ D vào cụm Cj mà nó gần tâm nhất;
For j=1,...,k do z j ← mod e(C j ) ;
Repeat
Phân bố lại cụm theo tâm mới// như k-mean;
Cập nhật lại tâm cho các cụm // nhờ tính mode
Until các cụm không đổi;
Xác định các cụm
End

 Nhận xét
Khi thuật toán kết thúc, các đối tượng tâm có thể không thuộc tập X. Để tìm phần tử
đại diện cho mỗi cụm, ta lấy phần tử thuộc cụm gần với tâm của nó nhất.

Trang 16


Lưu Tuấn Lâm

Thuật toán Phân cụm dữ liệu nửa giám sát

Chương 4 : PHÂN CỤM DỮ LIỆU NỬA GIÁM SÁT
Phân cụm nửa giám sát là phương pháp sử dụng các thông tin bổ trợ để hướng
dẫn cho quá trình phân cụm. Các thông tin bổ trợ có thể được cho dưới dạng tập các cặp
ràng buộc hoặc một tập nhỏ một số dữ liệu được dán nhãn. Công việc xác định những tập
ràng buộc hay những tập dữ liệu được dán nhãn được thực hiện bởi người phân cụm. Sau
đây là một số thuật toán phân cụm dựa vào tập dữ liệu được dán nhãn.


t←0.
2 Lặp cho tới khi hội tụ
2.1 Gán cụm: Gán mỗi đối tượng dữ liệu x vào cụm h*
(tức là tập

{X }

K
( t +1)
h*
h =1

(t ) 2
) với h* = argmin || x − µh ||

( t +1)
2.2 Ước lượng tâm: µh ¬

1
| X h(t +1) |

2.3 t ¬ t+1

Trang 17

∑

x∈ X h( t +1)

x

x∈S h

x , với h = 1,...K; t←0.

2 Lặp cho tới khi hội tụ
2.1 Gán cụm:
- Với mỗi x ∈ S , nếu x ∈ Sh thì gán x vào cụm h
-Với mỗi x ∉ S gán x vào cụm h* , với h* = argmin
|| x − µh( t ) ||2
( t +1)
2.2 Ước lượng tâm: µh ¬

2.4 t ¬ t+1

1
| X h(t +1) |

∑

x∈X h( t +1)

x

* Nhận xét
Các Thuật toán dựa trên tập giống Seeded-KMeans, Constrained-KMeans do
Basu đề xuất vào năm 2002 và COP-KMeans do Wagstaff đề xuất năm 2001 là các thuật
toán điển hình hiện nay về phân cụm nửa giám sát. Các thông tin bổ trợ đều do người
dùng cung cấp. Vậy phân cụm nửa giám sát thực chất là quá trình kết hợp giữa người và
máy để làm tăng chất lượng phân cụm.


danh.
K mức độ rủi ro từ các thông tin khách hàng cung cấp theo ý kiến của các chuyên
gia có kinh nghiệm.
Output: Đưa ra k nhóm khách hàng có sự giống nhau là lớn nhất và dựa theo sự đánh
giá của các chuyên gia để có thể đưa ra các mẫu khách hàng với các mức độ rủi ro tương
ứng.

Trang 19


Lưu Tuấn Lâm

Thuật toán Phân cụm dữ liệu nửa giám sát

Bảng sau gồm các thuộc tính dùng để đánh giá các mức độ rủi ro:
Số
TT
1
2
3

4
5
6
7
8
9

10
11

hiểm
2:Bình thường
3: Hơi nguy hiểm
4: Nguy hiểm
Thu nhập gia đình của người mua bảo Số
hiểm
Bệnh của người mua bảo hiểm
Định danh
Tên bảo hiểm đăng kí mua
Định danh
Số tiền mua bảo hiểm
Số
Số năm mua bảo hiểm
Số
5÷60 (tùy từng bảo
hiểm)

Vì thuộc tính bệnh của khách thì có rất nhiều các bệnh khách nhau do đó trong
chương trình ứng dụng để đơn giản em chuyển thuộc tính bệnh thành các cấp độ tình
trạng của sức khỏe từ 1 đến 10 theo cấp độ nguy hiểm tăng dần 1: Hoàn toàn khỏe mạnh
và tăng dần đến 10 là các bệnh nghiêm trọng ung thư, tiểu đường, bệnh về tim mạch. Với
cấp độ 10 khách hàng sẽ khó có cơ hội mua bảo hiểm hoặc được mua nhưng với phí sẽ
rất cao. Do đó thuộc tính bệnh sẽ được coi như thuộc tính có thứ tự trong chương trình
ứng dụng
Tương tự như vậy với thuộc tính nghề nghiệp, em xin bỏ thuộc tính nghề nghiệp,
thay vào đó sẽ xét theo mức độ nguy hiểm của nghề nghiệp theo thuộc tính loại nghề
nghiệp.

Trang 20



 Kết quả phân cụm
Trang 23


Lưu Tuấn Lâm

Thuật toán Phân cụm dữ liệu nửa giám sát

KẾT LUẬN
Data mining là một trong những lĩnh vực nghiên cứ mới, nhưng đồng thời nó cũng
là một trong những xu hướng nghiên cứu ngày càng phổ biến. Do nhu cầu của thực tế,
với sự phát triển của công nghệ máy tính, của các lĩnh vực kinh tế - xã hôi thì lượng
thông tin lưu trữ ngày càng tăng, và nhu cầu khai thác thông tin, tri thức ngày càng lớn.
Do đó việc đọc, nghiên cứu và phát triển phương pháp phân cụm dữ liệu đóng một vai
trò rất quan trọng trong hoạt động của khoa học công nghệ máy tính, cũng như trong hoạt
động thực tiễn.
Trong bài báo cáo này tôi đã nêu lên những nét đặc trưng nhất trong lĩnh vực Data
Mining bao gồm các vấn đề cần khám phá tri thức, các hướng tiếp cận nghiên cứu tiêu
biểu, trong đó phân cụm dữ liệu là một phương pháp khám phá tri thức quan trọng trong
Data Mining có nhiều ý nghĩa trong khoa học cũng như thực tiễn. Trong đó phân cụm dữ
liệu nửa giám sát là một trong những hướng nghiên cứu mới được nhiều nhà khoa học
quan tâm. Bài báo cáo đã nêu được một cách khái quát về data mining và phương pháp
phân cụm không giám sát, từ đó phân tích chi tiết về phân cụm nửa giám sát. Trình bày
ba thuật toán điển hình của phân cụm nửa giám sát đó là : COP-KMeans, SeededKMeans, Constrained-KMeans và trình bày thuật toán KMeans phân cấp mới được đề
xuất của hai tác giả Việt Nam là : Hoàng Xuân Huấn và Nguyễn Trung Thông.

Trang 24



at
http://www.cs.utexas.edu/˜sugato/.

Trang 25