Phân cụm dữ liệu dựa trên mật độ và ứng dụng (Luận văn Thạc sĩ)

Tìm hiểu phân cụm dữ liệu mật độ, khám phá các thuật toán phổ biến như DBSCAN, OPTICS và những ứng dụng quan trọng trong khoa học dữ liệu.

• Tác giả: Vũ Ngọc Thanh
• Người hướng dẫn: TS. Nguyễn Huy Đức
• Trường học: Trường Đại Học Công Nghệ Thông Tin Và Truyền Thông - Đại Học Thái Nguyên
• 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. Phân Cụm Dữ Liệu Mật Độ Tổng Quan và Tại Sao Quan Trọng

Phân cụm dữ liệu là một kỹ thuật khai phá dữ liệu quan trọng, cho phép khám phá các nhóm dữ liệu tự nhiên trong một tập dữ liệu lớn. Không giống như phân lớp, phân cụm là một phương pháp học không giám sát, không yêu cầu phải định nghĩa trước các mẫu huấn luyện. Điều này làm cho nó trở nên vô cùng hữu ích trong việc khám phá các cấu trúc ẩn trong dữ liệu. Phân cụm dữ liệu mật độ là một hướng tiếp cận đặc biệt hiệu quả, đặc biệt khi dữ liệu chứa các cụm có hình dạng bất kỳ và nhiều nhiễu. Phương pháp này dựa trên ý tưởng rằng các cụm được hình thành bởi các vùng có mật độ điểm dữ liệu cao, được phân tách bởi các vùng có mật độ thấp. DBSCAN và OPTICS là hai thuật toán phân cụm mật độ nổi tiếng. Theo [1], phân cụm dữ liệu mật độ có khả năng tìm ra các cụm bất kỳ hình dạng, khác với phân cụm K-means vốn chỉ thích hợp với dữ liệu phân bố cầu. Phân cụm dữ liệu là quá trình nhóm một tập các đối tượng tương tự nhau trong tập dữ liệu vào các cụm sao cho các đối tượng thuộc cùng một cụm là tương đồng còn các đối tượng thuộc các cụm khác nhau sẽ không tương đồng.

1.1. Tầm Quan Trọng của Phân Cụm Dữ Liệu Không Gian Mật Độ Cao

Phân cụm dữ liệu mật độ cao đặc biệt quan trọng trong các ứng dụng mà dữ liệu có thể có hình dạng bất kỳ và có nhiều điểm nhiễu. Các thuật toán truyền thống như k-means thường gặp khó khăn trong những trường hợp này. Ví dụ, trong phân tích ảnh, các đối tượng có thể có hình dạng phức tạp và không thể dễ dàng phân loại bằng các thuật toán dựa trên khoảng cách. Phân cụm dựa trên mật độ cho phép xác định chính xác hơn các cụm này, cũng như loại bỏ các điểm nhiễu không liên quan.

1.2. Ưu Điểm và Nhược Điểm của Phân Cụm Dữ Liệu Mật Độ

Ưu điểm: Khả năng tìm các cụm có hình dạng bất kỳ, khả năng xử lý nhiễu tốt, không yêu cầu xác định trước số lượng cụm. Nhược điểm: Khó khăn trong việc xác định tham số tối ưu (ví dụ: epsilon và MinPts trong DBSCAN), khó khăn trong việc xử lý các cụm có mật độ rất khác nhau, hiệu suất có thể giảm khi dữ liệu có số chiều cao. Để phân cụm, người ta phải đi tìm cách thích hợp để xác định “khoảng cách” giữa các đối tượng, hay là phép đo tương tự dữ liệu. Đây là các hàm để đo sự giống nhau giữa các cặp đối tượng dữ liệu, thông thường các hàm này hoặc là để tính độ tương tự (Similar) hoặc là tính độ phi tương tự (Dissimilar) giữa các đối tượng dữ liệu.

II. Thách Thức Phân Cụm Mật Độ Xác Định Tham Số và Độ Phức Tạp

Một trong những thách thức lớn nhất của phân cụm dữ liệu mật độ là việc xác định các tham số phù hợp. Ví dụ, trong thuật toán DBSCAN, các tham số epsilon (ε) và MinPts đóng vai trò quan trọng trong việc xác định các cụm. Epsilon xác định bán kính của vùng lân cận, trong khi MinPts xác định số lượng điểm tối thiểu cần thiết để một điểm được coi là điểm lõi. Việc lựa chọn sai các tham số này có thể dẫn đến kết quả phân cụm kém chất lượng. Ngoài ra, độ phức tạp tính toán cũng là một vấn đề, đặc biệt khi xử lý các tập dữ liệu lớn. Các thuật toán phân cụm mật độ có thể tốn kém về mặt tính toán, đặc biệt là khi cần tính toán khoảng cách giữa tất cả các cặp điểm dữ liệu.

2.1. Ảnh Hưởng của Tham Số Epsilon và MinPts trong DBSCAN

Tham số epsilon (ε) xác định kích thước của vùng lân cận xung quanh mỗi điểm dữ liệu. Nếu epsilon quá nhỏ, nhiều điểm sẽ bị coi là nhiễu và không thuộc bất kỳ cụm nào. Nếu epsilon quá lớn, các cụm có thể bị hợp nhất lại với nhau, dẫn đến các cụm lớn và không có ý nghĩa. Tham số MinPts xác định số lượng điểm tối thiểu cần thiết trong vùng lân cận của một điểm để điểm đó được coi là điểm lõi. Nếu MinPts quá nhỏ, nhiều điểm có thể được coi là điểm lõi, dẫn đến các cụm nhỏ và rời rạc. Nếu MinPts quá lớn, các cụm có thể bị bỏ sót.

2.2. Giải Pháp Giảm Độ Phức Tạp Tính Toán Phân Cụm Mật Độ

Để giảm độ phức tạp tính toán, có thể sử dụng các kỹ thuật như lập chỉ mục không gian (ví dụ: cây R-tree) để tăng tốc quá trình tìm kiếm các điểm lân cận. Ngoài ra, các thuật toán xấp xỉ cũng có thể được sử dụng để giảm số lượng tính toán khoảng cách cần thiết. Một phương pháp khác là sử dụng các thuật toán song song hoặc phân tán để phân tán quá trình tính toán trên nhiều máy tính. DBRS được giới thiệu là thuật toán phân cụm dữ liệu không gian với các đặc trưng như sau: Các cụm được phát hiện có nhiều hình dạng khác nhau. Chẳng hạn như dữ liệu về địa chỉ của sinh viên của một trường đại học. Khi phân cụm sinh viên theo địa chỉ thì có thể có các cụm sinh viên tại các nhà chung cư (cụm có dạng hình chữ nhật), cụm sinh viên dọc theo các tuyến xe bus (cụm có dạng tuyến),...

III. Thuật Toán DBSCAN Hướng Dẫn Chi Tiết và Các Bước Triển Khai

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) là một thuật toán phân cụm dữ liệu mật độ phổ biến. Thuật toán này hoạt động bằng cách xác định các điểm lõi, điểm biên và điểm nhiễu dựa trên các tham số epsilon (ε) và MinPts. Điểm lõi là điểm có ít nhất MinPts điểm trong vùng lân cận epsilon của nó. Điểm biên là điểm không phải là điểm lõi nhưng nằm trong vùng lân cận của một điểm lõi. Điểm nhiễu là điểm không phải là điểm lõi hoặc điểm biên. Thuật toán bắt đầu bằng cách chọn một điểm chưa được phân loại và tìm tất cả các điểm kề mật độ với điểm đó. Nếu điểm đó là điểm lõi, một cụm mới được tạo và tất cả các điểm kề mật độ với điểm đó được thêm vào cụm. Quá trình này được lặp lại cho đến khi không còn điểm nào có thể được thêm vào cụm. Sau đó, thuật toán tiếp tục với một điểm chưa được phân loại khác.Theo [3], DBSCAN thực hiện tốt trên 100 tiêu chuẩn đánh giá hiệu quả thuật toán.

3.1. Các Bước Chi Tiết của Thuật Toán DBSCAN

1. Chọn một điểm chưa được phân loại từ tập dữ liệu. 2. Tìm tất cả các điểm trong vùng lân cận epsilon của điểm đó. 3. Nếu số lượng điểm trong vùng lân cận lớn hơn hoặc bằng MinPts, điểm đó được đánh dấu là điểm lõi và một cụm mới được tạo. 4. Tất cả các điểm trong vùng lân cận epsilon của điểm lõi được thêm vào cụm. 5. Lặp lại bước 2-4 cho tất cả các điểm trong cụm cho đến khi không còn điểm nào có thể được thêm vào cụm. 6. Nếu số lượng điểm trong vùng lân cận nhỏ hơn MinPts, điểm đó được đánh dấu là điểm nhiễu. 7. Lặp lại bước 1-6 cho tất cả các điểm chưa được phân loại trong tập dữ liệu.

3.2. Ví Dụ Triển Khai DBSCAN trong Python với Scikit learn

from sklearn.cluster import DBSCAN
import numpy as np
X = np.array([[1, 2], [2, 2], [2, 3],
              [8, 7], [8, 8], [7, 8]])
dbscan = DBSCAN(eps=3, min_samples=2)
clusters = dbscan.fit_predict(X)
print(clusters) # Output: [ 0  0  0  1  1  1]

Đoạn code trên minh họa cách sử dụng thư viện Scikit-learn trong Python để triển khai thuật toán DBSCAN. Các tham số epsilon và MinPts có thể được điều chỉnh để phù hợp với đặc điểm của dữ liệu.

IV. Thuật Toán OPTICS Giải Pháp Cho Dữ Liệu Mật Độ Thay Đổi

OPTICS (Ordering Points To Identify the Clustering Structure) là một thuật toán phân cụm dữ liệu mật độ, được thiết kế để giải quyết vấn đề các cụm có mật độ khác nhau. Thay vì tạo ra một phân hoạch cụ thể, OPTICS tạo ra một thứ tự của các điểm dữ liệu, biểu thị cấu trúc phân cụm của dữ liệu. Thứ tự này cho phép xác định các cụm ở các mức mật độ khác nhau. OPTICS không trả về một phân hoạch cụ thể mà cung cấp thông tin đầy đủ để tạo các phân hoạch với epsilon khác nhau [3].

4.1. Reachability Distance và Order Distance trong OPTICS

OPTICS sử dụng hai khái niệm chính: reachability distance và core distance. Core distance của một điểm p là khoảng cách epsilon nhỏ nhất sao cho p là điểm lõi. Reachability distance của một điểm q từ một điểm p là khoảng cách nhỏ nhất giữa p và q, hoặc core distance của p, tùy theo giá trị nào lớn hơn. Những khái niệm này giúp xác định các cụm ở các mức mật độ khác nhau.

4.2. Ưu Điểm và Nhược Điểm của Thuật Toán OPTICS so với DBSCAN

Ưu điểm: OPTICS có thể xử lý các cụm có mật độ khác nhau tốt hơn DBSCAN. OPTICS cung cấp thông tin đầy đủ về cấu trúc phân cụm của dữ liệu, cho phép tạo các phân hoạch với các mức mật độ khác nhau. Nhược điểm: OPTICS phức tạp hơn DBSCAN và đòi hỏi nhiều bộ nhớ hơn. Việc phân tích kết quả của OPTICS có thể tốn thời gian hơn so với DBSCAN.

V. Ứng Dụng Thực Tế Phân Cụm Dữ Liệu Mật Độ Từ Y Tế Đến An Ninh

Phân cụm dữ liệu mật độ có nhiều ứng dụng thực tế trong các lĩnh vực khác nhau. Trong y tế, nó có thể được sử dụng để xác định các nhóm bệnh nhân có các triệu chứng tương tự hoặc để phát hiện các ổ dịch bệnh. Trong an ninh, nó có thể được sử dụng để phát hiện các hoạt động gian lận hoặc để xác định các khu vực có tỷ lệ tội phạm cao. Phân cụm dữ liệu mật độ cũng có thể được sử dụng trong marketing để phân khúc khách hàng hoặc trong phân tích mạng xã hội để xác định các cộng đồng trực tuyến.

5.1. Ứng Dụng Phân Cụm Mật Độ trong Phát Hiện Gian Lận và Tội Phạm

Trong lĩnh vực phát hiện gian lận, phân cụm mật độ có thể được sử dụng để xác định các giao dịch bất thường hoặc các tài khoản có hoạt động đáng ngờ. Bằng cách phân cụm dữ liệu giao dịch, các giao dịch gian lận có thể được xác định là các điểm nhiễu hoặc các cụm có mật độ thấp. Tương tự, trong lĩnh vực phân tích tội phạm, phân cụm mật độ có thể được sử dụng để xác định các khu vực có tỷ lệ tội phạm cao hoặc để phát hiện các mẫu tội phạm.

5.2. Phân Tích Dữ Liệu Khách Hàng và Phân Khúc Thị Trường Nhờ Phân Cụm Mật Độ

Trong marketing, phân cụm mật độ có thể được sử dụng để phân khúc khách hàng dựa trên hành vi mua hàng, nhân khẩu học hoặc các yếu tố khác. Bằng cách phân cụm dữ liệu khách hàng, các nhóm khách hàng có nhu cầu và sở thích tương tự có thể được xác định. Thông tin này có thể được sử dụng để tạo ra các chiến dịch marketing nhắm mục tiêu hoặc để phát triển các sản phẩm và dịch vụ mới phù hợp với nhu cầu của từng phân khúc khách hàng.

VI. Kết Luận Tương Lai Phân Cụm Dữ Liệu Mật Độ và Các Hướng Nghiên Cứu

Phân cụm dữ liệu mật độ là một kỹ thuật mạnh mẽ để khám phá các cấu trúc ẩn trong dữ liệu. Tuy nhiên, vẫn còn nhiều thách thức cần được giải quyết, bao gồm việc xác định tham số tối ưu, giảm độ phức tạp tính toán và xử lý dữ liệu có số chiều cao. Các hướng nghiên cứu tiềm năng bao gồm việc phát triển các thuật toán phân cụm mật độ thích ứng, kết hợp các kỹ thuật phân cụm mật độ với các phương pháp học máy khác và ứng dụng các thuật toán phân cụm mật độ vào các lĩnh vực mới.

6.1. Các Hướng Nghiên Cứu Phát Triển Thuật Toán Phân Cụm Mật Độ Thích Ứng

Một hướng nghiên cứu quan trọng là phát triển các thuật toán phân cụm mật độ thích ứng có thể tự động điều chỉnh các tham số của chúng để phù hợp với đặc điểm của dữ liệu. Các thuật toán này có thể sử dụng các kỹ thuật như học tăng cường hoặc thuật toán di truyền để tìm ra các tham số tối ưu cho từng tập dữ liệu. Chức năng của nó là xác định một nhóm nhỏ các đối tượng dữ liệu khác thường so với các dữ liệu trong cơ sở dữ liệu, tức là các đối tượng dữ liệu không tuân theo các hành vi hoặc mô hình dữ liệu nhằm tránh sự ảnh hưởng của chúng tới quá trình và kết quả của phân cụm.

6.2. Kết Hợp Phân Cụm Mật Độ với Các Phương Pháp Học Máy Khác

Một hướng nghiên cứu khác là kết hợp các thuật toán phân cụm mật độ với các phương pháp học máy khác, chẳng hạn như phân lớp hoặc hồi quy. Ví dụ, phân cụm mật độ có thể được sử dụng để tiền xử lý dữ liệu trước khi áp dụng một thuật toán phân lớp. Hoặc, kết quả của phân cụm mật độ có thể được sử dụng để xây dựng các mô hình dự đoán tốt hơn.

Nội dung chính

Tổng quan nghiên cứu

Sự bùng nổ của công nghệ thông tin và quá trình số hóa đã tạo ra khối lượng dữ liệu khổng lồ với dung lượng từ hàng Gigabyte đến hàng Terabyte, ghi nhận mức tăng trưởng hơn 50% mỗi năm. Nhu cầu cấp thiết đặt ra cho các tổ chức là phải chuyển đổi nguồn tài nguyên thô này thành tri thức hữu ích nhằm phục vụ công tác dự báo và hỗ trợ ra quyết định. Trong các kỹ thuật khai phá dữ liệu, phân cụm dữ liệu đóng vai trò then chốt như một phương pháp học không giám sát nhằm tự động phát hiện các cấu trúc tiềm ẩn mà không cần dữ liệu gắn nhãn trước.

Tuy nhiên, các giải thuật phân cụm truyền thống dựa trên khoảng cách thường chỉ nhận diện được các cụm dạng hình cầu và bộc lộ sự hạn chế nghiêm trọng khi xử lý dữ liệu chứa nhiều tạp âm hoặc các cụm có hình dạng bất kỳ. Nhằm giải quyết triệt để vấn đề này, luận văn thạc sĩ chuyên ngành Khoa học máy tính với đề tài nghiên cứu phương pháp phân cụm dữ liệu dựa trên mật độ và ứng dụng được thực hiện bởi tác giả Vũ Ngọc Thanh dưới sự hướng dẫn khoa học của Tiến sĩ Nguyễn Huy Đức 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.

Mục tiêu cụ thể của công trình là hệ thống hóa các kỹ thuật phân cụm hiện đại, đi sâu phân tích giải thuật mật độ tiêu biểu như DBSCAN, DBRS, OPTICS, đồng thời thiết kế và xây dựng chương trình thực nghiệm hoàn chỉnh. Nghiên cứu mang ý nghĩa thực tiễn lớn khi chứng minh giải thuật dựa trên mật độ có khả năng nâng cao hiệu suất xử lý từ 250 đến 1.900 lần so với các phương pháp phân hoạch truyền thống, mở ra hướng ứng dụng hiệu quả trong quy hoạch đô thị, phân tích tài chính và quản lý hệ thống dữ liệu không gian.

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 xây dựng trên nền tảng tiến trình khám phá tri thức từ cơ sở dữ liệu gồm 5 giai đoạn chuẩn mực: trích chọn dữ liệu, tiền xử lý, chuyển đổi, khai phá dữ liệu và đánh giá biểu diễn tri thức. Trọng tâm của luận văn vận dụng lý thuyết không gian metric với các độ đo khoảng cách quen thuộc như Minkowski, khoảng cách Euclide và Manhattan để xác định sự tương đồng giữa các phần tử dữ liệu.

Khung lý thuyết mật độ đưa vào hệ thống 3 khái niệm cốt lõi:

• Điểm nòng cốt: Phần tử có số lượng đối tượng trong vùng lân cận bán kính đạt tối thiểu một ngưỡng quy định.
• Điểm biên: Phần tử nằm trong vùng lân cận của điểm nòng cốt nhưng bản thân không đạt ngưỡng mật độ tối thiểu.
• Điểm nhiễu: Các phần tử ngoại lai không thuộc vùng lân cận của bất kỳ điểm nòng cốt nào.

Hệ thống lý thuyết được hoàn thiện thông qua việc mô hình hóa các quan hệ mật độ đạt được trực tiếp, mật độ đạt được và mật độ liên thông. Đây là nền tảng toán học vững chắc để giải thuật DBSCAN và biến thể mở rộng DBRS nhận diện chính xác các cụm dữ liệu đa hình học.

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

Phương pháp nghiên cứu kết hợp giữa nghiên cứu lý thuyết chuyên sâu và mô phỏng thực nghiệm trên máy tính.

• Cỡ mẫu và dữ liệu: Tác giả sử dụng bộ dữ liệu không gian 2 chiều với quy mô từ 1.000 đến hơn 50.000 điểm dữ liệu, mô phỏng các phân bố hình học phức tạp và mật độ khác nhau.
• Phương pháp chọn mẫu: Áp dụng kỹ thuật lấy mẫu phân tầng kết hợp lấy mẫu ngẫu nhiên không hoàn lại nhằm kiểm tra độ bền vững của thuật toán trước các yếu tố ngoại lai.
• Phương pháp phân tích: Lựa chọn giải thuật DBSCAN kết hợp cấu trúc chỉ mục cây không gian R-tree để tối ưu hóa truy vấn lân cận. Lý do lựa chọn là giải thuật này không yêu cầu khai báo trước số lượng cụm, đồng thời có khả năng cô lập 100% điểm nhiễu và giảm độ phức tạp thời gian từ mức lũy thừa bậc 2 xuống mức xấp xỉ tuyến tính. Toàn bộ quá trình nghiên cứu và thử nghiệm được hoàn thiện trong lộ trình 9 tháng của năm 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 nghiệm thực tế đã mang lại 4 phát hiện quan trọng:

Thứ nhất, giải thuật DBSCAN thể hiện ưu thế tuyệt đối trong việc phát hiện các cụm có hình dạng bất kỳ, bao gồm dạng tuyến uốn lượn, hình vòng nhẫn và các cấu trúc phi lồi. Độ chính xác phân tách cụm đạt trên 96%, trong khi các thuật toán phân hoạch như K-Means hoặc CLARANS bị phân mảnh hoàn toàn và gộp sai lệch các cụm liền kề.

Thứ hai, khả năng khử nhiễu tự động của phương pháp đạt hiệu quả vượt trội. Các điểm dị biệt nằm ngoài ngưỡng bán kính bị cô lập hoàn toàn thành tập hợp riêng biệt, giúp giảm thiểu 85% sai số phân cụm so với phương pháp truyền thống.

Thứ ba, về tốc độ thực thi, DBSCAN cho thấy thời gian xử lý tăng gần như tuyến tính theo kích thước dữ liệu. Khi kích thước tập dữ liệu tăng từ 2.000 lên 50.000 điểm, DBSCAN duy trì tốc độ xử lý nhanh hơn CLARANS từ 250 đến 1.900 lần.

Thứ tư, phương pháp heuristic xác định tham số thông qua đồ thị khoảng cách 4 láng giềng gần nhất cho phép chuẩn hóa tham số MinPts cố định bằng 4 cho không gian 2 chiều, giúp người dùng dễ dàng xác định ngưỡng bán kính tối ưu mà không cần can thiệp thử nghiệm nhiều lần.

Thảo luận kết quả

Sở dĩ giải thuật mật độ đạt được hiệu năng cao vượt bậc là nhờ cơ chế mở rộng cụm dựa trên tính liên thông mật độ thay vì tối ưu hóa hàm khoảng cách toàn cục tới các tâm điểm giả định. Khi tích hợp cùng các cấu trúc cây chỉ mục không gian như R-tree hay R*-tree, chi phí truy vấn lân cận giảm mạnh từ bậc n xuống mức logarit.

Kết quả dữ liệu có thể được mô tả trực quan qua 2 dạng biểu diễn:

• Biểu đồ phân tán 2 chiều: Các cụm dữ liệu phức tạp được mã hóa bằng các dải màu riêng biệt, các điểm nhiễu phân bố rải rác được đánh dấu màu đen độc lập tại vùng rìa.
• Bảng so sánh thời gian thực thi: Thể hiện rõ đường cong thời gian của DBSCAN bám sát trục hoành, trong khi đường biểu diễn của CLARANS dốc đứng theo dạng parabol bậc 2 khi số lượng điểm vượt mốc 10.000 bản ghi.

Tuy nhiên, nghiên cứu cũng chỉ ra hạn chế của DBSCAN là hoạt động kém hiệu quả khi dữ liệu có sự chênh lệch mật độ giữa các cụm vượt quá 40%. Để khắc phục điểm này, việc kết hợp thuật toán DBRS với thuộc tính phi không gian hoặc cấu trúc phân cấp OPTICS là giải pháp mở rộng hoàn toàn khả thi.

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

Dựa trên các kết quả đạt được, luận văn đưa ra 4 khuyến nghị then chốt nhằm nâng cao hiệu quả ứng dụng khai phá dữ liệu mật độ:

Thứ nhất, chuẩn hóa quy trình tiền xử lý dữ liệu trước khi phân cụm. Đội ngũ kỹ thuật dữ liệu cần thực hiện làm sạch, loại bỏ thuộc tính rỗng và chuẩn hóa thang đo về khoảng giá trị từ 0 đến 1 cho 100% biến số đầu vào. Mục tiêu là triệt tiêu hoàn toàn sự sai lệch do đơn vị tính trong vòng 30 ngày đầu triển khai dự án.

Thứ hai, tích hợp cấu trúc chỉ mục không gian đa chiều vào hệ quản trị cơ sở dữ liệu. Các kỹ sư hệ thống cần cấu hình cây R-tree hoặc cây tứ phân để tối ưu hóa thời gian phản hồi truy vấn lân cận dưới 15 mili-giây cho các cơ sở dữ liệu có quy mô trên 500.000 bản ghi, hoàn thành trong giai đoạn 3 tháng.

Thứ ba, áp dụng thuật toán mở rộng DBRS cho các bài toán phân tích đa chiều kết hợp thuộc tính phi không gian. Các doanh nghiệp bán lẻ và viễn thông nên triển khai mô hình này với ngưỡng độ thuần khiết từ 0,7 đến 0,9 nhằm phân nhóm hành vi khách hàng chính xác hơn trong thời gian 6 tháng tới.

Thứ tư, tự động hóa việc xác định tham số bán kính bằng thuật toán tìm điểm uốn trên đồ thị 4 láng giềng. Bộ phận phân tích dữ liệu nên xây dựng module quét tự động nhằm giảm 90% thời gian cấu hình thủ công của chuyên viên.

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

Công trình nghiên cứu mang giá trị học thuật và ứng dụng thực tiễn cao, đặc biệt phù hợp cho 4 nhóm đối tượng:

Nhóm 1: Học viên cao học và nghiên cứu sinh chuyên ngành Khoa học máy tính, Công nghệ thông tin và Hệ thống thông tin. Luận văn cung cấp bức tranh toàn cảnh về 6 phương pháp phân cụm kinh điển cùng hệ thống chứng minh toán học chặt chẽ về các giải thuật mật độ.

Nhóm 2: Kỹ sư dữ liệu và chuyên gia trí tuệ nhân tạo. Nhóm này có thể ứng dụng trực tiếp mã nguồn, thuật giải DBSCAN và kỹ thuật tối ưu hóa chỉ mục không gian vào việc xây dựng các đường ống xử lý dữ liệu lớn với hơn 100.000 đối tượng.

Nhóm 3: Chuyên gia quy hoạch đô thị và phân tích hệ thống thông tin địa lý. Luận văn cung cấp công cụ đắc lực để phân cụm mật độ dân cư, phân tích mạng lưới giao thông công cộng và theo dõi khoanh vùng các điểm nóng địa chấn nguy hiểm.

Nhóm 4: Chuyên viên phân tích rủi ro tài chính và an ninh mạng. Ứng dụng khả năng phát hiện ngoại lai tự động của DBSCAN để nhận diện chính xác 99% các giao dịch thẻ tín dụng bất thường hoặc các cuộc tấn công từ chối dịch vụ trong hệ thống ngân hàng số.

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

Thuật toán DBSCAN có điểm gì vượt trội so với thuật toán K-Means truyền thống? DBSCAN vượt trội ở khả năng tự động tìm kiếm các cụm có hình dạng bất kỳ mà không cần người dùng khai báo trước số lượng cụm k. Ngoài ra, DBSCAN có cơ chế nhận diện và cô lập điểm nhiễu hoàn hảo, trong khi K-Means buộc mọi điểm ngoại lai phải thuộc về một cụm nhất định, gây méo mó kết quả phân tích.

Làm thế nào để xác định giá trị bán kính lân cận và số điểm tối thiểu một cách tối ưu? Tác giả đề xuất sử dụng heuristic dựa trên đồ thị khoảng cách 4 láng giềng gần nhất đã được sắp xếp. Tham số số điểm tối thiểu được cố định bằng 4 cho không gian 2 chiều, sau đó người phân tích xác định điểm ngưỡng uốn cong đầu tiên trên đồ thị để lấy giá trị khoảng cách đó làm bán kính lân cận tối ưu.

Thuật toán DBSCAN gặp những hạn chế nào trong môi trường dữ liệu thực tế? Hạn chế lớn nhất của DBSCAN là kém hiệu quả khi các cụm dữ liệu có mật độ chênh lệch quá lớn, do thuật toán chỉ sử dụng một bộ tham số toàn cục duy nhất. Bên cạnh đó, nếu không sử dụng cây chỉ mục không gian, chi phí tính toán khoảng cách giữa các cặp điểm sẽ rất tốn kém khi số chiều dữ liệu vượt quá 10 chiều.

Thuật toán DBRS đã cải tiến những điểm yếu nào của DBSCAN? DBRS kết hợp phương pháp lấy mẫu ngẫu nhiên để giảm thiểu số lần truy vấn cơ sở dữ liệu lớn, giúp tăng tốc độ phân tích cho tập dữ liệu hàng trăm nghìn bản ghi. Đồng thời, DBRS đưa thêm tham số độ thuần khiết để xem xét đồng thời cả thuộc tính không gian và thuộc tính phi không gian của đối tượng.

Độ phức tạp tính toán của thuật toán DBSCAN là bao nhiêu trong các trường hợp? Trong trường hợp xấu nhất khi không có cấu trúc chỉ mục hỗ trợ, độ phức tạp thời gian của DBSCAN là bậc hai của kích thước dữ liệu. Tuy nhiên, khi cơ sở dữ liệu được đánh chỉ mục không gian bằng cây R-tree, độ phức tạp trung bình giảm xuống mức tích giữa số phần tử và logarit của số phần tử.

Kết luận

• Hệ thống hóa toàn diện cơ sở lý luận về khai phá tri thức từ cơ sở dữ liệu và phân loại chi tiết 6 trường phái phân cụm dữ liệu hiện đại.
• Làm sáng tỏ cấu trúc toán học và cơ chế vận hành của giải thuật phân cụm dựa trên mật độ DBSCAN cùng các biến thể mở rộng DBRS, OPTICS.
• Thực nghiệm chứng minh DBSCAN đạt hiệu năng xử lý vượt trội gấp 250 đến 1.900 lần so với giải thuật CLARANS và cô lập triệt để các điểm dữ liệu nhiễu.
• Đề xuất quy trình chuẩn hóa cấu hình tham số thông qua đồ thị 4 láng giềng kết hợp xây dựng thành công ứng dụng thử nghiệm trực quan.
• Mở ra định hướng nghiên cứu hoàn thiện các giải thuật lai ghép mật độ và xử lý dữ liệu đa chiều quy mô trên 1.000.000 mẫu trong giai đoạn tiếp theo.

Nghiên cứu của tác giả Vũ Ngọc Thanh là tài liệu tham khảo học thuật giá trị, đóng góp thiết thực cho cộng đồng nghiên cứu khoa học máy tính và các chuyên gia phân tích dữ liệu ứng dụng.

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 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 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.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 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 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 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,. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 18 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.