Luận văn thạc sĩ Trần Quang Hào: Phân cụm dữ liệu dựa trên đồ thị sử dụng cây khung cực tiểu

Luận văn thạc sĩ VNU UET nghiên cứu phân cụm dữ liệu dựa trên đồ thị với phương pháp cây khung cự tiểu, mang lại hiệu quả cao trong phân tích dữ liệu.

• Tác giả: Trần Quang Hào
• Người hướng dẫn: PGS. Hoàng Xuân Huấn
• Trường học: Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Phân Cụm Dữ Liệu Dựa Trên Đồ Thị Sử Dụng Cây Khung Cực Tiểu
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2014
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
• DANH MỤC HÌNH VẼ
• LỜI MỞ ĐẦU
• 1. CHƯƠNG 1: GIỚI THIỆU VỀ KHÁM PHÁ TRI THỨC VÀ PHÂN CỤM DỮ LIỆU
• 1.1. Khám phá tri thức
• 1.2. Vai trò và các mục tiêu chính của KDD
• 1.3. Khái niệm phân cụm dữ liệu
• 1.4. Các ứng dụng của phân cụm
• 1.5. Một số phương pháp phân cụm điển hình
• 1.5.1. Phương pháp phân cụm phân hoạch
• 1.5.2. Phương pháp phân cụm phân cấp
• 1.5.3. Phương pháp phân cụm dựa trên mật độ
• 1.5.4. Phương pháp phân cụm dựa trên lưới
• 1.6. Một số vấn đề liên quan đến phân cụm
• 2. CHƯƠNG 2: THUẬT TOÁN PHÂN CỤM SỬ DỤNG CÂY KHUNG CỰC TIỂU
• 2.1. Cây khung cực tiểu
• 2.1.1. Định nghĩa cây khung cực tiểu
• 2.1.2. Thuật toán xây dựng cây khung cực tiểu
• 2.5. Một số khái niệm cần dùng
• 2.5.1. Cụm được mô tả bởi Zahn và Handl
• 2.5.2. Thiết lập toán phân cụm ngẫu nhiên
• 2.5.3. Độ phức tạp của thuật toán 2-MSTs
• 3. CHƯƠNG 3: THỰC NGHIỆM ỨNG DỤNG
• 3.1. Chương trình và kết quả thử nghiệm
• 3.1.1. Chương trình
• 3.2. Kết quả thử nghiệm
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Giới thiệu về luận văn thạc sĩ VNU UET phân cụm dữ liệu

Luận văn thạc sĩ VNU UET của Trần Quang Hào tập trung vào việc phân cụm dữ liệu dựa trên đồ thị sử dụng cây khung cực tiểu. Phân cụm dữ liệu là một trong những vấn đề quan trọng trong lĩnh vực khai phá dữ liệu, giúp tổ chức và phân tích thông tin hiệu quả hơn. Luận văn này không chỉ trình bày lý thuyết mà còn áp dụng thực tiễn để giải quyết các bài toán cụ thể trong lĩnh vực công nghệ thông tin.

1.1. Khái niệm phân cụm dữ liệu và tầm quan trọng

Phân cụm dữ liệu là quá trình chia một tập dữ liệu thành các nhóm sao cho các phần tử trong cùng một nhóm có sự tương đồng cao. Điều này giúp dễ dàng hơn trong việc phân tích và xử lý thông tin. Các ứng dụng của phân cụm rất đa dạng, từ phân tích thị trường đến nhận diện mẫu trong sinh học.

1.2. Cây khung cực tiểu trong phân cụm dữ liệu

Cây khung cực tiểu là một cấu trúc đồ thị quan trọng trong việc phân cụm dữ liệu. Nó giúp xác định các mối quan hệ giữa các điểm dữ liệu, từ đó tạo ra các cụm có tính chất tương đồng cao. Việc sử dụng cây khung cực tiểu trong phân cụm giúp tối ưu hóa quá trình phân tích và giảm thiểu độ phức tạp tính toán.

II. Vấn đề và thách thức trong phân cụm dữ liệu

Mặc dù phân cụm dữ liệu mang lại nhiều lợi ích, nhưng vẫn tồn tại nhiều thách thức trong quá trình thực hiện. Một trong những vấn đề lớn nhất là xác định số lượng cụm cần thiết trước khi thực hiện phân cụm. Điều này có thể dẫn đến kết quả không chính xác nếu số lượng cụm được chọn không phù hợp với dữ liệu.

2.1. Khó khăn trong việc xác định số lượng cụm

Việc xác định số lượng cụm là một thách thức lớn trong phân cụm dữ liệu. Nếu số lượng cụm quá ít, thông tin quan trọng có thể bị bỏ sót. Ngược lại, nếu số lượng cụm quá nhiều, có thể dẫn đến việc phân tán thông tin và khó khăn trong việc phân tích.

2.2. Ảnh hưởng của dữ liệu nhiễu đến kết quả phân cụm

Dữ liệu nhiễu có thể làm giảm độ chính xác của các thuật toán phân cụm. Việc xử lý dữ liệu nhiễu trước khi thực hiện phân cụm là rất quan trọng để đảm bảo kết quả phân tích chính xác và đáng tin cậy.

III. Phương pháp phân cụm dữ liệu sử dụng cây khung cực tiểu

Luận văn trình bày phương pháp phân cụm dữ liệu dựa trên cây khung cực tiểu, một kỹ thuật hiệu quả trong việc tổ chức và phân tích dữ liệu. Phương pháp này không chỉ giúp xác định các cụm mà còn tối ưu hóa quá trình tính toán.

3.1. Thuật toán 2 MSTs trong phân cụm

Thuật toán 2-MSTs là một trong những thuật toán chính được sử dụng trong luận văn. Thuật toán này giúp xây dựng cây khung cực tiểu từ dữ liệu đầu vào, từ đó xác định các cụm dữ liệu một cách hiệu quả.

3.2. Ưu điểm của phương pháp cây khung cực tiểu

Phương pháp cây khung cực tiểu có nhiều ưu điểm, bao gồm khả năng xử lý dữ liệu lớn và độ chính xác cao trong việc xác định các cụm. Điều này giúp cải thiện hiệu quả của các ứng dụng trong lĩnh vực công nghệ thông tin.

IV. Ứng dụng thực tiễn của phân cụm dữ liệu

Phân cụm dữ liệu có nhiều ứng dụng thực tiễn trong các lĩnh vực khác nhau như thương mại, sinh học, và phân tích dữ liệu không gian. Các ứng dụng này cho thấy tầm quan trọng của việc phân tích dữ liệu trong việc ra quyết định.

4.1. Ứng dụng trong thương mại

Trong thương mại, phân cụm dữ liệu giúp các doanh nghiệp xác định các nhóm khách hàng tiềm năng, từ đó tối ưu hóa chiến lược marketing và tăng cường hiệu quả kinh doanh.

4.2. Ứng dụng trong sinh học

Phân cụm dữ liệu cũng được sử dụng trong sinh học để phân loại các loài sinh vật và phân tích các mẫu gen. Điều này giúp các nhà nghiên cứu hiểu rõ hơn về sự đa dạng sinh học và các mối quan hệ giữa các loài.

V. Kết luận và tương lai của phân cụm dữ liệu

Luận văn thạc sĩ VNU UET đã trình bày một cách chi tiết về phương pháp phân cụm dữ liệu dựa trên cây khung cực tiểu. Kết quả nghiên cứu cho thấy phương pháp này có tiềm năng lớn trong việc cải thiện hiệu quả phân tích dữ liệu. Tương lai của phân cụm dữ liệu hứa hẹn sẽ có nhiều tiến bộ mới, đặc biệt trong bối cảnh dữ liệu ngày càng lớn và phức tạp.

5.1. Tiềm năng phát triển của phương pháp phân cụm

Phương pháp phân cụm dữ liệu dựa trên cây khung cực tiểu có tiềm năng phát triển mạnh mẽ trong tương lai. Các nghiên cứu tiếp theo có thể tập trung vào việc cải thiện độ chính xác và hiệu quả của các thuật toán phân cụm.

5.2. Hướng nghiên cứu tiếp theo trong lĩnh vực phân cụm

Hướng nghiên cứu tiếp theo có thể bao gồm việc áp dụng các kỹ thuật học máy mới vào phân cụm dữ liệu, nhằm nâng cao khả năng phân tích và xử lý thông tin trong các lĩnh vực khác nhau.

Nội dung chính

Tổng quan nghiên cứu

Trong kỷ nguyên bùng nổ công nghệ thông tin, khối lượng dữ liệu số tích lũy tại các tổ chức kinh tế và xã hội tăng trưởng theo cấp số nhân. Tuy nhiên, theo các phân tích khoa học dữ liệu, chỉ có khoảng 5% đến 10% lượng dữ liệu thu thập được đưa vào phân tích thực tế, phần lớn còn lại bị bỏ sót do hạn chế của các công cụ xử lý truyền thống. Khám phá tri thức trong cơ sở dữ liệu (KDD) và phân cụm dữ liệu là giải pháp then chốt để giải quyết bài toán này. Khác với các bài toán học có giám sát, phân cụm dữ liệu vận hành theo cơ chế học không giám sát nhằm tự động nhận diện cấu trúc tự nhiên bên trong tập mẫu mà không cần gắn nhãn từ trước.

Hạn chế lớn nhất của phần lớn thuật toán kinh điển như K-Means là yêu cầu người dùng phải xác định trước số lượng cụm $k$. Việc ấn định tham số $k$ mang tính chủ quan, dẫn đến sai lệch lớn khi tập dữ liệu có hình dạng phức tạp hoặc mật độ không đồng đều. Đề tài luận văn thạc sĩ kỹ thuật phần mềm tập trung nghiên cứu, phát triển và thử nghiệm thuật toán phân cụm dữ liệu dựa trên đồ thị sử dụng cây khung cực tiểu hai vòng (2-MSTs).

Nghiên cứu được triển khai thực nghiệm trên dữ liệu vận hành bay thực tế của Tổng công ty Hàng không Việt Nam với 21 đối tượng và 10 thuộc tính đặc trưng, song song với tập kiểm thử gồm 11 bản ghi nhân tạo. Giải pháp đề xuất giúp tự động xác định 4 cụm dữ liệu riêng biệt mà không cần chỉ định số cụm trước, đạt độ phức tạp thuật toán tối ưu $O(N^2)$, mở ra hướng ứng dụng hiệu quả trong việc tối ưu hóa kế hoạch bay và kiểm soát rủi ro vận tả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 quy trình khám phá tri thức gồm 5 giai đoạn chuẩn mực: lựa chọn dữ liệu, tiền xử lý, đổi dạng, khai phá dữ liệu và biểu diễn tri thức. Trọng tâm lý thuyết của luận văn là sự kết hợp giữa lý thuyết đồ thị và học máy không giám sát thông qua cấu trúc cây khung cực tiểu (Minimum Spanning Tree - MST).

Mô hình 2-MSTs mở rộng khái niệm cây khung truyền thống bằng cách xây dựng hai cây khung kế tiếp: cây thứ nhất $T_1 = f_{mst}(V, E)$ và cây thứ hai $T_2 = f_{mst}(V, E \setminus T_1)$ trên phần đồ thị còn lại. Đồ thị hợp nhất $G_{mst}(X) = (V, T_1 + T_2)$ sở hữu các đặc tính toán học vượt trội, cho phép phân tách các cụm dữ liệu rời và cụm tự tách ranh giới rõ ràng. Ba khái niệm nền tảng được chuẩn hóa gồm:

• Cụm tách tốt: tập hợp các điểm có khoảng cách nội cụm nhỏ hơn khoảng cách tới mọi điểm ngoại cụm.
• Cụm compact: tập hợp điểm mà khoảng cách tới tâm diện luôn nhỏ hơn khoảng cách tới tâm diện của cụm khác.
• Cụm kết nối: cấu trúc điểm mà mỗi phần tử luôn có ít nhất một láng giềng gần hơn khoảng cách tới tập ngoài.

Hệ thống sử dụng lý thuyết Entropy và độ tăng thông tin (Information Gain) để xác định thuộc tính phân nhánh tối ưu, kết hợp hàm khoảng cách đa dạng như Euclidean, Manhattan và hệ số tương đồng Jaccard cho dữ liệu hỗn hợp.

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

Nghiên cứu sử dụng nguồn dữ liệu thứ cấp từ kế hoạch khai thác bay của Tổng công ty Hàng không Việt Nam gồm 21 chuyến bay đại diện và bộ dữ liệu đối chứng gồm 11 bản ghi nhân tạo. Phương pháp chọn mẫu có chủ đích được áp dụng nhằm tập trung vào 7 thuộc tính định lượng then chốt gồm số chuyến bay kế hoạch, số chuyến bay hủy, số lần thay đổi lịch bay và các chỉ số thời gian vận hành.

Lý do lựa chọn phương pháp phân tích 2-MSTs bắt nguồn từ khả năng khắc phục hiện tượng liên kết chuỗi (chaining effect) của cây khung đơn và tính nhạy cảm với hình dạng cụm cầu của K-Means. Quy trình phân tích gồm hai thuật toán chính: Thuật toán 1 nhận dạng tách cụm bằng vết cắt hợp lệ dựa trên ngưỡng tỷ lệ cạnh $\alpha$, và Thuật toán 2 thực hiện gom cụm tự động bằng cách so sánh danh sách phân vùng đã lọc $RPT_1$ và $RPT_2$.

Toàn bộ thuật toán được lập trình thử nghiệm trên nền tảng ASP.NET với môi trường Visual Studio 2010 trong giai đoạn hoàn thành luận văn vào tháng 12 năm 2014, đảm bảo khả năng tính toán thời gian thực trên đồ thị đầy đủ.

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

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

Quá trình thực nghiệm thuật toán 2-MSTs trên tập dữ liệu hàng không thực tế và dữ liệu giả lập đã mang lại những phát hiện quan trọng:

Thứ nhất, trên tập dữ liệu thực 21 đối tượng với 7 thuộc tính số, thuật toán tự động phân tách chính xác thành 4 cụm riêng biệt qua 2 bước tính toán Entropy mà không cần tham số số cụm đầu vào. Tại bước 1, thuộc tính $f_{10}$ đạt giá trị Information Gain cao nhất nên được chọn làm điểm chia cụm đầu tiên. Tại bước 2, các thuộc tính $f_{13}$ và $f_{14}$ tiếp tục đạt Gain cực đại để hoàn tất việc phân chia.

Thứ hai, kết quả phân cụm phát hiện ra các quy luật khai thác mang tính quy chuẩn cao. Trong 4 cụm được tạo ra, nhóm các chuyến bay có tỷ lệ hủy chuyến phát sinh hoàn toàn không có sự thay đổi lịch bay (0% thay đổi lịch), ngược lại nhóm có biến động lịch bay ghi nhận 0% tỷ lệ hủy chuyến.

Thứ ba, phân tích phân phối cạnh chỉ ra rằng trong 20 cạnh có trọng số lớn nhất trên đồ thị hai vòng $G_{mst}$, có tới 17 cạnh xuất phát từ cây $T_2$ và 3 cạnh xuất phát từ $T_1$, hoàn toàn phù hợp với Định lý 3 về quan hệ độ dài cạnh liên cụm.

Thứ tư, khi kiểm thử trên tập dữ liệu phi logic gồm 11 bản ghi, thuật toán tuy xuất ra 4 cụm danh nghĩa nhưng thực chất 50% số cụm bị trùng lặp nội dung, chứng minh tính nhạy cảm và cơ chế phản ánh tính chân thực của dữ liệu đầu vào.

Thảo luận kết quả

Cơ chế phân tách của 2-MSTs thành công nhờ tận dụng độ dài cạnh liên cụm lớn hơn đáng kể so với cạnh nội bộ. Khi biểu diễn qua bảng ma trận Gain và cấu trúc vết cắt đồ thị, tỷ số cắt $Ratio(E_{gcut})$ trên tập dữ liệu thực đạt 0,444 (vượt ngưỡng $\alpha$), bảo đảm tính hợp lệ của vết cắt. Ngược lại, tại các cụm không thể tách thêm, tỷ số này giảm xuống còn 0,304, giúp thuật toán tự động dừng mà không làm phân mảnh dữ liệu.

So với phương pháp phân cụm phân cấp truyền thống và DBSCAN, 2-MSTs loại bỏ được sự phụ thuộc vào bán kính lân cận $\varepsilon$ và số điểm tối thiểu $MinPts$. Cấu trúc hai vòng cung cấp bằng chứng kép trước khi quyết định cắt cạnh, ngăn ngừa việc cô lập điểm nhiễu thành cụm rác. Độ phức tạp tính toán tổng thể duy trì ở mức $O(N^2)$, tương đương với thời gian dựng cây của thuật toán Prim trên đồ thị đầy đủ $|E| = |V|^2$, chứng minh tính khả thi cao khi ứng dụng vào các hệ thống quản lý lịch trình thực tế.

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

Nhằm phát huy giá trị ứng dụng của thuật toán phân cụm 2-MSTs, các giải pháp cụ thể được kiến nghị triển khai theo lộ trình:

• Chuẩn hóa quy trình tiền xử lý dữ liệu: Các đơn vị quản lý dữ liệu cần thiết lập cổng chuẩn hóa thuộc tính hỗn hợp, chuyển đổi thuộc tính định danh và thứ tự về thang đo $[0, 1]$, hướng tới mục tiêu đạt trên 95% tính toàn vẹn dữ liệu trong vòng 6 tháng đầu năm.
• Tích hợp động cơ 2-MSTs vào hệ thống điều hành bay: Bộ phận Công nghệ Thông tin tại các hãng hàng không cần đóng gói thuật toán thành mô-đun phân tích độc lập, tự động phân nhóm chuyến bay chậm, hủy hoặc đổi lịch theo thời gian thực với độ trễ phản hồi dưới 2 giây trước quý 4.
• Tối ưu hóa tính toán phân tán cho dữ liệu lớn: Đội ngũ phát triển phần mềm cần nâng cấp cấu trúc dữ liệu sang mô hình hàng đợi Fibonacci và lập trình song song trên nền tảng đám mây, nâng quy mô xử lý lên trên 100.000 bản ghi bay vào năm tiếp theo.
• Đào tạo chuyên gia điều hành khai thác: Trung tâm huấn luyện bay cần tổ chức các khóa chuyển giao công nghệ cho ít nhất 50 cán bộ điều độ và phân tích dữ liệu trong vòng 3 tháng, giúp khai thác hiệu quả các tri thức rút ra từ 4 nhóm đặc trưng bay.

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

• Học viên cao học và nghiên cứu sinh ngành Khoa học Máy tính, Kỹ thuật Phần mềm: Nắm vững phương pháp chứng minh định lý đồ thị 2-MSTs, kỹ thuật cắt cạnh và quy trình tính toán Information Gain trên dữ liệu hỗn hợp.
• Kỹ sư phát triển phần mềm và kiến trúc sư hệ thống: Ứng dụng mã nguồn C# và ASP.NET để xây dựng các công cụ khai phá dữ liệu tự động, thay thế cho các thuật toán phân cụm truyền thống cần tham số $k$.
• Chuyên viên điều hành và phân tích dữ liệu ngành Hàng không: Khai thác các mẫu hình tương quan giữa hủy chuyến và thay đổi lịch bay, từ đó tối ưu biểu đồ khai thác sân bay và giảm chi phí đền bù chậm chuyến.
• Chuyên viên Phân tích nghiệp vụ (BA) và Trí tuệ doanh nghiệp (BI) trong logistics: Vận dụng mô hình phân cụm không giám sát để phân nhóm tuyến vận tải, đội xe và tối ưu hóa chuỗi cung ứng dịch vụ.

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

Thuật toán 2-MSTs có ưu điểm gì vượt trội so với cây khung cực tiểu đơn (Single MST)? Cây khung đơn rất dễ bị lỗi liên kết chuỗi khi hai cụm bị nối bởi một điểm nhiễu duy nhất. Thuật toán 2-MSTs bổ sung vòng cây $T_2$ trên đồ thị $E \setminus T_1$, đòi hỏi vết cắt phải đồng thời loại bỏ ít nhất 2 cạnh từ cả hai cây, tạo ra ranh giới phân tách vững chắc hơn.

Độ phức tạp tính toán $O(N^2)$ của 2-MSTs có phù hợp với hệ thống lớn không? Với kích thước mẫu $N$, việc xây dựng hai vòng cây bằng thuật toán Prim kết hợp hàng đợi Fibonacci chỉ tiêu tốn chi phí $O(N^2)$. Quá trình sắp xếp và lọc phân vùng diễn ra trong $O(N \log N)$, đảm bảo tốc độ phản hồi nhanh chóng trên các tập dữ liệu nghiệp vụ hàng ngàn bản ghi.

Vì sao nghiên cứu lại kết hợp độ đo Entropy trong thuật toán phân cụm đồ thị? Sau khi đồ thị nhận dạng các khả năng tách cụm, chỉ số Entropy và Information Gain đóng vai trò như tiêu chuẩn khách quan để chọn ra thuộc tính có mức độ thuần nhất cao nhất, như việc tìm ra thuộc tính $f_{10}$ và $f_{13}$ trong bài toán hàng không.

Dữ liệu có nhiều kiểu thuộc tính khác nhau được xử lý như thế nào? Luận văn thiết lập metric khoảng cách hỗn hợp, trong đó thuộc tính nhị phân dùng hệ số đối sánh hoặc Jaccard, thuộc tính định danh tính theo tỷ lệ trùng khớp, và thuộc tính số được chuẩn hóa khoảng cách Minkowski hoặc Euclidean với trọng số chuyên gia.

Kết quả thử nghiệm trên tập dữ liệu nhân tạo mang lại bài học gì? Tập dữ liệu nhân tạo 11 bản ghi phi logic dù tạo ra 4 cụm danh nghĩa nhưng thực chất bị trùng lặp thành 2 cụm thực tế. Điều này khẳng định thuật toán phản ánh trung thực chất lượng dữ liệu và đòi hỏi khâu tiền xử lý dữ liệu phải chuẩn xác.

Kết luận

• Luận văn đã hoàn thiện khung lý thuyết phân cụm dữ liệu dựa trên đồ thị sử dụng cấu trúc cây khung cực tiểu hai vòng 2-MSTs.
• Xây dựng thành công thuật toán tự động nhận diện cụm rời và gom cụm mà không cần người dùng xác định trước tham số số lượng cụm $k$.
• Chứng minh tính tối ưu về mặt thuật toán với độ phức tạp $O(N^2)$, kết hợp hiệu quả độ đo Entropy để lựa chọn thuộc tính phân rã tối ưu.
• Thực nghiệm thành công trên dữ liệu khai thác bay thực tế của Tổng công ty Hàng không Việt Nam, trích xuất được 4 cụm tri thức đặc trưng về hủy chuyến và đổi lịch.
• Khẳng định khả năng ứng dụng rộng rãi của mô hình trong công nghệ phần mềm, quản trị vận tải và khai phá dữ liệu lớn trong giai đoạn 12 đến 24 tháng tới.

Các tổ chức và doanh nghiệp đang tìm kiếm giải pháp phân nhóm dữ liệu tự động, chính xác và không phụ thuộc tham số chủ quan nên sớm áp dụng mô hình 2-MSTs vào hạ tầng phân tích thông minh của mình.