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. ô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. Bằng các phương pháp tiếp cận khác nhau, các nhà nghiên cứu như Dubois, Prade, Mamdani, Tagaki, Sugeno, Ishibuchi, Herrera, v.
đã đư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: 1. Tập mờ Định nghĩa 1.2 [25]: Cho tập nền X và x là phần tử của tập X. Một tập mờ F trên tập X được định nghĩa bởi một hàm thành viên hay còn gọi là hàm thuộc F x (degree of membership), đo “mức độ” mà phần tử x thuộc về tập F thỏa mãn điều kiện với x X , 0 F x 1. F x, F x x X 5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Khi F x = 0 thì x F hoàn toàn.
Khi F x = 1 thì x F hoàn toàn. 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 x = 1 với x X 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 x chỉ nhận hai giá trị 0 hoặc 1.3: X = {X1, X2, X3, X4} Hàm thuộc không còn mang 2 Biểu diễn tập mờ theo đồ thị. giá trị tuyệt đối 0 hay 1, mà là giá trị thuộc đoạn [0,1].1: Tập mờ và biểu diễn tập mờ Ví dụ 1.4: Cho tập X gồm 5 người là x 1 , x 2 , x 3 , x 4 , x 5 tương ứng có tuổi là 50, 10, 15, 55, 70, xác định tập F là tập hợp những người “Trẻ”? Ta có thể xây dựng hàm thuộc như sau: µF(50)=0. 6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Khi đó tập mờ F = {(50, 0.05)} và F được biểu diễn như Hình 1.2: Ví dụ một tập mờ * Số 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. Trong điều khiển, với mục đích sử dụng các hàm thuộc sao cho khả năng tích hợp chúng là đơn giản, người ta thường chỉ quan tâm đến hai dạng số mờ hình thang và số mờ hình tam giác. Số mờ hình thang Hàm thành viên có dạng sau [1]: 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.
Số mờ hình thang. Số mờ hình tam giác Số mờ hình tam giác là trường hợp đặc biệt của số mờ hình thang. Hàm thành viên có dạng sau: xa b a , a x b c x F x , b xc cb 0, otherwise Hình 1. Số mờ hình tam giác.
Giới thiệu về phân cụm mờ 1. Khái quát phân cụm 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, 8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com sao cho các đối tượng trong cùng một cụm tương tự nhau và các đối tượng khác cụm thì không tương tự nhau [23]. 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.1: Cho X là một tập dữ liệu gồm N vector: x 1 , x 2 ,. Bài toán phân cụm là chia tập dữ liệu X , c cụm dữ liệu Z z 1 , z 2 ,. Thỏa mãn 3 điều kiện sau: zi , i 1, 2,., c c X i 1 zi zi z j với i j ; i, j 1, 2,., c 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 9 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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. - Lập quy hoạch đô thị: Nhận dạng các nhóm nhà theo kiểu và vị trí địa lý, v.v, nhằm cung cấp thông tin cho quy hoạch đô thị.
- 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. - Địa lý: Phân lớp các động vật, thực vật và đưa ra đặc trưng của chúng. - 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.
Độ đo gần gũi Trong định nghĩa về bài toán phân cụm, chúng tôi đã đưa ra cụm từ “đối tượng tương tự nhau”. Vậy hai đối tượng như thế nào để gọi là tương tự nhau và làm sao để đo mức độ tương tự giữa chúng. Định nghĩa: Một độ đo không tương tự trên X là một hàm: :XX R Sao cho: 0 R : x, x x, y , x, y R x, y y, x , x, y Ngoài ra nếu: x, x 0 nếu x y x, y x , z z , y 10 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Thì được gọi là một độ đo không tương tự metric (DM metric). Như vậy, ta thấy rằng, độ đo không tương tự nhỏ nhất khi hai vector đồng nhất hay tương tự nhau.
Một số độ đo không tương tự: Khoảng cách giữa hai đối tượng x , y như sau Khoảng cách Minskowski: 1/ q n q d ( x, y ) xi yi i 1 với q là số nguyên dương. Khoảng cách Euclide: n 2 d ( x, y ) x y i 1 i i Đây là trường hợp đặc biệt của khoảng cách Minkowski với q 2 N Khoảng cách Manhattan: x, y i 1 xi yi. Khoảng cách cực đại: x, y max i 1. y Độ đo tương tự Cosin hai vector: cos x.
y Một số phương pháp phân cụm điển hình Dựa trên cách tiếp cận và thuật toán sử dụng, người ta phân các thuật toán phân cụm theo các phương pháp chính sau: - Phân cụm phân hoạch - Phân cụm phân cấp - Phân cụm dựa trên mật độ - Phân cụm dựa trên lưới - Phân cụm dựa trên mô hình - Phân cụm có ràng buộc 11 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Các bước phân cụm - Chọn lựa đặc trưng: Các đặc trưng phải được chọn lựa một cách hợp lý để có thể “mã hoá” nhiều nhất thông tin liên quan đến công việc. Mục tiêu chính của bước này là phải giảm thiểu sự dư thừa thông tin giữa các đặc trưng. Các đặc trưng cần được tiền xử lý trước khi dùng chúng trong các bước sau.
- Chọn độ đo gần gũi: Đây là một độ đo chỉ ra mức độ tương tự hay không tương tự giữa hai véc tơ đặc trưng. Phải đảm bảo rằng tất cả các véc tơ đặc trưng góp phần như nhau trong việc tính toán độ đo gần gũi và không có đặc trưng nào át hẳn đặc trưng nào. Điều này được đảm nhận bởi quá trình tiền xử lý. - Tiêu chuẩn phân cụm: Điều này phụ thuộc vào sự giải thích của chuyên gia cho thuật ngữ “dễ nhận thấy” dựa vào loại của các cụm được chuyên gia cho rằng đang ẩn dấu dưới tập dữ liệu.
Chẳng hạn, cụm trong không gian một chiều sẽ có tiêu chuẩn khác với cụm trong không gian nhiều chiều. - Thuật toán phân cụm: Cần lựa chọn một sơ đồ thuật toán riêng biệt nhằm làm sáng tỏ cấu trúc cụm của tập dữ liệu.