MỞ ĐẦU Trong nhiều năm qua, cùng với sự phát triển của công nghệ thông tin và ứng dụng của công nghệ thông tin trong nhiều lĩnh vực của đời sống xã hội, lƣợng dữ liệu đƣợc các cơ quan thu thập và lƣu trữ ngày một nhiều lên. Dữ liệu đƣợc tổ chức thành các cơ sở dữ liệu để đảm bảo đƣợc tính nhất quán, dễ quản lí và đáp ứng nhu cầu khai thác đồng thời của nhiều ngƣời. Với sự gia tăng bùng nổ của dữ liệu hiện nay, các cơ sở dữ liệu thực tế chứa đựng rất nhiều thông tin tiềm ẩn, phong phú và đa dạng, đòi hỏi phải có những phƣơng pháp nhanh, phù hợp, chính xác, hiệu quả để lấy đƣợc những thông tin bổ ích. Công nghệ phát hiện tri thức và khai phá dữ liệu đã ra đời đáp ứng nhu cầu đó và đang đƣợc nghiên cứu, ứng dụng ngày càng rộng rãi.
Khai phá cơ sở dữ liệu quan hệ là một trong những lĩnh vực đang đƣợc quan tâm nghiên cứu của khai phá dữ liệu. Trong một cơ sở dữ liệu quan hệ, dữ liệu đƣợc lƣu trữ trong các bảng có mối quan hệ với nhau. Khi giải quyết bài toán phân loại trong khai phá dữ liệu quan hệ, các phƣơng pháp truyền thống thƣờng yêu cầu liên kết dữ liệu đƣợc lƣu trong nhiều bảng thành một bảng duy nhất. Trong nhiều trƣờng hợp, quá trình này là không hiệu quả vì bảng đã nối quá lớn cho việc xử lí và một số thông tin có thể bị mất khi phép nối thực hiện [2].
Mặt khác, việc áp dụng các phƣơng pháp tóm tắt dữ liệu trên nhiều bảng có quan hệ một-nhiều thƣờng bị hạn chế bởi sự phức tạp của lƣợc đồ cơ sở dữ liệu. Một phƣơng pháp tóm tắt dữ liệu sử dụng thuật toán DARA đã đƣợc đề xuất để giải quyết vấn đề này. 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 bảng tham chiếu. Thuật toán DARA 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.
Sau đó, dữ liệu tóm tắt từ bảng tham chiếu sẽ đƣợc cập nhật vào bảng đích. Khi thực hiện chuyển đổi dữ liệu, các bản ghi trong bảng tham chiếu đƣợc đƣa vào các túi mẫu tƣơng ứng với các bản ghi đích. Nghĩa là, mỗi bản ghi đích đƣợc biểu diễn nhƣ một túi các mẫu. Thông thƣờng, tập đặc trƣng đƣợc lấy để xây dựng các mẫu chính là tập các thuộc tính ban đầu trong bảng tham chiếu.
Tập đặc trƣng này cũng có thể đƣợc xây dựng dựa trên sự kết hợp các thuộc tính bằng một số thuật toán đơn giản. Tuy nhiên, các phƣơng pháp hiện có này chƣa thực sự hiệu quả. Do vậy, vấn đề xây dựng một tập đặc trƣng thích hợp cho thuật toán DARA đƣợc đặt ra nhƣ một bài toán tối ƣu cần giải. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 8 Trƣớc các vấn đề nêu trên, luận văn tập trung nghiên cứu một phƣơng pháp xây dựng đặc trƣng dựa trên di truyền để nâng cao hiệu quả tóm tắt dữ liệu với thuật toán DARA.
Nghiên cứu này dựa trên ý tƣởng nghiên cứu của Rayner Alfred [3]. Thử nghiệm cho thuật toán đƣợc thực hiện trên cơ sở dữ liệu về thuê bao di động phát sinh của thành phố Hà Nội. Ngoài phần kết luận và các phụ lục, phần còn lại của luận văn đƣợc chia thành 4 chƣơng chính: Chƣơng I 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. Chƣơng II trình bày về giải thuật di truyền cổ điển và những cải tiến về cách biểu diễn nhiễm sắc thể, phƣơng pháp chọn lọc và một số toán tử di truyền thƣờng dùng.
Chƣơng III 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. Chƣơng IV trình bày các 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. Chƣơng trình cài đặt thử nghiệm cho thuật toán đƣợc thực hiện bằng ngôn ngữ Java trên tập dữ liệu. Phần Kết luận trình bày tổng hợp các kết quả thực hiện luận văn và hƣớng nghiên cứu tiếp theo.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 9 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 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ác mô hình cơ sở dữ liệu có thể đƣợc phân loại dựa trên những khái niệm mà chúng sử dụng để mô tả cấu trúc cơ sở dữ liệu [19] Các mô hình dữ liệu bậc cao hay mô hình dữ liệu mức quan niệm cung cấp các khái niệm gắn liền với cách cảm nhận dữ liệu của nhiều ngƣời sử dụng Các mô hình dữ liệu thể hiện hay mô hình dữ liệu mức logic cung cấp những khái niệm mà ngƣời sử dụng có thể hiểu đƣợc và không khác nhiều với cách tổ chức dữ liệu bên trong máy tính Các mô hình dữ liệu bậc thấp hay các mô hình dữ liệu vật lí, cung cấp các khái niệm mô tả chi tiết về việc dữ liệu đƣợc lƣu trữ trong máy tính. Các mô hình dữ liệu thể hiện là các mô hình đƣợc sử dụng nhiều nhất.
Ba mô hình cơ bản thuộc loại này là mô hình mạng, mô hình phân cấp và mô hình quan hệ. Mô hình mạng cung cấp ba khái niệm cơ bản: mẫu tin hay bản ghi, loại mẫu tin và loại liên hệ. Trong mô hình này, dữ liệu đƣợc biểu diễn trong các bản ghi liên kết với nhau bằng các mối nối liên kết tạo thành một đồ thị có hƣớng. Mô hình phân cấp cũng sử dụng ba khái niệm cơ bản ở mô hình mạng nhƣng trong mô hình này, dữ liệu đƣợc biểu diễn dƣới dạng cây với các đỉnh của cây là các bản ghi.
Các bản ghi liên kết với nhau theo mối quan hệ cha-con, một bản ghi cha có thể có nhiều con nhƣng mỗi bản ghi con chỉ có một cha. Mô hình quan hệ cung cấp những khái niệm cơ bản là thuộc tính, miền, bộ và quan hệ. Trong mô hình này, dữ liệu đƣợc biểu diễn dƣới dạng bảng. Mô hình quan hệ là mô hình đƣợc sử dụng phổ biến nhất hiện nay.
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ệ.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, ., Tn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 10 và một tập các mối quan hệ R1,. Mỗi bảng Ti bao gồm các cột và các hàng, các cột đại diện cho một dãy các thuộc tính, attr(T)=A1,., Ak, và các hàng đại diện cho các bản ghi trong bảng.Aj biểu thị thuộc tính thứ j của bảng Ti, Aj attr(Ti).1 Miền của thuộc tính Ti.Aj ký hiệu là D(Ti.Aj) đƣợc định nghĩa là tập của tất cả các giá trị khác nhau đƣợc phép đƣợc gán cho thuộc tính Aj trong bảng Ti.2 Khóa chính của bảng Ti, ký hiệu là Ti.ID, có giá trị duy nhất cho mỗi hàng trong bảng.3 Khóa ngoại của bảng Tj tham chiếu tới bảng Ti, ký hiệu là Tj.TiID, nhận giá trị từ D(Ti. Tập các mối quan hệ R1, ., Rm mô tả mối liên kết giữa các bảng trong cơ sở dữ liệu quan hệ.
Một bảng Ti có thể có một trong ba kiểu liên kết với bảng Tj, căn cứ vào lực lƣợng trong liên kết giữa Ti và Tj, đó là: 1:1 (một-một), 1:n (một-nhiều) và m:n (nhiều-nhiều) Hình 1.1: Một tập dữ liệu với hai mức của liên kết 1:n Định nghĩa 1.4 Một bảng đích T là một bảng bao gồm các hàng của các đối tƣợng mà mỗi hàng đại diện cho một đối tƣợng duy nhất.5 Một bảng tham chiếu NT là một bảng bao gồm các hàng của các đối tƣợng mà một tập con những hàng này có thể đƣợc liên kết với một đối tƣợng duy nhất đƣợc lƣu trữ trong bảng đích.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]. Xét dữ liệu đƣợc cho nhƣ sau: Một bảng đích T Các bản ghi trong bảng đích RT LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 11 Một bảng tham chiếu NT Các bản ghi trong bảng tham chiếu RNT Trong đó, một hoặc nhiều bản ghi RNT trong bảng tham chiếu NT đƣợc liên kết với một bản ghi duy nhất RT trong bảng đích T. Tóm tắt dữ liệu trong nhiều bảng với các mối quan hệ một-nhiều có thể đƣợc định nghĩa nhƣ sau: Đị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 RNT trong bảng NT 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 RNT liên kết với mỗi bản ghi RT trong bảng T.2 Tóm tắt dữ liệu trong nhiều bảng với các mối quan hệ 1:n 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 tất cả các bảng tham chiếu (NT1, NT2, NT3, NT4, NT41). Vì bảng NT4 có mối quan hệ một-nhiều với bảng NT41 nên NT4 trở thành bảng đích để tóm tắt dữ liệu từ bảng tham chiếu NT41.
Dữ liệu tóm tắt từ các bảng NT1, NT2, NT3 và NT4 tạo nên các trƣờng đặc trƣng cho các giá trị của các bảng tham chiếu liên kết với T, các trƣờng này đƣợc nối thêm vào danh sách thuộc tính đã có trong bảng đích T. Một quá trình tóm tắt dữ liệu quan hệ bao gồm ba giai đoạn chính nhƣ mô tả trong hình 1. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.3: Ba giai đoạn chính trong quá trình tóm tắt dữ liệu quan hệ Trong giai đoạn thứ nhất, dữ liệu đƣợc xử lí để chuẩn bị cho quá trình chuyển đổi dữ liệu.