Tư vấn thông tin dựa trên lọc cộng tác

14 CHƯƠNG 2. TƯ VẤN THÔNG TIN DỰA TRÊN LỌC CỘNG TÁC 2.1 Tư vấn thông tin dựa trên lọc cộng tác CF phát triển rất nhanh và phổ biến trong hầu hết các hệ thống tư vấn [3], [20]. Trong CF, dữ liệu đầu vào của hệ thống là một tập đánh giá của người dùng trên các tài nguyên. Dựa trên các đánh giá này, người dùng có thể được so sánh với nhau, hình thành nên khái niệm người dùng tương đồng. Và cũng dựa trên các đánh giá này, tài nguyên cũng được so sánh với nhau, hình thành nên khái niệm tài nguyên tương đồng. Điểm đánh giá tài nguyên của một người dùng có thể được dự đoán dựa trên các đánh giá của các người dùng “lân cận” hoặc các tài nguyên “gần gũi”. Chúng ta có thể phân các phương pháp dự đoán điểm đánh giá của một người dùng cho một tài nguyên ra làm 3 cách tiếp cận chính:  Dựa trên người dùng (User-based)  Dựa trên tài nguyên (Item-based)  Dựa trên mô hình (Model-based) Những cách tiếp cận này được mô hình hóa và so sánh trong phần này. Hình 2.1 mô tả bảng dữ liệu đánh giá của người dùng lên tài nguyên. Gọi U là tập N người dùng, I là tập M tài nguyên và R là tập các đánh giá rui của người dùng u  U lên tài nguyên i  I. Su  I đại diện cho một tập tài nguyên mà người dùng u đã đánh giá. I U I1 … Ij … IM u1 r11 … r1j … r1M … ui ri1 … rij … riM … uN rN1 .. rNj … rNM Hình 2.1: Ma trận đánh giá R của người dùng lên tài nguyên 15 Mục tiêu của các phương pháp CF là có thể dự đoán đánh giá pai của một người dùng a lên một tài nguyên i. Người dùng a được giả định là hiệu lực (active), nghĩa là người này đã đánh giá một vài tài nguyên, vì vậy Sa  . Tài nguyên được dự đoán thì chưa được biết đối với người dùng a, do đó i  Sa. (Hình 2.2) Hình 2.2: Quy trình CF Hình 2.2 mô tả quy trình CF bao gồm 2 nhiệm vụ chính là:  Dự đoán: cho ra giá trị Paj thể hiện đánh giá có tiềm năng nhất của người dùng a lên tài nguyên j.  Tư vấn: cho ra danh sách N tài nguyên {TiN} mà người dùng a thích nhất. 2.1.1 Cách tiếp cận dựa trên người dùng (User-based approaches) Theo cách tiếp cận dựa trên người dùng [3], việc dự đoán đánh giá của một người dùng lên một tài nguyên được dựa trên các đánh giá của những người dùng “lân cận” trên tài nguyên đó. Vì vậy một độ đo tương đồng giữa những người dùng cần được định nghĩa trước khi một tập những người dùng hàng xóm gần nhất được chọn ra. Độ đo tương đồng này sẽ được thảo luận ở phần (2.4.4). Bây giờ, gọi sim(a, u) là độ tương đồng giữa người dùng a và u. Số lượng những người dùng hàng xóm cần xem xét thường được xác lập bởi một tham số hệ thống, được ký hiệu K. Vì vậy 16 tập hàng xóm của người dùng a, ký hiệu là Ta, được tạo bởi K người dùng có độ tương đồng lớn nhất đối với a. Một cách khả thi để dự đoán đánh giá của người dùng a lên tài nguyên i là sử dụng tổng trọng số các đánh giá của những hàng xóm gần nhất u  Ta đã đánh giá tài nguyên i: (2.1) Để xem xét sự khác nhau trong việc sử dụng thang đánh giá của những người dùng khác nhau, việc dự đoán dựa trên độ lệch từ đánh giá trung bình được đề xuất. pai có thể được tính bằng tổng của đánh giá trung bình của người dùng a với tổng trọng số của các độ lệch từ đánh giá trung bình của các hàng xóm đã đánh giá tài nguyên i: (2.2) là đánh giá trung bình của người dùng u (2.3) Thật vậy, giả sử rằng những tài nguyên được đánh giá có điểm giữa 1 và 5. Một người dùng có thể đánh một tài nguyên anh ta thích là 4 và tài nguyên anh ta không thích là 1. Tuy nhiên, một người dùng khác có thể đánh giá tài nguyên anh ta thích là 5 và một tài nguyên anh ta không thích là 2. Bằng việc sử dụng độ lệch từ đánh giá trung bình, ngữ nghĩa riêng của từng người, về mặt thể hiện sự ưa thích trên tài nguyên mà họ đánh giá, được giải thích tốt hơn. 17 Độ phức tạp thời gian của các tiếp cận dựa trên người dùng là O(N2xMxK) cho cấu trúc mô hình hàng xóm và O(K) cho dự đoán một đánh giá. Độ phức tạp chung là O(NxK). 2.1.2 Cách tiếp cận dựa trên tài nguyên (Item-based approaches) Gần đây, có một sự quan tâm gia tăng trong việc sử dụng cách tiếp cận dựa trên tài nguyên [25], [19], [6]. Theo cách tiếp cận này, một độ đo tương đồng giữa các tài nguyên phải được đưa ra để xác định các tài nguyên hàng xóm. Dự đoán đánh giá của một người dùng lên một tài nguyên được suy ra từ các đánh giá của người dùng đó trên các tài nguyên hàng xóm. Các độ đo tương tự khả thi sim(i, j) định nghĩa giữa các tài nguyên i và j được thảo luận ở phần 2.1.4. Cũng như cách tiếp cận dựa trên người dùng, kích thước K của tập tài nguyên hàng xóm là một tham số hệ thống, và cần được định nghĩa. Cho Ti tập hàng xóm của tài nguyên i, có 2 cách cho việc dự đoán các đánh giá mới của người dùng có thể được xem xét: 1. Sử dụng tổng trọng số (2.4) 2. Sử dụng một tổng trọng số của những độ lệch từ các đánh giá tài nguyên trung bình. (2.5) là đánh giá trung bình trên tài nguyên i (2.6) 18 Độ phức tạp thời gian của các tiếp cận dựa trên tài nguyên là O(M2xNxK) cho cấu trúc mô hình hàng xóm và O(K) cho một dự đoán đánh giá. Độ phức tạp chung O(MxK). 2.1.3 Cách tiếp cận dựa trên mô hình (Model-based approaches) Độ phức tạp bậc 2 của hai cách tiếp cận trên thì quá cao cho tập dữ liệu lớn và nhiều ứng dụng thực tế cần các dự đoán có thể được tạo ra nhanh chóng. Những yếu tố này là điểm khởi đầu cho cách tiếp cận dựa trên mô hình [4]. Ý tưởng chung là bắt nguồn từ một mô hình dữ liệu được lưu trữ (off-line) để dự đoán các đánh giá trực tuyến (on-line) nhanh nhất có thể. Mô hình đầu tiên được đề xuất bao gồm việc phân nhóm người dùng sử dụng kỹ thuật phân cụm (clustering) và sau đó việc dự đoán đánh giá một người dùng trên một tài nguyên chỉ sử dụng các đánh giá của những người dùng thuộc về cùng nhóm. Các mô hình Bayesian cũng được đề xuất để mô hình sự phụ thuộc giữa các tài nguyên. Việc phân nhóm tài nguyên được nghiên cứu kỹ trong [29]. Cũng vậy, các mô hình dựa trên các luật kết hợp cũng được nghiên cứu bởi [27] và [18]. Các thuật toán phân nhóm theo xác xuất cũng được sử dụng để cho phép người dùng thuộc về, một mức độ nào đó, các nhóm khác nhau [22], [16]. Và sự phân cấp các nhóm cũng được đề xuất, để nếu một nhóm người dùng được xem xét không có ý kiến trên một tài nguyên cụ thể, thì nhóm cao hơn có thể được xem xét [14]. Trong những tiếp cận như vậy, số lượng các nhóm là quan trọng chính yếu. Trong nhiều trường hợp, các số lượng khác nhau của các nhóm được kiểm tra, và số lượng nào dẫn đến tỉ lệ lỗi thấp nhất trong việc kiểm tra chéo sẽ được giữ. Các nhóm nói chung được biểu diễn bởi tâm của chúng, và sau đó đánh giá dự đoán của một người dùng cho một tài nguyên có thể tính trực tiếp từ đánh giá của tâm gần nhất với nó. Nếu cả hai, nhóm người dùng và nhóm tài nguyên được sử dụng, đánh 19 giá dự đoán là đánh giá trung bình, trên các tài nguyên (thuộc nhóm tài nguyên) của các người dùng (thuộc nhóm người dùng). Độ phức tạp thời gian của thuật toán dựa trên phân nhóm là O(NxMxKxL) cho giai đoạn học và O(I) cho một dự đoán đánh giá. Độ phức tạp chung, khi việc phân nhóm cả người dùng và tài nguyên được xem xét là O((N+M)xK). 2.1.4 Các độ đo tương tự (Similarity Measures) Độ tương đồng giữa người dùng và tài nguyên là định nghĩa thiết yếu trong CF. Độ đo đầu tiên được đưa ra trong [3] là độ tương đồng Pearson - tương đương với Cosine của độ lệch từ khoảng giữa. Độ tương đồng đơn giản Cosine và Manhattan cũng là những độ tương đồng truyền thống. Vì những độ tương đồng này chỉ xét tập thuộc tính chung giữa hai vector. Do đó hai vector có thể hoàn toàn tương đồng ngay cả khi chúng chỉ chia sẽ một đánh giá trên một thuộc tính. Những độ đo như vậy có khuyết điểm. Ví dụ, trong ngữ cảnh tư vấn phim, xem xét trường hợp khi một người dùng là fan của khoa học viễn tưởng trong khi một người khác chỉ xem hài kịch, hơn nữa hai người dùng này chưa đánh giá bất kỳ phim chung nào vì vậy độ tương đồng của họ là rỗng (null). Bây giờ cả hai nói rằng họ thích “Men In Black”, một phim hài kịch khoa học viễn tưởng. Do đó những người dùng này trở nên hoàn toàn tương đồng nhau theo những độ đo đã được trình bày trên, ví dụ này cho thấy họ chỉ có một điểm (phim) tham chiếu chung được đánh giá bằng nhau. Tuy nhiên, độ tương tự Jaccard không bị khuyết điểm này, vì nó đo độ chồng lấp thuộc tính của hai vector với nhau. Mặt khác, độ đo này không xem xét sự khác nhau giữa các đánh giá của hai vector. Trong trường hợp này, nếu 2 nguời dùng xem cùng một số phim nhưng có ý kiến hoàn toàn trái ngược nhau trên những phim này, thì chúng được xem là tương tự nhau theo độ tương đồng Jaccard. Khi Jaccard được kết hợp với một độ đo tương đồng khác, một hệ thống có thể thu lợi từ sự bổ sung qua lại của chúng. Ví dụ, nhân Jaccard với một độ đo tương 20 đồng khác cho ra một kết quả mới. Trong trường hợp này, Jaccard phục vụ như một trọng số. Dó đó, có thể wPearson thể hiện một độ đo Pearson trọng số - được sinh ra bởi phép nhân Pearson và Jaccard. Tương tư, wCosine và wManhattan ký hiệu tương ứng cho sự kết hợp của Jaccard với Cosine và Manhattan. Giá trị của Cosine dựa trên độ đo tương đồng nằm giữa -1 và 1 trong khi các độ đo tương đồng khác có giá trị nằm giữa 0 và 1. Các kết quả thực nghiệm cho thấy độ tương đồng kết hợp này dành cho kiểu dữ liệu có giá trị tượng trưng (ví dụ. rất thưa), thường cho kết quả tốt hơn. Trong những nhược điểm chính của hệ thống CF, chúng ta có thể đề cập đến vấn đề cold start, xuất hiện khi một người dùng mới chưa cung cấp bất cứ đánh giá nào hoặc một tài nguyên mới chưa nhận bất kỳ đánh giá nào từ người dùng. Hệ thống thiếu dữ liệu để cho ra các tư vấn phù hợp (ví dụ, hệ thống tư vấn MovieLens đòi hỏi ít nhất 15 đánh giá trước khi nó có thể cung cấp tư vấn). Đối với vấn đề người dùng mới, [21][21] đề xuất khai thác dữ liệu nhân khẩu học về người dùng chẳng hạn như tuổi, vị trí, nghề nghiệp để cải tiến các tư vấn ban đầu được cung cấp cho một người dùng mới, mà họ chưa đánh giá bất kỳ tài nguyên nào. Vấn đề tài nguyên mới và người dùng mới có thể xử lý bằng cách sử dụng cách tiếp cận tư vấn lai (Hybrid Filtering). Cách tiếp cận này là sự kết hợp của hai kiểu CB và CF theo một cách nào đó để cho ra kết quả tốt hơn. 2.2 Tạo lập cộng đồng Ở phần 2.1.3 luận văn đã đề cập đến các phương pháp theo hướng tiếp cận dựa trên mô hình, trong phần này luận văn sẽ trình bày các phương pháp thuộc mô hình phân nhóm (clustering model) dùng để tạo lập cộng đồng (nhóm người dùng) trong hệ thống. Bên cạnh đó, luận văn cùng trình bày mô hình cộng đồng đa tiêu chí. 2.2.1 Mô hình phân nhóm (clustering model) Trong CF ta có thể phân nhóm người dùng hoặc tài nguyên theo các kỹ thuật phân nhóm, sau đó dựa trên các nhóm người dùng hoặc tài nguyên hoặc kết hợp cả 21 hai, các tư vấn được tạo ra. Các kỹ thuật phân nhóm được trình bày chi tiết trong [29]. Ở đây luận văn sẽ trình bày 2 kỹ thuật cơ bản nhất được sử dụng trong nhiều ứng dụng CF là phương pháp hàng xóm gần nhất và phương pháp khoảng cách tâm. Hai phương pháp này thành lập cộng động dựa trên khoảng cách giữa các người dùng, và khoảng cách này được tính bằng độ tương đồng hoặc cosine của các vector đánh giá của người dùng. 2.2.1.1 Phương pháp phân nhóm hàng xóm gần nhất (nearest neighbor clustering) Đây là phương pháp được sử dụng nhiều nhất [3], [4], [25]. Phương pháp này sử dụng hệ số k làm ngưỡng xác lập cộng đồng, k có thể là ngưỡng số lượng thành viên của một nhóm (gọi tắc là ngưỡng thành viên) hoặc ngưỡng khoảng cách giữa 2 thành viên trong một nhóm (gọi tắc là ngưỡng khoảng cách). Đầu tiên xuất phát từ người dùng u, hệ thống tìm ra k người dùng có khoảng cách gần u nhất (trong trường hợp k là ngưỡng thành viên) hoặc tất cả người dùng có khoảng cách không lớn hơn k (trong trường hợp k là ngưỡng khoảng cách) để hình thành một cộng đồng. Ví dụ ở hình 2.3, ta thấy các phần tử (đại diện cho người dùng) được phân thành 3 nhóm C1, C2, C3 với k = 6 (trong trường hợp k là ngưỡng thành viên) hoặc khoảng cách giữa hai phần tử bất kỳ trong một nhóm phải nhỏ hơn k (trong trường hợp k là ngưỡng khoảng cách). Hình 2.3: Phân nhóm bằng phương pháp hàng xóm gần nhất 22 2.2.1.2 Phương pháp phân nhóm khoảng cách tâm (k-mean clustering) Phương pháp này sẽ phân người dùng trong hệ thống thành k nhóm, bắt đầu bằng việc chọn tâm của k nhóm một cách ngẫu nhiên. Sau đó lần lượt gán mỗi người dùng vào nhóm có khoảng cách từ tâm của nó đến người dùng đó là gần nhất. Tâm của mỗi nhóm chính là vector trung bình của của các vector đánh giá của tất cả người dùng hiện có trong nhóm. Ví dụ ở hình 2.4 cho thấy, hệ thống có 3 cộng đồng và người dùng u sẽ thuộc về cộng đồng C3 vì khoảng cách từ u đến tâm C3 là ngắn nhất so với khoảng cách từ u đến tâm của C1 và C2. Hình 2.4: Phân nhóm bằng phương pháp k-mean Hai phương pháp trên đơn giản và hiệu quả trong phần lớn các trường hợp, ngoại trừ nhược điểm về thời gian và chi phí vì phải tính toán trên toàn bộ ma trận đánh giá R. 2.2.2 Tạo lập cộng đồng dựa trên mô hình cộng đồng đa tiêu chí Với hai phương pháp phân nhóm theo hàng xóm gần nhất và khoảng cách tâm thì quá trình tạo lập cộng đồng chỉ dựa trên một tiêu chí là điểm đánh giá. Trong trường hợp người dùng mới đăng nhập vào hệ thống, khi đó hệ thống chưa có thông tin đánh giá của người dùng. Để tạo lập cộng đồng, hệ thống phải cung cấp các tài nguyên để người dùng đánh giá và dựa trên những thông tin này để thành lập cộng 23 đồng. Theo cách này người dùng phải tốn khá nhiều công sức trước khi được xếp vào một cộng đồng nào đó. Ngoài ra, thông tin tư vấn mà nguời dùng nhận được không có tính đa dạng và phong phú (vì chỉ dựa trên một tiêu chí là điểm đánh giá). Mô hình không gian cộng đồng đa tiêu chí có thể khắc phục được những hạn chế trên [21]. Với cách tiếp cận này, mỗi thuộc tính trong profile (tuổi tác, nghề nghiệp, nơi cư trú, trình độ, chủ đề quan tâm, sở thích, thông tin phản hồi …) đều có thể được sử dụng như một tiêu chí để thành lập cộng đồng. Như vậy, một người dùng có thể thuộc về nhiều cộng đồng khác nhau và tập hợp tất cả những cộng đồng trong hệ thống hình thành nên một không gian cộng đồng và sẽ được biểu diễn bằng một bảng cộng đồng (-community table) Tmxn.  U   j  n u1 … ui uij … um Hình 2.5: Bảng cộng đồng Tmxn Trong đó, ui  U là tập người dùng, j  A là tập tiêu chí dùng để phân nhóm hoặc phân hoạch người dùng, mỗi giá trị T[ui, j] thể hiện người dùng ui thuộc về cộng đồng tiêu chí j. Với những tiêu chí đơn giản (ví dụ: tuổi, nghề nghiệp, nơi cư trú …) hệ thống có thể phân nhóm người sử dụng bằng cách so sánh trực tiếp. Ngược lại, với những tiêu chí phức tạp (ví dụ: nền tảng kiên thức, thông tin đánh giá, …) hệ thống có thể sử dụng các phương pháp hàng xóm gần nhất, khoảng cách tâm, … để phân hoạch người sử dụng. 24 Trong trường hợp người dùng mới chưa có thông tin gì về đánh giá, tiếp cận này còn đưa ra một phương pháp quy nạp dựa trên luật để suy diễn ra cộng đồng theo tiêu chí đánh giá của người dùng dựa trên những cộng đồng theo tiêu chí khác. 2.3 Định vị người dùng mới vào cộng đồng Khi một người dùng mới đăng ký vào hệ thống, để cung cấp những thông tin tư vấn dựa trên cộng đồng, hệ thống phải định vị họ vào các cộng đồng thích hợp. Đối với những cộng đồng dựa vào tiêu chí là các giá trị nhân khẩu học (tuổi, nghề nghiệp, nơi cư trú …) thì việc định vị người dùng vào cộng đồng là tương đối đơn giản. Tuy nhiên, trong các phương pháp CF cổ điển, việc thành lập cồng đồng dựa vào tiêu chí đánh giá (điểm đánh giá của người dùng lên tài nguyên) thì tại thời điểm này, cộng đồng theo tiêu chí đánh giá của người dùng mới vẫn còn chưa biết. Vì thế, hệ thống không thể cung cấp tư vấn thích hợp. Để giải quyết vấn đề này, hiện nay có nhiều cách tiếp cận khác nhau [24]. 2.3.1 Khai thác thông tin thăm dò Theo phương pháp này hệ thống yêu cầu người dùng mới đánh giá một số lượng tối thiểu các tài nguyên. Hệ thống có thể đưa ra một danh sách tài nguyên đã được chọn một cách ngẫu nhiên hoặc chọn theo một tiêu chí nào đó để người dùng đánh giá. Tuy nhiên cách này có thể gây khó khăn cho người dùng trong trường hợp người dùng không thể đưa ra những đánh giá cụ thể cho một số tài nguyên nào đó vì chưa biết gì về những tài nguyên đó hoặc nhiều lý do khác. Vì vậy người dùng mới cũng có thể tự chọn những tài nguyên trong phạm vi hiểu biết của mình để đánh giá. 2.3.2 Cung cấp profile mẫu Trước tiên, hệ thống sẽ xây dựng sẵn những profile mẫu – profile là một cấu trúc mô tả đặc trưng của người dùng - và sau đó dựa trên những giá trị nhân khẩu học (tuổi, nghề nghiệp, …) hay trả lời một số câu hỏi mà người dùng sẽ được tự động gán cho một trong những profile mẫu. Xuất phát từ profile này, hệ thống sẽ áp 25 dụng sự thích nghi cá nhân [21] nhằm cung cấp những tài nguyên phù hợp cho người dùng, và quá trình phản hồi thông tin đã có thể được bắt đầu để sau đó được dùng cho việc định vị. Nhìn chung, các phương pháp nêu trên đều yêu cầu người dùng phải tốn nhiều thời gian và công sức để được định vị vào một cộng đồng ban đầu theo tiêu chí đánh giá mà cũng chưa chắc đã thực sự phù hợp. Hiện nay, có một cách tiếp cận có thể khắc phục được vấn đề này. 2.3.3 Phương pháp suy diễn cộng đồng Phương pháp này dựa trên một mô hình cộng đồng đa tiêu chí (phần 2.2.2). Với U là tập người dùng, A là tập tiêu chí, một vector định vị của người dùng u, ký hiệu là Pu, là danh sách n cộng đồng của u trong các không gian tương ứng: Pu = [Gα] α  A, trong đó, Gα là những cộng đồng theo tiêu chí α mà u thuộc vào. Khi có một người dùng mới đăng ký, vector định vị của họ có thể không hoàn hảo, nghĩa là vẫn còn một số cộng đồng chưa xác định đặc biệt là cộng đồng theo tiêu chí đánh giá. Để có thể định vị người dùng mới vào trong cộng đồng theo tiêu chí đánh giá mà không cần họ phải cung cấp những thông tin phản hồi, phương pháp này sử dụng kỹ thuật quy nạp dựa trên luật. Nghĩa là dựa vào các tiêu chí đơn giản có sẵn trong profile (tuổi, nghề nghiệp, …) để suy diễn ra các giá trị còn thiếu trong vector định vị trong đó có giá trị đánh giá. Từ đó có thể định vị người dùng mới vào trong cộng đồng theo thiêu chuẩn đánh giá này. Phương pháp này đã phần nào làm giảm công sức của người dùng trong quá trình định vị và tạo nên sự đa dạng hóa về các thông tin tư vấn mà hệ thống cung cấp cho người dùng. Nó là một phương thức giao tiếp mới bên cạnh thông tin phản hồi. 2.3.4 Định vị dựa trên CP Khuyết điểm của 3 phương pháp trên là việc các cộng đồng được tạo ra giống như những hộp đen đối với người dùng [10]. Nghĩa là họ hoàn toàn không biết quá 26 trình thành lập cộng đồng dựa trên tiêu chí đánh giá được diễn ra như thế nào? Họ được hệ thống sắp xếp vào một cộng đồng nào đó vì lý do gì? Hiện nay, có một cách thức định vị mới có thể khắc phục được khuyết điểm này là dựa trên CP [9]. Trong các phần tiếp theo luận văn sẽ trình bày chi tiết hình thức định vị này, vì đây là trọng tâm của luận văn. CP là khái niệm dùng để chỉ những tài nguyên tiêu biểu nhất được dùng làm đặc trưng, mô tả tóm tắt một cộng đồng. Các tài nguyên này được trích ra theo một số tiêu chí nào đó từ tập các tài nguyên mà cộng đồng đã đánh giá. Vì CP mô tả nét đặc trưng của mỗi cộng đồng, nên nó có thể giúp cho người dùng hiểu và phân biệt một cách cơ bản các cộng đồng với nhau. Các tiêu chí cơ bản cho việc trích chọn tài nguyên làm đặc trưng trong hầu hết các hệ thống CF được trình bày dưới đây: Tính Phổ biến (Popularity) của tài nguyên: tiêu chí này thể hiện mức độ người dùng trong cộng đồng tham gia đánh giá tài nguyên. Số lượng người dùng tham gia đánh giá tài nguyên càng cao thì tính phổ biến càng cao. Giả sử cộng đồng có n người dùng khi đó tí