Đăng ký Đăng nhập
Trang chủ Thuật toán phân cụm đồng thời và ứng dụng...

Tài liệu Thuật toán phân cụm đồng thời và ứng dụng

.PDF
90
188
58

Mô tả:

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN -------------------------------- LƯU XUÂN VĂN THUẬT TOÁN PHÂN CỤM ĐỒNG THỜI VÀ ỨNG DỤNG Chuyên ngành: Cơ sở toán cho tin học Mã số: 60460110 LUẬN VĂN THẠC SĨ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Nguyễn Thị Hồng Minh Hà Nội - 2015 LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu do chính tôi thực hiện. Các số liệu, kết quả phân tích trong luận văn là hoàn toàn trung thực và chưa từng được ai công bố trong bất kỳ công trình nghiên cứu nào trước đây. Hà Nội, ngày 21 tháng 12 năm 2015 Tác giả Lưu Xuân Văn LỜI CẢM ƠN Được sự cho phép của Khoa Toán-Cơ-Tin, Trường Đại học Khoa học tự nhiên, ĐHQGHN và sự đồng ý của cô giáo hướng dẫn TS Nguyễn Thị Hồng Minh, tác giả đã thực hiện đề tài nghiên cứu “Thuật toán phân cụm đồng thời và ứng dụng”. Để hoàn thành luận văn này, tác giả xin chân thành cảm ơn các thầy cô giáo Bộ môn Tin học, Khoa Toán-Cơ-Tin đã tận tình hướng dẫn, giảng dạy và tạo điều kiện trong suốt quá trình học tập, nghiên cứu và rèn luyện ở trường Đại học Khoa học tự nhiên. Tác giả xin tỏ lòng biết ơn sâu sắc đến cô giáo TS. Nguyễn Thị Hồng Minh đã tận tình, chu đáo hướng dẫn, giúp đỡ, tạo mọi điều kiện thuận lợi cho tác giả trong suốt quá trình nghiên cứu, thực hiện luận văn này. Xin được chân thành cảm ơn các bạn bè đã luôn động viên, khích lệ tinh thần để tác giả có đủ nghị lực hoàn thành luận văn này. Mặc dù đã có nhiều cố gắng để thực hiện đề tài một cách hoàn chỉnh nhất. Song do thời gian thực tế vừa công tác, vừa đi học cùng với những hạn chế về kiến thức và kinh nghiệm nên không thể tránh khỏi thiếu sót nhất định mà bản thân chưa thấy được, tác giả rất mong được sự góp ý của quý thầy, cô giáo và các bạn đồng nghiệp để luận văn và những nghiên cứu tiếp theo được hoàn chỉnh hơn. Tác giả xin chân thành cảm ơn! MỤC LỤC Nội dung Trang Mở đầu 1 Chương 1 - Tổng quan về phân cụm dữ liệu 3 1.1. Phân cụm dữ liệu 3 1.2. Ứng dụng và yêu cầu của thuật toán phân cụm dữ liệu 5 1.3. Các kiểu dữ liệu trong phân cụm 11 1.4. Phép đo độ tương tự và khoảng cách đối với các kiểu dữ liệu 14 1.5. Một số thuật toán phân cụm 21 Chương 2 - Phân cụm đồng thời 25 2.1. Vấn đề phân cụm đồng thời - Biclustering 25 2.2. Phân loại các khối kết quả của phân cụm đồng thời 29 2.3. Cấu trúc các khối kết quả của phân cụm đồng thời 31 2.4. Thuật toán phân cụm đồng thời 35 2.4.1. Tìm hiểu thuật toán phân cụm đồng thời theo từng loại 35 khối kết quả 2.4.2. Thuật toán của Hartigan 42 2.4.3. Thuật toán của Cheng & Church 45 2.4.4. Thuật toán Bimax 60 Chương 3 - Ứng dụng của phân cụm đồng thời 66 3.1. Ứng dụng của phân cụm đồng thời 66 3.2. Hoạt động thực nghiệm 68 Kết luận 78 Danh mục tài liệu tham khảo 80 DANH MỤC CÁC HÌNH Nội dung Hình 1.1. Ví dụ về phân cụm dữ liệu Số trang 3 Hình 1.2. Mô hình cấu trúc dữ liệu lưới 10 Hình 2.1. Ví dụ phân cụm đồng thời 26 Hình 2.2. Minh họa ma trận dữ liệu 27 Hình 2.3. Phân loại các khối kết quả của phân cụm đồng thời - 30 Biclusters Hình 2.4: Cấu trúc các khối kết quả của phân cụm đồng thời 31 Hình 2.5. Chuỗi các giai đoạn chia tách của thuật toán của 44 Hartigan Hình 2.6. Ví dụ ma trận biểu hiện và một ma trận con là bicluster 46 Hình 2.7. Ví dụ một ma trận con (bicluster) nhất quán hoàn hảo 47 Hình 2.8. Biểu đồ biểu diễn mức độ biểu hiện của gen theo từng 48 điều kiện Hình 2.9. Ví dụ ma trận biểu hiện biến đổi logarit 49 Hình 2.10. Biểu đồ biểu diễn mức độ biểu hiện của gen theo từng 50 điều kiện (theo dữ liệu ma trận logarit) Hình 2.11. Biểu đồ biểu hiện gien và giá trị MSR tương ứng 54 Hình 2.12. Minh họa hai vectơ nghịch đảo nhau 57 Hình 2.13. Ví dụ một ma trận nhị phân 62 Hình 2.14. Sắp xếp lại hàng và cột theo thuật toán Bimax 63 Hình 2.15. Các ma trận con tiếp tục được xử lý lặp theo thuật toán 64 Bimax Hình 3.1. Ma trận dữ liệu đầu vào 69 Hình 3.2. Hình ảnh ma trận dữ liệu đầu vào được tô màu 70 Hình 3.3. Hình ảnh Bicluster 25x6 tìm thấy bởi thuật toán Bimax 70 Hình 3.4. Hình ảnh Bicluster 19x7 tìm thấy bởi thuật toán Bimax 71 Hình 3.5. Hình ảnh Bicluster 37x19 tìm thấy bởi thuật toán Cheng 71 & Church Hình 3.6. Hình ảnh Bicluster 33x20 tìm thấy bởi thuật toán Cheng 72 & Church Hình 3.7. Thời gian chạy của một số thuật toán phân cụm đồng 72 thời Hình 3.8. Thực nghiệm thuật toán Cheng & Church với 74 Hình 3.9. Thực nghiệm thuật toán Cheng & Church với 75 Hình 3.10. Thực nghiệm thuật toán Cheng & Church với 76 Hình 3.11. Thực nghiệm thuật toán Cheng & Church với 76 DANH MỤC CÁC BẢNG Nội dung Số trang Bảng 1.1. Bảng tham số 19 Bảng 2.1. Tổng hợp các thuật toán phân cụm đồng thời 42 Bảng 3.1. Tính toán chỉ số Jaccard một số kết quả phân cụm đồng 73 thời Bảng 3.2. Tính toán giá trị phương sai một số thuật toán phân cụm đồng thời 73 MỞ ĐẦU Việc phân tích dữ liệu biểu hiện gene, mà cụ thể là phân nhóm các gene có sự biểu hiện giống nhau trong từng thời điểm thành các nhóm (cluster) được thực hiện bởi các thuật toán phân cụm (clustering methods). Các thuật toán này thường tìm cách nhóm các gene có sự biểu hiện phụ thuộc nhau trên toàn bộ các điều kiện thí nghiệm. Tuy nhiên, trên thực tế các gene thường chỉ thể hiện phụ thuộc với nhau trên một số điều kiện nào đó và độc lập với nhau trong điều kiện khác. Điều này dẫn đến một hạn chế rất lớn của các thuật toán clustering là không thể tìm ra được các gene chỉ thể hiện giống nhau trên một số điều kiện thí nghiệm. Để khắc phục hạn chế này, các nhà khoa học đã đề xuất một phương pháp phân cụm mới có tên là biclustering (hoặc coclustering). Các thuật toán biclustering sẽ tìm cách phân cụm đồng thời trên các hàng (gene) và cột (condition) của ma trận dữ liệu biểu hiện gene nhằm tìm ra các ma trận con thoả mãn một số tiêu chí đặt ra, từ đó có thể giúp chúng ta hiểu thêm các tiến trình sinh học giữa các gene trong các cá thể. Nhưng gần như tất cả các phương pháp tiếp cận đến nay là heuristic và không đảm bảo để tìm giải pháp tối ưu. Trong trường hợp dữ liệu biểu hiện gene theo chuỗi thời gian, thì các mẫu sinh học thường được đo theo một thời điểm nhất định nhằm quan sát các tiến trình sinh học xảy ra trong các cá thể. Vì vậy, việc tìm ra các mẫu có thể hiện giống nhau trong một khoảng thời gian liên tục nào đó, có thể hình dung như chúng vừa hoàn thành một tiến trình sinh học, hoặc một giai đoạn chức năng sinh học nào đó. Việc phân tích trên dữ liệu thể hiện gene cho phép hiểu được cơ chế điều khiển gene và tương tác giữa chúng. Các mẫu dữ liệu này có thể coi như là một bicluster gồm các hàng và các cột trong ma trận. Vì lý do đó, tác giả lựa chọn đề tài: “Thuật toán phân cụm đồng thời và ứng dụng” là hướng nghiên cứu cho luận văn của mình. 1 Trong luận văn này, tác giả đặt mục tiêu như sau: - Nghiên cứu những nội dung liên quan tới phân cụm dữ liệu, một số tư tưởng và thuật toán cơ bản,.... - Nghiên cứu một số thuật toán phân cụm đồng thời đã được công bố. - Ứng dụng một số thuật toán biclustering vào tập dữ liệu thực cụ thể, phân tích và đánh giá các cụm bicluster thu được. Để hướng tới mục tiêu trên, tác giả đã thu thập và tìm đọc các tài liệu, tổng hợp các nội dung lý thuyết, thực hiện việc phân tích, nghiên cứu các công trình của các nhà khoa học đã công bố trước đây theo từng bước: - Nghiên cứu lý thuyết cơ bản về phân cụm dữ liệu - Nghiên cứu thuật toán phân cụm đồng thời. - Nghiên cứu dữ liệu biểu hiện gene, một số lĩnh vực, bài toán mà phân cụm đồng thời đã được áp dụng. - Áp dụng một số thuật toán phân cụm đồng thời (biclustering) trên bộ dữ liệu thực để thực nghiệm và đối chứng. Sau quá trình nghiên cứu, tác giả đã hoàn thành bản luận văn của mình, nội dung luận văn được trình bày trong 3 chương như sau: Chương 1: Tổng quan về phân cụm dữ liệu. Trong chương này trình bày tổng quan về hoạt động phân cụm dữ liệu, một số phương pháp phân cụm dữ liệu phổ biến như phân cụm phân hoạch, phân cụm phân cấp, phân cụm dựa trên mật độ,... Chương 2: Phân cụm đồng thời. Trong chương này trình bày về một số loại hình, cấu trúc của các bicluster có thể tồn tại trong cơ sở dữ liệu, trình bày một số thuật toán tìm kiếm các bicluster trong đó, tóm tắt một số kết nghiên cứu các thuật toán này. Chương 3: Ứng dụng của phân cụm đồng thời. Trong chương này trình bày những ứng dụng thực tế đã từng thực hiện bởi các nghiên cứu trước đây. Áp dụng thuật toán phân cụm đồng thời (biclustering) vào bộ dữ liệu thực, xem xét, tìm hiểu các bicluster thu được. 2 CHƯƠNG 1 TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU 1.1. Phân cụm dữ liệu Khai phá dữ liệu (Data mining) là quá trình trích xuất các thông tin có giá trị tiềm ẩn bên trong tập dữ liệu lớn được lưu trữ trong các cơ sở dữ liệu, kho dữ liệu. Các nhà khoa học xác định: “Phân cụm dữ liệu là một kỹ thuật trong khai phá dữ liệu, nhằm tìm kiếm, phát hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn, quan trọng trong tập dữ liệu lớn, từ đó cung cấp thông tin, tri thức hữu ích cho việc ra quyết định”. Phân cụm là quá trình nhóm các điểm dữ liệu trong cơ sở dữ liệu thành các cụm sao cho những điểm dữ liệu trong cùng một cụm có độ tương đồng lớn và những điểm không cùng một cụm có sự tương đồng là rất nhỏ. Một cụm các đối tượng dữ liệu có thể xem như là một nhóm trong nhiều ứng dụng, ví dụ: mô hình về phân cụm các trường dựa trên tiêu chuẩn về thu nhập và số nợ. Cụm 1 là cụm những người thu nhập cao, số nợ nhiều. Cụm 2 gồm những người thu nhập cao nhưng nợ ít. Cụm 3 gồm những đối tượng thu nhập ít nhưng nợ nhiều. Cụm 1 Cụm 3 Nợ Cụm 2 Thu nhập Hình 1.1. Ví dụ về phân cụm dữ liệu 3 Quá trình phân cụm là quá trình tìm ra các đối tượng trong cơ sở dữ liệu một cách tự động. Không giống như phân lớp (classification), phân cụm không cần những thông tin được xác định trước. Nói cách khác, phân cụm là phương pháp học từ quan sát (learning from obversation) hay còn gọi là học không giám sát (unsupervised learning or automatic classfication) trong trí tuệ nhân tạo. Phân cụm đặc biệt hiệu quả khi không biết về thông tin các cụm, hoặc khi ta quan tâm tới các thuộc tính của cụm mà chưa biết hoặc biết rất ít về các thông tin đó. Đã có rất nhiều thuật toán cũng như hệ thống được phát triển cho bài toán phân cụm trong cơ sở dữ liệu lớn. Sự phát triển của lĩnh vực này đã được áp dụng vào nhiều lĩnh vực ứng dụng như xử lý ảnh, nhận dạng, đánh giá kinh doanh... Sự đa dạng của thuật toán phân cụm là do sự khác nhau của những ứng dụng thực tế cũng dẫn tới những yêu cầu về dữ liệu khác nhau và đòi hỏi những thuật toán phân cụm khác nhau. Một trong những câu hỏi lớn đặt ra trong bài toán phân cụm là đo độ tương đồng không gian giữa các đối tượng dữ liệu (spatial similarity). Trong dữ liệu không gian thì độ đo tương đồng được xem như sự quan hệ về vị trí không gian giữa các đối tượng dữ liệu. Nói cách khác thì hai đối tượng dữ liệu được gọi là tương đồng nếu “khoảng cách không gian” giữa chúng là nhỏ. Một trong những phương pháp đo độ tương đồng giữa hai đối tượng là bằng nghịch đảo của hàm không tương đồng (dissimilarity function). Hàm không tương đồng là hàm dựa trên những thuộc tính không gian của các đối tượng dữ liệu như: toạ độ của các đối tượng, độ cao của các đối tượng... Trong nhiều trường hợp thì hàm không tương đồng được xem như là hàm khoảng cách không gian giữa các đối tượng như hàm khoảng cách Euclid, hàm khoảng cách Manhattan, hàm khoảng cách Minkowski,... Bài toán phân cụm là quá trình nhóm một cơ sở dữ liệu thành những nhóm đối tượng dữ liệu phục vụ cho mục đích cụ thể của từng ứng dụng thực tế. Không có một thuật toán phân cụm nào là tốt nhất và thích hợp cho tất cả 4 mọi ứng dụng mà với mỗi ứng dụng khác nhau thì người sử dụng phải lựa chọn ra một thuật toán phân cụm cụ thể thích ứng với ứng dụng đó. Kết quả đánh giá cho từng thuật toán cũng phụ thuộc vào những yêu cầu của từng ứng dụng. 1.2. Ứng dụng và yêu cầu của thuật toán phân cụm dữ liệu 1.2.1. Ứng dụng của phân cụm dữ liệu Phân cụm dữ liệu đã và đang được nghiên cứu, ứng dụng trong nhiều lĩnh vực khác nhau ở các nước trên thế giới, tại Việt Nam kỹ thuật này tương đối còn mới mẻ tuy nhiên cũng đang được nghiên cứu và dần đưa vào ứng dụng tại nhiều lĩnh vực như: - Quy hoạch đô thị: Nhận dạng các nhóm nhà theo kiểu và vị trí địa lí,... nhằm cung cấp thông tin cho quy hoạch đô thị; - Nghiên cứu trái đất: Phân cụm để theo dõi các tâm động đất nhằm cung cấp thông tin cho nhận dạng các vùng nguy hiểm; - Thương mại: Tìm kiếm nhóm các khách hàng quan trọng có đặc trưng tương đồng từ các bản ghi mua bán trong cơ sở dữ liệu mua, bán hàng; - Sinh học: Phân loại các gene với các chức năng tương đồng và thu được các cấu trúc trong mẫu; - Thư viện: Theo dõi người đọc, sách, dự đoán nhu cầu của độc giả.. - Bảo hiểm: Phân nhóm các đối tượng sử dụng bảo hiểm và các dịch vụ tài chính, dự đoán xu hướng của khách hàng, phát hiện gian lận tài chính; - Phân loại tài liệu, phân loại người dùng web... 1.2.2. Yêu cầu về thuật toán phân cụm dữ liệu Theo các nghiên cứu cho thấy hiện nay chưa có một phương pháp phân cụm tổng quát nào có thể giải quyết trọn vẹn cho tất cả các dạng cấu trúc cơ sở dữ liệu. Hơn nữa, các phương pháp phân cụm cần có cách thức biểu diễn cấu trúc của cơ sở dữ liệu, với mỗi cách thức biểu diễn khác nhau sẽ có tương ứng thuật toán phân cụm phù hợp. Vì vậy, phân cụm dữ liệu vẫn đang là một vấn đề khó và mở vì phải giải quyết nhiều vấn đề cơ bản một cách trọn vẹn và phù hợp với nhiều dạng dữ liệu khác nhau, đặc biệt là với kho dữ liệu hỗn hợp đang 5 ngày càng tăng và đây cũng là một trong những thách thức lớn trong lĩnh vực khai phá dữ liệu. Vậy phân cụm dữ liệu là một thách thức trong lĩnh vực nghiên cứu, vì những ứng dụng tiềm năng của chúng được đưa ra ngay chính trong những yêu cầu đặc biệt của chúng. Do đặc thù của của cơ sở dữ liệu là lớn, phức tạp, và có dữ liệu nhiễu nên những thuật toán phân cụm được áp dụng phải thoả mãn những yêu cầu sau: - Thuật toán phải hiệu quả và thời gian chạy phải là tăng tuyến tính theo kích thước của dữ liệu; - Thuật toán phải xử lý và áp dụng được với cơ sở dữ liệu nhiều nhiễu, phức tạp gồm cả dữ liệu không gian, phi không gian, dữ liệu số, phi số, kiểu nhị phân, dữ liệu định danh, hạng mục, thích nghi với kiểu dữ liệu hỗn hợp. - Thuật toán phải có khả năng xác định được những cụm với hình dáng bất kỳ bao gồm cả những cụm có hình dạng lồng nhau, cụm có hình dạng lõm, hình cầu, hình que... - Tối thiểu lượng tri thức cần cho xác định các tham số đầu vào. Do các giá trị đầu vào thường ảnh hưởng rất lớn đến thuật toán phân cụm và rất phức tạp để xác định các giá trị vào thích hợp đối với các cơ sở dữ liệu lớn. - Thuật toán phải thực hiện với mọi thứ tự đầu vào dữ liệu. Nói cách khác kết quả của thuật toán nên độc lập với dữ liệu đầu vào (Cùng một tập dữ liệu, khi đưa vào xử lý cho thuật toán phân cụm dữ liệu với các thứ tự vào của các đối tượng dữ liệu ở các lần thực hiện khác nhau thì không ảnh hưởng lớn đến kết quả phân cụm); - Thuật toán không đòi hỏi những tri thức về cơ sở dữ liệu từ người dùng; - Thuật toán phải làm việc được với cơ sở dữ liệu chứa nhiều lớp đối tượng dữ liệu phức tạp và có tính chất khác nhau; - Thuật toán phải thích nghi với dữ liệu đa chiều: Thuật toán có khả năng áp dụng hiệu quả cho dữ liệu có số khác chiều nhau; 6 - Thuật toán phải dễ hiểu, dễ cài đặt và khả thi: Người sử dụng có thể chờ đợi những kết quả phân cụm dễ hiểu, dễ lý giải và dễ sử dụng. Nghĩa là, sự phân cụm có thể cần được giải thích ý nghĩa và ứng dụng rõ ràng. Việc nghiên cứu cách để một ứng dụng đạt được mục tiêu rất quan trọng có thể gây ảnh hưởng tới sự lựa chọn các phương pháp phân cụm. 1.2.3. Các hướng tiếp cận của bài toán phân cụm dữ liệu Các kỹ thuật phân cụm có rất nhiều cách tiếp cận và ứng dụng trong thực tế, nó hướng tới hai mục tiêu chung đó là chất lượng của các cụm khám phá được và tốc độ thực hiện của thuật toán. Hiện nay, các kỹ thuật phân cụm có thể phân loại theo các cách tiếp cận chính sau. 1.2.3.1. Phương pháp phân cụm phân hoạch Phương pháp phân cụm phân hoạch nhằm phân một tập dữ liệu có n phần tử cho trước thành k nhóm dữ liệu sao cho: mỗi phần tử dữ liệu chỉ thuộc về một nhóm dữ liệu và mỗi nhóm dữ liệu có tối thiểu ít nhất một phần tử dữ liệu. Các thuật toán phân hoạch dữ liệu có độ phức tạp rất lớn khi xác định nghiệm tối ưu toàn cục cho vấn đề phân cụm dữ liệu, do nó phải tìm kiếm tất cả các cách phân hoạch có thể được. Chính vì vậy, trên thực tế người ta thường đi tìm giải pháp tối ưu cục bộ cho vấn đề này bằng cách sử dụng một hàm tiêu chuẩn để đánh giá chất lượng của các cụm cũng như để hướng dẫn cho quá trình tìm kiếm phân hoạch dữ liệu. Với chiến lược này, thông thường người thực hiện bắt đầu khởi tạo một phân hoạch ban đầu cho tập dữ liệu theo phép ngẫu nhiên hoặc theo heuristic và liên tục tinh chỉnh nó cho đến khi thu được một phân hoạch mong muốn, thoả mãn ràng buộc cho trước. Các thuật toán phân cụm phân hoạch cố gắng cải tiến tiêu chuẩn phân cụm, bằng cách tính các giá trị đo độ tương tự giữa các đối tượng dữ liệu và sắp xếp các giá trị này, sau đó thuật toán lựa chọn một giá trị trong dãy sắp xếp sao cho hàm tiêu chuẩn đạt giá trị tối thiểu. Như vậy, ý tưởng chính của thuật toán phân cụm phân hoạch tối ưu cục bộ là sử dụng chiến lược tham lam (Greedy) để tìm kiếm nghiệm. Một số thuật toán phân cụm phân hoạch điển hình như K-means, PAM, CLARA, CLARANS,.... 7 1.2.3.2. Phương pháp phân cụm phân cấp Phương pháp này xây dựng một phân cấp trên cơ sở các đối tượng dữ liệu đang xem xét. Nghĩa là sắp xếp một tập dữ liệu đã cho thành một cấu trúc có dạng hình cây, cây phân cấp này được xây dựng theo kỹ thuật đệ quy có hai cách tiếp cận phổ biến của kỹ thuật này đó là: - Hòa nhập nhóm (thường được gọi là tiếp cận Bottom-Up): Phương pháp này bắt đầu với mỗi đối tượng được khởi tạo tương ứng vói các cụm riêng biệt, sau đó tiến hành nhóm các đối tượng theo một độ đo tương tự (như khoảng cách giữa hai trung tâm của hai nhóm), quá trình này được thực hiện cho đến khi tất cả các nhóm được hòa nhập vào một nhóm (mức cao nhất của cây phân cấp) hoặc cho đến khi các điều kiện kết thúc thỏa mãn. Như vậy, cách tiếp cận này sử dụng chiến lược tham lam trong quá trình phân cụm. - Phân chia nhóm (thường được gọi là tiếp cận Top-Down): Bắt đầu với trạng thái là tất cả các đối tượng được xếp trong cùng một cụm. Mỗi vòng lặp thành công, một cụm được tách thành các cụm nhỏ hơn theo giá trị của một phép đo độ tương tự nào đó cho đến khi mỗi đối tượng là một cụm, hoặc cho đến khi điều kiện dừng thỏa mãn. Cách tiếp cận này sử dụng chiến lược chia để trị trong quá trình phân cụm. Một số thuật toán phân cụm phân cấp điển hình như CURE, BIRCH,... Thực tế áp dụng, có nhiều trường hợp người ta kết hợp cả hai phương pháp phân cụm phân hoạch và phương phân cụm phân cấp, nghĩa là kết quả thu được của phương pháp phân cấp có thể cải tiến thông quan bước phân cụm phân hoạch. Phân cụm phân hoạch và phân cụm phân cấp là hai phương pháp phân cụm dữ liệu cổ điển, hiện nay đã có nhiều thuật toán cải tiến dựa trên hai phương pháp này đã được áp dụng phổ biến trong khai phá dữ liệu. 1.2.3.3. Phương pháp phân cụm dựa trên mật độ Phương pháp này nhóm các đối tượng theo hàm mật độ xác định. Mật độ được định nghĩa như là số các đối tượng lân cận của một đối tượng dữ liệu theo một ngưỡng nào đó. Trong cách tiếp cận này, khi một cụm dữ liệu đã xác định 8 thì nó tiếp tục được phát triển thêm các đối tượng dữ liệu mới miễn là số các đối tượng lân cận của các đối tượng này phải lớn hơn một ngưỡng đã được xác định trước. Phương pháp phân cụm dựa vào mật độ của các đối tượng để xác định các cụm dữ liệu có thể phát hiện ra các cụm dữ liệu với hình thù bất kỳ. Kỹ thuật này có thể khắc phục được các phân tử ngoại lai hoặc giá trị nhiễu rất tốt, tuy vậy việc xác định các tham số mật độ của thuật toán rất khó khăn, trong khi các tham số này lại có tác động rất lớn đến kết quả phân cụm dữ liệu. Một số thuật toán phân cụm dữ liệu dựa trên mật độ điển hình như DBSCAN, OPTICS,... 1.2.3.4. Phương pháp phân cụm dựa trên lưới Kỹ thuật phân cụm dựa trên mật độ không thích hợp với dữ liệu nhiều chiều, để giải quyết cho đòi hỏi này, người ta đã dử dụng phương pháp phân cụm dựa trên lưới. Đây là phương pháp dựa trên cấu trúc dữ liệu lưới để phân cụm dữ liệu, phương pháp này chủ yếu tập trung áp dụng cho lớp dữ liệu không gian. Thí dụ như dữ liệu được biểu diễn dưới dạng cấu trúc hình học của đối tượng trong không gian cùng với các quan hệ, các thuộc tính, các hoạt động của chúng. Mục tiêu của phương pháp này là lượng hoá tập dữ liệu thành các ô (cell), các cell này tạo thành cấu trúc dữ liệu lưới, sau đó các thao tác phân cụm dữ liệu làm việc với các đối tượng trong từng cell này. Cách tiếp cận dựa trên lưới này không di chuyển các đối tượng trong các cell mà xây dựng nhiều mức phân cấp của nhóm các đối tượng trong một cell. Trong ngữ cảnh này, phương pháp này gần giống với phương pháp phân cụm phân cấp nhưng chỉ có điều chúng không trộn các cell. Do vậy các cụm không dựa trên độ đo khoảng cách (hay còn gọi là độ đo tương tự đối với các dữ liệu không gian) mà nó được quyết định bởi một tham số xác định trước. Ưu điểm của phương pháp phân cụm dữ liệu dựa trên lưới là thời gian xử lý nhanh và độc lập vói số đối tượng dữ liệu trong tập dữ liệu ban đầu, thay vào đó là chúng phụ thuộc vào số cell trong mỗi chiều của không gian lưới. Một thí dụ về cấu trúc dữ liệu lưới chứa các cell trong không gian như hình sau: 9 Hình 1.2. Mô hình cấu trúc dữ liệu lưới Một số thuật toán phân cụm dữ liệu dựa trên cấu trúc lưới điển hình: Sting, WaveCluster,... 1.2.3.5. Phương pháp phân cụm dựa trên mô hình Phương pháp này cố gắng khám phá các phép xấp xỉ tốt của các tham số mô hình sao cho khớp với dữ liệu một cách tốt nhất. Chúng có thể sử đụng chiến lược phân cụm phân hoạch hoặc chiến lược phân cụm phân cấp, dựa trên cấu trúc hoặc mô hình mà chúng giả định về tập dữ liệu và cách mà chúng tinh chỉnh các mô hình này để nhận dạng ra các phân hoạch. Phương pháp phân cụm dữ liệu dựa trên mô hình cố gắng khớp giữa dữ liệu với mô hình toán học, nó dựa trên giả định rằng dữ liệu được tạo ra bằng hỗn hợp phân phối xác suất cơ bản. Các thuật toán phân cụm dựa trên mô hình có hai tiếp cận chính: mô hình thống kê và mạng Nơron. Phương pháp này gần giống với phương pháp dựa trên mật độ, bởi vì chúng phát triển các cụm riêng biệt nhằm cải tiến các mô hình đã được xác định trước đó, nhưng đôi khi nó không bắt đầu với một số cụm cố định và không sử dụng cùng một khái niệm mật độ cho các cụm. 1.2.3.6. Phương pháp phân cụm có dữ liệu ràng buộc Sự phát triển của phân cụm dữ liệu không gian trên cơ sở dữ liệu lớn đã cung cấp nhiều công cụ tiện lợi cho việc phân tích thông tin địa lí, tuy nhiên hầu hết các thuật toán này cung cấp rất ít cách thức cho người dùng để xác định các ràng buộc trong thế giới thực cần phải được thỏa mãn trong quá trình phân 10 cụm. Để phân cụm dữ liệu không gian hiệu quả hơn, các nghiên cứu bổ sung cần được thực hiện để cung cấp cho người dùng khả năng kết hợp các ràng buộc trong thuật toán phân cụm. Hiện nay, các phương pháp phân cụm trên đã, đang được phát triển và áp dụng nhiều trong các lĩnh vực khác nhau và đã có một số nhánh nghiên cứu được phát triển trên cơ sở của các phương pháp đó như: - Phân cụm thống kê: Dựa trên các khái niệm phân tích thống kê, nhánh nghiên cứu này sử dụng các độ đo tương tự để phân hoạch các đối tượng, nhưng chúng chỉ áp dụng cho các dữ liệu có thuộc tính số. - Phân cụm mờ: Sử dụng kỹ thuật mờ để phân cụm dữ liệu, các thuật toán thuộc loại này chia ra lược đồ phân cụm thích hợp với tất cả các hoạt động đời sống hàng ngày, chúng chỉ xử lí các dữ liệu thực hiện không chắc chắn. - Phân cụm mạng Kohonen: Loại phân cụm này dựa trên khái niệm của các mạng Nơron. Mạng Kohonen có tầng Nơron vào và các tầng Nơron ra. Mỗi Nơron của tầng vào tương ứng với mỗi thuộc tính của bản ghi, mỗi một Nơron vào kết nối với tất cả các Nơron của tầng ra. Mỗi liên kết được gắn liền với một trọng số nhằm xác định vị trí của Nơron ra tương ứng. Các kỹ thuật phân cụm dữ liệu trình bày ở trên đã được sử dụng rộng rãi trong thực tế, thế nhưng hầu hết chúng chỉ nhằm áp dụng cho tập dữ liệu với cùng một kiểu thuộc tính. Vì vậy, việc phân cụm dữ liệu trên tập dữ liệu có kiểu hỗn hợp là một vấn đề đặt ra trong khai phá dữ liệu trong giai đoạn hiện nay. 1.3. Các kiểu dữ liệu trong phân cụm Trong phân cụm, các đối tượng dữ liệu thường được diễn tả dưới dạng các đặc tính hay còn gọi là thuộc tính (Khái niệm “các kiểu dữ liệu” và “các kiểu thuộc tính dữ liệu” được xem là tương đương với nhau). Các thuộc tính này là các tham số để giải quyết vấn đề phân cụm và sự lựa chọn chúng có tác động đáng kể đến kết quả phân cụm. Phân loại các kiểu thuộc tính khác nhau là vấn đề cần giải quyết đối với hầu hết các tập dữ liệu nhằm cung cấp các 11 phương tiện thuận lợi để nhận dạng sự khác nhau của các phần tử dữ liệu. Các thuật toán phân cụm thường sử dụng một trong hai cấu trúc dữ liệu sau: - Ma trận dữ liệu (Data matrix): là mảng n hàng, p cột, trong đó p là số thuộc tính của mỗi đối tượng. Mỗi hàng biểu diễn một đối tượng, các phần tử trong mỗi hàng chỉ giá trị thuộc tính tương ứng của đối tượng đó. Mảng được cho như sau: 𝑥11 … 𝑥𝑖1 … [𝑥𝑛1 … 𝑥1𝑓 … … … 𝑥1𝑓 … … … 𝑥𝑛𝑓 … … … … … 𝑥1𝑝 … 𝑥1𝑝 … 𝑥𝑛𝑝 ] - Ma trận phi tương tự (Dissimilarity matrix): là mảng n hàng, n cột. Phần tử d(i,j) chứa khoảng cách hay độ khác biệt giữa các đối tượng i và đối tượng j; d(i,j) là một số không âm, trong đó nếu d(i,j) xấp xỉ 0 thì hai đối tượng i và j là khá “gần” nhau, nếu d(i,j) càng lớn thì hai đối tượng i, j khá khác nhau. Do d(i,i) = d(j,j) = 0 nên ta có thể biểu diễn ma trận phi tương tự như sau: 0 𝑑(2,1) 0 𝑑(3,1) 𝑑(3,2) … … [𝑑(𝑛, 1) 𝑑(𝑛, 2) 0 … … … … … 0] Phần lớn các thuật toán phân cụm sử dụng cấu trúc ma trận phi tương tự. Do vậy, nếu dữ liệu cần phân cụm được tổ chức dưới dạng ma trận dữ liệu thì cần biến đổi về dạng ma trận phi tương tự trước khi tiến hành phân cụm. Có hai đặc trưng để phân loại: kích thước miền và hệ đo. Cho một CSDL D chứa n đối tượng trong không gian k chiều; X, Y, Z là các đối tượng thuộc D: X = (x1,x2,...,xk); Y = (y1,...,yk); Z = (z1,z2,...zk) (trong đó xi, yi, zi với i = 1,.., k) là các đặc trưng hoặc thuộc tính tương ứng của các đối tượng X, Y, Z; như vậy sẽ có các kiểu dữ liệu sau: + Kiểu dữ liệu dựa trên kích thước miền 12 - Thuộc tính liên tục: Nếu miền giá trị của nó là vô hạn không đếm được, nghĩa là giữa hai giá trị tồn tại vô số giá trị khác (ví dụ, các thuộc tính màu, nhiệt độ hoặc cường độ âm thanh,...) - Thuộc tính rời rạc: Nếu miền giá trị của nó là tập hữu hạn, đếm được (ví dụ: các thuộc tính số,...) trường hợp đặc biệt của thuộc tính rời rạc là thuộc tính nhị phân mà miền giá trị chỉ có hai phần tử (ví dụ: Yes/No, True/False, On/Off,...) + Kiểu dữ liệu dựa trên hệ đo - Thuộc tính định danh: Là dạng thuộc tính khái quát hoá của thuộc tính nhị phân, trong đó có miền giá trị là rời rạc, không phân biệt thứ tự và có nhiều hơn hai phần tử. Nếu x và y là hai đối tượng thuộc tính thì chỉ có thể xác định là x ≠ y hoặc x = y. - Thuộc tính có thứ tự: Là thuộc tính định danh nhưng có thêm tính thứ tự nhưng chúng không được định lượng. Nếu x và y là hai thuộc tính thứ tự thì có thể xác định là x ≠ y hoặc x = y hoặc x > y hoặc x < y. - Thuộc tính khoảng: để đo các giá trị theo xấp xỉ tuyến tính, với thuộc tính khoảng có thể xác định một thuộc tính là đứng trước hoặc đứng sau thuộc tính khác với một khoảng là bao nhiêu. Nếu xi > yi thì có thể nói xi cách yi một khoảng xi - yi tương ứng với thuộc tính thứ i. Việc lựa chọn đơn vị đo cho các thuộc tính cũng ảnh hưởng đến chất lượng phân cụm. Nếu đơn vị độ đo của một thuộc tính càng được chia nhỏ, thì khoảng cách xác định của thuộc tính đó càng lớn và ảnh hưởng nhiều hơn đến kết quả phân cụm. Để tránh phụ thuộc vào việc lựa chọn đơn vị đo, dữ liệu cần được chuẩn hóa. Việc chuẩn hóa sẽ gán cho tất cả các thuộc tính một trọng số bằng nhau. Tuy nhiên, trong nhiều trường hợp người sử dụng có thể thay đổi trọng số cho các thuộc tính ưu tiên. Để chuẩn hóa các độ đo, một cách làm phổ biến là biến đổi các thuộc tính về dạng không có đơn vị đo. Giả sử đối với các thuộc tính f, ta thực hiện như sau: 13
- Xem thêm -

Tài liệu liên quan