ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
\\\
TRẦN NAM NGỌC
NGHIÊN CỨU LUẬT KẾT HỢP VÀ ỨNG
DỤNG TRONG BÀI TOÁN XÂY DỰNG HỆ HỖ
TRỢ HỌC SINH TRUNG HỌC PHỔ THÔNG
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Thái Nguyên - 2015
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
LỜI CẢM ƠN
Đầu tiên cho tôi gửiTRẦN
lời cảm ơn
chân NGỌC
thành và sâu sắc nhất đến thầy
NAM
PGS.TS Lê Bá Dũng - Viện CNTT - Viện KH và CN Việt nam đã tận tình
hƣớng dẫn, chỉ bảo cho tôi trong suốt quá trình làm luận văn.
NGHIÊN
LUẬT
HỢP
ỨNG
DỤNG
Tôi cũngCỨU
gửi lời cảm
ơn đến KẾT
các thầy cô
trƣờngVÀ
Đại học
Công nghệ
thông tin và Truyền
– Đại học
Thái Nguyên,
các thầy
Viện ÂNCông
TRONG
BÀIthông
TOÁN
XÂY
DỰNG
HỆcôHỖ
TRỢ
nghệ thông tin đã truyền đạt những kiến thức và giúp đỡ tôi trong suốt quá
SINH
trìnhHỌC
học của mình.
TRUNG HỌC PHỔ THÔNG
Chuyên ngành: Khoa học máy tính
Mã số : 60 48 01 01
những ngƣời đã động viên tạo mọi điều kiện giúp đỡ tôi trong suốt hai năm
Tôi cũng xin gửi lời cảm ơn tới các đồng nghiệp, gia đình và bạn bè
học.
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
NGƢỜI HƢỚNG DẪN KHOA HỌC: TS ĐẶNG THỊ THU HIỀN
Thái Nguyên - 2015
Số hóa bởi Trung tâm Học liệu – ĐHTN
http://www.lrc.tnu.edu.vn
1
MỤC LỤC
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ........................................................ 4
DANH MỤC CÁC BẢNG .................................................................................................... 5
MỞ ĐẦU ............................................................................................................................... 1
CHƢƠNG I TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU ....................................................... 2
1.1. Tổ chức và khai thác cơ sở dữ liệu truyền thống........................................................ 2
1.2. Tổng quan về kỹ thuật phát hiện tri thức và khai phá dữ liệu .................................... 3
1.2.1. Qui trình khai phá dữ liệu và phát hiện tri thức. ................................................. 4
1.2.2. Các lĩnh vực liên quan đến khai phá dữ liệu và phát hiện tri thức ...................... 5
1.3. Các nhiệm vụ trong khai phá dữ liệu và phát hiện tri thức. ....................................... 6
CHƢƠNG II: MỘT SỐ KỸ THUẬT KHAI PHÁ LUẬT KẾT HỢP................................. 15
2.1 Lý thuyết về luật kết hợp ........................................................................................... 15
2.2 Thuật toán kinh điển .................................................................................................. 16
2.2.1. Thuật toán Apriori ............................................................................................. 16
2.2.2 Ý tƣởng .............................................................................................................. 16
2.2.3 Thuật toán........................................................................................................... 16
2.3 Một số thuật toán luật kết hợp ................................................................................... 19
2.3.1 Thuật toán Fp_Growth ....................................................................................... 19
2.3.2 Thuật toán Fp_Tree ............................................................................................ 20
2.3.3 Thuật toán Fast Algorithm for Discovering Frequent Itemsets (FIT) ................ 21
2.3.4 Thuật toán NSFI ALGORITHM ....................................................................... 22
2.3.5 Thuật toán NSFI ALGORITH ........................................................................... 25
2.4 Thuật toán FSM ........................................................................................................ 26
2.4.1 Cơ sở lý thuyết của thuật toán FSM ................................................................... 27
2.4.2 Nội dung cơ bản của thuật toán FSM ................................................................. 27
2.4.3. Một số khái niệm của thuật toán ....................................................................... 28
2.4.4 Nội dung bài toán: .............................................................................................. 31
CHƢƠNG III: ÁP DỤNG KHAI PHÁ TRÊN CƠ SỞ DỮ LIỆU BẢNG ĐIỂM CỦA HỌC
SINH THPT TÂN LẬP - ĐAN PHƢỢNG ........................................................................ 34
3.1. Phát biểu bài toán: .................................................................................................... 34
3.2 Lựa chọn phƣơng pháp .............................................................................................. 35
3.3 Cài đặt và thử nghiệm................................................................................................ 35
3.3.1. Môi trƣờng cài đặt và thử nghiệm ..................................................................... 35
3.3.2 Cài đặt thuật toán tìm luật kết hợp ..................................................................... 36
3.3.3 Một số giao diện chƣơng trình ........................................................................... 37
3.4 Đánh giá: .................................................................................................................. 38
TÀI LIỆU THAM KHẢO ................................................................................................... 47
PHỤ LỤC ............................................................................................................................ 49
Số hóa bởi Trung tâm Học liệu – ĐHTN
http://www.lrc.tnu.edu.vn
2
Tác giả xin chân thành cảm ơn các thầy giáo, cô giáo Trƣờng Đại học Công
nghệ thông tin và Truyền thông Thái Nguyên và các thầy Viện Công nghệ thông
tin – Viện khoa học Công nghệ Việt Nam, đã tận tâm giảng dạy các kiến thức
trong hai năm học qua cùng với sự cố gắng hết mực của bản thân.
Đặc biệt tôi xin bày tỏ sự biết ơn sâu sắc đến thầy giáo Tiến sĩ Đặng Thị
Thu Hiền, PGS. TS Ngô Quốc Tạo ngƣời đã tận tình giảng dạy và hƣớng dẫn
tôi thực hiện luận văn này.
Tác giả cũng xin chân thành cảm ơn các thầy cô giáo trƣờng THPT Tân
Lập, các bạn đồng nghiệp, các bạn trong lớp cao học CK12H đã tạo điều kiện,
giúp đỡ tôi trong suốt thời gian qua.
Rất mong nhận đƣợc sự góp ý của các thầy, cô, bạn bè, đồng nghiệp để
luận văn có thể phát triển và hoàn thiện hơn.
Số hóa bởi Trung tâm Học liệu – ĐHTN
http://www.lrc.tnu.edu.vn
3
LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi.
Các số liệu, kết quả nêu trong luận văn và chƣa từng đƣợc ai công bố
trong bất kỳ công trình nào khác.
Thái Nguyên, tháng 12 năm 2015
TÁC GIẢ
Trần Nam Ngọc
Số hóa bởi Trung tâm Học liệu – ĐHTN
http://www.lrc.tnu.edu.vn
4
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
Từ viết tắt
Tiếng Anh
Tiếng Việt
Ck
Ck
Tập các K – itemset ứng cử
Conf
Confidence
Độ tin cậy
CSDL
Database
Cơ sở dữ liệu
DW
Data Warehouse
Kho dữ liệu
Item
Item
Khoản mục
Itemset
Itemset
Tập các khoản mục
K- itemset
K- itemset
Tập gồm K mục
KDD
Knowledge Discovery and
Kỹ thuật phát hiện tri thức và khai
Data Mining
phá dữ liệu
Lk
Lk
Tập các K - itemset phổ biến
Minconf
Minimum Confidence
Độ tin cậy tối thiểu
Minsup
Minimum Support
Độ hỗ trợ tối thiểu
OLAP
On Line Analytical
Phân tích trực tuyến
Processing
MOLAP
Multidimensional OLAP
Phân tích đa chiều trực tuyến
ROLAP
Relational OLAP
Phân tích quan hệ trực tuyến
pre(k, s)
pre(k, s)
Tiếp đầu dãy có độ dài k của s
Record
Record
Bản ghi
Supp
Support
Độ hỗ trợ
TID
Transaction Indentification
Định danh giao tác
SQL
Structured Query Language
Ngôn ngữ truy vấn có cấu trúc
SQO
Semantic Query Optimization
Tối ƣu truy vấn ngữ nghĩa
DBSCAN
Density Based Spatial
Thuật toán phân lớp dựa vào vị trí
Clustering of Application
địa phƣơng
with Noise
Số hóa bởi Trung tâm Học liệu – ĐHTN
http://www.lrc.tnu.edu.vn
5
DENCLUE
DENsity Based CLUstEring
Thuật toán phân lớp cơ bản (tổng
quát)
ADO
Activate X Data Object
Đối tƣợng dữ liệu Active X
DFS
Depth First Search
Tìm kiếm theo chiều sâu
BFS
Breadth First Search
Tìm kiếm theo chiều rộng
DHP
Direct Hashing and Pruning
Bảng băm trực tiếp và sự cắt tỉa
PHP
Perfect Hashing and Pruning
Bảng băm lý tƣởng và sự cắt tỉa
I/O
Input/Output
Vào/ra
D
Data
CSDL có các trƣờng
Size
Size
Số lƣợng các Item trong tập
Itemset
DANH MỤC CÁC BẢNG
Bảng 1.1. So sánh các nhiệm vụ phát hiện tri thức ...................................................12
Bảng 2.1. Cơ sở dữ liệu .............................................................................................29
Bảng 2.2. Giá trị lmv và cổ phần của các mục dữ liệu trong CSDL bảng 2.1. ........30
Bảng 2.3. Các tập mục cổ phần cao của CSDL bảng 2.1. ........................................31
Bảng 2.4. CSDL minh họa ngữ nghĩa của tập mục cổ phần cao. .............................33
Số hóa bởi Trung tâm Học liệu – ĐHTN
http://www.lrc.tnu.edu.vn
6
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Hình 1.1. Quy trình phát hiện tri thức ........................................................................4
Hình 2.1. CSDL giao dịch .........................................................................................17
Hình 2.2. Minh họa các bước khai phá .....................................................................18
Hình 2.3. Kết quả tìm luật kết hợp ............................................................................18
Hình 3.1. Ví dụ về dữ liệu đầu vào cho thực nghiệm ...............................................37
Hình 3.2. Giao diện chương trình thực hiện .............................................................37
Hình 3.3. Kết quả ......................................................................................................38
Số hóa bởi Trung tâm Học liệu – ĐHTN
http://www.lrc.tnu.edu.vn
1
MỞ ĐẦU
Ngày nay, thông tin đƣợc coi là tài sản quan trọng của các tổ chức, doanh
nghiệp và các cá nhân. Cá nhân hoặc tổ chức nào thu thập và hiểu đƣợc thông
tin, và hành động kịp thời dựa trên các thông tin đó sẽ đạt đƣợc kết quả tốt.
Chính vì lý do đó, việc tạo ra thông tin, tổ chức lƣu trữ và khai thác thông tin
ngày càng trở nên quan trọng và gia tăng không ngừng.
Sự tăng trƣởng vƣợt bậc của các cơ sở dữ liệu (CSDL) trong các hoạt
động nhƣ: sản xuất kinh doanh, thƣơng mại, quản lý đã làm nảy sinh và thúc
đẩy sự phát triển của kỹ thuật thu thập, lƣu trữ, phân tích và khai phá dữ liệu…
không chỉ bằng các phƣơng pháp thông thƣờng nhƣ: thống kê mà đòi hỏi cách
xử lý thông minh hơn, hiệu quả hơn. Từ đó các nhà quản lý có đƣợc thông tin
hữu ích để tác động lại quá trình sản xuất, kinh doanh của mình… đó là tri
thức. Các kỹ thuật cho phép ta khai thác đƣợc tri thức hữu dụng từ CSDL (lớn)
đƣợc gọi là các kỹ thuật khai phá dữ liệu (DM – Data Mining). Khai phá luật
kết hợp là một nội dung quan trọng trong khai phá dữ liệu.
Luận văn tìm hiểu về luật kết hợp và ứng dụng thử nghiệm khai phá cơ sở
dữ liệu bảng điểm học tập của học sinh trƣờng THPT Tân Lập – Đan Phƣơng
nhằm hỗ trợ cho công tác quản lý, định hƣớng học tập cho học sinh phổ thông.
Nhằm hỗ trợ học sinh chọn trƣờng đại học, cao đẳng phù hợp với khả năng của
bản thân hoặc đi học trƣờng nghề chuyên nghiệp. Giúp cho học sinh tập chung
vào đúng khối mà mình có khả năng cũng nhƣ có thế mạnh. Đồng thời cũng
giúp nhà trƣờng và giáo viên thấy đƣợc điểm mạnh, điểm chƣa mạnh về
chuyên môn của mình. Đƣa ra những hƣớng đi đúng nhằm xây dựng nhà
trƣờng thành nhà trƣờng có chuyên môn tốt, môi trƣờng thân thiện.
1
2
CHƢƠNG I TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU
1.1. Tổ chức và khai thác cơ sở dữ liệu truyền thống
Việc dùng các phƣơng tiện tin học để tổ chức và khai thác cơ sở dữ liệu
(CSDL) đã đƣợc phát triển từ những năm 60 của thế kỉ trƣớc. Từ đó cho đến
nay, rất nhiều CSDL đã đƣợc tổ chức, phát triển và khai thác ở mọi quy mô và
các lĩnh vực hoạt động của con ngƣời và xã hội. Cho đến nay, số lƣợng CSDL
đã trở nên khổng lồ bao gồm các CSDL cực lớn cỡ gigabytes và thậm chí
terabytes lƣu trữ các dữ liệu kinh doanh ví dụ nhƣ dữ liệu thông tin khác hàng,
dữ liệu bán hàng, dữ liệu các tài khoản, ... Nhiều hệ quản trị CSDL mạnh với
các công cụ phong phú và thuận tiện đã giúp con ngƣời khai thác có hiệu quả
nguồn tài nguyên dữ liệu. Mô hình CSDL quan hệ và ngôn ngữ vấn đáp chuẩn
(SQL) đã có vai trò hết sức quan trọng trong việc tổ chức và khai thác CSDL.
Tuy nhiên bên cạnh chức năng khai thác dữ liệu có tính chất tác nghiệp,
sự thành công trong công việc không còn là năng suất của các hệ thống thông
tin nữa mà là tính linh hoạt và sẵn sàng đáp ứng những yêu cầu trong thực tế,
CSDL cần đem lại những “tri thức” hơn là chính những dữ liệu trong đó. Lúc
này, các mô hình CSDL truyền thống và ngôn ngữ SQL đã cho thấy không có
khả năng thực hiện công việc này. Để lấy thông tin có tính “tri thức” trong
khối dữ liệu khổng lồ này, ngƣời ta đã tìm ra những kỹ thuật có khả năng hợp
nhất các dữ liệu từ các hệ thống giao dịch khác nhau, chuyển đổi thành một tập
hợp các CSDL ổn định, có chất lƣợng đƣợc sử dụng chỉ cho riêng một vài mục
đích nào đó. Các kỹ thuật đó gọi chung là kỹ thuật tạo kho dữ liệu (data
warehousing) và môi trƣờng các dữ liệu có đƣợc gọi là các kho dữ liệu (data
warehouse).
Đồng thời, Công nghệ khai phá dữ liệu (data mining) ra đời đáp ứng
những đòi hỏi trong khoa học cũng nhƣ trong hoạt động thực tiễn. Đây chính
là một ứng dụng chính để khai phá kho dữ liệu nhằm phát hiện tri thức
(Knowledge Discovery) phục vụ công tác quản lý, kinh doanh,….
2
3
1.2. Tổng quan về kỹ thuật phát hiện tri thức và khai phá dữ liệu
Chúng ta có thể xem tri thức nhƣ là các thông tin tích hợp, bao gồm các
sự kiện và các mối quan hệ giữa chúng. Các mối quan hệ này có thể đƣợc hiểu
ra, có thể đƣợc phát hiện, hoặc có thể đƣợc học. Nói cách khác, tri thức có thể
đƣợc coi là dữ liệu có độ trừu tƣợng và tổ chức cao.
Phát hiện tri thức trong các cơ sở dữ liệu là một qui 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 năng: hợp thức, mới, khả ích,
và có thể hiểu đƣợc. Còn khai phá dữ liệu là một bƣớc trong qui trình phát
hiện tri thức gồm có các thuật toán khai thác dữ liệu chuyên dùng dƣới một số
qui định về hiệu quả tính toán chấp nhận đƣợc để tìm ra các mẫu hoặc các mô
hình trong dữ liệu. Nói một cách khác, mục đích của phát hiện tri thức và khai
phá dữ liệu chính là tìm ra các mẫu và/hoặc các mô hình đang tồn tại trong các
cơ sở dữ liệu nhƣng vẫn còn bị che khuất bởi hàng núi dữ liệu.
Định nghĩa: Phát hiện tri thức và khai phá dữ liệu (KDD: Knowledge
Discovery and Data Mining) là 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 [7].
Còn các nhà thống kê thì xem Khai phá dữ liệu nhƣ là một qui trình phân
tích đƣợc thiết kế để thăm dò một lƣợng cực lớn các dữ liệu nhằm phát hiện ra
các mẫu thích hợp và/hoặc các mối quan hệ mang tính hệ thống giữa các biến
và sau đó sẽ hợp thức hoá các kết quả tìm đƣợc bằng cách áp dụng các mẫu đã
phát hiện đƣợc cho các tập con mới của dữ liệu. Qui trình này bao gồm ba giai
đoạn cơ bản: thăm dò, xây dựng mô hình hoặc định nghĩa mẫu, hợp thức/kiểm
chứng.
3
4
1.2.1. Qui trình khai phá dữ liệu và phát hiện tri thức.
Qui trình phát hiện tri thức đƣợc mô tả tóm tắt trên Hình 1:
Hình 1.1. Quy trình phát hiện tri thức
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, xử lý việc thiế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.
Bƣớc thứ ba: Khai phá dữ liệu, rút ra các tri thức. Là trích ra các mẫu
và/hoặc 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?
Bƣớc thứ tƣ: 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.
4
5
Tóm lại: KDD là một quá trình chiế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.
1.2.2. Các lĩnh vực liên quan đến khai phá dữ liệu và phát hiện tri thức
Khai phá dữ liệu và phát hiện tri thức 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 học, tính toán song
song và tốc độ cao, thu thập tri thức cho các hệ chuyên gia, quan sát dữ liệu...
Đặ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 dữ liệu và phát hiện các mẫu,
luật... Kho dữ liệu (Data Warehousing) và các công cụ phân tích trực tuyến
(OLAP) cũng liên quan rất chặt chẽ với Phát hiện tri thức và khai phá dữ liệu.
Khai phá dữ liệu có nhiều ứng dụng trong thực tế. Một số ứng dụng điển
hình 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, ...
- Đ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
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ị (chế độ dinh dƣỡng, thuố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 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ụ, ...
5
6
1.3. Các nhiệm vụ trong khai phá dữ liệu và phát hiện tri thức.
Do sự phát triển mạnh mẽ của các loại hệ thống phát hiện tri thức trong
CSDL (KDD) theo yêu cầu nhằm đáp ứng những đòi hỏi trong nhiều lĩnh vực
khác nhau, việc phát hiện tri thức cũng trở lên đa dạng hơn. Do đó, nhiệm vụ
của phát hiện tri thức trong CSDL cũng trở lên phong phú và có thể phát hiện
rất nhiều kiểu tri thức khác nhau. Một trong các bƣớc đầu tiên trong quá trình
phát hiện tri thức trong CSDL là quyết định xem loại kiến thức nào mà thuật
toán phát hiện tri thức trong CSDL cần phải kết xuất từ dữ liệu. Do đó, vệc
phân loại và so sánh các kiểu nhiệm vụ phát hiện tri thức trong CSDL là vấn
đề đáng quan tâm nhằm tạo ra một hệ thống phát hiện tri thức trong CSDL hữu
ích. Ta sẽ xem xét một số kiểu nhiệm vụ phát hiện tri thức sau:
Phát hiện các luật tối ƣu truy vấn ngữ nghĩa (Sematics Query
Optimization - SQO Rules)
Các luật tối ƣu truy vấn CSDL thông thƣờng thực hiện một phép biến đổi
cú pháp, hay sắp xếp lại thứ tự của các phép toán quan hệ trong một truy vấn
và sản sinh ra một truy vấn hiệu quả hơn. Các phép biến đổi này thƣờng dựa
trên lý thuyết đại số quan hệ. Các luật đƣợc biến đổi trả lại cùng một câu trả lời
nhƣ câu truy vấn ban đầu ở bất kỳ trạng thái nào của CSDL. Ngƣợc lại, luật tối
ƣu truy vấn ngữ nghĩa biến đổi các câu truy vấn ban đầu thành một truy vấn
mới bằng cách thêm vào hoặc xoá đi các mối liên kết bằng việc sử dụng các tri
thức CSDL ngữ nghĩa bao gồm các ràng buộc về tính toàn vẹn và sự phụ thuộc
hàm để sản sinh ra các câu truy vấn hiệu quả hơn. Nhƣ vậy câu truy vấn đã
biến đổi cũng trả lại cùng câu trả lời giống nhƣ câu truy vấn ban đầu trong bất
kỳ trạng thái nào của CSDL thoả mãn kiến thức về ngữ nghĩa đƣợc sử dụng
trong phép biến đổi. Các hệ thống phát hiện luật SQO có thể đƣợc chia thành
ba lớp:
6
7
- Các hệ thống hƣớng truy vấn (hệ thống báo cáo) trong đó thuật toán
phát hiện tri thức trong CSDL nhằm phục vụ các truy vấn CSDL thực của
ngƣời dùng;
- Các hệ thống hƣớng dữ liệu (hệ thống tác nghiệp) trong đó thuật toán
phát hiện tri thức trong CSDL chủ yếu phục vụ sự phân bổ dữ liệu trong trạng
thái hiện thời của CSDL;
- Các hệ thống lai kết hợp các đặc tính của cả hệ thống hƣớng truy vấn và
hƣớng dữ liệu.
Một đặc tính quan trọng của các luật SQO, khác với các kiểu phát hiện tri
thức khác, là việc chọn các thuộc tính để tổng hợp một SQO cần phải tính đến
chi phí liên quan nhƣ dùng phƣơng pháp truy cập nào và sơ đồ chỉ số trong hệ
quản trị CSDL. Việc này là cần thiết để tiết kiệm thời gian xử lý truy vấn. Một
thuật toán phát hiện tri thức trong CSDL loại này đòi hỏi phải xem xét tối ƣu
chi phí.
Phát hiện sự phụ thuộc CSDL (Database Dependencies)
Trong mô hình dữ liệu quan hệ, chúng ta đã nghiên cứu quan hệ trong
CSDL quan hệ không tính đến quan hệ giữa các thuộc tính. Các quan hệ này
thƣờng đƣợc thể hiện thông qua sự phụ thuộc dữ liệu hoặc ràng buộc toàn vẹn.
Ở đây sẽ sử dụng thuật ngữ phụ thuộc CSDL để chỉ sự phụ thuộc dữ liệu kiểu
này. Sự phụ thuộc CSDL đƣợc sử dụng trong thiết kế và duy trì một CSDL.
Phƣơng pháp phát hiện tự động các sự phụ thuộc CSDL này chính là một kiểu
nhiệm vụ của Khai phá dữ liệu.
Phát hiện sự sai lệch (Deviation)
Nhiệm vụ này nhằm phát hiện sự sai lệch đáng kể giữa nội dung của tập
con dữ liệu thực và nội dung mong đợi. Hai mô hình sai lệch hay dùng là mô
hình sai lệch theo thời gian và sai lệch nhóm. Sai lệch theo thời gian là sự thay
đổi có ý nghĩa của dữ liệu theo thời gian. Sai lệch theo nhóm là sự khác nhau
7
8
không chờ đợi giữa dữ liệu trong hai tập con dữ liệu, ở đây tính đến cả trƣờng
hợp tập con này thuộc trong tập con kia, nghĩa là 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, các sai sót dữ liệu hay sự sai lệch so với giá trị thông thƣờng
đƣợc phát hiện.
Phát hiện luật kết hợp (Association Rules)
Ta xét một ví dụ: Xét một tập các mặt hàng trong một giỏ mua hàng. Vấn
đề đặt ra là tìm những mối liên quan giữa các mặt hàng trong giỏ.
Một cách chi tiết hơn, xét một tập các thuộc tính nhị phân với một tập các
bộ, mỗi bộ đƣợc gọi là một giỏ. Các thuộc tính nhị phân đƣợc gọi là các mục
hay các mặt hàng trong giỏ mà mỗi mục chỉ nhận một trong hai giá trị đúng
hoặc sai tuỳ thuộc vào khách hàng có mua mặt hàng đó trong giao dịch hay
không. Trên thực tế, loại dữ liệu này rất phổ biến và đƣợc gọi là dữ liệu giỏ.
Chúng thƣờng đƣợc thu thập thông qua công nghệ mã số, mã vạch trong các
hoạt động kinh doanh siêu thị.
Một giao dịch có thể chứa một số khoản mục, tập hợp tất cả các khoản mục
sẽ thuộc vào một không gian T nào đó mà mỗi giao dịch khi đó là một tập con
của T. Ta cần phát hiện những mối tƣơng quan quan trọng hoặc mối quan hệ,
mối kết hợp trong số các khoản mục chứa trong các giao dịch của một dữ liệu
nào đó sao cho sự xuất hiện của một số khoả mục nào đó trong giao dịch sẽ kéo
theo sự xuất hiện của một số khoản mục khác trong cùng một giao dịch đó.
Ta sẽ tìm hiểu luật kết hợp cụ thể hơn ở phần sau.
Mô hình hoá sự phụ thuộc (Dependence Modeling)
Nhiệm vụ này liên quan đến việc phát hiện sự phụ thuộc trong số các thuộc
tính. Những phụ thuộc này thƣờng đƣợc biểu thị dƣới dạng luật “nếu thì”: “nếu
(tiên đề là đúng) thì (kết luận là đúng)”. Về nguyên tắc, cả tiên đề và kết luận
của luật đề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ế,
8
9
tiên đề thƣờng là nhóm các giá trị thuộc tính và kết luận chỉ là một giá trị tuộc
tính. Lƣu ý là những luật này không phải hoàn toàn giống với sự phụ thuộc
CSDL đƣợc nêu ở phần 2.2. Hơn nữa, hệ thống có thể phát hiện các luật với
phần kết luận nhiều thuộc tính. Điều này khác với 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.
Mô hình hoá nhân quả (Causation Modeling)
Nhiệm vụ này liên quan đến việc phát hiện mối quan hệ nhân quả trong
thuộc tính. Các luật nhân quả cũng là các luật “nếu - thì” giống các luật phụ
thuộc, nhƣng mạnh hơn. Luật phụ thuộc đơn giản chỉ ra một mối tƣơng hỗ
giữa tiên đề và kết luận của luật mà không có ý nghĩa nhân quả trong quan hệ
này. Do đó, cả tiên đề và kết luận có thể quan hệ dƣới sự ảnh hƣởng của một
biến thứ ba, tức là một thuộc tính hoặc có ở trong tiên đề hoặc có ở trong kết
luận. Luật nhân quả không chỉ chỉ ra mối tƣơng quan giữa tiên đề và kết luận
mà còn cho biết tiên đề thực sự tạo ra kết luận và mối quan hệ giữa hai thành
phần này là trực tiếp. Tập các mối quan hệ nhân quả có thể đƣợc biểu diễn
bằng đồ thị nhân quả.
Các quan hệ nhân quả cần phụ thuộc vào thời gian theo nghĩa là nguyên
nhân trƣớc kết quả (kết luận). Nguyên nhân và kết quả đều có ít nhất một sự
kiện thời gian đi kèm và thời gian của kết quả phải đi sau thời gian của nguyên
nhân. Mặc dù yếu tố thời gian làm rõ ý nghĩa nhân quả nhƣng hệ thống thƣờng
khó phân biệt các liên kết giả tạo.
Phân cụm, nhóm (Clustering).
Một nhiệm vụ của các hệ thống phát hiện tri thức là phân tích các đối
tƣợng dữ liệu dạng nhƣ các giỏ hàng mà không quan tâm tới lớp của chúng.
Các hệ thống này phải tự phát hiện ra các lớp và sinh ra một sơ đồ phân nhóm
của tập dữ liệu đó.
9
10
Tuy nhiên, chất lƣợng của việc phân nhóm này là một vấn dề khó có thể
xác định đƣợc. Bài toán phân nhóm xác định các nhóm dựa vào quan hệ nhiều
- nhiều, tức là bất kỳ thuộc tính nào cũng có thể đƣợc sử dụng để xác định các
nhóm và để dự báo các giá trị thuộc tính khác. Điều này trái với cách xác định
nhiều - một liên quan đến nhiệm vụ phân lớp các đối tƣợng, trong đó, một
thuộc tính đƣợc xem nhƣ lớp và tất cả các thuộc tính khác đƣợc sử dụng để
phán đoán giá trị cho thuộc tính lớp.
Phân lớp (Classification)
Trong nhiệm vụ phân lớp, mỗi bộ dữ liệu theo dạng giỏ mua hàng thuộc
về một lớp nào đó đã đƣợc xác định trƣớc. Các bộ dữ liệu bao gồm tập các
thuộc tính dự báo và một thuộc tính phân lớp cụ thể. Lớp của bộ đƣợc chỉ ra
bởi giá trị của thuộc tính lớp mà ngƣời dùng xác định trƣớc.
Ta xét ví dụ sau: Giả sử, mỗi bộ dữ liệu biểu diễn các thông tin về nhân
viên, trong đó các thuộc tính dự báo là tuổi, giới tính, trình độ học vấn, ... của
nhân viên đó và thuộc tính phân lớp là trình độ lãnh đạo của nhân viên. 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 các thuộc tính
dự báo và thuộc tính phân lớp, từ đó sử dụng mối quan hệ này để dự báo lớp
cho các bộ dữ liệu mới khác cùng khuôn dạng.
Trong trƣờng hợp những kiến thức đƣợc phát hiện biểu diễn dƣới dạng
các luật thì khuôn dạng của luật có thể là: “nếu các thuộc tính dự báo của một
bộ dữ liệu thoả mãn các điều kiện của tiên đề, thì bộ dữ liệu đó có lớp chỉ ra
trong kết luận”.
Hồi quy (Regression)
Về khái niệm, nhiệm vụ 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 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, các phƣơng pháp mô hình hoá cũng đƣợc
10
11
sử dụng, chẳng hạn nhƣ cây quyết định, trong đó nút lá là mô hình tuyến tính phát
sinh tập các lớp giả (pseudo - class) có giá trị thuộc tính đích tƣơng tự nhau, sau
đó sử dụng phƣơng pháp quy nạp để thay thế các lớp trong luật quy nạp bằng tổ
hợp các giá trị của thuộc tính lớp cho các bộ dữ liệu theo luật.
Tổng hợp (Sumarization)
Nhiệm vụ tổng hợp chính là sản sinh ra các mô tả đặc trƣng cho một lớp.
Mô tả này là một kiểu tổng hợp, tóm tắt mô tả các đặc tính chung của tất cả
(hoặc hầu hết) các bộ dữ liệu dạng giỏ mua hàng thuộc một lớp.
Các mô tả đặc trƣng thể hiện dƣới dạng luật có dạng sau: ”nếu một bộ dữ
liệu thuộc về một lớp đã chỉ ra trong tiên đề, thì bộ dữ liệu đó có tất cả các
thuộc tính đã nêu trong kết luận”. Cần lƣu ý là các luật này có những đặc trƣng
khác biệt so với luật phân lớp. Luật phát hiện đặc trƣng cho một lớp chỉ sản
sinh khi các bộ dữ liệu đã thuộc về lớp đó.
So sánh các nhiệm vụ phát hiện tri thức.
Điểm giống và khác giữa các nhiệm vụ phát hiện tri thức đƣợc tóm tắt
trong bảng sau:
Nhiệm vụ
SQO
Mục đích
Kiểu phát hiện
Hƣớng hệ quản trị
Tối ƣu truy vấn
CSDL
Sự phụ thuộc
Hƣớng hệ quản trị
Thiết kế và duy trì
CSDL
CSDL
CSDL
Phát hiện sai lệch
Mục đích chung
Xác định trội
Phát hiện liên kết
Mục đích chung
Dự báo, xác định
trội
11
Kiểu dự báo
Không học
Không học
Không học
Có học
12
Nhân quả
Mục đích chung
Dự báo, mô tả
Không học
Phân nhóm
Mục đích chung
Dự báo, mô tả
Không học
Phân lớp
Mục đích chung
Dự báo
Có học
Hồi quy
Mục đích chung
Dự báo
Có học
Tổng hợp
Mục đích chung
Dự báo
Có học
Bảng 1.1. So sánh các nhiệm vụ phát hiện tri thức
Trong bảng này, cột đầu tiên chỉ ra nhiệm vụ phát hiện tri thức. Cột thứ
hai chỉ ra kiểu tri thức đƣợc phát hiện. Các kiểu có thể là hƣớng hệ quản trị
CSDL (nhƣ các luật SQO) hoặc phụ thuộc CSDL hoặc là mục đích chung (tức
là các nhiệm vụ phát hiện bổ trợ khác). Tri thức hƣớng hệ quản trị CSDL
thƣờng dùng trong thiết kế và giao dịch của một CSDL. Tuy nhiên, tri thức
hƣớng hệ quản trị CSDL cũng có thể dùng cho việc kiểm tra các luật tối ƣu
truy vấn ngữ nghĩa để cải thiện việc tìm hiểu ứng dụng. Trong khi tri thức theo
kiểu mục đích chung có thể đƣợc sử dụng theo các mục đích khác nhau tuỳ
thuộc vào nhu cầu của ngƣời dùng theo nghĩa mờ và nó có thể sử dụng hiệu
quả trong hệ quản trị CSDL. Tuy vậy, điểm khác biệt quan trọng là tri thức
hƣớng hệ quản trị CSDL yêu cầu độ chính xác cao hơn so với tri thức theo
mục đích chung.
Cột thứ ba trong bảng chỉ ra mục đích của việc phát hiện tri thức. Cột này
xuất phát từ cột hai. Mục đích chính của các tri thức hƣớng hệ quản trị CSDL
là khá cụ thể: Tối ƣu truy vấn (trong trƣờng hợp SQO) và thiết kế, duy trì
CSDL (trong trƣờng hợp sự phụ thuộc CSDL). Các tri thức theo kiểu mục đích
chung thƣờng đƣợc dùng co một sự kết hợp các mục đích dự báo, mô tả và xác
định trội. Dự báo liên quan đến xác định giá trị của các tri thức trên cơ sở xác
định giá trị của các thuộc tính khác. Kỹ thuật đặc trƣng là phân lớp và hồi quy.
Tuy nhiên, dự báo cũng dựa trên quan hệ nhân quả, mô hình hoá sự phụ thuộc
12
- Xem thêm -