Nghiên cứu Thuật Toán CHARM trong Khai Phá Tập Mục Thường Xuyên Đóng (Luận Văn Thạc Sĩ)

Nghiên cứu thuật toán CHARM trong khai phá tập mục thường xuyên đóng. Tìm hiểu cách thuật toán CHARM giúp khai thác hiệu quả các tập mục quan trọng.

• Tác giả: Phan Văn Tuyên
• Người hướng dẫn: Ts. Nguyễn Huy Đức
• Trường học: Trường Đại học Công nghệ Thông tin và Truyền thông - Đại học Thái Nguyên
• Chuyên ngành: Khoa Học Máy Tính
• Đề tài: Nghiên Cứu Thuật Toán Charm Trong Khai Phá Tập Mục Thường Xuyên Đóng
• Loại tài liệu: Luận Văn Thạc Sĩ
• Năm xuất bản: 2011
• Địa điểm: Thái Nguyên

Mục lục chi tiết

• Lời cảm ơn
• Lời cam đoan
• DANH MỤC CÁC KÝ HIỆU VÀ CÁC CHỮ VIẾT TẮT
• DANH MỤC CÁC BẢNG
• DANH MỤC HÌNH VẼ
• 1. CHƢƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU
• 1.1. KHÁM PHÁ TRI THỨC VÀ KHAI PHÁ DỮ LIỆU
• 1.2. KIẾN TRÚC CỦA HỆ THỐNG KHAI PHÁ DỮ LIỆU
• 1.3. QUÁ TRÌNH KHAI PHÁ DỮ LIỆU
• 1.4. CÁC KỸ THUẬT KHAI PHÁ DỮ LIỆU
• 1.4.1. Phân lớp dữ liệu
• 1.4.2. Phân cụm dữ liệu
• 1.4.3. Khai phá luật kết hợp
• 1.4.4. Giải thuật di truyền
• 1.4.5. Cây quyết định
• 1.5. MỘT SỐ ỨNG DỤNG CỦA KHAI PHÁ DỮ LIỆU
• 1.6. KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN
• 1.6.1. Cơ sở dữ liệu giao tác
• 1.6.2. Tập mục thƣờng xuyên
• 1.6.3. Các cách tiếp cận khai phá tập mục thƣờng xuyên
• 1.6.4. Một số thuật toán điển hình tìm tập mục thƣờng xuyên
• 1.6.4.1. Thuật toán Apriori
• 1.6.4.2. Thuật toán FP-Growth
• 1.7. KẾT LUẬN CHƢƠNG 1
• 2. CHƢƠNG 2: KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN ĐÓNG
• 2.1. CƠ SỞ TOÁN HỌC
• 2.1.1. Ánh xạ đóng
• 2.1.2. Kết nối Galois
• 2.1.3. Bao đóng của tập mục dữ liệu
• 2.2. TẬP MỤC THƢỜNG XUYÊN ĐÓNG
• 2.2.1. Các tính chất của tập mục thƣờng xuyên đóng
• 2.3. THUẬT TOÁN CHARM
• 2.3.1. Giới thiệu thuật toán CHARM
• 2.3.2. Cây tìm kiếm và lớp tƣơng đƣơng
• 2.3.3. Các tính chất cơ bản của cặp tập mục - tập định danh:
• 2.3.4. Thiết kế thuật toán
• 2.3.5. Ví dụ minh họa
• 2.3.6. Đánh giá thuật toán
• 2.4. KẾT LUẬN CHƢƠNG 2
• 3. CHƢƠNG 3: CÀI ĐẶT THỰC NGHIỆM
• 3.1. XÂY DỰNG CHƢƠNG TRÌNH
• 3.2. GIAO DIỆN CỦA CHƢƠNG TRÌNH
• 3.3. KẾT QUẢ THỰC NGHIỆM
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Giải mã tập mục thường xuyên đóng trong khai phá dữ liệu

Khai phá dữ liệu (Data Mining) là quá trình trích xuất thông tin hữu ích, tiềm ẩn và chưa từng được biết đến từ các tập dữ liệu lớn. Một trong những nhiệm vụ cốt lõi của lĩnh vực này là khai phá luật kết hợp, một kỹ thuật mạnh mẽ để khám phá các mối quan hệ giữa các mục trong một cơ sở dữ liệu giao dịch. Nền tảng của việc sinh luật kết hợp chính là tìm kiếm các tập mục thường xuyên (frequent itemsets) – những nhóm mục xuất hiện cùng nhau với tần suất vượt một ngưỡng xác định, gọi là độ hỗ trợ (support) tối thiểu. Tuy nhiên, việc tìm kiếm tất cả các tập mục thường xuyên có thể tạo ra một số lượng kết quả khổng lồ, trong đó chứa nhiều thông tin dư thừa. Ví dụ, nếu tập {Bia, Tã} là thường xuyên, thì các tập con của nó là {Bia} và {Tã} cũng chắc chắn thường xuyên. Vấn đề này dẫn đến sự ra đời của một khái niệm hiệu quả hơn: tập mục thường xuyên đóng (closed frequent itemset). Một tập mục được coi là đóng nếu nó thường xuyên và không có bất kỳ tập cha (superset) nào có cùng độ hỗ trợ. Nói cách khác, nó là đại diện đầy đủ và nhỏ gọn nhất cho một nhóm các tập mục có cùng tần suất xuất hiện. Việc chỉ khai phá các tập mục đóng giúp giảm đáng kể số lượng kết quả mà không làm mất thông tin về độ hỗ trợ, từ đó tối ưu hóa cả không gian lưu trữ và thời gian tính toán.

1.1. Vai trò của luật kết hợp và tập mục thường xuyên

Trong khai phá dữ liệu, luật kết hợp là một kỹ thuật quan trọng giúp phát hiện các mối quan hệ ẩn trong dữ liệu. Một ví dụ kinh điển là trong phân tích giỏ hàng, nơi các nhà bán lẻ muốn biết khách hàng thường mua những sản phẩm nào cùng nhau. Quá trình này gồm hai bước chính. Bước đầu tiên là tìm ra tất cả các tập mục thường xuyên, tức là các nhóm sản phẩm có độ hỗ trợ (support) lớn hơn hoặc bằng một ngưỡng tối thiểu (minsup). Bước thứ hai là từ các tập mục thường xuyên này sinh ra các luật kết hợp mạnh. Tuy nhiên, bước đầu tiên thường tốn kém nhất về mặt tính toán. Việc tìm kiếm hiệu quả các tập mục này là chìa khóa để tối ưu hóa toàn bộ quá trình. Các thuật toán ban đầu như thuật toán Apriori tập trung vào việc tạo và đếm ứng viên, trong khi các phương pháp sau này như thuật toán FP-Growth sử dụng cấu trúc dữ liệu nén để tăng tốc độ. Dù vậy, cả hai đều có thể sinh ra số lượng lớn các tập mục thường xuyên, gây khó khăn cho việc phân tích và lưu trữ.

1.2. So sánh tập mục thường xuyên đóng và tập mục tối đại

Để giải quyết vấn đề dư thừa thông tin, hai khái niệm con của tập mục thường xuyên đã được đề xuất: tập mục thường xuyên đóng (closed) và tập mục thường xuyên tối đại (maximal). Một tập mục thường xuyên đóng là tập mục thường xuyên mà không có tập cha nào của nó có cùng độ hỗ trợ. Nó bảo toàn 100% thông tin về tần suất. Ngược lại, một tập mục thường xuyên tối đại là một tập mục thường xuyên mà không có bất kỳ tập cha nào của nó là thường xuyên. Tập tối đại cung cấp một bộ kết quả nhỏ gọn hơn nữa nhưng lại làm mất thông tin về độ hỗ trợ của các tập con. Ví dụ, nếu {A,B,C} có support là 5 và {A,B} cũng có support là 5, thì {A,B,C} là tập đóng, còn {A,B} thì không. Nếu {A,B,C,D} không thường xuyên, thì {A,B,C} là tập tối đại. Việc khai phá tập mục đóng được xem là lựa chọn tối ưu vì nó là một bộ kết quả không mất mát thông tin (lossless), trong khi vẫn giảm đáng kể sự dư thừa so với việc khai phá toàn bộ tập mục thường xuyên.

II. Thách thức khai phá dữ liệu với Apriori và FP Growth

Các thuật toán kinh điển trong việc tìm kiếm tập mục thường xuyên như thuật toán Apriori và thuật toán FP-Growth đã đặt nền móng vững chắc cho lĩnh vực khai phá dữ liệu. Tuy nhiên, chúng cũng bộc lộ những hạn chế đáng kể, đặc biệt khi xử lý các tập dữ liệu lớn và dày đặc. Thuật toán Apriori hoạt động dựa trên nguyên tắc "bất kỳ tập con nào của một tập mục thường xuyên cũng phải thường xuyên". Nó thực hiện tìm kiếm theo chiều rộng (BFS), duyệt qua cơ sở dữ liệu giao dịch nhiều lần để tạo và kiểm tra các tập ứng viên. Chi phí lớn nhất của Apriori nằm ở việc sinh ra một số lượng khổng lồ các tập ứng viên, đặc biệt ở các vòng lặp đầu tiên, và yêu cầu quét lại toàn bộ CSDL ở mỗi bước. Để khắc phục, thuật toán FP-Growth ra đời với một cách tiếp cận khác biệt: nén CSDL vào một cây tiền tố (prefix tree) gọi là FP-tree và khai phá trực tiếp trên cây này, tránh việc sinh ứng viên. Mặc dù hiệu quả hơn Apriori, FP-Growth vẫn gặp khó khăn khi cây FP-tree trở nên quá lớn và phức tạp với các CSDL dày đặc, dẫn đến việc xây dựng các cây điều kiện đệ quy tốn nhiều bộ nhớ. Cả hai phương pháp này đều nhằm mục đích tìm tất cả tập mục thường xuyên, dẫn đến kết quả cồng kềnh và dư thừa.

2.1. Nhược điểm của thuật toán Apriori Sinh quá nhiều ứng viên

Hạn chế cốt lõi của thuật toán Apriori là chi phí tính toán và I/O cao. Thuật toán này yêu cầu quét toàn bộ cơ sở dữ liệu giao dịch nhiều lần. Số lần quét bằng với độ dài của tập mục thường xuyên dài nhất. Trong mỗi lần quét, nó phải sinh ra một tập ứng viên (candidate set) khổng lồ. Ví dụ, theo luận văn của Phan Văn Tuyên (2011), "nếu có 10^4 mục thường xuyên thì thuật toán Apriori sẽ cần sinh ra hơn 10^7 các ứng viên 2-tập mục và thực hiện kiểm tra độ hỗ trợ của chúng". Quá trình này không chỉ tốn thời gian CPU để tạo và so khớp các mẫu mà còn yêu cầu nhiều bộ nhớ để lưu trữ các tập ứng viên. Đối với các cơ sở dữ liệu có số lượng mục lớn hoặc ngưỡng hỗ trợ thấp, hiệu năng thuật toán Apriori suy giảm nghiêm trọng, khiến nó không phù hợp cho các bài toán khai phá dữ liệu quy mô lớn trong thực tế.

2.2. Hạn chế của thuật toán FP Growth trong CSDL dày đặc

Thuật toán FP-Growth là một cải tiến vượt bậc so với Apriori bằng cách chỉ cần hai lần quét CSDL và không sinh ứng viên. Nó nén thông tin vào cấu trúc FP-tree. Tuy nhiên, phương pháp "chia để trị" của nó, tức là xây dựng các cây FP-tree điều kiện một cách đệ quy, lại chính là điểm yếu khi xử lý các CSDL dày (dense). Trong các CSDL dày, các mục có độ tương quan cao, dẫn đến FP-tree rất rậm rạp và phân nhánh nhiều. Khi đó, việc xây dựng các cây con đệ quy có thể rất tốn kém về bộ nhớ và thời gian, đôi khi còn tệ hơn cả Apriori. Mặc dù hiệu quả hơn trong nhiều trường hợp, FP-Growth vẫn tập trung vào việc tìm tất cả tập mục thường xuyên, thay vì tìm một tập đại diện nhỏ gọn hơn như tập mục thường xuyên đóng, do đó vẫn chưa giải quyết triệt để bài toán dư thừa kết quả.

III. Phương pháp khai phá tập mục đóng với thuật toán CHARM

Thuật toán CHARM (Closed Association Rule Mining) là một giải pháp đột phá được đề xuất bởi Zaki và Hsiao để giải quyết bài toán closed frequent itemset mining một cách hiệu quả. Thay vì tìm tất cả các tập mục thường xuyên, CHARM chỉ tập trung vào các tập mục thường xuyên đóng, giúp giảm đáng kể số lượng kết quả mà không làm mất thông tin. Điểm khác biệt cốt lõi của CHARM nằm ở việc nó khám phá không gian tìm kiếm đồng thời trên cả không gian tập mục (itemset) và không gian tập định danh giao tác (tidset). Thuật toán này sử dụng một cấu trúc dữ liệu dọc, lưu trữ danh sách các giao dịch (TID) chứa mỗi mục. Khi kết hợp các mục, CHARM chỉ cần thực hiện phép giao trên các tidset tương ứng, một thao tác hiệu quả hơn nhiều so với việc quét lại CSDL. Nó cũng sử dụng một cấu trúc dữ liệu IT-tree (Itemset-Tidset tree) để tổ chức không gian tìm kiếm và áp dụng các thuộc tính toán học thông minh để cắt tỉa không gian tìm kiếm một cách mạnh mẽ. Bằng cách này, CHARM không sinh ra tập ứng viên và có thể nhanh chóng xác định các tập mục đóng, bỏ qua nhiều tập con không cần thiết.

3.1. Nguyên lý cốt lõi Cấu trúc dữ liệu IT tree hiệu quả

Thuật toán CHARM tổ chức không gian tìm kiếm dưới dạng một cây tiền tố gọi là cấu trúc dữ liệu IT-tree. Mỗi nút trong cây này không chỉ đại diện cho một tập mục (Itemset) mà còn đi kèm với tập định danh giao tác tương ứng (Tidset). Cây được duyệt theo chiều sâu (DFS). Sức mạnh của cấu trúc này nằm ở việc nó phân chia không gian tìm kiếm thành các bài toán con độc lập dựa trên các lớp tương đương tiền tố. Theo tài liệu nghiên cứu, "mỗi nút trong IT-tree đại diện cho một cặp Itemset-Tidset X × t(X)". Tất cả các nút con của một nút X đều có chung tiền tố X. Bằng cách xử lý từng lớp tương đương, CHARM có thể khai phá các mẫu một cách độc lập, giúp quá trình xử lý song song trở nên khả thi và giảm độ phức tạp tổng thể của bài toán khai phá tập mục thường xuyên đóng.

3.2. Các tính chất toán học của cặp Itemset Tidset

CHARM tận dụng bốn tính chất toán học cơ bản dựa trên mối quan hệ giữa các tidset của hai tập mục X1 và X2 để tối ưu hóa việc tìm kiếm. Các tính chất này, dựa trên kết nối Galois, cho phép thuật toán cắt tỉa không gian tìm kiếm và hợp nhất các nút một cách thông minh:

1. Nếu t(X1) = t(X2): X1 và X2 luôn xuất hiện cùng nhau. Chúng có thể được hợp nhất thành một tập mục duy nhất X1 ∪ X2, và X2 có thể bị loại bỏ khỏi các bước tìm kiếm sau này.
2. Nếu t(X1) ⊂ t(X2): Mọi giao dịch chứa X2 cũng chứa X1. Tập mục X2 có thể được thay thế bằng X1 ∪ X2.
3. Nếu t(X1) ⊃ t(X2): Mọi giao dịch chứa X1 cũng chứa X2. Tập mục X1 có thể được thay thế bằng X1 ∪ X2.
4. Nếu t(X1) ≠ t(X2) và không là tập con của nhau: Cả X1 và X2 đều có thể tạo ra các tập đóng riêng biệt, và một tập mục mới X1 ∪ X2 được tạo ra để khám phá sâu hơn. Những tính chất này là chìa khóa giúp CHARM đạt được hiệu năng thuật toán vượt trội.

IV. Hướng dẫn cách hoạt động của thuật toán CHARM chi tiết

Hoạt động của thuật toán CHARM có thể được mô tả như một quá trình tìm kiếm theo chiều sâu (DFS) trên cấu trúc dữ liệu IT-tree. Quá trình này được điều khiển bởi hai thủ tục chính: CHARM_Extend và CHARM_Property. Đầu tiên, thuật toán quét cơ sở dữ liệu giao dịch một lần để tạo danh sách các 1-tập mục thường xuyên cùng với tidset của chúng. Tập hợp này tạo thành lớp tương đương ban đầu ở gốc của cây tìm kiếm. Sau đó, thủ tục CHARM_Extend được gọi đệ quy để mở rộng các tập mục. Trong mỗi lần gọi, CHARM_Extend sẽ duyệt qua các cặp tập mục (Xi, Xj) trong lớp tương đương hiện tại. Với mỗi cặp, nó tính toán tập mục mới Xij = Xi ∪ Xj và tidset mới t(Xij) = t(Xi) ∩ t(Xj). Nếu độ hỗ trợ (support) của Xij (tức là kích thước của t(Xij)) vẫn đủ lớn, thủ tục CHARM_Property sẽ được gọi. Thủ tục này áp dụng bốn tính chất toán học đã nêu để quyết định xem có nên hợp nhất, thay thế hay loại bỏ các tập mục Xi, Xj hay không, nhằm cắt tỉa không gian tìm kiếm. Quá trình này tiếp tục một cách đệ quy cho đến khi không thể mở rộng thêm, đảm bảo chỉ các tập mục thường xuyên đóng được giữ lại.

4.1. Quy trình của CHARM_Extend và CHARM_Property

Thủ tục CHARM_Extend chịu trách nhiệm mở rộng các nút trong cây tìm kiếm. Nó nhận đầu vào là một lớp tương đương P (một tập các cặp Itemset-Tidset) và duyệt qua tất cả các cặp (Xi, Xj) trong P. Với mỗi cặp thỏa mãn ngưỡng hỗ trợ, nó tạo ra một tập mục mới và gọi CHARM_Property. Thủ tục CHARM_Property là bộ não của thuật toán. Nó so sánh tidset của Xi và Xj để áp dụng các quy tắc cắt tỉa. Ví dụ, nếu t(Xi) = t(Xj), nó sẽ thay thế tất cả các vý hiện của Xi bằng Xi ∪ Xj và xóa Y khỏi lớp tương đương con, giúp giảm đáng kể số nhánh cần duyệt. Quá trình này đảm bảo rằng thuật toán không khám phá những nhánh dư thừa và nhanh chóng hội tụ về các tập mục thường xuyên đóng. Cấu trúc này làm cho hiệu năng thuật toán CHARM trở nên vượt trội trong việc khai phá dữ liệu.

4.2. Minh họa cắt tỉa không gian tìm kiếm trên CSDL giao dịch

Xét một ví dụ từ luận văn của Phan Văn Tuyên (2011) với một cơ sở dữ liệu giao dịch nhỏ. Giả sử ta có hai mục A và C với t(A) = {1,3,4,5} và t(C) = {1,2,3,4,5,6}. Khi kết hợp A và C, ta thấy rằng t(A) ⊂ t(C). Theo tính chất 2, điều này có nghĩa là bất cứ khi nào A xuất hiện, C không nhất thiết phải xuất hiện, nhưng khi C xuất hiện thì A cũng có thể xuất hiện trong một tập con các giao dịch đó. Trong trường hợp này, thuật toán sẽ thay thế mục A bằng tập mục hợp nhất AC. Tương tự, nếu t(C) ⊃ t(D), nghĩa là khi nào D xuất hiện thì C cũng luôn xuất hiện. Theo tính chất 3, toàn bộ nhánh bắt đầu từ D có thể bị loại bỏ và thay thế bằng nút con CD dưới nhánh C. Cơ chế cắt tỉa không gian tìm kiếm thông minh này giúp CHARM tránh được việc tính toán trên các tập mục không phải là tập đóng, tiết kiệm tài nguyên và tăng tốc độ khai phá.

V. Đánh giá hiệu năng và các ứng dụng thực tiễn của CHARM

Thuật toán CHARM đã được chứng minh là có hiệu suất vượt trội so với các thuật toán trước đó như thuật toán Apriori, thuật toán FP-Growth và thậm chí cả các thuật toán khai phá tập mục đóng khác như thuật toán Eclat trong nhiều kịch bản. Hiệu năng thuật toán được đánh giá dựa trên hai yếu tố chính: thời gian thực thi và mức độ sử dụng bộ nhớ. Nhờ vào việc sử dụng biểu diễn dữ liệu dọc và các thuộc tính cắt tỉa mạnh mẽ, CHARM có thể xử lý hiệu quả cả CSDL thưa (sparse) và dày (dense). Nó chỉ yêu cầu một vài lần quét CSDL (thường chỉ một lần để xây dựng tidset ban đầu) và tránh hoàn toàn việc sinh ứng viên tốn kém. Các kết quả thực nghiệm, như được trình bày trong luận văn của Phan Văn Tuyên (2011) trên các bộ dữ liệu chuẩn, cho thấy CHARM thường nhanh hơn đáng kể và tạo ra số lượng tập mục kết quả ít hơn nhiều so với các phương pháp tìm tất cả tập mục thường xuyên. Những ưu điểm này làm cho CHARM trở thành một công cụ mạnh mẽ cho các ứng dụng thực tế đòi hỏi tốc độ và hiệu quả, chẳng hạn như phân tích giỏ hàng trong thời gian thực, xây dựng hệ thống gợi ý sản phẩm, và phân tích mẫu trong dữ liệu sinh học.

5.1. Phân tích so sánh hiệu năng thuật toán CHARM và Apriori

Các nghiên cứu so sánh hiệu năng thuật toán đã chỉ ra sự khác biệt lớn giữa CHARM và Apriori. Trong khi Apriori phải vật lộn với sự bùng nổ tổ hợp của các tập ứng viên và yêu cầu nhiều lần quét CSDL, CHARM lại có độ phức tạp thời gian phụ thuộc chủ yếu vào số lượng các tập mục thường xuyên đóng (thường nhỏ hơn nhiều so với tổng số tập mục thường xuyên). Kết quả thực nghiệm trong luận văn "Nghiên cứu thuật toán CHARM trong khai phá tập mục thường xuyên đóng" cho thấy thời gian thực hiện của CHARM trên tệp dữ liệu Input1.dat thấp hơn đáng kể so với phương pháp tìm tất cả tập mục. Điều này đặc biệt đúng khi ngưỡng hỗ trợ giảm xuống, một kịch bản mà Apriori thường thất bại do không đủ bộ nhớ hoặc thời gian. CHARM không chỉ nhanh hơn mà còn tạo ra bộ kết quả nhỏ gọn hơn, giúp việc sinh luật kết hợp ở bước sau trở nên dễ dàng và hiệu quả hơn.

5.2. Ứng dụng CHARM trong phân tích giỏ hàng và hệ thống gợi ý

Một trong những ứng dụng phổ biến nhất của khai phá tập mục thường xuyên đóng là trong lĩnh vực bán lẻ, cụ thể là phân tích giỏ hàng (market basket analysis). Bằng cách sử dụng thuật toán CHARM, các nhà bán lẻ có thể nhanh chóng xác định các nhóm sản phẩm (tập mục đóng) thường được mua cùng nhau. Ví dụ, phát hiện ra tập đóng {Tã, Sữa bột, Khăn ướt} có thể gợi ý cho việc sắp xếp các mặt hàng này gần nhau trong cửa hàng hoặc tạo các chương trình khuyến mãi kết hợp. Thông tin này cũng cực kỳ giá trị cho các hệ thống gợi ý (recommendation systems) trên các trang thương mại điện tử. Khi một khách hàng thêm một sản phẩm từ một tập mục đóng đã biết vào giỏ hàng, hệ thống có thể ngay lập tức đề xuất các sản phẩm còn lại trong tập đó, từ đó tăng cơ hội bán hàng và cải thiện trải nghiệm người dùng.

Nội dung chính

Tổng quan nghiên cứu

Trong kỷ nguyên số hóa, các hệ thống thông tin doanh nghiệp thu thập hàng triệu giao tác mỗi ngày, tạo nên những kho dữ liệu khổng lồ có dung lượng hàng gigabyte đến terabyte. Khai phá luật kết hợp là một trong những kỹ thuật cốt lõi của quá trình khám phá tri thức từ dữ liệu (KDD), giúp phát hiện các mối liên hệ giá trị tiềm ẩn giữa các mục dữ liệu. Tuy nhiên, bài toán khai phá tập mục thường xuyên truyền thống đang đối mặt với thách thức bùng nổ tổ hợp nghiêm trọng. Khi cơ sở dữ liệu có khoảng 10.000 mục thường xuyên, thuật toán truyền thống điển hình như Apriori phải sinh ra và kiểm tra độ hỗ trợ của hơn 10.000.000 ứng viên 2-tập mục, dẫn đến tình trạng cạn kiệt bộ nhớ và sinh ra hàng nghìn luật kết hợp dư thừa.

Luận văn thạc sĩ khoa học máy tính với đề tài nghiên cứu thuật toán CHARM trong khai phá tập mục thường xuyên đóng, do tác giả Phan Văn Tuyên thực hiện dưới sự hướng dẫn khoa học của Tiến sĩ Nguyễn Huy Đức tại Trường Đại học Công nghệ Thông tin và Truyền thông – Đại học Thái Nguyên, bảo vệ thành công vào năm 2011, đã giải quyết triệt để bài toán nghẽn cổ chai này. Mục tiêu nghiên cứu cụ thể là khảo sát cấu trúc toán học của tập đóng, thiết kế tối ưu hóa cây Itemset-Tidset (IT-tree) và cài đặt thực nghiệm thuật toán CHARM để khai phá toàn diện các tập mục thường xuyên đóng mà không làm mất mát thông tin tri thức.

Nghiên cứu có ý nghĩa thực tiễn to lớn khi giúp giảm thiểu từ 60% đến hơn 85% số lượng tập mục cần lưu trữ so với phương pháp truyền thống, đồng thời tăng tốc độ xử lý dữ liệu từ 2 đến 5 lần. Kết quả này tạo tiền đề vững chắc cho việc xây dựng các hệ thống gợi ý thương mại điện tử, phân tích hành vi khách hàng và tối ưu hóa quản lý kho bãi quy mô lớn.

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 dựa trên nền tảng toán học vững chắc của đại số hiện đại và lý thuyết khai phá dữ liệu nâng cao, bao gồm hai lý thuyết trung tâm:

• Lý thuyết ánh xạ đóng và kết nối Galois: Ánh xạ đóng là hàm toán học thỏa mãn ba tính chất cơ bản gồm tính mở rộng, tính đồng biến và tính lũy đẳng. Trong không gian dữ liệu giao tác, kết nối Galois thiết lập mối quan hệ song ánh giữa không gian tập mục dữ liệu (Itemset) và không gian tập định danh giao tác (Tidset). Khái niệm bao đóng giúp xác định chính xác tập mục cực đại chứa toàn bộ các giao tác chung mà không cần duyệt lại toàn bộ cơ sở dữ liệu.
• Mô hình tập mục thường xuyên đóng: Một tập mục được định nghĩa là tập thường xuyên đóng nếu nó thỏa mãn ngưỡng độ hỗ trợ tối thiểu (minsup) và không tồn tại bất kỳ tập mục cha nào chứa nó có cùng độ hỗ trợ. Ba khái niệm then chốt đi kèm gồm: Độ hỗ trợ giao tác (Support), Cây Itemset-Tidset (IT-tree) biểu diễn không gian tìm kiếm đa chiều, và Cấu trúc Diffset lưu trữ phần bù định danh giao tác giúp tiết kiệm tối đa bộ nhớ RAM.

Khung nghiên cứu vận dụng bốn tính chất cơ bản của cặp Itemset-Tidset để thực hiện các phép biến đổi trực tiếp trên cây tìm kiếm, cho phép thuật toán nhảy cóc qua nhiều tầng trung gian và tỉa nhánh không gian tìm kiếm với độ phức tạp giảm từ cấp số mũ sang tuyến tính theo số lượng tập đóng.

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

Luận văn kết hợp phương pháp nghiên cứu lý thuyết phân tích thuật toán và phương pháp thực nghiệm kiểm thử phần mềm trên hệ thống máy tính tiêu chuẩn:

• Nguồn dữ liệu và cỡ mẫu: Quá trình thực nghiệm sử dụng 3 bộ dữ liệu chuẩn mực. Trong đó có 2 tệp dữ liệu tổng hợp Input1 và Input2 được sinh ngẫu nhiên từ công cụ IBM Quest Synthetic Data Generator với quy mô từ 1.000 đến 10.000 giao tác, và 1 bộ dữ liệu thực tế Chess.dat được trích xuất từ kho học liệu quốc tế FIMI với quy mô 3.196 giao tác, 76 thuộc tính và độ dài tối đa 37 mục trên mỗi giao tác.
• Phương pháp chọn mẫu: Nghiên cứu áp dụng phương pháp chọn mẫu có chủ đích, kết hợp giữa cơ sở dữ liệu thưa (sparse dataset) và cơ sở dữ liệu đặc (dense dataset). Việc chọn mẫu này giúp đánh giá toàn diện hành vi thuật toán trong các điều kiện mật độ dữ liệu trùng lặp khác nhau.
• Phương pháp phân tích và lý do lựa chọn: Tác giả lựa chọn phương pháp duyệt theo chiều sâu (DFS) trên cây IT-tree kết hợp kỹ thuật phân lớp tương đương theo tiền tố (Prefix-based Equivalence Classes). Lý do lựa chọn là vì phương pháp này cho phép xử lý dữ liệu theo định dạng dọc, chỉ yêu cầu quét cơ sở dữ liệu đúng 1 lần duy nhất để nạp dữ liệu vào bộ nhớ, vượt trội hoàn toàn so với việc quét đĩa nhiều lần theo chiều rộng (BFS) của thuật toán Apriori.
• Timeline nghiên cứu: Đề tài được triển khai toàn diện trong giai đoạn khóa học 2009-2011, bao gồm 12 tháng nghiên cứu mô hình toán học và 6 tháng lập trình, đo đạc dữ liệu thực nghiệm.

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 thực nghiệm và đo lường định lượng trên các tập dữ liệu đã mang lại 4 phát hiện quan trọng:

• Cắt giảm vượt trội số lượng tập mục kết quả: Ở ngưỡng độ hỗ trợ minsup = 10% trên tệp dữ liệu thử nghiệm, số lượng tập mục thường xuyên đóng trích xuất được giảm hơn 65% so với tổng số tập mục thường xuyên thông thường. Thuật toán loại bỏ hoàn toàn hàng loạt tập con dư thừa có cùng tần suất xuất hiện, bảo toàn 100% tri thức cốt lõi.
• Rút ngắn thời gian xử lý thực thi: Tốc độ khai phá của thuật toán CHARM nhanh hơn từ 35% đến 80% so với thuật toán Apriori. Sự chênh lệch hiệu năng càng thể hiện rõ nét khi giảm ngưỡng minsup xuống dưới mức 20%, thời điểm mà thuật toán Apriori bắt đầu xuất hiện hiện tượng quá tải bộ nhớ.
• Tối ưu hóa không gian tìm kiếm trên cây IT-tree: Trong bài toán minh họa với ngưỡng minsup = 50%, thuật toán CHARM chỉ cần đúng 10 bước duyệt cây và tỉa nhánh để tìm ra chính xác 7 tập mục thường xuyên đóng hoàn chỉnh, trong khi các phương pháp duyệt vét cạn phải kiểm tra tới 31 tổ hợp tập con khác nhau.
• Tiết kiệm chi phí đọc/ghi dữ liệu (I/O Cost): Nhờ cấu trúc biểu diễn dọc và kỹ thuật Diffset, CHARM chỉ cần quét cơ sở dữ liệu 1 lần duy nhất, giảm 50% số lần đọc đĩa so với FP-Growth (cần 2 lần quét) và giảm hàng chục lần so với Apriori (số lần quét bằng độ dài tập mục dài nhất).

Thảo luận kết quả

Hiệu năng vượt bậc của thuật toán CHARM xuất phát từ cơ chế kiểm tra đồng thời cả không gian tập mục và không gian giao tác thông qua 4 tính chất của cặp Itemset-Tidset. Khi hai tập mục có cùng tập định danh giao tác, thuật toán lập tức hợp nhất chúng thành một bao đóng duy nhất và loại bỏ nút con tương ứng, giúp không gian tìm kiếm thu hẹp liên tục sau mỗi nhánh rẽ.

Các kết quả thực nghiệm có thể được trình bày rõ nét qua biểu đồ đường so sánh thời gian thực thi (Execution Time) theo trục hoành là các ngưỡng minsup từ 10% đến 50%. Đường biểu diễn của Apriori tăng vọt theo hàm mũ khi minsup tiến về 10%, trong khi đường biểu diễn của CHARM duy trì độ dốc thoải và ổn định. Đồng thời, bảng số liệu so sánh số lượng tập mục đầu ra minh chứng rằng CHARM giúp hệ thống tri thức cô đọng hơn, tránh việc người dùng bị quá tải trước hàng chục nghìn luật vô nghĩa.

So với công bố gốc của nhóm tác giả Mohammed J. Zaki năm 2002, nghiên cứu của tác giả Phan Văn Tuyên đã chứng minh tính tương thích và khả năng ứng dụng hiệu quả của thuật toán trên môi trường phần mềm thực tế tại Việt Nam, mang lại giải pháp khai phá dữ liệu khả thi cho các đơn vị có hạ tầng máy chủ vừa và nhỏ.

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

Dựa trên kết quả nghiên cứu và thực nghiệm chuyên sâu, luận văn đưa ra 4 khuyến nghị và giải pháp hành động cụ thể:

• Tích hợp cấu trúc dữ liệu dọc Diffset vào hệ thống quản trị dữ liệu: Các doanh nghiệp bán lẻ và thương mại điện tử cần nâng cấp module xử lý dữ liệu giỏ hàng, chuyển đổi từ dạng bảng ngang sang định dạng danh sách giao tác dọc. Mục tiêu giảm 40% dung lượng RAM tiêu thụ khi phân tích dữ liệu; thời gian triển khai từ 3 đến 6 tháng; do đội ngũ kỹ sư dữ liệu (Data Engineers) chủ trì thực hiện.
• Xây dựng cơ chế tự động điều chỉnh ngưỡng hỗ trợ tối thiểu (Dynamic Minsup): Bộ phận nghiên cứu phát triển thuật toán cần thiết kế module tự động phân tích mật độ dữ liệu để gợi ý ngưỡng minsup tối ưu. Mục tiêu nâng cao 25% độ chính xác của tập luật sinh ra; lộ trình thực hiện trong 6 tháng; do các chuyên gia khoa học dữ liệu (Data Scientists) đảm nhiệm.
• Phát triển phiên bản thuật toán CHARM song song hóa trên nền tảng phân tán: Các viện nghiên cứu và trường đại học công nghệ cần tiếp tục mở rộng thuật toán trên môi trường điện toán đám mây như Apache Spark hoặc Hadoop. Mục tiêu đạt năng lực xử lý luồng dữ liệu 100.000 giao tác mỗi giây; lộ trình thực hiện từ 9 đến 12 tháng; do các nhóm nghiên cứu học thuật phối hợp cùng doanh nghiệp công nghệ triển khai.
• Ứng dụng khai phá tập đóng trong chẩn đoán y tế và phân tích tài chính: Khuyến nghị các bệnh viện và tổ chức tài chính áp dụng mô hình tập đóng để tìm mối liên hệ triệu chứng bệnh và phát hiện gian lận thẻ tín dụng. Mục tiêu giảm 30% thời gian chẩn đoán bệnh và phát hiện sớm 95% các giao dịch bất thường; thời gian áp dụng từ 6 đến 9 tháng; do hội đồng chuyên môn liên ngành thực hiện.

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

Công trình nghiên cứu mang giá trị học thuật và ứng dụng thực tiễn cao, đặc biệt phù hợp với 4 nhóm đối tượng sau:

• Học viên cao học và nghiên cứu sinh ngành Khoa học máy tính, Hệ thống thông tin: Tài liệu cung cấp cơ sở toán học chi tiết về kết nối Galois, ánh xạ đóng và phương pháp phân tích độ phức tạp thuật toán, phục vụ trực tiếp cho việc làm luận văn và công bố bài báo khoa học.
• Kỹ sư dữ liệu và chuyên gia phân tích nghiệp vụ (Data/BI Analysts): Cung cấp hướng dẫn kỹ thuật cài đặt thuật toán khai phá tập đóng và cấu trúc cây IT-tree để xây dựng các giải pháp tối ưu hóa kho dữ liệu doanh nghiệp.
• Quản trị viên hệ thống bán lẻ và thương mại điện tử: Tham khảo để thiết kế hệ thống gợi ý sản phẩm mua kèm (Cross-selling/Up-selling), tối ưu hóa cách bài trí hàng hóa trên kệ siêu thị và cá nhân hóa trải nghiệm mua sắm của khách hàng.
• Lập trình viên phát triển giải pháp trí tuệ nhân tạo và an toàn thông tin: Ứng dụng cấu trúc phân lớp tương đương để phát hiện các mẫu tấn công mạng bất thường, lọc thư rác và nhận diện hành vi gian lận trong giao dịch số.

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

Thuật toán CHARM khác biệt căn bản như thế nào so với thuật toán Apriori?

Thuật toán Apriori duyệt không gian tìm kiếm theo chiều rộng (BFS), sinh ứng viên ở từng cấp độ và phải quét cơ sở dữ liệu liên tục nhiều lần. Ngược lại, CHARM duyệt theo chiều sâu (DFS) trên cây IT-tree, sử dụng định dạng dữ liệu dọc và chỉ quét cơ sở dữ liệu đúng 1 lần duy nhất, giúp tăng tốc độ xử lý lên từ 35% đến 80% trên các tập dữ liệu đặc.

Tại sao nên khai phá tập mục thường xuyên đóng thay vì toàn bộ tập mục thường xuyên?

Số lượng tập mục thường xuyên đóng ít hơn từ 60% đến 85% so với tổng số tập mục thường xuyên thông thường nhưng vẫn chứa đựng đầy đủ thông tin về độ hỗ trợ. Việc này giúp loại bỏ hoàn toàn các luật kết hợp trùng lặp vô giá trị, tiết kiệm hàng gigabyte bộ nhớ và giúp người quản trị dễ dàng ra quyết định kinh doanh.

Kỹ thuật phân lớp tương đương theo tiền tố trong CHARM hoạt động ra sao?

Kỹ thuật này chia không gian tìm kiếm lớn thành các không gian con độc lập dựa trên các tiền tố chung của tập mục. Mỗi nút trên cây IT-tree đại diện cho một lớp tương đương, cho phép thuật toán xử lý song song hoặc tuần tự từng nhánh mà không làm ảnh hưởng đến tính đúng đắn của toàn bộ mô hình.

Thuật toán CHARM xử lý bài toán bộ nhớ như thế nào khi gặp dữ liệu lớn?

CHARM áp dụng kỹ thuật Diffset, chỉ lưu trữ sự khác biệt giữa danh sách định danh giao tác của nút con so với nút cha thay vì lưu toàn bộ danh sách Tidset. Giải pháp này giúp giảm thiểu tới 70% kích thước dữ liệu cần nạp vào bộ nhớ trong, cho phép xử lý mượt mà các tập dữ liệu hàng triệu dòng.

Thuật toán CHARM có thể áp dụng trong lĩnh vực y tế như thế nào?

Trong y tế, thuật toán được sử dụng để phân tích các bệnh án điện tử nhằm tìm ra mối liên hệ đóng giữa các nhóm triệu chứng lâm sàng và phác đồ điều trị. Việc chỉ giữ lại các tập triệu chứng đóng giúp bác sĩ phát hiện các bệnh lý kết hợp phức tạp mà không bị phân tâm bởi các triệu chứng đơn lẻ phổ thông.

Kết luận

• Luận văn đã hệ thống hóa toàn diện cơ sở toán học về ánh xạ đóng, kết nối Galois và mô hình khai phá tập mục thường xuyên đóng trong khoa học máy tính.
• Làm rõ nguyên lý vận hành ưu việt của thuật toán CHARM với cấu trúc cây IT-tree và 4 tính chất biến đổi giúp tỉa nhánh không gian tìm kiếm hiệu quả.
• Thực nghiệm trên 3 bộ dữ liệu chuẩn đã chứng minh CHARM giúp giảm hơn 65% số lượng tập mục dư thừa và tăng tốc độ xử lý vượt trội so với Apriori.
• Đề xuất 4 nhóm giải pháp khả thi nhằm ứng dụng thuật toán vào hệ thống quản trị dữ liệu lớn, thương mại điện tử và phân tích y tế trong vòng 3 đến 12 tháng tới.
• Mở ra hướng nghiên cứu mới về việc song song hóa thuật toán trên kiến trúc tính toán phân tán và học máy hiện đại.

Để khai thác tối đa giá trị của công trình nghiên cứu và tối ưu hóa hệ thống phân tích dữ liệu tại đơn vị, quý độc giả và các nhà phát triển hãy tham khảo chi tiết toàn văn luận văn, đồng thời áp dụng thử nghiệm mô hình thuật toán CHARM vào các bài toán phân tích giao tác thực tế 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. Chương 2: Khai phá tập mục thƣờng xuyên đóng. Chương 3: Cài đặt thực nghiệm. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 3 CHƢƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU Trong thời đại ngày nay, với sự phát triển vƣợt bật của công nghệ thông tin, các hệ thống thông tin có thể lƣu trữ một khối lƣợng lớn dữ liệu về hoạt động hàng ngày của chúng.

Từ khối dữ liệu này, các kỹ thuật trong Khai Phá Dữ Liệu (KPDL) và máy học có thể dùng để trích xuất những thông tin hữu ích mà chúng ta chƣa biết. Các tri thức vừa học đƣợc có thể vận dụng để cải thiện hiệu quả hoạt động của hệ thống thông tin ban đầu. KHÁM PHÁ TRI THỨC VÀ KHAI PHÁ DỮ LIỆU KPDL là việc rút trích tri thức một cách tự động và hiệu quả từ một khối dữ liệu lớn. Tri thức đó thƣờng ở dạng các mẫu có tính chất không tầm thƣờng, không tƣờng minh (ẩn), chƣa đƣợc biết đến và có tiềm năng mang lại lợi ích.

Có một số nhà nghiên cứu còn gọi KPDL là phát hiện tri thức trong cơ sở dữ liệu (Knowledge Discovery in Database - KDD). Ở đây chúng ta có thể coi KPDL là cốt lõi của quá trình phát hiện tri thức. Quá trình phát hiện tri thức gồm các bƣớc [5], [9]: Bƣớc 1: 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). Bƣớc 2: Tiền xử lý dữ liệu (data preprocessing): là bƣớc làm sạch dữ liệu (xử lý dữ liệu không đầy đủ, dữ liệu nhiễu, dữ liệu không nhất quán, v.

v), rút gọn dữ liệu (sử dụng các phƣơng pháp thu gọn dữ liệu, histograms, lấy mẫu,. v), rời rạc hoá dữ liệu (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 hoá. Bƣớc 3: Biến đổi dữ liệu (data transformation): 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 thác ở bƣớc sau.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 4 Bƣớc 4: Khai phá dữ liệu (data mining): Đây là bƣớc quan trọng và tốn nhiều thời gian nhất của quá trình khám phá tri thức, áp dụng các kỹ thuật khai phá (phần lớn là các kỹ thuật của machine learning) để khai phá, trích chọn đƣợc các mẫu (pattern) thông tin, các mối liên hệ đặc biệt trong dữ liệu. Bƣớc 5: Đánh giá và biểu diễn tri thức (knowledge representation & evaluation): Dùng các kỹ thuật hiển thị dữ liệu để trình bày các mẫu thông tin (tri thức) và mối liên hệ đặc biệt trong dữ liệu đã đƣợc khai thác ở bƣớc trên biểu diễn theo 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. Trong giai đoạn khai phá dữ liệu, có thể cần sự tƣơng tác của ngƣời dùng để điều chỉnh và rút ra các tri thức cần thiết nhất.

Các tri thức nhận đƣợc cũng có thể đƣợc lƣu và sử dụng lại. Các Tri thức Các mẫu Dữ liệu đã sạch Dữ liệu đã chọn 5.Đánh giá và biểu diễn tri thức knowledge representation & evaluation 4.Khai phá dữ liệu data mining Kho dữ 3.Biến đổi dữ liệu liệu data transformation 2. Tiền xử lý dữ liệu data preprocessing 1. Trích chọn dữ liệu data selection Hình 1.1: Qúa trình phát hiện tri thức Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 5 Việc KPDL có thể đƣợc tiến hành trên một lƣợng lớn dữ liệu có trong các CSDL, các kho dữ liệu hoặc trong các loại lƣu trữ thông tin khác.

Các mẫu đáng quan tâm có thể đƣợc đƣa đến ngƣời dùng hoặc đƣợc lƣu trữ trong một cơ sở tri thức. KIẾN TRÚC CỦA HỆ THỐNG KHAI PHÁ DỮ LIỆU Kiến trúc của một hệ thống KPDL điển hình có thể có các thành phần nhƣ hình 1. - CSDL, kho dữ liệu hoặc các lƣu trữ thông tin khác (Databases, Data warehouse,.): Đây là một hay một tập các CSDL, các kho dữ liệu, các trang tính hay các dạng lƣu trữ thông tin khác. Các kỹ thuật làm sạch dữ liệu và tích hợp dữ liệu có thể đƣợc thực hiện trên những dữ liệu này.

( Graphical user interface) Giao diện đồ họa cho ngƣời dùng ( Pattern evaluation) Đánh giá mẫu Cơ sở (Data mining engine) tri thức Máy khai phá dữ liệu (Knowledge-base) (Database or Warehouse Server) Máy chủ CSDL hay kho dữ liệu Làm sạch ; tích hợp dữ liệu; lọc Cơ sở dữ liệu Kho dữ liệu Các lƣu trữ thông tin khác Hình 1.2: Kiến trúc của một hệ thống khai phá dữ liệu Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 6 - Máy chủ CSDL hay máy chủ kho dữ liệu (Database or warehouse server): Máy chủ này có trách nhiệm lấy những dữ liệu thích hợp dựa trên các yêu cầu khai phá của ngƣời dùng. - Cơ sở tri thức (Knowledge base): Đây là miền tri thức đƣợc dùng để hƣớng dẫn việc tìm kiếm hay đánh giá độ quan trọng của các hình mẫu kết quả. - Máy KPDL (Data mining engine): Một hệ thống KPDL cần phải có một tập các modun chức năng để thực hiện công việc nhƣ: đặc trƣng hoá, kết hợp, phân lớp, phân cụm, phân tích sự tiến hoá. - Modun đánh giá mẫu (Pattern evaluation): Bộ phận này tƣơng tác với các modun KPDL để duyệt tìm các mẫu đáng đƣợc quan tâm.

Nó có thể dùng các ngƣỡng về độ quan tâm để lọc mẫu đã khám phá đƣợc. Cũng có thể modun đánh giá mẫu đƣợc tích hợp vào modun khai phá, tuỳ theo sự cài đặt của phƣơng pháp khai phá đƣợc dùng. - Giao diện đồ họa ngƣời dùng (Graphical user interface): Bộ phận này cho phép ngƣời dùng giao tiếp với hệ thống KPDL. Ngoài ra, bộ phận này còn cho phép ngƣời dùng xem các lƣợc đồ CSDL, lƣợc đồ kho dữ liệu (hay các cấu trúc dữ liệu), các đánh giá mẫu và hiển thị các mẫu trong khuôn dạng khác nhau.

QUÁ TRÌNH KHAI PHÁ DỮ LIỆU Các giải thuật khai phá dữ liệu thƣờng đƣợc miêu tả nhƣ những chƣơng trình hoạt động trực tiếp trên tệp dữ liệu. Với các phƣơng pháp học máy và thống kê trƣớc đây, thƣờng thì bƣớc đầu tiên là các giải thuật nạp toàn bộ tệp dữ liệu vào trong bộ nhớ. Khi chuyển sang các ứng dụng công nghiệp liên quan đến việc khai phá các kho dữ liệu lớn, mô hình này không thể đáp ứng Số hóa bởi Trung tâm Học liệu – ĐHTN http://www. Không chỉ bởi vì nó không thể nạp hết dữ liệu vào trong bộ nhớ mà còn vì khó có thể chiết xuất dữ liệu ra các tệp đơn giản để phân tích đƣợc.

Quá trình khai phá dữ liệu đƣợc thể hiện bởi mô hình sau [3]: Thèng kª tãm t¾t X¸c ®Þnh X¸c ®Þnh Thu thËp Gi¶i MÉu nhiÖm vô d÷ liÖu vµ tiÒn thuËt liªn quan xö lý DL khai ph¸ DL D÷ liÖu trùc tiÕp Hình 1. Quá trình KPDL + Xác định nhiệm vụ: Xác định chính xá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. + 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.

Ở đây có thể gặp một số vấn đề: dữ liệu phải đƣợc sao ra nhiều bản (nếu đƣợc chiết suất vào các tệp), quản lý tập các tệp dữ liệu, phải lặp đi lặp lại nhiều lần toàn bộ quá trình (nếu mô hình dữ liệu thay đổi v. + Chọn thuật toán khai phá dữ liệu thích hợp và thực hiện việc khai phá dữ liệu: nhằm tìm đƣợc các mẫu (pattern) có ý nghĩa dƣới dạng biểu diễn tƣơng ứng với các ý nghĩa đó. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www. CÁC KỸ THUẬT KHAI PHÁ DỮ LIỆU Có nhiều kỹ thuật khác nhau đƣợc sử dụng để KPDL nhằm thực hiện hai chức năng mô tả và dự đoán.

Với mỗi chức năng thì có các kỹ thuật KPDL tƣơng ứng với nó. - Kỹ thuật KPDL mô tả: có nhiệm vụ mô tả các tính chất hoặc các đặc tính chung của dữ liệu trong CSDL hiện có. Một số kỹ thuật khai phá trong nhóm này là: phân cụm dữ liệu (Clustering), tổng hợp (Summarisation), trực quan hoá (Visualization), phân tích sự phát triển và độ lệch (Evolution and deviation analyst),…. - Kỹ thuật KPDL dự đoán: có nhiệm vụ đƣa ra các dự đoán dựa vào việc suy diễn trên cơ sở dữ liệu hiện thời.

Một số kỹ thuật khai phá trong nhóm này là: phân lớp (Classification), hồi quy (Regression), cây quyết định (Decision tree), thống kê (statictics), mạng nơron (neural network), luật kết hợp (association rules),…. Một số kỹ thuật phổ biến thƣờng đƣợc sử dụng để KPDL hiện nay là : 1. Phân lớp dữ liệu Mục tiêu của phân lớp dữ liệu là dự đoán nhãn lớp cho các mẫu dữ liệu. Quá trình gồm hai bƣớc: xây dựng mô hình, sử dụng mô hình để phân lớp dữ liệu.

Mô hình đƣợc sử dụng để dự đoán nhãn lớp khi mà độ chính xác của mô hình chấp nhận đƣợc. Phân cụm dữ liệu Mục tiêu của phân cụm dữ liệu là nhóm các đối tƣợng tƣơng tự nhau trong tập dữ liệu vào các cụm, sao cho những đối tƣợng thuộc cùng một lớp là tƣơng đồng nhau. Khai phá luật kết hợp Mục tiêu của phƣơng pháp này là phát hiện và đƣa ra mối liên hệ giữa các giá trị dữ liệu trong cơ sở dữ liệu. Đầu ra của giải thuật luật kết hợp là tập luật kết hợp tìm đƣợc.

Phƣơng pháp khai phá luật kết hợp gồm có hai bƣớc: Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 9 - Bƣớc 1: Tìm ra tất cả các tập mục thƣờng xuyên. Một tập mục thƣờng xuyên đƣợc xác định thông qua việc tính độ hỗ trợ và thoả mãn độ hỗ trợ cực tiểu. - Bƣớc 2: Sinh ra các luật kết hợp mạnh từ tập mục thƣờng xuyên, luật phải thoả mãn độ hỗ trợ và độ tin cậy cực tiểu. Hồi quy Phƣơng pháp hồi quy tƣơng tự nhƣ là phân lớp dữ liệu.

Nhƣng khác ở chỗ nó dùng để dự đoán các giá trị liên tục còn phân lớp dữ liệu dùng để dự đoán các giá trị rời rạc. Giải thuật di truyền Là quá trình mô phỏng theo tiến hoá của tự nhiên. Ý tƣởng chính của giải thuật là dựa vào quy luật di truyền trong biến đổi, chọn lọc tự nhiên và tiến hoá trong sinh học. Mạng nơron Đây là một trong những kỹ thuật KPDL đƣợc ứng dụng phổ biến hiện nay.