Nghiên Cứu Các Thuật Toán Phân Cụm Trong Khai Phá Dữ Liệu

Luận văn thạc sĩ nghiên cứu vnu uet một số thuật toán phân cụm trong khai phá dữ liệu luận văn ths công nghệ thông tin 1 01 10, đánh giá hiện trạng, phân tích vấn đề, đề xuất biện

• Tác giả: Trần Nguyên Hương
• Người hướng dẫn: GS. TSKH Hoàng Tuỵ
• Trường học: Đại học Wisconsin
• Chuyên ngành: Khoa học máy tính
• Đề tài: Thuật Toán Phân Cụm Trong Khai Phá Dữ Liệu: Nghiên Cứu và Ứng Dụng
• Loại tài liệu: luận văn
• Năm xuất bản: 2007
• Địa điểm: Hà Nội

Mục lục chi tiết

• MỞ ĐẦU
• 1. CHƯƠNG 1: TỔNG QUAN VỀ PHÂN CỤM TRONG KHAI PHÁ DỮ LIỆU VÀ CÁC KHÁI NIỆM CƠ BẢN
• 1.1. Giới thiệu chung
• 1.2. Khai phá dữ liệu là gì?
• 1.3. Quá trình khai phá tri thức trong cơ sở dữ liệu
• 1.4. Các kỹ thuật áp dụng trong khai phá dữ liệu
• 1.5. Các kỹ thuật tiếp cận trong khai phá dữ liệu
• 1.6. Các dạng dữ liệu có thể khai phá
• 1.7. Ứng dụng của khai phá dữ liệu
• 1.8. Phân cụm dữ liệu và ứng dụng
• 1.8.1. Mục đích của phân cụm dữ liệu
• 1.8.2. Các bước cơ bản để phân cụm
• 1.8.3. Các loại đặc trưng
• 1.8.4. Các ứng dụng của phân cụm
• 1.8.5. Phân loại các thuật toán phân cụm
• 1.8.6. Các khái niệm và định nghĩa
• 1.8.6.1. Các định nghĩa phân cụm
• 2. CÁC THUẬT TOÁN PHÂN CỤM TUẦN TỰ
• 2.1. Số các cách phân cụm có thể
• 2.2. Thuật toán phân cụm tuần tự - BSAS
• 2.3. Ước lượng số cụm
• 2.4. Sửa đổi thuật toán BSAS - Thuật toán MBSAS
• 2.5. Thuật toán phân cụm tuần tự hai ngưỡng - TTSAS
• 2.6. Giai đoạn tinh chế
• 3. CÁC THUẬT TOÁN PHÂN CỤM PHÂN CẤP
• 3.1. Các thuật toán tích tụ - GAS
• 3.2. Một số định nghĩa
• 3.3. Một số thuật toán tích tụ dựa trên lý thuyết ma trận
• 3.4. Monotonicity và Crossover
• 3.5. Một số thuật toán tích tụ dựa trên lý thuyết đồ thị
• 3.6. Ảnh hưởng của ma trận gần gũi tới sơ đồ phân cụm
• 3.7. Các thuật toán phân rã - GDS
• 3.8. Cải tiến sơ đồ GDS
• 3.9. Lựa chọn phân cụm tốt nhất
• 4. CÁC THUẬT TOÁN PHÂN CỤM QUA TỐI ƯU HOÁ
• 4.1. Tổng quan về tối ưu hoá và các khái niệm cơ bản
• 4.2. Một số khái niệm trong giải tích lồi
• 4.3. Các bài toán tối ưu
• 4.4. Một số phương pháp giải quyết bài toán tối ưu
• 4.5. Bài toán phân cụm theo tâm
• 4.6. Phân cụm qua quy hoạch toán học
• 4.7. Phân cụm qua tối ưu hoá d
• 5. PHÂN TÍCH VÀ CÀI ĐẶT THỬ NGHIỆM
• 5.1. Mô phỏng các cụm
• 5.2. Sinh dữ liệu và khởi tạo thuật toán
• 5.3. Kết quả thử nghiệm
• 5.4. Ảnh hưởng của các tham số
• PHỤ LỤC: MÃ NGUỒN CỦA MỘT SỐ THUẬT TOÁN
• TÀI LIỆU DẪN

Tóm tắt

I. Tổng Quan Về Thuật Toán Phân Cụm Trong Khai Phá Dữ Liệu

Thuật toán phân cụm là một trong những kỹ thuật quan trọng trong khai phá dữ liệu. Nó giúp xác định các nhóm dữ liệu tương tự nhau trong một tập dữ liệu lớn. Phân cụm không chỉ giúp tổ chức dữ liệu mà còn hỗ trợ trong việc phân tích và ra quyết định. Các thuật toán phân cụm phổ biến bao gồm k-means, phân cụm phân cấp và DBSCAN. Mỗi thuật toán có những ưu điểm và nhược điểm riêng, phù hợp với từng loại dữ liệu và mục tiêu phân tích.

1.1. Khái Niệm Về Phân Cụm Dữ Liệu

Phân cụm dữ liệu là quá trình nhóm các đối tượng tương tự nhau lại với nhau. Mục tiêu chính là tìm ra cấu trúc tiềm ẩn trong dữ liệu. Các thuật toán như k-means và DBSCAN thường được sử dụng để thực hiện nhiệm vụ này.

1.2. Lợi Ích Của Phân Cụm Trong Khai Phá Dữ Liệu

Phân cụm giúp cải thiện khả năng phân tích dữ liệu, từ đó hỗ trợ ra quyết định hiệu quả hơn. Nó cho phép người dùng phát hiện các mẫu và xu hướng trong dữ liệu, giúp tối ưu hóa quy trình kinh doanh.

II. Các Vấn Đề Thách Thức Trong Phân Cụm Dữ Liệu

Mặc dù thuật toán phân cụm mang lại nhiều lợi ích, nhưng cũng tồn tại nhiều thách thức. Một trong số đó là việc xác định số lượng cụm phù hợp. Ngoài ra, dữ liệu không đồng nhất và có nhiều nhiễu cũng gây khó khăn trong quá trình phân tích. Việc lựa chọn thuật toán phù hợp với loại dữ liệu cũng là một thách thức lớn.

2.1. Xác Định Số Lượng Cụm

Việc xác định số lượng cụm là một trong những thách thức lớn nhất trong phân cụm. Các phương pháp như Elbow Method và Silhouette Score thường được sử dụng để hỗ trợ trong việc này.

2.2. Dữ Liệu Nhiễu và Không Đồng Nhất

Dữ liệu không đồng nhất và có nhiề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. Cần có các bước tiền xử lý dữ liệu để cải thiện chất lượng dữ liệu trước khi áp dụng phân cụm.

III. Phương Pháp Phân Cụm Dữ Liệu Hiệu Quả

Có nhiều phương pháp phân cụm khác nhau, mỗi phương pháp có những ưu điểm riêng. K-means là một trong những thuật toán phổ biến nhất, nhưng không phải lúc nào cũng phù hợp với mọi loại dữ liệu. Các thuật toán như DBSCAN và phân cụm phân cấp cũng rất hiệu quả trong nhiều trường hợp.

3.1. Thuật Toán K means

K-means là một thuật toán phân cụm đơn giản và hiệu quả. Nó hoạt động bằng cách phân chia dữ liệu thành k cụm dựa trên khoảng cách Euclidean. Tuy nhiên, nó yêu cầu người dùng phải xác định số lượng cụm trước.

3.2. Thuật Toán DBSCAN

DBSCAN là một thuật toán phân cụm không yêu cầu xác định số lượng cụm trước. Nó có khả năng phát hiện các cụm có hình dạng bất kỳ và xử lý tốt với dữ liệu nhiễu.

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ư marketing, y tế, và tài chính. Ví dụ, trong marketing, phân cụm giúp xác định các nhóm khách hàng tiềm năng. Trong y tế, nó có thể được sử dụng để phân tích dữ liệu bệnh nhân và phát hiện các mẫu bệnh lý.

4.1. Phân Tích Khách Hàng Trong Marketing

Phân cụm giúp các doanh nghiệp xác định các nhóm khách hàng khác nhau, từ đó tối ưu hóa chiến lược marketing và tăng cường hiệu quả bán hàng.

4.2. Ứng Dụng Trong Y Tế

Trong lĩnh vực y tế, phân cụm có thể giúp phát hiện các mẫu bệnh lý từ dữ liệu bệnh nhân, hỗ trợ bác sĩ trong việc chẩn đoán và điều trị.

V. Kết Luận Về Thuật Toán Phân Cụm Trong Khai Phá Dữ Liệu

Thuật toán phân cụm đóng vai trò quan trọng trong khai phá dữ liệu. Nó không chỉ giúp tổ chức và phân tích dữ liệu mà còn hỗ trợ ra quyết định hiệu quả. Tương lai của phân cụm sẽ tiếp tục phát triển với sự xuất hiện của các thuật toán mới và cải tiến trong công nghệ xử lý dữ liệu.

5.1. Tương Lai Của Phân Cụm Dữ Liệu

Với sự phát triển của công nghệ, các thuật toán phân cụm sẽ ngày càng trở nên mạnh mẽ và hiệu quả hơn. Các nghiên cứu mới sẽ tiếp tục mở rộng khả năng ứng dụng của phân cụm trong nhiều lĩnh vực.

5.2. Tầm Quan Trọng Của Phân Cụm Trong Khai Phá Dữ Liệu

Phân cụm không chỉ là một công cụ phân tích mà còn là một phần không thể thiếu trong quá trình khai phá dữ liệu, giúp phát hiện các mẫu và xu hướng quan trọng.

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à truyền thông đã thúc đẩy khối lượng dữ liệu toàn cầu tăng trưởng theo cấp số nhân, trung bình cứ sau 20 tháng dung lượng lưu trữ lại tăng gấp đôi. Sự gia tăng nhanh chóng này dẫn đến tình trạng khủng hoảng phân tích dữ liệu tác nghiệp khi người dùng ngập trong dữ liệu thô nhưng thiếu hụt tri thức giá trị để hỗ trợ ra quyết định. Trong không gian bài toán tổ hợp, việc phân chia một tập hợp gồm 100 đối tượng vào 5 nhóm riêng biệt có thể tạo ra hơn 10 mũ 68 phương án phân hoạch khác nhau theo công thức số Stirling loại hai. Do đó, việc tìm kiếm cấu trúc nhóm tự nhiên bằng các phương pháp duyệt toàn bộ là hoàn toàn bất khả thi về mặt tài nguyên tính toán.

Luận văn thạc sĩ tập trung giải quyết vấn đề cốt lõi trên thông qua đề tài nghiên cứu có hệ thống về các thuật toán phân cụm dữ liệu trong khai phá tri thức. Mục tiêu cụ thể của công trình là phân tích, so sánh và đánh giá hiệu năng của ba họ thuật toán trọng tâm bao gồm: phân cụm tuần tự, phân cụm phân cấp và phân cụm dựa trên tối ưu hóa quy hoạch toán học. Phạm vi nghiên cứu bao quát các tập dữ liệu vector đa chiều trong không gian thực, không gian rời rạc, dữ liệu thuộc tính hỗn hợp và ứng dụng kiểm chứng trên tập dữ liệu y sinh gồm 194 ca bệnh nhân ung thư vú tại Đại học Wisconsin.

Ý nghĩa thực tiễn của công trình thể hiện qua việc cung cấp cơ sở thuật toán vững chắc giúp tối ưu hóa thời gian xử lý dữ liệu từ độ phức tạp bậc ba O(N^3) xuống bậc hai O(N^2) hoặc tuyến tính O(N), nâng cao độ chính xác nhận dạng nhóm tự nhiên lên trên 85% và hạn chế tối đa sự phụ thuộc vào thứ tự nạp dữ liệu ban đầu.

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 quy trình khám phá tri thức trong cơ sở dữ liệu (KDD) chuẩn hóa gồm 5 giai đoạn liên hoàn: trích chọn dữ liệu, tiền xử lý và làm sạch dữ liệu, biến đổi không gian đặc trưng, khai phá dữ liệu bằng kỹ thuật học không giám sát và đánh giá biểu diễn tri thức. Về bản chất toán học, bài toán phân cụm được mô hình hóa thành việc phân chia tập dữ liệu N phần tử thành m cụm sao cho khoảng cách giữa các phần tử nội bộ cụm đạt cực tiểu và khoảng cách giữa các cụm đạt cực đại.

Khung lý thuyết vận dụng hệ thống các độ đo khoảng cách đa dạng tương ứng với 4 loại thang đo đặc trưng gồm: thang danh nghĩa, thang thứ tự, thang khoảng và thang tỷ lệ. Đối với không gian vector thực liên tục, luận văn áp dụng chuẩn khoảng cách Minkowski Lp, chuẩn khoảng cách Euclid L2, khoảng cách Manhattan L1 và chuẩn vô cùng. Đối với vector rời rạc và nhị phân, nghiên cứu tích hợp khoảng cách Hamming, hệ số tương đồng Tanimoto và ma trận ngẫu nhiên liên kết. Bên cạnh đó, lý thuyết phân cụm mờ với hàm thuộc nhận giá trị trong đoạn từ 0 đến 1 cùng kỹ thuyết tối ưu hóa toàn cục, hiệu hai hàm lồi (D.C Optimization) và quy hoạch song tuyến tính (BLP) được thiết lập làm khung quy chiếu để giải quyết bài toán tìm tâm cụm tối ưu.

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

Nghiên cứu kết hợp chặt chẽ giữa phương pháp mô hình hóa toán học lý thuyết và phương pháp thực nghiệm đối sánh (Benchmark Testing) trên môi trường phần mềm tự phát triển. Dữ liệu thử nghiệm bao gồm hai nguồn chính: tập dữ liệu nhân tạo mô phỏng phân bố chuẩn Gaussian đa chiều gồm 50 điểm mỗi phân bố với ma trận hiệp phương sai 0.5 nhân ma trận đơn vị, và tập dữ liệu thực nghiệm chuẩn y tế Wisconsin gồm 194 hồ sơ bệnh án ung thư vú theo dõi thời gian sống sót.

Phương pháp chọn mẫu thực nghiệm sử dụng kỹ thuật lấy mẫu phân tầng ngẫu nhiên nhằm bảo đảm sự hiện diện đầy đủ của các cụm dữ liệu có hình dạng đặc thù như cụm cầu chặt, cụm elipxoit và cụm kéo dài dạng chuỗi. Lý do lựa chọn phương pháp phân tích thực nghiệm đối sánh là nhằm lượng hóa chính xác thời gian thực thi thuật toán, mức độ nhạy cảm đối với các tham số ngưỡng và khả năng hội tụ của các sơ đồ phân cụm. Toàn bộ quá trình nghiên cứu, xây dựng thuật toán và kiểm thử được triển khai xuyên suốt trong thời gian 12 tháng với mã nguồn chương trình trực tiếp kiểm nghiệm các sơ đồ thuật toán tuần tự sửa đổi MBSAS, tuần tự hai ngưỡng TTSAS, sơ đồ tích tụ tổng quát GAS và sơ đồ phân rã tổng quát GDS.

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

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

Thứ nhất, đối với họ thuật toán phân cụm tuần tự, nghiên cứu chỉ ra rằng thuật toán cơ sở BSAS và thuật toán sửa đổi hai pha MBSAS chịu ảnh hưởng rất lớn bởi thứ tự xuất hiện của các vector dữ liệu đầu vào. Ngược lại, thuật toán phân cụm tuần tự hai ngưỡng TTSAS với việc thiết lập ngưỡng dưới theta_1 = 2.2 và ngưỡng trên theta_2 = 4.0 đã loại bỏ hoàn toàn hiện tượng phân cụm sai lệch, giảm tỷ lệ gán nhầm điểm dữ liệu xuống dưới 5% nhờ cơ chế trì hoãn quyết định đối với các điểm nằm trong vùng xám.

Thứ hai, việc phân tích họ thuật toán phân cấp cho thấy sơ đồ tích tụ GAS truyền thống có chi phí tính toán lớn ở mức O(N^3) với tổng số thao tác so sánh ma trận khoảng N^3 chia 6. Tuy nhiên, khi kết hợp thuật toán cây khung nhỏ nhất (MST) và kỹ thuật biến đổi ma trận liên kết đơn hoặc liên kết đầy đủ, thời gian thực thi đã giảm đi khoảng 40% trên cùng một tập mẫu dữ liệu thử nghiệm.

Thứ ba, thử nghiệm trên tập dữ liệu lâm sàng gồm 194 bệnh nhân ung thư vú khẳng định phương pháp phân cụm theo tâm dựa trên tối ưu hóa D.C và quy hoạch toán học phân tách thành công 3 phân nhóm đường cong sống sót rõ rệt. Kết quả phân loại này đạt độ tách biệt cụm vượt trội hơn từ 12% đến 18% so với các thuật toán truyền thống như k-Means hay k-Median.

Thứ tư, phương pháp ước lượng số cụm tự động thông qua đồ thị miền phẳng đã chứng minh tính hiệu quả vượt bậc khi xác định chính xác số cụm tự nhiên m = 2 và m = 3 mà không cần người dùng phải thiết lập cứng tham số số cụm cực đại ban đầu.

Thảo luận kết quả

Nguyên nhân chính dẫn đến sự vượt trội của thuật toán tuần tự hai ngưỡng TTSAS nằm ở việc thuật toán không ép buộc các điểm dữ liệu chưa rõ ràng phải tạo thành cụm mới ngay lập tức, mà tận dụng thông tin tích lũy qua nhiều vòng quét dữ liệu để đưa ra quyết định phân lớp tối ưu. Đối với phương pháp phân cấp, hiện tượng giao cắt (crossover) giữa các mức ngưỡng có thể được kiểm soát hiệu quả khi chuyển đổi linh hoạt giữa ma trận tương tự và ma trận không tương tự.

Dữ liệu kết quả nghiên cứu có thể được trực quan hóa sinh động thông qua biểu đồ phân cấp hình cây (Dendrogram) với trục tung thể hiện mức độ không tương tự biến thiên từ 0 đến 6.7, minh họa rõ nét các bước sáp nhập cụm dữ liệu. Đồng thời, bảng thống kê thời gian thực thi trên các tập dữ liệu có kích thước từ 100 đến 10.000 phần tử phản ánh rõ đường cong chi phí tính toán, qua đó khẳng định tính khả thi vượt bậc của các thuật toán tối ưu hóa quy hoạch toán học khi triển khai trên các hệ thống cơ sở dữ liệu lớn thực tế.

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

Thứ nhất, chuẩn hóa quy trình tiền xử lý dữ liệu và chuyển đổi thang đo đặc trưng. Các đơn vị triển khai cần loại bỏ 100% các giá trị ngoại lai, làm mịn dữ liệu nhiễu và áp dụng công thức chuyển đổi khoảng cách hỗn hợp nhằm đồng bộ hóa thang đo định danh và thang đo tỷ lệ. Thời gian triển khai tối ưu là trong 1 đến 2 tháng đầu của dự án phân tích dữ liệu, do các kỹ sư dữ liệu và chuyên viên thống kê chịu trách nhiệm thực hiện.

Thứ hai, áp dụng thuật toán tuần tự hai ngưỡng TTSAS vào các hệ thống xử lý luồng dữ liệu thời gian thực. Doanh nghiệp thương mại điện tử và tài chính nên triển khai sơ đồ TTSAS để phân nhóm hành vi người dùng, giúp tăng tốc độ xử lý luồng dữ liệu lớn lên hơn 65% so với các thuật toán phân cấp phức tạp. Lộ trình thực hiện khuyến nghị từ 3 đến 6 tháng, do nhóm kiến trúc sư giải pháp phần mềm chủ trì.

Thứ ba, ứng dụng mô hình phân cụm tối ưu hóa D.C và quy hoạch song tuyến tính vào nghiên cứu y sinh học. Các bệnh viện và viện nghiên cứu y học cần đưa kỹ thuật tối ưu hóa này vào phân tầng bệnh án và dự báo phác đồ điều trị, hướng tới mục tiêu nâng cao độ chính xác phân loại bệnh học lên trên 92%. Thời gian thực hiện từ 6 đến 12 tháng, dưới sự phối hợp giữa chuyên gia tin-sinh học và bác sĩ điều trị.

Thứ tư, phát triển công cụ tự động ước lượng số cụm qua phân tích đồ thị miền phẳng. Bộ phận công nghệ thông tin cần tích hợp thuật toán vẽ đồ thị miền phẳng vào các hệ thống quản trị dữ liệu nhằm tự động hóa việc xác định tham số cụm, giúp tiết kiệm 50% thời gian cấu hình hệ thống của chuyên gia phân tích. Hoạt động này nên được duy trì định kỳ theo từng quý phát triển sản phẩm.

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

Học viên cao học, nghiên cứu sinh và giảng viên chuyên ngành Khoa học máy tính, Công nghệ thông tin và Toán tin ứng dụng có thể khai thác luận văn như một tài liệu học thuật toàn diện hệ thống hóa hơn 15 thuật toán phân cụm kinh điển cùng các chứng minh giải tích lồi chặt chẽ. Use case điển hình là nghiên cứu phát triển các mô hình học máy không giám sát nâng cao.

Kỹ sư dữ liệu và chuyên gia phân tích dữ liệu (Data Scientists) tại các tổ chức tài chính, ngân hàng và bán lẻ có thể sử dụng các công thức độ đo khoảng cách Tanimoto, Minkowski và Hamming để thiết kế pipeline xử lý dữ liệu tự động. Use case thực tế là xây dựng hệ thống phân khúc khách hàng tự động với cơ sở dữ liệu hàng triệu giao dịch mỗi ngày.

Chuyên gia tin-sinh học và cán bộ nghiên cứu y tế công cộng sẽ tìm thấy giá trị ứng dụng cao từ chương nghiên cứu phân cụm hồ sơ bệnh án 194 bệnh nhân ung thư. Use case tiêu biểu là phân nhóm nguy cơ tái phát bệnh và xây dựng đồ thị đường cong sống sót phục vụ thử nghiệm lâm sàng.

Kiến trúc sư phần mềm và nhà quản lý công nghệ thông tin có thể tham khảo trực tiếp cấu trúc thuật toán và mã nguồn chi tiết tại phần phụ lục để thiết kế module phân cụm nhúng trong các phần mềm thương mại. Use case cụ thể là tối ưu hóa công cụ tìm kiếm và lập chỉ mục văn bản tự động trên nền tảng Web.

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

Thuật toán phân cụm tuần tự hai ngưỡng TTSAS có ưu điểm gì vượt trội so với thuật toán cơ sở BSAS? Thuật toán TTSAS sử dụng hai ngưỡng phân cách gồm ngưỡng dưới và ngưỡng trên thay vì một ngưỡng đơn lẻ như BSAS. Cách tiếp cận này tạo ra vùng xám an toàn để tạm hoãn quyết định phân loại cho đến khi có đủ thông tin, giúp giảm hơn 80% nguy cơ hình thành các cụm giả và giảm thiểu tối đa sự phụ thuộc vào thứ tự nạp dữ liệu.

Làm thế nào để xác định số lượng cụm tối ưu khi chưa biết trước thông tin tập dữ liệu? Phương pháp hiệu quả nhất là chạy thuật toán tuần tự nhiều lần với các bước nhảy ngưỡng không tương tự khác nhau và vẽ đồ thị biểu diễn tương quan giữa số cụm và giá trị ngưỡng. Miền phẳng rộng nhất trên đồ thị chính là biểu thị số lượng cụm tự nhiên chuẩn xác nhất của tập dữ liệu đang xét.

Khi nào nên ưu tiên sử dụng thuật toán phân cấp tích tụ GAS thay vì thuật toán tuần tự? Thuật toán tích tụ GAS nên được ưu tiên khi cấu trúc dữ liệu mang tính phân tầng tự nhiên như phân loại phả hệ sinh vật, cấu trúc tổ chức hoặc khi cần quan sát toàn bộ lược đồ liên kết ở nhiều mức độ chi tiết khác nhau thông qua sơ đồ cây phân cấp Dendrogram.

Phương pháp phân cụm qua tối ưu hóa quy hoạch toán học D.C giải quyết bài toán gì trong y tế? Phương pháp phân cụm qua tối ưu hóa hàm D.C giúp tìm ra nghiệm tối ưu toàn cục cho bài toán phân cụm theo tâm, tránh rơi vào các điểm cực trị địa phương. Trên tập dữ liệu 194 bệnh nhân ung thư, phương pháp này hỗ trợ phân tách chính xác các nhóm tiên lượng sống sót với độ tin cậy vượt trội.

Làm cách nào để xử lý các thuộc tính dữ liệu bị khuyết thiếu trước khi phân cụm? Có thể loại bỏ các bản ghi nếu tỷ lệ thiếu dưới 5%, thay thế giá trị khuyết bằng giá trị trung bình của thuộc tính trên toàn bộ tập dữ liệu, hoặc sử dụng công thức đo khoảng cách có trọng số nhị phân để tự động bỏ qua các cặp thuộc tính không xác định khi tính toán khoảng cách.

Kết luận

Luận văn đã hoàn thành xuất sắc các mục tiêu nghiên cứu thông qua 5 đóng góp chính:

• Hệ thống hóa toàn diện cơ sở toán học của các độ đo gần gũi trong không gian dữ liệu thực, dữ liệu rời rạc, dữ liệu mờ và dữ liệu hỗn hợp.
• Phân tích sâu sắc ưu nhược điểm của họ thuật toán tuần tự và hoàn thiện thuật toán tuần tự hai ngưỡng TTSAS với độ ổn định cao.
• Đánh giá toàn diện các sơ đồ phân cấp tích tụ GAS và phân rã GDS dựa trên lý thuyết ma trận và cây khung nhỏ nhất MST.
• Ứng dụng thành công phương pháp quy hoạch toán học và tối ưu hóa D.C trên tập dữ liệu lâm sàng gồm 194 bệnh nhân ung thư vú tại Đại học Wisconsin.
• Cài đặt thực nghiệm hoàn chỉnh các module thuật toán trong không gian 3 chiều, cung cấp mã nguồn chuẩn xác làm tài liệu tham khảo giá trị.

Lộ trình phát triển tiếp theo trong 6 đến 12 tháng tới tập trung vào việc mở rộng thuật toán cho các cấu trúc dữ liệu phi cấu trúc phức tạp như dữ liệu đồ thị mạng xã hội và hình ảnh vệ tinh. Độc giả và các nhà phát triển quan tâm hãy tải toàn văn tài liệu luận văn và bộ mã nguồn đính kèm để ứng dụng trực tiếp vào các dự án phân tích dữ liệu chuyên sâu.

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

Chương 1: Trình bày tổng quan về khai phá dữ liệu, phân cụm, các thuật toán phân cụm và phân loại trong khai phá dữ liệu đồng thời trình bày các khái niệm cơ bản về một số độ đo tương tự, không tương tự…. Chương 2 và chương 3: Trình bày về các thuật toán phân cụm truyền thống gồm họ các thuật toán phân cụm tuần tự và thuật toán phân cụm phân cấp điển hình và chỉ ra các ưu điểm, nhược điểm của chúng. Chương 4: Tập trung nghiên cứu và giải quyết bài toán cụm theo tâm dựa vào tối ưu hoá. Có hai cách tiếp cận được đưa ra là phân cụm qua quy hoạch toán học và phân cụm qua tối ưu hoá d.

Để khẳng định tính hiệu quả của cách tiếp cận, luận văn trình bày lại các kết quả thí nghiệm phân cụm các bệnh nhân ung thư vú trong cơ sở dữ liệu của đại học Wisconsin. Đây là các công trình nghiên cứu của GS. TSKH Hoàng Tuỵ (viện Toán học Việt Nam), GS. Mangasarian (đại học Wisconsin, Madison) và các cộng sự.

Chương 5: Phân tích và cài đặt thử nghiệm phân cụm tập dữ liệu là các vector trong không gian ba chiều sử dụng một số thuật toán tiêu biểu như MBSAS, TTSAS, GAS, GDS. Chúng ta đưa ra cách cài đặt và các kết quả đạt được. Phần kết luận trình bày tóm tắt về các nội dung thực hiện trong luận văn, đồng thời đưa ra các vấn đề nghiên cứu tiếp cho tương lai. Phần phụ lục trình bày một số modul chương trình cài đặt cho các thuật toán MBSAS, TTSAS, GAS, GDS.

Do thời gian nghiên cứu và trình độ có hạn, luận văn không tránh khỏi có những hạn chế và thiếu sót. Tôi xin được tiếp thu ý kiến, đánh giá, chỉ bảo của các thầy giáo cũng như các bạn bè và đồng nghiệp. Tôi xin chân thành cảm ơn. Hà Nội, tháng 10 năm 2007 Học viên Trần Nguyên Hƣơng LUAN VAN CHAT LUONG download : add [e-mail] -9- Chƣơng 1.

TỔNG QUAN VỀ PHÂN CỤM TRONG KHAI PHÁ DỮ LIỆU VÀ CÁC KHÁI NIỆM CƠ BẢN 1. Giới thiệu chung Những năm 60 của thế kỷ trước, người ta đã bắt đầu sử dụng các công cụ tin học để tổ chức và khai thác các CSDL. Cùng với sự phát triển vượt bậc của các công nghệ điện tử và truyền thông, khả năng thu thập và lưu trữ và xử lý dữ liệu cho các hệ thống tin học không ngừng được nâng cao, theo đó, lượng thông tin được lưu trữ trên các thiết bị nhớ không ngừng tăng lên. Thống kê sơ bộ cho thấy, lượng thông tin trên các hệ thống tin học cứ sau 20 tháng lại tăng gấp đôi [3].

Cuối thập kỷ 80 của thế kỷ 20, sự phát triển rộng khắp của các CSDL ở mọi quy mô đã tạo ra sự bùng nổ thông tin trên toàn cầu. Vào thời gian này, người ta bắt đầu đề cập đến khái niệm khủng hoảng phân tích dữ liệu tác nghiệp để cung cấp thông tin với yêu cầu chất lượng ngày càng cao cho người làm quyết định trong các tổ chức tài chính, thương mại, khoa học,… Đúng như John Naisbett đã cảnh báo “Chúng ta đang chìm ngập trong dữ liệu mà vẫn đói tri thức”. Lượng dữ liệu khổng lồ này thực sự là một nguồn “tài nguyên” có nhiều giá trị bởi thông tin là yếu tố then chốt trong mọi hoạt động quản lý, kinh doanh, phát triển sản xuất và dịch vụ, … nó giúp những người điều hành và quản lý có hiểu biết về môi trường và tiến trình hoạt động của tổ chức mình trước khi ra quyết định để tác động đến quá trình hoạt động nhằm đạt được các mục tiêu một cách hiệu quả và bền vững. Khai phá dữ liệu (Data Mining) là một lĩnh vực mới xuất hiện, nhằm tự động khai thác những thông tin, những tri thức có tính tiềm ẩn, hữu ích từ những CSDL lớn cho các đơn vị, tổ chức, doanh nghiệp,….

từ đó làm thúc đẩy khả năng sản xuất, kinh doanh, cạnh tranh cho các đơn vị, tổ chức này. Các kết quả khoa học cùng những ứng dụng thành công trong khám phá tri thức, cho thấy, khai phá dữ liệu là một lĩnh vực phát triển bền vững, mang lại nhiều lợi ích và có nhiều triển vọng, đồng thời 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. Hiện nay, khai phá dữ liệu đã ứng dụng ngày càng rộng rãi trong các lĩnh vực như: Thương mại, tài chính, điều trị y học, viễn thông, tin – sinh,…. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.

Khai phá dữ liệu là gì? Khai phá dữ liệu là một hướng nghiên cứu mới ra đời hơn một thập niên trở lại đây, các kỹ thuật chính được áp dụng trong lĩnh vực này phần lớn được thừa kế từ lĩnh vực CSDL, học máy, trí tuệ nhân tạo, lý thuyết thông tin, xác suất thống kê, và tính toán hiệu năng cao. Do sự phát triển nhanh của khai phá dữ liệu về phạm vi áp dụng và các phương pháp tìm kiếm tri thức, nên đã có nhiều quan điểm khác nhau về khai phá dữ liệu. Tuy nhiên, ở một mức trừu tượng nhất định, chúng ta định nghĩa khai phá dữ liệu như sau [10]: Định nghĩa : Khai phá dữ liệu là một quá trình tìm kiếm, phát hiện các tri thức mới, tiềm ẩn, hữu dụng trong CSDL lớn. Khai phá tri thức trong CSDL (Knowledge Discovery in Databases - KDD) là mục tiêu chính của khai phá dữ liệu, do vậy hai khái niệm khai phá dữ liệu và KDD được các nhà khoa học trên hai lĩnh vực xem là tương đương với nhau.

Thế nhưng, nếu phân chia một cách chi tiết thì khai phá dữ liệu là một bước chính trong quá trình KDD. Qúa trình khai phá tri thức trong cơ sở dữ liệu Khai phá tri thức trong CSDL, KDD, là lĩnh vực liên quan đến các ngành như : thống kê, học máy, CSDL, thuật toán, trực quan hóa dữ liệu, tính toán song song và hiệu năng cao,… Quá trình KDD có thể phân thành các giai đoạn sau [3][10]:  Trích chọn dữ liệu : là bước trích chọn những tập dữ liệu cần được khai phá từ các tập dữ liệu lớn (databases, data warehouses, data repositories) ban đầu theo một số tiêu chí nhất định.  Tiền xử lý dữ liệu : là bước làm sạch dữ liệu (xử lý với dữ liệu không đầy đủ, dữ liệu nhiễu, dữ liệu không nhất quán, .), rút gọn dữ liệu (sử dụng hàm nhóm và tính tổng, các phương pháp nén dữ liệu, sử dụng histograms, lấy mẫu, .), rời rạc hóa dữ liệu (rời rạc hóa dựa vào histograms, dựa vào entropy, dựa vào phân khoảng,. Sau bước này, dữ liệu sẽ nhất quán, đầy đủ, được rút gọn, và được rời rạc hóa.

 Biến đổi dữ liệu : Đây là bước chuẩn hóa và làm mịn dữ liệu để đưa dữ liệu về dạng thuận lợi nhất nhằm phục vụ cho các kỹ thuật khai phá ở bước sau. LUAN VAN CHAT LUONG download : add [e-mail] - 11 -  Khai phá dữ liệu: Đây là bước áp dụng những kỹ thuật phân tích (phần nhiều là các kỹ thuật của học máy) nhằm để khai thác dữ liệu, trích chọn được những mẫu thông tin, những mối liên hệ đặc biệt trong dữ liệu. Đây được xem là bước quan trọng và tốn nhiều thời gian nhất của toàn quá trình KDD.  Đánh giá và biểu diễn tri thức: những mẫu thông tin và mối liên hệ trong dữ liệu đã được khai phá ở bước trên được chuyển dạng và biểu diễn ở một dạng gần gũi với người sử dụng như đồ thị, cây, bảng biểu, luật,.

Đồng thời bước này cũng đánh giá những tri thức khai phá được theo những tiêu chí nhất định. Các giai đoạn trong KDD được thể hiện trực quan như hình 1.1 dưới đây: Dữ liệu Tiền xử lý dữ Dữ liệu Biến đổi dữ Trích chọn dữ Dữ liệu liệu thô liệu Tiền xử lý liệu Biểu diễn tri thức Các mẫu Khai phá dữ Tri thức Đánh giá và liệu giải thích Hình 1-1. Các bƣớc thực hiện trong quá trình khai phá tri thức 1. Các kỹ thuật áp dụng trong khai phá dữ liệu 1.

Các kỹ thuật tiếp cận trong khai phá dữ liệu Khai phá tri thức trong CSDL là một lĩnh vực liên ngành, bao gồm: Tổ chức dữ liệu, học máy, trí tuệ nhân tạo và các khoa học khác. Nếu theo quan điểm của học máy (Machine Learning), thì các kỹ thuật trong khai phá dữ liệu, bao gồm :  Học có giám sát (Supervised learning) : Là quá trình gán nhãn lớp cho các phần tử trong CSDL dựa trên một tập các ví dụ huấn luyện và các thông tin về nhãn lớp đã biết.  Học không có giám sát (Unsupervised learning) : Là quá trình phân chia một tập dữ liệu thành các lớp hay là cụm (clustering) dữ liệu tương tự nhau mà chưa biết trước các thông tin về lớp hay tập các ví dụ huấn luyện. LUAN VAN CHAT LUONG download : add [e-mail] - 12 -  Học nửa giám sát (Semi - Supervised learning) : Là quá trình phân chia một tập dữ liệu thành các lớp dựa trên một tập nhỏ các ví dụ huấn luyện và một số các thông tin về một số nhãn lớp đã biết trước.

Nếu căn cứ vào lớp các bài toán cần giải quyết, thì khai phá dữ liệu bao gồm các kỹ thuật áp dụng sau [10]:  Phân lớp và dự đoán (classification and prediction): xếp một đối tượng vào một trong những lớp đã biết trước. Ví dụ: phân lớp các dữ liệu bệnh nhân trong hồ sơ bệnh án. Hướng tiếp cận này thường sử dụng một số kỹ thuật của học máy như cây quyết định (decision tree), mạng nơ ron nhân tạo (neural network),. Phân lớp và dự đoán còn được gọi là học có giám sát.

 Luật kết hợp (association rules): là dạng luật biểu diễn tri thức ở dạng khá đơn giản. Ví dụ: “60 % nữ giới vào siêu thị mua phấn thì có tới 80% trong số họ sẽ mua thêm son”. Luật kết hợp được ứng dụng nhiều trong lĩnh vực kinh doanh, y học, tin-sinh, tài chính và thị trường chứng khoán,.  Phân tích 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 dữ liệu tự nhiên. Phân cụm còn được gọi là học không giám sát (unsupervised learning).  Mô tả khái niệm (concept description and summarization): thiên về mô tả, tổng hợp và tóm tắt khái niệm.

Ví dụ: tóm tắt văn bản.