Phân cụm dữ liệu trừ mờ và ứng dụng luận án thạc sĩ

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG TRẦN THỊ YẾN PHÂN CỤM DỮ LIỆU TRỪ MỜ VÀ ỨNG DỤNG Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS. TS LÊ BÁ DŨNG Thái Nguyên - 2012 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn LỜI CẢM ƠN Lời đầu tiên, em xin gửi lời biết ơn sâu sắc đến PGS.TS Lê Bá Dũng, ngƣời đã tận tình hƣớng dẫn, chỉ bảo, giúp đỡ em trong suốt quá trình làm luận văn. Em cũng xin đƣợc bày tỏ lòng biết ơn tới các thầy đã tham gia giảng dạy và chia sẻ những kinh nghiệm quý báu cho tập thể lớp nói chung và cá nhân em nói riêng. Tôi xin gửi lời cảm ơn tới gia đình, bạn bè, đồng nghiệp đã luôn ủng hộ, động viên và giúp đỡ để tôi có thể hoàn thành tốt luận văn.

Tôi cũng xin gửi lời cảm ơn tới Ban giám hiệu trƣờng Đại học Khoa học, Ban chủ nhiệm Khoa Toán-Tin đã tạo điều kiện thuận lợi cho tôi tham gia khóa học và hoàn thành luận văn. Một lần nữa, xin chân thành cảm ơn. Thái Nguyên, tháng 09 năm 2012 Học viên Trần Thị Yến Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn LỜI CAM ĐOAN Tôi xin cam đoan luận văn là kết quả của sự tìm hiểu, nghiên cứu các tài liệu một cách nghiêm túc dƣới sự hƣớng dẫn của PGS. TS Lê Bá Dũng.

Nội dung luận văn đƣợc phát triển từ ý tƣởng, sự sáng tạo của bản thân và kết quả có đƣợc hoàn toàn trung thực. Học viên Trần Thị Yến Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn MỤC LỤC LỜI CẢM ƠN. i LỜI CAM ĐOAN. iii MỤC LỤC.

iv DANH MỤC CÁC TỪ VIẾT TẮT. vi DANH MỤC CÁC BẢNG BIỂU, HÌNH ẢNH. vii MỞ ĐẦU .2 TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU. Khái niệm và mục tiêu của phân cụm dữ liệu.

Các ứng dụng của phân cụm dữ liệu. Các yêu cầu của phân cụm dữ liệu. Các kỹ thuật tiếp cận và một số thuật toán cơ bản trong phân cụm dữ liệu. Các phương pháp phân cụm phân hoạch - Partitioning Methods.

Phương pháp phân cụm phân cấp - Hierarchical Methods. Phương pháp phân cụm dựa trên mật độ - Density-Based Methods. Phương pháp phân cụm dựa trên lưới - Grid-Based Methods. Phương pháp phân cụm dựa trên mô hình - Model-Based Clustering Methods15 1.6 Phương pháp phân cụm có dữ liệu ràng buộc .19 PHƢƠNG PHÁP PHÂN CỤM TRỪ MỜ.

Phân cụm mờ và thuật toán phân cụm mờ. Tổng quan về phân cụm mờ. Thuật toán phân cụm C-Means mờ (FCM). Thuật toán phân cụm trừ (SC - Subtractive Clustering).

Thuật toán phân cụm trừ mờ (FSC – Fuzzy Subtractive Clustering) .31 ỨNG DỤNG PHƢƠNG PHÁP PHÂN CỤM TRỪ MỜ. Ứng dụng thuật toán SC cho xây dựng hệ luật .1 Trích xuất luật với tính toán xấp xỉ hàm. 31 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.2 Hệ thống suy diễn mờ (FIS) cho bài toán nút giao thông vùng ngoại ô .2 Ứng dụng thuật toán FSC vào phân đoạn ảnh .1 Phân đoạn ảnh. Phân đoạn ảnh sử dụng thuật toán phân cụm trừ mờ FSC .3 Thử nghiệm với thuật toán phân cụm trừ .4 Thử nghiệm với thuật toán phân cụm trừ mờ .5 Thử nghiệm thuật toán phân SC và FSC trên cùng một ảnh .49 DANH MỤC CÔNG TRÌNH KHOA HỌC ĐÃ CÔNG BỐ .50 TÀI LIỆU THAM KHẢO .51 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn DANH MỤC CÁC TỪ VIẾT TẮT CURE Clustering Using Representatives DBSCAN Density based Spatial Clutering of Application with Noise DENCLUE Clustering Based on Density Distribution Functions EM Expectation Maximization FCM Fuzzy C-Means FSC Fuzzy Subtractive Clustering OPTICS Ordering Points to Identify the Clustering Structure SC Subtractive Clustering Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn DANH MỤC CÁC BẢNG BIỂU, HÌNH ẢNH Hình 2.1: Hai nhóm dữ liệu của phân cụm trừ mờ Hình 3.1: Biểu đồ dữ liệu vào và dữ liệu ra Hình 3.2: Kết quả sau khi phân cụm Hình 3.3: Hàm thành viên tƣơng ứng với biến vào số ô tô sở hữu Hình 3.4: Hàm thành viên tƣơng ứng với biến vào số lƣợng việc làm Hình 3.5: Hàm thành viên tƣơng ứng với biến vào thu nhập trung bình Hình 3.6: Ảnh ban đầu của thuật toán phân cụm trừ Hình 3.7: Ảnh kết quả của thuật toán phân cụm trừ Hình 3.8: Ảnh ban đầu của thuật toán phân cụm trừ mờ Hình 3.9: Ảnh kết quả của thuật toán phân cụm trừ mờ Hình 3.10: Ảnh đầu vào cho cả 2 thuật toán Hình 3.11: Ảnh kết quả của thuật toán SC với 122 cụm Hình 3.12: Ảnh kết quả của thuật toán FSC với 18 cụm Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn MỞ ĐẦU Ngày nay, khai phá dữ liệu (Datamining) đã trở thành một trong những xu hƣớng nghiên cứu phổ biến trong lĩnh vực học máy và công nghệ tri thức.

Nhiều thành tựu nghiên cứu của Datamining đã đƣợc áp dụng trong thực tế. Datamining có nhiều hƣớng quan trọng và một trong các hƣớng đó là phân cụm dữ liệu (Data Clustering). Phân cụm dữ liệu là quá trình phân chia một tập dữ liệu ban đầu thành các cụm dữ liệu sao cho các phần tử trong một cụm "tƣơng tự" (similar) với nhau và các phần tử trong các cụm khác nhau sẽ "phi tƣơng tự" (dissimilar) với nhau. Phân cụm dữ liệu là một phƣơng pháp học không giám sát.

Hiện nay, các phƣơng pháp phân cụm đã và đang đƣợc phát triển và áp dụng nhiều trong các lĩnh vực khác nhau, bao gồm: nhận dạng, phân tích dữ liệu, nghiên cứu thị trƣờng, xử lý ảnh,… Các thuật toán phân cụm cũng rất đa dạng nhƣ K- means, Pam, C-means, C-means mờ, thuật toán phân cụm trừ,… Để tăng tính ổn định và chính xác của kết quả phân cụm, ngày càng có các tiếp cận mới. Một trong những cách tiếp cận đang đƣợc nghiên cứu đó là ứng dụng lý thuyết mờ vào bài toán phân cụm dữ liệu. Luận văn này trình bày phân cụm dữ liệu, một cách tiếp cận mới về phân cụm dữ liệu là thuật toán phân cụm trừ mờ và ứng dụng vào bài toán cụ thể. Luận văn bao gồm các nội dung chính sau: Chương 1: Tổng quan về phân cụm dữ liệu Chương 2: Phƣơng pháp phân cụm trừ mờ Chương 3: Ứng dụng phƣơng pháp phân cụm trừ mờ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn Chƣơng 1.

TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU 1. Khái niệm và mục tiêu của phân cụm dữ liệu Phân cụm dữ liệu là một kỹ thuật trong khai phá dữ liệu, là quá trình phân chia một tập dữ liệu ban đầu thành các cụm sao cho các phần tử trong một cụm “tƣơng tự” với nhau và các phần tử trong các cụm khác nhau sẽ “phi tƣơng tự” với nhau. Số các cụm dữ liệu đƣợc phân ở đây có thể đƣợc xác định trƣớc theo kinh nghiệm hoặc có thể đƣợc tự động xác định theo phƣơng pháp phân cụm. Trong học máy, phân cụm dữ liệu đƣợc xem là vấn đề học không có giám sát, vì nó phải giải quyết vấn đề tìm một cấu trúc trong tập hợp dữ liệu chƣa biết trƣớc các thông tin về cụm hay các thông tin về tập huấn luyện.

Trong nhiều trƣờng hợp, nếu phân lớp đƣợc xem là vấn đề học có giám sát thì phân cụm dữ liệu là một bƣớc trong phân lớp dữ liệu, phân cụm dữ liệu sẽ khởi tạo các lớp cho phân lớp bằng cách xác định các nhãn cho các nhóm dữ liệu. Phân cụm có ý nghĩa rất quan trọng trong hoạt động của con ngƣời. Ngay từ lúc bé, con ngƣời đã học cách làm thế nào để phân biệt giữa mèo và chó, giữa động vật và thực vật và liên tục đƣa vào sơ đồ phân loại trong tiềm thức của mình. Phân cụm đƣợc sử dụng rộng rãi trong nhiều ứng dụng, bao gồm nhận dạng mẫu, phân tích dữ liệu, xử lý ảnh, nghiên cứu thị trƣờng.

Với tƣ cách là một chức năng khai phá dữ liệu, phân cụm có thể đƣợc sử dụng nhƣ một công cụ độc lập chuẩn để quan sát đặc trƣng của mỗi cụm thu đƣợc bên trong sự phân bố của dữ liệu và tập trung vào một tập riêng biệt của các cụm để giúp cho việc phân tích đạt kết quả. Một vấn đề thƣờng gặp trong phân cụm là hầu hết các dữ liệu cần cho phân cụm đều có chứa dữ liệu nhiễu do quá trình thu thập thiếu chính xác hoặc thiếu đầy đủ, vì vậy cần phải xây dựng chiến lƣợc cho bƣớc tiền xử lý dữ liệu nhằm khắc phục hoặc loại bỏ nhiễu trƣớc khi chuyển sang giai đoạn phân tích cụm dữ liệu. Nhiễu ở đây đƣợc hiểu là các đối tƣợng dữ liệu không chính xác, không tƣờng minh Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn hoặc là các đối tƣợng dữ liệu khuyết thiếu thông tin về một số thuộc tính. Một trong các kỹ thuật xử lý nhiễu phổ biến là việc thay thế giá trị các thuộc tính của đối tƣợng nhiễu bằng giá trị thuộc tính tƣơng ứng.

Ngoài ra, dò tìm phần tử ngoại lai cũng là một trong những hƣớng nghiên cứu quan trọng trong phân cụm, chức năng của nó là xác định một nhóm nhỏ các đối tƣợng dữ liệu khác thƣờng so với các dữ liệu trong cơ sở dữ liệu, tức là các đối tƣợng dữ liệu không tuân theo các hành vi hoặc mô hình dữ liệu nhằm tránh sự ảnh hƣởng của chúng tới quá trình và kết quả của phân cụm. Tóm lại, phân cụm dữ liệu cần phải giải quyết các vần đề cơ bản nhƣ sau: - Biểu diễn dữ liệu, - Xây dựng hàm tính độ tƣợng tự, - Xây dựng các tiêu chuẩn phân cụm, - Xây dựng mô hình cho cấu trúc cụm dữ liệu, - Xây dựng thuật toán phân cụm và xác lập các điều kiện khởi tạo, - Xây dựng các thủ tục biểu diễn và đánh giá kết quả phân cụm. Theo các nghiên cứu cho thấy thì hiện nay chƣa có một phƣơng pháp phân cụm tổng quát nào có thể giải quyết trọn vẹn cho tất cả các dạng cấu trúc dữ liệu. Hơn nữa, các phƣơng pháp phân cụm cần có cách thức biểu diễn cấu trúc của các dữ liệu, với mỗi cách thức biểu diễn khác nhau sẽ có tƣơng ứng một thuật toán phân cụm phù hợp.