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:
TRƯỜNG ðẠI HỌC TÂY ðÔ
KHOA KỸ THUẬT CÔNG NGHỆ
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
SVTH: Quách Luyl ða
Trang 4
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
luyldaquach@gmail.com
NGHIÊN CỨU KHAI MỎ DỮ LIỆU
VÀ KHÁM PHÁ TRI THỨC
SVTH: Quách Luyl ða
Trang 5
BẢNG KÝ HIỆU VÀ VIẾT TẮT
STT
TỪ VIẾT
TẮT
TIẾNG ANH
NGHĨA TIẾNG VIỆ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
04
GUI
Graphical user interface
Giao diện ñồ họa người
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
08
KDD
Knowledge Discovery in
Databases
Khám phá tri thức từ dữ liệu
09
RAM
Ram memory
Bộ nhớ ram
10
XML
Extensible Markup
Language
Ngôn ngữ ñánh dấu mở rộng
11
web
website, web page
Trang web
luyldaquach@gmail.com
NGHIÊN CỨU KHAI MỎ DỮ LIỆU
VÀ KHÁM PHÁ TRI THỨC
SVTH: Quách Luyl ða
Trang 6
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.
luyldaquach@gmail.com
NGHIÊN CỨU KHAI MỎ DỮ LIỆU
VÀ KHÁM PHÁ TRI THỨC
SVTH: Quách Luyl ða
Trang 7
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.”
luyldaquach@gmail.com
NGHIÊN CỨU KHAI MỎ DỮ LIỆU
VÀ KHÁM PHÁ TRI THỨC
SVTH: Quách Luyl ða
Trang 8
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á.
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
Xác
ñịnh
nhiệm
vụ
Xác
ñịnh
dữ
liệu
liên
Thu
thập và
tiền xử
lý dữ
liệu
Thống kê
tóm tắt
Dữ liệu
trực tiếp
Giải
thuật
khai
phá
Mẫu
Hình I-2. Quá trình khai phá dữ liệu
luyldaquach@gmail.com
NGHIÊN CỨU KHAI MỎ DỮ LIỆU
VÀ KHÁM PHÁ TRI THỨC
SVTH: Quách Luyl ða
Trang 9
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á trình ñặt và kiểm tra giả ñịnh
một cách hoàn toàn tự ñộng. Hơn nữa, dữ liệu ñược phân tích trong khai phá dữ
luyldaquach@gmail.com
NGHIÊN CỨU KHAI MỎ DỮ LIỆU
VÀ KHÁM PHÁ TRI THỨC
SVTH: Quách Luyl ða
Trang 10
liệu là dữ liệu ngẫu nhiên nên các phương pháp phân tích truyền thống không thể
áp dụng cho các tập dữ liệu phức tạp và mang tính ngẫu nhiên.
I.3. PHẠM VI CỦA ðỀ TÀI
ðề tài ñi sâu nghiên cứu về quá trình khai phá dữ liệu và khám phá tri thức
từ dữ liệu. Qua việc nghiên cứu có thể tìm hiểu thêm về các kỹ thuật cơ bản trong
việc tiền xử lý dữ liệu, các kỹ thuật khai phá dữ liệu cơ bản và từ ñó có ñược
những kiến thức trong việc tìm hiểu một công cụ khai phá dữ liệu, xây dựng
demo khai phá dữ liệu dựa trên một số thuật toán của cây quyết ñịnh và luật kết
hợp. Từ quá trình nghiên cứu và thực tiễn ñể có thể thấy ñược các vấn ñề thách
thức trong lĩnh vực khai phá dữ liệu.
Sử dụng cơ sở lý thuyết ñã nghiên cứu ñể cài ñặt chuơng trình sinh luật kết
hợp và cây quyết ñịnh là 2 kỹ thuật cơ bản của quá trình khai phá dữ liệu.
I.4. PHƯƠNG PHÁP NGHIÊN CỨU
Dựa trên việc tìm hiểu các tư liệu trong lĩnh vực khai phá dữ liệu, từ ñó rút
ra ñược những kết quả của quá trình tiền xử lý dữ liệu, một số kỹ thuật khai phá
dữ liệu cơ bản cùng với các thuật toán của nó. ðể có ñược những hiểu biết về quá
trình khai phá dữ liệu và khám phá tri thức.
Dựa trên quá trình tìm hiểu về khai phá dữ liệu, tiếp cận một công cụ khai
phá dữ liệu, ñể chứng minh cho các thuật toán và giải thuật ñã nghiên cứu.
Tổng hợp các dữ liệu ñã tìm hiểu, minh họa một thuật toán cơ bản trong
việc khai phá dữ liệu bằng cây quyết ñịnh và luật kết hợp bằng demo cụ thể.
Demo sử dụng ngôn ngữ lập trình Microsoft Visual Basic 2008 ñể xây dựng các
thuật toán.
luyldaquach@gmail.com
NGHIÊN CỨU KHAI MỎ DỮ LIỆU
VÀ KHÁM PHÁ TRI THỨC
SVTH: Quách Luyl ða
Trang 11
Chương II : CƠ SỞ LÝ THUYẾT
II.1. KHÁI NIỆM VỀ KHAI PHÁ DỮ LIỆU
II.1.1. Khái niệm:
Khai phá dữ liệu (Data mining) là một một bước trong quá trình khám phá
tri thức trong cơ sở dữ liệu (Knowledge Discovery in Databases – KDD).
Hình II-1. Quá trình khám phá tri thức trong cơ sở dữ liệu
Tại hội nghị quốc tế lần thứ nhất về Khám phá tri thức và Khai phá dữ liệu
(Knowledge Discovery and Data mining, ñược tổ chức ở Motreal vào năm 1995,
Usama Fayaad ñã ñưa ra khái niệm chính thức về Data mining. Nó ñược sử dụng
ñể chỉ một tập hợp các kỹ thuật phân tích ñược chia làm nhiều giai ñoạn khác
nhau, với mục tiêu kiến thức trước ñây chưa biết sẽ ñược suy luận từ kho dữ liệu
khổng lồ, mà dường như không có bất cứ một quy luật hoặc mối quan hệ rõ ràng
nào. Khi thuật ngữ “Data mining” từ từ ñược hình thành, nó ñã trở thành kiến
thức dành cho việc suy luận. ðiều này hết sức hữu ích vì ñã bác bỏ những khía
cạnh – mục ñích cuối cùng của khai khoáng dữ liệu còn mơ hồ trước ñó. Mục
tiêu của khai khoáng dữ liệu là thu ñược kết quả có thể ño bằng mức ñộ phù hợp
của dữ liệu cho các chủ sở hữu cơ sở dữ liệu–kinh doanh ñược thuận lợi.
Khai phá dữ liệu (Data mining) là một quá trình khám phá thông tin hữu
dụng trong 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 trên các cơ sở dữ liệu lớn nhằm tìm kiếm các mẫu hay các qui
luật (pattern) mới và hữu dụng mà chưa từng ñược biết trước ñó. Ví dụ: Người ta
thường mua ñường khi mua ñậu xanh, 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.
Các kỹ thuật khai phá dữ liệu cũng cung cấp khả năng phán ñoán (dự ñoán)
kết quả của các quan sát trong tương lai dựa vào dữ liệu hiện tại và quá khứ. Khai
phá dữ liệu không chỉ là 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 repositories) mà còn bao gồm các công việc
liên quan ñến lĩnh vực truy xuất thông tin (information retrieval).
Theo sơ ñồ Quá trình khám phá tri thức trong cơ sở dữ liệu (Hình II-1), ta
có một số khái niệm như sau:
luyldaquach@gmail.com
NGHIÊN CỨU KHAI MỎ DỮ LIỆU
VÀ KHÁM PHÁ TRI THỨC
SVTH: Quách Luyl ða
Trang 12
– Input Data: dữ liệu ñầu vào, nó có thể ñược lưu trữ với dưới nhiều ñịnh
dạng khác nhau (file text, file bảng tính, các bản quan hệ) và ñược lưu trữ trong
kho dữ liệu tập trung hoặc phân tán nhiều nơi khác nhau.
– Data Preprocessing: Quá trình tiền xử lý dữ liệu bao gồm phân rã (puse)
dữ liệu từ nhiều nguồn dữ liệu khác nhau, làm sạch (clean) dữ liệu bằng cách loại
bỏ nhiễu và dữ liệu trùng nhau, lựa chọn các mẫu tin (record) và các ñặc tính
(feature) có liên quan ñến quá trình khai thác (mine) dữ liệu. Trong thực tế, dữ
liệu có thể ñược thu nhập và lưu trữ bằng nhiều cách khác nhau nên quá trình tiền
xử lý dữ liệu là một quá trình hết sức quan trọng, khá nặng nhọc và tiêu tốn nhiều
thời gian cũng như công sức.
– Postproccessing: Hậu xử lý kết quả là quá trình loại bỏ các kết quả
không phù hợp hay lựa chọn các kết quả phù hợp với các công việc và nhu cầu
thực tế. Các kết quả sau bước hậu xử lý sẽ ñược sử dụng cho các hệ thống hỗ trợ
ra quyết ñịnh (Decision Support System).
II.1.2. Nhiệm vụ của khai thác dữ liệu:
Khai phá dữ liệu có 2 nhiệm vụ lớn là dự ñoán và mô tả:
II.1.2.1. Nhiệm vụ dự ñoán:
Mục ñích của nhiệm vụ dự ñoán là dự ñoán giá trị của một thuộc tính cụ thể
dựa trên giá trị của các thuộc tính khác. Thuộc tính ñược dự ñoán ñược gọi là
thuộc tính mục tiêu (target attributed) hay thuộc tính phụ thuộc (dependent
variables/ attributed), thuộc tính dùng ñể tạo dự ñoán gọi là thuộc tính mô tả hay
thuộc tính ñộc lập (explanatory/ Indepent variables).
Ví dụ: ðể quyết ñịnh việc cấp học bổng cho sinh viên ñại học và sau ñại
học, người ta có thể dựa vào rất nhiều yếu tố cũng như tiêu chí khác nhau. Một
trong những tiêu chí ñó là khả năng thành công trong học tập của người sẽ ñược
cấp học bổng. Làm thế nào ñể ước lượng ñược khả năng học tập của các ứng viên
xin học bổng? Người/ tổ chức cấp học bổng có thể sử dụng các thông tin về sinh
viên như: giới tính, ñộ tuổi, hoàn cảnh gia ñình, tình trạng hôn nhân, nghề
nghiệp.
II.1.2.2. Nhiệm vụ mô tả:
Mục ñích của nhiệm vụ mô tả là lấy ra từ các mẫu (pattern) mang tính mô tả
như: sự tương quan (correlation), xu hướng (trend), nhóm (cluster), ñường di
chuyển (trajectory) và ngoại lệ. Các mẫu này nói lên mối quan hệ giữa dữ liệu.
Nhiệm vụ của phần này thường là giải thích về mặt bản chất và thường yêu cầu
các kỹ thuật hậu xử lý (postproccessing) nhằm xác nhận (validate) và giải thích
(explain) các kết quả.
II.1.2.3. Nhiệm vụ trọng tâm của khai phá dữ liệu:
Nhiệm vụ trọng tâm của khai báo dữ liệu là: mô hình hóa cho việc dự báo,
phân tích và nhóm các ñối tượng dữ liệu thành từng nhóm dựa trên những thuộc
tính của chúng, phân tích và ñưa ra các luật kết hợp dựa trên các dữ liệu hiện tại,
phân tích và phát hiện các trường hợp ngoại lệ. Bốn nhiệm vụ ấy có thể ñược mô
tả ngắn gọn như sau:
luyldaquach@gmail.com
NGHIÊN CỨU KHAI MỎ DỮ LIỆU
VÀ KHÁM PHÁ TRI THỨC
SVTH: Quách Luyl ða
Trang 13
a) Mô hình hóa cho việc dự báo:
Nhiệm vụ chính là xây dựng mô hình cho thuộc tính cần ñược dự ñoán giá
trị (target variable) như là một hàm của các biến ñộc lập (independent variable)
ñược dùng ñể ñoán giá trị cho target variable. Có hai kiểu mô hình dự báo
(predictive modeling), ñó là: phân lớp dữ liệu (classification analysis) và hồi quy
(regression). Sự phân lớp dữ liệu ñược sử dụng cho các thuộc tính target có giá
trị rời rạc. Sự hồi quy ñược sử dụng cho các thuộc tính target có giá trị liên tục.
Ví dụ 1: Dự ñoán một người dùng Internet sẽ mua hàng trực tuyến hay
không thì phải sử dụng phương pháp phân lớp vì giá trị của thuộc tính target rời
rạc (“mua” và “không”).
Ví dụ 2: Dự ñoán giá cổ phiếu trong tương lai thì phải sử dụng phương pháp
regession vì giá trị của cổ phiếu là giá trị liên tục.
Mục ñích của cả phân lớp và hồi quy là tìm ra mô hình ñể dự ñoán giá trị
của một thuộc tính dựa trên các thuộc tính khác sao cho tối thiểu quá sai khác
giữa các dự ñoán và giá trị thực tế.
b) Phân tích kết hợp:
Phân tích kết hợp dùng ñể khám phá các mẫu (pattern) mà các mẫu này mô
tả một cách mạnh mẽ các mối quan hệ giữa các ñặc ñiểm của dữ liệu. Các mẫu
qui luật ñược khám phá thông thường ñược biểu diễn bằng luật kết hợp. Bởi vì
kích thước của không gian tìm kiếm tăng lên theo cấp số nhân nên mục ñích
chính của phương pháp phân tích kết hợp là kết xuất các mẫu có ý nghĩa bằng
cách làm hiệu quả hay nói cách khác là phải “loại bỏ các luật có giá trị sử dụng
ít”.
Ví dụ: Xét các giao dịch tại một cửa hàng như bảng bên dưới:
Hình II-2. Bốn nhiệm vụ trọng tâm của khai phá dữ liệu
luyldaquach@gmail.com
NGHIÊN CỨU KHAI MỎ DỮ LIỆU
VÀ KHÁM PHÁ TRI THỨC
SVTH: Quách Luyl ða
Trang 14
Hình II-3. Một số giao dịch tại cửa hàng
Phân tích lớp dữ liệu có thể ñược dùng ñể phân tích và tìm các mặt hàng
ñược mua cùng với nhau ñể “bố trí các mặt hàng sao cho khách hàng mua hàng
thuận tiện nhất”.
c) Phân tích nhóm:
Phương pháp phân tích nhóm dùng ñể tìm các nhóm (groups) của các giá trị
quan sát ñược (observations) có liên quan ñến nhau. Các giá trị quan sát cùng
một nhóm chắc chắn sẽ giống nhau nhiều hơn so với các giá trị ở các nhóm khác
nhau.
Ví dụ: phân nhóm khách hàng ñể tìm ra các khách hàng có cùng sở thích
mua sắm.
d) Phát hiện ngoại lệ:
Phát hiện các ngoại lệ là tìm các quan sát mà chúng khác rất nhiều so với
các giá trị khác. Các giá trị khác biệt so với các giá trị khác ñược gọi là ngoại lệ
(anomaly, outlier).
Ví dụ: Ứng dụng phương pháp phát hiện ngoại lệ ñể tìm các giao dịch “bất
thường” trong lĩnh vực ngân hàng như: rửa tiền, gian lận khác trong giao dịch.
II.1.3. Ứng dụng của khai phá dữ liệu:
Từ khi ra ñời, khai phá dữ liệu ñược ứng dụng rộng rãi, sau ñây là một số
ứng dụng cụ thể:
a) Thiên văn học: Xác ñịnh vị trí và hướng di chuyển của các chòm sao, các
hành tinh trong hệ mặt trời dựa trên những dữ liệu về hướng di chuyển, lịch sử
phát triển của nó,…
b) Phát hiện gian lận: Dựa trên những doanh thu, tài khoản phải thu, thu thập
những dữ liệu hiệu quả biên của biên chế gian lận, kiểm toán tự ñộng hoặc các kỹ
thuật ñể phát hiện gian lận, sử dụng dữ liệu phân tích kết quả ñể kiểm soát biên
chế phòng ngừa gian lận,…
c) Quản lý quan hệ bán hàng: Lưu trữ thông tin khách hàng, phân loại khách
hàng, các thông tin mua hàng,…từ ñó ñưa ra các chiến lược, phương pháp kinh
doanh mới nhằm mục ñích:
– Khách hàng có lợi và những ñặc ñiểm nào làm cho họ như vậy.
luyldaquach@gmail.com
NGHIÊN CỨU KHAI MỎ DỮ LIỆU
VÀ KHÁM PHÁ TRI THỨC
SVTH: Quách Luyl ða
Trang 15
– Thay ñổi trong hành vi mua của khách hàng – hoặc là một cơ hội hay ñe
dọa ñối với kinh doanh.
–
Những khoảng trống trong danh mục sản phẩm – cho biết qua việc bán,
số lượng bán sản phẩm tăng, và lặp lại các lần mua hàng,..
–
Những mặt hàng nào bố trí thuận lợi và tiện dụng cho khách hàng,..
d) Chăm sóc sức khỏe: Lưu trữ thông tin các bệnh, các hiện tượng, triệu
chứng,…từ ñó, dựa trên những thông tin ấy ñể phát hiện các bệnh và hướng ñiều
trị cụ thể ñối với các bệnh ñã ñược phát hiện.
e) Nông nghiệp: Tìm kiếm các thông tin về rầy nâu, hướng di chuyển, lịch sử
phát triển,… ñể ñưa ra các biện pháp phòng và tránh rầy nâu phá hoại mùa màng.
f) Giáo dục: Dựa trên những thông tin về tập quán, nơi cư trú, ñiều kiện của
xã hội, tính cách,…ñể ñưa ra những ñịnh hướng trong việc lựa chọn nghề nghiệp
cho học sinh vừa tốt nghiệp phổ thông ñể có hướng lựa chọn nghề nghiệp hợp
lý,…
II.2. CÁC KHÁI NIỆM CƠ BẢN
II.2.1. Dữ liệu và kiểu dữ liệu:
Dữ liệu là phần tử hoặc tập hợp các phần tử mà ta gọi là tín hiệu. Nó ñược
biểu hiện dưới các dạng như hình ảnh, âm thanh, màu sắc, mùi vị,…Từ những tín
hiệu ñó, chúng ta có sự hiểu biết về một sự vật, hiện tượng hay quá trình nào ñó
trong thế giới khách quan thông qua quá trình nhận thức.
Một tập hợp dữ liệu có thể ñược xem như một tập hợp các ñối tượng dữ
liệu. Các ñối tượng dữ liệu có thể là mẫu tin (record), ñiểm (point), véc tơ
(vector), mẫu (pattern), sự kiện (event), trường hợp (case), dữ liệu mẫu (sample),
các thực thể (entity) và các kết quả quan sát (observation). ðối tượng dữ liệu
ñược mô tả bằng các thuộc tính (attribute) mà các thuộc tính này nói lên tính chất
/ ñặc ñiểm cơ bản của ñối tượng dữ liệu. Trong ngữ cảnh khai phá dữ liệu, thuộc
tính ñược gọi với những tên khác nhau như: Biến (variable), ñặc trưng
(characteristis), trường dữ liệu (field), tính năng (feature), kích thước
(dimension).
II.2.1.1. Thuộc tính và phép ño:
a) ðịnh nghĩa thuộc tính:
Thuộc tính là tính chất của một ñối tượng mà giá trị của nó có thể khác
nhau tùy vào từng ñối tượng cụ thể.
Ví dụ: màu mắt, cân nặng, chiều cao là thuộc tính của con người, tùy vào
từng người sẽ có giá trị khác nhau.
b) Phép tính ñộ ño:
Phép tính ñộ ño là một quy tắc (rule) hay một hàm (function) dùng ñể kết
hợp một giá trị hoặc một ký hiệu với một thuộc tính của ñối tượng, nhằm làm rõ
tính chất của ñối tượng.
Ví dụ: Xác ñịnh cân nặng bằng kg, chiều dài bằng mét, giới tính là nam hay
nữ, số ghế trong phòng học là ñủ hay thiếu,…
c) Kiểu của thuộc tính:
luyldaquach@gmail.com
NGHIÊN CỨU KHAI MỎ DỮ LIỆU
VÀ KHÁM PHÁ TRI THỨC
SVTH: Quách Luyl ða
Trang 16
STT
Kiểu thuộc tính
(Attributed type)
Mô tả
Ví dụ
1
ðịnh danh
(nominal)
Giá trị của thuộc tính kiểu
nominal là các tên gọi hay ñịnh
danh khác nhau, chỉ cung cấp
vừa ñủ thông tin ñể phân biệt
giống nhau hay khác nhau
(=, ≠).
Mã
tỉnh,
mã
nhân viên, giới
tính,..
2
Thứ tự
(ordinal)
Giá trị thuộc tính kiểu ordinal
cung cấp ñầy ñủ thông tin ñể
phân biệt (=, ≠) và so sánh theo
thứ tự (<, <=,>,>=).
Cao, cao hơn,
cao nhất,…
3
Khoảng cách
(interval)
ðối với thuộc tính kiểu interval,
ngoài phân biệt cung cấp ñầy ñủ
thông tin ñể phân biệt(=, ≠), so
sánh (<, <=,>,>=), sự khác nhau
(+,-) giữa các giá trị là hết sức
quan trọng.
Ngày
tháng
năm
ðộ C hoặc ñộ F
4
Tỷ lệ
(ratio)
ðối với thuộc tính kiểu ratio, sự
khác nhau (+,-) và tỉ lệ (*,/)
giữa các giá trị là hết sức quan
trọng
Số lượng, ñộ
dài, tuổi,…
Trong ñó, thuộc tính kiểu ñịnh danh và thứ tự ñược coi như thuộc tính
dùng ñể phân biệt/ phân loại hay thuộc tính ñịnh danh. Thuộc tính kiểu khoảng
cách và tỉ lệ ñược xem như là thuộc tính ñịnh lượng hay thuộc tính kiểu số.
d) Mô tả thuộc tính bằng tập hợp các giá trị:
Bằng cách dựa vào số lượng và giá trị mà thuộc tính có thể có, chúng ta có
thể chia làm 3 loại thuộc tính:
– Thuộc tính nhị phân: có 2 giá trị. Thường ñược sử dụng với thuộc tính
kiểu nhị phân, kiểu yes/no. Ví dụ: 0 và 1.
– Thuộc tính rời rạc là thuộc tính có một tập hợp hữu hạn các giá trị, có
nhiều hơn 2 giá trị. Thường ñược sử dụng với thuộc tính kiểu số nguyên, kiểu ký
tự, kiểu chuỗi ký tự. Ví dụ: mã tỉnh, số ñiện thoại, giới tính, số chứng minh nhân
dân,…
– Thuộc tính liên tục: là thuộc tính có một tập vô hạn các giá trị liên tục
hay có giá trị là các số thực, có vô hạn các giá trị. Thuộc tính liên tục thường
ñược sử dụng là thuộc tính kiểu số thực hay số có dấu chấm ñộng.
II.2.1.2. Kiểu của tập dữ liệu:
Có rất nhiều kiểu dữ liệu ñược sử dụng trong lĩnh vực khai phá dữ liệu khi
có càng nhiều các tập dữ liệu ñược sử dụng ñể phân tích. Kiểu dữ liệu có thể
ñược chia ra làm 3 nhóm lớn:
o Dữ liệu mẫu tin (record data).
luyldaquach@gmail.com
NGHIÊN CỨU KHAI MỎ DỮ LIỆU
VÀ KHÁM PHÁ TRI THỨC
SVTH: Quách Luyl ða
Trang 17
o Dữ liệu trên cơ sở ñồ thị (graph-based data).
o Dữ liệu có thứ tự (ordered data).
a) Tính chất tổng quát của các tập dữ liệu: Có 3 tính chất quan trọng ảnh
hưởng ñến việc lựa chọn và sử dụng các kỹ thuật khai phá dữ liệu là:
– Số chiều (dimensionality): Số chiều của 1 tập hợp dữ liệu là số lượng
các thuộc tính mà các ñối tượng trong tập dữ liệu ñó sở hữu. Một trong những
thách thức của lĩnh vực khai phá là dữ liệu có nhiều thuộc tính.
– Sự thưa thớt (sparsity): ðối với một số tập hợp như các thuộc tính không
ñối xứng. Hầu hết các thuộc tính của các ñối tượng có giá trị 0 nhưng chỉ một số
trường hợp không có giá trị 0. Trong thực tế, ñây là một thuận lợi vì chỉ cần lưu
trữ và thao tác trên các giá trị khác 0. Cách làm này sẽ làm giảm thời gian tính
toán cũng như bộ nhớ lưu trữ.
– ðộ phân giải (resolution): Trong khai phá dữ liệu, ñộ phân giải dữ liệu
thường ở nhiều mức ñộ khác nhau và tính chất của dữ liệu cũng khác nhau tùy
vào mức ñộ phân giải. Mẫu trong dữ liệu thường phụ thuộc nhiều vào mức ñộ
phân giải. Ví dụ: ðộ phân giải quá mịn thì mẫu sẽ bị mờ, ñộ phân giải quá thô thì
mẫu sẽ mất.
b) Chi tiết về các kiểu dữ liệu trong khai phá dữ liệu:
Dữ liệu dạng mẫu tin:
Hầu hết các trường hợp dữ liệu của khai phá dữ liệu là dạng mẫu tin (record
data). Mỗi mẫu tin là một ñối tượng dữ liệu bao gồm một tập hợp các thuộc tính.
Các mẫu tin có thể ñược lưu trong các tập tin phẳng (flat files) hoặc lưu trong các
bảng dữ liệu (table) trong cơ sở dữ liệu quan hệ. Dữ liệu dạng mẫu tin có thể là
các bảng ghi trong cơ sở , giao dịch (transaction), ma trận dữ liệu (data matrix)
và ma trận thuật ngữ trong văn bản (document – term matrix).
b) Ma trận dữ liệu
a) Dữ liệu mẫu tin
luyldaquach@gmail.com
NGHIÊN CỨU KHAI MỎ DỮ LIỆU
VÀ KHÁM PHÁ TRI THỨC
SVTH: Quách Luyl ða
Trang 18
Dữ liệu dựa trên ñồ thị:
ðồ thị ñược coi như là 1 công cụ rất mạnh và rất thuận lợi cho việc biểu
diễn dữ liệu vì nó có thể mô tả ñược mối quan hệ giữa các thành phân dữ liệu.
Các ñối tượng dữ liệu biểu diễn bằng các nút trên ñồ thị còn mối quan hệ giữa
các ñối tượng thì ñược biểu diễn bằng các ñường liên kết giữa các nút. Mối quan
hệ giữa các ñối tượng thường nói lên thông tin quan trọng về dữ liệu.
Dữ liệu có thứ tự:
Trong một số trường hợp, các thuộc tính của dữ liệu mẫu tin có các mối
quan hệ về mặt thời gian cũng như không gian. Dữ liệu như vậy ñược gọi là dữ
liệu có thứ tự. Dữ liệu có thứ tự bao gồm:
– Dữ liệu ñược sắp xếp liên tục theo thời gian: ðây là một dạng mở rộng
của dữ liệu dạng mẫu tin. Không chỉ mẫu tin và từng thuộc tính của mẫu tin cũng
có sự kết hợp với thời gian (thời ñiểm). Ví dụ: Dữ liệu về giao dịch của khách
hàng tại từng thời ñiểm như sau:
IDcustomers
Items
1
Bread, coke, milk
2
Beer, Bread
3
Beer, Coke, Diaper, Milk
4
Beer, Bread, Diaper, Milk
5
Coke, Diaper, Milk
a) Các trang web ñược liên kết với nhau
b) Cấu trúc ADN
Hình II-4. Các ñối tượng của dữ liệu dạng mẫu tin
Hình II-5. Các ñối tượng dữ liệu dựa trên ñồ thị
luyldaquach@gmail.com
NGHIÊN CỨU KHAI MỎ DỮ LIỆU
VÀ KHÁM PHÁ TRI THỨC
SVTH: Quách Luyl ða
Trang 19
Hình II-7. Bảng dữ liệu giao dịch theo thời gian (tiếp theo)
– Dữ liệu dạng chuỗi: (sequence data) là một tập hợp dữ liệu mà nó là một
chuỗi các thực thể ñơn lẻ giống như 1 chuỗi các con số, ký tự hay từ khóa. Rất
giống với kiểu dữ liệu theo thời gian nhưng không liên quan ñến thời gian (thời
ñiểm). Ví dụ về thông tin di chuyển của loài ñộng hay thực vật ñược biểu diễn
như 1 chuỗi nucleotide ñược gọi là lag gene.
Hình II-8. Chuỗi dữ liệu
– Time series data: Là một dạng ñặc biệt của dữ liệu dạng chuỗi, mỗi mẫu
tin là 1 time series. Nói cách khác, mỗi mẫu tin là một chuỗi các giá trị ño ñược
tại các thời ñiểm.
– Spatial data: Một số ñối tượng có thuộc tính liên quan ñến không gian
hay vị trí. Ví dụ: Dữ liệu về thời tiết tại các vị trí khác nhau trên trái ñất.
II.2.2. Chất lượng của dữ liệu:
Khai phá dữ liệu thường sử dụng ñược thu nhập cho những mục ñích khác
hoặc cho việc sử dụng trong tương lai hoặc không rõ ứng dụng cụ thể. Chính vì
vậy mà chất lượng dữ liệu là một vấn ñề cần quan tâm khi khai thác chi thức từ
dữ liệu. Vì vậy, trước khi sử dụng, dữ liệu phải ñược xử lý ñể loại bỏ nhiễu, cũng
như loại bỏ dữ liệu trùng nhau và dữ liệu vô ích không thể phục vụ cho công việc
khai phá dữ liệu hiện tại. Vấn ñề ñược trình bày tiếp theo là vấn ñề liên quan ñến
chất lượng dữ liệu.
Hình II-6. Bảng dữ liệu giao dịch theo thời gian
luyldaquach@gmail.com
NGHIÊN CỨU KHAI MỎ DỮ LIỆU
VÀ KHÁM PHÁ TRI THỨC
SVTH: Quách Luyl ða
Trang 20
II.2.2.1. ðộ ño chất lượng và vấn ñề thu thập dữ liệu:
Trong cuộc sống không có gì là hoàn hảo, dữ liệu ñược thu nhập cũng ñể xử
lý cũng gặp nhiều vấn ñề khác nhau và không ñảm bảo ñược chất lượng của dữ
liệu phục vụ cho quá trình khai phá dữ liệu. Các vấn ñề có thể là:
– Giá trị của một hoặc nhiều thuộc tính của một hoặc ñối tượng có thể bị
thiếu.
– Dữ liệu bị trùng lắp nhiều lần.
Nguyên nhân của những vấn ñề trên có thể ñến từ:
– Lỗi của con người, có thể nói ñến lỗi của người thu thập dữ liệu hay tác
ñộng trực tiếp ñến dữ liệu.
– Sự giới hạn của các thiết bị ño, có thể do ñơn vị ño và khoảng cách quá
chênh lệch.
– Lỗi trong quá trình thu thập dữ liệu.
Vì thế, vấn ñề liên quan ñến chất lượng của dữ liệu, chúng ta cần quan tâm
ñến các vấn ñề sau:
a) Lỗi ño lường và thu thập dữ liệu:
Lỗi của sự ño lường có thể ñến từ các thiết bị hay chính sự tác ñộng trực
tiếp của con người. Nó ñược sinh ra do quá trình ño lường. Các lỗi có thể xảy ra
do những nguyên nhân sau:
– Giá trị ñược lưu khác với giá trị thực. Ví dụ: Năng lượng ion hóa nguyên
tử hirô là 13,6 eV, do quá trình ghi chép và lưu trữ trong thiết bị có thể là 13,9eV;
14eV; 13eV;…
– Do phương pháp ño không phù hợp hoặc thiết bị ño hay ñiều kiện ño
không phù hợp. Ví dụ: Trong việc ño huyết áp của bệnh nhân, tư thế ño : nằm
hoặc ngồi, sử dụng thiết bị ño cánh tay ño ở cổ tay hoặc ngược lại, uống cà phê
trước khi ño,… cũng ảnh hưởng ñến chất lượng của mỗi lần ño huyết áp.
– Lỗi thu thập dữ liệu xảy ra do quá trình thu thập dữ liệu và thường là bỏ
qua một số ñối tượng dữ liệu hay thuộc tính, thu thập dữ liệu không ñúng. Ví dụ:
Xác ñịnh bệnh sốt rét cần có các thông tin: lượng bạch cầu trong máu, thay ñổi
dịch não tủy, giảm canxi trong máu, hạ natri máu, bệnh nhân suy thận,…nếu
thiếu 1 trong các triệu chứng và các xét nghiệm trên thì không thể có kết luận cụ
thể về bệnh.
b) Nhiễu và dữ liệu bị bóp méo:
Nhiễu ñược hiểu là thành phần ngẫu nhiên của lỗi ño lường dữ liệu. Lỗi này
có thể làm cho dữ liệu bị biến dạng, bị ñưa vào các ñối tượng giả mạo. Lỗi
thường gặp ñối với các ñối tượng là âm thanh, số lượng dữ liệu quá lớn không
thể gom nhóm ñược,…Vấn ñề nhiễu và dữ liệu bị bóp méo có thể do những
nguyên nhân: tiếng ồn xung quanh, phương pháp hay giải thuật xử lý nhiễu chưa
hợp lý và làm mất quá nhiều thông tin,…
luyldaquach@gmail.com
NGHIÊN CỨU KHAI MỎ DỮ LIỆU
VÀ KHÁM PHÁ TRI THỨC
SVTH: Quách Luyl ða
Trang 21
Hình II-9. Nhiễu trong Time series data
c) Tính chính xác, ñộ lệch, sự ñúng ñắn của dữ liệu:
Trong quá trình thống kê và thí nghiệm, chất lượng của quá trình ño lường
và dữ liệu của kết quả ñược ño bằng tính chính xác (precision) và ñộ lệch (bias).
– Tính chính xác: Là gần kề của kết quả ño ñược lặp lại nhiều lần.
– ðộ lệch: Là sự khác nhau về mặt hệ thống của những kết quả ño khi ño
cùng một ñại lượng.
Tính chính xác thường ñược ño bằng ñộ lệch tiêu chuẩn (standard
deviation) của một tập các giá trị. ðộ lệch ñược ño bằng sự khác nhau giữa giá trị
trung bình của tập hợp các giá trị với giá trị ñã biết của lượng ñược ño. Ví dụ: ðộ
ño của vật thể X sau 5 lần ño, có kết quả như sau: 1.015;0.99;1.013;1.001;0.986.
Giá trị trung bình là X =1.001, ñộ lệch tiêu chuẩn bằng 0.013096.
– Sự ñúng ñắn: Sự gần ñúng của các số liệu ño ñược với giá trị thực của
lượng ñược ño. Sự ñúng ñắn (accuracy) thường ñược sử dụng ñể mô tả mức ñộ
ño sai. Sự ñúng ñắn phụ thuộc vào tính chính xác và ñộ lệch của phép ño (kết quả
ño).
d) Ngoại lệ:
Là những ñối tượng dữ liệu có những ñặc ñiểm khác xa so với hầu hết dữ
liệu trong cùng 1 nhóm hay ngoại lệ là những trường hợp các ñối tượng dữ liệu
có giá trị của một số thuộc tính khác xa giá trị của cùng thuộc tính của các ñối
tượng còn lại trong nhóm. Ví dụ: Trong cùng 1 loài hoa Iris có ñộ dài ñài hoa, ñộ
rộng ñài hoa, ñộ dài cuốn hoa, ñộ rộng cuốn hoa lần luợt có giá trị trung bình lần
Hình II-10. Dữ liệu gốc và dữ liệu bị nhiễu
luyldaquach@gmail.com
NGHIÊN CỨU KHAI MỎ DỮ LIỆU
VÀ KHÁM PHÁ TRI THỨC
SVTH: Quách Luyl ða
Trang 22
lượt là: 5.1, 3.5, 1.4, 0.2; nhưng xuất hiện một bông hoa iris có các số ño tương
ứng là: 7.0,3.2,4.7,1.4 và xuất hiện màu khác,…
Từ ñấy có thể rút ra kết luận rằng, ngoại lệ ảnh hưởng rất lớn ñến quá trình
phân tích dữ liệu trong khai phá dữ liệu. Ngoại lệ cần ñược phát hiện và loại bỏ
trong quá trình tiền xử lý dữ liệu.
e) Giá trị bị thiếu:
Giá trị bị thiếu do quá trình thu nhập dữ liệu không ñảm bảo thu thập ñầy
ñủ giá trị của tất cả các thuộc tính của các ñối tượng dữ liệu. Lỗi ñó có thể do 1
số nguyên nhân sau:
–
Do người dùng không cung cấp dữ liệu không cung cấp ñầy ñủ thông
tin.
–
Do người thu thập dữ liệu làm mất thông tin.
–
Trong 1 số trường hợp ñặc biệt nào ñó mà dữ liệu bị mất ñi một phần.
Vì vậy, dữ liệu bị thiếu ñóng một vai trò rất quan trọng trong quá trình phân
tích. Việc xử lý dữ liệu có nhiều cách khác nhau, nhưng mỗi cách ñều có ưu
ñiểm, khuyết ñiểm và phù hợp với những tình huống cụ thể khác nhau. Do ñó,
cần cẩn thận trong việc lựa chọn cách xử lý nhằm tránh ảnh hưởng ñến kết quả
của các bước tiếp theo và ñộ chính xác cũng như hiệu quả của cả hệ thống. Sau
ñây là một vài cách xử lý cho các trường hợp cụ thể:
Loại bỏ ñối tượng dữ liệu hay thuộc tính: là cách xử lý ñơn giản và hiệu
quả trong trường hợp dữ liệu bị thiếu giá trị. Tương ứng với các trường hợp sẽ có
biện pháp xử lý sau:
– Nếu ñối tượng dữ liệu nào thiếu thuộc tính thì loại ra khỏi tập dữ liệu
dùng ñể phân tích.
– Nếu có quá nhiều ñối tượng cùng thiếu giá trị do một thuộc tính nào ñó
thì loại bỏ thuộc tính ñó ra khỏi tập thuộc tính của ñối tượng dữ liệu.
Ước lượng giá trị bị thiếu: Trong một số trường hợp, các giá trị thiếu có
thể ñược ước lượng từ các giá trị khác ñã có trước ñó.
Không quan tâm ñến giá trị bị thiếu trong suốt quá trình phân tích: Nhiều
hướng tiếp cận của khai phá dữ liệu có thể bỏ qua các giá trị bị thiếu trong lúc
phân tích.
f) Giá trị không nhất quán:
Ví dụ: 2 mẫu tin có giá trị “tỉnh thành” giống nhau nhưng giá trị “mã bưu
cục” khác nhau.
Có nhiều nguyên nhân dẫn ñến dữ liệu không nhất quán. Có thể do cơ sở dữ
liệu thiết kế không tốt, do người cung cấp dữ liệu cung cấp sai thông tin, do
người thu nhập nhập dữ liệu sai,…Dữ liệu không nhất quán có thể ñược phát hiện
và chỉnh sửa kịp thời.
g) Dữ liệu bị trùng lắp:
Dữ liệu trong quá trình thu nhập có thể chứa nhiều ñối tượng dữ liệu bị
trùng lắp. Dữ liệu trùng lắp có thể do quá trình nhập liệu và thu thập dữ liệu
không lặp lại nhiều lần. Dữ liệu bị trùng lắp cần ñược phát hiện và loại bỏ trong
quá trình tiền xử lý dữ liệu.
luyldaquach@gmail.com
NGHIÊN CỨU KHAI MỎ DỮ LIỆU
VÀ KHÁM PHÁ TRI THỨC
SVTH: Quách Luyl ða
Trang 23
II.2.2.2. Các vấn ñề liên quan ñến ứng dụng:
Chất lượng của dữ liệu có thể ñược quan sát và ñánh giá ở nhiều gốc ñộ ứng
dụng khác nhau. Tùy vào ứng dụng cụ thể mà chất lượng dữ liệu sẽ phù hợp với
ứng dụng ñó. Một số trường hợp ñòi hỏi dữ liệu phải thật tốt (chất lượng cao)
trong khi một số trường hợp chấp nhận dữ liệu có chứa một ít sai sót. Một số vấn
ñề cần quan tâm ñến ứng dụng là:
a) Tính phù hợp theo thời gian:
Trong một số trường hợp, dữ liệu chỉ có giá trị sử dụng trong một khoảng
thời gian nhất ñịnh kể từ khi dữ liệu ñược thu thập. Dữ liệu ñược thu thập quá lâu
có thể sẽ không còn hữu dụng, không còn phản ánh ñúng bản chất của sự vật.
Ví dụ: ðiểm sàng ñại học năm 2010 không thể áp dụng cho ñiểm sàng ñại
học năm 2010.
b) Tính liên quan:
Dữ liệu phải chứa thông tin hữu ích và cần thiết cho ứng dụng.
Ví dụ: ðể xây dựng mô hình tư vấn việc chọn ngành nghề cho thí sinh thi
tuyển sinh ñại học. Thông tin về mức sống, sở thích, ñiều kiện và hoàn cảnh gia
ñình của thí sinh không thật sự cần thiết. Trong khi, thông tin về học lực, hạnh
kiểm, sức khỏe,…lại rất quan trọng.
c) Tri thức về dữ liệu:
Một cách lý tưởng, các tập dữ liệu có ñược từ các tài liệu mô tả các khía
cạnh khác nhau của dữ liệu. Chất lượng của tài liệu này sẽ giúp ích rất nhiều cho
quá trình phân tích dữ liệu. Kiến thức về dữ liệu còn thể hiện ở việc nhận biết các
ñặc ñiểm quan trọng của dữ liệu như: tính chính xác của dữ liệu, các kiểu thuộc
tính, tỉ lệ ño và nguồn gốc của dữ liệu.
II.3. Thu thập và tiền xử lý dữ liệu:
ðể dữ liệu có thể ứng dụng vào quá trình khai phá dữ liệu, dữ liệu cần ñược
thu thập và xử lý. Công việc của giai ñoạn này là lựa chọn ñối tượng dữ liệu và
thuộc tính cho quá trình phân tích hoặc tạo ra các thuộc tính mới hoặc thay ñổi
thuộc tính. Mục ñích cuối cùng của quá trình này là cải thiện quá trình phân tích
trong khai phá dữ liệu ở khía cạnh thời gian, tiền của và chất lượng.
II.3.1. Tổng hợp dữ liệu:
Là việc gom 2 hay nhiều ñối tượng dữ liệu lại với nhau, nhằm mục ñích tạo
thành một ñối tượng.
Ví dụ: Ở một siêu thị có nhiều phòng ban, mỗi phòng ban có quyền truy cập
ñến hệ thống ở một lãnh vực riêng của hệ thống. Mỗi nhân viên ở siêu thị sẽ làm
việc cho các văn phòng của siêu thị. Bằng việc thiết lập quyền truy cập cho các
phòng của siêu thị sẽ tiết kiệm thời gian và không gian bộ nhớ hơn việc thiết lập
quyền riêng cho các nhân viên.
Tổng hợp dữ liệu sẽ phải dựa trên các nguyên tắt sau:
– ðối với thuộc tính kiểu số: lấy tổng hoặc trung bình.
– ðối với các thuộc tính không phải kiểu số: có thể bỏ qua hoặc tổng hợp
như là môt tập hợp các giá trị.
Ưu ñiểm của việc kết hợp dữ liệu:
luyldaquach@gmail.com
NGHIÊN CỨU KHAI MỎ DỮ LIỆU
VÀ KHÁM PHÁ TRI THỨC
SVTH: Quách Luyl ða
Trang 24
(1) Tập hợp dữ liệu sau khi kết hợp nhỏ hơn ñáng kể so với tập dữ liệu ban
ñầu. Dung lượng bộ nhớ lưu trữ ít hơn, thời gian xử lý ngắn hơn, sử
dụng các thuật toán vét cạn.
(2) Có thể coi việc kết hợp dữ liệu như là việc thay ñổi giá trị và thang
chia giá trị. Cung cấp góc nhìn dữ liệu ở mức cao.
(3) Dữ liệu sau khi kết hợp ổn ñịnh hơn dữ liệu ñơn lẽ trước khi kết hợp.
Hạn chế của việc kết hợp dữ liệu: Khả năng mất các thông tin hay chi
tiết quan trọng.
II.3.2. Lấy mẫu:
Thường ñược sử dụng trong việc lựa chọn tập thuộc tính con dùng ñể phân
tích và cũng là một cách làm rất hữu dụng trong khai phá dữ liệu. Mục ñích chính
của việc lấy mẫu là “làm giảm thời gian và tài nguyên cho quá trình phân tích dữ
liệu”.
Nguyên tắt lấy mẫu hiệu quả:
– Lấy mẫu phải ñại diện cho tập hợp dữ liệu.
– Mẫu dữ liệu phải có ñầy ñủ các thuộc tính như tập dữ liệu gốc.
– Phương pháp lấy mẫu phải ñảm bảo tính ñại diện của mẫu dữ liệu.
– Kỹ thuật lấy mẫu và số lượng mẫu phải phù hợp.
Cách tiếp cận khi lấy mẫu:
(1) Lấy mẫu ngẫu nhiên (random samling): ðây là cách lấy mẫu ñơn giản
nhất. ðối với cách này, xác suất ñể chọn các phần tử trong tập hợp là như nhau.
Có 2 cách biến thể của lấy mẫu ngẫu nhiên là:
– Lấy mẫu không có sự thay thế: Mỗi phần tử chỉ có thể ñược chọn một
lần duy nhất. Khi một phần tử ñược chọn thì nó sẽ bị loại ra khỏi tập hợp và việc
lựa chọn mẫu tiếp theo sẽ áp dụng trên các tập hợp các phần tử chưa ñược chọn.
– Lấy mẫu có sự lặp lại: Một phần tử có thể ñược chọn nhiều hơn một lần.
Khi chọn một phần tử ñuợc chọn thì nó sẽ không bị loại ra khỏi tập hợp và nó sẽ
có khả năng ñược chọn ở lần chọn tiếp theo.
(2) ðể hạn chế các hiệu ứng phụ (ñiểm yếu) của phương pháp lấy mẫu, dữ
liệu ban ñầu nên ñược chia làm nhiều lớp. Việc chọn lấy mẫu sẽ áp dụng cho
từng lớp dữ liệu nên mẫu lấy về sẽ ñại diện cho cả tập hợp dữ liệu ban ñầu.
Lấy mẫu theo lũy tiến (progressive sampling): Trong thực tế, rất khó xác
ñịnh số lượng mẫu của từng tập dữ liệu. Lấy mẫu theo cách lũy tiến là cách lấy
mẫu như sau:
– Bắt ñầu với 1 lượng mẫu nhỏ.
– Tăng dần lượng mẫu cho ñến khi nào ñạt ñược kích thước phù hợp (ñủ
lớn).
– Dừng tăng khi nào ñộ chính xác của mô hình ñạt ñến mức ổn ñịnh.
Mất thông tin trong lấy mẫu:
Vấn ñề lựa chọn kích thước của tập hợp mẫu rất quan trọng vì nó ảnh
hưởng ñến ñộ chính xác của mô hình sau khi phân tích. Kích thước của mẫu càng
lớn thì kết quả phân tích càng gần với kết quả phân tích của tập dữ liệu gốc
nhưng ý nghĩa của việc lấy mẫu sẽ không còn nữa. Kích thước của mẫu càng nhỏ
luyldaquach@gmail.com
NGHIÊN CỨU KHAI MỎ DỮ LIỆU
VÀ KHÁM PHÁ TRI THỨC
SVTH: Quách Luyl ða
Trang 25
thì sẽ dẫn ñến mất thông tin và thu ñược kết quả phân tích khác xa so với kết quả
phân tích của tập dữ liệu gốc.
II.3.3. Giảm bớt thuộc tính:
Giảm bớt thuộc tính chính là ñể chỉ các kỹ thuật làm giảm số chiều (thuộc
tính) của dữ liệu bằng cách tạo ra thuộc tính mới là tập hợp của các thuộc tính cũ.
Việc giảm bớt thuộc tính mang lại rất nhiều lợi ích cho quá trình phân tích dữ
liệu.
II.3.3.1. Thuận lợi:
– Các thuật toán trong khai phá dữ liệu sẽ làm việc tốt hơn khi áp dụng
trên tập dữ liệu có ích thuộc tính. Bởi vì, giảm bớt thuộc tính sẽ bỏ ñi các thuộc
tính kém quan trọng và có thể giảm ñược nhiễu trong dữ liệu.
– Làm cho quá trình biểu diễn (visualize) dữ liệu dễ hơn.
– Giảm thời gian và tài nguyên cho việc phân tích.
II.3.3.2. Khó khăn:
Thuật ngữ “the curse of dimensionality” dùng ñể chỉ hiện tượng mà nhiều
kiểu phân tích dữ liệu trở nên khó khăn hơn khi số thuộc tính của dữ liệu tăng
lên. Một cách ñặt biệt, khi tăng số lượng thuộc tính thì dữ liệu càng trở nên thưa
thớt trong không gian mà nó chiếm giữ. Tùy vào mức ảnh hưởng, nó sẽ tác ñộng
trực tiếp ñến các thuật toán của khai phá dữ liệu.
– ðối với quá trình phân lớp dữ liệu (classification) là rất khó khăn, vì
không ñủ ñối tượng dữ liệu cho việc tạo ra mô hình ñáng tin cậy.
– ðối với việc gom nhóm dữ liệu (clustering), mật ñộ và khoảng cách giữa
các ñối tượng trở nên vô nghĩa.
Tóm lại, thuật toán phân lớp dữ liệu và gom nhóm dữ liệu gặp rắc rối khi
dữ liệu có quá nhiều thuộc tính.
a) Ảnh ban ñầu b) Ảnh mất thông tin
c) Ảnh mất thông tin
do nhiễu muối tiêu
do nhiễu Gause
Hình II-11. Mất thông tin khi lấy mẫu
