Ứng dụng và cải tiến hệ số tương đồng cosine trong xây dựng và quản lý ngân hàng câu hỏi trắc nghiệm

Để hiểu rõ cách tính, hãy xét ví dụ tính độ và chỉ phù hợp với tài liệu dài. Với các tài liệu 
tương đồng của 2 tài liệu A, B sau: khác nhau hoàn toàn thì SimHash vẫn thường 
 cho giá trị khoảng 0.5 trong khi kết quả mong 
DocA: “Ba Một Năm” - “315” 
 đợi phải là 0. 
DocB: “Một Hai Ba Một Hai Một Một” - 
 Để thấy rõ hơn độ chính xác của SimHash 
“1231211” 
 và Cosine xét ví dụ sau: 
Các bước thực hiện 
 Trường hợp 1: Hai đoạn văn ngắn và 
Bước 1 – Biểu diễn tài liệu thành vector tần khác nhau hoàn toàn: 
suất của các shingle V1 = “Hai đoạn văn bất kỳ” 
 Tạp Chí Khoa Học Giáo Dục Kỹ Thuật Số 53 (07/2019) 
 20 Trường Đại Học Sư Phạm Kỹ Thuật TP. Hồ Chí Minh 
V2 = “Có nội dung khác nhau” Câu 2: Trên Internet, phần mềm của người 
Trường hợp 2: Hai đoạn văn gần giống nhau: dùng sử dụng cổng đích nào để kết nối đến 
 mày chủ POP3? 
V3 = “Mặt trời mọc ở phía đông” 
 A) 80 
V4 = “Mặt trời lặn ở phía tây” 
 B) 110 
 Bảng 1. So sánh SimHash và Cosine 
 C) 25 
 SimHash Cosine Chú thích 
 D) 404 
 Trường 0.508 0.0 Simhash 
 hợp 1 cho kết quả Với cách tính thông thường 2 câu hỏi này 
 (V1,V2) sai có hệ số tương đồng Cosine = 0.95. 
 Trường 0.766 0.667 Tương tự, xét 2 câu hỏi khác thuộc ngân 
 hợp 2 hàng câu hỏi môn “Nhập môn hệ điều hành” 
 (V3,V4) 
 Câu 3: Trên hệ điều hành Linux đĩa cứng 
 Theo kết quả từ bảng 1, SimHash đã cho được ký hiệu là had, hdbvà primary 
kết quả sai trong trường hợp 1. Hai tài liệu nói partition trên đĩa cứng được đánh số là 
trên khác nhau hoàn toàn nhưng SimHash vẫn A) 1 
cho kết quả là 0.508 trong khi Cosine cho kết 
quả đúng là 0.0. B) 1 đến 4 
4. CẢI TIẾN PHƯƠNG PHÁP TÍNH C) 5 trở lên 
 HỆ SỐ TƯƠNG ĐỒNG COSINE D) Tất cả đều sai 
 Khác với các văn bản thông thường, trong Câu 4: Trên hệ điều hành Linux đĩa cứng 
ngân hàng câu hỏi, các câu hỏi thường có nội được ký hiệu là had, hdbvà extended 
dung ngắn và đặc biệt nhiều câu hỏi có nội partition trên đĩa cứng được đánh số là 
dung tương tự nhau về mặt từ vựng. Trong 
thực tế đề thi bao gồm nhiều phần. Mỗi phần A) 1 
có các câu hỏi thuộc cùng một chương (phần) B) 1 đến 4 
và các câu hỏi này thường có nội dung khá 
 C) 5 trở lên 
giống nhau. Khi ứng dụng hệ số tương đồng 
Cosine với giá trị ngưỡng từ 0.9-0.95 để kiểm D) Tất cả đều sai 
tra nội dung các câu hỏi trong ngân hàng có bị Hệ số tương đồng Cosine của 2 câu hỏi 
trùng lặp (đã tồn tại) hay không thì cả 8/8 bộ này (câu 3 và câu 4) là 0.978. Nếu theo kết 
ngân hàng câu hỏi đều phát hiện có sự trùng quả tính hệ số tương đồng Cosine có thể kết 
lặp tuy nhiên khi kiểm tra lại bằng phương luận 2 cặp câu hỏi trên giống nhau nhưng thực 
pháp thủ công thì không tìm thấy sự trùng lặp. tế đây là các câu hỏi khác nhau hoàn toàn. 
 Hãy xem xét 2 câu hỏi (cặp câu hỏi cùng Trong cặp câu hỏi (1,2) người ra đề đang nói 
chủ đề) được trích từ ngân hàng câu hỏi môn tới cổng kết nối của 2 giao thức khác nhau là 
học “Mạng máy tính cơ bản” sau: SMTP và POP3, và trong cặp câu hỏi (3,4) 
 người ra đề muốn nói tới phân vùng chính 
Câu 1: Trên Internet, phần mềm của người 
 (primary partition) và phân vùng mở rộng 
dùng sử dụng cổng đích nào để kết nối đến 
 (extended partition) khi chia ổ đĩa cứng. 
mày chủ SMTP? 
 Mặc dù hệ số tương đồng Cosine đủ tốt 
 A) 80 
 và được áp phổ biến trong các ứng dụng khai 
 B) 110 thác văn bản, nhưng chưa hoàn toàn phù hợp 
 C) 25 cho bài toán ngân hàng câu hỏi do số từ trong 
 câu hỏi ít và một số câu hỏi có rất nhiều từ 
 D) 404 giống nhau. Để cải thiện độ chính xác, trong 
 Tạp Chí Khoa Học Giáo Dục Kỹ Thuật Số 53 (07/2019) 
 Trường Đại Học Sư Phạm Kỹ Thuật TP. Hồ Chí Minh 21 
tài liệu [11] nhóm tác giả đã đề xuất “Khoảng Bước 2 - Chuẩn hóa Vector trọng số cho tất cả 
cách tương đồng Cosine có trọng số” các từ thuộc A  B. Trọng số mặc định cho tất 
(Distance Weighted Cosine Similarity) nhưng cả các shingle bằng 1: 
thực chất đây là kết hợp 2 phương pháp đo: 
 VectorW = {(“1”,5), (“2”,1), (“3”,1), 
Hamming Distance và Cosine Similarity, do 
 (“5”,1)} 
đó vẫn chưa thể hiện được chủ ý của người ra 
đề. Vì vậy chúng tôi đề xuất cải tiến giải thuật Bước 3. Tính hệ sô tương đồng Cosine cải 
tính hệ số tương đồng Cosine để phục vụ cho tiến theo công thức (2) 
mục đích này. 
 Weighted Cosine A , B , W 
4.1 Phương pháp đánh trọng số cho hệ số 
 2 2 22 2 2 2 2
 tương đồng Cosine 145******** 021145******** 111 101 021 111 101
 Với mỗi câu hỏi trong đề thi người biên 22222222 22222222
 15011111*********22222222 45211101 22222222
soạn có thể định nghĩa các từ khóa chính (nếu 15011111********* 45211101 
cần) cùng trọng số tương ứng thể hiện dụng ý 
 101 101
của mình. Từ đó biểu diễn thành vector mức 0.966 0.966
độ quan trọng (Vector of Shingle Importance) 27* 40527* 405
của các shingle trong tài liệu. Mặc định các 
shingle có trọng số là 1. Các từ chính sẽ có 4.1.2 Trường hợp 2 - có một tài liệu không 
trọng số >1. chứa từ khóa 
 Giả sử vector trọng số của các shingle Giả sử từ khóa “2” có mức độ quan trọng 
trong tập hợp các shingle phân biệt của tài liệu bằng 5. Từ khóa này không có trong DocA 
A và B là W. Hệ số tương đồng Cosine có trọng nhưng có trong DocB. 
số sẽ được tính theo công thức đề xuất sau: Bước 1 – Tạo Vector trọng số do người dùng 
Weighted Cosine (A,B,W) = định nghĩa 
 n
 A*B*W 2 VectorU = {(“2”,5)} 
 i 1 i i i
 (2) 
 nn Bước 2 - Chuẩn hóa Vector trọng số cho tất cả 
 A*W*B*W2 2 2 2
 ii 11i i i i các từ thuộc A  B. Trọng số mặc định cho tất 
 cả các shingle bằng 1: 
 Trong đó: 
 VectorW={(“1”,1), (“2”,5), (“3”,1), (“5”,1)} 
 Ai và Bi là các phần tử thứ i trong vector Bước 3. Tính hệ sô tương đồng Cosine cải 
 A và B của 2 tài liệu DocA và DocB tiến theo công thức (2) 
 W là phần tử thứ i trong vector trọng số 
 i Weighted Cosine A , B , W 
 của tài liệu A 
 2 2 2 2
Xét lại ví dụ trình bày trong mục 3: 141******** 025 2 111 101 2 2 2
 141******** 025 111 101
 22222222 22222222
 DocA: “3 1 5” 11051111*********22222222 41251101 22222222 
 11051111********* 41251101 
 DocB: “1 2 3 1 2 1 1” 
 5
 5 0.267
4.1.1 Trường hợp 1- từ khóa nằm trong cả 3* 117 0.267
 hai tài liệu 3* 117
 Giả sử từ khóa “1” có mức độ quan trọng Như vậy nếu hai văn bản càng có cùng 
bằng 5 nhiều từ khóa quan trọng thì càng giống nhau 
 có nghĩa là hệ số tương đồng càng gần bằng 
Bước 1 – Tạo Vector trọng số do người dùng 
 1.0, ngược lại nếu văn bản không chứa từ 
định nghĩa 
 khóa quan trọng thì càng khác nhau nghĩa là 
VectorU = {(“1”,5)} hệ số tương đồng càng gần về 0.0 
 Tạp Chí Khoa Học Giáo Dục Kỹ Thuật Số 53 (07/2019) 
 22 Trường Đại Học Sư Phạm Kỹ Thuật TP. Hồ Chí Minh 
 Bảng 2. So sánh hệ số tương đồng Cosine và 5. ỨNG DỤNG HỆ SỐ TƯƠNG ĐỒNG 
 Cosine có trọng số COSINE VÀ HỆ SỐ TƯƠNG ĐỒNG 
 Cosine Weighted Cosine Weighted Cosine COSINE CẢI TIẾN TRONG XÂY 
 DỰNG NGÂN HÀNG CÂU HỎI 
 Trường hợp 1 Trường hợp 2 
 TRẮC NGHIỆM 
 0.6299 0.966 0.267 
 Hệ số tương đồng Cosine và hệ số tương 
 Áp dụng phương pháp tính hệ số Cosine đồng Cosine cải tiến được ứng dụng để xây 
cải tiến cho 2 cặp câu hỏi ví dụ nói trên: dựng phần mềm quản lý ngân hàng câu hỏi thi 
 trắc nghiệm trong 3 chức năng chính: 
Câu hỏi 1: CH1 = “Trên Internet, phần mềm 
của người dùng sử dụng cổng đích nào để kết 1. Tạo ngân hàng câu hỏi từ các đề thi trắc 
nối đến mày chủ SMTP? . . . ” nghiệm cũ có sẵn 
VectorWCH1 = {(“cổng đích”,5), 2. Thêm câu hỏi mới vào ngân hàng câu hỏi 
 (“SMTP”,10)} 3. Đánh giá, kiểm tra đề thi sau khi phát sinh 
Câu hỏi 2: CH2 = “Trên Internet, phần mềm Các bước thực hiện: 
của người dùng sử dụng cổng đích nào để kết 
nối đến mày chủ POP3? . . .” Bước 1: Dùng hệ số tương đồng cosine 
 với ngưỡng 0.9 để tạo ngân hàng câu hỏi từ 
VectorWCH2 = {(“cổng đích”,5), các đề thi có sẵn hoặc khi thêm câu hỏi mới 
 (“POP3”,10)} vào ngân hàng. Nếu hệ số tương đồng của câu 
Câu hỏi 3: CH3 = “Trên hệ điều hành Linux hỏi thêm vào so với tất cả các câu hỏi trong 
đĩa cứng được ký hiệu là had, hdbvà ngân hàng nhỏ hơn ngưỡng (<0.9) câu hỏi 
primary partition trên đĩa cứng được đánh số mới sẽ tự động được thêm vào ngân hàng. 
là ... “ Bước 2: Trong trường hợp câu hỏi mới 
VectorWCH3 = {(“hệ điều hành Linux”, 5), có hệ số tương đồng so với tất cả các câu hỏi 
(“đĩa cứng”, 5), (“primary partition”, 10)} trong ngân hàng lớn hơn hoặc bằng ngưỡng 
 (>=0.9) sẽ được kiểm tra bằng tay và định 
Câu hỏi 4: CH4 = “Trên hệ điều hành Linux nghĩa thêm các từ khóa quan trọng (theo mục 
đĩa cứng được ký hiệu là had, hdbvà 4 – hệ số tương đồng Cosine cải tiến) 
extended partition trên đĩa cứng được đánh số 
là ...” Bước 3: Các đề thi sau khi được phát 
 sinh dùng hệ số tương đồng Cosine cải tiến 
VectorWCH4 = {(“hệ điều hành Linux”,5), với ngưỡng 0.95 để kiểm tra đảm bảo không 
(“đĩa cứng”,5), (“extended partition”,10)} có trùng lặp 
 Bảng 3. So sánh hệ số tương đồng Cosine và Kết quả áp dụng phương pháp trên cho 
 Cosine cải tiến 100 câu hỏi của ngân hàng câu hỏi môn 
 Không Có trọng số Dụng ý “Mạng máy tính cơ bản” như sau: 
 trọng số - Bước 1: Với ngưỡng tương đồng 0.90 
 (CH1, 0.542 Khác có 35 câu hỏi tương tự nhau và được chia 
 0.950 
 CH2) (khác hơn) nhau thành 3 nhóm với số lượng câu hỏi trong mỗi 
 nhóm lần lượt là: 19, 9, 7; Với ngưỡng tương 
 (CH3, 0.776 Khác 
 0.977 đồng 0.95 chỉ còn 24 câu hỏi tương tự nhau và 
 CH4) (khác hơn) nhau được chia thành 4 nhóm với số lượng câu hỏi 
 trong mỗi nhóm lần lượt là: 5, 8, 6, 5 
 Kết quả bảng trên (bảng 2 và 3) cho thấy 
phương pháp tính hệ số Cosine cải tiến làm - Bước 2 và 3: Sau khi áp dụng phương 
gia tăng sự khác biệt hay tương đồng theo pháp đánh trọng số cho 24 câu hỏi trong 4 
đúng dụng ý của người dùng. nhóm, số lượng câu hỏi tương đồng là 0. 
 Tạp Chí Khoa Học Giáo Dục Kỹ Thuật Số 53 (07/2019) 
 Trường Đại Học Sư Phạm Kỹ Thuật TP. Hồ Chí Minh 23 
 Áp dụng tương tự với 80 câu hỏi trong xác hai đoạn văn tương tự nhau về ngữ nghĩa 
ngân hàng câu hỏi môn “Nhập môn hệ điều nhưng khác nhau về từ vực, hay trường hợp 
hành”. Với ngưỡng tương đồng 0.90 và 0.95 ngược lại hai văn bản rất giống nhau về từ vực 
chỉ có 6 câu hỏi tương tự nhau và được chia (hệ số Cosine lớn) nhưng lại rất khác nhau về 
thành 2 nhóm với số lượng câu hỏi trong mỗi dụng ý (ví dụ 2 cặp câu hỏi nói trên). Nói cách 
nhóm lần lượt là: 4, 2. Sau khi áp dụng khác khi sử dụng hệ số tương đồng Cosine sẽ 
phương pháp đánh trọng số cho 6 câu hỏi này rất khó thể hiện được đúng dụng ý của tác giả, 
số lượng câu hỏi tương đồng là 0 mà điều này đặc biệt quan trọng trong việc xác 
 định trùng lặp các câu hỏi trong ngân hàng câu 
 hỏi, khi các câu hỏi thuộc cùng nhóm chủ đề 
 rất tương tự nhau, đôi khi chỉ khác nhau một 
 vài từ khóa. Với cải tiến công thức tính hệ số 
 tương đồng Cosine áp dụng phương pháp 
 đánh trọng số từ khóa sử dụng trong xây dựng 
 ngân hàng hỏi thi trắc nghiệm các nhược điểm 
 nói trên đã được khắc phục, đặc biệt đảm bảo 
 việc thêm câu hỏi mới vào trong ngân hàng 
 câu hỏi không bị trùng lặp nội dung. 
 Theo công thức tính hệ số Cosine cải tiến 
 (2) thì tác động của trọng số đến kết quả phụ 
 Hình 3. Các nhóm câu hỏi tương đồng môn thuộc vào cả giá trị của các trọng số cao hay 
 Mạng máy tính thấp và cả vào độ lớn của tài liệu (số chiều hay 
 kích thước của vector tần suất). Với trường 
 hợp vector tần suất có kích thước nhỏ thì việc 
 tăng giảm giá trị các trọng số có ảnh hướng 
 lớn tới kết quả. Ngược lại, với vector tần suất 
 rất lớn thì việc tăng giảm giá trị các trọng số 
 lại chỉ có ảnh hướng nhỏ tới kết quả. Vì vậy 
 tùy vào các trường hợp cụ thể có thể linh hoạt 
 sử dụng phương pháp đánh trọng số bằng giá 
 trị tuyệt đối như các ví dụ ở trên hay tương đối 
 dùng tỷ lệ phần trăm. 
 Do các câu hỏi trong ngân hàng câu hỏi 
 thường ngắn (kích thước vector tần suất nhỏ) 
 Hình 4. Các nhóm câu hỏi tương đồng môn và dễ dàng xác định được các từ khóa quan 
 Nhập môn hệ điều hành trọng nên khuyến nghị sử dụng phương pháp 
 đánh trọng số tuyệt đối với giá trị các trọng số 
 Bằng phương pháp đánh trọng số các từ giao động từ 3 đến 10. Sau thử nghiệm trên 
quan trọng trong tính hệ số Cosine cải tiến các bộ ngân hàng câu hỏi thuộc bộ môn mạng 
giúp xác định chính xác hơn, phân biệt rõ hơn máy tính và truyền thông xin đề xuất các từ 
sự tương đồng hay khác biệt của hai văn bản khóa dùng để nhận diện các câu hỏi chung có 
theo dụng ý của người dùng, đồng thời làm trọng số là 5, trong đó các từ khóa đặc trưng 
giảm ảnh hưởng của yếu tố từ vựng giúp độ riêng cho các câu hỏi cùng nhóm là 10. Ngoài 
chính xác tiến gần hơn về mặt ngữ nghĩa. ra có thể kết hợp tính độ tương đồng 2 cấp độ 
6. KẾT LUẬN VÀ KIẾN NGHỊ sử dụng hệ số Cosine cải tiến có trọng số để 
 xác định không trùng lặp sau đó dùng hệ số 
 Hệ số tương đồng Cosine được tính dựa Cosine thông thường để tự động phân loại 
vào tần số xuất hiện của các shingle duy nhất nhóm câu hỏi cùng chủ đề. 
trong tài liệu, do vậy sẽ không đánh giá chính 
 Tạp Chí Khoa Học Giáo Dục Kỹ Thuật Số 53 (07/2019) 
 24 Trường Đại Học Sư Phạm Kỹ Thuật TP. Hồ Chí Minh 
 TÀI LIỆU THAM KHẢO 
[1] Yildirim M., Heuristic optimization methods for generating test from a question bank, 
 Advances in Artificial Intelligence, pp. 1218-1229 (2007). 
[2] Yildirim M., A genetic algorithm for generating test from a question bank, Computer 
 Applications in Engineering Education, Vol.18, No. 2, pp. 298 – 305 (2010). 
[3] Toan Bui, Tram Nguyen, Bay Vo, Thanh Nguyen, Witold Pedrycz, Václav Snásel: 
 Application of Particle Swarm Optimization to Create Multiple-Choice Tests. J. Inf. Sci. 
 Eng. 34(6): 1405-1423 (2018). 
[4] Anand Rajaraman, Jure Leskovec,and Jeffrey D. Ullman,Mining of Massive Datasets, 
 Cambridge University Press, 2014 
[5] Felix Naumann, Melanie Herschel, An Introduction to Duplicate Detection, Morgan & 
 Claypool, 2010 
[6] Lavanya Pamulaparty, C.V Guru Rao, M. Sreenivasa Rao, A NEAR-DUPLICATE 
 DETECTION ALGORITHM TO FACILITATE DOCUMENT CLUSTERING, 
 International Journal of Data Mining & Knowledge Management Process (IJDKP) Vol.4, 
 No.6, November 2014 
[7] Wael H. Gomaa, Aly A. Fahmy, A Survey of Text Similarity Approaches, International 
 Journal of Computer Applications (0975 – 8887) Volume 68 – No.13, April 2013 
[8] Anshumali Shrivastava,Ping Li, In Defense of MinHash Over SimHash, Artificial 
 Intelligence and Statistics pp. 886-894 (2014) 
[9] Henzinger Monika, Finding near-duplicate web pages: a large-scale evaluation of 
 algorithms, Proceedings of the 29th Annual International ACM SIGIR Conference on 
 Research and Development in Information Retrieval, 2006 
[10] Pratap Dangeti, Statistics for Machine Learning, Packt Publishing, 2017 
[11] Li, Baoli: Distance Weighted Cosine Similarity Measure for Text Classification. In 
 IDEAL 2013 proceedings. 10.1007/978-3-642-41278-3_74, 2013 
Tác giả chịu trách nhiệm bài viết: 
Phạm Văn Tính 
Trường Đại học Nông Lâm TP. HCM 
Email: pvtinh@hcmuaf.edu.vn