Header Page 1 of 166.

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
-------------------------------------------------

LÊ MINH HẢI

PHÂN LOẠI HÀNH VI KHÁCH HÀNG SỬ DỤNG DỊCH VỤ DI
ĐỘNG DỰA TRÊN THUẬT TOÁN K-MEANS

LUẬN VĂN THẠC SỸ KỸ THUẬT

HÀ NỘI - 2013

Footer Page 1 of 166.


Header Page 2 of 166.

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
---------------------------------------

LÊ MINH HẢI

PHÂN LOẠI HÀNH VI KHÁCH HÀNG SỬ DỤNG DỊCH VỤ DI ĐỘNG DỰA
TRÊN THUẬT TOÁN K-MEANS

Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01

TÓM TẮT LUẬN VĂN THẠC SĨ

MỞ ĐẦU
1. Lý do chọn đề tài
Đối với một doanh nghiệp thông di động di động việc phát triển thuê bao để kiếm
tìm lợi nhuận vào thời điểm hiện tại đã không còn đem lại hiệu quả. Thay vào đó là một
phương án kinh doanh tiến đến phát triển chất lượng dịch vụ cung cấp thêm nhiều dịch vụ
giá trị gia tăng. Tuy nhiên các dịch vụ truyền thống như thoại, nhắn tin vẫn có thể đem lại
nguồn lợi nhuận cao hơn nếu kích thích được nhu cầu sử dụng của khách hàng.

Lưu lượng cuộc gọi theo giờ
80

Tỷ lệ lưu lượng (%)

70

60
50

Nhóm B

40

Nhóm A

30
20
10
0
0


đài MSC. Các dữ liệu CDR ghi lại lịch sử cuộc gọi tại một địa điểm cụ thể, đây là nguồn dữ
liệu rất thích hợp tuy nhiên khối lượng dữ liệu này rất lớn nên cần có các kỹ thuật phân tích

Footer Page 4 of 166.


Header Page 5 of 166.

3

thích hợp. Hiện nay các kỹ thuật khai phá dữ liệu đã đạt được nhiều thành tựu có thể hỗ trợ
bài toán phân tích hành vi khách hàng như phân cụm dựa vào thuật toán k-means.
Dựa vào thực trạng như trên kết hợp với các kỹ thuật phân cụm trong khai phá dữ
liệu đã được phát triển để đưa ra đề tài “Phân loại hành vi khách hàng sử dụng dịch vụ di
động dựa trên thuật toán k-means”.
1. Mục đích của đề tài: đề tài hướng đến phân loại hành vi khách hàng, tìm ra các
nhóm khác hàng phổ biến, đang hoạt động trong mạng di động Mobifone; tiến đến đề xuất
tích hợp kết quả vào hệ thống báo cáo số liệu sản xuất kinh doanh cho Tập đoàn VNPT..
2. Đối tượng và phạm vi nghiên cứu: Việc nghiên cứu sẽ tập trung vào lý thuyết
phân cụm dữ liệu theo thuật toán k-means, áp dụng vào phân cụm hành vi sử dụng dịch vụ
thoại và nhắn tin của khách hàng VMS Mobifone.
3. Phương pháp nghiên cứu: Tìm hiểu các tài liệu liên quan đến các kỹ
thuật phân cụm, tập trung vào thuật toán k-means.
4. Kết cấu của luận văn
Luận văn gồm 3 chương
Chương 1: Bài toán phân nhóm khách hàng dựa trên hành vi sử dụng dịch vụ dị
động. Chương này luận văn trình bày nhu cầu phân tích số liệu di động để đưa ra được
thông tin về thói quen sử dụng dịch vụ viễn thông, dịch vụ truyền thống thoại và nhắn tin,
trên một địa bàn.
Chương 2: Thuật toán k-means. Chương này luận văn trình bày một trong những


(2)

 m là số cuộc gọi của khách hàng i trong khoản thời gian t.
 Di,j là thời lượng cuộc gọi của khách hàng i trong cuộc gọi thứ j trong khoảng thời
gian t. Với dịch vụ tin nhắn giá trị này = 1 hay Cit = m.
Khung thời gian có Lt nhỏ nhất là khoảng thời gian cần kích thích để các thuê bao sử
dụng sử dụng nhiều hơn.
Định nghĩa hành vi: Hành vi nói chung là một khái niệm rộng. Trong luận văn này,
khái niệm hành vi dùng để chỉ hành động thực hiện dịch vụ của khách hàng dựa vào vùng
nơi thuê bao thực hiện dịch vụ và thời điểm thực hiện dịch vụ.

1.1.2. Nhu cầu phân tích hành vi sử dụng dịch vụ di động
Hiện tại hệ thống báo cáo số liệu kinh doanh được tập đoàn VNPT khai thác đang
cung cấp dữ liệu dạng tổng hợp. Tuy nhiên câu hỏi chỉ ra tính chất của dữ liệu chưa được
khai thác. Luận văn đề xuất việc phân tích dữ liệu lịch sử cuộc gọi của khách hàng để tìm ra
các nhóm hành vi. Xem xét các nhóm hành vi có thể chỉ ra được tác động của nhóm này đối

Footer Page 6 of 166.


Header Page 7 of 166.

5

với năng lực mạng tại một địa bàn cụ thể; từ đó trợ giúp việc thiết kế các gói khuyến mại để
tận dụng năng lực mạng.

1.1.3. Các khía cạnh phục vụ phân tích hành vi
Thời điểm thực hiện dịch vụ: là một thuộc tính của hành vi sử dụng dịch vụ của



Header Page 8 of 166.

6

Hình 1. 1 Sự phát triển của hệ thống cơ sở dữ liệu (dựa trên [2, tr.2])
Hệ quản trị cơ sở dữ liệu quan hệ được xuất hiện từ những năm 1970 đến đầu 1980,
đại diện là các tên tuổi lớn như Oracle, DB2, MS SQL, MySQL. Đến nay, hệ quản trị cở sở
dữ liệu quan hệ có nhiều cải tiến mạnh mẽ và được ứng dụng rất rộng rãi. Các doanh nghiệp
đã tích lũy các số liệu kinh doanh qua thời gian dài nhờ sử dụng cở sở dữ liệu, tuy nhiên các
mẫu báo cáo kinh doanh thông thường vẫn chưa khai thác hết thông tin mà các dữ liệu đó
đang cất giữ. Chính vì vậy các kỹ thuật khai phá dữ liệu được nghiên cứu và ứng dụng.
Các kiến thức tìm được nhờ ưng dụng kỹ thuật khai phá dữ liệu gồm:
Nhận biết và phân biệt các lớp dữ liệu: Nhận biết đặc tính dữ liệu là việc tìm ra
một tổng kết về các đặc điểm chung hoặc các tính năng của một lớp dữ liệu mục tiêu. Phân
biệt các lớp dữ liệu là việc so sánh các đặc tính dữ liệu của một lớp dữ liệu với một lớp khác
hoặc một tập các lớp khác đã biết.
Khai thác mẫu phổ biến: Mẫu phổ biến là các mẫu dữ liệu hay xuất hiện trong tập
dữ liệu đang xét. Mẫu thường xuyên bao gồm các kiểu như tập phổ biến. các mẫu tuần tự.

Footer Page 8 of 166.


Header Page 9 of 166.

7

Phân loại và dự báo: quá trình của việc tìm kiếm một mô hình (hoặc chức năng) mô
tả và phân biệt các lớp dữ liệu hoặc các khái niệm, sử dụng các mô hình tìm được để dự

Vấn đề xác định độ tương đồng của dữ liệu: Khi dữ liệu cần phân cụm có nhiều
thuộc tính và các thuộc tính rất đa dạng nhiều kiểu. Trong thực tế việc xem xét phân cụm
trong khi dữ liệu mang nhiều thuộc tính và nhiều kiểu thuộc tính là một vần đề cần giải
quyết.
Ngoài ra nhiều thuật toán xác định sự tương đồng của đối tượng dựa trên các khoảng
cách Euclidean hoặc Manhattan thì cho ra các phần tử tương đồng tạo thành một cụm dạng
cầu. Tuy nhiên cụm có thể có hình dạng bất kỳ vì vậy cần phát triển thuật toán tính độ tương
đồng với hình dạng tuỳ ý.
Vấn đề xử lý nhiễu trong phân cụm dữ liệu: Hầu hết các cơ sở dữ liệu thực tế có
chứa các dữ liệu cá biệt hoặc mất tích, không rõ, hoặc dữ liệu sai. Một số thuật toán phân
cụm nhạy cảm với các dữ liệu đó và có thể dẫn đến kết quả phân cụm có chất lượng kém.
Tập dữ liệu gốc được loại bỏ các thành phần nhiễu sẽ trở thành đầu vào tốt cho giai đoại
phân cụm dữ liệu.

1.3

Kết luận
Trong chương 1, luận văn đã trình bày các vấn đề sau:
 Nêu lên bài toán phân tích hành vi sử dụng dịch vụ khách hàng, để hỗ trợ việc xây
dựng chính sách phát triển dịch vụ tận dụng tốt tài nguyên của mạng lưới.
 Nêu các mặt khó khăn trong việc giải quyết bài toán dựa trên khảo sát thị trường. Đề
xuất sử dụng kỹ thuật khai phá dữ liệu, cụ thể là phương pháp phân cụm dữ liệu, để
phân tích các nhóm hành vi
Chương tiếp theo luận văn trình bày kỹ thuật phân cụm k-means, bên cạnh đó đánh

giá khả năng áp dụng thuật toán vào bài toán phân cụm hành vi.

Footer Page 10 of 166.



đến nhau hay khá tương đồng nhau, trong khi các đối tượng khác nhau thì khác nhau.

2.2

Cài đặt thuật toán

2.2.1 Dữ liệu đầu vào
Thuật toán k-means yêu cầu hai nguồn dữ liệu đầu vào
 k : số lượng các cụm mong muốn phân tách.
 D : Tập dữ liệu chứa N phần tử cần phân cụm.

Footer Page 11 of 166.


Header Page 12 of 166.

10

K cụm và vị trí ban đầu: Chọn k là một vấn đề trong phân cụm, và hiện chưa có sự
thống nhất về giải pháp. Việc chọn k có thể ảnh hưởng lớn đến kết quả phân cụm. Chọn
thêm hoặc số lượng hay việc xác định các vị trí ban đầu của k nhiều trưởng hợp sẽ cho ra
kết quả khác nhau. Ví dụ phân cụm nhóm các điểm trong trong hình vuông 1x1.

Hình 2. 1 Ví dụ việc chọn k tốt [6, tr.21]

Hình 2. 2 Các kết quả sau khi thay đổi số cụm khởi tạo (dựa trên [6,tr.21])

Footer Page 12 of 166.



(4)

Cập nhật thông số cụm, nghĩa là, tính toán giá trị trung bình cho từng cụm;

(5) cho đến khi không có cụm nào thay đổi;

Footer Page 13 of 166.


Header Page 14 of 166.

12

Hình 2. 3 Mô tả thuật toán k-means [2, tr.403]

Trong thuật toán phương pháp tính khoảng cách gần nhất cho mỗi khách hàng dựa
vào công thức Euclidean, dựa trên [2,tr.389], như sau:
√
Trong đó Pk là giá trị của các điểm trung tâm. Do các tham số để đánh giá khoảng
cách có cùng thứ nguyên và bình đẳng vì vậy có thể sử dụng công thức Euclidean đối với
các tham số. Trong nhiều trường hợp các tham số không cùng thứ nguyên ,ví dụ thuộc tính
“giới tính” và “độ tuổi” của người, nên cần thiết phải chuyển đổi về cùng một đơn vị.

2.3

Đánh giá thuật toán

2.3.1 Đánh giá kết quả
Với kết quả đầu ra dạng mô tả điểm trung tâm với các thuộc tính có giá trị trung bình
của các phần tử trong nhóm, thuật toán đưa ra được kết quả phù hợp với nhu cầu phân tích

phương pháp phân cấp có độ phức tạp thuật toán

tuy nhiên phương pháp này không

sử dụng với các nhóm có hình dạng cầu vì không dùng công thức tính toán khoảng cách.
Các tiêu chí đánh giá và xếp loại một hành vi sử dụng ba tiêu chí cùng ý nghĩa, vì vậy cách
tính khoảng cách áp dụng trong thuật toán k-means đưa ra các nhóm hình cầu tỏ ra thích
hợp. Bên cạnh đó, việc phân cụm được lặp lại hàng ngày; việc tái sử dụng kết quả phân cụm
cũng giụp giảm số lần tái lặp , từ đó giảm chi phí thực hiện.
Thuật toán k-means có một nhược điểm là có khả năng chống nhiễu kém; nếu trong
nhóm có một lượng các giá trị nhiễu thì giá trị chung bình của nhóm sẽ bị thay đổi đáng kể
từ đó dẫn đến kết nạp sai lầm tại những vòng lặp xử lý sau. Tuy nhiên vẫn có thể áp dụng
một số phương pháp tiền xử lý dữ liệu đầu vào để giảm sự ảnh hưởng nhiễu.

2.4

Kết luận
Trong chương 2, luận văn đã trình bày các vấn đề :
 Giới thiệu thuật toán k-means.
 Cài đặt thuật toán k-means
 Đánh giá sơ bộ kết quả và khả năng triển khai thuật toán k-means vào công việc phân
cụm hành vi sử dụng dịch vụ viễn thông.
Chương tiếp theo luận văn trình bày quá trình áp dụng thuật toán k-means vào bài

toán phân cụm hành vi sử dụng khách hàng của mạng di động VMS Mobifone.

Footer Page 15 of 166.


Header Page 16 of 166.

Bảng 3. 1 Tổng lưu lượng và tỷ lệ lưu lượng của thuê bao theo thời gian

S (giây)
100

C (giây)
1000

T (giây)
50

PS
0.1

PC
1

PT
0.05

Luận văn đề xuất một số mẫu kết quả cần đạt được như sau:
Tiêu chí : đánh giá nhu cầu sử dụng dịch vụ của khách hàng theo khung thời gian.
Bảng 3. 2 Định dạng mẫu đánh giá nhu cầu sử dụng dịch vụ của khách hàng theo thời gian
Ngày

/Tuần Địa

/Tháng /Năm phương
báo cáo
(tỉnh/ thành

của một địa phương.
Bảng 3. 3 Định dạng mẫu đánh giá nhóm hành vi sử dụng dịch vụ thoại của khách hàng theo
ngày của một địa phương
Số thứ
tự cụm

Số
lượng Thời gian gọi trung bình
thuê bao
Buổi
Buổi
Buổi tối
sáng

chiều

Tổng thời gian gọi
Buổi

Buổi

sáng

chiều

Buổi tối

Tiêu chí : đánh giá nhóm hành vi sử dụng dịch vụ tin nhắn của khách hàng theo ngày
của một địa phương.
Bảng 3. 4 Định dạng mẫu đánh giá nhóm hành vi sử dụng dịch vụ tin nhắn của khách hàng

động (MSC – mobile switching center). VMS Mobifone quy định một chuẩn giản lược và
đang khai thác dữ liệu lịch sử cuộc gọi theo chuẩn đo. Cấu trúc dữ liệu được áp dụng cho tất
cả loại tổng đài và sử kiện và gồm hơn 43 trường. Dựa vào chuẩn dữ liệu VMS đang khai
thác, luận văn xác định các thuộc tính có thể khai thác để phục vụ bài toán gồm:
Thuộc tính “calling isdn” và “called_isdn” : sử dụng làm khóa xác định thuê bao.
Thuộc tính này ghi lại số điện thoại mà tổng đài phục vụ. số máy này theo nguyên tắc thuộc
về các thuê bao của Mobifone và các thuê bao sử dụng dịch vụ roaming qua mạng
Mobifone. Đối với bản ghi cuộc gọi đi calling_isdn chứa thuê bao thực hiện quay số, đối
với bản ghi cuộc gọi đến thì calling_isdn mang số máy nhận cuộc gọi hoặc tin nhắn. Thuộc

Footer Page 17 of 166.


Header Page 18 of 166.

16

tính calling_isdn lại có giá trị để phân biệt khách hàng vì vậy calling_isdn có thể làm mã
xác nhận phần tử trong thuật toán phân cụm k-means.
Thuộc tính “call type”: nhận biết loại dịch vụ. Gồm các giá trị : OG: cuộc gọi đi.
Số máy calling_isdn gọi cho số máy called_isdn; IC: cuộc gọi đến. Số máy calling_isdn
nhận cuộc gọi từ số called_isdn; SMO: tin nhắn đi. Số máy calling_isdn nhắn tin cho số
máy called_isdn; SMT: tin nhắn đến. Số máy calling_isdn nhận tin nhắn của called_isdn.
Để xác định hành vi khách hàng, các sự kiện chủ động được quan tâm vì vậy chỉ khai thác
sự kiện cuộc gọi đi (OG) và tin nhắn đi (SMO).
Thuộc tính “call sta time” : nhận biết thời điểm cuộc gọi. Thời điểm bắt đầu cuộc
gọi hay thời điểm tin nhắn. Định dạng dữ liệu là “DD/MM/YYYY HH:MI:SS”
(Ngày/tháng/năm giờ/phút/giây).
Thuộc tính “duration” : nhận biết lượng sử dụng của sự kiện. Đối với dịch vụ
thoại thời lượng gọi chỉ ra số giây khách hàng thực hiện một cuộc gọi. Đối với dịch vụ tin


Mã tỉnh/thành phố nơi đặt trạm

REGION

String

Mã trung tâm, nơi quản lý trạm.

Footer Page 18 of 166.


Header Page 19 of 166.

17

3.2.2 Khối lượng dữ liệu cần xử lý
VMS Mobifone có một hệ thống tổng đài MSC gồm 25 tổng đài. Trung bình một
ngày cần xử lý hơn 30000 file và dung lượng trung bình 57GB.
Theo thống kê, mỗi có khoảng 10 triệu thuê mobifone thực hiện 39 triệu cuộc gọi và
thực hiện gửi 52 triệu tin nhắn tinh trên toàn mạng. Quá trình tiền xử lý dữ liệu cho đầu vào
thuật toán k-means cần phải tổng hợp lượng sử dụng dịch vụ từ hơn 90 triệu bản ghi để tạo
thành một nguồn 10 triệu bản ghi trong đó mỗi bản ghi lưu số máy và các đặc trưng sử dụng
của số máy đó trong ngày.

3.3

Tiền xử lý dữ liệu đầu vào

3.3.1 Định dạng tập dữ liệu phần tử đầu vào thuật toán k-means


5

Ps

Tỷ lệ thời lượng sử dụng buổi sáng so với thời lượng lớn nhất

6

Pc

Tỷ lệ thời lượng sử dụng buổi chiều so với thời lượng lớn nhất

7

Pt

Tỷ lệ thời lượng sử dụng buổi tối so với thời lượng lớn nhất

Với dữ liệu định dạng file đầu ra liệt kê các điểm trung tâm có dạng:

Footer Page 19 of 166.


Header Page 20 of 166.

18

Bảng 3. 7 Cấu trúc dữ liệu đầu ra thuật toán k-means dạng mô tả điểm trung tâm
Số thứ tự

Tỷ lệ thời lượng sử dụng buổi tối so với thời lượng lớn nhất

3.3.2 Phương pháp xác định k điểm khởi tạo ban đầu
Mỗi một khách hàng cần được tổng hợp thành dữ liệu mô tả được tương quan lượng
sử dụng giữa các buổi trong ngày tính theo tỷ lệ phần trăm so với giờ cao điểm nhất. Tương
quan sử dụng dịch vụ giữa các khung giờ được định thành ba mức : 0; 0.5 và 1. Các giá trị
khung giờ có thể mang một trong ba giá trị; tuy nhiên có một ràng buộc là trong ba giá trị
phải bằng 1. Như vậy danh sách các điểm k khởi tạo gồm.
Bảng 3. 8 Danh sách k điểm khởi tạo sau khi điều chỉnh
Nhóm
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18


1
0
0.5
1
1
1
0
0
0
0.5
0.5
0.5
1
1
1

PT

1
1
0
0.5
1
1
1
0
0.5
1
0
0.5

(5)

Kiểm tra thuộc tính “call type”, nếu khác OG, SMO thì bỏ qua

(6)

Kiểm tra HashMap có chứa key có giá trị bằng thuộc tính
“calling_isdn”, nếu chưa có khởi tạo đối tượng mô tả hành vi và thêm
vào HashMap

(7)

Xác định khung thời gian

(8)

Cộng tích lũy giá trị “duration” vào thuộc tính mô tả lượng sử dụng của
khung thời gian xác định được tại bước (7). Với “call type” là SMO thì
coi giá trị “duration” = 1

(9)
(10)

Kết thúc lặp dòng
Kết thúc lặp file

(11)Kết thúc lặp thư mục
(12)Ghi tập mô tả thuộc tính ra đĩa nhớ

3.3.4 Xử lý nguồn nhiễu trong số liệu hành vi

Triển khai thuật toán phân lớp k-means
Luận văn sử dụng ngôn ngữ Java để triển khai thuật toán. Dưới đây là phần thiết kế

các lớp trong chương trình phân cụm. Chương trình gồm 03 lớp chính:
Lớp NormalObject chứa thông tin về hành vi sử dụng dịch vụ của một khách hàng.
Lớp này là một phần của lớp Cluster, phục vụ việc mô tả các giá trị trung bình lượng sử
dụng, tỷ lệ lượng sử dụng của các đối tượng trong cùng một cụm.
Lớp Cluster chứa thông tin về cụm gồm : số lượng phần tử trong nhóm và đặc tính
hành vi của nhóm.
Lớp Program triển khai thuật toán k-means.

3.5

Tăng tốc độ xử lý phân cụm
Nghiệp vụ phân cụm hành vi sử dụng dịch vụ sẽ phải thực hiện hàng ngày trên dữ

liệu lưu lượng ngày đó, khối lượng dữ liệu cần xử lý là rất lớn vì vậy việc lựa chọn k điểm
khởi tạo có ảnh hưởng nhiều đến thời gian xử lý. Hành vi khách hàng gần như biến đổi ít so
với ngày trước đó vì vậy các giá trị trung tâm cuối cùng của lần phân cụm ngày trước có thể
được dùng như các điểm khởi tạo cho thuật toán cho dữ liệu hôm sau. Các thời điểm sử
dụng lại các điểm khởi tạo mặc định:
 Ngày nghỉ lễ: thời gian này thói quen sử dụng dịch vụ khác với ngày thường.
 Ngày thứ 7: tương tự với nghỉ lễ 2 ngày nghỉ cuối tuần.
 Ngày sau kỳ nghỉ lễ: sau nghỉ lễ thói quen sử dụng dịch vụ trở lại bình thường.
 Ngày thứ 2: vì vậy thói quen sử dụng dịch vụ trở lại bình thường sau hai ngày nghỉ.

Footer Page 22 of 166.


Header Page 23 of 166.


400000000

Series18

350000000

Series17

300000000

Series16

250000000

Series15

200000000

150000000

Series14

100000000

Series13

50000000

Series12

điều kiện. Giả sử các thuê bao này thực hiện 1 phút cuộc gọi và mỗi khung giờ tối, số liệu
thu được sẽ là
Bảng 3. 10 Kết quả tăng doanh thu với gói khuyến mại cước khung giờ tối

Footer Page 24 of 166.


Header Page 25 of 166.

23

Như vậy tổng số doanh thu có thể thu thêm khoảng 506 triệu đồng một ngày với điều
kiện các thuê bao thỏa mãn gói khuyến mãi thực hiện thêm một phút gọi vào khung giờ tối.

3.8

Kết luận
Trong chương 3, luận văn đã trình bày các vấn đề:
 Phân tích chi tiết bài toán phân cụm hành vi sử dụng dịch vụ thoại và nhắn tin của
mạng di động VMS Mobifone.
 Khảo sát nguồn dữ liệu lịch sử cuộc gọi.
 Quá trình tiền xử lý dữ liệu lịch sử, tạo ra nguồn dữ liệu đầu vào phù hợp cho thuật
toán k-means.
 Triển khai thuật toán phân cụm k-means.
 Đánh giá kết quả thu được sau quá trình phân cụm.
 Nêu hướng khuyến nghị tăng hiệu quả sử dụng tài nguyên mạng dựa trên kết quả thu
được.

Footer Page 25 of 166.