XÂY DỰNG MỘT HỆ THỐNG HỎI ĐÁP TỰ ĐỘNG PHỤC VỤ TƯ VẤN GHI DANH TRỰC TUYẾN
NGUYỄN THỊ THU TRANG
Trang nhan đề
Lời cảm ơn
Mục lục
Danh mục
Mở đầu
Chương 1: Tổng quan về hỏi-đáp tự động
Chương 2: Các phương pháp phân tích câu hỏi và tìm kiếm thông tin trong hệ thống hỏi đáp
Chương 3: Giải pháp và thử nghiệm hệ thống hỏi-đáp tự động phục vụ tư vấn ghi danh trực tuyến
Chương 4: Kết luận và hướng phát triển
Tài liệu tham khảo
Phụ lục
Mục lục
MỞ ĐẦU 1
Chương 1. TỔNG QUAN VỀ HỆ THỐNG HỎI-ĐÁP TỰ ĐỘNG .4
1.1 Hệ thống hỏi-đáp tự động .4
1.2 Sơ lược lịch sử phát triển 5
1.3 Kiến trúc hệ thống hỏi-đáp 7
1.3.1 Giao diện người dùng (User Interface) .9
1.3.2 Phân tích câu hỏi (Question Analyzer) .9
1.3.3 Tìm kiếm dữ liệu (Data Retrieval) 10
1.3.4 Rút trích câu trả lời (Answer Extraction) .11
1.3.5 Chiến lược xếp hạng (Ranking) 11
1.3.6 Xác minh câu trả lời (Answer Verification) .12
1.4 Một số vấn đề quan tâm khi xây dựng hệ thống hỏi đáp .12
1.5 Hệ thống hỏi-đáp tiếng Việt 13
Chương 2. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÂU HỎI VÀ TÌM KIẾM THÔNG TIN TRONG HỆ THỐNG HỎI ĐÁP .15
2.1 Phương pháp phân tích câu hỏi 15
2.1.1 Phương pháp nông (Shallow Method) .16
2.1.2 Phương pháp sâu (Deep Method) .16
2.2 Vấn đề phân tích câu hỏi trong ngôn ngữ tiếng Việt .17
2.3 Tìm kiếm thông tin .18
2.4 Mô hình không gian vector (Vector Space Model) 19
2.4.1 Phương pháp trọng số tf-idf 20
2.4.2 Xác định độ tương tự giữa hai tài liệu 20
2.4.3 Hạn chế của mô hình vector .21
2.4.4 Chuẩn hóa trọng số tf-idf 21
2.5 Phương pháp gom cụm dữ liệu .21
2.5.1 Thuật toán K-Means .23
2.5.2 Thuật toán HAC 25
Chương 3. GIẢI PHÁP VÀ THỬ NGHIỆM HỆ THỐNG HỎI-ĐÁP TỰ ĐỘNG PHỤC VỤ TƯ VẤN GHI DANH TRỰC TUYẾN .27
3.1 Mục tiêu .28
3.2 Giải pháp .29
3.2.1 Giai đoạn phân tích truy vấn .30
3.2.2 Giai đoạn so khớp câu hỏi 32
3.2.3 Giai đoạn so khớp câu trả lời 33
3.2.4 Xây dựng bộ dữ liệu thử nghiệm 34
3.3 Chương trình cài đặt .39
3.4 Thử nghiệm 40
3.4.1 Mục tiêu thử nghiệm .40
3.4.2 Kế hoạch thử nghiệm 41
3.4.3 Kết quả thử nghiệm 42
Chương 4. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN .51
4.1 Kết luận .51
4.2 Hướng phát triển của luận văn .52
TÀI LIỆU THAM KHẢO 53
PHỤ LỤC .56
23 trang |
Chia sẻ: maiphuongtl | Lượt xem: 2157 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Luận văn Xây dựng một hệ thống hỏi đáp tự động phục vụ tư vấn ghi danh trực tuyến, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Trang 28
HỎI-ĐÁP TỰ ĐỘNG PHỤC VỤ TƯ VẤN GHI
DANH TRỰC TUYẾN
Chương này chúng tôi trình bày mục tiêu, giải pháp, kế họach thử nghiệm và
kết quả thử nghiệm hệ thống hỏi-đáp tự động phục vụ tư vấn ghi danh trực tuyến.
3.1 Mục tiêu
Mục tiêu của luận văn là xây dựng hệ thống hỏi-đáp tự động phục vụ cho một
miền xác định đó là tư vấn ghi danh trực tuyến. Tư vấn ghi danh trực tuyến có các
đặc điểm riêng (đề cập trong chương mở đầu) nên cần những phương pháp giải
quyết riêng. Mục tiêu của chúng tôi là xây dựng được một hệ thống hỏi-đáp tiếng
Việt phục vụ tư vấn ghi danh trực tuyến với kết quả chấp nhận được. Chấp nhận
được ở đây có nghĩa là người hỏi chấp nhận các kết quả hệ thống đưa ra là một kết
quả tương đối chính xác hoặc chấp nhận các câu trả lời của hệ thống như một gợi ý
trả lời có liên quan về mặt ngữ nghĩa với câu hỏi.
Các câu hỏi và câu trả lời trong tư vấn ghi danh trực tuyến mang những đặc
điểm riêng, đó là ở dưới dạng văn bản tự do, không theo một loại câu hỏi nhất định
nào, cũng không theo một chủ đề nhất định nào cả. Do đó, một phần hết sức quan
trọng trong hệ thống này là phân tích câu hỏi như thế nào để lấy được thông tin
nhiều nhất khi mà câu hỏi không hề có một cấu trúc nhất định nào cả. Hầu hết các
hệ thống hỏi-đáp truyền thống đều chỉ trả lời cho các câu hỏi thuộc về một loại câu
hỏi nào đó. Do đó, phương pháp mà chúng tôi chọn thử nghiệm cho hệ thống tư vấn
ghi danh trực tuyến là phương pháp dựa trên từ khóa, trích từ khóa và đánh trọng số
cho các từ khóa trong văn bản để tìm kiếm câu trả lời. Ngoài ra, nhằm cải thiện hiệu
quả hệ thống, giảm không gian tìm kiếm, trước khi tìm kiếm, các cặp hỏi-đáp được
phân thành các cụm gồm các câu hỏi tương tự nhau.
Chúng tôi tiến hành thử nghiệm các phương pháp đề xuất, cải thiện hiệu quả
hệ thống trên mỗi bước phù hợp với dữ liệu của lĩnh vực tư vấn ghi danh trực tuyến.
Trang 29
Do chưa có một hệ thống hỏi-đáp tiếng Việt nào tương tự nên không thể so sánh
hiệu quả của hệ thống với một hệ thống tiếng Việt khác, nên chúng tôi thử nghiệm,
so sánh, đánh giá kết quả bằng cách thử nghiệm nhiều phương pháp cho hệ thống
nhằm thu được kết quả tốt hơn.
Giải pháp, kế họach thử nghiệm được trình bày chi tiết trong các phần bên
dưới.
3.2 Giải pháp
Kiến trúc hệ thống hỏi-đáp (chương 1) gồm có 3 phần chính yếu nhất là phân
tích câu hỏi, tìm kiếm văn bản chứa câu trả lời và rút trích câu trả lời từ trong các
văn bản tìm được. Hệ thống hỏi-đáp phục vụ cho tư vấn ghi danh trực tuyến có đặc
thù riêng, không cần rút trích câu trả lời nên chúng tôi đề xuất mô hình được biểu
thị trong hình 3-1. Hệ thống này được chia thành 3 giai đoạn chính:
- Giai đoạn phân tích truy vấn
- Giai đoạn so khớp câu hỏi
- Giai đoạn so khớp câu trả lời
Trong giai đoạn phân tích truy vấn (câu hỏi mới), câu truy vấn được đưa vào
hệ thống sẽ được tách câu, tách từ, loại bỏ các hư từ và loại bỏ các cụm từ xuất hiện
nhiều nhưng không có ý nghĩa, để còn lại các từ cần thiết (từ khóa) cho việc tìm
kiếm câu trả lời.
Ở giai đoạn so khớp câu hỏi, các từ khóa thu được trong giai đoạn trước sẽ
được sử dụng để xây dựng vector đặc trưng truy vấn, sau đó xác định các cụm chứa
các câu hỏi tương tự nhất với truy vấn. Vector truy vấn sẽ được so khớp với tất cả
các vector câu hỏi trong các cụm đó theo độ đo tương tự cosin. Các giá trị tương tự
này được xếp hạng, và hệ thống chọn ra nQ câu hỏi có giá trị tương tự cao nhất đưa
vào giai đoạn tiếp theo.
nQ câu hỏi này được chuyển sang giai đoạn so khớp câu trả lời để tìm nQ câu
trả lời tương ứng. Trong giai đoạn này, vector truy vấn sẽ được so khớp với vector
Trang 30
của các câu trả lời tìm được. Một chiến lược xếp hạng được sử dụng để tìm ra nA
câu trả lời tốt nhất.
Hình 3-1: Kiến trúc hệ thống hỏi-đáp phục vụ tư vấn ghi danh online
3.2.1 Giai đoạn phân tích truy vấn
Đây là giai đọan quan trọng nhất trong các hệ thống hỏi-đáp, với mục tiêu là
xác định thông tin cần thiết trong câu hỏi để đưa vào giai đọan tiếp theo. Thông tin
này thu được dựa trên các từ ngữ quan trọng có trong câu hỏi. Vì vậy, mục tiêu của
giai đọan này là xác định các từ khóa (các từ có ý nghĩa trong câu hỏi).
Trang 31
- Tách từ
Việc đầu tiên trước khi xác định từ khóa là phân đoạn câu hỏi thành các từ,
cụm từ, hay còn gọi là tách từ. Như đã đề cập trong chương 2, ngôn ngữ tiếng Việt
rất đa dạng và phong phú, việc xác định ranh giới giữa các câu, các từ tương đối
phức tạp và không có một phương pháp nào là tối ưu cho tất cả các trường hợp. Các
nghiên cứu về tách câu, tách từ tiếng Việt đã có nhiều nhóm tham gia phát triển,
chúng tôi chọn sử dụng công cụ tách từ, tách câu có kết quả chấp nhận được. Và
trong phần thử nghiệm hệ thống, chúng tôi sử dụng bộ công cụ tách từ của [12].
- Trích từ khóa
Truy vấn sau khi tách từ sẽ được loại bỏ bớt các cụm từ không cần thiết, giữ
lại những thông tin quan trọng nhất làm đầu vào cho các giai đoạn sau này. Ngoài
các hư từ là những từ không có ý nghĩa đối với hệ thống, thì trong hệ thống diễn
đàn tư vấn ghi danh trực tuyến có rất nhiều cụm từ xuất hiện trong câu hỏi, nhưng
lại thật sự không có vai trò gì trong việc tìm kiếm câu trả lời, ví dụ: “cảm ơn”,
“xin”, “cho biết”, “thông cảm”…Chính vì lý do này nên chúng tôi tìm cách xây
dựng danh sách các cụm từ xuất hiện nhiều nhưng không có ý nghĩa trong diễn đàn
một cách tự động. Tuy nhiên trong quá trình thử nghiệm với nhiều cách đánh giá
mức độ quan trọng của cụm từ khác nhau, việc xây dựng danh sách này một cách tự
động là không khả quan nên chúng tôi đã xây dựng danh sách này một cách thủ
công. Phần trích từ khóa này, chúng tôi sử dụng bộ từ điển hư từ do nhóm [12] xây
dựng. Từ điển hư từ này bao gồm 795 mục từ. Danh sách các cụm từ xuất hiện
nhiều nhưng không có ý nghĩa với diễn đàn tư vấn chúng tôi xây dựng gồm có 52
mục từ.
Danh mục các hư từ và cụm từ xuất hiện nhiều trong diễn đàn được trình bày
trong phần phụ lục.
Trang 32
3.2.2 Giai đoạn so khớp câu hỏi
Các từ khóa thu được sau giai đoạn phân tích truy vấn sẽ được chuyển vào giai
đoạn này để tìm kiếm các câu trả lời tương tự trong kho dữ liệu.
- Xây dựng vector truy vấn
Có rất nhiều phương pháp tìm kiếm thông tin khác nhau, chúng tôi lựa chọn
phương pháp tìm kiếm phổ biến nhất dựa trên mô hình không gian vector (vector
space model) (chương 2). Trong mô hình này, tài liệu văn bản được xây dựng
vector đặc trưng của văn bản đó, việc so khớp văn bản dựa trên độ đo tương tự giữa
2 vector, cụ thể là độ đo cosin. Sử dụng vector đặc trưng là một phương pháp phổ
biến và khá hiệu quả khi tìm kiếm sự tương đồng giữa hai văn bản.
- Xác định cụm của truy vấn
Sau khi xây dựng vector truy vấn, vector này sẽ được dùng để xác định cụm
gần nhất.
Trước khi thực hiện việc xác định cụm truy vấn, kho dữ liệu đầu tiên được
vector hóa, sau đó được phân cụm theo câu hỏi. Chúng tôi thử nghiệm sử dụng hai
phương pháp là K-means và HAC. Do vậy, khi xác định cụm gần nhất với truy vấn,
chúng tôi sử dụng phương pháp so sánh với tâm của từng cụm (centroid-based
method).
Với mục tiêu là tìm nQ câu hỏi trong kho dữ liệu gần với truy vấn nhất, sau
khi chọn cụm gần nhất, có thể các số lượng các câu hỏi trong cụm nhỏ hơn nQ,
chính vì vậy, chúng tôi chọn giải pháp là nếu số lượng các câu hỏi nhỏ hơn nQ thì
sẽ tìm thêm trong các cụm bên cạnh.
- So khớp câu hỏi và xếp hạng
Sau bước xác định cụm gần nhất với truy vấn, vector truy vấn sẽ được so khớp
với tất cả các câu hỏi trong cụm đó, dựa trên độ đo tương tự là độ đo cosine giữa 2
vector.
Trang 33
Các giá trị tương tự này được xếp hạng từ cao xuống thấp.
Nhằm tránh trường hợp câu truy vấn do người dùng đưa vào không có cặp
hỏi-đáp tương tự trong kho dữ liệu, chúng tôi xác định một giá trị ngưỡng T (giá trị
ngưỡng này được xác định qua thử nghiệm).
nQ câu hỏi được chọn là các câu hỏi thỏa mãn điều kiện:
- Độ đo tương tự với truy vấn là cao nhất.
- Độ đo tương tự lớn hơn ngưỡng T.
Nếu nQ=0 thì hệ thống xem như truy vấn không có câu trả lời nào tương ứng
trong kho dữ liệu.
3.2.3 Giai đoạn so khớp câu trả lời
nQ câu hỏi tìm được sẽ được hệ thống chọn ra nQ câu trả lời tương ứng với
các câu hỏi này. Để tăng tính hiệu quả cho hệ thống, hệ thống tiến hành so khớp
vector truy vấn với vector của các câu trả lời tìm được dựa trên độ tương tự giữa các
vector.
Với ý tưởng là cặp hỏi-đáp nào mà cả câu hỏi và câu trả lời càng tương tự với
truy vấn thì càng được ưu tiên đứng đầu tiên trong số các kết quả hiển thị cho người
dùng, chứ không phải là chỉ có câu trả lời tương tự, chúng tôi kết hợp 2 độ đo tương
tự trong cả giai đọan so khớp câu hỏi và so khớp câu trả lời để tăng hiệu quả cho hệ
thống, gọi là độ đo tổng hợp:
Độ đo tổng hợp:
Trong đó: δ là hệ số tổng hợp (tùy thực nghiệm)
Trang 34
Thêm nữa, hệ thống có thể có rất nhiều câu hỏi tương tự trong kho dữ liệu,
nhưng khi hiển thị kết quả cho người dùng, hệ thống chỉ cần đưa ra một số lượng
hạn chế các câu trả lời, vì vậy một chiến lược xếp hạng dựa trên độ đo tổng hợp
được sử dụng để tìm ra nA (nA<nB) câu trả lời tốt nhất làm kết quả cuối cùng, chứ
không phải là toàn bộ nQ câu trả lời.
3.2.4 Xây dựng bộ dữ liệu thử nghiệm
Để thử nghiệm hiệu quả của hệ thống chúng tôi xây dựng bộ dữ liệu gồm hai
phần: tập các tài liệu bao gồm các cặp hỏi-đáp, tập các câu hỏi để thử nghiệm.
a. Xây dựng kho dữ liệu
Toàn bộ dữ liệu được tải về từ diễn đàn tư vấn ghi danh trực tuyến của Trung
tâm tin học trường Đại học Khoa học tự nhiên TpHCM tại địa chỉ:
dưới dạng tập tin văn bản gồm tất cả các câu
hỏi của học viên và các câu trả lời của nhân viên tư vấn.
Diễn đàn tư vấn ghi danh trực tuyến của Trung tâm tin học có trung bình khoảng 20
đến 200 câu hỏi mỗi ngày được gởi lên diễn đàn tùy theo từng thời điểm. Nhân viên
tư vấn chỉ có thể trả lời trực tiếp các câu hỏi của học viên vào khoảng thời gian trực
tuyến, ngoài thời gian này ra, các câu hỏi của học viên sẽ phải đợi sang ngày hôm
sau mới có câu trả lời. Các câu hỏi trên diễn đàn có số lượng rất lớn, dữ liệu phong
phú thích hợp cho việc thử nghiệm của đề tài.
Để có được tập dữ liệu và tập đánh giá dùng cho thử nghiệm, chúng tôi lấy ngẫu
nhiên dữ liệu hỏi đáp trên diễn đàn tư vấn ghi danh trực tuyến của Trung tâm tin
học 1000 cặp hỏi-đáp. Trong đó 800 cặp hỏi-đáp dùng để làm kho dữ liệu và 200
cặp còn lại dùng để chọn lọc 100 câu hỏi thử nghiệm hiệu quả của hệ thống.
Đặc điểm của dữ liệu:
¾ Dữ liệu còn là tổng hợp tất cả các câu hỏi và câu trả lời.
Trang 35
Hình 3-2: Dữ liệu thô
¾ Các câu hỏi trong diễn đàn là dạng văn bản tiếng Việt tự do (có dấu, không dấu,
sai chính tả, không có cú pháp, lồng ghép các từ tiếng Anh).
Ví dụ: “xin chào, cho mình hỏi vài điều, xin chao,hiện tại mình muốn học thiết
kế nội thất,vậy trung có dạ chương trình này không? thanks”. Đây là câu hỏi
vừa có dấu, vừa không dấu, sai chính tả, dùng từ tiếng Anh và có các từ lặp lại.
¾ Các câu hỏi không theo một chủ đề nhất định nào cả. Các câu hỏi có thể hỏi về
thời gian khai giảng, học phí các khóa học, hỏi về các thông tin nội dung khóa
học, việc miễn giảm học phí…
Ví dụ:
Hỏi về thời gian khai giảng: “Tôi xin hỏi các lớp về lập trình JAVA-J2EE ,
chừng nào khai giảng vậy?”
Trang 36
Hỏi về học phí: “EM đã học qua phần mềm 3ds max, bây giờ em muốn học khóa
3ds max nâng cao, xin hỏi trung tâm có dạy không ạ? Và nếu có dạy thì khi nào
dạy? Mỗi khóa thời gian bao lâu? Học phí bao nhiêu tiền / khóa?”
Hỏi về nội dung học: “Cho em hỏi thời khóa biểu của lớp SQL sắp khai giảng.
Anh/ Chị có thể nói cho em biết nội dung chương trình dạy của trung tâm về
khóa học đấy được không ạ. Em chưa biết gì về CSDL,đang phân vân chưa biết
nên học SQL hay Oracle. Xin cho em lời khuyên.”
¾ Các câu hỏi thuộc nhiều lọai câu hỏi khác nhau.
Ví dụ:
o Câu hỏi lựa chọn có không:
“HI. Cho nình hỏi trung tâm còn mở lớp chuyên viên mạng không?”
“Chào tư vấn, tôi muốn học ngành mạng, không biết bên TTTH có các khóa
học nào về mạng không ?”
o Câu hỏi sự kiện:
“ Cho em hỏi ngày khai giảng khóa Đồ họa đa truyền thông.”
o Câu hỏi cách thức:
“Em thuộc lớp KTV ngành lập trình khóa V98TA. Sau khi hoc xong 5 học
phần rồi,còn việc chuẩn bị kì thi tốt nghiệp thì bây giờ em phải làm gì? T3H
có mở lớp ôn tập không hoặc có tài liệu trên mạng không? Mong đươc sự
giúp đỡ”
“xem diểm thì chứng chỉ B xem làm sao?. Sao vào xem toàn thấy chúng chị
A ko ah.chị giúp dùm đi”
o Câu hỏi lý do
“xin hỏi, em có xem trên mạng thấy có chương trình 3d quảng cáo truyền
hình nhưng sao không thấy nội dung a”…
Trang 37
¾ Các câu hỏi có thể chứa nhiều ý hỏi khác nhau. Ví dụ:
Hình 3-3: Ví dụ câu nhiều ý
Chính vì các đặc điểm trên nên dữ liệu này cần được tiền xử lý (xem phần
dưới) trước khi đưa vào hệ thống. Hơn nữa, do đặc điểm là các câu hỏi không theo
một chủ đề nhất định và không thuộc một loại câu hỏi nhất định, trong khi các
phương pháp của hệ thống hỏi-đáp thường phục vụ cho một loại câu hỏi hoặc một
chủ đề nhất định nào đó, vì vậy chúng tôi chọn phương pháp xây dựng vector đặc
trưng đánh trọng số dựa trên từ khóa. Do đó, sau khi tiền xử lý, để đưa vào hệ thống
hỏi-đáp, chúng tôi thực hiện trích từ khóa và xây dựng vector đặc trưng cho toàn bộ
các cặp hỏi-đáp đã có. Việc tìm kiếm câu trả lời sau này dựa hoàn toàn vào dữ liệu
vector đặc trưng đã tạo ra. Hơn nữa, các vector đặc trưng này được gom thành N
cụm khác nhau để giảm thời gian xử lý trong giai đoạn tìm kiếm câu trả lời.
• Giai đoạn tiền xử lý dữ liệu
Các công việc tiền xử lý sau được thực hiện để dữ liệu tạm có thể làm dữ liệu
chuẩn phục vụ cho hệ thống hỏi-đáp sau này:
¾ Tách văn bản tổng hợp thành các tập tin chỉ gồm một câu hỏi và một câu
trả lời.
¾ Bổ sung dấu và sửa các lỗi chính tả, bỏ các từ tiếng Anh thông dụng trên
diễn đàn như “Hi”, “Hello”, “Thanks”,…
Trang 38
¾ Loại bỏ các câu hỏi dài có quá nhiều ý, hoặc câu hỏi ngắn nhưng hỏi các
ý hoàn toàn độc lập với nhau, nhằm giới hạn câu hỏi, một câu hỏi có thể
gồm nhiều câu nhưng chỉ hỏi về một ý hỏi.
• Trích từ khóa
Đối với mỗi cặp câu hỏi-trả lời sau khi tiền xử lý, chúng tôi thực hiện các
bước sau để trích từ khóa:
¾ Tách câu.
¾ Tách từ.
¾ Loại bỏ các hư từ.
¾ Loại bỏ các cụm từ xuất hiện nhiều nhưng không có ý nghĩa trong diễn
đàn.
(đã trình bày ở trên)
• Xây dựng vector đặc trưng
Xây dựng vector đặc trưng cho tất cả câu hỏi và câu trả lời trong kho dữ liệu,
chúng tôi tiến hành thử nghiệm trên cả 2 độ đo: chỉ sử dụng Tf và sử dụng kết hợp
Tf-Idf (trình bày kết quả trong phần 3.4.3).
• Gom cụm các câu hỏi trong kho dữ liệu
Trước khi tìm kiếm câu trả lời, tất cả các câu hỏi trong kho dữ liệu sẽ được
gom cụm trước nhằm tăng tính hiệu quả của hệ thống. Truy vấn do người dùng đưa
vào không cần thiết phải so khớp với toàn bộ các câu hỏi trong kho dữ liệu mà chỉ
cần so khớp với các câu hỏi trong cùng cụm mà thôi.
Do các câu hỏi trên diễn đàn là dạng văn bản tự do, không theo bất kỳ một chủ
đề nào, các khách tham quan diễn đàn có thể hỏi bất cứ câu nào mà họ muốn. Chính
vì lý do này, chúng tôi thực hiện gom cụm để đưa các câu hỏi gần giống nhau vào
cùng một cụm và dễ dàng cho quá trình tìm kiếm về sau.
Nhiều phương pháp gom cụm được đề cập trong chương 3, chúng tôi chỉ chọn
phương pháp gom cụm có độ phức tạp nhỏ nhất, thích hợp với dữ liệu lớn là
Trang 39
phương pháp gom cụm K-means và HAC. Hai phương pháp này được thử nghiệm,
so sánh đánh giá hiệu quả trong phần 3.4.3.
b. Xây dựng tập câu hỏi thử nghiệm
Tập câu hỏi thử nghiệm là 100 câu hỏi, được lấy từ dữ liệu thực tế trên diễn
đàn trung tâm tin học. Nhằm tránh trường hợp các câu hỏi trong tập câu hỏi thử
nghiệm hoàn toàn không liên quan gì đến các cặp hỏi-đáp đã chọn trong cơ sở dữ
liệu nên chúng tôi chọn tập câu hỏi thử nghiệm với tỉ lệ như sau:
¾ 10 câu hoàn toàn không liên quan.
¾ 50 câu lấy từ câu hỏi trên diễn đàn trung tâm tin học có ít nhất 3 câu trả
lời liên quan trong kho dữ liệu (việc kiểm chứng được thực hiện thủ
công).
¾ 40 câu hỏi được lấy từ kho dữ liệu nhưng có sửa chữa về từ ngữ, về cấu
trúc.
3.3 Chương trình cài đặt
Hệ thống hỏi-đáp tự động phục vụ cho diễn đàn tư vấn ghi danh trực tuyến
được cài đặt gồm các chức năng như: chức năng xây dựng kho dữ liệu, chức năng
gom cụm câu hỏi, chức năng tìm kiếm câu trả lời và chức năng cập nhật kho dữ
liệu. Các chức năng này được biểu diễn như trong hình 4.4.
Trang 40
Hình 3-4: Chức năng hệ thống
Hệ thống hỏi-đáp tự động phục vụ tư vấn ghi danh trực tuyến được cài đặt trên
máy tính có cấu hình: Intel Core2 Duo 2GHz, RAM 2GB.
Chương trình được cài đặt bằng ngôn ngữ C#, .NET framework 2.0, viết trên
môi trường phát triển Microsoft Visual Studio 2005.
Các màn hình chức năng cụ thể trình bày trong phần phụ lục.
3.4 Thử nghiệm
3.4.1 Mục tiêu thử nghiệm
Với mục tiêu thử nghiệm đánh giá kết quả các phương pháp sử dụng, kết quả
của bước này làm nền tảng để thử nghiệm các bước tiếp theo, hướng đến mục tiêu
chung của hệ thống là xây dựng được một hệ thống hỏi-đáp cho lĩnh vực tư vấn ghi
danh trực tuyến để đạt được kết quả hiển thị cho người dùng là chấp nhận được,
chúng tôi đề ra các mục tiêu chi tiết như sau:
o Thử nghiệm, so sánh, đánh giá hiệu quả rút trích từ khóa dựa vào từ điển
(xử lý ngôn ngữ tự nhiên).
o So sánh, đánh giá hiệu quả hệ thống khi sử dụng các phương pháp gom
cụm khác nhau.
Trang 41
o So sánh, đánh giá hiệu quả hệ thống với 2 phương pháp xây dựng vector
đặc trưng khác nhau là sử dụng độ đo Tf và sử dụng độ đo tổng hợp Tf-
Idf.
o Đánh giá hiệu quả sử dụng của tìm kiếm câu trả lời thông tin dựa trên mô
hình đề xuất, với các ngưỡng T khác nhau.
3.4.2 Kế hoạch thử nghiệm
Để đạt được các mục tiêu như trên, chúng tôi thử nghiệm từng giai đoạn, kết
quả của bước này làm nền tảng để thử nghiệm các bước sau. Đầu tiên, chúng tôi xây
dựng hệ thống hỏi-đáp theo kiến trúc đã trình bày trong phần 3.2. Sau đó tiến hành
thử nghiệm lần lượt việc sử dụng các phương pháp khác nhau để so sánh, đánh giá
kết quả đạt được.
o Bước 1: Chúng tôi tiến hành thử nghiệm trên toàn bộ những câu hỏi đã có
trong kho dữ liệu của hệ thống xem liệu kết quả có chính xác 100% hay
không, sau đó mới thử nghiệm trên 100 câu hỏi thử nghiệm để đánh giá kết
quả.
o Bước 2: Thử nghiệm, so sánh, đánh giá hiệu quả hệ thống trong 2 trường
hợp: có sử dụng danh sách các cụm từ xuất hiện nhiều nhưng không có ý
nghĩa với diễn đàn tư vấn và không sử dụng danh sách này. Trường hợp tốt
hơn sẽ sử dụng tiếp cho các bước thử nghiệm tiếp theo.
o Bước 3: Thử nghiệm, so sánh, đánh giá kết quả hệ thống với 2 phương
pháp gom cụm phổ biến là K-means và HAC. Phương pháp nào tốt hơn sẽ
được sử dụng trong các bước thử nghiệm tiếp theo.
o Bước 4: Thử nghiệm, so sánh, đánh giá kết quả hệ thống với 2 phương
pháp đánh trong số từ khóa là tf và tf-idf. Phương pháp nào tốt hơn sẽ được
sử dụng cho bước thử nghiệm tiếp theo.
o Bước 5: Thử nghiệm, so sánh, đánh giá kết quả hệ thống với các giá trị
ngưỡng khác nhau.
Trang 42
3.4.3 Kết quả thử nghiệm
Phương pháp đánh giá phổ biến nhất cho các hệ thống tìm kiếm, cũng như hệ
thống hỏi-đáp là dựa trên hai độ đo: độ chính xác và độ phủ. Để phục vụ cho hệ
thống tư vấn ghi danh trực tuyến, chúng tôi định nghĩa lại độ chính xác và độ phủ
cho các trường hợp cụ thể như sau:
¾ Đối với 800 câu hỏi có trong kho dữ liệu
o Độ chính xác
Do 800 câu hỏi thực nghiệm được chọn hoàn toàn từ kho dữ liệu, mục đích
của bước này là chỉ kiểm tra xem kết quả của hệ thống trả về có chính xác là câu trả
lời tương ứng với câu hỏi đó hay không, nên chỉ cần tính độ chính xác, không xác
định độ phủ.
Trong đó: Pi: Độ chính xác khi trả lời câu hỏi thứ i.
¾ Đối với 100 câu hỏi thử nghiệm được chọn theo tiêu chí như đã trình bày
trong phần 3.2.4b
o Độ chính xác
o Độ phủ
¾ Độ chính xác và độ phủ trung bình:
Trang 43
Với:
Pi: Độ chính xác khi trả lời câu hỏi thứ i.
Ri: Độ phủ khi trả lời câu hỏi thứ i.
N: Số câu thử nghiệm.
3.4.3.1 Hiệu quả rút trích từ khóa
Như đã đề cập trong phần trước, chúng tôi sử dụng công cụ tách từ của nhóm
[12]. Phương pháp tách từ này sử dụng bộ từ điển tiếng Việt do nhóm xây dựng để
tách từ. Các cặp hỏi-đáp sau khi tách từ xong, sẽ được loại bỏ các cụm từ không có
ý nghĩa (chúng tôi sử dụng từ điển hư từ cũng của nhóm gồm 795 mục từ) để rút
trích các từ khóa quan trọng.
Ngoài ra, nếu chỉ sử dụng từ điển hư từ thì rất nhiều cụm từ không phải là hư
từ nhưng lại không cần thiết trong ngữ nghĩa của câu hỏi, và những từ này không
nhất thiết phải tham gia vào quá trình so khớp câu hỏi. Ví dụ: “Xin cho biết thời
khóa biểu của lớp tin học bằng A, tôi xin cảm ơn rất nhiều”. Trong câu này cụm từ
“xin cho biết”, “cảm ơn” rõ ràng là không phải hư từ nhưng nó không cần thiết khi
so khớp câu hỏi, nên không được xem là từ khóa.
Chính vì lý do này, chúng tôi bổ sung danh sách các cụm từ xuất hiện nhiều
nhưng không có ý nghĩa với diễn đàn tư vấn qua thực nghiệm. Trong phần thử
nghiệm này, chúng tôi thử nghiệm hiệu quả hệ thống trong 2 trường hợp:
Trường hợp 1: Không sử dụng danh sách các cụm từ xuất hiện nhiều nhưng
không có ý nghĩa với diễn đàn tư vấn
Trường hợp 2: Có sử dụng thêm danh sách các cụm từ xuất hiện nhiều nhưng
không có ý nghĩa với diễn đàn tư vấn.
Kết quả thử nghiệm được trình bày trong bảng 3-1
Trang 44
Bảng 3-1: Thử nghiệm danh sách cụm từ xuất hiện nhiều
Phương pháp
Đánh giá
Trường hợp 1 Trường hợp 2
Số lượng từ khóa thu được 2574 2528
Thời gian chạy trung bình (1 câu hỏi) (giây) 4.35 4.15
Thời gian xây dựng vector đặc trưng (cho 800
cặp hỏi-đáp) (phút)
14.96 14.01
Độ chính xác (800 câu trong kho dữ liệu) 100% 100%
Độ chính xác (100 câu thử nghiệm) sử dụng
vector trọng số tf-idf có chuẩn hóa
77.72% 79.52%
Kết quả cho thấy, có sử dụng danh sách các cụm từ xuất hiện nhiều nhưng
không có ý nghĩa với diễn đàn tư vấn sẽ làm tăng tốc thời gian xử lý, đồng thời tăng
độ chính xác của câu trả lời (do loại bỏ được các câu hỏi giống nhau ở các từ không
quan trọng). Việc sử dụng thêm danh sách này có ưu điểm:
- Trích từ khóa tốt hơn (vì loại bỏ được nhiều cụm từ không có ý nghĩa)
- Giảm số chiều của vector văn bản, do đó giảm không gian tìm kiếm
- Tốc độ nhanh hơn
- Độ chính xác cao hơn
Trang 45
Từ kết quả thử nghiệm của bước này, danh sách các cụm từ xuất hiện nhiều
nhưng không có ý nghĩa với diễn đàn tư vấn cho kết quả tốt, nên sẽ được sử dụng ở
bước thử nghiệm sau.
3.4.3.2 Hiệu quả gom cụm
Như đã đề cập trong phần giải pháp, để giảm không gian tìm kiếm, thay vì tìm
kiếm với 800 vector cặp hỏi-đáp có trong kho dữ liệu, hệ thống sẽ gom các câu hỏi
tương tự nhau vào cùng một cụm, như vậy chỉ cần tìm kiếm các câu hỏi tương tự
trong một vài cụm mà thôi. Chúng tôi thử nghiệm hệ thống với 2 phương pháp gom
cụm có độ phức tạp thấp là k-means và HAC (đã trình bày trong Chương 2).
Thử nghiệm phương pháp gom cụm k-means và HAC dựa trên vector câu hỏi
của các cặp hỏi-đáp với cùng số lượng cụm nC=30, chúng ta được kết quả như bảng
bên dưới:
Bảng 3-2: Thử nghiệm phương pháp gom cụm
Phương pháp
Đánh giá
K-means HAC
Số cặp trong một cụm (tối đa) 637 625
Thời gian gom cụm (800 cặp) (giây) 5.07 360
Độ chính xác (100 câu thử nghiệm) sử
dụng vector trọng số tf-idf có chuẩn hóa
79.52% 79.42%
Nhận thấy rằng, thời gian gom cụm thuật toán HAC chậm so với k-means do
độ phức tạp cao hơn (Chương 2), vả lại kết quả cũng không tốt hơn, vì vậy chúng
tôi chọn sử dụng thuật toán gom cụm k-means để thực hiện các thử nghiệm sau này.
Trang 46
Dữ liệu thử nghiệm cũng cho thấy, khi chạy với thuật tóan k-means và cả với
thuật toán HAC, kết quả gom cụm phân bố không đều, có khoảng 80% (637/800)
cặp hỏi-đáp tập trung vào một cụm và 20% cặp hỏi-đáp tập trung vào các cụm còn
lại.
Chúng tôi chạy thử nghiệm k-means với số lượng cụm khác nhau xem kết quả
gom cụm và giá trị các độ đo liệu có tốt hơn không. Chúng tôi khảo sát hiệu quả của
hệ thống với nhiều giá trị số lượng cụm khác nhau đối với 100 câu hỏi trọng số tf-
idf có chuẩn hóa. Kết quả thu được như sau:
Bảng 3-3: Thử nghiệm thông số gom cụm
Đánh giá
Số cụm
Độ chính
xác
Độ phủ
Thời gian
chạy trung
bình (1 câu
hỏi)(giây)
Số cặp tối
đa trong
một cụm
10 77.6% 79.86% 4.19 624
20 78.18% 75.53% 4.15 612
30 79.52% 81.67% 4.47 637
40 78.51% 80.67% 4.29 629
50 78.52% 80.33% 4.15 612
Nhận xét:
- Kết quả gom cụm với các giá trị số cụm khác nhau cũng không ảnh hưởng
nhiều đến kết quả cuối cùng, vì vậy chúng tôi chọn số lượng cụm là 30 cho
các bước tiếp theo.
- Kết quả gom cụm vẫn phân bố không đều, điều này có nghĩa là dữ liệu trong
kho dữ liệu mà chúng tôi có được từ trên diễn đàn tư vấn là không đều.
Mục tiêu của bước gom cụm là giảm không gian tìm kiếm nhưng rõ ràng là
Trang 47
đối với bộ dữ liệu trên diễn đàn tư vấn cụ thể này thì bước gom cụm này
cũng không làm cho hệ thống tốt hơn bao nhiêu.
3.4.3.3 Hiệu quả tìm kiếm câu trả lời
Nhận thấy kết quả gom cụm trong phần thử nghiệm trước với phương pháp
trọng số tf-idf là không đều, nên trong bước này chúng tôi thử nghiệm hiệu quả hệ
thống với phương pháp trọng số tf (chỉ đánh giá mức độ quan trọng của mục từ ở
mức cục bộ). Cũng nhận thấy rằng, các câu hỏi diễn đàn tư vấn có thể là một câu rất
ngắn cũng có thể là một đọan văn bản nhiều câu khá dài, để việc đánh trọng số này
không phụ thuộc vào chiều dài văn bản, chúng tôi thử nghiệm phương pháp trọng số
có chuẩn hóa (chương 2).
Ngòai ra, mô hình đề xuất cũng sử dụng giá trị ngưỡng T để xác định các câu
trả lời trả về, nên chúng tôi cũng thử nghiệm giá trị các ngưỡng T sao cho độ chính
xác hệ thống là cao nhất có thể.
Trong phần này, chúng tôi thử nghiệm hiệu quả của hệ thống khi tìm kiếm câu
trả lời cho 100 câu hỏi được lựa chọn theo tiêu chí nêu trong phần 3.3.2.
- So sánh hai phương pháp đánh trọng số tf và tf-idf kết hợp với chuẩn
hóa.
Trong phần thử nghiệm này chúng tôi thử nghiệm với cùng ngưỡng T=0.5,
δ=0.5 (xem phần 4.1.3). Kết quả thử nghiệm được trình bày trong bảng sau:
Trang 48
Bảng 3-4: Thử nghiệm phương pháp đánh trọng số
Đánh giá
Phương pháp
Độ chính xác Độ phủ
Thời gian
chạy trung
bình (1 câu
hỏi)(giây)
Sử dụng Tf-Idf chưa chuẩn hóa 77.41% 80.70% 3.91
Sử dụng Tf-Idf có chuẩn hóa 79.52% 81.67% 4.15
Sử dụng Tf có chuẩn hóa 49,93% 61,03% 1.43
Sử dụng Tf có chuẩn hóa, tăng
ngưỡng T=0.55
53% 61.03% 1.43
Ta có biểu đồ so sánh như sau:
Hình 3-5: Biểu đồ so sánh độ chính xác và độ phủ trung bình của hệ thống
Trang 49
Nhận xét:
- Sử dụng phương pháp trọng số tf-idf có chuẩn hóa cho kết quả độ chính xác
tốt nhất nhưng thời gian chạy trung bình lại chậm nhất.
- Sử dụng phương pháp trọng số tf có chuẩn hóa cho kết quả độ chính xác
không cao nhưng thời gian chạy nhanh hơn. Kết quả này có được là do sử
dụng tf, kết quả phân cụm đều hơn nên thời gian chạy cũng nhanh hơn. Tuy
nhiên, gom cụm đều không đồng nghĩa với gom cụm tốt, minh chứng là độ
chính xác đã giảm đi.
- Thử nghiệm hiệu quả khi thay đổi ngưỡng
Với mục tiêu tăng độ chính xác của hệ thống, chúng tôi thử nghiệm thay đổi
ngưỡng T với 100 câu hỏi thử nghiệm:
Bảng 3-5: Bảng kết quả thử nghiệm khi thay đổi ngưỡng
Ngưỡng Độ chính xác Độ phủ
0.4 63.3% 83.83%
0.45 73.03% 80.67%
0.5 79.52% 81.67%
0.55 75.56% 73.22%
0.6 74.9% 70.26%
Ta có biểu đồ so sánh như sau:
Trang 50
Hình 3-6: Độ chính xác và độ phủ khi thay đổi ngưỡng T
Kết luận:
Qua quá trình thử nghiệm, kết quả thử nghiệm cho 800 cặp hỏi-đáp và 100 câu
hỏi trên diễn đàn tư vấn ghi danh trực tuyến Trung tâm tin học với mô hình đề xuất
là khá khả quan. Độ chính xác cao nhất là 79.52% và độ phủ là 81.67%, trong khi
các công trình đã có liên quan đến hệ thống hỏi-đáp cho diễn đàn có độ chính xác
và độ phủ dao động trong khoảng 70% cho tới 90% ([26], [3], [16]). Các nghiên
cứu đã có cũng cho thấy, trong trường hợp bổ sung thêm các xử lý ngôn ngữ chẳng
hạn như xử lý thêm từ đồng nghĩa, loại câu hỏi… thì kết quả đạt được sẽ cao hơn
[3]. Vì vậy, hiệu quả hệ thống có thể sẽ tăng lên nếu chúng ta bổ sung thêm các xử
lý ngôn ngữ.