Phương pháp lai chuyển đổi cải thiện vấn đề dữ liệu thưa của kỹ thuật lọc cộng tác trong hệ thống tư vấn

TÓM TẮT:

Lọc cộng tác là một kỹ thuật mạnh đã được sử dụng trong nhiều hệ thống tư vấn với những thành công đáng kể. Kỹ thuật này sử dụng cơ sở dữ liệu sở thích của người dùng đối với các sản phẩm để dự đoán những sản phẩm mà họ có thể thích. Nhưng dữ liệu sở thích thu được rất ít, chiếm không tới 10%, gây ảnh hưởng nhiều đến hiệu quả tư vấn. Nhiều công trình nghiên cứu đã đưa ra giải pháp khác để giải quyết vấn đề này và bước đầu đã có những hiệu quả đáng kể, cải thiện phần nào vấn đề dữ liệu thưa, tuy nhiên vẫn còn tồn tại những khuyết điểm riêng. Bài viết nghiên cứu và đề xuất một phương pháp mới để cải thiện vấn đề dữ liệu thưa, cho hiệu quả tư vấn cao hơn cách tiếp cận lọc cộng tác truyền thống và một số phương pháp khác.

Từ khóa: Lọc cộng tác, hệ thống tư vấn, dữ liệu thưa, giải quyết vấn đề dữ liệu thưa.

1. Đặt vấn đề

Gần đây, hệ thống tư vấn (Recommender Systems - RS) được phát triển rộng rãi ở nhiều lĩnh vực, đặc biệt là thương mại điện tử. Tuy vậy, RS vẫn không ngừng phát triển và được nhiều nhà nghiên cứu quan tâm bởi có nhiều vấn đề cần nghiên cứu như dữ liệu thưa (Spare Data Problem - SDP), xuất phát chậm (Cold Start Problem - CSP)... Những vấn đề này làm ảnh hưởng trực tiếp đến độ chính xác của dự đoán. Vì vậy, đây là một trong những trọng tâm nghiên cứu của RS [1].

Có hai cách tiếp cận chính trong các RS là lọc dựa trên nội dung (content-based filtering - CB) và lọc cộng tác (collaborative filtering - CF). Bài viết tập trung vào hướng tiếp cận lọc cộng tác của RS, hay còn gọi là hệ thống lọc cộng tác. Trong một RS gồm N người dùng U = {u1, u2, …, un}, M sản phẩm I = {i1, i2, …, im} với ma trận đánh giá R = (rij). Trong hệ thống lọc cộng tác, số lượng người dùng |U| và số lượng sản phẩm |I| là rất lớn. Nhiệm vụ của hệ thống lọc cộng tác là dự đoán cho người dùng hiện thời dựa trên ma trận R với hầu hết các giá trị rij = Ø. Tuy vậy, mỗi người dùng chỉ đưa ra một ít đánh giá cho tập sản phẩm khiến ma trận đánh giá R có số lượng đánh giá rij ≠ Ø nhỏ hơn rất nhiều so với rij = Ø. Tỉ lệ dữ liệu đánh giá chiếm tỉ lệ rất thấp, cụ thể là trong tập MovieLens (http://grouplens.org/datasets/movielens/) dữ liệu đánh giá chỉ chiếm 4,3% hoặc tỉ lệ trong tập dữ liệu EachMovie chỉ chiếm 2,4%. Trong RS, người ta xem vấn đề này như là SDP.

Bảng 1. Ví dụ về ma trận đánh giá user-item

SDP đã gây trở ngại cho quá trình tính độ tương tự. Ví dụ cần xác định mức độ tương tự giữa người dùng u4 và u2 trong Bảng 1. Vì số các sản phẩm của cả u4 và u2 đều đánh giá không phủ nhau hay không giao nhau, do đó độ tương tự giữa u4 và u2 tính theo các độ đo tương tự là 0. Điều này ảnh hưởng trực tiếp đến phương pháp huấn luyện và kết quả dự đoán vì các đánh giá khác rỗng của người dùng u2 không bao giờ được xem xét đến quá trình huấn luyện và tham gia đóng góp vào kết quả dự đoán cho người dùng u4. Trường hợp tương tự cho 2 sản phẩm i1 và i2. Độ tương tự của hai sản phẩm này cũng bằng 0 do không có người dùng nào đánh giá lên cả 2 sản phẩm.

Bên cạnh đó, SDP còn làm cho việc xác định tập hàng xóm cho người dùng hiện thời kém tin cậy. Ví dụ, ta cần dự đoán các sản phẩm cho người dùng u4 trong Bảng 1, dựa trên các độ tương tự ta sẽ tính toán được u4 tương tự với u1 vì r[u1, i1] = r[u4, i1] = 5. Kết quả là các sản phẩm i4, i5 sẽ được tư vấn cho u4 vì u4 tương tự với u1 mà u1 “thích” i4, i5. Tuy nhiên, ta cũng tính toán được u4 tương tự với u3 vì r[u3, i3] = r[u4, i3] = 5, do đó i4, i5 sẽ bị gỡ bỏ trong danh sách các sản phẩm phân bổ cho u4 vì u4 tương tự với u3 mà u3 “không thích” i4, i5. Như vậy, nếu coi hoặc u1 hoặc u3 là láng giềng của u4 thì kết quả dự đoán trở nên kém tin cậy. Nếu xem xét cả u1 và u3 đều là láng giềng của u4 thì xảy ra mâu thuẫn vì u1 và u3 hoàn toàn không tương tự nhau.

Khi hệ thống có thêm một người dùng mới, người dùng này cần có một số đánh giá ban đầu cho một vài sản phẩm thì hệ thống mới có thể dự đoán cho họ những sản phẩm tiếp theo. Tương tự như vậy, đối với các sản phẩm mới chưa được bất kỳ người dùng nào đánh giá, chúng sẽ không được tư vấn cho bất cứ người dùng nào cho đến khi được một vài người dùng đánh giá. Trong RS, người ta gọi đây là vấn đề xuất phát chậm (CSP).

2. Các nghiên cứu liên quan

Nhiều nhà nghiên cứu đã tập trung vào giải quyết vấn đề này nhằm nâng cao hiệu quả của hệ thống tư vấn. Có thể tóm tắt như sau: giảm số chiều, phân cụm, phương pháp biểu diễn bằng đồ thị, phương pháp lai giữa lọc cộng tác và dựa trên nội dung.

Chiến lược đơn giản nhất để giảm số chiều của ma trận đánh giá là tạo lập nên các cụm sản phẩm hoặc cụm người dùng, sau đó sử dụng những cụm này như những đơn vị cơ bản để sinh ra dự đoán. Tác giả Ungar & Foster [2] sử dụng kỹ thuật

K-median phân cụm người dùng và sản phẩm độc lập nhau, sau đó các cụm người dùng và sản phẩm được phân cụm lại để tạo nên các cụm có mức độ tương tự cao theo cả người dùng và sản phẩm.

Xun Zhou và cộng sự [3] đề xuất việc sử dụng phương pháp phát hiện ngữ nghĩa ẩn (LSM) dựa trên kỹ thuật phân rã giá trị riêng (SVD). Tuy nhiên, trong nhiều trường hợp thông tin hữu ích có thể bị mất trong quá trình giảm số chiều ma trận khiến kết quả dự đoán gặp nhiều hạn chế.

Một hướng tiếp cận khác hạn chế vấn đề dữ liệu thưa dựa vào việc khai thác các mối liên hệ gián tiếp trên ma trận đánh giá. Bài viết [4] biểu diễn người dùng và sản phẩm như một đồ thị hai phía (Bipart Graph Model). Một phía là tập người dùng, phía còn lại là tập sản phẩm, mỗi cạnh nói từ đỉnh người dùng đến đỉnh sản phẩm được thiết lập nếu người dùng đã mua hoặc đánh giá cao cho sản phẩm tương ứng. Dựa trên biểu diễn mối quan hệ người dùng và sản phẩm, dữ liệu được điền vào các ô còn trống trong ma trận đánh giá thực hiện bằng cách lan truyền có trọng số trên đồ thị hai phía.

Một số tác giả cho rằng thông tin trên ma trận thưa không đủ đưa ra kết quả tư vấn hiệu quả nên kết hợp với nguồn dữ liệu khác như thêm thông tin về sản phẩm và thông tin người dùng bằng cách lai hệ thống tư vấn lọc cộng tác với hệ thống tư vấn dựa vào nội dung [5] hay tích hợp mạng xã hội vào mô hình dự đoán [6].

Một số nhóm tác giả khác còn độc đáo hơn là dựa vào thông tin sở thích người dùng sách mà tư vấn phim [7]. Kết hợp với nguồn dữ liệu khác cũng là một giải pháp hay để giải quyết vấn đề ma trận thưa, nhưng phương pháp này cũng gặp không ít khó khăn khi phân tích và chọn nguồn dữ liệu phù hợp.

Qua các hướng giải quyết hạn chế ma trận thưa nêu trên, phương pháp đề xuất của chúng tôi theo hướng tiếp cận thứ nhất, nghĩa là không bổ sung thông tin từ những nguồn dữ liệu khác mà chỉ tận dụng dữ liệu của ma trận đánh giá. Bài viết đề xuất hướng kết hợp giữa hai phương pháp truyền thống của lọc cộng tác là lọc theo người dùng (User-based) và lọc theo sản phẩm (Item-based) theo cách lai chuyển đổi trình bày ở mục 3.

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

Trong quá trình nghiên cứu các phương pháp nâng cao hiệu quả của hệ thống, thông tin từ ma trận đánh giá tuy đơn giản nhưng quan trọng, cần được khai phá triệt để. Xem xét hai hướng tiếp cận của lọc cộng tác là dựa trên người dùng và dựa trên sản phẩm, mỗi phương pháp có những ưu điểm và nhược điểm có thể bổ trợ nhau nếu kết hợp sử dụng đúng giai đoạn.

Ví dụ, nếu chỉ dùng phương pháp lọc cộng tác dựa vào người dùng, khi có một người dùng mới thêm vào hệ thống, họ hoàn toàn chưa có một đánh giá nào thì phương pháp này không thể đưa ra dự đoán được. Nếu kết hợp với phương pháp dựa trên sản phẩm tại giai đoạn này, hoàn toàn có thể khắc phục tình trạng người dùng mới, vì lúc này dựa vào sản phẩm tương tự để đưa ra dự đoán. Ngược lại, nếu có một sản phẩm mới thêm vào hệ thống, ta vẫn có thể đưa ra dự đoán dựa và người dùng. Với phương pháp Lai chuyển đổi, có thể lựa chọn phương pháp tùy theo từng trường hợp cụ thể nhằm phát huy tối đa hiệu quả của các phương pháp.

Dựa trên những nghiên cứu các phương pháp đã có, bài viết đề xuất một phương pháp mới là phương pháp tư vấn Lai chuyển đổi giữa tư vấn dựa trên người dùng và tư vấn dựa trên sản phẩm. Theo kiến trúc như Hình 1. Cốt lõi của phương pháp là tận dụng triệt để dữ liệu đánh giá ma trận user-item để tìm ra điều kiện chuyển đổi giữa hai phương pháp User-based và Item-based sao cho mang lại hiệu quả tối ưu nhất.

Hình 1: Mô hình lai đề xuất

Gọi φu và φi lần lượt là ngưỡng độ tương tự của hai người dùng và hai sản phẩm. φu và φi có giá trị trong khoảng từ -1 đến 1. Khoảng này thể hiện mức độ tương đồng của 2 người dùng hoặc 2 sản phẩm, ví dụ khi φu = -1 tức độ tương đồng thấp nhất, 2 người dùng có sở thích hoàn toàn trái ngược nhau, φu = 0 tức 2 người dùng không tương đồng, sở thích ko giống nhau, φu = 1 tức 2 người dùng có sở thích hoàn toàn giống nhau. Giá trị của φ giúp ta xác định tập láng giềng lân cận nhất của người dùng hoặc sản phẩm.

Gọi S(u) là tập các độ tương đồng lớn hơn ngưỡng φu của người dùng u và hàng xóm của u, ta có:

Gọi S(i) là tập các độ tương đồng lớn hơn ngưỡng φi của sản phẩm i và những sản phẩm tương tự i, ta có:

Lúc này có thể xác định điều kiện để chuyển đổi lựa chọn phương pháp User-based hay Item-based.

Trường hợp đầu tiên phải xét đến là hai tập S(u) và S(i) đề rỗng, tức số láng giềng của cả u và i không đủ để đưa ra dự đoán nên ta sẽ đưa ra dự đoán dựa trên toàn bộ ma trận đánh giá bằng giá trị trung bình của tất cả đánh giá trên ma trận ký hiệu là ṝ:

Trường hợp thứ hai là khi tập S(u) bằng rỗng và tập S(i) khác rỗng, tức số lượng láng giềng của người dùng u không đủ để đưa ra kết quả dự đoán nên sẽ dựa vào tập láng giềng của sản phẩm i để đưa ra kết quả dự đoán theo công thức (4) nhưng chỉ chọn những láng giềng trong tập S(i):

Ngược lại, khi tập S(i) bằng rỗng và tập S(u) khác rỗng thì số lượng láng giềng của sản phẩm i không đủ để đưa ra kết quả dự đoán nên phải dựa vào tập láng giềng của người dùng u để đưa ra kết quả dự đoán theo công thức (5).

Trường hợp cuối cùng là cả hai tập S(u) và S(i) đều khác rỗng, lúc này sẽ dựa vào cả hai tập láng giềng để đưa ra kết quả dự đoán. Kết quả được tính theo công thức sau.

Vậy ta có thể tóm tắt điều kiện để lựa chọn hai phương pháp User-based và Item-based như Hình 2.

Hình 2: Mô hình thuật toán Lai chuyển đổi

4. Kết quả và thảo luận 4.1. Phương pháp thực nghiệm

Thuật toán đề xuất được thực nghiệm trên bộ dữ liệu của MovieLens. Đây là bộ dữ liệu được cộng đồng nghiên cứu về hệ thống tư vấn sử dụng phổ biến [8, 9]. MovieLens là cơ sở dữ liệu được xây dựng bởi nhóm nghiên cứu GroupLens của Trường Đại học Minnesota. Nhóm GroupLens đã tập hợp được nhiều bộ dữ liệu với kích thước khác nhau để phục vụ cho việc nghiên cứu hệ thống tư vấn như MovieLens 100k (ML_100k), MovieLens 1M (ML_1M), MovieLens 10M, MovieLens 20M,… Trong phạm vi thực nghiệm của đề tài chỉ sử dụng 2 bộ dữ liệu MovieLens 100k và MovieLens 1M để thử nghiệm. Hai bộ dữ liệu được mô tả chi tiết trong Bảng 2.

Bảng 2. Mô tả dữ liệu MovieLens

Bài viết sử dụng hai độ đo MAE (Mean Absolute Error) và RMSE (Root Mean Square Error) để đánh giá hiệu quả của thuật toán đề xuất. Hai độ đo này thường sử dụng phổ biến trong nghiên cứu về hệ thống tư vấn nói chung và lọc cộng tác nói riêng. MAE tính độ lệch của dự đoán đánh giá của thuật toán và đánh giá thực tế (đánh giá của bộ test).

Trong công thức 7, MAE tính độ lệch trung bình tuyệt đối giữa dự đoán tư vấn rec(u, i) và giá trị đánh giá thực tế ru,i cho tất cả người dùng u ϵ U và tất cả các sản phẩm i thuộc tập kiểm tra testsetu.

Tương tự như MAE, RMSE cũng dùng để đo độ chính xác của dự đoán, nhưng RMSE chú trọng hơn nhiều vào độ lệch lớn hơn, được tính theo công thức 8.

Giá trị của MAE và RMSE tỉ lệ nghịch với độ chính xác của dự đoán, nghĩa là MAE và RMSE càng nhỏ thì độ chính xác của dự đoán càng cao.

Bài viết có sử dụng thư viện LibRec trong quá trình cài đặt các thuật toán so sánh và thuật toán đề xuất nhằm đảm bảo tính đúng đắn và khoa học trong quá trình thực nghiệm. LibRec là thư viện phát triển bằng Java nhằm phục vụ cho nghiên cứu của hệ thống tư vấn trong thư viện có rất nhiều thuật toán đã được công bố của các tác giả nghiên cứu lĩnh vực hệ thống tư vấn. Để thực nghiệm, bài viết đã cài đặt 3 thuật toán gồm User-based và Item-based là 2 thuật toán của lọc cộng tác truyền thống và phương pháp Lai chuyển đổi (Switch Hybrid) đề xuất.

4.2. Kết quả thực nghiệm

Tiến hành thực nghiệm trên 5-fold của bộ dữ liệu MovieLens 100k với 2 độ đo MAE và RMSE, sau đó tính trung bình. Thực nghiệm được so sánh bởi 3 phương pháp: User-based, Item-based, và phương pháp đề xuất lai chuyển đổi (Switch Hybrid).

Sau khi thực nghiệm nhận thấy kết quả của thuật toán đề xuất Lai chuyển đổi có giá trị MAE và RMSE nhỏ hơn hẳn so với 2 thuật toán truyền thống của lọc cộng tác dựa trên người dùng và dựa vào sản phẩm (Hình 3 và Hình 4). Điều này cho thấy thuật toán đề xuất có độ chính xác dự đoán cao hơn.

Hình 3: Biểu đồ so sánh bằng độ lỗi MAE

Hình 4: Biểu đồ so sánh bằng độ lỗi RMSE

Do thực nghiệm được cài đặt và phát triển trên thư viện Librec.net nên dễ dàng so sánh với một số thuật toán đã cài đặt sẵn trong thư viện này. Kết quả Bảng 3 cho thấy dự đoán của phương pháp Lai chuyển đổi mà bài viết đề xuất tốt hơn hẳn các phương pháp UserCluster, ItemCluster, URP, BUCM, GPLSA,… Kết quả thực nghiệm này được thực thi trên cùng 1 bộ dữ liệu MovieLens 100k.

Bảng 3. So sánh các phương pháp khác

5. Kết luận

Bài viết đã trình bày phương pháp Lai chuyển đổi giữa lọc cộng tác dựa trên người dùng và lọc cộng tác dựa trên sản phẩm theo một cách mới. Kết quả thực nghiệm trên bộ dữ liệu MovieLens cho thấy phương pháp đề xuất cho kết quả dự đoán chính xác hơn hai phương pháp lọc truyền thống và một số phương pháp khác trong thư viện Librec.

Phương pháp đề xuất đã tìm cách cải thiện độ chính xác của dự đoán trên ma trận thưa nhằm mang lại kết quả dự đoán chính xác hơn, nâng cao hiệu quả của hệ thống tư vấn chứ không “làm dày” ma trận thưa. Trong nghiên cứu tiếp theo sẽ phát triển thêm bước “làm dày” ma trận thưa bằng cách thêm vào giai đoạn “huấn luyện lại”. Tức khi đưa dự đoán đánh giá của người dùng cho một sản phẩm nào đó, có thể lựa chọn những giá trị đáng tin cậy để đưa vào tập huấn luyện hỗ trợ cho lần dự đoán tiếp theo, với mong muốn sẽ cải thiện kết quả dự đoán của phương pháp Lai chuyển đổi này.

TÀI LIỆU THAM KHẢO:

C. Desrosiers and G. Karypis (2008), "Solving the sparsity problem: Collaborative filtering via indirect similarities," in Technical Report. Department of Computer Science and Engineering University of Minnesota 4-192 EECS Building 200 Union Street SE Minneapolis, MN 55455-0159 USA.
L. H. Ungar and D. P. Foster (1998), "Clustering methods for collaborative filtering," in AAAI workshop on recommendation systems, 114-129
Zhou, Xun & He, Jing & Huang, Guangyan & Zhang, Yanchun. (2014). SVD-based incremental approaches for recommender systems. Journal of Computer and System Sciences, 81(4), 717-733.
N. D. Phuong and T. M. Phuong (2008), "A graph-based method for combining collaborative and content-based filtering," in PRICAI 2008: Trends in Artificial Intelligence, Springer, Vol 5351, 859-869.
L. Pasquale, G. d. Marco and S. Giovanni (2011), "Content-based Recommender Systems: State of the Art and Trends," in Recommender Systems Handbook, Springer, 73-105.
Huynh-Ly Thanh-Nhan, Le Huy-Thap and Nguyen Thai-Nghe (2017). Toward integrating social networks into Intelligent Tutoring Systems. In proceedings of the 2017 International Conference on Knowledge and Systems Engineering (KSE 2017), 112-117, ISBN 978-1-5386-3576-6.
B. Li, Q. Yang and X. Xue (2009), "Can Movies and Books Collaborate? Cross-Domain Collaborative Filtering for Sparsity Reduction," in IJCAI'09: Proceedings of the 21st international jont conference on Artifical intelligence, 2052-2057.
A. Gunawardana and C. Meek (2008), "Tied boltzmann machines for cold start recommendations," in Proceedings of the 2008 ACM conference on Recommender systems, ACM, 19-26.
D. Jannach, M. Zanker, A. Felfernig and G. Friedrich (2014), "Hybrid recommendation approaches," in Recommender systems: An introduction, Cambridge University Press, 124-142.

A SWITCHING HYBRID APPROACH

TO IMPROVE SPARSE DATA PROBLEM

OF COLLABORATIVE FILTERING

RECOMMENDER SYSTEM

• Master. HUYNH LY THANH NHAN

• Master. TRAN THI TUYET VAN

• Master. NGUYEN QUANG HUY

An Giang University, An Giang, Vietnam

Vietnam National University Ho Chi Minh City, Vietnam

ABSTRACT:

Collaborative filtering is a powerful technique that has been used in many recommender systems with considerable success. This technique uses the interested databases of users with items to predict what products they might like. Nevertheless, these interested databases collected very few under 10%, greatly affect the efficiency of recommender system. Many research projects have given different solutions to solve this problem. Initially, they have made significant efficiency, improved somewhat sparse data problem, but they still have existed their own shortcomings. In this paper, we research and propose a new method for improving sparse data problem, which offers higher efficiency of reccommendation than the approaching traditional collaborative filtering and some other methods.

Keywords: Collaborative filtering, recommender system, sparse data, solving sparse data problem.