Luận văn thạc sĩ: Các lược đồ phân cụm phân cấp bất biến - ĐH Quốc Gia HN

Luận văn thạc sĩ về các lược đồ phân cụm phân cấp bất biến. Nghiên cứu chuyên sâu về thuật toán và ứng dụng phân cụm dữ liệu hiệu quả.

• Tác giả: Dương Hải Đường
• Người hướng dẫn: Pgs. Hoàng Xuân Huấn
• Trường học: Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Các Lược Đồ Phân Cụm Phân Cấp Bất Biến
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2014
• Địa điểm: Hà Nội

Mục lục chi tiết

• Lời cảm ơn
• Lời cam đoan
• DANH MỤC CÁC KÝ HIỆU, TỪ VIẾT TẮT
• DANH MỤC CÁC HÌNH VẼ
• DANH MỤC CÁC BẢNG BIỂU
• 1. CHƯƠNG I: TỔNG QUAN VỀ PHÂN CỤM
• 1.1. Phân cụm dữ liệu là gì
• 1.2. Các kiểu dữ liệu và độ đo tương tự
• 1.2.1. Cấu trúc dữ liệu
• 1.2.2. Các kiểu dữ liệu
• 1.3. Các phương pháp phân cụm dữ liệu
• 1.4. Vấn đề chuẩn hóa dữ liệu
• 2. CHƯƠNG II: PHÂN CỤM DỮ LIỆU HƯỚNG TIẾP CẬN PHÂN CẤP
• 2.1. Phân cụm phân cấp
• 2.2. Thuật toán BIRCH
• 2.3. Thuật toán CURE
• 2.4. Thuật toán ANGNES
• 2.5. Thuật toán DIANA
• 2.6. Thuật toán ROCK
• 2.7. Thuật toán Chameleon
• 3. CHƯƠNG 3: CÁC LƯỢC ĐỒ PHÂN CỤM PHÂN CẤP BẤT BIẾN
• 3.1. Các thủ tục phân cụm bất biến và không bất biến
• 3.2. Các định nghĩa cơ bản
• 3.3. Lược đồ tổng quát của các thủ tục phân cụm phân cấp bất biến
• 3.4. Một tiếp cận thuyết đồ thị để tính bao đóng bắc cầu
• 3.5. Các thủ tục phân cụm với các hàm hàng xóm đồng nhất
• 3.6. Lựa chọn các cụm có giá trị
• 3.7. Các thủ tục với các hàm hàng xóm không đồng nhất
• 3.8. Kết quả thực nghiệm
• 3.8.1. Chương trình
• 3.8.2. Ví dụ dữ liệu chuỗi thời gian
• KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Khám phá Phân Cụm Phân Cấp Bất Biến Luận văn CNTT

Tin học hóa đã tạo ra lượng dữ liệu khổng lồ. Các kỹ thuật khai phá dữ liệu cũ bộc lộ hạn chế, dẫn đến nhu cầu kỹ thuật mới để chuyển đổi dữ liệu thành tri thức. Luận văn này trình bày khảo cứu về lược đồ tham số tổng quát cho các thủ tục phân cụm phân cấp với tính bất biến qua các biến đổi đơn điệu các giá trị tương tự và tính bất biến qua đánh số các đối tượng. Lược đồ này bao gồm 2 bước: tinh chỉnh những giá trị tương tự được đưa ra giữa các đối tượng và bao đóng bắc cầu của quan hệ định trị đạt được.

Luận văn cũng khảo cứu vài thuộc tính về mặt lý thuyết của lược đồ đã được chỉ ra, và các lớp tham số khác nhau từ lược đồ dựa trên nhận thức như kiểu “giữ các lớp tương tự”, “ngắt các cầu giữa các cụm.” Có ít nhất hai mục đích khi tiến hành phân tích giá trị tương tự giữa các đối tượng trong một tập: (1) chia tập đối tượng thành các lớp các đối tượng tương tự và (2) phân tích cấu trúc tương tự của tập này. Nhiều thuật toán phân cụm hướng đến chia tập đối tượng đã cho thành một số cho trước các lớp đối tượng tương tự, mà không đưa ra cấu trúc đặc trưng nhưng các thuật toán này phù hợp dữ liệu với một vài mô hình định trước [16,27].

Người dùng có thể rất hài lòng với những cụm tốt đạt được đối với dữ liệu của mình bởi thủ tục phân cụm chuẩn nào đó, nhưng rất có thể cấu trúc các cụm đạt được không phản ánh cấu trúc dữ liệu thực chất của dữ liệu mà bị áp đặt bởi các chi tiết kỹ thuật của thuật toán phân cụm được áp dụng. Một trong những nguyên nhân của nhược điểm này trong nhiều thuật toán phân cụm phổ biến là từ tính không bất biến của các thuật toán này với việc đánh số (hoán vị, xếp thứ tự) các đối tượng. Việc đổi trật tự đánh số các đối tượng tại đầu vào của thủ tục phân cụm không bất biến thường gây ra sự thay đổi các kết quả của phân cụm. Có nghĩa là việc phân cụm đạt được đối với cách đánh số đối tượng đã cho không phản ánh cấu trúc của tập các đối tượng.

Đòi hỏi tính bất biến của các thuật toán phân cụm đối với đánh số các đối tượng trong phân tích cụm là đòi hỏi quan trọng nhất [2,7,9,22], nhưng thật không may, đa số các thuật toán phân cụm phổ biến không thỏa mãn thuộc tính này. Thuộc tính này được thỏa mãn trong thuật toán liên kết đơn (còn được gọi là hàng xóm gần nhất) và được trình bày trong [16,22-24]. Luận văn quan tâm tới lược đồ tham số của các thủ tục phân cụm bất biến, lược đồ này đa dạng quan điểm đối với “cụm” và bao gồm thuật toán liên kết đơn như là một trường hợp cụ thể.

1.1. Tổng quan về Phân Cụm và các bài toán liên quan

Phân cụm dữ liệu là quá trình chia tập dữ liệu thành các cụm sao cho các đối tượng trong cùng một cụm tương tự nhau hơn so với các đối tượng ở các cụm khác. Các bài toán liên quan đến phân cụm bao gồm tóm tắt dữ liệu, tạo mẫu phân lớp thống kê, tạo tâm nơron nhân tạo, và xử lý dữ liệu lớn. Các kiểu dữ liệu khác nhau (liên tục, rời rạc, nhị phân) và các độ đo tương tự (Euclidean, Manhattan, Mahalanobis) ảnh hưởng đến kết quả phân cụm. Việc chuẩn hóa dữ liệu cũng quan trọng để đảm bảo tính công bằng giữa các thuộc tính.

1.2. Ứng dụng của Phân Cụm trong Công Nghệ Thông Tin CNTT

Phân cụm được sử dụng rộng rãi trong CNTT để giải quyết nhiều vấn đề khác nhau. Trong khai phá dữ liệu, phân cụm giúp phát hiện ra các mẫu và xu hướng ẩn trong dữ liệu lớn. Trong học máy, nó được sử dụng để huấn luyện các mô hình không giám sát. Phân cụm cũng có thể được áp dụng trong phân tích mạng xã hội, xử lý ảnh, và phân tích văn bản. Việc lựa chọn thuật toán phân cụm phù hợp phụ thuộc vào đặc điểm của dữ liệu và mục tiêu của ứng dụng.

II. Vấn đề Bất Biến trong Phân Cụm Phân Cấp Tại sao

Một đòi hỏi quan trọng khác đối với thuật toán phân cụm là bất biến với sự biến đổi đều của các giá trị tương tự giữa các đối tượng [19,22,23,25]. Đòi hỏi này là cần thiết đối với thuật toán phân cụm nếu các giá trị tương tự được ước lượng bởi các chuyên gia trong độ đo có thứ tự. Sự đòi hỏi này cũng rất cần thiết cho sự không nhạy cảm của các kết quả phân cụm đối với việc chọn độ đo tương tự hoặc độ đo không tương tự.

Luận văn khảo cứu lược đồ tổng quát của thủ tục phân cụm phân cấp thỏa mãn cả hai sự đòi hỏi bất biến được quan tâm ở trên. Lược đồ này được đề xuất đầu tiên bởi Batyrshin [3-5] dựa vào khái niệm quan hệ tương đương mờ, khái niệm này được giới thiệu và nghiên cứu trong [29,31]. Thủ tục phân cụm trong lược đồ này bao gồm 2 bước: tinh chỉnh các giá trị tương tự đã cho giữa các đối tượng và bao đóng bắc cầu lớn nhất-nhỏ nhất của quan hệ (mờ) định trị đạt được. Khi tinh chỉnh các giá trị tương tự không được dùng và chỉ áp dụng bao đóng bắc cầu của quan hệ tương tự đã cho thì lược đồ phân cụm dẫn tới thủ tục phân cụm được đề xuất trong [29] thuật toán này tương tự như thuật toán liên kết đơn [17]. Bởi vì bao đóng bắc cầu là bất biến đối với đánh số các đối tượng và đối với biến đổi đều của các giá trị tương tự, thủ tục phân cụm sẽ thỏa mãn cả hai loại bất biến nếu thủ tục tinh chỉnh cũng thỏa mãn hai bất biến trên. Vài lược đồ của các thủ tục tinh chỉnh tham số bất biến như vậy được đưa ra nghiên cứu trong luận văn.

2.1. Tính Bất Biến Định nghĩa và vai trò trong phân tích dữ liệu

Tính bất biến trong phân cụm đề cập đến khả năng của thuật toán phân cụm để tạo ra kết quả nhất quán bất kể sự thay đổi trong cách dữ liệu được biểu diễn hoặc sắp xếp. Có hai loại bất biến chính: bất biến đối với đánh số (kết quả không thay đổi khi thay đổi thứ tự các đối tượng) và bất biến đối với biến đổi đơn điệu (kết quả không thay đổi khi giá trị tương tự được biến đổi một cách đơn điệu). Tính bất biến đảm bảo rằng kết quả phân cụm phản ánh cấu trúc thực sự của dữ liệu, không bị ảnh hưởng bởi các yếu tố bên ngoài. [2,7,9,22]

2.2. Hạn chế của các thuật toán phân cụm truyền thống về tính bất biến

Nhiều thuật toán phân cụm truyền thống không đáp ứng được yêu cầu về tính bất biến. Ví dụ, thuật toán liên kết trung bình có thể tạo ra kết quả khác nhau khi thay đổi thứ tự các đối tượng. Điều này là do các thuật toán này thường dựa trên các độ đo khoảng cách nhạy cảm với sự thay đổi trong cách dữ liệu được biểu diễn. Sự thiếu bất biến có thể dẫn đến kết quả phân cụm không chính xác và khó diễn giải.[16,27]

2.3. Ví dụ minh họa sự không bất biến của thuật toán trung bình

Cho một ví dụ đơn giản với 7 điểm phân bố đều trên hình tròn. Khi sử dụng thuật toán liên kết trung bình, việc thay đổi thứ tự đánh số các điểm có thể dẫn đến các phân chia khác nhau. Điều này cho thấy kết quả phân cụm không phản ánh cấu trúc đối xứng của dữ liệu. Chỉ có 2 sự phân chia tầm thường là A={{a},{b},{c},{d},{e},{f},{g}} và B={{a,b,c,d,e,f,g}} tương ứng với sự đối xứng dữ liệu.

III. Phương pháp Phân cụm Phân Cấp Bất Biến Lược đồ tổng quát

Để xây dựng thủ tục phân cụm hợp lý trong lược đồ quan tâm, cần thiết phải đề xuất thủ tục hiệu chỉnh phù hợp. Luận văn khảo cứu các thuộc tính của các quan hệ tương tự và các thủ tục hiệu chỉnh liên quan đến nhận thức cụm “tự nhiên” và phân cụm “hợp lý”. Các kết quả chính được đưa ra trong Định lý 2 và Bổ đề 5 cho thấy mối quan hệ giữa các thuộc tính của các quan hệ tương tự và các thủ tục hiệu chỉnh. Định lý 2 đưa ra các nguyên nhân cho việc xây dựng lớp tổng thể của thủ tục hiệu chỉnh như là sự biến đổi làm giảm các giá trị tương tự trong quan hệ tương tự khởi tạo cho trước. Bổ đề 5 nói rằng một vài lớp biến đổi như vậy thì kết quả của thủ tục phân cụm sẽ thỏa mãn tính chất “giữ nguyên các lớp tương tự”. Kết quả này được dùng xa hơn đối với việc xây dựng thủ tục phân cụm, “ngắt” các lớp tương tự được xem như “các cầu” giữa các cụm.

3.1. Tổng quan về Lược đồ Tham số Tổng quát cho Phân Cụm Bất Biến

Lược đồ tổng quát cho các thủ tục phân cụm phân cấp bất biến bao gồm hai bước chính: tinh chỉnh các giá trị tương tự giữa các đối tượng và bao đóng bắc cầu của quan hệ định trị đạt được. Công thức có dạng E = Q(S) = TC(F(S)) = F(S) , trong đó F là thủ tục "tinh chỉnh", TC là thủ tục bao đóng bắc cầu, Q là thủ tục phân cụm. Lược đồ này đảm bảo tính bất biến đối với đánh số các đối tượng và biến đổi đơn điệu giá trị tương tự nếu F thỏa mãn. Thủ tục F cần phải thỏa mãn rằng F(S) ⊆ S

3.2. Các bước thực hiện và thuộc tính quan trọng của lược đồ

Thủ tục phân cụm trong lược đồ này gồm hai bước: tinh chỉnh các giá trị tương tự đã cho giữa các đối tượng và bao đóng bắc cầu lớn nhất - nhỏ nhất của quan hệ (mờ) định trị đạt được. Việc tinh chỉnh các giá trị tương tự và áp dụng bao đóng bắc cầu đảm bảo tính bất biến. Điều này đảm bảo thuật toán luôn đưa ra kết quả tương tự dù dữ liệu có bị xáo trộn thứ tự hay giá trị tương tự giữa các phần tử bị thay đổi.

3.3. Cách lựa chọn thủ tục tinh chỉnh F phù hợp

Để xây dựng một thủ tục tinh chỉnh phù hợp F cần thỏa mãn ràng buộc F(S) ⊆ S, có nghĩa là F không được làm tăng các giá trị tương tự. Việc lựa chọn thủ tục tinh chỉnh phù hợp phụ thuộc vào mục tiêu phân tích dữ liệu. Nếu mục tiêu là giữ lại các cụm tương tự thì thủ tục tinh chỉnh cần bảo toàn cấu trúc tương tự ban đầu. Nếu mục tiêu là loại bỏ các cầu nối giữa các cụm thì thủ tục tinh chỉnh cần giảm thiểu sự tương tự giữa các đối tượng thuộc các cụm khác nhau.

IV. Các hàm lân cận và tinh chỉnh Bí quyết Phân cụm Bất Biến

Để bất biến đối với đánh số đối tượng thì thủ tục tinh chỉnh phải được áp dụng đối với tất cả các cặp đối tượng (x,y) một cách đồng thời và độc lập với đánh số của các đối tượng. Để bất biến đối với phép biến đổi đều của các giá trị tương tự thì thủ tục tinh chỉnh phải lưu ý tới sắp xếp tuyến tính giữa các giá trị tương tự S(x,y). Tất nhiên, khi thuật toán phân cụm không đòi hỏi phải bất biến đối với phép biến đổi đều của các giá trị tương tự thì thủ tục tinh chỉnh có thể dùng các độ đo định lượng nào đó tùy thuộc vào các giá trị tương tự S(x,y).

4.1. Khái niệm hàm lân cận f1 f2 f3 và vai trò trong tinh chỉnh

Các hàm lân cận (f1, f2, f3) được sử dụng để xác định các đối tượng "tương tự" hoặc "hàng xóm" của một cặp đối tượng (x, y). Hàm f1 xác định mức độ tương tự cần thiết để một đối tượng z được coi là hàng xóm của x hoặc y. Hàm f2 xác định mức độ tương tự cần thiết để một đối tượng z được coi là hàng xóm của ít nhất một trong hai đối tượng x hoặc y. Hàm f3 xác định mức độ tương tự cần thiết để một đối tượng z được coi là hàng xóm "khỏe" hoặc "phổ biến" của cả hai đối tượng x và y. Các hàm lân cận đóng vai trò quan trọng trong việc quyết định tinh chỉnh giá trị S(x, y).

4.2. Cách thức tinh chỉnh giá trị tương tự S x y dựa trên hàm lân cận

Việc tinh chỉnh giá trị tương tự S(x, y) dựa trên các hàm lân cận nhằm mục đích làm nổi bật các cụm tự nhiên trong dữ liệu. Nếu một cặp đối tượng (x, y) có nhiều hàng xóm "khỏe" thì giá trị S(x, y) sẽ được giữ nguyên hoặc tăng lên. Ngược lại, nếu một cặp đối tượng (x, y) có ít hàng xóm "khỏe" thì giá trị S(x, y) sẽ bị giảm xuống. Việc giảm giá trị S(x, y) có thể giúp loại bỏ các "cầu nối" giữa các cụm, tạo ra các cụm rõ ràng hơn.

4.3. Các cách thức đánh giá sự liên quan của các cặp đối tượng x và y

Giá trị S(x,y) được đánh giá thông qua 2 tham số là p thuộc [0,1] và j thuộc [0,1,...]. Qua đó, hai đối tượng có liên quan được đánh giá sự tương đồng để quyết định chỉnh sửa kết quả thuật toán. Công thức ( , ) ế ℎ ≥ ( ( , )) = , ( , ) ườ ℎợ ≠ với p ∈ [0,1], j là các tham số và Fj(x,y) là một giá trị đã được tinh chỉnh, như vậy Fj(x,y) ≤ S(x,y) là một phương pháp đánh giá.

V. Tiếp cận đồ thị Phương pháp Hiệu quả tính Bao đóng Bắc cầu

Từ định nghĩa 3.10, ta thấy để tính bao đóng bắc cầu TC ta tiến hành nhân ma trận S với n-1 lần. Ta giới thiệu ở đây, một phương pháp tính toán tính bao đóng dựa vào thuật toán Prim tạo cây khung lớn nhất, và tìm đường trọng số lớn nhất trên cây khung lớn nhất. Phương pháp này tốt hơn nhiều so với thuật toán nhân ma trận cả về thời gian tính toán và yêu cầu bộ nhớ.

5.1. Giới thiệu phương pháp đồ thị để tính bao đóng bắc cầu hiệu quả

Thay vì nhân ma trận, phương pháp đồ thị sử dụng thuật toán Prim để tạo cây khung lớn nhất. Sau đó, tìm đường trọng số lớn nhất trên cây khung lớn nhất. Phương pháp này hiệu quả hơn về thời gian và bộ nhớ so với nhân ma trận. Lược đồ phân cụm phân cấp được tạo bởi một họ tham số của các quan hệ tương đương xRλy trên tập X, đạt được từ quan hệ mờ đối xứng tùy ý f1: X x X → [0,1] thỏa mãn f1(x,x) = 1 và f1(x,y) = f1(y,x).

5.2. Ưu điểm của phương pháp đồ thị so với phương pháp nhân ma trận

Thuật toán Prim có độ phức tạp O(n^2), trong khi nhân ma trận có độ phức tạp O(n^3). Do đó, phương pháp đồ thị hiệu quả hơn đáng kể khi kích thước dữ liệu lớn. Ngoài ra, phương pháp đồ thị yêu cầu ít bộ nhớ hơn so với nhân ma trận.

VI. Kết quả Thực nghiệm và Hướng Phát triển trong tương lai

Trong phần thực nghiệm luận văn thực hiện cài đặt thuật toán TC(F(S)). Chương trình được lập trình bằng ngôn ngữ Java trên nền trên nền JDK 8 (Java SE Development Kit 8), phần mềm hỗ trợ code là Eclipse phiên bản Luna Service Release 1 (4. Cấu hình máy tính: Ram 2G, tốc độ xử lý 2,53GHz.

Đầu vào: Mảng S kích thước NxN chứa giá trị tương tự từng cặp trong N đối tượng. Các giá trị lựa chọn để tinh chỉnh f1, f2, f3, j, r, q, p. Đầu ra: Cây phân cấp. Thuật toán bao gồm 2 pha: Pha 1: Tinh chỉnh ma trận đầu vào, với các tham số f1, f2, f3, j, r, q, p. Pha 2: Dùng thuật toán Prim tìm cây khung lớn nhất. Tính giá trị ma trận bao đóng, bỏ dần từng cạnh của cây khung lớn nhất và đưa ra cây phân cấp.

6.1. Kết quả thực nghiệm của thuật toán TC F S

Các kết quả thực nghiệm cho thấy thuật toán TC(F(S)) có khả năng tạo ra các cụm có độ chính xác cao và tính bất biến tốt. Thuật toán cũng cho thấy hiệu quả về thời gian và bộ nhớ khi áp dụng cho dữ liệu lớn.

6.2. Hướng phát triển và nghiên cứu trong tương lai

Trong tương lai, cần nghiên cứu thêm về các phương pháp tinh chỉnh hiệu quả hơn và các độ đo tương tự phù hợp với các loại dữ liệu khác nhau. Ngoài ra, cần phát triển các thuật toán phân cụm bất biến có khả năng xử lý dữ liệu động và dữ liệu phân tán.

Trích đoạn nội dung tài liệu

CHƯƠNG I: TỔNG QUAN VỀ PHÂN CỤM 1. Phân cụm dữ liệu là gì Dựa vào khám phá cấu trúc tập dữ liệu, ta chia tập dữ liệu thành các cụm rời nhau sao cho các đối tượng trong cùng một cụm thì tương tự nhau so với các đối tượng khác cụm [1]. Phân cụm được dùng cho các mục đích sau: + Tóm tắt và giải thích dữ liệu bài toán. Nhiều bài toán, dữ liệu có thể được tóm tắt nhờ xem xét thuộc tính của các cụm dữ liệu mà không cần thiết xem xét thuộc tính của từng mẫu.

Trong nhiều lý thuyết khoa học, việc giải thích theo cụm cũng rất có ý nghĩa, chẳng hạn, việc phân tích tiến hóa sinh học có thể thực hiện theo loài và nhóm loài. + Tạo mẫu cho tiếp cận phân lớp thống kê. Trong nhiều bài toán phân lớp, việc thu thập dữ liệu mất nhiều thời gian và chi phí lớn. Việc phân cụm dữ liệu được thực hiện ở giai đoạn đầu để ước lượng phân phối lớp cho các tập mẫu nhỏ.

+ Để tạo tâm cho các nơron nhân tạo trong các bộ phân lớp loại này. Khi dùng mạng nơron nhân tạo để phân lớp, người ta thường dùng vectơ trung bình của các vectơ đặc trưng trong cụm làm tâm của các nơron để nhận biết các mẫu có đặc trưng gần nó. + Một giải pháp giúp xử lý dữ liệu lớn. Việc khám phá tri thức trong các cơ sở dữ liệu thường phải xử lý khối lượng dữ liệu rất lớn, nhiều khi ngay cả các thuật toán với độ phức tạp tính toán là đa thức cũng không dùng được.

Việc phân và xử lý dữ liệu theo các cụm là một giải pháp hữu hiệu, vì vậy bài toán phân cụm nay được nhiều người quan tâm trở lại. Các kiểu dữ liệu và độ đo tương tự 1. Cấu trúc dữ liệu Các thuật toán gom cụm hầu hết sử dụng hai cấu trúc dữ liệu điển hình sau: Ma trận dữ liệu (hay cấu trúc đối tượng theo biến): Biểu diễn n đối tượng và p biến (hay còn được gọi là các phép đo hoặc các thuộc tính) của đối tượng, có dạng ma trận n hàng và p cột. Trong đó, mỗi hàng biểu diễn một đối tượng, các phần tử trong mỗi hàng chỉ giá trị thuộc tính tương ứng của đối tượng đó.

xnp   TIEU LUAN MOI download : [e-mail] 12 Ma trận phi tương tự (cấu trúc đối tượng theo đối tượng): Lưu trữ khoảng cách của tất cả các cặp đối tượng. Biểu thị bằng ma trận n hàng và n cột. Trong đó, d(i,j) là khoảng cách hay độ khác biệt giữa các đối tượng i và đối tượng j. d(i,j) là một số không âm, d(i,j) gần tới 0 khi hai đối tượng i và j có độ tương đồng cao hay chúng “gần” nhau, d(i,j) càng lớn nghĩa là hai đối tượng i và j có độ tương đồng càng thấp hay chúng càng “xa” nhau.

0 Ma trận dữ liệu thường được gọi là ma trận 2 kiểu (two-mode matrix), trong khi đó ma trận phi tương tự được gọi là ma trận 1 kiểu (one-mode matrix). Phần lớn các thuật toán phân cụm thường sử dụng cấu trúc ma trận phi tương tự. Do đó, nếu dữ liệu cần phân cụm được tổ chức dưới dạng ma trận dữ liệu thì cần biến đổi về dạng ma trận phi tương tự trước khi tiến hành phân cụm. Các kiểu dữ liệu Cho một cơ sở dữ liệu D chứa n đối tượng trong không gian k chiều; x, y, z là các đối tượng thuộc D: x = ( , , … , ); y = ( , , … , ); z = ( , , … , ).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.

Do đó, khái niệm “các kiểu dữ liệu” và “các kiểu thuộc tính dữ liệu” được xem là tương đương nhau. Có hai đặc trưng để phân loại kiểu dữ liệu là kích thước miền và hệ đo. Phân loại kiểu dữ liệu dựa trên kích thước miền Kích thước miền Liên tục Rời rạc Nhị phân Hình 1.1: Phân loại 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à không đếm được, nghĩa là giữa hai giá trị tồn tại vô số giá trị khác.

Thí dụ: các thuộc tính về màu, cường độ âm thanh,. TIEU LUAN MOI download : [e-mail] 13 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. Thí dụ: loại ô tô là một thuộc tính rời rạc với tập giá trị là: {xe tải, xe khách, xe con, taxi}. Thuộc tính nhị phân (Binary Attribute): 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ó hai phần tử được diễn tả như: Yes/ No hoặc Nam/ Nữ,.

Phân loại kiểu dữ liệu dựa trên hệ đo Hệ đo Định danh Có thứ tự Khoảng Tỉ lệ Hình 1.2: Phân loại kiểu dữ liệu dựa trên hệ đo. Thuộc tính định danh (Nominal): đâ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ử. 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. Thí dụ như thuộc tính về nơi sinh.

Thuộc tính có thứ tự (Ordinal): 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. Thí dụ như thuộc tính huy chương của vận động viên thể thao. Thuộc tính khoảng (Interval): dùng để đo các giá trị theo xấp xỉ tuyến tính.

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. Một thí dụ về thuộc tính khoảng như thuộc tính số serial của một đầu sách trong thư viện hoặc thuộc tính số kênh trên truyền hình. Thuộc tính tỉ lệ (Ratio): 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.

Độ đo tương tự Sự khác biệt hay tương tự giữa hai đối tượng được xác định qua một hàm khoảng cách giữa chúng, khoảng cách d(x,y) giữa x và y cho bởi mêtric thỏa mãn các tính chất sau: Tính xác định dương: d(x,y) ≥0, ∀ x,y, d(x,y) = 0 khi và chỉ khi x = y. TIEU LUAN MOI download : [e-mail] 14 Tính giao hoán: d(x,y) = d(y,x), ∀ x, y. Bất đẳng thức tam giác: d(x,y) ≤ d(x,z) + d(z,y), ∀ x, y, z. Nếu không gian đặc trưng là không gian số học d-chiều và mêtric có tính chất: d(ax,y) = | |d(x,y) Sau đây là các phép đo độ tương tự áp dụng đối với các kiểu dữ liệu khác nhau.1 Thuộc tính nhị phân Để tìm độ đo, trước hết người ta xây dựng bảng sau: Bảng 1: Bảng giá trị tham số Đối tượng y y:1 y:0 Tổng Đối tượng x x:1   + x:0    + Tổng  +  +  Trong đó :  =  +  +  +  , các đối tượng x, y mà tất cả các thuộc tính tính của nó đều là nhị phân biểu thị bằng 0 và 1.

Bảng trên cho ta các thông tin sau:  là tổng số các thuộc tính có giá trị là 1 trong cả hai đối tượng x, y;  là tổng số các giá trị thuộc tính có giá trị là 1 trong x và 0 trong y;  là tổng số các giá trị thuộc tính có giá trị là 0 trong x và 1 trong y;  là tổng số các giá trị thuộc tính có giá trị là 0 trong x và y. Khi đó độ đo tương tự được đo như sau:   Hệ số đối sánh đơn giản: d ( x, y )  , ở đâ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 )  , chú ý rằng tham số này bỏ qua số các đối     sánh giữa 0 – 0. 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 Độ đo phi tương tự giữa hai đối tượng x và y được định nghĩa như sau: pm d ( x, y )  p Trong đó: m là số thuộc tính đối sánh tương ứng trùng nhau và p là tổng số các thuộc tính. TIEU LUAN MOI download : skknchat@gmail. Thuộc tính có thứ tự Phép đo độ phi tương tự giữa các đối tượng dữ liệu với thuộc tính thứ tự được thực hiện như sau, ở đây ta giả sử i là thuộc tính thứ tự có Mi giá trị (Mi là kích thước miền giá trị): Các trạng thái Mi được sắ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. 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 : ( j) r 1 ( j) i z  1 i M i Sử dụng công thức tính độ phi tương tự của thuộc tính khoảng đối với các giá trị z i( j ) , đây cũng chính là độ phi tương tự của thuộc tính có thứ tự.

Thuộc tính khoảng Sau khi chuẩn hoá, độ đo phi tương tự của hai đối tượng dữ liệu x, y được xác định bằng các metric khoảng cách: Khoảng cách Minskowski: ( , ) = (∑ | − | ) , q ≥ 1. Có ba khoảng cách phổ biến sử dụng khoảng cách Minskowski định nghĩa như sau: Khoảng cách Euclide: ( , ) = (∑ | − | ) , (q = 2) Khoảng cách Manhattan: ( , ) = ∑ | − | , (q = 1) Khoảng cách cực đại: ( , ) = | − |, (q → ∞). Khoảng cách Euclide là chuẩn khoảng cách được dùng phổ biến nhất trong các chuẩn theo khoảng cách Minshowski. Ngoài ra, còn có chuẩn khoảng cách Mahalanobis: ( , )=( − ) ( − ) Trong đó, A là một ma trận đối xứng xác định dương.