ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CHƯƠNG TRÌNH ĐÀO TẠO THẠC SĨ CNTT QUA MẠNG

BÀI THU HOẠCH
MÔN CÔNG NGHỆ TRI THỨC VÀ ỨNG DỤNG
TÌM HIỂU VÀ ỨNG DỤNG LÝ THUYẾT TẬP THÔ
TRONG KHAI THÁC DỮ LIỆU GIAO THÔNG VẬN TẢI
GIẢNG VIÊN HƯỚNG DẪN
GS.TSKH HOÀNG KIẾM
HỌC VIÊN THỰC HIỆN
NGUYỄN SỬ VIỆT
MSHV: CH1101156
TPHCM 05-2012
MỤC LỤC

2/21
Công nghệ tri thức và ứng dụng – Học Viện: Nguyễn Sử Việt
Xác định bài toán
Thu thập và ền xử lý dữ liệu
KHAI PHÁ DỮ LIỆU
Chiết xuất tri thức
Phát biểu kết quả và đánh giá
Chiết xuất tri thức
Sử dụng tri thức đã phát hiện
Chiết xuất tri thức
Chương 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU
1.1. Khai phá dữ liệu
Khai phá dữ liệu, phát hiện tri thức(data mining) trong cơ sở dữ liệu là quá trình tìm
kiếm và rút trích những thông tin tiềm ẩn có giá trị và hữu ích từ các tập cơ sở dữ liệu
lớn. Việc rút trích các tri thức này sẽ giúp cho các doanh nghiệp, công ty…, có thể

- Làm sạch dữ liệu (data cleaning/cleansing): làm sạch dữ liệu là vấn đề bậc
nhất của nhà kho dữ liệu, quá trình làm sạch bao gồm các bước như sau:
o Điền các giá trị còn thiếu tự động: việc điền các giá trị bằng tay là vô vị
và không thể thực hiện, vì vậy các giá trị còn thiếu có thể được điền 1
cách tự động, giá trị thiếu có thể thay bằng :
 Hằng số chung, ví dụ: “không biết”, 0
 Thay thế bằng giá trị trung bình của thuộc tính trong một lớp
 Thay thế bằng giá trị có nhiều khả năng nhất, suy ra từ công thức
Bayesian, cây quyết định hoặc thuật giải.
o Các phương pháp cơ bản khử nhiễu:
 Phương pháp chia giỏ(binning): sắp xếp và chia dữ liệu vào các
giỏ cùng độ sâu, khử nhiễu bằng giá trị trung bình, trung tuyến,
biên giỏ…
4/21
Công nghệ tri thức và ứng dụng – Học Viện: Nguyễn Sử Việt
 Gom nhóm(Clustering): phát hiện và loại bỏ các khác biệt
 Kết hợp sự kiểm tra giữa máy tính và con
người(computer/human inspection): Phát hiện giá trị nghi ngờ và
kiểm tra bởi con người.
 Phương pháp hồi qui(Regression): đưa dữ liệu vào hàm hồi qui.
- Chọn lọc, tích hợp dữ liệu (data integration): trộn dữ liệu (merge data) từ
nhiều nguồn, tập tin khác nhau vào một kho dữ liệu, chọn lọc những dữ liệu
thật sự cần thiết cho tiến trình khai thác dữ liệu. Quá trình chọn lọc bao gồm
các bước sau:
o Sơ đồ tập hợp dữ liệu:
 Làm thế nào để các thực thể từ nhiều nguồn dữ liệu trở nên
tương xứng, ví dụ: US=USA, MSNV=MaNhanVien,…
o Loại bỏ dữ liệu dư thừa, trùng lắp:
 Một thuộc tính là thừa nếu có thể suy ra từ các thuộc tính khác
 Cùng một thuộc tính có thể có nhiều tên trong CSDL khác nhau

liệu có được và tách ra các tri thức cần thiết.
1.2.4. Phát biểu kết quả và đánh giá tri thức
Do nhiều phương pháp khai thác có thể được áp dụng nên các kết quả có mức độ tốt,
xấu khác nhau. Việc đánh giá các kết quả thu được là cần thiêt, Các tri thức phát
hiện từ cơ sở dữ liệu cần được tổng hợp dưới dạng các báo cáo phục vụ cho các mục
đích hỗ trợ các quyết định khác nhau.
1.2.5. Sử dụng tri thức đã phát hiện
Củng cố, tinh chế các tri thức đã được phát hiện. Kết hợp các tri thức thành hệ
thống. Giải quyết các xung đột tiềm tàng trong tri thức khai thác được. Sau đó tri
thức được chuẩn bị sẵn sàng cho ứng dụng.
Các kết quả của quá trình phát hiện tri thức có thể được đưa vào ứng dụng trong
những lĩnh vực khác nhau. Do các kết quả có thể là các dự báo hoặc các mô tả
nên chúng có thể được đưa vào các hệ thống hỗ trợ ra quyết định nhằm tự động
hoá quá trình này.
1.3. Luật kết hợp
1.3.1. Khái niệm
Luật kết hợp là một trong những lĩnh vực quan trọng trong khai phá dữ liệu, là
một trong những kỹ thuật mới và là chủ đề hấp dẫn. Khám phá và phát hiện ra
các luật kết hợp nhằm tìm ra các mối liên quan giữa các thành phần(item) trong
dữ liệu. Chẳng hạn như khi phân tích cơ sở dữ liệu giao thông, ta có thể phát hiện
ra một qui luật như: “các xe có số ghế lớn hơn 45 chổ thường chạy tuyến cố
định” hay “ các xe chạy tuyến Nha Trang thì chạy tuyến Phan Thiết”…
1.3.2. Một số vấn đề liên quan đến luật kết hợp.
6/21
Công nghệ tri thức và ứng dụng – Học Viện: Nguyễn Sử Việt
Chúng ta sẽ không quan tâm đến tất cả các kết hợp giữa các item có thể có trong
cơ sở dữ liệu, mà chúng ta chỉ quan tâm đến những luật kết hợp có ý nghĩa và xác
thực.
Để hạn chế việc phát sinh quá nhiều các luật không có ý nghĩa, người ta đề nghị
sử dụng các thước đo tiêu chuẩn cho 1 luật kết hợp đó là độ hỗ trợ(support) và độ

0 0 0 0
T
2
1 1 1 1
T
3
1 0 1 0
Ta gọi một giao tác T chứa X nếu X⊆T với X là tập 1 vài item trong I
Ta có luật kết hợp: X ⇒ Y, nếu X ⊂ I , Y ⊂ I và X∩Y = ∅
1.3.2.1. Độ hỗ trợ(Support)
Độ hỗ trợ của luật X ⇒ Y được định nghĩa là số bộ giá trị chứa cả X và Y:
Supp(X ⇒ Y)=P(X∪Y)
Các luật kết hợp có độ hỗ trợ càng cao(xuất hiện nhiều) được gọi là phổ biến
và quan trọng.
1.3.2.2. Độ tin cậy(Confidence)
Độ tin cậy của luật X ⇒ Y được định nghĩa:
Conf(X ⇒ Y)=
Các luật có độ tin cậy càng cao thì càng hiểu ích
1.3.2.3. Ví dụ về độ hỗ trợ và độ tin cậy
7/21
Công nghệ tri thức và ứng dụng – Học Viện: Nguyễn Sử Việt
8/21
Công nghệ tri thức và ứng dụng – Học Viện: Nguyễn Sử Việt
Chương 2. TÌM HIỂU LÝ THUYẾT VỀ TẬP THÔ
2.1. Nội dung
Lý thuyết tập thô được Zdzislaw Pawlak phát triển vào năm 1980-1992 và được áp
dụng trên mô hình cơ sở dữ liệu quan hệ. Hiện nay lý thuyết tập thô được nhiều nhà khoa
học nghiên cứu và áp dụng và nhiều lĩnh vực khác nhau như: khai thác dữ liệu, hệ chuyên
gia, hệ hỗ trợ ra quyết định, máy học, nhận dạng…
Trong thực tế, dữ liệu lưu trữ thường không đầy đủ, dư thừa hoặc không chính xác,

D
X
1
X
2
X
3
X
4
X
5
X
6
X
7
X
8
X
9
X
1
0
0
0
0
1
1
1
1
2

Các thuộc tính điều
kiện
Các thuộc tính
quyết định
U C1 C2 D
X1
X2
X3
X4
0
0
0
1
L
H
H
L
0
0
0
0
10/21
Công nghệ tri thức và ứng dụng – Học Viện: Nguyễn Sử Việt
U = {x
1
, x
2
, , x
10
}

X9
X10
1
1
1
2
2
2
L
H
H
L
L
H
1
1
1
0
1
1
2.3. Quan hệ tương đương
Cho A ⊆ Q
IND(A) ={(x, y) ∈ U × U | ∀a ∈ A
f(x, a) = f(y, a)}
IND(A): Quan hệ tương đương trên tập A Hai đối tượng x, y tương đương trên tập
thuộc tính A.
Ví dụ về quan hệ tương đương:
ST
T
Age LEMS Walk

1
,X
2
,…X
r
}
Tập quyết định D
*
xác định từ tập U: D
*
={Y
1
,Y
2
,…Y
l
}
Mỗi lớp Yi(i=1,2, l) xác định luật quyết định, luật quyết định thứ i được biểu diễn
Phát biểu dưới dạng logic như sau:
Nếu (tập điều kiện) thì (tập quyết định)
Tập luật quyết định trên các lớp Y
j

∈
D
*
với (j=1,2,…,l), ký hiệu:
12/21
Công nghệ tri thức và ứng dụng – Học Viện: Nguyễn Sử Việt
A-xấp xỉ dưới AX = {x |

={x
2
, x
3
, x
4
, x
7
, x
8
}
Des
D
(Y
1
)= (d= Tốt)
Des
D
(Y
2
)= (d= Xấu
Tập thuộc tính điều kiện A={Động cơ}
Phân vùng U trên quan hệ tương đương IND(A) là:
A
*
=U/IND(A)={{x
1
},{x
2
, x

Luật quyết định:
Nếu (Động cơ= propane) thì (d=Tốt)
Nếu (Động cơ= propane) thì (d=Tốt)
13/21
Công nghệ tri thức và ứng dụng – Học Viện: Nguyễn Sử Việt
Luật quyết định dựa trên lớp Y
2
với quyết định của chuyên gia là Xấu:
Luật quyết định:
Nếu (Động cơ= diesel) thì (d=Xấu)
Nếu (Động cơ= gasoline) thì (d=Xấu)
Nếu Tập thuộc tính quyết định:
D= {d}, V
d
= {Tốt, Xấu}
Tập thuộc tính điều kiện:
A= {Động cơ, Kích thước}.
Thì:
L1: Nếu (ĐC=propane) và (KT=nhỏ) thì (d=Tốt)
L2: Nếu (ĐC=gasoline) và (KT=nhỏ) thì (d=Tốt)
L3: Nếu (ĐC=gasoline) và (KT=trung) thì (d=Tốt)
L4: Nếu (ĐC=diesel) và (KT=trung) thì (d=Xấu)
L5: Nếu (ĐC=diesel) và (KT=lớn) thì (d=Xấu)
L6: Nếu (ĐC=gasoline) và (KT=nhỏ) thì (d=Xấu)
L7: Nếu (ĐC=gasoline) và (KT=lớn) thì (d=Xấu)
Chương 3. ỨNG DỤNG KHAI THÁC DỮ LIỆU GIAO THÔNG VẬN TẢI
.1. Thông tin về dự án quản lý hổ sơ ISO tại Sở GTVT TPHCM
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

1 HieuXeID varchar(20) Khóa chính table
2 MaHieuXe nvarchar(50) Mã hiệu xe
3 TenHieuXe nvarchar(200) Tên hiệu xe
4 MoTa nvarchar(1000
)
Thông tin mô tả hiệu xe
5 Active char(1) Cho biết hiệu xe còn sử dụng
hay không?
VTDB_DM_LOAIHINHXE: Lưu thông tin về các loại hình kinh doanh như:
xe bus, xe du lịch, xe taxi, xe chạy tuyến cố định,…
Danh sách các cột
ST
T
Tên cột Kiểu dữ liệu Mô tả
1 LoaiHinhXeID varchar(20) Khóa chính table
2 MaLoaiHinhXe nvarchar(50) Mã loại hình xe
3 TenLoaiHinhXe nvarchar(200) Tên loại hình xe
4 MoTa nvarchar(1000
)
Thông tin mô tả loại hình
5 Active char(1) Cho biết loại hình xe còn sử
dụng hay không?
6 LoaiHinhKinhDoanhI
D
varchar(20) Khóa ngoại cho biết xe thuộc
loại hình kinh doanh gì?
VTDB_XE: Lưu trữ thông tin về các xe đã đăng ký với sở, các thông tin bao
gồm: biển số xe, hiệu xe, số ghế, năm sản xuất, tên đăng ký, tên đơn vị, loại
hình kinh doanh,…
ST

Cùng một hiệu xe “Sài Gòn Bus” nhưng có rất nhiều tên gần giống với
nhau như: “SAI GON BUS”, “SÀI GÒN BUS”, “SÀI GÒN-BUS”,
“SÀIGÒNBUS”, ” SAIGONBUS”,…
Mã hóa dữ liệu: xét dữ liệu danh mục các xe ô tô ta thấy số chổ của xe
có các giá trị từ 2 đến 80. Giả sử ta chỉ quan tâm đến các xe có số ghế
như sau:
STT Số ghế Giá trị mã hóa
1 <=4 chổ 1
2 Từ 5 đến 7 chổ 2
3 Từ 8 đến 16 chổ 3
4 Từ 17 đến 30 chổ 4
5 Từ 31 đến 80 chổ 5
Việc mã hóa phải được thực hiện bằng cách tự động bằng cách thực hiện
các scritp SQL server như sau:
Ví dụ: mã hóa các xe có số ghế<=4, giá trị mã hóa được lưu vào cột
“MaHoaSoGhe”
update VTDB_XE
set MaHoaSoGhe=1
where SoGhe is not null and SoGhe>0 and SoGhe<=4
Làm tương tự các giá trị mã hóa còn lại: 2,3,4,5
3.3.2. Ứng dụng lý thuyết tập thô, cài đặt và thử nghiệm
17/21
Công nghệ tri thức và ứng dụng – Học Viện: Nguyễn Sử Việt
Giao diện trang chính của chương trình demo
Danh mục hiệu xe
Sau khi chuẩn hóa dữ liệu danh mục hiệu xe thì cơ sở dữ liệu 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

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)

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
Next
Next
20/21

[4].Bài giảng môn khai thác dữ liệu(datamining) của PGS.TS Đỗ Phúc, trường ĐH
CNTT TPHCM.
21/21
Công nghệ tri thức và ứng dụng – Học Viện: Nguyễn Sử Việt