ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CNTT & TRUYỀN THÔNG
DƯƠNG ĐỨC NGUYÊN
NGHIÊN CỨU MỘT SỐ THUẬT TOÁN LIÊN QUAN ĐẾN
TẬP RÚT GỌN TRÊN BẢNG QUYẾT ĐỊNH NHẤT QUÁN
Chuyên ngành: Khoa học máy tính
Mã số: 60 48 01
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
NGƯỜI HƯỚNG DẪN KHOA HỌC: GS.TS VŨ ĐỨC THI
Thái Nguyên – 2013
i
LỜI CAM ĐOAN
1) Tôi xin cam đoan luận văn này là sản phẩm nghiên cứu của riêng tôi.
2) Một số định lý, định nghĩa và hệ quả, thuật toán tôi lấy từ nguồn tài liệu
chính xác có trích dẫn tên tài liệu và tên tác giả rõ ràng.
3) Chương trình thử nghiệm là của tôi viết và cài đặt, tôi không hề sao chép
của bất cứ ai.
4) Tôi xin chịu trách nhiệm hoàn toàn về sản phẩm nghiên cứu của mình.
Tác giả
Dương Đức Nguyên
ii
LỜI CẢM ƠN
Để có thể hoàn thành đề tài luận văn thạc sĩ một cách hoàn chỉnh, bên cạnh
sự nỗ lực cố gắng của bản thân còn có sự hướng dẫn nhiệt tình của quý Thầy Cô,
cũng như sự động viên ủng hộ của gia đình và bạn bè trong suốt thời gian học tập
nghiên cứu và thực hiện luận văn thạc sĩ.
Xin chân thành bày tỏ lòng biết ơn đến Thầy Vũ Đức Thi, người đã hết lòng
giúp đỡ và tạo mọi điều kiện tốt nhất cho tôi hoàn thành luận văn này. Xin gửi lời tri
ân nhất của tôi đối với những điều mà Thầy đã dành cho tôi.
Xin chân thành bày tỏ lòng biết ơn đến toàn thể quý thầy cô đã giảng dạy và
truyền đạt kiến thức cho tôi để tôi có thể hoàn thành các môn học trong xuất thời
gian học cao học tại trường Đại học Thái Nguyên.
Xin gửi lời cảm ơn tới ban lãnh đạo cùng toàn thể các thầy cô trong trường
Đại học Công Nghệ Thông Tin và Truyền Thông Đại Học Thái Nguyên đã tạo điều
kiện thuận lợi cho tôi trong thời gian tôi học tập và nghiên cứu tại đây.
Xin chân thành bày tỏ lòng biết ơn đến gia đình, những người đã không
ngừng động viên, hỗ trợ và tạo mọi điều kiện tốt nhất cho tôi trong suốt thời gian
học tập và thực hiện luận văn.
Cuối cùng, tôi xin chân thành bày tỏ lòng cảm ơn đến các anh chị, các đồng
nghiệp đã hỗ trợ cho tôi rất nhiều trong suốt quá trình học tập, nghiên cứu và thực
hiện đề tài luận văn thạc sĩ một cách hoàn chỉnh.
Thái Nguyên, tháng 8 năm 2013.
Học viên
Dương Đức Nguyên
iii
MỤC LỤC
MỞ ĐẦU......................................................................................................................1
CHƯƠNG 1: MỘT SỐ KHÁI NIỆM CƠ BẢN..........................................................4
1.1. Quá trình khai phá tri thức từ cơ sở dữ liệu..........................................................4
1.1.1. Xác định vấn đề..................................................................................................5
1.1.2. Thu thập và tiền xử lí dữ liệu.............................................................................5
1.2. Khai phá dữ liệu.....................................................................................................7
1.2.1. Một số quan niệm về khai phá dữ liệu...............................................................7
1.2.2.Nhiệm vụ của khai phá dữ liệu............................................................................7
1.2.3. Triển khai việc khai phá dữ liệu.........................................................................8
1.2.4. Một số ứng dụng khai phá dữ liệu......................................................................9
1.2.5. Các kỹ thuật khai phá dữ liệu............................................................................9
1.2.6. Kiến trúc của hệ thống khai phá dữ liệu...........................................................11
1.2.7. Quá trình khai phá dữ liệu................................................................................12
1.2.8. Những khó khăn trong khai phá dữ liệu...........................................................13
1.3. Hệ thông tin đầy đủ và mô hình tập thô truyền thống........................................14
1.3.1. Hệ thông tin đầy đủ..........................................................................................14
1.3.2 Mô hình tập thô truyền thống............................................................................15
1.3.3. Bảng quyết định đầy đủ....................................................................................17
1.3.4. Tập rút gọn và tập lõi........................................................................................18
1.4.1. Một số khái niệm cơ bản..................................................................................20
1.4.2 Một số thuật toán cơ bản...................................................................................22
1.5.Tổng kết chương...................................................................................................27
CHƯƠNG 2: RÚT GỌN THUỘC TÍNH VÀ MỘT SỐ THUẬT TOÁN TRÊN
BẢNG QUYẾT ĐỊNH NHẤT QUÁN......................................................................28
2.1 Mở đầu..................................................................................................................28
2.2 Một số tính chất của metric trên bảng quyết định................................................29
2.3. Rút gọn thuộc tính trong bảng quyết định sử dụng metric.................................34
2.3.1.Tập lõi và tập rút gọn của bảng quyết định dựa trên metric.............................34
iv
2.3.2. Thuật toán tìm tập rút gọn của bảng quyết định sử dụng metric.....................35
2.3.3. Mối liên hệ giữa tập rút gọn dựa trên Metric và tập rút gọn Entropy Shannon
.....................................................................................................................................42
2.3.4. Thuật toán tìm tập rút gọn theo tham số độ chắc chắn của tập luật................43
2.4. Thuật toán tìm tập tất cả các thuộc tính rút gọn của bảng quyết định nhất quán
.....................................................................................................................................45
2.4.1. Đặt vấn đề.........................................................................................................45
2.4.2. Thuật toán.........................................................................................................46
2.5. Thuật toán tìm họ tất cả các tập rút gọn của bảng quyết định nhất quán..........48
2.6. Thuật toán xây dựng các phụ thuộc hàm từ bảng quyết định nhất quán............51
2.7. Thuật toán xây dựng bảng quyết định từ tập phụ thuộc hàm.............................52
2.8. Tổng kết chương 2...............................................................................................56
CHƯƠNG 3: CÀI ĐẶT CHƯƠNG TRÌNH TÌM TẬP TẤT CẢ CÁC THUỘC
TÍNH RÚT GỌN TRÊN BẢNG QUYẾT ĐỊNH NHẤT QUÁN.............................57
1. Đặt vấn đề...............................................................................................................57
2. Yêu cầu hệ thống và cấu hình cho máy..................................................................57
2.1. Yêu cầu hệ thống.................................................................................................57
2.2. Cấu hình cho máy................................................................................................57
3. Giới thiệu chương trình và cách sử dụng...............................................................58
3.1 Cấu trúc chương trình...........................................................................................58
3.2. Giới thiệu chương trình.......................................................................................60
4. Thực hiện thuật toán với bộ dữ liệu Flu, EXAMPLE1, EXAMPLE....................62
4.1. Bộ dữ liệu “Flu”...................................................................................................62
4.2. Bộ dữ liệu “EXAMPLE1”...................................................................................63
4.3. Bộ dữ liệu “EXAMPLE”.....................................................................................65
5. Kiểm thử.................................................................................................................67
6. Tổng kết chương.....................................................................................................67
KẾT LUẬN VÀ ĐỀ NGHỊ........................................................................................68
TÀI LIỆU THAM KHẢO..........................................................................................69
v
vi
DANH MỤC CÁC BẢNG
BẢNG 1.1 BẢNG THÔNG TIN VỀ BỆNH CÚM...........................................16
BẢNG 1.2. BẢNG QUYẾT ĐỊNH VỀ BỆNH CÚM........................................19
BẢNG 2.1. BẢNG QUYẾT ĐỊNH VỀ BỆNH CẢM CÚM..............................33
BẢNG 2.2. BẢNG QUYẾT ĐỊNH MINH HỌA VÍ DỤ 2.2/.............................36
BẢNG 2.3. BẢNG QUYẾT ĐỊNH Ở VÍ DỤ 2.6...............................................50
BẢNG 2.4. BẢNG BẢNG QUYẾT ĐỊNH ĐƯỢC XÂY DỰNG TỪ THUẬT
TOÁN..............................................................................................................56
BẢNG 3.1. TRIỆU CHỨNG CÚM CỦA BỆNH NHÂN..................................62
BẢNG 3.2. BẢNG QUYẾT ĐỊNH...................................................................63
BẢNG 3.3. BẢNG DỮ LIỆU KẾT QUẢ THỰC HIỆN TRÊN 3 BỘ DỮ LIỆU
MẪU................................................................................................................67
vii
DANH MỤC CÁC HÌNH
HÌNH 1.1. QUÁ TRÌNH KHÁM PHÁ TRI THỨC TỪ CƠ SỞ DỮ LIỆU........4
HÌNH 1.2. KIẾN TRÚC CỦA HỆ THỐNG KHAI PHÁ DỮ LIỆU.................11
HÌNH 1.3. QUÁ TRÌNH KHAI PHÁ DỮ LIỆU..............................................13
HÌNH 3.1. LIÊN KẾT GIỮA CÁC LỚP TRONG CHƯƠNG TRÌNH............58
HÌNH 3.2. LỚP REDUCED.............................................................................59
HÌNH 3.3. LỚP DESISIONTABLE.................................................................59
HÌNH 3.4. LỚP EQUALSYSTEM...................................................................59
HÌNH 3.5. LỚP ULTILITIES..........................................................................60
HÌNH 3.6. GIAO DIỆN CHÍNH CỦA CHƯƠNG TRÌNH..............................60
HÌNH 3.7. SỬA HAY THÊM MỘT DÒNG DỮ LIỆU MỚI TRÊN BẢNG
“FLU”..............................................................................................................61
HÌNH 3.8. KẾT QUẢ CỦA BỘ DỮ LIỆU FLU...............................................63
HÌNH 3.9. KIỂM TRA XEM BẢNG QUYẾT ĐỊNH EXAMPLE1 CÓ NHẤT
QUÁN KHÔNG...............................................................................................64
HÌNH 3.10. KẾT QUẢ KHI THỰC HIỆN THUẬT TOÁN VỚI BỘ DỮ LIỆU
EXAMPLE1.....................................................................................................65
HÌNH 3.11. KIỂM TRA XEM BẢNG QUYẾT ĐỊNH EXAMPLE CÓ NHẤT
QUÁN KHÔNG...............................................................................................66
HÌNH 3.12. KẾT QUẢ KHI THỰC HIỆN THUẬT TOÁN VỚI BỘ DỮ LIỆU
EXAMPLE......................................................................................................66
vii
i
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
Ký hiệu, từ viết tắt
Diễn giải
IS = (U,A,V,f)
Hệ thông tin, hệ thông tin đầy đủ
IIS = (U,A,V,f)
Hệ thông tin không đầy đủ
DS =(U,C D,V,f)
Bảng quyết định, bảng quyết định đầy đủ
IDS =(U,C D,V,f) Bảng quyết định không đầy đủ
U
Số đối tượng
C
Số thuộc tính điều kiện trên bảng quyết định
A
Số thuộc tính trong hệ thông tin
BX
B- xấp xỉ dưới của X
BX
Xấp xỉ trên của X
BNB(D)
B – Miền biên của D
POSB(D)
B- Miền dương của D
HRED(C)
Họ tất cả các tập rút gọn Entropy Shannon
U/B
Phân hoạch của U sinh bởi tập thuộc tính B
SB(u)
Lớp dung sai của đối tượng u
SĐQH
Sơ đồ quan hệ
H(Q/P)
Entropy Shannon có điều kiện của Q khi đã biết P
IE(P)
Entropy liang mở rộng của tập thuộc tính P trong hệ thông tin
đầy đủ
SIM(B)
Quan hệ dung sai trên hệ thuộc tính
IND(B)
Quan hệ B không phân biệt
dj(K(P),K(Q))
Khoảng cách giữa K(P) và K(Q) trong hệ thông tin đầy đủ
dựa trên entropy Liang mở rộng
1
MỞ ĐẦU
Trong những năm gần đây, sự phát triển mạnh mẽ của công nghệ thông tin
đã làm cho khả năng thu thập và lưu trữ thông tin của hệ thống thông tin tăng
nhanh một cách nhanh chóng. Sự bùng nổ này đã dẫn tới một yêu cầu cấp thiết là
cần có những kỹ thuật và công cụ mới để tự động chuyển đổi lượng dữ liệu
khổng lồ kia thành các tri thức có ích. Từ đó, các kỹ thuật khai phá dữ liệu đã trở
thành một lĩnh vực thời sự của nền công nghệ thông tin thế giới hiện nay nói
chung và Việt Nam nói riêng.
Khai phá dữ liệu đang được áp dụng một cách rộng rãi trong nhiều lĩnh vực
kinh doanh và đời sống khác nhau: Market tinh, tài chính ngân hàng và bảo hiểm,
khoa học kinh tế…Rất nhiều tổ chức và công ty lớn trên thế giới đã áp dụng kỹ
thuật khai phá dữ liệu vào các hoạt động sản xuất kinh doanh của mình và thu được
nhiều lợi ích to lớn.
Trong lý thuyết tập thô, dữ liệu được biểu diễn thông qua một hệ thông tin
IS=(U,A) với U là tập các đối tượng và A là tập thuộc tính. Phương pháp tiếp cận
chính của lý thuyết tập thô là dựa trên quan hệ không phân biệt được để đưa ra các
tập xấp xỉ dưới và xấp xỉ trên của nó. Xấp xỉ dưới bao gồm các đối tượng chắc chắn
thuộc tập đó, còn xấp xỉ trên chứa tất cả các đối tượng có khả năng thuộc về tập đó.
Nếu tập xấp xỉ dưới bằng tập xấp xỉ trên thì tập đối tượng cần quan sát là tập rõ.
Ngược lại là tập thô. Các tập xấp xỉ là cơ sở để đưa ra các kết luận từ tập dữ liệu.
Bảng quyết định là hệ thông tin IS với tập thuộc tính A được chia thành hai tập
con khác rỗng rời nhau C và D, lần lượt được gọi là tập thuộc tính điều kiện và
tập thuộc tính quyết định. Nói cách khác, DS=(U,C D) với C D . Bảng
quyết định là mô hình thường gặp trong thực tế, Khi mà giá trị dữ liệu tại các
thuộc tính điều kiện có thể cung cấp cho ta thông tin về giá trị của thuộc tính
quyết định. Bảng quyết định là nhất quán khi phụ thuộc hàm C→D là đúng, trái
lại là không nhất quán.
Rút gọn thuộc tính là ứng dụng quan trọng nhất trong lý thuyết tập thô. Mục
2
tiêu của rút gọn thuộc tính là loại bỏ các thuộc tính dư thừa để tìm ra các thuộc tính
cốt yếu và cần thiết trong cơ sở dữ liệu. Với bảng quyết định, rút gọn thuộc tính là
tập con nhỏ nhất của tập thuộc tính điều kiện bảo toàn thông tin phân lớp của bảng
quyết định. Đối với một bảng quyết định có nhiều tập rút gọn khác nhau tuy nhiên
trong thực hành thường không đòi hỏi tìm tất cả các tập rút gọn mà chỉ cần tìm
được một tập rút gọn tốt nhất theo một tiêu chuẩn đánh giá nào đó là đủ. Vì vậy,
mỗi phương pháp rút gọn thuộc tính đều trình bày một thuật toán Heuristic tìm tập
rút gọn. Các thuộc tính này giảm thiểu đáng kể khối lượng tính toán, nhờ đó có thể
áp dụng đối với các bài toán có khối lượng dữ liệu lớn.
Cho bảng quyết định nhất quán DS=(U,C {d}), tập thuộc tính R C được gọi
là tập rút gọn của thuộc tính điều kiện C nếu R là tập tối thiểu thỏa mãn phụ thuộc
hàm R→{d}. Xét quan hệ r trên tập thuộc tính R C{d} được gọi là một tập tối
thiểu của thuộc tính {d} nếu R là tập thuộc tính tối thiểu thỏa mãn phụ thuộc hàm
R→{d}. Do đó, khái niệm tập rút gọn của bảng quyết định tương đương với tập tối
thiểu của thuộc tính {d} trên quan hệ, và một vài bài toán trên bảng quyết định liên
quan đến tập rút gọn có thể được giải quyết bằng một số kết quả liên quan đến tập
tối thiểu của một thuộc tính trong cơ sở dữ liệu quan hệ; bao gồm bài toán tìm tập
tất cả các thuộc tính rút gọn, bài toán tìm họ tất cả các tập rút gọn, bài toán trích lọc
tri thức dưới dạng các phụ thuộc hàm từ bảng quyết định, bài toán xây dựng bảng
quyết định từ tập phụ thuộc hàm cho trước. Cho đến nay, hướng tiếp cận này chưa
được nhiều tác giả quan tâm nghiên cứu.
Trên bảng quyết định nhất quán, vấn đề nhiên cứu đặt ra là xây dựng các thuật
toán có ý nghĩa liên quan đến tập rút gọn sử dụng một số kết quả liên quan đến tập
tối thiểu của một thuộc tính trong một cơ sở dữ liệu quan hệ.
Mục tiêu nghiên cứu của đề tài
- Tổng hợp kiến thức cơ bản nhất liên quan đến tập rút gọn và bảng quyết định
nhất quán.
- Dựa trên lý thuyết đã tổng kết được, đi xâu vào tìm hiểu, nghiên cứu một số
3
thuật toán liên quan đến tập rút gọn trên bảng quyết định nhất quán. Cài đặt thuật
toán tìm tập tất cả các thuộc tính rút gọn của bảng quyết định nhất quán.
Ý nghĩa khoa học của đề tài
- Đây là lĩnh vực được nhiều nhà khoa học nghiên cứu và đã có đóng góp
trong thực tiễn.
- Có thể coi đề tài là một tài liệu tham khảo khá đầy đủ, rõ ràng về một số
thuật toán liên quan đến tập rút gọn trên bảng quyết định nhất quán.
Đối tượng và phạm vi nghiên cứu của đề tài
- Các thuật toán cơ bản nhất liên quan đến tập rút gọn trên bảng quyết định
nhất quán.
Phương pháp nghiên cứu
- Lập kế hoạch, lên quy trình, tiến độ thực hiện.
-
Tham khảo nhiều tài liệu có liên quan, tham khảo các ý kiến các chuyên gia
trong lịnh vực nghiên cứu.
Thực tiễn của đề tài nghiên cứu
- Tổng kết các kiến thức cơ bản nhất của khai phá dữ liệu
- Luận văn có thể trở thành tài liệu tham khảo cho những người muốn tìm hiểu
về khai phá dữ liệu và một số thuật toán liên quan đến tập rút gọn trên bảng
quyết định nhất quán. Luận văn gồm 3 chương với các nội dung sau:
Chương 1: Trình bày về một số khái niện cơ bản
Chương 2: Rút gọn thuộc tính và một số thuật toán trên bảng quyết định nhất quán.
Chương 3: Cài đặt chương trình tìm tập tất cả các thuộc tính rút gọn trên bảng
quyết định nhất quán.
4
CHƯƠNG 1: MỘT SỐ KHÁI NIỆM CƠ BẢN
1.1. Quá trình khai phá tri thức từ cơ sở dữ liệu
Quá trình khai phá tri thức có thể chia thành các bước như sau:
- Làm sạch dữ liệu (Data cleaning): Loại bỏ dữ liệu nhiễu hoặc dữ liệu không
thích hợp.
- Tích hợp dữ liệu (Data integration): Tích hợp dữ liệu từ các nguồn khác nhau.
- Chọn dữ liệu (Data Selection): Chọn những dữ liệu liên quan trực tiếp đến
nhiệm vụ.
- Chuyển đổi dữ liệu (Data Transformation): Chuyển dữ liệu về những dạng
phù hợp cho việc khai thác.
- Khai phá dữ liệu (Data mining): Các kỹ thuật được áp dụng để trích xuất
thông tin có ích hoặc các mẫu điển hình trong dữ liệu.
- Đánh giá mẫu (Pattern evaluation): Đánh giá mẫu hoặc tri thức đã thu được.
- Trình diễn dữ liệu (Knowledge presentation): Biểu diễn những tri thức khai
phá được cho người sử dụng.
5. Đưa kết quả vào thực tiễn
4. Minh hoạ và đánh giá tri thức
3. Khai thác dữ liệu- trích ra các
mẫu/mô
2. Thu thập và tiền xử lí dữ liệu
hình
1. Hiểu và xác định vấn đề
Hình 1.1. Quá trình khám phá tri thức từ cơ sở dữ liệu
Hình 1.1 mô tả 5 giai đoạn trong quá trình khám phá tri thức từ cơ sở đến dữ
liệu. Mặc dù có 5 giai đoạn như trên trong quá trình khám phá tri thức từ cơ sở dữ
liệu là một quá trình tương tác lặp đi lặp lại theo chu trình liên tục kiểu xoáy trôn
ốc, trong đó lần lặp sau hoàn chỉnh hơn lần lặp trước. Ngoài ra, giai đoạn sau lại
5
dựa trên kết quả theo kiểu thác nước. Đây là một quá trình biện chứng mang tính
chất khoa học của lĩnh vực phát hiện tri thức và là phương pháp luận trong việc xây
dựng các hệ thống phát hiện tri thức.
1.1.1. Xác định vấn đề
Đây là một quá trình mang tính định tính với mục đích xác định được lĩnh vực
yêu cầu phát hiện tri thức và xây dựng bài toán. Trong thực tế, các cơ sở dữ liệu
được chuyên môn hoá và phân chia theo các lĩnh vực khác nhau như sản phẩm, kinh
doanh, tài chính,...Với mỗi tri thức phát hiện được có thể có giá trị trong lĩnh vực
này nhưng lại không mang nhiều ý nghĩa đối với một lĩnh vực khác. Vì vậy mà việc
xác định lĩnh vực và định nghĩa bài toán giúp định hướng cho giai đoạn tiếp theo
thu nhập và tiền sử lí dữ liệu.
1.1.2. Thu thập và tiền xử lí dữ liệu
Người ta chia giai đoạn thu thập và tiền xử lí dữ liệu thành các công đoạn như:
lựa chọn dữ liệu, làm sạch, làm giàu, mã hóa dữ liệu. Các công đoạn được thực hiện
theo trình tự đưa ra được một cơ sở dữ liệu thích hợp cho các giai đoạn sau. Tuy
nhiên, tùy từng dữ liệu cụ thể mà quá trình trên được điều chỉnh cho phù hợp vì
người ta đưa ra một phương pháp cho mọi loại dữ liệu.
a. Chọn lọc dữ liệu: Đây là bước chọn lọc các dữ liệu có liên quan trong các
nguồn dữ liệu khác nhau. Các thông tin được chọn lọc sao cho có chứa nhiều thông
tin liên quan tới lĩnh vực cần phát hiện tri thức đã xác định trong giai đoạn xác định
vấn đề.
b. Làm sạch dữ liệu: Dữ liệu thực tế, đặc biệt dữ liệu lấy từ nhiều nguồn khác
nhau thường không đồng nhất. Do đó còn có biện pháp xử lí để đưa về một cơ sở dữ
liệu thống nhất phục vụ cho khai thác. Nhiệm vụ làm sạch dữ liệu thường bao gồm:
Điều hoà dữ liệu, xử lí các giá trị khuyết, xử lí nhiễu và các ngoại lệ.
c. Làm giàu dữ liệu: Việc thu nhập dữ liệu đôi khi không đảm bảo tính đầy
đủ của dữ liệu. Một số thông tin quan trọng có thể thiếu hoặc không đầy đủ. Chẳng
6
hạn, dữ liệu về khách hàng lấy từ một nguồn bên ngoài không có hoặc không đầy
đủ thông tin về thu nhập. Nếu thông tin về thu nhập là quan trọng trong quá trình
khai thác dữ liệu để phân tích hành vi khách hàng thì rõ ràng là ta không thể chấp
nhận đưa các dữ liệu khuyết thiếu vào được.
d. Mã hóa:
Các Phương pháp dùng để chọn lọc, làm sạch, làm giàu dữ liệu sẽ được mã
hóa dưới dạng các thủ tục, chương trình hay tiện ích nhằm tự động hóa việc kết
xuất, biến đổi và di chuyển dữ liệu. Các hệ thống con đó có thể được thực thi định
kỳ làm tươi dữ liệu phục vụ cho việc phân tích.
1.1.3. Khai thác dữ liệu
Giai đoạn khai thác dữ liệu được bắt đầu sau khi dữ liệu đã được thu thập và
tiến hành xử lí. Trong giai đoạn này, công việc chủ yếu là xác định được bài toán
khai thác dữ liệu, tiến hành lựa chọn phương pháp khai thác phù hợp với dữ liệu có
được và tách ra các tri thức cần thiết.
Thông thường, các bài toán khai thác dữ liệu bao gồm: Các bài toán mang tính
chất mô tả - đưa ra những tính chất chung nhất của các dữ liệu, các bài toán khai
thác dự báo - bao gồm cả việc thực hiện các suy diễn trên dữ liệu. Tùy theo bài toán
xác định được mà ta lựa chọn các phương pháp khai thác dữ liệu cho phù hợp.
1.1.4. Minh họa và đánh giá tri thức
Các tri thức phát hiện từ cơ sở dữ liệu cần được tổng hợp dưới dạng các báo
cáo phục vụ cho các mục đích hỗ trợ quyết định khác nhau.
Do nhiều phương pháp khai thác có thể được áp dụng nên các kết quả có mức
độ tốt/xấu khác nhau. Việc đánh giá các kết quả thu được là cần thiết, giúp tạo cơ sở
cho các quyết định chiến lược. Thông thường chúng được tổng hợp, so sánh bằng
các biểu đồ và được kiểm nghiệm, tin học hoá. Công việc này thường là của các
chuyên gia, các nhà phân tích và quyết định.
7
1.2. Khai phá dữ liệu
1.2.1. Một số quan niệm về khai phá dữ liệu
Sau đây là một số quan niệm về khai phá dữ liệu:
Khai phá dữ liệu là tập hợp các thuật toán nhằm chiết xuất những thông tin có
ích từ kho dữ liệu khổng lồ.
Khai phá dữ liệu được định nghĩa như một quá trình phát hiện mẫu trong dữ
liệu. Quá trình này có thể là tự động hay bán tự động, song phần nhiều là bán tự
động. Các mẫu được phát hiện thường hữu ích theo nghĩa: Các mẫu mang lại cho
người sử dụng một lợi thế nào đó, thường là lợi thế về kinh tế.
Khai phá dữ liệu giống như quá trình tìm ra và mô tả mẫu dữ liệu. Dữ liệu như
là một tập hợp của các sự kiện, còn đầu ra quá trình khai phá dữ liệu như là dự báo
của các vật hay sự kiện mới.
Khai phá dữ liệu áp dụng trong các cơ sở dữ liệu quan hệ, giao dịch, cơ sở
dữ liệu không gian, cũng như các kho dữ liệu phi cấu trúc, điển hình là World
Wide Web.
Khám phá tri thức là quá trình nhận biết các mẫu hoặc các mô hình trong dữ
liệu với các tính chất: Đúng đắn, mới, khả ích và có thể hiểu được. Khai phá dữ liệu
là một bước trong quá trình khám phá tri thức bao gồm các thuật toán khai phá dữ
liệu chuyên dùng dưới một số quy định về hiệu quả tính toán chấp nhận được để
tìm ra các mẫu và các mô hình trong dữ liệu.
1.2.2.Nhiệm vụ của khai phá dữ liệu
Các bài toán liên quan đến khai phá dữ liệu về bản chất là các bài toán thống
kê. Điểm khác biệt giữa các kỹ thuật khai phá dữ liệu và các công cụ phục vụ tính
toán thống kê mà chúng ta đã biết là ở khối lượng cần tính toán. Khi dữ liệu đã trở
nên khổng lồ thì những khâu như: Thu thập dữ liệu, tiền xử lí và xử lí dữ liệu đều
đòi hỏi phải được tự động hoá. Tuy nhiên ở công đoạn cuối cùng, việc phân tích kết
8
quả sau khi đã khai phá dữ liệu vẫn luôn là công việc của con người.
Do là một lĩnh vực đa ngành, khai phá dữ liệu thu hút các lĩnh vực khoa học
khác như trí tuệ nhân tạo, cơ sở dữ liệu, hiển thị dữ liệu, marketing, toán học, vận
trù học sinh, nhận dạng mẫu, tính toán thống kê…
Điều mà khai phá dữ liệu có thể làm rất tốt là phát hiện ra những giả thuyết
mạnh trước khi sử dụng những công cụ tính toán thống kê. Mô hình dự báo sử dụng
kỹ thuật phân cụm (Crustering) để chia nhóm các sự vật, sự kiện sau đó rút ra các
luật nhằm tìm ra đặc trưng cho mỗi nhóm và cuối cùng đề nghị một mô hình. Ví dụ,
những bạn đọc đăng ký dài hạn của một tạp chí có thể phân nhóm dựa theo nhiều
tiêu trí khác nhau (lứa tuổi, giới tính, thu nhập…), sau đó tạp chí căn cứ vào đặc
trưng riêng của từng nhóm để đề ra mức phí thu trong năm sao cho phù hợp nhất.
Chúng ta thấy, những nhiệm vụ cơ bản nhất của khai phá dữ liệu là:
- Phân cụm, phân loại, phân nhóm, phân lớp. Nhiệm vụ là trả lời câu hỏi; khai
phá luật kết hợp; Lập mô hình dự báo, bao gồm hai nhiệm vụ; Phân tích đối tượng
ngoài cuộc; Phân tích sự tiến hoá.
1.2.3. Triển khai việc khai phá dữ liệu
Nhóm các tác giả CABENAETAL. Đề nghị triển khai quá trình khai phá dữ
liệu theo 5 bước.
Bước 1: Xác định rõ mục tiêu thương mại cần khai phá.
Bước 2: Chuẩn bị dữ liệu (thu thập, tiền xử lí, chuyển đổi khuôn dạng dữ liệu
nếu thấy cần thiết).
Bước 3: Khai phá dữ liệu (chọn thuật toán thích hợp).
Bước 4: Phân tích kết quả thu được (xem có gì thú vị không ?).
Bước 5: Xử lí các tri thức thu lượm được (nhằm đề ra kế hoạch khai thác các
thông tin mới).
9
1.2.4. Một số ứng dụng khai phá dữ liệu
Hiện nay, kỹ thuật khai phá dữ liệu đang được áp dụng một cách rộng rãi trong
rất nhiều lĩnh vực kinh doanh và đời sống khác nhau như:
- Thương mại: Phân tích dữ liệu bán hàng và thị trường, phân tích đầu tư,...
- Thông tin sản xuất: Điều khiển và lập kế hoạch, hệ thống quản lý,...
- Thông tin khoa học: Dự báo thời tiết, cơ sở sản xuất sinh học,...
- Trong y tế marketing, ngân hàng, viễn thông, du lịch, internet,…
1.2.5. Các kỹ thuật khai phá dữ liệu
Các kỹ thuật khai phá dữ liệu thường được chia thành hai nhóm chính:
- Kỹ thuật khai phá dữ liệu mô tả: Có nhiệm vụ mô tả về tính chất hoặc các
đặc tính chung của dữ liệu trong cơ sở dữ liệu hiện có. Các kỹ thuật này gồm có:
Phân cụm (clustering), tóm tắt (summerization), trực quan hoá (visualiztation), phân
tích sự phát triển và độ lệch (evolution and deviation analyst), phân tích luật kết hợp
(association rules)...
- Kỹ rhuật khai phá dữ liệu đoán: Có nhiệm vụ đưa ra các dự đoán dựa vào các
suy diễn trên dữ liệu hiện thời. Các kỹ thuật này gồm có: Phân lớp (classification),
hồi quy (regession)...
Tuy nhiên, chỉ có một số phương pháp thông dụng nhất là: Phân cụm dữ liệu,
phân lớp dữ liệu, phương pháp hồi quy và khai phá kết hợp.
a. Phân cụm dữ liệu: Mục tiêu chính của phương pháp phân cụm dữ liệu là
nhóm các đối tượng tương tự nhau trong tập dữ liệu vào các cụm sao cho các đối
tượng thuộc các cụm khác nhau sẽ không tương đồng. Phân cụm dữ liệu là một ví
dụ của phương pháp học không có thầy. Không giống như phân lớp dữ liệu, phân
cụm dữ liệu không đòi hỏi phải định nghĩa trước các mẫu dữ liệu huấn luyện. Vì thế
có thể coi phân cụm dữ liệu là một cách học bằng quan sát (learning by
observation). Trong phương pháp này bạn không thể biết kết quả các cụm thu được
10
sẽ thế nào khi bắt đầu quá trình. Vì vậy, thông thường cần có một chuyên gia về lĩnh
vực đó để đánh giá các cụm thu được. Phân cụm dữ liệu được sử dụng nhiều trong
các ứng dụng về phân đoạn thị trường, phân đoạn khách hàng, nhận dạng mẫu, phân
loại trang web...Ngoài ra phân cụm dữ liệu còn có thể được sử dụng như một bước
tiền xử lí cho các thuật toán khai phá dữ liệu khác.
b. Phân lớp dữ liệu: Mục tiêu của phương pháp phân lớp dữ liệu là dự đoán
nhãn lớp cho các mẫu dữ liệu. Quá trình phân lớp dữ liệu thường gồm hai bước:
Xây dựng mô hình và sử dụng mô hình để phân lớp dữ liệu.
Bước 1: Một mô hình sẽ được xây dựng dựa trên việc phân tích các mẫu dữ
liệu có sẵn. Mỗi mẫu tương ứng với một lớp, được quyết định bởi một thuộc tính
gọi là thuộc tính lớp. Các lớp dữ liệu này còn được gọi là lớp dữ liệu huấn luyện
(training data set). Các nhãn lớp của tập dữ liệu đều phải được xác định trước khi
xây dựng mô hình.
Bước 2: Sử dụng mô hình để phân lớp dữ liệu. Trước hết chúng ta phải tính độ
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 để dự đoán nhãn lớp cho các mẫu dữ liệu khác trong tương lai.
c. Phương pháp hồi quy: Phương pháp hồi quy khác với phân lớp dữ liệu ở
chỗ: Hồi quy dùng để dự đoán về các giá trị liên tục còn phân lớp dữ liệu chỉ dùng
để dự đoán về các giá trị rời rạc.
Hồi quy là một hàm học ánh xạ mục dữ liệu thành một biến dự đoán có giá trị
thực. Có rất nhiều ứng dụng khai phá dữ liệu với nhiệm vụ hồi quy, chẳng hạn như
khả năng đánh giá tử vong của bệnh nhân khi biết các kết quả. X ét nghiệm, chẩn
đoán, dự đoán nhu cầu tiêu thụ một sản phẩm mới bằng một hàm chỉ tiêu quảng cáo
d. Khai phá luật kết hợp: Mục tiêu của phương pháp này là phát hiện và đưa
ra các mối liên hệ giữa các giá trị dữ liệu trong cơ sở dữ liệu. Một đầu ra của giải
thuật khai phá dữ liệu là luật kết hợp tìm được. Chẳng hạn phân tích cơ sở dữ liệu
bán hàng nhận được thông tin về những khách hàng mua máy tính có khuynh hướng
mua phần mềm quản lý tài chính trong cùng lần mua được miêu tả trong luật kết
11
hợp sau: "Máy tính => Phần mềm quản lý tài chính" (độ hỗ trợ: 2%, độ tin cậy: 60%).
Khai phá luật kết hợp được thực hiện qua hai bước:
Bước1: Tìm tất cả các tập mục phổ biến, một tập mục phổ biến được xác định
qua tính hỗ trợ và thoả mãn độ hỗ trợ cực tiểu.
Bước2: Sinh ra các luật kết hợp mạnh từ tập mục phổ biến, các luật thoả mãn
độ hỗ trợ cực và độ tin cậy cực tiểu.
Phương pháp này được sử dụng rất hiệu quả trong các lĩnh vực như maketing
có chủ đích, phân tích quyết định, quản lý kinh doanh, phân tích giá thị trường...
1.2.6. Kiến trúc của hệ thống khai phá dữ liệu
Như đã trình bày ở trên, khai phá dữ liệu là một giai đoạn trong quá trình phát
hiện tri thức từ số lượng lớn dữ liệu lưu trữ trong các cơ sở dữ liệu, kho dữ liệu
hoặc các kho lưu trữ khác. Bước này có thể tương tác lẫn nhau giữa người sử dụng
và cơ sở tri thức, những mẫu đáng quan tâm được đưa cho người dùng hoặc lưu trữ
như là tri thức mới trong cơ sở tri thức.
Giao diện người dùng
Đánh giá mẫu
Mô tả khai phá dữ liệu
cơ sở tri thức
CSDL hay kho dữ liệu phục
vụ
Cơ sở dữ liệu
Kho dữ liệu
Hình 1.2. Kiến trúc của hệ thống khai phá dữ liệu
Kiến trúc của hệ thống khai phá dữ liệu (Hình 1.2) có các thành phần sau:
- Cơ sở dữ liệu, kho dữ liêụ đó là một hoặc tuyển tập các cơ sở dữ liệu, kho
dữ liệu...Các kĩ thuật làm sạch dữ liệu, lọc dữ liệu có thể thực hiện trên dữ liệu.
- Xem thêm -