Chương 1. PHÂN CỤM DỮ LIỆU 1. Khái niệ và mục tiêu cũa phân cụm đữ li Phân cụm đỡ liệu là một kỹ thuật trong khai phá đỡ liệu, nhằm tìm kiểm, phat hiện các cụm, các mẫu đỡ liệu ty nhiên iềm in, quan trong trong tip dé liệu lồn, từ đồ cong cấp thông tin, tr thức hồu ích cho việc ra quyết định Phin cụm dỡ liệu là kỹ thuật sở đụng quan sắt đổi trợng để nhỏm các đối trong thành các cụm hoặc chỉa một tập dỡ liệu ban đầu thành các cum s4o ch - Các đổi trọng trong cing mét cum là giếng nhau hoặc gẫn giếng nhau được sxc dinh bing 4 tvong ar. Hay nối một cách khác, các đối trợng trong công một cm là ương tr với nhau - Các đối trọng thuộc các cụm khắc nhau sẽ Đông tương tr (plÍ tương t) với nhau.
‘Vay có thể hiểu một cách đơn giãn là “Điển cơn là guá ơình tổ chức các đối tượng thônh các nhôm ao cho các đối trọng trong cùng một nhôm là trơng tự với hau" Số các cụm được xác định tuỹ thuộc vào ghương pháp phân cụm. Các thuật teán phân cụm tim các nhôm chứa đối trọ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 xip xỉ với các khái niệm được mồ tả trước. Một cụm là các đối trợng có thể xem như là một nhôm trong nhiều ứng dụng XMặt khác, phân cơn 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à lọc không giám sie.
Phâncụm dỡ liệu cổ ý nghĩa rất quan trọng trong heạ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 dung như: nhận đạng mẫn, phân tích đỡ liệu, xử ý ảh, nghiền 4 cứu thị trường,.
Ngoài ra phân cụm đỡ 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 r các cụơt Một vẫn đề thường ip trong phân cụm là hầu hết các dữ liệu cần cho phần cum đều cô chứa đỡ liệu nhiễu đo 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ử ỉ đ tệu nhằm khắc phục heặc loi bỏ nhiễu troớc khi chuyển sang giai đoạn phan tich cum dỡ liệu. Nhễu ở đây được hiễu là các đối tượng dỡ liệu không chính xác, không tường mình hoặc là các đối tượng dỡ liệu thiếu thông ti 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ể gỹá trị các thuộc tính cña đối tượng nhiễu b 1g giá trị thuộc tính tương ứng. Ngoàira, dé tim phẫn tử ngoại lại 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 đỡ 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 vỉ hoặc “mô bì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 AMpc tiêu của phân cụm là ắc định được bản chất nhềm tong tập đỡ liệu chưa có nhần để có hễ quyết định được cái sỉ tạo thành một cụm tốt. Nề cổthể được chỉ a 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 cum. Vi vậy, nỗ đồi hỏi người sử dụng phải cung cấp tiêu chuẩn nay, theo cách mã kết quả phân cụm sẽ đáp ting 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 cum tổng quất nào cô th giải quyết trọn ven cho tắt cả các đạ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 cm 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. Vivậy phân cum đỡ 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 dang dữ liệu khác nhau, đặc iệt à đố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ị đỡ liệu và đấy cũng là một trong những thách thức lồn trong Tĩnh vực khai phá đỡ liệu. Các kiểu dữ liệu vàđộ đo phân loại dữ liệu 1. Phân loại đỡ liệu Cho mt co sé di liệu D có chứan đổi tượng trong không gian k chiév, trong đồ x, y, z là các đối tượng thuộc D: (81, 2, RR: = (Vy YH z= (Zi, 22,.
24); Trong 6 x, y, 21 v6i LF là các đặc trơng hoặc thuộc tỉnh trơng ứng của các đối tượng x. y,z Sau đây là các iễu đỡ liệu: -+ Phân loại các kiẫu dữ liệu dự trên kích durớc miễn = Thuộc tỉnh liên tục (Coninuote Atibue):nễu miễn gi tr của nỗ là vô bạn không đêm được ~_ Thuộc tỉnh vồi rạc (Diecrefe Atiöut): Nếu miễn gi ti cba nộ là tập hữu hạn, đếm được ~_ Lập các thuộc tín nhị phẩm: là trường hợp đặc it của thuộc tính rồi rạc mà miền giá tỉ của nỗ chỉ cô 2 phần tử được điễn tả như : Yeo, True False bode Nan’ -+ Phân loại các kẫu đề liệu dự trên hệ đø Giả sử rằng chồng ta cổ hai đổi trợnglàx, ÿ và các thuộctính xi tương ứng ới thuộ tính thứ ¡ côa chúng, Chúng tacó các lớp kiễu dữ liệu chữ sau: = Dhue tn dah dan (Nominal Scale): Sy la dang thuậc tính khấi quit hoa của thuộc tính hi phn, trong đó miễn gi tr a bi rạc không phân iệt thứ tự và có nhiều hơn bai phân tố nghĩa là nếu x và y là hai đối tượng thuộc. tinh hủ cỉ có thể xác định là x 1= hofe x= y 6 ~ Thue tinh c6 thie te (Ordinal Scale): 1a thuéc tính định danh có thêm tinh 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 06 thể xác định là x= ÿ hoặc x hoặc x> y hole x <y = Thuộc tỉnh khoảng (Õeral Soal: Với thuộc tỉnh khoäng, chủng ta cô thể xấc định một thuộc tính là đớng tướ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 tỉ ta nỗi x cảchy một khoảng xi— trơng ứng với thuộc tính thứ ¡ ~_ Thuộc tính tỉ lệ (Âerie Seal): 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í áp như thuộc tính chiều cao hoặc Treng các thuộc tíh dỡ liệu tỉnh bày ở trên, thuậc tính định danh và thuộc tính cổ thử ty goi chung là thuộc tính hạng mục (Catsgorical), còn thuộc tính Xkhoäng và thuộc tính lệ được gọi chung à thuộc tính số (Numeric) 1.
Độ đ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 trợng, hay là phép do 46 trơng tự của dỡ liệu. Day là các hàm để đo sự giống nhau giữa các cặp đối trợng dỡ liên. Trhông thường các hàm này hoặc là để tính độ tương ty (Simila) hoặc tính độ phi tương tự (Diesinila) giữa các đổi trọng đỡ liệu [2] Tất cả các độ đo dưới đầy được xác định trong không gian metic. Không gian metric li 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í 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ủanỗ có thể là những đối tượng bất ỷ) các đối tượng dỡ iệu trong cơ sở điệu D như đã đề cập ở trên được gọi là một không gian metric név: ~_ Với mỗi cặp phần tử x y e X đều cổ xắc định, theo một quy tắc nào đồ, một số thực BỌc y), được gọi là khoảng cách giữa x vay. = Quy tắc nối trên tha mẫn hệ tỉnh chất sa: + Bực x) > 0sểu x#y ~ Bụ, y)~ 0 nấu x + ô(, y) = ð(y.x) với mọi x, ~ Bụ, y) 8£, ø)+ 8, y) Him &(x,y) được gọi là một mteudc cũa không gian metic. Các phinti cia X được gọi là các điểm của không gian nay Thuộc tính khoảng là các phép đo tên tục của một tỷ lệ toyển tỉnh thé. DE 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ị (onides3) Điều này có thể được biễu diễn như sau: “Tính trong bình độ lệch tuyệt đối Sự 20%, — my l*lxy,~m, I*-#lxự —,D Với Xu.xư là n phếp ổo của £ mự là giá tị đo trung bình của £ tóc là mya haem, ttm) Tinh phép đo chuẩn hóa gọi là z-score nb sau: Sau khi chuỗn hoá hay không cần chuẩn hoá trong một số ứng dung nào đồ, ta tính độ đo trong tự giồa 2 đối trợng dữ liệu x, y.
Cho trước các biến lệ khoảng cách, đựa trên khoảng cách gia từng cặp đối trợng. Các phép đo nay bao g6m: = Khong cách Miskowsit: dix) Six -310% trong d6 q lasé tự nhiền đương, = Khodng céch Euclidean đây là trường hop dic biét oa khodng céch Minskowski trong trường hợp q =2. = Khodng cach Mankattan 8 d= Dlx. đây là rường hợp đặc biệt của khoảng cách Minskowsk rong trường hợp q =1 ~_ hoảng cách cực đại icy) = Max’, |x, đây là tường hợp của khoảng cách Minskowrsi trong trường hợpq > 20 > Thuộc tính nhj phan: Xột thuộc tỉnh nhị phân chỉ c bai trạng thấi 0 hay 1, với là thuộc tính ving mặt, 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 cả các thuộc tính nhị phân được xem: nh là có công trong số, ta cổ bằng L1, với a là tổng số các thuộc tính cổ giá tr bằng 1 cho cả bai đối tượng x và y, b là tổng số các thuộc tính có giá t bằng 1 cho đối tượng x và Ú che đối tượng y, c là tổng số các thuộc tính cổ giá tị bằng Ö cho đổi tượng x và 1 cho đi tượng y,đ là tổng số các thuộc tính cổ giátrị bằng 0 cho cả đổi tượng x và y ng số ượng của các thuộc tỉnh làp,p ~ ä~ b >> đ Bing 1.