Khóa luận Biểu diễn văn bản sử dụng các khái niệm mờ

i viết là: Tìm các tài liệu có chứa từ “tôi” hoặc từ “ta” hoặc “tao”. Nhược điểm Đòi hỏi người tìm kiếm phải có kinh nghiệm và chuyên môn trong lĩnh vực tìm kiếm vì câu hỏi đưa vào dưới dạng Logic nên kết quả trả lại cũng có giá trị Logic (Boolean). Một số tài liệu sẽ được trả lại khi thoả mãn mọi điều kiện đưa vào. Như vậy muốn tìm được tài liệu theo nội dung thì phải biết đích xác về tài liệu. Việc Index các tài liệu rất phức tạp và làm tốn nhiều thời gian, đồng thời cũng tốn không gian để lưu trữ các bảng Index. Các tài liệu tìm được không được xắp xếp theo độ chính xác của chúng. Các bảng Index không linh hoạt vì khi các từ vựng thay đổi (thêm, xóa,…) thì dẫn tới chỉ số Index cũng phải thay đổi theo. 2.3. Mô hình phân tích cú pháp Trong mô hình này, mỗi văn bản đều phải được phân tích cú pháp và trả lại thông tin chi tiết về chủ đề của văn bản đó. Sau đó, người ta tiến hành Index các chủ đề của từng Khóa luận tốt nghiệp Nguyễn Việt Cường 15 văn bản. Cách Index trên chủ đề cũng giống như khi Index trên văn bản nhưng chỉ Index trên các từ xuất hiện trong chủ đề. Các văn bản được quản lý thông qua các chủ đề này để có thể tìm kiếm được khi có yêu cầu, câu hỏi tìm kiếm sẽ dựa trên các chủ đề trên. ™ Cách tìm kiếm: Tiến hành tìm kiếm bằng cách dựa vào các chủ đề đã được Index ở trên. Câu hỏi đưa vào có thể được phân tích cú pháp để trả lại một chủ đề và tìm kiếm trên chủ đề đó. Như vậy bộ phận xử lý chính đối với một hệ CSDL xây dựng theo mô hình này chính là hệ thống phân tích cú pháp và đoán nhận nội dung văn bản. Một số ưu điểm, nhược điểm của phương pháp này Ưu điểm Tìm kiếm theo phương pháp này lại khá hiệu quả và đơn giản, do tìm kiếm nhanh và chính xác. Đối với những ngôn ngữ đơn giản về mặt ngữ pháp thì việc phân tích trên có thể đạt được mức độ chính xác cao và chấp nhận được. Nhược điểm Chất lượng của hệ thống theo phương pháp này hoàn toàn phụ thuộc vào chất lượng của hệ thống phân tích cú pháp và đoán nhận nội dung tài liệu. Trên thực tế, việc xây dựng hệ thống này là rất phức tạp, phụ thuộc vào đặc điểm của từng ngôn ngữ và đa số vẫn chưa đạt đến độ chính xác cao. 2.4. Mô hình không gian vector Cách biểu diễn văn bản thông dụng nhất là thông qua vector biểu diễn theo mô hình không gian vector (Vector Space Model). Đây là một cách biểu diễn tương đối đơn giản và hiệu quả. Theo mô hình này, mỗi văn bản được biểu diễn thành một vector. Mỗi thành phần của vector là một từ khóa riêng biệt trong tập văn bản gốc và được gán một giá trị là hàm f chỉ mật độ xuất hiện của từ khóa trong văn bản. Khóa luận tốt nghiệp Nguyễn Việt Cường 16 Hình 3: Biểu diễn các vector văn bản trong không gian 2 chiều Giả sử ta có một văn bản và nó được biểu diễn bởi vector V(v1,v2, …, vn). Trong đó, vi là số lần xuất hiện của từ khóa thứ i trong văn bản. Ta xét 2 văn bản sau: VB1: Life is not only life VB2: To life is to fight Sau khi qua bước tiền xử lý văn bản, ta biểu diễn chúng như sau: Trong các cơ sở dữ liệu văn bản, mô hình vector là mô hình biểu diễn văn bản được sử dụng phổ biến nhất hiện nay. Mối quan hệ giữa các trang văn bản được thực hiện thông qua việc tính toán trên các vector biểu diễn vì vậy được thi hành khá hiệu quả. Đặc biệt, nhiều công trình nghiên cứu về mối quan hệ "tương tự nhau" giữa các trang web (một trong những quan hệ điển hình nhất giữa các trang web) dựa trên mô hình biểu diễn vector . Khóa luận tốt nghiệp Nguyễn Việt Cường 17 2.4.1. Mô hình Boolean Một mô hình biểu diễn vector với hàm f cho ra giá trị rời rạc với duy nhất hai giá trị đúng và sai (true và false, hoặc 0 và 1) gọi là mô hình Boolean. Hàm f tương ứng với từ khóa ti sẽ cho ra giá trị đúng nếu và chỉ nếu từ khóa ti xuất hiện trong văn bản đó. Mô hình Boolean được xác định như sau: Giả sử có một cơ sở dữ liệu gồm m văn bản, D = {d1, d2,… dm}. Mỗi văn bản được biểu diễn dưới dạng một vector gồm n từ khóa T = {t1, t2,…tn}. Gọi W = {wij} là ma trận trọng số, trong đó wij là giá trị trọng số của từ khóa ti trong văn bản dj. ⎩⎨ ⎧= lai nguoc neu trongmat co neu 0 dt1 w jiij Trở lại với 2 văn bản trên, áp dụng mô hình Boolean ta có biểu diễn sau: 2.4.2. Mô hình tần suất Trong mô hình tần suất, ma trận W = {wij} được xác định dựa trên tần số xuất hiện của từ khóa ti trong văn bản dj hoặc tần số xuất hiện của từ khóa ti trong toàn bộ cơ sở dữ liệu. Sau đây là một số phương pháp phổ biến: a. Phương pháp dựa trên tần số từ khóa (TF – Term Frequency) Các giá trị wij được tính dựa trên tần số (hay số lần) xuất hiện của từ khóa trong văn bản. Gọi fij là số lần xuất hiện của từ khóa ti trong văn bản dj, khi đó wij được tính bởi một trong ba công thức: wij = fij wij = 1 + log(fij) Khóa luận tốt nghiệp Nguyễn Việt Cường 18 wij = ijf Trong phương pháp này, trọng số wij tỷ lệ thuận với số lần xuất hiện của từ khóa ti trong văn bản dj. Khi số lần xuất hiện từ khóa ti trong văn bản dj càng lớn thì điều đó có nghĩa là văn bản dj càng phụ thuộc vào từ khóa ti, hay nói cách khác từ khóa ti mang nhiều thông tin trong văn bản dj. Ví dụ, khi văn bản xuất hiện nhiều từ khóa máy tính, điều đó có nghĩa là văn bản đang xét chủ yếu liên quan đến lĩnh vực tin học. Nhưng suy luận trên không phải lúc nào cũng đúng. Một ví dụ điển hình là từ “và” xuất hiện nhiều trong hầu hết các văn bản, nhưng trên thực tế từ này lại không mang nhiều ý nghĩa như tần suất xuất hiện của nó. Hoặc có những từ không xuất hiện trong văn bản này nhưng lại xuất hiện trong văn bản khác, khi đó ta sẽ không tính được giá trị của log(fij). Một phương pháp khác ra đời khắc phục được nhược điểm của phương pháp TF, đó là phương pháp IDF. b. Phương pháp dựa trên nghịch đảo tần số văn bản (IDF – Inverse Document Frequency) Trong phương pháp này, giá trị wij được tính theo công thức sau: ⎪⎩ ⎪⎨ ⎧ −== l¹i ng−îc nÕu liÖu tµi trong xuÊt hiÖn khãa tõ nÕu 0 dt)hlog()mlog( h mlog w jiiiij trong đó m là số lượng văn bản và hi là số lượng văn bản mà từ khóa ti xuất hiện. Trọng số wij trong công thức này được tính dựa trên độ quan trọng của từ khóa ti trong văn bản dj. Nếu ti xuất hiện trong càng ít văn bản, điều đó có nghĩa là khi nó xuất hiện trong dj thì trọng số của nó đối với văn bản dj càng lớn hay nó là điểm quan trọng để phân biệt văn bản dj với các văn bản khác và hàm lượng thông tin trong nó càng lớn. c. Phương pháp TF × IDF Phương pháp này là tổng hợp của hai phương pháp TF và IDF, giá trị của ma trận trọng số được tính như sau: Khóa luận tốt nghiệp Nguyễn Việt Cường 19 ⎪⎩ ⎪⎨ ⎧ ≥⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛+= l¹i ng−îc nÕu f nÕu1 0 1 h mlog)]flog([ w iji ij ij Đây là phương pháp kết hợp được ưu điểm của cả hai phương pháp trên. Trọng số wij được tính bằng tần số xuất hiện của từ khóa ti trong văn bản dj và độ hiếm của từ khóa ti trong toàn bộ cơ sở dữ liệu. Cách tìm kiếm: Các câu hỏi đưa vào sẽ được ánh xạ vector Q(q1,q2,…,qm) theo hệ số của các từ vựng trong nó là khác nhau. Tức là: Khi từ vựng càng có ý nghĩa với nội dung cần tìm thì nó có hệ số càng lớn. qi = 0 khi từ vựng đó không thuộc danh sách những từ cần tìm. qi 0 khi từ vựng đó thuộc danh sách các từ cần tìm. Khi đó, cho một hệ thống các từ vựng ta sẽ xác định được các vector tương ứng với từng tài liệu và ứng với mỗi câu hỏi đưa vào ta sẽ có một vector tương với nó cùng những hệ số đã được xác định từ trước. Việc tìm kiếm và quản lý sẽ được thực hiện trên tài liệu này. ™ Một số ưu, nhược điểm của phương pháp biểu diễn này: ƒ Ưu điểm: Các tài liệu trả lại có thể được sắp xếp theo mức độ liên quan đến nội dung yêu cầu do trong phép thử mỗi tài liệu đều trả lại chỉ số đánh giá độ liên quan của nó đến nội dung. Việc đưa ra các câu hỏi tìm kiếm là dễ dàng và không yêu cầu người tìm kiếm có trình độ chuyên môn cao về vấn đề đó. Tiến hành lưu trữ và tìm kiếm đơn giản hơn phương pháp Logic. ƒ Nhược điểm Khóa luận tốt nghiệp Nguyễn Việt Cường 20 Việc tìm kiếm tiến hành chậm khi hệ thống các từ vựng là lớn do phải tính toán trên toàn bộ các vector của tài liệu. Khi biểu diễn các vector với các hệ số là số tự nhiên sẽ làm tăng mức độ chính xác của việc tìm kiếm nhưng làm tốc độ tính toán giảm đi rẩt nhiều do các phép nhân vector phải tiến hành trên các số tự nhiên hoặc số thực, hơn nữa việc lưu trữ các vector sẽ tốn kém và phức tạp. Hệ thống không linh hoạt khi lưu trữ các từ khóa. Chỉ cần một thay đổi rất nhỏ trong bảng từ vựng sẽ kéo theo hoặc là vector hoá lại toàn bộ các tài liệu lưu trữ, hoặc là sẽ bỏ qua các từ có nghĩa bổ sung trong các tài liệu được mã hóa trước đó. Một nhược điểm nữa, chiều của mỗi Vector theo cách biểu diễn này là rất lớn, bởi vì chiều của nó được xác định bằng số lượng các từ khác nhau trong tập hợp văn bản. Ví dụ số lượng các từ có thể có từ 103 đến 105 trong tập hợp các văn bản nhỏ, còn trong tập hợp các văn bản lớn thì số lượng sẽ nhiều hơn, đặc biệt trong môi trường Web. 2.5. Biểu diễn văn bản trong máy tìm kiếm 2.5.1. Giới thiệu về máy tìm kiếm Thông tin trên các trang Web đa dạng về mặt nội dung cũng như hình thức. Tuy nhiên cùng với sự đa dạng và số lượng lớn thông tin như vậy đã nảy sinh vấn đề quá tải thông tin. Đối với mỗi người dùng chỉ một phần rất nhỏ thông tin là có ích, chẳng hạn có người chỉ quan tâm đến trang Thể thao, Văn hóa mà không mấy khi quan tâm đến Kinh tế. Người ta không thể tìm tự kiếm địa chỉ trang Web chứa thông tin mà mình cần, do vậy đòi hỏi cần phải có một trình tiện ích quản lý nội dung của các trang Web và cho phép tìm thấy các địa chỉ trang Web có nội dung giống với yêu cầu của người tìm kiếm. Hiện nay chúng ta đã làm quen với một số các tiện ích như vậy đó là: Yahoo, Google, Alvista,... Máy tìm kiếm là các hệ thống được xây dựng có khả năng tiếp nhận các yêu cầu tìm kiếm của người dùng (thường là một tập các từ khóa), sau đó phân tích và tìm kiếm trong cơ sở dữ liệu đã có sẵn và đưa ra các kết quả là các trang web cho người sử dụng. Cụ thể, người dùng gửi một truy vấn, dạng đơn giản nhất là một danh sách các từ khóa, và máy tìm kiếm sẽ làm việc để trả lại một danh sách các trang Web có liên quan hoặc có chứa các từ khóa đó. Phức tạp hơn, thì truy vấn là cả một văn bản hoặc một đoạn văn bản hoặc nội dung tóm tắt của văn bản. Khóa luận tốt nghiệp Nguyễn Việt Cường 21 2.5.2. Mô hình biểu diễn văn bản trong máy tìm kiếm Như đã được giới thiệu, mô hình vector là mô hình biểu diễn phổ biến nhất trong các CSDL văn bản. Tuy nhiên, còn có một các biểu diễn khác cũng thường được sử dụng, đặc biệt trong các máy tìm kiếm, đó biểu diễn theo mô hình index ngược (inverted index). Với một từ khoá trong câu hỏi của người dùng, thông qua mô hình index ngược hệ thống cơ sở dữ liệu văn bản sẽ nhanh chóng xác định được tập hợp các văn bản chứa từ khóa đó và các vị trí xuất hiện của từ khóa đó trong các văn bản kết quả. Ở dạng đơn giản nhất, mô hình index ngược có dạng như được mô tả như hình sau: Hình 4. Mô hình index ngược Trong mô hình này, tồn tại tập hợp V (được gọi là từ điển) gồm tất cả các từ khóa trong hệ thống; các từ khóa trong V được lưu trữ theo danh sách Inverted Index. Mỗi một từ khóa vi trong V liên kết với một con trỏ b(vi) chỉ dẫn tới một cấu trúc dữ liệu, được gọi là brucket, là một danh sách chứa tất cả các bản ghi mô tả văn bản chứa từ khóa vi và vị trí xuất hiện của từ khóa vi trong văn bản đó (hình 2). Tồn tại một số giải pháp tổ chức từ điển V hiệu quả nhằm cho phép lưu trữ V ở bộ nhớ trong, chẳng hạn V thường được tổ chức theo dạng bảng băm để tăng hiệu quả truy cập. Nếu như brucket được lưu ngay trong bộ nhớ trong thì việc thay đổi chỉnh sửa các brucket được thực hiện rất dễ dàng. Khóa luận tốt nghiệp Nguyễn Việt Cường 22 Tuy nhiên, điều này là không khả thi do kích thước của chúng thường khá lớn so với kích thước bộ nhớ trong. Vì vậy, các brucket (cũng như nội dung các văn bản) được lưu trong đĩa cứng. Để các cơ sở dữ liệu văn bản có khả năng quản lý được một lượng lớn các trang văn bản thì cần có các thuật toán chuyên biệt nhằm đảm bảo việc thao tác tới các brucket trên đĩa cứng được nhanh chóng. CSDL văn bản sử dụng mô hình index ngược cho khả năng tìm ra các trang văn bản có chứa từ khóa vi cho trước là khá đơn giản. Đầu tiên, hệ thống truy cập vào “inverted index” để lấy b(vi) và sau đó duyệt danh sách theo các con trỏ của b(vi) để lấy được các trang văn bản. Trường hợp câu truy vấn có dạng một biểu thức phức tạp có nhiều từ khóa được kết nối với nhau theo các phép toán lôgic như AND, OR, NOT thì công việc tìm kiếm phức tạp hơn. Với câu truy vấn có k từ khóa, thuật toán thực hiện việc lấy các trang văn bản tương ứng với mỗi từ khóa (dựa trên thuật toán tìm kiếm theo từ khóa nói trên) và nhận được k danh sách trang văn bản. Kết quả trả lời câu truy vấn nhận được bằng cách kết hợp k danh sách này tương ứng với biểu thức lôgic đã cho. Trong mọi trường hợp, sử dụng biểu diễn index ngược thì tìm kiếm văn bản đáp ứng câu hỏi thông qua từ khoá sẽ có tốc độ rất nhanh. Khóa luận tốt nghiệp Nguyễn Việt Cường 23 Chương 3. BIỂU DIỄN VĂN BẢN SỬ DỤNG CÁC KHÁI NIỆM MỜ Trong chương này chúng tôi sẽ trình bày một số khái niệm cơ bản về tập mờ, tiến hành định nghĩa các khái niệm mờ và một số tính chất của các khái niệm mờ thông qua việc tích hợp các từ khóa và mối quan hệ giữa chúng với nhau. Từ đó, sẽ giới thiệu phương pháp biểu diễn văn bản theo khái niệm mờ. 3.1. Lý thuyết mờ Có thể nói cho đến nay, phần lớn các thành tựu của khoa học của loài người đều dựa trên lập luận logic rất chặt chẽ mà nền tảng của các lập luận này là đại số logic Bool. Trong đại số logic Bool mọi toán hạng, biểu thức chỉ có giá trị 0 (false) hoặc 1 (true). Tuy nhiên trên thực tế điều này không luôn luôn đúng, nhiều hiện tượng trong tự nhiên và xã hội không thể biểu diễn rõ ràng như vậy. Để có thể phản ánh đúng bản chất của các sự vật, hiện tượng diễn ra trong thực tế, buộc người ta phải mở rộng đại số Bool để sao cho các toán hạng, các biểu thức có thể nhận giá trị không chỉ là 0 hoặc 1 mà chúng có thể nhận giá trị nào đó nằm giữa 0 và 1. Một cách tự nhiên để xây dựng lí thuyết mờ, người ta phải đi từ những khái niệm nguyên thuỷ nhất. Giống như trong toán học, một trong những khái niệm nguyên thuỷ của toán học là tập hợp, trong lí thuyết mờ người ta đi từ xây dựng tập mờ. 3.1.1. Tập mờ Trong toán học truyền thống khái niệm tập hợp được phát biểu như sau: Cho tập hợp X và A ⊆ X khi đó ta có thể xây dựng một hàm, được gọi là hàm đặc trưng, xác định các phần tử của tập X như sau: Xét µ : X → {0,1 } với x ∈ X thì: µ (x) = 1 nếu x ∈ A; µ (x) = 0 nếu x ∉ A; Hàm đặc trưng µ(x) rõ ràng là hàm xác định các phần tử của tập A. Nhờ hàm µ(x) ta có thể nói tập A là tập gồm những phần tử x mà µ (x)=1. Bây giờ tập A có thể biểu diễn một cách khác qua các phần tử của tập X: Khóa luận tốt nghiệp Nguyễn Việt Cường 24 A={(x, µ(x)=1)| x ∈ X} Mở rộng khái niệm tập hợp của toán học học cổ điển nêu trên, Lofti Zadeh xét hàm µ trên toàn đoạn [0,1]. Định nghĩa 3.1: Tập mờ Cho X là một tập hợp. A được gọi là một tập mờ trong X nếu: A = {(x, µA(x))| x∈X} trong đó µA(x) là hàm xác định trên đoạn [0,1], µA: X → [0,1]. Hàm µA được gọi là hàm thuộc của A còn µA(x) là một giá trị trong đoạn [0,1] được gọi là mức độ thuộc của x trong A. Biểu diễn tập mờ Khi X là tập các điểm rời rạc x1, x2, …xn thì tập mờ A có thể biểu diễn bằng cách liệt kê A = {(x1, µ A(x1)), (x2, µ A(x2)),...... (xn , µ A(xn))} Hoặc được ký hiệu là: A = µ A(x1)/ x1 + µ A(x2)/ x2 + … + µ A(xn)/ xn Trường hợp X liên tục thì A được kí hiệu là: A = ∫ ∈ µXx A x/)x( Ví dụ: Cho X là tập các điểm tổng kết trung bình các môn học của sinh viên. Qua thống kê người ta thấy rằng : 0% số người coi một sinh viên là giỏi khi điểm tổng kết đạt dưới 7.0 5% số người coi một sinh viên là giỏi khi điểm tổng kết đạt điểm từ 7.0 đến 7.5 10% số người coi một sinh viên là giỏi khi điểm tổng kết đạt đến 8.0; 20% số người coi một sinh viên là giỏi khi điểm tổng kết đạt đến 8.5; 80% số người coi một sinh viên là giỏi chỉ khi điểm tổng kết đạt từ 9 đến 9,5 . 100% số người coi một sinh viên là giỏi khi điểm tổng kết đạt đến điểm 10 Bây giờ cần biểu diễn tập các điểm trên X, được ký hiệu là tập A, để mô tả một "sinh viên giỏi". Với kết quả thống kê như trên, không thể dùng khái niệm tập hợp theo Khóa luận tốt nghiệp Nguyễn Việt Cường 25 quan niệm truyền thống để biểu diễn tập A. Trong trường hợp này, khái niệm tập mờ là rất hữu dụng và A chính là một tập mờ. Nếu xét X chỉ gồm các đại lượng hữu hạn, X = {7, 7.5, 8.0, 8.5, 9.0, 9.5, 10.0}, thì tập mờ A được biểu diễn như sau: A={ (7, 0.05),(7.5,0.05),(8.0,0.1), (8.5, 0.2), (9.0,0.8) (9.5,0.8),(10,1.0 ) } Hoặc: A= 0.05/7 + 0.05/7.5 + 0,0.1/8 + 0.2/8.5 + 0,0.8/9 + 0.8/9.5 + 1.0/10 Nếu xét X là một khoảng liên tục X = [7.0, 10] thì ta có thể biểu diễn đồ thị hàm thuộc của A như sau: Hình 5: Đồ thị hàm phụ thuộc tập mờ A 3.1.2. Các phép toán trên tập mờ ™ Giao của hai tập mờ. Cho X là tập hợp, A, B là hai tập mờ trong X và có các hàm thuộc lần luợt là µA, µB. Giao của hai tập mờ A và B, ký hiệu A∩B, là một tập mờ có hàm thuộc µA∩B xác định như sau: µA∩B(x) = min(µA(x), µB(x)) ∀x∈X ™ Hợp của hai tập mờ. Cho X là tập hợp, A, B là hai tập mờ trong X và có các hàm thuộc lần luợt là µA, µB. Hợp của hai tập mờ A và B trong X, ký hiệu A∪B, là một tập mờ có hàm thuộc µA∪B xác định như sau: µA∪B(x) ) = max(µA(x), µB(x)) ∀x∈X Khóa luận tốt nghiệp Nguyễn Việt Cường 26 ™ Tích đại số của hai tập mờ. Cho X là tập hợp, A, B là hai tập mờ trong X và có các hàm thuộc lần lượt là µA(x), µB(x). Tích đại số của hai tập mờ A và B trong X, ký hiệu A.B là một tập mờ có hàm thuộc được xác định như sau: µA.B(x) = µA(x).µB(x) ∀x∈X ™ Tổng đại số của hai tập mờ. Cho X là tập hợp, A, B là hai tập mờ trong X và có các hàm thuộc lần lượt là µA, µB. Tổng đại số của hai tập mờ A và B trong X, ký hiệu A+B là một tập mờ có hàm thuộc được xác định như sau: µA+B(x) = µA(x) + µB(x) - µA(x).µB(x) ∀x∈X. ™ Phần bù của một tập mờ. Cho A là tập mờ trong X có hàm thuộc µA. Phần bù A của A trong X là một tập mờ có hàm thuộc xác định như sau: )x( A µ = 1 - µA(x) ∀x∈X. ™ Tổng rời của hai tập mờ. Cho X là tập hợp, A và B là hai tập mờ trong X. Tổng rời của hai tập mờ A và B trong X, ký hiệu A⊕B định nghĩa như sau: A⊕B = ( A∩B) ∪ (A∩B ) ™ Phép trừ hai tập mờ. Cho X là tập hợp, A, B là hai tập mờ trong X và có các hàm thuộc lần lượt là µA, µB. Phép trừ của hai tập mờ A và B trong X ký hiệu A\B được định nghĩa như sau: A\B = A∩B . ™ Cho X là tập hợp, A và B là hai tập mờ trong X, có các hàm thuộc lần lượt là µA, µB. A gọi là nằm trong B, ký hiệu A⊂B nếu hàm thuộc thỏa mãn: µA(x) ≤ µB(x) ∀x∈X. Khóa luận tốt nghiệp Nguyễn Việt Cường 27 ™ Cho X là tập hợp, A và B là hai tập mờ trong X, có các hàm thuộc lần lượt là µA, µB . A gọi là bằng B, ký hiệu A=B nếu và chỉ nếu: µA(x) = µB(x) ∀x∈X ™ Tập hợp mức α của tập mờ. Cho α ∈[0,1], X là tập hợp, A là một tập mờ trong X có hàm thuộc µA. Tập hợp Aα thoả mãn Aα={x∈X | µA(x) ≥ α} gọi là tập hợp mức α của tập mờ A. ™ Khoảng cách Euclid trên tập mờ X là tập hợp có hữu hạn n phần tử, A và B là hai tập mờ trên X. Khoảng cách Euclid (trong không gian n chiều) trên tập mờ được tính như sau: e(A,B) = ∑ = µ−µn 1i 2 iBiA ))x()x(( Khoảng cách e2(A,B) được gọi là một chuẩn Euclid. 3.1.3. Quan hệ mờ Định nghĩa 3.2: Quan hệ mờ trên tích Đề-các Cho X,Y là hai tập và x∈X, y∈Y. Ký hiệu (x,y) là cặp thứ tự nằm trong tích Đề- các XxY. Tập mờ R = {(x,y), µR(x,y)|(x,y) ∈ XxY} được gọi là một quan hệ mờ trên X×Y với hàm thuộc: µR(x,y): X×Y → [0,1] Nếu R là một tập mờ trong X = X1×X2×….×Xn thì R được gọi là một quan hệ mờ n ngôi. Định nghĩa 3.3: Quan hệ mờ trên tập mờ Cho X,Y là hai tập mờ và x∈X, y∈Y. Ký hiệu (x,y) là cặp thứ tự nằm trong tích Đề-các X×Y. R = {(x,y), µR(x,y)|(x,y) ∈ X×Y} được gọi là một quan hệ mờ trên tập mờ A, B nếu: µR(x,y) ≤µA(x,y), ∀X×Y và µR(x,y) ≤µB(x,y) ∀X×Y 3.1.4. Các phép toán trên quan hệ mờ Ngoài một số phép toán giống như trên tập mờ trong tích Đề-các: Phép hợp, giao, tổng đại số, tích đại số…, người ta còn đưa ra thêm một số phép toán khác trong quan hệ mờ như sau: Khóa luận tốt nghiệp Nguyễn Việt Cường 28 ™ Phép hợp thành max-min Giả sử R1 là quan hệ mờ trong X×Y, R2 là quan hệ mờ trong Y×Z. Phép hợp thành max-min của hai quan hệ mờ R1, R2 (kí hiệu R1 o R2) là một quan hệ mờ trong X×Z thoả mãn: µ R1oR2(x,z) = maxy(min(µR1(x,y), µR2(y,z))) ∀x∈X, ∀y∈Y, ∀z∈Z ™ Phép hợp thành max-tích Giả sử R1 là quan hệ mờ trong X×Y, R2 là quan hệ mờ trong Y×Z. Phép hợp thành max-tích của hai quan hệ mờ R1, R2 (kí hiệu R1.R2) là một quan hệ mờ trong X×Z thoả mãn: µ R1.R2(x,z) = maxy(µR1(x,y). µR2(y,z)) ∀x∈X, ∀y∈Y, ∀z∈Z ™ Phép hợp thành max-trung bình Giả sử R1 là quan hệ mờ trong X×Y, R2 là quan hệ mờ trong Y×Z. Phép hợp thành max-trung bình của hai quan hệ mờ R1, R2 (R1avR2) là quan hệ mờ trong X×Z thoả mãn: µ R1avR2(x,z) = maxy((µR1(x,y)+µR2(y,z))/2) ∀x∈X, ∀y∈Y, ∀z∈Z ™ Phép hợp thành max-*.(max-* composition) (* là toán tử hai ngôi bất kỳ) Giả sử R1 là quan hệ mờ trong X×Y, R2 là quan hệ mờ trong Y×Z. Phép hợp thành max-* của hai quan hệ mờ R1, R2 (R1* R2) là một quan hệ mờ trong X×Z thoả mãn: µR1*R2(x,z) = max(µR1(x,y)*µR2(y,z)) ∀x∈X, ∀y∈Y, ∀z∈Z ™ Hàm tích hợp mờ Khi có một tập các tập mờ và tích hợp các hàm thuộc của chúng lại, ta sẽ thu được một tập mờ là một hàm tích hợp mờ. Khóa luận tốt nghiệp Nguyễn Việt Cường 29 Một hàm tích hợp mờ được định nghĩa là một toán tử n ngôi như sau: F: [0,1]n → [0,1] thỏa mãn điều kiện: Nếu 0, 1 là hai điểm cực trị thì: F(0,…,0) = 0 và F(1,…,1)=1 và ∀a trong [0,1] thì: F(a,…,a)=a Nếu ai’ > ai thì: F(a1,…,ai’,…,an) ≥ F(a1,…,ai,…,an) (tính đơn điệu tăng của hàm tích hợp mờ) Một số hàm tích hợp mờ: 1. Hàm trung bình tổng quát: 2. Hàm trung bình số học: 3. Hàm trung bình hình học: 4. Hàm min: 5. Hàm max: 3.2. Biểu diễn văn bản sử dụng các khái niệm mờ Cách biểu diễn văn bản thông thường là sử dụng mô hình không gian vector, trong đó văn bản được biểu diễn bằng một vector và mỗi thành phần của vector là một từ khóa. Ở chương II, khóa luận đã nêu ra một số nhược điểm của phương pháp này: gây tốn kém, phức tạp trong việc lưu trữ, chiều của mỗi vector là rất lớn khi văn bản có nhiều từ khóa … Trong phần này, chúng tôi xin trình bày một phương pháp biểu diễn văn bản mà phần nào khắc phục được nhược điểm nêu trên, đó là phương pháp biểu diễn văn bản sử dụng các khái niệm mờ. 0pR,p,)(x n 1 )x,...,F(x p n 1i p 1n1 ≠∈= ∑ = )0( →= pn 1 n21n1 )...x.x(x)x,...,F(x )(min −∞→= p)x,...,x,(x)x,...,F(x n21n1 )(max +∞→= p)x,...,x,(x)x,...,F(x n21n1 ∑ = == n 1i 1n1 )(xn 1 )x,...,F(x )1( p Khóa luận tốt nghiệp Nguyễn Việt Cường 30 3.2.1. Khái niệm mờ Có một tập gồm m văn bản: D=(d1, d2, …dm). Khí đó xác định được một tập p từ khóa: K = (k1, k2, … kp) Một khái niệm có thể là một từ khóa theo nghĩa thông thường, trong đó gồm các từ có liên quan đến từ khóa đó. Ví dụ với khái niệm là “bệnh viện”, nó có thể bao gồm 1 số từ khóa: “bác sĩ”, “y tá”, “bệnh nhân”, “ống nghe”, “thuốc” Gọi C là tập gồm có n khái niệm liên quan đến văn bản, C được kí hiệu như sau: C = {c1, c2, …cn} Trong đó: ci là khái niệm do người dùng xác định. Giả sử một khái niệm ci sẽ bao gồm các từ khóa có liên quan, ci = {k1, k2, …kp}, trong đó ki là các từ khóa trong tập từ điển và có liên quan đến khái niệm ci. Trong ví dụ trên chúng ta có “bệnh viện” = {“bác sĩ”, “y tá”, “bệnh nhân”, “ống nghe”, “thuốc”}. Định nghĩa 3.3: Khái niệm mờ Một tập mờ tương ứng với khái niệm trong đó hàm thuộc của nó được xác định bằng độ quan trọng của các từ khóa có liên quan tới khái niệm đó được gọi là một khái niệm mờ, kí hiệu c* . Ta có thể biểu diễn khái niệm mờ qua tập từ khóa như sau: ))}k(,k)),...(k(,k()),k(,k{(c pcp2c21c1 * µµµ= Trong đó: Từ khái niệm mờ, ta có định nghĩa sau: Định nghĩa 3.4: Hàm tích hợp khái niệm mờ: Một hàm tích hợp khái niệm mờ là hàm tích hợp các hàm thuộc của các khái niệm mờ. Hàm tích hợp này được kí hiệu F: [0,1]p → [0,1], thỏa mãn các tính chất của hàm tích hợp mờ: ⎪⎪ ⎪ ⎩ ⎪⎪ ⎪ ⎨ ⎧ = c niÖm kh¸ithuéc i k nÕu)i(kc c vµotoµn hoµnthuéc i k nÕu1 c thuéc kh«ng i k nÕu0 ) i (k c µ µ Khóa luận tốt nghiệp Nguyễn Việt Cường 31 1. 2. Trong đó, µc(ki) biểu diễn mức độ quan trọng của các từ khóa trong văn bản. Ví dụ: Giả sử ta có tập từ khóa: ‘bệnh viện’, ‘trường học’, ‘thuốc’, ‘xe máy’, ‘y tá’, ‘bệnh nhân’, ‘ống nghe’, ‘sinh viên’, ‘hoa hồng’, ‘điện thoại’, ‘bác sỹ’. K = {‘bệnh viện’, ‘bác sỹ’, ‘trường học’, ‘thuốc’, ‘xe máy’, ‘y