Hướng tiếp cận giải bài toán đa mục tiêu trong điều kiện thay đổi

94<br /> <br /> Nguyễn Văn Hiệu<br /> <br /> HƯỚNG TIẾP CẬN GIẢI BÀI TOÁN ĐA MỤC TIÊU TRONG ĐIỀU KIỆN<br /> THAY ĐỔI<br /> THE APPROACH OF SOLVING MULTIPLE CRITICAL DECISION MAKING PROBLEMS<br /> IN CHANGING CONDITIONS<br /> Nguyễn Văn Hiệu<br /> Trường Đại học Bách khoa, Đại học Đà Nẵng; nvhieuqt@dut.udn.vn<br /> Tóm tắt - Các hệ thống hỗ trợ ra quyết định đóng vai trò rất lớn<br /> trong việc giải quyết các vấn đề phức tạp có cấu trúc hoặc phi cấu<br /> trúc. Một hướng đi khác của hệ hỗ trợ ra quyết định là hệ thống gợi<br /> ý (RS) được sử dụng cho những vấn đề đơn giản hơn nhưng đòi<br /> hỏi tốc độ ra quyết định nhanh. Bài báo trình bày phương pháp ra<br /> quyết định đa mục tiêu trên cơ sở phương pháp Smart-Swaps (SS)<br /> và đề xuất phương pháp cải biên Smart-Swaps 2 (SS2) để từ đó<br /> định hướng xây dựng hệ thống gợi ý. Ngoài ra bài báo cũng đề<br /> xuất mô hình giải bài toán ra quyết định đa mục tiêu chấp nhận rủi<br /> ro với điều kiện thay đổi, để từ đó chỉ ra hướng tiềm năng áp dụng<br /> phương pháp đã đề xuất vào hệ thống gợi ý theo ngữ cảnh.<br /> <br /> Abstract - Decision Support System (DSS) is taking a big role in<br /> solving complicated structured and unstructured problems.<br /> Another approach of DSS is Recommender Systems (RS), which<br /> are implemented to solve simpler problems which require a high<br /> speed of making the decision. This paper covers the following<br /> topics: (i) presenting a method of solving multiple critical decision<br /> problems namely Smart-Swaps (SS), (ii) proposing the SmartSwaps 2 (SS2) method based on SS with the main goal of taking<br /> the advantages of SS to build RS, (iii) proposing a method of<br /> solving decision-making problems with acceptable risk under<br /> changing conditions to point out the potential approach of applying<br /> the proposed method to Context-aware Recommender System<br /> (CRS).<br /> <br /> Từ khóa - tiến trình PrOACT; phương pháp Even Swap; phương<br /> pháp Smart-Swaps; phương pháp Smart Choices; hệ thống gợi ý<br /> theo ngữ cảnh<br /> <br /> Key words - PrOACT process; Even Swap method; Smart-Swaps<br /> method; Smart Choices method; Context-aware Recommender<br /> System (CRS)<br /> <br /> 1. Đặt vấn đề<br /> Trong những năm gần đây hệ thống gợi ý<br /> (Recommender System) phát triển mạnh do sự phát triển<br /> vượt bậc của trí tuệ nhân tạo và học máy. Hệ thống gợi ý<br /> bán hàng nổi tiếng như của Amazon, hay hệ thống gợi ý<br /> phim của Netflix là những ví dụ điển hình trong việc áp<br /> dụng hệ thống gợi ý vào thực tế. Các hướng tiếp cận trong<br /> việc xây dựng hệ thống gợi ý thông thường là sử dụng lọc<br /> cộng tác [6], lọc dựa trên nội dung [7], lọc hỗn hợp [8].<br /> Một hướng tiếp cận khác của hệ thống gợi ý là hệ thống gợi<br /> ý đa tiêu chí [9], đây là sự ứng dụng cơ sở lý thuyết của các<br /> hệ thống ra quyết định đa mục tiêu định hướng hệ thống<br /> gợi ý. Phương pháp Smart-Swaps [2] có những tính chất<br /> phù hợp trong việc xây dựng hệ thống ra quyết định định<br /> hướng hệ thống gợi ý, đặc biệt là tính chất không phải xác<br /> định độ quan trọng cho từng tiêu chí và khả năng “học”<br /> người ra quyết định. Bài báo đề xuất xây dựng phương<br /> pháp Smart Swaps 2 dựa trên SS nhằm kế thừa những ưu<br /> viết của SS vào hệ thống gợi ý.<br /> <br /> rút gọn tập phương án trên bảng Tradeoff.<br /> <br /> 2. Cơ sở lý thuyết<br /> 2.1. Phương pháp Smart-Swaps<br /> Phương pháp Smart-Swaps được xây dựng trên cơ sở<br /> phương pháp học là phương pháp Smart Choices [1] dựa<br /> trên cơ sở áp dụng kỹ thuật Even Swap [3, 4, 5] (ES) vào<br /> quy trình PrOACT [1] để giải quyết bài toán ra quyết định<br /> đa mục tiêu.<br /> 2.1.1. Quy trình PrOACT<br /> PrOACT<br /> (Problem,<br /> Objectives,<br /> Alternatives,<br /> Consequences, Tradeoff) được sử dụng để mô hình hóa bài<br /> toán thực thế theo cấu trúc mối quan hệ tương ứng giữa các<br /> tiêu chí và các phương án. Kỹ thuật ES được áp dụng để<br /> <br /> Hình 1. Quá trình giải quyết bài toán với Smart-Swaps<br /> <br /> Trong mỗi bước thực thi kỹ thuật ES, ứng với tập<br /> phương án ta có thể phân hoạch tập phương án thành 2 tập:<br /> tập phương án ưu thế và tập phương án mất ưu thế. Ứng<br /> <br /> ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG, SỐ 3(112).2017-Quyển 1<br /> <br /> với tập tiêu chí cũng được phân hoạnh thành: tập tiêu chí<br /> vô ích và tập tiêu chí có ích. Kết thúc mỗi lượt áp dụng kỹ<br /> thuật ES, các phương án trong tập phương án ưu thế được<br /> giữ lại.<br /> Quá trình giải quyết bài toán đa mục tiêu với Smart-Swaps<br /> là một vòng lặp áp dụng ES được thể hiện trong hình 1.<br /> Ánh xạ mô hình bài toán lên ma trận đại số, gọi m là số<br /> phương án, n là số tiêu chí, ta có ma trận hệ quả tương ứng<br /> của phương án thứ x trên tiêu chí thứ i được xác định bởi<br /> P ∶ O A → P , trong đó A =<br /> ,<br /> , …,<br /> là tập<br /> phương án, O =<br /> , ,…,<br /> là tập tiêu chí.<br /> Từ đây, giá trị phương án<br /> được xác định bởi hàm<br /> f(x):<br /> ( ) = <br /> <br /> ( , ∈<br /> <br /> (P ).<br /> <br /> 95<br /> <br /> (<br /> <br /> )<br /> <br /> (P ) = <br /> (P ) = <br /> <br /> 1<br /> 1<br /> <br /> ( )<br /> <br /> (<br /> <br /> ( )<br /> <br /> )<br /> <br /> (5)<br /> 1<br /> <br /> 1<br /> <br /> (6)<br /> <br /> ) (1)<br /> <br /> Trong đó wi là trọng số thể hiện mức độ quan trọng của<br /> tiêu chí , (P ) là giá trị hệ quả P được chuẩn hóa và<br /> được tính bởi công thức:<br /> (P ) =<br /> <br /> P<br /> <br /> min P<br /> <br /> max P<br /> <br /> P<br /> <br /> ớ ∈ 1, 2, . . . ,<br /> <br /> Giá trị tổng ở công thức (1) sẽ được Smart-Swaps sử<br /> dụng làm căn cứ để so sánh hai phương án, tuy nhiên wi là<br /> chưa biết. Như mục tiêu của phương pháp là người ra quyết<br /> định không phải xác định mức độ quan trọng của từng tiêu<br /> chí, vì thế công thức (1) chưa áp dụng ngay được. Thay vì<br /> sử dụng giá trị xác định, Smart-Swaps sử dụng ràng buộc<br /> về mức độ quan trọng tương đối giữa hai tiêu chí, tập các<br /> ràng buộc được khởi tạo bởi hằng số r qua công thức:<br /> <br /> <br /> ớ ∀ ,<br /> <br /> (3)<br /> <br /> Tập các ràng buộc rút ra từ (3) là tuyến tính nên tạo<br /> thành tập lồi hay miền khả thi S.<br /> 2.1.2. Xác định phương án mất ưu thế<br /> Phương án thứ<br /> là phương án mất ưu thế nếu:<br /> ∃ ∈ | (P )<br /> <br /> (P ) ∀<br /> <br /> ∈<br /> <br /> Một cách xác định phương án mất ưu thế khác là sử<br /> dụng miền khả thi S để vét cạn các giá trị phương án có thể<br /> có và so sánh hai phương án với nhau, phương án mất ưu<br /> thế sẽ có giá trị nhỏ hơn phương án kia với mọi w ∈ S. Theo<br /> đó, nếu:<br /> min<br /> ∈<br /> <br /> (P )<br /> <br /> P<br /> <br /> 0, (4)<br /> <br /> với (P ) và P là giới hạn dưới và trên của (P )<br /> và P được tính theo công thức (5) và (6), đồng thời<br /> tồn tại ít nhất một bộ w = {w1, w2, ..., wn}∈ S sao cho (4)<br /> đúng với điều kiện lớn hơn thì phương án<br /> mất ưu thế<br /> trước phương án .<br /> SS sử dụng hàm mũ để xác định giới hạn trên và dưới<br /> của một hệ quả. Gọi a là hằng số xác định độ cong của hàm<br /> mũ, ta có đồ thị trong hình 2.<br /> Như vậy, công thức xác định giới hạn trên, dưới của hệ<br /> quả là:<br /> <br /> Hình 2. Giới hạn trên, dưới của giá trị của hệ quả trên đồ thị<br /> hàm mũ (a=0,2)<br /> <br /> 2.1.3. Kỹ thuật Even Swap<br /> Bản chất của ES là sự đánh đổi, tăng/giảm hệ quả này<br /> và bù đắp bằng sự giảm/tăng ở hệ quả khác trên cùng<br /> phương án. Mục đích của ES:<br /> •<br /> <br /> Tạo ra phương án ảo có cùng giá trị nhưng thuận<br /> tiện trong việc so sánh.<br /> <br /> •<br /> <br /> Làm xuất hiện phương án mất ưu thế.<br /> <br /> •<br /> <br /> Làm xuất hiện tiêu chí vô ích.<br /> <br /> • Cập nhật tỉ lệ mức độ quan trọng giữa các tiêu chí.<br /> Sự thay đổi tỉ lệ mức độ quan trọng dẫn đến miền khả<br /> thi S thay đổi, công thức cập nhật tỉ lệ wi/wj trong lượt áp<br /> dụng ES vào tiêu chí thứ i, j trên phương án x, y là:<br /> P<br /> P<br /> <br /> (7)<br /> P<br /> P<br /> 2.2. Phương pháp Smart-Swap 2<br /> Phương pháp SS2 kế thừa cơ sở lý thuyết của SS và<br /> được xây dựng định hướng hệ thống gợi ý, kí hiệu tập items<br /> là I, tập các thuộc tính của item là A và U là tập users. Mô<br /> hình bài toán lúc này sẽ trở thành ma trận 3 chiều:<br /> ∶ U I A →<br /> với<br /> là một số thực hoặc một phần tử trong tập rời<br /> ứng với mỗi<br /> là mức<br /> rạc dạng chữ hoặc số. Trọng số<br /> độ quan trọng của thuộc tính Ii đối với người dùng Uu.<br /> Từ đây, các công thức trong phần 2.1 vẫn được áp dụng<br /> trên SS2 với công thức chuyển đổi:<br /> ( ) = (P )<br /> Để thuận tiện cho việc so sánh và sử dụng cơ sở lý<br /> thuyết của phương pháp SS, các item được xem như là các<br /> phương án, các thuộc tính của item là các tiêu chí. Khác<br /> với SS, SS2 yêu cầu khởi tạo thứ tự mức độ quan trọng<br /> của các tiêu chí. Sắp xếp các tiêu chí vào l (l ≤ n) mức độ<br /> quan trọng ta xây dựng được ma trận mức độ quan trọng<br /> <br /> 96<br /> <br /> Nguyễn Văn Hiệu<br /> <br /> W: U I →<br /> với<br /> ∈ 1, . Khởi tạo tỉ lệ về mức độ<br /> quan trọng giữa hai lớp liên tiếp là r, tỉ lệ về mức độ quan<br /> trọng giữa các tiêu chí cùng lớp là v, ta có được các ràng<br /> buộc giữa các tiêu chí, từ đó miền khả thi S được hình<br /> thành. Tương tự như SS, kỹ thuật ES trong SS2 cũng được<br /> sử dụng để cập nhật mức độ quan trọng giữa các tiêu chí.<br /> Có 2 nguyên tắc cần được lưu ý về mức độ quan trọng là:<br /> •<br /> <br /> Mức độ quan trọng của các tiêu chí lớp dưới<br /> không thể vượt quá mức độ quan trọng của tiêu<br /> chí lớp trên.<br /> <br /> •<br /> <br /> Tính chất bắc cầu không nhất thiết phải thỏa mãn<br /> đối với tỉ lệ mức độ quan trọng.<br /> <br /> •<br /> <br /> Miền khả thi S luôn được cập nhật sau một lượt<br /> áp dụng ES, đây chính là khả năng thu thập thông<br /> tin người dùng của SS2.<br /> <br /> kiện bài toán mà ta có thể lựa chọn cách xử lý thích hợp.<br /> Một số cách có thể sử dụng là:<br /> •<br /> <br /> Ràng buộc bằng tính chất bắc cầu để tìm ra giá trị<br /> trọng số tuyệt đối, ưu tiên tỉ lệ trọng số của lượt<br /> áp dụng ES sau.<br /> <br /> •<br /> <br /> Lựa chọn w ngẫu nhiên từ S.<br /> <br /> •<br /> <br /> Tính theo một số giá trị w trên S rồi lấy giá trị<br /> trung bình giá trị các phương án.<br /> <br /> •<br /> <br /> Trong điều kiện lý tưởng, khi mà tính chất bắc cầu<br /> thỏa mãn với mọi tỉ lệ mức độ quan trọng, miền<br /> khả thi là một điểm duy nhất.<br /> Để hiểu rõ sự hình thành miền khả thi S, lấy ví dụ bài<br /> toán với 3 tiêu chí, tiêu chí 1 được xếp vào mức quan trọng<br /> thứ nhất (cao hơn), tiêu chí 2 và 3 được xếp vào mức quan<br /> trọng thứ 2. Khởi tạo r = 2, v được khởi tạo tùy ý, sau một<br /> lượt sử dụng ES, tỉ lệ w2/w3 được cập nhật từ v thành 2,<br /> miền khả thi S được hình thành như hình 3.<br /> <br /> Hình 4. Quy trình giải bài toán với SS2<br /> <br /> Hình 3. Mô phỏng miền khả thi S với 3 tiêu chí<br /> <br /> Sau khi miền khả thi S được hình thành, tùy vào điều<br /> <br /> Tập các phương án có giá trị cao nhất là lời giải của bài<br /> toán khi sử dụng phương pháp SS2. Sơ đồ trong hình 4 thể<br /> hiện quy trình tìm ra lời giải bài toán với SS2.<br /> Để hiểu rõ hơn về bản chất của phương pháp. Hãy cùng<br /> xem xét ví dụ “Bài toán chọn văn phòng” [3, 4]. Yêu cầu<br /> của bài toán là tìm ra văn phòng phù hợp nhất dựa trên 8<br /> tiêu chí. Có 12 văn phòng được liệt kê trong ví dụ, mô hình<br /> bài toán cho một user được thể trong bảng 1.<br /> <br /> Bảng 1. Bài toán chọn văn phòng theo [3,4]<br /> Phương án<br /> <br /> Kích<br /> thước<br /> (m2)<br /> <br /> Giá Mức độ cần cải<br /> thuê ($)<br /> tạo<br /> <br /> 1<br /> <br /> 180<br /> <br /> 2.000<br /> <br /> Đáng kể<br /> <br /> 2<br /> <br /> 240<br /> <br /> 3.000<br /> <br /> Không<br /> <br /> 3<br /> <br /> 210<br /> <br /> 2.800<br /> <br /> Vừa phải<br /> <br /> 4<br /> <br /> 214<br /> <br /> 2.000<br /> <br /> Rất nhỏ<br /> <br /> 5<br /> <br /> 300<br /> <br /> 3.200<br /> <br /> Đáng kể<br /> <br /> 6<br /> <br /> 170<br /> <br /> 1.800<br /> <br /> Đáng kể<br /> <br /> 7<br /> <br /> 250<br /> <br /> 2.600<br /> <br /> Đáng kể<br /> <br /> 8<br /> <br /> 260<br /> <br /> 2.650<br /> <br /> Vừa phải<br /> <br /> 9<br /> <br /> 262<br /> <br /> 2.400<br /> <br /> Lớn<br /> <br /> Bãi đỗ xe<br /> Tốt<br /> <br /> Khoảng<br /> Phương tiện cách đến<br /> công cộng trung tâm<br /> (km)<br /> <br /> Khác<br /> <br /> Chất lượng<br /> sinh sống<br /> <br /> Vừa phải<br /> <br /> Tuyệt vời<br /> <br /> Khá tệ<br /> <br /> 12<br /> <br /> Tốt<br /> <br /> Tốt<br /> <br /> 15<br /> <br /> Tốt<br /> <br /> Tồi tệ<br /> <br /> Tồi tệ<br /> <br /> Tuyệt vời<br /> <br /> 0<br /> <br /> Tuyệt vời<br /> <br /> Tốt<br /> <br /> Tuyệt vời<br /> <br /> Tồi tệ<br /> <br /> 25<br /> <br /> Vừa phải<br /> <br /> Tốt<br /> <br /> Tuyệt vời<br /> <br /> Tốt<br /> <br /> 4<br /> <br /> Tuyệt vời<br /> <br /> Rất tốt<br /> <br /> Khá tệ<br /> <br /> Tốt<br /> <br /> 0<br /> <br /> Tuyệt vời<br /> <br /> Tốt<br /> <br /> Tuyệt vời<br /> <br /> Vừa phải<br /> <br /> 7<br /> <br /> Tốt<br /> <br /> Vừa phải<br /> <br /> Vừa phải<br /> <br /> Tốt<br /> <br /> 10<br /> <br /> Vừa phải<br /> <br /> Vừa phải<br /> <br /> Tuyệt vời<br /> <br /> Tốt<br /> <br /> 10<br /> <br /> Vừa phải<br /> <br /> Rất tốt<br /> <br /> ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG, SỐ 3(112).2017-Quyển 1<br /> <br /> 97<br /> <br /> 10<br /> <br /> 241<br /> <br /> 2.500<br /> <br /> Nhỏ<br /> <br /> Rất tốt<br /> <br /> Vừa phải<br /> <br /> 7<br /> <br /> Tốt<br /> <br /> Tốt<br /> <br /> 11<br /> <br /> 198<br /> <br /> 2.200<br /> <br /> Đáng kể<br /> <br /> Tốt<br /> <br /> Tồi tệ<br /> <br /> 17<br /> <br /> Tốt<br /> <br /> Tốt<br /> <br /> 12<br /> <br /> 201<br /> <br /> 2.000<br /> <br /> Vừa phải<br /> <br /> Khá tệ<br /> <br /> Tồi tệ<br /> <br /> 22<br /> <br /> Khá tệ<br /> <br /> Vừa phải<br /> <br /> Tích cực<br /> <br /> Tiêu<br /> cực<br /> <br /> Tiêu cực<br /> <br /> Tích cực<br /> <br /> Tích cực<br /> <br /> Tiêu cực<br /> <br /> Tích cực<br /> <br /> Tích cực<br /> <br /> Ảnh hưởng<br /> <br /> Sử dụng SS và thông qua 19 lượt áp dụng ES [3],<br /> phương án 5 là phương án tối ưu. Tiến hành giải quyết bài<br /> toán sử dụng SS2, trước tiên ta cần sắp xếp tiêu chí vào các<br /> mức độ quan trọng. Dựa vào kết quả các lượt áp dụng ES<br /> <br /> khi sử dụng SS để giải quyết bài toán ta có thể nắm được<br /> yêu cầu của user từ đó giả sử rằng mức độ quan trọng của<br /> các tiêu chí được sắp xếp như bảng 2.<br /> <br /> Bảng 2. Sắp xếp mức độ quan trọng<br /> Tiêu chí<br /> <br /> Kích thước<br /> <br /> Giá thuê<br /> <br /> Mức độ cần<br /> cải tạo<br /> <br /> Bãi đỗ xe<br /> <br /> Phươnng tiện<br /> công cộng<br /> <br /> Khoảng cách<br /> đến trung tâm<br /> <br /> Khác<br /> <br /> Chất lượng<br /> sinh sống<br /> <br /> Mức<br /> <br /> A<br /> <br /> B<br /> <br /> C<br /> <br /> D<br /> <br /> E<br /> <br /> F<br /> <br /> G<br /> <br /> G<br /> <br /> Gọi cx là số tiêu chí trong mức độ quan trọng thứ x, khởi<br /> tạo giá trị r = 1,3, v = 1 và giá trị trọng số lớp thấp nhất là<br /> ta có bảng 3.<br /> Bảng 3. Bảng khởi tạo giá trị<br /> cx<br /> <br /> Mức<br /> <br /> Trọng số<br /> <br /> Giá trị khởi tạo<br /> <br /> Giá trị trọng số thực<br /> <br /> Giá trị trọng số sau khi chuẩn hóa<br /> <br /> 1<br /> <br /> A<br /> <br /> r5. r4. r3. r2. r1.r0.<br /> <br /> r5 = 1,3<br /> <br /> 4,83<br /> <br /> 0,26<br /> <br /> 1<br /> <br /> B<br /> <br /> r4. r3. r2. r1.r0.<br /> <br /> r4 = 1,3<br /> <br /> 3,71<br /> <br /> 0,20<br /> <br /> 1<br /> <br /> C<br /> <br /> r3. r2. r1.r0.<br /> <br /> r3 = 1,3<br /> <br /> 2,86<br /> <br /> 0,15<br /> <br /> 1<br /> <br /> D<br /> <br /> r2. r1.r0.<br /> <br /> r2 = 1,3<br /> <br /> 2,20<br /> <br /> 0,12<br /> <br /> 1<br /> <br /> E<br /> <br /> r1.r0.<br /> <br /> r1 = 1,3<br /> <br /> 1,69<br /> <br /> 0,09<br /> <br /> 1<br /> <br /> F<br /> <br /> r0.<br /> <br /> r0 = 1,3<br /> <br /> 1,30<br /> <br /> 0,07<br /> <br /> 2<br /> <br /> G<br /> <br /> 1,00<br /> <br /> 0,05<br /> <br /> 18,69<br /> <br /> 1<br /> <br /> Tổng<br /> <br /> .(<br /> <br /> ).<br /> <br /> Từ bảng 2 và 3, áp dụng công thức (5) để chuẩn hóa các<br /> hệ quả và tính toán giá trị của các phương án. Biểu đồ trong<br /> hình 5 mô tả mức độ ảnh hưởng của các tiêu chí lên giá trị<br /> của phương án, r được khởi tạo với giá trị là 1,3.<br /> 0.7<br /> <br /> Chất lượng sinh<br /> sống<br /> Khác<br /> <br /> 0.6<br /> <br /> Khoảng cách tớ<br /> trung tâm<br /> Phương tiện côn<br /> cộng<br /> Bãi đỗ xe<br /> <br /> 0.5<br /> 0.4<br /> 0.3<br /> <br /> Mức độ cần cải<br /> tạo<br /> Giá thuê<br /> <br /> 0.2<br /> 0.1<br /> <br /> Kích thước<br /> <br /> 0<br /> P/a P/a P/a P/a P/a P/a P/a P/a P/a P/a P/a P/a<br /> 1 2 3 4 5 6 7 8 9 10 11 12<br /> <br /> Hình 5. Biểu đồ giá trị của các phương án<br /> <br /> Sau bước khởi tạo, ta có thể chọn ra tập các phương án<br /> cao nhất để đưa ra sự gợi ý và thu thập thông tin người<br /> dùng qua các lượt áp dụng ES, để đưa ra sự gợi ý chính xác<br /> hơn. Với việc sử dụng hệ thống ri như trong bảng 4, tính<br /> chất bắc cầu về tỉ lệ mức độ quan trọng sẽ được bảo toàn<br /> <br /> dẫn đến miền khả thi S lúc này là một điểm duy nhất.<br /> Quay trở lại ví dụ, sau khi khởi tạo, các phương án có<br /> thể được sử dụng làm phương án gợi ý là các phương án có<br /> giá trị cao nhất, trong trường hợp này, các phương án được<br /> chọn là 4, 5, 7, 9, 10. Đến đây, để nâng cao độ chính xác<br /> của tập phương án tối ưu, ta có thể sử dụng kỹ thuật ES để<br /> cập nhật miền khả thi S. Số lượt áp dụng ES được càng<br /> nhiều thì độ chính xác trong việc tìm ra tập phương án tối<br /> ưu càng cao.<br /> Tiếp tục với ví dụ, xét phương án 5 và 9, thực hiện áp<br /> dụng ES trên tiêu chí Kích thước và Giá thuê của phương<br /> án 5; theo đó, hệ quả trên tiêu chí Kích thước của phương<br /> án 5 thay đổi từ 300 sang 262 (tương ứng với sự thay đổi từ<br /> 1 sang 0,71), hệ quả trên tiêu chí Giá thuê thay đổi từ 3.200<br /> sang 2.600 (tương ứng với sự thay đôi từ 0 sang 0,57). Sau<br /> lượt áp dụng ES này, áp dụng công thức 7, r5 sẽ được thay<br /> đổi từ 1,3 sang x, với x là tỉ lệ wA/wB rút ra từ phương trình:<br /> = 0,71 + 0,57<br /> 1 +0<br /> Ta được kết quả r5 = x = 1,97, tiếp tục tiến hành cập<br /> nhật miền khả thi S.<br /> Một yếu tố ảnh hưởng đến quá trình giải bài toán là giá<br /> trị khởi tạo cho r. Biểu đồ 2 thể hiện sự thay đổi giá trị các<br /> phương án với các giá trị khởi tạo r. Nhận thấy độ chênh<br /> lệch giá trị tổng càng tăng khi tăng r.<br /> <br /> 98<br /> <br /> Nguyễn Văn Hiệu<br /> <br /> có thể được thay đổi sau khi áp dụng ES.<br /> <br /> 0.8<br /> <br /> 3. Áp dụng Smart-Swaps 2 vào hệ thống gợi ý theo ngữ<br /> cảnh<br /> Xét bài toán ra quyết định chấp nhận rủi ro với điều<br /> kiện thay đổi, bài toán có hai tính chất:<br /> <br /> 0.7<br /> 0.6<br /> 0.5<br /> <br /> •<br /> <br /> 0.4<br /> 0.3<br /> <br /> Tính chất rủi ro (hay sai số) nhưng chấp nhận<br /> được.<br /> <br /> •<br /> <br /> 0.2<br /> 0.1<br /> 0<br /> 1<br /> <br /> 2<br /> <br /> 3<br /> <br /> 4<br /> <br /> 5<br /> <br /> r = 1.2<br /> <br /> 6<br /> r=1.3<br /> <br /> 7<br /> <br /> 8<br /> <br /> 9<br /> <br /> 10 11 12<br /> <br /> r=1.6<br /> <br /> r=3<br /> <br /> Hình 6. Biểu đồ giá trị của các phương án khi thay đổi giá trị<br /> khởi tạo r<br /> <br /> Để giải quyết bài toán, người ra quyết định có thể thay<br /> đổi giá trị khởi tạo cho r cho đến khi thấy được sự phân hóa<br /> rõ rệt. Giá trị khởi tạo không nên quá lớn (tiến ra xa 1+) hay<br /> quá bé (tiền gần 1+) vì điều này sẽ khiến độ phân hóa quá<br /> lớn, các tiêu chí có mức độ quan trọng thấp có nguy cơ bị<br /> lấn át hoàn toàn, hoặc độ phân hóa quá thấp khiến sự phân<br /> nhóm là không rõ rệt. Cần lưu ý trong ví dụ này v được<br /> khởi tạo là 1, tức là các tiêu chí trên cùng lớp mức độ quan<br /> trọng được khởi tạo với cùng mức độ quan trọng, tỉ lệ này<br /> <br /> Tính chất điều kiện thay đổi, tập phương án thay<br /> đổi liên tục.<br /> Yêu cầu của bài toán là tốc độ tìm ra tập phương án tối<br /> ưu nhanh và phù hợp với từng hoàn cảnh của người ra<br /> quyết định.<br /> Phương pháp SS2 có thể giải quyết bài toán đã nêu bằng<br /> cách xem mỗi hoàn cảnh của người ra quyết định là một<br /> user tương ứng với một ma trận hệ quả và ma trận mức độ<br /> quan trọng, mỗi ma trận mức độ quan trọng tương ứng hình<br /> thành một miền khả thi S. Các miền khả thi S đã được hình<br /> thành sẽ được cập nhật thông qua các lượt áp dụng ES, từ<br /> đó ta tính được giá trị từng phương án trên các tập phương<br /> án khác nhau trong những hoàn cảnh khác nhau.<br /> Bảng 4 chỉ ra sự tương đồng giữa bài toán gợi ý theo<br /> ngữ cảnh có mô hình “user, item, thuộc tính item” và bài<br /> toán ra quyết định chấp nhận rủi ro với điều kiện thay đổi.<br /> Điều này chứng minh việc áp dụng phương pháp SS2 được<br /> trình bày trong bài báo vào bài toán gợi ý theo ngữ cảnh là<br /> hoàn toàn có tiềm năng.<br /> <br /> Bảng 4. Sự tương đồng giữa bài toán gợi ý theo ngữ cảnh và bài toán ra quyết định với điều kiện thay đổi<br /> Bài toán gợi ý theo ngữ cảnh<br /> <br /> Bài toán ra quyết định với điều kiện thay đổi<br /> <br /> Người dùng<br /> <br /> Người ra quyết định<br /> <br /> Tập sản phẩm<br /> <br /> Tập phương án<br /> <br /> Thuộc tính của sản phẩm<br /> Sự thay đổi<br /> ngữ cảnh<br /> <br /> Tập tiêu chí<br /> <br /> Sự thay đổi về hoàn cảnh của người<br /> dùng<br /> <br /> Sự thay đổi về hoàn cảnh của hoàn cảnh của<br /> người ra quyết định.<br /> <br /> Sự thay đổi tập sản phẩm<br /> <br /> Thay đổi tập phương án<br /> <br /> Thu thập thông tin người dùng<br /> <br /> 4. Kết luận và triển vọng<br /> Bài báo đã trình bày sơ lược về cơ sở lý thuyết trong hệ<br /> thống hỗ trợ ra quyết định Smart-Swaps và lấy đó làm cơ<br /> sở để xây dựng phương pháp Smart-Swaps 2 theo định<br /> hướng hệ thống gợi ý. Hướng tiếp cận của bài báo là đánh<br /> đổi độ chính xác với tốc độ ra quyết định, theo đó đầu ra<br /> của SS2 là một tập các phương án tối ưu. Bài báo đã có<br /> những đóng góp sau:<br /> •<br /> <br /> Xây dựng phương pháp SS2 định hướng hệ thống<br /> gợi ý.<br /> <br /> •<br /> <br /> Đề xuất hướng sử dụng SS2 để giải quyết bài toán<br /> ra quyết định chấp nhận rủi ro với điều kiện thay<br /> đổi.<br /> <br /> •<br /> <br /> Chỉ ra hướng tiềm năng trong việc áp dụng SS2<br /> vào hệ thống gợi ý theo ngữ cảnh.<br /> <br /> Cập nhật miền khả thi S thông qua các phiên áp<br /> dụng kĩ thuật ES<br /> <br /> Phương pháp SS2 hứa hẹn có thể được áp dụng trong<br /> các hệ thống gợi ý cá nhân được cài đặt trên thiết bị của<br /> người dùng và thu thập thông tin người dùng thông qua<br /> thông tin được cung cấp trong các lượt sử dụng ES dưới<br /> dạng câu hỏi nhanh, qua đó đưa ra gợi ý cho người dùng<br /> thích hợp theo từng hoàn cảnh.<br /> TÀI LIỆU THAM KHẢO<br /> [1] John S. Hammond, Ralph L. Keeney, Howard Raiffa, Smart<br /> Choices: A Practical Guide to Making Better Decisions, 2002<br /> [2] R.P. Hämäläinen, J. Mustajoki, P. Alanaatu, V. Karttunen, A. Arstila<br /> and J. Nissinen, SmartSwaps – Smart Choices with Even Swaps,<br /> Computer Software, Systems Analysis Laboratory, Helsinki<br /> University of Technology, 2003.<br /> [3] Jyri Mustajoki and Raimo P. Hämäläinen, Smart-Swaps – A<br /> decision support system for multicriteria decision analysis with the<br /> even swaps, Systems Analysis Laboratory, Helsinki University of<br /> Technology, P.O. Box 1100, FIN-02015 HUT, Finland, 2006.<br /> <br />