I. Tổng Quan Về Khám Phá Tri Thức và Phân Cụm Dữ Liệu
Khám phá tri thức từ cơ sở dữ liệu là quá trình nhận diện các mẫu, mô hình hữu ích, mới lạ, khả thi và dễ hiểu. Đây là một lĩnh vực nghiên cứu sử dụng các phương tiện tự động để phân tích lượng lớn dữ liệu. Mục tiêu chính là tìm ra các mẫu và mô hình ẩn sâu trong dữ liệu. Các thông tin và tri thức thu được có thể ứng dụng trong phân tích thị trường, phát hiện gian lận, kiểm soát sản xuất và nghiên cứu khoa học. Khai phá dữ liệu có thể xem như kết quả của sự tiến hóa công nghệ thông tin. KDD (Knowledge Discovery in Databases) là quá trình trích chọn các mẫu hấp dẫn. Quá trình KDD bao gồm lựa chọn dữ liệu, tiền xử lý, chuyển đổi, khai phá dữ liệu, và biểu diễn tri thức. Các bước này đảm bảo dữ liệu nhất quán, đầy đủ, được rút gọn và rời rạc hóa. Trích dẫn: 'Khai phá dữ liệu có thể xem như là một kết quả của sự tiến hóa tự nhiên của công nghệ thông tin'.
1.1. Vai Trò và Mục Tiêu Chính của Khám Phá Tri Thức
Vai trò của khám phá tri thức là thu thập tri thức từ dữ liệu có sẵn. Nhiều tổ chức đã thu thập lượng lớn dữ liệu, và cần các phương pháp để khai thác thông tin tiềm ẩn. Dữ liệu chứa đựng thông tin về thị trường, đối thủ, khách hàng, sản xuất, vận hành, và các giải pháp cải tiến quy trình. Chỉ một phần nhỏ dữ liệu (5-10%) được phân tích. Dữ liệu chưa phân tích vẫn tiếp tục được thu thập, dù tốn kém, vì tiềm năng chứa đựng thông tin quan trọng. Lượng dữ liệu lớn gây khó khăn cho các phương pháp phân tích truyền thống. Trích dẫn: 'Trong kinh doanh, dữ liệu hàm chứa các thông tin về thị trường, về các đối thủ và về các khách hàng'.
1.2. Khái Niệm Phân Cụm Dữ Liệu và Ứng Dụng Thực Tế
Phân cụm dữ liệu (Data Clustering) là quá trình chia tập dữ liệu thành các cụm sao cho các phần tử trong cùng một cụm tương tự nhau, và các phần tử trong các cụm khác nhau thì khác nhau. Số lượng cụm có thể được xác định trước hoặc tự động xác định. Trong học máy, phân cụm là một vấn đề học không giám sát, vì nó tìm cấu trúc trong dữ liệu mà không có thông tin về cụm. Ứng dụng của phân cụm rất đa dạng, bao gồm thương mại, sinh học, phân tích dữ liệu không gian, lập quy hoạch đô thị, nghiên cứu trái đất, và tóm tắt dữ liệu. Trích dẫn: 'Phân cụm dữ liệu (Data Clustering) là quá trình phân chia một tập dữ liệu đầu vào thành các cụm dữ liệu sao cho các phần tử trong một cụm "tương tự" với nhau'.
II. Cách Phân Cụm Phân Hoạch K Means và Ưu Điểm Vượt Trội
Với số lượng cụm đã định, phương pháp phân hoạch sẽ lần lượt phân các đối tượng dữ liệu vào các cụm, sau đó thực hiện lặp quá trình điều chỉnh để tối thiểu hàm mục tiêu. Thuật toán k-means là thuật toán thông dụng nhất trong phương pháp này. Trong các thuật toán này, số lượng cụm k thường được xác định trước hoặc đặt bởi người dùng tham số. Với tập dữ liệu D gồm n đối tượng trong không gian s chiều, các đối tượng được phân thành k cụm sao cho tổng bình phương độ lệch của mỗi mẫu tới tâm của nó là nhỏ nhất. Trích dẫn: 'Với tập dữ liệu D gồm n đối tượng trong không gian s chiều, các đối tượng được phân thành k cụm sao cho tổng bình phương độ lệch của mỗi mẫu tới tâm của nó là nhỏ nhất'.
2.1. Thuật Toán K Means Chi Tiết và Các Bước Thực Hiện
Thuật toán k-means (MacQueen, 1967) chia tập dữ liệu cho trước thành k cụm { }, sao cho tổng bình phương khoảng cách các đối tượng dữ liệu tới tâm cụm chứa nó là cực tiểu. Hàm mục tiêu của thuật toán này là: $\sum_{i=1}^{k} \sum_{x \in S_i} ||x - \mu_i||^2$$. Thuật toán thực hiện như sau: Bước 0: Xác định trước số lượng cụm k và điều kiện dừng; Bước 1: Khởi tạo ngẫu nhiên k điểm làm các tâm cụm; Bước 2: Lặp khi điều kiện dừng chưa thỏa mãn. Trích dẫn: 'Thuật toán k-means (MacQueen, 1967) chia tập dữ liệu cho trước thành k cụm { }, sao cho tổng bình phương khoảng cách các đối tượng dữ liệu tới tâm cụm chứa nó là cực tiểu'.
2.2. Ưu Điểm và Nhược Điểm của Thuật Toán K Means
Ưu điểm của thuật toán k-means là đơn giản, dễ cài đặt và hiệu quả với dữ liệu lớn. Tuy nhiên, thuật toán nhạy cảm với việc khởi tạo tâm cụm ban đầu và có thể hội tụ vào cực tiểu cục bộ. Điều kiện dừng của thuật toán thường chọn từ các điều kiện sau: số lần lặp t = tmax (tmax là số cho trước); giá trị của hàm E nhỏ hơn một ngưỡng cho trước; hoặc khi các cụm không thay đổi. Độ phức tạp của thuật toán là O(tns), với n là số mẫu, s là số thuộc tính, và t là số lần lặp. Trích dẫn: 'Nếu tập dữ liệu D gồm n mẫu với số thuộc tính là s, phân thành k cụm và số lần lặp ở bước 2 là t thì độ phức tạp của thuật toán chỉ là 0(tns)'.
III. Phân Cụm Phân Cấp Cách Tiếp Cận Từ Dưới Lên Bottom Up
Trong phương pháp này, tập dữ liệu được sắp xếp thành một cấu trúc có dạng hình cây gọi là cây phân cụm. Cây này có thể được xây dựng nhờ kỹ thuật đệ quy theo hai phương pháp tổng quát: phương pháp dưới lên (bottom up) và phương pháp trên xuống (top down). Các thuật toán theo phương pháp dưới lên còn gọi là các thuật toán trộn, người ta khởi tạo mỗi đối tượng làm một cụm và dùng thủ tục đệ quy để trộn hai cụm gần nhất với nhau trong mỗi bước để có kết quả chia cụm mới. Thủ tục đệ quy kết thúc khi ta có tập duy nhất là toàn bộ dữ liệu. Trích dẫn: 'Trong phương pháp này tập dữ liệu được sắp xếp thành một cấu trúc có dạng hình cây gọi là cây phân cụm'.
3.1. Phương Pháp Dưới Lên Bottom Up Chi Tiết và Ví Dụ Minh Họa
Các thuật toán theo phương pháp dưới lên (bottom-up) còn gọi là các thuật toán trộn. Người ta khởi tạo mỗi đối tượng làm một cụm và dùng thủ tục đệ quy để trộn hai cụm gần nhất với nhau trong mỗi bước để có kết quả chia cụm mới. Thủ tục đệ quy kết thúc khi ta có tập duy nhất là toàn bộ dữ liệu. Các thuật toán phân biệt với nhau ở tiêu chuẩn đánh giá hai cụm nào là gần nhất dựa trên khoảng cách các cụm chọn trước. Trích dẫn: 'Các thuật toán theo phương pháp dưới lên (bottom up) còn gọi là các thuật toán trộn, người ta khởi tạo mỗi đối tượng làm một cụm và dùng thủ tục đệ quy để trộn hai cụm gần nhất với nhau trong mỗi bước để có kết quả chia cụm mới'.
3.2. Các Quy Tắc Liên Kết Trong Phân Cụm Phân Cấp
Kết quả phân cụm phụ thuộc vào metric được dùng để tính khoảng cách giữa các đối tượng. Kết quả phân cụm phân cấp cũng phụ thuộc vào quy tắc liên kết hay cách tính khoảng cách giữa hai cụm. Với metric trong không gian đặc trưng xác định bởi một chuẩn đã có, sau đây là một số quy tắc liên kết thông dụng: liên kết đơn, liên kết đầy đủ, liên kết trung bình giữa các nhóm. Trích dẫn: 'Kết quả phân cụm phụ thuộc vào metric được dùng để tính khoảng cách giữa các đối tượng'.
IV. Phân Cụm Dựa Trên Mật Độ DBSCAN và Ứng Dụng Thực Tế
Phương pháp phân cụm dựa vào mật độ xem các cụm như là các vùng có mật độ các đối tượng lớn trong không gian dữ liệu. Các phương pháp dựa vào mật độ có thể sử dụng để loại bỏ nhiễu và phát hiện ra các cụm có hình dạng tự nhiên. Thuật toán dựa vào mật độ đầu tiên là thuật toán DBSCAN (Ester et al, 1996), thuật toán này xem xét mật độ theo lân cận của mỗi đối tượng, nếu số lượng các đối tượng trong khoảng cách của một đối tượng lớn hơn ngưỡng MinPts thì đối tượng đó được xem là nằm trong một cụm. Trích dẫn: 'Phương pháp phân cụm dựa vào mật độ xem các cụm như là các vùng có mật độ các đối tượng lớn trong không gian dữ liệu'.
4.1. Thuật Toán DBSCAN Chi Tiết và Các Tham Số Quan Trọng
Thuật toán DBSCAN (Density – based Spatial Clustering of Applications with Noise) nhóm các vùng có mật độ đủ cao vào trong một cụm và phát triển dự trên các đối tượng lõi để có các cụm với hình dạng tự nhiên trong các tập không gian đặc trưng. Thuật toán yêu cầu xác định trước hai tham số đầu vào là ε và MinPts. Phân cụm dữ liệu theo thuật toán DBSCAN áp dụng các luật sau: các đối tượng nằm trong hình cầu bán kính ε (ε–lân cận) của một đối tượng được gọi là ε– láng giềng của đối tượng đó. Trích dẫn: 'Thuật toán DBSCAN (Density – based Spatial Clustering of Applications with Noise) nhóm các vùng có mật độ đủ cao vào trong một cụm và phát triển dự trên các đối tượng lõi để có các cụm với hình dạng tự nhiên trong các tập không gian đặc trưng'.
4.2. Ứng Dụng của DBSCAN trong Phát Hiện Cụm Dữ Liệu
Đối tượng có ít nhất là MinPts đối tượng khác là ε–láng giềng thì được gọi là đối tượng nhân. Một đối tượng có thể nằm trong một cụm khi và chỉ khi nó nằm trong ε –lân cận của một đối tượng nhân thuộc cụm đó. Hai cụm có giao khá rỗng thì nhập thành một cụm. Một đối tượng không là nhân và không là ε–láng giềng của một đối tượng nhân nào thì được xem là phần tử ngoài lai hay là đối tượng nhiễu. Trích dẫn: 'Một đối tượng có thể nằm trong một cụm khi và chỉ khi nó nằm trong ε –lân cận của một đối tượng nhân thuộc cụm đó'.
