Luận Văn: Phân Cụm Dựa Trên Tri Thức Theo Từng Cặp - Giải Pháp Tối Ưu

Chuyên khảo phân tích Luận văn phân cụm dựa trên tri thức theo từng cặp, đánh giá các khía cạnh quan trọng, đề xuất hướng nghiên cứu tiếp theo.

• Tác giả: Đỗ Văn Việt
• Người hướng dẫn: PGS. Hoàng Xuân Huấn
• Trường học: Đại học Công nghệ - Đại học Quốc gia Hà Nội
• Chuyên ngành: Hệ thống thông tin
• Đề tài: Phương Pháp Phân Cụm Dựa Trên Tri Thức Theo Từng Cặp Hiệu Quả
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2020
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• MỤC LỤC
• DANH MỤC KÝ HIỆU VÀ TỪ VIẾT TẮT
• DANH SÁCH HÌNH VẼ
• 1. CHƯƠNG 1: PHÂN CỤM DỮ LIỆU
• 1.1. Phân cụm là gì
• 1.2. Một số phương pháp phân cụm dữ liệu cơ bản
• 1.2.1. Phương pháp phân hoạch
• 1.2.1.1. Thuật toán k-Means
• 1.2.2. Phương pháp phân cấp
• 1.2.2.1. Thuật toán Chameleon
• 1.2.3. Phương pháp dựa trên mật độ
• 2. CHƯƠNG 2: PHÂN CỤM DỰA TRÊN TRI THỨC THEO TỪNG CẶP
• 2.1. Phân cụm dựa trên ràng buộc
• 2.2. Phân loại các ràng buộc
• 2.3. Các phương pháp phân cụm dựa trên ràng buộc
• 2.4. Phương pháp S3C2
• 2.4.1. Giới thiệu sơ lược
• 2.4.2. Chi tiết mô hình
• 2.4.3. Đánh giá mô hình
• 3. CHƯƠNG 3: CHƯƠNG TRÌNH VÀ THỬ NGHIỆM
• 3.1. Dữ liệu thử nghiệm
• 3.1.1. Dữ liệu hoa Iris
• 3.1.2. Dữ liệu chữ số viết tay MNIST
• 3.2. Thử nghiệm trên bộ dữ liệu hoa Iris
• 3.2.1. Kịch bản thử nghiệm
• 3.2.2. Kết quả thử nghiệm
• 3.3. Thử nghiệm trên bộ dữ liệu MNIST
• 3.3.1. Kịch bản thử nghiệm
• 3.3.2. Kết quả thử nghiệm
• 3.4. Nhận xét thử nghiệm
• 4. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Phương pháp phân cụm

Phương pháp phân cụm là một kỹ thuật quan trọng trong lĩnh vực khai phá dữ liệu, giúp chia tập dữ liệu thành các cụm dựa trên độ tương tự giữa các đối tượng. Phân cụm dựa trên tri thức là một hướng tiếp cận mới, sử dụng thông tin bổ trợ như ràng buộc hoặc tập giống để nâng cao chất lượng phân cụm. Phân cụm theo từng cặp là một phương pháp hiệu quả, tập trung vào việc xác định mối quan hệ giữa các cặp dữ liệu để tạo ra các cụm chính xác hơn.

1.1. Phân cụm dữ liệu

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 có độ tương tự cao hơn so với các đối tượng ở cụm khác. Phương pháp này được ứng dụng rộng rãi trong nhiều lĩnh vực như kinh doanh thông minh, nhận dạng mẫu, và tìm kiếm web. Phân cụm thông minh sử dụng các thuật toán tiên tiến để tối ưu hóa quá trình phân cụm, đặc biệt là trong xử lý dữ liệu lớn.

1.2. Phân cụm dựa trên tri thức

Phân cụm dựa trên tri thức là phương pháp sử dụng thông tin bổ trợ như ràng buộc hoặc tập giống để cải thiện chất lượng phân cụm. Tri thức trong phân cụm có thể được biểu diễn dưới dạng các ràng buộc như must-link hoặc cannot-link, giúp xác định mối quan hệ giữa các cặp dữ liệu. Phương pháp này đặc biệt hiệu quả trong các bài toán phân cụm bán giám sát.

II. Phân cụm theo từng cặp

Phân cụm theo từng cặp là phương pháp tập trung vào việc xác định mối quan hệ giữa các cặp dữ liệu để tạo ra các cụm chính xác hơn. Phân cụm dựa trên cặp sử dụng các ràng buộc để xác định liệu hai đối tượng có thuộc cùng một cụm hay không. Phương pháp này đặc biệt hiệu quả trong các bài toán phân cụm dữ liệu lớn, nơi mà việc xử lý thông tin từng cặp giúp giảm thiểu độ phức tạp tính toán.

2.1. Phân cụm dựa trên ràng buộc

Phân cụm dựa trên ràng buộc là phương pháp sử dụng các ràng buộc như must-link hoặc cannot-link để xác định mối quan hệ giữa các cặp dữ liệu. Phân cụm dựa trên logic và phân cụm dựa trên mối quan hệ là hai hướng tiếp cận chính trong phương pháp này. Các ràng buộc này giúp cải thiện chất lượng phân cụm bằng cách hướng dẫn thuật toán tập trung vào các mối quan hệ quan trọng giữa các đối tượng.

2.2. Phân cụm dựa trên ngữ nghĩa

Phân cụm dựa trên ngữ nghĩa là phương pháp sử dụng thông tin ngữ nghĩa để xác định mối quan hệ giữa các đối tượng. Phân cụm dựa trên trí tuệ nhân tạo và phân cụm dựa trên mô hình là hai hướng tiếp cận chính trong phương pháp này. Phương pháp này đặc biệt hiệu quả trong các bài toán phân cụm dữ liệu lớn, nơi mà việc xử lý thông tin ngữ nghĩa giúp cải thiện độ chính xác của kết quả phân cụm.

III. Phân cụm hiệu quả

Phân cụm hiệu quả là phương pháp tập trung vào việc tối ưu hóa quá trình phân cụm để đạt được kết quả chính xác và nhanh chóng. Phân cụm tối ưu sử dụng các thuật toán tiên tiến để giảm thiểu thời gian tính toán và cải thiện chất lượng phân cụm. Phân cụm dựa trên học máy và phân cụm dựa trên thuật toán là hai hướng tiếp cận chính trong phương pháp này.

3.1. Phân cụm dựa trên học máy

Phân cụm dựa trên học máy là phương pháp sử dụng các mô hình học máy để tự động hóa quá trình phân cụm. Phân cụm dựa trên trí tuệ nhân tạo và phân cụm dựa trên mô hình là hai hướng tiếp cận chính trong phương pháp này. Phương pháp này đặc biệt hiệu quả trong các bài toán phân cụm dữ liệu lớn, nơi mà việc tự động hóa giúp giảm thiểu thời gian tính toán và cải thiện độ chính xác của kết quả phân cụm.

3.2. Phân cụm dựa trên thuật toán

Phân cụm dựa trên thuật toán là phương pháp sử dụng các thuật toán tiên tiến để tối ưu hóa quá trình phân cụm. Phân cụm dựa trên thống kê và phân cụm dựa trên quy tắc là hai hướng tiếp cận chính trong phương pháp này. Phương pháp này đặc biệt hiệu quả trong các bài toán phân cụm dữ liệu lớn, nơi mà việc tối ưu hóa thuật toán giúp giảm thiểu thời gian tính toán và cải thiện chất lượng phân cụm.

Nội dung chính

Tổng quan nghiên cứu

Trong kỷ nguyên công nghệ thông tin phát triển mạnh mẽ, lượng dữ liệu sinh ra ngày càng lớn, đòi hỏi các kỹ thuật khai phá dữ liệu hiệu quả để xử lý và phân tích. Phân cụm dữ liệu là một kỹ thuật quan trọng trong khai phá dữ liệu, giúp nhóm các đối tượng tương tự vào cùng một cụm, phục vụ nhiều lĩnh vực như kinh doanh thông minh, nhận dạng mẫu, sinh học và bảo mật. Tuy nhiên, phân cụm truyền thống thường dựa trên học không giám sát, dẫn đến kết quả khó giải thích và không chính xác khi thiếu thông tin bổ trợ.

Luận văn tập trung nghiên cứu phương pháp phân cụm dựa trên tri thức theo từng cặp, cụ thể là phương pháp S3C2 (Semi-Supervised Siamese Classifiers for Clustering) sử dụng mạng nơ-ron nhân tạo và học sâu để cải thiện chất lượng phân cụm. Phương pháp này tận dụng các ràng buộc must-link và cannot-link giữa các cặp dữ liệu, giúp tăng độ chính xác phân cụm ngay cả khi số lượng ràng buộc ban đầu rất ít. Thời gian nghiên cứu tập trung vào năm 2020, với thử nghiệm trên hai bộ dữ liệu tiêu biểu: Iris (150 mẫu, 4 thuộc tính) và MNIST (70.000 mẫu ảnh chữ số viết tay, 28×28 pixel).

Nghiên cứu có ý nghĩa quan trọng trong việc nâng cao hiệu quả phân cụm bán giám sát, đặc biệt với dữ liệu lớn và phức tạp, góp phần phát triển các ứng dụng trong khai phá dữ liệu lớn và trí tuệ nhân tạo. Các chỉ số đánh giá như Normalized Mutual Information (NMI), Adjusted Rand Index (ARI) và Rand Index (RI) được sử dụng để đo lường chất lượng phân cụm, cho thấy phương pháp S3C2 vượt trội so với các thuật toán hiện có.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên các lý thuyết và mô hình sau:

• Phân cụm dữ liệu (Clustering): Quá trình phân chia tập dữ liệu thành các cụm sao cho các đối tượng trong cùng cụm có tính tương tự cao hơn so với các đối tượng ở cụm khác. Các phương pháp phân cụm cơ bản gồm phân hoạch (k-Means), phân cấp (Chameleon), dựa trên mật độ (DBSCAN) và dựa trên lưới (STING).

• Phân cụm bán giám sát (Semi-Supervised Clustering): Kết hợp thông tin tri thức dưới dạng ràng buộc must-link (cặp điểm cùng cụm) và cannot-link (cặp điểm khác cụm) để cải thiện chất lượng phân cụm.

• Mạng nơ-ron nhân tạo (Artificial Neural Networks): Mô hình tính toán lấy cảm hứng từ cấu trúc sinh học của não bộ, gồm các nơ-ron nhân tạo kết nối qua các trọng số. Mạng đa lớp truyền tới nhiều tầng (Multilayer Feed-forward Networks) với các hàm kích hoạt phi tuyến như sigmoid, softmax được sử dụng để học các biểu diễn phức tạp.

• Mạng Siamese Neural Networks (SNN): Mạng gồm hai nhánh chia sẻ trọng số, dùng để học biểu diễn và so sánh cặp dữ liệu, phù hợp cho bài toán phân loại nhị phân như xác định must-link hay cannot-link.

• Hàm mất mát (Loss Functions): Bao gồm hàm contrastive loss cho mạng LabNet và hàm misclassification loss cho mạng CluNet, giúp tối ưu hóa quá trình huấn luyện mạng nơ-ron.

Phương pháp nghiên cứu

• Nguồn dữ liệu: Hai bộ dữ liệu tiêu chuẩn được sử dụng là Iris (150 mẫu, 4 thuộc tính) và MNIST (70.000 mẫu ảnh chữ số viết tay, 28×28 pixel).

• Phương pháp phân tích: Phương pháp S3C2 gồm hai giai đoạn chính:

  1. LabNet: Mạng Siamese được huấn luyện để phân loại nhị phân các cặp điểm dữ liệu thành must-link hoặc cannot-link dựa trên các ràng buộc ban đầu. Mạng sử dụng hàm contrastive loss và thuật toán tối ưu RMSprop.

  2. CluNet: Mạng Siamese thứ hai được huấn luyện dựa trên các cặp đã gán nhãn từ LabNet để dự đoán cụm cho từng điểm dữ liệu. Mạng sử dụng hàm misclassification loss và thuật toán tối ưu Adam.

• Timeline nghiên cứu: Thực hiện từ đầu năm 2020 đến tháng 9/2020, bao gồm giai đoạn xây dựng mô hình, cài đặt chương trình bằng Python 3.7, thử nghiệm trên hai bộ dữ liệu, đánh giá và so sánh kết quả.

• Cỡ mẫu và chọn mẫu: Toàn bộ dữ liệu Iris và MNIST được sử dụng. Các cặp dữ liệu được gán nhãn must-link hoặc cannot-link được sinh ngẫu nhiên với số lượng thay đổi theo từng kịch bản thử nghiệm (từ 30 đến 160 cặp cho Iris, từ 100 đến 5000 cặp cho MNIST).

• Đánh giá: Sử dụng các chỉ số NMI, ARI, RI để đánh giá chất lượng phân cụm, đồng thời đo thời gian chạy để đánh giá hiệu năng.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Hiệu quả phân cụm trên bộ dữ liệu Iris:

   • Với số lượng cặp gán nhãn từ 30 đến 160, phương pháp S3C2 đạt chỉ số RI trung bình trên 0.9, ARI và NMI cũng tăng theo số lượng cặp gán nhãn.

   • Thời gian chạy trung bình mỗi lần khoảng 31 giây trên cấu hình máy tính tiêu chuẩn.

2. Hiệu quả phân cụm trên bộ dữ liệu MNIST:

   • Khi số lượng cặp gán nhãn tăng từ 100 đến 5000, chỉ số NMI, ARI, RI đều tăng rõ rệt, đạt giá trị cao nhất khi có 5000 cặp.

   • Thời gian chạy trung bình mỗi lần khoảng 412 giây, phù hợp với kích thước và độ phức tạp của dữ liệu.

3. So sánh với các phương pháp khác:

   • Trên Iris, S3C2 vượt trội hơn các phương pháp SSGC, SSDBSCAN, SSK-Means, MCSSGC với chỉ số RI khoảng 0.9 so với khoảng 0.6 của các phương pháp còn lại.

   • Trên MNIST, S3C2 đạt NMI cao hơn so với d-graph, DCPR, IDEC, đặc biệt khi số lượng cặp gán nhãn lớn.

4. Khả năng mở rộng và linh hoạt:

   • Mô hình S3C2 có thể áp dụng chung kiến trúc mạng cho cả dữ liệu nhỏ (Iris) và dữ liệu lớn, phức tạp (MNIST).

   • Phương pháp khắc phục được nhược điểm của các phương pháp phân cụm phân loại khác khi số lượng ràng buộc ban đầu ít.

Thảo luận kết quả

Kết quả cho thấy việc sử dụng mạng nơ-ron Siamese trong S3C2 để gán nhãn cho các cặp dữ liệu chưa gán nhãn giúp tăng số lượng ràng buộc, từ đó cải thiện đáng kể chất lượng phân cụm. Việc tách bài toán phân cụm thành hai giai đoạn (gán nhãn cặp và phân cụm) giúp giảm độ phức tạp và tăng hiệu quả học.

So với các phương pháp truyền thống như k-Means, DBSCAN hay các phương pháp bán giám sát khác, S3C2 tận dụng tốt hơn thông tin tri thức theo từng cặp, đặc biệt trong trường hợp dữ liệu lớn và số lượng ràng buộc hạn chế. Các biểu đồ kết quả phân cụm có thể được trình bày dưới dạng đường biểu diễn chỉ số NMI, ARI, RI theo số lượng cặp gán nhãn, hoặc bảng so sánh kết quả giữa các phương pháp.

Tuy nhiên, thời gian chạy trên dữ liệu lớn như MNIST vẫn còn khá cao, cho thấy cần tối ưu thêm về mặt thuật toán hoặc phần cứng để ứng dụng thực tế hiệu quả hơn.

Đề xuất và khuyến nghị

1. Tăng cường thu thập và gán nhãn ràng buộc: Khuyến nghị các nhà nghiên cứu và thực hành thu thập thêm các cặp dữ liệu có ràng buộc must-link và cannot-link để nâng cao chất lượng phân cụm, đặc biệt với dữ liệu lớn.

2. Tối ưu hóa mô hình và thuật toán: Đề xuất phát triển các kỹ thuật tối ưu hóa mạng nơ-ron và thuật toán huấn luyện để giảm thời gian chạy, tăng khả năng mở rộng cho các bộ dữ liệu siêu lớn.

3. Ứng dụng đa lĩnh vực: Khuyến khích áp dụng phương pháp S3C2 trong các lĩnh vực như quản lý khách hàng, nhận dạng mẫu, phân tích hình ảnh y tế, nơi dữ liệu phức tạp và có thể tận dụng tri thức theo cặp.

4. Phát triển giao diện trực quan: Đề xuất xây dựng các công cụ trực quan hóa kết quả phân cụm và mạng nơ-ron để hỗ trợ người dùng đánh giá và điều chỉnh mô hình dễ dàng hơn.

5. Nghiên cứu mở rộng: Khuyến nghị nghiên cứu thêm về việc kết hợp các loại ràng buộc khác như ràng buộc trên cụm hoặc trên thước đo tương tự để nâng cao hiệu quả phân cụm.

Đối tượng nên tham khảo luận văn

1. Nghiên cứu sinh và học viên cao học ngành Hệ thống Thông tin, Khoa học Máy tính: Luận văn cung cấp kiến thức chuyên sâu về phân cụm bán giám sát và ứng dụng mạng nơ-ron, hỗ trợ phát triển đề tài nghiên cứu liên quan.

2. Chuyên gia và kỹ sư dữ liệu (Data Scientists, Data Engineers): Cung cấp phương pháp mới để xử lý dữ liệu lớn, cải thiện chất lượng phân cụm trong các dự án khai phá dữ liệu và trí tuệ nhân tạo.

3. Doanh nghiệp và tổ chức ứng dụng công nghệ thông tin: Giúp nâng cao hiệu quả phân tích khách hàng, nhận dạng mẫu, quản lý dữ liệu phức tạp, từ đó tối ưu hóa chiến lược kinh doanh và vận hành.

4. Giảng viên và nhà đào tạo: Tài liệu tham khảo để xây dựng giáo trình, bài giảng về phân cụm dữ liệu, mạng nơ-ron và học máy, cập nhật các phương pháp tiên tiến trong lĩnh vực.

Câu hỏi thường gặp

1. Phân cụm bán giám sát khác gì so với phân cụm không giám sát?
   Phân cụm bán giám sát sử dụng thêm thông tin tri thức như ràng buộc must-link và cannot-link để hướng dẫn quá trình phân cụm, giúp kết quả chính xác hơn so với phân cụm không giám sát chỉ dựa trên tính tương tự dữ liệu.

2. Mạng Siamese Neural Networks (SNN) có vai trò gì trong phương pháp S3C2?
   SNN được dùng để học biểu diễn và phân loại nhị phân các cặp dữ liệu thành must-link hoặc cannot-link, từ đó mở rộng số lượng ràng buộc cho quá trình phân cụm, giúp cải thiện chất lượng phân cụm.

3. Phương pháp S3C2 có thể áp dụng cho những loại dữ liệu nào?
   S3C2 phù hợp với dữ liệu có kích thước và số chiều lớn, phức tạp như ảnh chữ số viết tay MNIST, cũng như dữ liệu nhỏ hơn như Iris, miễn là có thể biểu diễn dưới dạng vector và có ràng buộc theo cặp.

4. Các chỉ số NMI, ARI, RI dùng để đánh giá phân cụm có ý nghĩa gì?
   NMI đo lường sự tương đồng giữa phân cụm và nhãn thực tế, ARI điều chỉnh Rand Index để loại bỏ ảnh hưởng ngẫu nhiên, RI đo tỷ lệ cặp điểm được phân loại đúng. Các chỉ số càng gần 1 càng cho thấy phân cụm chính xác.

5. Thời gian chạy của phương pháp S3C2 có phù hợp với ứng dụng thực tế không?
   Trên dữ liệu nhỏ như Iris, thời gian chạy trung bình khoảng 31 giây là hợp lý. Với dữ liệu lớn như MNIST, thời gian khoảng 6-7 phút mỗi lần chạy, cần tối ưu thêm để ứng dụng trong môi trường thời gian thực hoặc dữ liệu siêu lớn.

Kết luận

• Phương pháp phân cụm dựa trên tri thức theo từng cặp S3C2 sử dụng mạng nơ-ron Siamese hiệu quả trong việc cải thiện chất lượng phân cụm bán giám sát.
• Thử nghiệm trên bộ dữ liệu Iris và MNIST cho thấy S3C2 vượt trội so với nhiều phương pháp phân cụm tiên tiến khác về độ chính xác (NMI, ARI, RI).
• Mô hình có tính linh hoạt cao, áp dụng được cho dữ liệu có kích thước và độ phức tạp khác nhau với cùng kiến trúc mạng.
• Thời gian chạy phù hợp với dữ liệu nhỏ và trung bình, cần tối ưu để mở rộng cho dữ liệu lớn hơn.
• Đề xuất tiếp tục phát triển các giải pháp tối ưu hóa, mở rộng ứng dụng và tích hợp thêm các loại ràng buộc khác để nâng cao hiệu quả phân cụm.

Các nhà nghiên cứu và chuyên gia dữ liệu nên áp dụng và thử nghiệm phương pháp S3C2 trong các dự án thực tế, đồng thời phát triển các công cụ hỗ trợ để khai thác tối đa tiềm năng của phương pháp này.

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

Chương I. Giới thiệu bài toán phân cụm dữ liệu, các khái niệm và các tiếp cận cơ bản. Giới thiệu kiến thức về mạng nơ-ron cần dùng để di sâu vào tìm hiểu việc ứng dụng chúng cho bài toán phân cụm dựa trên tri thức được trình bảy ở chương 3. Trình bày phương pháp S°C”, một mô hình phân lớp sử dụng mạng nơ-ron cho bài toán phân cụm dựa trên ràng buộc theo từng cặp.

Trình bày kết qua cài đặt chương trình cho phương pháp S°C2, và chạy thử nghiệm trên tập dữ liệu hoa Iris, MNIST; dua ra kết quả thực nghiệm của S°C? đồng thời so sánh kết quả với các phương pháp khác: SSGC, SSDBSCAN, SSK-Means, MCSSGC [5,6]. PHAN CUM DU LIEU Trước khi đi sâu vào phân cụm bán giám sát dựa trên tri thức theo từng cặp, cũng như phương pháp S°C7 [1], chương này chúng tôi sẽ trình bày sơ lược về phân cụm dữ liệu, các phương pháp phân cụm dữ liệu. Phân cụm là gì Phân cụm là quá trình phân tách một tập các đối tượng dữ liệu thành các tập con. Mỗi tập con là một cụm, sao cho các đối tượng trong cùng một cụm thì giống nhau, nhưng không giống so với các đối tượng ở các cụm khác [2].

Phân cụm được sử dụng rộng rãi trong nhiều lĩnh vực, như BI, nhận dạng mẫu, tìm kiếm web, sinh học và bảo mật,. Trong BI, phân cụm có thể được sử dụng để sắp xếp một số lượng lớn các khách hàng vào các nhóm, trong đó các khách hàng trong cùng một nhóm sẽ có sự tương tự lớn về một số đặc điểm. Điều này tạo điều kiện cho phát triển các chiến lược kinh doanh đề tăng cường quản lý quan hệ khách hàng (Customer Relationship Management: CRM) [2]. Trong nhận dạng mẫu, phân cụm cũng được sử dụng cho nhiều bài toán có tinh img dung cao, va rất thực tiễn, như nhận dạng chữ ký, nhận dạng chữ viết tay, nhận dạng vân tay, nhận diện khuôn mặt,.

San phẩm của phân cụm được triển khai trong rất nhiều hệ thống, và ngày càng trở nên phô biến. Từ các ứng dụng của các cá nhân, tới các hệ thống lớn hơn của các doanh nghiệp, ngân hàng, các tập đoàn đa quốc gia, thậm chí là các hệ thống chính phủ,. đều có sự hiện diện của phân cụm. Chẳng hạn như, ngày nay nhận dạng vân tay được sử dụng làm cơ chế xác thực cho hầu hết các thiết bị và ứng dụng.

Phân cụm cũng được ứng dụng khá nhiều trong tìm kiếm web. Ví dụ như: một từ khóa tìm kiếm có thể cho ra một số lượng rất lớn các kết quả, do số lượng trang web là vô cùng lớn. Phân cụm có thể được sử dụng đề sắp các kết quả đó vào các nhóm và trình bày các kết quả một cách ngắn gọn. Giúp người dùng có trải nghiệm tốt hơn, tìm kiếm đễ dàng và hiệu quả hơn.

Hơn nữa, các kỹ thuật phân cụm cũng đã được phát triển đề phân loại các tài liệu thành các chủ đề, kết quả của nó thường được sử dụng trong truy hồi thông tin. Trong khai phá dữ liệu, phân cụm được sử dụng như một công cụ độc lập để hiểu rõ hơn về phân phối của đữ liệu, để quan sát các đặc điểm của từng cụm và tập trung vào một nhóm cụ thê đề phân tích thêm. Ngoài ra, nó cũng đóng vai trò là bước tiền xử lý cho các thuật toán khác như phân lớp, trích chọn đặc trưng,. 4 Bởi vì mỗi cụm là một tập các đối tượng tương tự nhau và không tương tự với các đối tượng thuộc lớp khác, nên mỗi cụm có thê được hiểu là một lớp ấn.

Theo nghĩa này, phân cụm đôi khi còn được gọi là phân lớp tự động. Trong một số ứng dụng, phân cụm còn được gọi là phân đoạn dữ liệu (Data Segmentation), bởi nó phân chia dữ liệu thành các nhóm dựa trên độ tương tự của chúng. Phân cụm cũng có thể được sử dụng để phát hiện ngoại lệ (các đối tượng cách xa bất kỳ cụm nào). Ví đụ như phát hiện gian lận thẻ tín dụng, giám sát các hoạt động tội phạm trong thương mại điện tử.

Trong học máy, phân lớp được gọi là học có giám sát (Supervised Learning) vì thông tin nhãn lớp được sử dụng trong thuật toán học. Còn phân cụm được gọi là học không giám sát, do không sử dụng thông tin nhãn lớp. Vì lý do này, phân cụm là hình thức học tập dựa trên quan sát thay vì học qua các ví du [2]. Một số phương pháp phân cụm dữ liệu cơ bản Tùy theo đặc điểm về tính tương đồng của các đối tượng trong các bài toán đang xét, có nhiều cách tiếp cận cho thuật toán phân cụm.

Phương pháp phân hoạch Cho tập đữ liệu D gồm n đối tượng, phương pháp phân hoạch phân phối các đối tượng thuộc D thành k cụm, C¡, C2, ., Cx, sao cho C¡ 6 D và Œ¡ n Cj = @ voi1l<i,j <k. Mét ham mục tiêu được sử dụng để đánh giá chất lượng phân cụm sao cho các đối tượng trong cùng một cụm thì tương tự nhau nhưng khác so với các đối tượng ở các cụm khác. Ở đây, hàm mục tiêu sẽ nhắm đến việc làm tăng cao độ tương tự nội bộ (Intracluster Similarity) và giảm thấp độ tương tự liên kết (Intercluster Similarity). Hầu hết các phương pháp phân hoạch đều dựa trên khoảng cách (Distance-based).

Ban dau chúng khởi tạo một phân vùng. Sau đó, no lặp đi lặp lại việc di chuyền các đối tượng từ nhóm này sang nhóm khác để cố gắng cải thiện chất lượng phân vùng. Phân cụm phân hoạch thường rất khó để đạt được tối ưu toàn cục mà thường thực hiện tối ưu cục bộ bằng các cách tiếp cận tham lam như thuật toán k-Means và k-medoids. Chúng thường hoạt động tốt khi được sử dụng để tìm 5 các cụm có hình cầu (Spherical Shaped Cluster) trong cơ sở đữ liệu có kích thước từ nhỏ đến trung bình [2].

Thuật toán k-Means [2] K-Means là một thuật toán phân cụm phân hoạch dựa trên trọng tâm. Chúng sử dụng trọng tâm của một cụm để đại diện cho cụm đó. Trọng tâm có thê được định nghĩa theo nhiều cách khác nhau, chẳng hạn như giá trị trung bình của các đối tượng trong cụm. Giả sử ta có cụm C¡ với tâm c¡.

Gọi dist(p, c¡) là khoảng cách giữa điểm p và tâm c¡. Chất lượng của cụm C¡ có thể được đo bằng tổng bình phương khoảng cách giữa tất các các đối tượng trong cụm và tâm c¡, được định nghĩa như sau: Ee = >. dist(p,c)* pec Ec, càng nhỏ thì chất lượng của cụm càng tốt. Từ đó, chất lượng của một kết quả phân cụm hay một bộ phân hoạch có thể được tính bởi công thức sau: E= y ».

dist(p, c2 i=1 p€C; Tối ưu hóa E là một việc rất khó khăn. Trong trường hợp xấu nhất, chúng ta sẽ phải liệt kê một số lượng là ly thừa của số cụm các phân hoạch có thể có. Bài toán là NP-hard trong không gian Euclide nói chung (chưa biết số chiều), thẫm chí ngay cả khi số cụm k=2. Trong trường hợp, các đối tượng đữ liệu là các vec-tơ trong không gian Euclide 2 chiều, nhưng chưa biết số cụm k, thì việc tối ưu E cũng là NP-hard.

Đề khắc phục điều nay, k-Means su dung cach tiép cận tham lam và thực hiện tối ưu cục bộ. Thuật toán k-Means định nghĩa trọng tâm của cụm là giá trị trung bình của các điểm trong cụm. Lược đồ giải thuật của thuật toán như sau: Input: = ks6 lượng các cụm "_D: iập dữ liệu gồm n đối tượng Output: Mot tap gom k cum. Phuong thire: (1) tity chon k đối tượng trong D làm tâm khởi tạo cho k cụm (2) lặp cho tới khi không có sự thay đổi nào nữa (2.1) gán (hoặc gán lại) mỗi đối tượng vào cụm mà nó gần tâm nhất (2.2)cập nhật lại tâm các cụm, bằng cách tính giá trị trung bình của các đối tuong trong cum.

Hình bên dưới mô phỏng giải thuật phân cụm k-Means "¬ es _ sa om} es z ` r7 ®` se 7 ° e@ NY +? " Nó " , eK ° ' ’ t e , + , e e fe oe” ie ‘ite oe? 2 ee -.2- + Sin Se ` ozs " ` -=« e ¬. ‘ * eo ` — (a) Initial clustering (b) Iterate (c) Final clustering Hinh 1.1 Phan cum k-Means 1. Phương pháp phân cấp Phân cụm phân cấp còn được gọi là phân cụm cây, trong đó sắp xếp một tập dữ liệu đã cho thành một cấu trúc có dạng hình cây. Tùy theo cách xây dựng cây phân cấp, mà phân cụm phân cấp được chia thành hai phương pháp kết tụ (Agglomerative) hoặc phân tách (Divisive).

Phương pháp kết tụ, còn được gọi là phương pháp từ dưới lên (Bottom-up), bắt đầu với mỗi đối tượng tạo thành một nhóm riêng biệt. Sau đó, nó liên tiếp trộn các đối tượng hoặc các nhóm gần nhau lại, cho tới khi tất cả các nhóm được trộn thành một, hoặc đạt tới một điều kiện kết thúc nào đó [2]. Phương pháp tách còn được gọi là phương pháp từ trên xuống (Top- down), bắt đầu với tất cả các đối tượng trong cùng một cụm. Trong mỗi lần lặp liên tiếp, một cụm lại được chia thành các cụm nhỏ hơn, kết thúc khi mỗi đối tượng nằm trong một cụm hoặc đạt tới điều kiện kết thúc nào đó.

Phân cụm phân cấp có thể dựa trên khoảng cách hoặc dựa trên mật độ. Nó có mặt hạn chế bởi thực tế một khi một bước trộn (merge) hoặc tách (split) được thực hiện, nó không bao giờ có thể được hoàn tác và các bước tiếp theo của quá trình sẽ được thực hiện trên các cụm vừa mới được tạo. Do đó, nếu các quyết định trộn hoặc tách không được lựa chọn tốt sẽ dẫn đến chất lượng phân cụm không được tốt. Song sự cứng nhắc này cũng hữu ích ở chỗ nó dẫn đến chỉ phí tính toán nhỏ hơn bởi không phải lo lắng về tô hợp của các lựa chọn khác nhau.

Dù không thể sửa các quyết định sai lầm, tuy nhiên nhiều cách thức cải thiện chất lượng phân cụm phân cấp đã được đề xuất. Trong đó, một hướng đi đầy hứa hẹn là tích hợp phân cụm phân cấp với các kỹ thuật phân cụm khác, được gọi là phân cụm đa pha (Multiphase Clustering). Trong đoạn sau của tiểu mục này, chúng tôi sẽ giới thiệu một phương pháp như vậy, đó là Chameleon. Có một số cách đề phân loại các phương pháp phân cụm phân cấp.