Câu 3:

Nghiên cứu MF
Matrix Factorization: Phương pháp gợi ý dựa trên kỹ thuật phân rã ma trận
1. Khái niệm
Matrix Factorization là một hướng tiếp cận khác của Collaborative Filtering,
còn gọi là Matrix Decomposition, nghĩa là gợi ý bằng "kỹ thuật phân rã ma trận".
Kỹ thuật phân rã ma trận là phương pháp chia một ma trận lớn X thành hai ma
trận có kích thước nhỏ hơn là W và H, sao cho ta có thể xây dựng lại X từ hai ma trận
nhỏ hơn này càng chính xác càng tốt, nghĩa là

Có thể hiểu rằng, ý tưởng chính của Matrix Factorization là đặt items và users
vào trong cùng một không gian thuộc tính ẩn. Trong đó,

là một ma trận

mà mỗi dòng u là một vector bao gồm K nhân tố tiềm ẩn (latent factors) mô tả user u
và

là một ma trận mà mỗi dòng i là một vector bao gồm K nhân tố tiềm

ẩn mô tả cho item i.
Áp dụng phương pháp này vào bài toán gợi ý, chúng ta có x là một vector của
item profile.
Mục tiêu của chúng ta là tìm một vector w tương ứng với mỗi user sao cho
ratings đã biết của user đó cho item (y) xấp xỉ với:


Mở rộng với Y là utility matrix, giả sử đã được điền hết giá trị, ta có:

với M, N lần lượt là số users và số items.

Lưu ý, do X là được xây dựng dựa trên thông tin mô tả item và quá trình xây
dựng này độc lập với quá trình đi tìm hệ số phù hợp cho mỗi user nên việc xây dựng
item profile đóng vai trị quan trọng và có thể ảnh hưởng trực tiếp đến hiệu năng của
mơ hình. Thêm nữa, việc xây dựng mơ hình riêng lẻ cho mỗi user dẫn đến kết quả
chưa thực sự tốt vì khơng khai thác được đặc điểm giống nhau giữa các user.
Giả sử rằng ta không cần xây dựng trước các item profile mà ma trận này có thể
huấn luyện đồng thời với ma trận trọng số, hay nói các khác bài toán này là bài toán
tối ưu các ma trận X và W, trong đó X là ma trận của toàn bộ các item profiles, mỗi
hàng tương ứng với 1 item. Cịn W là ma trận của tồn bộ user models (các mơ hình
của users), mỗi cột tương ứng với một user. Chúng ta sẽ cố gắng xấp xỉ utility matrix
bằng tích của hai ma trận con là

Trong

đó, K được chọn thường nhỏ hơn rất nhiều so với M và N, và cả hai ma trận X và W
đều phải có bậc (rank) khơng được vượt q K


2. Xây dựng và tối ưu hàm mất mát
Cụ thể, quy trình xây dựng và tối ưu hàm mất mát như sau:
2.1. Hàm mất mát
Đầu tiên, chúng ta sẽ xét hàm mất mát khơng có cả bias và biến tối ưu cho X và
W:

Trong đó,

nếu item thứ m đã được đánh giá bởi user thứ n, ‖○‖ là căn

bậc hai của tổng bình phương tất cả các phần tử của ma trận, s là tồn bộ số ratings
đã có. Thành phần thứ nhất chính là trung bình sai số của mơ hình. Thành phần thứ

hai trong hàm mất mát phía, có tách dụng giúp tránh overfitting.
Lưu ý, tương tự như NBCF, các giá trị ratings được sử dụng là các giá trị đã
chuẩn hóa, bằng cách trừ đi trung bình cộng các giá trị ratings đã biết trong cùng một
hàng (với iiCF) và trong cùng một cột (với uuCF) – bài trước. Trong một số trường
hợp, ta có thể khơng cần chuẩn hóa ma trận utility matrix nhưng những trường hợp
đó sẽ phải dùng các kĩ thuật khác để giải quyết tính cá nhân trong các ratings.
Tiếp theo, chúng ta sẽ tối ưu X và W bằng cách cố định từng ma trận và tối ưu
ma trận còn lại cho tới khi hội tụ.
2.2. Tối ưu hàm mất mát


Khi cố định X, việc tối ưu W chính là bài toán tối ưu của Content-based
Filtering:

Ngược lại, khi cố định W, việc tối ưu X được đưa về tối ưu hàm:

Hai bài toán này sẽ được tối ưu bằng Gradient Descent.
Chúng ta có thể thấy rằng, bài tốn tối ưu W có thể được tách thành N bài tốn
nhỏ (N là số lượng users), mỗi bài toán tương ứng với việc đi tối ưu một cột của ma
trận W.


Sau khi cố định X, tính W và ngược lại, cố định W và tính X cho đến khi các ma
trận này hội tụ, ta sẽ thu được ma trận X và W cần tìm. Từ đó, dự đốn các giá trị ratings
chưa biết.
Ngoài phương pháp trên, để tăng độ chính xác của thuật tốn này, ta sẽ xét hàm mất
mát với bias và hệ số tối ưu cho X và W.
Như trong NBCF, chúng ta có bước chuẩn hóa ma trận để tránh sự thiên lệch do sự
khó ttính hay dễ tính khác nhau giữa các users. Với MF, ta có thể chuẩn khơng chuẩn hóa
mà sử dụng trực tiếp các giá trị ratings ban đầu, bằng cách tối ưu các biases cùng lúc với

X và W.
Trong trường hợp này, ratings của user m cho item n được xác định bởi công thức:


Cuối cùng, ta sẽ thu được các ma trận X, b, W, d, từ đó dự đốn các ratings chưa
biết.
Trên đây là những lý thuyết căn bản về Matrix Factorization.

Nghiên cứu KNN
1. KNN là gì?
KNN (K-Nearest Neighbors) là một trong những thuật tốn học có giám sát đơn
giản nhất được sử dụng nhiều trong khai phá dữ liệu và học máy. Ý tưởng của thuật tốn này
là nó khơng học một điều gì từ tập dữ liệu học (nên KNN được xếp vào loại lazy learning),
mọi tính tốn được thực hiện khi nó cần dự đốn nhãn của dữ liệu mới.


Lớp (nhãn) của một đối tượng dữ liệu mới có thể dự đốn từ các lớp (nhãn) của k
hàng xóm gần nó nhất.
Ví dụ:
Giả sử ta có D là tập các dữ liệu đã được phân loại thành 2 nhãn (+) và (-) được
biểu diễn trên trục tọa độ như hình vẽ và một điểm dữ liệu mới A chưa biết nhãn. Vậy làm
cách nào để chúng ta có thể xác định được nhãn của A là (+) hay (-)?
Có thể thấy cách đơn giản nhất là so sánh tất cả các đặc điểm của dữ liệu A với tất
cả tập dữ liệu học đã được gắn nhãn và xem nó giống cái nào nhất, nếu dữ liệu (đặc điểm)
của A giống với dữ liệu của điểm mang nhãn (+) thì điểm A mang nhãn (+), nếu dữ liệu A
giống với dữ liệu nhãn (-) hơn thì nó mang nhãn (-), trơng có vẻ rất đơn giản nhưng đó là
những gì mà KNN làm.
Trong trường hợp của KNN, thực tế nó khơng so sánh dữ liệu mới (khơng được
phân lớp) với tất cả các dữ liệu khác, thực tế nó thực hiện một phép tính tốn học để đo
khoảng cách giữa dữ liệu mới với tất cả các điểm trong tập dữ liệu học D để thực hiện phân

lớp. Phép tính khoảng cách giữa 2 điểm có thể là Euclidian, Manhattan, trọng số,
Minkowski, …


Các bước trong KNN
-

Ta có D là tập các điểm dữ liệu đã được gắn nhãn và A là dữ liệu chưa được phân

-

loại.
Đo khoảng cách (Euclidian, Manhattan, Minkowski, Minkowski hoặc Trọng số) từ

-

dữ liệu mới A đến tất cả các dữ liệu khác đã được phân loại trong D.
Chọn K (K là tham số mà bạn định nghĩa) khoảng cách nhỏ nhất.
Kiểm tra danh sách các lớp có khoảng cách ngắn nhất và đếm số lượng của mỗi lớp

-

xuất hiện.
Lấy đúng lớp (lớp xuất hiện nhiều lần nhất).
Lớp của dữ liệu mới là lớp mà bạn đã nhận được ở bước 5.

Ví dụ:


Giả sử ta có tập dữ liệu D có gắn nhãn gồm 15 điểm như trên ảnh.

-

Điểm cần dự đoán nhãn A(3,9)
Ta tính khoảng cách từ điểm A đến các điểm dữ liệu trong D bằng công thức

-

Euclidian.
Ta chọn K= 5, và tìm ra 5 điểm có khoảng cách gần với điểm A nhất.
Trong 5 điểm ta thấy có 4 điểm mang nhãn (+) và 1 điểm mang nhãn (-).
Vậy ta có thể đưa ra kết luận là điểm A cần dự đoán mang nhãn (+).


Ưu điểm
Thuật toán đơn giản, dễ dàng triển khai.
Độ phức tạp tính tốn nhỏ.
Xử lý tốt với tập dữ liệu nhiễu
Nhược điểm
Với K nhỏ dễ gặp nhiễu dẫn tới kết quả đưa ra khơng chính xác
Cần nhiều thời gian để thực hiện do phải tính tốn khoảng cách với tất cả các đối tượng
trong tập dữ liệu.
Cần chuyển đổi kiểu dữ liệu thành các yếu tố định tính.