Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu một số phương pháp tìm kiếm xấp xỉ và xây dựng ứng dụng hỗ trợ lựa chọn phản biện cho Tạp chí Khoa học và Công nghệ Đại học Thái nguyên

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:85

Thêm vào BST

Báo xấu

28
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nội dung chính của luận văn là nghiên cứu một số bài toán lựa chọn phản biện tự động cho Hội nghị khoa học đã được công bố và một số thuật toán tìm kiếm xấp xỉ và ứng dụng giải bài toán hỗ trợ lựa chọn phản biện cho Tạp chí Khoa học. Xây dựng ứng dụng hỗ trợ lựa chọn phản biện bài báo cho Tạp chí Khoa học và Công nghệ Đại học Thái Nguyên. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu một số phương pháp tìm kiếm xấp xỉ và xây dựng ứng dụng hỗ trợ lựa chọn phản biện cho Tạp chí Khoa học và Công nghệ Đại học Thái nguyên

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG TRẦN THÁI SƠN NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP TÌM KIẾM XẤP XỈ VÀ XÂY DỰNG ỨNG DỤNG HỖ TRỢ LỰA CHỌN PHẢN BIỆN CHO TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC THÁI NGUYÊN Chuyên ngành: Khoa học máy tính Mã số: 8480101 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Người hướng dẫn khoa học: TS. NGUYỄN ĐÌNH DŨNG THÁI NGUYÊN, 2018 iii
MỤC LỤC LỜI CẢM ƠN ...................................................................................................... vi LỜI CAM ĐOAN................................................................................................ vii DANH MỤC CÁC BẢNG................................................................................. viii DANH MỤC CÁC HÌNH VẼ.............................................................................. ix LỜI MỞ ĐẦU ...................................................................................................... xi CHƯƠNG 1. TỔNG QUAN ................................................................................. 1 1.1. Tổng quan về hệ thống hỗ trợ lựa chọn phản biện ................................... 1 1.1.1. Thuật toán Kalmukov ......................................................................... 2 1.1.2. Bài toán lựa chọn phản biện CMACRA ............................................... 6 1.1.3. Lựa chọn phản biện với thuật toán xấp xỉ 1/3 ...................................... 9 CHƯƠNG 2. CƠ SỞ LÝ THUYẾT ................................................................... 11 2.1. Một số phương pháp so khớp mẫu trong tính toán độ gần tựa ngữ nghĩa 11 2.1.1. Thuật toán Brute Force ....................................................................... 11 2.1.2. Thuật toán Knuth-Morris-Pratt ........................................................... 12 2.2. Phương pháp quy hoạch động và ứng dụng trong lựa chọn phản biện .... 13 2.2.1. Phương pháp quy hoạch động............................................................. 14 2.2.2. Thuật toán lựa chọn phản biện ............................................................ 16 2.3. Otomat hữu hạn mờ và ứng dụng trong lựa chọn phản biện bài báo........ 20 2.3.1. Độ gần tựa ngữ nghĩa theo mô hình Otomat hữu hạn mờ .................. 20 2.3.2. Thuật toán lựa chọn phản biện ............................................................ 22 CHƯƠNG 3. XÂY DỰNG ỨNG DỤNG........................................................... 25 3.1. Phát biểu bài toán ...................................................................................... 25 3.2. Mô tả yêu cầu hệ thống ............................................................................. 25 3.3. Phân tích hệ thống ..................................................................................... 30 3.3.1. Xác định Actor và Use Case ............................................................... 30 3.3.2. Biểu đồ Use Case ................................................................................ 32 3.3.3. Biểu đồ lớp phân tích ......................................................................... 43 3.3.4. Biểu đồ trạng thái ............................................................................... 44 3.4. Thiết kế hệ thống....................................................................................... 44 3.4.1. Biểu đồ tuần tự .................................................................................... 44 3.4.2. Biểu đồ lớp chi tiết .............................................................................. 53 iv
3.4.3. Các đối tượng cơ sở dữ liệu và các chức năng của chương trình ....... 54 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN .......................................................... 71 TÀI LIỆU THAM KHẢO ................................................................................... 72 v
LỜI CẢM ƠN Luận văn này được hoàn thành tại Trường Đại học Công nghệ Thông tin và Truyền thông dưới sự hướng dẫn của TS. Nguyễn Đình Dũng. Tác giả xin bày tỏ lòng biết ơn tới các thầy cô giáo thuộc Trường Đại học Công nghệ Thông tin và Truyền thông đã tạo điều kiện và giúp đỡ tác giả trong quá trình học tập và làm luận văn tại Trường, đặc biệt tác giả xin bày tỏ lòng biết ơn tới TS. Nguyễn Đình Dũng đã tận tình hướng dẫn và cung cấp nhiều tài liệu cần thiết để tác giả có thể hoàn thành luận văn đúng thời hạn. Xin chân thành cảm ơn anh chị em học viên cao học và bạn bè đồng nghiệp đã trao đổi, động viên và khích lệ tác giả trong quá trình học tập và làm luận văn tại Trường Đại học Công nghệ Thông tin và Truyền thông – Đại học Thái Nguyên. vi
LỜI CAM ĐOAN Tôi xin cam đoan luận văn này do chính tôi thực hiện, dưới sự hướng dẫn khoa học của TS. Nguyễn Đình Dũng, các kết quả lý thuyết được trình bày trong luận văn là sự tổng hợp từ các kết quả đã được công bố và có trích dẫn đầy đủ, Chương trình ứng dụng trong luận văn này được tác giả thực hiện là hoàn toàn trung thực, nếu sai tôi hoàn toàn chịu trách nhiệm. Thái Nguyên, tháng 4 năm 2018 Học viên cao học Trần Thái Sơn vii
DANH MỤC CÁC BẢNG Bảng 1: Các từ khóa của phản biện (ReviewerKeyword).............................................17 Bảng 2. Khoảng cách chuyên môn (ExpertiseDistance)..............................................17 Bảng 3. Bảng RK minh họa thuật toán……………………............................................19 Bảng 4. Kết quả thực hiện thuật toán ………………..................................................19 Bảng 5. Xác định các tác nhân……………….............................................................30 Bảng 6. Xác định các use case ……………….............................................................32 Bảng 7. Scenario cho use case Đăng nhập ………………...........................................33 Bảng 8. Scenario cho use case Cập nhật lý lịch sơ lược ..............................................35 Bảng 9. Scenario cho use case Tổng hợp bài báo theo phản biện................................36 Bảng 10. Scenario cho use case Tổng hợp bài báo theo tác giả……...........................39 Bảng 11. Scenario cho use case Chọn bài báo phản biện.............................................42 Bảng 12. Bảng tblCriticism lưu các thông tin về phản biện.........................................55 Bảng 13. Bảng tblJournal lưu các thông tin về bài báo................................................56 Bảng 14. Bảng tblChuyensan lưu trữ danh mục các chuyên san..................................57 Bảng 15. Bảng tblCri_Journal_and_Book ………………...........................................57 Bảng 16. Bảng tblCri_ProcessOfWork ………............................................................57 Bảng 17. Bảng tblCri_ScientificResearch....................................................................57 Bảng 18. Bảng tblGender lưu thông tin danh mục giới tính.........................................57 Bảng 19. Bảng tblKeywordKHX..................................................................................58 Bảng 20. Bảng tblKeywordNLY..................................................................................58 Bảng 21. Bảng tblKeywordTNK………………..........................................................58 Bảng 22. Bảng tblManageRegist………………..........................................................58 Bảng 23. Bảng tblMenu lưu thông tin danh mục menu trang chủ................................58 Bảng 24. Bảng tblPermission lưu thông tin danh mục phân quyền trong hệ thống....59 Bảng 25. Bảng tblResultOfCriticism ………………………………………………...59 Bảng 26. Bảng tblUser lưu thông tin người sử dụng hệ thống ....................................59 viii
DANH MỤC CÁC HÌNH VẼ Hình 1. Bước 1-Xác định ma trận độ tương tự.............................................................3 Hình 2. Bước 2 – Xây dựng mảng cấu trúc invlovedReviewers; Bước 3 – Xử lý involvedReviewers và phân bài báo cho phản biện tại hàng đầu tiên của ma trận K; Bước 4 – Kết thúc lựa chọn phản biện………...............................................................4 Hình 3. Nhóm Use case Quản trị hệ thống...................................................................32 Hình 4. Use case Đăng nhập.........................................................................................33 Hình 5. Nhóm Use case Quản lý phản biện..................................................................34 Hình 6. Phân rã Use case Cập nhật thông tin phản biện...............................................34 Hình 7. Phân rã Use case Tổng hợp bài báo theo phản biện........................................35 Hình 8. Use case Thống kê và tìm kiếm.......................................................................36 Hình 9. Nhóm Use case Cập nhật bài báo....................................................................37 Hình 10. Phân rã Use case Cập nhật bài báo khoa học tự nhiên..................................37 Hình 11. Phân rã Use case Cập nhật bài báo khoa học Xã hội và Nhân văn................38 Hình 12. Phân rã Use case Cập nhật bài báo Nông Lâm Ngư Y Sinh..........................38 Hình 13. Nhóm Use case Tổng hợp bài báo theo tác giả..............................................39 Hình 14. Use case Đổi mật khẩu...................................................................................40 Hình 15. Use case Đăng ký làm phản biện...................................................................40 Hình 16. Nhóm Use case Tìm kiếm phản biện.............................................................41 Hình 17. Phân rã Use case chọn bài báo phản biện......................................................41 Hình 18. Nhóm Use case Chỉ định phản biện...............................................................42 Hình 19. Biểu đồ lớp phân tích.....................................................................................43 Hình 20. Biểu đồ trạng thái lớp Journal........................................................................44 Hình 21. Biểu đồ tuần tự cho chức năng đăng nhập.....................................................44 Hình 22. Biểu đồ tuần tự cho chức năng tìm kiếm phản biện theo từng từ khóa.........45 Hình 23. Biểu đồ tuần tự cho chức năng tìm kiếm phản biện theo dãy từ khóa...........46 Hình 24. Biểu đồ tuần tự cho chức năng Chọn bài báo................................................47 Hình 25. Biểu đồ tuần tự cho chức năng Cập nhật lý lịch sơ lược...............................48 Hình 26. Biểu đồ tuần tự cho chức năng Cập nhật từ khóa chuyên môn.....................49 ix
Hình 27. Biểu đồ tuần tự cho chức năng đổi mật khẩu.................................................50 Hình 28. Biểu đồ tuần tự cho chức năng Thêm bài báo...............................................50 Hình 29. Biểu đồ tuần tự cho chức năng Chỉ định phản biện 1....................................51 Hình 30. Biểu đồ tuần tự cho chức năng Chỉ định phản biện 2....................................52 Hình 31. Biểu đồ lớp chi tiết.........................................................................................53 Hình 32. Sơ đồ thực thể liên kết...................................................................................59 Hình 33. Các chức năng hệ thống hỗ trợ lựa chọn phản biện.......................................60 Hình 34. Form Đăng nhập hệ thống.............................................................................61 Hình 35. Form Chức năng tìm kiếm phản biện............................................................61 Hình 36. Form Đăng nhập lại hệ thống........................................................................62 Hình 37. Form Đổi mật khẩu........................................................................................62 Hình 38. Form Chức năng cập nhật thành viên............................................................63 Hình 39. Form Chức năng quản lý đăng ký phản biện.................................................63 Hình 40. Form Xem thông tin đăng ký tham gia phản biện.........................................64 Hình 41. Form Cập nhật lý lịch của phản biện.............................................................64 Hình 42. Form Cập nhật quá trình đào tạo...................................................................65 Hình 43. Form Cập nhật quá trình công tác.................................................................65 Hình 44. Form Cập nhật đề tài nghiên cứu khoa học...................................................66 Hình 45. Form Cập nhật công trình khoa học đã công bố............................................66 Hình 46. Form Cập nhật các từ khóa chuyên môn.......................................................67 Hình 47. Form Tổng hợp bài báo theo phản biện.........................................................67 Hình 48. Form Cập nhật bài báo...................................................................................68 Hình 49. Form Thống kê bài báo theo các tiêu chí.......................................................68 Hình 50. Form Tổng hợp bài báo theo tác giả..............................................................69 Hình 51. Form Chức năng xem hồ sơ của phản biện....................................................69 x
LỜI MỞ ĐẦU Trong thời đại ngày nay, cùng với các phương pháp về chế độ tài chính, chính sách nhân sự, công nghệ thông tin (CNTT) được xác định là một trong các yếu tố quan trọng của một tạp chí. Ứng dụng CNTT trong hoạt động tạp chí có thể hiểu là việc nghiên cứu, phát triển, đầu tư đưa các công nghệ tiên tiến trong lĩnh vực CNTT vào ứng dụng thực tiễn trong các công đoạn của quá trình hoạt động của tạp chí, từ khâu nhận bài, phản biện, biên tập và xuất bản. Các hoạt động chủ yếu gồm thiết lập một chiến lược tổng thể về phát triển CNTT, các quy chế, quy trình quản lý, xây dựng hạ tầng phần cứng, đường truyền, cơ sở dữ liệu, phần mềm ứng dụng. Hiện nay đã có một số tạp chí như Tạp chí Khoa học và Công nghệ Đại học Đà Nẵng [26], Tạp chí Khoa học kỹ thuật Mỏ - Điạ chất [27]… đã có giải pháp ứng dụng công nghệ thông tin và hệ thống tiện ích của Internet, tự động hóa một số bước trong quy trình quản lý tạp chí. Nội dung chính của giải pháp là xây dựng hệ thống website tự động hóa các khâu quản lý tạp chí như: quá trình nộp bài của tác giả, mời đọc phản biện, theo dõi quá trình xử lý một công trình từ khi gửi đăng cho đến lúc bài được nhận đăng vào các số của tập chí. Việc nghiên cứu xây dựng hệ thống phần mềm website tạp chí khoa học đã từng bước hiện đại hóa quá trình quản lý trong thời kỳ hội nhập quốc tế, tạo môi trường trao đổi giữa các nhà khoa học và tận dụng tối đa nguồn tài liệu quý. Để đạt được và giữ vững các tiêu chí cơ bản của một tạp chí khoa học quốc tế, hiện nay một số các tạp chí quốc tế được xếp hạng bởi ISI ngoài việc đảm bảo phát hành đều đặn, liên tục, đúng thời hạn theo kế hoạch thì tạp chí còn phải tuân thủ các điều kiện chặt chẽ khác như quá trình biên tập, về nội dung bài, quá trình xét duyệt, hình thức xét duyệt. Muốn vậy, việc tác nghiệp của những tạp chí này chủ yếu phải thực hiện qua mạng, qua hệ thống phần mềm, vì qua hệ thống này các công ước biên tập quốc tế được lưu giữ trong hệ thống cơ sở dữ liệu (nội dung bài báo, tác giả và tài liệu tham khảo được trích dẫn), Ban biên tập là ban biên tập quốc tế gồm các nhà khoa học tiêu biểu cho các hướng chính của tạp chí có thể trao đổi tác nghiệp một cách hiệu quả; bài gửi đăng được tiếp nhận và xử lý theo đúng thông lệ quốc tế, được phản biện kín, độc lập và khách quan. xi
Nhằm nâng cao hiệu quả của việc tiếp nhận, chọn lọc và phản biện, hiện nay một số hội nghị trong nước và quốc tế đã đăng ký sử dụng dịch vụ quản lý và tổ chức hội nghị khoa học của phần mềm Easychair [28], đây là một phần mềm được đặt tại máy chủ của Khoa Khoa học máy tính thuộc Đại học Manchester. Việc nộp báo cáo của các thành viên đều nộp qua mạng tại trang đó. Quá trình lấy bài, nhận xét và cho kết quả phản biện của các thành viên trong Ban chương trình đều thực hiện trực tuyến thông qua phần mềm. Việc cho điểm bài báo được các phản biện thực hiện khách quan theo các tiêu chí và kèm theo nhận xét. Trao đổi thông tin giữa tác giả bài báo và thành viên trong Ban chương trình hay giữa các thành viên trong Ban chương trình đều thực hiện bằng email thông qua sự quản lý của hệ thống Easychair. Đối với kết quả phản biện, những tác giả có bài được chấp nhận sẽ nhận được bản nhận xét và yêu cầu chỉnh sửa, bài đã chỉnh sửa cũng sẽ được gửi lại thông qua phần mềm và cuối cùng là hệ thống sẽ tự động lập danh sách mục lục tác giả, bài được tuyển chọn phục vụ cho việc in ấn. Tạp chí Khoa học và Công nghệ Đại học Thái Nguyên thành lập theo quyết định số 1571/QĐ-BGD&ĐT ngày 31 tháng 3 năm 2006 của Bộ trưởng Bộ Giáo dục và Đào tạo; Giấy phép hoạt động báo chí số 149/GP-BVHTT ngày 17 tháng 04 năm 2001 do Bộ Văn hóa Thông tin cấp và Giấy phép sửa đổi, bổ sung số 1270/GP-BTTTT ngày 26 tháng 8 năm 2010 do Bộ Thông tin và Truyền thông cấp với mục đích công bố các công trình nghiên cứu khoa học và công nghệ của cán bộ, sinh viên Đại học Thái Nguyên, của các nhà khoa học trong và ngoài nước; các thông tin về những kết quả nghiên cứu và hoạt động khoa học công nghệ nổi bật của các đơn vị thành viên thuộc Đại học Thái Nguyên. Sau hơn 10 năm hoạt động, Tạp chí đã góp một phần không nhỏ trong việc quảng bá, nâng cao vị thế của Đại học Thái Nguyên trong lĩnh vực hoạt động khoa học công nghệ, số lượng bài gửi đăng ngày càng lớn, chất lượng bài ngày càng đòi hỏi được nâng cao. Để tiệm cận với chuẩn quốc tế, Tạp chí Khoa học và Công nghệ Đại học Thái Nguyên cần tập trung nâng cao chất lượng các chuyên san, xử lý linh hoạt và cải tiến hơn nữa trong quy trình phản biện, biên tập; nâng cao điểm số công trình của bài báo; quảng bá rộng rãi hơn nữa các công trình nghiên cứu của tác giả trên mạng. Đề tài luận văn ” Nghiên cứu một số phương pháp tìm kiếm xấp xỉ và xây dựng ứng dụng hỗ trợ lựa chọn phản biện cho tạp chí khoa học và công nghệ Đại học Thái Nguyên” tập trung nghiên cứu và thực hiện 2 nội dung chính sau: xii
1. Nghiên cứu một số bài toán lựa chọn phản biện tự động cho Hội nghị khoa học đã được công bố và một số thuật toán tìm kiếm xấp xỉ và ứng dụng giải bài toán hỗ trợ lựa chọn phản biện cho Tạp chí Khoa học. 2. Xây dựng ứng dụng hỗ trợ lựa chọn phản biện bài báo cho Tạp chí Khoa học và Công nghệ Đại học Thái Nguyên. Các kết quả đạt được trong luận văn này là kết quả trong quá trình học tập và nghiên cứu của tác giả tại Trường Đại học Công nghệ Thông tin và Truyền thông. Ngoài phần mở đầu, kết luận và tài liệu tham khảo, nội dung luận văn được trình bày thành 3 chương. Chương 1 trình bày các vấn đề tổng quan về hệ thống lựa chọn phản biện cho Hội nghị, tạp chí. Chương 2 trình bày các thuật toán so khớp mẫu và một phương pháp tìm kiếm xấp xỉ hỗ trợ lựa chọn phản biện. Chương 3 là các kết quả đạt được trong quá trình phân tích và thiết kế hệ thống và xây dựng ứng dụng hỗ trợ lựa chọn phản biện bài báo cho Tạp chí Khoa học và Công nghệ Đại học Thái Nguyên. xiii
CHƯƠNG 1. TỔNG QUAN 1.1. Tổng quan về hệ thống hỗ trợ lựa chọn phản biện Việc chọn ra người phản biện có cùng hướng nghiên cứu với nội dung bài báo từ cơ sở dữ liệu các nhà khoa học đảm bảo tính chất khách quan, đúng vấn đề cần phản biện là điều hết sức cần thiết đối với một tạp chí, hội nghị khoa học. Muốn vậy, việc phân loại và chọn phản biện cần phải dựa vào nội dung bài báo, hay phần tóm tắt bài báo hoặc các từ khóa cho mỗi bài báo… Điều này thực sự hết sức khó khăn cho việc tìm kiếm phản biện trong cơ sở dữ liệu các nhà khoa học nếu thực hiện thủ công và thay vào đó ta cần có thuật toán hữu hiệu cho việc lựa chọn phản biện. Bài toán lựa chọn phản biện bài báo cho tạp chí hay hội nghị không phải là bái toán mới, hiện nay đã có rất nhiều tác giả đã nghiên cứu tìm lời giải cho bài toán trên nhiều góc độ khác nhau, với các cách tiếp cận khác nhau. Một số cách tiếp cận như: Phương pháp của Chumki Basu và cộng sự đề xuất khi chọn tập bài báo phù hợp với phản biện có sử dụng kết hợp các kỹ thuật thu thập thông tin và cơ sở dữ liệu bằng cách khai thác các nguồn thông tin từ web [4]; phương pháp chỉ mục ngữ nghĩa ẩn [5]; phương pháp mô hình hóa chủ đề xác suất [6], phương pháp quy hoạch nguyên tuyến tính lựa chọn tập người phản biện cho tập bài báo có xét đến các điều kiện ràng buộc [7]; phương pháp luồng chi phí tối thiểu [8] và cách tiếp cận mô hình lai ghép tri thức trong lựa chọn phản biện, đánh giá thẩm định cho các dự án nghiên cứu [9]. Gần đây, Tayal, Saxena, Sharma, Khanna và Gupta đưa ra một phương pháp mới giải bài toán lựa chọn phản biện trong chính sách tài chính của chính phủ [10]; Li và Watanabe đưa ra phương pháp tự động lựa chọn phản biện cho bài báo dựa trên mức độ chuyên môn của phản biện [11]; Long, Wong, Peng, và Ye đã đưa ra thuật toán xấp xỉ 1/3 nhằm giải bài toán cực đại hóa sự bao phủ chủ đề chuyên môn trong lựa chọn phản biện [12], theo cách tiếp cận này mỗi bài báo sẽ được lựa chọn phản biện sao cho các chủ đề của bài báo sẽ được phủ hoàn toàn (mức độ phủ là lớn nhất) bởi chuyên môn của các nhà phản biện và thỏa mãn 3 điều kiện: (1) mỗi bài báo được phản biện bởi một hay nhiều phản biện ở trong trạng thái “sẵn sàng”; (2) mỗi phản biện sẽ phản biện số lượng bài báo không lớn hơn số lượng bài quy định; (3) Không có sự xung đột giữa người phản biện và tác giả, điều này có nghĩa là không xảy ra trường hợp tác giả hoặc đồng tác giả lại đóng vai trò là người tham gia phản biện. Sau đây chúng tôi trình bày chi tiết một số phương 1
pháp tìm lời giải cho bài toán lựa chọn phản biện. 1.1.1. Thuật toán Kalmukov Thuật toán lựa chọn phản biện cho bài báo dựa trên từ khóa được thiết kế bởi Yordan Kalmukov năm 2006 [19], theo cách tiếp cận này thì giữa bài báo và phản biện có chung với nhau ít nhất một từ khóa thì bài báo sẽ được đưa vào phản biện; từ khóa bài báo và từ khóa của phản biện sẽ được chọn trong tập từ khóa cho trước; mỗi người phản biện sẽ có số lượng bài báo cần phản biện không được vượt quá giới hạn cho phép. Ngoài ra, khi lựa chọn phản biện thuật toán phải đảm bảo tính phân phối đều về số lượng bài báo được phân cho các phản biện và được xác định bởi (1). Noppr= ceil((Nop * Norpp) / Nor); (1) Noppr: Số lượng bài báo được phân cho một người phản biện; Nop: Số lượng bài báo; Norpp: Số lượng người phản biện cho một bài báo; Nor: Số người phản biện; ceil: Hàm làm tròn trên. Thuật toán lựa chọn phản biện phù hợp nhất cho mỗi bài báo dựa trên độ tương tự và được xác định như sau: Ta ký hiệu SF(Pi,Rj) là hàm xác định độ tương tự của bài báo Pi với phản biện Rj và được xác định bởi công thức (2) count( KWPi  KWR j ) SF ( Pi , R j )  (2) count( KWPi  KWR j ) KWPi: Tập các từ khóa của bài báo Pi; KWRj: Tập các từ khóa của phản biện Rj; count(S): Số lượng phần tử trong tập S. KWP  KU ; KWR  KU i j KU: là tập các từ khóa được xác định bởi hội nghị; Như vậy, công thức (2) cho thấy SF ( Pi , R j )  [0,1] là đại lượng chỉ ra mức độ phù hợp của bài báo và phản biện và là đại lượng để xác định Pi có thể được phân cho phản biện Rj hay không. Để rõ hơn các khái niệm này, ta xét một ví dụ cụ thể như sau: Trong một hội nghị khoa học, tập các từ khóa được xác định là KU = {A, B, C, D, E, F, G, H, I}; một bài báo có các từ khóa là KWP = {A, C, F}; xét 2 phản biện lần lượt có tập các từ khóa là KWR1 = {B, C, F, G}; KWR2 = {A, F}. Xét trực quan ta dễ thấy khả năng chuyên môn phản biện của R1 và R2 cho bài báo P là tương đương nhau, vì họ đều có cùng số lượng từ khóa thuộc vào KWP. Trong trường hợp này, để tìm 2
được phản biện phù hợp nhất ta phải sử dụng đến hàm xác định độ tương tự SF(Pi,Rj) và ta có SF(P,R1) = 2/5 < SF(P,R2) = 2/3. Vậy, từ hàm tương tự ta thấy bài báo P sẽ được phân cho phản biện R2 là phù hợp hơn. Xét về mặt ý nghĩa thì việc phân bài báo P cho phản biện R2 sẽ tiết kiệm được tài nguyên khi quan tâm tới giới hạn tối đa số bài báo cho mỗi phản biện, vì count(KWR1)> count(KWR2), nên khả năng phản biện cho bài báo khác của R1 là lớn hơn R2, hơn nữa nếu có một bài báo kế tiếp là P1 có KWP1 = {B, G } cũng cần được phản biện và giả thiết mỗi phản biện chỉ phản biện tối đa là 01 bài báo. Khi đó, nếu ta phân P cho phản biện R1 thì khi đó bài báo P1 sẽ không có người phản biện mặc dù R1 có chung 2 từ khóa với P1 (vì R1 đã bận phản biện cho P). Vậy P được phản biện bởi R2 là phù hợp nhất. Ta gọi, PS và RS lần lượt là các bản ghi thông tin về bài báo và người phản biện và có cấu trúc như sau: Thuật toán lựa chọn phản biện gồm 4 bước chính như sau: Bước 1: Xây dựng ma trận độ tương tự K. Trong bước này, mỗi bài báo Pi sẽ được tính độ tương tự với tất cả các phản biện Rj ta thu được K[i]={ SF(Pi,Rj)}. Sau đó sắp xếp K[i] theo thứ tự giảm dần của độ tương tự khi đó phản biện phù hợp nhất sẽ nằm trên đầu danh sách. Hình 1. Bước 1-Xác định ma trận độ tương tự Chuyển sang các bước sau, thuật toán xử lý hàng đầu tiên của ma trận, đó là hàng gợi ý chọn phản biện phù hợp nhất. Lưu đồ sau chỉ ra quá trình thực hiện thuật 3
toán: Hình 2. Bước 2 – Xây dựng mảng cấu trúc invlovedReviewers; Bước 3 – Xử lý involvedReviewers và phân bài báo cho phản biện tại hàng đầu tiên của ma trận K; Bước 4 – Kết thúc lựa chọn phản biện. Tại Bước 2, thuật toán xây dựng mảng cấu trúc involvedReviewers nhằm khắc phục hạn chế đối với những phản biện có số lượng bài báo vượt quá giới hạn cho phép, 4
cấu trúc được xác định như sau: involvedReviewers[‘revUsername’][index][k_pid];[SFactor] revUsername: Username của phản biện; Sfactor: Độ tương tự bài báo và phản biện Ví dụ: ta có bảng K là involvedReviewers[‘R1’][1][k_pid]=2; [SFactor]=0.54 Độ tương tự lưu trong involvedReviewers được xác định bao gồm hằng số C, mục đích của đại lượng C là để xác định và đảm bảo rằng nếu giữa bài báo và phản biện có chung nhau ít nhất một từ khóa thì bài báo sẽ được phân cho phản biện đó (đối với phản biện phù hợp nhất và có số lượng bài báo không vượt quá số lượng bài báo cho phép). Đại lượng C được chia làm 2 phần, C= C1+C2. C1 được xác định như sau: If (number of non-zero SFs == 0){ C1 = max; (4) } else if (number of non-zero SFs > 2*(revsPerPaper – numberOfRevs for Pi)){ C1 = 0; (5) } else{ revsPerPaper  numberOf Re vs for Pi C1  ; (6) (nuber of non  zeroSFs) 3 } Trong đó, number of non-zero SFs là số lượng các đại lượng đo độ tương tự khác không đối với bài báo Pi; revsPerPaper số người phản biện cho mỗi bài báo, số lượng này được xác định bởi hội nghị, thường chọn là 2 hoặc 3; numberOfRevs for Pi là số người phản biện hiện thời được làm phản biện cho bài báo Pi. Nếu người phản biện tại hàng đầu tiên của K[i] là phản biện duy nhất trong hàng thì phản biện này (R) sẽ được gán cho bài báo Pi mà không cần quan tâm đến độ 5
tương tự của R với các bài báo khác. Nếu không có phản biện nào phù hợp với Pi (độ tương tự bằng 0 trong K[i]) thì C1=0. Đại lượng C2 đảm bảo rằng bài báo được gán cho phản biện thứ 2 là phản biện có mức độ phù hợp thứ 2, C2 được xác định như sau: C2 = 2 * (SF of first-suitable reviewer for Pi – SF of second-suitable reviewer for Pi) SF of first-suitable reviewer for Pi: Độ tương tự của phản biện thứ nhất đối với Pi; SF of second-suitable reviewer for Pi: Độ tương tự của phản biện thứ 2 đối với Pi. Trong quá trình thực hiện tại bước 3, thuật toán xác định bài báo sẽ được gán cho phản biện nào trong hàng đầu tiên của ma trận K. Có thể minh họa cho bước này bằng một ví dụ sau: Nếu các điều kiện ràng buộc giới hạn đặt ra là mỗi phản biện được phản biện tối đa là 2 bài báo, mỗi bài báo sẽ được phản biện bởi 2 người phản biện thì sau khi thực hiện bước 2 ta được kết quả là Sắp xếp lại involvedReviewers[‘R1’] theo thứ tự giảm dần của độ tương tự ta được involvedReviewers[‘R1’]={P2, P5, P4, P1}. Vì số lượng tối đa cho mỗi phản biện là 2 bài báo, nên P2 và P5 sẽ được gán cho R1, quá trình thực hiện tiếp tục tại bước này và các bước sau được mô tả chi tiết trong Hình 2. Trong trường hợp số lượng bài báo tối đa cho mỗi phản biện là khác nhau (phụ thuộc vào chuyên môn và các điều kiện của phản biện) và số lượng phản biện gán cho mỗi bài báo là khác nhau cũng đã được Maryam Karimzadehgan, ChengXiang Zhai [7] đề xuất và đưa ra thuật toán tìm lời giải cho bài toán này. 1.1.2. Bài toán lựa chọn phản biện CMACRA Năm 2009, Maryam Karimzadehgan và ChengXiang Zhai [7] mở rộng bài toán của Yordan Kalmukov và đề xuất 2 thuật toán giải bài toán CMACRA (ConstrainedMulti-Aspect Committee Review Assignment) bao gồm thuật toán Greedy và thuật toán quy hoạch nguyên tuyến tính. 6
Bài toán CMACRA đặt ra là lựa chọn phản biện cho tập các bài báo sao cho thỏa mãn 4 điều kiện sau: (1) Mỗi bài báo sẽ được phản biện bởi ít nhất một phản biện luôn trong trạng thái “sẵn sàng”; (2) Số lượng bài báo cho mỗi phản biện không vượt quá giới hạn cho phép; (3) Mỗi phản biện được gán cho mỗi bài báo phải có chuyên môn phù hợp với bài báo; (4) Chuyên môn tổng hợp của các phản biện phải phủ đủ tốt cho toàn bộ các chủ đề của bài báo đề cập. Để giải quyết các vấn đề của bài toán đặt ra, CMACRA được mô hình hóa như sau: Gọi P={p1, p2,…,pn} là tập các bài báo pi; R={r1, r2,…,rm} - tập các phản biện ri; NR={NR1, NR2,…, NRm} – tập các giới hạn số lượng bài báo cho mỗi phản biện, NRi là số lượng bài báo tối đa cho phản biện ri; NP={NP1, NP2,…, NPm} – tập các số lượng phản biện sẽ được gán cho mỗi bài báo, NPi là số lượng phản biện được gán cho bài báo Pi. Kết quả tính toán sẽ cho ra một ma trận M={Mi,j}nxm, trong đó Mij  {0,1} (Mi,j=1 nếu ri là phản biện cho bài báo pj). Các điều kiện ràng buộc (1) và (2) có thể được mô tả như sau: n i  1, m,  M i , j  NRi ; (7) j 1 m j  1, n,  M i , j  NPj . (8) i 1 Để đảm bảo đủ số lượng phản biện để phản biện cho các chủ đề của tất cả các n n bài báo thì cần phải đảm bảo điều kiện  NP   NR j 1 j i 1 i . Giả sử trong một hội nghị có k chủ đề khác nhau, ta ký hiệu   { 1 , 2 , ...,  k } là tập các chủ đề,  i là ký hiệu chủ đề thứ i (mỗi chủ đề có thể được đặc trưng như là một từ khóa mà đặc trưng chuyên môn của phản biện hay chủ đề bài báo đề cập sẽ được lựa chọn trong tập này). Gọi P và R lần lượt là 2 ma trận chỉ mức độ tương tự của các chủ đề với nội dung bài báo và độ tương tự của các chủ đề với chuyên môn phản biện; P  {Pi , j }nk , Pi , j là mức độ tương tự của chủ đề  j với bài báo pi; R  {Ri , j }mk , Ri , j là mức độ tương tự của chủ đề  j với chuyên môn của phản biện ri; mức độ tương tự Pi , j , Ri , j  {0,1} . 7
Thuật toán Greedy giải bài toán gán phản biện cho bài báo được thực hiện như sau: Bước 1: Sắp xếp các bài báo theo thứ tự giảm dần về số lượng chủ đề mà bài báo đề cập (Số lượng từ khóa của bài báo). Bước 2: Chọn phản biện có mức độ chuyên môn phù hợp nhất cho bài báo đứng đầu danh sách (phản biện có chuyên môn phủ các chủ đề bài báo đề cập). Bước 3: Kiểm tra các ràng buộc: giới hạn về số lượng bài báo cho phản biện, giới hạn về số lượng phản biện cho mỗi bài báo. Nếu đạt được giới hạn về số lượng bài báo cho phản biện thì loại bỏ phản biện ra khỏi danh sách, làm tương tự như vậy đối với bài báo nếu đạt được giới hạn về số lượng phản biện cho mỗi bài báo. Bước 4: Lặp lại bước 2 cho đến khi các phản biện được gán cho tất cả các bài báo. Thuật toán thứ 2 mà Maryam Karimzadehgan sử dụng để tìm lời giải cho bài toán CMACRA là thuật toán quy hoạch tuyến tính nguyên. Để sử dụng thuật toán này, bài toán CMACRA được mô hình hóa như sau: Nếu coi ti,j là số lượng phản biện có chuyên môn phủ chủ đề  j của bài báo pi, thì bài toán đặt ra là tìm ti,j sao cho n k  t i 1 j 1 i, j  max ; (9) t i , j  [0, NPi ] ; (10) và thỏa mãn điều kiện m i  1,2,..., n; j  1,2,..., k ; Pi , j t i , j   Rl , j M l ,i (11) l 1 Vậy, từ (9), (10), (11) kết hợp với các điều kiện (7), (8) ta có thể phát biểu bài toán CMACRA như sau: Tìm tìm ti,j sao cho n k  t i 1 j 1 i, j  max và thỏa mãn các điều kiện 8
C1 : i  [1, m], j  [1, n], M i , j  {0,1} C 2 : i  [1, n], j  [1, k ], t i , j  {0,1,..., NPi } m C 3 : j  [1, n],  M i , j  NPj i 1 n C 4 : i  [1, m],  M i , j  NRi j 1 m C 5 : i  [1, n], j  [1, k ], Pi , j t i , j   Rl , j M l ,i l 1 1.1.3. Lựa chọn phản biện với thuật toán xấp xỉ 1/3 Tiếp tục mở rộng các kết quả của Maryam Karimzadehgan, năm 2013, Cheng Long và cộng sự [12] đã xét bài toán khi bổ sung các ràng buộc xung đột giữa tác giả và phản biện (COI-conﬂict of interest) đồng thời đưa ra thuật toán xấp xỉ 1/3 giải bài toán lựa chọn phản biện đảm bảo cực đại hóa phủ chủ đề. Các ràng buộc COI được xét đến ở đây gồm một số dạng như: phản biện được lựa chọn và tác giả bài báo lại là đồng tác giả cho một số bài báo; mối quan hệ đồng nghiệp; mối quan hệ là thầy trò, tác giả bài báo là thầy hướng dẫn của người phản biện….Có thể nói bổ sung ràng buộc COI đảm bảo cho quá trình lựa chọn phản biện thực sự có tính khách quan nhằm nâng cao chất lượng phản biện cho hội nghị. Bài toán mà Cheng Long đưa ra được gọi là bài toán MaxTC-PRA (Maximum Topic Coverage Paper- Reviewer Assignment), bài toán đặt ra là lựa chọn phản biện cho bài báo sao cho tổng số các chủ đề khác nhau của bài báo được phủ bởi chuyên môn của các phản biện là cực đại và thảo mãn 3 điều kiện: Mỗi bài báo phải được phản biện bởi  p phản biện; Mỗi phản biện phản biện không quá  r bài báo; thỏa mãn ràng buộc COI giữa tác giả bài báo và phản biện được chọn. Bài toán MaxTC-PRA được mô hình hóa như sau: Gọi P={p1, p2,…,pn} là tập các bài báo pi; R={r1, r2,…,rm} - tập các phản biện ri; T={t1, t2,…,tk} - tập các chủ đề; mỗi bài báo pi được đặc trưng bởi các chủ đề trong miền T, ký hiệu là T(pi); mỗi phản biện rj được đặc trưng bởi các chủ đề trong miền T, ký hiệu là T(rj); M=(pi, rj) là một phép gán (lựa chọn) bài báo pi với phản biện rj (rj phản biện cho bài báo pi, M.p=pi, M.r=rj); A  P x R là tập tất cả các phép gán, A(pi)={M: M  A, M.p=pi}, A(rj)= {M: M  A, M.r=rj};  i (A) là số lượng các chủ đề của bài báo pi. Như vậy Bài toán MaxTC-PRA được phát biểu như sau: Tìm tập các phép gán A sao cho 9