Tài liệu Phân cụm mờ và ứng dụng phân loại bệnh

ĐẠI HỌC THÁI NGUYÊN 1 TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG HOÀNG THỊ TÂN PHÂN CỤM MỜ VÀ ỨNG DỤNG PHÂN LOẠI BỆNH LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên - 2016 ĐẠI HỌC THÁI NGUYÊN 2 TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG HOÀNG THỊ TÂN PHÂN CỤM MỜ VÀ ỨNG DỤNG PHÂN LOẠI BỆNH Chuyên ngành: Khoa học máy tính Mã số: 60.48.01.01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC PGS. TS. ĐOÀN VĂN BAN Thái Nguyên - 2016 i LỜI CẢM ƠN Tôi xin chân thành cảm ơn toàn thể quý thầy cô trong Khoa Sau Đại Học Trường Đại học công nghệ thông tin và truyền thông là những người đã hết lòng dạy dỗ và truyền đạt những kiến thức quý báu cho tôi trong suốt thời gian học tập. Tôi xin gửi lời cảm ơn sâu sắc đến Thầy PGS-TS. Đoàn Văn Ban người đã giúp đỡ tôi trong suốt thời gian tôi thực hiện đề tài. Thầy đã định hướng, tạo những điều kiện thuận lợi và đã tận tình hướng dẫn để tôi hoàn thành đề tài này. Tôi xin gửi lời cảm ơn chân thành đến gia đình, bạn bè đã luôn là nguồn động viên to lớn, giúp đỡ tôi trong suốt quá trình tôi thực hiện đề tài. Tác giả Hoàng Thị Tân ii LỜI CAM ĐOAN Tôi xin cam đoan : - Những nội dung trong luận văn này là do tôi thực hiện dưới sự hướng dẫn trực tiếp của Thầy Đoàn Văn Ban. - Mọi tham khảo dùng trong luận văn đều được trích dẫn rõ ràng và trung thực. - Mọi sao chép không hợp lệ, vi phạm quy chế đào tạo hay gian trá, tôi xin chịu hoàn toàn trách nhiệm. - Các số liệu, kết quả nêu trong luận văn là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác. Tác giả Hoàng Thị Tân iii MỤC LỤC TRANG PHỤ BÌA .......................................................................................... 0 LỜI CẢM ƠN ..................................................................................................i LỜI CAM ĐOAN ...........................................................................................ii MỤC LỤC .................................................................................................... iii DANH MỤC CÁC BẢNG ............................................................................. vi DANH MỤC CÁC HÌNH VẼ .......................................................................vii MỞ ĐẦU ........................................................................................................ 1 Chương 1. PHÂN CỤM DỮ LIỆU ................................................................. 3 1.1. Khái niệm và mục tiêu của phân cụm dữ liệu ...................................... 3 1.1.1. Khái niệm ..................................................................................... 3 1.1.2. Mục tiêu........................................................................................ 4 1.2. Các kiểu dữ liệu và độ đo phân loại dữ liệu .......................................... 5 1.2.1. Phân loại dữ liệu ........................................................................... 5 1.2.2. Độ đo phân cụm dữ liệu ................................................................ 6 1.3. Các yêu cầu của phân cụm ................................................................. 10 1.4. Một số ứng dụng của phân cụm dữ liệu .............................................. 12 1.5. Một số kỹ thuật tiếp cận trong phân cụm dữ liệu ................................ 13 1.5.1. Phương pháp phân cụm phân hoạch ............................................ 13 1.5.2. Phương pháp phân cụm dữ liệu phân cấp .................................... 14 1.5.3. Phương pháp phân cụm dựa trên mật độ...................................... 15 1.5.4. Phương pháp phân cụm dựa trên lưới .......................................... 15 1.5.5. Phương pháp phân cụm dựa trên mô hình ................................... 16 1.5.6. Phương pháp phân cụm có dữ liệu ràng buộc .............................. 17 1.6. Một số thuật toán cơ bản trong phân cụm dữ liệu ............................... 18 1.6.1. Thuật toán phân cụm phân hoạch - Thuật toán k-means .............. 18 1.6.2. Thuật toán phân cụm phân cấp – Thuật toán CURE .................... 20 1.6.3. Thuật toán phân cụm dựa trên mật độ - Thuật toán DBSCAN ..... 22 1.6.4. Thuật toán phân cụm dựa trên lưới - Thuật toán STING.............. 26 1.6.5. Thuật toán phân cụm dựa trên mô hình - Thuật toán EM............. 28 1.6.6. Thuật toán phân cụm có dữ liệu ràng buộc .................................. 29 iv 1.7. Kết luận chương 1 .............................................................................. 30 Chương 2. PHÂN CỤM DỮ LIỆU MỜ ........................................................ 31 2.1. Phân cụm mờ ..................................................................................... 31 2.1.1. Giới thiệu phân cụm mờ .............................................................. 31 2.1.2. Các thuật toán trong phân cụm mờ .............................................. 32 2.2. Thuật toán FCM (Fuzzy C-means) ..................................................... 32 2.2.1. Hàm mục tiêu.............................................................................. 32 2.2.2. Thuật toán ................................................................................... 35 2.3. Thuật toán εFCM (ε- Insensitive Fuzzy C-means) .............................. 39 2.3.1. Hàm mục tiêu.............................................................................. 39 2.3.2. Thuật toán ................................................................................... 40 2.4. Thuật toán FCM-Cải tiến .................................................................. 41 2.5. Kết luận chương 2 .............................................................................. 48 Chương 3. ỨNG DỤNG PHÂN LOẠI BỆNH .............................................. 50 3.1. Thu thập và biểu diễn tri thức............................................................. 50 3.1.1. Giới thiệu bài toán phân loại bệnh ............................................... 50 3.1.2. Xây dựng quy trình lập luận phân loại bệnh ................................ 50 3.1.3. Thu thập các triệu chứng ............................................................. 52 3.1.4. Biểu diễn tri thức trong môi trường mờ ....................................... 56 3.2. Phương pháp suy diễn mờ .................................................................. 57 3.2.1. Cơ chế suy diễn mờ..................................................................... 57 3.2.2. Xác định độ phụ thuộc dựa trên tập mờ đa điều kiện ................... 58 3.3. Xây dựng ứng dụng ............................................................................ 59 3.3.1. Phân tích yêu cầu ........................................................................ 59 3.3.2. Thiết kế cơ sở dữ liệu .................................................................. 60 3.3.3. Xây dựng chương trình ............................................................... 61 3.3.4. Đánh giá thực nghiệm ................................................................. 67 3.4. Kết luận chương 3 .............................................................................. 70 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ..................................................... 71 TÀI LIỆU THAM KHẢO ............................................................................. 72 v DANH MỤC CÁC TỪ VIẾT TẮT FCM Fuzzy C-means εFCM ε- Insensitive Fuzzy C-means CSDL DBSCAN Cơ sở Dữ liệu Density Based Spatial Clustering of Applications with Noise STRING STatistical INformation Grid EM Expectation-Maximization CURE Clustering Using REpresentatives PAM Partitioning Around Medois CLARA Clustering LARge Application BIRCH OPTICS Thuật toán c-means mờ Balanced Iterative Reducing and Clustering using Hierarchies Ordering Points To Identify the Clustering Structure vi DANH MỤC CÁC BẢNG Số hiệu Tên Bảng Trang Bảng 1.1 Bảng các thuộc tính nhị phân 10 Bảng 3.1 Nhóm bệnh 53 Bảng 3.2. Vị trí, vùng đau 54 Bảng 3.3 Hướng lan của cơn đau 54 Bảng 3.4 Triệu chứng đau 54 Bảng 3.5 Triệu chứng phụ 55 Bảng 3.6 Tính chất cơn đau 55 Bảng 3.7 Thời điểm xuất hiện cơn đau 55 Bảng 3.8 Vùng mờ hóa để đánh giá mức độ triệu chứng 58 Bảng 3.9 Bảng lưu trữ thông tin Bệnh 60 Bảng 3.10 Bảng lưu trữ thông tin các triệu chứng 60 Bảng 3.11 Bảng quan hệ giữa Triệu chứng và Bệnh 60 Bảng 3.12 Ví dụ nhóm các triệu chứng vào các nhóm bệnh 69 Bảng 3.13 Độ phụ thuộc các triệu chứng 69 vii DANH MỤC CÁC HÌNH VẼ Số hiệu Tên Hình vẽ Trang Hình 1.1 Các chiến lược phân cụm dữ liệu 14 Hình 1.2 Cấu trúc phân cấp 16 Hình 1.3 Các cách mà các cụm có thể đưa ra 17 Hình 1.4 Các thiết lập để xác định ranh giới các cụm ban đầu 18 Hình 1.5 Tính toán trọng tâm của các cụm mới 18 Hình 1.6 Khái quát thuật toán CURE 20 Hình 1.7 Các cụm dữ liệu được khám phá bởi CURE 21 Hình 1.8 Hình dạng các cụm được khám phá bởi thuật toán DBSCAN 23 Hình 1.9 Ba tầng liên tiếp của cấu trúc string 26 Hình 2.1 Mô phỏng về tập dữ liệu đơn chiều 37 Hình 2.2 Hàm thuộc với trọng tâm của cụm A trong k-means 37 Hình 2.3 Hàm thuộc với trọng tâm của cụm A trong FCM 38 Hình 2.4 Các cụm khám phá được bởi thuật toán FCM 39 Hình 3.1 Mô hình Diagram CSDL của hệ thống 61 Hình 3.2 Thêm triệu chứng 64 Hình 3.3 Xoá triệu chứng 64 Hình 3.4 Thêm bệnh 65 Hình 3.5 Xoá bệnh 65 Hình 3.6 Mối quan hệ giữa triệu chứng và bệnh 66 Hình 3.7 Chuẩn đoán bệnh 66 Hình 3.8 Vùng Mờ hoá 67 1 MỞ ĐẦU 1. Lý do chọn đề tài Sự phát triển của công nghệ thông tin và việc ứng dụng công nghệ thông tin trong các lĩnh vực đời sống, kinh tế, xã hội trong nhiều năm qua cũng đồng nghĩa với lượng dữ liệu đã được các cơ quan thu thập và lưu trữ ngày một tích lũy nhiều lên. Các công nghệ lưu trữ và phục hồi dữ liệu phát triển một cách nhanh chóng vì thế cơ sở dữ liệu ở các cơ quan, doanh nghiệp ngày càng nhiều thông tin tiềm ẩn phong phú và đa dạng. Mặt khác, trong môi trường cạnh tranh, người ta ngày càng cần có nhiều thông tin với tốc độ nhanh để trợ giúp việc ra quyết định và ngày càng có nhiều câu hỏi mang tính chất định tính cần phải trả lời dựa trên một khối lượng dữ liệu khổng lồ đã có. Để thuận tiện cho việc tra cứu thông tin người ta thường phân cụm các dữ liệu lại với nhau. Phân cụm dữ liệu là một kỹ thuật trong khai phá dữ liệu, 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, quan tâm trong tập dữ liệu lớn, từ đó cung cấp thông tin, tri thức hữu ích cho việc ra quyết định. Phương pháp phân cụm dữ liệu là phân một tập dữ liệu ban đầu thành các cụm dữ liệu có cùng tính chất hay có các tính chất gần giống nhau và mỗi đối tượng dữ liệu chỉ thuộc về một cụm dữ liệu, phương pháp này phù hợp với việc khám phá ra các cụm có mật độ cao và rời nhau, với đường biên giữa các cụm được xác định tốt. Tuy nhiên, trong thực tế, các cụm dữ liệu lại có thể chồng chéo lên nhau, nghĩa là một số các đối tượng dữ liệu thuộc về nhiều cụm khác nhau, do đó mô hình này không mô tả được dữ liệu thực. Chính vì vậy người ta đã áp dụng lý thuyết về tập mờ trong phân cụm dữ liệu để giải quyết cho trường hợp này. Cách thức kết hợp này được gọi là phân cụm mờ. Phân cụm mờ là phương pháp phân cụm dữ liệu mà cho phép mỗi điểm dữ liệu thuộc về hai hoặc nhiều cụm thông qua bậc thành viên. Chính vì lý do đó mà em chọn đề tài “Phân cụm mờ và Ứng dụng phân loại bệnh ” làm đề tài cho luận văn tốt nghiệp thạc sĩ của mình. 2 2. Mục tiêu nghiên cứu - Tìm hiểu các khái niệm cơ bản về phân cụm dữ liệu, kiểu dữ liệu và các thuật toán phân cụm dữ liệu. - Tìm hiểu lý thuyết về phân cụm mờ và các kỹ thuật phân cụm mờ. - Áp dụng thuật toán phân cụm mờ xây dựng ứng dụng phân loại bệnh 3. Đối tượng và phạm vi nghiên cứu Đề tài tập trung đi sâu nghiên cứu về cách xây dựng hệ thống phân cụm dữ liệu theo hướng phân cụm mờ. Hệ thống này được phát triển nhằm phục vụ cho việc phân loại các dữ liệu rõ ràng hơn, tối ưu các dữ liệu được phân cụm. 4. Phương pháp nghiên cứu - Phân tích, nghiên cứu lý thuyết tổng quan về phân cụm dữ liệu rồi từ đó tìm hiểu các phương pháp, kỹ thuật và thuật toán phân cụm dữ liệu mờ. - Xây dựng, cài đặt chương trình ứng dụng. 5. Bố cục của luận văn Ngoài phần mở đầu, kết luận và danh mục tài liệu tham khảo, nội dung luận văn được bố cục làm ba chương chính: Chương 1. Tổng quan về phân cụm dữ liệu: Nêu khái quát về khái niệm, mục tiêu, các kiểu dữ liệu, độ đo dữ liệu và các yêu cầu của phân cum dữ liệu. Trình bày một số ứng dụng, một số kỹ thuật tiếp cận và thuật toán áp dụng trong phân cụm dữ liệu. Chương 2. Kỹ thuật phân cụm dữ liệu mờ: Giới thiệu về phân cụm mờ và trình bày các thuật toán phân cụm mờ. Chương 3. Bài toán ứng dụng phân loại bệnh: Áp dụng thuật toán phân cụm mờ FCM để xây dựng chương trình Phân loại bệnh. 3 Chương 1. PHÂN CỤM DỮ LIỆU 1.1. Khái niệm và mục tiêu của phân cụm dữ liệu 1.1.1. Khái niệm Phân cụm dữ liệu là một kỹ thuật trong khai phá dữ liệu, 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, quan trọng trong tập dữ liệu lớn, từ đó cung cấp thông tin, tri thức hữu ích cho việc ra quyết định. Phân cụm dữ liệu là kỹ thuật sử dụng quan sát đối tượng để nhóm các đối tượng thành các cụm hoặc chia một tập dữ liệu ban đầu thành các cụm sao cho: - Các đối tượng trong cùng một cụm là giống nhau hoặc gần giống nhau được xác định bằng độ tương tự. Hay nói một cách khác, các đối tượng trong cùng một cụm là tương tự với nhau. - Các đối tượng thuộc các cụm khác nhau sẽ không tương tự (phi tương tự) với nhau. Vậy có thể hiểu một cách đơn giản là “Phân cụm là quá trình tổ chức các đối tượng thành các nhóm sao cho các đối tượng trong cùng một nhóm là tương tự với nhau”. Số các cụm được xác định tuỳ thuộc vào phương pháp phân cụm. Các thuật toán phân cụm tìm các nhóm chứa đối tượng tương tự nhau. Hai hay nhiều đối tượng được xếp vào cùng một cụm nếu chúng có chung một định nghĩa về khái niệm hoặc chúng xấp xỉ với các khái niệm được mô tả trước. Một cụm là các đối tượng có thể xem như là một nhóm trong nhiều ứng dụng. Mặt khác, phân cụm là học bằng quan sát hơn là học bằng ví dụ nên còn được gọi là học không giám sát. P h â n c ụ m dữ liệu có ý nghĩa rất quan trọng trong hoạt động của con người. Lúc đầu, chúng ta đã học cách làm thế nào để phân biệt giữa người và vật, giữa động vật và thực vật, giữa cái này và cái kia, ... và liên tục được phân loại rồi đưa vào 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 như: nhận dạng mẫu, phân tích dữ liệu, xử lý ảnh, nghiên 4 cứu thị trường, ... Ngoài ra phân cụm dữ liệu còn có thể được sử dụng như một bước tiền xử lí cho các thuật toán khai phá dữ liệu khác như là phân loại và mô tả đặc điểm, có tác dụng trong việc phát hiện ra các cụm. 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 hoặc là các đối tượng dữ liệu thiếu thông tin về một số thuộc tính nào đó... 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. 1.1.2. Mục tiêu Mục tiêu của phân cụm là xác định được bản chất nhóm trong tập dữ liệu chưa có nhãn để có thể quyết định được cái gì tạo thành một cụm tốt. Nó có thể được chỉ ra rằng không có tiêu chuẩn tuyệt đối tốt mà có thể không phụ thuộc vào kết quả phân cụm. Vì vậy, nó đòi hỏi người sử dụng phải cung cấp tiêu chuẩn này, theo cách mà kết quả phân cụm sẽ đáp ứng yêu cầu. 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 cụm 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 cụm 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. Vì vậy phân cụm dữ liệu vẫn đang là một vấn đề khó và mở, vì phải giải quyết nhiều vấn đề cơ bản một cách trọn vẹn và phù hợp với nhiều dạng dữ liệu khác nhau, đặc biệt là đối với dữ liệu hỗn hợp đang ngày càng tăng 5 trong các hệ quản trị dữ liệu và đây cũng là một trong những thách thức lớn trong lĩnh vực khai phá dữ liệu. 1.2. Các kiểu dữ liệu và độ đo phân loại dữ liệu 1.2.1. Phân loại dữ liệu Cho một cơ sở dữ liệu D có chứa n đối tượng trong không gian k chiều, trong đó x, y, z là các đối tượng thuộc D: x = (x1, x2, .., xk); y = (y1, y2, .., yk); z = (z1, z2, .., zk); Trong đó xi, yi, zi với i= 1, k là các đặc trưng hoặc thuộc tính tương ứng của các đối tượng x, y, z. Sau đây là các kiểu dữ liệu:  Phân loại các kiểu dữ liệu dựa trên kích thước miền - Thuộc tính liên tục (Continuous Attribute): nếu miền giá trị của nó là vô hạn không đếm được - Thuộc tính rời rạc (Discrette Attribute): Nếu miền giá trị của nó là tập hữu hạn, đếm được - Lớp các thuộc tính nhị phân: là trường hợp đặc biệt của thuộc tính rời rạc mà miền giá trị của nó chỉ có 2 phần tử được diễn tả như : Yes/No, True/False hoặc Nam/Nữ, …  Phân loại các kiểu dữ liệu dựa trên hệ đo Giả sử rằng chúng ta có hai đối tượng là x, y và các thuộc tính xi, yi tương ứng với thuộc tính thứ i của chúng. Chúng ta có các lớp kiểu dữ liệu như sau: - Thuộc tính định danh (Nominal Scale): đây là dạng thuộc tính khái quát hoá của thuộc tính nhị phân, trong đó miền giá trị là rời rạc không phân biệt thứ tự và có nhiều hơn hai phần tử, nghĩa là nếu x và y là hai đối tượng thuộc tính thì chỉ có thể xác định là x != y hoặc x = y. 6 - Thuộc tính có thứ tự (Ordinal Scale): là thuộc tính định danh có thêm tính thứ tự, nhưng chúng không được định lượng. Nếu x và y là hai thuộc tính thứ tự thì ta có thể xác định là x != y hoặc x = y hoặc x > y hoặc x < y. - Thuộc tính khoảng (Interval Scale): Với thuộc tính khoảng, chúng ta có thể xác định một thuộc tính là đứng trước hoặc đứng sau thuộc tính khác với một khoảng là bao nhiêu. Nếu xi > yi thì ta nói x cách y một khoảng xi – yi tương ứng với thuộc tính thứ i. - Thuộc tính tỉ lệ (Ratio Scale): là thuộc tính khoảng nhưng được xác định một cách tương đối so với điểm mốc, thí dụ như thuộc tính chiều cao hoặc cân nặng lấy điểm 0 làm mốc. Trong các thuộc tính dữ liệu trình bày ở trên, thuộc tính định danh và thuộc tính có thứ tự gọi chung là thuộc tính hạng mục (Categorical), còn thuộc tính khoảng và thuộc tính tỉ lệ được gọi chung là thuộc tính số (Numeric). 1.2.2. Độ đo phân cụm dữ liệu Để phân cụm, người ta phải xác định "khoảng cách" giữa các đối tượng, hay là phép đo độ tương tự của dữ liệu. Đây là các hàm để đo sự giống nhau giữa các cặp đối tượng dữ liệu. Tthông thường các hàm này hoặc là để tính độ tương tự (Similar) hoặc là tính độ phi tương tự (Dissimilar) giữa các đối tượng dữ liệu [2]. Tất cả các độ đo dưới đây được xác định trong không gian metric. Không gian metric là một tập trong đó có xác định các khoảng cách giữa từng cặp phần tử, với những tính chất thông thường của khoảng cách hình học. Nghĩa là, một tập X (các phần tử của nó có thể là những đối tượng bất kỳ) các đối tượng dữ liệu trong cơ sở dữ liệu D như đã đề cập ở trên được gọi là một không gian metric nếu: - Với mỗi cặp phần tử x, y ϵ X đều có xác định, theo một quy tắc nào đó, một số thực δ(x, y), được gọi là khoảng cách giữa x và y. - Quy tắc nói trên thỏa mãn hệ tính chất sau: + δ(x, y) > 0 nếu x ≠ y; + δ(x, y) = 0 nếu x = y; + δ(x, y) = δ(y,x) với mọi x, y; 7 + δ(x, y) ≤ δ(x, z) + δ(z, y). Hàm δ(x, y) được gọi là một metric của không gian metric. Các phần tử của X được gọi là các điểm của không gian này.  Thuộc tính khoảng: Thuộc tính khoảng là các phép đo liên tục của một tỷ lệ tuyến tính thô. Để chuẩn hoá các phép đo, một lựa chọn đó là chuyển đổi các phép đo gốc sang các biến không đơn vị (unitless). Điều này có thể được biểu diễn như sau: Tính trung bình độ lệch tuyệt đối Sf mf  sf  1 (| x1 f  m f |  | x2 f  m f | ... | xnf  m f |) n Với X1f,...,xnf là n phép đo của f, mf là giá trị đo trung bình của f, tức là 1 ( x1 f  x2 f  ...  xnf ) . n Tính phép đo chuẩn hóa gọi là z-score như sau: zif  xif  m f sf Sau khi chuẩn hoá hay không cần chuẩn hoá trong một số ứng dụng nào đó, ta tính độ đo tương tự giữa 2 đối tượng dữ liệu x, y. Cho trước các biến tỷ lệ khoảng cách, dựa trên khoảng cách giữa từng cặp đối tượng. Các phép đo này bao gồm: - Khoảng cách Minskowski: n d ( x, y )  ( | xi  yi |q ) 1 q i 1 trong đó q là số tự nhiên dương. - Khoảng cách Euclidean : n d ( x, y )   (x  y ) i 2 i i 1 đây là trường hợp đặc biệt của khoảng cách Minskowski trong trường hợp q = 2. - Khoảng cách Manhattan : 8 n d ( x, y )   | xi  yi | i 1 đây là trường hợp đặc biệt của khoảng cách Minskowski trong trường hợp q = 1. - Khoảng cách cực đại : d ( x, y )  Max in1 | xi  yi | đây là trường hợp của khoảng cách Minskowski trong trường hợp q   .  Thuộc tính nhị phân: Một thuộc tính nhị phân chỉ có hai trạng thái 0 hay 1, với 0 là thuộc tính vắng mặt, 1 là thuộc tính có mặt. Một tiếp cận để tính toán ma trận tương tự từ dữ liệu nhị phân đã cho. Nếu tất cả các thuộc tính nhị phân được xem như là có cùng trọng số, ta có bảng 1.1, với a là tổng số các thuộc tính có giá trị bằng 1 cho cả hai đối tượng x và y, b là tổng số các thuộc tính có giá trị bằng 1 cho đối tượng x và 0 cho đối tượng y, c là tổng số các thuộc tính có giá trị bằng 0 cho đối tượng x và 1 cho đối tượng y, d là tổng số các thuộc tính có giá trị bằng 0 cho cả đối tượng x và y. Tổng số lượng của các thuộc tính là p, p = a + b + c + d. Bảng 1.1. Bảng các thuộc tính nhị phân Đối tượng x Đối tượng y 1 0 Tổng 1 a b a+b 0 c d c+d Tổng a+c b+d p Một thuộc tính nhị phân là đối xứng nếu như cả hai trạng thái của nó có cùng trị giá và mang cùng trọng số, do vậy không có sự ưu tiên nên kết quả mã hoá là 0 hay 1. Các phép đo độ tương tự đối với dữ liệu thuộc tính nhị phân được định nghĩa như sau : - Hệ số đối sánh đơn giản d ( x, y )  ad p 9 ở đây cả hai đối tượng x và y có vai trò như nhau, nghĩa là chúng đối xứng và có cùng trọng số. - Hệ số Jacard d ( x, y )  bc abc Công thức tính này được sử dụng trong trường hợp mà trọng số của các thuộc tính có giá trị 1 của đối tượng dữ liệu có cao hơn nhiều so với các thuộc tính có giá trị 0, như vậy các thuộc tính nhị phân ở đây là không đối xứng.  Thuộc tính định danh: Thuộc tính định danh là sự suy rộng của thuộc tính nhị phân, trong đó nó có thể mang nhiều hơn hai trạng thái. Ví dụ, bản đồ màu là một thuộc tính định danh có thể có 5 trạng thái: đỏ, vàng, xanh lá cây, hồng và xanh da trời. Cho số các trạng thái của một thuộc tính định danh là M. Các trạng thái có thể được chỉ ra bởi các ký tự, các biểu tượng hay một tập các số nguyên như 1,2,...,M. Lưu ý rằng các số nguyên như thế này chỉ được dùng cho dữ liệu điều khiển và không đại diện cho bất kỳ một trật tự cụ thể nào. Độ phi tương tự giữa hai đối tượng x và y có thể được định nghĩa như sau: d ( x, y )  pm p trong đó, m là số thuộc tính đối sánh tương ứng trùng nhau, p là tổng số các thuộc tính. Các thuộc tính định danh có thể được mã hoá bởi một số lượng lớn các thuộc tính nhị phân không đối xứng bằng cách tạo một thuộc tính nhị phân mới cho mỗi trạng thái định danh. Đối với một đối tượng với giá trị trạng thái cho trước, thuộc tính nhị phân miêu tả trạng thái đó đặt là 1, trong khi các thuộc tính nhị phân còn lại đặt là 0. Ví dụ, để mã hoá thuộc tính định danh bản đồ màu, một thuộc tính nhị phân có thể được tạo lập cho từng màu trong danh sách 5 màu trên. Cho một đối tượng có màu vàng, thuộc tính vàng đặt là 1, trong khi bốn thuộc tính còn lại đặt là 0.  Thuộc tính có thứ tự 10 Thuộc tính có thứ tự rời rạc tương tự như một thuộc tính định danh, loại trừ M trạng thái của giá trị có thứ tự được sắp xếp theo một trật tự có nghĩa. Các thuộc tính có thứ tự rất hữu ích cho việc thể hiện các đánh giá chất lượng một cách chủ quan mà không thể đo được bằng cách khách quan. Một thuộc tính có thứ tự liên tục trông giống như một tập dữ liệu liên tục với một tỷ lệ chưa biết, đó là mối quan hệ có thứ tự của các giá trị, là yếu tố cần thiết nhưng không phải là tính chất trọng yếu thực sự của chúng. Giả sử i là thuộc tính thứ tự có Mi giá trị (Mi kích thước miền giá trị). Các trạng thái Mi được sắp xếp thứ tự như sau: [1… Mi], chúng ta có thể thay thế mỗi giá trị của thuộc tính bằng giá trị cùng loại ri, với ri ∈ {1… Mi}. Mỗi một thuộc tính có thứ tự có các miền giá trị khác nhau, vì vậy chúng ta chuyển đổi chúng về cùng miền giá trị [0,1] bằng cách thực hiện phép biến đổi sau cho mỗi thuộc tính Zi  ri  1 . M i 1 Sử dụng công thức tính độ tương tự của thuộc tính khoảng đối với các giá trị Zi, đây cũng chính là độ tương tự của thuộc tính có thứ tự.  Thuộc tính tỉ lệ Để tính độ tương tự giữa các thuộc tính tỉ lệ có nhiều cách khác nhau. Một trong những cách đó là sử dụng công thức tính logarit cho mỗi thuộc tính. Hoặc loại bỏ đơn vị đo của các thuộc tính dữ liệu bằng cách chuẩn hóa chúng, hoặc gán trọng số cho mỗi thuộc tính giá trị trung bình, độ lệch chuẩn. Với mỗi thuộc tính dữ liệu đã được gán trọng số tương ứng wi ( 1  i  k ), độ tương đồng dữ liệu được xác định như sau: n d ( x, y )   W (x  y ) i i 2 i i 1 1.3. Các yêu cầu của phân cụm Những yêu cầu cơ bản của phân cụm trong khai phá dữ liệu là:  Có khả năng mở rộng: Nhiều thuật toán phân cụm làm việc tốt với những tập dữ liệu nhỏ chứa ít hơn 200 đối tượng, tuy nhiên, một cơ sở dữ liệu lớn có thể 11 chứa tới hàng triệu đối tượng. Việc phân cụm với một tập dữ liệu lớn có thể làm ảnh hưởng tới kết quả. Vậy làm cách nào để chúng ta có thể phát triển các thuật toán phân cụm có khả năng mở rộng cao đối với các cơ sở dữ liệu lớn?  Khả năng thích nghi với các kiểu thuộc tính khác nhau: Nhiều thuật toán được thiết kế cho việc phân cụm dữ liệu có kiểu khoảng (kiểu số). Tuy nhiên, nhiều ứng dụng có thể đòi hỏi việc phân cụm với nhiều kiểu dữ liệu khác nhau, như kiểu nhị phân, kiểu tường minh (định danh - không thứ tự), và dữ liệu có thứ tự hay dạng hỗn hợp của những kiểu dữ liệu này.  Khám phá các cụm với hình dạng bất kỳ: Nhiều thuật toán phân cụm xác định các cụm dựa trên các phép đo khoảng cách Euclidean và khoảng cách Manhattan. Các thuật toán dựa trên các phép đo như vậy hướng tới việc tìm kiếm các cụm hình cầu với mật độ và kích cỡ tương tự nhau. Tuy nhiên, một cụm có thể có bất kỳ một hình dạng nào. Do đó, việc phát triển các thuật toán có thể khám phá ra các cụm có hình dạng bất kỳ là một việc làm quan trọng.  Tối thiểu lượng tri thức cần cho xác định các tham số đầu vào: Nhiều thuật toán phân cụm yêu cầu người dùng đưa vào những tham số nhất định trong phân tích phân cụm (như số lượng các cụm mong muốn). Kết quả của phân cụm thường khá nhạy cảm với các tham số đầu vào. Nhiều tham số rất khó để xác định, nhất là với các tập dữ liệu có số lượng các đối tượng lớn. Điều này không những gây trở ngại cho người dùng mà còn làm cho khó có thể điều chỉnh được chất lượng của phân cụm.  Khả năng thích nghi với dữ liệu nhiễu: Hầu hết những cơ sở dữ liệu thực đều chứa đựng dữ liệu ngoại lai, dữ liệu lỗi, dữ liệu chưa biết hoặc dữ liệu sai. Một số thuật toán phân cụm nhạy cảm với dữ liệu như vậy và có thể dẫn đến chất lượng phân cụm thấp.  Ít nhạy cảm với thứ tự của các dữ liệu vào: Một số thuật toán phân cụm nhạy cảm với thứ tự của dữ liệu vào, ví dụ như với cùng một tập dữ liệu, khi được đưa ra với các thứ tự khác nhau thì với cùng một thuật toán có thể sinh ra các