TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI 2
KHOA CÔNG NGHỆ THÔNG TIN


NGUYỄN VIỆT DŨNG

ỨNG DỤNG CÂY QUYẾT ĐỊNH ĐỂ
PHÂN LOẠI KHÁCH HÀNG VAY VỐN CỦA
NGÂN HÀNG TMCP NGOẠI THƢƠNG
CHI NHÁNH VIỆT TRÌ KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
Chuyên ngành: Khoa học máy tính
TS. LƯU THỊ BÍCH HƯƠNG HÀ NỘI – 2015


Để hoàn thành đƣợc khóa luận này, trƣớc hết em xin gửi lời cảm ơn
sâu sắc nhất tới TS. Lƣu Thị Bích Hƣơng đã tận tình hƣớng dẫn, chỉ bảo,
định hƣớng, đóng góp những ý kiến quý báu cho em trong suốt quá trình
thực hiện.
Em xin chân thành cảm ơn các thầy, cô giáo trong khoa Công nghệ
Thông tin, trƣờng Đại học Sƣ phạm Hà Nội 2 đã quan tâm giảng dạy và giúp
đỡ em trong suốt bốn năm học vừa qua cũng nhƣ trong thời gian em làm bài
khóa luận này. Là sinh viên khoa Công nghệ Thông tin, em rất tự hào về
khoa mình học, về thầy cô giáo của mình. Em xin kính chúc các thầy, các cô
luôn mạnh khỏe, hạnh phúc và thành công. Chúc khoa Công nghệ Thông tin
sẽ ngày một khang trang, vững mạnh, góp phần to lớn trong sự nghiệp đào
tạo chuyên nghiệp của trƣờng Đại học Sƣ phạm Hà Nội 2.
Lần đầu nghiên cứu khoa học, chắc chắn đề tài của em không tránh
khỏi những thiếu sót, hạn chế. Vì vậy, em rất mong sự đóng góp ý kiến của
các thầy cô giáo và các bạn để đề tài của em đƣợc hoàn thiện.

Hà Nội, tháng 05 năm 2015
Sinh viên Nguyễn Việt Dũng
LỜI CAM ĐOAN
Tên em là: Nguyễn Việt Dũng
Sinh viên: K37A – CNTT, trƣờng Đại học Sƣ phạm Hà Nội 2.
Em xin cam đoan:
1. Đề tài “Ứng dụng cây quyết định để phân loại khách hàng vay vốn của
Ngân hàng thương mại cổ phần Ngoại thương, chi nhánh Việt Trì” là kết

1.5.1. Xử lý dữ liệu 13
1.5.2. Tạo cây 13
1.5.3. Tiêu chuẩn tách 14
1.5.4. Tiêu chuẩn dừng 15
1.5.5. Tỉa cây 15
1.6. Phát biểu bài toán 16
CHƢƠNG 2: KHAI PHÁ DỮ LIỆU 19
2.1. Khám phá tri thức 19
2.1.1. Khai phá dữ liệu 20
2.2. Một số phƣơng pháp khai phá dữ liệu thông dụng 24
2.2.1. Phân lớp 24
2.2.2.Phân cụm 28
2.2.3. Luật kết hợp 32
2.3. Ứng dụng khai phá dữ liệu trong lĩnh vực ngân hàng 35
2.3.1. Marketing 35
2.3.2. Quản lý rủi ro 35 2.3.3. Phát hiện sai lệch 37
2.3.4. Quản trị quan hệ khách hàng 38
2.3.5. Phân tích dữ liệu tài chính (Financial Data Analysis) 40
CHƢƠNG 3: ỨNG DỤNG KHAI PHÁ DỮ LIỆU ĐỂ PHÂN LOẠI KHÁCH
HÀNG 42
3.1. Quy trình tín dụng 42
3.1.1. Khái niệm quy trình tín dụng 42
3.1.2. Ý nghĩa của quy trình tín dụng 42
3.1.3. Quy trình tín dụng căn bản 42
3.1.4.Thử nghiệm dự đoán rủi ro tín dụng 43
3.2. Sử dụng cây quyết định để phân loại khách hàng 45
3.2.1. Tiêu chí chọn thuộc tính phân lớp 45

1. Lý do chọn đề tài
Ứng dụng Công nghệ Thông tin vào các lĩnh vực của đời sống, kinh tế
xã hội ngày càng phổ biến. Điều này đồng nghĩa với việc dữ liệu đƣợc lƣu trữ
trong các cơ quan, xí nghiệp, trƣờng học,… ngày càng khổng lồ. Tuy nhiên
theo thống kê thì chỉ có một lƣợng nhỏ của những dữ liệu này (khoảng từ 5%
đến 10%) là luôn đƣợc phân tích, số còn lại họ không biết sẽ phải làm gì và có
thể làm gì với những dữ liệu này, nhƣng họ vẫn tiếp tục thu thập và lƣu trữ vì
hy vọng những dữ liệu này sẽ cung cấp cho họ những thông tin quý giá một
cách nhanh chóng để đƣa ra những quyết định kịp thời vào một lúc nào đó.
Chính vì vậy, các phƣơng pháp quản trị và khai thác cơ sở dữ liệu truyền
thống ngày càng không đáp ứng đƣợc thực tế. Từ đó đã làm phát triển một
khuynh hƣớng kỹ thuật mới đó là kỹ thuật phát hiện tri thức và khai phá dữ
liệu (KDD - Knowledge Discovery and Data Mining).
Cho đến nay, khai phá dữ liệu ngày càng đƣợc nghiên cứu, phát triển và
đã đạt đƣợc những thành tựu đáng kể trong các lĩnh vực: kinh doanh, y tế,
công nghệ sinh học, quân sự, bƣu chính viễn thông, xây dựng,… Rất nhiều tổ
chức và công ty lớn trên thế giới đã áp dụng kỹ thuật khai phá dữ liệu vào các
hoạt động sản xuất kinh doanh của mình và thu đƣợc những lợi ích to lớn.
Ngành công nghiệp ngân hàng đã bắt đầu nhận ra sự cần thiết của các kỹ thuật
khai phá dữ liệu, các kỹ thuật đó có thể giúp họ cạnh tranh trên thị trƣờng.
Các ngân hàng đã và đang sử dụng các công cụ khai phá dữ liệu cho việc
phân khúc khách hàng và lợi nhuận, chấm điểm tín dụng, phê duyệt, quảng bá
và bán sản phẩm, phát hiện các giao dịch gian lận,…Việc sử dụng phƣơng
pháp khai phá tri thức từ dữ liệu để phân loại khách hàng vay vốn là một
phƣơng pháp mới nhằm giảm nguy cơ trong rủi ro tín dụng.
Với mong muốn nghiên cứu về việc ứng dụng cây quyết định để phân
loại khách hàng của ngân hàng thƣơng mại cổ phần Ngoại thƣơng, em đã
2

chọn đề tài “Ứng dụng cây quyết định để phân loại khách hàng vay vốn của

các vấn đề của khóa luận.
Phân tích và tổng hợp các tài liệu về khai phá dữ liệu sử dụng thuật
toán về Decision Tree có thuật toán ID3, phân loại dữ liệu, mô hình dự báo.

b. Phương pháp chuyên gia
Tham khảo ý kiến của các chuyên gia để có thể thiết kế chƣơng trình
phù hợp với yêu cầu thực tiễn. Nội dung xử lý nhanh đáp ứng đƣợc yêu cầu
ngày càng cao của ngƣời sử dụng.
c. Phương pháp thực nghiệm
Thông qua quan sát thực tế, yêu cầu của cơ sở, những lý luận đƣợc
nghiên cứu và kết quả đạt đƣợc qua những phƣơng pháp trên.
Ứng dụng kết hợp kỹ thuật phân loại và mô hình cây quyết định để
phân loại khách hàng vay vốn của Ngân hàng thƣơng mại.
6. Cấu trúc khóa luận
Ngoài lời cảm ơn, mở đầu, kết luận và hƣớng phát triển, tài liệu tham
khảo, khóa luận có những nội dung sau:
Chương 1: Cơ sở lý thuyết - Chƣơng này nghiên cứu tổng quan về
thuật toán cây quyết định. Phát biểu bài toán xây dựng cây quyết định trong
việc phân loại khách hàng vay vốn của ngân hàng.
Chương 2: Khai phá dữ liệu - Tìm hiểu về khám phá tri thức, khai phá
dữ liệu và một số phƣơng pháp khai phá dữ liệu thông dụng. Chƣơng này đƣa
ra những ứng dụng cụ thể của khai phá dữ liệu trong ngân hàng.
4

Chương 3: Ứng dụng khai phá dữ liệu để phân loại khách hàng -
Chƣơng này tìm hiểu về thuật toán ID3 để xây dựng cây quyết định; nghiên
cứu tổng quan về quy trình tín dụng từ đó xây dựng chƣơng trình mô phỏng
cây quyết định trong việc phân loại khách hàng vay vốn.
, x
2
, x
3,
, x
k
, y)
6

Biến phụ thuộc (dependant variable) y là biến cần tìm hiểu, phân loại
hay tổng quát hóa. x
1
, x
2
, x
3
, là các biến sẽ giúp thực hiện công việc phân
lớp dữ liệu.
Cây quyết định là một cấu trúc phân cấp của các nút và các nhánh
(mang giá trị của thuộc tính). Có3 loại nút trên cây:
 Nút gốc
 Nút nội bộ: mang tên thuộc tính của CSDL
 Nút lá: mang tên lớp C
i

Cây quyết định đƣợc sử dụng trong phân lớp bằng cách duyệt từ nút
gốc của cây cho đến khi đụng đến nút lá, từ đó rút ra lớp của đối tƣợng cần
xét.
Ví dụ: Cây quyết định phân lớp mức lƣơng.
Hình 1.1: Cây quyết định phân lớp mức lƣơng

sai số (error term).
+Phân loại (Classification): Là phƣơng pháp dự báo, cho phép phân
loại một đối tƣợng vào một hoặc một số lớp cho trƣớc. Phân loại bằng thống
kê là một thủ tục thống kê trong đó các cá thể riêng biệt sẽ đƣợc sắp vào từng
nhóm dựa trên số lƣợng thông tin về một hay nhiều tính chất kế thừa của cá
thể đó (đƣợc xem nhƣ là các điểm, các biến, các đặc điểm, ) và dựa vào
một tập huấn luyện của các cá thể đã đƣợc đánh nhãn sẵn.
+ Về mặt hình thức, bài toán có thể diễn giải nhƣ sau: cho sẵn một tập
huấn luyện {(x
1
,y), ,(x
n
,y)} cần tạo ra một phân loại h: X→ Y mà ánh xạ một
đối tƣợng x

X vào nhãn phân loại y

Y. Ví dụ, nếu bài toán là lọc spam,
thì x
i
là một biểu diễn nào nó cho một thƣ điện tử y hoặc là "Spam" hoặc
"Không Spam".
Các giải thuật phân loại bằng thống kê thƣờng đƣợc sử dụng trong các
hệ thống nhận dạng mẫu.
1.3. Ƣu điểm của cây quyết định
So với các phƣơng pháp khai phá dữ liệu khác, cây quyết định là
phƣơng pháp có một số ƣu điểm:
 Cây quyết định dễ hiểu. Ngƣời ta có thể hiểu mô hình cây quyết định
sau khi đƣợc giải thích ngắn gọn.
8

9

tối nghĩa bởi những dữ liệu lỗi (noisy). Cây quyết định là một sự lựa chọn tự
nhiên khi nghi ngờ sự tồn tại của các quy tắc ẩn, không rõ ràng.
 Dễ dàng tính toán trong khi phân lớp
Cây quyết định có thể chứa nhiều định dạng, nhƣng trong thực tế, các
thuật toán sử dụng để tạo ra cây quyết định thƣờng tạo ra những cây với số
phân nhánh thấp và các test đơn giản tại từng nút. Những test điển hình là: so
sánh số, xem xét phần tử của một tập hợp và các phép nối đơn giản. Khi thực
thi trên máy tính, những test này chuyển thành các hàm logic và số nguyên là
những toán hạng thực thi nhanh và đơn giản. Đây là một ƣu điểm quan trọng
bởi trong môi trƣờng thƣơng mại, các mô hình dự đoán thƣờng đƣợc sử dụng
để phân lớp hàng triệu thậm trí hàng tỉ bản ghi.
 Khả năng xử lý với cả thuộc tính liên tục và thuộc tính rời rạc
Cây quyết định xử lý “tốt” nhƣ nhau với thuộc tính liên tục và thuộc
tính rời rạc. Tuy rằng với thuộc tính liên tục cần nhiều tài nguyên tính toán
hơn. Những thuộc tính rời rạc đã từng gây ra những vấn đề với mạng neural
và các kỹ thuật thống kê lại thực sự dễ dàng thao tác với các tiêu chuẩn phân
chia (splitting criteria) trên cây quyết định: mỗi nhánh tƣơng ứng với từng
phân tách tập dữ liệu theo giá trị của thuộc tính đƣợc chọn để phát triển tại nút
đó. Các thuộc tính liên tục cũng dễ dàng phân chia bằng việc chọn ra một số
gọi là ngƣỡng trong tập các giá trị đã sắp xếp của thuộc tính đó. Sau khi chọn
đƣợc ngƣỡng tốt nhất, tập dữ liệu phân chia theo test nhị phân của ngƣỡng đó.
 Thể hiện rõ ràng những thuộc tính tốt nhất
Các thuật toán xây dựng cây quyết định đƣa ra thuộc tính mà phân chia
tốt nhất tập dữ liệu đào tạo bắt đầu từ nút gốc của cây. Từ đó có thể thấy
những thuộc tính nào là quan trọng nhất cho việc dự đoán hay phân lớp.
1.4. Ví dụ
David là quản lý của một câu lạc bộ đánh golf nổi tiếng. Anh ta đang có
rắc rối chuyện các thành viên đến hay không đến. Có ngày ai cũng muốn chơi

2
Sunny
Hot
High
Strong
No
3
Overcast
Hot
High
Weak
Yes
4
Rain
Mild
High
Weak
Yes
5
Rain
Cool
Normal
Weak
No
6
Rain
Cool
Normal
Strong
Yes

12
Overcast
Mild
High
Strong
Yes
13
Overcast
Hot
Normal
Weak
Yes
14
Rain
Mild
High
Strong
No 12

Đây là cây quyết định kiểm tra khi nào chơi golf, khi nào không chơi.



Weak
Sunny
High
Outlook
No
Yes
No
Yes
Yes
13

Hình 1.3: Mô tả cây quyết định
1.5.1. Xử lý dữ liệu
Trong bƣớc này dữ liệu đƣợc thu nhập ở dạng thô (nguồn dữ liệu thu
thập có thể là từ các kho dữ liệu hay nguồn thông tin internet). Trong giai
đoạn này dữ liệu cũng đƣợc tiền xử lý để biến đổi và cải thiện chất lƣợng dữ
liệu cho phù hợp với phƣơng pháp khai phá dữ liệu đƣợc chọn lựa.
Công việc cụ thể của bƣớc tiền xử lý dữ liệu gồm các công việc:
 Lọc thuộc tính (Filtering Attributes): Điền giá trị thiếu, làm trơn
dữ liệu nhiễu, định danh hoặc xóa ngoại lai, và khử tính không nhất quán.

Việc tìm các tiêu chí để đánh giá tìm điểm chia là rất quan trọng, chúng
đƣợc xem là một tiêu chuẩn “heuristic” để phân chia dữ liệu. Ý tƣởng chính
trong việc đƣa ra các tiêu chí trên là làm sao cho các tập con đƣợc phân chia
càng trở nên “trong suốt” (tất cả các bộ thuộc về cùng một nhãn) càng tốt.
Chọn thuộc tính sao cho việc phân lớp tập mẫu là tốt nhất. Nhƣ vậy cần
phải có một tiêu chuẩn để đánh giá vấn đề này. Có rất nhiều tiêu chuẩn đƣợc
đánh giá đƣợc sử dụng đó là: Lƣợng thông tin thu thêm IG (Information
Gain), thuật toán ID3 của John Ross Quilan.
Tiêu chuẩn tách 1 chiều (Univariate Splitting Criteria):Nghĩa là tách chỉ
dựa trên 1 thuộc tính.
Xét theo cấu trúc của mẫu dữ liệu thì có 3 tiêu chuẩn:
 Impurity-base Criteria: Khi tất cả các mẫu dữ liệu thuộc về 1
phân lớp, ta gọi đó là Purity. Ngƣợc lại, khi các mẫu dữ liệu tạo ra nhiều phân
lớp thì đó gọi là Impurity.
 Binary criteria Dùng để tạo cây quyết định nhị phân. Các tiêu
chuẩn thƣờng đƣợc sử dụng đối với tiêu chuẩn này là:
- Twoing Criterion
15

- Orthogonal (ORT) Criterion
- Kolmogorov–Smirnov Criterion
- AUC–Splitting Criteria
 Normalized impurity based criteria: Dùng tiêu chuẩn này khi
thuộc tính có nhiều giá trị hiện hành (dĩ nhiên các giá trị này phải thuộc miền
giá trị, ví dụ với 100 mẫu tin có 80 giá trị khác nhau của thuộc tính khi sử
dụng phép chiếu lên thuộc tính).
Tiêu chuẩn tách đa chiều: Khác với tách 1 chiều nghĩa là tách theo 1
thuộc tính, tiêu chuẩn tách đa chiều sử dụng kết hợp nhiều thuộc tính cùng lúc
để phân tách. Tuy nhiên, điều này sẽ ảnh hƣởng tới performance nên ít đƣợc
sử dụng.

làm tăng độ chính xác của cây quyết định bằng cách loại bỏ sự phụ thuộc vào
mức độ lỗi (noise) của dữ liệu đào tạo mang tính chất thống kê, hay những sự
biến đổi mà có thể là đặc tính riêng biệt của dữ liệu đào tạo. Giai đoạn này chỉ
truy cập dữ liệu trên cây quyết định đã đƣợc phát triển trong giai đoạn trƣớc
và quá trình thực nghiệm cho thấy giai đoạn này không tốn nhiều tài nguyên
tính toán, nhƣ với phần lớn các thuật toán, giai đoạn này chiếm khoảng dƣới
1% tổng thời gian xây dựng mô hình phân lớp.
1.6. Phát biểu bài toán
Ngân hàng TMCP Ngoại thƣơng Việt Nam (Vietcombank), đƣợc thành
lập và chính thức đi vào hoạt động ngày 01/4/1963. Trải qua hơn 50 năm xây
dựng và phát triển, Vietcombank đã có những đóng góp quan trọng cho sự ổn
định và phát triển của kinh tế đất nƣớc, phát huy tốt vai trò của một ngân hàng
đối ngoại chủ lực, phục vụ hiệu quả cho phát triển kinh tế trong nƣớc, đồng
thời tạo những ảnh hƣởng quan trọng đối với cộng đồng tài chính khu vực và
toàn cầu.
Ngày 22/09/2011, đã khai trƣơng hoạt động chi nhánh Vietcombank
Việt Trì, tỉnh Phú Thọ. Đây là chi nhánh thứ 76 trong hệ thống và là chi
17

nhánh đầu tiên của Vietcombank trên quê hƣơng đất Tổ cũng nhƣ các tỉnh
trung du vùng núi phía Bắc.
Từ một ngân hàng chuyên doanh phục vụ kinh tế đối ngoại,
Vietcombank ngày nay đã trở thành một ngân hàng đa năng, hoạt động đa lĩnh
vực, cung cấp cho khách hàng đầy đủ các dịch vụ tài chính hàng đầu trong
lĩnh vực thƣơng mại quốc tế; trong các hoạt động truyền thống nhƣ kinh
doanh vốn, huy động vốn, tín dụng, tài trợ dự án… cũng nhƣ mảng dịch vụ
ngân hàng hiện đại, kinh doanh ngoại tệ, các công vụ phái sinh, dịch vụ thẻ,
ngân hàng điện tử…
Trong một vài năm gần đây nền kinh tế của các nƣớc cũng nhƣ ở Việt
Nam đang bị suy thoái, đặc biệt là ngành ngân hàng, khách hàng luôn luôn là