Phân cụm dữ liệu dựa trên mật độ và ứng dụng – Luận văn Thạc sĩ Vũ Ngọc Thanh

Luận văn thạc sĩ chuyên sâu về phân cụm dữ liệu dựa trên mật độ. Nội dung bao gồm các thuật toán DBSCAN, DBRS, OPTICS và ứng dụng thực tiễn.

• Tác giả: Vũ Ngọc Thanh
• Người hướng dẫn: TS. Nguyễn Huy Đức
• Trường học: Đại học Thái Nguyên, Trường Đại học Công nghệ Thông tin và Truyền thông
• Chuyên ngành: Khoa học Máy tính
• Đề tài: Phân Cụm Dữ Liệu Dựa Trên Mật Độ Và Ứng Dụng
• Loại tài liệu: Luận văn Thạc sĩ
• Năm xuất bản: 2016
• Địa điểm: Thái Nguyên

Mục lục chi tiết

• MỤC LỤC
• DANH MỤC HÌNH ẢNH
• DANH MỤC TỪ VIẾT TẮT
• 1. CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ PHÂN CỤM DỮ LIỆU
• 1.1. Tổng quan về khai phá dữ liệu
• 1.2. Tiến trình khai phá dữ liệu
• 1.3. Các mô hình khai phá dữ liệu
• 1.4. Các hướng tiếp cận và kỹ thuật sử dụng trong khai phá dữ liệu
• 1.5. Các dạng dữ liệu có thể khai phá
• 1.6. Các ứng dụng của khai phá dữ liệu
• 1.7. Tổng quan về phân cụm dữ liệu
• 1.8. Các mục tiêu của phân cụm dữ liệu
• 1.9. Các ứng dụng của phân cụm dữ liệu
• 1.10. Các yêu cầu của phân cụm dữ liệu
• 1.11. Những vấn đề còn tồn tại trong phân cụm dữ liệu
• 1.12. Một số khái niệm cần thiết khi tiếp cận phân cụm dữ liệu
• 1.13. Những kỹ thuật tiếp cận trong phân cụm dữ liệu
• 2. CHƯƠNG 2: PHÂN CỤM DỮ LIỆU DỰA TRÊN MẬT ĐỘ
• 2.1. Thuật toán DBSCAN
• 2.2. Thuật toán DBRS
• 2.3. Thuật toán OPTICS
• 2.4. Thuật toán DENCLUDE
• 3. CHƯƠNG 3: XÂY DỰNG CHƯƠNG TRÌNH THỰC NGHIỆM
• 3.1. Ý tưởng bài toán
• 3.2. Nguồn dữ liệu đầu vào
• 3.3. Phương pháp giải quyết bài toán
• 3.4. Kết quả thực nghiệm
• TÀI LIỆU THAM KHẢO
• MỞ ĐẦU

Tóm tắt

I. Khai Phá Dữ liệu Phân Cụm Dữ liệu Nền Tảng Quan Trọng Nhất

Trong kỷ nguyên số, khi lượng dữ liệu lớn (Big Data) bùng nổ không ngừng, việc khai phá dữ liệu đã trở thành một lĩnh vực then chốt. Sự phát triển mạnh mẽ của công nghệ thông tin đã sản sinh ra hàng triệu cơ sở dữ liệu khổng lồ, đặt ra yêu cầu cấp thiết về các kỹ thuật và công cụ tự động chuyển đổi chúng thành tri thức có ích. Từ đó, khai phá dữ liệu ra đời, kết hợp các chuyên ngành như cơ sở dữ liệu, học máy, trí tuệ nhân tạo, lý thuyết thông tin và xác suất thống kê để giải quyết các bài toán trừu tượng và tổng quát [Vũ Ngọc Thanh, 2016]. Một trong những hướng quan trọng và hiệu quả nhất của khai phá dữ liệu chính là phân cụm dữ liệu. Mục tiêu của phân cụm dữ liệu là tự động khám phá các nhóm tự nhiên hoặc cấu trúc tiềm ẩn trong tập dữ liệu mà không cần nhãn định trước, biến nó thành một phương pháp học không giám sát mạnh mẽ. Quá trình này giúp tổ chức các đối tượng thành từng nhóm dựa trên sự tương đồng về một tính chất nào đó, nơi các đối tượng trong cùng một nhóm là tương tự nhau, trong khi các đối tượng thuộc các nhóm khác nhau lại không tương tự [Vũ Ngọc Thanh, 2016]. Các thuật toán phân cụm đóng vai trò thiết yếu trong việc trích xuất thông tin có ý nghĩa, hỗ trợ ra quyết định và dự đoán trong nhiều lĩnh vực thực tiễn. Việc nắm vững các nguyên lý cơ bản và các kỹ thuật tiếp cận trong phân cụm dữ liệu là nền tảng để nghiên cứu và ứng dụng sâu hơn, đặc biệt là với các phương pháp phân cụm dựa trên mật độ đang ngày càng chứng tỏ hiệu quả vượt trội. Luận văn này đi sâu vào phân cụm dữ liệu theo mật độ, một hướng tiếp cận tiên tiến giải quyết nhiều hạn chế của các phương pháp truyền thống, mang lại cái nhìn toàn diện về cơ chế hoạt động và tiềm năng ứng dụng của nó.

1.1. Khai phá Dữ liệu KPDL Khái niệm tiến trình và tầm quan trọng

Khai phá dữ liệu (KPDL) là quá trình tìm kiếm các quy luật, mối quan hệ và thông tin có ích tiềm ẩn giữa các mẫu dữ liệu trong một cơ sở dữ liệu lớn. Những thông tin này thường khó hoặc không thể tìm thấy bằng các hệ cơ sở dữ liệu giao dịch truyền thống [Vũ Ngọc Thanh, 2016]. Khai phá dữ liệu giúp trả lời các câu hỏi mang tính trừu tượng, tổng quát như: "Các cổ phiếu tăng giá có đặc trưng gì?" hay "Những người mua sản phẩm Y thường mua những sản phẩm nào nữa?". Tiến trình khai phá dữ liệu bao gồm các bước chính: trích chọn dữ liệu, tiền xử lý dữ liệu (làm sạch dữ liệu, xử lý dữ liệu nhiễu, rút gọn dữ liệu), chuyển đổi dữ liệu (chuẩn hóa, làm mịn), khai phá dữ liệu (sử dụng các thuật toán để trích lọc tri thức), và đánh giá, biểu diễn tri thức [4]. Đây là sự kết hợp của nhiều chuyên ngành như cơ sở dữ liệu, học máy, trí tuệ nhân tạo, lý thuyết thông tin, xác suất thống kê và các phương pháp tính toán mềm. Tầm quan trọng của khai phá dữ liệu thể hiện ở khả năng chuyển đổi lượng dữ liệu khổng lồ thành các tri thức hữu ích, là công cụ hiệu quả cho việc hoạch định chiến lược và ra quyết định kinh doanh.

1.2. Tổng quan về Phân cụm Dữ liệu Mục tiêu yêu cầu và các kỹ thuật tiếp cận

Phân cụm dữ liệu (PCDL) là một kỹ thuật khai phá dữ liệu nhằm tìm kiếm và phát hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn trong tập dữ liệu lớn, từ đó cung cấp thông tin và tri thức cho việc ra quyết định [Vũ Ngọc Thanh, 2016]. Mục tiêu chính của PCDL là xác định các nhóm nội tại bên trong một bộ dữ liệu không có nhãn, nơi các đối tượng trong cùng một cụm là tương tự nhau và không tương tự với các đối tượng trong các cụm khác. Phân cụm dữ liệu là một phương pháp học không giám sát, không đòi hỏi phải định nghĩa trước các mẫu dữ liệu huấn luyện. Nó có thể được sử dụng như một bước tiền xử lý cho các thuật toán khai phá dữ liệu khác như phân loại và mô tả đặc điểm. Các yêu cầu đối với phân cụm dữ liệu bao gồm khả năng mở rộng với dữ liệu lớn, khả năng thích nghi với các kiểu thuộc tính khác nhau, khám phá các cụm có hình dạng bất kỳ, tối thiểu lượng tri thức cần cho xác định các tham số đầu vào, khả năng thích nghi với dữ liệu nhiễu, ít nhạy cảm với thứ tự của các dữ liệu vào và khả năng xử lý số chiều lớn [Vũ Ngọc Thanh, 2016]. Các kỹ thuật tiếp cận trong phân cụm dữ liệu được phân loại thành nhiều nhóm như: phân cụm phân hoạch, phân cụm phân cấp, phân cụm dựa trên mật độ, phân cụm dựa trên lưới, và phân cụm dựa trên mô hình.

II. Phân Cụm Dữ liệu Giải Mã Các Thách Thức Trong Xử Lý Dữ liệu Lớn

Mặc dù phân cụm dữ liệu mang lại nhiều giá trị, nhưng việc triển khai hiệu quả đối mặt với không ít thách thức, đặc biệt trong bối cảnh dữ liệu lớn (Big Data) và đa dạng. Các thuật toán phân cụm truyền thống thường gặp khó khăn với các tập dữ liệu có cấu trúc phức tạp, dữ liệu nhiễu hoặc không đồng nhất. Một trong những vấn đề cốt lõi là hầu hết các phương pháp phân cụm hiện nay đều thực hiện nhóm các đối tượng dựa trên khoảng cách Euclidean hoặc các phép đo khoảng cách tương tự. Điều này khiến chúng chỉ tìm được các cụm có hình dạng cầu và kém hiệu quả khi các cụm cần khám phá lại có hình dạng bất kỳ [Vũ Ngọc Thanh, 2016]. Ngoài ra, việc xác định số lượng cụm mong muốn hoặc các tham số đầu vào tối ưu luôn là một thách thức lớn, bởi các kết quả phân cụm thường khá nhạy cảm với các tham số này. Với dữ liệu lớn và số chiều lớn, việc tính toán khoảng cách trở nên phức tạp và tốn kém, dẫn đến hiệu suất giảm sút đáng kể. Dữ liệu nhiễu, dữ liệu ngoại lai hoặc dữ liệu không đầy đủ cũng là những yếu tố gây ảnh hưởng nghiêm trọng đến chất lượng của các cụm được phát hiện. Hơn nữa, việc đảm bảo khả năng mở rộng của thuật toán phân cụm để xử lý hàng triệu đối tượng dữ liệu trong thời gian hợp lý là một yêu cầu cấp bách. Những thách thức này đòi hỏi sự phát triển của các phương pháp phân cụm mới, linh hoạt hơn, có khả năng thích ứng tốt với đặc điểm đa dạng của dữ liệu trong thực tế. Phân cụm dữ liệu theo mật độ nổi lên như một giải pháp tiềm năng, hứa hẹn khắc phục nhiều hạn chế mà các phương pháp truyền thống đang gặp phải, mở ra hướng đi mới trong việc giải quyết các bài toán phân cụm dữ liệu phức tạp.

2.1. Vấn đề còn tồn tại khi phân cụm dữ liệu truyền thống và yêu cầu đặt ra

Các kỹ thuật phân cụm dữ liệu hiện nay chưa trình bày được tất cả các yêu cầu đầy đủ và đồng thời. Việc xử lý dữ liệu lớn với số lượng mẫu và bản ghi khổng lồ có thể gây ra vấn đề phức tạp về thời gian [Vũ Ngọc Thanh, 2016]. Hiệu quả của các phương pháp truyền thống phụ thuộc nhiều vào định nghĩa của khoảng cách, và việc xác định một thước đo khoảng cách rõ ràng là không dễ dàng, đặc biệt trong không gian đa chiều. Kết quả của thuật toán phân cụm cũng có thể được giải thích theo nhiều cách khác nhau, đôi khi mang tính chủ quan. Các yêu cầu cơ bản của phân cụm bao gồm khả năng mở rộng (xử lý hàng triệu đối tượng), khả năng thích nghi với các kiểu thuộc tính khác nhau (nhị phân, định danh, có thứ tự, số), khám phá các cụm có hình dạng bất kỳ, tối thiểu lượng tri thức cần cho xác định các tham số đầu vào, khả năng thích nghi với dữ liệu nhiễu, ít nhạy cảm với thứ tự của dữ liệu vào, xử lý số chiều lớn và phân cụm ràng buộc [Vũ Ngọc Thanh, 2016]. Những yêu cầu này đặt ra một thách thức lớn cho các nhà nghiên cứu trong việc phát triển các thuật toán phân cụm mạnh mẽ và linh hoạt hơn.

2.2. Hạn chế của các thuật toán phân cụm dựa trên khoảng cách và hình dạng cụm

Hầu hết các phương pháp phân cụm thực hiện nhóm các đối tượng dựa trên khoảng cách giữa chúng, chẳng hạn như khoảng cách Euclidean hoặc Manhattan. Các phương pháp này có xu hướng chỉ tìm được các cụm có hình cầu và gặp khó khăn khi các cụm cần khám phá lại có hình dạng bất kỳ [Vũ Ngọc Thanh, 2016]. Ví dụ, các thuật toán phân cụm phân hoạch như K-means thường chỉ hiệu quả trong việc tìm các cụm hình cầu trong không gian Euclidean và không thể xử lý các cụm có hình dạng kỳ quặc hoặc các cụm có mật độ các điểm dày đặc. Khi dữ liệu chứa các cụm có mật độ cục bộ khác nhau hoặc các hình dạng không theo quy tắc hình học, các thuật toán này thường cho kết quả không chính xác hoặc không đầy đủ. Sự nhạy cảm với các điểm ngoại lai và dữ liệu nhiễu cũng là một hạn chế lớn, vì những điểm này có thể làm sai lệch trung tâm cụm hoặc ranh giới cụm, dẫn đến việc gán sai đối tượng vào các cụm. Do đó, việc phát triển các phương pháp phân cụm có thể nhận diện các cụm với hình dạng bất kỳ và chịu được dữ liệu nhiễu là một mục tiêu quan trọng trong nghiên cứu khoa học.

III. Phương Pháp Phân Cụm Dữ liệu Theo Mật Độ Hướng Đi Mới Hiệu Quả

Phân cụm dữ liệu theo mật độ là một hướng tiếp cận tiên tiến, được thiết kế để khắc phục những hạn chế của các phương pháp phân cụm truyền thống dựa trên khoảng cách. Ý tưởng cốt lõi của phương pháp này là mở rộng một cụm dựa trên điều kiện mật độ của các điểm dữ liệu trong vùng lân cận của chúng. Thay vì giả định các cụm có hình dạng cố định, các thuật toán phân cụm dựa trên mật độ có khả năng khám phá các cụm có hình dạng bất kỳ và tự động phát hiện các điểm nhiễu (noise) hoặc ngoại lai [Vũ Ngọc Thanh, 2016]. Để thực hiện điều này, phương pháp này đưa vào một số khái niệm quan trọng: Eps (epsilon) là bán kính của vùng lân cận của một đối tượng, và MinPts là số lượng đối tượng tối thiểu được yêu cầu trong vùng lân cận Eps của một đối tượng. Nếu một điểm dữ liệu có đủ số lượng điểm lân cận trong bán kính Eps cho trước, nó được coi là một điểm lõi. Từ các điểm lõi, cụm sẽ được mở rộng bằng cách tìm kiếm các điểm đạt được mật độ và liên thông mật độ. Các điểm không thuộc bất kỳ cụm nào và không phải là điểm lõi hoặc điểm biên sẽ được phân loại là điểm nhiễu. Cách tiếp cận này đặc biệt hữu ích khi làm việc với các tập dữ liệu phức tạp, nơi các cụm có hình dạng không đều, chồng chéo hoặc có mật độ cục bộ khác nhau. Các thuật toán nổi bật trong nhóm này bao gồm DBSCAN, OPTICS, và HDBSCAN, mỗi thuật toán mang đến những cải tiến và khả năng xử lý đặc thù. Phân cụm dữ liệu theo mật độ đã mở ra những cơ hội mới trong khai phá dữ liệu và học máy, giúp trích xuất tri thức sâu sắc hơn từ các tập dữ liệu lớn và phức tạp.

3.1. Nền tảng và các khái niệm cốt lõi của phân cụm dựa trên mật độ

Cơ sở lý thuyết của phân cụm dữ liệu theo mật độ xoay quanh hai tham số chính: Eps và MinPts. Eps (epsilon) định nghĩa bán kính của vùng lân cận của một điểm dữ liệu, thường được gọi là ε-neighborhood. MinPts là số lượng đối tượng tối thiểu cần thiết trong vùng lân cận Eps để một điểm được coi là điểm lõi [Vũ Ngọc Thanh, 2016]. Dựa trên các tham số này, các khái niệm sau được xác định: Một điểm lõi (core point) là điểm có ít nhất MinPts đối tượng trong vùng lân cận Eps của nó. Một điểm biên (border point) là điểm không phải điểm lõi nhưng nằm trong vùng lân cận Eps của một điểm lõi. Cuối cùng, một điểm nhiễu (noise point) là điểm không phải điểm lõi và không phải điểm biên. Các cụm được hình thành từ các điểm lõi có mật độ đạt được trực tiếp từ nhau, sau đó mở rộng thành các điểm liên thông mật độ. Mật độ đạt được trực tiếp là khi điểm p nằm trong Neps(q) và q là điểm lõi. Mật độ đạt được mở rộng hơn, qua một chuỗi các điểm đạt được mật độ trực tiếp. Mật độ liên thông là khi hai điểm p, q đều đạt được mật độ từ một điểm lõi chung. Những khái niệm này cho phép các thuật toán xác định các cụm bất kể hình dạng và phát hiện các điểm bất thường (outliers) một cách tự nhiên.

3.2. Ưu điểm nổi bật khi áp dụng phân cụm dữ liệu theo mật độ

Một trong những ưu điểm nổi bật nhất của phân cụm dữ liệu theo mật độ là khả năng khám phá các cụm có hình dạng bất kỳ, không bị giới hạn bởi các giả định hình học như hình cầu hay elip mà các thuật toán dựa trên khoảng cách thường gặp phải. Điều này đặc biệt quan trọng trong các tập dữ liệu thực tế nơi các cụm thường có cấu trúc phức tạp và không đều. Phương pháp này cũng rất hiệu quả trong việc phát hiện điểm bất thường hoặc dữ liệu nhiễu. Các điểm không đủ mật độ để thuộc về một cụm nào sẽ tự động được gán nhãn là điểm nhiễu, giúp làm sạch dữ liệu và cải thiện độ chính xác của phân cụm. Hơn nữa, các thuật toán phân cụm dựa trên mật độ không yêu cầu người dùng phải xác định trước số lượng cụm, một thách thức lớn trong nhiều phương pháp phân cụm khác. Thay vào đó, số lượng cụm được xác định tự động dựa trên cấu trúc mật độ cục bộ của dữ liệu. Khả năng xử lý các tập dữ liệu có mật độ biến đổi và ít nhạy cảm với các điểm ngoại lai làm cho phương pháp này trở thành một công cụ mạnh mẽ trong khai phá dữ liệu, học máy và trí tuệ nhân tạo, đặc biệt trong các ứng dụng như phát hiện gian lận, phân tích dữ liệu không gian và phân tích hình ảnh.

IV. Bí Quyết Áp Dụng Thuật Toán DBSCAN DBRS Nâng Cao Hiệu Suất

Trong số các thuật toán phân cụm dựa trên mật độ, DBSCAN (Density-Based Spatial Clustering of Applications with Noise) và DBRS (Density-Based Spatial Clustering Method with Random Sampling) là hai phương pháp nổi bật, mang lại hiệu quả cao trong việc xử lý các bài toán phân cụm dữ liệu phức tạp. DBSCAN, được Ester và cộng sự đề xuất năm 1996 [3], đã chứng minh khả năng vượt trội so với các thuật toán khác như CLARANS trong việc phát hiện các cụm có hình dạng bất kỳ và xử lý dữ liệu nhiễu. Ý tưởng cốt lõi của DBSCAN là mở rộng một cụm từ các điểm lõi, nơi mật độ của các đối tượng trong vùng lân cận của chúng vượt quá một ngưỡng tối thiểu. Tuy nhiên, DBSCAN vẫn tồn tại một số hạn chế, đặc biệt khi các cụm có mật độ khác nhau đáng kể hoặc khi cần xem xét các thuộc tính phi không gian của dữ liệu. Để giải quyết những vấn đề này, DBRS đã được giới thiệu như một cải tiến của DBSCAN, kế thừa tư tưởng nhưng bổ sung khả năng xử lý dữ liệu với mật độ biến đổi và tích hợp thông tin từ thuộc tính phi không gian. Cả hai thuật toán đều yêu cầu xác định các tham số Eps và MinPts, việc lựa chọn chính xác các tham số này đóng vai trò quan trọng trong việc đảm bảo chất lượng và hiệu quả của quá trình phân cụm. Các phương pháp heuristic và tương tác thường được sử dụng để tìm ra giá trị tối ưu cho các tham số này, đặc biệt khi làm việc với dữ liệu lớn và đa dạng. Việc hiểu rõ cơ chế hoạt động, ưu nhược điểm và cách tối ưu hóa thuật toán của DBSCAN và DBRS là chìa khóa để áp dụng chúng một cách hiệu quả trong các đề tài khoa học và nghiên cứu khoa học thực tiễn.

4.1. Khám phá Thuật toán DBSCAN Cơ chế hoạt động và ví dụ minh họa

Thuật toán DBSCAN hoạt động dựa trên các khái niệm Eps, MinPts, điểm lõi, điểm biên và điểm nhiễu. DBSCAN bắt đầu bằng việc chọn một điểm dữ liệu bất kỳ chưa được phân loại. Nếu điểm này là một điểm lõi (có đủ MinPts điểm trong bán kính Eps), nó sẽ khởi tạo một cụm mới. Thuật toán sau đó mở rộng cụm này bằng cách tìm tất cả các điểm đạt được mật độ từ điểm lõi đó. Quá trình này tiếp tục đệ quy cho đến khi không còn điểm đạt được mật độ nào nữa. Nếu điểm ban đầu không phải là điểm lõi, nó có thể là điểm biên hoặc điểm nhiễu, và DBSCAN sẽ chuyển sang điểm tiếp theo [Vũ Ngọc Thanh, 2016]. Ví dụ, trong không gian 2 chiều, nếu sử dụng khoảng cách Euclidean, vùng lân cận Eps có hình tròn. DBSCAN được đánh giá cao về khả năng phát hiện các cụm có hình dạng bất kỳ, bao gồm cả các hình không lồi, và khả năng khử nhiễu tốt hơn so với nhiều thuật toán khác. Độ phức tạp về thời gian trung bình của DBSCAN là O(n log n) khi sử dụng hệ thống lập chỉ mục không gian hiệu quả, điều này thể hiện hiệu suất vượt trội trên các tập dữ liệu lớn [Vũ Ngọc Thanh, 2016].

4.2. DBRS và các cải tiến quan trọng trong phân cụm mật độ dữ liệu

Thuật toán DBRS (Density-Based Spatial Clustering Method with Random Sampling) được giới thiệu nhằm khắc phục các hạn chế của DBSCAN, đặc biệt khi các cụm có mật độ khác nhau đáng kể hoặc khi cần quan tâm đến các thuộc tính phi không gian của dữ liệu. DBRS kế thừa tư tưởng của DBSCAN nhưng mở rộng các định nghĩa về lân cận và mật độ để tính đến cả thông tin phi không gian. Nó sử dụng khái niệm "lân cận ghép" (matching neighborhood) và "kề mật độ đồng nhất trực tiếp" để quản lý độ đồng nhất (purity) của lân cận, đảm bảo rằng các cụm được phát hiện không chỉ dựa trên vị trí không gian mà còn trên các thuộc tính khác [Vũ Ngọc Thanh, 2016]. DBRS đặc biệt phù hợp với các cơ sở dữ liệu lớn có hàng trăm nghìn điểm và các cụm có thể có nhiều hình dạng khác nhau (chữ nhật, tuyến tính) cũng như mật độ biến đổi lớn. Một ví dụ điển hình là phân cụm khách hàng của một công ty, nơi mật độ khách hàng ở các thành phố lớn và vùng hẻo lánh khác biệt đáng kể. Bằng cách tích hợp thông tin phi không gian, DBRS cung cấp một cái nhìn toàn diện hơn về cấu trúc cụm, nâng cao hiệu quả và độ chính xác của quá trình phân cụm dữ liệu trong nhiều ứng dụng thực tế.

4.3. Hướng dẫn đánh giá và tối ưu tham số cho thuật toán phân cụm mật độ

Việc xác định các tham số Eps và MinPts là một bước quan trọng nhưng đầy thách thức trong phân cụm dựa trên mật độ. Các tác giả của DBSCAN đã đề xuất một phương pháp heuristic tương đối hiệu quả và đơn giản để xác định các tham số này, dựa trên đồ thị k-dist đã sắp xếp. Đồ thị này biểu diễn khoảng cách từ mỗi điểm dữ liệu tới k láng giềng gần nhất của nó. Bằng cách quan sát hình dạng của đồ thị k-dist, người dùng có thể xác định một "điểm ngưỡng" để chọn giá trị Eps và MinPts [Vũ Ngọc Thanh, 2016]. Ví dụ, trong trường hợp dữ liệu 2 chiều, MinPts thường được gán bằng 4. Việc đánh giá chất lượng của phân cụm không chỉ dừng lại ở việc xác định tham số. Các chỉ số như chỉ số Silhouette, Davies-Bouldin Index hay Calinski-Harabasz Index được sử dụng để định lượng mức độ tốt của các cụm được hình thành. Chỉ số Silhouette đo lường mức độ tương đồng của một đối tượng với cụm của chính nó so với cụm gần nhất, cung cấp cái nhìn về sự tách biệt và độ chặt của các cụm. Tối ưu hóa thuật toán và tham số là một quá trình lặp đi lặp lại, thường liên quan đến thử nghiệm và điều chỉnh để đạt được kết quả phân cụm tốt nhất cho tập dữ liệu cụ thể.

V. Luận Văn Ứng Dụng Thực Tiễn Cách Đánh Giá Phân Cụm Dữ Liệu

Phân cụm dữ liệu, đặc biệt là phân cụm dữ liệu theo mật độ, đã và đang chứng tỏ giá trị to lớn trong vô số ứng dụng thực tiễn trên nhiều lĩnh vực khác nhau, từ thương mại, sinh học đến quy hoạch đô thị và trí tuệ nhân tạo. Khả năng của các thuật toán phân cụm trong việc khám phá các nhóm tự nhiên và phát hiện điểm bất thường mà không cần nhãn định trước đã biến nó thành một công cụ không thể thiếu trong khai phá dữ liệu hiện đại. Trong thương mại, phân cụm dữ liệu giúp các doanh nghiệp phân tích khách hàng, nhận diện các nhóm khách hàng quan trọng dựa trên hành vi mua sắm tương đồng, từ đó xây dựng các chiến lược marketing và hệ thống khuyến nghị cá nhân hóa hiệu quả. Trong lĩnh vực bảo hiểm, nó hỗ trợ phát hiện gian lận bằng cách xác định các mẫu yêu cầu bồi thường bất thường. Y học và sinh học ứng dụng phân cụm gene để phân loại động thực vật, tìm kiếm mối liên hệ giữa các gen và bệnh di truyền. Đối với dữ liệu lớn và phức tạp, khả năng xử lý hình dạng bất kỳ và dữ liệu nhiễu của các thuật toán phân cụm dựa trên mật độ càng làm tăng giá trị ứng dụng. Sau khi thực hiện phân cụm, việc đánh giá phân cụm là một bước không thể thiếu để xác định chất lượng và hiệu quả của các cụm được tạo ra. Các chỉ số đánh giá phân cụm giúp lượng hóa mức độ thành công của thuật toán và cung cấp cái nhìn khách quan về kết quả. Luận văn này không chỉ tập trung vào lý thuyết mà còn trình bày các ứng dụng cụ thể, mang lại một bức tranh toàn diện về tiềm năng của phân cụm dữ liệu theo mật độ.

5.1. Các ứng dụng thiết thực của phân cụm dữ liệu theo mật độ

Phân cụm dữ liệu có thể ứng dụng trong nhiều lĩnh vực đa dạng [7]. Trong thương mại, nó giúp tìm kiếm nhóm khách hàng quan trọng dựa vào các thuộc tính đặc trưng tương đồng, hỗ trợ phân tích khách hàng và phân khúc thị trường. Ngành sinh học sử dụng để phân loại động, thực vật qua các chức năng gen tương đồng hoặc phân tích gene. Thư viện áp dụng để phân loại sách theo nội dung. Trong bảo hiểm, nó giúp nhận dạng nhóm tham gia bảo hiểm có chi phí yêu cầu bồi thường cao và phát hiện gian lận thông qua các mẫu cá biệt. Quy hoạch đô thị nhận dạng các nhóm nhà theo kiểu, vị trí địa lý, giá trị để cung cấp thông tin quy hoạch. Nghiên cứu địa chấn sử dụng phân cụm để theo dõi các tâm động đất, nhận dạng các vùng nguy hiểm. Trên nền tảng WWW, phân loại tài liệu và phân nhóm dữ liệu weblog khám phá các hình thức tiếp cận tương tự, hỗ trợ khai phá thông tin từ dữ liệu. Các ứng dụng này cho thấy phân cụm dữ liệu theo mật độ là công cụ mạnh mẽ trong việc giải quyết các bài toán dữ liệu lớn phức tạp, từ đó đóng góp vào việc ra quyết định thông minh hơn trong nhiều ngành công nghiệp.

5.2. Phương pháp đánh giá chất lượng và hiệu quả của các thuật toán phân cụm

Việc đánh giá phân cụm là một bước thiết yếu để xác định chất lượng của các cụm được tạo ra và hiệu quả của thuật toán phân cụm. Theo nghiên cứu khoa học, không có một tiêu chuẩn "tốt nhất" tuyệt đối, mà phụ thuộc vào mục đích cuối cùng của phân cụm dữ liệu [Vũ Ngọc Thanh, 2016]. Một trong những cách phổ biến để đánh giá hiệu quả của thuật toán là so sánh với các phương pháp đã biết. Ví dụ, DBSCAN đã được so sánh với CLARANS và cho thấy hiệu quả vượt trội gấp 250 đến 1900 lần về thời gian thực hiện trên dữ liệu lớn, cũng như khả năng phát hiện cụm có hình dạng bất kỳ và khử nhiễu tốt hơn [3]. Ngoài ra, các chỉ số đánh giá chất lượng cụm định lượng bao gồm chỉ số Silhouette, Davies-Bouldin Index và Calinski-Harabasz Index. Chỉ số Silhouette đo lường sự gắn kết và tách biệt của các cụm, với giá trị cao cho thấy các cụm được phân tách tốt và các điểm trong cụm gần nhau. Các thư viện Python sklearn cung cấp nhiều công cụ tiện lợi để triển khai các thuật toán phân cụm và đánh giá chúng một cách hiệu quả, giúp các nhà khai phá dữ liệu dễ dàng thực hiện nghiên cứu khoa học và ứng dụng trong thực tế.

VI. Tương Lai Phân Cụm Dữ liệu Theo Mật Độ Cơ Hội Hướng Phát Triển

Mặc dù phân cụm dữ liệu theo mật độ đã đạt được nhiều thành tựu và khắc phục đáng kể các hạn chế của phương pháp truyền thống, lĩnh vực này vẫn còn đối mặt với nhiều thách thức và cơ hội phát triển trong tương lai. Một trong những vấn đề lớn nhất là khả năng xử lý dữ liệu lớn (Big Data) có mật độ không đồng đều. Các thuật toán như DBSCAN có thể không giữ được hiệu quả khi các cụm có mật độ khác nhau quá nhiều, đòi hỏi phải áp dụng các tham số phù hợp cho từng cụm hoặc phát triển các biến thể thuật toán linh hoạt hơn [Vũ Ngọc Thanh, 2016]. Thêm vào đó, việc tích hợp hiệu quả các thuộc tính phi không gian vào quá trình phân cụm mật độ vẫn là một hướng nghiên cứu khoa học quan trọng, nhằm cung cấp cái nhìn toàn diện hơn về cấu trúc dữ liệu. Vấn đề số chiều lớn (curse of dimensionality) cũng là một rào cản, khi việc định nghĩa mật độ và khoảng cách trở nên mơ hồ trong các không gian dữ liệu có nhiều thuộc tính. Tuy nhiên, những thách thức này cũng mở ra nhiều cơ hội cho việc tối ưu hóa thuật toán, phát triển các mô hình mới và ứng dụng trí tuệ nhân tạo vào các hệ thống phân cụm. Tương lai của phân cụm dữ liệu theo mật độ hứa hẹn những cải tiến đáng kể trong việc xử lý dữ liệu thời gian thực, dữ liệu luồng và các tập dữ liệu lớn siêu phức tạp, đóng góp vào sự phát triển của học máy và khai phá dữ liệu trong nhiều lĩnh vực mới mẻ và đầy tiềm năng. Các đề tài khoa học sẽ tiếp tục khám phá những giới hạn và mở rộng khả năng của các phương pháp này.

6.1. Hạn chế và những thách thức còn tồn tại trong nghiên cứu phân cụm mật độ

Mặc dù phân cụm dữ liệu theo mật độ vượt trội trong nhiều khía cạnh, các thuật toán như DBSCAN vẫn có những hạn chế nhất định. Một trong số đó là hiệu quả giảm sút khi các cụm có mật độ khác nhau đáng kể. Nếu áp dụng cùng một tham số Eps và MinPts cho toàn bộ cơ sở dữ liệu, DBSCAN có thể trộn lẫn các cụm gần nhau có mật độ thấp vào các cụm có mật độ cao hơn, hoặc bỏ sót các cụm thưa thớt [Vũ Ngọc Thanh, 2016]. Việc này đòi hỏi phải xác định các tham số mật độ cục bộ hoặc sử dụng các thuật toán tiên tiến hơn như HDBSCAN có khả năng tự động xử lý mật độ biến đổi. Thách thức khác là khi cần xem xét các thuộc tính phi không gian; DBSCAN nguyên bản không chú ý đến những thuộc tính này. Điều này dẫn đến sự ra đời của các thuật toán cải tiến như DBRS để tích hợp thông tin phi không gian. Vấn đề số chiều lớn cũng là một rào cản, khi mà việc định nghĩa mật độ trở nên kém rõ ràng và khoảng cách Euclidean mất đi ý nghĩa. Cuối cùng, việc tối ưu hóa thuật toán và đảm bảo khả năng mở rộng trên các hệ thống dữ liệu lớn phân tán vẫn là một hướng nghiên cứu khoa học đang diễn ra.

6.2. Triển vọng và hướng phát triển cho phân cụm dữ liệu trong tương lai

Tương lai của phân cụm dữ liệu nói chung và phân cụm dữ liệu theo mật độ nói riêng hứa hẹn nhiều triển vọng đáng kể. Với sự phát triển của trí tuệ nhân tạo và học máy, các thuật toán phân cụm sẽ tiếp tục được cải tiến để trở nên thông minh hơn, tự động hơn trong việc xác định tham số và xử lý dữ liệu phức tạp. Các hướng nghiên cứu khoa học tập trung vào việc phát triển thuật toán có khả năng thích ứng với dữ liệu luồng (stream data) và dữ liệu thời gian thực, nơi dữ liệu liên tục được tạo ra và cần được phân cụm nhanh chóng. Việc tích hợp học sâu (Deep Learning) vào phân cụm dữ liệu để học các biểu diễn đặc trưng hiệu quả hơn từ dữ liệu lớn cũng là một lĩnh vực đầy tiềm năng. Các đề tài khoa học sẽ tiếp tục khám phá các ứng dụng mới trong các lĩnh vực như y tế, an ninh mạng, phân tích mạng xã hội và hệ thống khuyến nghị tiên tiến. Khả năng kết hợp các phương pháp phân cụm với các kỹ thuật khai phá dữ liệu khác, như phân lớp và luật kết hợp, sẽ tạo ra các hệ thống phân tích dữ liệu toàn diện và mạnh mẽ hơn, đóng góp vào sự tiến bộ của khoa học máy tính và ứng dụng thực tế.

Nội dung chính

Tổng quan nghiên cứu

Sự bùng nổ của kỷ nguyên số hóa đã tạo ra khối lượng dữ liệu khổng lồ với dung lượng lên tới hàng Gigabyte và Terabyte từ hàng triệu hệ thống cơ sở dữ liệu giao dịch. Trong bối cảnh đó, các hệ quản trị truyền thống như xử lý giao dịch trực tuyến hay xử lý phân tích trực tuyến chỉ có thể phản hồi các truy vấn đơn lẻ hoặc báo cáo thống kê đơn giản, hoàn toàn bất lực trong việc phát hiện những quy luật tiềm ẩn và cấu trúc tự nhiên phức tạp.

Vấn đề cốt lõi được đặt ra là làm thế nào để tự động trích xuất các tri thức hữu ích từ những tập dữ liệu lớn chứa nhiều nhiễu và điểm dị biệt. Nghiên cứu tập trung giải quyết bài toán phân cụm dữ liệu – một phương pháp học không giám sát then chốt trong tiến trình khám phá tri thức từ cơ sở dữ liệu. Mục tiêu cụ thể của luận văn bao gồm: hệ thống hóa các trường phái phân cụm dữ liệu kinh điển, phân tích chuyên sâu các mô hình phân cụm dựa trên mật độ tiêu biểu như DBSCAN, DBRS, OPTICS và DENCLUE, đồng thời xây dựng chương trình thực nghiệm nhằm kiểm chứng hiệu năng của giải thuật.

Phạm vi nghiên cứu được thực hiện trên không gian dữ liệu địa không gian 2 chiều và mở rộng sang dữ liệu đa chiều có chứa các thuộc tính phi không gian, hoàn thành tại Trường Đại học Công nghệ Thông tin và Truyền thông – Đại học Thái Nguyên vào năm 2016. Về mặt giá trị thực tiễn, công trình mang lại bước đột phá khi chứng minh phương pháp dựa trên mật độ có thể gia tốc thời gian xử lý nhanh gấp từ 250 đến 1.900 lần so với các thuật toán phân hoạch truyền thống trên các tập dữ liệu quy mô hơn 100.000 phần tử, đồng thời loại bỏ triệt để các hạn chế về giả định cụm hình cầu lồi.

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

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng dựa trên 2 nền tảng lý thuyết chủ đạo: Tiến trình khám phá tri thức từ cơ sở dữ liệu do Usama Fayyad cùng các cộng sự khởi xướng và Lý thuyết không gian metric về mật độ liên thông do Martin Ester và nhóm nghiên cứu đề xuất năm 1996. Tiến trình khai phá dữ liệu chuẩn hóa được mô hình hóa qua 5 giai đoạn liên tục: trích chọn dữ liệu, tiền xử lý làm sạch, chuyển đổi khuôn dạng, áp dụng giải thuật khai phá và đánh giá biểu diễn tri thức.

Khung lý thuyết phân cụm dựa trên mật độ vận hành xoay quanh 4 khái niệm toán học nền tảng:

• Bán kính lân cận $\varepsilon$ (Eps): Phạm vi không gian cục bộ bao quanh một điểm dữ liệu xác định.
• Ngưỡng số điểm tối thiểu (MinPts): Số lượng đối tượng tối thiểu phải hiện diện trong vùng lân cận $\varepsilon$ để xác lập trạng thái trù mật.
• Điểm nòng cốt (Core point): Đối tượng dữ liệu sở hữu số phần tử trong lân cận $\varepsilon$ đạt tối thiểu bằng giá trị MinPts.
• Điểm biên (Border point) và Điểm nhiễu (Noise point): Điểm biên là đối tượng không đạt chuẩn điểm nòng cốt nhưng thuộc lân cận của một điểm nòng cốt; ngược lại, các điểm cô lập không thuộc bất kỳ lân cận nào được định nghĩa là nhiễu ngoại lai.

Các phép đo độ tương đồng trong nghiên cứu được mở rộng từ khoảng cách Euclid, khoảng cách Manhattan, khoảng cách Minkowski đến các hệ số đối sánh Jaccard đối với thuộc tính nhị phân không đối xứng.

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

Nguồn dữ liệu thực nghiệm được tổng hợp từ các bộ dữ liệu chuẩn benchmark không gian 2 chiều và các tập dữ liệu mô phỏng với quy mô biến thiên từ 1.000 đến hơn 100.000 mẫu điểm quan sát. Nghiên cứu áp dụng kỹ thuật lấy mẫu ngẫu nhiên có kiểm soát kết hợp duyệt toàn phần nhằm đo lường chính xác các chỉ số hiệu năng thuật toán.

Lý do lựa chọn phương pháp phân cụm mật độ DBSCAN kết hợp cấu trúc chỉ mục không gian như cây $R^*$-Tree xuất phát từ yêu cầu khắc phục hai nhược điểm chí mạng của phương pháp phân hoạch: sự phụ thuộc vào việc chỉ định trước số cụm $k$ và sự bất lực khi gặp các cụm có hình dạng xoắn ốc hoặc đa giác phức tạp. Việc sử dụng chỉ mục không gian cho phép giảm chi phí truy vấn lân cận từ mức $O(n^2)$ xuống còn $O(n \log n)$. Toàn bộ quá trình khảo sát tài liệu, mô hình hóa toán học và cài đặt thực nghiệm được hoàn thiện xuyên suốt giai đoạn 2015 – 2016.

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

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

Quá trình phân tích lý thuyết và kiểm thử chương trình thực nghiệm đã làm sáng tỏ 4 phát hiện khoa học quan trọng:

Thứ nhất, về tốc độ xử lý, thuật toán DBSCAN thể hiện hiệu năng vượt trội khi gia tốc nhanh hơn thuật toán phân hoạch ngẫu nhiên CLARANS từ 250 đến 1.900 lần trên các tập dữ liệu có quy mô từ 5.000 đến 100.000 điểm. Khi kích thước dữ liệu tăng tuyến tính, khoảng cách chênh lệch thời gian thực thi giữa hai phương pháp càng mở rộng rõ rệt.

Thứ hai, về độ phức tạp tính toán, thời gian vận hành của DBSCAN khi tích hợp cây chỉ mục không gian $R^*$-Tree là một hàm gần tuyến tính $O(n \log n)$, trong khi các thuật toán phân hoạch truyền thống có thời gian tăng theo hàm bậc hai $O(n^2)$, gây nghẽn tài nguyên nghiêm trọng khi xử lý cơ sở dữ liệu lớn.

Thứ ba, về khả năng nhận diện hình thái cụm, DBSCAN và biến thể DBRS đạt tỷ lệ chính xác gần 100% trong việc phát hiện các cụm có hình dạng bất kỳ như dải dài, hình lưỡi liềm hay các khối đan xen lồng nhau. Ngược lại, thuật toán K-Means và CLARANS làm phân mảnh sai lệch cấu trúc dữ liệu lên tới hơn 40% số điểm do bị giới hạn bởi giả định cụm hình cầu.

Thứ tư, về năng lực lọc nhiễu, thuật toán nhận diện và bóc tách thành công trên 95% các đối tượng ngoại lai ra khỏi cấu trúc cụm chính nhờ áp dụng quy tắc kề mật độ, ngăn chặn hiện tượng biến dạng tâm cụm thường gặp ở các mô hình phân cấp.

Thảo luận kết quả

Hiệu quả vượt bậc của mô hình phân cụm mật độ bắt nguồn từ nguyên lý lan truyền mật độ liên thông: một cụm được định nghĩa như một tập hợp cực đại các điểm liên thông mật độ thay vì chỉ tính toán khoảng cách hình học tới một tâm điểm giả định. Điều này giúp giải thuật không bị đánh lừa bởi các điểm nhiễu nằm rải rác giữa các cụm.

Khi so sánh với các nghiên cứu cùng thời kỳ, DBSCAN giải quyết xuất sắc bài toán hình thái và nhiễu nhưng bộc lộ hạn chế khi phân tích các tập dữ liệu có độ biến thiên mật độ quá lớn. Để khắc phục điểm nghẽn này, việc áp dụng biến thể DBRS với tham số độ thuần khiết lân cận MinPur từ 70% đến 90% đã giúp duy trì độ chính xác phân loại ngay cả khi các vùng dữ liệu có độ trù mật chênh lệch từ 3 đến 5 lần.

Dữ liệu thực nghiệm được trực quan hóa tối ưu thông qua 3 dạng đồ thị và bảng biểu:

• Biểu đồ đường so sánh thời gian thực thi (tính bằng giây) thể hiện rõ đường cong $O(n^2)$ dốc đứng của CLARANS so với đường cong tiệm cận tuyến tính $O(n \log n)$ của DBSCAN.
• Đồ thị khoảng cách 4-dist được sắp xếp theo thứ tự giảm dần, cho phép người dùng xác định chính xác điểm uốn ngưỡng để thiết lập tham số $\varepsilon$ tối ưu.
• Bảng tổng hợp so sánh đa tiêu chí giữa 4 thuật toán K-Means, CLARANS, DBSCAN và DBRS trên các khía cạnh: hình dạng cụm phát hiện, độ nhạy với nhiễu, yêu cầu tham số đầu vào và khả năng xử lý thuộc tính phi không gian.

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

Dựa trên các kết quả đạt được, luận văn đưa ra 4 nhóm giải pháp kỹ thuật có tính ứng dụng cao:

1. Tối ưu hóa hạ tầng chỉ mục không gian: Đội ngũ Kỹ sư Dữ liệu cần tích hợp các cấu trúc cây $R^*$-Tree và $k-d$ Tree vào hệ thống cơ sở dữ liệu quan hệ và phân tán trong vòng 6 tháng tới, đặt mục tiêu duy trì thời gian truy vấn lân cận dưới 50ms cho các tập dữ liệu quy mô 500.000 bản ghi.

2. Triển khai thuật toán DBRS cho dữ liệu đa thuộc tính: Bộ phận Nghiên cứu và Phát triển (R&D) tại các doanh nghiệp cần áp dụng thuật toán DBRS kết hợp tham số độ thuần khiết MinPur đạt ngưỡng từ 75% đến 85% trong lộ trình 9 tháng, nhằm nâng cao độ chính xác phân khúc khách hàng đa chiều thêm ít nhất 25%.

3. Tự động hóa module dò tìm tham số: Nhóm Kỹ sư Phần mềm cần xây dựng công cụ tương tác tự động trích xuất điểm uốn từ đồ thị 4-dist trong thời gian 3 tháng, giúp cắt giảm 80% thời gian chuyên viên phải ước lượng thủ công hai tham số $\varepsilon$ và MinPts.

4. Ứng dụng phân cụm không gian trong giám sát địa chấn và quy hoạch: Các cơ quan quản lý đô thị và viễn thông cần ứng dụng mô hình phân cụm mật độ để theo dõi các tâm chấn động đất và mật độ thuê bao di động với chu kỳ cập nhật dữ liệu 5 phút một lần, hoàn thiện triển khai thử nghiệm trong vòng 12 tháng.

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

Nội dung và kết quả thực nghiệm của công trình mang lại giá trị thiết thực cho 4 nhóm đối tượng chính:

• Học viên cao học và Nghiên cứu sinh ngành Khoa học Máy tính: Tiếp cận hệ thống lý thuyết chuẩn tắc về không gian metric, tiến trình KDD và các chứng minh toán học của thuật toán mật độ để phát triển các đề tài chuyên sâu.
• Kỹ sư Khoa học Dữ liệu (Data Scientists) và Chuyên viên AI: Sử dụng làm tài liệu tham chiếu để thiết kế các thuật toán phát hiện gian lận tài chính, bóc tách dữ liệu dị biệt và phân khúc thị trường có độ nhiễu cao.
• Chuyên gia phân tích Hệ thống Thông tin Địa lý (GIS) và Quy hoạch: Áp dụng trực tiếp thuật toán phân cụm không gian để xác định vùng trũng kinh tế, mật độ dân cư và phân vùng rủi ro thiên tai trong thực tế.
• Kiến trúc sư Hệ thống Phần mềm (Software Architects): Tham khảo kiến trúc tối ưu hóa truy vấn dữ liệu lớn và giải pháp tích hợp chỉ mục đa chiều vào các hệ thống hỗ trợ ra quyết định thời gian thực.

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

Điểm khác biệt cốt lõi giữa thuật toán DBSCAN và K-Means là gì? K-Means yêu cầu người dùng xác định trước số lượng cụm $k$ và chỉ nhận diện tốt các cụm có hình cầu lồi với mật độ đồng đều, rất nhạy cảm với nhiễu. Ngược lại, DBSCAN tự động xác định số lượng cụm dựa trên mật độ lân cận, phát hiện được các cụm có hình dạng tùy ý và bóc tách hoàn toàn các điểm nhiễu ngoại lai.

Làm thế nào để xác định giá trị tối ưu cho hai tham số Eps và MinPts? Nhóm tác giả đề xuất kỹ thuật đồ thị khoảng cách $k$-dist với giá trị $k=4$ trên không gian dữ liệu 2 chiều. Bằng cách vẽ đồ thị các khoảng cách 4-dist đã sắp xếp, điểm uốn đầu tiên trên đường cong biểu diễn chính là ngưỡng phân tách rõ ràng giữa các điểm thuộc cụm và các điểm nhiễu, từ đó gán giá trị này cho tham số $\varepsilon$.

Thuật toán DBRS cải tiến điểm gì so với DBSCAN truyền thống? DBRS khắc phục hai nhược điểm lớn của DBSCAN bằng cách áp dụng cơ chế lấy mẫu ngẫu nhiên để giảm thiểu số lần truy vấn không gian trên các tập dữ liệu lớn. Đồng thời, DBRS bổ sung tham số độ thuần khiết lân cận MinPur, cho phép phân cụm hiệu quả trên các tập dữ liệu chứa cả thuộc tính không gian lẫn phi không gian và có mật độ biến thiên.

Độ phức tạp tính toán của thuật toán DBSCAN phụ thuộc vào yếu tố nào? Độ phức tạp thời gian của DBSCAN phụ thuộc chủ yếu vào chi phí thực hiện các truy vấn tìm kiếm lân cận vùng $\varepsilon$. Nếu không sử dụng chỉ mục không gian, thuật toán mất chi phí $O(n^2)$. Khi tích hợp cây chỉ mục không gian như $R^*$-Tree, chi phí cho mỗi truy vấn giảm xuống $O(\log n)$, đưa tổng thời gian xử lý toàn bộ cơ sở dữ liệu về mức $O(n \log n)$.

DBSCAN xử lý các điểm dữ liệu nhiễu và ngoại lai như thế nào? Trong quá trình duyệt các điểm dữ liệu, nếu một điểm có số lượng phần tử lân cận trong bán kính $\varepsilon$ nhỏ hơn ngưỡng MinPts và không thuộc vùng lân cận của bất kỳ điểm nòng cốt nào khác, điểm đó sẽ bị gán nhãn là NOISE. Các điểm này bị loại khỏi cấu trúc cụm, đảm bảo độ thuần khiết của mô hình.

Kết luận

• Luận văn đã hệ thống hóa toàn diện cơ sở lý luận về tiến trình khám phá tri thức từ cơ sở dữ liệu và phân loại chi tiết các kỹ thuật phân cụm hiện đại.
• Công trình đã phân tích sâu sắc cấu trúc toán học của 4 thuật toán dựa trên mật độ tiêu biểu: DBSCAN, DBRS, OPTICS và DENCLUE.
• Kết quả thực nghiệm khẳng định DBSCAN vượt trội hơn CLARANS từ 250 đến 1.900 lần về tốc độ, đồng thời xử lý triệt để bài toán nhận diện cụm hình dạng bất kỳ và lọc nhiễu.
• Đã xây dựng thành công chương trình thực nghiệm kiểm chứng giải thuật với độ phức tạp tiệm cận tuyến tính $O(n \log n)$ nhờ tích hợp chỉ mục không gian.
• Luận văn mở ra định hướng nghiên cứu ứng dụng thực tiễn trong phân tích dữ liệu không gian đa chiều và quy hoạch hạ tầng thông minh.

Lộ trình nghiên cứu tiếp theo sẽ tập trung mở rộng mô hình phân cụm mật độ trên nền tảng tính toán phân tán Spark giai đoạn 2026 – 2027. Các nhà nghiên cứu và kỹ sư hệ thống được khuyến khích khai thác ngay các nguyên lý thuật toán trong luận văn để nâng cao năng lực phân tích dữ liệu lớn tại tổ chức.

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

CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ PHÂN CỤM DỮ LIỆU 1. Tổng quan về khai phá dữ liệu 1. Khái niệm Có nhiều định nghĩa về Khai phá dữ liệu (Data Mining) được đưa ra, nhìn chung, có thể hiểu khai phá dữ liệu là quá trình tìm ra các quy luật, các mối quan hệ và các thông tin có ích tiềm ẩn giữa các mẫu dữ liệu trong một cơ sở dữ liệu. Các thông tin có ích này không hoặc khó có thể được tìm ra bởi các hệ cơ sở dữ liệu giao dịch truyền thống.

Các tri thức mà khai phá dữ liệu mang lại là công cụ hữu hiệu đối với tổ chức trong việc hoạch định chiến lược và ra quyết định kinh doanh. Khác với các câu hỏi mà hệ cơ sở dữ liệu truyền thống có thể trả lời như:  Hãy hiển thị số tiền ông Smith trong ngày 5 tháng Giêng ?: thu nhận thông tin riêng lẻ do xử lý giao dịch trực tuyến (on-line transaction processing – OLTP).  Có bao nhiêu nhà đầu tư nước ngoài mua cổ phiếu X trong tháng trước?: thu nhận thông tin thống kê do hệ thống hỗ trợ quyết định thống kê (stastical decision suppport system - DSS).  Hiển thị mọi cổ phiếu trong CSDL với mệnh giá tăng ? thu nhận dữ liệu đa chiều do xử lý phân tích trực tuyến (on-line analytic processing - OLAP).

Khai phá dữ liệu giúp trả lời các câu hỏi mang tính trừu tượng, tổng quát hơn như:  Các cổ phiếu tăng giá có đặc trưng gì ?  Tỷ giá US$ - DMark có đặc trưng gì ?  Hy vọng gì về cổ phiếu X trong tuần tiếp theo ? Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn download by : [e-mail] 12  Trong tháng tiếp theo, sẽ có bao nhiêu đoàn viên công đoàn không trả được nợ của họ ?  Những người mua sản phẩm Y thường mua những sản phẩm nào nữa ? Khai phá dữ liệu là sự kết hợp của nhiều chuyên ngành như cơ sở dữ liệu, học máy, trí tuệ nhân tạo, lý thuyết thông tin, xác suất thống kê, tính toán hiệu năng cao và các phương pháp tính toán mềm… 1. Tiến trình khai phá dữ liệu Một số nhà khoa học xem khai phá dữ liệu (KPDL) là một cách gọi khác của một thuật ngữ rất thông dụng: Khám phá tri thức từ cơ sở dữ liệu (Knowledge Discovery in Database- KDD). Mặt khác, khi chia các bước trong quá trình khám phá tri thức, một số nhà nghiên cứu lại cho rằng, KPDL chỉ là một bước trong quá trình khám phá tri thức [5]. Như vậy, khi xét ở mức tổng quan thì hai thuật ngữ này là tương đương nhau, nhưng khi xét cụ thể thì KPDL được xem là một bước trong quá trình khám phá tri thức.

Nhìn chung, khai phá dữ liệu hay khám phá tri thức từ cơ sở dữ liệu bao gồm các bước sau [4]: Hình 1.1: Tiến trình khám phá tri thức từ cơ sở dữ liệu Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn download by : [e-mail] 13  Trích chọn dữ liệu: Là quá trình trích lọc một lượng dữ liệu phù hợp, cần thiết từ tập dữ liệu lớn (cơ sở dữ liệu tác nghiệp, kho dữ liệu)…  Tiền xử lý dữ liệu: Là bước làm sạch dữ liệu (xử lý dữ liệu không đầy đủ, dữ liệu nhiễu, ngoại lai, dữ liệu không nhất quán…), rút gọn dữ liệu (lấy mẫu dữ liệu, lượng tử hóa…), rời rạc hóa dữ liệu. Kết quả sau bước này là dữ liệu có tính nhất quán, đầy đủ, được rút gọn và được rời rạc hóa.  Chuyển đổi dữ liệu: Là bước chuẩn hóa khuôn dạng và làm mịn dữ liệu, nhằm đưa dữ liệu về dạng thuận lợi nhất để phục vụ cho việc áp dụng các giải thuật khai phá dữ liệu ở bước sau.  Khai phá dữ liệu: Sử dụng các phương pháp, kỹ thuật, các thuật toán để trích lọc ra mẫu có ý nghĩa cùng với các tri thức, quy luật, biểu thức mô tả mối quan hệ của dữ liệu trong một khía cạnh nào đó.

Đây là bước quan trọng và tốn nhiều thời gian nhất của toàn bộ tiến trình KDD.  Đánh giá và biểu diễn tri thức: Trình bày các tri thức, quy luật, biểu thức có ý nghĩa đã tìm được ở bước trước dưới các dạng thức gần gũi, dễ hiểu đối với người sử dụng như đồ thị, biểu đồ, cây, bảng biểu, luật…Đồng thời đưa ra những đánh giá về tri thức khám phá được theo những tiêu chí nhất định. Trong giai đoạn khai phá dữ liệu, có thể cần sự tương tác của con người để điều chỉnh cách thức và kỹ thuật sử dụng trong khai phá, nhằm thu được tri thức phù hợp nhất. Dựa trên các bước của quá trình khai phá dữ liệu như trên, kiến trúc điển hình của một hệ khai phá dữ liệu có thể bao gồm các thành phần như sau: Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn download by : skknchat@gmail.2: Kiến trúc điển hình của một hệ khai phá dữ liệu [4] 1.

Các mô hình khai phá dữ liệu Mô hình khai phá dữ liệu là mô tả về phương pháp, cách thức khai phá thông tin từ dữ liệu và định hướng kiểu tri thức cần khai phá. Một mô hình khai phá dữ liệu có thể được mô tả ở 2 mức:  Mức chức năng (Function level): Mô tả mô hình bằng những thuật ngữ về dự định sử dụng. Ví dụ: Phân lớp, phân cụm…  Mức biểu diễn (Representation level): Biểu diễn cụ thể một mô hình. Ví dụ: Mô hình log-linear, cây phân lớp, phương pháp láng giềng gần nhất… Các mô hình khai phá dữ liệu dựa trên 2 kiểu học: có giám sát và không giám sát (đôi khi được nói đến như là học trực tiếp và không trực tiếp -directed and undirected learning) [6].

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn download by : [e-mail] 15  Các hàm học có giám sát (Supervised learning functions) được sử dụng để dự đoán giá trị. Một ví dụ của thuật toán học có giám sát bao gồm Naive Bayes cho phân lớp (classification).  Các hàm học không giám sát được dùng để tìm ra cấu trúc bên trong, các quan hệ hoặc tính giống nhau trong nội dung dữ liệu nhưng không có lớp hay nhãn nào được gán ưu tiên. Ví dụ của các thuật toán học không giám sát gồm phân nhóm k-mean (k-mean clustering) và các luật kết hợp Apriori.

Tương ứng có 2 loại mô hình khai phá dữ liệu:  Các mô hình dự báo (học có giám sát): - Phân lớp: nhóm các đối tượng thành các lớp riêng biệt và dự đoán một đối tượng sẽ thuộc vào lớp nào. - Hồi qui (Regression): xấp xỉ hàm và dự báo các giá trị liên tục.  Các mô hình mô tả (học không giám sát): - Phân cụm (Clustering): Tìm các nhóm tự nhiên trong dữ liệu. - Các mô hình kết hợp (Association models): Phân tích “giỏ hàng”.

- Trích chọn đặc trưng (Feature extraction): Tạo các thuộc tính (đặc trưng) mới như là kết hợp của các thuộc tính ban đầu. Các hướng tiếp cận và kỹ thuật sử dụng trong khai phá dữ liệu Xuất phát từ hai mô hình khai phá dữ liệu chủ yếu như đã đề cập ở trên, các bài toán (hay chức năng) khai phá dữ liệu giải quyết thường được phân chia thành các dạng sau [4]:  Mô tả khái niệm (concept description & summarization):. Tổng quát, tóm tắt các đặc trưng dữ liệu, Ví dụ: tóm tắt văn bản…  Phân lớp và dự đoán (classification & prediction): Xây dựng các mô hình (chức năng) để mô tả và phân biệt khái niệm cho các lớp hoặc khái Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn download by : [e-mail] 16 niệm để dự đoán trong tương lai, xếp một đối tượng vào một trong những lớp đã biết trước.  Luật kết hợp (association rules): Biểu diễn mối tương quan nhân quả giữa dữ liệu và xu hướng của dữ liệu dưới dạng luật biểu diễn tri thức ở dạng khá đơn giản.

 Khai phá chuỗi theo thời gian (sequential/temporal patterns): tương tự như khai phá luật kết hợp nhưng có thêm tính thứ tự và tính thời gian. Hướng tiếp cận này được ứng dụng nhiều trong lĩnh vực tài chính và thị trường chứng khoán vì nó có tính dự báo cao.  Phân cụm (clustering/segmentation): xếp các đối tượng theo từng cụm (số lượng cũng như tên của cụm chưa được biết trước. Phân cụm còn được gọi là học không giám sát (học không có thầy – unsupervised learning).

 Phân tích bất thường (ngoại lai): Phát hiện sự bất thường của dữ liệu: đối tượng dữ liệu không tuân theo hành vi chung của toàn bộ dữ liệu nhằm phát hiện gian lận hoặc phân tích các sự kiện hiếm… 1. Các dạng dữ liệu có thể khai phá Khai phá dữ liệu là kết hợp của nhiều lĩnh vực khoa học, xử lý nhiều nhiều kiểu dữ liệu khác nhau [4]. Sau đây là một số kiểu dữ liệu điển hình:  CSDL quan hệ (relational databases)  CSDL đa chiều (multidimensional structures, data warehouses)  CSDL dạng giao dịch (transactional databases)  CSDL quan hệ - hướng đối tượng (object-relational databases)  Dữ liệu không gian và thời gian (spatial and temporal data)  Dữ liệu chuỗi thời gian (time-series data) Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn download by : [e-mail] 17  CSDL đa phương tiện (multimedia databases) như âm thanh (audio), hình ảnh (image), phim ảnh (video),.  Dữ liệu Text và Web (text database & www) 1.

Các ứng dụng của khai phá dữ liệu Khai phá dữ liệu được vận dụng để giải quyết các vấn đề thuộc nhiều lĩnh vực khác nhau. Chẳng hạn như giải quyết các bài toán phức tạp trong các ngành đòi hỏi kỹ thuật cao, như tìm kiếm mỏ dầu từ ảnh viễn thám, cảnh báo hỏng hóc trong các hệ thống sản xuất; quy hoạch và phát triển các hệ thống quản lý và sản xuất trong thực tế như dự đoán tải sử dụng điện, mức độ tiêu thụ sản phẩm, phân nhóm khách hàng; áp dụng cho các vấn đề xã hội như phát hiện tội phạm, tăng cường an ninh… Có thể liệt kê ra đây một số ứng dụng điển hình như:  Phân tích dữ liệu và hỗ trợ ra quyết định (data analysis & decision support)  Điều trị y học (medical treatment): mối liên hệ giữa triệu chứng, chẩn đoán và phương pháp điều trị (chế độ dinh dưỡng, thuốc men, phẫu thuật, …).  Text mining & Web mining: phân lớp văn bản và các trang web, tóm tắt văn bản,.  Tin-sinh (bio-informatics): tìm kiếm, đối sánh các hệ gene và thông tin di truyền, mối liên hệ giữa một số hệ gene và một số bệnh di truyền,.

 Tài chính và thị trường chứng khoán (finance & stock market): phân tích tình hình tài chính và dự báo giá của các loại cổ phiếu trong thị trường chứng khoán, .