<span class="text_page_counter">Trang 1</span><div class="page_container" data-page="1">

MỞ DAU

Ngày nay, người dùng Internet gặp phải vấn đề dữ liệu tăng trưởng quá nhanh về số lượng

cũng như độ đa dạng, điều này dẫn đến khó khăn là người dùng khó lựa chọn những thơng tin hữu ich từ rất nhiều thơng tin đó. Những van đề thực tế này dẫn đến sự ra đời và phát triển của

hệ tư vấn.

Với sự tăng trưởng nhanh chóng của dit liệu, van đề mở rộng và độ hiệu quả của hệ thống

tư vấn cũng như công việc tính tốn ở tầng dưới trở thành vấn đề chính được quan tâm. Việc

thực hiện tính tốn trên một máy duy nhất yêu cầu cau hình phần cứng phải nâng cấp liên tục

dé đáp ứng hiệu năng va ràng buộc về thời gian, thậm chí việc nâng cấp phan cứng không thé theo kịp sự tăng trưởng dữ liệu một cách chóng mặt. Do những bắt lợi này, giải pháp chỉ dùng một máy duy nhất là rất dat đỏ và khó điều khiến.

Để giải quyết van đề này, rất nhiều công nghệ đã ra đời nhắm thực hiện tính tốn và mở rộng việc xử lý dữ liệu theo mơ hình song song và khả năng chịu lỗi cao trên một số lượng lớn

<small>máy tính. Các máy tính thực hiện tính tốn độc lập với nhau và khơng ảnh hưởng bởi việc xảy</small>

ra lỗi ở máy khác, điều này giúp tăng hiệu năng tính tốn so với việc chỉ ding một máy, ngồi

<small>ra sử dụng mơ hình tính tốn song song cịn g1úp giảm giá thành.</small>

Khi áp dụng phương pháp này cho hệ tư van, cần phải sắp xếp lại các thuật tốn dé tối ưu việc tính tốn song song. Một trong các cơng nghệ được sử dụng phổ biến dé tối ưu hóa việc

<small>tính tốn song song là Hadoop — MapReduce. Luận văn trình bay phương pháp áp dụng</small>

framework này vào việc xây dựng hệ tư vấn, cụ thể là bằng phương pháp lọc cộng tác dựa vào người dùng và lọc cộng tác dựa vào sản phẩm.

Nội dung của luận văn gồm:

© Chương I: Tổng quan về Hadoop MapReduce.

e_ Chương II: Phát triển hệ tư vấn trên Hadoop MapReduce.

<small>e Chương II: Thử nghiệm và đánh gia</small>

</div><span class="text_page_counter">Trang 2</span><div class="page_container" data-page="2">

CHUONG 1- TONG QUAN VE HADOOP MAPREDUCE

1.1 Giới thiệu chung về Hadoop

Hadoop là một phần mềm mã nguồn mở, được viết bởi Doug Cutting (người đã viết Apache Lucene — thư viện tìm kiếm được sử dụng rộng rãi). Hadoop cho phép lưu trữ và truy cập dữ

<small>liệu, xử lí, phân tích cũng như hỗ trợ học máy trên tập dữ liệu lớn một cách phân tán thông qua</small>

<small>các cụm server (cluster)[3, 4, 5, 14].</small>

Hadoop gồm 2 framework chính là: HDFS và MapReduce.

- HDFS (Hadoop Distributed File System) là hệ thong file phân tán, có nhiệm vụ lưu trữ

dữ liệu phân tán, thông qua nhiều node khác nhau, mỗi node này là một Hadoop cluster.

- MapReduce là một framework cung cấp cho lập trình viên các API để xử lý và phân tích

<small>dữ liệu trên các Hadoop cluster.</small>

1.2 Các thành phần cơ bản của Hadoop Ecosystem

<small>- Framework chính của Hadoop: HDES, MapReduce.</small>

<small>- Quan lý siêu dữ liệu: HCatalog.</small>

- Luu trữ dữ liệu và truy vấn: Pig, Hive, HBase.

- Xuat nhập đữ liệu: Flume, Sqoop.

<small>- Hoc máy va phân tích dữ liệu: Mahout.</small>

- _ Điều chỉnh hệ thống phân tán: Zookeeper.

<small>- Quan ly cluster: Ambari.</small>

- Lwuu trữ dữ liệu và hệ thống tuần tự: Avro.

1.3 Hệ thống file phân tán của Hadoop

<small>Định nghĩa HDFS</small>

<small>Khái niệm block trong HDFS</small>

Kiến trúc của HDES . Tố chức dữ liệu

pose

</div><span class="text_page_counter">Trang 3</span><div class="page_container" data-page="3">

<small>1.4 Mơ hình tính tốn MapReduce</small>

<small>1.4.1 Định nghĩa MapReduce</small>

1.4.2 Mơ hình làm việc và luồng dữ liệu của MapReduce 1.4.3 Luồng điều khiến khi thực thi một MapReduce Job 1.5 Kết luận chương

Chương 1 đã trình bày các khái niệm về Hadoop các thành phần cơ bản của Hadoop MapReduce, kiến trúc và cách làm việc của Hadoop — MapReduce. Chương 2 của luận văn tập trung vào phương pháp xây dựng hệ tư vấn trên Hadoop — MapReduce.

</div><span class="text_page_counter">Trang 4</span><div class="page_container" data-page="4">

Chương 2 - PHÁT TRIEN HỆ TU VAN TREN HADOOP MAPREDUCE

2.1 Phat biểu bai toán

2.2 Các phương pháp xây dựng hệ tư van bằng lọc cộng tác

<small>2.2.1 Phương pháp lọc cộng tác dựa vào người dùng</small>

<small>Kỹ thuật lọc cộng tác dựa vào người dùng được thực hiện theo 3 bước:</small>

- _ Bước 1: Biểu diễn tập dữ liệu

Biểu diễn đánh giá của người dùng và sản phẩm thành ma trận đánh

<small>Ny 2 ¬</small>

<small>Trt Fam</small>

Ma trận đánh giá trên gồm có n người dùng, đánh giá trên m san phẩm. Mỗi phan tử rxy của ma trận thể hiện đánh giá của người dùng ux với sản phẩm iy, rxy = 0 nếu người dùng ux chưa đánh giá sản phẩm iy.

<small>- Bước 2: Tính tốn độ tương tự giữa các cặp người dùng</small>

<small>Kí hiệu suv là độ tương tự giữa người dùng u và người dùng v.Luận văn tính độ tương tự sử dụng độ tương quan Pearson:</small>

<small>giá bởi cả người dùng u và người dùng v.</small>

tui, rụ lần lượt là đánh giá của người dùng u và v với sản phẩm i.

<small>là trung bình đánh giá của người dùng u.là trung bình đánh giá của người dùng v.</small>

- _ Bước 3: Tính tốn dự đốn của người dùng đó với sản phẩm

Sau khi tính được độ tương tự giữa các người dùng, một tập con gồm k

</div><span class="text_page_counter">Trang 5</span><div class="page_container" data-page="5">

người dùng có độ tương tự lớn nhất với người dùng đang xét sẽ được chọn và đánh giá của người dùng đang xét với sản phẩm sẽ được tính tốn dựa

<small>vào đó theo cơng thức:</small>

<small>Trong đó:</small>

<small>pu là đánh giá của người dùng u với sản phâm i.</small>

kNN là tập k hàng xóm gần nhất của người dùng u.

2.2.2 Phương pháp tư van dựa vào sản phẩm

Kỹ thuật lọc cộng tác dựa vào sản phâm được thực hiện theo các bước

- Bước 1: biểu diễn dữ liệu

<small>Tương tự như kỹ thuật lọc cộng tác dựa vào người dùng, kỹ thuật lọc</small>

cộng tác dựa vào sản phẩm cũng thực hiện biểu diễn đánh giá của người dùng và sản phẩm thành ma trận đánh giá:

<small>hi Hạ ` Tìm</small>

<small>R= "21</small>

<small>My 1 " Rim</small>

Ma trận đánh giá trên gồm có n người dùng, đánh giá trên m san phẩm. Mỗi phan tử rxy của ma trận thể hiện đánh giá của người dùng ux với sản phẩm iy, rxy = 0 nếu người dùng ux chưa đánh giá sản phẩm iy.

<small>- Bước 2: tính tốn độ tương tự</small>

Kí hiệu suy là độ tương tự giữa sản phẩm¡ và sản phẩm j.

Phương pháp lọc cộng tác dựa vào sản phẩm sử dụng cơng thức tính

</div><span class="text_page_counter">Trang 6</span><div class="page_container" data-page="6">

Do đó U¡ Uj là tập các người dùng đánh giá cả hai sản phâm i và j.

Tui, ru lần lượt là đánh giá của người dùng u với sản phẩm i và sản phẩm j.

Độ tương quan Pearson cũng được đề xuất dé tính độ tương tự giữa hai sản phẩm, tuy nhiên nó khơng hiệu quả băng phương pháp tính độ tương

<small>tự Cosine[®!'</small>

- Bước 3: tính cơ sở dự đoán của người dùng với sản phẩm (baseline

<small>Cơ sở dự đốn là phương pháp làm tăng độ chính xác khi dự đoán</small>

đánh giá của người dùng và sản phẩm, cơ sở dự đốn có thể được sử dụng dé dự đoán cho người dùng mới[7].

Trường hợp đơn giản, cơ sở dự đốn có thê được tính băng cách: <small>bu = uy (2.4)</small>

Dé chính xác hơn, cơ sở dự đốn được tinh theo công thức tông quát:

<small>bụi = u + bu + bị (2.5)</small>

<small>Trong đó:</small>

bụi là cơ sở dự đốn của người dùng u đối với sản phẩm i. ụ là trung bình đánh giá của tat cả người dùng.

bu, bị tương ứng là cơ sở đánh giá của người dùng u và sản phẩm i.

<small>bu và bị được tính theo công thức:</small>

tui là đánh giá của người dùng u đối với sản phẩm i.

- _ Bước 4: dự đoán đánh giá của người dùng với sản phẩm

Sau khi tính toán độ tương tự giữ các cặp sản phẩm và tính cơ sở dự

đốn giữa người dùng và sản phẩm, bước thực hiện tiếp theo là dự đoán

</div><span class="text_page_counter">Trang 7</span><div class="page_container" data-page="7">

đánh giá của người dùng với sản phẩm. Trong luận văn này, phương pháp dự đoán đánh giá bằng cách tính tổng trọng số được sử dụng. Tập gồm k sản phẩm tương tự nhất với sản phẩm đang xét sẽ được chon ra và sử dụng dé tính tốn tổng trọng số theo cơng thức:

Pụi là đánh giá dự đoán của người dùng u với sản pham i. Bụi là cơ sở dự đoán của người dùng u với sản phẩm ¡.

Bu; là cơ sở dự đoán của người dùng u với sản phẩm j. Ry; là đánh giá của người dùng u với sản phẩm j.

S là tập gồm k sản phâm tương tự nhất với sản pham i.

2.2.3 Vấn đề dữ liệu lớn đối với hệ tư van 2.3 Áp dụng MapReduce cho hệ tư van

2.3.1 Áp dụng MapReduce cho hệ tư vấn dựa vào người dùng

Bước 1:Xử lý tập dữ liệu đầu vào (Job 1)

<small>Dữ liệu vào ra tương ứng của bước này được mô tả như sau:</small>

<small>e KI là thứ tự của dòng dữ liệu trong tập dữ liệu.</small>

<small>e VỊ là I dòng trong tập dữ liệu.e K2 1a itemid.</small>

<small>e V2 la userid va rating tương ứng.e K3 1a itemid.</small>

<small>e V3 là danh sách userid va rating tương ứng với itemid ở K3.</small>

Dữ liệu đầu ra của Job 1 được lưu trong thư mục pair_user.

<small>DataSplitMapper thực hiện công viéc:</small>

<small>e Đọc từng dong dit liệu trong tập dữ liệu tạo ra giá trị V1.e Tach VI thành giá tri itemid va userid, rating.</small>

<small>e Gán itemid cho K2, gan userid, rating cho V2.</small>

</div><span class="text_page_counter">Trang 8</span><div class="page_container" data-page="8">

<small>DataSplitReducer thực hiện công việc:</small>

e Nhận đầu vào là một danh sách userid và rating tương ứng (list(V2)) của một <small>itemid (K2).</small>

° Sắp xếp danh sách V2 theo userid tăng dần.

e Gan K3 1a itemid (giống K2), gan V3 là list(V2).

<small>Bước 2: Tính độ tương tự giữa hai người dùng (Job 2)</small>

<small>Dữ liệu vào ra tương ứng của bước này được mơ tả như sau:e KI là thứ tự dịng dữ liệu trong thư mục pair_user.</small>

<small>e VỊ là I dòng dữ liệu đọc từ thư mục pair_user.</small>

<small>e K2 là cặp userid.</small>

e V2 là itemid va rating của cả hai người dùng đối với sản phẩm đó. <small>e K3 là cặp userid.</small>

<small>e V3 là độ tương tự giữa cặp người dùng đó.</small>

Dữ liệu đầu ra của Job 2 được lưu trong thư mục similarity.

<small>SimilarityMapper thực hiện cơng việc:</small>

<small>e Đọc từng dịng dữ liệu trong các file trong thư mục pair_user, đó là giá trị V1.e Tach VI thành itemid và danh sách các cặp userid và rating.</small>

<small>e Lặp và tách danh sách userid và rating thành tập các cap userid va cặp ratingtương ứng. Gán K2 là cặp userid, V2 là cặp rating tương ứng.</small>

<small>SimilarityReducer thực hiện các công việc:</small>

e Nhận đầu vào là danh sách cap rating (list(V2)) của một cặp userid (K2).

<small>e Với mỗi V2, tách thành hai giá tri rating.</small>

e Sau khi duyệt hết danh sách các giá trị V2, nhận được hai vector chứa đánh giá của hai người dùng với các sản phẩm chung của họ.

e Áp dụng cơng thức 2.1 dé tính độ tương tự.

Y Tinh giá trị đánh giá trung bình của mỗi người dùng bằng cách tính trung bình

<small>cộng các giá trị của mỗi vector người dùng. Với mỗi cặp người dùng khác</small>

<small>nhau thì giá trị đánh giá trung bình của người dùng đó cũng khác nhau vì nó</small>

phụ thuộc vào những sản phâm chung của hai người dùng đó.

</div><span class="text_page_counter">Trang 9</span><div class="page_container" data-page="9">

* Áp dụng cơng thức dé tính độ tương tự với các tham số đã có và đã tính được

<small>ở trên.</small>

e©_ Sau khi tính được độ tương tự của hai sản phẩm, gán cặp userid cho K3, gan giá

<small>trị độ tương tự và đánh giá trung bình của hai người dùng cho V3.</small>

Bước 3: Chọn ra tập k hàng xóm với mỗi người dùng u

Dữ liệu đầu vào và đầu ra của bước này có dạng như sau:

<small>e KI là thứ tự dòng dữ liệu trong thư mục similarity.e VỊ là 1 dòng dữ liệu đọc từ thư mục similarity.</small>

<small>e K2 là một userid tách ra từ K1.</small>

<small>e V2 là userid còn lại và độ tương tự giữa hai userid đó.</small>

<small>e K3 1a userid từ K2.</small>

e V3 là danh sách gồm userid và độ tương tự giữa userid đó với userid ở K3.

Dữ liệu đầu ra của bước này được lưu trong thư mục kNeighbor.

<small>Lớp FindKNeighborMapper thực hiện các công việc:</small>

<small>e Đọc vào từng dòng dữ liệu từ thư mục similarity là giá trị V1.e Tach VI thành hai userid và độ tương tự giữa hai userid đó.</small>

<small>e Với mỗi userid, gan K2 là userid đó, V2 là userid cịn lại và độ tương tự.</small>

<small>Lớp FindKNeighborReducer thực hiện các công việc:</small>

<small>e Nhận vào K2 là userid và danh sách V2 là userid và độ tương tự.</small>

<small>e Gan K3 là userid từ K2. Từ danh sách V2, chọn ra k giá tri có độ tương tự lớn</small>

nhất và gan V3 là danh sách k giá tri này.

Bước 4: Dự đoán đánh giá của người dùng u với sản phẩm i (Driver)

e Đọc tập dữ liệu từ thư mục kNeighbor, với mỗi dòng dữ liệu, tách ra thành các

<small>giá trị: hai userid, độ tương tự giữa hai người dùng đó. Các giá trị này được lưutrong một HashMap với key là một userid, value là userid còn lại và độ tương tự.</small>

e Doc tập dữ liệu kiểm nghiệm, duyệt các cặp userid và itemid trong tap kiểm

<small>nghiệm và tính dự đốn đánh giá cho mỗi cặp đó sử dụng cơng thức 2.2.</small>

2.3.2 Áp dụng MapReduce cho hệ tư vấn dựa vào sản phẩm

Bước 1: Xử lý tập dữ liệu đầu vào (Job 1)

</div><span class="text_page_counter">Trang 10</span><div class="page_container" data-page="10">

<small>Dữ liệu vào ra tương ứng của bước này được mô tả như sau:</small>

<small>e KI là thứ tự của dòng đỡ liệu trong tập dữ liệu.</small>

<small>e VỊ là l dòng trong tập dữ liệu.</small>

<small>e K2 1a userid.</small>

<small>e V2 là itemid va rating tương ứng.e K3 1a userid.</small>

<small>e V3 là tập các cặp itemid va rating tương ứng với userid đó.</small>

Dữ liệu đầu ra của Job 1 được lưu trong thư mục pair_item.

<small>DataSplitMapper thực hiện công việc:</small>

<small>e Đọc tùng dòng dữ liệu trong tập dữ liệu tao ra giá trị V1.e Tach VI thành giá tri userid và itemid rating.</small>

<small>e Gan userid cho K2, gan itemid rating cho V2.e DataSplitReducer thực hiện công việc:</small>

e Nhận đầu vào là một danh sách itemid và rating tương ứng (list(V2)) của một

<small>userid (K2).</small>

e Sắp xếp danh sách V2 theo itemid tăng dan. Gan K3 bằng K2 và gan V3 là danh sách V2 đã sắp xếp.

Bước 2: Tính độ tương tự giữa các cặp sản phẩm (Job2)

<small>Dữ liệu vào ra tương ứng của bước này được mô tả như sau:e KI là thứ tự dòng dữ liệu trong thư mục pair_item.</small>

<small>e V1 là I dòng dữ liệu đọc từ thư mục pair_item.e K2 là cặp itemid.</small>

e V2 là userid va rating của userid đối với cả 2 item đó.

<small>e K3 là cặp itemid.</small>

<small>e V3 là độ tương tự giữa cặp itemid đó.</small>

Dữ liệu đầu ra của Job 2 được lưu trong thư mục similarity.

<small>SimilarityMapper thực hiện công việc:</small>

<small>e Đọc từng dòng dữ liệu trong các file trong thư mục pair_item, đó là giá trị V1.e Tach VI thành userid và tập các cặp itemid va rating.</small>

</div><span class="text_page_counter">Trang 11</span><div class="page_container" data-page="11">

<small>e Lap và tách tập itemid va rating thành các cặp itemid và cặp rating.e Gán cặp itemid cho K2, gan cặp rating cho V2.</small>

<small>e SimilarityReducer thực hiện các công việc:</small>

e Nhận đầu vào là danh sách cap rating (list(V2)) của một cặp itemid (K2).

<small>e Với mỗi V2, tách thành hai giá tri rating.</small>

e Ap dụng cơng thức tính độ tương tự Cosine 2.3 dé tính độ tương tự, trong đó:

v Tử số là tích vơ hướng của hai vector sản phẩm, chính là tổng của tích của hai

<small>giá trị rating tách được với mỗi V2.</small>

VY Mẫu số là tích độ dài của hai vector sản phẩm.

e©_ Sau khi tính được độ tương tự của hai sản phẩm, gán cặp itemid cho K3, gan giá

<small>trị độ tương tự cho V3.</small>

<small>Bước 3: Tính cơ sở dự đốn của người dùng u (Job 3)</small>

<small>Dữ liệu vào ra tương ứng của bước này được mé tả như sau:</small>

e KI là thứ tự dòng trong tap dit liệu ban đầu.

e VI là 1 dòng dữ liệu trong tập dữ liệu ban dau.

<small>e K2 1a userid.</small>

<small>e V2 la itemid va rating tương ứng.e K3 1a userid.</small>

<small>e V3 là giá trị của co sở dự đoán của người dùng tương ứng.</small>

Dữ liệu đầu ra của bước 3 được lưu trong thư mục user_bias.

<small>UserBiasMapper thực hiện các công việc:</small>

e Nhận vào giá trị V1 tương ứng với một dòng dữ liệu trong tập dữ liệu ban đầu.

<small>e Tach VI thành các giá tri userid, itemid va rating.e Gan userid cho K2, gan itemid va rating cho V2.UserBiasReducer thực hiện các công việc:</small>

<small>e Nhận vào danh sách itemid va rating (list(V2)) cua một userid (K2).</small>

<small>e Với mỗi V2, tách thành giá trị itemid và giá tri rating.</small>

<small>e Tính cơ sở dự đốn của người dùng theo cơng thức 2.6.</small>

Bước 4: Tính cơ sở dự đốn của sản phẩm i(Job4)

</div><span class="text_page_counter">Trang 12</span><div class="page_container" data-page="12">

<small>Dữ liệu vào ra của bước này được mơ tả như sau:</small>

e KI là thứ tự dịng trong tập dữ liệu ban đầu.

e VI là I dòng dữ liệu trong tập dữ liệu ban dau.

<small>e K2 1a itemid.</small>

<small>e V2 là userid va rating tương ứng.e K3 1a itemid.</small>

e V3 là giá tri của cơ sở dự đoán của san phẩm tương ứng.

Dữ liệu đầu ra của bước này được lưu trong thư mục item_bias.

<small>ItemBiasMapper thực hiện các công việc:</small>

e_ Nhận vào giá trị V1 tương ứng với một dòng dữ liệu trong tập dữ liệu ban đầu.

<small>e Tach VI thành các giá trị itemid, userid và rating.e Gan itemid cho K2, gan userid và rating cho V2.</small>

<small>ItemBiasReducer thực hiện các công viéc:</small>

<small>e Nhận vào danh sách userid va rating (list(V2)) của một itemid (K2).</small>

<small>e Với mỗi V2, tách thành giá trị itemid và giá tri rating.</small>

e_ Đọc từ tập dữ liệu user_bias dé lấy các giá trị cơ sở dự đốn của người dùng. e_ Tính cơ sở dự đốn của sản phẩm theo cơng thức 2.7.

Bước 5: Chọn k hàng xóm có độ tương tự lớn nhất

Dữ liệu đầu vào và dau ra của bước này có dạng như sau:

<small>e KI là thứ tự dịng dữ liệu trong thư mục similarity.e VỊ là 1 dòng dữ liệu đọc từ thư mục similarity.</small>

<small>e K2 là một itemid tách ra từ K1.</small>

<small>e V2 là itemid còn lại và độ tương tự giữa hai itemid đó.e K3 làitemid từ K2.</small>

e _ V3 là danh sách gồm itemid và độ tương tự giữa itemid đó với itemid ở K3.

Dữ liệu đầu ra của bước này được lưu trong thư mục kNeighbor.

<small>Lớp FindKNeighborMapper thực hiện các công việc:</small>

<small>e Đọc vào từng dòng dữ liệu từ thư mục similarity là giá trị V1.e Tach VI thành hai itemid và độ tương tự giữa hai itemid đó.</small>

</div>