BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
________________________

ĐỖ THỊ TÂM

MỘT SỐ THUẬT TOÁN CỤM MỜ VÀ BÀI
TOÁN PHÂN TÍCH DỮ LIỆU KHÁCH HÀNG
NGÂN HÀNG

LUẬN VĂN THẠC SỸ KHOA HỌC
Chuyên ngành Quản trị Kinh doanh

NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS.TSKH BÙI CÔNG CƯỜNG

HÀ NỘI - 2010


Một số thuật toán phân cụm mờ và bài toán phân tích dữ liệu khách hàng ngân hàng

Mục lục
Mục lục............................................................................................................................ 1
Mở đầu............................................................................................................................. 2
Chương 1 - Phân cụm mờ ................................................................................................ 4
1.1
Phân cụm mờ là gì ............................................................................................ 4
1.2
Thuật toán phân cụm mờ FCM (Fuzzy C -means) ............................................ 4
1.2.1
Thuật toán ................................................................................................. 5

3.3
Lựa chọn chỉ tiêu ............................................................................................ 28
3.4
Cài đặt thuật toán phân cụm ........................................................................... 29
3.4.1
Thuật toán phân cụm mờ FCM ............................................................... 29
3.4.2
Xác định cụm .......................................................................................... 30
3.5
Phân cụm ngành nghề ..................................................................................... 31
3.6
Phân cụm Quy mô .......................................................................................... 34
3.7
Phân cụm doanh nghiệp.................................................................................. 38
Kết luận ......................................................................................................................... 42
Tài liệu tham khảo ......................................................................................................... 43

Đỗ Thị Tâm - Đảm bảo Toán học cho máy tính và hệ thống tính toán , 2008 2010
1


Một số thuật toán phân cụm mờ và bài toán phân tích dữ liệu khách hàng ngân hàng

Mở đầu
Hoạt động ngân hàng trong nền kinh tế thị tr ường là một trong những hoạt động
kinh tế chứa đầy rủi ro. Rủi ro trong hoạt động ngân hàng có thể gây ra tai họa cho
nền kinh tế hơn bất cử rủi ro của các loại hình hoạt động kinh tế khác, do tính chất
lây lan của nó có thể làm rung chuyển toàn bộ hệ thốn g kinh tế.
Hoạt động của ngân hàng thương mại gồm nhiều nghiệp vụ, nhưng chung quy
lại, đây là loại hình kinh doanh tiền tệ tín dụng của một trung gian tài chính dựa

Em xin chân thành cảm ơn thầy Bùi Công Cường đã rất tậ n tình hướng dẫn em
làm luận văn này!

Đỗ Thị Tâm - Đảm bảo Toán học cho máy tính và hệ thống tính toán , 2008 2010
3


Một số thuật toán phân cụm mờ và bài toán phân tích dữ liệu khách hàng ngân hàng

Chương 1 - Phân cụm mờ
1.1 Phân cụm mờ là gì
Phân cụm là phương pháp phân loại các đối tượng dữ liệu vào các nhóm (cụm)
khác nhau sao cho các đối tượng dữ liệu trong cùng một nhóm (cụm) là tương tự
nhau và trong các nhóm khác nhau l à không tương tự nhau.
Trong phân cụm rõ, mỗi đối tượng dữ liệu chỉ thuộc vào một cụm, do đó chỉ áp
dụng phù hợp trong trường hợp các cụm có mật độ cao và rời nhau. Tuy nhiên, trong
thực tế, các cụm dữ liệu lại chồng lên nhau, nghĩa là một số đối tượng dữ liệu có thể
thuộc về nhiều cụm khác nhau. Do đó, để giải quyết trường hợp này, người ta đã áp
dụng lý thuyết về tập mờ vào phân cụm dữ liệu.
Trong phân cụm mờ, mỗi cụm được xem như một tập mờ trong tập dữ liệu. Do
vậy, mỗi đối tượng dữ liệu sẽ gắn với mỗi cụm bởi một đại lượng gọi là độ thuộc có
giá trị trong đoạn [0, 1], thể hiện mức độ thuộc của đ ối tượng đó vào cụm.

1.2 Thuật toán phân cụm mờ FCM (Fuzzy C-means)
Thuật toán FCM có nhiều tên trước khi có tên là FCM. Đó là Fuzzy ISODATA
và Fuzzy k-Means. Ruspini (1969) giới thiệu khái niệm phân hoạch mờ để mô tả cấu
trúc cụm của tập dữ liệu và đề xuất một thuật toán để tính toán tối ưu phân hoạch
mờ. Dunn (1973) mở rộng phương pháp phân cụm và đã phát triển thuật toán phân
cụm mờ. ý tưởng của thuật toán là xây d ựng một phương pháp phân cụm mờ dựa
trên tối thiểu hóa hàm mục tiêu. Bezdek (1981) cải tiến và tổng quát hóa hàm mục

i 1 k 1

(1.1)
c

với ràng buộc:

u
i 1

ik

1

k 1 ... N ,

(1.2)

với X , c, m là các tham số đầu vào đã biết. Trong đó


X là tập các đối tượng



c là số cụm



m 1 là số mũ mờ hóa, nếu m 1 , thuật toán phân cụm mờ trở thành


với A là ma trận xác định dương. Trong công thức khoảng cách
Euclidean, A là ma trận đơn vị.

Đỗ Thị Tâm - Đảm bảo Toán học cho máy tính và hệ thống tính toán , 2008 2010
5


Một số thuật toán phân cụm mờ và bài toán phân tích dữ liệu khách hàng ngân hàng

Người ta đã chứng minh rằ ng, giá trị P*, U * làm cực tiểu hóa J FCM P , U ở
phương trình (1.1) với ràng buộc (1.2) phải thỏa mãn các phương trình cập nhật sau:
N

p
*
i

u
k 1
N

u
k 1

uik*

m
ik


Tìm c tâm cụm mờ (ma trận P ) theo phương trình (1.3).
Bước 3:
Cập nhật độ thuộc U theo phương trình (1.4).
Bước 4:
So sánh sự thay đổi giá trị độ thuộc bằng một chuẩn thích hợp. Nếu sự
thay đổi này là nhỏ thì dừng. Ngược lại, quay về bước 2.

1.2.2 Ưu điểm và nhược điểm của thuật toán FCM
Ưu điểm:
Thuật toán này không phức tạp để lập trình.

Đỗ Thị Tâm - Đảm bảo Toán học cho máy tính và hệ thống tính toán , 2008 2010
6


Một số thuật toán phân cụm mờ và bài toán phân tích dữ liệu khách hàng ngân hàng

Thuật toán sử dụng hàm mục tiêu trực quan và dễ hiểu
Với các tập dữ liệu tạo thành các cụm tách rời nhau và có dạng siêu cầu
thì FCM tìm ra các cụm này khá chính xác.
FCM dựa trên cơ sở mờ, nên nó rất mạnh: nó luôn hội tụ đến một giải
pháp, và nó cung cấp các giá trị độ thuộc thích hợp. Ràng buộc ở phương
trình (1.2) là điều kiện cần thiết để chứng minh tính hội tụ tới giá trị cực
tiểu địa phương của thuật toán FCM.
Nhược điểm:
FCM yêu cầu số cụm là một tiên nghiệm (priori).
FCM tìm các cụm có cùng hình dạng (các cụm siêu cầu nếu sử dụng
metric Euclidean); các hình dáng cụm khác sẽ không được trộn vào.
Hàm mục tiêu của FCM không phải là một tiêu chuẩn phân cụm tốt khi
các cụm gần với một cụm khác nhưng không bằng nhau về kích thước

1

(1.6)

1

(1.7)

i 1

ik

c

i 1

i

Đỗ Thị Tâm - Đảm bảo Toán học cho máy tính và hệ thống tính toán , 2008 2010
7


Một số thuật toán phân cụm mờ và bài toán phân tích dữ liệu khách hàng ngân hàng

với i là phần tử chuẩn hóa cụm i.






u
k 1

xk
(1.9)
m
ik

1

N
m 2 r 1
u


ik dik
*

i k 1
1
c
N
m 2 r 1

uik dik
i 1 k 1


(1.10)


OF nhiều hơn cụm nhỏ bởi vì khoảng cách của nó lớn hơn. Do vậy, khoảng cách
tương đối giữa các cụm đóng vai trò trong v iệc xác định sự đóng góp của mỗi cụm
tới OF. Nói chung, cụm lớn đóng góp nhiều hơn cụm nhỏ.
Đỗ Thị Tâm - Đảm bảo Toán học cho máy tính và hệ thống tính toán , 2008 2010
8


Một số thuật toán phân cụm mờ và bài toán phân tích dữ liệu khách hàng ngân hàng

uik*

1
dik2
2

j 1 d jk
c





k 1,..., N , i 1,..., c .

1
m 1

Những điểm nằm rất gần một nguyên mẫu (prototype) có độ thuộc hầu như bằng
0 với tất cả các nguyên mẫu khác. Tuy nhiên, các điểm nằm ở giữa hai nguyên mẫu
sẽ có độ thuộc xấp xỉ 0.5. Trong phương pháp này, chúng đóng góp cho OF của cả

A

2

i

i 1

m

x p A x p
T

k

i

i

k

i

(1.11)
Trong đó Ai là ma trận đối xứng xác định dương, và ngoài ràng buộc ở phương
trình (1.2) còn thêm ràng buộc:

Đỗ Thị Tâm - Đảm bảo Toán học cho máy tính và hệ thống tính toán , 2008 2010
9


Bước 3:
N

Cập nhật các nguyên mẫu P bởi pi

u
k 1
N

m
ik

u
k 1

xk
m
ik

Bước 4:

1
C
i i

Tính Ai1

1
p


Nếu điều kiện dừng không thỏa mãn, quay lại Bước 2.

Đỗ Thị Tâm - Đảm bảo Toán học cho máy tính và hệ thống tính toán , 2008 2010
10


Một số thuật toán phân cụm mờ và bài toán phân tích dữ liệu khách hàng ngân hàng

1.5 Phân cụm mờ c-Elliptotypes (Fuzzy c-Elliptotypes - FCE)
Thuật toán này được đưa ra bởi Bezdek để tìm các cụm có dạng đường thẳng
hoặc mặt phẳng. ý tưởng chính của nó là giảm khoảng cách Euclidean của các điểm
nằm dọc theo các hướng vector đặc trưng của một cụm (giống như là nằm trên một
đường thẳng) trong khi lấy đủ khoảng cách E uclidean của các điểm khác. Bằng cách
sử dụng khoảng cách là sự kết hợp có trọng số của hai khoảng cách:
2
2
d ik2 xk , pi dVik
1 d Eik

(1.13)

2
2
ở đây d Eik
là khoảng cách Euclidean và dVik
được định nghĩa như s au:
2
dVik
xi pi xk pi .eij
2

sử dụng là:

Đỗ Thị Tâm - Đảm bảo Toán học cho máy tính và hệ thống tính toán , 2008 2010
11


Một số thuật toán phân cụm mờ và bài toán phân tích dữ liệu khách hàng ngân hàng



d 2 xk , pi , ri xk pi ri 2
2



2

(1.16)

Trong thuật toán đường bao mờ thích nghi (adaptive fuzzy), các đường bao có
dạng elip được tìm thấy bằng cách sử dụng độ đo khoảng cách:

d xk , pi , A

2

x k pi

T


tín nhiệm chứa đựng cả ý kiến chủ quan củ a chuyên gia xếp hạng tín nhiệm.
Theo công ty Moodys, xếp hạng tín nhiệm là ý kiến về khả năng và sự sẵn sàng
của một nhà phát hành trong việc thanh toán đúng hạn cho một khoản nợ nhất định
trong suốt thời gian tồn tại của khoản nợ.[4]

2.2 Mục đích của xếp loại tín dụng
Mục đích của xếp loại tín dụng là dựa trên cơ sở các số liệu kiểm tra, phân tích
dữ kiện từ các hồ sơ lưu trữ, báo cáo tài chính và báo cáo kiểm toán của doanh
nghiệp để nhận xét đánh giá tình hình hoạt động, khả năng sinh lời, khả năng thanh
toán hiện tại và trong tương lai của doanh nghiệp nhằm xác định khả năng thu hồi
vốn của ngân hàng cho vay.
Việc xếp loại tín dụng được thực hiện nhằm hỗ trợ ngân hàng cho vay trong
việc:[4]
-

Ra quyết định cấp tín dụng: xác định h ạn mức tín dụng của một khách
hàng, số tiền cho vay/ bảo lãnh, thời hạn, mức lãi suất/phí, biện pháp đảm
bảo cho khoản tín dụng.

-

Giám sát và đánh giá khách hàng tín dụng khi khoản tín dụng đang còn
dư nợ; Hạng khách hàng cho phép ngân hàng cho vay lường tr ước những

Đỗ Thị Tâm - Đảm bảo Toán học cho máy tính và hệ thống tính toán , 2008 2010
13


Một số thuật toán phân cụm mờ và bài toán phân tích dữ liệu khách hàng ngân hàng


2.3.2.1 Theo ngành kinh tế
Hiện tại các ngân hàng Căn cứ vào ngành nghề/ lĩnh vực sản xuất kinh doanh
chính đăng ký trên Giấy chứng nhận đăng ký kinh doanh của doanh nghiệp, để xác
định ngành nghề/ lĩnh vực sản xuất kinh doanh của doanh nghiệp, bao gồm:
Nông, lâm và ngư nghiệp
Thương mại và dịch vụ
Đỗ Thị Tâm - Đảm bảo Toán học cho máy tính và hệ thống tính toán , 2008 2010
14


Một số thuật toán phân cụm mờ và bài toán phân tích dữ liệu khách hàng ngân hàng

Xây dựng
Công nghiệp
Trường hợp doanh nghiệp hoạt động đa ngành nghề thì căn cứ vào ngành nghề/
lĩnh vực nào đem lại tỷ trọng doanh thu lớn nhất cho doanh nghiệp.
Ngân hàng Công Thương Việt Nam phân loại doanh nghiệp vào một trong bốn
ngành nghề trên như bảng sau:
Nông, lâm và - Chăn nuôi
ngư nghiệp

- Trồng trọt: cây lương thực, hoa màu, cây ăn quả, cây công
nghiệp,
- Trồng rừng
- Khai thác lâm sản
- Đánh bắt, nuôi trồng thủy hải sản
- Làm muối

Thương


- Hạ tầng đô thị và nhà ở
- Xây lắp (xây dựng cơ bản)

Công nghiệp

- Chế biến các loại nông sản, lâm sản, thủy hải sản, thực phẩm,
rượu bia, nước giải khát
- Sản xuất thuốc lá, dược phẩm, thiết bị y tế, mỹ phẩm, văn hóa
phẩm, vật liệu xây dựng, hóa chất (bao gồm cả phân bón, thuốc
trừ sâu), hàng tiêu dùng, hàng mỹ thuật, mỹ nghệ, nguyên vật liệu
cho các ngành khác.
- Sản xuất, lắp ráp hàng điện tử, máy móc, phương tiện giao thông
vận tải
- Sản xuất điện, khí đốt
- Khai thác khoáng sản
- Khai thác than, vật liệu xây dựng (cát, đá, ), dầu khí

Ngân hàng Ngoại Thương Việt Nam phân doanh nghiệp vào một trong bốn
ngành nghề theo như trong bảng sau:
Sản phẩm, lĩnh vực hoạt động chính của doanh nghiệp

Được xếp vào
ngành/lĩnh
vực

Nông nghiệp và các dịch vụ có liên q uan:
Trồng trọt
Lâm nghiệp và các dịch vụ liên quan:
Trồng rừng, cây phân tán; nuôi rừng, chăm sóc tự nhiên;
khai thác và chế biến gỗ lâm sản tại rừng


thải

vận tải đường không; các hoạt động phụ trợ cho vận tải,
hoạt động của các tổ chức du lịch; Dịch vụ bưu chính viễn
thông; kinh doanh tài sản và dịch vụ tư vấn; cho thuê máy
móc thiết bị; các hoạt động có liên quan đến máy tính; các
hoạt động kinh doanh khác
Xây dựng:
Chuẩn bị mặt bằng
Xây dựng công trình hoặc hạng mục công trình
Hoàn thiện công trình xây dựng
Cho thuê thiết bị xây dựng hoặc thiết bị phá dỡ có kèm

Xây dựng

Lắp đặt trang thiết bị cho các công trình xây dựng

người điều khiển
Sản xuất vật liệu xây dựng

Đỗ Thị Tâm - Đảm bảo Toán học cho máy tính và hệ thống tính toán , 2008 2010
17


Một số thuật toán phân cụm mờ và bài toán phân tích dữ liệu khách hàng ngân hàng

Công nghiệp khai thác mỏ:
Khai thác than các loại
Khai thác dầu thô, khí tự nhiên và các dịch vụ khai thác

Đỗ Thị Tâm - Đảm bảo Toán học cho máy tính và hệ thống tính toán , 2008 2010
18


Một số thuật toán phân cụm mờ và bài toán phân tích dữ liệu khách hàng ngân hàng

Sản xuất dịch vụ y tế, dụng cụ chính xác, dụng cụ quang
học và đồng hồ các loại
Sản xuất xe có động cơ, rơ moóc
Sản xuất các phương tiện vận tải khác
Sản xuất giường, bàn, tủ, ghế
Tái chế phế liệu, chất thải
Sản xuất và phân phối điện, khí đốt
Khai thác, lọc và phân phối nước
2.3.2.2 Theo quy mô của doanh nghiệp
Các tiêu chí sử dụng để chấm điểm và xác định quy mô doanh nghiệp gồm:
nguồn vốn kinh doanh, lao động, doanh thu thuần và giá trị nộp N gân sách Nhà
nước.
Dưới đây là bảng hướng dẫn chấm điểm Quy mô doanh nghiệp tại Sở giao dịch I
- Ngân hàng Công Thương Việt Nam.
STT Tiêu chí

Trị số

Điểm

1

Từ 50 tỷ đồng trở lên


Từ 1500 người trở lên

15

Lao động

(Là số lao động thực tế Từ 1000 người đến dưới 1500 người

12

sử dụng (được nêu tại Từ 500 người đến dưới 1000 người

9

thuyết minh báo cáo tài Từ 100 người đến dưới 500 người

6

chính) tính bình quân Từ 50 người đến dưới 100 người

3

trong 3 năm gần nhất)

Dưới 50 người

1

Doanh thu thuần


Dưới 5 tỷ đồng

2

Nộp ngân sách TK Từ 10 tỷ đồng trở lên
Từ 7 tỷ đồng đến 10 tỷ đồng

314- CĐKT

15
12

9
(Lấy theo số thực nộp Từ 5 tỷ đồng đến 7 tỷ đồng
vào NSNN phát sinh Từ 3 tỷ đồng đến 5 tỷ đồng
6
trong kỳ (không kể số
3
thiếu của kỳ trước nộp Từ 1 tỷ đồng đến 3 tỷ đồng
kỳ này) bao gồm các Dưới 1 tỷ đồng
1
loại thuế và các khoản
nộp khác theo quy định
của Nhà nước trong năm
báo cáo)
Căn cứ vào thang điểm trên, các doanh nghiệp được xếp loại thành: Quy mô lớn,
vừa và nhỏ:
Điểm

Quy mô

gian ngắn, kết quả nợ ngắn hạn sẽ tăng nhanh hơn tài sản ngắn hạn và hệ số
thanh toán ngắn hạn sẽ giảm xuống. Còn nếu tỷ lệ này quá cao, thì có thể là một
dấu hiệu cho thấy việc đầu tư vào các tài sản lưu động còn thiếu hiệu quả. Có
thể so sánh chỉ tiêu này trong các doanh nghiệp cùng ngành để đánh giá hiệu
quả tương đối của các doanh nghiệp. Tuy nhiên, để có cái nhìn đầy đủ về sự
phát triển của doanh nghiệp thì ta nên theo dõi chỉ tiêu này trong một khoảng
thời gian đủ dài. Trong những điều kiện thông thường tỷ lệ này bằng 1 là tốt
nhất.
= Tài sản ngắn hạn / Nợ ngắn hạn
Tài sản ngắn hạn : bảng CĐKT 100
Nợ ngắn hạn : bảng CĐKT 310
Hệ số thanh toán nhanh (Đơn vị tính: lần)
Thể hiện khả năng dùng tiền hoặc các tài sản có thể chuyển đổi thành tiền để trả
nợ ngay khi đến hạn và quá hạn, đồng thời nói lên tình trạng tài chính ngắn hạn
của công ty là tốt hay xấu. Nếu chỉ số này nhỏ hơn 1, doanh nghiệp không có
khả năng thanh toán ngay lập tức các khoản nợ ngắn hạn, do đó cần phải thận
trọng khi đầu tư vào doanh nghiệp này. Hàng tồn kho và các chi phí trả trước
không được đưa vào công thức này vì khó có thể chuyển thành tiền mặt ngay.
= (Tiền và các khoản tương đương tiền + Các khoản thu ngắn hạn + Các khoản
đầu tư tài chính ngắn hạn + tài sản ngắn hạn khác) / nợ ngắn hạn
Tiền và các khoản tương đương tiền : CĐKT 110.
Các khoản phải thu ngắn hạn: CĐKT 130.
Các khoản đầu tư ngắn hạn : CĐKT 120.
Tài sản ngắn hạn khác: CĐKT 150.
Nợ ngắn hạn: CĐKT 310.
II

Chỉ tiêu hoạt động: Cho thấy doanh nghiệp đã sử dụng tài sản hiệu quả như thế
nào.
Doanh thu thuần về bán hàng và cung cấp dịch vụ / Tổng tài sản (Đơn vị tính: lần)

Cho biết trong tài sản của doanh nghiệp có bao nhiêu phần trăm là nợ. Nếu tỷ lệ
này lớn hơn 50% thì tài sản của doanh nghiệp chủ yếu là từ các khoản nợ.
= Nợ phải trả / Tổng tài sản
Nợ phải trả: CĐKT 300.
Tổng tài sản: CĐKT 270.
Nợ phải trả / Nguồn vốn chủ sở hữu (Đơn vị tính: %)
Cho biết tài sản của doanh nghiệp được hình thành chủ yếu từ nguồn nào, nợ
Đỗ Thị Tâm - Đảm bảo Toán học cho máy tính và hệ thống tính toán , 2008 2010
22


Một số thuật toán phân cụm mờ và bài toán phân tích dữ liệu khách hàng ngân hàng

phải trả hay nguồn vốn chủ sở hữu. Nếu chỉ số này lớn hơn 1 nghĩa là tài sản
của doanh nghiệp được tài trợ chủ yếu từ các khoản nợ, ngược lại, tài sản của
doanh nghiệp được tài trợ chủ yếu từ nguồn vốn chủ sở hữu.
= Nợ phải trả / Nguồn vốn chủ sở hữu
Nợ phải trả: CĐKT 300.
Vốn chủ sở hữu: CĐKT 400
Nợ phải trả / Tổng dư nợ ngân hàng (Đơn vị tính: %)
= Nợ phải trả / Tổng dư nợ ngân hàng
Nợ phải trả: CĐKT 300.
Tổng dư nợ ngân hàng: Thuyết minh BCTC
IV Chỉ tiêu thu nhập: cho biết khả năng sinh lợi của công ty như thế nào.
Lợi nhuận trước thuế / Doanh thu thuần (Đơn vị tính: %)
Phản ánh kết quả tiêu thụ được một đồng doanh thu thì có được bao nhiêu đồng
lợi nhuận.
= Tổng lợi nhuận trước thuế / Doanh thu thuần về bán hàng và cung cấp dịch vụ.
Tổng lợi nhuận trước thuế: KQHĐKD 50.
Doanh thu thuần về bán hàng và cung cấp dịch vụ: KQHĐKD 10.