TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP HÀ NỘI
KHOA: CÔNG NGHỆ THÔNG TIN
**************

BÁO CÁO BÀI TẬP LỚN
MÔN: LÝ THUYẾT TẬP THÔ VÀ ỨNG DỤNG
ĐỀ TÀI: LÝ THUYẾT TẬP THÔ TRONG BÀI TOÁN TRÍCH CHỌN ĐẶC
TRƯNG
GIÁO VIÊN HƯỚNG DẪN: TH.S TRẦN THANH HUÂN
NHÓM 30- Lớp LT_KHMT2_K6
Thành viên trong nhóm:
1. Bùi Trung Hiếu (NT)
2. Trần Thị Hồng Thắm
3. Vũ Văn Chung

Hà Nội, ngày 26 tháng 02 năm 2014


ĐH CÔNG NGHIỆP HÀ NỘI

LÝ THUYẾT TẬP THÔ

MỤC LỤC

LỜI NÓI ĐẦU
Lý thuyết tập thô được Balan Zdzilaw Pawlak đề xuất ra vào đầu những
năm 80 của thế kỷ 19. Nó cung cấp một công cụ để phân tích, suy diễn dữ liệu
không chính xác để phát hiện ra mối quan hệ giữa các đối tượng và những
tiềm ẩn trong dữ liệu. Một hướng tiếp cận mới về tính không chắc chắn và
không chính xác của dữ liệu.
Lý thuyết tập thô ngày càng được áp dụng rộng rãi trong lĩnh vực trích

TỔNG QUAN VỀ LÝ THUYẾT TẬP THÔ
1.1 Giới thiệu lý thuyết tập thô
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.
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

NHÓM 30 LT_KHMT2_K6

3


ĐH CÔNG NGHIỆP HÀ NỘI

LÝ THUYẾT TẬP THÔ

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à

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].

Bảng 1: Một hệ thông tin đơn giản
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, x 4 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ệ

NHÓM 30 LT_KHMT2_K6

5


ĐH CÔNG NGHIỆP HÀ NỘI

LÝ THUYẾT TẬP THÔ

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}

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à 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 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
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 :

NHÓM 30 LT_KHMT2_K6

7


ĐH CÔNG NGHIỆP HÀ NỘI

LÝ THUYẾT TẬP THÔ

 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' )}

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, x 2, x6 }, {x3, x 4 }, {x5, x7 }}
IND ({LEMS}) = {{x1}, {x 2 }, {x3, x 4 }, {x5, x6, x7 }}
IND ({Age, LEMS}) = {{x1}, {x 2}, {x3, x 4 }, {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 B.
 Tập thuộc tính O.

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
Thì : P = P ∪ {y}
O = O \ {y}

NHÓM 30 LT_KHMT2_K6

9


ĐH CÔNG NGHIỆP HÀ NỘI

LÝ THUYẾT TẬP THÔ

{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 :
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 x 3 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ứ


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 đó.

NHÓM 30 LT_KHMT2_K6

12


ĐH CÔNG NGHIỆP HÀ NỘI

LÝ THUYẾT TẬP THÔ

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: 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 ={x 1, x6}, BW ={x1, x3, x4,
x6}


NHÓM 30 LT_KHMT2_K6

14


ĐH CÔNG NGHIỆP HÀ NỘI

LÝ THUYẾT TẬP THÔ

Ví dụ 1-9 : Xét bảng quyết định dưới đây:

Bảng 6 : Bảng quyết định dùng minh hoạ hàm thuộc thô
1.6 Sự phụ thuộc giữa các tập thộ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

NHÓM 30 LT_KHMT2_K6

15


ĐH CÔNG NGHIỆP HÀ NỘI

LÝ THUYẾT TẬP THÔ

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ụ


LÝ THUYẾT TẬP THÔ

 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 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

- có thể bỏ được (Q - dispensible) trong

P nếu POSP(Q) = POS{P− a}(Q), ngược lại là Q - không thể bỏ được (Qindispensible). Tập tất cả các thuộc tính Q - không thể bỏ được trong P được
gọi là Q - lõi tương đối (Q - relative core) của P hay Q - lõi (Q - core) của P
và được ký hiệu là COREQ (P).
Tập thuộc tính B ⊆ P được gọi là Q - rút gọn (Q - reduct) của P khi và
chỉ khi POSB (Q) = POSP (Q). Một tập Q - rút gọn B của P là Q - rút gọn

NHÓM 30 LT_KHMT2_K6

18


ĐH CÔNG NGHIỆP HÀ NỘI

LÝ THUYẾT TẬP THÔ

hoàn toàn nếu với mọi tập thuộc tính B'⊂ B, B ' không là Q - rút gọn của P.
Như vậy, Q - rút gọn hoàn toàn của P là tập thuộc tính nhỏ nhất trong tất cả
các Q - rút gọn của P và được ký hiệu là REDQ (P).
Tính chất: Tập thuộc tính Q - lõi của P là giao của tất cả các tập thuộc tính
Q - rút gọn tương đối của P, tức là :

COREQ(P) = ∩ REDQ(P).

CHƯƠNG II
BÀI TOÁN NHẬN DẠNG VÂN TAY
I.BÀI TOÁN NHẬN DẠNG VÂN TAY
1.1 Mục đích của việc nhận dạng vân tay
Trong thời đại hiện nay, khi tất cả các lĩnh vực trong xã hội đều được ứng

minh thư để xác định một cách nhanh nhất các đặc điểm, hồ sơ của một công
nhân đã được lưu trong cơ sở dữ liệu
+ Ngoài ra, hệ thống còn được hỗ trợ đắc lực cho việc quản lý và chấm công
tại các nhà máy, xí nghiệp, công ty, bảo vệ anh ninh cho mỗi gia đình hoặc cá
nhân…..
1.2 Cấu tạo, đặc điểm và các dạng vân tay
1.2.1 Cấu tạo vân tay
Dấu vân tay của mỗi cá nhân là độc nhất. Xác suất hai cá nhân – thậm chí
ngay cả anh em (Hoặc chị em) sinh đôi cùng trứng – có cùng một bộ dấu vân
tay là 1 trên 64 tỉ. Ngay cả các ngón trên cùng bàn tay cũng có vân khác nhau.
Dấu vân tay của mỗi người là không đỏi trong suốt cuộc đời. Người ta có thể
làm phẫu thuật thay da ngón tay, nhưng chỉ sau một thời gian dấu vân tay lại
được phục hồi như ban đầu. Vân tay chỉ là những đường có dạng dòng chảy
trên ngón tay người. Nó là một tham số sinh học bất biến theo tuổi tác đặc
trưng cho mỗi cá thể. Trên vân tay có các đường gợn và các luống

NHÓM 30 LT_KHMT2_K6

20


ĐH CÔNG NGHIỆP HÀ NỘI

LÝ THUYẾT TẬP THÔ

1.2.2 Các điểm đặc trưng của vân tay
Trên các ảnh vân tay có các đặc điểm đặc trưng ( là những đặc điểm mà vị
trí của nó không trùng lặp trên các vân tay khác nhau ) được phân thành hai
loại : Singularity và munutiae
Singularity : Trên vân tay có những vùng có cấu trúc khác thường so với

Dựa trên các thông tin về số lương tam phân điểm và vị trí của chúng là ta
hoàn toàn có thể xác định được loại của vân tay. Vì vậy vấn đề trích chọn tâm
và tâm phân điểm là khâu không thể thiếu được trong quá trình phân loại vân
tay.
Sau đây là một số phương pháp phân loại vân tay đã được nghiên cứu và
công bốm, muốn lưu ý tới phương pháp trích chọn tâm và tam phân điểm
được sử dụng.
Phương pháp phân loại Henry: Đây là phương pháp phân loại cổ điển và
phổ biến nhất, được sử dụng chủ yếu khi nhận dạng vân tay một cách thủ
công. Các tâm và tam phân điểm được nhận biết bằng mắt thường và vân tay
được phân loại dựa trên số lượng đường vân bị cắt bởi đường nối tâm và tam
phân điểm.
Các phương pháp phân loại dựa trên các đặc điểm tổng thể: Việc phân loại
vân tay trong phần lớn các hệ AFIS hiện nay đều dựa trên cá đặc điểm tổng

NHÓM 30 LT_KHMT2_K6

23


ĐH CÔNG NGHIỆP HÀ NỘI

LÝ THUYẾT TẬP THÔ

thể. Việc trích chọn tâm và tam phân điểm có thể được thực hiện trực tiếp trên
ảnh vân tay theo phương pháp xử lí ảnh theo từng điểm, nhưng nhược điểm
của phương pháp này là tốc độ xử lú chậm. Sau khi tách hướng các vùng, ta
nhận được một ảnh định hướng đặc trưng cho vân tay.
Phương pháp 2: Màu phân bố hướng chuẩn được định nghĩa là một mẫu hai
chiều mô tả phấn bố của các hướng lằn xung quanh một điểm đặc trưng.bằng


lý và tạo ra mẫu vân tay. Mẫu vân tay được chuyển đổi thành tín hiệu số và là
dữ liệu để nhận dạng người sử dụng chỉ trong chưa đến 2 giây.
Công nghệ truyền ánh sáng của hitachi cho phép ghi lại rõ nét sơ đò vân
nhờ đọ tương phản và khả năng tương thích với mọi loại da tay, kể cả da khô,
da dầu hay có vết bẩn, vết nhăn hay bị khiếm khuyết do toại hóa trên bề mặt
của các ngón tay. Lượng dữ liệu nhỏ đó là việc nhận dạng và tạo nên một hệ
thống nhỏ gọn, an toàn, thân thiện và nhanh nhất trên thế giới.
Hệ thống này có thể lưu trữ từ 6000-8000 ngón tay trong một máy và mỗi
người có thể nhận dạng bởi 1 trong 5 ngón tay khác nhau đã được đăng ký
trước đó. Ưu điểm vượt trội của hệ thống này là chỉ tương tác với cơ thể sống
nên việc bắt trước, giả mạo hay ăn cắp dữ liệu là điều hoàn bất khả thi.
FVB ra đời vào hồi đầu năm 2006, đã nhanh chóng thành công tại thị trường
Nhật Bản, Singapor, Trung Quốc ...

 Nhận diện dấu vân tay (finger indentification)
Dấu vân tay sẽ được đưa vào để đối chiếu với database chứa các vân tay để
truy ra các đặc điểm muốn truy xuất.
Việc đó sánh ảnh vân tay cần nhận dạng chỉ cần được tiến hành trên các vân
tay (có trong cơ sở dữ liệu) thuộc loại đã được xác định nhờ quá trình phân
loại. Đây là giai đoạn quyết định xem 2 ảnh vân tay có hoàn toàn giống nhau
hay không và đưa ra kết quả nhận dạng, tức là ảnh vân tay cần nhận. Dạng
tương ứng với vân tay của cá thể nào đã được lưu trữ trong cơ sở dữ liệu.
1.4 Hai phương pháp nhận dạng dấu vân tay
 Dựa vào các đặc tính cụ thể của dấu vân tay như điểm cuối, điểm rẽ
nhánh của các vân trên tay.
 So sánh toàn bộ đặc tính của dấu vân tay.

NHÓM 30 LT_KHMT2_K6