- VỀ TÍNH HIỆU QUẢ CỦA CÁC THUẬT TOÁN TỐI ƢU TIẾN HÓA CHO PHÂN CỤM MỜ VÀ ỨNG DỤNG. - CHƢƠNG 1: TỔNG QUAN VỀ PHÂN CỤM MỜ. - Tập mờ. - Giới thiệu về phân cụm mờ. - Khái quát phân cụm. - Các bước phân cụm. - Phân cụm mờ. - Thuật toán Fuzzy C – Means (FCM. - Thuật toán Fuzzy C - Means. - CHƢƠNG 2: CÁC THUẬT TOÁN TỐI ƢU TIẾN HÓA CHO PHÂN CỤM MỜ. - Tính toán tiến hóa. - Các dạng của thuật toán tiến hóa. - Thuật toán lập trình tiến hóa. - Chiến lược tiến hóa. - Thuật toán di truyền. - Tiến hóa vi phân. - Thuật toán văn hóa. - Một số thuật toán cụ thể. - Thuật toán tìm kiếm Tabu. - Áp dụng thuật toán tối ưu tiến hóa cho phân cụm mờ. - Thuật toán Fuzzy J – Means heuristic (FJM. - Thuật toán VNS. - Thuật toán tối ưu bầy đàn cho phân cụm mờ (FPSO. - CHƢƠNG 3: SO SÁNH HIỆU NĂNG THUẬT TOÁN TỐI ƢU TIẾN HÓA. - Dữ liệu. - So sánh hiệu năng thuật toán. - Bài toán. - Kết quả chạy thực nghiệm bài toán. - Tập mờ và biểu diễn tập mờ Hình 1.2. - Ví dụ một tập mờ. - Minh họa dữ liệu đầu vào thử nghiệm lưu trên tệp excel Hình 3. - Tóm tắt trường dữ liệu đầu vào. - Tóm tắt trường dữ liệu đầu vào Hình 3. - Minh họa dữ liệu đầu vào cho bài toán ứng dụng lưu trên tệp exel Hình 3.6. - Phân cụm mờ C - Means FCM Fuzzy C – Means. - Phân cụm mờ J - Means FJM Fuzzy J – Means. - Chiến lược tiến hóa ES Evolutionary Strategies Thuật toán di truyền GA Genetic Algorithms. - Thuật toán tiến hóa EA Evolutionary Algorithms. - Tập mờ FS Fuzzy Set. - Thuật toán tìm kiếm Tabu TS Tabu search. - Sự bùng nổ thông tin đã đem đến lượng dữ liệu khổng lồ. - Chúng ta càng có nhu cầu khám phá kho dữ liệu đó phục vụ cho nhu cầu con người, điều đó đòi hỏi con người phải biết khai thác dữ liệu và xử lý thông tin đó thành tri thức có ích.. - Một trong những kỹ thuật quan trọng trong quá trình khai phá dữ liệu và xử lý dữ liệu lớn là kỹ thuật phân cụm dữ liệu. - Phân cụm đặc biệt hiệu quả khi ta không biết về thông tin của các cụm, hoặc khi ta quan tâm tới những thuộc tính của cụm mà chưa biết hoặc biết rất ít về những thông tin đó. - Phân cụm được coi như một công cụ độc lập để xem xét phân bố dữ liệu, làm bước tiền xử lý cho các thuật toán khác. - Việc phân cụm dữ liệu có rất nhiều ứng dụng như trong lập quy hoạch đô thị, nghiên cứu trái đất, địa lý, khai phá Web v.v.. - Ngày nay, cùng với kỹ thuật phân cụm kết hợp với lý thuyết mờ của Zadeh phương pháp phân cụm mờ đã và đang phát triển và được ứng dụng rộng rãi trong thực thực tiễn, ví dụ như phân tích nhu cầu khách hàng, phân đoạn ảnh, nhận dạng mặt người, nhận dạng cử chỉ và điệu bộ, phân tích rủi ro, dự báo nguy cơ phá sản cho ngân hàng và nhiều bài toán khác. - Những vấn đề chính được quan tâm nhiều trong phân cụm nói chung và phân mờ nói riêng là nâng cao chất lượng phân cụm, tính toán thông qua một số độ đo chất lượng cụ thể. - Những nhược điểm của phân cụm mờ liên quan đến việc xác định số cụm tự động, học đo khoảng cách thích nghi, lựa chọn tham số tối ưu, xây dựng tập mờ trên các tập mờ mở rộng, v.v. - Tuy nhiên, các nghiên cứu này chưa quan tâm đến việc xác định nghiệm tối ưu toàn cục của bài toán phân cụm, và hàm mục tiêu của bài toán hay cách thức phân chia dữ liệu vẫn được sử. - Để xác định nghiệm tối ưu toàn cục của bài toán phân cụm, các thuật toán tối ưu tiến hóa như thuật toán di truyền, tối ưu bầy đàn, v.v. - được áp dụng trong việc tìm nghiệm tối ưu toàn cục của bài toán tối ưu. - Và trong khuôn khổ luận văn này sẽ tìm hiểu vấn đề đó trên cơ sở khảo sát một số thuật toán tối ưu tiến hóa cho bài toán phân cụm mờ, cụ thể là thuật toán Fuzzy J - Means, Variable Neighbourhood Search và Fuzzy Particle Swarm Optimization.. - Trong luận văn này chúng tôi khảo sát môt số thuật toán tối ưu tiến hóa cho bài toán phân cụm mờ, cụ thể là thuật toán Fuzzy J – Means (FJM), Variable Neighbourhood Search (VNS) và Fuzzy Particle Swarm Optimization (FPSO). - Các thuật toán này sẽ được áp dụng cho bài toán phân tích nhu cầu khách hàng – là mục tiêu quan trọng của bất kỳ doanh nghiệp nào trong việc xác định các khách hàng tiềm năng, nhu cầu của nhóm khách hàng đó và mức độ hài lòng về sản phẩm và dịch vụ. - Cụ thể với một cơ sở dữ liệu mẫu về thống kê doanh doanh số bán hàng của một công ty kinh doanh thiết bị y tế cho khoảng 500 bệnh viện [26] được sử dụng làm dữ liệu đầu vào cho các thuật toán trên. - Qua đây, tính hiệu quả của các thuật toán tối ưu tiến hóa cho bài toán phân cụm mờ theo các tiêu chí về chất lượng và thời gian tính toán được làm rõ đồng thời phác họa chi tiết về các chức năng chính của bài toán phân tích nhu cầu khách hàng.. - Chƣơng 1: Tổng quan về phân cụm mờ. - Trong chương này, luận văn sẽ trình bày tổng quan về tập mờ, bài toán phân cụm và phân cụm mờ và thuật toán cơ bản giải quyết vấn đề phân cụm trên tập mờ đó là thuật toán Fuzzy C – Means (FCM). - Từ thuật toán này chúng tôi sẽ khảo sát các thuật toán tối ưu tiến hóa cho bài toán phân cụm mờ.. - Chƣơng 2: Các thuật toán tối ƣu tiến hóa cho phân cụm mờ. - Tiếp theo, chúng tôi sẽ trình bày thuật toán Fuzzy J – Means (FJM) được phát triển từ thuật toán Fuzzy C – Means (FCM) trong việc tìm nghiệm tối ưu cho bài toán, từ đó có nhận xét về hiệu quả của bài toán phân cụm mờ được áp dụng thuật toán trên. - Tiếp theo, chúng tôi khảo sát thuật toán Variable Neighbourhood Search (VNS) được phát triển tiếp từ thuật toán Fuzzy J – Means và phần cuối của chương này trình bày về thuật toán Fuzzy Particle Swarm Optimization (FPSO) lai của hai phương pháp Fuzzy C – Means và Particle Swarm Optimization (PSO). - Nhận xét chung các thuật toán cũng được nhắc trong chương này.. - Chƣơng 3: So sánh hiệu năng thuật toán tối ƣu tiến hoá. - Trong chương này, chúng tôi cài đặt và đánh giá hiệu năng các thuật toán:. - FCM, FJM, VNS và FPSO theo các tiêu chí về chất lượng phân cụm thông qua giá trị hàm mục tiêu và thời gian tính toán. - Từ đây, hiệu quả của các thuật toán tối ưu tiến hóa cho phân cụm mờ được khẳng định.. - Do đó, lý thuyết này không thể xử lý những dữ liệu có tính không chắc chắn, không rõ ràng.. - Zadeh và Dieter Klaua là người sáng lập ra lý thuyết tập mờ [25], mở đầu bằng bài báo “Fuzzy Sets” trên tạp chí “Information and Control” năm 1965. - Ý tưởng lý thuyết tập mờ của Zadeh là từ những khái niệm trừu tượng, không chắc chắn của thông tin như độ tuổi (trẻ – già), chiều cao (cao – thấp), nhiệt độ (nóng – lạnh), v.v. - ông đã tìm ra cách biểu diễn bằng một khái niệm toán học được gọi là tập mờ FS, như là một sự khái quát của khái niệm tập hợp.. - đã đưa ra những kết quả cả về lý thuyết và ứng dụng trong các bài toán điều khiển mờ, khai phá dữ liệu mờ, cơ sở dữ liệu mờ, các hệ hỗ trợ quyết định. - Tập mờ FS được định nghĩa như sau:. - Một tập mờ. - Tập mờ F rỗng nếu và chỉ nếu F. - x = 0 với x X Tập mờ F toàn phần nếu và chỉ nếu F. - Như vậy, khái niệm tập mờ là sự tổng quát hóa khái niệm tập rõ bởi hàm thuộc của nó có thể lấy giá trị bất kỳ trong khoảng [0, 1], tập rõ chỉ là một tập mờ đặc biệt vì hàm thuộc F. - Biểu diễn tập mờ theo đồ thị.. - Hình 1.1: Tập mờ và biểu diễn tập mờ. - Khi đó tập mờ F và F được biểu diễn như Hình 1.2 sau:. - Hình 1.2: Ví dụ một tập mờ. - Xét tập mờ F trên tập các số thực R. - Về nguyên tắc, không có ràng buộc chặt đối với việc xây dựng các tập mờ để biểu thị ngữ nghĩa của các khái niệm ngôn ngữ. - Tuy nhiên, để đơn giản trong xây dựng các tập mờ và trong tính toán trên các tập mờ, người ta đưa ra khái niệm tập mờ có dạng đặc biệt, gọi là số mờ để biểu thị các khái niệm mờ về số như gần 10, khoảng 15, lớn hơn nhiều so với 10,v.v.. - Giới thiệu về phân cụm mờ 1.2.1. - Phân cụm là kỹ thuật rất quan trọng trong khai phá dữ liệu, nó thuộc lớp các phương pháp học không giám sát trong học máy, nhằm tìm kiếm, phát hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn và quan trọng trong tập dữ liệu lớn để từ đó cung cấp thông tin, tri thức cho việc ra quyết định.. - Có rất nhiều định nghĩa khác nhau về kỹ thuật này, nhưng về bản chất ta có thể hiểu phân cụm là các qui trình tìm cách nhóm các đối tượng đã cho vào các cụm,. - Mục đích của phân cụm là tìm ra bản chất bên trong các nhóm nội tại bên trong của bộ dữ liệu không có nhãn. - Tuy nhiên, không có tiêu chí nào là được xem là tốt nhất để đánh giá hiệu quả của phân tích phân cụm, điều này phụ thuộc vào mục đích cuối cùng của phân cụm dữ liệu. - Do đó, người sử dụng phải cung cấp tiêu chuẩn, theo cách như vậy mà kết quả của phân cụm sẽ phù hợp với nhu cầu của người sử dụng cần.. - Cho X là một tập dữ liệu gồm N vector. - Bài toán phân cụm là chia tập dữ liệu X , c cụm dữ liệu Z. - Phân cụm được đóng vai trò quan trọng trong các nghành khoa học:. - Thương mại: Phân cụm dữ liệu giúp các nhà cung cấp biết được nhóm khác hàng quan trọng có các đặc trưng tương đồng nhau và đặc tả họ từ các mẫu trong cơ sở dữ liệu khách hàng.. - Sinh học: Phân cụm dữ liệu được sử dụng để xác định các loại sinh vật, phân loại các Gen với chức năng tương đồng và thu được các cấu trúc trong các mẫu.. - Phân tích dữ liệu không gian: Do sự đồ sộ của dữ liệu không gian như dữ liệu thu được từ các hình ảnh chụp từ vệ tinh, các thiết bị y học hoặc hệ thống thông tin địa lý (GIS), v.v, làm cho người dùng rất khó để kiểm tra các dữ liệu không gian một cách chi tiết. - Phân cụm dữ liệu có thể trợ giúp người dùng tự động. - phân tích và xử lý các dữ liêu không gian như nhận dạng và chiết xuất các đặc tính hoặc các mẫu dữ liệu quan tâm có thể tồn tại trong cơ sở dữ liệu không gian.. - Nghiên cứu trái đất: Phân cụm để theo dõi các tâm động đất nhằm cung cấp thông tin cho nhận dạng các vùng nguy hiểm.. - Khai phá Web: Phân cụm dữ liệu có thể khám phá các nhóm tài liệu quan trọng, có nhiều ý nghĩa trong môi trường Web. - Các lớp tài liệu này trợ giúp cho việc khám phá tri thức từ dữ liệu Web, khám phá ra các mẫu truy cập của khách hàng đặc biệt hay khám phá ra cộng đồng Web, v.v.