zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

Ứng dụng đại số gia tử trong tóm tắt dữ liệu bằng ngôn ngữ

Chia sẻ: ViMoscow2711 ViMoscow2711 | Ngày: | Loại File: PDF | Số trang:9

Báo xấu

25
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết trình bày một phương pháp mới để sinh ra các tóm tắt bằng ngôn ngữ mà ngữ nghĩa dựa trên cấu trúc Đại số gia tử. So với cách tiếp cận dựa trên lí thuyết mờ, cách tiếp cận dựa trên Đại số gia tử hạn chế được sự mất thông tin và làm giảm độ sai lệch trong tóm tắt dữ liệu.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Ứng dụng đại số gia tử trong tóm tắt dữ liệu bằng ngôn ngữ

JOURNAL OF SCIENCE OF HNUE DOI: 10.18173/2354-1059.2015-00010 Natural Sci. 2015, Vol. 60, No. 4, pp. 71-79 This paper is available online at http://stdb.hnue.edu.vn ỨNG DỤNG ĐẠI SỐ GIA TỬ TRONG TÓM TẮT DỮ LIỆU BẰNG NGÔN NGỮ Phạm Thị Lan và Hồ Cẩm Hà Khoa Công nghệ thông tin, Trường Đại học Sư phạm Hà Nội Tóm tắt. Tóm tắt dữ liệu bằng ngôn ngữ (linguistic database summarization) là một trong những khả năng mà các hệ thống thông tin hướng đến. Kacprzyk và các cộng sự đã đạt được nhiều kết quả khi nghiên cứu bài toán tóm tắt dữ liệu do Yager đề ra (1982) dựa trên lí thuyết mờ của Zadeh. Trong bài báo này, chúng tôi trình bày một phương pháp mới để sinh ra các tóm tắt bằng ngôn ngữ mà ngữ nghĩa dựa trên cấu trúc Đại số gia tử. So với cách tiếp cận dựa trên lí thuyết mờ, cách tiếp cận dựa trên Đại số gia tử của chúng tôi hạn chế được sự mất thông tin và làm giảm độ sai lệch trong tóm tắt dữ liệu. Từ khóa: Tóm tắt dữ liệu, đại số gia tử, định lượng ngôn ngữ. 1. Mở đầu Dữ liệu con người thu thập được ở nhiều dạng: dạng số, dạng phi số (từ ngữ, hình ảnh, âm thanh...). Tuy nhiên, trong hầu hết các tình huống, chúng ta đưa ra quyết định dựa trên các thông tin diễn đạt bằng ngôn ngữ. Các câu tóm tắt dữ liệu bằng ngôn ngữ được rút ra từ những cơ sở dữ liệu là một dạng của tri thức. Do đó, tóm tắt dữ liệu bằng ngôn ngữ là cơ sở quan trọng trong các hệ thống hỗ trợ ra quyết định, điều khiển tự động. Một tóm tắt dữ liệu theo Yager (1982) định nghĩa trong [1] gồm có 3 thành phần: tóm tắt S, định lượng thỏa đáng Q, độ tin cậy T. Dựa trên khái niệm protoform của Zadeh, các tác giả Kacprzyk, Zadrozny [2] đã đưa ra hai dạng tổng quát cho một tóm tắt như sau: Dạng 1: Q y are S. Ví dụ: Hầu hết (Q) công nhân (y) lương cao (S). Dạng 2: Q B y are S. Ví dụ: Hầu hết (Q) công nhân (y) trẻ (B) lương cao (S). Với y có nghĩa là bản ghi, B là điều kiện lọc. Các nghiên cứu về tóm tắt dữ liệu [1-4] đều dựa trên lí thuyết tập mờ. Khi đó, ngữ nghĩa của các hạng từ trong S, B, Q được diễn đạt bằng các tập mờ, độ tin cậy T được tính toán dựa trên giá trị của các hàm thuộc như công thức (1) và (2) [5]. Công thức (3) tính độ thỏa mãn (matching degree) của bản ghi R trên điều kiện AT = F V (AT là một thuộc tính, FV là hạng từ, ví dụ Tuổi = trẻ ). Công thức (4) tính độ phù hợp (matching degree) của bản ghi R với truy vấn “Q trong số N điều kiện thỏa mãn” [3]. 1 n  (1) truth(Q y are S )  Q   S  yi  n  i 1   n      B  yi   S  yi    (2) i 1 truth (Q B y are S )  Q  n    B  yi    i 1   md  AT  FV , R    FV   R  AT    (3)  1 N  (4)   md Q Cli 1,..., N  , R  Q     md  Cli , R      n i 1  Ngày nhận bài: 13/4/2015. Ngày nhận đăng: 22/5/2015. Tác giả liên lạc: Phạm Thị Lan, địa chỉ e-mail: ptlan@hnue.edu.vn 71
Phạm Thị Lan và Hồ Cẩm Hà Trước hết, hạng từ được xác định theo công thức (1) và (2) (hạng từ có độ tin cậy cao nhất sẽ được chọn đưa vào câu tóm tắt) chưa chắc đã diễn đạt đúng ngữ nghĩa tóm tắt dữ liệu so với thực tế. Xét ví dụ sau đây. Ví dụ 1.1. Cơ sở dữ liệu gồm có 20 bản ghi, số người và độ thuộc của tuổi vào hạng từ trẻ như trong Bảng 1. Ta cần đánh giá về tỉ lệ người trẻ so với tổng số người trong cơ sở dữ liệu. Đây là một dạng tóm tắt theo kiểu biết S, cần xác định Q. Giả sử các hạng từ biểu diễn giá trị cho thuộc tính Tuổi là trẻ, trung niên, già, 3 hạng từ biểu diễn cho Q là một ít, khoảng một nửa, hầu hết với các tập mờ biểu diễn cho chúng như trong Hình 1. Bảng 1. Thống kê số lượng công nhân theo tuổi Số người 5 5 5 5 Tuổi 20 22 29 45 Độ thuộc 0.9 0.8 0.5 0 1.2 Tre Trung nien Gia 1.0 0.8 0.6 0.4 0.2 0 0 10 20 30 40 50 60 70 80 90 (a) (b) Hình 1. (a) Hàm thuộc biểu diễn ngữ nghĩa của hạng từ một ít, khoảng một nửa, hầu hết (b) Hàm thuộc biểu diễn ngữ nghĩa của hạng từ trẻ, trung niên, già 1 n Đặt TBC   S  yi  , công thức (1) trở thành T  truth  Q y are S   Q TBC  n i 1 Áp dụng cho dữ liệu trong Bảng I, ta có: 1 20 0.9  5  0.8  5  0.5  5  0  5  trÎ  yi   20  TBC   0.55 i 1 20 Dựa vào Error! Reference source not found.(b), ta có ước lượng như sau: T1  mét Ýt  0.55  0 , T2  kho¶ng mét nöa  0.55  0.8 , T3  hÇu hÕt  0.55  0.1 . Như vậy với cách tiếp cận của Kacprzyk [2] dựa trên lý thuyết mờ, câu tóm tắt được chọn là “Khoảng một nửa số người có tuổi trẻ” có độ tin cậy T = 0.8 cao nhất. Nhưng nhìn vào Bảng 1, ta có thể thấy câu tóm tắt đó không phù hợp, mà “Hầu hết số người có tuổi trẻ” là kết luận đúng hơn mặc dù độ tin cậy của câu này thấp hơn (T = 0.1). Trong trường hợp khác, nếu giá trị của biểu thức bằng với hoành độ giao điểm G của hai hàm thuộc của hầu hết và khoảng một nửa thì khi đó sẽ có hai hạng từ định lượng khác nhau với độ tin cậy như nhau và độ tin cậy rất thấp. Theo quan điểm của logic mờ, để khắc phục điều này cần thêm vào một hạng từ khá nhiều với thứ tự về mặt ngữ nghĩa là khoảng một nửa ≤ khá nhiều ≤ hầu hết (hàm thuộc biểu diễn bằng nét đứt trong Hình 2). Khi đó, hạng từ được chọn cho câu kết luận là Q = khá nhiều với độ tin cậy cao T = 0.95. Tuy nhiên, cách làm này không tránh được có nhiều hạng từ cùng độ tin cậy trong khi ngữ nghĩa định lượng của chúng là khác nhau (phát sinh giao điểm H trong Hình 2 mà "Khá nhiều" (trẻ) khác với "khoảng một nửa" (trẻ)). Như vậy, công thức (1), (2) có thể đưa ra những hạng từ Q không hợp lí. 72
Ứng dụng đại số gia tử trong tóm tắt dữ liệu bằng ngôn ngữ Hình 2. Bổ sung thêm hạng từ “khá nhiều” Mặt khác, còn có những điểm không hợp lí trong truy vấn khi sử dụng công thức (4), (5). Trong trích rút câu tóm tắt, truy vấn dữ liệu là một giai đoạn có vai trò quyết định đến độ tin cậy. Theo [2, 4] nếu độ phù hợp của bản ghi R lớn hơn một giá trị ngưỡng thì R được đưa vào kết quả truy vấn. Trong 1 N md  Cli , R  (trung bình cộng độ phù hợp của N điều kiện) có thể dẫn đến N công thức (4), giá trị i 1 kết quả sai lệch. Cho dữ liệu trong Bảng 2, hai điều kiện truy vấn được xem xét là “Tuổi = trẻ ”; "Lương = cao". Nếu truy vấn trên hai điều kiện đó với định lượng Q = tất cả (nghĩa là truy vấn những bản ghi thỏa đồng thời cả hai điều kiện) thì hai bản ghi có cùng độ phù hợp (0.4) với câu truy vấn. Rõ ràng điều này không hợp lí vì bản ghi thứ nhất không thỏa điều kiện "Lương = cao". Việc lấy trung bình cộng độ phù hợp của bản ghi với các điều kiện đã che giấu sự không phù hợp với một điều kiện nào đó. Bảng 2. Độ thuộc của thuộc tính Tuổi và Lương của hai bản ghi R1 và R2 vào 2 hạng từ tương ứng trẻ và cao trẻ(tuổi) cao(lương) R1 0.8 0 R2 0.4 0.4 Nhằm khắc phục những hạn chế đã được chỉ ra ở trên trong tóm tắt dữ liệu, chúng tôi chọn cách tiếp cận ứng dụng Đại số gia tử trong cả hai giai đoạn truy vấn và chọn hạng từ Q cho bài toán này. Đại số gia tử (ĐSGT) do Nguyễn Cát Hồ và W.Wechler đề xuất năm 1990. Đây là một cấu trúc đại số cho miền giá trị của các hạng từ mà ngữ nghĩa được xác định dựa trên thứ tự của nó trong miền hạng từ [6]. ĐSGT được trang bị các công thức để dễ dàng tính toán các định lượng mờ như độ đo mờ, khoảng mờ, ánh xạ định lượng ngữ nghĩa dựa trên bộ tham số với số lượng nhỏ hơn hoặc bằng 5 và dễ dàng được xác định dựa trên tri thức thông thường của con người. Ưu điểm nổi bật của ĐSGT là các tính toán, ánh xạ luôn luôn bảo toàn quan hệ thứ tự ngữ nghĩa. Trong bài báo này, thuật ngữ "tóm tắt dữ liệu bằng ngôn ngữ" được viết tắt bằng LDS (Linguistic database summarization). 2. Nội dung nghiên cứu 2.1. Đại số gia tử Trong phần này, khái niệm cơ bản về đại số gia tử và định lượng ngữ nghĩa trong đại số gia tử được tóm tắt theo [6]. 2.1.1. Các khái niệm cơ bản Cho X là một biến ngôn ngữ và Dom(X ) là tập chứa tất cả các hạng từ trong tập giá trị của biến X. Tập X = Dom(X ) có thể được coi như là một cấu trúc đại số AX = (X, G, C, H, ), trong đó: 73
Phạm Thị Lan và Hồ Cẩm Hà - (X, ) là cấu trúc dựa trên thứ tự,  là quan hệ thứ tự sinh ra từ ngữ nghĩa vốn có của các hạng từ của biến X. - G = {c, c+} là tập các phần tử sinh, c+ được coi là hạng từ nguyên thủy dương, c- là hạng từ nguyên thủy âm. Ta có c-  c+. Ví dụ: chậm  nhanh, ít  nhiều. - C = {0, W, 1} tập các phần tử hằng thỏa mãn 0  c-  W  c+  1, hai phần tử 0 và 1 được coi là hạng từ nhỏ nhất, lớn nhất trong cấu trúc (X, ), W là phần tử trung bình. Ví dụ: 0 có nghĩa là cực kì chậm, W có nghĩa là trung bình, 1 có nghĩa là cực kì nhanh. - HI = H  {I} với H là tập các gia tử của biến X. I là một gia tử nhân tạo mang nghĩa của phần tử đơn vị, tức là Ix = x. Tập H gồm các gia tử dương H+ và các gia tử âm H-. Các gia tử dương làm tăng ngữ nghĩa của các hạng từ mà nó tác động, còn các gia tử âm làm giảm ngữ nghĩa của các hạng từ. Giả sử rằng H = {h0, h-1, ..., h-q} và H+ = {h0, h1,..., hp}, với h-1
Ứng dụng đại số gia tử trong tóm tắt dữ liệu bằng ngôn ngữ 2.2. Tóm tắt dữ liệu bằng ngôn ngữ Theo Yager (1982) bài toán LDS được phát biểu như sau [1]: - V là tập các thuộc tính cần quan tâm. Ví dụ: thuộc tính Tuổi trong CSDL công nhân; - Một tập các bản ghi có các thuộc tính trong V. Ví dụ: tập các công nhân với V(yi) là tuổi của công nhân yi ; - D = {V(y1), …., V(yn)} là tập dữ liệu; Một LDS của tập dữ liệu trên gồm có: - Một tóm tắt S (ví dụ: trẻ) (a summerizer); - Một định lượng thỏa đáng Q (ví dụ: hầu hết) (a quantity in agreement); - Độ đúng đắn T (ví dụ: 0,7) (truth degree); Ví dụ: Hầu hết công nhân là trẻ (Truth = 0,7). Tóm tắt S là một diễn đạt bằng ngôn ngữ tự nhiên, một phương tiện giao tiếp phù hợp nhất của con người. Một tóm tắt đơn giản chỉ đưa ra đánh giá cho một thuộc tính. Có thể mở rộng tóm tắt trên nhiều thuộc tính như là “trẻ và lương cao”. Sau đó có thể là các tổ hợp phức tạp hơn nữa. Các điều kiện trên các thuộc tính có thể là AND hoặc/và OR, k trong số n, hầu hết... Định lượng thỏa đáng Q là chỉ số thể hiện số lượng dữ liệu thỏa tóm tắt và được diễn đạt bằng một hạng từ. Cơ bản có hai loại định lượng bằng ngôn ngữ là: 1) Tuyệt đối: khoảng 5, một vài, không nhỏ hơn 20, . . . 2) Tương đối: một ít, hầu hết, gần như tất cả... Định lượng tương đối chính là định lượng mờ. Độ đúng đắn T là một giá trị nằm trong khoảng [0, 1]. Ngữ nghĩa của T thể hiện chất lượng hoặc độ tốt của tóm tắt. Giá trị T đã từng được tính theo 2 phương pháp hoặc bằng công thức tính toán của Zadeh (1983) đối với một câu có định lượng bằng ngôn ngữ hoặc là dùng phép toán tính trung bình có trọng số (OWA) của Yager (1988) [2]. Các công thức tính toán trong cả hai phương pháp nói trên đều dựa vào giá trị hàm thuộc tóm tắt S và định lượng thỏa đáng Q khi S và Q được biểu diễn bằng các tập mờ. Ở đây không xét đến các LDS định lượng tuyệt đối như “Hơn 70% số công nhân có tuổi dưới 35” mà thay vào đó là LDS có nghĩa tương tự nhưng sử dụng ngôn ngữ tự nhiên như “Hầu hết công nhân là trẻ”. Tức là, ba thành phần trong dạng tiền định Q, B, S là các hạng từ trong ngôn ngữ tự nhiên. Trong khi đó, giá trị thuộc tính trong cơ sở dữ liệu là các con số [2]. Đã có một số tiêu chuẩn định tính khác T được đề xuất để đánh giá một LDS như độ đo thông tin [1], độ đúng đắn (truth), độ mờ (imprecision), độ bao quát (covering), độ thích hợp (appropriateness), độ dài (length) [2]. Kacprzyk và Zadrozny [2] đã đưa ra 5 kiểu tóm tắt bằng ngôn ngữ theo mức độ khái quát tăng dần như trong Bảng 3. Trong đó: Scấu trúc – các thuộc tính và liên kết của chúng, Sgiá trị– các giá trị của thuộc tính cần xác định. Bảng 3. Các kiểu tóm tắt dữ kiệu bằng ngôn ngữ Kiểu Cho trước Yêu cầu Ghi chú 1 S Q Tóm tắt đơn giản thông qua truy vấn 2 SB Q Tóm tắt có điều kiện thông qua truy vấn 3 Q Scấu trúc Sgiá trị Tóm tắt đơn giản hướng đến giá trị 4 Q Scấu trúc B Sgiá trị Tóm tắt có điều kiện hướng đến giá trị 5 Rỗng SBQ Các luật mờ thông thường 2.3. Ứng dụng đại số gia tử trong tóm tắt dữ liệu bằng ngôn ngữ Đã có những nghiên cứu ứng dụng ĐSGT trong truy vấn mờ và hạng từ định lượng cũng được đưa vào truy vấn [8,9]. Các nghiên cứu trước đây, xây dựng ĐSGT cho các thuộc tính luôn giả thiết fm(W) = 0 và hạng từ định lượng được xác định trước. Trong bài toán LDS, hạng từ định lượng Q là một thành phần trong đầu vào (kiểu 3, 4), cũng có thể là thành phần trong đầu ra (kiểu 1, 2, 5). Dưới đây, chúng tôi trình bày phương pháp sử dụng ĐSGT mở rộng với fm(W) ≠ 0 để phù hợp hơn thực tế. Tập gia tử là H   h1 và H   h1 [7]. 75
Phạm Thị Lan và Hồ Cẩm Hà 2.3.1. Sử dụng đại số gia tử trong truy vấn mờ Với mỗi thuộc tính tham gia trong truy vấn theo điều kiện S hoặc điều kiện lọc B, ta xây dựng một ĐSGT cho miền giá trị của chúng. Không mất tính tổng quát, giả sử rằng điều kiện lọc B và điều kiện truy vấn S là điều kiện đơn dạng “AT = AF”, với AF là một hạng từ. Thuật toán 2.1. Truy vấn CSDL theo điều kiện đơn “AT = AF” Vào: Quan hệ r xác định trên tập thuộc tính U = {AT1, …, ATn} Câu truy vấn dạng Select … from … where AT = AF Ra: Quan hệ rresult thỏa mãn với mọi bộ t rresult có AT = AF Phương pháp: (1) Xác định miền tham chiếu thực cho thuộc tính AT là DAT = [minAT, maxAT]. Xây dựng ĐSGT cho thuộc tính AT (2) Chọn G = {c+, c-}, C = {0, W, 1}, H- = {h-1}, H+ = {h1}. (3) Xác định khoảng giá trị tương ứng với W là [min W, maxW][minAT, maxAT] (4) Tính độ đo mờ: maxW  minW  1 minW  1 fm W   maxAT  minAT  1   , fm c   max AT  minAT  1 , fm  c    1  fm W   fm  c   (5) Chọn độ đo mờ cho h-1, tính độ đo mờ của h1 theo công thức (6) Xác định tập hạng từ mức k là Xk {W}, k là độ dài hạng từ AF (7) Tính các khoảng mờ cho tập các hạng từ trong Xk {W}: I(x1),I(x2 ), …., I(x (8) Xác định khoảng tham chiếu tương ứng của AF là DAF Thực hiện truy vấn (9) rresult =  (10) Với mỗi bộ t r thỏa t(AT) DAF thì rresult = rresult  t (11) Trả về rresult Việc sử dụng ĐSGT trong truy vấn mờ theo cách này là rất tự nhiên và đảm bảo sự hợp lí về ngữ nghĩa. Vì khi giá trị của thuộc tính AT là t(AT)DAF thì AF chính là diễn đạt bằng ngôn ngữ của giá trị đó. Hơn nữa, một bản ghi có được đưa vào kết quả truy vấn hay không chỉ phụ thuộc vào các giá trị thuộc tính của nó mà không bị tác động bởi các bản ghi khác. Khi đã được đưa vào kết quả truy vấn thì nó được tính một đơn vị bản ghi trong kết quả. Ví dụ 2.1: Xét một truy vấn có điều kiện “Tuổi = trẻ”. Xây dựng một ĐSGT như sau: G = {trẻ, già}, H- = {khá}, H+ = {rất}. Dựa vào biểu diễn tập mờ của 3 hạng từ của thuộc tính tuổi trong Hình 1a, miền tham chiếu của tuổi là [0, 90], dưới 30 tuổi được gọi là trẻ, tuổi từ 30 đến 59 được gọi là trung niên, từ 60 tuổi được gọi là già. Khi đó ta có fm(trẻ) = 30/90 = 1/3, fm(trung niên) = 1/3, fm(già) = 1/3. Giả sử fm(khá) = 0.4, fm(rất) = 0.6. Khoảng mờ: I(trẻ)= [0, 1/3), I(trung niên) = [1/3, 2/3), I(già) = [2/3, 1). Miền tham chiếu tương ứng với trẻ là Dtrẻ = [0, 30) Kết quả truy vấn trên tập dữ liệu như trong Bảng 1, cho kết quả truy vấn có 15 bản ghi. Tỉ lệ bản ghi thỏa truy vấn là: f = 15/20 = 0.75. Lúc này, sử dụng hạng từ hầu hết để diễn đạt cho giá trị 0.75 sẽ có được độ tin cậy cao. 2.3.2. Xây dựng một đại số gia tử cho định lượng bằng ngôn ngữ Coi tập các hạng từ dùng để diễn đạt định lượng là Xk {0, W, 1} với hằng 0 được hiểu là không có bản ghi nào thỏa, hằng 1 là tất cả các bản ghi đều thỏa, hằng W được hiểu là khoảng một nửa. Nếu cần tăng độ chính xác cho việc diễn đạt Q thì chỉ cần tăng giá trị của k. Thông thường k≤3. Thuật toán 2.2: Áp dụng ĐSGT trong định lượng bằng ngôn ngữ Vào: Một tập các hạng từ T, giá trị f. Ra: Hạng từ yT diễn đạt cho f. 76
Ứng dụng đại số gia tử trong tóm tắt dữ liệu bằng ngôn ngữ Phương pháp: (1) Chọn G = {c-, c+}, C = {0, W, 1}, H- = {h-1}, H+ = {h1}. (2) Chọn fm(c+), fm(c-) và fm(W) sao cho phù hợp với từng ngữ cảnh cụ thể (3) Chọn fm(h-1), tính fm(h1). (4) Chọn k sao cho Q cần tìm thuộc Xk{0, W, 1} (5) Tính toán các khoảng mờ của tập các hạng từ Xk{W} (6) Nếu giá trị fI(x) thì trả về x. Ví dụ 2.2: Các hạng từ định lượng tương đối thường dùng là: rất ít, ít, nhiều, hầu hết, khoảng một nửa. Thứ tự ngữ nghĩa của các hạng từ như sau: rất ít < ít < khoảng một nửa < nhiều < hầu hết. Xây dựng một ĐSGT như sau: G = {ít, nhiều}, C = {0, W, 1}. Nếu tỉ lệ từ 45% đến 55% thì coi là khoảng một nửa. Do đó khoảng mờ của W là [0.45, 0.55]. Từ đó, ta suy ra độ đo mờ là fm(W) = 0.1 và fm(0) = fm(1) = 0, fm(ít) = fm(nhiều) = 0.45. Chọn tập gia tử H- = {khá}, H+ = {rất} với fm(khá) = 0.4, fm(rất) = 0.6 Ta sử dụng các hạng từ trong tập X2 {0, W, 1} = {0, rất ít, khá ít, W, khá nhiều, rất nhiều, 1}. Bảng 4 sau đưa ra cách ánh xạ tập các hạng từ cần dùng với tập các hạng từ trong X2{0, W, 1}. Bảng 4. Ánh xạ giữa hai tập hạng từ T và X2{0, W, 1} Hạng từ Rất ít Ít Khoảng Nhiều Hầu hết Không có Tất cả cần dùng một nửa Hạng từ Rất ít Khá ít W Khá nhiều Rất nhiều 0 1 trong X2 Tính toán khoảng tính mờ của các hạng từ trong X2 theo các tham số mờ đã chọn ở trên. Ta có kết quả như Hình 3. fm(rất ít) = 0.27, fm(khá ít) = 0.18, fm(khá nhiều) = 0.18, fm(rất nhiều) = 0.27 I(rất ít) I(khá ít) I(W) I(khá nhiều) I(rất nhiều) 0 1 0.27 0.45 0.55 0.73 Hình 3. Các khoảng mờ của các hạng từ định lượng Với cơ sở dữ liệu gồm 20 công nhân như trong Bảng 1. Sau khi thực hiện truy vấn với điều kiện “Tuổi = trẻ” như trong ví dụ 2.1, ta có tỉ lệ số bản ghi thỏa so với tổng số bản ghi là 0,75. Do đó, định lượng thỏa Q = hầu hết vì 0,75  I (rất nhiều). Hạng từ hầu hết là duy nhất. Kết quả này cho thấy trong cùng một tình huống như trong Ví dụ 1.1, việc sử dụng thuật toán 2.1 và 2.2 sẽ đưa đến câu tóm tắt như mong muốn. Chọn hạng từ diễn đạt Q theo thuật toán 2.2 đảm bảo đúng về mặt ngữ nghĩa và cho kết quả duy nhất. Ở đây không đề cập đến giá trị độ đúng đắn T vì hạng từ được chọn có độ đúng đắn cao nhất, các hạng từ còn lại có độ đúng đắn bằng không. 2.3.3. Thuật toán cho kiểu tóm tắt Trong phần này sẽ trình bày các cách sinh các LDS theo 5 kiểu trong Bảng 3 sử dụng hai thuật toán 2.1 và 2.2. Kiểu 1, 2 dễ dàng thực hiện được khi áp dụng thuật toán 4.1 trong lọc và truy vấn, 77
Phạm Thị Lan và Hồ Cẩm Hà thuật toán 2.2 dùng để xác định hạng từ cho Q. Thuật toán 2.3 dưới đây để sinh LDS kiểu 3 và có thể mở rộng cho kiểu 4 bằng việc bổ sung thêm giai đoạn lọc trước khi thực hiện truy vấn. Thuật toán 2.3: Tóm tắt dữ liệu theo kiểu 3 Vào: Q, Scấu trúc Ra: Sgiá trị * Phương pháp: Bước 1: Xây dựng một ĐSGT cho miền hạng từ của thuộc tính trong điều kiện S. Bước 2: Với mỗi hạng từ mờ xi trong tập Xk: - Thực hiện truy vấn theo điều kiện AT = xi . - Tính fi = số bản ghi thỏa điều kiện AT = xi/tổng số bản ghi. - Từ fi xác định hạng từ Qi theo thuật toán 2.2. - Nếu Q = Qi thì Sgiá trị = xi Dưới đây trình bày một thuật toán để sinh ra các tóm tắt có dạng tiền định “Q B y are S” về mối quan hệ giữa hai thuộc tính AT1 và AT2. Tóm tắt này thuộc kiểu thứ 5, tức là ba thành phần Q, B, S là đầu ra của thuật toán. Không làm mất tính tổng quát, giả sử rằng điều kiện lọc B và điều kiện truy vấn S là điều kiện đơn trên một thuộc tính có dạng “AT = AF” với AF là một hạng từ mờ. Thuật toán 2.4: Trích rút tóm tắt về mối quan hệ giữa hai thuộc tính AT1 và AT2 Vào: AT1, AT2 lần lượt là thuộc tính trong điều kiện lọc B và điều kiện truy vấn S, quan hệ r Ra: Các tóm tắt dạng “Q B y are S” * Phương pháp: Bước 1: Xây dựng ĐSGT cho miền hạng từ của thuộc tính AT1. Xác định miền tham chiếu cho thuộc tính , phân hoạch thành các khoảng mờ mức k. Bước 2: Xây dựng ĐSGT cho miền hạng từ của thuộc tính AT2. Xác định miền tham chiếu cho thuộc tính , phân hoạch thành các khoảng mờ mức k. Bước 3: Xây dựng ĐSGT cho miền hạng từ của định lượng Q. Bước 4: Với mỗi hạng từ trong thực hiện: - Lọc trên r theo điều kiện được kết quả là r1. - Với mỗi hạng từ trong thực hiện: + Truy vấn trên r1 theo điều kiện được kết quả r2 + Tính tỉ lệ f = số bản ghi trong r2/ số bản ghi trong r1 + Từ f xác định Q + Sinh câu tóm tắt là “Q y are ” Thuật toán 2.4 đã xét được tất cả các tổ hợp của B và S , đồng thời chọn được Q phù hợp với từng tổ hợp đó, với và . Trong thực tế, thường sử dụng 2 gia tử và k ≤ 3 [7]. Do đó, và . 3. Kết luận Khai phá tri thức từ cơ sở dữ liệu đóng vai trò quan trọng trong các hệ thống thông tin, các hệ trợ giúp ra quyết định. Tóm tắt dữ liệu bằng ngôn ngữ chính là một quá trình khai phá tri thức. Bài báo đã phân tích một vài hạn chế khi thực hiện tóm tắt dữ liệu bằng ngôn ngữ dựa trên lí thuyết tập mờ, đồng thời đề xuất cách tiếp cận ĐSGT vào tóm tắt dữ liệu nhằm khắc phục được các hạn chế đó. Việc sử dụng ĐSGT để mở rộng tóm tắt dữ liệu bằng ngôn ngữ cho các cơ sở dữ liệu mờ, cơ sở dữ liệu hướng đối tượng mờ, xem xét mối quan hệ giữa tóm tắt dữ liệu với khai phá luật kết hợp là hướng phát triển tiếp theo của bài báo này. Lời cảm ơn. Bài báo được thực hiện với sự hỗ trợ từ Quỹ Phát triển Khoa học công nghệ Việt Nam (NAFOSTED), mã số 102.05-2015.28. 78
Ứng dụng đại số gia tử trong tóm tắt dữ liệu bằng ngôn ngữ TÀI LIỆU THAM KHẢO [1] R. R. Yager, 1982. A New Approach tothe Summarization of Data. Information Sciences 28, 1982, pp. 69-86. [2] J. Aprzyk, S. Arozny, 2005. Linguistic database summuries and their protoforms: towards natural language based knowledge discovery tools. Information Sciences 173, pp. 281-304. [3] J. Kacprzyk, S. Zadrozny, 2001. Computing with words in intelligent database querying: standalone and Internet-based applications. Information Sciences 134, pp. 71-109. [4] J. Kacprzyk, S. Zadrozny, 2010. Computing With Words Is an Implementable Paradigm: Fuzzy Queries, Linguistic Data Summaries, and Natural-Language Generation. IEEE Transactions on Fuzzy Systems, Vol. 18, No. 3, pp. 71-109. [5] L. A. Zadeh, 1983. A computational approach to fuzzy quantifiers in natural languages. Comp & Maths with Appls, Vol. 9. No. 1, pp. 149-184. [6] Cat Ho Nguyen, Dong Anh Nguyen and Nhu Lan Vu, 2011. Fuzzy Controllers Using Hedge Algebra Based Semantics of Vague Linguistic Terms. Nova Science Publishers, Inc, ISBN 978-1-61324-488-3. [7] Cat Ho Nguyen, Thai Son Tran, Dinh Phong Pham, 2014. Modeling of a semantics core of linguistic terms based on an extension of hedge algebra semantics and its application. Knowledge-Based Systems 67, pp. 244-262. [8] Nguyễn Cát Hồ, Nguyễn Công Hào, 2008. Một phương pháp xử lí truy vấn trong CSDL mờ tiếp cận ngữ nghĩa lân cận của Đại số gia tử. Tạp chí Tin học và điều khiển học, T.24, S.4, pp. 281-294. [9] Nguyễn Công Hào, Trương Thị Mỹ Lệ, 2012. Truy vấn trong cơ sở dữ liệu hướng đối tượng mờ dựa trên ngữ nghĩa của Đại số gia tử. Tạp chí khoa học, Đại học Huế, Tập 74B, Số 5, pp. 39-53. ASTRACT Applying hedge algebra in linguistic database summarization Linguistic database summarization is a capability needed by any intelligent system. Kacprzyk et al. achieved good results when they studied the problem of linguistic database summarization introduced by Yager (1982) and based on Zadeh’s fuzzy theory. In this paper, we present a new method to generate linguistic summaries using hedge algebra structure. Compared with the fuzzy set approach, ours, based on hedge algebra, limits the loss of information and reduces bias in the data summary. Keywords: Database summarization, hedge algebra, linguistic quantifier. 79

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.