Xem mẫu
- 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, trong bài báo
center’s coordinates; này, chúng tôi cải tiến thuật toán PKMeans
6. Take key as key’;
7. Construct value’ as a string comprise of the center’s thành ImagePKMeans gồm 2 thuật toán chính
coordinates; với các hàm mapImage và reduceImage.
8. output < key , value > pair;
9. End Bảng 3: Thuật toán cho hàm
4. GIẢI PHÁP PHÂN CỤM ẢNH DỰA mapImage(key,value)
TRÊN MAPREDUCE Input: Global variable centers, the offset key, the sample
value is the list of color bands and position
Để phân cụm ảnh với mô hình Output: pair, where the key’ is the index of the closest
MapReduce, chúng tôi đề xuất lược đồ phân center point and value’ is a string comprise of color bands
and position
cụm như sau: 1. Construct the sample instance from value;
• B1: Chuyển đổi dữ liệu 2. minDis = Double.MAX VALUE;
• B2: Phân cụm với thuật toán 3. index = -1;
4. For i=0 to centers.length do dis=
ImagePKMeans ComputeDist(instance, centers[i]); If dis < minDis {
• B3: Khôi phục kết quả phân cụm ảnh minDis = dis; index = i; }
5. End For
6. Take index as key’;
5. CHUYỂN ĐỔI d÷ LIỆU 7. Construct value’ as a string comprise of the values of
different dimensions and position;
Yêu cầu: 8. output < key , value > pair;
• Chuyển đổi dữ liệu điểm ảnh thành list 9. End
các hàng.
Bảng 4: Thuật toán cho hàm reduce
• Mỗi hàng bao gồm: thông tin vị trí và Image(key,V)
danh sách giá trị là các thành phần của vector Input: key is the index of the cluster, V is the list of color
biểu diễn cho một điểm ảnh. bands and position of the same cluster from different host
Output: < key , value > pair, where the key’ is new center
4.1. Cải tiến thuật toán PKMeans cho of the cluster, value’ is a string representing values of
phân cụm dữ liệu ảnh different dimensions and position
1. Initialize one array record the sum of value of each
dimensions of the samples contained in the same cluster,
e.g. the samples in the list V;
2. Initialize a counter NUM as 0 to record the sum of
sample number in the same cluster;
3. while(V.hasNext()){
Construct the sample instance by extract values of
different dimensions from V.next();
Add the values of different dimensions of instance to the
array NUM += num;
4. }
5. Divide the entries of the array by NUM to get the new
center’s coordinates;
6. Take key as key’;
7. Construct value’ as a string comprise of the center’s
coordinates and position;
8. output < key , value > pair;
Hình 2: Sơ đồ thuật toán ImagePKMeans. 9. End
152
- Tuyển tập Hội nghị Khoa học thường niên năm 2019. ISBN: 978-604-82-2981-8
5.2. Khôi phục kết quả phân cụm ảnh Thuật
ImagePKMeans KMeans
Từ dữ liệu đầu ra của của thuật toán toán
ImagePKMeans, đơn giản nhất, có thể khôi
Thời gian 63556 87955
phục lại ảnh kết quả phân cụm từ thông tin vị chạy (ms)
trí và tâm cụm… Ngoài ra, sau đó, chúng ta
Tâm cụm 111.34,144.54,57.47 111.34,144.54,57.47
có thể thực hiện những việc khác đánh giá dữ sau hội tụ 171.97,65.98,151.51 171.97,65.98,151.51
liệu, phân tích dữ liệu, nhận dạng, phân lớp, 241.18,178.06,232.22 241.18,178.06,232.22
ra quyết định… về sau. 27.09,39.43,17.52 27.09,39.43,17.52
61.75,73.56,36.08 61.75,73.56,36.08
6. THỬ NGHIỆM VÀ ĐÁNH GIÁ
Thời gian 57224 108054
Dữ liệu thử nghiệm Lấy từ bộ dữ liệu của chạy (ms)
Kaggle, bao gồm 210 bản ghi [5]. Một số kết
Tâm cụm 129.69,138.09,78.88 129.69,138.09,78.89
quả phân cụm với 5 cụm được thống kê trong sau hội tụ 219.20,221.84,62.35 219.2,221.84,62.35
bảng 5 và 6. 224.67,230.73,152.24 224.67,230.73,152.24
33.32,39.65,23.32 33.32,39.65,23.32
Bảng 5. Ảnh kết quả phân cụm 85.66,90.67,42.43 85.66,90.67,42.43
với KMeans và ImagePKMeans
Thời gian 125549 173422
Đầu vào ImagePKMeans K-means chạy (ms)
7. KẾT LUẬN
Trong bài báo này, tác giả đã đề xuất lược đồ
phân cụm ảnh với việc sử dụng thuật toán
ImagePKMeans được cải tiến từ thuật toán
PKMeans dùng cho phân cụm ảnh. Các kết quả
thử nghiệm cho thấy thuật toán ImagePKMeans
cho kết quả phân cụm tốt tương đương và hiệu
suất cao hơn với KMeans. Trong khi, thuật toán
ImagePKMeans có thể thực hiện song song và
phân tán trên cụm máy tính để tăng cường
Từ dữ liệu trong bảng 6, ta thấy tập tâm hiệu suất thực hiện.
cụm sinh ra bởi 2 thuật toán là như sau. Nói Trong nghiên cứu tiếp theo, chúng tôi dự
cách khác, hai thuật toán cho chất lượng phân
kiến áp dụng mô hình MapReduce cho những
cụm tương đương nhau. Tuy nhiên, về thời
gian thực thi, thuật toán ImagePKMeans có thuật toán học máy khác để có thể khai thác,
hiệu suất tốt hơn. phân tích và xử lý dữ liệu lớn hiệu quả hơn.
Bảng 6. Tâm cụm sinh ra sau khi hội tụ 8. TÀI LIỆU THAM KHẢO
Thuật toán ImagePKMeans KMeans [1] Balaji T., Sumathi M., Relational Features of
Tâm cụm 121.25,33.69,38.11 121.25,33.69,38.11 Remote Sensing Image classification using
sau hội tụ 186.78,37.58,64.25 186.78,37.58,64.25 Effective KMeans Clustering, International
224.81,65.30,98.80 224.81,65.30,98.80
Journal of Advancements in Research &
247.19,111.52,154.32 247.19,111.52,154.32
30.13,21.61,14.97 30.13,21.61,14.97
Technology, Volume 2, Issue 8, August-
2013, pp. 103-107.
Thời gian 63556 246916 [2] Chih-Tang Chang và cộng sự, A Fuzzy
chạy (ms)
Tâm cụm 102.13,119.54,63.75 102.13,119.54,63.75
KMeans Clustering Algorithm Using
sau hội tụ 21.72,24.67,17.19 21.72,24.67,17.19 Cluster Center Displacement, Journal of
215.19,71.73,14.58 215.19,71.73,14.56 Information science and Engineering 27,
249.06,124.79,24.10 249.06,124.79,24.10 2011, pp. 995-1009.
62.65,71.94,36.40 62.65,71.94,36.40
153
nguon tai.lieu . vn
