Xem mẫu
- Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XIV về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR), TP. HCM, ngày 23-24/12/2021
DOI: 10.15625/vap.2021.0082
VỀ VẤN ĐỀ TÌM TẤT CẢ CÁC RÚT GỌN TRONG BẢNG
QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ
Vũ Đức Thi1, Nguyễn Long Giang2, Nguyễn Ngọc Cương3, Phạm Việt Anh4
Viện Công nghệ thông tin, Đại học Quốc gia Hà Nội
1
2
Viện Công nghệ thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt Nam
3
Cục An ninh mạng và Phòng chống tội phạm sử dụng công nghệ cao - Bộ Công an
4
Viện Công nghệ HaUI, Trường Đại học Công nghiệp Hà Nội
TÓM TẮT: Các vấn đề liên quan đến bài toán rút gọn thuộc tính là những vấn đề quan trọng trong lý thuyết tập thô [13].
Hiện nay nhiều nhà khoa học trên thế giới quan tâm và phát triển những vấn đề này. M.Kryszkiewics [12] đã đưa ra khái niệm quan
hệ tương đối (tolerance relation) để nghiên cứu những vấn đề về các bảng quyết định không đầy đủ. Trong bài báo này, chúng tôi
giải quyết bài toán tìm tất cả các rút gọn trong bảng quyết định không đầy đủ theo hướng tiếp cận cơ sở dữ liệu quan hệ. Chúng tôi
đề xuất thuật toán tìm tất cả các rút gọn của bảng quyết định không đầy đủ. Thuật toán này có độ phức tạp tồi nhất là hàm mũ. Tuy
nhiên, trong nhiều trường hợp với các dữ liệu khác nhau thì thuật toán có độ phức tạp thời gian là đa thức.
Từ khóa: Tập rút gọn, lí thuyết tập thô, quan hệ tương đối, bảng quyết định không đầy đủ.
I. MỞ ĐẦU
Rút gọn thuộc tính trong bảng quyết định là quá trình loại bỏ các thuộc tính dư thừa trong tập thuộc tính điều
kiện mà không ảnh hưởng đến việc phân lớp các đối tượng. Dựa vào tập rút gọn thu được, việc sinh luật và phân lớp
đạt hiệu quả cao nhất. Cho đến nay, có rất nhiều công trình nghiên cứu về các thuật toán rút gọn thuộc tính trong lý
thuyết tập thô. Tuy nhiên, các thuật toán này đều tìm được một tập rút gọn tốt nhất theo một tiêu chí đánh giá nào đó
với độ phức tạp đa thức (các thuật toán theo hướng tiếp cận heuristic) mà chưa giải quyết bài toán tìm tất cả các tập rút
gọn trong bảng quyết định không đầy đủ. Trong [7], các tác giả đã đưa ra một phương pháp tính các thuộc tính rút gọn
(thuộc tính tham gia ít nhât một rút gọn) trong bảng quyết định không đầy đủ. Đối với bảng rút gọn nhất quán đầy đủ,
với cách tiếp cận bằng mô hình dữ liệu quan hệ [15, 16], chúng tôi [10] đã đề xuất một thuật toán có thời gian tính đa
thức tìm tất cả các thuộc tính rút gọn. Với thuật toán này chúng ta có thể rút gọn các cột (các thuộc tính) trong bảng
quyết định. Trong [9], chúng tôi đã đề xuất một thuật toán đa thức rút gọn các dòng (các đối tượng) trong bảng quyết
định. Như vậy, với hai thuật toán hiệu quả này chúng ta có thể loại bỏ các các cột, các dòng dư thừa trên bảng quyết
định. Mặt khác, việc tìm tất cả các rút gọn trong bảng quyết định đầy đủ rất quan trọng. Trong [8], các tác giả đã đưa ra
phương pháp tìm tất cả các rút gọn trong một bảng quyết định nhất quá và đầy đủ. Các tác giả đã chứng minh bài toán
tìm tất cả các rút gọn trên bảng quyết định này có độ phức tạp hàm mũ theo số lượng thuộc tính. Có nghĩa là phải
chứng minh được: Tồn tại một thuật toán hàm mũ tìm tất cả các rút gọn này và chứng minh độ phức tạp của bài toán
này không nhỏ hơn hàm mũ.
Dù rằng, trên một bảng quyết định nhất quán đầy đủ việc tìm một rút gọn được thực hiện bằng một thuật toán đa
thức, nhưng việc tìm một rút gọn có lực lượng nhỏ nhất là không khả thi. Có nghĩa rằng cho đến nay, không tồn tại một
thuật toán đa thức thực hiện công việc này. Trong [11], vì tập các rút gọn trên một bảng quyết định nhất quán đầy đủ là
quan trọng, chúng tôi đã chứng minh tập các rút gọn này tương đương với hệ Sperner ( hệ này là một hệ tổ hợp trong
đó các phần tử của nó không chứa nhau). Có nghĩa rằng việc nghiên cứu về tập các rút gọn có thể đưa về việc nghiên
cứu hệ Sperner.
II. CÁC KHÁI NIỆM CƠ BẢN
Các khái niệm cơ bản trong lý thuyết tập thô
Trong phần này sẽ trình bày một số khái niệm cơ bản trong lý thuyết tập thô [9]. Bảng quyết định là một bộ tứ
𝐷𝑇 = (𝑈, 𝐶 ∪ 𝐷, 𝑉, 𝑓) trong đó 𝑈 = {𝑢1 , 𝑢2 , . . . , 𝑢𝑛 } là tập khác rỗng, hữu hạn các đối tượng; 𝐶 = {𝑐1 , 𝑐2 , . . . , 𝑐𝑚 } là tập
các thuộc tính điều kiện; 𝐷là tập các thuộc tính với C và D là hai tập rời nhau và 𝑉 = UVa , với Va là tập giá trị của
thuộc tính 𝑎 ∈ 𝐴 = 𝐶 𝑈 𝐷; 𝑓: 𝑈 × (𝐶 ∪ 𝐷) → 𝑉 là hàm thông tin, với ∀𝑎 ∈ 𝐶 ∪ 𝐷, 𝑢 ∈ 𝑈 hàm 𝑓 cho giá trị 𝑓(𝑢, 𝑎) ∈
𝑉𝑎 . Không mất tính chất tổng quát giả thiết 𝐷 chỉ gổm một thuộc tính quyết định 𝑑 duy nhất (trường hợp 𝐷 có nhiều
thuộc tính thì bằng một phép mã hóa có thể quy về một thuộc tính [8]). Do đó, từ nay về sau ta xét bảng quyết định
𝐷𝑇 = (𝑈, 𝐶 ∪ 𝑑, 𝑉, 𝑓), trong đó {𝑑} ∉ 𝐶.
Mỗi tập con 𝑃 ⊆ 𝐶 𝑈{𝑑} xác định một quan hệ không phân biệt được, gọi là quan hệ tương đương.
𝐼𝑁𝐷(𝑃) = {(𝑥, 𝑦) ∈ 𝑈 × 𝑈|∀𝑎 ∈ 𝑃, 𝑓(𝑥, 𝑎) = 𝑓(𝑦, 𝑎)}.
- 400 VỀ VẤN ĐỀ TÌM TẤT CẢ CÁC RÚT GỌN TRONG BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ
𝐼𝑁𝐷(𝑃) xác định một phân hoạch của 𝑈, ký hiệu là 𝑈/𝑃 = {𝑃1 , 𝑃2 , . . . , 𝑃𝑚 }. Một phần tử trong 𝑈/𝑃 gọi là một
lớp tương đương.
Với 𝐵 ⊆ 𝐶 và 𝑋 ⊆ 𝑈, 𝐵 − xấp xỉ trên của 𝑋 là tập 𝐵𝑋 = {𝑢 ∈ 𝑈|[𝑢]𝐵 ∩ 𝑋 ≠ ∅}, 𝐵 − xấp xỉ dưới của 𝑋 là tập
𝐵𝑋 = {𝑢 ∈ 𝑈|[𝑢]𝐵 ⊆ 𝑋}, 𝐵 − miền biên của 𝑋 là tập 𝐵𝑋\𝐵𝑋 và 𝐵 − miền dương của {𝑑} là tập 𝑃𝑂𝑆𝐵 ({𝑑}) =
∪𝑋∈𝑈/𝐷(𝐵𝑋). Bảng quyết định 𝐷𝑇 được gọi là nhất quán khi và chỉ khi 𝑃𝑂𝑆𝐶 ({𝑑}) = 𝑈, hay phụ thuộc hàm 𝐶 → 𝑑
đúng, ngược lại 𝐷𝑇 là không nhất quán. Trường hợp 𝐷𝑇 không nhất quán thì 𝑃𝑂𝑆𝐶 ({𝑑}) chính là tập con cực đại của
𝑈 sao cho phụ thuộc hàm 𝐶 → 𝑑 đúng.
Định nghĩa 2.1: Cho bảng quyết định 𝐷𝑇 = (𝑈, 𝐶 ∪ 𝑑, 𝑉, 𝑓). Nếu 𝐵 ⊆ 𝐶 thỏa mãn:
(1) 𝑃𝑂𝑆𝐵 ({𝑑}) = 𝑃𝑂𝑆𝐶 ({𝑑})
(2) ∀𝐵′ ⊂ 𝐵(𝑃𝑂𝑆𝐵′ ({𝑑}) ≠ 𝑃𝑂𝑆𝐶 ({𝑑}))
thì 𝐵 được gọi là một tập rút gọn của 𝐶
Trường hợp 𝐷𝑇 nhất quán, định nghĩa trên cho thấy 𝐵 là một tập rút gọn nếu 𝐵 thỏa mãn 𝐵 → 𝑑 và ∀𝐵′ ⊂ 𝐵, 𝐵′ ↛
{𝑑}, ký hiệu 𝑅𝑑 là tập tất cả các rút gọn của 𝐷𝑇.
Định nghĩa 2.2: Quan hệ r = {ℎ1 , … , ℎ𝑚 } là quan hệ trên R={a1,...,an}. Nếu ∀𝑎𝑖 ∈ 𝑅 có 𝒟𝑎𝑖 và ∗ ∈ 𝒟𝑎𝑖
ℎ𝑗 : R→ ∪ 𝒟𝑎𝑖 sao cho ℎ𝑗 (𝑎𝑖 ) ∈ 𝒟𝑎𝑖
Định nghĩa 2.3: Cho r là quan hệ trên R={a1,...,an}, A ⊆ R
Khi đó ta kí hiệu ℎ𝑖 ~ ℎ𝑗 (𝐴) nếu với mỗi a thuộc A : ℎ𝑖 (𝑎) = ℎ𝑗 (𝑎) hoặc ℎ𝑖 (𝑎) = ∗ hoặc ℎ𝑗 (𝑎) = ∗ .
Định nghĩa 2.4: Cho 𝑟 = { ℎ1 , … , ℎ𝑚 } trên R={a1,...,an}. Khi đó 𝐴, 𝐵 ⊆ 𝑅 và ta gọi 𝐴 xác định tương đối 𝐵 kí hiệu
𝑡
𝐴 → 𝐵 nếu:
(∀ ℎ𝑖 , ℎ𝑗 ∈ 𝑟) (nếu ℎ𝑖 ~ℎ𝑗 (𝐴) thì ℎ𝑖 ~ℎ𝑗 (𝐵))
𝑡
Đặt 𝑇𝑟 = { (𝐴, 𝐵): 𝐴, 𝐵 ⊆ 𝑅 𝑣à 𝐴 → 𝐵}
Dễ thấy: 1) (𝐴, 𝐴) ∈ 𝑇𝑟 ∀𝐴 ⊆ 𝑅
2) (𝐴, 𝐵) ∈ 𝑇𝑟 thì 𝐴 ⊆ 𝐶, 𝐷 ⊆ 𝐵 có (𝐶, 𝐷) ∈ 𝑇𝑟
3) (𝐴, 𝐵) ∈ 𝑇𝑟 , (𝐵, 𝐶) ∈ 𝑇𝑟 ⟹ (𝐴, 𝐶) ∈ 𝑇𝑟
𝑡
Đặt 𝐴+ = {𝑎 ∈ 𝑅: 𝐴 → {𝑎}}
Định nghĩa 2.5: Bảng quyết định không đầy đủ 𝐷𝑆 = 〈𝑈, 𝐶 ∪ 𝑑, 𝑣, 𝑓〉 với ∗∉ 𝒟 α (có nghĩa cột giá trị của thuộc tính
quyết định 𝑑 không chứa ∗). 𝐶 là tập các thuộc tính điều kiện. 𝐷𝑆 là bảng quyết định không đầy đủ là nhất quán nếu
𝑡
𝐶 → {𝑑}
Có thể thấy nếu DS không nhất quán ta có thể kiểm tra bằng một thuật toán thời gian đa thức các phần tử của U
để loại bỏ các phần tử không làm cho DS là nhất quán. Sau khi loại bỏ chúng ta có tập U’ thì DS = < U’, C U d, V, f>
là nhất quán.
Định nghĩa 2.6: 𝐷𝑆 = 〈𝑈, 𝐶 ∪ 𝑑, 𝑣, 𝑓〉 là bảng quyết định không đầy đủ nhất quán, 𝐵 là tập rút gọn 𝐷𝑆 nếu:
𝑡 𝑡
𝐵 ⊆ 𝐶: 𝐵 → {𝑑} và ∀𝐵’ ⊊ 𝐵 thì 𝐵’ ↛ {𝑑} (có nghĩa B’ là tập con thực sự của B thì B’ không xác định tương
đối với d)
Đặt PRED(C) = {𝐵 là các tập rút gọn của 𝐷𝑆}
Định nghĩa 2.7: Giả sử 𝑅 = {𝑎1 , … , 𝑎𝑛 } và 𝒦 = {𝐴1 , … , 𝐴𝑚 } là hệ Sperner trên R nếu:
𝐴𝑖 ⊈ 𝐴𝑗 ∀ 𝑖, 𝑗
Định nghĩa 2.8: 𝒦 = {𝐴1 , … , 𝐴𝑚 } là hệ Sperner trên R.
Đặt 𝒦 −1 = {𝐵 ⊊ 𝑅: (𝐴 ∈ 𝒦 ⟹ 𝐴 ⊈ 𝐵 và 𝐵 ⊊ 𝐶 thì ∃𝐴 ∈ 𝒦: 𝐴 ⊆ 𝐶}
Nhận xét 2.1: Giả sử 𝐷𝑆 = 〈𝑈, 𝐶 ∪ 𝑑, 𝑣, 𝑓〉 là bảng quyết định nhất quán không đầy đủ. Đặt 𝑟 = 𝑈 = {𝑢1 , … , 𝑢𝑚 },
𝑅 = 𝐶 ∪ 𝑑.
- Vũ Đức Thi, Nguyễn Long Giang, Nguyễn Ngọc Cương, Phạm Việt Anh 401
𝑡 𝑡
Có thể thấy 𝑃𝑅𝐸𝐷(𝐶) = 𝒦𝑑𝑡 = {𝐴 ⊆ 𝐶: 𝐴 → {𝑑} và ∄𝐵: 𝐵 → {𝑑} 𝑣à 𝐵 ⊊ 𝐴 }
và 𝑃𝑅𝐸𝐷(𝐶) là hệ Sperner.
Nhận xét 2.2: Giả sử 𝐷𝑆 = 〈𝑈, 𝐶 ∪ 𝑑, 𝑣, 𝑓〉 là bảng quyết định nhất quán không đầy đủ. Đặt 𝑟 = 𝑈 = {𝑢1 , … , 𝑢𝑛 }, 𝑅 =
𝐶 ∪ 𝑑.
1. Từ r ta tính tập bằng nhau:
𝜀𝑟 = { 𝐸𝑖𝑗 ∶ 1 ≤ i ≤ j ≤ 𝑚 } với 𝐸𝑖𝑗 = { 𝑎 ∈ 𝑅: a(𝑢𝑖 ) = 𝑎(𝑢𝑗 ) hoặc 𝑎(𝑢𝑖 ) = ∗ hoặc 𝑎(𝑢𝑗 ) = ∗}
2. Từ 𝜀𝑅 đặt 𝑀𝑑 = {𝐴 ∈ 𝜀𝑟 : 𝐴 ≠ 𝑅, 𝑑 ∉ 𝐴 và ∄𝐵 ∈ 𝜀𝑟 : 𝑑 ∉ 𝐵 và 𝐴 ⊊ 𝐵}
III. MỘT SỐ THUẬT TOÁN CƠ BẢN TRONG CƠ SỞ DŨ LIỆU QUAN HỆ
A. Thuật toán tìm tập phản khoá
Thuật toán 3.1. [14] Tìm tập phản khoá 𝐾 −1
Đầu vào: 𝐾 = {𝐵1 , … , 𝐵𝑛 } là hệ Sperner trên 𝑅.
Đầu ra: 𝐾 −1
Bước 1: Đặt 𝐾1 = {𝑅 − {𝑎}: 𝑎 ∈ 𝐵1 }. Hiển nhiên 𝐾1 = {𝐵1 }−1
Bước q+1: (𝑞 < 𝑚). Giả thiết rằng 𝐾𝑞 = 𝐹𝑞 ∪ �𝑋1 , … , 𝑋𝑡𝑞 �, ở đây 𝑋1 , … , 𝑋𝑡𝑞 chứa 𝐵𝑞+1 và 𝐹𝑞 =
�𝐴 ∈ 𝐾𝑞 : 𝐵𝑞+1 ⊄ 𝐴�. Đới với mỗi 𝑖(𝑖 = 1, … , 𝑡𝑞 ) ta tìm các phản khoá của 𝐵𝑞+1 trên 𝑋𝑖 tương tự như 𝐾1 . Ký pháp của
chúng là 𝐴1𝑖 , … , 𝐴𝑖𝑟𝑖 . Đặt:
𝐾𝑞+1 = 𝐹𝑞 ∪ �𝐴𝑖𝑝 : 𝐴 ∈ 𝐹𝑞 ⇒ 𝐴𝑖𝑝 ⊄ 𝐴, 1 ≤ 𝑖 ≤ 𝑡𝑞 , 1 ≤ 𝑝 ≤ 𝑟𝑖 �
Cuối cùng ta đặt 𝐾 −1 = 𝐾𝑚
Độ phức tạp thuật toán
Đặt 𝐼𝑞 (1 ≤ 𝑞 ≤ 𝑚 − 1) là số phẩn tử của 𝐾𝑞 trong thuật toán trên. Theo [14], độ phức tạp thời gian của thuật
𝑚−1
toán là 𝑂�|𝑅|2 ∑𝑞=1 𝑡𝑞 𝑢𝑞 � với 𝑢𝑞 = 𝐼𝑞 − 𝑡𝑞 nếu 𝐼𝑞 > 𝑡𝑞 và 𝑢𝑞 = 1 nếu 𝐼𝑞 = 𝑡𝑞 .
Nhận xét
1) Trong mỗi bước của thuật toán, 𝐾𝑞 là hệ số Sperner trên 𝑅. Theo [5], kích thước của hệ Sperner bất kỳ trên
[𝑛/2]
𝑅 không vượt quá 𝐶𝑛 ≈ 2𝑛+1/2 /�∏. 𝑛1/2 � với 𝑛 = |𝑅|. Do đó, độ phức tạp tồi nhất của thuật toán là hàm số mũ
theo 𝑛.
2) Trường hợp 𝐼𝑞 ≤ 𝐼𝑚 (𝑞 = 1, … , 𝑚 − 1), độ phức tạp của thuật toán không lớn hơn 𝑂(|𝑅|2 |𝐾||𝐾 −1 |2 ), khi
đó độ phức tạp thuật toán là đa thức theo |𝑅|, |𝐾| và |𝐾 −1 |. Nếu số lượng các phấn tử của 𝐾 là nhỏ thì thuật toán rất
hiệu quả, đòi hỏi thời gian đa thức theo |𝑅|.
B. Thuật toán tìm tập khoá tối thiểu từ tập các phản khoá
Thuật toán 3.2. [5] Tìm một khoá tối thiểu từ tập các phản khoá
Đầu vào: Cho 𝐾 là hệ Sperner đóng vai trò là tập phản khoá, 𝐶 = {𝑏1 , … , 𝑏𝑛 } ⊆ 𝑅 và 𝐻 là hệ Sperner đóng
vai trò tập khoá (𝐾 = 𝐻 −1 ) sao cho ∃𝐵 ∈ 𝐾: 𝐵 ⊊ 𝐶.
Đầu ra: 𝐷 ∈ 𝐻
Bước 1: Đặt 𝑇(0) = 𝐶;
Bước i+1: Đặt 𝑇(𝑖 + 1) = 𝑇(𝑖) − 𝑏𝑖+1 nếu ∀𝐵 ∈ 𝐾 không có 𝑇(𝑖 + 1) ⊂ 𝐵; trong trường hợp ngược lại đặt
𝑇(𝑖 + 1) = 𝑇(𝑖);
Cuối cùng ta đặt 𝐷 = 𝑇(𝑛).
Có thể thấy độ phức tạp thời gian tồi nhất của thuật toán trên là đa thức với n và / K/.
Thuật toán 3.3. [5] Tìm tập các khoá tối thiểu từ tập các phản khoá
Đầu vào: Cho 𝐾 = {𝐵1 , … , 𝐵𝑘 } là hệ Sperner trên 𝑅.
Đầu ra: 𝐻 mà 𝐻 −1 = 𝐾.
- 402 VỀ VẤN ĐỀ TÌM TẤT CẢ CÁC RÚT GỌN TRONG BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ
Bước 1: Bởi thuật toán 3.2 ta tính 𝐴1 , đặt 𝐾1 = 𝐴1 .
Bước i+1: Nếu có 𝐵 ∈ 𝐾𝑖 −1 sao cho 𝐵 ⊄ 𝐵𝑗 (∀𝑗: 1 ≤ 𝑗 ≤ 𝑘) thì bởi Thuật toán 3.2 ta tính 𝐴𝑖+1 , ở đây
𝐴𝑖+1 ∈ 𝐻, 𝐴𝑖+1 ⊆ 𝐵. Đặt 𝐾𝑖+1 = 𝐾𝑖 ∪ 𝐴𝑖+1 . Trong trường hợp ngược lại ta đặt 𝐻 = 𝐾𝑖 .
Độ phức tạp thuật toán 3.3
𝑚−1
Theo [5], độ phức tạp Thuật toán 3.3 là 𝑂 �|𝑅|�∑𝑞=1 �|𝐾|𝐼𝑞 + |𝑅|𝑡𝑞 𝑢𝑞 � + |𝐾|2 + |𝑅|��
với 𝐼𝑞 , 𝑡𝑞, , 𝑢𝑞 như trong Thuật toán 3.1. Do đó, độ phức tạp tồi nhất của Thuật toán 3.3 là hàm số mũ theo 𝑛 với 𝑛 là số
phần tử của 𝑅. Trường hợp 𝐼𝑞 ≤ |𝐾|(𝑞 = 1, … , 𝑚 − 1), độ phức tạp của Thuật toán 3.3 là 𝑂(|𝑅|2 |𝐾|2 |𝐻|), độ phức tạp
của đa thức theo |𝑅|, |𝐾| và |𝐻|. Nếu |𝐻| là đa thức theo |𝑅|, |𝐾| thì thuật toán hiệu quả. Nếu số lượng các phần tử của
𝐻 là nhỏ thì thuật toán rất hiệu quả.
IV. THUẬT TOÁN TÌM TẤT CẢ CÁC RÚT GỌN TRONG BẢNG QUYẾT ĐỊNH
Định lí 4.1: 𝑀𝑑 = (𝒦𝑑𝑡 )−1
Chứng minh:
∀𝐴 ∈ 𝑀𝑑 có thể thấy 𝐴 = 𝐴+ vì nếu 𝐴 ⊊ 𝐴+ thì có 𝑒 ∈ 𝐴+ và 𝑒 ∉ 𝐴. Vì 𝐴 là tập bằng nhau cực đại thì
𝑡
∃𝑖, 𝑗 (1 ≤ 𝑖 < 𝑗 ≤ 𝑚) để 𝐸𝑖𝑗 = 𝐴 và theo định nghĩa tập 𝐴+ , ta có 𝐴 → {𝑒} và phù hợp với định nghĩa tập 𝐸𝑖𝑗 thì
𝑡
𝑒 ∈ 𝐸𝑖𝑗 . Vì thế 𝐴 = 𝐴+ và 𝑑 ∉ 𝐴 nên 𝑑 ∉ 𝐴+ . Vậy 𝐴 ↛ {𝑑} (𝐴 không xác định tương đối 𝑒).
Nếu có 𝐵 mà 𝐴 ⊊ 𝐵, theo định nghĩa của tập 𝐴 nếu 𝑑 ∉ 𝐵 thì ∀𝑖, 𝑗 (1 ≤ 𝑖 < 𝑗 ≤ 𝑚) ta có ℎ𝑖 ~ℎ𝑗 (𝐵) không
𝑡
đúng. Do đó, theo định nghĩa của xác định tương đối, ta có 𝐵 → 𝑅. Trường hợp 𝑑 ∈ 𝐵 thì dễ thấy 𝑑 ∈ 𝐵+ . Như vậy, cả
𝑡
hai trường hợp ta có ∀𝐵: 𝐴 ⊊ 𝐵 ⇒𝐵+ → {𝑑}. Vậy theo định nghĩa của 𝒦𝑑𝑡 thì có 𝐶 ∈ 𝒦𝑑𝑡 để 𝐶 ⊆ 𝐵. Như vậy theo định
nghĩa của tập (𝒦𝑑𝑡 )−1 ta có 𝐴 ∈ (𝒦𝑑𝑡 )−1 . Ngược lại nếu 𝐴 ∈ (𝒦𝑑𝑡 )−1 thì 𝐴+ = 𝐴. Vì ngược lại nếu 𝐴 ⊊ 𝐴+ thì theo
𝑡 𝑡
định nghĩa của tập phản khóa ta có 𝐶 ∈ (𝒦𝑑𝑡 ) để 𝐶 ⊆ 𝐴+ , có nghĩa là 𝐴+ → {𝑑}, như vậy kéo theo 𝐴 → {𝑑}. Mà theo
𝑡
định nghĩa của (𝒦𝑑𝑡 )−1 thì 𝐴 không xác định tương đối {𝑑} (𝐴 ↛ {𝑑}). Như vậy 𝐴+ = 𝐴.
Theo định nghĩa của tập 𝑀𝑑 và tập (𝒦𝑑𝑡 )−1 (là tập hợp các tập lớn nhất không xác định 𝑑) có nghĩa là 𝐴 ∈ 𝑀𝑑 .
Vậy 𝑀𝑑 = (𝒦𝑑𝑡 )−1 .
Thuật toán 4.1: Thuật toán tìm tất cả các tập rút gọn trên bảng quyết định không đầy đủ
Giả sử 𝐷𝑆 = 〈𝑈, 𝐶 ∪ 𝑑, 𝑣, 𝑓〉 là bảng quyết định nhất quán không đầy đủ. Đặt 𝑟 = 𝑈 = {𝑢1 , … , 𝑢𝑛 }, 𝑅 = 𝐶 ∪ 𝑑.
1) Từ 𝑟 ta tính tập bằng nhau:
𝜀𝑟 = { 𝐸𝑖𝑗 ∶ 1 ≤ i ≤ j ≤ 𝑚 } với 𝐸𝑖𝑗 = { 𝑎 ∈ 𝑅: a(𝑢𝑖 ) = 𝑎(𝑢𝑗 ) hoặc 𝑎(𝑢𝑖 ) = ∗ hoặc 𝑎(𝑢𝑗 ) = ∗}
2) Từ 𝜀𝑅 đặt 𝑀𝑑 = {𝐴 ∈ 𝜀𝑟 : 𝐴 ≠ 𝑅, 𝑑 ∉ 𝐴 và ∄𝐵 ∈ 𝜀𝑟 : 𝑑 ∉ 𝐵 và 𝐴 ⊊ 𝐵}
3) Bởi Thuật toán 3.3 ta xây tập K từ Md ( K-1 = Md )
4) Đặt PRED (C) = K – {d}
Ví dụ 4.1: Giả sử 𝑆 = 〈𝑈, 𝐶 ∪ 𝑑, 𝑣, 𝑓〉, 𝑈 = {𝑢1 , 𝑢2 , . . . , 𝑢5 }, 𝐶 = {𝑎1 , 𝑎2 , 𝑎3 , 𝑎4 }
Bảng 1. Một ví dụ bảng quyết định không đầy đủ
𝑎1 𝑎2 𝑎3 𝑎4 d
𝑢1 1 1 ∗ ∗ 6
𝑢2 2 ∗ 5 2 7
𝑢3 2 2 4 1 6
𝑢4 3 1 4 1 7
𝑢5 3 1 4 * 7
Theo bước 1 và 2 của Thuật toán 4.1, cần thực hiện các bước sau:
1) Tính:
+ 𝐸12 = {𝑎2 , 𝑎3 , 𝑎4 } + 𝐸13 = {𝑎3 , 𝑎4 , 𝑑} + 𝐸14 = {𝑎2 , 𝑎3 , 𝑎4 } + 𝐸15 = {𝑎2 , 𝑎3 , 𝑎4 }
+ 𝐸23 = {𝑎1 , 𝑎2 } + 𝐸24 = {𝑎2 , 𝑑} + E25 = {a2, a4, d} + 𝐸34 = {𝑎3 , 𝑎4 }
- Vũ Đức Thi, Nguyễn Long Giang, Nguyễn Ngọc Cương, Phạm Việt Anh 403
+𝐸35 = {𝑎3 , 𝑎4 } + 𝐸45 = {𝑎1 , 𝑎2 , 𝑎3 , 𝑎4 , 𝑑}
2) Theo bước 2 Thuật toán 4.1 có 𝐴1 = {𝑎2 , 𝑎3 , 𝑎4 } và 𝐴2 = {𝑎1 , 𝑎2 } thỏa mãn điều kiện của Md.
Như vậy 𝑀𝑑 = {{𝑎2 , 𝑎3 , 𝑎4 }, {𝑎1 , 𝑎2 }}
Có thể thấy, trên cơ sở Thuật toán 3.3 từ Md chúng ta có:
PRED (C) = {{𝑎1 , 𝑎3 }, {𝑎1 , 𝑎4 }}
Độ phức tạp của thuật toán:
Dễ thấy, đô phức tạp thuật toán của Bước 1 và Bước 2 là đa thức theo kích thước của 𝑟. Do đó, độ phức tạp
của thuật toán là độ phức tạp của Thuật toán 3.3 tính tập khoá tối thiểu từ tập phản khoá tại Bước 3. Do đó độ phức tạp
của thuật toán là:
𝑚−1
𝑂 �|𝑅| � � �|𝑀𝑑 |𝐼𝑞 + |𝑅|𝐼𝑞 𝑢𝑞 � + |𝑀𝑑 |2 + |𝑅|��
𝑞=1
với 𝐼𝑞 , 𝑡𝑞, , 𝑢𝑞 như trong Thuật toán 3.1 và độ phức tạp thuật toán này trong trường hợp xấu nhất là hàm số mũ theo 𝑛
với 𝑛 là số phần tử của 𝑅. Trường hợp 𝐼𝑞 ≤ |𝑀𝑑 |(𝑞 = 1, … , 𝑚 − 1), độ phức tạp của thuật toán là 𝑂(|𝑅|2 |𝑀𝑑 |2 |𝐾𝑑𝑡 |),
độ phức tạp này là đa thức theo |𝑅|, |𝑀𝑑 | và |𝐾𝑑𝑡 |. Dễ thấy tại bước 2, |𝑀𝑑 | là đa thức theo kích thước của 𝑟, do đó nếu
|𝐾𝑑𝑡 | là đa thức theo |𝑅| thì độ phức tạp của thuật toán là đa thức theo kích thước của 𝑟. Nếu số lượng các phần tử của
|𝐾𝑑𝑡 | là nhỏ thì thuật toán rất hiệu quả.
Cho DS = 〈𝑈, 𝐶 ∪ 𝑑, 𝑣, 𝑓〉 là bảng quyết định không đầy đủ. Thuộc tính a của C được gọi là cốt lõi DS nếu a
tham gia trong tất các rút gọn của DS. Kí pháp CORE (DS) là tập tất cả các thuộc tính cốt lõi của DS. Có thể thấy rằng
CORE (DS) là tập giao của các tập rút gọn A của DS.
Từ Thuật toán 4.1 chúng ta có hệ quả sau:
Hệ quả 4.1: Cho 𝐷𝑆 = 〈𝑈, 𝐶 ∪ 𝑑, 𝑣, 𝑓〉 là bảng quyết định không đầy đủ thì tồn tại thuật toán tìm CORE (DS).
Chúng ta có thể thấy rằng trên cơ sở Thuật toán 3.2 và Định lí 4.1 chúng ta có hệ quả sau:
Hệ quả 4.2: Cho 𝐷𝑆 = 〈𝑈, 𝐶 ∪ 𝑑, 𝑣, 𝑓〉 là bảng quyết định không đầy đủ thì tồn tại thuật toán tìm một rút gọn
của DS. Thuật toán này có độ phức tạp thời gian là đa thức.
TÀI LIỆU THAM KHẢO
[1] J. Demetrovics, On the equivalence of candidate keys with Sperner systems, Acts Cybernetica 4, 247-252, 1979.
[2] J. Demetrovics, V. D. Thi, Algorithms for generating Armstrong relation and inferring functional dependencies in the relational
datamodel, Computer and Mathematics with Applications 26 (4) 43-55 (Great Britain).
[3] J. Demetrovics, V. D. Thi, antikeys and prime attributes, Ann. Univ. Scien. Budapest Sect. Comut. 8: 37-54, 1987.
[4] J. Demetrovics, V. D. Thi, Relations and minimal keys, Acta Cybernetica 8 (3): 297-285, 1998.
[5] J. Demetrovics, V. D. Thi, Some remarks on generating, Armstrong and inferring functional dependencies relation, Acta
Cybernetica 12: 167-180, 1995.
[6] J. Demetrovics, V. D. Thi, Some result about functional dependencies, Acta Cybernetica 8 (3): 273- 280, 1988.
[7] J. Demetrovics, N. L. Giang, V. D. Thi, An efficient algorithm for determining the set of all reductive attributes in incomplete
decision tables. Journal CIT, Bungary, 13 (4): 118-126, 2013.
[8] J. Demetrovics, N. L. Giang, V. D.Thi, “On finding all reducts of consistent decision tables”. Journal CIT, Bungary, 14 (4): 3-
10, 2014.
[9] J. Demetrovics, V. D.Thi, H. M. Quang, N. V. Anh, “A method to reduce the size of consistent decision tables”, Acta
Cybernetica, V. 23: 167-180, 2018.
[10] N. L. Giang, V. D. Thi, “Some problems concerning condition attributes and reducts in decision tables”. Proceeding of the 5th
National Symposium Fundamential and Applied Information Technology Research (FAIR), 142-152, 2011.
[11] N. L. Giang, J. Demetrovics, V. D. Thi, P. D. Khoa, “Some Properties Related to Reduct of Consistent Decision Systems”,
Journal of Cybernetics and Information Technologies, Bulgarian Academy of Sciences, V. 21(2): 3-9, 2021.
[12] M. Kryszkiewicz, Rough set approach to incomplete information systems, Information Science, 39-40, 1998.
[13] Z. Pawlak, Rough Sets - Theoritical Aspets of Reasoning about Data, Kluwer Academic Publishers, Dordrecht, 1991.
[14] V. D. Thi, Minimal keys and antikeys, Acta Cybernetica 7 (4): 361-371, 1986.
[15] V. D.Thi, N. L. Giang, “A method for extracting knowledge from decision tables in terms of functional dependencies”. Journal
CIT, Bungary, 13, 1, 73-82, 2013.
[16] V. D. Thi, N. L. Giang, “A method to construct decision table from relation scheme”, Cybernetics and Information
Technologies, Bulgarian Academy of Sciences, V.11 (3): 32-41, 2011.
- 404 VỀ VẤN ĐỀ TÌM TẤT CẢ CÁC RÚT GỌN TRONG BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ
ON THE PROBLEM FINDING ALL REDUCTS IN INCOMPLETE DECISION TABLE
Vu Duc Thi, Nguyen Long Giang, Nguyen Ngoc Cuong, Pham Viet Anh
ABSTRACT: Problems related to the attribute reduction are important in rough set theory [13]. Nowadays, scientists in the
world consider and develop these problems. M.Kryszkiewics [12] provided the tolerance relation to conduct research on issues
relating to incomplete decision tables. In this paper, we find all reducts in incomplete decision tables according to the relational
database approach. We propose the algorithm to find all reducts of incomplete decision tables. This algorithm has the time
complexity which is exponential. However, this algorithm has the time complexity which is polynomial in different cases of the
database.
nguon tai.lieu . vn
