Tài liệu Toán: Đề xuất cải tiến thuật toán tìm kiếm trong cơ sở dữ liệu mờ

Tìm hiểu các phương pháp cải tiến thuật toán tìm kiếm trong cơ sở dữ liệu mờ nhằm nâng cao hiệu suất xử lý và độ chính xác kết quả truy vấn.

• Tác giả: Nguyễn Thanh Tân
• Người hướng dẫn: PGS. Nguyễn Thiện Luận
• Trường học: Trường Đại học Công nghệ thông tin và Truyền thông, Đại học Thái Nguyên
• Chuyên ngành: Khoa học máy tính
• Đề tài: Đề xuất cải tiến thuật toán tìm kiếm trong cơ sở dữ liệu mờ
• Loại tài liệu: Luận văn Thạc sĩ
• Năm xuất bản: 2016
• Địa điểm: Thái Nguyên

Tóm tắt

I. Tổng Quan Về Lý Thuyết Mờ Và Cơ Sở Dữ Liệu Mờ

Lý thuyết mờ là một nhánh quan trọng của toán học hiện đại, được sáng lập bởi Lotfi Aliasker Zadeh vào năm 1965. Khác với logic cổ điển chỉ có hai giá trị đúng/sai, lý thuyết mờ cho phép các giá trị trung gian, phản ánh tính không chắc chắn của thế giới thực. Cơ sở dữ liệu mờ là sự kết hợp giữa lý thuyết mờ và hệ quản trị cơ sở dữ liệu, cho phép lưu trữ và truy vấn dữ liệu không chính xác, không đầy đủ. Ứng dụng của cơ sở dữ liệu mờ ngày càng phổ biến trong các lĩnh vực như y tế, tài chính, quản lý hình ảnh và xử lý video. Việc cải tiến thuật toán tìm kiếm trong môi trường dữ liệu mờ trở nên cần thiết để nâng cao hiệu suất và độ chính xác của các hệ thống tìm kiếm hiện đại.

1.1. Khái Niệm Tập Mờ Và Hàm Thuộc

Tập mờ là mở rộng của khái niệm tập hợp cổ điển, trong đó mỗi phần tử có mức độ thuộc về từ 0 đến 1. Hàm thuộc định nghĩa mức độ này cho từng phần tử, thay vì chỉ có hai trạng thái thuộc hoặc không thuộc. Có nhiều kiểu hàm thuộc khác nhau như hàm tam giác, hàm hình thang, hàm L (ghế) và hàm Gamma tuyến tính, mỗi loại phù hợp với các ứng dụng cụ thể khác nhau.

1.2. Các Phép Toán Trên Tập Mờ

Các phép toán trên tập mờ bao gồm phép giao, phép hợp, phép bổ sung dựa trên các hàm thuộc. Ngoài ra, trong cơ sở dữ liệu mờ còn có các phép toán đặc biệt như phép chọn mờ, phép chiếu mờ và phép kết nối mờ, giúp thực hiện truy vấn phức tạp trên dữ liệu không chính xác.

II. Cải Tiến Thuật Toán Tìm Kiếm Trong Cơ Sở Dữ Liệu Mờ

Thuật toán tìm kiếm truyền thống gặp khó khăn khi làm việc với dữ liệu mờ do tính không chắc chắn và không đầy đủ của dữ liệu. Đề xuất cải tiến tập trung vào việc tích hợp lý thuyết mờ vào quá trình tìm kiếm, cho phép các hệ thống xử lý truy vấn một cách linh hoạt hơn. Cải tiến thuật toán tìm kiếm đòi hỏi phải phát triển các phương pháp đối sánh (matching) mới, sử dụng khoảng cách Levenshtein hoặc khoảng cách Damerau-Levenshtein để so sánh độ tương đồng. Ngoài ra, việc áp dụng SIFT (Scale Invariant Feature Transform) và kỹ thuật phát hiện điểm đặc trưng (keypoint) giúp cải thiện hiệu suất tìm kiếm hình ảnh trong cơ sở dữ liệu video.

2.1. Sử Dụng Số Mờ Tam Giác Trong Tìm Kiếm

Số mờ tam giác (Triangular Fuzzy Number) được sử dụng để biểu diễn các giá trị không chính xác trong quá trình tìm kiếm. Cấu trúc ba tham số của số mờ tam giác cho phép mô tả tốt hơn mức độ không chắc chắn, từ giá trị tối thiểu đến tối đa. Phương pháp này cải thiện khả năng tìm kiếm mờ và đưa ra kết quả gần đúng (approximative) phù hợp hơn với yêu cầu người dùng.

2.2. Thuật Toán SIFT Cho Tìm Kiếm Hình Ảnh

Giải thuật SIFT (Scale Invariant Feature Transform) là một phương pháp mạnh mẽ để phát hiện và mô tả điểm đặc trưng (keypoint) trong hình ảnh. Quá trình bao gồm phát hiện các điểm cực trị trong không gian scale, định vị các điểm đặc trưng, và tính toán mô tả bộ cục bộ để đối sánh hình ảnh. Ứng dụng SIFT trong tìm kiếm video giúp cải thiện độ chính xác và tốc độ xử lý đáng kể.

III. Ứng Dụng Tìm Kiếm Video Trong Cơ Sở Dữ Liệu

Tìm kiếm video trong cơ sở dữ liệu là một ứng dụng thực tiễn quan trọng của cải tiến thuật toán tìm kiếm mờ. Hệ thống tìm kiếm video cần xử lý các chuỗi video với khối lượng dữ liệu lớn, yêu cầu phải phát hiện các điểm cực trị trong không gian scale để tách biệt các hồi (episode) hoặc các cảnh (scene) khác nhau. Quá trình phân đoạn video và mờ hóa video là các bước quan trọng giúp giảm kích thước dữ liệu và tăng tốc độ tìm kiếm. Các kỹ thuật như phát hiện chuyển cảnh sử dụng Difference of Gaussian (DoG) cho phép xác định ranh giới giữa các cảnh một cách chính xác.

3.1. Mô Hình Bài Toán Tìm Kiếm Video

Mô hình bài toán tìm kiếm video bao gồm cơ sở dữ liệu video, hệ thống tìm kiếm thông tin hỗ trợ, và các công cụ xử lý như phần mềm Smart Cutter for DV and DVB. Mô hình này cho phép người dùng thực hiện truy vấn bằng hình ảnh hoặc video mẫu, hệ thống sẽ trả về các kết quả tương tự từ cơ sở dữ liệu.

3.2. Quy Trình Tìm Kiếm Video Bằng Hình Ảnh

Quy trình tìm kiếm bằng hình ảnh trong cơ sở dữ liệu video bao gồm: trích xuất điểm keypoint từ hình ảnh truy vấn, tính toán mô tả các điểm đặc trưng, và so sánh với các điểm keypoint đã lưu trữ trong cơ sở dữ liệu. Sử dụng TCP socket cho giao tiếp client-server giúp cải thiện hiệu năng và cho phép xử lý song song.

IV. Đánh Giá Hiệu Năng Và Kết Quả Thực Nghiệm

Đánh giá hiệu năng của đề xuất cải tiến thuật toán tìm kiếm được thực hiện thông qua các bộ dữ liệu thực nghiệm với các video mẫu khác nhau. Các chỉ số đánh giá bao gồm tốc độ xử lý, độ chính xác kết quả, và khả năng xử lý dữ liệu không đầy đủ hoặc không chính xác. Kết quả thực nghiệm cho thấy phương pháp sử dụng số mờ tam giác và giải thuật SIFT cải thiện độ chính xác tìm kiếm từ 15-25% so với phương pháp truyền thống. Tối ưu hóa thuật toán thông qua việc giảm kích thước bộ mô tả keypoint và sử dụng bộ dữ liệu thông tin được lập chỉ mục giúp giảm thời gian truy vấn từ 30-40%.

4.1. Phương Pháp Đánh Giá Và Các Chỉ Số Hiệu Năng

Phương pháp đánh giá sử dụng các chỉ số hiệu năng như độ phủ (recall), độ chính xác (precision), và thời gian phản hồi. Bộ dữ liệu thực nghiệm bao gồm các video với độ dài khác nhau, nhiều cảnh (scene) và hồi (episode) khác nhau. Việc so sánh giữa các phương pháp được thực hiện trên cùng một bộ dữ liệu để đảm bảo tính công bằng.

4.2. Kết Quả Thực Nghiệm Và Hướng Phát Triển

Kết quả cho thấy thuật toán cải tiến đặc biệt hiệu quả với dữ liệu không chắc chắn và không chính xác. Hướng phát triển tiếp theo bao gồm tích hợp các kỹ thuật học máy (machine learning) để tự động hóa quá trình trích xuất đặc trưng và cải thiện độ chính xác của phép đối sánh mờ.

Trích đoạn nội dung tài liệu

Chương 1: Tổng quan về lý thuyết mỡ, cơ sở dữ liệu mờ và ứng dung 1. Tổng quan về lý thuyết mờ 1. Cỡ sở đữ liệu mờ, phương thức biểu điễn và ứng đụng 1. Tổng quan về phương pháp tìm kiếm mờ 1.

Kết luận chương. Chương 2: Thuật toán tìm kiếm trong cơ sỡ dữ liệu mời 2. Số mờ tam giác. Tổ chức đữ liệu cho thuật toán tìm kiểm dữ liệu mờ 2.

Cải tiễn thuật toán tìm kiếm dữ liệu mờ 2. Kết luận chương Chương 3: Cài đặt thuật toán tìm kiếm trong cơ sỡ đỡ liệu quản lý các chương trình truyền hình Đài PT - TH tỉnh Hòa Bình. Phân tích một số nhu cầu tìm kiếm video trong CSDL quân lý các chương trình truyền hình 3. Thiết kế mô hình bài toán tìm kiếm trong CSDL mờ quản lý các chương trình truyền hình 3.

Cài đặt thuật toán tìm kiểm mỡ và một số giao diện chính. Kết luận chương. Phương pháp nghiên cứu Sit dung các phương pháp nghiên cứu chính sau: - Phương pháp nghiên cứu lý thuyết: Phân tích, liệt kê, đối sánh, nghiên cứu tà liệu, tổng hợp các kết quả của các nhà nghiên cứu liên quan đến lĩnh vực nghiên cứ. ~ Phương pháp trao đổi khoa học, lấy ý kiến chuyên gia.

- Phương pháp thực nghiệm: Cài đặt thử nghiệm thuật toán cho bài toán tìm kiếm với điều kiện tìm kiếm mờ trong cơ sỡ dữ liệu mi quản lý các chương trình truyền hình. Ý nghĩa khoa học của đề tài - Giúp tìm hiểu, đảnh giá khái quát về hệ cơ sỡ đữ liệu mờ, các thuật toán tìm kiếm với điều kiện tìm kiếm mờ. - Vận dụng tốt thuật toán tìm kiếm với điều kiện tìm kiếm mỡ, giúp chúng ta cô thê đễ đàng tìm kiếm những nội đung trong cơ sở dữ liệu. - Xây dựng cơ sở khoa học cho các bài toán tìm kiếm trong cơ sở đữ liệu.

Tổng quan về lý thuyết mờ [5] L. Zadeh là người sắng lập ra ý th tập mỡ với hàng loạt bài báo mỡ đường cho sự phat trién và ứng dung của lý thuyết này, khởi đầu là bài báo “Fuzzy Sets” trén Tap chi Information and Control, 8, 1965. Ý tưỡng nổi bật của khái niệm tập mờ của Zadeh là từ những khái niệm trừu tượngvề ngữ nghĩa của thông tin mờ, không chắc chắn như trẻ, nhanh, cao thấp, xinh đẹp. ông đã tim ra cách biểu diễn nó, ằng một khái niệm toán học, được gọi là tập mờ, như 1à một sựkhái quát trực tiếp của khái niệm tập hợp kinh điển.

Khải niệm tập mở "Tập mờ44 được xác định trên không gian nền X bao gồm các phần tử, mà mỗi phần tử là một cp (x, we (2)) trong46 x € X'va ya (x) là ánh xa: wa: X— [0.1] Anh xa ¿ được gọi là hàm liên thuộc (hàm phụ thuộc hay hàm thuộc) của .Một sổ khái niệm của tập mờ' Định nghĩa 1. Độ cao của một tập mờ4 trên không gian nền X là giá trịh = sup g„ (x)chỉ giá trị nhỏ nhất trong các giá trị chặn trên của hàm /¿ (X). Miền xác định của tập mờ 4 trên khôi gian nền Ý được. ký hiệu bởi Š là tập con của Ý thoả mãn: S=suppue (8) = & €X/ wa ()> 0} Dinh nghia 1.

Miền tin cây của tập mỡ tập mờ4 trên không gian nên X được ký hiệu bởi 7 là tập con của X thoả mãn: 7= {x €. Miền biên của tập mờ tập mỡ4 trên không gian nền được kỹ hiệu bởi là tập con của X thoả mẫn: €Z/0</u@<1} Miễn tn cậy, — Miav Miễn xác định.1: Biểu diễn các miền của một tập mờ Định nghĩa 1. Tập cắt ø (4 € [0,]) của tập mỡ 4 trên không gian nền. _ được ký hiệu bởi 4; là tập con cia X théa min 4a= (¢/ ws (x) 2 0} và được gọi là tập cắt mạnh ø và ký hiệu là 4z.

néu Aq = (x / uy (x) > a} Định nghĩa 1. Tập mức a, hay là tập nhát cắt - œ của tập mờ tập mờ 4 trên không gian nén X ky hiệu bởi A(4) là tập các tập con cia Xthéa mãn: A4) = {%/ 1a G) = 4} với ø € [0,1] Dinh nghia 1. Tap mo A trên không gian nền X tuyến tính được gọi là. tập mở lỗi nếu .4; là tập lỗi vø € [0.

Lực lượng của tập mỡ 4 trên không gian nền X được biểu diễn như sau: NG CD) = Ya Œ) 1. Các pháp toán trên tập mo a) Phép hop hat tap ma: Dinh nghĩa 1.8: Hop cia hai tap mo 4 WB là một tập mỡ được xác dink trong không gian nền X'va cé him lién thude uu» (x) thôa mãn các tiên đề: + Chi phụ thuộc vào /¿ (+) và /s G) + Nếu /ø @) =0 với vx thì .ø G) = /ư G) + Cô tính giao hoán ga. ) 4 (X) + Có tính kết hợp đạu. c Œ) av@vo G) + Cé tinh không giảm (đồng biển).4: L2 8: 7 tạ, Œ Sa; GỒ S đi vẽ 6) S;2s @) 3) Pháp giao hai tập mờ: Dinh nghia 1.9: Giao của hai tập mờ4 và Ö là một tập mờ 4 ¬ B xác định trong không gian nền XÝ có hàm liên thuộc ø ~z (2) thöa mãn các tiên đề: + Chi phụ thuộc vào / (x) va ma (x) + Néu ys (x) = 0 với vx thi was (x) = wa (X) + Cé tính giao hoãn wa nz (© dana (x) + C6 tính kết hợp ga ~ø ¬c G)= á^@^o Œ) + C6 tính không giảm (đồng biển).

Nếu 4; C 4; thì 4; ¬ 8 C4; ¬ 8: May (X) Š tá (X) đai 8 (X) Š tay ¬ (X) ©. Phép bù của một tập mờ Dinh nghita 1.10: Tập bù của tập mỡ 4 trên nền X là mộttập mỡ (Ä, /z) xác định trên không gian nền X với hàm liên thuộc thỏa mãn các điều kiện: + 1 (2) chi phu thuse va0 wa (x) + Nếu wu G9 thi uz) + Nếu su 09 thi uz) + Nếu 4C 8 thì cô #2 Œ) > øs () Dinh nghia _1.11: Tập bù của tập mờ4 trên nền X là một tập mỡ (4, 2) xác định trên không gian nền X với him lién thuée (1): [0.1] thỏa "mãn các điều kiện sau: +4(0)=1 +u()=0 + Ma S us (14) > u(ua) ‘Néu hàm một biến u(u,) con théa min thém điều kiện. +Liên tục va #4 <ua =u (ua) > u(us) 8 "Thì phép bù trên còn gọi là phép bit mé chat. Mét phép bù mờ chặt được gọi là phép bù mở mạnh tiêu: = wa))tic a A= A + u(u(ua u(x) Hx) Hinh 1.2: Biểu diễn hàm liên thuộc của phép 1 Pháp hiệu đối xứng: Mỡ tông công thức cho phép hiệu đối xứng các tập kinh điển: 4 V B= (4.

8) \ (4 ¬ 8) = (4 ¬ B) © (4 ¬ 8) có thê xây dựng. phép hiệu đối xứng cho các tập mờ. Tử công thức xác định hàm liên thuộc đối. với phép hiệu đối xứng của các tập kinh điển.

Có thể áp đụng trực tiếp đề xây dung ham liên thuộc hiệu đối xứng của các tập mi (4, 14 (x)) va (B, ,z ()) may 30) = a (2) + pa (2) — ua (8) x wa @. Tích ĐỂ các: Cho tập mỡ (x, dụ: (x)), f=1,2,. trền các không gian nin Xí. Tích Đề các của ø tập mờ là một tập mờ: (61, 49), fat Œú, Xi, X9} trên không gian nền Xj xX;x.

Ä; có hàm liên thuộc được xác định như sa: /0x xxx, Út, Xi.14 Các kiểu ham thuge a. Tam gid (Triangular): Dinh nghĩa bỡi các cận đưới a, cận trên b và giá trim, a<m <b. Chiing ta gọi giá trị b - m là biên (margin) nếu giá trị này bằng giá trị m ~a. 9 0 nếu x < b hoặc x >b x-& ma 4nếu 4 < x<m Ma) =), oy.

=e nếum < x< b 1 néux =m Hình 1.3: Các tập mờ hình tam giác: a)Téng quét va b) Déiximg b. Singleton: Cô giá trị 0 tại tất cã các điểm trong tập vũ trụ, ngoại trừ tại điểm m cógiá trị 1, ding dé biéu diễn các giá trị rõ. SG(x) = nếu nếu xx #m =m Ly Hình 1.4: Tap ma Singleton c. Hàm L: Hàm này được định nghĩa bởi hai tham số a va b theo cach: be1 néux<a LG)= 47 néua<x<b IN.

Ham Gamma tuyến tính: Hàm này được định nghĩa bởi hai tham số a và b theo cách sau: nếu x< 4 Tứ) = nếu a < x < b nếu x> b 1 0 x Hình 1.6: Tap mé Gamma tuyén tinh e. Hàm hình thang: Được định nghĩa bỡi bộ 4 gid tri a b, ¢, d theo céng thức sau: nếu x < ø hoặc x > đ nếu a < x<b Tay=) b-a 37S néuc<x<d d-c 1 néub<x<e / / ab ed X Hình 1.7: Tap ma hinh thang 1. Các loại số mờ a. ,¿ () trong không gian nền số thực - được gọi là số thực mờ nếu thõa mãn 3 điều kiện: - 4 là tập mỡ chính tắc ul ~ dala la cdc khoảng đồng với vư € (0.1] - TậpS = supp/¿ (x) = {x € X/ #¿ @) > 0} g i nội ö.

SỐ mờ hình chuông: Là một tập mờ cô dạng [ a - a, a + Ø ] trong đô a2 0, £20 là các số thực với hàm liên thuộc: I@) khia-a<x<a Haag) @)={r@) Khia<x<a+ 0 Khi@<a-a)A(@w>a+8) c. Sé mé dangtam gidc: La m6t tap mé cé dang [a- a, a, a+ 8] trongdo a2 0, £20 là các số thực với hàm liên thuộc: x +1 khia~ø <x<a Haag) (*) = + +1 khia<x<a+†# 0 Khi x < đ— ø vàx > 4+ d. Sé mờ dạng hình thang: Là một tập mờ cô đạng [ a - 4, a, b, b + 8] trong đô ø > 0, đ > 0 là các số thực với hàm liên thuộc: 1 Khix<a<b x @ khia~ø <x<a Mcaae) 0) = {b— “ptt Mhibexsp+s 0 Khi (x < &— 8) hoặc ( > b+ Ø) e. Số mờ dạng khoảng: Là tập mờ cô đạng (a, z) trong đó z > 0 là các số thực với hàm liên thuộc: x +1 kha-er<xs<a eo (3) = +1 Kkhia<x<a+£ : 0 Khi x— a — £ hoặc x > & + £ 1.

Cỡ sở dữ liệu mờ, phương thức biểu diễn và ứng dụng [5] Mô hình quan hệ do Codd E. đề xuất năm 1970 đã đáp ứng được nhụ cầu lưu trữ và xử lý đữ liệu của con người trong một thời gian đài. Tuy nhiên, 12 mô hình này vị tên tại nhiều hạn chế chưa giải quyết được. Trên thực tế, đôi khi chúng ta có thể thu nhận được dữ liệu với thô tin không đầy đủ, hoặc có những thông tin không chính xác, không chắc chắn gọi chung là các dữ liệu mờ.

Nếu giới hạn trong mô hình cơ sở đữ liệu kinh điễn thì phải đợi đầy đủ.