ĐẠI HỌC QUỐC GIA TP.HCM
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN

ĐỒ ÁN MÔN HỌC TOÁN CHO MÁY TÍNH
XÂY DỰNG MÔ HÌNH DỰ BÁO SỐ LƯỢNG
THÍ SINH TRÚNG TUYỂN NHẬP HỌC
TRONG KỲ THI TUYỂN SINH
ĐẠI HỌC, CAO ĐẲNG
GVHD: TS. Dương Tôn Đảm
HVTH: Lê Thành Nguyên
MSHV: CH1301102
Lớp : Cao học Khóa 8

TP HCM, Tháng 11 năm 2014


3.1.5.

Tập xấp xỉ 6

3.1.6.

Rút gọn (Reduction) và lõi (Core) 7

3.1.7.

Ma trận phân biệt 8

3.2.CÂY QUYẾT ĐỊNH 9

3.2.1.

Giới thiệu 9

3.2.2.

Ưu điểm 10

3.2.2.

Entropy 11

3.2.3.

Information Gain 11


PHẦN 4: XÂY DỰNG MÔ HÌNH DỰ BÁO 29

4.1. DỮ LIỆU 29

4.2. GIẢI PHÁP 29

4.2.1.

Xếp hạng dữ liệu 30

ii

4.2.2.

Phân tích hồi quy 31

4.2.3.

Xây dựng mô hình dự báo cây quyết định 32

4.2.4.

Xây dựng mô hình dự báo dựa trên lý thuyết tập thô 32

TÀI LIỆU THAM KHẢO 34


Hình 14. Cấu trúc chung của quá trình học 28

Hình 15. Quy trình xây dựng mô hình dự báo 32

GVHD: TS. Dương Tôn Đảm HVTH: Lê Thành Nguyên

Trang 1

PHẦN 1: MỞ ĐẦU
Khai phá dữ liệu là một lĩnh vực khoa học liên ngành đang phát triển và dần hoàn
thiện cơ sở lý thuyết trong nhiều lĩnh vực nhằm khám phá các tri thức trong các cơ sở dữ
liệu lớn, trích xuất những thông tin ẩn dưới dạng các quy luật, ràng buộc, quy tắc hữu ích
cho các tổ chức, doanh nghiệp,… Các kỹ thuật được sử dụng trong khai phá dữ liệu bao
gồm: phân lớp và dự đoán, phân cụm, luật kết hợp, phân tích hồi quy và phân tích các
mẫu theo thời gian. Hiện nay, các kỹ thuật khai phá dữ liệu được ứng dụng rộng rãi trong
các lĩnh vực phân tích dữ liệu hỗ trợ ra quyết định trong điều trị y học, giáo dục, thương
mại, tài chính,… Trong số đó, lý thuyết tập thô đang được nghiên cứu và phát triển với
các khả năng ứng dụng trong nhiều lĩnh vực đặc biệt trong phân tích dữ liệu, tri thức
không đầy đủ.
Nước ta đang thực hiện công cuộc công nghiệp hóa hiện đại hóa nhằm thúc đẩy
nền kinh tế phát triển mạnh mẽ. Trong quá trình này, vai trò nền tảng của giáo dục, đặc
biệt là giáo dục Đại học đã được xã hội ghi nhận và phát huy. Vì vai trò quan trọng của
giáo dục Đại học đối với xã hội, các cơ quan quản lý đã quy định các tiêu chuẩn đảm bảo
chất lượng giáo dục trong luật giáo dục Đại học và nhiều văn bản ngang luật. Trong số
đó, quy mô đào tạo và chỉ tiêu tuyển sinh ở từng trường được quy định chặt chẽ.
Tuy nhiên, như chúng ta đã biết, hằng năm, trong kỳ thi tuyển sinh Đại học và Cao
đẳng các trường phải đối mặt với vấn đề số lượng thí sinh ảo và trúng tuyển ảo. Vấn đề
đặt ra cho các trường là xác định giá trị ảo. Từ đó, xác định số lượng thí sinh trúng tuyển
nhập học tương xứng với chỉ tiêu tuyển sinh đã được quy định trước đó là vấn đề nan giải
ở đại bộ phận các trường Đại học và Cao đẳng trong cả nước. Vì lý do đó, tác giả thực

này sẽ xem như bất khả thi nếu không có công cụ phân tích dữ liệu.

GVHD: TS. Dương Tôn Đảm HVTH: Lê Thành Nguyên

Trang 3

PHẦN 3: KHAI PHÁ DỮ LIỆU
3.1. TẬP THÔ
3.1.1. Giới thiệu
Lý thuyết tập thô (Rough set) được đề xuất vào năm 1980 bởi Z.Pawlak. Lý thuyết
này xây dựng phương pháp luận liên quan đến sự phân loại và phân tích không chắc chắn
thông tin và tri thức không đầy đủ. Khái niệm cơ bản của lý thuyết tập thô là xấp xỉ dưới
và trên của một tập, sự xấp xỉ của không gian là hình thức phân loại tri thức liên quan đến
miền dữ liệu quan tâm. Tập con được tạo ra bởi xấp xỉ dưới mô tả bởi các đối tượng là
những thành phần chắc chắn của một tập, trong khi xấp xỉ trên được đặc trưng bởi các đối
tượng có khả năng thuộc tập quan tâm.
Trong nhiều trường hợp trong khai phá dữ liệu, dữ liệu được sử dụng thường
không hoàn thiện, các giá trị không xác định hoặc lỗi trong quá trình thu thập, tổng hợp
dữ liệu. Lý thuyết tập thô phát huy tác dụng cho các trường hợp này vì nó là công cụ
nhằm giải quyết sự gần đúng và các trường hợp quyết định không chắc chắn. Một ưu
điểm của lý thuyết tập thô đối với hướng tiếp cận xác suất Bayes là không cần giả định về
sự độc lập của các thuộc tính cũng như không cần bất kỳ kiến thức nền nào về dữ liệu.
Gần đây, lý thuyết tập thô trở thành một công cụ đánh giá trong xử lý các vấn đề
khác nhau như trình bày tri thức không chắc chắn hoặc không chính xác, phân tích tri
thức, đánh giá chất lượng và tính khả dụng của thông tin đối với tính nhất quán và sự có
mặt các mẫu không theo thời gian, nhận dạng và đánh giá sự phụ thuộc thời gian, suy
luận.
Lý thuyết tập thô dựa trên giả thuyế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ụ.
Trong nội dụng tiếp theo sẽ trình bày các khái niệm cơ bản của tập thô như sau:

i
), với
mọi i =1, 2, , k.
Một hệ thông tin bao gồm 8 đối tượng U={u1,u2,u3,u4,u5,u6,u7,u8}, tập thuộc
tính A={Color, Size }, và miền giá trị cho từng thuộc tính là IColor = {Green, Yellow,
Red}, ISize = {Small, Medium, Big }
ID Color Size
U1 Green Big
U2 Green Small
U3 Yellow Medium
U4 Red Medium
U5 Yellow Medium
U6 Green Big
U7 Red Small
U8 Red Small
Bảng 1: Hệ thông tin
GVHD: TS. Dương Tôn Đảm HVTH: Lê Thành Nguyên

Trang 5

3.1.3. Bảng quyết định
Bảng quyết định là một hệ thống thông tin có dạng T=(U,A),với U là tập các đối
tượng và A là tập các thuộc tính, trong đó tập thuộc tính A được chia thành 2 tập thuộc
tính rời nhau là C và D, C được gọi là tập thuộc tính điều kiện và D là tập thuộc tính
quyết định. Tức là T = (U, C, U, D).
Ví dụ: Bảng sau đây là một bảng quyết định. Bảng này có 8 đối tượng như trong
bảng 1, nhưng có thêm thuộc tính quyết định (Shape). Trong bài toán phân lớp thì thuộc
tính quyết định chính là lớp của đối tượng cần xếp lớp. Trong ví dụ này thuộc tính quyết
định Shape có 3 giá trị là Circle, Square và Triangle.
ID Color Size Shape (D)

hệ R với x.
Xét hệ thông tin S = (U, A), với mỗi tập thuộc tính B  A tạo ra một quan hệ hai
ngôi trên U, ký hiệu IND(B):
IND(B) = {( u, v)  U2 | a  B, a(u) = a(v)}
IND(B) được gọi là quan hệ bất khả phân biệt theo B. Dễ kiểm chứng đây là một
quan hệ tương đương trên U. Với mọi đối tượng u  U, lớp tương đương của u trong
quan hệ IND(B) được kí hiệu bởi [u]
B
.
Ví dụ: Tập thuộc tính B= {Color, Size} trong Bảng 2 phân hoạch tập 8 đối tượng
thành tập các lớp tương đương như sau:
IND(B) = {(u1, u6), (u2), (u3, u5), (u4), (u6, u7)}
Nhận xét: Ta thấy, các đối tượng u1và u6 cùng một lớp tương đương nên chúng
không thể phân biệt với nhau trên tập thuộc tính {Color, Size }.
3.1.5. Tập xấp xỉ
Một quan hệ tương đương dẫn đến một phân hoạch phổ quát U. Có thể dùng phép
phân hoạch để tạo các tập con mới của tập phổ quát. Các tập con thường được quan tâm
là các tập con có cùng giá trị của thuộc tính quyết định.
Cho một hệ thông tin S = (U, A), với mỗi tập con X  U và B  A,
Ký hiệu R = IND(B), ta có 2 tập con sau :
BX = { x | [x]
B
 X }
và 

=
{

|
[]

Trong trường hợp BN
B
(X)  , X được gọi là tập thô, ngược lại X được gọi là tập
rõ.
Ví dụ: Xét hệ thống thông tin biểu diễn các triệu chứng của cảm cúm như sau:
ID Đau đầu Thân nhiệt Cảm cúm
U1 Có Bình thường

Không
U2 Có Cao Có
U3 Có Rất Cao Có
U4 Không Bình thường

Không
U5 Không Cao Không
U6 Không Rất Cao Có
U7 Không Cao Có
U8 Không Rất Cao Không
Bảng 3: Triệu chứng cảm cúm
Từ hệ thống thông tin trên, ta có các lớp không phân biệt được B={Đau đầu, Thân
Nhiệt} là {u1},{u2},{u3},{u4},{u5,u7},{u6,u8}.
Nếu đặt V={u|u(Cảm cúm)=Có}={u2,u3,u6,u7}, lúc đó ta có:
BV= {u2,u3} và 

= {u2,u3,u5,u7,u6,u8}.
Từ đó ta có B-miền biên của V là tập 

(

)

Trong đó RED(C) là tập hợp tất cả các rút gọn của C.
Ví dụ: Cho bảng quyết định về bệnh cúm như bảng bảng 4
ID Đau đầu Đau cơ Thân nhiệt Cảm cúm
U1 Có Có Bình thường Không
U2 Có Có Cao Có
U3 Có Có Rất Cao Có
U4 Không Có Bình thường Không
U5 Không Không Cao Không
U6 Không Có Rất Cao Có
Bảng 4: Bảng quyết định về bệnh cúm
Bảng này có 2 tập rút gọn là R1={Đau đầu, Thân nhiệt} và R2= {Đau cơ, Thân
nhiệt}. Tập lõi Core={Thân nhiệt}. Vậy Thân nhiệt là thuộc tính cần thiết duy nhất, các
thuộc tính Đau đầu, Đau cơ đều không cần thiết. Điều này có nghĩa rằng có thể loại bỏ 1
trong 2 thuộc tính Đau đầu hoặc Đau cơ (không thể bỏ đồng thời cả 2) mà không ảnh
hưởng đến kết quả chuẩn đoán bệnh.
3.1.7. Ma trận phân biệt
Với S là một hệ thông tin với n đối tượng, ma trận phân biệt của S là một ma trận
đối xứng n x n với các giá trị m
ij
được định nghĩa như sau:


=

{
∈
|


(

Ma trận phân biệt không chỉ được định nghĩa trên tập tất cả các thuộc tính của hệ
thông tin mà còn có thể được xây dựng trên một tập thuộc tính B  A bất kỳ. Trong
trường hợp đó, phần tử m
ij
là tập các thuộc tính trong B phân biệt hai đối tượng x
i
, x
j
Xét ma trận phân biệt được xây dựng trên tập thuộc tính B  A. Giả sử tập thuộc
tính B phân hoạch tập đối tượng thành các lớp tương đương X
1
, X
2
,…, X
k
và do hai đối
GVHD: TS. Dương Tôn Đảm HVTH: Lê Thành Nguyên

Trang 9

tượng thuộc một lớp tương đương thì nhận giá trị như nhau tại các thuộc tính trong B nên
thay vì xây dựng ma trận phân biệt giữa từng cặp đối tượng, ta xây dựng ma trận phân
biệt giữa từng cặp lớp tương đương.
Khi đó, phần tử c
ij
, i, j  {1,2, …,k} là tập hợp thuộc tính phân biệt hai đối
tượng bất kỳ thuộc hai lớp tương đương X
i
và X
j

được nữa, hay khi một phân loại đơn có thể áp dụng cho từng phần tử của tập con dẫn
xuất. Cây quyết định là một phương tiện có tính mô tả dành cho việc tính toán các xác
suất có điều kiện. Cây quyết định có thể được mô tả như là sự kết hợp của các kỹ thuật
toán học và tính toán nhằm hỗ trợ việc mô tả, phân loại và tổng quát hóa một tập dữ liệu
cho trước. Ra quyết định dựa trên cây quyết định là quá trình học trên tập dữ liệu huấn
luyện theo mô hình cây quyết định và được sử dụng trong dự đoán các mẫu dữ liệu trong
tương lai.
Cây quyết thông thường được xây dựng dựa trên tập dữ liệu mẫu (dữ liệu huấn
luyện) có kích thước đủ lớn có khả năng bao phủ các trường hợp đã xảy ra của biến mục
tiêu thông qua các thuật toán khai phá dữ liệu dựa trên bộ quy ước độ đo nhất định. Trong
nhiều trường hợp, cây quyết định được xây dựng dựa trên thuật toán ID3 với các độ đo
Entropy và Information Gain.
3.2.2. Ưu điểm
Khả năng sinh các quy tắc hiểu được: từ cây quyết có thể xây dựng các phương
pháp sinh ra các quy tắc có dạng luật dễ hiểu kể cả cho người dùng không có chuyên môn
toán học.
Cây quyết định có thể được hiển thị trực quan, việc xây dựng một đường đi từ nút
gốc đến nút lá là một điều kiện phân lớp cho dữ liệu. Do đó, sự giải thích cho bất cứ một
phân lớp hay dự đoán nào đều minh bạch, rõ ràng.
Khả năng xử lý biến đa dạng: các thuật toán xây dựng cây quyết định có khả năng
xử lý trên biến liên tục và biến rời rạc.
GVHD: TS. Dương Tôn Đảm HVTH: Lê Thành Nguyên

Trang 11

Thể hiện rõ ràng những thuộc tính tốt nhất: thuộc tính tốt nhất sẽ được thuật toán
xây dựng cây quyết định quan tâm đầu tiên và được chọn làm nút gốc.
3.2.2. Entropy
Entropy là đại lượng dùng để đo tính thuần nhất của một tập dữ liệu. Entropy của
một tập S được tính theo công thức sau:


)
=−



(

)
=()



Giá trị Gain của thuộc tính A trong tập S ký hiệu là Gain(S,A) và được tính theo
công thức sau:

(
,
)
=
(

)
−
(

)
=
(


định từ trên xuống. Giải thuật được trình bày trong đoạn mã bên dưới:
Function induce_tree(tập mẫu, tập_thuộc_tính)
begin
if mọi mẫu trong tập mẫu đều cùng một lớp then
return một nút lá được gán nhãn bởi lớp đó
else if tập_thuộc_tính là rỗng then
return nút lá được gán nhãn bởi tuyển của tất cả
các lớp trong tập_ví_dụ
else
begin
Tính giá trị gain cho tất cả các thuộc tính;
Chọn thuộc tính Ai có giá trị gain lớn nhất
xóa Ai ra khỏi tập_thuộc_tính;
với mỗi giá trị Vj của Ai
begin
Tạo một nhánh của cây gán nhãn Vj;
Đặt vào phân_vùngVj các ví dụ trong
tập_ví_dụ có giá trị Vj tại thuộc tính
Ai;
Gọi induce_tree(phân_vùngV,
tập_thuộc_tính), gắn kết quả vào nhánh V
;
end
end
end
3.2.5. Minh họa thuật toán ID3
Xét bài toán phân loại xem có đi cho tennis ứng với thời tiết nào đó không.
Giải thuật ID3 sẽ xây dựng cây quyết định từ tập mẫu sau:

GVHD: TS. Dương Tôn Đảm HVTH: Lê Thành Nguyên

entropy(S) = entropy(9+, 5-) = –p
+
log
2
p
+
– p
-
log
2
p
-

= –


log
2


–


log
2


= 0.94
 Values(quang cảnh) = {nắng, âm u, mưa}
S



entropy(S
mưa
)
Trong đó:
 Entropy(S) = 0.94
 Entropy(S
nắng
) = –


log
2


–


log
2


= 0.971
 Entropy(S
âm u
) = –


log


= 0.971
 gain(S,
quang cảnh
) = 0.246
 Values(nhiệt độ) = {nóng, ấm áp, mát}
S
nóng
= [2+, 2-]
S
ấm áp
= [4+, 2-]
S
mát
= [3+, 1-]
gain(S, nhiệt độ) = entropy(S) –
∑
|


|
|

|
(

)
∈{ó,ấá,á}

= entropy(S) –


log
2


= 1
 Entropy(S
ấm áp
) = –


log
2


–


log
2


= 0.9178
 Entropy(S
mát
) = –


log
2

gain(S, gió) = 0.048
Ta thu được kết quả:
gain(S, quang cảnh) = 0.246
gain(S, nhiệt độ) = 0.029
gain(S, độ ẩm) = 0.151
gain(S, gió) = 0.048
Ta thấy giá trị gain(S, quang cảnh) lớn nhất nên quang cảnh được chọn làm nút
gốc.
Sau khi lập được cấp đầu tiên của cây quyết đinh ta xét nhánh nắng, tiếp tục lấy
entropy và gain cho nhánh nắng ta có:
Gain(S
nắng
, độ ẩm) = 0.97
Gain(S
nắng
, nhiệt độ) = 0.57
Gain(S
nắng
, gió) = 0.019
Như vậy, thuộc tính độ ẩm có tác động phân loại cao nhất trong nhánh nắng. Do
đó, thuộc tính độ ẩm sẽ được chọn là nút tiếp theo. Thực hiện tiếp tục ta sẽ được cây
quyết định đầy đủ thể hiện khả năng phân lớp của từng thuộc tính trên tập dữ liệu.
GVHD: TS. Dương Tôn Đảm HVTH: Lê Thành Nguyên

Trang 16 Hình 2. Cây quyết định được tạo ra bởi thuật toán ID3

Các luật được rút ra từ cây quyết định:


Hình 3. Cấu tạo của neural sinh học
Các thành phần chính của Neural:
 Khớp kết nối(Synapse): kết nối các Neural nhờ các tính chất hoá lý.
 Xúctu(dendrites): Thu nhận thông tin về nhân qua khớp.
 Thân tế bào: tổng hợp tín hiệu và khi đủ mạnh thì có tín hiệu ra ở trục cảm ứng
và nổ lúc đó gọi là cháy.
 Trục cảm ứng(Axon): đưa tín hiệu ra và truyền tới các Neural khác qua các
khớp kết nối.
3.3.2. Mạng neural nhân tạo
Mặc dù hiểu biết của con người về kiến trúc và hoạt động của não còn chưa đầy
đủ, người ta tạo ra được các máy có một số tính năng tương tự não nhờ mô phỏng các đặc
điểm:
GVHD: TS. Dương Tôn Đảm HVTH: Lê Thành Nguyên

Trang 18

 Tri thức thu nhận được nhờ quá trình học
 Tính năng có được nhờ kiến trúc mạng và tính chât kết nối
Các máy loại mô phỏng này có tên chung là mạng Neural nhân tạo hay mạng
Neural (còn có tên gọi là máy thần kinh) và viết tắt là ANN hay NN. Trong ứng dụng
chúng thường được tích hợp với các hệ khác.
3.3.3. Mô hình và kiến trúc mạng neural
Mô hình toán học của mạng Neural sinh học được đề xuất bởi McCulloch và Pitts,
thường được gọi là Neural M-P, ngoài ra nó còn được gọi là phần tử xử lý và được ký
hiệu là PE (Processing Element).
Mô hình Neural có m đầu vào x
1
, x
2

Hình bên dưới môtả mạng neural có đầu vào đơn, có hoạt động như sau: Một tín
hiệu vào p được nhân với trọng số w thành wp và một tín hiệu khác bằng 1 nhân với giá
trị khuynh hướng b đưa tới bộ tổng. Tín hiệu ra n của bộ tổng qua hàm chuyển f cho tín
hiệu ra a. Trong đó, trọng số w tương ứng với độ liên kết của khớp kết nối (Synapse),
hàm tổng và hàm chuyển mô phỏng thân tế bào còn tín hiệu ra mô phỏng tín hiệu ở
Axon.

Hình 5. Mạng neural có đầu vào đơn
Tín hiệu ra a phụ thuộc vào hàm chuyển còn khuynh hướng có thể xem như là một
trọng số của tín hiệu vào bằng 1.
Hàm chuyển :Hàm chuyển f có thể là hàm tuyến tính hoặc phi tuyến và phụ thuộc
theo từng bài toán. Có nhiều loại hàm chuyển, việc chọn hàm chuyển cần phù hợp với bài
toán cụ thể phải giải quyết.
Hàm truyền có thể có các dạng sau:
Hàm bước






00
01
xkhi
xkhi
y

Hàm giới hạn chặt (hay còn gọi là hàm bước)



xkhi
xkhix
xkhi
xy

Hàm ngưỡng đơn cực
x




e
y
1
1
với λ>0
Hàm ngưỡng hai cực
1
1
2



 x

e
y
với λ > 0
Đồ thị các dạng hàm truyền được biểu diễn như sau