Đề tài: K-Means trên MapReduce và ứng dụng phân cụm ảnh (ĐH Thủy Lợi)

Tìm hiểu thuật toán K-Means dựa trên MapReduce và ứng dụng phân cụm ảnh. Bài viết trình bày chi tiết về K-Means, MapReduce và cách kết hợp chúng để xử lý ảnh hiệu quả.

• Tác giả: Vũ Thị Hường
• Người hướng dẫn: Ts. Nguyễn Tu Trung
• Trường học: Trường Đại học Thủy Lợi
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Tìm hiểu thuật toán K-Means dựa trên mô hình MapReduce và ứng dụng trong phân cụm ảnh
• Loại tài liệu: Đồ án tốt nghiệp
• Năm xuất bản: 2019
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CẢM ƠN
• DANH MỤC BẢNG BIỂU
• DANH MỤC HÌNH ẢNH
• 1. CHƯƠNG 1: TỔNG QUAN VỀ BIGDATA VÀ PHÂN CỤM DỮ LIỆU
• 1.1. Tổng quan về dữ liệu lớn (Big Data)
• 1.2. Tổng quan về phân tích dữ liệu lớn
• 1.3. Tổng quan về phân cụm dữ liệu
• 1.4. Tổng quan về phân cụm ảnh
• 2. CHƯƠNG 2: MÔ HÌNH MAPREDUCE TRONG PHÂN TÍCH DỮ LIỆU LỚN
• 2.1. Mô hình MapReduce
• 2.1.1. Tổng quan về mô hình MapReduce
• 2.1.2. Kiến trúc của MapReduce
• 2.1.3. Nguyên tắc hoạt động của mô hình MapReduce
• 2.1.4. Ưu và nhược điểm của mô hình MapReduce
• 2.1.5. Ứng dụng của MapReduce
• 2.2. Tổng quan về Apache Hadoop
• 2.2.1. Kiến trúc của Apache Hadoop
• 2.2.2. Các trình nền của Hadoop
• 2.2.3. Nguyên tắc hoạt động của Hadoop MapReduce
• 2.2.4. Ứng dụng của hadoop
• 3. CHƯƠNG 3: PHÂN CỤM DỮ LIỆU VỚI THUẬT TOÁN KMEANS
• 3.1. Thuật toán KMeans
• 3.1.1. Tổng quan về thuật toán KMeans
• 3.1.2. Giải thuật của thuật toán KMeans
• 3.1.3. Ví dụ tính toán bằng tay
• 3.1.4. Ưu điểm và nhược điểm của KMeans
• 3.2. Ý tưởng và giải pháp MapReduce hoá thuật toán KMeans
• 3.2.1. Đặc trưng của KMeans để MapReduce
• 3.2.2. Ý tưởng MapReduce hóa KMeans
• 3.3. Thuật toán IPKMeans – cải tiến của PKMeans cho phân cụm ảnh
• 3.3.1. Chuyển đổi dữ liệu
• 3.3.2. Phân cụm ảnh với thuật toán IPKMeans
• 3.3.3. Khôi phục kết quả phân cụm ảnh
• 4. CHƯƠNG 4: CƠ SỞ CÔNG NGHỆ
• 4.1. Hệ điều hành Linux
• 4.2. Công nghệ docker
• 4.2.1. Tổng quan về docker
• 4.2.2. Docker ứng dụng trong multi-node
• 4.3. Ngôn ngữ lập trình Java
• 4.3.1. Tổng quan về Java
• 4.4. Môi trường lập trình Intellij IDEA Ultimate
• 5. CHƯƠNG 5: XÂY DỰNG CHƯƠNG TRÌNH VÀ THỰC NGHIỆM ĐÁNH GIÁ
• 5.1. Yêu cầu hệ thống
• 5.1.1. Yêu cầu chung
• 5.1.2. Yêu cầu chức năng
• 5.2. Xây dựng chương trình
• 5.2.1. Môi trường thực nghiệm
• 5.2.2. Dữ liệu thực nghiệm
• 5.2.3. Cài đặt chương trình
• 5.3. Thực nghiệm và đánh giá
• 5.3.1. Kết quả cài đặt
• 5.3.2. Kết quả thực nghiệm và đánh giá
• TÀI LIỆU THAM KHẢO
• MỞ ĐẦU
• 1.1. Tổng quan về vấn đề nghiên cứu

Tóm tắt

I. Tổng Quan K Means MapReduce Phân Cụm Ảnh Hiệu Quả

Trong kỷ nguyên số, lượng dữ liệu hình ảnh tăng trưởng chóng mặt đặt ra thách thức lớn cho việc xử lý ảnh. Các phương pháp truyền thống gặp khó khăn khi đối mặt với big data. Phân cụm ảnh, một kỹ thuật quan trọng trong data mining và machine learning, giúp tự động phân nhóm ảnh dựa trên đặc điểm tương đồng. Tuy nhiên, với dữ liệu lớn, các thuật toán phân cụm tiêu chuẩn trở nên chậm chạp và thiếu hiệu quả. K-Means, một thuật toán thuật toán phân cụm phổ biến, gặp vấn đề về scalability khi xử lý ảnh big data. MapReduce, một mô hình lập trình tính toán song song, cung cấp giải pháp khả thi để giải quyết vấn đề này. Sự kết hợp giữa K-Means và MapReduce mở ra hướng tiếp cận mới, giúp phân cụm ảnh hiệu quả hơn trên các hệ thống cloud computing và distributed computing.

1.1. Ứng dụng Phân Cụm Ảnh trong Thực Tế

Phân cụm ảnh có ứng dụng rộng rãi trong nhiều lĩnh vực. Trong y tế, kỹ thuật này được sử dụng để phân tích ảnh chụp y tế, hỗ trợ chẩn đoán bệnh. Trong thương mại điện tử, nó giúp phân loại sản phẩm theo hình ảnh. Trong giám sát an ninh, nó được dùng để nhận diện đối tượng và phát hiện bất thường. Theo tài liệu gốc, phân cụm ảnh là "Bộ phận cấu thành cơ bản trong nhiều ứng dụng về xử lý ảnh", nhấn mạnh tầm quan trọng của nó trong các hệ thống image processing.

1.2. Thách Thức khi Phân Cụm Ảnh Dữ Liệu Lớn

Khi kích thước dữ liệu tăng lên, các thuật toán phân cụm ảnh truyền thống gặp phải nhiều thách thức. Thời gian tính toán tăng theo cấp số nhân, đòi hỏi tài nguyên phần cứng lớn. Vấn đề về lỗi và độ chính xác cũng trở nên nghiêm trọng hơn. Bài toán phân cụm dữ liệu lớn cần các giải pháp tính toán song song và distributed computing để đảm bảo hiệu quả phân cụm và khả năng mở rộng.

II. Bài Toán Phân Cụm Ảnh Vấn Đề Cách Tiếp Cận Hay

Bài toán phân cụm ảnh đặt ra yêu cầu phân chia một ảnh thành các vùng không trùng lặp, mỗi vùng chứa các pixel có đặc điểm tương đồng. Mục tiêu là tạo ra các cụm có tính đồng nhất cao và khác biệt rõ rệt giữa các cụm. Có hai hướng tiếp cận chính: dựa trên pixel và dựa trên đối tượng. Tuy nhiên, việc xử lý ảnh vẫn còn nhiều hạn chế về độ phức tạp tính toán và khối lượng dữ liệu. Theo tài liệu, "Việc xử lý ảnh còn tồn tại nhiều vấn đề như: Độ phức tạp của thời gian tính toán theo cấp số nhân; khối lượng dữ liệu được xử lý giới hạn, vấn đề về lỗi…". K-Means là một lựa chọn phổ biến, nhưng cần được điều chỉnh để phù hợp với big data.

2.1. Các Tiêu Chí Đánh Giá Phân Cụm Ảnh Tốt

Một phương pháp phân cụm ảnh tốt cần tạo ra các cụm có chất lượng cao. Điều này có nghĩa là các pixel trong cùng một cụm phải có mức độ tương đồng cao, trong khi các pixel thuộc các cụm khác nhau phải khác biệt đáng kể. Chất lượng của kết quả phân cụm phụ thuộc vào cả độ đo tương tự được sử dụng và cách thức thực hiện. Khả năng phát hiện các mẫu tiềm ẩn cũng là một tiêu chí quan trọng.

2.2. Các Bước Cơ Bản Trong Quy Trình Phân Cụm Ảnh

Quy trình phân cụm ảnh thường bao gồm các bước sau: Thu nhận ảnh, Tiền xử lý ảnh (lọc nhiễu, tăng độ tương phản), Phân cụm, Biểu diễn và mô tả ảnh, Nhận dạng và giải thích, và Cơ sở tri thức. Theo tài liệu, bước phân cụm là "phần phức tạp, khó khăn nhất trong xử lý ảnh và cũng dễ gây lỗi, làm mất độ chính xác của ảnh". Việc lựa chọn thuật toán phân cụm phù hợp là yếu tố then chốt để đạt được kết quả tốt.

III. Phương Pháp MapReduce Hóa Thuật Toán K Means Hướng Dẫn

MapReduce là một mô hình lập trình tính toán song song cho phép xử lý dữ liệu lớn một cách hiệu quả. Bằng cách chia nhỏ dữ liệu và xử lý song song trên nhiều máy tính, MapReduce giúp giảm thời gian tính toán đáng kể. Trong bối cảnh phân cụm ảnh, MapReduce có thể được sử dụng để tăng tốc thuật toán K-Means. Ý tưởng chính là phân rã quá trình tính toán thành hai giai đoạn: Map và Reduce. Giai đoạn Map chia dữ liệu đầu vào thành các phần nhỏ và xử lý song song. Giai đoạn Reduce tổng hợp kết quả từ giai đoạn Map để tạo ra kết quả cuối cùng.

3.1. Ưu Điểm Của MapReduce Trong Phân Tích Dữ Liệu Lớn

MapReduce mang lại nhiều lợi ích cho việc phân tích dữ liệu lớn. Nó cung cấp khả năng mở rộng dễ dàng, cho phép xử lý dữ liệu có kích thước lớn hơn nhiều so với các phương pháp truyền thống. Nó cũng cung cấp khả năng chịu lỗi, đảm bảo rằng quá trình tính toán sẽ không bị gián đoạn nếu một máy tính bị lỗi. Ngoài ra, MapReduce giúp đơn giản hóa quá trình lập trình, cho phép các nhà phát triển tập trung vào logic nghiệp vụ thay vì các chi tiết kỹ thuật của tính toán song song.

3.2. Kiến Trúc và Nguyên Tắc Hoạt Động của Mô Hình MapReduce

Kiến trúc MapReduce bao gồm các thành phần chính: Client Program, JobTracker và TaskTracker. Client Program là chương trình mà người dùng sử dụng để chạy một MapReduce Job. JobTracker tiếp nhận job và điều phối job này, chia nhỏ job thành các task và lên lịch phân công các task đến các TaskTracker. TaskTracker tiếp nhận maptask hay reducetask từ JobTracker để thực hiện. Theo tài liệu, "MapReduce được xây dựng từ mô hình lập trình hàm và lập trình song song. Tăng tốc độ thực thi xử lý dữ liệu là mục đích quan trọng nhất của MAPREDUCE."

3.3. Hướng Dẫn Triển Khai K Means trên Nền Tảng MapReduce

Để triển khai K-Means trên nền tảng MapReduce, cần thực hiện các bước sau: 1. Chuẩn bị dữ liệu đầu vào ở định dạng phù hợp với MapReduce (key-value pairs). 2. Viết hàm Map để tính khoảng cách từ mỗi điểm dữ liệu đến các centroid và gán điểm đó cho centroid gần nhất. 3. Viết hàm Reduce để tính lại các centroid bằng cách lấy trung bình cộng của các điểm được gán cho mỗi centroid. 4. Lặp lại các bước 2 và 3 cho đến khi các centroid hội tụ (không thay đổi đáng kể).

IV. IPKMeans Giải Pháp Tối Ưu Phân Cụm Ảnh Song Song Với Big Data

IPKMeans là một thuật toán cải tiến của PKMeans, được thiết kế đặc biệt cho việc phân cụm ảnh big data. Nó tận dụng MapReduce để xử lý song song dữ liệu ảnh, giúp tăng tốc quá trình phân cụm. Điểm khác biệt chính của IPKMeans so với PKMeans là nó bao gồm thông tin vị trí của pixel trong quá trình tính toán, giúp cải thiện độ chính xác của kết quả phân cụm. Thuật toán IPKMeans được triển khai trong 3 giai đoạn: Chuyển đổi dữ liệu, Phân cụm với thuật toán IPKMeans, và Khôi phục kết quả phân cụm ảnh.

4.1. Chi Tiết Các Bước Trong Thuật Toán IPKMeans

Giai đoạn 1: Chuyển đổi dữ liệu ảnh thành dạng chuỗi các hàng, mỗi hàng chứa thông tin vị trí và danh sách giá trị màu của pixel. Giai đoạn 2: Phân cụm với thuật toán IPKMeans (sử dụng hàm mapImage và reduceImage). Giai đoạn 3: Khôi phục lại ảnh kết quả phân cụm bằng cách sử dụng thông tin vị trí, tâm cụm và điểm ảnh thuộc tâm cụm. Theo tài liệu, "Dữ liệu ảnh sẽ được chia thành nhiều mảnh khác nhau. Với mỗi mảnh, dữ liệu được gom cụm dựa trên hàm mapImage(key,value). Hệ thống thực hiện việc này song song trên các mảnh dữ liệu."

4.2. Ưu điểm của IPKMeans so với các thuật toán khác

IPKMeans vượt trội hơn các thuật toán khác như K-Means và PKMeans khi xử lý phân cụm ảnh do những ưu điểm sau: Khả năng xử lý dữ liệu lớn hiệu quả nhờ MapReduce. Cải thiện độ chính xác nhờ sử dụng thông tin vị trí pixel. Thích hợp với các bài toán phân tích ảnh phức tạp. IPKMeans là lựa chọn tốt cho các ứng dụng đòi hỏi độ chính xác cao và khả năng mở rộng tốt.

V. Thực Nghiệm và Đánh Giá Hiệu Suất Phân Cụm Ảnh Với IPKMeans

Để đánh giá hiệu suất của thuật toán IPKMeans, cần thực hiện các thử nghiệm trên các bộ dữ liệu ảnh có kích thước khác nhau. Các kết quả thử nghiệm sẽ được sử dụng để phân tích thời gian thực thi, độ chính xác và khả năng mở rộng của thuật toán. Các chỉ số đánh giá quan trọng bao gồm thời gian tính toán, độ chính xác phân cụm, và đánh giá chất lượng phân cụm bằng các phương pháp phù hợp. So sánh kết quả với các thuật toán khác như K-Means và PKMeans để thấy rõ ưu điểm của IPKMeans.

5.1. Thiết Lập Môi Trường Thử Nghiệm và Bộ Dữ Liệu Ảnh

Môi trường thử nghiệm nên bao gồm một cluster Hadoop với nhiều node để mô phỏng môi trường distributed computing. Bộ dữ liệu ảnh nên đa dạng về kích thước, độ phân giải và nội dung. Sử dụng các công cụ và thư viện hỗ trợ xử lý ảnh và data mining để thực hiện các thử nghiệm một cách hiệu quả. Ghi lại các thông số cấu hình và kết quả thử nghiệm một cách chi tiết để có thể so sánh và phân tích sau này.

5.2. Phân Tích Kết Quả Thực Nghiệm và So Sánh Với Các Thuật Toán

Phân tích thời gian thực thi của IPKMeans trên các bộ dữ liệu ảnh khác nhau để đánh giá khả năng mở rộng của thuật toán. So sánh độ chính xác phân cụm của IPKMeans với K-Means và PKMeans để đánh giá hiệu quả của việc sử dụng thông tin vị trí pixel. Đánh giá chất lượng của kết quả phân cụm bằng các phương pháp như Silhouette Score hoặc Davies-Bouldin Index. Rút ra kết luận về ưu điểm và hạn chế của IPKMeans trong các ứng dụng thực tế.

VI. Kết Luận Hướng Phát Triển Phân Cụm Ảnh trong Tương Lai

K-Means kết hợp với MapReduce, đặc biệt là thuật toán IPKMeans, mang đến giải pháp hiệu quả để phân cụm ảnh trong môi trường big data. Thuật toán này có tiềm năng ứng dụng rộng rãi trong nhiều lĩnh vực. Tuy nhiên, vẫn còn nhiều hướng nghiên cứu và phát triển để cải thiện hiệu suất và độ chính xác. Nghiên cứu cần tập trung vào việc tối ưu hóa các tham số thuật toán, cải thiện khả năng xử lý nhiễu và phát triển các phương pháp đánh giá chất lượng phân cụm tốt hơn. Hướng đến phát triển các mô hình machine learning tích hợp với IPKMeans để tự động điều chỉnh các tham số và nâng cao độ chính xác.

6.1. Các Hướng Nghiên Cứu Tiềm Năng trong Phân Cụm Ảnh

Nghiên cứu các thuật toán phân cụm mới, phù hợp với đặc điểm của dữ liệu ảnh phức tạp. Phát triển các phương pháp tiền xử lý ảnh hiệu quả hơn để giảm nhiễu và tăng độ tương phản. Nghiên cứu các phương pháp kết hợp nhiều thuật toán phân cụm để tận dụng ưu điểm của từng thuật toán. Phát triển các công cụ và nền tảng hỗ trợ phân cụm ảnh big data một cách dễ dàng và hiệu quả.

6.2. Ứng Dụng Tiềm Năng của Phân Cụm Ảnh trong Tương Lai

Phân cụm ảnh sẽ đóng vai trò quan trọng trong các ứng dụng trí tuệ nhân tạo và thị giác máy tính trong tương lai. Ứng dụng trong xe tự lái (nhận diện đường xá, biển báo). Ứng dụng trong y tế (phân tích ảnh y tế, hỗ trợ chẩn đoán bệnh). Ứng dụng trong nông nghiệp (giám sát mùa màng, phát hiện sâu bệnh). Ứng dụng trong giám sát an ninh (nhận diện đối tượng, phát hiện hành vi bất thường).

Trích đoạn nội dung tài liệu

CHƯƠNG 1: TỔNG QUAN VỀ BIGDATA VÀ PHÂN CỤM DỮ LIỆU 1.1 Tổng quan về dữ liệu lớn (Big Data). Định nghĩa: Theo wikipedia: Dữ liệu lớn(Big data) là một thuật ngữ chỉ bộ dữ liệu lớn hoặc phức tạp mà các phương pháp truyền thống không đủ các ứng dụng để xử lý dữ liệu này. Theo Gartner : Dữ liệu lớn là những nguồn thông tin có đặc điểm chung khối lượng lớn, tốc độ nhanh và dữ liệu định dạng dưới nhiều hình thức khác nhau, do đó muốn khai thác được phải đòi hỏi phải có hình thức mới để đưa ra quyết định khám phá và tối ưu hóa quy trình. Nguồn dữ liệu lớn: Dữ liệu đến từ rất nhiều nguồn khác nhau: Hình 1.

Tốc độ gia tăng nguồn dữ liệu. - Dữ liệu lớn được hình thành chủ yếu từ 9 nguồn: [3] (1) Dữ liệu hành chính (phát sinh từ chương trình của một tổ chức, có thể là chính phủ hay phi chính phủ). Ví dụ: hồ sơ y tế điện tử ở bệnh viện, hồ sơ bảo hiểm,. Ví dụ: các giao dịch thẻ tín dụng, giao dịch trên mạng, … SVTH: VŨ THỊ HƯỜNG 11 LỚP: 57TH2 Đồ Án Tốt Nghiệp Khoa Công Nghệ Thông Tin (3) Dữ liệu từ các thiết bị cảm biến như thiết bị chụp hình ảnh vệ tinh, cảm biến đường, cảm biến khí hậu.

(4) Dữ liệu từ các thiết bị theo dõi. Ví dụ theo dõi dữ liệu từ điện thoại di động. (5) Dữ liệu từ các hành vi. Ví dụ như tìm kiếm trực tuyến (tìm kiếm sản phẩm, dịch vụ hay thông tin khác), đọc các trang mạng trực tuyến,.

(6) Dữ liệu từ các thông tin về ý kiến, quan điểm của các cá nhân, tổ chức, trên các phương tiện thông tin xã hội. (7) Dữ liệu điện lực bao gồm các thông tin cụ thể từ các điểm giao nhau của các nút thông tin sử dụng. (8) Dữ liệu các thiết bị tìm kiếm, công cụ tìm kiếm có cơ sở dữ liệu cực kỳ rộng lớn, nơi họ có thể tìm thấy dữ liệu họ cần. Xu hướng doanh thu từ phân tích dữ liệu lớn đem lại.

Thị trường dữ liệu lớn toàn cầu được dự báo sẽ tăng lên 103 tỷ USD vào năm 2027, gấp đôi quy mô thị trường dự kiến vào năm 2018. Đặc trưng cơ bản của dữ liệu lớn [3]. SVTH: VŨ THỊ HƯỜNG 12 LỚP: 57TH2 Đồ Án Tốt Nghiệp Khoa Công Nghệ Thông Tin Hình 3. Đặc trưng của dữ liệu lớn.

(1) Khối lượng lớn (Volume): - Khối lượng dữ liệu rất lớn là đặc điểm tiêu biểu nhất của dữ liệu lớn và dữ liệu đang ngày càng tăng lên. - Kích cỡ tính đến 2014 thì có thể trong khoảng vài trăm terabyte (1 petabyte = 1024 terabyte) chỉ cho 1 tập hơn dữ liệu. - Sử dụng công nghệ “đám mây” mới có khả năng lưu trữ được dữ liệu lớn. - Xử lý dữ liệu nhanh ở mức thời gian thực (real-time), có nghĩa dữ liệu được xử lý ngay tức thời sau khi chúng được phát sinh.

(3) Đa dạng (Variety): - Dữ liệu truyền thống chúng ta hay nói đến dữ liệu có cấu trúc. - Ngày nay hơn 80% dữ liệu được sinh ra là phi cấu trúc( tài liệu, blog, hình ảnh,.) - Big data cho phép liên kết và phân tích nhiều dạng dữ liệu khác nhau. (4) Độ tin cậy/chính xác (Veracity): - Một trong những tính chất phúc tạp nhất của BigData là độ tin cậy/chính xác của dữ liệu. SVTH: VŨ THỊ HƯỜNG 13 LỚP: 57TH2 Đồ Án Tốt Nghiệp Khoa Công Nghệ Thông Tin - Xu hướng phương tiện truyền thông xã hội và mạng xã hội ngày nay và sự gia tăng mạng mẽ tính tương tác và chia sẻ của người dùng mobile làm cho bức trang xác định về độ tin cậy và chính xác của dữ liệu ngày một khó khăn hơn.

- Bài toán phân tích và loại bỏ dữ liệu thiếu chính xác và nhiễu đang là tính chất quan trọng của bigdata. (5) Giá trị(Value): - Là đặc điểm quan trọng nhất của dữ liệu lớn. Trước khi làm phân tích dữ liệu lớn thì việc đầu tiên là lảm rõ, xác định rõ được giá trị của thông tin mang lại ra sao. - Kết quả dự báo chính xác thể hiện rõ nét nhất về giá trị của dữ liệu lớn mang lại.2 Tổng quan về phân tích dữ liệu lớn.

✯Nhiệm vụ khoa học công nghệ dữ liệu lớn: - Quản trị dữ liệu (Data management): Lưu trữ, bảo trì và truy nhập các nguồn dữ liệu lớn. - Mô hình hoá và phân tích dữ liệu (Big Modeling and analytics): Tìm cách hiểu được dữ liệu và tìm ra các thông tin hoặc tri thức quý báu từ dữ liệu. - Trao đổi, hiển thị dữ liệu và kết quả phân tích dữ liệu (Visualization Decisions and Values) để tạo ra sản phẩm giá trị. ✯ Quản lý dữ liệu lớn: Hình 4.

Công cụ quản lý dữ liệu lớn. SVTH: VŨ THỊ HƯỜNG 14 LỚP: 57TH2 Đồ Án Tốt Nghiệp Khoa Công Nghệ Thông Tin Ứng dụng của dữ liệu lớn: - Được ứng dụng trong nhiều lĩnh vực như: + Hoạt động chính trị. … Yêu cầu khi phân tích dữ liệu lớn. - Khả năng mở rộng: Hệ thống có khả năng đối phó với sự tăng trưởng của dữ liệu, tính toán và độ phức tạp.

- Hiệu suất vào ra dữ liệu: Tốc độ truyền dữ liệu giữa hệ thống và thiết bị ngoại vi. - Khả năng chấp nhận lỗi: Khả năng tiếp tục hoạt động đúng trong trường hợp thất bại của một hay nhiều thành phần. - Xử lý thời gian thực: Khả năng xử lý dữ liệu và đưa ra kết quả chính xác trong những ràng buộc thời gian nhất định. - Hỗ trợ kích thước dữ liệu: Kích thước của dữ liệu mà hệ thống có thể xử lý tốt.

- Hỗ trợ tác vụ lặp: Hệ thống hỗ trợ hiệu quả tác vụ lặp. ✯Công nghệ chính trong phân tích dữ liệu lớn: Tính toán phân tán, tính toán song song, song song hóa bằng CPU đa nhân, xử lý phân tán với hệ thống cluster, xử lý phân tán trên cloud. Công cụ hỗ trợ phân tích dữ liệu lớn. Big Data là một tập hợp dữ liệu mà không thể phân tích/khai thác theo các phương pháp truyền thống.

Do đó việc kiểm thử trên các tập dữ liệu lớn cũng cần sử dụng nhiều công cụ, kỹ thuật và nền tảng đặc thù khác nhau. Công nghệ phân tích dữ liệu lớn. Big Data Big Data Tools NoSQL Databases MongoDB, Cassandra, Redis, ZooKeeper, Hbase MapReduce Hadoop, Hive, Pig, Cascading, Kafka, S4, MapR, Flume SVTH: VŨ THỊ HƯỜNG 15 LỚP: 57TH2 Đồ Án Tốt Nghiệp Khoa Công Nghệ Thông Tin Storage S3, HDFS ( Hadoop Distributed File System) Servers Elastic, Heroku, Elastic, Google App Engine, EC2 Processing R, Yahoo! Pipes, Mechanical Turk, BigSheets, Datamee Lợi ích của khai thác dữ liệu lớn: - Tiết kiệm chi phí. - Tiết kiệm thời gian và giúp tối ưu hoá sản phẩm.

- Hỗ trợ con người đưa ra những quyết định đúng và hợp lý hơn.2 Tổng quan về phân cụm dữ liệu. • Khái niệm: Ở một mức cơ bản nhất, người ta đã đưa ra định nghĩa phân cụm dữ liệu (PCDL) như sau: [3] "Phân cụm dữ liệu là một kỹ thuật trong khai phá dữ liệu (Data mining), 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 tâm trong tập dữ liệu lớn, từ đó cung cấp thông tin, tri thức hữu ích cho ra quyết định.” • Mục đích: Quá trình PCDL là quá trình phân chia một tập dữ liệu ban đầu thành các cụm dữ liệu sao các phần tử trong cùng một cụm thì “tương tự” nhau và các phần tử khác cụm nhau thì “phi tương tự nhau”. Minh họa quá trình phân cụm. • Giải quyết vấn đề: Một số bài toán học máy không giám sát như tìm kiếm, phát hiện các cụm, các mẫu dữ liệu trong một tập hợp dữ liệu ban đầu, các dữ liệu không SVTH: VŨ THỊ HƯỜNG 16 LỚP: 57TH2 Đồ Án Tốt Nghiệp Khoa Công Nghệ Thông Tin có nhãn.

• Quá trình phân cụm dữ liệu: Hình 6. Quá trình phân cụm dữ liệu. (1) Lựa chọn đặc trưng: Các đặc trưng được chọn một cách hợp lý để có thể "mã hóa" nhiều nhất thông tin liên quan đến công việc quan tâm. => Mục tiêu chính là: Giảm thiểu độ dư thừa thông tin giữa các đặc trưng.

+ Chọn độ đo tương tự: Đưa ra mức độ tương tự hay không tương tự giữa hai vector đặc trưng góp phần như nhau trong việc tính toán. + Tiêu chuẩn phân cụm: Có thể diễn đạt bởi kinh nghiệm của chuyên gia, cũng có thể được diễn đạt bởi hàm chi phí hay loại quy tắc khác. (2) Thuật toán phân cụm: Lựa chọn 1 thuật toán phân cụm riêng biệt nhằm làm sáng tỏ cấu trúc cụm của tập dữ liệu. (3) Đánh giá cụm: Khi đã có kết quả phân cụm thì tiến hành kiểm tra tính đúng đắn của nó.

Bằng việc dùng các kiểm định phù hợp. (4) Giải thích kết quả: Trong nhiều trường hợp, phải kết hợp giữa kết quả phân loại với bằng chứng thực nghiệm và phân tích để đưa ra các kết luận đúng đắn. • Thế nào là phân cụm tốt? SVTH: VŨ THỊ HƯỜNG 17 LỚP: 57TH2 Đồ Án Tốt Nghiệp Khoa Công Nghệ Thông Tin - Một phương pháp phân cụm tốt sẽ sinh ra các cụm có chất lượng cao [3], trong đó: + Mức độ tương tự giữa các đối tượng trong cùng một cụm là cao. + Mức độ tương tự giữa các đối tượng nằm trong các cụm khác nhau là thấp.

- Chất lượng của kết quả phân cụm phụ thuộc vào cả độ đo tương tự được sử dụng và cách thức thực hiện. - Chất lượng của phương pháp phân cụm cũng được đánh giá bởi khả năng phát hiện các mẫu tiềm ẩn. ✯ Một số ví dụ về phân cụm dữ liệu. Phân cụm được ứng dụng trong nhiều lĩnh vực.

Ví dụ như: Hình 7. Minh hoạ một số ví dụ phân cụm. (1) Xử lý dữ liệu lớn: Việc khám phá tri thức trong các cơ sở dữ liệu thường phải xử lý khối lượng dữ liệu rất lớn, nhiều khi ngay cả các thuật toán với độ phức tạp tính toán là đa thức cũng không dùng được. Do đó, việc phân và xử lý theo các cụm là một giải pháp hữu hiệu.

SVTH: VŨ THỊ HƯỜNG 18 LỚP: 57TH2 Đồ Án Tốt Nghiệp Khoa Công Nghệ Thông Tin (2) Phân cụm dữ liệu trong hoạt động phân đoạn ảnh: Phân đoạn ảnh là việc phân tích mức xám hay màu của ảnh thành lát đồng nhất. (3) Tạo giả thuyết: Phân tích cụm được sử dụng để suy ra một số giả thuyết liên quan đến dữ liệu. (4) 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 và những đặc tả họ từ các bản ghi mua bán trong cơ sở dữ liệu khách hàng.