- Sử dụng phương pháp xây dựng đặc trưng dựa trên di truyền để tóm tắt dữ liệu. - Giới thiệu về cơ sở dữ liệu quan hệ, quá trình tóm tắt dữ liệu trong cơ sở dữ liệu quan hệ và trình bày chi tiết các giai đoạn thực hiện của thuật toán DARA để tóm tắt dữ liệu. - Tìm hiểu một số vấn đề về chuyển đổi đặc trưng liên quan đến xây dựng đặc trưng và giới thiệu một phương pháp xây dựng đặc trưng dựa trên GA để tóm tắt dữ liệu. - Phân tích kết quả thực nghiệm về phương pháp xây dựng đặc trưng dựa trên giải thuật di truyền.. - Cơ sở dữ liệu quan hệ. - Dữ liệu. - CHƢƠNG 1: TÓM TẮT DỮ LIỆU QUAN HỆ VỚI THUẬT TOÁN DARA. - 1.1 Cơ sở dữ liệu quan hệ 1.1.1 Giới thiệu. - Một cơ sở dữ liệu là một tập hợp dữ liệu có liên quan với nhau được tổ chức và lưu trữ theo một cấu trúc chặt chẽ.. - Một mô hình cơ sở dữ liệu là một tập hợp các khái niệm dùng để biểu diễn cấu trúc của cơ sở dữ liệu. - Cơ sở dữ liệu được tổ chức theo mô hình quan hệ được gọi là cơ sở dữ liệu quan hệ.. - 1.1.2 Tổ chức dữ liệu. - Dữ liệu lưu trữ trong cơ sở dữ liệu quan hệ được tổ chức thành các bảng có mối quan hệ với nhau. - Một cơ sở dữ liệu quan hệ bao gồm một tập hợp các bảng T1. - Hình 1.1: Một tập dữ liệu với hai mức của liên kết 1:n. - 1.2 Tóm tắt dữ liệu trong cơ sở dữ liệu quan hệ. - Thuật ngữ tóm tắt dữ liệu thường được dùng để nói đến tóm tắt dữ liệu được lưu trữ trong cơ sở dữ liệu quan hệ với các mối quan hệ một-nhiều [8].. - Định nghĩa 1.6 Một quá trình tóm tắt dữ liệu cho tất cả các bản ghi R NT trong bảng tham chiếu NT được định nghĩa là một quá trình nối thêm vào bảng đích T ít nhất một trường dữ liệu đặc trưng cho các giá trị của các bản ghi R NT được liên kết với mỗi bản ghi RT trong bảng T.. - Hình 1.2 minh họa trình tự tóm tắt dữ liệu cho một bảng đích T có mối quan hệ ràng buộc một-nhiều với các bảng tham chiếu (NT1, NT2, NT3, NT4, NT41).. - Hình 1.2 Tóm tắt dữ liệu trong nhiều bảng với các mối quan hệ 1:n. - Một quá trình tóm tắt dữ liệu gồm 3 giai đoạn chính (xem hình 1.3).. - Hình 1.3: Ba giai đoạn chính trong quá trình tóm tắt dữ liệu quan hệ 1.3.1 Giới thiệu. - Thuật toán DARA (Dynamic Aggregation of Relational Attributes: tổng hợp động các thuộc tính quan hệ) [4] được thiết kế cho mục đích tóm tắt dữ liệu trong cơ sở dữ liệu quan hệ. - Quá trình tóm tắt dữ liệu sử dụng thuật toán DARA được minh hoạ trong hình 1.4.. - Hình 1.4: Quá trình tóm tắt dữ liệu sử dụng thuật toán DARA 1.3.2 Tiền xử lí dữ liệu. - Trong giai đoạn này, thuật toán DARA thực hiện qúa trình rời rạc hóa dữ liệu và quá trình xây dựng đặc trưng. - Quá trình rời rạc hóa dữ liệu làm giảm số lượng các giá trị của đặc trưng liên tục bằng các chia miền giá trị đặc trưng thành các khoảng, nhãn được gán tương ứng cho mỗi khoảng và được dùng thay cho giá trị thực của đặc trưng. - Quá trình xây dựng đặc trưng tạo ra các đặc trưng mới từ một tập các đặc trưng, sao cho tập đặc trưng mới mô tả các giả thuyết ít nhất cũng tốt như tập ban đầu.. - 1.3.3 Chuyển đổi dữ liệu. - Trong một cơ sở dữ liệu quan hệ, một bản ghi đơn Ri trong bảng đích có thể được liên kết với nhiều bản ghi khác nhau được lưu trong bảng tham chiếu như minh họa ở hình 1.5.. - Quá trình chuyển đổi dữ liệu của bảng tham chiếu được mô tả trong hình 1.6 [2].. - Hình 1.6: Chuyển đổi dữ liệu trong bảng tham chiếu với một thuộc tính. - Trong trường hợp này, thuật toán có thể xây dựng các đặc trưng mới từ các thuộc tính ban đầu. - Quá trình chuyển đổi dữ liệu trong bảng tham chiếu với nhiều thuộc tính được minh họa trong hình 1.7. - Có thể lấy ví dụ về một thuật toán đơn giản để xây dựng đặc trưng: đặt dom(Fi)=(Fi, 1 ,Fi, 2 , Fi, 3. - Hình 1.7: Chuyển đổi dữ liệu bảng tham chiếu có nhiều thuộc tính 1.3.3.2 Biểu diễn dữ liệu trong mô hình không gian Vector. - Giả sử một cơ sở dữ liệu quan hệ DB có bảng đích gồm n bản ghi. - 1.3.4 Tóm tắt dữ liệu bằng cách phân cụm. - Một thuật toán phân cụm thực hiện trên dữ liệu đã chuyển đổi để phân cụm các đối tượng.. - 1.3.5 Mô tả đặc điểm cụm và mô hình hoá dữ liệu. - Sau khi tóm tắt dữ liệu được lưu trữ trong các bảng tham chiếu, công việc khai phá dữ liệu thực sự chuyển sang giai đoạn mô hình hoá, dựa trên các mục tiêu xác định và sự đánh giá dữ liệu đã có, một thuật toán thích hợp được lựa chọn và thực hiện trên dữ liệu đã được xử lý.. - CHƢƠNG III - PHƢƠNG PHÁP XÂY DỰNG ĐẶC TRƢNG DỰA TRÊN GIẢI THUẬT DI TRUYỀN ĐỂ TÓM TẮT DỮ LIỆU. - Trong một cơ sở dữ liệu quan hệ mà các bảng có mối quan hệ một-nhiều, mỗi bản ghi trong bảng đích được liên kết với một hoặc nhiều bản ghi trong một bảng tham chiếu. - Thuật toán DARA tóm tắt dữ liệu bằng cách chuyển đổi dữ liệu trong bảng tham chiếu vào một mô hình không gian vector và thực hiện phân cụm. - Việc phân cụm được coi là một trong những nhiệm vụ mô tả nhằm xác định các nhóm tự nhiên trong dữ liệu dựa trên các mẫu. - Phương pháp xây dựng đặc trưng có thể được áp dụng để cải thiện độ chính xác mô tả của thuật toán.. - Với dữ liệu tóm tắt thu được từ các bảng tham chiếu, thuật toán DARA tạo điều kiện thuận lợi cho nhiệm vụ phân loại thực hiện trên dữ liệu được lưu trữ trong bảng đích.. - Sử dụng thuật toán dựa trên GA là một lựa chọn phù hợp để xây dựng đặc trưng cho mục đích tóm tắt dữ liệu.. - Trong chương này, luận văn trình bày một số vấn đề về chuyển đổi đặc trưng liên quan đến xây dựng đặc trưng và giới thiệu một phương pháp xây dựng đặc trưng dựa trên GA để tóm tắt dữ liệu.. - Có một số lợi ích của việc áp dụng chuyển đổi đặc trưng để tạo ra các đặc trưng mới trong thuật toán DARA, đó là:. - (1) Cải thiện độ chính xác mô tả của tóm tắt dữ liệu bởi tạo ra các mẫu có liên quan mô tả mỗi đối tượng được lưu trữ trong bảng tham chiếu.. - (2) Tạo điều kiện cho nhiệm vụ lập mô hình dự báo cho các dữ liệu được lưu trữ trong bảng đích, khi dữ liệu tóm tắt được nối thêm vào bảng đích. - (3) Tối ưu hóa không gian đặc trưng để mô tả các đối tượng được lưu trữ trong bảng tham chiếu.. - Sự biểu diễn dữ liệu vào của mọi thuật toán học đều có thể được chuyển đổi để cải thiện độ chính xác cho một nhiệm vụ cụ thể. - Chuyển đổi đặc trưng có thể được định nghĩa như sau:. - Trọng số phản ánh tầm quan trọng tương đối của một đặc trưng và có thể được sử dụng trong quá trình học quy nạp.. - Nghiên cứu này áp dụng phương pháp xây dựng đặc trưng để cải thiện độ chính xác mô tả của thuật toán DARA.. - Xây dựng đặc trưng là quá trình xây dựng các đặc trưng mới bằng cách áp dụng một số phép toán hay hàm số với các đặc trưng ban đầu. - Mục đích của xây dựng đặc trưng là tạo ra tập các đặc trưng mới làm cho nhiệm vụ học trở nên dễ dàng hơn với một thuật toán khai phá dữ liệu [10]. - Điều này đạt được bằng cách xây dựng đặc trưng mới từ tập các đặc trưng đã cho để trừu tượng tương tác giữa một số thuộc tính vào một thuộc tính mới... - Dựa vào chiến lược xây dựng, phương pháp xây dựng đặc trưng có thể được chia thành hai nhóm: phương pháp hướng giả thuyết và phương pháp hướng dữ liệu [17].. - Có hai cách tiếp cận khác nhau để xây dựng đặc trưng trong mối liên hệ với khai phá dữ liệu: Phương pháp lọc (the Filter approach) và phương pháp tiếp cận bao gói (the Wrapper approach). - Trong phương pháp tiếp cận bao gói, các đặc trưng mới được xây dựng trong quá trình quy nạp.. - Trong nghiên cứu này, phương pháp lọc sử dụng chiến lược hướng dữ liệu được áp dụng để xây dựng đặc trưng cho nhiệm vụ mô tả.. - Các đặc trưng cũng có thể được biểu diễn ở dạng thức phi đại số, trong đó sự biểu diễn không sử dụng các phép toán. - mà chữ số đề cập đến số lượng thuộc tính được kết hợp để tạo ra đặc trưng đầu tiên.. - Biểu diễn phi đại số các đặc trưng có một vài lợi thế so với biểu diễn đại số [19]. - IG của một đặc trưng mới F, ký hiệu là InfoGain(F), đại diện cho entropy cuả lớp trong tập dữ liệu trước khi sử dụng đặc trưng F, ký hiệu là Ent(C), và sau khi sử dụng đặc trưng F để tách tập dữ liệu thành các tập hợp con, ký hiệu là Ent(C|F):. - Xây dựng đặc trƣng để tóm tắt dữ liệu. - Hình 3.3: Đối tượng O j được biểu diễn bởi một túi các mẫu như một tập các đặc trưng riêng biệt. - Hình 3.4: Đối tượng O j được biểu diễn bởi một túi các mẫu như một đặc trưng duy nhất được xây dựng bằng cách kết hợp tất cả các thuộc tính. - Hình 3.5: Đối tượng O j được biểu diễn bởi một túi các mẫu như một tập các đặc trưng đã được kết hợp từ tập các thuộc tính ban đầu. - Nghiên cứu này áp dụng một phương pháp tiếp cận lọc để xây dựng đặc trưng để tóm tắt dữ liệu với thuật toán Dara (xem Hình 3.6).. - Hình 3.6: Quá trình xây dựng đặc trưng dựa trên phương pháp lọc. - 3.3.2 Phƣơng pháp xây dựng đặc trƣng dựa trên di truyền để tóm tắt dữ liệu quan hệ 3.3.2.1 Hàm thích nghi. - Thử nghiệm trong nghiên cứu này đánh giá tính hiệu quả của phương pháp xây dựng đặc trưng dựa trên chất lượng của cấu trúc cụm với hàm thích nghi dựa trên chỉ số DBI. - Với mỗi nhiễm sắc thể, dựa vào thành phần X và A ta có một tập các đặc trưng được xây dựng từ tập thuộc tính ban đầu. - biểu diễn điểm sắp xếp lại trình tự của dãy các chỉ số thuộc tính, tập các đặc trưng được xây dựng là {F1F2F3, F7F5F6, F4}.. - Khả năng hỗ trợ cải thiện hiệu quả tóm tắt dữ liệu với thuật toán DARA bằng phương pháp xây dựng đặc trưng dựa trên di truyền.. - 4.2 Chƣơng trình và dữ liệu thử nghiệm 4.2.1 Chƣơng trình. - Chương trình cài đặt thuật toán xây dựng đặc trưng dựa trên giải thuật di truyền để tóm tắt dữ liệu với thuật toán DARA (P GA ) được viết bằng ngôn ngữ Java trong môi trường NetBean IDE. - Thuật toán phân cụm được sử dụng để tóm tắt dữ liệu là k-mean. - Module 1: Đọc dữ liệu đầu vào và chuyển đổi dữ liệu thành mảng vector. - Module 3: Phân cụm một tập dữ liệu và đánh giá cụm. - Hình 4.2: Giao diện NetBean IDE tạo chương trình 4.2.2 Dữ liệu thử nghiệm. - Dữ liệu thử nghiệm là một cơ sở dữ liệu quan hệ về Thuê bao di động phát sinh của thành phố Hà Nội. - Cơ sở dữ liệu gồm 3 bảng được mô tả như hình 4.3.. - Hình 4.3: Mô hình quan hệ của dữ liệu thử nghiệm. - Trong thử nghiệm này, bảng Huyen (có 28 bản ghi) là bảng đích và bảng Thue_bao_phat_sinh (có 203 bản ghi) là bảng tham chiếu cần được tóm tắt dữ liệu. - Tập đặc trưng được. - xây dựng. - Dữ liệu thu được cho thấy, trong nhiều trường hợp khác nhau của số lượng cụm, giá trị hàm mục tiêu đạt được khi sử dụng P GA cao hơn so với P single. - Như vậy, phương pháp xây dựng đặc trưng dựa trên di truyền làm tăng hiệu qủa tóm tắt dữ liệu với thuật toán DARA.. - Luận văn giới thiệu một phương pháp tóm tắt dữ liệu quan hệ với thuật toán DARA.. - Phương pháp này được áp dụng cho các cơ sở dữ liệu có các mối quan hệ một-nhiều. - Dữ liệu trong các bảng tham chiếu được tóm tắt bằng cách phân cụm và một vài trường đặc trưng cho dữ liệu đã tóm tắt được nối thêm vào bảng đích. - Do không yêu cầu phải nối các bảng lại với nhau, phương pháp này khắc phục được khó khăn về khối lượng và sự phức tạp của lược đồ cơ sở dữ liệu quan hệ khi tóm tắt dữ liệu trong cách tiếp cận truyền thống.. - Luận văn đã làm rõ phương pháp xây dựng đặc trưng dựa trên giải thuật di truyền.. - Các kết quả thực nghiệm cho thấy phương pháp này cải thiện đáng kể chất lượng phân cụm, từ đó, nâng cao hiệu qủa tóm tắt dữ liệu.. - Trong thời gian tới, tôi sẽ thử nghiệm cài đặt thuật toán xây dựng đặc trưng dựa trên giải thuật di truyền với các hàm thích nghi khác như IG, CE, kết hợp của IG và CE