Tài liệu Phát triển thuật toán khai phá tập thường xuyên dựa vào sự gom cụm dữ liệu 272992

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI ----------------------------------------------------- Mai Thị Hiên PHÁT TRIỂN THUẬT TOÁN KHAI PHÁ TẬP THƯỜNG XUYÊN DỰA VÀO SỰ GOM CỤM DỮ LIỆU Chuyên ngành: CÔNG NGHỆ THÔNG TIN LUẬN VĂN THẠC SĨ KỸ THUẬT NGƯỜI HƯỚNG DẪN KHOA HỌC TS. NGUYỄN HỮU TRỌNG Hà Nội – 2013 LỜI CẢM ƠN Tác giả xin chân thành tri ân TS Nguyễn Hữu Trọng - Đại học Nha Trang, vị thầy đáng kính, đã dày công hướng dẫn và giúp đỡ tác giả hoàn thành luận văn này. Xin chân thành cảm ơn Quý Thầy Cô, nhân viên thuộc Viện Công nghệ thông tin và Truyền Thông, Viện Sau đại học – Trường Đại học Bách Khoa Hà Nội, Quý Thầy cô Trường Đại học Nha Trang, … bởi sự quan tâm giúp đỡ tận tâm và thiết thực trong quá trình nghiên cứu và hoàn thành luận văn. Xin chân thành cảm ơn quý Thầy Cô đã đọc và góp ý chân thành để tác giả hoàn thiện luận văn. Xin chân thành cảm ơn các đồng nghiệp thuộc Trung tâm Ngoại ngữ - Tin học – Học viện Hải quân, cảm ơn các bạn học viên lớp Cao học Công nghệ thông tin khóa 2012A học tại Nha Trang, những người thân yêu đã tạo điều kiện về mặt thời gian, công việc, động viên, giúp đỡ trong suốt quá trình học tập và hoàn thành luận văn. Cuối cùng xin cảm ơn những người thân trong gia đình cùng bạn bè đã luôn tạo những điều kiện thuận lợi nhất, luôn là chỗ dựa về mặt tinh thần vững chắc để tác giả hoàn thành nhiệm vụ của mình. Hà Nội, tháng 10 năm 2013 Mai Thị Hiên ii LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của tôi dưới sự hướng dẫn của TS Nguyễn Hữu Trọng. Các số liệu, kết quả nêu trong luận văn là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác. Hà Nội, ngày 1 tháng 11 năm 2013 Mai Thị Hiên iii MỤC LỤC TRANG PHỤ BÌA .................................................................................................. i LỜI CẢM ƠN ....................................................................................................... II LỜI CAM ĐOAN ............................................................................................... III MỤC LỤC........................................................................................................... IV DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT......................................... VI DANH MỤC CÁC BẢNG ................................................................................. VII DANH MỤC CÁC HÌNH, ĐỒ THỊ ................................................................ VIII MỞ ĐẦU ................................................................................................................ 1 CHƯƠNG 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ PHÂN CỤM DỮ LIỆU ...................................................................................................................... 4 1.1. MỞ ĐẦU .......................................................................................................... 4 1.2. CÁC MÔ HÌNH KHAI PHÁ DỮ LIỆU............................................................ 6 1.2.1. Khai phá dữ liệu suy diễn .............................................................................. 6 1.2.2. Khai phá dữ liệu mô tả................................................................................... 7 1.3. CÁC KHÁI NIỆM CƠ BẢN ............................................................................ 9 1.3.1. Cơ sở dữ liệu giao tác .................................................................................... 9 1.3.2. Tính chất của tập thường xuyên ................................................................... 13 1.4. KHAI PHÁ LUẬT KẾT HỢP ........................................................................ 13 1.4.1. Cách tiếp cận khai phá luật kết hợp ............................................................. 14 1.4.2. Một số thuật toán phát hiện luật kết hợp ...................................................... 15 1.5. PHÂN CỤM DỮ LIỆU .................................................................................. 23 1.5.1. Khái niệm phân cụm .................................................................................... 23 1.5.2. Các phép đo độ tương tự .............................................................................. 24 1.5.3. Một số thuật toán phân cụm ......................................................................... 26 1.6. KẾT LUẬN .................................................................................................... 29 CHƯƠNG 2. THUẬT TOÁN KHAI PHÁ TẬP THƯỜNG XUYÊN HIỆU QUẢ SỬ DỤNG KỸ THUẬT PHÂN CỤM ....................................................... 30 2.1. MỞ ĐẦU ........................................................................................................ 30 iv 2.2. NỘI DUNG THUẬT TOÁN .......................................................................... 31 2.2.1. Phân cụm và phân hoạch ............................................................................. 31 2.2.2. Các thủ tục cài đặt ....................................................................................... 32 2.3. VÍ DỤ MINH HỌA ........................................................................................ 34 2.4. KẾT LUẬN .................................................................................................... 36 CHƯƠNG 3. PHÁT TRIỂN THUẬT TOÁN KHAI PHÁ TẬP THƯỜNG XUYÊN DỰA VÀO SỰ GOM CỤM DỮ LIỆU. THUẬT TOÁN QFIM. ........ 38 3.1. MỞ ĐẦU ........................................................................................................ 38 3.2. THUẬT TOÁN QFIM TÌM TẬP THƯỜNG XUYÊN TRÊN CƠ SỞ DỮ LIỆU GIAO TÁC ĐÃ PHÂN CỤM .............................................................. 39 3.2.1. Phân cụm cơ sở dữ liệu giao tác .................................................................. 39 3.2.2. Thuật toán QFIM ......................................................................................... 43 3.3. VÍ DỤ MINH HỌA ........................................................................................ 47 3.3.1. Dữ liệu......................................................................................................... 47 3.3.2. Áp dụng thuật toán QFIM để khai phá tập thường xuyên ............................. 49 3.4. KẾT QUẢ THỬ NGHIỆM ............................................................................. 58 3.4.1. Tập dữ liệu T10I4D100K ............................................................................. 59 3.4.2. Tập dữ liệu T1I5D10000K ........................................................................... 60 3.5. ĐÁNH GIÁ THUẬT TOÁN .......................................................................... 61 3.5.1. Độ phức tạp của thuật toán .......................................................................... 61 3.5.2. Tính đúng đắn của thuật toán ...................................................................... 62 3.6. KẾT LUẬN .................................................................................................... 62 KẾT LUẬN .......................................................................................................... 64 1. NHỮNG KẾT QUẢ ĐẠT ĐƯỢC ..................................................................... 64 2. HƯỚNG NGHIÊN CỨU TIẾP THEO .............................................................. 66 TÀI LIỆU THAM KHẢO ................................................................................... 67 v DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT Trong suốt luận văn này, tác giả dùng thống nhất: Ký hiệu: I = {x1, x2, …, xn}: Tập n mục dữ liệu. T = {t1, t2, …, tm}: Cơ sở dữ liệu có m giao tác. xj: mục dữ liệu thứ j. ti:Giao tác thứ i. m: Số giao tác của một cơ sở dữ liệu giao tác. n: Số mục dữ liệu của một cơ sở dữ liệu giao tác. A, B, C, …: Tên của các mục dữ liệu trong cơ sở dữ liệu giao tác ví dụ. X, Y: Là các tập con của tập mục dữ liệu I, X, Y ⊆ I. S: Là tập con các giao tác của cơ sở dữ liệu giao tác T, S ⊆ T. X = ABC thay cho X = {A, B, C} trong các ví dụ minh họa. S0, MinSup: Ngưỡng tối thiểu. Supp(xi) thay cho Supp({xi}). ∥X∥: Số phần tử của tập hợp X. Set(t): Tập hợp các mục dữ liệu của giao tác t Subset(U) = {X | X ⊆ U}: Tập các tập con của U. Viết tắt: KPDL: Khai phá dữ liệu KPTT: Khai phá tri thức CSDL: Cơ sở dữ liệu. DL: Dữ liệu. MDL: Mục dữ liệu. TT: Thuật toán. GC: Gom cụm CNTT: Công nghệ thông tin TUV: Tập ứng viên vi DANH MỤC CÁC BẢNG Bảng 1.1. Cơ sở dữ liệu giao tác .............................................................................. 9 Bảng 1.2. Ma trận giao tác ..................................................................................... 10 Bảng 1.3. Biểu diễn ngang của CSDL giao tác ...................................................... 11 Bảng 1.4. Biểu diễn dọc của CSDL giao tác .......................................................... 11 Bảng 1.5. Kết quả thuật toán Apriori ..................................................................... 16 Bảng 1.6. Những biến đổi dữ liệu của FP-Growth ................................................. 20 Bảng 2.1. Cơ sở dữ liệu giao tác ............................................................................ 34 Bảng 2.2. Kết quả phân cụm .................................................................................. 34 Bảng 2.3. Kết quả thuật toán Improved Apriori ..................................................... 35 Bảng 3.1. Mã hóa các dịch vụ giá trị gia tăng ........................................................ 47 Bảng 3.2. Dữ liệu của 20 thuê bao di động ............................................................ 48 Bảng 3.3. Ma trận giao tác ..................................................................................... 49 Bảng 3.4. Độ hỗ trợ của các MDL ......................................................................... 49 Bảng 3.5. Độ hỗ trợ giảm dần của các MDL .......................................................... 50 Bảng 3.6. CSDL đã được sắp xếp .......................................................................... 50 Bảng 3.7. Kết quả phân rã giao tác ........................................................................ 51 Bảng 3.8. Kết quả phân cụm giao tác ..................................................................... 52 Bảng 3.9. Tập C2’ .................................................................................................. 55 Bảng 3.10. Ý nghĩa của các tham số trong tên CSDL............................................. 58 Bảng 3.11. So sánh thời gian chạy hai thuật toán QFIM và Apriori trên dữ liệu T10I4D100K. ........................................................................................................ 59 Bảng 3.12. So sánh thời gian chạy hai thuật toán QFIM và Apriori trên dữ liệu T1I5D10000K. ...................................................................................................... 60 vii DANH MỤC CÁC HÌNH, ĐỒ THỊ Hình 1.1. Quá trình khai phá tri thức trong CSDL ................................................... 4 Hình 1.2. Cây quyết định ......................................................................................... 6 Hình 1.3. FP-tree của dữ liệu bảng 1.1 ................................................................... 20 Hình 1.4 Thành phần của FP-tree .......................................................................... 21 Hình 3.1. So sánh thời gian chạy hai thuật toán QFIM và Apriori trên dữ liệu T10I4D100K. ........................................................................................................ 59 Hình 3.2. So sánh thời gian chạy hai thuật toán QFIM và Apriori trên dữ liệu T1I5D10000K. ...................................................................................................... 60 viii MỞ ĐẦU Trên thế giới, nhân loại đang bước vào một thời đại mới - đó là thời đại mà thông tin, tri thức trở thành lực lượng sản xuất trực tiếp; thời đại của xã hội thông tin và nền kinh tế tri thức được hình thành trên cơ sở phát triển và ứng dụng rộng rãi Công nghệ thông tin (CNTT) - Truyền thông. Việt Nam đã trở thành thành viên Tổ chức Thương mại Thế giới (WTO). Trong xu thế thương mại toàn cầu hóa đó, sự cạnh tranh trên thị trường quốc tế ngày càng diễn ra gay gắt. Để tồn tại và phát triển, mỗi công ty cần phải luôn nỗ lực và cố gắng đề ra các chiến lược đúng đắn để sử dụng đạt hiệu quả tối đa nguồn lực của công ty, nâng cao được lợi thế cạnh tranh và cuối cùng trở thành người chiến thắng. Ngành công nghiệp viễn thông cũng không thể đi khỏi quỹ đạo ấy. Các công ty viễn thông lưu trữ một khối lượng dữ liệu khổng lồ, bao gồm: dữ liệu về các khách hàng, các dịch vụ giá trị gia tăng, thông tin cảnh báo tình trạng của hệ thống mạng viễn thông,… Những dữ liệu về khách hàng bao gồm: thông tin cá nhân, chi tiết các cuộc gọi, các dịch vụ giá trị gia tăng mà khách hàng đăng ký sử dụng,… có thể giúp nhận diện được những đặc tính của khách hàng. Hiện nay, trên một thuê bao viễn thông, có rất nhiều dịch vụ giá trị gia tăng khác nhau. Ví dụ: truy cập internet, đọc truyện online, đọc sách điện tử, gửi tin nhắn nhóm, chặn các cuộc gọi lạ, báo cuộc gọi nhỡ, nhạc chờ Imuzilk, chuyển tiền, Yahoo chat, quà tặng âm nhạc, đọc báo online, dịch vụ Game,… Với cơ sở dữ liệu (CSDL) các thuê bao, chúng ta có thể khám phá mối liên kết trong việc sử dụng các dịch vụ. Có thể đưa ra các luật như “có 75% khách hàng gọi điện thoại quốc tế thì có truy cập internet”, “có 10% khách hàng sử dụng dịch vụ nhạc chờ Imuzilk thì có truy cập internet”, “có 70% khách hàng dùng dịch vụ Mobile Internet và dịch vụ Dailyinfo thì sử dụng Yahoo chat”, ... Trên cơ sở phân tích được các luật như vậy, các công ty viễn thông có thể điều chỉnh việc đầu tư thiết bị sao cho phù hợp với sự phát triển khách hàng. Ví dụ có thêm một số lượng lớn khách hàng đăng ký gọi điện thoại quốc tế thì phải đầu tư thêm thiết bị cung cấp dịch vụ Internet, nhưng nếu có một số lượng lớn khách hàng sử dụng nhạc chờ 1 Imuzilk thì chưa cần đầu tư thêm thiết bị cung cấp dịch vụ Internet. Cũng từ việc phân tích được các tập luật, công ty có thể tăng số lượng các trạm giao dịch tại những nơi có tần suất sử dụng các dịch vụ cao và những nơi có số lượng người dùng đăng ký sử dụng dịch vụ lớn. Thông qua đó, có thể đưa ra các chính sách chăm sóc khách hàng thích hợp, có những chiến lược kinh doanh, tiếp thị hiệu quả, phát huy tối đa hiệu suất công việc, tiết kiệm chi phí và nhân lực dựa trên các kết quả dự đoán. Ứng dụng kỹ thuật khai phá dữ liệu (data mining) để phát hiện các quy luật ẩn chứa trong khối dữ liệu khổng lồ đó sẽ mang lại cho các công ty viễn thông nhiều cơ hội để phát triển các ứng dụng mang tính thực tiễn cao. Đây là một hướng đi phù hợp và đã sớm được áp dụng phổ biến ở nhiều công ty viễn thông lớn trên thế giới cũng như các công ty viễn thông ở nước ta. Khai phá dữ liệu là một công đoạn trong tiến trình lớn hơn là khai phá tri thức (Knowledge Discovery Process - KDP). Khai phá dữ liệu giúp phát hiện những xu thế phát triển từ những thông tin quá khứ, cũng như cho phép đề xuất các dự báo mang tính thống kê, gom cụm và phân loại dữ liệu. Tìm các luật kết hợp là công việc cơ bản trong khai phá dữ liệu. Quá trình đó được giải quyết theo hai bước chính: Bước một, tìm tất cả các tập thường xuyên theo ngưỡng tối thiểu S0 cho trước. Bước hai, dựa vào các tập thường xuyên, tìm các luật kết hợp. Tất cả khó khăn của quá trình tập trung ở bước một. Các nghiên cứu về khai phá luật kết hợp đều tập trung cải tiến tốc độ xử lý, dung lượng bộ nhớ và số lần truy cập CSDL. Nghiên cứu về sự liên hệ, tìm các luật kết hợp giữa các MDL được giới thiệu lần đầu tiên bởi Agrawal. R., Imielinski. T., Swami. A., trong [9]. Trên thế giới, kết quả nghiên cứu về khai phá luật kết hợp được tổng kết trong [15] và bởi B.Goethals trong [16]. Thuật toán AIS được Agrawal. R giới thiệu lần đầu tiên vào năm 1993 trong [9], thuật toán Apriori năm 1994 trong [10] rồi từng bước được các tác giả và nhóm nghiên cứu công bố: FP_Growth của J. Han năm 2000 [18]... 2 Ở Việt Nam, khai phá dữ liệu đã được nhiều tiến sĩ nghiên cứu như GS TSKH Hồ Tú Bảo, PGS TSKH Nguyễn Xuân Huy, PGS TS Đoàn Văn Ban, GS TSKH Hoàng Văn Kiếm, PGS TS Vũ Đức Thi, PGS TS Đỗ Phúc, PGS TS Lê Hoài Bắc, TS Nguyễn Hữu Trọng với nhiều bài báo được công bố [1], [2], [3], [4], [5], [6], [7], [8 ] đã có nhiều luận án tiến sĩ và thạc sĩ đã bảo vệ có nhiều kết quả được công bố. Mục đích của luận văn là “Phát triển thuật toán khai phá tập thường xuyên dựa vào sự gom cụm dữ liệu”. Bố cục của luận văn bao gồm phần mở đầu, ba chương nội dung, phần kết luận, kiến nghị và hướng phát triển, cuối luận văn là tài liệu tham khảo. Đầu của mỗi chương có phần giới thiệu nội dung của chương để tiện theo dõi. Chương 1 trình bày tổng quan về khai phá dữ liệu và phân cụm dữ liệu: Các mô hình khai phá dữ liệu, các khái niệm cơ bản về khai phá luật kết hợp. Trong chương này trình bày một số thuật toán cơ bản trong việc tìm tập thường xuyên: Apriori, Partition, FP-Growth. Trình bày các khái niệm về phân cụm dữ liệu và một số phương pháp phân cụm phổ biến. Chương 2 tìm hiểu thuật toán khai phá tập thường xuyên hiệu quả sử dụng kỹ thuật phân cụm (Efficient Algorithm For Mining Frequent Itemsets Using Clustering Techniques) đã được D.Kerana Hanirex và Dr.M.A Dorai Rangaswamy phát triển năm 2011 trong [21], trình bày hai thuật toán con của thuật toán là: PAFI và Improved Apriori. Các đóng góp chính của luận văn được trình bày trong chương 3. Trong chương này tác giả đề nghị thuật toán mới để khai phá tập thường xuyên, được đặt tên QFIM (Quick Frequent Itemset Mining), dựa vào kỹ thuật gom cụm dữ liệu. Thuật toán được chứng minh sự đúng đắn bằng toán học. Kết quả thử nghiệm trên dữ liệu chuẩn khẳng định sự nhanh chóng của thuật toán. Phần kết luận nêu những đóng góp của luận văn và đề xuất hướng phát triển của đề tài. Cuối cùng là phần tài liệu tham khảo. 3 Chương 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ PHÂN CỤM DỮ LIỆU 1.1. MỞ ĐẦU Khai phá dữ liệu (data mining) là quá trình khám phá các tri thức mới và các tri thức có ích ở dạng tiềm năng trong nguồn dữ liệu đã có. Đây là quá trình cốt lõi trong khai phá tri thức từ CSDL. Đánh giá mẫu và biểu diễn tri thức Tri thức Khai phá dữ liệu Mẫu dữ liệu Lựa chọn và biến đổi Lọc và tích hợp Dữ liệu thực Kho dữ liệu Dữ liệu để khai phá Hình 1.1. Quá trình khai phá tri thức trong CSDL Quá trình khai phá dữ liệu trải qua 3 bước chính sau: Bước 1: Chuẩn bị dữ liệu. Do dữ liệu được thu thập từ nhiều nguồn khác nhau nên có thể có những sai sót, dư thừa và trùng lặp. Vì vậy bước chuẩn bị dữ liệu là bước rất quan trọng. Dữ liệu sau bước chuẩn bị này sẽ nhỏ hơn, xử lý nhanh chóng hơn. Chuẩn bị dữ liệu bao gồm các công đoạn sau: - Lọc dữ liệu (Data cleaning): Loại bỏ dữ liệu nhiễu, dữ liệu không thích hợp. - Tích hợp dữ liệu(Data integration): Tích hợp dữ liệu từ các nguồn khác nhau. - Chọn dữ liệu (Data selection): Chọn những dữ liệu liên quan trực tiếp đến nhiệm vụ. 4 - Chuyển đổi dữ liệu (Data transformation): Chuyển dữ liệu về những dạng phù hợp cho việc khai phá. Ví dụ, Công ty cung cấp dịch vụ điện thoại, trong bài toán khảo sát việc sử dụng dịch vụ của nhóm khách hàng là sinh viên, xem họ thường xuyên sử dụng dịch vụ gì: nhắn tin, tải nhạc, Yahoo chat…? Từ dữ liệu nguồn do trạm viễn thông cung cấp, có thể có nhiều thuộc tính không cần thiết cho KPDL như: Mã khách hàng, Họ tên khách hàng, Số chứng minh nhân dân, Địa chỉ khách hàng,… Các thuộc tính này cần cho quản lý chứ không cần cho KPDL, do đó nên loại bỏ các thuộc tính này khỏi dữ liệu trước khi khai phá. Bước 2: Khai phá dữ liệu Đây là bước mang tính tư duy của khai phá tri thức. Ở bước này cần trích xuất thông tin có ích, các mẫu điển hình trong dữ liệu hay các quy luật liên quan giữa các yếu tố của dữ liệu. Có rất nhiều các kỹ thuật, thuật toán khác nhau được đề xuất ở bước này. Bước 3: Hậu xử lý Không phải bất cứ mẫu dữ liệu nào được trích xuất ra ở bước khai phá dữ liệu cũng đều là mẫu hữu ích, đôi khi nó còn bị sai lệch. Vì vậy cần phải có những tiêu chuẩn đánh giá phù hợp để trích xuất ra các tri thức thực sự có ích. Bước hậu xử lý bao gồm 2 công đoạn: - Đánh giá mẫu (Pattern evaluation): Đánh giá mẫu hoặc tri thức đã thu được. - Biểu diễn tri thức (Knowledge Presentation): Biểu diễn những tri thức khai phá được để người sử dụng dễ hiểu. Đây là quá trình mang tính định tính với mục đích phát hiện tri thức và xây dựng bài toán tổng kết. Những khó khăn cần giải quyết trong bài toán KPDL là lượng dữ liệu lớn, kích thước dữ liệu lớn, dữ liệu động và luôn tăng trưởng, các trường dữ liệu không phù hợp, các giá trị bị thiếu, các trường dữ liệu bị thiếu,… 5 1.2. CÁC MÔ HÌNH KHAI PHÁ DỮ LIỆU Nói chung, có hai mô hình khai phá dữ liệu: suy diễn và mô tả [17]. Suy diễn là quá trình dựa trên dữ liệu hiện thời để dự đoán những quy luật được phát hiện từ các mối liên hệ giữa các thuộc tính của dữ liệu. Mô tả dữ liệu là tổng kết hoặc diễn tả những đặc điểm chung của những thuộc tính dữ liệu trong kho dữ liệu. Với hai mô hình khai phá dữ liệu này có nhiều kỹ thuật đã được nghiên cứu và sử dụng như: Phân lớp dữ liệu, hồi qui, luật kết hợp, gom cụm dữ liệu,... 1.2.1. Khai phá dữ liệu suy diễn a. Phân lớp Phân lớp dữ liệu là xây dựng một mô hình mà có thể chia các đối tượng thành những lớp khác nhau để 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. Các luật phân lớp được sử dụng để xây dựng các bộ phận lớp dữ liệu. Phân lớp dữ liệu có vai trò quan trọng trong tiến trình dự báo các khuynh hướng, quy luật phát triển. 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. 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. Một ví dụ tiêu biểu về cây quyết định: Tuổi <30 Sinh viên Yes >35 30-35 Giáo sư Yes Yes No Hình 1.2. Cây quyết định 6 No Hình 1.2 là một cây quyết định cho lớp mua máy laptop, cho thấy 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, 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 tuổi và nghề nghiệp của khách hàng. 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. b. Hồi quy Phân lớp dữ liệu chỉ dùng để dự đoán về các giá trị rời rạc còn phương pháp hồi qui dùng để dự đoán về các giá trị liên tục. Hồi qui là một hàm toán học, ánh xạ một MDL thành một biến dự đoán có giá trị thực. Có rất nhiều ứng dụng KPDL với nhiệm vụ hồi qui, như khả năng đánh giá tử vong của bệnh nhân khi biết các kết quả xét nghiệm; chuẩn đoán, dự đoán nhu cầu tiêu thụ một sản phẩm mới bằng một hàm chi tiêu quảng cáo,... 1.2.2. Khai phá dữ liệu mô tả a. Gom cụm Gom cụm dữ liệu hay phân cụm dữ liệu là nhóm các đối tượng tương tự nhau trong tập dữ liệu vào các cụm sao cho các đối tượng trong cùng một cụm là tương đương nhau còn các đối tượng thuộc các cụm khác nhau thì không tương đương. Gom cụm là một ví dụ về phương pháp học không được giám sát. Trong phân lớp dữ liệu, bản ghi thuộc về lớp nào là phải xác định trước, trong khi phân cụm không xác định trước. Trong gom cụ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, không thể biết kết quả các cụm thu được sẽ như thế nào khi bắt đầu quá trình. Sự giống nhau giữa những đối tượng được xác định bởi những hàm đánh giá sự tương tự. Thông thường những hàm định lượng như hàm đo khoảng cách, hàm xác định độ đo,… được xác định bởi những chuyên gia trong lĩnh vực chuyên môn của mình. Đa số các ứng dụng phân cụm được sử dụng trong sự phân chia thị trường, phân đoạn khách hàng, nhận dạng mẫu, phân loại trang Web,.... Với sự phân chia khách hàng vào trong từng cụm, những doanh nghiệp có thể cung cấp những dịch vụ khác 7 nhau tới từng cụm khách hàng một cách thuận lợi. Ví dụ, dựa vào các dịch vụ điện thoại mà khách hàng đăng ký sử dụng công ty viễn thông có thể xếp những khách hàng vào những cụm khác nhau. Với mỗi cụm, công ty có thể đưa ra những gói khuyến mãi phù hợp. Ngoài ra phân cụm dữ liệu có thể được sử dụng như một bước tiền xử lý cho các thuật toán khai phá dữ liệu khác. 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 cụm trong [16]. b. Luật kết hợp Agrawal và nhóm nghiên cứu đưa ra khái niệm luật kết hợp năm 1993 [9]. Mục tiêu của luật kết hợp là tìm ra những mối tương quan giữa những MDL thường xuyên trong CSDL. Một luật kết hợp X → Y phản ánh sự xuất hiện của tập X dẫn đến sự xuất hiện đồng thời tập Y. Luật kết hợp là dạng luật khá đơn giản nhưng lại mang nhiều ý nghĩa và thông tin mà nó mang lại hỗ trợ không nhỏ trong quá trình ra quyết định. Ví dụ 1.1 Công ty viễn thông Khánh Hòa lưu trữ một lượng rất lớn dữ liệu về việc sử dụng các dịch vụ điện thoại của khách hàng. Mỗi khách hàng có thể bao gồm các thông tin như: số máy, họ và tên, số chứng minh nhân dân, các dịch vụ mà khách hàng đã và đang sử dụng (Ứng tiền, Chuyển tiền, Nhạc chờ, Yahoo chat,…). Từ CSDL này người ta tìm ra mối quan hệ giữa các thuộc tính, ví dụ: Có 80% khách hàng sử dụng cả hai dịch vụ Nhạc chờ và Yahoo chat; Có 70% khách hàng sử dụng cả hai dịch vụ Yahoo chat và EZmail. Trong ví dụ trên có 2 luật kết hợp được tìm thấy là: - Có 80% khách hàng sử dụng dịch vụ Nhạc chờ thì đồng thời sử dụng dịch vụ Yahoo chat. - Có 70% khách hàng sử dụng dịch vụ Yahoo chat thì đồng thời sử dụng dịch vụ EZmail. Dựa vào những luật kết hợp được tìm thấy, công ty có thể biết được xu hướng sử dụng dịch vụ của khách hàng và từ đó có thể đưa ra những chương trình và chiến lược thu hút khách hàng phù hợp. 8 1.3. CÁC KHÁI NIỆM CƠ BẢN 1.3.1. Cơ sở dữ liệu giao tác 1.3.1.1. Định nghĩa cơ sở dữ liệu giao tác Cho I = {x1, x2, …, xn} là tập hợp các MDL. Mỗi xi∈ I gọi là một MDL hay một thuộc tính. Một tập con {xi1, xi2, …, xik} ⊆ I được gọi là một giao tác trên I. Đặt ti = {xi1, xi2, …, xik}, ti gọi là định danh của giao tác {xi1, xi2, …, xik}. Một tập hợp gồm m định danh giao tác T = {t1, t2, …, tm}, với m bất kỳ được gọi là một CSDL giao tác trên I. Mỗi tập con X ⊆ I với ǁXǁ = k được gọi là tập k-MDL hay k-thuộc tính của I (trong trường hợp không quan tâm đến số MDL của X, ta gọi tắt: X là tập MDL), mỗi tập con S ⊆ T gọi là tập định danh giao tác. Để thuận tiện trong các ví dụ, ta viết X = ABC thay cho X = {A, B, C} và S = 123 thay cho S = {t1, t2, t3}, XY thay cho X ∪ Y. 1.3.1.2. Biểu diễn cơ sở dữ liệu giao tác Ví dụ 1.2. Xét một CSDL bao gồm 9 giao tác như sau: Bảng 1.1. Cơ sở dữ liệu giao tác Giao tác Mục dữ liệu t1 A, B, E t2 B, D t3 B, C t4 A, B, D t5 A, C t6 B, C t7 A, C t8 A, B, C, E t9 A, B, C, G Để biểu diễn CSDL giao tác người ta thường dùng một ma trận nhị phân gọi là ma trận giao tác. 9 Định nghĩa ma trận giao tác: Cho một CSDL giao tác T = {t1, t2, …, tm} trên I = {x1, x2, …, xn}. Ma trận giao tác của T là ma trận M = (mij)mxnvới: 1 khi x j ∈ t i m ij =  0 khi x j ∉ t i Ví dụ 1.1 Ma trận giao tác ứng với CSDL giao tác cho ở bảng 1.1 Bảng 1.2. Ma trận giao tác A B C D E G t1 1 1 0 0 1 0 t2 0 1 0 1 0 0 t3 0 1 1 0 0 0 t4 1 1 0 1 0 0 t5 1 0 1 0 0 0 t6 0 1 1 0 0 0 t7 1 0 1 0 0 0 t8 1 1 1 0 1 0 t9 1 1 1 0 0 1 Ngoài ra, có hai cách biểu diễn tập CSDL giao tác [25]: Biểu diễn ngang: Dạng danh sách: Một CSDL là một danh sách các giao tác. Mỗi giao tác có một định danh giao tác (tid) và một danh sách các MDL trong giao tác đó (Bảng 1.3.a). Dạng vector: CSDL cũng có thể được tổ chức thành một tập các dòng, mỗi dòng lưu một định danh giao tác và một vector nhị phân biểu diễn các dữ liệu thuộc hay không thuộc giao tác đó (Bảng 1.3b). 10 Bảng 1.3. Biểu diễn ngang của CSDL giao tác (1.3a) Dạng danh sách E (1.3b) Dạng vector A B C D E G t1 1 1 0 0 1 0 t1 A B t2 B D t2 0 1 0 1 0 0 t3 B C t3 0 1 1 0 0 0 t4 A B t4 1 1 0 1 0 0 t5 A C t5 1 0 1 0 0 0 t6 B C t6 0 1 1 0 0 0 t7 A C t7 1 0 1 0 0 0 t8 A B C E t8 1 1 1 0 1 0 t9 A B C G t9 1 1 1 0 0 1 D Biểu diễn dọc: Dạng danh sách: Một CSDL là một danh sách những MDL, với mỗi MDL có một danh sách tất cả các định danh của các giao tác chứa MDL này (Bảng 1.4.a). Dạng vector: Tương tự biểu diễn ngang, với cách biểu diễn dọc CSDL cũng có thể tổ chức thành một tập các cột, mỗi cột lưu một MDL và một vector nhị phân biểu diễn các giao tác chứa hay không chứa MDL đó (Bảng 1.4 b). Bảng 1.4. Biểu diễn dọc của CSDL giao tác (1.4 a) Dạng danh sách A B C D E G t1 t1 t3 t2 t1 t9 t4 t2 t5 t4 t8 t5 t3 t7 (1.4 b) Dạng vector A B C D E G t1 1 1 0 0 1 0 t2 0 1 0 1 0 0 t6 t3 0 1 1 0 0 0 t4 t7 t4 1 1 0 1 0 0 t8 t6 t8 t5 1 0 1 0 0 0 t9 t8 t9 t6 0 1 1 0 0 0 t7 1 0 1 0 0 0 t8 1 1 1 0 1 0 t9 1 1 1 0 0 1 t9 11 1.3.1.3. Độ hỗ trợ (support) Độ hỗ trợ của một tập MDL X ⊆ I trong CSDL giao tác T, ký hiệu Supp(X) là tổng số các giao tác trong T chứa X. Supp(X) = ∥{t ∈ T | X ⊆ t}∥. Với CSDL cho ở bảng 1.1 ta có: Supp(A) = 6, Supp(B) = 7, Supp(ABC) = 2, Supp(DG) = 0. Một số tác giả [21] định nghĩa độ hỗ trợ theo công thức: Supp(X) = ‖{ ∈  |  ⊆ }‖ ‖ ‖ 1.3.1.4. Tập mục dữ liệu thường xuyên (frequent itemset) Cho S0 là một số nguyên, ta nói X là tập MDL thường xuyên theo ngưỡng S0 (gọi tắt là tập thường xuyên) nếu Supp(X) ≥ S0. Nếu X={xi} và Supp(X) ≥ S0 ta nói : xi là MDL thường xuyên theo ngưỡng S0. Với CSDL giao tác cho ở bảng 1.1 ta có:
AB, AC, BC: là các tập thường xuyên theo ngưỡng S0 = 4.
A, B, C: là các MDL thường xuyên theo ngưỡng S0 = 6. 1.3.1.5. Luật kết hợp (Association rule) Một luật kết hợp trên CSDL giao tác T là một biểu thức có dạng X → Y, với X, Y ⊆ I và X ∩ Y = φ. Độ hỗ trợ của luật kết hợp X → Y, được định nghĩa và ký hiệu: Supp(X → Y) = Supp(XY). Với CSDL giao tác cho ở bảng 1.1 ta có: Supp(A → B) = Supp(AB) = 4, Supp(AB → C) = Supp(ABC) = 2, Supp(AB → E) = Supp(ABE) = 2, Supp(BC → E) = Supp(BCE) = 1. Luật kết hợp f: X → Y trên T là luật thường xuyên theo ngưỡng S0 nếu Supp(X → Y) ≥ S0. Với CSDL giao tác cho ở bảng 1.1 ta có: f: A → B là luật thường xuyên theo ngưỡng S0 = 4 vì Supp(AB) = 4≥ 4 f: AB→C không là luật thường xuyên theo ngưỡng S0 = 4 vì Supp(ABC)= 2<4 12