Tài liệu Khai phá dữ liệu trên cơ sở phương pháp luật kết hợp và ứng dụng

ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN ---------------------- NGUYỄN KHẢI HOÀI ANH KHAI PHÁ DỮ LIỆU TRÊN CƠ SỞ PHƯƠNG PHÁP LUẬT KẾT HỢP VÀ ỨNG DỤNG CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH MÃ SỐ : 604801 Công trình được hoàn thành tại: TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Người hướng dẫn khoa học: PGS.TS. Nguyễn Trọng Bình THÁI NGUYÊN 2010 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 1 http://www.lrc-tnu.edu.vn Công trình được hoàn thành tại: Khoa công nghệ thông tin – Đại học Thái Nguyên Người hướng dẫn khoa học: PGS.TS.Vũ Đức Thi Phản biện 1: Phản biện 2: Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn họp tại: Khoa Công nghệ thông tin – Đại học Thái Nguyên, vào hồi...... giờ...... ngày....... tháng........ năm 2010. Có thể tìm hiểu luận văn tại trung tâm học liệu Đại học Thái Nguyên và thư viện Trường CĐCN – Thái Nguyên Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 2 http://www.lrc-tnu.edu.vn 1 LỜI CAM ĐOAN Tôi xin cam đoan toàn bộ nội dung trong Luận văn hoàn toàn theo đúng nội dung đề cương cũng như nội dung mà cán bộ hướng dẫn giao cho. Nội dung luận văn, các phần trích lục các tài liệu hoàn toàn chính xác. Nếu có sai sót tôi hoàn toàn chịu trách nhiệm. Tác giả luận văn Nguyễn Khải Hoài Anh Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2 MỤC LỤC Trang Trang phụ bìa Lời cam đoan Mục lục………………………………………………………………………………………i Danh sách các ký hiệu, các từ viết tắt……………………………………………………...iv Danh mục các bảng…………………………………………………………………………v Danh mục các hình…………………………………………………………………………vi MỞ ĐẦU…………………………………………………………………………………...1 CHƢƠNG I: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU………………………………...3 1.1. Khai phá dữ liệu………………………………………………………………………3 1.1.1. Khái niệm về khám phá tri thức và khai phá dữ liệu…………………………3 1.1.2. Kiến trúc của một hệ thống khai phá dữ liệu ………………………………..5 1.1.3. Các loại dữ liệu được khai phá……………………………………………….6 1.1.4. Chức năng khai phá dữ liệu…………………………………………………..6 1.2. Một số phƣơng pháp khai phá dữ liệu thông dụng…………………………………7 1.2.1. Phương pháp luật kết hợp……………………………………………….......7 1.2.2. Phương pháp cây quyết định……………………………………………......7 1.2.3. Phương pháp k-Mean………………………………………………………...8 1.3. Một số ứng dụng của khai phá dữ liệu………………………………………………9 1.3.1. Phân tích dữ liệu gen và sinh học y học……………………………………...9 1.3.2. Phân tích dữ liệu tài chính………………………………………………........9 1.3.3. Dịch vụ bán lẻ……………………………………………………….............10 1.3.4. Công nghiệp viễn thông…………………………………………………….10 1.4. Các khuynh hƣớng và thách thức trong khai phá dữ liệu………………………...11 CHƢƠNG 2: KHAI PHÁ LUẬT KẾT HỢP TRONG CƠ SỞ DỮ LIỆU LỚN……..13 2.1. Khai phá luật kết hợp………………………………………………………….........13 2.1.1. Một số khái niệm cơ bản …………………………………………………13 2.1.2. Cách khai phá luật kết hợp………………………………………………….14 2.1.3. Các tính chất của frequent itemset………………………………………….14 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 3 2.1.4. Các tiêu chuẩn để phân loại luật kết hợp……………………………………15 2.1.4.1. Kiểu của giá trị được quản lý trong luật……………………………..15 2.1.4.2. Chiều của dữ liệu được đề cập trong luật……………………….......15 2.1.4.3. Mức trừu tượng được đề cập trong luật…………………………..15 2.2. Khai phá luật kết hợp boolean một chiều từ CSDL giao dịch…………………...16 2.2.1. Thuật toán Apriori: Tìm các frequent itemset sử dụng việc sinh ra các ứng viên……………………………………………………………………….16 2.2.2. Sinh luật kết hợp từ các frequent temset [5, 8, 15]…………………….........19 2.2.3. Cải tiến hiệu quả thuật toán Apriori………………………………………...19 2.2.3.1. Phương pháp dựa trên bảng băm……………………………........20 2.2.3.2. Giảm số giao dịch……………………………………………………….20 2.2.3.3. Phân đoạn………………………………………………………………..21 2.2.3.4. Lấy mẫu…………………………………………………………………..21 2.2.4. Khai phá các frequent itemset bằng cách không sinh ứng cử viên……........21 2.3. Khai phá luật kết hợp đa thức từ CSDL giao dịch………………………………...24 2.3.1. Luật kết hợp đa thức………………………………………………………...24 2.3.2. Các phương pháp khai phá luật kết hợp đa mức………………………........26 2.3.2.1. Đồng nhất độ hỗ trợ tối thiểu cho tất cả các mức…………………..26 2.3.2.2. Giảm dần độ hỗ trợ tối thiểu ở mức thấp hơn…………………….27 2.3.2.3. Độc lập theo từng mức………………………………………………….27 2.3.2.4. Lọc chéo mức bởi một itemset………………………………………….........27 2.4. Khai phá luật kết hợp đa chiều từ CSDL quan hệ và kho dữ liệu………………..28 2.4.1. Luật kết hợp đa chiều……………………………………………………….28 2.4.2. Khai phá luật kết hợp đa chiều sử dụng việc rời rạc hoá tĩnh các thuộc tính số lượng……………………………………………………………………….29 2.4.3. Khai phá luật kết hợp số lượng……………………………………………..30 2.4.4. Khai phá luật kết hợp dựa vào khoảng cách………………………………...31 CHƢƠNG 3: MỘT SỐ THUẬT TOÁN KHAI PHÁ LUẬT KẾT HỢP……………..34 3.1. Khám phá các frequent itemset……………………………………………….34 3.1.1. Thuật toán AIS………………………………………………….......34 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 4 3.1.2. Thuật toán SETM……………………………………………….......35 3.1.3. Thuật toán Apriori…………………………………………………..39 3.1.3.1. Hàm Apriori_gen……………………………………….40 3.1.3.2. Hàm subset……………………………………………...40 3.1.4. Thuật toán AprioriTID…………………………………….41 3.1.5. Thuật toán AprioriHybrid…………………………………………...43 3.2. Khám phá luật kết hợp……………………………………………………...44 3.2.1. Thuật toán sinh luật đơn giản……………………………………….45 3.2.2. Thuật toán nhanh………………………………………………........45 3.3. Thuật toán DHP (Direct Hashing with Efficent Pruning)………………...46 3.3.1 Thuật toán DHP……………………………………………………...46 3.3.2. Giảm kích thước của cơ sở dữ liệu giao dịch………………….........51 3.3.3. Giảm số lần quét cơ sở dữ liệu (Scan – Reduction method)………..53 3.4. Thuật toán PHP (Perfect Hash and Pruning)……………………………...53 3.5. So sánh các thuật toán khám phá các frequent itemset…………………...55 3.5.1. Sinh dữ liệu tổng hợp………………………………………….........55 3.5.2. So sánh các thuật toán AIS, SETM, Apriori và AprioriTID………..56 CHƢƠNG 4: CÀI ĐẶT CHƢƠNG TRÌNH THỬ NGHIỆM……………........63 “ MÔ PHỎNG THUẬT TOÁN APRIORI” 4.1. Phát biểu bài toán …………………………………………………………..63 4.2. Phân tích bài toán …………………………………………………………...63 4.3. Xây dựng dữ liệu…………………………………………………………….64 4.4. Cài đặt chƣơng trình thử nghiệm…………………………………………..64 4.5. Giao diện chính của chƣơng trình………………………………………….65 KẾT LUẬN VÀ ĐỀ NGHỊ…………………………………………………........67 TÀI LIỆU THAM KHẢO……………………………………………………….68 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 5 DANH MỤC CÁC KÝ HIỆU VÀ CÁC CHỮ VIẾT TẮT Diễn giải Ký hiệu Ck Tập các k-itemset ứng viên Ck 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 D Cơ sở dữ liệu giao dịch Di Phần thứ i của cơ sở dữ liệu D I Tập các mục Lk Tập các k-itemset phổ biến T Giao dịch (transaction) X ⇒Y Luật kết hợp (với X là tiền đề, Y là hệ quả) Conf Độ tin cậy (Confidence) k-itemset Tập mục gồm k mục Min_conf Ngưỡng tin cậy tối thiểu Min_sup Ngưỡng hỗ trợ tối thiểu Sup Độ hỗ trợ (support) Tid Định danh của giao dịch Tid-List Danh sách các định danh của giao dịch ARCS Association Rule Clustering System SQL Structured Query Language FP -growth Frequent -Pattern Growth FP -Tree Frequent pattern tree min_sup_count minimum support count DHP Direct Hashing with Efficent Pruning PHP Perfect Hash and Pruning Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 6 DANH MỤC CÁC BẢNG Trang Bảng 2.1: Tóm tắt quá trình khai phá cây FP – Tree 24 Bảng 2.2: Dữ liệu giao dịch của cho nhánh AllElectronecs 25 Bảng 2.3: Phân chia dựa trên khoảng cách 32 Bảng 3.1: Các tham số của chương trính sinh dữ liệu tổng hợp 56 Bảng 3.2: Các tham số 56 Bảng 3.3: Thời gian thực hiện theo giây (s) của thuật toán SETM 57 Bảng 3.4: So sánh thời gain thực hiện của Apriori và DHP (T15.I4.D100) 61 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 7 DANH MỤC HÌNH VẼ Trang Hình 1.1: Quy trình phát hiện tri thức 4 Hình 1.2: Kiến trúc của một hệ khai phá dữ liệu điển hình 5 Hình 1.3: Mẫu kết quả với phương pháp cây quyết định 7 Hình 1.4: Phân cụm các đối tượng k-Mean ( + là tâm của cụm) 8 Hình 2. 1: CSDL để thực hiện các bước hình 2.2 17 Hình 2.2: Các bước thực hiện của thuật toán Apriori với min _sup = 2/9 = 22% 18 Hình 2.3: Hai giai đoạn của kỹ thuật phân đoạn 21 Hình 2.4: Cây FP – tree 23 Hình 2.5: Cây conditional FP – tree 24 Hình 2.6: Hệ thống phân cấp khái niệm cho các item 25 Hình 2.7: min_sup được sử dụng khi khai phá ở các mức trừu tượng khác nhau 26 Hình 2.8: Giảm dần độ hỗ trợ tối thiểu ở mức thấp hơn 27 Hình 2.9: Độc lập theo từng mức 27 Hình 2.10: Lọc chéo mức bởi một itemset 28 Hình 2.11: Mạng cuboids tạo thành một data cube 3D 29 Hình 2.12: Lưới hai chiều do các luật kết hợp số lượng hai chiều với điều kiện buys 31 Hình3.1a: 38 Hìn 3.1b: Các bước thực hiện thuật toán SETM và min_sup_count = 2 39 Hình 3.2: Các bước thực hiện của thuật toán AprioriTID 43 Hình 3.3: Thời gian xử lý mỗi bước quét của thuật toán Apriori và AprioriTID 44 Hình 3.4: Các bước thực hiện thuật toán DHP 49 Hình 3.5: Tìm L2 và D3 52 Hình 3.6a: Thời gian thực hiện với các tập dữ liệu T5.I2.D100K và T10.I2.D100K 57 Hình 3.6b: Thời gian thực hiện với các tập dữ liệu T10.I4.D100K và T20.I2.D100K 58 Hình 3.6c: Thời gian thực hiện với các tập dữ liệu T20.I4.D100K và T20.I6.D100K 58 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 8 Hình 3.7: Kích thước của các tập frequent và các tập ứng cử viên 59 Hình 3.8: Thời gian thực hiện của Apriori và DHP 61 Hình 3.9: So sánh thời gian thực hiện của DHP và Apriori 62 Hình 4.1: Giao diện chính của chương trình 65 Hình 4.2: Lựa chọn CSDL 65 Hình 4.3: Kết quả khai phá luật kết hợp 66 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 9 LỜI NÓI ĐẦU Ngày nay các lĩnh vực khoa học kỹ thuật đang ngày một phát triển mạnh mẽ. Đặc biệt là nghành khoa học máy tính rất phát triển, nó được ứng dụng rất nhiều trong các lĩnh vực khác nhau của cuộc sống như: Giáo dục, Y tế, Kinh tế, Khoa học, Xây dựng… Với sự phát triển mạnh mẽ của công nghệ thông tin trong những năm gần đây, hâu, hầu hết các tổ chức, cơ quan đã thu thập một lượng lớn các dữ liệu trong cơ quan của họ. Các tổ chức này muốn chuyển những dữ liệu sẵn có của chính mình thành các tri thức và các thông tin có ích cho chính họ. Để làm được điều đó người ta đã sử dụng quá trình Phát hiện tri thức trong cơ sở dữ liệu( Knowledge Discovery in Database-KDD). Nhiệm vụ của KDD là từ dữ liệu sẵn có phải tìm ra những thông tin tiềm ẩn có giá trị mà trước đó chưa được phát hiện cũng như tìm ra những xu hướng phát triển và các xu hướng tác động lên chúng .Các kỹ thuật cho phép ta lấy được các tri thức từ cơ sở dữ liệu sẵn có đó được gọi là kỹ thuật Khai phá dữ liệu( Data Mining). Khai phá dữ liệu có thể xem như kết quả phát triển của công nghệ thông tin, khai phá dữ liệu là một giai đoạn quan trọng của quá trình phát triển tri thức. Một trong những bài toán phổ biến của khai phá dữ liệu là khai phá luật kết hợp. Khai phá luật kết hợp là tìm kiếm sự kết hợp đáng quan tâm hoặc quan hệ tương quan giữa một tập lớn các khoản mục (item). Những luật kết hợp khai phá được có thể giúp các tổ chức và các nhà quản lý đưa ra những quyết định kinh doanh hiệu quả hơn. Xuất phát từ những vấn đề đó em đã mạnh dạn lựa chọn đề tài luận văn: “KHAI PHÁ DỮ LIỆU TRÊN CƠ SỞ PHƢƠNG PHÁP LUẬT KẾT HỢP VÀ ỨNG DỤNG” là một việc làm không chỉ có ý nghĩa khoa học và còn mang đậm tính thực tiễn. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 10 Luận văn gồm 4 chương: Chương 1: Tổng quan về khai phá dữ liệu. Chương 2: Khai phá dữ liệu trong cơ sở dữ liệu lớn. Chương 3: Một số thuật toán khai phá luật kết hợp. Chương 4: Cài đặt chương trình thử nghiêm. Để có được kết quả này là nhờ sự giúp đỡ của các thầy cô trong Khoa Công nghệ thông tin - Đại học Thái Nguyên cũng như của bạn bè, đồng nghiệp, đặc biệt là chỉ bảo tận tình của PGS.TS.Vũ Đức Thi và sự nỗ lực của bản thân, đến nay tôi đã hoàn thành đề tài. Tuy nhiên trong quá trình làm việc, mặc dù đã cố gắng, nỗ lực hết sức nhưng không thể tránh khỏi thiếu sót, em tha thiết kính mong nhận được sự chỉ bảo của các thầy cô để đề tài được hoàn thiện hơn. Em xin chân thành cảm ơn ! Thái Nguyên, ngày 15 tháng 10 năm 2010 Học viên: Nguyễn Khải Hoài Anh Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 11 CHƢƠNG I TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU Trong thời đại ngày nay, với sự phát triển vượt bật của công nghệ thông tin, các hệ thống thông tin có thể lưu trữ một khối lượng lớn dữ liệu về hoạt động hàng ngày của chúng. Từ khối dữ liệu này, các kỹ thuật trong Khai Phá Dữ Liệu (KPDL) và máy học có thể dùng để trích xuất những thông tin hữu ích mà chúng ta chưa biết. Các tri thức vừa học được có thể vận dụng để cải thiện hiệu quả hoạt động của hệ thống thông tin ban đầu. 1.1. Khai phá dữ liệu 1.1.1. Khái niệm về khám phá tri thức và 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 trong 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 [3, 8, 16]: - Làm sạch dữ liệu (Data cleaning): Các thủ tục làm sạch dữ liệu được sử dụng để lấp kín những giá trị còn thiếu, loại bỏ nhiễu, nhận dạng các phần tử ngoài cuộc và hiệu chỉnh những dữ liệu không đồng nhất. - Tích hợp dữ liệu (Data intergation): Nó tổ hợp các dữ liệu từ nhiều nguồn khác nhau thành một kho dữ liệu không đồng nhất. - Lựa chọn dữ liệu (Data selection): Những dữ liệu thích hợp với nhiệm vụ phân tích được trích rút từ cơ sở dữ liệu (CSDL) - Chuyển đồi dữ liệu (Data transformation): Nó chuyển đổi hay hợp nhất dữ liệu về dạng thích hợp cho việc khai phá. Việc chuyển đổi dữ liệu có thể gồm các bước: + Loại bỏ nhiễu khỏi dữ liệu. + Kết tập các dữ liệu. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 4 + Khái quát hóa dữ liệu: Các dữ liệu mức thấp (hoặc mức nguyên thuỷ) được thay thế bởi các khái niệm mức cao hơn thông qua việc sử dụng phân cấp khái niệm. + Xây dựng thuộc tính: Các thuộc tính mới được xây dựng trên các dữ liệu cho trước và được thêm vào dữ liệu mới. - Khai phá dữ liệu (Data mining): Là giai đoạn thiết yếu, trong đó các phương pháp thông minh sẽ được áp dụng để trích xuất ra các mẫu dữ liệu. - Đánh giá mẫu (Pattern evaluation): Đánh giá sự hữu ích của các mẫu biểu diễn tri thức dựa vào một số phép đo. - Biểu diễn tri thức (Knowledge presentation): Ở giai đoạn này các kỹ thuật biểu diễn và hiển thị tri thức được sử dụng để đưa tri thức khai phá được đến người dùng. Hình 1.1: Quy trình phát hiện 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 các CSDL, các kho dữ liệu hoặc trong các loại lưu trữ thông tin khác. Các biểu 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 - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 5 1.1.2. Kiến trúc của một 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 như hình 1.2 [3, 8] - CSDL, kho dữ liệu hoặc các lưu trữ thông tin khác (Databases, Data warehouse,..): Đây là một hay một tập các 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ể hiện trên những dữ liệu này. - 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 thích hợp dựa trên các yêu cầu khai phá của người dùng. Giao diện đồ hạo ngƣời dùng Đánh giá mẫu Máy khai phá dữ liệu Cơ sở tri thức Máy chủ CSDL hay kho dữ liệu Làm sạch và tích hợp dữ liệu Cơ sở dữ liệu Lọc Kho dữ liệu Hình 1.2: Kiến trúc của một hệ khai phá dữ liệu điển hình - Cơ sở tri thức (Knowledge base): Đây là miền tri thức đượ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ả. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 6 - 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 hoá, kết hợp, phân lớp, phân cụm, phân tích sự tiến hoá. - 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á, tuỳ theo sự 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 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 khuôn dạng khác nhau. 1.1.3. Các loại dữ liệu đƣợc khai phá KPDL phải có thể được áp dụng vào một loại lưu trữ thông tin bất kì [8]. Các loại dữ liệu đó có thể là CSDL quan hệ, CSDL giao dịch, kho dữ liệu, các hệ CSDL nâng cao, các tập tin phẳng ( flat file) và Web. Các hệ CSDL nâng cao gồm CSDL hướng đối tượng, CSDL quan hệ đối tượng, CSDL hướng ứng dụng cụ thể như: CSDL chuỗi thời gian ( time-series), CSDL văn bản và CSDL đa phương tiện. 1.1.4. Chức năng khai phá dữ liệu KPDL có hai chức năng chính: mô tả (description) và dự đoán (prediction) [3,8] Công việc KPDL mô tả sẽ mô tả các tính chất hoặc đặc tính chung của dữ liệu trong CSDL, nghĩa là phân tích và mô tả một tập mẫu đã biết (a set of known sample) trong khả năng nhận thức của con người nhằm giúp họ hiểu rõ hơn, sâu hơn về dữ liệu. Còn công việc KPDL dự đoán sẽ thực hiện việc suy luận dựa trên dữ liệu hiện hành để cho ra các dự báo, nghĩa là phân tích tập dữ liệu huấn luyện và tạo ra một hoặc vài mô hình cho phép dự đoán các mẫu mới chưa biết (unseen new examples). Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 7 1.2. Một số phƣơng pháp khai phá dữ liệu thông dụng 1.2.1. Phƣơng pháp luật kết hợp Một trong những chủ đề phổ biến của KPDL là khám phá luật kết hợp [18]. Mục đích của khám phá luật kết hợp là xác định mối quan hệ, sự kết hợp giữa các item trong một CSDL lớn. Luật kết hợp là một luật dạng X => Y, với X, Y là tập các item [4, 5, 8]. Một luật kết hợp được gọi là mạnh, nếu nó thoả độ hỗ trợ và thoả độ tin cậy tối thiểu. Có nhiều thuật toán để khai phá luật kết hợp theo từng loại luật. Một trong những thuật toán thường gặp nhất là thuật toán Apriori. Chúng tôi sẽ trình bày chi tiết các thuật toán AIS, SETM, Apriori … trong các chương sau. 1.2.2. Phƣơng pháp cây quyết định Cây quyết định là một mô tả tri thức dạng đơn giản nhằm phân các đối tượng dữ liệu thành một số lớp nhất định[8]. Các nút của cây được gán nhãn là tên các thuộc tính, các cạnh được gán các giá trị có thể của các thuộc tính, các lá mô tả các lớp khác nhau. Các đối tượng được phân lớp theo các đường đi trên cây, qua các cạnh tương ứng với các giá trị của thuộc tính của đối tượng tới lá. Hình 1.3 mô tả một mẫu đầu ra có thể của quá trình khai phá dữ liệu dùng phương pháp cây quyết định với tập dữ liệu khách hàng xin vay vốn. Nợ < n Nợ > n Không cho vay Thu nhập < T Không cho vay Thu nhập > T Cho vay Hình 1.3: Mẫu kết quả với phương pháp cây quyết định Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 8 1.2.3. Phƣơng pháp k-Mean Phân cụm cũng là một trong những chủ đề được quan tâm nhiều trong nghiên cứu KPDL. Có nhiều phương pháp được sử dụng trong phân cụm, phương pháp kMean được coi là các kỹ thuật cơ bản của phân cụm [8]. Với phương pháp này sẽ chia tập có n đối tượng thành k cụm sao cho các đối tượng trong cùng một cụm thì giống nhau, các đối tượng khác cụm thì khác nhau. Đầu tiên chọn k đối tượng ngẫu nhiên, mỗi đối tượng đại diện cho tâm của cụm (cluster mean or center). Dựa vào khoảng cách giữa tâm cụm với mỗi đối tượng còn lại, gán mỗi đối tượng vào một cụm mà nó giống nhau nhất. Sau đó, tính tâm mới của mỗi cụm. Quá trình được lặp lại cho đến khi hàm tiêu chuẩn hội tụ (criterion function k converges). Chẳng hạn sử dụng hàm tiêu chuẩn: E    p  mi , với p là một điểm đại diện một đối tượng cho trước và mi là tâm 2 i 1 pCi của cụm. Ví dụ: Phân cụm các đối tượng trong không gian thành 3 cụm (k=3) như hình 1.4       +                            (a)             (b)                    (c) Hình 1.4: Phân cụm các đối tượng k-Mean ( + là tâm của cụm) Với đối tượng được đánh dấu cộng (+) là tâm cụm. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn   9 1.3. Một số ứng dụng của khai phá dữ liệu 1.3.1. Phân tích dữ liệu gen và sinh học y học KPDL đã trở thành một công cụ mạnh và đóng góp thiết thực vào việc phân tích gen theo các cách sau [8]: Nghiên cứu tương tự và so sánh các chuỗi gen: Một trong những nghiên cứu quan trọng trong phân tích gen là nghiên cứu tương tự và so sánh các chuỗi gen. Các chuỗi gen được cô lập từ các mô bệnh và khoẻ có thể được so sánh với nhau để nhận dạng những khác biệt giữa hai lớp gen. Phân tích kết hợp: Nhận dạng các chuỗi gen cùng xảy ra, phân tích kết hợp có thể được sử dụng giúp chúng ta xác định các loại gen thường kết hợp với nhau để gây nên bệnh. Phân tích hướng đi: Liên kết các gen ở các giai đoạn khác nhau của quá trình phát triển bệnh, nếu một chuỗi hoạt động của các gen ở những giai đoạn khác nhau của bệnh được xác định, thì có thể giúp chúng ta chế tạo ra các dược phẩm can thiệp vào từng giai đoạn của bệnh. Do đó, có thể đạt được cách điều trị bệnh hiệu quả hơn. 1.3.2. Phân tích dữ liệu tài chính Dữ liệu tài chính nhận được tương đối hoàn chỉnh, đáng tin cậy và chất lượng cao làm thuận lợi cho việc phân tích dữ liệu, KPDL một cách hệ thống. Các ứng dụng của KPDL vào lĩnh vực tài chính là [8, 14]: Dự đoán trả tiền vay và phân tích chính sách tín dụng khách hàng: Dự đoán trả tiền vay và phân tích chính sách tín dụng khách hàng là vấn đề quan trọng đối với việc kinh doanh của ngân hàng. Có nhiều yếu tố (chẳng hạn: tỉ lệ trả trên thu nhập, mức thu nhập, mức học vấn, vùng dân cư, lịch sử tín dụng,…) có thể ảnh hưởng mạnh hoặc yếu đến việc thực hiện trả tiền vay và sự đánh giá mức độ tín nhiệm khách hàng. Các phương pháp KPDL như lựa chọn đặc trưng, xếp hạng các thuộc tính liên quan có thể giúp xác định các yếu tố quan trọng và loại bỏ những yếu tố không liên quan. Do đó, ngân hàng có thể điều chỉnh chính sách cho vay đối với Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 10 những khách hàng mà trước đây ngân hàng đã từ chối nhưng nay tỉ mạo hiểm đối với họ là thấp dựa vào các phân tích trên. Phát hiện các tội phạm tài chính: Để phát hiện việc chuyển tiền bất chính vào ngân hàng và các tội phạm tài chính, việc tích hợp thông tin từ các CSDL khác nhau (CSDL giao dịch ngân hàng, CSDL về lịch sử tội phạm) là rất quan trọng. Sau khi có dữ liệu tổng hợp, chúng ta có thể dựa trên các công cụ của KPDL để phát hiện ra các mẫu khác thường. 1.3.3. Dịch vụ bán lẻ Dịch vụ bán lẻ là một trong những lĩnh vực ứng dụng của KPDL. Một lượng dữ liệu khổng lồ đã và đang được thu thập ngày càng tăng, đặc biệt với sự gia tăng về sự tiện lợi, lợi ích và tính phổ biến của việc kinh doanh trên Web, thương mại điện tử. Dữ liệu bán lẻ cung cấp một kho dữ liệu phong phú cho việc khai phá dữ liệu. KPDL bán lẻ có thể giúp chúng ta xác định được hành vi mua hàng của khách hàng, phát hiện những mẫu mua hàng của người dùng, những khuynh hướng mua hàng [8]. Thiết kế các chiến dịch kinh doanh: Giữ khách hàng - Phân tích lòng trung thành của khách hàng: Lòng trung thành của khách hàng và khuynh hướng mua hàng có thể được phân tích một cách hệ thống. 1.3.4. Công nghiệp viễn thông Công nghiệp viễn thông đã phát triển nhanh từ các dịch vụ điện thoại cục bộ và điện thoại đường dài cho đến các dịch vụ truyền thông khác như voice, fax, image, e-mail, truyền dữ liệu Web, các giao lộ dữ liệu khác. Tích hợp viễn thông, mạng máy tính, internet, các phương tiện truyền thông khác đã và đang được thực hiện. Điều này tạo ra một yêu cầu lớn về KPDL để giúp hiểu thêm việc kinh doanh, xác định các mẫu viễn thông, chặn đứng các hoạt động lừa dối nhằm tạo điều kiện sử dụng các tài nguyên tốt hơn và nâng cao được chất lượng dịch vụ [8]. Phân tích nhu cầu: Dữ liệu viễn thông là các dữ liệu đa chiều đích thực, với các chiều như: giờ gọi, thời gian gọi, vị trí người gọi, vị trí người được gọi, Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn