Luận văn Thạc sĩ Khoa học máy tính: 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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:76

Thêm vào BST

Báo xấu

41
lượt xem 20
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học máy tính: 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

ĐẠ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 NAMchân NGỌC thành và sâu sắc nhất đến thầy 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 Tôi cũngCỨU LUẬT gửi lời cảm ơn đến KẾT HỢP các thầy cô trƣờngVÀ ỨNG Đại học DỤNG Công nghệ thông tin và Truyền TRONG BÀIthông – Đại học TOÁN XÂYThái Nguyên, DỰNG các thầy HỆcôHỖ Viện ÂNCông TRỢ nghệ thông tin đã truyền đạt những kiến thức và giúp đỡ tôi trong suốt quá trìnhHỌC SINH học của mình. TRUNG HỌC PHỔ THÔNG Chuyên ngành: Khoa học máy tính 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è 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 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ụ Kiểu phát hiện Mục đích Kiểu dự báo Hƣớng hệ quản trị SQO Tối ƣu truy vấn Không học CSDL Sự phụ thuộc Hƣớng hệ quản trị Thiết kế và duy trì Không học CSDL CSDL CSDL Phát hiện sai lệch Mục đích chung Xác định trội Không học Dự báo, xác định Phát hiện liên kết Mục đích chung Có học trội 11
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