Tài liệu Nghiên cứu tập mục thường xuyên và luật kết hợp

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐH CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG ------------------- LÊ VĂN SƠN NGHIÊN CỨU TẬP MỤC THƯỜNG XUYÊN VÀ LUẬT KẾT HỢP LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH Chuyên ngành : Khoa học máy tính Mã số : 60 48 01 Thái Nguyên, năm 2011 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 i MỤC LỤC Trang MỞ ĐẦU..................................................................................................................1 Chƣơng 1: TỔNG QUAN VỀ PHÁ DỮ LIỆU......................................................3 1.1. Khai phá dữ liệu. .................................................................................... 3 1.2. Các phƣơng pháp chính trong khai phá dữ liệu ..................................... 4 1.3. Các cơ sở dữ liệu có thể khai phá .......................................................... 5 1.4. Quá trình khai phá dữ liệu...................................................................... 6 1.5. Một số ứng dụng của khai phá dữ liệu ................................................... 7 1.6. Khai phá dữ liệu và các lĩnh vực có liên quan ....................................... 8 1.7. Những khó khăn, thách thức trong khai phá dữ liệu. ............................. 9 Chƣơng 2: TẬP MỤC THƢỜNG XUYÊN VÀ LUẬT KẾT HỢP TRONG KHAI PHÁ DỮ LIỆU...........................................................................................12 2.1. Các khái niệm cơ bản ........................................................................... 12 2.1.1. Cơ sở dữ liệu giao tác.................................................................... 12 2.1.2. Tập mục và độ hỗ trợ .................................................................... 14 2.1.3. Tập mục thƣờng xuyên (Frequent intemset) ................................. 14 2.1.4. Luật kết hợp (Association Rule) ................................................... 15 2.2. Khai phá tập mục thƣờng xuyên và mở rộng ....................................... 16 2.2.1. Khai phá tập mục thƣờng xuyên ................................................... 16 2.2.2. Mở rộng bài toán khai phá tập mục thƣờng xuyên ....................... 17 2.3. Khai phá luật kết hợp ........................................................................... 18 2.4. Một số tính chất của tập mục thƣờng xuyên và luật kết hợp ............... 20 2.4.1. Một số tính chất của tập mục thƣờng xuyên ................................. 20 2.4.2. Một số tính chất của luật kết hợp. ................................................. 20 2.5. Một số hƣớng tiếp cận trong khai phá luật kết hợp ............................. 21 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 ii CHƢƠNG 3: MỘT SỐ PHƢƠNG PHÁP KHAI PHÁ DỮ LIỆU BẰNG LUẬT KẾT HỢP...............................................................................................................23 3.1. Mở đầu ................................................................................................. 23 3.2. Thuật toán APRIORI khai phá tập mục thƣờng xuyên ........................ 24 3.3. Khai phá tập mục thƣờng xuyên theo hƣớng tiếp cận không sinh ứng cử. ................................................................................................................ 30 3.3.1. Thuật toán tạo cây FP-tree [4]....................................................... 31 3.3.2. Duyệt cây FP-tree để sinh các tập mục thƣờng xuyên.................. 40 3.4. Khai phá tập mục cổ phần cao ............................................................. 43 3.5. Thuật toán FSM.................................................................................... 47 3.5.1. Cơ sở lý thuyết của thuật toán FSM.............................................. 47 3.5.2 Thuật toán FSM.............................................................................. 48 3.6. Thuật toán AFSM ................................................................................. 52 3.6.1 Cơ sở lý thuyết của thuật toán AFSM ............................................ 52 3.6.2 Thuật toán AFSM ........................................................................... 55 Chƣơng 4: XÂY DỰNG ỨNG DỤNG KHAI PHÁ TẬP MỤC CỔ PHẦN CAO - THỬ NGHIỆM TRÊN CSDL BÁN HÀNG......................................................59 4.1. Đặt bài toán .......................................................................................... 59 4.2. Thiết kế modul chƣơng trình và giải thuật ........................................... 59 4.3. Giao diện sử dụng và chức năng chƣơng trình .................................... 60 4.4. Đánh giá kết quả và hƣớng phát triển của chƣơng trình. ..................... 63 KẾT LUẬN............................................................................................................64 TÀI LIỆU THAM KHẢO.....................................................................................65 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 iii DANH MỤC CÁC KÝ HIỆU VÀ CÁC TỪ VIẾT TẮT Từ hoặc cụm từ Từ viết tắt Tiếng Anh Khai phá tri thức KDD Knowledge Discovery in Database Khai phá dữ liệu KPDL Data Mining Cơ sở dữ liệu CSDL Database 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 iv DANH MỤC CÁC BẢNG Bảng 2.1: Biểu diễn ngang của cơ sở dữ liệu giao tác.........................................15 Bảng 2.2: Biểu diễn dọc của cơ sử dữ liệu giao tác.............................................15 Bảng 2.3: Ma trận giao tác của cơ sở dữ liệu bảng 2.1........................................16 Bảng 2.4: Các tập mục thƣờng xuyên của CSDL bảng 2.3 với minsup=50%....17 Bảng 2.5: Các luật kết hợp sinh ra từ tập mục thƣờng xuyên BCE....................21 Bảng 3.1: Ký hiệu mô tả trong thuật toán Apriori................................................26 Bảng 3.2: CSDL minh hoạ thuật toán Apriori......................................................29 Bảng 3.3: Danh sách các tập mục thƣờng xuyên của CSDL bảng 3.2................31 Bảng 3.4: CSDL giao tác minh hoạ xây dựng cây FP-tree..................................35 Bảng 3.5: Thống kê tần xuất của các mục trong CSDL.......................................35 Bảng 3.6: CSDL giao tác sau khi loại bỏ các mục không thƣờng xuyên và sắp xếp các mục theo thứ tự giảm dần của tần xuất....................................................37 Bảng 3.7: Cơ sở dữ liệu ví dụ...............................................................................46 Bảng 3.8: Giá trị lmv và cổ phần của các mục dữ liệu trong CSDL bảng 3.7.....47 Bảng 3.9: Các tập mục cổ phần cao của CSDL bảng 3.7....................................47 Bảng 3.10: Cơ sở dữ liệu minh hoạ thuật toán FSM............................................52 Bảng 3.11: Giá trị lmv và CF với k =1.................................................................52 Bảng 3.12: Giá trị lmv và CF với k = 2................................................................52 Bảng 3.13: Giá trị lmv và CF với k = 3................................................................53 Bảng 3.14: Giá trị lmv và CF với k=4..................................................................53 Bảng 3.15: Các giá trị lmv và hàm tới hạn với k=2..............................................58 Bảng 3.16: Các giá trị lmv và hàm tới hạn với k=3..............................................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 v DANH MỤC CÁC HÌNH Hình 1.1: Quá trình khai phá dữ liệu......................................................................9 Hình 1.2: Khai phá dữ liệu và các lĩnh vực có liên quan.....................................11 Hình 2.1: Phân loại các thuật toán khai phá tập mục thƣờng xuyên...................19 Hình 3.1: Bảng Header của cây FP-tree của CSDL bảng 3.5..............................36 Hình 3.2: Cây FP-tree sau khi xét giao tác với TID = T01..................................37 Hình 3.3: Cây FP-tree sau khi xét giao tác với TID = T02..................................37 Hình 3.4: Cây FP-tree sau khi xét giao tác với TID = T03..................................38 Hình 3.5: Cây FP-tree sau khi xét giao tác với TID = T04..................................38 Hình 3.6: Cây FP-tree sau khi xét giao tác với TID = T05..................................39 Hình 3.7: Cây FP-tree sau khi xét giao tác với TID = T06..................................39 Hình 3.8: Cây FP-tree sau khi xét giao tác với TID = T07..................................40 Hình 3.9: Cây FP-tree sau khi xét giao tác với TID = T08..................................40 Hình 3.10: Cây FP-tree sau khi xét giao tác với TID = T09................................41 Hình 3.11: Cây FP-tree CSDL bảng 3.4...............................................................42 Hình 3.12: Không gian tìm kiếm tập mục cổ phần cao theo thuật toán AFSM..59 Hình 4.1: Cửa sổ giao diện chƣơng trình.............................................................61 Hình 4.2: Cửa sổ thực hiện nhập CSDL...............................................................62 Hình 4.3: Nhập ngƣỡng cổ phần minShare..........................................................63 Hình 4.4: Cửa sổ thể hiện các bƣớc tìm tập mục cổ phần cao.............................64 Hình 4.5: Cửa sổ hiển thị kết quả tìm tập mục cổ phần cao................................64 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 1 MỞ ĐẦU Sự phát triển nhanh chóng của các ứng dụng Công nghệ thông tin và Internet vào nhiều lĩnh vực đời sống xã hội nhƣ quản lý kinh tế, quản lý nhân sự, khoa học kỹ thuật…đã mở ra nhiều cơ hội cho các tổ chức, doanh nghiệp trong việc thu thập và xử lý thông tin. Hơn nữa các công nghệ lƣu trữ, phục hồi dữ liệu phát triển một cách nhanh chóng, làm xuất hiện nhiều cơ sở dữ liệu khổng lồ. Để khai thác có hiệu quả nguồn thông tin từ các cơ sở dữ liệu khổng lồ trên, yêu cầu cấp thiết đặt ra là cần phải có những kỹ thuật, công cụ để chuyển đổi kho dữ liệu khổng lồ thành những tri thức có ích. Từ đó các kỹ thuật Khai phá dữ liệu trở thành một lĩnh vực đƣợc đặc biệt quan tâm trong ngành Công nghệ thông tin. Khai phá dữ liệu là một khái niệm đƣợc ra đời vào những năm cuối của thập kỷ 1980, là quá trình khám phá thông tin ẩn đƣợc tìm thấy trong các cơ sở dữ liệu và đƣợc ứng dụng một cách rộng rãi trong nhiều lĩnh vực khác nhau nhƣ: marketing, tài chính, ngân hàng và bảo hiểm, khoa học, y tế, an ninh, internet…Rất nhiều tổ chức và công ty lớn trên thế giới đã áp dụng kỹ thuật khai phá dữ liệu vào các hoạt động sản xuất kinh doanh của mình và đã thu đƣợc những lợi ích to lớn. Một trong các nội dung cơ bản và phổ biến nhất trong khai phá dữ liệu là tìm các tập mục thƣờng xuyên từ đó 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. Đồng thời mở rộng khai phá tập mục thƣờng xuyên là khai phá tập mục cổ phần cao để có thể đánh giá đƣợc sự đóng góp của tập mục trong tổng số các mục dữ liệu của cơ sở 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 2 Từ những lý do trên tôi chọn đề tài “Nghiên cứu tập mục thường xuyên và luật kết hợp”. Luận văn đƣợc xây dựng dựa trên một số nghiên cứu trong lĩnh vực khai phá tập mục thƣờng xuyên và luật kết hợp trong những năm gần đây. Luận văn đƣợc tổ chức thành 04 chƣơng Chƣơng 1. Tổng quan về khai phá dữ liệu Chƣơng 2. Tập mục thƣờng xuyên và luật kết hợp trong khai phá dữ liệu Chƣơng 3: Một số phƣơng pháp khai phá dữ liệu bằng luật kết hợp Chƣơng 4. Xây dựng ứng dụng khai phá tập mục cổ phần cao-ứng dụng thử nghiệm trên CSDL bán hàng Kết luậ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 3 Chƣơng 1: TỔNG QUAN VỀ PHÁ DỮ LIỆU 1.1. Khai phá dữ liệu. Trong kỷ nguyên bùng nổ công nghệ thông tin, các công nghệ lƣu trữ dữ liệu ngày càng phát triển tạo điều kiện cho việc thu thập, lƣu trữ dữ liệu tốt hơn. Đặc biệt trong lĩnh vực kinh doanh, các doanh nghiệp đã nhận thức đƣợc tầm quan trọng của việc nắm bắt và xử lý thông tin, nhằm giúp các chủ doanh nghiệp trong việc vạch ra các chiến lƣợc kinh doanh, kịp thời mang lại lợi nhuận to lớn. Từ đó khiến các tổ chức, doanh nghiệp tạo ra một lƣợng dữ liệu khổng lồ cho riêng mình. Các kho dữ liệu ngày càng lớn trong đó tiềm ẩn nhiều thông tin có ích. Để khai thác có hiệu quả nguồn thông tin từ các kho dữ liệu khổng lồ dẫn tới một yêu cầu cấp thiết là phải có những kỹ thuật và công cụ mới để biến kho dữ liệu khổng lồ thành những thông tin cô đọng và có ích. Kỹ thuật Khai phá dữ liệu (Data mining) ra đời nhƣ một kết quả tất yếu đáp ứng yêu cầu đó. Khai phá dữ liệu (Data mining) là quá trình trích xuất các thông tin có giá trị tiềm ẩn bên trong lƣợng lớn dữ liệu đƣợc lƣu trữ trong các cơ sở dữ liệu, kho dữ liệu. Hiện nay, ngoài thuật ngữ khai phá dữ liệu ngƣời ta còn dùng một số thuật ngữ khác có ý nghĩa tƣơng tự nhƣ: Khai phá tri thức từ CSDL (Knowledge mining from databases), trích lọc dữ liệu (Knowledge extraction), phân tích dữ liệu/mẫu (data/pattern analysis), khảo cổ dữ liệu (data archaeology), nạo vét dữ liệu (data dredging). Nhiều ngƣời coi khai phá dữ liệu và một thuật ngữ thông dụng khác là khám phá tri thức trong CSDL (Knowledge Discovery in Databases –KDD) là nhƣ nhau. Thực tế khai phá dữ liệu chỉ là một bƣớc thiết yếu trong quá trình khám phá tri thức trong CSDL. 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 Theo Giáo sƣ Tom Mitchell [11] định nghĩa KPDL: “KPDL là việc sử dụng dữ liệu lịch sử để khám phá những qui tắc và cải thiện những quyết định trong tƣơng lai” Tóm lại: Khai phá dữ liệu là một quá trình tìm kiếm, phát hiện ra các tri thức mới và các tri thức có ích ở dạng tiềm ẩn trong các cơ sở dữ liệu lớn. 1.2. Các phƣơng pháp chính trong khai phá dữ liệu Các phƣơng pháp chính trong KPDL có thể đƣợc phân chia theo chức năng hay lớp các bài toán khác nhau [7] nhƣ sau: - Phân lớp và dự đoán (classicfication and 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 các bệnh nhân theo dữ liệu trong hồ sơ bệnh án. Hƣớng tiếp cận này thƣờng sử dụng các kỹ thuật nhƣ học máy (Machine learning), cây quyết định (Decision tree), mạng nơ ron nhân tạo (Neural network)...Với phƣơng pháp này còn đƣợc gọi là học có giám sát. - 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. Mục tiêu của phƣơng pháp này là phát hiện và đƣa ra các mối liên hệ giữa các giá trị dữ liệu trong cơ sở dữ liệu. Luật kết hợp đƣợc ứng dụng nhiều trong lĩnh vực kinh doanh, y học, tin – sinh học, tài chính, thị trƣờng chứng khoán... - Khai phá chuỗi theo thời gian (Sequential temporal patterns): Tƣơng tự nhƣ khai phá dữ liệu bằng 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 bởi vì chúng có tính dự báo cao. - Phân cụm và phân đoạn (Clusterring and Segmentation): Sắp xếp các đối tƣợng theo từng cụm dữ liệu tự nhiên (số lƣợng và tên của cụm chƣa đƣợc biết trƣớc). Các đối tƣợng đƣợc gom cụm sao cho mức độ tƣơng tự giữa các đối tƣợng trong cùng một cụm là lớn nhất và mức độ tƣơng tự giữa cá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 đối tƣợng nằm trong các cụm khác nhau là nhỏ nhất. Lớp bài toán phân cụm còn đƣợc gọi là học không giám sát (Unsupervised learning). - Mô tả khái niệm và tổng hợp hóa (Concept description and summarization): Liên quan đến các phƣơng pháp tìm kiếm một mô tả cho một tập con dữ liệu. Các kỹ thuật tóm tắt thƣờng đƣợc áp dụng cho các phân tích dữ liệu tƣơng tác có tính thăm dò và tạo báo cáo tự động. 1.3. Các cơ sở dữ liệu có thể khai phá KPDL đƣợc ứng dụng rộng rãi nên có rất nhiều dạng dữ liệu khác nhau có thể khai phá [7]. Sau đây là một số dữ liệu điển hình: - Cơ sở dữ liệu quan hệ (Relational databases): Là cơ sở dữ liệu tác nghiệp đƣợc tổ chức theo mô hình quan hệ, có cấu trúc cao, dữ liệu đƣợc mô tả bởi một tập những thuộc tính và lƣu trong những bảng. Khai phá dữ liệu trên cơ sở dữ liệu quan hệ chủ yếu tập trung khai phá mẫu. Hầu hết các hệ quản trị CSDL hiện nay đều hỗ trợ dạng CSDL này nhƣ SQL Server, Oracle, DB2, MySQL, MS Access... [2] - Cơ sở dữ liệu giao tác (Transaction databases): Cơ sở dữ liệu giao tác là tập hợp những bản ghi giao dịch, trong đa số các trƣờng hợp chúng là những bản ghi các dữ liệu hoạt động của doanh nghiệp, tổ chức. Với tính phổ biến của máy tính và thƣơng mại điện tử, ngày nay có rất nhiều cơ sở dữ liệu giao tác. Khai phá dữ liệu trên cơ sở dữ liệu giao tác tập trung vào khai phá luật kết hợp, tìm mối tƣơng quan giữa những mục dữ liệu của bản ghi giao dịch. - CSDL đa chiều (Multidimentional structures, data warehouses, data smart): Là các kho dữ liệu đƣợc tập hợp, chọn lọc từ nhiều nguồn khác nhau. CSDL đa chiều có mang tính lịch sử (mang tính thời gian) và chủ yếu phục vụ cho quá trình phân tích cũng nhƣ khai phá tri thức nhằm hỗ trợ quá trình ra 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 6 - CSDL hướng đối tượng (Object databases): Dữ liệu cũng đƣợc lƣu trữ trong các bảng dữ liệu nhƣng các bảng có bổ sung thêm các tính năng hƣớng đối tƣợng nhƣ lƣu trữ thêm các hành vi, nhằm thể hiện hành vi của đối tƣợng. Mỗi bảng xem nhƣ một lớp dữ liệu, một dòng dữ liệu trong bảng là một đối tƣợng. Các hệ quản trị có hỗ trợ cơ sở dữ liệu quan hệ nhƣ: MS SQL server, Oracle, Postgres... - CSDL không gian (Spatial databases): Bao gồm hai phần: Phần thứ nhất là dữ liệu quan hệ hay giao tác, phần thứ hai là thông tin định vị hoặc thông tin địa lý. Những luật kết hợp trên cơ sở dữ liệu không gian mô tả mối quan hệ giữa các đặc trƣng trong cơ sở dữ liệu không gian. Dạng của luật kết hợp không gian có dạng X  Y, với X, Y là tập hợp những vị từ không gian. Những thuật toán khai phá luật kết hợp không gian tƣơng tự nhƣ khai phá luật kết hợp nhƣng thêm những vị từ về không gian. - CSDL có yếu tố thời gian (Time – series databases): Giống nhƣ cơ sở dữ liệu không gian, cơ sở dữ liệu có yếu tố thời gian bao gồm hai phần: Phần thứ nhất là dữ liệu quan hệ hay giao tác, phần thứ hai là thông tin về thời gian xuất hiện dữ liệu ở phần thứ nhất. Những luật kết hợp có yếu tố thời gian có nhiều thông tin hơn những luật kết hợp cơ bản. - CSDL đa phương tiện (Multimedia databases): CSDL đƣợc tích hợp gồm nhiều dạng khác nhau nhƣ: âm thanh, hình ảnh, văn bản. 1.4. Quá trình khai phá dữ liệu. - Trích chọn dữ liệu: Là bƣớc trích chọn những tập dữ liệu cần đƣợc khai phá từ các tập dữ liệu lớn. - Tiền xử lý dữ liệu: Là bƣớc làm sạch dữ liệu (xử lý với dữ liệu không đầy đủ, dữ liệu nhiễu, dữ liệu không nhất quán...), rút gọn dữ liệu (sử dụng hàm nhóm và tính tổng, các phƣơng pháp nén dữ liệu, sử dụng histogram, lấy mẫu,...), rời rạc hoá dữ liệu (rời rạc hoá dựa vào histogram, dựa vào entropy, 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 dựa vào phân khoảng,...). Sau bƣớc này, dữ liệu sẽ nhất quán, đầy đủ, đƣợc rút gọn và đƣợc rời rạc hoá. - Biến đổi dữ liệu: Là bƣớc chuẩn hoá và làm mềm dữ liệu để đƣa dữ liệu về dạng thuận lợi nhất nhằm phục vụ cho các kỹ thuật khai phá tiếp theo. - Thuật toán khai phá dữ liệu: Lựa chọn các thuật toán khai phá dữ liệu cho phù hợp hiệu quả với yêu cầu để tiến hành khai phá tìm ra các mẫu. - Đánh giá và biểu diễn tri thức: Những mẫu thông tin và mối liên hệ trong dữ liệu đã đƣợc khám phá ở bƣớc trên đƣợc chuyển dạng và biểu diễn ở một dạng gần gũi với ngƣời sử dụng nhƣ đồ thị, luật kết hợp, cây quyết định,...Đồng thời bƣớc này cũng đánh giá những tri thức khám phá đƣợc theo những tiêu chí nhất định. Quá trình khai phá dữ liệu đƣợc mô tả theo sơ đồ sau: Dữ liệu thô Tri thức Trích chọn dữ liệu Biến đổi dữ liệu Tiền xử lý dữ liệu Thuật toán khai phá dữ liệu Đánh giá, giải thích Hình 1.1: Quá trình khai phá dữ liệu 1.5. Một số ứng dụng của khai phá dữ liệu KPDL là một lĩnh vực quan trọng của ngành Công nghệ thông tin. Đây là lĩnh vực đã thu hút đông đảo các nhà khoa học trong nƣớc và trên thế giới tham gia nghiên cứu, nhờ vào những ứng dụng thực tiễn của nó. Sau đây là một số hƣớng nghiên cứu và ứng dụng điển hình hiện nay: - Phân tích dữ liệu và hỗ trợ quyết định (Data analysis & decision support) 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 - Điều trị trong y học (Medical treatment): Mối liên hệ giữa triệu chứng, chuẩn đoán và phƣơng pháp điều trị. - Phân lớp, tóm tắt văn bản và phân lớp các trang Web (Text ming & Web mining) - Tin - sinh (Bio - Informatics): Tìm kiếm, đối sánh các hệ gene và thông tin di truyền, mối liên hệ giữa một số hệ gene và một số bệnh di truyền... - Nhận dạng. - Tài chính và thị trƣờng chứng khoán (Finance & stock market): Phân tích tình hình tài chính và dự đoán giá cổ phiếu. - Bảo hiểm (Insurance) - Giáo dục (Education) 1.6. Khai phá dữ liệu và các lĩnh vực có liên quan Khai phá dữ liệu đƣợc coi là trung tâm của nhiều ngành khoa học, nó liên quan đến rất nhiều ngành, nhiều lĩnh vực khác nhau nhƣ tài chính, ngân hàng, thƣơng mại, y tế, giáo dục, thống kê, máy móc, trí tuệ nhân tạo, cơ sở dữ liệu, thuật toán, tính toán song song, thu nhận tri thức trong các hệ chuyên gia, quan sát dữ liệu. Lĩnh vực học máy và nhận dạng mẫu là giống nhau trong khai phá dữ liệu nghiên cứu các lý thuyết và thuật toán của hệ thống trích ra các mẫu và mô hình dữ liệu. Khai phá dữ liệu tập trung vào việc mở rộng lý thuyết và thuật toán cho các vấn đề về tìm ra các mẫu đặc biệt, đây đƣợc coi là những mẫu hữu ích hoặc tri thức quan trọng tập dữ liệu lớn. Đặ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…, kho dữ liệu và các công cụ xử lý trực tuyến (OLAP – online analytical processing) tập trung vào phân tích dữ liệu đa chiều, tốt hơn SQL 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 trong tính toán và phân tích thống kê đa chiều cũng liên quan chặt chẽ đến khai phá dữ liệu. Khai phá dữ liệu và các lĩnh vực có liên quan đƣợc mô tả nhƣ sau: Thống kê Cơ sở dữ liệu Thƣơng mại Khai phá dữ liệu Máy móc, trí tuệ nhân tạo Tài chính, ngân hàng Y tế Giáo dục Các ngành khoa học khác Thuật toán Hình 1.2: Khai phá dữ liệu và các lĩnh vực có liên quan Đặc trƣng của hệ thống khai phá dữ liệu là nhờ vào các phƣơng pháp thuật toán và kỹ thuật từ những lĩnh vực khác nhau, với mục đích cuối cùng là trích rút ra tri thức có ích trong CSDL khổng lồ. 1.7. Những khó khăn, thách thức trong khai phá dữ liệu. Khai phá dữ liệu có vai trò quan trọng trong việc tìm ra các tri thức có ích tiềm ẩn trong các kho dữ liệu khổng lồ mà hàng ngày đang đƣợc thu thập, lƣu trữ để giúp các cá nhân, tổ chức đƣa ra đƣợc các quyết định, chính xác và nhanh chóng. Tuy đã có rất nhiều các giải pháp và phƣơng pháp đƣợc ứng dụng trong khai phá dữ liệu, nhƣng trong thực tế quá trình này vẫn gặp không ít những khó khăn và thách thức nhƣ: - Cơ sở dữ liệu lớn - Số chiều các thuộc tính lớn - Thay đổi dữ liệu và tri thức có thể làm cho các mẫu đã phát hiện không còn phù hợp - Dữ liệu bị thiếu hoặc bị nhiễ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 10 - Quan hệ giữa các trƣờng phức tạp Cơ sở dữ liệu lớn có thể lớn về số lƣợng các bản ghi, lớn về số lƣợng các thuộc tính trong CSDL. Số lƣợng các bản ghi trong CSDL lớn có khi dung lƣợng tới hàng gigabyte, terabyte; số các thuộc tính trong CSDL có thể rất nhiều và đa dạng. Để giải quyết vấn đề này, ngƣời ta thƣờng đƣa ra một ngƣỡng nào đó cho CSDL bằng các cách nhƣ chiết xuất mẫu, xấp xỉ hoặc xử lý song song. Trong CSDL, khi mà số các thuộc tính là rất lớn, cùng với số lƣợng lớn các bản ghi sẽ dẫn đến kích thƣớc độ phức tạp của bài toán tăng lên. Vì vậy, không gian tìm kiếm, không gian trạng thái gia tăng, nhiều mẫu hay mô hình thừa, trùng lặp phát sinh nhiều luật thừa, đây đƣợc coi là vấn đề nan giải trong quá trình khai phá dữ liệu. Nhằm giải quyết đƣợc những vấn đề trên, phải sử dụng một số các tri thức đã biết trƣớc để loại bỏ và trích lọc ra những dữ liệu thích hợp với yêu cầu của bài toán. Dữ liệu bị thay đổi phụ thuộc theo thời gian, nghĩa là dữ liệu bị ảnh hƣởng và phụ thuộc vào thời điểm quan sát, lấy mẫu thời điểm khai phá. Kết quả đạt đƣợc sau khai phá cũng gây không ít khó khăn cho khai phá dữ liệu, nhƣ các mẫu đƣợc khai phá ở bƣớc trƣớc, có thể không còn giá trị hay vô nghĩa đối với thời điểm sử dụng hoặc có thể làm nhiễu hay phát sinh hiệu ứng phụ làm sai lệch kết quả. Để khắc phục đƣợc vấn đề này cần phải chuẩn hóa, cải tiến, nâng cấp các mẫu, các mô hình và có thể xem các thay đổi này là mục đích của khai phá và tìm kiếm các mẫu bị thay đổi. Thuộc tính không phù hợp, các bộ giá trị không đầy đủ, bị thiếu giá trị trong các miền thuộc tính đã làm ảnh hƣởng rất lớn trong khai phá dữ liệu. Trong quá trình khai phá dữ liệu, khi các hệ thống tƣơng tác với nhau phụ thuộc nhau mà thiếu vắng một vài giá trị nào đó, sẽ dẫn đến các mẫu không đƣợc chính xác, bị thiếu, không đầy đủ. Để giải quyết cho vấn đề này, ngƣờ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 11 ta coi sự thiếu vắng của các dữ liệu này là giá trị ẩn, chƣa biết và có thể đƣợc tiên đoán bằng một số phƣơng pháp nào đó. Quan hệ phức tạp giữa các thuộc tính trong CSDL cũng là vấn đề cần đƣợc quan tâm. Những bộ thuộc tính có cấu trúc, phân lớp phức tạp, có mối liên hệ phức tạp với nhau trong CSDL đòi hỏi khai phá dữ liệu phải có các giải pháp, các kỹ thuật để có thể áp dụng đƣợc, nhận ra đƣợc các mối quan hệ này trong quá trình khai phá 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 12 Chƣơng 2: TẬP MỤC THƢỜNG XUYÊN VÀ LUẬT KẾT HỢP TRONG KHAI PHÁ DỮ LIỆU 2.1. Các khái niệm cơ bản Khai phá luật kết hợp là một kỹ thuật quan trọng của khai phá dữ liệu. Mục tiêu khai phá là phát hiện những mối quan hệ giữa các giá trị dữ liệu trong cơ sở dữ liệu. Mô hình đầu tiên của bài toán khai phá luật kết hợp là mô hình nhị phân hay còn gọi là mô hình cơ bản đƣợc R.Agrawal, T.Imielinski và A.Swami đề xuất vào năm 1993, phân tích cơ sở dữ liệu giao tác, phát hiện các mối quan hệ giữa các tập mục hàng hoá đã bán đƣợc tại các siêu thị. Từ đó có kế hoạch bố trí, sắp xếp, kinh doanh hợp lý những mặt hàng tại các quầy, đồng thời tổ chức sắp xếp các quầy gần nhau nhƣ thế nào để có doanh thu trong các phiên giao dịch là lớn nhất. Ngoài ra, có thể áp dụng tri thức này để dự đoán số lƣợng các mặt hàng đƣợc bán chạy nhất trong thời gian sắp tới. Tổng hợp các tri thức này để lên kế hoạch cho hoạt động, sản xuất, kinh doanh một cách thuận tiện hơn nhằm giảm bớt thời gian thống kê, tìm hiểu thị trƣờng,... Sau đây là một số khái niệm cơ bản của bài toán khai phá tập mục thƣờng xuyên và luật kết hợp. 2.1.1. Cơ sở dữ liệu giao tác Định nghĩa: Cho tập các mục (item) I = {i 1, i2, ..., in}. Một giao tác (transaction) T là một tập con của I, T I. Cơ sở dữ liệu giao tác là một tập các giao tác DB = {T1, T2, ..., Tm}. Mỗi giao tác đƣợc gán một định danh TID. Một tập mục con X  I, gồm k mục phân biệt đƣợc gọi là một k – tập mục. Giao tác T gọi là chứa tập mục X nếu XT. - Biểu diễn cơ sở dữ liệu giao tác: Thƣờng đƣợc biểu diễn ở dạng biểu diễn ngang, biểu diễn dọc và biểu diễn bởi ma trận giao tá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 13 + Biểu diễn ngang: Cơ sở dữ liệu là một danh sách các giao tác. Mỗi giao tác có một định danh TID và một danh sách các mục dữ liệu trong giao tác đó. Ví dụ: TID Transaction T01 {A, C, D} T02 {B, C, E} T03 {A, B, C, E} T04 {B, E} Bảng 2.1: Biểu diễn ngang của cơ sở dữ liệu giao tác + Biểu diễn dọc: Cơ sở dữ liệu là một danh sách các mục dữ liệu, mỗi mục dữ liệu có một danh sách tất cả các định danh của các giao tác chứa mục dữ liệu. Ví dụ: Transaction TID A T01, T03 B T02, T03, T04 C T01, T02, T03 D T01 E T02, T03, T04 Bảng 2.2: Biểu diễn dọc của cơ sử dữ liệu giao tác + Ma trận giao tác: Cơ sở dữ liệu giao tác DB = {T1, T2, ..., Tm} trên các tập mục (item) I = {i1, i2, ..., in} đƣợc biểu diễn bởi ma trận nhị phân M = (mpq)mxn ở đó: mpq = 1 khi iq  Tp 0 khi iq  Tp 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 14 Ví dụ: Cơ sở dữ liệu bảng 2.1 biểu diễn ở dạng ma trận giao tác là: TID A B C D E T01 1 0 1 1 0 T02 0 1 1 0 1 T03 1 1 1 0 1 T04 0 1 0 0 1 Bảng 2.3: Ma trận giao tác của cơ sở dữ liệu bảng 2.1 2.1.2. Tập mục và độ hỗ trợ - Tập mục: Tập X, XI đƣợc gọi là tập mục (itemset) - Độ hỗ trợ (Support) của tập mục X trong CSDL giao tác DB đƣợc ký hiệu sup(X): Là tỷ lệ phần trăm số giao tác trong CSDL có chứa X trên tổng số các giao tác trong DB: sup( X )  | {t  DB | X  t} | *100% | DB | Ta có 0 ≤ sup(X) ≤ 1 với mọi tập mục X  I Ví dụ: Bảng CSDL 2.3, cho tập mục X = ABC, ta có - Số giao tác chứa tập mục X ={A,B,C} là 1 - Số giao tác trong CSDL là 4 Vậy sup( X )  1 *100%  25% 4 2.1.3. Tập mục thường xuyên (Frequent intemset) Tập mục X đƣợc gọi là tập mục thƣờng xuyên với độ hỗ trợ minsup. Với minsup là giá trị cho trƣớc đƣợc xác định bởi ngƣời sử dụng. Nếu độ hỗ trợ của nó lớn hơn hoặc bằng minsup tức là: s(X) ≥ minsup Bảng liệt kê các tập mục thƣờng xuyên (frequent-itemset) trong CSDL bảng 2.3 với giá trị minsup = 50% 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