Thuật toán Colaborative fittering(CF) trong hệ thống gợi ý (phần 1)

Giới thiệu

Để thu hút sự chú ý của người sử dụng và tăng sự hài lòng của họ đối với kết quả tìm kiếm thông tin trực tuyến và hơn hết là tăng doanh số bán hàng, các nhà phát triển website và các nhà cung cấp dịch vụ bán hàng trực tuyến cố gắng dự đoán mối quan tâm của người dùng. Khuyến nghị đưa ra chủ yếu sẽ dựa trên những hành vi của người sử dụng và dữ liệu thông tin của người sử dụng.Như vậy đến đây chúng ta có thể thấy được thành phần đầu tiên của hệ thống khuyến nghị đó chính là “Bộ thu thập dữ liệu hành vi người dùng”và thành phần tiếp theo đó là “Bộ cơ sở dữ liệu lưu trữ thông tin người dùng”. Đối với một trang bán hàng trực tuyến như Hangtot.com thì một phần rất quan trọng trong dữ liệu được lưu trữ là các item và các thông tin đi kèm. Bất kì một hệ thống hay một chương trình máy tính nào cũng không thể thiếu được bộ xử lí dữ liệu.Thành phần chính để biến input=>output.Thành phần thứ tư có trong hệ thống gợi ý là “Bộ xử lí dữ liệu trung tâm”. Thành phần Quan trọng cuối cùng là “Bộ truy xuất dữ liệu” dùng để xuất dữ liệu ra màn hình.Bao gồm toàn bộ các qui tắc hiển thị dữ liệu.Phù hợp,hài hòa với giao diện của trang hangtot.com.Nơi hiển thị hợp lí giúp người dùng có thể dễ dàng xem thêm các sản phẩm mình đang quan tâm. Và dù có làm gì đi nữa cũng không được quên đi mục tiêu chính của hệ thống gợi ý là hỗ trợ người dùng xem các mục họ quan tâm một cách dễ dàng hơn và tránh các mục có thể bị quá tải.Từ mục tiêu như vậy đề ra các chức năng chính của hệ thống khuyến nghị bao gồm việc phân tích dữ liệu người dùng và giải nén thông tin dự đoán hữu ích hơn nữa. Hệ thống gợi ý áp dụng các kỹ thuật khai thác dữ liệu để xác định tính tương tự trong số hàng ngàn hoặc thậm chí hàng triệu dữ liệu.Kỹ thuật lọc cộng tác đã thành công trong việc giúp dự đoán,một phương pháp phổ biến sử dụng trong các hệ thống gợi ý trên các trang web nổi tiếng như:Amazon.com,YouTobe.com,Facebook.com,… (Hill et al . , 1995, Shardanand & Maes , 1995). Lọc cộng tác nhằm mục đích tìm kiếm các mối quan hệ giữa các cá nhân và các dữ liệu hiện có để xác định thêm sự giống nhau và cung cấp các gợi ý. Làm thế nào để xác định sự giống tương tự là một vấn đề quan trọng dự đoán sở thích ? tương tự các quyết định được kết luận khác nhau bằng các kỹ thuật lọc cộng tác . Ví dụ,người thích và không thích phim trong các danh mục tương tự sẽ được coi là những người có hành vi tương tự ( Chee et al. , 2001). Khái niệm hàng xóm gần nhất - thuật toán đã được bao gồm trong việc thực hiện các hệ thống khuyến nghị( Resnick et al. , 1994). Các mẫu thiết kế của các hệ thống tiên phong đề nghị tập trung vào các lĩnh vực giải trí ( Resnick et al. , 1994, Hill et al. , 1995, Shardanand & Maes , năm 1995,Dahlen et al. , 1998). Những thách thức của các thuật toán lọc cộng tác thông thường là vấn đề khả năng mở rộng ( Sarwar et al. , 2000a). Các thuật toán thông thường khám phá mối quan hệ giữa người sử dụng hệ thống trong các bộ dữ liệu lớn . Dữ liệu người dùng năng động, mà có nghĩa là các dữ liệu khác nhau trong một khoảng thời gian ngắn . Người dùng hiện tại có thể thay đổi họ mô hình hành vi , và người dùng mới có thể nhập vào hệ thống bất cứ lúc nào . hàng triệu dữ liệu người dùng , được gọi là các người láng giềng , sẽ được kiểm tra trong thời gian thực để cung cấp các khuyến nghị ( Herlocker et al. , 1999). Tìm kiếm trong số hàng triệu hàng xóm là một quá trình tốn nhiều thời gian . Để giải quyết, hợp tác dựa trên item thuật toán lọc được đề nghị cho phép giảm của tính toán vì tính chất của mặt hàng này là tương đối tĩnh ( Sarwar et al. , 2001). Đề nghị là một Top –N động cơ khuyến nghị thực hiện với các thuật toán khuyến nghị dựa trên item( Karypis. 2000, Deshpande & Karypis , 2004). Trong khi đó, số lượng các mặt hàng là thường ít hơn so với số lượng người dùng . ví dụ Amazon.com Trang phục & Phụ kiện cửa hàng cung cấp khoảng một tram năm mươi ngàn mặt hàng nhưng có nhiều hơn một triệu tài khoản khách hàng có đặt hàng từ cửa hàng này . Amazon.com sử dụng thuật toán dựa trên item cho đề nghị hợp tác lọc để tránh nhược điểm của thuật toán lọc cộng tác thông thường. dữ liệu lưu trữ sẽ tăng đột biến do các mối quan hệ mới được cập nhật là cấp số mũ.Đặt ra vấn đề rất nghiêm trọng trong khả năng mở rộng.Để giải quyết vấn đề trên,người ta đã áp dụng một số biện pháp: Chọn hàng xóm gần nhất. Số lượng hàng xóm gần nhất để lựa chọn và tiêu chuẩn sử dụng cho lựa chọn này có thể cũng có tác động nghiêm trọng đến chất lượng của hệ thống gợi ý. việc lựa chọn của những người hàng xóm sử dụng trong việc giới thiệu các mặt hàng thường được thực hiện theo hai bước:

một bước lọc toàn cầu mà chỉ có các ứng cử viên có nhiều khả năng được lưu giữ

Trong hệ thống gợi ý lớn có thể có hàng triệu người sử dụng và các mặt hàng , nó thường là không thể để lưu trữ các ( khác không ) giống nhau giữa mỗi cặp của người sử dụng hoặc các mục ,do hạn chế về bộ nhớ. Hơn nữa , làm như vậy sẽ rất lãng phí bởi chúng ta sẽ chỉ cần một số lượng chấp nhận được những mối tương quan để gợi ý. Quá trình lọc của 130 Christian Desrosiers và George Karypis là một bước cần thiết mà làm cho cách tiếp cận các người hàng xóm dựa trên thực tế bằng cách giảm số lượng trọng lượng tương tự để lưu trữ, và hạn chế số lượng hàng xóm(ứng cử viên)để xem xét trong dự đoán. Có một số cách thức có thể được thực hiện để giải quyết:

• Lọc Top- N(Top – hàng xóm) : Đối với mỗi người dùng hoặc item , chỉ có một danh sách giới hạn nhất định các hàng xóm gần nhất N và trọng lượng tương tự của mình được lưu giữ . Để tránh những vấn đề về hiệu quả và độ chính xác, N nên được lựa chọn cẩn thận.Bởi vì nếu N là quá lớn,việc lưu trữ sẽ trở nên cồng kềnh và tốc độ đưa ra dự đoán sẽ bị làm chậm.Mặt khác , việc lựa chọn một giá trị quá nhỏ để có thể tồn tại giảm phạm vi của phương pháp đề nghị , gây ra một số mặt hàng được đề nghị không bao giờ khuyến khích.
• Ngưỡng lọc : Thay vì giữ một số cố định các người hàng xóm gần nhất ,cách tiếp cận này sẽ giúp tất cả những người hàng xóm có trọng lượng tương tự có độ lớn lớn hơn một ngưỡng nhất định wmin sẽ được sử dụng. Trong khi điều này là linh hoạt hơn so với trước mặc dù giá trị wmin có thể khó khăn để xác định.
• lọc phủ định: Nói chung, mối tương quan đánh giá tiêu cực là ít đáng tin cậy hơn những người tích cực .Người ta có thể loại bỏ tất cả các điểm tương đồng tiêu cực cũng như những người có cường độ thấp hơn so với một định ngưỡng .

cho mỗi bước dự đoán ta phải chọn các ứng cử viên tốt nhất cho dự đoán này

Khi một danh sách các ứng cử viên hàng xóm đã được tính toán cho mỗi người dùng hoặc mục,dự đoán xếp hạng mới thường được thực hiện với k- láng giềng gần nhất , đó là những người hàng xóm k có trọng lượng tương tự có độ lớn nhất. quan trọng câu hỏi là có giá trị k cố định được sử dụng cho k hay không. Người ta đã chứng minh bằng thực nghiệm được rằng khi hạn chế bằng cách sử dụng một k nhỏ (ví dụ , k < 20), độ chính xác dự đoán là bình thường thấp.Nhưng khi k tăng , nhiều người hàng xóm đóng góp vào dự báo và phương sai được giới thiệu bởi hàng xóm khác là trung bình ra . Kết quả là, độ chính xác dự đoán cải thiện . Cuối cùng, độ chính xác thường giảm khi quá nhiều người hàng xóm được sử dụng,do thực tế rằng rất ít các mối quan hệ hàng xóm mạnh mẽ sẽ bị " Pha loãng " bởi nhiều những người yếu kém.Bởi vậy giá trị tối ưu của knên được xác định qua xác nhận .

• Tính hệ số tương quan Trọng lượng tương tự đóng một vai trò kép trong phương pháp gợi ý dựa trên lọc cộng tác: 1) họ cho phép lựa chọn người hàng xóm tin cậy mà đánh giá này được sử dụng trong dự đoán, và 2) họ cung cấp các phương tiện trong dự đoán. Việc tính toán trọng lượng tương tự là một trong những khía cạnh quan trọng nhất của việc xây dựng một hệ thống gợi ý dựa trên lọc cộng tác, vì nó có thể có một tác động đáng kể trên cả hai phương diện là tính chính xác và hiệu quả của của hệ thống.

• Một thước đo về sự giống nhau giữa hai đối tượng a và b , thường được sử dụng trong thông tin, bao gồm đại diện cho các đối tượng trong hình thức của hai vectơ xa và xb . và tính toán Cosine Vector (CV) (hoặc Vector Space(VP)) tương tự giữa các vectơ: cos(xa,xb)=a.b/|a||b|

Trong phần 2 sẽ tìm hiểu rõ hơn về các công thức tính toán trong thuật tóan Collaborative Filtering