Luận Văn Thạc Sĩ Đề Xuất Cải Tiến Thuật Toán Tìm Kiếm Trong Cơ Sở Dữ Liệu Mờ

Luận văn thạc sĩ toán học nghiên cứu đề xuất cải tiến thuật toán tìm kiếm trong cơ sở dữ liệu mờ, khảo sát thực trạng, phân tích nguyên nhân, đề xuất giải pháp cải thiện thực tiễ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: Đạ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: 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. Giới thiệu về luận văn thạc sĩ

Luận văn thạc sĩ với tiêu đề 'Cải tiến thuật toán tìm kiếm trong cơ sở dữ liệu mờ' tập trung vào việc nghiên cứu và đề xuất các phương pháp tối ưu hóa thuật toán tìm kiếm trong môi trường dữ liệu mờ. Cơ sở dữ liệu mờ là một lĩnh vực quan trọng trong công nghệ thông tin, đặc biệt khi xử lý các thông tin không chính xác, không đầy đủ hoặc không chắc chắn. Luận văn này nhằm mục đích cải thiện hiệu quả của các thuật toán tìm kiếm, giúp người dùng tìm kiếm thông tin một cách chính xác và nhanh chóng hơn.

1.1. Đối tượng và phạm vi nghiên cứu

Luận văn tập trung vào việc nghiên cứu các phương pháp tìm kiếm thông tin trong cơ sở dữ liệu mờ, đặc biệt là các dữ liệu không chắc chắn. Phạm vi nghiên cứu bao gồm các trường dữ liệu truyền thống và phi truyền thống như văn bản, hình ảnh, video. Mục tiêu chính là cải tiến các thuật toán tìm kiếm để xử lý hiệu quả các yêu cầu tìm kiếm mờ.

1.2. Hướng nghiên cứu của đề tài

Hướng nghiên cứu chính của luận văn bao gồm việc tìm hiểu lý thuyết mờ, cơ sở dữ liệu mờ, và các kỹ thuật tìm kiếm thông tin trong môi trường dữ liệu mờ. Luận văn cũng đề xuất các cải tiến trong thuật toán tìm kiếm để tối ưu hóa quá trình tìm kiếm thông tin.

II. Tổng quan về lý thuyết mờ và cơ sở dữ liệu mờ

Chương này cung cấp cái nhìn tổng quan về lý thuyết mờ và cơ sở dữ liệu mờ, bao gồm các khái niệm cơ bản như tập mờ, hàm liên thuộc, và các phép toán trên tập mờ. Lý thuyết mờ được giới thiệu bởi L. Zadeh, là nền tảng cho việc xử lý các thông tin không chắc chắn. Cơ sở dữ liệu mờ là sự mở rộng của cơ sở dữ liệu truyền thống, cho phép lưu trữ và xử lý các dữ liệu mờ.

2.1. Khái niệm tập mờ

Tập mờ là một khái niệm toán học được sử dụng để biểu diễn các thông tin không chắc chắn. Một tập mờ được xác định bởi hàm liên thuộc, ánh xạ từ không gian nền vào khoảng [0,1]. Hàm liên thuộc này biểu diễn mức độ thuộc của một phần tử vào tập mờ.

2.2. Các phép toán trên tập mờ

Các phép toán cơ bản trên tập mờ bao gồm phép hợp, phép giao, và phép bù. Các phép toán này được sử dụng để xử lý và phân tích dữ liệu mờ trong cơ sở dữ liệu mờ. Ví dụ, phép hợp của hai tập mờ được xác định bởi hàm liên thuộc tối đa của hai tập mờ đó.

III. Thuật toán tìm kiếm trong cơ sở dữ liệu mờ

Chương này tập trung vào việc phân tích và cải tiến các thuật toán tìm kiếm trong cơ sở dữ liệu mờ. Các thuật toán tìm kiếm truyền thống thường không hiệu quả khi xử lý các yêu cầu tìm kiếm mờ. Luận văn đề xuất các cải tiến trong thuật toán tìm kiếm để tối ưu hóa quá trình tìm kiếm thông tin trong môi trường dữ liệu mờ.

3.1. Số mờ tam giác

Số mờ tam giác là một dạng đặc biệt của số mờ, được sử dụng rộng rãi trong cơ sở dữ liệu mờ. Số mờ tam giác được biểu diễn bởi ba giá trị: cận dưới, giá trị trung tâm, và cận trên. Các phép toán trên số mờ tam giác được sử dụng để xử lý và so sánh các giá trị mờ trong cơ sở dữ liệu.

3.2. Cải tiến thuật toán tìm kiếm

Luận văn đề xuất các cải tiến trong thuật toán tìm kiếm để tối ưu hóa quá trình tìm kiếm thông tin trong cơ sở dữ liệu mờ. Các cải tiến này bao gồm việc sử dụng các phương pháp tìm kiếm mờ, như phương pháp N-gram và phương pháp kiểm tra chính tả, để tăng độ chính xác và hiệu quả của quá trình tìm kiếm.

IV. Cài đặt và đánh giá thuật toán

Chương này trình bày quá trình cài đặt và đánh giá các thuật toán tìm kiếm được đề xuất trong luận văn. Các thuật toán được cài đặt và thử nghiệm trên một cơ sở dữ liệu mờ quản lý các chương trình truyền hình. Kết quả thử nghiệm cho thấy các thuật toán đề xuất có hiệu quả cao hơn so với các thuật toán truyền thống.

4.1. Thiết kế mô hình bài toán tìm kiếm

Luận văn thiết kế một mô hình bài toán tìm kiếm trong cơ sở dữ liệu mờ quản lý các chương trình truyền hình. Mô hình này bao gồm các bước chính như phân tích nhu cầu tìm kiếm, thiết kế cơ sở dữ liệu, và cài đặt thuật toán tìm kiếm.

4.2. Đánh giá hiệu năng thuật toán

Các thuật toán tìm kiếm được đề xuất trong luận văn được đánh giá dựa trên các tiêu chí như độ chính xác, thời gian tìm kiếm, và khả năng xử lý các yêu cầu tìm kiếm mờ. Kết quả đánh giá cho thấy các thuật toán đề xuất có hiệu quả cao hơn so với các thuật toán truyền thống.

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 DỤNG 1. Tổng quan về lý thuyết mờ [5] L. Zadeh là người sáng lập ra lý thuyết tập mờ với hàng loạt bài báo mở đường cho sự phát triển và ứng dụng của lý thuyết này, khởi đầu là bài báo “Fuzzy Sets” trên Tạp chí 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ượng về ngữ nghĩa của thông tin mờ, không chắc chắn như trẻ, nhanh, cao thấp, xinh đẹp., ông đã tìm ra cách biểu diễn nó bằng một khái niệm toán học, được gọi là tập mờ, như là 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ờ A đượ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 cặp (x, µ A (x)) trong đó x ∈ X và µ A (x) là ánh xạ: µ A : X → [0,1] Ánh xạ µ A được gọi là hàm liên thuộc (hàm phụ thuộc hay hàm thuộc) của tập mờ 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ờ A trên không gian nền X là giá trị ℎ = sup 𝜇𝐴 (𝑥)chỉ giá trị nhỏ nhất trong các giá trị chặn trên của hàm µ A (x). Miền xác định của tập mờ A trên không gian nền X được ký hiệu bởi S là tập con của X thoả mãn: S = suppµ A (x) = {x ∈ X / µ A (x) > 0} Định nghĩa 1.

Miền tin cậy của tập mờ tập mờ A trên không gian nền X được ký hiệu bởi T là tập con của X thoả mãn: T = {x ∈ X / µ A (x) = 1} Định nghĩa 1. Miền biên của tập mờ tập mờ A trên không gian nền X được ký hiệu bởi U là tập con của X thoả mãn: U = {x ∈ X / 0 < µ A (x) < 1} 6 Hình 1.1: Biểu diễn các miền của một tập mờ Định nghĩa 1. Tập cắ t α (α ∈ [0,1]) của tập mờ A trên không gian nền X được ký hiệu bởi Aα là tập con của X thỏa mãn Aα = {x / µ A (x) ≥ α} và được gọi là tập cắ t mạnh α và ký hiệu là Aα+ nếu Aα+ = {x / µ A (x) > α} Định nghĩa 1. Tập mức α, hay là tập nhát cắt - α của tập mờ tập mờ A trên không gian nền X ký hiệu bởi Λ(A) là tập các tập con của X thỏa mãn: Λ(A) = {x / µ A (x) = α} với α ∈ [0,1] Định nghĩa 1.

Tập mờ A trên không gian nền X tuyến tính được gọi là tập mờ lồi nếu Aα là tập lồi ∀𝛼 ∈ [0,1]. Lực lượng của tập mờ A trên không gian nền X được biểu diễn như sau: 𝑁(𝐴, 𝜇𝐴 (𝑥)) = ∑ 𝜇𝐴 (𝑥) 𝑛=1 1. Các phép toán trên tập mờ a) Phép hợp hai tập mờ: Định nghĩa 1.8: Hợp của hai tập mờ A  B là một tập mờ được xác định trong không gian nền X và có hàm liên thuộc µ A  B (x) thỏa mãn các tiên đề: + Chỉ phụ thuộc vào µ A (x) và µ B (x) + Nếu µ B (x) = 0 với ∀x thì µ A  B (x) = µ A (x) + Có tính giao hoán µ A  B (x) = µ B  A (x) + Có tính kết hợp µ (A  B)  C (x) = µ A  (B  C) (x) + Có tính không giảm (đồng biến). Nếu A1 ⊆ A2 thì A1  B ⊆ A2  B: 7 µ A1 (x) ≤ µ A2 (x) ⇒ µ A1  B (x) ≤ µ A2  B (x) b) Phép giao hai tập mờ: Định nghĩa 1.9: Giao của hai tập mờ A và B là một tập mờ A  B xác định trong không gian nền X có hàm liên thuộc µ A  B (x) thỏa mãn các tiên đề: + Chỉ phụ thuộc vào µ A (x) và µ B (x) + Nếu µ B (x) = 0 với ∀x thì µ A  B (x) = µ A (x) + Có tính giao hoán µ A  B (x) = µ B  A (x) + Có tính kết hợp µ (A  B)  C (x) = µ A  (B  C) (x) + Có tính không giảm (đồng biến).

Phép bù của một tập mờ Định nghĩa 1.10: Tập bù của tập mờ A trên nền X là một tập mờ (𝐴, µ 𝐴 ) 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: + µ 𝐴 (x) chỉ phụ thuộc vào µ A (x) + Nếu µ A (x) = 0 thì µ 𝐴 (x) = 1 + Nếu µ A (x) = 1 thì µ 𝐴 (x) = 0 + Nếu A  B thì có µ 𝐴 (x) ≥ µ 𝐵 (x) Định nghĩa 1.11: Tập bù của tập mờ A trên nền X là một tập mờ (𝐴, µ 𝐴) xác định trên không gian nền X với hàm liên thuộc µ(µ A): [0,1] → [0,1] thỏa mãn các điều kiện sau: + µ(0) = 1 + µ(1) = 0 + µ A ≤ µ B ⇒µ(µ A) ≥ µ(µ B) Nếu hàm một biến µ(µ A) còn thỏa mãn thêm điều kiện + Liên tục và µ A < µ B ⇒µ(µ A) > µ(µ B) 8 Thì phép bù trên còn gọi là phép bù mờ chặt. Một phép bù mờ chặt được gọi là phép bù mờ mạnh nếu: ̿=𝑨 + µ(µ(µ A)) = µ A tức là 𝑨 Hình 1.2: Biểu diễn hàm liên thuộc của phép lấy phần bù d. Phép hiệu đối xứng: Mở rộng công thức cho phép hiệu đối xứng các tập kinh điển: A ∇ B = (A  B) \ (A  B) = (A  𝐵)  (𝐴  B) 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 dụng trực tiếp để xây dựng hàm liên thuộc hiệu đối xứng của các tập mờ (A, µ A (x)) và (B, µ B (x)) µ A ∇ B (x) = µ A (x) + µ B (x) – 2µ A (x)  µ B (x) e. Tích Đề các: Cho n tập mờ (xi, µ Ai (xi)), i=1,2,.n trên các không gian nền Xi. Tích Đề các của n tập mờ là một tập mờ: {(x1, x2,.xn)} trên không gian nền X1  X2 … Xn có hàm liên thuộc được xác định như sau: µ X1  X2 .xn) = min {µ Xi (xi)} 𝑖=1,2,…𝑛 1. Các kiểu hàm thuộc a.

Tam giác (Triangular): Định nghĩa bởi các cận dưới a, cận trên b và giá trị m, a < m < b. Chúng 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 𝑥 ≤ 𝑏 hoặc 𝑥 ≥ 𝑏 𝑥−𝑎 nếu 𝑎 < 𝑥 < 𝑚 𝜇𝐴 (𝑥) = 𝑚 − 𝑎 𝑏−𝑥 nếu 𝑚 < 𝑥 < 𝑏 𝑏−𝑚 {1 nếu 𝑥 = 𝑚 Hình 1.3: Các tập mờ hình tam giác: a)Tổng quát và b) Đối xứng 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, dùng để biểu diễn các giá trị rõ.

𝑆𝐺(𝑥) = { 0 nếu 𝑥 ≠ 𝑚 1 nếu 𝑥 = 𝑚 Hình 1.4: Tập mờ Singleton c. Hàm L: Hàm này được định nghĩa bởi hai tham số a và b theo cách: 1 nếu 𝑥 ≤ 𝑎 𝑏−𝑥 𝐿(𝑥) = { nếu 𝑎 < 𝑥 < 𝑏 𝑏−𝑎 0 nếu 𝑥 ≥ 𝑏 Hình 1. Hàm 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: 0 nếu 𝑥 ≤ 𝑎 𝑥−𝑎 Γ(𝑥) = { nếu 𝑎 < 𝑥 < 𝑏 𝑏−𝑎 1 nếu 𝑥 ≥ 𝑏 Hình 1.6: Tập mờ Gamma tuyến tính e. Hàm hình thang: Được định nghĩa bởi bộ 4 giá trị a, b, c, d theo công thức sau: 0 nếu 𝑥 ≤ 𝑎 hoặc 𝑥 ≥ 𝑑 𝑥−𝑎 nếu 𝑎 < 𝑥 < 𝑏 𝑇(𝑥) = 𝑏 − 𝑎 𝑑−𝑥 nếu 𝑐 < 𝑥 < 𝑑 𝑑−𝑐 {1 nếu 𝑏 ≤ 𝑥 ≤ 𝑐 Hình 1.7: Tập mờ hình thang 1.

Các loại số mờ a.12: Tập mờ A = (x, µ A (x)) trong không gian nền số thực R được gọi là số thực mờ nếu thỏa mãn 3 điều kiện: - A là tập mờ chính tắc 11 - Aα là là các khoảng đóng với ∀α ∈ (0,1] - Tập S = suppµ A (x) = {x ∈ X / µ A (x) > 0} giới nội b. Số mờ hình chuông: Là một tập mờ có dạng [ a - α, a + β ] trong đó α ≥ 0, β ≥ 0 là các số thực với hàm liên thuộc: 𝑙(𝑥) khi 𝑎 − 𝛼 ≤ 𝑥 ≤ 𝑎 𝜇( 𝑎,𝛼,𝛽 ) (𝑥) = { 𝑟(𝑥) khi 𝑎 ≤ 𝑥 ≤ 𝑎 + 𝛽 0 khi (𝑥 < 𝑎 − 𝛼) Λ (𝑥 > 𝑎 + 𝛽) c. Số mờ dạng tam giác: Là một tập mờ có dạng [ a - α, a, a + β ] trong đó α ≥ 0, β ≥ 0 là các số thực với hàm liên thuộc: 𝑥−𝑎 +1 khi 𝑎 − 𝛼 ≤ 𝑥 ≤ 𝑎 𝛼 𝜇( 𝑎,𝛼,𝛽 ) (𝑥) = 𝑥 − 𝑎 + 1 khi 𝑎 ≤ 𝑥 ≤ 𝑎 + 𝛽 𝛽 { 0 khi 𝑥 < 𝑎 − 𝛼 và 𝑥 > 𝑎 + 𝛽 d. Số mờ dạng hình thang: Là một tập mờ có dạng [ a - α, a, b, b + β ] trong đó α ≥ 0, β ≥ 0 là các số thực với hàm liên thuộc: 1 khi 𝑥 ≤ 𝑎 ≤ 𝑏 𝑥−𝑎 +1 khi 𝑎 − 𝛼 ≤ 𝑥 ≤ 𝑎 𝛼 𝜇( 𝑎,𝛼,𝛽 ) (𝑥) = 𝑏 − 𝑥 +1 khi 𝑏 ≤ 𝑥 ≤ 𝑏 + 𝛽 𝛽 { 0 khi (𝑥 < 𝑎 − 𝛼) hoặc (𝑥 > 𝑏 + 𝛽) e.

Số mờ dạng khoảng: Là tập mờ có dạng (a, ε) trong đó ε ≥ 0 là các số thực với hàm liên thuộc: 𝑥−𝑎 +1 khi 𝑎 − 𝜀 ≤ 𝑥 ≤ 𝑎 𝜀 𝜇( 𝑎,𝜀) (𝑥) = 𝑎 − 𝑥 +1 khi 𝑎 ≤ 𝑥 ≤ 𝑎 + 𝜀 𝜀 { 0 khi 𝑥 − 𝑎 − 𝜀 hoặc 𝑥 > 𝑎 + 𝜀 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 nhu cầu lưu trữ và xử lý dữ liệu của con người trong một thời gian dài. Tuy nhiên, 12 mô hình này vẫn tồn tại nhiều hạn chế chưa giải quyết được.