Đồ án Tìm kiếm văn bản tiếng Việt

hỉ giữ lại k hàng biểu diễn ý nghĩa quan trọng. Một trong những phương pháp thành công nhất cho dữ liệu văn bản lớn chỉ được số hoá. Kỹ thuật này cho phép chúng ta loại bỏ những cụm từ và nhóm cụm từ mà chúng ta phân biệt được giữa những tài liệu khác nhau. Với lượng các văn bản lớn để tạo bảng chỉ số từ các văn bản thì một trong những vấn đề cần giải quyết đó là bảng tần xuất có kích thước rất lớn. Để giảm bớt kích thước của bảng tần số nhỏ hơn nhiều so với (M x N). Kỹ thuật chỉ dẫn ngữ nghĩa tiềm ẩn (LSI) gồm các bước sau đây: Tạo bảng SVD: Bằng tính toán thực hiện phép phân tích thành giá trị riêng (A, S, B) của FreqT. Bởi phép phân tách FreqT vào trong 3 ma trận A, S, B. Đồng nhất với vectơ: Với mỗi tài liệu d đặt tương ứng với Vec (d) là tập hợp của tất cả các term trong Freqt mà những hàm tương ứng không bị loại trừ trong ma trận đơn S Tạo mục chỉ dẫn: Lưu trữ tập hợp của tất cả các Vec(d) đã được chỉ số theo con số đã qui định của kỹ thuật. Khi đã có một yêu cầu thu hồi tài liệu tương tự với một tài liệu truy vấn dQ thì chúng ta chỉ xem cấu trúc chỉ số được tạo ra ở trên và thử để tìm tài liệu d trong tập tài liệu lưu trữ sao cho vec (dQ) là bao đóng tới vec (d) với khoảng cách đã chọn trên vectơ. Quá trình phân tích giá trị riêng (Singular Value Decomposion SVD) Ta nói m x n là cấp của ma trận M nếu như nó có m hàng và n cột. Nếu M1 và M2 là các ma trận có cấp (m1 x n1) và (m2 x n2), nếu số cột n1 bằng số hàng m2 của ma trận M2 (n1 = m2) thì ta nói tích của M1 và M2 ký hiệu là M1 x M2 là một ma trận cấp (m1x n2) Ví dụ: Ta có 2 ma trận A và B A x B có cấp là (2 x 3) Tổng quát: Định nghĩa tích của hai ma trận Giả sử: Thì Trong đó (7) Ví dụ x Cho một ma trận M với cấp (m x n), chuyển vị của M1, ký hiệu là MT được thành lập bởi chuyển mỗi hàng của M thành cột tương ứng của MT. Sau đó, hàng đầu tiên của M được trở thành cột đầu tiên của MT, hàng thứ hai của M trở thành cột thứ hai của MT và tiếp tục, cho tới khi thứ m hàng của M trở thành thứ m cột của MT. Cuối cùng là một ma trận kích thước (n x m). Xem mỗi vectơ là một ma trận có cấp (n x m). Hai vectơ x và y cùng cấp là trực giao thì xTy = o Ví dụ: Giả sử có hai véc là trực giao (Orthogonal), bởi vì: xTy = (1 2 - 1) x Ma trận M là đã được nói là trực giao (Orthogonal) nếu (Mt x M) là ma trận đơn vị (ma trận có các phần tử trên đường chéo là 1). Với các từ khác nhau, M là một ma trận đường chéo. Nếu nó là một ma trận vuông và tất cả các phần tử trên đường chéo là 0. Cần lưu ý rằng không nhất thiết các phần tử trên đường chéo là khác 0. Chúng có thể bằng 0 hoặc khác 0. Ví dụ, cả hai ma trận A và B ở dưới là ma trận đường chéo, nhưng C thì không phải. A = B = C = Một ma trận đường chéo M có cấp (m x n) được nói là không tăng thêm với mọi : i £ j, j £ m,, i ¹ j => M(i,j) ³ M(j,j). Trong một số từ khác, đường chéo từ đỉnh tới cái đáy (đường chéo chính) giá trị giảm đi. Từ ví dụ trên, B là một ma trận chéo không tăng nhưng A thì ngược lại. Giả sử rằng FreqT là một bẳng tần số bất kỳ. Một biểu biễn theo giá trị riêng của FreqT là một bộ ba (A, S, B) Trong đó: FreqT = (A x S x BT) FreqT M x N Reduction giảm đi M x N J M x M M x M J M x R k x k DT R x k x N a) = x x Hình 3: Thu nhỏ kích thước qua SVD. A là một ma trận giao (Orthogonal) cấp (M x M) thật vậy ATA=I. B là một ma trận trực giao cấp (N x N) thật vậy BT. B= I S gọi là ma trận đường chéo gọi là ma trận đơn. Điều đó cho ta thấy rằng với ma trận bất kỳ có cấp (m x n), nó là có thể tìm một phân tích một phân tích theo giá trị riêng (A, S, B) của M. Như vậy, S là một ma trận chéo không tăng. Ví dụ phân tích theo giá trị riêng của 1.44 3.08 3.92 1.44 Là cho bởi 0.6 - 0.8 5 0 0.8 0.6 0.8 0.6 0 2 0.6 - 0.8 Trong đó, giá trị riêng là 5 và 2 dễ thấy rằng ma trận đơn không tăng. Nếu FreqT có kích thước (M x N) thì T có cỡ (M x M) và S là có cấp (MxR), trong đó R là bậc của FreqT và có cấp (R x N). Sau đây là các bước thực hiện: 1. Chọn một số nguyên k có giá trị thực sự nhỏ hơn R. 2. Thay thế S bởi S* là một ma trận (k x k) như S*(i,j) = S(i,j) với 1£ i, j£k. 3. Thay thế ma trận DT cấp (R x N) bởi ma trận D*T cấp (k x N) ở đây D*T(i,j)=DT(i, j) nếu 1 £ i£ k và 1 £ j £N. 4. Thay thế ma trận T (M x M) bởi ma trận T*(M x K) một cách tương tự. Sau đây chúng ta xét ví dụ về làm giảm kích thước ma trận dùng kỹ thuật LSI. Giả sử FreqT có SVD như sau: Do đó, khi hệ thống cơ sở dữ liệu văn bản có thể có thể chọn rất tốt sau khi đã làm kích thước của ma trận bởi sự loại trừ hai hàng và cột trước của ma trận đơn này. Kết quả là: Thông thường, kích thước của ma trận riêng trong trong vùng rộng hợp lý là 200. Với kích thước này nó có những ý nghĩa sau: 1. Kích thước của ma trận tần suất ban đầu là (M x N) ở đây M là số term của tất cả các văn bản và N số văn bản. Có thể dễ dàng nhận thấy số term M (số term) có thể lên đến hàng triệu và N (số văn bản) có thể lên đến hàng nghìn. 2. Kích thước của 3 ma trận sau khi chúng ta giảm kích thước của ma trận riêng(giả sử M=1.000.000 , R=200, N=10.000): + Kích thước của ma trận đầu tiên là M*R : 200 triệu đầu vào. + Kích thước của ma trận thứ hai là R*R: 40.000 đầu vào ( nhưng thực tế chỉ có 200 đầu vào cần lưu trữ, còn các đầu vào khác là bằng 0 ). + Kích thước của ma trận cuối cùng là R*N: 2 triệu đầu vào. Cộng tất cả lại chúng ta có khoảng 202 triệu đầu vào của bảng sau khi áp dụng SVD 3. Ngược lại, nếu áp dụng ngay trên ma trận nguyên ban đầu với kích thước là M*N thì số đầu vào sẽ là 10 tỉ. Nói một cách khác, SVD đã làm giảm không gian lưu trữ xuống 50 lần Chú ý: Những phân tích trên có phần hơi đơn giản vào khả năng có thể tin cậy của SVD. Trong nhiều trường hợp, ma trận ban đầu (m x N) là một ma trận thưa (sparse matrix). Nó sử dụng số đầu vào ít hơn so với M*N. Trong trường hợp này, việc dùng SVD có thể làm tăng số lượng vùng chứa cần thiết. 2.4.Tìm kiếm tài liệu dùng SVD Giả sử với biểu diễn SVD, T*S*D*T của một bảng tần suất. Trong phần này chúng ta xem xét sự biểu diễn này và trả lời câu hỏi. Cho hai tài liệu d1 và d2 trong một tập hợp các tài liệu văn bản lưu trữ, chúng “tương tự” thế nào? Cho một câu truy vấn Q, trong n văn bản thì văn bản nào “tương tự” nhất với Q. Trước hết chúng ta dưa vào khái niệm phép nhân vô hướng của hai vectơ (có cùng độ dài): Giả sử x = (x1, … ,Xw) và y = (y1, …, yw) là hai vectơ có giá trị thực. Thì tích vô hướng của x và y ký hiệu là xoy = . * Độ tương tự của tài liệu Giả sử di, và dj là hai tài liệu. Sự tương tự giữa tài liệu này với nhau liên quan tới sự biểu diễn SVD, TS* x D*T của bảng tần số đã cho bởi tính toán vô hướng của hai cột trong ma trận D*T liên kết giữa hai tài liệu này. (8) Trong đó, ma trận đơn sau sự thu nhỏ kích thước là (R x R). Thay vì so sánh thuật ngữ (term) M giữa 2 tài liệu này, chúng ta chỉ so sánh R. * Tìm kiếm tài liệu tương tự với truy vấn Q Giả sử Q là một truy vấn. Xem Q như một tài liệu và tạo một vectơ VecQ tương ứng của nó. Cho dù có một sự khác nhau, chỉ R term quan trọng là được xem xét chứ không phải tất cả N. Khi tìm tài liệu tương tự với truy vấn Q. Chúng ta phải đi tìm p tài liệu dQ(1), dQ(2), dQ(p) Với tất cả 1 £ i £ j £ p sự tương tự giữa vecQ và dQ(i) là quan trọng hơn hoặc bình đẳng với sự tương tự giữa vecQ và dQ(i). Với mục đích này một kỹ thuật cần thiết. TV_Tree được trình bầy trong phần sau nhằm giải quyết vấn đề này. 2.5. TV_Tree Để truy nhập chỉ số dữ liệu trong không gian kích thước rất lớn phải đạt hiệu quả cao. Chúng ta đã biết một tài liệu d có thể được xem như một vectơ d có chiều dài K. Với ma trận có giá trị riêng, sau khi phân tích, là có kích thước (k x k). 2.5.1. Thiết lập TV_Tree Trước khi định nghĩa TV_Tree để lưu trữ một điểm k chiều, chúng ta cần xác định 2 tham số sau: Numchild: Số lượng tối đa các con mà bất kỳ nút nào trong TV_Tree cho phép có. a: Một số lớn hơn 0 và nhỏ hơn hoặc bằng k gọi là số của chiều hoạt động. Chúng ta ký hiệu TV (k, NumChild, a) để biểu thị một TV_Tree được dùng để lưu trữ số liệu kiểu k chiều, với Numchild là số con lớn nhất và a là một số chiều được kích hoạt. Mỗi nút trong TV_Tree có 3 trường: N.Center: Đại diện cho 1 điểm trong không gian k chiều. N.Radius: Một số thực lớn 0 N.ActiveDims: Đây là danh sách tối đa a chiều. Mỗt một chiều đó là 1 số giữa 1 và k. Như vậy, N.ActiveDims là một tập con của (1,…,k). Giả sử x và y là 2 điểm trong không gian k chiều và ActiveDims là tập hợp nào đó của chiều hoạt động. Khoảng cách hoạt động (active_distance) giữa x và y, ký hiệu bởi act_dist (x,y) và được biểu diễn bằng công thức: act_dist (x, y) = (9) Trong đó xi và yi biểu thị giá trị của chiều thứ i của x và y tương ứng. Ví dụ: Giả sử k = 200, a = 5 và tập hợp ActiveDims = (1..5). Giả sử x = (10, 5, 11, 13, 7, x6, x7,…,x2000) y = (2, 4, 14, 8, 6, y6, y7,…y2000) Vậy khoảng cách hoạt động tương ứng là: act_dist(x,y)= Một nút N trong TV_Tree đại diện cho vùng chứa tất cả các điểm x như vậy khoảng cách hoạt động (với tương ứng tới chiều hoạt động trong N.ActiveDims) giữa x và N.Center nhỏ hơn hoặc bằng N.Radius. Ví dụ: nếu ta có nút N với center của nó. N.Center = (10, 5, 11, 13, 7, 0, 0, 0, 0,…, 0). N.ActiveDims = {91, 2, 3, 4, 5} thì nút này đại diện cho vùng gồm tất cả các điểm x như sau: £ N.Radius Ký hiệu Region (N) để biểu thị vùng được đại diện bởi nút N trong TV_Tree. Ngoài Center, Radius và ActiveDims, 1 nút trong cây TV_Tree cũng chứa một mảng, Child hoặc Numchild là con trỏ tới nút khác có cùng kiểu. Tất cả các dữ liệu được lưu trữ ở nút lá. Mỗi nút trong cây TV (kể cả gốc và lá) phải ít nhất là chứa một nửa (half full) có nghĩa là ít nhất con trỏ Child không chứa Nil. Nếu N là một nút và chứa một tập các nút con N1, N2, Nr thì Region (N) = Region(Ni). 2.5.2.Chèn vào TV_Tree Có 3 bước để chèn một vectơ vào cây TV. Chọn nhánh (branch selection): Khi ta chèn một vectơ vào cây TV mà ta dang ở nút Nj có con là Ni và 1 £ i £ NumChiild. Ta cần xác định con nào sẽ được chèn khoá vào. Tách (Split): Ta dùng phương pháp này khi ta ở nút và nó đã đầy (full) và không thể chứa thêm vectơ v mà ta cần chèn. Vấn đề này là nguyên nhân cần tách các nút. Thu gọn (Telescoping): Giả sử 1 nút N được tách vào 2 nút N1 và N2. Trong trường hợp này, có thể sản sinh vectơ trong Region(N1) chấp thuận hoặc không chiều hoạt động của nút cha N. Việc thêm một số chiều được gọi là lồng động mà chúng ta se xem xét sau đây. Lựa chọn rẽ nhánh: Xét tình huống khi có nút N với 1 ³ j, =NumChild con ký hiệu là n1,…,Numchilds. Dùng ký hiệu expj(v) để biểu thị số lượng. Ta phải mở rộng Nj, Radius như vậy khoảng cách hoạt động của v từ Nj, Center nhỏ hơn hoặc bằng với (Nj (v), Radius +expj(v)). Expj(v) = 0 nếu act_dist(v, Rj, Center), £ Rj, Radius Hoặc expj(V) = act_dist(v, R, Center) – Rj.Radius nếu act_dist(v,Rj, Center) > Rj.Radius. Đầu tiên ta chọn tất cả do vậy expj(v) giảm đến mức tối thiểu. Cách nói khác, nếu ta có nút N1,…, N5 với exp có giá trị 10, 40, 19, 10 ,32 tương ứng, hai ứng viên khả thi của việc chọn để chèn là N1 & N4 vì sự mở rộng của chúng là nhỏ nhất. 2.5.3.Tìm kiếm trên TV_Tree Tìm kiếm một vectơ v trong TV_Tree chỉ là phụ trong quá trình chèn. Khi tìm kiếm một văn bản đại diện bởi vectơ trong TV_Tree, ta có cách giải quyết sau: ThuËt to¸n 1 Search (T, V); if leaf (t) then {Return (T, Center = v); Half} {if v Î Region (T) then Return VNumchild Search (t, child [i], v)} end Thuật toán tìm kiếm trên cây TV_Tree ThuËt to¸n 2 : NNSearch (T, v, p); For i = 1 to p do SOL [i] = ¥; NNSearch 1 (T, v, p); end: (* kết thúc NNSearch*) Procedure NNSearch 1 (T, v, p); if leaf (T) & act_dist (T, val, v) < SOL [p] then Insert T. vail into Sol Else { if lef (T) then r = 0 else {Let N1,...,Nr Là con của; S¾p cÕp Nis t¨ng dÇn víi liªn quan tíi min (Ni, v); §Ó Nh [r] lµ kÕt qu¶ cña s¾p xÕp. } done = false; i = 1; While ((i < r) ^ Ø done) do } NNSearch (Nh [i], v, p); if SOL [p], min (Nh [i = 1], v) then done = true; i = i +1; }; } Return SOL; Thuật toán tìm kiếm lân cận gần nhất trên TV_Tree LSI đã được chứng minh là một trong những phương pháp hiệu quả để lập bảng chỉ dẫn cho văn bản. Tuy nhiên, có một số kỹ thuật khác được sử dụng hiệu quả hơn so với cơ sở dữ liệu văn bản nhằm giải quyết được thời gian và độ phức tạp thuật toán thực hiện 3. 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 thông tin đúng theo ý của người sử dụng. Hiện nay, có rất 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 các kỹ thuật tìm kiếm thông tin 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 đề trên với sự mập mờ và không chính xác được giới thiệu bởi Pawlak trong 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à tập các xấp xỉ dưới được xác định bởi quan hệ tương đương trong tập vũ trụ. Việc xử 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 rất 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 đó là đư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ẽ nhận thấy rằng, việc sử dụng các quan hệ tương đương trong ERSM là không phù hợp cho việc khai thác thông tin. Điều này là đúng bởi 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. Tuy nhiên trong một số trường hợp các tính chất này tỏ ra quá nghiêm ngặt trong việc xử lý ngôn ngữ tự nhiên và khai thác thông tin bởi vì tính chất đối xứng không phải lúc nào cũng được thoả mãn. Vì lý do trên nên ở đây chúng ta làm quen với một mô hình khác gọi là mô hình tập thô dung sai(Tolerance Rough Set Model TRSM) cho việc khai thác thông tin qua các lớp dung sai thay thế cho các lớp tương đương đã giới thiệu ở trên. Đây chính là mô hình mà tôi sẽ nghiên cứu kỹ và sẽ cài đặt để phục vụ cho việc tìm kiếm văn bản tiếng Việt. 3.1 Khái niệm tập thô và không gian dung sai Lý thuyết tập thô được phát triển từ giả định rằng để định nghĩa một tập vũ trụ ta cần phải biết một số thông tin (hay tri thức) về các phần tử của tập vũ trụ. Trái với cách tiếp cận cổ điển, định nghĩa tập hợp một cách duy nhất dựa trên các phần tử của tập đó và không cần thêm bất cứ thông tin gì về các phần tử của tập (thông tin về các phần tử có thể biểu diễn. Ví dụ như dưới dạng thuộc tính-giá trị mà đôi khi được gọi là hệ thông tin). Hiển nhiên, là đối với một số phần tử, thông tin của chúng có thể tương tự nhau và do đó các phần tử này không thể phân biệt được một cách rõ ràng nếu chỉ nhìn từ thông tin về chúng. Quan hệ không phân biệt được chính là điểm khởi đầu của lý thuyết tập thô và quan hệ này chỉ ra rằng sự mập mờ và không chắc chắn có quan hệ chặt chẽ với tính không phân biệt được và chúng có thể định nghĩa dựa trên các cơ sở của quan hệ này. Điểm đầu tiên của lý thuyết tập thô là mỗi tập X trong tập vũ trụ U có thể được xem xét một cách xấp xỉ bởi các xấp xỉ dưới và xấp xỉ trên trong một không gian xấp xỉ R=(U,R) với RÍ U´U là một quan hệ tương đương. Hai đối tượng x,y ÎU được xem là không phân biệt được trong R nếu xRy. Các xấp xỉ dưới và trên trong R của các tập XÍU, biểu diễn bởi L(R,X) và U(R,X) được định nghĩa bởi công thức sau: L(R,X)={xÎU :[x]R ÍX} (1) U(R,X)={xÎU :[x]R Ç X ¹ Æ} (2) Trong đó: [x]R biểu diễn lớp các đối tượng tương đương không phân biệt được với x trong quan hệ R . Tất cả các công việc ban đầu của khai thác thông tin sử dụng tập thô đều dựa trên ERSM dựa trê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- Tính đối xứng : xRy ® yRx 3- Tính bắc cầu : xRy Ç yRz ® xRz (" x,y,z Î U) 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ể được 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 chúng ta có khái niệm không gian 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, n,P) trong đó U là tập các đối tượng, I : U ® 2u là hàm không chắc chắn, n:2ux2u®[0,1] là thành phần mập mờ, P: I(U) ® [0,1] là hàm cấu trúc. Chúng ta xem xét một đối tượng x được cho bởi thông tin inf(x). Hàm không chính xác I : U ® 2u 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 nghĩa là những hàm thoả mãn điều kiện: x ÎI(x) và yÎI(x) nếu xÎI(y) với x,yÎU. Điều này tương đương với hàm tương ứng với một quan hệ V ÍU x U trong đó xVy nếu yÎI(x). V là một quan hệ dung sai bởi vì quan hệ này thoả mãn hai thuộc tính phản xạ và đối xứng . Hàm mập mờ n : 2u x 2u ® [0,1] đánh giá mức độ của các tập trong tập vũ trụ, trong trường hợp đặc biệt nó liên quan đến câu hỏi lớp dung sai I(x) của đối tượng xÎU có thuộc tập X không ? Trong hàm n còn yêu cầu tính đơn điệu đối với tham số thứ hai : n(X,Y)£n(X,Z) với YÍ Z , X, Y,Z ÍU. Cuối cùng, với hàm cấu trúc P được đề xuất bởi việc phân tích với hình thái toán học. Trong việc xây dựng các xấp xỉ trên và dưới chỉ một số các tập dung sai được coi là các yếu tố có cấu trúc. Chúng ta định nghĩa hàm P: I(U) ® [0,1] các lớp I(x) với mỗi xÎU thuộc vào hai lớp: Các tập hợp con có cấu trúc (P(I(x))=1) và không có cấu trúc (P(I(x))=0). Xấp xỉ dưới L(R,X) và xấp xỉ trên U(R,X) trong R với XÎU được xác định như sau: L(R,X) = {xÎU \ P(I(x))=1 & n(I(x),X)=1 } (3) U(R,X)= {xÎU \ P(I(x))=1 & n(I(x),X) > 0} (4) Vấn đề cơ bản của việc sử dụng không gian dung sai trong các ứng dụng là làm thế nào để xác định được các hàm I, n và P phù hợp. 3.2 Mô hình tập thô dung sai (TRSM) trong việc khai thác thông tin 3.2.1 Không gian dung sai: Trước hết chúng ta mô tả cách xác định các hàm I, n và P phù hợp cho việc khai thác thông tin. Đầu tiên, để định nghĩa không gian dung sai chúng ta chọn tập vũ trụ U là tập t của tất cả các terms. U={t1, t2 ,…, tM}= t (5) Vấn đề cốt yếu trong công thức của TRSM trong khai thác thông tin là 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 các 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 và dễ máy tính hoá Chúng ta cũng cần lưu ý rằng đặc điểm của 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 (ti ,tj) là tần số xuất hiện đồng thời của hai term ti và tj trong D (Tập các văn bản). Chúng ta định nghĩa hàm không chính xác I phụ thuộc vào ngưỡng q như sau: Iq(ti) ={tj | c(ti ,tj ) ³q }È {ti} (6) Hàm mập mờ n được xác định như sau: n(X,Y) = | XÇY | / |X| (7) Hàm này đơn điệu với mối quan hệ trong tham số thứ 2. Dựa trên hàm này chúng ta xây dựng một hàm thành viên quan trọng m như sau: m(ti,X)= n(Iq(ti),X) = | Iq(ti) ÇX | / | Iq(ti)| (8) Giả sử rằng tập t là đóng trong quá trình khai thác thông tin. Một truy vấn Q bao gồm các từ khoá từ t. Với giả thiết này chúng ta có thể cho rằng tất cả các lớp dung sai của các term là các lớp con có cấu trúc (P(Iq(ti))=1 với ti Ît). Với những định nghĩa trên chúng ta đã đạt được không gian dung sai R=(t,I,n,P) trong đó xấp xỉ trên và xấp xỉ dưới trong R của các tập hợp con XÌ t có thể được xác định như sau: L(R,X)={ti Ì t | n(Iq(ti),X)=1} (9) U(R,X)={tiÌt | n(Iq(ti),X)>0} (10) Để minh hoạ cho phần lý thuyết trên chúng ta hãy xem xét một cơ sở dữ liệu nhỏ gồm có 10 tài liệu về chủ đề “học máy” được cho trong bảng dưới đây. Các từ khoá trong tập vũ trụ nhỏ được thể hiện bởi các biến ti như sau: t1=”học máy”, t2=”thu nhận tri thức” ,…, t30=”mạng nơ ron”, t31=”lập trình logic” . Với ngưỡng q = 2 bởi công thức (6) chúng ta có các lớp dung sai của các chỉ mục I2(t1)={t1, t2 , t5 , t16}, I2(t2)={t1, t2 ,t4, t5 , t26}, I2(t3)={t3}, I2(t4)={t2, t4}, I2(t5)={t1, t2 , t5 }, I2(t6)={t6, t7 }, I2(t16)={t1, t16} I2(t26)={t2 ,t26} còn lại đối với các term khác có lớp dung sai tương ứng chính là bản thân nó. No. Các từ khoá của tài liệu D1 máy học, thu nhận tri thức, biểu diễn tri thức,cơ sở tri thức, lập luận D2 máy tri thức, trí tuệ nhân tạo , ứng dụng, kỹ nghệ D3 lập luận, học máy, lập luận tình huống, giải quyết vấn đề, thu nhận tri thức D4 máy tri thức, trí tuệ nhân tạo, thiết kế bằng máy tính, tích hợp mức độ cao, thiết kế số D5 thu nhận tri thức, phương thức xây dựng ống, cơ sở tri thức D6 học máy, học quy nạp, học từ khái niệm, học có mẫu, học từ quan sát và phát hiện, phân nhóm khái niệm D7 học dựa trên giải thích, điều khiển vĩ mô, biên dịch tri thức, cấp độ tri thức, phân loại tri thức D8 Thu nhận tri thức, thiết kế bằng máy tính, hệ chuyên gia, thiết kế bố trí thiết bị D9 hệ chuyên gia, thu nhận tri thức, hệ phỏng vấn D10 học máy, học quy nạp, học dựa trên giải thích, hệ chuyên gia, liên kết, mạng nơ ron, lập trình logic Bảng 2: Thông tin về 10 văn bản tiếng Việt No. Từ khoá L(R,di) U(R,di) D1 t1, t2, t3, t4, t5 t3, t4, t5 t1, t2, t3, t4, t5, t16, t26 D2 t6, t7, t8, t9 t6, t7, t8, t9 t6, t7, t8, t9 D3 t5, t1, t10, t11, t2 t5,t10, t11 t1, t2, t3, t4, t5, t10,t11,t16 t26 D4 t6, t7, t12, t13, t14 t6, t7, t12, t13, t14 t6, t7, t12, t13, t14 D5 t2,t15,t4 t15,t4 t1,t2,t4,t5, t15, t26 D6 t1, t16, t17, t18, t19,t20 t1, t16, t17, t18, t19,t20 t1 , t2 , t5, t16, t17, t18, t19 ,t20 D7 t21, t22, t23, t24, t25 t21, t22, t23, t24, t25 t21, t22, t23, t24, t25 D8 t2, t12, t26, t27 t12, t26, t27 t1 , t2 , t4 , t5 , t12, t26 ,t27 D9 t26, t2, t28 t26 , t28 t1 , t2 , t4 , t5 , t26, t28 D10 t1, t16, t21, t26, t29, t30, t31 t16, t21, t26, t29, t30, t31 t1, t2 , t5, t16, t21, t26, t29, t30, t31 Bảng 3: Biểu diễn các xấp xỉ trên và dưới của 10 văn bản 3.2.2 Giải thuật tìm kiếm văn bản sử dụng TRSM Kết quả mang lại giữa truy vấn của người sử dụng và các tài liệu có thể thực hiện bởi việc kiểm tra các cấp độ khác nhau của các thành phần thô giữa các xấp xỉ dung sai. Có 12 cấp độ của các thành phần giữa hai tập có thể xuất hiện trong khi so sánh tập các term trong truy vấn q với tập các term trong mỗi tài liệu dj. 1- Định nghĩa: đây là cấp độ đơn giản và chính xác nhưng rất hiếm khi tồn tại : q = dj [1-1] 2- Tương đương thô : với các tập X,Y Ít Nếu L(R,X)=L(R,Y) thì X,Y được gọi là tương đương thô dưới. Tương tự nếu U(R,X)=U(R,Y) thì X,Y được gọi là tương đương thô trên. Khi X và Y thoả mãn cả hai tính chất trên thì ta nói X và Y là tương đương thô. Với truy vấn q ta có các trường hợp sau: q là tương đương thô với văn bản dj [2-1] q là tương đương thô dưới với văn bản dj [2-2] q là tương đương thô trên với văn bản dj [2-1] 3- dj bao hàm thô q: Với các tập X,Y Ít. Nếu L(R,X) Í L(R,Y) thì X được gọi là thành phần thô dưới trong Y. Tương tự nếu U(R,X) Í U(R,Y) thì X được gọi là thành phần thô trên trong Y. Khi X và Y thoả mãn cả hai tính chất trên thì ta nói X thành phần thô trong Y. Với truy vấn q ta có các trường hợp sau: q là thành phần thô trong văn bản dj [3-1] q là thành phần thô dưới trong văn bản dj [3-2] q là thành phần thô trên trong văn bản dj [3-3] 4- q bao hàm thô dj (ngược với 3): Với q là một truy vấn ta có các trường hợp sau: Văn bản dj là thành phần thô trong q [4-1] Văn bản dj là thành phần thô dưới trong q [4-2] Văn bản dj là thành phần thô trên trong q [4-3] 5- Chồng thô: Điều này có thể xảy ra khi xấp xỉ trên và dưới dung sai của q và dj là chồng nhau L(R,q) Ç L(R,dj ) ¹Æ [5-1] U(R,q) Ç U(R,dj ) ¹Æ [5-2] Chúng ta hãy xem xét một ví dụ của các quan hệ thô trong tập 10 tài liệu đã giới thiệu ở trên với một truy vấn q={học máy, hệ chuyên gia}={t1,t26}. Chúng ta xác định được xấp xỉ trên và dưới của q trong không gian dung sai được định nghĩa như trên với ngưỡng q=2: L(R,Q)=Æ , U(R,Q)={t1,t2,t5,t16,t26} So sánh các xấp xỉ trên với bảng các xấp xỉ của các tài liệu dj chúng ta thấy q là thành phần thô trên của các tài liệu dj với j = 1,3,10 và chồng thô dưới đối với các văn bản dj với j = 1 , 3 , 5 , 6 , 8 , 9 , 10. Chúng ta biểu diễn A11, A12,…, A52 tương ứng là tập các tài liệu thoả mãn các điều kiện [ 1-1] ,[ 2-1] ,…, [ 5-2] Một cách tổng quát ta có Akl ={dj ÎD | dj thoả mãn điều kiện [k-l] } đối với truy vấn q. A11:=Æ; A11:= Æ; … A52:= Æ ; For j =1 to |D| do begin If Q = dj then A11:=A11 È ídjý; Else If L(R,Q) ¹ Æ then If L(R,Q) = L(R,dj)