Báo cáo Tóm tắt dữ liệu quan hệ sử dụng phương pháp phân cụm bán giám sát dựa trên giải thuật di truyền

Tổng quan về phân cụm dữ liệu: Giới thiệu cách biểu diễn dữ liệu trong máy tính nhằm phục vụ cho quá trình phân cụm, giới thiệu độ tương đồng giữa các đối tượng trong tập dữ liệu, các phương pháp phân cụm dữ liệu. Với mỗi phương pháp phân cụm sẽ trình bày một số thuật toán tương ứng. Giải thuật di truyền: Tổng quan về giải thuật di truyền với các cách biểu diễn dữ liệu, cách xây dựng một giải thuật di truyền và mô tả các phép toán thực hiện trên đó. Phân tích ứng...
Nội dung trích xuất từ tài liệu:
Báo cáo "Tóm tắt dữ liệu quan hệ sử dụng phương pháp phân cụm bán giám sát dựa trên giải thuật di truyền "Tóm tắt dữ liệu quan hệ sử dụng phương pháp phân cụm bán giám sát dựa trên giải thuật di truyền Đỗ Thị Hòa Trường Đại học Công nghệ Luận văn Thạc sĩ ngành: Công nghệ phần mềm; Mã số: 60 48 10 Người hướng dẫn: PGS.TS Hoàng Xuân Huấn Năm bảo vệ: 2011 Abstract: Tổng quan về phân cụm dữ liệu: Giới thiệu cách biểu diễn dữ liệu trong máy tính nhằm phục vụ cho quá trình phân cụm, giới thiệu độ tương đồng giữa các đối tượng trong tập dữ liệu, các phương pháp phân cụm dữ liệu. Với mỗi phương pháp phân cụm sẽ trình bày một số thuật toán tương ứng. Giải thuật di truyền: Tổng quan về giải thuật di truyền với các cách biểu diễn dữ liệu, cách xây dựng một giải thuật di truyền và mô tả các phép toán thực hiện trên đó. Phân tích ứng dụng của giải thuật di truyền trong bài toán phân cụm. Tóm tắt dữ liệu quan hệ sử dụng phương pháp phân cụm bán bán giám sát dựa trên giải thuật di truyền. Phân tích khái niệm, cấu trúc quan hệ các bảng trong cơ sở dữ liệu, cách chuyển đổi dữ liệu. Trình bày thuật toán phân cụm bán giám sát dựa trên giải thuật di truyền để tóm tắt dữ liệu. Kết quả cài đặt thử nghiệm thuật toán. Chương này trình bày các kết quả thực nghiệm về phương pháp tóm tắt dữ liệu quan hệ sử dụng thuật toán phân cụm bán giám sát dựa trên giải thuật di truyền. Cài đặt thử nghiệm cho thuật toán được thực hiện bằng ngôn ngữ C++ trên tập dữ liệu thử nghiệm về năng suất lúa. Thông qua các nhận xét về giá trị các độ đo đánh giá, kết quả thực hiện chương trình là khả quan. Keywords: Phân cụm dữ liệu; Thuật toán; Giải thuật di truyền; Công nghệ phần mềmContent Trong thời đại hiện nay, cuộc cách mạng về khoa học và công nghệ đã có những bướcphát triển vượt bậc, đánh dấu những mốc son đáng tự hào trong nền văn minh của thế giới.Đóng góp một phần cho sự thay đổi này, không thể kể không kể đến các ngành đã và đangđược xem là mũi nhọn hiện nay như: Công nghệ thông tin, điện tử và truyền thông, công nghệsinh học… với những ứng dụng rộng rãi, đem lại những lợi ích to lớn cho các ngành khoa họckhác và các hệ thống phục vụ cho đời sống, kinh tế, xã hội. Cùng với sự phát triển này, mộtlượng dữ liệu ngày càng lớn và vô cùng phong phú đã được tạo ra. Với các kho dữ liệu khổnglồ như vậy, các thông tin yêu cầu từ nó không đơn thuần là các số liệu, mà đòi hỏi thêm ởmức cao hơn là các tri thức có thể hỗ trợ ra quyết định cho người dùng. Đã có rất nhiều cáccông trình nghiên cứu về việc tổ chức các kho dữ liệu, các thuật toán nhận dạng mẫu, và phânlớp ảnh, các hệ thốn thông tin lớn, các hệ hỗ trợ ra quyết định, …được công bố và ứng dụng.Một khái niệm mới là Data mining ra đời và mở ra những xu hướng mới trong công nghệkhám phá tri thức hiện nay. Một trong các hướng nghiên cứu của Data mining là Phân cụm dữ liệu. Bài toán phâncụm dữ liệu thuộc lĩnh vực học không giám sát, nhằm phân tập dữ liệu thành các tập con, thỏamãn điều kiện các đối tượng trong cùng một tập con có độ tương đồng cao, và ngược lại cácđối tượng ở các tập con khác nhau thì có độ tương đồng thấp. Hay nói cách khác, bài toánphân cụm dữ liệu là bài toán khám phá cấu trúc của tập dữ liệu. Tùy theo đặc điểm cấu trúccủa tập dữ liệu và mục đích sử dụng, có các phương pháp giải quyết khác nhau như: Phâncụm dựa vào phân hoạch, phân cụm theo phân cấp, phân cụm dựa vào mật độ và phân cụmdựa vào lưới. Trong đó, phương pháp phân cụm bán giám sát đươc ứng dụng khá phổ biến.Đây là phương pháp kết hợp giữa học không giám sát và học có giám sát. Trong việc giải quyết bài toán phân loại trong khai phá dữ liệu quan hệ, các phươngphá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ảngduy nhất. Khi đó, bảng dữ liệu thu được sẽ có kích thước vô cùng lớn. Để truy vấn, phải sửdụng các phép toán đại số quan hệ và tối ưu các phép toán này bằng phương pháp tối ưu truyvấn heuristic tức là tìm cách thực hiện các phép chiếu, phép chọn trước các phép toán 2 ngôi.Trong một số trường hợp khi nối nhiều bảng sẽ gây mất thông tin hoặc trùng lặp dữ liệu. Dođó, chuyển đổi dữ liệu trở thành phức tạp và tóm tắt dữ liệu thường kém hiệu quả. Mặt khác,việc áp dụng các phương pháp tóm tắt dữ liệu trong khai phá dữ liệu được lưu trên nhiều bảngcó quan hệ một-nhiều thường bị hạn chế do sự phức tạp của lược đồ cơ sở dữ liệu. Để có thể khắc phục được các vấn đề nêu trên, luận văn sẽ nghiên cứu một phươngpháp tiếp cận: Sử dụng kỹ thuật phần cụm bán giám sát dựa trên giải thuật di truyền để tóm tắtdữ liệu được lưu trong nhiều bảng. Nghiên cứu này dựa trên ý tưởng nghiên cứu của RaynerAlfred [17]. Kết quả của thuật toán được áp dụng phân c ...