Phân cụm dữ liệu: Thuật toán phân cấp

Phần này định nghĩa khai phá dữ liệu (Data Mining) là một lĩnh vực khoa học mới nhằm tự động hóa việc khai thác thông tin và tri thức tiềm ẩn từ các cơ sở dữ liệu (CSDL) lớn. Sự phát triển vượt bậc của công nghệ điện tử và truyền thông dẫn đến khả năng lưu trữ thông tin ngày càng tăng, tạo ra một lượng dữ liệu khổng lồ. John Naisbett đã cảnh báo về tình trạng "chìm ngập trong dữ liệu mà vẫn đói tri thức", nhấn mạnh sự cần thiết của khai phá dữ liệu để chuyển đổi dữ liệu thô thành thông tin hữu ích. Khai phá dữ liệu được xem là có ưu thế hơn hẳn so với các công cụ phân tích dữ liệu truyền thống và mang lại nhiều lợi ích to lớn. Hiện nay, khai phá dữ liệu được ứng dụng rộng rãi trong nhiều lĩnh vực, bao gồm phân tích dữ liệu hỗ trợ ra quyết định, điều trị y học, tin sinh học, thương mại, tài chính, bảo hiểm, text mining và web mining. Quá trình khai phá dữ liệu bao gồm các bước như biến đổi dữ liệu (chuẩn hóa, làm mịn dữ liệu) và áp dụng các kỹ thuật phân tích (thường là các kỹ thuật học máy) để trích lọc các mẫu tin và mối quan hệ đặc biệt trong dữ liệu. Đây là bước quan trọng và tốn nhiều thời gian nhất trong toàn bộ quá trình.

Dựa trên các lớp bài toán cần giải quyết, khai phá dữ liệu bao gồm nhiều kỹ thuật khác nhau. Phân lớp và dự đoán (Classification and prediction), hay còn gọi là học có giám sát, là việc xếp các đối tượng vào các lớp đã biết trước (ví dụ: phân loại bệnh nhân, phân loại loài thực vật). Các kỹ thuật học máy như cây quyết định (decision tree) và mạng nơ-ron nhân tạo (neural network) thường được sử dụng. Một kỹ thuật khác là mô tả khái niệm và tổng hợp (Concept description and summarization), tập trung vào việc mô tả, tổng hợp và tóm tắt các khái niệm (ví dụ: tóm tắt văn bản). Khai phá dữ liệu có thể làm việc với nhiều kiểu dữ liệu khác nhau, bao gồm CSDL giao tác, CSDL quan hệ hướng đối tượng, dữ liệu không gian và thời gian, CSDL đa phương tiện, dữ liệu văn bản và web. Một ứng dụng phổ biến trong các công ty viễn thông là dự đoán khách hàng thay đổi nhà cung cấp dịch vụ (customer churn) bằng cách sử dụng dữ liệu cước, dữ liệu chi tiết cuộc gọi và dữ liệu khách hàng để xây dựng các mô hình dự đoán, ví dụ bằng cây quyết định hay mạng nơ-ron. Các kỹ thuật khai phá dữ liệu cũng được sử dụng trong chiến lược marketing, ví dụ để tìm ra các nhóm thành phố thường xuyên liên lạc với nhau, hỗ trợ hoạch định chiến lược tiếp thị và xây dựng vùng cước phù hợp. Phân loại khách hàng (classifying) dựa trên kỹ thuật học trên cây quyết định cũng là một ứng dụng phổ biến. Cuối cùng, khai phá dữ liệu còn được ứng dụng trong việc phát hiện và cô lập lỗi trên hệ thống mạng viễn thông, giúp quản lý và duy trì độ tin cậy của hệ thống.

Khai phá dữ liệu được đánh giá là một lĩnh vực khoa học tiềm năng, mang lại nhiều lợi ích và có ưu thế hơn hẳn so với các công cụ phân tích dữ liệu truyền thống. Nó giúp giải quyết vấn đề "ngập trong dữ liệu mà vẫn đói tri thức", tự động hóa việc khai thác thông tin và tri thức hữu ích, tiềm ẩn trong các CSDL lớn. Kết quả nghiên cứu và ứng dụng thành công trong khai phá dữ liệu và khám phá tri thức khẳng định tiềm năng và lợi ích to lớn của lĩnh vực này. Khai phá dữ liệu liên quan đến nhiều ngành khoa học như hệ CSDL, thống kê, trực quan hóa và có thể áp dụng nhiều kỹ thuật khác nhau như mạng nơ-ron, phương pháp hệ chuyên gia, lý thuyết tập thô, tập mờ. Những ưu điểm này giúp khai phá dữ liệu trở thành một công cụ không thể thiếu trong việc phân tích dữ liệu hiện đại, hỗ trợ ra quyết định hiệu quả hơn trong nhiều lĩnh vực.

Phân cụm dữ liệu (Data Clustering), một hướng nghiên cứu trọng tâm trong khai phá dữ liệu, nhằm mục đích nhóm các đối tượng vào các cụm sao cho các đối tượng trong cùng một cụm có tính tương đồng cao, và độ bất tương đồng giữa các cụm là lớn. Quá trình này giúp cung cấp thông tin, tri thức hữu ích cho việc ra quyết định. Phân cụm dữ liệu còn được gọi là phân tích cụm, gom cụm, phân tích phân đoạn hay phân tích phân loại. Nó được định nghĩa là kỹ thuật tìm kiếm, phát hiện và nhóm các đối tượng (thực thể hay trừu tượng) thành các lớp đối tượng tương tự nhau trong tập dữ liệu lớn, từ đó cung cấp thông tin, tri thức cho việc ra quyết định. Trong học máy, phân cụm dữ liệu được xem là vấn đề học không giám sát, vì không có thông tin về lớp hay tập ví dụ huấn luyện sẵn. Trong nhiều trường hợp, phân cụm dữ liệu là bước khởi tạo các lớp cho phân lớp có giám sát, bằng cách xác định các nhãn cho các nhóm dữ liệu. Một vấn đề thường gặp là dữ liệu nhiễu (noise) do quá trình thu thập không chính xác hoặc thiếu đầy đủ, cần phải có bước tiền xử lý dữ liệu để khắc phục. Trong phân cụm dữ liệu khái niệm (Concept Clustering), các đối tượng được xếp vào cùng một cụm nếu chúng có chung định nghĩa về khái niệm hoặc xấp xỉ với các khái niệm mô tả cho trước, khác với khái niệm "tương tự" dựa trên độ đo khoảng cách.

Có nhiều phương pháp phân cụm khác nhau, tùy thuộc vào kiểu dữ liệu, mục tiêu và ứng dụng. Phương pháp phân cụm dựa trên mật độ xác định các cụm dựa trên mật độ điểm dữ liệu, có thể phát hiện các cụm với hình thù bất kỳ, nhưng việc xác định tham số mật độ rất khó khăn. Các thuật toán điển hình bao gồm DBSCAN, OPTICS, DENCLUE. Đối với dữ liệu nhiều chiều, phương pháp phân cụm dựa trên lưới được sử dụng. Phương pháp này dựa trên cấu trúc dữ liệu lưới, lượng hóa dữ liệu thành các ô (cell), thực hiện phân cụm trên các ô này. Thời gian xử lý nhanh và độc lập với số lượng đối tượng, nhưng phụ thuộc vào số cell trong mỗi chiều của không gian lưới. Phương pháp dựa trên mô hình cố gắng khớp dữ liệu với mô hình toán học, giả định dữ liệu được tạo ra từ hỗn hợp các phân phối xác suất cơ bản. Hai tiếp cận chính là mô hình thống kê và mạng nơ-ron. Phương pháp này tương tự phương pháp dựa trên mật độ, nhưng đôi khi không bắt đầu với số cụm cố định và không sử dụng khái niệm mật độ. Phân cụm dữ liệu có ràng buộc nhằm cải thiện hiệu quả phân cụm không gian trên CSDL lớn bằng cách kết hợp các ràng buộc thực tế. Các nhánh nghiên cứu khác bao gồm phân cụm thống kê (dựa trên độ đo tương tự, áp dụng cho dữ liệu số) và phương pháp dựa trên mô hình (gom cụm khái niệm, mạng neural). Hầu hết các kỹ thuật chỉ áp dụng cho tập dữ liệu cùng một kiểu thuộc tính, nên phân cụm dữ liệu trên tập dữ liệu kiểu hỗn hợp là một vấn đề đặt ra.

Hầu hết dữ liệu cần cho phân cụm đều chứa dữ liệu nhiễu (noise) do quá trình thu thập không chính xác hoặc thiếu đầy đủ. Cần xây dựng chiến lược tiền xử lý dữ liệu để khắc phục hoặc loại bỏ nhiễu, ví dụ bằng cách thay thế giá trị thuộc tính của đối tượng nhiễu. Dữ liệu ngoại lai (outlier data) là những dữ liệu bất thường, có thể làm sai lệch kết quả phân cụm. Vì vậy, cần loại bỏ dữ liệu ngoại lai trước khi phân cụm. Việc xác định và xử lý dữ liệu nhiễu và dữ liệu ngoại lai là rất quan trọng để đảm bảo chất lượng và độ tin cậy của kết quả phân cụm. Chọn phương pháp đo độ tương tự thích hợp cho từng loại thuộc tính (định danh, rời rạc, nhị phân, khoảng, tỉ lệ) cũng đóng vai trò quan trọng trong việc đảm bảo tính chính xác của kết quả phân cụm. Chuẩn hóa dữ liệu, loại bỏ đơn vị đo hoặc gán trọng số cho các thuộc tính cũng là các kỹ thuật cần thiết để xử lý dữ liệu trước khi phân cụm.

Thuật toán BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies) là một thuật toán phân cụm phân cấp hiệu quả cho tập dữ liệu lớn, sử dụng chiến lược top-down. Ý tưởng chính là không lưu trữ toàn bộ đối tượng dữ liệu trong bộ nhớ mà chỉ lưu các đại lượng thống kê, cụ thể là bộ ba (n, LS, SS) - đặc trưng của cụm (Cluster Features - CF). Thuật toán xây dựng cây CF, chèn đối tượng vào nút lá gần nhất và cập nhật thông tin các nút. Nếu đường kính cụm con vượt quá ngưỡng T, nút lá được tách. Nếu bộ nhớ không đủ, cây CF nhỏ hơn được xây dựng lại mà không cần đọc lại dữ liệu từ đầu. Tuy nhiên, BIRCH có những hạn chế: không xử lý tốt các cụm không có hình dạng cầu (vì dùng khái niệm bán kính/đường kính), hoạt động tốt với dữ liệu số (nếu dùng khoảng cách Euclidean), tham số T ảnh hưởng lớn đến kích thước và tính tự nhiên của cụm, và không thích hợp với dữ liệu đa chiều. Độ phức tạp của BIRCH là O(n), duyệt dữ liệu một lần, hiệu quả với dữ liệu tăng trưởng theo thời gian. Tuy nhiên, mỗi nút trong cây CF chỉ lưu trữ một số hữu hạn đối tượng.

Thuật toán CURE (Clustering Using Representatives) sử dụng nhiều hơn một phần tử đại diện cho các cụm, cho phép khám phá các cụm có hình thù và kích thước khác nhau. Việc co các đối tượng đại diện lại giúp giảm tác động của các phần tử ngoại lai. Để xử lý CSDL lớn, CURE sử dụng phương pháp ngẫu nhiên và phân hoạch: một mẫu được chọn ngẫu nhiên, phân cụm trên mỗi phân hoạch, và các cụm thu được được phân cụm lại lần hai. Tuy nhiên, mẫu ngẫu nhiên không đảm bảo mô tả tốt toàn bộ tập dữ liệu. Độ phức tạp tính toán của CURE là O(n^2 log(n)), độ phức tạp không gian là O(n) nhờ sử dụng kd-tree và heap. CURE tin cậy trong việc khám phá các cụm bất kỳ, xử lý tốt dữ liệu ngoại lai và dữ liệu hai chiều, nhưng rất nhạy cảm với các tham số như số đối tượng đại diện và tỉ lệ co.

Cả BIRCH và CURE đều là các thuật toán phân cụm phân cấp được sử dụng để xử lý dữ liệu lớn. BIRCH có ưu điểm về tốc độ (O(n)) và khả năng xử lý dữ liệu tăng trưởng theo thời gian nhờ cấu trúc cây CF. Tuy nhiên, nó có những hạn chế về hình dạng cụm và loại dữ liệu. CURE xử lý tốt hơn các cụm có hình dạng phức tạp và dữ liệu ngoại lai, nhưng có độ phức tạp tính toán cao hơn (O(n^2 log(n))). Sự lựa chọn giữa hai thuật toán phụ thuộc vào đặc điểm của dữ liệu và yêu cầu về tốc độ và độ chính xác của kết quả. Bài toán phân cụm dữ liệu, đặc biệt là với dữ liệu lớn, đòi hỏi sự lựa chọn thuật toán phù hợp để đảm bảo chất lượng kết quả cũng như hiệu quả tính toán.

Phân cụm dữ liệu là một nhiệm vụ quan trọng trong khai phá dữ liệu, thu hút sự quan tâm của nhiều nhà nghiên cứu và được ứng dụng thành công trong nhiều lĩnh vực khoa học và đời sống xã hội. Sự phát triển không ngừng của công nghệ thông tin và truyền thông dẫn đến sự gia tăng nhanh chóng về số lượng và đa dạng của các hệ thống cơ sở dữ liệu (CSDL). Nhu cầu khai thác tri thức từ các CSDL này ngày càng lớn, đòi hỏi việc nghiên cứu các mô hình dữ liệu mới và áp dụng các phương pháp khai phá dữ liệu hiệu quả, trong đó có kỹ thuật phân cụm dữ liệu. Vì vậy, việc nghiên cứu kỹ thuật phân cụm dữ liệu là rất cần thiết và có ý nghĩa thiết thực.

Đồ án đã trình bày về bài toán phân cụm dữ liệu, các cách tiếp cận, ứng dụng, các kiểu dữ liệu có thể phân cụm và các độ đo độ tương tự. Đặc biệt, đồ án tập trung nghiên cứu kỹ thuật phân cụm dữ liệu phân cấp và hai thuật toán điển hình là BIRCH và CURE. Đối với mỗi thuật toán, đồ án đã trình bày cách thức tổ chức dữ liệu, thuật toán cụ thể, và đánh giá ưu, nhược điểm của từng thuật toán. Việc nghiên cứu sâu về hai thuật toán này nhằm mục đích hiểu rõ hơn về hiệu quả và khả năng ứng dụng của chúng trong việc giải quyết bài toán phân cụm dữ liệu, đặc biệt trong các trường hợp xử lý dữ liệu lớn.

Các kỹ thuật phân cụm, bao gồm cả phân cụm phân cấp, đã và đang được ứng dụng thành công trong nhiều lĩnh vực. Sự phát triển không ngừng của công nghệ thông tin và truyền thông dẫn đến sự gia tăng nhanh chóng về lượng và chất lượng dữ liệu, làm tăng nhu cầu khai thác tri thức từ các CSDL. Do đó, việc nghiên cứu các mô hình dữ liệu mới và áp dụng các phương pháp khai phá dữ liệu, trong đó có kỹ thuật phân cụm dữ liệu, là rất cần thiết và có ý nghĩa. Việc lựa chọn thuật toán phân cụm phù hợp (như BIRCH hay CURE) phụ thuộc vào đặc điểm của dữ liệu và yêu cầu về tốc độ và độ chính xác. Hiểu rõ ưu nhược điểm của từng thuật toán là điều cần thiết để áp dụng hiệu quả trong thực tế.