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

ĐỒ ÁN
TỐT NGHIỆP ĐẠI HỌC
Đề tài: “Ứng dụng khai phá dữ liệu để phân loại khách hàng viễn thông “

Giảng viên hướng dẫn: ThS. NGUYỄN QUỲNH CHI
Sinh viên thực hiện: LÊ TUẤN KHANG
Lớp

: D10HTTT2

Khoá : 2010-2015
Hệ

: Chính Quy

Hà Nội, tháng 11 /2014


NHẬN XÉT, ĐÁNH GIÁ, CHO ĐIỂM
(Của giáo viên hướng dẫn)

……………………………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………………………

……………
Điểm: ……………………………..(bằng chữ: ………………………………)
Đồng ý/ Không đồng ý cho sinh viên bảo vệ trước hội đồng chấm đồ án tốt nghiệp.
………………, ngày

tháng

năm 2014

GIÁO VIÊN PHẢN BIỆN


SVTH: Lê Tuấn Khang, Lớp D10HTTT2

LỜI CẢM ƠN
Em xin chân thành cảm ơn các thầy giáo, cô giáo trong khoa Công nghệ thông tin –
Học viện công nghệ bưu chính viễn thông, đã tận tâm giảng dạy các kiến thức
trong 4 năm học qua cùng với sự động viên từ gia đình và bạn bè và người thân
Đặc biệt em xin bày tỏ lòng biết ơn sâu sắc đến cô giáo Nguyễn Quỳnh Chi, người
đã tận tình hướng dẫn em thực hiện đồ án này. Tuy nhiên trong quá trình nghiên
cứu, thực hiện không tránh khỏi những thiếu sót, rất mong sự đóng góp ý kiến từ
tất cả thầy cô, bạn bè để đồ án có thể phát triển và hoàn thiện hơn.
Hà nội,tháng 11,năm 2014.
Người thực hiện.
Lê Tuấn Khang

Trang 4


SVTH: Lê Tuấn Khang, Lớp D10HTTT2

các thay đổi về chính sách, dịch vụ hay phản hồi nhằm đảm bảo doanh thu cũng như
đường lối của công ty .Các thông tin này rất quan trọng nhưng thường không có sẵn trong
các thông tin dạng thô, rất khó để sử dụng các phương pháp như liệt kê, tìm kiếm thông
thường. Ứng dụng khai phá dữ liệu nhằm phát hiện các thông tin ẩn chứa trong khối dữ
liệu khổng lồ và đưa ra những phỏng đoán (prediction) sẽ hỗ trợ quá trình ra quyết định
của các cấp lãnh đạo cũng như góp phần cải thiện, nâng cao hiệu quả của quá trình kinh
doanh của các của các doanh nghiệp (công ty) viễn thông.
Trong đề tài tốt nghiệp “Ứng dụng khai phá dữ liệu để phân loại khách hàng
viễn thông”, người viết sẽ tìm hiểu về khai phá dữ liệu và ứng dụng của nó trong thực
tiễn, đó là bài toán phân loại thông tin khách hàng viễn thông.

Mục tiêu nghiên cứu.

Trang 6


SVTH: Lê Tuấn Khang, Lớp D10HTTT2

Xây dựng chương trình thử nghiệm có thể áp dụng trong thực tế, giúp các doanh
nghiệp viễn thông phỏng đoán thói quen trả cước của khách hàng. Từ đó hỗ trợ việc ra
quyết định cũng như nâng cao hiệu quả của quá trình kinh doanh.

Đối tượng, phạm vi nghiên cứu.
Tìm hiểu về khai phá dữ liệu, thuật toán SVM, để phân loại khách hàng viễn thông
dựa trên dữ liệu đã có.
• Phạm vi nghiên cứu: Trong khuôn khổ kiến thức đã học cũng như nghiên cứu.
•

Phương pháp nghiên cứu.
Nghiên cứu các vấn đề cơ bản của khai khá dữ liệu, quá trình học máy, thuật toán máy

phía khách hàng hoặc phía công ty viễn thông. Khách hàng không trả phí dịch vụ đúng
hạn cho bên cung cấp dịch vụ như đã thỏa thuận trong hợp đồng, điều này gây ảnh hưởng
không nhỏ tới các công ty viễn thông. Việc không thu được phí dịch vụ đúng hạngây ảnh
hưởng xấu tới nhiều mặt của các doanh nghiệp viễn thông, bao gồm doanh thu, quá trình
kiểm toán, trả lương cho nhân viên… Mặc dù tình trạng xảy trên là điều không ai mong
muốn, tuy nhiên khi nó xảy ra thì các công ty viễn thông cần tìm cách giải quyết vấn
đề.Trong các giải pháp để giải quyết tình trạng này thì ngoài việc thống kê các khách
hàng có thói quen trả cước muộn, việc phỏng đoán, phân loại các khách hàng có thói
quen trả phí dịch vụ đúng hạn cũng quan trọng không kém. Việc phỏng đoán, phân loại
thói quen trả cước của khách hàng có nhiều ý nghĩa đối với các công ty viễn thông bởi
khi phỏng đoán, phân loại các khách hàng có thói quen trả cước tốt hay xấu không chỉ hỗ
trợ giải quyết được vấn đề đã nêu ở trên, mà còn giúp các công ty viễn thông có cái nhìn
chính xác hơn về các đối tượng khách hàng. Từ đó giúp các công ty viễn thông đề ra
chính sách đối với từng đối tượng khách hàng, hoặc hỗ trợ việc ra quyết định cũng như
nâng cao hiệu quả của quá trình kinh doanh.
Có thể cụ thể hóa bài toán cần giải quyết trong đề tài này như sau.
Phân loại, phỏng đoán thói quen trả cước dịch vụ của khách hàng (đúng hạn hay
không đúng hạn) dựa vào những dữ liệu viễn thông sẵn có (sẽ đề cập trong phần
sau).
• Phỏng đoán tháng trả cước không đúng hạn của các khách hàng trả cước không
đúng hạn.
•

1.2.

Dữ liệu đầu vào để giải quyết bài toán.
Các công ty viễn thông lưu trữ một khối lượng dữ liệu khổng lồ, bao gồm:
• Các thông tin cá nhân của khách hàng
• Các thông tin về dịch vụ của khách hàng
Trang 8

1.4.

Phương pháp tiếp cận.

Như đã nói ở phần đặt vấn đề, bài toán ở đây là phỏng đoán, phân loại khách
hàng viễn thông do đó phương pháp tiếp cận ở trong đề tài này đó là dùng ứng dụng của
khai phá dữ liệu để giải quyết bài toán. Trong đó, kĩ thuật khai phá dữ liệu được sử dụng
đó là phương pháp phân loại (classification)[1]. Các bước của quá trình khai phá dữ liệu
gồm 2 quá trình:
1.4.1. Quá trình huấn luyện mô hình phân loại.
• Tiền xử lý dữ liệu: Dữ liệu thô (các thông tin về khách hàng, dịch vụ, trả cước) thu

thập được không thể tiến hành khai phá được ngay mà phải được xử lý và tinh
chỉnh trước tiên, ta sẽ tiến hành một vài bước nhỏ hơn trong quá trình tiền xử lý
dữ liệu nhằm đưa tập dữ liệu thô trở thành tập dữ liệu mới ở dạng có thể khai phá,
áp dụng thuật toán được.

Trang 9


SVTH: Lê Tuấn Khang, Lớp D10HTTT2

Xây dựng mô hình phân loại: Sau quá trình tiền xử lý dữ liệu,ta tiến hành xây
dựng mô hình từ tập dữ liệu đã qua tiền xử lý dựa vào thuật toán phân loại SVM.
Kết quả của quá trình này là một bộ mô hình đã qua huấn luyện, có thể áp dụng
vào quá trình phân loại
• Đánh giá hiệu quả của mô hình phân loại: Sau quá trình xây dựng mô hình phân
loại, không phải kết quả thu được đã có thể sử dụng ngay bởi ngay trong quá trình
tiền xử lý cũng như huấn luyện mô hình, ta thường gặp phải nhiều vấn đề như
nhiễu dữ liệu (noise) hay dữ liệu quá vừa (overfiting).Bộ mô hình thu được có thể

Ta tóm gọn quá trình phân loại dữ liệu như trong hình dưới .

Hình 1.4.2. Mô tả các bước của quá trình phân loại dữ liệu.
1.5.

Một số vấn đề cần giải quyết.
Về bộ dữ liệu: Bộ dữ liệu thô ban đầu không thể tiến hành khai phá, phân loại
được ngay do các dữ liệu này vốn không đồng nhất, rời rạc, thiếu thuộc tính…. Do
đó phải tiến hành quá trình tiền xử lý, tuy nhiên tiền xử lý thế nào để dữ liệu được
đưa về dạng chuẩn, có thể sử dụng được, đạt hiệu quả tốt khi tiên hành phân loại là
một vấn đề cần giải quyết trong đồ án.
Về phương pháp phân loại: Phương pháp phân loại dựa trên thuật toán SVM, tuy
vậy vấn đề làm thế nào để xây dựng được bộ phân loại SVM đạt hiệu quả tốt, kết
quả thu được có độ chính xác cao,có thể sử dụng được trong thực tế là một yêu
cầu quan trọng của đồ án.
Về quá trình đánh giá độ chính xác: Hiệu quả của quá trình phân loại được thể
hiện qua các độ đo chính xác, tuy nhiên ta phải lựa chọn độ đo nào phù hợp với
bài toán, phản ánh đúng hiệu quả của quá trình phân loại .

1.6.

Kết luận.
Trang 11


SVTH: Lê Tuấn Khang, Lớp D10HTTT2

Như vậy trong chương 1, đồ án đã trình bày những vấn đề như sau:
Phát biểu bài toán phân loại, phỏng đoán thói quen trả phí dịch vụ của các khách
hàng sử dụng dịch vụ của các công ty viễn thông.


Hình 2.1.1.a. Mô tả các thuộc tính, lớp và giá trị

Trang 13


SVTH: Lê Tuấn Khang, Lớp D10HTTT2

Mục tiêu của bướchọc máy(học mô hình) là tìm ra một mô hình(thông qua thuật
toán học máy)thể hiện mối liên hệ, các luật giữa các thuộc tính và lớp . Mối liên hệ (hay
các luật) này được mô tả nhưng một hàm . Tức là tìm hàm sao cho:

Tập giá trị
Có thể mô tả bằng hình ảnh của quá trình học máy như sau

Hình 2.1.1.b. Mô tả quá trình học máy
Sau khi thu được mô hình, chúng ta sẽ tiến hành quá trình kiểm tra để xác định độ chính
xác của mô hình. Một tập kiểm tra bao gồm các thuộc tính và các giá trị của nó, tuy
nhiên ta chưa biết giá trị của lớp (y = ?). Ta sẽ sử dụng mô hình vừa tìm được để xác
định giá trị của thuộc tính lớp nhãn Y (xác định giá trị y) dựa vào hàm vừa tìm được.
Tóm lại ta đã có , ta đã có , ta sẽ xác định được các giá trị (y) của lớp .

Hình 2.1.1.c. Giá trị của lớp Class(y=?) chưa biết.

Trang 14


SVTH: Lê Tuấn Khang, Lớp D10HTTT2

Thông thường, tập dữ liệu có sẵn đang xét được phân của thành một tập dùng để huấn

đúng chia cho tổng số giá trị phỏng đoán. Tương tự ta cũng có độ đo lỗi phân loại được
tính theo công thức.

Tuy nhiên vấn đề gặp phải với độ chính xác accuracyđó là nó chỉ thể hiện mức độ phỏng
đoán đúng chứ không thể hiện mức độ phân loại chính xác, do đó ta sẽ xây dựng thêm 2
công thức đánh giá độ chính xác khác đó là precision và recall.

Trang 16


SVTH: Lê Tuấn Khang, Lớp D10HTTT2

Ta sử dụng ma trận lôn xôn (Confusion Matrix) [3] để đo hiệu quả của việc phân loại như
sau:

Lớp

Lớp dự đoán
Thuộc

Lớp thực tế

Không thuộc

Thuộc
Không thuộc

Trong đó:
TPi:(True positive) Số các giá trị thuộc lớp ci được phân loại chính xác vào lớp ci.Kí hiệu
là a.

theo tỉ lệ 2/3.
• Phương pháp xác nhận chéo (cross-validation): Theo phương pháp này, tập dữ
liệu được phân (ngẫu nhiên) thành N phần; ta sử dụng N-1 phần để huấn luyện
(training) và một phần còn lại để thử nghiệm (testing); quá trình này lặp lại cho
đến khi tất cả các phần đều được thử nghiệm. Kết quả cuối cùng là trung bình
cộng của cả N phần.Phương pháp houldoutlà trường hợp đặc biệt với N = 1. Trong
đồ án này chúng ta sử dụng N =10 để đảm bảo tính khách quan.

2.2. Thuật toán máy vector hỗ trợ SVM (Support vector machine).
2.2.1.Khái niệm và cơ sở của thuật toán SVM dựa trên bài toán phân loại
tuyến tính.
Phương pháp máy véc tơ hỗ trợ SVM (Support Vector Machine) ra đời từ lý
thuyết học thống kê do Vapnik và Chervonekis xây dựng năm 1995 [7], và có nhiều tiềm
năng phát triển về mặt lý thuyết cũng như ứng dụng trong thực tế.Phương pháp SVM có
khả năng phân loại khá tốt đối với bài toán phân lớp cũng như trong nhiều ứng dụng thực
tế.SVM là một phương pháp phân loại xuất phát từ lý thuyết thống kê, dựa trên nguyên
tắc tối thiểu rủi ro cấu trúc. SVM sẽ cố gắng tìm cách phân loại dữ liệu sao cho lỗi xảy ra
trên tập kiểm tra là thấp nhất.
Đầu tiên xét trường hợp đơn giản nhất đó là phân loại hai lớp tuyến tính. Tức là
phân loại hai lớp dựa trên phương trình bậc nhất.Tập dữ liệu D được định nghĩa bởi ,
trong đó là tập dữ liệu huấn luyện với lớp phân loại có giá trị là , có thể nhận 2 giá trị là
+1 và -1 (hay ). Đây được coi như bài toán phân loại hai lớp.

Trang 18


SVTH: Lê Tuấn Khang, Lớp D10HTTT2

Hình 2.2.1.a. Mô tả bài toán
Hình thức đơn giản của việc phân lớp là phân lớp nhị phân: phân biệt giữa các đối

margin).

Hình 2.2.1.d. Đường biên cực đại

Các điểm mà đường biên này chạm phải được gọi là các vector hỗ trợ (support
vectors). Đường biên cực đại này còn được gọi là siêu phẳng phân chia hai lớp với
khoảng cách từ nó tới điểm gần nhất là cực đại (maximum marginal hyperplane). Đây
chính là dạng đơn giản nhất của thuật toán SVM, còn được gọi là dạng SVM tuyến tính
(LSVM).
Như vậy, mục tiêu của thuật toán SVM là xây dựng một siêu phẳng giữa hai lớp
sao cho khoảng cách từ nó tới các điểm gần siêu phằng nhất của hai lớp là cực đại. Siêu
phẳng có thể được mô tả bởi phương trình:
(1)
Trong đó:
là vector trọng số (hay vector pháp tuyến).
- .
là một đại lượng vô hướng, thường liên quan đến độ nghiêng.
được gọi là hàm quyết định (Decision function)

Trang 21


SVTH: Lê Tuấn Khang, Lớp D10HTTT2

Theo yêu cầu của bài toán phân loại tuyến tính, ta phải chia các đối tượng thành 2 lớp
đó là (+1) và (-1). Áp dụng công thức (1) và các công thức toán học khác ta thu được
điều kiện phân loại đó là:
- Nếu . Phân loại đối tượng vào lớp dương (+1).
- Nếu . Phân loại đối tượng vào lớp âm (-1).
Từ hai bất đẳng thức trên, ta cũng thu được bất đẳng thức:

được các vector hỗ trợ (support vectors) như đã nêu trong phần 2.2.1. Quá trình huấn
luyện mô hình hoàn tất. Ta có thể tiến hành quá trình kiểm tra để tiến hành xác định độ
chính xác của mô hình

2.2.3. Bài toán phân loại dữ liệu tuyến tính không thể phân chia(linearly
inseparable data) bằng thuật toán SVM.
Trang 23


SVTH: Lê Tuấn Khang, Lớp D10HTTT2

Trong phần 2.2.1 và 2.2.2, ta đã tìm ra cách giải quyết bài toán phân loại tuyến
tính bằng cách tìm độ rộng cực đại của siêu phẳng. Tuy nhiên trong nhiều trường hợp, dữ
liệu tuyến tính không thể phân chia thành hai lớp theo phương pháp thông thường (hình
2.2.3.a)

Hình 2.2.3.a. Trường hợp không thể phân chia tuyến tính bằng một siêu phẳng.
Giải pháp:
• Chấp nhận huấn luyện có lỗi, tức là trong quá trình huấn luyện có một số đối
tượng bị phân loại sai lớp.
• Đồng thời phải tối thiểu hóa số đối tượng bị phân loại sai lớp.
Theo đó về mặt thuật toán:
Sử dụng một biến mềm sao cho

(*)

Bài toán tối ưu siêu phẳng trở thành:
Tối thiểu:

-