án t t nghi

i h c dân l p H i Phòng
L IC

Trong su t th i gian h c t
m

án t t nghi p

c các th y cô ch b o, dìu d

n bè quan tâm,

ng viên.
c tiên e
Ngô Qu c T o

c bày t lòng bi
i

t t i PGS TS

ng và nhi t tình ch b o,

su t quá trình th c hi

ng d n em trong

án t t nghi p này.
il ic


Bùi Trung Thành - CT1301

Page 1


án t t nghi

i h c dân l p H i Phòng
M CL C

L IC
L

....................................................................................................... 1
U ...................................................................................................... 4
NG QUAN V KHAI PHÁ D LI U .................................. 7

1.1. Gi i thi u v khám phá tri th c .................................................................. 7
1.2. Khai phá d li u và các khái ni m liên quan ................................................ 9
1.2.1. Khái ni m khai phá d li u..................................................................... 9
1.2.2.

c trong quá trình khai phá d li u ........................................... 10

1.2.3. Các thành ph n trong khai phá d li u ................................................. 11
1.2.4.
ng ti p c n và k thu t áp d ng trong khai phá d li u .................. 12
1.2.5.


i................................................... 29
2.4.5.
pháp phân c m d a trên mô hình ............................................ 30
2.4.6.
pháp phân c m d a trên d li u ràng bu c ............................. 30
2.5. M t s thu t toán phân c m d li u ............................................................ 30
2.5.1. Các thu t toán phân c m phân ho ch ................................................... 30
2.5.2. Thu t toán phân c m phân c p ............................................................. 32
2.5.3. Thu t toán COP Kmeans ................................................................... 33

Bùi Trung Thành - CT1301

Page 2


án t t nghi

i h c dân l p H i Phòng

CH

NG D NG THU T TOÁN K - MEANS TRONG PHÂN
N NH ........................................................................................................ 35
3.1. T ng quan v phân vùng nh ........................................................................ 35
3.2.
ng ti p c
n nh.............................................................. 36
3.2.1.
................................. 36
3.2.2.


Bùi Trung Thành - CT1301

Page 3


án t t nghi

i h c dân l p H i Phòng
DANH M C HÌNH

Hình 1: Quy trình phát hi n tri th c ......................................................................... 8
c trong khai phá d li u ............................................................. 10
p c n phân c p........................................................ 25
Hình 4: p là m

m h t nhân v

Pts là 3. Kho
h c hai chi u, q là m
Hình 5: q là m

ng trù m t là min

c dùng là kho ng cách Euclide trong không gian hình
m liên thông m
tr c ti p t p. ............................ 27

m liên thông m
m có k t n i m

U

Trong nh
kh

phát tri n m nh m c

th

thông tin c a các h th

chóng. Bên c

c tin h c hóa m t cách
c khá

Hàng tri u

d li u (CSDL)
.

t làm cho ho
o ra m

ng s n xu t

ng d li u kh ng l .

c s d ng cho các ho


phá d li u mô t và k thu t khai phá d li u d

oán.

án t t nghi p này em xin trình bày v
c ng

t trong nh ng v

-

n c a khai phá d li u.

ng quan v Khai phá d
li u; ng d ng trong

m

li u; Phân c m d

i s ng.

-

m c ng

n nh.

K t lu n: Tóm t t nh ng v
ng phát tri

th c. Quy trình khám phá tri th c; khai phá d li u, nhi m v c a khai phá d
li

ng ti p c

t áp d ng trong khai phá d li

ng d ng c a khai phá d li u trong th c t
Phân c m d li u và các thu t tóan phân c m d li u
u v phân c m d li u; m t s ki u d li
ng ti p c n phân c m d li u và m t s thu t tóan phân
c m d li u.
ng d ng thu t tóan ku t ng quan v
n nh; m t s thu
n nh và giao di

n nh
n

n nh; nghiên c u thu t tóan k-means
t mô ph ng thu t toán k-

n nh.

Bùi Trung Thành - CT1301

Page 6


án t t nghi

c g i cho m

nh. Chúng ta s d
li

t i thi

ng các thông

cl cb

c rút g n t i m c

n cho d li u. Chúng ta có th xem tri th c
p bao g m các thông tin và các m i quan h . Các m i

quan h này có th

c hi u ra, có th

cách khác, tri th c có th

c phát hi n ho c có th

c coi là d li

Phát hi n tri th

ng và t ch c cao.



nt

d li

n còn

b che khu t b i hàng núi d li u.

Bùi Trung Thành - CT1301

Page 7


án t t nghi

i h c dân l p H i Phòng

Quy trình khám phá tri th

Hình thành và

Thu th p và ti n x lý
d li u

Khai thác d li u rút
ra các tri th c

phân tích và ki m
nh k t qu

mô hình
i các d li u.

-

c 4: Hi u tri th
c bi t là làm sáng t các mô t và d
c trên có th l
p l i m t s l n, k t qu
c có th
l y trung bình trên t t c các l n th c hi n.

Bùi Trung Thành - CT1301

Page 8


án t t nghi

i h c dân l p H i Phòng

1.2. Khai phá d li u và các khái ni m liên quan
Khai phá d li
m

c thi t k

ng c c l n các d li u nh m phát hi n ra các m u thích h p ho c các m i

quan h mang tính h th ng gi a các bi


y? Và t

li

Khai phá d li u

li u kh ng

i.

mô t quá trình phát hi n ra tri th c trong

CSDL. Quá trình này k t xu t ra các tri th c ti m n t d li u giúp cho vi c d
báo trong kinh doanh, các ho

ng s n xu

phí v th i gian so v

n th

Khai phá d li u làm gi m chi
c kia.V

li
Khai phá d li u là quá trình tr giúp quy
phá các m

t và b t ng trong CSDL l n.

x lý
d
li u

Xác
nh
d li u
liên
quan

Hình 2
-

nh nhi m v

-

nh các d li

Th ng
kê tóm
Gi i
thu t
KPD
D li u
tr c ti p

M u

c trong khai phá d li u


cách so sánh các giá tr hi n t i v i các giá tr

c các giá tr

mong mu n), ho c b ng tri th c (m i liên h gi

i
m ic am

giá b ng m t hàm logic ho c m
Ngoài ra, m u còn ph i có kh
c x lý và di n gi i ph i d

m

d ng ti m tàng. Các m u này sau
n nh

ng m t hàm l i ích. Ví d
kho n vay, hàm l
Bùi Trung Thành - CT1301

b t ng c a m u.

li u các
i nhu n t các kho n
Page 10




nguy hi m do b h c quá nhi u và làm gi m
d

tr nên ph c t
-

u di n

li

a, vi c tìm ki m s càng

c gi

.

Ki

t m

c các tiêu

chu n c a quá trình phát hi n tri th c hay không. Vi
c th c hi n thông qua ki m tra d li
vi

giá mô hình

i v i nhi m v d


c áp d

t
ng s

d ng các k thu t tìm ki m heuristic b
các mô hình có th
Bùi Trung Thành - CT1301

c c a không gian

n các tìm ki m t ng th .
Page 11


án t t nghi

i h c dân l p H i Phòng

1.2.4.

-

c có giám sát ): Phân l p d li u là vi c xây

Phân l p và d

d ng m t mô hình mà có th


Khai phá chu i theo th i gian:Phân tích chu
trong t p r i r c. Chu

ng.

cs d

tìm m u

c t o thành t t p các giá tr r i r c. Phân tích

chu i theo th i gian và khai phá lu t k t h
thêm tính th t và th i gian.
-

Phân tích ngo i l : Phân tích ngo i l
t

t d ng c a phân c m, nó

ng h p r t khác bi t so v

ng h

khi nó th hi n nh ng l i trong d li u ho c th hi n ph n thú v nh t
trong d li
-

cs d



i s

marketing, tài

chính, ngân hàng và b o hi m, khoa h c, y t , an ninh, internet
-

Yh

c kh e: Chu

nh trong y t d a trên

k t qu xét nghi
-

Tài chính và th

ng ch ng khoán: Áp d ng vào phân tích các th

tín d ng tiêu bi u c

n tài kho n nh

c,

ng khoán, gi y ch ng nh n
và các qu


ng d a vào yêu c

c: Quan sát chú tr ng t i vi c thu th p và phân tích d
li u, s d ng các nguyên t
thuy

nc av

c lý

ng theo s phát tri n các mô hình máy tính hay mô
miêu t các v t th và hi
c b sung l

c lý thuy t tìm cách gi i

thích các k t qu quan sát, và vi c quan sát l
xác nh n các k t qu lý thuy t.
-

Th thao, gi i trí

-

Vi n thông

-

Máy tìm ki m



a phân c

ng vào các

ng trong cùng m t c
ng gi a các c m l n, t

ra quy

b t

p thông tin, tri th c h u ích cho vi c

nh.

c tính c a d li
nh kho ng cách gi

d li u.
gi ng nhau gi a các c

ng các hàm này ho
(Dissimilar) gi

ng d li u, thông

(Similar) ho
ng d li u. Giá tr c




án t t nghi

i h c dân l p H i Phòng

c chính trong quá trình phân c m d li u:
-

Xây
Phân c m d li u là bài toán thu
c ng d ng r

c h c máy không giám sát

khai thác thông tin t d li u

2.1.2.
Phân c m d li u có th

c ng d ng trong nhi

c c a cu c s ng

ví d
-

i: Tìm ki m nhóm các khách hàng quan tr
ng và nh



m dòng c a ma tr n D.

Cách th 2 là nhóm các m u khác nhau trên các h

ng, ví d

gom các c t c a ma tr n D.
- Phân c m d li u ph c v trong s c kh e tâm lý: Phân c m d li u áp
d ng trong nhi

c s c kh e, tâm lý, bao g m c vi

duy trì s c kh e, c i thi n cho h th
Bùi Trung Thành - CT1301

y và

c kh e và công tác
Page 15


án t t nghi

i h c dân l p H i Phòng

phòng ch ng b nh t

i khuy t t t. Trong s phát tri n c a h


r i ro do phát tri n y t

- Phân c m d li u trong ho
c u th

nh

u ki n nh

ng nghiên c u th

ng phân c m d li

n th
n th

phân chia th
ng h n

ng

ng, phân c m

ng thành nh ng c m mang ý

ng nam gi i t 21

gi i ngoài 51 tu

i có

V

phân c m d li

c quan tâm m t cách r ng rãi, m

ng b v phân c m d li u. Nói m
d li

t t p d li u và m

nhóm d li u l i ch ng h

, chúng ta

m d li u trong cùng m t nhóm gi ng nhau

m d li u trong các nhóm khác nhau v s
v

i khái, phân c m

ng d ng. Rõ ràng là

c b t g p trong nhi u ng d ng, ch ng h

b n, bi u di n gene, phân lo i khách hàng, x lí nh...

Bùi Trung Thành - CT1301



nhau c a các ph n t d li u. Các thu t toán phân c

iv ih uh t

nh n d ng s khác
ng s d ng m t trong

hai c u trúc d li u sau:
1. Ma tr n d li u: Là m ng n hàng, p c
ng, các ph n t trong m i hàng ch giá tr thu

thu c tính c

i

ng c

i

M

2. Ma tr

: Là ma tr n n hàng, n c t, ph n t d(i,j) ch a kho ng
khác bi t gi
u d(i,j) x p x b

càng l



.

c mi n và h

d

ng trong không gian k chi

ng thu c

D, v i x=(x1, x2,...xk); y=(y1, y2,...yk); z=(z1, z2,...zk
c các thu

i,

yi, zi v i i=1...k

ng c

y nó

s có các ki u d li u sau:
2.2.1.
- Thu c tính liên t c: N u mi n giá tr c a nó là vô h n không
a 2 giá tr t n t i vô s giá tr khác (ví d
các thu

, nhi


nh x=y hay xy.

t : Là thu

tính th t
2 thu c tính th t thì có th
- Thu c tính kho ng:
thu c tính kho ng có th

ng. N u x và y là
nh là x=y, x<>y, x>y, xyi thì có th nói x cách y 1 kho ng là x i - yi

ng v i


ng h

i s d ng có th

i tr ng s cho các

thu
chu

bi n là bi

d

s
+T

i các thu c tính v

i v i thu c tính f ta th c hi

l nh trung bình:

1f...xnf

là các giá tr thu c tính f c a n ph n t d li u và mf là giá tr

trung bình c

+


i v i các ki u d li u

2.3.1.
c tính c a d li

p

nh "kho ng cách" gi

d li u.

gi ng nhau gi a các c
ng các hàm này ho

(Similar) ho c là tính

tính

(Dissimilar) gi

ng d li u, thông

ng d li u. Giá tr c

càng l n thì s gi ng nhau gi

ng càng l

c l i, còn

t

k m

cl

tránh s nh m l n, thu t ng
hàm tính

c

ho c

. M t không gian metric là m t t

nh

các "kho ng cách" gi a t ng c p ph n t , v i nh ng tính ch
kho ng cách hình h
ng b t k

ng c a

t t p X (các ph n t c a nó có th là nh ng
ng d li

c p

c


iii.

d( x, y) =d( y, x) v i m i x, y;

iv.

d( x, y) d(x, z) + d (z, y);

Hàm d

y;

c g i là m t metric c a không gian. Các ph n t c a X

cg

m c a không gian này

2.3.2.
Thu c tính kho ng: Sau khi chu
ng d li

c

nh b ng các metric kho
q

n

-


c bi t

i 1

c a

ng h p q=2).
n

-

Kho ng cách Manhattan: d x, y

xi
i 1

c a kho
-

ng h p q=1).

Kho ng cách c c

i: d x, y

Max in 1 xi

kho ng cách


-

ng s các thu c tính có giá tr là 1 trong c

ng x,y.

-

ng s các giá tr thu c tính có giá tr là 1 trong x và 0 trong y.

-

ng s các giá tr thu c tính có giá tr 0 trong x và 1 trong y.

-

ng s các giá tr thu c tính có giá tr 0 trong x và y.
i v i d li u thu c tính nh

-H s

n: d x, y

,

ng x và y có vai

i x ng và có tr ng s .
- H s Jacard: d x, y



p m
p

i sánh

ng trùng nhau và p là t ng s các thu c tính.
Thu c tính có th t :Phép
v i thu c tính th t

c th c hi n

th t cóM igiá tr (Mikích
th t

sau:

phi

t gi a các
sau,

i

ng d li u

ta gi s i là thu c tính

c mi n giá tr ): Các tr ng thái Mi



d ng công th c tính

phi

i v i các giá tr zi( j ) ,

,v i
t c a thu c tính kho ng

chính là

phi

Thu c tính t l : Có nhi u cách khác nhau

tính

t c a thu c

tính có giá tr .

cácthu c tính t l . M t trong nh ng s

t

là s d ng công th c tính

logarit cho m ithu c tính xi, thí d qi= log( xi), lúc nàyqi
thu c tính kho ng. Phép bi n

c a các thu c tính d li u b ng cách chu n hoá chúng ho c gán tr ng
s cho m i thu c tính giá tr trung bình,
s d ng trong các

l ch chu n. Các tr ng s này có th

kho ng cách trên, thí d v i m i thu c tính d li u

c gán tr ng s

ngwi (1

),

t d li u

c xác

n

sau: d x, y

w i ( xi

yi )2 .

i 1

i ta có th chuy n


thu t toán PCDL có hi u qu cao trong vi c

m b o ch t

ng

chi phí tính toán c a thu t toán.
Bùi Trung Thành - CT1301

Page 23


án t t nghi
2.4. Các

i h c dân l p H i Phòng

ng ti p c n c a bài toán phân c m d li u

phân ho

a trên m

d

i, phân c m d a trên mô hình, phân c m d a trên ràng bu c.
2.4.1.

pháp phân


nh

PCDL, do nó ph i tìm ki m t t c các cách

M t s thu t toán phân c m phân ho

- MEANS,

PAM, CLARA, CLARANS ....
2.4.2.

pháp phân

phân

Phân c m d li u phân c p s p x p m t t p d li
trúc có d ng hình cây, cây phân c
Cây phân c p có th

tc u

c xây d ng theo k thu

quy.

c xây d

trên xu

i lên (Bottom up).


án t t nghi

i h c dân l p H i Phòng

G p:
Xu t phát m

ng và t o m t c m ch a nó.

N u hai c

g n nhau s

c g p l i thành m t c m

duy nh t.
Lpl

n khi ch còn m t c m duy nh t là toàn b

không gian.
Tách:
Xu t phát t c m duy nh t là toàn b không gian
Ch n c

phân bi t cao nh

c này s