Luận văn: Phân cụm dữ liệu định danh với số chiều cao - Đại học Quốc Gia Hà Nội
Luận văn thạc sĩ về phân cụm dữ liệu định danh. Nghiên cứu các thuật toán, ứng dụng phân cụm trong các bài toán thực tế. Tải luận văn miễn phí!
Trường đại học
Trường Đại Học Công Nghệ - Đại Học Quốc Gia Hà NộiChuyên ngành
Công Nghệ Thông TinNgười đăng
Ẩn danhThể loại
Luận Văn Thạc SỹPhí lưu trữ
35 PointMục lục chi tiết
Tóm tắt
I. Tổng quan về Phân Cụm Dữ Liệu Định Danh Luận Văn
Bài toán phân cụm dữ liệu định danh đóng vai trò quan trọng trong nhiều lĩnh vực, từ phân tích thống kê đa chiều đến học máy không giám sát. Ứng dụng của nó trải rộng trong nhiều ngành như gian lận tài chính, chẩn đoán y tế, xử lý ảnh, tìm kiếm thông tin và tin sinh học. Các thuật toán phân cụm ban đầu tập trung vào dữ liệu số, nhưng sự phát triển của công nghệ thông tin đã thúc đẩy nhu cầu khám phá tri thức trên nhiều dạng dữ liệu khác nhau, đặc biệt là dữ liệu quan hệ nhiều chiều với các thuộc tính định danh. Luận văn thạc sĩ này tập trung vào việc giải quyết bài toán phân cụm dữ liệu định danh hiệu quả, đặc biệt khi số chiều dữ liệu lớn. Theo tài liệu gốc, bài toán phân cụm dữ liệu thuộc loại "thiết lập không đúng đắn", tức là lời giải thường không duy nhất và nhạy cảm với thay đổi nhỏ trong dữ liệu. Một cách tiếp cận cho dữ liệu chiều cao là chiếu chúng lên không gian có chiều thấp hơn, chẳng hạn, các phƣơng pháp: CLIQUE[2], ENCLUS[6], MAFIA[19], Proclus[4], ORCLUS[5], FINDIT[13], DOC [7], d-clusters[9], HARP[14] và LDR[11] cho dữ liệu số. Việc lựa chọn thuật toán thích hợp, đặc biệt khi số chiều dữ liệu tăng cao, là yếu tố then chốt để đảm bảo hiệu quả và chất lượng của quá trình phân cụm.
1.1. Ứng dụng đa dạng của clustering dữ liệu định danh
Phân cụm dữ liệu định danh không chỉ là một kỹ thuật học thuật mà còn là một công cụ mạnh mẽ trong nhiều ứng dụng thực tế. Ví dụ, trong lĩnh vực y tế, nó có thể được sử dụng để phân loại bệnh nhân dựa trên các triệu chứng và tiền sử bệnh, giúp các bác sĩ đưa ra chẩn đoán chính xác hơn. Trong lĩnh vực tài chính, nó có thể giúp phát hiện các giao dịch gian lận bằng cách xác định các mẫu giao dịch bất thường. Theo tài liệu gốc, các kỹ thuật PCDL đã đƣợc áp dụng cho một số ứng dụng điển hình trong các lĩnh vực sau [1, 10, 17]: 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. Việc hiểu rõ các ứng dụng này giúp chúng ta đánh giá được tầm quan trọng của việc nghiên cứu và phát triển các thuật toán phân cụm hiệu quả.
1.2. Tổng quan về luận văn thạc sĩ về phân cụm dữ liệu
Luận văn này đi sâu vào bài toán phân cụm dữ liệu định danh với số chiều cao, một thách thức lớn trong lĩnh vực khai phá dữ liệu. Luận văn trình bày tổng quan về các phương pháp phân cụm truyền thống, đồng thời giới thiệu các thuật toán mới được phát triển để giải quyết các hạn chế của các phương pháp truyền thống khi đối mặt với dữ liệu chiều cao. Mục tiêu của luận văn là cung cấp một cái nhìn toàn diện về bài toán phân cụm dữ liệu định danh, từ lý thuyết đến ứng dụng thực tế. Theo tài liệu gốc, luận văn trình bày một số thuật toán tối ƣu hoá để so sánh phân nhóm dữ liệu phân loại chiều cao. Trong các thuật toán trình bày, một kỹ thuật trọng số mới phân loại dữ liệu đƣợc đƣa ra để tính toán trọng số cho mỗi thuộc tính (hoặc chiều) trong mỗi cụm và sử dụng các giá trị trọng số để xác định tập hợp con cuả các thuộc tính quan trọng mà phân loại cụm khác nhau.
1.3. Độ đo tương đồng trong phân cụm dữ liệu định danh
Một trong những yếu tố then chốt trong phân cụm dữ liệu là việc xác định độ đo tương đồng phù hợp. Đối với dữ liệu định danh, các độ đo khoảng cách truyền thống thường không hiệu quả. Do đó, cần phải sử dụng các độ đo đặc biệt, chẳng hạn như khoảng cách Hamming hoặc các độ đo dựa trên tần suất xuất hiện của các giá trị thuộc tính. Theo tài liệu gốc, tất cả phƣơng pháp đo khoảng cách đều phụ thuộc vào kiểu thuộc tính (hay kiểu dữ liệu) của các đối tƣợng đƣợc phân tích. Chẳng hạn thuộc tính hạng mục (Categorical) ngƣời ta không sử dụng độ đo khoảng cách mà sử dụng một hƣớng hình học của dữ liệu. Mỗi một kiểu dữ liệu đều tồn tại một không gian đo mêtric cho nó. Việc lựa chọn độ đo tương đồng phù hợp có ảnh hưởng trực tiếp đến chất lượng của kết quả phân cụm. Luận văn này sẽ đi sâu vào các độ đo tương đồng khác nhau và đánh giá hiệu quả của chúng trong các tình huống cụ thể.
II. Thách Thức khi Phân Cụm Dữ Liệu Định Danh Chiều Cao
Khi số chiều của dữ liệu tăng lên, bài toán phân cụm dữ liệu định danh trở nên phức tạp hơn đáng kể. Một trong những thách thức lớn nhất là hiện tượng "lời nguyền chiều cao", trong đó khoảng cách giữa các điểm dữ liệu trở nên đồng đều hơn, làm giảm khả năng phân biệt giữa các cụm. Ngoài ra, dữ liệu chiều cao thường chứa nhiều thuộc tính không liên quan hoặc dư thừa, gây nhiễu cho quá trình phân cụm. Cuối cùng, việc tính toán độ đo tương đồng trên dữ liệu chiều cao có thể tốn kém về mặt thời gian và tài nguyên tính toán. Luận văn này sẽ tập trung vào việc giải quyết các thách thức này bằng cách phát triển các thuật toán phân cụm hiệu quả và có khả năng mở rộng.
2.1. Vấn đề dữ liệu thưa thớt thuộc tính dư thừa
Trong dữ liệu chiều cao, hiện tượng thưa thớt xảy ra khi số lượng giá trị khác không trong mỗi đối tượng dữ liệu rất ít so với tổng số thuộc tính. Điều này có thể dẫn đến việc các đối tượng dữ liệu trông giống nhau hơn so với thực tế, làm giảm khả năng phân biệt giữa các cụm. Ngoài ra, dữ liệu chiều cao thường chứa nhiều thuộc tính dư thừa, tức là các thuộc tính cung cấp thông tin tương tự nhau. Việc loại bỏ các thuộc tính dư thừa có thể giúp cải thiện hiệu quả và chất lượng của quá trình phân cụm. Theo tài liệu gốc, với kỹ thuật thông thƣờng không đạt đƣợc khi phân cụm đƣợc tiến hành trong không gian chiều cao. Chẳng hạn dữ liệu thƣa thớt, chứa các thuộc tính dƣ thừa trong dữ liệu chiều cao, sự gia tăng kích thƣớc, sự khác nhau giữa các khoảng cách của đối tƣợng.
2.2. Ảnh hưởng của lời nguyền chiều cao đến phân cụm
"Lời nguyền chiều cao" là một hiện tượng trong đó hiệu suất của các thuật toán học máy giảm sút khi số chiều của dữ liệu tăng lên. Trong ngữ cảnh của phân cụm dữ liệu, "lời nguyền chiều cao" có thể dẫn đến việc khoảng cách giữa các đối tượng dữ liệu trở nên đồng đều hơn, làm cho việc phân biệt giữa các cụm trở nên khó khăn hơn. Điều này là do khi số chiều tăng lên, không gian dữ liệu trở nên thưa thớt hơn, và các đối tượng dữ liệu có xu hướng tập trung ở các góc của không gian. Để giảm thiểu ảnh hưởng của "lời nguyền chiều cao", cần phải sử dụng các thuật toán phân cụm có khả năng chống lại hiện tượng này, hoặc sử dụng các kỹ thuật giảm chiều để giảm số lượng thuộc tính.
III. Thuật toán K Modes Các Biến Thể Cải Tiến Mới Nhất
Thuật toán K-modes là một thuật toán phân cụm phổ biến được sử dụng để phân cụm dữ liệu định danh. Thuật toán này là một biến thể của thuật toán K-means, được thiết kế để làm việc với dữ liệu số. Tuy nhiên, thuật toán K-modes có một số hạn chế, đặc biệt khi đối mặt với dữ liệu chiều cao và dữ liệu chứa nhiều thuộc tính không liên quan. Do đó, nhiều biến thể cải tiến của thuật toán K-modes đã được phát triển để giải quyết các hạn chế này. Luận văn này sẽ trình bày một số biến thể cải tiến quan trọng nhất của thuật toán K-modes, bao gồm thuật toán K-modes có trọng số và thuật toán MWKM.
3.1. Tìm hiểu sâu về thuật toán K modes cơ bản
Thuật toán K-modes là một thuật toán phân cụm dựa trên việc tìm kiếm các "mode" (giá trị xuất hiện nhiều nhất) trong mỗi cụm. Thuật toán này bắt đầu bằng cách chọn ngẫu nhiên k đối tượng dữ liệu làm trung tâm của k cụm. Sau đó, mỗi đối tượng dữ liệu được gán cho cụm có trung tâm gần nhất, dựa trên một độ đo tương đồng phù hợp. Sau khi tất cả các đối tượng dữ liệu đã được gán cho một cụm, các trung tâm cụm được cập nhật bằng cách tính toán mode của mỗi cụm. Quá trình này được lặp lại cho đến khi các trung tâm cụm không thay đổi nữa, hoặc cho đến khi đạt được một số điều kiện dừng khác.
3.2. K modes có trọng số WKM Giải quyết hạn chế thuộc tính
Một trong những hạn chế của thuật toán K-modes cơ bản là nó coi tất cả các thuộc tính là quan trọng như nhau. Tuy nhiên, trong thực tế, một số thuộc tính có thể quan trọng hơn các thuộc tính khác trong việc xác định cấu trúc cụm. Để giải quyết hạn chế này, thuật toán K-modes có trọng số (WKM) đã được phát triển. Trong thuật toán WKM, mỗi thuộc tính được gán một trọng số, thể hiện tầm quan trọng của thuộc tính đó trong việc phân cụm. Theo tài liệu gốc, thuật toán có trọng số k-modes(WKM) Khi thuật toán đƣợc sử dụng để xử lý dữ liệu phạm trù, thuật toán đƣợc xem nhƣ là một thuật toán k-modes có trọng số (The weighting k-modes algorithm - WKM) [17]. Các trọng số này được cập nhật trong quá trình phân cụm, để phản ánh tầm quan trọng thực tế của các thuộc tính.
IV. Thuật toán MWKM Phân Cụm Dữ Liệu Hỗn Hợp Tối Ưu
Thuật toán MWKM (Mixed Attribute Weighting K-modes) là một thuật toán phân cụm được thiết kế để làm việc với dữ liệu hỗn hợp, tức là dữ liệu chứa cả thuộc tính số và thuộc tính định danh. Thuật toán MWKM là một biến thể cải tiến của thuật toán K-modes có trọng số, được thiết kế để giải quyết các hạn chế của thuật toán WKM khi đối mặt với dữ liệu hỗn hợp. Thuật toán MWKM sử dụng một phương pháp trọng số hỗn hợp để đánh giá tầm quan trọng của các thuộc tính số và thuộc tính định danh trong quá trình phân cụm. Nhƣ vậy kết quả phân cụm của MWKM chính xác hơn hẳn K-Modes và WKM trong tất cả các trƣờng hợp.
4.1. Ưu điểm vượt trội của MWKM so với K Modes WKM
Thuật toán MWKM có một số ưu điểm vượt trội so với các thuật toán K-modes và WKM. Thứ nhất, MWKM có khả năng làm việc với dữ liệu hỗn hợp, trong khi K-modes và WKM chỉ có thể làm việc với dữ liệu định danh. Thứ hai, MWKM sử dụng một phương pháp trọng số hỗn hợp để đánh giá tầm quan trọng của các thuộc tính số và thuộc tính định danh, giúp cải thiện độ chính xác của quá trình phân cụm.Thứ ba, MWKM có khả năng chống lại hiện tượng "lời nguyền chiều cao" tốt hơn các thuật toán K-modes và WKM. Khắc phục nhƣợc điểm của thuật toán WKM, thuật toán k-modes cho dữ liệu hỗn hợp có trọng số (The mixed attribute weighting k-modes algorithm - MWKM) bên cạnh ma trận trọng số phản ánh chính xác sự bất tƣơng đồng khi giá trị các thuộc tính khác nhau thì còn ma trận trọng số S giúp phản ánh chính xác sự bất tƣơng đồng khi giá trị các thuộc tính bằng nhau.
4.2. Phân tích chi tiết phương pháp trọng số hỗn hợp trong MWKM
Phương pháp trọng số hỗn hợp trong thuật toán MWKM là một phương pháp độc đáo cho phép đánh giá tầm quan trọng của các thuộc tính số và thuộc tính định danh một cách linh hoạt. Trong phương pháp này, mỗi thuộc tính được gán một trọng số dựa trên mức độ phân tán của các giá trị của thuộc tính đó trong mỗi cụm. Các thuộc tính có độ phân tán thấp được gán trọng số cao, trong khi các thuộc tính có độ phân tán cao được gán trọng số thấp. Đồng thời Nhờ vậy kết quả phân cụm của MWKM chính xác hơn hẳn K-Modes và WKM trong tất cả các trƣờng hợp.
4.3. Ứng dụng thực tiễn và đánh giá hiệu quả của MWKM
Thuật toán MWKM có thể được áp dụng cho nhiều ứng dụng thực tế, chẳng hạn như phân loại khách hàng, phân tích dữ liệu y tế và phân tích dữ liệu web. Trong luận văn này, chúng ta sẽ đánh giá hiệu quả của thuật toán MWKM trên một số bộ dữ liệu thực tế, so sánh với các thuật toán phân cụm khác. Kết quả cho thấy rằng thuật toán MWKM có hiệu quả hơn các thuật toán K-modes và WKM trong nhiều tình huống. Trong khuôn khổ luận văn quan tâm đến việc phân cụm dữ liệu định danh. Ở chƣơng này chúng tôi có trình bày một số thuật toán, trong đó đi sâu vào hai thuật toán COOLCAT và MWKM để phân cụm dữ liệu định danh với nhiều thuộc tính. Luận văn cũng đã so sánh đƣợc ƣu, nhƣợc điểm của hai thuật toán này thông qua kết quả thực nghiệm ở chƣơng 4.
V. Entropy Thuật Toán COOLCAT Giải Pháp Phân Cụm Mới
Entropy là một khái niệm trong lý thuyết thông tin, được sử dụng để đo độ không chắc chắn hoặc độ ngẫu nhiên của một biến. Trong ngữ cảnh của phân cụm dữ liệu, entropy có thể được sử dụng để đánh giá chất lượng của các cụm. Một cụm có entropy thấp là một cụm có độ đồng nhất cao, tức là các đối tượng dữ liệu trong cụm có các giá trị thuộc tính tương tự nhau. Thuật toán COOLCAT là một thuật toán phân cụm sử dụng entropy để đánh giá chất lượng của các cụm. Thuật toán COOLCAT có một số ưu điểm so với các thuật toán phân cụm khác, chẳng hạn như khả năng tìm kiếm các cụm có hình dạng bất kỳ và khả năng xử lý dữ liệu chiều cao.
5.1. Vai trò của Entropy trong đánh giá chất lượng phân cụm
Entropy đóng vai trò quan trọng trong việc đánh giá chất lượng của các cụm. Một cụm có entropy thấp là một cụm có độ đồng nhất cao, tức là các đối tượng dữ liệu trong cụm có các giá trị thuộc tính tương tự nhau. Ngược lại, một cụm có entropy cao là một cụm có độ đồng nhất thấp, tức là các đối tượng dữ liệu trong cụm có các giá trị thuộc tính khác nhau. Do đó, entropy có thể được sử dụng để đánh giá xem một thuật toán phân cụm có tạo ra các cụm có ý nghĩa hay không.
5.2. Thuật toán COOLCAT Chi tiết cách tiếp cận dựa trên Entropy
Thuật toán COOLCAT là một thuật toán phân cụm sử dụng entropy để đánh giá chất lượng của các cụm. Thuật toán COOLCAT bắt đầu bằng cách chọn ngẫu nhiên k đối tượng dữ liệu làm trung tâm của k cụm. Sau đó, mỗi đối tượng dữ liệu được gán cho cụm có trung tâm gần nhất, dựa trên một độ đo tương đồng phù hợp. Sau khi tất cả các đối tượng dữ liệu đã được gán cho một cụm, các trung tâm cụm được cập nhật bằng cách tính toán trung bình của các giá trị thuộc tính trong mỗi cụm. Quá trình này được lặp lại cho đến khi các trung tâm cụm không thay đổi nữa, hoặc cho đến khi đạt được một số điều kiện dừng khác.
5.3. So sánh COOLCAT với MWKM và các thuật toán khác
Thuật toán COOLCAT có một số ưu điểm so với các thuật toán phân cụm khác, chẳng hạn như khả năng tìm kiếm các cụm có hình dạng bất kỳ và khả năng xử lý dữ liệu chiều cao. Tuy nhiên, thuật toán COOLCAT cũng có một số hạn chế, chẳng hạn như việc nó nhạy cảm với các tham số đầu vào và có thể không hoạt động tốt trên các bộ dữ liệu có nhiều nhiễu. Các hàm mục tiêu để đánh giá chất lƣợng phân cụm là CU, ARI và ER đã đƣợc trình bày kỹ trong chƣơng 3.
VI. Kết quả Thử Nghiệm Hướng Phát Triển Phân Cụm
Luận văn này đã trình bày một số thuật toán phân cụm cho dữ liệu định danh, đặc biệt là thuật toán MWKM và COOLCAT. Để đánh giá hiệu quả của các thuật toán này, chúng ta đã thực hiện một số thử nghiệm trên các bộ dữ liệu thực tế. Kết quả cho thấy rằng các thuật toán MWKM và COOLCAT có hiệu quả hơn các thuật toán K-modes và WKM trong nhiều tình huống. Tuy nhiên, vẫn còn nhiều hướng phát triển cho các thuật toán phân cụm cho dữ liệu định danh. Một hướng phát triển quan trọng là phát triển các thuật toán có khả năng xử lý dữ liệu chiều cao tốt hơn.
6.1. Đánh giá hiệu năng của các thuật toán trên dữ liệu thực tế
Để đánh giá hiệu năng của các thuật toán MWKM và COOLCAT, chúng ta đã thực hiện một số thử nghiệm trên các bộ dữ liệu thực tế, bao gồm cả bộ dữ liệu y tế, bộ dữ liệu tài chính và bộ dữ liệu web. Các kết quả cho thấy rằng các thuật toán MWKM và COOLCAT có hiệu quả hơn các thuật toán K-modes và WKM trong nhiều tình huống, đặc biệt khi đối mặt với dữ liệu chiều cao và dữ liệu chứa nhiều thuộc tính không liên quan. Luận văn đã trình bày kết quả thực nghiệm so sánh hai thuật toán COOLCAT và MWKM với 5 bộ dữ liệu với nhiều thuộc tính: Cơ sở dữ liệu đậu tƣơng, cơ sở dữ liệu nấm, cơ sở dữ liệu ung thƣ phổi, CSDL về thuê bao di động phát sinh của thành phố Hà Nội và CSDL điều tra dân số của Mỹ năm 1990.
6.2. Các hướng nghiên cứu phát triển tiềm năng trong tương lai
Mặc dù các thuật toán MWKM và COOLCAT đã cho thấy hiệu quả trong nhiều tình huống, vẫn còn nhiều hướng phát triển cho các thuật toán phân cụm cho dữ liệu định danh. Một hướng phát triển quan trọng là phát triển các thuật toán có khả năng xử lý dữ liệu chiều cao tốt hơn. Một hướng phát triển khác là phát triển các thuật toán có khả năng xử lý dữ liệu có nhiều nhiễu tốt hơn. Cuối cùng, một hướng phát triển quan trọng là phát triển các thuật toán có khả năng tự động lựa chọn các tham số phù hợp. Phần kết luận trình bày tóm tắt kết quả thu đƣợc và đề xuất hƣớng nghiên cứu tiếp theo.
24/09/2025
