ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
NGUYỄN KHẮC GIÁO
KHAI THÁC LUẬT KẾT HỢP
TỪ CƠ SỞ DỮ LIỆU GIAO DỊCH
CỦA SIÊU THỊ BÁN LẺ
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
Hà Nội – 2013
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
NGUYỄN KHẮC GIÁO
KHAI THÁC LUẬT KẾT HỢP TỪ CƠ SỞ DỮ LIỆU
GIAO DỊCH CỦA SIÊU THỊ BÁN LẺ
Ngành: Công nghệ thông tin
Chuyên ngành: Hệ thống thông tin
Mã số: 60 48 05
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
NGƯỜI HƯỚNG DẪN KHOA HỌC: GS.TS Vũ Đức Thi
Hà Nội - 2013
3
LỜI CẢM ƠN
Tôi xin bày tỏ lòng biết ơn sâu sắc đến:
- GS.TS Vũ Đức Thi - Viện Công nghệ thông tin, Viện Hàn lâm Khoa
học và Công nghệ Việt Nam, người thày đã tận tình hướng dẫn, chỉ bảo tôi
hoàn thành tốt luận văn này.
- Các thày cô giáo Khoa Công nghệ thông tin - Trường Đại học Công
nghệ đã tận tâm giảng dạy, truyền đạt cho tôi những kiến thức, phương
pháp nghiên cứu trong suốt hai năm học.
- Các thày cô, các anh chị tại viện Công nghệ thông tin, Viện Hàn lâm
Khoa học và Công nghệ Việt Nam đã giúp đỡ tôi rất nhiều trong quá trình
nghiên cứu.
Cuối cùng xin cảm ơn gia đình và bạn bè đã giúp đỡ động viên, tạo điều kiện
thuận lợi cho tôi trong suốt thời gian nghiên cứu.
Hà Nội, tháng 9 năm 2013
Nguyễn Khắc Giáo
4
LỜI CAM ĐOAN
Tôi xin cam đoan luận văn "Khai thác luật kết hợp từ cơ sở
dữ liệu giao dịch của siêu thị bán lẻ" này là công trình nghiên
cứu của tôi dưới sự hướng dẫn khoa học của GS.TS Vũ Đức Thi.
Các số liệu, kết quả tham khảo trong luận văn là chính xác và được
trích dẫn đầy đủ trong các tài liệu tham khảo. Phần ứng dụng thực
tiễn do cá nhân tôi tự thực hiện. Tôi xin chịu trách nhiệm về luận
văn của mình.
Nguyễn Khắc Giáo
5
MỤC LỤC
Danh mục hình vẽ ................................................................................................. 7
MỞ ĐẦU ............................................................................................................... 8
CHƯƠNG 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU ................................... 11
1.1. Nhu cầu của khai phá dữ liệu ................................................................... 11
1.2. Định nghĩa khai phá dữ liệu ..................................................................... 12
1.3. Các ứng dụng của khai phá dữ liệu .......................................................... 13
1.4. Các bước của quá trình khai phá dữ liệu.................................................. 14
1.5. Kiến trúc của một hệ thống khai phá dữ liệu ........................................... 17
1.6. Kiểu dữ liệu trong khai phá dữ liệu ......................................................... 18
1.7. Các bài toán khai phá dữ liệu điển hình ................................................... 19
1.7.1. Mô tả khái niệm ................................................................................ 19
1.7.2. Quan hệ kết hợp ................................................................................ 20
1.7.3. Phân lớp (phân loại – classification) ................................................. 20
1.7.4. Phân cụm (clustering) ....................................................................... 20
1.7.5. Hồi quy (regression) .......................................................................... 20
1.7.6. Mô hình hóa sự phục thuộc (dependency modeling) ........................ 21
1.7.7. Phát hiện sự biến đổi và độ lệch (change and deviation detection) .. 21
1.8. Lợi thế của khai phá dữ liệu so với các phương pháp cơ bản.................. 22
1.8.1. Học máy (Machine Learning) ........................................................... 22
1.8.2. Phương pháp hệ chuyên gia .............................................................. 23
1.8.3. Phát kiến khoa học ............................................................................ 23
1.8.4. Phương pháp thống kê....................................................................... 23
1.9. Thách thức trong ứng dụng và nghiên cứu kỹ thuật khai phá dữ liệu ..... 24
1.9.1. Các vấn đề về CSDL ......................................................................... 24
1.9.2. Một số vấn đề khác ........................................................................... 26
1.10. Tình hình ứng dụng khai phá dữ liệu ..................................................... 27
CHƯƠNG 2. KHAI PHÁ DỮ LIỆU BẰNG LUẬT KẾT HỢP ........................ 29
2.1. Một số khái niệm ...................................................................................... 29
6
2.1.1. Độ hỗ trợ (support) ............................................................................ 29
2.1.2. Tập phổ biến ...................................................................................... 29
2.1.3. Luật kết hợp....................................................................................... 30
2.2. Phát biểu bài toán tìm luật kết hợp........................................................... 31
2.2. Một số hướng tiếp cận trong khai phá luật kết hợp ................................. 33
2.3. Một số thuật toán phát hiện luật kết hợp .................................................. 35
2.3.1. Thuật toán Apriori ............................................................................. 35
2.3.2. Thuật toán FP-Growth....................................................................... 40
CHƯƠNG 3. TÌM LUẬT KẾT HỢP TRONG CƠ SỞ DỮ LIỆU GIAO DỊCH
CỦA SIÊU THỊ BÁN LẺ ................................................................................... 50
3.1. Bài toán tìm luật kết hợp trong cơ sở dữ liệu giao dịch của siêu thị bán lẻ
......................................................................................................................... 50
3.1.1. Giới thiệu bài toán ............................................................................. 50
3.1.2. Thuật toán khai phá tập mục cổ phần cao AFSM – Advanced Fast
Share Measure) ............................................................................................ 51
3.2. Xây dựng chương trình khai phá luật kết hợp trong cơ sở dữ liệu giao
dịch của siêu thị bán lẻ .................................................................................... 59
3.2.1. Dữ liệu đầu vào ................................................................................. 59
3.2.2. Giao diện chương trình ..................................................................... 61
3.2.3. Thử nghiệm chương trình.................................................................. 66
3.2.4. Nhận xét ............................................................................................ 69
KẾT LUẬN ......................................................................................................... 70
Kết quả đạt được ............................................................................................. 70
Hướng nghiên cứu tiếp theo ............................................................................ 70
TÀI LIỆU THAM KHẢO ................................................................................... 72
7
Danh mục hình vẽ
Hình 1.1. Tiến hóa công nghệ Cơ sở dữ liệu ................................................ 12
Hình 1.2. Quá trình phát hiện tri thức trong CSDL ...................................... 14
Hình 1.3. Quy trình phát hiện tri thức ........................................................... 15
Hình 1.4. Kiến trúc điển hình của hệ thống khai phá dữ liệu ....................... 17
Hình 2.1. Tính chất Apriori của tập mục phổ biến ....................................... 36
Hình 2.2. Nhánh tập cha không phổ biến sinh từ tập con không phổ biến ... 36
Hình 2.3. Ví dụ minh họa thuật toán Apriori ................................................ 39
Hình 3.1. Kết quả ví dụ về thuật toán AFSM ............................................... 57
Hình 3.2. Sơ đồ khối thuật toán AFSM ........................................................ 58
Hình 3.3. Dữ liệu dạng bảng ......................................................................... 59
Hình 3.4. Dữ liệu dạng CSDL....................................................................... 60
Hình 3.5. Dữ liệu dạng Text.......................................................................... 61
Hình 3.6. Form Giao diện chính ................................................................... 63
Hình 3.7. Form kết quả ................................................................................. 64
Hình 3.8. Giao diện mở file dữ liệu .............................................................. 65
Hình 3.9. Cảnh báo lỗi nếu nhập thiếu thông tin .......................................... 65
Hình 3.10. Cảnh báo lỗi nếu chọn sai dữ liệu ............................................... 66
8
MỞ ĐẦU
Ngày nay, với sự phát triển nhanh chóng của công nghệ thông tin, tin học đã
được ứng dụng trên nhiều mặt của kinh tế, đời sống xã hội. Kéo theo đó là một
khối lượng dữ liệu đồ sộ được lưu trữ trong các hệ thống cơ sở dữ liệu, kho dữ
liệu. Chúng ta biết rằng trong khối lượng dữ liệu khổng lồ đó đang ẩn chứa
những giá trị nhất định. Chẳng hạn như, tập dữ liệu về thông tin khám bệnh của
các bệnh nhân tại một bệnh viện hoặc một vùng có thể cho biết mối liên quan
giữa các triệu chứng bệnh hay xảy ra: người bị nhức đầu thường hay bị sốt,
người bị ho thường bị rát họng... ;Cơ sở dữ liệu giao dịch của một siêu thị có thể
ẩn chứa thông tin về thói quen mua hàng của khách hàng tại siêu thị: khách hàng
mua bánh mì thường mua sữa, khách hàng mua sữa bột thường mua bỉm, quần
áo trẻ sơ sinh...; Lịch sử duyệt web của người dùng ẩn chứa thông tin về thói
quen lướt web của người đó...v.v. Việc tìm ra những quy luật có thể được thực
hiện bằng phương pháp thống kê nhưng khi làm việc với cơ sở dữ liệu vô cùng
lớn thì phương pháp thống kê trở nên khó thực hiện và vô cùng tốn kém. Nhu
cầu khai thác tri thức từ dữ liệu ngày càng lớn làm cho một khuynh hướng kỹ
thuật mới ra đời: đó là phát hiện tri thức và khai phá dữ liệu KDD (Knowledge
Discovery and Data Mining). Phát hiện tri thức trong cơ sở dữ liệu là một quá
trình không tầm thường nhận ra những mẫu có giá trị, mới, hữu ích tiềm năng và
hiểu được trong dữ liệu. KDD là sự kế thừa và phát triển các thành tựu của nhiều
lĩnh vực nghiên cứu ứng dụng tin học trước đó như: Hệ chuyên gia, Trí tuệ nhân
tạo, lý thuyết nhận dạng, …
KDD được ứng dụng rất rộng rãi trong nghiên cứu khoa học, đời sống chính
trị xã hội và kinh tế: nghiên cứu thiên văn học, tin sinh học, phát hiện gian lận,
khai thác mạng xã hội, văn bản, phát hiện tội phạm, phát hiện lừa đảo, hỗ trợ ra
quyết định, quản lý rủi ro...
Hiện nay, thói quen mua sắm của người tiêu dùng tại các đô thị đang dần
thay đổi. Với các hệ thống siêu thị rộng khắp, thuận tiện và an toàn hơn, người
tiêu dùng chuyển sang mua sắm tại các siêu thị nhiều hơn. Nhờ việc ứng dụng
tin học vào trong công tác quản lý, các giao dịch mua sắm của khách hàng được
lưu lại trong cơ sở dữ liệu của siêu thị. Vấn đề đặt ra là, người quản lý siêu thị
có thể tìm thấy những tri thức mới từ kho dữ liệu giao tác khổng lồ kia? Họ
mong muốn tìm ra từ đó các quy luật mua sắm của khách hàng để điều phối, sắp
xếp hàng hóa một cách phù hợp. Bài toán này có thể tìm ra lời giải bằng phương
9
pháp khai phá luật kết hợp thực hiện trên bảng cơ sở dữ liệu giao tác (giao dịch
mua hàng).
Trước đây, bảng dữ liệu đầu vào chỉ thể hiện việc có hay không thực hiện
một giao tác nào đó (ví dụ như mặt hàng nào bán được ghi 1, không bán ghi 0),
nhưng bảng dữ liệu còn thể hiện số lượng trong giao tác (mặt hàng nào không
bán được ghi 0, mặt hàng bán được thì ghi số lượng của mặt hàng đó được bán.
Điều này dẫn bài toán đến sát thực tiễn và có ý nghĩa thực tiễn hơn bài toán 0 và
1. Nhưng cũng vì thế mà làm biến đổi nhiều đặc tính của dữ liệu 0 và 1. Do đó
nhiều nhà khoa học đã tiến hành nghiên cứu bảng dữ liệu giao tác có số lượng để
tìm ra những quy luật sao cho việc tìm kiếm các tập mục phổ biến trong bảng
giao tác có số lượng là nhanh nhất.
Trong luận văn này, tôi chọn cách nghiên cứu và xây dựng thực nghiệm với
bài toán khai thác luật kết hợp từ cơ sở dữ liệu của siêu thị bán lẻ mà các giao
dịch không chỉ đơn thuần được thể hiện ở dạng nhị phân mà có cả số lượng hàng
hóa được mua trong các giao dịch.
Nội dung chính của luận văn gồm 3 chương:
Chương 1: Tổng quan về khai phá dữ liệu
Nêu những kiến thức cơ bản khai phá dữ liệu và phát hiện tri thức trong
cơ sở dữ liệu:
- Một số định nghĩa về khai phá dữ liệu.
- Các phương pháp khai phá dữ liệu phổ biến và ứng dụng của chúng.
- Khuynh hướng phát triển của khai phá dữ liệu.
Chương 2: Khai phá dữ liệu bằng luật kết hợp
- Giới thiệu về bài toán khai phá luật kết hợp, các khái niệm liên quan và
các phương pháp khai phá luật kết hợp.
- Giới thiệu một số thuật toán được sử dụng để khai phá luật kết hợp.
Chương 3: Tìm luật kết hợp trong cơ sở dữ liệu giao dịch của siêu thị bán lẻ
Mô tả bài toán thực nghiệm là tìm tập các luật kết hợp thể hiện thói quen
mua sắm của các khách hàng từ tập cơ sở dữ liệu về các giao dịch mua bán
của một siêu thị bán lẻ. Trong đó:
- Mô tả sự khác biệt giữa cơ sở dữ liệu bán lẻ của siêu thị so với bảng dữ liệu
nhị phân.
10
- Giới thiệu một số cách giải quyết mà các nhà khoa học đã công bố.
- Xây dựng phần mềm tìm luật kết hợp dựa trên phương pháp AFSM.
11
CHƯƠNG 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU
1.1. Nhu cầu của khai phá dữ liệu
Chúng ta đang sống trong thời kỳ công nghệ thông tin phát triển như vũ bão.
Công nghệ thông tin ứng dụng trên hầu hết các lĩnh vực khoa học, đời sống,
kinh tế, chính trị, xã hội. Đồng thời với đó là lượng dữ liệu được lưu trữ cũng
được tăng lên nhanh chóng tạo ra những kho dữ liệu khổng lồ. Chúng ta biết
rằng, ẩn chứa trong lượng dữ liệu đó có những giá trị nhất định. Tuy nhiên theo
thống kê, chỉ một lượng nhỏ của những dữ liệu này (khoảng 5% - 10%) là luôn
được phân tích, số còn lại không biết để làm gì nhưng chúng ta vẫn luôn phải
lưu trữ vì sợ sẽ bỏ qua những thông tin quan trọng nào đó hoặc một ngày nào đó
sẽ dùng tới chúng. Mặt khác, trong thời đại ngày nay, chúng ta cần có nhiều
thông tin để trợ giúp ra quyết định và ngày càng có nhiều câu hỏi mang tính chất
định tính cần phải trả lời dựa trên một khối lượng dữ liệu khổng lồ đã có. Do đó,
các phương pháp quản trị và khai thác cơ sở dữ liệu truyền thống ngày càng
không thể đáp ứng được thực tế. Trong [13] hai tác giả Jiawei Han và Micheline
Kamber đã nhận định rằng, tình trạng "giàu về dữ liệu mà nghèo về thông tin" là
một động lực phát triển lĩnh vực khai phá dữ liệu và phát hiện tri thức trong cơ
sở dữ liệu. Quá trình tiến hóa trong lĩnh vực công nghệ cơ sở dữ liệu được hai
tác giả mô tả như Hình 1.1, trong đó công nghệ khai phá dữ liệu được coi là giai
đoạn tiến hóa mới của công nghệ cơ sở dữ liệu. Quá trình tiến hóa này được bắt
đầu từ cuối những năm 1980 và không ngừng được phát triển về cả bề rộng lẫn
chiều sâu.
Việc nghiên cứu và phát triển lĩnh vực khai phá dữ liệu và phát hiện tri thức
trong CSDL nhằm giải quyết tình trạng "tràn ngập thông tin và thiếu thốn tri
thức". Những kho dữ liệu khổng lồ về Web (Google, Alexa, Internet Achive), về
CSDL (Yahoo, Max Phanck Institute for Meteorology, AT&T), kho dữ liệu về
thiên văn, y tế, chứng khoán tài chính.... được xây dựng không ngoài mục đích
tìm ra những thông tin có giá trị từ những dữ liệu đó. Chẳng hạn như, từ một
giải pháp phân lớp trong khai phá dữ liệu Web (Web mining) có thể phát triển
thành một thành phần của máy tìm kiếm để khi một trang web mới được tải về,
máy tìm kiếm sẽ tự động phân nó vào một lớp trang web đã được xác định; việc
phân lớp đó sẽ tạo thuận lợi cho việc tìm kiếm về sau của người sử dụng. Hay
như giải pháp khai phá luật kết hợp từ một cơ sở dữ liệu về các lỗi của mạng di
động cho ra được mối liên quan giữa các lỗi "phổ biến" xảy ra trong mạng di
động với một xác suất nhất định (mức độ "phổ biến" này được xác định bằng
12
một ngưỡng cho trước của người khai phá) từ đó phần nào hỗ trợ người quản trị
mạng có thể dự đoán được các lỗi xảy ra để có biện pháp phòng chống.
Tập hợp dữ liệu và khởi tạo CSDL
(tới cuối những năm 1960)
- Xử lý file thô sơ
Hệ quản trị CSDL
(những năm 1970 và những năm đầu 1980)
- Hệ thống CSDL phân cấp và mạng Hệ thống CSDL quan hệ
- Công cụ mô hình dữ liệu: Mô hình quan hệ thực thể...
- Kỹ thuật đánh chỉ số và tổ chức dữ liệu: Cây B+, băm ...
- Ngôn ngữ hỏi SQL...
- Giao diện người dùng, nhập liệu và kết xuất
- Xử lý truy vấn, tối ưu truy vấn
- Quản lý giao dịch: khôi phục, điều khiển đồng thời...
- Xử lý giao dịch trực tuyến (QL TP)
Hệ CSDL mở rộng
(những năm giữa 1980 đến nay)
- Mô hình dữ liệu mở rộng: quan hệ mở rộng,
hướng đối tượng, quan hệ - đối tượng, suy luận.
- Định hướng ứng dụng không gian, thời gian, đa
phương tiện, tích cực, khoa học, cơ sở tri thức.
Kho dữ liệu và khai phá dữ liệu
(những năm cuối 1980 đến nay)
- Kho dữ liệu và công nghệ OLAP.
- Khai phá dữ liệu & phát hiện tri thức
Hệ CSDL dựa trên Web
(những năm 1990 đến nay)
- Hệ CSDL dựa trên XML.
- Khai phá Web.
Thế hệ mới hệ thông tin tích hợp (2000 -)
Hình 1.1. Tiến hóa công nghệ Cơ sở dữ liệu
1.2. Định nghĩa khai phá dữ liệu
"Khai phá dữ liệu được dùng để chỉ việc kết xuất hoặc khai thác tri thức từ
lượng lớn dữ liệu"[13]. 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
các tác giả về khai phá dữ liệu được Friedman tổng hợp trong [11]:
Đị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 có giá trị mới, hữu ích tiềm năng và hiểu được trong
dữ liệu” [10].
13
Định nghĩa của Zekulin: "Khai phá dữ liệu là quá trình trích lọc những
thông tin chưa biết, hiểu được và hữu ích từ những cơ sở dữ liệu lớn và dùng
chúng để đưa ra những quyết định kinh doanh quan trọng".
Đị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 John: "Khai phá dữ liệu là quá trình phát hiện những mẫu có
ích 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 CSDL
lớn”.
J. Han và M. Kamber cho rằng, cụm từ tiếng Anh "Data mining" (Khai phá
dữ liệu) chưa diễn tả đầy đủ và toàn diện ý nghĩa của lĩnh vực nghiên cứu - triển
khai mà nó mang tên. Như việc khai thác vàng từ đá hay cát không thể diễn đạt
bằng cụm từ "Khai thác đá" hoặc "Khai thác cát"[13]. Tuy vậy, thuật ngữ "Khai
phá dữ liệu" đã trở nên phổ biến trong các tài liệu tiếng Việt hiện nay.
Hai thuật ngữ “Khám phá tri thức” và “Khai phá dữ liệu” đã xuất hiện và
phổ biến trên thế giới, tuy nhiên ở việt nam thì những thuật ngữ này còn tương
đối là mới mẻ do vậy rất nhiều người đã coi khai phá dữ liệu và khám phá tri
thức trong cơ sở dữ liệu (knowledge discovery in databases - KDD) là như nhau.
Tuy nhiên thực chất, khai phá dữ liệu chỉ là một khâu trong quá trình khám phá
tri thức.
Khái niệm về Khai phá dữ liệu của Frawley, Piatetski-Shapiro và Matheus:
"Khai phá dữ liệu là một bước trong quá trình Phát hiện tri thức trong cơ sở dữ
liệu, thi hành một thuật toán khai phá dữ liệu để tìm ra các mẫu từ dữ liệu theo
khuôn dạng thích hợp".
1.3. 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, CSDL, 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ư:
14
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.
Điều trị y học và chăm sóc y tế: một số thông tin về chẩn đoán bệnh 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, chẩn đoán và phương pháp điều trị.
Sản xuất và chế biến: Quy trình, phương pháp chế biến và xử lý sự cố.
Text mining và Web mining: Phân tích lớp văn bản và 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 gene, dữ liệu sinh vật học,
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.4. Các bước của quá trình khai phá dữ liệu
Trình diễn
Khai phá
dữ liệu
Tri thức
Đổi dạng
Tiền xử lý
Mẫu
Chọn lựa
Dữ liệu đã
chuyển dạng
Dữ liệu đã
tiền xử lý
Dữ liệu đích
Dữ liệu
Hình 1.2. Quá trình phát hiện tri thức trong CSDL
Theo [7,8,10] quy trình phát hiện tri thức thường tuân theo các nhóm bước
như mô tả cụ thể như trong Hình 1.3.
15
Nhóm bước thứ nhất: Mở rộng hiểu biết về miền ứng dụng, về các tri thức
với độ ưu tiên thích hợp và về mục đích của người dùng cuối. Có thể coi nội
dung công việc này tương ứng với nội dung khảo sát bài toán trong quy trình
xây dựng một hệ thống thông tin nói chung.
Khởi tạo tập dữ liệu đích, tạo kho dữ liệu: chọn tập dữ liệu "và/hoặc" hướng
trọng tâm tới các tập con các biến hoặc mẫu dữ liệu mà trên đó công việc phát
hiện tri thức được tiến hành. Tri thức miền ứng dụng có được thông qua việc mở
rộng hiểu biết về miền ứng dụng nói trên đóng vai trò là nền tảng tri thức để
khởi tạo tập dữ liệu đích, kho dữ liệu.
Tạo/lựa chọn
CSDL đích
Tạo kho dữ liệu
1
Lựa chọn kỹ
thuật lấy mẫu
và dữ liệu
Bổ sung dữ
liệu thất lạc
Loại trừ dữ
liệu tạp nhiễu
2
Chuẩn hóa dữ
liệu
Chuyển dạng
dữ liệu
Lựa chọn bài
toán DM
Lựa chọn
phương pháp
DM
Tìm các thuộc tính
quan trọng và các
phạm vi có giá trị
Tạo các thuộc
tính xuất phát
3
Rút tri thức
Test tri thức
Tinh chế
tri thức
Chuyển sang
các dạng trình
diễn khác
4
5
Hình 1.3. Quy trình phát hiện tri thức
Nhóm bước thứ hai: làm sạch và tiền xử lý dữ liệu: thực hiện các thao tác cơ
sở như giải quyết thiếu vắng giá trị, loại bỏ nhiễu hoặc yếu tố ngoại lai, kết nối
các thông tin cần thiết tới mô hình hoặc loại bỏ nhiễu, quyết định chiến lược
nhằm nắm bắt các trường dữ liệu (các thuộc tính), tính toán dãy thông tin thời
gian và sự biến đổi được định trước.
Chất lượng của hệ thống khai phá dữ liệu phụ thuộc vào chất lượng của dữ
liệu đầu vào. Mục tiêu làm sạch dữ liệu nhằm đảm bảo dữ liệu đầu vào có chất
lượng tốt. Nhờ đó mà nâng cao chất lượng của hệ thống.
16
Thu gọn và trình diễn dữ liệu có mục tiêu tìm được các đặc trưng hữu ích
nhằm trình bày mối phụ thuộc dữ liệu theo mục đích của bài toán. Thu gọn dữ
liệu được thi hành về chiều ngang (giảm số lượng đối tượng), chiều dọc (giảm
số lượng trường dữ liệu) hoặc cả hai nhằm làm giảm kích thước dữ liệu được xử
lý, tăng tốc độ hoạt động của hệ thống. Sử dụng các phương pháp thu gọn hoặc
biến đổi chiều nhằm rút gọn số lượng các biến cần quan tâm hoặc để tìm ra các
mô tả bất biến đối với dữ liệu nhằm trình diễn dữ liệu phù hợp nhất. Do khối
lượng dữ liệu trong bài toán KDD là rất lớn nên việc thực hiện bước này là rất
cần thiết. Khi thu gọn theo chiều ngang cần lưu ý là tập dữ liệu được lựa chọn
phải có tính đại diện cho toàn bộ dữ liệu của miền ứng dụng. Việc chọn lựa dữ
liệu vào xây dựng mô hình khai thác dữ liệu thông thường cần được tiến hành
theo một phương pháp đảm bảo tính "ngẫu nhiên" khi chọn lựa dữ liệu trong
miền ứng dụng. Tương tự, khi thu gọn theo chiều dọc cần lưu ý các thuộc tính
còn lại phải đảm bảo tính đại diện cho đối tượng trong bài toán khai phá dữ liệu
đang xem xét. Trong nhiều bài toán khai phá dữ liệu, thu gọn theo chiều dọc thu
được kết quả tốt hơn không chỉ về thời gian, không gian mà còn cả về chất
lượng của bài toán khai phá dữ liệu cũng đạt độ chính xác cao hơn vì đã loại bỏ
được một số thuộc tính gây nhiễu.
Nhóm bước thứ ba: Chọn bài toán khai phá dữ liệu: quyết định mục tiêu của
quá trình KDD là loại bài toán cụ thể nào. Chọn lựa phương pháp khai phá dữ
liệu. Nội dung này bao gồm cả việc quyết định các mô hình và tham số có thể
được chấp nhận và phương pháp khai phá dữ liệu phù hợp với tiêu chuẩn tổng
thể của quá trình KDD. Thi hành thuật toán khai phá dữ liệu: tiến hành việc dò
tìm các mẫu cần quan tâm dưới dạng trình bày riêng biệt, hoặc một tập các trình
bày như quy tắc phân lớp, cây, hồi quy, phân đoạn, ... Trong bước này, sự hỗ trợ
của người dùng vẫn đóng một vài trò quan trọng.
Nhóm bước thứ tư: Giải thích mẫu đối với các mẫu được khám phá, có thể
quay về một cách hợp lý tới bất kỳ bước nào từ bước đầu tiên tới bước thi hành
thuật toán khai phá dữ liệu đã thực hiện.
Bước thứ năm: Hợp nhất các tri thức đã được khám phá, kết hợp các tri thức
này thành một hệ thống trình diễn hoặc được biên soạn dễ dàng và kết xuất
thành những thành phần hấp dẫn. Kiểm tra và giải quyết xung đột đối với tri
thức được trích chọn.
Tóm lại: Khai phá tri thức là một quá trình kết xuất ra tri thức từ tập dữ liệu
vô cùng lớn mà trong đó khai phá dữ liệu là công đoạn quan trọng nhất.
17
1.5. Kiến trúc của một hệ thống khai phá dữ liệu
Kiến trúc của một hệ thống KPDL điển hình có thể có các thành phần như
hình 1.4 [7, 8, 13]
Giao diện đồ họa người dùng
Đánh giá mẫu
Máy khai phá dữ liệu
Cơ sở tri thức
Máy chủ CSDL hay kho dữ liệu
Làm sạch và tích hợp dữ liệu
Cơ sở dữ liệu
Lọc
Kho dữ liệu
Hình 1.4. Kiến trúc điển hình của hệ thống khai phá dữ liệu
- CSDL, kho dữ liệu hoặc các lưu trữ thông tin khác (Databases, Data
warehouse, …): Đây là một hay một tập các CSDL, các kho dữ liệu, các trang
tính hay các dạng lưu trữ thông tin khác. Các kỹ thuật làm sạch dữ liệu và tích
hợp dữ liệu có thể được thể hiện trên những dữ liệu này.
- Máy chủ CSDL hay máy chủ kho dữ liệu (Database or warehouse server):
Máy chủ này có trách nhiệm lấy những dữ liệu thích hợp dựa trên các yêu cầu
khai phá của người dùng.
- Cơ sở tri thức (Knowledge base): Đây là miền tri thức được dùng để hướng
dẫn việc tìm kiếm hay đánh giá độ quan trọng của các hình mẫu kết quả.
- Máy KPDL (Data mining engine): Một hệ thống KPDL cần phải có một
tập các modun chức năng để thực hiện công việc như: đặc trưng hoá, kết hợp,
phân lớp, phân cụm, phân tích sự tiến hoá.
- Modun đánh giá mẫu (Pattern evaluation): Bộ phận này tương tác với các
modun KPDL để duyệt tìm các mẫu đáng được quan tâm. Nó có thể dùng các
18
ngưỡng về độ quan tâm để lọc mẫu đã khám phá được. Cũng có thể modun đánh
giá mẫu được tích hợp vào modun khai phá, tuỳ theo sự cài đặt của phương pháp
khai phá được dùng.
- Giao diện đồ họa người dùng (Graphical user interface): Bộ phận này cho
phép người dùng giao tiếp với hệ thống KPDL. Ngoài ra, bộ phận này còn cho
phép người dùng xem các lược đồ CSDL, lược đồ kho dữ liệu (hay các cấu trúc
dữ liệu), các đánh giá mẫu và hiển thị các mẫu trong khuôn dạng khác nhau.
1.6. Kiểu dữ liệu trong khai phá dữ liệu
Nguồn dữ liệu được sử dụng để tiến hành khai phá dữ liệu rất phong phú và
đa dạng, trong đó điển hình nhất là CSDL quan hệ, kho dữ liệu, CSDL giao
dịch, các hệ thống dữ liệu và thông tin mở rộng khác.
Cơ sở dữ liệu quan hệ: Tính phổ biến của hệ thống CSDL quan hệ hiện nay
dẫn đến việc CSDL quan hệ là một nguồn đầu vào điển hình nhất, rất được quan
tâm của khai phá dữ liệu. Các loại "quan hệ" tiềm ẩn trong CSDL quan hệ cũng
là một trong những mối quan tâm của khai phá dữ liệu.
Kho dữ liệu: theo định nghĩa của W.H. Inmon "kho dữ liệu là tập hợp các dữ
liệu định hướng theo chủ đề, được tích hợp lại, có tính phiên bản theo thời gian
và kiên định được dùng để hỗ trợ việc tạo ra quyết định trong quản lý", ngoài ra
cũng còn nhiều định nghĩa khác về kho dữ liệu. Kho dữ liệu là một kết quả xuất
hiện trong quá trình tiến hóa các hệ hỗ trợ ra quyết định. Quá trình phát hiện tri
thức trong CSDL tiếp nhận đầu vào là các hệ thống CSDL, các nhà kho tổ chức
dữ liệu từ các nguồn và các dữ liệu mô tả. Đồng thời với sự phát triển của công
nghệ kho dữ liệu, các hệ thống tích hợp các nguồn dữ liệu cả dữ liệu trong quá
khứ lẫn dữ liệu tác nghiệp đã được xây dựng. Nhiều hệ thống khai phá dữ liệu
có đầu vào từ siêu dữ liệu cùng các nguồn dữ liệu trong các kho dữ liệu.
Cơ sở dữ liệu giao dịch: Một lớp bài toán khai phá dữ liệu phổ biến là khai
phá quan hệ kết hợp trong đó điển hình là bài toán khai phá luật kết hợp, được
xuất phát từ việc xem xét các CSDL giao dịch (bán hàng). Dữ liệu giao dịch
chính là dữ liệu nguyên thủy xuất hiện trong định nghĩa về luật kết hợp cùng với
các độ do của luật như độ hỗ trợ và độ tin cậy. Khi mở rộng dữ liệu từ dữ liệu
giao dịch sang dữ liệu vô hướng, hoặc dữ liệu phức tạp hơn có trong các CSDL
quan hệ, các giải pháp khai phá luật kết hợp được cải tiến để thích ứng với sự
biến đổi này. Các giải pháp ứng dụng lý thuyết tập mờ và lý thuyết tập thô tương
ứng với việc mở rộng miền dữ liệu cần khai phá đã được tiến hành trong nhiều
công trình nghiên cứu.
19
Các hệ thống dữ liệu mở rộng: CSDL hướng đối tượng, CSDL không gian thời gian, CSDL tạm thời, dữ liệu chuỗi thời gian, dữ liệu dòng, CSDL Text và
CSDL đa phương tiện, CSDL hỗ tạp và CSDL thừa kế, Word Wide Web.
1.7. Các bài toán khai phá dữ liệu điển hình
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á dữ liệu được xây dựng từ các phương pháp học máy, thiết kế
mẫu, thống kê...
Ở mức tổng quát, hai mục tiêu chủ yếu của khai phá dữ liệu là dự báo và mô
tả, tương đương với hai dạng bài toán tổng quát của khai phá dữ liệu. Bài toán
dữ báo sử dụng một số biến (hoặc trường) trong CSDL để dự đoán về những giá
trị chưa biết hoặc là những giá trị sẽ xuất hiện trong tương lai của các biến. Bài
toán mô tả hướng tới việc tìm ra các mẫu mô tả dữ liệu. Dự đoán và mô tả có
tầm quan trọng khác nhau đối với các thuật toán khai phá dữ liệu riêng. Trong
ngữ cảnh KDD, vấn đề mô tả có khuynh hướng quan trọng hơn vấn đề dự báo,
điều này trái ngược với nội dung chủ yếu của các ứng dụng nhận dạng mẫu và
học máy, thì vấn đề dự báo lại là quan trọng hơn.
Ở mức chi tiết - cụ thể, dự báo và mô tả được thể hiện thông qua các bài
toán cụ thể như mô tả khái niệm, quan hệ kết hợp, phân cụm, phân lớp, hồi quy,
mô hình phụ thuộc, phát hiện biến đổi và độ lệch, và một số bài toán cụ thể
khác.
1.7.1. Mô tả khái niệm
Nội dung của bài toán mô tả khái niệm là tìm ra các đặc trưng và tính chất
của khái niệm (dùng để mô tả khái niệm đó). Điển hình nhất trong bài toán mô
tả khái niệm là các bài toán như tổng quát hóa, tóm tắt, phát hiện các đặc trưng
dữ liệu ràng buộc...
Bài toán tóm tắt là một bài toán mô tả điển hình áp dụng các phương pháp để
tìm ra một mô tả cô đọng nhất đối với 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 lại 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 đặc
20
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.7.2. Quan hệ kết hợp
Phát hiện mối quan hệ kết hợp trong tập dữ liệu là một bài toán quan trọng
trong khai phá dữ liệu. Một trong những mối quan hệ kết hợp điển hình là quan
hệ kết hợp giữa các biến dữ liệu, trong đó bài toán khai phá luật kết hợp là một
bài toán điển hình. Bài toán khai phá luật kết hợp (thuộc lớp quan hệ kết hợp)
thực hiện việc phát hiện ra mối quan hệ giữa các tập thuộc tính (các tập biến) có
dạng X Y, trong đó X, Y là hai tập thuộc tính. Về hình thức, luật kết hợp có
dạng giống như phụ thuộc hàm trong CSDL quan hệ, nhưng nó không được định
sẵn từ tri thức miền.
1.7.3. Phân lớp (phân loại – classification)
Là việc xác định một hàm ánh xạ từ một tập mẫu dữ liệu vào một trong số
các lớp đã được biết trước đó. 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 thỏa 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ụ: 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.7.4. Phân cụ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 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 CSDL tiếp thị; xác định tập 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 CSDL.
1.7.5. Hồi quy (regression)
Là việc học một hàm ánh xạ từ một mẫu dữ liệu thành một biến dự đoán có
giá trị thực. Nhiệm vụ của hồi quy tương tự như phân lớp, điểm khác nhau chính
là ở chỗ thuộc tính để dự báo liên tục (không phải rời rạc). Việc dự báo các giá
- Xem thêm -