Xem mẫu
- 196 KỶ YẾU HỘI THẢO KHOA HỌC QUỐC GIA CITA 2017 “CNTT VÀ ỨNG DỤNG TRONG CÁC LĨNH VỰC”
Một cải tiến thuật toán K-Means song song
sử dụng phương pháp lấy mẫu
Trần Hoàng Việt1, Nguyễn Thị Tuyết1, Trần Thiên Thành1
1
Khoa Công nghệ thông tin, Đại học Quy Nhơn
tranhoangviet92@gmail.com,
nguyenthituyet@qnu.edu.vn,thanhtranthien@gmail.com
Tóm tắt: Phân cụm dữ liệu là một kỹ thuật ứng dụng trong nhiều lĩnh vực khác nhau.
K-means là thuật toán kinh điển trong phân cụm dữ liệu. Hiện tại, trong thời điểm bùng nổ
dữ liệu, K-means cũng như các thuật toán khác không đáp ứng yêu cầu về tốc độ. Việc cải
tiến thuật toán để xử lý dữ liệu lớn là nhu cầu cấp thiết. Trong nghiên cứu này, chúng tôi
trình bày ý tưởng cải tiến thuật toán phân cụm dữ liệu PK-means, phân tích ưu và nhược
điểm của thuật toán này, sau đó trình bày thuật toán cải tiến của chúng tôi SK-meansMR và
thực nghiệm đánh giá chất lượng, tốc độ của thuật toán trên dữ liệu lớn.
Keywords: K-means cải tiến, MapReduce, PK-means, SK-meansMR.
1 Mở đầu
“Chúng ta đang tràn ngập trong thông tin nhưng lại khát tri thức”, nhận định của John
Naisbett’s đã thể hiện được nhu cầu rất lớn về khai phá dữ liệu. Đặc biệt trong thời điểm bùng
nổ thông tin, việc khai phá dữ liệu lớn càng trở nên cấp thiết hơn nữa.
Các bài toán hiện tại thường gắn liền với tập dữ liệu lớn nhưng các thuật toán truyền thống
không đáp ứng yêu cầu về thời gian. Xử lý song song trên môi trường phân tán là một giải pháp
để giải quyết vấn đề này.
Phân cụm dữ liệu là một bước quan trọng trong khai phá dữ liệu, được ứng dụng trong nhiều
lĩnh vực khác nhau như: thiên văn học, tin sinh học, thương mại điện tử, phát hiện lừa đảo,
quảng cáo, quản lý quan hệ khách hàng, chăm sóc sức khỏe, viễn thông, đầu tư. Trong phân
cụm dữ liệu, thuật toán K-means là thuật toán kinh điển nhưng không thể giải quyết tập dữ liệu
lớn. Để khắc phục một số nhược điểm của K-means khi xử lý dữ liệu lớn, các cải tiến thường sử
dụng mô hình lập trình MapReduce để tăng hiệu suất thuật toán.
Một trong những thuật toán cải tiến nổi tiếng của K-means là PK-means của Weizhong Zhao
[5]. Ý tưởng của thuật toán là chia nhỏ dữ liệu rồi thực hiện xác định cụm trên từng phần dữ liệu
đó. Kế tiếp tổng hợp các điểm cùng cụm lại với nhau thực hiện tính toán lại tâm cụm, kiểm tra
độ hội tụ, quá trình này cũng được lặp đi lặp lại tương tự như K-means cổ điển. Tuy nhiên, quá
trình chuẩn bị dữ liệu, truyền và nhận dữ liệu trong hệ thống phân tán mất một khoảng thời gian
nhất định. Vì vậy, nếu áp dụng mô hình này cần hạn chế việc gọi lại cả quá trình nhiều lần. Đối
với ý tưởng của Weizhong Zhao, thuật toán cần lặp đi lặp lại quá trình phân tán và xử lý song
song làm cho thuật toán trở nên kém hiệu quả.
Để cải tiến thuật toán PK-means, chúng tôi thực hiện chọn một số lượng mẫu nhất định đại
diện cho từng bộ dữ liệu. Sau đó thực hiện phân cụm trên tập mẫu đó để xác định k tâm cụm
cuối cùng. Khi có được k tâm cụm, chúng tôi xác định các điểm trong từng cụm. Đây cũng là
- Trần Hoàng Việt, Nguyễn Thị Tuyết, Trần Thiên Thành 197
kết quả phân cụm của thuật toán. Số lần thực hiện MapReduce trong giải thuật của chúng tôi
luôn luôn là hai lần. Như vậy, trong thuật toán này, rõ ràng giảm thời gian chuẩn bị, truyền và
nhận dữ liệu hơn so với thuật toán PK-means.
Để chứng minh hiệu quả thuật toán của mình, chúng tôi cũng tiến hành thực nghiệm trên hai
khía cạnh. Một là, việc lấy mẫu có ảnh hưởng đến chất lượng phân cụm hay không. Hai là, so
sánh tốc độ với thuật toán K-means cổ điển.
Nghiên cứu gồm 5 phần. Sau phần mở đầu, chúng tôi trình bày các kiến thức liên quan về
mô hình lập trình MapReduce, về các thuật toán K-means và PK-means. Phần ba trình bày về
một cải tiến thuật toán K-means bằng phương pháp lấy mẫu (SK-meansMR). Phần bốn là kết
quả thực nghiệm để chứng minh hiệu quả thuật toán SK-meansMR. Cuối cùng là phần kết luận
và hướng nghiên cứu trong tương lai.
2 Kiến thức liên quan
2.1 Mô hình lập trình song song MapReduce
MapReduce là mô hình lập trình song song được Google đề xuất để xử lý dữ liệu lớn trong
môi trường phân tán. Theo [12] MapReduce gồm hai bước Map và Reduce thực hiện hoàn toàn
độc lập, song song trên các cặp dữ liệu (key, value):
Hàm Map
Nhận dữ liệu đầu vào (input) dưới dạng (key1, value1), thực hiện xử lý lọc (filter) và phân
loại (sort) trên dữ liệu rồi trả về danh sách các cặp dữ liệu (key2, value2):
map(key1,value1) list(key2,value2)
Hàm Reduce
Hệ thống nhóm các value theo key từ kết quả của các hàm Map, tạo thành tập các cặp dữ liệu
với cấu trúc (key, tập các value cùng key). Hàm Reduce nhận các cặp dữ liệu này, thực hiện xử
lý trên từng cặp dữ liệu và trả kết quả về cho người dùng:
reduce(key2, list (value2)) list(value3)
Hình 1. Mô hình lập trình MapReduce
2.2 Thuật toán K-means
Thuật toán K-means [4] là một thuật toán quan trọng và được sử dụng phổ biến trong kỹ
thuật phân cụm. K-means chia một tập D đối tượng thành k cụm sao cho kết quả tương đồng
- 198 KỶ YẾU HỘI THẢO KHOA HỌC QUỐC GIA CITA 2017 “CNTT VÀ ỨNG DỤNG TRONG CÁC LĨNH VỰC”
trong cùng cụm tương đối cao, ngược lại là sự tương đồng thấp giữa các cụm khác nhau. Ý
tưởng thuật toán:
Bước 1: Thuật toán xác định k tâm ngẫu nhiên.
Bước 2: Thuật toán lặp lại quá trình:
- Xác định cụm cho các điểm;
- Xác định tâm cụm mới;
- Nếu đạt ngưỡng hội tụ giữa tâm cụm cũ và mới hoặc qua một số lần lặp nhất định thì kết
thúc thuật toán.
Nhược điểm của K-means là lặp lại việc tính khoảng cách để xác định cụm cho các điểm lặp
đi lặp lại. Trong mỗi lần lặp, tổng số các phép tính khoảng cách phải thực hiện là D*k trong đó
D là số đối tượng, k là số lượng các cụm. Với bộ dữ liệu lớn, đòi hỏi cần cải tiến để đáp ứng
được yêu cầu về thời gian.
2.3 Thuật toán K-means cải tiến của Weizhong Zhao (PK-means)
Để phân cụm dữ liệu lớn, Weizhong Zhao đề xuất một cải tiến theo hướng xử lý song song
[5]. Theo ý tưởng của Weizhong Zhao dữ liệu sau khi được chia nhỏ và phân tán, sẽ thực hiện
song song việc xác định cụm cho các điểm. Nhờ mô hình MapReduce, các điểm cùng cụm trong
các bộ dữ liệu phân tán sẽ được nhóm chung lại với nhau để thực hiện việc tính toán lại tâm và
kiểm tra độ hội tụ. Thuật toán cũng tiến hành lặp quá trình xác định cụm và tính toán tâm tương
tự như K-means cổ điển. Hình 2 thể hiện quá trình thực hiện MapReduce trên ý tưởng của
Weizhong Zhao.
Hình 2. Thuật toán PK-means
Hàm Map:
Đối với mỗi hàm Map, PK-means xây dựng một mảng chứa thông tin về các tâm cụm. Với
mảng này, hàm Map có thể tính tâm gần nhất cho mỗi đối tượng. Kết quả trả về của hàm Map là
các cặp: .
Hàm Combine:
Được xây dựng để kết hợp các dữ liệu trung gian của cùng một Map. Khi kết quả trả về được
lưu trữ trong bộ nhớ cục bộ của máy thực hiện hàm Map, hệ thống sẽ thực hiện hàm Combine
tổng hợp các điểm được gán cho cùng một cụm lại với nhau, tính tọa độ trung bình cho mỗi cụm
và ghi lại số lượng các mẫu trong cùng một cụm nhằm thu gọn kết quả, giảm chi phí truyền
thông đến Reduce.
- Trần Hoàng Việt, Nguyễn Thị Tuyết, Trần Thiên Thành 199
Hàm Reduce:
Đầu vào là số liệu thu được từ hàm Combine của mỗi máy. Như mô tả trong hàm Combine,
dữ liệu bao gồm tổng số các mẫu có trong cùng một cụm và số lượng mẫu trong cụm đó.
Hàm Reduce tổng hợp tất cả các mẫu, tính toán và xác định các tâm mới để sử dụng cho lần lặp
tiếp theo.
Về lý thuyết, việc xử lý song song trên các bộ dữ liệu được chia nhỏ sẽ tăng tốc độ của thuật
toán. Tuy nhiên, trong thực tế, thuật toán lại tồn tại một nhược điểm của mô hình MapReduce là
mất thời gian chuẩn bị dữ liệu, khởi chạy và truyền tải giữa các máy tính hệ thống. Thuật toán
của Weizhong Zhao lại lặp đi lặp lại việc sử dụng MapReduce làm thời gian thực tế tăng lên rất
lớn. Trong thực nghiệm của chúng tôi trên R, thậm chí còn chậm hơn K-means cổ điển.
3 Thuật toán K-means cải tiến bằng phương pháp lấy mẫu (SK-meansMR)
Ý tưởng PK-means vừa thực hiện việc lặp đi lặp lại quá trình xử lý song song để xác định
các tâm cụm vừa lưu trữ liên tục các tâm để xác định độ hội tụ dẫn đến thời gian thực hiện thuật
toán tăng lên rất lớn. Để loại bỏ sự phụ thuộc lặp quá trình xử lý song song của thuật toán,
chúng tôi sử dụng phương pháp lấy mẫu nhằm xác định các tập con đại diện cho tập dữ liệu lớn.
Sau đó sử dụng thuật toán phân cụm cổ điển trên các tập con để xác định k tâm cuối cùng [8].
Quá trình thực hiện phân cụm qua 2 Job MapReduce thể hiện trong hình 3.
Hình 3. Quá trình thực hiện phân cụm của thuật toán SK-meansMR
Thuật toán: Xác định k tâm sử dụng phương pháp lấy mẫu
Input : tập dữ liệu D, k
Output : k tâm cụm
Map(k1, v1){
Xử lý dữ liệu đầu vào;
Chuyển đổi dữ liệu sang kiểu số thực;
Output(1, K-means(v1, 2*k)).
}
Reduce(k2, v2)
Output(K-means(v2, k))
- 200 KỶ YẾU HỘI THẢO KHOA HỌC QUỐC GIA CITA 2017 “CNTT VÀ ỨNG DỤNG TRONG CÁC LĨNH VỰC”
Hình 4. Sơ đồ thể hiện thuật toán xác định tâm SK-meansMR
Trong thuật toán trên, chúng tôi thực hiện việc lấy mẫu trên từng tập dữ liệu phân tán. Việc
thực hiện lấy mẫu dựa trên phương pháp xác định tâm cụm với số lượng tâm bất kỳ sao cho số
lượng tâm có thể đại diện cho tập dữ liệu và tổng số tâm không vượt quá khả năng xử lý của
một node. Giả sử, với n hàm Map được xử lý song song và k' tâm là các điểm sẽ đại diện cho
tập dữ liệu đầu vào mỗi hàm Map. Tập đại diện sẽ có kích thước n*k' phần tử, phải đảm bảo
không vượt quá khả năng xử lý của một Node. Chúng tôi chọn số lượng mẫu là 2*k tâm trong
thực nghiệm của mình. Hàm Reduce nhận kết quả từ hàm Map, thực hiện thuật toán K-means để
xác định k tâm.
4 Kết quả thực nghiệm
Chúng tôi thực nghiệm thuật toán trên 5 máy tính Core 2 Duo E8400 3.00GHz, hệ điều hành
Ubuntu 14.04, Hadoop 2.7.3, R 3.3.3 gồm 1 MasterNode và 4 NameNode.
Bộ dữ liệu thực nghiệm gồm có KddCup (1999) 42 thuộc tính, 2.155.000 điểm, kích thước
197,6 MB; Individual Household Electric Power Consumption (House) 14 thuộc tính, 4.098.559
điểm, kích thước 226,5 MB. Các bộ dữ liệu được tải về tại UCI Machine Learning Repository
http://archive.ics.uci.edu/ml/index.php.
4.1 Đánh giá chất lượng
Việc đánh giá chất lượng phân cụm rất khó khăn. Theo [6] [7], có 3 loại độ đo chất lượng
phân cụm: đánh giá trong (internal evaluation), đánh giá ngoài (external evaluation), đánh giá
quan hệ (relative evalution). Để so sánh chất lượng phân cụm của hai thuật toán, chúng tôi sử
dụng chỉ số Davies-Bouldin (DBI) của kỹ thuật đánh giá trong.
- Trần Hoàng Việt, Nguyễn Thị Tuyết, Trần Thiên Thành 201
Theo [13] chỉ số Davies-Bouldin (DBI) (được David L. Davies và Donald W. Bouldin đưa ra
vào năm 1979) xác nhận tính hợp lệ của việc phân cụm đã được thực hiện bằng cách sử dụng
các số liệu và các đặc tính vốn có của bộ dữ liệu.
Chỉ số Davies-Bouldin được tính theo công thức:
1 n i j
DB
n
i 1
M axi j (
d (ci , c j )
)
Trong đó:
+ n là số cụm;
+ cx là trọng tâm của cụm x;
+ σx là trung bình khoảng cách của tất cả các phần tử trong cụm x tới trọng tâm cx;
+ d(ci,cj) là khoảng cách giữa hai trọng tâm của cụm i và j.
Giá trị DBI càng nhỏ thì chất lượng phân cụm càng tốt.
Bộ dữ liệu KddCup(1999) 42 thuộc tính, 2.155.000 điểm:
Bảng 1. Chỉ số DB của K-means và SK-
meansMR trên bộ dữ liệu KddCup
K K-means SK-meansMR
5 1,578 0,239
6 1,829 0,231
7 0,813 0,263
8 2,069 0,268 Hình 5. Biểu đồ chất lượng phân cụm
9 0,741 0,431 K-means và SK-meansMR trên bộ DL KddCup
Bộ dữ liệu House 14 thuộc tính, 4.098.559 điểm:
Bảng 2. Chỉ số DB của K-means và
SK-meansMR trên bộ dữ liệu House
K K-means SK-meansMR
10 1,514 1,091
11 1,252 1,157
12 1,552 1,225
13 1,562 1,279 Hình 6. Biểu đồ chất lượng phân cụm K-means
14 1,438 1,373 và SK-meansMR trên bộ DL House
Qua thực nghiệm, có thể thấy chỉ số DBI của thuật toán SK-meansMR thấp hơn K-means cổ
điển. Chứng tỏ thuật toán cải tiến SK-meansMR có chất lượng phân cụm tốt hơn K-means.
Với mỗi số lượng cụm nhất định, chỉ số DBI của K-means thay đổi rất lớn. Điều này cũng
chứng minh việc chọn tâm ảnh hưởng đến chất lượng cụm. Ngược lại, so với K-means, thuật
toán SK-meansMR có chất lượng phân cụm rất tốt và ít thay đổi.
Qua hai bộ dữ liệu thực nghiệm có thể thấy số lượng điểm lớn cũng ảnh hưởng đến chất
lượng phân cụm của thuật toán SK-meansMR.
- 202 KỶ YẾU HỘI THẢO KHOA HỌC QUỐC GIA CITA 2017 “CNTT VÀ ỨNG DỤNG TRONG CÁC LĨNH VỰC”
4.2 Đánh giá tốc độ
Để đánh giá hiệu năng của thuật toán, chúng tôi tiến hành thực nghiệm so sánh thuật toán
SK-meansMR với thuật toán K-means cổ điển trên hai bộ dữ liệu: KddCup và House. Đối với
thuật toán SK-meansMR, chúng tôi thực nghiệm với số lượng mẫu đại diện cho mỗi tập con dữ
liệu là 2*k tâm.
Bộ dữ liệu KddCup(1999) 42 thuộc tính, 2.155.000 điểm:
Bảng 3. Thời gian chạy của K-means và
SK-meansMR trên bộ dữ liệu KddCup
K K-means SK-meansMR
5 119,76 56,44
6 122,06 56,50
7 146,18 56,50
8 155,37 57,59 Hình 7. Biểu đồ tốc độ của K-means và
9 190,33 58,30 SK-meansMR trên bộ dữ liệu KddCup
Bộ dữ liệu House 14 thuộc tính, 4.098.559 điểm:
Bảng 4. Thời gian chạy (s) của K-means và
SK-meansMR trên bộ dữ liệu House
K K-means SK-meansMR
10 65,07 56,82
11 67,91 57,73
12 68,56 58,84
13 74,93 58,09 Hình 8. Biểu đồ tốc độ của K-means và
14 81,28 59,40 SK-meansMR trên bộ dữ liệu House
Qua thực nghiệm, có thể thấy thời gian thực hiện thuật toán SK-meansMR giảm đáng kể so
với thời gian thực hiện thuật toán K-means cổ điển.
Với số lượng tâm cụm k = 10, k = 11 đối với House và k = 5, k = 6 đối với KddCup, thời
gian thực hiện thuật toán K-means tăng không đáng kể. Tuy nhiên, với số lượng tâm cụm lớn
hơn, thời gian thực hiện thuật toán K-means bắt đầu tăng rất nhanh.
Ngược lại, thuật toán SK-meansMR của chúng tôi cho kết quả tăng đều về mặt thời gian khi
thay đổi số lượng cụm trên cả hai bộ dữ liệu.
5 Kết luận và hướng nghiên cứu trong tương lai
Trong nghiên cứu chúng tôi đã trình bày thuật toán SK-meansMR, thực nghiệm và đánh giá
để chứng minh chất lượng phân cụm và tốc độ của thuật toán cải tiến tốt hơn K-means cổ điển.
Bài toán phân cụm dữ liệu ứng dụng rất nhiều trong thực tế. Trong thời gian đến, chúng tôi
tiếp tục nghiên cứu ứng dụng trên bài toán phân cụm dữ liệu điểm sinh viên và thực nghiệm trên
bộ dữ liệu điểm của trường Đại học Quy Nhơn. Sau đó mô hình hóa kết quả thực nghiệm và
phân tích từng cụm dữ liệu để đưa ra các tư vấn phù hợp cho sinh viên đồng thời tiếp tục cập
nhật và phân cụm dữ liệu các khóa tiếp theo để chứng minh tính đúng đắn trong các phân tích
và tư vấn của mình.
- Trần Hoàng Việt, Nguyễn Thị Tuyết, Trần Thiên Thành 203
Tài liệu tham khảo
1. George Karypis, Eui-Hong (Sam) Han, and Vipin Kumar. “Multilevel Refinement for Hierarchical
Clustering”. 1999.
2. Graham J. Williams, Simeon J. Simoff, “Data Mining: Theory, Methodology, Techniques, and
Applications”, Springer-Verlag, 2006.
3. Huang, Z., “Clustering Large Data Sets with Mixed Numeric and Categorical Values, In Proceedings
of The First Pacific-Asia Conference on Knowledge Discovery and Data Mining”, Singapore, World
Scientific, 1997.
4. J. A. Hartigan and M. A. Wong, “A K-means clustering algorithm”, Applied Statistics, Vol. 28,
pp. 100-108, 1979.
5. Weizhong Zhao, Huifang Ma, and Qing He, “Parallel K-Means Clustering Based on MapReduce”,
2009.
6. Darius Pfitzner, Richard Leibbrandt, David M. W. Powers (2009): “Characterization and evaluation
of similarity measures for pairs of clusterings”. Knowl. Inf. Syst. 361-394.
7. Maria Halkidi, Yannis Batistakis, Michalis Vazirgiannis: “On Clustering Validation Techniques”.
J. Intell. Inf. Syst. 17(2-3): 107-145, 2001.
8. Trần Thiên Thành, Nguyễn Thị Tuyết, Hồ Văn Lâm, Trần Hoàng Việt, “Cài đặt thuật toán K-means
cải tiến bằng phương pháp lấy mẫu áp dụng mô hình lập trình MapReduce trên công cụ R”, bài báo
đăng trong Kỷ yếu “Hội thảo Một số vấn đề chọn lọc của Công nghệ thông tin và Truyền thông” lần
thứ 20, 11/2017.
9. Oyelade O. J, Oladipupo O. O, Obagbuwa I. C, “Application of k-Means Clustering algorithm for
prediction of Students’ Academic Performance”, (IJCSIS) International Journal of Computer Science
and Information Security, Vol. 7, No. 1, 2010.
10. Md.H.I.Shovon, M. Haque, “An Approach of Improving Student’s Academic Performance by using
K-means clustering algorithm and Decision tree”, (IJACSA) International Journal of Advanced
Computer Science and Applications, Vol.3, No. 8, 2012.
11. Byoungwook Kim, JaMee Kim, Gangman Yi, “Analysis of Clustering Evaluation Considering
Features of Item Response Data Using Data Mining Technique for Setting Cut-Off Scores”,
Symmetry 2017, 9, 62.
12. Tom White, Hadoop, The Definitive Guide, 4th Edition, O’Reilly Media, Inc, 2015.
13. Wikipedia, “Cluster analysis”, Website: https://en.wikipedia.org/wiki/Cluster_analysis.
nguon tai.lieu . vn