ĐINH THỊ QUYÊN
PHƯƠNG PHÁP PHÂN TÍCH NGỮ NGHĨA TIÈM ẨN
TÌM KIẾM VĂN BẢN TIẾNG ANH DựA TRÊN NỘI
DUNG
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
• • • •
Chuyên ngành: Khoa học máy tính
ĐINH THỊ QUYÊN
PHƯƠNG PHÁP PHÂN TÍCH NGỮ NGHĨA TIÊM ẨN
TÌM KIẾM VĂN BẢN TIẾNG ANH DựA TRÊN NỘI
DUNG
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
• • • •
Chuyên ngành: Khoa học máy tính
Ngưòi hướng dẫn khoa học
TS. TRỊNH ĐÌNH VINH
TRƯỜNG ĐẠI HỌC sư PHẠM HÀ NỘI 2
KHOA CÔNG NGHỆ THÔNG TIN
HÀ NỘI,
Để hoàn thành khóa luận này, em xin bày tỏ lòng cảm ơn sâu sắc đến TS.
Trịnh Đình Vinh, thầy là người đã giúp đỡ, chỉ bảo em rất tận tình trong suốt thời
gian viết bài.
Em xin chân thành cảm ơn quý thầy cô trong khoa Công nghệ thông tin -
Trường Đại học Sư phạm Hà Nội 2 đã rất nhiệt tình và tâm huyết truyền đạt kiến
thức cho chúng em trong suốt 4 năm học tập. Các thầy cô không chỉ dạy chúng
em kiến thức chuyên ngành mà còn truyền đạt những kinh nghiệm sống quý báu,
đó là hành trang, là nền tảng để chúng em có thể tự tin hơn trong cuộc sống sau
này.
Cuối cùng, em xin gửi lời cảm ơn sâu sắc tới gia đình, bạn bè đã luôn chia sẻ,
động viên trong thời gian học tập và hoàn thành luận văn tốt nghiệp.
Dù đã rất cố gắng hoàn thiện để nghiên cứu, sưu tầm tư liệu nhưng khóa luận
Bảng 2.4. Kết quả khoảng cách từ truy vấn Q với các tài liệu
Ký hiệu viết
tắt
Tiếng Anh Tiếng Việt
CSDL DataBase Cở sở dữ liệu
IDF Inverse Document Frequency Tần số xuất hiện tài liệu
TF Term Frequency Tần số xuất hiện thuật ngữ
LSI Latent Semantic Indexing Chỉ số hóa ngữ nghĩa ẩn
LSA Latent Semantic Analysis Phân tích ngữ nghĩa tiềm ẩn
SVD Singular Value Decomposition Tách giá tri riêng
ERSM Equivalance Rough Set Model
Mô hình tập thô tương đương
TRSM Tolerance Rough Set Model Mô hình tập thô dung sai
Bảng 2.5. Số lần xuất hiện của thuật ngữ trong mỗi tài liệu
DANH MỤC CÁC HÌNH
•
Hình 1.1. Ví dụ phân phối của các giá trị có thứ tự ưu tiên
Hình 2.1. Sử dụng các khái niệm cho truy vấn
Hình 2.2. Biểu đồ 2-D của 12 thuật ngữ và 9 tài liệu từ tập mẫu
Hình 2.3. Sơ đồ SVD của 1 ma trận hình chữ nhật thuật ngữ - tài liệu
Hình 2.4. Sơ đồ của SVD được giảm lược của một ma trận thuật ngữ - tài liệu
Hình 3.1. File chứa các từ dừng (stopword)
Hình 3.2. Các thông số Ư, S"
1
, V
T
Hình 3.3. Ánh xạ truy vấn q vào cùng một không gian vecto cơ sở dữ liệu
Hình 3.4. Giao diện tìm kiếm văn bản Hình 3.5. Kết quả tìm kiếm văn bản
MỞ ĐẦU
1. Lý do chọn đề tài
đạt được hiệu quả tối đa, các tài liệu không liên quan có thể được truy tìm đơn giản
bởi những thuật ngữ xuất hiện ngẫu nhiên trong nó giống với thuật ngữ trong truy
vấn, mặt khác các tài liệu liên quan có thể bị bỏ qua bởi không có thuật ngữ xuất
hiện trong tài liệu truy vấn.
Từ đó, một ý tưởng thú vị được xem xét, liệu việc truy tìm dựa vào nội
dung, ý nghĩa có hiệu quả hơn là việc truy tìm trực tiếp trên các thuật ngữ? Mô
hình LSA ra đời là một giải pháp hữu hiệu cho vấn đề truy tìm thông tin dựa trên
cơ sở nội dung tài liệu văn bản, tìm kiếm trên cơ sở nội dung.
Trước khi truy tìm các tài liệu được coi như danh sách các từ và chúng phải
được đánh chỉ mục. Có một thực tế là không phải tất cả các từ đều có ý nghĩa, vì
vậy việc loại đi danh sách các từ không có nghĩa vô cùng quan ttọng và các từ
không có ý nghĩa sẽ không được đánh chỉ mục. Từ thông tin của người sử dụng
biểu thị qua câu truy vấn, thuật toán truy tìm phải đảm bảo rằng, chiến lược xếp
hạng tập các tài liệu trong câu trả lời luôn ưu tiên cho những thông tin phù họp với
truy vấn của người sử dụng đưa ra. Hơn thế nữa, một kĩ thuật được đánh giá là tốt
phải dựa trên việc xếp hạng các tài liệu này, tức là những tài liệu phù hợp và được
coi là “gần” vói câu tiny vấn nhất sẽ được xếp lên trên các tài liệu ít phù hợp trong
danh sách tài liệu trả lời. Chính vì vậy, em lựa chọn đề tài: “Phương pháp phân tích
ngữ nghĩa tiềm ẩn tìm kiếm văn bản tiếng anh dựa trên nội dung” làm đề tài khóa
luận tốt nghiệp.
2. Mục đích nghiên cứu
Khóa luận tìm hiểu về một số phương pháp tìm kiếm văn bản, phương pháp
LSA. Từ đó, xây dựng chương trình tìm kiếm văn bản tiếng anh bằng phương pháp
LSA để người dùng có thể tìm kiếm thông tin, tài liệu một cách hiệu quả.
3. Nhiệm vụ nghiên cứu
Nhiệm vụ của khóa luận là đi sâu vào nghiên cứu phương pháp tìm kiếm
văn bản LSA (Latent Semantic Analysis): Từ việc hiểu được phương pháp LSA
như thế nào, đến biết được các bước thực hiện cơ bản LSA. Từ đó xây dựng được
chương trình tìm kiếm văn bản với tốc độ nhanh và độ chính xác cao.
7
Chương 3. Tìm kiếm văn bản tiếng anh bằng phương pháp phân
tích ngữ nghĩa tiềm ẩn
Xây dựng một chương trình cụ thể.
CHƯƠNG 1: Cơ SỞ LÝ THUYẾT
1.1. Các bộ máy tìm kiếm
Các bộ máy tìm kiếm (search engine/ moteur de recherche) ra đời từ giữa
những năm 1990, với chức năng tìm kiếm khác hẳn các danh bạ mạng: Thay vì tìm
kiếm các website như danh bạ mạng, các bộ máy tìm kiếm lại sưu tập các ừang
web, đọc toàn bộ nội dung của từng trang và lưu vào chỉ mục. Người dùng mạng
chỉ cần gõ từ khóa cần tìm và bộ máy sẽ tìm trong toàn bộ nội dung đó.
Với các bộ máy tìm kiếm có thể:
- lìm những thông tin chính xác: Như thông tin liên lạc của một cá nhân, tổ chức,
hoặc chi tiết liên quan đến một sản phẩm nào đó.
- Tìm những tài liệu chuyên biệt, đặc thù: Như các công ước quốc tế, các văn bản
nhà nước.
- Tìm những website mới xuất hiện trên mạng: Với vòng quay tương đối nhanh, các
robot có thể tiếp cận các trang web mới hoặc quay lại cập nhật các ừang web đã
lưu chỉ mục trong vòng vài tuần lễ.
- Ket quả các công thức tìm kiếm đa dạng: Với các từ khóa, thuật ngữ, thuật toán
khác nhau theo khả năng đáp ứng và công nghệ phát triển của từng bộ máy.
Tuy nhiên, có một điểm cần lưu ý khi sử dụng các bộ máy tìm kiếm đó là
các trang được đưa ra trong kết quả tìm kiếm không phải là trang hiện hữu trên
mạng mà là ừang được lưu trong chỉ mục của bộ máy tìm kiếm.
Một số bộ máy tìm kiếm thông dụng:
- Ask Jeeves: Cơ chế tìm kiếm theo ngôn ngữ tự nhiên, có thể cho phép lưu trữ đến
1000 kết quả tìm kiếm, sắp xếp và ghi chú trong hồ sơ cá nhân. Có nhiều kiểu giao
diện khác nhau cho người dùng lựa chọn và các phiên bản tiếng Nhật, Tây Ban
Nha, Đức, Pháp, Hà Lan, Ý.
9
- Brainboost: Tìm kiếm theo ngôn ngữ tự nhiên, kết quả được trích từ các
tin. Tính tự nhiên của ngôn ngữ thường được yêu càu tính tự nhiên ưong chiến
lược tìm kiếm.
1.2.1. Các từ dừng và từ gốc
Đa số ngôn ngữ tự nhiên có những từ chức năng, những liên từ giói từ
xuất hiện vói số lượng lớn trong các tài liệu và điển hình là ít được sử dụng
trong việc xác định các tài liệu thỏa mãn thông tín tìm kiếm. Các từ như vậy (ví
dụ: a, an, the, on ) được gọi là các từ dừng (stopword).
Các kỹ thuật tìm kiếm thông thường không chỉ số hóa các từ dừng, nhưng
có ý tưởng thay thế chúng với một đối tượng thay thế để ghi nhớ sự xuất hiện
của các từ dừng. Điều này cho phép tìm kiếm những cụm từ chứa các từ dừng,
ví dụ như “books on the table”. Việc giảm bớt không gian chỉ số và cải thiện
thực hiện là những lý do quan trọng để loại trừ các từ dừng. Tuy nhiên, như vậy
một số câu truy vấn như “to be or not to be” có thể không còn được hỏi. Một
điều nữa là từ nhiều nghĩa (một từ có nhiều nghĩa phụ thuộc vào văn cảnh hoặc
cách nói): “can” là một động từ thì không có ích cho các truy vấn từ khóa,
nhưng “can” là một danh từ có thể là trung tâm đối với một câu truy vấn, vì yậy
nó không nằm trong danh sách từ dừng.
STEMMỈNG (từ gốc) hay là CONFLATING là phương thức hỗ trợ sự phù
hợp của một thuật ngữ truy vấn với biến đổi hình thái trong kho dữ liệu. Trong
tiếng Anh, cũng như một số ngôn ngữ khác, các phần của văn nói, thời và số
lượng được chuyển từ những biến tố của từ. Có thể muốn một truy vấn chứa từ
“comparable” phù hợp vói một tài liệu chứa từ “compare”. Các phương pháp
stemming nhìn chung sử dụng sự kết họp việc phân tích hình thái (chẳng hạn,
giải thuật của Porter hay to cứu từ điển như WordNet). Stemming có thể làm
tăng số lượng các tài liệu trả lời, nhưng có thể bao gồm cả các tài liệu không
thích họp. Chẳng hạn, giải thuật Porter không chấp nhận “university” và
“universal” cùng là “univers”. Conflating, xác định các thuật ngữ liên quan qua
việc sử dụng từ điển, trong đó liệt kê các thuật ngữ đồng nghĩa và đôi khi cả liệt
kê cả quan hệ giữa chúng. Ví dụ, các từ “study”, “leaming”, “school word”,
1
- Nhận biết các từ đồng nghĩa bằng tham khảo từ điển đồng nghĩa. Mọi thuật
ngữ có ý nghĩa tương tự sẽ được thay thế bằng tò chung.
- Tìm từ gốc (stemming) bằng thuật toán loại bỏ các tiền tố và hậu tố (suffix
và prefix).
- Đếm tàn số stem trong mỗi tài liệu.
- Tính toán trọng số các thuật ngữ hay từ gốc.
- Tạo tệp mục lục trên cơ sở các thuật ngữ và trọng số nói trên.
1.2.3. Phân nhóm văn bản
Với nhiệm vụ bài toán khai phá dữ liệu văn bản là tìm kiếm những thông tin
còn tiềm ẩn trong cơ sở dữ liệu. Với những cơ sở dữ liệu lớn vấn đề đặt ra là các hệ
thống tìm kiếm sao cho hiệu quả, một trong những kỹ thuật chủ yếu là phân nhóm
văn bản nhằm giải quyết vấn đề trên.
Trong bài toán phân nhóm, một nhóm là một tập hợp các phàn tử giống nhau
hơn so với các phàn tử thuộc nhóm khác. Mục tiêu của bài toán phân nhóm là tìm
ra một tập họp các nhóm sao cho độ tương đồng giữa các phần bên trong mỗi
nhóm cao và độ tương đồng giữa các phần tử khác nhau phải thấp.
• Phương pháp phân nhóm phân cấp
Đối với phương pháp phân nhóm phân cấp, quá trình xây dựng phân cấp
thường có chi phí lớn nhất. Đã có nhiều thuật toán được phát triển nhằm xây dụng
cây phân cấp văn bản một cách hiệu quả. Các thuật toán này thường có chung
phương pháp lặp quá trình phân tích hai cặp nhóm đã được xây dựng từ trước và
hợp nhất cặp có độ tương đồng lớn nhất thành một nhóm văn bản. Các thuật toán
chỉ khác nhau về việc tính toán độ tương đồng khi một tong số các cặp là sản phẩm
của quá trình họp nhất trước đó. Phương pháp phân nhóm đơn liên kết định nghĩa
độ tương đồng là độ tương đồng lớn nhất giữa hai đơn vị từ hai nhóm. Các phương
pháp phân nhóm khác hoàn toàn sử dụng độ tương đồng nhỏ nhất, phương pháp
phân nhóm liên kết nhóm trung bình sử dụng độ tương đồng trung bình. Các thuật
toán này thường có chung đặc tính tích tụ ở chỗ chứng đều lặp quá trình ghép hai
nhóm văn bản thành một nhóm.
1
) thì hiện diện của một trong hai thuật ngữ trong bản ghi (hay
trong tài liệu) đủ để đáp ứng truy tìm bản ghi này.
1
- Toán tử AND: Tổ hợp các thuật ngữ (hay từ khóa) vào một câu thuật
ngữ. Vậy truy vấn (terril! AND term
2
) chỉ ra cả hai thuật ngữ phải đồng thòi hiện
diện trong tài liệu để đem lại kết quả.
- Toán tử NOT: Là hạn chế hay thuật ngữ hẹp, thông thường nó được
sử dụng với toán tử AND. Câu truy vấn (termi AND NOT term
2
) dẫn tới truy tìm
bản ghi có termi nhưng không có term
2
.
1.2.5. Cấu trúc tệp
Một trong các vấn đề cơ bản trong thiết kế hệ thống IR là quyết định sử dụng
loại cấu trúc tệp nào để lưu trữ CSDL tài liệu, cấu trúc tệp sử dụng trong các hệ
thống IR bao gồm các tệp phẳng, tệp mục lục (inverted), tệp chữ ký và các tệp khác
như cây và đồ thị.
Với quan điểm tệp phẳng, một hay nhiều tài liệu lưu trữ trong tệp, thông
thường trong mã ASCII hay EBCDIC, không chỉ mục tài liệu. Tìm kiếm tệp phẳng
thông qua tìm kiếm mẫu. Trong UNIX, khi lưu trữ tập hợp các tài liệu người ta lưu
trữ mỗi tài liệu trong một tệp, trong danh mục. Các tệp này có thể tìm kiếm nhờ các
công cụ tìm kiếm theo mẫu như “grep”, “awk”. Tiệm cận này không hiệu quả vì
mỗi lần truy vấn thì toàn bộ tập hợp tài liệu phải được duyệt để tìm ra mẫu văn
bản.
Các tệp chữ ký: Chứa các chữ ký (mẫu bit) đại diện cho tài liệu. Có nhiều
cách để sinh chữ ký tài liệu. Câu truy vấn được đại diện bởi chữ ký mà nó sẽ được
so sánh với chữ ký tài liệu trong khi truy tìm.
2, 3, 4) là số ID của bản ghi (record) i hay tài liệu i.
Dòng 1 có nghĩa rằng Recordi và Record
3
chứa termi. Các dòng khác có
ý nghĩa tương tự. Việc tìm kiếm sẽ được thực hiện nhanh chóng trong các tệp
mục lục. Chỉ các hàng chứa thuật ngữ tìm kiếm mới được truy tìm. Không cần
tìm mọi bản ghi trong CSDL.
Quy tắc tìm kiếm mô hình Bool trên cơ sở các tệp mục lục như sau:
- Truy vấn AND: Ví dụ (Temii AND temij), cho danh sách ttộn hàng i với
hàng j trong tệp mục lục và mọi bản ghi đều chứa Teraii và Ternij sẽ là kết quả
truy tìm ở đầu ra. Ví dụ: (Termi AND Term
2
) cho kết quả là Recordi.
- Truy vấn OR: Ví dụ (Teriĩii OR Temij), cho danh sách trộn hàng i và
hàng j mọi mục trong danh sách trộn là đầu ra kết quả.
- Truy vấn NOT: Ví dụ (Ternii AND NOT Temij) sẽ cho kết quả là các
mục xuất hiện trong hàng i nhưng không trong hàng j. Truy vấn (TemXị AND
NOT Termi) cho kết quả là Record
2
, Recordị. Truy vấn (Termi AND NOT
TeriĩLị) sẽ cho đầu ra là rỗng.
Mở rộng thao tác tệp mục lục
Cho đến thời điểm hiện tại đã bỏ qua hai yếu tố quan trọng khi chỉ mục
và truy tìm tài liệu, đó là vị trí của các thuật ngữ và ý nghĩa các thuật ngữ (tần
số thuật ngữ) trong tài liệu. Trong các truy vấn AND, mọi bản ghi chứa cả hai
thuật ngữ được tìm thấy, không quan tâm đến vị trí của chúng trong tài liệu. Để
nâng cao hiệu quả truy vấn, hai yếu tố này cần được xem xét.
Các quan hệ đặc tả giữa hai hay nhiều thuật ngữ được tăng cường bằng
cách bổ sung các tham số “tính gàn kề” vào đặc tả truy vấn. Khi tham số gần kề
được bổ sung thì chủ điểm được xác định cụ thể hơn, tính phù hợp của mục truy
Chẳng hạn, nếu tò bottle xuất hiện trong các tài liệu được đánh số 5, 30
và 47, bản ghi cho bottle là vectơ (5, 25, 17).
Với ví dụ này có thể không giống như việc lưu trữ tài liệu với số lượng lớn,
nhưng đã cho thấy các thuật ngữ thường xuyên thì các ID gap trung bình sẽ nhỏ
1
hơn và những thuật ngữ hiếm xuất hiện dù sao cũng không chiếm quá nhiều không
gian, vì vậy cả hai trường hçfp đó đều có lọi.
Vấn đề tiếp theo là mã hóa những gap này vói số lượng lớn các bit hay biến
đổi, vì vậy một gap nhỏ yêu càu số các bit ít hơn nhiều so với một ID tài liệu. Mã
hóa nhị phân chuẩn gán cùng chiều dài cho tất cả các ký hiệu hay những giá tñ sẽ
được mã hóa, là tối ưu (nếu số các bit trong mã hóa giá trị X là L(x), yêu càu của
mã này là S.Ï Pr(-ĩ) LỌT) số các bit yêu càu để truyền một
kí hiệu). Một mã tối ưu giảm đến mức tối thiểu giá trị này khi tất cả các giá trị có
thể tương đương trừ các gap. Cách khác với mã đơn nguyên (một gap X được biểu
diễn bởi x-1 những dấu hiệu theo sau), ưu tiên những gap ngắn khá mạnh (nó là tối
ưu nếu gap theo sau được đưa ra bỏi Pr(X = x) = 2'
x
, xác suất của việc làm mất các
gap lớn).
Thông thường, một chỉ mục bị nén tói giới hạn thì việc nâng cấp rất hỗn độn
khi thêm, xóa hoặc sửa đổi các tài liệu. Ví dụ, nếu có tài liệu mới thì phải thêm vào
chỉ mục ngược, các bản ghi của một vài thuật ngữ sẽ tăng kích thước. Điều đó chỉ
có thể được giải quyết với nhiều I/o ngẫu nhiên tạo ra những việc cập nhật thay đổi
lớn.
1.3. Hệ thống khai thác thông tin
Các hệ thống khai thác thông tin có thể được công thức hóa một cách tổng
quát như một hàm <p = (r, D, Q, ơ) với T - {ti, t
2
, t
M
, w
q
t) với
q
k
fr và w
qk
Ể [0,1], Nhiệm vụ khai thác thông tin mang lại tập A =
{dji, dj2, , djml — D với truy vấn q với một hàm xếp hạng Ữ(Q, đjk).
Có ba mô hình tìm kiếm thông tin được sử dụng rộng rãi và khá phổ biến đó
là mô hình lý thuyết tập thô, mô hình không gian vectơ và mô hình xác suất.
1.4. Độ tương tự
1.4.1. Định nghĩa
Độ tương tự là một khái niệm quan trọng và đã được sử dụng rộng rãi. Các
định nghĩa trước đây về độ tương tự được trói buộc trong một ứng dụng cụ thể
hoặc một dạng thể hiện của tri thức.
Khái niệm về độ tương tự được định nghĩa thông qua các trực giác về độ
tương tự:
- Trực giác 1: Độ tương tự giữa A và B có liên quan tới sự tương đồng của chúng. Sự
tương đồng càng nhiều, độ tương tự càng lớn.
- Trực giác 2: Độ tương tự giữa A và B có liên quan tới những sự khác biệt giữa
chúng. Càng nhiều sự khác biệt độ tương tự càng thấp.
- Trực giác 3: Độ tương tự lớn nhất giữa A và B đạt được khi A và B giống hệt nhau.
1.4.2. Đô tưone tư giữa các giá tri có thứ tư ưu tiên
• o • o o • •
Rất nhiều các đặc trưng có các giá trị ưu tiên. Ví dụ, thuộc tính “chất lượng”
có thể mang một trong các giá trị sau: “excellent”, “good”, “average”, “bad”,
“awful”. Không có một định nghĩa nào ở trên cung cấp độ đo độ tương tự giữa hai
giá trị có thứ tự. Bây giờ sẽ chỉ ra cách định nghĩa có thể được áp dụng.
1
0
3
2
1
1
excellent
;
p
average
ba
Kết quả chỉ ra rằng độ tương tự giữa “excellent” và “good” cao hơn độ
tương tự giữa “good” và “average” độ tương tự giữa “excellent” và “average”
cao hơn độ tương tự giữa “good” và “bad”.
1.4.3. Độ tương tự chuỗi
Xem xét công việc tìm kiếm từ một danh sách từ các từ mà được xuất phát
từ cùng một gốc như là một từ có sẵn. Ví dụ, cho trước từ “eloquently”, mục
đích là để tìm ra các từ liên quan khác như “ineloquently”, “eloquent” và
“eloquence”. Để làm điều đó, có thể định nghĩa độ đo tương tự giữa hai chuỗi
và xếp hạng các từ ttong danh sách từ theo thứ tự giảm dần của độ tương tự
vói từ có sẵn. Những tò xuất phát từ cùng một từ gốc nên xuất hiện sớm trong
bảng xếp hạng.
Tiến hành thử nghiệm với 3 độ đo sau:
- Độ đo đầu tiên được định nghĩa như sau:
Smw,
t
(x,y) =
1+edlt
n
1-(lĩ
,
2
Độ đo độ tương tự ngữ nghĩa gần đây được áp dụng và phát triển trong
rất nhiều lĩnh vực như trong y học (so sánh gen), trong phân lớp văn bản (các
văn bản tương tự nhau thì cùng thuộc một lớp).
Mỗi lĩnh vực khác nhau có các cách để tính độ tương tự
ngữ nghĩa khác nhau. Sau đây, sẽ tìm hiểu các phương pháp
tính độ đo tương tự từ - từ và độ đo tương tự giữa văn
bản - văn bản.
CHƯƠNG 2: MỘT SỐ PHƯƠNG PHÁP TÌM KIẾM VĂN BẢN
2.1. Tìm kiếm văn bản theo mô hình tập thô dung sai
Hầu hết, các hệ thống thông tin làm việc chính xác bởi các toán tử
logic. Mặc dù, cách này đơn giản nhưng không phải lúc nào nó cũng mang
lại đúng theo ý ngưòi sử dụng. Hiện nay, có nhiều nỗ lực trong việc cải tiến
chất lượng khai thác thông tin vói việc sử dụng kỹ thuật tìm kiếm thông tín
cho suy diễn phát triển tò tính mập mờ (vagueness) và tính không chắc
chắn (uncertainty) của một khái niệm.
Lý thuyết tập thô, một công cụ toán học để giải quyết vấn đề ừên
được giới thiệu bởi Pawlak vào những năm 80. Lý thuyết tập thô này đã
thảnh công trong một vài ứng dụng. Trong lý thuyết này, mỗi thành phần
của tập vũ trụ được mô tả bởi một cặp hai tập họp khác được gọi là các xấp
xỉ trên và các xấp xỉ dưới. Tập các xấp xỉ trên và xấp xỉ dưới được xác định
bỏi quan hệ tương đương trong tập vũ trụ. Việc sử dụng mô hình tập thô
như trên sau này được gọi là mô hình tập thô tương đương (Equivalance
Rough Set Model ERSM) đã được sự quan tâm đặc biệt của nhiều nhà
nghiên cứu. Điểm quan trọng của việc áp dụng tập thô tương đương
(ERSM) cho việc khai thác thông tin đó đưa ra cách mới để tính mối quan
hệ ngữ nghĩa dựa trên việc tổ chức từ vựng vào các lớp tương đương. Tuy
nhiên chúng ta sẽ thấy rằng, việc sử dụng các quan hệ tương đương ừong
ERSM không phù hợp cho việc khai thác thông tin bởi các quan hệ tương
đương yêu cầu phải có các tính chất: Phản xạ, đối xứng, bắc càu. Trong một
đều dựa ừên ERSM dựa ừên sự giả định tập T của các term có thể được
phân chia vào các lớp tương đương xác định bởi quan hệ tương đương.
Một quan hệ tương đương R đòi hỏi 3 tính chất sau:
1- Tính phản xạ: xRx
2
2- Tính đối xứng: xRy -* yRx
3- Tính bắc cầu: xRy rì yRz —xRz (Vx,y,z £ Ư)
Tính bắc cầu không phải lúc nào cũng được thỏa mãn.
Các lớp chồng nhau có thể sinh ra bởi quan hệ dung sai trong quan hệ này
chỉ yêu cầu tính phản xạ và tính đối xứng. Vói sự xuất hiện của quan hệ
dung sai.
Không gian dung sai là không gian trong đó bao gồm các lớp chồng nhau
của các đối tượng trong tập vũ trụ. Một không gian dung sai được định
nghĩa bởi công thức chung R(U,I,V,P), trong đó: u là một tập các đối tượng,
I: Ư
là hàm không chắc chắn, V: 2
U
X 2“ -» [0,1] là thành phần mập mờ, P:
I(U) [0,1] là hàm cấu trúc.
Xem xét một đối tượng X được cho bởi thông tin f(x). Hàm không chính
xác I: u -*• 2
11
xác định I(x) như một lớp dung sai của tất cả các đối
tượng được xem xét có cùng thông tin với X. Hàm không chính xác được
định là những hàm thỏa mãn điều kiện: X £ I(x) và y € I(x) nếu X £ I(y)
với
x,y t u. Điều này tương đương với hàm tương ứng với một quan hệ Ç — ux
u. Trong đó X ç y nếu y £ I(x), Ç là một quan hệ dung sai bởi vì quan hệ này
thỏa mãn hai thuộc tính phản xạ và đối xứng.
Hàm mập mờ V:2
các lớp dung sai của các term. Có nhiều cách để xác định khái niệm các term
tương tự. Các đặc điểm của các term được chọn bởi tính chất sau:
1- Nó mang lại sự giải thích có ý nghĩa trong văn cảnh của khai thác thông
tin về sự phụ thuộc và quan hệ ngữ nghĩa của các term.
2- Nó là quan hệ đơn giản dễ máy tính hóa.
Cũng cần lưu ý rằng đặc điểm các term không có tính đối xứng và
không thể được sử dụng tự động để xác định các lớp tương đương. Với c (tị,
tj) là tần số xuất hiện đồng thời của hai term ti, tj trong D (tập các văn bản).
Định nghĩa hàm không chính xác I phụ thuộc vào ngưỡng 9 như sau:
Giả sử rằng tập r là đóng trong quá trình khai thác thông tin. Một truy
vấn Q bao gồm các từ khóa từ T. Với giả thuyết này có thể cho rằng tất cả các
2
Copyright: Tài liệu đại học ©