- DOI:10.22144/ctu.jsi.2017.006 GIẢI THUẬT ƯỚC LƯỢNG SỐ CỤM DỮ LIỆU CẢI TIẾN CHO TẬP DỮ LIỆU LỚN Dương Văn Hiếu, Trần Huy Long và Phạm Ngọc Giàu. - Cây phủ tối thiểu, đồ thị tối ưu, tập dữ liệu lớn, tế bào hóa tập dữ liệu, ước lượng số cụm dữ liệu. - Bài báo này trình bày một giải thuật ước lượng số cụm dữ liệu cải tiến dùng để ước lượng số cụm dữ liệu của tập dữ liệu lớn. - Thuật toán cải tiến cho kết quả ổn định hơn so với thuật toán ban đầu khi xét trên cùng các tập dữ liệu và trong cùng một điều kiện thực nghiệm.. - Giải thuật ước lượng số cụm dữ liệu cải tiến cho tập dữ liệu lớn. - Trong thời đại cuộc cách mạng công nghiệp lần thứ tư, hầu hết dữ liệu đều được số hóa. - Quá trình số hóa dữ liệu đã tạo ra một cuộc cách mạng về dữ liệu mà người ta thường gọi là big data hay dữ liệu lớn. - Big data không chỉ là dữ liệu lớn về dung lượng mà còn đa dạng về cấu trúc, định dạng, nguồn phát sinh, mức độ thay đổi. - Trong lĩnh vực khai khoáng dữ liệu và khoa học dữ liệu, phân cụm dữ liệu được xem là công cụ quan trọng trong phân tích và xử lý các tập dữ liệu lớn và được ứng dụng nhiều trong các lĩnh vực kinh doanh, công nghệ, khoa học, giáo dục. - Dựa vào phương pháp phân cụm, các giải thuật phân cụm dữ liệu được chia thành 5 nhóm như trong Hình 1 (Fahad et al., 2014).. - Hiện tại, có nhiều định nghĩa khác nhau về tập dữ liệu lớn, một định nghĩa được nhiều người chấp nhận và sử dụng là “tập dữ liệu lớn là tập dữ liệu mà chúng ta không thể xử lý bằng những phương pháp tuyền thống”. - Các tập dữ liệu mà Jesus et al.. - (2017) đã sử dụng trong các thí nghiệm có số lượng từ 1.025.000 mẫu tin đến cũng được xem là các tập dữ liệu lớn.. - Trong bài báo này, các tập dữ liệu được sử dụng để thí nghiệm có số lượng từ 300.000 mẫu tin đến mẫu tin. - Trong hoàn cảnh tối ưu hóa các thuật toán thì một số tập dữ liệu được sử dụng trong bài báo này đã được chấp nhận là các tập dữ liệu lớn (Van Hieu and Phayung, 2016).. - Các thuật toán này phân chia một tập dữ liệu. - Vì K-Means là một thuật toán phân cụm dữ liệu rất thông dụng nên bày báo này chọn thuật toán K-Means để làm nền tảng cho giải thuật ước lượng số cụm dữ liệu.. - Input: Tập dữ liệu có đối tượng trong không gian chiều, số lượng nhóm cần phân chia là. - Output: Tâm của nhóm và danh sách các đối tượng dữ liệu thuộc vào từng nhóm.. - Gán các đối tượng dữ liệu. - Hình 2: Ví dụ về kết quả phân cụm Để phân chia một tập dữ liệu có phần tử thành nhóm thì các giải thuật phân nhóm cần được cung cấp giá trị của trước khi thực hiện việc phân nhóm.. - Đối với các tập dữ liệu nhỏ hoặc có từ 1 đến 2 thuộc tính thì việc ước lượng số cụm dữ liệu có thể được thực hiện thông qua các công cụ trực quan hóa dữ liệu. - Đối với các tập dữ liệu lớn và có nhiều hơn 2 thuộc tính thì có thể ước lượng cố cụm thông qua kiến thức chuyên gia về lĩnh vực của dữ liệu.. - Tuy nhiên, để ước lượng số cụm chính xác thì cần đến các giải thuật ước lượng số cụm dữ liệu.. - Tuy nhiên, các phương pháp đó khó áp dụng để hiện thực việc ước lượng số nhóm của các tập dữ liệu lớn khi thực hiện trên các máy tính cá nhân có cấu hình chuẩn vì lý do bộ nhớ khả dụng của máy tính cá nhân không thể đáp ứng được yêu cầu cấp phát và lưu trữ dữ liệu khi tính toán.. - Ví dụ: Cần ước lượng số cụm dữ liệu cho một tập dữ liệu có đối tượng dữ liệu.. - Trong trường hợp sử dụng kiểu dữ liệu float có kích thước 4 byte để lưu trữ giá trị số thập phân và kiểu dữ liệu unsigned char có kích thước 1 byte để lưu trữ giá trị số nguyên nhỏ. - Yêu cầu về dung lượng bộ nhớ để lưu trữ dữ liệu cần thiết liên quan đến quá trình ước lượng số cụm có thể được tính như Bảng 1.. - (Zhong et al Để cài đặt được thuật toán ước lượng số cụm dữ liệu theo phương pháp cây phủ tối thiểu thì cần phải giảm số đối tượng trong tập dữ liệu đến một giá trị nhất định tùy vào dung lượng khả dụng của bộ nhớ RAM.. - Mặt khác, có nhiều giải thuật ước lượng số cụm dữ liệu không đòi hỏi phải sử dụng dung lượng bộ nhớ lớn nhưng lại tốn rất nhiều thời gian khi thực hiện việc phân cụm như thuật toán QEM (Kolesnikov et al., 2015).. - Thuật toán ước lượng số cụm dữ liệu cho tập dữ liệu lớn dựa trên sự kết hợp giữa phương pháp cây phủ tối thiểu và phương pháp tế bào hóa (Cell- MST-Based) (Van Hieu và Phayung, 2015) được đề xuất và được xem như một giải pháp tốt cho việc ước lượng số cụm của các tập dữ liệu lớn được thiết kế để thực thi trên các máy tính cá nhân có cấu hình chuẩn (Texas Tech University, 2015).. - Kết quả thực nghiệm cho thấy thuật toán ước lượng số cụm dữ liệu Cell-MST-based cho kết quả tốt hơn rất nhiều khi so sánh với các thuật toán khác khi áp dụng cho các tập dữ liệu lớn. - Tuy nhiên, khi áp dụng cho một vài tập dữ liệu đặc biệt thì kết quả có thể không được ổn định. - Do đó, bài báo này trình bày một cách cải tiến thuật toán ước lượng số cụm dữ liệu Cell-MST-Based bằng cách áp dụng khái niệm khoảng cách có trọng số thay vì sử dụng khoảng cách Euclid. - Đóng góp của bài báo này là đề xuất khái niệm khoảng cách có trọng số giữa 2 đối tượng, đồng thời áp dụng khoảng cách có trọng số để cải tiến thuật toán ước lượng số cụm dữ liệu Cell-MST- Based để nhận được kết quả ổn định hơn cho một số tập dữ liệu đặc biệt.. - 2 THUẬT TOÁN ƯỚC LƯỢNG SỐ CỤM CELL-MST-BASED. - Phần này trình bày những nội dung chủ yếu về cơ sở lý thuyết có liên quan đến thuật toán ước lượng số cụm dữ liệu Cell-MST-Based. - Nội dung trình bày gồm phương pháp biến đổi tập dữ liệu lớn gồm đối tượng thành tập dữ liệu nhỏ gồm có tế bào, cách xây dựng đồ thị tối ưu từ tập tế bào, ước lượng số cụm dữ liệu bằng cây phủ tối thiểu, các chỉ số dùng để đánh giá kết quả phân cụm dữ liệu.. - Ví dụ là vector hoặc là đối tượng dữ liệu.. - 2.2 Chỉ số so sánh kết quả phân cụm Để xác định kết quả phân cụm dữ liệu là tốt hay chưa tốt, người ta thường sử dụng nhiều chỉ số khác nhau. - Đối với bài toán ước lượng số cụm dữ liệu kết hợp với việc phân cụm thì các chỉ số thường được sử dụng là chỉ số Dunn, Davies- Boudlin, Krzanowski-Lai, Calinski-Harabasz, Intra-Inter. - Tùy vào đặc điểm của các tập dữ liệu dùng để phân cụm hoặc ước lượng số cụm dữ liệu mà người ta chọn các chỉ số phù hợp.. - 2.3 Tế bào hóa tập dữ liệu lớn. - Đây là thuật toán biến đổi tập dữ liệu lớn thành tập tế bào có kích thước nhỏ hơn rất nhiều so với tập dữ liệu ban đầu đã được đề xuất cho các thuật toán xử lý tập dữ liệu lớn (Van Hieu và Phayung, 2015).. - Ánh xạ đối tượng dữ liệu vào tế bào Một tế bào dữ liệu được định nghĩa như một nhóm các đối tượng dữ liệu gần giống nhau.. - là tập dữ liệu gốc có đối tượng trong không gian chiều,. - là giá trị lớn nhất của các thuộc tính của các đối tượng dữ liệu. - Input: Tập dữ liệu , vector với 1. - Chuyển tập dữ liệu thành tập tế bào Mục đích của bước này là lấy địa chỉ của các tế bào. - Mỗi tế bào là một nhóm các đối tượng dữ liệu.. - Gọi là dung lượng khả dụng của bộ nhớ RAM, là kích thước của kiểu dữ liệu dùng để lưu trữ khoảng cách giữa các tế bào, giá trị của được xác định bằng biểu thức (11).. - (13) Thuật toán chuyển đổi tập dữ liệu thành tập tế bào được mô tả như sau:. - Thuật toán 3: Tế bào. - Input: Tập dữ liệu có đối tượng trong không gian chiều, là kích cỡ của kiểu dữ liệu dùng để lưu giá trị khoảng cách.. - 2.4 Xây dựng đồ thị tối ưu và ước lượng số cụm dữ liệu. - Mục đích của việc xây dựng đồ thị tối ưu là hạn chế việc cấp phát ô nhớ và lưu trữ những giá trị không cần thiết cho quá trình ước lượng số cụm dữ liệu. - Ước lượng số cụm dữ liệu. - Bước thứ 3 của thuật toán ước lượng số cụm dữ liệu Cell-MST-based là ước lượng số cụm dữ liệu kết hợp với phân cụm bằng thuật toán K-Means.. - cũng được xem là số cụm các tế bào và tương đương với số cụm dữ liệu của tập dữ liệu. - Tâm của từng cụm tế bào được xác định thông qua giá trị các thuộc tính của tế bào, địa chỉ này được ánh xạ ngược thành tâm của các cụm dữ liệu.. - Thuật toán phân cụm K-Means được sử dụng để phân cụm tập dữ liệu ban đầu , các chỉ số Dunn, Davies-Boudlin, Intra-Inter được tính tương ứng với từng giá trị. - là tâm ban đầu của các nhóm khi sử dụng thuật toán K- Means trên tập dữ liệu gốc . - a) Số cụm dữ liệu b) Số cây của rừng Hình 3: Ví dụ mối tương quan giữa số cụm dữ liệu và số cây 3 THUẬT TOÁN ƯỚC LƯỢNG SỐ CỤM. - DỮ LIỆU CẢI TIẾN WEIGHTED-CELL- MST-BASED. - Để cải thiện kết quả của thuật toán ước lượng số cụm dữ liệu Cell-MST-Based khi áp dụng cho một số tập dữ liệu đặc biệt, nghiên cứu đề xuất sử dụng khoảng cách có trọng số thay gì khoảng cách Euclid, tiếp theo là thay đổi các thuật toán xây dựng đồ thị tối ưu, ước lượng số cụm cho phù hợp với khái niệm khoảng cách có trọng số.. - Khoảng cách Euclid dùng để đo khoảng cách giữa 2 điểm không có trọng số, trong khi tế bào dữ liệu có trọng số. - Hình 5: Ví dụ minh họa chia 1 tập dữ liệu thành tế bào 3.2 Thuật toán ước lượng số cụm dữ liệu. - Sự thay đổi này dẫn đến kết quả ước lượng số cụm dữ liệu của thuật toán cải tiến có thể khác hơn so với thuật toán ban đầu.. - Mô hình tổng quát của thuật toán Thuật toán ước lượng số cụm dữ liệu cải tiến gồm 4 bước như sau:. - Hình 6: Minh họa thuật toán ước lượng số cụm dữ liệu cải tiến gồm 4 bước. - Tế bào cải tiến. - Bước 1: Ánh xạ đối tượng dữ liệu vào tế bào Nội dung của bước này là chia tập dữ liệu lớn gồm đối tượng thành một tập hợp các tế bào có tối đa tế bào. - Mỗi tế bào chứa nhiều đối tượng dữ liệu.. - Giải thuật cải tiến sử dụng lại giải thuật Ánh xạ , với j 1 tới D của thuật toán Cell-MST- Based để ánh xạ các đối tượng dữ liệu trong tập dữ liệu sang tế bào của các đối tượng dữ liệu.. - Trọng số của mỗi tế bào được định nghĩa là tổng trọng số của các đối tượng dữ liệu nằm trong tế bào. - Giá trị thuộc tính của tế bào được tính bằng trung bình cộng giá trị thuộc tính tương ứng của các đối tượng dữ liệu trong tế bào.. - Thuật toán 5: Tế bào cải tiến. - Bước 4: Ước lượng số cụm dữ liệu kết hợp phân cụm. - Mục đích của bước này là ước lượng số cụm dữ liệu của tập tin ban đầu thông qua tập tế bào, kết hợp với việc phân cụm tập dữ liệu ban đầu. - Hình 7: Lưu đồ thuật toán ước lượng số cụm dữ liệu kết hợp phân cụm 4 KẾT QUẢ THỰC NGHIỆM. - 4.1 Cài đặt thuật toán. - Cấu trúc dữ liệu danh sách kề được sử dụng để lưu trữ đồ thị.. - 4.2 Dữ liệu thực nghiệm. - Dữ liệu dùng để thực nghiệm là các tập tin đã được sử dụng bởi thuật toán Cell-MST-Based gồm 13 tập dữ liệu (Van Hieu và Phayung, 2015). - Trong 13 tập dữ liệu dùng để thực nghiệm, có 10 tập dữ liệu biết trước số cụm, 3 tập dữ liệu còn lại chưa biết trước số cụm dữ liệu.. - Tất cả các tập dữ liệu dùng để thực nghiệm không chứa dữ liệu nhiễu nên kết quả của các thuật toán không bị ảnh hưởng bởi dữ liệu ngoại lệ.. - Bảng 2: Thông tin các tập dữ liệu dùng để thực nghiệm. - So sánh kết quả thực hiện của giải thuật ước lượng số cụm dữ liệu ban đầu (Cell-MST-Based) và giải thuật cải tiến (Weighted-Cell-MST-Based) cho thấy:. - Đối với 10 tập dữ liệu đã biết trước số cụm thì kết quả của giải thuật cải tiến giống với kết quả của giải thuật ban đầu đối với cả 3 giá trị của. - Đối với 3 tập dữ liệu chưa biết trước số cụm thì có 1 trường hợp kết quả giống nhau (tập dữ liệu GeolifeTrajectory), 1 trường hợp giải thuật cải tiến ước lượng ít cụm hơn (tập dữ liệu 3D road networks). - Đặc biệt, đối với tập dữ liệu TDriveTrajectory thì giải thuật cải tiến cho kết quả nhỏ hơn và ổn định hơn.. - Để hiểu kỹ hơn kết quả của 2 tập dữ liệu 3D road networks và TdriveTrajectory, chúng ta xét tiếp chỉ số Intra-Inter. - Khi xét về mức độ chính xác thì giải thuật cải tiến cho kết quả tốt hơn giải thuật ban đầu khi áp dụng với 2 tập dữ liệu 3D road networks và TDriveTrajectory bởi vì 2 tập dữ liệu này có sự phân phối dữ liệu đặc biệt hơn so với các tập dữ liệu khác. - Bảng 3: So sánh kết quả số cụm dữ liệu ước lượng được. - Bảng 4: So sánh chỉ số Intra-Inter đối với 2 tập dữ liệu có kết quả ước lượng số cụm dữ liệu khác nhau, với =10%. - Tâp dữ liệu Giải thuật Cell-MST-based Giải thuật Weighted Cell-MST-based Số cụm Intra-Inter Số cụm Intra-Inter. - Khi mật độ của các đối tượng dữ liệu tại những vùng gần nhau có sự chênh lệch quá lớn thì kéo theo sự chênh lệch lớn về trọng số của các tế bào gần nhau. - Do đó, khi áp dụng khoảng các có trọng số vào quá trình tính khoảng cách giữa 2 tế bào thì giải thuật ước lượng số cụm dữ liệu cải tiến Weighted-. - Mặt khác, các tập dữ liệu dùng để phân cụm có thể chứa các đối tượng dữ liệu ngoại lệ. - Nên áp dụng thuật toán loại bỏ các đối tượng dữ liệu ngoại lệ Cell-DROS (Hieu and Phayung, 2016) để loại bỏ dữ liệu ngoại lệ trước khi áp dụng thuật toán ước lượng số cụm dữ liệu.