K-Means in Music Recommendations
k-means dựng Discover Weekly cho Spotify
Công ty nào đang ứng dụng Phân cụm k-means?
Sáng thứ Hai, bạn mở Spotify (dịch vụ phát nhạc lớn nhất thế giới) và thấy Discover Weekly đã sẵn sàng với 30 bài hát mới. Bài đầu tiên lạ hoắc nhưng hợp gu đến kỳ lạ. Làm sao Spotify biết bạn thích bài này, khi bạn còn chưa từng nghe?
Đằng sau sự “tiên tri” đó là một cách nhìn thú vị. Spotify biến bạn và mỗi bài hát thành một điểm trong không gian nhiều chiều. Gu âm nhạc của bạn là một toạ độ. Nhiệm vụ duy nhất là tìm các bài hát có toạ độ gần bạn, dùng đúng kỹ thuật clustering bạn đã học ở bài lý thuyết.
Vấn đề công ty cần giải quyết
Spotify có hơn 100 triệu bài hát và hơn 600 triệu người dùng. Dịch vụ này phân loại tới 6.291 thể loại vi mô (micro-genre), từ “trance guru” tới “cult-progressive-rock”.
Kho nhạc khổng lồ
100 triệu bài. Nghe thử mỗi bài một phút thôi cũng mất gần 200 năm liên tục.
Gu rất đa dạng
600 triệu người nghe. Không có hai người trùng gu 100%.
Phải cá nhân hoá
Gợi ý chung kiểu “Top 50 toàn cầu” không ai xem. Cần một danh sách riêng cho từng người.
Vấn đề cốt lõi: từ ma trận tương tác (ai đã nghe bài gì) giữa hàng trăm triệu người và bài hát, làm sao tìm ra những nhóm người nghe có gu giống nhau, rồi gợi ý cho bạn các bài mà “đồng minh thẩm mỹ” của bạn yêu thích nhưng bạn chưa từng nghe?
Cách Phân cụm k-means giải quyết vấn đề
Thu thập implicit feedback. Spotify không hỏi thẳng bạn thích bài gì, vì hỏi thì rườm rà mà câu trả lời thường không trung thực. Thay vào đó, họ ghi lại lượt nghe đủ lâu (trên 30 giây), lượt lưu vào playlist, lượt bỏ qua giữa chừng. Cộng dồn cả hệ thống là khoảng 1 TB mỗi ngày.
Biến người và bài hát thành “điểm”. Ma trận khổng lồ {người × bài} được phân rã thành hai ma trận nhỏ. Mỗi người dùng trở thành một vector 40 chiều, mỗi bài hát cũng là một vector 40 chiều. Hai điểm gần nhau trong không gian 40 chiều nghĩa là gu âm nhạc tương đồng.
Tìm láng giềng gần nhất. Với vector của bạn, Spotify dùng thư viện Voyager (nhanh hơn Annoy 10 lần) để tìm các bài hát có vector gần nhất. Đây chính là logic của k-means, chỉ khác ở chỗ k rất lớn và không gian nhiều chiều. Việc này tương đương với tìm cụm bài hát phù hợp nhất cho mỗi người nghe.
Bổ sung tín hiệu âm thanh. Một bài hát mới chưa có ai nghe thì sao? Bài toán này gọi là cold-start. CNN (mạng nơ-ron tích chập) phân tích phổ âm thanh thô của bài đó và dự đoán vector luôn, không cần chờ tới hàng nghìn lượt nghe đầu tiên.
Vòng phản hồi mỗi thứ Hai. Bạn nghe một bài trong Discover Weekly và bỏ qua một bài khác. Mỗi hành động cập nhật vector của bạn một chút. Tâm gu (user centroid) dịch chuyển nhẹ về phía bài bạn vừa thích, và tuần sau, 30 bài mới đã phản ánh dịch chuyển đó.
Không gian đặc trưng 2D: energy × danceability
Spotify thực tế dùng 40 chiều, nhưng chỉ 2 chiều cũng đủ để thấy các cụm tự nhiên hiện ra. Mỗi chấm là một bài hát tiếng Việt. Trục X là energy (năng lượng), trục Y là danceability (độ khiêu vũ). Bấm vào một bài để xem nó thuộc cụm nào.
Bấm tim ít nhất 2 bài hát trên để xem gợi ý. Gu của bạn sẽ hiện thành chấm vàng trong không gian bên trên.
Quan sát: mỗi lần bạn bấm tim thêm một bài, chấm vàng (gu của bạn) dời nhẹ. Các bài được gợi ý là những bài có khoảng cách d nhỏ nhất tới chấm vàng. Spotify thực tế làm điều này trên 40 chiều và hàng triệu bài hát, nhưng nguyên lý giống hệt.
Con số thật
Gu của bạn cập nhật thế nào khi thích thêm bài mới?
Mỗi khi bạn bấm tim, Spotify không viết lại toàn bộ hồ sơ. Nó chỉ dịch chuyển nhẹvector của bạn về phía vector của bài hát vừa thích. Bấm “Tiếp tục” để đi qua từng bước.
Bạn mới tạo tài khoản. Spotify chưa biết gì về gu của bạn nên vector khởi đầu là một giá trị mặc định, thường là trung bình toàn hệ thống, kiểu “người nghe phổ thông”.
Gu của bạn (chấm vàng) nằm giữa. Chưa có hướng rõ ràng.
Thử tự tay
Ba câu hỏi nhanh để kiểm tra bạn đã nắm vững nguyên lý Spotify dùng để gợi ý nhạc.
Bạn vừa tạo tài khoản Spotify mới và chưa nghe bài nào. Hệ thống sẽ gợi ý thế nào?
Bạn nghe 9 bài bolero và 1 bài EDM liên tục. Tuần sau Discover Weekly chủ yếu có gì?
Spotify ra bài mới chưa có ai nghe. Làm sao đưa vào gợi ý mà không phải chờ hàng nghìn lượt nghe đầu tiên?
Tại sao Spotify dùng 40 chiều mà không phải 2 chiều (energy và danceability) như đồ thị trên?
Nếu không có Phân cụm k-means, app sẽ ra sao?
Không có clustering và biểu diễn vector, Spotify sẽ phải so sánh trực tiếp mỗi người dùng với hàng trăm triệu người khác. Việc này bất khả thi về mặt tính toán. Một truy vấn gợi ý đơn giản sẽ mất hàng giờ thay vì mili-giây.
Kỹ thuật phân rã ma trận và clustering biến mỗi người, mỗi bài hát thành vector ngắn gọn. Bài toán so sánh giờ trở thành phép nhân vector đơn giản. Thư viện tìm kiếm láng giềng gần đúng (Voyager) tiếp tục tăng tốc bằng cách không duyệt toàn bộ không gian. Kết quả: Discover Weekly có thể tạo ra cho 600 triệu người mỗi thứ Hai, xong trong vài giờ tính toán. Nếu phải so từng cặp, đây là một con số không thể tưởng tượng được.
Nguyên lý này không chỉ dành cho nhạc. Netflix dùng cho phim, TikTok cho video, Shopee cho sản phẩm. Tất cả đều quy về cùng một bài toán: biến người và sản phẩm thành điểm, rồi tìm láng giềng gần nhất.