Ứng dụng lý thuyết tập thô trong khai phá dữ liệu giao thông vận tải
Học viên thực hiện : - Đặng Thị Thanh Châu, CH1201005
- Bùi Văn Chương, CH1201092
- Mã Khánh Xuyên, CH1201149
Trang 1
MỤC LỤC

LỜI GIỚI THIỆU 2
Chương 1: Tổng quan về khai phá dữ liệu và lý thuyết tập thô 3
1.1. Data Mining là gì: 3
1.1.1. Các phương pháp khai phá trong Data Mining: 4
1.1.2. Các ứng dụng của Data Mining: 6
1.2. Lý thuyết tập thô: 7
1.2.1. Hệ thông tin và bảng quyết định: 7
1.2.2. Phân lớp tương đương: 8
1.2.3. Không gian xấp xỉ: 10
1.2.4. Sự phụ thuộc các thuộc tính: 10
1.2.5. Kết luận: 11
Chương 2: Phương pháp rút gọn thuộc tính và sinh luật trên bảng quyết định 12
2.1. Rút gọn các thuộc tính: 12
2.2. Ma trận phân biệt và hàm phân biệt: 12
2.3. Luật quyết định: 13
2.4. Thuật toán LEM1 rút gọn thuộc tính trên bảng quyết định: 14
2.5. Sinh luật quyết định trên tập rút gọn của bảng quyết định 16
2.6. Kết luận: 17
Chương 3: Chương trình ứng dụng lý thuyết tập thô trong 18
khai thác dữ liệu giao thông vận tải 18
3.1. Giới thiệu về chương trình ứng dụng: 18
3.2. Ứng dụng lý thuyết tập thô, cài đặt và thử nghiệm 18
3.2.1. Giao diện của chương trình demo 18
3.2.2. Một số source code minh họa: 21

3.3. Kết luận: 23
TÀI LIỆU THAM KHẢO 24

Ứng dụng lý thuyết tập thô trong khai phá dữ liệu giao thông vận tải
Học viên thực hiện : - Đặng Thị Thanh Châu, CH1201005
- Bùi Văn Chương, CH1201092
- Mã Khánh Xuyên, CH1201149
Trang 2
LỜI GIỚI THIỆU


Sự bùng nổ và phát triển của công nghệ thông tin đã mang lại nhiều hiệu quả
đối với khoa học cũng như trong các hoạt động thực tế, trong đó khai phá dữ
liệu (Data Mining) là một lĩnh vực mang lại hiệu quả thiết thực cho con người.
Khai phá dữ liệu giúp ta chắt lọc được những thông tin có giá trị từ những khối
dữ liệu thô khổng lồ ta nhận được, tìm ra những xu hướng phát triển và những
yếu tố tác động lên chúng.
Lý thuyết tập thô do nhà logic học Balan Zdzislak Pawlak đề xuất vào đầu
những năm 80 được xem như là một cách tiếp cận mới để phát hiện tri thức và
tạo thành một cơ sở vững chắc cho các ứng dụng khai phá dữ liệu. Nó rất hữu
ích trong việc giải quyết các bài toán phân lớp dữ liệu, phát hiện luật, … chứa
dữ liệu mơ hồ không chắc chắn.
Tập thô có quan điểm hoàn toàn khác với quan điểm truyền thống về 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ử thuộc 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 rằng
chúng có quan hệ không thể phân biệt được. Đây chính là quan hệ mấu chốt và
chính 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, chúng ta phải xấp xỉ nó bằng các tập hợp khác nhau, nhằm mục đích cuối
cùng là trả lời được rằng một đối tượng nào đó thuộc tập hợp hay không.

Lý thuyết tập thô với các tiếp cận như vậy đã và đang được ứng dụng rất rộng
rãi. Có nhiều đề tài nghiên cứu cho kết quả khả quan và đã được đưa vào ứng
dụng trong thực tế như xử lý ảnh trong y tế, khai phá dữ liệu y tế, nhận dạng, trí
tuệ nhân tạo,

Ứng dụng lý thuyết tập thô trong khai phá dữ liệu giao thông vận tải
Học viên thực hiện : - Đặng Thị Thanh Châu, CH1201005
- Bùi Văn Chương, CH1201092
- Mã Khánh Xuyên, CH1201149
Trang 3
Chương 1: Tổng quan về khai phá dữ liệu và lý thuyết tập thô

1.1. Data Mining là gì:
Data Mining (khai phá dữ liệu) là một khái niệm mô tả quá trình khám phá
các tri thức mới và các tri thức có ích ở dạng tiềm năng trong các nguồn dữ liệu
lớn, đã có.
Data Mining là một bước của tiến trình KDD (Knowledge discovery in
databases), nhằm:
- Rút trích thông tin hữu ích, chưa biết, tiềm ẩn trong khối dữ liệu lớn
- Phân tích dữ liệu bán tự động
- Giải thích dữ liệu trên các tập dữ liệu lớn

Một tiến trình KDD là một chuỗi lặp gồm các bước:
1) Data cleaning & intergration (làm sạch dữ liệu, tích hợp dữ liệu)
2) Selection & transformation (chọn lựa dữ liệu, biến đổi dữ liệu)
3) Data Mining (khai phá dữ liệu)
4) Evaluation & presentation (đánh giá kết quả mẫu, biểu diễn tri
thức).
Bắt đầu của quá trình KDD là kho dữ liệu thô và kết thúc của quá trình là kết
xuất ra tri thức từ kho dữ liệu mà trong đó khai phá dữ liệu là bài toán quan

trọng nhất.
Ứng dụng lý thuyết tập thô trong khai phá dữ liệu giao thông vận tải
Học viên thực hiện : - Đặng Thị Thanh Châu, CH1201005
- Bùi Văn Chương, CH1201092
- Mã Khánh Xuyên, CH1201149
Trang 4
1.1.1. Các phương pháp khai phá trong Data Mining:
Thông thường, các bài toán trong Data Mining có thể đưa về 2 nhóm chính:
Các bài toán mang tính dự đoán (Predictive): đưa ra các dự đoán dựa vào các
suy diễn trong cơ sở dữ liệu mẫu, gồm các phương pháp:
- Classification (Phân lớp)
- Regression (Hồi qui)
- Time Series Analysis (Phân tích chuỗi thời gian)
- Prediction (Dự đoán)
Các bài toán mang tính mô tả (Description): đưa ra các tính chất chung nhất
của dữ liệu trong cơ sở dữ liệu mẫu , gồm các phương pháp:
- Clustering (Phân cụm)
- Summarization (Tổng quát hóa)
- Association Rule (Luật kết hợp)
- Sequence Discovery ( Khám phá tuần tự)
Tuỳ theo bài toán xác định được mà ta lựa chọn các phương pháp khai phá dữ
liệu cho phù hợp.

a. Phân lớp và dự đoán (Classification & Prediction)
Là đặt các mẫu vào các lớp được xác định trước. Nhiệm vụ chính là tìm các
hàm ánh xạ các mẫu dữ liệu một cách chính xác vào trong các lớp.Ví dụ một
ngân hàng muốn phân loại các khách hành của họ vào trong hai nhóm có nợ hay
không nợ, từ đó giúp họ ra quyết định cho vay hay không cho vay.
Trong kỹ thuật phân lớp chúng ta có thể sử dụng các phương pháp như: Cây
quyết định (Decision Tree), K-Láng giềng gần nhất (k-Nearest Neighbor), Mạng

Ứng dụng lý thuyết tập thô trong khai phá dữ liệu giao thông vận tải
Học viên thực hiện : - Đặng Thị Thanh Châu, CH1201005
- Bùi Văn Chương, CH1201092
- Mã Khánh Xuyên, CH1201149
Trang 5
Nơron (Neural networks), Giải thuật di truyền (Genetic algorithms), Mạng
Bayesian(Bayesian networks), Tập mờ và tập thô (Rough and Fuzzy Sets),…
b. Hồi quy (Regression)
Hồi quy là việc đưa một hàm ánh xạ từ một mẫu dữ liệu thành một biến dự
đoán có giá trị thực. Nhiệm vụ của hồi quy tương tự như phân lớp, điểm khác
nhau chính là ở chỗ thuộc tính để dự báo là liên tục chứ không rời rạc. Việc dự
báo các giá trị số thường được làm bởi các phương pháp thống kê cổ điển chẳng
hạn như hồi quy tuyến tính.
c. Time Series Analysis (Phân tích chuỗi thời gian)
Dựa trên việc phân tích chuỗi quan sát của một biến duy nhất theo biến số độc
lập là thời gian. Phương pháp dự báo theo chuỗi thời gian là một phương pháp
định lượng, sử dụng những dữ liệu quá khứ theo thời gian, dựa trên dữ liệu lịch
sử để phát hiện chiều hướng vận động của đối tượng phù hợp với một mô hình
bài toán nào đó và đồng thời sử dụng mô hình đó làm mô hình ước lượng. Tiếp
cận định lượng dựa trên giả định rằng giá trị tương lai của biến số dự báo sẽ phụ
thuộc vào xu thế vận động của đối tượng đó trong quá khứ.
d. Prediction (Dự đoán)
Với mô hình học tương tự như bài toán phân lớp, lớp bài toán dự đoán sẽ lọc
ra các bộ dự đoán. Khi có dữ liệu mới đến, bộ dự đoán sẽ dựa trên thông tin
đang có để đưa ra một giá trị số học cho hàm cần dự đoán. Bài toán tiêu biểu
trong nhóm này là dự đoán giá sản phẩm để lập kế hoạch trong kinh doanh.
e. Clustering (Gom nhóm)
Mục tiêu chính của việc phân nhóm dữ liệu là nhóm các đối tượng tương tự
nhau trong tập dữ liệu vào các nhóm sao cho mức độ tương tự giữa các đối
tượng trong cùng một nhóm là lớn nhất và mức độ tương tự giữa các đối tượng

nằm trong các nhóm khác nhau là nhỏ nhất. Một đối tượng có thể vừa thuộc
nhóm này, nhưng cũng có thể vừa thuộc nhóm khác.
Phân nhóm dữ liệu được sử dụng nhiều trong các ứng dụng về phân đoạn thị
trường, phân đoạn khách hàng, nhận dạng mẫu, phân loại trang Web, … Ngoài
Ứng dụng lý thuyết tập thô trong khai phá dữ liệu giao thông vận tải
Học viên thực hiện : - Đặng Thị Thanh Châu, CH1201005
- Bùi Văn Chương, CH1201092
- Mã Khánh Xuyên, CH1201149
Trang 6
ra phân nhóm dữ liệu còn có thể được sử dụng như một bước tiền xử lý cho các
bài toán khai phá dữ liệu khác.
f. Summarization (Tổng quát hóa)
Kỹ thuật mô tả khái niệm và tổng quát hóa thường áp dụng trong việc phân
tích dữ liệu có tính thăm dò và báo cáo tự động. Nhiệm vụ chính là sản sinh ra
các mô tả đặc trưng cho một lớp. Mô tả loại này là một kiểu tổng hợp, tóm tắt
các đặc tính chung của tất cả hay hầu hết các mục của một lớp.
g. Luật kết hợp (Association Rules):
Luật kết hợp là dạng luật biểu diễn tri thức ở dạng tương đối đơn giản. Các
giải thuật tìm luật kết hợp tìm kiếm các mối liên kết giữa các phần tử dữ liệu, ví
dụ như nhóm các món hàng thường được mua kèm với nhau trong siêu thị.
Tuy luật kết hợp là một dạng luật khá đơn giản nhưng lại mang rất nhiều ý
nghĩa. Thông tin mà dạng luật này đem lại rất có lợi trong các hệ hỗ trợ ra quyết
định. Tìm kiếm được những luật kết hợp đặc trưng và mang nhiều thông tin từ
CSDL tác nghiệp, là một trong những hướng tiếp cận chính của lĩnh vực khai
phá dữ liệu.
1.1.2. Các ứng dụng của Data Mining:
- Tài chính và thị trường chứng khoán (Finance & stock market): Phân tích
tình hình tài chính và dự đoán giá cổ phiếu.
- Thống kê, phân tích dữ liệu và hỗ trợ ra quyết định
- Trong lĩnh vực y tế: Phân tích mối liên hệ giữa các triệu chứng bệnh,

chuẩn đoán và phương pháp điều trị (chế độ dinh dưỡng, thuốc, thời gian )
- Text mining và Web mining: Phân lớp văn bản và các trang Web, tóm tắt
văn bản,
- Lĩnh vực khoa học: Quan sát thiên văn, dữ liệu gene, dữ liệu sinh vật học,
tìm kiếm, so sánh các hệ gene và thông tin di truyền, mối liên hệ gene và một
số bệnh di truyền,
- Mạng viễn thông: Phân tích các cuộc gọi điện thoại và hệ thống giám sát
lỗi, sự cố, chất lượng dịch vụ,
Ứng dụng lý thuyết tập thô trong khai phá dữ liệu giao thông vận tải
Học viên thực hiện : - Đặng Thị Thanh Châu, CH1201005
- Bùi Văn Chương, CH1201092
- Mã Khánh Xuyên, CH1201149
Trang 7
1.2. Lý thuyết tập thô:
Lý thuyết tập thô (Rough set Theory) được Zdzislaw Pawlak đề xuất vào đầu
những năm 1980 và nó nhanh chóng được các nhà khoa học tiếp nhận như một
công cụ toán học mới để xử lý những thông tin không đầy đủ và không chắc
chắn.
1.2.1. Hệ thông tin và bảng quyết định:
a. Hệ thông tin (information system):
Một tập bất kỳ các đối tượng không thể phân biệt được (các đối tượng tương
tự) được gọi là tập cơ bản (elementary set) và tạo thành nguyên tử (atom hay
granule) của tri thức về vũ trụ.
Hệ thông tin là một bộ bốn: S=<U, A, V, f>
Trong đó:
U = { x
1
,x
2
, ,x

n
} là một tập hữu hạn các đối tượng (objects)
A là tập thuộc tính và được chia thành 2 tập con: các thuộc tính điều kiện
(condition attribute )C và các thuộc tính quyết định (decision attribute) D;
A=CD
- V là tập hữu hạn các giá trị thuộc tính
trong đó : V = U
a A
V
a
,với V
a
là miền (domain) của thuộc tính a
- f: U×A  V là hàm thông tin (information function),
trong đó f(x,a) V
a
; a A; x U

b. Bảng quyết định:
Giả sử rằng 𝐴=𝐶𝐷 𝑣à 𝐶𝐷=∅ , thì một hệ thông tin có thể được xem như
một bảng quyết định hay còn gọi là bảng thuộc tính giá trị (attribute-value table)
𝑆=〈𝑈,𝐶𝐷,𝑉,𝑓〉
Bảng quyết định là có tính quyết định (determainistic) khi và chỉ khi 𝐶→𝐷.
Ngược lại nó không có tính quyết định.
Trong trường hợp bảng quyết định không có tính quyết định thì quyết định
không được xác định một cách duy nhất mà có thể là cả một tập quyết định.
Ứng dụng lý thuyết tập thô trong khai phá dữ liệu giao thông vận tải
Học viên thực hiện : - Đặng Thị Thanh Châu, CH1201005
- Bùi Văn Chương, CH1201092
- Mã Khánh Xuyên, CH1201149

Trang 8
Một cơ sở dữ liệu được xem như một thông tin trong đó các cột là các thuộc
tính, các hàng là các đối tượng và thực thể ở cột p, hàng x có giá trị p(x). Mỗi
hàng trong bảng biểu diễn thông tin về một đối tương trong U. Trong cơ sở dữ
liệu, có thuộc tính là thuộc tính quyết định, các thuộc tính còn lại là thuộc tính
điều kiện.
Từ bảng quyết định người ta có thể tạo ra một tập các luật quyết định
(decisoin rules)
Bảng biểu diễn một hệ thông tin

1.2.2. Phân lớp tương đương:
Các đối tượng được đặc trưng bởi cùng thông tin thì không thể phân biệt được
(indiscernable). Vì vậy quan hệ tương đương là cơ sở toán học của lý thuyết tập
thô.
Cho S=⟨𝑈,𝐴,𝑉,𝑓⟩ là một hệ thống thông tin, 𝑃⊆𝐴 ;𝑋⊆𝑈;𝑥,𝑦∈𝑈 mọi tập
không rỗng các đối tượng được gọi là một khái niệm (concept).
Vậy X là một khái niệm trong hệ thông tin.Ta nói rằng, x và y là không
thể phân biệt (indiscernable) bởi tập các thuộc tính P trong S, khi và chỉ khi:
𝑓(𝑥,𝑎)=𝑓(𝑦,𝑎);∀𝑎∈𝐴 .
Từ đó ta định nghĩa, tập thuộc tính P được gọi là không thể phân biệt (ký hiệu
là IND(P)) nếu: 𝐼𝑁𝐷(𝑃)={(𝑥,𝑦)∈𝑈×𝑈:𝑓(𝑥,𝑎)=𝑓(𝑦,𝑎), ∀𝑎∈𝑃}
Quan hệ không thể phân biệt là một quan hệ tương đương và nó chia U thành
các lớp tương đương và ta ký hiệu sự phân lớp này bởi 𝑈/𝑃 .
Ứng dụng lý thuyết tập thô trong khai phá dữ liệu giao thông vận tải
Học viên thực hiện : - Đặng Thị Thanh Châu, CH1201005
- Bùi Văn Chương, CH1201092
- Mã Khánh Xuyên, CH1201149
Trang 9
Với ∀𝑥∈𝑈,lớp tương đương của x trong quan hệ IND(P))được biểu diễn đơn
giản là : [𝒙]

𝑰𝑵𝑫
(
𝑷
)

Ví dụ: Cho hệ thông tin 𝑈={u
0
,𝑢
1
,𝑢
2
,𝑢
3
,𝑢
4
,𝑢
5
} 𝐴={𝑎
1
,𝑎
2
,𝑎
3
,𝑎
4
}
𝑉
a0
=𝑉
a2

={𝛼,𝛽,𝛾,𝛿} ; 𝑉
a1=
{𝑄,𝑅} ; 𝑉
a3
={𝛼𝛽,𝛽𝛾,𝛾𝛽,𝛾𝛿};
𝑉
a4
={ℰ,ℱ,Ω} ; 𝑓(𝑥
0
,𝑎
0
)=𝛼 ; 𝑓(x
0
,𝑎
1
)=𝑄 ; … (xem bảng )


Hệ thông tin trên có một số quan hệ phân biệt sau:
𝑃={𝑎
0
,𝑎
2
} ; 𝑄={𝑎
1
}
𝐼𝑁𝐷(𝑃)={(𝑢
0
,𝑢
3

)}; 𝑈∣𝐼𝑁𝐷(𝑃)={(𝑢
0
,𝑢
3
),(𝑢
1
),(u
2
)(𝑢
4
),(𝑢
5
)}
𝐼𝑁𝐷(𝑄)={(𝑢
0
,𝑢
1
),(𝑢
2
,𝑢
3
),(𝑢
2
,𝑢
4
),(𝑢
2
,𝑢
5
),(𝑢

3
,𝑢
4
),(𝑢
3
,𝑢
5
),(𝑢
4
,𝑢
5
)} ;
𝑈∣𝐼𝑁𝐷(𝑄)={{𝑢
0
,𝑢
1
},{𝑢
2
,u
3
,𝑢
4
,𝑢
5
}}
Nếu sự phân biệt của các đối tượng được sử dụng nhiều hơn là giá trị của các
thuộc tính thì hệ thông tin có thể được biểu diễn bởi ma trận phân biệt
(discernibility matrix), mô tả bằng công thức sau:
𝐷
𝑥

,
𝑦
={𝑎∈𝐴:𝑓(𝑥,𝑎)≠𝑓(𝑦,𝑎);𝑥,𝑦∈𝑈}

Ma trận phân biệt tương ứng với ví dụ trên

Ứng dụng lý thuyết tập thô trong khai phá dữ liệu giao thông vận tải
Học viên thực hiện : - Đặng Thị Thanh Châu, CH1201005
- Bùi Văn Chương, CH1201092
- Mã Khánh Xuyên, CH1201149
Trang 10
1.2.3. Không gian xấp xỉ:
Cho hệ thông tin 𝑆=〈𝑈,𝐴,𝑉,𝑓〉, và 𝑃⊆𝐴 ; XU . Một cặp có thứ tự
𝐴𝑆=(𝑈,𝐼𝑁𝐷(𝑃)) được gọi là không gian xấp xỉ (approximation space), ký hiệu là
AS.
Các lớp tương đương được gọi là các tập P – cơ bản trong AS, vì chúng biểu
diễn các nhóm đối tượng phân biệt được nhỏ nhất.
P – xấp xỉ dưới (lower approximation) của X trong AS, ký hiệu 𝑃
*
(𝑋) hay ,
được định nghĩa bởi: 𝑃
*
(𝑋)={𝑦∈𝑈: [𝑦]
𝐼𝑁𝐷
(
𝑃
)
⊆𝑋} . Tập 𝑃
*
(𝑋) là tập tất cả các

đối tượng trong U mà sử dụng tập thuộc tính P ta chắc chắn chúng là các phần tử
của X.
P – xấp xỉ trên (upper approximation) của X trong AS, ký hiệu 𝑃
*
(𝑋) hay ,
được định nghĩa bởi: 𝑃
*
(𝑋) ={𝑦∈𝑈: [𝑦]
𝐼𝑁𝐷
(
𝑃
)
∩𝑋≠∅} . Tập 𝑃
*
(𝑋) là tập tất cả
các đối tượng trong U mà sử dụng tập thuộc tính P ta chỉ có thể nói rằng chúng là
các phần tử của X.
Nếu 𝑃
*
(𝑋)=𝑃
*
(𝑋) , khi đó ta nói rằng X là tập P – chính xác (P – exact),
ngược lại X được gọi là P – thô (P – rough).
Hệ số chính xác hay độ chính xác xấp xỉ (accuracy of approximation) của tập
đối tương X đối với tập thuộc tính P được định nghĩa bởi:

- Nếu 𝛼
𝑃

(𝑋)=1, tập X là tập rõ đối với quan hệ P.

- Nếu 𝛼
𝑃
(𝑋)<1, tập X là tập thô đối với quan hệ P.
1.2.4. Sự phụ thuộc các thuộc tính:
Cho hệ thông tin 𝑆=〈𝑈,𝐴,𝑉,𝑓〉, và 𝑃⊆𝐴 ; R A
Ta nói rằng tập các thuộc tính 𝑅⊆𝐴 phụ thuộc vào tập các thuộc tính P ⊆𝐴
trong S, ký hiệu 𝑃→𝑅, khi và chỉ khi IND(P)=IND(R) . Việc tìm ra sự phụ
thuộc giữa các thuộc tính là vấn đề rất quan trọng trong tiếp cận tập thô với
phân tích tri thức.
Ứng dụng lý thuyết tập thô trong khai phá dữ liệu giao thông vận tải
Học viên thực hiện : - Đặng Thị Thanh Châu, CH1201005
- Bùi Văn Chương, CH1201092
- Mã Khánh Xuyên, CH1201149
Trang 11
Cho 𝑃,𝑄 ⊆𝐴 . Vùng dương của phân loại 𝑈∣𝐼𝑁𝐷(𝑄) đối với tập thuộc tính
P,gọi là P – vùng dương của Q (P – positive region of Q) được xác định bởi :

P – vùng dương của Q gồm tất cả những đối tượng mà bằng các thuộc tính P
ta phân loại chúng một cách chắc chắn vào một lớp của phân loại 𝑈∣𝐼𝑁𝐷(𝑄).
Lưc lượng của P – vùng dương của Q ,được dùng để đo mức độ phụ thuộc
của Q vào P, và được xác định bởi :
Không phải tất cả các thuộc tính trong P đều có ý nghĩa như nhau đối với
phân loại 𝑈∣𝐼𝑁𝐷(𝑄), do đó người ta xác định hệ số quan trọng (coefficient of
significance) của thuộc tính a bởi:

1.2.5. Kết luận:
Lý thuyết tập thô có nhiều công cụ toán học khác nhau được dùng để xử lý tri
thức không đầy đủ.
Các phép toán cơ bản và phương pháp của lý thuyết tập thô được sử dụng để
phát hiện các mẫu cơ sở (fundamental pattern) trong dữ liệu. Do đó, hết sức

quan trọng đối với lĩnh vực trí tuệ nhân tạo và các ngành khoa học liên quan đến
nhận thức (máy học; 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, phát hiện hiện tri thức,…).

Ứng dụng lý thuyết tập thô trong khai phá dữ liệu giao thông vận tải
Học viên thực hiện : - Đặng Thị Thanh Châu, CH1201005
- Bùi Văn Chương, CH1201092
- Mã Khánh Xuyên, CH1201149
Trang 12
Chương 2: Phương pháp rút gọn thuộc tính và sinh luật trên
bảng quyết định
Trong một hệ thông tin, môt số thuộc tính có thể là dư thừa đối với một phân
loại nhất định. Lý thuyết tập thô đưa ra các khái niệm cho phép rút gọn các
thuộc tính mà không làm giảm khả năng phân loại.
2.1. Rút gọn các thuộc tính:
Cho 𝑃,𝑄∈𝐴 ; 𝑎∈𝑃. Một thuộc tính a là bỏ qua được (dispensable) trong P, nếu
𝐼𝑁𝐷(𝑃)=𝐼𝑁𝐷(𝑃−{𝑎}). Ngược lại , a là không thể bỏ được (indispensable).Thuộc
tính bỏ qua được không lảm giảm hoặc tăng khả năng phân loại khi có hoặc
không có mặt thuộc tính đó.
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, và ký hiệu là CORE(P). Lõi có thể là một tập rỗng .
Một thuộc tính a được gọi là Q – bỏ qua được trong P, nếu :
𝑃𝑂𝑆
𝑃
(𝑄)=𝑃𝑂𝑆
𝑃
−{
𝑎
}
(𝑄) , ngược lại a là Q – không thể bỏ được. Tập tất cả

các thuộc tính Q – bỏ qua được gọi là Q – lõi tương đối (Q – relative) và ta ký
hiệu là 𝐶𝑂𝑅E_
𝑄
(𝑃).
2.2. Ma trận phân biệt và hàm phân biệt:
a. Ma trận phân biệt:
Xét bảng quyết định T= (U,CD) với U = {u1 , u2 , , un } . Ma trận phân
biệt của T ký hiệu M(T) = (m
ij
)
n×n
là một ma trận đối xứng, trong đó mỗi phần
tử của nó là một tập thuộc tính được xác định như sau:

)]()([ )}()( :{
)]()([
jiji
ji
ududDdifucucCc
ududDdif
mij





b. Hàm phân biệt:
Hàm phân biệt f
Τ
là một hàm Boole, được xác định từ ma trận phân biệt M(T)

như sau:
Uunjijmuf
iij
j
iT
 }},, ,2,1{,:{)(

Trong đó, mỗi thuộc tính được đặt tương ứng một biến logic cùng tên và
Ứng dụng lý thuyết tập thô trong khai phá dữ liệu giao thông vận tải
Học viên thực hiện : - Đặng Thị Thanh Châu, CH1201005
- Bùi Văn Chương, CH1201092
- Mã Khánh Xuyên, CH1201149
Trang 13
(1) m
ij
là biểu thức tuyển của tất cả các biến c m
ij
, nếu m
ij
,
(2) m
ij
= true, nếu m
ij
= và u
i
(D) = u
j
(D),
(3) m

ij
= false, nếu m
ij
= và u
i
(D) u
j
(D).
Ví dụ:

2.3. Luật quyết định:
Cho T= (U,CD) là một bảng quyết định, giả sử U/C = {X1, X2, , Xm} và
U/D= {Y1, Y2, , Yn}. Nếu X
i
Y
j
≠, ký hiệu des(Xi), des(Yj) lần lượt là các mô
tả của các lớp tương đương ứng với X
i
, Y
j
. Một luật quyết định xác định bởi X
i
,
Y
j
có dạng:
Z
ij
: des(X

i
)  des(Y
j
)
Độ chắc chắn và độ hỗ trợ của luật quyết định Z
ij
được định nghĩa như sau:
 (Z
ij
)= Xi Yj  X
i
và s(Z
ij
) = Xi Yj  U

Ứng dụng lý thuyết tập thô trong khai phá dữ liệu giao thông vận tải
Học viên thực hiện : - Đặng Thị Thanh Châu, CH1201005
- Bùi Văn Chương, CH1201092
- Mã Khánh Xuyên, CH1201149
Trang 14
2.4. Thuật toán LEM1 rút gọn thuộc tính trên bảng quyết định:
Thuật toán LEM1 (Learning from Examples Module version 1), một thành
phần của LERS (Learning from Examples using Rough Sets - hệ thống khai thác
dữ liệu sử dụng tập thô)
Mô tả thuật toán:
- Input: Các thuộc tính điều kiện A, phân vùng thuộc tính quyết định {d}
*
trên U
- Output: tập các thuộc tính Rút gọn R
1.

2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.

Begin
Tính toán phân vùng A
*
;
P:=A;
R:=;
If A
*
 {d}
*
Then
Begin
For a A do
Begin

Q:= P – {a};
Tính toán phân vùng Q
*

If Q
*
 {d}
*
then P:= Q
End
R:= P
End
End.

Trên cơ sở quy tắc bao phủ tổng thể được tính toán bằng cách sử dụng kỹ
thuật “Dropping conditions” (Michalski, 1983). Cho một quy luật như sau:
C
1
& C
2
& & C
n
→ D
“ Dropping condition” (bỏ điều kiện): có nghĩa là quét các danh sách của tất
cả các điều kiện, từ trái sang phải để thử giảm bớt các điều kiện bất kỳ. Kết hợp
kiểm tra lại bảng quyết định chứa các quy tắc đơn giản hóa không vi phạm tính
nhất quán của biểu thức được mô tả.

Ứng dụng lý thuyết tập thô trong khai phá dữ liệu giao thông vận tải
Học viên thực hiện : - Đặng Thị Thanh Châu, CH1201005

- Bùi Văn Chương, CH1201092
- Mã Khánh Xuyên, CH1201149
Trang 15
Ví dụ: Cho bảng quyết định sau

Ban đầu, ta có:
{Nhiệt độ, Đau đầu, Nhức mỏi, Buồn nôn}
*
= {{u1}, {u2}, {u3}, {u4}, {u5}, {u6},
{u7}},
{Cúm}
*
= {{u1, u2, u4, u5}, {u3, u6, u7}}
và
{Nhiệt độ, Đau đầu, Nhức mỏi, Buồn nôn}
*
≤ {Cúm }
*

Tiếp theo, ta kiểm tra {Đau đầu, Nhức mỏi, Buồn nôn}
*
≤ {Cúm}
*

không?
Sai, vì
{Đau đầu, Nhức mỏi, Buồn nôn}
*
= {{u1}, {u2}, {u3, u6}, {u4}, {u5, u7}}
Tiếp tục tính

{Nhiệt độ, Nhức mỏi, Buồn nôn}
*
={{u1}, {u2}, {u3}, {u4}, {u5}, {u6}, {u7}}
Ta thấy
{Nhiệt độ, Nhức mỏi, Buồn nôn}
*
≤ {Cúm}
*

Các thuộc tính điều kiện tiếp theo để tính toán là
{Nhiệt độ, Buồn nôn}
*
= {{u1}, {u2}, {u3, u7}, {u4}, {u5, u6}}
và
{Nhiệt độ, Buồn nôn}
*
≤ {Cúm}
*

Bước cuối cùng để tính toán
{Nhiệt độ, Nhức mỏi}
*
={{u1}, {u2,u6}, {u3}, {u4, u7}, {u5}},
từ {Nhiệt độ, Nhức mỏi}
*


{Cúm}
*


Ứng dụng lý thuyết tập thô trong khai phá dữ liệu giao thông vận tải
Học viên thực hiện : - Đặng Thị Thanh Châu, CH1201005
- Bùi Văn Chương, CH1201092
- Mã Khánh Xuyên, CH1201149
Trang 16
Do đó: ta giữ nguyên các thuộc tính {Nhiệt độ, Nhức mỏi, Buồn nôn}
Trường hợp u1 ta có
(Nhiệt độ, rất cao) & (Nhức mỏi, có) & (Buồn nôn, không có) → (Cảm, có)
Điều kiện đầu tiên (Nhiệt độ, rất cao) không thể giảm vì quy tắc
(Nhức mỏi, có) & (Buồn nôn, không có) → (Cảm, có)
bao gồm u1 và u7.
Tuy nhiên, điều kiện giảm tiếp theo (Nhức mỏi, có) là thành công, vì
(Nhiệt độ, rất cao) & (Buồn nôn, không có) → (Cảm, có) chỉ có ở u1.
Khả năng tiếp theo, để giảm điều kiện (Nhức mỏi, có) là thành công , vì các quy
tắc kết quả (Nhiệt độ, rất cao) → (Cảm, có) chỉ có ở u1.
Ta tiếp tục thực hiện theo cách tương tự cho các điều kiện còn lại.
Cuối cùng ta có được 2 tập thuộc tính được rút gọn là:
R1(Nhiệt độ, Buồn nôn)
R2 (Nhiệt độ, Nhức mỏi)
2.5. Sinh luật quyết định trên tập rút gọn của bảng quyết định
Thuật toán RuleExtract
Input: Bảng quyết định DS = (U, C

D, V, f).
Output: Hiển thị danh sách các luật với độ chắc chắn

và độ hỗ trợ
s
.
1. Tính phân hoạch

/UC
;
2. For each
/
i
X U C

3. Begin
4. Tính
/
i
XD
;
5. For each
/
ji
Y X D

6. Begin
7. Sinh luật
 
 
:
ij i j
Z des X des Y

8. Tính
 
/
ij j i

Z Y X

;
Ứng dụng lý thuyết tập thô trong khai phá dữ liệu giao thông vận tải
Học viên thực hiện : - Đặng Thị Thanh Châu, CH1201005
- Bùi Văn Chương, CH1201092
- Mã Khánh Xuyên, CH1201149
Trang 17
9. Tính
 
/
ij j
s Z Y U
;
10. Hiển thị luật
ij
Z
, độ chắc chắn
 
ij
Z

, độ hỗ trợ
 
ij
sZ
;
11. End;
12. End;
13. Return.

2.6. Kết luận:
Rút gọn thuộc tính là một bài toán quan trọng trong lý thuyết tập thô. Thông
tin lưu trữ có các thuộc tính dư thừa , không chắc chắn gây khó khăn cho việc
khai phá tri thức. Do đó việc rút gọn thuộc tính là yêu cầu cần thiết trong khai
phá tri thức.
Mục tiêu của rút gọn thuộc tính là loại bỏ các thuộc tính dư thừa để tìm ra các
thuộc tính cốt yếu và cần thiết trong cơ sở dữ liệu. Với bảng quyết định, rút gọn
thuộc tính là tìm tập con nhỏ nhất của tập thuộc tính điều kiện bảo toàn thông tin
phân lớp của bảng quyết định.
Ứng dụng lý thuyết tập thô trong khai phá dữ liệu giao thông vận tải
Học viên thực hiện : - Đặng Thị Thanh Châu, CH1201005
- Bùi Văn Chương, CH1201092
- Mã Khánh Xuyên, CH1201149
Trang 18
Chương 3: Chương trình ứng dụng lý thuyết tập thô trong
khai thác dữ liệu giao thông vận tải

3.1. Giới thiệu về chương trình ứng dụng:
Nhằm nâng cao hiệu quả công tác quản lý, rút ngắn thời gian giải quyết các
hồ sơ, và minh bạch hơn trong việc xây dựng và giải quyết các thủ tục hành
chính, UBND TPHCM đã đầu tư và xây dựng 1 phần mềm dùng chung, và ứng
dụng tại các sở ban ngành như: sở Giao thông vận tải (GTVT), sở Xây dựng, sở
Tài nguyên và môi trường,…
Vấn đề là hiện nay tại phòng vận tải công nghiệp thuộc sở GTVT, số lượng
hồ sơ xin phép về các thủ tục như: thẩm định tuyến, cấp sổ nhật trình, phù hiệu,
cấp phép kinh doanh vận tải,…đang tăng lên rất nhanh và cơ sở dữ liệu là rất
lớn. Mỗi một xe ô tô sẽ đăng ký một loại hình kinh doanh như: xe bus, xe taxi,
xe hợp đồng, xe chạy tuyến cố định, xe du lịch và xe công ten nơ.
Yêu cầu đặt ra là các doanh nghiệp vận tải muốn khai thác cơ sở dữ liệu này
để tìm được mối quan hệ giữa các “hiệu xe” , “số ghế” và “loại hình kinh

doanh” nhằm hỗ trợ và nâng cao hiệu quả kinh doanh của doanh nghiệp.
Ví dụ như hiệu xe “MERCEDES” thì loại hình kinh doanh là xe “du lịch”
hay xe chạy tuyến cố định…, hiệu xe “TRANSINCO” và có số ghế 45 chổ thì
thì loại hình kinh doanh là “xe bus” hay “xe chạy tuyến cố định”…
3.2. Ứng dụng lý thuyết tập thô, cài đặt và thử nghiệm
3.2.1. Giao diện của chương trình demo

Ứng dụng lý thuyết tập thô trong khai phá dữ liệu giao thông vận tải
Học viên thực hiện : - Đặng Thị Thanh Châu, CH1201005
- Bùi Văn Chương, CH1201092
- Mã Khánh Xuyên, CH1201149
Trang 19
Danh mục hiệu xe

Sau khi chuẩn hóa dữ liệu danh mục hiệu xe thì có tổng cộng 177 hiệu xe
Danh mục loại hình xe

Cơ sở dữ liệu có tổng cộng 6 loại hình xe
Danh mục xe

Cơ sở dữ liệu có tổng cộng 39285 xe ô tô các loại
Ứng dụng lý thuyết tập thô trong khai phá dữ liệu giao thông vận tải
Học viên thực hiện : - Đặng Thị Thanh Châu, CH1201005
- Bùi Văn Chương, CH1201092
- Mã Khánh Xuyên, CH1201149
Trang 20
Phân vùng tập thuộc tính quyết định {Loại hình xe}

Có tổng cộng: có tổng cộng 6 phân vùng tương ứng với 6 loại hình xe.
Phân vùng tập điều kiện 1 {hiệu xe}


Có tổng cộng: 177 phân vùng tương ứng với 177 hiệu xe.
Phân vùng tập điều kiện 2 {hiệu xe, số ghế}

Có tổng cộng 802 phân vùng tương ứng với từng hiệu xe và từng số ghế.
Ứng dụng lý thuyết tập thô trong khai phá dữ liệu giao thông vận tải
Học viên thực hiện : - Đặng Thị Thanh Châu, CH1201005
- Bùi Văn Chương, CH1201092
- Mã Khánh Xuyên, CH1201149
Trang 21
Tập luật phát sinh thỏa độ tin cậy và độ hỗ trợ

Kết quả đối với tập thuộc tính điều kiện {Hiệu xe} và tập thuộc tính quyết
định{Loại hình xe}

Kết quả đối với tập thuộc tính điều kiện {Hiệu xe},{Số ghế} và tập thuộc tính
quyết định{Loại hình xe}
3.2.2. Một số source code minh họa:
Để nâng cao hiệu quả của việc truy xuất cơ sở dữ liệu, với một số lượng
record tương đối lớn, ta cài đặt các hàm truy xuất dữ liệu bằng các script ngôn
ngữ SQL như sau:
Ứng dụng lý thuyết tập thô trong khai phá dữ liệu giao thông vận tải
Học viên thực hiện : - Đặng Thị Thanh Châu, CH1201005
- Bùi Văn Chương, CH1201092
- Mã Khánh Xuyên, CH1201149
Trang 22
Procedure dùng để phân vùng tập thuộc tính quyết định{Loại hình xe}
create PROCEDURE [dbo].[CaoHoc_TapQuyeDinh]
AS
select distinct TenLoaiHinhXe,x.LoaiHinhXeID

from VTDB_XE x
left join VTDB_DM_LOAIHINHXE lhx on
lhx.LoaiHinhXeID=x.LoaiHinhXeID
where x.HieuXeID is not null and X.LoaiHinhXeID is not null and
x.SoGhe>0and TenLoaiHinhXe is not null
declare @LoaiHinhXeID varchar(50)
declare @TenLoaiHinhXe nvarchar(100)
DECLARE pCurD CURSOR LOCAL
FOR select distinct TenLoaiHinhXe,x.LoaiHinhXeID
from VTDB_XE x
left join VTDB_DM_LOAIHINHXE lhx on
lhx.LoaiHinhXeID=x.LoaiHinhXeID
where x.HieuXeID is not null and X.LoaiHinhXeID is not null and
x.SoGhe>0 and TenLoaiHinhXe is not null
phân vùng tập vũ trụ U thành các tập Y1,Y2 tương ứng
với tập D
OPEN pCurD
FETCH NEXT FROM pCurD INTO @TenLoaiHinhXe,@LoaiHinhXeID
WHILE @@FETCH_STATUS = 0
BEGIN
select x.BienSoXe,TenLoaiHinhXe
from VTDB_XE x
left join VTDB_DM_LOAIHINHXE lhx on
lhx.LoaiHinhXeID=x.LoaiHinhXeID
where x.LoaiHinhXeID=@LoaiHinhXeID
FETCH NEXT FROM pCurD INTO @TenLoaiHinhXe,@LoaiHinhXeID
END
CLOSE pCurD
DEALLOCATE pCurD


Procedure dùng để phân vùng tập thuộc tính điều kiện{Hiệu xe}
create PROCEDURE [dbo].[CaoHoc_TapDieuKien1]
AS
select distinct TenHieuXe, x.HieuXeId
from VTDB_XE x
left join VTDB_DM_HIEUXE hx on hx.HieuXeID=x.HieuXeID
where x.HieuXeID is not null and X.LoaiHinhXeID is not null and
x.SoGhe>0 and TenHieuXe is not null
declare @HieuXeID varchar(50)
declare @TenHieuXe nvarchar(100)
DECLARE pCurHX CURSOR LOCAL
FOR select distinct TenHieuXe, x.HieuXeId
from VTDB_XE x
left join VTDB_DM_HIEUXE hx on
hx.HieuXeID=x.HieuXeID
where x.HieuXeID is not null and X.LoaiHinhXeID is not null and
x.SoGhe>0 and TenHieuXe is not null
OPEN pCurHX
FETCH NEXT FROM pCurHX INTO @TenHieuXe,@HieuXeID
WHILE @@FETCH_STATUS = 0
BEGIN
select x.BienSoXe,TenHieuXe
from VTDB_XE x
left join VTDB_DM_HIEUXE hx on hx.HieuXeID=x.HieuXeID
where x.HieuXeID=@HieuXeID
FETCH NEXT FROM pCurHX INTO @TenHieuXe,@HieuXeID
Ứng dụng lý thuyết tập thô trong khai phá dữ liệu giao thông vận tải
Học viên thực hiện : - Đặng Thị Thanh Châu, CH1201005
- Bùi Văn Chương, CH1201092
- Mã Khánh Xuyên, CH1201149

Trang 23
END
CLOSE pCurHX
DEALLOCATE pCurHX

Source code visual basic.net minh họa phép toán giao giữa 2 tập hợp:

For i As Integer = 1 To dsQuyetDinh.Tables(0).Rows.Count - 1
Dim contactTable As DataTable = dsQuyetDinh.Tables(i)
For j As Integer = 1 To dsDieuKien1.Tables(0).Rows.Count
- 1
Dim contacts = contactTable.AsEnumerable.
Intersect(dsDieuKien1.Tables(j).AsEnumerable(),DataRowComparer.Defau
lt) 'tìm thấy luật
If contacts.Count > 0 Then
Dim dsSC As DataSet
dsSC = DataProder.ExecuteQuery("CaoHoc_DoHoTro " & "N'" &
dsDieuKien1.Tables(0).Rows(j - 1).Item("TenHieuXe") & "',N'" &
dsQuyetDinh.Tables(0).Rows(i - 1).Item("TenLoaiHinhXe") & "'")
If CInt(dsSC.Tables(0).Rows(0).Item("S")) >= CInt(txtDoPB.Text) And
CInt(dsSC.Tables(1).Rows(0).Item("C")) >= CInt(txtDoTC.Text) Then
Dim lvi As New ListViewItem
tempValue = tempValue + 1
lvi.Text = tempValue
Dim strLuat As String = "Nếu hiệu xe là " &
dsDieuKien1.Tables(0).Rows(j - 1).Item("TenHieuXe") & " thì loại
hình xe là " & dsQuyetDinh.Tables(0).Rows(i -
1).Item("TenLoaiHinhXe")
lvi.SubItems.Add(strLuat)
lvi.SubItems.Add(dsSC.Tables(0).Rows(0).Item("S") "%")

lvi.SubItems.Add(dsSC.Tables(1).Rows(0).Item("C") & "%")
lvLuatKetHop.Items.Add(lvi)
End If
End If


3.3. Kết luận:
Đề tài nghiên cứu về lý thuyết tập thô và ứng dụng của nó trong lĩnh vực giao
thông vận tải với mục đích xây dựng chương trình tạo luật cho hệ chuyên gia
trong việc hỗ trợ thông tin đăng ký cho các doanh nghiệp vận tải.
Tiếp tục tìm hiểu và nghiên cứu sâu hơn về lý thuyết tập thô như các kỹ thuật
đánh giá luật nhằm tìm ra những tri thức thật sự có ý nghĩa, tiếp tục tiền xử lý và
thu thập các dữ liệu về giao thông để có thể áp dụng vào thực tế.



Ứng dụng lý thuyết tập thô trong khai phá dữ liệu giao thông vận tải
Học viên thực hiện : - Đặng Thị Thanh Châu, CH1201005
- Bùi Văn Chương, CH1201092
- Mã Khánh Xuyên, CH1201149
Trang 24
TÀI LIỆU THAM KHẢO

[1]. TS. Dương Tôn Đảm, Bài giảng cao học môn Toán chung, ĐHCNTT-
TPHCM.
[2]. GS.TSKH Hoàng Kiếm, TS. Đỗ Văn Nhơn, Th.sĩ Đỗ Phúc. Giáo trình
Các hệ cơ sở tri thức, đại học Quốc gia TPHCM – 2002.
[3]. GS.TSKH Hoàng Kiếm, Bài giảng cao học môn học Công nghệ tri thức
và Ứng dụng, ĐHKHTN-TPHCM.
[4]. Alex Berson Stephen J. Smith, Data Warehousing, Data Mining, and

Olap.
[5]. Grzymala-Busse, Jerzy W. "Rule induction." Data Mining and
Knowledge Discovery Handbook, Springer US, 2010. 249-265.
[6]. Data Mining and Business Intelligence,