Chương 1: GIỚI THIỆU ĐỀ TÀI 1.1 Lý do chọn đề tài Chúng ta đang sống trong một thế giới đầy dữ liệu. Mỗi ngày, người ta gặp phải một số lượng lớn các thông tin và lưu trữ hoặc biểu diễn nó thành các dữ liệu, để dễ dàng cho việc phân tích và quản lý thêm. Thêm vào đó, với sự phát triển ngày càng mạnh mẽ của công nghệ thông tin, việc tin học hóa đã đi vào mọi lĩnh vực đời sống sản xuất, kinh doanh, giáo dục, quản lý, y tế, vận tải,. đã làm cho khả năng thu thập và lưu trữ thông tin của các hệ thống thông tin tăng một cách nhanh chóng với một lượng dữ liệu lưu trữ khổng lồ.
Lúc này, việc phân tích dữ liệu đóng một vai trò không thể thiếu cho sự hiểu biết các hiện tượng khác nhau. Với lượng dữ liệu tăng nhanh và khổng lồ như vậy, rõ ràng các phương pháp phân tích dữ liệu truyền thống sẽ không còn hiệu quả, gây tốn kém và dễ dẫn đến những kết quả sai lệch. Để có thể khai thác hiệu quả các cơ sở dữ liệu (CSDL) lớn, một lĩnh vực khoa học mới ra đời: Khám phá tri thức trong CSDL (Knowledge Discovery in Databases – KDD), và khai phá dữ liệu (Data Mining) là một công đoạn chính của quá trình KDD. Gom 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 có giám sát (Unsupervised Learning) trong học máy (Machine Learning).
Gom cụm dữ liệu được nghiên cứu phát triển trên nhiều cộng đồng như thống kê, học máy…. Tuy nhiên, việc nghiên cứu và ứng dụng các kỹ thuật khai phá dữ liệu cũng gặp phải những khó khăn, thách thức lớn, trong đó có vấn đề dữ liệu không đầy đủ. Dữ liệu không đầy đủ hay dữ liệu bị thiếu, xảy ra khi không có giá trị dữ liệu được lưu trữ trong các biến trong một quan sát. Dữ liệu không đầy đủ xuất hiện phổ biến và có thể có một tác động đáng kể đến kết luận có thể được rút ra từ các dữ liệu.
Rất nhiều các nghiên cứu gần đây trong lĩnh vực khai phá dữ liệu có liên quan đến dữ liệu không đầy đủ. Chính vì những lý do trên, tôi chọn đề tài “Gom cụm dữ liệu không đầy đủ”, tập trung giải quyết vấn đề gom cụm trên tập dữ liệu không đầy đủ, đồng thời cũng đảm bảo mô hình gom cụm có chất lượng cụm cao.2 Mục tiêu của đề tài Đề tài tập trung nghiên cứu bài toán gom cụm với dữ liệu không đầy đủ, từ đó đưa ra giải thuật để giải quyết bài toán đó. Đối với vấn đề xử lý dữ liệu bị thiếu, đề tài sẽ giải quyết bên trong giải thuật. Kết quả đạt được là mô hình cụm có chất lượng cụm cao chấp nhận được và khả năng xử lý dữ liệu không đầy đủ với độ sai lệch nhỏ.
Về mặt khoa học, đề tài xem xét giải quyết bài toán gom cụm dữ liệu không đầy đủ với hai phương pháp gom cụm dựa trên kernel là Kernel-based fuzzy-c-means 1 (KFCM) và Mean shift, kết quả thu được đảm bảo chất lượng cụm đủ tốt, cụm có hình dạng tùy ý, xử lý được các giá trị bị thiếu và hạn chế thông số đầu vào. Với giải thuật KFCM cải tiến, đã gom được các cụm có chất lượng cao, xử lý được dữ liệu bị thiếu. Nhưng cụm kết quả của KFCM cải tiến còn bị phụ thuộc dạng siêu cầu, giải thuật Mean shift cải tiến đã giải quyết tốt hơn, giải thuật Mean shift không cần biết trước số lượng cụn, không hạn chế hình dạng cụm, ít thông số đầu vào, cụm có chất lượng cao và xử lý được dữ liệu không đầy đủ. Về mặt thực tiễn, các dữ liệu không đầy đủ là thường gặp, làm tốn kém về chi phí, thời gian, con người.
Các trường hợp gây ra dữ liệu không đầy đủ phổ biến như là dữ liệu cần xử lý đến trễ, dữ liệu cố tình bị xóa do thông tin không phù hợp hoặc do ngẫu nhiên bị thiếu bởi các nguyên nhân từ con người, thiết bị hỏng hóc. Để đối phó với loại dữ liệu này ta có thể thực hiện trong giai đoạn tiền xử lý nhưng kết quả có thể tạo ra các dữ liệu sai lệch làm ảnh hưởng tới chất lượng gom cụm. Do đó một giải pháp gom cụm tốt có khả năng xử lý dữ liệu không đầy đủ sẽ giúp ích rất nhiều cho quá trình khám phá tri thức, giảm thiểu được nhiều về chi phí.3 Đối tượng và phạm vi nghiên cứu Đối tượng nghiên cứu sẽ được lấy từ tập dữ liệu chuẩn UCI (http://archive.edu/ml/) và tập dữ liệu nhân tạo, với kích thước được xem là đủ lớn. Dữ liệu sẽ được xử lý để trở thành không đầy đủ cho bài toán gom cụm.
Việc xử lý dữ liệu ở đây chỉ là cho một số thành phần mất đi theo nguyên tắc cụ thể sẽ được nói rõ trong thực nghiệm, không xem xét đến các vấn đề tiền xử lý dữ liệu (thu giảm chiều, chuẩn hóa,…). Mã nguồn được viết trên ngôn ngữ lập trình java. Phạm vi nghiên cứu tập trung xem xét trên toàn bộ thuộc tính của tập dữ liệu, bao gồm trong đó các giá trị bị thiếu. Xây dựng mô hình gom cụm xử lý được tập dữ liệu không đầy đủ để sau khi gom cụm đảm bảo được chất lượng gom cụm cao.4 Phương pháp nghiên cứu Việc chuẩn bị tài liệu nghiên cứu: Trong quá trình nghiên cứu, có tham khảo tài liệu về các chủ đề sau đây: Các tài liệu về data mining.
Tài liệu về gom cụm dữ liệu và đánh giá các kỹ thuật gom cụm. Các tài liệu về gom cụm dữ liệu không đầy đủ. Các tài liệu về đánh giá các kỹ thuật gom cụm không đầy đủ. 2 Việc tiến hành nghiên cứu: Hình 1.1: Mô hình thủ tục gom cụm cơ bản [20] Việc tiến hành nghiên cứu sẽ dựa theo hình 1.
Xu và Donald C.Wunsch [20], gồm các bước như sau: Việc chuẩn bị dữ liệu: Một phần sẽ dùng tập dữ liệu nhân tạo theo ý tưởng của R.Bezdek [3], một phần dữ liệu sẽ được lấy từ data chuẩn UCI, dữ liệu sẽ được xử lý trở thành không đầy đủ cho phù hợp với yêu cầu của bài toán. Việc xây dựng giải pháp gom cụm trên dữ liệu không đầy đủ sẽ dựa trên thuật toán Mean shift ở [1] và Kernel-based fuzzy-c-means ở [6], các thuật toán này được chọn do được chứng minh về tính hiệu quả, hiện thực với chi phí và thời gian cho phép. Đánh giá cụm, đây là khâu quan trọng nhất trong kỹ thuật gom cụm, cũng là khâu quan trọng nhất của đề tài. Đánh giá, so sánh và chọn ra phương pháp gom cụm có chất lượng đủ tốt.
Việc đánh giá kết quả gom cụm dữ liệu không đầy đủ không thể dùng đánh giá ngoại được bởi vì cấu trúc bản thân tập dữ liệu không rõ ràng do chứa các giá trị thiếu, các giá trị này làm mờ đi cấu trúc tập dữ liệu do đó sẽ đánh giá kết quả gom cụm thông qua các chỉ số đánh giá nội về độ phân tách, độ chặt của cụm và thông qua chỉ số đánh giá cho việc xử lý dữ liệu không đầy đủ. Các chỉ số đánh giá nội gồm Xie- Beni, Fukuyama-Sugeno và Dunn, đánh giá cho việc xử lý dữ liệu không đầy đủ trên độ đo Input error. Tiếp theo sẽ so sánh các kết quả đánh giá gom cụm trên các giải thuật khác nhau. Từ các đánh giá, đưa ra nhận xét và xác định cụm kết quả tốt nhất.
3 Chương 2: TỔNG QUAN VỀ GOM CỤM VÀ DỮ LIỆU KHÔNG ĐẦY ĐỦ Các thuật toán gom cụm dữ liệu phân dữ liệu vào một số lượng nhất định các cụm (nhóm, tập hợp con hoặc các danh mục). Hầu hết định nghĩa mô tả một cụm bằng cách xem xét tính đồng nhất bên trong và sự tách biệt bên ngoài, tức là, các đối tượng trong cùng một cụm sẽ tương tự như nhau, trong khi các đối tượng trong các cụm khác nhau thì không tương tự. Sau đây là một số mô tả toán học đơn giản của một số loại gom cụm. Cho một tập các mẫu đầu vào X x1 ,., xi , , xn với xi xi1 , xi 2 ,, xid R T d và mỗi xij còn được gọi là một đặc trưng (biến, chiều, hoặc thuộc tính).
1) Gom cụm cứng tìm kiếm một phân vùng K của X, C C1 ,, CK K N , để cho Ci , i 1,., K và i j 2) Với gom cụm cứng, mỗi một đối tượng chỉ thuộc về một cụm. Tuy nhiên một đối tượng cũng có thể thuộc về tất cả các cụm với một mức độ thành viên trong gom cụm mờ. 3) Gom cụm theo cấp bậc cố gắng để xây dựng một cấu trúc phân vùng lồng cấp giống như cấu trúc cây của X, H H1 ,., HQ Q N sao cho Ci H m , C j H l và m l nghĩa là Ci C j hoặc Ci C j , với i, j i, m, l 1,.1 Phân tích cụm 2.1 Bốn bước cơ bản của thủ tục phân tích cụm Bốn bước của thủ tục phân tích cụm sẽ dựa theo Rui. Xu và Donald C.Wunsch [20] theo như ở hình 1.
Lựa chọn hoặc khai thác đặc trưng. Lựa chọn đặc trưng là lựa chọn các đặc trưng phân biệt từ một tập hợp các ứng viên, trong khi khai thác đặc trưng sử dụng một số biến đổi để tạo ra các đặc trưng hữu ích và mới lạ từ những bản gốc. Cả hai đều rất quan trọng đối với hiệu quả của ứng dụng gom cụm. Việc lựa chọn các đặc trưng rất có thể làm giảm khối lượng công việc và đơn giản hóa quá trình thiết kế tiếp theo.
Nói chung, các đặc trưng lý tưởng nên được sử dụng trong phân biệt các mẫu thuộc các cụm khác nhau, phải ít bị nhiễu và dễ dàng để trích xuất và diễn giải. Thiết kế hoặc lựa chọn thuật toán gom cụm. Thường được kết hợp với việc lựa chọn một độ đo tương ứng và việc xây dựng một hàm tiêu chuẩn. Các đối tượng được nhóm lại theo sự giống nhau.
Rõ ràng, các độ đo sự tương đồng trực tiếp ảnh hưởng sự hình thành của các cụm kết quả. Hầu hết các thuật toán gom cụm là rõ ràng hoặc ngầm định có sự kết nối với một số định nghĩa của độ đo tương đồng. Khi một độ đo 4 tương đồng được chọn, việc xây dựng một hàm mục tiêu cho cụm là một vấn đề tối ưu hóa, và có nhiều giải pháp phong phú.
