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

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) then begin A22:=A22 È ídjý; If U(R,Q) = U(R,dj) then A21:= A21È ídjý end; If U(R,Q) = U(R,dj) then A23:= A23È ídjý ; Else If L(R,Q) ¹ Æ then If L(R,Q) Ì L(R,dj) then begin A32:=A32 È ídjý; If U(R,Q) Ì U(R,dj) then A31:= A31È ídjý End; If U(R,Q) Ì U(R,dj) then A33:= A33È ídjý ; Else If L(R,Q) ¹ Æ then If L(R,dj) Ì L(R,Q) then begin A42:=A42 È ídjý; If U(R,dj) Ì U(R,Q) then A41:= A41È ídjý End; If U(R,dj) Ì U(R,Q) then A43:= A43È ídjý ; Else If L(R,Q) Ç L(R,dj) ¹ Æ then A51:= A51È ídjý ; If U(R,Q) Ç U(R,dj) ¹ Æ then A52:= A52È ídjý ; end Giải thuật TRSM ThuËt to¸n TRSM 3.3 Hàm xếp hạng chính và xếp hạng phụ trong việc đánh giá mức độ chính xác của tài liệu. Việc xác định độ chính xác giữa truy vấn của người sử dụng và các tài liệu được khai thác chúng ta sử dụng hàm xếp hạng chính a: Q ´ D® R+ Có một vấn đề trong việc khai thác thông tin từ các nhận xét về độ chính xác là chủ quan và không chắc chắn. Khi một số yếu tố để đưa ra sự nhận định về độ chính xác là tương đối phức tạp, chính vấn đề này đã được nhận biết rằng các mô hình khai thác thông tin không thể chọn chính xác tuyệt đối các tài liệu theo yêu cầu. Điều này đã gợi cho chúng ta xây dựng một hàm xếp hạng rời rạc dựa trên 12 cấp độ khai thác đồng thời xây dựng một hàm xếp hạng phụ cho cấp độ được xác định bởi [5-1] và [5-2]. Với các xấp xỉ dưới là tập các thành phần chắc chắn thuộc về tập các đối tượng cần tìm, và các xấp xỉ trên là tập các đối tượng có thể thuộc tập đó. Chúng ta có thể thấy các xấp xỉ dưới có vai trò mạnh mẽ và quan trọng hơn các xấp xỉ trên. Với đặc điểm này kết hợp với các yếu tố ở trên cho phép chúng ta thiết lập được một hàm xếp hạng độ chính xác cho 12 cấp độ khai thác thông tin của các tài liệu. Chúng ta xem xét 12 cấp độ khai thác thông tin A11, A12 ,…, A52 theo thứ tự giảm dần của độ chính xác với một truy vấn q bất kỳ và một hàm a(Q,dj) xác định mức độ mập mờ như nhau đối với tất c các tài liệu trong cùng một cấp độ. Với hàm cấp độ này chúng ta có thể thấy A11 là tập của các tài liệu hầu như chính xác đối với truy vấn q. Một điểm quan trọng cần lưu ý là trong chiến lược của chúng ta trong các cấp độ A11 , A12 ,…,A43 cho chúng ta số lượng các tài liệu là không lớn lắm nhưng với cấp độ A51, A52 thì có thể mang lại số lượng lớn các tài liệu, điều này tỏ ra không thuận lợi đối với chúng ta. Để giải quyết vấn đề đó chúng ta sử dụng một hàm xếp hạng phụ thực hiện phân chia hai tập này vào các tập con trong đó các thành phần trong mỗi tập con là có cùng độ chính xác. Hàm xếp hạng phụ này được thiết lập thông qua hàm mập mờ được định nghĩa trong (7). Trong thực tế mỗi tài liệu dj được chia vào một trong | Q | +1 nhóm con dựa trên giá trị : n(Q,dj) = | Q Ç dj | / | Q | (12) Chúng ta nhận thấy rằng các tài liệu trong mỗi nhóm con có cùng độ chính xác tương đương với chúng có cùng số từ khoá chung với truy vấn q. Một cách tổng quát chúng ta có được 2*| Q | +12 các nhóm con của các tài liệu với độ chính xác giảm dần. TRSM cũng phát triển một chiến lược xếp hạng khác từ chiến lược xếp hạng của ERSM thông qua việc lọc ra các xếp hạng rời rạc bởi công thức sau: TSIM(Q , dj ) = | L(R,Q) Ç L(R,dj) | / | L(R,Q) È L(R,dj) | + | U(R,Q) Ç U(R,dj) | / | U(R,Q) È U(R,dj) | (13) Chúng ta không thể ức lượng so sánh một cách thực nghiệm giữa chiến lược xếp hạng của ERSM và TRSM bởi vì ERSM phụ thuộc mạnh vào cách xây dựng không gian xấp xỉ. Khi trọng lượng của các term là có sẵn, với việc sử dụng hàm thành viên m(tj,Q) trong (8) hàm xếp hạng có thể được xác định như sau : a(Q,dj) = Swji ´ m(tji,Q) với tji Î dj (14) PHẦN II. PHƯƠNG ÁN GIẢI QUYẾT VÀ CÀI ĐẶT THỬ NGHIỆM I. PHƯƠNG ÁN GIẢI QUYẾT Như chúng ta đã biết, nhiệm vụ của hệ thống tìm kiếm văn bản là phải xử lý dữ liệu ở dạng phi cấu trúc. Các hệ thống tìm kiếm văn bản tập chung vào hai lĩnh vực chính là tìm kiếm và duyệt. Tìm kiếm được xử dụng khi người dùng đã biết chính xác họ muốn tìm văn bản về lĩnh vực cũng như chủ đề gì còn duyệt là được xử dụng khi người dùng chưa biết chính xác cái mà hộ muốn tìm. Tìm kiếm và duyệt bổ xung lẫn nhau và tỏ ra hết sức hiệu quả khi ta kết hợp cả hai kỹ thuật theo thứ tự thích hợp. Kỹ thuật duyệt có thể được sử dụng để phát hiện các chủ đề cần tìm kiếm sau đó áp dụng kỹ thuật tìm kiếm trên kết quả. Có rất nhiều mô hình tìm kiếm thông tin đã được xây dựng để phục vụ cho việc tìm kiếm văn bản. Mỗi mô hình tìm kiếm đều có các tiêu chí tìm kiếm khác nhau, kỹ thuật áp dụng cũng khác nhau nhưng chúng đều phải xây dựng dựa trên các các mục tiêu cụ thể đó là: Biểu diễn văn bản. Biểu diễn truy vấn. Hàm tìm kiếm Nhờ có mô hình tìm kiếm thông tin, mỗi văn bản được biểu diễn bằng tập của một số thành phần đặc trưng đó là các term. Mỗi term sẽ được ánh xạ thành một điểm trong không gian nhiều chiều hơn. Tuỳ theo từng mô hình, không gian này có thể là không gian vector n chiều (với mô hình không gian vector), không gian tập thô dung sai (với mô hình tập thô dung sai)… Mô hình Phương pháp đánh giá Xếp hạng trọng lượng term Chi phí Toán tử logic Chính xác Không Không Thấp Không gian vector Không chính xác Liên tục Có Trung bình Tập thô Không chính xác Rời rạc Có Thấp Bảng 4: Các đặc trưng cơ bản của một số mô hình tìm kiếm thông tin Trong các mô hình tìm kiếm thông tin đã được đưa ra, chúng ta thấy mỗi một mô hình có những điểm mạnh và điểm hạn chế nhất định. Nhưng qua nghiên cứu ta thấy mô hình lý thuyết tập thô thể hiện được những điểm mạnh nhất là trong việc khai dữ liệu phá văn bản nói chung và việc tìm kiếm văn bản tiếng Việt nói riêng. Mô hình lý thuyết tập thô dung sai được xây dựng dựa trên mô hình lý thuyết tập thô nhưng đồng thời nó đã khắc phục được những nhược điểm của mô hình lý thuyết tập thô. Mô hình tập thô dung sai đã sử dụng các lớp dung sai thay cho việc sử dụng các lớp tương đương như mô hình tập thô đã sử dụng. Cụ thể là có thể loại bỏ được tính chất đối xứng, một trong những tính chất khá nghiêm ngặt của mô hình lý thuyết tập thô. Vì lý do trên cộng với một khả năng mà mô hình tập thô dung sai có thể giải quyết được vấn đề đồng nghĩa cho nên em chọn mô hình này để nghiên cứu chi tiết để áp dụng trực tiếp vào bài toán tìm kiếm văn bản tiếng Việt. Phần trên chúng ta đã tìm hiểu về khả năng của TRSM trong việc khai thác thông tin. Dưới đây chúng ta sẽ xây dựng một mô hình cụ thể để có thể phục vụ cho việc tìm kiếm văn bản tiếng Việt dựa trên mô hình tập thô dung sai. Để giải quyết bài toán tìm kiếm văn bản tiếng Việt trong cơ sở dữ liệu văn bản chúng ta phải làm một loạt các công việc như tiền xử lý văn bản, tách từ, chích lọc các từ đại diện cho văn bản, kỹ thuật lưu trữ từ điển và và sử dụng mô hình tập thô dung sai để tìm kiếm văn bản. Nếu các công việc trên được xử lý tốt thì kết quả của việc tìm kiếm sẽ đạt hiệu quả cao hơn. Yêu cầu xử lý dữ liệu Đối với bài toán phân nhóm cũng như các bài toán tìm kiến văn bản, dữ liệu đầu vào phải được tiền xử lý để tìm được các đặc tính cơ bản. Cụ thể trong bài toán văn bản tiếng Việt, văn bản đầu vào phải được tiền xử lý để tách thành các term. Sau đó chọn ra các term đại diên cho văn bản từ đó có thể áp dụng kỹ thuật tính lớp dung sai cho từng term sau đó tính lớp xấp xỉ trên và xấp xỉ dưới cho từng văn bản. Tách các term từ văn bản Xây dựng một lược đồ mã hoá term-ID nhằm tiết kiệm không gian lưu trữ và tăng tốc độ xử lý nhờ không phải làm việc trực tiếp với văn bản nguyên thuỷ. Gán trọng số cho các term đã tách. Xây dựng tập các từ đại diện cho văn bản. Chức năng này có thể loại bỏ các term có trọng số nhỏ hơn một ngưỡng nào đó nhằm tăng tốc độ tính toán và giảm không gian lưu trữ. Trong bài toán phân nhóm văn bản dùng mô hình tập thô dung sai này, quá trình tiền xử lý còn có thể thực hiện công việc sau: Xác định các lớp dung sai cho các term Xác định các xấp xỉ trên và xấp xỉ dưới cho mỗi văn bản đầu vào. Trong tất cả các hệ thống, việc đọc từ bộ nhớ ngoài (đĩa từ) luôn có tốc độ thấp hơn rất nhiều so vơi đọc từ bộ nhớ trong. Do vậy, quá trình tiền xử lý phải được tổ chức sao cho số lần đọc dữ liệu từ bộ nhớ ngoài là tối thiều và dung lượng bộ nhớ trong sử dụng là tối đa. Các phương pháp tách từ tiếng Việt Một văn bản tiếng Việt, hay cụ thể hơn là một câu tiếng Việt có thể được tách thành các từ theo các phương pháp sau. Mỗi phương pháp đều có những hạn chế nhất định. Do đó, chúng ta phải chọn một phương pháp hợp lý và phù hợp với yêu cầu của từng bài toán cụ thể. Phân tích cú pháp tiếng Việt. Phương pháp này cho kết quả rất tốt nhưng do đặc điểm ngữ pháp của tiếng Việt, việc thiết kế và cài đặt được một chương trình phân tích cú pháp gặp rất nhiều khó khăn. Thống kê tần suất xuất hiện. Phương pháp này đã được nghiên cứu và áp dụng với một số ngôn ngữ như tiếng Anh, tiếng Pháp trong trường hợp muốn tách một cụm từ. Phương pháp này xác định một cụm từ dựa trên tần suất xuất hiện cạnh nhau của các từ nằm trong cụm từ đó. Phương pháp này đơn giản hơn phương pháp phân tích cú pháp nhưng phải quét qua toàn bộ văn bản để tính toán xác suất xuất hiện. Đối với từ ghép tiếng Việt, việc tính toán này là không cần thiết. Dựa vào từ điển. Đây là phương pháp đơn giản nhất do văn bản được tách chỉ dựa vào từ điển. Ta không phải quét qua toàn bộ văn bản hoặc toàn bộ câu mà chỉ lấy một số hình vị đủ dài rồi tìm trong từ điển. Phương pháp này có thể sử dụng tốt khi từ điển đầy đủ. Nhược điểm chính của phương pháp này là không phân biệt được các từ đồng âm khác nghĩa. Như đã trình bày ở trên, phương pháp tách từ dựa vào từ điển là phương pháp đơn giản nhất và có hiệu quả tương đối tốt do các từ đồng âm khác nghĩa thường xuất hiện rất ít trong cùng một văn bản tiếng Việt. Do vậy, chúng ta sẽ chọn phương pháp này làm công cụ tách từ trong quá trình tiền xử lý văn bản tiếng Việt. 1. Nhập văn bản cần tách 2. Thực hiện tách văn bản đầu vào thành các câu 3. Đọc câu tiếp theo trong văn bản 4. Đọc hình vị tiếp theo w trong câu cần tách 5. Lấy l là số hình vị tối đa của từ có hình vị đầu tiên là w 6. Đọc l hình vị vào word Nếu tìm thấy word trong stoplist 7. Xoá l hình vị khỏi câu cần tách 8. Trong khi không tìm thấy word trong từ điển và stoplist và l>0 Xoá hình vị cuối cùng khỏi word giảm l đi 1 lặp lại bước 8 Nếu l>0 thực hiện công việc tiền xử lý tiếp theo đối với word Xoá l hình vị khỏi văn bản đầu vào Ngược lại: bổ xung w vào tập không tách được Xoá 1 hình vị khỏi câu đầu vào 9. Lặp lại từ bước 4 cho đến khi câu rỗng. 10. Lặp lại từ bước 3 cho đến khi tất cả các câu trong văn bản được tách Giải thuật tách từ tiếng Việt Loại bỏ các từ mang ít thông tin Văn bản tiếng Việt thường có rất nhiều từ không mang hoặc mang ít thông tin. Những từ này chỉ có chức năng bổ sung ý nghĩa cho từ (thường là danh từ) đứng bên cạnh nó (ví dụ như: các , cái, con, những,…) hoặc đóng vai trò là liên từ giữa các thành phần trong câu (ví dụ như: và, mặc dù, cho nên…). Rõ ràng là việc để lại các từ mang ít thông tin (từ bây giờ được gọi là từ phụ) trong tập các từ đại diện cho văn bản sẽ làm nội dung của văn bản không tập trung vào trọng tâm và do đó có thể dẫn tới kết quả phân nhóm không tốt. Như vậy, các từ phụ phải được loại bỏ ngay trong quá trình tiền xử lý để đại diện văn bản gần với nội dung trung tâm của văn bản. Thao tác này phải được thực hiện trước khi các thực hiện tách các từ khoá. Tập các từ phụ được tổ chức thành một từ điển từ phụ và được sử dụng mỗi khi tách được một từ tthuộc văn bản đầu vào. Chọn các từ khoá đại diện cho văn bản. Sau khi đã tách thành công văn bản chúng ta thực hiện công việc tiếp theo đó là chọn ra các từ đại diện tốt nhất cho văn bản. Đây là công việc quan trọng và có ảnh hưởng trực tiếp đến quá trình tìm kiếm văn bản. Nếu các term được chọn là đại diện cho văn bản mà không tốt thì kết quả tìm kiếm văn bản sẽ trả lại những tài liệu không mong đợi. Việc chọn các từ khoá phụ thuộc vào nhiều kỹ thuật. Ví dự như từ loại được ưu tiên, tầm quan trọng của từ trong văn bản cũng như tần trọng số của từ. Các kỹ thuật gán trọng số thực hiện đánh giá tầm quan trọng của các từ có nghĩa trong văn bản để từ đó trọn ra các từ có nghĩa và là đại diện xứng đáng nhất cho văn bản. Bước tiếp theo của công việc xử lý dữ liệu văn bản để phục vụ cho mô hình TRSM trong việc tìm kiếm văn bản tiếng việt đó là từ những từ đại diện cho từng văn bản ta phải tính được lớp dung sai cho từng term để từ đó xây dụng tập các xấp xỉ trên và xấp xỉ dưới cho từng văn bản. Dưới đây là phác thảo mô hình thực hiện của hệ thống tìm kiếm văn bản tiếng Việt mà em xây dựng trong đồ án này Cơ sở dữ liệu Truy vấn Q quan h ệ dung sai Các xấp xỉ trên/dưới Các xấp xỉ dươi So sánh Các tài liệu chính xác Hình 4. Kiến trúc của hệ thống Chức năng của hệ thống tìm kiếm văn bản tiếngViệt sử dụng mô hình TRSM gồm hai nhiệm vụ chính đó là : - Xác định các lớp dung sai của tất cả các term và tập các xấp xỉ trên và tập các xấp xỉ dưới của tất cả các tài liệu - Tìm kiếm các tài liệu theo yêu cầu của người sử dụng Trong nhiệm vụ thứ nhất hệ thống cung cấp các công cụ cho việc cập nhật cơ sở dữ liệu. Hệ thống tính các lớp dung sai của các term theo một giá trị ngưỡng nào đó. Công việc tiếp theo hệ thống sau khi đã có được lớp dung sai của các term trong văn bản là xác định các xấp xỉ trên và dưới cho từng tài liệu trong tập tất cả các tài liệu trong cơ sở dữ liệu văn bản. Chú ý rằng khi tính lớp dung sai mỗi term chúng ta phải đặt ra một ngưỡng cụ thể. Ví dụ như trong đồ án này khi cài đặt giải thuật em đặt ngưỡng là q=2. Điều này có nghĩa là term A có quan hệ dung sai với term B khi mà A và B xuất hiện cùng nhau ít nhất là trong hai văn bản trở lên. Đối với nhiệm vụ thứ hai, khi người sử dụng đưa vào một truy vấn điều đầu tiên là hệ thống sẽ thực hiện tách từ có nghĩa cho câu truy vấn. Sau đó tính dung sai và tính các xấp xỉ của truy vấn đó sau đó thực hiện các phép đối chiếu giữa các xấp xỉ trên và dưới của truy vấn và các xấp xỉ trong các văn bản để xác định các cấp độ phù hợp qua đó đưa ra được các tài liệu theo yêu cầu của người sử dụng. Trên cơ sở của mô hình trên có thể thấy công việc chính phải thực hiện bao gồm : - Xây dựng chương trình thực hiện công việc quản trị cơ sở dữ liệu. - Tạo giao diện ngưới dùng để thực thi quá trình tìm kiếm tài liệu. Trong công việc thứ nhất có thể hình dung để có thể khai thác được thông tin chúng ta phải có chiến lược trong việc lưu trữ thông tin. Trong đề tài này dữ liệu là các tài liệu dạng văn bản sau quá trình tiền xử lý tập các term đại diện cho tài liệu sẽ được lưu trữ vào cơ sở dữ liệu. Công việc tiếp theo là dựa trên cơ sở dữ liệu này chúng ta thực hiện tính các không gian xấp xỉ cho từng tài liệu dựa trên lý thuyết tập thô dung sai. Kết quả của công việc quản trị cơ sở dữ liệu này là chúng ta nhận được một cơ sở dữ liệu của các văn bản trong cơ sở dữ liệu lưu trữ thông tin về các tài liệu cũng như không gian xấp xỉ của từng tài liệu. Công việc thứ hai mà em đặt ra trong đề tài là mô phỏng một giao diện người dùng cho việc tìm kiếm tài liệu theo yêu cầu của người sử dụng. Để có thể thực hiện công việc tìm kiếm thông tin người sử dụng nhập vào một truy vấn. Thông qua tiền xử, câu lý truy vấn này được phân tách thành các term. Hệ thống sẽ thực hiện tính các không gian xấp xỉ của truy vấn và áp dụng thuật toán TRSM để cung cấp các tài liệu có khả năng đáp ứng thông tin theo yêu cầu người sử dụng với các cấp độ chính xác được chỉ ra. II. CÀI ĐẶT THỬ NGHIỆM 1. TIỀN XỬ LÝ VĂN BẢN TIẾNG VIỆT 1.1 Tổ chức từ điển Việc chọn một cơ sở dữ liệu phù hợp cho việc tổ chức từ điển cũng hết sức cần thiết và quan trọng. Nếu cơ sở dữ liệu được tổ chức tốt và hợp lý thì công việc tiền xử lý văn bản tiếng Việt sẽ đạt hiệu quả cao đặc biệt là về mặt tốc độ xử lý. Trong phần cài đặt này em sử dụng cơ sở dữ liệu Access. Đây là một cơ sở dữ liệu được sử dụng rộng rãi và phổ biến đối với những bài toán vừa và nhỏ và không yêu cầu nhiều về độ an toàn của dữ liệu. Việc tổ chức dữ liệu từ điển theo các bảng và được chia theo bảng chữ cái sẽ giúp cho chúng ta thu hẹp được phạm vi tìm kiềm của các từ trong toàn bộ các từ có trong từ điển. Đồng thời giúp cho tốc độ của quá trình tách từ tiếng Việt nhanh hơn. Cũng trong cơ sở dữ liệu này em định nghĩa một bảng chứa các từ không có nghĩa, ít ý nghĩa, các ký hiệu để từ đó giúp cho việc tách các từ có nghĩa trong văn bản nhanh hơn và chia nhỏ các đoạn cần tách tốt hơn. Chính việc chia nhỏ các đoạn cần tách tốt sẽ giúp cho thuật toán tách từ có nghĩa đạt hiệu quả cao hơn vì tránh phải thực hiện nhiều vòng lặp thừa mà không tách ra được từ có nghĩa nào cả. Hình 5: Tổ chức lưu trữ từ điển 1.2. Tổ chức cơ sở dữ liệu văn bản Việc chuyển đổi dữ liệu văn bản từ dạng phi cấu trúc về dạng cấu trúc đó là một công việc cần thiết để từ đó chúng ta có thể áp dụng các kỹ thuật khai phá văn bản nói chung cũng như tìm kiếm văn bản tiếng Việt nói riêng. Các văn bản tiếng Việt được lưu trữ trong cơ sử dữ liệu Access như sau: Hình 6: Sơ đồ lưu trữ cơ sở dữ liệu văn bản 1.3. Xác định các từ khoá trong văn bản Để xác định chính xác các từ khoá cho văn bản cũng là một bài toán hết sức phức tạp, đặc biệt là đối với các văn bản tiếng Việt. Để giải quyết tốt bài toán này chúng ta cần phải tổ chức tốt từ điển, cần phải có một giải thuật tách từ tiếng Việt hợp lý để chọn ra tập các từ đại diện cho văn bản. Sau đó chọn lọc ra các từ khoá làm tập các từ đại diện cho văn bản. Các từ đại diện cho văn bản phải thoả mãn các tính chất đó là một tập các từ có thể phân biệt được giữa văn bản này với các văn bản khác nhưng đồng thời phải đưa ra được các từ mang tính trọng tâm của văn bản. Trong đồ án này em chọn ngưỡng cho từ tách được dài nhất gồm bốn tiếng ghép lại. Các từ được tách sẽ ưu tiên từ có độ dài dài nhất. Ví dụ từ công nhân sẽ được chọn thay vì từ công và từ nhân. Một điểm cần lưa ý là từ loại của từ cần tách cũng quan trọng. Chúng ta nhận thấy rằng nếu từ, từ ghép được tách là danh từ hoặc động từ thì có ý nghĩa đại diện cho văn bản nhiều hơn so với các từ loại dạng đại từ giới từ. Dưới đây là kết quả của việc tách từ có nghĩa cho một số văn bản tiếng Việt. Hình 7:Giao diện ứng dụng tách từ có nghĩa cho văn bản 2. Xử lý dữ liệu để phục vụ cho mô hình tìm kiếm văn bản bằng phương pháp tập thô dung sai. Tính không gian dung sai và các xấp xỉ trên và xấp xỉ dưới Với những mục đích đã đặt ra trong đồ án. Em xây dựng hai form để áp dụng mô hình lý thuyết tập thô dung sai vào bài toán tìm kiếm văn bản tiếng Việt. Trong chương trình công việc xử lý chuỗi được sử dụng khá nhiều. Trong đó công việc tách từ cũng như so sánh quan hệ giữa hai chuỗi thông qua các thành phần trong chuỗi. Để thực hiện công việc tách từ trong câu truy vấn em sẽ xử dụng môdul tách từ trong phần tiền xử lý văn bản tiếng Việt. Việc so sánh hai chuỗi được thực hiện thông qua một hàm so sánh sau: Function sosanh(ByVal str1 As String, ByVal str2 As String) As Byte Dim mang1() As String Dim mang2() As String Dim i, j, tg As Integer Dim dung As Boolean Call tachchuoi(mang1(), str1) Call tachchuoi(mang2(), str2) // Thực hiện so sánh hai mảng For i = 1 To UBound(mang1()) dung = False j = 0 Do j = j + 1 If mang1(i) = mang2(j) Then tg = tg + 1 // Biến đếm số phần tử giống nhau của hai mảng dung = True End If Loop Until (j = UBound(mang2())) Or (dung = True) Next If tg = 0 Then sosanh = 0 // Hai chuỗi không có phần tử chung ElseIf (tg < UBound(mang1())) And (tg < UBound(mang2())) Then sosanh = 1 // Hai chuỗi giao nhau ElseIf (tg < UBound(mang1())) And (tg = UBound(mang2())) Then sosanh = 2 // Chuỗi 1 là tập con của chuỗi 2 ElseIf (tg = UBound(mang1())) And (tg < UBound(mang2())) Then sosanh = 3 // Chuỗi 2 là tập con của chuỗi 1 Else sosanh = 4 // Hai chuỗi gồm các phần tử giống hệt nhau End If End Function Tính lớp dung sai cho các term Chức năng này sẽ thực hiện nhiệm vụ tính các lớp dung sai của tập các term cho từng tài liệu đã được lạp vào cơ sở dữ liệu. Điểm quan trọng trong thuật toán tính các lớp dung sai là phải xây dựng được ma trận quan hệ giữa các term và các văn bản. với ma trận Amn xây dựng được ta sẽ có giá trị của aii cho biết term ti có thuộc văn bản di hay không . Nếu giá trị này bằng 1 thì đúng, ngược lại giá trị bằng không có nghĩa là term này không thuộc văn bản di. Với ma trận này để có thể xác định được hai term ti và tj có suất hiện cùng nhau trong bao nhiêu văn bản ta chỉ việc tính bằng vòng lặp sau: For k=1 số văn bản Do Giá trị = Giá trị = Giá trị +aik*ajk sau vòng lặp trên kết quả sẽ là Giá trị (số văn bản cùng chứa hai term ti và tj) Đoạn mã dưới đây sẽ thực hiện chức năng tính lớp dung sai cho các term trên toàn bộ các văn bản trong cơ sở dữ liệu. Dim db As Database Dim rs As Recordset Private Sub cmdlopdungsai_Click() Dim mang() As String Dim rs1 As Recordset Dim rs2 As Recordset Dim i, j, k, l As Integer Dim sohang, socot As Integer Dim dem As Byte Dim term1, term2 As String Set rs1 = db.OpenRecordset("tukhoa") rs1.MoveLast sohang = rs1.RecordCount 'So tu khoa Set rs2 = db.OpenRecordset("tai lieu") rs1.MoveLast socot = rs2.RecordCount // Số văn bản //Xây dựng ma trậm dùng để tính các lớp dung sai ReDim mang(1 To sohang, 1 To socot) //Xây dựng ma trận mang(i,j) để xem từ khoá i có thuộc văn bản j không // mang(i,j)= 1 nếu từ khoá i thuộc văn bản j, nếu từ khoá i không thuộc văn bản j thì mang(i,j)=0 rs1.MoveFirst rs2.MoveFirst k = 1 Do Until rs1.EOF l = 1 rs2.MoveFirst Do Until rs2.EOF If sosanh(rs1!term_ID, rs2!cactukhoa) = 3 Then mang(k, l) = 1 // Neu tk thuoc dl Else mang(k, l) = 0 End If rs2.MoveNext l = l + 1 Loop rs1.MoveNext k = k + 1 Loop rs1.Close rs2.Close Set rs1 = db.OpenRecordset("tukhoa") Do Until rs1.EOF rs1.Edit rs1!lopdungsai = rs1!term_ID rs1.Update rs1.MoveNext Loop For i = 1 To sohang For j = 1 To sohang If j i Then l = 0 For k = 1 To socot l = l + mang(i, k) * mang(j, k) Next If l > 1 Then // xét theo giá trị ngưỡng. trong trường hợp này=2 rs1.MoveFirst dem = 1 Do Until (dem = j) rs1.MoveNext dem = dem + 1 // tìm đến từ khoá có số thứ tự = dem Loop term1 = rs1!term_ID dem = 1 rs1.MoveFirst Do Until (dem = i) rs1.MoveNext dem = dem + 1 Loop term2 = rs1!lopdungsai // cập nhật lớp dung sai If Trim(term2) "" Then term2 = term2 + "," + term1 Else term2 = term1 rs1.Edit rs1!lopdungsai = term2 rs1.Update End If End If Next Next DBGrid1.Refresh End Sub Hình 8: Giao diện thực hiện tính không gian dung sai cho các term Chức năng thực hiện tính lớp dung sai cho các term cho ra kết quả đúng theo công thức tính lớp dung sai mà chúng ta đã được tìm hiểu trong phần lý thuyết về tập thô dung sai. Trong phần đemô này em đưa ra lớp dung sai cho tất các term của các văn bản dưới dạng tập các mã của term chứ không phải là tập các term. Tính xấp xỉ trên và xấp xỉ dưới Sau khi tình được lớp dung sai cho các từ đại diện cho văn bản chúng ta tiến hành tính xấp xỉ trên và xấp xỉ dưới cho từng văn bản trong toàn bộ tập văn bản. Dưới đây là đoạn mã thực hiện công việc tính xấp xỉ trên và xấp xỉ dưới. Private Sub cmdtinhxapxi_Click() Dim i, j, k As Integer Dim rs1 As Recordset Dim str As String Dim lopdungsai As String Dim tukhoa() As String Dim xapxi() As String Dim xapxiduoi As String Dim xapxitren As String Set rs = db.OpenRecordset("tai lieu") Do Until rs.EOF xapxiduoi = "" // Chuỗi lưu xấp xỉ dưới tính được xapxitren = "" // Chuỗi lưu xấp xỉ trên tính được str = "" // Lưu tập các từ khoá của một tài liệu str = rs!cactukhoa Call tachchuoi(tukhoa(), str) Set rs1 = db.OpenRecordset("tukhoa") For i = 1 To UBound(tukhoa()) rs1.MoveFirst // Tìm đến từ khoá thuộc vào văn bản trong bảng từ khoá Do Until (Trim(tukhoa(i)) = Trim(rs1!term_ID)) rs1.MoveNext Loop lopdungsai = rs1!lopdungsai //Xác định lớp dung sai của từ khoá Call tachchuoi(xapxi(), lopdungsai) For j = 1 To UBound(xapxi()) // Tính các xấp xỉ If xapxitren = "" Then xapxitren = xapxi(j) Else If sosanh(xapxi(j), xapxitren) < 3 Then xapxitren = xapxitren + "," + xapxi(j) End If Next If (sosanh(lopdungsai, str) >= 3) Then If xapxiduoi = "" Then xapxiduoi = tukhoa(i) Else xapxiduoi = xapxiduoi + "," + tukhoa(i) End If Next // Cập nhật các xấp xỉ tính được cho các tài liệu rs.Edit rs!cacxapxiduoi = xapxiduoi rs!cacxapxitren = xapxitren rs.Update rs.MoveNext Loop rs1.Close rs.Close DBGrid2.Refresh End Sub Hình 9: Giao diện thực hiện tính xấp xỉ trên và dưới cho các văn bản. Đánh giá kết quả: Công việc tính xấp xỉ trên và dưới lấy trực tiếp kết quả của phần tính lớp dung sai cho các từ đại diện cho văn bản làm đầu vào. Do vậy hiệu quả của phần này phụ thuộc rất nhiều vào các phần đã được xử lý trước đó. Nhìn chung phần cài đặt công việc tính xấp xỉ trên và dưới đã hoạt động được và cho ra kết quả đúng như lý thuyết về cách xây dựng không gian xấp xỉ. Nhưng còn một vấn đề đáng quan tâm đó là việc trích lọc các từ khoá không tốt dẫn đến bùng nổ tổ hợp. Tuy nhiên trong quá trình cài đặt cũng như quá trình test thử chương trình thì sự cố trên vẫn chưa xảy ra. 3. Tìm kiếm văn bản sử dụng mô hình tập thô dung sai Trong phần tìm kiếm văn bản, nhiệm vụ của hệ thống là phải tính được xấp xỉ trên và dưới của câu truy vấn. Từ đó đưa ra các tài liệu phù hợp nhất có dựa trên các xấp xỉ của từng tài liệu. Trong phần tìm kiếm văn bản này, hệ thống sẽ so sánh tập xấp xỉ trên và tập xấp xỉ dưới của câu truy vấn và sau đó đưa ra những tài liệu gần với câu truy vấn nhất. Mỗi tài liệu được trả lại sau câu truy vấn sẽ thuộc một trong 12 cấp độ đã được nêu ra trong phần lý thuyết về mô hình TRSM ở phần đầu. Hình 10: Giao diện phục vụ tìm kiếm văn bản Đánh giá kết quả: Như chúng ta đã biết, sự khó khăn nhất của bài toán khai phá dữ liệu văn bản tiếng Việt nói chung cũng như bài toán tìm kiếm văn bản tiếng Việt nói riêng thì ngoài một giải thuật tìm kiếm tốt ra chúng ta cần phải có một phương án giải quyết thật tốt bài toán bài toán tiền xử lý dữ liệu văn bản. Các thuật toán tìm kiếm tốt đến mấy cũng trở thành vô nghĩa khi phần tiền xử lý không tốt. Một điều chắc chắn là nếu chúng ta chọn các từ đại diện cho văn bản không tốt thì kết quả mà chúng ta nhận được sau câu truy vấn sẽ không như mong muốn. Mô hình TRSM cũng không lằm ngoài trường hợp này. TRSM là một mô hình khá phù hợp với bài toán tìm kiếm văn bản tiếng Việt không những đẫ giải quyết khá tốt vấn đề đồng nghĩa mà nó còn đưa ra được những tài liệu sau khi truy vấn theo phương pháp xấp xỉ, đây là một phương pháp khá mới và cũng hiệu quả dựa trên lý thuyết mờ để tìm kiếm thông tin. Để xây dựng hệ thống tìm kiếm văn bản tiếng Việt sử dụng mô hình tập thô dung sai đạt hiệu quả cao, ngoài phần tách các từ đại diện cho văn bản ra chúng ta còn phải tính chính xác được lớp dung sai của các term để từ đó xây dựng tập xấp xỉ trên và dưới đại diện cho văn bản một cách chính xác. Do vậy, khi đánh giá tầm quan trọng của mô hình lý thuyết tập thô dung sai chúng ta không được tập chung vào phần nào cả. Bởi vì kết quả của phần trước làm đầu vào cho phần sau và kết quả cuối cùng sẽ phụ thuộc trực tiếp vào tất cả các phần mà mô hình lý thyuết tập thô dung sai đưa ra. HƯỚNG PHÁT TRIỂN TRONG TƯƠNG LAI Trong thời gian làm đồ án tốt nghiệp em đã tìm hiểu về các đặc điểm của tiếng Việt cũng như các cách chuyển đổi nguồn dữ liệu văn bản tiếng Việt ở dạng phi cấu trúc về dạng cấu trúc để làm đầu vào cho các mô hình khai phá dữ văn bản liệu nói chung và nguồn dữ liệu phục vụ cho bài toán tìm kiếm văn bản tiếng Việt nói riêng. Đồ án đã trình bầy một số phương pháp về xử lý văn bản tiếng Việt, nghiên cứu một số phương pháp để lọc ra tập các từ khoá và hai mô hình tìm kiếm văn bản tiếng Việt đó là mô hình không gian vector và mô hình tập thô dung sai đồng thời áp dụng mô hình lý thuyết tập thô dung sai để cài đặt chương trình. Trong đồ án này một số kỹ thuật khai phá dữ liệu văn bản đã được nghiên cứu và tìm hiểu. Mục tiêu của em trong thời gian tới là sẽ là áp dụng những nghiên cứu ở phần trên và từ đó xây dựng được một hệ thống tìm kiếm văn bản tiếng Việt tự động. Việc tự động được thực hiện từ việc tách từ, đánh trọng số cho các từ được tách, lọc các từ đại diện cho văn bản và cuối cùng là áp dụng và cải tiến mô hình tập tập thô dung sai vào công việc tìm kiếm văn bản Việt. Cụ thể hơn về những công việc cũng như các bước cần phải làm để có thể hoàn thiện được một hệ thống phục vụ tìm kiếm văn bản tiếng Việt một cách hiệu quả đó là: Nghiên cứu và lựa chọn ra một kỹ thuật tách các từ đại diện cho văn bản sao cho thật chính xác. Áp dụng phân tích cú pháp đối với văn bản đầu vào sau đó áp dụng kỹ thuật sinh từ đại diện. Từ tập các từ đại diện, thực hiện kỹ thuật lọc từ để đưa ra các từ đại diện cuối cùng cho văn bản. Những terms được tách ra của văn bản cần phải có đầy đủ những yếu tố sau: Đó là các từ đại diện đặc trưng nhất của văn bản và đồng thời phân biệt được sự khác biệt giữa văn bản này với văn bản khác trong tập các văn bản. Đưa ra phương pháp xử lý tốt và hiệu quả đối với vấn đề đồng âm khác nghĩa hoặc đồng nghĩa khác âm, giải quyết được phần nào sự nhập nhằng trong ngôn ngữ. Tổ chức dữ liệu hợp lý để đáp ứng được thời gian xử lý và thích hợp về không gian lưu trữ đồng thời có thể chạy tốt trên môi trường nhiều người sử dụng. Xây dựng một mô hình tìm kiếm văn bản tiếng Việt dựa trên mô hình TRSM đồng thời có những cải tiến về mặt thuật toán để có thể đáp ứng được tính hợp lý, chính xác cao trong việc tìm kiếm văn bản tiếng Việt. TÀI LIỆU THAM KHẢO. 1 Nguyễn Văn Ba - Giáo trình ngôn ngữ hình thức – Nguyễn Văn Ba - Trường đại học Bách Khoa Hà Nội 2 Nguyễn Tài Cẩm - Từ loại danh từ trong tiếng Việt hiện đại 3 Lê Minh Hiền- Một số phương pháp xử lý văn bản tiếng Việt tự động– Luận văn thạc sỹ - Trường đại học Bách Khoa Hà Nội 4 Lê Thanh Hương - Phân Tích cú pháp tiếng Việt –Luận văn thạc sỹ - Trường đại học Bách Khoa Hà Nội. 5 Phạm Thị Anh Lê -Tìm kiếm thông tin dựa vào phương pháp thống kê- luận văn thạc sỹ - Trường đại học Bách Khoa Hà Nội Vũ Lục - Giáo trình phân tích cú pháp – Trường đại học Bách Khoa Hà Nội 7 Lưu Anh Tuấn - Khai phá dữ liệu văn bản tiếng Việt - Luận văn tốt nghiệp - Trường đại học Bách Khoa Hà Nội 8 Hồ Tú Bảo, Funakoshi K.-Information Retrieval Using Rough Sets 9 Nguyễn Ngọc Bình, Hồ Tú Bảo Nonhierarchical Document clustering based on Tolerance Rough Set model V.S.Subrahmanian- Principles of multimedia database system 11 Roby L.kennedy, Yuchung Lee, Benjamin Van Roy Solving Data Mining Problems Through pattern Recognition 12 Ngữ pháp tiếng Việt – Trung tâm khoa học xã hội và nhân văn quốc gia- Nhà xuất bản giáo dục 13 Text Data Mining – 14 Text Mining – Knowled extraction from unstructured textual data – 15 Một số các tài liệu khác từ trang