Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu các phương pháp phân lớp dữ liệu và ứng dụng trong bài toán dự báo thuê bao rời mạng viễn thông

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

Thêm vào BST

Báo xấu

55
lượt xem 9
download

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

Nội dung chính của luận văn là đưa ra cái nhìn tổng quan về thuê bao rời mạng, khái niệm thuê bao rời mạng, các hình thức rời mạng của thuê bao. Trình bày được lý thuyết khai phá dữ liệu, các ứng dụng khai phá dữ liệu di động, bài toán phân lớp và dự báo. Tìm hiểu các phương pháp phân lớp dữ liệu. 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 các phương pháp phân lớp dữ liệu và ứng dụng trong bài toán dự báo thuê bao rời mạng viễn thông

ĐẠI HỌC THÁI NGUYÊN ĐẠI HỌC TRƢỜNG ĐẠI HỌC CÔNG THÁI NGHỆ NGUYÊN THÔNG TIN VÀ TRUYỀN THÔNG TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG Nguyễn Nhƣ Thế Nguyễn Nhƣ Thế NGHIÊN CỨU CÁC PHƢƠNG PHÁP PHÂN LỚP DỮ LIỆU NGHIÊN CỨU CÁC PHƢƠNG PHÁP PHÂN LỚP DỮ LIỆU VÀ ỨNG DỤNG TRONG BÀI TOÁN DỰ BÁO THUÊ BAO VÀ ỨNG DỤNG TRONG BÀI TOÁNDỰ BÁOTHUÊ BAO RỜI MẠNG VIỄN THÔNG RỜI MẠNG VIỄN THÔNG LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên -2016 Thái Nguyên - 2016
ĐẠI HỌC THÁI NGUYÊN ĐẠI HỌC TRƢỜNG ĐẠI HỌC CÔNG THÁI NGHỆ NGUYÊN THÔNG TIN VÀ TRUYỀN THÔNG TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG Nguyễn Nhƣ Thế Nguyễn Nhƣ Thế CỨU CÁC NGHIÊN CỨU NGHIÊN CÁC PHƢƠNG PHƢƠNG PHÁP PHÁP PHÂN PHÂN LỚP LỚP DỮ DỮ LIỆU LIỆU VÀ VÀỨNG ỨNGDỤNG DỤNGTRONG TRONGBÀI BÀITOÁN DỰ BÁO TOÁNDỰ BÁOTHUÊ BAO THUÊ BAO RỜI MẠNG RỜI MẠNG VIỄN VIỄN THÔNG THÔNG Chuyên ngành: Khoa học máy tính Chuyên ngành: Khoa học máy tính Mã số: 60 48 0101 Mã số: 60 48 0101 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƢỜI HƢỚNG DẪN KHOA HỌC:TS.NGUYỄN LONG GIANG NGƢỜI HƢỚNG DẪN KHOA HỌC: TS NGUYỄN LONG GIANG Thái Nguyên -2016 Thái Nguyên - 2016
i LỜI CAM ĐOAN Tên tôi là: Nguyễn Nhƣ Thế Sinh ngày: 12/12/1989 Học viên lớp cao học: CHK13E - Trƣờng Đại học Công nghệ thông tin và Truyền thông – Đại học Thái Nguyên. Hiện đang công tác tại: Sở Thông tin và Truyền thông tỉnh Phú Thọ Xin cam đoan: Đề tài “Nghiên cứu các phương pháp phân lớp dữ liệu và ứng dụng trong bài toán dự báo thuê bao rời mạng viễn thông” do Thầy giáo TS. Nguyễn Long Giang hƣớng dẫn là công trình nghiên cứu của riêng tôi. Tất cả tài liệu tham khảo đều có nguồn gốc, xuất xứ rõ ràng. Tác giả xin cam đoan tất cả những nội dung trong luận văn đúng nhƣ nội dung trong đề cƣơng và yêu cầu của thầy giáo hƣớng dẫn. Nếu sai tôi hoàn toàn chịu trách nhiệm trƣớc hội đồng khoa học và trƣớc pháp luật. Thái Nguyên, ngày 28 tháng 6 năm 2016 HỌC VIÊN Nguyễn Nhƣ Thế
ii LỜI CẢM ƠN Sau một thời gian nghiên cứu và làm việc nghiêm túc, đƣợc sự động viên, giúp đỡ và hƣớng dẫn tận tình của Thầy giáo hƣớng dẫn TS. Nguyễn Long Giang, luận văn với đề tài “Nghiên cứu các phương pháp phân lớp dữ liệu và ứng dụng trong bài toán dự báo thuê bao rời mạng viễn thông”đã hoàn thành. Tôi xin bày tỏ lòng biết ơn sâu sắc đến: Thầy giáo hƣớng dẫn TS. Nguyễn Long Giang đã tận tình chỉ dẫn, giúp đỡ tôi hoàn thành luận văn này. Tôi xin bày tỏ lòng biết ơn đến các thầy cô trong Trƣờng Đại học Công nghệ thông tin và Truyền thông – Đại học Thái Nguyên đã giúp đỡ tôi trong quá trình học tập cũng nhƣ thực hiện luận văn. Tôi xin cảm ơn Chi nhánh Mobifone Phú Thọ đã nhiệt tình giúp đỡ, cung cấp thông tin trong quá trình nghiên cứu, thực nghiệm chƣơng trình luận văn. Tôi xin chân thành cảm ơn bạn bè, đồng nghiệp và gia đình đã động viên, khích lệ, tạo điều kiện giúp đỡ tôi trong suốt quá trình học tập, thực hiện và hoàn thành luận văn này. Thái Nguyên, ngày 28 tháng 6 năm 2016 HỌC VIÊN Nguyễn Nhƣ Thế
iii MỤC LỤC LỜI CAM ĐOAN ............................................................................................................. i LỜI CẢM ƠN .................................................................................................................. ii DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT .................................................... v DANH MỤC HÌNH ẢNH .............................................................................................. vi DANH MỤC BẢNG BIỂU........................................................................................... vii MỞ ĐẦU .......................................................................................................................... 1 Chương 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU .................................................. 3 1.1. Tổng quan về khai phá dữ liệu ....................................................................... 3 1.1.1. Tại sao cần khai phá dữ liệu .................................................................... 3 1.1.2. Các khái niệm cơ bản .............................................................................. 3 1.1.3. Quy trình khai phá dữ liệu ....................................................................... 5 1.1.4. Các bài toán cơ bản trong khai phá dữ liệu .............................................. 6 1.1.5. Các ứng dụng của khai phá dữ liệu .......................................................... 7 1.1.6. Quy trình xây dựng mô hình khai phá dữ liệu .......................................... 8 1.2.Bài toán phân lớp và dự báo ......................................................................... 10 1.2.1. Giới thiệu bài toán ................................................................................. 10 1.2.2 Các bƣớc giải quyết bài toán ................................................................. 11 Chƣơng 2: CÁC PHƢƠNG PHÁP PHÂN LỚP TRONG KHAI PHÁ DỮ LIỆU .... 12 2.1. Phân lớp bằng phƣơng pháp quy nạp cây quyết định ................................... 12 2.2. Phân lớp bằng phƣơng pháp Bayesian ......................................................... 15 2.3. Support Vector Machine (SVM) ................................................................. 16 2.3.1 Phân tách tuyến tính với lề cực đại ......................................................... 16 2.3.1.1. Tìm kiếm siêu phẳng với lề cực đại .................................................... 21 2.3.1.2. Hàm phân loại tuyến tính với lề mềm cực đại ..................................... 22 2.3.1.3. Lý thuyết tối ƣu Lagrangian ............................................................... 23 2.3.1.4. Tìm kiếm siêu phẳng với lề cực đại .................................................... 25 2.3.2. Phƣơng pháp hàm nhân (kernel methods) ................................................... 28 2.3.2.1 Chiều VC về khả năng phân tách của hàm tuyến tính .......................... 29 2.3.2.2 Hàm nhân và SVM phi tuyến (Kernel function and nonlinear SVMs) . 30
iv 2.4. Phân lớp bằng mạng lan truyền ngƣợc (mạng Nơron) .................................. 33 Chƣơng 3: ỨNG DỤNG BÀI TOÁN PHÂN LỚP DỮ LIỆU THUÊ BAO RỜI MẠNG VIỄN THÔNG ................................................................................................. 37 3.1. Bài toán phân lớp dữ liệu thuê bao rời mạng................................................ 37 3.1.1. Phát biểu bài toán .................................................................................. 37 3.1.2. Khái niệm thuê bao rời mạng “churn” ................................................... 38 3.1.3. Thu thập, chuẩn hóa dữ liệu .................................................................. 39 3.1.4. Lựa chọn thuộc tính............................................................................... 42 3.2. Lựa chọn phƣơng pháp, công cụ .................................................................. 45 3.2.1. Ngôn ngữ R ........................................................................................... 45 3.2.2. Phƣơng pháp phân lớp........................................................................... 47 3.2.3. Đánh giá hiệu năng................................................................................ 48 3.3. Thực nghiệm phân lớp trên ngôn ngữ R....................................................... 50 3.3.1. Phân lớp dữ liệu sử dụng cây quyết định C4.5 ....................................... 51 3.3.2. Phân lớp dữ liệu sử dụng phƣơng pháp Naive Bayes ............................. 53 3.3.3. Phân lớp dữ liệu bằng Support Vector Machines .................................. 55 3.3. Đánh giá kết quả.......................................................................................... 56 KẾT LUẬN .................................................................................................................... 58 TÀI LIỆU THAM KHẢO ............................................................................................. 60
v DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT TT Thuật ngữ Định nghĩa 1. KPDL Khai phá dữ liệu 2. KDD Knowledge Discovery and Data Mining 3. NB Naïve Bayes 4. SVM Support vector machine 5. NN Neural Networks
vi DANH MỤC HÌNH ẢNH Hình 1.1- Các bƣớc trong khai phá dữ liệu ..............................................................6 Hình 1.2 - Quy trình xây dựng mô hình khai phá dữ liệu ..........................................9 Hình 2.1 - Ví dụ về cây quyết định ......................................................................... 12 Hình 2.2 - Về mặt trực quan thì hàm tuyến tính siêu phẳng với lề lớn nhất trông có vẻ hợp lý ................................................................................................................ 19 Hình 2.3 - Ví dụ về bài toán phân loại trong không gian hai chiều .......................... 19 Hình 2.4 - Ba điểm trong mặt phẳng bị chia tách bởi một đƣờng thẳng có hƣớng. ..28 Hình 2.5 - Mạng nơ-ron truyền thẳng nhiều lớp ...................................................... 34 Hình 3.1 - Mô hình quan hệ các bảng dữ liệu.......................................................... 40 Hình 3.2 - Các giai đoạn của mô hình dự đoán thuê bao rời mạng .......................... 42 Hình 3.3 - Lựa chọn thuộc tính trong phân lớp dữ liệu ............................................ 44 Hình 3.4 - Số lƣợng thuộc tính đƣợc thu thập ......................................................... 44 Hình 3.5 – Giao diện làm việc trên ngôn ngữ R ...................................................... 47 Hình 3.6 – Quy trình thực nghiệm bài toán phân lớp dữ liệu thuê bao rời mạng......50 Hình 3.7- mô hình phân lớp cây quyết định ........................................................... 52 Hình 3.8 - Chi tiết nút nhánh thứ 15 trong phân lớp cây quyết định ........................ 52 Hình 3.9 - Kết quả phân lớp dữ liệu bằng SVM ...................................................... 55 Hình 3.10 – Hiệu năng các thuật toán với lớp thuê bao rời mạng ............................ 57
vii DANH MỤC BẢNG BIỂU Bảng 1 - Ma trận nhầm lẫn ..................................................................................... 49 Bảng 2 – Kết quả mô hình phân lớp sử dụng C 4.5 ................................................. 53 Bảng 3 – Độ đo hiệu năng thuật toán Cây quyết định ............................................. 53 Bảng 4 – Kết quả mô hình phân lớp sử dụng NB .................................................... 54 Bảng 5. – Độ đo hiệu năng thuật toán NB ............................................................... 54 Bảng 6 – Kết quả mô hình phân lớp sử dụng SVM ................................................ 55 Bảng 7. – Độ đo hiệu năng thuật toán SVM ............................................................ 56 Bảng 8. – Tổng hợp đánh giá hiệu năng các phƣơng pháp phân lớp ........................ 56
1 MỞ ĐẦU Sự bùng nổ và phát triển của ngành công nghệ thông tin đã làm lƣợng dữ liệu đƣợc thu thập và lƣu trữ ở các hệ thống thông tin tăng lên một cách nhanh chóng. Trƣớc tình hình đó, việc khai thác và chọn lọc những dữ liệu có ích, tiền ẩn từ lƣợng dữ liệu khổng lồ này là rất cần thiết. Các tri thức trích lọc từ dữ liệu sẽ giúp các cơ quan, tổ chức đƣa ra những dự báo và điều hành hiệu quả. Khai phá dữ liệu và khám phá tri thức (Data mining and Knowledge discovery) là một lĩnh vực quan trọng của ngành Công nghệ thông tin với mục tiêu là tìm kiếm các tri thức có ích, cần thiết, tiềm ẩn và chƣa đƣợc biết trƣớc trong cơ sở dữ liệu lớn. Đây là lĩnh vực đã và đang thu hút đông đảo các nhà khoa học trên thế giới và trong nƣớc tham gia nghiên cứu. Phân lớp (classification) là một trong những bài toán cơ bản trong khai phá dữ liệu với mục tiêu là phân loại các đối tƣợng vào các lớp cho trƣớc. Theo tiếp cận học máy, phân lớp là phƣơng pháp học có giám sát với hai giai đoạn: Giai đoạn 1 là xây dựng mô hình phân lớp dựa trên tập dữ liệu huấn luyện có đầu vào và đầu ra mong muốn (gọi là nhãn lớp); Giai đoạn 2 là sử dụng mô hình phân lớp để phân loại các tập dữ liệu chƣa có nhãn lớp vào các lớp đã cho và có ứng dụng trong nhiều bài toán dự báo trong thực tế. Phân lớp đƣợc sử dụng rộng rãi trong các bài toán thực tiễn nhƣ trong y tế, ngân hàng, viễn thông, kinh tế, tài chính... Ngày nay, cùng với sự phát triển mạnh mẽ của thị trƣờng viễn thông là sự ra đời của nhiều nhà cung cấp và kinh doanh dịch vụ mạng viễn thông. Thị trƣờng viễn thông đang đi vào giai đoạn bão hòa, khách hàng có nhiều sự lựa chọn, dẫn đến họ có thể thay đổi sử dụng dịch vụ bất cứ khi nào, kết quả là số
2 lƣợng khách hàng rời mạng tăng lên một cách nhanh chóng. Hậu quả ảnh hƣởng không nhỏ tới kinh tế cũng nhƣ trong quản lý của doanh nghiệp kinh doanh dịch vụ viễn thông. Vì vậy, các nhà kinh doanh dịch vụ mạng cần có các giải pháp dữ chân khách hàng hơn là tìm kiếm khách hàng mới. Việc dự báo khách hàng có thể rời bỏ mạng trong tƣơng lai là rất cần thiết, nhằm mục đích hỗ trợ các nhà kinh doanh dịch vụ mạng có quyết sách kịp thời trong công việc giữ chân khách hàng.
3 Chương 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 1.1. Tổng quan về khai phá dữ liệu 1.1.1. Tại sao cần khai phá dữ liệu Khoảng hơn một thập kỷ trở lại đây, lƣợng thông tin đƣợc lƣu trữ trên các thiết bị điện tử (đĩa cứng, CD-ROM, băng từ, .v.v.) không ngừng tăng lên. Sự tích lũy dữ liệu này xảy ra với một tốc độ bùng nổ. Ngƣời ta ƣớc đoán rằng lƣợng thông tin trên toàn cầu tăng gấp đôi sau khoảng hai năm và theo đó số lƣợng cũng nhƣ kích cỡ của các cơ sở dữ liệu (CSDL) cũng tăng lên một cách nhanh chóng. Nói một cách hình ảnh là chúng ta đang “ngập” trong dữ liệu nhƣng lại “đói” tri thức. Câu hỏi đặt ra là liệu chúng ta có thể khai thác đƣợc gì từ những “núi” dữ liệu tƣởng chừng nhƣ “bỏ đi” ấy không? [3] “Necessity is the mother of invention” - Data Mining ra đời nhƣ một hƣớng giải quyết hữu hiệu cho câu hỏi vừa đặt ra ở trên. Khá nhiều định nghĩa về Data Mining, tuy nhiên có thể tạm hiểu rằng Data Mining nhƣ là một công nghệ tri thức giúp khai thác những thông tin hữu ích từ những kho dữ liệu đƣợc tích trữ trong suốt quá trình hoạt động của một công ty, tổ chức nào đó. 1.1.2. Các khái niệm cơ bản Khai phá dữ liệu (datamining) [4] đƣợc định nghĩa nhƣ là một quá trình chắt lọc hay khai phá tri thức từ một lƣợng lớn dữ liệu. Một ví dụ hay đƣợc sử dụng là là việc khai thác vàng từ đá và cát, Dataming đƣợc ví nhƣ công việc "Đãi cát tìm vàng" trong một tập hợp lớn các dữ liệu cho trƣớc. Thuật ngữ Dataming ám chỉ việc tìm kiếm một tập hợp nhỏ có giá trị từ một số lƣợng lớn các dữ liệu thô. Có nhiều thuật ngữ hiện đƣợc dùng cũng có nghĩa tƣơng tự với từ Datamining nhƣ Knowledge Mining (khai phá tri thức), knowledge
4 extraction (chắt lọc tri thức), data/patern analysis(phân tích dữ liệu/mẫu), data archaeoloogy (khảo cổ dữ liệu), datadredging(nạo vét dữ liệu),... Định nghĩa: Khai phá dữ liệu là một tập hợp các kỹ thuật được sử dụng để tự động khai thác và tìm ra các mối quan hệ lẫn nhau của dữ liệu trong một tập hợp dữ liệu khổng lồ và phức tạp, đồng thời cũng tìm ra các mẫu tiềm ẩn trong tập dữ liệu đó. Khai phá dữ liệu nhấn mạnh hai khía cạnh chính đó là khả năng trích xuất thông tin có ích tự động (Automated) và bán tự động (Semi - Automated) mang tính dự đoán (Predictive). Khai phá dữ liệu là một lĩnh vực liên ngành, liên quan chặt chẽ đến các lĩnh vực sau: Statistics (Thống kê): là một số đo cho một thuộc tính nào đó của một tập mẫu. Mỗi giá trị thống kê đƣợc tính bằng một hàm nào đó và thông tin của môt thống kê mang tính đại diện cho thông tin của tập mẫu mang lại. Machine Learning (Máy học): là một phƣơng pháp để tạo ra các chƣơng trình máy tính bằng việc phân tích các tập dữ liệu. Máy học có liên quan lớn đến thống kê, vì cả hai lĩnh vực đều nghiên cứu việc phân tích dữ liệu, nhƣng khác với thống kê, học máy tập trung vào sự phức tạp của các giải thuật trong việc thực thi tính toán. Databases technology (Công nghệ cơ sở dữ liệu): kho thông tin về một chủ đề, đƣợc tổ chức hợp lý để dễ dàng quản lý và truy tìm. Visualization (Sự trực quan): Biểu diễn giúp dữ liệu dễ hiểu, dễ sử dụng, thuận tiện cho việc tạo các báo cáo, tìm ra các tri thức phục vụ việc ra quyết định và dự đoán của nhà quản lý.
5 1.1.3. Quy trình khai phá dữ liệu Khai phá dữ liệu là một bƣớc trong bảy bƣớc của quá trình KDD (Knowleadge Discovery in Database) và KDD đƣợc xem nhƣ 7 quá trình khác nhau theo thứ tự sau [1]: 1. Làm sạch dữ liệu (data cleaning & preprocessing): Loại bỏ nhiễu và các dữ liệu không cần thiết. 2. Tích hợp dữ liệu: (data integration): quá trình hợp nhất dữ liệu thành những kho dữ liệu (data warehouses & data marts) sau khi đã làm sạch và tiền xử lý (data cleaning & preprocessing). 3. Trích chọn dữ liệu (data selection): trích chọn dữ liệu từ những kho dữ liệu và sau đó chuyển đổi về dạng thích hợp cho quá trình khai thác tri thức. Quá trình này bao gồm cả việc xử lý với dữ liệu nhiễu (noisy data), dữ liệu không đầy đủ (incomplete data), .v.v. 4. Chuyển đổi dữ liệu: Các dữ liệu đƣợc chuyển đổi sang các dạng phù hợp cho quá trình xử lý. 5. Khai phá dữ liệu (data mining): Là một trong các bƣớc quan trọng nhất, trong đó sử dụng những phƣơng pháp thông minh để chắt lọc ra những mẫu dữ liệu. 6. Ƣớc lƣợng mẫu (knowledge evaluation): Quá trình đánh giá các kết quả tìm đƣợc thông qua các độ đo nào đó. 7. Biểu diễn tri thức (knowledge presentation): Quá trình này sử dụng các kỹ thuật để biểu diễn và thể hiện trực quan cho ngƣời dùng.
6 Hình 1.1- Các bước trong khai phá dữ liệu [1] 1.1.4. Các bài toán cơ bản trong khai phá dữ liệu Mô tả khái niệm (concept description): là bài toán tìm đặc trƣng và tính chất của khái niệm. Bài toán thiên về mô tả, tổng hợp và tóm tắt khái niệm. Ví dụ: tóm tắt văn bản. Luật kết hợp (association rules): là dạng luật biểu diễn tri thức ở dạng khá đơn giản. Ví dụ: “60 % nam giới vào siêu thị nếu mua bia thì có tới 80% trong số họ sẽ mua thêm thịt bò khô”. Luật kết hợp đƣợc ứng dụng nhiều trong lĩnh vực kính doanh, y học, tin-sinh, tài chính & thị trƣờng chứng khoán, .v.v. Phân lớp và dự đoán (classification & prediction): xếp một đối tƣợng vào một trong những lớp đã biết trƣớc. Ví dụ: phân lớp vùng địa lý theo dữ liệu thời tiết. Hƣớng tiếp cận này thƣờng sử dụng một số kỹ thuật của machine
7 learning nhƣ cây quyết định (decision tree), mạng nơ ron nhân tạo (neural network), .v.v. Ngƣời ta còn gọi phân lớp là học có giám sát (học có thầy). Phân cụm (clustering): xếp các đối tƣợng theo từng cụm (số lƣợng cũng nhƣ tên) của cụm chƣa đƣợc biết trƣớc. Ngƣời ta còn gọi phân cụm là học không giám sát (học không thầy). Hồi quy (regression ): là bài toán điển hình trong phân tích thống kê và dự báo. Trong khai phá dữ liệu, bài toán hồi quy đƣợc quy về việc học một hàm ánh xạ dữ liệu nhằm xác định một giá trị thực của một biến theo biến số khác. Phân tích hồi quy sẽ xác định đƣợc định lƣợng quan hệ giữa các biến, và quảng bá giá trị một biến phụ thuộc vào giá trị của những biến khác. Phƣơng pháp hồi quy khác với phân lớp dự liệu là hồi quy dùng để dự đoán những giá trị liên lục, còn phân lớp dữ liệu là dự đoán các giá trị rời rạc. Khai phá chuỗi (sequential/temporal patterns): tƣơng tự nhƣ khai phá luật kết hợp nhƣng có thêm tính thứ tự và tính thời gian. Hƣớng tiếp cận này đƣợc ứng dụng nhiều trong lĩnh vực tài chính và thị trƣờng chứng khoán vì nó có tính dự báo cao. Ngoài ra còn có một số bài toán khai phá dữ liệu thống kê khác. 1.1.5. Các ứng dụng của khai phá dữ liệu Phát hiện tri thức và khai phá dữ liệu 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, 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 ... Ngân hàng dữ liệu (Data Warehousing) và các công cụ phân tích
8 trực tuyến (OLAP- On Line Analytical Processing) 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ế,[3] ví dụ 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, ...  Thống kê, phân tích dữ liệu và hỗ trợ ra quyết định.  Đ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, ...)  Sản xuất và chế biến: Quy trình, phƣơng pháp chế biến và xử lý sự 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ụ, dự báo thuê bao rời mạng ... 1.1.6. Quy trình xây dựng mô hình khai phá dữ liệu Việc thực hiện một DMM với đầy đủ 4 bƣớc công việc chính của quá trình khai phá dữ liệu là:
9 Bƣớc 1: Chuẩn bị dữ liệu (Data Preparation); Trong bƣớc này chúng ta thực hiện các công việc tiền xử lý dữ liệu theo yêu cầu của mô hình nhƣ trích chọn thuộc tính, rời rạc hóa dữ liệu và cuối cùng là chia dữ liệu nguồn (Data Source) thành 2 tập dữ liệu dùng để huấn luyện mô hình (Training Data) và kiểm tra mô hình (Testing data). Bƣớc 2: Xây dựng mô hình (Data Modeling); ta sử dụng Training Data vừa tạo ra để xây dựng mô hình. Bƣớc 3: Đánh giá mô hình (Validation); Sau khi sử dụng Training Data để xây dựng mô hình, bây giờ ta sử dụng Testing Data để kiểm tra xem mô hình có đủ tốt để sử dụng hay không? ( Nếu chƣa đủ tốt thì phải sử dụng Training Data khác để huấn luyện lại). Có 3 kỹ thuật chính để kiểm tra mô hình đó là sử dụng Accuracy Chart ( Lift Chart), Classification Matrix và ProfitChart. Bƣớc 4: Sử dụng mô hình để dự đoán dự liệu trong tƣơng lai (Model Usage); Sau khi mô hình đƣợc kiểm tra (Testing) nếu độ chính xác đáp ứng yêu cầu thì có thể sử dụng model đã xây dựng vào dự đoán các dữ liệu chƣa biết. Hình 1.2 - Quy trình xây dựng mô hình khai phá dữ liệu
10 1.2.Bài toán phân lớp và dự báo 1.2.1. Giới thiệu bài toán Phân lớp: là quá trình xây dựng một mô hình để mô tả dữ liệu đƣợc phân chia nhƣ thế nào, nói cách khác, phân lớp là quá trình xây dựng một mô hình bằng các gán các đối tƣợng dữ liệu (thuộc tính) vào các lớp đã xác định. Tiến trình phân lớp dựa trên 4 thành phần cơ bản: - Lớp (class) - Dự đoán (predictors) - Tập dữ liệu được đào tạo (Training dataset) - Tập dữ liệu kiểm thử (Testing dataset) Đặc trƣng của tiến trình phân lớp gồm những điểm sau: Input: tập dữ liệu đào tạo chứa những đối tƣợng với thuộc tính của nó,với một số thuộc tính đã đƣợc gán nhãn; Output: mô hình (classifier) đƣợc gán bởi những nhãn cụ thể cho mỗi đối tƣợng phân lớp các đối tƣợng từng các thƣ mục), dựa trên những thuộc tính khác; Dự báo: là một quá trình gồm hai bƣớc, nó gần giống với quá trình phân lớp. Tuy nhiên để dự báo, chúng ta bỏ qua khái niệm nhãn phân lớp bởi vì các giá trị đƣợc dự báo là liên tục (đƣợc sắp xếp) hơn là các giá trị phân loại. Ví dụ thay vì phân loại xem một khoản vay có là an toàn hay rủi do thì chúng ta sẽ dự đoán xem tổng số tiền cho vay của một khoản vay là bao nhiêu thì khoản vay đó là an toàn. Có thể xem xét việc dự báo cũng là một hàm y = f(X), trong đó X là dữ liệu đầu vào, và đầu ra là một giá trị y liên tục hoặc sắp xếp đƣợc. Việc dự báo và phân lớp có một vài điểm khác nhau khi sử dụng các phƣơng pháp xây
11 dựng mô hình. Giống với phân lớp, tập dữ liệu huấn luyện sử dụng để xây dựng mô hình dự báo không đƣợc dùng để đánh giá tính chính xác. Tính chính xác của mô hình dự báo đƣợc đánh giá dựa trên việc tính độ lệch giá các giá trị dự báo với các giá trị thực sự nhận đƣợc của mỗi bộ kiểm tra X. 1.2.2 Các bƣớc giải quyết bài toán Các bƣớc giải quyết bài toán gồm: Bƣớc 1:Xây dựng mô hình từ tập huấn luyện. - Mỗi bộ/mẫu dữ liệu đƣợc phân vào một lớp đƣợc xác định trƣớc. - Lớp của một bộ/mẫu dữ liệu đƣợc xác định bởi thuộc tính gán nhãn lớp. - Tập các bộ/mẫu dữ liệu huấn luyện - tập huấn luyện - đƣợc dùng để xây dựng mô hình. - Mô hình đƣợc biểu diễn bởi các luật phân lớp, các cây quyết định hoặc các công thức toán học. Bƣớc 2: Sử dụng mô hình - kiểm tra tính đúng đắn của mô hình và dùng nó để phân lớp dữ liệu mới - Phân lớp cho những đối tƣợng mới hoặc chƣa đƣợc phân lớp. - Đánh giá độ chính xác của mô hình: + Lớp biết trƣớc của một mẫu/bộ dữ liệu đem kiểm tra đƣợc so sánh với kết quả thu đƣợc từ mô hình + Tỉ lệ chính xác = phần trăm các mẫu/bộ dữ liệu đƣợc phân lớp đúng bởi mô hình trong số các lần kiểm tra