Luận văn Khai mỏ dữ liệu và khám phá tri thức
Sựbùng nổthông tin ngày càng lan rộng và nhanh chóng, bên cạnh dữ liệu ngày càng gia tăng vềsố l ượng. Các nhà khoa học ñã nghiên cứu về kh ả năng sửdụng những dữliệu ấy ñểphục vụnhu cầu kinh doanh, học tập và nghiên cứu. Việc khai thác dữliệu dựa trên những dữliệu ñã tồn tại ñược gọi là khai phá dữliệu (Data mining). Quá trình khai phá dữliệu là bước ngoặc quan trọng cho quá trình khám phá tri thức từdữliệu (Knowledge Discovery in Databases). Dựa trên dữliệu vềkhai phá dữliệu và khám phá tri thức từdữliệu văn bản (text mining), luận văn ñi sâu vào việc tìm hiểu vềquá trình khai phá dữliệu bao gồm: tiền xử lý dữ liệu, các phương pháp khai phá dữ liệu làm nền tản, chương trình khai phá dữliệu, lập trình xửlý 1 sốthuật toán cơbản của phương pháp khai phá dữliệu bằng luật kết h ợp và cây quy ết ñịnh,. Tuy nhiên, ñềtài chưa ñi khai thác ñược hết các khía cạnh của khai phá dữ liệu từhình ảnh (Image mining), web (web mining), Các phương pháp khai phá dữliệu khác
Bạn đang xem trước 20 trang tài liệu Luận văn Khai mỏ dữ liệu và khám phá tri thức, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
TR Ư NG ð I H C TÂY ðÔ
KHOA K THU T CÔNG NGH
LU N V ĂN T T NGHI P ð I H C
KHAI M D LI U
VÀ KHÁM PHÁ TRI TH C
Sinh viên th c hi n: Cán b h ư ng d n:
H và tên: Quách Luyl ða Ths. D ươ ng V ăn Hi u
MSSV: 0751010009
L p: ð i h c Tin h c 2
C n Th ơ, 2011
TR Ư NG ð I H C TÂY ðÔ
KHOA K THU T CÔNG NGH
LU N V ĂN T T NGHI P ð I H C
KHAI M D LI U
VÀ KHÁM PHÁ TRI TH C
Sinh viên th c hi n Cán b h ư ng d n
H và tên: Quách Luyl ða Ths. D ươ ng V ăn Hi u
MSSV: 0751010009
L p: ð i h c Tin h c 2
Cán b ph n bi n
H c hàm, h c v , h và tên cán b ph n bi n
Lu n v ăn ñư c b o v t i: H i ñ ng ch m lu n v ăn t t nghi p B môn ……..
…………………….. ..…..Khoa K Thu t Công Ngh , Tr ư ng ð i h c Tây ðô vào
ngày .... tháng ..... n ăm ….
Mã s ñ tài:
Có th tìm hi u lu n v ăn t i:
• Th ư vi n: Tr ư ng ð i h c Tây ðô.
• Website:
L I CÁM ƠN
“ði kh p th gian không ai t t b ng M
Gánh n ng cu c ñ i không ai kh b ng Cha
Nư c bi n mênh mông không ñong ñ y tình M
Mây tr i l ng l ng không ph kín công Cha”
Khuy t danh Vi t Nam
ði kh p th gian không ai t t nh ư m , ch ăm lo cu c s ng cho con không ai b ng cha,
gánh n ng y cha m không nói ra, nh ưng tôi có th c m nh n và bi t ñư c qua mái tóc
b c c a m , nh ng gi t m hôi và làn da rám n ng c a cha. T t c nh ng vi c làm c a cha
m ch ñ cho gia ñình ñư c s ng vui v và h nh phúc, cho anh em tôi ñư c ăn h c nên
ng ư i. Gánh n ng y càng gia t ăng và n ng n h ơn trên vai cha và trong m t m khi con
bư c vào ng ư ng c a ñ i h c. V i bao lo l ng t cái ăn, cái m c, vi c h c hành càng làm
tăng gánh n ng cho cha m . Gánh n ng y không th th y ñư c trong ti ng c ư i c a cha,
trong ánh m t và ti ng nói c a m . Tôi xin g i l i cám ơn và k t qu h c t p trong nh ng
năm tháng h c xa nhà ñ làm món quà dâng t ng lên cha m c a tôi!
Tôi xin chân thành cám ơn quý th y cô trong ban giám hi u, các th y cô trong khoa
và các th y cô tr c ti p gi ng d y chúng tôi, và ñã cung c p cho chúng tôi ñư c nh ng
ki n th c, nh ng k n ăng c n thi t trong cu c s ng và chuyên môn. T ñó có th v n d ng
vào trong h c t p và quá trình nghiên c u. ð c bi t, tôi xin chân thành cám ơn th y D ươ ng
Văn Hi u, m c dù có nhi u khó kh ăn v m t ñ a lý và công vi c, nh ưng th y ñã t o m i
ñi u ki n ñ h ư ng d n chúng tôi hoàn thành khóa lu n này. Tôi xin chân thành cám ơn!
Kho ng th i gian theo h c t i tr ư ng, v i nh ng l l m khi v a b ư c vào môi
tr ư ng m i, v i nhi u b n m i. Chính nh ng ng ư i b n cùng ñ ng hành v i tôi trên b ư c
ñư ng ñ i h c, v i nh ng lý t ư ng và tính cách khác nhau. Chính nh ng câu chuy n bu n
– vui – gi n – ghét và chính nh ng s giúp ñ trong h c t p và công tác, các b n ñã giúp
tôi thêm tr ư ng thành h ơn, trao d i ñư c nhi u ki n th c h ơn t các b n. Tôi xin chân
thành cám ơn!
Và l i c m ơn sau cùng, xin chân thành cám ơn các anh ch , và c ũng là nh ng ng ư i
b n, các cô chú nhân viên tr ư ng ñã giúp ñ và quan tâm tôi trong su t th i gian theo h c
t i tr ư ng. Tôi xin chân thành cám ơn!
Xin chân thành cám ơn!
luyldaquach@gmail.com NGHIÊN C U KHAI M D LI U
VÀ KHÁM PHÁ TRI TH C
M C L C
L I CÁM ƠN
B NG KÝ HI U VÀ VI T T T
Ch ươ ng I : T NG QUAN ............................................................................................ 7
I.1. ð T V N ð .................................................................................................... 7
I.2. L CH S GI I QUY T V N ð ...................................................................... 7
I.3. PH M VI C A ð TÀI .................................................................................. 10
I.4. PH ƯƠ NG PHÁP NGHIÊN C U ..................................................................... 10
Ch ươ ng II : C Ơ S LÝ THUY T .............................................................................. 11
II.1. KHÁI NI M V KHAI PHÁ D LI U.......................................................... 11
II.1.1. Khái ni m: ................................................................................................ 11
II.1.2. Nhi m v c a khai thác d li u: ................................................................ 12
II.1.3. ng d ng c a khai phá d li u:................................................................. 14
II.2. CÁC KHÁI NI M C Ơ B N ........................................................................... 15
II.2.1. D li u và ki u d li u:............................................................................. 15
II.2.2. Ch t l ư ng c a d li u: ............................................................................. 19
II.3. Thu th p và ti n x lý d li u: ......................................................................... 23
II.3.1. T ng h p d li u:...................................................................................... 23
II.3.2. L y m u:................................................................................................... 24
II.3.3. Gi m b t thu c tính: ................................................................................. 25
II.3.4. L a ch n t p thu c tính con: ..................................................................... 26
II.3.5. T o ra thu c tính m i:............................................................................... 27
II.3.6. R i r c hóa và nh phân hóa: ..................................................................... 29
II.3.7. Chuy n ñ i thu c tính: .............................................................................. 30
II.4. M t s k thu t khai phá d li u:..................................................................... 30
II.4.1. Phân c m d li u (Cluster analysis): ......................................................... 30
II.4.2. H i quy (Regression): ............................................................................... 33
II.4.3. Cây quy t ñ nh (Decision tree):................................................................. 37
II.4.4. K – lân c n g n nh t: (K Nearest neighbour-KNN) ................................... 44
II.4.5. Gi i thu t di truy n: .................................................................................. 46
II.4.6. M ng neuron nhân t o (Neural networks):................................................. 50
II.4.7. Lu t k t h p (Association rule): ................................................................ 57
Ch ươ ng III : N I DUNG NGHIÊN C U................................................................... 67
III.1. NGHIÊN C U V PH N M M KHAI PHÁ D LI U ............................... 67
III.1.1. Gi i thi u Tanagra:.................................................................................. 67
III.1.2. Tìm hi u v Tanagra:............................................................................... 68
III.1.3. ng d ng Tanagra: .................................................................................. 81
III.2. CH ƯƠ NG TRÌNH NG D NG:................................................................... 83
III.2.1. Khai phá d li u b ng lu t k t h p:.......................................................... 83
III.2.2. Khai phá d li u b ng cây quy t ñ nh: ..................................................... 93
K T LU N VÀ KI N NGH
PH L C
Ph l c I: ðo kho ng cách gi a 2 ñ i t ư ng
Ph l c II: Thu t gi i Heuristic
Ph l c III: H ư ng d n s d ng ch ươ ng trình khai phá lu t k t h p
Ph l c IV: H ư ng d n s d ng ch ươ ng trình khai phá cây quy t ñ nh
TÀI LI U THAM KH O
SVTH: Quách Luyl ða Trang 4
luyldaquach@gmail.com NGHIÊN C U KHAI M D LI U
VÀ KHÁM PHÁ TRI TH C
B NG KÝ HI U VÀ VI T T T
T VI T
STT TI NG ANH NGH ĨA TI NG VI T
T T
01 ANN Artifical neural network M ng th n kinh nhân t o
02 AND, DNA Acid DeoxyriboNucleic Ph n t nucleotic a xít
03 GA Genetic Algorithm Gi i thu t di truy n
Giao di n ñ h a ng ư i
04 GUI Graphical user interface
dùng
05 Item Item Món hàng, m c,..
06 Itemset Itemset T p các m c, các hàng,…
07 KNN K Nearest neighbour K-lân c n g n nh t
Knowledge Discovery in
08 KDD Khám phá tri th c t d li u
Databases
09 RAM Ram memory B nh ram
Extensible Markup
10 XML Ngôn ng ñánh d u m r ng
Language
11 web website, web page Trang web
SVTH: Quách Luyl ða Trang 5
luyldaquach@gmail.com NGHIÊN C U KHAI M D LI U
VÀ KHÁM PHÁ TRI TH C
TÓM T T
S bùng n thông tin ngày càng lan r ng và nhanh chóng, bên c nh d
li u ngày càng gia t ăng v s l ư ng. Các nhà khoa h c ñã nghiên c u v kh
năng s d ng nh ng d li u y ñ ph c v nhu c u kinh doanh, h c t p và nghiên
c u. Vi c khai thác d li u d a trên nh ng d li u ñã t n t i ñư c g i là khai phá
d li u (Data mining). Quá trình khai phá d li u là b ư c ngo c quan tr ng cho
quá trình khám phá tri th c t d li u (Knowledge Discovery in Databases).
D a trên d li u v khai phá d li u và khám phá tri th c t d li u v ăn
b n (text mining), lu n v ăn ñi sâu vào vi c tìm hi u v quá trình khai phá d li u
bao g m: ti n x lý d li u, các ph ươ ng pháp khai phá d li u làm n n t n,
ch ươ ng trình khai phá d li u, l p trình x lý 1 s thu t toán c ơ b n c a ph ươ ng
pháp khai phá d li u b ng lu t k t h p và cây quy t ñ nh,..
Tuy nhiên, ñ tài ch ưa ñi khai thác ñư c h t các khía c nh c a khai phá d
li u t hình nh (Image mining), web (web mining),…Các ph ương pháp khai phá
d li u khác.
ABSTRACT
The explosion of information becomes more widely and quickly, besides
increasing the data quantity. Scientists have been studying the possibility of using
that data to serve the needs of business, learning and research activities. Mining
based on historical data is called data mining. The data mining process is an very
important landmark for the process of discovering knowledge from data.
In this study, we focus on understanding the data mining process including
data preprocessing, common data mining techniques, data-mining programs.
And, implementing the basic methods of data mining such as association rule
and decision tree, …
However, the topic is not going to exploit every aspect of data-mining from
image (Image mining), web (web mining), ... The data-mining methods other.
SVTH: Quách Luyl ða Trang 6
luyldaquach@gmail.com NGHIÊN C U KHAI M D LI U
VÀ KHÁM PHÁ TRI TH C
Ch ươ ng I : T NG QUAN
I.1. ð T V N ð
Ngày nay, công ngh thông tin ñã tr thành m t trong nh ng ñ ng l c quan
tr ng c a s phát tri n. V i kh n ăng s hóa m i thông tin (s , ñ th , v ăn b n,
hình nh, âm thanh, ti ng nói,…), máy tính ñã tr thành m t công c thông minh,
nó ñư c s d ng ñ x lý thông tin v i nhi u d ng thông tin thu c nhi u l ĩnh v c
khác nhau trong ñ i s ng nh ư: kinh doanh, y h c,…
Bên c nh ñó, cùng v i s phát tri n c a công ngh l ưu tr d li u ph c v
trong công vi c l ưu tr các thông tin liên quan ñ n nhi u m t c a cu c s ng: kinh
doanh, buôn bán, … ñã góp ph n c i thi n cu c s ng và làm gi m b t ñi vi c l ưu
tr thông tin d a trên v ăn b n.
ðó chính là ti n ñ cho s ra ñ i c a n n kinh t m i – n n kinh t s ( hay
có th g i là n n kinh t tri th c, n n kinh t d a trên tri th c). N n kinh t ñ y
ñã và ñang làm cho s phát tri n thông tin l ưu tr ngày càng nhi u, và kh n ăng
linh ho t c a các ph n m m ph i ñ m ñươ ng nhi u công vi c trong vi c l a ch n
thông tin. Và trong nh ng n ăm 1980, m t s nhà nghiên c u ñã ñư a m t s k
thu t nh m gi i quy t các v n ñ trên, và ñư c g i là k thu t khai phá d li u
(data mining).
Các k thu t khai phá d li u ñã ñư c các công ty kinh doanh các s n ph m
liên quan ñ n thông tin ñã ng d ng nh ư:
- Duy t web, tìm ki m các thông tin trên Google, Google luôn ñư a ra các
g i ý, có l b n s ngh ĩ: nó ñã ñ c ñư c nh ng suy ngh ĩ c a mình! Mà ña ph n
các g i ý ñ y g n nh ư là các thông tin mà b n c n tìm ki m. Vì sao Google bi t
mình c n tìm thông tin ñ y?
- Facebook, nh c ñ n Facebook b n s ngh ĩ ñ n m t c ng ñ ng v i s
lư ng thông tin cá nhân ñư c l ưu tr v i s l ư ng l n, ph i nói là r t l n. Khi
b n mu n k t b n trên c ng ñ ng y, Facebook luôn ñưa ra nh ng g i ý v
nh ng ng ư i b n cho b n k t b n. Và nh ng ng ư i b n y g n nh ư b n ñã quen
bi t ngoài cu c s ng ñ i th ư ng. B n ngh ĩ t i sao nó có th làm nh ư v y?
- M t ví d khác, ñó là vi c tìm và mua 1 quy n sách trên c a hàng sách
tr c tuy n kh ng l Amazon. Khi l a ch n m t quy n sách, nó luôn ñưa ra cho
b n các l a ch n v nh ng quy n sách mà 90% là b n c n mua. V y t i sao nó
hi u b n nhi u nh ư th ?
Và câu h i cu i cùng, vi c x lý thông tin c a nó ra sao? T t c nh ng câu
h i ñ y là m t ng d ng c th c a khai phá d li u và khám phá tri th c. V y
khai phá d li u là gì?
I.2. L CH S GI I QUY T V N ð
“ Data mining là quá trình th ăm dò, l a ch n và mô hình hóa kh i l ư ng
l n d li u ñ tìm ra nh ng quy lu t ho c các m i quan h ch ưa bi t ñ u tiên v i
m c ñích là ñ có ñư c k t qu rõ ràng và h u ích cho các ch s h u c a c ơ s
d li u.”
SVTH: Quách Luyl ða Trang 7
luyldaquach@gmail.com NGHIÊN C U KHAI M D LI U
VÀ KHÁM PHÁ TRI TH C
Qua quá trình phát tri n, ñ nh ngh ĩa v khai phá d li u ngày càng ñư c m
r ng, và d n d n hoàn thi n:
- Khai phá d li u là quá trình khám phá thông tin h u d ng trong các kho
d li u kh ng l m t cách t ñ ng. Các k thu t khai phá d li u ñư c tri n khai
d a trên các c ơ s d li u l n nh m tìm ki m các m u hay các quy lu t (pattern)
m i và h u d ng mà ch ưa t ng ñư c bi t tr ư c ñó. Ví d : “Nh ng sinh viên h c
gi i các môn Toán r i r c, L p trình, C u trúc d li u và C ơ s d li u thì s h c
gi i môn khai phá d li u”
- Khai phá d li u là quá trình tìm ki m các m u m i, nh ng thông tin, tri
th c có ích, ti m n và mang tính d ñoán trong kh i l ư ng d li u l n.
Các k thu t khai phá d li u c ũng cung c p các kh n ăng phán ñoán (d
ñoán) k t qu c a các quan sát trong hi n t i và quá kh . Khai phá d li u không
ch khám phá các thông tin h u d ng trong các c ơ s d li u (databases) hay kho
d li u (data respostories) mà còn liên quan ñ n các l ĩnh v c truy xu t thông tin
(information retrieval).
Ví d : S d ng h qu n tr c ơ s d li u ñ tìm ki m các m u tin ho c s
d ng các công c tìm ki m trên Internet ñ tìm ki m các trang web ho c thông
tin ñư c l ưu tr các trang web c th nào ñó.
Data mining là 1 ph n hoàn ch nh c a l ĩnh v c khám phá tri th c
(Knowledge Discovery). Nó là toàn b quá trình chuy n d li u thô sang thông
tin h u d ng. Quá trình này g m nhi u b ư c ti n x lý d li u ñ n h u x lý k t
qu c a quá trình khai phá.
Th ng kê
tóm t t
Xác Xác Thu Gi i
ñ nh th p và
ñ nh thu t M u
nhi m d ti n x khai
v li u lý d phá
liên li u
D li u
tr c ti p
Hình I-2. Quá trình khai phá d li u
Các khó kh ăn trong vi c khai thác tri th c t d li u:
a) Tính qui mô:
V i s phát tri n trong vi c t o ra d li u c ũng nh ư thu th p d li u, các t p
h p d li u ñu c l ưu tr ngày càng l n (gigabytes, terabytes,petabytes) và ngày
càng tr nên thông d ng. Các thu t toán khai phá d li u ph i có kh n ăng phân
tích ñư c các t p d li u ñó. Nhi u k thu t khai phá d li u tri n khai các chi n
lư c nghiên c u ñ c bi t nh m qu n lý các v n ñ trong nghiên c u t ăng theo c p
SVTH: Quách Luyl ða Trang 8
luyldaquach@gmail.com NGHIÊN C U KHAI M D LI U
VÀ KHÁM PHÁ TRI TH C
s nhân. Tính qui mô (scalability) yêu c u ph ươ ng pháp cài ñ t c a c u trúc d
li u m i nh m truy xu t ñư c các m u tin m t cách hi u qu .
Ví d : Các thu t toán “x lý d li u ngoài b nh (RAM)” (out-of-core) r t
c n thi t khi x lý các t p d li u l n h ơn dung l ư ng c a b nh . Tính qui mô
có th ñư c c i ti n b ng cách s d ng các d li u m u (samples), s d ng các
gi i thu t song song và phân tán.
b) Tính ña thu c tính:
X lý các t p d li u có hàng tr ăm hay hàng nghìn thu c tính ngày càng tr
nên ph bi n. Trong l ĩnh v c tin h c cho sinh h c, d li u v gen có th bao g m
hàng ngàn thu c tính. Các t p d li u v i các thành ph n d li u theo th i gian
hay còn ñư c g i là d li u tu n t (temporal/ spatial components) c ũng có xu
hư ng có r t nhi u thu c tính.
Ví d : T p d li u ch a các thông tin v ñ a ch t nhi u khu v c khác
nhau ñư c thu th p l p ñi l p l i nhi u l n, s l ư ng các thu c tính có th t ăng
d n theo th i gian. Các k thu t phân tích d li u truy n th ng ñư c thi t k cho
d li u có ít thu c tính không th áp d ng cho tr ư ng h p d li u có nhi u thu c
tính.
c) D li u không thu n nh t và ph c t p:
Các ph ươ ng pháp phân tích d li u truy n th ng áp d ng cho các t p h p
d li u ch a các thu c tính có cùng ki u d li u (có th là liên t c hay r i r c).
Khi vi c s d ng khai phá d li u trong kinh doanh, trong khoa h c và trong y
h c ngày càng t ăng thì c n có các k thu t phân tích d li u có th áp d ng ñư c
cho các thu c tính không thu n nh t (heterogeneous attributes). Bên c nh ñó,
cũng ph i áp d ng ñư c cho các d li u ph c t p.
Ví d : Các ki u d li u truy n th ng bao g m: t p h p các trang web l ưu
văn b n và liên k t bán c u trúc, các d li u v DNA trong không gian 3 chi u,
d li u v th i ti t (nhi t ñ , áp su t, ñ m) t i nhi u vùng trên th gi i. Các k
thu t ñư c phát tri n cho khai phá d li u c n ph i quan tâm ñ n m i quan h
trong d li u nh ư: m i quan h v nhi t ñ theo th i gian, s liên thông gi a các
ñ th , quan h gi a các thành ph n trong d li u bán c u trúc và XML.
d) S h u và phân b d li u:
Có khi d li u c n ñư c phân tích ñư c l ưu tr nhi u n ơi khác nhau và
ñư c s h u b i nhi u c ơ quan khác nhau. Các khó kh ăn này ñòi h i ph i phát
tri n các k thu t khai phá d li u theo d ng phân tán. V n ñ c n quan tâm là
“làm sao h n ch l ưu l ư ng truy n t i d li u khi th c hi n các thu t toán phân
tán?”, “làm sao h p nh t d li u t các ngu n g c khác nhau m t cách hi u qu
nh t?”, “làm sao ñ m b o tính an toàn và b o m t?”,…
e) Vi c phân tích d li u không theo cách truy n th ng:
Cách ti p c n d li u theo ph ươ ng pháp th ng kê truy n th ng d a trên
cách ñ t gi thuy t và ki m tra gi thuy t c n r t nhi u công s c ñ ki m tra các
gi thuy t. Các công vi c phân tích d li u hi n t i ñòi h i ph i ñ t và ki m tra
hàng nghìn gi ñ nh m t cách tu n t . Quá trình phát tri n các k thu t khai phá
d li u ñã ñư c thúc ñ y b i s mong ñ i m t quá
