Luận Văn Thạc Sĩ Về Khai Phá Mẫu Phổ Biến, Luật Kết Hợp Và Thước Đo Tương Quan

Luận văn thạc sĩ VNU UET khám phá mẫu phổ biến luật kết hợp và thước đo tương quan, cung cấp cái nhìn sâu sắc về nghiên cứu và ứng dụng.

• Tác giả: Vũ Mỹ Hạnh
• Người hướng dẫn: TS. Nguyễn Công Điều
• Trường học: Đại học Quốc gia Hà Nội
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Khai Phá Mẫu Phổ Biến và Luật Kết Hợp
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2011
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ MẪU PHỔ BIẾN, LUẬT KẾT HỢP VÀ CÁC THƯỚC ĐO TƯƠNG QUAN
• 1.1. Tổng quan về khai phá dữ liệu
• 1.2. Các hướng tiếp cận trong khai phá dữ liệu
• 1.3. Một số ứng dụng trong khai phá dữ liệu
• 1.4. Một số thách thức trong khai phá dữ liệu
• 1.5. Các khái niệm cơ bản về khai phá mẫu phổ biến tìm luật kết hợp và phân tích mối tương quan
• 1.5.1. Khái niệm về khai phá mẫu phổ biến
• 1.5.2. Phát biểu bài toán tìm luật kết hợp
• 1.5.3. Minh họa bài toán khai phá mẫu phổ biến tìm luật kết hợp
• 1.5.4. Mối tương quan giữa các mục
• 2. CHƯƠNG 2: MỘT SỐ PHƯƠNG PHÁP KHAI PHÁ LUẬT KẾT HỢP
• 2.1. Phương pháp khai phá tập mục phổ biến sử dụng kỹ thuật sinh ứng viên
• 2.2. Tư tưởng của thuật toán
• 2.3. Tính chất Apriori
• 2.4. Các bước thực hiện thuật toán Apriori
• 2.5. Phương pháp sinh luật kết hợp mạnh
• 2.6. Phương pháp khai phá tập mục phổ biến không cần sinh ứng viên
• 2.7. Một số bất cập trong phương pháp khai phá tập phổ biến sử dụng kỹ thuật sinh ứng viên
• 2.8. Thuật toán FP-growth
• 2.9. Giới thiệu một số thuật toán khai phá tập mục phổ biến khác
• 2.9.1. Thuật toán Apriori-TID
• 2.9.2. Thuật toán Apriori-Hybrid
• 2.9.3. Thuật toán AIS (Agrawal Imielinski Swami)
• 2.9.4. Thuật toán DIC (Dynamic Itemset Counting)
• 2.9.5. Thuật toán phân hoạch
• 2.10. Khai phá luật kết hợp định lượng
• 2.11. Một số hướng tiếp cận trong khai phá luật kết hợp
• 2.12. Khai phá luật kết hợp định lượng. Các thước đo tương quan
• 2.13. Các luật mạnh không nhất thiết đã thú vị. Từ phân tích luật kết hợp đến phân tích tương quan
• 3. CHƯƠNG 3: GIỚI THIỆU CÔNG CỤ KHAI PHÁ DỮ LIỆU WEKA VÀ MÔ PHỎNG
• 3.1. Tổng quan về phần mềm Weka
• 3.2. Cửa sổ ứng dụng Explorer trong Weka
• 3.3. Giao diện người dùng
• 3.4. Tiền xử lý – Preprocessing
• 3.5. Luật kết hợp
• 3.6. Một số định dạng tập tin trong Weka
• 3.7. Sử dụng công cụ Weka mô phỏng thuật toán sinh luật kết hợp
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Về Khai Phá Mẫu Phổ Biến và Luật Kết Hợp

Khai phá mẫu phổ biến và luật kết hợp là hai khái niệm quan trọng trong lĩnh vực khai thác dữ liệu. Chúng giúp phát hiện các mẫu và mối quan hệ trong dữ liệu lớn, từ đó hỗ trợ ra quyết định trong nhiều lĩnh vực khác nhau. Việc hiểu rõ về khai thác dữ liệu và các phương pháp liên quan là cần thiết để áp dụng hiệu quả trong thực tiễn.

1.1. Khái Niệm Về Khai Phá Mẫu Phổ Biến

Khai phá mẫu phổ biến đề cập đến việc tìm kiếm các tập mục xuất hiện thường xuyên trong một tập dữ liệu. Điều này giúp xác định các mẫu có giá trị, từ đó hỗ trợ cho việc phân tích và ra quyết định.

1.2. Luật Kết Hợp Là Gì

Luật kết hợp là một kỹ thuật trong khai thác dữ liệu nhằm tìm ra mối quan hệ giữa các mục trong một tập dữ liệu. Luật này thường được biểu diễn dưới dạng A ⇒ B, cho thấy rằng nếu A xảy ra thì B cũng có khả năng xảy ra.

II. Thách Thức Trong Khai Phá Mẫu Phổ Biến và Luật Kết Hợp

Mặc dù khai thác dữ liệu mang lại nhiều lợi ích, nhưng vẫn tồn tại nhiều thách thức trong quá trình thực hiện. Các vấn đề như dữ liệu lớn, dữ liệu không đầy đủ và mối quan hệ phức tạp giữa các thuộc tính là những khó khăn chính cần giải quyết.

2.1. Dữ Liệu Lớn và Độ Phức Tạp

Khi làm việc với các cơ sở dữ liệu lớn, việc tìm kiếm các mẫu phổ biến trở nên khó khăn hơn do số lượng bản ghi và thuộc tính tăng lên. Điều này dẫn đến việc cần phải có các phương pháp tối ưu hóa hiệu quả hơn.

2.2. Dữ Liệu Không Đầy Đủ

Dữ liệu không đầy đủ có thể gây ra những sai lệch trong kết quả khai phá. Việc xử lý các giá trị thiếu và không chính xác là một thách thức lớn trong khai thác dữ liệu.

III. Phương Pháp Khai Phá Mẫu Phổ Biến Hiệu Quả

Có nhiều phương pháp khác nhau để khai phá mẫu phổ biến, trong đó thuật toán Apriori và FP-Growth là hai phương pháp phổ biến nhất. Những phương pháp này giúp tối ưu hóa quá trình tìm kiếm và phân tích dữ liệu.

3.1. Thuật Toán Apriori

Thuật toán Apriori là một trong những phương pháp đầu tiên được sử dụng để khai phá luật kết hợp. Nó dựa trên nguyên tắc rằng nếu một tập mục là phổ biến, thì tất cả các tập con của nó cũng phải phổ biến.

3.2. Thuật Toán FP Growth

FP-Growth là một phương pháp khai phá mẫu phổ biến không cần sinh ứng viên. Nó sử dụng cấu trúc cây để lưu trữ thông tin, giúp giảm thiểu thời gian và không gian tính toán.

IV. Ứng Dụng Thực Tiễn Của Khai Phá Mẫu Phổ Biến

Khai phá mẫu phổ biến và luật kết hợp có nhiều ứng dụng thực tiễn trong các lĩnh vực như marketing, y tế, và tài chính. Những ứng dụng này giúp các tổ chức đưa ra quyết định chính xác hơn dựa trên dữ liệu.

4.1. Ứng Dụng Trong Marketing

Trong marketing, khai phá mẫu phổ biến giúp phân tích thói quen mua sắm của khách hàng, từ đó tối ưu hóa chiến lược tiếp thị và tăng doanh thu.

4.2. Ứng Dụng Trong Y Tế

Trong lĩnh vực y tế, khai phá dữ liệu giúp phát hiện mối quan hệ giữa triệu chứng và bệnh lý, từ đó hỗ trợ cho việc chẩn đoán và điều trị hiệu quả hơn.

V. Kết Luận Về Khai Phá Mẫu Phổ Biến và Luật Kết Hợp

Khai phá mẫu phổ biến và luật kết hợp là những công cụ mạnh mẽ trong khai thác dữ liệu. Việc hiểu rõ và áp dụng các phương pháp này sẽ giúp các tổ chức khai thác tối đa giá trị từ dữ liệu của họ.

5.1. Tương Lai Của Khai Phá Dữ Liệu

Với sự phát triển không ngừng của công nghệ, tương lai của khai thác dữ liệu hứa hẹn sẽ mang lại nhiều cơ hội mới cho các nhà nghiên cứu và doanh nghiệp.

5.2. Tầm Quan Trọng Của Đào Tạo

Đào tạo và nâng cao kỹ năng cho nhân viên trong lĩnh vực khai thác dữ liệu là rất quan trọng để đảm bảo rằng các tổ chức có thể tận dụng tối đa các công cụ và phương pháp hiện có.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh phát triển vượt bậc của khoa học và công nghệ, khả năng thu thập và lưu trữ dữ liệu ngày càng tăng, dẫn đến sự xuất hiện của các kho dữ liệu khổng lồ với dung lượng lên đến hàng Gigabyte (GB) hoặc Terabyte (TB). Việc khai thác tri thức từ các kho dữ liệu này trở thành một thách thức lớn, đòi hỏi các phương pháp phân tích hiệu quả để rút ra các thông tin hữu ích phục vụ cho các lĩnh vực khoa học, kinh tế và xã hội. Khai phá dữ liệu (Data Mining) là lĩnh vực khoa học liên ngành nhằm tự động hóa quá trình trích xuất tri thức tiềm ẩn trong cơ sở dữ liệu, vượt trội hơn hẳn so với các công cụ phân tích truyền thống.

Một trong những nhiệm vụ quan trọng của khai phá dữ liệu là khai phá mẫu phổ biến (Frequent Pattern Mining), đóng vai trò thiết yếu trong việc tìm kiếm luật kết hợp (Association Rules) và phân tích mối tương quan giữa các mục trong dữ liệu. Luận văn tập trung nghiên cứu các phương pháp khai phá mẫu phổ biến, luật kết hợp và các thước đo tương quan, đặc biệt là các thuật toán khai phá tập mục phổ biến sử dụng kỹ thuật sinh ứng viên và phương pháp không cần sinh ứng viên như FP-growth. Phạm vi nghiên cứu tập trung vào các thuật toán khai phá dữ liệu trong lĩnh vực Công nghệ thông tin, chuyên ngành Hệ thống thông tin, với dữ liệu giao dịch thực tế và mô phỏng trên công cụ Weka.

Mục tiêu chính của luận văn là phân tích, đánh giá các phương pháp khai phá mẫu phổ biến và luật kết hợp, đồng thời đề xuất các giải pháp cải tiến nhằm nâng cao hiệu quả khai phá dữ liệu, giảm thiểu chi phí tính toán và tăng độ chính xác của các luật kết hợp định lượng. Nghiên cứu có ý nghĩa quan trọng trong việc hỗ trợ ra quyết định dựa trên dữ liệu lớn, góp phần phát triển các ứng dụng trong quản lý thị trường, tài chính, y học và nhiều lĩnh vực khác.

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 dựa trên các lý thuyết và mô hình nghiên cứu sau:

• Khai phá dữ liệu (Data Mining): Quá trình tự động trích xuất các mẫu, luật và mối quan hệ có ý nghĩa từ cơ sở dữ liệu lớn. Tiến trình khai phá tri thức (KDD) bao gồm các bước: chọn lựa dữ liệu, tiền xử lý, biến đổi dữ liệu, khai phá dữ liệu và trình diễn tri thức.

• Khai phá mẫu phổ biến (Frequent Pattern Mining): Tìm kiếm các tập mục (itemsets) xuất hiện phổ biến trong tập dữ liệu giao dịch, làm cơ sở để sinh ra các luật kết hợp mạnh.

• Luật kết hợp (Association Rules): Các luật dạng A ⇒ B, trong đó A và B là các tập con không giao nhau của tập mục, được đánh giá bằng độ hỗ trợ (support) và độ tin cậy (confidence). Luật mạnh là luật thỏa mãn ngưỡng hỗ trợ và tin cậy tối thiểu do người dùng định nghĩa.

• Thuật toán Apriori: Thuật toán khai phá tập mục phổ biến dựa trên kỹ thuật sinh ứng viên và tính chất không đơn điệu (Apriori property), giúp giảm không gian tìm kiếm bằng cách loại bỏ các tập mục không phổ biến.

• Thuật toán FP-growth: Phương pháp khai phá tập mục phổ biến không cần sinh ứng viên, sử dụng cấu trúc cây FP-tree để nén dữ liệu và khai phá mẫu phổ biến hiệu quả hơn, đặc biệt với các mẫu dài.

• Luật kết hợp định lượng (Quantitative Association Rules): Mở rộng khai phá luật kết hợp cho các thuộc tính định lượng và phân loại, sử dụng kỹ thuật phân vùng giá trị định lượng thành các khoảng và ánh xạ sang dạng nhị phân để áp dụng các thuật toán khai phá luật kết hợp.

• Mức đầy đủ bộ phận (Partial Completeness Level): Khái niệm dùng để kiểm soát lượng thông tin mất mát khi phân vùng các thuộc tính định lượng, đảm bảo các luật sinh ra vẫn giữ được độ tin cậy và hỗ trợ cần thiết.

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

• Nguồn dữ liệu: Sử dụng các cơ sở dữ liệu giao dịch thực tế và mô phỏng trên công cụ Weka, bao gồm các tập dữ liệu có thuộc tính định lượng và phân loại.

• Phương pháp phân tích:

  • Áp dụng thuật toán Apriori để khai phá tập mục phổ biến và sinh luật kết hợp mạnh.
  • Phân tích các hạn chế của phương pháp sinh ứng viên, đặc biệt khi số lượng tập mục phổ biến lớn hoặc ngưỡng hỗ trợ thấp.
  • Áp dụng thuật toán FP-growth để khai phá tập mục phổ biến không cần sinh ứng viên, giảm chi phí tính toán và tăng tốc độ xử lý.
  • Ánh xạ các thuộc tính định lượng và phân loại sang dạng nhị phân để khai phá luật kết hợp định lượng.
  • Sử dụng khái niệm mức đầy đủ bộ phận để xác định số lượng khoảng phân vùng tối ưu, cân bằng giữa độ chính xác và hiệu quả tính toán.

• Timeline nghiên cứu:

  • Giai đoạn 1: Tổng quan lý thuyết và khảo sát các thuật toán khai phá dữ liệu (3 tháng).
  • Giai đoạn 2: Phân tích và mô phỏng thuật toán Apriori và FP-growth trên công cụ Weka (4 tháng).
  • Giai đoạn 3: Nghiên cứu khai phá luật kết hợp định lượng và đề xuất phương pháp phân vùng tối ưu (3 tháng).
  • Giai đoạn 4: Tổng hợp kết quả, viết luận văn và hoàn thiện (2 tháng).

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

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

1. Hiệu quả của thuật toán Apriori: Thuật toán Apriori có khả năng tìm tập mục phổ biến chính xác với độ hỗ trợ tối thiểu 22% trên tập dữ liệu gồm 9 giao dịch. Tuy nhiên, khi số lượng tập mục phổ biến tăng lên (ví dụ 10^4 tập mục phổ biến 1-itemsets), số lượng tập mục ứng viên 2-itemsets có thể lên đến hơn 10^7, gây tốn kém về thời gian và bộ nhớ.

2. Ưu điểm của thuật toán FP-growth: FP-growth giảm đáng kể số lần quét cơ sở dữ liệu (chỉ 2 lần) và không sinh tập mục ứng viên, giúp tăng tốc độ xử lý. Trên tập dữ liệu mô phỏng, FP-growth xử lý nhanh hơn Apriori từ 20% đến 50% tùy thuộc vào kích thước dữ liệu và độ dài mẫu phổ biến.

3. Khai phá luật kết hợp định lượng: Ánh xạ các thuộc tính định lượng và phân loại sang dạng nhị phân cho phép áp dụng các thuật toán khai phá luật kết hợp nhị phân. Tuy nhiên, việc phân vùng giá trị định lượng thành nhiều khoảng nhỏ có thể làm giảm độ hỗ trợ của từng khoảng, dẫn đến mất một số luật có ý nghĩa. Kết hợp các khoảng liền kề giúp tăng độ hỗ trợ và giảm số lượng luật không đáng quan tâm.

4. Mức đầy đủ bộ phận và phân vùng tối ưu: Xác định mức đầy đủ bộ phận K giúp cân bằng giữa độ tin cậy và độ hỗ trợ của các luật sinh ra. Phân vùng với kích thước đều (equi-depth) được chứng minh là tối ưu trong việc giảm số lượng khoảng cần thiết để đạt mức đầy đủ bộ phận, từ đó giảm thiểu mất mát thông tin và tăng hiệu quả khai phá.

Thảo luận kết quả

Kết quả nghiên cứu cho thấy thuật toán Apriori, mặc dù là phương pháp cơ bản và phổ biến, gặp khó khăn khi xử lý dữ liệu lớn hoặc khi ngưỡng hỗ trợ thấp do số lượng tập mục ứng viên tăng đột biến. Việc quét nhiều lần cơ sở dữ liệu cũng làm tăng chi phí tính toán. Trong khi đó, FP-growth với cấu trúc cây FP-tree giúp nén dữ liệu và khai phá hiệu quả hơn, đặc biệt với các mẫu dài và dữ liệu lớn.

Việc mở rộng khai phá luật kết hợp sang dạng định lượng là cần thiết để phản ánh đúng bản chất dữ liệu thực tế, nơi các thuộc tính không chỉ là nhị phân mà còn có giá trị liên tục hoặc phân loại phức tạp. Tuy nhiên, việc phân vùng giá trị định lượng cần được thực hiện cẩn trọng để tránh mất mát thông tin và sinh ra quá nhiều luật không cần thiết.

Mức đầy đủ bộ phận là một khái niệm quan trọng giúp kiểm soát chất lượng luật kết hợp định lượng, đảm bảo các luật sinh ra vẫn giữ được độ tin cậy và hỗ trợ cần thiết. Phân vùng kích thước đều được khuyến nghị vì tính tối ưu trong việc giảm số lượng khoảng và duy trì độ chính xác.

Các kết quả này phù hợp với các nghiên cứu trong ngành và có thể được minh họa qua các biểu đồ so sánh thời gian xử lý giữa Apriori và FP-growth, bảng thống kê số lượng luật sinh ra theo các mức phân vùng khác nhau, cũng như biểu đồ thể hiện mức đầy đủ bộ phận K tương ứng với số lượng khoảng phân vùng.

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

1. Áp dụng thuật toán FP-growth trong khai phá mẫu phổ biến: Để nâng cao hiệu quả khai phá dữ liệu, các tổ chức nên ưu tiên sử dụng thuật toán FP-growth thay vì Apriori, đặc biệt khi xử lý dữ liệu lớn hoặc có nhiều mẫu dài. Thời gian thực hiện có thể giảm từ 20% đến 50% so với phương pháp truyền thống. Chủ thể thực hiện: các nhà phân tích dữ liệu, kỹ sư dữ liệu. Timeline: triển khai trong 3-6 tháng.

2. Phân vùng giá trị định lượng theo kích thước đều: Khi khai phá luật kết hợp định lượng, nên phân vùng các thuộc tính định lượng thành các khoảng có kích thước đều để tối ưu hóa mức đầy đủ bộ phận, giảm thiểu mất mát thông tin và số lượng luật không cần thiết. Chủ thể thực hiện: nhà khoa học dữ liệu, nhà nghiên cứu. Timeline: áp dụng trong giai đoạn tiền xử lý dữ liệu.

3. Sử dụng mức đầy đủ bộ phận để điều chỉnh ngưỡng hỗ trợ và tin cậy: Để đảm bảo các luật sinh ra có độ tin cậy và hỗ trợ phù hợp, cần xác định mức đầy đủ bộ phận K và điều chỉnh ngưỡng tin cậy tối thiểu tương ứng (min-conf/K). Chủ thể thực hiện: chuyên gia khai phá dữ liệu, nhà phát triển thuật toán. Timeline: tích hợp trong quá trình thiết kế mô hình khai phá.

4. Tích hợp công cụ Weka cho mô phỏng và đánh giá thuật toán: Khuyến nghị sử dụng công cụ Weka để mô phỏng các thuật toán khai phá dữ liệu, giúp đánh giá hiệu quả và điều chỉnh tham số phù hợp với từng tập dữ liệu cụ thể. Chủ thể thực hiện: sinh viên, nhà nghiên cứu, kỹ sư dữ liệu. Timeline: sử dụng trong quá trình nghiên cứu và phát triển.

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

1. Nhà nghiên cứu và sinh viên ngành Công nghệ thông tin, Hệ thống thông tin: Luận văn cung cấp kiến thức chuyên sâu về khai phá dữ liệu, thuật toán Apriori, FP-growth và khai phá luật kết hợp định lượng, hỗ trợ nghiên cứu và phát triển các đề tài liên quan.

2. Chuyên gia phân tích dữ liệu và kỹ sư dữ liệu: Các giải pháp và thuật toán được trình bày giúp cải thiện hiệu quả khai phá dữ liệu lớn, hỗ trợ ra quyết định trong doanh nghiệp và tổ chức.

3. Nhà quản lý và hoạch định chính sách trong lĩnh vực tài chính, y tế, marketing: Hiểu rõ các phương pháp khai phá dữ liệu giúp áp dụng hiệu quả trong phân tích thị trường, dự báo tài chính, phát hiện gian lận và quản lý rủi ro.

4. Phát triển phần mềm và công cụ khai phá dữ liệu: Luận văn cung cấp cơ sở lý thuyết và thực tiễn để phát triển hoặc cải tiến các công cụ khai phá dữ liệu, đặc biệt là tích hợp thuật toán FP-growth và khai phá luật kết hợp định lượng.

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

1. Khai phá mẫu phổ biến là gì và tại sao nó quan trọng?
   Khai phá mẫu phổ biến là quá trình tìm kiếm các tập mục xuất hiện thường xuyên trong dữ liệu. Nó quan trọng vì là bước nền tảng để sinh ra các luật kết hợp và phân tích mối tương quan, hỗ trợ các nhiệm vụ khai phá dữ liệu khác như phân lớp và phân cụm.

2. Thuật toán Apriori có những hạn chế gì?
   Apriori sinh ra nhiều tập mục ứng viên, đặc biệt khi ngưỡng hỗ trợ thấp hoặc dữ liệu lớn, dẫn đến tốn kém thời gian và bộ nhớ do phải quét nhiều lần cơ sở dữ liệu. Điều này làm giảm hiệu quả khi xử lý dữ liệu phức tạp.

3. FP-growth khác gì so với Apriori?
   FP-growth không sinh tập mục ứng viên mà sử dụng cấu trúc cây FP-tree để nén dữ liệu và khai phá trực tiếp trên cây, giảm số lần quét dữ liệu và tăng tốc độ xử lý, đặc biệt hiệu quả với các mẫu dài và dữ liệu lớn.

4. Làm thế nào để khai phá luật kết hợp định lượng?
   Phương pháp phổ biến là phân vùng giá trị định lượng thành các khoảng, ánh xạ sang dạng nhị phân, sau đó áp dụng các thuật toán khai phá luật kết hợp nhị phân. Việc phân vùng cần được tối ưu để cân bằng giữa độ chính xác và hiệu quả tính toán.

5. Mức đầy đủ bộ phận (Partial Completeness Level) có vai trò gì?
   Mức đầy đủ bộ phận giúp kiểm soát lượng thông tin mất mát khi phân vùng thuộc tính định lượng, đảm bảo các luật sinh ra vẫn giữ được độ tin cậy và hỗ trợ cần thiết, từ đó nâng cao chất lượng kết quả khai phá.

Kết luận

• Khai phá mẫu phổ biến và luật kết hợp là nền tảng quan trọng trong khai phá dữ liệu, hỗ trợ nhiều ứng dụng thực tiễn.
• Thuật toán FP-growth vượt trội hơn Apriori về hiệu quả và tốc độ xử lý, đặc biệt với dữ liệu lớn và mẫu dài.
• Khai phá luật kết hợp định lượng mở rộng khả năng phân tích dữ liệu đa dạng, nhưng đòi hỏi kỹ thuật phân vùng giá trị định lượng hợp lý.
• Mức đầy đủ bộ phận là công cụ quan trọng để cân bằng giữa độ chính xác và hiệu quả khai phá luật kết hợp định lượng.
• Các giải pháp và phương pháp nghiên cứu trong luận văn có thể áp dụng trong nhiều lĩnh vực, góp phần nâng cao chất lượng phân tích dữ liệu và ra quyết định.

Next steps: Triển khai áp dụng thuật toán FP-growth và kỹ thuật phân vùng tối ưu trên các tập dữ liệu thực tế, đồng thời phát triển công cụ hỗ trợ tự động hóa quá trình khai phá luật kết hợp định lượng.

Call-to-action: Các nhà nghiên cứu và chuyên gia phân tích dữ liệu nên tiếp cận và áp dụng các phương pháp này để nâng cao hiệu quả khai phá dữ liệu trong tổ chức của mình.

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

Chương 1: Tổng quan về khai phá mẫu phổ biến, luật kết hợp và các thước đo tương quan. Chương 2: Một số phương pháp cơ bản và mở rộng trong khai phá luật kết hợp. Chương 3: Giới thiệu công cụ khai phá dữ liệu Weka và mô phỏng. Hà Nội, ngày 10 tháng 10 năm 2011 Học viên Vũ Mỹ Hạnh LUAN VAN CHAT LUONG download : add [e-mail] 9 CHƢƠNG 1: TỔNG QUAN VỀ KHAI PHÁ MẪU PHỔ BIẾN, LUẬT KẾT HỢP VÀ CÁC THƢỚC ĐO TƢƠNG QUAN 1.

Tổng quan về khai phá dữ liệu 1. Khai phá dữ liệu Phát hiện tri thức trong cơ sở dữ liệu (còn được gọi là khai phá dữ liệu) là một quá trình không tầm thường, nhận ra những mẫu có giá trị, mới, hữu ích, tiềm năng và hiểu được trong dữ liệu.Tiến trình khai phá tri thức Nhiều người cho rằng khai phá dữ liệu (data mining) đồng nghĩa với khám phá tri thức từ dữ liệu – Knowledge Discovery form Data hoặc KDD. Một cách nhìn khác cho rằng khai phá dữ liệu đơn giản chỉ là một bước cốt yếu trong tiến trình khám phá tri thức[2]. Khai phá tri thức là một tiến trình bao gồm một dãy các bước: Hình 1.1: Khai phá dữ liệu là một bƣớc trong tiến trình khai phá tri thức 1.Chọn lựa dữ liệu (Trích chọn dữ liệu) – Data selection: 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 như CSDL - databases, kho dữ liệu - data warehouses, theo một số tiêu chí nhất định.

LUAN VAN CHAT LUONG download : add [e-mail]ền xử lý dữ liệu – Data preprocessing: là bước làm sạch dữ liệu (xử lý với dữ liệu không đầy đủ, dữ liệu nhiễu, dữ liệu không đồng nhất, v.), rút gọn dữ liệu (sử dụng hàm nhóm và tính tổng, các phương pháp nén dữ liệu, sử dụng histograms, lấy mẫu,v.), rời rạc hóa dữ liệu (rời rạc hóa dựa vào histograms, dựa vào entropy, dựa vào phân khoảng,v. Kết thúc bước này, dữ liệu sẽ nhất quán, đầy đủ, được rút gọn và được rời rạc hóa.Đổi dạng dữ liệu – data transformation: là bước chuẩn hóa và làm mịn dữ liệu để đưa dữ liệu về dạng thuận lợi nhất nhằm phục vụ cho các kỹ thuật khai phá ở bước sau.Khai phá dữ liệu – data mining: là bước áp dụng những kỹ thuật khai phá ( phần nhiều là các kỹ thuật của học máy – machine learning) để khai phá, trích chọn được những mẫu – patterns thông tin, những mối liên hệ - relationships đặc biệt trong dữ liệu. Đây được xem là bước quan trọng và tốn nhiều thời gian nhất của toàn quá trình khai phá tri thức – KDD.Trình diễn (Biểu diễn và đánh giá tri thức) – knowledge representation & evaluation: những mẫu thông tin và mối quan hệ trong dữ liệu đã được khai phá ở bước trên được chuyển dạng và biểu diễn ở một dạng gần gũi với người sử dụng, như đồ thị, cây, bảng biểu, luật,v. Đồng thời bước này cũng đánh giá những tri thức khám phá được theo những tiêu chí nhất định.

Các hướng tiếp cận trong khai phá dữ liệu Các hướng tiếp cận của KPDL có thể được phân chia theo chức năng hay lớp các bài toán khác nhau. Sau đây là một số hướng tiếp cận khá phổ biến: Phân lớp và dự đoán (classification and prediction): là phương pháp xếp một đối tượng vào một trong những lớp đã biết trước. Hướng tiếp cận này thường sử dụng một số kỹ thuật học máy như: cây quyết định – decision, mạng nơ-ron – neural network,. Phân lớp còn được gọi là học có giám sát – supervised learning.

Phân cụm (clustering/segmentation): Xếp các đối tượng theo từng cụm, số lượng cũng như tên các cụm chưa được biết trước. Phân cụm còn được gọi là học không giám sát – unsupervised learning. LUAN VAN CHAT LUONG download : add [e-mail] 11 Khai phá luật kết hợp (association rules): là cách biểu diễn tri thức dưới dạng các luật khá đơn giản nhưng mang rất nhiều ý nghĩa. Thông tin luật đem lại là rất đáng kể và hỗ trợ không nhỏ trong quá trình ra quyết định.

Tìm kiếm được những luật thực sự “mạnh” chứa đựng nhiều thông tin từ CSDL tác nghiệp là một trong những hướng tiếp cận chính của lĩnh vực KPDL, là một động lực không nhỏ thúc đẩy việc tập trung nghiên cứu của nhiều nhà khoa học. Khai phá chuỗi theo thời gian (sequential/temporal patterns): giống như khai phá luật kết hợp, nhưng có thêm tính thứ tự và tính thời gian. Hướng tiếp cận này được ứng dụng nhiều trong lĩnh vực tài chính và thị trường chứng khoán vì nó có tính dự báo cao. Mô tả khái niệm (concept description & summarization): thiên về mô tả, tổng hợp và tóm tắt khái niệm.

Ví dụ như: tóm tắt văn bản,. Một số ứng dụng trong khai phá dữ liệu Khai phá dữ liệu là một lĩnh vực mới nhưng thu hút được rất nhiều sự quan tâm của các nhà nghiên cứu nhờ vào tính ứng dụng thực tiễn của nó. Một số ứng dụng điển hình được kể đến bao gồm: Phân tích dữ liệu và hỗ trợ quyết định (data analysis and dicision support): oPhân tích và quản lý thị trường: Tiếp thị định hướng, quản lý quan hệ khách hàng, phân tích thói quen mua sắm, tiếp thị chéo, phân đoạn thị trường. oPhân tích và quản lý rủi ro: dự báo, duy trì khách hàng, cải thiện bảo lãnh, kiểm soát chất lượng, phân tích cạnh tranh.

oPhát hiện gian lận, phát hiện mẫu bất thường (ngoại lai). Ứng dụng khác: oKhai phá văn bản (text mining), khai phá web (web mining). oKhai phá dữ liệu dòng. oTin sinh (bio-informatics): tìm kiếm, đối sánh giữa các hệ gen và thông tin di truyền, mối liên hệ giữa một số hệ gen và bệnh di truyền, phân tích AND và dữ liệu sinh học.

LUAN VAN CHAT LUONG download : add [e-mail] 12 oĐiều trị y học ( medical treament), như tìm hiểu mối quan hệ giữa triệu chứng, chuẩn đoán và phương pháp điều trị, giữa chế độ dinh dưỡng với bệnh lý và thuốc,. oTài chính và thị trường chứng khoán ( finance and stock market): phân tích và dự báo tình tình tài chính cũng như quy luật hoạt động của cổ phiếu trên trị thường chứng khoán,. Một số thách thức trong khai phá dữ liệu Hiện nay, khai phá dữ liệu được ứng dụng trong nhiều lĩnh vực khá điển hình như: trong Phân tích dữ liệu hỗ trợ ra quyết đinh, trong y học, bảo hiểm, giáo dục, trong lĩnh vực tài chính và phân tích thị trường, và một số lính vực khác như Tin sinh học, và khai phá dữ liệu web,. Có khá nhiều những giải pháp cũng như các phương pháp được sử dụng trong khai phá dữ liệu, tuy nhiên vẫn tồn tại không ít khó khăn và thách thức: Cơ sở dữ liệu lớn (về số lượng các bản ghi cũng như về số chiều thuộc tính) trong cơ sở dữ liệu ( CSDL).

Dung lượng của các bản ghi trong CSDL đôi khi lên tới hàng GigaByte(GB), TeraByte(TB). Số chiều thuộc tính trong CSDL có thể rất lớn và đa dạng. Để giải quyết vấn đề này, người ta đưa ra một ngưỡng nào đó cho CSDL bằng các cách như: chiết xuất mẫu, xấp xỉ hoặc xử lý song song. Trong CSDL khi số chiều thuộc tính là rất lớn, cùng với số lượng lớn các bản ghi sẽ dẫn đến kích thước và độ phức tạp của bài toán tăng lên.Vì vậy, không gian tìm kiếm và không gian trạng thái gia tăng, nhiều mẫu dư thừa và trùng lặp, phát sinh nhiều luật thừa.

Đây được coi là vấn đề nan giải trong quá trình khai phá dữ liệu. Nhằm giải quyết những vấn đề trên, phải sử dụng một số tri thức đã biết để loại bỏ và trích lọc ra những dữ liệu thích hợp với yêu cầu bài toán. Dữ liệu bị thay đổi phụ thuộc theo thời gian: có nghĩa là dữ liệu bị ảnh hưởng và phụ thuộc vào thời điểm quan sát, thời điểm lấy mẫu, thời điểm khai phá. Kết quả đạt được sau khai phá cũng gây không ít khó khăn cho khai phá dữ liệu, ví dụ như các mẫu khai phá ở giai đoạn trước có thẻ không còn giá trị hay vô nghĩa tại thời điểm sử dụng, hoặc có thể bị làm nhiễu hay phát sinh LUAN VAN CHAT LUONG download : add [e-mail] 13 hiệu ứng phụ làm sai lệch kết quả.

Để khắc phục được vấn đề này cần thiết phải chuẩn hóa, cải tiến và nâng cấp mẫu, nâng cấp các mô hình và có thể xem các thay đổi này là mục đích của khai phá và tìm kiếm mẫu bị thay đổi. Thuộc tính không phù hợp, các bộ giá trị không đầy đủ, bị thiếu các giá trị trong các miền thuộc tính đã làm ảnh hưởng không nhỏ đến quá trình khai phá dữ liệu. Trong khai phá dữ liệu, khi các hệ thống tương tác với nhau phụ thuộc nhau mà thiếu vắng mội vài giá trị nào đó, sẽ dẫn đến các mẫu không còn chính xác, bị thiếu và không đầy đủ. Để giải quyết vấn đề này, người ta coi sự thiếu vắng của các dữ liệu này như là các giá trị ẩn, chưa biết và có thể được tiên đoán bằng một số phương pháp nào đó.

Quan hệ phức tạp giữa các thuộc tính trong CSDL cũng là vấn đề cần được quan tâm. Những bộ thuộc tính có cấu trúc, phân lớp phức tạp, có mối liên hệ phức tạp với nhau trong CSDL đòi hỏi tiến trình khai phá dữ liệu phải có các giải pháp, các kỹ thuật để có thể áp dụng được, nhận ra được các mối quan hệ này. Lựa chọn giải pháp khai phá dữ liệu tự động: Hiện này người ta chưa đưa ra được một tiêu chuẩn để đánh giá cho việc lựa chọn phương pháp nào là phù hợp và hiệu quả cho từng trường hợp cụ thể. Các kỹ thuật đều khá mới mẻ trong các lĩnh vực ứng dụng, hơn nữa lại có rất nhiều kỹ thuật được sử dụng cho nhiều bài toán khác nhau.

Vì vậy, ngay sau câu hỏi khai phá dữ liệu là gì? Câu hỏi kế tiếp ngay sau đó sẽ là: Nên sử dụng kỹ thuật nào là phù hợp và hiệu quả? Câu trả lời thật sự không đơn giản! 1. Các khái niệm cơ bản về khai phá mẫu phổ biến tìm luật kết hợp và phân tích mối tương quan 1. Khái niệm về khai phá mẫu phổ biến 1. Mẫu phổ biến Frequent patterns – mẫu phổ biến được biết đến như: các tập mục – itemsets, dãy con – subsequence, hoặc cấu trúc con – substructures, là những mẫu xuất hiện phổ biến trong một tập dữ liệu.

LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Ý nghĩa của khai phá mẫu phổ biến Tìm kiếm các mẫu phổ biến đóng vai trò thiết yếu trong khai phá luật kết hợp, tìm kiếm mối tương quan, và các mối quan hệ thú vị trong dữ liệu.