Luận văn Nghiên cứu xây dựng đặc trưng cộng đồng trong các hệ thống tư vấn thông tin

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ính phổ biến của tài nguyên thuộc đoạn [1, n], tính phổ biến nhỏ nhất khi chỉ có một người dùng đánh giá và lớn nhất khi được tất cả người dùng trong cộng đồng đánh giá. Chất lượng (AvgRating) của tài nguyên: tiêu chí này thể hiện điểm đánh giá trung bình của người dùng trong cộng đồng đã đánh giá tài nguyên. Điểm trung bình càng cao thì chất lượng càng tốt. Tiêu chí chất lượng có thang điểm trùng với thang điểm đánh giá tài nguyên của hệ thống. Tính Duy nhất (Uniqueness) của tài nguyên: tiêu chí này thể hiện mức độ trùng lắp các tài nguyên giữa các CP với nhau. Nếu sự trùng lắp càng lớn thì tính duy nhất càng thấp. Giả sử hệ thống có k cộng đồng và mỗi cộng đồng có m tài nguyên làm CP khi đó, tính duy nhất sẽ thuộc đoạn [k, mk], nghĩa là tính duy nhất nhỏ nhất bằng n khi tất cả các CP đều giống nhau và tính duy nhất lớn nhất bằng mk 27 khi tất cả các CP đều phân biệt với nhau. Tính duy nhất càng cao thì mức độ phân biệt giữa các CP trong hệ thống càng lớn. Trong phần tiếp theo, luận văn sẽ giới thiệu 3 phương pháp xây dựng CP được giới thiệu trong các nghiên cứu [9], đồng thời phân tích ưu, nhược điểm của chúng dựa trên 3 tiêu chí đã đề cập trên. Bài toán xây dựng CP: Với C = { Ci }: Ci là cộng đồng hay nhóm người sử dụng. I = { Ij }: Ij là tài nguyên (văn bản, phim, …) Với mỗi cộng đồng Ci  C, chúng ta cần tìm CPi - là những tài nguyên Ij  I được dùng làm đặc trưng cho Ci. 2.3.4.1 Phương pháp 1 - POP (Porpularly Rated) Đây là phương pháp dựa trên số lượng người dùng trong mỗi cộng đồng đã đánh giá các tài nguyên. Trong phương pháp này mỗi cộng đồng Ci  C sẽ được mô tả bởi n tài nguyên được nhiều người dùng trong cộng đồng đánh giá nhất. Thuật toán 1 Input: C : là tập k cộng đồng I : là tập m tài nguyên của hệ thống n : số lượng tài nguyên cần lấy cho mỗi CP Output: { CPk } : Tập đặc trưng cộng đồng của hệ thống Với mỗi Ci  C, (S1) Lấy tất cả tài nguyên Ij  I sao cho có ít nhất một người dùng trong Ci đã đánh giá Ij. Xếp hạng các Ij theo số người dùng trong Ci đã đánh giá. (S2) Lấy n tài nguyên có thứ hạng cao nhất làm CPi - đặc trưng của cộng 28 đồng Ci. (S3) Đánh dấu thứ tự các tài nguyên được chọn làm CPi. Tài nguyên thứ j được thêm vào là tài nguyên đặc trưng thứ j của cộng đồng Ci. Nhận xét: Ưu điểm của phương pháp POP là đơn giản, dễ cài đặt vì không tốn nhiều thời gian và công sức để tính toán số lượng người dùng tham gia đánh giá các tài nguyên, và hiệu quả trong trường hợp các hệ thống chỉ quan tâm đến tính phổ biến. Hơn nữa, phương pháp này cho ra CP có tính phổ biến rất cao (vì bản chất của phương pháp là dựa vào số lượng người sử dụng). Hạn chế của phương pháp POP là trong một số trường hợp, chất lượng của CP có thể không cao. Ví dụ, có thể xảy ra trường hợp một tài nguyên được nhiều người dùng đánh giá nhưng điểm trung bình đánh giá không cao, hoặc một tài nguyên nào đó mà đa số những người dùng đều rất ghét, vì thế họ cho điểm rất thấp. Hạn chế thứ hai của phương pháp này là CP có tính duy nhất thấp vì một tài nguyên được nhiều người dùng ở một cộng đồng quan tâm thì cũng có khả năng được nhiều người dùng ở cộng đồng khác quan tâm nên tài nguyên này có thể làm CP của nhiều cộng đồng dẫn đến mức độ trùng lắp các tài nguyên giữa các CP cao nghĩa là tính duy nhất thấp. 2.3.4.2 Phương pháp 2 – HR20 (High Ratings 20) Phương pháp HR20 dựa trên điểm đánh giá trung bình của tài nguyên. Phương pháp này sẽ chọn ra n tài nguyên có điểm trung bình đánh giá cao nhất và số lượng người dùng đánh giá không nhỏ hơn 20 để làm CP. Thuật toán 2: Input: C : là tập k cộng đồng I : là tập m tài nguyên của hệ thống n : số lượng tài nguyên cần lấy cho mỗi CP Output: {CPk } : tập đặc trưng cộng đồng của hệ thống 29 Với mỗi Ci  C, (S1) Lấy tất cả các tài nguyên Ij  I mà mỗi tài nguyên này có ít nhất 20 người sử dụng trong Ci đã đánh giá. Xếp hạng các tài nguyên này theo điểm đánh giá trung bình của Ci cho mỗi tài nguyên. (S2) Lấy n tài nguyên được xếp hạng cao nhất làm CPi - đặc trưng của cộng đồng Ci. (S3) Đánh dấu thứ tự các tài nguyên được chọn làm CP. Tài nguyên có thứ hạng j là tài nguyên đặc trưng thứ j của cộng đồng Ci. Nhận xét: Phương pháp HR20 hướng đến tiêu chí chất lượng, do đó nếu sử dụng phương pháp này sẽ cho ra CP có chất lượng rất cao. Tuy nhiên cũng như phương pháp POP, CP thu được từ phương pháp này có tính duy nhất không cao – vì khả năng trùng lắp tài nguyên nhiều. Về tính phổ biến thì với ngưỡng phổ biến 20, phương pháp này cho ra CP có tính phổ biến không quá thấp, tuy nhiên để CP có tính phổ biến cao hơn chúng ta có thể tăng ngưỡng phổ biến (>20), nhưng nếu ngưỡng phổ biến quá cao sẽ khiến cho chất lượng của CP giảm - vì những tài nguyên có điểm đánh giá trung bình cao nhưng số lượng người dùng tham gia đánh giá không vượt ngưỡng phổ biến bị loại bỏ, do đó làm giảm chất lượng của CP. 2.3.4.3 Phương pháp 3 – avgMatch Phương pháp này nhằm đạt được tính duy nhất tối đa và CP được xây dựng dựa trên điểm đánh giá trung bình của tài nguyên. Với mỗi tài nguyên Ij  I, cộng đồng Ci  C sẽ thêm Ij vào danh sách đặc trưng của nó nếu một trong hai điều kiện sau đây được thỏa:  Ij chưa được thêm vào bất kỳ cộng đồng nào khác và điểm trung bình của Ci đã đánh giá Ij là lớn nhất so với điểm trung bình của Ci đã đánh giá tất cả các tài nguyên khác nằm trong tập tài nguyên chưa được xét của Ci. 30  Ij đã được thêm vào cộng đồng Ck nhưng Ij thích hợp với Ci hơn Ck (điểm trung bình của Ci đã đánh giá Ij lớn hơn điểm trung bình của Ck đã đánh giá Ij). Thuật toán 3 Input: C : là tập k cộng đồng I : là tập m tài nguyên của hệ thống n : số lượng tài nguyên cần lấy cho mỗi CP Output: {CPk } : tập đặc trưng cộng đồng của hệ thống (S1) Đặt mỗi tài nguyên trong I là “chưa khớp”. (S2) Với mỗi cộng đồng Ci  C, xếp hạng tất cả tài nguyên trong I dựa trên điểm đánh giá trung bình của cộng đồng Ci cho tài nguyên đó. Giảm tuyến tính giá trị điểm trung bình đánh giá của Ci cho các tài nguyên có số lượng đánh giá nhỏ hơn 50. (S3) Trong khi còn tồn tại một tài nguyên “chưa khớp” trong I. Với mỗi cộng đồng Ci thuộc C, (S3.1) Trong khi Ci chưa tìm thấy một tài nguyên để thêm, Ci để xuất tài nguyên Ij có thứ hạng cao nhất và chưa được xét bởi Ci. (S3.1.1) Ij chấp nhận đề xuất của Ci nếu nó là “chưa khớp” hoặc nếu nó thích hợp với Ci hơn cộng đồng hiện tại nó được “khớp”. (S3.1.2) Nếu Ij chấp nhận đề xuất của Ci, đặt Ij là “khớp”, loại bỏ Ij ra khỏi bất kỳ cộng đồng nào trước đó mà Ij được “khớp” và thêm Ij vào Ci. (S3.2) Đánh dấu thứ tự các tài nguyên được thêm vào trong Ci. Tài nguyên thứ n được thêm vào trong Ci là tài nguyên điển hình nhất thứ n của Ci (S4) Mỗi Ci lấy ra n tài nguyên điển hình nhất. 31 Một cách trực quan, chúng ta tin tưởng 100 đánh giá với điểm trung bình là 4.5 hơn là chỉ có một đánh giá với điểm 5. Để mô hình hóa điều này avgMatch thực hiện việc giảm tuyến tính điểm trung bình cho những tài nguyên có điểm đánh giá nhỏ hơn 50 (xem ở bước S2). Những hệ thống khác nhau có thể chọn các ngưỡng khác với 50 hoặc các kỹ thuật giảm tuyến tính phù hợp với nó. Cụ thể, cách giảm tuyến tính điểm đánh giá trung bình của Ci như sau: Gọi Avg là điểm trung bình của nhóm Ci đã đánh giá tài nguyên Ij Num_ratings là số người sử dụng trong nhóm Ci đã đánh giá Ij Threshold là ngưỡng giảm tuyến tính. iF (num_ratings < threshold) then Avg = Avg * (num_ratings/threshold) End if Nhận xét: Phương pháp avgMatch được xây dựng nhằm khắc phục tình trạng trùng lắp tài nguyên giữa các CP trong hệ thống. Do đó, CP của mỗi cộng đồng là duy nhất, phân biệt giữa các cộng đồng với nhau. Hạn chế của phương pháp avgMatch là tính phổ biến của các tài nguyên được chọn làm CP có thể không cao. Vì phương pháp này dựa chủ yếu vào điểm trung bình đánh giá của tài nguyên nên có trường hợp một tài nguyên có chất lượng cao nhưng tính phổ biến lại thấp hơn so với những tài nguyên khác (ví dụ, một số lượng ít những người dùng trong cộng đồng rất thích tài nguyên này nên cho điểm rất cao). Hạn chế thứ hai của phương pháp avgMatch là trả về các tài nguyên được chọn làm CP có thể có chất lượng không cao. Mặc dù phương pháp này dựa vào điểm đánh giá trung bình của tài nguyên những vẫn có thể xảy ra trường hợp tài nguyên được chọn có chất lượng không cao so với những tài nguyên khác. Ví dụ, nếu hai cộng đồng C1 và C2 có điểm đánh giá trung bình tài nguyên Ij là bằng nhau, 32 cộng đồng nào xét Ij trước thì Ij sẽ được thêm vào CP của cộng đồng đó. Khi đó, cộng đồng còn lại sẽ phải xét những tài nguyên có chất lượng thấp hơn Ij. Nếu tình huống này xảy ra nhiều lần thì sẽ gặp phải vấn đề: CP của một cộng đồng có chất lượng rất cao, còn CP của cộng đồng khác có chất lượng rất thấp. Hạn chế cuối cùng của phương pháp avgMatch đó là CP của mỗi cộng đồng phụ thuộc vào thứ tự duyệt các cộng đồng. Nghĩa là, nếu thứ tự duyệt các cộng đồng Ci  C khác nhau thì có thể cho ra kết quả tập CP của hệ thống khác nhau. 2.4 Quan điểm xây dựng CP như giải bài toán ra quyết định đa tiêu chí Nhìn chung, các phương pháp POP, HR20, avgMatch đều hướng đến những tiêu chí riêng, có thể đáp ứng được bài toán xây dựng CP trong một số tình huống cụ thể :  Phương pháp POP áp dụng cho các hệ thống chỉ quan tâm đến tính phổ biến của CP.  Phương pháp HR20 đáp ứng các hệ thống quan tâm đến chất lượng CP, và  Phương pháp avgMatch dành cho các hệ thống muốn đạt được tính duy nhất tối đa. Tuy nhiên trong thực tế hiếm khi người ta chỉ quan tâm đến một tiêu chí mà thông thường người ta mong muốn có sự dung hòa nhiều tiêu chí khác nhau theo một cách thức nào đó và cho phép người xây dựng hệ thống ấn định mức độ quan trọng của từng tiêu chí. Với nhu cầu này thì phương pháp POP không thể đáp ứng được vì phương pháp này chỉ cho ra CP có tính phổ biến cao nhất, còn chất lượng cũng như tính duy nhất thì không thể kiểm soát được, trong một số trường hợp cho kết quả rất kém trên 2 tiêu chí này. Phương pháp HR20 hướng đến tiêu chí chất lượng CP, mặc dù có sử dụng ngưỡng 20 để tránh tình trạng tính phổ biến của CP quá thấp, tuy nhiên việc sử dụng ngưỡng 20 cố định khiến cho phương pháp này không được linh hoạt. Vì lẽ đó 33 trong [1] tác giả đã cải tiến HR20 thành HAR (High Average Rating) bằng cách dùng ngưỡng d thay cho 20. Khi đó, với ngưỡng d có thể thay đổi, người thiết kế hệ thống có thể điều khiển được tính phổ biến theo ý muốn, tuy nhiên sự kết hợp này cũng chưa phải là sự thỏa hiệp đúng nghĩa, hơn nữa HAR cũng chưa kiểm soát được tính duy nhất của CP. Phương pháp avgMatch hướng đến việc đạt được tính duy nhất tối đa, nghĩa là tập CP của hệ thống không có sự trùng lắp. Tuy nhiên không phải lúc nào hệ thống cũng mong muốn có độ duy nhất tối đa, trong trường hợp hệ thống mong muốn tính duy nhất chỉ đảm bảo ở một mức nào đó (chẳng hạn cho phép 50% tài nguyên trùng lắp) thì sao? Trong những tình huống này phương pháp avgMatch không đáp ứng được. Nói cách khác, phương pháp avgMatch chỉ cho tính duy nhất tối đa chứ không điều khiển được tính duy nhất theo ý muốn của người thiết kế hệ thống. Bên cạnh đó việc kết hợp hai tiêu chí tính phổ biến và chất lượng của tài nguyên bằng cách giảm tuyến tính điểm đánh giá trung bình, phần nào tăng tính hợp lý của việc xếp hạng tài nguyên, tuy nhiên đó cũng chưa phải là sự thỏa hiệp linh hoạt. Việc chọn ra các tài nguyên làm CP chưa nhất quán, còn phụ thuộc vào thứ tự duyệt của cộng đồng. Trong [1] tác giả cũng đã đề xuất một phương pháp cải tiến từ phương pháp avgMatch là freq_avgMatch. Phương pháp cải tiến này đã đưa ra một cách kết hợp 2 tiêu chí tính phổ biến và chất lượng của tài nguyên theo hướng xác suất thống kê nhằm cải thiện hai tiêu chí này nhưng đồng thời vẫn đảm bảo tính duy nhất tối đa. Ngoài ra phương pháp freq_avgMatch cũng đưa ra cách xử lý khuyết điểm tập CP của hệ thống phụ thuộc vào thứ tự duyệt cộng đồng. Phương pháp cải tiến này đã cho ra kết quả tốt hơn so với phương pháp avgMatch, tuy nhiên vẫn chưa cho phép điều khiển tính duy nhất theo ý muốn của người thiết kế hệ thống. Với nhu cầu tìm CP không phải đáp ứng một tiêu chí duy nhất mà thỏa mãn nhiều tiêu chí. Đặc biệt là những tiêu chí này xung đột với nhau, nghĩa là trong hầu hết các trường hợp tập CP của hệ thống không thể đạt được sự tối ưu ở cả 3 tiêu chí, 34 nếu như tính phổ biến tối ưu thì có chất lượng và tính duy nhất rất thấp, hoặc nếu có tính duy nhất tối ưu thì hai tiêu chí còn lại rất thấp. Điều này luôn dẫn đến một kết cục là tìm tập CP của hệ thống thỏa hiệp tốt nhất 3 tiêu chí trên và bài toán xây dựng CP mặc nhiên chính là bài toán đa tiêu chí. Chương 3 tiếp theo, luận văn sẽ giới thiệu bài toán đa tiêu chí cùng với các phương pháp hỗ trợ quyết định đa tiêu chí, đặc biệt là phương pháp PROMETHEE mà luận văn sẽ sử dụng để phát triển một phương pháp xây dựng CP mới.