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.

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.