Luận văn Thạc sĩ Công nghệ thông tin: Hệ tư vấn và ứng dụng cho bài toán dự báo kết quả bóng đá

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

Thêm vào BST

Báo xấu

32
lượt xem 6
download

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

Mục tiêu nghiên cứu của đề tài là việc dự báo kết quả bóng đá cũng sẽ giúp cho người tham gia dự đoán có được những ý kiến gợi ý nhất định, tránh được những sai lầm không đáng có. Trang web dự báo kết quả bóng đá được xây dựng dựa trên hệ tư vấn. Luận văn tiến hành trình bày và phân tích dựa trên thuật toán lọc sử dụng độ đo tương tự để tính toán đưa ra khuyến nghị. Sau đó dựa trên kết quả phân tích để so sánh và đánh giá khả năng dự bá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ĩ Công nghệ thông tin: Hệ tư vấn và ứng dụng cho bài toán dự báo kết quả bóng đá

1 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ NINH HỆ TƢ VẤN VÀ ỨNG DỤNG CHO BÀI TOÁN DỰ BÁO KẾT QUẢ BÓNG ĐÁ LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN HÀ NỘI - 2014
2 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ NINH HỆ TƢ VẤN VÀ ỨNG DỤNG CHO BÀI TOÁN DỰ BÁO KẾT QUẢ BÓNG ĐÁ Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60480104 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS.TS Nguyễn Đình Hóa TS. Lê Hoàng Sơn HÀ NỘI - 2014
3 LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu độc lập của riêng tôi, không sao chép ở bất kỳ một công trình hoặc một luận văn, luận án của các tác giả khác. Các số liệu, kết quả nêu trong luận văn này là trung thực và chƣa đƣợc công bố trong bất kỳ công trình nào khác. Các trích dẫn, các số liệu và kết quả tham khảo dùng để so sánh đều có nguồn trích dẫn rõ ràng. Tôi xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy định cho lời cam đoan của mình. Hà Nội, tháng 12 năm 2014 Tác giả luận văn Nguyễn Thị Ninh
4 LỜI CẢM ƠN Trƣớc khi trình bày nội dung chính của luận văn, em xin bày tỏ lòng biết ơn sâu sắc tới PGS.TS Nguyễn Đình Hóa và Tiến sĩ Lê Hoàng Sơn, ngƣời đã tận tình hƣớng dẫn và tạo điều kiện để em có thể hoàn thành luận văn này. Thứ hai, em xin bày tỏ lòng biết ơn chân thành tới toàn thể các thầy cô giáo trong khoa Công nghệ thông tin, trƣờng Đại học Công nghệ Hà Nội, Đại học Quốc gia Hà Nội đã dạy bảo tận tình em trong suốt quá trình em học tập tại khoa. Thứ ba, em xin đƣợc gửi lời cảm ơn tới các thầy cô, các anh chị và các bạn trong Trung tâm Tính toán Hiệu năng cao, trƣờng Đại học Khoa học tự nhiên đã giúp đỡ em trong suốt thời gian làm luận văn này. Cuối cùng em xin chân thành cảm ơn tới gia đình, bạn bè, đồng nghiệp đã luôn bên em cổ vũ, động viên, giúp đỡ em trong suốt quá trình học tập và thực hiện luận văn này. Luận văn này đƣợc thực hiện dƣới sự tài trợ của đề tài NAFOSTED, mã số: 102.05-2014.01. Mặc dù đã cố gắng hoàn thành luận văn trong phạm vi và khả năng cho phép nhƣng chắc chắn sẽ không tránh khỏi những thiếu sót. Em rất mong đƣợc sự góp ý chân thành của thầy cô và các bạn để em hoàn thiện luận văn của mình. Xin chân thành cảm ơn! Hà Nội, ngày 02 tháng 12 năm 2014 Học viên Nguyễn Thị Ninh
5 MỤC LỤC LỜI CAM ĐOAN ........................................................................................................... 2 LỜI CẢM ƠN ................................................................................................................. 4 MỤC LỤC ...................................................................................................................... 5 DANH SÁCH HÌNH VẼ................................................................................................ 8 DANH SÁCH BẢNG ..................................................................................................... 9 DANH MỤC CÁC KÝ HIỆU VIẾT TẮT ................................................................... 10 MỞ ĐẦU ...................................................................................................................... 11 CHƢƠNG 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU............................................. 13 1.1. KHAI PHÁ DỮ LIỆU ............................................................................................13 1.1.1. Định nghĩa khai phá dữ liệu ...................................................................... 13 1.1.2. Khám phá tri thức ..................................................................................... 13 1.2. KỸ THUẬT KHAI PHÁ DỮ LIỆU.......................................................................14 1.2.1. Các thành tố cơ bản .................................................................................. 14 1.2.2. Các nhiệm vụ khai phá dữ liệu .................................................................. 16 1.2.3. Kỹ thuật khai phá dữ liệu .......................................................................... 17 1.3. ỨNG DỤNG CỦA KHAI PHÁ DỮ LIỆU ............................................................19 1.3.1. Ứng dụng của khai phá dữ liệu .................................................................. 19 1.3.2. Ứng dụng các phƣơng pháp khai phá dữ liệu trong hệ tƣ vấn ...................... 20 1.4. KẾT LUẬN CHƢƠNG ..........................................................................................21 CHƢƠNG 2. HỆ TƢ VẤN VÀ CÁC PHƢƠNG PHÁP LỌC .................................... 22 2.1. HỆ TƢ VẤN ..........................................................................................................22 2.1.1. Định nghĩa hệ tƣ vấn ................................................................................. 22 2.1.2. Các phƣơng pháp khuyến nghị .................................................................. 22 2.2. PHƢƠNG PHÁP LỌC CỘNG TÁC .....................................................................23 2.2.1. Khát quát lọc cộng tác............................................................................... 23 2.2.2. Cách tiếp cận dựa trên ngƣời dùng ............................................................ 24 2.2.3. Cách tiếp cận dựa trên tài nguyên .............................................................. 26 2.3. VẤN ĐỀ COLD - START .....................................................................................28
6 2.3.1. Phát sinh vấn đề cold - start ....................................................................... 28 2.3.2. Phƣơng pháp dựa trên nhân khẩu ............................................................... 29 2.4. PHƢƠNG PHÁP TIẾP CẬN ĐA CHIỀU .............................................................31 2.4.1. Mô hình khuyến nghị đa chiều .................................................................. 31 2.4.2. Giảm chiều cho mô hình khuyến nghị đa chiều .......................................... 32 2.5. NGỮ CẢNH TRONG HỆ TƢ VẤN .....................................................................34 2.5.1. Vai trò của ngữ cảnh ................................................................................. 34 2.5.2. Kết hợp ngữ cảnh trƣớc khi lọc ................................................................. 35 2.5.3. Kết hợp ngữ cảnh sau khi lọc .................................................................... 35 2.5.4. Kết hợp ngữ cảnh trong khi lọc ................................................................. 36 2.6. MÔ HÌNH NGƢỜI DÙNG TƢƠNG TỰ NHSM .................................................36 2.6.1. Nhƣợc điểm của độ đo tƣơng tự hiện có..................................................... 36 2.6.2. Công thức của độ đo tƣơng tự NHSM ........................................................ 39 2.7. THUẬT TOÁN DỰ BÁO ......................................................................................40 2.8. KẾT LUẬN CHƢƠNG ..........................................................................................42 CHƢƠNG 3. ỨNG DỤNG CHO BÀI TOÁN DỰ BÁO KẾT QUẢ BÓNG ĐÁ ....... 43 3.1. ĐẶC TẢ YÊU CẦU...............................................................................................43 3.1.1. Yêu cầu thực tế ......................................................................................... 43 3.1.2. Thực tế hóa hệ thống ................................................................................ 43 3.1.3. Mục đích của hệ thống .............................................................................. 43 3.2. PHÂN TÍCH HỆ THỐNG .....................................................................................44 3.2.1. Chức năng ngƣời dùng .............................................................................. 44 3.2.2. Chức năng ngƣời quản trị .......................................................................... 44 3.2.3. Mô hình tổng thể thể hiện mối quan hệ giữa các ca sử dụng ........................ 46 3.2.4. Mô tả giao diện hệ thống ........................................................................... 46 3.3. ĐẶC TẢ CSDL ......................................................................................................49 3.3.1. CSDL....................................................................................................... 49 3.3.2. Mô tả quan hệ CSDL ................................................................................ 51 3.4. THIẾT KẾ HỆ THỐNG .........................................................................................51
7 3.4.1. Modul dự báo ........................................................................................... 51 3.4.2. Modul giải đấu ......................................................................................... 52 3.4.3. Modul mùa giải ........................................................................................ 52 3.4.4. Modul thông tin đội bóng .......................................................................... 52 3.4.5. Modul thuật toán ...................................................................................... 53 3.5. MINH HỌA CÁC CHỨC NĂNG HỆ THỐNG ....................................................53 3.5.1. Chức năng dự báo kết quả bóng đá ............................................................ 53 3.5.2. Các chức năng trong việc quản lý dữ liệu ................................................... 56 3.6. KẾT LUẬN CHƢƠNG ..........................................................................................58 KẾT LUẬN .................................................................................................................. 59 TÀI LIỆU THAM KHẢO .............................................................................................60
8 DANH SÁCH HÌNH VẼ Hình 1.1: Quá trình khám phá tri thức Hình 1.2: Các nhiệm vụ khai phá dữ liệu Hình 1.3: Các kỹ thuật khai phá dữ liệu Hình 2.1: Ma trận đánh giá R của ngƣời dùng lên tài nguyên Hình 2.2: Minh họa một đánh giá cần dự đoán của ngƣời dùng với lọc cộng tác Hình 2.3: Các cách tiếp cận trong lọc cộng tác Hình 2.4: Phƣơng pháp dựa trên nhân khẩu Hình 2.5: Khung đánh giá thuộc tính nhân khẩu Hình 2.6: Mô hình khuyến nghị đa chiều với không gian Ngƣời dùng  Mặt hàng  Thời gian. Hình 2.7: Tƣ vấn cho ngƣời dùng theo ngữ cảnh (thời tiết) Hình 2.8: Mô hình (U  I  C  R) : Dữ liệu ban đầu gồm các ngƣời dùng, các mục để đƣa ra khuyến nghị, các ngữ cảnh liên quan và hàm xếp hạng. Hình 2.9: Ma trận ngƣời dùng tƣơng tự theo bảng 2.3 Hình 3.1: Sơ đồ ca sử dụng của ngƣời dùng Hình 3.2: Sơ đồ ca ngƣời quản trị quản lý thông tin đội bóng Hình 3.3: Sơ đồ ca ngƣời quản trị quản lý giải đấu Hình 3.4: Sơ đồ ca ngƣời quản trị quản lý mùa giải Hình 3.5: Sơ đồ ca ngƣời quản trị quản trị quản lý thuật toán Hình 3.6: Sơ đồ ca tổng thể mối quan hệ giữa các ca sử dụng Hình 3.7: Giao diện tại mục trang chủ (phần trang chủ) Hình 3.8: Giao diện tại menu ảnh nằm ngang (phần trang quản trị) Hình 3.9: CSDL quan hệ giữa các bảng Hình 3.10: Lựa chọn giải đấu cho dự báo Hình 3.11: Lựa chọn mùa giải cần dự báo Hình 3.12: Lựa chọn tập huấn luyện và tập kiểm tra Hình 3.13: Lựa chọn ô kết quả cần dự báo Hình 3.14: Lựa chọn sai số cho kết quả cần dự báo và hiển thị kết quả Hình 3.15: Giao diện phần quản lý thông tin đội bóng Hình 3.16: Giao diện phần quản lý giải đấu
9 Hình 3.17: Giao diện phần quản lý mùa giải chung Hình 3.18: Giao diện phần quản lý mùa giải chi tiết Hình 3.19: Giao diện phần quản lý thuật toán DANH SÁCH BẢNG Bảng 2.1: Ví dụ về đánh giá của ngƣời dùng lên tài nguyên Bảng 2.2: Ma trận đánh giá của ngƣời dùng lên tài nguyên có ngƣời dùng mới Bảng 2.3: Bảng thông tin nhân khẩu của một số ngƣời dùng Bảng 2.4: Ma trận đánh giá ngƣời dùng – tài nguyên Bảng 3.1: Bảng giải đấu Bảng 3.2: Bảng mùa giải Bảng 3.3: Bảng thông tin đội bóng Bảng 3.4: Bảng tham chiếu Bảng 3.5: Bảng thuật toán
10 DANH MỤC CÁC KÝ HIỆU VIẾT TẮT Từ hoặc cụm từ Từ viết tắt Từ Tiếng Anh Khai phá dữ liệu KPDL Data mining Khám phá tri thức KDD Knowledge Discovery in Databases Cơ sở dữ liệu CSDL Database Đa chiều MD Multidimensional Chênh lệch trung bình bình MSD Mean squared difference phƣơng Lọc cộng tác CF Collaborative filtering Mô hình ngƣời dùng tƣơng tự NHSM New heuristic similarity model mới Độ đo PIP PIP Proximity Impact Popylarity Độ đo tƣơng quan Pearson PCC Pearson correlation coefficient Độ tƣơng tự cosin COS Cosine Độ đo tƣơng quan Pearson có CPCC Constrained Pearson correlation ràng buộc coefficient Độ đo cosin hiệu chỉnh ACOS Adjusted Cosine Độ đo PSS PSS Proximity Signsficance Singularity
11 MỞ ĐẦU 1/. ĐẶT VẤN ĐỀ Trong hơn một thập niên trở lại đây, với sự phát triển mạnh của xã hội thì công nghệ viễn thông và thiết bị điện tử cũng phát triển không ngừng. Tuy nhiên, sự bùng nổ này cũng kèm theo mặt trái của nó. Lƣợng thông tin lƣu trữ ngày một lớn đã gây sức ép đáng kể tới phần cứng, buộc con ngƣời tìm đủ mọi cách để tận dụng nguồn tài nguyên dồi dào này. Khai phá dữ liệu xuất hiện nhƣ câu trả lời cho khủng hoảng thừa thông tin. Internet có mặt trên mọi phƣơng diện của cuộc sống. Tuy nhiên, ngƣời sử dụng lại mất nhiều thời gian để tìm kiếm thông tin với nhu cầu bản thân. Một số công cụ tìm kiếm trực tuyến đã đƣợc triển khai hỗ trợ cho ngƣởi dùng nhƣng nhiều khi vẫn chƣa cho hiệu quả nhƣ mong muốn. Để thay đổi điều đó, các phƣơng pháp khai phá thông tin đƣợc hình thành, hỗ trợ không nhỏ cho sự phát triển của hệ thống khuyến nghị. Hệ tƣ vấn sinh ra nhằm mục đích tính toán thông tin trong dữ liệu và để dự đoán sở thích của ngƣời dùng và đƣa ra các khuyến nghị phù hợp với ngƣời dùng. Để thực hiện mục tiêu đó, hệ tƣ vấn vẫn không ngừng đƣợc cải thiện, nâng cao chất lƣợng hiện có. Phƣơng pháp phổ biến, đóng vai trò quan trọng trong hệ tƣ vấn là lọc cộng tác. Xuất hiện trong hệ tƣ vấn, ngữ cảnh mô tả chi tiết hơn về các đối tƣợng trong hệ thống, góp phần tƣ vấn đƣợc chính xác hơn. Hệ tƣ vấn có ứng dụng trong nhiều lĩnh vực thực tế nhƣ hệ thống dự báo phim, âm nhạc, v.v. Bóng đá là một môn thể thao đƣợc nhiều ngƣời quan tâm và triển khai nhiều dịch vụ giải trí. Ngƣời hâm mộ đƣợc khuyến khích đƣa ra kết quả dự báo của mình mỗi khi trận đấu đƣợc xảy ra. Hiểu rõ điều này, chúng tôi xây dựng hệ thống dự báo kết bóng đá dựa trên hệ tƣ vấn. Hệ thống áp dụng phƣơng pháp điển hình của hệ tƣ vấn kết hợp với các đặc trƣng vốn có của một trận đấu bóng đá để dự báo kết quả theo các hƣớng khác nhau. Hệ thống này đƣợc triển khai cho thấy đƣợc hƣớng phát triển của hệ tƣ vấn trong lĩnh vực thể thao. 2/. MỤC ĐÍCH CỦA LUẬN VĂN Việc dự báo kết quả bóng đá cũng sẽ giúp cho ngƣời tham gia dự đoán có đƣợc những ý kiến gợi ý nhất định, tránh đƣợc những sai lầm không đáng có. Trang web dự báo kết quả bóng đá đƣợc xây dựng dựa trên hệ tƣ vấn. Luận văn tiến hành trình bày và phân tích dựa trên thuật toán lọc sử dụng độ đo tƣơng tự để tính toán đƣa ra khuyến nghị. Sau đó dựa trên kết quả phân tích để so sánh và đánh giá khả năng dự báo. 3/. BỐ CỤC CỦA LUẬN VĂN Luận văn gồm 3 chƣơng, có phần mở đầu, phần kết luận, phần mục lục, phần tài liệu tham khảo. Các nội dung cơ bản của luận văn đƣợc trình bày theo cấu trúc nhƣ sau:
12 Chƣơng 1: Tổng quan về khai phá dữ liệu Trong chƣơng này, luận văn sẽ trình bày những vấn đề cơ bản của khai phá dữ liệu nhƣ: định nghĩa, các thành tố cơ bản của một nhiệm vụ khai phá dữ liệu, các nhiệm vụ, các kỹ thuật và ứng dụng của khai phá dữ liệu. Thông qua đó, khai phá dữ liệu tạo đã điều kiện phát triển cho hệ tƣ vấn. Chƣơng 2: Hệ tƣ vấn và các phƣơng pháp lọc Phần đầu tiên giới thiệu là các thông tin liên quan đến hệ tƣ vấn: định nghĩa và phƣơng pháp khuyến nghị lọc cộng tác. Vấn đề thứ hai đƣợc trình bày trong chƣơng này là vấn đề cold - start nảy sinh và phƣơng pháp khắc phục dựa trên tính nhân khẩu. Nội dung phần này cũng trình bày cụ thể vai trò của ngữ cảnh cùng sự xuất hiện của phƣơng pháp tiếp cận đa chiều trong khuyến nghị. Phần tiếp theo trình bày về các độ đo tƣơng tự. Đƣa ra độ đo tƣơng tự mới NHSM và thuật toán dự báo kết quả bóng đá với độ đo mới này. Chƣơng 3: Ứng dụng cho bài toán dự báo kết quả bóng đá Nội dung chƣơng này trình bày phân tích, thiết kế trang web dự báo kết quả bóng đá và xây dựng chƣơng trình ứng dụng.
13 CHƢƠNG 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 1.1. KHAI PHÁ DỮ LIỆU 1.1.1. Định nghĩa khai phá dữ liệu Trong những năm trở lại đây, công nghệ thông tin đã có những bƣớc đột phá, đạt đƣợc nhiều thành tựu to lớn. Sự phát triển của công nghệ điện tử dựa trên định luật Moore đã cho ra những thiết bị có dung lƣợng chứa lớn mà giá thành lại giảm. Với nhu cầu của con ngƣời thì lƣợng thông tin đang đƣợc lƣu trữ là một con số khổng lồ và không ngừng tiếp tục gia tăng nhanh chóng. Trong tác phẩm John Naisbitt năm 1982 thì Megatrends đã đề cập [29]: “Chúng ta đang ngập trong dữ liệu nhƣng lại đói tri thức”. Thực trạng đòi hỏi con ngƣời phải tìm cách khai thác nguồn dữ liệu này, tuy nhiên chỉ có 20% dữ liệu ẩn chứa những tri thức quý giá. Vấn đề đƣợc đặt ra là làm thế nào chúng ta có thể lấy ra đƣợc những thông tin hữu ích đó trong một “núi” dữ liệu nhƣ vậy? Nhƣ một quy luật của tự nhiên, sự khó khăn của bài toán thúc đẩy con ngƣời tìm mọi cách khắc phục. KPDL đã đƣợc xuất hiện nhƣ một giải pháp thần kỳ cho vấn đề nan giải của công nghệ thông tin. Gắn liền với dữ liệu, KPDL đƣợc úng dụng rộng rãi không chỉ trong khoa học mà còn cả kinh tế, xã hội, giáo dục, v.v. Thuật ngữ KPDL xuất hiện vào những năm thập niên 90 nhƣng sự phát triển của KPDL là quá trình phát triển của một lĩnh vực với lịch sử lâu dài. Hiểu một cách đơn giản, KPDL là chiết xuất hoặc khai thác kiến thức từ một lƣợng lớn dữ liệu. Thuật ngữ này dễ làm cho ngƣời ta hiểu nhầm ý nghĩa của nó. Cụ thể hóa là việc thực hiện khai thác vàng từ các loại đá hoặc cát là đƣợc gọi là khai thác vàng chứ không phải khai thác đá hoặc cát. Do đó, KPDL hiểu một cách chính xác hơn là khai thác tri thức từ dữ liệu, mặc dù cái tên gọi đó hơi dài. Nếu tên gọi đƣợc đổi lại là khai thác tri thức, sẽ là ngắn gọn hơn nhƣng nó có thể sẽ không nhấn mạnh vào việc khai thác từ một lƣợng lớn dữ liệu. Tuy nhiên, KPDL là một thuật ngữ sinh động, thể hiện ra việc tìm kiếm một lƣợng tài nguyên nhỏ từ lƣợng lớn dữ liệu. Từ những lý giải trên, định nghĩa về KPDL có thể đƣợc mô tả nhƣ sau [2, 23, 27]: Khai phá dữ liệu là một quá trình khai thác, chiết xuất các tri thức mới có khả năng hữu ích từ một lƣợng lớn dữ liệu. 1.1.2. Khám phá tri thức KPDL là một bƣớc quan trọng trong quá trình KDD [18, 30] nhằm phân tích và giải thích các mẫu dữ liệu trong không gian lớn dữ liệu. KDD là một quá trình bao gồm một chuỗi lặp đi lặp lại 5 bƣớc sau [3, 8, 27, 28]:  Trích chọn dữ liệu là công đoạn lấy dữ liệu liên quan đến nhiệm vụ đƣợc phân tích từ kho dữ liệu lƣu trữ ở trên.  Tiền xử lý dữ liệu bao gồm có các quá trình làm sạch dữ liệu, tích hợp dữ liệu.
14  Chuyển đổi dữ liệu có nhiệm vụ biến đổi dữ liệu hoặc hợp nhất thành các hình thức thích hợp cho khai thác.  Khai phá dữ liệu là quá trình cần thiết, có vai trò quyết định việc tìm ra những tri thức ẩn.  Đánh giá mô hình và trình bày tri thức là quá trình xác định giá trị của các mẫu dữ liệu đại diện cho tri thức nằm bên trong dựa trên một số các độ đo, sau đó sử dụng các kỹ thuật biểu diễn và thể hiện trực quan các tri thức khai phá đƣợc cho ngƣời sử dụng. Hình 1.1: Quá trình khám phá tri thức 1.2. KỸ THUẬT KHAI PHÁ DỮ LIỆU 1.2.1. Các thành tố cơ bản Mỗi ngƣời dùng sẽ có nhũng nhiệm vụ KPDL cần đƣợc thực hiện. Một nhiệm vụ KPDL có thể đƣợc xác định hình thức bằng một truy vấn KPDL, là đầu vào của hệ thống KPDL. Năm thành tố cơ bản để đặc tả một nhiệm vụ KPDL gồm: dữ liệu với nhiệm vụ liên quan, loại tri thức sẽ đạt đƣợc, tri thức nền, các độ đo, mô hình trực quan và biểu diễn tri thức [17, 27]. Dữ liệu với nhiệm vụ liên quan [17, 26] là phần dữ liệu từ các nguồn đƣợc điều tra tƣơng ứng với các thuộc tính hay chiều hƣớng của dữ liệu đƣợc quan tâm. Các dữ liệu cụ thể này bao gồm có tên kho dữ liệu hoặc CSDL, các bảng dữ liệu hoặc các khối dữ liệu, các điều kiện chọn dữ liệu, các thuộc tính hoặc chiều dữ liệu đƣợc quan tâm, các tiêu chí gom nhóm dữ liệu, v.v. Loại tri thức sẽ đạt đƣợc [17, 26] có trọng tâm là phải xác định những tri thức đƣợc khai thác, vì điều này sẽ quyết định chức năng KPDL sẽ đƣợc thực hiện. Các loại tri thức bao gồm đặc trƣng hóa dữ liệu, phân biệt hóa dữ liệu, mô hình phân tích kết hợp hay tƣơng quan, mô hình phân lớp, mô hình dự đoán, mô hình gom cụm, mô hình phân tích phần tử biên, mô hình phân tích tiến hóa, v.v.
15 Tri thức nền [17, 26] là những thông tin về lĩnh vực cụ thể sẽ đƣợc khai phá. Thành tố này hƣớng dẫn quá trình khám phá tri thức bằng cách hỗ trợ KPDL ở nhiều mức khác nhau. Hệ thống phân cấp khái niệm là một hình thức điển hình của tri thức nền. Hệ thống này bao gồm bốn loại chính là phân cấp lƣợc đồ, phân cấp thiết lập nhóm, phân cấp nguồn gốc hoạt động, phân cấp dựa trên quy. Một số hệ thống phân cấp là:  Hệ thống phân phân cấp lƣợc đồ là thứ tự toàn bộ hoặc một phần các thuộc tính trong lƣợc đồ CSDL.  Hệ thống phân cấp thiết lập nhóm tổ chức các giá trị cho thuộc tính thành các nhóm hoặc tập các giá trị. Hệ thống này đƣợc dùng để hoàn thiện hoặc làm phong phú thêm cho hệ thống phân cấp lƣợc đồ, thƣờng đƣợc sử dụng cho một tập nhỏ của thuộc tính đối tƣợng.  Hệ thống phân cấp nguồn gốc hoạt động dựa trên các hoạt động cụ thể. Các hoạt động này có thể bao gồm giải mã các chuỗi thông tin mã hóa, khai thác thông tin từ các đối tƣợng dữ liệu phức tạp, phân cụm dữ liệu.  Hệ thống phân cấp dựa trên quy luật xuất hiện khi toàn bộ hoặc một phần của hệ thống phân cấp khái niệm đƣợc định nghĩa là một tập hợp các quy tắc và đƣợc đánh giá tự động dựa trên CSDL hiện tại và quy tắc định nghĩa. Các độ đo [17, 26] đƣợc sử dụng để giới hạn số lƣợng các mẫu dữ liệu dựa trên cấu trúc của mẫu và số liệu thống kê cơ bản của chúng. Các độ đo thƣờng đi kèm với các ngƣỡng giá trị đƣợc lựa chọn bởi ngƣời khai thác nhằm dẫn đƣờng cho quá trình khai phá hoặc đánh giá các mẫu tìm thấy. Các phép đo khách quan bao gồm các thuộc tính là tính đơn giản, tính chắc chắn, tính hữu dụng, tính mới lạ. Các thuộc tính trên đƣợc sử dụng nhƣ sau:  Tính đơn giản của một mô hình đƣợc dựa trên sƣ đơn giản tổng thể của mô hình đó đối với sự hiểu biết của con ngƣời. Ví dụ, quy định về độ dài là một quy định đơn giản.  Tính chắc chắn đánh giá những giá trị độ tin cậy của một mô hình. Ví dụ, xác suất có điều kiện mua máy tính thì sẽ mua phần mềm cao chứng tỏ nhiều khả năng ngƣời mua máy tính cũng sẽ mua phần mềm.  Tính hữu ích cho thấy khả năng sử dụng của một mô hình. Ví dụ, một xác suất cho trƣớc cho các quy tắc mua phần mềm trƣớc đó có ý nghĩa là với xác suất này thì tất cả ngƣời mua máy tính cũng sẽ mua phần mềm trong các của hàng.  Tính mới lạ chỉ ra các mẫu góp phần thông tin mới cho việc thiết lập mô hình đƣợc gọi là mẫu mới. Việc loại bỏ mô hình dƣ thừa là chiến lƣợc cho việc phát hiện mẫu mới lạ.
16 Mô hình trực quan và biểu diễn tri thức [17, 26] có tác dụng giúp cho khai thác dữ liệu có hiệu quả, bằng cách hiển thị các mẫu đƣợc phát hiện ở nhiều hình thức bao gồm các quy tắc, bảng, báo cáo, biểu đồ, đồ thị, cây, khối và các trình bày trực quan khác. Ngƣời khai thác phải có khả năng xác định các hình thức trình bày cần đƣợc sử dụng để hiển thị các mô hình đƣợc phát hiện. 1.2.2. Các nhiệm vụ khai phá dữ liệu Nhiệm vụ KPDL là rất đa dạng bởi có nhiều mẫu trong một CSDL lớn. Dựa trên các loại mẫu, nhiệm vụ KPDL có thể đƣợc phân chia thành năm loại gồm có tổng hợp, phân lớp, phân cụm, luật kết hợp và phân tích xu hƣớng [16, 27]. Tổng hợp [16] là sự trừu tƣợng hoặc khái quát hóa dữ liệu. Cụ thể là:  Một tập hợp các dữ liệu có liên quan đƣợc tổng hợp và trừu tƣợng hóa dẫn đến một tập nhỏ hơn và đƣa ra cái nhìn tổng quan về dữ liệu với thông tin kèm theo. Ví dụ nhƣ cuộc gọi đƣờng dài của một khách hàng có thể đƣợc tóm tắt trong tổng số phút, tổng số chi phí, tổng số các cuộc gọi, v.v.  Tổng kết có thể lên đến những mức độ trừu tƣợng khác nhau và đƣợc nhìn từ nhiều góc độ khác nhau. Các phút gọi và chi phí điện thoại có thể đƣợc tổng cộng theo thời gian gọi điện thoại trong tuần, tháng, quý, năm. Tƣơng tự nhƣ vậy, các cuộc gọi đƣợc tóm tắt vào trong cuộc gọi trong thành phố, cuộc gọi giữa các thành phố, cuộc gọi châu Á, cuộc gọi châu Âu, v.v. Phân lớp [16] xác định lớp của một đối tƣợng dựa trên thuộc tính của nó. Phân lớp có thể hiểu nhƣ:  Một tập hợp các đối tƣợng đƣợc cho là tập huấn luyện, trong đó mỗi đối tƣợng đƣợc biểu diễn bởi một véc-tơ các thuộc tính của nó. Một chức năng phân lớp đƣợc xây dựng bằng cách phân tích mối quan hệ giữa các thuộc tính của đối tƣợng trong tập huấn luyện. Ví dụ, từ một tập các bệnh nhân đƣợc chẩn đoán, đƣợc dùng nhƣ một tập huấn luyện, một mô hình phân lớp có thể đƣợc xây dựng, trong đó kết luận bệnh của bệnh nhân mắc phải từ dữ liệu chẩn đoán của mình.  Mô hình phân lớp có thể đƣợc sử dụng để chẩn đoán bệnh của bệnh nhân mới dựa trên dựa trên dữ liệu chẩn đoán của bệnh nhân, chẳng hạn nhƣ tuổi, giới tính, khối lƣợng, nhiệt độ, huyết áp, v.v. Luật kết hợp [16] khám phá sự liên kết hoặc kết nối của các đối tƣợng. Liên kết hoặc kết nối nhƣ vậy đƣợc gọi với thuật ngữ là luật kết hợp. Luật kết hợp về căn bản nhƣ sau:  Một luật kết hợp cho thấy mối quan hệ liên kết giữa các đối tƣợng. Sự xuất hiện của một tập hợp các đối tƣợng trong một CSDL có liên quan chặt chẽ đến sự xuất hiện của một tập hợp các đối tƣợng khác.
17  Các luật kết hợp có tác dụng trong tiếp thị, quản lý hàng hóa, quảng cáo, v.v. Phân cụm [16] xác định các cụm hay nhóm cho một tập các đối tƣợng mà nhóm của chúng chƣa rõ. Khi các cụm đƣợc quyết định, các đối tƣợng đƣợc dán nhãn với các cụm tƣơng ứng của chúng và các tính năng phổ biến của các đối tƣợng trong một cụm đƣợc tổng hợp để hình thành các mô tả các lớp. Phân tích xu hƣớng [16] là phân tích các chuỗi dữ liệu đƣợc tích lũy theo thời gian. Phƣơng pháp phân tích xu hƣớng khám phá ra mẫu trong lịch sử phát triển của các đối tƣợng. Một mẫu đƣợc xây dựng để mô phỏng hành vi của các đối tƣợng, có thể sử dụng để dự đoán hành vi trong tƣơng lai. Hình 1.2: Các nhiệm vụ khai phá dữ liệu 1.2.3. Kỹ thuật khai phá dữ liệu Khai phá dữ liệu bao gồm cả thống kê, học máy, định hƣớng CSDL, mạng nơron, tập thô và trực quan [16, 27]. Kỹ thuật thống kê [16, 24] chỉ ra rằng nhiều công cụ thống kê đã đƣợc sử dụng cho khai phá dữ liệu bao gồm cả mạng Bayesian, phân tích hồi quy, phân tích tƣơng quan và phân tích cụm. Mô hình thống kê thƣờng đƣợc xây dựng đƣợc từ một tập hợp các dữ liệu huấn luyện. Một mô hình tối ƣu, dựa vào kỹ thuật thống kê đƣợc xác định trƣớc, đƣợc tìm kiếm trong không gian giả thuyết. Quy định và quy luật sau đó đƣợc rút ra từ mô hình. Các mô hình trên đƣợc mô tả nhƣ sau:  Một mạng Bayes là một đồ thị có hƣớng đại diện cho các mối quan hệ thông thƣờng giữa các biến, đƣợc tính bằng cách sử dụng lý thuyết xác suất Bayes.  Hồi quy là nguồn gốc của một hàm ánh xạ một tập hợp các thuộc tính của các đối tƣợng đến một biến đầu ra.  Phân tích tƣơng quan nghiên cứu sự tƣơng ứng của các biến với nhau.
18  Phân tích cụm tìm thấy các nhóm từ một tập hợp đối tƣợng dựa trên thƣớc đo khoảng cách. Kỹ thuật học máy [16, 24] tìm kiếm một mô hình phù hợp nhất với các dữ liệu thử nghiệm giống nhƣ thống kê. Khác với thống kê ở chỗ, không gian tìm kiếm trong học máy là một không gian nhận thức của nhiều thuộc tính. Bên cạnh đó, hầu hết kỹ thuật học máy sử dụng kỹ thuật chẩn đoán trong tìm kiếm. Kỹ thuật học máy phổ biến nhất đƣợc sử dụng cho khai phá dữ liệu là cây quyết định, học quy nạp khái niệm và phân cụm khái niệm. Các mô hình áp dụng cụ thể là:  Cây quyết định là một phân loại tự do, xác định một lớp các đối tƣợng bằng cách đi theo con đƣờng hình thành từ gốc đến nút lá, lựa chọn các chi nhánh theo các giá trị thuộc tính đối tƣợng. Cây quyết định đƣợc tạo nên từ tập huấn luyện và quy tắc phân loại có thể đƣợc trích ra từ những cây quyết định khác.  Học quy nạp khái niệm xuất phát ngắn gọn, mô tả hợp logic các khái niệm từ một tập hợp các ví dụ.  Phân cụm khái niệm tìm thấy các nhóm hoặc các cụm trong một tập đối tƣợng dựa trên khái niệm gần gũi giữa các đối tƣợng. Kỹ thuật định hƣớng CSDL [16, 24] không tìm kiếm một mô hình tốt nhất nhƣ hai kỹ thuật trƣớc. Thay vào đó, mẫu dữ liệu hoặc CSDL phỏng đoán cụ thể đƣợc sử dụng để khai thác dữ liệu theo cách thủ công. Các thuộc tính định hƣớng quy nạp, kỹ thuật quét CSDL lặp đi lặp lại, và các thuộc tính tập trung, là đại diện của các kỹ thuật định hƣớng CSDL.  Trong định hƣớng thuộc tính quy nạp, dữ liệu cấp thấp tổng hợp vào các khái niệm cao cấp sử dụng hệ thống phân cấp khái niệm.  Kỹ thuật quét CSDL lặp đi lặp lại sử dụng để tìm kiếm các tập hợp thƣờng xuyên trong một CSDL.  Kỹ thuật tập trung liên kết tìm kiếm các mẫu với xác xuất bất thƣờng bằng cách thêm thuộc tính chọn lọc vào mô hình. Kỹ thuật trực quan hóa [16, 24] là kỹ thuật khai thác dựa vào việc phân tích biểu diễn. Dữ liệu đƣợc chuyển đổi thành dấu chấm, đƣờng, khu vực, v.v và hiển thị trong một không gian hai hoặc ba chiều. Ngƣời sử dụng có thể tƣơng tác, khám phá những điểm lý thú bằng cách kiểm tra trực quan. Các kỹ thuật trên có thể kết hợp với nhau để giải quyết các vấn đề phức tạp hoặc cung cấp giải pháp thay thế cách thức đã có.
19 Hình 1.3: Các kỹ thuật khai phá dữ liệu 1.3. ỨNG DỤNG CỦA KHAI PHÁ DỮ LIỆU 1.3.1. Ứng dụng của khai phá dữ liệu KPDL đã đƣợc áp dụng thành công trên nhiều lĩnh vực, từ các lĩnh vực truyền thống nhƣ kinh doanh, khoa học cho đến các lĩnh vực mới nhƣ thể thao. Ứng dụng trong kinh doanh [16]: Nhiều tổ chức hiện nay sử dụng KPDL nhƣ là một vũ khí bí mật để giữ hoặc đạt đƣợc lợi thế cạnh tranh. KPDL đã đƣợc sử dụng trong tiếp thị, phân tích dữ liệu bán lẻ, lựa chọn cổ phiếu, phê duyệt tín dụng, v.v. Cụ thể các ứng dụng đó là:  CSDL của tiếp thị là một trong những ứng dụng kinh doanh thành công và phổ biến của KPDL. Bằng cách khai thác CSDL về lịch sử khách hàng, xu hƣớng đƣợc rút ra và hồ sơ khách hàng đƣợc xây dựng có thể đƣợc sử dụng để tiếp thị hiệu quả hơn.  CSDL bán lẻ có chứa các giao dịch mua sắm của khách hàng. KPDL có thể tìm thấy mô hình mua sắm của khách hàng đã đƣợc sử dụng. Ví dụ, trong chiến dịch bán hàng.  Sử dụng KPDL, nhà đầu tƣ có thể xây dựng mô hình đƣợc sử dụng để dự đoán hiệu suất của các cổ phiếu. Bằng cách tìm kiếm các xu hƣớng và các mẫu cổ phiếu trong dữ liệu, KPDL có thể giúp các nhà đầu tƣ tìm cổ phiếu có hiệu suất tốt.  Ứng dụng cho tín dụng hoặc cho vay đƣợc quyết định dựa trên thông tin của thông tin ngƣời nộp đơn. Một hỗ trợ quyết định duyệt tín dụng hoặc cho vay có thể đƣợc xây dựng từ dữ liệu lịch sử sử dụng các công cụ KPDL.
20 Ứng dụng trong khoa học [16]: KPDL cũng đƣợc sử dụng trong thiên văn học, sinh học phân tử, y học địa chất và nhiều hơn nữa. Ví dụ, hệ thống KPDL có thể phân loại các đối tƣợng trên bầu trời, chẳng hạn nhƣ ngôi sao, thông qua hình ảnh của những vệ tinh. Ứng dụng khác: KPDL cũng đƣợc sử dụng trong nhiều lĩnh vực khác, chẳng hạn nhƣ quản lý chăm sóc sức khỏe, phát hiện gian lân thuế, giám sát hoạt động rửa tiền, thậm chí cả thể thao. 1.3.2. Ứng dụng các phƣơng pháp khai phá dữ liệu trong hệ tƣ vấn Thuật ngữ KPDL để cập đến một loạt các mô hình toán học và các công cụ phần mềm đƣợc sử dụng để tìm kiếm các mẫu trong dữ liệu và sử dụng chúng để xây dựng mô hình. Trong bối cảnh các ứng dụng khuyến nghị, thuật ngữ KPDL đƣợc sử dụng để mô tả bộ các kỹ thuật phân tích đƣợc sử dụng hệ đƣa ra quy tắc khuyến nghị hoặc xây dựng các mô hình khuyến nghị từ các tập dữ liệu lớn. Hệ thống tƣ vấn kết hợp các kỹ thuật KPDL làm cho khuyến nghị của chúng có thể sử dụng những kiến thức học đƣợc từ những hành động và các thuộc tính của ngƣời sử dụng. Các hệ thống này thƣờng dựa trên phát triển hồ sơ của ngƣời dùng kéo dài (dựa trên tính nhân khẩu hoặc dữ liệu lịch sử tiêu thụ), nhất thời (dựa trên các hành động ở hiện tại) hoặc là cả hai. Các thuật toán đƣợc sử dụng bao gồm phân cụm, phân lớp, luật kết hợp, v.v. [22] Phân cụm [22] đƣợc thực hiện bằng cách xác định các nhóm (cụm) ngƣời tiêu dùng có sở thích tƣơng tự. Khi nhóm đƣợc tạo ra, trung bình các ý kiến của ngƣời dùng khác trong nhóm có thể đƣợc sử dụng để đƣa ra dự đoán cho một cá nhân. Dự đoán là một giá trị trung bình dựa trên các cụm, trọng số là mức độ tham gia của từng cụm. Phƣơng pháp phân cụm thƣờng tạo ra các khuyến nghị ít mang tính cá nhân hơn các phƣơng pháp khác. Một số trƣờng hợp, phân cụm có độ chính xác kém hơn các thuật toán lọc cộng tác. Mỗi khi một quá trình phân cụm đƣợc hoàn tất, hiệu quả đạt đƣợc có thể rất tốt nếu nhƣ kích thƣớc của một nhóm đƣợc phân chia thành rất nhỏ. Phân lớp [25] là các mô hình tính toán chung gán với một thể loại đầu vào. Các đầu vào có thể là các véc-tơ tính năng cho các tài nguyên đƣợc phân lớp hoặc dữ liệu về mối quan hệ giữa các mặt hàng. Thể loại là một tên miền phân lớp, cụ thể nhƣ ác tính hoặc lành tính để phân loại cho khối u, cho phép hoặc không cho phép yêu cầu tín dụng, xâm nhập hoặc ủy quyền cho kiểm tra an ninh. Một cách để xây dựng một hệ thống tƣ vấn sử dụng phân lớp là sử dụng thông tin về một sản phẩm mà đầu vào là một khách hàng và thể loại đầu ra sản phẩm đại diện chắc chắn để khuyến nghị cho khách hàng. Phân lớp có thể đƣợc thực hiện bằng cách sử dụng nhiều chiến lƣợc học máy khác nhau bao gồm quy tắc cảm ứng, mạng noron và mạng Bayes. Trong mỗi trƣờng hợp, phân lớp đƣợc đào tạo bởi tập huấn luyện trong đó phân loại đúng đã có sẵn. Sau đó, phân lớp có thể đƣợc áp dụng để phân loại các mặt hàng mới mà chƣa có sẵn phân loại đúng. Ví dụ, mạng Bayes tạo ra một mô hình đào tạo dựa trên một thiết lập với một