Mối liên quan giữa khái niệm tính bao đóng bắc cầu Min - Max với thuật toán phân cụm theo khoảng cách độ đo

JOURNAL OF SCIENCE OF HNUE Natural Sci., 2014, Vol. 59, No. 4, pp. 96-105 This paper is available online at MỐI LIÊN QUAN GIỮA KHÁI NIỆM TÍNH BAO ĐÓNG BẮC CẦUMIN - MAX VỚI THUẬT TOÁN PHÂN CỤM THEO KHOẢNG CÁCH ĐỘ ĐO Phạm Thanh Huyền Bộ môn Tin học, Khoa Tự nhiên, Trường Cao Đẳng Sư phạm Quảng Ninh Tóm tắt. Điểm giống nhau mà hầu hết các thuật toán phân cụm theo độ đo khoảng cách (thuật toán k-means, thuật toán c-means) là đều phụ thuộc vào khả năng chọn số cụm và tập tâm cụm ban đầu. Điều này ảnh hưởng lớn đến hiệu quả thực hiện của thuật toán, thậm chí dẫn đến kết quả thu được không có chất lượng. Trong bài báo này, chúng tôi xây dựng thuật toán phân cụm dựa vào khoảng cách Min - Max (tạm đặt tên là thuật toán phân cụm theo khoảng cách Min - Max). Thuật toán này được đảm bảo hiệu quả dựa vào tính chất độ đo khoảng cách Euclide (hoặc khoảng cách Hamming) và vận dụng khái niệm tính bao đóng Min - Max. Nói cách khác, chúng tôi đề xuất xây dựng thuật toán phân cụm theo khoảng cách Min - Max không phụ thuộc vào việc lựa chọn trước tập tâm cụm mà chỉ phụ thuộc vào n đối tượng cần phân cụm và việc xác định độ đo giữa các đối tượng đó. Từ khóa: Phân cụm, độ đo khoảng cách, bao đóng Min - Max 1. Mở đầu Phân cụm (Clustering) là sắp xếp các đối tượng theo từng cụm dữ liệu tự nhiên, tức là số lượng và tên cụm chưa được biết trước. Các đối tượng được gom cụm sao cho mức độ tượng tự giữa các đối tượng trong cùng một cụm là lớn nhất và mức độ tương tự giữa các đối tượng nằm trong các cụm khác nhau là nhỏ nhất. 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 cứu vũ trụ, nén ảnh và phân khúc ảnh. Trong thực tế, người ta đã áp dụng lí thuyết tập mờ trong phân cụm dữ liệu để giải quyết những kiểu đối tượng này [2]. Phân cụm phân tích các đối tượng dữ liệu khi chưa biết nhãn của lớp. Nhãn của các lớp không tồn tại trong suốt quá trình huấn luyện dữ liệu. Việc phân cụm sẽ xác định nhãn của lớp. Mỗi cụm được tạo thành có thể xem như một lớp đối tượng có cùng quy tắc tạo ra nó. Do đó, để giải được bài toán phân cụm việc cuối cùng phải xác định được bản chất nhóm đối tượng trong tập dữ liệu chưa có nhãn. Tuy nhiên, việc giải bài toán này vẫn đang Ngày nhận bài: 25/4/2014. Ngày nhận đăng: 21/5/2014. Tác giả liên lạc: Phạm Thanh Huyền, địa chỉ e-mail: phamthanhhuyen34@gmail.com. 96 Mối liên quan giữa khái niệm tính bao đóng bắc cầu Min - Max với thuật toán... còn là 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 trong các hệ quản trị dữ liệu. Một số yếu tố cần quan tâm của bài toán phân cụm đó là nhạy cảm với các kiểu dữ liệu khác nhau, có khả năng mở rộng, hình dạng các cụm không ấn định, dễ bị ảnh hưởng của các kết quả dữ liệu nhiễu. Trong lí thuyết quan hệ mờ, khái niệm bao đóng bắc cầu Min - Max và quan hệ bất tương đương đã được [2] nêu là căn cứ để phân cụm dữ liệu. Trong [3] có chỉ rõ khả năng ứng dụng các khái niệm này trong phân cụm nhưng chưa trình bày tường minh các bước giải thuật phân cụm. Từ ý tưởng muốn có một thuật toán phân cụm không phụ thuộc vào việc lựa chọn trước tập tâm cụm (dữ liệu đầu vào) mà chỉ phụ thuộc vào n đối tượng cần phân cụm và việc xác định độ đo giữa các đối tượng đó, chúng tôi đề xuất bổ sung thêm ràng buộc về quan hệ bất tương đương, tính chất bao đóng bắc cầu để đảm bảo tính hiệu quả của thuật toán và tường mình các bước thực hiện phân cụm dữ liệu mà trong [2, 3] chưa trình bày. Trong nội dung của bài viết này, chúng tôi trình bày một số khái niệm lí thuyết về quan hệ mờ quan trọng; chỉ ra có thể vận dụng tính chất của nó để đề xuất thuật toán phân cụm theo khoảng cách độ đo và tiến hành triển khai tường minh các bước giải thuật phân cụm theo khoảng cách độ đo. Ở đây, chúng tôi không chỉ xác định được tính dừng của giải thuật mà còn chứng minh được những căn cứ đúng đắn về xây dựng hệ tiêu chuẩn trên cơ sở lí thuyết quan hệ mờ. 2. Nội dung nghiên cứu 2.1. Cơ sở lí thuyết về quan hệ mờ Trong số những khái niệm mờ quan trọng nhất về phương diện ứng dụng có thể có, các quan hệ mờ mở rộng khái niệm quan hệ cổ điển được định nghĩa trên các tập dữ liệu. Chúng làm nổi bật những mối liên kết không chính xác hay có cấp độ giữa các phần tử của cùng một tập hợp giúp cho việc tổ chức, phân loại dữ liệu hiệu quả hơn [4]. * Định nghĩa các quan hệ mờ Định nghĩa một quan hệ mờ R: Một quan hệ mờ R giữa r tập tham chiếu X1, X2, . . . , Xr là một tập con mờ của X1 X2  . . . Xr với hàm thuộc µR. Nghịch đảo của một quan hệ mờ R giữa X và Y là quan hệ mờ R−1 giữa Y và X được định nghĩa: 8y 2 Y,8x 2 X,µR 1(y, x) = µR(x, y) * Hợp thành mờ Hợp thành của hai quan hệ mờ R1 trênX Y và R2 trên Y Z xác định một quan hệ mờ R = R1 ◦R2 trên X  Z có hàm thuộc được định nghĩa bởi: 8(x, z) 2 X  Z, µR(x, z) = Maxy[min(µR1(x, y), µR2(y, z))] Định nghĩa này tương ứng với hợp thành Max - Min. Ta còn có định nghĩa hợp thành Min - Max như sau [2]: Hợp thành của hai quan hệ mờ R1 trên X  Y và R2 trên 97 Phạm Thanh Huyền Y Z xác định một quan hệ mờ R = R1 R2 trênX Z có hàm thuộc được định nghĩa: 8(x, z) 2 X  Z, µR(x, z) = Miny[Max(µR1(x, y), µR2(y, z))] * Quan hệ hai ngôi mờ  Các tính chất đặc biệt Quan hệ nhị phân mờ R trên X được định nghĩa: - Đối xứng nếu nghiệm đúng: 8(x, y) 2 X X,µR(x, y) = µR(y, x). - Phản xạ nếu nghiệm đúng: 8x 2 X,µR(x, x) = 1. - Bắc cầu nếu nghiệm đúng: R ◦R  R. - Bắc cầu Max - Min nếu ta dùng hợp thành Max - Min của các quan hệ mờ: 8(x, z) 2 X X,µR(x, z)  supy 2 XMin(µR(x, y), µR(y, z)) - Phản xứng nếu nghiệm đúng: 8(x, y) 2 X X, (µR(x, y) > 0vµR(y, x) > 0)) x = y Khi X hữu hạn, ta thấy: + Tính đối xứng của quan hệ mờ R tương ứng với tính đối xứng của ma trậnM(R) + Tính phản xạ của quan hệ R tương ứng với một đường chéo bằng 1 của ma trận M(R) + Tính bắc cầu dễ kiểm tra vì khi đó các phần tử của ma trận M(R) phải lớn hơn hay bằng các phần tử tương ứng của ma trậnM(R ◦R) + Tính phản xứng của quan hệ R thoả mãn nếu ma trậnM(R) là tam giác.  Các hình thái của tính chất bắc cầu Tính chất bắc cầu Max - Min: Cho một quan hệ R xác định trên X X . Lập hợp thành Max - Min R2 = R ◦R Nếu R2 = R ◦R  R thì quan hệ R gọi là có tính bắc cầu Max - Min. Tính chất bắc cầu Max - tích: Nếu hợp thành Max - tích thoả mãn điều kiện R.R  R thì quan hệ R gọi là có tính bắc cầu Max - tích. Tính chất bắc cầuMin - Max: Nếu hợp thànhMin - Max thoả mãn điều kiệnRR  R thì quan hệ R gọi là có tính chất bắc cầu Min - Max. Quan hệ mờ có các tính chất của tập mờ. Ngoài ra, từ tính hợp thành Max - Min và Min -Max, ta có thể thấy một số tính chất của quan hệ mờ. Chẳng hạn, tính chất kết hợp của quan hệ mờ: Cho các quan hệ mờ R1, R2, R3, khi đó: (R1 ◦R2) ◦R3 = R1 ◦(R2 ◦R3) Tính chất đối ngẫu của quan hệ mờ nói lên mối quan hệ giữa phép hợp thành Max - Min và phép hợp thành Min - Max được thể hiện như sau [3]: R ◦R = R R Đây là hai tính chất có tác dụng làm giảm độ phức tạp tính toán cũng như khối lượng thông tin cần lưu trữ trong quá trình phân lớp, phân cụm dữ liệu. 98 Mối liên quan giữa khái niệm tính bao đóng bắc cầu Min - Max với thuật toán...  Bao đóng bắc cầu của một quan hệ hai ngôi mờ Định nghĩa bao đóng bắc cầuMax - Min [3]: Cho một quan hệ mờR. Quan hệ dạng: ∧ R = R [R2 [R3 [ . . . , R2 = R ◦R,R3 = R2◦R... gọi là bao đóng bắc cầu Max - Min của quan hệ R. Định lí: Bao đóng bắc cầu Max - Min ∧ R có tính chất bắc cầu Max - Min: ∧◦ R ∧ R  ∧ R Định lí này đã được chứng minh [3]. Ngoài ra, với hệ quy chiếu hữu hạn, card X = n, thì có thể tìm được một k n sao cho: ∧ R = R [R2 [R3... [Rk′′ . Định nghĩa bao đóng bắc cầu Min - Max: Cho một quan hệ mờ R. Quan hệ dạng: ∨ R = R \ (R R) \ (R R R) \ ... gọi là bao đóng bắc cầu Min - Max của quan hệ R. * Quan hệ tương đương và quan hệ bất tương đương mờ - Quan hệ tương đương mờ Một quan hệ tương đương là một quan hệ mờ đối xứng, phản xạ và bắc cầu Max - Min [5]. Theo định nghĩa, một quan hệ tương đương mờ R trên tập tích X  X phải có 3 tính chất sau: Tính phản xạ: R(x, x) = 1, với mọi x 2 X; Tính đối xứng: R(x, y) = R(y, x), với mọi cặp (x, y) 2 X X; Tính bắc cầu Max - Min: R ◦R  R. - Quan hệ bất tương đương mờ Một quan hệ bất tương đương là một quan hệ mờ có tính chất đối xứng, phản - phản xạ và bắc cầu Min - Max [4]. Một quan hệ bất tương đương mờ R trên tập tích X  X phải có 3 tính chất sau: Tính phản - phản xạ: R(x, x) = 0,8x 2 X; Tính đối xứng: R(x, y) = R(y, x), với mọi cặp (x, y) 2 X X; Tính bắc cầu Min - Max: R R  R. Định lí: Nếu R là một quan hệ tương đương mờ thì R sẽ là một quan hệ bất tương đương mờ và ngược lại: R ◦R  R, R R  R. Định lí này đã được chứng minh [3]. 2.2. Thuật toán phân cụm theo độ đo Min - Max 2.2.1. Thuật toán phân cụm Min - Max Yếu tố thúc đẩy việc đề xuất ý tưởng xây dựng thuật toán phân cụm Min - Max: - Dựa trên các tính chất của khoảng cách Euclide (khoảng cách Hamming), ta có thể vận dụng để biến đổi khoảng cách giữa các phần dữ liệu mờ. Đối với những dữ liệu chính xác (không có tính mờ), thông qua chuyển đổi về dạng dữ liệu mờ, ta hoàn toàn áp dụng được các tính chất này. - Tính chất của bao đóng bắc cầu Min - Max cho phép xác định tính hữu hạn cho vòng lặp. Thuật toán phân cụm Min - Max được đề xuất không phụ thuộc vào việc lựa chọn trước tập tâm cụm (hay trong thuật toán này tạm gọi là hệ tiêu chuẩn) đầu vào mà chỉ phụ 99 Phạm Thanh Huyền thuộc vào n đối tượng cần phân cụm và việc xác định độ đo giữa các đối tượng đó. Đầu vào: n đối tượng với m thuộc tính Xi = xi1, xi2, .., xim(0  i  n) Đầu ra: Các phân cụm Các bước tiến hành thuật toán: Bước 1: Mỗi đối tượng tham gia phân cụm được đánh giá đầy đủ các thuộc tính bằng số mờ biểu thị bởi hàm thuộc (do các chuyên gia đánh giá). Bước 2: Tính khoảng cách mờ giữa các đối tượng (từ công thức tính khoảng cách Euclide tương đối hoặc khoảng cách Hamming tương đối). Ta được một quan hệ bất tương đương mờ D. Bước 3: Tính bao đóng bắc cầu Min - Max ∨ R đối với quan hệ mờ (xác định ở bước 2). Việc tính bao đóng dừng khi tìm được k(k  n) thoả mãn ma trận quan hệDk = Dk+1. Bước 4: Xác định hệ tiêu chuẩn từ các giá trị khoảng cách thu được bởi ∨ R. Phân tích ∨ R thành các cụm dựa trên các tiêu chuẩn đó. 2.2.2. Áp dụng tính chất bao đóng bắc cầu trong giải quyết thuật toán phân cụm Từ việc nghiên cứu các hình thái của tính chất bắc cầu và bao đóng bắc cầu của một quan hệ hai ngôi mờ, ta có thể có những nhận xét sau: Mệnh đề 2.2.1. Cho R là một quan hệ mờ thì phép hợp thành Max - Min và phép hợp thành Min - Max có tính chất: Rk◦R = R ◦Rk (a) Rk R = R Rk (b) Chứng minh. Để chứng minh ta cần sử dụng các tính chất sau: Tính chất kết hợp: (R1 ◦R2) ◦R3 = R1 ◦(R2 ◦R3). Tính chất đối ngẫu: R ◦R = R R ∧R = ∨ R. Bằng phương pháp quy nạp, ta có thể lần lượt chứng minh được (a) và (b) của nhận xét 1. Với k = 1, ta có R ◦R = R2 (đã nêu ở nội dung 1.4.2) nên (a) đúng. Giả sử (a) đúng với k = n, tức là Rn◦R = R ◦Rn. Khi đó, ta cần chứng minh (a) đúng với k = n+ 1. Thật vậy, Rn+1◦R = (R ◦Rn) ◦R = R ◦(Rn◦R) = R ◦Rn+1 (do áp dụng tính chất kết hợp của quan hệ mờ). Như vậy (a) đúng, ta có thể gọi đây là tính chất “giao hoán” của phép hợp thành Max - Min của một quan hệ mờ. Từ tính chất đối ngẫu De Morgan trong quan hệ hợp thành Max - Min (hợp thành Min - Max): Rk ◦R = Rk R và R ◦Rk = R Rk Khi đó, R là một quan hệ mờ có Rk R = R Rk hay ta chứng minh được (b) đúng với Rk R = R Rk. Ta có thể gọi R có tính chất giao hoán. 2 Mệnh đề 2.2.2. Với R là một quan hệ mờ có tính chất đối xứng thì mọi giá trị 100 Mối liên quan giữa khái niệm tính bao đóng bắc cầu Min - Max với thuật toán... k  1, Rk cũng có tính chất đối xứng. Chứng minh. Không mất tính chất tổng quát, R là một quan hệ mờ có tính chất đối xứng. Khi đó, giá trị phần tử của các ma trận R,Rk và Rk+1 lần lượt là: R = [aij], R k = [bij]vR k+1 = [cj] với i, j = 1, 2, 3, .., n;n : số đối tượng. Dễ thấy với k = 1 thì Rk = R,Rk có tính chất đối xứng. Ta cần chứng minh: Rk+1 = R2 = R ◦R cũng có tính chất đối xứng Thật vậy, với i, j, h = 1, 2, .., n ta có: cij = Max(Min(aih, bhj))vcji = Max(Min(ajh, bhi)) Trong trường hợp này, ta còn có thể viết: cij = Max(Min(aih, ahj))vcji = Max(Min(ajh, ahi)) Do R là đối xứng nên ta luôn có aih = ahivàajh = ahj(8i, j, h = 1, 2, ..., n). Suy ra: cij = cji, 8i, j = 1, 2, .., n. Giả sử Rk vẫn đúng với k = m, ta cần chứng minh k = m + 1 thì điều này vẫn đúng. Thật vậy, theo giả sử thì ta có Rk có tính đối xứng hay bij = bji8i, j. Khi đó: cij = Max(Min(aih, bhj))vàcji = Max(Min(ajh, bhi)) Từ tính chất giao hoán đã chứng minh ở nhận xét 1 ta có: cij = n Max h=1 (Min(bih, ahj)) = n Max h=1 (Min(ahj, bih)) mà ahj = ajh và bih = bhi nên cij = n Max h=1 (Min(ahj, bih)) = n Max h=1 (Min(ajh, bhi)) = cji Như vậy, hợp thành Max - Min của quan hệ mờ Rk có tính chất đối xứng. Tương tự chứng minh ta cũng có kết quả đúng với hợp thành Min - Max của một quan hệ mờ cũng có tính chất đối xứng. 2 Mệnh đề 2.2.3. Với R là một quan hệ mờ có tính chất phản xạ, hợp thành Max - Min của R là các quan hệ Rk và Rk+1 thoả mãn: Rk  Rk+1 (c) Với phép hợp thành Min - Max của quan hệ hai ngôi R có tính chất phản - phản xạ thì: Rk+1  Rk (d) Chứng minh. Ta có: cij = n Max h=1 (Min(aih, bhj)), để (c) đúng thì ta cần chứng minh: cij  bij  aij8i, j = 1, .., n (f) Thật vậy, với k = 1 thì aij = bji, khi đó: cij = n Max h=1 (Min(aih, bhj)) = n Max h=1 (Min(aih, ahj)) với h = i và aii = 1 (theo giả thiết) nên aij luôn được đưa vào tập hợp để xét lấy Max. Do vậy, cij  aij và cij = 1 khi i = j. Với k = 2, ta có: cij = n Max h=1 (Min(aih, bhj)) Khi đó với h = i thì ta luôn có bij được đưa vào tập hợp để xét lấy Max cho cij . Do 101 Phạm Thanh Huyền vậy, cij  bij . Bằng phương pháp quy nạp, dễ dàng rút ra kết luận (f). 2 Vậy, ma trận quan hệ tạo thành từ việc tính hợp thành Max - Min của một quan hệ có tính chất phản xạ cũng là một quan hệ có tính chất phản xạ và giá trị của phần tử của quan hệ này không nhỏ hơn phần tử tương ứng của ma trận tham gia phép lấy hợp thành (tức là Rk  Rk+1). Chứng minh tương tự, ta cũng có kết luận quan hệR có tính phản - phản xạ (aii = 0) thì hợp thành Min - Max của quan hệ đó cũng là một quan hệ có tính phản - phản xạ, tức là có: cij = n Min h=1 (Max(aih, bhj)) thoả mãn cij  bij  aij và cii = 0 (hay chính là Rk+1  Rk). Các kết luận này đều có vai trò hữu ích trong quá trình giải quyết thuật toán đã nêu ở trên. Nhờ áp dụng những kết luận này trong thực hiện cài đặt thuật toán, ta sẽ có kết quả về khối lượng tính toán giảm và việc lưu trữ các giá trị trung gian Ri(i = 1, 2, .., k) sẽ được loại bỏ ngay cả khi số đối tượng tham gia n và điểm dừng k là lớn (k  n). Cụ thể: + Quá trình tính toán các giá trị phần tử của ma trận quan hệ: Vì các ma trận khoảng cách, hay ma trận quan hệ được tính từ hợp thành Min - Max cấp luỹ thừa của một quan hệ mờ có tính chất phản - phản xạ (hoặc ma trận quan hệ được tính từ hợp thành Max - Min cấp luỹ thừa của một quan hệ có tính chất phản xạ) đều có tính đối xứng, nên khi tính giá trị của các phần tử cij ta chỉ cần tính toán trong trường hợp i < j và i = j(cii = 0). Còn trường hợp i > j thì cij = cji. + Quá trình thực hiện tìm bao đóng bắc cầu của một quan hệ mờ: Với R là quan hệ mờ có tính phản - phản xạ, hợp thành Min - Max luôn có kết quả là Rk+1  Rk. Như vậy, luôn tồn tại một điểm dừng k thoả mãn Rk+1 = Rk và bao đóng bắc cầu Min - Max của một quan hệ ∨ R chính là Rk. Như vậy, ta có 2 kết luận khi giải quyết thuật toán phân cụm nêu trên: - Thuật toán tìm bao đóng bắc cầu luôn có tính dừng, với cấp luỹ thừa thứ k(1  k  n) thoả mãn Rk = Rk+1. - Có thể loại bỏ các giá trị trung gian trong quá trình tìm bao đóng bắc cầu Min - Max. Ta cần lưu trữ các giá trị của 3 ma trận quan hệ là R,Rk và Rk+1. Độ phức tạp của thuật toán phân cụm dựa trên khoảng cách Min - Max là O(n2k). Trong đó, n là số đối tượng tham gia, k là cấp lũy thừa tìm bao đóng bắc cầu (hay k là số vòng lặp tìm bao đóng bắc cầu). Như vậy, khi giải quyết các bài toán về phân lớp, phân cụm đối tượng, dựa vào tính chất này của quan hệ mờ, ta có thể xây dựng một thuật toán phân cụm theo khoảng cách để thu được những cụm đối tượng mong muốn. Việc áp dụng hợp lí quan hệ bất tương đương mờ, bao đóng bắc cầu đã đảm bảo đặc tính dừng và giảm bớt một lượng lớn các giá trị cần tính toán và lưu trữ. Điểm khác biệt cơ bản của thuật toán này đối với các thuật toán phân cụm theo độ đo khác (K - mean, K - medoid, Fuzzy C - mean [1]) là việc xác định cụm không cần 102 Mối liên quan giữa khái niệm tính bao đóng bắc cầu Min - Max với thuật toán... xác định tâm ban đầu. Thuật toán đề xuất khắc phục được nhược điểm không cần lặp thử nhiều lần tìm các cụm tối ưu theo các trung tâm cụm, loại trừ các phần tử nhiễu. 2.2.3. Phân tích quan hệ mờ dựa trên các giá trị khoảng cách Cho một tập dữ liệu với n đối tượng tương ứng có m thuộc tính, ta luôn có thể xây dựng được một quan hệ hai ngôi mờ tương ứng. Vấn đề đặt ra là cần tìm cách phân cụm hay gom cụm các dữ liệu đó theo khoảng cách (tức là dựa vào ma trận quan hệ xây dựng được từ các khái niệm khoảng cách, ta cần tìm ra các cụm phù hợp) [3]. Khái niệm khoảng cách Min - Max, tương ứng với một quan hệ bất tương đương thích hợp cho bài toán này. Khi phân tích những quan hệ mờ tương ứng, các khái niệm thông thường thu được có tính chất bảo toàn tính bắc cầu đối với khoảng cách Min - Max. Ví dụ 1: Cho một danh sách gồm 7 đối tượng sinh viên (n = 7) với các thuộc tính như bảng sau: Tên ĐT Văn hoá Tâm lí CT ĐĐội Tập giảng VD01 9,3 8,0 9,7 9,0 VD02 6,0 6,0 6,0 7,0 VD03 5,7 5,8 5,0 5,0 VD04 8,9 9,4 8,6 8,5 VD05 8,0 5,0 5,8 6,5 VD06 5,0 6,8 8,5 7,0 VD07 7,5 8,0 5,5 6,8 ! Sử dụng khoảng cách Hamming tương đối không trọng số: Duv = 1 7 duv ta có ma trận khoảng cách tương ứng: D VD01 VD02 VD03 VD04 VD05 VD06 VD07 VD01 0,000 0,109 0,109 0,049 0,109 0,109 0,109 VD02 0,109 0,000 0,050 0,109 0,053 0,061 0,059 VD03 0,109 0,050 0,000 0,109 0,053 0,061 0,059 VD04 0,049 0,109 0,109 0,000 0,109 0,109 0,109 VD05 0,109 0,053 0,053 0,109 0,000 0,061 0,059 VD06 0,109 0,061 0,061 0,109 0,061 0,000 0,061 VD07 0,109 0,059 0,059 0,109 0,059 0,061 0,000 ! Thực hiện tính bao đóng bắc cầu Min - Max của D: ∨ D = D \ (D D) \ (D D D) \ ... 103 Phạm Thanh Huyền Ta tìm được k = 3 thoả mãn k < 7 để D3 = D4. Khi đó kết quả ∨ D cần tìm là: ∨ D VD01 VD02 VD03 VD04 VD05 VD06 VD07 VD01 0,000 0,109 0,109 0,049 0,109 0,109 0,109 VD02 0,109 0,000 0,05 0,109 0,053 0,061 0,059 VD03 0,109 0,050 0,000 0,109 0,053 0,061 0,059 VD04 0,049 0,109 0,109 0,000 0,109 0,109 0,109 VD05 0,109 0,053 0,053 0,109 0,000 0,061 0,059 VD06 0,109 0,061 0,061 0,109 0,061 0,000 0,061 VD07 0,109 0,059 0,059 0,109 0,059 0,061 0,000 ! Xác định hệ tiêu chuẩn: TC = f0; 0, 049; 0, 050; 0, 053; 0, 059; 0, 061; 0, 109g ! Phân tích quan hệ ∨D thu được thành quan hệ thông thường dựa trên các giá trị khoảng cách tương ứng với từng giá trị tiêu chuẩn đã xác định: - Với tiêu chuẩn TC1 = 0: Quan hệ thông thường này cho ta 7 cụm riêng biệt là: fV D01g, fV D02g, fV D03g, fV D04g, fV D05g, fV D06g, fV D07g - Với tiêu chuẩn TC2 = 0, 049: Ta được 6 cụm là: fV D01, V D04g, fV D02g, fV D03g, fV D05g, fV D06gvfV D07g - Với tiêu chuẩn TC3 = 0, 050: Ta được 5 cụm là: fV D01, V D04g, fV D02, V D03g, fV D05g, fV D06gvfV D07g - Với tiêu chuẩn TC4 = 0, 053: Ta được 4 cụm là: fV D01, V D04g, fV D02, V D03, V D05g, fV D06gvfV D07g - Với tiêu chuẩn TC5 = 0, 059: Ta được 3 cụm là: fV D01, V D04g, fV D02, V D03, V D05, V D07gvfV D06g - Với tiêu chuẩn TC6 = 0, 061: Ta được 2 cụm là: fV D01, V D04g, fV D02, V D03, V D05, V D06, V D07g - Với tiêu chuẩn TC7 = 0, 109: Ta được 1 cụm là: fV D01, V D02, V D03, V D04, V D05, V D06,