ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN THỊ HOÀN

MỘT MÔ HÌNH KẾT HỢP HỌC GIÁM SÁT VÀ BÁN GIÁM SÁT
CHO BÀI TOÁN DỰ BÁO KHÁCH HÀNG
CÓ NGUY CƠ RỜI MẠNG VINAPHONE

LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN

HÀ NỘI - 2015


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN THỊ HOÀN

MỘT MÔ HÌNH KẾT HỢP HỌC GIÁM SÁT VÀ BÁN GIÁM SÁT
CHO BÀI TOÁN DỰ BÁO KHÁCH HÀNG
CÓ NGUY CƠ RỜI MẠNG VINAPHONE

Ngành: Công nghệ thông tin
Chuyên ngành: Hệ thống thông tin
Mã số:60.48.01.04

LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN
Ngƣời hƣớng dẫn khoa học: PGS.TS. HÀ QUANG THỤY

HÀ NỘI - 2015

phát triển các nghiên cứu về bài toán dự báo khách hàng rời mạng trong nước và trên
thế giới do tôi thực hiện.
Luận văn này là mới, các đề xuất trong luận văn do chính tôi thực hiện, qua quá
trình nghiên cứu đưa ra và không sao chép nguyên bản từ bất kỳ một nguồn tài liệu
nào khác.

ii


Mục lục
Lời cảm ơn ....................................................................................................................... i
Danh mục các hình vẽ và bảng biểu ................................................................................ v
Danh mục từ viết tắt ....................................................................................................... vi
Mở đầu ............................................................................................................................ 1
Chƣơng 1: Khái quát bài toán dự đoán khách hàng rời mạng ................................. 2
1.1.Bài toán dự đoán khách hàng rời mạng ..................................................................... 2
1.2.Vai trò của khai phá dữ liệu trong quản lý khách hàng rời mạng ............................. 3
1.3. Một số nghiên cứu cho bài toán dự đoán khách hàng rời mạng............................... 4
1.3.1. Đánh giá hiệu quả của mô hình ............................................................................. 4
1.3.2. Một số mô hình nghiên cứu về dự đoán khách hàng rời mạng ............................. 5
1.4.Tóm tắt chương 1....................................................................................................... 8
Chƣơng 2: Một số mô hình điển hình cho bài toán dự đoán khách hàng rời mạng9
2.1. Mô hình dựa trên luật cho bài toán dự đoán khách hàng rời mạng dịch vụ viễn
thông ............................................................................................................................ 9
2.1.1. Giới thiệu mô hình phân lớp dựa trên luật ............................................................ 9
2.1.2. Mô hình sinh các luật ............................................................................................ 9
2.1.3. Phân lớp ............................................................................................................... 12
2.1.4. Kết quả và đánh giá mô hình ............................................................................... 13
2.2. Mô hình học lai cho bài toán dự đoán khách hàng rời mạng ................................. 15
2.3. Tóm tắt chương 2 .................................................................................................... 21

Hình 7: So sánh đường cong ROC, AUC với kỹ thuật phân lớp khác nhau ................ 21
Hình 8: So sánh hiệu quả của mô hình lai đề xuất và các mô hình lai khác dựa trên
ROC ............................................................................................................................... 21
Hình 9: Mô hình kết hợp học giám sát và bán giám sát ................................................ 23
Hình 10: Một ví dụ về phân lớp KNN ........................................................................... 25
Hình 11: Mô hình học bán giám sát Self-training ......................................................... 26
Hình 12: Sơ đồ thuật toán Self-training......................................................................... 27
Hình 13: Giả mã học luật FOIL ..................................................................................... 28
Hình 14: Giả mã học 1 luật FOIL .................................................................................. 28
Bảng 1: Tỉ lệ rời mạng của các mạng tại Hàn Quốc năm 2007-2008 ............................. 9
Bảng 2: Chức năng, kỹ thuật khai phá dữ liệu và ứng dụng ........................................... 3
Bảng 3: Ma trận Confusion ............................................................................................. 4
Bảng 4: Tập dữ liệu cho mô hình dự đoán dựa trên luật ............................................... 13
Bảng 5: Tập dữ liệu mô hình Ying Hwuang và cộng sự ............................................... 20
Bảng 6: Kết quả mô hình Ying Hwuang và cộng sự sử dụng độ đo AUC.................... 20
Bảng 7: So sánh mô hình Ying Hwuang và cộng sự với một số mô hình khác ............ 20
Bảng 8: Phần mềm sử dụng trong luận văn ................................................................... 30
Bảng 9: Bảng mô tả dữ liệu mẫu .................................................................................. 31
Bảng 10: Trọng số một số thuộc tính dữ liệu ................................................................ 31
Bảng 11: Ma trận Confusion ......................................................................................... 33
Bảng 12: Kết quả thực nghiệm với trọng số weight2 .................................................... 33
Bảng 13: Kết quả thực nghiệm với trọng số weight1 .................................................... 34

v


Danh mục từ viết tắt
STT

Từ/cụm từ


DMEL

6

True Prediction/False Prediction

TP/FP

7

First Order Inductive Learning

FOIL

vi


Mở đầu
Sự phát triển mạnh mẽ của công nghệ viễn thông trong những năm gần đây đã
mở ra nhiều cơ hội cho các nhà cung cấp dịch vụ mạng di động. Song song với việc
mở rộng và phát triển các khách hàng mới, việc quản lý khách hàng cũ cũng là một
nhiệm vụ quan trọng. Dự báo khách hàng có nguy cơ rời mạng chính là phần trọng yếu
trong quản lý khách hàng rời mạng. Xác định được khách hàng có nguy cơ rời mạng
giúp nhà cung cấp dịch vụ kịp thời đưa ra các biện pháp, phương thức để quản lý,
chăm sóc khách hàng, tránh để khách hàng rời bỏ dịch vụ của mình.
Nhiều mô hình cho bài toán dự báo khách hàng rời mạng đã được nghiên cứu
và phát triển. Các công trình nghiên cứu về dự báo khách hàng rời mạng được công bố
trong các hội nghị nổi tiếng như Elsevier1 và được áp dụng thực tế tại các nhà mạng
lớn như Taiwan Mobile của Đài Loan, China Mobile, của Trung Quốc, T&T của Mỹ.

1.1.

giảm một lượng lớn dịch vụ viễn thông và khiến nó trở thành vấn đề nghiêm trọng của
các nhà cung cấp dịch vụ.
Khách hàng rời mạng (customer churn) được xem là những khách hàng có giá
trị rời bỏ sử dụng dịch của một nhà mạng sang sử dụng dịch vụ của một nhà mạng
khác. Quản lý khách hàng rời mạng (churn management) là các chính sách xử lý của nhà
mạng nhằm giữ chân các khách hàng có nguy cơ rời mạng. Một trong những thách thức của
“churn management” là dự đoán các “churner”. Bài toán dự đoán khách hàng rời mạng (churn
prediction) chính là đi tìm các “churner” dựa trên các thuộc tính của khách hàng như: dữ liệu
hợp đồng, thông tin khách hàng, log sử dụng dịch vụ, chi tiết cuộc gọi, dữ liệu khiếu nại,
thông tin hóa đơn và thanh toán.
Theo các nghiên cứu thị trường của Berson, Smitch và cộng sự năm 2000 [C1_06], tỉ
lệ khách hàng ngưng sử dụng dịch vụ của các nhà mạng di động lên tới 2% trên tháng. Điều
đó có nghĩa mỗi nhà mạng mất gần ¼ lượng khách hàng mỗi năm, hơn nữa, các nhà mạng
Châu Á phải đối mặt với nhiều thách thức rời mạng hơn là các nhà mạng khác trên thế giới.

Hình 1: Tỉ lệ rời mạng của một số mạng Châu Âu năm 2010-2011(1)
Trên thực tế, một nhà mạng có thể phân đoạn các khách hàng của họ dựa trên
các lợi ích mà khách hàng mang lại và quản lý khách hàng chỉ dựa trên phân đoạn
khách hàng có lợi ích. Tuy nhiên, công nghiệp dịch vụ viễn thông không thể tiêu

2


chuẩn hóa tập độ đo lợi ích. Vì vậy, kỹ thuật khai phá dữ liệu được áp dụng để
giải quyết vấn đề thách thức của khách hàng rời mạng trong lĩnh vực dịch vụ viễn
thông.
1.2.


Ứng dụng

Mạng Neuron

Đánh gia tỉ lệ thay đổi
Đánh giá giá cổ phiếu
Biển thủ hóa đơn
Phân đoạn thị trường

Cây quyết định
Làm mờ
Mạng Neuron
Thuật toán di truyền
Mạng Neuron
Hồi quy
Cây quyết định
Mạng Neuron
Thuật toán di truyền
Cây quyết định

Dự đoán khách hàng rời mạng
Dự đoán gian lân

Phân đoạn thị trường

Thống kê

Bảng 1: Chức năng, kỹ thuật khai phá dữ liệu và ứng dụng

3

Churn
Non-churn

Predicted
Non-churn
a12
a21

Churn
a11
a22

Bảng 2: Ma trận Confusion

Từ cặp TP và FE, kỹ thuật đường cong hoạt động nhận được (Receive
Operationg Curves (ROC) ) [Bradley-97] được sử dụng để tìm cặp tỉ lệ dự đoán mong
đợi (TP và FP).
Tuy nhiên, kỹ thuật ROC thường khó sử dụng để đánh giá từ các kỹ thuật mô
hình dự đoán khác nhau hoặc tập thuộc tính dữ liệu khác nhau. Để giải quyết khó
khăn, kỹ thuật tính miền dưới đường cong ROC (Area under ROC AUC) được sử
dụng để đánh giá mô hình và tập thuộc tính trong dự đoán khách hàng rời mạng. Miền
dưới đường cong ROC được tính theo công thức:
AUC 

s0  n0 x(n0  1) x0.5
n0 n1

4



Chi tiết cuộc gọi đến:



b. Chuẩn hóa dữ liệu
Một số mô hình dự đoán, phân lớp gặp khó khăn trong xử lý dữ liệu liên tục
(dạng chuỗi,..). Quá trình chuẩn hóa dữ liệu chia các các thuộc tính liên tục thành các
thuộc tính rời rạc. Quá trình này thường được sử dụng như bước đầu tiên trong các hàm tuyến
tính hoặc học quy nạp. Mô tả dữ liệu thành dạng mà bộ phân lớp, dự đoán có thể hiểu được.

c. Dự đoán/Phân lớp
Rất nhiều kỹ thuật được đề xuất cho mô hình dự đoán trong viễn thông, dưới đây
là bẩy mô hình phổ biến:
 Mô hình hồi quy logic (Logistic Regressions): [Hosmer-89]: Được áp dụng
rộng rãi cho phân lớp xác xuất rõ ràng. Hồi quy xác suất đánh giá xác suất
để xảy ra sự kiện như sau:
0 

prob( y  1) 

e
1 e

k

 k k
k 1

0 


( | ) ( )
( )

Áp dụng trong bài toán phân loại, các dữ kiện gồm có:
 D: tập dữ liệu huấn luyện đã được vector hóa dưới dạng ⃗
 Ci: phân lớp i, với i = {1,2,…,m}.
 Các thuộc tính độc lập điều kiện đôi một với nhau.
Theo định lý Bayes:
( | )

(

)

( | ) ( )
( )

Theo tính chất độc lập điều kiện:
( | )

∏ (

| )

Trong đó:

( | ) là xác suất thuộc phân lớp i khi biết trước mẫu X.

( ) xác suất là phân lớp i.


 Mạng Neuron nhân tạo (Artificial neural networks)
Một một neuron đa lớp (Multilayer Perceptron Neural Networks (MLP)) là một
mạng neuron giám sát, thường bao gồm lớp đầu và lớp ẩn và lớp đầu ra. Thông
thường, hàm khởi động của MLP là hàm sigmoid. Ví dụ MLP với một lớp ẩn, đầu ra
mạng có thể đạt được bằng cách biến đổi hàm khởi động của đơn vị ẩn sử dụng hai
tầng xử lý.
L

D

i 1

i

Outputnet ( j )  f ( w ji f ( w ii xi )), j  1,..., J

Với D, L và J là tổng số đơn vị lớp đầu vào, ẩn, và lớp ra, f là hàm khởi tạo.
Chi tiết về mạng Neuron nhân tạo được Rumelhart, Hiton và Williams mô tả chi
tiết trong [Rumelhart-86]
 Máy Vector hỗ trợ (Support Vector Machines - SVM)
Một bộ phân lớp SVM sử dụng thuật toán học nhằm xây dựng một siêu mặt
phẳng làm cực tiểu hóa độ phân lớp sai của một đối tượng dữ liệu mới. Độ phân lớp
sai của một siêu phẳng được đặc trưng bởi khoảng cách bé nhất tới siêu phẳng đấy.
Xét bài toán phân lớp đơn giản nhất – phân lớp hai lớp với tập mẫu dữ liệu:
{(x i ,yi )i=1,2,...N, x i  R m }

Trong đó mẫu là các vector đối tượng được phân lớp thành các mẫu dương và
mẫu âm.
Các mẫu dương là các mẫu xi thuộc lĩnh vực quan tâm và được gãn nhãn yi=1.
Các mẫu âm là các mẫu xi không thuộc lĩnh vực quan tâm và được gán nhãn yi=-1.

Trong chương này, luận văn giới thiệu khái quát về bài toán dự đoán khách
hàng rời mạng, các khái niệm liên quan. Chương 1 cũng đề cập đến vai trò của khai
phá dữ liệu và một số kỹ thuật khai phá dữ liệu dùng trong bài toán dự đoán khách
hàng có nguy cơ rời mạng. Trong chương tiếp theo, luận văn sẽ giới thiệu chi tiết hai
mô hình dự đoán khách hàng rời mạng: Mô hình dự đoán dựa trên học luật và mô hình
dựa trên học giám sát và không giám sát của Ying Huwang và cộng sự.

8


Chƣơng 2: Một số mô hình điển hình cho bài toán dự đoán khách
hàng rời mạng
2.1. Mô hình dựa trên luật cho bài toán dự đoán khách hàng rời mạng dịch vụ
viễn thông
2.1.1. Giới thiệu mô hình phân lớp dựa trên luật

Phương pháp phân lớp dựa trên học luật (classification by rule learning (CRL))
là một phương pháp nổi tiếng. Một trong những đặc trưng của quy nạp luật là chúng rõ
ràng và dễ hiểu hơn những mô hình khác. Đã có nhiều nghiên cứu về lĩnh vực này.
Trong xử lý luật quy nạp, hai phương pháp thường được sử dụng là: general-tospecific(top-down) tức là xử lý từ luật chung đến các luật riêng và phương pháp
specific-to-general (bottom-up) tức là đi từ các luật riêng tới các luật chung. Trong đó,
phương pháp top-down thường được áp dụng rộng rãi hơn.
“Luật” được định nghĩa là một mệnh đề dạng: {NẾU Tiền đề THEN kết quả},
với tiền đề được định nghĩa là một sự kết hợp của một số cặp và kết quả là nhãn của lớp. “Luật chung” và “luật riêng” là hai khái niệm quan
trọng. Thông thường, một luật với cặp <thuộc tính, khoảng cách> nhỏ hơn trong kết
quả thì “chung” hơn.
2.1.2. Mô hình sinh các luật

Phân lớp dựa trên học luật (CRL) là một chiến lược từ chung-đến-riêng, vì vậy,

Giải thuật 2: First_order_rules(training data)
1. First_order_rules ←  ;
2. For i=1; i ≤ num_attribute; i++ do
3.
4.
5.
6.
7.
8.

For j=1; j≤ num_interval; j++ do
For k=1; k≤ num_class; k++ do
If Pruning (ruleijk) returns fales then
First_order_rules ← First_order_rule

ruleijk

End if
End for

9. End for
10. End for
11. Return First_order_rules
High-order Rules (Giải thuật 3): Highter-order rules được xây dựng lặp lại từ các
luật cấp thấp hơn. Luật bậc 2 (second_order) được xây dựng từ luật bậc 1 (first_order),
luật bậc 3 (third_order) được xây dựng từ luật bậc 2 (second_order). Luật (n-1)_order
là cơ sơ để xây dựng luật n_order. Trong thuật toán 3, item được dùng để định nghĩa
một cặp <thuộc tính, khoảng cách>, positive_items bao gồm tất các các phần tử được
trích xuất từ tất cả các luật dương. Tập các negative-items cũng được sinh tương tự.
Mỗi luật riêng được đặc tả bởi thuật toán hill_climbing để thêm một phần tử vào phần

9. If WRAi is not in the list of accuracy_list then
10. all_rules ← all_rules high_rule;
11. accuracy_list ← accuracy_list WRAi ;
12. end if
13. end if
14. end for
15. do same work to generate negative_rules;
16. all_rules ← all_rules negative_rule;
17. return all_rules

Thuật toán hill_climbing
Giải thuật 4: hill_climbing (one_lower_rule, all_low_items)
1. accuracy_list ←  ;
2. for i=1; i ≤ num_low_items; i++ do
3. If one_lower_rule does not include itemi then
4.
one_high_rule ← combination of one_lower_rule and itemi;
5.
WRAi ← calculate the Weighted_Relative_Accuracy for one_high_rule;
6.
accuracy_list ← accuracy_list WRAi ;
7. end if
8. end for
9. BEST ← one of high order rules having the highest WRA;
10. return BEST

Số lương luật sinh ra có thể rất lớn, để việc phân lớp được hiệu quả, Ying Hwuang và
cộng sự đã loại bỏ bớt những luật xấu với các thông tin nhiễu hoặc không quan trọng.

11

ngưỡng giá trị đánh giá  2 , minS và minC là hai giá trị ngưỡng, được định nghĩa là
giá trị nhỏ nhất của support và confidence.
Giải thuật 5: pruning (rule)
1. flag ← true;
2. If chi-square statistics > α AND support_rule > minS AND Confidence_rule >
minC then
3. flag ← false;
4. End if
5. return flag;

2.1.3. Phân lớp

Để phân lớp cho tập dữ liệu, Ying Hwuang và cộng sự coi Rules bao gồm hai
lớp: churn và non-churn. Hai mô hình dự đoán được xây dựng dựa trên tất cả các luật
churn và tất cả các luật non-churn. Để đánh giá độ quan trọng của các luật, Ying
Hwuang và cộng sử xếp hạng các luật trong mỗi mô hình dựa trên một số nguyên lý
sau:
 Nếu confidence_1 > confidence_2 thì luật rule_1 có độ ưu tiên cao hơn
rule_2.
 Nếu confidence_1= confedence_2 và support_1 > support_2 thì luật
rule_1 có độ ưu tiên cao hơn rule_2.
12


 Nếu confidence_1 = confedence_2 và support_1 = support_2 vàn
rule_2 là “chung” hơn luật rule_2 thì rule_1 có độ ưu tiên cao hơn
rule_2.
Sau khi xếp hạng, mỗi luật có một vị trí trong mỗi mô hình dự đoán, nếu một
luật có độ quan trọng hơn các luật khác thì nó có vị trí tốt hơn. Ying Hwuang và cộng
sự định nghĩa mực độ quan trọng của mỗi luật như sau:


Với S0 là tổng xếp hạng của lớp 0 (churn) tập mẫu, n0 là số tập mẫu thuộc về lớp 0
(churn) và n1 là số tập mẫu thuộc lớp 1 (nonchurn).
13


Hình 2: So sánh độ AUC giữa các mô hình

Hình trên mô tả kết quả so sánh AUC khi áp dụng CRL và DMEL với các tỉ lệ
churn-rate khác nhau: (a):1%, (b) :2%, (c): 4%, (d): 6%, (e): 8%, (f):10%. [Huang-11]

14


Hình 3: So sánh AUC mô hình CRL và DMEL cho tỉ lệ churn rate khác nhau

Hình 4: So sánh AUC cho mô hình CRL và DMEL với tập dữ liệu UCI

Bên trên là kết quả của tác giả Ying Hwuang và cộng sự khi so sánh độ AUC
cho mô hình CRL và DMEL với dữ liệu viễn thông có tỉ lệ churn-rate khác nhau, và
hình 4 là kết quả với dữ liệu UCI [Ying-11].
2.2. Mô hình học lai cho bài toán dự đoán khách hàng rời mạng
Ngoài mô hình phân lớp dựa trên luật, Ying Hwuang và công sự M.Tahar còn
xây dựng mô hình lai để dự đoán các hành vi tương lai của khách hàng. Ý tưởng chính
cho mô hình học lai là dự đoán khách hàng theo dữ liệu học tương tự với nó. Giả thiết
rằng, khách hàng có thuộc tính giống nhau thì hành vi sẽ giống nhau. Vì vậy, sẽ chính
xác hơn nếu một đối tượng chưa gán nhãn được dự đoán sử dụng đối tượng học hơn là
toàn bộ dữ liệu bằng cách chia dữ liệu học thành các cụm và đối tượng test được gán
nhãn theo cụm gần nó nhất.
15

4. Tính toán lại trung tâm cụm của tất cả các cụm
5. Until trung tâm cụm không thay đổi
Trung tâm các cụm không thay đổi là việc khó đạt được, vì vậy, để kết thúc
vòng lặp, người ta tính toán độ SSE (Sum of the Squared Error), tức là tổng khoảng
cách từ các đối tượng tới các trung tâm cụm đạt được một ngưỡng nào đó.

16


K

ni

SSE   | (ci  oij )

2

i 1 j 1

Giá trị của SSE càng nhỏ, thì độ chính xác càng cao.
 Phân cụm K-means có trọng số
Ying Hwuang và cộng sự sử dụng tập dữ liệu được cung cấp bởi nhà mạng viễn
thông cho mô hình. Tập dữ liệu có một lượng lớn các thuộc tính mà mỗi thuộc tính có
độ ảnh hưởng khác nhau đến kết quả. Vì vậy, để hiệu quả hơn, tác giả đánh trọng số
cho mỗi thuộc tính, nhằm mục đích giảm độ ảnh hưởng của một thuộc tính đối với kết
quả.
b. Học luật quy nạp
Học luật quy nạp là một phần quan trọng trong mô hình dự đoán lai. Một tập
các luật được sinh ra từ các cụm, các luật này biểu diễn đặc trưng của các cụm. Ưu
điểm chính của phương pháp học dựa trên luật là kết quả dễ hiểu và rõ ràng. Trong