BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG

PHẠM ĐÌNH BÔN

NGHIÊN CỨU CÂY QUYẾT ĐỊNH
VÀ ỨNG DỤNG ĐỂ PHÂN LOẠI
KHÁCH HÀNG VAY VỐN TẠI NGÂN HÀNG
VIETINBANK CHI NHÁNH KON TUM

Chuyên ngành: Hệ Thống Thông Tin
Mã số: 60.48.01.04

TÓM TẮT
LUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TIN

Đà Nẵng - Năm 2017


Luận văn đƣợc hoàn thành tại
Đại học Đà Nẵng

Ngƣời hƣớng dẫn khoa học: TS. PHẠM ANH PHƢƠNG

Phản biện 1: TS. Nguyễn Trần Quốc Vinh
Phản biện 2: TS. Nguyễn Quang Thanh
Luận văn đã đƣợc bảo vệ tại hội đồng chấm luận văn thạc
sĩ Hệ thống thông tin họp tại Đại học Đà Nẵng vào ngày 07
tháng 01 năm 2017.

Có thể tìm hiểu luận văn tại:

Thƣ viện trƣờng Đại học Sƣ phạm Đại học Đà Nẵng
Trung tâm Thông tin học liệu Đại học Đà Nẵng.


1
MỞ ĐẦU
1. Tính cấp thiết của đề tài
Trong gần hai thập kỷ qua, các hệ thống cơ sở dữ liệu đã đem
lại những lợi ích vô cùng to lớn cho nhân loại. Cùng với sự phát triển
của Công nghệ Thông tin và ứng dụng của nó trong đời sống - kinh
tế - xã hội, lƣợng dữ liệu thu thập đƣợc ngày càng nhiều theo thời
gian, làm xuất hiện ngày càng nhiều các hệ thống cơ sở dữ liệu có
kích thƣớc lớn. Ngƣời ta lƣu trữ những dữ liệu này vì cho rằng nó ẩn
chứa những giá trị nhất định nào đó. Tuy nhiên theo thống kê thi chỉ
có một lƣợng nhỏ của những dữ liệu này (khoảng dƣới10%) 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ế đã
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).
Kỹ thuật phát hiện tri thức và khai phá dữ liệu đã và đang
đƣợc nghiên cứu, ứng dụng trong nhiều lĩnh vực khác nhau trên thế
giới, tại Việt Nam kỹ thuật này còn tƣơng đối mới mẻ tuy nhiên cũng
đang đƣợc nghiên cứu và bắt đầu đƣa vào một số ứng dụng thực tế.
Vì vậy, hiện nay ở nƣớc ta vấn đề phát hiện tri thức và khai phá dữ
liệu đang thu hút đƣợc sự quan tâm của nhiều ngƣời và nhiều công ty

phát triển ứng dụng Công nghệ Thông tin. Đƣợc đánh giá sẽ tạo ra
cuộc cách mạng trong thế kỷ 21, khai phá dữ liệu sẽ ngày càng đƣợc
ứng dụng phổ biến trong các lĩnh vực kinh tế, xã hội: ngân hàng,
truyền thông, quảng cáo…


2
Có nhiều phƣơng pháp phân lớp đƣợc đề xuất, tuy nhiên
không có phƣơng pháp tiếp cận phân loại nào là tối ƣu và chính xác
hơn hẳn những phƣơng pháp khác. Dù sao với mỗi phƣơng pháp có
một lợi thế và bất lợi riêng khi sử dụng. Một trong những công cụ
khai phá tri thức hiệu quả hiện nay là sử dụng cây quyết định để tìm
ra các luật phân lớp. 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,
tôi đã chọn đề tài “Nghiên cứu cây quyết định và ứng dụng để
phân loại khách hàng vay vốn tại ngân hàng Vietinbank chi
nhánh Kon Tum”.
2. Mục tiêu nghiên cứu
- Nghiên cứu các thuật toán xây dựng cây quyết định ID3.
- Áp dụng mô hình cây quyết định (ID3: Decision Tree) vào
việc phân loại khách hàng vay vốn tại ngân hàng Vietinbank
chi nhánh Kon Tum.
3. Đối tƣợng và phạm vi nghiên cứu
 Đối tượng nghiên cứu
- Bài toán phân lớp dữ liệu trong khai phá dữ liệu;
- Cây quyết định;
 Phạm vi nghiên cứu
- Nghiên cứu về thuật toán ID3;
- Phân lớp dữ liệu khách hàng, cụ thể: khách hàng vay vốn tại
ngân hàng Vietinbank chi nhánh Kon Tum.

4. Phƣơng pháp nghiên cứu
- Đọc hiểu tài liệu.
- Cài đặt ứng dụng chạy trên hệ điều hành Window
5. Cấu trúc luận văn
Báo cáo luận văn gồm các phần chính nhƣ sau:
MỞ ĐẦU


3
CHƢƠNG 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU
CHƢƠNG 2. CÂY QUYẾT ĐỊNH TRONG KHAI PHÁ DỮ LIỆU
CHƢƠNG 3. ỨNG DỤNG CÂY QUYẾT ĐỊNH TRONG PHÂN
LOẠI KHÁCH HÀNG VAY VỐN TẠI NGÂN HÀNG
VIETINBANK CHI NHÁNH KON TUM
KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN.

CHƯƠNG 1
TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU
Chƣơng này trình bày sơ lƣợc về khai phá dữ liệu, ứng dụng
của khai phá dữ liệu, các phƣơng pháp khai phá dữ liệu thông dụng
và ứng dụng của khai phá dữ liệu trong lĩnh vực tài chính ngân hàng.
1.1. GIỚI THIỆU VỀ KHAI PHÁ DỮ LIỆU
1.1.1. Khám phá tri thức
Quá trình khám phá dữ liệu gồm các bƣớc cơ bản sau đây
[1][2][9]:
Bƣớc 1: Xác định vấn đề và lựa chọn nguồn dữ liệu (Problem
Understanding anh Data Understanding)
Bƣớc 2: Chuẩn bị dữ liệu (Data preparation)
Bƣớc 3: Khai phá dữ liệu (Data Mining)
Bƣớc 4: Đánh giá mẫu (Partern Evalution)

Bƣớc 5: Biểu diễn tri thức và triển khai (Knowlegde
presentation and Deployment)
Tóm lại: KDD là một quá trình kết xuất ra tri thức từ kho dữ
liệu mà trong đó khai phá dữ liệu là công đoạn quan trọng nhất [2],
[3],[8].


4

Hình 1.1: Quá trình phát hiện tri thức trong CSDL
1.1.2. Khai phá dữ liệu
Khai phá dữ liệu đƣợc dùng để mô tả quá trình phát hiện ra tri
thức trong CSDL. Quá trình khai phá dữ liệu bao gồm các giai đoạn
[1][3]:
Giai đoạn 1: Gom dữ liệu
Giai đoạn 2: Trích lọc dữ liệu
Giai đoạn 3: Làm sạch, tiền xử lý và chuẩn bị trước dữ
Giai đoạn 4: Chuyển đổi dữ liệu
Giai đoạn 5: Phát hiện và trích mẫu dữ
Giai đoạn 6: Đánh giá kết quả mẫu
Quá khai phá dữ liệu đƣợc mô hình hóa một cách tổng quát
nhƣ hình vẽ dƣới đây [2][7]:

Hình 1.2: Kiến trúc điển hình của hệ thống khai phá dữ liệu


5
1.2. ỨNG DỤNG CỦA KHAI PHÁ DỮ LIỆU
Data Mining tuy là một hƣớng tiếp cận mới nhƣng thu hút đƣợc
rất nhiều sự quan tâm của các nhà nghiên cứu và phát triển nhờ vào

những ứng dụng thực tiễn của nó. Sau đây là một số lĩnh vực mà
Data mining đang đƣợc ứng dụng rộng rãi:
 Phân tích dữ liệu tài chính (Financial Data Analysis)
 Công nghiệp bán lẻ (Retail Industry)
 Công nghiệp viễn thông (Telecommunication Industry)
 Phân tích dữ liệu sinh học (Biological Data Analysis)
 Phát hiện xâm nhập (Intrusion Detection)
 Một số ứng dụng trong khoa học (Scientific Applications)
1.3. CÁC PHƯƠNG PHÁP KHAI PHÁ DỮ LIỆU THÔNG
DỤNG
1.3.1. Phân lớp (Classification)
Ngày nay phân lớp dữ liệu (classification) là một trong những
hƣớng nghiên cứu chính của khai phá dữ liệu. Thực tế đặt ra nhu
cầu là từ một cơ sở dữ liệu với nhiều thông tin ẩn con ngƣời có thể
trích rút ra các quyết định nghiệp vụ thông minh. Phân lớp và dự
đoán là hai dạng của phân tích dữ liệu nhằm trích rút ra một mô hình
mô tả các lớp dữ liệu quan trọng hay dự đoán xu hƣớng dữ liệu
tƣơng lai. Phân lớp dự đoán giá trị của những nhãn xác định
(categorical label) hay những giá trị rời rạc (discrete value), có nghĩa
là phân lớp thao tác với những đối tƣợng dữ liệu mà có bộ giá trị là
biết trƣớc. Trong khi đó, dự đoán lại xây dựng mô hình với các hàm
nhận giá trị liên tục.
Quá trình phân lớp dữ liệu gồm hai bƣớc [4][5]:
Bƣớc thứ nhất (Learning)
Quá trình học nhằm xây dựng một mô hình mô tả một tập các
lớp dữ liệu hay các khái niệm định trƣớc. Đầu vào của quá trình này


6
là một tập dữ liệu có cấu trúc đƣợc mô tả bằng các thuộc tính và

đƣợc tạo ra từ tập các bộ giá trị của các thuộc tính đó. Mỗi bộ giá trị
đƣợc gọi chung là một phần tử dữ liệu (data tuple), có thể là các mẫu
(sample), ví dụ (example), đối tƣợng (object), bản ghi (record) hay
trƣờng hợp (case). Luận văn sử dụng các thuật ngữ này với nghĩa
tƣơng đƣơng. Trong tập dữ liệu này, mỗi phần tử dữ liệu đƣợc giả sử
thuộc về một lớp định trƣớc, lớp ở đây là giá trị của một thuộc tính
đƣợc chọn làm thuộc tính gán nhãn lớp hay thuộc tính phân lớp
(class label attribute). Đầu ra của bƣớc này thƣờng là các quy tắc
phân lớp dƣới dạng luật dạng if-then, cây quyết định, công thức
logic, hay mạng nơron. Quá trình này đƣợc mô tả nhƣ trong hình 1.3

Hình 1.3 : Quá trình phân lớp dữ liệu - (a) Bƣớc xây dựng mô hình
phân lớp
Bƣớc thứ hai (Classification)
Bƣớc thứ hai dùng mô hình đã xây dựng ở bƣớc trƣớc để phân
lớp dữ liệu mới. Trƣớc tiên độ chính xác mang tính chất dự đoán của
mô hình phân lớp vừa tạo ra đƣợc ƣớc lƣợng. Holdout là một kỹ
thuật đơn giản để ƣớc lƣợng độ chính xác đó. Kỹ thuật này sử dụng
một tập dữ liệu kiểm tra với các mẫu đã đƣợc gán nhãn lớp. Các mẫu
này đƣợc chọn ngẫu nhiên và độc lập với các mẫu trong tập dữ liệu
đào tạo. Độ chính xác của mô hình trên tập dữ liệu kiểm tra đã đƣa là
tỉ lệ phần trăm các các mẫu trong tập dữ liệu kiểm tra đƣợc mô hình


7
phân lớp đúng (so với thực tế).

Hình 1.4: Quá trình phân lớp dữ liệu - (b1)Ƣớc lƣợng độ chính xác
của mô hình


Hình 1.5: Quá trình phân lớp dữ liệu - (b2) Phân lớp dữ liệu mới
Có thể liệt kê ra đây các kỹ thuật phân lớp đã đƣợc sử dụng trong
những năm qua:
 Phân lớp cây quyết định (Decision tree classification)
 Bộ phân lớp Bayesian (Bayesian classifier)
 Mô hình phân lớp K-hàng xóm gần nhất (K-nearest neighbor
classifier)
 Mạng nơron
 Phân tích thống kê
 Các thuật toán di truyền


8
 Phƣơng pháp tập thô (Rough set Approach)
1.3.2. Phân cụm (Clustering)
Phân cụm là kỹ thuật rất quan trọng trong khai phá dữ liệu, nó
thuộc lớp các phƣơng pháp Unsupervised Learning trong Machine
Learning. Có rất nhiều định nghĩa khác nhau về kỹ thuật này, nhƣng
về bản chất ta có thể hiểu phân cụm là các qui trình tìm cách nhóm
các đối tƣợng đã cho vào các cụm (clusters), sao cho các đối tƣợng
trong cùng 1 cụm tƣơng tự (similar) nhau và các đối tƣợng khác cụm
thì không tƣơng tự (Dissimilar) nhau.
Mục đích của phân cụm là tìm ra bản chất bên trong các nhóm
của dữ liệu.
1.3.3. Luật kết hợp (Association Rules)
Khai phá luật kết hợp đƣợc thực hiện qua 2 bƣớc:
 Bƣớc 1 : Tìm tất cả các tập mục phổ biến, một văn bản phổ
biến đƣợc xác định qua độ hỗ trợ và thỏa mãn độ hỗ trợ cực tiểu.
 Bƣớc 2: Sinh ra các luật kết hợp mạnh từ tập mục phổ biến,
các luật phải thỏa mãn độ hỗ trợ cực tiểu và độ tin cậy cực tiểu.

1.4. ỨNG DỤNG KHAI PHÁ DỮ LIỆU TRONG LĨNH VỰC
NGÂN HÀNG
Ngành công nghiệp ngân hàng trên toàn thế giới đã trải qua
những thay đổi to lớn trong cách thức kinh doanh. Với việc thực hiện
các nhiệm vụ kinh doanh đặc thù của mình trong thời gian gần đây,
các ngân hàng đã có sự thay đổi lớn đó là chấp nhận và áp dụng công
nghệ thông vào việc kinh doanh của mình. Nhƣ một kết quả hiển
nhiên, việc thực hiện giao dịch đã trở nên dễ dàng và đồng thời khối
lƣợng dữ liệu từ các giao dịch này đã tăng lên đáng kể. Nó là vƣợt
quá khả năng của con ngƣời để phân tích số lƣợng dữ liệu thô khổng
lồ này và chuyển đổi nó thành tri thức hữu ích cho các tổ chức.
1.4.1. Marketing


9
Một trong những lĩnh vực đƣợc ứng dụng rộng rãi nhất cho
ngành ngân hàng của kỹ thuật khai phá dữ liệu đó là lĩnh vực quảng bá
sản phẩm. Bộ phận tiếp thị và bán hàng của các Ngân hàng có thể sử
dụng kỹ thuật khai phá dữ liệu để phân tích cơ sở dữ liệu về khách hàng.
1.4.2. Quản lý rủi ro
Khai phá dữ liệu đƣợc sử dụng rộng rãi để quản lý rủi ro trong
ngành công nghiệp ngân hàng.
1.4.1. Phát hiện gian lận
Một lĩnh vực khác trong khai phá dữ liệu có thể đƣợc sử dụng
trong ngành công nghiệp ngân hàng là việc phát hiện gian lận.
1.4.1. Quản trị quan hệ khách hàng
Tìm kiếm khách hàng, tăng giá trị của khách hàng và duy trì
khách hàng.
1.5. KẾT LUẬN
Trong chƣơng này, luận văn đã giới thiệu tổng quan về khai

phá dữ liệu, ứng dụng của khai phá dữ liệu, một số phƣơng pháp khai
phá dữ liệu thông dụng. Trong chƣơng sau, luận văn sẽ trình bày nội
dung lý thuyết và ứng dụng của thuật toán khai phá dữ liệu thông
dụng : Thuật toán cây quyết định ID3. Đó là một thuật toán đƣợc ứng
dụng để khai phá dữ liệu trong các lĩnh vực khác nhau, đặc biệt trong
lĩnh vực ngân hàng.
CHƯƠNG 2
CÂY QUYẾT ĐỊNH TRONG KHAI PHÁ DỮ LIỆU
2.1. TỔNG QUAN VỀ PHƯƠNG PHÁP HỌC THEO CÂY
QUYẾT ĐỊNH
2.1.1. Giới thiệu chung
Trong lĩnh vực học máy, cây quyết định là một kiểu mô hình
dự báo (predictive model), nghĩa là một ánh xạ từ các quan sát về


10
một sự vật/hiện tƣợng tới các kết luận về giá trị mục tiêu của sự
vật/hiện tƣợng. Mỗi một nút trong (internal node) tƣơng ứng với một
biến; đƣờng nối giữa nó với nút con của nó thể hiện một giá trị cụ thể
cho biến đó. Mỗi nút lá đại diện cho giá trị dự đoán của biến mục
tiêu, cho trƣớc các giá trị của các biến đƣợc biểu diễn bởi đƣờng đi
từ nút gốc tới nút lá đó. Kỹ thuật học máy dùng trong cây quyết định
đƣợc gọi là học bằng cây quyết định, hay chỉ gọi với cái tên ngắn
gọn là cây quyết định[6].
2.1.2. Các kiểu cây quyết định
Cây quyết định còn có hai tên khác:
 Cây hồi quy (Regression tree): ƣớc lƣợng các hàm giá có giá
trị là số thực thay vì đƣợc sử dụng cho các nhiệm vụ phân loại. (ví
dụ: ƣớc tính giá một ngôi nhà hoặc khoảng thời gian một bệnh nhân
nằm viện)

 Cây phân loại (Classification tree): nếu y là một biến phân
loại nhƣ: giới tính (nam hay nữ), kết quả của một trận đấu (thắng hay
thua).
2.1.3. Ƣu điểm 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.
 Việc chuẩn bị dữ liệu cho một cây quyết định là cơ bản hoặc
không cần thiết. Các kỹ thuật khác thƣờng đòi hỏi chuẩn hóa dữ liệu,
cần tạo các biến phụ (dummy variable) và loại bỏ các giá trị rỗng.
 Cây quyết định có thể xử lý cả dữ liệu có giá trị bằng số và
dữ liệu có giá trị là tên thể loại. Các kỹ thuật khác thƣờng chuyên để
phân tích các bộ dữ 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ỉ


11
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.

2.2. CÁC THUẬT TOÁN
2.2.1. Thuật toán CLS
Thuật toán này đƣợc Holland và Hint giới thiệu trong Concept
learning System (CLS) vào những năm 50 của thế kỷ 20[4]. Thuật
toán CLS đƣợc thiết kế theo chiến lƣợc chia để trị từ trên xuống. Nó
gồm các bƣớc sau:
1. Tạo một nút T, nút này gồm tất cả các mẫu của tập huấn
luyện.
2. Nếu tất cả các mẫu trong T có thuộc tính quyết định mang
giá trị "yes" (hay thuộc cùng một lớp), thì gán nhãn cho nút T là
"yes" và dừng lại. T lúc này là nút lá.
3. Nếu tất cả các mẫu trong T có thuộc tính quyết định mang
giá trị "no" (hay thuộc cùng một lớp), thì gán nhãn cho nút T là "no"
và dừng lại. T lúc này là nút lá.
4. Trƣờng hợp ngƣợc lại các mẫu của tập huấn luyện thuộc cả
hai lớp "yes" và "no" thì:
 Chọn một thuộc tính X trong tập thuộc tính của tập mẫu dữ


12
liệu , X có các giá trị vi,v2, ...vn.
 Chia tập mẫu trong T thành các tập con T1, T2,..,Tn. chia
theo giá trị của X.
 Tạo n nút con T; (i=1,2.n) với nút cha là nút T.
 Tạo các nhánh nối từ nút T đến các nút T; (i=1,2.n) là các
thuộc tính của X.
5. Thực hiện lặp cho các nút con T:(i =1,2..n) và quay lại bƣớc
2.
2.2.1. Thuật toán ID3
Thuật toán ID3 đƣợc phát biểu bởi Quinlan (trƣờng đại học

Syney, Australia) và đƣợc công bố vào cuối thập niên 70 của thế kỷ
20[4]. Sau đó, thuật toán ID3 đƣợc giới thiệu và trình bày trong mục
Induction on decision trees, machine learning năm 1986. ID3 đƣợc
xem nhƣ là một cải tiến của CLS với khả năng lựa chọn thuộc tính
tốt nhất để tiếp tục triển khai cây tại mỗi bƣớc. ID3 xây dựng cây
quyết định từ trên- xuống (top -down).
2.2.2. Thuật toán C4.5
Thuật toán C4.5 do Quinlan phát triển vào năm 1996 [1] [2]
[3] [4]. Thuật toán C4.5 là một thuật toán đƣợc cải tiến từ thuật toán
ID3 với việc cho phép xử lý trên tập dữ liệu có các thuộc tính số
(numeric atributes) và và làm việc đƣợc với tập dữ liệu bị thiếu và bị
nhiễu. Nó thực hiện phân lớp tập mẫu dữ liệu theo chiến lƣợc ƣu tiên
theo chiều sâu (Depth - First).
Một số cài tiến của thuật toán C4.5:
1. Làm việc với thuộc tính đa trị
2. Làm việc với dữ liệu bị thiếu
2.2.3. Thuật toán SLIQ[5]
Thuật toán SLIQ (Supervised Learning In Quest) đƣợc gọi là
thuật toán phân lớp leo thang nhanh. Thuật toán này có thể áp dụng
cho cả hai kiểu thuộc liên tục và thuộc tính rời rạc[4][5].


13
Thuật toán này có sử dụng kỹ thuật tiền xử lý phân loại(Pre
sorting) trƣớc khi xây dựng cây, do đó giải quyết đƣợc vấn đề bộ nhớ
cho thuật toán ID3.
Thuật toán SLIQ có sử dụng giải thuật cắt tỉa cây hữu hiệu.
Thuật toán SLIQ có thể phân lớp rất hiệu quả đối với các tập
dữ liệu lớn và không phụ thuộc vào số lƣợng lớp, số lƣợng thuộc tính
và số lƣợng mẫu trong tập dữ liệu.

2.3. VÍ DỤ MINH HỌA
2.3.1. Phát biểu bài toán
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 golf nhƣng số nhân viên câu lạc bộ lại
không đủ phục vụ. Có hôm, không hiểu vì lý do gì mà chẳng ai đến
chơi, và câu lạc bộ lại thừa nhân viên.
Mục tiêu của David là tối ƣu hóa số nhân viên phục vụ mỗi
ngày bằng cách dựa theo thông tin dự báo thời tiết để đoán xem khi
nào ngƣời ta sẽ đến chơi golf. Để thực hiện điều đó, anh cần hiểu
đƣợc tại sao khách hàng quyết định chơi và tìm hiểu xem có cách
giải thích nào cho việc đó hay không.
Vậy là trong hai tuần, anh ta thu thập thông tin về: Trời
(outlook) (nắng (sunny), nhiều mây (overcast) hoặc mƣa (raining).
Nhiệt độ (temperature) bằng độ F. Độ ẩm (humidity). Có gió mạnh
(windy) hay không. Và là số ngƣời đến chơi golf vào hôm đó. David
thu đƣợc một bộ dữ liệu gồm 14 dòng và 5 cột.


14
Bảng 2.1: Dữ liệu chơi golf
Ngày
D1
D2
D3
D4
D5
D6
D7
D8

D9
D10
D11
D12
D13
D14

Quang cảnh
Nắng
Nắng
Âm u
Mƣa
Mƣa
Mƣa
Âm u
Nắng
Nắng
Mƣa
Nắng
Âm u
Âm u
Mƣa

Nhiệt độ
Nóng
Nóng
Nóng
Ấm áp
Mát
Mát

Mát
Ấm áp
Mát
Ấm áp
Ấm áp
Ấm áp
Nóng
Ấm áp

Độ ẩm
Cao
Cao
Cao
Cao
TB
TB
TB
Cao
TB
TB
TB
Cao
TB
Cao

Gió
Nhẹ
Mạnh
Nhẹ
Nhẹ

Nhẹ
Mạnh
Mạnh
Nhẹ
Nhẹ
Nhẹ
Mạnh
Mạnh
Nhẹ
Mạnh

Chơi Tennis
Không
Không
Có
Có
Có
Không
Có
Không
Có
Có
Có
Có
Có
Không

Sau đó, để giải quyết bài toán của David, ngƣời ta đã đƣa ra
một mô hình cây quyết định.


Hình 2.2: Mô hình cây quyết định chơi golf
Cây quyết định là một mô hình dữ liệu mã hóa phân bố của
nhãn lớp theo các thuộc tính dùng để dự đoán. Đây là một đồ thị
có hƣớng phi chu trình dƣới dạng một cây. Nút gốc (nút nằm trên
đỉnh) đại diện cho toàn bộ dữ liệu. Thuật toán cây phân loại phát
hiện ra rằng cách tốt nhất để giải thích biến phụ thuộc, play
(chơi), là sử dụng biến Outlook. Phân loại theo các giá trị của
biến Outlook, ta có ba nhóm khác nhau: Nhóm ngƣời chơi golf


15
khi trời nắng, nhóm chơi khi trời nhiều mây, và nhóm chơi khi
trời mƣa.
2.3.2. Minh họa xây dựng cây quyết định
Cây quyết định cần tìm bằng cách minh họa

Hình 2.7: Cây quyết định cần tìm.
2.1. KẾT CHƯƠNG
Chƣơng 2 trình bày tổng quan về khai phá dữ liệu bằng hình
thức phân lớp với cây quyết định, bao gồm khái niệm phân lớp và ƣu
điểm cây quyết định. Nghiên cứu thuật toán khai phá dữ liệu, trong
đó nghiên cứu sâu về thuật toán ID3 làm tiền đề cho việc nghiên cứu
thực nghiệm, đồng thời đƣa ra những khó khăn trong quá trình sử
dụng thuật toán ID3. Các khó khăn này cần phải đƣợc giải quyết
trong khai phá dữ liệu. Trong chƣơng sau, luận văn sẽ trình bày một
ứng dụng cụ thể mà ngân hàng có thể áp dụng để phân loại khách
hàng của mình, căn cứ vào kết quả ngân hàng sẽ có thêm sự hỗ trợ để
quyết định có cho khách hàng vay vốn hay không.



16
CHƯƠNG 3
ỨNG DỤNG CÂY QUYẾT ĐỊNH TRONG PHÂN LOẠI
KHÁCH HÀNG VAY VỐN TẠI NGÂN HÀNG VIETINBANK
CHI NHÁNH KON TUM
3.1. GIỚI THIỆU QUY TRÌNH TÍN DỤNG TẠI NGÂN HÀNG
VIETINBANK CHI NHÁNH KON TUM
3.1.1. Tổng quan về quy trình tín dụng:
a. Khái niệm:
Quy trình tín dụng là bảng tổng hợp mô tả công việc của ngân
hàng từ khi tiếp nhận hồ sơ vay vốn của khách hàng cho đến khi
quyết định cho vay, giải ngân, thu nợ và thanh lý hợp đồng tín dụng.
b. Vai trò:
Việc xác lập một quy trình tín dụng và không ngừng hoàn
thiện nó đặc biệt quan trọng đối với một ngân hàng thƣơng mại:
 Về mặt hiệu quả, một quy trình tín dụng hợp lý sẽ giúp cho
ngân hàng nâng cao chất lƣợng tín dụng và giảm thiểu rủi ro tín
đụng.
 Về mặt quản lý, quy trình tín dụng có tác dụng:
+ Làm cơ sở cho việc phân định quyền, trách nhiệm cho từng
bộ phận trong hoạt động tín dụng.
+ Làm cơ sở để thiết lập các hồ sơ, thủ tục vay vốn về mặt
hành chính.
+ Chỉ rõ mối quan hệ giữa các bộ phận liên quan trong hoạt
động tín dụng.
c. Nội dung cơ bản của quy trình tín dụng:
3.1.2. Quy trình tín dụng của ngân hàng công thƣơng Việt
Nam – Vietinbank
Bƣớc 1: Phỏng vấn và hƣớng dẫn khách hàng lập hồ sơ đề
nghị vay vốn

 Phỏng vấn và trao đổi với khách hàng:
 Hƣớng dẫn khách hàng lập, tiếp nhận và đối chiếu hồ sơ đề
nghị vay vốn
Sau khi trao đổi thông tin với khách hàng, nếu khách hàng
chấp thuận, CBTD hƣớng dẫn khách hàng lập và gửi hồ sơ vay vốn.
Lƣu ý: Hồ sơ phải do khách hàng vay vốn lập, cán bộ tín dụng
khôn2 đƣợc lập thay.


17
Bƣớc 2. Thẩm định mức độ đáp ứng các điều kiện vay vốn
Bƣớc 3. Xác định số tiền, phƣơng thức, lãi suất, thời hạn cho
vay; định kỳ hạn nợ và xem xét điều kiện thanh toán
Bƣớc 4. Lập tờ trình thẩm định cho vay, soạn thảo hợp đồng
tín dụng, hợp đồng bảo đảm tiền vay và trình phê duyệt cho vay
Bƣớc 5. Công chứng hoặc chứng thực ; đăng ký gia dịch bảo
đảm; giao nhận giấy tờ của tài sản bảo đảm và hoặc tài sản bảo đảm.
Bƣớc 6. Giải ngân, thu nợ gốc, lãi và kiểm tra, giám sát món
vay
Bƣớc 7. Cơ cấu lại thời hạn trả nợ
Bƣớc 8. Giải chấp tài sản bảo đảm, thanh lý hợp đồng tín
dụng, hợp đồng tài sản bảo đảm.
3.2. THUẬT TOÁN ID3
3.2.1. Giới thiệu về thuật toán ID3
Giải thuật quy nạp cây ID3 (gọi tắt là ID3) là một giải thuật
học đơn giản nhƣng tỏ ra thành công trong nhiều lĩnh vực. ID3 là
một giải thuật hay vì cách biểu diễn tri thức học đƣợc của nó, tiếp
cận của nó trong việc quản lý tính phức tạp, heuristic của nó dùng
cho việc chọn lựa các khái niệm ứng viên, và tiềm năng của nó đối
với việc xử lý dữ liệu nhiễu.

ID3 biểu diễn các khái niệm (concept) ở dạng các cây quyết
định (decision tree). Biểu diễn này cho phép chúng ta xác định phân
loại của một đối tƣợng bằng cách kiểm tra các giá trị của nó trên một
số thuộc tính nào đó.
Nhƣ vậy, nhiệm vụ của giải thuật ID3 là học cây quyết định từ
một tập các mẫu rèn luyện (training example) hay còn gọi là dữ liệu
rèn luyện (training data). Hay nói khác hơn, giải thuật có:
Đầu vào: Một tập hợp các mẫu. Mỗi mẫu bao gồm các thuộc
tính mô tả một tình huống, hay một đối tƣợng nào đó, và một giá trị phân
loại của nó.
Đầu ra: Cây quyết định có khả năng phân loại đúng đắn
các mẫu trong tập dữ liệu rèn luyện, và hy vọng là phân loại đúng
cho cả các mẫu chƣa gặp trong tƣơng lai.
3.2.2. Giải thuật ID3 xây dựng cây quyết định từ trên
xuống
ID3 xây dựng cây quyết định (cây QĐ) theo cách từ trên
xuống. Lƣu ý rằng đối với bất kỳ thuộc tính nào, chúng ta cũng có


18
thể phân vùng tập hợp các mẫu rèn luyện thành những tập con tách
rời, mà ở đó mọi mẫu trong một phân vùng (partition) có một giá trị
chung cho thuộc tính đó. ID3 chọn một thuộc tính để kiểm tra tại nút
hiện tại của cây và dùng cách kiểm tra này để phân vùng tập hợp các
mẫu; thuật toán khi đó xây dựng theo cách đệ quy một cây con cho
từng phân vùng. Việc này tiếp tục cho đến khi mọi thành viên của
phân vùng đều nằm trong cùng một lớp; lớp đó trở thành nút lá của
cây.
3.2.3. Thuộc tính dùng để phân loại cây quyết định
Quinlan (1983) là ngƣời đầu tiên đề xuất việc sử dụng lý

thuyết thông tin để tạo ra các cây quyết định và công trình của ông là
cơ sở cho phần trình bày ở đây. Lý thuyết thông tin của Shannon
(1948) cung cấp khái niệm entropy để đo tính thuần nhất (hay ngƣợc
lại là độ pha trộn) của một tập hợp.
1. Entropy đo tính thuần nhất của tập huấn luyện
2. Lƣợng thông tin thu đƣợc đo mức độ giảm entropy mong
đợi
3. Tìm kiếm không gian giả thuyết trong ID3
4. Đánh giá hiệu suất của cây quyết định
5. Chuyển cây về các luật
6. Ứng dụng của giải thuật ID3
3.3. . ỨNG DỤNG ID3 ĐỂ PHÂN LỚP ĐỐI TƯỢNG KHÁCH
HÀNG VAY VỐN
3.3.1. Quy trình thực nghiệm
Mô hình thực nghiệm của chƣơng trình hệ thống quyết định
cho vay vốn ngân hàng.

Hình 3.6: Quy trình thực nghiệm của quy trình quyết định cho vay vốn


19
- Quy trình thực nghiệm với 621 mẫu dữ liệu đƣợc nạp vào hệ
thống dƣới dạng file excel Dulieuvayvon.xlsx.
- Sau khi dữ liệu đƣợc nạp vào hệ thống ta thực hiện lọc những
dữ liệu trùng và những mẫu dữ liệu mâu thuẫn với nhau ta đƣợc bộ
dữ liệu sau khi lọc.
- Sau đó dùng thuật toán ID3 thực hiện đối với bộ dữ liệu sau
khi lọc bỏ nhũng mẫu trùng và mâu thuẫn ta đƣợc mô hình cây quyết
định ID3 và tập luật sinh ra từ bộ dữ liệu.
- Nạp bộ dữ liệu khách hàng mới chƣa phân loại cho vay vốn

vào hệ thống. Từ tập luật và mô hình cây quyết định ID3 tập dữ liệu
khách hàng mới sẽ đƣợc phân lớp dữ liệu là có đƣợc cho vay vốn hay
không.
3.3.1. Giới thiệu bài toán
Chúng ta đang sống trong thế giới thừa thông tin thiếu tri thức
– đó là nhận định của nhiều ngƣời trong thời đại bùng nổ thông tin
hiện nay.
Sử dụng phƣơng pháp khai phá tri thức từ dữ liệu để dự đoán
rủi ro tín dụng là một phƣơng pháp mới nhằm nâng cao chất lƣợng
tín dụng của Ngân hàng.
Rủi ro tín dụng có thể đƣợc hiểu là nguy cơ một ngƣời đi vay
không thể trả đƣợc gốc và/hoặc lãi đúng thời hạn quy định.
Trong phạm vi luận văn này tôi đã tập trung nghiên cứu đối
với công tác tín dụng tiêu dùng của khách hàng với tập mẫu dữ liệu
bao gồm 621 mẫu dữ liệu khách hàng vay vốn tại ngân hàng
Vietinbank chi nhánh Kon Tum. Dựa vào tập mẫu
Dulieuvayvon.xlsx sẽ xây dựng mô hình cây quyết định, từ cây quyết
định rút ra các luật quyết định. Dựa vào các luật quyết định đó ta sẽ
phân lớp đƣợc tập dữ liệu mới (dữ liệu về khách hàng xin vay tiêu
dùng, nhƣng chƣa đƣợc phân lớp) và tập dữ liệu sau khi đƣợc phân
lớp sẽ hỗ trợ cho các cán bộ tín dụng ra quyết định cho khách hàng
vay hay không.
3.3.1. Đặc tả dữ liệu
Luận văn sử dụng tập dữ liệu: Dulieuvayvon .xlsx gồm 621
đối tƣợng với 10 thuộc tính điều kiện và thuộc tính quyết định
“result” quyết định một khách hàng là đƣợc vay và không đƣợc vay.
Các thuộc tính và giá trị của các thuộc tính của tập dữ liệu
Dulieuvayvon đƣợc mô tả trong bảng sau:



20
Thứ tự

Thuộc tính

Giá trị

Ý nghĩa

1

Tuoi

Tre, TrungNien, Gia

Trẻ, Trung niên, già

2

Gioitinh

Nam, Nu

Nam, Nữ

3

Hokhau

NongThon, ThiTran,

NgoaiO, ThanhPho

Nông thôn, Thị trấn,
Ngoại ô, Thành phố

4

Thunhap

Thap,Trungbinh, Cao

Thấp, trung bình, cao

5

Kethon

Co, Khong

Có, không

SoCon

Khongcon, Motcon,
Haicon, Bacon

Không con, Một con,
Hai con, Ba con

7


XeOto

Co, Khong

Có, không

8

TaikhoaTietkiem

Co, Khong

Có, không

6

9

TaikhoanHientai

Co, Khong

Có, không

10

TaisanThechap

Co, Khong


Có, không

11

RESULT(Chovay)

True, false

Có (True), Không (False)

Bảng 3.7: Bảng thuộc tính tập dữ liệu ngân hàng
3.3.2. Cài đặt thuật toán
Ứng dụng này đƣợc viết trong môi trƣờng Visual Studio
2010, viết bằng ngôn ngữ lập trình C#. Ứng dụng này tập trung vào
xây dựng và đƣa ra các quyết định và các tập luật của thuật toán
ID3. Từ các cây quyết định hay các luật quyết định rút ra từ cây
quyết định sẽ hỗ trợ cho các cán bộ tín dụng trong ngân hàng quyết
định cho khách hàng đƣợc vay hay không.
 Cài đặt ứng dụng
Chƣơng trình:
- Đầu vào: Dữ liệu đầu vào dạng file Excel Dulieuvayvon.xlsx
là tập các dữ liệu mẫu chứa các thông tin đƣợc sử dụng trong
mô tả bài toán.
- Đầu ra: Đầu ra của chƣơng trình là tập các luật dự đoán sắp
xếp phân loại khách hàng vay vốn, mô hình cây quyết định
ID3 với tập dữ liệu mẫu đầu vào và ứng dụng phân loại khách
hàng vay vốn cho cán bộ tín dụng.
Chƣơng trình gồm các mô đun chính nhƣ sau:
- Đọc dữ liệu đầu vào từ file excel( Tập dữ liệu mẫu gồm 621

đối tƣợng Dulieuvayvon.xlsx)


21

Hình 3.9: Thực hiện nạp dữ liệu vào hệ thống
- Kiểm tra dữ liệu
+ Chuẩn hóa dữ liệu( Lọc ra và loại những dữ liệu
trùng, những bộ dữ liệu mâu thuẫn)

Hình 3.10: Chuẩn hóa dữ liệu đầu vào
- Tạo luật đƣợc sinh ra từ tập dữ liệu mẫu sau khi đã chuẩn hóa


22

Hình 3.13: Kết quả các luật đƣợc sinh ra với thuật toán ID3
- Tạo cây ID3 với bộ dữ liệu Dulieuvayvon.xlsx( Gồm 621 đối
tƣợng)

Hình 3.14: Kết quả cây ID3 với bộ dữ liệu Dulieuvayvon.xlsx
- Ứng dụng ID3 quyết định cho vay vốn

Hình 3.17: Kết quả sau khi thực hiện quyết định có cho khách hàng
mới vay hay không


23
3.4. KẾT CHƯƠNG
Trong chƣơng này đã phát biểu bài toán để kiểm chứng các

thuật toán xây dựng cây quyết định ở chƣơng 2 trên bộ dữ liệu mẫu
Dulieuvayvon.xlsx. Đồng thời cài đặt chƣơng trình hỗ trợ cán bộ tín
dụng ra quyết định vay vốn. Dựa vào mô hình cây quyết định (các
luật quyết định) đã đƣợc xây dựng, phân lớp các mẫu dữ liệu khách
hàng mới.
KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN
Khai phá dữ liệu là một lĩnh vực đã, đang và luôn luôn thu hút
các nhà nghiên cứu bởi nó là một lĩnh vực cho phép phát hiện tri
thức trong cơ sở dữ liệu khổng lồ bằng các phƣơng thức thông minh.
Nghiên cứu lĩnh vực này đòi hỏi ngƣời nghiên cứu phải biết tổng hợp
các kết quả nghiên cứu ở nhiều lĩnh vực của khoa học máy tính và
việc ứng dụng nó trong từng nhiệm vụ của khai phá dữ liệu.
Qua hai năm học tập, tìm tòi, nghiên cứu, đặc biệt là trong
khoảng thời gian làm luận văn, tác giả đã hoàn thiện luận văn với các
mục tiêu đặt ra ban đầu. Cụ thể luận văn đã đạt đƣợc những kết quả
sau:
1. KẾT QUẢ ĐẠT ĐƢỢC
- Trình bày các kiến thức cơ bản về khai phá dữ liệu; hệ thống
hóa các kiến thức cơ bản của lý thuyết tập thô đƣợc áp dụng để xây
dựng cây quyết định.
- Giới thiệu phƣơng pháp tổng quát xây dựng cây quyết định,
và trình bày bốn thuật toán xây dựng cây quyết định CLS, ID3,
C4.5, FLIQ[5] và một số mẫu minh họa cho các phƣơng pháp xây
dựng cây quyết định cũng đƣợc trình bày.
- Cài đặt bằng Visual Studio thuật toán xây dựng cây quyết
định ID3 trên cơ sở dữ liệu mẫu Dulieuvayvon hỗ trợ cán bộ tín dụng
ra quyết định vay vốn.
2. HẠN CHẾ CỦA ĐỀ TÀI
- Dữ liệu còn hạn chế, mang tính chất nghiên cứu demo.
- Giao diện chƣơng trình chƣa thân thiện.

- Chƣa so sánh, đánh giá đƣợc với các phƣơng pháp khác.
3. KIẾN NGHỊ VÀ HƢỚNG PHÁT TRIỂN
Qua quá trình học tập, nghiên cứu tác giả không những tích
lũy đƣợc thêm các kiến thức mà còn nâng cao đƣợc khả năng lập