• Không có kết quả nào được tìm thấy

7 1.4 Các phƣơng pháp khai phá dữ liệu

Protected

Academic year: 2022

Chia sẻ "7 1.4 Các phƣơng pháp khai phá dữ liệu"

Copied!
51
0
0

Loading.... (view fulltext now)

Văn bản

Lượng dữ liệu khổng lồ được tập trung và lưu trữ trong cơ sở dữ liệu trên các thiết bị điện tử như ổ cứng, băng từ, đĩa quang… Trong lượng dữ liệu khổng lồ này có rất nhiều thông tin tổng hợp hữu ích, những thông tin thông thường còn ẩn giấu mà chúng ta không biết. Cần có các công cụ để tự động trích xuất thông tin và kiến ​​thức hữu ích từ lượng dữ liệu rất lớn.

Một cách tiếp cận có khả năng giúp các công ty trích xuất thông tin có ý nghĩa từ các tập dữ liệu lớn là khai thác dữ liệu. Với sự bùng nổ và phát triển của công nghệ thông tin đã mang lại nhiều tác dụng cho cả hoạt động khoa học và thực tiễn, trong đó khai phá dữ liệu là một trong những lĩnh vực mang lại hiệu quả thiết thực cho các em. Mọi người. KPDL đã giúp người dùng trích xuất kiến ​​thức hữu ích từ cơ sở dữ liệu hoặc kho lưu trữ dữ liệu lớn khác.

Môn học đề cập đến các khái niệm và vấn đề cơ bản trong khai phá dữ liệu và khai phá dữ liệu, ngoài ra môn học còn đề cập đến một số phương pháp khai phá dữ liệu đóng được ứng dụng nhiều trong thực tế.

TỔNG QUAN VỀ KPTT VÀ KPDL

  • Giới thiệu chung về khai phá tri thức và khai phá dữ liệu
  • Quá trình khai phá tri thức
  • Quá trình khai thác dữ liệu
  • Các phương pháp khai phá dữ liệu
  • Các lĩnh vực ứng dụng thực tiễn của khai phá dữ liệu
  • Các hướng tiếp cận trong khai phá dữ liệu
  • Phân loại các hệ khai phá dữ liệu
  • Các thách thức - khó khăn trong KPTT và KPDL

Mô tả dữ liệu là một bản tóm tắt hoặc mô tả các đặc điểm chung của các thuộc tính dữ liệu trong kho lưu trữ dữ liệu mà con người có thể hiểu được. Thu thập và tiền xử lý dữ liệu: Thu thập dữ liệu liên quan và xử lý trước để thuật toán KPDL có thể hiểu được. Data Mining Algorithm: Lựa chọn thuật toán KPDL và thực hiện PKDL để tìm các mẫu có ý nghĩa, các mẫu này được biểu diễn dưới dạng luật kết hợp, cây quyết định.

Có nhiều phương pháp khai phá dữ liệu đã được nghiên cứu ở trên, ba trong số đó được các nhà nghiên cứu sử dụng phổ biến nhất: luật kết hợp, phân loại dữ liệu và phân cụm dữ liệu. Phân loại dựa trên loại dữ liệu được khai thác: cơ sở dữ liệu quan hệ, kho dữ liệu, cơ sở dữ liệu giao dịch, cơ sở dữ liệu hướng đối tượng, cơ sở dữ liệu không gian, cơ sở dữ liệu đa phương tiện (multimedia database), cơ sở dữ liệu Text và WWW, v.v. Cơ sở dữ liệu lớn thì tập dữ liệu cần xử lý là vô cùng lớn. Trên thực tế, kích thước của bộ dữ liệu thường ở mức terabyte (hàng nghìn gigabyte).

Việc thay đổi dữ liệu và kiến ​​thức có thể có nghĩa là các mẫu được phát hiện không còn phù hợp nữa.

PHƯƠNG PHÁP KHAI PHÁ TẬP PHỔ BIẾN

Giới thiệu

Giới thiệu một số thuật toán khai phá tập phổ biến

  • Thuật toán Apriori
  • Thuật toán Freespan

Ưu tiên thuộc tính[2]: Cắt bớt không gian tìm kiếm để tránh trường hợp mỗi lk phải quét hết dữ liệu một lần. Thuật toán Apriori vẫn có một số vấn đề khi tập dữ liệu lớn hoặc chuỗi mẫu khai thác dài hoặc lớn. Thuật toán Freespan sử dụng các phần tử thường xuyên để đệ quy chuỗi dữ liệu thành các chuỗi dữ liệu nhỏ hơn.

Khai thác tập hợp thông thường sử dụng phạm vi dữ liệu để giới hạn việc tìm kiếm và phân phối các chuỗi con. Bằng cách lặp lại chuỗi dữ liệu thành chuỗi dữ liệu nhỏ hơn dựa trên các bộ mẫu chung. Quét dữ liệu, tìm các hạng mục thường xuyên từ tập dữ liệu danh sách hạng mục thường xuyên với độ hỗ trợ giảm dần gọi là f_list (danh sách hạng mục thường xuyên).

Nếu có sự lựa chọn giữa một dãy và một tập hợp, dãy sẽ được ưu tiên (Hình 2.5). 5) Quét dữ liệu để tạo bộ lặp mục và mục nhập cơ sở dữ liệu dự án (Hình 2.6).

Tóm tắt

TÌM HIỂU PHƯƠNG PHÁP KHAI PHÁ TẬP PHỔ BIẾN ĐÓNG

Phương pháp khai phá tập phổ biến đóng trong không gian 2 chiều

  • Tổng quan
  • Sự chuẩn bị
  • Tiến bộ của phương pháp khai phá tập phổ biến đóng
  • Khung cải tiến cho khai phá tập phổ biến đóng
  • Thuật toán C-Miner
  • Thuật toán B-Miner
  • Khai phá tập phổ biến đóng song song
  • Độ phức tạp thời gian

Thuộc tính này cho phép chúng ta khai thác các không gian con khác nhau một cách độc lập và đồng thời. Trong giai đoạn 2, Giai đoạn khai thác không gian con, mọi không gian con đều được khai thác và chúng tôi nhận được các FCP độc lập. Tuy nhiên, FCP được trích xuất từ ​​không gian con có thể không phải là câu trả lời.

Ta gọi các không gian con O' là các không gian rút gọn. Khai thác không gian con để tạo tập phổ biến đóng. Để tạo FCP thực sự, mỗi không gian con phải được khai thác độc lập.

Đặt S1,…,St là các không gian con được tạo trong giai đoạn 1 của C-Miner. Đặt P1,…,Pt là tập hợp các FCPS bị loại bỏ khỏi các không gian con tương ứng trong giai đoạn 2. FCPS không được tạo ra trong các không gian con có ít luật hơn minsup.

Tập hợp cột với đủ hỗ trợ hàng đầu tiên được bao phủ bởi các không gian con. Giống như C-Miner, bất kỳ thuật toán khai thác FCP nào cũng có thể được áp dụng cho các không gian con. Ở đây chúng tôi tiếp tục sử dụng D-Miner để khai thác FCP từ các không gian con.

Đặt S1,...,St là các không gian con được tạo trong giai đoạn 1 của B-Miner. Chúng tôi lưu ý rằng mỗi không gian con Si có thể được khai thác độc lập mà không có bất kỳ kết quả nào từ các không gian con khác. Do đó, tất cả các nút có thể hoạt động song song khi khai thác các không gian con được phân bổ.

Cho P1,…,Pt là tập FCPS bị cắt bớt bởi các không gian con tương ứng trong giai đoạn 2.

Phương pháp khai phá tập phổ biến đóng trong không gian 3 chiều

  • Tổng quan
  • Sự chuẩn bị
  • Thuật toán khai phá lát đại diện(RSM)
  • Thuật toán CubeMiner
  • Khai phá FCC song song
  • Độ phức tạp thời gian

Để đảm bảo điều này, chúng ta cần chuyển dữ liệu ban đầu O cho tất cả các nút tham gia. Ngoài ra, bộ dữ liệu thực của chúng tôi không lớn. Trong chương này, chúng tôi giải quyết vấn đề khai thác FCC từ bộ dữ liệu 3D.

Thứ ba, chúng tôi cũng chỉ ra cách CubeMiner và RSM có thể dễ dàng mở rộng để khai thác song song. Định nghĩa vấn đề: Với tập dữ liệu ba chiều O, vấn đề của chúng ta là khai thác tất cả các khối thông thường đã đóng theo các ngưỡng hỗ trợ do người dùng xác định là min, minr và minc. Trong phần này, chúng tôi đề xuất một khuôn khổ, được gọi là Khai thác lát cắt đại diện (RSM)[1], để khai thác FCC.

Trong Khung này, bất kỳ thuật toán khai thác FCP 2D nào cũng có thể được áp dụng để hoạt động trên bộ dữ liệu 3D. Dựa trên ý tưởng này, chúng tôi chia khung RSM thành ba giai đoạn, như thể hiện trong Thuật toán 1. Để loại bỏ tất cả các mô hình đóng 3D thông thường bị lộ, chúng tôi phát triển một chiến lược hậu cắt tỉa dựa trên Bổ sung, chủ đề 7.

Trong phần này, chúng tôi trình bày một phương pháp mới khai thác FCC trực tiếp từ bộ dữ liệu 3D. Từ đó, chúng ta cần xác định khối tối đa với tất cả các ô của nó có giá trị "1". Chúng tôi cố gắng loại bỏ càng nhiều giá trị "0" càng tốt trong mỗi tiểu mục.

Ta nối các ô có giá trị “0” sao cho Z có số đoạn bằng số dòng trong tất cả các đoạn chiều cao của mảng dữ liệu 3D. Phải có một chiến lược cắt giảm để đảm bảo rằng chúng tôi nhận được tất cả các FCC và chỉ các FCC. Trong phần này, chúng tôi chỉ ra cách dễ dàng khai thác song song RSM và CubeMiner.

Nói cách khác, chúng ta có thể gán cho bộ xử lý một nhánh của quá trình tách cây.

Tóm tắt

CÀI ĐẶT THUẬT TOÁN THỬ NGHIỆM

  • Giới thiệu về chương trình
  • Giao diện chương trình
  • Các thành phần và chức năng trong chương trình
  • Kết quả thực nghiệm

Các nút thêm giao dịch, sửa giao dịch, xóa, xóa tất cả có chức năng thêm, sửa, xóa và xóa các hàng trong tập dữ liệu. 3 ListView ở bên phải đại diện cho ma trận dữ liệu, bộ cắt và bộ FCP được khai thác. Sau khi chạy một số ví dụ trên các bộ dữ liệu khác nhau với các ngưỡng min_sup và min_len khác nhau.

Chúng tôi thấy rằng thuật toán C-Miner khai thác chính xác tất cả các FCP và tất cả đều là FCP. Với bộ dữ liệu lớn, hiệu quả của C-Miner được cải thiện rất nhiều. Hiện nay con người đang chìm trong tri thức nhưng lại rất thiếu thông tin, với lượng dữ liệu lớn và phức tạp như hiện nay thì nhu cầu khai thác tri thức trở nên rất thiết yếu đối với con người.

Dự án đã giới thiệu tổng quan về kinh tế số và phân tích không gian, các cách tiếp cận chính trong kinh tế số, các lĩnh vực ứng dụng của công nghệ thông tin trong thực tiễn. Ngoài ra, đồ án còn đề cập đến một số phương pháp khai phá dữ liệu đóng được ứng dụng ngày nay trong nhiều lĩnh vực thực tế (phân tích thị trường, phân tích sinh học,...). Cụ thể, các thuật toán C-Miner và B-Miner trong khai thác tập dữ liệu 2-D và RSM và CubeMiner trong khai thác tập dữ liệu 3-D.

Lag: Do thời gian tìm hiểu không nhiều nên mình chỉ xây dựng chương trình khai thác dữ liệu dựa trên thuật toán C-Miner với đầu vào là tập dữ liệu văn bản. Xây dựng chương trình thử nghiệm thuật toán B-Miner, RSM, CubeMiner trên dữ liệu là cơ sở dữ liệu thực.

Tài liệu tham khảo

Tài liệu liên quan