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

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ữ