B GIÁO D CăVÀă ÀOăT O
TR

NGă

I H C CÔNG NGH TP.HCM

---------------------------

NGUY NăV Nă I N

KHAI THÁC LU T PHÂN L P K T H P
TRểNăC ăS

D

LI U B S Aă

LU NăV NăTH CăS
Chuyên ngành: Công ngh thông tin
Mã s ngành: 60480201

TP. H CHệăMINH,ăthángă11ăn mă2016

I


B GIÁO D CăVÀă ÀOăT O
TR

NGă


Cán b h

NGă

C HOÀN THÀNH T I

I H C CÔNG NGH TP. HCM

ng d n khoa h c : TS. NGUY N TH THUÝ LOAN
(Ghi rõ h , tên, h c hàm, h c v và ch ký)

Lu nă v nă Th că s ă đ

c b o v t iă Tr

ngă

i h c Công ngh TP. HCM

ngày 17 tháng 12 n mă2016
Thành ph n H iăđ ngăđánhăgiáăLu năv năTh căs ăg m:
(Ghi rõ h , tên, h c hàm, h c v c a H i đ ng ch m b o v
TT
H ăvƠătênă
Ch
1
GS. TS. Phan Th T i
2
TS. Cao Tùng Anh


IăH C

căl păậ T ădoăậ H nhăphúc
TP. HCM, ngày 01 tháng 12 n m 2016

NHI MăV ăLU NăV NăTH CăS ă
H tên h c viên: NGUY NăV Nă I N .................. Gi i tính: Nam .....................
NgƠy,ătháng,ăn măsinh: 22/06/1982 ........................... N iăsinh:

ng Nai ..............

Chuyên ngành: Công ngh thông tin ......................... MSHV: 1441860006 ............
I- Tênăđ ătƠi:ă
Khai thác lu t phân l p k t h pătrênăc ăs d li u b s aăđ i ..................................
II- Nhi măv ăvƠăn iădung:ăă
 Tìm hi u thu n toán khai thác lu t phân l pătrênăc ăs d li uăt nh.
 Tìm hi u thu n toán khai thác lu t phân l p k t h p trênă c ă s d li u
t ngătr

ng.

 Tìm hi u và xây d ng ví d cho thu n toán khai thác lu t phân l p k t
h p trênăc ăs d li u b s aăđ i.
 Xây d ngă ch

ngă trìnhă khaiă thácă lu t phân l p k t h p trên li u b s a

đ i.
 Vi t báo cáo.

(Ký và ghi rõ h tên)

NGUY NăV Nă I N


L IăCỄMă N
Tr

c tiên tôi xin bày t lòng bi tă năchơnăthƠnhăđ n cô Nguy n Th Thuý

Loanăđưăt n tình h tr ,ăh

ng d năvƠăđ ng viên tinh th n giúp chúng tôi hoàn

thành lu năv nănƠy.
Cho chúng tôi bày t lòng bi tă năchơnăthƠnhăđ n Quý Th yăCôăđưăh t lòng
gi ng d y, truy năđ t nh ng tri th c khoa h c và kinh nghi m quý báu cho chúng
tôi trong su t th i gian tham gia h c t pătheoăch

ngătrìnhăth c s

tr

ngăđ i

h c Công ngh Tp.HCM.
Sauăcùng,ăchoătôiăđ

c chuy n l iăcámă năgiaăđìnhăthơnăyêuăc aătôiăđưăluônă


d li uăt nhănh ngăcácăthu t toán khai thác lu t phân l pătrênăc ăs d li u b s a
đ iăthìăch aăcó.
gi i quy t các v nă đ nh ăđưănêuă trên, n i dung nghiên c u c a lu n
v năs t p trung vào nghiên c u các thu t toán khai thác lu t k t h p, khai thác lu t
phân l p k t h pătrênăc ăs d li u b s aăđ i, vi tăch
thu tătoánăđưănghiênăc u.

ngătrìnhăth c nghi m m t


ABSTRACT
Today, data is increasingly rich, and huge variety of fields. In particular the
development of information technology and the application of information
technology in various fields has made data warehouse was increasing rapidly. This
leads to a problem is the need for new techniques and tools to automatically convert
other huge amounts of data into useful knowledge, to serve man. On the other hand,
in a competitive environment, people increasingly need information at a fast pace to
help in decision-making and more questions of qualitative nature need to be
answered based on the volume of data giant had. Currently also had many mining
algorithms combined classification rules based on static data mining algorithms but
subclass law on database is modified, then no.
To solve the problems as mentioned above, the research content of the thesis
will focus on the study of algorithms combined mining law, mining law combined
classification on the basis of revised data, Useful program an algorithm
experimentally studied.


i

DANHăM CăCỄCăT ăVI TăT Tă


h tr ng

ng trên

SL

Lower support threshold

h tr ng

ng d

minSup

Minimum support

h tr t i thi u

minConf

Minimum Confidence

tin c y t i thi u

i


ii


Hình 2.4: Quá trình h c [5] .......................................................................................13
Hình 2.5: Quá trình phân l p [5] ...............................................................................14
Hình 2.6: Thu t toán CAR-Miner .............................................................................20
Hình 2.7: CơyăMECRăđ

c xây d ng t CSDL c a b ng 2.1 .................................20

Hình 3.1: Thu t toán CAR-MinerăModifiedăchoăc ăs d li uăt ngătr

ng ............25

Hình 3.2: Mã gi hàm CAR-Incre và UPDATE-Tree. ............................................26
Hình 3.3: Mã gi hàm TRAVERSE-TREE-TO-CHECK, ......................................27
Hình 3.4: Cây MECR-treeăđ

c t o t c ăs d li u c a b ng 3.1 ........................28

Hình 3.5: Mã gi hàm CAR_Del và UPDATE_TREE_LV1_DEL ........................31
Hình 3.6: Cây MERC-treeăđ

c c p nh t sau khi b xoá ........................................36

Hình 3.7: Mã gi hàm CAR_Modified ....................................................................37
Hình 3.8: C p nh t cây MECR sau khi d li u b s a .............................................40


iv

M CăL C
Ch

2.1. Khai thác d li u ...............................................................................................4
2.1.1. Khái ni m ...................................................................................................4
2.1.2. Quá trình khai thác d li u .........................................................................4
2.1.3. Ki n trúc c a m t h th ng khai thác d li u ............................................6
2.1.4. M t s ph

ngăphápăkhaiăthácăd li u ......................................................7

2.2. Khai thác lu t k t h p .....................................................................................10
2.2.1. Gi i thi u ..................................................................................................10
2.2.2. M t s h

ng ti p c n trong khai thác lu t k t h p ................................11

2.3. Khai thác lu t phân l p ...................................................................................12
2.3.1. Gi i thi u ..................................................................................................12
2.3.2. Quá trình phân l p....................................................................................12
2.3.3. M t s ph

ngăphápăphơnăl p .................................................................14

2.4. Khai thác lu t phân l p d a vào lu t k t h p .................................................14
2.5. Khai thác lu t phân l p k t h p CAR-Miner .................................................15
2.5.1. M t s khái ni m ......................................................................................16


v

2.5.2. C u trúc cây MECR .................................................................................16
2.5.3. Thu t toán khai thác hi u qu cho CAR-Miner.......................................18

Ch

ngă4:ăK T QU TH C NGHI MăVÀă ỄNHăGIỄ .......................................41

4.1.ăC ăs d li u th c nghi măvƠămôiătr

ng xây d ng ......................................41

4.1.1.ăC ăs d li u th c nghi m .......................................................................41
4.1.2.ăMôiătr

ng xây d ng thu t toán ..............................................................41

4.2. K t qu th c nghi m .......................................................................................41
4.2.1. K t qu th c nghi mătrênăc ăs d li u Breast .......................................41
4.2.2. K t qu th c nghi mătrênăc ăs d li u Lymph ......................................42
4.2.3. K t qu th c nghi mătrênăc ăs d li u Iris ............................................43


vi

4.2.4. Kh o sát k t qu th c nghi m..................................................................44
Ch

ngă5:ăK T LU NăVÀăH

NG PHÁT TRI N ...............................................45

5.1. K t lu n ...........................................................................................................45
5.2.ăH

kh ng l kia thành các tri th c có ích, ph c v choăconăng
tr

ng c nhătranhăthìăng

i. M t khác, trong môi

i ta ngày càng c n có thông tin v i t căđ nhanhăđ giúp

cho vi c ra quy tăđ nh và ngày càng có nhi u câu h i mang tính ch tăđ nh tính c n
ph i tr l i d a trên kh iăl

ng d li u kh ng l đưăcó.ăQuá trình ti n hành các công

vi cănh ăv y g i là quá trình phát hi n tri th cătrongăc ăs d li u, trong đóăk thu t
khai thác d li u cho phép phát hi n tri th c ti m n y. T đó,ăcácăk thu t khai
thác d li uăđưătr thành m tăl nhăv c th i s c a n n Công ngh thông tin th gi i
hi n nay nói chung và Vi t Nam nói riêng. R t nhi u t ch c và công ty l n trên th
gi iăđưăápăd ng k thu t khai thác d li u vào các ho tăđ ng s n xu t kinh doanh
c aămìnhăvƠăthuăđ

c nh ng l i ích to l n.

Các k thu t phát hi n tri th c và khai thác d li uăđ

c th c hi n qua nhi u

giaiă đo n và s d ng nhi u k thu t: phân l p, phân c m, phân tích s t

ngă t ,


c nhi u

s quan tâm nghiên c u c a các nhà nghiên c u trên th gi i.ăC ngăđưăcóănhi u gi i
phápăđ

căđ xu t cho v n đ khai thác lu tănh ălu t khai thác lu t truy n th ng,

khai thác lu tăkhôngăd ăth a.
Tuy nhiên nh ngă ph

ngă phápă trênă ch t p trung ch y u trong vi c xây

d ng thu t toán phân l p d a trên lu t k t h p ho c xây d ng lu t phân l p, mà
không th o lu n nhi u v v năđ th i gian th c thi (khai thác) c a các thu t toán.
H năth n a, khai thác phân l p d a trên lu t k t h p (CARs) tiêu t n r t nhi u th i
gian b i vì nó khai thác m t t păđ yăđ các lu t th aăng

ng. Vì th , c i thi n th i

gian khai thác phân l p d a trên lu t k t h p là m t trong nh ng v năđ chính c n
đ

c gi i quy t. Ngoài ra, các nghiên c u hi n nay t p trung ch y u v khai thác

lu t phân l p k t h pătrênăc ăs d li uăt nh,ămƠăítăquanătơmăđ n vi c khai thác trên
c ăs d li u b s aăđ i.
T nh ng v năđ nêu trên, tôi ch năđ tƠiă“Khaiăthácălu t phân l p k t h p
trênăc ăs d li u b s aăđ i” đ làm lu năv năt t nghi p.
1.3. M cătiêu,ăđ iăt


ngăphápălu năvƠăph

ngăphápănghiênăc u

 Tìm hi u các tài li uă trongă vƠă ngoƠiă n

c v khai thác d li u, lu t k t

h p, lu t phân l p, lu t phân l p k t h p.
 Tìm hi u thu t toán CAR-Miner trong bài toán phân l p d a vào lu t k t
h p.


4

Ch

ngă2: T NG QUAN

2.1. Khai thác d li u
2.1.1. Khái ni m
Khai thác d li u (Data Mining) là m t khái ni măraăđ i vào nh ngăn măcu i
c a th p k 1980. Nó là quá trình khám phá thông tin tìm n trongăcácăc ăs d li u
và có th xemănh ălƠăm tăb

c trong quá trình khám phá tri th c. Khai thác d li u

lƠăgiaiăđo n quan tr ng nh t trong ti n trình khai thác tri th c t c ăs d li u, các
tri th c này h tr trong vi c ra quy tăđ nh trong khoa h c và kinh doanh, ...

căđ

căđ u tiên trong quá trình khai thác d li u.

c khai thác trong m tăc ăs d li u, m t kho d li u và th m chí

các d li u t các ngu n ng d ng Web.
2. L a ch n d li u: hay còn g i là trích l c d li u.

giaiăđo n này d li uăđ

c

l a ch n ho c phân chia theo m t s tiêu chu n nƠoăđó,ăvíăd ch n t t c nh ng
ng

i có tu iăđ i t 25 - 35ăvƠăcóătrìnhăđ đ i h c.

3. Làm s ch, ti n x lý và chu n b tr

c d li u:ăGiaiăđoanăth ba này là giai

đo n hay b saoă lưng,ă nh ngă th c t nó là m tă b

c r t quan tr ng trong quá


5

trình khai thác d li u. M t s l iăth


6

5. Khai thác d li u: Là phát hi n và trích m u d li u.
thu tătoánăkhácănhauăđưăđ
th

giaiă đo n này nhi u

c s d ngăđ trích ra các m u t d li u. Thu t toán

ng dùng là nguyên t c phân lo i, nguyên t c k t h p ho c các mô hình d

li u tu n t .
6.

ánhăgiáăk t qu m u:

ơyălƠăgiaiăđo n cu i trong quá trình khai thác d li u.

giaiăđo n này, các m u d li uăđ

c chi t xu t ra b i ph n m m khai thác d

li u. Không ph i b t c m u d li uănƠoăc ngăđ u h uăích,ăđôiăkhiănóăcònăb sai
l ch. Vì v y, c n ph iă uătiênănh ng tiêu chu năđánhăgiáăđ chi t xu t ra các tri
th c.
2.1.3. Ki n trúc c a m t h th ng khai thác d li u

Hình 2.2: Ki n trúc c a m t h th ng khai thác d li u [3]

M tăc ăs d li u là m tăkhoăthôngătinănh ngăcácăthôngătinăquanătr ngăh nă
c ngăcóăth đ

c suy di n t kho thôngătinăđó.ăCóăhaiăk thu tăchínhăđ th c hi n

vi c này là suy di n và quy n p.
Ph

ng pháp suy di n: Nh m rút ra thông tin là k t q a logic c a các thông

tinătrongăc ăs d li u.ăPh

ngăphápăsuyădi n d a trên các s ki năchínhăxácăđ suy

ra các tri th c m i t cácă thôngă tină c .ă M u chi t xu tă đ
ph

ngăphápănƠyăth
Ph

c b ng cách s d ng

ng là các lu t suy di n.

ng pháp quy n p: Ph

ngăphápăquyăn păsuyăraăcácăthôngătinăđ

c sinh


c gán các giá tr có th c a các thu c tính, các lá mô t các


8

l pă khácă nhau.ă Cácă đ iă t
c nhăt

ngă đ

c phân l pă theoă cácă đ

ngă ng v i các giá tr , thu c tính c aăđ iăt
T o lu t: Các lu tăđ

ngă điă trênă cơy,ă quaă cácă

ng t i lá.

c t o ra nh m suy di n m t s m u d li uăcóăỦăngh aă

v m t th ng kê. Các lu t có d ng N u P thì Q, v i P là m nhăđ đúngăm t ph n
trong CSDL, Q là m nhăđ d đoán.
Cây quy tăđ nh và lu tăcóă uăđi m là hình th c mô t đ năgi n, mô hình suy
di n khá d hi uăđ i v iăng

i s d ng. Tuy nhiên, gi i h n c a nó là mô t cây và

lu t ch có th bi u di nă đ


i mua sách

âm nh c, ngo i ng , th thaoăthìăc ngămuaăđ aăCD.ăLúcăđóătaăquanătơmăđ n s l
tr

ng h p khách hàng tho mãn lu tănƠyătrongăc ăs d li uăhayăđ h tr cho lu t

nƠy.ă

h tr cho lu t chính là ph nătr măs dòng có c sách âm nh c, ngo i ng ,

th thaoăvƠăđ aăCDăhayăt t c nh ng ng

i thích c ba lo i sách trên.

Tuy nhiên, giá tr h tr lƠăkhôngăđ . Có th cóătr
t

ng

ngăđ i nh ngăng

l năh nănh ngăng
đ aăCD.ăTrongătr

ng h p ta có m t nhóm

iăđ c c ba lo iăsáchătrênănh ngăl i có m t nhóm v iăl

ng

toán h c và kh n ngăh c.ăCácăph

ngăpháp là k t qu c a vi c nghiên c u mô hình

h c c a h th ng th năkinhăconăng

i.

M ng Neuron có th đ aăraăỦăngh aăt các d li u ph c t p ho c không chính
xác và có th đ

c s d ngăđ chi t xu t các m u và phát hi năraăcácăxuăh

ph c t p mà con ng
đ

ng quá

iăc ngănh ăcácăk thu t máy tính khác không th phát hi n

c.ă Khiă đ c pă đ n khai thác d li u,ă ng

iă taă th

ngă đ c p nhi uă đ n m ng

Neuron. Tuy m ng Neuron có m t s h n ch gơyăkhóăkh nătrongăvi c áp d ng và
phát tri nănh ngănóăc ngăcóănh ngă uăđi măđángăk .
D li u



ng và bi năđ iănh ăth nào? Ví d nh ăxácăđ nh xem làm th nƠoăđ

l a ch n các cá th t o gi ng và l a ch n các cá th nào s b lo i b . Gi i thu t
c ngămôăph ng l i y u t gen trong nhi m s c th sinh h cătrênămáyătínhăđ có th
gi i quy t nhi u bài toán th c t khác nhau.
Gi i thu t di truy n là m t gi i thu t t iă uăhóa.ăNóăđ

c s d ng r t r ng rãi

trong vi c t iă uă hóaă cácă k thu t khai thác d li uă trongă đóă cóă k thu t m ng
Neuron. S liên h c a nó v i các quá trình khai thác d li u. Ví d nh ătrongăk
thu t cây quy tăđ nh, t o lu t.ăNh ăđưăđ c p
li u ch a các tham s đ

ph nătr

c, các lu t mô hình hóa d

căxácăđ nh b i các gi i thu t phát hi n tri th c.

Giaiăđo n t iă uăhóaălƠăc n thi tăđ xácăđ nh xem các giá tr tham s nào t o
ra các lu t t t nh t. Vì v y mà gi i thu t di truy năđưăđ

c s d ng trong các công

c khai thác d li u.
2.2. Khai thác lu t k t h p
2.2.1. Gi i thi u
T khiă đ

Chanel”ăho că“70%ăkháchăhƠngălƠăcôngănhơnăkhiămuaăTVăth

ng mua lo i TV 21

inches”. Nh ng thông tin nh v y r t h u ích trong vi c đ nhă h
V y v năđ đ t ra là li uăcóătìmăđ

c hoa hi u

ng kinh doanh.

c các lu tănh ăv y b ng các công c khai thác

d li u hay không? Câu tr l i là hoàn toàn có th .ă óăchínhălƠănhi m v khai thác
lu t k t h p.
2.2.2. M t s h

ng ti p c n trong khai thác lu t k t h p

L nhăv c khai thác lu t k t h păchoăđ nănayăđưăđ
theo nhi uăh

c nghiên c u và phát tri n

ng khác nhau. Có nh ngăđ xu t nh m c i ti n t căđ thu t toán, có

nh ngăđ xu t nh m tìm ki m lu tăcóăỦăngh aăh n...ăvƠăcóăm t s h

ng chính sau