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


Luận văn được hoàn thành tại:
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Người hướng dẫn khoa học: TS NGUYỄN MẠNH HÙNG

Phản biện 1: …………………………………………………………………………

Phản biện 2: …………………………………………………………………………

Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn thạc sĩ tại Học viện Công
nghệ Bưu chính Viễn thông
Vào lúc: giờ ngày tháng năm

Có thể tìm hiểu luận văn tại:
- Thư viện của Học viện Công nghệ Bưu chính Viễn thông

2 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

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
thuật toán phân cụm k-means và đánh giá khả năng áp dụng đối với bài toán phân cụm hành
vi khách hàng sử dụng dịch vụ viễn thông.
Chương 3: Áp dụng thuật toán k-means vào phân cụm hành vi sử dụng dịch vụ
thoại và nhắn tin. Chương này luận văn trình bày các bước xử lỷ dữ liệu, xây dựng các
nguồn dữ liệu đầu vào, thực hiện phân cụm theo phương pháp k-means và cuối cũng sẽ
đánh giá một số thông tin rút ra được từ kết quả sau khi phân cụm.

4 CHƯƠNG 1. BÀI TOÁN PHÂN NHÓM KHÁCH HÀNG DỰA TRÊN







(2)
 m là số cuộc gọi của khách hàng i trong khoản thời gian t.
 D
i,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 C
i
t
= m.
Khung thời gian có L
t
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
5

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ự.
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ự
đoán lớp của các đối tượng mà chưa gán được lớp.
Phân cụm dữ liệu: Khác với phân loại và dự báo dữ liệu, phân cụm dữ liệu là phân
tích dữ liệu mà không tham khảo một lớp dữ liệu biết trước nào. Với một nguồn dữ liệu biểu
diễn một tập các đối tượng, phân cụm dữ liệu sẽ nhóm các đối tượng thành các nhóm dựa
trên sự tối đa hóa sự sai khác các phần tử ở các nhóm khác nhau và tối thiểu hóa sự sai khác
giữa các phần tử cùng nhóm.
Phân tích bất thường: Một cơ sở dữ liệu có thể chứa các đối tượng dữ liệu mà
không tuân thủ với các hành vi chung, mang các đặc điểm về dữ liệu khác nhiều so với đại
bộ phận các đối tượng còn lại. Các đối tượng dữ liệu đó có thể coi là dữ liệu bất thường.
Đánh giá dữ liệu theo thời gian: tìm ra các mô hình mô tả xu hướng của dữ liệu

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.

9 CHƯƠNG 2. THUẬT TOÁN K-MEANS
2.1 Giới thiệu thuật toán k-means
Thuật ngữ "k-means" lần đầu tiên được sử dụng bởi James MacQueen vào năm 1967,
dựa trên ý tưởng trước đó của Hugo Steinhaus vào năm 1957. Tuy nhiên thuật toán hoản
thiện được đề xuất lần đầu tiên bởi Stuart Lloyd vào năm 1957 mặc dù nó đã không được
công bố cho đến năm 1982. Năm 1965, EWForgy công bố về một phương pháp về cơ bản
tương tự với thuật toán của Stuart Lloyd, vì vậy đôi khi thuật toán k-means cũng được gọi là
Lloyd-Forgy. Một phiên bản cải tiến đã được đề xuất và xuất bản tại Fortran bởi Hartigan và
Wong năm 1975/1979 [7].
Có nhiều loại phương pháp phân cụm dữ liệu, k-means là một trong số những thuật
toán phân cụm dựa trên phương pháp phân vùng. Phương pháp phân vùng được mô tả như
sau : Cho một cơ sở dữ liệu có n đối tượng hoặc bộ dữ liệu, một phương pháp phân vùng
xây dựng nên k vùng dữ liệu, nơi mà mỗi phân vùng đại diện cho một cụm và   . Có
nghĩa là, nó phân loại các dữ liệu vào k nhóm và cần đáp ứng các yêu cầu sau đây:
 Mỗi nhóm phải có ít nhất một đối tượng.
 Mỗi đối tượng phải thuộc về một nhóm.
Với k cho trước, chính là số lượng các phân vùng cần xây dựng, thuật toán tạo ra k
phân vùng đầu tiên. Sau đó sử dụng một kỹ thuật xác định nhóm cho các đối tượng lặp đi
lặp lại, các đối tượng được di chuyển từ nhóm này sang nhóm khác đến khi đạt được tối ưu.
Các tiêu chí chung của một phân vùng tốt là các đối tượng trong cùng một cụm có liên quan

Đầu vào thuật toán:
 k: số lượng các cụm,
 D: một tập dữ liệu chứa các đối tượng n.
Đầu ra thuật toán:
 Một tập hợp các k cụm.
Phương pháp [2]:
(1) tùy ý lựa chọn k đối tượng từ D là trung tâm cụm ban đầu;
(2) lặp lại
(3) Chỉ định (hoặc chỉ định lại) cho mỗi đối tượng một cụm mà đối tượng là
tương tự nhất (gần nhất), dựa trên giá trị trung bình của các đối tượng trong
cụm;
(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;
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:
 



 




 

  

  


13   là số phần tử trong tập phân cụm.
  là số cụm cần phân chia
  là số lần tái lặp xác định các phần tử trong mỗi cụm.
Thông thường  và  nhỏ hơn rất nhiều so với , tuy phương pháp phân cụm dựa trên
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.




; là giá trị tương quan lượng sử dụng buổi tối với lượng sử dụng lớn nhất.
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)
C (giây)
T (giây)
P
S

P
C

P
T
100
1000
50
0.1
1
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
/Tháng /Năm
báo cáo
Địa
phương

ngày của một địa phương
Số thứ
tự cụm
Số lượng
thuê bao
Thời gian gọi trung bình
Tổng thời gian gọi
Buổi
sáng
Buổi
chiều
Buổi tối
Buổi
sáng
Buổi
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
theo ngày của một địa phương
Số thứ

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
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
nhắn thuộc tính này không có giá trị, lúc này có thể đánh giá hành vi nhắn tin bằng tổng số
tin nhắn mà khách hàng gửi trong một khung thời gian.
Thuộc tính “cell id” : nhận biết địa điểm cuộc gọi được khởi tạo. Mỗi lần tổng đài
thực hiện khởi tạo dịch vụ thì đều ghi lại tọa độ nơi khách hàng bắt đầu sử dụng dịch vụ.
Tọa độ “cell id” chính là mã các trạm phát sóng di động quy hoạch theo mạng tổ ong. Với
cấp độ của bài toán hiện tại, luận văn chỉ khai thác thông tin đến địa bàn tỉnh, từ đó cung
cấp cái nhìn tổng quát các nhóm hành vi trên toàn tỉnh. Nguồn dữ liệu xác định địa bàn của
dựa vào cell_id có dạng sau:

định dạng đầu ra kiểu liệt kê phần tử (định dạng đầu vào thuật toán k-means) như sau:
Bảng 3. 6 Cấu trúc dữ liệu đầu ra thuật toán k-means dạng liệt kê phần tử
Số thứ tự
Tên cột
Ý nghĩa
1
Phone Number
Số điện thoại của khách hàng
2
S
Tổng số thời lượng sử dụng buổi sáng
3
C
Tổng số thời lượng sử dụng buổi chiều
4
T
Tổng số thời lượng sử dụng buổi tối
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:

18


C

Tỷ lệ thời lượng sử dụng buổi chiều so với thời lượng lớn nhất
9
P
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
P
S

P
C

P
T

0
0
0
1
1

0.5
9
0.5
1
1
10
1
0
0
11
1
0
0.5
12
1
0
1
13
1
0.5
0
14
1
0.5
0.5
15
1
0.5
1
16

(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) Kết thúc lặp dòng
(10) 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
Trong hai dịch vụ, dữ liệu thoại ít có nguồn nhiễu, mỗi cuộc gọi đều xuất phát từ nhu
cầu thật sự của cá nhân khách hàng.
Với dịch vụ nhắn tin nguồn nhiễu xuất hiện. Dịch vụ nhắn tin ngoài mục đích trao
đổi thông tin giữa hai người dùng còn có thêm một số trường hợp như : nhắn tin dịch vụ
(đăng ký nhạc chuông, ủng hộ quỹ xã hội, bình chọn trò chơi truyền hình v.v…); các tin
20 nhắn quảng bá từ tổng đài; tin nhắn quảng bá từ tư nhân. Vì vậy trong quá trình tổng hợp dữ
liệu sẽ loại bỏ các dữ liệu này. Cụ thể bộ lọc sẽ loại bộ các số dạng:
 Dạng 1800XXXX, 1900XXXX (X đại diện cho số từ 0 đến 9).
 Độ dài số máy  .
Quá trình lọc nhiễu được áp dụng trước quá trình phân cụm, và được triển khai trong
phần chuyển đổi định dạng theo mẫu định nghĩa, được trình bày tại phần 3.3.1 và 3.3.3.
3.4 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.

 Nội dung khuyễn mại: giảm 50% cước cuộc gọi thực hiện trong khoảng thời gian từ
20h đến 23h59 và từ 0h đến 4h sáng trong một tháng.
 Điều kiện áp dụng: thuê bao thực hiện ít nhất 100 phút (tương đương thực hiện
khoảng 200s đàm thoại vào buổi chiều) đàm thoại vào khung giờ 12h đến 20h trong
tháng trước.
Trường hợp gói cước được triển khai sẽ có nhiều 11 nhóm khách hàng thỏa mãn
đ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
0
50000000
100000000
150000000
200000000
250000000
300000000
350000000
400000000
450000000
500000000
Sáng
Chiều Tối
Tổng lượng sử dụng
Khung thời gian
Biểu đồ tương quan các nhóm hành vi trong ngày
21/09/2012 tại TP. Hồ Chí Minh
Series19
Series18
Series17
Series16