Chương 1: “Tổng quan về khai thác tập mục” trình bày các khái niệm về khai thác FI các phƣơng pháp khai thác FI, FWI, FWUI và TRFIk. Phân tích ƣu điểm và hạn chế của các phƣơng pháp này đồng thời đề xuất hƣớng nghiên cứu của luận án. 5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chương 2: “Khai thác tập mục phổ biến trên cơ sở dữ liệu số lƣợng” trình bày một số cấu trúc dữ liệu mới để biểu diễn tidset của các tập mục, trên cơ sở đó đề xuất các phƣơng pháp hiệu quả để khai thác nhanh FWI, FWUI trên CSDL số lƣợng. Đồng thời, trong chƣơng này cũng đề xuất bài toán khai thác k nhóm tập mục phổ biến trọng số hữu ích có thứ hạng cao nhất (TRFWUIk) trên CSDL số lƣợng và thuật toán hiệu quả để giải quyết bài toán này với hai cấu trúc DTab và DHeap.
Chương 3: “Khai thác tập mục phổ biến trên cơ sở dữ liệu số lƣợng có sự phân cấp các mục” đề xuất thuật toán khai thác FWUI trên CSDL số lƣợng có sự phân cấp các mục. Chƣơng này trình bày một mở rộng của cấu trúc dữ liệu trong chƣơng 2 và một số đề xuất nhằm cải tiến thuật toán khai thác hiệu quả FWUI trên CSDL số lƣợng có sự phân cấp các mục. 6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com CHƢƠNG 1. TỔNG QUAN VỀ KHAI THÁC TẬP MỤC Chƣơng này trình bày các nghiên cứu liên quan đến khai thác tập mục phổ biến trên các loại CSDL nhƣ CSDL nhị phân, CSDL số lƣợng, CSDL có sự phân cấp các mục và khai thác k nhóm tập phổ biến có thứ hạng cao nhất (Top-rank-k) từ các nhóm nghiên cứu trong nƣớc và quốc tế.
Phần này cũng trình bày các phân tích về ƣu điểm và hạn chế của các phƣơng pháp khai thác tập mục phổ biến hiện có. Từ cơ sở đó luận án đề ra các thuật toán mới dựa trên các cấu trúc dữ liệu phù hợp hơn cho các bài toán này trong chƣơng 2 và 3 của luận án. Bài toán khai thác tập mục Mục đích của việc khai thác tập mục là để xác định nhóm các mục (item) có tần suất xuất hiện thỏa mãn một ngƣỡng nào đó của ngƣời sử dụng đƣa vào. Trong đó, bài toán khai thác tập mục phổ biến là một bài toán con của bài toán khai thác tập mục với việc khai thác các tập mục có tần suất xuất hiện nhiều trong CSDL.
Tần suất xuất hiện này thỏa mãn ngƣỡng do ngƣời sử dụng đƣa vào (đƣợc gọi là ngƣỡng phổ biến). Từ các FI khai thác đƣợc có thể sinh ra tập luật kết hợp nhằm khám phá mối quan hệ tiềm ẩn, hữu ích giữa các mục trong CSDL, phục vụ các yêu cầu xuất phát từ đòi hỏi của thực tế của ngƣời sử dụng. Có thể nói, từ khi đƣợc giới thiệu đến nay, đã có khá nhiều công trình nghiên cứu liên quan nhằm mục đích giải quyết tốt bài toán này. Hiện nay, bài toán khai thác tập mục đang đƣợc tiếp tục nghiên cứu để tìm ra các giải pháp hiệu quả hơn.
Nội dung chƣơng 1 sẽ trình bày một số định nghĩa và khái niệm liên quan đến bài toán khai thác tập mục trên một CSDL nhƣ CSDL nhị phân, CSDL có sự phân cấp các mục, CSDL số lƣợng và một biến thể của CSDL số lƣợng là CSDL trọng số. Đồng thời chƣơng 1 giới thiệu tổng quát một số tiếp cận chính cho bài toán khai thác tập mục trên các loại CSDL đó. 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Một số khái niệm cơ bản Định nghĩa 1.
CSDL nhị phân (binary database) là một bộ gồm hai thành phần: T, I trong đó: T = {t1, t2, ., tm} là tập gồm m giao dịch của CSDL I = {i1, i2, ., in} là tập gồm n mục trong CSDL Với giao dịch thứ k (k = 1.m): ={ } trong đó 0 hoặc 1, với j = Ví dụ 1.1: Cho CSDL DB với tập các mục I = {A, B, C, D, E} và tập các giao dịch T đƣợc biểu diễn bởi Bảng 1.1 nhƣ sau: Bảng 1. Các giao dịch của CSDL nhị phân DB Mục A B C D E Giao dịch t1 1 1 0 1 1 t2 0 1 1 1 0 t3 1 1 0 1 1 t4 1 1 1 0 1 t5 1 1 1 1 1 t6 0 1 1 0 1 Các mục xuất hiện trong một giao dịch của CSDL tƣơng ứng có giá trị 1, ngƣợc lại có giá trị 0. Ví dụ giao dịch t1 = {1, 1, 0, 1, 1} có nghĩa các mục A, B, D, E có trong giao dịch, mục C không có trong giao dịch. CSDL nhị phân là CSDL biểu diễn sự xuất hiện hay không của các mục trong các giao dịch.
Trong nhiều trƣờng hợp, các mục trong CSDL có mối quan hệ với nhau đƣợc thể hiện qua các cây phân cấp, ví dụ "computer" là mức khái quát của "Desktop" và "Notebook", hay "Printer" là mức khái quát 8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com của "Laser priter", "Ink-Jet printer", v.v… Những CSDL có thể hiện mối quan hệ của các mục thông qua cây phân cấp nhƣ trên đƣợc gọi là CSDL nhị phân có sự phân cấp các mục. CSDL nhị phân có sự phân cấp các mục (hierarchical database) là một bộ gồm ba thành phần: T, I, Tr, trong đó: T = {t1, t2, ., tm} là tập gồm m giao dịch của CSDL I = {i1, i2, ., in} là tập gồm n mục trong CSDL Với giao dịch thứ k (k = 1.m): ={ } trong đó 0 hoặc 1, với j = 1. Tr là cây phân cấp thể hiện mối quan hệ của các mục trong CSDL. Cho CSDL nhị phân có sự phân cấp mục DB với tập các mục I = {Desktop, Dot-matrix printer, Ink-jet printer, Laser printer, Notebook, Scanner}, các giao dịch T đƣợc biểu diễn nhƣ Bảng 1.2 và cây phân cấp thể hiện quan hệ các mục nhƣ Hình 1.
Các giao dịch của CSDL nhị phân có sự phân cấp mục DB Giao dịch Mục t1 Notebook, Laser printer t2 Scanner, Dot-matrix printer t3 Dot-matrix printer, Ink-jet printer t4 Notebook, Dot-matrix printer, Laser printer t5 Scanner t6 Desktop 9 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Printer Computer Scanner Non – impact Dot – matrix Desktop Notebook Laser Ink – jet Hình 1. Cây phân cấp Tr Để đơn giản, ta gán các mục trên cây phân cấp Tr bằng các ID nhƣ Bảng 1. ID các mục của DB ID mục Tên mục A Desktop B Ink-jet Printer C Laser Printer D Notebook E Scanner F Dot-matrix Printer G Non-impact H Computer K Printer Từ ID đƣợc định nghĩa trong Bảng 1.3, các giao dịch trong Bảng 1.2 và cây phân cấp Tr đƣợc biểu diễn lại nhƣ trong Bảng 1. Các giao dịch của DB bằng ID Giao dịch mục t1 D, C t2 E, F t3 F, B t4 D, F, C t5 E t6 A 10 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.
Cây phân cấp Tr biểu diễn theo ID Tập J = {G, K, H} là tập các mục cha của cây phân cấp không xuất hiện trong các giao dịch của DB. Tuy nhiên chúng có vai trò nhất định, thể hiện mối quan hệ của các mục trong DB. Do đó, khi khai thác FI trên CSDL phân cấp đòi hỏi phải khai thác cả tập các mục trên cây phân cấp bao gồm (I J). CSDL nhị phân là CSDL thể hiện sự có mặt hay không của mục trong các giao dịch của CSDL mà không quan tâm đến giá trị (trọng số, lợi ích, số lƣợng, v.v…) của các mục trong các giao dịch.
Trong nhiều ứng dụng thực tế nhƣ CSDL bán hàng trong siêu thị, CSDL đơn thuốc, v.v… mỗi mục trên mỗi đơn hàng thƣờng kèm theo số lƣợng và giá trị của chúng. Các CSDL dạng này đƣợc gọi là CSDL số lƣợng. CSDL số lượng (quantitative database) là một bộ ba thành phần: T, I, W, trong đó: T = {t1, t2, ., tm} là tập gồm m giao dịch của CSDL I = {i1, i2, ., in} là tập gồm n mục trong CSDL W = {w1, w2, …, wn} là tập gồm n trọng số của các mục tƣơng ứng trong tập I Với giao dịch thứ k (k = 1.m): tk = { , , …, }, là số tự nhiên chỉ số lƣợng của mục thứ j trong giao dịch, j = 1.2: Cho CSDL số lƣợng DB với tập các mục I = {A, B, C, D, E}, các giao dịch T đƣợc biểu diễn trong Bảng 1.5, trọng số các mục nhƣ trong bảng 1. 11 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.
Giao dịch của CSDL số lƣợng BD Giao dịch A B C D E 1 1 0 4 1 0 1 3 0 1 2 1 0 3 2 3 1 1 0 1 1 2 2 1 3 0 1 1 1 0 Bảng 1. Trọng số các mục trong DB Mục Trọng số A 0,6 B 0,1 C 0,3 D 0,9 E 0,2 Theo Bảng 1.5, DB có sáu giao dịch {t1, t2, t3, t4, t5, t6}, ví dụ giao dịch = {1, 1, 0, 4, 1} có nghĩa là trong giao dịch có một mục A, một mục B, bốn mục D, một mục E, không có mục C. Trong nhiều ứng dựng thực tế, CSDL số lƣợng có thể không quan tâm đến số lƣợng của các mục trong mỗi giao dịch, mà chỉ quan tâm đến trọng số của chúng. Ví dụ CSDL vi phạm giao thông, ngƣời ta chỉ quan tâm là ngƣời vi phạm lỗi gì và mức tiền phạt tƣơng ứng cho từng lỗi ấy, hay CSDL khám bệnh, ngƣời ta quan tâm đến bệnh nhân có những triệu chứng gì mức độ nặng nhẹ (trọng số) của từng triệu chứng ấy, v.v… Các CSDL đó đƣợc gọi là CSDL có trọng số hay CSDL trọng số - một biến thể của CSDL số lƣợng với số lƣợng của các mục xuất hiện trong CSDL là 1.
12 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Định nghĩa 1. CSDL trọng số (weighted database) là một bộ gồm ba thành phần: T, I, W, trong đó: T = {t1, t2, ., tm} là tập gồm m giao dịch của CSDL I = {i1, i2,., in} là tập gồm n mục trong CSDL W = {w1, w2, …, wn} là tập gồm n trọng số của các mục tƣơng ứng trong tập I Ví dụ 1.3: Cho CSDL trọng số DB với tập mục I = {A, B, C, D, E}, các giao dịch đƣợc biểu diễn trong Bảng 1.7, trọng số các mục đƣợc thể hiện trong Bảng 1. Các giao dịch của CSDL trọng số DB Giao dịch Mục A, B, D, E B, C, E A, B, D, E A, B, C, E A, B, C, D, E B, C, D Bảng 1. Trọng số của các mục của DB mục Trọng số A 0,6 B 0,1 C 0,3 D 0,9 E 0,2 Định nghĩa 1.
Tidset của tập mục X là tập hợp các giao dịch chứa X.