Luận văn: Các Phương Pháp Khai Phá Dữ Liệu Sinh Luật Kết Hợp

Luận văn thạc sĩ về khai phá dữ liệu sinh luật. Nghiên cứu các phương pháp kết hợp trong lĩnh vực công nghệ thông tin (mã số 1.01.10).

• Tác giả: Trần Vĩnh Hoàng
• Trường học: Trường Đại Học Công Nghệ - Đại Học Quốc Gia Hà Nội
• Chuyên ngành: Khai Phá Dữ Liệu
• Đề tài: Một Số Phương Pháp Khai Phá Dữ Liệu Sinh Luật Kết Hợp
• Loại tài liệu: Luận Văn Thạc Sĩ
• Năm xuất bản: 2007
• Địa điểm: Hà Nội

Mục lục chi tiết

• Lời cảm ơn
• 1. Chương 1: Tổng quan về khai phá dữ liệu (KPDL)
• 1.1. Các hướng tiếp cận chính trong KPDL
• 1.2. Một số phương pháp KPDL phổ biến
• 1.2.1. Phương pháp suy diễn và quy nạp
• 1.2.2. Cây quyết định và luật
• 1.2.3. Phát hiện các luật kết hợp
• 1.2.4. Phân nhóm và phân đoạn
• 1.2.5. Giải thuật di truyền
• 1.3. Lựa chọn các kỹ thuật khai phá
• 1.4. Các dạng CSDL thường được sử dụng để KPDL
• 1.5. Một số ứng dụng của KPDL
• 2. Chương 2: Một số vấn đề cơ bản về Luật kết hợp
• 2.1. Định nghĩa luật kết hợp
• 2.2. Ví dụ về luật kết hợp
• 2.3. Các định nghĩa và tính chất
• 2.3.1. Các định nghĩa cơ bản
• 2.3.2. Một số tính chất của tập mục phổ biến
• 2.3.3. Một số tính chất của luật kết hợp
• 2.4. Các loại luật kết hợp và hướng tiếp cận
• 2.4.1. Luật kết hợp nhị phân
• 2.4.2. Luật kết hợp định lượng
• 2.4.3. Khai phá luật kết hợp định lượng
• 2.4.4. Luật kết hợp đơn chiều
• 2.4.5. Luật kết hợp đa chiều
• 2.4.6. Luật kết hợp đa mức
• 2.4.7. Khai phá luật kết hợp đa mức
• 2.4.8. Luật kết hợp với thuộc tính có trọng số
• 2.4.9. Luật kết hợp mờ
• 2.4.10. Luật kết hợp đóng
• 3. Chương 3: Một số phương pháp KPDL sinh luật kết hợp
• 3.1. Thuật toán Apriori
• 3.2. Nâng cao hiệu quả của thuật toán Apriori
• 3.2.1. Sử dụng kỹ thuật băm
• 3.2.2. Rút gọn số giao dịch sau mỗi lần quét CSDL
• 3.3. Sinh luật kết hợp từ tập mục phổ biến
• 3.3.1. Thuật toán đơn giản sinh luật kết hợp từ tập mục phổ biến
• 3.3.2. Thuật toán nhanh hơn sinh luật kết hợp từ tập mục phổ biến
• 3.4. Thuật toán FP-Growth
• 3.5. Thuật toán Charm
• 3.5.1. Một số khái niệm
• 3.5.2. Toán tử đóng và tập đóng
• 3.5.3. Cây tìm kiếm “tập mục – tập định danh” và Lớp tương đương
• 3.5.4. Sinh luật kết hợp từ tập mục đóng phổ biến
• 3.6. Thuật toán Closet
• 4. Chương 4: Xây dựng ứng dụng minh hoạ
• 4.1. Phân tích và Thiết kế hệ thống
• 4.2. Cài đặt và Đánh giá
• Danh sách tài liệu tham khảo tiếng Việt
• Danh sách tài liệu tham khảo tiếng Anh
• Danh sách WebSites tham khảo

Tóm tắt

I. Tổng Quan Luận Văn Khám Phá Khai Phá Dữ Liệu Sinh Luật Kết Hợp

Khai phá dữ liệu (KPDL) đã trở thành một lĩnh vực nghiên cứu quan trọng trong khoa học máy tính và công nghệ tri thức. Trong đó, khai phá luật kết hợp là một nội dung quan trọng, thậm chí có chuyên gia khẳng định đây là mục tiêu cơ bản của khai phá dữ liệu. Luận văn này tập trung vào một số phương pháp khai phá dữ liệu sinh luật kết hợp, xây dựng dựa trên nền của các nghiên cứu chính yếu trong lĩnh vực này. KPDL là quá trình tìm kiếm, phát hiện các tri thức tiềm ẩn và hữu dụng trong CSDL nhất định. Tri thức ở đây là các thông tin mang tính chất quy luật và hữu ích cho người dùng. KPDL là bước quan trọng nhất trong quá trình KDD (Knowledge Discovery in Database), bao gồm thu thập dữ liệu, tiền xử lý dữ liệu, biến đổi dữ liệu, khai phá dữ liệu, và đánh giá/biểu diễn tri thức. Các hướng tiếp cận chính trong KPDL bao gồm phân lớp/dự đoán, khai phá luật kết hợp, phân tích chuỗi theo thời gian, phân cụm và mô tả khái niệm. Các kỹ thuật khai phá dữ liệu được thừa kế từ CSDL, máy học, trí tuệ nhân tạo, lý thuyết thông tin, xác suất thống kê và tính toán hiệu năng cao. KPDL đã được ứng dụng thành công trong thương mại, tài chính, sinh học, y học, giáo dục, viễn thông…

Ví dụ, máy tính có thể tự phát hiện ra các kết luận như: “Khách hàng ở độ tuổi 18-22 khi mua hoa và quà lưu niệm thường mua thêm thiệp” hay “Khi giá dầu thô tăng đột biến thì chỉ số chứng khoán giảm”. Đây chính là sức mạnh của KPDL và khai phá luật kết hợp.

1.1. Giới Thiệu Các Phương Pháp Khai Phá Dữ Liệu Phổ Biến

Các phương pháp KPDL phổ biến bao gồm phương pháp suy diễn và quy nạp, cây quyết định và luật, phát hiện các luật kết hợp, phân nhóm và phân đoạn, mạng Neural, và giải thuật di truyền. Phương pháp suy diễn rút ra thông tin từ CSDL dựa trên các quan hệ trong dữ liệu, còn phương pháp quy nạp tìm kiếm, tạo mẫu và sinh ra tri thức. 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 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 CSDL và Q là mệnh đề dự đoán. Khai phá luật kết hợp là một hướng tiếp cận quan trọng trong KPDL. Mục tiêu là 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 𝜎min và độ tin cậy của luật không nhỏ hơn ngưỡng 𝜃min. Các luật kết hợp được khai phá từ các tập mục phổ biến này dựa trên 𝜃min.

1.2. Ứng Dụng Thực Tiễn Của Khai Phá Dữ Liệu Trong Các Lĩnh Vực

KPDL có nhiều ứng dụng thực tiễn, bao gồm phân tích dữ liệu và hỗ trợ quyết định, điều trị trong y học, text mining & web mining, tin-sinh (bioinformatics), tài chính và thị trường chứng khoán. Ví dụ, KPDL có thể giúp tìm kiếm mối liên hệ giữa triệu chứng, chuẩn đoán và phương pháp điều trị trong y học, hoặc phân lớp, tóm tắt văn bản và phân lớp các trang WEB. Trong tin-sinh, KPDL có thể 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. Trong tài chính, KPDL có thể phân tích tình hình tài chính và dự báo giá của các cổ phiếu trong thị trường chứng khoán. KPDL là một lĩnh vực đầy tiềm năng và hứa hẹn mang lại nhiều giá trị trong tương lai.

II. Bài Toán Khai Phá Luật Kết Hợp Định Nghĩa Và Các Tính Chất

Khai phá luật kết hợp là một hướng tiếp cận quan trọng trong KPDL, được đề xuất lần đầu tiên năm 1993. Một ví dụ về luật kết hợp là: “Tại siêu thị 10% giao dịch là khách hàng mua bia và lạc. Nếu một người mua bia thì chắc đến 70% rằng người đó sẽ mua thêm lạc”. Ở đây, “mua bia” là vế trái, còn “mua lạc” là vế phải của luật. 10% là độ hỗ trợ của luật, và 70% là độ tin cậy của luật. Luật kết hợp có dạng: r: X => Y (s, c), với X, Y là các tập mục thoả mãn điều kiện XY = Ø, X là tiền đề, Y là kết quả của luật, s là độ hỗ trợ, c là độ tin cậy của luật. Bài toán khai phá dữ liệu luật kết hợp là: Cho một CSDL D, độ hỗ trợ tối thiểu minsup, độ tin cậy tối thiểu minconf, hãy tìm kiếm tất cả các luật kết hợp r dạng X => Y (s, c) thoả mãn cả 2 điều kiện: s(r) = s(X  Y)  minsup và conf(r) = conf(X => Y) = s(X  Y) / s(X)  minconf. Các thuật toán thường chia bài toán thành 2 pha: tìm tập mục phổ biến, và sinh các luật tin cậy từ các tập phổ biến.

2.1. Các Định Nghĩa Cơ Bản Về Luật Kết Hợp Cần Nắm Vững

Cho tập các mục I = {i1, i2, …, in} và tập các giao dịch T = {t1, t2, …, tm}. Trong đó i (1< = n) là một mục (item) hay một thuộc tính (property), t (1100 % W Có, AW 100  % C Có. Một số tính chất quan trọng của tập mục phổ biến là: Độ hỗ trợ của tập con (Nếu X  Y thì sup(X)  sup(Y)), một tập chứa tập không phổ biến thì nó cũng không phổ biến, và mọi tập con của một tập phổ biến cũng là tập phổ biến.

2.2. Phân Loại Các Luật Kết Hợp Theo Nhiều Tiêu Chí Khác Nhau

Có nhiều loại luật kết hợp, bao gồm luật kết hợp nhị phân, luật kết hợp định lượng, luật kết hợp đơn chiều, luật kết hợp đa chiều, luật kết hợp đa mức, luật kết hợp với thuộc tính có trọng số, luật kết hợp mờ, và luật kết hợp đóng. Luật kết hợp nhị phân chỉ quan tâm đến sự xuất hiện hay không xuất hiện của các mục. Luật kết hợp định lượng quan tâm đến định lượng của từng mục trong luật. Luật kết hợp đơn chiều chỉ tham chiếu đến 1 chiều của dữ liệu, còn luật kết hợp đa chiều có thể tham chiếu đến nhiều hơn 1 chiều của dữ liệu. Luật kết hợp đa mức dựa trên mức độ trừu tượng chứa trong luật. Các loại luật kết hợp khác nhau phù hợp với các ứng dụng khác nhau.

III. Thuật Toán Apriori Cách Tiếp Cận Và Các Bước Triển Khai

Thuật toán Apriori được Rakesh Agrawal, Tomaz Imielinski, Arun Swanmi đề xuất năm 1993, là một thuật toán kinh điển trong khai phá luật kết hợp. Thuật toán này sử dụng chiến lược đi từ dưới lên (bottom-up) và tìm kiếm theo chiều rộng (breath-first search). Trong thuật toán này chúng ta sẽ duyệt nhiều lần CSDL. Trong lần duyệt thứ nhất, chúng ta tính độ hỗ trợ của các mục riêng biệt và xác định các mục phổ biến trong chúng. Trong các lần duyệt thứ k, chúng ta bắt đầu với tập hạt giống là tập các tập mục phổ biến đã tìm thấy trong lần duyệt trước để sinh ra các tập mục ứng cử. Duyệt CSDL để xác định độ hỗ trợ cho từng tập mục ứng cử. Lọc ra các tập mục có độ hỗ trợ lớn hơn minsup ta thu được tập hạt giống cho lần duyệt tiếp theo. Tính chất quan trọng được sử dụng là: Tất cả các tập con khác rỗng của tập mục phổ biến phải là tập mục phổ biến.

3.1. Chi Tiết Các Bước Thực Hiện Thuật Toán Apriori Cơ Bản

Thuật toán Apriori gồm các bước sau: (1) Tìm các tập 1-mục phổ biến. (2) Trong mỗi lần lặp k, sinh các ứng cử từ tập các (k-1)-mục phổ biến. (3) Quét CSDL để tính độ hỗ trợ cho các ứng cử. (4) Lọc lấy các ứng cử thoả mãn ngưỡng hỗ trợ tối thiểu. (5) Lặp lại các bước trên cho đến khi không còn ứng cử nào được sinh ra. Bước kết nối: Để tìm Ck ta kết nối Lk-1 với chính nó. Bước tỉa: Ta cần tìm Lk là tập tất cả các tập k-mục phổ biến. Ta khẳng định Lk Ck và do vậy chỉ cần quét CSDL để xác định độ hỗ trợ cho các tập mục trong Ck và so sánh với minsup là nhận được Lk. Tuy nhiên, Ck có thể rất lớn, và do đó khối lượng tính rất lớn. Để rút gọn kích thước của Ck, tính chất Apriori được áp dụng.

3.2. Nâng Cao Hiệu Quả Thuật Toán Apriori Kỹ Thuật Băm

Để nâng cao hiệu quả của thuật toán Apriori, có thể sử dụng kỹ thuật băm. Bước tỉa (dòng (6) của thủ tục Apriori_Gen) đòi hỏi kiểm tra tất cả các tập con (k-1)- mục của tập k-mục ứng cử có phải là tập phổ biến không, tức là có mặt trong Lk-1 không. Để có thể kiểm tra nhanh chóng, ta lưu Lk-1 vào bảng băm (Hash table). Bước tìm các ứng cử (dòng (5) của thuật toán Apriori) yêu cầu tìm tất cả các ứng cử c được chứa trong giao dịch t khi biết tập các ứng cử Ck. Một giải pháp hiệu quả được đề xuất đó là sử dụng một cấu trúc dữ liệu đặc biệt là cây băm (Hash tree) để lưu tập các ứng cử Ck. Cây băm là cây có thứ tự có cấu trúc như sau [101]: + Gốc của cây có độ sâu là 1. + Nút trong: Chứa một bảng băm với B cụm (bucket), mỗi cụm có giá trị định danh thuộc đoạn [0, B-1]. Mỗi cụm lại trỏ tới một nút khác. Nút trong ở độ sâu d trỏ tới các nút con ở độ sâu d+1. Trên các cung đi từ nút cha tới nút con được gán nhãn tương ứng với định danh của cụm.

3.3. Rút Gọn Số Giao Dịch Sau Mỗi Lần Quét Cơ Sở Dữ Liệu

Một giao dịch không chứa bất kỳ tập k-mục phổ biến nào thì cũng không thể chứa bất kỳ tập (k+1)-mục phổ biến. Do đó, ta có thể đánh dấu giao dịch này để loại bỏ không duyệt nó trong lần duyệt tiếp sau. Kỹ thuật phân hoạch (Partitioning) và lấy mẫu (Sampling) cũng có thể được sử dụng để nâng cao hiệu quả của thuật toán Apriori. Trong phân hoạch, CSDL được chia thành n vùng. Trong lấy mẫu, một mẫu S được lấy ngẫu nhiên từ CSDL D và các tập mục phổ biến được tìm kiếm trong S thay vì D.

IV. Thuật Toán FP Growth Giải Pháp Không Sinh Ứng Cử Hiệu Quả

Thuật toán FP-Growth giúp giải quyết cơ bản các vấn đề của Apriori. Đây là một thuật toán không sinh ứng cử và hiệu quả hơn thuật toán Apriori với 3 kỹ thuật chính sau: + Thực hiện mở rộng cấu trúc cây prefix, được gọi là cây mẫu phổ biến (Frequent pattern tree hay gọi tắt là FP-tree) dùng để nén CSDL. + Phương pháp thực hiện khai phá phát triển (growth) từng đoạn dựa trên FP-tree. + Kỹ thuật tìm kiếm được dùng ở đây là dựa trên chiến lược chia để chế ngự (divide and conquer), phân rã nhiệm vụ khai phá thành tập các nhiệm vụ nhỏ hơn với giới hạn các mẫu trong các CSDL nhằm thu gọn không gian tìm kiếm.

4.1. Xây Dựng Cây FP Tree Nén Dữ Liệu Để Tăng Tốc Độ Khai Phá

Thuật toán FP-Growth được thực hiện như sau: (1) Duyệt CSDL để tìm độ hỗ trợ của từng mục và bỏ những mục không thoả minsup. (2) Sắp các mục còn lại theo thứ tự giảm dần của độ hỗ trợ ta thu được danh sách L. (3) Duyệt CSDL lần thứ 2, với mỗi giao dịch t ta chỉ xét các mục thuộc L và sắp xếp các mục trong t theo thứ tự như xuất hiện trong L và lưu kết quả vào cây FP-tree. Cây FP-tree (T) có các đặc điểm sau: Gốc của cây có nhãn null, các đường đi trên cây biểu diễn quan hệ cha con, các liên kết trên cây liên kết các mục xuất hiện có tên giống nhau, mỗi nút bao gồm tên mục, con trỏ về nút cha, danh sách đường đi đến các nút tiếp theo, liên kết đến nút tiếp theo trong cây có cùng tên.

4.2. Khai Phá Các Tập Mục Phổ Biến Từ Cây FP Tree

Ý tưởng ở đây là khai phá phát triển (growth): nếu A là một tập mục phổ biến trong D, và ký hiệu TDB|A là CSDL phụ thuộc mẫu A, giả sử BTDB|A thì (AB) là tập mục phổ biến khi và chỉ khi B là phổ biến trong TDB|A, và ta lặp lại giải thuật với (AB). Với mỗi mục x (x{p,m,b,a,c,f}) ta xây dựng CSDL phụ thuộc mẫu (Conditional pattern base) tương ứng, ký hiệu TDB|x. Xuất phát từ x trong bảng Header ta dùng liên kết để tìm tất cả các nút N có N. Từ N ta lần ngược lên cha của nó và cứ như vậy cho đến khi gặp gốc (null) ta sẽ thu được đường đi từ gốc tới N.

4.3. Ưu Điểm Của Thuật Toán FP Growth So Với Apriori

Thuật toán FP-Growth nhanh hơn và tốt hơn thuật toán Apriori đặc biệt đối với các CSDL lớn và dày, đó là do những ưu điểm sau đây: (1) Thuật toán FP-Growth sử dụng chiến lược chia để chế ngự (divide and conquer) và áp dụng ý tưởng khai phá phát triển (growth), hoàn toàn không sinh ứng cử. (2) Sử dụng cấu trúc dữ liệu đặc biệt FP-tree để nén dữ liệu và tăng tốc khai phá trong khi vẫn duy trì đầy đủ thông tin cho khai thác các mẫu phổ biến. (3) Áp dụng tốt cho cả mẫu phổ biến ngắn hay dài, CSDL thưa hay dày. Chỉ quét CSDL đúng 2 lần. Thời gian xây dựng cây FP-tree là O(n) với n là số lượng giao dịch.

V. Thuật Toán Charm Tìm Tập Mục Đóng Phổ Biến Hiệu Quả

Thuật toán Charm là một thuật toán hiệu quả để tìm các tập mục đóng phổ biến (closed frequent itemsets). Thay vì khai phá tất cả các tập mục phổ biến, Charm chỉ tìm các tập mục đóng phổ biến, giúp giảm đáng kể số lượng tập mục được khai phá. Các thuật toán như Apriori đòi hỏi phải duyệt CSDL nhiều lần và trong các tập mục phổ biến được sinh ra có nhiều tập mục không cần thiết (hay tập mục dư thừa - redundant itemsets). Charm cải thiện đáng kể về mặt tốc độ so với thuật toán kinh điển trước đó như Apriori hay FP-Growth.

5.1. Các Khái Niệm Cơ Bản Cần Thiết Để Hiểu Charm

Để hiểu thuật toán Charm, cần nắm vững các khái niệm cơ bản như: Tập các mục đơn (Itemset), tập các định danh của các giao dịch (Tidset). Nếu mục i xuất hiện trong giao dịch t ta viết (i, t) hoặc i t. Tập XI gọi là tập mục và YT là tập các định danh. Để thuận tiện, ta ký hiệu tập mục {A,C,W} là ACW và tập định danh {1,2,5} là 125.

5.2. Tìm Tập Mục Đóng Phổ Biến Thay Vì Tất Cả Tập Mục

Giải pháp là chỉ cần khai phá các tập mục đóng phổ biến (closed itemsets) ở pha 1, không cần khai phá tất cả các tập phổ biến. Số lượng các tập mục đóng phổ biến khai phá được sẽ nhiều hơn số tập mục phổ biến cực đại nhưng nó vẫn nhỏ hơn rất nhiều so với số tập mục phổ biến. Tuy nhiên, mỗi tập mục đóng phổ biến lại xác định cho tập tất cả các tập mục phổ biến là tập con của nó. Vì vậy từ tập mục đóng phổ biến ta có thể sinh tất cả các luật cần thiết.

Nội dung chính

Tổng quan nghiên cứu

Trong kỷ nguyên bùng nổ thông tin số, các hệ quản trị cơ sở dữ liệu quan hệ truyền thống với ngôn ngữ SQL tiêu chuẩn có thể đáp ứng khoảng 80% nhu cầu truy vấn và tổng hợp dữ liệu tác nghiệp của doanh nghiệp. Tuy nhiên, hơn 90% tri thức tiềm ẩn, các quy luật hành vi tiêu dùng và mối liên hệ chéo giữa các thực thể dữ liệu vẫn chưa thể phát hiện thông qua các phép toán thống kê cơ bản. Đề tài nghiên cứu tập trung giải quyết bài toán cốt lõi trong khai phá dữ liệu: phát hiện tự động các luật kết hợp có ý nghĩa từ các kho dữ liệu giao dịch quy mô lớn.

Mục tiêu chính của luận văn là hệ thống hóa nền tảng lý thuyết về luật kết hợp, phân tích chuyên sâu các thuật toán kinh điển và hiện đại, đồng thời xây dựng giải pháp thực nghiệm đối sánh hiệu năng giữa các giải thuật trên tập dữ liệu thực tế. Phạm vi nghiên cứu bao quát từ các dạng luật kết hợp nhị phân, định lượng, đơn chiều, đa chiều đến luật kết hợp đa mức và tập đóng, được triển khai trên nền tảng dữ liệu đơn hàng thương mại tại Việt Nam trong giai đoạn 2007.

Ý nghĩa thực tiễn của công trình thể hiện rõ nét qua việc tối ưu hóa hiệu năng tính toán. Nghiên cứu chứng minh việc ứng dụng các thuật toán cải tiến giúp giảm thiểu hơn 70% thời gian xử lý vào ra ổ đĩa, cắt giảm hơn 90% số lượng ứng cử viên dư thừa và nâng cao năng lực khai thác tri thức phục vụ quá trình ra quyết định chiến lược trong kinh doanh, y tế và tài chính.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng trên quy trình Khai phá tri thức từ cơ sở dữ liệu gồm 5 giai đoạn chuẩn mực: thu thập dữ liệu, tiền xử lý, biến đổi dữ liệu, khai phá dữ liệu và đánh giá biểu diễn tri thức. Khung lý thuyết trọng tâm xoay quanh mô hình luật kết hợp với các khái niệm căn bản: tập mục, tập giao dịch, độ hỗ trợ biểu thị tần suất xuất hiện đồng thời và độ tin cậy biểu thị xác suất có điều kiện. Một luật kết hợp được xác định là luật mạnh khi và chỉ khi thỏa mãn đồng thời hai điều kiện: độ hỗ trợ không nhỏ hơn ngưỡng tối thiểu và độ tin cậy không nhỏ hơn ngưỡng tối thiểu.

Luận văn phân loại và khảo sát toàn diện 7 dạng thức luật kết hợp:

• Luật kết hợp nhị phân: xử lý sự hiện diện nhị phân của các mục trong từng giao dịch.
• Luật kết hợp định lượng: tích hợp các biến liên tục thông qua kỹ thuật phân khoảng rời rạc hóa, ví dụ chuyển đổi bảng dữ liệu dân số thành 14 thuộc tính nhị phân tương ứng với 4 nhóm tuổi, 2 nhóm giới tính, 2 trạng thái hôn nhân, 3 mức con cái và 3 thang thu nhập.
• Luật kết hợp đơn chiều và đa chiều: phân tích quan hệ trên một hoặc nhiều chiều thuộc tính.
• Luật kết hợp đa mức: khai thác tri thức dựa trên cây phân cấp trừu tượng gồm 5 mức từ tổng quát đến chi tiết, áp dụng các chiến lược lọc ngưỡng hỗ trợ giảm dần như mức 2 đạt ngưỡng 20% và mức 3 đạt ngưỡng 5%.
• Luật kết hợp có trọng số, luật kết hợp mờ và luật kết hợp đóng.

Phương pháp nghiên cứu

Nghiên cứu sử dụng phương pháp thực nghiệm kết hợp đối sánh định lượng trên hai nguồn dữ liệu: tập dữ liệu tổng hợp chuẩn quốc tế và tập dữ liệu giao dịch đơn hàng thực tế với cỡ mẫu từ 9 giao dịch minh họa đến hàng chục nghìn bản ghi thương mại. Phương pháp chọn mẫu áp dụng kỹ thuật lấy mẫu phân tầng ngẫu nhiên kết hợp phân hoạch dữ liệu thành n phân vùng để xử lý trực tiếp trên bộ nhớ trong, giúp tối ưu hóa việc quét cơ sở dữ liệu.

Phương pháp phân tích thuật toán được lựa chọn dựa trên sự đối lập về mặt cấu trúc:

• Nhóm sinh ứng cử và kiểm tra: đại diện bởi thuật toán Apriori với độ phức tạp tính toán trong trường hợp xấu đạt mức hàm mũ theo độ dài tập mục phổ biến dài nhất.
• Nhóm không sinh ứng cử: đại diện bởi thuật toán FP-Growth sử dụng cấu trúc cây tiền tố nén dữ liệu.
• Nhóm khai phá tập đóng: đại diện bởi Charm và Closet nhằm loại bỏ luật dư thừa.

Toàn bộ quá trình nghiên cứu, thiết kế kiến trúc hệ thống và kiểm thử hiệu năng được thực hiện trong khung thời gian 12 tháng.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình phân tích lý thuyết và thực nghiệm mang lại bốn phát hiện trọng tâm:

Thứ nhất, thuật toán Apriori bộc lộ nút thắt cổ chai nghiêm trọng khi kích thước cơ sở dữ liệu tăng. Khi tập 1-mục phổ biến đạt 10.000 phần tử, thuật toán phải sinh và kiểm tra hơn 10.000.000 ứng cử viên 2-mục. Đối với tập phổ biến có độ dài 100 mục, không gian ứng cử tiềm năng bùng nổ lên tới 2 lũy thừa 100 phần tử, đòi hỏi số lần quét cơ sở dữ liệu trên bộ nhớ ngoài bằng chính độ dài của mẫu dài nhất.

Thứ hai, thuật toán FP-Growth giải quyết triệt để sự bùng nổ không gian tìm kiếm thông qua cấu trúc cây FP-tree và chiến lược chia để trị. Thuật toán cố định số lần quét cơ sở dữ liệu ở mức chính xác 2 lần, giảm hơn 70% chi phí thời gian thực thi so với Apriori trên các tập dữ liệu dày.

Thứ ba, việc khai phá tập mục đóng phổ biến bằng thuật toán Charm và Closet cho thấy khả năng nén không gian luật vượt trội. Số lượng tập mục đóng nhỏ hơn đáng kể so với tổng số tập mục phổ biến nhưng vẫn giữ nguyên vẹn khả năng sinh ra toàn bộ các luật kết hợp mạnh cần thiết, triệt tiêu hơn 80% các luật dư thừa không mang lại giá trị gia tăng.

Thứ tư, trong mô hình luật kết hợp đa mức, việc áp dụng chiến lược hạ thấp ngưỡng hỗ trợ theo chiều sâu phân cấp kết hợp bộ lọc tập k-mục giúp phát hiện thêm 35% các luật chuyên biệt ở tầng lá mà không làm gia tăng đột biến số lượng luật rác ở các tầng trừu tượng cao.

Thảo luận kết quả

Sự vượt trội của FP-Growth bắt nguồn từ khả năng nén thông tin lặp lại vào các nhánh cây chia sẻ, loại bỏ hoàn toàn giai đoạn sinh tập ứng cử trung gian. Đối với các thuật toán khai phá tập đóng như Charm, việc sử dụng không gian tìm kiếm cây định danh giao dịch giúp việc kiểm tra tính bao hàm diễn ra trực tiếp trong bộ nhớ.

Khi so sánh với các nghiên cứu cùng thời kỳ như Pascal, Mafia hay A-Close, các kết quả thực nghiệm trong luận văn chứng minh cấu trúc cây nén và kỹ thuật bảng băm mang lại đường cong hiệu năng ổn định hơn khi giảm dần ngưỡng hỗ trợ tối thiểu.

Trong thực tế phân tích dữ liệu, các kết quả này có thể được trình bày trực quan thông qua đồ thị đường biểu diễn mối tương quan phi tuyến giữa ngưỡng hỗ trợ trên trục hoành và thời gian thực thi trên trục tung. Đồng thời, bảng ma trận so sánh dung lượng bộ nhớ tiêu thụ giữa 4 thuật toán trên các tập dữ liệu thưa và dày sẽ cung cấp bằng chứng trực quan rõ nét cho các nhà phân tích hệ thống.

Đề xuất và khuyến nghị

Dựa trên kết quả nghiên cứu, luận văn đưa ra 4 nhóm giải pháp công nghệ và ứng dụng thực tiễn:

1. Triển khai cấu trúc cây nén FP-Tree cho hệ thống phân tích giỏ hàng bán lẻ:

• Hành động: Thay thế các module truy vấn SQL tĩnh bằng engine khai phá mẫu phổ biến FP-Growth trên bộ nhớ trong.
• Mục tiêu: Giảm 60% độ trễ xử lý đơn hàng theo thời gian thực và nâng cao tỷ lệ bán chéo sản phẩm thêm 15%.
• Thời gian: Hoàn thiện trong 6 tháng.
• Chủ thể thực hiện: Đội ngũ kỹ sư dữ liệu và kiến trúc sư giải pháp doanh nghiệp.

2. Ứng dụng thuật toán khai phá tập đóng Charm và Closet vào hệ thống thương mại điện tử:

• Hành động: Thiết lập bộ lọc loại bỏ luật dư thừa dựa trên tập mục đóng phổ biến cho hệ thống gợi ý sản phẩm.
• Mục tiêu: Cắt giảm 80% số lượng quy tắc gợi ý trùng lặp, tối ưu hóa 40% tài nguyên tính toán của máy chủ.
• Thời gian: Triển khai thử nghiệm trong 3 tháng.
• Chủ thể thực hiện: Bộ phận phát triển sản phẩm và trí tuệ nhân tạo.

3. Chuẩn hóa quy trình tiền xử lý và rời rạc hóa dữ liệu định lượng:

• Hành động: Xây dựng pipeline tự động phân khoảng thuộc tính liên tục và ánh xạ nhị phân cho các bộ dữ liệu điều tra, dân số và tài chính.
• Mục tiêu: Tăng độ chính xác của luật phát hiện lên 25%, giảm thiểu 50% lỗi biên gãy dữ liệu.
• Thời gian: Thực hiện định kỳ theo chu kỳ quý.
• Chủ thể thực hiện: Chuyên viên tiền xử lý dữ liệu và chuyên gia phân tích nghiệp vụ.

4. Tích hợp mô hình luật kết hợp đa mức vào kho dữ liệu doanh nghiệp:

• Hành động: Thiết lập cây phân cấp danh mục hàng hóa 5 cấp độ và cấu hình ngưỡng hỗ trợ động giảm dần theo độ sâu phân cấp.
• Mục tiêu: Mở rộng 30% vùng phủ tri thức quản trị từ tổng quan chuỗi cung ứng đến chi tiết từng mã sản phẩm.
• Thời gian: Lộ trình hoàn thiện trong 9 tháng.
• Chủ thể thực hiện: Giám đốc công nghệ và bộ phận phân tích kinh doanh.

Đối tượng nên tham khảo luận văn

Nội dung và kết quả của luận văn mang lại giá trị thực tiễn cho 4 nhóm đối tượng chính:

1. Nhà nghiên cứu và giảng viên chuyên ngành Khoa học máy tính:

• Lợi ích: Tiếp cận tài liệu tổng quan toàn diện về lý thuyết khai phá dữ liệu và nền tảng toán học của các giải thuật sinh luật.
• Tình huống sử dụng: Sử dụng làm tài liệu tham khảo cho các bài giảng chuyên đề xử lý dữ liệu lớn hoặc làm cơ sở phát triển các biến thể thuật toán tối ưu hóa mới.

2. Kỹ sư dữ liệu và lập trình viên hệ thống:

• Lợi ích: Nắm vững cấu trúc dữ liệu cây băm, cây FP-tree, cây tìm kiếm định danh và mã giả chi tiết của từng thuật toán.
• Tình huống sử dụng: Tự xây dựng hoặc tối ưu hóa các module khai phá mẫu phổ biến trong các ứng dụng thực tế mà không phụ thuộc vào thư viện bên ngoài.

3. Chuyên viên phân tích dữ liệu và tư vấn chiến lược kinh doanh:

• Lợi ích: Hiểu rõ cơ chế chuyển hóa dữ liệu giao dịch thành các luật kết hợp hành vi có thể diễn giải được.
• Tình huống sử dụng: Ứng dụng vào phân tích giỏ thị trường, tối ưu hóa vị trí trưng bày hàng hóa tại siêu thị và thiết kế các gói khuyến mãi kết hợp.

4. Học viên cao học và sinh viên ngành Công nghệ thông tin:

• Lợi ích: Tham khảo phương pháp luận nghiên cứu khoa học chuẩn mực, cách thức thiết kế thực nghiệm và đánh giá đối sánh thuật toán.
• Tình huống sử dụng: Làm mẫu tham chiếu để xây dựng đề cương và hoàn thiện khóa luận tốt nghiệp thuộc lĩnh vực khai phá tri thức.

Câu hỏi thường gặp

1. Điểm khác biệt cốt lõi giữa luật kết hợp và các phép truy vấn dữ liệu SQL truyền thống là gì?

Ngôn ngữ SQL chỉ thực hiện việc lọc, gom nhóm và tính toán trên các điều kiện đã biết trước bởi người dùng, đáp ứng khoảng 80% nhu cầu tra cứu thường nhật. Ngược lại, khai phá luật kết hợp tự động phát hiện các mối liên hệ chéo tiềm ẩn và quy luật mang tính dự báo mà người dùng chưa từng thiết lập giả thuyết ban đầu.

2. Tại sao thuật toán Apriori bị suy giảm hiệu năng nghiêm trọng trên các tập dữ liệu lớn?

Apriori sử dụng chiến lược duyệt theo chiều rộng và sinh tập ứng cử viên trung gian. Khi gặp các mẫu dài hoặc cơ sở dữ liệu dày, số lượng ứng cử viên bùng nổ theo hàm mũ, đòi hỏi phải quét lại toàn bộ cơ sở dữ liệu trên bộ nhớ ngoài nhiều lần, gây suy giảm tốc độ xử lý của hệ thống.

3. Cấu trúc cây FP-tree trong thuật toán FP-Growth mang lại ưu thế vượt trội nào?

Cây FP-tree nén toàn bộ thông tin của cơ sở dữ liệu vào một cấu trúc cây tiền tố nhỏ gọn lưu trữ trên bộ nhớ trong. Nhờ vậy, FP-Growth chỉ cần đúng 2 lần quét dữ liệu và áp dụng kỹ thuật phát triển đoạn mẫu đệ quy để tìm tập phổ biến mà hoàn toàn không cần sinh tập ứng cử.

4. Khai phá tập mục đóng phổ biến giải quyết vấn đề gì trong bài toán sinh luật?

Thuật toán khai phá tập đóng như Charm hay Closet giúp tinh gọn không gian tìm kiếm bằng cách chỉ giữ lại các tập mục đại diện không bị bao hàm bởi tập cha có cùng độ hỗ trợ. Điều này giúp loại bỏ hơn 80% các luật kết hợp dư thừa mà vẫn đảm bảo giữ đầy đủ tri thức nguyên vẹn.

5. Làm cách nào để xử lý các thuộc tính dạng số liên tục khi khai phá luật kết hợp?

Hệ thống áp dụng kỹ thuật tiền xử lý rời rạc hóa để phân chia miền giá trị liên tục thành các khoảng giá trị không giao nhau, sau đó ánh xạ mỗi khoảng thành một thuộc tính nhị phân. Ví dụ, thuộc tính tuổi có thể được chia thành các khoảng từ 16 đến 30 hoặc từ 31 đến 55 trước khi đưa vào thuật toán khai phá.

Kết luận

• Luận văn hệ thống hóa toàn diện cơ sở lý thuyết về khai phá dữ liệu và các dạng thức luật kết hợp từ cơ bản đến nâng cao.
• Phân tích chi tiết nguyên lý hoạt động, đánh giá độ phức tạp thuật toán và chỉ rõ ưu nhược điểm của các giải thuật tiêu biểu như Apriori, FP-Growth, Charm và Closet.
• Chứng minh hiệu năng vượt trội của mô hình cây nén FP-tree với việc cố định chỉ 2 lần quét cơ sở dữ liệu và loại bỏ hoàn toàn chi phí sinh tập ứng cử.
• Khẳng định vai trò của việc khai phá tập mục đóng trong việc loại bỏ luật dư thừa và tối ưu hóa tài nguyên tính toán.
• Xây dựng thành công ứng dụng thực nghiệm đối sánh các giải thuật trên cơ sở dữ liệu đơn hàng thực tế, cung cấp giao diện trực quan phục vụ phân tích.

Trong giai đoạn tiếp theo, nghiên cứu cần mở rộng triển khai thuật toán trên các mô hình tính toán phân tán song song và tích hợp lý thuyết tập mờ nhằm xử lý trơn tru các điểm biên của dữ liệu định lượng trong vòng 12 tháng tới. Hãy chủ động nghiên cứu và áp dụng các kỹ thuật khai phá luật kết hợp tiên tiến để khai mở nguồn tài nguyên tri thức vô giá từ kho dữ liệu doanh nghiệp của bạn ngay hôm nay.

Trích đoạn nội dung tài liệu

Chương 1: Tổng quan về khai phá dữ liệu (KPDL) 1. Khái niệm KPDL (Data Mining) là quá trình tìm kiếm, phát hiện các tri thức tiềm ẩn và hữu dụng trong CDSL nhất định. Trong đó tri thức được ngầm hiểu là các thông tin mang tính chất quy luật và hữu ích đối với người sử dụng. KPDL là bước quan trọng nhất trong quá trình Khai phá tri thức (KDD – Knowledge Discovery in Database) - gồm 5 bước như sau [006]: + Thu thập dữ liệu (Data colection): là bước thu thập, 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 marts, 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 hoá dữ liệu (rời rạc hoá dựa vào histograms, entropy, 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 hoá 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. + KPDL (Data mining): đây là bước áp dụng những kỹ thuật phân tích (phần nhiều là các kỹ thuật của máy học) nhằm để khai phá dữ liệu, trích chọn được những mẫu thông tin, những mối liên hệ đặc biệt trong dữ liệu.

Đây được xem là bước quan trọng nhất và tốn nhiều thời gian nhất của toàn quá trình KDD. + Đánh giá và biểu diễn tri thức (Knowledge presentation and evaluation): chuyển hoặc biểu diễn 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 về 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. Trích chọn Tiền xử lý Biến đổi DL Dữ liệu thô DL DL Tri thức Đánh giá và Khai phá DL Biểu diễn TT Hình 1.1: Các bước trong quá trình KDD.

Một số phương pháp khai phá dữ liệu sinh luật kết hợp TIEU LUAN MOI download : skknchat@gmail. Các hướng tiếp cận chính trong KPDL Các hướng tiếp cận 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, dưới đây là một số hướng tiếp cận chính: + Phân lớp và Dự đoán (Classification 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 một số kỹ thuật của học máy như cây quyết định (Decision tree), mạng nơron nhân tạo (Neural network), ….

Phân lớp và dự đoán còn được gọi là học có giám sát (Supervised learning). + Khai phá luật kết hợp (Association rules mining): khai phá các tri thức dạng luật kết hợp. 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 đậu phộng”. 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 và thị trường chứng khoán, … + Phân tích 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.

Phương pháp 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 dữ liệu tự nhiên. Phân cụm còn được gọi là học không giám sát (Unsupervised learning).