Hệ gợi ý địa điểm trong mạng xã hội trên điện thoại di động

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (5.75 MB, 24 trang )

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

MỞ ĐẦU 1. Tính cấp thiết của đề tài

Hệ gợi ý hay hệ gợi ý (Recommender System) là hệ thống có khả năng tự động phân tích, dự đốn và gợi ý thơng tin mới phù hợp cho mỗi người dùng Internet. Hệ gợi ý xuất hiện trong nhiều ứng dụng khác nhau của khoa học máy tính

như gợi ý kết quả tìm kiếm, gợi ý sử dụng dịch vụ, gợi ý khách hàng tiềm năng. Đặc

biệt, hệ gợi ý đóng vai trị quan trọng trong việc nâng cao hiệu quả của các hệ thống

thương mại điện tử. Các phương pháp xây dựng hệ gợi ý trước đây chỉ xem xét tập

người dùng trong hệ gợi ý là tập người dùng cơ định có quyền lợi gan bó mật thiết với hệ thống và được hưởng lợi từ việc cung cấp thông tin trong hệ thống. Mối liên hệ của người dùng ln bị đóng kín trong tập người dùng hệ thống. Vì vậy, với cách tiếp cận này hệ gợi ý gặp phải một số khó khăn trong khi giải quyết trường hợp người dùng mới, sản phẩm mới và một số van đề khác.

Sự ra đời các mạng xã hội làm thay đổi phương thức trao đổi thơng tin tồn cầu. Mỗi người dùng trong mạng khơng cịn độc lập với những người dùng khác mà

họ bị chi phối và ảnh hưởng bởi các mối quan hệ xã hội như gia đình, bạn bè, đồng nghiệp, sở thích hoặc chủ đề quan tâm. Người dùng trong mạng xã hội tự do chia sẻ,

bày tỏ quan điểm, ý tưởng và đánh giá của mình về tất cả các vấn đề với cộng đồng

các quan hệ khác nhau. Sự tương tác của người dùng với các mối quan hệ xã hội tạo

nên nguồn tài nguyên thông tin to lớn độc lập với nguồn tài nguyên sẵn có của các hệ thống gợi ý trước đây. Chính vì vậy, nếu xem xét ngữ cảnh của hệ gợi ý được sử

dụng cùng với các quan hệ trong mạng xã hội thì những thơng tin này cũng phải được

xem xét đến trong q trình dự đốn. Tích hợp các mối quan hệ xã hội vào hệ gợi ý

không chỉ cải thiện đáng ké chất lượng dự đốn mà cịn giải quyết hiệu quả van dé

người dùng mới, sản phâm mới, dữ liệu thưa của các cách tiếp cận trước đây. Với những lý do nêu trên, em lựa chọn đề tài “Hệ gợi ý địa điểm trong mạng xã hội trên điện thoại di động” dé thực hiện trong khuôn khổ luận văn thạc sỹ ngành hệ thống

thông tin với mục tiêu, phạm vi và phương pháp cụ thể như dưới đây.

2. Tông quan về van dé nghiên cứu

Hệ gợi ý trở thành lĩnh vực nghiên cứu độc lập từ giữa những năm của thập

kỷ 90 khi bài báo đầu tiên về gợi ý cộng tác được cơng bó. Ngay lập tức, van dé đã

thu hút được sự quan tâm của nhiều học giả đến từ các lĩnh vực khác nhau như toán học, vật lý học, tâm lý học và khoa học máy tính. Ké từ năm 2006 đến nay, hội nghị

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

thé giới thường niên về hệ gợi ý đã được tổ chức do ACM, Microsoft, IBM, Google, FaceBook bảo trợ gián tiếp công nhận đây là lĩnh vực riêng của khoa học máy tính.

Các hệ gợi ý trước đây được tiếp cận theo ba xu hướng chính: Hệ gợi ý dựa

vào phương pháp lọc nội dung (Content-based Filtering Recommendation), hệ gợi ýdựa vào phương pháp lọc cộng tác (Collaboraive Filtering Recommendation) và hệgợi ý lai (Hybrid Filtering Recommendation).

Hệ gợi ý xã hội (Social-based recommender System) là mở rộng của các hệ

gợi y trước đây với việc tích hợp thêm tài ngun thơng tin trên các mang xã hộivào q trình dự đốn. Tài nguyên thông tin của mạng xã hội thường được sử dụng

trong hệ gợi ý là các quan hệ bạn bè hoặc quan hệ tin cậy. Trong dé tài này, bên

cạnh việc nghiên cứu phương pháp gợi ý xã hội dựa vào kỹ thuật ma trận nhân tử

(matrix factorization) em xây dung một tập dữ liệu là các địa điểm du lịch Việt Nam

được người dùng trong các mạng xã hội bình chọn. Trên cơ sở tập người dùng thu

thập được, đề tài xây dựng ứng dụng hệ gợi ý địa điểm trên điện thoại di động.

3. Mục đích nghiên cứu

Mục đích nghiên cứu luận văn là các phương pháp gợi ý sử dụng tài nguyêncủa mạng xã hội dựa vào bộ nhớ. Đặc biệt chú trọng nghiên cứu độ tương tự dựa

trên độ tin cậy trong các quan hệ xã hội. Đánh giá sự khác biệt giữa tiếp cận xã hội cho lọc cộng tác và các phương pháp tiếp cận truyền thống. Thử nghiệm thuật toán

trên các tập dữ liệu xã hội, so sánh hiệu quả gợi ý khi sử dụng các độ đo tương tự

khác nhau. Xây dựng ứng dụng chia sẻ địa điểm trên điện thoại di động.

4. Đối tượng và phạm vi nghiên cứu

Đối tượng nghiên cứu của đề tài: Đối tượng nghiên cứu của đề tài là các hệ

gợi ý trong mạng xã hội, đi sâu vào nghiên cứu phương pháp dự đoán cho ngườidùng sử dụng kỹ thuật phân tích ma trận.

Pham vi nghiên cứu: Pham vi nghiên cứu được giới hạn đối với các phương pháp gợi ý trong mạng xã hội dựa vào kỹ thuật phân tích ma trận. Hệ thống gol ý

địa điểm được lây từ nguồn dữ liệu trên các mạng xã hội.

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

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

Tiếp cận lý thuyết: Sử dụng các kết quả nghiên cứu đã được công bố,

nghiên cứu kỹ các phương pháp xây dựng hệ gợi ý không dựa vào quan hệ xã hội,từ các nghiên cứu cơ bản, di sâu vào nghiên cứu hệ gợi ý sử dụng mạng xã hội. Sosánh và đánh giá sự khác biệt giữa phương pháp gợi ý không sử dụng mạng xã hội

và phương pháp gợi ý dựa vào mạng xã hội. Sau đó tiễn hành xây dựng hệ gợi ý địa điểm cho người dùng di động.

Nghiên cứu thực nghiệm: Xây dựng bộ dữ liệu thử nghiệm cho các địa

điểm du lịch tại Việt Nam. Cai đặt và đánh giá kết quả thử nghiệm của phương pháp

trình bày so với một số phương pháp khác.

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

CHUONG 1

GIỚI THIEU VE HE GOI Ý TRONG MẠNG XÃ HOI

Trong chương này, chúng ta sẽ tìm hiểu một số van đề về hệ gợi ý truyền thống, hệ gợi ý mạng xã hội và các phương pháp khác nhau đã được sử dụng trong hai hệ gợi ý trên. So sánh và đánh giá các phương pháp gợi ý truyền thống trong

mạng xã hội.

1.1. Hệ gợi ý truyền thống

Nội dung này trình bày tổng quan về các hệ gợi ý truyền thống, các phương pháp được áp dụng trong hệ gợi ý truyền thống cùng với những hạn chế cịn tơn tại.

Trên cơ sở đó, nêu định hướng nghiên cứu giải quyết.

1.1.1. Giới thiệu hệ gợi ý truyền thống

Cùng với sự phát triển mạnh mẽ của World Wide Web, sự tăng trưởng chóng mặt của thông tin đã gây ra van đề quá tải đối với người dùng trực tuyến. Hệ gợi ý đã ra đời để giải quyết vấn đề đó. Các hệ gợi ý truyền thống từ trước tới nay đều

đưa ra gợi ý dựa trên những gi người dùng đã làm trong quá khứ hoặc dựa trên việc

tổng hợp ý kiến của những người dùng khác.

Hiện nay, đang có rất nhiều phương pháp xây dựng hệ gợi ý, điển hình như là: ° Dựa trên nội dung (content-based): Người dùng được gợi ý sản phẩm tương tự như những sản phẩm họ đã từng đánh giá cao.

° Lọc cộng tác (collaborative): Người dùng được gợi ý những sản pham

mà những người dùng cùng sở thích với họ đánh giá cao.

° Lai ghép (hybrid): Kết hợp cả hai phương pháp trên.

1.1.2. Hệ gợi ý dựa trên lọc nội dung (content - based)

Lọc theo nội dung là phương pháp thực hiện dựa trên việc so sánh nội dung

thông tin hay mô tả sản phẩm, nhằm tìm ra những sản phẩm tương tự với những gì

mà người dùng đã từng quan tâm trong quá khứ dé giới thiệu cho họ những sản phẩm này. Các phương pháp tiếp cận cho lọc theo nội dung có nguồn gốc từ truy vấn thơng

tin, trong đó mỗi sản phâm được biểu diễn bằng một hồ sơ sản phẩm, mỗi người dùng được biểu diễn bằng một hồ sơ người dùng. Hệ gợi ý dựa trên nội dung dựa vào việc

xem xét các hồ sơ sản phẩm có mức độ phù hợp cao với hồ sơ người dùng.

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

1.1.3. Hệ gợi ý dựa trên lọc cộng tác

Lọc cộng tác là kỹ thuật thành công nhất và được áp dụng rộng rãi nhất trong

hệ gợi ý ngày nay. Lọc cộng tác khai thác những khía cạnh liên quan đến thói quen sở thích của người sử dụng sản phẩm dé đưa ra gợi ý các sản phẩm mới cho người dùng. Dữ liệu đầu vào của hệ thống là một tập các đánh giá của người dùng dành cho sản phâm. Dựa trên các đánh giá này người dùng có thể được so sánh với nhau, hình thành nên khái niệm người dùng tương đồng. Và cũng dựa trên các đánh giá này, tài nguyên được so sánh với nhau hình thành khái niệm tài nguyên tương đồng.

Điểm đánh giá tài nguyên của một người dùng có thể được dự đoán dựa vào các

đánh giá của người dùng “lân cận” hoặc tài nguyên “gần gũi”. Lọc cộng tác phân

tích, bóc tách, hiểu và đánh giá cho nội dung sản phẩm. Chính vì vậy lọc cộng tác có thể lọc hiệu quả trên nhiều dạng sản phẩm khác nhau.

Hiện nay, có rất nhiều phương pháp tiếp cận trên hình thức này được trình

bày, các kỹ thuật phổ biến là xét đến sự tương tự trực tiếp giữa hai người dùng hoặc

hai sản phâm. Trong những phương pháp này, hai người dùng được coi là tương tự nếu họ thé hiện mối quan tâm giống nhau về cùng sản phâm thông qua việc mua hoặc đưa ra đánh giá về sản phẩm đó. Chúng ta có thé phân các phương pháp dự đoán điểm đánh giá của một người dùng cho một tài nguyên ra làm 2 cách tiếp cận chính:

° Dựa trên bộ nhớ (Memory-based)

° Dựa trên mơ hình (Model-based).

Thuật tốn lọc cộng tác dựa trên bộ nhớ thao tác trên toàn bộ cơ sở dữ liệu

người dùng dé đưa ra những dự đoán.

Ngược lại, thuật toán lọc cộng tác dựa trên mơ hình sử dụng cơ sở dữ liệu

người dùng dé đánh giá hoặc học mơ hình, sau đó sử dụng cho các dự đốn.

“* Phương pháp dựa trên bộ nhớ

Lọc cộng tác dựa trên độ bộ nhớ được tiếp cận theo hai phương pháp chính: Phương pháp lọc dựa vào người dùng (UserBased) va lọc dựa vào sản phâm (ItemBased).

Đặc điểm chung của ca hai phương pháp này là sử dung toàn bộ tập dữ liệu đánh giá dé dự đoán quan điểm của người dùng cần được gợi ý về các sản phẩm ma

họ chưa hề biết đến. Mỗi người dùng là một phần của một nhóm người dùng có sở thích giống nhau. Bằng việc xác định các “hàng xóm” của người dùng, ta có thé dự

đốn mức độ u thích các sản phẩm mới cho họ.

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

° Thuật toán lọc cộng tác dựa trên người dùng

Thuật tốn dùng tồn bộ dữ liệu người dùng-sản phẩm để tạo ra lời dự đoán. Hệ thống dùng thuật toán này sử dụng các kỹ thuật thống kê dé tìm ra một tập người

dùng (cịn gọi là hàng xóm) mà có cùng quan điểm với người dùng đích (ví dụ họ

đánh giá những sản phẩm khác tương tự hoặc họ có xu hướng mua một tập sản phẩm

tương tự nhau). Khi những người hàng xóm của người dùng đích được xác lập, hệ

thống sẽ sử dụng các thuật toán khác nhau để kết hợp sở thích của những hàng xóm

nay tạo ra lời dự đoán hoặc danh sách N sản phẩm tốt nhất gợi ý cho người dùng. Kỹ

thuật này được gọi là hàng xóm gần nhất hoặc lọc cộng tác dựa trên người dùng, một kỹ thuật rất phô biến và được sử dụng rộng rãi trong thực tế.

Thuật toán lọc cộng tác dựa trên người dùng do nhóm nghiên cứu GroupLensđưa ra. Thuật tốn được thực hiện theo 3 bước:

Bước 1: Tính tốn mức độ tương tự giữa các cặp người dùng

Bưóc 2: Xác định tập láng giéng cho người dùng can gợi ý

Bước 3: Tính tốn đưa ra dự đốn

° Thuật toán lọc cộng tác dựa trên sản phẩm

Phương pháp dự đốn sử dụng những sản phẩm tương tự trên chính người dùng sẽ hợp lý hơn, bởi vì người dùng quen thuộc hơn các sản phẩm được ưa thích

trước đây. Trong nhiều trường hợp, hệ thống lọc cộng tác dựa trên sản phẩm cho

thấy khả năng mở rộng tốt hơn và cải thiện dự đốn chính xác hơn.

Thuật tốn lọc cộng tác dựa trên sản phẩm xem xét tập sản phẩm mà người dùng đích đã đánh giá và tính toán chúng tương tự như thế nào với sản phẩm ¡ và sau

đó chon ra k sản phẩm tương tự nhất {ủ, 1z... „}. Trong thời gian đó, độ tương tự tương ứng cũng được tính tốn {s;;, s;¿,..., s„}. Khi những sản phẩm tương tự nhất

được tìm thấy, lời dự đốn được tính bằng cách lấy trung bình trọng số của đánh giá người dùng về những sản phẩm tương tự đó. Thuật tốn này gồm 3 bước chính:

Bước 1: Tính tốn độ tương tự sản phẩm

Bước 2: Xác định tập láng giéng cho sản phẩm can gợi ý

Bước 3: Tính tốn đưa ra lời dự đốn.

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

s Phương pháp dựa trên mơ hình

Khác với phương pháp dựa trên bộ nhớ, phương pháp lọc dựa trên mơ hình sử

dụng tập đánh giá để xây dựng mơ hình huấn luyện. Kết quả của mơ hình huấn luyện được sử dụng dé sinh ra dự đoán quan điểm của người dùng về các sản phâm được họ đánh giá. Ưu điểm của phương pháp này là mơ hình huấn luyện có kích thước nhỏ hơn rất nhiều so với ma trận đánh giá và thực hiện dự đoán nhanh. Mơ hình chỉ cần

cập nhật lại những thay đơi lớn và chỉ thực hiện lại phần xây dựng mô hình.

Một số mơ hình nổi tiếng: Mơ hình mang Bayes, mơ hình phân cụm, mơ hình ngữ nghĩa ân... Trong đó, mơ hình ngữ nghĩa an có giá trị tiềm năng nhất.

Mơ hình ngữ nghĩa an cho lọc cộng tác dựa vào các kỹ thuật thống kê trong đó các tham biến an được thiết lập trong một mơ hình hỗn hợp dé khám phá ra một cộng

đồng người dùng phù hợp với mẫu hồ sơ thích hợp. Các phương pháp lọc cộng tác

dựa trên mơ hình:

° Mơ hình ngữ nghĩa an:

Mơ hình ngữ nghĩa ân dựa vào các kỹ thuật thống kê, trong đó các tham biến ân

được thiết lập trong một mơ hình hỗn hợp dé khám phá ra một cộng đồng người dùng phù hợp với mẫu hồ sơ thích hợp. Phương pháp điển hình cho mơ hình này là phương

pháp Phân tích ma trận.

° Mơ hình mạng Bayes:

Mơ hình mạng Bayes biểu diễn mỗi sản phẩm như một đỉnh của đồ thi, trạng thái của mỗi đỉnh tương ứng với giá trị đánh giá của người dùng đó với sản phâm đã

được đánh giá.

° Mơ hình phân cụm:

Phân cụm dữ liệu (Data Clustering) là nhóm một tập các đối tượng thực thể

thành các lớp đối tượng tương tự. Một cum là một tập hợp các đối tượng dữ liệu mà

các phần tử của nó tương tự nhau cùng trong một cụm và phi tương tự với các đối

tượng trong các cụm khác.

1.1.4. Hạn chế trong lọc cộng tác và phương pháp đề xuất

Mặc dù đã được áp dụng thành công cho nhiều hệ thống thương mại điện tử, tuy vậy các phương pháp User-Based và Item-Based van tồn tại một số hạn chế đặc biệt là những hệ thong có nhiều người dùng mới (cold-start-user). Trên thực tế, các hệ thống gợi ý thường có số lượng người dùng và số lượng sản phẩm rat lớn ngày càng mở rộng. Do vậy ma trận đánh giá user-item rất lớn. Tuy nhiên, số lượng

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

người dùng đánh giá lên các sản phẩm lại rat hạn chế, vì thé dữ liệu đánh giá rat ít và vấn đề dữ liệu thưa được đặt ra.

Vấn đề này thường gặp trong một số trường hợp, đặc biệt là khi người dùng có đánh giá một số sản phẩm nhưng số lượng đánh giá này rất ít so với số sản phẩm có trong hệ thống thì một vấn đề khác xuất hiện là vấn đề độ bao phủ bị giảm (reduced coverage). Độ bao phủ là tỉ lệ phần trăm của sản pham mà hệ thống có thé gợi ý cho người dùng. Độ bao phủ giảm tức số lượng sản phẩm được gợi ý sẽ rất hạn chế. Ngồi ra khi dữ liệu thưa khơng thể xác định những người có cùng sở thích với nhau nếu như họ không cùng đánh giá trên một số sản phẩm. Vấn đề này gọi là van dé tinh bắc cầu của láng giêng (neighbor transitivity). Bởi vậy việc sử dụng đơn thuần dữ liệu đánh giá của người dùng dé xây dựng hệ gợi ý sẽ không thé đưa

ra dự đốn chính xác.

Dé giải quyết những van dé này thì hệ gợi ý mạng xã hội đã được phát trién.

Phương pháp tiếp cận này cho phép hệ thống đưa ra các lời gợi ý dựa trên những

đánh giá của tập người dùng có quan hệ xã hội (social relations) với người dùng đích.

Đầu vào của hệ gợi ý trong mạng xã hội là tập các quan hệ xã hội (Social Rating Network), mỗi người dùng sẽ đánh giá các sản pham và tạo ra các mối quan hệ với người dùng khác. Nhờ vậy, gợi ý trong mạng xã hội có thé đưa ra gợi ý đối với các người dùng mới miễn là họ có quan hệ tới tập các người dùng đủ lớn trong mạng xã hội. Theo thống kê, có hơn 50% người dùng trong tập dữ liệu thật là người dùng mới (có ít hơn 5 đánh giá). Vì vậy, việc gợi ý cho người dùng mới là rất cần thiết.

1.2. Hé gợi ý mạng xã hội (social recommender system)

Trong mục này, chúng ta sẽ giải quyết, làm rõ các vấn đề của mạng xã hội trong hệ gợi ý, các thuật ngữ “social network” và “trust network”, tìm hiểu về mang

quan hệ xã hội (Social Relation Network). Tiếp đến, chúng ta sẽ đánh giá từng phương pháp truyền thống được sử dụng cho mạng xã hội trong hệ gợi ý.

1.2.1. Định nghĩa về hệ gợi ý mạng xã hội

Một trong những mạng xã hội xuất hiện sớm nhất là vào những năm 1997. Những năm gần đây, vô số mạng xã hội xuất hiện như: Facebook, Twitter cho phép con người giao tiếp và kết nối với nhau một cách dé dang hơn. Dang chú ý hơn, lượng người dùng mạng xã hội là rất lớn. Ví dụ Facebook có 35,000,000,000 mối

liên hệ bạn bè. Sự phát triển không ngừng của mạng xã hội mở ra một hướng phát

triển cải tiến hơn của hệ gợi ý. Câu hỏi lớn đặt ra là: Mối quan hệ trong mạng xã hội

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

là rất phong phú, làm sao lợi dụng được thế mạnh này đưa vào hệ gợi ý, sử dụng mối quan hệ thân thiết giữa con người với con người giúp đưa ra cho người sử dụng những gợi ý phù hợp nhất.

1.2.2. Bài toán gợi ý mạng xã hội

Như đã đề cập trước đó, lọc cộng tác là phương pháp được áp dụng rộng rãi

để xây dựng hệ gợi ý, hầu hết các hệ gợi ý dựa trên mạng xã hội hiện nay đều dựa trên kỹ thuật lọc cộng tác. Vì vậy, trong luận văn này sẽ tìm hiểu về xây dựng hệ

gợi ý xã hội dựa trên lọc cộng tác. Hệ gợi ý xã hội có 2 đầu vào: 1 là thông tin đánh giá (giống với các hệ gợi ý truyền thống); 2 là các thông tin xã hội. Vì thế, phương pháp lọc cộng tác cho hệ gợi ý xã hội gồm 2 phần: (1) mơ hình lọc cộng tác cơ bản

và (2) mơ hình thơng tin xã hội:

Mơ hình CF cho hệ gợi ý xã hội = mơ hình CF cơ bản+ mơ hình thơng tin xã hội.

1.3. Một số phương pháp dự đốn cho hệ gợi ý xã hội

Trong mục này, chúng ta sẽ giải quyết, làm rõ các vấn đề của mạng xã hội trong hệ gợi ý, các thuật ngữ “social network” và “trust network”, tìm hiểu về mạng quan hệ xã hội (Social Relation Network). Tiếp đến, chúng ta sẽ đánh giá từng phương pháp truyền thống được sử dụng cho mạng xã hội trong hệ gợi ý.

Mạng xã hội trong hệ gợi ý:

Chúng ta sẽ dựa vào các đặc tính của mạng xã hội dé nang cao kha nang du đoán trong hệ gợi ý và giới thiệu một số thuật toán truyền thống sử dung mạng xã

hội trong hệ gợi ý.

1.3.1. TidalTrust

TidalTrust là một kỹ thuật sử dụng trong hệ gợi ý mạng xã hội, về cơ bản kỹ thuật

này dựa trên thuật tốn tìm kiếm theo chiều rộng, TidalTrust tính tốn độ tin tưởng giữa 2 người dùng dựa trên tiêu chí đường đi ngắn nhất. Ta gọi tập người dùng đã đánh giá sản

phẩm i là D, để dự đoán đánh giá của người dùng u với sản phâm i ta cần thực hiện 2 giai

đoạn chính: Tính tốn độ tin tưởng của người dùng u với từng người sử dụng đã đánh giá

sản phẩm ¡ và sử dụng các giá trị tin tưởng vừa tính được kết hợp với những đánh giá của người dùng với sản phẩm i dé đưa ra dự đoán của người dùng u với sản pham i.

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

1.3.2. MoleTrust

Ý tưởng của TidalTrust và MoleTrust là tương tự nhau, nhưng với MoleTrust tập người dùng đánh giá cho sản phẩm i phải thỏa mãn độ sâu nhỏ hơn giá trị Mg cho trước. Độ sâu này được tính bằng số bước dé đi từ người dùng u đến v hay số lần thực

hiện vòng lặp quay lui. MoleTrust thực hiện thuật tốn quay lui để tìm ra giá tri tin

tưởng gitra người dùng u va v.

1.4. Kết luận chương

Chương 1 của luận văn chúng ta đã tìm hiểu về hệ gợi ý truyền thống và một số phương pháp xây dựng hệ gợi ý truyền thống. Tìm hiểu về hệ gợi ý mạng xã hội và một số cách thức truyền thống xây dựng hệ gợi ý mạng xã hội, làm rõ các van đề về gợi ý trong mạng xã hội, tìm hiểu về mạng quan hệ xã hội (Social Relation Network).

Ở chương tiếp theo luận văn sẽ trình bày về các phương pháp tiếp cận mới xây

dựng hệ gợi ý mạng xã hội nhằm khắc phục những nhược điểm còn tồn tại O các

phương pháp trên.

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

CHUONG 2

PHƯƠNG PHAP PHAN TÍCH MA TRAN CHO HE GOT Ý

TRONG MANG XA HOI

Chương nay sé phan tích các quan hệ xã hội của người dùng (SRN) va xây

dựng phương pháp Phân tích ma trận dựa trên tập các quan hệ xã hội đó. Đồng thời mơ tả cách thức kiểm nghiệm và đánh giá kết quả của các phương pháp dựa trên các

bộ dữ liệu thực nghiệm.

Như đã đề cập ở chương 1, phương pháp tiếp cận dựa trên mơ hình sử dụng các tham số đặc trưng dé dưa ra dự đoán của người dùng vi vậy trong quá trình học phương pháp này chỉ cần lưu lại các tham số thay vì phải đưa ra đánh giá cho tất cả

các cặp người dùng — sản phâm như trong hướng tiếp cận dựa trên dữ liệu. Bởi vậy

phương pháp dựa trên mơ hình sẽ đưa ra dự đoán với tốc độ cao sau khi dữ liệu là các tham số đặc trưng được học. Phương pháp tiếp cận sử dụng kỹ thuật matrix factorization (MF) vào trong hệ gợi ý là một trong các hướng tiếp cận dựa trên mơ hình, trong đó các tham số đặc trưng được biểu diễn dưới dạng các đặc trưng của sản phẩm và người dùng. Hướng tiếp cận dựa trên mạng xã hội áp dụng mối quan

hệ giữa người dùng với người dùng vào trong hệ gợi ý. Việc đưa ra dự đoán đánh

giá của người dùng với một sản phẩm nào đó dựa trên đánh giá của những người dùng hàng xóm trực tiếp với họ.

Mục đích của kỹ thuật Phân tích ma trận là sinh ra các giá trị trong hai ma

trận U và V đề từ đó sử dụng vào trong hệ gợi ý.

Như đã phân tích các nhược điểm của lọc cơng tác và các phương pháp đề xuất tại mục 1.1.4, van đề người dùng mới là một van dé quan trọng trong phan này, luận văn xin đưa ra hướng giải quyết bằng cách sử dụng kỹ thuật Phân tích ma trận kết hợp dữ liệu mạng xã hội vào trong hệ gợi ý, có hai hướng tiếp cận là “Social

matrix factorization” (SocialMF) và “Social trust ensemble” (STE).

2.1. Phuong pháp Phan tích ma trận cho hệ gợi ý xã hội

Y tưởng chính cua Phân tích ma trận là việc chia ma trận lớn X thành hai ma trận có kích thước nhỏ hơn U và V sao cho ta có thể xây dựng lại X từ hai ma trận

nhỏ hon này càng chính xác càng tốt (Koren et al.,2009), nghĩa là X ~ UV.

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

2.2. Social trust ensemble (STE)

Social trust ensemble là một hướng tiép cận sử dung dữ liệu mang xã hội vào

trong hệ gợi ý, phương pháp nảy như một phương pháp mở rộng của kỹ thuật Phântích ma trận đơn giản. Dự đốn được đưa ra không chỉ sử dụng dữ liệu là 2 vector

dặc trưng tiềm ân U và V của người dùng u và sản phẩm i, nó cịn sử dụng các

vector đặc trưng tiềm ân U, V của hàng xóm trực tiếp với người dùng u.

2.3. Social matrix factorization

Khác với phương pháp STE đã được trình bay ở trên, phương pháp social

matrix factorization được tiép cận theo một hướng khác. Mang xã hội được nhắc đến trong phan này có thé đến từ nhiều nguồn khác nhau, nó có thé là mang xã hội như facebook, tweeter,... Dữ liệu mạng xã hội được biểu diễn dưới dạng các liên kết, trong đó những người nào có mối quan hệ thân thuộc sẽ được biểu diễn bằng 1 liên kết trực tiếp. Dữ liệu đầu vào luận văn sử dụng gồm có dữ liệu đánh giá của người

dùng với sản phẩm và dit liệu biểu diễn thông tin mạng xã hội giữa các người dùng.

2.4. Độ phức tạp của thuật toán STE và SocialMEF

bước nhảy trong thuật toán tối ưu (trong trường hợp này là thuật toán leo đồi).

Với mỗi lần đưa ra kết quả dự đoán, STE cần phải tính trung bình đánh giá của tất cả người dùng là hàng xóm trực tiếp, điều này làm nó chậm hơn so với thuật

tốn SocialMF.

2.5. Thực nghiệm và kết qua

2.5.1. Dữ liệu thực nghiệm

Dữ liệu trong phân thực nghiệm này là một mạng xã hội với sô lượng sảnphâm và người dùng lớn. Đó là mạng Epinions và Foursquare.

Epinions đây là một Wesite đánh giá sản phâm với cộng đồng người sử dụng rất tích cực. Người dùng với nhau thông qua sự tin cậy hay không tin cậy trong mạng, nó là sự kết hợp giữa việc đánh giá sản phâm của người dùng đưa lên cũng

như đánh giá chính người dùng đó. Dữ liệu của website được thu thập từ năm 1999

đến tháng Tám năm 2003.

Foursquare là dịch vụ mang xã hội mà người dùng có thể đánh giá địa điểm hay check-in địa diém hién tai cua minh. Mat khac, người dùng có thé thêm danh

sách các bạn bè và tạo mới các quan hệ xã hội.

</div>