ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Đinh Quang Thắng

MỘT SỐ ỨNG DỤNG
CỦA HẠT DỮ LIỆU
LUẬN VĂN THẠC SĨ


Mã số: 1.01.1
LUẬN VĂN THẠC SĨ

NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS.TS HOÀNG CHÍ THÀNH
Hà Nội - 2005
- 1 -
MỤC LỤC
MỞ ĐẦU 4
CHƢƠNG 1: TỔNG QUAN VỀ TÍNH TOÁN HẠT 7
1.1 Khái niệm về tính toán hạt 7
1.2 Tại sao chúng ta nghiên cứu tính toán hạt 8
1.3 Những vấn đề cơ bản của tính toán hạt 8
1.4 Một số mô hình tính toán hạt 9
1.4.1 Các tập mờ 9
1.4.2 Các tập thô 10
1.4.3. Một mô hình dựa trên lý thuyết tập hợp của tính toán hạt 11
1.4.3.1 Đại số luỹ thừa 11

3.2 Các tập thô và khai phá tri thức trong cơ sở dữ liệu 36
3.2.1 Làm sạch dữ liệu và tiền xử lý 36
3.2.1.1 Rút gọn dữ liệu 36
3.2.1.2 Quản lý giá trị không đúng 37
3.2.1.3 Lựa chọn và trích chọn đặc trƣng 37
3.2.2 Khai phá dữ liệu 40
3.3 Khai phá luật kết hợp 40
3.3.1 Các luật kết hợp 41
3.3.2 Thuật giải tuần tự Apriori 42
3.3.3 Các thuật giải song song và phân tán 43
3.3.3.1 Các kỹ thuật khai phá dữ liệu phân tán 43
3.3.3.1.1 Kỹ thuật sinh các tập ứng cử 43
3.3.3.1.2 Phép tỉa cục bộ các tập ứng cử 45
3.3.3.1.3 Phép tỉa toàn cục các tập ứng cử 48
3.3.3.1.4 Bầu kiểu kiểm phiếu 50
3.3.3.2 Thuật giải 1: Phân tán tính toán 51
3.3.3.3 Thuật giải 2: Phân tán dữ liệu 52
3.3.3.4 Thuật giải 3: Phân tán ứng cử viên 55
3.3.3.5 Sinh các luật song song 57
3.3.3.6 Thuật giải nhanh khai phá phân tán các luật kết hợp FDM 58
3.3.3.7 Sinh luật Apriori phân tán 61
3.4 Kết luận 64
CHƢƠNG 4: CHƢƠNG TRÌNH THỬ NGHIỆM 66
4.1 Thuật giải Apriori ……………………………………………………………… 66
4.2 Cấu trúc dữ liệu T-tree 66
4.3 Giới thiệu chƣơng trình 67
4.4 Kết quả thử nghiệm 73

- 3 -
4.4 Kết luận 74

sử dụng các hạt để giảm chi phí một cách đáng kể. Điều này mở ra một định hƣớng
của logic mờ: “Khai thác độ không chắc chắn và tính đúng bộ phận để có đƣợc khả
năng dễ kiểm soát, tính mạnh mẽ, chi phí thấp và phù hợp với thực tế hơn”. Những
nguyên tắc này hƣớng tới nhiều mô hình vật lý để giải quyết các bài toán thế giới thực:
thay cho việc tìm kiếm những lời giải tối ƣu, ta có thể tìm kiếm những lời giải xấp xỉ
tốt. Nhƣ vậy chỉ khi cần thiết chúng ta mới khảo sát bài toán tại một mức kết hạt mịn
hơn với nhiều thông tin chi tiết hơn.
Tính toán hạt cũng đƣợc nghiên cứu rộng rãi trong lý thuyết các tập thô. Nhƣ một
nền tảng cụ thể của tính toán hạt, mô hình tập thô cho phép chúng ta định nghĩa một
cách chính xác và phân tích nhiều khái niệm của tính toán hạt. Các kết quả nghiên cứu
mang lại một cách hiểu thấu đáo hơn về tính toán hạt.

- 5 -
Luận văn tập trung vào nghiên cứu tính toán hạt dựa trên lý thuyết các tập thô. Cụ
thể, luận văn có nội dung nhƣ sau sau:
Chƣơng 1: Tổng quan về tính toán hạt: Trong chƣơng này, trình bày những thuật
ngữ chung, các yếu tố và những vấn đề cơ bản của tính toán hạt và một số ứng dụng
của chúng. Luận văn trình bày cách xây dựng, cách hiểu và cách biểu diễn các hạt
cũng nhƣ các yếu tố cơ bản và các phép toán để tính loán và lập luận với các hạt. Phần
cuối của chƣơng giới thiệu khái quát ba mô hình đang tồn tại của tính toán hạt: mô
hình dựa trên các tập thông thƣờng, mô hình dựa trên lý thuyết các tập thô và mô hình
dựa trên lý thuyết các tập mờ.
Chƣơng 2: Bài toán quyết định và phƣơng pháp giải quyết dựa vào hạt dữ liệu:
Luận văn giới thiệu một cách tổng quát hai cách kết hạt của một tập, các định nghĩa về
các tập thô. Với các xấp xỉ tập thô, một tập tổng thể đƣợc phân thành ba vùng là POS,
NEG và vùng biên BND. Bài toán quyết định là làm thể nào để xác định đƣợc ba vùng
trên một cách hiệu quả. Một phƣơng pháp thƣờng hay đƣợc sử dụng để giải quyết bài
toán quyết định trên là sử dụng thủ tục quyết định của Bayes. Luận văn trình bày tóm
tắt thủ tục quyết định Bayes này và xây dựng một mô hình lý thuyết quyết định sử
dụng các hạt dữ liệu dựa trên lý thuyết các tập thô.

máy, cơ sở dữ liệu và một số lĩnh vực khác. Chủ đề về phƣơng pháp kết hạt thông tin
mờ đầu tiên đƣợc trình bày bởi Zadeh vào năm 1979 [6]. Các ứng dụng của tính toán
hạt đã đƣợc phát triển một cách nhanh chóng và nó đóng một vai trò quan trọng trong
sự phát triển của logic mờ, lý thuyết các tập thô và các ứng dụng của chúng [6].
Những khái niệm và các thành phần cơ bản của tính toán hạt trên thực tế đã phát
triển trong rất nhiều lĩnh vực, nhƣng đến nay chƣa có một định nghĩa tổng quát về tính
toán hạt [3] [5] [6]. Tuy vậy, thông qua các phƣơng pháp giải một số bài toán trong
thực tế, chúng ta vẫn có thể khái quát đƣợc các thành phần cơ bản của tính toán hạt [3,
7]. Do đó, chúng ta có thể nghiên cứu tính toán hạt dựa trên việc tập trung giải các bài
toán sử dụng các tính chất chung của các hạt, các quan sát kết hạt, các tính chất của hạt
và các hệ thống phân cấp của lớp các hạt. Khi đó, ta có thể coi tính toán hạt nhƣ là một
nghiên cứu về lý thuyết tổng quát để giải quyết bài toán dựa trên các mức khác nhau
về tính chất hạt [3, 6].
Những khái niệm dƣới đây của Zadeh có thể giúp chúng ta hiểu rõ hơn phạm vi ứng
dụng và lập luận với các hạt:
“Phƣơng pháp kết hạt của một đối tƣợng A hình thành một tập các hạt của A, với
mỗi hạt là một cụm của các điểm (các đối tƣợng) đƣợc ghép lại với nhau theo quan hệ
“không phân biệt đƣợc”, “quan hệ tƣơng tự”, “quan hệ xấp xỉ” hoặc “quan hệ có cùng
chức năng”” [3], (Zadel 1997).
“Lý thuyết về phƣơng pháp kết hạt thông tin mờ đƣợc xây dựng theo cách thức con
ngƣời kết hạt thông tin và lập luận với chúng” [3] (Zadeh, 1997).
“Lý thuyết về phƣơng pháp kết hạt thông tin mờ xây dựng trên bộ máy đang tồn tại
của phƣơng pháp kết hạt thông tin mờ trong logic mờ nhƣng mang nó tới một mức cao
hơn của tính tổng quát, thống nhất các nghiên cứu của nó và đề xuất các hƣớng nghiên
cứu mới” [3] (Zadeh, 1997).
“Tính toán hạt là một khái niệm của lý thuyết về phƣơng pháp kết hạt thông tin mờ,
lý thuyết tập thô và tính toán khoảng và là một phần trong toán học tính toán với các
hạt” [3] (Zadeh, 1997).
Có thể thấy rằng ý tƣởng chung nhất của tính toán hạt là sử dụng các nhóm, các lớp
hoặc cụm các phần tử đƣợc gọi là các hạt [3, 7]. Mặc dù đã có những ứng dụng cụ thể

tính chính xác cao và những phƣơng pháp tính toán không kết hạt.
1.3 Những vấn đề cơ bản của tính toán hạt
Những vấn đề cơ bản của tính toán hạt có thể đƣợc nghiên cứu theo hai khía cạnh:
phƣơng pháp xây dựng các hạt và phƣơng pháp tính toán với các hạt. Phƣơng pháp
xây dựng các hạt nghiên cứu sự hình thành các công thức, các phép biểu diễn và các
cách hiểu các hạt, phƣơng pháp tính toán với các hạt nghiên cứu các tiện ích sử dụng
các hạt trong giải quyết bài toán [3] [4] [6].

- 9 -
Cách hiểu các hạt trả lời cho câu hỏi tại sao hai đối tƣợng đƣợc đặt vào trong cùng
một hạt. Tổng quát, các phần tử trong một hạt đƣợc nhóm lại với nhau theo các quan
hệ không phân biệt đƣợc, quan hệ tƣơng tự hoặc quan hệ có cùng chức năng [1] [3]
[6]. Hơn nữa, các hạt thông tin phụ thuộc vào các tri thức sẵn có. Trong việc xây dựng
các hạt, cần thiết phải nghiên cứu các tiêu chuẩn để quyết định hai phần tử nào nên
đƣợc đặt trong cùng một hạt dựa trên các thông tin có đƣợc. Nói cách khác, cần thiết
phải xây dựng một cách hiểu ngữ nghĩa cho các quan hệ không phân biệt đƣợc, quan
hệ đồng dạng hoặc quan hệ có cùng chức năng. Cũng cần thiết phải xây dựng các cấu
trúc kết hạt của một tập tổng thể. Hình thành công thức và biểu diễn các hạt nghiên
cứu các vấn đề thuộc thuật toán của phƣơng pháp xây dựng các hạt. Chúng trả lời cho
câu hỏi đặt hai đối tƣợng vào trong cùng một hạt nhƣ thế nào. Các thuật giải cần đƣợc
phát triển để xây dựng các hạt một cách hiệu quả [1] [3] [6].
Để tính toán với các hạt, chúng ta cần phải hiểu đƣợc mối liên hệ giữa các hạt nhƣ
mối quan hệ gần gũi, mối quan hệ phụ thuộc, mối quan hệ kết hợp và định nghĩa và
cách hiểu các phép toán trên các hạt. Hay chúng ta cần thiết kế một hệ phƣơng pháp và
các công cụ cho tính toán hạt nhƣ các phép toán xấp xỉ, các lập luận và các suy luận
với chúng [1] [3] [4] [5] [6].
1.4 Một số mô hình tính toán hạt
Để hiểu rõ hơn về tính toán hạt, luận văn trình bầy một số mô hình cụ thể của tính
toán hạt. Đó là mô hình dựa trên lý thuyết tập mờ của Zadel, mô hình dựa trên lý
thuyết tập thô và mô hình dựa trên lý thuyết tập hợp thông thƣờng.

đƣợc biểu diễn bằng một đồ thị mờ. Ta có thể sử các luật nếu-thì mờ hoặc các đồ thị
mờ để tìm ra kết kết quả lập luận [6].
1.4.2 Các tập thô
Với các kết hạt của một tập tổng thể, chúng ta nghiên cứu các phần tử trong một hạt
là một khối thay cho việc quan sát chúng dƣới dạng các hạt cụ thể [6]. Khi hệ thống
chứa thông tin về các hạt chƣa đầy đủ, có nghĩa là chỉ có một số tập con của tập tổng
thể đƣợc mô tả một cách chính xác, các tập con còn lại có các phần tử là không phấn
biệt đƣợc. Lý thuyết các tập thô đƣợc sử dụng trong các trƣờng hợp xấp xỉ hạt thông
tin [1].
Gọi
E U U
là một quan hệ tƣơng đƣơng trên tập tổng thể U. Cặp
 
,apr U E

đƣợc gọi là một không gian xấp xỉ. Quan hệ tƣơng đƣơng E phân hoạch tập U thành
các tập con không giao nhau. Mỗi lớp tƣơng đƣơng có thể đƣợc quan sát nhƣ một hạt
chứa các phần tử không phân biệt đƣợc và nó cũng đƣợc coi nhƣ một hạt tƣơng đƣơng.
Một biểu diễn ngữ nghĩa cụ thể của các quan hệ tƣơng đƣơng đƣợc cung cấp dựa trên
các khái niệm của các bảng thông tin. Hai đối tƣợng là tƣơng đƣơng nếu chúng có các
giá trị chính xác giống nhau trong một tập các thuộc tính. Do đó một hạt tƣơng đƣơng
đƣợc mô tả bởi một ràng buộc tƣơng đƣơng [6].
Một tập
XU
có thể không là hợp của một số lớp tƣơng đƣơng. Điều đó nói lên
rằng ta không thể mô tả X một cách chính xác khi sử dụng các lớp tƣơng đƣơng của E.
Trong trƣờng hợp này ta có thể mô tả X bằng một cặp các xấp xỉ trên và xấp xỉ dƣới:
 
 
E

phân tích dữ liệu trong các bảng thông tin, chẳng hạn nhƣ thu gọn thuộc tính, phân tích
tính phụ thuộc và học các luật quyết định [6].

- 11 -
1.4.3. Một mô hình dựa trên lý thuyết tập hợp của tính toán hạt
Trong phần này, luận văn trình bày một hệ thống dựa trên lý thuyết tập hợp của tính
toán hạt. Mỗi hạt biểu diễn một khái niệm cụ thể và mỗi phần tử của hạt là một bản thể
của khái niệm đó. Các hạt có thể đƣợc xây dựng trên các bảng thông tin, nhƣ đƣợc
trình bày trên lý thuyết tập thô [6]. Việc sử dụng các tập xác định (các hạt) có thể đƣợc
biểu diễn tƣơng tự một họ các tập xác định (các hạt) sử dụng nhát cắt của nó. Các phép
toán trên các hạt mờ do đó có thể đƣợc định nghĩa bằng các phép toán trên nhát cắt.
1.4.3.1 Đại số luỹ thừa
Giả sử U là một tập hợp và o là một phép toán hai ngôi trên U. Ta định nghĩa một
phép toán hai ngôi o
+
trên các tập con của U nhƣ sau:
 
|,X Y x y x X y Y

  

với mọi
,X Y U
. Tổng quát, ta có thể suy rộng bất kỳ phép toán f trên các phần
tử của U thành một phép toán f
+
trên các tập con của U, và gọi là phép toán luỹ thừa
của f. Giả sử
 
:1

k
U f f
của tập cơ sở U và các phép toán
1
, ,
k
ff
, đại số luỹ thừa của chúng đƣợc cho bởi bộ
1
(2 , , , )
U
k
ff

.
Phép toán luỹ thừa f
+
có thể có một số tính chất của f. Ví dụ với một phép toán hai
ngôi
2
:f U U
, nếu f là giao hoán và kết hợp thì f
+
cũng tƣơng ứng là giao hoán và
kết hợp. Nếu e là một phần tử đơn vị với một phép toán f, tập {e} là một phần tử đơn
vị với f
+
. Nếu một phép toán
:f U U
là một phép đối hợp, tức là

,|a a x a x a

  

.
Các khoảng đặc biệt có dạng [a, a] là tƣơng đƣơng với các số thực.

- 12 -
Ta có thể thực hiện các phép toán trên các khoảng bằng cách suy rộng các phép toán
trên các số thực. Giả sử
,A a a



và
,B b b



là hai khoảng, ta có:
 
| , ,A B x y x A y B a b a b

       

.
 
| , ,A B x y x A y B a b a b

       

12
AA
.
 
1 2 1 2
, 2 |
U
A A X A X A

    

A
đƣợc gọi là một tập khoảng đóng. Tập A
1

đƣợc gọi là biên dƣới của tập khoảng, và tập A
2
là biên trên. Các tập khoảng đặc biệt
dạng [A,A] là tƣơng đƣơng với các tập thông thƣờng.
Suy rộng các phép toán của lý thuyết tập hợp nhƣ phép giao, phép hợp và phần bù,
chúng ta định nghĩa các phép toán của tập khoảng nhƣ sau:
 
 
 
 
 
 
1 1 2 2
1 1 2 2
1 2 2 1

, ~ ,~U A U A A A  
.
1.5 Kết luận
Tính toán hạt có một tầm ảnh hƣởng lớn trong việc thiết kế và triển khai các hệ
thống thông tin thông minh, và trong việc giải các bài toán trong thực tế. Các kết quả
từ những nghiên cứu đang tồn tại chỉ ra sự phong phú và tính mềm dẻo của tính toán
hạt. Những nghiên cứu đó cũng chỉ ra sự cần thiết phải nghiên cứu xa hơn, đặc biệt là
khía cạnh ngữ nghĩa của tính toán hạt. - 13 -
CHƢƠNG 2: BÀI TOÁN QUYẾT ĐỊNH VÀ PHƢƠNG PHÁP GIẢI QUYẾT
DỰA VÀO HẠT DỮ LIỆU
2.1 Các cách kết hạt từ một tập
Khái niệm về quan hệ “không phân biệt đƣợc” cung cấp một phƣơng pháp mô tả
mối quan hệ giữa các phần tử trong một tập tổng thể. Trong lý thuyết các tập thô, quan
hệ không phân biệt đƣợc đƣợc mô hình hoá bằng một quan hệ tƣơng đƣơng. Một quan
sát kết hạt của tập tổng thể có thể nhận đƣợc từ các lớp tƣơng đƣơng. Bằng cách thay
đổi quan hệ tƣơng đƣơng thành quan hệ chỉ có tính chất phản xạ, ta có thể nhận đƣợc
các cách kết hạt khác nhau của một tập tổng thể.
2.1.1 Kết hạt bằng các quan hệ tƣơng đƣơng
Giả sử
E U U
là một quan hệ tƣơng đƣơng trên một tập hữu hạn khác rỗng U. E
có tính phản xạ, đối xứng và bắc cầu. Quan hệ tƣơng đƣơng có thể đƣợc định nghĩa
dựa trên các tri thức sẵn có. Ví dụ trong một bảng thông tin, các phần tử trong bảng
đƣợc mô tả bằng một tập các thuộc tính. Hai phần tử đƣợc gọi là tƣơng đƣơng nếu
chúng có cùng giá trị trên một số thuộc tính nào đó. Lớp tƣơng đƣơng:
 
 

phép lấy phần bù, phép giao và phép hợp.

- 14 -
2.1.2 Kết hạt bằng các quan hệ đồng dạng
Giả sử R là một quan hệ hai ngôi trên tập tổng thể U biểu diễn tính đồng dạng của
các phần tử trong U. Chúng ta giả thiết rằng R có tính chất phản xạ, tức là một phần tử
e là đồng dạng với chính nó, nhƣng không nhất thiết phải có tính đối xứng và bắc cầu.
Với hai phần tử
,x y U
, nếu xRy thì ta nói rằng x là đồng dạng với y. Quan hệ R có
thể đƣợc biểu diễn thuận tiện hơn sử dụng tập các phân tử đồng dạng với x, hoặc lân
cận gần nhƣ sau:
   
|
R
x y U yRx
.
Tập (x)
R
chứa tất cả các phần tử đồng dạng với x. Chúng ta có
()
R
xx
. Khi R là
một quan hệ tƣơng đƣơng, (x)
R
là lớp tƣơng đƣơng chứa x. Họ của các lân cận gần:
 
 
/|

đƣơng thì
R

là R.
Cặp apr=(U,R) đƣợc nghiên cứu là một không gian xấp xỉ tổng quát. Lân cận (x)
R

đƣợc gọi là một hạt cơ bản. Các hạt cơ bản, tập rỗng và hợp của các hạt cơ bản đƣợc
gọi là các hạt xác định trong không gian apr = (U, R). Gọi Def(U / R) là tập tất cả các
hạt xác định. Nó là đóng với phép hợp, và có thể không cần thiết là đóng với phép giao
và phép lấy phần bù. Tập Def(U / R) chứa cả tập rỗng và tập U. Từ Def(U / R), ta định
nghĩa:
 
( / ) | ( / )
CC
Def U R A A Def U R
,
trong đó A
c
là phần bù của A. Hệ thống mới Def
C
(U/R) chứa rỗng và U và đóng với
phép giao. Hệ thống này còn đƣợc gọi là hệ thống đóng kín. Nếu quan hệ R là một
quan hệ tƣơng đƣơng thì hai hệ thống là một. Trong trƣờng hợp tổng quát, hai hệ
thống là không giống nhau.

- 15 -
2.2 Giới thiệu về các tập thô
2.2.1 Giới thiệu
Tập thô là một lý thuyết toán học mới nhằm giải quyết các bài toán có tính không

(Flu)
p1
không
có
cao
có
p2
Có
không
cao
có
p3
Có
có
rất cao
có
p4
không
có
bình thường
không
p5
Có
không
cao
không
p6
không
có
rất cao

Bảng quyết định là hệ thông tin có dạng
( , { })A U A d
, (hay
( , ,{ }))A U A d
, với d

A là thuộc tính quyết định. Các thuộc tính thuộc A được
gọi là thuộc tính điều kiện hay điều kiện.
Thuộc tính quyết định có thể có nhiều hơn hai giá trị, tuy nhiên thông dụng là thuộc
kiểu logic.
Nhƣ vậy chúng ta không thể phân biệt đƣợc một số đối tƣợng đƣợc mô tả từ một tập
thuộc tính. Nhƣng chúng ta lại có thể quan sát, đo hoặc định nghĩa một tập các đối
tƣợng trong một khối tổng thể, không phân biệt đƣợc chúng dƣới dạng các đối tƣợng
riêng lẻ, và trong tập luỹ thừa, chỉ một số tập con có thể đƣợc đo hoặc đƣợc định
nghĩa. Do đó, tình trạng không chắc chắn xảy ra khi chúng ta muốn phân biệt cụ thể
các đối tƣợng này.
Một trong những ý tƣởng cơ bản là làm thế nào để chúng ta có thể biểu diễn các tập
con không xác định thông qua các tập con xác định. Trả lời cho câu hỏi này ta có một
giải pháp: một tập con không xác định đƣợc biểu diễn một cách xấp xỉ bằng hai tập
con xác định, đƣợc gọi là các xấp xỉ trên và xấp xỉ dƣới.
2.2.2 Các định nghĩa về các tập thô
Giả sử U là một tập hữu hạn và đƣợc gọi là tập tổng thể, E là một quan hệ tƣơng
đƣơng trên U. Dƣới đây là một số ký hiệu đƣợc sử dụng trong luận văn.
 U/E là phân hoạch sinh bởi quan hệ tƣơng đƣơng E.
 [x]
E
biểu diễn lớp tƣơng đƣơng chứa x.
 apr=(U, E) đƣợc gọi là một không gian xấp xỉ.
 Def(U) là họ tất cả các tập con xác định trên U.
2.2.2.1 Định nghĩa hƣớng phần tử

   
 
( ) |
( ) |
EE
EE
apr X x x X
apr X x x X


  



Xấp xỉ dƣới là hợp của các lớp tƣơng đƣơng nằm trọn trong X. Xấp xỉ trên là hợp
của các lớp tƣơng đƣơng có giao khác rỗng với X. Định nghĩa hƣớng hạt cung cấp một
mô hình cho tính toán hạt.
Trong một không gian xấp xỉ tổng quát apr = (U, R), các xấp xỉ tập thô hƣớng hạt
có thể đƣợc định nghĩa nhƣ trên nhƣng lớp tƣơng đƣơng [x]
E
đƣợc thay bằng lân cận
(x)
R
.
2.2.2.3 Định nghĩa hƣớng hệ thống con
Định nghĩa 2.5.
Với bất kỳ tập con
XU
, các xấp xỉ trên và xấp xỉ dƣới đƣợc định nghĩa bởi:
 

x



,

- 18 -
trong đó

là ký hiệu lực lƣợng của một tập. Giá trị thuộc thô
()
A
x

có thể hiểu là
xác suất có điều kiện để một phần tử bất kỳ thuộc vào A thì thuộc vào [x]
E
. Trên thực
tế các xác suất có điều kiện đã đƣợc sử dụng trƣớc khi có sự phát triển của mô hình tập
thô theo lý thuyết xác xuất.
Các hàm thuộc thô có thể đƣợc hiểu nhƣ các hàm thuộc mờ. Khi áp dụng các hàm
thuộc mờ trong lý thuyết tập thô chúng ta có:
(1) ( ) 1,
U
x



(2) ( ) 0,x


 
(7) ( ) 0,
AE
x x A

  

(8) ( ) ( )
AB
A B x x

  

Tính chất (3) chỉ ra rằng các phần tử trong cùng lớp tƣơng đƣơng phải có cùng mức
thuộc. Do đó các phần tử không phân biệt đƣợc phải có cùng giá trị thuộc. Tính chất
(4) và (5) có thể đƣợc diễn đạt một cách tƣơng đƣơng nhƣ sau:
(4) ( ) 0 ,
A
x x A

  

(5) ( ) 1 ,
A
x x A

  

Trong một không gian xấp xỉ tổng quát, apr = (U, R) đƣợc định nghĩa bằng một
quan hệ phản xạ, với một tập con A của tập tổng thể, một hàm thuộc thô có thể đƣợc

.
 
(3 ) ( ) , ( ) 0 ( ) 1
R A A
b y x x y

   
.
hoặc có thể viết
 
(3 ) ( ) , ( ) 0 ( ) 1
R A A
a y x y x

   
.
 
(3 ) ( ) , ( ) 1 ( ) 0
R A A
b y x y x

   
.
Chúng có thể đƣợc hiểu một cách tƣơng tự đối với các quan hệ tƣơng đƣơng:
(3 ) ( ) ( )
R A A
c x y x y

  
.


( 4) max( ( ), ( )) ( ) min(1, ( ) ( ))
A B A B A B
o x x x x x
    

  

Ta có thể kiểm tra những tính chất sau tƣơng ứng với các tính chất của t-chuẩn và t-
đối chuẩn:
(t1) Các điều kiện biên:

( ( ) 0, ( ) 0) ( ) 0
A B A B
x x x
  

   
.

( ( ) 1, ( ) ) ( )
A B A B
x x a x a
  

   
.

( ( ) , ( ) 1) ( )
A B A B

   

.
(s1) Các điều kiện biên

( ( ) 1, ( ) 1) ( ) 1
A B A B
x x x
  

   
.

( ( ) 0, ( ) ) ( )
A B A B
x x a x a
  

   
.

( ( ) , ( ) 0) ( )
A B A B
x a x x a
  

   
.
(s2) Đơn điệu


một tập con
AU
. Bằng cách lựa chọn các phần tử có giá thuộc khác 0 và 1, chúng
ta nhận đƣợc các xấp xỉ trên và dƣới của A nhƣ sau:
 
( ) | ( ) 1
A
apr A x U x

  
.
 
( ) | ( ) 0
A
apr A x U x

  
.

- 20 -
2.2.2.5 Một số tính chất của các xấp xỉ
Các xấp xỉ có một số tính chất sau đây:
1)
( ) ( )apr X X apr X
,
2)
( ) ( ) ; ( ) ( )apr apr apr U apr U U      
,
3)
( ) ( ) ( )apr X Y apr X apr Y  

2.2.2.6 Sự phân lớp thô
Dựa trên các xấp xỉ trên và xấp xỉ dƣới, tập tổng thể U có thể đƣợc phân chia thành
các vùng không giao nhau đƣợc gọi là POS(X), NEG(X) và vùng ranh giới BND(X)
nhƣ sau:
( ) ( )
( ) ( )
( ) ( ) ( )
POS X apr X
NEG X U apr X
BND X apr X apr X




Vùng ranh giới chứa các đối tƣợng không thể đƣợc phân lớp mà không có độ không
chắc chắn, phù hợp với khả năng không thể của chúng ta để phân biệt một số các đối
tƣợng khác nhau.
Các vùng trên cũng có thể đƣợc định nghĩa theo các hàm thuộc thô:
 
 
 
( ) | ( ) 1
( ) | ( ) 0
( ) |0 ( ) 1
X
X
X
POS X x U x
NEG X x U x
BND X x U x

2.3.1 Khái quát về thủ tục quyết định Bayes
Gọi
 
1s
w , ,w


là một tập hữu hạn s trạng thái, gọi
 
1
, ,
m
A a a
là một tập
hữu hạn m tác động có thể. P(w
j
/x) là xác suất có điều kiện của đối tƣợng x trong trạng
thái w
j
khi x xảy ra. Giả thiết rằng các xác suất có điều kiện P(w
j
/x) là đã biết.
Gọi
ij
(a |w )

biểu diễn lƣợng tiêu hao để nhận đƣợc tác động a
i
khi trạng thái là
w

()x

trả
lại một trong các tác động a
1
,…, a
m
. Độ rủi ro toàn cục R là lƣợng hao phí kỳ vọng gắn
với với một luật quyết định cho trƣớc. Vì
( ( )| )R x x

là độ rủi ro có điều kiện gắn với
tác động
()x

, độ rủi ro toàn cục đƣợc định nghĩa bởi:

( ( )| ) ( )
x
R R x x P x



.

- 22 -
Ở trên, phép tính tổng đƣợc thực hiện trên tập của tất cả các mô tả có thể của các
đối tƣợng. Nếu
()x


1
)=0,2.
 Tập các tác động
a
0
– Để xe trên vỉa hè (trả 2 nghìn)
a
1
– Để xe trên bãi đỗ xe (trả 7 nghìn)
 Hàm tiêu hao:

(a
0
| s
0
) = 2

(a
1
| s
0
) = 10

(a
0
| s
1
) = 60

(a

1
) =

(a
1
| s
0
)P(s
0
) +

(a
1
| s
1
)P(s
1
)
= 10 * 0,8 + 10 * 0,2 = 10,0.
 Do đó lựa chọn tác động a
1
.
2.3.2 Mô hình lý thuyết quyết định sử dụng tập thô
Các xấp xỉ dƣới của một tập là tƣơng ứng với vùng POS. Xấp xỉ trên là hợp của
vùng ranh giới và vùng POS,
( ) ( ) ( )apr A POS A BND A
. Có thể nói rằng một phần
tử bất kỳ
()x POS A
thuộc vào A, và phần tử bất kỳ

3
là ba tác động trong việc phân
lớp một đối tƣợng thuộc vùng POS(A), NEG(A) hay BND(A).
Ký hiệu
 
|
i
aA

là lƣợng tiêu hao khi thực hiện tác động a
i
để một đối tƣợng
thuộc vào A, và đặt
 
|
i
aA


là ký hiệu lƣợng tiêu hao khi thực hiện cùng tác động a
i

nhƣng đối tƣợng không thuộc vào A. Các giá trị thuộc thô
 
( ) ( | )
A
E
x P A x



,

     
2 21 22
( | ) ( | ) ( | )
E E E
R a x P A x P A x

  
,

     
3 31 32
( | ) ( | ) ( | )
E E E
R a x P A x P A x

  
,
trong đó
 
1
|
ii
aA


,
 
2

EE
R a x R a x
thì quyết định NEG(A);
(B) Nếu
   
31
( | ) ( | )
EE
R a x R a x
và
   
32
( | ) ( | )
EE
R a x R a x
, quyết định NEG(A);
Khi các tác động có cùng giá trị trên R, nên thêm vào các luật lựa chọn tác động để
mỗi phần tử đƣợc phân lớp vào trong chỉ một vùng. Vì
   
( | ) ( | ) 1
EE
P A x P A x  
,
các luật quyết định ở trên có thể đƣợc phân lớp chỉ theo
 
( | )
E
P A x
. Chúng ta có thể
phân lớp bất kỳ một đối tƣợng nào trong lớp tƣơng đƣơng [x]

 
( | )
E
P A x


và
 
( | )
E
P A x


thì quyết định POS(A);