Ứng dụng Datamining cho bài toán dự đoán khách hàng sử dụng dịch vụ viễn thông

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (5.82 MB, 27 trang )

Trang 1<div class="page_container" data-page="1">

HỌC VIỆN CƠNG NGHỆ BƯU CHÍNH VIÊN THƠNG

</div>Trang 2<div class="page_container" data-page="2">

Luận văn được hồn thành tại:

HỌC VIEN CƠNG NGHỆ BƯU CHÍNH VIÊN THONG

Người hướng dẫn khoa học: TS. Nguyễn Đức Dũng

Phản biện 1: PGS.TS Nguyễn Linh Giang

Phản biện 2: TS. Nguyễn Văn Linh

Bưu chính Viễn thông

Vào lúc: 9 giờ 00 ngày 27 tháng 02 năm 2016

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

</div>Trang 3<div class="page_container" data-page="3">

MO DAU

Ngành công nghiệp viễn thông ngày nay cần lưu trữ một khối lượng dữ liệu không

lồ, bao gồm chi tiết cuộc gọi, thơng tin cảnh báo trình trạng của hệ thống mạng viễn thông và thông tin đữ liệu về khách hàng. Ứng dụng kỹ thuật khai phá dữ liệu (data mining) dé phát hiện các quy luật ân chứa trong khối dữ liệu khơng 16 đó sẽ mang lại cho các doanh nghiệp viễn thông nhiều cơ hội đề phát triển các ứng dụng mang tính thực tiễn

cao. Đây là một hướng đi phù hợp và đã sớm được áp dụng phổ biến ở nhiều công ty viễn

thông lớn trên thế giới.

Ở Việt Nam, nhu cau dich vụ viễn thông ngày càng gia tăng và mở rộng với nhiều

dich vụ tiện ich, bao gồm cả internet và băng rộng, có thể trở thành truy cập phố cập,

thay thế nhu cầu viễn thơng cố định. Chính vì vậy, một nhu cầu đặt ra cho các nhà cung cấp các dịch vụ viễn thông là đối mặt được với áp lực cạnh tranh khốc liệt từ các nhà

cung cấp dịch vụ trong nước đến các tập đồn viễn thơng đa quốc gia. Vì lý do đó các

cơng ty viễn thông không ngừng nâng cao, cải tiến các dich vụ của minh và tìm kiếm

dich vụ mới đề đáp ứng nhu cầu ngày càng lớn của khách hàng. Khai phá dữ liệu chính là

một trong những kỹ thuật hữu ích nhất dé giải quyết những van đề này.

Đã có nhiều cơng trình nghiên cứu khoa học trên thế giới và trong nước sử dụng

kỹ thuật phân loại dữ liệu cho bài tốn viễn thơng như: dự đốn th bao rời mạng, phân

loại khách hàng thành một nhóm đối tượng, hay tìm hiểu hành vi và thói quen của khách hàng, thì khác với các cơng trình nghiên cứu trước, trong luận văn này đi sâu và chỉ tiết

hơn về bài tốn viễn thơng, đó là dự đốn khách hàng sử dụng dịch vụ viễn thông và sử

dụng nhiều phương pháp để so sánh kết quả. Ngày nay ngành viễn thông phát triển rất mạnh, đòi hỏi các nhà mạng cần phải thêm các dịch vụ mới dé phuc vu khach hang, vi vậy việc dự đoán khách hang sử dung dịch vụ là hết sức quan trọng.

Luận văn “Ứng dụng Datamining cho bài toán dự đoán khách hàng sử dụng dịch vụ viễn thơng” nhằm giúp nhà mạng có thé dự đoán khách hàng sử dụng dich vụ, từ dự đốn đó nhà mạng có thể đưa ra chính sách quảng cáo, chính sách chăm sóc khách hàng hợp lý. Luận văn gồm các chương sau:

Chương 1: Tổng quan về phân tích và khai phá tri thức từ dir liệu viễn thông.

Chương 2: Kỹ thuật phân lớp dữ liệu

Chương 3: Ứng dụng bài toán dự đoán khách hàng sử dụng dịch vụ viễn thông.

</div>Trang 4<div class="page_container" data-page="4">

Chương I - TONG QUAN VE PHAN TÍCH VÀ KHAI PHA TRI

THUC TU DU LIEU VIEN THONG

1.1. Tổng quan về Khai phá dữ liệu

1.1.1. Quá trình khám phá tri thức

Quá trình khám phá tri thức gồm các bước sau [1]:

1) Data Cleaning (làm sạch dữ liệu

2) Data Integration (tích hợp dữ liệu)

3) Data Selection (chọn lựa dữ liệu)

4) Data transformation (biến đổi dit liệu)

5) Data mining (khai pha dữ liệu)

6) Pattern evaluation (đánh giá mau)

7) Knowledge presentation (biéu diễn tri thức)

Pattern Evaluation/ dIe++°

Hinh 1.1- Qua trinh kham pha tri thire

1.1.2. Các khái niệm về Khai phá dữ liệu

Khai pha dữ liệu (Data Mining) là một khái niệm ra đời vào khoảng những năm

cuối của thập kỷ 1980. Có rất nhiều định nghĩa khác nhau.

Về bản chất thì Khai phá dữ liệu là một q trình trích xuất thơng tin có mối quan hệ hoặc có mối tương quan nhất định từ một kho đữ liệu cực lớn nhắm mục đích đự đốn các xu thế, các hành vi trong tương lai hoặc tìm kiếm những tập thơng tin hữu ích mà bình thường không thể nhận diện được [7] [1].

</div>Trang 5<div class="page_container" data-page="5">

Data Warehouse Server

H data cleaning, integration and selection ¡

Database, Data Warehouse, World Wide Web, và Information repositoriesDatabase or Data Warehouse Server

Knowledge Base

Data Mining Engine

V Vv VY WV

Pattern Evaluation Module

> User Interface

1.2. Nhiệm vu chính của khai phá dữ liệu

Nhiệm vụ của khai phá đữ liệu có thể phân thành hai loại chính đó là [7]:

Classification Regression Time Series Prediction Clustering Summarization Association Sequence

Analysis Rules Discovery

</div>Trang 6<div class="page_container" data-page="6">

1.3. Các kỹ thuật trong khai phá dữ liệu

> Theo quản điểm học máy có các kỹ thuật sau:

+) Hoc có giảm sát (Supervised learning):

+) Học không giảm sat (Unsupervised learning):

+) Học nửa giám sát (Semi-Supervised learning):

> Theo các lớp của bài tốn cần giải quyết thì có các kỹ thuật sau:

+) Phân lớp dit liệu (Classification)+) Phân cum (Clustering

+) Hồi qui (Regression)

+) Luật kết hợp (Association rules)

+) Phân tích chuỗi theo thời gian (Time Series Analysis +) Mô tả khái niệm và tổng hợp hóa

1.4. Ứng dung của khai phá dữ liệu

1.4.1. Lợi ích mang lại của khai pha dữ liệu

Trong thời hiện đại ngày nay, việc nắm bắt được thơng tin coi như là nắm bắt được chìa khố của thành cơng. Ai thu thập, phân tích và hiểu được thông tin và hành

động được nhờ vào những thông tin đó là kẻ thắng cuộc.

1.4.2. Các lĩnh vực được ứng dụng khai pha dữ liệu

Một số ứng dụng cụ thể như sau [7]:

> Khai phá dữ liệu được sử dụng dé phân tích dữ liệu, hỗ trợ ra quyết định.

> Trong sinh học: Khai phá dữ liệu được dùng dé tìm kiếm, so sánh các hệ gen va thơng tin di truyền, tìm mối liên hệ giữa các hệ gen và chan đoán một số bệnh di truyền.

> Trong y học: giúp tim ra mối liên hệ giữa các triệu chứng lâm sàng, chan đốn

> Tài chính và thị trường chứng khốn: Khai phá dữ liệu dé phân tích tình hình tài chính, phân tích đầu tư, phân tích cổ phiếu.

> Khai phá dữ liệu web, thông tin kỹ thuật: Khai phá dit liệu dùng dé phân tích

các sai hỏng, điều khién và lập lịch trình.

> Trong lĩnh vực viễn thông

1.5. Ứng dụng của khai phá dữ liệu trong lĩnh vực viễn thơng

</div>Trang 7<div class="page_container" data-page="7">

1.5.1. Tình hình phát triển của lĩnh vực viễn thông

Ung dung kỹ thuật khai phá dữ liệu dé phát hiện các quy luật ấn chứa trong khối

dữ liệu khơng lồ đó sẽ mang lại cho các doanh nghiệp viễn thông nhiều cơ hội để phát triển các ứng dụng mang tính thực tiễn cao. Đây là một hướng đi phù hợp và đã sớm

được áp dụng phô biến ở nhiều công ty viễn thông lớn trên thế giới [3][10].

1.5.2. Sự cần thiết của khai phá dữ liệu trong lĩnh vực viễn thơng

Bài tốn đặt ra cho các nhà mạng di động là thu thập được các tri thức từ các kho

dữ liệu khách hàng không lồ. Ứng dụng kỹ thuật khai phá dữ liệu để phát hiện các quy

luật an chứa trong khối dữ liệu khong 16 đó và đưa ra những dự đoán, quyết định đúng, sẽ

mang lại cho các doanh nghiệp viễn thông nhiều cơ hội dé phát triển các ứng dụng mang

tính thực tiễn cao.

1.5.3. Định hình và Phân loại khách hàng viễn thông

Phân loại khách hàng viễn thông là q trình phân chia nhóm khách hàng thành

các nhóm đồng nhất theo từng thuộc tính chung của họ. Những thuộc tính này bao gồm như: sở thích, thói quen, hành động thông qua hồ sơ của khách hàng bởi những đặc điểm của họ như: độ ti, tích cách giới tính, đặc điểm khu vực nơi ở, thu nhập kinh tế...

1.5.4. Các loại dữ liệu viễn thơng

Có ba loại lữ liệu viễn thông như sau:> Dữ liệu chỉ tiết cuộc gọi

> Tiếp thị hoặc dự báo hành vi của khách hàng

> Phân tích xác định lỗi mạng và cơ lập lỗi mạng.

</div>Trang 8<div class="page_container" data-page="8">

Chương 2 - KY THUẬT PHAN LỚP DU LIEU

2.1.Téng quan về phân lớp dữ liệu

2.1.1. Phân lớp dữ liệu

Quá trình phân lớp dữ liệu gồm hai bước như sau:

s* Bước 1: Hoc (training)

Mơ hình phân lớp được đưa ra sau khi đã phân tích xong tap dir liệu huấn luyện

thường có dạng là những quy tắc phân lớp, cây quyết định hay các công thức tốn học [6]

Combior Car Type =Sports

Hình 2.1 - Bước xây dung mơ hình phan lớp [4]

s* Bước 2 Phân lớp (Classification)

Bước này sử dụng mơ hình phân lớp đã được xây dựng ở bước 1 dé kiểm tra, đánh

giá và thực hiện phân lớp. [6] [4].

Classifier (model)

Hình 2.2 - Kiếm tra độ chính xác của mơ hình

</div>Trang 9<div class="page_container" data-page="9">

Nếu độ chính xác của một mơ hình là chấp nhận được, thì có thể được sử dụng dé

phân lớp những bộ dữ liệu mới hoặc những mẫu dữ liệu mà giá trị nhãn phân lớp là chưa

Hình 2.3 - Phân lớp cho dữ liệu mới [4]

2.1.2. Tiền xử lý dữ liệu cho q trình phân lóp dữ liệu

Q trình tiền xử lý dữ liệu gồm có các cơng việc sau:

> Làm sạch dit liệu

> Phân tích sự can thiết của dữ liệu

> Chuyển đổi dữ liệu

2.1.3. Cac kỹ thuật trong phân lớp dữ liệu

Trong kỹ thuật phân lớp chúng ta có thể sử dụng các phương pháp sau:> Cây quyết định (Decision Tree):

> K-láng giêng gan nhất (k-Nearest Neighbor)

> Mạng noron (Neural networks)

> Giải thuật di truyén (Genetic algorithms)

> Mang Bayesian (Bayesian networks)

> Tập mo và tập thô (Rough and Fuzzy Sets)

2.1.4. Các phương pháp đánh gia độ chính xác của mơ hình phân lớp

Hai kỹ thuật đánh giá độ chính xác phổ biến hiện nay là holdout và k-fold cross-validation. Cả hai kỹ thuật này đều dựa trên các phân hoạch ngẫu nhiên tập dữ liệu ban

đầu. [4] [7].

</div>Trang 10<div class="page_container" data-page="10">

2.2. Phân lớp dữ liệu dựa trên kỹ thuật Naive Bayes

2.2.1. Kỹ thuật Naive Bayes

Cho trước tập dữ liệu huấn luyện D với mô tả (nhãn) của các lớp C¡, i=1..m, quá trình phân loại một tuple/đối tượng X = (x), Xa, ..., xạ) với mang Bayes như sau [20] [1]:

P(X 1C,)=] J Py IC) = PQ IC) * Pl 1C,)*..* P(x, 1G)

> P(XIC) được tinh vdi'gia định class conditional independence.

> x,, k = 1..n: trị thuộc tinh A, của X> P(x,/C;) được tính như sau:

+) A, là thuộc tính rời rac.

+) Laplace (Pierre Laplace, nhà toán học Pháp, 1749-1827)

P(XAIC;) = (| {X? |x’, = XR AX’ e C¡}I+1)/(C;pl + m)+) z-estimate

P(XIC,) = (|{Xˆ|x”x = XK AX’ e Ci} + Z*P(x¿))/(C¡ pl + Z)

2.2.2. Vi dụ minh họa

Bài tốn chơi Tennis, có 14 bản ghi, được mô tả như sau [3] [19]:

Quang cảnh | Nhiệt độ | Độ 4m Gió Chơi tennis

Nang Nong Cao Nhe Không

</div>Trang 11<div class="page_container" data-page="11">

Mưa Am áp Cao Mạnh Không

Bảng 2.1. Dữ liệu bài tốn chơi Tennis

Ta có 14 mẫu trong đó có 9 tập mẫu phân lớp là (+) và 5 tập mẫu là (-), Ta đi tính

xác xuất cho từng thuộc tính như sau:

> Tính xác suất cho thuộc tính phân lớp:

</div>Trang 12<div class="page_container" data-page="12">

Từ xác suất của từng thuộc tinh này ta có thé dự đốn cho từng mẫu cụ thé.

Ví dụ ta muốn tính mẫu D = {Quang cảnh|nắng, Nhiệt độlắm áp, Độ âmlcao,

2.2.3. Đánh giá Naive Bayes trong khai pha dữ liệu

Phân loại Naive Bayes được triển khai rất rộng rãi trong khai pha đữ liệu vi dé hiểu, dễ triển khai . Tuy nhiên, Bayes giả thiết rằng các biến trong mơ hình là độc lập nhau. Nếu các bién không độc lập nhau thì Bayes cho kết quả thiếu chính xác. [1][20]

2.3. Phân lớp dữ liệu dựa trên kỹ thuật cây quyết định 2.3.1. Phân lóp dữ liệu dựa trên cây quyết định

Trong cây quyết định gồm có:

> Gốc: là node trên cùng của cây

> Node trong: biéu diễn một kiểm tra trên một thuộc tinh đơn (hình chữ nhật) > Nhánh: biéu diễn các kết quả của kiểm tra trên node trong (mũi tên)

> Node lá: biểu diễn lớp hay sự phân phối lớp (hình trịn)

2.3.2. Xây dựng cây quyết định

Qua trình xây dựng cây quyết định đều được chia làm ba giai đoạn cơ bản sau [4]:

> Xây dựng cây

> Cắt tỉa cây

> Đánh giá cây

</div>Trang 13<div class="page_container" data-page="13">

Có ba tiêu chuẩn xác định thuộc tính tốt nhất phát triển tại mỗi node [4]: > Gini-index (Breiman và các đồng sự, 1984):

> Information—gain (Quinlan, 1993)

> x2 -bảng thông kê các sự kiện xảy ra ngẫu nhiên

2.3.3. Sử dụng thuật toán ID3 xây dựng cây quyết định

2.3.3.1. Thuật toán ID3

ID3 xây dựng cây quyết định từ trên- xuống (top -down), ID3 biểu diễn các khái

niệm ở dạng các cây quyết định biểu diễn này cho phép chúng ta xác định phân loại một

đối tượng bằng cách kiểm tra các giá trị của nó trên một số thuộc tính nào đó. [3]

2.3.3.2. Lựa chọn thuộc tính tốt nhất để phân loại a) Entropy do tính thuần nhat của tập dữ liệu:

- Nếu trong tập S có số mẫu phân bồ đều nhau vào các lớp thì Entropy (S) =1

- Các trường hợp còn lại: 0< Entropy(S) <1

b) Information Gain (viết tắt là Gain):

Gain là đại lượng dùng dé đo tính hiệu quả của một thuộc tính được lựa chọn cho

việc phân lớp. Đại lượng này được tính thơng qua hai giá trị Information và Entropy.

Gain(A,S)= Eniropy(S)— > LS, |

yeValues(A) 1S | Entropy(S,,)

- § là tập hợp ban đầu với thuộc tinh A. Các giá trị của v tương ứng là các giá trị

của thuộc tính A

- Sy bằng tập hợp con của tập S mà có thuộc tinh A mang giá trị v

- [Sy| là số phần tử của tập Sy; |S| là số phan tử của tập S

</div>Trang 14<div class="page_container" data-page="14">

Trong quá trình xây dựng cây quyết định theo thuật toán ID3 tại mỗi bước triển khai cây, thuộc tính được chọn dé triển khai là thuộc tính có giá trị Gain lớn nhất

c) Giải thuật ID3 xây dựng cây quyết định từ trên xuống Đầu vào: Một tập hợp các ví dụ

Đầu ra: Cây quyết định có khả năng phân loại

Thuật toán ID3 xây dựng cây quyết định theo giải thuật sau:

Function induce_tree (án ví dụ, tập thuộc_ tính) [4]

if mọi ví dụ trong tập ví dụ déu nam trong cùng một lop then

return một nut lá được gan nhãn bởi lớp đó

else if t@p_thudc_tinh là rong then

return mit lá được gán nhãn bởi tuyển của tat cả các lép trong tập_ ví dụ

chọn một thuộc tính P, lấy nó làm sốc cho cây hiện tại,

xóa Pra khỏi tập thuộc tính;

với mỗi giá trị V của P

tạo một nhánh cua cây gan nhãn V;

Đặt vào phân_ vùng các ví dụ trong tập ví dụ có gia trị V tại thuộc

2.3.3.3. Vi dụ minh họa với bài toán chơi Tennis

Giả sử S là một tập 14 mẫu trong đó có 9 (+) và 5(-) ta có:

Entropy (S) = - (9/14) Log, (9/14) - (5/14) Log, (5/14) = 0.940

Từ đó ta tính tiếp Gain cho từng thuộc tinh dé chon làm nút gốc như sau:

Gain (S, Quang cảnh) = Entropy(S) — (5/14) Entropy (Sqáng) — (4/14) Entropy (Samu) —(5/14) Entropy (Sua) = 0.246

Gain (S, Nhiệt độ) = Entropy (S) - (4/14) x Entropy (Snong) - (6/14) x Entropy (SAm áp) —

(4/14) x Entropy (Sma) = 0.029

Gain (S, Gió) = Entropy (S) - (6/14) x Entroy (Swann) - (8/14) x Entropy (Syne) = 0.04

Gain (S, Độ 4m) = Entropy (S) — (7/14) x Entropy (Scao) — (7/14) x Entropy (S7g)= 0.151

</div>Trang 15<div class="page_container" data-page="15">

Hình 2.4- Cây quyết định có Quang cảnh được chọn làm node gốc

Tương tự sau khi xét được nút gốc thì ta đi xét từng nhánh cịn lại ta thu

được cây qut định hồn chỉnh như sau:

Hình 2.5. Cây quyết định hồn chỉnh

2.3.4. Sứ dụng thuật tốn C4.5 xây dựng cay quyết định

2.3.4.1. Thuật toán C4.5

Thuật toán C4.5 được cải tiến từ thuật tóan ID3 với việc cho phép xử lý trên tập

đữ liệu có các thuộc tinh số (numeric atributes) và làm việc được với tập dữ liệu bị thiếu

và bị nhiễu. Nó thực hiện phan lớp tập mẫu dữ liệu theo chiến lược ưu tiên theo chiều sâu

(Depth - First). Thuật toán xét tat cả các phép thử có thé dé phân chia tập dữ liệu đã cho

va chọn ra một phep thử có giá trị GainRatio tốt nhất.

Information Gain theo công thức sau:

</div>Trang 16<div class="page_container" data-page="16">

T; là tập con của tập T ứng với thuộc tính X = giá trị là vị.

Đối với các thuộc tính liên tục, chúng ta tiến hành phép thử nhị phân cho mọi giá trị của thuộc tính đó. Đề thu thập được giá trị Entropy gain của tất cả các phép thử nhị

phân một cách hữu hiệu ta tiến hành xắp xếp cac dữ liệu theo giá trị của thuộc tinh liên

tục đó băng thuật tốn Quicksort.

2.3.4.2. Một số cải tiễn mới của thuật tốn C4.5

- Thích hợp được với các dit liệu liên tục

- Có thé chuyên đổi từ Cây quyết định thanh các Luật - Lam việc với đữ liệu bị thiếu, bị nhiễu

- Làm việc với thuộc tinh đa trị, thuật toán C4.5 đã đưa ra các đại lượng GainRatio vàSplitInfo (SplitInformation), xác định theo các công thức sau:

+) Giá trị SplitInfo là đại lượng đánh gia thông tin tiềm năng thu thập được khi

phân chia tập T thành n tập hợp con.

+) GainRatio la tiêu chuẩn dé đánh giá việc lựa chọn thuộc tính phân loại. [7]