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

NGUYỄN LÊ PHƯƠNG

ỨNG DỤNG KHAI PHÁ DỮ LIỆU TÌM HIỂU THÔNG TIN
KHÁCH HÀNG VIỄN THÔNG

Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01
Người hướng dẫn khoa học: TS VŨ VĂN THỎA
TÓM TẮT LUẬN VĂN THẠC SĨ

HÀ NỘI - 2012
1
MỞ ĐẦU
Khai phá dữ liệu (KPDL) là một tiến trình khai phá tự động những tri thức
tiềm ẩn trong cơ sở dữ liệu, cụ thể hơn là tiến trình lọc sản sinh những tri thức hoặc
mẫu tiềm ẩn chứa thông tin hữu ích từ số lượng dữ liệu lớn. KPDL là tiến trình khái
quát các sự kiện rời rạc trong dữ liệu thành các tri thức mang tính quy luật, hỗ trợ

tranh. Bằng cách hiểu những hành vi và thói quen của khách hàng, những
công ty viễn thông sẽ đưa ra những chiến lược quảng bá hiệu quả để đưa
ra những sản phẩm mà khách hàng yêu thích, phát triển khách hàng trung
thành, và tăng lợi ích cho khách hàng.
 Tốc độ phát triển thuê bao: số lượng thuê bao đề cập đến doanh thu hàng
năm hoặc hàng tháng dựa trên cơ sở khách hàng. Việc canh tranh dẫn đến
tỉ lệ phát triển thuê bao cao. Ban đầu, việc tăng trưởng trong thị trường
viễn thông tăng theo cấp số nhân, do có rất nhiều khách hàng mới, tốc độ
phát triển thuê bao không phải là vấn đề. Khi thị trường trở nên bão hòa,
tốc độ phát triển thuê bao giảm. Việc bão hòa của các thuê bao và sự cạnh
tranh ngày càng gay gắt dẫn đến việc những công ty viễn thông sẽ phải
hướng tới vào những khách hàng đã có và tìm cách giữ họ lại. KPDLcó
thể dùng trong việc phân tích tốc độ phát triển thuê bao để dự đoán dựa
trên dữ liệu cụ thể là khách hàng sẽ không hoặc vẫn dùng sản phẩm của
công ty và tại sao.
 Bộ dữ liệu đồ sộ: các công ty viễn thông có một khối lượng dữ liệu đồ sộ.
Khi những sản phẩm chính của các công ty được sử dụng, mỗi khách
hàng đã tạo ra hàng trăm giao dịch trên một ngày. Một bản ghi cuộc gọi
được lưu trữ trong cơ sở dữ liệu và nó là một nguồn dữ liệu rất lớn. Các
công ty viễn thông cũng lưu trữ dữ liệu khách hàng, miêu tả khách hàng,
dữ liệu mạng, và miêu tả họ sử dụng những dịch vụ nào.
Luận văn: “Ứng dụng khai phá dữ liệu để tìm hiểu thông tin khách hàng
viễn thông” nhằm góp phần nghiên cứu các mục tiêu nêu ra ở trên. Luận văn gồm
các chương sau:
Chương 1: Tổng quan về khai phá dữ liệu
Chương 2: Khai phá dữ liệu bằng cây quyết định
Chương 3: Xây dựng hệ thống tìm hiểu thông tin khách hàng

3


Dựa trên thực tế, trên một khía cạnh nào đó, là đang tồn tại một lượng dữ
liệu hệ thống khổng lồ mà chưa được khám phá một cách cụ thể. Nghĩa là đang có
rất nhiều thông tin “ẩn giấu” và đã nằm ngoài khả năng phát hiện ra bởi những
phương thức truyền thống và dựa trên khả năng phân tích của con người.Sự cần
thiết của “khai phá” dữ liệu có thể miêu tả bằng sự cần thiết trong lĩnh vực cuộc
sống thực:
 Kinh tế, tài chính
 Chăm sóc sức khỏe
 Nghiên cứu khoa học
Vậy, KPDL là gì? Tuy nhiên rất khó khăn để đưa ra một định nghĩa duy nhất
mà phản ánh toàn sự kiện của hiện tượng. Vì thế, với từng cách tiếp cận khác nhau
sẽ có những cái nhìn khác nhau về KPDL:
 Là việc tìm kiếm tự động những mẫu trong CSDL khổng lồ, sử dụng
công nghệ tính toán từ thống kê, học máy và nhận biết mẫu;
 Là việc khai thác sự có ích của thông tin ẩn, mà trước đó chưa biết và có
khả năng thông tin là hữu ích từ dữ liệu;
 Kỹ thuật tách thông tin hữu dụng từ một tập dữ liệu lớn hoặc CSDL;
 Việc thăm dò tự động hoặc bán tự động và phân tích một lượng lớn của
dữ liệu, nhằm phát hiện những mô hình có ý nghĩa;
 Tiến trình tự động khám phá thông tin, việc xác định mô hình và mối
quan hệ ẩn giấu trong dữ liệu.
Tóm lại, KPDL là quá trình phân tích của một tập dữ liệu quan sát (thường là
rất lớn) để tìm ra những mối quan hệ ẩn giấu và tổng kết dữ liệu theo nhiều cách
nhằm dễ hiểu và dễ sử dụng cho người sở hữu dữ liệu đó.
1.2 Quá trình khai phá dữ liệu
Nói một cách đơn giản, KPDL liên quan đến việc “tách” hoặc “dò” tri thức
từ một lượng lớn của dữ liệu, khai phá tri thức từ dữ liệu, tách tri thức, phân tích
mẫu/dữ liệu
5


 Lấy mẫu (Sampling)
6
 Giảm chiều thông tin (Dimensionality reduction)
 Chọn tính năng (Feature selection)
 Tạo ra các tính năng (Feature creation)
 Rời rạc và nhị phân (Discretization and binarization)
 Chuyển đổi thuộc tính (Atrribute transformation)
1.2.2 Xây dựng và xác nhận mô hình
Xây dựng và xác nhận mô hình là một bước của tiến trình KPDL sau tiến
trình tiền xử lý. Chú ý rằng, trong một tiến trình KPDL, trạng thái dữ liệu xử lý sẽ
lặp lại nếu cần thiết. Một khi dữ liệu “khai phá” được chọn, cần phải quyết định lấy
mẫu dữ liệu như thế nào khi không làm việc với toàn bộ CSDL.
Một khi dữ liệu đã phân tích được xác định, khi đó sẽ quan tâm đến mục đích
của tiến trình KPDL.
 Hiểu các giới hạn
 Chọn hướng nghiên cứu thích hợp
 Kiểu nghiên cứu
 Lựa chọn thành phần
 Vấn đề lấy mẫu
 Đọc dữ liệu và xây dựng mô hình
1.2.3 Áp dụng và đánh giá mô hình
Sau khi mô hình xây dựng, áp dụng, cần phải quan tâm đến một số tính năng
quan trọng:
 Độ chính xác của mô hình (model accuracy)
 Độ dễ hiểu của mô hình (model intelligibility)
 Khả năng thực thi (performance)
 Nhiễu (noise)

tượng (phân lớp các đối tượng từng các thư mục), dựa trên những thuộc
tính khác;
 Mô hình sử dụng để dự đoán những lớp mới, những đối tượng chưa biết.
Tập dữ liệu kiểm thử cũng dùng dể xác định độ chính xác của mô hình.
8
Khi một mô hình phân loại được xây dựng, nó sẽ phải so sánh với những mô
hình khác để lựa chọn mô hình tốt nhất. Liên quan đến việc so sánh giữa các mô
hình phân loại (mô hình phân lớp), sẽ có một số thành phần cần được tính đến.
 Khả năng dự đoán (predictive accuracy)
 Tốc độ (speed)
 Độ mạnh mẽ (robustness)
 Độ mềm dẻo (scalability)
 Tính dễ diễn giải (interpreability)
 Độ đơn giản (simplicity).
1.3.2 Phân cụm
Nói đến phân cụm, nghĩa là nói đến chia một tập dữ liệu thành một vài cụm
(cluster), dựa trên việc xác định những đặc điểm chung.
 Các đối tượng thuộc 1 cụm là tương tự nhau.
 Đối tượng ở cụm này sẽ ít tương tự với đối tượng ở cụm khác.
Phân cụm dữ liệu được sử dụng nhiều trong các ứng dụng về phân đoạn thị
trường, khân khúc khách hàng, nhận dạng mẫu, phân loại trang web…
1.3.3 Luật kết hợp
Luật kết hợp là tiến trình xác định những luật phụ thuộc giữa những nhóm
khác nhau của hiện tượng. Khai phá luật kết hợp dựa trên hai bước:
 Tìm tất cả các tập mục phổ biến, được xác định qua tính hỗ trợ và thỏa
mãn độ hỗ trợ cực tiểu;
 Sinh ra các luật kết hợp từ các mục phổ biến, các luật phải thỏa mãn độ

 Viễn thông:
o Phát hiện gian lận trong cuộc gọi;
o Xác định các hồ sơ khách hàng trung thành;
o Xác định các nhân tố ảnh hưởng đến hành vi khách hàng liên quan
đến các kiểu gọi điện thoại;
o Xác định các rủi ro trong việc sử dụng đầu tư các công nghệ mới;
o Xác định những sự khác nhau giữa các dịch vụ và sản phẩm giữa
các đối thủ cạnh tranh.

10
Chương 2. KHAI PHÁ DỮ LIỆU BẰNG CÂY QUYẾT ĐỊNH
2.1 Cây quyết định
2.1.1 Vấn đề phân lớp
Dữ liệu vào của một nhiệm vụ phân lớp là một tập hợp những bản ghi. Mỗi
bản ghi, cũng được biết đến như một thể hiện hoặc ví dụ, được miêu tả bởi (x,y)=
(x
1
, x
2
, x
3
, x
k
, y) với x là tập thuộc tính, còn y là biến phụ thuộc
(dependantvariable) cần tìm hiểu, phân loại hay tổng quát hóa, (x
1
, x





(2.1)
Tương tự, khả năng thực thi chính xác của mô hình có thể biểu diễn dưới
dạng error rate, được cung cấp bởi điều kiện sau:
Error rate =
   
   
=












(2.2)
Hầu hết các thuật toán tìm kiếm trong phân lớp được chọn khi đạt được độ
chính xác cao nhất hoặc hiệu quả, và tỉ lệ lỗi thấp.
11

Hình 2.4: Các nút của cây quyết định
Thuật toán thường được sử dụng để phát triển là chiến lược tham lam. Nghĩa
là phát triển cây bằng cách đưa ra một chuỗi các quyết định tối ưu cục bộ về thuộc
tính được sử dụng trong dữ liệu. Một trong những thuật toán đó là thuật toán
Hunt’s, sử dụng đệ quy để phát triển cây.
Gọi D
t
là các nhóm của tập kiểm thử gắn với nútt và C = {c
1
,c
2
, c
c
} là tập
nhãn. Theo tuần tự, thuật toán Hunts thực hiện theo những bước sau:
1. Biểu diễn tập D
t
là tập các đối tượng học (dữ liệu) là nút t;
2. Nếu tập D
t
là tập rỗng, thì t cũng chính là nútđích (nút lá) được gán nhãn
bởi lớp O
t

3. Nếu D
t
chứa những đối tượng mà phụ thuộc vào cùng lớp C
t
, thì t cũng là
nút lá, gán nhãn C

if(all points in S are in the same class)then
return
for each attribute A do
evaluate splits on attribute A;
use the best found split to partition S into S1 and S2
Partition(S1)
Partition(S2)
}
Có rất nhiều đơn vị đo lường được sử dụng để xác định cách tốt nhất để chia
tách cây. Những đơn vị đo lường đó định nghĩa như những thuật ngữ của việc phân
chia thuộc tính lớp trước và sau khi chia.
 Chỉ số GINI (impurity)
 Chỉ số Entropy
 Biện pháp phân loại sai.
2.3.1.1 GINI index
Đặt f(i,j) là tần số xảy ra của lớp j tại nút i hoặc, nói theo cách khác, là vị trí
của đối tượng phụ thuộc vào lớp j mà phân chia đến nút i (với m điểm đích lớp của
đối tượng). Chỉ số GINI được tính như sau:
I

(
i
)
= 1 −  f

(
i,j
)



= I

(
i
)
= −
∑
f
(
i,j
)
.log

[
f
(
i,j
)]


(2.5)
Với tương tự như chỉ số GINI, f(i,j) là tần số xảy ra của lớp j tại nút i (tỷ lệ
của đối tượng của lớp j phụ thuộc vào nút i).
Khi nút cha được chia thành p phần, chất lượng của việc chia cắt được tính
bởi chỉ số Entropy splitting: Entropy
split
Entropy

= 


Với f(i,j) là tỷ lệ của đối tượng của lớp j mà gán bởi nút i.
Khi nút “cha” được chia thành p phần, chất lượng của việc phân chia đo bởi
chỉ số Error
split
:


= 





(

)


(2.8)
2.2 Một số thuật toán xây dựng cây quyết định
2.2.1 ID3
Đầu vào: Một tập các ví dụ. Mỗi ví dụ bao gồm các thuộc tính rời rạc, mô tả
một tình huống, hay một đối tượng nào đó, và một giá trị phân loại của nó
Đầu ra: Cây quyết định có khả năng phân loại đúng các ví dụ trong tập dữ
liệu rèn luyện, và phân loại đúng cho cả các ví dụ chưa gặp trong tương lai
15
Mã giả cho thuật toán ID3

j
, S) =| S
j
|/|S|
Với | S
j
| là kích thước tập các trường hợp có giá trị phân lớp là C
j
. |S| là kích
thước tập dữ liệu đào tạo. Việc tính toán chỉ số gain và tỉ lệ gain theo công thức 2.5
và 2.6
2.2.2 C4.5
C4.5 là thuật toán dùng để xây dựng cây quyết định được được đề xuất bởi
Ross Quinlan, là mở rộng của ID3 -
cite_note-0. Đặc điểm của C4.5 :
 Cho phép dữ liệu đầu vào ở các thuộc tính là liên tục;
 Cho phép thao tác với các thuộc tính có dữ liệu không xác định (do bị
mất mát dữ liệu, …);
 Đưa ra phương pháp “cắt tỉa” cây và giản lược các luật để phù hợp với
những bộ dữ liệu lớn.
C4.5 giới thiệu một số mở rộng của thuật toán ID3.
16
Đối với những thuộc tính liên tục sẽ được xử lý như sau:
1. Kỹ thuật Quick sort được sử dụng để sắp xếp các trường hợp trong tập dữ
liệu đào tạo theo thứ tự tăng dần hoặc giảm dần các giá trị của thuộc tính liên tục V
đang xét. Được tập giá trị V = {v
1

V
2
= {v
i+1
, v
i+2
, …, v
m
}
3. Xét (m-1) ngưỡng θ
i
có thể có ứng với m giá trị của thuộc tính V bằng
cách tính Information gain hay Gain ratio với từng ngưỡng đó. Ngưỡng có giá trị
của Information gain hay Gain ratio lớn nhất sẽ được chọn làm ngưỡng phân chia
của thuộc tính đó.
Đối với những giá trị thiếu
Trong quá trình xây dựng cây từ tập dữ liệu đào tạo S, B là tập dữ liệu kiểm
thử dựa trên thuộc tính A
a
với các giá trị đầu ra là (b
1
, b
2
, , b
t
). Tập S
0
là tập con các
trường hợp trong S mà có giá trị thuộc tính A
a

|

|
|

|
log (
|

|
|

|
) −
∑
|

|
||
log (
|

|
||
)


(công thức 2.10)
Hai thay đổi này làm giảm giá trị của kiểm thử liên quan đến thuộc tính có tỉ
lệ giá trị thiếu cao.

2.3.3 Điều kiện dừng cho quá trình tách
Có hai luật điều khiển dừng khi muốn dừng phân tách:
 Giá trị tối thiểu n
 Tỷ lệ của các đối tượng.
2.3.4 Cắt tỉa cây quyết định
Có hai kiểu của việc tỉa cây quyết định:
 Tiền cắt tỉa (Pre-pruning): dừng sớm việc phát triển cây trước khi nó
vươn đến điểm mà việc phân lớp các mẫu huấn luyện được hoàn thành.
Hậu cắt tỉa (Post-pruning): Chiến thuật này ngược với chiến thuật tiền
cắt tỉa, cho phép phát triển câyđầy đủ sau đó mới cắt tỉa.
2.3.5 Tách luật phân loại từ cây quyết định
Một khi cây quyết định đã được xây dựng, mô hình được sử dụng để đưa ra
quyết định một cách tối ưu. Tri thức đạt được bởi cấu trúc “của cây” có thể dễ dàng
“đọc” bằng duyệt cây theo từng “nhánh” đến lá (duyệt từ gốc đến ngọn), vì thế, luật
của cây phân loại theo câu lệnh if-then.
18
2.4 Đánh giá cây quyết định
2.4.1 Ưu điểm của cây quyết định
 Khả năng tạo ra những luật dễ hiểu.
 Khả năng xử lý với cả thuộc tính liên tục và thuộc tính rời rạc.
 Thể hiện rõ ràng những thuộc tính tốt nhất.
 Xử lý cả dữ liệu có giá trị bằng số và dữ liệu có giá trị theo loại
 Cây quyết định là mô hình hộp trắng (whitebox)
2.4.2 Nhược điểm của cây quyết định
 Mắc lỗi với quá nhiều lớp
 Việc đào tạo tốn kém


3.3 Thực hiện mô phỏng và đánh giá kết quả
3.3.1 WEKA
Weka chứa một tập các công cụ mô hình và thuật toán cho việc phân tích dữ
liệu và mô hình dự đoán, cùng với giao diện đồ họa cho người sử dụng dễ dàng truy
cập vào các chức năng.
Những ưu điểm của Weka:
 Miễn phí cho người sử dụng;
 Hỗ trợ trên nhiều nền tảng hệ điều hành;
 Là một tập hợp xử lý dữ liệu và kỹ thuật mô hình;
 Hỗ trợ đồ họa.
ARFF file: Attribute Relationship File Format (ARFF) là tập file text sử
dụng bởi weka cho việc lưu trữ dữ liệu từ cơ sở dữ liệu. Kiểu cấu trúc file như sau:
 @relation: xác định tên quan hệ
 @attribute: xác định thuộc tính
 @data:xác định dữ liệu
3.3.2 Thử nghiệm
Chọn nguồn dữ liệu

Hình 3.2: Chọn nguồn dữ liệu
21
Sử dụng c4.5 để phân lớp

Hình 3.3: Sử dụng C4.5 để xây dựng cây
Kết quả thử nghiệm:
Dạng text bao gồm các thông tin:

22

hướng và hỗ trợ ra quyết định đã trở thành một nhu cầu cần thiết trong phân tích dữ
liệu. Khóa luận cần được phát triển thêm để có thể xây dựng các ứng dụng phân tích
dữ liệu mang tính thông minh hơn.
Do điều kiện thời gian và hiểu biết của bản thân còn nhiều hạn chế nên chắc
chắn không tránh khỏi những thiếu sót. Rất mong nhận được sự góp ý chân thành
của các thầy cô, bạn bè và những người quan tâm đến đề tài này.