Tài liệu Nghiên cứu chung về khai phá dữ liệu

MỤC LỤC MỞ ĐẦU............................................................................................................2 NỘI DUNG ĐỀ TÀI GỒM ...............................................................................3 CHƯƠNG I: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU..............................3 CHƯƠNG II: KHAI PHA DỮ LIỆU BẰNG LUẬT KẾT HỢP.................3 CHƯƠNG III: ỨNG DỤNG LUẬT KẾT HỢP TRONG BÀI TOÁN DỮ LIỆU MÔ PHỎNG GIAO DỊCH BÁN HÀNG TRONG SIÊU THỊ TÔN MÙI................................................................................................................3 CHƯƠNG I: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU..................................4 1.1. Khái niệm cơ bản....................................................................................4 1.1.1. Mục tiêu của khai phá dữ liệu............................................................4 1.1.2. Định nghĩa khai phá dữ liệu...............................................................5 1.1.3. Các dạng dữ liệu có thể khai phá. ......................................................5 1.1.4. Quá trình khai phá dữ liệu .................................................................6 1.1.5. Các hướng tiếp cận cơ bản và kỹ thuật áp dụng. ...............................8 1.1.6. Các lĩnh vực ứng dụng của khai phá dữ liệu ......................................8 1.2. Phương pháp khai phá dữ liệu...............................................................9 1.2.1. Một số phương pháp khai phá dữ liệu phổ biến .................................9 1.2.2. Lựa chọn các kỹ thuật khai phá .......................................................14 CHƯƠNG II: KHAI PHÁ DỮ LIỆU BẰNG LUẬT KẾT HỢP...................16 2.1. Ý nghĩa của luật kết hợp .....................................................................16 2.2. Bài toán khai phá dữ liệu bằng luật kết hợp. ...........................................17 2.2.1. Phát biểu bài toán và các pha thực hiện. ..........................................17 2.2.2. Ví dụ ...............................................................................................20 2.3. Một số tính chất của tập mục phổ biến và luật kết hợp......................22 2.3.1. Một số tính chất với tập mục phổ biến:............................................22 2.3.2. Một số tính chất với luật kết hợp: ....................................................23 2.3.3. Các loại luật kết hợp........................................................................24 2.4. Các thuật toán khai phá dữ liệu nhờ luật kết hợp. .............................26 2.4.1. Khai phá luật kết hợp Boolean đơn chiều từ cơ sở dữ liệu tác vụ .....26 2.4.2. Khai phá luật kết hợp định lượng....................................................52 2.4.3. Khai phá luật kết hợp đa mức. .........................................................55 CHƯƠNG III: ỨNG DỤNG THỬ NGHIỆM CHO BÀI TOÁN KHAI PHÁ LUẬT KẾT HỢP TRÊN CƠ SỞ DỮ LIỆU NHỊ PHÂN...............................61 3.1 Đặt bài toán .............................................................................................61 3.2 Thiết kế giao diện sử dụng.......................................................................62 3.3 Đánh giá kết quả và hướng phát triển của chương trình. ..........................64 TÀI LIỆU THAM KHẢO...............................................................................65 MỞ ĐẦU Trong những năm gần đây, khai phá dữ liệu đã trở thành một trong những lĩnh vực chính được các nhà khoa học quan tâm nghiên cứu bởi tính ứng dụng cao trong thực tiễn cuộc sống. Với hàng loạt các nghiên cứu, đề xuất được thử nghiệm và ứng dụng thành công vào đời sống đã chứng minh khai phá dư liệu là lĩnh vực nghiên cứu có nền tảng lý thuyết vững chắc. Khai phá dữ liệu được ứng dụng rộng rãi trong nhiều lĩnh vực như: Tài chính và thị trường chứng khoán, Thương mại, Giáo dục, Y tế, Sinh học, Bưu chính viễn thông ... với nhiều hướng tiếp cận khác nhau như: Phân lớp/ Dự đoán, Phân cụm, Luật kết hợp, .... Các kỹ thuật chính được áp dụng trong khai phá dữ liệu phần lớn được thừa kế từ lĩnh vực: Cơ sở dữ liệu, Học máy, Trí tuệ nhân tạo, Lý thuyết thông tin, Xác suất thống kê, ... Luật kết hợp là một trong những phương pháp khai phá dữ liệu có hiệu quả và là vấn đề quan trọng được nhiều nhà khoa học tìm hiểu và đã thu được những thành công lớn. Với một lĩnh vực khoa học công nghệ mới còn nhiều triển vọng trong tương lai, em đã chọn hướng nghiên cứu về Một số phương pháp khai phá dữ liệu bằng luật kết hợp cho luận văn của mình. Luận văn được xây dựng và tổng hợp các nội dung dựa trên nền một số nghiên cứu chủ yếu trong lĩnh vực khai phá dữ liệu của các nhà nghiên cứu trong những năm gần đây ở một số hội nghị quốc tế và một số các bài báo được công bố trên các tạp chí chuyên ngành, trên Internet. 2 NỘI DUNG ĐỀ TÀI GỒM CHƯƠNG I: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU Chương này trình bày những nét khái quát nhất về khai phá dữ liệu, khai phá dữ liệu trong quá trình phát hiện tri thức; Các hướng tiếp cận; Các kỹ thuật áp dụng trong khai phá dữ liệu; Các lĩnh vực ứng dụng chính. CHƯƠNG II: KHAI PHA DỮ LIỆU BẰNG LUẬT KẾT HỢP Trong chương này trình bày các phương pháp khai phá dữ liệu bằng luật kết hợp từ thuật toán đầu tiên – Thuật toán Apriori và các hướng cải tiến của thuật toán này nhằm nâng cao hiệu quả của quá trình tính toán. Đồng thời cũng trình bày một số hướng nghiên cứu về luật kết hợp đa mức, định lượng, đóng. CHƯƠNG III: ỨNG DỤNG LUẬT KẾT HỢP TRONG BÀI TOÁN DỮ LIỆU MÔ PHỎNG GIAO DỊCH BÁN HÀNG TRONG SIÊU THỊ TÔN MÙI Chương này trình bày bài toán và qua bài toán xác định rõ nhiệm vụ khai phá dữ liệu, phân tích và thiết kế các môdul chương trình đồng thời thiết kế các giao diện sao cho thuận lợi và thân thiết với người sử dụng nhưng dễ theo dõi và kiểm tra. Chương trình được xây dựng với mục đích thử nghiệm để đánh giá kết quả. 3 CHƯƠNG I: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 1.1. Khái niệm cơ bản. 1.1.1. Mục tiêu của khai phá dữ liệu. Gần ba thập niên trở lại đây, lượng thông tin được lưu trữ trên các thiết bị như đĩa cứng, CD-ROM, băng từ, .... không ngừng tăng lên. Sự tích lũy dữ liệu này xảy ra với một tốc độ bùng nổ. Người ta ước đoán rằng, lượng thông tin trên toàn cầu tăng khoảng gấp đôi sau hai năm đồng thời theo đó số lượng cũng như kích cỡ của các cơ sở dữ liệu cũng tăng lên một cách nhanh chóng. Trong lĩnh vực kinh doanh, những nhà quản lý quả thực đang ngập trong dữ liệu nhưng lại cảm thấy thiếu tri thức và thông tin hữu ích. Lượng dữ liệu khổng lồ này thực sự đã trở thành nguồn tài nguyên rất giá trị bởi thông tin là yếu tố then chốt trong mọi hoạt động thương mại vì thông tin giúp người điều hành và nhà quản lý có cái nhìn sâu sắc, chính xác, khách quan vào tiến trình kinh doanh của doanh nghiệp trước khi ra quyết định. Việc khai thác những thông tin tiềm ẩn mang tính dự đoán từ những cơ sở dữ liệu lớn là mục tiêu chính của khai phá dữ liệu – một hướng tiếp cận mới với khả năng giúp các đơn vị, tổ chức chú trọng vào những thông tin có nhiều ý nghĩa từ những tập hợp dữ liệu lớn mang tính lịch sử. Những công cụ khai phá dữ liệu có thể dự đoán những xu hướng trong tương lai do đó cho phép các tổ chức, doanh nghiệp ra những quyết định kịp thời được định hướng bởi tri thức mà khi khai phá dữ liệu đem lại. Sự phân tích dữ liệu một cách tự động và mang tính dự báo của khai phá dữ liệu khiến nó có ưu thế hơn hẳn so với sự phân tích thông thường dựa trên những sự kiện trong quá khứ của các hệ hỗ trợ ra quyết định truyền thống trước đây. Công cụ khai phá dữ liệu cũng có thể trả lời các câu hỏi trong lĩnh vực kinh doanh mà trước đây được xem là tốn nhiều thời gian để xử lý. Với tất cả các ưu thế trên, khai phá dữ liệu đã chính tỏ được tính hữu dụng của nó trong mỗi môi trường kinh doanh đầy tính cạnh tranh ngày nay. Giờ đây khai phá dữ liệu đã và đang trở thành một trong những hướng nghiên cứu chính của lĩnh vực khoa học máy tính và công nghệ tri thức. Phạm vị ứng dụng ban đầu 4 của khai phá dữ liệu chỉ là trong lĩnh vực thương mại và tài chính. Nhưng ngày nay, khai phá dữ liệu đã được ứng dụng rộng rãi trong các lĩnh vực khác như: Tin sinh học, điều trị y học, viễn thông, giáo dục, ... 1.1.2. Định nghĩa khai phá dữ liệu. Qua những nội dung đã trình bày ở trên, chúng ta có thể hiểu một cách sơ lược rằng khai phá dữ liệu là quá trình tìm kiếm thông tin hữu ích, tiềm ẩn và mang tính dự báo trong các cơ sở dữ liệu lớn. Như vậy, nên chăng gọi quá trình này là khám phá tri thức thay vì là khai phá dữ liệu. Tuy nhiên một số nhà khoa học đồng ý với nhau rằng hai thuật ngữ trên là tương đương và có thể thay thế cho nhau. Họ lí giải rằng mục đích chính của quá trình khám phá tri thức và thông tin và tri thức có ích, nhưng đối tượng mà chúng ta phải xử lí rất nhiều trong quá trình đó lại chính là dữ liệu. Mặt khác, khi chia các bước trong khá trình khám phá tri thức, nhiều nhà khoa học khác lại cho rằng khai phá dữ liệu chỉ là một bước trong quá trình khám phá tri thức1. Như vậy, khi xét ở mức không thật chi tiết thì hai thuật ngữ này được xem là đồng nghĩa nhưng khi xét cụ thể thì khai phá dữ liệu lại là một bước trong quá trình khám phá tri thức. 1.1.3. Các dạng dữ liệu có thể khai phá. Khai phá dữ liệu được ứng dụng rộng rãi nên có rất nhiều kiểu dữ liệu khác nhau được chấp nhận để khai phá 2. Sau đây là một số loại điển hình: Cơ sở dữ liệu quan hệ (relational databases): là các cơ sở dữ liệu tác nghiệp được tổ chức theo mô hình dữ liệu quan hệ. Hầu hết các hệ quản trị cơ sở dữ liệu đều hỗ trợ dạng cơ sở dữ liệu này như: Oracle, IBM DB2, MS SQL Server, MS Access, ... Cơ sở dữ liệu đa chiều (multimensional structures, data warehouses, data mart): là các kho dữ liệu được tập hợp, chọn lọc từ nhiều nguồn dữ liệu khác nhau. Dạng dữ liệu này mang tính lịch sử (tức có tính thời gian) và chủ yếu phục vụ cho quá trình phân tích cũng như là khai phá tri thức nhằm hỗ trợ cho việc ra quyết định. 5 Cơ sở dữ liệu dạng giao dịch (transactional databases): là dạng cơ sở dữ liệu tác nghiệp nhưng các bản ghi thường là các giao dịch. Dạng dữ liệu này thường phổ biến trong lĩnh vực thương mại và ngân hàng. Cơ sở dữ liệu quan hệ – hướng đối tượng (object-relational databases): là dạng cơ sở dữ liệu lai giữa hai mô hình quan hệ và hướng đối tượng. Dữ liệu không gian và thời gian (spatial, temporal and time-series data): là dạng dữ liệu có tích hợp thuộc tính về không gian (ví dụ như dữ liệu về bản đồ) hoặc thời gian (ví dụ như dữ liệu về thị trường chứng khoán). Cơ sở dữ liệu đa phương tiện (multimedia databases): là dạng dữ liệu âm thanh (audio), hình ảnh (image), phim ảnh (video), Text & WWW,... Dạng dữ liệu này hiện đang rất phổ biến trên Internet do sự ứng dụng rộng rãi của nó. 1.1.4. Quá trình khai phá dữ liệu 1.1.4.1. Các bước trong quá trình khai phá. Thông thường quá trình khai phá dữ liệu thực hiện qua các bước sau: - Xác định nhiệm vụ: Xác định chính xác các vấn đề cần giải quyết. - Xác định các dữ liệu liên quan dùng để xây dựng giải pháp giải quyết nhiệm vụ bài toán. - Thu thập các dữ liệu có liên quan và xử lý chúng thành dạng sao cho giải thuật khai phá dữ liệu có thể hiểu được. - Chọn thuật toán khai phá dữ liệu thích hợp và thực hiện việc khai phá nhằm tìm được các mẫu có ý nghĩa dưới dạng biểu diễn tương ứng với các ý nghĩa đó. 1.1.4.2. Các thành phần của giải thuật khai phá. Quá trình khai phá dữ liệu là quá trình phát triển mẫu trong đó giải thuật khai phá dữ liệu tìm kiếm các mẫu đáng quan tâm theo dạng xác định các luật, cây phân lớp, hồi quy, phân nhóm, …. Giải thuật khai phá dữ liệu bao gồm 3 thành phần chính như sau: 6 - Biểu diễn mô hình. - Đánh giá mô hình. - Tìm kiếm mô hình.  Biểu diễn mô hình: Mô hình được biểu diễn bằng một ngôn ngữ sao cho có thể khai phá được. Nếu mô hình có sự mô tả hạn chế thì sẽ không thể học được hoặc sẽ không thể có các mẫu tạo ra. Nếu diễn tả mô hình càng lớn thì càng làm tăng mức độ nguy hiểm do bị học quá nhiều và làm giảm đi khả năng dự đoán các dữ liệu chưa biết. Hơn nữa, việc tìm kiếm sẽ càng trở nên phức tạp hơn và việc giải thích mô hình cũng khó khăn hơn.  Đánh giá mô hình: Đánh giá xem một mẫu có đáp ứng được các tiêu chuẩn của quá trình phát hiện tri thức hay không. Việc đánh giá mô hình được thực hiện thông qua kiểm tra dữ liệu, đối với nhiệm vụ dự đoán thì việc đánh giá mô hình ngoài kiểm tra dữ liệu còn dựa trên độ chính xác dự đoán mà việc đánh giá độ chính xác dự đoán dựa trên đánh giá chéo.  Tìm kiếm mô hình: Bao gồm 2 thành phần: tìm kiếm tham số và tìm kiếm mô hình. - Tìm kiếm tham số: Giải thuật cần tìm các tham số để tối ưu hoá các tiêu chuẩn đánh giá mô hình với các dữ liệu quan sát được và với một miêu tả mô hình đã định. - Tìm kiếm mô hình: Quá trình này xảy ra giống như một vòng lặp qua phương pháp tìm kiếm tham số. Khi miêu tả, mô hình bị thay đổi tạo nên một họ các mô hình thì với mỗi một miêu tả mô hình phương pháp tìm kiếm tham số được áp dụng để đánh giá chất lượng mô hình. Các phương pháp tìm kiếm mô hình thường sử dụng các kỹ thuật tìm kiếm heuristic (tức dựa trên kinh nghiệm, thử nghiệm, rút ra kết luận) bởi kích thước của không gian các mô hình có thể ngăn cản các tìm kiếm tổng thể. 7 1.1.5. Các hướng tiếp cận cơ bản và kỹ thuật áp dụng. Vấn đề khai phá dữ liệu có thể được phân chia theo lớp các hướng tiếp cận chính sau: Phân lớp và dự đoán (classification &prediction): xếp một đối tượng vào một trong những lớp đã biết. Ví dụ: phân lớp vùng địa lý theo dữ liệu thời tiết. Đối với hướng tiếp cận này thường áp dụng một số kỹ thuật như học máy (machinne learning, cây quyết định (decision tree), mạng nơ ron nhân tạo (neural network), v.v... Hay lớp bài toán này còn đươc gọi là học có giám sát – Học có thày (supervised learning). Phân cụm (clustering/segmentation): Sắp xếp các đối tượng theo từng cụm nhưng số lượng và tên các cụm chưa biết trước. Lớp bài toán phân cụm còn được gọi là học không giám sát – Học không thày (unsupervised learning). Luật kết hợp (association rules): là dạng luật biểu diễn tri thức ở dạng khá đơn giản. Ví dụ: “80% sinh viên đăng ký học Cơ sở dữ liệu thì có tới 70% trong số họ đăng ký học Phân tích thiết kế hệ thống thông tin.” Hướng tiếp cận này được ứng dụng nhiều trong lĩnh vực kinh doanh, y học, tin sinh học, giáo dục, ..... Khai phá chuỗi theo thời gian (sequential/temporal patterns): Cũng 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 chúng có tính dự báo cáo. Mô tả khái niệm (concept desccription & summarization): lớp bài toán này thiên về mô tả, tổng hợp và tóm tắt khái niệm. Ví dụ: tóm tắt văn bản. 1.1.6. Các lĩnh vực ứng dụng của khai phá dữ liệu Khai phá dữ liệu là một lĩnh vực mới phát triển nhưng thu hút được nhiều nhà 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ố lĩnh vực ứng dụng điển hình: - Phân tích dữ liệu và hỗ trợ ra quyết định. 8 - Điều trị trong y học: 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 văn bản, tóm tắt văn bản và phân lớp các trang WEB. - Tin sinh học: 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, ... - Tài chính và thị trường chứng khoán: Phân tích tình hình tài chính và dự báo giá của các cổ phiếu. - Bảo hiểm. - Giáo dục... 1.2. Phương pháp khai phá dữ liệu. 1.2.1. Một số phương pháp khai phá dữ liệu phổ biến 1.2.1.1. Phương pháp suy diễn và quy nạp  Phương pháp suy diễn: Rút ra thông tin là kết quả logic từ các thông tin nằm trong cơ sở dữ liệu dựa trên các quan hệ trong dữ liệu. Phương pháp suy diễn dựa trên các sự kiện chính xác để uy ra các tri thức mới từ các thông tin cũ. Mẫu chiết suất được bằng cách sử dụng phương pháp này thường là các luật suy diễn.  Phương pháp quy nạp: Các thông tin được suy ra từ cơ sở dữ liệu bằng cách nó tự tìm kiếm, tạo mẫu và sinh ra tri thức chứ không bắt đầu với các tri thức đã biết trước. 1.2.1.2. Cây quyết định và luật Cây quyết định: Cây quyết định là một phương pháp 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. 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á miêu 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 giá trị của các thuộc tính của đối tượng tới lá. 9 Tạo luật: Các luật được tạo ra nhằm suy diễn cho một số mẫu dữ liệu có ý nghĩa về mặt thống kê. Các luật có dạng nếu P thì Q, trong đó P là mệnh đề đúng với một phần dữ liệu trong cơ sở dữ liệu và Q là mệnh đề dự đoán. Ví dụ: Ta có mẫu phát hiện được bằng phương pháp tạo luật “Nếu giảm ngưỡng chỉ cần học đủ số trình là 120 sẽ được phát chứng nhận tốt nghiệp giai đoạn I thì số lượng sinh viên đăng ký tăng lên 30%. Cây quyết định là phương pháp dùng trong các bài toán phân loại dữ liệu theo một tiêu chuẩn nào đó dựa trên mức độ khác nhau của thuộc tính. Cây quyết định và luật có ưu điểm là hình thức miêu tả đơn giản, mô hình suy diễn khá dễ hiểu đối với người sử dụng. Tuy nhiên, giới hạn của nó là miêu tả cây và luật chỉ có thể biểu diễn được một số dạng chức năng và vì vậy giới hạn cả về độ chính xác của mô hình. 1.2.1.3. Phát hiện các luật kết hợp. Các luật kết hợp là một dạng biểu diễn tri thức, hay chính xác là dạng mẫu của hình thành tri thức. Phương pháp này nhằm phát hiện ra các luật kết hợp giữa các thành phần dữ liệu trong cơ sở dữ liệu. Một đầu ra của giải thuật khai phá dữ liệu là tập các luật kết hợp tìm được. Cho một lược đồ R = { A1, A2,...., Ap} với các thuộc tính có miền giá trị {0,1} và một quan hệ r trên R. Ta gọi một luật kết hợp trên quan hệ r được mô tả như sau: XB với X  R và B  R\X. Cho WR, đặt s(W,r) là tần số xuất hiện của W trong r được tính bằng tỉ lệ của các hàng trong r có giá trị 1 tại mỗi cột. Khi đó ta định nghĩa tần số xuất hiện và độ tin cậy của luật XB trong r như sau: - Tần số xuất hiện =s(X{B},r). - Độ tin cậy = s(X{B},r)\s(X,r). Với X gồm nhiều thuộc tính và B là giá trị không cố định. 10 Nhiệm vụ của việc phát hiện các luật kết hợp là phải tìm tất cả các luật XB sao cho tần số xuất hiện của luật không nhỏ hơn ngưỡng  cho trước và độ tin cậy của luật không nhỏ hơn ngưỡng  cho trước. Khi thiết kế dữ liệu dùng cho kỹ thuật luật kết hợp cần hết sức lưu ý để giảm thiểu số lượng các thuộc tính đầu vào bởi không gian tìm kiếm các luật sẽ tăng theo hàm mũ của số lượng các thuộc tính đầu vào. Giải thuật tìm các luật kết hợp được bắt đầu bằng việc tìm tất cả các tập thường xuyên xuất hiện. Tập thường xuyên xuất hiện là các tập thoả mãn tần số xuất hiện lớn hơn ngưỡng tần số được xác định trước. Các luật kết hợp sẽ được tạo ra bằng cách ghép dần các tập thuộc tính dựa trên mức độ thường xuyên. Ví dụ: Phân tích cơ sở dữ liệu bán hàng nhận được thông tin về những khách mua các mặt hàng máy tính cũng có khuynh hướng mua phần mềm quản lý tài chính trong cùng lần mua được mô tả bởi luật kết hợp như sau: “Nếu mua máy tính thì mua phần mềm quản lý tài chính”. [Độ hỗ trợ: 20%, Độ tin cậy: 60%] Phương pháp này có ưu thế cơ bản là đơn giản và dễ hiểu đối với con người. Ở ví dụ trên độ hỗ trợ 20% có nghĩa là: 20% của tất cả các giao dịch được phân tích thì chỉ ra rằng máy tính và phần mềm quản lý tài chính được mua cùng nhau. Còn độ tin cậy 60% có nghĩa là: 60% các khách hàng mua máy tính thì cũng mua phần mềm. Đặc biệt, các luật kết hợp được coi là đáng quan tâm nếu chúng thoả mãn cả hai ngưỡng độ hỗ trợ cực tiểu và độ tin cậy cực tiểu. Những ngưỡng này thường do người dùng hoặc các chuyên gia trong lĩnh vực xác định. Nhược điểm cơ bản của của phương pháp này là sự gia tăng nhanh chóng khối lượng tính toán và các thông số. Tuy nhiên với sự phát triển nhanh chóng và mạnh mẽ của phần cứng thì vấn đề này cũng được khắc phục. 1.2.1.4. Phân nhóm và phân đoạn Kỹ thuật phân nhóm và phân đoạn là những kỹ thuật phân chia dữ liệu sao cho mỗi phần hoặc mỗi nhóm giống nhau theo một tiêu chuẩn nào đó. Mối quan 11 hệ thành viên của các nhóm có thể dựa trên mức độ giống nhau của các thành viên và từ đó xây dựng nên các luật ràng buộc giữa các thành viên trong nhóm. Một kỹ thuật phân nhóm khác là xây dựng nên các hàm đánh giá các thuộc tính của các thành phần như là hàm của các tham số của các thành phần. Kỹ thuật này được gọi là kỹ thuật phân hoạch tối ưu. Một trong những ứng dụng của kỹ thuật phân nhóm theo độ giống nhau là cơ sở dữ liệu khách hàng để phân nhóm khách hàng theo các tham số và các nhóm thuế tối ưu có được khi thiết lập biểu thuế bảo hiểm. Mẫu đầu ra của quá trình khai phá dữ liệu sử dụng kỹ thuật này là các tập mẫu chứa dữ liệu có chung những tính chất nào đó được phân tách từ cơ sở dữ liệu. Khi các mẫu được thiết lập, chúng có thể được sử dụng để tái tạo các tập dữ liệu dễ hiểu hơn, đồng thời cũng cung cấp các nhóm dữ liệu cho các hoạt động cũng như công việc phân tích. Đối với cơ sở dữ liệu lớn, việc lấy ra các nhóm này là rất quan trọng. 1.2.1.5. Mạng neural. Mạng neural là một phương pháp khai phá dữ liệu phát triển dữ liệu trên cấu trúc toán học với khả năng học trên mô hình hệ thần kinh con người. Mạng neural có thể đưa ra ý nghĩa từ các dữ liệu phức tạp hoặc không chính xác và có thể được sử dụng để chiết suất các mẫu và phát hiện xu hướng quá phức tạp mà con người cũng như các kỹ thuật máy tính khác không thể phát hiện được. Một trong những ưu điểm phải kể đến của mạng neural là khả năng tạo ra các mô hình dự đoán do có độ chính xác cao, có thể áp dụng được cho nhiều các bài toán khác nhau đáp ứng được các nhiệm vụ đặt ra của khai phá dữ liệu như phân lớp, phân nhóm, mô hình hoá, dự báo,... Mẫu chiết xuất bằng mạng neural được thể hiện ở các nút đầu của mạng. Mạng neural sử dụng các hàm số chứ không sử dụng các hàm biểu tượng để tính mức tích cực của các nút đầu ra và cập nhật các trọng số của nó. 12 Đặc điểm của mạng neural là không cần gia công dữ liệu nhiều trước khi bắt đầu quá trình học như các kỹ thuật khác.Tuy nhiên để có thể sử dụng mạng neural có hiệu quả cần phải xác định các yếu tố khi thiết kế mạng như: - Mô hình mạng là gì? - Mạng cần bao nhiêu nút? - Khi nào thì việc học dừng? Ngoài ra còn có rất nhiều bước quan trọng cần phải làm để tiền xử lý dữ liệu trước khi đưa vào mạng neural để mạng có thể hiểu được. Mạng neural được đóng gói với những thông tin trợ giúp của các chuyên gia đáng tin cậy và được họ đảm bảo các mô hình này làm việc tốt. Sau khi học, mạng có thể được coi là một chuyên gia trong lĩnh vực thông tin mà nó vừa được học. 1.2.1.6. Giải thuật di truyền Đây là phương pháp không chỉ phục vụ phát hiện tri thức mà còn phục vụ rất nhiều bài toán khác. Ví dụ bài toán tối ưu hóa hoặc lập lịch. Tư tưởng của thuật toán là áp dụng quy luật của sự chọn lọc tự nhiên. Người ta mô phỏng tập hợp dữ liệu ban đầu bằng kí tự nhị phân và gọi là những quần thể xuất phát. Bằng các thao tác lai ghép, đột biến chúng ta biến đổi quần thể gene ban đầu và loại bỏ đi một số gene làm cho số lượng gene trong quần thể là không thay đổi. Một hàm thích nghi được xây dựng để xác định mức độ thích nghi của quần thể theo các giai đoạn. Quá trình tiến hóa làm cho các quần thể thích nghi ngày càng cao. Về mặt lý thuyết giải thuật di truyền cho ta lời giải tối ưu toàn cục (khác với phương pháp mạng neural). Tuy nhiên, người ta cũng hạn chế lời giải với một mức độ thích nghi nào đó để hạn chế số lượng các bước xây dựng quần thể. Nói theo nghĩa rộng thì giải thuật di truyền mô phỏng lại hệ thống tiến hóa trong tự nhiên, chính xác hơn là các giải thuật chỉ ra tập các cá thể được hình thành, được ước lượng và biến đổi như thế nào. Ví dụ như xác định xem làm thế nào để lựa chọn các cá thể tạo giống và lựa chọn các cá thể nào để loại bỏ. 13 Giải thuật di truyền là một giải thuật tối ưu hóa, nó được sử dụng rất rộng rãi trong việc tối ưu hóa các kỹ thuật khai phá dữ liệu trong đó có kỹ thuật mạng neural. Sự liên hệ của nó với các giải thuật khai phá dữ liệu là ở chỗ tối ưu hóa là cần thiết để xác định các giá trị tham số nào tạo ra các luật tốt nhất. 1.2.2. Lựa chọn các kỹ thuật khai phá Các giải thuật khai phá dữ liệu tự động mới chỉ ở giai đoạn phát triển ban đầu. Hiện nay người ta vẫn chưa đưa ra được một tiêu chuẩn nào trong việc quyết định sử dụng phương pháp nào vào trong trường hợp nào thì hiểu quả. Hầu hết các kỹ thuật về khai phá dữ liệu đều là mới trong các lĩnh vực. Hơn nữa lại có rất nhiều kỹ thuật được sử dụng cho nhiều bài toán khác nhau. Vì vậy câu hỏi dùng kỹ thuật nào để khai phá không phải là đơn giản. Mỗi phương pháp đều có những điểm mạnh và điểm yếu riêng của nó, nhưng đa số các điểm yếu đều có thể khắc phục được. Vậy phải làm như thế nào để áp dụng kỹ thuật một cách đơn giản nhất, dễ sử dụng, để không cảm thấy sự phức tạp vốn có của kỹ thuật đó và vấn đề là tất cả các mẫu tìm được đều đáng quan tâm? Đây chính là vấn đề quan trọng đối với một hệ thống khai phá dữ liệu. Hệ thống khai phá có thể sinh ra hàng nghìn mà thậm chí có thể hàng triệu mẫu hoặc luật, do vậy với câu hỏi trên thì câu trả lời là: Chỉ có một phần nhỏ trong các mẫu hay các luật là đáng quan tâm và hữu ích với người sử dụng. Có một vài câu hỏi thường đặt ra đối với một hệ thống khai phá dữ liệu là: 1. Cái gì tạo ra các mẫu quan tâm? 2. Hệ thống khai phá có thể sinh ra được tất cả các mẫu quan tâm không? 3. Hệ thống khai phá có thể chỉ sinh các mẫu quan tâm không? Để trả lời các câu hỏi này ta nên quan tâm đến sự gợi ý sau: Đối với câu hỏi 1: Mẫu l đáng quan tâm nếu: 14 o Dễ hiểu đối với con người. o Hợp lệ hoặc dữ liệu được kiểm tra với độ chắc chắn nào đó. o Có khả năng (tiềm năng) hữu ích. o Mới lạ. Mẫu cũng là đáng quan tâm nếu nó là giả thiết hợp lệ được người dùng xác nhận. Mẫu quan tâm luôn chứa đựng sự hiểu biết (tri thức). Có vài độ đo cho các mẫu quan tâm. Nó dựa trên cấu trúc của mẫu đã khai phá và thống kê chúng. Chẳng hạn độ đo của luật kết hợp dạng XY là độ hỗ trợ và độ tin cậy của luật. Cụ thể người ta định nghĩa là xác suất P(X U Y) và xác suất P(X/Y). Nhìn chung các độ đo này có thể được người dùng điều khiển. Đối với câu hỏi thứ 2: Có thể tạo ra được tất cả các mẫu đáng quan tâm không? Vấn đề này liên quan đến tính hoàn thiện của thuật toán khai phá. Nó thường không thực hiện được và không có khả năng đối với cá hệ thống khai phá dữ liệu để sinh ra tất cả các mẫu có thể có, có thể tồn tại. Thay cho điều đó người ta tập trung vào mục tiêu tìm kiếm. Khai phá luật kết hợp là một ví dụ, ở đó người ta sử dụng các độ đo có thể đảm bảo khai phá trọn vẹn, có nghĩa là với ngưỡng độ hỗ trợ và độ tin cậy nhỏ nhất xác định trước thì có thể tìm được. Đối với câu hỏi thứ ba: Hệ thống khai phá có thể chỉ sinh ra các mẫu cần quan tâm không? Đây chính là vấn đề tối ưu trong khai phá dữ liệu. Vấn đề này còn là thách thức rất lớn đối với các nhà khoa học trong lĩnh vực khai phá dữ liệu. 15 CHƯƠNG II: KHAI PHÁ DỮ LIỆU BẰNG LUẬT KẾT HỢP Khai phá dữ liệu bằng luật kết hợp là một phương pháp quan trọng trong khai phá dữ liệu. Nó được ra đời và phát triển mạnh mẽ trong những năm gần đây. Lần đầu tiên được Rakesh Agrawal, Tomasz Imielinski, Arun Swami đề xuất năm 1993. Sau đó năm 1996 được Rakesh Agrawal, Heikki Mannila, Ramakrishnan Srikant, Hannu Toivonen, A.Inkeri Verkamo tiếp tục phát triển và cải tiến. Đến nay những nghiên cứu về luật kết hợp tập trung xây dựng thuật toán khai phá luật kết hợp mới, hiệu quả hoặc cải tiến, phát triển các thuật toán để hiệu quả hơn. 2.1. Ý nghĩa của luật kết hợp Luật kết hợp là những luật có dạng như: - 70% khách hàng mua đường thì mua thêm sữa, 30% giao dịch có mua cả đường lẫn sữa, - 75% bệnh nhân có hút thuốc lá và sống ở ven vùng ô nhiễm thì bị ung thư phổi, trong đó 25% số bệnh nhân vừa hút thuốc lá, sống ven vùng ô nhiễm vừa bị ung thư phổi [3]. Ở đây vế trái (tiền đề) của luật là:“Mua đường”, “hút thuốc lá và sống ven vùng ô nhiễm”, còn “mua sữa” và “ung thu phổi” là vế phải (kết luận) của luật. Những con số: 30%, 25% là độ hỗ trợ của luật (support-Số phần trăm giao dịch chứa cả vế trái lẫn vế phải), còn 70% và 75% là độ tin cậy của luật(confidenceSố phần trăm các giao dịch thỏa mãn vế trái thì cũng thỏa mãn vế phải). Ta thấy tri thức đem lại bởi luật kết hợp ở dạng trên có một sự khác biệt cơ bản so với thông tin thu được từ các câu lệnh truy vấn dữ liệu thông thường. Đó thường là những tri thức, những mói liên hệ chưa được biết trước và mang tính dự báo đang tiềm ẩn trong dữ liệu. Những tri thức này không đơn giản chỉ là kết quả của các phép nhóm, tính tổng, sắp xếp mà là kết quả của một quá trình tính toán khá phức tạp và tốn nhiều thời gian. 16 Tuy luật kết hợp là dạng luật khá đơn giản nhưng lại mang rất nhiều ý nghĩa. Thông tin mà dạng luật này đem lại là rất đáng kể và hỗ trợ không nhỏ trong quá trình ra quyết định. Tìm kiếm được những luật kết hợp “quý hiếm” và mang nhiều thông tin từ cơ sở dữ liệu tác nghiệp là một trong những hướng tiếp cận chính của lĩnh vực khai phá dữ liệu. Đây chính là một động lực không nhỏ thúc đẩy việc tập trung nghiên cứu của nhiều nhà tin học. 2.2. Bài toán khai phá dữ liệu bằng luật kết hợp. 2.2.1. Phát biểu bài toán và các pha thực hiện. Cho I={i1, i2, ... , in} là tập gồm n mục (thuộc tính). T={t1, t2, ... ,tm} là tập gồm m giao dịch (bản ghi). Mỗi giao dịch được định danh bởi TID (Transaction Identification). Cho  là một quan hệ nhị phân trên I và T (hay   IxT ). Nếu mục i xuất hiện trong giao dịch t thì ta viết (i,t) . Một cơ sở dữ liệu D, về mặt hình thức chính là một quan hệ nhị phân  như trên. Về ý nghĩa, một cơ sở dữ liệu là một tập các giao dịch, mỗi giao dịch t là một tập mục: t  2 I (với 2I là tập các tập con của I)4 Sau đây là một ví dụ về cơ sở dữ liệu quan hệ (dạng giao dịch): I = {A, C, D, T, W}, T = {1, 2, 3, 4, 5, 6 } Với thông tin về các giao dịch cho ở bảng sau: 17 X I được gọi là tập mục (itemset). Độ hỗ trợ (support) của một tập mục X được ký hiệu s(X) – là phần trăm số giao dịch trong cơ sở dữ liệu chứa X. Một tập mục X được gọi là tập mục phổ biến nếu độ hỗ trợ của nó lớn hơn hoặc bằng một ngưỡng minsup nào đó được xác định bởi người sử dụng: s(X)  minsup. Bảng 2.2 Sẽ liệt kê tất cả các tập mục phổ biến (frequent – itemset) trong cơ sở dữ liệu cho ở bảng 2.1 với minsup bằng 50%. Các tập mục phổ biến độ hỗ trợ C 100% W, CW 83% A, D, T, AC, AW, CD, CT, ACW 67% AT, DW, TW, ACT, ATW, CDW, CTW, ACTW 50% Một số khái niệm cơ bản:  Luật kết hợp (Association Rule): Một luật kết hợp là một phát biểu dạng XY, trong đó X và Y là các tập mục thỏa mãn điều kiện: XI, Y I, X  Y = . Đối với luật kết hợp XY, X gọi là tiền đề, Y được gọi là kết quả của luật.  Độ hỗ trợ của một tập mục (itemset): Độ hỗ trợ (Support) của một tập mục X trong tập các tác vụ D, kí hiệu: supp(X) là tỉ số giữa số các tác vụ T (của D) chứa X và tổng số các tác vụ của D (hay số phần trăm của các tác vụ trong D có chứa X). sup p( X )  T  D T  X  D Độ hỗ trợ của một tập mục có giá trị giữa 0 và 1, tức là 0supp(X)1 với mọi tập mục X. 18  Tập mục phổ biến (frequent itemset): Tập mục X mà thỏa điều kiện: supp(X)  minsup ( với minsup là một giá trị cho trước) được gọi là tập mục phổ biến với độ hỗ trợ cực tiểu minsup.  Độ hỗ trợ của một luật: Cho luật r = XY, đỗ hỗ trợ của luật r kí hiệu là supp(r) được xác định như sau: supp(r) = supp(XY).  Độ tin cậy của một luật (confidence): Luật r = XY có độ tin cậy c trong D nếu c là số phần trăm các tác vụ trong D mà chứa X thì cũng chứa Y. Hay đó chính là xác xuất có điều kiện P(Y/X). Ta kí hiệu độ tin cậy của luật r là conf(f). Độ tin cậy của một luật cũng có giá trị giữa 0 và 1. Supp(XY) = P(XY) Conf(XY) = P(Y/X) = supp(XY) /supp(X)  Luật kết hợp mạnh (strong): Các luật thỏa mãn cả hai ngưỡng là độ hỗ trợ cực tiểu và độ tin cậy cực tiểu được gọi là luật kết hợp mạnh, tức là: Supp(XY) = P(XY)  minsup Conf(XY) = P(Y/X) = supp(XY) /supp(X)  minconf Người ta thường biểu diễn bằng % thay cho các giá trị từ 0 đến 1. Bài toán khai phá luật kết hợp (ở dạng đơn giản nhất) có thể phát biểu như sau: Cho một cơ sở dữ liệu D; Độ hỗ trợ tối thiểu minsup; Độ tin cậy tối thiểu minconf. Hãy tìm tất cả cả các luật kết hợp có dạng X Y thỏa mãn độ hỗ trợ s(X  Y)  minsup và độ tin cậy của luật là: c(X Y) = s(X  Y) / s(X)  minconf. Hầu hết các thuật toán được đề xuất để khai phá dữ liệu nhờ luật kết hợp đều theo hướng chia bài toán thành hai pha cụ thể như sau: 19 Pha 1: Tìm tất cả các tập mục phổ biến từ cơ sở dữ liệu, tức là tìm tất cả các tập mục X thỏa mãn s(X)  minsup. Đây là pha tốn khá nhiều thời gian của CPU và thời gian vào ra ổ đĩa. Pha 2: Sinh các luật tin cậy từ các tập phổ biến đã tìm thấy ở pha thứ nhất. Pha này tương đối đơn giản và tốn kém ít thời gian so với pha 1. Nếu X là tập c  X \ X ' , với phổ biến thì luật kết hợp được sinh ra từ X có dạng: X '  X’ là tập con khác rỗng của X, X \ X’ là hiệu của 2 tập hợp, c là độ tin cậy của luật thỏa mãn điều kiện c  minconf. 2.2.2. Ví dụ Cơ sở dữ liệu D được cho trong bảng 2.3 sau: Bảng: 2.3 - Cơ sở dữ liệu giao dịch D Định danh các giao dịch Tập mục (TID) (itemset) T1 A T2 T3 C D B A B T4 B T5 B E C E E D F Như vậy: Thông qua bảng 2.3 ta rút ra các thông số cho trong bảng như sau: - Số các tác vụ: 5 - Số các mục: 6 Khi đó ta xác định được độ hỗ trợ của các tập mục, cụ thể cách tính độ hỗ trợ của mục A là - Số tác vụ có chứa mục A là 2. - Số các tác vụ trong cơ sở dữ liệu là 5 Do đó: supp(A)=2/5=40% 20