Qua phân tích hiện trạng các phương pháp xây dựng CP hiện có, những ưu khuyết diểm, cũng như những nhu cầu thực tế mà những phương pháp này không thể đáp ứng, Luận văn đề xuất một phương pháp mới với mục tiêu thỏa hiệp được 3 tiêu chí tính phổ biến, chất lượng và tính duy nhất của CP một cách tự nhiên nhất -gần với suy nghĩ của con người. Hơn nữa, phương pháp mới này cũng cho phép ấn định trọng số của các tiêu chí - xác lập mức độ quan trọng tương đối giữa các tiêu chí với nhau - nhằm đáp ứng với các yêu cầu khác nhau của từng ngữ cảnh.
18 trang |
Chia sẻ: vietpd | Lượt xem: 1280 | Lượt tải: 0
Bạn đang xem nội dung tài liệu Xây dựng cp bằng phương pháp prometheematch, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
58
CHƯƠNG 4. XÂY DỰNG CP BẰNG PHƯƠNG PHÁP
PROMETHEEMATCH
4.1 Cách tiếp cận chính của PrometheeMatch
Qua phân tích hiện trạng các phương pháp xây dựng CP hiện có, những ưu
khuyết diểm, cũng như những nhu cầu thực tế mà những phương pháp này không
thể đáp ứng, Luận văn đề xuất một phương pháp mới với mục tiêu thỏa hiệp được 3
tiêu chí tính phổ biến, chất lượng và tính duy nhất của CP một cách tự nhiên nhất -
gần với suy nghĩ của con người. Hơn nữa, phương pháp mới này cũng cho phép ấn
định trọng số của các tiêu chí - xác lập mức độ quan trọng tương đối giữa các tiêu
chí với nhau - nhằm đáp ứng với các yêu cầu khác nhau của từng ngữ cảnh. Nói
cách khác, phương pháp mới này hướng đến việc cho ra CP thỏa hiệp tốt nhất các
tiêu chí theo những yêu cầu cụ thể của hệ thống, đồng thời có khả năng linh hoạt để
phù hợp với nhiều hệ thống khác nhau. Luận văn gọi phương pháp mới này là
PrometheeMatch xuất phát từ việc ứng dụng và cải tiến phương pháp
PROMETHEE II để giải quyết những vấn đề sau:
1. PrometheeMatch sử dụng phương pháp PROMETHEE II để xây dựng một tiền
thứ tự toàn phần các tài nguyên thuộc một cộng đồng dựa trên việc thỏa hiệp 2
tiêu chí tính phổ biến và chất lượng của tài nguyên. Lý do chọn phương pháp
này vì tính hiệu quả, có nền tảng toán học, dễ sử dụng, hơn nữa công cụ GAIA
đi kèm cho phép mô tả trực quan các tài nguyên cùng với mối liên hệ của chúng,
giúp người thiết kế hệ thống hiểu rõ hơn về kết quả tìm được. Ngoài ra, việc
chọn PROMETHEE II còn vì phương pháp này cho ra một tiền thứ tự toàn phần
trên tập tài nguyên mà cộng đồng quan tâm, từ đó những tài nguyên có thứ hạng
cao nhất sẽ được chọn làm CP.
2. PrometheeMatch sử dụng một ngưỡng trùng lắp u để giới hạn mức độ trùng lắp
tài nguyên giữa các CP, u được tính toán dựa trên trọng số của tiêu chí tính duy
nhất. Việc sử dụng ngưỡng trùng lắp nhằm cho phép các CP giữ lại những tài
59
nguyên được nhiều cộng đồng ưa thích nhưng vẫn đảm bảo sự khác biệt tương
đối giữa các CP với nhau, giúp người dùng không phải bối rối khi chọn cộng
đồng để tham gia.
3. PrometheeMatch cũng giải quyết vấn đề phụ thuộc thứ tự duyệt cộng đồng trong
quá trình chọn tài nguyên làm CP. Khi có tài nguyên I được nhiều cộng đồng ưa
thích và năng lực của tài nguyên này trên các cộng đồng là bằng nhau, và giả sử
I chỉ có thể thuộc về một CP duy nhất (để thỏa ngưỡng trùng lắp), vậy tài
nguyên này sẽ được thuộc về CP nào? Nếu không thiết lập quyền ưu tiên cho
cộng đồng thì điều này sẽ phụ thuộc vào thứ tự duyệt của cộng đồng, cộng đồng
nào xem xét (tiếp xúc) tài nguyên I trước thì I sẽ thuộc về CP của cộng đồng đó.
Phương pháp cải tiến sẽ bổ sung quyền ưu tiên cho mỗi cộng đồng, để khi xảy ra
sự tranh chấp này, cộng đồng nào có độ ưu tiên cao hơn thì giành quyền giữ tài
nguyên I trong CP của nó.
Phần tiếp theo luận văn trình bày chi tiết từng vấn đề.
4.2 Những cải tiến của PrometheeMatch
Bài toán xây dựng CP có thể được phát biểu theo hình thức bài toán MCDM
với 2 tiêu chí tính phổ biến và chất lượng của tài nguyên, còn tiêu chí tính duy nhất
xem như điều kiện ràng buộc trên tập CP của hệ thống. Tuy vậy trọng số vẫn được
áp dụng cho cả 3 tiêu chí, trong đó wp, wa, wu [0,1] và wp + wa = 1.
I
Popularity AvgRating Uniqueness
wp wa wu
I1
I2 . . .
Ii . . .
In
Pop(I1)
Pop(I2) . . .
Pop(Ii) . . .
Pop(In)
Avg(I1)
Avg(I2) . . .
Avg(Ii) . . .
Avg(In)
u = (1 – wu) kn
u: ngưỡng trùng lắp
k : số cộng đồng
n: số tài nguyên của mỗi CP
Hình 4.1 Dữ liệu bài toán xây dựng CP theo MCDM
60
Trong đó:
Ii I : các giải pháp (hành động) - là tập các tài nguyên mà cộng đồng
quan tâm.
Popularity và AvgRating : 2 tiêu chí tương ứng với tính phổ biến và chất
lượng của tài nguyên.
wp, wa : trọng số tương ứng với 2 tiêu chí Popularity và AvgRating. wp +
wa [0,1] và wp + wa = 1
Uniqueness: tiêu chí tính duy nhât của CP được phát biểu dưới hình thức
điều kiện ràng buộc của CP như sau:
Tập CP của hệ thống phải đảm bảo độ trùng lắp tài nguyên không lớn
hơn ngưỡng u yêu cầu.
Với k là số cộng đồng, n là số phần tử trong mỗi CP, wu là trọng số của
tiêu chí tính duy nhất wu [0,1]. Công thức để tính u như sau:
u = (1 – wu) kn (4.1)
Đầu tiên, phương pháp PrometheeMatch xác lập các trọng số wp, wa, wu, và
tham số u được tính từ wu, sau đó để tìm CP cho mỗi cộng đồng, PrometheeMatch
tiến hành 2 giai đoạn:
1. Sử dụng phương pháp PROMETHEE II để xếp hạng các tài nguyên trong
mỗi cộng đồng theo 2 tiêu chí Popularity và AvgRating
2. Sau đó, trên mỗi cộng đồng, lấy ra n tài nguyên có thứ hạng cao nhất làm
CP sao độ trùng lắp của các CP không vượt quá ngưỡng u.
61
4.2.1 Cải tiến 1 – Sử dụng PROMETHEE II để xếp hạng các tài nguyên trong cộng
đồng
Có nhiều phương pháp MCDA để thỏa hiệp 2 tiêu chí Popularity và
AvgRating nhưng Luận văn chọn phương pháp PROMETHEE II để xếp hạng các
tài nguyên trong cộng đồng theo 2 tiêu chí này vì những lý do sau đây [3]:
Hai tiêu chí Ppularity và AvgRating sử dụng hai thang điểm đánh giá khác
nhau. Ví dụ, trong MovieLens, AvgRating có thang điểm [1, 5] còn
Popularity có thang điểm [1, num_user], với num_user là số người dùng
trong cộng đồng.
Điểm của hai tiêu chí này không thể bù trừ cho nhau, việc mất điểm trên
tiêu chí này không thể bù đắp bằng việc có điểm trên tiêu chí khác.
Vì điểm đánh giá của tiêu chí avgRating là số thập phân nên hai điểm đánh
giá có độ chênh lệch không đáng kể có thể xem là bằng nhau. Cũng như
thang điểm đánh giá của popularity lớn nên độ chênh lệch giữa hai điểm
đánh giá nhỏ cũng không thể nói là có sự tốt hơn của một trong hai tài
nguyên. Do đó có thể sử dụng ngưỡng phân biệt (ngưỡng lớn hơn và
ngưỡng bằng nhau) trong cấu trúc so sánh.
Phương pháp PROMETHEE II rõ ràng, dễ hiểu, hơn nữa có nền tảng toán
học, cùng với công cụ GAIA đi kèm sẽ cho phép mô tả trực quan kết quả,
giúp người thiết kế hệ thống hiểu rõ hơn về kết quả tìm được.
PROMETHEE II cho ra kết quả là thứ tự toàn phần, đã loại bỏ quan hệ
không thể so sánh mặc dù cách loại bỏ này không phải lúc nào cũng thuyết
phục. Nhưng vì cách tiếp cận của luận văn là chọn n tài nguyên có thứ hạng
cao nhất làm CP, do đó một thứ tự toàn phần các tài nguyên là cần thiết, vì
vậy luận văn chọn thuật toán PROMETHEE II để áp dụng.
Sau đây luận văn trình bày một ví dụ về ứng dụng PROMETHEE II để xếp
hạng các tài nguyên trong một cộng đồng, tài nguyên ở đây là các phim.
62
Ví dụ 4.1:
Giả sử trong ứng dụng tư vấn phim, ta có một cộng đồng gồm 21 người dùng
thực hiện việc đánh giá trên 5 phim và thang điểm đánh giá từ 1 đến 5 như bảng 4.1:
C1
movie Popularity AvgRating
m1 11 4.9
m2 21 4.8
m3 20 4.5
m4 19 4.3
m5 18 4.0
Bảng 4.1 Bảng đánh giá của cộng đồng C1
Luận văn sẽ xem xét cách xếp hạng các tài nguyên theo kỹ thuật giảm tuyến
tính điểm trung bình đánh giá (AvgRating) dựa trên ngưỡng phổ biến (Popularity)
đã được áp dụng trong phương pháp avgMatch, khi đó với ngưỡng giảm tuyến tính
là 50% số người dùng trong cộng đồng thì tất cả điểm AvgRating đều không thay
đổi, vì tất cả các phim đều có Popularity lớn hơn ngưỡng giảm tuyến tính (10.5)
(xem chi tiết thuật toán ở phần 2.3.4.3). Và như vậy thứ tự các phim xét theo điểm
AvgRating sẽ là:
m1 > m2 > m3 > m4 > m5
Thứ tự trên cho thấy phim m1 và m2 có điểm AvgRating gần bằng nhau, trong
khi phim m2 có điểm Popularity gần như gấp đôi phim m1. Nhưng phim m1 vẫn xếp
thứ hạng cao hơn, vì theo kỹ thuật giảm tuyến tính thì một khi đã thỏa ngưỡng
Popularity rồi thì chỉ còn xét điểm AvgRating. Kết quả này không được tự nhiên
lắm (không gần với cách hành xử của con người), do đó một phương pháp thỏa hiệp
2 tiêu chí trên một cách hợp lý hơn nên được xem xét.
Sau đây, luận văn xem xét việc xếp hạng các tài nguyên bằng phương pháp
PROMETHEE II. Các tham số được sử dụng cho PROMETHEE II như trong bảng
4.2:
63
Popularity AvgRating
wk 0.5 0.5
qk 0 0
pk 20 4
Bảng 4.2: Tham số PROMETHEE II Cho ví dụ 4.1
Vì tổng số người dùng trong C1 là 21, và mỗi phim có ít nhất một người dùng
đánh giá nên khoảng cách tối đa giữa hai giá trị trên tiêu chí Popularity là 20
(p1 = 20) và khoảng cách tối thiểu giữa hai giá trị trên tiêu chí này là 0 (q1 = 0). Các
phim được đánh giá theo thang điểm từ 1 đến 5 nên độ lệch tối đa giữa 2 giá trị trên
tiêu chí AvgRating là 4 (p2 = 4) và độ lệch tối thiểu của 2 giá trị trên tiêu chí này là
0 (q2 = 0).
Ở đây luận văn chọn hàm thích hơn kiểu 5 (Hình 4.2) vì mong muốn phân biệt
mức độ thích hơn khác nhau của các tài nguyên theo điểm Popularity và điểm
AvgRating (tùy theo mục đích cụ thể mà chúng ta có thể chọn các kiểu hàm thích
hơn khác)
Hình 4.2 Hàm thích hơn kiểu 5
Tính chỉ số thích hơn và các dòng hơn cấp như bảng 4.3
m1 m2 m3 m4 m5
m1 - 0.025 0.1 0.15 0.225 0.50 -1.20
m2 0.5 - 0.125 0.225 0.35 1.20 1.18
m3 0.45 0 - 0.1 0.225 0.78 0.55
m4 0.4 0 0 - 0.125 0.53 0.05
m5 0.35 0 0 0 - 0.35 -0.58
1.7 0.025 0.225 0.475 0.925
Bảng 4.3: Chỉ số thích hơn và các dòng hơn cấp của Ví dụ 4.1
64
Trong đó:
(m1, m2) = 0.5 * 0 + 0.5 * (4.9 – 4.8)/4 = 0.025
(m2, m1) = 0.5 * (21 – 11)/20 + 0.5 * 0 = 0.5
+(m1) = 0.025 + 0.1 + 0.15 + 0.225 = 0.5
(m1) = 0.5 + 0.45 + 0.4 + 0.35 = 1.7
(m1) = +(m1) – (m1) = 0.5 – 1.7 = -1.2
Dựa vào kết quả dòng hơn cấp thực (.) trong Bảng 4.3, phương pháp
PROMETHEE II cho ta tiền thứ tự toàn phần cuối cùng của các phim:
m2 > m3 > m4 > m5 > m1
So sánh với kết quả phương pháp avgMatch ta thấy rõ ràng sự thỏa hiệp các
tiêu chí của PROMETHEE II cho ta kết quả hợp lý và tự nhiên hơn nhiều. Bằng
chứng của sự thỏa hiệp là mặc dầu m1 có điểm đánh giá trung bình cao nhất nhưng
vì số người tham gia đánh giá thấp hơn nhiều so với các tài nguyên khác nên có thứ
hạng thấp nhất, điều này cũng gần với cách mà con người vẫn thường đánh giá.
4.2.2 Cải tiến 2 – Sử dụng ngưỡng trùng lắp
Ngưỡng trùng lắp u cho phép giới hạn sự trùng lắp tài nguyên giữa các CP và
được tính theo công thức (4.1).
Sau khi áp dụng PROMETHEE II để xếp hạng tài nguyên trên mỗi cộng đồng
ta thu được tập thứ tự {<i } trên tập cộng đồng {Ci }. Để chọn ra tập {CPi} không vi
phạm ngưỡng trùng lắp u, ta làm như sau:
Trên mỗi cộng đồng chúng ta lần lượt chọn tài nguyên có thứ hạng cao nhất và
chưa được xét bởi cộng đồng đó để đưa vào CP. Mỗi lần chọn, thực hiện kiểm tra
tình trạng vi phạm ngưỡng trùng lắp, nếu sự vi phạm xảy ra - nghĩa là số lượng tài
nguyên trùng lắp trong các CP vượt ngưỡng u cho phép - thực hiện việc xếp hạng
tất cả các tài nguyên trùng lắp và loại bỏ tài nguyên trùng lắp có thứ hạng thấp nhất
65
ra khỏi CP chứa nó. Thủ tục này lặp lại cho đến khi tât cả CP đều có đủ n tài
nguyên. (Xem thuật giải và sơ đồ ở phần 4.3)
Việc xếp hạng các tài nguyên trùng lắp cũng được thực hiện bằng phương
pháp PROMETHEE II với cùng tham số như khi xếp hạng các tài nguyên trong một
cộng đồng.
Sau đây luận văn sẽ trình bày một ví dụ về cách chọn tài nguyên làm CP thỏa
ngưỡng trùng lắp u.
Ví dụ 4.2:
Giả sử ta có 3 cộng đồng (k = 3) C1, C2, C3. Mỗi cộng đồng có tối đa 21 người
dùng, mỗi người dùng tham gia đánh giá ít nhất một phim, như bảng sau:
C1 C2
movie Popularity AvgRating movie Popularity AvgRating
m1 10 4.5 m5 10 4
m3 9 4 m1 9 3.8
m4 8 3.5 m7 8 3.5
m5 7 3 m6 7 3
m2 6 2 m10 6 2
C3
movie Popularity AvgRating
m1 10 4
m4 9 3.7
m5 8 3.5
m8 7 3
m6 6 2
Hình 4.3: Dữ liệu đánh giá của 3 cộng đồng - ví dụ 4.2
Áp dụng phương pháp PROMETHEE II để xếp hạng các tài nguyên trong mỗi
cộng đồng với các tham số như Bảng 4.4. Kết quả ta có thứ hạng các tài nguyên
trong mỗi cộng đồng (Bảng 4.5).
66
Popularity AvgRating
wk 0.5 0.5
pk 20 4
Bảng 4.4: Tham số của PROMETHEE II – ví dụ 4.2
Stt C1 C2 C3
1 m1 m5 m1
2 m3 m1 m4
3 m4 m7 m5
4 m5 m6 m8
5 m2 m10 m6
Bảng 4.5: Thứ tự tài nguyên trong 3 cộng đồng - ví dụ 4.2
Để chọn trên mỗi cộng đồng 3 tài nguyên (n = 3) làm CP và các CP không vi
phạm ngưỡng trùng lắp u = 3 (kết quả như Bảng 4.6).
Stt C1 C2 C3
1 m1 m5 m1
2 m3 m1 m4
3 m4 m7 m5
4 m5 m8
5 m2
Bảng 4.6: CP của 3 cộng đồng với u = 3 trong ví dụ 4.2
Luận văn thực hiện như sau:
Đầu tiên xét C1, chọn 3 tài nguyên m1, m3, m4 vào CP1.
Xét C2, chọn 3 tài nguyên m5, m1, m7 vào CP2. Lúc này có 2 tài nguyên
trùng lắp là {(m1, C1), (m1, C2)}, số tài nguyên trùng lắp là 2 < u, chưa vi
phạm ngưỡng trùng lắp.
Xét tiếp C3, chọn m1 vào CP3, các tài nguyên trùng lắp bao gồm {(m1, C1),
(m1, C2), (m1, C3)}, số tài nguyên trùng lắp lúc này là 3 = u nên vẫn chưa vi
phạm ngưỡng trùng lắp.
67
Tiếp tục chọn m4 vào CP3, các tài nguyên trùng lắp bao gồm {(m1, C1),
(m1, C2), (m1, C3), (m4, C1), (m4, C3)} số tài nguyên trùng lắp là 5 > u. Như
vậy sự vi phạm ngưỡng trùng lắp đã xảy ra.
Xếp hạng các tài nguyên trùng lắp bằng phương pháp PROMETHEE II
cho ra tiền thứ tự sau:
(m1, C1) > (m1, C2) > (m1, C3) > (m4, C3) > (m4, C1).
Loại tài nguyên có thứ hạng thấp nhất là (m4, C1) ra khỏi C1 và như vậy
số tài nguyên trùng lắp giảm xuống còn 3 không vi phạm ngưỡng.
Ở C1, chọn m5 vào CP1 thay thế cho tài nguyên m4 đã bị loại, và cứ thế
tiếp tục cho đến khi mỗi cộng đồng có đủ 3 tài nguyên trong CP.
Kết quả cuối cùng như bảng sau:
CP1 m1 >1 m3 >1 m2
CP2 m5 >2 m1 >2 m7
CP3 m1 >3 m4 >3 m8
Bảng 4.7: Kết quả CP của 3 cộng đồng thỏa ngưỡng trùng lắp-Ví dụ 4.2
Nhờ sử dụng ngưỡng trùng lắp u, 3 cộng đồng giữ được phim m1 – có thứ
hạng rất cao trong cả 3 cộng đồng – trong CP của chúng, đồng thời vẫn đảm bảo sự
phân biệt tương đối giữa 3 CP với nhau. Ngoài ra, việc giữ lại những tài nguyên có
thứ hạng cao cũng làm tăng năng lực của các CP – năng lực CP chính là năng lực
trung bình của các tài nguyên trong CP.
4.2.3 Cải tiến 3 – Giảm sự phụ thuộc vào thứ tự duyệt cộng đồng
Trong quá trình chọn tài nguyên làm CP thỏa mãn ngưỡng trùng lắp u, khi số
tài nguyên trùng lắp vượt quá ngưỡng u, PromeetheeMatch sẽ thực hiện công việc
loại bỏ tài nguyên trùng lắp có năng lực thấp nhất ra khỏi CP của nó để giảm mức
độ trùng lắp. Nhưng nếu có nhiều hơn 2 tài nguyên trùng lắp có năng lực thấp nhất
thì sẽ loại tài nguyên nào? Xem xét ví dụ dưới đây:
68
Ví dụ 4.3: có 3 cộng đồng như hình 4.4:
C2
movie Popularity AvgRating
m5 10 4
m8 8 3.5
m7 8 3.5
m6 6 3
C1 C3
movie Popularity AvgRating movie Popularity AvgRating
m10 10 4.5 m6 10 4
m3 8 4 m9 8 3.7
m4 8 3.5 m4 8 3.5
m1 6 3 m5 6 3
Hình 4.4: Dữ liệu đánh giá của 3 cộng đồng - ví dụ 4.3
Áp dụng phương pháp PROMETHEE II để xếp hạng các tài nguyên trong mỗi
cộng đồng ta có kết quả thứ tự các tài nguyên như bảng 4.8 (luận văn cố tình chọn
dữ liệu có thứ tự định sẵn trên 2 tiêu chí nhằm đơn giản việc xếp hạng tài nguyên và
làm nổi bật việc phụ thuộc vào thứ tự duyệt cộng đồng khi chọn CP).
Stt C1 C2 C3
1 m10 m5 m6
2 m3 m8 m9
3 m4 m7 m4
4 m1 m6 m5
Bảng 4.8: Thứ tự tài nguyên trên mỗi cộng đồng cho ví dụ 4.3
Giả sử chọn trên mỗi cộng đồng 3 tài nguyên để làm CP thỏa ngưỡng trùng lắp
u = 0 (nghĩa là các CP không có tài nguyên nào trùng lắp).
Khi đó xét các tài nguyên trong cộng đồng theo thứ hạng từ trên xuống thì C1
và C3 đều chọn m4 làm CP của chúng, nhưng vì để đảm bảo ngưỡng trùng lắp u=0
nên m4 chỉ có thể thuộc về một CP. PrometheeMatch sẽ tiến hành xếp hạng (m4,C1)
69
và (m4,C3) để loại tài nguyên có năng lực thấp hơn ra khỏi CP nhưng vì (m4,C1) và
(m4,C3) có năng lực bằng nhau (xét theo dữ liệu bảng đánh giá), do đó trong trường
hợp này, nếu không xét độ ưu tiên cho cộng đồng thì mặc nhiên cộng nào duyệt m4
trước (nghĩa là cộng đồng nào xem xét m4 trước) sẽ được ưu tiên giữ m4 trong CP
của nó, và kết quả như trong bảng 4.9 và 4.10:
CP1 m10 >1 m3 >1 m4
CP2 m5 >2 m8 >2 m7
CP3 m6 >3 m9 >3 m2
Bảng 4.9: CP của 3 cộng đồng theo thứ tự duyệt C1, C2, C3 của ví dụ 4.3
CP1 m10 >1 m3>1 m1
CP2 m5 >2 m8 >2 m7
CP3 m6 >3 m9 >1 m4
Bảng 4.10 CP của 3 cộng đồng theo thứ tự duyệt C3, C2, C1 của ví dụ 4.3
Kết quả trên cho thấy nếu duyệt cộng đồng theo thứ tự C1, C2, C3. Khi đó m4
thuộc về CP1, và nếu duyệt theo thứ tự ngược lại C3, C2, C1 khi đó m4 thuộc về CP3.
Điều này dẫn đến kết quả không nhất quán, phụ thuộc vào thứ tự duyệt cộng đồng.
Để cho ra kết quả nhất quán, luận văn đề xuất độ ưu tiên cho mỗi cộng đồng.
Độ ưu tiên này nhằm giảm độ chênh lệch năng lực giữa các CP. Ví dụ, nếu CP1 có
năng lực cao hơn CP2 và 2 cộng đồng C1, C2 cùng tranh chấp một tài nguyên m, nếu
cho m thuộc về CP1 khi đó C2 phải đi tìm một tài nguyên có năng lực kém hơn m để
đưa vào CP2, khi đó năng lực của CP1 càng lớn hơn CP2. Do đó độ ưu tiên đưa ra
nhằm cho phép m thuộc về CP2 (CP có năng lực yêu hơn) và khi đó độ chênh lệch
năng lực của CP1 và CP2 sẽ giảm xuống.
Trên tinh thần đó, Luận văn định nghĩa độ ưu tiên của cộng đồng như sau:
Độ ưu tiên của cộng đồng Ci đối với tài nguyên mj ký hiệu là P(Ci,mj) và cũng
được đánh giá dựa trên 2 tiêu chí Popularity và AvgRating, giá trị của P(Ci, mj) tại
các tiêu chí này được xác định bằng nghịch đảo của 2 giá trị Popularity trung bình
và AvgRating trung bình của tất cả tài nguyên thuộc Ci và có thứ hạng lớn hơn mj.
70
Sau đây, luận văn sẽ trình bày minh họa cách tính độ ưu tiên của 2 cộng đồng
C1 và C3 đối với tài nguyên m4 ở ví dụ 4.3
Gọi P(m4, C1) và P(m4, C3) là độ ưu tiên của C1 và C3 trên tài nguyên m4, ta có
bảng dữ liệu quyền ưu tiên như sau:
Trong đó:
Popularity của P(m4, C1) = 1/ [(popularity(m10) + popularity(m3))/2]
= 1/ [(10 + 8)/2] = 1/9 = 0.11
Popularity của P(m4, C3) = 1/ [(popularity(m6) + popularity(m9))/2]
= 1 / [(10 + 8)/2] = 1/9 = 0.11
AvgRating của P(m4, C1) = 1 / [(4.5 + 4)/2] = 1/4.25 = 0.24
AvgRating của P(m4, C3) = 1 / [(4 + 3.7)/2] = 1/3.85 = 0.25
Để biết độ ưu tiên nào lớn hơn ta thực hiện việc xếp hạng các độ ưu tiên này
theo 2 tiêu chí Popularity và AvgRating bằng PROMETHEE II với cùng tham số
với xếp hạng tài nguyên trong cộng đồng. Kết quả là:
P(m4, C3) > P(m4, C1)
Điều này có nghĩa là C3 được quyền giữ m4 trong CP3 và C1 phải loại m4 ra
khỏi CP1. Và kết quả tập CP cuối cùng
CP1 m10 >1 m3 >1 m1
CP2 m5 >2 m8 >2 m7
CP3 m6 >3 m9 >1 m4
Độ ưu tiên mà luận văn đề xuất đã giải quyết được vấn đề phụ thuộc thứ tự
duyệt cộng đồng nhưng vẫn còn hạn chế trong trường hợp độ ưu tiên của 2 cộng
đồng cũng bằng nhau luôn thì sao? Khi đó thuật toán vẫn lưỡng lự trong việc chọn
tài nguyên nào để loại bỏ. Dĩ nhiên có thể đưa thêm nhiều độ ưu tiên khác bổ sung,
Popularity AvgRating
P(m4, C1) 0.11 0.24
P(m4, C3) 0.11 0.25
71
nhưng cho dù có thêm bao nhiêu độ ưu tiên thì vấn đề 3 về mặt lý thuyết vẫn không
thể giải quyết triệt để được. Cho nên quan điểm của luận văn là sử dụng quyền ưu
tiên ở mức thực tế nhất, vì hiếm khi có trường hợp một tài nguyên được 2 cộng
đồng thích bằng nhau và quyền ưu tiên của 2 cộng đồng cũng bằng nhau.
Với độ ưu tiên đề xuất này phương pháp PrometheeMatch đã góp phần tăng
tính nhất quán của CP tìm được.
4.3 Thuật toán và sơ đồ khối
Phần này luận văn trình bày phương pháp PrometheeMatch hoàn chỉnh dưới
dạng thuật toán và sơ đồ khối.
Thuật toán:
Input: Cho C = {Ci}, Ci là cộng đồng hay nhóm người sử dụng
I = {Ij} là tập tài nguyên hệ thống
n : số tài nguyên làm CP
wp, wa, wu : trọng số của 3 tiêu chí Popularity và avgRating và
Uniqueness
Kiểu hàm thích hơn và các tham số đi kèm của PROMETHEE II
Output: { CPi } danh sách tập đặc trưng của các cộng đồng
(S1) Với mỗi cộng đồng Ci C, xếp hạng tất cả tài nguyên trong I mà Ci đã
đánh giá theo 2 tiêu chí popularity và avgRating bằng phương pháp
PROMETHEE II.
(S2) Với mỗi cộng đồn