Tóm tắt Luận văn Thạc sĩ Công nghệ thông tin: Phương pháp phân cụm dựa trên tập thô và giải thuật di truyền

Luận văn trình bày khảo cứu một cách hệ thống của bài báo các kiến thức về phân cụm dữ liệu rõ, thô theo hướng KMeans và ứng dụng giải thuật di truyền để phân cụm dữ liệu thô. Trên cơ sở đó xây dựng chương trình thực nghiệm trên một số bộ dữ liệu, kết quả cho thấy ưu điểm của phương pháp mới.
Nội dung trích xuất từ tài liệu:
Tóm tắt Luận văn Thạc sĩ Công nghệ thông tin: Phương pháp phân cụm dựa trên tập thô và giải thuật di truyềnĐẠI HỌC QUỐC GIA HÀ NỘITRƢỜNG ĐẠI HỌC CÔNG NGHỆHOÀNG HUYỀN TRANGPHƢƠNG PHÁP PHÂN CỤM DỰA TRÊNTẬP THÔ VÀ GIẢI THUẬT DI TRUYỀNChuyên ngành: Hệ thống thông tinMã số: 60480104TÓM TẮT LUẬN VĂN THẠC SĨHà Nội - 20161MỞ ĐẦUPhân cụm dữ liệu là một trong những nghiên cứu quan trọngtrong khai thác dữ liệu và được áp dụng cho đa lĩnh vực [7,8].Mục tiêu chính trong phân cụm dữ liệu là để phân loại các đốitượng không có nhãn thành nhiều cụm mà các đối tượng thuộccùng một cụm thì tương tự nhau và khác nhau đối với các cụmkhác nhau. Phân cụm dữ liệu được chia làm hai loại là phân cụmcứng/rõ và phân cụm mềm [12,15].Một kỹ thuật được sử dụng phổ biến trong phân cụm dữ liệulà thuật toán K-Means, thuộc phân cụm rõ, với sự hội tụ nhanhchóng và khả năng tìm kiếm địa phương mạnh mẽ. Trong quátrình phân cụm K-Means truyền thống, các đối tượng dữ liệu thuđược trong cụm là nhất định. Tuy nhiên, trong thực tế giữanhững đối tượng thường không có ranh giới rõ ràng. Để tănghiệu quả và kết quả chính xác cho phân cụm việc sử dụng lýthuyết tập thô tiếp cận hỗ trợ phân cụm K-Meansđược đề xuất.Mặc dù giải thuật K-Means thô có khả năng tìm kiếm địaphương mạnh mẽ nhưng lại dễ rơi vào cực trị địa phương. Mộttrong những biện pháp có thể khắc phục được hạn chế này là kếthợp với giải thuật di truyền là một thuật toán dựa trên nguyêntắc của sự tiến hóa sinh học, có lượng lớn số song song tiềm ẩnthực hiện không gian tìm kiếm lớn và cung cấp giải pháp tối ưuhóa toàn cầu giúp tránh được tối ưu địa phương.Luận văn trình bày khảo cứu một cách hệ thống của bài báo[6] các kiến thức về phân cụm dữ liệu rõ, thô theo hướng KMeans và ứng dụng giải thuật di truyền để phân cụm dữ liệu thô.Trên cơ sở đó xây dựng chương trình thực nghiệm trên một sốbộ dữ liệu, kết quả cho thấy ưu điểm của phương pháp mới. Cấutrúc của luận văn gồm 3 chương :Chương I. Phân cụm dữ liệu và một số vấn đề liên quan.Chương II. Phân cụm dựa trên tập thô và thuật toán di truyền.Chương III. Cài đặt và phân tích thí nghiệm.2CHƢƠNG I. PHÂN CỤM DỮ LIỆU VÀ MỘT SỐ VẤN ĐỀLIÊN QUAN1.1. Giới thiệu về phân cụm dữ liệuKhai phá dữ liệu tuộc quá trình khám phá tri thức. Về bảnchất là giai đoạn duy nhất tìm ra được thông tin mới, tiềm ẩn cótrong cơ sở dữ liệu chủ yếu phục vụ cho mô tả và dự đoán.Phân cụm dữ liệu là một kỹ thuật trong khai phá dữ liệu vớimục đích chính là khám phá cấu trúc của mẫu dữ liệu để thànhlập các nhóm dữ liệu từ tập dữ liệu lớn, cho phép phân tích vànghiên cứu cho từng cụm dữ liệu nhằm khám phá và tìm kiếmcác thông tin tiềm ẩn, hữu ích.1.1.1. Khái niệm và mục đích của phân cụm dữ liệuBài toán phân cụm dữ liệu là một nhánh ứng dụng chính củalĩnh vực học không giám sát, mà dữ liệu mô tả trong bài toán làkhông được dán nhãn. Trong trường hợp này, thuật toán sẽ tìmcách phân cụm dữ liệu thành từng nhóm có đặc điểm tương tựnhau, nhưng đồng thời đặc tính giữa các nhóm đó lại phải càngkhác biệt càng tốt. Số các cụm dữ liệu có thể được xác địnhtrước theo kinh nghiệm hoặc có thể được tự động xác định theothuật toán.Hình 1.1. Quy trình phân cụm.Độ tương tự được xác định dựa trên giá trị các thuộc tính môtả đối tượng. Thông thường, phép đo khoảng cách thường đượcsử dụng để đánh giá độ tương tự hay phi tương tự. Vấn đề phâncụm có thể minh hoạ như hình 1,2:Hình 1.2. Mô phỏng sự phân cụm dữ liệu.3Ứng dụng của phân cụm dữ liệu: Được áp dụng trong rấtnhiều lĩnh vực như: Kinh doanh; Sinh học; Thư viện; Bảohiểm; www…1.1.2. Phương pháp phân cụm dữ liệuPhân cụm dữ liệu được chia làm hai loại là phân cụm dữ liệucứng và phân cụm dữ liệu mềm: Phân cụm dữ liệu cứng (hay phân cụm rõ) là phươngpháp gán mỗi đối tượng vào một và chỉ một cụm và xác địnhrõ ranh giới giữa các cụm. Một số thuật toán: Thuật toán KMeans, Thuật toán K-Medoids... Phân cụm dữ liệu mềm (hay phân cụm mờ) là phươngpháp cho phép mỗi đối tượng có thể thuộc một hoặc nhiềucụm dữ liệu và có sự mơ hồ hoặc mờ ranh giới giữa cáccụm: Thuật toán Fuzzy C-mean…Hình 1.3. Mô tả phân cụm cứng/rõ và phân cụm mềm/mờTùy theo đặc điểm về tính tương đồng của các đối tượngtrong bài toán đang xét, có nhiều cách tiếp cận cho thuật toánphân cụm. Các kỹ thuật gồm:- Phân cụm phân cấp (Hierarchical Data Clustering)- Phân cụm phân hoạch (Partition Based Data Clustering)- Phân cụm dựa trên mật độ (Density Based Data Clustering)- Phân cụm dựa trên lưới (Grid Based Data Clustering)1.1.3. Phân cụm với giải thuật K-MeansThuật toán K-Means (MacQueen, 1967)[2] là một trongnhững thuật toán học không giám sát đơn giản nhất để giải quyếtvấn đề phân cụm dữ liệu nổi tiếng, với số cụm được xác địnhtrước là k cụm.4Thuộc nhóm phân cụm dữ liệu cứng/rõ, ý tưởng chính là đểxác định k trọng tâm cho k cụm, một trọng tâm cho mỗi cụm.Những trọng tâm nên được đặt ở vị trí thích hợp nhất vì vị tríkhác nhau gây ra kết quả khác n ...