Luận văn: Các tập mục thường xuyên trong khai phá dữ liệu và ứng dụng

Luận văn thạc sĩ về các tập mục thường xuyên trong khai phá dữ liệu. Nghiên cứu ứng dụng các thuật toán khai phá tập mục, phân tích dữ liệu hiệu quả.

• Tác giả: Hoàng Minh Quang
• Người hướng dẫn: Pgs. Vũ Đức Thi
• 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: Công Nghệ Thông Tin
• Đề tài: Các Tập Mục Thường Xuyên Trong Khai Phá Dữ Liệu Và Ứng Dụng
• Loại tài liệu: Luận Văn Thạc Sỹ
• Năm xuất bản: 2010
• Địa điểm: Hà Nội

Mục lục chi tiết

• MỤC LỤC
• DANH MỤC VIẾT TẮT VÀ KÝ HIỆU
• DANH MỤC BẢNG BIỂU, HÌNH ẢNH
• 1. KHAI PHÁ TẬP MỤC THƯỜNG XUYÊN
• 1.1. Một số khái niệm cơ bản về tập mục
• 1.2. Tập mục thường xuyên và luật kết hợp
• 1.3. Mô tả bài toán khai phá luật kết hợp
• 1.4. Một số thuật toán khai phá tập mục thường xuyên và luật kết hợp
• 1.5. Thuật toán Apriori
• 1.6. Thuật toán FP-Growth
• 2. CÁC BÀI TOÁN MỞ RỘNG KHAI PHÁ TẬP MỤC THƯỜNG XUYÊN
• 2.1. Một số nghiên cứu chuyên sâu về khai phá luật kết hợp
• 2.2. Khai phá tập mục cổ phần cao
• 2.3. Khai phá tập mục lợi ích cao
• 3. CÀI ĐẶT ỨNG DỤNG THỬ NGHIỆM KHAI PHÁ TẬP MỤC LỢI ÍCH CAO
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Khai Phá Tập Mục Thường Xuyên và Ứng Dụng

Sự phát triển của CNTT và Internet đã tạo ra lượng lớn dữ liệu. Việc khai thác thông tin từ các cơ sở dữ liệu lớn là rất quan trọng để hỗ trợ ra quyết định. Khai phá dữ liệu và khám phá tri thức là một lĩnh vực quan trọng. Khai phá tập mục thường xuyên là một bài toán con của khai phá luật kết hợp, được giới thiệu bởi Agrawal năm 1993. Nó phân tích cơ sở dữ liệu bán hàng, tìm ra những mặt hàng được mua cùng nhau. Thông tin này giúp người quản lý kinh doanh tiếp thị và sắp xếp hàng hóa hiệu quả hơn. Khai phá tập mục thường xuyên gặp khó khăn khi xử lý cơ sở dữ liệu lớn. Đã có nhiều nghiên cứu về cách thức mở rộng và ứng dụng. Tuy nhiên, đây vẫn là một bài toán khó. Mục đích của bài viết này là tìm hiểu và nghiên cứu về các thuật toán khai phá tập mục thường xuyên phổ biến nhất, đem lại cái nhìn tổng quan về khai phá tập mục thường xuyên và luật kết hợp.

1.1. Giới Thiệu về Bài Toán Khai Phá Luật Kết Hợp

Khai phá tập mục thường xuyên đóng vai trò quan trọng trong nhiều nhiệm vụ khai phá dữ liệu. Nó xuất hiện như một bài toán con của nhiều lĩnh vực như khám phá luật kết hợp, khám phá mẫu tuần tự, phân tích tương quan, phân lớp, phân cụm dữ liệu, khai phá Web. Bài toán này được giới thiệu lần đầu bởi Agrawal vào năm 1993. Khai phá luật kết hợp 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. Khai phá luật kết hợp có hai bước: tìm các tập mục thường xuyên thỏa mãn ngưỡng độ hỗ trợ tối thiểu, và sinh ra các luật kết hợp thỏa mãn ngưỡng độ tin cậy tối thiểu. Mọi khó khăn tập trung ở bước thứ nhất, đó là khai phá tập mục thường xuyên.

1.2. Ứng Dụng Thực Tế Của Khai Phá Tập Mục Thường Xuyên

Kể từ khi Agrawal đề xuất, khai phá tập mục thường xuyên đã thu hút được sự quan tâm của nhiều nhà nghiên cứu. Đã có hàng trăm kết quả nghiên cứu được công bố giới thiệu các thuật toán mới hay đề xuất các giải pháp nâng cao hiệu quả các thuật toán đã có. Tập mục thường xuyên đã có vai trò quan trọng trong nhiều ứng dụng thực tế như quản lý quan hệ khách hàng, nâng cao hiệu quả của thương mại điện tử, trong lĩnh vực tin sinh học, phân tích cấu trúc Protein và DNA, mở rộng truy vấn, phát hiện xâm nhập mạng. Mô hình khai phá tập mục thường xuyên cơ bản có nhiều ứng dụng trong thực tế nhưng có những hạn chế, không đáp ứng đầy đủ yêu cầu của người sử dụng. Ràng buộc về độ hỗ trợ và độ tin cậy của luật kết hợp chỉ mang ngữ nghĩa thống kê, không phản ánh được vai trò khác nhau của các thuộc tính cũng như đặc tính dữ liệu vốn có của chúng trong cơ sở dữ liệu.

1.3. Mở Rộng và Ứng Dụng Trong Thực Tiễn

Để đáp ứng yêu cầu của thực tiễn, khai phá tập mục thường xuyên đã có nhiều cách thức mở rộng và ứng dụng, từ thay đổi phương pháp luận đến thay đổi đa dạng các kiểu dữ liệu, mở rộng các nhiệm vụ khai phá và đa dạng các ứng dụng mới. Trong những năm qua, đã có nhiều hướng mở rộng bài toán được quan tâm nghiên cứu. Một số khái niệm cơ bản cần nắm vững bao gồm: định nghĩa về tập mục, giao tác, cơ sở dữ liệu giao tác, và k-tập mục. Cách biểu diễn cơ sở dữ liệu giao tác cũng rất quan trọng, bao gồm biểu diễn ngang, biểu diễn dọc, và biểu diễn bởi ma trận giao tác.

II. Khái Niệm Quan Trọng Tập Mục Thường Xuyên Luật Kết Hợp

Cho tập mục X ⊆ I. Độ hỗ trợ (Support) của tập mục X trong cơ sở dữ liệu giao tác DB, ký hiệu sup(X), là tỷ lệ phần trăm của các giao tác chứa tập mục X trên tổng số giao tác trong DB. Cho tập mục X⊆I với ngưỡng hộ trợ tối thiểu (minimum support) minsup ∈ [0,1]. X được gọi là tập mục thường xuyên (frequent itemset hoặc large itemset) với độ hỗ trợ tối thiểu minsup nếu sup(X) ≥ minsup, ngược lại X gọi là tập mục không thường xuyên. Một luật kết hợp là một biểu thức dạng X →Y, trong đó X và Y là các tập con của I, X∩Y=∅; X gọi là tiên đề, Y gọi là kết luận của luật. Luật kết hợp có hai thông số quan trọng là độ hỗ trợ và độ tin cậy.

2.1. Định Nghĩa Độ Hỗ Trợ Support và Ngưỡng Hỗ Trợ Tối Thiểu

Độ 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 của X và Y trong một giao tác. Độ tin cậy (confidence) luật kết hợp, ký hiệu là conf(X→Y), là tỷ lệ phần trăm giữa số giao tác chứa X∪Y và số giao tác chứa X trong cơ sở dữ liệu DB. Bài toán khai phá luật kết hợp là xác định tất cả X⇒Y thỏa mãn độ hỗ trợ và độ tin cậy tối thiểu. Các tập mục thường xuyên có tính chất quan trọng sau: nếu X, Y là các tập mục và X ⊆ Y thì sup(X) ≥ sup(Y). Nếu một tập mục là không thường xuyên thì mọi tập cha của nó cũng là không thường xuyên. Nếu một tập mục là thường xuyên thì mọi tập con khác rỗng của nó cũng là tập mục thường xuyên. Tính chất Apriori là cơ sở để rút gọn không gian tìm kiếm các tập mục thường xuyên.

2.2. Mô Tả Bài Toán Khai Phá Luật Kết Hợp

Khai phá luật kết hợp là một kỹ thuật quan trọng của khai phá dữ liệu. Vấn đề này được Rakesh Agrawal, Tomasz Imielinski, Arun Swami đề xuất lần đầu vào năm 1993. Ngày nay bài toán khai thác các luật kết hợp nhận được rất nhiều sự quan tâm của nhiều nhà khoa học. Việc khai thác các luật như thế nào vẫn là một trong các phương pháp khai thác mẫu phổ biến nhất trong việc khám phá tri thức và khai thác dữ liệu (KDD). Mục đích chính của khai phá dữ liệu là trích rút tri thức một cách tự động, hiệu quả và “thông minh” từ kho dữ liệu.

2.3. Tiếp Cận Khai Phá Tập Mục Thường Xuyên và Luật Kết Hợp

Các nghiên cứu về khai phá tập mục thường xuyên tập trung vào tìm các thuật toán mới hoặc đề xuất giải pháp nâng cao hiệu quả các thuật toán đã có. Bài toán khai phá tập mục thường xuyên: tìm các tập mục ứng viên và tìm các tập mục thường xuyên. Tập mục ứng viên là tập mục mà ta hy vọng nó là tập mục thường xuyên, phải tính độ hỗ trợ của nó để kiểm tra. Tập mục thường xuyên là tập mục có độ hỗ trợ lớn hơn hoặc bằng ngưỡng tối thiểu cho trước. Có thể phân loại thuật toán theo hai tiêu chí: phương pháp duyệt qua không gian tìm kiếm và phương pháp xác định độ hỗ trợ của tập mục.

III. Các Thuật Toán Khai Phá Tập Mục Thường Xuyên Phổ Biến

Các thuật toán khai phá tập mục thường xuyên có thể được phân loại dựa trên phương pháp duyệt qua không gian tìm kiếm (duyệt theo chiều rộng hoặc chiều sâu) và phương pháp xác định độ hỗ trợ của tập mục (đếm số giao tác chứa X hoặc tính phần giao của các tập chứa định danh của các giao tác chứa X). Có nhiều tiếp cận khác nhau để khai phá luật kết hợp, bao gồm luật kết hợp nhị phân, luật kết hợp có thuộc tính số và thuộc tính hạng mục, luật kết hợp tiếp cận theo hướng tập thô, luật kết hợp nhiều, luật kết hợp mờ, luật kết hợp với thuộc tính được đánh trọng số, và khai thác luật kết hợp song song.

3.1. Thuật Toán Apriori Nguyên Lý và Ưu Nhược Điểm

Ý tưởng chính của thuật toán Apriori là: sinh ra các tập mục ứng viên từ các tập mục thường xuyên ở bước trước, sử dụng kỹ thuật tỉa để bỏ bớt đi những tập mục ứng viên không thỏa mãn ngưỡng hỗ trợ tối thiểu (minsup). Cơ sở của thuật toán này là tính chất Apriori “Bất kỳ tập con nào của tập mục thường xuyên cũng phải là tập mục thường xuyên”. Thuật toán giúp tỉa bớt những tập ứng viên có tập con không thường xuyên trước khi tính độ hỗ trợ. Nhược điểm của thuật toán là chi phí sinh ra số lượng khổng lồ tập ứng viên và phải duyệt cơ sở dữ liệu nhiều lần. Thuật toán Apriori gồm hai giai đoạn chính: sinh tập ứng viên và tỉa tập ứng viên.

3.2. Thuật Toán FP Growth Giải Pháp Khắc Phục Nhược Điểm Apriori

Phát triển từ thuật toán Apriori, J.Mao đã đề xuất thuật toán FP-growth nhằm khắc phục những hạn chế của thuật toán Apriori. Thuật toán này được xây dựng với ba kỹ thuật chính là: Nén dữ liệu thích hợp vào một cấu trúc cây gọi là FP-tree. Chỉ có 1–tập mục ở trong cây và các nút của cây được sắp xếp để các nút xuất hiện thường xuyên hơn có thể dễ dàn chia sẻ với các nút xuất hiện ít hơn; Thực hiện phương pháp khai phá phát triển (growth) từng đoạn dựa trên cây FP-tree gọi là phương pháp FP-growth; Kỹ thuật tìm kiếm được dùng ở đây là dựa vào sự phân chia, “chia để trị”, phân rã nhiệm vụ khai phá thành nhiệm vụ nhỏ hơn.

3.3. Các Thuật Toán Khai Phá Tập Mục Thường Xuyên Khác

Ngoài Apriori và FP-Growth, còn rất nhiều các thuật toán khai phá tập mục thường xuyên khác có thể kể đến như: AIS, SETM, CHARM, Pincer-Search, Max-Miner, DepthProject, MAFIA, MFI, GenMax, v.v… Tuy nhiên, mỗi thuật toán có những ưu nhược điểm riêng và phù hợp với từng loại dữ liệu khác nhau. Việc lựa chọn thuật toán phù hợp là yếu tố quan trọng để đạt hiệu quả cao trong khai phá dữ liệu.

IV. Các Bài Toán Mở Rộng Khai Phá Tập Mục Thường Xuyên

Mô hình khai phá tập mục thường xuyên cơ bản có nhiều ứng dụng trong thực tế nhưng nó có những hạn chế, không đáp ứng đầy đủ yêu cầu của người sử dụng. Ràng buộc về độ hỗ trợ của tập mục thường xuyên chủ yếu mang ngữ nghĩa thống kê, không phản ánh được vai trò khác nhau của các thuộc tính cũng như đặc tính dữ liệu vốn có của chúng trong cơ sở dữ liệu. Để đáp ứng yêu cầu của thực tiễn, bài toán khai phá tập mục thường xuyên đã có nhiều cách thức mở rộng và ứng dụng.

4.1. Khai Phá Luật Kết Hợp Chuyên Sâu Hướng Nghiên Cứu Mới

Một hướng mở rộng bài toán có nhiều ứng dụng là quan tâm đến cấu trúc dữ liệu và mức độ quan trọng khác nhau của các mục dữ liệu, các thuộc tính trong cơ sở dữ liệu. Một số mô hình mở rộng bài toán đã được nghiên cứu là: Quan tâm đến mức độ quan trọng khác nhau của các mục dữ liệu bằng cách gán cho mỗi mục một giá trị được gọi là trọng số. Quan tâm đến các kiểu thuộc tính khác nhau trong cơ sở dữ liệu như nhị phân, đa phân, định lượng. Chú ý đến cả cấu trúc dữ liệu và mức độ quan trọng khác nhau của các thuộc tính trong cơ sở dữ liệu.

4.2. Khai Phá Tập Mục Cổ Phần Cao Định Nghĩa và Ứng Dụng

Năm 1997, Hiderman và các cộng sự đề xuất bài toán khai phá tập mục cổ phần cao. Trong mô hình này, giá trị của mục dữ liệu trong giao tác là một số, số đó có thể là số nguyên. Cổ phần của một tập mục là số đo tỷ lệ đóng góp của tập mục trong cơ sở dữ liệu. Khai phá tập mục cổ phần cao là khám phá tất cả cac tập mục có cổ phần không nhỏ hơn ngưỡng quy định bởi người sử dụng. Trong bài toán cơ bản, các thuật toán khám phá được xây dựng theo phương pháp tìm kiếm từng bước. Cơ sở của các thuật toán là tính chất Apriori của tập mục thường xuyên. Trong mô hình khai phá tập mục cổ phần cao, tính chất này không còn đúng nữa.

4.3. Khai Phá Tập Mục Lợi Ích Cao Tiếp Cận Mới Trong Khai Phá

Khai phá tập mục lợi ích cao là sự mở rộng, tổng quát hóa của khai phá tập mục cổ phần cao. Mô hình khai phá tập mục lợi ích cao được Yao và cộng sự đề xuất. Trong mô hình khai phá tập mục lợi ích cao, giá trị của mục dữ liệu trong giao tác là một số, ngoài ra còn có bảng lợi ích cho biết lợi ích mang lại khi bán một đơn vị hàng đó. Lợi ích của một tập mục là số đo lợi nhuận mà tập mục đó đóng góp trong cơ sở dữ liệu. Khai phá tập mục lợi ích cao là khám phá tất cả các tập mục lợi ích không nhỏ hơn ngưỡng lợi ích tối thiểu quy định bởi người sử dụng.

V. Thuật Toán FSM Giải Pháp Khai Phá Tập Mục Cổ Phần Cao

Năm 2005, Yu-Chiang Li và đồng nghiệp giới thiệu thuật toán FSM (Fast Share Measure). Đây là thuật toán hiệu quả tìm ra tất cả các tập mục cổ phần cao. Thay vì khai thác tính chất Apriori, thuật toán FSM sử dụng một số tính chất của tập mục cổ phần cao để rút gọn các tập mục ứng viên. Hàm tới hạn CF(X) được sử dụng để thu gọn tập các tập mục ứng viên. Mệnh đề 2.1 nêu rõ điều kiện để một k-tập mục không là tập mục cổ phần cao. Nội dung thuật toán FSM bao gồm việc duyệt nhiều lần cơ sở dữ liệu và sử dụng hàm CF(X) để tỉa các ứng viên không tiềm năng.

5.1. Cơ Sở Lý Thuyết Của Thuật Toán FSM

Cơ sở lý thuyết của thuật toán FSM dựa trên các khái niệm như: Giá trị cổ phần tối thiểu min_lmv = minShare * Tmv; Độ dài cực đại của các giao tác trong cơ sở dữ liệu; Giá trị cực đại của tất cả các mục trong cơ sở dữ liệu; Mệnh đề 2.1 về điều kiện để một k-tập mục không là tập mục cổ phần cao. Dựa trên các khái niệm và mệnh đề này, thuật toán FSM có thể loại bỏ các tập mục ứng viên không tiềm năng, từ đó giảm thiểu thời gian tính toán và cải thiện hiệu suất khai phá.

5.2. Mô Tả Chi Tiết Thuật Toán FSM

Thuật toán duyệt nhiều lần cơ sở dữ liệu, ở lần duyệt thứ k, Ck lưu các tập mục ứng viên, RCk lưu các tập mục nhận được sau khi kiểm tra hàm CF, Fk lưu các tập mục cổ phần cao nhận được. Giống như thuật toán Apriori, ban đầu mỗi mục dữ liệu làm một ứng viên. Trong lần duyệt thứ nhất, thuật toán duyệt cơ sở dữ liệu, tính giá trị của mỗi mục dữ liệu. Mỗi ứng viên 1-tập mục X sẽ bị tỉa nếu CF(X) < min_lmv.

5.3. Ưu Điểm và Hạn Chế Của Thuật Toán FSM

Thuật toán FSM có ưu điểm là tương đối dễ hiểu, sau khi thực hiện tìm được tập F chứa tất cả các tập mục cổ phần cao. Đây là một thuật toán tốt để khai phá tập mục cổ phần cao. Tuy vậy, thuật toán còn một số hạn chế. Thuật toán sử dụng hàm tới hạn CF(X) để thu gọn tập các tập mục ứng viên nhưng thực tế số các tập mục của tập RCk vẫn còn lớn do giá trị hàm tới hạn CF(X) còn cao, chưa sát với giá trị thực của các tập mục trong RCk.

VI. Thuật Toán AFSM Cải Tiến Hiệu Quả Cho Khai Phá Cổ Phần

Thuật toán AFSM là một cải tiến của thuật toán FSM, nhằm nâng cao hiệu quả khai phá tập mục cổ phần cao. Cơ sở lý thuyết của thuật toán AFSM dựa trên khái niệm “giá trị theo giao tác tập mục”, “tập mục cổ phần theo giao tác cao” và chứng minh tập mục cổ phần theo giao tác có tính chất phản đơn điệu. Mệnh đề 2.6 và 2.7 trình bày các tính chất quan trọng liên quan đến tập mục cổ phần theo giao tác. Nhờ đó, thuật toán AFSM có thể tỉa các tập mục ứng viên hiệu quả hơn.

6.1. Cơ Sở Lý Thuyết Của Thuật Toán AFSM

Ràng buộc cổ phần không có tính chất phản đơn điệu như tập mục thường xuyên. Để khắc phục điều này, khái niệm “giá trị theo giao tác tập mục”, “tập mục cổ phần theo giao tác cao” được đề xuất và chứng minh có tính chất phản đơn điệu. Điều này cho phép tỉa các tập mục ứng viên một cách hiệu quả.

6.2. Mô Tả Thuật Toán AFSM và Các Bước Thực Hiện

Thuật toán AFSM giữ nguyên các bước của thuật toán FSM. Tuy nhiên, ở bước lặp thứ k, hàm Apriori-gen nối các cặp (k-1)-tập mục trong RCk-1 để được tập ứng viên Ck. Sau khi duyệt cơ sở dữ liệu để tính giá trị lmv(X) và tmv(X) của các ứng viên X∈Ck, thuật toán tỉa ứng viên X∈Ck nếu tmv(X) <min_lmv.

6.3. So Sánh AFSM và FSM Ưu Điểm Vượt Trội

Để so sánh thuật toán FSM và AFSM, có thể phân tích hai hàm tới hạn mà chúng sử dụng. Mệnh đề 2.8 so sánh giá trị hai hàm tới hạn và chứng minh hàm tới hạn mới nhỏ hơn hàm tới hạn cũ. Điều này đảm bảo thuật toán AFSM thực hiện hiệu quả hơn thuật toán FSM. Việc cải tiến bước sinh tập ứng viên Ck theo phương pháp Fk-1×F1 cũng góp phần nâng cao hiệu suất.

Nội dung chính

Tổng quan nghiên cứu

Khai phá dữ liệu và khám phá tri thức đóng vai trò then chốt trong việc chuyển hóa các kho dữ liệu khổng lồ thành thông tin chiến lược hỗ trợ quá trình ra quyết định. Kể từ khi bài toán khai phá luật kết hợp được khởi xướng vào năm 1993, việc tìm kiếm các tập mục thường xuyên đã trở thành nền tảng quan trọng bậc nhất của khai phá dữ liệu. Trong thực tế hoạt động kinh doanh bán lẻ, các hệ thống thường phải xử lý hàng triệu giao dịch mỗi ngày nhằm xác định những mặt hàng thường xuyên được mua cùng nhau với ngưỡng độ hỗ trợ từ 20% đến 40% và ngưỡng độ tin cậy từ 80% đến 90%. Thông tin này cho phép các nhà quản trị tối ưu hóa không gian trưng bày, xây dựng chiến lược tiếp thị chéo và nâng cao đáng kể doanh số bán hàng.

Tuy nhiên, mô hình khai phá tập mục thường xuyên truyền thống dựa trên logic nhị phân thuần túy đang bộc lộ những hạn chế nghiêm trọng. Mô hình này chỉ ghi nhận sự xuất hiện của mục dữ liệu dưới dạng 0 hoặc 1 mà hoàn toàn bỏ qua số lượng mua thực tế cũng như giá trị lợi nhuận biên của từng mặt hàng. Luận văn thạc sĩ chuyên ngành Hệ thống thông tin của tác giả Hoàng Minh Quang, dưới sự hướng dẫn của PGS. Vũ Đức Thi tại Trường Đại học Công nghệ – Đại học Quốc gia Hà Nội, tập trung giải quyết bài toán cốt lõi này. Mục tiêu nghiên cứu cụ thể là khảo sát toàn diện các thuật toán kinh điển, đồng thời mở rộng không gian bài toán sang hai hướng tiếp cận hiện đại: khai phá tập mục cổ phần cao và khai phá tập mục lợi ích cao. Nghiên cứu mang lại ý nghĩa học thuật và ứng dụng to lớn khi giúp giảm thiểu trên 50% không gian tìm kiếm ứng viên vô ích và nâng cao hiệu quả phân bổ nguồn lực kinh doanh trong các doanh nghiệp thương mại.

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

Khung lý thuyết áp dụng

Luận văn xây dựng trên nền tảng khung lý thuyết khám phá tri thức từ cơ sở dữ liệu kết hợp với lý thuyết tập mục thường xuyên và luật kết hợp do Rakesh Agrawal cùng các cộng sự khởi xướng. Hệ thống lý thuyết tiếp tục mở rộng sang mô hình định lượng và lợi ích kinh tế với các khái niệm then chốt sau:

• Tập mục thường xuyên: Tập hợp các mục dữ liệu xuất hiện đồng thời trong cơ sở dữ liệu với tần suất không thấp hơn một ngưỡng độ hỗ trợ tối thiểu định trước.
• Luật kết hợp: Biểu thức dạng kéo theo phản ánh mối quan hệ phụ thuộc giữa các tập mục, được xác định thông qua hai tham số xác suất thống kê là độ hỗ trợ và độ tin cậy.
• Tính chất phản đơn điệu: Nguyên lý xác định rằng mọi tập con khác rỗng của một tập mục thường xuyên đều phải là tập mục thường xuyên, đóng vai trò là cơ sở triệt tiêu không gian ứng viên trong thuật toán Apriori.
• Cổ phần của tập mục: Chỉ số đo lường tỷ lệ phần trăm đóng góp của giá trị các mặt hàng trong tập mục trên tổng giá trị của toàn bộ cơ sở dữ liệu giao tác.
• Lợi ích của tập mục: Hàm kết hợp giữa giá trị khách quan là số lượng thực tế trong từng giao dịch và giá trị chủ quan là biên độ lợi nhuận trên mỗi đơn vị sản phẩm do nhà quản lý quy định.

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

Luận văn kết hợp phương pháp mô hình hóa toán học, phân tích độ phức tạp thuật toán và thực nghiệm kiểm chứng trên môi trường máy tính. Dữ liệu nghiên cứu bao gồm bộ cơ sở dữ liệu giao tác tổng hợp và dữ liệu giao dịch bán hàng mô phỏng với quy mô từ 10 đến 11 giao tác mẫu có độ phức tạp cao, kiểm thử các trường hợp cực hạn với độ dài giao tác tối đa là 7 và giá trị thuộc tính cực đại là 4.

Phương pháp chọn mẫu có chủ đích được áp dụng nhằm tạo ra các tập dữ liệu có cấu trúc từ thưa đến dày, giúp đánh giá chính xác độ nhạy của thuật toán trước các ngưỡng hỗ trợ và ngưỡng lợi ích khác nhau. Nghiên cứu lựa chọn phân tích thuật toán cấu trúc cây và phép chứng minh toán học định lý chặn trên vì phương pháp này cho phép so sánh định lượng trực tiếp số lượng tập ứng viên sinh ra, dung lượng bộ nhớ tiêu thụ và thời gian xử lý giữa các thuật toán đối sánh. Toàn bộ tiến trình nghiên cứu lý thuyết, phát triển thuật toán cải tiến và lập trình thử nghiệm được triển khai đồng bộ trong mốc 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 thuật toán và kiểm nghiệm thực nghiệm đã làm sáng tỏ bốn phát hiện học thuật cốt lõi:

Thứ nhất, thuật toán kinh điển Apriori bộc lộ điểm nghẽn nghiêm trọng khi xử lý cơ sở dữ liệu quy mô lớn. Đối với một tập dữ liệu có 10.000 mục thường xuyên, thuật toán phải sinh ra hơn 10.000.000 tập ứng viên 2-mục và thực hiện số lần quét cơ sở dữ liệu tương đương với độ dài của tập mục dài nhất, dẫn đến chi phí tính toán bùng nổ theo cấp số nhân.

Thứ hai, việc chuyển đổi không gian biểu diễn sang cấu trúc cây như FP-tree và cấu trúc cây không đệ quy COFI-tree giúp tối ưu hóa hiệu năng vượt bậc. Cấu trúc cây nén toàn bộ cơ sở dữ liệu vào bộ nhớ chỉ sau 2 lần quét, cho phép khai phá mẫu thường xuyên nhanh hơn nhờ kỹ thuật chia để trị mà không cần phát sinh tập ứng viên trung gian.

Thứ ba, nghiên cứu chứng minh tính chất phản đơn điệu không còn được bảo toàn trong bài toán khai phá cổ phần cao, nhưng tính chất này lại được tái lập trên đại lượng giá trị theo giao tác. Thuật toán cải tiến AFSM đã tận dụng xuất sắc đặc tính này để hạ thấp giá trị hàm tới hạn từ khoảng 125 đến 350 của thuật toán FSM xuống còn 13 đến 38. Nhờ đó, ngay tại bước lặp đầu tiên với ngưỡng cổ phần 30% tương ứng giá trị ngưỡng 16,8, thuật toán AFSM đã tỉa bỏ thành công 4 trên 8 mục dữ liệu là A, F, G, H, giảm 50% số lượng ứng viên cần duyệt.

Thứ tư, khai phá tập mục lợi ích cao giúp nhận diện các tri thức kinh doanh bị che lấp bởi các thuật toán thống kê. Một tập mục chỉ xuất hiện trong 20% giao dịch vẫn có thể đóng góp tới 50% cổ phần hoặc mang lại giá trị lợi nhuận vượt ngưỡng 119,4 trên tổng lợi ích 398 đơn vị của toàn hệ thống.

+-------------------------------------------------------------+
| SO SÁNH GIÁ TRỊ HÀM TỚI HẠN VÀ KHẢ NĂNG TỈA ỨNG VIÊN (k=1)  |
+-------------------------------------------------------------+
| Mục dữ liệu        |   A   |   B   |   C   |   D   |   E    |
| Lợi nhuận cục bộ   |   5   |  14   |  14   |   8   |   4    |
| Hàm CF (FSM)       |  125  |  350  |  350  |  200  |  100   |
| Hàm tmv (AFSM)     |   13  |   38  |   38  |   38  |   22   |
| Ngưỡng cắt (16,8)  | Tỉa   | Giữ   | Giữ   | Giữ   | Giữ    |
+-------------------------------------------------------------+

Thảo luận kết quả

Sự vượt trội của thuật toán AFSM xuất phát từ việc thiết lập được cận trên chặt hơn rất nhiều so với hàm tới hạn của thuật toán FSM. Trong khi hàm tới hạn cũ ước lượng giá trị cực đại dựa trên tích của độ dài giao tác lớn nhất và giá trị mục lớn nhất trên toàn bộ cơ sở dữ liệu, thì thuật toán AFSM tính toán trực tiếp tổng giá trị của các giao tác thực tế có chứa tập mục đó.

Khi thể hiện qua các bảng đối sánh ma trận giao tác và biểu đồ nhánh cây phân cấp, dữ liệu cho thấy không gian tìm kiếm của AFSM co hẹp nhanh chóng qua từng bước lặp k từ 1 đến 3, triệt tiêu hoàn toàn các nhánh tính toán rỗng. Kết quả này đồng nhất và củng cố vững chắc cho các nghiên cứu tiên phong của Hong Yao, Hamilton và Erwin, khẳng định rằng khai phá hướng lợi ích và giá trị thực tế là bước tiến tất yếu của ngành khoa học dữ liệu hiện đại.

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

Nhằm chuyển hóa các phát hiện lý thuyết thành giá trị thực tiễn, luận văn đưa ra bốn đề xuất hành động cụ thể:

Thứ nhất, tích hợp thuật toán AFSM và giải thuật CTU-PRO vào các hệ thống phân tích dữ liệu bán lẻ và thương mại điện tử. Giải pháp này hướng tới mục tiêu giảm 40% thời gian xử lý các lô giao dịch định kỳ, với lộ trình triển khai 6 tháng do đội ngũ kỹ sư dữ liệu và kiến trúc sư hệ thống phụ trách.

Thứ hai, xây dựng ma trận trọng số và bảng lợi ích động cho danh mục sản phẩm. Doanh nghiệp cần cập nhật liên tục biên lợi nhuận và chi phí lưu kho theo thời gian thực nhằm tối ưu hóa 25% danh mục hàng tồn và nâng cao hiệu quả xếp dỡ hàng hóa tại điểm bán. Hoạt động này được thực hiện trong vòng 3 quý bởi bộ phận kinh doanh phối hợp cùng chuyên viên phân tích tài chính.

Thứ ba, phát triển các module khai phá tập mục lợi ích cao vận hành trên nền tảng điện toán phân tán. Đề xuất này nhắm đến năng lực xử lý mượt mà các tập dữ liệu có quy mô trên 10 triệu bản ghi với độ trễ giảm hơn 60%, thực hiện theo kế hoạch 12 tháng dưới sự chủ trì của trung tâm nghiên cứu và phát triển công nghệ.

Thứ tư, chuẩn hóa quy trình tiền xử lý và rời rạc hóa dữ liệu định lượng đa chiều. Mục tiêu là kiểm soát sai số phân lớp và nâng độ chính xác của các luật kết hợp định lượng lên trên 90%, áp dụng định kỳ hàng quý bởi đội ngũ quản trị cơ sở dữ liệu.

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

Nội dung và kết quả nghiên cứu của luận văn mang lại giá trị thiết thực cho bốn nhóm đối tượng:

• Kỹ sư dữ liệu và chuyên gia phân tích nghiệp vụ: Nắm vững cấu trúc giải thuật FP-tree, COFI-tree và AFSM để tối ưu hóa quy trình truy vấn dữ liệu lớn và thiết kế các đường ống xử lý dữ liệu thông minh trong doanh nghiệp.
• Nhà quản trị bán lẻ và tiếp thị số: Ứng dụng mô hình tập mục lợi ích cao để tái cấu trúc chiến lược bán chéo, phân bổ vị trí quầy kệ siêu thị và thiết lập các gói khuyến mãi nhắm đúng nhóm hàng sinh lời cao nhất, giúp tăng trưởng biên lợi nhuận từ 15% đến 20%.
• Học viên cao học và nghiên cứu sinh công nghệ thông tin: Khai thác khung lý thuyết toán học chặt chẽ, các phép chứng minh tính chất phản đơn điệu và phương pháp thiết kế hàm tới hạn để làm tài liệu nghiên cứu chuyên sâu.
• Giảng viên chuyên ngành Khoa học dữ liệu và Hệ thống thông tin: Sử dụng nguồn học liệu chuẩn mực gồm các ví dụ tính toán từng bước, bảng biểu đối sánh trực quan để biên soạn bài giảng môn Khai phá dữ liệu và Khám phá tri thức.

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

Khai phá tập mục thường xuyên khác gì so với khai phá luật kết hợp? Khai phá tập mục thường xuyên là giai đoạn thứ nhất và phức tạp nhất của quá trình khai phá luật kết hợp. Giai đoạn này tìm các tập mặt hàng có tần suất xuất hiện vượt ngưỡng hỗ trợ cho trước, ví dụ lớn hơn hoặc bằng 30%. Từ các tập mục thường xuyên tìm được, hệ thống mới sinh ra các luật kết hợp dạng suy diễn thỏa mãn ngưỡng độ tin cậy.

Tại sao tính chất phản đơn điệu Apriori bị phá vỡ trong bài toán cổ phần cao? Tính chất Apriori dựa trên tần suất xuất hiện nên tập con luôn có số lần xuất hiện lớn hơn hoặc bằng tập cha. Tuy nhiên, cổ phần tính bằng tổng giá trị đóng góp của các mục, nên một tập cha gồm nhiều mục có thể có tổng giá trị lớn hơn từng mục con riêng lẻ, khiến một tập con có cổ phần dưới 30% nhưng tập cha mở rộng lại vượt ngưỡng 30%.

Thuật toán AFSM vượt trội hơn thuật toán FSM ở điểm mấu chốt nào? Điểm đột phá của AFSM nằm ở việc sử dụng giá trị giao tác làm hàm tới hạn thay vì hàm chặn trên lỏng lẻo của FSM. Bằng cách chứng minh giá trị giao tác có tính phản đơn điệu, AFSM thiết lập ngưỡng chặn sát thực tế từ 13 đến 38, giúp loại bỏ các ứng viên không tiềm năng ngay từ vòng lặp đầu tiên mà không làm sót nghiệm.

Làm thế nào để xác định ngưỡng lợi ích tối thiểu trong bài toán khai phá lợi ích cao? Ngưỡng lợi ích tối thiểu được xác định bằng cách nhân tỷ lệ phần trăm mong muốn của nhà quản lý với tổng lợi ích toàn bộ cơ sở dữ liệu. Ví dụ, với tổng lợi nhuận hệ thống là 398 đơn vị và tỷ lệ chọn lọc là 30%, ngưỡng lợi ích tối thiểu được tính chính xác là 119,4 đơn vị để lọc ra các tập mục lợi nhuận cao.

Khi nào nên ưu tiên cấu trúc cây COFI-tree thay vì giải thuật Apriori? Nên ưu tiên cấu trúc COFI-tree khi làm việc với các cơ sở dữ liệu giao dịch dày hoặc có chuỗi mục dài. Cấu trúc này chỉ cần 2 lần quét dữ liệu và khai phá trực tiếp trên cây bộ nhớ cục bộ mà không sử dụng đệ quy phức tạp, giúp tiết kiệm bộ nhớ và tránh việc sinh ra hàng triệu tập ứng viên trung gian như Apriori.

Kết luận

Luận văn đã hoàn thành xuất sắc các mục tiêu nghiên cứu với năm đóng góp trọng tâm:

• Hệ thống hóa toàn diện cơ sở lý thuyết về khai phá tập mục thường xuyên và luật kết hợp từ các thuật toán cơ bản đến nâng cao.
• Phân tích sâu sắc các hạn chế của mô hình nhị phân truyền thống và làm rõ sự cần thiết của các mô hình mở rộng định lượng.
• Chứng minh chặt chẽ tính chất phản đơn điệu của đại lượng giá trị theo giao tác trong không gian bài toán cổ phần cao.
• Trình bày chi tiết thuật toán cải tiến AFSM cùng cơ chế tỉa ứng viên vượt trội, giúp tối ưu hóa đáng kể tài nguyên tính toán.
• Thiết lập nền tảng toán học và giải thuật vững chắc cho bài toán khai phá tập mục lợi ích cao hướng tới ứng dụng kinh doanh thực tế.

Trong lộ trình từ 6 đến 12 tháng tới, hướng phát triển tiếp theo cần tập trung mở rộng thuật toán trên các kiến trúc tính toán song song GPU và luồng dữ liệu thời gian thực. Hãy liên hệ với nhóm nghiên cứu hoặc tra cứu toàn văn tài liệu học thuật để áp dụng ngay các mô hình tối ưu này vào hệ thống phân tích dữ liệu của bạn.

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

Mở đầu Khai phá tập mục thường xuyên đóng vai trò quan trọng trong nhiều nhiệm vụ khai phá dữ liệu. Khai phá tập mục thường xuyên xuất hiện như bài toán con của nhiều lĩnh vực khai phá dữ liệu như khám phá luật kết hợp, khám phá mẫu tuần tự, phân tích tương quan, phân lớp, phân cụm dữ liệu, khai phá Web,… Bài toán khai phá tập mục thường xuyên được giới thiệu lần đầu bởi Agrawal vào năm 1993 khi phân tích cơ sở dữ liệu bán hàng của siêu thị [9] trong mô hình của bài toán khai phá luật kết hợp. Khai phá luật kết hợp 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, các mối quan hệ đó chính là các luật kết hợp. Khai phá luật kết hợp có hai bước: bước thứ nhất, tìm các tập mục thường xuyên thỏa mãn ngưỡng độ tối thiểu minsup cho trước, bước thứ hai, từ các tập mục thường xuyên tìm được, sinh ra các luật kết hợp thỏa mãn ngưỡng độ tin cậy minconf cho trước.

Mọi khó khăn của bài toán khai phá luật kết hợp tập trung ở bước thứ nhất, đó là khai phá tập mục thường xuyên thỏa mãn ngưỡng độ hỗ trợ cho trước. Kể từ khi Agrawa đề xuất, khai phá tập mục thường xuyên đã thu hút được sự quan tâm của nhiều nhà nghiên cứu, đã có hàng trăm kết quả nghiên cứu được công bố giới thiệu các thuật toán mới hay đề xuất các giải pháp nâng cao hiệu quả các thuật toán đã có. Tập mục thường xuyên đã có vai trò quan trọng trong nhiều ứng dụng thực tế như quản lý quan hệ khách hàng, nâng cao hiệu quả của thương mại điện tử, trong lĩnh vực tin sinh học, phân tích cấu trúc Protein và DNA, mở rộng truy vấn, phát hiện xâm nhập mạng…[13, 14, 15, 16]. Mô hình khai phá tập mục thường xuyên cơ bản có nhiều ứng dụng trong thực tế nhưng có những hạn chế, không đáp ứng đầy đủ yêu cầu của người sử dụng.

Ràng buộc về độ hỗ trợ và độ tin cậy của luật kết hợp chỉ mang ngữ nghĩa thống kê, không phản ánh được vai trò khác nhau của các thuộc tính cũng như đặc tính dữ liệu vốn có của chúng trong cơ sở dữ liệu. TIEU LUAN MOI download : [e-mail] 6 Để đáp ứng yêu cầu của thực tiễn, khai phá tập mục thường xuyên đã có nhiều cách thức mở rộng và ứng dụng, từ thay đổi phương pháp luận đến thay đổi đa dạng các kiểu dữ liệu, mở rộng các nhiệm vụ khai phá và đa dạng các ứng dụng mới. Trong những năm qua, đã có nhiều hướng mở rộng bài toán được quan tâm nghiên cứu. Chương một này sẽ trình bày các vấn đề cơ bản của bài toán khai pháp tập mục thường xuyên.

Một số khái niệm cơ bản về tập mục Định nghĩa 1.1: Cho tập mục (item) I={I1,I2,…,Im}. 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à 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à 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: 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. 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 đó. Giao tác Mục dữ liệu T1 A, C, D T2 B, C, E T3 A, B, C, E T4 B, E Bảng 1. Biểu diễn cơ sở dữ liệu giao tác ngang 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 này. TIEU LUAN MOI download : [e-mail] 7 Mục dữ liệu Các giao tác A T1, T3 B T2, T3, T4 C T1, T2, T3 D T1 E T2, T3, T4 Bảng 2.

Biểu diễn cơ sở dữ liệu giao tác dọc Biểu diễn ma trận nhị phân: Cơ sở dữ liệu giao tác trên tập mục (item) được biểu diễn bởi ma trận nhị phân M = (mpq)mxn ở đó 1 ݇ℎ݅ ݅௣ ∈ ܶ௤ ݉௣௤ = ൜
0 ݇ℎ݅ ݅௣ ∉ ܶ௤ Mục T1 T2 T3 T4 A 1 0 1 0 B 0 1 1 1 C 1 1 1 0 D 1 0 0 0 E 0 1 1 1 Bảng 3. Biểu diễn cơ sở dữ liệu giao tác ma trận I. Tập mục thường xuyên và luật kết hợp Định nghĩa 1.2: Cho tập mục X ⊆ I. Độ hỗ trợ (Support) của tập mục X trong cơ sở dữ liệu giao tác DB, ký hiệu sup(X), là tỷ lệ phần trăm của các giao tác chứa tập mục X trên tổng số giao tác trong DB, tức là: | {T ∈ DB | T ⊇ X } | sup( X ) = | DB | Định nghĩa 1.3: Cho tập mục X⊆I với ngưỡng hộ trợ tối thiểu (minimum support) minsup ∈ [0,1] (được xác định trước bởi người sử dụng).

X được gọi là tập mục thường xuyên (frequent itemset hoặc large itemset) với độ hỗ trợ tối TIEU LUAN MOI download : [e-mail] 8 thiểu minsup nếu sup(X) ≥ minsup, ngược lại X gọi là tập mục không thường xuyên.4: Một luật kết hợp là một biểu thức dạng X →Y, trong đó X và Y là các tập con của I, X∩Y=∅; X gọi là tiên đề, Y gọi là kết luận của luật. Luật kết hợp có hai thông số quan trọng là độ hỗ trợ và độ tin cậy. Như vậy độ 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 của X và Y trong một giao tác. Ta có 0 ≤ sup (X →Y ) ≤ 1 Định nghĩa 1.6: Độ tin cậy (confidence) luật kết hợp, ký hiệu là conf(X→Y), là tỷ lệ phần trăm giữa số giao tác chứa X∪Y và số giao tác chứa X trong cơ sở dữ liệu DB.

Bài toán khai phá luật kết hợp Xác định tất cả X⇒ ⇒Y thỏa mãn độ hỗ trợ và độ tin cậy tối thiểu thì luật ⇒Y được gọi là luật kết hợp mạnh. X⇒ TIEU LUAN MOI download : skknchat@gmail. Một số tính chất của tập mục thường xuyên Cho cơ sở dữ liệu giao tác DB và ngưỡng độ hỗ trợ tối thiểu minsup. Các tập mục thường xuyên có tính chất sau: (1) Nếu X, Y là các tập mục và X ⊆ Y thì sup(X) ≥ sup(Y) (2) Nếu một tập mục là không thường xuyên thì mọi tập cha của nó cũng là không thường xuyên (3) Nếu một tập mục là thường xuyên thì mọi tập con khác rỗng của nó cũng là tập mục thường xuyên Tính chất (3) là tính chất quan trọng, nó được gọi là tính chất Apriori, tính chất này là cơ sở để rút gọn không gian tìm kiếm các tập mục thường xuyên.

Mô tả bài toán khai phá luật kết hợp Khai phá luật kết hợp là một kỹ thuật quan trọng của khai phá dữ liệu. Vấn đề này được Rakesh Agrawal, Tomasz Imielinski, Arun Swami đề xuất lần đầu vào năm 1993 [9]. Sau đó năm 1996 được Rakesh Agrawal, Heikki Mannia, Ramakrishnan Srikant, Hannu Toivonen, A.Inkeri Verkamo tiếp tục cải tiến. Ngày nay bài toán khai thác các luật kết hợp nhận được rất nhiều sự quan tâm của nhiều nhà khoa học.

Việc khai thác các luật như thế nào vẫn là một trong các phương pháp khai thác mẫu phổ biến nhất trong việc khám phá tri thức và khai thác dữ liệu (KDD – Knowledge Discovery and Data Minning). Mục đích chính của khai phá dữ liệu là trích rút tri thức một cách tự động, hiệu quả và “thông minh” từ kho dữ liệu. Trong hoạt động sản xuất kinh doanh, ví dụ kinh doanh các mặt hàng tại siêu thị, các nhà quản lý rất thích có được những thông tin mang tính thống kê như: “90% phụ nữ có xe máy màu đỏ và đeo đồng hồ Thụy Sỹ thì dùng nước hoa hiệu Chanel” hoặc “70% khách hàng là công nhân thì mua TV thường mua loại 21 inches”. Những thông tin như vậy rất hữu ích trong việc định hướng kinh doanh.

Vậy vấn đề đặt ra là liệu có tìm được các luật như vậy bằng các TIEU LUAN MOI download : [e-mail] 10 công cụ khai phá dữ liệu hay không? Câu trả lời là hoàn toàn có thể. Đó chính là nhiệm vụ khai phá luật kết hợp. Giả sử chúng ta có một CSDL D. Luật kết hợp cho biết phạm vi mà trong đó sự xuất hiện của tập các thuộc tính S nào đó trong các bản ghi (records) của D sẽ kéo theo sự xuất hiện của một tập những thuộc tính khác U cũng trong những bản ghi đó.

Mỗi luật kết hợp được đặc trưng bởi một cặp tỉ lệ hỗ trợ (support ration). Mỗi tỉ lệ hỗ trợ được biểu diễn bằng tỉ lệ % những bản ghi trong D chứa cả S và U. Vấn đề khám phá luật kết hợp được phát biểu như sau: Cho trước tỉ lệ hỗ trợ (support ration) θ và độ tin cậy (confidence) β Đánh số tất cả các luật trong D có các giá trị tỉ lệ hỗ trợ và tin cậy lớn hơn θ và β tương ứng. Ví dụ: Gọi D là CSDL mua bán và với θ = 40%, β = 90% Vấn đề phát hiện luật kết hợp được thực hiện như sau: Liệt kê (đếm) tất cả những quy luật chỉ ra sự xuất hiện một số các mục kéo theo một số mục khác.

Chỉ xét những quy luật mà tỉ lệ hỗ trợ lớn hơn 40% và độ tin cậy lớn hơn 90% Hay chúng ta hãy tưởng tượng, một công ty bán hàng qua mạng Internet. Các khách hàng được yêu cầu điền vào các mẫu bán hàng để công ty có một CSDL về các yêu cầu của khách hàng. Giả sử công ty quan tâm đến mối quan hệ “tuổi, giới tính, nghề nghiệp => sản phẩm”. Khi đó có thể có rất nhiều câu hỏi tương ứng với luật trên.

Ví dụ: trong lứa tuổi nào thì những khách hàng nữ là công nhân đặt mua mặt hàng gì đó, ví dụ áo dài chẳng hạn là nhiều nhất (thỏa mãn một ngưỡng nào đó)? Cho cơ sở dữ liệu giao tác DB, ngưỡng độ hỗ trợ tối thiểu minsup và ngưỡng độ tin cậy minconf. TIEU LUAN MOI download : skknchat@gmail.