GIỚI THIỆU
Đặt vấn đề
Sự phát triển của internet đã tạo ra một kho tàng thông tin phong phú, bao gồm âm nhạc, phim ảnh, sách vở và thông tin cá nhân, khiến người dùng cảm thấy bối rối và đặt ra câu hỏi "Cái gì là thích hợp với tôi hơn?" Hệ thống gợi ý (Recommender Systems - RS) đã được phát triển như một giải pháp hiệu quả để giải quyết vấn đề này Đặc biệt, sinh viên, đặc biệt là sinh viên trường đại học Thủ Dầu Một, thường xuyên truy cập mạng xã hội và thường chia sẻ những dòng trạng thái thể hiện tâm trạng, chủ yếu xoay quanh việc tìm kiếm những người bạn có sở thích và quan điểm tương đồng để cùng trò chuyện, chia sẻ và học tập.
Trước xu thế hiện nay, chúng tôi đã phát triển ý tưởng xây dựng một trang web để cung cấp môi trường thuận lợi cho người dùng trong việc tìm kiếm thông tin một cách nhanh chóng và dễ dàng thông qua hệ thống gợi ý.
Khảo sát các tài liệu liên quan
Một số tài liệu liên quan trong quá trình xây dựng website:
• Tài liệu nghiên cứu liên quan về thiết kế và lập trình website theo mô hình MVC
• Tài liệu nghiên cứu liên quan về Hệ thống gợi ý (Recommender Systems – RS) đặc biệt là thuật toán Asymmetric - Singular Value Decomposition
• Các trang web chuyên ngành về lĩnh vực máy học.
Giới hạn đề tài
Bài viết này tập trung vào việc nghiên cứu các thuật toán trong hệ thống gợi ý, nhằm xây dựng một website giới thiệu bạn bè dựa trên điểm số bình chọn, sở thích, tính cách và độ tuổi của các thành viên.
• Dữ liệu được nhập vào bằng việc thu thập các thông tin cơ bản như tên, tuổi, sở thích, châm ngôn về tình yêu…
• Website dễ sử dụng trên mọi trình duyệt Gợi ý được tương đối chính xác đối tượng bạn mà người sử dụng có khả năng phù hợp
Phương pháp nghiên cứu
• Thu thập dữ liệu từ việc khảo sát chính từ các bạn sinh viên trong trường đại học Thủ Dầu Một
Nghiên cứu cách xây dựng website kết hợp với các thuật toán mới trong lĩnh vực máy học (Machine Learning) nhằm tạo ra trang web gợi ý phù hợp Quá trình này sử dụng dữ liệu đầu vào để kiểm tra và đánh giá độ chính xác của thuật toán.
Nội dung của đề tài
• Tìm hiểu mô hình láng giềng, mô hình nhân tố tiềm ẩn
• Tìm hiểu mô hình Asymmetric - Singular Value Decomposition - SDV
• Sử dụng mô hình Asymmetric - SVD xây dựng thuật toán gợi ý theo mô hình láng giềng
• Áp dụng thuật toán xây dựng trang web gợi ý kết bạn
• Kiểm thử hệ thống với bộ dữ liệu lấy từ việc khảo sát thực tế với các bạn sinh viên
• Kết luận về kết quả nghiên cứu và nêu hướng phát triển tiếp theo của phương pháp
CÁC GIẢI PHÁP CÔNG NGHỆ
Công nghệ, nền tảng, ngôn ngữ lập trình
Chương trình được xây dựng trên:
- Sử dụng công nghệ ASP.Net MVC được tích hợp sẵn trong Microsoft Visual Studio 2015
- Sử dụng ngôn ngữ lập trình C_Sharp (C#) được tích hợp trong Visual studio 2015
Tổng quan về ASP.NET MVC
Trong kiến trúc MVC, một đối tượng đồ họa người dùng (GUI Component) bao gồm ba thành phần chính: Model, View và Controller Model chịu trách nhiệm quản lý dữ liệu và trạng thái của đối tượng đồ họa, trong khi View cung cấp giao diện trực quan để người dùng tương tác Controller đóng vai trò điều khiển sự tương tác giữa người dùng và đối tượng đồ họa, cũng như các thành phần khác trong hệ thống.
Hình 1: Mô hình MVC
Khi người dùng cần thay đổi trạng thái của đối tượng đồ họa, họ sẽ tương tác qua Controller Controller thực hiện các thay đổi trên Model, và khi Model thay đổi, nó sẽ phát thông điệp thông báo cho View và Controller Nhận được thông điệp này, View sẽ cập nhật hiển thị của mình để phản ánh chính xác trạng thái mới của Model Đồng thời, Controller cũng sẽ thực hiện các tương tác cần thiết để phản hồi lại người dùng hoặc các đối tượng khác.
Tổng quan về hệ gợi ý (Recommender System - RS)
Hệ gợi ý là công cụ hữu ích giúp tìm kiếm thông tin phù hợp trong khối lượng lớn dữ liệu hỗn độn Bằng cách sử dụng các kỹ thuật lọc, hệ thống này chọn ra những thông tin đặc trưng, hiển thị nội dung phù hợp với sở thích của người dùng Ứng dụng rộng rãi trong nhiều lĩnh vực, hệ gợi ý giải quyết vấn đề quá tải thông tin và giúp người dùng lựa chọn thông tin nhanh chóng, nâng cao trải nghiệm tìm kiếm.
Recommender Systems (RS) are a type of information filtering system designed to predict user preferences or ratings for specific items These systems play a crucial role in personalizing user experiences by suggesting relevant content based on individual tastes.
Hình 2: Sơ đồ hoạt động MVC
5 thông tin (item) nào đó mà họ chưa xem xét tới trong quá khứ (item có thể là bài hát, bộ phim, đoạn video clip, sách, bài báo, )
Các hệ thống gợi ý nổi bật như Amazon, Netflix, IMDb, Youtube, Last.fm và MovieLens đã thu hút lượng lớn khách truy cập nhờ vào tính năng hỗ trợ quyết định của mình.
Trong hệ thống gợi ý (RS), ba thông tin chính được quan tâm là người dùng, mục tin và phản hồi của người dùng đối với mục tin đó Mục tin có thể là sản phẩm, bộ phim, bài hát hoặc bài báo, tùy thuộc vào từng hệ thống Thông tin này thường được biểu diễn qua một ma trận, trong đó mỗi hàng đại diện cho một người dùng, mỗi cột là một mục tin, và mỗi ô chứa giá trị phản hồi, chẳng hạn như xếp hạng, thể hiện mức độ thích của người dùng đối với mục tin tương ứng Các ô có giá trị là những mục đã được người dùng xếp hạng trong quá khứ, trong khi các ô trống là những mục chưa được xếp hạng, tạo ra một ma trận thưa, vì mỗi người dùng chỉ xếp hạng cho một số ít mục trong quá khứ.
Hình 3: Ma trận biểu diễn dữ liệu trong RS (User - items raiting matrix)
Nhiệm vụ chính của hệ thống gợi ý (RS) là sử dụng dữ liệu quá khứ để dự đoán các ô còn trống trong ma trận, từ đó sắp xếp kết quả dự đoán theo thứ tự và chọn ra Top-N items để gợi ý cho người dùng Để đảm bảo tính hiệu quả trong việc cung cấp thông tin gợi ý, mỗi hệ thống cần có một mô hình gợi ý tối ưu, có khả năng khai thác tốt dữ liệu.
Nhóm giải thuật lọc nội dung (Content-based Filtering) cung cấp gợi ý cho người dùng bằng cách phân tích hồ sơ cá nhân của họ hoặc dựa trên các thuộc tính của những mục dữ liệu tương tự mà người dùng đã lựa chọn trước đó.
Nhóm giải thuật lọc cộng tác (Collaborative Filtering) chủ yếu sử dụng các kỹ thuật như phương pháp láng giềng (Neighborhood-based), dựa vào dữ liệu quá khứ của người dùng để đưa ra những gợi ý chính xác và phù hợp.
Có ba phương pháp chính trong hệ thống gợi ý: phương pháp dựa trên người dùng (user-based approach), phương pháp dựa trên các item tương tự (item-based approach), và phương pháp dựa trên mô hình (model-based approach) Phương pháp đầu tiên tập trung vào sở thích của người dùng, trong khi phương pháp thứ hai phân tích dữ liệu của những item tương tự Cuối cùng, phương pháp dựa trên mô hình xây dựng các mô hình dự đoán dựa trên dữ liệu thu thập từ quá khứ.
Nhóm kết hợp cả hai phương pháp trong hệ thống gợi ý sản phẩm dựa trên nội dung Hệ thống này xây dựng mô hình cho từng người dùng dựa trên đặc trưng của từng sản phẩm, không phụ thuộc vào các người dùng khác Đặc điểm nổi bật của các Hệ thống Gợi ý Dựa trên Nội dung là sử dụng thông tin từ hồ sơ của từng sản phẩm để đưa ra gợi ý phù hợp.
Ưu điểm của phương pháp này bao gồm việc tiết kiệm bộ nhớ và thời gian tính toán Nó còn có khả năng tận dụng thông tin đặc trưng của từng item thông qua bản mô tả, có thể được cung cấp bởi nhà cung cấp hoặc thu thập từ người dùng bằng cách yêu cầu gán thẻ cho các item Việc xây dựng vector tính năng cho mỗi item thường áp dụng các kỹ thuật phù hợp.
Xử lý ngôn ngữ tự nhiên (Natural Language Processing - NLP)
Nhược điểm của hệ thống lọc nội dung là nó không tận dụng thông tin từ các người dùng khác, dẫn đến việc thiếu sót trong việc hiểu hành vi mua hàng, vì hành vi này thường được nhóm thành các mẫu đơn giản Thêm vào đó, không phải lúc nào cũng có mô tả cho mỗi sản phẩm, và việc yêu cầu người dùng gán thẻ cũng gặp khó khăn do không phải ai cũng sẵn lòng thực hiện hoặc có thể gán thẻ theo cách cá nhân Các thuật toán NLP cũng phải đối mặt với thách thức trong việc xử lý từ đồng nghĩa, viết tắt, lỗi chính tả và ngôn ngữ khác nhau.
Ngày nay, hệ thống gợi ý chủ yếu sử dụng giải thuật lọc cộng tác (Collaborative Filtering - CF), dựa vào hành vi quá khứ của người dùng như lịch sử giao dịch, đánh giá sản phẩm và thời gian xem mục tin Đặc biệt, hệ thống này không yêu cầu người dùng phải cung cấp phản hồi rõ ràng Để đưa ra gợi ý, CF so sánh các đối tượng cơ bản như người dùng và các mục tin Giải thuật này áp dụng các kỹ thuật như phương pháp láng giềng và các mô hình nhân tố tiềm ẩn.
Mô hình láng giềng (neighborhood approach) sử dụng dữ liệu quá khứ của người dùng hoặc các item tương tự để cung cấp gợi ý chất lượng cao trong thời gian thực Phương pháp này có thể được chia thành hai loại: dựa trên người dùng (user-based approach) và dựa trên item (item-based approach), và thường áp dụng cho các tập dữ liệu lớn để tối ưu hóa trải nghiệm người dùng.
Mô hình nhân tố tiềm ẩn (Latent factor models) tương tự như phương pháp phân tích giá trị đơn (Singular Value Decomposition), giúp chuyển đổi cả mục tin và người dùng vào một không gian tiềm ẩn chung của các nhân tố Điều này cho phép so sánh trực tiếp giữa các mục tin và người dùng, nâng cao khả năng phân tích và dự đoán trong các hệ thống gợi ý.
Phương pháp này không chỉ cho phép biểu diễn và so sánh các khía cạnh khác nhau của dữ liệu mà còn thường mang lại kết quả dự đoán chính xác hơn so với các mô hình láng giềng.
NỘI DUNG NGHIÊN CỨU
Kỹ thuật K_Láng giềng dựa trên người dùng/mục tin (User/Item KNNs) (K_Nearest Neighbor)
K_Nearest Neighbor (KNN) là một trong những thuật toán học có giám sát đơn giản và hiệu quả trong một số trường hợp trong Machine Learning Thuật toán này không thực hiện việc học từ dữ liệu huấn luyện trong quá trình training; thay vào đó, mọi tính toán được thực hiện khi cần dự đoán kết quả cho dữ liệu mới.
Ngôn ngữ người Ngôn ngữ Máy Học Thuật ngữ tiếng anh
Câu hỏi Điểm dữ liệu Data point Đáp án Đầu ra, nhãn Output, Label
Dữ liệu nhập vào Tập dữ liệu tập huấn Training set
Tiêu chí tìm kiếm của người dùng Tập dữ liểu kiểm thử Test set
Các tiêu chí cụ thể để như Tuổi, Sỏ thích, địa chỉ…
Dữ liệu kiểm thử Test data point
Những tiêu chí không có chung Nhiễu Noise, Outlier
Các tiêu chí gần giống Điểm dữ liệu gần nhất Nearest Neighbor
Lọc cộng tác theo mô hình K láng giềng có hai cách tiếp cận chính: User_kNN, dựa trên sự tương tự giữa các người dùng, và Item_kNN, dựa trên sự tương tự giữa các mục tin.
- Một đối tượng được phân lớp dựa vào K láng giềng của nó K là số nguyên dương được xác định trước khi thực hiện thuật toán
Thuật toán K-NN hoạt động bằng cách xác định giá trị tham số K, tức số láng giềng gần nhất Đầu tiên, nó tính khoảng cách giữa đối tượng cần phân lớp (Query Point) và tất cả các đối tượng trong dữ liệu huấn luyện Sau đó, thuật toán sắp xếp các khoảng cách theo thứ tự tăng dần để xác định K láng giềng gần nhất Cuối cùng, nó thu thập tất cả các lớp của K láng giềng gần nhất và dựa vào lớp chiếm ưu thế để phân loại đối tượng cần phân lớp.
Trong phương pháp KNN (K-Nearest Neighbors), nhãn của một điểm dữ liệu mới được xác định dựa trên K điểm dữ liệu gần nhất trong tập huấn luyện Việc phân loại nhãn cho dữ liệu kiểm tra có thể thực hiện thông qua hình thức bầu chọn theo số phiếu (major voting) giữa các điểm gần nhất, hoặc bằng cách áp dụng trọng số khác nhau cho từng điểm gần nhất để đưa ra quyết định về nhãn.
KNN, hay K-Nearest Neighbors, là một thuật toán học máy dùng để dự đoán giá trị đầu ra cho một điểm dữ liệu mới dựa vào K điểm dữ liệu gần nhất trong tập huấn luyện Thuật toán này không xem xét đến việc có thể có những điểm dữ liệu nhiễu trong số K điểm lân cận đó.
- Phân tích K_Nearest Neighbor (KNN):
Hình 4: Phân tích KNN
Kỹ thuật k láng giềng dựa trên người dùng (User _kNN) xác định độ tương tự giữa hai người dùng bằng cách so sánh các đánh giá của họ trên cùng một sản phẩm Phương pháp này cho phép dự đoán xếp hạng của sản phẩm i bởi người dùng u dựa trên các xếp hạng của những người dùng tương tự Độ tương tự giữa người dùng u và người dùng u' có thể được tính toán thông qua chỉ số Cosine.
Trong bài viết này, chúng ta đề cập đến các đánh giá của người dùng đối với một item cụ thể Cụ thể, r_ui và r_u′i là các đánh giá của người dùng u và u' trên item i tương ứng Tập hợp các item được đánh giá bởi cả hai người dùng này được ký hiệu là Iuu' Giá trị đánh giá trung bình của người dùng u được biểu thị bằng r̅_u, trong khi giá trị đánh giá trung bình của người dùng u' được ký hiệu là r̅̅̅̅.
- Với phương pháp User_kNN, xếp hạng (đánh giá/feedback) của người dùng u trên sản phẩm i được dự đoán qua công thức: r̂ = r ui ̅ + u ∑ u′ϵKu sim(u, u ′ )(r u ′ i − r̅̅̅̅) u ′
Sim (u, u') là độ tương tự giữa người dùng u và u', được xác định bằng phương pháp Cosine Ku đại diện cho số lượng người dùng có độ lân cận gần gũi với người dùng u, trong đó k là số lượng láng giềng của u.
- Ưu và nhược điểm của KNN:
Quá trình huấn luyện có độ phức tạp tính toán bằng 0, giúp việc dự đoán kết quả từ dữ liệu mới trở nên đơn giản Hơn nữa, phương pháp này không yêu cầu bất kỳ giả định nào về phân phối của các lớp.
KNN có một số nhược điểm đáng lưu ý Đầu tiên, thuật toán này rất nhạy cảm với nhiễu khi giá trị K nhỏ Thứ hai, KNN thực hiện mọi tính toán trong giai đoạn kiểm tra, dẫn đến việc tính toán khoảng cách tới từng điểm dữ liệu trong tập huấn luyện tốn nhiều thời gian, đặc biệt là khi làm việc với cơ sở dữ liệu có nhiều chiều và số lượng điểm dữ liệu lớn Khi giá trị K tăng, độ phức tạp tính toán cũng gia tăng Cuối cùng, việc lưu trữ toàn bộ dữ liệu trong bộ nhớ có thể ảnh hưởng tiêu cực đến hiệu suất của KNN.
Đánh giá độ tin cậy của giải thuật
Có nhiều phương pháp đánh giá thuật toán như F-Measure và Area Under the ROC Curve (AUC), mỗi phương pháp phù hợp với từng lĩnh vực cụ thể Trong nghiên cứu này, phương pháp đo lỗi tối ưu nhất được sử dụng là Root Mean Square Deviation (RMSD).
Thực ghiệm và kết quả
Trong cơ sở dữ liệu, các thuộc tính địa chỉ được sử dụng để xác định mã vùng, trong khi các thuộc tính sở thích được phân loại theo hướng nội và hướng ngoại, giúp tính toán khoảng cách tương đồng một cách hiệu quả.
Hình 5: Quan hệ cơ sở dữ liệu
Hình 6: Màn hình đăng nhập
Hình 7: Màn hình đăng kí
- Kết quả áp dụng thuật toán ước lượng dự đoán của từng user một lên các user còn lại:
Bảng 2: Lần kiểm tra thứ nhất
Bảng 3: Tỉ lệ sai số sau lần kiểm tra thứ nhất
Bảng 4: Lần kiểm tra thứ hai
Bảng 5: Tỉ lệ sai số sau lần kiểm tra thứ hai Lần 3:
Bảng 6: Lần kiểm tra thứ ba
Sai số không xác định Lần 4:
Bảng 7: Lần kiểm tra thứ tư
Sai số không xác định Lần 5:
Bảng 8: Lần kiểm tra thứ năm
Bảng 9: Tỉ lệ sai số sau lần kiểm tra thứ năm Lần 6:
Bảng 10: Lần kiểm tra thứ sáu
Bảng 11: Tỉ lệ sai số sau lần kiểm tra thứ sáu
Bảng 12: Lần kiểm tra thứ bảy
Bảng 13: Tỉ lệ sai số sau lần kiểm tra thứ bảy Lần 8:
Bảng 14: Lần kiểm tra thứ tám
Bảng 15: Tỉ lệ sai số sau lần kiểm tra thứ tám Lần 9:
Bảng 16: Lần kiểm tra thứ chín
Bảng 17: Tỉ lệ sai số sau lần kiểm tra thứ chín Lần 10:
Bảng 18: Lần kiểm tra thứ mười
Sai số không xác định
- Kết quả độ đo lỗi RMSE qua mỗi lần thử thu được bảng sau:
Bảng 19: Kết quả đo lỗi sau mỗi lần kiểm tra
Sau 10 lần kiểm tra độ tin cậy của thuật toán, chúng tôi nhận thấy rằng: nếu số lượng mẫu trong tập kiểm tra quá ít, tỷ lệ lỗi sẽ cao hơn so với khi sử dụng tập kiểm tra lớn hơn Bên cạnh đó, nếu tỷ lệ đánh giá của người dùng trong tập kiểm tra quá thấp, tính xác thực của thuật toán sẽ không được đảm bảo Do đó, để nâng cao độ tin cậy, tất cả người dùng cần tham gia đánh giá toàn bộ tập kiểm tra mà không tự đánh giá chính mình, từ đó giúp cải thiện độ chính xác của thuật toán.
Lần kiểm tra Tỉ lệ lỗi (%)
