Tóm tắt Luận văn Thạc sĩ Khoa học máy tính: Khai phá phụ thuộc hàm xấp xỉ sử dụng phủ tối thiểu và lớp tương đương

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

Thêm vào BST

Báo xấu

19
lượt xem 3
download

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

Luận văn này tìm hiểu về phụ thuộc hàm xấp xỉ và nghiên cứu thuật toán AFDMCEC, một thuật toán mới tìm các phụ thuộc hàm xấp xỉ trong các CSDL lớn dựa trên độ đo xấp xỉ. Thuật toán này sử dụng một số khái niệm trong lý thuyết thiết kế CSDL quan hệ, đặc biệt là các khái niệm phủ tối thiểu và lớp tương đương. 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: Tóm tắt Luận văn Thạc sĩ Khoa học máy tính: Khai phá phụ thuộc hàm xấp xỉ sử dụng phủ tối thiểu và lớp tương đương

i ĐẠ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 KHÁNH KHAI PHÁ PHỤ THUỘC HÀM XẤP XỈ SỬ DỤNG PHỦ TỐI THIỂU VÀ LỚP TƢƠNG ĐƢƠNG Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 TÓM TẮT LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Thái Nguyên - 2015 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
ii MỤC LỤC MỤC LỤC .................................................................................................................. i DANH MỤC VIẾT TẮT VÀ KÍ HIÊU ̣ .................................................................. iii DANH MỤC CÁC BẢNG BIỂU ............................................................................ iv DANH MỤC CÁC HÌNH VẼ ................................................................................... v MỞ ĐẦU ........................................................................................................... 1 CHƢƠNG 1....................................................................................................... 4 TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ KHAI PHÁ PHỤ THUỘC HÀM, PHỤ THUỘC HÀM XẤP XỈ ................................................................ 4 1.1. Khai phá dữ liệu ..................................................................................... 4 1.1.1. Khám phá tri thức và khai phá dữ liệu ............................................ 4 1.1.2. Kiến trúc của hệ thống khai phá dữ liệu ......................................... 6 1.1.3. Quá trình khai phá dữ liệu............................................................... 7 1.1.4. Một số kỹ thuật khai phá dữ liệu..................................................... 8 1.1.5. Các cơ sở dữ liệu phục vụ cho khai phá dữ liệu ........................... 12 1.1.6. Một số ứng dụng của khai phá dữ liệu .......................................... 14 1.2. Khai phá phụ thuộc hàm và phụ thuộc hàm xấp xỉ .............................. 15 1.2.1. Khai phá phụ thuộc hàm. .............................................................. 15 1.2.2. Khai phá phụ thuộc hàm xấp xỉ .................................................... 19 1.2.2.1. Định nghĩa phụ thuộc hàm xấp xỉ .......................................... 20 1.2.2.2. Một số độ đo cơ bản ............................................................... 21 CHƢƠNG 2 THUẬT TOÁN KHAI PHÁ PHỤ THUỘC HÀM XẤP XỈ SỬ DỤNG PHỦ TỐI THIỂU VÀ LỚP TƢƠNG ĐƢƠNG ........................... 28 2.1. Lớp tƣơng đƣơng và phủ tối thiểu ....................................................... 29 2.1.1. Sự phân hoạch ............................................................................... 29 2.1.2. Phân hoạch mịn hơn ...................................................................... 31 2.1.3. Phủ tối thiểu .................................................................................. 32 2.1.4. Phụ thuộc hàm xấp xỉ và lớp tƣơng đƣơng ................................... 35 2.2. Thuật toán TANE sửa đổi..................................................................... 38 2.2.1. Thủ tục chính của thuật toán TANE sửa đổi ................................. 38 2.2.2. Độ phức tạp của thuật toán TANE sửa đổi. .................................. 41 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
iii 2.3. Thuật toán khai phá phụ thuộc hàm xấp xỉ sử dụng phủ tối thiểu và lớp tƣơng đƣơng ................................................................................................ 41 2.3.1. Mô tả thuật toán ............................................................................ 41 2.3.2. Độ phức tạp của thuật toán khai phá phụ thuộc hàm xấp xỉ sử dụng phủ tối thiểu và lớp tƣơng đƣơng ............................................................ 44 2.3.3. Phân tích thử nghiệm, so sánh về độ phức tạp thời gian . ............ 45 2.3.3.1. Phân tích thử nghiệm. ............................................................ 45 2.3.3.2. So sánh về độ phức tạp thời gian (theo [8]) ........................... 46 CHƢƠNG 3 THỰC NGHIỆM KHAI PHÁ PHỤ THUỘC HÀM XẤP XỈ ... 48 3.1. Xây dựng chƣơng trình thực nghiệm ................................................... 48 3.1.1. Giới thiệu bài toán ......................................................................... 48 3.1.2. Dữ liệu thử nghiệm ....................................................................... 48 3.1.3. Xây dựng chƣơng trình thực nghiệm ............................................ 50 3.2. Thực nghiệm khai phá phụ thuộc hàm xấp xỉ ...................................... 50 3.3. Kết quả thực nghiệm ............................................................................ 51 KẾT LUẬN ..................................................................................................... 52 TÀI LIỆU THAM KHẢO ............................................................................... 53 PHỤ LỤC ........................................................................................................ 55 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
iv DANH MỤC VIẾT TẮT VÀ KÍ HIỆU SỬ DỤNG TRONG LUẬN VĂN Ký hiệu Diễn giải R U  Quan hê ̣ trên tâ ̣p thuô ̣c tính U U   A1, ..., Am Tâ ̣p m thuô ̣c tính. Lƣơ ̣c đồ quan hê ̣ với U là tập thuộc tính , F là tập S = (U, F) các phụ thuộc hàm trên U LĐQH Lƣơ ̣c đồ quan hê ̣ CSDL Cơ sở dữ liệu PTH Phụ thuộc hàm Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
v DANH MỤC CÁC BẢNG BIỂU Bảng 1.1: Ví dụ về quan hệ ............................................................................. 17 Bảng 1.2: Các thuật toán khai phá phụ thuộc hàm ......................................... 19 Bảng 1.3. Bảng quan hệ ví dụ về PTH xấp xỉ ................................................. 21 Bảng 1.4: Bảng dữ liệu quan hệ số ................................................................. 24 Bảng 1.5: Bảng quan hệ ví dụ ......................................................................... 25 Bảng 1.6: Bảng quan hệ ví dụ về phụ thuộc hàm điều kiện ........................... 27 Bảng 2.1: Bảng quan hệ vi dụ cho phân hoạch ............................................... 30 Bảng 2.2: Bảng quan hệ ví dụ cho phân hoạch mịn hơn ................................ 32 Bảng 2.3: Bảng quan hệ ví dụ cho phụ thuộc hàm xấp xỉ .............................. 36 Bảng 2.4: Thời gian thực hiện cho cả hai thuật toán ...................................... 45 Bảng 2.5: So sánh độ phức tạp thời gian dựa trên T(n) của hai thuật toán ..... 46 Bảng 3.1: Dữ liệu trích chọn để khai phá. ...................................................... 49 Bảng 3.2: Bảng mã hóa các thuộc tính............................................................ 49 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
vi DANH MỤC CÁC HÌNH VẼ Hình 1.1. Quá trình khám phá tri thức .............................................................. 5 Hình 1.2. Kiến trúc của hệ thống khai phá dữ liệu ........................................... 6 Hình 1.3: Quá trình khai phá dữ liệu................................................................. 7 Hình 1.4: Cây quyết định .................................................................................. 9 Hình 1.5: Mẫu kết quả của nhiệm vụ phân cụm dữ liệu ................................. 10 Hình 1.6: Mẫu kết quả của nhiệm vụ hồi quy ................................................. 11 Hình 1.7: Các loại phụ thuộc dữ liệu .............................................................. 16 Hình 1.8 : Kỹ thuật phát hiện phụ thuộc hàm ................................................. 18 Hình 2.1: Dàn cho các thuộc tính (A, B, C, D, E) .......................................... 38 Hình 3.1: Dữ liệu đã mã hóa chuẩn bị cho khai phá ....................................... 50 Hình 3.2: Giao diện kết quả đƣợc khai phá phụ thuộc hàm xấp xỉ................. 51 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
1 MỞ ĐẦU 1. Đặt vấn đề Trong những năm gần đây, Công nghệ thông tin (CNTT) phát triển mạnh mẽ đã tác động đến mọi mặt của xã hội, những thành tựu của công nghệ lƣu trữ đã cho phép tạo ra những nguồn dữ liệu khổng lồ. Việc khai thác các nguồn dữ liệu này ngày càng cấp thiết, đặt ra những thách thức lớn cho ngành CNTT, đặc biệt là lĩnh vực khai phá dữ liệu. Với nguồn dữ liệu lớn nhƣ vậy thì việc tìm kiếm, phân tích, xử lý và đƣa ra các thông tin cần thiết, phù hợp với thời gian và yêu cầu là điều không dễ dàng. Các phƣơng pháp khai thác cơ sở dữ liệu truyền thống ngày càng không đáp ứng đƣợc nhu cầu thực tế này. Vì vậy các phƣơng pháp nghiên cứu, tiếp cận với những công cụ cho phép phân tích, tổng hợp, khai phá tri thức từ dữ liệu một cách thông minh, hiệu quả đã đƣợc nhiều nhà khoa học quan tâm nghiên cứu. Khái niệm phụ thuộc hàm đóng một vai trò rất quan trọng trong lý thuyết cơ sở dữ liệu quan hệ. Các phụ thuộc hàm rất hữu ích trong việc phân tích và thiết kế cơ sở dữ liệu quan hệ nhƣ xác định khóa, xác định các dạng chuẩn, các vấn đề về nhất quán dữ liệu ... Tuy nhiên trong thực tế do có một số giá trị dữ liệu không chính xác hoặc một số ngoại lệ nào đó làm cho các phụ thuộc hàm không thỏa. Sự phụ thuộc tuyệt đối này dƣờng nhƣ quá nghiêm ngặt khi ta hình dung tới một quan hệ có hàng nghìn bộ, trong khi đó chỉ có khoảng vài bộ vi phạm phụ thuộc hàm. Bỏ qua các phụ thuộc hàm này sẽ làm mất tính chất phụ thuộc vốn có giữa các thuộc tính. Vì vậy các nhà nghiên cứu đã mở rộng khái niệm phụ thuộc hàm thành phụ thuộc hàm xấp xỉ theo một cách thức, một nghĩa nào đó, các phụ thuộc hàm xấp xỉ (Approximate Functional Dependencies - AFDs) này cho phép có một số lƣợng lỗi nhất định của các bộ dữ liệu đối với phụ thuộc hàm. Phụ thuộc hàm xấp xỉ đƣợc khai phá từ CSDL quan hệ biểu diễn các mối Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
2 quan hệ có ý nghĩa, có nhiều ứng dụng khác nhau nhƣ: Dự đoán giá trị thiếu thuộc tính trong bảng quan hệ bằng cách sử dụng các giá trị của các thuộc tính trong việc xác định tập hợp các AFDs, tối ƣu hóa truy vấn, viết lại câu truy vấn, chuẩn hóa cơ sở dữ liệu để cho hiệu suất tốt hơn và thiết kế lƣu trữ hiệu quả hơn,… Luận văn sẽ tìm hiểu về phụ thuộc hàm xấp xỉ và nghiên cứu thuật toán AFDMCEC, một thuật toán mới tìm các phụ thuộc hàm xấp xỉ trong các CSDL lớn dựa trên độ đo xấp xỉ. Thuật toán này sử dụng một số khái niệm trong lý thuyết thiết kế CSDL quan hệ, đặc biệt là các khái niệm phủ tối thiểu và lớp tƣơng đƣơng. 2. Đối tƣợng và phạm vi nghiên cứu Luận văn tìm hiểu tổng quan về khai phá dữ liệu, đi sâu tìm hiểu khái niệm phụ thuộc hàm, phụ thuộc hàm xấp xỉ và các tính chất, độ đo lỗi của phụ thuộc hàm xấp xỉ, từ đó nghiên cứu thuật toán TANE sửa đổi và thuật toán AFDMCEC tìm phụ thuộc hàm xấp xỉ. 3. Hƣớng nghiên cứu của đề tài - Tìm hiểu về phụ thuộc hàm, phụ thuộc hàm xấp xỉ và các độ đo lỗi của chúng. - Nghiên cứu về thuật toán khai phá phụ thuộc hàm xấp xỉ từ bảng quan hệ. 4. Phƣơng pháp nghiên cứu Phƣơng pháp nghiên cứu chính của luận văn là nghiên cứu lý thuyết kết hợp với đánh giá thực nghiệm, cụ thể là: Phân tích, tổng hợp các kết quả nghiên cứu về phụ thuộc hàm, phụ thuộc hàm xấp xỉ, … đã công bố trên các bài báo khoa học, hội thảo chuyên ngành trong và ngoài nƣớc. Từ đó, trình bày làm rõ vấn đề khai phá phụ thuộc hàm xấp xỉ sử dụng phủ tối thiểu và lớp tƣơng đƣơng. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
3 5. Ý nghĩa khoa học và thực tiễn Phụ thuộc hàm đóng vai trò quan trọng trong lý thuyết CSDL quan hệ. Tuy nhiên, trong thực tế do có một số giá trị dữ liệu không chính xác hoặc một số ngoại lệ nào đó, làm cho các phụ thuộc hàm không thỏa mãn. Sự phụ thuộc tuyệt đối này dƣờng nhƣ quá nghiêm ngặt khi ta hình dung một quan hệ có hàng nghìn bộ, trong khi đó chỉ có vài bộ vi phạm phụ thuộc hàm. Do vậy, mở rộng khái niệm phụ thuộc hàm thành phụ thuộc hàm xấp xỉ, cho phép có một số lỗi nhất định của các bộ dữ liệu, là rất cần thiết và có ý nghĩa cả về mặt lý thuyết cũng nhƣ thực tiễn. Các phụ thuộc hàm xấp xỉ không những giúp chúng ta thấy đƣợc mối quan hệ tiềm ẩn giữa các thuộc tính mà còn giúp ta thuận tiện hơn trong việc phân tích dữ liệu, đánh giá thông tin. Phát hiện phụ thuộc hàm xấp xỉ trong CSDL là một vấn đề nghiên cứu hấp dẫn và cũng là một trong những mục tiêu của phát hiện tri thức. Tiếp cận phụ thuộc hàm xấp xỉ sử dụng phủ tối thiểu và lớp tƣơng đƣơng của khai phá dữ liệu là một hƣớng đi thú vị, hứa hẹn nhiều kết quả và ứng dụng hiệu quả trong thực tiễn. 6. Cấu trúc luận văn: Luận văn đƣợc trình bày trong 3 chƣơng: Chƣơng 1: Tổng quan về khai phá dữ liệu và khai phá phụ thuộc hàm, phụ thuộc hàm xấp xỉ. Chƣơng 2: Thuật toán khai phá phụ thuộc hàm xấp xỉ sử dụng phủ tối thiểu và lớp tƣơng đƣơng. Chƣơng 3: Thực nghiệm khai phá phụ thuộc hàm xấp xỉ. Cuối cùng là kết luận của luận văn và tài liệu tham khảo. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
4 CHƢƠNG 1 TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ KHAI PHÁ PHỤ THUỘC HÀM, PHỤ THUỘC HÀM XẤP XỈ 1.1. Khai phá dữ liệu 1.1.1. Khám phá tri thức và khai phá dữ liệu Khai phá dữ liệu (KPDL) là việc rút trích tri thức một cách tự động và hiệu quả từ một khối dữ liệu lớn. Tri thức đó thƣờng ở dạng các mẫu có tính chất không tầm thƣờng, không tƣờng minh (ẩn), chƣa đƣợc biết đến và có tiềm năng mang lại lợi ích. Có một số nhà nghiên cứu còn gọi KPDL là phát hiện tri thức từ cơ sở dữ liệu (Knowledge Discovery in Database – KDD). Ở đây chúng ta có thể coi KPDL là cốt lõi của quá trình phát hiện tri thức. Quá trình phát hiện tri thức gồm các bƣớc: Bƣớc 1: Trích chọn dữ liệu (data selection): Là bƣớc trích chọn những tập dữ liệu cần đƣợc khai phá từ các tập dữ liệu lớn (databases, data ware houses). Bƣớc 2: Tiền xử lý dữ liệu (data preprocessing): Là bƣớc làm sạch dữ liệu (xử lý dữ liệu không đầy đủ, dữ liệu nhiễu, dữ liệu không nhất quán,…v.v), rút gọn dữ liệu (sử dụng các phƣơng pháp thu gọn dữ liệu, histograms, lấy mẫu…v.v), rời rạc hóa dữ liệu (dựa vào histograms, entropy, phân khoảng,...v.v). Sau bƣớc này, dữ liệu sẽ nhất quán, đầy đủ, đƣợc rút gọn và đƣợc rời rạc hóa. Bƣớc 3: Biến đổi dữ liệu (data transformation): Là bƣớc chuẩn hóa và làm mịn dữ liệu để đƣa dữ liệu về dạng thuận lợi nhất nhằm phục vụ cho các kỹ thuật khai thác ở bƣớc sau. Bƣớc 4: Khai phá dữ liệu (data mining): Đây là bƣớc quan trọng và tốn nhiều thời gian nhất của quá trình khám phá tri thức, áp dụng các kỹ thuật khai phá (phần lớn là các kỹ thuật của machine learning) để khai phá, trích chọn đƣợc các mẫu (pattern) thông tin, các mối liên hệ đặc biệt trong dữ liệu. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
5 Bƣớc 5: Đánh giá và biểu diễn tri thức (knowledge representation & evaluation): Dùng các kỹ thuật hiển thị dữ liệu để trình bày các mẫu thông tin (tri thức) và mối liên hệ đặc biệt trong dữ liệu đã đƣợc khai thác ở bƣớc trên biểu diễn theo dạng gần gũi với ngƣời sử dụng nhƣ đồ thị, cây, bảng biểu, luật,…v.v. Đồng thời bƣớc này cũng đánh giá những tri thức khám phá đƣợc theo những tiêu chí nhất định. Trong giai đoạn khai phá dữ liệu, có thể cần sự tƣơng tác của ngƣời dùng để điều chỉnh và rút ra các tri thức cần thiết nhất. Các tri thức nhận đƣợc cũng có thể đƣợc lƣu và sử dụng lại. Các Tri thức Các mẫu Dữ liệu đã sạch Dữ liệu đã chọn 5.Đánh giá và biểu diễn tri thức knowledge representation & evaluation 4.Khai phá dữ liệu Kho data mining dữ 3.Biến đổi dữ liệu liệu data transformation 2. Tiền xử lý dữ liệu data preprocessing 1. Trích chọn dữ liệu data selection Hình 1.1. Quá trình khám phá tri thức Việc KPDL có thể đƣợc tiến hành trên một lƣợng lớn dữ liệu có trong CSDL, các kho dữ liệu hoặc trong các loại lƣu trữ thông tin khác. Các mẫu đáng quan tâm có thể đƣợc đƣa đến ngƣời dùng hoặc đƣợc lƣu trữ trong một cơ sở tri thức. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
6 1.1.2. Kiến trúc của hệ thống khai phá dữ liệu Kiến trúc của một hệ thống KPDL điển hình có thể có các thành phần phần nhƣ hình 1.2. - CSDL, kho dữ liệu hoặc các lƣu trữ thông tin khác (Databases, Data ware house,…): Đây là một hay một tập CSDL, các kho dữ liệu, các trang tính hay các dạng lƣu trữ thông tin khác. Các kỹ thuật làm sạch dữ liệu và tích hợp dữ liệu có thể đƣợc thực hiện trên những dữ liệu này. (Graphical user interface) Giao diện đồ họa cho ngƣời dùng (Pattern evaluation) Đánh giá mẫu Cơ sở dữ liệu (Data mining engine) Máy khai phá dữ liệu (Knowledge-base) (Database or Warehouse Server Máy chủ CSDL hay ho dữ liệu Làm sạch: Tích hợp dữ liệu, lọc Cơ sở dữ liệu Kho dữ liệu Các lƣu trữ thông tin khác Hình 1.2. Kiến trúc của hệ thống khai phá dữ liệu - Máy chủ CSDL hay máy chủ kho dữ liệu (Database or Warehouse Server): Máy chủ này có trách nhiệm lấy những dữ liệu tích hợp dựa trên các Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
7 yêu cầu khai phá của ngƣời dùng. - Cơ sở tri thức (Knowledge-base): Đây là miền tri thức dùng để hƣớng dẫn việc tìm kiếm hay đánh giá độ quan trọng của các hình mẫu kết quả. - Máy KPDL (Data mining engine): Một hệ thống KPDL cần phải có một tập các modun chức năng để thực hiện công việc nhƣ: đặc trƣng hóa, kết hợp, phân lớp, phân cụm, phân tích sự tiến hóa. - Modun đánh giá mẫu (Pattern evaluation): Bộ phận này tƣơng tác với các modun KPDL để duyệt tìm các mẫu đáng đƣợc quan tâm. Nó có thể dùng các ngƣỡng về độ quan tâm để lọc mẫu đã khám phá đƣợc. Cũng có thể modun đánh giá mẫu đƣợc tích hợp vào modun khai phá, tùy theo cách cài đặt của phƣơng pháp khai phá đƣợc dùng. - Giao diện đồ họa ngƣời dùng (Graphical user interface): Bộ phận này còn cho phép ngƣời dùng giao tiếp với hệ thống KPDL. Ngoài ra, bộ phận này còn cho phép ngƣời dùng xem các lƣợc đồ CSDL, lƣợc đồ kho dữ liệu (hay các cấu trúc dữ liệu), các đánh giá mẫu và hiển thị các mẫu trong các khuôn dạng khác nhau. 1.1.3. Quá trình khai phá dữ liệu Quá trình khai phá dữ liệu đƣợc thể hiện bởi mô hình sau: Thống kê tóm tắt Xác định Xác định dữ Thu thập và Giải thuật Mẫu nhiệm vụ liệu liên quan tiền xử lý DL khai phá DL Dữ liệu trực tiếp Hình 1.3: Quá trình khai phá dữ liệu + Xác định nhiệm vụ: Xác định chính xác vấn đề cần giải quyết. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
8 + Xác định các dữ liệu liên quan dùng để xây dựng giải pháp. + Thu thập các dữ liệu có liên quan và xử lý chúng thành dạng sao cho giải thuật khai phá dữ liệu có thể hiểu đƣợc. Ở đây có thể gặp một số vấn đề: dữ liệu phải đƣợc sao ra nhiều bản (nếu đƣợc chiết suất vào các tệp), quản lý tập các tệp dữ liệu, phải lặp đi lặp lại nhiều lần toàn bộ quá trình (nếu mô hình dữ liệu thay đổi v.v.). + Chọn thuật toán khai phá dữ liệu thích hợp và thực hiện việc khai phá dữ liệu: nhằm tìm đƣợc các mẫu (pattern) có ý nghĩa dƣới dạng biểu diễn tƣơng ứng với các ý nghĩa đó. 1.1.4. Một số kỹ thuật khai phá dữ liệu Mục đích của khai phá dữ liệu là chiết xuất ra các tri thức có lợi cho kinh doanh hay cho nghiên cứu khoa học… Do đó, ta có thể xem mục đích của khai phá dữ liệu sẽ là mô tả các sự kiện và dự đoán. Các mẫu khai phá dữ liệu phát hiện đƣợc nhằm vào mục đích này. Dự đoán liên quan đến việc sử dụng các biến hoặc các đối tƣợng (bản ghi) trong CSDL để chiết xuất ra các mẫu, dự đoán đƣợc những giá trị chƣa biết hoặc những giá trị tƣơng lai của các biến đáng quan tâm. Mô tả tập trung vào việc tìm kiếm các mẫu mô tả dữ liệu mà con ngƣời có thể hiểu đƣợc. Một số kỹ thuật chính của khai phá dữ liệu: Phân lớp dữ liệu Khái niệm phân lớp dữ liệu đƣợc Han và Kamber đƣa ra năm 2000. Phân lớp dữ liệu là xây dựng một mô hình mà có thể phân các đối tƣợng thành những lớp để dự đoán giá trị bị mất tại một số thuộc tính của dữ liệu hay tiên đoán giá trị của dữ liệu sẽ xuất hiện trong tƣơng lai. Quá trình phân lớp dữ liệu đƣợc thực hiện qua hai bƣớc. Bước thứ nhất: Dựa vào tập hợp dữ liệu huấn luyện, xây dựng một mô hình mô tả những đặc trƣng của những lớp dữ liệu hoặc những khái niệm, đây là quá trình học có Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
9 giám sát, học theo mẫu đƣợc cung cấp trƣớc. Bước thứ hai: Từ những lớp dữ liệu hoặc những khái niệm đã đƣợc xác định trƣớc, dự đoán giá trị của những đối tƣợng quan tâm. Một kỹ thuật phân lớp dữ liệu đƣợc Han và Kamber đƣa ra là cây quyết định. Mỗi nút của cây đại diện một quyết định dựa vào giá trị thuộc tính tƣơng ứng. Kỹ thuật này đã đƣợc nhiều tác giả nghiên cứu và đƣa ra nhiều thuật toán. Một ví dụ tiêu biểu về cây quyết định: Hình 1.4: Cây quyết định Trong hình 1.4 là một cây quyết định cho lớp mua laptop, chỉ ra một khách hàng sẽ mua hay không mua một laptop. Mỗi nút lá đại diện một lớp mà đánh giá mua laptop là Yes hay No. Sau khi mô hình này đƣợc xây dựng, chúng ta có thể dự đoán việc có thể mua một laptop hay không dựa vào những thuộc tính khách hàng mới là tuổi và nghề nghiệp. Cây quyết định có thể ứng dụng rộng rãi trong nhiều hoạt động của đời sống thực. Phân nhóm dữ liệu Phân nhóm là kỹ thuật khai phá dữ liệu tƣơng tự nhƣ phân lớp dữ liệu. Tuy nhiên, sự phân nhóm dữ liệu là quá trình học không đƣợc giám sát, là quá trình nhóm những đối tƣợng vào trong những lớp tƣơng đƣơng, đến những đối tƣợng trong một nhóm là tƣơng đƣơng nhau, chúng phải khác với những đối tƣợng trong những nhóm khác. Trong phân lớp dữ liệu, một bản ghi thuộc về lớp nào Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
10 là phải xác định trƣớc, trong khi phân nhóm không xác định trƣớc. Trong phân nhóm, những đối tƣợng đƣợc nhóm lại cùng nhau dựa vào sự giống nhau của chúng. Sự giống nhau giữa những đối tƣợng đƣợc xác định bởi những chức năng giống nhau. Thông thƣờng những sự giống về định lƣợng nhƣ khoảng cách hoặc độ đo khác đƣợc xác định bởi những chuyên gia trong lĩnh vực của mình. Hình 1.5: Mẫu kết quả của nhiệm vụ phân cụm dữ liệu Đa số các ứng dụng phân nhóm đƣợc sử dụng trong sự phân chia thị trƣờng. Với sự phân nhóm khách hàng vào trong từng nhóm, những doanh nghiệp có thể cung cấp những dịch vụ khác nhau tới nhóm khách hàng một cách thuận lợi. Ví dụ, dựa vào chi tiêu, số tiền trong tài khoản và việc rút tiền của khách hàng, một ngân hàng có thể xếp những khách hàng vào những nhóm khác nhau. Với mỗi nhóm, ngân hàng có thể cho vay những khoản tiền tƣơng ứng cho việc mua nhà, mua xe,… Trong trƣờng hợp này ngân hàng có thể cung cấp những dịch vụ tốt hơn và cũng chắc chắn rằng tất cả các khoản tiền cho vay đều có thể thu hồi đƣợc. Ta có thể tham khảo một khảo sát toàn diện về kỹ thuật và thuật toán phân nhóm trong. Hồi qui (Regression): Là việc học một hàm ánh xạ từ một tập dữ liệu thành một biến dự đoán có giá trị thực. Nhiệm vụ hồi qui tƣơng tự nhƣ phân lớp, điểm khác nhau chính là ở chỗ thuộc tính để dự báo là liên tục chứ không rời rạc [6]. 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ổ Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
11 điển chẳng hạn nhƣ hồi qui tuyến tính. Tuy nhiên, phƣơng pháp mô hình hóa cũng đƣợc sử dụng. Nợ đƣờng hồi quy tuyến tính + 0 0 0 + 0 0 0 + + 0 0 Thu nhập + + 0 Hình 1.6: 0 + 0 Mẫu kết quả + của nhiệm 0 vụ hồi quy 0 + 0 Ứng dụng của hồi quy là rất nhiều, ví dụ: dự đoán số lƣợng sinh vật phát quang hiện thời trong khu rừng bằng cách dò tìm vi sóng bằng thiết bị cảm biến từ xa; dự đoán khả năng tử vong của bệnh nhân khi biết các kết quả xét nghiệm chẩn đoán; dự đoán nhu cầu tiêu thụ một sản phẩm mới bằng một hàm chi tiêu quảng cáo… hình 1.6 chỉ ra mẫu kết quả hồi quy tuyến tính đơn giản, ở đây tổng số nợ đƣợc điều chỉnh cho phù hợp giống nhƣ một hàm thu nhập tuyến tính. Việc điều chỉnh này là không đáng kể bởi vì chỉ tồn tại một tƣơng quan yếu giữa hai biến. Tổng hợp (summarization): Là công việc liên quan đến các phƣơng pháp tìm kiếm một mô tả cô đọng cho tập con dữ liệu. Các kỹ thuật tổng hợp thƣờng đƣợc áp dụng trong việc phân tích dữ liệu có tính thăm dò và báo cáo tự động. Mô hình hóa phụ thuộc (dependency modeling): Là việc tìm kiếm mô tả các phụ thuộc quan trọng giữa các biến. Mô hình phụ thuộc tồn tại hai mức: Mức cấu trúc của mô hình (thƣờng dƣới dạng đồ thị) xác định các biến phụ thuộc cục bộ vào các biến khác; Mức định lƣợng của mô hình xác định mức độ phụ thuộc của biến. Những phụ thuộc này thƣờng đƣợc biểu thị dƣới dạng luật. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
12 Quan hệ phụ thuộc cũng có thể biểu diễn dƣới dạng mạng tin cậy [6]. Đó là đồ thị có hƣớng không có dạng chu trình, các nút biểu diễn thuộc tính và trọng số chỉ liên kết phụ thuộc giữa các nút đó. Phát hiện sự thay đổi và độ lệch (change and deviation dectection): Nhiệm vụ này tập trung vào khám phá những thay đổi có ý nghĩa trong dữ liệu dựa vào các giá trị chuẩn hay độ đo đã biết trƣớc, phát hiện độ lệch đáng kể giữa nội dung của tập con dữ liệu và nội dung mong đợi. Hai mô hình độ lệch thƣờng dùng là lệch theo thời gian và lệch theo nhóm. Độ lệch theo thời gian là sự thay đổi có nghĩa của dữ liệu theo thời gian. Độ lệch theo nhóm là sự khác nhau giữa dữ liệu trong hai tập con dữ liệu, tính cả trƣờng hợp tập con của đối tƣợng này thuộc 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 nhau đáng kể so với toàn bộ đối tƣợng. 1.1.5. Các cơ sở dữ liệu phục vụ cho khai phá dữ liệu Dựa vào những kiểu dữ liệu mà kỹ thuật khai phá áp dụng, có thể chia dữ liệu thành các loại khác nhau. Cơ sở dữ liệu quan hệ Đến nay, hầu hết dữ liệu đƣợc lƣu giữ dƣới dạng cơ sở dữ liệu quan hệ. Cơ sở dữ liệu quan hệ là một nguồn tài nguyên lớn nhất chứa những đối tƣợng mà chúng ta cần khai phá. Cơ sở dữ liệu quan hệ có cấu trúc cao, dữ liệu đƣợc mô tả bởi một tập những thuộc tính và lƣu trong những bảng. Khai phá dữ liệu trên cơ sở dữ liệu quan hệ chủ yếu tập trung khai phá mẫu. Ví dụ, trong cơ sở dữ liệu của một ngân hàng, ta có thể tìm đƣợc những khách hàng có mức chi tiêu cao, ta có thể phân loại những khách hàng này dựa vào quá trình chi tiêu của họ. Cũng với việc phân tích những mục tiêu của khách hàng, chúng ta có thể cung cấp một số thông tin của khách hàng đến những doanh nghiệp khác. Giả sử rằng một khách hàng chi mỗi tháng 500 đô la cho thời trang, nếu đƣợc phép, ngân hàng có thể cung cấp thông tin về khách hàng này cho những cửa hàng thời Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
13 trang. Cơ sở dữ liệu giao tác Cơ sở dữ liệu giao tác là tập hợp những bản ghi giao dịch, trong đa số các trƣờng hợp chúng là những bản ghi các dữ liệu hoạt động của doanh nghiệp, tổ chức. Với tính phổ biến của máy tính và thƣơng mại điện tử, ngày nay có rất nhiều cơ sở dữ liệu giao tác. Cơ sở dữ liệu không gian Cơ sở dữ liệu không gian bao gồm hai phần: Phần thứ nhất là dữ liệu quan hệ hay giao tác, phần thứ hai là thông tin định vị hoặc thông tin địa lý. Ví dụ, những luật kết hợp trên cơ sở dữ liệu không gian mô tả mối quan hệ giữa các đặc trƣng trong cơ sở dữ liệu không gian. Dạng của luật kết hợp không gian có dạng X  Y, với X, Y là tập hợp những vị từ không gian. Những thuật toán khai phá luật kết hợp không gian tƣơng tự nhƣ khai phá luật kết hợp nhƣng thêm những vị từ về không gian. Cơ sở dữ liệu có yếu tố thời gian Giống nhƣ cơ sở dữ liệu không gian, cơ sở dữ liệu có yếu tố thời gian bao gồm hai phần: Phần thứ nhất là dữ liệu quan hệ hay giao tác, phần thứ hai là thông tin về thời gian xuất hiện dữ liệu ở phần thứ nhất. Những luật kết hợp có yếu tố thời gian có nhiều thông tin hơn những luật kết hợp cơ bản. Ví dụ, từ luật kết hợp cơ bản {Bia}  {Thuốc lá}, với dữ liệu có yếu tố thời gian chúng ta có thể có nhiều luật: Độ hỗ trợ của luật {Bia}  {Thuốc lá} là 20% từ 9 giờ đến 13 giờ là 50% trong thời gian từ 19 giờ tới 22 giờ. Rõ ràng rằng, những ngƣời bán lẻ có thể xác định chiến lƣợc để buôn bán tốt hơn. Hầu hết nghiên cứu về lĩnh vực này ngày nay hình thành một hƣớng khai phá dữ liệu mới gọi là khai phá mẫu lặp liên tục, khai phá tập mục dữ liệu thƣờng xuyên trong cơ sở dữ liệu thời gian. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
14 Cơ sở dữ liệu đa phƣơng tiện Số lƣợng trang web đang bùng nổ trên thế giới, web có mặt ở khắp mọi nơi, duyệt web đã là nhu cầu của mọi tầng lớp trong xã hội. Thông tin trên web đang phát triển với tốc độ rất cao, khai phá thông tin trên web (web mining) đã trở thành một lĩnh vực nghiên cứu chính của khai phá dữ liệu, đƣợc các nhà nghiên cứu đặc biệt quan tâm. Khai phá dữ liệu web thông thƣờng đƣợc chia thành ba phạm trù chính: Khai phá cách dùng web (web usage mining), khai phá cấu trúc web (web structure mining) và khai phá nội dung web (web content mining). Khai phá cách dùng web tập trung vào việc khai phá thông tin của ngƣời truy cập web. Với những thông tin này ngƣời khai phá dữ liệu có thể cung cấp những thông tin hữu ích cho ngƣời dùng và các nhà kinh doanh. 1.1.6. Một số ứng dụng của khai phá dữ liệu KPDL đƣợc vận dụng trong nhiều lĩnh vực khác nhau nhằm khai thác nguồn dữ liệu phong phú đƣợc lƣu trữ trong các hệ thống thông tin. Tuỳ theo bản chất của từng lĩnh vực, việc vận dụng KPDL có những cách tiếp cận khác nhau. KPDL đƣợc vận dụng có hiệu quả để giải quyết các bài toán phức tạp trong những ngành đòi hỏi kỹ thuật cao nhƣ: tìm kiếm mỏ dầu từ ảnh viễn thám, xác định vùng gãy trong ảnh địa chất để dự đoán thiên tai, cảnh báo hỏng hóc trong các hệ thống sản xuất. Phân nhóm và dự đoán là những kỹ thuật rất cần thiết cho việc quy hoạch và phát triển hệ thống quản lý và sản xuất trong thực tế nhƣ: dự đoán tái sử dụng điện năng cho các công ty cung cấp điện, lƣu lƣợng viễn thông cho các công ty điện thoại, mức độ tiêu thụ sản phẩm cho các nhà sản xuất, giá trị của sản phẩm trên thị trƣờng cho các công ty tài chính hay phân nhóm khách hàng tiềm năng. Ngoài ra KPDL còn đƣợc áp dụng trong việc giải quyết các vấn đề xã hội nhƣ: phát hiện tội phạm hay tăng cƣờng an ninh xã hội và mang lại những hiệu Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn