Luận văn Phá dữ liệu ứng dụng trong đào tạo
1
TRƯỜNG ………………….
KHOA……………………….
----------
Báo cáo tốt nghiệp
Đề tài:
PHÁ DỮ LIỆU ỨNG DỤNG TRONG ĐÀO TẠO
2
MỤC LỤC
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ...................................... 5
DANH MỤC CÁC HÌNH VẼ............................................................................ 6
LỜI MỞ ĐẦU.................................................................................................... 7
Chương 1 .......................................................................................................... 9
TỔNG QUAN KHAI PHÁ DỮ LIỆU VÀ PHÁT HIỆN TRI THỨC............ 9
1.1. Khái niệm phát hiện tri thức và khai phá dữ liệu ...................................... 9
1.2. Các bước trong quá trình phát hiện tri thức[7]........................................ 10
1.3. Kiến trúc hệ thống khai phá dữ liệu........................................................ 12
1.4.1. Cơ sở dữ liệu quan hệ ...................................................................... 12
1.4.2. Kho dữ liệu...................................................................................... 12
1.4.3. Cơ sở dữ liệu không gian ................................................................. 13
1.4.4. Cơ sở dữ liệu văn bản ...................................................................... 13
1.4.5. Dữ liệu Web..................................................................................... 13
3
1.5. Các phương pháp khai phá dữ liệu ......................................................... 13
1.5.1. Các thành phần của giải thuật khai phá dữ liệu ................................ 14
1.5.2. Phương pháp suy diễn / quy nạp ...................................................... 16
1.5.3. Phương pháp ứng dụng K-láng giềng............................................... 16
1.5.4. Phương pháp sử dụng cây quyết định và luật[14]............................. 17
1.5.5. Phương pháp phát hiện luật kết hợp ................................................. 18
1.6. Các nhiệm vụ trong khai phá dữ liệu...................................................... 19
1.6.1. Phát hiện các luật tối ưu truy vấn ngữ nghĩa..................................... 20
1.6.2. Phát hiện sự phụ thuộc Cơ sở dữ liệu............................................... 20
1.6.3. Phát hiện sự sai lệch......................................................................... 21
1.6.4. Phát hiện luật kết hợp....................................................................... 21
1.6.5. Mô hình hoá sự phụ thuộc................................................................ 21
1.6.6. Mô hình hoá nhân quả...................................................................... 22
1.6.7. Phân cụm, nhóm .............................................................................. 22
1.6.8. Phân lớp........................................................................................... 23
1.6.9. Hồi quy............................................................................................ 23
1.6.10. Tổng hợp ....................................................................................... 23
1.7. Các thách thức và giải pháp cơ bản ........................................................ 24
1.7.1. Thách thức....................................................................................... 24
1.7.2. Một số giải pháp .............................................................................. 25
1.8. Kết luận.................................................................................................. 25
Chương 2 ........................................................................................................ 26
CƠ SỞ LÝ THUYẾT CỦA LUẬT KẾT HỢP, MỘT SỐ THUẬT TOÁN
PHÁT HIỆN LUẬT KẾT HỢP..................................................................... 26
2.1. Lý thuyết về luật và luật kết hợp ............................................................ 26
2.1.1. Luật thừa.......................................................................................... 26
2.1.2. Luật kết hợp..................................................................................... 27
2.1.3. Một số tính chất của luật kết hợp[6]................................................. 30
2.1.4. Phát biểu bài toán khai phá luật kết hợp[8] ...................................... 31
2.1.5. Một số hướng tiếp cận trong khai phá luật kết hợp........................... 32
2.2. Các đặc trưng của luật kết hợp ............................................................... 34
2.2.1. Không gian tìm kiếm của luật .......................................................... 34
4
2.2.2. Độ hỗ trợ của luật ............................................................................ 36
2.3.Một số giải thuật cơ bản khai phá các tập phổ biến ................................. 36
2.3.1.Kỹ thuật BFS .................................................................................... 37
2.3.2.Kỹ thuật DFS.................................................................................... 44
2.5. Thuật toán AIS....................................................................................... 44
2.5.1. Bài toán đặt ra.................................................................................. 44
2.5.2. Thuật toán AIS................................................................................. 45
2.6. Thuật toán SETM................................................................................... 47
2.6.1. Bài toán đặt ra.................................................................................. 47
2.6.2. Thuật toán SETM ............................................................................ 47
2.7. Thuật toán CHARM[9] .......................................................................... 50
2.7.1. Tư tưởng thuật toán CHARM .......................................................... 50
2.7.1.1. Cơ sở lý thuyết .......................................................................... 50
2.7.2.2. Bài toán đặt ra............................................................................ 52
2.7.2. Thuật toán CHARM......................................................................... 53
2.8. Kết luận.................................................................................................. 56
Chương 3 ........................................................................................................ 57
ỨNG DỤNG KHAI PHÁ LUẬT KẾT HỢP TRONG ĐÀO TẠO .............. 57
3.1. Bài toán.................................................................................................. 57
3.2. Đặc tả dữ liệu......................................................................................... 58
3.3. Chương trình thử nghiệm minh họa........................................................ 63
3.4. Kết luận .............................................................................................. 66
KẾT LUẬN...................................................................................................... 67
PHỤ LỤC ........................................................................................................ 68
TÀI LIỆU THAM KHẢO................................................................................ 77
5
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
Từ viết tắt
ADO
BFS
Tiếng Anh
Activate X Data Object
Breadth First Search
Ck
Tiếng Việt
Tìm kiếm theo bề rộng
Tập các K – itemset ứng cử
Độ tin cậy
Ck
Conf
confidence
CSDL
DFS
Database
Cơ sở dữ liệu
Depth First Search
Data Warehouse
item
Tìm kiếm theo độ sâu
Kho dữ liệu
DW
Item
Khoản mục
Itemset
itemset
Tập các khoản mục
Tập gồm K mục
K- itemset K- itemset
KDD
Knowledge Discovery and
Kỹ thuật phát hiện tri thức và khai
phá dữ liệu
Data Mining
Lk
Lk
Tập các K - itemset phổ biến
Độ tin cậy tối thiểu
Minconf
Minsup
MOLAP
OLAP
Minimum Confidence
Minimum Support
Multidimensional OLAP
Độ hỗ trợ tối thiểu
Phân tích đa chiều trực tuyến
Phân tích trực tuyến
On Line Analytical
Processing
ROLAP
Record
Supp
TID
Relational OLAP
Phân tích quân hệ trực tuyến
Bản ghi
record
suppport
Độ hỗ trợ
Transaction Indentification
Structured Query Language
Sematics Query Optimization
Định danh giao tác
Ngôn ngữ vấn đáp chuẩn
SQL
SQO
TC
Tính chất
6
DANH MỤC CÁC HÌNH VẼ
Hình 1.1: Các bước trong quá trình phát hiện tri thức ....................................................11
Hình 1.2: Kiến trúc hệ thống khai phá dữ liệu ................................................................12
Hình 1.3: Ví dụ mô hình khai phá dữ liệu .......................................................................15
Hình 1.4: Ví dụ cây quyết định.........................................................................................17
Hình 1.5: Ví dụ về luật kết hợp ........................................................................................19
Hình 1.6: Ví dụ Form nhập liệu........................................................................................24
Bảng 2.1: Ví dụ về một cơ sở dữ liệu dạng giao dịch - D...............................................28
Bảng 2.2 : Các tập phổ biến trong cơ sở dữ liệu ở bảng 1 với độ hỗ trợ tối thiểu 50% 28
Hình 2.3: Dàn cho tập I = {1,2,3,4} .................................................................................34
Hình 2.4: Cây cho tập I = {1, 2, 3, 4} ..............................................................................35
Hình 2.5: Hệ thống hóa các giải thuật..............................................................................37
Bảng 2.6: Ví dụ thuật toán Apriori...................................................................................42
Bảng 2.7. Ví dụ thuật toán AIS ........................................................................................46
Bảng 2.8: Ví dụ thuật toán SETM....................................................................................50
Bảng 2.9: Tập các giao dịch trong ví dụ thuật toán CHARM ........................................53
Bảng 2.10: Tập mục phổ biến trong ví dụ minh hoạ thuật toán CHARM.....................54
Hình 2.11: Thuật toán CHARM sắp xếp theo thứ tự từ điển..........................................54
Hình 2.12: Sắp xếp theo độ hỗ trợ tăng dần ....................................................................55
Hình 3.1: Trường Đại học Dân lập Hải phòng ................................................................57
Bảng 3.2: Ví dụ CSDL điểm của sinh viên......................................................................59
Bảng 3.3: Dữ liệu đã chuyển đổi từ dạng số sang dạng logic.........................................60
Bảng 3.4: Bảng ký hiệu tên các môn học.........................................................................63
Hình 3.5: Sơ đồ quan hệ CSDL điểm sinh viên ..............................................................63
Hình 3.6: Giao diện chương trình chính ..........................................................................63
Hình 3.7: Phần kết nối CSDL...........................................................................................64
Hinh 3.8: Form cập nhật điểm sinh viên..........................................................................64
Hình 3.9: Form cập nhật thêm sinh viên..........................................................................64
Hình 3.10: Phần dữ liệu đã được mã hoá.........................................................................65
Hình 3.11: Phần tạo luật kết hợp dùng thuật toán Apriori..............................................65
Hình 3.12: Phần mô phỏng thuật toán với dữ liệu nhập vào từ bàn phím.....................66
7
LỜI MỞ ĐẦU
Ngày nay công nghệ thông tin luôn luôn phát triển và không ngừng đổi mới, cùng
với sự phát triển đó là các hệ thống thông tin phục vụ việc tự động hoá trong các lĩnh
vực của con người cũng được triển khai vượt bậc. Điều đó đã tạo ra những dòng dữ
liệu khổng lồ. Nhiều hệ quản trị CSDL mạnh cũng đã ra đời giúp chúng ta khai thác
hiệu quả nguồn tài nguyên đã thu thập được.
Với lượng dữ liệu, thông tin thu thập được ngày càng nhiều như vậy đòi hỏi
chúng ta phải trích rút ra những thông tin tiềm ẩn nhằm đưa ra các quyết định đúng
đắn trong công việc. Xuất phát từ thực tiễn đó, vào những năm cuối của thế kỷ 20 khai
phá dữ liệu ra đời. Đây là một lĩnh vực nghiên cứu khá mới mẻ của ngành khoa học
máy tính và khai phá tri thức (KDD). Nó đã thu hút sự quan tâm của rất nhiều người ở
các lĩnh vực khác nhau như : các hệ CSDL, thống kê, nhận dạng, máy học, trí tuệ nhân
tạo...
Khai phá dữ liệu sử dụng các công cụ phân tích dữ liệu như: truy vấn, báo cáo,
dịch vụ phân tích trực tuyến (OLAP, ROLAP, MOLAP) để tìm ra các mẫu có giá trị
trong kho dữ liệu. Khai phá dữ liệu đã và đang được ứng dụng thành công vào các
ngành thương mại, tài chính, kinh doanh, sinh học, y học, giáo dục, viễn thông...
Khai phá luật kết hợp từ CSDL lớn được khởi xướng từ năm 1993, nó đã và đang
được nghiên cứu, phát triển mạnh vì khả năng tìm được các luật có ích, từ đó có những
dự báo giúp chúng ta có kế hoạch các hướng phát triển cho tương lai.
Việc khai phá luật kết hợp ứng dụng vào trong công tác đào tạo còn chưa được
nghiên cứu và ứng dụng tối đa. Để từng bước nâng cao khả năng ứng dụng khai phá
luật kết hợp vào giải quyết những công việc trong công tác đào tạo đạt hiệu quả cao,
bằng những kinh nghiệm thực tế và qua kiến thức thu thập được trong những năm theo
học tại khoa Công nghệ Thông tin trường đại học Quốc Gia Hà Nội, nghiên cứu giảng
dạy tại trường đại học Dân Lập Hải Phòng, chính vì vậy tác giả chọn đề tài “KHAI
PHÁ DỮ LIỆU ỨNG DỤNG TRONG ĐÀO TẠO”. Nội dung chính của đề tài là đi
sâu vào tìm hiểu một số thuật toán khai phá luật kết hợp và áp dụng thuật toán kinh
điển Apriori ứng dụng trong công tác đào tạo của trường đại học Dân lập Hải Phòng.
Kết quả nghiên cứu sẽ cung cấp các thông tin hỗ trợ cho sinh viên lựa chọn môn học,
ngành học, hướng nghiên cứu, đồng thời hỗ trợ cán bộ làm công tác tư vấn đào tạo,
cán bộ phòng đào tạo được thuận lợi hơn trong công tác đào tạo.
Nội dung của luận văn gồm 3 chương và phần phụ lục:
8
Chương 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ PHÁT HIỆN TRI
THỨC. Chương này đề cập đến các giai đoạn của quy trình phát hiện tri thức, các vấn
đề chính của khai phá dữ liệu, các phương pháp, các nhiệm vụ trong khai phá dữ liệu.
Chương 2: CƠ SỞ LÝ THUYẾT CỦA LUẬT KẾT HỢP, MỘT SỐ THUẬT
TOÁN PHÁT HIỆN LUẬT KẾT HỢP. Chương này trình bày một số vấn đề chính của
khai phá luật kết hợp: lý thuyết luật kết hợp, bài toán khai phá và phát hiện luật kết
hợp, các phương pháp phát hiện luật kết hợp, một số thuật toán điển hình giải quyết
vấn đề, phân tích độ phức tạp của bài toán.
Chương 3: ỨNG DỤNG KHAI PHÁ LUẬT KẾT HỢP TRONG ĐÀO TẠO.
Nội dung của chương là áp dụng kỹ thuật khai phá luật kết hợp vào trong đào tạo của
trường Đại học Dân lập Hải phòng. Ứng dụng này nhằm đưa ra dự báo hỗ trợ cho công
tác đào tạo của trường.
Phần phụ lục đưa ra một số modul của chương trình ứng dụng. Cuối cùng là kết
luận lại những kết quả đạt được của đề tài và hướng phát triển trong tương lai.
9
Chương 1
TỔNG QUAN KHAI PHÁ DỮ LIỆU
VÀ PHÁT HIỆN TRI THỨC
1.1. Khái niệm phát hiện tri thức và khai phá dữ liệu
Việc dùng các phương tiện tin học để tổ chức và khai thác các CSDL đã được
phát triển từ những năm 60, nhiều CSDL đã được tổ chức, phát triển và khai thác ở
mọi qui mô và khắp các lĩnh vực hoạt động của xã hội. Với sự phát triển mạnh mẽ của
máy tính và các mạng viễn thông, người ta đã xây dựng được nhiều hệ CSDL lớn tập
trung hoặc phân tá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ả các nguồn tài nguyên dữ liệu trong các
hoạt động kinh tế xã hội.
Tuy nhiên từ đầu thập niên 90, con người mới thực sự bước vào giai đoạn bùng
nổ thông tin. Nhờ áp dụng các công nghệ và kỹ thuật mới, rất nhiều các thiết bị tiên
tiến ra đời có khả năng hỗ trợ đắc lực cho việc thu thập, lưu trữ và khai thác dữ liệu.
Các thiết bị lưu trữ với tốc độ cao, dung lượng lớn như đĩa từ, CD/DVD-ROM, thiết bị
điều khiển từ xa, vệ tinh nhân tạo… đã giúp con người hàng ngày thu thập được hàng
chục, hàng trăm gigabytes dữ liệu.
Sự phát triển nhanh chóng của một lượng lớn dữ liệu được thu thập và lưu trữ
trong các CSDL lớn đã vượt ra ngoài khả năng của con người có thể hiểu được chúng
nếu không có những công cụ hỗ trợ tốt. Kết quả là, dữ liệu thu thập được trong một
lượng lớn CSDL đã trở thành những đống dữ liệu mà ít khi được xem xét đến. Do vậy,
việc đưa ra những quyết định thường không dựa vào những thông tin hoặc dữ liệu thu
thập được mà chỉ dựa vào nhận thức, suy đoán của người đưa ra quyết định. Đơn giản
là vì họ không có những công cụ giúp cho việc lấy ra những tri thức từ lượng lớn dữ
liệu. Tình huống này đã đặt chúng ta trong hoàn cảnh nhiều dữ liệu nhưng thiếu thông
tin, thiếu tri thức. Với một khối lượng lớn dữ liệu như vậy rõ ràng là các phương pháp
thủ công truyền thống áp dụng để phân tích dữ liệu như chia bảng không còn là phù
hợp nữa. Và có một kỹ thuật mới ra đời đó là kỹ thuật khai phá tri thức trong cơ sở dữ
kiệu (Knowledge Discovery in Database) gọi tắt là KDD.
Thuật ngữ KDD được đưa ra vào năm 1989 với ý nghĩa là thực hiện các xử lý để
tìm ra các tri thức trong CSDL và mục đích nhấn mạnh đến các ứng dụng ở mức cao
hơn của khai phá dữ liệu (data mining). Khai phá dữ liệu thường được dùng trong các
lĩnh vực thống kê, đánh giá dữ liệu và các hệ thống quản lý dữ liệu.
10
Chúng ta có thể phân biệt một cách tương đối giữa phát hiện tri thức trong CSDL
và khai phá dữ liệu. KDD để chỉ một quá trình tổng thể bao gồm nhiều bước nhằm
phát hiện ra các tri thức hữu ích trong dữ liệu còn khai phá dữ liệu chỉ tập trung vào
việc ứng dụng các thuật toán nhằm phát hiện các mẫu từ dữ liệu mà không có thêm các
bước của quá trình KDD như bước kết hợp với tri thức đã có hoặc bước đánh giá kết
quả thu được. Các bước thêm vào này rất cần thiết để thấy rõ được rằng những thông
tin thu được từ dữ liệu là thực sự hữu ích. Đối với quá trình khai phá dữ liệu, nhiều khi
các mẫu thu được nhờ thực hiện một ứng dụng nào đó không có giá trị hoặc không
phục vụ cho mục đích nào. Như vậy, một quá trình phát hiện tri thức từ dữ liệu được
đặc trưng bằng các bước lặp chính là lặp lại các ứng dụng theo một thuật toán khai phá
dữ liệu cụ thể và hiểu các mẫu thu được từ thuật toán này
Định nghĩa: “KDD là một quá trình không tầm thường của việc xác định các
mẫu mới, có giá trị, có hiệu quả sử dụng và cơ bản hiểu được trong cơ sở 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.
1.2. Các bước trong quá trình phát hiện tri thức[7]
Phát hiện tri thức bao gồm nhiều giai đoạn được lặp đi lặp lại nhiều lần mà không
cần phân biệt từng bước trong quá trình thực hiện.
1. Giai đoạn 1: Hình thành, xác định và định nghĩa bài toán. Là việc 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 cùng với bản
chất của dữ liệu.
2. Giai đoạn 2: Thu thập và tiền xử lý ( xử lý thô). Bước này còn được gọi là tiền xử
lý dữ liệu nhằm loại bỏ nhiễu (dữ liệu dư thừa), làm sạch dữ liệu, xử lý và khắc
phục vấn đề thiếu hoặc thừa 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 (bước quan trọng) trong toàn bộ
quy trình phát hiện tri thức.
11
3. Giai đoạn 3: Biến đổi dữ liệu, chọn lựa một số phương pháp. Phân loại
(Classification), hồi quy (Regression), phân nhóm (Clustering), quy nạp, tổng hợp
kết quả (Summarization).
Giải thích kết quả
và đánh giá mẫu
Tri thức và
cách sử dụng
Khai phá dữ liệu
Biến đổi dữ liệu
Thu thập và tiền xử lý
Hình thành, xác định và
Mẫu và
mô hình
định nghĩa vấn đề
Dữ liệu
đã được
Dữ liệu đã
biến đổi
được tiền xử
lý
Mục
tiêu dữ
liệu
Internet,...
Kho dữ liệu
Hình 1.1: Các bước trong quá trình phát hiện tri thức
4. Giai đoạn 4: Khai phá dữ liệu, hay nói cách khác là trích chọn, chiết xuất ra các
mẫu hay các mô hình tiềm ẩn dưới các dữ liệu có ý nghĩa, hiểu được. 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 khai
phá dữ liệu, dùng phương pháp khai phá nào là thích hợp?.
5. Giai đoạn 5: Giải thích kết quả và đánh giá các mẫu hay mô hình. Các mẫu và mô
hình này là kết quả của giai đoạn 3 trong quy trình. Đây là công đoạn không thể
thiếu trong quá trình khai phá tri thức.
6. Giai đoạn 6: Hiểu và sử dụng 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 trên tất cả các lần thực hiện.
Tóm lại: Quá trình phát hiện tri thức từ trong kho dữ liệu (KDD – Knowledge
Discovery Database) là 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.
12
1.3. Kiến trúc hệ thống khai phá dữ liệu
Kiến trúc của hệ thống khai phá dữ liệu có thể chia thành các thành phần chính
như trong hình.
1- Kho dữ liệu: là một tập các cơ sở dữ liệu, các công cụ làm sạch dữ liệu và tích
hợp dữ liệu có thể thực hiện trên chúng.
2- Cơ sở tri thức: là yếu tố tri thức được dùng để đánh giá các mẫu kết quả khai
phá được.
Hình 1.2: Kiến trúc hệ thống khai phá dữ liệu
3- Kỹ thuật khai phá: là các công cụ để thực hiện các nhiệm vụ: mô tả, kết hợp,
phân lớp, phân nhóm dữ liệu.
4- Công cụ đánh giá mẫu: gồm một số modul sử dụng các độ đo và tương tác với
các modul khai phá dữ liệu để tập trung vào các thuộc tính cần quan tâm.
5- Biểu diễn dạng đồ hoạ: modul này giao tiếp giữa người dùng và hệ thống khai
phá dữ liệu.
1.4. Các loại dữ liệu sử dụng
1.4.1. Cơ sở dữ liệu quan hệ
Các CSDL quan hệ là một trong những kho chứa phổ biến nhiều thông tin nhất
và là dạng dữ liệu chủ yếu để nghiên cứu khai phá dữ liệu.
1.4.2. Kho dữ liệu
13
Kho dữ liệu (Data Warehouse) chứa thông tin thu thập từ nhiều nguồn, được lưu
trữ trong một lược đồ hợp nhất. Kho dữ liệu được tổ chức theo các chủ đề và cung cấp
tính lịch sử, tổng hợp cao với cấu trúc vật lý là CSDL quan hệ hoặc khối dữ liệu nhiều
chiều. Kho dữ liệu là môi trường tốt nhất cho khai phá dữ liệu hoạt động hiệu quả.
1.4.3. Cơ sở dữ liệu không gian
CSDL không gian chứa các thông tin có quan hệ về mặt không gian như CSDL
địa lý, CSDL ảnh vệ tinh và y học…Dữ liệu được biểu diễn theo dạng mã vạch, chứa
bản đồ bit n- chiều hoặc bản đồ các điểm pixel. Bản đồ có thể được biểu diễn thành
dạng vectơ trong đó đường phố, cầu, toà nhà, hồ…Khai phá dữ liệu có thể phát hiện
mẫu bằng cách mô tả đặc trưng của ngôi nhà gần một vị trí nào đó như hồ chẳng hạn.
Nói chung, các khối dữ liệu không gian có thể tổ chức thành cáu trúc đa chiều và phân
cấp.
1.4.4. Cơ sở dữ liệu văn bản
CSDL văn bản chứa các mô tả từ như các câu, đoạn. Có nhiều CSDL văn bản có
tính phi cấu trúc như các trang Web hoặc nửa cấu trúc như các message mail, trang
XML…Để phát hiện các đặc tả chung của các lớp đối tượng, từ khoá, nội dung liên
quan, đối tượng văn bản…các phương pháp khai phá dữ liệu cần tích hợp với các kỹ
thuật lấy thông tin và xây dựng từ điển, từ điển đồng nghĩa…
1.4.5. Dữ liệu Web
Dữ liệu Word Wide Web cung cấp các dịch vụ thông tin trực tuyến toàn cầu là cơ
hội phong phú với nhiều thách thức mới cho khai phá dữ liệu. Khai phá dữ liệu Web
với các mục đích như:
Khai phá nội dung Web để phát hiện ra các tri thức từ nội dung các trang
Web
Khai phá cấu trúc Web: phát hiện mô hình nền tảng cấu trúc liên kết.
Khai phá sử dụng Web: phát hiện thông tin từ các phiên làm việc truy
nhập của người dùng. Khi nắm bắt được các mẫu tra cứu trang có thể sắp
xếp lại các liên kết và đưa các quảng cáo vào những trang mà người dùng
thường quan tâm
1.5. Các phương pháp khai phá dữ liệu
Khai phá dữ liệu là lĩnh vực mà con người luôn tìm cách đạt được mực đích sử
dụng thông tin của mình. Quá trình khai phá dữ liệu là quá trình phát hiện mẫu, trong
14
đó phương pháp khai phá dữ liệu để tìm kiếm các mẫu đáng quan tâm theo dạng xác
định. Có thể kể ra đây một vài phương pháp như: sử dụng công cụ truy vấn, xây dựng
cây quyết định, dựa theo khoảng cách (K-láng giềng gần), giá trị trung bình, phát hiện
luật kết hợp, … Các phương pháp trên có thể được phỏng theo và được tích hợp vào
các hệ thống lai để khai phá dữ liệu theo thống kê trong nhiều năm nghiên cứu. Tuy
nhiên, với dữ liệu rất lớn trong kho dữ liệu thì các phương pháp này cũng đối diện với
thách thức về mặt hiệu quả và quy mô.
1.5.1. Các thành phần của giải thuật khai phá dữ liệu
Giải thuật khai phá dữ liệu bao gồm 3 thành phần chính như sau: biểu diễn mô
hình, kiểm định mô hình và phương pháp tìm kiếm.
Biểu diễn mô hình: Mô hình được biểu diễn theo một ngôn ngữ L nào đó để miêu
tả các mẫu có thể khai thác được. Mô tả mô hình rõ ràng thì học máy sẽ tạo ra mẫu có
mô hình chính xác cho dữ liệu. Tuy nhiên, nếu mô hình quá lớn thì khả năng dự đoán
của học máy sẽ bị hạn chế. Như thế sẽ làm cho việc tìm kiếm phức tạp hơn cũng như
hiểu được mô hình là không đơn giản hoặc sẽ không thể có các mẫu tạo ra được một
mô hình chính xác cho dữ liệu. Ví dụ: mô tả cây quyết định sử dụng phân chia các nút
theo một trường dữ liệu, chia không gian đầu vào thành các siêu phẳng song song với
trục các thuộc tính. Phương pháp cây quyết định như vậy không thể khai phá được dữ
liệu dạng công thức “X = Y” dù cho tập học có quy mô lớn thế nào đi nữa. Vì vậy,
việc quan trọng là người phân tích dữ liệu là cần phải hiểu đầy đủ các giả thiết miêu tả.
Một điều cũng khá quan trọng là người thiết kế giải thuật cũng phải diễn tả được các
giả thiết mô tả nào được tạo ra bởi giải thuật nào. Khả năng miêu tả mô hình càng lớn
thì càng làm tăng mức độ nguy hiểm do bị học quá và làm giảm đi khả năng dự đoán
các dữ liệu chưa biết. Hơn nữa, việc tìm kiếm sẽ càng trở lên phức tạp hơn và việc giải
thích mô hình cũng khó khăn hơn.
Mô hình ban đầu được xác định bằng cách kết hợp biến đầu ra (phụ thuộc) với
các biến độc lập mà biến đầu ra phụ thuộc vào. Sau đó phải tìm những tham số mà bài
toán cần tập trung giải quyết. Việc tìm kiếm mô hình sẽ đưa ra được một mô hình phù
hợp với tham số được xác định dựa trên dữ liệu (trong một số trường hợp khác thì mô
hình và các tham số lại thay đổi để phù hợp với dữ liệu). Trong một số trường hợp, tập
các dữ liệu được chia thành tập dữ liệu học và tập dữ liệu thử. Tập dữ liệu học được
dùng để làm cho tham số của mô hình phù hợp với dữ liệu. Mô hình sau đó sẽ được
đánh giá bằng cách đưa các dữ liệu thử vào mô hình và thay đổi các tham số cho phù
hợp nếu cần. Mô hình lựa chọn có thể là phương pháp thống kê như SASS, … một số
giải thuật học máy (ví dụ như cây quyết định và các quyết định học có thầy khác),
15
mạng neuron, suy diễn hướng tình huống (case based reasoning), các kỹ thuật phân
lớp.
Hình 1.3: Ví dụ mô hình khai phá dữ liệu
Kiểm định mô hình (model evaluation): Là việc đánh giá, ước lượng các mô hình
chi tiết, chuẩn trong quá trình xử lý và phát hiện tri thức với sự ước lượng có dự báo
chính xác hay không và có thoả mãn cơ sở logic hay không? Ước lượng phải được
đánh giá chéo (cross validation) với việc mô tả đặc điểm bao gồm dự báo chính xác,
tính mới lạ, tính hữu ích, tính hiểu được phù hợp với các mô hình. Hai phương pháp
logic và thống kê chuẩn có thể sử dụng trong mô hình kiểm định.
Phương pháp tìm kiếm: Phương pháp này bao gồm hai thành phần: tìm kiếm
tham số và tìm kiếm mô hình. Trong tìm kiếm tham số, giải thuật cần tìm kiếm các
tham số để tối ưu hóa các tiêu chuẩn đánh giá mô hình với các dữ liệu quan sát được
và với một mô tả mô hình đã định. Việc tìm kiếm không cần thiết đối với một số bài
toán khá đơn giản: các đánh giá tham số tối ưu có thể đạt được bằng các cách đơn giản
hơn. Đối với các mô hình chung thì không có các cách này, khi đó giải thuật “tham
lam” thường được sử dụng lặp đi lặp lại. Ví dụ như phương pháp giảm gradient trong
giải thuật lan truyền ngược (backpropagation) cho các mạng neuron. Tìm kiếm mô
hình xảy ra giống như một vòng lặp qua phương pháp tìm kiếm tham số: mô tả mô
hình bị thay đổi tạo nên một họ các mô hình. Với mỗi một mô tả mô hình, phương
pháp tìm kiếm tham số được áp dụng để đánh giá chất lượng mô hình. Các phương
pháp tìm kiếm mô hình thường sử dụng các kỹ thuật tìm kiếm heuristic vì kích thước
của không gian các mô hình có thể thường ngăn cản các tìm kiếm tổng thể, hơn nữa
các giải pháp đơn giản (closed form) không dễ đạt được.
16
1.5.2. Phương pháp suy diễn / quy nạp
Một CSDL là một kho thông tin nhưng các thông tin quan trọng hơn cũng có thể
được suy diễn từ kho thông tin đó. Có hai kỹ thuật chính để thực hiện việc này là suy
diễn và 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 CSDL. 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ừ
CSDL. 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 CSDL. Phương pháp này
liên quan đến việc tìm kiếm các mẫu trong CSDL. 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.5.3. Phương pháp ứng dụng K-láng giềng
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 đã làm”.
Ví dụ: Để 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ể đó.
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 hạn là 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ế
17
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 K-lá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.5.4. Phương pháp sử dụng cây quyết định và luật[14]
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.
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.
Hình 1.4: Ví dụ cây quyết định
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.
18
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.5.5. 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 CSDL. 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 CSDL về các điểm của sinh viên, các dòng
tương ứng với các các sinh viên, các cột tương ứng với các điểm các môn học thì giá
trị 1 tại ô (Trần Thu Hà, lập trình C đạt 8) xác định rằng sinh viên đó cũng đạt (Trần
Thu Hà, hệ điều hành đạt 7).
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 {B}, r) còn gọi là độ hỗ trợ của luật, độ tin cậy của luật là
s(X {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 CSDL 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.
19
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.
Hình 1.5: Ví dụ về luật kết hợp
1.6. Các nhiệm vụ trong khai phá dữ liệu
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 đó, việ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:
20
1.6.1. Phát hiện các luật tối ưu truy vấn ngữ nghĩa
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:
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;
1. 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;
2. Các hệ thống lại 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í.
1.6.2. Phát hiện sự phụ thuộc Cơ sở dữ liệu
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.
21
1.6.3. Phát hiện sự sai lệch
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 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.
1.6.4. Phát hiện luật kết hợp
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ỏ hàng.
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 đó.
Một luật kết hợp là một quan hệ có dạng X Y, trong đó, X và Y là tập các
khoản mục và X Y = . Mỗi luật kết hợp được đặc trưng bởi độ hỗ trợ (sup) và độ
tin cậy (conf). sup được định nghĩa như tỷ lệ số giỏ thoả mãn cả X và Y trên toàn bộ số
giỏ. conf được xác định như tỷ lệ số giỏ thoả mãn cả X và Y trên toàn bộ chỉ thoả mãn
X. Ta sẽ tìm hiểu luật kết hợp ở phần sau.
1.6.5. Mô hình hoá sự phụ thuộc
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ể
22
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 giá trị thuộc tính. 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.
Quan hệ phụ thuộc cũng có thể biểu diễn dưới dạng Bayes. Đó là một đồ thị có
hướng, không chu trình. Các nút biểu diễn các thuộc tính và trọng số của cung biểu
diễn độ mạnh của sự phụ thuộc giữa các nút đó.
1.6.6. Mô hình hoá nhân quả
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ả.
Thuật toán phát hiện các luật nhân quả CAUDISCO áp dụng các phép kiểm tra
sự độc lập thống kê của từng cặp thuộc tính. Sau đó, đối với các thuộc tính phụ thuộc
lẫn nhau, thuật toán sẽ xác định mối quan hệ có là xác thực, tiềm năng hay chỉ là một
liên kết giả tạo, không phụ thuộc vào tập các điều kiện thoả mãn bởi quan hệ 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.
1.6.7. Phân cụm, nhóm
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 đó.
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
23
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.
1.6.8. Phân lớp
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”.
1.6.9. Hồi quy
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 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.
1.6.10. Tổng hợp
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
24
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 đó.
1.7. Các thách thức và giải pháp cơ bản
1.7.1. Thách thức
Cơ sở dữ liệu rất lớn: các CSDL với hàng trăm trường và bảng, hàng triệu bản
ghi, chiếm nhiều gigabyte và terabyte.
Kích thước chiều lớn: Tập dữ liệu lớn có nhiều thuộc tính và biến nên số chiều
của bài toán tăng làm cho không gian tìm kiếm mẫu tăng rất nhanh. Nếu giả sử có 3
mẫu thuộc tính, mỗi thuộc tính có 2 giá trị thì số các bản ghi là 23=8 và số mẫu sẽ là
3*3*3=27. Nếu có p thuộc tính, mỗi thuộc tính có d giá trị thì số mẫu dữ liệu là dp
Biến động dữ liệu và tri thức: Sự thay đổi nhanh chóng dữ liệu làm cho các mẫu
đã phát hiện trước đây có thể không còn đúng. Hơn nữa các độ đo biến trong các
CSDL ứng dụng có thể thay đổi, bị xoá, hoặc tăng lên theo độ đo mới. Các giải pháp
có thể là các phương pháp gia tăng để cập nhật các mẫu.
Thiếu dữ liệu và thừa dữ liệu: Đây là vấn đề có thể nói rất khó khăn cho việc khai
phá dữ liệu. Thông thường các hệ tác nghiệp chỉ quan tâm đến các dữ liệu cần để giải
quyết các hoạt động tác nghiệp hàng ngày, các dữ liệu khác chưa chú trọng thu thập
hoặc người thao tác không nhập vào, nếu họ cảm thấy chưa dùng để làm gì. Hầu hết
các thiết kế dữ liệu trong các hệ tác nghiệp về thuế cũng như bảo hiểm các số liệu về
tài chính, tài sản, thu nhập, vốn, doanh số, hoặc khai báo chi tiết tình trạng sức khoẻ
thường được bỏ qua mặc dù các thiết kế dữ liệu cũng như các Form nhập liệu đều đã
được cài đặt.
Hình 1.6: Ví dụ Form nhập liệu
25
1.7.2. Một số giải pháp
Có thuật toán hiệu quả và đủ mềm dẻo để tăng bộ nhớ.
Lấy ví dụ mẫu: Chọn lọc các bộ dữ liệu đặc trưng và tốt nhất.
Giảm chiều: Chọn lọc các thuộc tính thích hợp cho mục đích khai phá.
Tận dụng các xử lý song song: Hiện nay, do giá thành các thiết bị phần cứng
không cao lắm, có thể áp dụng các giải pháp song song cho việc khai phá dữ
liệu: Phân chia nhiệm vụ. dữ liệu cho nhiều bộ xử lý thực hiện đồng thời.
1.8. Kết luận
Nội dung chương đã tìm hiểu quá trình phát hiện tri thức và các vấn đề khai phá
dữ liệu. Phát hiện tri thức (KDD) là một quá trình rút ra tri thức từ dữ liệu mà trong đó
khai phá dữ liệu là giai đoạn chủ yếu. Khai phá dữ liệu là nhiệm vụ khám phá các mẫu
có ích từ số lượng lớn dữ liệu, ở đó dữ liệu có thể được lưu trữ trong các CSDL, kho
dữ liệu hoặc kho lưu trữ thông tin khác. Nó là một lĩnh vực còn mới mẻ, phát triển từ
các lĩnh vực như hệ thống CSDL, kho dữ liệu, thống kê, học máy, trực quan hoá dữ
liệu…Khám phá tri thức bao gồm nhiều giai đoạn trong đó giai đoạn khai phá dữ liệu
là giai đoạn quan trọng nhất. Chương này đã tóm tắt một số phương pháp phổ biến
dùng để khai phá dữ liệu và phân tích việc khai phá dữ liệu. Trong các phương pháp
khai phá dữ liệu, phát hiện các luật kết hợp là một lĩnh vực đang được quan tâm
nghiên cứu nhiều. Phần này sẽ được trình bày rõ hơn trong chương sau.
26
Chương 2
CƠ SỞ LÝ THUYẾT CỦA LUẬT KẾT HỢP, MỘT SỐ THUẬT
TOÁN PHÁT HIỆN LUẬT KẾT HỢP
2.1. Lý thuyết về luật và luật kết hợp
2.1.1. Luật thừa
a. Định nghĩa: Xét luật r: XY thuộc tập các luật {R} của một cơ sở tri thức.
Luật r được gọi là luật thừa nếu với các luật còn lại thuộc tập R {r} nếu chúng ta
có thể suy ra một luật r: XY
Một định nghĩa khác: Gọi R: tập luật của cơ sở tri thức; r thuộc R: XY; (X)R-
{r}: tập các mệnh đề suy ra từ X bằng các luật thuộc R-{r}; luật r: XY thuộc R gọi là
thừa nếu Y thuộc (X)R-{r}
Ví dụ: Xét tập luật sau:
R1: AB
R2: BC
R3: CD
R4: AD
Trong các luật trên, ta thấy luật R4: AD là thừa bởi vì: Từ R1, R2, R3, ta có:
ABCD
Thuật toán xác định (X)R-{r}
1. Bước 1: Ket qua:= X;
2. Bước 2: Với mọi r thuộc R, nếu vế trái r thuộc kết quả thì ket qua:= ket qua
Vephai(r)
3. Bước 3: Lặp lại bước 2 cho đến khi nào ket qua không thay đổi nữa. Khi đó ta
có (X)R-{r}
b. Thuật toán loại bỏ luật thừa:
Tư tưởng thuật toán gồm các bước sau:
1. Bước 1: t R = R {r}, từ định nghĩa của luật thừa trên, chúng ta có thuật
toán kiểm tra luật r: X Y có thừa trong tập các luật R hay không:
27
2. Bước 2: Xác định (X)R = (Aj| Aj là các mệnh đề có thể suy diễn từ X dựa
trên tập luật R)
3. Bước 3 : Kiểm tra nếu Y thuộc (X)R hay không:
nếu đúng: thì luật r là thừa đối với tập R
ngược lại: thì luật r không thừa đối với tập R
Giải thuật chính loại bỏ luật thừa:
Bước 1: Xét luật r trong tập luật R, kiểm tra r có thừa đối với tập R - {r} không?
Bước 2 : Nếu thừa thì R= R {r}; lặp lại bước 1 với luật khác.
Bước 3: Lặp lại cho đến khi không còn bỏ luật nào nữa.
2.1.2. Luật kết hợp
Cho một tập I = {I1, I2,...,Im} là tập gồm m khoản mục (item), còn được gọi là
các thuộc tính (attribute). Các phần tử trong I là phân biệt nhau. X I được gọi là tập
mục (itemset). Nếu lực lượng của X bằng k (tức là |X| = k) thì X được gọi là k-itemset.
Một giao dịch (transaction) T được định nghĩa như một tập con (subset) của các
khoản mục trong I (T I). Tương tự như khái niệm tập hợp, các giao dịch không được
trùng lặp, nhưng có thể nới rộng tính chất này của tập hợp và trong các thuật toán sau
này, người ta đều giả thiết rằng các khoản mục trong một giao dịch và trong tất cả các
tập mục (item set) khác, có thể coi chúng đã được sắp xếp theo thứ tự từ điển của các
item.
Gọi D là CSDL của n giao dịch và mỗi giao dịch được đánh nhãn với một định
danh duy nhất (Unique Transasction IDentifier-TID). Nói rằng, một giao dịch T D
hỗ trợ (support) cho một tập X I nếu nó chứa tất cả các item của X, nghĩa là X T,
trong một số trường hợp người ta dùng ký hiệu T(X) để chỉ tập các giao dịch hỗ trợ
cho X. Kí hiệu support(X) (hoặc supp(X), s(X)) là tỷ lệ phần trăm của các giao dịch hỗ
trợ X trên tổng các giao dịch trong D, nghĩa là:
T D X T
supp(X) =
D
Ví dụ về cơ sở dữ liệu D (dạng giao dịch) : I = {A, B, C, D, E}, T = {1, 2, 3, 4, 5,
6}. Thông tin về các giao dịch cho ở bảng sau :
28
Định danh giao dịch (TID)
Tập mục (itemset)
A B D E
1
2
3
4
5
6
B C E
A B D E
A B C E
A B C D E
B C D
Bảng 2.1: Ví dụ về một cơ sở dữ liệu dạng giao dịch - D
Tập phổ biến (frequent itemset): Support tối thiểu minsup ( 0, 1] (Minimum
Support) là một giá trị cho trước bởi người sử dụng. Nếu tập mục X I có supp(X)
minsup thì ta nói X là một tập phổ biến-frequent itemset (hoặc large itemset). Một
frequent itemset được sử dụng như một tập đáng quan tâm trong các thuật toán, ngược
lại, những tập không phải frequent itemset là những tập không đáng quan tâm. Trong
các trình bày sau này, ta sẽ sử dụng những cụm từ khác như “X có support tối thiểu”,
hay “X không có support tối thiểu” cũng để nói lên rằng X thỏa mãn hay không thỏa
mãn support(X) minsupp.
Ví dụ: Với cơ sở dữ liệu D cho ở bảng 1, và giá trị ngưỡng minsupp = 50% sẽ liệt
kê tất cả các tập phổ biến (frequent-itemset) như sau :
Các tập mục phổ biến
Độ hỗ trợ (supp) tương ứng
100% (6/6)
B
E, BE
83% (5/6)
A, C, D, AB, AE, BC, BD, ABE
67% (4/6)
AD, CE, DE, ABD, ADE, BCE, BDE 50% (3/6)
Bảng 2.2 : Các tập phổ biến trong cơ sở dữ liệu ở bảng 1
với độ hỗ trợ tối thiểu 50%
Một số tính chất (TC) liên quan đến các frequent itemset:
TC 1. support cho tất cả các subset: nếu A B, A, B là các itemset thì supp(A)
supp(B) vì tất cả các giao dịch của D support B thì cũng support A.
29
TC 2. Nếu một item A không có support tối thiểu trên D nghĩa là support(A) <
minsupp thì một superset B của A sẽ không phải là một frequent vì support(B)
support(A) < minsup.
TC 3. Nếu item B là frequent trên D, nghĩa là support(B) minsup thì mọi subset
A của B là frequent trên D vì support(A) support(B) > minsup.
Định nghĩa luật kết hợp: Một luật kết hợp có dạng R: X Y, trong đó X, Y là
các itemset, X, Y I và X Y = . X được gọi là tiên đề và Y được gọi là hệ quả của
luật.
Một số nhận xét :
. Luật X Y tồn tại một độ hỗ trợ support - supp. Supp(X Y) được định
nghĩa là khả năng mà tập giao dịch hỗ trợ cho các thuộc tính có có trong
cả X lẫn Y, nghĩa là: Support(XY) = support(XY).
. Luật X Y tồn tại một độ tin cậy c (confidence - conf). Conf c được định
nghĩa là khả năng giao dịch T hỗ trợ X thì cũng hỗ trợ Y. Nói cách khác c
biểu thị số phần trăm giao dịch có chứa luôn Y trong số những giao dịch
có chứa X.
. Ta có công thức tính conf c như sau: conf(X Y) = p(Y I | X I ) =
p(Y T X T) sup p(X Y)
p(X T)
sup p(X )
. Ta nói rằng, luật X Y là thoả trên D nếu với một support tối thiểu
minsup và một ngưỡng cofidence tối thiểu minconf cho trước nào đó mà:
Support(X
Y) ≥ minsup và confidence(X Y) ≥ minconf
Chú ý rằng, nếu luật X Y mà thoả trên D thì cả X và Y đều phải là các
Frequent Itemset trên D và khi xét một luật có thoả hay không, thì cả support và
confidence của nó đều phải quan tâm, vì một luật có thể có confidence = 100% >
minconf nhưng có thể là nó không đạt support tối thiểu minsup.
Khi khai phá các luật kết hợp, có 2 vấn đề chính cần phải giải quyết :
. Thứ nhất, đó là độ phức tạp của giải thuật. Số lượng luật tăng theo cấp độ
luỹ thừa cùng với số lượng các mục (item). Tuy nhiên, các giải thuật hiện
nay có thể giảm bớt không gian tìm kiếm này dựa trên các ngưỡng tối
thiểu để đánh giá độ hiệu quả của luật.
. Thứ hai, các luật tốt (tối ưu) phải được lấy ra từ tập hợp các luật tìm được.
Điều này rất khó bởi vì tập hợp các luật tìm được là rất lớn, trong đó số
30
lượng các luật có thể dùng được lại chiếm tỷ lệ vô cùng nhỏ. Các nghiên
cứu liên quan đến vấn đề thứ hai hầu hết chú trọng vào việc giúp người
dùng duyệt tập luật cũng như việc phát triển các độ đo chất lượng của luật.
2.1.3. Một số tính chất của luật kết hợp[6]
Trước hết ta phải giả sử rằng với luật X
Y, X có thể là rỗng, còn Y phải luôn
support(X Y)
1
khác rỗng và X Y vì nếu không thì: confidence(XY) =
Ta có các tính chất sau :
support(X)
1) Nếu X
Z và Y Z là thoả trên D, thì không nhất thiết là X Y Z.
Để ý đến trường hợp X Y = và các giao dịch trên D hỗ trợ Z nếu và chỉ nếu
chúng hỗ trợ X hoặc hỗ trợ Y. Khi đó support(X Y) = 0 và cofidence(X Y) = 0.
Tương tự ta cũng có : Nếu X Y và Z Z không thể suy ra X Y Z.
2) Nếu luật X Y Z là thoả trên D thì X Z và Y Z có thể không thoả trên
D.
Chẳng hạn, khi Z là có mặt trong một giao dịch chỉ nếu cả X và Y đều có mặt
trong giao dịch đó, nghĩa là support(X Y)=support(Z). Nếu support cho X và Y lớn
hơn support(X Y), thì 2 luật trên sẽ không có confidence yêu cầu. Tuy nhiên, nếu
X
Y Z là thoả trên D thì có thể suy ra X Y và X Z cũng thoả trên D Vì
support(XY) ≥ support(XYZ) và support(XZ) ≥ support(XYZ).
3) Nếu X Y và Y Z là thoả trên D thì không thể khẳng định rằng X Z cũng
giữ được trên D.
Giả sử T(X)T(Y) T(Z) và confidence(X Y) = confidence(Y Z) =
minconf. Khi đó ta có confidence(X Z) = minconf < minconf vì minconf <1, nghĩa
là luật X Z không có cofidence tối thiểu.
4) Nếu luật A (L-A) không có confidence tối thiểu thì cũng không có luật nào
trong các luật B
BA.
(L-B) có confidence tối thiểu trong đó L-A.B là các intemset và
Thật vậy, theo tính chất TC1, vì BA. Nên support(B) ≥ support(A) và theo định
nghĩa của confidence, ta có :
sup port(L)
sup port(B)
sup port(L)
sup port(A)
confidence(B (L-B)) =
<minconf.
Tải về để xem bản đầy đủ
78 trang
13/06/2025
50
Bạn đang xem 30 trang mẫu của tài liệu "Luận văn Phá dữ liệu ứng dụng trong đào tạo", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.
File đính kèm:
- luan_van_pha_du_lieu_ung_dung_trong_dao_tao.pdf
