Tài liệu ứng dụng phương sai trong phân cụm dữ liệu mờ

.. ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG ĐỖ THỊ PHƢƠNG LAN ỨNG DỤNG PHƢƠNG SAI TRONG PHÂN CỤM DỮ LIỆU MỜ 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 Nguyễn Tân Ân THÁI NGUYÊN Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ i LỜI CAM ĐOAN Tôi xin cam đoan kết quả đạt được trong luận văn là sản phẩm cá nhân, không sao chép lại của người khác. Trong toàn bộ nội dung luận văn, những điều được trình bày là của cá nhân hoặc là tổng hợp từ nhiều nguồn tài liệu. Tất cả các tài liệu tham khảo đều có xuất xứ rõ ràng và được trích dẫn hợp pháp. Tôi xin chịu trách nhiệm và mọi hình thức kỷ luật theo quy định cho lời cam đoan của mình. Thái Nguyên, tháng 10 năm 2013 Tác giả luận văn Đỗ Thị Phƣơng Lan Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ ii LỜI CẢM ƠN Em xin chân thành cảm ơn thầy PGS.TS Nguyễn Tân Ân đã tận tình hướng dẫn khoa học và chỉ bảo em hoàn thành tốt luận văn tốt nghiệp này. Em cũng xin bày gửi lời cảm ơn tới các thầy giáo, cô giáo đã chỉ bảo và truyền đạt kiến thức cho em trong suốt quá trình học tập và nghiên cứu. Thái Nguyên, tháng 10 năm 2013 Tác giả luận văn Đỗ Thị Phƣơng Lan Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ iii MỤC LỤC LỜI CAM ĐOAN ......................................................................................... i LỜI CẢM ƠN ............................................................................................... ii MỤC LỤC ................................................................................................... iii DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT.................................. v DANH MỤC CÁC HÌNH .......................................................................... vi DANH MỤC CÁC BẢNG ........................................................................ vii CHƢƠNG 1: BÀI TOÁN PHÂN CỤM DỮ LIỆU ..................................... 3 1.1. Khái quát chung ...................................................................................... 3 1.2. Các kiểu dữ liệu và độ đo khoảng cách .................................................... 5 1.2.1. Các kiểu dữ liệu .................................................................................... 5 1.2.2 . Độ đo tương tự và phi tương tự............................................................ 7 1.2.3. Các biến tỷ lệ khoảng cách ................................................................... 9 1.2.4. Các biến nhị phân ............................................................................... 11 1.2.5. Các biến tên, có thứ tự và dựa trên tỷ lệ .............................................. 14 1.2.6 .Các biến có sự pha trộn của các kiểu .................................................. 16 1.3. Các đặc trưng cơ bản để phân cụm dữ liệu ............................................ 18 1.3.1. Các yêu cầu của phân cụm dữ liệu ...................................................... 18 1.3.2. Các đặc trưng cơ bản để phân cụm dữ liệu ......................................... 20 1.4. Những phương pháp tiếp cận trong phân cụm dữ liệu............................ 21 1.4.1. Phương pháp phân cụm phân hoạch.................................................... 21 1.4.2. Phương pháp phân cụm phân cấp ....................................................... 22 1.4.3. Phương pháp phân cụm dựa trên mật độ ............................................. 24 1.4.4. Phương pháp phân cụm dựa trên mô hình ........................................... 25 1.4.5. Phương pháp phân cụm dựa trên lưới ................................................. 25 1.4.6. Phương pháp phân cụm có dữ liệu ràng buộc ..................................... 26 Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ iv 1.5. Các ứng dụng của phân cụm dữ liệu ...................................................... 28 1.6. Kết luận ................................................................................................. 28 CHƢƠNG 2: ỨNG DỤNG PHƢƠNG SAI TRONG PHÂN CỤM DỮ LIỆU MỜ .................................................................................................... 30 2.1. Thuật toán Fuzzy C-Means chuẩn ......................................................... 30 2.2. Thuật toán Fuzzy C-Means cải tiến ....................................................... 34 2.2.1. Cấu trúc khoảng cách ......................................................................... 34 2.2.2. Thuật toán Fuzzy C-Means cải tiến .................................................... 37 2.3. Kết luận ................................................................................................. 51 CHƢƠNG 3: CHƢƠNG TRÌNH THỰC NGHIỆM ................................ 52 3.1. Giới thiệu bài toán ................................................................................. 52 3.2. Thiết kế chương trình ............................................................................ 55 KẾT LUẬN ................................................................................................. 61 TÀI LIỆU THAM KHẢO.......................................................................... 62 Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ v DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT FCM : Fuzzy C-Means CSDL : Cơ sở dữ liệu PCDL : Phân cụm dữ liệu KPDL : Khai phá dữ liệu Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ vi DANH MỤC CÁC HÌNH Hình 1.1: Ví dụ về phân cụm dữ liệu .............................................................. 3 Hình 1.2: So sánh giữa khoảng cách Euclid và khoảng cách Manhattan ....... 11 Hình 1.3: Các bước trong quá trình phân cụm .............................................. 21 Hình 1.4: các chiến lược phân cụm phân cấp ................................................ 23 Hình 1.5: Các cụm dữ liệu được khám phá bởi Cure .................................... 24 Hình 1.6: Cấu trúc phân cụm dữ liệu dựa trên lưới ....................................... 26 Hình 1.7: Các cách mà các cụm có thể đưa ra............................................... 27 Hình 2.1: Ví dụ thể hiện giới hạn của khoảng cách Euclid trong dựng hình theo hàm Gaussian........................................................................ 36 Hình 2.2: Phân cụm sử dụng thuật toán FCM chuẩn..................................... 48 Hình 2.3: Phân cụm sử dụng thuật toán FCM cải tiến................................... 48 Hình 2.4: Khoảng cách từ mỗi cụm dữ liệu tới các trung tâm cụm sử dụng khoảng cách (2.7) trong trường hợp thuật toán FCM chuẩn với tập hợp ba cụm. 48 Hình 2.5: Khoảng cách từ mỗi cụm dữ liệu tới các trung tâm cụm sử dụng khoảng cách (2.7) trong trường hợp sử dụng thuật toán FCM cải tiến với tập hợp ba cụm ................................................................ 49 Hình 2.6: Khoảng cách từ mỗi cụm dữ liệu tới các trung tâm cụm sử dụng khoảng cách (2.7) trong trường hợp thuật toán FCM chuẩn với tập hợp hai cụm 49 Hình 2.7: Khoảng cách từ mỗi cụm dữ liệu tới các trung tâm cụm sử dụng khoảng cách (2.7) trong trường hợp thuật toán FCM cải tiến với tập hợp hai cụm .................................................................................. 50 Hình 3.1. Gan trong cơ thể người ................................................................. 52 Hình 3.2: Giao diện khi thực hiện chương trình............................................ 57 Hình 3.3: Chức năng thoát khỏi chương trình ............................................... 58 Hình 3.4: Cập nhật danh sách bệnh nhân ...................................................... 58 Hình 3.5: Thiết lập các thông số đầu vào để phân cụm ................................. 58 Hình 3.6: Quá trình phân cụm ...................................................................... 59 Hình 3.7: Kết quả phân cụm ......................................................................... 59 Hình 3.8: Đưa kết quả bài toán ra giấy ......................................................... 60 Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ vii DANH MỤC CÁC BẢNG Bảng 1.1: Bảng ngẫu nhiên cho các biến nhị phân........................................ 12 Bảng 1.2: Bảng quan hệ chứa hầu hết các thuộc tính nhị phân ..................... 13 Bảng 2.1: Thuật toán FCM ........................................................................... 34 Bảng 2.2: Bảng thuật toán FCM cải tiến ....................................................... 46 Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ 1 MỞ ĐẦU Ngày nay, cùng với sự phát triển của công nghệ thông tin thì lượng thông tin mà con người có thể thu thập được ngày càng lớn. Trong những kho dữ liệu khổng lồ ấy đều chứa một kho tàng tri thức quý báu. Con người đã nhận ra điều đó và từ đó cũng là các phương pháp để khai thác dữ liệu đã ra đời. Trong khai phá dữ liệu (KPDL), phân cụm dữ liệu (PCDL) là một kỹ thuật được nghiên cứu mở rộng hiện nay với nhiều khả năng ứng dụng trong thực tế. Phân cụm các đối tượng để các đối tượng trong cùng một cụm sẽ nhận được được sự quan tâm giống nhau, chịu những phương pháp tác động giống nhau. Ví dụ phân cụm các học sinh để các học sinh trong cùng một cụm sẽ nhận được các phương pháp giáo dục như nhau. Phân cụm các ngân hàng để các ngân hàng trong cùng một cụm sẽ nhận được sự đầu tư giống nhau… Như vậy, phân cụm là một việc khó. Mỗi đối tượng tham gia vào quá trình phân cụm thường được đặc trưng bởi nhiều thuộc tính. Dựa vào giá trị của các thuộc tính đó, qua những phương pháp thích hợp, người ta chia các đối tượng này vào các cụm khác nhau sao cho hai đối tượng trong cùng một cụm phải giống nhau hơn một đối tượng ở cụm này so với một đối tượng ở cụm khác. Trong phân cụm việc xác định mức độ giống nhau giữa hai đối tượng có ảnh hưởng lớn tới chất lượng phân cụm. Trong trường hợp mỗi đối tượng được biểu diễn bởi nhiều thuộc tính, một số thuộc tính đó lại là thuộc tính mờ, việc biểu diễn các đối tượng, việc xác định độ giống nhau giữa các đối tượng rất phức tạp. Khi đó hệ thống phân cụm phải là hệ thống xử lý các tín hiệu mờ. Đã có nhiều phương pháp PCDL, tuy nhiên không có phương pháp nào đủ tổng quát để mang lại hiệu quả tốt nhất cho mọi trường hợp. Do tầm quan Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ 2 trọng của phân cụm, hiện nay người ta vẫn đang tìm kiếm các phương pháp phân cụm mới hoặc cải thiện những phương pháp phân cụm đã có nhằm nâng cao hiệu quả của phân cụm. Luận văn trình bày một số vấn đề về PCDL - đây là một trong những kỹ thuật cơ bản để KPDL. Đây là một hướng nghiên cứu có triển vọng và chỉ ra những sơ lược trong việc tìm hiểu và khai thác các thông tin hữu ích còn tiềm ẩn và hiểu được ý nghĩa thực tiễn của dữ liệu. Trong khuôn khổ của luận văn thạc sỹ, tôi chọn đề tài: “Ứng dụng phương sai trong phân cụm dữ liệu mờ” nhằm kết hợp giữa việc phân cụm với lý thuyết xác suất nhằm nâng cao hiệu quả của phân cụm. Luận văn được trình bày trong 3 chương: Chƣơng 1: Trình bày tổng quan về bài toán PCDL, các kiểu dữ liệu và một số kỹ thuật tiếp cận trong PCDL. Qua đó ta thấy đƣợc ứng dụng của PCDL trong hoạt động đời sống xã hội; Chƣơng 2: Giới thiệu, phân tích và đánh giá thuật toán Fuzzy CMeans (FCM) chuẩn và thuật toán FCM cải tiến; Chƣơng 3: Demo chƣơng trình thử nghiệm. Kết luận: Tóm lược các vấn đề tìm hiểu trong luận văn và các vấn đề liên quan trong luận văn, đưa ra phương hướng nghiên cứu tiếp theo. Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ 3 CHƢƠNG 1: BÀI TOÁN PHÂN CỤM DỮ LIỆU 1.1. Khái quát chung Khái niệm về khai phá dữ liệu (Data Mining) hay phát hiện tri thức (Knowledge Discovery) có rất nhiều cách diễn đạt khác nhau nhưng về bản chất đó là quá trình tự động trích xuất thông tin có giá trị (thông tin dự đoán - Predictive Information) ẩn chứa trong khối lượng dữ liệu khổng lồ trong thực tế[4]. Trong KPDL thì phân cụm là một trong các phương pháp quan trọng trong quá trình khai thác dữ liệu[2]. Chưa có một khái niệm cụ thể nào về phân cụm nhưng có thể hiểu rằng phân cụm dữ liệu hay phân cụm, cũng có thể được gọi là phân tích cụm, phân tích phân đoạn, phân tích phân loại, là quá trình nhóm một tập các đối tượng tương tự nhau trong một tập dữ liệu vào với cụm sao cho hai đối tượng cùng một cụm là tương tự nhau hơn một đối tượng ở cụm này so với một đối tượng ở cụm khác. PCDL là một ví dụ của phương pháp học không có thầy. Không giống như việc phân lớp dữ liệu, PCDL không đòi hỏi phải định nghĩa trước các mẫu dữ liệu huấn luyện. Vì thế, có thể coi PCDL là một cách học bằng quan sát, trong khi phân lớp dữ liệu là cách học bằng các ví dụ... Ngoài ra PCDL còn có thể được sử dụng như một bước tiền xử lý cho các thuật toán KPDL 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. Hình 1.1: Ví dụ về phân cụm dữ liệu Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ 4 Phân cụm có ý nghĩa rất quan trọng trong hoạt động của con người. Trong cuộc sống hằng ngày chúng ta luôn gặp những bài toán phân cụm. Chẳng hạn như trong ngành bưu điện, hàng ngày bưu điện phải phân loại thư theo mã nước, trong mã nước lại phân loại theo mã tỉnh/thành phố. Sau đó khi thư về đến bưu điện tỉnh thì bưu điện tỉnh lại phải phân loại thư theo quận/huyện để gửi đi, đến bưu điện quận/huyện lại phân loại thư theo xã/phường để gửi thư. Đó chính là một ứng dụng của bài toán phân cụm dữ liệu rõ. Nhưng trên thực tế không phải lúc nào bài toán phân cụm dữ liệu rõ được áp dụng. Ví dụ, theo khảo sát trên thị trường thì những người dùng điện thoại đắt tiền là những người có tiền, những người dùng điện thoại rẻ tiền là những người ít tiền. Vậy những người vừa dùng điện thoại nhiều tiền, vừa dùng điện thoại ít tiền thì là người có nhiều tiền hay ít tiền?! Từ bài toán đó con người chúng ta đã đưa vào khái niệm bài toán phân cụm dữ liệu mờ. Phân cụm được sử dụng rộng rãi trong nhiều lĩnh vực như nhận dạng mẫu, phân tích dữ liệu, xử lý ảnh, nghiên cứu thị trường,... Là một chức năng trong KPDL, phân tích phân cụm đượ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 PCDL là hầu hết các dữ liệu cần cho phân cụm đều có chứa quá nhiều dữ liệu nhiễu do quá trình thu thập thiếu chính xác hoặc không đầ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ó thể đượ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 khuyết thiếu thông tin về một thuộc tính, hoặc các phần tử ngoại lai,... Một trong các kỹ thuật xử lý nhiễu phổ biến là việc thay thế giá trị của các thuộc tính của đối Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ 5 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ó 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 CSDL, 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. 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. Nhưng để có thể quyết định được những dữ liệu nào tạo thành một cụm thì có thể chỉ ra rằng không có 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 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 được trọn vẹn cho tất cả các dạng cấu trúc 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ủa các loại dữ liệu, với mỗi cách thức biểu diễn khác nhau thì sẽ có tương ứng một thuật toán phân cụm phù hợp. Vì vậy PCDL vẫn đang là một vấn đề khó và mờ, vì nó 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 lên 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 KPDL. 1.2. Các kiểu dữ liệu và độ đo khoảng cách 1.2.1. Các kiểu dữ liệu Cho một CSDL D chứa n đối tượng trong không gian n chiều trong đó x, y, z là các đối tượng thuộc D sao cho 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. Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ 6 Để phân loại các kiểu dữ liệu ta có thể: + Phân loại dựa trên kích thước miền (Domain Size):  Thuộc tính liên tục: nghĩa là giữa hai giá trị tồn tại vô số giá trị khác. Ví dụ như các thuộc tính về màu, nhiệt độ hoặc cường độ âm thanh.  Thuộc tính rời rạc: nghĩa là nếu miền giá trị của nó là tập hữu hạn, đếm được. Ví dụ như các thuộc tính về số thành viên trong một gia đình,…  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 hoặc False/True,… + Phân loại dựa trên hệ đo(Measurement Scale):  Thuộc tính định danh: đây là dạng thuộc tính khái quát hóa các 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. Ví dụ như thuộc tính nơi sinh của một người.  Thuộc tính có thứ tự: 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. Ví dụ như kết quả xếp loại đua xe ô tô công thức.  Thuộc tính khoảng: 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. Ví dụ như thuộc tính số kênh trên truyền hình.  Thuộc tính tỷ lệ: 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. Ví dụ như thuộc tính chiều cao và 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 thứ tự gọi chung là thuộc tính hạng mục; thuộc tính khoảng và thuộc tính tỷ lệ gọi chung là thuộc tính số. Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ 7 1.2.2 . Độ đo tương tự và phi tương tự Ứng với mỗi kiểu dữ liệu thì có một hàm tính độ đo tương tự để xác định khoảng cách giữa hai phần tử của cùng một kiểu dữ liệu. Và để phân cụm, người ta phải đi tìm cách thích hợp nào đó để xác định “khoảng cách” giữa các đối tượng, hay chính là phép đo tương tự dữ liệu. Đây chính là các hàm để so sánh sự giống nhau giữa các cặp đối tượng dữ liệu, thông thường các hàm này hoặc là để tính độ tương tự (Similar) hoặc tính độ phi tương tự (Dissimilar) giữa các đối tượng dữ liệu. Theo quy ước, giá trị của hàm tính độ đo tương tự càng lớn thì sự tương đồng giữa các đối tượng càng lớn và ngược lại. Hàm tính độ đo phi tương tự tỉ lệ nghịch với hàm tính độ đo tương tự. Tất cả các độ đo dưới đây được xác định trong không gian metric. Một 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. Bất kỳ một không gian metric nào cũng là một độ đo nhưng ngược lại thì không đúng. Độ đo ở đây có thể là tương tự hoặc phi tương tự. Nghĩa là với 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 CSDL 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ử i, j thuộc X đều có xác định theo một quy tắc nào đó, một số thực , được gọi là khoảng cách giữa x và y. + Quy tắc trên thỏa mãn hệ tính các yêu cầu toán học của một hàm khoảng cách:  d(i,j) ≥ 0 cho biết khoảng cách là một số không âm  d(i,i) = 0 cho biết khoảng cách của một đối tượng tới chính nó thì bằng 0  d(i,j) = d(j,i) cho biết khoảng cách là một hàm đối xứng  d(i,j) ≤ d(i,h) + d(h,j) bất đẳng thức tam giác này cho biết khoảng cách trực tiếp từ i tới j không lớn hơn khoảng cách đi theo đường vòng qua bất kỳ một điểm h nào. Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ 8 Hàm được đo bởi sự giống nhau hay độ tương tự nhau giữa c đối tượng i và j. Như vậy thì, phép đo trong phân cụm được dùng để đo chất lượng của phân cụm. Độ tương tự d(i,j) là một số không âm, nó gần bằng 0 khi i, j gần nhau và sẽ lớn hơn khi chúng khác biệt nhau nhiều hơn. Độ tượng tự có được bằng các đánh giá chủ quan đơn giản bởi một tập các quan sát viên hay các chuyên gia trên các đối tượng khác nhau nào đó. Độ tượng tự được tính toán từ các hệ số tương quan. Cho trước n đối tượng để phân cụm, tương quan giữa hai biến f và g được định nghĩa trong (1.1), tại đó f và g là các biến mô tả các đối tượng, mf và mg là các giá trị trung bình của f và g và xif là giá trị của f cho đối tượng thứ i, xig là giá trị của g cho đối tượng thứ i. Công thức chuyển đổi (1.2) được dùng để tính hệ số tương tự d(f,g) từ các hệ số tương quan R(f,g): Các biến với một tương quan dương cao sẽ ấn định hệ số tương tự gần bằng 0. Các biến với một tương quan âm mạnh sẽ ấn định hệ số không tương tự gần bằng 1 (nghĩa là các biến rất khác nhau). Trong nhiều ứng dụng, người dùng thích dùng công thức chuyển đổi (1.3) hơn, tại đó các biến với tương quan âm hay dương cao ấn định cùng một giá trị tương đồng cao. Người dùng có thể sử dụng hệ số không tương đồng s(i,j) thay cho hệ số không tương đồng. Công thức (1.4) được dùng để chuyển đổi giữa hai hệ số. Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ 9 Lưu ý rằng không phải tất cả các biến đều cần trong phép phân tích cụm. Một biến là vô nghĩa với một phân cụm cho trước thì tính hữu ích sẽ ít hơn, do vậy nó ẩn đi thông tin hữu ích đã cung cấp bởi các biến khác. Ví dụ, số điện thoại của một người thường vô ích trong phân cụm người theo mô tả về họ như tuổi, chiều cao, cân nặng,... Kiểu biến "rác" như vậy nên có trọng số 0, trừ khi nó được phép phân cụm xử lý. 1.2.3. Các biến tỷ lệ khoảng cách Tất cả các độ đo dưới đây được xác định trong không gian metric. Một 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. Bất kỳ một không gian metric nào cũng là một độ đo nhưng ngược lại thì không đúng. Độ đo ở đây có thể là tương tự hoặc phi tương tự. Các phép đo này bao gồm các khoảng cách Euclidean, Mahattan và Minkowski. Các mẫu điển hình như trọng lượng và chiều cao, sự kết hợp vĩ độ và kinh độ và nhiệt độ khí hậu. Đơn vị phép đo đã dùng có thể ảnh hưởng đến phép phân cụm. Ví dụ, thay đổi các đơn vị đo, như thay đổi từ meter tới inch cho chiều cao hay từ kilogram tới pound cho trọng lượng, có thể dẫn tới một cấu trúc phân cụm rất khác biệt. Nhìn chung, biểu diễn một biến dưới các đơn vị nhỏ hơn sẽ dẫn tới một phạm vi lớn hơn cho biến đó và do vậy một hiệu ứng lớn hơn trên kết quả cấu trúc phân cụm. Để tránh sự phụ thuộc vào việc lựa chọn đơn vị đo, dữ liệu nên được chuẩn hoá. Chuẩn hoá các phép đo cố gắng mang lại cho tất cả các biến một trọng số như nhau. Tuy nhiên, trong nhiều ứng dụng người ta có thể cố ý muốn mang tới trọng số lớn hơn cho một tập các biến nào đó so với các biến khác. Ví dụ, khi phân cụm các cầu thủ chơi bóng rổ người ta có thể thích mang tới trọng số hơn cho biến chiều cao. Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ 10 Để 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ị. Cho trước các phép đo đối với biến f. Điều này có thể được biểu diễn như sau: - Tính trung bình độ lệch tuyệt đối sf với x1f ,..., xnf là n phép đo của f, mf là giá trị trung bình của f, tức là - Tính phép đo chuẩn hóa, gọi là chỉ số Z (z-score: số đo độ rủi ro)như sau: Thuận lợi của việc sử dụng độ lệch tuyệt đối trung bình đó là z-scores của các phần tử ngoại lai không trở nên quá nhỏ, do vậy các phần tử ngoại lai vẫn dễ nhận thấy. Tuy nhiên lựa chọn việc chuẩn hoá và biểu diễn chuẩn hoá như thế nào là thuộc về phía người dùng. 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 độ tương tự (hay không tươn gtự) giữa các đối tượng. 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ó một số tiếp cận để định nghĩa khoảng cách giữa các đối tượng. Phép đo khoảng cách phổ biến nhất là khoảng cách Euclidean, nó được định nghĩa như sau: với i = (xi1, xi2,..., xip) và j =(xj1,xj2,...,xjp) là hai đối tượng dữ liệu p chiều. Trong không gian metric vẫn thường dùng khoảng cách Mahattan: Cả khoảng cách Euclidean và khoảng cách Mahattan thoả các yêu cầu toán học của một hàm khoảng cách. Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ 11 Khoảng cách Minkowski là tổng quát hoá của cả hai khoảng cách Euclidean và Mahattan. Nó được định nghĩa như sau: với q là một số nguyên dương, nó đại diện cho khoảng cách Mahattan khi q = 1 và Euclidean khi q = 2. Nếu mỗi biến được ấn định một trọng số theo độ quan trọng nhận biết của nó, khoảng cách Euclidean được đánh trọng số có thể được tính như sau: Các trọng số cũng được áp dụng cho khoảng cách Mahattan và Minkowski. Dưới đây là ví dụ về việc so sánh giữa khoảng cách Euclid và khoảng cách Manhattan trong việc tính khoảng cách giữa hai điểm trong hệ tọa độ Oxy giữa hai điểm P1có tọa độ (x1, y1) và điểm P2 có tọa độ (x2, y2). Các đường mầu đỏ, xanh lam, vàng biểu diễn khoảng cách Manhattan có cùng độ dài là 12, trong khi đường mầu xanh lục biểu diễn khoảng cách Euclid với độ dài 6×√2 ≈ 8.48[12]. Hình 1.2: So sánh giữa khoảng cách Euclid và khoảng cách Manhattan 1.2.4. Các biến nhị phân Một biến nhị phân chỉ có hai trạng thái 0 hay 1 với 0 là biến vắng mặt 1 là biến có mặt. Cho trước biến hút thuốc mô tả một bệnh nhân, ví dụ: 1 chỉ rằng bệnh nhân hút thuốc và 0 cho biết bệnh nhân không hút thuốc. Xử lý các Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ 12 biến nhị phân giống như các biến tỷ lệ khoảng cách có thể dẫn tới sự sai lệch các kết quả phân cụm. Bởi vậy, các phương pháp chỉ định cho dữ liệu nhị phân cần phải tính toán độ tương tự. Nếu tất cả các biến nhị phân được xem như là có cùng trọng số, ta có bảng ngẫu nhiên 2 x 2, bảng 1.1, với a là số các biến bằng 1 cho cả hai đối tượng i và j, b là số các biến bằng 1 cho đối tượng i và 0 cho đối tượng j, c là số các biến bằng 0 cho đối tượng i và 1 cho đối tượng j, d là số các biến bằng 0 cho cả đối tượng i và j. Tổng số lượng của các biến là p, p = a + b + c + d. Bảng 1.1: Bảng ngẫu nhiên cho các biến nhị phân j=0 j=1 Tổng i=1 b a a+b i=0 d c c+d Tổng b+d a+c p Một biến 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. Ví dụ, giới tính có thể là nam hay nữ. Độ tương đồng dựa trên các biến nhị phân đối xứng được gọi là độ tương đồng bất biến trong đó kết quả không thay đổi khi một số hay tất cả các biến nhị phân được mã hoá khác nhau. Đối với các độ đo tương đồng bất biến, hệ số được biết đến nhiều nhất là hệ số đối sánh đơn giản được định nghĩa trong (1.11). Một biến nhị phân là không đối xứng nếu như kết quả của các trạng thái quan trọng không bằng nhau. Ta sẽ mã hoá như sau: kết quả có tầm quan trọng nhất là 1 (ví dụ dương tính HIV) và những cái còn lại bằng 0 (ví dụ như âm tính HIV). Độ tương đồng dựa trên các biến đó được gọi là độ tương đồng không bất biến. Đối với các độ tương đồng không bất biến, hệ số được biết Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/