NGUYN THU TRÀ CÔNG NGH THÔNG TIN 2004-2006
B GIÁO DC VÀ ðÀO TO
TRƯNG ðI HC BÁCH KHOA HÀ NI
----------------------------------------------
LUN VĂN THC S KHOA HC
NGÀNH: CÔNG NGH THÔNG TIN
NGHIÊN CU VÀ ÁP DNG MT S K THUT
KHAI PHÁ D LIU
VI CƠ S D LIU NGÀNH THU VIT NAM
NGUYN THU TRÀ
Hà Ni
2006 Hà Ni 2006
2
MC LC
DANH MC CÁC KÝ HIU VÀ CÁC CH VIT TT........................4
DANH MC CÁC BNG ..........................................................................5
DANH MC CÁC HÌNH V.....................................................................6
M ðU .....................................................................................................8
CHƯƠNG 1.
KHAI PHÁ D LIU .....................................................12
1.1.
Tng quan khai phá d liu.....................................................12
1.1.1
D liu.............................................................................. 14
1.1.2
Tin x lý d liu .............................................................. 16
1.1.3
Mô hình khai phá d liu .................................................. 18
1.2.
Các chc năng cơ bn khai phá d liu ..................................19
1.2.1
Phân lp (Classification) .................................................. 19
1.2.2
Hi qui.............................................................................. 31
1.2.3
Phân nhóm........................................................................ 34
1.2.4
Khai phá lut kt hp........................................................ 38
CHƯƠNG 2.
MT S THUT TOÁN KHAI PHÁ D LIU ..........46
2.1.
Thut toán khai phá lut kt hp.............................................46
2.1.1
Thut toán Apriori ............................................................ 46
2.1.2
Thut toán AprioriTid ....................................................... 49
2.1.3
Thut toán AprioriHybrid ................................................. 51
2.2.
Ci tin hiu qu thut toán Apriori........................................54
2.2.2
Phương pháp FP-tree ....................................................... 56
2.2.3
Thut toán PHP ................................................................ 59
2.2.4
Thut toán PCY................................................................. 63
2.2.5
Thut toán PCY nhiu chng............................................. 65
2.3.
Thut toán phân lp bng hc cây quyt ñnh ........................67
2.3.1
Các ñnh nghĩa.................................................................. 68
2.3.2
Thut toán ID3.................................................................. 69
2.3.3
Các m rng ca C4.5 ...................................................... 70
CHƯƠNG 3.
ÁP DNG KHAI PHÁ TRÊN CSDL NGÀNH THU..72
3.1.
CSDL ngành Thu..................................................................72
3.2.
La chn công c khai phá .....................................................73
3.2.1
La chn công c.............................................................. 73
3.2.2
Oracle Data Mining (ODM) ............................................. 76
3.2.3
DBMS_DATA_MINING.................................................... 78
3.3.
Mc tiêu khai thác thông tin ca ngành Thu.........................79
3
3.4.
Th nghim khai phá lut kt hp ..........................................81
3.5.
Phân lp bng hc cây quyt ñnh ..........................................91
3.5.1
Phân lp ðTNT da vào so sánh t sut các năm ............. 93
3.5.2
Phân lp ðTNT theo s liu ca mt năm......................... 96
CHƯƠNG 4.
KT LUN....................................................................102
HƯNG NGHIÊN CU TIP THEO..................................................103
TÀI LIU THAM KHO ......................................................................104
PH LC................................................................................................106
4
DANH MC CÁC KÝ HIU VÀ CÁC CH VIT TT
Ký hiu, ch vit tt Ý nghĩa
Association Rules Các lut kt hp
Candidate itemset Mt itemset trong tp C
k
ñưc s dng ñ sinh ra các
large itemset
C
k
Tp các candidate k-itemset giai ñon th k
Confidence ð chc chn ca lut kt hp
= support(X∪Y)/support(X) phn ánh kh năng giao
dch h tr X thì cũng h tr Y
CSDL Cơ s d liu
DM Data mining – Khai phá d liu
DW Data warehouse – Kho d liu
ðTNT ði tưng np thu, ch ti các cá nhân hoc t chc
np thu
Frequent/large itemset Mt itemset có ñ h tr (support) >= ngư ng ñ h
tr ti thiu
ID Identifier
Item Mt ph!n t ca itemset
Itemset Tp ca các item
k-itemset Mt itemset có ñ dài k
L
k
Tp các Large itemset giai ñon th k
ODM Oracle Data Mining – 1 công c khai phá d liu
TID Unique Transaction Identifier
Transaction Giao dch
5
DANH MC CÁC BNG
Bng 1.1: CSDL ñơn gin g"m các ví d hu#n luyn ....................................25
Bng 1.2 Mô hình CSDL giao dch ñơn gin .................................................39
Bng 2.1 Cơ s d liu giao dch T ...............................................................56
Bng 2.2 Bng các sn ph$m khai phá d liu ...............................................74