ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
________ ________
BÀI THU HOẠCH MÔN HỌC
Môn: CÔNG NGHỆ TRI THỨC & ỨNG DỤNG
CÂY QUYẾT ĐỊNH VÀ ỨNG DỤNG
TRONG VAY TÍN CHẤP
Học viên thực hiện:
CH1101154
TRẦN THỊ TƯỜNG VI

TP. HCM, năm 2012
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
Mở đầu
Ngày nay cùng với sự phát triển vượt bậc của công nghệ thông tin, lượng thông tin
ngày càng bùng nổ và trở nên khổng lồ. Các phương pháp thống kê truyền thống hầu
như không còn phù hợp nữa. Khai khoáng dữ liệu (data mining) ngày càng được
nhiều người chú ý. Nó thực sự đã đem lại những lợi ích đáng kể trong việc cung cấp
những thông tin tiềm ẩn trong các cơ sở dữ liệu lớn. Trong rất nhiều phương pháp
khai khoáng thì cây quyết định (decision tree) được coi là công cụ mạnh và phổ biến.
Trong kinh doanh, ra quyết định cho một vấn đề thiếu khoa học, cảm tính sẽ rất nguy
hiểm. Nghiên cứu những cơ sở của việc ra quyết định một cách khoa học sẽ giúp ta
nhận thức đúng đắn những cơ sở khoa học, những quy luật chi phối và lường trước
được những hậu quả tất yếu sẽ xảy ra nếu như các quyết định được chấp nhận.
Trong bài thu hoạch nhỏ này, em muốn giới thiệu về cây quyết định, một vài thuật
toán trên nó và áp dụng để giải một bài toán ‘đánh giá khách hàng tiềm năng cho
gói vay tín chấp’ của các ngân hàng. Hy vọng với những kiến thức thu nhận được,
cùng với việc cố gắng mô phỏng ý tưởng giải bài toán sẽ giúp mọi người hiểu rõ hơn
ý nghĩa của data mining, đặc biệt là cây quyết định trong thực tiễn.
MÔN HỌC : CÔNG NGHỆ TRI THỨC & ỨNG DỤNG - 1 -

2. Xây dựng dữ liệu 14
3. Chuẩn bị dữ liệu cho chương trình 15
4. Chạy chương trình 16
5. Tập luật suy ra từ kết quả chạy 20
II. NHẬN XÉT 20
Tài liệu tham khảo 21
MÔN HỌC : CÔNG NGHỆ TRI THỨC & ỨNG DỤNG - 2 -
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
PHẦN I : LÝ THUYẾT
I. CÂY QUYẾT ĐỊNH
I.1. Khái niệm
Cây quyết định (Decision Tree) là một cây phân cấp có cấu trúc được dùng để phân
lớp các đối tượng dựa vào dãy các luật (series of rules).
Trong đó, mỗi nút nhánh thể hiện một sự lựa chọn trong số nhiều sự lựa chọn và mỗi
nút lá là sự thể hiện của một quyết định.
Cây quyết định được xây dựng để hỗ trợ quá trình ra quyết định.
Cho dữ liệu về các đối tượng gồm các thuộc tính cùng với lớp (classes) của nó, cây
quyết định sẽ sinh ra các luật để dự đoán lớp của các đối tượng chưa biết (unseen
data)
I.2. Ví dụ
Dưới đây là một ví dụ về cây quyết định được xây dựng từ một tập dữ liệu đã có
nhằm phân lớp những khách hàng có thông tin phản hồi (Responded) sau khi nhận
quảng cáo ‘nhà cho thuê’.
Input: Giá trị của 4 thuộc tính dưới đây:
- District = {Suburban, Rural, Urban}
- House Type = {Detached, Semi-deteched, Terrace}
- Income = {High, Low}
- Previous Customer = {Yes, No}
Output/Outcome: Nothing, Responded

liệu chỉ gồm một loại biến. Chẳng hạn, các luật quan hệ chỉ có thể dùng cho
các biến tên, trong khi mạng nơ-ron chỉ có thể dùng cho các biến có giá trị
bằng số.
• Cây quyết định là một mô hình hộp trắng. Nếu có thể quan sát một tình
huống cho trước trong một mô hình, thì có thể dễ dàng giải thích điều kiện đó
bằng logic Boolean. Mạng nơ-ron là một ví dụ về mô hình hộp đen, do lời giải
thích cho kết quả quá phức tạp để có thể hiểu được.
• Có thể thẩm định một mô hình bằng các kiểm tra thống kê. Điều này làm
cho ta có thể tin tưởng vào mô hình.
• Cây quyết định có thể xử lý tốt một lượng dữ liệu lớn trong thời gian
ngắn. Có thể dùng máy tính cá nhân để phân tích các lượng dữ liệu lớn trong
một thời gian đủ ngắn để cho phép các nhà chiến lược đưa ra quyết định dựa
trên phân tích của cây quyết định.
• Cây quyết định là một sự tổng quát tốt cho những trường hợp ta không để
ý đến, chỉ những trường hợp được mô tả trong những giới hạn của những đặc
tính mà liên quan đến những khái niệm mục tiêu.
II. CÁC THUẬT TOÁN
II.1. Giới thiệu vài khái niệm
1. Entropy
- Entropy mô tả mức độ hỗn loạn trong một tín hiệu lấy từ một sự kiện ngẫu nhiên.
Nói cách khác, entropy cũng chỉ ra có bao nhiêu thông tin trong tín hiệu, với
thông tin là các phần không hỗn loạn ngẫu nhiên của tín hiệu.
- Claude E. Shannon đã xây dựng định nghĩa về entropy để thoả mãn các giả định
sau:
• Entropy phải tỷ lệ thuận liên tục với các xác suất xuất hiện của các phần tử
ngẫu nhiên trong tín hiệu. Thay đổi nhỏ trong xác suất phải dẫn đến thay đổi
nhỏ trong entropy.
• Nếu các phần tử ngẫu nhiên đều có xác suất xuất hiện bằng nhau, việc tăng số
lượng phần tử ngẫu nhiên phải làm tăng entropy.
• Có thể tạo các chuỗi tín hiệu theo nhiều bước, và entropy tổng cộng phải bằng

- Gain xác định độ cải thiện entropy tong qua phân lớp một thuộc tính, Gain càng
cao càng tốt.
- Chúng ta có thể sử dụng khái niệm về thu thập để đánh giá tầm quan trọng những
thuộc tính và xây dựng những cây quyết định mà mỗi nút chứa thuộc tính mà
nhận được lớn nhất trong những thuộc tính chưa được xem xét trong đường đi từ
gốc.
- Mục đích của việc sắp thứ tự này là :
1. Để tạo ra cây quyết định nhỏ mà những record có thể được xát định sau chỉ
một vài lần cây quyết định phân chia.
2. Để kết nối một hi vọng đối với việc tối thiểu của quá trình tạo quyết định.
II.2. ID3
Ý tưởng chính của thuật toán này
1. Tính đồng nhất định lượng (entropy) của các thuộc tính chưa dùng dựa vào các
dữ liệu test (test data)
2. Chọn thuộc tính có entropy nhỏ nhất (hoặc information gain là lớn nhất)
3. Tạo node chứa thuộc tính đó.
Mô tả thuật toán:
ID3 (Examples, Target_Attribute, Attributes)
1. Create a root node for the tree
2. If all examples are positive, Return the single-node tree Root, with label = +.
3. If all examples are negative, Return the single-node tree Root, with label =
4. If number of predicting attributes is empty, then Return the single node tree
Root, with label = most common value of the target attribute in the examples.
5. Otherwise
Begin
o A = The Attribute that best classifies examples.
o Decision Tree attribute for Root = A.
o For each possible value, , of A,
 Add a new tree branch below Root, corresponding to the test A =
MÔN HỌC : CÔNG NGHỆ TRI THỨC & ỨNG DỤNG - 7 -

None of the features provide any information gain. In this case, C4.5
creates a decision node higher up the tree using the expected value of the
MÔN HỌC : CÔNG NGHỆ TRI THỨC & ỨNG DỤNG - 8 -
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
class.
Instance of previously-unseen class encountered. Again, C4.5 creates a
decision node higher up the tree using the expected value.
2. For each attribute a
1. Find the normalized information gain from splitting on a
3. Let a_best be the attribute with the highest normalized information gain
4. Create a decision node that splits on a_best
5. Recurse on the sublists obtained by splitting on a_best, and add those
nodes as children of node
III. VẤN ĐỀ TRONG CÂY QUYẾT ĐỊNH
Các vấn đề đặc thù trong khi học hay phân lớp dữ liệu bằng cây quyết định gồm: xác
định độ sâu để phát triển cây quyết định, xử lý với những thuộc tính liên tục, chọn
phép đo lựa chọn thuộc tính thích hợp, sử dụng tập dữ liệu đào tạo với những giá trị
thuộc tính bị thiếu, sử dụng các thuộc tính với những chi phí khác nhau, và cải thiện
hiệu năng tính toán. Sau đây là những vấn đề chính đã được giải quyết trong các thuật
toán phân lớp dựa trên cây quyết định.
III.1. Overfitting
- Định nghĩa: Cho một không giả thuyết H , một giả thuyết h thuộc H được gọi là
overfit trên training data nếu tồn tại một vài giả thuyết h’ thuộc H mà h có ít lỗi
hơn h’ trên training example , nhưng h’ có lỗi nhỏ hơn h trên toàn bộ sự phân bố
của những trường hợp.
- Một vài cách để tránh overfiting
+ Dừng phát triển cây sớm hơn bình thường, trước khi đạt tới điểm phân lớp
hoàn hảo tập dữ liệu đào tạo. Với phương pháp này, một thách thức đặt ra là
phải ước lượng chính xác thời điểm dừng phát triển cây.

ra một thuộc tính logic A
c
mang giá trị true nếu A < C và false nếu ngược lại.
- Trong thuật toán C4.5, Ci được chọn là giá trị trung bình của hai giá trị liền kề
nhau trong dãy giá trị đã sắp xếp.
III.3. Thao tác với dữ liệu bị thiếu
- Thực tế sẽ gặp rất nhiều trường hợp giá trị của các thuộc tính bị thiếu, vậy điều gì
xảy ra nếu dữ liệu chứa một hoặc nhiều giá trị không biết “?” thay cho một giá trị
thuộc tính cụ thể.
- Xét một trường hợp mà trong đó Gain(S,A) được tính toán tại nút n trong cây
quyết định đề xát định khi nào thuộc tính A là thuộc tính tốt nhất để kiểm tra nút
quyết định này. Giả sử rằng (x,c(x)) là một trong những training example trong S
và giá trị A(x) là không được biết đến.
- Một trong những chiến thuật liên quan đến thiếu giá trị thuộc tính là gán nó giá trị
mà hầu như chung trong số những training example tại nút n . Thay phiên nhau,
chúng ta gán nó giá trị chung trong số những training example tại nút n mà có sự
phân loại c(x).
- Thứ hai một thủ tục phức tạp hơn là gán một kết quả có thể xảy ra cho mỗi một
giá trị của A hơn là đơn giản gán một giá trị chung cho A(x).Khả năng có thể
nhận được bằng cách quan sát tần số của những giá trị khác nhau cho A trong số
những ví dụ tại nút n.
- Cho ví dụ, cho trước thuộc tính với giá trị logic A , nếu nút n chứa 6 trường hợp
được biết đến với A=1 và 4 trường hợp là A=0 , như vậy chúng ta có xát suất mà
A=1 là 0,6 và xát suất mà A=0 là 0,4.Phân số 0,6 của thực thể x được phân bố
MÔN HỌC : CÔNG NGHỆ TRI THỨC & ỨNG DỤNG - 10 -
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
xuống nhánh với A=1 và phân số 0,4 của x phân bố xuống nhánh của những
nhánh cây khác.Những tỉ số ví dụ này được sử dụng mục đích tính toán thông tin
Gain và những sự phân chia xa hơn ở những nhánh con của cây nếu sự thiếu giá

vay được tiền từ các ngân hàng, điều kiện trước tiên là phải có tài sản thế chấp,
thì hiện nay vay tín chấp dần dần trở thành chiến lược cho nhiều ngân hàng. Các
đối tượng họ hướng tới là những người có thu nhập ổn định, cần tiền để dùng cho
các mục đích như: mua xe, sửa nhà, làm đám cưới,
- Do vay tín chấp không có tài sản đảm bảo nên lãi suất sẽ cao hơn vay thế chấp.
Như vậy nếu ngân hàng xây dựng được những chương trình dự đoán được khách
hàng tiềm năng (khách hàng có khả năng trả nợ cũng như trả đúng hạn) sẽ giúp
thu được lợi nhuận lớn từ mảng vay tín chấp này.
- Để được đồng ý trên một khoản vay, người đi vay phải cung cấp trực tiếp hoặc
gián tiếp các thông tin như: tuồi, tình trạng hôn nhân, tên công ty, lý do vay, mức
lương… Bên cạch đó, các thông tin về ngày trả tiền sẽ giúp ta đánh giá là ‘tốt’
hay ‘xấu’ sau khi kết thúc một hợp đồng vay.
- Dựa vào các thông tin lưu trữ này ta có thể dùng phương pháp khai khoáng dữ
liệu (data mining) thông qua việc xây dựng cây quyết định để dự đoán khách
hàng tiềm năng.
- Việc đánh giá này cũng sẽ giúp công ty có những quyết định duyệt trên các khoản
vay một cách khoa học hơn. Có thể duyệt bằng, nhỏ hơn số tiền khách hàng đề
xuất hoặc khuyết khích khách hàng vay thêm.
- Ghi chú: Những khách hàng này phải là những người đi vay thỏa được các yêu
cầu tối thiểu của từng ngân hàng như: lương phải lớn hơn 4 triệu, phải làm ở công
ty hiện tại ít nhất 1 năm Nên cây quyết định được xây dựng sẽ chỉ áp dụng ở
bước xét duyệt số tiền cho vay sau khi hồ sơ đăng ký là hợp lệ.
MÔN HỌC : CÔNG NGHỆ TRI THỨC & ỨNG DỤNG - 12 -
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
I.2. Công cụ hỗ trợ
- Chúng ta sẽ sử dụng chương trình có sẵn thay vì phải xây dựng lại từ đầu.
- Weka là phần mềm khai thác dữ liệu viết bằng ngôn ngữ Java. Weka tập hợp các
thuật toán máy học cho các tác vụ khai thác dữ liệu. Weka gồm các công cụ thực
hiện: tiền xử lý dữ liệu(data pre-processing), phân lớp (classification), hồi quy

d
Pre-
contract
Reason Amount Result
Finance 44 Married 30 yes no Other 150 Bad
Finance 36 Single 20 yes no SB 100 Bad
Finance 28 Single 12 no no Other 50 Good
Technolog
y 56 Married 24 no no Other 140 Good
? 27 Married 18 no yes Shop 80 Bad
Technolog
y 31 Single 18 no yes SB 100 Good
Technolog
y 36 Married 12 no no SB 40 Good
Service 24 Married 13 no no Other 50 Bad
? 52 Married 35 yes yes SB 200 Bad
? 33 Single 15 no yes Shop 70 Bad
Service 26 Single 10 no no SB 80 Good
Service 24 Married 8 no no Other 32 Bad
Technolog
y 29 Single 12 yes no Shop 60 Bad
Technolog
y 28 Single 19 no no Shop 120 Bad
Thêm thuộc tính cho bộ dữ liệu
- Ratio = round(Amount/Salary)
Field Age Satus Salary
Loan
ed
Pre-
contract

@attribute Loaned {yes,no}
@attribute Pre-contract {yes,no}
@attribute Reason {SB,Shop,Other}
@attribute Amount numeric
@attribute Ratio numeric
@attribute Result {Good,Bad}
@data
Finance,44,Married,30,yes,no,Other,150,5,Bad
Finance,36,Single,20,yes,no,SB,100,5,Bad
Finance,28,Single,12,no,no,Other,50,4,Good
Technology,56,Married,24,no,no,Other,140,6,Good
?,27,Married,18,no,yes,Shop,80,4,Bad
Technology,31,Single,18,no,yes,SB,100,6,Good
Technology,36,Married,12,no,no,SB,40,3,Good
Service,24,Married,13,no,no,Other,50,4,Bad
?,52,Married,35,yes,yes,SB,200,6,Bad
?,33,Single,15,no,yes,Shop,70,5,Bad
Service,26,Single,10,no,no,SB,80,8,Good
Service,24,Married,8,no,no,Other,32,4,Bad
MÔN HỌC : CÔNG NGHỆ TRI THỨC & ỨNG DỤNG - 15 -
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
Technology,29,Single,12,yes,no,Shop,60,5,Bad
Technology,28,Single,19,no,no,Shop,120,6,Bad
4. Chạy chương trình
- Chọn Application là Explorer
- Load file data
MÔN HỌC : CÔNG NGHỆ TRI THỨC & ỨNG DỤNG - 16 -
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG

MÔN HỌC : CÔNG NGHỆ TRI THỨC & ỨNG DỤNG - 20 -
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
Tài liệu tham khảo
1. Bài giảng môn học “Công nghệ tri thức” .
Giảng viên : GS.TSKH Hoàng Văn Kiếm
2. Decision Tree with Classification Problem
Nguyễn Văn Chức
3. Combining Classifiers with Meta Decision Trees
Robert E. Schapire
4. Bagging, Boosting and C4.5
J. R. Quinlan
5. NEURAL NETWORKS Design and Applications
Lakhmi Jain, Ph.D.
6.
7. ID3, C4.5
MÔN HỌC : CÔNG NGHỆ TRI THỨC & ỨNG DỤNG - 21 -