PHÂN CỤM DỮ LIỆU
Kỹ thuật phân cụm dữ liệu
PCDL là một kỹ thuật trong khai thác dữ liệu (Data Mining) được sử dụng để phát hiện và tìm kiếm các cụm, mẫu dữ liệu tự nhiên tiềm ẩn trong các tập dữ liệu lớn Kỹ thuật này giúp cung cấp thông tin và tri thức hữu ích, hỗ trợ quá trình ra quyết định hiệu quả.
Mục tiêu chính của phương pháp phân cụm dữ liệu là tổ chức các đối tượng tương tự trong tập dữ liệu thành các cụm, đảm bảo rằng các đối tượng trong cùng một lớp có sự tương đồng cao với nhau.
Các đối tượng trong cùng một cụm sẽ có sự tương đồng, trong khi các đối tượng thuộc các cụm khác nhau sẽ không tương đồng Phân cụm dữ liệu là một kỹ thuật quan trọng, thường được áp dụng trong các lĩnh vực như phân loại văn bản, phân đoạn khách hàng, nhận dạng mẫu và phân loại trang web.
Các ứng dụng của phân cụm dữ liệu
Một số ứng dụng điển hình phân cụm dữ liệu trong các lĩnh vực sau:
Trong lĩnh vực 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 lĩnh vực sinh học, PCDL được áp dụng để 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à thu thập các cấu trúc từ các mẫu.
Phân tích dữ liệu không gian là một ứng dụng quan trọng của PCDL, giúp người dùng tự động nhận dạng và chiết xuất các đặc tính, cũng như các 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 thông qua việc phân cụm các tâm động đất giúp nhận diện các vùng nguy hiểm Trong lĩnh vực địa lý, việc phân lớp động vật và thực vật cùng với đặc trưng của chúng là rất quan trọng Bên cạnh đó, Web Mining cho phép PCDL khám phá các nhóm tài liệu quan trọng trên môi trường Web, từ đó hỗ trợ việc khai thác tri thức từ dữ liệu một cách hiệu quả.
Các kiểu dữ liệu và độ đo tương tự
Phân cụm dữ liệu là quá trình chia nhỏ một tập dữ liệu thành các nhóm sao cho các đối tượng trong cùng một nhóm có sự tương đồng cao Để thực hiện điều này, cần tính toán "khoảng cách" hoặc độ tương tự giữa các đối tượng nhằm phân loại chúng vào các nhóm khác nhau Hàm tính độ tương tự cho phép xác định mức độ tương đồng giữa hai đối tượng: giá trị cao hơn cho thấy sự tương đồng lớn hơn, trong khi hàm tính độ phi tương tự lại tỉ lệ nghịch với hàm tính độ tương tự.
Trong PCDL, các kiểu dữ liệu phổ biến bao gồm con người, nhà cửa, tiền lương và các thực thể phần mềm Những đối tượng này thường được mô tả thông qua các thuộc tính liên quan của chúng, giúp quá trình phân tích trở nên hiệu quả hơn.
Có 2 cách phân loại các kiểu thuộc tính: Dựa trên kích thước miền (Domain size) & Dựa trên hệ đo (Measurement Scale)
1.3.1 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à những thuộc tính mà giữa hai giá trị có vô số giá trị khác tồn tại 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) được định nghĩa là thuộc tính có miền giá trị là một tập hữu hạn và có thể đếm được Ví dụ điển hình cho loại thuộc tính này bao gồm số serial của một cuốn sách và số thành viên trong một gia đình.
Lớp các thuộc tính nhị phân là một dạng đặc biệt của thuộc tính rời rạc, với miền giá trị chỉ bao gồm hai phần tử, thường được biểu thị dưới dạng: Có/Không, Nam/Nữ, hoặc Đúng/Sai.
1.3.2 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, y và các thuộc tính x i , y i tương ứng với thuộc tính thứ i của chúng Chúng ta có các lớp kiểu dữ liệu nhƣ sau:
Thuộc tính định danh (nominal scale) cho phép xác định sự khác biệt giữa các đối tượng, ví dụ như nơi sinh hoặc các đội bóng trong giải vô địch quốc gia Việt Nam, với chỉ hai khả năng là x=y hoặc x≠y Trong khi đó, thuộc tính có thứ tự (ordinal scale) không chỉ phân biệt mà còn sắp xếp các đối tượng theo thứ tự, mặc dù không thể định lượng chính xác Ví dụ, thuộc tính huy chương của vận động viên thể thao cho phép so sánh thứ hạng, với các mối quan hệ như x>y, x yi, ta có thể nói rằng x cách y một khoảng là xi – yi Ví dụ điển hình về thuộc tính khoảng là số kênh trên truyền hình, nơi mà sự khác biệt giữa các giá trị có thể được đo lường một cách chính xác.
Thuộc tính tỉ lệ (Ratio Scale) là loại thuộc tính khoảng, nhưng được xác định một cách tương đối dựa trên 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 đóng vai trò là mốc tham chiếu.
Thuộc tính định danh và thuộc tính có 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ệ đƣợc gọi là thuộc tính số.
Một số kỹ thuật tiếp cận trong phân cụm dữ liệu
Các kỹ thuật phân cụm dữ liệu nhằm đạt được hai mục tiêu chính: nâng cao chất lượng các cụm được khám phá và tối ưu hóa tốc độ thực hiện của thuật toán Hiện nay, các phương pháp phân cụm dữ liệu có thể được phân loại theo các cách tiếp cận chủ yếu.
Chúng ta cần phân chia một tập dữ liệu gồm n phần tử thành k nhóm khác nhau, đảm bảo rằng mỗi phần tử chỉ thuộc về một nhóm duy nhất và mỗi nhóm ít nhất phải có một phần tử.
Một số thuật toán phân cụm phân hoạch điển hình nhƣ k-means, PAM, CLARA, CLARANS,…
1.4.2 Phân cụm dữ liệu phân cấp
Phân cụm phân cấp tổ chức một tập dữ liệu thành một cấu trúc dạng cây, được xây dựng thông qua kỹ thuật đệ quy Có hai phương pháp tổng quát để xây dựng cây phân cụm.
Phương pháp "dưới lên" (Bottom up) bắt đầu bằng việc nhóm các đối tượng có độ đo tương tự, như khoảng cách giữa hai trung tâm của hai nhóm Quá trình này tiếp tục cho đến khi tất cả các nhóm được hòa nhập thành một nhóm duy nhất, đạt đến mức cao nhất của cây phân cấp, hoặc cho đến khi các điều kiện kết thúc được thỏa mãn Cách tiếp cận này áp dụng chiến lược ăn tham trong quá trình phân cụm.
Phương pháp "trên xuống" (Top Down) bắt đầu bằng việc xếp tất cả các đối tượng vào một cụm duy nhất Qua mỗi vòng lặp, cụm này sẽ được tách thành các cụm nhỏ hơn dựa trên giá trị của một phép đo độ tương tự cho đến khi mỗi đối tượng trở thành một cụm riêng lẻ hoặc khi điều kiện dừng được thỏa mãn Cách tiếp cận này áp dụng chiến lược chia để trị trong quá trình phân cụm.
Thí dụ: Hình 4 dưới đây là một thí dụ sử dụng hai chiến lược phân cụm phân cấp khác nhau nhƣ đã trình bày ở trên
Hình 4: Các chiến lƣợc phân cụm phân cấp
Một số thuật toán phân cụm phân cấp điển hình nhƣ CURE, BIRCH, …
1.4.3 Phân cụm dữ liệu dựa trên mật độ
Phương pháp này phân loại các đối tượng dựa trên hàm mật độ xác định, trong đó mật độ được hiểu là số lượng các đối tượng lân cận của một đối tượng dữ liệu theo một ngưỡng nhất định.
Một số thuật toán PCDL dựa trên mật độ điển hình nhƣ DBSCAN, OPTICS, DENCLUE, …
1.4.4 Phân cụm dữ liệu dựa trên lưới
Phương pháp này chủ yếu tập trung áp dụng cho lớp dữ liệu không gian
Bước 4 Bước 3 Bước 2 Bước 1 Bước 0
Một số thuật toán PCDL dựa trên cấu trúc lưới điển hình như: STING,
1.4.5 Phân cụm dữ liệu dựa trên mô hình
Có hai tiếp cận chính: Mô hình thống kê và Mạng Nơ ron
1.4.6 Phân cụm dữ liệu có ràng buộc Để phân cụm dữ liệu không gian hiệu quả hơn, các nghiên cứu bổ sung cần được thực hiện để cung cấp cho người dùng khả năng kết hợp các ràng buộc trong thuật toán phân cụm.
Các yêu cầu cho kỹ thuật PCDL
Hầu hết các nghiên cứu và phát triển thuật toán phân cụm dữ liệu đều nhằm thoả mãn các yêu cầu cơ bản sau:
Khả năng mở rộng (Scalability) là yếu tố quan trọng trong việc lựa chọn thuật toán, vì một số thuật toán có thể hoạt động hiệu quả trên tập dữ liệu nhỏ (khoảng 200 bản ghi), nhưng lại không đáp ứng tốt khi xử lý tập dữ liệu lớn (khoảng 1 triệu bản ghi).
Thuật toán có khả năng thích nghi với nhiều kiểu dữ liệu khác nhau, bao gồm dữ liệu số, dữ liệu nhị phân và dữ liệu hạng mục Điều này cho phép thuật toán phân cụm hiệu quả các tập dữ liệu đa dạng, kể cả khi chúng chứa sự kết hợp của các loại dữ liệu khác nhau.
Khám phá các cụm dữ liệu với hình thù đa dạng là rất quan trọng, vì hầu hết các cơ sở dữ liệu chứa nhiều cụm có hình dạng khác nhau như hình lõm, hình cầu, và hình que Để nhận diện các cụm tự nhiên, các thuật toán phân cụm cần phải có khả năng phát hiện những hình thù này một cách hiệu quả.
Để xác định các tham số đầu vào cho thuật toán phân cụm, cần có một lượng tri thức tối thiểu, vì các giá trị đầu vào thường có ảnh hưởng lớn đến kết quả và việc xác định giá trị phù hợp cho các cơ sở dữ liệu lớn là rất phức tạp Hơn nữa, thuật toán phân cụm ít nhạy cảm với thứ tự dữ liệu đầu vào; điều này có nghĩa là, khi xử lý cùng một tập dữ liệu với các thứ tự khác nhau, kết quả phân cụm không bị ảnh hưởng nhiều.
Khả năng thích nghi với dữ liệu nhiễu cao là một yếu tố quan trọng trong phân cụm dữ liệu Hầu hết dữ liệu trong Data Mining thường chứa lỗi, không đầy đủ và dữ liệu rác, vì vậy thuật toán phân cụm cần phải hiệu quả trong việc xử lý những dữ liệu này mà không làm giảm chất lượng kết quả Ngoài ra, thuật toán cũng nên ít nhạy cảm với các tham số đầu vào, tức là sự thay đổi của các tham số này không nên gây ra biến động lớn trong kết quả phân cụm.
Thích nghi với dữ liệu đa chiều: Thuật toán có khả năng áp dụng hiệu quả cho dữ liệu có số chiều khác nhau
Dễ hiểu, cài đặt và khả dụng
Các yêu cầu này cũng là tiêu chí đánh giá hiệu quả của các phương pháp phân cụm dữ liệu, đồng thời đặt ra thách thức cho các nhà nghiên cứu trong lĩnh vực PCDL.
Giới thiệu thuật toán phân cụm dữ liệu điển hình
Các thuật toán PCDL điển hình bao gồm: thuật toán phân cụm phân hoạch (Partition), thuật toán phân cụm phân cấp (Hierarchical), thuật toán phân cụm dựa trên lưới, cùng với các thuật toán phân cụm đặc thù khác như thuật toán phân cụm dựa trên mật độ và thuật toán phân cụm dựa trên mô hình.
Họ các thuật toán phân hoạch
Clustering algorithms, such as K-means, PAM (Partitioning Around Medoids), CLARA (Clustering Large Applications), and CLARANS (Clustering Large Applications), are widely used in practical applications for effective data partitioning.
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 thành k cụm dữ liệu {C1, C2, …, Ck} trong không gian d chiều, với mỗi đối tượng được biểu diễn dưới dạng vector Xi = (xi1, xi2, …, xid).
(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 Trong đó: mi là trọng tâm của cụm C i, D là khoảng cách giữa hai đối tƣợng
Trọng tâm của một cụm là 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 từ các đối tượng vectơ dữ liệu trong cụm Thuật toán k-means yêu cầu tham số đầu vào là số cụm k và cho ra tham số đầu ra là các trọng tâm của các cụm dữ liệu Để đo khoảng cách D giữa các đối tượng, thường sử dụng khoảng cách Euclide vì 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 thuộc vào ứng dụng và quan điểm của người dùng Thuật toán k-means thực hiện theo các bước cơ bản được mô tả trong hình.
Hình: Các bước thực hiện của thuật toán k-means
K-means biểu diễn các cụm bởi các trọng tâm của các đối tƣợng trong cụm đó do k-means phân tích phân cụm đơn giản nên có thể áp dụng đối với tập dữ liệu lớn Tuy nhiên, nhƣợc điểm của k-means là chỉ áp dụng với dữ liệu có thuộc tính số và khám ra các cụm có dạng hình cầu, k-means còn rất nhạy cảm với nhiễu và các phần tử ngoại lai trong dữ liệu
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 lệch so với các cụm tự nhiên, kết quả phân cụm sẽ kém, dẫn đến việc các cụm dữ liệu không phản ánh đúng 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.
InPut: Số cụm k và các trọng tâm cụm {mj} k j=1 ;
OutPut: Các cụm Ci (i 1,k) và hàm tiêu chuẩn E đạt giá trị tối thiểu;
Chọn k trọng tâm {m j } k j=1 ban đầu trong không gian R d (d là số chiều của dữ liệu) Việc lựa chọn này có thể là ngẫu nhiên hoặc theo kinh nghiệm
Bước 2: Tính toán khoảng cách giữa mỗi điểm X_i (1