Luận văn Khảo sát ứng dụng của tập thô trong lựa chọn và rút gọn đặc trưng cho bài toán nhận dạng
Luận văn
Khảo sát ứng dụng của tập
thô trong lựa chọn và rút
gọn đặc trưng cho bài toán
nhận dạng
Mục Lục
Danh Sách Các Hình......................................................................................................5
Danh Sách Các Bảng......................................................................................................7
Lời Mở Đầu.....................................................................................................................8
Chương 1 .......................................................................................................................10
Lý Thuyết Tập Thô......................................................................................................10
1.1. Giới thiệu............................................................................................................10
1.2. Hệ thông tin........................................................................................................11
1.3. Quan hệ bất khả phân biệt ...............................................................................13
1.3.1. Sự dư thừa thông tin..................................................................................13
1.3.2. Quan hệ tương đương - Lớp tương đương..............................................13
1.3.3. Thuật toán xác định lớp tương đương.....................................................15
1.4. Xấp xỉ tập hợp...................................................................................................16
1.5. Sự không chắc chắn và hàm thuộc..................................................................25
1.6. Sự phụ thuộc giữa các tập thuộc tính.............................................................27
1.7. Rút gọn thuộc tính............................................................................................28
1.7.1. Khái niệm ...................................................................................................28
1.7.2. Ma trận phân biệt và hàm phân biệt .......................................................30
1.8. Một số thuật toán hiệu quả..............................................................................36
1.8.1. Lớp tương đương.......................................................................................36
1.8.2. Xấp xỉ trên, xấp xỉ dưới.............................................................................37
1.8.3. Vùng dương................................................................................................38
1.8.4. Rút gọn thuộc tính .....................................................................................38
1.8.4.1. Chiến lược Johnson.............................................................................39
1.8.4.2. Chiến lược ngẫu nhiên........................................................................40
1.8.4.3. Loại bỏ thuộc tính thừa trong một rút gọn.......................................41
================================ 1 ================================
Chương 2 .......................................................................................................................42
Bài Toán Nhận Dạng Mặt Người................................................................................42
2.1. Giới thiệu...........................................................................................................42
2.2. Các nghiên cứu trước đây................................................................................45
2.3. Mô hình nhận dạng mặt người tiêu biểu........................................................48
2.3.1. Mô hình.......................................................................................................48
2.3.2. Rút trích đặc trưng....................................................................................49
2.3.3. Nhận dạng mẫu..........................................................................................50
2.4. Một số khó khăn trong nhận dạng mặt người...............................................51
2.5. Phương pháp nhận dạng mặt người bằng mặt riêng....................................54
2.5.1. Mô tả phương pháp ...................................................................................55
2.5.2. Vấn đề tìm các mặt riêng ..........................................................................57
2.5.3. Sử dụng mặt riêng để nhận dạng .............................................................60
2.5.4. Tóm tắt phương pháp nhận dạng bằng mặt riêng .................................62
2.6. Ứng dụng các thuật toán lượng hoá vector trong quá trình phân lớp........63
2.6.1. Giới thiệu ....................................................................................................63
2.6.2. Một số thuật toán lượng hoá vector.........................................................64
2.6.2.1. Thuật toán LVQ1................................................................................64
2.6.2.2. Thuật toán OLVQ1.............................................................................66
2.6.3. Vấn đề khởi tạo vector tham chiếu ..........................................................67
Chương 3 .......................................................................................................................70
Ứng Dụng Tập Thô Vào ..............................................................................................70
Bài Toán Nhận Dạng Mặt Người................................................................................70
3.1. Giới thiệu...........................................................................................................70
3.2.1. Phương pháp chung...................................................................................71
3.2.2. Kết hợp heuristic và lý thuyết tập thô .....................................................71
3.2.2.1. Mô tả heuristic.....................................................................................71
================================ 2 ================================
3.2.2.2. Thuật toán............................................................................................72
3.2.2.3. Ví dụ minh hoạ....................................................................................73
3.3. Mô hình thử nghiệm.........................................................................................77
3.3.1. Tập dữ liệu..................................................................................................77
3.3.2. Mô hình 1....................................................................................................78
3.3.3. Mô hình 2....................................................................................................80
3.3.4. Vấn đề lựa chọn số khoảng rời rạc...........................................................84
Chương 4 .......................................................................................................................86
Cài Đặt Chương Trình.................................................................................................86
Và Thử Nghiệm ............................................................................................................86
4.1. Chương trình cài đặt........................................................................................86
4.1.1. Ngôn ngữ và môi trường ...........................................................................86
4.1.2. Tổ chức thư mục mã nguồn ......................................................................86
4.1.3. Một số lớp quan trọng...............................................................................86
1. Lớp bảng quyết định .................................................................................86
2. Các lớp thực hiện rút trích đặc trưng......................................................87
3. Lớp rời rạc hoá ..........................................................................................88
4. Lớp thuật toán tập thô ..............................................................................88
5. Các lớp rút gọn thuộc tính........................................................................88
6. Lớp mạng lượng hoá vector (LVQ) .........................................................90
7. Lớp thuật toán phân loại người láng giềng gần nhất.............................90
4.2. Tổ chức dữ liệu thử nghiệm.............................................................................90
4.3. Hướng dẫn và minh hoạ sử dụng chương trình ............................................91
4.3.1. Màn hình chính..........................................................................................91
4.3.2. Nhập tập ảnh huấn luyện..........................................................................92
4.3.3. Chọn thuật toán rút gọn thuộc tính .........................................................94
4.3.4. Quá trình huấn luyện ................................................................................94
================================ 3 ================================
4.3.5. Quá trình phân lớp....................................................................................96
4.3.6. Xem thông tin.............................................................................................97
4.4. Một số kết quả...................................................................................................98
4.4.1. Thư mục Face_10_24_20...........................................................................98
4.4.2. Thư mục Face_15_24_20...........................................................................99
4.4.3. Thư mục Face_20_24_20.........................................................................100
4.4.4. Thư mục Face_25_24_20.........................................................................101
4.5. Nhận xét kết quả.............................................................................................102
Chương 5 .....................................................................................................................104
Tự Đánh Giá Và Hướng Phát ...................................................................................104
Triển Đề Nghị .............................................................................................................104
5.1. Tự đánh giá .....................................................................................................104
5.2. Hướng phát triển đề nghị...............................................................................105
Tài Liệu Tham Khảo..................................................................................................106
================================ 4 ================================
Danh Sách Các Hình
Hình 1- 1 : Xấp xỉ tập đối tượng trong Bảng 1- 2 bằng các thuộc tính điều kiện Age và
LEMS. Mỗi vùng được thể hiện kèm theo tập các lớp tương đương tương ứng. ..19
Hình 1- 2 : Ma trận phân biệt của Bảng1-7....................................................................31
Hình 1- 3 : Ma trận phân biệt của hệ thông tin Bảng 1-7 xây........................................32
Hình 1- 4 : Ma trận phân biệt giữa các lớp tương đương của........................................33
Hình 1- 5 : Ma trận phân biệt tương đối ........................................................................33
Hình 1- 6 : Ma trận phân biệt Hình 1-2 sau khi chọn c .................................................34
Hình 2- 1 : Mô hình nhận dạng mặt người tiêu biểu.....................................................49
Hình 2- 2 : Ảnh với nền phức tạp với ...........................................................................51
Hình 2- 3 : Kết quả của một bộ dò tìm thẳng................................................................53
Hình 2- 4 : Vùng “đáng kể nhất” của gương mặt .........................................................53
Hình 2- 5 : Kết quả dò tìm trên ảnh có gương mặt được hoá trang ..............................54
Hình 2- 6 : Tập ảnh huấn luyện và ảnh trung bình .......................................................58
Hình 2- 7 : Các mặt riêng tương ứng với bảy giá trị riêng lớn nhất .............................60
Hình 2- 8 : Vector tham chiếu được di chuyển gần với vector dữ liệu hơn – trường
hợp hai vector này cùng lớp......................................................................66
Hình 2- 9 : Vector tham chiếu được đẩy ra xa vector dữ liệu hơn - trường hợp hai
vector này khác lớp ...................................................................................66
Hình 2- 10 : Vector tham chiếu OC khởi tạo không tốt nên sau khi cập nhật thành
OC1 thì càng xa vector dữ liệu OA hơn. ...............................................68
Hình 3- 1 : Ma trận phân biệt tương đối của hệ thông tin trong Bảng 3-1 ...................75
Hình 3- 2 : Phân chia tập dữ liệu huấn luyện và kiểm tra.............................................78
Hình 3- 3 : Ảnh của 10 người đầu tiên trong tập dữ liệu ORL.....................................78
================================ 5 ================================
Hình 3- 4 : Giai đoạn huấn luyện tạo tập vector tham chiếu ........................................79
Hình 3- 5 : Giai đoạn phân lớp tập ảnh kiểm tra...........................................................80
Hình 3- 6 : Giai đoạn huấn luyện tạo tập vector tham chiếu ........................................84
Hình 3- 7 : Giai đoạn phân lớp tập ảnh kiểm tra...........................................................84
================================ 6 ================================
Danh Sách Các Bảng
Bảng 1- 1 : Một hệ thông tin đơn giản...........................................................................11
Bảng 1- 2 : Một hệ quyết định với C = {Age, LEMS} và D = {Walk}.............................12
Bảng 1- 3 : Một bảng dữ liệu dư thừa thông tin.............................................................13
Bảng 1- 4 : Một hệ quyết định điều tra vấn đề da cháy nắng.........................................16
Bảng 1- 5 : Hệ thông tin về các thuộc tính của xe hơi...................................................20
Bảng 1- 6 : Bảng quyết định dùng minh hoạ hàm thuộc thô .........................................26
Bảng 1- 7 : Hệ thông tin dùng minh hoạ ma trận phân biệt.........................................31
Bảng 1- 8 : Một hệ thông tin..........................................................................................35
Bảng 3- 1 : Bảng quyết định cho ví dụ minh hoạ ..........................................................74
Bảng 3- 2 : Trạng thái ban đầu.......................................................................................75
Bảng 3- 3 : Trạng thái tiếp theo khi thêm a ..................................................................76
Bảng 3- 4 : Trạng thái tiếp theo khi thêm c ..................................................................76
Bảng 3- 5 : Trạng thái tiếp theo khi thêm d ..................................................................76
Bảng 4- 1 : Kết quả huấn luyện, kiểm tra tập Face_10_24_20......................................99
Bảng 4- 2 : Kết quả huấn luyện, kiểm tra tập Face_15_24_20....................................100
Bảng 4- 3 : Kết quả huấn luyện, kiểm tra tập Face_20_24_20....................................101
Bảng 4- 4 : K ết quả huấn luyện, kiểm tra tập Face_25_24_20...................................102
================================ 7 ================================
Lời Mở Đầu
-----oOo-----
Trong chuyên ngành Trí tuệ nhân tạo, Nhận dạng là một trong những lĩnh vực phát
triển sớm nhất và đã tìm được rất nhiều ứng dụng trong cuộc sống, chẳng hạn như dự
báo tiềm năng khoáng sản từ ảnh vệ tinh, nhận diện tội phạm qua vân tay, hay gần đây
người ta đưa ra khái niệm ngôi nhà thông minh với nhiều chức năng tự động hoá hoàn
toàn dựa vào khả năng nhận biết các đặc điểm của chủ nhân (như tiếng nói, dáng
người,…). Chính vì tầm quan trọng như vậy, lĩnh vực Nhận dạng đã thu hút được sự
quan tâm nghiên cứu của nhiều nhà khoa học. Rất nhiều thuật toán và mô hình đã được
đưa ra nhằm tăng tối đa hiệu suất của các giai đoạn trong một hệ thống nhận dạng.
Trong số đó, vấn đề lựa chọn và rút gọn đặc trưng liên quan trực tiếp đến độ chính xác
và tốc độ của hệ thống. Đây cũng là lý do của việc chọn đề tài :
“Khảo Sát Ứng Dụng Của Tập Thô Trong Lựa Chọn Và
Rút Gọn Đặc Trưng Cho Bài Toán
Nhận Dạng Mặt Người”
Việc lựa chọn lý thuyết Tập thô trong vấn đề nêu trên xuất phát từ những ứng dụng
rất thành công của nó trong thực tế như các hệ dự báo hay chuẩn đoán dựa trên luật.
Ngoài ra, ý tưởng gắn liền đối tượng với thông tin cũng như các khái niệm rút gọn
thuộc tính được đưa ra trong lý thuyết này hứa hẹn khả năng thành công cho hệ thống
nhận dạng kết hợp với lý thuyết Tập thô.
Cuối cùng, đối tượng nhận dạng được thử nghiệm trong luận văn này là khuôn mặt
bởi đây là đối tượng nghiên cứu khá lý thú với nhiều đặc điểm phong phú mang hàm
lượng thông tin cao như cảm xúc, tuổi tác,…và các hệ thống nhận dạng mặt người
đang đóng vai trò quan trọng trong bảo mật và an ninh.
Với cách đặt vấn đề như trên, luận văn được cấu trúc thành 5 chương như sau :
================================ 8 ================================
Chương 1 : Lý thuyết Tập thô.
Chương 2 : Bài toán nhận dạng mặt người.
Chương 3 : Ứng dụng Tập thô vào bài toán nhận dạng mặt người.
Chương 4 : Cài đặt chương trình và thử nghiệm.
Chương 5 : Tự đánh giá và hướng phát triển đề nghị.
================================ 9 ================================
Chương 1 – Lý thuyết Tập thô
Chương 1
Lý Thuyết Tập Thô
-----oOo-----
1.1. Giới thiệu
Lý thuyết tập thô (rough set theory) lần đầu tiên được đề xuất bởi Z. Pawlak và
nhanh chóng được xem như một công cụ xử lý các thông tin mơ hồ và không chắc
chắn. Phương pháp này đóng vai trò hết sức quan trọng trong lĩnh vực trí tuệ nhận tạo
và các ngành khoa học khác liên quan đến nhận thức, đặc biệt là lĩnh vực máy học, thu
nhận tri thức, phân tích quyết định, phát hiện và khám phá tri thức từ cơ sở dữ liệu, các
hệ chuyên gia, các hệ hỗ trợ quyết định, lập luận dựa trên quy nạp và nhận dạng [5].
Lý thuyết tập thô dựa trên giả thiết rằng để định nghĩa một tập hợp, chúng ta cần
phải có thông tin về mọi đối tượng trong tập vũ trụ. Ví dụ, nếu các đối tượng là những
bệnh nhân bị một bệnh nhất định thì các triệu chứng của bệnh tạo thành thông tin về
bệnh nhân. Như vậy tập thô có quan điểm hoàn toàn khác với quan điểm truyền thống
của tập hợp, trong đó mọi tập hợp đều được định nghĩa duy nhất bởi các phần tử của nó
mà không cần biết bất kỳ thông tin nào về các phần tử của tập hợp. Rõ ràng, có thể tồn
tại một số đối tượng giống nhau ở một số thông tin nào đó, và ta nói chúng có quan hệ
bất khả phân biệt với nhau. Đây chính là quan hệ mấu chốt và là điểm xuất phát của lý
thuyết tập thô : biên giới của tập thô là không rõ ràng, và để xác định nó chúng ta phải
đi xấp xỉ nó bằng các tập hợp khác nhằm mục đích cuối cùng là trả lời được (tất nhiên
càng chính xác càng tốt) rằng một đối tượng nào đó có thuộc tập hợp hay không. Lý
thuyết tập thô với cách tiếp cận như vậy đã được ứng dụng trong rất nhiều lĩnh vực của
đời sống xã hội.
================================ 10 ================================
Chương 1 – Lý thuyết Tập thô
Trong chương này chúng ta sẽ nghiên cứu các khái niệm và ý nghĩa cơ bản của lý
thuyết tập thô. Đây là những kiến thức quan trọng cho việc áp dụng tập thô vào bài
toán lựa chọn và rút gọn đặc trưng cho bài toán nhận dạng được đề cập trong chương 3.
1.2. Hệ thông tin
Một tập dữ liệu thể hiện dưới dạng bảng, trong đó mỗi dòng thể hiện cho một
trường hợp, một sự kiện, một bệnh nhân hay đơn giản là một đối tượng. Mỗi cột của
bảng thể hiện một thuộc tính (là một giá trị, một quan sát, một đặc điểm, …) được “đo
lường” cho từng đối tượng. Ngoài ra giá trị của thuộc tính cũng có thể được cung cấp
bởi chuyên gia hay bởi người sử dụng. Một bảng như vậy được gọi là một hệ thông tin
(information system) .
Một cách hình thức, hệ thông tin là một cặp A = (U, A) trong đó U là tập hữu hạn
không rỗng các đối tượng và được gọi là tập vũ trụ, A là tập hữu hạn không rỗng các
thuộc tính sao cho a :U → Va với mọi a ∈ A. Tập Va được gọi là tập giá trị của thuộc
tính a .
Ví dụ 1-1 : Bảng dữ liệu trong Bảng 1-1dưới đây cho ta hình ảnh về một hệ thông
tin với 7 đối tượng và 2 thuộc tính [1].
Age
LEMS
50
x1
x2
x3
x4
x5
x6
x7
16 – 30
16 – 30
31 – 45
31 – 45
46 – 60
16 – 30
46 – 60
0
1 – 25
1 – 25
26 – 49
26 – 49
26 – 49
Bảng 1- 1 : Một hệ thông tin đơn giản
================================ 11 ================================
Chương 1 – Lý thuyết Tập thô
Ta có thể dễ dàng nhận thấy rằng trong bảng trên, các cặp đối tượng x3 , x4 và x5 ,
x7 có giá trị bằng nhau tại cả hai thuộc tính. Khi đó ta nói rằng các đối tượng này
không phân biệt từng đôi đối với tập thuộc tính {Age, LEMS} .
□
Trong nhiều ứng dụng, tập vũ trụ được phân chia thành các tập đối tượng con bởi
một tập các thuộc tính phân biệt được gọi là tập thuộc tính quyết định. Nói cách khác
tập vũ trụ đã được phân lớp bởi thuộc tính quyết định. Hệ thông tin trong trường hợp
này được gọi là một hệ quyết định. Như vậy hệ quyết định là một hệ thông tin có dạng
A = (U,C ∪ D) trong đó A = C ∪ D , C và D lần lượt được gọi là tập thuộc tính điều
kiện và tập thuộc tính quyết định của hệ thông tin.
Ví dụ 1-2 : Bảng 1-2 dưới đây thể hiện một hệ quyết định, trong đó tập thuộc tính
điều kiện giống như trong Bảng 1-1 và một thuộc tính quyết định {Walk} được thêm
vào nhận hai giá trị kết xuất là Yes và No [1].
Age
Walk
Yes
No
LEMS
50
x1
x2
x3
x4
x5
x6
x7
16 – 30
16 – 30
31 – 45
31 – 45
46 – 60
16 – 30
46 – 60
0
No
1 – 25
1 – 25
26 – 49
26 – 49
26 – 49
Yes
No
Yes
No
Bảng 1- 2 : Một hệ quyết định với C = {Age, LEMS} và D = {Walk}
Một lần nữa ta thấy rằng, các cặp đối tượng x3 , x4 và x5 , x7 vẫn có giá trị như
nhau tại hai thuộc tính điều kiện, nhưng cặp thứ nhất {x3 , x4} thì có giá trị kết xuất khác
nhau (tức giá trị tại thuộc tính quyết định khác nhau), trong khi đó cặp thứ hai {x5 , x7 }
thì bằng nhau tại thuộc tính quyết định.
□
================================ 12 ================================
Chương 1 – Lý thuyết Tập thô
1.3. Quan hệ bất khả phân biệt
1.3.1. Sự dư thừa thông tin
Một hệ quyết định (hay một bảng quyết định) thể hiện tri thức về các đối tượng
trong thế giới thực. Tuy nhiên trong nhiều trường hợp bảng này có thể được tinh giảm
do tồn tại ít nhất hai khả năng dư thừa thông tin sau đây :
• Nhiều đối tượng giống nhau, hay không thể phân biệt với nhau lại được
thể hiện lặp lại nhiều lần.
• Một số thuộc tính có thể là dư thừa, theo nghĩa khi bỏ đi các thuộc tính
này thì thông tin do bảng quyết định cung cấp mà chúng ta quan tâm sẽ
không bị mất mát.
Ví dụ 1-3 : Trong bảng ở Bảng 1-3 dưới đây, nếu chúng ta chỉ quan tâm tới tập
thuộc tính {a,b,c} của các đối tượng thì ta sẽ có nhận xét : có thể bỏ đi thuộc tính c mà
thông tin về các đối tượng vẫn không đổi, chẳng hạn nếu ta có một đối tượng với hai
thuộc tính a , b nhận hai giá trị 0 , 1 thì có thể nói ngay rằng giá trị của nó tại thuộc
tính c là 1.
Bảng 1- 3 : Một bảng dữ liệu dư thừa thông tin
1.3.2. Quan hệ tương đương - Lớp tương đương
================================ 13 ================================
Chương 1 – Lý thuyết Tập thô
Chúng ta bắt đầu xem xét vấn đề dư thừa thông tin nói trên qua khái niệm quan hệ
tương đương. Một quan hệ hai ngôi R ⊆ XxX được gọi là quan hệ tương đương khi và
chỉ khi :
•
•
•
R là quan hệ phản xạ : xRx,∀x ∈ X .
R là quan hệ đối xứng : xRy ⇒ yRx,∀x, y ∈ X .
R là quan hệ bắc cầu : xRy và yRz ⇒ xRz , ∀x, y, z ∈ X .
Một quan hệ tương đương R sẽ phân hoạch tập đối tượng thành các lớp tương
đương, trong đó lớp tương đương của một đối tượng x là tập tất cả các đối tượng có
quan hệ R với x .
Tiếp theo, xét hệ thông tin A = (U, A) . Khi đó mỗi tập thuộc tính B ⊆ A đều tạo ra
tương ứng một quan hệ tương đương IND A :
IND A (B) = {(x, x') ∈U 2 | ∀a ∈ B,a(x) = a(x')}
IND A (B) được gọi là quan hệ B -bất khả phân biệt. Nếu (x, x')∈ IND A (B) thì các
đối tượng x và x' là không thể phân biệt được với nhau qua tập thuộc tính B . Với mọi
đối tượng x ∈U , lớp tương đương của x trong quan hệ IND A (B) được kí hiệu bởi
[x]B . Nếu không bị nhầm lẫn ta viết IND(B) thay cho IND A (B) . Cuối cùng, quan hệ
B -bất khả phân biệt phân hoạch tập đối tượng U thành các lớp tương đương mà ta kí
hiệu là U | IND(B) .
Ví dụ 1-4 : Tập thuộc tính {a,b,c} trong Bảng 1-3 phân tập đối tượng {1,2,...,9}
thành tập lớp tương đương sau :
U | IND(B) = {{1},{2,3,4},{5,6,7},{8,9}}
Ta thấy, chẳng hạn, do đối tượng 2 và đối tượng 3 thuộc cùng một lớp tương
đương nên chúng không phân biệt được với nhau qua tập thuộc tính{a,b,c}.
□
Ví dụ 1-5 : Trong ví dụ này chúng ta sẽ xem xét các quan hệ bất khả phân biệt được
định nghĩa trong Bảng 1-2.
================================ 14 ================================
Chương 1 – Lý thuyết Tập thô
Chẳng hạn, xét tại thuộc tính {LEMS}, các đối tượng x3 , x4 có cùng giá trị 1− 25
nên thuộc cùng lớp tương đương định bởi quan hệ IND({LEMS}) , hay chúng bất khả
phân biệt qua tập thuộc tính {LEMS}. Tương tự như vậy là ba đối tượng x5 , x6 và x7
cùng thuộc vào một lớp tương đương định bởi quan hệ IND({LEMS}) tương ứng với
giá trị thuộc tính LEMS bằng 26 − 49 .
Quan hệ IND định ra ba phân hoạch sau của tập các đối tượng trong vũ trụ :
IND({Age}) = {{x1, x2 , x6},{x3 , x4},{x5 , x7 }}
IND({LEMS}) = {{x1},{x2},{x3 , x4},{x5 , x6 , x7 }}
IND({Age, LEMS}) = {{x1},{x2},{x3 , x4},{x5 , x7 },{x6}}
□
1.3.3. Thuật toán xác định lớp tương đương
Vào :
Tập đối tượng O
Tập thuộc tính B
Ra :
Tập các lớp tương đương L
Thuật toán :
Bước 1: L = ∅
Bước 2: Nếu O = ∅
Thì : Thực hiện bước 5.
Ngược lại : Thực hiện bước 3.
Hết nếu
Bước 3: Xét x ∈ O
P = {x}
O = O \ {x}
Với mọi phần tử y ∈ O :
Nếu x và y không thể phân biệt được qua tập thuộc tính B
================================ 15 ================================
Chương 1 – Lý thuyết Tập thô
Thì : P = P ∪ {y}
O = O \ {y}
Hết nếu
Hết với mọi
L = L ∪ {P}
Bước 4: Thực hiện bước 2.
Bước 5: Kết thúc.
1.4. Xấp xỉ tập hợp
Như trên đã nói, một quan hệ tương đương cho ta một sự phân hoạch các đối tượng
của tập vũ trụ. Các lớp tương đương này có thể được sử dụng để tạo nên các tập con
của tập vũ trụ. Các tập con này thường chứa các đối tượng có cùng giá trị tại tập các
thuộc tính quyết định. Trong trường hợp này ta nói rằng các khái niệm, hay tập các giá
trị tại tập các thuộc tính quyết định, có thể được mô tả một cách rõ ràng thông qua tập
các giá trị tại tập các thuộc tính điều kiện. Để làm rõ ý tưởng quan trọng này ta xem ví
dụ dưới đây.
Ví dụ 1-6 : Xét hệ quyết định điều tra vấn đề da cháy nắng sau đây
Trọng
lượng
Nhẹ
Dùng
thuốc
Có
STT
Kết quả
1
2
3
4
Không cháy nắng
Không cháy nắng
Cháy nắng
Nhẹ
Có
Nặng
Không
Không
Trung bình
Không cháy nắng
Bảng 1- 4 : Một hệ quyết định điều tra vấn đề da cháy nắng
Trong hệ quyết định trên, thuộc tính Kết quả là thuộc tính quyết định và hai thuộc
tính giữa là thuộc tính điều kiện. Tập thuộc tính điều kiện C = {Trọng lượng, Dùng
thuốc} phân hoạch tập các đối tượng thành các lớp tương đương :
================================ 16 ================================
Chương 1 – Lý thuyết Tập thô
U | IND(C) = {{1,2},{3},{4}}
Nhận xét rằng tất cả các đối tượng thuộc cùng một lớp tương đương đều có cùng
giá trị tại thuộc tính quyết định. Do đó ta có thể mô tả thuộc tính quyết định như sau :
Kết quả sẽ là không cháy nắng nếu và chỉ nếu
trọng lượng là nhẹ và có dùng thuốc hoặc
trọng lượng trung bình và không dùng thuốc.
Kết quả sẽ là cháy nắng nếu và chỉ nếu
trọng lượng là nặng và không dùng thuốc.
Ta nói hai khái niệm Cháy nắng và Không cháy nắng trong thuộc tính Kết quả có
thể được định nghĩa rõ ràng qua 2 thuộc tính Trọng lượng và Dùng thuốc. Tuy vậy
không phải lúc nào cũng có thể định nghĩa một khái niệm nào đó một cách rõ ràng như
vậy. Chẳng hạn với bảng quyết định trong Bảng 1-2, khái niệm Walk không thể định
nghĩa rõ ràng qua 2 thuộc tính điều kiện Age và LEMS : hai đối tượng x3 và x4 thuộc
cùng một lớp tương đương tạo bởi 2 thuộc tính điều kiện nhưng lại có giá trị khác
nhau tại thuộc tính Walk, vì vậy nếu một đối tượng nào đó có
(Age, LEMS) = (31− 45,1− 25) thì ta vẫn không thể biết chắc chắn giá trị của nó tại thuộc
tính Walk (Yes hay No ?), nói cách khác ta sẽ không thể có một luật như sau : “Walk là
Yes nếu Age là 31− 45 và LEMS là 1− 25 ”. Và đây chính là nơi mà khái niệm tập thô
được sử dụng! .
Mặc dù không thể mô tả khái niệm Walk một cách rõ ràng nhưng căn cứ vào tập
thuộc tính {Age, LEMS} ta vẫn có thể chỉ ra được chắc chắn một số đối tượng có Walk
là Yes , một số đối tượng có Walk là No , còn lại là các đối tượng thuộc về biên giới
của 2 giá trị Yes và No , cụ thể :
• Nếu đối tượng nào có giá trị tại tập thuộc tính {Age, LEMS} thuộc tập
{{16 – 30, 50}, {16 – 30, 26 – 49}} thì nó có Walk là Yes .
================================ 17 ================================
Chương 1 – Lý thuyết Tập thô
• Nếu đối tượng nào có giá trị tại tập thuộc tính {Age, LEMS} thuộc tập
{{16 – 30, 0}, {46 – 60, 26 – 49}} thì nó có Walk là No .
• Nếu đối tượng nào có giá trị tại tập thuộc tính {Age, LEMS} thuộc tập
{{31 – 45, 1 – 25}} thì nó có Walk là Yes hoặc No . Những đối tượng
này, như nói ở trên thuộc về biên giới của 2 giá trị Yes và No .
Những khái niệm trên được thể hiện một cách hình thức như sau.
Cho hệ thông tin A = (U, A) , tập thuộc tính B ⊆ A, tập đối tượng X ⊆ U . Chúng ta
có thể xấp xỉ tập hợp X bằng cách chỉ sử dụng các thuộc tính trong B từ việc xây
dựng các tập hợp B -xấp xỉ dưới và B -xấp xỉ trên được định nghĩa như sau :
•
•
B -xấp xỉ dưới của tập X : BX = {x |[x]B ⊆ X}
B -xấp xỉ trên của tập X : BX = {x |[x]B ∩ X ≠ ∅}
Tập hợp BX là tập các đối tượng trong U mà sử dụng các thuộc tính trong B ta có
thể biết chắc chắn được chúng là các phần tử của X .
Tập hợp BX là tập các đối tượng trong U mà sử dụng các thuộc tính trong B ta chỉ
có thể nói rằng chúng có thể là các phần tử của X .
Tập hợp BNB (X ) = BX \ BX được gọi là B -biên của tập X và chứa những đối
tượng mà sử dụng các thuộc tính của B ta không thể xác định được chúng có thuộc tập
X hay không.
Tập hợp U \ BX được gọi là B -ngoài của tập X , gồm những đối tượng mà sử dụng
tập thuộc tính B ta biết chắc chắn chúng không thuộc tập X .
Một tập hợp được gọi là thô nếu đường biên của nó là không rỗng, ngược lại ta nói
tập này là rõ. Lưu ý rằng do khái niệm biên của một tập đối tượng gắn liền với một tập
thuộc tính nào đó nên khái niệm thô hay rõ ở đây cũng gắn liền với tập thuộc tính đó.
Trong đa số trường hợp, người ta luôn muốn hình thành các định nghĩa của các lớp
quyết định từ các thuộc tính điều kiện.
Ví dụ 1-7 :
================================ 18 ================================
Chương 1 – Lý thuyết Tập thô
Xét Bảng 1-2 ở trên với tập đối tượng W = {x |Walk(x) = Yes} = {x1, x4 , x6} và tập
thuộc tính B = {Age, LEMS}. Khi đó ta nhận được các vùng xấp xỉ sau đây của W
thông qua B :
BW = {x1, x6} , BW = {x1, x3 , x4 , x6}
BNB (W) = {x3 , x4} , U \ BW = {x2 , x5 , x7 }
Hình 1- 1 : Xấp xỉ tập đối tượng trong Bảng 1- 2 bằng các thuộc tính điều kiện Age và
LEMS. Mỗi vùng được thể hiện kèm theo tập các lớp tương đương tương ứng.
□
Ví dụ 1-8 : Ta xét một ví dụ khác với bảng giá trị về thuộc tính của xe hơi như sau :
Đối
Model Cylinder
Door
Power
Weight
Mileage
tượng
1
2
3
4
5
6
7
8
USA
USA
USA
USA
USA
USA
USA
USA
6
6
4
4
4
6
4
4
2
4
2
2
2
4
2
2
High
Medium
Medium
Medium
High
Medium
Medium
Medium
Medium
Medium
Medium
Medium
Medium
Medium
Medium
High
Medium Medium
High
Medium
Light
Medium
High
High
================================ 19 ================================
Chương 1 – Lý thuyết Tập thô
9
Japan
Japan
Japan
Japan
Japan
USA
4
4
4
4
4
4
2
2
2
2
2
2
Low
Medium
High
Light
High
High
High
High
High
High
10
11
12
13
14
Medium
Medium
Medium
Medium
Medium
Low
Medium
Medium
Bảng 1- 5 : Hệ thông tin về các thuộc tính của xe hơi
Ta có tập vũ trụ U = {1,2,...,14}. Giả sử chọn tập thuộc tính
B ={Cylinder, Power,Weight} và chọn thuộc tính quyết định là D = Mileage. Như vậy
thuộc tính quyết định gồm 2 khái niệm DMedium ="Mileage = Medium" và
DHigh ="Mileage = High" .
DMedium = {1,2,3,4,5,6,7}
DHigh = {8,9,10,11,12,13,14}
Các lớp tương đương ứng với quan hệ IND(B) là : E1 = {1,6}, E2 = {2},
E3 = {3,4,10,13,14}, E4 = {5,7,11}, E5 = {8}, E6 = {9} và E7 = {12}.
Xấp xỉ trên và xấp xỉ dưới của DMedium và DHigh là :
BDMedium = {E1, E2} = {1,6,2}
BDMedium = {E1, E2 , E3 , E4} = {1,6,2,3,4,10,13,14,5,7,11}
BDHigh = {E5 , E6 , E7 } = {8,9,12}
BDHigh = {E3 , E4 , E5 , E6 , E7 } = {3,4,10,13,14,5,7,11,8,9,12}
□
Một số tính chất của các tập hợp xấp xỉ
1. B(X ) ⊆ X ⊆ B(X )
2. B(∅) = B(∅) = ∅, B(U) = B(U) = U
================================ 20 ================================
Chương 1 – Lý thuyết Tập thô
3. B(X ∪Y) = B(X ) ∪ B(Y)
4. B(X ∩Y) = B(X ) ∩ B(Y)
5. Nếu X ⊆ Y thì B(X ) ⊆ B(Y), B(X ) ⊆ B(Y)
6. B(X ∪Y) ⊇ B(X ) ∪ B(Y)
7. B(X ∩Y) ⊆ B(X ) ∩ B(Y)
8. B(U \ X ) = U \ B(X )
9. B(U \ X ) = U \ B(X )
10. B(B(X )) = B(B(X )) = B(X )
11. B(B(X )) = B(B(X )) = B(X )
Ta chứng minh một số định lý điển hình.
3. Từ định nghĩa xấp xỉ trên ta có:
o ∈ B(X ∪Y) ⇔ ∃ P ∈U | IND(B): (o ∈ P, P ∩ (X ∪Y) ≠ ∅)
Mặt khác : P ∩ (X ∪Y) ≠ ∅ ⇔ P ∩ X ≠ ∅ hoặc P ∩Y ≠ ∅.
Do đó :
o ∈ B(X ∪Y) ⇔ (o ∈ P, P ∩ X ≠ ∅) hoặc (o ∈ P, P ∩Y ≠ ∅)
⇔ (o ∈ B(X )) hoặc (o ∈ B(Y))
⇔ o ∈ B(X ) ∪ B(Y)
⇒ (đpcm)
4. Chứng minh tương tự 3.
5. Chứng minh : (X ⊆ Y) ⇒ (B(X ) ⊆ B(Y))
Giả sử : X ⊆ Y
Xét o ∈ B(X ) . Khi đó : ∃P, P ∈U | IND(B) : o ∈ P, P ⊆ X .
Mà X ⊆ Y
nên P ⊆ Y . Nhưng theo định nghĩa tập xấp xỉ dưới :
B(Y) = {x | x ∈ P, P ∈U | IND(B), P ⊆ Y}
Nên : P ⊆ B(Y), từ đó : o ∈ B(Y)
================================ 21 ================================
Chương 1 – Lý thuyết Tập thô
Vậy : B(X ) ⊆ B(Y) . Tương tự ta chứng minh được B(X ) ⊆ B(Y)
6. Xét o ∈ B(X ) ∪ B(Y) ⇒ ∃P, P ∈U | IND(B),o ∈ P,(P ⊆ X ∨ P ⊆ Y)
⇒ P ⊆ X ∪Y . Mặt khác theo định nghĩa tập xấp xỉ dưới :
B(X ∪Y) = {x | x ∈ P, P ∈U | IND(B), P ⊆ X ∪Y}
Vậy : P ⊆ B(X ∪Y) , từ đó o ∈ B(X ∪Y)
⇒ đpcm.
7. Chứng minh tương tự 6
8. Ta có : B(U \ X ) = { P | P ∈U | IND(B), P ⊆ U \ X}
U
= U \{ P | P ∈U | IND(B),P ∩ X ≠ ∅}
U
= U \ B(X ) (đpcm).
9. Chứng minh tương tự hoặc có thể suy ra từ 8.
10. Từ định nghĩa của tập xấp xỉ dưới :
B(B(X )) = {x ∈U |[x]B ⊆ B(X )}
= {x ∈U |[x]B ⊆ X} , vì B(X ) ⊆ X
= B(X )
Tương tự : B(B(X )) = B(X ). Vậy ta có đpcm.
11. Chứng minh tương tự 10.
□
Dựa vào ý nghĩa của các xấp xỉ trên và xấp xỉ dưới, người ta định nghĩa bốn lớp cơ
bản của các tập thô, hay bốn hình thức của sự mơ hồ (vagueness) :
(a) X được gọi là B -định nghĩa được một cách thô (roughly B -definable) nếu
và chỉ nếu B(X ) ≠ ∅ và B(X ) ≠ U .
(b) X được gọi là B -không định nghĩa được một cách nội vi (internally B -
undefinable) nếu và chỉ nếu B(X ) = ∅ và B(X ) ≠ U .
(c) X được gọi là B -không định nghĩa được một cách ngoại vi (externally B -
undefinable) nếu và chỉ nếu B(X ) ≠ ∅ và B(X ) = U .
================================ 22 ================================
Chương 1 – Lý thuyết Tập thô
(d) X được gọi là B -không định nghĩa được một cách hoàn toàn (totally B -
undefinable) nếu và chỉ nếu B(X ) = ∅ và B(X ) = U .
Các khái niệm trên có thể diễn tả như sau :
•
•
•
•
X là B -định nghĩa được một cách thô nghĩa là : với sự giúp đỡ của tập
thuộc tính B ta có thể chỉ ra một số đối tượng của U thuộc về tập X và
một số đối tượng của U thuộc về U \ X .
X là B -không định nghĩa được một cách nội vi nghĩa là : sử dụng tập
thuộc tính B ta có thể chỉ ra một số đối tượng của U thuộc về U \ X ,
nhưng lại không thể chỉ ra được các đối tượng thuộc về X .
X là B -không định nghĩa được một cách ngoại vi nghĩa là : sử dụng tập
thuộc tính B ta có thể chỉ ra một số đối tượng của U thuộc về X , nhưng
không chỉ ra được các đối tượng thuộc về U \ X .
X là B -không định nghĩa được một cách hoàn toàn nghĩa là : sử dụng
tập thuộc tính B ta không thể chỉ ra bất kỳ đối tượng nào của U thuộc về
X hay thuộc về U \ X .
Cuối cùng, một tập thô có thể được định lượng bởi hệ số :
| B(X ) |
αB (X ) =
| B(X ) |
được gọi là độ chính xác của xấp xỉ, trong đó | X | chỉ số phần tử của tập X . Rõ
ràng 0 < αB (X ) < 1. Nếu αB (X ) = 1 thì X là rõ ( chính xác) đối với tập thuộc tính B .
Ngược lại, nếu αB (X ) < 1 thì X là thô (mơ hồ) đối với tập thuộc tính B .
Chúng ta kết thúc mục này với thuật toán xác định các xấp xỉ trên và xấp xỉ dưới
của một tập đối tượng theo một tập thuộc tính cho trước.
Thuật toán xác định xấp xỉ dưới
Vào :
Tập các đối tượng X
================================ 23 ================================
Chương 1 – Lý thuyết Tập thô
Tập các thuộc tính B
Ra :
Tập các đối tượng BX
Thuật toán :
Bước 1 : Khởi tạo BX = ∅ .
Xác định tập các phân hoạch P của tập vũ trụ U tạo bởi B.
Bước 2 : U1 = U
Nếu U1 ≠ ∅
Thì : Thực hiện bước 3.
Ngược lại : Thực hiện bước 5
Hết nếu
Bước 3 : Xét x ∈ U1
Tìm phân hoạch Pi ∈ P sao cho : x ∈ Pi .
Nếu Pi ⊆ X
Thì : BX = BX ∪ P
i
Hết nếu
U1 = U1 \ Pi .
Bước 4 : Thực hiện bước 2.
Bước 5 : Kết thúc
Thuật toán xác định xấp xỉ trên
Vào :
Tập các đối tượng X
Tập các thuộc tính B
Ra :
Tập các đối tượng BX
Thuật toán :
================================ 24 ================================
Chương 1 – Lý thuyết Tập thô
Bước 1 : Khởi tạo BX = ∅ .
Xác định tập các phân hoạch P của tập vũ trụ U tạo bởi B.
Bước 2 : X1 = X
Nếu X1 ≠ ∅
Thì : Thực hiện bước 3.
Ngược lại : Thực hiện bước 5
Hết nếu
Bước 3 : Xét x ∈ X1 .
Tìm phân hoạch Pi ∈ P sao cho : x ∈ Pi .
BX = BX ∪ P
i
Với mọi p ∈ Pi ∩ X1
X1 = X1 \ {p}
Hết với mọi
Bước 4 : Thực hiện bước 2.
Bước 5 : Kết thúc.
1.5. Sự không chắc chắn và hàm thuộc
Chúng ta đã biết BNB (X ) là tập các đối tượng trong tập vũ trụ U mà bằng cách sử
dụng tập thuộc tính B ta không thể xác định được chắc chắn chúng có thuộc tập đối
tượng X hay không. Do đó, sự không chắc chắn trong ngữ cảnh này gắn với một câu
hỏi về độ thuộc (membership) của các phần tử vào một tập hợp.
Trong lý thuyết tập hợp cổ điển, một phần tử hoặc là thuộc vào tập hợp hoặc không.
Như vậy hàm thuộc tương ứng là một hàm đặc trưng cho tập hợp, nghĩa là hàm sẽ nhận
giá trị 0 và 1 tương ứng.
Trong lý thuyết tập thô, hàm thuộc thô µXB là khái niệm dùng để đo mức độ thuộc
của đối tượng x trong tập vũ trụ U vào tập các đối tượng X ⊆U , và được tính bởi
================================ 25 ================================
Chương 1 – Lý thuyết Tập thô
mức độ giao nhau giữa tập X và lớp tương đương [x]B mà đối tượng x thuộc về. Một
cách hình thức, ta có :
µXB : U → [0,1]
[x]B ∩ X
x
a
[x]B
Một số tính chất của hàm thuộc thô
1. µXB (x) = 1 ⇔ x ∈ BX
2. µXB (x) = 0 ⇔ x ∈U − BX
3. 0 < µXB (x) < 1 ⇔ x ∈ BNB (X )
4. µXB (x) = µXB (y) nếu (x, y) ∈ IND(B)
5. µUB−X (x) = 1− µXB (x),∀x ∈U
6. µXB∪Y (x) = max(µXB (x),µYB (x)),∀x ∈U
7. µXB∩Y (x) = min(µXB (x),µYB (x)),∀x ∈U
Ví dụ 1-9 : Xét bảng quyết định dưới đây
A0
1
2
4
1
3
1
A
A2
A3
34
23
32
12
32
12
A4
1
x0
x1
x2
x3
x4
x5
A
A
B
B
B
B
2
3
3
2
1
4
Black
Blue
White
Black
Blue
Black
Bảng 1- 6 : Bảng quyết định dùng minh hoạ hàm thuộc thô
================================ 26 ================================
Chương 1 – Lý thuyết Tập thô
Xét tập thuộc tính B = {A0 , A } và tập đối tượng X = {x0 , x1, x3}. Lớp tương đương
1
tương ứng với quan hệ IND(B) là : E1 = {x0}, E2 = {x1}, E3 = {x2}, E4 = {x3 , x5},
E5 = {x4}.
Áp dụng định nghĩa hàm thuộc thô, ta thu được :
{x0}
µXB (x0 ) =
= 1.0
{x0}
{x3}
{x3 , x5}
µXB (x0 ) =
= 0.5
□
Từ định nghĩa hàm thuộc thô, hai khái niệm xấp xỉ trên và xấp xỉ dưới có thể được
1
xây dựng một cách tổng quát tương ứng với một độ rõ bất kỳ π ∈( ,1] như sau :
2
Bπ (X ) = {x | µ B (x) ≥ π}
X
Bπ (X ) = {x | µ B (x) > 1−π}
X
Lưu ý rằng hai khái niệm xấp xỉ trên và xấp xỉ dưới mà ta đã xây dựng trong phần
1.4 tương ứng với trường hợp độ rõ π = 1.0 .
1.6. Sự phụ thuộc giữa các tập thuộc tính
Một vấn đề quan trọng trong phân tích dữ liệu là khám phá sự phụ thuộc giữa các
thuộc tính. Một cách trực giác, một tập thuộc tính D được cho là phụ thuộc hoàn toàn
vào tập thuộc tính C , ký hiệu C ⇒ D , nếu tất cả các giá trị của các thuộc tính trong D
có thể được xác định duy nhất bởi các giá trị của các thuộc tính trong C . Nói cách
khác, D phụ thuộc hoàn toàn vào C nếu tồn tại một ánh xạ từ các giá trị của tập C tới
các giá trị của tập D . Khái niệm phụ thuộc thuộc tính được thể hiện dưới dạng hình
thức như sau.
Cho C và D là các tập con của tập thuộc tính A . Ta nói D phụ thuộc C với độ
phụ thuộc k (0 ≤ k ≤ 1) , kí hiệu C ⇒k D nếu :
================================ 27 ================================
Chương 1 – Lý thuyết Tập thô
| POSC (D) |
|U |
k = γ (C, D) =
trong đó
POSC (D) =
C(X )
U
X∈U|IND(D)
được gọi là C -vùng dương của D . Đây là tập các đối tượng của U mà bằng cách sử
dụng tập thuộc tính C ta có thể phân chúng một cách duy nhất vào các phân hoạch của
U theo tập thuộc tính D .
Dễ dàng thấy rằng :
CX
γ (C, D) =
∑
U
X∈U|IND(D)
Nếu k = 1 thì ta nói D phụ thuộc hoàn toàn vào C , ngược lại nếu k < 1 thì ta nói D
phụ thuộc một phần vào C với độ phụ thuộc k .
Có thể nhận thấy rằng nếu D phụ thuộc hoàn toàn vào C thì IND(C) ⊆ IND(D) .
Điều này có nghĩa là các phân hoạch tạo ra bởi tập thuộc tính C mịn hơn các phân
hoạch tạo ra bởi D .
1.7. Rút gọn thuộc tính
1.7.1. Khái niệm
Trong phần 1.3 chúng đã đề cập đến hai khả năng dư thừa trong một hệ thông tin,
đó là :
Các đối tượng giống nhau theo một tập thuộc tính đang quan tâm được lặp
lại nhiều lần.
Một số thuộc tính có thể được bỏ đi mà thông tin chúng ta đang quan tâm do
bảng quyết định cung cấp vẫn không bị mất mát.
Với trường hợp thứ nhất, khái niệm lớp tương đương hiển nhiên cho ta một tiếp cận
tự nhiên trong việc tinh giảm thông tin cần lưu trữ trong một hệ thông tin : chỉ cần sử
dụng một đối tượng để đại diện cho mỗi lớp tương đương. Trong phần này chúng ta
================================ 28 ================================
Chương 1 – Lý thuyết Tập thô
nghiên cứu tiếp cận cho loại dư thừa thông tin thứ hai, đó là chỉ giữ lại những thuộc
tính bảo toàn quan hệ bất khả phân biệt, và do đó bảo toàn khả năng xấp xỉ tập hợp
trong một hệ thông tin.
Xét hệ thông tin A = (U, A) và hai tập thuộc tính P,Q ⊆ A. Thuộc tính a ∈ P được
gọi là có thể bỏ được (dispensible) trong P nếu IND(P) = IND(P −{a}) , ngược lại ta
nói a là không thể bỏ được (indispensible) trong P . Rõ ràng thuộc tính có thể bỏ được
không làm tăng / giảm khả năng phân loại khi có / không có mặt thuộc tính đó trong
P . Tập tất cả các thuộc tính không thể bỏ được trong P được gọi là lõi (core) của P ,
ký hiệu CORE(P) . Lưu ý rằng lõi có thể là tập rỗng, và khi đó mọi tập con của P với
lực lượng bằng card(P) −1 đều giữ nguyên khả năng phân loại của P .
Khi loại ra khỏi P một số thuộc tính có thể bỏ được thì ta được một tập rút gọn của
P . Nói cách khác, rút gọn của một tập thuộc tính P là tập thuộc tính B ⊆ P giữ
nguyên khả năng phân loại của P , hay IND(B) = IND(P) . Dễ dàng thấy rằng, vì lõi của
P là tập các thuộc tính không thể bỏ được của P nên tất cả các rút gọn của P đều
chứa tập thuộc tính lõi.
Một rút gọn B của tập thuộc tính P được gọi là rút gọn hoàn toàn nếu với mọi tập
thuộc tính B' ⊂ B , B' không là rút gọn của P . Như vậy rút gọn hoàn toàn là tập thuộc
tính nhỏ nhất trong tất cả các rút gọn có thể có của P và được ký hiệu là RED(P) .
Tính chất : Tập thuộc tính lõi của P là giao của tất cả các rút gọn hoàn toàn của P ,
tức là :
CORE(P) = RED(P)
I
Để minh hoạ cho những khái niệm trên, ta xét ví dụ sau.
Ví dụ 1-10 : Xét Bảng 1-3 với tập thuộc tính P = {a,b,c}. Ta có :
U | IND(P) = {{1},{2,3,4},{5,6},{7,8,9}}
U | IND({a}) = {{1,2,3,4},{5,6,7,8,9}}
U | IND({b}) = {{1,5,6},{2,3,4,7,8,9}}
U | IND({c}) = {{1,2,3,4},{5,6,7,8,9}}
================================ 29 ================================
Tải về để xem bản đầy đủ
109 trang
21/05/2025
60
Bạn đang xem 30 trang mẫu của tài liệu "Luận văn Khảo sát ứng dụng của tập thô trong lựa chọn và rút gọn đặc trưng cho bài toán nhận dạng", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.
File đính kèm:
- luan_van_khao_sat_ung_dung_cua_tap_tho_trong_lua_chon_va_rut.pdf
