Đề tài Khai phá dữ liệu và thuật toán khai phá luật kết hợp song song

Với sự bùng nổ và phát triển của công nghệ thông tin đã mang lại nhiều hiệu quả đối với khoa học cũng như các hoạt động thực tế, trong đó khai phá dữ liệu là một lĩnh vực mang lại hiệu quả thiết thực cho con người. Khai phá dữ liệu đã giúp người sử dụng thu được những tri thức hữu ích từ những cơ sở dữ liệu hoặc các kho dữ liệu khổng lồ khác. Cơ sở dữ liệu trong các đơn vị, tổ chức kinh doanh, quản lý khoa học chứa đựng nhiều thông tin tiềm ẩn, phong phú và đa dạng, đòi hỏi phải có những phương pháp nhanh, phù hợp, chính xác, hiệu quả để lấy được những thông tin bổ ích. Những “tri thức” chiết suất từ nguồn cơ sở dữ liệu trên sẽ là nguồn thông tin hỗ trợ cho lãnh đạo trong việc lên kế hoạch hoạt động hoặc trong việc ra quyết định sản xuất kinh doanh. Tiến hành công việc như vậy chính là thực hiện quá trình phát hiện tri thức trong cơ sở dữ liệu (Knowledge Discovery in Database) mà trong đó kỹ thuật khai phá dữ liệu (Data Mining) cho phép phát hiện những tri thức tiềm ẩn. Để lấy được thông tin mang tính tri thức trong khối dữ liệu khổng lồ, cần thiết phải phát triển các kỹ thuật có khả năng tích hợp các dữ liệu từ các hệ thống giao dịch khác nhau, chuyển chúng thành một tập hợp các cơ sở dữ liệu ổn định có chất lượng. Các kỹ thuật như vậy được gọi là kỹ thuật tạo kho dữ liệu và môi trường các dữ liệu nhận được khi áp dụng các kỹ thuật tạo kho dữ liệu nói trên được gọi là kho dữ liệu (Data Warehouse) [19, 24].

pdf86 trang | Chia sẻ: lvbuiluyen | Lượt xem: 3529 | Lượt tải: 2download
Bạn đang xem trước 20 trang tài liệu Đề tài Khai phá dữ liệu và thuật toán khai phá luật kết hợp song song, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN ----------------------------- LÊ THỊ VIỆT HOA KHAI PHÁ DỮ LIỆU VÀ THUẬT TOÁN KHAI PHÁ LUẬT KẾT HỢP SONG SONG Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số : 60.48.01 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Hướng dẫn khoa học: PGS.TS ĐOÀN VĂN BAN THÁI NGUYÊN 2008 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên LỜI CẢM ƠN Xin chân thành cảm ơn Thầy giáo PGS.TS Đoàn Văn Ban đã tận tình chỉ dạy và hướng dẫn tôi trong suốt thời gian học tập và làm luận văn. Tôi cũng xin xin lời biết ơn chân thành đến quý Thầy giáo, cô giáo Viện Công nghệ Thông đã tận tình giảng dạy, trang bị cho tôi những kiến thức quý báu trong suốt quá trình học tập tại Khoa. Xin cảm ơn tất cả các anh chị em học viên Cao học khóa 5, cám ơn cán bộ công chức, giảng viên – Khoa Công nghệ Thông tin - Đại học Thái Nguyên đã tạo điều kiện giúp đỡ tôi trong suốt quá trình học tập và làm luận văn. Cuối cùng xin cảm ơn gia đình, bạn bè, đồng nghiệp đã giúp đỡ tôi trong suốt thời gian học tập và hoàn thành luận văn này. Thái Nguyên, tháng 9 năm 2008 Tác giả Lê Thị Việt Hoa Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên LỜI CAM ĐOAN Tôi xin cam đoan đề tài khoa học “Khai phá dữ liệu và thuật toán khai phá luật kết hợp song song” này là công trình nghiên cứu của bản thân tôi. Các số liệu và kết quả nghiên cứu nêu trong luận văn này là trung thực, được các tác giả cho phép sử dụng và các tài liệu tham khảo như đã trình bày trong luận văn. Tôi xin chịu trách nhiệm về luận văn của mình. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên MỤC LỤC Trang phụ bìa Trang Lời cám ơn Lời cam đoan Mục lục Danh mục các kí hiệu, các chữ viết tắt Danh mục các hình vẽ Mở đầu 1 Chương 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 3 1.1. Khái niệm 3 1.2. Kiến trúc của một hệ thống khai phá dữ liệu 3 1.3. Các giai đoạn của quá trình khai phá dữ liệu 4 1.4. Một số kỹ thuật khai phá dữ liệu 6 1.5. Các cơ sở dữ liệu phục vụ cho khai phá dữ liệu 10 1.6. Các phương pháp chính trong khai phá dữ liệu 11 1.7. Các ứng dụng của khai phá dữ liệu 13 1.8. Khai phá dữ liệu và các lĩnh vực liên quan 14 1.9. Các thách thức trong phát hiện tri thức và khai phá dữ liệu 15 1.10. Kết luận chương 1 16 Chương 2: KHAI PHÁ LUẬT KẾT HỢP TRONG CƠ SỞ DỮ LIỆU 17 2.1. Mở đầu 17 2.2 Luật kết hợp 18 2.2.1 Các khái niệm cơ bản 18 2.2.2. Khai phá luật kết hợp 21 2.2.3. Cách tiếp cận khai phá luật kết hợp 22 2.3 Luật kết hợp cơ sở 24 2.3.1 Phát hiện các tập mục phổ biến 24 2.3.2 Sinh luật kết hợp 30 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2.4. Khai phá luật kết hợp với một số khái niệm mở rộng 32 2.4.1. Giới thiệu 32 2.4.2. Khai phá luật kết hợp trọng số 32 2.4.3 Khai phá luật kết hợp tổng quát 43 2.5. Kết luận chương 2 49 Chương 3: MỘT SỐ PHƯƠNG PHÁP KHAI PHÁ LUẬT KẾT HỢP SONG SONG VÀ PHÂN TÍCH ĐÁNH GIÁ CÁC THUẬT TOÁN 50 3.1. Nguyên lý thiết kế thuật toán song song 50 3.2. Hư ớng tiếp cận chính trong thiết kế thuật toán khai phá luật kết hợp song song 51 3.2.1. Mô hình song song dữ liệu 51 3.2.2. Mô hình song song thao tác 51 3.3. Một số thuật toán khai phá luật kết hợp song song 52 3.3.1 Thuật toán Count Distribution (CD) 52 3.3.2. Thuật toán Data Distribution (DD) 54 3.3.3. Thuật toán Candidate Distribution 58 3.3.4. Thuật toán song song Fp-Growth 60 3.3.5 Thuật toán song song Eclat 65 3.4. Phân tích, đánh giá và so sánh việc thực hiện thuật toán 71 3.4.1. Phân tích và đánh giá thuật toán song song 71 3.4.2. So sánh việc thực hiện các thuật toán 73 3.5. Kết luận chương 3 74 Kết luận 75 Tài liệu tham khảo 77 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên DANH MỤC CÁC KÝ HIỆU VIẾT TẮT Ký hiệu Diễn giải Ck Tập các k-itemset ứng viên kC Tập các k-itemset ứng viên mà TID của giao dịch sinh ra liên kết với tập mục ứng viên Conf Độ tin cậy (Confidence) CFPT FP-Tree điều kiện cơ sở (Fisst conditional FP-Tree) D Cơ sở dữ liệu giao dịch Di Phần thứ i của cơ sở dữ liệu D Item Mục Itemset Tập mục I Tập các mục KDD Phát hiện tri thức trong cơ sở dữ liệu (Knowledge Discovery in Database) CSDL Cơ sở dữ liệu (Database) k-itemset Tập mục gồm k mục Lk Tập các k-itemset phổ biến MPI Truyền thông điệp minconf Ngưỡng tin cậy tối thiểu minsup Ngưỡng hỗ trợ tối thiểu OLAP Phân tích trực tuyến OLTP Xử lý giao dịch trực tuyến SC Số đếm hỗ trợ (support count) sup Độ hỗ trợ (support) T Giao dịch (transaction) Tid Định danh của giao dịch Tid-List Danh sách các định danh của giao dịch X ⇒Y Luật kết hợp (với X là tiền đề, Y là hệ quả) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên DANH MỤC HÌNH VẼ VÀ BẢNG Trang Hình 1.1. Khám phá tri thức trong cơ sở dữ liệu điển hình 3 Hình 1.2. Các bước của quy trình khai phá dữ liệu 5 Hình 1.3: Cây quyết định 7 Hình 1.4: Mẫu kết quả của nhiệm vụ phân cụm dữ liệu 8 Hình 1.5: Mẫu kết quả của nhiệm vụ hồi quy 8 Hình 1.6: Một số lĩnh vực liên quan đến khai phá dữ liệu 14 Hình 2.1. Sơ đồ tổng quan của thuật toán khai phá tập mục phổ biến 24 Hình 2.2: Ví dụ thuật toán Apriori 28 Bảng 2.1.a. Thông tin của một cửa hàng bán lẻ 33 Bảng 2.1.b. Tập giao dịch D của cửa hàng 33 Hình 3.1. Mô hình song song dữ liệu 51 Hình 3.2. Mô hình song song thao tác 52 Hình 3.3. Sơ đồ thuật toán Count Distribution 52 Hình 3.4. Phát hi ện các tập mục phổ biến bởi thuật toán song song CD 54 Hình 3.5. Sơ đồ mô tả thuật toán Data Distribution 55 Hình 3.6: Sơ đồ luồng thuật toán Data Distribution 56 Hình 3.7: Phát hi ện các tập mục phổ biến bởi thuật toán song song DD 57 Hình 3.8: Các phân hoạch CSDL và các FP-Tree cục bộ ban đầu 61 Bảng 3.1: Các mẫu điều kiện cơ sở và các FP-Tree điều kiện cơ sở 62 Hình 3.9: Quá trình sinh tập phổ biến bởi 2 bộ xử lý P1 và P2 63 Hình 3.10: Quá trình chuyển đổi CSDL theo chiều dọc 70 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 1 MỞ ĐẦU Với sự bùng nổ và phát triển của công nghệ thông tin đã mang lại nhiều hiệu quả đối với khoa học cũng như các hoạt động thực tế, trong đó khai phá dữ liệu là một lĩnh vực mang lại hiệu quả thiết thực cho con người. Khai phá dữ liệu đã giúp người sử dụng thu được những tri thức hữu ích từ những cơ sở dữ liệu hoặc các kho dữ liệu khổng lồ khác. Cơ sở dữ liệu trong các đơn vị, tổ chức kinh doanh, quản lý khoa học chứa đựng nhiều thông tin tiềm ẩn, phong phú và đa dạng, đòi hỏi phải có những phương pháp nhanh, phù hợp, chính xác, hiệu quả để lấy được những thông tin bổ ích. Những “ tri thức” chiết suất từ nguồn cơ sở dữ liệu trên sẽ là nguồn thông tin hỗ trợ cho lãnh đạo trong việc lên kế hoạch hoạt động hoặc trong việc ra quyết định sản xuất kinh doanh. T iến hành công việc như vậy chính là thực hiện quá trình phát hiện tri thức trong cơ sở dữ liệu (Knowledge Discovery in Database) mà trong đó kỹ thuật khai phá dữ liệu (Data Mining) cho phép phát hiện những tri thức tiềm ẩn. Để lấy được thông tin mang tính tri thức trong khối dữ liệu khổng lồ, cần thiết phải phát triển các kỹ thuật có khả năng tích hợp các dữ liệu từ các hệ thống giao dịch khác nhau, chuyển chúng thành một tập hợp các cơ sở dữ liệu ổn định có chất lượng. Các kỹ thuật như vậy được gọi là kỹ thuật tạo kho dữ liệu và môi trường các dữ liệu nhận được khi áp dụng các kỹ thuật tạo kho dữ liệu nói trên được gọi là kho dữ liệu (Data Warehouse) [19, 24]. Một trong các nội dung cơ bản nhất trong khai phá dữ liệu và rất phổ biến là phát hiện các luật kế t hợp. Phương pháp này nhằm tìm ra các tập thuộc tính thường xuất hiện đồng thời trong cơ sở dữ liệu và rút ra các luật về ảnh hưởng của một tập thuộc tính dẫn đến sự xuất hiện của một (hoặc một tập) thuộc tính khác như thế nào. Bên cạnh đó, nhu cầu song song hóa và xử lý phân tán là rất cần thiết hiện nay bởi kích thước lưu trữ dữ liệu ngày càng nhiều nên đòi hỏi tốc độ xử lý cũng như dung lượng bộ nhớ hệ thống phải đảm bảo. Vì thế, yêu cầu cần có những thuật toán song song hiệu quả cho việc phát hiện luật kết hợp. Ứng dụng khai phá dữ liệu đã mang lại những lợi ích to lớn trong việc tổng hợp và cung cấp những thông tin trong các nguồn cơ sở dữ liệu lớn. Hơn nữa hiện nay nhu cầu song song hóa và xử lý phân tán là rất cần thiết bởi kích Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2 thước dữ liệu lưu trữ ngày càng lớn nên đòi hỏi tốc độ xử lý cũng như dung lượng bộ nhớ hệ thống phải đảm bảo Vì thế, yêu cầu cần có những thuật toán song song hiệu quả cho luật kết hợp. Phương pháp nghiên cứu của luận văn là tổng hợp các kết quả dự a trên các bài báo khoa học trong một số hội thảo quốc tế và các bài báo chuyên ngành, từ đó trình bày các vấn đề khai phá dữ liệu và xây dựng một số thuật toán khai phá luật kết hợp song song. Nội dung luận văn được trình bày trong 3 chương và phần kết luận Chương 1: Tổng quan về khai phá dữ liệu: Giới thiệu tổng quan về quá trình khai phá dữ liệu, kho dữ liệu và khai phá dữ liệu; kiến trúc của một hệ thống khai phá dữ liệu; Nhiệm vụ chính và các phương pháp khai phá dữ liệu. Chương 2: Khai phá luật kết hợp song song: Chương này trì nh bày tổng quan về luật kết hợp; phát biểu bài toán khai phá dữ liệu, phát hiện luật kết hợp; các khái niệm cơ bản luật kết hợp và các phương pháp khai phá luật kết hợp; khai phá luật kết hợp với một số khái niệm mở rộng. Chương 3: Một số phương pháp khai phá luật kết hợp song song và phân tích đánh giá các thuật toán song song . Thái Nguyên 01 tháng 10 năm 2008 Tác giả Lê Thị Việt Hoa Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 3 Chương 1 TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 1.1. Khái niệm Khai phá dữ liệu là một khái niệm ra đời vào những năm cuối của thập kỷ 80, nó là quá trình tìm kiếm, khám phá d ưới nhiều góc độ khác nhau nhằm phát hiện các mối liên hệ, quan hệ giữa các dữ liệu, đối tượng bên trong CSDL, kết quả của việc khai phá là xác định các mẫu hay các mô hình tồn tại bên trong nhưng chúng nằm ẩn ở các CSDL [3]. Về bản chất nó là giai đoạn duy nhất rút trích và tìm ra được các mẫu, các mô hình hay thông tin mới, tri thức tiềm ẩn có trong CSDL chủ yếu phục vụ cho mô tả và dự đoán. Đây là giai đoạn quan trọng nhất trong quá trình phát hiện tri thức từ CSDL, các tri thức này hỗ trợ trong việc ra quyết định, điều hành trong khoa học và kinh doanh. Khai phá dữ liệu là tiến trình khám phá tri thức tiềm ẩn trong các CSDL, cụ thể hơn, đó là tiến trình lọc, sản sinh những tri thức hoặc các mẫu tiềm ẩn, chưa biết những thông tin hữu ích từ các CSDL lớn. 1.2. Kiến trúc của một hệ thống khai phá dữ liệu Khai phá d ữ liệu là quá trình rút trích thông tin bổ ích từ những kho dữ liệu lớn. Khai phá d ữ liệu là quá trình chính trong khai phá tri th ức từ cơ sở dữ liệu. Kiến trúc của một hệ thống khai phá dữ liệu có các thành [2] phần như sau: Hình 1.1. Khám phá tri thức trong cơ sở dữ liệu điển hình Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 4 • CSDL, kho dữ liệu hoặc lưu trữ thông tin khác: Đây là một hay các tập CSDL, các khi dữ liệu, các trang tính hay các dạng khác của thông tin được lưu trữ. 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. • Máy chủ CSDL (Database or Warehouse Server): Máy chủ có trách nhiệm lấy những dữ liệu thích hợp dựa trên những yêu cầu khám phá của người dùng. • Cơ sở tri thức (Knowledge-base): Đây là miền tri thức dùng để tìm kiếm hay đánh giá độ quan trọng của các mẫu kết quả thu được. Tri thức này có thể bao gồm một sự phân cấp khái niệm dùng để tổ chức các thuộc tính hay các giá trị thuộc tính ở các mức trừu tượng khác nhau. • Máy khai phá dữ liệu (Data mining engine): là một hệ thống khai phá dữ liệu cần phải có một tập các Modul chức năng để thực hiện công việc, chẳng hạn như kết hợp, phân lớp, phân cụm. • Modul đánh giá mẫu ( Pattern evaluation): Bộ phận tương tác với các Modul khai phá dữ liệu để tập trung vào việc 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ể Modul đánh giá mẫu được tích hợp vào Modul khai phá dữ liệu, tùy theo cách cài đặt của phương pháp khai phá dữ liệu được dùng. • Giao diện đồ họa cho người dùng (Graphical user interface) Bộ phận này cho phép người dùng giao tiếp với hệ thống khai phá dữ liệu. Thông qua giao diện này người dùng tương tác với hệ thống bằng cách đặc tả một yêu cầu khai phá hay một nhiệm vụ, c ung cấp thông tin trợ giúp cho việc tìm kiếm và thực hiện khai phá thăm dò trên các kết quả khai phá trung gian. 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, 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.3. Các giai đoạn của quá trình khai phá dữ liệu Các thuật toán khai phá dữ liệu thường được mô tả như những chương trình hoạt động trực tiếp trên tệp dữ liệu. Với các phương pháp học máy và thống kê trước đây, bước đầu tiên là thuật toán thường nạp toàn bộ tệp (file) dữ liệu vào trong bộ nhớ. Khi chuyển sang các ứng dụng công nghiệp liên quan đến việc khai phá các kho dữ liệu lớn, mô hình này không thể đáp ứng được. Không Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 5 chỉ bởi nó không thể nạp hết dữ liệu vào trong bộ nhớ mà còn khó có thể chiết xuất dữ liệu ra các tệp đơn giản để phân tích. Hình 1.2. Các bước của quy trình khai phá dữ liệu Quá trình xử lý khai phá dữ liệu bắt đầu bằng việc xác định chính xác vấn đề cần giải quyết. Sau đó sẽ xác định dữ liệu liên quan dùng để xây dựng giải pháp. Tiếp theo là thu thập dữ liệu có liên quan và xử lý chúng thành dạng sao cho thuật toán khai phá dữ liệu có thể hiểu được. Quá trình khai phá dữ liệu [2] trải qua ba bước: Bước một: Lọc dữ liệu được thực hiện trong quá trình tiền xử lý. Công việc đầu tiên là tích hợp và chỉnh sửa dữ liệu. Khi dữ liệu được thu thập từ nhiều nguồn khác nhau nên có thể có những sự sai sót, dư thừa và trùng lặp. Lọc dữ liệu là cắt bỏ những dư thừa để dữ liệu được định dạng thống nhất. Dữ liệu sau khi lọc và chỉnh sửa sẽ nhỏ hơn, xử lý nhanh chóng hơn. Ví dụ, trong bài toán tìm quy luật mua hàng của khách hàng trong một siêu thị, ta tìm xem khách hàng thường cùng mua những mặt hàng nào để sắp xếp những món hàng đó gần nhau. Từ dữ liệu nguồn do siêu thị cung cấp, có thể có nhiều thuộc tính không cần thiết cho khai phá dữ liệu như: Mã khách hàng, nhà cung cấp, đơn giá hàng, người bán hàng… Các dữ liệu này cần cho quản lý bán hàng nhưng không cần cho khai phá dữ liệu, ta loại bỏ các thuộc tính này khỏi dữ liệu trước khi khai phá dữ liệu. Bước hai: Khai phá dữ liệu, là công việc chính, sử dụng các thuật toán khác nhau để khai phá các kiến thức tiềm ẩn trong dữ liệu. Xác định nhiệm vụ Xác định dữ liệu liên quan Thu thập và tiền xử lý dữ liệu Giải thuật khai phá dữ liệu DL trực tiếp Thống kê tóm tắt Mẫu Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 6 Bước ba: Sau xử lý, là quá trình ước lượng kết quả khai phá theo yêu cầu của người dùng. Nhiều kỹ thuật khai phá dữ liệu được ứng dụng cho một nguồn dữ liệu, các kỹ thuật cho các kết quả có thể khác nhau. Các kết quả được ước lượng bởi những quy tắc nào đó, nếu cuối cùng kết quả không thỏa mãn yêu cầu, chúng ta phải làm lại với kỹ thuật khác cho đến khi có kết quả mong muốn. 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. Để đạt được những mục đích này, nhiệm vụ chính của khai phá dữ liệu bao gồm như sau: Phân lớp dữ liệu [24] 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ó 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. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 7 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.3: Cây quyết định Trong hình 1.3 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 [13, 24] 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ữn g đố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 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 nhau 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. Tuổi 30-35 >35 Yes Sinh viên Giáo sư Yes No Yes No TID Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 8 Hình 1.4: 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 [13, 23]. 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ểm 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 [13, 24]. + + + + + + + + + + + + + + + + + + + + + + nhóm 1 + + nhóm 2 nhóm 3 Nợ