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

CÔNG NGHỆ TRI THỨC VÀ
ỨNG DỤNG
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: GS. TSKH. Hoàng Văn Kiếm
HVTH: Lê Thành Nguyên
MSHV: CH1301102
TP HCM, Tháng 09 năm 2014
MỤC LỤC
2
DANH MỤC HÌNH
3
GVHD: GS. TSKH. Hoàng Văn Kiếm HVTH: Lê Thành Nguyên
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

tiềm năng khách hàng. Khi đó, chúng ta có thể nghiên cứu những hành vi của những
khách hàng trước đó và dự báo cho người tiếp theo. Tương tự, chúng ta có thể xem xét
những lựa chọn của những thí sinh trước đó và dự báo cho tương lai.
Như vậy, bài toán đặt ra yêu cầu tìm giải pháp trả lời câu hỏi “một thí sinh sẽ chọn
theo học ngành nào ở trường nào khi thí sinh này đã đủ điểm trúng tuyển ít nhất hai
ngành của ít nhất một trường Đại học, Cao đẳng trong kỳ thi tuyển sinh?". Với yêu cầu
này sẽ xem như bất khả thi nếu không có công cụ phân tích dữ liệu.
Trang 5
GVHD: GS. TSKH. Hoàng Văn Kiếm HVTH: Lê Thành Nguyên
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.

) = v(b
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
Trang 7
GVHD: GS. TSKH. Hoàng Văn Kiếm HVTH: Lê Thành Nguyên
ID Color Size
U8 Red Small
Bảng 1: Hệ thông tin
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)

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 }
Trang 9
GVHD: GS. TSKH. Hoàng Văn Kiếm HVTH: Lê Thành Nguyên
và
Trong đó BX, X lần lượt gọi là B-xấp xỉ dưới và B- xấp xỉ trên của tập X.
Tập BX bao gồm tất cả các phần tử của U chắc chắn thuộc vào X.
Tập bao gồm các phần tử của U có khả năng được phân loại vào những phần tử
thuộc X ứng với quan hệ R.
Từ hai tập xấp xỉ người ta định nghĩa các tập:
+ BN

Độ chính xác của xấp xỉ
3.1.6. Rút gọn (Reduction) và lõi (Core)
Trong bảng quyết định, các thuộc tính điều kiện được phân thành 3 loại, đó là:
thuộc tính lõi (core), thuộc tính rút gọn và thuộc tính không cần thiết. Thuộc tính lõi là
thuộc tính không thể thiếu trong việc phân hoạch tập dữ liệu. Thuộc tính không cần thiết
là những thuộc tính dư thừa (có thể loại bỏ một thuộc tính như vậy chứ không phải loại
bỏ tất cả) mà không ảnh hưởng đến việc phân hoạch dữ liệu. Thuộc tính rút gọn nằm giữa
2 tập thuộc tính trên, với một tổ hợp thuộc tính nào đó, nó là thuộc tính dư thừa nhưng
với tổ hợp thuộc tính khác, nó có thể là thuộc tính lõi.
Cho một bảng quyết định . Tập thuộc tính được gọi là một rút gọn của C nếu
POS
R
(D)= POS
C
(D). Lõi của tập thuộc tính C, ký hiệu CORE(C) là tất cả các thuộc tính
giao của tất cả các tập rút gọn của C.
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
Trang 11

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
hay có thể nói c
ij
là tập các thuộc tính
phân biệt
3.2. CÂY QUYẾT ĐỊNH
3.2.1. Giới thiệu
Cây quyết định là một ứng dụng của đồ thị dạng cây trong quá trình ra quyết định.
Một cây quyết định là một đồ thị của các quyết định và các hệ quả có thể của nó (bao
gồm rủi ro và hao phí tài nguyên). Cây quyết định được sử dụng để xây dựng một kế
hoạch nhằm đạt được mục tiêu mong muốn(phân tích thị trường, đầu tư,…) trong quá
trình ra quyết định của cá nhân, tổ chức,….
Trang 12
GVHD: GS. TSKH. Hoàng Văn Kiếm HVTH: Lê Thành Nguyên
Hình 1: Cấu trúc cây quyết định
Trong lĩnh vực máy học, cây quyết định là một kiểu mô hình dự báo, nghĩa là một
ánh xạ từ các quan sát về một sự vật/hiện tượng đến các kết luận về giá trị mục tiêu của
sự vật/hiện tượng. Mỗi nút trong đồ thị tương ứng với một biến dự báo, giá trị biến dự
báo thể hiện trên mối liên kết giữa nó và nút con. Mỗi nút lá đại diện cho giá trị dự đoán
của biến mục tiêu. Quá trình ra quyết định là các bước xây dựng đường đi từ nút gốc đến
nút lá.
Học bằng cây quyết định cũng là một phương pháp thông dụng trong khai phá dữ

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:
Trong đó, P
i
là tỷ lệ các mẫu thuộc lớp I trên tập S các mẫu kiểm tra.
− Các trường hợp đặc biệt
+ Nếu tất cả các mẫu thành viên trong tập S đều thuộc cùng một lớp thì
Entropy(S) =0
+ Nếu trong tập có số mẫu phân bố đều nhau vào các lớp thì Entropy(S) = 1
+ Các trường hợp còn lại 0 < Entropy(S) < 1
Trang 14
GVHD: GS. TSKH. Hoàng Văn Kiếm HVTH: Lê Thành Nguyên
3.2.3. Information Gain
(Viết tắt Gain) là đại lượng dùng để đo mức độ giảm entropy mong đợi của một
thuộc tính được lựa chọn cho việc phân lớp. Đại lượng này được tính thông qua hai giá trị
Information và Entropy.
Cho tập dữ liệu S gồm có n thuộc tính Ai(i=1,2, …, n) giá trị Information của
thuộc tính Ai ký hiệu là Information (Ai) được xác định bởi công thức:
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:
Trong đó:
+ S là tập hợp ban đầu với thuộc tính A. Các giá trị của v tương ứng là các giá
trị của thuộc tính A.
+ Sv bằng tập hợp con của tập S mà có thuộc tính A mang giá trị v.
+ |Sv| là số phần tử của tập Sv
+ |S| là số phân tử của tập S
3.2.4. Thuật toán ID3
Thuật toán ID3 được phát biểu bởi Quinlan (Đại học Syney, Australia) và được
công bố vào cuối thập niên 70 của thế kỷ 20. Sau đó, thuật toán ID3 được giới thiệu và

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:
Ngày Quang cảnh Nhiệt độ Độ ẩm Gió Chơi Tennis
D1 Nắng Nóng Cao Nhẹ Không
D2 Nắng Nóng Cao Mạnh Không
D3 Âm u Nóng Cao Nhẹ Có
D4 Mưa Ấm áp Cao Nhẹ Có
D5 Mưa Mát Trung bình Mạnh Có
D6 Mưa Mát Trung bình Mạnh Không
D7 Âm u Mát Trung bình Manh Có
D8 Nắng Ấm áp Cao Nhẹ Không
D9 Nắng Mát Trung bình Nhẹ Có
D10 Mưa Ấm áp Trung bình Nhẹ Có
D11 Nắng Ấm áp Trung bình Mạnh Có
D12 Âm u Ấm áp Cao Mạnh Có
D13 Âm u Nóng Trung bình Nhẹ Có
D14 Mưa Ấm áp Cao Mạnh Không
Tập dữ liệu gồm 14 ví dụ, mỗi ví dụ biểu diễn cho tình trạng thời tiết gồm
các thuộc tính quang cảnh, nhiệt độ, độ ẩm và gió và dẫn đến được phân loại có
chơi tennis hay không. Giá trị phân loại chỉ có hai loại có hoặc không hay ta nói
tập ví dụ của khái niệm này được phân loại thành hai lớp.
Trang 16
GVHD: GS. TSKH. Hoàng Văn Kiếm HVTH: Lê Thành Nguyên
Mỗi thuộc tính đều có một tập hữu hạn giá trị. Thuộc tính quang cảnh có ba
giá trị: âm u, mưa, nắng; nhiệt độ có ba giá trị: nóng, mát, ấm áp; độ ẩm có hai giá
trị: cao và trung bình; gió có hai giá trị: mạnh, nhẹ.
Từ tập dữ liệu huấn luyện này, giải thuật ID3 sẽ xây dựng một cây quyết
định có khả năng phân loại đúng đắn các ví dụ trong tập này, đồng thời hy vọng
trong tương lai, nó cũng sẽ có khả năng phân loại đúng các trường hợp với dữ liệu

)
– entropy(S
âm u
) – entropy(S
mưa
)
Trong đó:
− Entropy(S) = 0.94
− Entropy(S
nắng
) = – log
2
– log
2
= 0.971
− Entropy(S
âm u
) = – log
2
– log
2
= 0
− Entropy(S
mưa
) = – log
2
– log
2
= 0.971
⇒ gain(S,

2
= 1
− Entropy(S
ấm áp
) = – log
2
– log
2
= 0.9178
− Entropy(S
mát
) = – log
2
– log
2
= 0.81128
⇒gain(S, nhiệt độ) = 0.029
− Values(độ ẩm) = {cao, trung bình}
S
cao
=[3+, 4-]
S
trung bình
= [6+, 1-]
Tính tương tự như trên ta có gain(S, độ ẩm) = 0.151
− Values(gió) = {nhẹ, mạnh}
S
nhẹ
= [6+, 2-]
S

If(độ ẩm = cao ∧ quang cảnh = mưa) then chơi tenis = không.
If(độ ẩm = thấp) then chơi tenis = có.
If(độ ẩm = bình thường ∧ nhiệt độ = nóng) then chơi tenis = không.
If(độ ẩm = bình thường ∧ nhiệt độ = trung bình) then chơi tenis = có.
Trang 19
GVHD: GS. TSKH. Hoàng Văn Kiếm HVTH: Lê Thành Nguyên
3.3. MẠNG NEURAL
3.3.1. Mạng neural sinh học
Đến nay người ta biết rằng các quá trình tính toán trong bộ não sinh học khác với
các máy tính số. Công trình nghiên cứu về não đầu tiên thuộc về Ramond-Cajál (1911),
ông cho rằng hệ thần kinh cấu tạo từ các Neural. Bộ não xử lý chậm hơn(10
-3
s) so với
các thiết bị vật lý (10
-9
) tuy nhiên tốn ít năng lượng hơn và thực hiện được nhiều chức
năng hơn. Con người có khoảng 10
11
Neural, 10
15
khớp kết nối. Các khớp khi mới sinh
ít kết nối với nhau, chúng được kết nối nhờ quá trình học.
Đặc điểm của não:
− Xử lý song song
− Phân tán
− Phi tuyến
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.

Tập các đầu vào: Là các tín hiệu vào của Neural, các tín hiệu này thường được đưa
vào dưới dạng một vector m chiều.
Tập các liên kết (các trọng số): Mỗi liên kết được thể hiện bởi một trọng số
(thường được gọi là trọng số liên kết). Trọng số liên kết giữa tín hiệu vào thứ j cho
Trang 21
GVHD: GS. TSKH. Hoàng Văn Kiếm HVTH: Lê Thành Nguyên
Neural i thường được ký hiệu là w
ij
. Thông thường các trọng số này được khởi tạo ngẫu
nhiên ở thời điểm khởi tạo mạng và được cập nhật liên tục trong quá trình học mạng.
Bộ tổng (Hàm tổng): Thường dùng để tính tổng của tích các đầu vào với trọng số
liên kết của nó.
Ngưỡng: Ngưỡng này thường được đưa vào như một thành phần của hàm truyền.
Hàm truyền: Hàm này dùng để giới hạn phạm vi đầu ra của mỗi Neural. Nó nhận
đầu vào là kết quả của hàm tổng và ngưỡng đã cho. Thông thường, phạm vi đầu ra của
mỗi Neural được giới hạn trong đoạn [0,1] hoặc [-1,1]. Các hàm truyền rất đa dạng, có
thể là các hàm tuyến tính hoặc phi tuyến. Việc lựa chọn hàm truyền tùy thuộc vào từng
bài toán và kinh nghiệm của người thiết kế mạng.
Đầu ra: Là tín hiệu đầu ra của một Neural, với mỗi Neural sẽ có tối đa một đầu ra.
Neural có đầu vào đơn
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

Hàm bậc thang





<
≤≤
>
==
00
10
11
)sgn(
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

biệt với nhau qua vector hàm trọng số ở đầu vào w. Nguyên lý cấu tạo của mạng Neural
bao gồm nhiều lớp, mỗi lớp bao gồm nhiều Neural có cùng chức năng trong mạng.
Trang 24
GVHD: GS. TSKH. Hoàng Văn Kiếm HVTH: Lê Thành Nguyên
Mạng Neural được xây dựng như trên là mạng gồm 3 lớp mắc nối tiếp nhau đi từ
đầu vào đến đầu ra. Trong mạng không tồn tại bất kỳ một mạch hồi tiếp nào. Một mạng
Neural có cấu trúc như vậy gọi là mạng một hướng hay mạng truyền thẳng một hướng
(Feed forward network), và có cấu trúc mạng ghép nối hoàn toàn (vì bất cứ một Neural
nào trong mạng cũng được nối với một hoặc vài Neural khác). Mạng Neural bao gồm
một hay nhiều lớp trung gian được gọi là mạng Multilayer Perceptrons) (MLP-Network).
Mạng Neural khi mới được hình thành thì chưa có tri thức, tri thức của mạng sẽ
được hình thành dần dần sau một quá trình học. Mạng Neural được học bằng cách đưa
vào những kích thích, và mạng hình thành những đáp ứng tương ứng, những đáp ứng
tương ứng phù hợp với từng loại kích thích sẽ được lưu trữ. Giai đoạn này được gọi là
giai đoạn học của mạng. Khi đã hình thành tri thức mạng, mạng có thể giải quyết các vấn
đề một cách đúng đắn. Đó có thể là vấn đề ứng dụng rất khác nhau, được giải quyết chủ
yếu dựa trên sự tổ chức hợp nhất giữa các thông tin đầu vào của mạng và các đáp ứng
đầu ra.
Nếu nhiệm vụ của một mạng là hoàn chỉnh hoặc hiệu chỉnh các thông tin thu được
không đầy đủ hoặc bị tác động của nhiễu. Mạng Neural kiểu này được ứng dụng trong
lĩnh vực hoàn thiện mẫu, trong đó có một ứng dụng cụ thể là nhận dạng chữ viết.
Nhiệm vụ tổng quát của một mạng Neural là lưu giữ động các thông tin. Dạng
thông tin lưu giữ này chính là quan hệ giữa các thông tin đầu vào và các đáp ứng đầu ra
tương ứng, để khi có một kích thích bất kỳ tác động vào mạng, mạng có khả năng suy
diễn và đưa ra một đáp ứng phù hợp. Đây chính là chức năng nhận dạng theo mẫu của
mạng Neural. Để thực hiện chức năng này, mạng Neural đóng vai trò như một bộ phận tổ
chức các nhóm thông tin đầu vào, và tương ứng với mỗi nhóm là một đáp ứng đầu ra phù
hợp. Như vậy, một nhóm bao gồm một loại thông tin đầu vào và một đáp ứng đầu ra. Các
Trang 25