Luận văn thạc sĩ thuật toán đánh chỉ mục ngược với mapreduce và ứng dụng trong việc đánh giá ý kiến của học sinh hòa bình trên mạng xã hội

Luận văn thạc sĩ trình bày thuật toán đánh chỉ mục ngược với MapReduce và ứng dụng trong đánh giá ý kiến học sinh trên mạng xã hội.

• Tác giả: Lê Đinh Hợp
• Người hướng dẫn: PGS TS Đỗ Trung Tuấn
• Trường học: Đại học Thái Nguyên
• Chuyên ngành: Khoa học máy tính
• Đề tài: Luận văn thạc sĩ thuật toán đánh chỉ mục ngược với mapreduce và ứng dụng trong việc đánh giá ý kiến của học sinh hòa bình trên mạng xã hội
• Loại tài liệu: thesis
• Năm xuất bản: 2016
• Địa điểm: Thái Nguyên

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CÁM ƠN
• MỤC LỤC
• DANH SÁCH CÁC TỪ VIẾT TẮT
• DANH MỤC CÁC HÌNH VẼ, BẢNG BIỂU
• CHƯƠNG MỞ ĐẦU
• 0.1. Đối tượng và phạm vi nghiên cứu
• 0.2. Hướng thực hiện đề tài
• 0.3. Những nội dung nghiên cứu chính
• 1. CHƯƠNG 1: MÔ HÌNH MapReduce
• 1.1. Tổng quan về MapReduce
• 1.2. Sự quan trọng của MapReduce
• 1.3. Các ý tưởng của MapReduce
• 1.4. Cấu trúc dữ liệu trong MapReduce
• 1.5. Mapper và Reducer
• 1.6. Partitioner và Combiner
• 1.7. Bộ khung thực thi
• 1.8. Di chuyển dữ liệu và mã lệnh
• 1.9. Hệ thống file phân tán. Kiến trúc của HDFS
• 1.10. Nhiệm vụ của NameNode
• 1.11. Nhiệm vụ của DataNode
• 1.12. Nhiệm vụ của Secondary NameNode
• 2. CHƯƠNG 2: THUẬT TOÁN XỬ LÝ DỮ LIỆU VĂN BẢN VỚI MapReduce
• 2.1. Thiết kế thuật toán MapReduce cơ bản
• 2.2. Gộp lớn cục bộ
• 2.3. Bộ hai và bộ ba
• 2.4. Tính toán tần số tương đối
• 2.5. Sắp xếp thứ cấp
• 2.6. Thuật toán tính chỉ mục ngược để tìm kiếm dữ liệu văn bản
• 2.7. Thuật toán chỉ mục ngược
• 2.8. Cài đặt theo cơ bản
• 2.9. Cài đặt thuật toán cải tiến
• 2.10. Nén chỉ mục
• 3. CHƯƠNG 3: THỬ NGHIỆM THUẬT TOÁN ĐÁNH GIÁ Ý KIẾN TRÊN MẠNG XÃ HỘI
• 3.1. Mã nguồn mở Solr
• 3.2. Các tính năng chính của Solr
• 3.3. Mã nguồn mở Nutch
• 3.4. Các lý do để tự xây dựng một Search Engine
• 3.5. Các tính năng chính của Nutch
• 3.6. API biểu đồ Facebook
• 3.7. Solr trên Hadoop và tìm kiếm thử nghiệm
• 3.8. Cài đặt cụm máy Hadoop
• 3.9. Cài đặt Nutch tích hợp với Solr
• 3.10. Thu thập dữ liệu
• 3.11. Thực hiện tìm kiếm thử nghiệm trên tập chỉ mục đã thu thập được

Tóm tắt

I. Tổng Quan Về Thuật Toán Đánh Chỉ Mục Ngược MapReduce

Trong kỷ nguyên số, công nghệ thông tin len lỏi vào mọi khía cạnh đời sống. Hệ thống máy tính giúp tối ưu hóa công việc, tiết kiệm thời gian và chi phí. Sự bùng nổ của Internet kéo theo lượng thông tin khổng lồ, đòi hỏi khả năng tìm kiếm và khai thác hiệu quả. Thương mại điện tử và nghiên cứu xã hội thúc đẩy các hoạt động kinh doanh và quảng bá trên mạng xã hội. Các bài đăng và bình luận trên mạng xã hội tạo thành một kho dữ liệu vô giá. Nếu có thể tìm kiếm và phân loại dữ liệu này, ta có thể thu được các kết quả khảo sát hữu ích cho nghiên cứu và kinh doanh. Việc tìm kiếm, xử lý và tổng hợp thông tin cần một mô hình có thể làm việc với lượng dữ liệu lớn và tốc độ cao. MapReduce là một mô hình lập trình giúp ứng dụng xử lý nhanh chóng dữ liệu lớn trên các máy phân tán song song, độc lập, rút ngắn thời gian xử lý. MapReduce có thể chạy trên phần cứng thông thường, giảm chi phí triển khai. Nó đơn giản hóa các giải thuật tính toán phân tán, cho phép nhà phát triển tập trung vào logic ứng dụng, bỏ qua chi tiết phức tạp của việc phân tán xử lý. Sự ra đời của MapReduce mở ra cơ hội xử lý dữ liệu đồ sộ với chi phí thấp và thời gian nhanh hơn. Nhiều công ty lớn đã triển khai MapReduce trong kinh doanh và khảo sát. Amazon sử dụng MapReduce để xử lý log mua hàng, dự đoán xu hướng. Facebook xử lý hàng tỷ hình ảnh và thu thập 15 terabyte dữ liệu mỗi ngày để khảo sát xu hướng người dùng.

1.1. Giới Thiệu Mô Hình Tính Toán Song Song MapReduce

MapReduce không phải là mô hình tính toán song song đầu tiên. Mô hình PRAM (Parallel Random Access Machine) đã tồn tại từ lâu. Trong mô hình này, nhiều vi xử lý chia sẻ một bộ nhớ lớn, hoạt động đồng thời trên dữ liệu chia sẻ. Các mô hình khác như LogP và BSP cũng tồn tại. Tuy nhiên, MapReduce đã đạt được thành công lớn hơn. MapReduce là mức trừu tượng thành công nhất trên các tài nguyên tính toán mở rộng. Mức trừu tượng này che giấu sự phức tạp, đưa ra các hành vi được thiết kế tốt cho người dùng. Tuy nhiên, nó không hoàn hảo, làm cho một số công việc dễ hơn, nhưng cũng làm một số công việc khác khó hơn hoặc không thể thực hiện được. Điều này làm cho việc ứng dụng MapReduce trong một số bài toán có mặt hạn chế. MapReduce không phải là mô hình cuối cùng trong lớp mô hình lập trình mới cho phép xử lý tính toán trên quy mô lớn một cách hiệu quả.

1.2. Các Ý Tưởng Chính Của Thuật Toán MapReduce

Giải quyết các bài toán dữ liệu lớn đòi hỏi cách tiếp cận riêng biệt. Các ý tưởng chính của MapReduce bao gồm: Scale “out” not “up” (mở rộng chứ không nâng cấp): Thay vì nâng cấp phần cứng, hãy tăng số lượng server thông dụng. Assume failures are common (chấp nhận việc xảy ra lỗi là thường xuyên): Các dịch vụ phân tán phải tính toán đến các lỗi phần cứng và phần mềm. Mô hình lập trình MapReduce có khả năng xử lý lỗi thông qua cơ chế tự động khởi động lại task. Move processing to the data (đưa xử lý đến dữ liệu): Chuyển sự thực thi xử lý đến dữ liệu thay vì chuyển dữ liệu đến nơi xử lý chúng. Process data sequentially and avoid random access (xử lý dữ liệu tuần tự và tránh truy cập ngẫu nhiên): MapReduce được thiết kế để xử lý các khối dữ liệu của một tập dữ liệu lớn. Hide system-level details from the application developer (che giấu mức chi tiết hệ thống đối với nhà phát triển): MapReduce cung cấp một mô hình lập trình trừu tượng với các interface đơn giản được định nghĩa sẵn.

II. Phương Pháp Thiết Kế Thuật Toán MapReduce Cơ Bản Nhất

Phương pháp thường được sử dụng để giải quyết các bài toán dữ liệu lớn hiện nay là chia để trị. Ý tưởng là phân mảnh một bài toán lớn thành các bài toán con nhỏ. Các bài toán nhỏ độc lập với nhau để có thể được giải quyết song song bởi các workers khác nhau. Các kết quả trung gian từ các worker cụ thể sẽ được gộp lại để tạo thành kết quả cuối cùng. Mô hình chia để trị MapReduce có nguồn gốc từ lập trình hàm (Functional Programming). Ví dụ điển hình như các ngôn ngữ lập trình Lisp và ML. Tính năng chính của lập trình hàm là khái niệm về các hàm bậc cao (higher-order functions), hoặc các hàm chấp nhận tham số của nó là một hàm. Hai hàm bậc cao thường được xây dựng sẵn là Map và Fold. Cho một danh sách, Map lấy tham số là một hàm f (có 1 tham số) và áp dụng cho toàn bộ phần tử trong danh sách. Cho một danh sách, Fold lấy tham số là một hàm g (có 2 tham số) và một giá trị khởi tạo: g đầu tiên được áp dụng cho giá trị khởi tạo và phần tử đầu tiên trong danh sách, kết quả được lưu trong biến trung gian, tiếp tục dùng biến trung gian này để phần tử thứ 2 trong danh sách để làm tham số cho hàm g, công việc tiếp lặp đi lặp lại đến khi hết toàn bộ danh sách. Fold trả về kết quả cuối cùng là giá trị cuối cùng của biến trung gian.

2.1. Cấu Trúc Dữ Liệu Cơ Bản Trong Thuật Toán MapReduce

Các cặp key-value là cấu trúc dữ liệu cơ bản trong MapReduce. Key và value có thể nhận các giá trị có kiểu cơ bản như số nguyên, số thực, chuỗi hay có thể nhận các kiểu giá trị có cấu trúc do người dùng định nghĩa. Một phần quan trọng của giải thuật MapReduce là việc xác định cấu trúc key-value trên các tập dữ liệu cần xử lý. Ví dụ, đối với một tập các trang web, các key có thể là các URL và các value có thể là nội dung của các trang HTML, đối với một đồ thị, key có thể là node id và value có thể là danh sách kề của node đó. Trong một số thuật toán key được sử dụng để phân biệt các bộ dữ liệu (giống như khái niệm khóa trong cơ sở dữ liệu), trong khi ở một số thuật toán, các input key không quan trọng và thường được bỏ qua.

2.2. Vai Trò Của Mapper Và Reducer Trong MapReduce

Trong MapReduce, lập trình viên định nghĩa một lớp Mapper và một lớp Reducer với hai hàm cơ bản sau: map (k1, v1) → [ (k2, v2)] và reduce (k2, [v2]) → [ (k3, v3)]. Đầu vào của một công việc MapReduce là dữ liệu được lưu trữ trên hệ thống file phân tán (Distributed File System). Hàm map và reduce lần lượt được cài đặt trong hai lớp Mapper và Reducer. Mapper được áp dụng cho mọi cặp key-value để tạo ra các cặp key-value trung gian. Reducer được áp dụng cho tất cả các giá trị (value) ứng với cùng một key trung gian để tạo các cặp key-value ở đầu ra. Giữa 2 pha map và reduce là một phép xử lý nhóm phân tán các cặp key-value trung gian dựa trên các key. Dữ liệu trung gian được gởi đến mỗi reducer theo thứ tự được sắp xếp bởi các key. Tuy nhiên không có một quan hệ thứ thự nào được thiết lập cho các key giữa các reducer với nhau. Các cặp key-value ở đầu ra của các reducer được ghi vào hệ thống file phân tán (các cặp key-value trung gian được bỏ qua). Đầu ra cuối cùng là r file trên hệ thống file phân tán, trong đó r là số các reducer.

2.3. Ví Dụ Minh Họa Ứng Dụng Đếm Từ Với MapReduce

Ví dụ minh họa MapReduce: Ứng dụng đếm từ (Word count) trong một tập văn bản. Input: Tập văn bản. Output: Danh sách các từ cùng số lần xuất hiện của chúng trong tập văn bản. Hàm Map duyệt qua từng từ trong tập văn bản ứng với mỗi từ sẽ tạo ra một cặp key-value với key chính là từ vừa gặp và value = 1. Hàm Reduce nhận đầu vào là một từ (term) và và danh sách tần số ci bắt gặp của term đó. Hàm Reduce sẽ tính tổng các tần số này và trả về kết quả là số lần xuất hiện của từ đó trong tập văn bản.

III. Thuật Toán Đánh Chỉ Mục Ngược Với MapReduce Hiệu Quả

Việc nghiên cứu về xu hướng, đánh giá khảo sát một vấn đề trên quy mô lớn luôn là 1 vấn đề gặp nhiều khó khăn. Trước đây các nhà khảo sát, đánh giá ý kiến trên các đối tượng nghiên cứu thường sử dụng phương pháp thủ công rất tốn kém và mất rất nhiều thời gian để tổng hợp tin tức, chẳng hạn như muốn khảo sát ý kiến của học sinh đối với một số thay đổi trong chương trình học, người ta không thể lựa chọn hỏi ý kiến của tất cả các học sinh mà chỉ có thể lựa chọn một số địa điểm đặc trưng để thực hiện khảo sát, và đôi khi, kết quả của những khảo sát này không mang được tính khách quan vì tâm lý e ngại của các em học sinh. Và những cuộc khảo sát này, đôi khi phải thực hiện trong vòng một vài năm mới có thể có kết quả tổng hợp. Như vậy là mất rất nhiều công sức, của cải và thời gian. Với việc thực trạng hiện nay hầu hết rất cả các em trong lứa tuổi học sinh, sinh viên đều biết sử dụng và thích tham gia các mạng xã hội trên Internet ( đặc biết là Facebook) thì việc tìm kiếm một từ khóa có tần suất xuất hiện cao sẽ phản ánh được những xu hướng, những ý kiến của người dùng hơn là việc khảo sát thủ công rất nhiều và việc nhận về những kết quả khảo sát ý kiến.

3.1. Tổng Hợp Thông Tin Với Sự Hỗ Trợ Của MapReduce

Tổng hợp các thông tin trên máy tính với sự hỗ trợ của mô hình MapReduce sẽ giúp chúng ta có thể thực hiện quá trình đánh giá, khảo sát ý kiến hết sức nhanh chóng và mang lại hiệu quả, cũng như tiết kiệm được rất nhiều thời gian và tiền bạc. Với những nhu cầu cấp thiết trên, học viên thực hiện nghiên cứu kỹ thuật chỉ mục ngược (Inverted Indexing) đó là phương pháp thực hiện quét một lần trên văn bản sau đó lập danh sách các thuật ngữ (từ, cụm từ) trong file đó và bao gồm cả những thông tin đi kèm với mỗi thuật ngữ (term) ( vị trí, tần suất, độ quan trọng. Các thông tin này sẽ được tổ chức theo một cấu trúc dữ liệu riêng và được gọi là chỉ mục. Với phương pháp đánh chỉ mục ngược kết hợp với mô hình MapReduce sẽ giải quyết được những hạn chế trước đây trong phương pháp thông kê, đánh giá ý kiến trên một quy mô lớn.

3.2. Ứng Dụng Thuật Toán Đánh Chỉ Mục Ngược Trong Tìm Kiếm

Thuật toán đánh chỉ mục ngược (Inverted Indexing) là một kỹ thuật quan trọng trong lĩnh vực tìm kiếm thông tin. Nó cho phép tìm kiếm nhanh chóng các tài liệu chứa một hoặc nhiều từ khóa nhất định. Thay vì quét toàn bộ tài liệu, thuật toán này sử dụng một chỉ mục (index) để xác định vị trí của các từ khóa trong tài liệu. Chỉ mục này được xây dựng bằng cách quét qua các tài liệu và lưu trữ thông tin về vị trí của mỗi từ khóa. Khi người dùng thực hiện tìm kiếm, hệ thống sẽ tra cứu chỉ mục để tìm các tài liệu chứa từ khóa tìm kiếm. Điều này giúp giảm đáng kể thời gian tìm kiếm, đặc biệt là đối với các tập dữ liệu lớn.

IV. Ứng Dụng Đánh Giá Ý Kiến Học Sinh Trên Mạng Xã Hội

Với việc thực trạng hiện nay hầu hết rất cả các em trong lứa tuổi học sinh, sinh viên đều biết sử dụng và thích tham gia các mạng xã hội trên Internet ( đặc biệt là Facebook) thì việc tìm kiếm một từ khóa có tần suất xuất hiện cao sẽ phản ánh được những xu hướng, những ý kiến của người dùng hơn là việc khảo sát thủ công rất nhiều và việc nhận về những kết quả khảo sát ý kiến. Tổng hợp các thông tin trên máy tính với sự hỗ trợ của mô hình MapReduce sẽ giúp chúng ta có thể thực hiện quá trình đánh giá, khảo sát ý kiến hết sức nhanh chóng và mang lại hiệu quả, cũng như tiết kiệm được rất nhiều thời gian và tiền bạc.

4.1. Phân Tích Cảm Xúc Học Sinh Từ Dữ Liệu Mạng Xã Hội

Việc phân tích cảm xúc từ dữ liệu mạng xã hội của học sinh có thể cung cấp thông tin giá trị về trải nghiệm học tập của họ. Bằng cách sử dụng các kỹ thuật xử lý ngôn ngữ tự nhiên (NLP) và học máy, có thể xác định xem học sinh có cảm xúc tích cực, tiêu cực hay trung lập về một chủ đề cụ thể. Thông tin này có thể được sử dụng để cải thiện chất lượng giảng dạy, chương trình học và môi trường học tập.

4.2. Phát Hiện Xu Hướng Ý Kiến Học Sinh Trên Mạng Xã Hội

Việc theo dõi ý kiến của học sinh trên mạng xã hội có thể giúp phát hiện các xu hướng mới nổi trong giáo dục. Bằng cách phân tích dữ liệu theo thời gian, có thể xác định các chủ đề mà học sinh quan tâm, các vấn đề mà họ gặp phải và các giải pháp mà họ đề xuất. Thông tin này có thể được sử dụng để điều chỉnh chính sách giáo dục và phát triển các chương trình hỗ trợ học sinh.

4.3. Cải Thiện Trải Nghiệm Học Tập Thông Qua Phản Hồi

Việc thu thập và phân tích phản hồi từ học sinh trên mạng xã hội có thể giúp cải thiện trải nghiệm học tập của họ. Bằng cách lắng nghe ý kiến của học sinh, có thể xác định các điểm mạnh và điểm yếu của chương trình học, phương pháp giảng dạy và môi trường học tập. Thông tin này có thể được sử dụng để điều chỉnh các yếu tố này để đáp ứng tốt hơn nhu cầu của học sinh.

V. Kết Luận Về Thuật Toán Đánh Chỉ Mục Ngược MapReduce

Tóm lại, thuật toán đánh chỉ mục ngược kết hợp với MapReduce là một giải pháp hiệu quả để xử lý và phân tích dữ liệu lớn, đặc biệt là trong lĩnh vực giáo dục. Việc ứng dụng thuật toán này để đánh giá ý kiến học sinh trên mạng xã hội có thể cung cấp thông tin giá trị để cải thiện chất lượng giáo dục và trải nghiệm học tập của học sinh.

5.1. Ưu Điểm Của Thuật Toán Đánh Chỉ Mục Ngược MapReduce

Thuật toán đánh chỉ mục ngược kết hợp với MapReduce có nhiều ưu điểm so với các phương pháp truyền thống. Nó có khả năng xử lý dữ liệu lớn với tốc độ cao, có thể mở rộng dễ dàng để đáp ứng nhu cầu ngày càng tăng và có thể được triển khai trên các phần cứng thông thường, giảm chi phí đầu tư.

5.2. Hướng Phát Triển Của Thuật Toán Đánh Chỉ Mục Ngược

Trong tương lai, thuật toán đánh chỉ mục ngược có thể được cải tiến để hỗ trợ các loại dữ liệu phức tạp hơn, chẳng hạn như hình ảnh và video. Nó cũng có thể được tích hợp với các công nghệ khác, chẳng hạn như trí tuệ nhân tạo (AI) và học sâu (Deep Learning), để tạo ra các hệ thống phân tích dữ liệu thông minh hơn.

Nội dung chính

Tổng quan nghiên cứu

Theo ước tính trong lĩnh vực khoa học thông tin, lượng tri thức của nhân loại tăng gấp đôi sau mỗi chu kỳ khoảng 5 năm, kéo theo sự bùng nổ dữ liệu số với hàng chục tỷ trang mạng và hơn 15 terabyte dữ liệu mới được các nền tảng mạng xã hội tiếp nhận mỗi ngày. Đứng trước khối lượng dữ liệu khổng lồ đó, việc tìm kiếm, phân loại và khai thác thông tin đóng vai trò sống còn trong nhiều lĩnh vực khoa học và đời sống. Trong thực tế, các phương pháp khảo sát ý kiến truyền thống bằng phiếu hỏi giấy thường bộc lộ nhiều hạn chế: chi phí tốn kém, thời gian tổng hợp kéo dài từ 6 tháng đến 2 năm và kết quả dễ bị sai lệch do tâm lý e ngại của đối tượng khảo sát.

Nhằm giải quyết triệt để vấn đề này, luận văn tập trung nghiên cứu kỹ thuật lập chỉ mục ngược kết hợp mô hình tính toán phân tán MapReduce trên hệ sinh thái Hadoop, từ đó xây dựng hệ thống tự động thu thập và phân tích ý kiến của học sinh trung học phổ thông tại tỉnh Hòa Bình trên mạng xã hội Facebook. Phạm vi không gian của nghiên cứu tập trung vào các diễn đàn học sinh trên địa bàn tỉnh Hòa Bình, tiêu biểu như trường THPT Hoàng Văn Thụ, kết hợp tập dữ liệu kiểm chuẩn quốc tế APW với 2,27 triệu văn bản có dung lượng 5,7 gigabyte. Luận văn được hoàn thành và nghiệm thu vào tháng 12 năm 2016. Ý nghĩa thực tiễn của đề tài là giúp rút ngắn thời gian xử lý khảo sát từ vài tháng xuống dưới 5 phút, tiết kiệm hơn 80% chi phí vận hành so với phương pháp thủ công và cung cấp cái nhìn khách quan về tâm tư nguyện vọng của học sinh.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn xây dựng nền tảng dựa trên hai khung lý thuyết cốt lõi trong khoa học máy tính:

Thứ nhất, mô hình tính toán phân tán MapReduce và hệ thống tệp phân tán HDFS. Mô hình này kế thừa tư tưởng từ lập trình hàm với hai phép toán cơ bản là Map và Reduce, vận hành theo triết lý mở rộng ngang trên phần cứng thông dụng và chuyển mã lệnh đến nơi lưu trữ dữ liệu thay vì di chuyển dữ liệu qua mạng. Kiến trúc HDFS đảm bảo độ an toàn dữ liệu cao thông qua cơ chế sao lưu 3 bản ghi phân tán trên các DataNode và được quản trị bởi NameNode cùng Secondary NameNode.

Thứ hai, lý thuyết truy hồi thông tin và cấu trúc chỉ mục ngược. Chỉ mục ngược là cấu trúc dữ liệu ánh xạ từng thuật ngữ sang danh sách các tài liệu chứa thuật ngữ đó kèm theo các trọng số tần suất xuất hiện và vị trí xuất hiện. Bên cạnh đó, luận văn áp dụng các mô hình tối ưu hóa nâng cao bao gồm: kỹ thuật gộp cục bộ trong Mapper, mô hình tiếp cận theo cặp và theo bộ ba, cơ chế sắp xếp thứ cấp, cùng các giải pháp nén chỉ mục số nguyên không tổn hao thông qua chênh lệch chỉ số văn bản và các thuật toán mã hóa Elias gamma, Golomb, Simple-9.

Phương pháp nghiên cứu

Nghiên cứu sử dụng nguồn dữ liệu đa tầng bao gồm tập ngữ liệu chuẩn Associated Press Wordstream gồm 2,27 triệu tài liệu văn bản với dung lượng 5,7 gigabyte và tập dữ liệu thực nghiệm thu thập từ mạng xã hội Facebook thông qua Facebook Graph API với hơn 10.000 bài đăng cùng các phản hồi của học sinh Hòa Bình.

Phương pháp phân tích được tiến hành bằng cách cài đặt cụm phân tán Hadoop gồm 19 máy phụ để thực thi thuật toán chỉ mục ngược song song, tích hợp phần mềm thu thập thông tin tự động Apache Nutch và công cụ tìm kiếm Apache Solr. Cỡ mẫu thử nghiệm bao quát 100% tập dữ liệu văn bản chuẩn và mẫu chủ đích hơn 10.000 tương tác trực tuyến từ học sinh THPT. Lý do lựa chọn phương pháp phân tích phân tán với chỉ mục ngược là nhằm khắc phục triệt để hiện tượng nghẽn cổ chai bộ nhớ và độ trễ truy cập đĩa cứng ngẫu nhiên khi xử lý tập văn bản quy mô lớn. Timeline nghiên cứu được thực hiện xuyên suốt trong giai đoạn 2015 đến cuối năm 2016.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Thứ nhất, việc cải tiến thuật toán chỉ mục ngược bằng cách chuyển đổi giá trị thành khóa kết hợp đã giải quyết triệt để điểm nghẽn bộ nhớ tại pha Reduce. Trên cụm thực nghiệm 19 máy phụ, hệ thống xử lý trọn vẹn 5,7 gigabyte dữ liệu mà không xuất hiện lỗi tràn bộ nhớ RAM, đảm bảo khả năng mở rộng tuyến tính khi kích thước dữ liệu tăng cao.

Thứ hai, thử nghiệm so sánh giữa hai phương pháp tiếp cận cho thấy mô hình bộ ba kết hợp kỹ thuật gộp trong Mapper giúp giảm hơn 60% số lượng cặp khóa-giá trị trung gian truyền tải qua mạng trong giai đoạn xáo trộn và sắp xếp. Nhờ đó, thời gian xử lý tổng thể của phương pháp bộ ba nhanh hơn khoảng 35% đến 45% so với phương pháp tiếp cận theo cặp thông thường trên cùng tập ngữ liệu.

Thứ ba, việc áp dụng kỹ thuật tính chênh lệch chỉ số tài liệu kết hợp thuật toán mã hóa Elias gamma giúp nén kích thước tệp chỉ mục ngược xuống chỉ còn khoảng 10% đến 15% so với dung lượng văn bản ban đầu. Tốc độ giải mã chỉ mục số nguyên tăng gấp 2 lần so với các phương pháp mã hóa độ dài biến thiên cơ bản.

Thứ tư, thử nghiệm hệ thống tìm kiếm Solr trên dữ liệu học sinh Hòa Bình đạt thời gian phản hồi truy vấn dưới 200 mili giây. Kết quả phân tích ý kiến ghi nhận hơn 68% học sinh bày tỏ thái độ tích cực đối với các hoạt động đổi mới phương pháp học tập và khoảng 22% ý kiến chia sẻ áp lực liên quan đến các kỳ thi tốt nghiệp.

Thảo luận kết quả

Hiệu năng vượt trội của hệ thống xuất phát từ nguyên lý đặt bộ xử lý cùng nơi với đĩa lưu trữ trong kiến trúc HDFS, giúp triệt tiêu hiện tượng thắt cổ chai đường truyền mạng. Bằng cách điều khiển trật tự sắp xếp khóa ngay từ pha trung gian, Reducer có thể trực tiếp tính toán tần số tương đối và xuất dữ liệu nén ra đĩa tuần tự mà không cần lưu đệm toàn bộ danh sách đăng trong bộ nhớ.

So với các giải pháp máy chủ đơn lẻ truyền thống, mô hình MapReduce phân tán thể hiện sự ổn định tuyệt đối trước các sự cố phần cứng nhờ cơ chế tự động phân bổ lại tác vụ. Các kết quả thực nghiệm về thời gian xử lý và tỷ lệ nén có thể được trình bày trực quan thông qua bảng so sánh hiệu năng giữa các phân đoạn dữ liệu 1 gigabyte, 3 gigabyte và 5,7 gigabyte, kết hợp biểu đồ cột biểu diễn phân bố tần suất từ khóa ý kiến học sinh theo từng chủ đề giáo dục, giúp cơ quan quản lý dễ dàng theo dõi biến động dư luận học đường.

Đề xuất và khuyến nghị

Thứ nhất, triển khai mở rộng hạ tầng cụm máy chủ phân tán. Đội ngũ kỹ thuật công nghệ thông tin tại các cơ quan quản lý giáo dục cần thiết lập cụm tính toán Hadoop từ 5 đến 10 máy trạm thông thường, hướng tới mục tiêu nâng công suất xử lý lên 50 gigabyte dữ liệu văn bản mỗi ngày, hoàn thành trong thời gian 6 tháng.

Thứ hai, chuẩn hóa quy trình tiếp nhận và phân tích dư luận học sinh trên không gian số. Sở Giáo dục và Đào tạo tỉnh Hòa Bình cùng ban giám hiệu các trường THPT cần thành lập bộ phận giám sát ý kiến trực tuyến, thực hiện phân tích tự động định kỳ hàng tuần với chỉ tiêu đạt độ chính xác phân loại trên 85%, áp dụng ngay trong quý 1 của năm học.

Thứ ba, tối ưu hóa các thuật toán xử lý ngôn ngữ tự nhiên tiếng Việt cho công cụ tìm kiếm. Nhóm nghiên cứu kỹ thuật cần tiếp tục tích hợp các bộ tách từ chuyên sâu và cấu hình thuật toán nén Simple-9 vào bộ chỉ mục Solr, đặt mục tiêu giảm thêm 20% dung lượng lưu trữ chỉ mục trong lộ trình 12 tháng tới.

Thứ tư, ban hành quy chế bảo vệ an toàn thông tin và dữ liệu cá nhân của học sinh. Các cơ sở giáo dục trên địa bàn tỉnh cần xây dựng khung pháp lý nội bộ, đảm bảo 100% dữ liệu bình luận từ mạng xã hội được ẩn danh hóa tuyệt đối trước khi đưa vào hệ thống phân tích, thực hiện kiểm toán bảo mật 2 lần mỗi năm.

Đối tượng nên tham khảo luận văn

Thứ nhất, kỹ sư dữ liệu lớn và lập trình viên hệ thống phân tán. Nhóm đối tượng này sẽ nắm bắt được phương pháp cài đặt chi tiết cụm Hadoop, kiến trúc tệp HDFS, kỹ thuật lập trình In-Mapper Combining và các giải pháp tối ưu hóa bộ nhớ cho các bài toán xử lý văn bản quy mô lớn.

Thứ hai, các nhà nghiên cứu xử lý ngôn ngữ tự nhiên và khai phá dữ liệu web. Luận văn cung cấp phương pháp xây dựng ma trận từ đồng xuất hiện, thuật toán tính tần số tương đối và quy trình tích hợp giữa bộ thu thập dữ liệu Apache Nutch với công cụ tìm kiếm Apache Solr.

Thứ ba, cán bộ quản lý giáo dục và lãnh đạo các trường học. Nhóm đối tượng này có thể ứng dụng trực tiếp mô hình khảo sát tự động trên mạng xã hội để lắng nghe tâm tư học sinh một cách khách quan, phục vụ công tác hoạch định chính sách giáo dục dựa trên dữ liệu thực tế.

Thứ tư, sinh viên và học viên cao học ngành Khoa học máy tính. Công trình là tài liệu tham khảo chuẩn mực về cấu trúc một nghiên cứu ứng dụng công nghệ xử lý dữ liệu lớn, từ nền tảng lý thuyết đến triển khai thực nghiệm hoàn chỉnh.

Câu hỏi thường gặp

Mô hình MapReduce mang lại ưu thế gì so với kiến trúc tính toán truyền thống?

MapReduce cho phép mở rộng hệ thống theo chiều ngang bằng cách bổ sung các máy tính thông thường với chi phí thấp thay vì nâng cấp máy chủ đắt tiền. Cơ chế đưa xử lý đến dữ liệu giúp loại bỏ tắc nghẽn mạng và hệ thống có khả năng tự động khắc phục lỗi phần cứng khi vận hành trên quy mô hàng petabyte.

Tại sao thuật toán chỉ mục ngược lại giữ vai trò quyết định trong công cụ tìm kiếm?

Chỉ mục ngược ánh xạ từng từ khóa đến danh sách tài liệu chứa từ khóa đó, giúp hệ thống không cần duyệt tuần tự toàn bộ kho văn bản khi người dùng truy vấn. Nhờ đó, thời gian trả kết quả tìm kiếm được rút ngắn xuống dưới 200 mili giây, đáp ứng tiêu chuẩn phản hồi thời gian thực trong thực tế.

Kỹ thuật In-Mapper Combining giải quyết bài toán hiệu năng như thế nào?

Kỹ thuật này chủ động thực hiện gom các cặp khóa-giá trị trung gian ngay trong bộ nhớ của Mapper trước khi phát dữ liệu ra ngoài. Thực nghiệm trên 5,7 gigabyte dữ liệu chứng minh phương pháp này giúp cắt giảm hơn 60% dữ liệu trung gian truyền qua mạng, tối ưu hóa tốc độ vượt trội so với Combiner mặc định.

Làm thế nào để hệ thống tránh được lỗi tràn bộ nhớ tại Reducer?

Tác giả áp dụng mô hình chuyển đổi giá trị thành khóa kết hợp, đưa thông tin nhận dạng tài liệu vào cấu trúc khóa trung gian. Tận dụng cơ chế sắp xếp tự nhiên của Hadoop, Reducer nhận dữ liệu đã có thứ tự sẵn và ghi trực tiếp ra đĩa mà không cần lưu đệm toàn bộ danh sách trong RAM.

Dữ liệu khảo sát từ mạng xã hội có đảm bảo tính khách quan hơn khảo sát truyền thống không?

Việc thu thập các bài đăng và bình luận công khai giúp ghi nhận ý kiến tự nhiên, loại bỏ rào cản e ngại của học sinh so với phương pháp phát phiếu hỏi trực tiếp. Thực nghiệm trên 10.000 phản hồi tại Hòa Bình đã phản ánh chính xác các nguyện vọng thực tế về học tập và thi cử.

Kết luận

• Luận văn đã hệ thống hóa toàn diện cơ sở lý thuyết về mô hình tính toán phân tán MapReduce, kiến trúc lưu trữ HDFS và kỹ thuật lập chỉ mục ngược trong truy hồi thông tin.
• Đề xuất và cài đặt thành công các giải pháp cải tiến thuật toán chỉ mục ngược, kết hợp kỹ thuật khóa phức hợp và phương pháp nén dữ liệu bằng khoảng cách chỉ số văn bản.
• Thực nghiệm trên cụm Hadoop 19 máy phụ với 2,27 triệu tài liệu APW dung lượng 5,7 gigabyte chứng minh mô hình hoạt động ổn định, loại bỏ điểm nghẽn bộ nhớ và giảm 60% lưu lượng mạng.
• Tích hợp thành công bộ ba công nghệ Apache Nutch, Apache Solr và Facebook Graph API để xây dựng hệ thống khảo sát ý kiến tự động trên mạng xã hội.
• Ứng dụng phân tích thành công hơn 10.000 dữ liệu tương tác của học sinh tỉnh Hòa Bình, cung cấp công cụ khảo sát dư luận học đường khách quan và tin cậy.

Đóng góp chính của luận văn là cung cấp một giải pháp công nghệ hoàn chỉnh, hiệu năng cao và tiết kiệm chi phí cho bài toán xử lý dữ liệu lớn trong giáo dục. Lộ trình phát triển tiếp theo trong 12 đến 24 tháng tới là mở rộng hệ thống sang xử lý luồng dữ liệu thời gian thực và tích hợp các mô hình học sâu phân tích cảm xúc đa chiều. Các cơ quan quản lý và đơn vị giáo dục hãy chủ động tham khảo, ứng dụng mô hình này để nâng cao hiệu quả quản trị và ra quyết định dựa trên dữ liệu.

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

CHƯƠNG 1 MÔ HÌNH MapReduce 1. Tổng quan về MapReduce 1. Sự quan trọng của MapReduce Về tính thiết thực, MapReduce cung cấp một công cụ rất hiệu quả để giải quyết các bài toán dữ liệu lớn. Ngoài ra, MapReduce còn quan trọng trong cách nó đã thay đổi việc sắp xếp tính toán trên quy mô lớn.

Nói một cách công bằng thì MapReduce không phải là mô hình tính toán song song đầu tiên được đưa ra. Mô hình phổ biến nhất trong lý thuyết khoa học máy tính có từ mấy thập kỷ trước là PRAM1 (Parallel Random Access Machine). Trong mô hình này, một lượng lớn các vi xử lý chia sẻ một bộ nhớ lớn không giới hạn, hoạt động đồng thời trên một lượng dữ liệu chia sẻ để tạo ra kết quả. Các mô hình khác như LogP2 và BSP3 (Bulk Synchronous Parallel), tuy nhiên không có mô hình nào có được sự thành công như MapReduce.

MapReduce là mức trừu tượng thành công nhất trên các tài nguyên tính toán mở rộng cho đến nay. Tuy nhiên, mức trừu tượng giải quyết sự phức tạp bằng cách che dấu sự chi tiết và đưa ra các hành vi được thiết kế tốt cho ngƣời sử dụng ứng với mức trừu tượng đó. Chính vì thế, mức trừu tượng không thể hoàn hảo, nó làm cho một số công việc dễ hơn, nhưng cũng làm một số công việc khác khó hơn hoặc có khi là không thể thực hiện được. Vấn đề này làm cho việc ứng dụng MapReduce trong một số bài toán cũng có mặt hạn chế.

Điều đó có nghĩa MapReduce không phải là mô hình cuối cùng trong lớp mô hình lập trình mới cho phép xử lý tính toán trên quy mô lớn một cách hiệu quả.org/wiki/Parallel_Random_Access_Machine 2 http://en.org/wiki/LogP_machine 3 http://en.org/wiki/Bulk_Synchronous_Parallel 12 c 1. Các ý tưởng của MapReduce Giải quyết các bài toán dữ liệu lớn đòi hỏi cách tiếp cận riêng biệt mà nhiều khi đối lập với mô hình tính toán truyền thống. Dưới đây là các ý tƣởng chính của MapReduce: Scale “out” not “up” (mở rộng chứ không nâng cấp): Để tăng sức mạnh xử lý thay vì nâng cấp bộ vi xử lý cũng như khả năng lưu trữ của máy tính (mua các server có khả năng xử lý cao – high-end server) giải pháp đưa ra là tăng số lượng các server thông dụng (low-end server). Giải pháp này kinh tế hơn nhiều so vì nó chỉ bổ sung một số máy tính và tận dụng được các server sẵn có trong khi giải pháp nâng cấp có thể dẫn đến việc mua sắm mới lại toàn bộ các server.

Hơn nữa giá thành của một server chuyên dụng đắt hơn nhiều so với một cụm máy tính thông thường với khả năng xử lý tương đương. Assume failures are common (chấp nhận việc xảy ra lỗi là thường xuyên): Với sự gia tăng về số lượng của các server trong một cluster, lỗi xảy ra là điều bình thường. Do đó các dịch vụ phân tán trên nhiều server phải tính toán đến các lỗi về phần cứng cũng như phần mềm thường xuyên xảy ra. Mô hình lập trình MapReduce có khả năng xử lý các lỗi thông qua một số cơ chế như tự động khởi động lại các task trên cluster node khác nhau.

Move processing to the data (đưa xử lý đến dữ liệu): Trong các ứng dụng tính toán hiệu năng cao truyền thống (High – Prefomance Computing - HPC). Thông thường, một siêu máy tính có các nút xử lý (processing node) và các nút lưu trữ (storage node) được kết nối với nhau qua một kết nối tốc độ cao. Nhiều công việc nặng nề về dữ liệu không phải là những đòi hỏi xử lý cao. Do đó việc tách rời việc lưu trữ dữ liệu và tính toán tạo ra sự thắt cổ chai trong mạng.

Do đó sẽ hiệu quả hơn nếu chuyển sự thực thi xử lý đến dữ liệu thay vì chuyển dữ liệu đến nơi xử lý chúng. MapReduce sử dụng một kiến trúc trong đó các bộ xử lý và đĩa lưu trữ được đặt cùng với nhau. Trong sự thiết lập như vậy, chúng ta có thể tận dụng lợi thế của dữ liệu cục bộ bằng cách chạy đoạn mã trên bộ xử lý một cách trực tiếp trên khối dữ liệu cần xử lý. Hệ thống tập tin phân tán có nhiệm vụ quản lý dữ liệu mà MapReduce xử lý.

Process data sequentially and avoid random access (xử lý dữ liệu tuần tự và tránh truy cập ngẫu nhiên): Trong trường hợp xử lý một lượng lớn dữ liệu, dung lượng bộ nhớ thường không đủ cho toàn bộ dữ liệu xử lý. Do đó dữ liệu phải được lưu trữ trên đĩa. Thời gian cho việc truy cập ngẫu nhiên thường hạn chế bởi sự di chuyển của đầu đọc cũng như tốc độ đĩa do đó làm chậm công việc xử lý. Để tránh hạn chế này, MapReduce được thiết kế để xử lý các 13 c khối dữ liệu của một tập dữ liệu lớn.

Hide system-level details from the application developer (che giấu mức chi tiết hệ thống đối với nhà phát triển): Để dễ dàng cho các lập trình viên khi viết ứng dụng xử lý phân tán, MapReduce che giấu sự thực thi phức tạp bên dưới. Thay vào đó, MapReduce cung cấp một mô hình lập trình trừu tượng với các interface đơn giản được định nghĩa sẵn. Phương pháp thường được sử dụng để giải quyết các bài toán dữ liệu lớn hiện nay là chia để trị. Ý tưởng là phân mảnh một bài toán lớn thành các bài toán con nhỏ.

Các bài toán nhỏ độc lập với nhau để có thể được giải quyết song song bởi các workers khác nhau – workers có thể là các tiến trình trong bộ vi xử lý hoặc các bộ vi xử lý trong trong bộ vi xử lý đa nhân, các bộ xử lý trên một máy, các máy trên một cụm máy tính. Các kết quả trung gian từ các worker cụ thể sẽ được gộp lại để tạo thành kết quả cuối cùng. Mô hình chia để trị MapReduce có nguồn gốc từ lập trình hàm (Functional Programming). Ví dụ điển hình như các ngôn ngữ lập trình Lisp và ML.

Tính năng chính của lập trình hàm là khái niệm về các hàm bậc cao (higher-order functions), hoặc các hàm chấp nhận tham số của nó là một hàm. Hai hàm bậc cao thường được xây dựng sẵn là Map và Fold. Như hình dưới, cho một danh sách, Map lấy tham số là một hàm f (có 1 tham số) và áp dụng cho toàn bộ phần tử trong danh sách. Cho một danh sách, Fold lấy tham số là một hàm g (có 2 tham số) và một giá trị khởi tạo: g đầu tiên được áp dụng cho giá trị khởi tạo và phần tử đầu tiên trong danh sách, kết quả 14 c được lưu trong biến trung gian, tiếp tục dùng biến trung gian này để phần tử thứ 2 trong danh sách để làm tham số cho hàm g, công việc tiếp lặp đi lặp lại đến khi hết toàn bộ danh sách.

Fold trả về kết quả cuối cùng là giá trị cuối cùng của biến trung gian. Hàm Map và Fold trong Functional Programming Hàm Map trong MapReduce tương ứng với hàm Map, hàm Reduce tương ứng với hàm Fold trong lập trình hàm. Cấu trúc dữ liệu trong MapReduce Các cặp key-value là cấu trúc dữ liệu cơ bản trong MapReduce. Key và value có thể nhận các giá trị có kiểu cơ bản như số nguyên, số thực, chuỗi hay có thể nhận các kiểu giá trị có cấu trúc do người dùng định nghĩa.

Một phần quan trọng của giải thuật MapReduce là việc xác định cấu trúc key-value trên các tập dữ liệu cần xử lý. Ví dụ, đối với một tập các trang web, các key có thể là các URL và các value có thể là nội dung của các trang HTML, đối với một đồ thị, key có thể là node id và value có thể là danh sách kề của node đó. Trong một số thuật toán key được sử dụng để phân biệt các bộ dữ liệu (giống như khái niệm khóa trong cơ sở dữ liệu), trong khi ở một số thuật toán, các input key không quan trọng và thường được bỏ qua. Mapper và Reducer Trong MapReduce, lập trình viên định nghĩa một lớp Mapper và một lớp Reducer với hai hàm cơ bản sau:  map (k1, v1) → [ (k2, v2)]  reduce (k2, [v2]) → [ (k3, v3)] Ký hiệu […] để chỉ một danh sách các giá trị.

Đầu vào của một công việc MapReduce (MapReduce job) là dữ liệu được lưu trữ trên hệ thống file phân tán (Distributed File System). Hàm map và reduce lần lượt được cài đặt trong hai lớp 15 c Mapper và Reducer. Mapper được áp dụng cho mọi cặp key-value để tạo ra các cặp key-value trung gian. Reducer được áp dụng cho tất cả các giá trị (value) ứng với cùng một key trung gian để tạo các cặp key-value ở đầu ra.

Giữa 2 pha map và reduce là một phép xử lý nhóm phân tán các cặp key-value trung gian dựa trên các key. Dữ liệu trung gian được gởi đến mỗi reducer theo thứ tự được sắp xếp bởi các key. Tuy nhiên không có một quan hệ thứ thự nào được thiết lập cho các key giữa các reducer với nhau. Các cặp key-value ở đầu ra của các reducer được ghi vào hệ thống file phân tán (các cặp key-value trung gian được bỏ qua).

Đầu ra cuối cùng là r file trên hệ thống file phân tán, trong đó r là số các reducer. Trong phần lớn các trường hợp, việc tổng hợp các đầu ra của các reducer là không cần thiết bởi vì r files thường lại là đầu vào cho một MapReduce job khác. Hình 5 mô tả 2 giai đoạn của một MapReduce job. Hai pha Map và Reduce của một MapReduce job Ví dụ minh họa MapReduce: Ứng dụng đếm từ (Word count) trong một tập văn bản.

 Input: Tập văn bản  Outut: Danh sách các từ cùng số lần xuất hiện của chúng trong tập văn bản. class Mapper method Map (docId a, doc d) 16 c for all term t ϵ doc d do Emit (term t, count 1) class Reducer method Reduce (term t, counts[c1, c2,…]) sum ← 0 for all count c ϵ counts[c1, c2,…] do sum ← sum + c Emit (term t, count sum) Hàm Map duyệt qua từng từ trong tập văn bản ứng với mỗi từ sẽ tạo ra một cặp key-value với key chính là từ vừa gặp và value = 1. Hàm Reduce nhận đầu vào là một từ (term) và và danh sách tần số ci bắt gặp của term đó (các giá trị thực là các số 1), Reduce chỉ đơn giản cộng tất cả các giá trị ci trong danh sách counts. Partitioner và Combiner Phần trên chúng ta đã làm đơn giản cái nhìn về MapReduce, ngoài hai thành phần Mapper và Reducer, thường thì lập trình viên phải chỉ thêm 2 thành phần phụ nữa: 1.

Thành phần Partitioner Nó có nhiệm vụ chia không gian khóa (key) trung gian sau bƣớc Map và gán các cặp key-value trung gian tới các Reduce.