Ứng dụng mô hình MapReduce trong phân cụm ảnh

Phân cụm là kỹ thuật rất quan trọng trong khai phá dữ liệu, nó thuộc lớp các phương pháp Unsupervised Learning trong Machine Learning. Bài viết Ứng dụng mô hình mapreduce trong phân cụm ảnh đề xuất cải tiến thuật toán phân cụm KMeans dựa trên mô hình MapReduce để có thể áp dụng cho phân cụm ảnh.
Nội dung trích xuất từ tài liệu:
Ứng dụng mô hình MapReduce trong phân cụm ảnh Tuyển tập Hội nghị Khoa học thường niên năm 2019. ISBN: 978-604-82-2981-8 ỨNG DỤNG MÔ HÌNH MAPREDUCE TRONG PHÂN CỤM ẢNH Vũ Thị Hường1, Nguyễn Tu Trung2 1 Sinh viên khoa Công nghệ thông tin – Trường Đại học Thủy lợi, huongvt52@wru.vn 2 Trường Đại học Thủy lợi 1. ĐẶT VẤN ĐỀ MapReduce là mô hình xử lý tính toán song song và phân tán do google đề xuất. Nó Phân cụm là kỹ thuật rất quan trọng trong bao gồm hai chức năng cơ bản: 'Map' và khai phá dữ liệu, nó thuộc lớp các phương 'Reduce' được xác định bởi người dùng [4]. pháp Unsupervised Learning trong Machine Dữ liệu đầu vào được chia thành nhiều mảnh Learning. Về bản chất ta có thể hiểu phân nhỏ và xử lý song song bởi các Worker cụm là quá trình tìm cách nhóm các đối (MapTasktracker và ReduceTasktracker), tượng đã cho vào các cụm, sao cho các đối như được thể hiện trong hình 1. tượng trong cùng 1 cụm tương tự nhau và các đối tượng khác cụm thì không tương tự nhau. 3. THUẬT TOÁN PHÂN CỤM SONG Có nhiều phương pháp phân cụm khác SONG PKMEANS nhau như: phương pháp hình thái, phương Từ thuật toán KMeans [6] và mô hình xử pháp họ KMeans, tách và hợp... Trong [2], lý dữ liệu phân tán MapReduce, Jaatun và các tác giả đã đề xuất thuật toán KMeans sử công sự đã đưa ra thuật toán PKMeans dựa dụng thay thế tâm cụm. Trong [1], Balaji và trên MapReduce gồm 2 thuật toán chính cho cộng sự trình bày phương pháp phân đoạn hàm map và hàm reduce. ảnh mới dựa trên đặc trưng màu từ ảnh với việc chuyển điểm ảnh từ không gian RGB Bảng 1: Thuật toán cho hàm map(key,value) sang không gian L*a*b*. Input: Global variable centers, the offset key, the sample Sự bùng nổ của nguồn dữ liệu lớn (Big value Output: pair, where the key’ is the index of the closest Data), những phương pháp xử lý mới. center point and value’ is a string comprise of sample MapReduce là mô hình xử lý dữ liệu phân tán information rất hiệu quả, đã và đang được ứng dụng rộng 1. Construct the sample instance from value; rãi trong xử lý dữ liệu lớn. Trong [3] [7], các 2. minDis = Double.MAX VALUE; 3. index = -1; tác giả đã trình bày thuật toán KMeans song 4. For i=0 to centers.length do dis= ComputeDist(instance, song và hiệu quả dựa trên MapReduce. Tuy centers[i]); If dis < minDis { minDis = dis; index = i; } nhiên, các tác giả chưa chỉ ra cách ứng dụng 5. End For 6. Take index as key’; thuật toán này cho dữ liệu ảnh lớn. 7. Construct value’ as a string comprise of the values of Bài báo này đề xuất cải tiến thuật toán phân different dimensions; cụm KMeans dựa trên mô hình MapReduce để 8. output < key , value > pair; 9. End có thể áp dụng cho phân cụm ảnh. Từ thuật toán cho hàm map, ta thấy đầu 2. MÔ HÌNH MAPREDUCE vào cho thuật toán PKMeans phải ở dạng list các đối tượng dữ liệu mà có thể chuyển về dạng key/value. Tuy nhiên, với dữ liệu ảnh thì cần có một bước chuyển đổi. Ngoài ra, với kết quả của hàm reduce như trên, mặc dù đã thu được tâm và thông tin điểm ảnh nhưng rất bất tiện nếu thực hiện các thao tác tiếp theo trên ảnh mà sử dụng kết quả phân cụm vì thông tin Hình 1: Mô hình MapReduce [4]. vị trí không bao gồm trong kết quả. 151 Tuyển tập Hội nghị Khoa học thường niên năm 2019. ISBN: 978-604-82-? Bảng 2. Thuật toán cho hàm reduce(key,V) Hình 2 minh họa sơ đồ thuật toán Input: key is the index of the cluster, V is the list of the ImagePKMeans. Dữ liệu ảnh sẽ được chia partial sums from different host thành nhiều mảnh khác nhau. Với mỗi mảnh, Output: < key , value > pair, where the key’ is the index of dữ liệu được gom cụm dựa trên hàm mapImage the cluster, value’ is a string representing the new center 1. Initialize one array record the sum of value of each (key, value). Hệ thống thực hiện việc này song dimensions of the samples contained in the same cluster, song trên các mảnh dữ liệu. Sau khi tất cả các e.g. the samples in the list V; mảnh dữ liệu đều thực hiện gom cụm, dữ liệu 2. Initialize a counter NUM as 0 to record the sum of sample number in the same cluster; được gom theo từng cụm. Sau đó, quá trình tính 3. while(V.hasNext()){ Construct the sample instance from tâm được thực hiện trên từng cụm. Cuối cùng, V.next(); Add the values of different dimensions of thuật toán kiểm tra độ hội tụ và quyết định kết instance to the array NUM += num; 4. } thúc hay tiếp tục vòng lặp mới. 5. Divide the entries of the array by NUM to get the new Để giải quyết vấn đề trên, tr ...