Chương 1, Giới thiệu: giới thiệu tổng quan về đề tài, mục tiêu nghiên cứu và giới hạn của đề tài. Chương 2, Kiến thức nền tảng: trình bày tổng quan các khái niệm cơ bản về khai phá luật kết hợp, lập trình song song, các công trình nghiên cứu liên quan trong vấn đề khai phá luật kết hợp. Chương 3, Tổng thuật các công trình liên quan: khảo sát các công trình nghiên cứu đã đăng tải liên quan. Chương 4, Phương pháp giải quyết vấn đề: trình bày phương pháp khai phá luật kết hợp sử dụng đa ngưỡng hỗ trợ tối thiểu, hướng tiếp cận song song trong giai đoạn tìm tập phổ biến.
Chương 5, Thực nghiệm: chạy thực nghiệm, trình bày các kết quả thực nghiệm, so sánh và đánh giá hệ thống trên các tập dữ liệu khác nhau. Chương 6, Kết luận: đưa ra kết luận và hướng phát triển tiếp theo của đề tài trong tương lai. 2 CHƯƠNG 2: KIẾN THỨC NỀN TẢNG 2. Một số khái niệm cơ bản 2.
Phát hiện tri thức và khai phá dữ liệu Quá trình khai phá tri thức thường gồm có các bước chính sau: Trích chọn dữ liệu (data selection): 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 (databases, data warehouses, data repositories) ban đầu theo một số tiêu chí nhất định. Tiền xử lý dữ liệu (data preprocessing): 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 histograms, lấy mẫu, .), rời rạc hóa dữ liệu (rời rạc hóa dựa vào histograms, dựa vào entropy, 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 hóa. Biến đổi dữ liệu (data transformation): đây là bước chuẩn hóa và làm mịn 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á ở bước sau.
Khai phá dữ liệu (data mining): đây là bước áp dụng những kỹ thuật khai phá (phần nhiều là các kỹ thuật của machine learning) để khai phá, trích chọn được những mẫu (patterns) thông tin, những mối liên hệ (relationships) đặc biệt trong dữ liệu. Đây được xem là bước quan trọng và tốn nhiều thời gian nhất của toàn quá trình KDD. Biểu diễn và đánh giá tri thức (knowledge representation and evaluation): những mẫu thông tin và mối liên hệ trong dữ liệu đã được khai 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ị, cây, bảng biểu, luật,. Đồ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.
Các kỹ thuật và hướng tiếp cận chính trong khai phá dữ liệu Các hướng tiếp cận của KPDL có thể được phân chia theo chức năng hay lớp các bài toán khác nhau. Sau đây là một số hướng tiếp cận chính: 3 - 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 trước. Ví dụ: phân lớp vùng địa lý theo dữ liệu thời tiết. Hướng tiếp cận này thường sử dụng một số kỹ thuật của machine learning như cây quyết định (decision tree), mạng nơ ron nhân tạo (neural network),.
Phân lớp còn được gọi là học có giám sát (supervised 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ụ: “60 % nam giới vào siêu thị nếu mua bia thì có tới 80% trong số họ sẽ mua thêm thịt bò khô”. Luật kết hợp được ứng dụng nhiều trong lĩnh vực kinh doanh, y học, tin-sinh, 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á 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 vì nó có tính dự báo cao. - Phân cụm (clustering/segmentation): xếp các đối tượng theo từng cụm (số lượng cũng như tên của cụm chưa được biết trước. Phân cụm còn được gọi là học không giám sát (unsupervised learning).
Phân loại các hệ thống khai phá dữ liệu Khai phá dữ liệu là một công nghệ tri thức liên quan đến nhiều lĩnh vực nghiên cứu khác nhau như cơ sở dữ liệu, máy học (machine learning), giải thuật, trực quan hóa (visualization),. Có thể phân loại các hệ thống khai phá dữ liệu dựa trên các tiêu chí khác nhau. - Phân loại dựa trên kiểu dữ liệu được khai phá: cơ sở dữ liệu (CSDL) giao dịch (transactional database), CSDL quan hệ (relational database), kho dữ liệu (data warehouse), CSDL hướng đối tượng, CSDL không gian (spatial database), CSDL đa phương tiện (multimedia database), CSDL Text và WWW,. - Phân loại dựa trên dạng tri thức được khám phá: tóm tắt và mô, luật kết hợp, phân lớp (classification), phân cụm, khai phá chuỗi ,.
- Phân loại dựa trên kỹ thuật được áp dụng: hướng CSDL (database oriented), phân tích trực tuyến (OnLine Analytical Processing – OLAP), machine learning (cây quyết định, mạng nơ ron nhân tạo, k-min, giải thuật di truyền, máy vectơ hỗ trợ - SVM, tập thô, tập mờ, .), trực quan hóa visualization),. 4 - Phân loại dựa trên lĩnh vực được áp dụng: kinh doanh bán lẻ, tài chính và thị trường chứng khoán, truyền thông, tin sinh học, y học, ,web mining,. Khai phá luật kết hợp Tập phần tử (itemset): một tập hợp gồm một hoặc nhiều phần tử (item).Ví dụ tập phần tử: {Milk, Bread, Diaper}. Tập phần tử mức k (k-itemset): Một tập gồm có k phần tử.
Cơ sở dữ liệu giao dịch: Cho I = {I1, I2,., In} là một tập các phần tử. Gọi D là một tập CSDL giao dịch (transaction database) xác định trên I. Một giao dịch (transaction) T là một tập con của I, T I. Mỗi giao dịch được gán một định danh TID.
Một tập phần tử con X I, gồm k phần tử phân biệt được gọi là một k- tập phần tử. Giao dịch T gọi là chứa tập phần tử X nếu và chỉ nếu X T. TID Itemset (tập các phần tử) (mã giao dịch) 1 A, B, E 2 B, D 3 B, C 4 A, B, D 5 A, C 6 B, C 7 A, C 8 A, B, C, E 9 A, B, C Bảng 2.1 Ví dụ cơ sở dữ liệu giao dịch Định nghĩa luật kết hợp: Cho tập phần tử I = {I1,I2,…, In}. Một luật kết hợp là một phép kéo theo, dạng A B, trong đó: A I, B I, và A B = .
Độ hỗ trợ: Cho tập phần tử A, A I. Độ hỗ trợ của luật kết hợp X Y chính là xác suất P(X Y) của sự xuất hiện đồng thời X và Y trong một giao dịch. Ta có: 0 ≤ sup(X Y) ≤ 1 Luật X Y có trong tập giao dịch D với độ hỗ trợ s (support) là tỷ lệ các giao dịch trong D mà có chứa cả X và Y, tức là phép hợp X Y, so với tổng số giao dịch trong D. Tỷ lệ này tương đương với xác suất P(X Y).
Chẳng hạn, độ hỗ trợ s = 1% nghĩa là có 1% số giao dịch trên tổng số giao dịch trong CSDL thể hiện X và Y cùng có mặt. Độ tin cậy: Luật kết hợp có dạng X c Y , trong đó X, Y là các tập phần tử thỏa mãn điều kiện X Y = , X được gọi là tiền đề, Y được gọi là kết quả của luật, c là độ tin cậy (confidence) của luật. Luật X Y có độ tin cậy c trong tập giao tác D, với c là tỷ lệ các giao dịch trong D chứa X và cũng chứa cả Y, so với tổng số giao dịch có chứa X. 6 Độ tin cậy (confidence) của luật kết hợp X Y, ký hiệu là conf(X Y), là tỷ lệ phần trăm giữa số giao dịch chứa X Y và số giao dịch chứa X trong CSDL giao dịch D.
Xác suất có điều kiện P(Y/X) – xác xuất mà một giao dịch có chứa Y với điều kiện giao dịch đó đã chứa X. Ví dụ với độ tin cậy confidence = 50% nghĩa là trong một giao dịch nếu X đã có mặt thì khả năng có tới 50% là Y sẽ có mặt trong đó. Khi đó độ tin cậy của luật X Y được biểu diễn bằng: sup( X Y ) conf ( X Y ) P(Y / X ) sup( X ) 2. Các tính chất của luật kết hợp Luật kết hợp có một số tính chất sau: - Tính chất 1: Không hợp các luật kết hợp Nếu có hai luật X Y và Y Z trong D thì không nhất thiết XY Z là đúng Xét trường hợp X Z = và các giao dịch trong D hỗ trợ Z nếu và chỉ nếu chúng hỗ trợ mỗi X hoặc Y, khi đó luật XY Z có độ hỗ trợ 0%.
Tương tự : X Y X Z thì không nhất thiết X YZ là đúng. - Tính chất 2: Không tách luật Nếu XY Z thì X Z và Y Z chưa chắc đã xảy ra 7 Ví dụ trường hợp Z có mặt trong một giao dịch chỉ khi cả hai X và Y cũng có mặt, tức là sup(XY) = sup(Z), nếu độ hỗ trợ của X và Y thỏa mãn s(X) > s(XY) và s(Y) > s(XY) thì hai luật riêng biệt sẽ không đủ độ tin cậy. - Tính chất 3: Các luật kết hợp không có tính bắc cầu. Nếu XY và YZ thì không thể suy ra XZ.
- Tính chất 4: Nếu luật X (L - X) không thoả mãn độ tin cậy cực tiểu thì luật Y (L - Y) cũng không thoả mãn, với X, Y, L là các tập phần tử và Y X. Ta có s(Y) ≥ s(X) nên: s (L) s ( L) c(Y(L-Y))= min_conf s (Y ) s ( X ) Nếu có luật (L-X) X thỏa mãn độ tin cậy thì ta có luật (L-Y) Y cũng thỏa mãn độ tin cậy, với X, Y, L là các tập phần tử và Y X. Một số hướng tiếp cận luật kết hợp Luật kết hợp cho đến nay đã được nghiên cứu và phát triển theo nhiều hướng khác nhau. Dưới đây là một số hướng chính: - Luật kết hợp nhị phân (Binary association rule hay Boolean association rule): là hướng nghiên cứu đầu tiên của luật kết hợp.
Theo luật này, các phần tử chỉ quan tâm là xuất hiện hay không trong cơ sở dữ liệu giao dịch.