£)~I HQC QUOC GIA THANH PHO HO CHi MINH
TRU'CrNG gAl HOC KHOA HOC TU' NHIEN

NGUYEN HA GIANG
KHAM PHA LuA T KET HO'P MO'
. .
vA lrNG DUNG
.
Chuyen nganh: TIN HQC
Ma so: 1.01.10
LuAN VAN THAC sl
. .
(Chuyen nganh Tin hQc)
NGU'O'I HU'O'NG DAN KHOA HQC:
TS. LE HoAI BAc
Thanh phi> Ho Chi Minh -2004
1
MVC LVC
ro, *<>G\
MVC LVC 1
DANH MVC BANG MINH HQA 4
DANH MVC HINH MINH HQA 6
LdI CAM ON 9
PHANMa DAu 10
Chuang 1: TONGQUANKHAMPHADU LIEu , 12
1.1Khalll pha du li~u 12
1.2Cac giai dol,lnchinh trong ti€n trinh kham pha du li~u
, 13
1.3 Cac nhi~m v\,lk~am pha du li~u 15
1.4Phuang phap kham pha du li~u""""""""""""""""""""""""""""""""""" 16
1.5Cac lol,lidu li~uduQ'ckham pha 18

3.3.2 Th\l'c nghi~m v~ k~t qua Imam pha 82
Chuang 4: KHAM PHA LuAT KET HOP MO TANG CVONG 85
4.1 Kham pha diI li~utang cuang 85
4.2 Kham pha lu~tk~t hqp tang cuang 86
4.3 Xay d\l'ngthu~troan kham pha lu~tk~thQ'pma tang cuang 89
4.3.1 Cac tinh hu6ng c~p nh~titemset 90
4.3.2 Ap d\lng cay ti~nt6 cac itemset d~Imampha tang cuang 92
4.3.3 Thu~t toan kham pha lu~tk~thqp ma tang cuang 96
4.4 K~t qua th\l'Cnghi~m 100
Chuang 5: lrNG D1)NGKHAM PHA LuAT KET HOP MO
" 102
5.1 Kham pha lu~t trong giao tac sieu thi 102
5.2 Kham pha lu~ttrong ca sa diI li~uKDD-CUP-98 108
5.3 Kham pha lu~ttrong diI li~ub~nh nhan Hemophilia 115
5.4 Kham pha lu~t trong diIli~uti~u duang cua v~t nu6i 120
3
Chuang 6: CHUaNG TRINH CAI BAT 122
6.1 M6i truang ling d\lng 122
6.2 Chuang trinh FARMiner 122
6.3 Chuang trinh IncFARMiner 126
KET LuAN vA Hu6NG PHAT TRIEN 131
K€t lu~n 131
Huang phat tri~n 132
TAl LI$U THAM KHAo 133
roe*eoG\
4

DANH M1JCBANG MINH HQA
ro, ~
Bang 2.1: Bang cac giao .tac 24

Bang 5.2: Danh m\lCmQts6 man hang minh hQa 102
Bang 5.3: MQt s6lu~t di~n hinh du<;yckham pha l06
Bang 5.4: Mo ta thuQc tinh trong bang dl1li~u kham pha 108
Bang 5.5: Danh m\lCcac item t6ng quat trong nhl1ng cfiy phan lap 111
Bang 5.6: Minh ho~ mQt s6 lu~t di~n hinh du<;yckham pha 112
Bang 5.7: Bang thuQc tinh cO'sa dl1li~u b~nh nhan Hemophilia A 116
Bang 5.8: Nhl1ng lu~t di~n hinh du<;yckham pha 118
Bang 5.9: Minh ho~ mQts6 m~utin trong bang dl1li~uti~u duang 120
Bang 5.10: MQts6 lu~t du<;yckham pha tir dl1li~uti~u duang v~t nuoi 120
Bang 6.1: Thong tin chuang trinh cai d~t 122
~*~
6
nANH M1)CHiNH MINH HQA
ibe*~
Hinh 1.1: Minh hQa cac nnh V\fCduQ'c(rng d\mg kham pha 11
Hinh 1.2: T6ng quail tien trinh kham pha du li~u 13
Hinh 2.1: Minh hQalu~tket hQ'p , 23
Hinh 2.2: Minh hQadQh6 trQ'va dQtin c~y cua lu~tket hqp 25
Hinh 2.3: Minh hQamQtc.1utruc phan lap CCYban 27
Hinh 2.4: Kien truc phan c.1pd€ rai r~c cac thuQctinh s6 luQ'llg 40
Hinh 2.5: Cac khoang rai r~c 43
Hinh 2.6: Cac khoang chia ch6ng cheo 44
Hinh 2.7: Phan khoang d\fatren t~pma 45
Hinh 2.8: Ham thanh vien cho cac vling ma 46
Hinh 2.9: C.1utruc phan lap tren thuQc tinh Mon-hang 49
Hinh 2.10: M6 hinh kham pha lu~tket hQ'pt6ng quat ma 61
Hinh 3.1: M6 hinh thu~t toan AFAR 66
Hinh 3.2: Cay ti~n t6 cac item ma 70
Hinh 3.3: Cay FIP a c.1pth(rnh.1t 71
Hinh 3.4: Cay FIP vai cac itemset (rngvien a C.1pth(r2 72

Hinh 5.5: C~pthu hai cua nhanh Others 104
Hinh 5.6: Vung ma va ham thanh VieDtuong ling cho cac item 105
Hinh 5.7: Phan lap cho nh6m ki~u nha 110
Hinh 5.8: Phan lap cho nh6m g6c dan 110
Hinh 5.9: Phan lap cho nh6m nghanh ngh~ 110
Hinh 5.10: Phan lap cho nh6m thu nh~p III
Hinh 5.11: Phan nh6m cho nh6m phuong ti~n di lam III
Hinh 5.12: T~pma va ham thanh VieDd~phan lap 112
Hinh 5.13: C~utruc phan lap cho bang du li~ukham pha 117
Hinh 5.14: T~p ma va ham thanh vien cho thuQctinh Age va Height 117
8
Hinh 5.15: Ham thanh vien cho PVIII, Weight va s61~n chay mall 117
Hinh 5.16: Ham thanh vien cho tu6i, tn;mg luQ'ng, li~u luQ'llg 120
Hinh 6.1: Man hinh chinh chuang trinh PARMiner " 123
Hinh 6.2: Man hinh k~t n6i dfi'li~uva chQnbang kham pha 124
Hinh 6.3: Man hinh khai baa c~vtruc phan lap va vung mO'. ". 124
Hinh 6.4: Man hinh chQnthu~ttoan kham pha. 125
Hinh 6.5: Man hinh xu~t lu~tduQ'ckham pha. 125
Hinh 6.6: Man hinh so sach thai gian thvc hi~n cua hai thu~ttoan 126
Hinh 6.7: Man hinh chinh cua chuang trinh IncPARMiner. 127
Hinh 6.8: Man hinh xem bang giao tac kham pha. 128
Hinh 6.9: Man hinh xem c~utruc phan lap. 128
Hinh 6.10: Man hinh xem cac lu~tduQ'ckham pha. " 129
Hinh 6.11: Man hinh xem t~p itemset ph6 bi~n 129
Hinh 6.12: Man hinh xem itemset thuQcNBd(pDB+). 130
~.o@
9
LOI CAM ON
~.~
2:Jdu tiin toi xin ba!) to [onE} bid o'n j.au j.dc ciin nE}uo'i~hd!) cia tqin tLnh hudnE}

Nh~n bi€t duQ'ct~m quail trQng cua lInt V\fCnay nen m<)ts6 cac h~ th6ng
qUailtri cO'sa du li~u dil tich hQ'pcong C\1kham pha du li~u, Day la m<)tS\fcach
m~ngso vai h~th6ng cu, vi truac day cac h~ qUailtri cO'sa du li~uchi c6 chuc nang
chinh la quail ly du li~u mQtcach hi~uqua. S\fc6 mi;itcua cong C\1kham pha du li~u
VaGtrong h~ qUail tri cO'sa du li~u ph~n naG dil n6i len y nghla th\fc ti€n cua lInt
V\l'cnay.
MQttrong nhung chuc nang duQ'cd~c~p reltnhi~u trong kham pha du li~u la
kham pha S\fk€t hQ'pgiua cac m~u trong du li~u hay con gQi la lu~t k€t hQ'p.Trong
thai ky d~u lu~t k€t hQ'pchi dO'ngian la kham pha S\fhi~n di~n cua mQt m~u A thi
d~n d€n S~'xucit hi~n m~u B, Sau d6 lu~t k€t hQ'pduQ'cphat tri€n d€ kham pha quail
h~ c6 tinh s6 luQ'ng giu'a cac m~u, Lu~t nay duQ'c gQi la lu~t k€t hQ'ps6 luQ'ng, M<)t
s6 cac khai ni~m duQ'c b6 sung VaGdu li~u d€ kham pha lu~t k€t hQ'Pa muc t6ng
quat
11
Trong thai gian gftnday, ly thuy€t t~p ma duQ'cap d\lng d~ xu ly cac dl1li~u
s6 luQ'ngtrong kham pha dl1li~u,Nguyen nhan cua vi~c ap d\lng ly thuy€t t~p ma la
do nhl1ngh~n ch€ cua t~p c6 di~n(t~p r5) trong vi~c rai r~c gia tri s6luQ'ng.
Khai ni~m khcimphci luqt kit h9'PmiY(Fuzzy Association Rule Mining) cling
xu~t hi~n tlI' d6 va la 111<)tHnh V\fCkha m6i me va dfty ti~m nrmg, Day cling chinh la
v~n d~ 111alu~n van d~ c~p: "Khcim phci luqt kit h9'P miY va ung d1;lng".Lu~n van
trinh bay khai ni~m v~ lu~t k€t hQ'Pma, xay d\fng mo hinh va thu~t toan d~ kham
pha lu~tk€t hQ'pma, Ngoai ra lu~nvan cling nghien elm den vi~c kham pha lu~tk€t
hQ'p 1110'tang cuang.
C~u truc chinh cua lu~n van baa g6m 6 chuang duQ'ct6m t~t nhu sail:
1. ChU'O'n~: T6ng quail kham pha dl1li~u
Gi6i thi~u t6ng quail v~ kham pha dl1li~ubaa g6m: ky thu~t ap d\lng, nhi~m
V\lth\fc hi~n, HnhV\fCap d\lng,xu hu6ng quail trQngcua llnh V\fCnay
2. ChU'o'n2 2: Lu~t k€t hQ'pt6ng quat ma
Gi6i thi~u khai ni~m lu~t k€t hQ'pt6ng quat ma, cac mo hinh va thu~t toan
t6ng quat d~ kha111pha.

tiJm nang trang dif fi?u" [19]. Thong qua vi~c rut trich tri thlic trong du li~u, nhung
ca sa du li~u Ian cling c~p m<)tngu6n thong tin d6i daD,tin c~y dap ling cho vi~c
tim ki~mva xac nh~n tri thlic. Nhung tri thlic kham pha co th~ duQ'cap dl,lngcho
c6ngvi~cqUailly thong tin, ra quy~t dinh, di~ukhi~n xu ly va nhi~uling dl,lngkhac.
13
Do d6 kham pha du li~u duQ'c xem nhu la m<)tlInh V\fCnghien clm quail tn;mg va
cling dfiy thach thuG. Nhi~u nha nghien CUutrong nhi~u lInh V\fCkhac nhu h~ ca s6
diI li~u, h~ ca s6 tri thuG, tri tu~ nhan t1;1o,hQc may, tim ki~m tri thuG, th6ng ke,. da
c6 nhi~u SlJquail tam d~n lInh V\fCkhai pha tri thuG. SlJ n~m b~t thong tin la chia
kh6a thanh Gong trong lInh VlJCthuang m1;1i,cac nha kinh doanh da cam nh~n ra
duQ'ctfim quail trQng cila lInh VlJCnay va hQ da c6 nhi~u ung d\lng hi~u qua tir k~t
qua kham pha diI li~u d~ gia tang lQ'inhu~n trong vi~c kinh doanh.
Qua trinh kham pha tri thuGtrong diI li~u c6 th~ duQ'ct6m t~t qua cac giai
do1;1nchinh nhu: chQn lQc diI li~u tir m<)tngu6n diI li~u, cac giai do1;1nchuftn bi
thong tin, giai do1;1nap d\,mgcac thu~t toan kham pha diI li~u va giai do1;1ncu6i la
chuy~n k~t qua thanh tri thUGma con nguoi hi~u duQ'c.C6 th~ xem qua trinh ap
d\mg cac thu~t toan kham pha diI li~u la quail trQngnhAt,qua trinh nay se quy~t
dinh d~n ki~u k~t qua duQ'ckham pha.
M9t trong s6 nhiIng k~t qua thu duQ'ctir ti~n trinh kham pha tri thUGtrong diI
li~u la nhiIng thong tin d1;1nglu~t, day la m<)td1;1ngth~ hi~n tri thUGph6 bi~n nhAt.
N6i b~t han ca do nh~n duQ'cnhi~u SlJquail tam va c6 nhi~u Gong trinh nghien CUu
la !wjt kit h9P (Association Rule). D1;1nglu~t nay th~ hi~n m6i quail h~ cung xuAt
hi~n nhung d6i tUQ'llgtrong m<)tca s6 diI li~u nao d6. Cho phep xac dinh duQ'cSlJ
xuAthi~n cila m<)td6i tuQ'ng nay thong qua S\fhi~n di~n cila m<)td6i tUQ'llgkhac.
1.2 Cac giai ao{ln chink trong ti~n trinh kham pha diJoliill
Chinh vi m\lc tieu kham pha tri thuG ngfim dinh trong ca s6 diI li~u nen qua
trinh kham pha thuong phai qua m<)ts6 cac giai do1;1ncfin thi~t. Bao g6m nhUng giai
do1;1nchuftn bi diI li~u kham pha, giai do1;1nkham pha diI li~u va cu6i cung la giai
do1;1nchuy~n k~t qua kham pha sang nhUng tri thuG cho con nguoi hi~u duQ'c. Chi
ti€t cae bUGCth\fc hi~n duQ'cmo ta t6m t~t nhu sail:

trong ca sa du li~u.Vi d\l nhu nhung tri~u chung cila rnQtdin b~nh S thi thucmg
c6 th~duQ'cth~ hi~nqua mQtt~plu~tthuQcHnhA.
* Kharn phil nhung luat rheinbiet: kharn philnhung d~ctIling, nhung thuQctinh d~
rhein bi~t gil1'at~p du li~u nay v6'i t~p du li~u khac. Vi d\l nhu nh~rnrhein bi~t
giua cac chung b~nh, thi rnQtlu~trhein bi~t duQ'cdung d~ tom t~t nhung tri~u
chung nh~rnrhein bi~t chung b~nhxac dinh v6'inhung chung b~nhkhac.
* Kharn phil luat k€t hap: kharn pha S\fk€t hQ'pgiua nhung d6i tuQ'ngtrong rnQt
t~pdu li~u. Gia Slrhai t~p d6i tuQ'ng{Al, A2, ,Am}va {Bl, B2, ,Bn} thi lu~tk€t
hQ'p c6 d<;lng(AI /I /\ Am) ~ (Bl /I /\ Bn).
* Kharn pha luat rhein lap: rhein lo<;lidu li~u VaGtrong t~p nhung lap da:bi€t. Vi
d\l nhu rnQts6 chi€c xe co nhung d~ctinh chung d~ rhein VaGcac lap d\fa tren
cach tieu th\l nhien li~u ho~c co th~ rhein VaGcac lap d\fa tren tai trQng
* rhein nh6rn: xac dinh rnQt nhorn cho rnQt t~p nhung d6i tUQllg d\fa tren thuQc
tinh cila chung. MQts6 cac tieu chu~n duQ'csu d\lng d~ xac dinh d6i tuQ'ngc6
thuQcv~ nh6rn hay khong.
* Du baa: d\f baa gia tri c6 th~ dung cila nhung du li~u bi thi€u ho~c S\frhein b6
thuQctinh naGd6 trong t~p du li~u.
* Kharn pha quy luat bi€n d6i: tirn nhung t~p lu~t phan anh nhung hanh vi ti€n
h6a, bi€n d6i chung cila rnQtt~p du li~u. Vi d\l nhu lu~t kharn pha nhung y€u t6
chinh taGdQng leu S\fthay d6i cila nhung gia c6 phi€u naG do.
16
1.4 PhtfO'ngphap kham pha dit li~u
Tu nhung nhi~m V\ltren chung ta th~y r~ng vi~c kham pha du li~ukhong chi
dan gian la st'l'd\lng duy nh~t m<)tky thu?t nao do. B~t cu phuang phap nao h6 trQ'
cho vi~c tim ki~m thong tin t6t thi se duQ'csu d\lng. Tuy thu<)cvao cac nhi~m V\l
khac nhau ma cac phuang phap co th€ duQ'cchQn,m6i phuang phap co di€m m:;1nh
va nhung m~ith:;1nch~ rieng. Chung ta co th€ phan 10:;1inhung phuang phap kham
pha du li~utheo cac nhom sail:
.:. Phuang phap th6ng ke: huang ti~p c?n th6ng ke d\1'atren n~n tang mo hinh xac
su~t.Cach thl,l'chi~n dl,l'atren vi~c ki€m chung nhung ly thuy~t da xac dinh truac

c(;tnhth~ hi~n xac sufttphl,1thuQcgiua nhUngthuQctinh do.
.:. Thuat giai di truy~n: hay I~ptrinh ti~n hoa Ii cach giai quy~t theo chi~n Iu<Jct6i
uu d\fa theo nguyen Iy ti~n hoa du<Jckhao sat trong t\f nhien. NhUng giai phap
vftnd~ t6t nhfttse di qua giai do(;tnchQnIQcvi chung se du<Jck~t hQ'Pv6'i nhau
d~ cho nhung giai phap khac t6t han. Qua trinh Cll'I~p I(;tinhu v~y cho d~n khi
vftn d~ du<Jcgiai quy~t ho~c ti~n d~n mQtnguang dUng.
.:. Tap ma: day Ii kg thu~t chinh cua vi~c th~ hi~n vi xu Iy tinh khong chinh xac.
SI!khong chinh xac du<Jcnay sinh tu nhung cO'sa du Ii~ungiy nay: S\fkhong
chinh xac, khong th~ xac djnh, khong nhfttquail vi mO'h6 NhUngt~p ma khai
thac tinh khong ch~c ch~n d~ Iim cho h~ th6ng phuc t(;tpITanen d€ quail Iy. Do
v~y nhung t~p ma t(;tothinh cach ti~p c~n m(;tnhkhong chi d~ giai quy~t tinh
khong tn,mvtfn, nhi€u hay du li~u khong chinh xac mi con giup phat tri~n cac
1110hinh khong ch~c ch~n cua du Ii~u nh~m t(;tora S\fth\fc thi thong minh, m~m
cleohan so v6'i h~ th6ng truy~n th6ng.
.:. Tap tho: t~p tho du<JCdinh nghla bai t~p xftpxi tren vi t~p xftpxi du6'LCac d6i
tuqng thuQct~p xftpxi du6'i Ii xac djnh hoin toin. Cac d6i tuqng thuQct~p xftp
xi tren Ii ph~n khong xac dinh. T~p xftpxi trencua t~p tho Ii hQicua t~p xftpxi
du6'i vi t~p bien. MQt d6i tuqng thuQct~p bien Ii xac dinh nhung khong xac
dinh hoin toin. Vi v~y, t~p tho co th~ du<Jcxem nhu Ii t~p ma co him thinh
vien ba gia tri: "dung", "saC'vi "co thi". Gi6ng nhu t~p ma, t~p tho Ii mQtkhai
18
ni~m tmln hQcd~ phan lap du li~u. T?p tho cling nhu t?P ma it duqc S11d\mg
nhu la mOtgiai phap dO"nIe. Chung thuang duqc k€t hqp vai cac phuang phap
khac nhu suy di~n lu?t, phan lap va phan nh6m.
1 5 Ctie lop; dfl' /ifu dU'{1eklttim pita
Kham pha du li~uthuang lam vi~c vai nhi€u ki~u du li~u khac nhau. Hftuh€t
cac ki~udu li~u duqc kham pha la nhung ki~u nhu sail:
ff CO"sa du lieu quail he: nhung cO"sa du li~u duqc t6 chuc theo mo hint quail h~.
Hftuh€t nhung h~ qUailtri cO"sa du li~u hi~n nay d€u h6 trq mo hint nay nhu:
Oracle, IBM DB2, MS SQL Server, MS Access