Luận Văn Thạc Sĩ Về 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 Hòa Bình 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

• 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

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.