Đề tài Nghiên cứu mô hình đa tác tử hút và đẩy cho phương pháp lọc cộng tác

hư thế nào. Còn sự hợp tác giữa các tác tử là cơ chế mà thông qua đó các tác tử trao đổi tri thức, các kế hoạch cộng tác giữa chúng để giải quyết những vấn đề lớn hơn khả năng của mỗi tác tử. Khả năng di trú: Các tác tử có thể di chuyển đến các môi trường khác, tìm kiếm thông tin cần thiết và trả lại kết quả mà người dùng mong muốn. b) Phân loại: Dựa trên các đặc điểm được trình bày ở trên, có thể chia các tác tử thành các loại sau: Tác tử phụ tá (Assistant agents): Tác tử phụ tá hoạt động như một người phụ tá, cùng cộng tác với người sử dụng trong một môi trường. Tác tử loại này quan sát, giám sát các hành động của người sử dụng, “học” điều đó và đưa ra cách tốt hơn để thực hiện các tác vụ. Tác tử phụ tá học để trợ giúp cho người sử dụng theo bốn cách khác nhau: - Quan sát và bắt chước người sử dụng (học từ người sử dụng). - Thông qua các phản hồi tích cực và tiêu cực nhận được từ người sử dụng. - Bằng việc nhận được những lời hướng dẫn rõ ràng từ phía người sử dụng. - Bằng việc hỏi lời khuyên từ các tác tử khác. Sự hợp tác giữa tác tử giao diện với các tác tử khác chỉ giới hạn trong việc hỏi các thông tin. Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 29 Tác tử cộng tác (Collaboration agents): Đối với các tác tử loại này, tính tự trị và sự cộng tác với các tác tử khác được nhấn mạnh. Để có được sự cộng tác với các tác tử khác, các tác tử này phải thực hiện đàm phán để đạt sự thoả thuận về cơ chế cộng tác. Tác tử động (Mobile agents): Tác tử động là phần mềm tính toán có khả năng “di chuyển” trên các mạng diện rộng như Internet, tương tác với các máy chủ phân tán, thu thập thông tin và quay về sau khi đã thực hiện các công việc cho người sử dụng. Khả năng động này đưa đến khái niệm lập trình từ xa (remote programming), trong đó các tác tử tham gia tương tác đảm nhân cả hai vai trò: cung cấp dịch vụ (server) và khai thác dịch vụ (client). Tác tử phản ứng (Reactive agents): Các tác tử phản ứng không xử lý mô hình bên trong đặc trưng của môi trường, thay vào đó chúng phản ứng lại với sự kích thích đối với trạng thái hiện tại của môi trường mà chúng hoạt động. Kiến trúc của các tác tử phản ứng và sự giao tiếp giữa chúng nhìn chung rất đơn giản. Tuy nhiên, khi xem xét tổng quát hệ thống tác tử, có thể thấy được sự tương tác phức tạp giữa chúng. Ba nguyên tắc cơ bản đối với các tác tử phản ứng là: - Tương tác động giữa các tác tử không thông minh có thể dẫn tới sự phức tạp. - Mỗi tác tử phản ứng thường được xem như là một tập hợp các đối tượng hoạt động một cách độc lập và thực hiện các tác vụ cụ thể, chẳng hạn cảm biến, mô tơ điều khiển. Giao tiếp giữa các đối tượng này thường ở mức thấp. Một tác tử phản ứng thường làm với biểu diễn dữ liệu cảm biến mức thô, ngược lại với biểu diễn dữ liệu mức cao thường được sử dụng bởi các loại tác tử khác. 2.1.2. Hệ thống đa tác tử 1) Khái niệm Qua khái niệm tác tử, hình ảnh của một hệ thống đa tác tử có thể được liên tưởng như một xã hội của những động vật bậc thấp (ví dụ đàn kiến) mà các phần tử trong đó có những nét đặc trưng như: có mối quan hệ (phụ thuộc, chi phối, ngang hàng), có tương tác trao đổi thông tin và học hỏi lẫn nhau, tác động vào môi trường và ngược lại. Một hệ thống đa tác tử được cấu thành bởi: môi trường sống; tập các đối tượng thụ động chịu Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 30 sự tác động của các tác tử lên nó; tập các tác tử là các phần tử chủ động; tập các mối quan hệ giữa các phần tử với nhau; tập các thao tác giữa các phần tử với nhau. 2) Đặc điểm Một hệ đa tác tử có các đặc điểm sau: - Mỗi tác tử có những thông tin không đầy đủ để giải quyết một bài toán đặt ra, do khả năng của mỗi tác tử là có hạn và bài toán cần giải quyết là quá lớn với một tác tử đơn. - Hệ đa tác tử không có bộ điều khiển toàn cục hệ thống, tức là các tác tử hoạt động một cách độc lập không phụ thuộc vào tác tử khác và cả hệ thống tổng thể. - Dữ liệu được phân tán cho nhiều tác tử khác nhau trong hệ thống. Mỗi tác tử chỉ có thể quản lý một nguồn tài nguyên hạn chế. Đồng thời, sự tính toán trong hệ đa tác tử là không đồng bộ. Như vậy, trong hệ đa tác tử, các tác tử hoạt động một cách tự chủ và độc lập với nhau và có thể tương tác với nhau dưới nhiều hình thức khác nhau: cộng tác, cạnh tranh, thương lượng,... để chia sẻ tài nguyên và khả năng hợp lý. Môi trường của hệ đa tác tử có tính chất: - Là môi trường mở. Môi trường đa tác tử cung cấp một cơ sở hạ tầng để xác định các giao thức truyền thông và tương tác. - Môi trường chứa những tác tử tự quản, phân tán. Mỗi tác tử có mục tiêu hoạt động riêng. 3) Ứng dụng Hiện nay, các hệ thống đa tác tử đang ngày càng được sử dụng rộng rãi hơn trong nhiều ứng dụng, từ các hệ thống tương đối nhỏ để hỗ trợ cá nhân đến các hệ thống mở, phức tạp, và đặc biệt quan trọng dành cho các ứng dụng công nghiệp. Ứng dụng công nghiệp là những ứng dụng rất quan trọng cho các hệ thống đa tác tử bởi vì chúng là nơi mà công nghệ đa tác tử đầu tiên được thử nghiệm và chứng minh tiềm năng ban đầu của nó. Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 31 Một trong những lĩnh vực ứng dụng quan trọng nữa của hệ thống đa tác tử là quản lý thông tin. Ví dụ, các tác tử có thể được sử dụng để tìm kiếm và lọc thông tin. Internet đã thúc đẩy việc sử dụng công nghệ tác tử trong lĩnh vực quản lý tiến trình nghiệp vụ và thương mại điện tử. Trong thực tế, trước sự gia tăng của thương mại điện tử, việc quản lý tiến trình nghiệp vụ đã gần như được điều khiển bởi các tương tác của con người. Giờ đây thương mại điện tử và tiến trình nghiệp vụ được tự động hóa đang ngày càng đóng vai trò then chốt trong nhiều tổ chức bởi vì chúng cung cấp những cơ hội để cải thiện đáng kể cách thức mà các thực thể khác nhau tham gia vào tương tác của tiến trình nghiệp vụ. Giao thông và vận tải cũng là một lĩnh vực quan trọng, nơi mà bản chất phân tán của các tiến trình giao thông, vận tải và sự độc lập mạnh mẽ giữa các thực thể có liên quan trong các tiến trình đó làm cho các hệ thống đa tác tử trở thành một công cụ có giá trị cho việc thực hiện các giải pháp thương mại thực sự có hiệu quả. Một số lĩnh vực đã được giải quyết như OASIS, OASIS là một hệ thống điều khiển không lưu phức tạp dự trên mô hình tác tử BDI, được triển khai và được sử dụng thành công tại sân bay Sydney ở Australia. Các hệ thống viễn thông là một lĩnh vực ứng dụng đã sử dụng thành công các hệ đa tác tử. Trong thực tế, các hệ thống viễn thông là các mạng lưới lớn và phân tán gồm các thành phần được kết nối với nhau. Những thành phần đó cần phải được theo dõi và quản lý trong thời gian thực. Vì vậy, các hệ đa tác tử được sử dụng cả trong việc quản lý các mạng lưới phân tán lẫn cho việc cài đặt các dịch vụ viễn thông tiên tiến. Nhiều hệ thống đa robot cũng sử dụng các kỹ thuật lập kế hoạch phân tán và đa tác tử để phối hợp các robot khác nhau. FIRE phối hợp các hành động của nhiều robot ở nhiều mức trừu tượng hóa. MISUS phối hợp các kỹ thuật từ việc lập kế hoạch và lập lịch với học máy để thực hiện việc thăm dò có tính khoa học một cách tự chủ. Kỹ thuật lập kế hoạch và lập lịch phân tán được sử dụng để tạo ra các kế hoạch cộng tác nhiều lần, việc thực thi kế hoạch giám sát có hiệu quả và thực hiện làm lại kế hoạch khi cần thiết. Hơn nữa, những hệ thống này có thể suy luận về những mục đích phụ thuộc lẫn nhau để thực hiện tối ưu hóa kế hoạch và để tăng giá trị của dữ liệu thu thập được. Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 32 Một số ứng dụng đa tác tử đáng quan tâm khác có thể được tìm thấy trong hệ thống chăm sóc sức khỏe. Trong thực tế, các hệ thống đa tác tử đã được đề xuất để giải quyết nhiều loại vấn đề khác nhau trong lĩnh vực chăm sóc sức khỏe, bao gồm lập kế hoạch và quản lý bệnh nhân, chăm sóc sức khỏe người cao tuổi và cộng đồng, truy cập và quản lý thông tin y tế và hỗ trợ quyết định. Một vài ứng dụng đã cài đặt cho thấy rằng hệ thống đa tác tử có thể là giải pháp đúng đắn cho việc xây dựng các hệ thống hỗ trợ quyết định y học và cải thiện sự phối hợp giữa các chuyên gia khác nhau tham gia vào quá trình chăm sóc sức khỏe. 2.2. Mô hình đa tác tử sử dụng lực hút và đẩy Trong những năm gần đây, một hướng tiếp cận mới của hệ thống đa tác tử là ứng dụng đa tác tử sử dụng lực hút và đẩy giữa các tác tử vào một số bài toán tự tổ chức (self-organization). Đây là động lực chính để tôi sử dụng mô hình đa tác tử trong bài toán của hệ tư vấn. Trong phần này, khóa luận sẽ trình bày hai nghiên cứu ứng dụng hệ thống đa tác tử sử dụng lực hút và đẩy trong ứng dụng phân loại email của Renault [6] và ứng dụng tìm kiếm ảnh của Cao Hồng Huệ và các đồng nghiệp [4]. 2.2.1. Mô hình đa tác tử cho phân loại email Renault [6] đã đề xuất một mô hình đa tác tử tự động hút / đẩy cho ứng dụng phân loại email. Mục đích của mô hình này là tổ chức các email trong một không gian hai chiều theo độ tương tự, trong đó mỗi email được gắn với một từ khóa, đồng thời được đại diện bởi một tác tử và không cần phải xác định trục tọa độ hoặc cách để tổ chức thông tin. Mô hình này cho phép các tác tử giao tiếp với nhau thông qua các kích thích tố ảo và chúng tự tổ chức trong không gian. Kích thích tố là những yếu tố trong môi trường tác động trực tiếp vào bản thân tác tử. Hệ thống có thể tổ chức (gom cụm / phân loại ) email và cho phép người dùng trực quan tương tác với nó. Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 33 Hình 2.2. Mô hình đa tác tử hút và đẩy cho phân loại email 2.2.2. Mô hình đa tác tử cho tìm kiếm ảnh Dựa trên ý tưởng của Renault [6] đã trình bày ở trên, Cao Hồng Huệ và các đồng nghiệp [4] đã nghiên cứu mô hình đa tác tử hút và đẩy cho tìm kiếm ảnh. Mô hình này sử dụng các tác tử phản ứng với môi trường (reactive agent) sử dụng các lực hút / đẩy cho tổ chức dữ liệu trong không gian hai chiều. Các tác tử được di chuyển tự do trong không gian này mà đường đi của chúng sẽ không xác định trước. Chúng chỉ phản ứng với các kích thích bên ngoài được gửi từ các tác tử khác. Mỗi tác tử tương tác với những tác tử khác thông qua lực, lực đó có thể là lực hút hoặc lực đẩy. Lực được tính toán giữa hai tác tử dựa trên sự giống nhau của các vector đặc tính hoặc từ các từ khóa mô tả của từng tác tử. Do đó, các tác tử được hút bởi những tác tử tương tự và bị đẩy lùi từ những tác tử không tương tự. Mô hình hoạt động dựa trên chu trình lặp theo một khoảng thời gian. Cứ mỗi lần lặp là các tác tử sẽ bị thay đổi vị trí về mặt không gian trong mô hình. Sự thay đổi đó như đã nói ở trên là do lực tác động bởi các tác tử khác, hay còn gọi là các láng giềng. Việc lựa chọn láng giềng trong mỗi lần lặp khiến mô hình hoạt động khá chậm, đây cũng là hạn chế của mô hình này. Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 34 Hình 2.3. Mô hình đa tác tử hút và đẩy cho tìm kiếm ảnh Ý tưởng hệ đa tác tử của Renault [6] và Cao Hồng Huệ [4] khá giống với ý tưởng trong hệ tư vấn. Cả hai đều dùng độ tương tự để tổ chức dữ liệu, còn hệ tư vấn thì dùng độ tương tự giữa những người dùng hay sản phẩm để lấy ra danh sách các sản phẩm tư vấn. Nhưng trong hệ tư vấn, ví dụ phương pháp lọc cộng tác, việc lấy danh sách tư vấn được tính dựa trên công thức phức tạp. Còn nếu áp dụng ý tưởng của hệ đa tác tử hút và đẩy thì việc lấy kết quả tư vấn sẽ dễ dàng hơn bằng cách lấy các láng giềng (trong mặt phẳng hai chiều) của một tác tử. Do đó, tác giả đề xuất mô hình đa tác tử sử dụng lực hút / đẩy cho tư vấn phim. 2.3. Mô hình đa tác tử hút và đẩy cho phương pháp lọc cộng tác 2.3.1. Tổng quan về mô hình Mô hình đề xuất sẽ sử dụng các tác tử với các lực hút và đẩy cho việc tổ chức dữ liệu trong mặt phẳng hai chiều và hiệu chỉnh cho phù hợp với bài toán tư vấn phim. Trong mô hình này, hướng tiếp cận được sử dụng là dựa trên sản phẩm (item-based). Do đó, mỗi bộ phim được đại diện bởi một tác tử / hình ảnh (poster của bộ phim) trong mặt phẳng hai chiều. Mỗi tác tử sẽ có một mảng chứa các đánh giá (giá trị trong đoạn [1,5]) của người dùng cho bộ phim đó. Các tác tử này tương tác với nhau và sinh ra các lực hút hoặc lực đẩy giữa chúng. Hai tác tử là hút nhau khi độ tương tự giữa chúng là cao và đẩy nhau khi độ tương tự giữa chúng là thấp. Dựa trên việc tổng hợp các lực hút / đẩy tác dụng lên một tác tử, tác Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 35 tử đó sẽ di chuyển đến vị trí mới. Tại vị trí mới này, tác tử lại tương tác với các tác tử láng giềng mới và lại tiếp tục di chuyển. Quá trình di chuyển sẽ kết thúc khi tác tử di chuyển về đúng vị trí của nó trong môi trường các tác tử và tạo thành môi trường ổn định. Cách thức hoạt động của các tác tử trong môi trường như vậy làm cho mô hình này trở thành một mô hình tự tổ chức (self – organization). Sau khi môi trường đạt đến trạng thái ổn định, hai tác tử nằm gần nhau trong mặt phẳng hai chiều sẽ là hai tác tử giống nhau và có thể được dùng để tư vấn cho nhau. Hình 2.4. Không gian của mô hình Tiếp theo, khóa luận xin trình bày những nội dung cụ thể nhất về mô hình đề xuất như: môi trường, cách thức hoạt động của tác tử, cách thức tương tác của các tác tử, cách thức chọn láng giềng,... 1) Môi trường Trong mô hình, môi trường được thể hiện qua không gian hai chiều, dữ liệu của chúng được lưu trữ trên hai trục x và y. Mô hình sẽ lặp liên tục sau mỗi bước thời gian, cứ mỗi bước lặp là một lần các tác tử thay đổi về mặt vị trí trong không gian. Với mỗi tác tử, hướng di chuyển của nó được sinh ra bằng cách tổng hợp các lực tác động từ các láng giềng lên nó. Sự di chuyển của các tác tử được thể hiện ở hình 2.5. Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 36 Hình 2.5. Môi trường của các tác tử 2) Tác tử phản ứng với môi trường Các tác tử trong mô hình là tác tử phản ứng với môi trường, nghĩa là chúng không có bộ nhớ để lưu trữ hoạt động của mình. Hành động duy nhất của tác tử có thể làm là di chuyển. Điều này dẫn đến khả năng tăng tốc, phanh hoặc thay đổi hướng. Do đó, chuyển động của tác tử được gây ra bởi các lực áp dụng trực tiếp vào chính nó và lực quán tính có sẵn của bản thân nó. Hình 2.6 biểu diễn cách quản lý lực quán tính và lực áp dụng của tác tử trong mô hình, Ti tương ứng với một mốc thời gian nhất định và Ti +1 là mốc thời gian kế tiếp. Hình 2.6. Quản lý lực quán tính trong mô hình Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 37 3) Tương tác giữa các tác tử Tại mỗi bước lặp, các tác tử của hệ thống (toàn bộ hoặc không) sẽ tương tác với láng giềng của chúng. Những tương tác này được đặc trưng bởi các lực áp dụng giữa các tác tử với nhau. Các lực này thể hiện mong muốn thu hút hoặc đẩy lùi một tác tử, do đó các lực này được gọi là lực hút / đẩy. Các lực này gây ra chuyển động cho các tác tử. Đọc phần 2.3.2 để hiểu rõ về lực hút / đẩy trong mô hình này. 4) Phương pháp chọn láng giềng Tại mỗi lần lặp, mỗi tác tử chỉ phản ứng với các tác tử nhất định trong một khu vực. Do mô hình luôn thay đổi và vận động nên tại mỗi lần lặp khu vực đó có thể sẽ thay đổi. Khái niệm về khu vực không giới hạn một khái niệm về khoảng cách trong không gian như thường lệ. Khóa luận đề xuất bốn chế độ lựa chọn láng giềng như sau: Lân cận: Tất cả các tác tử trong bán kính cố định được coi là láng giềng. Chọn Mẫu: Trong danh sách của vùng cận kề, lựa chọn ngẫu nhiên một vài tác tử làm láng giềng chứ ko chọn toàn bộ. Ngẫu nhiên: Các tác tử được lựa chọn ngẫu nhiên từ tất cả các tác tử trong mô hình. Đây là loại khu vực có thể mở rộng phạm vi tương tác giữa các tác tử. Vùng xác định: Các tác tử được chọn từ một khu vực xác định nào đó để làm láng giềng. Lựa chọn này cho phép kiểm soát tương tác giữa các tác tử một cách chính xác. Hình 2.7. Các cách chọn láng giềng Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 38 Trong mô hình đề xuất, ở cấp độ địa phương tác giả chọn láng giềng ở vùng lân cận. Sau đó, ở cấp độ toàn cục tác giả chọn láng giềng theo cách ngẫu nhiên. Để hiểu rõ hơn về cấp độ địa phương và toàn cục, xin đọc phần 2.3.3. 2.3.2. Lực hút và đẩy trong mô hình 1) Độ tương tự giữa hai tác tử Trong phương pháp lọc cộng tác dựa trên sản phẩm (item-based), các sản phẩm được so sánh dựa trên mức độ tương tự của chúng. Do đó, mô hình này cũng sử dụng độ tương tự của phương pháp lọc cộng tác dựa trên sản phẩm làm căn cứ để tạo ra lực hút và đẩy cho các tác tử. Một số cách đo độ tương tự đã được giới thiệu ở chương I, như: Độ tương tự Pearson, Hệ số tương quan Spearman, Hệ số tương quan của Kendall, Sai phân bình phương trung bình, Entropy, Độ tương tự cosin, Độ tương tự cosin điều chỉnh. Về bản chất, những độ đo tương tự này là biến đổi của độ tương quan Pearson, nhưng các nghiên cứu thực nghiệm đã cho thấy rằng hệ số tương quan Pearson cho kết quả tốt hơn. Do đó, tác giả quyết định chọn Hệ số Pearson để tính độ tương tự giữa hai tác tử: 𝑤𝑎,𝑢 = ∑ (𝑟𝑎,𝑖 − 𝑟�̅�)(𝑟𝑢,𝑖 − 𝑟�̅�)𝑖∈𝐼 √∑ (𝑟𝑎,𝑖 − 𝑟�̅�) 2 ∑ (𝑟𝑢,𝑖 − 𝑟�̅�) 2 𝑖∈𝐼𝑖∈𝐼 Trong đó, trọng số 𝑤𝑎,𝑢 là độ tương tự giữa người dùng u và người cần tư vấn a, I là tập các sản phẩm được bình chọn bởi cả hai người dùng, 𝑟𝑢,𝑖 là bình chọn được gán cho sản phẩm i bởi người dùng u, và 𝑟�̅� là giá trị bình chọn trung bình của người dùng u. 2) Quy tắc xác định lực Một tác tử luôn luôn tạo ra một lực để áp dụng vào tác tử khác. Lực đó được đặc trưng bởi hướng và độ mạnh. Hướng được xác định bởi bản chất của lực là hút hoặc đẩy. Lực này thể hiện mong muốn của một tác tử hướng về hoặc tránh xa một tác tử khác. Muốn xác định hành vi của các tác tử ở mức độ địa phương phải biết được độ tương tự hoặc không tương tự Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 39 của chúng trong giới hạn láng giềng. Các tác tử tương tự nhau sẽ có vị trí gần nhau và ngược lại. Dựa trên ý tưởng này, tác giả đặt ra hai quy tắc cơ bản để xác định hành vi của các tác tử ở mức độ địa phương: Hai tác tử tương tự nhau sẽ hút nhau, mục đích là làm cho chúng gần nhau hơn. Hai tác tử không tương tự nhau sẽ đẩy nhau, mục đích là làm cho chúng tách xa nhau ra. Còn về độ mạnh của lực, nó phụ thuộc vào hai điều: Đầu tiên là độ tương tự giữa các tác tử, thứ hai là khoảng cách giữa các tác tử. Sau khi hợp nhất hai tiêu chí độ tương tự và khoảng cách đó, quy tắc thiết lập lực giữa hai tác tử được thể hiện qua hình 2.8. Hình 2.8. Tính chất lực và độ mạnh lực dựa trên độ tương tự và khoảng cách (cách tiếp cận rời rạc) Trong thực tế, sẽ không thể giới hạn chính xác giá trị rời rạc khi đánh giá khoảng cách và sự tương đồng giữa các tác tử. Cho nên Khóa luận đề xuất các quy tắc phù hợp với các giá trị liên tục như hình 2.9. Hình 2.9. Tính chất lực và độ mạnh lực dựa trên độ tương tự và khoảng cách (cách tiếp cận liên tục) Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 40 Dựa vào hình 2.9, ta thấy luôn tồn tại một ngưỡng trung lập của lực. Ngưỡng này làm căn cứ để xác định lực đó là hút hay đẩy. Do đó: Nếu kết quả đưa ra lớn hơn ngưỡng trung lập, lực đó là lực đẩy. Lực này được tính theo công thức: 𝑓 = 𝑤 − 𝑤𝑚𝑖𝑛 (𝑤𝑚𝑎𝑥 − �̅�) × 𝑑 Nếu kết quả đưa ra nhỏ hơn ngưỡng trung lập, lức đó là lực hút. Lực này được tính theo công thức: 𝑓 = 𝑤 − �̅� (𝑤𝑚𝑎𝑥 − �̅�) × 𝑑 Trong đó, 𝑤 là độ tương tự giữa hai tác tử; �̅�, 𝑤𝑚𝑎𝑥, 𝑤𝑚𝑖𝑛 lần lượt là giá trị độ tương tự trung bình, lớn nhất, nhỏ nhất của của các láng giềng với tác tử đang xét; 𝑑 là khoảng cách giữa hai tác tử theo công thức Manhattan. 3) Tổng hợp lực Chúng ta đã biết các quy tắc để tạo ra lực ở phần trên, cụ thể là dựa vào độ tương tự và khoảng cách không gian giữa hai tác tử. Khi tính toán độ tương tự cho một cặp tác tử chỉ tạo ra một lực độc lập. Sự tương tác giữa hai tác tử đó không thể tạo ra một lực hút/đẩy duy nhất mà phải phụ thuộc vào nhiều lực khác trong không gian. Các lực này sau đó được hợp nhất để tạo ra một lực kết hợp. Hình 2.10. Ví dụ về phản ứng của một tác tử với hai láng giềng Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 41 Hình 2.10 đã cho thấy nguyên tắc của việc tổng hợp lực, tại mỗi tác tử sẽ được mô phỏng phản ứng với một tác tử trong láng giềng. Lực phát sinh từ các phản ứng này được kết hợp để làm phát sinh một lực kết hợp tổng thể. 4) Xác định giá trị dự đoán Sau khi mô hình hoạt động khoảng 300 bước lặp, tác giả nhận thấy lực tác động giữa các tác tử giảm dần về không (0), dẫn đến các tác tử không còn di chuyển nữa, khoảng cách giữa các tác tử trong không gian sẽ không còn thay đổi. Khi đó, mô hình đã đạt đến trạng thái ổn định. Mô hình đề xuất là mô hình tự tổ chức giữa các tác tử trong không gian, cho nên giá trị của độ tương tự đã được thể hiện chính xác trong mô hình. Vì vậy, tác giả sẽ không sử dụng công thức xác định giá trị dự đoán đã nêu ở chương 1 mà sẽ sử dụng cách tính: Lấy giá trị bình chọn của bộ phim gần nhất trong không gian so với bộ phim muốn dự đoán làm kết quả. Kết quả này cũng là căn cứ để đánh giá hệ tư vấn được sử dụng ở bước đánh giá trong Chương 3. 2.3.3. Mô hình tự tổ chức Trong quá trình mô hình này hoạt động, các tác tử sẽ di chuyển dần về vị trí ổn định theo một lộ trình không định trước. Việc di chuyển phụ thuộc vào môi trường xung quanh như thế này là giống với việc tự tổ chức của các thuật toán tự tổ chức (self- organization) trong lĩnh vực máy học. Do đó, kết quả của mô hình này ngẫu nhiên lại là kết quả của một mô hình tự tổ chức. Đó là một kỹ thuật mạnh mẽ và hiện đại. Tuy nhiên, tương tự như mô hình của Cao Hồng Huệ [4], mô hình này phải sử dụng hai cấp độ: cấp độ địa phương và cấp độ toàn cục. Cấp độ địa phương: Các tác tử lựa chọn láng giềng trong một phạm vi nhỏ, cụ thể là các láng giềng có vị trí lân cận. Việc này giống như chia không gian trong môi trường thành từng khu vực riêng để hoạt động độc lập. Lực địa phương được tạo ra từ các tác tử giúp chúng gom cụm thành các nhóm nhỏ nằm rải rác trong không gian. Bởi vì phạm vi láng giềng là nhỏ nên tính chính xác của mô hình là không cao. Do đó, mô hình cần có cấp độ toàn cục để phá vỡ các mối liên hệ ở địa phương, nhằm gom các nhóm nhỏ lại với nhau để tăng độ chuẩn xác cho mô hình. Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 42 Cấp độ toàn cục: Các tác tử lựa chọn láng giềng trong phạm vi lớn, các láng giềng đó có vị trí ngẫu nhiên trong mô hình. Lực sinh ra trong cấp độ này được gọi là lực toàn cục. Kết hợp lực địa phương đã nêu ở trên và lực toàn cục, ta được một lực kết quả mà quy tắc tổng hợp lực ở phần 2.3.2 đã đề cập. Chức năng của hai cấp độ này được thể hiện ở hình 2.11. Hình 2.11. Mô phỏng trên mức độ toàn cục và địa phương Ta rất dễ nhận thấy rằng, ở cấp độ địa phương, các tác tử được phân nhóm thành các nhóm màu khác nhau, nhưng trong đó vẫn tồn tại các nhóm cùng màu nhưng lại xa nhau. Còn ở cấp độ toàn cục, màu trong mô hình đã được sắp xếp theo một trật tự nhất định, các màu giống nhau sẽ có vị trí gần nhau và ngược lại. Hình 2.11 đã mô tả được cách thức hoạt động của một mô hình tự tổ chức điển hình. Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 43 Chương 3 HỆ THỐNG THỬ NGHIỆM TƯ VẤN PHIM SỬ DỤNG MÔ HÌNH ĐA TÁC TỬ HÚT VÀ ĐẨY 3.1. Giới thiệu hệ thống tư vấn 3.1.1. Mô tả bài toán Hệ thống thử nghiệm tư vấn phim sử dụng mô hình đa tác tử hút và đẩy được xây dựng với mục đích đề xuất một hướng tiếp cận mới trong phương pháp tư vấn với bộ dữ liệu mẫu MovieLens. Hệ thống sẽ nhận các dữ liệu đầu vào từ bộ dữ liệu mẫu MovieLens. Các thông tin về Người dùng (user), Bộ phim (item) và đặc biệt là đánh giá của người dùng với từng bộ phim (rate). Khi đó, hệ thống sẽ phân tính, tính toán mối liên hệ giữa các bộ phim (item-based) đồng thời thể hiện mối liên hệ đó lên một không gian hai chiều trực quan để người sử dụng có thể quan sát được. Cuối cùng, hệ thống sẽ tự đánh giá chất lượng của mô hình này thông qua các bộ Test có sẵn trong bộ dữ liệu mẫu MovieLens, từ đó làm căn cứ để đưa ra lời tư vấn cho khách hàng. 3.1.2. Mô tả về bộ dữ liệu MovieLens Nhằm xây dựng thành công mô hình đa tác tử hút và đẩy cho hệ tư vấn, tác giả cần có một cơ sở dữ liệu đủ lớn, đầy đủ thông tin và quan trọng là cần có đánh giá của nguời dùng nên việc tự tạo một cơ sở dữ liệu là khá mất thời gian khó đảm bảo được tính khoa học. Từ đó, tác giả đề xuất việc sử dụng một cơ sở dữ liệu mẫu đã được tổng hợp một cách khoa học và hợp lý, cụ thể trong khóa luận này sẽ sử dụng cơ sở dữ liệu MovieLens nghiên cứu, thu thập dữ liệu về phim của GroupLens. Bộ dữ liệu MovieLens được thu thập bởi GroupLens Research Project tại Đại học Minnesota. GroupLens Research đã thu thập và thực hiện đánh giá tập hợp dữ liệu từ trang web MovieLens ( Các bộ dữ liệu được thu thập qua các thời kỳ khác nhau của thời gian, tùy thuộc vào kích thước của bộ này. Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 44 Có 3 tập dữ liệu MovieLens: - MovieLens 100k – bao gồm 100.000 đánh giá từ gần 1000 người dùng trên gần1700 phim. - MovieLens 1M – bao gồm 1.000.000 đánh giá từ gần 6000 người dùng trên gần 4000 phim. - MovieLens 10M – bao gồm 10.000.000 đánh giá và 100.000 ứng dụng được áp dụng cho gần 10.000 phim bởi gần 72.000 người dùng. Phần nghiên cứu này sẽ sử dụng tập dữ liệu MovieLens 100k bao gồm 100.000 đánh giá (từ 1 – 5) từ 943 người dùng trên 1682 bộ phim. Mỗi người dùng sẽ đánh giá ít nhất 20 bộ phim và cung cấp thông tin nhân khẩu học cơ bản cho người sử dụng (tuổi tác, giới tính, nghề nghiệp...). Các dữ liệu này được thu thập trong khoảng thời gian bảy tháng, kể từ ngày 19 tháng 9 năm 1997 đến ngày 22 tháng 4 năm 1998. Những thông tin này đã được sàng lọc một cách cẩn thận, người dùng có ít hơn 20 xếp hạng hoặc thông tin nhân khẩu học không hoàn chỉnh đã được xóa bỏ. Bộ dữ liệu MovieLens 100k bao gồm: - Tập dữ liệu DATA: là tập hợp dữ liệu bao gồm 100.000 đánh giá từ 943 người dùng trên 1682 bộ phim. Mỗi người dùng đã đánh giá ít nhất 20 bộ phim. Tập dữ liệu bao gồm các trường: UserId | ItemId | Rating | TimeStamp. - Tập dữ liệu INFO: là thông tin về số lượng người dùng, bộ phim và đánh giá trong bộ dữ liệu MovieLens 100k (tập dữ liệu này chỉ để cung cấp thông tin). - Tập dữ liệu ITEM: chứa các thông tin về các bộ phim, bao gồm các trường: MovieId(Id) | MovieTitle(Title) | ReleaseDate | VideoReleaseDate | IMDbURL | Unknow | Action | Adventure | Animation | Children's | Comedy | Crime | Documentary | Drama | Fantasy | Film-Noir | Horror | Musical | Mystery | Romance | Sci-Fi | Thriller | War | Western. 19 trường cuối là các thể loại, giá trị 1 cho thấy phim thuộc thể loại đó, ngược lại là 0, mỗi phim có thể thuộc nhiều thể loại cùng một lúc. Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 45 - Tập dữ liệu GENRE: chứa danh sách các thể loại phim, gồm hai trường: Id | Title. - Tập dữ liệu USER: chứa các thông tin nhân khẩu học của người dùng, bao gồm các trường: UserId(Id) | Name | Age | Gender | Occupation | ZipCode. - Tập dữ liệu OCCUPATION: chứa danh sách các nghề nghiệp của người dùng, bao gồm hai trường: Id | Title. - Năm (5) tập dữ liệu u.base và u.test: Năm bộ dữ liệu u.base và u.test dữ liệu đào tạo và dữ liệu thử nghiệm. Chúng được chia tách từ tập dữ liệu DATA theo tỷ lệ 80%/20% theo phương pháp Cross-Validation. Tập dữ liệu này sẽ được tác giả sử dụng để đánh giá hệ tư vấn. 3.1.3. Ưu, nhược điểm của bộ dữ liệu MovieLens 1) Ưu điểm: Một trong những ưu điểm của bộ dữ liệu MovieLens là hầu như mọi thông tin đều đã được thu thập và sàng lọc một cách kỹ lưỡng, khoa học. Nó đáp ứng số lượng thông tin đủ nhiều để khai thác. Vấn đề đối với người nghiên cứu là họ không thể tự mình tạo một cơ sở dữ liệu với số lượng thông tin đủ lớn để đảm bảo tính khách quan, logic. Họ gặp khó khăn trong việc tạo lập, phân bổ các user cùng với các thông tin đi kèm và càng phức tạp hơn trong việc suy nghĩ, thiết lập thông tin chung giữa các đối tượng sao cho kết quả nhận được hợp lý nhất. Ví dụ điển hình ở đây là làm sao để có thể tạo thông tin ảo cho các USER, ITEM để thông tin ở DATA khoa học nhất khi vấn đề đặt ra là tạo Rating cho mỗi người dùng đối với quá nhiều bộ phim thuộc các thể loại khác nhau. Từ đó, việc sử dụng cơ sở dữ liệu mẫu là cách đơn giản, nhanh chóng đảm bảo tính chính xác về thông tin nhất. 2) Nhược điểm: Bên cạnh những ưu điểm thì bộ dữ liệu mẫu MovieLens cũng tồn tại những nhược điểm của nó. Nhược điểm lớn nhất chính là sự rời rạc, thưa thớt dữ liệu. Với bộ dữ liệu MovieLens, thông tin đưa ra là gần 1700 bộ phim nên khả năng trùng khớp của người dùng là rất ít. Có thể người dùng này sẽ đánh giá 20 phim này, nhưng người dùng khác Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 46 sẽ đánh giá 20 phim khác hoặc là chỉ đánh giá chung một số ít các bộ phim. Điều này khiến cho việc tính hệ số tương quan để xác định người dùng tương tự là rất khó khăn và hầu như mọi trường hợp hệ số tương quan đều trả về giá trị 0. Điều này sẽ gây khó khăn lớn cho việc đánh giá tìm ra tư vấn cho người dùng tiếp theo. 3.2. Ngôn ngữ lập trình Objective-C và thư viện đồ hoạ OpenGL Tiếp theo, tôi sẽ trình bày về hai công cụ được dùng để cài đặt hệ thống, đó là: Ngôn ngữ lập trình Objecive-C và Thư viện đồ họa OpenGL. 3.2.1. Ngôn ngữ lập trình Objective-C Vào đầu những năm 1980, Brad J. Cox đã thiết kế ra ngôn ngữ Objective-C dựa trên ngôn ngữ SmallTalk-80. Có thể hình dung rằng Objective-C là ngôn ngữ lập trình được đặt ở lớp trên của ngôn ngữ lập trình C truyền thống, điều này có nghĩa rằng ngôn ngữ C được bổ sung thêm các thành phần mở rộng (extensions) để hình thành nên một ngôn ngữ lập trình mới đó chính là Objective-C. Ngôn ngữ Objective-C này cho phép chúng ta tạo và quản lý các đối tượng (Objects). Hình 3.1. Ngôn ngữ lập trình Objective-C Từ năm 1988, Công ty NeXT Software nắm giữ bản quyền của ngôn ngữ Objective-C này. Họ đã phát triển các bộ thư viện và cả môi trường phát triển cho nó có tên là NEXTSTEP. Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 47 Năm 1994, NeXT Computer phối hợp với Sun Microsystems chuẩn hóa lại NEXTSTEP trong bản đặc tả tên là OPENSTEP. Bản hiện thực của OPENSTEP chính là GNUStep. Một hệ thống bao gồm cả Linux kenel và môi trường phát triển GNUStep lúc đó được gọi là LinuxSTEP. Đến năm cuối tháng 12 năm 1996, hãng Apple đã mua lại công ty NeXT Software và môi trường NEXTSTEP/OPENSTEP đã trở thành thành phần cột lỗi của hệ điều hành OS X mà Apple giới thiệu sau này. Phiên bản chính thức của môi trường phát triển này do Apple giới thiệu ban đầu có tên là Cocoa. Bằng việc hỗ trợ sẵn ngôn ngữ Objective- C, đồng thời tích hợp một số công cụ phát triển khác như Project Builder (đây chính là tiền thân của Xcode) và Interface Builder, Apple đã tạo ra một môi trường mạnh mẽ để phát triển ứng dụng trên MAC OS X. Đến năm 2007, Apple tung ra bảng nâng cấp cho ngôn ngữ Objective-C và gọi đó là Objective-C 2.0. Cho đến khi Apple chính thức giới thiệu iPhone vào năm 2007, các rất rất nhiều các nhà phát triển mong muốn được tham gia phát triển ứng dụng trên thiết bị mang tính cách mạng về công nghệ này. Ban đầu, Apple không khuyến khích việc tham gia phát triển ứng dụng từ bên thứ ba này mà chỉ cho phép các ứng dụng chạy trên nền web được chạy thông qua ứng dụng dạng trình duyệt Safari mà họ cấy sẵn trong iPhone. Điều này làm cho các ứng dụng khi muốn chạy phải yêu cầu kết nối tới máy chủ web host ứng dụng của các developers tham gia phát triển. Rõ ràng động tác này của Apple không thể đáp ứng nhu cầu của các nhà phát triển cho có rất nhiều hạn chế trong việc phát triển ứng dụng web-based như thế. Ngay sau đó, Apple đã trấn an giới phát triển ứng dụng bằng việc chính thức thông báo rằng các nhà phát triển sẽ có thể phát triển các ứng dụng thuần iPhone. Tức là các ứng dụng nằm trong iPhone và chạy trên hệ điều hành của iPhone giống như các ứng dụng có sẵn của Apple như Contacts, Stocks, Weather,...chạy trên thiết bị đặc biệt này. 3.2.2. Thư viện đồ hoạ OpenGL OpenGL là giao diện phần mềm hướng thủ tục theo chuẩn công nghiệp hỗ trợ đồ hoạ 3 chiều. Được phát triển đầu tiên bởi Silicon Graphic Inc, bao gồm khoảng 250 câu lệnh được hỗ trợ bởi nhiều ngôn ngữ như C, C++, Objective-C, Java,... cho phép người Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 48 lập trình sử dụng tạo ra các đối tượng đồ họa. OpenGL được thiết kế không phụ thuộc vào nền tảng phần cứng cũng như hệ điều hành máy tính (independence of hardware platform and operating system). Với OpenGL ta sẽ tạo ra các mô hình từ các đối tượng hình học cơ bản đó là điểm (point), đường (line) và đa giác (polygon). Cú pháp lệnh của OpenGL: Các câu lệnh của OpenGL đều sử dụng tiền tố gl và các từ tiếp theo được bắt đầu bằng kí tự hoa, ví dụ: glClearColor(). Các hằng được định nghĩa bằng tiền tố GL_ tiếp theo là các từ viết hoa được ngăn cách bằng kí tự gạch dưới, ví dụ GL_COLOR_BUFFER_BIT. Hình 3.2. Thư viện đồ họa OpenGL Các thư viện liên quan của OpenGL: Mặc dù OpenGL là một công cụ mạnh nhưng các đối tượng vẽ đều là các đối tượng hình học cơ bản. Để đơn giản hóa một số công việc, chúng ta được trang bị thêm một số thư viện cho phép sử dụng các thủ tục vẽ ở mức cao hơn: - OpenGL Utility Library (GLU): Bao gồm một số thủ tục thiết lập ma trận xác định hướng nhìn (viewing orientation), ma trận các phép chiếu (projection), và biểu diễn các mặt trong không gian 3 chiều (redering surfaces) - OpenGL Utility Toolkit (GLUT): Là một bộ công cụ được viết bởi Mark Kilgard bao gồm các thủ tục giúp cho đơn giản hóa việc xây dựng các đối tượng hình học. Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 49 Với sự hỗ trợ đa ngôn ngữ và tính phong phú của OpenGL, tác giả đã quyết định chọn thư viện này để mô phỏng hệ thống. 3.3. Cài đặt hệ thống 3.3.1. Các yếu tố đầu vào Hệ thống nhận 2 yếu tố đầu vào sau: Bộ dữ liệu MovieLens: Như đã giới thiệu ở phần 3.1.2, hệ thống sẽ sử dụng bộ dữ liệu mẫu MovieLens để hoạt động. Các file cần thiết là: u.item, u.user, u.base và u.test. Hình ảnh cho các bộ phim: Nghiên cứu của tác giả theo hướng tiếp cận dựa trên sản phẩm (item-based), mỗi bộ phim sẽ là một tác tử hoạt động trong môi trường. Tác giả lấy hình ảnh của chính bộ phim đó để đại diện cho mỗi tác tử trong mô hình. Cách lấy hình ảnh của các bộ phim cũng khá đơn giản. Trong thư mục u.item có lưu đường dẫn đến các bộ phim trên trang web www.us.imdb.com. Tác giả phân tích các đoạn code html trên trang web đó để tải ảnh về. Những bộ phim có thể là do quá cũ nên đã không còn ảnh, thay thế vào đó là một hình màu trắng có viết tên của chính bộ phim lên chính nó. Khi có bộ dữ liệu ảnh của các bộ phim, tác giả nhận thấy rằng dung lượng của chúng khá lớn, khi chạy trong mô hình sẽ làm giảm tốc độ. Vì vậy, trong hệ thống, tác giả chỉ sử dụng ảnh thu nhỏ (thumbnail) của các ảnh trên. Do đó, mô hình đã chạy khá mượt mà và tốc độ tính toán tăng đáng kể. Hình 3.3. Ảnh đại diện của phim / tác tử Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 50 3.3.2. Các yếu tố đầu ra Đầu ra của hệ thống bao gồm: Hình ảnh hoạt động của mô hình: cho người dùng thấy được trực quan hoạt động của mô hình. Dự đoán giá trị bình chọn: giá trị này làm căn cứ để đánh giá hệ tư vấn. Lập danh sách tư vấn: là kết quả để tư vấn cho người dùng. 3.3.3. Quy trình hoạt động Quy trình hoạt động của mô hình đề xuất được mô tả qua hình sau: Hình 3.4. Sơ đồ quy trình hoạt động Trong quy trình trên, mỗi bước lại được phân chia thành các quy trình nhỏ sau: Đọc dữ liệu: - Tạo danh sách Sản phẩm (Item). - Tạo danh sách Người dùng (User). - Tạo lưới quản lý các tác tử trong không gian (Grid). - Thiết lập các tham số cần thiết. Chạy mô hình đa tác tử: - Tính lực địa phương (Lực đối với các láng giềng lân cận). - Tính lực toàn cục (Lực đối với các láng giềng ngẫu nhiên). Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 51 - Di chuyển tác tử Vẽ từng bước kết quả chạy: - Vẽ hình ảnh của các tác tử ở vị trị mới trên mô hình. Tính giá trị dự đoán: - Khi mô hình ổn định, tính giá trị dự đoán để đánh giá hệ tư vấn. Lấy danh sách tư vấn: - Khi mô hình ổn định, lấy danh sách tư vấn cho từng người dùng. 1) Đọc dữ liệu Objective-C là ngôn ngữ lập trình hướng đối tượng, nó cho phép người dùng quản lý các đối tượng thông qua các lớp (class). Trong mô hình này, các bộ phim sẽ được lưu trữ trong danh sách Item còn danh sách User sẽ lưu trữ những người dùng. Đồng thời, mỗi tác tử được xem như là một đối tượng Item, mỗi đối tượng này có các thuộc tính và hành vi đặc trưng sau: - Chuỗi itemID: lưu trữ mã bộ phim. - Mảng arrayUserRate: lưu trữ mảng đánh giá của tất cả người dùng cho đối tượng này. Những người chưa đánh giá thì phần tử đó sẽ có giá trị 0. Vị trí của phần tử trong mảng chính là vị trí của người dùng trong danh sách người dùng. Ví dụ: mảng (3,4,0,5), người dùng thứ nhất đánh giá 3, người dùng thứ hai đánh giá 4, - Đối tượng hình ảnh NSImage: lưu trữ hình ảnh của bộ phim. - Đối tượng Điểm: lưu trữ cặp giá trị x,y của tác tử trong không gian. - Đối tượng Vector Quán tính: lưu trữ quán tính ngẫu nhiên của tác tử. - Hàm move dùng để di chuyển hình ảnh, draw dùng để vẽ hình ảnh. Các đối tượng User cũng được quản lý tương tự như Item, sau đó chúng được lưu vào hai danh sách Item và User riêng biệt. Riêng danh sách User được dùng vào việc dự đoán giá trị bình chọn của người dùng. Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 52 Môi trường có chiều dài và rộng đều bằng một nghìn (1000) pixel. Để thuận tiện trong việc lựa chọn láng giềng, mỗi ô trong mô hình có kích thước là 10x10 cho nên số ô trong mô hình là 100x100 = 1000 ô. Khi mỗi tác tử được khởi tạo hoặc di chuyển, tùy vào vị trí của nó mà lưu trữ tác tử đó vào ô nào trong lưới cho phù hợp. Đó là cách quản lý các tác tử theo lưới một cách đặc biệt mà khóa luận đề xuất. Cách quản lý này ngoài việc thuận tiện theo dõi các hoạt động của các tác tử còn dùng để lấy các láng giềng lân cận và ngẫu nhiên. Cách lấy láng giềng theo lưới sẽ được trình bày ở bước chạy mô hình đa tác tử. Hình 3.5. Cách quản lý trên lưới của mô hình Cuối cùng, các tham số của chương trình cũng sẽ được khởi tạo, có thể kể đến một vài tham số đặc biệt khác như: đếm số lần lặp của mô hình, số láng giềng tối thiểu, số láng giềng tối đa, Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 53 2) Chạy mô hình đa tác tử a) Tính lực địa phương (Lực đối với các láng giềng lân cận)  Chọn láng giềng lân cận Dựa vào cấu trúc lưu trữ theo lưới vừa trình bày ở trên, mỗi tác tử sẽ nằm trong một ô nhất định, vùng láng giềng của tác tử đó chính là các tác tử nằm chung ô và tám (8) ô xung quanh. Thuật toán này có độ phức tạp là O(n2), được thể hiện trong hình 3.6 bên dưới. Hình 3.6. Thuật toán chọn láng giềng lân cận. Ngoài ra, để hạn chế việc tính lại độ tương tự, hệ thống sử dụng cấu trúc dữ liệu từ điển (Dictionary) để lưu các cặp . Ví dụ: tác tử này có độ tương tự với tác tủ khác có id 100 là 0.5 thì tôi sẽ lưu vào Dictionary này cặp giá trị (100,0.5). Đồng thời, mô hình cũng lưu cặp giá trị đó vào láng giềng đang xét. Phương pháp này giúp giảm thiểu số lần tính toán, góp phần đẩy nhanh tốc độ mô hình. Đây cũng chính là biện pháp để tôi khắc phục điểm yếu của mô hình. Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 54  Tính lực địa phương Dựa vào công thức tính lực ở phần 2) mục 2.3.2. Sau khoảng 100 bước lặp sử dụng lực địa phương, mô hình lúc này được mô tả ở hình 3.7. Hình 3.7. Mô hình ở mức độ địa phương Lực địa phương chỉ phân cụm tác tử thành các nhóm nhỏ bị giới hạn về khoảng cách, điều này khiến mô hình chạy chưa chính xác. Khi đó, cần một lực toàn cục để gom các nhóm đó lại với nhau. Phần c) và d) sẽ trình bày phương pháp này. b) Tính lực toàn cục (Lực đối với các láng giềng ngẫu nhiên)  Chọn láng giềng ngẫu nhiên Chọn láng giềng ngẫu nhiên nhằm phục vụ cho việc tính lực toàn cục. Các bước chọn láng giềng ngẫu nhiên cũng giống như chọn láng giềng lân cận, chỉ khác là láng giềng sẽ được chọn ở vị trí ngẫu nhiên trong mô hình mà thôi. Do đó, khóa luận không Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 55 trình bày thuật toán chọn láng giềng ngẫu nhiên nữa. Kết thúc bước này, chúng ta có một danh sách các láng giềng ngẫu nhiển để tiếp tục tính toán.  Tính lực toàn cục Việc tính lực toàn cục không được thực hiện liên tục khi mô hình hoạt động mà chỉ được thực hiện trong một vài vòng lặp dựa vào biến lưu trữ số vòng lặp đã được khởi tạo trước đó. Việc này khiến thời gian mô hình được hội tụ chậm hơn một chút nhưng độ chính xác là tương đối cao bởi vì các tác tử chỉ di chuyển trong khoảng cách ngắn. Hình 3.8. Mô hình ở mức độ toàn cục Hình 3.8 cho thấy các tác tử được kéo về phía trung tâm giống như mô hình của Cao Hồng Huệ [4] và mô hình tự tổ chức. Các tác tử nằm riêng lẻ ở ngoài là do có ít đánh giá về các tác tử này, khiến các tác tử này có độ tương tự ít so với các tác tử còn lại. Vấn đề gặp phải là vấn đề về thưa thớt dữ liệu không thể tránh khỏi. Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 56 c) Di chuyển tác tử Việc di chuyển tác tử thực ra rất đơn giản, chúng ta chỉ cần xác định lại vị trí mới của tác tử thông qua giá trị của biến lưu trữ tọa độ. Hình dung việc di chuyển chúng như làm phim hoạt hình, các con vật di chuyển được là do nhiều bức hình mô tả hoạt động một cách liên tục. Di chuyển tác tử cũng vậy, sự thay đổi liên tục về vị trí với khoảng cách ngắn là nguyên lý của nó. Do đó, lực tác động quá mạnh mà làm thay đổi vị trí quá lớn so với vị trí ban đầu sẽ được tôi làm giảm lực đi để hoàn thành mục tiêu vừa nêu. Thuật toán di chuyển tác tử hay còn gọi là xác định vị trí mới như sau: - Giảm lực quán tính theo thời gian. - Kiểm tra lực địa phương và lực toàn cục, nếu quá lớn thì giảm bớt. Trong mô hình đề xuất, tác giả giảm độ lớn của lực ba (3) lần. - Cộng dồn ba (3) lực vừa nêu vào tọa độ hiện tại của tác tử. - Nếu tác tử đó vượt ra ngoài phạm vi của mô hình thì kéo tác tử đó về lại. Đương nhiên sau khi thay đổi vị trí hiện tại của tác tử, vị trí của nó trong lưới quản lý cũng được thay đổi theo để tiến hành lấy láng giềng lân cận ở lần lặp tiếp theo. 3) Vẽ từng bước kết quả chạy Để vẽ các tác tử lên không gian hai chiều, tác giả sử dụng các hàm sẵn có của thư viện OpenGL. Các bước vẽ có thể tóm gọn trong 3 bước sau: - Lấy đối tượng NSImage có sẵn trong các tác tử. - Gán đối tượng NSImage đó cho hàm GL_TEXTURE_2D của OpenGL. - Lấy tọa độ của tác tử, sau đó dùng hàm GL_TEXTURE_2D để vẽ. 4) Tính giá trị dự đoán Khi mô hình đạt trạng thái ổn định, hệ thống có thể tính giá trị dự đoán cho người dùng. Đối với thuật toán tính giá trị dự đoán, đầu vào của nó là item cần dự đoán của user nào đó và đầu ra là giá trị dự đoán. Khi đó, thuật toán có độ phức tạp là O(n) và được biểu diễn ở hình 3.9. Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 57 Sau khi đã có giá trị dự đoán cho toàn bộ người dùng, tác giả tiến hành tính giá trị sai số tuyệt đối trung bình MAE để đánh giá hệ tư vấn. Kết quả tính giá trị MAE được thực hiện trên toàn bộ năm tập dữ liệu u.base và u.test. Hình 3.9. Thuật toán tính giá trị dự đoán. 5) Lấy danh sách tư vấn Sau khi đã xác định được giá trị dự đoán cho mỗi người dùng, hệ thống chỉ cần lấy những bộ phim có giá trị dự đoán cao nhất mà người dùng đó chưa xem để tư vấn. Danh sách tư vấn cho người dùng được mô tả ở hình 3.10. Hình 3.10. Danh sách tư vấn phim Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 58 3.4. So sánh, đánh giá mô hình đa tác tử hút và đẩy với phương pháp lọc cộng tác Như đã đề cập ở bước tính giá trị dự đoán trong quy trình hoạt động đã nêu ở trên, sau khi dự đoán giá trị bình chọn của người dùng, tác giả tiến hành tính kết quả MAE cho cả năm tập dữ liệu kiểm tra. Kết quả được thể hiện ở hình 3.11. Hình 3.11. Biểu đồ biểu diễn kết quả MAE của 5 bộ dữ liệu kiểm tra Như vậy giá trị trung bình MAE cho cả năm bộ dữ liệu là khoảng 0.724. Điều này nói lên rằng, mô hình đa tác tử hút và đẩy mà tác giả đề xuất đưa ra các giá trị dự đoán có sai số tuyệt đối trung bình là 0.724. Trong khi đó, nghiên cứu [2] đã đưa ra giá trị MAE cho phương pháp lọc cộng tác là 0.723. Hai kết quả của hai phương pháp này gần tương đương nhau, cho thấy lời tư vấn của chúng đều có giá trị như nhau. Ở một góc độ khác, số láng giềng lân cận được chọn ảnh hưởng khá nhiều đến kết quả MAE. Qua nhiều lần thực nghiệm, tác giả nhận thấy rằng, lượng láng giềng được chọn dưới 50 thì giá trị MAE khá cao, còn trên 50 thì giá trị MAE khá ổn định và giảm dần đều sau đó. Điều này được thể hiện ở hình 3.12. Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 59 Hình 3.12. Biểu đồ biểu diễn kết quả MAE của hai phương pháp. Qua hình 3.12. ta nhận thấy rằng, mô hình đề xuất của tác giả ổn định hơn nhiều so với phương pháp lọc cộng tác. Mô hình này mang lại kết quả tốt. Xử lý dữ liệu bị thưa thớt hay dữ liệu có quá ít đánh giá luôn là nhược điểm của phương pháp lọc cộng tác. Việc thưa thớt dữ liệu làm quá trình tính toán của phương pháp này không còn chính xác, dẫn đến kết quả tư vấn không đúng. Đối lập với lọc cộng tác, các bộ phim có số lượng người dùng đánh giá nhiều hay ít đều được thể hiện trực quan trong không gian của mô hình, lời tư vấn vẫn được lấy theo nguyên tắc đã trình bày mà không cần quan tâm đến dữ liệu như thế nào. Tác giả của nghiên cứu [2] cũng thừa nhận rằng: có xảy ra sự thay đổi giá trị MAE lớn và tốc độ tính toán hệ thống chậm khi có thêm một sản phẩm hoặc người dùng. Thật vậy, đối với lọc cộng tác, nếu xuất hiện một đối tượng mới trong hệ thống, nó đều phải đi tính toán lại từ đầu, gây lãng phí tài nguyên và chậm trễ khi đưa ra lời tư vấn. Ngược lại, mô hình mà tác giả đề xuất lại không bị ảnh hưởng tiêu cực bởi sự kiện trên. Trong trường hợp này, tác tử mới xuất hiện sẽ được đưa vào mô hình, tiếp tục thực hiện việc tính toán và di chuyển cho đến khi đến khi nó tìm được vị trí chính xác. Đây chính là ưu điểm lớn nhất của mô hình. Với những ưu điểm kể trên, tác giả tin rằng mô hình này hoàn toàn có thể thay thế cho phương pháp lọc cộng tác trong một thời gian không xa. Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 60 KẾT LUẬN Tóm lại, sau khi hoàn thành đề tài “Nghiên cứu mô hình đa tác tử hút và đẩy cho phương pháp lọc cộng tác”, tác giả đưa ra những kết luận sau: Hệ tư vấn là công cụ phần mềm kỹ thuật cung cấp các mặt hàng đề xuất cho người sử dụng. Những lời tư vấn liên quan đến các khía cạnh khác nhau của quá trình ra quyết định, chẳng hạn như nên mua mặt hàng nào, nên nghe thể loại nhạc nào, hoặc nên đọc loại tin tức nào. Hiện nay, sự quan tâm đối với hệ tư vấn đang rất cao vì sự cần thiết của những ứng dụng có thể giúp người dùng xử lý với tình trạng quá tải thông tin & đưa ra những nội dung hoặc lời khuyên phù hợp cho từng cá nhân. Tuy nhiên, các phương pháp tư vấn hiện tại đã bộc lộ nhiều khuyết điểm như: vấn đề bộ nhớ của tư vấn dựa trên nội dung hay tốc độ tính toán của lọc cộng tác. Khóa luận đã đề xuất mô hình đa tác tử hút và đẩy cho phương pháp lọc cộng tác, hướng tiếp cận dựa trên láng giềng. Các bộ phim mà hệ thống tư vấn là kết quả có được dựa trên phân tích những lựa chọn, đánh giá của hàng trăm người dùng trước đó. Qua quá trình thực nghiệm hệ thống, tác giả nhận thấy rằng mô hình đề xuất đã đáp ứng được yêu cầu của khóa luận. Các giá trị tính toán mang tính thực tiễn cao và hoàn toàn chính xác. Đặc biệt là giải quyết được khuyết điểm của phương pháp lọc cộng tác như: tốc độ tính toán, sự xuất hiện người dùng hoặc sản phẩm mới. Bên cạnh đó, mô hình đã cho người dùng có cái nhìn trực quan về hệ thống đa tác tử, đặc biệt là áp dụng một hệ thống đa tác tử hút và đẩy cho hệ tư vấn phim. Khóa luận mang lại giá trị cao về tính khoa học và thực tiễn để thay thế cho phương pháp lọc cộng tác vốn đã lâu đời. Bên cạnh đó, mô hình vẫn còn một số khuyết điểm như: chưa có sự tương tác với người dùng do đây là mô hình tự tổ chức, chưa kết hợp được với phương pháp tư vấn dựa trên nội dung, chỉ đang hoạt động trên hệ điều hành MacOS, Những khuyết điểm này cũng là hướng phát triển của đề tài trong tương lai, nhằm hoàn thiện mô hình này để áp dụng rộng rãi vào hệ tư vấn. Khoá luận tốt nghiệp Sinh viên thực hiện: Nguyễn Minh Đức 61 DANH MỤC TÀI LIỆU THAM KHẢO [1]. Apple Inc, “OpenGL Programming Guide for Mac”, 2012. [2]. Badrul Sarwar; George Karypis; Joseph Konstan; John Riedl, “Item-Based Collaborative Filtering Recommendation Algorithms”, 2001. [3]. Francesco Ricci; Lior Rokach; Bracha Shapira; Paul B.Kantor, “Recommender Systems Handbook”, 2001. [4]. Hue Cao Hong; Guillaume Chiron; Alain Boucher; “A Multi-Agent Model for Image Browsing and Retrieval”. [5]. Michael Wooldridge, “An introduction to Multiagent Systems”, 2002. [6]. Renault V, “Organisation de Sociétés d'Agents pour la Visualisation d'Informations Dynamiques”, 2001. [7]. Stephen G.Kochan, “Programming in Objective-C 2.0”, 2008.