Luận văn Nghiên cứu và áp dụng một số kỹ thuật khai phá dữ liệu với cơ sơ sở dữ liệu ngành Thuế Việt Nam
Bꢀ GIÁO DꢁC VÀ ðÀO TꢂO
TRƯꢃNG ðꢂI HꢄC BÁCH KHOA HÀ NꢀI
----------------------------------------------
LUꢅN VĂN THꢂC Sꢆ KHOA HꢄC
NGÀNH: CÔNG NGHꢁ THÔNG TIN
NGHIÊN CꢂU VÀ ÁP DꢃNG MꢄT Sꢅ Kꢆ THUꢇT
KHAI PHÁ Dꢈ LIꢁU
VꢉI CƠ Sꢊ Dꢈ LIꢁU NGÀNH THUꢋ VIꢁT NAM
NGUYꢀN THU TRÀ
Hà Nꢌi 2006
Hà Nꢌi
2006
2
Mꢀ
C LꢀC
DANH MꢀC CÁC KÝ HIꢁU VÀ CÁC CHꢂ VIꢃT TꢄT........................4
DANH MꢀC CÁC BꢅNG ..........................................................................5
DANH MꢀC CÁC HÌNH Vꢆ.....................................................................6
Mꢇ ðꢈU .....................................................................................................8
CHƯƠNG 1. KHAI PHÁ Dꢂ LIꢁU .....................................................12
1.1. Tꢀng quan khai phá dꢁ liꢂu.....................................................12
1.1.1 Dꢀ liꢁu.............................................................................. 14
1.1.2 Tiꢂn xꢃ lý dꢀ liꢁu .............................................................. 16
1.1.3 Mô hình khai phá dꢀ liꢁu .................................................. 18
1.2. Các chꢃc năng cơ bꢄn khai phá dꢁ liꢂu ..................................19
1.2.1 Phân lꢄp (Classification) .................................................. 19
1.2.2 Hꢅi qui.............................................................................. 31
1.2.3 Phân nhóm........................................................................ 34
1.2.4 Khai phá luꢆt kꢇt hꢈp........................................................ 38
CHƯƠNG 2. MꢉT Sꢊ THUꢋT TOÁN KHAI PHÁ Dꢂ LIꢁU ..........46
2.1. Thuꢅt toán khai phá luꢅt kꢆt hꢇp.............................................46
2.1.1 Thuꢆt toán Apriori ............................................................ 46
2.1.2 Thuꢆt toán AprioriTid ....................................................... 49
2.1.3 Thuꢆt toán AprioriHybrid ................................................. 51
2.2. Cꢄi tiꢆn hiꢂu quꢄ thuꢅt toán Apriori........................................54
2.2.2 Phương pháp FP-tree ....................................................... 56
2.2.3 Thuꢆt toán PHP ................................................................ 59
2.2.4 Thuꢆt toán PCY................................................................. 63
2.2.5 Thuꢆt toán PCY nhiꢂu chꢉng............................................. 65
2.3. Thuꢅt toán phân lꢈp bꢉng hꢊc cây quyꢆt ñꢋnh........................67
2.3.1 Các ñꢊnh nghĩa.................................................................. 68
2.3.2 Thuꢆt toán ID3.................................................................. 69
2.3.3 Các mꢋ rꢌng cꢍa C4.5 ...................................................... 70
CHƯƠNG 3. ÁP DꢀNG KHAI PHÁ TRÊN CSDL NGÀNH THUꢃ..72
3.1. CSDL ngành Thuꢆ ..................................................................72
3.2. Lꢌa chꢊn công cꢍ khai phá .....................................................73
3.2.1 Lꢎa chꢏn công cꢐ.............................................................. 73
3.2.2 Oracle Data Mining (ODM) ............................................. 76
3.2.3 DBMS_DATA_MINING.................................................... 78
3.3. Mꢍc tiêu khai thác thông tin cꢎa ngành Thuꢆ.........................79
3
3.4. Thꢏ nghiꢂm khai phá luꢅt kꢆt hꢇp ..........................................81
3.5. Phân lꢈp bꢉng hꢊc cây quyꢆt ñꢋnh ..........................................91
3.5.1 Phân lꢄp ðTNT dꢎa vào so sánh tꢑ suꢒt các năm ............. 93
3.5.2 Phân lꢄp ðTNT theo sꢓ liꢁu cꢍa mꢌt năm......................... 96
CHƯƠNG 4. KꢃT LUꢋN....................................................................102
HƯꢌNG NGHIÊN CꢍU TIꢃP THEO..................................................103
TÀI LIꢁU THAM KHꢅO ......................................................................104
PHꢀ LꢀC................................................................................................106
4
DANH MꢀC CÁC KÝ HIꢁU VÀ CÁC CHꢂ VIꢃT TꢄT
Ký hiꢎu, chꢏ viꢐt tꢑt
Association Rules
Candidate itemset
Ý nghĩa
Các luꢅt kꢆt hꢇp
Mꢐt itemset trong tꢅp Ck ñưꢇc sꢏ dꢍng ñꢑ sinh ra các
large itemset
Ck
Tꢅp các candidate k-itemset ꢒ giai ñoꢓn thꢃ k
ðꢐ chꢔc chꢔn cꢎa luꢅt kꢆt hꢇp
= support(X∪Y)/support(X) phꢄn ánh khꢄ năng giao
dꢋch hꢕ trꢇ X thì cũng hꢕ trꢇ Y
Cơ sꢒ dꢁ liꢂu
Confidence
CSDL
DM
Data mining – Khai phá dꢁ liꢂu
Data warehouse – Kho dꢁ liꢂu
ðꢖi tưꢇng nꢐp thuꢆ, chꢗ tꢈi các cá nhân hoꢘc tꢀ chꢃc
nꢐp thuꢆ
DW
ðTNT
Frequent/large itemset Mꢐt itemset có ñꢐ hꢕ trꢇ (support) >= ngưꢙng ñꢐ hꢕ
trꢇ tꢖi thiꢑu
ID
Identifier
Item
Mꢐt phꢚn tꢏ cꢎa itemset
Tꢅp cꢎa các item
Itemset
k-itemset
Lk
Mꢐt itemset có ñꢐ dài k
Tꢅp các Large itemset ꢒ giai ñoꢓn thꢃ k
Oracle Data Mining – 1 công cꢍ khai phá dꢁ liꢂu
Unique Transaction Identifier
Giao dꢋch
ODM
TID
Transaction
5
DANH MꢀC CÁC BꢅNG
Bꢄng 1.1: CSDL ñơn giꢄn gꢛm các ví dꢍ huꢜn luyꢂn ....................................25
Bꢄng 1.2 Mô hình CSDL giao dꢋch ñơn giꢄn .................................................39
Bꢄng 2.1 Cơ sꢒ dꢁ liꢂu giao dꢋch T ...............................................................56
Bꢄng 2.2 Bꢄng các sꢄn phꢝm khai phá dꢁ liꢂu ...............................................74
6
DANH MꢀC CÁC HÌNH Vꢆ
Hình 1.1 Quá trình khám phá tri thꢃc.............................................................14
Hình 1.2 Khuôn dꢓng ñơn bꢄn ghi và ña bꢄn ghi ...........................................16
Hình 1.3: Cây quyꢆt ñꢋnh ñơn giꢄn vꢈi các tests trên các thuꢐc tính X và Y.22
Hình 1.4: Sꢌ phân lꢈp mꢐt mꢞu mꢈi dꢌa trên mô hình cây quyꢆt ñꢋnh .........23
Hình 1.5 Cây quyꢆt ñꢋnh cuꢖi cùng cho CSDL T ñã nêu trong bꢄng 1.1.......29
Hình 1.6 Cây quyꢆt ñꢋnh ꢒ dꢓng giꢄ code cho CSDL T (bꢄng 1.1)...............29
Hình 1.7 Hꢛi qui tuyꢆn tính ............................................................................32
Hình 1.8 Gꢐp nhóm theo phương pháp k-means (ðiꢑm ñánh dꢜu + là tâm) 36
Hình 1.9 Phân hoꢓch vun ñꢖng hoꢘc tách dꢚn...............................................37
Hình 1.10 Bưꢈc lꢘp ñꢚu tiên cꢎa thuꢅt toán Apriori cho CSDL DB ..............41
Hình 1.11 Lꢚn lꢘp thꢃ 2 cꢎa thuꢅt toán Apriori cho CSDL DB .....................42
Hình 1.12 Lꢚn lꢘp thꢃ 3 cꢎa thuꢅt toán Apriori cho CSDL DB .....................42
Hình 2.1 Thuꢅt toán Apriori............................................................................46
Hình 2.2 Thuꢅt toán AprioriTid......................................................................50
Hình 2.3 Ví dꢍ................................................................................................51
Hình 2.4: Thꢟi gian thꢌc hiꢂn cho mꢕi lꢚn duyꢂt cꢎa Apriori và AprioriTid 52
Hình 2.5: Mꢐt ví dꢍ cꢎa cây phân cꢜp khái niꢂm cho khai phá các frequent
itemsets nhiꢠu mꢃc..........................................................................................55
Hình 2.6: FP-tree cho CSDL T trong bꢄng 2.1...............................................57
Hình 2.7 Thuꢅt toán PHP ................................................................................62
Hình 2.8 Bꢐ nhꢈ vꢈi 2 lꢚn duyꢂt cꢎa thuꢅt toán PCY ..................................63
Hình 2.9 Sꢏ dꢍng bꢐ nhꢈ cho các bꢄng băm nhiꢠu chꢘng.............................66
Hình 3.1 Công sꢃc cꢚn cho mꢕi giai ñoꢓn khai phá dꢁ liꢂu..........................82
Hình 3.2 Các bưꢈc khai phá luꢅt kꢆt hꢇp trên CSDL ngành Thuꢆ................83
Hình 3.3 Nhánh cây phân cꢜp ngành nghꢠ ....................................................85
Hình 3.4 Các luꢅt khai phá tꢡ ODM (ñꢐ dài luꢅt = 2)...................................87
7
Hình 3.5 Các luꢅt khai phá tꢡ ODM (ñꢐ dài luꢅt = 3)...................................89
Hình 3.6 Cây quyꢆt ñꢋnh dùng ODM – Bài toán phân tích tꢢ suꢜt................95
Hình 3.7 Cây quyꢆt ñꢋnh dùng See5 – Bài toán phân tích tꢢ suꢜt .................96
Hình 3.8 Cây quyꢆt ñꢋnh dùng ODM – Bài toán xét sꢖ liꢂu mꢐt năm...........99
Hình 3.9 Cây quyꢆt ñꢋnh dùng See5 – Bài toán phân tích trong năm.......... 100
8
Mꢇ ðꢈU
Thꢟi ñꢓi phát triꢑn mꢓnh cꢎa Internet, Intranet, Data warehouse, cùng
vꢈi sꢌ phát triꢑn nhanh vꢠ công nghꢂ lưu trꢁ ñã tꢓo ñiꢠu kiꢂn cho các doanh
nghiꢂp, các tꢀ chꢃc thu thꢅp và sꢒ hꢁu ñưꢇc khꢖi lưꢇng thông tin khꢀng lꢛ.
Hàng triꢂu CSDL ñã ñưꢇc dùng trong quꢄn trꢋ kinh doanh, quꢄn lý chính phꢎ,
quꢄn lý dꢁ liꢂu khoa hꢊc và nhiꢠu ꢃng dꢍng khác. Vꢈi khꢄ năng hꢕ trꢇ mꢓnh
cꢎa các Hꢂ quꢄn trꢋ CSDL, các CSDL này càng lꢈn lên nhanh chóng. Câu “Sꢌ
lꢈn mꢓnh cꢎa các CSDL dꢞn ñꢆn sꢌ cꢚn thiꢆt phꢄi có các kꢣ thuꢅt và các công
cꢍ mꢈi ñꢑ thꢌc hiꢂn chuyꢑn ñꢀi tꢌ ñꢐng dꢁ liꢂu mꢐt cách thông minh thành
thông tin và tri thꢃc hꢁu ích” [10] ñã trꢒ thành ñꢘt vꢜn ñꢠ cꢎa nhiꢠu bài viꢆt
vꢠ khai phá thông tin và tri thꢃc tꢡ các CSDL lꢈn.
Công tác trong ngành Thuꢆ, nơi Công nghꢂ thông tin ñưꢇc áp dꢍng vào
quꢄn lý Thuꢆ tꢡ nhꢁng năm 1986, CSDL thông tin liên quan ñꢆn các lĩnh vꢌc
quꢄn lý Thuꢆ là mꢐt CSDL lꢈn và chꢔc chꢔn tiꢠm ꢝn nhiꢠu thông tin quý báu.
Vꢈi mong muꢖn bưꢈc ñꢚu áp dꢍng kꢣ thuꢅt khai phá dꢁ liꢂu trên CSDL
ngành Thuꢆ, luꢅn văn ñã tꢅp trung nghiên cꢃu vꢠ các kꢣ thuꢅt khai phá dꢁ
liꢂu và tiꢆn hành khai phá thꢏ nghiꢂm trên CSDL ngành Thuꢆ.
Khꢄ năng mꢒ rꢐng tri thꢃc có ích ꢝn trong dꢁ liꢂu ñꢑ ñưa ra nhꢁng
hành ñꢐng cꢚn thiꢆt dꢌa trên tri thꢃc ñó ñang trꢒ nên ngày càng quan trꢊng
trong thꢆ giꢈi cꢓnh tranh hiꢂn nay. Toàn bꢐ quá trình dùng các phương pháp
luꢅn dꢌa trên tính toán, bao gꢛm các kꢣ thuꢅt mꢈi ñꢑ phát hiꢂn ra tri thꢃc tꢡ
dꢁ liꢂu ñưꢇc gꢊi là khai phá dꢁ liꢂu (data mining). [9]
Khai phá dꢁ liꢂu là sꢌ tìm kiꢆm thông tin mꢈi, có giá trꢋ và không tꢚm
thưꢟng trong mꢐt khꢖi lưꢇng dꢁ liꢂu lꢈn. Nó là sꢌ phꢖi hꢇp nꢕ lꢌc cꢎa con
ngưꢟi và máy tính. Các kꢆt quꢄ tꢖt nhꢜt nhꢅn ñưꢇc bꢉng viꢂc cân bꢉng giꢁa
9
tri thꢃc cꢎa các chuyên gia con ngưꢟi trong viꢂc mô tꢄ các vꢜn ñꢠ và mꢍc
ñích vꢈi khꢄ năng tìm kiꢆm cꢎa máy tính.
Hai mꢍc ñích chính cꢎa khai phá dꢁ liꢂu là ñꢑ dꢌ ñoán (prediction) và
mô tꢄ (description). Dꢌ ñoán bao gꢛm viꢂc dùng mꢐt vài biꢆn hoꢘc trưꢟng
trong tꢅp dꢁ liꢂu ñꢑ dꢌ ñoán các giá trꢋ tương lai hoꢘc chưa biꢆt cꢎa các biꢆn
cꢚn quan tâm. Còn mô tꢄ tꢅp trung vào viꢂc tìm ra các mꢞu mô tꢄ dꢁ liꢂu mà
con ngưꢟi có thꢑ hiꢑu ñưꢇc/ biên dꢋch ñưꢇc. Có thꢑ ñưa các hoꢓt ñꢐng khai
phá dꢁ liꢂu vào mꢐt trong hai loꢓi sau:
Khai phá dꢀ liꢁu dꢎ báo, tꢓo ra mô hình cꢎa hꢂ thꢖng ñưꢇc mô tꢄ
bꢒi tꢅp dꢁ liꢂu cho trưꢈc, hoꢘc
Khai phá dꢀ liꢁu mô tꢔ, vꢈi viꢂc tꢓo ra thông tin mꢈi, không tꢚm
thưꢟng dꢌa trên tꢅp dꢁ liꢂu có sꢤn.
Mꢐt sꢖ chꢃc năng khai phá dꢁ liꢂu chính như:
Mô tꢄ khái niꢂm: Mô tꢄ ñꢘc ñiꢑm và phân biꢂt. Tìm ra các ñꢘc ñiꢑm
khái quát hoá, tꢀng kꢆt, các ñꢘc ñiꢑm khác nhau trong dꢁ liꢂu.
Kꢆt hꢇp: xem xét vꢠ tương quan và quan hꢂ nhân quꢄ.
Phân lꢈp và dꢌ báo (Classification and Prediction): Xác ñꢋnh mô
hình mô tꢄ các lꢈp riêng biꢂt và dùng cho dꢌ ñoán tương lai.
Phân tích nhóm (Cluster analysis): Chưa biꢆt nhãn lꢈp, thꢌc hiꢂn
nhóm dꢁ liꢂu thành các lꢈp mꢈi dꢌa trên nguyên tꢔc cꢌc ñꢓi hoá sꢌ
tương tꢌ trong cùng lꢈp và cꢌc tiꢑu hoá sꢌ khác tương tꢌ giꢁa các
lꢈp khác nhau.
Phân tích nhiꢥu (Outlier analysis): Hꢁu ích trong viꢂc phát hiꢂn lꢕi,
phân tích các sꢌ kiꢂn hiꢆm.
Phân tích xu hưꢈng và sꢌ phát triꢑn
Khai phá dꢁ liꢂu là mꢐt trong nhꢁng lĩnh vꢌc phát triꢑn nhanh nhꢜt
trong công nghiꢂp máy tính. Tꢡ chꢕ là mꢐt miꢠn quan tâm nhꢦ trong khoa hꢊc
10
máy tính và thꢖng kê, nó ñã nhanh chóng mꢒ rꢐng thành mꢐt lĩnh vꢌc/ngành
cꢎa riêng nó. Mꢐt trong nhꢁng lꢈn mꢓnh nhꢜt cꢎa khai phá dꢁ liꢂu là sꢌ ꢄnh
hưꢒng trong phꢓm vi rꢐng cꢎa các phương pháp luꢅn và các kꢣ thuꢅt ñưꢇc
ꢃng dꢍng ñꢖi vꢈi mꢐt loꢓt các bài toán, các lĩnh vꢌc.
Trong kinh doanh, khai phá dꢁ liꢂu có thꢑ ñưꢇc dùng ñꢑ khám phá ra
nhꢁng xu hưꢈng mua sꢔm mꢈi, kꢆ hoꢓch cho các chiꢆn lưꢇc ñꢚu tư, và phát
hiꢂn nhꢁng sꢌ tiêu dùng không chính ñáng tꢡ hꢂ thꢖng kꢆ toán. Nó có thꢑ
giúp cꢄi tiꢆn các chiꢆn dꢋch marketing ñꢑ mang lꢓi nhiꢠu hꢕ trꢇ và quan tâm
hơn tꢈi khách hàng. Các kꢣ thuꢅt khai phá dꢁ liꢂu có thꢑ ñưꢇc áp dꢍng ñꢖi
vꢈi các bài toán thiꢆt kꢆ lꢓi quy trình kinh doanh, trong ñó mꢍc ñích là ñꢑ hiꢑu
ñưꢇc các tương tác và quan hꢂ trong thông lꢂ kinh doanh và các tꢀ chꢃc kinh
doanh.
Nhiꢠu ñơn vꢋ thi hành luꢅt, các ñơn vꢋ ñiꢠu tra ñꢘc biꢂt, có nhiꢂm vꢍ
tìm ra các hành ñꢐng không trung thꢌc và phát hiꢂn ra các xu hưꢈng phꢓm tꢐi,
cũng ñã sꢏ dꢍng khai phá dꢁ liꢂu mꢐt cách thành công. Các kꢣ thuꢅt khai phá
dꢁ liꢂu cũng có thꢑ ñưꢇc dùng trong các tꢀ chꢃc tình báo nơi lưu giꢁ nhiꢠu
nguꢛn dꢁ liꢂu lꢈn liên quan ñꢆn các hoꢓt ñꢐng, các vꢜn ñꢠ vꢠ an ninh quꢖc
gia.
Vꢈi mꢍc ñích nghiên cꢃu mꢐt sꢖ phương pháp khai phá dꢁ liꢂu và thꢏ
nghiꢂm khai phá trên CSDL ngành Thuꢆ, luꢅn văn ñưꢇc trình bày vꢈi các
phꢚn sau:
Chương 1 – Khai phá dꢁ liꢂu: Tìm hiꢑu các chꢃc năng khai phá dꢁ liꢂu.
Chương 2 – Mꢐt sꢖ thuꢅt toán khai phá dꢁ liꢂu. Nghiên cꢃu trên hai
kiꢑu khai phá: Khai phá luꢅt kꢆt hꢇp - mꢐt kꢣ thuꢅt thông dꢍng trong hꢊc
không giám sát. Phân lꢈp bꢉng hꢊc cây quyꢆt ñꢋnh - kꢣ thuꢅt hꢊc có giám sát.
Chương 3 – Áp dꢍng khai phá trên CSDL ngành Thuꢆ: Thꢏ nghiꢂm
khai phá luꢅt kꢆt hꢇp và phân lꢈp trên CSDL ngành Thuꢆ
11
Chương 4 – Kꢆt luꢅn và nhꢁng kꢆt quꢄ ñꢓt ñưꢇc
Cuꢖi cùng là mꢐt sꢖ hưꢈng nghiên cꢃu tiꢆp theo.
Em xin chân thành cꢄm ơn PGS. TS Nguyꢥn Ngꢊc Bình ñã hưꢈng dꢞn
và cho em nhꢁng ý kiꢆn quý báu, chân thành cꢄm ơn các thꢚy cô giáo cꢎa
trưꢟng ðꢓi hꢊc Bách khoa Hà Nꢐi ñã trang bꢋ kiꢆn thꢃc giúp em hoàn thành
luꢅn văn này.
12
CHƯƠNG 1. KHAI PHÁ Dꢂ LIꢁU
1.1. Tꢒng quan khai phá dꢏ liꢎu
Khai phá dꢁ liꢂu có nguꢛn gꢖc tꢡ các phương pháp riêng biꢂt, 2 dꢓng
quan trꢊng nhꢜt là thꢖng kê và hꢊc máy. Thꢖng kê có nguꢛn gꢖc tꢡ toán hꢊc
và do ñó nhꢜn mꢓnh ñꢆn ñꢐ chính xác toán hꢊc, mong muꢖn thiꢆt lꢅp cái mà
có thꢑ nhꢅn ra trên nꢠn toán hꢊc trưꢈc khi kiꢑm thꢏ nó trong thꢌc tꢆ. Ngưꢇc
lꢓi, hꢊc máy có nguꢛn gꢖc rꢜt nhiꢠu trong thꢌc tiꢥn tính toán. ðiꢠu này dꢞn
ñꢆn sꢌ hưꢈng thꢌc tiꢥn, sꢤn sàng kiꢑm thꢏ ñꢑ biꢆt nó thꢌc hiꢂn tꢖt thꢆ nào mà
không cꢚn chꢟ mꢐt chꢃng minh chính thꢃc. [9]
Có thꢑ có ñꢋnh nghĩa vꢠ Khai phá dꢁ liꢂu như sau: Khai phá dꢁ liꢂu là
quá trình phát hiꢂn các mô hình, các tꢀng kꢆt khác nhau và các giá trꢋ ñưꢇc
lꢜy tꢡ tꢅp dꢁ liꢂu cho trưꢈc. [9]
Hay, Khai phá dꢁ liꢂu là sꢌ thăm dò và phân tích lưꢇng dꢁ liꢂu lꢈn ñꢑ
khám phá tꢡ dꢁ liꢂu ra các mꢞu hꢇp lꢂ, mꢈi lꢓ, có ích và có thꢑ hiꢑu ñưꢇc
[14]. Hꢇp lꢂ là các mꢞu ñꢄm bꢄo tính tꢀng quát, mꢈi lꢓ là mꢞu chưa ñưꢇc biꢆt
trưꢈc ñó, có ích là có thꢑ dꢌa vào mꢞu ñó ñưa ra các hành ñꢐng phù hꢇp, hiꢑu
ñưꢇc là có thꢑ biên dꢋch và hiꢑu thꢜu ñáo các mꢞu.
Các kꢣ năng phân tích cꢎa con ngưꢟi là không ñꢚy ñꢎ do: Kích thưꢈc
và chiꢠu cꢎa dꢁ liꢂu; tꢖc ñꢐ tăng trưꢒng cꢎa dꢁ liꢂu là rꢜt lꢈn. Thêm vào ñó là
nhꢁng ñáp ꢃng mꢓnh mꢧ cꢎa kꢣ thuꢅt vꢠ khꢄ năng: thu thꢅp dꢁ liꢂu, lưu trꢁ,
năng lꢌc tính toán, phꢚn mꢠm, sꢌ thành thꢓo vꢠ chuyên môn. Ngoài ra còn có
môi trưꢟng cꢓnh tranh vꢠ dꢋch vꢍ, chꢃ không chꢗ cꢓnh tranh vꢠ giá (ñꢖi vꢈi
Ngân hàng, công ty ñiꢂn thoꢓi, khách sꢓn, công ty cho thuê …) vꢈi câu “Bí
quyꢆt cꢎa sꢌ thành công là biꢆt nhꢁng gì mà không ai khác biꢆt” (Aristotle
Onassis [14]). Tꢜt cꢄ nhꢁng ñiꢠu ñó chính là nhꢁng nguyên nhân thúc ñꢝy
Khai phá dꢁ liꢂu phát triꢑn.
13
Quá trình khám phá tri thꢀc:
Trưꢈc tiên, phân biꢂt giꢁa các thuꢅt ngꢁ “mô hình (model)” và “mꢞu
(pattern)” dùng trong khai phá dꢁ liꢂu. Mô hình là mꢐt cꢜu trúc “quy mô lꢈn”,
có thꢑ là tꢀng kꢆt các quan hꢂ qua nhiꢠu trưꢟng hꢇp (case) (ñôi khi là tꢜt cꢄ
các trưꢟng hꢇp), trong khi mꢞu là mꢐt cꢜu trúc cꢍc bꢐ, thoꢄ mãn bꢒi mꢐt sꢖ ít
trưꢟng hꢇp hoꢘc trong mꢐt miꢠn nhꢦ cꢎa không gian dꢁ liꢂu. Trong khai phá
dꢁ liꢂu, mꢐt mꢞu ñơn giꢄn là mꢐt mô hình cꢍc bꢐ.
Quá trình khám phá tri thꢃc tiꢆn hành theo các bưꢈc sau:
1. Xác ñꢋnh bài toán nghiꢂp vꢍ: Trưꢈc tiên phꢄi tìm hiꢑu lĩnh vꢌc cꢎa ꢃng
dꢍng nghiꢂp vꢍ; Tìm hiꢑu các tri thꢃc liên quan và các mꢍc ñích cꢎa ꢃng
dꢍng.
2. Khai phá dꢁ liꢂu
- Lꢌa chꢊn dꢁ liꢂu: Xác ñꢋnh các tꢅp dꢁ liꢂu ñích và các trưꢟng liên
quan
- Làm sꢓch dꢁ liꢂu: Xoá bꢦ nhiꢥu, tiꢠn xꢏ lý. Phꢚn viꢂc này có thꢑ
chiꢆm tꢈi 60% công sꢃc.
- Giꢄm bꢈt dꢁ liꢂu và chuyꢑn ñꢀi dꢁ liꢂu: Tìm ra nhꢁng ñꢘc trưng
hꢁu dꢍng, giꢄm bꢈt các chiꢠu hoꢘc các biꢆn, biꢑu diꢥn lꢓi các ñꢓi
lưꢇng bꢜt biꢆn
- Lꢌa chꢊn chꢃc năng khai phá dꢁ liꢂu: Tꢀng kꢆt, phân lꢈp, Hꢛi qui,
kꢆt hꢇp, phân nhóm.
- Lꢌa chꢊn thuꢅt toán khai phá.
- Thꢌc hiꢂn khai phá dꢁ liꢂu (Data Mining): Tìm kiꢆm các mꢞu quan
tâm
- ðánh giá các mꢞu và biꢑu diꢥn tri thꢃc
14
Hình 1.1 Quá trình khám phá tri thꢃc
3. Áp dꢍng khám phá tri thꢃc
4. ðánh giá và ño ñꢓc
5. Triꢑn khai và tích hꢇp vào các qui trình nghiꢂp vꢍ
1.1.1 Dꢏ liꢎu
Do có nhiꢠu kiꢑu dꢁ liꢂu, các CSDL sꢏ dꢍng trong các ꢃng dꢍng cũng
khác nhau, nên ngưꢟi dùng luôn mong ñꢇi mꢐt hꢂ thꢖng khai phá dꢁ liꢂu có
thꢑ ñiꢠu khiꢑn ñưꢇc tꢜt cꢄ các loꢓi dꢁ liꢂu. Thꢌc tꢆ CSDL có sꢤn thưꢟng là
CSDL quan hꢂ và hꢂ thꢖng khai phá dꢁ liꢂu cũng thꢌc hiꢂn hiꢂu quꢄ viꢂc khai
phá tri thꢃc trên dꢁ liꢂu quan hꢂ. Vꢈi nhꢁng CSDL cꢎa ꢃng dꢍng chꢃa các
kiꢑu dꢁ liꢂu phꢃc tꢓp, như dꢁ liꢂu hypertext và multimedia, dꢁ liꢂu tꢓm và
không gian (spatial), dꢁ liꢂu kꢆ thꢡa (legacy)… thưꢟng phꢄi có các hꢂ thꢖng
khai phá dꢁ liꢂu riêng biꢂt xây dꢌng ñꢑ khai phá cho các kiꢑu dꢁ liꢂu cꢍ thꢑ.
15
Dꢁ liꢂu ñưꢇc khai phá có thꢑ là dꢁ liꢂu có cꢜu trúc, hoꢘc không có cꢜu
trúc. Mꢕi bꢄn ghi dꢁ liꢂu ñưꢇc coi như mꢐt trưꢟng hꢇp hoꢘc mꢐt ví dꢍ
(case/example).
Phân biꢂt hai kiꢑu thuꢐc tính: phân loꢕi (categorical) và sꢓ
(numerical). Các thuꢐc tính kiꢑu phân loꢓi là nhꢁng thuꢐc tính có các giá trꢋ
thuꢐc vào mꢐt sꢖ lưꢇng nhꢦ các phân loꢓi hoꢘc các lꢈp riêng rꢧ và giꢁa chúng
không có thꢃ tꢌ ꢝn nào. Nꢆu chꢗ có 2 giá trꢋ, ví dꢍ là yes và no, hoꢘc male và
female, thuꢐc tính ñưꢇc coi là binary. Nꢆu có hơn 2 giá trꢋ, ví dꢍ, nhꢦ, vꢡa,
lꢈn, rꢜt lꢈn, thuꢐc tính ñưꢇc coi là ña lꢈp (multiclass).
Các thuꢐc tính sꢖ là nhꢁng thuꢐc tính lꢜy các giá trꢋ liên tꢍc, ví dꢍ, thu
nhꢅp hàng năm, hoꢘc tuꢀi. Thu nhꢅp hàng năm hoꢘc tuꢀi có thꢑ vꢠ lý thuyꢆt
là bꢜt kỳ mꢐt giá trꢋ nào tꢡ 0 tꢈi vô hꢓn, mꢘc dù mꢕi giá trꢋ thưꢟng xuꢜt hiꢂn
phù hꢇp vꢈi thꢌc tꢆ. Các thuꢐc tính sꢖ có thꢑ ñưꢇc biꢆn ñꢀi thành categorical:
Ví dꢍ, thu nhꢅp hàng năm có thꢑ ñưꢇc chia thành các loꢓi: thꢜp, trung bình,
cao.
Dꢁ liꢂu không có cꢜu trúc có thꢑ áp dꢍng các thuꢅt toán khai phá dꢁ
liꢂu thưꢟng là dꢁ liꢂu kiꢑu Text.
Khuôn dꢁng bꢂng cꢃa dꢄ liꢅu có thꢆ thuꢇc hai loꢁi:
Dꢁ liꢂu dꢓng ñơn bꢄn ghi (còn gꢊi là kiꢑu không giao dꢋch), ñây là
các bꢄng dꢁ liꢂu quan hꢂ thông thưꢟng.
Dꢁ liꢂu dꢓng ña bꢄn ghi (còn gꢊi là kiꢑu giao dꢋch), ñưꢇc dùng cho
dꢁ liꢂu vꢈi nhiꢠu thuꢐc tính.
ꢨ dꢓng ñơn bꢄn ghi (kiꢑu không giao dꢋch), mꢕi bꢄn ghi ñưꢇc lưu trꢁ
như 1 dòng trong bꢄng. Dꢁ liꢂu ñơn bꢄn ghi không ñòi hꢦi cung cꢜp khoá ñꢑ
xác ñꢋnh duy nhꢜt mꢕi bꢄn ghi. Nhưng, khoá là cꢚn cho các trưꢟng hꢇp kꢆt
hꢇp (associate) ñꢑ có kꢆt quꢄ cho hꢊc có giám sát.
16
Trong dꢓng ña bꢄn ghi (kiꢑu giao dꢋch), mꢕi trưꢟng hꢇp (case) ñưꢇc
lưu trong nhiꢠu bꢄn ghi trong mꢐt bꢄng vꢈi các cꢐt: dãy sꢖ ñꢋnh danh, tên
thuꢐc tính, giá trꢋ.
Hình 1.2 Khuôn dꢓng ñơn bꢄn ghi và ña bꢄn ghi
1.1.2 Tiꢓn xꢔ lý dꢏ liꢎu
Dꢁ liꢂu ñưꢇc chꢊn lꢊc sꢧ phꢄi qua bưꢈc tiꢠn xꢏ lý trưꢈc khi tiꢆn hành
khai phá phát hiꢂn tri thꢃc. Bưꢈc thu thꢅp và tiꢠn xꢏ lý dꢁ liꢂu là bưꢈc rꢜt
phꢃc tꢓp. ðꢑ mꢐt giꢄi thuꢅt DM thꢌc hiꢂn trên toàn bꢐ CSDL sꢧ rꢜt cꢛng
kꢠnh, kém hiꢂu quꢄ. Trong quá trình khai phá dꢁ liꢂu, nhiꢠu khi phꢄi thꢌc
hiꢂn liên kꢆt/tích hꢇp dꢁ liꢂu tꢡ rꢜt nhiꢠu nguꢛn khác nhau. Các hꢂ thꢖng sꢤn
có ñưꢇc thiꢆt kꢆ vꢈi nhꢁng mꢍc ñích và ñꢖi tưꢇng phꢍc vꢍ khác nhau, khi tꢅp
hꢇp dꢁ liꢂu tꢡ nhꢁng hꢂ thꢖng này ñꢑ phꢍc vꢍ khai phá dꢁ liꢂu, hiꢂn tưꢇng dư
thꢡa là rꢜt phꢀ biꢆn, ngoài ra còn có thꢑ xꢄy ra xung ñꢐt gây mꢜy dꢁ liꢂu, dꢁ
liꢂu không ñꢛng nhꢜt, không chính xác. Rõ ràng yêu cꢚu chꢊn lꢊc và làm sꢓch
dꢁ liꢂu là rꢜt cꢚn thiꢆt.
Nꢆu ñꢚu vào cꢎa quá trình khai phá là dꢁ liꢂu trong DW thì sꢧ rꢜt thuꢅn
tiꢂn, vì dꢁ liꢂu này ñã ñưꢇc làm sꢓch, nhꢜt quán và có tính chꢜt hưꢈng chꢎ ñꢑ.
17
Tuy nhiên nhiꢠu khi vꢞn phꢄi có thêm mꢐt sꢖ bưꢈc tiꢠn xꢏ lý ñꢑ ñưa dꢁ liꢂu
vꢠ ñúng dꢓng cꢚn thiꢆt.
Ngoài mꢐt sꢖ xꢏ lý thông thưꢟng như: biꢆn ñꢀi, tꢅp hꢇp dꢁ liꢂu tꢡ
nhiꢠu nguꢛn vꢠ mꢐt kho chung, xꢏ lý ñꢑ ñꢄm bꢄo nhꢜt quán dꢁ liꢂu (khꢏ các
trưꢟng hꢇp lꢘp, thꢖng nhꢜt cách ký hiꢂu, chuyꢑn ñꢀi vꢠ khuôn dꢓng thꢖng
nhꢜt (ñơn vꢋ tiꢠn tꢂ, ngày tháng..)). Mꢐt sꢖ xꢏ lý ñꢘc biꢂt cꢚn chú ý trong
bưꢈc tiꢠn xꢏ lý dꢁ liꢂu:
Xꢈ lý vꢉi dꢄ liꢅu thiꢊu (missing data): Thưꢟng thì khi khai phá dꢁ liꢂu
không ñòi hꢦi NSD phꢄi xꢏ lý các giá trꢋ thiꢆu bꢉng cách thꢃc ñꢘc biꢂt nào.
Khi khai phá, thuꢅt toán khai phá sꢧ bꢦ qua các giá trꢋ thiꢆu. Tuy nhiên trong
mꢐt vài trưꢟng hꢇp cꢚn chú ý ñꢑ ñꢄm bꢄo thuꢅt toán phân biꢂt ñưꢇc giꢁa giá
trꢋ có nghĩa (“0”) vꢈi giá trꢋ trꢖng. (tham khꢄo trong [11]).
Các giá trꢋ gây nhiꢌu (Outliers): Mꢐt outlier là mꢐt giá trꢋ ꢒ xa bên
ngoài cꢎa miꢠn thông thưꢟng trong tꢅp hꢇp dꢁ liꢂu, là giá trꢋ chênh lꢂch vꢈi
chuꢝn vꢠ ý nghĩa. Sꢌ có mꢘt cꢎa outliers có thꢑ có ꢄnh hưꢒng ñáng kꢑ trong
các mô hình khai phá dꢁ liꢂu.
Outliers ꢄnh hưꢒng ñꢆn khai phá dꢁ liꢂu trong bưꢈc tiꢠn xꢏ lý dꢁ liꢂu
hoꢘc là khi nó ñưꢇc thꢌc hiꢂn bꢒi NSD hoꢘc tꢌ ñꢐng trong khi xây dꢌng mô
hình.
Binning: Mꢐt vài thuꢅt toán khai phá dꢁ liꢂu có thꢑ có lꢇi nhꢟ viꢂc
binning vꢈi cꢄ hai loꢓi dꢁ liꢂu number và categorical. Các thuꢅt toán Naive
Bayes, Adaptive Bayes Network, Clustering, Attribute Importance, và
Association Rules có thꢑ có lꢇi tꢡ viꢂc binning.
Binning nghĩa là nhóm các giá trꢋ liên quan vꢈi nhau, như vꢅy giꢄm sꢖ
lưꢇng các giá trꢋ riêng biꢂt cꢎa mꢐt thuꢐc tính. Có ít hơn các giá trꢋ riêng biꢂt
dꢞn ñꢆn mô hình gꢊn nhꢩ và xây dꢌng ñưꢇc nhanh hơn, nhưng nó cũng có thꢑ
18
dꢞn ñꢆn viꢂc mꢜt ñi ñꢐ chính xác [11] (Các phương pháp tính toán ranh giꢈi
bin [11]).
1.1.3 Mô hình khai phá dꢏ liꢎu
Mô hình khai phá dꢁ liꢂu là mꢐt mô tꢄ vꢠ mꢐt khía cꢓnh cꢍ thꢑ cꢎa mꢐt
tꢅp dꢁ liꢂu. Nó tꢓo ra các giá trꢋ ñꢚu ra cho tꢅp các giá trꢋ ñꢚu vào.
Ví dꢍ: Mô hình Hꢛi qui tuyꢆn tính, mô hình phân lꢈp, mô hình phân
nhóm.
Mꢐt mô hình khai phá dꢁ liꢂu có thꢑ ñưꢇc mô tꢄ ꢒ 2 mꢃc:
Mꢃc chꢃc năng (Function level): Mô tꢄ mô hình bꢉng nhꢁng thuꢅt
ngꢁ vꢠ dꢌ ñꢋnh sꢏ dꢍng. Ví dꢍ: Phân lꢈp, phân nhóm.
Mꢃc biꢑu diꢥn (representation level): Biꢑu diꢥn cꢍ thꢑ mꢐt mô hình.
Ví dꢍ: Mô hình log-linear, cây phân lꢈp, phương pháp láng giꢠng
gꢚn nhꢜt.
Các mô hình khai phá dꢁ liꢂu dꢌa trên 2 kiꢑu hꢊc: có giám sát và không
giám sát (ñôi khi ñưꢇc nói ñꢆn như là hꢊc trꢌc tiꢆp và không trꢌc tiꢆp –
directed and undirected learning) [11].
Các hàm hꢊc có giám sát (Supervised learning functions) ñưꢇc sꢏ dꢍng
ñꢑ dꢌ ñoán giá trꢋ. Các hàm hꢊc không giám sát ñưꢇc dùng ñꢑ tìm ra cꢜu trúc
bên trong, các quan hꢂ hoꢘc tính giꢖng nhau trong nꢐi dung dꢁ liꢂu nhưng
không có lꢈp hay nhãn nào ñưꢇc gán ưu tiên. Ví dꢍ cꢎa các thuꢅt toán hꢊc
không giám sát gꢛm phân nhóm k-mean (k-mean clustering) và các luꢅt kꢆt
hꢇp Apriori. Mꢐt ví dꢍ cꢎa thuꢅt toán hꢊc có giám sát bao gꢛm Naive Bayes
cho phân lꢈp (classification).
Tương ꢃng có 2 loꢓi mô hình khai phá dꢁ liꢂu:
Các mô hình dꢌ báo (hꢊc có giám sát):
19
• Phân lꢈp: nhóm các items thành các lꢈp riêng biꢂt và dꢌ ñoán
mꢐt item sꢧ thuꢐc vào lꢈp nào.
• Hꢛi qui (Regression): xꢜp xꢗ hàm và dꢌ báo các giá trꢋ liên tꢍc
• ðꢐ quan trꢊng cꢎa thuꢐc tính: xác ñꢋnh các thuꢐc tính là quan
trꢊng nhꢜt trong các kꢆt quꢄ dꢌ báo
Các mô hình mô tꢄ (hꢊc không giám sát):
• Phân nhóm (Clustering): Tìm các nhóm tꢌ nhiên trong dꢁ liꢂu
• Các mô hình kꢆt hꢇp (Association models): Phân tích “giꢦ hàng”
• Trích chꢊn ñꢘc trưng (Feature extraction): Tꢓo các thuꢐc tính
(ñꢘc trưng) mꢈi như là kꢆt hꢇp cꢎa các thuꢐc tính ban ñꢚu
1.2. Các chꢕc n
ăng c
ơ
bꢖn khai phá dꢏ liꢎu
1.2.1 Phân lꢗp (Classification)
Trong bài toán phân lꢈp, ta có dꢁ liꢂu lꢋch sꢏ (các ví dꢍ ñưꢇc gán nhãn
- thuꢐc lꢈp nào) và các dꢁ liꢂu mꢈi chưa ñưꢇc gán nhãn. Mꢕi ví dꢍ ñưꢇc gán
nhãn bao gꢛm nhiꢠu thuꢐc tính dꢌ báo và mꢐt thuꢐc tính ñích (biꢆn phꢍ
thuꢐc). Giá trꢋ cꢎa thuꢐc tính ñích chính là nhãn cꢎa lꢈp. Các ví dꢍ không
ñưꢇc gán nhãn chꢗ bao gꢛm các thuꢐc tính dꢌ báo. Mꢍc ñích cꢎa viꢂc phân
lꢈp là xây dꢌng mô hình dꢌa vào dꢁ liꢂu lꢋch sꢏ ñꢑ dꢌ báo chính xác nhãn
(lꢈp) cꢎa các ví dꢍ không gán nhãn. [11]
Nhiꢂm vꢍ phân lꢈp bꢔt ñꢚu vꢈi viꢂc xây dꢌng dꢁ liꢂu (dꢁ liꢂu huꢜn
luyꢂn) có các giá trꢋ ñích (nhãn lꢈp) ñã biꢆt. Các thuꢅt toán phân lꢈp khác
nhau dùng các kꢣ thuꢅt khác nhau cho viꢂc tìm các quan hꢂ giꢁa các giá trꢋ
cꢎa thuꢐc tính dꢌ báo và các giá trꢋ cꢎa thuꢐc tính ñích trong dꢁ liꢂu huꢜn
luyꢂn. Nhꢁng quan hꢂ này ñưꢇc tꢀng kꢆt trong mô hình, sau ñó ñưꢇc dùng
20
cho các trưꢟng hꢇp mꢈi vꢈi các giá trꢋ ñích chưa biꢆt ñꢑ dꢌ ñoán các giá trꢋ
ñích.
Mô hình phân lꢈp có thꢑ ñưꢇc dùng trên bꢐ dꢁ liꢂu kiꢑm thꢏ/dꢁ liꢂu
ñánh giá vꢈi mꢍc ñích so sánh các giá trꢋ dꢌ báo vꢈi các câu trꢄ lꢟi ñã biꢆt.
Kꢣ thuꢅt này ñưꢇc gꢊi là kiꢑm tra mô hình, nó ño ñꢐ chính xác dꢌ báo cꢎa
mô hình.
Áp dꢍng mô hình phân lꢈp ñꢖi vꢈi dꢁ liꢂu mꢈi ñưꢇc gꢊi là sꢏ dꢍng mô
hình, và dꢁ liꢂu ñưꢇc gꢊi là dꢁ liꢂu sꢏ dꢍng hay dꢁ liꢂu trung tâm (apply data
or scoring data). Viꢂc sꢏ dꢍng dꢁ liꢂu thưꢟng ñưꢇc gꢊi là ‘scoring the data’.
Sꢌ phân lꢈp ñưꢇc dùng trong phân ñoꢓn khách hàng, phân tích tín
dꢍng, và nhiꢠu ꢃng dꢍng khác. Ví dꢍ, công ty thꢪ tín dꢍng muꢖn dꢌ báo
nhꢁng khách hàng nào sꢧ không trꢄ ñúng hꢓn trên các chi trꢄ cꢎa hꢊ. Mꢕi
khách hàng tương ꢃng vꢈi mꢐt trưꢟng hꢇp; dꢁ liꢂu cho mꢕi trưꢟng hꢇp có thꢑ
bao gꢛm mꢐt sꢖ thuꢐc tính mô tꢄ thói quen tiêu dùng cꢎa khách hàng, thu
nhꢅp, các thuꢐc tính nhân khꢝu hꢊc,… ðây là nhꢁng thuꢐc tính dꢌ báo.
Thuꢐc tính ñích chꢗ ra có hay không ngưꢟi khách hàng ñã vꢙ nꢇ/không trꢄ
ñúng hꢓn; như vꢅy, có hai lꢈp có khꢄ năng, tương ꢃng vꢈi vꢙ nꢇ hoꢘc không.
Dꢁ liꢂu huꢜn luyꢂn sꢧ ñưꢇc dùng ñꢑ xây dꢌng mô hình dùng cho dꢌ báo các
trưꢟng hꢇp mꢈi sau này (dꢌ báo khách hàng mꢈi có khꢄ năng chi trꢄ nꢇ
không).
Chi phí (Costs):
Trong bài toán phân lꢈp, có thꢑ cꢚn xác ñꢋnh chi phí bao hàm trong viꢂc
tꢓo ra mꢐt quyꢆt ñꢋnh sai lꢚm. Viꢂc này là quan trꢊng và cꢚn thiꢆt khi có
chênh lꢂch chi phí lꢈn giꢁa các phân lꢈp sai (misclassification). Ví dꢍ, bài
toán dꢌ báo có hay không mꢐt ngưꢟi sꢧ trꢄ lꢟi vꢈi thư quꢄng cáo. ðích có 2
phân loꢓi: YES (khách hàng trꢄ lꢟi) và NO (khách hàng không trꢄ lꢟi). Giꢄ sꢏ
trꢄ lꢟi tích cꢌc ñꢖi vꢈi quꢄng cáo sinh ra $500 và nó trꢋ giá $5 ñꢑ gꢏi thư. Nꢆu
21
mô hình dꢌ báo YES và giá trꢋ thꢌc tꢆ là YES, giá trꢋ cꢎa phân lꢈp sai là $0.
Nꢆu mô hình dꢌ báo YES và giá trꢋ thꢌc tꢆ là NO, giá trꢋ cꢎa phân lꢈp sai là
$5. Nꢆu mô hình dꢌ báo NO và giá trꢋ thꢌc tꢆ là YES, giá trꢋ cꢎa phân lꢈp sai
là $500. Nꢆu mô hình dꢌ báo NO và giá trꢋ thꢌc là NO, chi phí là $0.
Ma trꢅn chi phí, có chꢗ sꢖ hàng ương ꢃng vꢈi các giá trꢋ thꢌc; chꢗ sꢖ cꢐt
tương ꢃng vꢈi các giá trꢋ dꢌ báo. Vꢈi mꢕi cꢘp chꢗ sꢖ thꢌc-dꢌ báo, giá trꢋ cꢎa
ma trꢅn chꢗ ra chi phí cꢎa sꢌ phân lꢈp sai.
Mꢐt vài thuꢅt toán, như Adaptive Bayes Network, tꢖi ưu ma trꢅn chi
phí mꢐt cách trꢌc tiꢆp, sꢏa ñꢀi mô hình mꢍc ñích tꢓo ra các giꢄi pháp chi phí
cꢌc tiꢑu. Các thuꢅt toán khác, như Naive Bayes (dꢌ báo xác suꢜt), dùng ma
trꢅn chi phí trong khi tìm kꢆt quꢄ trên dꢁ liꢂu thꢅt ñꢑ ñưa ra giꢄi pháp chi phí
ít nhꢜt.
1.2.1.1 Phân lꢗp - mꢘt quá trình hai bưꢗc
Bưꢉc 1. Xây dꢍng mô hình (Hꢎc)
Xây dꢌng mô hình bꢉng cách phân tích tꢅp dꢁ liꢂu huꢜn luyꢂn, sꢏ dꢍng
các thuꢅt toán phân lꢈp và thꢑ hiꢂn mô hình theo luꢅt phân lꢈp, cây quyꢆt ñꢋnh
hoꢘc các công thꢃc toán hꢊc, mꢓng nơron…
Bưꢈc này còn ñưꢇc coi là bưꢈc tꢓo ra bꢐ phân lꢈp (classifier).
Bưꢉc 2. Sꢈ dꢏng mô hình (Phân lꢉp)
Áp dꢍng mô hình cho tꢅp dꢁ liꢂu kiꢑm thꢏ vꢈi các lꢈp ñã xác ñꢋnh ñꢑ
kiꢑm tra và ñánh giá ñꢐ chính xác cꢎa mô hình. Nꢆu ñꢐ chính xác là chꢜp
nhꢅn ñưꢇc, mô hình sꢧ ñưꢇc sꢏ dꢍng ñꢑ phân lꢈp cho các dꢁ liꢂu mꢈi.
Như vꢅy có 3 tꢅp dꢁ liꢂu có cꢜu trúc và các thuꢐc tính dꢌ ñoán giꢖng
nhau: Tꢅp huꢜn luyꢂn và tꢅp kiꢑm thꢏ ñã biꢆt lꢈp; Tꢅp mꢈi chưa xác ñꢋnh lꢈp.
22
1.2.1.2 Phân lꢗp bꢙng hꢚc cây quyꢐt ñꢛnh
Cây quyꢊt ñꢋnh
Phương pháp hiꢂu quꢄ ñꢘc biꢂt cho viꢂc tꢓo ra các bꢐ phân lꢈp tꢡ dꢁ
liꢂu là sinh ra cây quyꢆt ñꢋnh. Biꢑu diꢥn cꢎa cây quyꢆt ñꢋnh là phương pháp
logic ñưꢇc sꢏ dꢍng rꢐng rãi nhꢜt [9]. Mꢐt cây quyꢆt ñꢋnh bao gꢛm các nodes
mà ꢒ ñó các thuꢐc tính ñưꢇc kiꢑm tra (tested). Các nhánh ra cꢎa mꢐt node
tương ꢃng vꢈi tꢜt cꢄ các kꢆt quꢄ có thꢑ cꢎa viꢂc kiꢑm tra tꢓi node. Ví dꢍ, cây
quyꢆt ñꢋnh ñơn giꢄn cho viꢂc phân lꢈp các mꢞu vꢈi 2 thuꢐc tính ñꢚu vào X và
Y ñưꢇc cho trong hình 1.3. Tꢜt cꢄ các mꢞu vꢈi các giá trꢋ ñꢘc trưng X>1 và
Y=B thuꢐc vào Class2, trong khi các mꢞu vꢈi giá trꢋ X<1 ñꢠu thuꢐc vào
Class1, dù Y lꢜy bꢜt kỳ giá trꢋ nào.
Hình 1.3: Cây quyꢆt ñꢋnh ñơn giꢄn vꢈi các tests trên các thuꢐc tính X và Y
Phꢚn quan trꢊng nhꢜt cꢎa thuꢅt toán là quá trình sinh ra mꢐt cây quyꢆt
ñꢋnh khꢒi ñꢚu tꢡ tꢅp các mꢞu huꢜn luyꢂn. Kꢆt quꢄ, thuꢅt toán sinh ra mꢐt bꢐ
phân lꢈp ꢒ dꢓng cꢎa mꢐt cây quyꢆt ñꢋnh; Mꢐt cꢜu trúc vꢈi 2 kiꢑu nodes: Node
lá, ñꢑ chꢗ 1 lꢈp, hoꢘc mꢐt node quyꢆt ñꢋnh chꢗ ra kiꢑm tra ñưꢇc thꢌc hiꢂn trên
mꢐt giá trꢋ thuꢐc tính ñơn, vꢈi mꢐt nhánh và cây con cho mꢕi khꢄ năng ñꢚu ra
cꢎa kiꢑm tra.
23
Mꢐt cây quyꢆt ñꢋnh có thꢑ ñưꢇc dùng ñꢑ phân lꢈp mꢐt mꢞu mꢈi bꢉng
cách khꢒi ñꢚu tꢓi gꢖc cꢎa cây và di chuyꢑn qua nó ñꢆn khi gꢘp mꢐt lá. Tꢓi
mꢕi node quyꢆt ñꢋnh không là lá, ñꢚu ra vꢈi kiꢑm tra tꢓi node ñưꢇc xác ñꢋnh
và lꢌa chꢊn di chuyꢑn tꢈi gꢖc cꢎa cây con. Ví dꢍ, nꢆu mô hình phân lꢈp cꢎa
bài toán ñưꢇc cho vꢈi cây quyꢆt ñꢋnh trong hình 1.4.1 và mꢞu cho viꢂc phân
lꢈp trong hình 1.4.2, thì thuꢅt toán sꢧ tꢓo ñưꢟng ñi qua các nodes A, C, và F
(node lá) ñꢆn khi nó tꢓo quyꢆt ñꢋnh phân lꢈp cuꢖi cùng: CLASS2.
Hình 1.4: Sꢌ phân lꢈp mꢐt mꢞu mꢈi dꢌa trên mô hình cây quyꢆt ñꢋnh
Thuꢅt toán phát triꢑn cây (tree-growing) cho viꢂc sinh ra cây quyꢆt ñꢋnh
dꢌa trên các phân tách ñơn biꢆn là ID3 vꢈi phiên bꢄn mꢒ rꢐng là C4.5.
Giꢄ sꢏ có nhiꢂm vꢍ lꢌa chꢊn mꢐt kiꢑm tra vꢈi n ñꢚu ra (n giá trꢋ cho
mꢐt ñꢘc trưng ñã cho) mà chia tꢅp các mꢞu hꢊc T thành các tꢅp con T1, T2,
…, Tn. Thông tin dùng cho viꢂc hưꢈng dꢞn là sꢌ phân tán cꢎa các lꢈp trong T
và các tꢅp con Ti cꢎa nó. Nꢆu S là tꢅp bꢜt kỳ các mꢞu, gꢊi freq (Ci, S) biꢑu thꢋ
sꢖ lưꢇng các mꢞu trong S mà thuꢐc vào lꢈp Ci, và |S| biꢑu diꢥn sꢖ lưꢇng các
mꢞu trong tꢅp S.
Thuꢅt toán ID3 gꢖc dùng mꢐt tiêu chuꢝn ñưꢇc gꢊi là lꢇi ích (gain) ñꢑ
lꢌa chꢊn thuꢐc tính ñưꢇc kiꢑm tra, dꢌa trên khái niꢂn lý thuyꢆt thông tin:
entropy. Quan hꢂ sau ñây ñưa ra tính toán cꢎa entropy cꢎa tꢅp S:
24
k
k
Info(S) = - ∑ pi log2pi = - ∑ ((freq(Ci, S) / |S|) * log2 (freq(Ci, S) / |S|)
i=1
i=1
Xem xét tꢅp T sau khi ñưꢇc phân chia tương ꢃng vꢈi n ñꢚu ra cꢎa mꢐt
thuꢐc tính kiꢑm tra X. Yêu cꢚu vꢠ thông tin mong ñꢇi có thꢑ ñưꢇc tìm ra như
là tꢀng trꢊng sꢖ cꢎa các entropies trên các tꢅp con:
n
Infox(T) = - ∑ ((|Ti| / |T|) * Info(Ti))
i=1
ðꢌ ño lꢈi ích thông tin Gain: Mꢐt thuꢐc tính có lꢇi ích thông tin cao,
nghĩa là nꢆu biꢆt ñưꢇc các giá trꢋ cꢎa thuꢐc tính ñó thì viꢂc phân lꢈp sꢧ tiꢆn
gꢚn tꢈi ñích. Như ví dꢍ trên hình 1.3, nꢆu biꢆt X>1 thì biꢆt ñưꢇc ngay thuꢐc
lꢈp Class1. Gain cꢎa thuꢐc tính X ñưꢇc ño bꢉng ñꢐ giꢄm entropy trung bình
cꢎa tꢅp T sau khi ñã biꢆt giá trꢋ cꢎa X:
Gain(X) = Info(T) – Infox(T)
Ví dꢏ minh hoꢁ viꢅc áp dꢏng các phép ño khi tꢁo cây quyꢊt ñꢋnh:
Giꢄ sꢏ CSDL T vꢈi 14 trưꢟng hꢇp (ví dꢍ) ñưꢇc mô tꢄ vꢈi 3 thuꢐc tính
ñꢚu vào và thuꢐc vào 2 nhóm cho trưꢈc: CLASS1 hoꢘc CLASS2. CSDL cho
trưꢈc trong bꢄng 1.1
9 mꢞu thuꢐc vào CLASS1 và 5 mꢞu thuꢐc CLASS2, vꢅy entropy trưꢈc
khi phân tách là:
Info(T) = – 9/14 log2 (9/14) – 5/14 log2 (5/14) = 0.940 bits
Sau khi dùng Attribute1 ñꢑ chia tꢅp ban ñꢚu cꢎa các mꢞu T thành 3 tꢅp
con (kiꢑm tra x1 biꢑu diꢥn lꢌa chꢊn mꢐt trong 3 giá trꢋ A, B hoꢘc C), thông tin
kꢆt quꢄ ñưꢇc cho bꢒi:
Infox1 (T) = 5/14 ( – 2/5 log2 (2/5) – 3/5 log2 (3/5))
+ 4/14 ( – 4/4 log2 (4/4) – 0/4 log2 (0/4))
+ 5/14 ( – 3/5 log2 (3/5) – 2/5 log2 (2/5))
= 0.694 bits
25
Bꢄng 1.1: CSDL ñơn giꢄn gꢛm các ví dꢍ huꢜn luyꢂn
CSDL T:
Attribute1
Attribute2
70
Attribute3
True
Attribute4
CLASS1
CLASS2
CLASS2
CLASS2
CLASS1
CLASS1
CLASS1
CLASS1
CLASS1
CLASS2
CLASS2
CLASS1
CLASS1
CLASS1
A
A
A
A
A
B
B
B
B
C
C
C
C
C
90
True
85
False
False
False
True
95
70
90
78
False
True
65
75
False
True
80
70
True
80
False
False
False
80
96
Thông tin thu ñưꢇc bꢉng kiꢑm tra x1 này là:
Gain (x1) = 0.940 – 0.694 = 0.246 bits
Nꢆu kiꢑm tra và phân tách dꢌa trên Attribute3 (kiꢑm tra x2 biꢑn diꢥn
lꢌa chꢊn mꢐt trong 2 giá trꢋ True hoꢘc False), mꢐt tính toán tương tꢌ sꢧ cho
các kꢆt quꢄ mꢈi:
Infox2 (T) = 6/14 ( – 3/6 log2 (3/6) – 3/6 log2 (3/6))
+ 8/14 ( – 6/8 log2 (6/8) – 2/8 log2 (2/8))
= 0.892 bits
26
Và gain tương ꢃng là
Gain(x2) = 0.940 – 0.892 = 0.048 bits
Dꢌa trên ñiꢠu kiꢂn lꢇi ích (gain criterion), thuꢅt toán cây quyꢆt ñꢋnh sꢧ
lꢌa chꢊn kiꢑm tra x1 như mꢐt kiꢑm tra khꢒi ñꢚu cho viꢂc phân tách CSDL T
bꢒi vì giá trꢋ lꢇi ích cao hơn. ðꢑ tìm ra kiꢑm tra tꢖi ưu, cꢚn phꢄi phân tích
kiꢑm tra trên Attribute2, là mꢐt ñꢘc trưng sꢖ vꢈi các giá trꢋ liên tꢍc.
ꢨ trên ñã giꢄi thích kiꢑm tra chuꢝn cho các thuꢐc tính phân loꢓi. Dưꢈi
ñây sꢧ nêu thêm vꢠ thꢎ tꢍc cho viꢂt thiꢆt lꢅp các kiꢑm tra trên các thuꢐc tính
vꢈi các giá trꢋ sꢖ. Các kiꢑm tra trên các thuꢐc tính liên tꢍc sꢧ khó công thꢃc
hoá, vì nó chꢃa mꢐt ngưꢙng bꢜt kỳ cho viꢂc phân tách tꢜt cꢄ các giá trꢋ vào 2
khoꢄng.
Có mꢐt thuꢅt toán cho viꢂc tính toán giá trꢋ ngưꢙng tꢖi ưu Z. Các mꢞu
hꢊc ñꢚu tiên ñưꢇc sꢔp xꢆp trên các giá trꢋ cꢎa thuꢐc tính Y ñang ñưꢇc xem
xét. Chꢗ có mꢐt sꢖ có hꢓn cꢎa các giá trꢋ này, vì vꢅy ký hiꢂu chúng trong thꢃ
tꢌ ñã ñưꢇc sꢔp xꢆp là {v1, v2 …, vm}. Bꢜt kỳ giá trꢋ ngưꢙng nào nꢉm giꢁa vi
và vi+1 sꢧ có cùng hiꢂu quꢄ nꢆu ngưꢙng ñó chia các trưꢟng hꢇp thành nhꢁng
phꢚn mà giá trꢋ cꢎa thuꢐc tính Y cꢎa chúng nꢉm trong {v1, v2 …, vi} và trong
{vi+1, vi+2, …, vm}. Chꢗ có m-1 khꢄ năng trên Y, tꢜt cꢄ chúng cꢚn ñưꢇc kiꢑm
tra mꢐt cách có hꢂ thꢖng ñꢑ thu ñưꢇc mꢐt phân tách tꢖi ưu. Thưꢟng chꢊn
ngưꢙng là ñiꢑm giꢁa cꢎa mꢕi khoꢄng (vi + vi+1)/2.
Ví dꢍ minh hoꢓ quá trình tìm ngưꢙng này: Vꢈi CSDL T, phân tích các
khꢄ năng phân tách Attribute2. Sau khi sꢔp xꢆp, tꢅp các giá trꢋ cho Attribute2
là {65, 70, 75, 78, 80, 85, 90, 95, 96} và tꢅp các giá trꢋ ngưꢙng tiꢠm năng Z
là {65, 70, 75, 78, 80, 85, 90, 95}. Z tꢖi ưu (vꢈi thông tin lꢇi ích cao nhꢜt) cꢚn
ñưꢇc lꢌa chꢊn. Trong ví dꢍ này, giá trꢋ Z tꢖi ưu là Z = 80 và quá trình tính
toán thông tin lꢇi ích tương ꢃng cho kiꢑm tra x3 (Attribute2 ≤ 80 or Attribute2
> 80) như sau:
27
Infox3 (T) = 9/14 ( – 7/9 log2 (7/9) – 2/9 log2 (2/9))
+ 5/14 ( – 2/5 log2 (2/5) – 3/5 log2 (3/5))
= 0.837 bits
Gain(x3) = 0.940 – 0.837 = 0.103 bits
So sánh thông tin lꢇi ích cho 3 thuꢐc tính trong ví dꢍ, ta có thꢑ thꢜy
Attribute1 vꢞn cho lꢇi ích cao nhꢜt 0.246 bits và do ñó thuꢐc tính này sꢧ ñưꢇc
lꢌa chꢊn cho viꢂc phân tách ñꢚu tiên trong viꢂc xây dꢌng cây quyꢆt ñꢋnh. Nút
gꢖc sꢧ có kiꢑm tra cho các giá trꢋ cꢎa Attribute1, và 3 nhánh sꢧ ñưꢇc tꢓo, mꢕi
nhánh cho mꢐt giá trꢋ thuꢐc tính. Cây ban ñꢚu này vꢈi các tꢅp con tương ꢃng
cꢎa các mꢞu trong các nodes con ñưꢇc biꢑu diꢥn trong hình 1.5.
Hình 1.5 Cây quyꢆt ñꢋnh ban ñꢚu
và tꢅp con các trưꢟng hꢇp cho mꢐt CSDL trong bꢄng 1.1
Sau viꢂc phân tách ban ñꢚu, mꢕi node con có mꢐt vài mꢞu tꢡ CSDL,
và toàn bꢐ quá trình lꢌa chꢊn và tꢖi ưu kiꢑm tra sꢧ ñưꢇc lꢘp lꢓi cho mꢊi node
con. Bꢒi vì node con cho kiꢑm tra x1: Attribute1 = B có 4 trưꢟng hꢇp và tꢜt cꢄ
chúng là trong CLASS1, node này sꢧ là node lá, và không có các kiꢑm tra bꢀ
sung nào cꢚn cho nhánh này cꢎa cây.
28
Cho node con còn lꢓi, có 5 trưꢟng hꢇp trong tꢅp con T1, các kiꢑm tra
trên các thuꢐc tính còn lꢓi có thꢑ ñưꢇc thꢌc hiꢂn; mꢐt kiꢑm tra tꢖi ưu (vꢈi
thông tin có ích cꢌc ñꢓi) sꢧ là kiꢑm tra x4 vꢈi 2 lꢌa chꢊn: Attribute2 ≤ 70 or
Attribute2 > 70.
Info (T1) = – 2/15 log2 (2/5) – 3/15 log2 (3/5) = 0.940 bits
Dùng Attribute2 ñꢑ chia T1 thành 2 tꢅp con (kiꢑm tra x4 biꢑu diꢥn lꢌa
chꢊn cꢎa mꢐt trong 2 khoꢄng), thông tin kꢆt quꢄ ñưꢇc cho bꢒi:
Infox4 (T1) = 2/5 ( – 2/2 log2 (2/2) – 0/2 log2 (0/2))
+ 3/5 ( – 0/3 log2 (0/3) – 3/3 log2 (3/3))
= 0 bits
Gain thu ñưꢇc bꢒi test này là cꢌc ñꢓi:
Gain(x4) = 0.940 – 0 = 0.940 bits
Và 2 nhánh sꢧ tꢓo các node lá cuꢖi cùng vì các tꢅp con cꢎa các trưꢟng
hꢇp trong mꢕi nhánh thuꢐc vào cùng mꢐt class.
Tính toán tương tꢌ sꢧ ñưꢇc tiꢆn hành/tiꢆp tꢍc cho con thꢃ 3 cꢎa node
gꢖc. Cho tꢅp con T3 cꢎa CSDL T, kiꢑm tra x5 tꢖi ưu ñưꢇc chꢊn là viꢂc kiꢑm
tra trên các giá trꢋ cꢎa Attribute3. Các nhánh cꢎa cây, Attribute3 = True và
Attribute3 = False, sꢧ tꢓo các tꢅp con ñꢛng nhꢜt cꢎa các trưꢟng hꢇp mà thuꢐc
vào cùng mꢐt lꢈp. Cây quyꢆt ñꢋnh cuꢖi cùng cho CSDL T ñưꢇc biꢑu diꢥn
trong hình 1.5.
29
Hình 1.5 Cây quyꢆt ñꢋnh cuꢖi cùng cho CSDL T ñã nêu trong bꢄng 1.1
Tuỳ chꢊn, mꢐt cây quyꢆt ñꢋnh cũng có thꢑ ñưꢇc biꢑu diꢥn ꢒ dꢓng mꢐt
mã thꢌc hiꢂn (hoꢘc giꢄ mã) vꢈi các cꢜu trúc if-then cho viꢂc tách nhánh thành
mꢐt cꢜu trúc cây. Cây quyꢆt ñꢋnh cuꢖi cùng trong ví dꢍ trên ñưꢇc ñưa trong
giꢄ code như hình 1.6.
Hình 1.6 Cây quyꢆt ñꢋnh ꢒ dꢓng giꢄ code cho CSDL T (bꢄng 1.1)
30
1.2.1.3 Phân lꢗp Bayees
Phân lꢈp Bayees là phương pháp phân lꢈp thꢖng kê dꢌ ñoán xác suꢜt
các thành viên thuꢐc lꢈp. Phân lꢈp Bayees cho tính chính xác và tꢖc ñꢐ cao
khi áp dꢍng vào các CSDL lꢈn. Phương pháp Naive Bayees là mꢐt phương
pháp phân lꢈp Bayees ñơn giꢄn. Phương pháp này giꢄ thiꢆt ꢄnh hưꢒng cꢎa
mꢐt giá trꢋ thuꢐc tính tꢈi lꢈp là ñꢐc lꢅp vꢈi các giá trꢋ thuꢐc tính khác - gꢊi là
ñꢐc lꢅp ñiꢠu kiꢂn lꢈp.
Lý thuyꢊt Bayees
Cho X là dꢁ liꢂu ví dꢍ cꢎa mꢐt lꢈp chưa biꢆt. H là giꢄ thiꢆt X thuꢐc lꢈp
C. Bài toán phân lꢈp sꢧ xác ñꢋnh P(H|X) – là xác suꢜt giꢄ thuyꢆt H chꢃa ví dꢍ
X. ðó là xác suꢜt hꢅu nghiꢂm cꢎa H vꢈi ñiꢠu kiꢂn X.
Công thꢃc Bayees là:
P(H|X) = P(X|H) * P(H) / P(X)
(1.1)
Vꢈi P(X|H) là xác suꢜt hꢅu nghiꢂm cꢎa X vꢈi ñiꢠu kiꢂn H.
P(X) là xác suꢜt tiên nghiꢂm cꢎa X.
Phân lꢉp Naive Bayees
1. Mꢕi dꢁ liꢂu ví dꢍ ñưꢇc biꢑu diꢥn bꢉng mꢐt vecto X=(x1, .. xn) mô tꢄ n
ñꢐ ño cꢎa n thuꢐc tính A1,.., An.
2. Giꢄ sꢏ có m lꢈp C1,…, Cm. Cho mꢐt trưꢟng hꢇp X chưa biꢆt lꢈp, phân
lꢈp sꢧ dꢌ ñoán X thuꢐc vꢠ lꢈp Ci có xác suꢜt ñiꢂu kiꢂn X cao nhꢜt,
nghĩa là
X
⊂
Ci ꢀ P(Ci|X)>P(Cj | X)
∀
1<=j<=m j # i
Theo công thꢃc Bayees có: P(Ci|X) = P(X | Ci)P(Ci)/ P(X)
Trong ñó Ci ñưꢇc gꢊi là giꢄ thuyꢆt hꢅu nghiꢂm lꢈn nhꢜt.
3. Nꢆu P(X) là hꢉng chꢗ cꢚn tìm max P(X|Ci)P(Ci). Nꢆu xác suꢜt tiên
nghiꢂm chưa biꢆt và giꢄ sꢏ P(C1)=P(C2)... thì tìm Ci có max
P(X|Ci)P(Ci).
(1.2)
Tải về để xem bản đầy đủ
112 trang
20/04/2025
90
Bạn đang xem 30 trang mẫu của tài liệu "Luận văn Nghiên cứu và áp dụng một số kỹ thuật khai phá dữ liệu với cơ sơ sở dữ liệu ngành Thuế Việt Nam", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.
File đính kèm:
- luan_van_nghien_cuu_va_ap_dung_mot_so_ky_thuat_khai_pha_du_l.pdf
