Khai Phá Dữ Liệu
Nguyễn Nhật Quang
[email protected]
Viện Công nghệ Thông tin và Truyền thông
Trường Đại học Bách Khoa Hà Nội
Năm học 2010-2011
Nội dung môn học:
 Giới thiệu về Khai phá dữ liệu
ề
 Giới thiệu v
ề
công cụ WEK
A
 Tiền xử lý dữ liệu
 Phát hiện các luật kết hợp

Các kỹ thuật phân lớpvàdự đoán

Các

kỹ

thuật

phân

lớp

và

dự

có
g
iám sát
ọ gg
 Học có giám sát (Supervised learning)

Tậpdữ liệu (dataset) bao gồmcácvídụ mà mỗivídụ được
gắn

Tập

dữ

liệu

(dataset)

bao

gồm

các

ví

dụ
,
mà

mỗi

hiện

có
 Giả thiết học được (learned hypothesis) sau đó sẽ được dùng để
phân lớp/dự đoán đối với các ví dụ mới
 Học không có giám sát (Unsupervised learning)
 Tập dữ liệu (dataset) bao gồm các ví dụ, mà mỗi ví dụ không có
thông tin về nhãn lớp/giá trị đầu ra mong muốn
thông

tin

về

nhãn

lớp/giá

trị

đầu

ra

mong

muốn
 Mục đích là tìm ra (học) các nhóm/các cấu trúc/các quan hệ tồn tại
trong tập dữ liệu hiện có
3

 Học phân nhóm

Đầu vào: mộttậpdữ liệu không có nhãn (các ví dụ không có nhãn

Đầu

vào:

một

tập

dữ

liệu

không

có

nhãn

(các

ví

dụ

không


4
Khai Phá Dữ Liệu
Phân nhóm – Ví d
ụ
ụ
Mộtvídụ về phân nhóm – trong đó, các ví dụ
đ
hâ
hi
thà h
3
hó
đ
ượcp
hâ
nc
hi
a
thà
n
h
3
n
hó
m
[Liu, 2006]
5
Khai Phá Dữ Liệu
Phân nhóm – Các thành
p

• Bản đồ tự tổ thức (Self-organizing map – SOM)
• Các mô hình hỗnh
ợp
(
Mixture models
)
ợp
()
• …

Đánh
giá
chất
lượng
phân
nhóm
(Clustering quality)
Đánh
giá
chất
lượng
phân
nhóm
(Clustering

quality)
• Khoảng cách/sự khác biệt giữa các nhóm → Cần được cực đại hóa
• Khoảng cách/dự khác biệt bên trong một nhóm → Cần được cực
ể
ti

r
}
•
là mộtvídụ (mộtvectơ trong một không gian
n
chiều)
•
x
i
là

một

ví

dụ

(một

vectơ

trong

một

không

gian

n

giá

trị

được

xác

định

trước

(vd: được chỉ định bởi người thiết kế hệ thống phân nhóm)
7
Khai Phá Dữ Liệu
k-Means – Các bước chính
Với một giá trị k được xác định trước
B ớ 1Ch ẫ hiê
k
íd (đ ilà
áht
•
B
ư
ớ
c
1
.
Ch
ọn ng

(
)
• Bước 2. Đối với mỗi ví dụ, gán nó vào nhóm (trong số k
nhóm) có điểm trung tâm (centroid) gần ví dụ đó nhất
• Bước 3. Đối với mỗi nhóm, tính toán lại điểm trung tâm
(centroid) của nó dựa trên tất cả các ví dụ thuộc vào
nhóm đó
nhóm

đó
• Bước 4. Dừng lại nếu điều kiện hội tụ (convergence
criterion
) đượcthỏa mãn; nếu không, quay lạiBước2
criterion
)

được

thỏa

mãn;

nếu

không,

quay

lại


as

the

initial

centroids
while not CONVERGENCE
for each instance x∈D
Compute the distance from x to each centroid
Assign x to the cluster whose centroid is closest to x
df
en
d

f
or
for each cluster
Re-com
p
ute its centroid based on its own instances
p
end while
return {The k clusters}
9
Khai Phá Dữ Liệu
Điều ki
ệ
n h
ộ


dụ

vào

các

nhóm khác, hoặc
• Không có (hoặc có không đáng kể) thay đổi về các điểm trung tâm
(tid)ủ áhó
h ặ
(
cen
t
ro
id
s
)
c
ủ
a c
á
c n
hó
m,
h
o
ặ
c
• Giảm không đáng kể về tổng lỗi phân nhóm:

k-Means – Minh h
ọ
a
(
1
)
ọ ()
11
Khai Phá Dữ Liệu
[Liu, 2006]
k-Means – Minh h
ọ
a
(
2
)
ọ ()
12
Khai Phá Dữ Liệu
[Liu, 2006]
Điểm trung tâm, Hàm khoảng cách
 Xác định điểm trung tâm: Điểm trung bình (Mean centroid)
1
•
(
vectơ
)
m
i
là điểm trun

Hàm khoảng cách:
Euclidean distance

Hàm

khoảng

cách:

Euclidean

distance
()( )( )
22
22
2
11
),(
innii
mxmxmxd −++−+−=−=
ii
mxmx
• (vectơ) m
i
là điểm trung tâm (centroid) của nhóm C
i
• d(x,m
i
) là khoảng cách giữa ví dụ x và điểm trung tâm m
i

các

ví

dụ

(kích

thước

của

tập

dữ

liệu)
 k: Tổng số nhóm thu được
 t: Tổng số bước lặp (của quá trình phân nhóm)
ế ả
ề ỏ ả
• N
ế
u c
ả
2 giá trị
k
và
t
đ


phổ

biến

nhất
14
Khai Phá Dữ Liệu
k-Means – Các nhược điểm (1)
 Giá trị k (số nhóm thu được) phải được xác định trước
 Giải thuật k-means cần xác định cách tính điểm trung bình
(centroid) của một nhóm
ố
•
Đố
i với các thuộc tính định danh (nominal attributes), giá trị trung
bình có thể được xác định là giá trị phổ biến nhất
Giảithuật
k
means nhạycảm(gặplỗi) với
các ví dụ

Giải

thuật

k
-
means


ệ
t với tất các ví d
ụ
khác
ụ g ạ ụ ( ) ệ ụ
• Các ví dụ ngoại lai có thể do lỗi trong quá trình thu thập/lưu dữ liệu
• Các ví dụ ngoại lai có các giá trị thuộc tính (rất) khác biệt với các
giá trị thuộc tính của các ví dụ khác
15
Khai Phá Dữ Liệu
k-Means – Các ví d
ụ
n
g
o
ạ
i lai
ụ g ạ
16
Khai Phá Dữ Liệu
[Liu, 2006]
Giải
q
u
y
ết vấn đề n
g
o
ạ
i lai


chỉ

1)

bước

lặp

phân

nhóm
,
trước

khi quyết định loại bỏ
• Giải
p
há
p
2. Th
ự
c hi
ệ
n vi
ệ
c lấ
y
mẫu n
g


là

rất nhỏ
─ Gán các ví dụ còn lại của tập dữ liệu vào các nhóm tùy theo đánh
giá về khoảng cách (hoặc độ tương tự)
giá

về

khoảng

cách

(hoặc

độ

tương

tự)
17
Khai Phá Dữ Liệu
k-Means – Các nhược điểm (2)
 Giải thuật k-means phụ thuộc vào việc chọn các điểm trung tâm ban
đầu (initial centroids)
1
st
centroid
2

mỗi

lần

bắt

đầu

với

một

tập

(khác

lần trước) các hạt nhân được chọn ngẫu nhiên
19
Khai Phá Dữ Liệu
[Liu, 2006]
k-Means – Các hạt nhân ban đầu (2)
 Lựa chọn ngẫu nhiên hạt nhân thứ 1 (m
1
)
 Lựa chọn hạt nhân thứ 2 (m
2
) càng xa càng tốt so với
hạt nhân thứ 1
 …
 Lựa chọn hạt nhân thứ i (m

20
Khai Phá Dữ Liệu
k-Means – Các nhược điểm (3)
 Giải thuật k-means không phù hợp để phát hiện các
nhóm (cụm) không có dạng hình elip hoặchìnhcầu
nhóm

(cụm)

không

có

dạng

hình

elip

hoặc

hình

cầu
21
Khai Phá Dữ Liệu
[
Liu, 2006]
Phân nhóm tích tụ phân cấp (1)
 Sinh ra một chuỗi lồng nhau của các nhóm, được gọi là

GiảithuậtHAC

Giải

thuật

HAC
• Bắt đầu, mỗi ví dụ chính là một nhóm (là một nút trong dendrogram)
• H
ợp
nhất 2 nhóm có mức đ
ộ
tươn
g
t
ự

(g
ần
)
nhau nhất
ợp ộ g ự (g )
 Cặp 2 nhóm có khoảng cách nhỏ nhất trong số các cặp nhóm
• Tiếp tục quá trình hợp nhất
• Giải thuật kết thúc khi tất cả các ví dụ được hợp nhất thành một
nhóm duy nhất (là nút gốc trong dendrogram)
23
Khai Phá Dữ Liệu
Giải thu
ậ

Liên

kết

trung

bình

(Average

link)
• Liên kết trung tâm (Centroid link)
• …
25
Khai Phá Dữ Liệu