PHÂN CỤM DỮ LIỆU - Data Clustering
Bài toán phân cụm dữ liệu
Bài toán phân cụm dữ liệu thường được hiểu là một bài toán học không giám sát và được phát biểu như sau:
Trong bài viết này, chúng ta sẽ xem xét tập N đối tượng dữ liệu X = {x1, …, xn} trong không gian số học n-chiều, với các đối tượng xi thuộc Rn Mục tiêu là chia tập X thành các cụm đôi một không giao nhau, sao cho các đối tượng trong cùng một cụm Ci có sự tương đồng cao, trong khi các đối tượng thuộc các cụm khác nhau lại có sự khác biệt rõ rệt theo một tiêu chí nhất định.
Số lượng cụm k có thể được xác định thông qua phương pháp phân cụm, yêu cầu đánh giá mức độ tương tự giữa các đối tượng và tiêu chuẩn phân cụm Dựa trên đó, chúng ta xây dựng mô hình và áp dụng các thuật toán phân cụm theo nhiều cách tiếp cận khác nhau Mỗi phương pháp mang lại kết quả phân cụm với ý nghĩa sử dụng riêng biệt.
Kiểu dữ liệu và độ đo tương tự sử dụng trong bài toán phân cụm dữ liệu
Trong phần này, chúng ta phân tích các kiểu dữ liệu thường được sử dụng trong PCDL, bao gồm con người, nhà, tiền lương, và các thực thể phần mềm Các đối tượng này được diễn tả qua các thuộc tính, đóng vai trò là tham số quan trọng trong việc giải quyết vấn đề PCDL Việc lựa chọn thuộc tính có ảnh hưởng lớn đến kết quả phân cụm, do đó, phân loại các kiểu thuộc tính khác nhau là cần thiết để nhận diện sự khác biệt giữa các phần tử dữ liệu Dựa trên hai đặc trưng x i , y i , z i, chúng ta có thể đồng nhất hai khái niệm “các kiểu dữ liệu” và “các kiểu thuộc tính dữ liệu”, từ đó xác định các kiểu dữ liệu cụ thể trong PCDL.
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) là loại thuộc tính có miền giá trị vô hạn không đếm được, với khả năng tồn tại vô số giá trị giữa hai điểm Ví dụ điển hình cho thuộc tính này bao gồm màu sắc, nhiệt độ và cường độ âm thanh.
Thuộc tính rời rạc (Discrete Attribute) là những thuộc tính có miền giá trị là tập hữu hạn và đếm được Ví dụ điển hình cho thuộc tính này bao gồm số serial của một cuốn sách hoặc số thành viên trong một gia đình.
Lớp thuộc tính nhị phân là một loại thuộc tính rời rạc đặc biệt, trong đó miền giá trị chỉ bao gồm hai phần tử, thường được biểu thị dưới dạng Yes/No, Nam/Nữ, hoặc True/False.
Phân loại các kiểu dữ liệu dựa trên hệ đo
Giả sử có hai đối tượng x và y, mỗi đối tượng đều có các thuộc tính tương ứng là x i và y i Chúng ta có thể xác định các lớp kiểu dữ liệu cho các thuộc tính này.
Thuộc tính định danh (nominal scale) là một dạng thuộc tính khái quát của thuộc tính nhị phân, với miền giá trị rời rạc và không phân biệt thứ tự Nó có thể chứa nhiều hơn hai phần tử, cho phép xác định mối quan hệ giữa các đối tượng thuộc tính, trong đó chỉ có thể phân loại là x khác y hoặc x bằng y.
Thuộc tính có thứ tự (Ordinal Scale) là loại thuộc tính định danh có tính thứ tự, nhưng không thể định lượng Khi so sánh hai thuộc tính thứ tự x và y, ta có thể xác định được mối quan hệ giữa chúng như x > y, x < y hoặc x = y.
Thuộc tính khoảng (Interval Scale) được sử dụng để đo các giá trị theo xấp xỉ tuyến tính, cho phép xác định thứ tự và khoảng cách giữa các thuộc tính Với thuộc tính này, nếu x i > y i, ta có thể nói rằng x cách y một khoảng xi – yi Một ví dụ điển hình về thuộc tính khoảng là số Serial của một đầu sách trong thư viện.
Thuộc tính tỉ lệ (Ratio Scale) là loại thuộc tính có khoảng cách xác định, nhưng được căn cứ vào một điểm mốc có ý nghĩa, chẳng hạn như chiều cao hoặc cân nặng, trong đó điểm 0 được coi là mốc quan trọng.
Trong các thuộc tính dữ liệu, thuộc tính định danh và thuộc tính có thứ tự được gọi là thuộc tính hạng mục (Categorical), trong khi thuộc tính khoảng và thuộc tính tỉ lệ được phân loại là thuộc tính số (Numeric).
Dữ liệu không gian (Spatial Data) là loại dữ liệu quan trọng, có các thuộc tính số khái quát trong không gian nhiều chiều, mô tả thông tin liên quan đến các đối tượng trong không gian như hình học Dữ liệu không gian có thể được phân loại thành dữ liệu liên tục hoặc rời rạc, thể hiện sự đa dạng và phong phú trong việc phân tích và ứng dụng thông tin không gian.
Dữ liệu không gian rời rạc là các điểm trong không gian nhiều chiều, giúp xác định khoảng cách giữa các đối tượng dữ liệu.
-Dữ liệu không gian liên tục: bao chứa một vùng trong không gian
Các thuộc tính số thường được đo bằng các đơn vị xác định như kilogam hoặc centimet, nhưng các đơn vị đo này có thể ảnh hưởng đến kết quả phân cụm Ví dụ, việc chuyển đổi đơn vị cân nặng từ kilogam sang pound có thể dẫn đến những kết quả phân cụm khác nhau Để khắc phục vấn đề này, cần phải chuẩn hoá dữ liệu, tức là sử dụng các thuộc tính dữ liệu không phụ thuộc vào đơn vị đo Quy trình chuẩn hoá dữ liệu thường được thực hiện bằng cách thay thế mỗi thuộc tính bằng thuộc tính số hoặc thêm trọng số cho các thuộc tính, tùy thuộc vào ứng dụng và nhu cầu của người dùng.
Khái niệm về tương tự và phi tương tự
Khi xác định các đặc tính của dữ liệu, cần tìm cách đo "khoảng cách" giữa các đối tượng, tức là xác định sự tương tự hoặc phi tương tự giữa chúng Các hàm đo này thường tính độ tương tự (Similar) hoặc độ phi tương tự (Dissimilar), với giá trị cao của hàm tương tự cho thấy sự giống nhau lớn giữa các đối tượng Ngược lại, hàm phi tương tự tỉ lệ nghịch với hàm tương tự Sự tương tự và phi tương tự có thể được xác định qua khoảng cách giữa các đối tượng, và phương pháp đo này phụ thuộc vào loại thuộc tính đang phân tích Ví dụ, với thuộc tính hạng mục (Categorical), không sử dụng khoảng cách mà áp dụng hướng hình học của dữ liệu.
Tất cả các độ đo được xác định trong không gian metric, trong đó thuật ngữ "độ đo" chỉ hàm tính độ tương tự hoặc độ phi tương tự Một không gian metric là tập hợp có thể xác định khoảng cách giữa các cặp phần tử, tuân theo các tính chất của khoảng cách hình học Tập X, với các đối tượng dữ liệu trong CSDL D, được gọi là không gian metric nếu đáp ứng các tiêu chí nhất định.
Với mỗi cặp phần tử x, y thuộc 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 thoả mãn hệ tính chất sau: (i)δ(x, y)>0 nếu x ≠y ; (ii)δ(x, y)=0 nếu =y; (iii) δ(x, y) = δ(y, x) với mọi x, y; (iv) δ(x, y) ≤ δ(x, z)+δ(z, y)
Hàm δ(x, y) được gọi là một metric của không gian Các phần tử của X được gọi là các điểm của không gian nà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:
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 như sau:
, trong đó q là số tự nhiên dương
( , đây là trường hợp đặc biệt của khoảng cách Minskowski trong trường hợp q=2
| ) , ( , đây là trường hợp đặc biệt của khoảng cách Minskowski trong trường hợp q=1
Max i i n y i x d , đâ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: Trước hết chúng ta có xây dựng bảng tham số sau:
Trong bài viết này, chúng ta sẽ xem xét các đối tượng x và y, trong đó tất cả các thuộc tính của chúng đều có giá trị nhị phân, biểu thị bằng 0 và 1 Bảng thông tin cung cấp cho chúng ta các chỉ số quan trọng: tổng số thuộc tính có giá trị 1 trong cả hai đối tượng x và y; tổng số thuộc tính có giá trị 1 trong x nhưng 0 trong y; tổng số thuộc tính có giá trị 0 trong x nhưng 1 trong y; và tổng số thuộc tính có giá trị 0 trong cả x và y.
Các phép đo độ tương tương đồng đố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 ) , ở đâ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, ký hiệu là d(x, y), là một chỉ số quan trọng trong phân tích dữ liệu, đặc biệt khi bỏ qua các đối sánh giữa 0-0 Công thức tính hệ số này rất hữu ích trong các trường hợp mà trọng số của các thuộc tính có giá trị 1 vượt trội so với các thuộc tính có giá trị 0, cho thấy tính không đối xứng của các thuộc tính nhị phân.
Độ đo phi tương tự giữa hai đối tượng x và y được xác định qua công thức d(x, y) = m/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.
Phép đo độ phi tương tự giữa các đối tượng dữ liệu với thuộc tính có thứ tự được thực hiện bằng cách xem xét thuộc tính thứ tự i với Mi giá trị, trong đó Mi đại diện cho kích thước miền giá trị.
Các trạng thái Mi được sắp xếp theo thứ tự từ 1 đến Mi Chúng ta có khả năng thay thế mỗi giá trị của thuộc tính bằng một giá trị tương ứng r i, với r i nằm trong khoảng từ 1 đến Mi.
Mỗi thuộc tính có thứ tự và các miền giá trị khác nhau, do đó chúng ta cần chuyển đổi chúng về cùng một miền giá trị [0, 1] Việc này được thực hiện thông qua các phép biến đổi cho từng thuộc tính.
Sử dụng công thức tính độ phi tương tự cho các giá trị z i ( j ) giúp xác định độ phi tương tự của thuộc tính khoảng, tương tự như độ phi tương tự của thuộc tính có thứ tự.
Để tính độ tương tự giữa các thuộc tính tỉ lệ, có thể áp dụng nhiều phương pháp khác nhau, trong đó sử dụng công thức logarit cho mỗi thuộc tính x_i là một lựa chọn hiệu quả Cụ thể, ta có thể tính q_i = log(x_i), giúp biến q_i trở thành thuộc tính khoảng (Interval-Scale) Phép biến đổi logarit này đặc biệt phù hợp khi các giá trị của thuộc tính có dạng số mũ.
Khi tính toán độ đo tương tự của dữ liệu, người ta thường chỉ xem xét một phần các thuộc tính đặc trưng hoặc gán trọng số cho tất cả các thuộc tính Để loại bỏ đơn vị đo của các thuộc tính, có thể chuẩn hóa chúng hoặc gán trọng số dựa trên giá trị trung bình và độ lệch chuẩn Các trọng số này được áp dụng trong các độ đo khoảng cách, trong đó độ tương đồng dữ liệu được xác định bằng công thức n i w i x i y i y x d, với mỗi thuộc tính dữ liệu được gán trọng số tương ứng w i (1 ≤ i ≤ k).
Có thể chuyển đổi giữa các mô hình dữ liệu, chẳng hạn như chuyển đổi dữ liệu kiểu hạng mục thành dữ liệu nhị phân và ngược lại Tuy nhiên, giải pháp này có chi phí tính toán cao, vì vậy cần cân nhắc kỹ lưỡng khi áp dụng.
Tùy thuộc vào từng trường hợp dữ liệu cụ thể, việc lựa chọn mô hình tính độ tương tự phù hợp là rất quan trọng Sự chính xác và khách quan trong việc xác định độ tương đồng dữ liệu không chỉ góp phần nâng cao hiệu quả của thuật toán PCDL mà còn đảm bảo chất lượng và tối ưu hóa chi phí tính toán.
Ứng dụng của phân cụm dữ liệu
Phân cụm DL là công cụ quan trọng được sử dụng rộng rãi trong các lĩnh vực thương mại và khoa học Kỹ thuật PCDL đã được áp dụng thành công trong nhiều ứng dụng điển hình, thể hiện tính đa dạng và hiệu quả của nó trong các lĩnh vực này.
Trong thương mại, PCDL hỗ trợ các thương nhân nhận diện các nhóm khách hàng quan trọng với những đặc điểm tương đồng, đồng thời phân tích họ dựa trên các mẫu giao dịch trong cơ sở dữ liệu khách hàng.
Trong sinh học, PCDL đóng vai trò quan trọng trong việc xác định các loại sinh vật, phân loại các gen có chức năng tương đồng và phân tích cấu trúc trong các mẫu.
Phân tích dữ liệu không gian trở nên khó khăn do khối lượng lớn dữ liệu từ hình ảnh vệ tinh, thiết bị y học và hệ thống thông tin địa lý (GIS) PCDL hỗ trợ người dùng tự động phân tích và xử lý dữ liệu không gian, giúp nhận dạng và chiết xuất các đặc tính cũng như mẫu dữ liệu quan tâm trong cơ sở dữ liệu không gian.
Lập quy hoạch đô thị: Nhận dạng các nhóm nhà theo kiểu và vị trí địa lý, …nhằm cung cấp thông tin cho quy hoạch đô thị
Nghiên cứu trái đất bao gồm việc phân cụm để theo dõi các tâm động đất, nhằm cung cấp thông tin quan trọng cho việc nhận dạng các vùng nguy hiểm Bên cạnh đó, địa lý cũng liên quan đến việc phân lớp các động vật và thực vật, từ đó đưa ra những đặc trưng nổi bật của chúng.
Web Mining: PCDL có khả năng phát hiện các nhóm tài liệu quan trọng, mang lại nhiều giá trị trong môi trường trực tuyến Những lớp tài liệu này hỗ trợ quá trình khám phá tri thức từ dữ liệu một cách hiệu quả.
PHÂN CỤM DỮ LIỆU PHÂN HOẠCH
Giới thiệu
Có nhiều kỹ thuật phân cụm dữ liệu khác nhau, và việc lựa chọn phương pháp phù hợp phụ thuộc vào yêu cầu cụ thể của từng trường hợp Bài đồ án này sẽ tập trung vào kỹ thuật phân cụm dữ liệu phân hoạch, nghiên cứu trong bối cảnh cơ sở dữ liệu không gian tĩnh có chứa nhiễu.
Phương pháp phân cụm phân hoạch chia một tập dữ liệu n phần tử thành k nhóm, đảm bảo mỗi phần tử chỉ thuộc một nhóm và mỗi nhóm có ít nhất một phần tử Các thuật toán phân hoạch có độ phức tạp cao khi tìm nghiệm tối ưu toàn cục, do phải xem xét mọi cách phân hoạch khả thi Do đó, thường áp dụng giải pháp tối ưu cục bộ bằng cách sử dụng hàm tiêu chuẩn để đánh giá chất lượng các cụm và hướng dẫn tìm kiếm Quá trình này thường bắt đầu bằng việc khởi tạo phân hoạch ngẫu nhiên hoặc theo heuristic, sau đó tinh chỉnh cho đến khi đạt được phân hoạch mong muốn Các thuật toán này cải tiến tiêu chuẩn phân cụm bằng cách tính toán độ tương tự giữa các đối tượng dữ liệu, sắp xếp các giá trị và chọn giá trị tối ưu để đạt được giá trị tối thiểu cho hàm tiêu chuẩn Ý tưởng chính của thuật toán là sử dụng chiến lược tham lam (Greedy) để tìm kiếm nghiệm.
Một số thuật toán phân cụm phân hoạch điển hình như : K-MEANS,
Thuật toán K-MEANS là một phương pháp mạnh mẽ để phân cụm dữ liệu lớn, nhưng chỉ hiệu quả với dữ liệu có thuộc tính số và thường phát hiện các cụm hình cầu Tuy nhiên, K-MEANS rất nhạy cảm với nhiễu và các điểm dữ liệu ngoại lai, điều này có thể ảnh hưởng đến chất lượng phân cụm Ngoài ra, kết quả phân cụm phụ thuộc nhiều vào các tham số đầu vào, đặc biệt là số cụm k và các trọng tâm khởi tạo ban đầu.
Thuật toán PAM được thiết kế để khắc phục nhược điểm của thuật toán KMEANS, đặc biệt là khả năng xử lý hiệu quả dữ liệu nhiễu và các phần tử ngoại lai Mặc dù PAM phù hợp với dữ liệu không gian, nhưng nó gặp khó khăn về thời gian tính toán khi giá trị của k và n tăng cao.
Thuật toán CLARA được thiết kế để khắc phục nhược điểm của thuật toán PAM khi số lượng giá trị k và n lớn Phương pháp của CLARA bao gồm việc lấy mẫu từ tập dữ liệu có n phần tử, sau đó áp dụng thuật toán PAM cho mẫu này để xác định các đối tượng tâm medoid từ dữ liệu được trích xuất.
Thuật toán CLARANS được thiết kế nhằm cải thiện chất lượng và mở rộng khả năng áp dụng cho các tập dữ liệu lớn CLARANS sử dụng các đối tượng trung tâm medoid để đại diện cho các cụm dữ liệu Một trong những ưu điểm nổi bật của CLARANS là không gian tìm kiếm không bị giới hạn như ở CLARA, đồng thời trong cùng một khoảng thời gian, chất lượng của các cụm phân được tạo ra từ CLARANS thường cao hơn so với CLARA.
Thuật toán K-means
Thuật toán K-means, được đề xuất bởi MacQueen vào năm 1967 trong lĩnh vực thống kê, nhằm mục đích phân chia một tập dữ liệu chứa n đối tượng trong không gian d chiều thành k cụm dữ liệu {C1, C2, …, Ck}.
= (xi1, xi2, …, x id ) ( i 1 , n ), sao cho hàm tiêu chuẩn: k i x C x i
2 ( ) đạt giá trị tối thiểu
Trọng tâm của một cụm là một véc tơ, với giá trị mỗi phần tử là trung bình cộng của các thành phần tương ứng trong các đối tượng vectơ dữ liệu của cụm Thuật toán yêu cầu đầu vào là số cụm k, và đầu ra là các trọng tâm của cụm dữ liệu Khoảng cách D giữa các đối tượng dữ liệu thường được đo bằng khoảng cách Euclide, do tính dễ dàng trong việc lấy đạo hàm và xác định cực trị tối thiểu Hàm tiêu chuẩn và độ đo khoảng cách có thể được điều chỉnh tùy theo ứng dụng hoặc quan điểm của người dùng.
Thuật toán k-means bao gồm các bước cơ bản như sau:
Bước 1 Chọn k phần tử ban đầu k j z j 1 của D làm tâm các cụm con
Bước 2 Với mỗi i = 1, ., N ; xếp x i vào cụm Cj nếu: d(x i , z j )= min d ( x i , z q ) / q k
Bước 3 Tính trung bình cộng của các phần của các cụm C j làm tâm mới:
, trong đó C j là số phần tử của cụm C j
Bước 4 Trở lại bước 2 để xếp lại các cụm con nhờ tâm mới cho tới khi các cụm không thay đổi
Nếu mêtric được dùng là mêtric Euclide thì thuật toán hội tụ tới cực tiểu địa phương của hàm: k j
Thuật toán k-means chi tiết được trình bày như sau:
1 Write (“Nhập số đối tượng dữ liệu”);readln(n);
2 Nhập n đối tượng dữ liệu;
3 Write (“Nhập số cụm dữ liệu”);readln(k);
5 For i = 1 to k do mi = xi+(i-1)*[n/k]; //Khởi tạo k trọng tâm
Tính toán khoảng cách Euclide
16 Tìm trọng tâm gần nhất m h tới X i
Các khái niệm biến và hàm sử dụng trong thuật toán k-means trong hình 9 như sau:
MSE (Sai số bình phương trung bình) là một hàm tiêu chuẩn được sử dụng để lưu trữ giá trị của sai số và cập nhật sau mỗi lần lặp Thuật toán sẽ dừng lại khi giá trị MSE tăng so với giá trị MSE của vòng lặp trước đó.
D 2 (x i , m j ): là khoảng cách Euclide từ đối tượng dữ liệu thứ i tới trọng tâm thứ j;
OldMSE, m' j, n' j là các biến tạm lưu trữ giá trị cho các trạng thái trung gian tương ứng Chúng bao gồm giá trị của hàm tiêu chuẩn, tổng giá trị của các đối tượng trong cụm thứ j, và số lượng đối tượng trong cụm đó.
Thuật toán k-means đã được chứng minh là hội tụ với độ phức tạp tính toán là O((3 nkd) T flop), trong đó n là số đối tượng dữ liệu, k là số cụm, d là số chiều, và T flop là thời gian thực hiện một phép toán cơ bản như nhân hay chia Nhờ vào việc phân tích phân cụm đơn giản, k-means có thể được áp dụng hiệu quả cho các tập dữ liệu lớn.
Phương pháp k-mean có thể biểu diễn qua hình ảnh sau:
K-means có nhược điểm là chỉ hoạt động hiệu quả với dữ liệu số và phát hiện các cụm hình cầu, đồng thời nó rất nhạy cảm với nhiễu và các phần tử ngoại lai trong dữ liệu Hình 11 minh họa các hình dạng cụm dữ liệu mà k-means có thể khám phá.
Hình 11: Thí dụ về một số hình dạng cụm dữ liệu đƣợc khám phá bởi k-means
Chất lượng phân cụm dữ liệu của thuật toán k-means phụ thuộc vào các tham số đầu vào như số cụm k và các trọng tâm khởi tạo Nếu các trọng tâm khởi tạo quá lệch so với các trọng tâm tự nhiên, kết quả phân cụm sẽ không chính xác, dẫn đến việc các cụm dữ liệu không phản ánh thực tế Hiện tại, chưa có giải pháp tối ưu để chọn các tham số đầu vào, và phương pháp phổ biến nhất là thử nghiệm với nhiều giá trị k khác nhau để tìm ra giải pháp tốt nhất Nhiều thuật toán kế thừa từ k-means đã được phát triển để xử lý các tập dữ liệu lớn, bao gồm k-modes, PAM, CLARA, CLARANS và k-prototypes, và đang được áp dụng hiệu quả trong lĩnh vực Data Mining.
Thuật toán PAM
Thuật toán PAM (Partitioning Around Medoids) là một phiên bản mở rộng của k-means, được thiết kế để xử lý hiệu quả dữ liệu nhiễu và các phần tử ngoại lai, theo đề xuất của Kaufman và Rousseeuw Khác với k-means, PAM sử dụng các đối tượng medoid để đại diện cho các cụm dữ liệu, giúp giảm thiểu ảnh hưởng của các điểm dữ liệu xa trung tâm Quá trình bắt đầu bằng việc khởi tạo k đối tượng medoid, sau đó phân phối các đối tượng còn lại vào các cụm dựa trên sự tương đồng với các đối tượng medoid tương ứng.
Nếu Oj không phải là medoid và Om là medoid, thì Oj thuộc về cụm có medoid là Om nếu khoảng cách d(Oj, Om) là nhỏ nhất so với khoảng cách d(Oj, Oe) với mọi đối tượng Oe khác.
Oj và Oe, minOe là giá trị nhỏ nhất của độ phi tương tự giữa Oj và các đối tượng medoid trong cụm dữ liệu Chất lượng của mỗi cụm được đánh giá qua độ phi tương tự trung bình giữa đối tượng và medoid tương ứng, cho thấy rằng chất lượng phân cụm phụ thuộc vào các đối tượng medoid Độ phi tương tự thường được xác định bằng độ đo khoảng cách, với thuật toán PAM áp dụng cho dữ liệu không gian PAM bắt đầu bằng cách chọn k đối tượng medoid ngẫu nhiên và thực hiện hoán chuyển giữa đối tượng medoid O m và một đối tượng không phải medoid Op, nhằm cải thiện chất lượng phân cụm Quá trình này dừng lại khi chất lượng phân cụm không còn thay đổi Chất lượng phân cụm được đánh giá thông qua hàm tiêu chuẩn, với chất lượng tốt nhất khi hàm tiêu chuẩn đạt giá trị tối thiểu.
Cụ thể ta xét ví dụ sau:
Trong quá trình phân cụm, chúng ta xem xét hai đối tượng medoid A và B Đối với mọi đối tượng Y thuộc cụm có medoid A, chúng ta tìm medoid của cụm gần nhất để thay thế Có hai trường hợp có thể xảy ra: Y có thể được chuyển tới cụm B, trong trường hợp này, chúng ta có thể di chuyển chúng tới cụm có đại diện là M, hoặc Y có thể giữ nguyên ở lại cụm B.
Thí dụ này có thể biểu diễn như hình 12 dưới đây:
Hình 12: Thí dụ về các khả năng thay thế các đối tƣợng tâm medoid
Sau đây là một số khái niệm biến được sử dụng cho thuật toán PAM:
Om : Là đối tượng medoid hiện thời cần được thay thế
Op: là đối tượng medoid mới thay thế cho Om;
Oj: Là đối tượng dữ liệu (không phải là medoid) có thể được di chuyển sang cụm khác
Oj, 2: Là đối tượng medoid hiện thời gần đối tượng O j nhất mà không phải là các đối tượng A và M như trong ví dụ trên
Trong bốn trường hợp được mô tả, PAM tính toán giá trị Cjmp cho tất cả các đối tượng O j Giá trị Cjmp này được sử dụng làm cơ sở cho việc hoán chuyển giữa các đối tượng.
O m và O p Các cách tính Trong mỗi trường hợp C jmp được tính với 4 cách khác nhau như sau:
Trường hợp 1: Giả sử Oj hiện thời thuộc về cụm có đại diện là Om và
Oj tương tự với Oj, 2 hơn Op (d(Oj, Op) d(Oj, Oj, 2)) Trong khi đó, Oj, 2 là đối
Case 4 này, chúng ta thay thế O m bởi đối tượng medoid mới Op và Oj sẽ thuộc về cụm có đối tượng đại diện là Oj, 2 Vì vậy, giá trị hoán chuyển Cjmp được xác định như sau:
Giá trị C jmp là không âm
Trong trường hợp 2, Oj thuộc về cụm có đại diện là Om, nhưng sự tương đồng giữa Oj và Om lại thấp hơn so với Op (tức là d(Oj, Op) < d(Oj, Om)) Nếu Om được thay thế bởi Op, thì Oj sẽ trở thành thành viên của cụm đại diện là Op Do đó, giá trị Cjmp được xác định theo công thức: Cjmp = (Oj, Op) - d(Oj, Om) Giá trị Cjmp có thể là âm hoặc dương.
Trong trường hợp 3, giả sử Oj không thuộc về cụm đại diện Om mà thuộc về cụm có đại diện Oj, 2 Nếu Oj tương tự hơn với Oj, 2 so với Op, thì khi Om được thay thế bằng Op, Oj vẫn giữ vị trí trong cụm đại diện Oj, 2 Do đó, giá trị Cjmp sẽ bằng 0.
Trong trường hợp 4, Oj hiện tại thuộc về cụm có đại diện là Oj,2, nhưng Oj lại ít tương tự với Oj,2 hơn so với Op Do đó, khi thay thế Om bằng Op, Oj sẽ chuyển từ cụm Oj,2 sang cụm Op Giá trị hoán chuyển Cjmp được xác định là Cjmp = (Oj, Op) - d(Oj, Oj,2), và giá trị Cjmp này luôn âm.
Kết hợp cả bốn trường hợp trên, tổng giá trị hoán chuyển Om bằng Op được xác định như sau: TC mp j
C jmp (5) Sử dụng các khái niệm trên, thuật toán PAM có các bước thực hiện như hình 13 sau:
Hình 13: Các bước thực hiện của thuật toán PAM
Trong bước 2 và 3, PAM cần duyệt tất cả k(n-k) cặp Om và Op, và để tính toán TC mp cho mỗi cặp, cần kiểm tra n-k đối tượng Do đó, độ phức tạp tính toán của PAM là O(Ik(n-k)²), với I là số vòng lặp Vì vậy, thuật toán PAM trở nên kém hiệu quả về thời gian tính toán khi giá trị của k và n lớn.
Sau đây là hình ảnh mô phỏng vấn đề phân cụm dữ liệu của thuật toán K- MEANS và PAM:
Input: Tập dữ liệu có n phần tử, số cụm k
Out Put: k cụm dữ liệu sao cho chất lượng phân hoạch là tốt nhất
Bước 1: Chọn k đối tượng medoid bất kỳ;
Bước 2: Tính TCmp cho tất cả các cặp đối tượng Om, Op Trong đó Om là đối tượng medoid và Op là đối tượng không phải là modoid
Bước 3: Chọn cặp đối tượng O m và Op Tính minOm, minOp, TCmp
Nếu TCmp là âm, thay thế Om bởi Op và quay lại bước 2 Nếu TCmp dương, chuyển sang bước 4
Bước 4: Với mỗi đối tượng không phải là medoid, xác định đối tượng medoid tương tự với nó nhất đồng thời gán nhãn cụm cho chúng
Hình 14: Mô phỏng kết quả của 2 thuật toán k-means và pam
- Hình (a) là mô phỏng dữ liệu ban đầu
- Hình (b) là mô phỏng kết quả phân cụm dữ liệu sau khi áp dụng thuật toán k-means
- Hình (c) là mô phỏng kết quả phân cụm dữ liệu của thuật toán pam
CLARA (Clustering LARge Application) được Kaufman đề xuất năm
Vào năm 1990, thuật toán CLARA được phát triển để khắc phục nhược điểm của thuật toán PAM khi giá trị k và n lớn Thuật toán này thực hiện trích mẫu từ tập dữ liệu có n phần tử, áp dụng PAM cho mẫu này để xác định các đối tượng tâm medoid Kết quả phân cụm tốt nhất được chọn từ các mẫu, và chất lượng của các cụm được đánh giá dựa trên độ phi tương tự trung bình của toàn bộ đối tượng trong tập dữ liệu ban đầu Các thực nghiệm cho thấy rằng 5 mẫu dữ liệu với kích thước 40+2k mang lại kết quả tốt.
Các bước thực hiện của thuật toán CLARA như hình 15 sau
2 Lấy một mẫu có 40 + 2k đối tượng dữ liệu ngẫu nhiên từ tập dữ liệu và áp dụng thuật toán PAM cho mẫu dữ liệu này nhằm để tìm các đối tượng medoid đại diện cho các cụm
3 Đối với mỗi đối tượng O j trong tập dữ liệu ban đầu, xác định đối tượng medoid tương tự nhất trong số k đối tượng medoid
4 Tính độ phi tương tự trung bình cho phân hoạch các đối tượng dành ở bước trước, nếu giá trị này bé hơn giá trị tối thiểu hiện thời thì sử dụng giá trị này thay cho giá trị tối thiếu ở trạng thái trước, như vậy, tập k đối tượng medoid xác định ở bước này là tốt nhất cho đến thời điểm này
Thuật toán CLARA có độ phức tạp tính toán O(k(40+k)² + k(n-k)), cho phép xử lý tập dữ liệu lớn Một điểm cần lưu ý trong kỹ thuật tạo mẫu trong PCDL là kết quả phân cụm có thể không phụ thuộc vào tập dữ liệu khởi tạo, tuy nhiên chỉ đạt được tối ưu cục bộ Ví dụ, nếu các đối tượng medoid của dữ liệu khởi tạo không nằm trong mẫu, kết quả thu được có thể không phải là tốt nhất.
Thuật toán CLARANS, được Ng & Han giới thiệu vào năm 1994, nhằm cải thiện chất lượng và mở rộng khả năng áp dụng cho các tập dữ liệu lớn Thuật toán này sử dụng các đối tượng trung tâm medoids để đại diện cho các cụm dữ liệu.
CÀI ĐẶT CHƯƠNG TRÌNH
Bài toán
Input: Có một tập rất lớn các điểm ảnh và phân ra làm k cụm
Output: Các nhóm (cụm) điểm ảnh, trong đó các điểm ảnh có cùng màu sẽ được gom vào một nhóm
Thuật toán phân cụm phân hoạch (kmean, pam) với các dữ liệu đầu vào là các điểm ảnh có 2 trường giá trị:
Giới thiệu chương trình ứng dụng
Chương trình được viết bằng ngôn ngữ visual C++, chạy trên visual studio 2008
Khi chạy chương trình, các điểm ảnh sẽ được gọi ra và chúng ta sẽ chọn số cụm từ khung bên Chương trình sẽ thực hiện thuật toán KMEANS và PAM để tiến hành phân cụm, với kết quả được trình bày như sau:
Hình 10: Yêu cầu nhập số cụm
Chương trình này thực hiện phân cụm trên một bài toán cụ thể, cho phép kiểm nghiệm kết quả của các thuật toán phân cụm dữ liệu như KMEANS và PAM.
Chương trình đã hoạt động hiệu quả, phân cụm các điểm ảnh dựa trên số cụm do người dùng nhập Một trong những ưu điểm nổi bật của chương trình là thời gian chạy nhanh, cho phép xử lý trên cơ sở dữ liệu lớn một cách dễ dàng.
Mặc dù thuật toán đã có những tiến bộ, nhưng vẫn tồn tại những hạn chế nhất định, đặc biệt là việc người dùng phải nhập tham số k, điều này ảnh hưởng đến hiệu quả và tính tự động của thuật toán.