1
LỜI CẢM ƠN
Trƣớc hết, tôi xin chân thành cảm ơn tới các thầy cô giáo Trƣờng Đại học Sƣ
phạm Hà Nội 2 đã tận tâm giảng dạy, cung cấp cho tôi kiến thức, phƣơng pháp
nghiên cứu trong khóa học cũng nhƣ trong quá trình thực hiện luận văn.
Đặc biệt tôi xin đƣợc bày tỏ lòng biết ơn sâu sắc đến thầy giáo hƣớng dẫn
PGS.TS Lê Huy Thập, ngƣời đã tận tình hƣớng dẫn, giúp đỡ và động viên để tôi
thực hiện luận văn này.
Xin cảm ơn gia đình, bạn bè và đồng nghiệp đã tạo điều kiện giúp đỡ tôi trong
thời gian tôi thực hiện luận văn.
Mặc dù tôi đã cố gắng nghiên cứu, tìm hiểu đề tài nhƣng vẫn không thể tránh
khỏi những sai sót nhất định, rất mong nhận đƣợc sự đóng góp và chia sẻ của quý
thầy cô và bạn bè.
Tôi xin chân thành cảm ơn.
Hà Nội, tháng 12 năm 2013
TÁC GIẢ LUẬN VĂN
Hoàng Văn Lê
\
2
LỜI CAM ĐOAN
Tôi xin cam đoan toàn bộ nội dung bản luận văn theo đúng nội dung đề
cƣơng. Nội dung luận văn là sự hƣớng dẫn tận tình của PGS. TS Lê Huy Thập và
bản thân tôi tự sƣu tầm, tra cứu và sắp xếp cho phù hợp với nội dung yêu cầu.
Nội dung luận văn này chƣa đƣợc công bố hay xuất bản dƣới bất kỳ hình
thức nào cũng nhƣ không đƣợc sao chép từ tài liệu đã có sẵn và đảm bảo tính chính
xác và thực tiễn.
Tôi xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện luận văn này đã
đƣợc cảm ơn.
Hà Nội, tháng 12 năm 2013
TÁC GIẢ LUẬN VĂN
Hoàng Văn Lê
3
MỤC LỤC
LỜI CẢM ƠN ........................................................................................................................ 1
LỜI CAM ĐOAN .................................................................................................................. 2
MỤC LỤC ............................................................................................................................. 3
DANH MỤC CÁC KÝ HIỆU VÀ CÁC CHỮ VIẾT TẮT ................................................... 5
DANH MỤC CÁC HÌNH VẼ ............................................................................................... 6
DANH MỤC CÁC BẢNG .................................................................................................... 7
PHẦN MỞ ĐẦU ................................................................................................................... 8
CHƢƠNG 1 TỔNG QUAN ................................................................................................ 10
1.1 KHAI PHÁ DỮ LIỆU ............................................................................................. 10
1.1.1 Định nghĩa khai phá dữ liệu ............................................................................... 10
1.1.2 Các ứng dụng của khai phá dữ liệu .................................................................... 10
1.1.3 Các bƣớc của quá trình khai phá dữ liệu ........................................................... 11
1.1.4 Nhiệm vụ chính trong khai phá dữ liệu ............................................................. 13
1.1.5 Các phƣơng pháp khai phá dữ liệu .................................................................... 15
1.1.6 Lợi thế cuả khai phá dữ liêu so với phƣơng pháp khác ..................................... 18
1.1.7 Lựa chọn phƣơng pháp ...................................................................................... 21
1.2 HỆ CHUYÊN GIA .................................................................................................. 22
1.2.1 Khái niệm Hệ chuyên gia................................................................................... 22
1.2.2 Kiến trúc tổng quát của các hệ chuyên gia ........................................................ 23
1.2.3 Các kĩ thuật thể hiện tri thức .............................................................................. 27
1.3 KẾT LUẬN CHƢƠNG ........................................................................................... 29
CHƢƠNG 2 HỖ TRỢ HỆ CHUYÊN GIA TRONG KHAI LUẬT KẾT HỢP .................. 30
2.1 PHƢƠNG PHÁP TÌM LUẬT KẾT HỢP TRONG KHAI PHÁ DỮ LIỆU ............ 30
2.1.1 Vài nét về khai phá luật kết hợp ........................................................................ 30
2.1.2 Luật kết hợp ....................................................................................................... 30
4
2.1.3 Thuật toán Apriorid ........................................................................................... 33
2.1.4 Thuật toán AprioriTID ...................................................................................... 39
2.1.5 Thuật toán AprioriHybrid .................................................................................. 43
2.1.6 Thuật toán K-Nearest Neighbors ....................................................................... 44
2.1.7 Thuật toán K-Means .......................................................................................... 45
2.2 CÁC PHƢƠNG PHÁP SUY LUẬT KHÔNG CHẮC CHẮN TRONG HCG…………48
2.2.1 Tổng quan về lý thuyết chắc chắn ..................................................................... 48
2.2.2 Cơ sở của lý thuyết chắc chắn ........................................................................... 49
2.2.3 Nhân tố chắc chắn dƣới khía cạnh xác suất ....................................................... 53
2.2.4 Lan truyền chắc chắn ......................................................................................... 53
2.2.5 Phƣơng pháp suy luận không chắc chắn trong Hệ chuyên gia .......................... 57
2.3 THỂ HIỆN ĐỘ CHẮC CHẮN CF TRONG SỰ KIỆN VÀ TRONG KHAI
PHÁ LUẬT KẾT HỢP ....................................................................................................... 61
2.3.1 Tập luật sau khai phá luật kết hợp ..................................................................... 61
2.3.2 Thể hiện độ chắc chắn CF trong sự kiện và luật khai phá kết hợp .................... 61
2.4 KẾT LUẬT CHƢƠNG ............................................................................................ 62
CHƢƠNG 3 ỨNG DỤNG HỖ TRỢ HCG TRONG KPDL TẠI SIÊU THỊ BÁN SÁCH . 64
3.1 LẬP TRÌNH ỨNG DỤNG TẠI SIÊU THỊ BÁN SÁCH ........................................ 64
3.1.1 Giới thiệu bài toán ............................................................................................. 64
3.1.2 Tóm tắt và phân tích và thiết kế hệ thống .......................................................... 64
3.2 CÁC GIAO DIỆN VÀ KẾT QUẢ CỦA CHƢƠNG TRÌNH ................................. 66
KẾT LUẬN.......................................................................................................................... 70
TÀI LIỆU THAM KHẢO ................................................................................................... 71
5
DANH MỤC CÁC KÝ HIỆU VÀ CÁC CHỮ VIẾT TẮT
Ý nghĩa
Ký hiệu, chữ viết tắt
Candidate itemset
Một itemset trong tập Ck đƣợc sử dụng để sinh ra
các large itemset
Ck
Tập các candidate k-itemset ở giai đoạn thứ k
Confidence
Độ tin cậy của luật kết hợp
CSDL
Cơ sở dữ liệu
HCG
Hệ chuyên gia
DM
Data mining- Khai phá dữ liệu
Frequent/large itemset
Một intemset có độ hỗ trợ (support)>= ngƣỡng độ
hỗ trợ tối thiểu
CF
Certainty factor
ID
Indentifier
Item
Một phần tử của Itemset
Itemset
Tập của các item
k-itemset
Một itemset có độ dài k
Lk
Tập các large itemset ở giai đoạn thứ k
TID
Transaction Indentifier
Transaction
Giao dịch
Classification
Phân loại
Candidate
Dự tuyển
6
DANH MỤC CÁC HÌNH VẼ
Ý nghĩa
Hình
Trang
Hình 1.1
Quy trình phát hiện tri thức
12
Hình 1.2
Hoạt động của hệ chuyên gia
23
Hình 1.3
Những thành phần cơ bản của một hệ chuyên gia
24
Hình 1.4
Quan hệ giữa máy suy diễn và cơ sở tri thức
25
Hình 1.5
Kiến trúc hệ chuyên gia theo J.Emine
26
Hình 1.6
Kiến trúc hệ chuyên gia theo C. Ernest
26
Hình 2.1
Query Point phân lớp
47
Hình 2.2
Thiết kế xác định danh giới các cụm ban đầu
48
Hình 2.3
Tính toán trọng tâm các cụm mới
48
Hình 2.4
Phạm vi của giá trị CF
53
Hình 3.1
Mô hình quan hệ thực thể
68
Hình 3.2
Sơ đồ giữ liệu quan hệ
69
Hình 3.3
Các giao dịch chính
70
Hình 3.4
Các giao dịch trong cơ sở dữ liệu
70
Hình 3.5
Thể hiện độ hỗ trợ tối thiểu và độ tin cậy tối thiểu
71
Hình 3.6
Thể hiện độ hỗ trợ tối thiểu và độ tin cậy tối thiểu khác
72
Hình 3.7
Thể hiện độ chắc chắn của luật
72
Hình 3.8
Kết quả chƣơng trình
73
7
DANH MỤC CÁC BẢNG
Ý nghĩa
Bảng
Trang
Bảng 2.1
Các mặt hàng và nhãn
38
Bảng 2.2
Các giao dịch
38
Bảng 2.3
Ứng viên C1
39
Bảng 2.4
Ứng viên L1
39
Bảng 2.5
Ứng viên C2
39
Bảng 2.6
Ứng viên C2
39
Bảng 2.7
Ứng viên C2
39
Bảng 2.8
Ứng viên L2
39
Bảng 2.9
Ứng viên C3
40
Bảng 2.10 Miêu tả giá trí CF
55
8
PHẦN MỞ ĐẦU
1. Lý do chọn đề tài
Để tìm ra các luật kết hợp trong khai phá dữ liệu, cơ bản dựa vào độ hỗ trợ Sup
(Suport) và độ tin cậy Conf (Confidence), nhƣng những tham số này phải đƣợc xác
định qua kinh nghiệm hay qua phƣơng pháp chuyên gia. Dù bằng cách nào thì độ
khả tín của các luật cũng ở mức độ tham khảo nào đó. Để tăng độ tin cậy vào các
luật đã tìm đƣợc chúng ta có thể dùng phƣơng pháp hỗ trợ thêm của hệ chuyên gia.
Từng chuyên đề trên thì thế giới và Việt Nam đã có sự quan tâm nghiên cứu, nhƣng
sự kết hợp gữa hai chuyên đề theo cách nêu ra trên thì chƣa.
Chúng ta sẽ dùng phƣơng pháp bổ sung nhân tố chắc chắn CF cho cả các sự
kiện, luật,… để tăng độ khả tín cho các luật kết hợp đã nhận đƣợc bằng phƣơng
pháp khai phá luật kết hợp.
2. Mục đích nghiên cứu (Các kết quả cần đạt đƣợc)
Dùng suy luận không chắc chắn để hỗ trợ khai phá luật kết hợp
Lập trình thể hiện luật kết hợp có hỗ trợ phƣơng pháp suy luận không chắc
chắn tại siêu thị bán sách
3. Nhiệm vụ nghiên cứu
Nghiên cứu khai phá dữ liệu có hỗ trợ của hệ chuyên gia.
4. Đối tƣợng và phạm vi nghiên cứu
Khai phá dữ liệu
Hệ chuyên gia
5. Giả thuyết khoa học
Dùng hệ chuyên gia, Trí tuệ nhân tạo,… để hỗ trợ khi nâng cao và mở rộng đề
tài.
6. Phƣơng pháp nghiên cứu
Phƣơng pháp tìm luật kết hợp trong khai phá dữ liệu
Các phƣơng pháp suy luận không chắc chắn trong hệ chuyên gia.
Thể hiện độ chắc chắn CF trong sự kiện và luật khai phá kết hợp
9
Nội dung luận văn gồm 3 chƣơng
Chƣơng 1. Tổng quan
1.1 Khai phá dữ liệu
1.2 Hệ chuyên gia
1.3 Kết luận chƣơng
Chƣơng 2. Hỗ trợ hệ chuyên gia trong khai phá luật kết hợp
2.1 Phƣơng pháp tìm luật kết hợp trong khai phá dữ liệu
2.2 Các phƣơng pháp suy luận không chắc chắn trong hệ chuyên gia.
2.3 Thể hiện độ chắc chắn CF trong sự kiện và luật khai phá kết hợp
2.4 Kết luận
Chƣơng 3. Ứng dụng hỗ trợ hệ chuyên gia trong khai phá luật kết hợp tại siêu
thị bán sách
3.1. Lập trình ứng dụng tại siêu thị bán sách
3.2. Các giao diện và kết quả của chƣơng trình ứng dụng
10
CHƢƠNG 1
TỔNG QUAN
1.1 KHAI PHÁ DỮ LIỆU
1.1.1 Định nghĩa khai phá dữ liệu
Khai phá dữ liệu đƣợc dùng để mô tả quá trình phát hiện ra tri thức trong cơ sở
dữ liệu. Quá trình này kết xuất ra các tri thức tiềm ẩn từ dữ liệu giúp cho việc dự
báo trong kinh doanh, các hoạt động sản xuất, ... Khai phá dữ liệu làm giảm chi phí
về thời gian so với phƣơng pháp truyền thống trƣớc kia (ví dụ nhƣ phƣơng pháp
thống kê). Sau đây là các định nghĩa mang tính mô tả của nhiều tác giả về khai phá
dữ liệu:
Định nghĩa của Ferruzza: “Khai phá dữ liệu là tập hợp các phƣơng pháp đƣợc
dùng trong tiến trình khám phá tri thức để chỉ ra sự khác biệt các mối quan hệ và
các mẫu chƣa biết bên trong dữ liệu”.
Định nghĩa của Parsaye: “Khai phá dữ liệu là quá trình trợ giúp quyết định,
trong đó chúng ta tìm kiếm các mẫu thông tin chƣa biết và bất ngờ trong cơ sở dữ
liệu lớn”.
Định nghĩa của Fayyad: “Khai phá dữ liệu là một quá trình không tầm thƣờng
nhận ra những mẫu dữ liệu có giá trị, mới, hữu ích, tiềm năng và có thể hiểu đƣợc”.
1.1.2 Các ứng dụng của khai phá dữ liệu
Phát hiện tri thức và khai phá dữ liệu liên quan đến nhiều ngành, nhiều lĩnh
vực: thống kê, trí tuệ nhân tạo, cơ sở dữ liệu, thuật toán, tính toán song song ... Đặc
biệt phát hiện tri thức và khai phá dữ liệu rất gần gũi với lĩnh vực thống kê, sử dụng
các phƣơng pháp thống kê để mô hình hóa dữ liệu và phát hiện các mẫu. Khai phá
dữ liệu có nhiều ứng dụng trong thực tế, ví dụ nhƣ:
Bảo hiểm, tài chính và thị trƣờng chứng khoán: phân tích tình hình tài chính
và dự báo giá của các loại cổ phiếu trong thị trƣờng chứng khoán. Danh mục vốn và
giá, lãi suất, dữ liệu thẻ tín dụng, phát hiện gian lận, ...
Thống kê, phân tích dữ liệu và hỗ trợ ra quyết định.
11
Điều trị y học và chăm sóc y tế: một số thông tin về chuẩn đoán bệnh đƣợc
lƣu trong các hệ thống quản lý bệnh viện. Phân tích mối liên hệ giữa các triệu chứng
bệnh, chuẩn đoán và phƣơng pháp điều trị.
Sản xuất và chế biến: các quy trình, phƣơng pháp chế biến và xử lý sự cố.
Text mining và Web mining: phân lớp văn bản và các trang Web, tóm tắt văn bản.
Lĩnh vực khoa học: quan sát thiên văn, dữ liệu sinh vật học, dữ liệu gene, tìm
kiếm, so sánh các hệ gene và thông tin di truyền, mối liên hệ gene và một số bệnh di
truyền, ...
Mạng viễn thông: phân tích các cuộc gọi điện thoại và hệ thống giám sát lỗi,
sự cố, chất lƣợng dịch vụ, ...
1.1.3 Các bƣớc của quá trình khai phá dữ liệu
Quy trình phát hiện tri thức thƣờng tuân theo các bƣớc sau:
Bƣớc thứ nhất: Hình thành, xác định và định nghĩa bài toán. Là tìm hiểu
lĩnh vực ứng dụng từ đó hình thành bài toán, xác định các nhiệm vụ cần phải
hoàn thành. Bƣớc này sẽ quyết định cho việc rút ra đƣợc các tri thức hữu ích và
cho phép chọn các phƣơng pháp khai phá dữ liệu thích hợp với mục đích ứng
dụng và bản chất của dữ liệu.
Bƣớc thứ hai: Thu thập và tiền xử lý dữ liệu. Là thu thập và xử lý thô, còn
đƣợc gọi là tiền xử lý dữ liệu nhằm loại bỏ nhiễu (làm sạch dữ liệu), xử lý việc thiếu
dữ liệu (làm giàu dữ liệu), biến đổi dữ liệu và rút gọn dữ liệu nếu cần thiết, bƣớc
này thƣờng chiếm nhiều thời gian nhất trong toàn bộ qui trình phát hiện tri thức. Do
dữ liệu đƣợc lấy từ nhiều nguồn khác nhau, không đồng nhất, … có thể gây ra các
nhầm lẫn. Sau bƣớc này, dữ liệu sẽ nhất quán, đầy đủ, đƣợc rút gọn và rời rạc hoá.
12
Hình 1.1. Quy trình phát hiện tri thức
Bƣớc thứ ba: Khai phá dữ liệu, rút ra các tri thức.Là khai phá dữ liệu, hay nói
cách khác là trích ra các mẫu hoặc/và các mô hình ẩn dƣới các dữ liệu. Giai đoạn
này rất quan trọng, bao gồm các công đoạn nhƣ: chức năng, nhiệm vụ và mục đích
của khai phá dữ liệu, dùng phƣơng pháp khai phá nào? Thông thƣờng, các bài toán
khai phá dữ liệu bao gồm: các bài toán mang tính mô tả - đƣa ra tính chất chung
nhất của dữ liệu, các bài toán dự báo - bao gồm cả việc phát hiện các suy diễn dựa
trên dữ liệu hiện có. Tùy theo bài toán xác định đƣợc mà ta lựa chọn các phƣơng
pháp khai phá dữ liệu cho phù hợp.
Bƣớc thứ tƣ: Là hiểu tri thức đã tìm đƣợc, đặc biệt là làm sáng tỏ các mô tả và
dự đoán. Các bƣớc trên có thể lặp đi lặp lại một số lần, kết quả thu đƣợc có thể
đƣợc lấy trung bình trên tất cả các lần thực hiện.
Bƣớc thứ năm: Sử dụng các tri thức phát hiện đƣợc. Là hiểu tri thức đã tìm
đƣợc, đặc biệt là làm sáng tỏ các mô tả và dự đoán. Các bƣớc trên có thể lặp đi lặp
lại một số lần, kết quả thu đƣợc có thể đƣợc lấy trung bình trên tất cả các lần thực
hiện. Các kết quả của quá trình phát hiện tri thức có thể đƣợc đƣa và ứng dụng trong
các lĩnh vực khác nhau. Do các kết quả có thể là các dự đoán hoặc các mô tả nên
chúng có thể đƣợc đƣa vào các hệ thống hỗ trợ ra quyết định nhằm tự động hoá quá
trình này.
Tóm lại: Khai phá dữ liệu là một quá trình kết xuất ra tri thức từ kho dữ liệu
mà trong đó khai phá dữ liệu là công đoạn quan trọng nhất.
13
1.1.4 Nhiệm vụ chính trong khai phá dữ liệu
Quá trình khai phá dữ liệu là quá trình phát hiện ra mẫu thông tin. Trong đó,
giải thuật khai phá tìm kiếm các mẫu đáng quan tâm theo dạng xác định nhƣ các
luật, phân lớp, hồi quy, cây quyết định, ...
Nhiệm vụ chính trong khai phá dữ liệu bao gồm: phân lớp, hồi qui, phân
nhóm, tổng hợp, mô hình hoá sự phụ thuộc và phát hiện sự biến đổi và độ lệch.
1.1.4.1 Phân lớp (phân loại – classification)
Là việc xác định một ánh xạ để ánh xạ các mẫu dữ liệu thỏa mãn ràng
buộc nào đó vào cùng một lớp, do đó dữ liệu sẽ đƣợc phân thành các lớp có thể
giao nhau hoặc không.
Mục tiêu của thuật toán phân lớp là tìm ra mối quan hệ nào đó giữa thuộc tính
dự báo và thuộc tính phân lớp. Nhƣ thế quá trình phân lớp có thể sử dụng mối quan
hệ này để dự báo cho các mục mới. Các kiến thức đƣợc phát hiện biểu diễn dƣới
dạng các luật theo cách sau: “Nếu các thuộc tính dự báo của một mục thoả mãn điều
kiện của các tiền đề thì mục nằm trong lớp chỉ ra trong kết luận”.
Ví dụ 1.1: Một mục biểu diễn thông tin về nhân viên có các thuộc tính dự báo
là: họ tên, tuổi, giới tính, trình độ học vấn, … và thuộc tính phân loại là trình độ
lãnh đạo của nhân viên.
1.1.4.2 Hồi qui (regression)
Là việc dùng một hàm dự báo để từ các mẫu dữ liệu đã có hàm dự báo sẽ cho
một giá trị thực. Nhiệm vụ của hồi qui tƣơng tự nhƣ phân lớp, điểm khác nhau
chính là ở chỗ thuộc tính để dự báo là liên tục chứ không phải rời rạc. Việc dự báo
các giá trị số thƣờng đƣợc làm bởi các phƣơng pháp thống kê cổ điển, chẳng hạn
nhƣ hồi quy tuyến tính. Tuy nhiên, phƣơng pháp mô hình hoá cũng đƣợc sử dụng, ví
dụ nhƣ cây quyết định.
Ứng dụng của hồi quy là rất nhiều: dự báo thời tiết, ƣớc lƣợng xác suất ngƣời
bệnh có thể chết bằng cách kiểm tra các triệu chứng; dự báo nhu cầu của ngƣời
dùng đối với một sản phẩm.
14
1.1.4.3 Phân nhóm (clustering)
Là việc mô tả chung để tìm ra các tập hay các nhóm, loại mô tả dữ liệu. Các
nhóm có thể tách nhau hoặc phân cấp hay gối lên nhau. Có nghĩa là dữ liệu có thể
vừa thuộc nhóm này lại vừa thuộc nhóm khác. Các ứng dụng khai phá dữ liệu có
nhiệm vụ phân nhóm nhƣ phát hiện tập các khách hàng có phản ứng giống nhau
trong cơ sở dữ liệu tiếp thị; xác định các quang phổ từ các phƣơng pháp đo tia hồng
ngoại, … Liên quan chặt chẽ đến việc phân nhóm là nhiệm vụ đánh giá dữ liệu, hàm
mật độ xác suất đa biến/ các trƣờng trong cơ sở dữ liệu.
1.1.4.4 Tổng hợp (summarization)
Là công việc liên quan đến các phƣơng pháp tìm kiếm một mô tả tập con dữ
liệu. Kỹ thuật tổng hợp thƣờng áp dụng trong việc phân tích dữ liệu có tính thăm dò
và báo cáo tự động.
Nhiệm vụ chính là sản sinh ra các mô tả đặc trƣng cho một lớp. Mô tả loại
này là một kiểu tổng hợp, tóm tắt các đặc tính chung của tất cả hay hầu hết các mục
của một lớp. Các mô tả đặc trƣng thể hiện theo luật có dạng sau: “Nếu một mục
thuộc về lớp đã chỉ trong tiền đề thì mục đó có tất cả các thuộc tính đã nêu trong kết
luận”. Lƣu ý rằng luật dạng này có các khác biệt so với luật phân lớp. Luật phát
hiện đặc trƣng cho lớp chỉ sản sinh khi các mục đã thuộc về lớp đó.
1.1.4.5 Mô hình hoá sự phụ thuộc (dependency modeling)
Là việc tìm kiếm một mô hình mô tả sự phụ thuộc giữa các biến, thuộc tính
theo hai mức:
Mức 1: Mức cấu trúc của mô hình mô tả (thƣờng dƣới dạng đồ thị). Trong đó,
các biến phụ thuộc bộ phận vào các biến khác.
Mức 2: Mức định lƣợng mô hình mô tả mức độ phụ thuộc. Những phụ thuộc này
thƣờng đƣợc biểu thị dƣới dạng theo luật “nếu - thì” (nếu tiền đề là đúng thì kết luận
đúng). Về nguyên tắc, cả tiền đề và kết luận đều có thể là sự kết hợp logic của các giá
trị thuộc tính. Trên thực tế, tiền đề thƣờng là nhóm các giá trị thuộc tính và kết luận chỉ
là một thuộc tính. Hơn nữa hệ thống có thể phát hiện các luật phân lớp trong đó tất cả
các luật cần phải có cùng một thuộc tính do ngƣời dùng chỉ ra trong kết luận.
15
Quan hệ phụ thuộc cũng có thể biểu diễn dƣới dạng mạng tin cậy Bayes. Đó
là đồ thị có hƣớng, không chu trình. Các nút biểu diễn thuộc tính và trọng số của
liên kết phụ thuộc giữa các nút đó.
1.1.4.6 Phát hiện sự biến đổi và độ lệch (change and deviation dectection)
Hai mô hình độ lệch hay dùng là lệch theo thời gian hay lệch theo nhóm. Độ
lệch theo thời gian là sự thay đổi có ý nghĩa của dữ liệu theo thời gian. Độ lệch theo
nhóm là sự khác nhau của giữa dữ liệu trong hai tập con dữ liệu, ở đây tính cả
trƣờng hợp tập con dữ liệu này thuộc tập con kia, nghĩa xác định dữ liệu trong một
nhóm con của đối tƣợng có khác đáng kể so với toàn bộ đối tƣợng không? Theo
cách này, sai sót dữ liệu hay sai lệch so với giá trị thông thƣờng đƣợc phát hiện.
Vì những nhiệm vụ này yêu cầu số lƣợng và các dạng thông tin rất khác nhau
nên chúng thƣờng ảnh hƣởng đến việc thiết kế và chọn phƣơng pháp khai phá dữ
liệu khác nhau. Ví dụ nhƣ phƣơng pháp cây quyết định (sẽ đƣợc trình bày mục
1.1.5.3) tạo ra đƣợc một mô tả phân biệt đƣợc các mẫu giữa các lớp nhƣng không
có tính chất và đặc điểm của lớp.
1.1.5 Các phƣơng pháp khai phá dữ liệu
1.1.5.1 Phƣơng pháp suy diễn / quy nạp
Phƣơng pháp suy diễn: Nhằm rút ra thông tin là kết quả logic của các thông
tin trong cơ sở dữ liệu. Ví dụ nhƣ toán tử liên kết áp dụng cho bảng quan hệ, bảng
đầu chứa thông tin về các nhân viên và phòng ban, bảng thứ hai chứa các thông tin
về các phòng ban và các trƣởng phòng. Nhƣ vậy sẽ suy ra đƣợc mối quan hệ giữa
các nhân viên và các trƣởng phòng. Phƣơng pháp suy diễn dựa trên các sự kiện
chính xác để suy ra các tri thức mới từ các thông tin cũ. Mẫu chiết xuất đƣợc bằng
cách sử dụng phƣơng pháp này thƣờng là các luật suy diễn.
Phƣơng pháp quy nạp: Phƣơng pháp quy nạp suy ra các thông tin đƣợc sinh ra
từ cơ sở dữ liệu. Có nghĩa là nó tự tìm kiếm, tạo mẫu và sinh ra tri thức chứ không
phải bắt đầu với các tri thức đã biết trƣớc. Các thông tin mà phƣơng pháp này đem
lại là các thông tin hay các tri thức cấp cao diễn tả về các đối tƣợng trong cơ sở dữ
16
liệu. Phƣơng pháp này liên quan đến việc tìm kiếm các mẫu trong cơ sở dữ liệu.
Trong khai phá dữ liệu, quy nạp đƣợc sử dụng trong cây quyết định và tạo luật.
1.1.5.2 Phƣơng pháp K-láng giềng gần
Sự miêu tả các bản ghi trong tập dữ liệu khi trỏ vào không gian nhiều chiều là
rất có ích đối với việc phân tích dữ liệu. Việc dùng các miêu tả này, nội dung của
vùng lân cận đƣợc xác định, trong đó các bản ghi gần nhau trong không gian đƣợc
xem xét thuộc về lân cận (hàng xóm–láng giềng) của nhau. Khái niệm này đƣợc
dùng trong khoa học kỹ thuật với tên gọi K-láng giềng gần, trong đó K là số láng
giềng đƣợc sử dụng. Phƣơng pháp này rất hiệu quả nhƣng lại đơn giản. Ý tƣởng
thuật toán học K-láng giềng gần là “thực hiện nhƣ các láng giềng gần của bạn trong
đời sống hàng ngày”.
Ví dụ 1.2: Để dự đoán hoạt động của cá thể xác định, K-láng giềng tốt nhất
của cá thể đƣợc xem xét, và trung bình các hoạt động của các láng giềng gần đƣa ra
đƣợc dự đoán về hoạt động của cá thể đó [4, 6].
Kỹ thuật K-láng giềng gần là một phƣơng pháp tìm kiếm đơn giản. Tuy nhiên,
nó có một số mặt hạn chế giới là hạn phạm vi ứng dụng của nó. Đó là thuật toán này
có độ phức tạp tính toán là luỹ thừa bậc 2 theo số bản ghi của tập dữ liệu.
Vấn đề chính liên quan đến thuộc tính của bản ghi. Một bản ghi gồm nhiều
thuộc tính độc lập, nó bằng một điểm trong không gian tìm kiếm có số chiều lớn.
Trong các không gian có số chiều lớn, giữa hai điểm bất kỳ hầu nhƣ có cùng
khoảng cách. Vì thế mà kỹ thuật K-láng giềng không cho ta thêm một thông tin có
ích nào, khi hầu hết các cặp điểm đều là các láng giềng. Cuối cùng, phƣơng pháp Kláng giềng không đƣa ra lý thuyết để hiểu cấu trúc dữ liệu. Hạn chế đó có thể đƣợc
khắc phục bằng kỹ thuật cây quyết định.
1.1.5.3 Phƣơng pháp sử dụng cây quyết định và luật
Với kỹ thuật phân lớp dựa trên cây quyết định, kết quả của quá trình xây dựng mô
hình sẽ cho ra một cây quyết định. Cây này đƣợc sử dụng trong quá trình phân lớp các
đối tƣợng dữ liệu chƣa biết hoặc đánh giá độ chính xác của mô hình. Tƣơng ứng với hai
giai đoạn trong quá trình phân lớp là quá trình xây dựng và sử dụng cây quyết định.
17
Quá trình xây dựng cây quyết định bắt đầu từ một nút đơn biểu diễn tất cả các
mẫu dữ liệu. Sau đó, các mẫu sẽ đƣợc phân chia một cách đệ quy dựa vào việc lựa
chọn các thuộc tính. Nếu các mẫu có cùng một lớp thì nút sẽ trở thành lá, ngƣợc lại ta
sử dụng một độ đo thuộc tính để chọn ra thuộc tính tiếp theo làm cơ sở để phân chia
các mẫu ra các lớp. Theo từng giá trị của thuộc tính vừa chọn, ta tạo ra các nhánh
tƣơng ứng và phân chia các mẫu vào các nhánh đã tạo. Lặp lại quá trình trên cho tới
khi tạo ra đƣợc cây quyết định, tất cả các nút triển khai thành lá và đƣợc gán nhãn.
Quá trình đệ quy sẽ dừng lại khi một trong các điều kiện sau đƣợc thỏa mãn:
- Tất cả các mẫu thuộc cùng một nút.
- Không còn một thuộc tính nào để lựa chọn.
- Nhánh không chứa mẫu nào.
Phần lớn các giải thuật sinh cây quyết định đều có hạn chế chung là sử dụng
nhiều bộ nhớ. Lƣợng bộ nhớ sử dụng tỷ lệ thuận với kích thƣớc của mẫu dữ liệu
huấn luyện. Một chƣơng trình sinh cây quyết định có hỗ trợ sử dụng bộ nhớ ngoài
song lại có nhƣợc điểm về tốc độ thực thi. Do vậy, vấn đề tỉa bớt cây quyết định trở
nên quan trọng. Các nút lá không ổn định trong cây quyết định sẽ đƣợc tỉa bớt. Kỹ
thuật tỉa trƣớc là việc dừng sinh cây quyết định khi chia dữ liệu không có ý nghĩa.
1.1.5.4 Phƣơng pháp phát hiện luật kết hợp
Phƣơng pháp này nhằm phát hiện ra các luật kết hợp giữa các thành phần dữ
liệu trong cơ sở dữ liệu. Mẫu đầu ra của giải thuật khai phá dữ liệu là tập luật kết
hợp tìm đƣợc. Ta có thể lấy một ví dụ đơn giản về luật kết hợp nhƣ sau: sự kết hợp
giữa hai thành phần A và B có nghĩa là sự xuất hiện của A trong bản ghi kéo theo sự
xuất hiện của B trong cùng bản ghi đó: A => B.
Cho một lƣợc đồ R = {A1, …, Ap} các thuộc tính với miền giá trị {0,1}, và
một quan hệ r trên R. Một luật kết hợp trên r đƣợc mô tả dƣới dạng X=>B với X
R và B
R\X. Về mặt trực giác, ta có thể phát biểu ý nghĩa của luật nhƣ sau: Nếu
một bản ghi của bảng r có giá trị 1 tại mỗi thuộc tính thuộc X thì giá trị của thuộc
tính B cũng là 1 trong cùng bản ghi đó. Ví dụ nhƣ ta có tập cơ sở dữ liệu về các mặt
hàng bán trong siêu thị, các dòng tƣơng ứng với các ngày bán hàng, các cột tƣơng
18
ứng với các mặt hàng thì giá trị 1 tại ô (20/10, bánh mì) xác định rằng bánh mì đã
bán ngày hôm đó cũng kéo theo sự xuất hiện giá trị 1 tại ô (20/10, bơ).
Cho W
R, đặt s(W, r) là tần số xuất hiện của W trong r đƣợc tính bằng tỷ lệ
của các hàng trong r có giá trị 1 tại mỗi cột thuộc W. Tần số xuất hiện của luật
X=>B trong r đƣợc định nghĩa là s(X
cậy của luật là s(X
{B}, r) còn gọi là độ hỗ trợ của luật, độ tin
{B}, r)/s(X, r). Ở đây X có thể gồm nhiều thuộc tính, B là giá
trị không cố định. Nhờ vậy mà không xảy ra việc tạo ra các luật không mong muốn
trƣớc khi quá trình tìm kiếm bắt đầu. Điều đó cũng cho thấy không gian tìm kiếm có
kích thƣớc tăng theo hàm mũ của số lƣợng các thuộc tính ở đầu vào. Do vậy cần
phải chú ý khi thiết kế dữ liệu cho việc tìm kiếm các luật kết hợp.
Nhiệm vụ của việc phát hiện các luật kết hợp là phải tìm tất cả các luật X=>B
sao cho tần số của luật không nhỏ hơn ngƣỡng σ cho trƣớc và độ tin cậy của luật
không nhỏ hơn ngƣỡng θ cho trƣớc. Từ một cơ sở dữ liệu ta có thể tìm đƣợc hàng
nghìn và thậm chí hàng trăm nghìn các luật kết hợp.
Ta gọi một tập con X
R là thƣờng xuyên trong r nếu thỏa mãn điều kiện
s(X,r) ≥ σ. Nếu biết tất cả các tập thƣờng xuyên trong r thì việc tìm kiếm các luật rất
dễ dàng. Vì vậy, giải thuật tìm kiếm các luật kết hợp trƣớc tiên đi tìm tất cả các tập
thƣờng xuyên này, sau đó tạo dựng dần các luật kết hợp bằng cách ghép dần các tập
thuộc tính dựa trên mức độ thƣờng xuyên.
Các luật kết hợp có thể là một cách hình thức hóa đơn giản. Chúng rất thích
hợp cho việc tạo ra các kết quả có dữ liệu dạng nhị phân. Giải thuật tìm kiếm các
luật kết hợp tạo ra số luật ít nhất phải bằng với số các tập phổ biến và nếu nhƣ một
tập phổ biến có kích thƣớc K thì phải có ít nhất là 2K tập phổ biến. Thông tin về các
tập phổ biến đƣợc sử dụng để ƣớc lƣợng độ tin cậy của các tập luật kết hợp.
1.1.6 Lợi thế cuả khai phá dữ liêu so với phƣơng pháp khác
1.1.6.1 Học máy (Machine Learning)
Mặc dù ngƣời ta đã cố gắng cải tiến các phƣơng pháp học máy để có thể phù
hợp với mục đích khai phá dữ liệu nhƣng sự khác biệt giữa cách thiết kế, các đặc
19
điểm của cơ sở dữ liệu đã làm cho phƣơng pháp học máy trở nên không phù hợp
với mục đích này, mặc dù cho đến nay, phần lớn các phƣơng pháp khai phá dữ
liệu vẫn đựa trên nền tảng cơ sở của phƣơng pháp học máy. Những phân tích sau
đây sẽ cho thấy điều đó. Trong quản trị cơ sở dữ liệu, một cơ sở dữ liệu là một
tập hợp đƣợc tích hợp một cách logic của dữ liệu đƣợc lƣu trong một hay nhiều
tệp và đƣợc tổ chức để lƣu trữ có hiệu quả, sửa đổi và lấy thông tin liên quan
đƣợc dễ dàng. Ví dụ nhƣ trong cơ sở dữ liệu quan hệ, dữ liệu đƣợc tổ chức thành
các tệp hoặc các bảng có các bản ghi có độ dài cố định. Mỗi bản ghi là một danh
sách có thứ tự các giá trị, mỗi giá trị đƣợc đặt vào một trƣờng. Thông tin về tên
trƣờng và giá trị của trƣờng đƣợc đặt trong một tệp riêng gọi là thƣ viện dữ liệu
(data dictionary). Một hệ thống quản trị cơ sở dữ liệu sẽ quản lý các thủ tục
(procedures) để lấy, lƣu trữ, và xử lý dữ liệu trong các cơ sở dữ liệu đó. Trong
học máy, thuật ngữ cơ sở dữ liệu chủ yếu đề cập đến một tập các mẫu (instance
hay example) đƣợc lƣu trong một tệp. Các mẫu thƣờng là các vector đặc điểm có
độ dài cố định. Thông tin về các tên đặc điểm, dãy giá trị của chúng đôi khi cũng
đƣợc lƣu lại nhƣ trong từ điển dữ liệu. Một giải thuật học còn sử dụng tập dữ
liệu và các thông tin kèm theo tập dữ liệu đó làm đầu vào và đầu ra biểu thị kết
quả của việc học (ví dụ nhƣ một khái niệm).
Với so sánh cơ sở dữ liệu thông thƣờng và cơ sở dữ liệu trong học máy nhƣ
trên, có thể thấy là học máy có khả năng đƣợc áp dụng cho cơ sở dữ liệu, bởi vì
không phải học trên tập các mẫu mà học trên tệp các bản ghi của cơ sở dữ liệu.
Tuy nhiên, phát hiện tri thức trong cơ sở dữ liệu làm tăng thêm các vấn đề vốn
đã là điển hình trong học máy và đã quá khả năng của học máy. Trong thực tế, cơ sở
dữ liệu thƣờng động, không đầy đủ, bị nhiễu, và lớn hơn nhiều so với tập các dữ
liệu học máy điển hình. Các yếu tố này làm cho hầu hết các giải thuật học máy trở
nên không hiệu quả trong hầu hết các trƣờng hợp. Vì vậy trong khai phá dữ liệu,
cần tập trung rất nhiều công sức vào việc vƣợt qua những khó khăn, phức tạp này
trong cơ sở dữ liệu.
20
1.1.6.2 Phƣơng pháp hệ chuyên gia
Các hệ chuyên gia cố gắng nắm bắt các tri thức thích hợp với bài toán nào đó.
Các kỹ thuật thu thập giúp cho việp háp đó là một cách suy diễn các chuyên gia con
ngƣời. Mỗi phƣơng pháp đó là một cách suy diễn các luật từ các ví dụ và giải pháp
đối với bài toán chuyên gia đƣa ra. Phƣơng pháp này khác với khai phá dữ liệu ở
chỗ các ví dụ của chuyên gia thƣờng ở mức chất lƣợng cao hơn rất nhiều so với các
dữ liệu trong cơ sở dữ liệu, và chúng thƣờng chỉ bao đƣợc các trƣờng hợp quan
trọng. Hơn nữa, các chuyên gia sẽ xác nhận tính giá trị và hữu dụng của các mẫu
phát hiện đƣợc. Cũng nhƣ với các công cụ quản trị cơ sở dữ liệu, ở các phƣơng
pháp này đòi hỏi có sự tham gia của con ngƣời trong việc phát hiện tri thức.
1.1.6.3 Phát kiến khoa học
Khai phá dữ liệu rất khác với phát kiến khoa học ở chỗ khai phá trong cơ sở
dữ liệu ít có chủ tâm và có điều kiện hơn. Các dữ liệu khoa học có từ thực nghiệm
nhằm loại bỏ một số tác động của các tham số để nhấn mạnh độ biến thiên của một
hay một số tham số đích. Tuy nhiên, các cơ sở dữ liệu thƣơng mại điển hình lại ghi
một số lƣợng thừa thông tin về các dự án của họ để đạt đƣợc một số mục đích về
mặt tổ chức. Độ dƣ thừa này (hay có thể gọi là sự lẫn lộn – confusion) có thể nhìn
thấy và cũng có thể ẩn chứa trong các mối quan hệ dữ liệu. Hơn nữa, các nhà khoa
học có thể tạo lại các thí nghiệm và có thể tìm ra rằng các thiết kế ban đầu không
thích hợp. Trong khi đó, các nhà quản lý cơ sở dữ liệu hầu nhƣ không thể xa xỉ đi
thiết kế lại các trƣờng dữ liệu và thu thập lại dữ liệu.
1.1.6.4 Phƣơng pháp thống kê
Một câu hỏi hiển nhiên là khai phá dữ liệu khác gì so với phƣơng pháp thống
kê.. Từ nhiều năm nay, con ngƣời đã sử dụng phƣơng pháp thống kê một cách rất
hiệu quả để đạt đƣợc mục đích của mình.
Mặc dù các phƣơng pháp thống kê cung cấp một nền tảng lý thuyết vững chắc
cho các bài toàn phân tích dữ liệu nhƣng chỉ có tiếp cận thống kê thuần túy thôi
chƣa đủ. Thứ nhất, các phƣơng pháp thống kê chuẩn không phù hợp đối với các
- Xem thêm -