Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu các phương pháp phân lớp dữ liệu và ứng dụng trong bài toán dự báo thuê bao rời mạng viễn thông

ĐẠI HỌC THÁI NGUYÊN ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

Nguyễn Nhƣ Thế Nguyễn Nhƣ Thế NGHIÊN CỨU CÁC PHƢƠNG PHÁP PHÂN LỚP DỮ LIỆU NGHIÊN CỨU CÁC PHƢƠNG PHÁP PHÂN LỚP DỮ LIỆU VÀ ỨNG DỤNG TRONG BÀI TOÁN DỰ BÁO THUÊ BAO VÀ ỨNG DỤNG TRONG BÀI TOÁNDỰ BÁOTHUÊ BAO RỜI MẠNG VIỄN THÔNG RỜI MẠNG VIỄN THÔNG

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái Nguyên -2016 Thái Nguyên - 2016

ĐẠI HỌC THÁI NGUYÊN ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

Nguyễn Nhƣ Thế Nguyễn Nhƣ Thế NGHIÊN CỨU CÁC PHƢƠNG PHÁP PHÂN LỚP DỮ LIỆU NGHIÊN CỨU CÁC PHƢƠNG PHÁP PHÂN LỚP DỮ LIỆU

VÀ ỨNG DỤNG TRONG BÀI TOÁN DỰ BÁO THUÊ BAO VÀ ỨNG DỤNG TRONG BÀI TOÁNDỰ BÁOTHUÊ BAO

RỜI MẠNG VIỄN THÔNG RỜI MẠNG VIỄN THÔNG

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

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƢỜI HƢỚNG DẪN KHOA HỌC:TS.NGUYỄN LONG GIANG NGƢỜI HƢỚNG DẪN KHOA HỌC: TS NGUYỄN LONG GIANG

Thái Nguyên -2016 Thái Nguyên - 2016

i

LỜI CAM ĐOAN

Tên tôi là: Nguyễn Nhƣ Thế

Sinh ngày: 12/12/1989

Học viên lớp cao học: CHK13E - Trƣờng Đại học Công nghệ thông tin

và Truyền thông – Đại học Thái Nguyên.

Hiện đang công tác tại: Sở Thông tin và Truyền thông tỉnh Phú Thọ

Xin cam đoan: Đề tài “Nghiên cứu các phương pháp phân lớp dữ liệu

và ứng dụng trong bài toán dự báo thuê bao rời mạng viễn thông” do Thầy

giáo TS. Nguyễn Long Giang hƣớng dẫn là công trình nghiên cứu của riêng

tôi. Tất cả tài liệu tham khảo đều có nguồn gốc, xuất xứ rõ ràng.

Tác giả xin cam đoan tất cả những nội dung trong luận văn đúng nhƣ nội

dung trong đề cƣơng và yêu cầu của thầy giáo hƣớng dẫn. Nếu sai tôi hoàn

toàn chịu trách nhiệm trƣớc hội đồng khoa học và trƣớc pháp luật.

Thái Nguyên, ngày 28 tháng 6 năm 2016

HỌC VIÊN

Nguyễn Nhƣ Thế

ii

LỜI CẢM ƠN

Sau một thời gian nghiên cứu và làm việc nghiêm túc, đƣợc sự động

viên, giúp đỡ và hƣớng dẫn tận tình của Thầy giáo hƣớng dẫn TS. Nguyễn

Long Giang, luận văn với đề tài “Nghiên cứu các phương pháp phân lớp dữ

liệu và ứng dụng trong bài toán dự báo thuê bao rời mạng viễn thông”đã

hoàn thành.

Tôi xin bày tỏ lòng biết ơn sâu sắc đến:

Thầy giáo hƣớng dẫn TS. Nguyễn Long Giang đã tận tình chỉ dẫn, giúp

đỡ tôi hoàn thành luận văn này.

Tôi xin bày tỏ lòng biết ơn đến các thầy cô trong Trƣờng Đại học Công

nghệ thông tin và Truyền thông – Đại học Thái Nguyên đã giúp đỡ tôi trong

quá trình học tập cũng nhƣ thực hiện luận văn.

Tôi xin cảm ơn Chi nhánh Mobifone Phú Thọ đã nhiệt tình giúp đỡ, cung

cấp thông tin trong quá trình nghiên cứu, thực nghiệm chƣơng trình luận văn.

Tôi xin chân thành cảm ơn bạn bè, đồng nghiệp và gia đình đã động

viên, khích lệ, tạo điều kiện giúp đỡ tôi trong suốt quá trình học tập, thực hiện

và hoàn thành luận văn này.

Thái Nguyên, ngày 28 tháng 6 năm 2016

HỌC VIÊN

Nguyễn Nhƣ Thế

iii

MỤC LỤC LỜI CAM ĐOAN ............................................................................................................. i

LỜI CẢM ƠN .................................................................................................................. ii

DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT .................................................... v

DANH MỤC HÌNH ẢNH .............................................................................................. vi

DANH MỤC BẢNG BIỂU........................................................................................... vii

MỞ ĐẦU .......................................................................................................................... 1

Chương 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU .................................................. 3

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

1.1.1. Tại sao cần khai phá dữ liệu .................................................................... 3

1.1.2. Các khái niệm cơ bản .............................................................................. 3

1.1.3. Quy trình khai phá dữ liệu ....................................................................... 5

1.1.4. Các bài toán cơ bản trong khai phá dữ liệu .............................................. 6

1.1.5. Các ứng dụng của khai phá dữ liệu .......................................................... 7

1.1.6. Quy trình xây dựng mô hình khai phá dữ liệu .......................................... 8

1.2.Bài toán phân lớp và dự báo ......................................................................... 10

1.2.1. Giới thiệu bài toán ................................................................................. 10

1.2.2 Các bƣớc giải quyết bài toán ................................................................. 11

Chƣơng 2: CÁC PHƢƠNG PHÁP PHÂN LỚP TRONG KHAI PHÁ DỮ LIỆU .... 12

2.1. Phân lớp bằng phƣơng pháp quy nạp cây quyết định ................................... 12

2.2. Phân lớp bằng phƣơng pháp Bayesian ......................................................... 15

2.3. Support Vector Machine (SVM) ................................................................. 16

2.3.1 Phân tách tuyến tính với lề cực đại ......................................................... 16

2.3.1.1. Tìm kiếm siêu phẳng với lề cực đại .................................................... 21

2.3.1.2. Hàm phân loại tuyến tính với lề mềm cực đại ..................................... 22

2.3.1.3. Lý thuyết tối ƣu Lagrangian ............................................................... 23

2.3.1.4. Tìm kiếm siêu phẳng với lề cực đại .................................................... 25

2.3.2. Phƣơng pháp hàm nhân (kernel methods) ................................................... 28

2.3.2.1 Chiều VC về khả năng phân tách của hàm tuyến tính .......................... 29

2.3.2.2 Hàm nhân và SVM phi tuyến (Kernel function and nonlinear SVMs) . 30

iv

2.4. Phân lớp bằng mạng lan truyền ngƣợc (mạng Nơron) .................................. 33

Chƣơng 3: ỨNG DỤNG BÀI TOÁN PHÂN LỚP DỮ LIỆU THUÊ BAO RỜI MẠNG VIỄN THÔNG ................................................................................................. 37

3.1. Bài toán phân lớp dữ liệu thuê bao rời mạng................................................ 37

3.1.1. Phát biểu bài toán .................................................................................. 37

3.1.2. Khái niệm thuê bao rời mạng “churn” ................................................... 38

3.1.3. Thu thập, chuẩn hóa dữ liệu .................................................................. 39

3.1.4. Lựa chọn thuộc tính............................................................................... 42

3.2. Lựa chọn phƣơng pháp, công cụ .................................................................. 45

3.2.1. Ngôn ngữ R ........................................................................................... 45

3.2.2. Phƣơng pháp phân lớp ........................................................................... 47

3.2.3. Đánh giá hiệu năng................................................................................ 48

3.3. Thực nghiệm phân lớp trên ngôn ngữ R....................................................... 50

3.3.1. Phân lớp dữ liệu sử dụng cây quyết định C4.5 ....................................... 51

3.3.2. Phân lớp dữ liệu sử dụng phƣơng pháp Naive Bayes ............................. 53

3.3.3. Phân lớp dữ liệu bằng Support Vector Machines .................................. 55

3.3. Đánh giá kết quả .......................................................................................... 56

KẾT LUẬN .................................................................................................................... 58

TÀI LIỆU THAM KHẢO ............................................................................................. 60

v

DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT

TT Thuật ngữ Định nghĩa

Khai phá dữ liệu 1. KPDL

Knowledge Discovery and Data Mining 2. KDD

Naïve Bayes 3. NB

Support vector machine 4. SVM

Neural Networks 5. NN

vi

DANH MỤC HÌNH ẢNH

Hình 1.1- Các bƣớc trong khai phá dữ liệu ..............................................................6

Hình 1.2 - Quy trình xây dựng mô hình khai phá dữ liệu ..........................................9

Hình 2.1 - Ví dụ về cây quyết định ......................................................................... 12

Hình 2.2 - Về mặt trực quan thì hàm tuyến tính siêu phẳng với lề lớn nhất trông có vẻ hợp lý ................................................................................................................ 19

Hình 2.3 - Ví dụ về bài toán phân loại trong không gian hai chiều .......................... 19

Hình 2.4 - Ba điểm trong mặt phẳng bị chia tách bởi một đƣờng thẳng có hƣớng. .. 28

Hình 2.5 - Mạng nơ-ron truyền thẳng nhiều lớp ...................................................... 34

Hình 3.1 - Mô hình quan hệ các bảng dữ liệu.......................................................... 40

Hình 3.2 - Các giai đoạn của mô hình dự đoán thuê bao rời mạng .......................... 42

Hình 3.3 - Lựa chọn thuộc tính trong phân lớp dữ liệu ............................................ 44

Hình 3.4 - Số lƣợng thuộc tính đƣợc thu thập ......................................................... 44

Hình 3.5 – Giao diện làm việc trên ngôn ngữ R ...................................................... 47

Hình 3.6 – Quy trình thực nghiệm bài toán phân lớp dữ liệu thuê bao rời mạng...... 50

Hình 3.7- mô hình phân lớp cây quyết định ........................................................... 52

Hình 3.8 - Chi tiết nút nhánh thứ 15 trong phân lớp cây quyết định ........................ 52

Hình 3.9 - Kết quả phân lớp dữ liệu bằng SVM ...................................................... 55

Hình 3.10 – Hiệu năng các thuật toán với lớp thuê bao rời mạng ............................ 57

vii

DANH MỤC BẢNG BIỂU

Bảng 1 - Ma trận nhầm lẫn ..................................................................................... 49

Bảng 2 – Kết quả mô hình phân lớp sử dụng C 4.5 ................................................. 53

Bảng 3 – Độ đo hiệu năng thuật toán Cây quyết định ............................................. 53

Bảng 4 – Kết quả mô hình phân lớp sử dụng NB .................................................... 54

Bảng 5. – Độ đo hiệu năng thuật toán NB ............................................................... 54

Bảng 6 – Kết quả mô hình phân lớp sử dụng SVM ................................................ 55

Bảng 7. – Độ đo hiệu năng thuật toán SVM ............................................................ 56

Bảng 8. – Tổng hợp đánh giá hiệu năng các phƣơng pháp phân lớp ........................ 56

1

MỞ ĐẦU

Sự bùng nổ và phát triển của ngành công nghệ thông tin đã làm lƣợng dữ

liệu đƣợc thu thập và lƣu trữ ở các hệ thống thông tin tăng lên một cách nhanh

chóng. Trƣớc tình hình đó, việc khai thác và chọn lọc những dữ liệu có ích,

tiền ẩn từ lƣợng dữ liệu khổng lồ này là rất cần thiết. Các tri thức trích lọc từ

dữ liệu sẽ giúp các cơ quan, tổ chức đƣa ra những dự báo và điều hành hiệu

quả.

Khai phá dữ liệu và khám phá tri thức (Data mining and Knowledge

discovery) là một lĩnh vực quan trọng của ngành Công nghệ thông tin với

mục tiêu là tìm kiếm các tri thức có ích, cần thiết, tiềm ẩn và chƣa đƣợc biết

trƣớc trong cơ sở dữ liệu lớn. Đây là lĩnh vực đã và đang thu hút đông đảo các

nhà khoa học trên thế giới và trong nƣớc tham gia nghiên cứu. Phân lớp

(classification) là một trong những bài toán cơ bản trong khai phá dữ liệu với

mục tiêu là phân loại các đối tƣợng vào các lớp cho trƣớc. Theo tiếp cận học

máy, phân lớp là phƣơng pháp học có giám sát với hai giai đoạn: Giai đoạn 1

là xây dựng mô hình phân lớp dựa trên tập dữ liệu huấn luyện có đầu vào và

đầu ra mong muốn (gọi là nhãn lớp); Giai đoạn 2 là sử dụng mô hình phân lớp

để phân loại các tập dữ liệu chƣa có nhãn lớp vào các lớp đã cho và có ứng

dụng trong nhiều bài toán dự báo trong thực tế. Phân lớp đƣợc sử dụng rộng

rãi trong các bài toán thực tiễn nhƣ trong y tế, ngân hàng, viễn thông, kinh tế,

tài chính...

Ngày nay, cùng với sự phát triển mạnh mẽ của thị trƣờng viễn thông là

sự ra đời của nhiều nhà cung cấp và kinh doanh dịch vụ mạng viễn thông. Thị

trƣờng viễn thông đang đi vào giai đoạn bão hòa, khách hàng có nhiều sự lựa

chọn, dẫn đến họ có thể thay đổi sử dụng dịch vụ bất cứ khi nào, kết quả là số

2

lƣợng khách hàng rời mạng tăng lên một cách nhanh chóng. Hậu quả ảnh

hƣởng không nhỏ tới kinh tế cũng nhƣ trong quản lý của doanh nghiệp kinh

doanh dịch vụ viễn thông. Vì vậy, các nhà kinh doanh dịch vụ mạng cần có

các giải pháp dữ chân khách hàng hơn là tìm kiếm khách hàng mới. Việc dự

báo khách hàng có thể rời bỏ mạng trong tƣơng lai là rất cần thiết, nhằm mục

đích hỗ trợ các nhà kinh doanh dịch vụ mạng có quyết sách kịp thời trong

công việc giữ chân khách hàng.

3

Chương 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU

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

1.1.1. Tại sao cần khai phá dữ liệu

Khoảng hơn một thập kỷ trở lại đây, lƣợng thông tin đƣợc lƣu trữ trên

các thiết bị điện tử (đĩa cứng, CD-ROM, băng từ, .v.v.) không ngừng tăng lên.

Sự tích lũy dữ liệu này xảy ra với một tốc độ bùng nổ. Ngƣời ta ƣớc đoán

rằng lƣợng thông tin trên toàn cầu tăng gấp đôi sau khoảng hai năm và theo

đó số lƣợng cũng nhƣ kích cỡ của các cơ sở dữ liệu (CSDL) cũng tăng lên

một cách nhanh chóng. Nói một cách hình ảnh là chúng ta đang “ngập” trong

dữ liệu nhƣng lại “đói” tri thức. Câu hỏi đặt ra là liệu chúng ta có thể khai

thác đƣợc gì từ những “núi” dữ liệu tƣởng chừng nhƣ “bỏ đi” ấy không? [3]

“Necessity is the mother of invention” - Data Mining ra đời nhƣ một

hƣớng giải quyết hữu hiệu cho câu hỏi vừa đặt ra ở trên. Khá nhiều định nghĩa

về Data Mining, tuy nhiên có thể tạm hiểu rằng Data Mining nhƣ là một công

nghệ tri thức giúp khai thác những thông tin hữu ích từ những kho dữ liệu

đƣợc tích trữ trong suốt quá trình hoạt động của một công ty, tổ chức nào đó.

1.1.2. Các khái niệm cơ bản

Khai phá dữ liệu (datamining) [4] đƣợc định nghĩa nhƣ là một quá trình

chắt lọc hay khai phá tri thức từ một lƣợng lớn dữ liệu. Một ví dụ hay đƣợc sử

dụng là là việc khai thác vàng từ đá và cát, Dataming đƣợc ví nhƣ công việc

"Đãi cát tìm vàng" trong một tập hợp lớn các dữ liệu cho trƣớc. Thuật ngữ

Dataming ám chỉ việc tìm kiếm một tập hợp nhỏ có giá trị từ một số lƣợng

lớn các dữ liệu thô. Có nhiều thuật ngữ hiện đƣợc dùng cũng có nghĩa tƣơng

tự với từ Datamining nhƣ Knowledge Mining (khai phá tri thức), knowledge

4

extraction (chắt lọc tri thức), data/patern analysis(phân tích dữ liệu/mẫu), data

archaeoloogy (khảo cổ dữ liệu), datadredging(nạo vét dữ liệu),...

Định nghĩa: Khai phá dữ liệu là một tập hợp các kỹ thuật được sử dụng

để tự động khai thác và tìm ra các mối quan hệ lẫn nhau của dữ liệu trong

một tập hợp dữ liệu khổng lồ và phức tạp, đồng thời cũng tìm ra các mẫu tiềm

ẩn trong tập dữ liệu đó.

Khai phá dữ liệu nhấn mạnh hai khía cạnh chính đó là khả năng trích

xuất thông tin có ích tự động (Automated) và bán tự động (Semi - Automated)

mang tính dự đoán (Predictive). Khai phá dữ liệu là một lĩnh vực liên ngành,

liên quan chặt chẽ đến các lĩnh vực sau:

Statistics (Thống kê): là một số đo cho một thuộc tính nào đó của một

tập mẫu. Mỗi giá trị thống kê đƣợc tính bằng một hàm nào đó và thông tin của

môt thống kê mang tính đại diện cho thông tin của tập mẫu mang lại.

Machine Learning (Máy học): là một phƣơng pháp để tạo ra các chƣơng

trình máy tính bằng việc phân tích các tập dữ liệu. Máy học có liên quan lớn

đến thống kê, vì cả hai lĩnh vực đều nghiên cứu việc phân tích dữ liệu, nhƣng

khác với thống kê, học máy tập trung vào sự phức tạp của các giải thuật trong

việc thực thi tính toán.

Databases technology (Công nghệ cơ sở dữ liệu): kho thông tin về một

chủ đề, đƣợc tổ chức hợp lý để dễ dàng quản lý và truy tìm.

Visualization (Sự trực quan): Biểu diễn giúp dữ liệu dễ hiểu, dễ sử dụng,

thuận tiện cho việc tạo các báo cáo, tìm ra các tri thức phục vụ việc ra quyết

định và dự đoán của nhà quản lý.

5

1.1.3. Quy trình khai phá dữ liệu

Khai phá dữ liệu là một bƣớc trong bảy bƣớc của quá trình KDD

(Knowleadge Discovery in Database) và KDD đƣợc xem nhƣ 7 quá trình khác

nhau theo thứ tự sau [1]:

1. Làm sạch dữ liệu (data cleaning & preprocessing): Loại bỏ nhiễu và

các dữ liệu không cần thiết.

2. Tích hợp dữ liệu: (data integration): quá trình hợp nhất dữ liệu thành

những kho dữ liệu (data warehouses & data marts) sau khi đã làm

sạch và tiền xử lý (data cleaning & preprocessing).

3. Trích chọn dữ liệu (data selection): trích chọn dữ liệu từ những kho

dữ liệu và sau đó chuyển đổi về dạng thích hợp cho quá trình khai

thác tri thức. Quá trình này bao gồm cả việc xử lý với dữ liệu nhiễu

(noisy data), dữ liệu không đầy đủ (incomplete data), .v.v.

4. Chuyển đổi dữ liệu: Các dữ liệu đƣợc chuyển đổi sang các dạng phù

hợp cho quá trình xử lý.

5. Khai phá dữ liệu (data mining): Là một trong các bƣớc quan trọng

nhất, trong đó sử dụng những phƣơng pháp thông minh để chắt lọc ra

những mẫu dữ liệu.

6. Ƣớc lƣợng mẫu (knowledge evaluation): Quá trình đánh giá các kết

quả tìm đƣợc thông qua các độ đo nào đó.

7. Biểu diễn tri thức (knowledge presentation): Quá trình này sử dụng

các kỹ thuật để biểu diễn và thể hiện trực quan cho ngƣời dùng.

6

Hình 1.1- Các bước trong khai phá dữ liệu [1]

1.1.4. Các bài toán cơ bản trong khai phá dữ liệu

Mô tả khái niệm (concept description): là bài toán tìm đặc trƣng và tính

chất của khái niệm. Bài toán thiên về mô tả, tổng hợp và tóm tắt khái niệm. Ví

dụ: tóm tắt văn bản.

Luật kết hợp (association rules): là dạng luật biểu diễn tri thức ở dạng

khá đơn giản. Ví dụ: “60 % nam giới vào siêu thị nếu mua bia thì có tới 80%

trong số họ sẽ mua thêm thịt bò khô”. Luật kết hợp đƣợc ứng dụng nhiều

trong lĩnh vực kính doanh, y học, tin-sinh, tài chính & thị trƣờng chứng

khoán, .v.v.

Phân lớp và dự đoán (classification & prediction): xếp một đối tƣợng vào

một trong những lớp đã biết trƣớc. Ví dụ: phân lớp vùng địa lý theo dữ liệu

thời tiết. Hƣớng tiếp cận này thƣờng sử dụng một số kỹ thuật của machine

7

learning nhƣ cây quyết định (decision tree), mạng nơ ron nhân tạo (neural

network), .v.v. Ngƣời ta còn gọi phân lớp là học có giám sát (học có thầy).

Phân cụm (clustering): xếp các đối tƣợng theo từng cụm (số lƣợng cũng

nhƣ tên) của cụm chƣa đƣợc biết trƣớc. Ngƣời ta còn gọi phân cụm là học

không giám sát (học không thầy).

Hồi quy (regression ): là bài toán điển hình trong phân tích thống kê và

dự báo. Trong khai phá dữ liệu, bài toán hồi quy đƣợc quy về việc học một

hàm ánh xạ dữ liệu nhằm xác định một giá trị thực của một biến theo biến số

khác. Phân tích hồi quy sẽ xác định đƣợc định lƣợng quan hệ giữa các biến,

và quảng bá giá trị một biến phụ thuộc vào giá trị của những biến khác.

Phƣơng pháp hồi quy khác với phân lớp dự liệu là hồi quy dùng để dự đoán

những giá trị liên lục, còn phân lớp dữ liệu là dự đoán các giá trị rời rạc.

Khai phá chuỗi (sequential/temporal patterns): tƣơng tự nhƣ khai phá

luật kết hợp nhƣng có thêm tính thứ tự và tính thời gian. Hƣớng tiếp cận này

đƣợc ứng dụng nhiều trong lĩnh vực tài chính và thị trƣờng chứng khoán vì nó

có tính dự báo cao.

Ngoài ra còn có một số bài toán khai phá dữ liệu thống kê khác.

1.1.5. Các ứng dụng của khai phá dữ liệu

Phát hiện tri thức và khai phá dữ liệu liên quan đến nhiều ngành, nhiều

lĩnh vực: thống kê, trí tuệ nhân tạo, cơ sở dữ liệu, thuật toán, tính toán song

song và tốc độ cao, thu thập tri thức cho các hệ chuyên gia, quan sát dữ liệu...

Đặc biệt phát hiện tri thức và khai phá dữ liệu rất gần gũi với lĩnh vực thống

kê, sử dụng các phƣơng pháp thống kê để mô hình dữ liệu và phát hiện các

mẫu, luật ... Ngân hàng dữ liệu (Data Warehousing) và các công cụ phân tích

8

trực tuyến (OLAP- On Line Analytical Processing) cũng liên quan rất chặt

chẽ với phát hiện tri thức và khai phá dữ liệu.

Khai phá dữ liệu có nhiều ứng dụng trong thực tế,[3] ví dụ nhƣ:

 Bảo hiểm, tài chính và thị trƣờng chứng khoán: phân tích tình hình tài

chính và dự báo giá của các loại cổ phiếu trong thị trƣờng chứng

khoán. Danh mục vốn và giá, lãi suất, dữ liệu thẻ tín dụng, phát hiện

gian lận, ...

 Thống kê, phân tích dữ liệu và hỗ trợ ra quyết định.

 Điều trị y học và chăm sóc y tế: một số thông tin về chuẩn đoán bệnh

lƣu trong các hệ thống quản lý bệnh viện. Phân tích mối liên hệ giữa

các triệu chứng bệnh, chuẩn đoán và phƣơng pháp điều trị (chế độ

dinh dƣỡng, thuốc, ...)

 Sản xuất và chế biến: Quy trình, phƣơng pháp chế biến và xử lý sự cố.

 Text mining và Web mining: Phân lớp văn bản và các trang Web, tóm

tắt văn bản,...

 Lĩnh vực khoa học: Quan sát thiên văn, dữ liệu gene, dữ liệu sinh vật

học, tìm kiếm, so sánh các hệ gene và thông tin di truyền, mối liên hệ

gene và một số bệnh di truyền, ...

 Mạng viễn thông: Phân tích các cuộc gọi điện thoại và hệ thống giám

sát lỗi, sự cố, chất lƣợng dịch vụ, dự báo thuê bao rời mạng ...

1.1.6. Quy trình xây dựng mô hình khai phá dữ liệu

Việc thực hiện một DMM với đầy đủ 4 bƣớc công việc chính của quá

trình khai phá dữ liệu là:

9

Bƣớc 1: Chuẩn bị dữ liệu (Data Preparation); Trong bƣớc này chúng ta

thực hiện các công việc tiền xử lý dữ liệu theo yêu cầu của mô hình nhƣ trích

chọn thuộc tính, rời rạc hóa dữ liệu và cuối cùng là chia dữ liệu nguồn (Data

Source) thành 2 tập dữ liệu dùng để huấn luyện mô hình (Training Data) và

kiểm tra mô hình (Testing data).

Bƣớc 2: Xây dựng mô hình (Data Modeling); ta sử dụng Training Data

vừa tạo ra để xây dựng mô hình.

Bƣớc 3: Đánh giá mô hình (Validation); Sau khi sử dụng Training Data

để xây dựng mô hình, bây giờ ta sử dụng Testing Data để kiểm tra xem mô

hình có đủ tốt để sử dụng hay không? ( Nếu chƣa đủ tốt thì phải sử dụng

Training Data khác để huấn luyện lại). Có 3 kỹ thuật chính để kiểm tra mô

hình đó là sử dụng Accuracy Chart ( Lift Chart), Classification Matrix và

ProfitChart.

Bƣớc 4: Sử dụng mô hình để dự đoán dự liệu trong tƣơng lai (Model

Usage); Sau khi mô hình đƣợc kiểm tra (Testing) nếu độ chính xác đáp ứng

yêu cầu thì có thể sử dụng model đã xây dựng vào dự đoán các dữ liệu chƣa

biết.

Hình 1.2 - Quy trình xây dựng mô hình khai phá dữ liệu

10

1.2.Bài toán phân lớp và dự báo

1.2.1. Giới thiệu bài toán

Phân lớp: là quá trình xây dựng một mô hình để mô tả dữ liệu đƣợc

phân chia nhƣ thế nào, nói cách khác, phân lớp là quá trình xây dựng một mô

hình bằng các gán các đối tƣợng dữ liệu (thuộc tính) vào các lớp đã xác định.

Tiến trình phân lớp dựa trên 4 thành phần cơ bản:

- Lớp (class)

- Dự đoán (predictors)

- Tập dữ liệu được đào tạo (Training dataset)

- Tập dữ liệu kiểm thử (Testing dataset)

Đặc trƣng của tiến trình phân lớp gồm những điểm sau:

Input: tập dữ liệu đào tạo chứa những đối tƣợng với thuộc tính của

nó,với một số thuộc tính đã đƣợc gán nhãn;

Output: mô hình (classifier) đƣợc gán bởi những nhãn cụ thể cho mỗi đối

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;

Dự báo: là một quá trình gồm hai bƣớc, nó gần giống với quá trình phân

lớp. Tuy nhiên để dự báo, chúng ta bỏ qua khái niệm nhãn phân lớp bởi vì các

giá trị đƣợc dự báo là liên tục (đƣợc sắp xếp) hơn là các giá trị phân loại. Ví

dụ thay vì phân loại xem một khoản vay có là an toàn hay rủi do thì chúng ta

sẽ dự đoán xem tổng số tiền cho vay của một khoản vay là bao nhiêu thì

khoản vay đó là an toàn.

Có thể xem xét việc dự báo cũng là một hàm y = f(X), trong đó X là dữ

liệu đầu vào, và đầu ra là một giá trị y liên tục hoặc sắp xếp đƣợc. Việc dự

báo và phân lớp có một vài điểm khác nhau khi sử dụng các phƣơng pháp xây

11

dựng mô hình. Giống với phân lớp, tập dữ liệu huấn luyện sử dụng để xây

dựng mô hình dự báo không đƣợc dùng để đánh giá tính chính xác. Tính

chính xác của mô hình dự báo đƣợc đánh giá dựa trên việc tính độ lệch giá

các giá trị dự báo với các giá trị thực sự nhận đƣợc của mỗi bộ kiểm tra X.

1.2.2 Các bƣớc giải quyết bài toán

Các bƣớc giải quyết bài toán gồm:

Bƣớc 1:Xây dựng mô hình từ tập huấn luyện.

- Mỗi bộ/mẫu dữ liệu đƣợc phân vào một lớp đƣợc xác định trƣớc.

- Lớp của một bộ/mẫu dữ liệu đƣợc xác định bởi thuộc tính gán nhãn

lớp.

- Tập các bộ/mẫu dữ liệu huấn luyện - tập huấn luyện - đƣợc dùng để

xây dựng mô hình.

- Mô hình đƣợc biểu diễn bởi các luật phân lớp, các cây quyết định hoặc

các công thức toán học.

Bƣớc 2: Sử dụng mô hình - kiểm tra tính đúng đắn của mô hình và dùng

nó để phân lớp dữ liệu mới

- Phân lớp cho những đối tƣợng mới hoặc chƣa đƣợc phân lớp.

- Đánh giá độ chính xác của mô hình:

+ Lớp biết trƣớc của một mẫu/bộ dữ liệu đem kiểm tra đƣợc so sánh

với kết quả thu đƣợc từ mô hình

+ Tỉ lệ chính xác = phần trăm các mẫu/bộ dữ liệu đƣợc phân lớp

đúng bởi mô hình trong số các lần kiểm tra

12

Chƣơng 2: CÁC PHƢƠNG PHÁP PHÂN LỚP TRONG KHAI PHÁ

DỮ LIỆU

2.1. Phân lớp bằng phƣơng pháp quy nạp cây quyết định

Cây quyết định là biểu đồ có cấu trúc dạng cây đƣợc giới thiệu lần đầu

tiên bởi Hunt và các cộng sự (Hunt, Marin, & Stone, 1966).

Hình 2.1 - Ví dụ về cây quyết định

Trong đó gồm:

- Node gốc của cây: node trên cùng của cây, là một thuộc tính điều kiện.

Các nhánh từ node gốc tƣơng ứng với các giá trị có thể của thuộc tính này.

- Node trong: Mỗi node trong của cây cũng tƣơng ứng với một thuộc tính

điều kiện. Một node trong của cây có thể coi nhƣ là node gốc của một cây

con.Mỗi node trong chỉ bao hàm những đối tƣợng dữ liệu thuộc một nhánh cụ

thể của node cha.

13

- Node lá: node cuối trong nhánh mà tất cả các đối tƣợng đều thuộc một

lớp hoặc không còn thuộc tính điều kiện nào để phân chia hoặc không còn đối

tƣợng dữ liệu nào để phân chia.

Điều quan trọng của thuật toán cây quyết định là tiêu chí đánh giá để tìm

điểm chia. Ý tƣởng chính trong việc đƣa ra các tiêu chí này là làm sao cho các

tập con đƣợc phân chia càng trở nên “trong suốt” (tất cả các bộ thuộc về cùng

một nhãn) càng tốt. Quinlan đã phát triển thuật toán ID3 dùng độ đo thông tin

thu thêm (Information Gain - Gain) để xác định điểm chia tốt nhất. Độ đo này

dựa trên cơ sở lý thuyết thông tin của Claude Shannon (1948) để đo tính

thuần nhất (hay ngƣợc lại là pha trộn) của một tập hợp. Độ đo này đƣợc xác

nhƣ sau:

m i=1

Entropy (S) = Pi log2Pi (1.1)

Trong đó m là số lƣợng các lớp khác nhau và Pi là tỉ lệ các đối tƣợng

mang nhãn i.

Để xác định điểm chia, ID3 so sánh entropy của một node cha với tổng tỉ

lệ entropy của các node con sau khi phân chia, Gain(S, A) của thuộc tính A,

trên tập S, đƣợc định nghĩa nhƣ sau:

𝑉∈𝑉𝑎𝑙𝑢𝑒

|𝑆𝑉 | |𝑉|

Gain 𝑆, 𝐴 = 𝐸𝑚𝑡𝑟𝑜𝑝𝑦 𝑆 − 𝐸𝑛𝑡𝑟𝑜𝑝𝑦 𝑆𝑉 (1.2)

Với giá trị Value (A) là tập các giá trị có thể cho thuộc tính A, và S|; là

tập con của S mà A nhận giá trị v.

C4.5 là kế thừa của thuật toán học máy bằng cây quyết định dựa trên nền

tảng là kết quả nghiên cứu của Hunt và các cộng sự của ông. Phiên bản đầu

tiên ra đời là ID3 (Quinlan, 1979)- một hệ thống đơn giản ban đầu chứa

khoảng 600 dòng lệnh Pascal, và tiếp theo là C4 (Quinlan 1987). Năm 1993,

14

J. Ross Quinlan đã kế thừa các kết quả đó phát triển thành C4.5 với 9000

dòng lệnh C. Mặc dù đã có phiên bản phát triển từ C4.5 là C5.0 - một hệ

thống tạo ra lợi nhuận từ Rule Quest Research, nhƣng nhiều tranh luận,

nghiên cứu vẫn tập trung vào C4.5 vì mã nguồn của nó là sẵn dùng.

Một số cải tiến của thuật toán C4.5 so với ID3:

- Sử dụng Gain Ratio (thay vì Information Gain) để chọn thuộc tính phân

chia trong quá trình xây dựng cây.

- Có thể xử lý tốt cả 2 loại dữ liệu rời rạc và liên tục

- Có thể xử lý dữ liệu không đầy đủ ( thiếu một số giá trị tại một số thuộc

tính)

- Thực hiện cắt tỉa cây sau khi xây dựng: loại bỏ những nhánh cây không

thực sự ý nghĩa.

Thuật toán C4.5, một cải tiến của ID3, mở rộng cách tính Information

Gain thành Gain Ratio để chọn thuộc tính phân chia trong quá trình xây dựng

cây.

Gain Ratio đƣợc xác định bởi công thức sau:

GainRatio = (1.3) Gain(S, A) SplitInformation(S, A)

Trong đó: SplitInformation(S, A) chính là thông tin do phân tách của A

m

trên cơ sở giá trị của thuộc tính phân loại S. Công thức tính nhƣ sau:

i=1

SplitInformation S, A = − (1.4) log2 |Si| |S| |Si| |S|

15

2.2. Phân lớp bằng phƣơng pháp Bayesian

Thuật toán phân lớp Naïve Bayes (NB) là một trong những thuật toán

phân lớp điển hình nhất trong học máy và khai thác dữ liệu. Naïve Bayes là

phƣơng pháp phân lớp dựa vào xác suất đƣợc sử dụng rộng rãi trong lĩnh vực

học máy, đƣợc sử dụng lần đầu tiên trong lĩnh vực phân loại bởi Maron vào

năm 1961 [Maron, 1961] sau đó trở nên phổ biến dùng trong nhiều lĩnh vực

nhƣ trong các công cụ tìm kiếm [Rijsbergen et al, 1970], các bộ lọc email

[Sahami et al, 1998],..

𝑃 𝑋 𝑌 𝑃(𝑌)

Thuật toán Naïve Bayes dựa trên định lý Bayes đƣợc phát biểu nhƣ sau:

𝑃 𝑋𝑌 𝑃 𝑋

𝑃(𝑋)

(2.1) 𝑃 𝑋 Y = =

Áp dụng trong bài toán phân lớp, các dữ kiện gồm có:

-D: tập dữ liệu huấn luyện đã đƣợc vector hóa dƣới dạng:

𝑋 = (𝑋1, 𝑋2,….𝑋𝑛 )

- Ci: phân lớp i, với i = {1,2,...,m}.

- Các thuộc tính độc lập điều kiện đôi một với nhau.

Theo định lý Bayes:

𝑃 𝑋 𝐶𝑖 𝑃(𝐶𝑖) 𝑃 𝑋

(2.2) 𝑃 𝐶𝑖 X =

n 𝑃 𝑋 Cj = P 𝑋𝑘 𝐶𝑗 k=1

Theo tính chất độc lập điều kiện:

Trong đó:

- P(Ci|X) là xác suất thuộc phân lớp i khi biết trƣớc mẫu X.

16

- P(Ci) xác suất là phân lớp i.

- P(xk|Ci) xác suất thuộc tính thứ k mang giá trị xk khi biết X thuộc

phân lớp i.

Các bƣớc thực hiện thuật toán Naive Bayes:

Bước 1: Huấn luyện Naive Bayes (dựa vào tập dữ liệu), tính P(Ci ) và

P(Xk|Ci)

Bước 2: Phân lớp Xnew= (x1,x2,...,xn), tính xác suất từng lớp khi đã

biết trƣớc đƣợc gán vào lớp có xác suất lớn nhất theo công thức

𝑛 𝑘=1

(2.3) 𝑚𝑎𝑥𝐶𝑖 ∈ 𝐶 𝑃 𝐶𝑖 𝑃 𝑋𝑘 Ci

2.3. Support Vector Machine (SVM)

2.3.1 Phân tách tuyến tính với lề cực đại

Chúng ta hãy bắt đầu SVM bằng một bài toán khá đơn gián: xây dựng

một hàm tuyến tính để phân tách một tập dữ liệu phân loại hai lớp rời nhau.

Dữ liệu phân loại hai lớp là một tập các đối tƣợng S gồm l phần tử, trong đó

mỗi phần tử đƣợc mô tả bởiVec-tơ d chiều và một giá trị nhãn + 1 hoặc -1:

𝑆 = 𝑥𝑖, 𝑦𝑖 , 𝑥𝑖 ∈ 𝑅𝑑 , 𝑦𝑖 ∈ −1,1 , 𝑖 = 1 … 𝑙 .

Khái niệm hai lớp rời nhau có nghĩa là tồn tại một siêu phẳng có phƣơng

trình [2]

(3.1) 𝑓 𝑥 = 𝑤. 𝑥 + 𝑏

Trong không gian Rd nằm giữa hay chia đôi tập dữ liệu S thành hai

phần, mỗi phần gồm toàn các đối tƣợng chung một nhãn +1 hay −1.

Các siêu phẳng này là các đƣờng thẳng trong không gian hai chiều, mặt phẳng

trong không gian ba chiều, và tổng quát hơn là các không gian con

17

𝑅𝑑−1 chiều trong không gian 𝑅𝑑 . Khi tập dữ liệu đƣợc dùng để xây dựng

nên các siêu phẳng thì S thƣờng đƣợc gọi là tập huấn luyện và các phần tử

trong đó đƣợc gọi là dữ liệu (hay véc-tơ huấn luyện ).

Có nhiều phƣơng pháp khác nhau có thể tìm ra lời giải của bài toán trên,

ví dụ nhƣ thuật toán Perceptron của Rosenblatt hay mạng nơ-ron nhân tao,

phƣơng pháp phân tách tuyến tính của Fisher và cả SVMs. Chúng ta sẽ cùng

tìm hiểu sự khác biệt của SVMs đối với các phƣơng pháp khác thông qua khái

niệm hàm phân tách tuyến tính với lề cực đại. Trƣóc tiên chúng ta sẽ xem xét

hai khái niệm khá quan trọng là lề hàm (functional margin) và lề hình học

(geometric margin) của một điểm tới một siêu phẳng nhƣ sau:

Định nghĩa 3.1. Lề hàm của một véc-tơ huấn luyện (xi, yi) đối với siêu

phẳng f (x) = 0 là đại lƣợng [2].

𝑝 𝑓 𝑥𝑖, 𝑦𝑖 = 𝑦𝑖 𝑤. 𝑥𝑖 + 𝑏 ( 3.2)

Đối với bài toán phân loại 2 –lớp 𝑝 𝑓 𝑥𝑖, 𝑦𝑖 > 0 đồng nghĩa với việc

phân loại đúng. Với 𝑦𝑖 = 1, giá trị của lề hàm 𝑤. 𝑥 + 𝑏 có giá trị dƣơng và

một giá trị càng lớn càng cho thấy mức độ chắc chắn của việc phân loại 𝑥𝑖

vào lớp + 1. Ngƣợc lại, nếu 𝑦𝑖 = 1 thì chúng ta muốn 𝑤. 𝑥 + 𝑏 có giá trị âm

với độ lớn tỷ lệ với độ rõ ràng của véc-tơ 𝑥𝑖 thuộc về lớp -1. Trong cả hai

trƣờng hợp, nếu giá trị 𝑦𝑖 (𝑤. 𝑥 + 𝑏 )> 0, hay lề dƣơng, thì sự chia tách của hàm 𝑓 đối với véc-tơ huấn luyện 𝑥𝑖, 𝑦𝑖 là đúng đắn.

Việc phân loại dựa vào giá trị của lề hàm 𝑝 𝑓 tuy thuận lợi nhƣ đã nêu

nhƣng có một nhƣợc điểm là có vô số hàm 𝑓 cho cùng một giá trị phân loại

đúng/sai. Chẳng hạn nhƣ chúng ta thay 𝑤 ′ bởi 2𝑤 và 𝑏′ bởi 2𝑏, thì hàm quyết

định không thay đổi vì sign 2𝑤. 𝑥 + 2𝑏 = 𝑠𝑖𝑔𝑛 𝑤. 𝑥 + 𝑏 . Nói một cách

18

khác, nhiều hệ số khác nhau của 𝑤 và b có thể cho cùng một kết quả phân

loại.

Để đơn giản hóa vấn đề mà không làm mất đi tính tổng quát, chúng ta có

thể chọn một giá trị đặc biết của w, chẳng hạn nhƣ 𝑤 = 1 và thay thế bộ

𝑤 𝑤

𝑏 |𝑤|

(𝑤, 𝑏) bởi ( ). Trong trƣờng hợp này, lề hàm trở thành lề hình học và ,

giá trị tuyệt đối chính là khoảng cách Ơ-clid từ một véc-tơ (điểm) đến siêu

phẳng phân cách 𝑓.

Định nghĩa 3.2. Lề hình học của một véc-tơ huấn luyện 𝑥𝑖, 𝑦𝑖 đối với

siêu phẳng 𝑓 𝑥 = 0 là đại lƣợng [2].

𝑤 𝑤

𝑏 𝑤

(3.3) 𝑝𝑓 𝑥𝑖, 𝑦𝑖 = 𝑦𝑖 . 𝑥𝑖 +

𝑝 𝑓 𝑥𝑖,𝑦𝑖 𝑤

=

Định nghĩa 3.3. Lề của một tập huấn luyện 𝑠 = {(𝑥𝑖, 𝑦𝑖 )}𝑖=1…𝑙 đối với

siêu phẳng 𝑓 𝑥 = 0 là giá trị bé nhất của lề hình học tại véc-tơ [2].

(3.4) 𝑝𝑓 = min𝑖=1…𝑙 𝑝𝑓 (𝑥𝑖, 𝑦𝑖)

Siêu phẳng mà SVM tìm kiếm là siêu phẳng có giá trị lề lớn nhất, hay

còn gọi là siêu phẳng với lề cực đại.

(3.5) 𝑓∗ = arg max𝑓 𝑝𝑓

19

Hình 2.2 - Về mặt trực quan thì hàm tuyến tính siêu phẳng với lề lớn nhất trông có vẻ hợp lý

Hình 2.3 - Ví dụ về bài toán phân loại trong không gian hai chiều

Dùng một đƣờng thẳng để phân tách các điểm „o‟ và điểm „+‟. Giả sử

rằng đƣờng thẳng có lề là p và tọa độ của các điểm „o‟ và điểm „+‟ bị dịch

20

chuyển qua bán kính r do có nhiễu. Nếu 𝑟 < 𝑝 thì đƣờng thẳng trên vẫn có

thể phân tách chính xác các điểm này

Định lý 4.1. Cho một lớp các hàm phân loại 𝑓 𝑥 = 𝑠𝑖𝑔𝑛 𝑤. 𝑥 (coi b=0

cho đơn giản) với 𝑤 ≤ 𝐴 và giả sử tất cả các véc-tơ đều nằm trong một

hình cầu 𝑥 ≤ 𝑅, với R,A> 0. Với p > 0, và v là tỷ lệ các véc-tơ huấn luyện

𝑝 𝑤

có lề nhỏ hơn gọi là lỗi lề. [2].

Với mọi phân bố P của véc-tơ X, vơi mọi p>0 và δ ∈ (0, 1), với xác suất

ít nhất là 1- δ trên toàn bộ l véc-tơ huấn luyện, khả năng phân loại lỗi đối với

bất kỳ véc-tơ X nào đều nhỏ hơn (bị chặn trên) bởi

(3.6)

Trong đó c là một hằng số.

Định lý trên nói rằng khả năng phân loại lỗi của 𝑓 đối với một véc-tơ bất

kỳ bị chặn trên bởi tổng của lỗi lề v (lỗi huấn luyện) và giá trị trong dấu √...

của công thức gọi là năng lực của 𝑓. Chúng ta có thể thấy rằng nếu l có

giá trị lớn vô cùng, hay với vô hạn dữ liệu huấn luyện thì giá trị trong dấu √...

tiến tới 0 và lỗi huấn luyện gần trở thành lỗi của hàm phân loại trên

toàn bộ P. Với một lƣợng dữ liệu huấn luyện hạn chế, năng lực của 𝑓

tỷ lệ nghịch với R và A, tỷ lệ thuận với lề p. Nếu chúng ta có thể giữ R và A có

các giá trị không đổi (ví dụ nhƣ chuẩn hóa dữ liệu trong một siêu cầu có bán

kính 1, 𝑥 ≤ 1, và chỉ xét các giá trị 𝑥 = 1), thì thành phần có giá trị ảnh

hƣởng lới tới cận trên của lỗi chính là p. Một giá trị lớn hơn của p mang lại

một hàm 𝑓 với năng lực nhỏ hơn và một lỗi lề lớn hơn (theo định nghĩa thì v

tỷ lệ thuận với p). Ngƣợc lại, với p nhỏ hơn thì lỗi lề sẽ giảm nhƣng thành

21

phần thứ 2 trong công thức 3.6 thƣờng đƣợc gọi là mức điều chỉnh/ phạt năng

lực sẽ tăng. Nhƣ vậy, để giảm thiểu khả năng phán đoán lỗi chúng ta cần tìm

một siêu phẳng 𝑓 với ít lỗi thực hiện (v nhỏ) và giá trị lề p lớn (đây cũng

thƣờng là tiêu chí chung của nhiều phƣơng pháp học máy khác nhau: ƣu tiên

các mô hình đơn giản với ít lỗi thực nghiệm).

Với giả thuyết dữ liệu có thể chia tách đƣợc nêu trên (lỗi thực nghiệm

bằng 0), siêu phẳng với lề cực đại dƣờng nhƣ là một trong những hàm phân

tách tuyến tính tốt nhất do có chặn trên của lỗi là bé nhất.

Một lý do khác mà siêu phẳng với hàm cực đại hay SVM đƣợc dùng thử

là đã có rất nhiều bài học thành công trên thực tế nhƣ: phân loại văn bản, nhận

dạng ảnh, nhận dạng chữ viết.

2.3.1.1. Tìm kiếm siêu phẳng với lề cực đại

Đối với dữ liệu khả tách tuyến tính, thuật toán SVM đơn giản chỉ là tìm

siêu phẳng 𝑓 𝑥 = 𝑤. 𝑥 + 𝑏 có giá trị lề càng lớn càng tốt. Để làm đƣợc điều

này, chúng ta có thể giả thiết rằng các giá trị lề tại các điểm huấn luyện

𝑝 𝑓 𝑥𝑖, 𝑦𝑖 ≥ 1 mà không làm mất đi tính tổng quát. Điều này tƣơng đƣơng với:

𝑤. 𝑥𝑖 + 𝑏 ≥ 1 𝑘𝑕𝑖 𝑦𝑖 = +1,

𝑤. 𝑥𝑖 + 𝑏 ≤ 1 𝑘𝑕𝑖 𝑦𝑖 = −1,

hay

𝑦𝑖 𝑤. 𝑥𝑖 + 𝑏 − 1 ≥ 0, 𝑖 = 1, … 𝑙. (3.7)

Nếu gọi siêu phẳng 𝐻+: 𝑤. 𝑥 + 𝑏 = +1, và 𝐻−: 𝑤. 𝑥 + 𝑏 = −1, thì lề

(𝑏−1) 𝑤

(𝑏 +1) , 𝑤

hình học của gốc tọa độ đối với hai siêu phẳng này lần lƣợt là và

22

2 𝑤

. Nhƣ vậy, việc tìm hay khoảng cách giữa hai siêu phẳng 𝐻+ và 𝐻− là

siêu phẳng với lề cực đại tƣơng đƣơng với việc tìm siêu phẳng 𝑓 có giá trị

𝑤 2 nhỏ nhất thỏa mãn điều kiện (3.7):

𝑤 2 (3.8) min 𝑤 ,𝑏 1 2

Thỏa mãn 𝑦𝑖 𝑤. 𝑥𝑖 + 𝑏 ≥ 1, 𝑖 = 1, … 𝑙. (3.9)

2.3.1.2. Hàm phân loại tuyến tính với lề mềm cực đại

Điều kiện 3.7 dƣờng nhƣ quá cứng nhắc vì trong nhiều ứng dụng thực tế

thì khả năng có nhiễu hay phần tử ngoại lai là rất cao. Cho dù bản chất của bài

toán là đơn giản và có thể phân loại tuyến tính một cách hiệu quả, nhƣng chỉ

với một phần tử nhiễu hay bị dữ liệu gán nhãn sai cũng có thể làm cho bài

toán tối ƣu 3.8 trở nên vô nghiệm vì không thể tìm ra đƣợc hàm phân tách

tuyến tính với lỗi thực nghiệm bằng 0. Trong khi đó khả năng kháng nhiễu là

một trong những tính chất bắt buộc đối với bất kỳ phƣơng pháp học máy hiệu

quả nào.

Để giải quyết vấn đề dữ liệu có nhiễu, SVM chọn giải pháp thay thế ràng

buộc 3.7 bởi một ràng buộc khác mềm mại hơn:

𝑦𝑖 𝑤. 𝑥𝑖 + 𝑏 ≥ 1 − ξi, 𝑖 = 1, … , 𝑙. (3.10)

ξi ≥ 0, 𝑖 = 1, … , 𝑙. (3.11)

Các biến số ξi trong (3.10) thƣờng đƣợc gọi là biến nới lỏng. Chúng cho

phép các véc-tơ huấn luyện có thể có lề hàm nhỏ hơn 1 (hay vi phạm điều

kiện cứng), tuy nhiên những véc-tơ này cần chịu một khoản phạt đƣợc tính

trong hàm mục tiêu tỷ lệ với mức độ vi phạm và một số C :

23

1

𝑙 𝑖=1

2

(3.12) min𝑤 ,𝑏 𝑤 2 + 𝐶 ξi

Tham số C có vai trò cân bằng lỗi thực nghiệm, mức độ vi phạm điều kiện

lề “cứng” và cả độ lớn của lề. Khi C = 0 thì có nghĩa là không cho phép vi

phạm điều kiện lề và yêu cầu tìm hàm f với điều kiện (3.7).

Tóm tắt lại thì bài toán tìm kiếm siêu phẳng phân cách với lề mềm cực

𝑙

đại đƣợc viết nhƣ sau:

𝑖=1

3.13 𝑤2 + 𝐶 ξi min 𝑤,𝑏,ξ 1 2

𝑡𝑕ỏ𝑎 𝑚ã𝑛 𝑦𝑖 𝑤. 𝑥𝑖 + 𝑏 > 1 − ξi, 𝑖 = 1, … , 𝑙. (3.14)

ξ𝑖 ≥ 0, 𝑖 = 1, … , 𝑙. (3.15)

2.3.1.3. Lý thuyết tối ƣu Lagrangian

Phƣơng pháp nhân tử La-grăng (Lagrange multiplier) [2] thƣờng đƣợc sử

dụng để giải các bài toán tối ƣu nhƣ trên. Tuy nhiên, với ràng buộc là các bất

đẳng thức thì bài toán gốc này cần đƣợc chuyển thành một dạng bài toán đối

ngẫu dễ giải hơn.

Định nghĩa 3.4. Với bài toán tối ƣu trên miền xác định lồi Ω ⊆ 𝑅𝑑

𝑓 𝜔 , 𝜔 ∈ Ω (3.16) min 𝜔

đ𝑖ề𝑢 𝑘𝑖ệ𝑛 𝑔𝑖 𝜔 ≤ 0, 𝑖 = 1, . … , 𝑘 (3.17)

𝑕𝑖 𝜔 = 0, 𝑖 = 1, . … , 𝑚 (3.18)

𝑘

𝑚

Hàm số La-grăng tổng quát là hàm số

𝑖=1

𝑖=1

𝐿 𝜔, 𝛼, 𝛽 = 𝑓 𝑥 + 𝛼𝑖𝛽𝑖 𝜔 + 𝛽𝑖𝑕𝑖 𝜔 (3.19)

24

Định nghĩa 3.5. Bài toán đối ngẫu của bài toán Lagrangian gốc là bài

toán [2]

max𝛼 ,𝛽 𝜃(𝛼, 𝛽) (3.20)

thỏa mãn 𝛼 ≥ 0 (3.21)

với

𝜃 𝛼, 𝛽 = 𝑖𝑛𝑓𝜔 ∈Ω 𝐿 𝜔, 𝛼, 𝛽 (3.22)

Mối quan hệ giữa hai bài toán gốc và bài toán đối ngẫu là giá trị tối ƣu

của bài toán đối ngẫu bị chặn trên bởi các giá trị của bài toán gốc:

sup 𝜃 𝛼, 𝛽 : 𝛼 ≥ 0 ≤ inf 𝑓 𝜔 : 𝑔 𝜔 ≤ 0, 𝑕 𝜔 = 0 (3.23)

Hơn thế nữa, nếu 𝜔∗ và (𝛼∗𝛽∗) là các giá trị nằm trong miền xác định

của hai bài toán và 𝑓 𝜔∗ = 𝜃 𝛼, 𝛽 , thì 𝜔∗và (𝛼∗, 𝛽∗) tƣơng ứng là hai

nghiệm của hai bài toán gốc và bài toán tối ƣu. Đồng thời định lý The Kuhn-

Tucker dƣới đây cho biết rằng nếu hàm mục tiêu 𝑓 là hàm lồi và 𝑔𝑖,𝑕𝑖 là các hàm affine, thì sự tồn tại của nghiệm tối ƣu (𝛼∗, 𝛽∗) là điều kiện cần và đủ

cho sự tồn tại của 𝜔∗.

Định lý 3.2. (Kuhn-Tucker) [2] Cho bài toán tối ưu trên miền xác định lồi

Ω ⊆ 𝑅𝑑

𝑓 𝜔 , 𝜔 ∈ Ω (3.14) min 𝜔

đ𝑖ề𝑢 𝑘𝑖ệ𝑛 𝑔𝑖 𝜔 ≤ 0, 𝑖 = 1, . … , 𝑘 (3.25)

𝑕𝑖 𝜔 = 0, 𝑖 = 1, . … , 𝑚 (3.26)

Với hàm lồi 𝑓 ∈ 𝐶1 (khả vi) và 𝑔𝑖,𝑕𝑖 là các hàm affine, điều kiện cần và

đủ để véc-tơ 𝜔∗là điểm tối ưu là tồn tại các giá trị của 𝛼∗ 𝑣à 𝛽∗ sao cho:

25

= 0 (3.27) 𝜕𝐿(𝜔∗, 𝛼∗, 𝛽∗) 𝜕𝜔

∗𝑔𝑖 𝜔∗ = 0, 𝑖 = 1, … , 𝑘 (3.29)

= 0 (3.28) 𝜕𝐿(𝜔∗, 𝛼∗, 𝛽∗) 𝜕𝛽

𝛼𝑖

𝑔𝑖 𝜔∗ ≤ 0, 𝑖 = 1, … , 𝑘 (3.30)

𝛼𝑖 ≥ 0, 𝑖 = 1, … , 𝑘 (3.31)

2.3.1.4. Tìm kiếm siêu phẳng với lề cực đại

Trở lại với bài toán tối ƣu tìm siêu phẳng với lề cực đại ở mục 2.3.1.1

𝑙

𝑙

𝑙

𝐿 𝜔, 𝑏, ξ, 𝛼, 𝛽 =

𝜔2 + 𝐶 ξ𝑖 − 𝛼𝑖(

𝑦𝑖 𝜔. 𝑥𝑖 + 𝑏 − 1 + ξ𝑖 − 𝛽𝑖ξ𝑖

1 2

𝑖=1

𝑖=1

𝑖=1

hàm Lagrangian tổng quát của bài toán XXX là hàm

(3.32)

Đặt đạo hàm của hàm số Lagrangian bằng không đối với các

biến số 𝜔, ξ𝑖 𝑣à 𝑏 chúng ta có các mối quan hệ sau:

𝑙 = 𝜔 − 𝑦𝑖𝛼𝑖𝑥𝑖 𝑖=1

= 0 (3.33) 𝜕𝐿(𝜔, 𝛼, 𝛽) 𝜕𝜔

= 𝐶 − 𝛼𝑖 − 𝛽𝑖 = 0 (3.34) 𝜕𝐿(𝜔, 𝛼, 𝛽) 𝜕ξ𝑖

𝑙 = 𝑦𝑖𝛼𝑖 𝑖=1

= 0 (3.35) 𝜕𝐿(𝜔, 𝛼, 𝛽) 𝜕𝑏

26

Thay thế các mối quan hệ trên vào hàm lagrangian, chúng ta có hàm mục

tiêu của bài toán đối ngẫu

𝑙 𝑦𝑖𝑦𝑗 𝛼𝑖𝛼𝑗 𝑥𝑖. 𝑥𝑗 𝑖,𝑗 =1

𝑙 + 𝐶 ξ𝑖 + 𝑖=1

𝑙 𝑦𝑖𝑦𝑗 𝛼𝑖𝛼𝑗 𝑥𝑖. 𝑥𝑗 𝑖,𝑗 =1

𝑙 − 𝑏 𝛼𝑖𝑦𝑖 𝑖=1

𝑙

𝑙

𝐿 𝛼, 𝛽 = 1 2

𝑖=1

𝑖=1

𝑙 − 𝛽𝑖ξ𝑖 𝑖=1

𝑙

𝑙

− 𝛼𝑖ξ𝑖 + 𝛼𝑖

𝑙 𝑦𝑖𝑦𝑗 𝛼𝑖𝛼𝑗 𝑥𝑖. 𝑥𝑗 + ξ𝑖 𝐶 − 𝛼𝑖 − 𝛽𝑖 + 𝛼𝑖 𝑖,𝑗 =1

𝑖=1

𝑖=1

𝑙

= − 1 2

𝑖=1

𝑙 𝑦𝑖𝑦𝑗 𝛼𝑖𝛼𝑗 𝑥𝑖. 𝑥𝑗 𝑖,𝑗 =1

(3.36) = 𝛼𝑖 − 1 2

Hai điều kiện 𝐶 − 𝛼𝑖 − 𝛽𝑖 = 0 và 𝛽𝑖 ≥ 0 làm cho 𝛼𝑖 ≤ 𝐶. Cuối cùng ta

𝑙

đƣợc bài toán tối ƣu đối ngẫu với điều kiện dễ có thể giải đƣợc hơn

𝑙 𝑦𝑖𝑦𝑗 𝛼𝑖𝛼𝑗 𝑥𝑖. 𝑥𝑗 𝑖,𝑗 =1

𝑖=1

𝑙

𝐿 𝛼 = − 𝛼𝑖 (3.37) min 𝛼 1 2

𝑖=1

𝑡𝑕ỏ𝑎 𝑚ã𝑛 𝑦𝑖 𝛼𝑖 = 0 (3.38)

0 ≤ 𝛼𝑖 ≤ 𝐶, 𝑖 = 1, … , 𝑙 (3.39)

Điều kiện thứ nhất trong định lý Kuhn-Tucker có liên quan tới một định

lý trong học máy thống kê gọi là định lý về sự biểu diễn.Chúng ta thấy rằng

một nghiệm tối ƣu 𝛼∗ của bài toán gốc có thể đƣợc biểu diễn thông qua một tổ

hợp tuyến tính của các véc-tơ huấn luyện 𝑥𝑖 với hệ số 𝛼𝑖 là nghiệm của bài toán

đối ngẫu.

27

Điều kiện thứ ba trong định lý Kuhn-Tuker, hay còn gọi là điều kiện

Karush-Kuhn-Tuker là [2]

ξ𝑖(𝛼𝑖 − 𝐶) = 0, 𝑖 = 1, … , 𝑙 (3.41)

𝛼𝑖(𝑦𝑖 𝜔. 𝑥𝑖 + 𝑏 − 1 + ξ𝑖) = 0, 𝑖 = 1, … , 𝑙 (3.40)

Các điều kiện này nói lên rằng ξ𝑖 ≠ 0 chỉ sảy ra khi 𝛼𝑖 = 𝐶, và những

véc-tơ thỏa 0 < 𝛼𝑖 < 𝐶 sẽ có lề hàm bằng 1 (do ξ𝑖 = 0). Nói cách khác, chỉ

những rằng buộc thực sự mới có giá trị 𝛼𝑖 ≠ 0 và lời giải tối ƣu của bài toán

∗ < 𝐶.

gốc chỉ phụ thuộc vào những véc-tơ này. Trong SVM, khái niệm véc-tơ hỗ trợ

là nói đến véc-tơ huấn luyện có các giá trị nhân tử 𝛼𝑖 tƣơng ứng khác không. Do số b của bài toán gốc không có mặt trong bài toán đối ngẫu nên giá trị tối ƣu 𝑏∗ đƣợc chọn sao cho 𝑦𝑖𝑓 𝑥𝑖 = 1 đối với các chỉ số i mà 0 < 𝛼𝑖

Bài toán đối ngẫu là một bài toán tối ƣu với hàm mục tiêu là hàm bậc 2

(đối với 𝛼∗) có các điều kiện tuyến tính và xác định trên một tập lồi, do vậy có

tồn tại duy nhất một nghiệm tối ƣu. Giải bài toán tối ƣu này chúng ta có đƣợc ∗, 𝑖 = 1, … , 𝑙 và chúng ta có đƣợc hàm phân tách tuyến tính với lề

các hệ số 𝛼𝑖 cực đại:

𝑦 = 𝑠𝑖𝑔𝑛 𝜔∗. 𝑥 + 𝑏

∗ = 𝑠𝑖𝑔𝑛 𝑦𝑖𝛼𝑖

𝛼𝑖≠0

𝑥𝑖. 𝑥 + 𝑏∗ (3.42)

Với bài toán lề cực đại cứng thì điều kiện 0 ≤ 𝛼𝑖 ≤ 𝐶 đƣợc thay bởi 2 (2-norom) trong trƣờng hợp lề mềm thì ngoài

0 ≤ 𝛼𝑖. Với mức phạt bậc 2 ξ𝑖 điều kiện thay đổi nhƣ bài toán lề cứng thì hàm mục tiêu trở thành

28

𝑙

𝑙 𝑦𝑖 𝑦𝑗 𝛼𝑖𝛼𝑗 (𝑥𝑖. 𝑥𝑗 𝑖,𝑗 =1

𝑖=1

𝐿 𝛼 = + 𝛿𝑖𝑗 ) − 𝛼𝑖 (3.43) min 𝛼 1 2 1 𝐶

2.3.2. Phƣơng pháp hàm nhân (kernel methods)

Khả tách tuyến tính là một giả thuyết quá mạnh đối với các ứng dụng

trong thực tế.Thông thƣờng thì nhiều bài toán trong thế giới thực đòi hỏi các

sự vật, hiện tƣợng cần đƣợc mô tả bởi những thuộc tính (feature) phức tạp

hơn là một tổ hợp tuyến tính của các điểm đặc trƣng (attribute). Một trong

những giải pháp cho vấn đề này là mạng nơ-ron nhiều lớp (multilayer neural

networks) và các thuật toán huấn luyện nhƣ lan truyền ngƣợc

(backpropagation).

Hình 2.4 - Ba điểm trong mặt phẳng bị chia tách bởi một đường thẳng

có hướng.

Phƣơng pháp hàm nhân (kernel-based method) [2] đƣa ra một cách tiếp

cận khá độc đáo là ánh xạ hay chiếu toàn bộ dữ liệu sang một không gian

khác nhiều chiều hơn, thƣờng đƣợc gọi là không gian thuộc tính, và các mô

hình tuyến tính đƣợc áp dụng trong không gian mới này. Trong mục này

29

chúng ta sẽ tìm câu trả lời cho hai vấn đề quan trọng là tại sao khi làm việc

trong một không gian mới nhiều chiều thì mô hình tuyến tính lại có thể giải

quyết đƣợc các vấn đề phức tạp trong thực tế và làm sao để có thể áp dụng

phƣơng pháp hàm phân tách tuyến tính với lề cực đại trong không gian thuộc

tính mới này.

2.3.2.1 Chiều VC về khả năng phân tách của hàm tuyến tính

Chiều VC (VC dimension), mang tên hai tác giả Vapnik và

Chervonenkis, là một độ đo về năng lực (capacity) của một lớp hàm, ví dụ

nhƣ lớp các hàm tuyến tính mà chúng ta đang quan tâm. Chúng ta đã biết rằng

với một tập gồm l điểm thì sẽ có 2l cách khác nhau để gán nhãn các điểm này

với một trong hai −1 hoặc +1. Với mỗi phƣơng án gán nhãn, nếu có thể tìm

đƣợc một thành viên của họ hàm f(x,α) phân tách một cách chính xác tất cả

các điểm thì chúng ta gọi tập l điểm có thể bị chia tách bởi họ hàm đó. Chiều

VC đƣợc định nghĩa nhƣ sau:

Định nghĩa 3.6. Chiều VC của một họ hàm số 𝑓(𝑥, 𝛼) là số lƣợng lớn nhất h các véc-tơ 𝑥1, … , 𝑥𝑕 có thể đƣợc chia tách thành hai lớp với bất kỳ 2𝑕 cách gán nhãn nào (số lƣợng lớn nhất các véc-tơ có thể bị chia tách bởi họ

hàm). Nếu với bất kỳ số tự nhiên n nào đều tồn tại một tập n vec-tơ có thể bị

chia tách thì chiều VC của họ hàm 𝑓(𝑥, 𝛼) là vô tận. Bây giờ chúng ta cùng

trở lại với câu hỏi đã nêu: tại sao một hàm tuyến tính lại có năng lực lớn hơn

khi đƣợc áp dụng trọng một không gian nhiều chiều hơn. Định lý sau sẽ cho

chúng ta biết câu trả lời [2].

Định lý 3.3. Cho một tập gồm m điểm trong không gian 𝑅𝑑 và chọn một

điểm bất kỳ làm gốc tọa độ. Chúng ta có m điểm có thể bị chia tách bởi một

30

siêu phẳng nếu và chỉ nếu các véc-tơ vị trí của tất cả các điểm còn lại là độc

lập tuyến tính [2].

Một hệ quả có thể đƣợc rút ra từ định lý trên là chiều VC của các siêu

phẳng có hƣớng trong không gian 𝑅𝑑 chính là d + 1 bởi vì chúng ta luôn có

thể chọn đƣợc một tập nhiều nhất gồm d điểm độc lập tuyến tính.Nói một

cách khác, càng làm việc trong không gian nhiều chiều thì các siêu phẳng

càng có khả năng chia tách đƣợc nhiều véc-tơ khác nhau. Do vậy, một tập

điểm không khả tách tuyến tính trong không gian đặc trƣng ít chiều nhƣng

ảnh của chúng trong không gian thuộc tính nhiều chiều hơn lại có thể là khả

tách tuyến tính (và do vậy thuật toán tìm siêu phẳng với lề cực đại có thể đƣợc

áp dụng). Vấn đề cốt lõi ở đây là làm sao để có đƣợc, hay xây dựng đƣợc, các

ánh xạ đó.

2.3.2.2 Hàm nhân và SVM phi tuyến (Kernel function and nonlinear

SVMs)

SVMs là một ví dụ điển hình của phƣơng pháp hàm nhân [2]. Trong cả

bài toán tối ƣu tìm siêu phẳng với lề cực đại (3.37) và hàm quyết định (3.42),

chúng ta không làm việc trực tiếp với từng véc-tơ 𝑥𝑖, 𝑖 = 1, . . . , 𝑙, mà chỉ cần

tới tích vô hƣớng giữa hai véc-tơ bất kỳ. Trong bài toán đối ngẫu, những giá

trị của tích vô hƣớng giữa hai véc-tơ 𝑥𝑖. 𝑥𝑗 đóng vai trò là các tham số để tìm

ra giá trị tối ƣu của các tham số La-grăng 𝛼𝑖. Do vậy, chúng ta chỉ cần biết

cách tính đƣợc tích vô hƣớng giữa hai ảnh véc-tơ trong không gian thuộc tính

là cũng đủ để tìm đƣợc siêu phẳng tối ƣu trong không gian thuộc tính mà

không cần biết một cách tƣờng minh không gian thuộc tính đó có bao nhiêu

chiều hay ảnh của mỗi véc-tơ đặc trƣng có tọa độ cụ thể là bao nhiêu. Hàm số

để tính đƣợc tích vô hƣớng đó thƣờng đƣợc gọi là hàm nhân (kernel function)

đƣợc định nghĩa nhƣ sau:

31

Định nghĩa 3.7. Hàm nhân K là một hàm số trên không gian X mà với

mọi véc-tơ 𝑢, 𝑣 ∈ 𝑋

𝐾 𝑢, 𝑣 = 𝛷 𝑢 . 𝛷 𝑣 (3.44)

với Φ là một ánh xạ từ X tới một không gian (vô hƣớng) thuộc tính F

(3.45) 𝛷 ∶ 𝑅𝑑 → 𝐹 Φ

Một khi chúng ta có thể tính đƣợc tích vô hƣớng của hai véc-tơ trong

một không gian đặt trƣng nào đó thì chúng ta có thể tìm siêu phẳng tối ƣu

𝑙

trong không gian đó bằng cách thay các giá trị xi. xj trong (3.37) bởi K xi. xj

𝑙 𝑦𝑖𝑦𝑗 𝛼𝑖𝛼𝑗 𝐾(𝑥𝑖. 𝑥𝑗 ) 𝑖,𝑗 =1

𝑖=1

𝑙

− 𝛼𝑖 (3.46) min 𝛼 1 2

𝑖=1

𝑡𝑕ỏ𝑎 𝑚ã𝑛 𝑦𝑖𝛼𝑖 = 0 (3.47)

0 ≤ 𝛼𝑖 ≤ 𝐶, 𝑖 = 1, … , 𝑙. (3.48)

Khi đó, hàm phân tách có dạng:

𝛼𝑖≠0

𝑓 𝑥 = 𝑦𝑖 𝛼𝑖 𝐾 𝑥𝑖. 𝑥𝑗 + 𝑏 (3.49)

Vấn đề cốt lõi bây giờ là những hàm số trên không gian đặc trƣng nào có

thể là nhân, hay là hàm số để tính đƣợc tích vô hƣớng trên một không gian

thuộc tính (nhiều chiều) nào đó?

Về lý thuyết, tất cả những hàm số thỏa mãn điều kiện Mercer sau đây

đều có thể là hàm nhân.

Định lý 3.4.(Mercer condition) [2] Điều kiện cần và đủ để một hàm đối

xứng khả vi liên tục 𝐾 𝑢, 𝑣 trong không gian 𝐿2 𝐶 (các hàm khả vi bậc 2) có thể được khai triển dưới dạng

32

∞

𝑘=1

𝐾 𝑢, 𝑣 = 𝑎𝑘 𝑧𝑘 𝑢 𝑧𝑘 𝑣 (3.50)

với các hệ số 𝑎𝑘 > 0 (ví dụ: 𝐾 𝑢, 𝑣 mô tả một tích vô hướng trong

không gian thuộc tính nào đó), là điều kiện

𝑐

𝑐

𝐾 𝑢, 𝑣 𝑔 𝑢 𝑔 𝑣 𝑑𝑢𝑑𝑣 ≥ 0 (3.51)

thỏa mãn với mọi hàm 𝑔 ∈ 𝐿2 𝐶 (C là một tập con (compact) của 𝑅𝑑).

Trên thực tế ứng dụng, có hai loại hàm nhân đƣợc sử dụng rộng rãi nhất.

Đó là hàm đa thức (polynomial function) và hàm RBF (radial basis function)

 Hàm nhân đa thức: là hàm số trên không gian Rd có dạng

𝐾 𝑢, 𝑣 = 𝑢. 𝑣 𝑝 (3.52)

Với p = 2 và d = 2, chúng ta có thể xây dựng một cách tƣờng minh một ánh xạ Φ từ R2 tới R3 nhƣ sau:

2 (3.54)

𝛷 ∶ 𝑅2 → 𝑅3 (3.53)

2, 2𝑢1𝑢2, 𝑢2

𝑢1, 𝑢2 → 𝑢1

và 𝐾 𝑢, 𝑣 chính là tích vô hƣớng của hai véc-tơ Φ(u) và Φ(v) trong R3

(lƣu ý rằng một hàm nhân có thể tƣơng ứng với nhiều ánh xạ). Với d > 2,

2

𝑑

chúng ta có:

𝑖=1

𝑑

𝑑 = 𝑢𝑖𝑢𝑗

𝑢. 𝑣 2 = 𝑢𝑖𝑣𝑖

𝑖=1

𝑗 =1

𝑣𝑖𝑣𝑗

33

(𝑑,𝑑)

𝑖,𝑗 =(1,1)

(3.55) = (𝑢𝑖𝑢𝑗 )(𝑣𝑖𝑣𝑗 )

Đây chính là tích vô hƣớng của hai véc-tơ đặc trƣng

, (3.56) 𝛷 𝑢 = 𝑢𝑖𝑢𝑗

, (3.57) 𝛷 𝑣 = 𝑣𝑖𝑣𝑗 𝑑, 𝑑 𝑖, 𝑗 = 1,1 𝑑, 𝑑 𝑖, 𝑗 = 1,1

và số chiều của không gian đặc trƣng trong trƣờng hợp này là . 𝑑 + 1 2

Một cách tổng quát hơn, số chiều của không gian đặc trƣng tƣơng ứng

đối với hàm nhân đa thức bậc p đồng nhất (homogeneous) và không đồng

nhất (inhomogeneous)

Số chiều này là rất lớn so với d khi giá trị và Là 𝐾 𝑢, 𝑣 = 𝑢. 𝑣 𝑝 (3.58) 𝐾 𝑢, 𝑣 = 𝑢. 𝑣 + 𝑐 𝑝 (3.59) 𝑑 + 𝑝 − 1 𝑝 𝑑 + 𝑝 𝑝

của p tăng.

 Hàm nhân RBF: là hàm số có dạng

𝐾 𝑢, 𝑣 = 𝑒− 𝑢−𝑣 2/2𝛿2 (3.60)

trong đó δ thƣờng đƣợc gọi là độ rộng (width) của hàm. Trong trƣờng

hợp này, số chiều của không gian đặc trƣng là vô tận, và do vậy năng lực của

các hàm tuyến tính cũng trở nên không giới hạn.

2.4. Phân lớp bằng mạng lan truyền ngƣợc (mạng Nơron)

Trong sinh học mạng nơ-ron (Neural Networks -NN) [7] là một tập hợp

các dây thần kinh kết nối với nhau. Ngày nay, thuật ngữ này còn dùng để chỉ

mạng nơ-ron nhân tạo (Artificial Neural Networks -ANN), là một tập hợp các

34

linh kiện điện tử hoặc chƣơng trình máy tính đƣợc thiết kế để mô hình hóa

cách thức bộ não thực hiện. NN tƣơng tự với bộ não sinh học ở hai khía cạnh:

Tri thức có đƣợc thông qua quá trình học tập và điểm kết nối các tế bào thần

kinh đƣợc gọi là khớp thần kinh đƣợc sử dụng để lƣu trữ tri thức.

Kiến trúc mạng nơ-ron đƣợc định nghĩa bởi số lớp(layer), số đơn vị trên

mỗi lớp và sự liên kết giữa các lớp nhƣ thế nào. Mạng nơ-ron nói chung có

thể đƣợc chia làm 2 loại: mạng truyền thẳng và mạng hồi quy.

Hình 2.5 - Mạng nơ-ron truyền thẳng nhiều lớp

Mạng truyền thẳng: Dòng dữ liệu giữa đơn vị đầu vào và đầu ra chỉ

truyền thẳng theo một hƣớng. Việc xử lý dữ liệu có thể mở rộng ra thành

nhiều lớp, nhƣng không có các liên kết phản hồi. Điều đó có nghĩa là không

tồn tại các liên kết mở rộng từ các đơn vị đầu ra tới các đơn vị đầu vào trong

cùng một lớp hay các lớp trƣớc đó.

35

Hình 2.6 - Mạng nơ- ron hồi quy

Mạng hồi quy: Khác với mạng truyền thẳng, thuộc tính động của mạng

hồi quy có đƣợc từ các liên kết ngƣợc. Mạng hồi quy đƣợc dùng trong các

trƣờng hợp khi có thông tin hiện thời đƣa vào mạng đó, nhƣng chuỗi đầu vào

là rất quan trọng, và chúng ta cần mạng nơ ron đó lƣu trữ một bản ghi của các

đầu vào trƣớc tiên và khuếch đại chúng với dữ liệu hiện thời đó để sinh ra câu

trả lời.

Khả năng học là điều thu hút nhiều quan tâm nhất tới mạng nơ-ron. Cho

trƣớc một bài toán cụ thể để giải quyết, và một lớp các hàm 𝑓, việc học có

nghĩa là sử dụng một tập các quan sát để tìm hàm 𝑓∗ ∈ 𝐹 giải đƣợc bài toán

một cách tốt nhất.

Việc đó đòi hỏi định nghĩa một hàm chi phí 𝐶: 𝐹 → 𝑅 sao cho, với lời

giải tối ƣu 𝑓∗, 𝐶(𝑓 ∗) ≤ 𝐶(𝑓)∀𝑓 ∈ 𝐹

Hàm chi phí 𝐶 là một khái niệm quan trọng trong học máy, là một phép

đo khoảng cách tới lời giải tối ƣu cho bài toán cần giải quyết. Các thuật toán

học tìm kiếm trong không gian lời giải để đƣợc một hàm có chi phí nhỏ nhất

có thể.

Có hai kiểu học máy cơ bản là học có giám sát và học không giám sát.

36

Học có giám sát là quá trình huấn luyện lặp đi lặp lại cho đến khi kết

quả đạt đƣợc giá trị mong muốn đã biết, mà để làm đƣợc điều đó phải điều

chỉnh dần mạng do tồn tại sự khác biệt giữa đầu ra thực tế và đầu ra mong

muốn. Sự khác biệt này đƣợc thuật toán học sử dụng để điều chỉnh các trọng

số trong mạng.Việc điều chỉnh các trọng số nhƣ vậy thƣờng đƣợc mô tả nhƣ

một bài toán xấp xỉ số - cho dữ liệu huấn luyện bao gồm các cặp (mẫu đầu

vào x, và một đích tƣơng ứng t), mục đích là tìm hàm f(x) thoả mãn tất cả các

mẫu học đầu vào.

Học không giám sát không sử dụng tri thức bên ngoài trong quá trình

học nên còn đƣợc gọi là mạng tự tổ chức. Mạng sẽ phải khám phá các đặc

trƣng, các điều chỉnh, các mối tƣơng quan, hay các lớp trong dữ liệu vào một

cách tự động. Trong thực tế, đối với phần lớn các biến thể của học không

giám sát, các đích trùng với đầu vào. Nói một cách khác, học không giám sát

thực hiện một công việc tƣơng tự nhƣ một mạng tự nhiên liên hợp, cô đọng

thông tin từ dữ liệu vào.

37

Chƣơng 3: ỨNG DỤNG BÀI TOÁN PHÂN LỚP DỮ LIỆU

THUÊ BAO RỜI MẠNG

Chƣơng này giới thiệu về bài toán phân lớp dữ liệu thuê bao rời mạng.

Quy trình thực nghiệm phân lớp dữ liệu thuê bao rời mạng với các thuật toán

cây quyết định C4.5, NB, SVM; Sau khi tiến hành thực nghiệm thực hiện

đánh giá các thuật toán. Các thực nghiệm đƣợc tiến hành trên ngôn ngữ R để

lựa chọn thuộc tính và phân lớp dữ liệu thuê bao rời mạng.

3.1. Bài toán phân lớp dữ liệu thuê bao rời mạng

3.1.1. Phát biểu bài toán

- Dữ liệu quản lý khách hàng khách hàng thuê bao

- Dữ liệu chi tiết sử dụng dịch vụ của thuê bao

- Dữ liệu hóa đơn của thuê bao

- Dữ liệu khuyến mại của thuê bao

- Dữ liệu thuê bao rời mạng

- Dữ liệu thuê bao cần cần dự báo

Đầu vào:

Đầu ra: Đƣa ra mô hình phân lớp dự báo, các chỉ số đánh giá mô hình,

các luật rút ra từ mô hình giúp đƣa ra dự báo khách hàng có thể rời mạng.

Ví dụ:

Đầu vào: Thông tin về khách hàng: Khách hàng đã hoạt động đƣợc 6

tháng, là thuê bao Postpaid, số cuộc gọi ngoại mạng trong tháng gần nhất tăng

cao, số lƣợng cuộc gọi nội mạng giảm dần, số lƣợng tin nhắn tháng gần nhất

tăng 50% so với các tháng trƣớc

38

Đầu ra: Dự đoán khách hàng có 60% khả năng rời mạng.

3.1.2. Khái niệm thuê bao rời mạng “churn”

Đặc điểm của thị trƣờng viễn thông những năm qua là biến đổi nhanh

chóng, tự do hóa thị trƣờng, cải tiến kỹ thuật, độ bão hòa và cạnh tranh khốc

liệt. Khách hàng có nhiều sự lựa chọn giữa các nhà khai thác di động, họ có

thể chuyển đổi giữa các nhà khai thác mà không có bất kỳ khó khăn nào và

không ngừng tìm kiếm nhà mạng có dịch vụ tốt hơn với chi phí thấp.

“Churn” [6] là một thuật ngữ đƣợc sử dụng trong viễn thông và nhiều

ngành công nghiệp khác nó đề cập đến quyết định di chuyển từ một nhà cung

cấp dịch vụ này đến một nhà cung cấp dịch vụ khác của khách hàng. “Churn”

có nguồn gốc từ change (sự thay đổi) và turn (chiều hƣớng). “Churn” [9] xảy

ra bởi nhiều lý do khác nhau nhƣ không hài lòng với các dịch vụ hay các hóa

đơn cao hoặc khách hàng thƣờng nhận đƣợc ƣu đãi hấp dẫn khi đăng ký với

một nhà cung cấp dịch vụ di động mới. Khi khách hàng rời mạng cũng ảnh

hƣởng đến những ngƣời quen của họ trong cùng một mạng, điều này làm gia

tăng khả năng rời mạng của các thuê bao này. Nếu coi việc rời mạng là một

hiện tƣợng thì việc rời mạng là sự kết hợp của thói quen sử dụng của ngƣời

dùng và của những hoạt động của ngƣời xung quanh. Tỷ lệ “churn” trung

bình trong một nhà cung cấp dịch vụ di động là khoảng 2% mỗi tháng

(Berson, Smith, và Thearling, 2000). Tỷ lệ rời mạng hàng năm ở Châu Âu là

25%, Mỹ 37% và Châu Á 48% (Mattersion, 2001).

Định nghĩa: Thuê bao rời mạng là việc khách hàng không sử dụng dịch

vụ mạng của nhà cung cấp dịch vụ viễn thông.

Việc mất khách hàng đồng nghĩa với việc mất doanh thu trong tƣơng lai

và mất chi phí đầu tƣ để có lại những khách hàng này. Trong khi đó, tìm kiếm

39

khách hàng mới trở nên khó khăn hơn bao giờ hết do sự cạnh tranh khốc liệt

và độ bão hòa của thị trƣờng thông tin di động. Chi phí đƣợc khách hàng mới

là cao hơn đáng kể so với việc giữ khách hàng hiện tại. Trong thực tế, chi phí

để phát triển một thuê bao mới lớn 5-10 lần chi phí để giữ chân khách hàng.

Đối mặt với thách thức này, các nhà khai thác cần phải tập trung vào việc làm

thế nào để ngăn chặn khách hàng rời mạng. Biết trƣớc khi nào khách hàng rời

mạng sẽ cho phép nhà quản lý có chiến lƣợc phòng tránh, và có nhiều cơ hội

hơn trong việc giữ chân khách hàng thành công. Dự đoán khi nào khách hàng

sẽ “churn” giúp tăng doanh thu và tiết kiệm đƣợc nguồn lực cho nhà mạng

[9,12,13].

3.1.3. Thu thập, chuẩn hóa dữ liệu

Luận văn thực hiện thu thập dữ liệu thông tin thuê bao tại nhà cung cấp

dịch vụ viễn thông Mobifone Phú Thọ. Thực hiện trích xuất từ kho dữ liệu

Mobifone Phú Thọ, thu thập các dữ liệu cần thiết cho mô hình “churn”. Các

thông tin về khách hàng cần thiết cho dự đoán thuê bao rời mạng gồm: dữ liệu

quản lý khách hàng khách hàng thuê bao, dữ liệu chi tiết sử dụng dịch vụ của

thuê bao, dữ liệu thanh toán và khuyến mại của thuê bao, dữ liệu thuê bao rời

mạng.

Dữ liệu thu thập đƣợc sau khi lọc và loại bỏ các thông tin không chính

xác, không cần thiết thì gồm các thông tin [11,14]:

- Dữ liệu quản lý khách hàng: tuổi, giới tính, loại thuê bao, bƣu cục thu,

thời gian hoạt động.

- Dữ liệu sử dụng dịch vụ: số dịch vụ sử dụng, số cuộc gọi nội mạng, số

cuộc gọi ngoại mạng, số cuộc gọi quốc tế, thời gian gọi nội mạng, thời gian

gọi ngoại mạng, thời gian gọi quốc tế, số lƣợng SMS.

40

- Dữ liệu thanh toán: tiền phát sinh gọi nội mạng, tiền phát sinh gọi

ngoại mạng, tiền phát sinh gọi quốc tế, tiền phát sinh SMS, tiền phát sinh

Data, tổng số tiền phát sinh, số tiền đƣợc khuyến mại, mức tiền thực phải

thanh toán.

Mô hình dƣới đây thể hiện mối quan hệ của cơ sở dữ liệu dự đoán thuê

bao rời mạng. Trong đó các bảng call_detail, zone, promotion, bill_data là các

bảng nguồn, các bảng cust_info, churn_list, cust_churn, cust_neighbor,

call_zone, bill, charges_real là các bảng đích, cuối cùng cust_file - một bảng

view là trung tâm của cơ sở dữ liệu này. Cust_file là bảng tạo ra bởi sự kết

hợp của các bảng đích hình thành lƣợc đồ hình sao xung quanh nó.

Hình 3.1 - Mô hình quan hệ các bảng dữ liệu

Trong đó:

41

- Bảng cust_info: là bảng mô tả tính năng đặc trƣng của khách

hàng nhƣ: tuổi tác, giới tính, nơi ở, nơi thanh toán, ngày hòa

mạng…

- Bảng churn_list: là bảng danh sách các thuê bao rời mạng.

- Bảng call_detail: là thông tin chi tiết các cuộc gọi.

- Bảng zone: là bảng xác định mã vùng các cuộc gọi đi.

- Bảng promotion: bảng lƣu trữ thông tin khuyến mại của thuê

bao.

- Bảng bill_data: bảng lƣu trữ thông tin cƣớc các cuộc gọi và dịch

vụ của khách hàng.

- Bảng cust_churn: là bảng kết hợp giữa bảng cust_info và

churn_list mô tả thông tin các khách hàng rời mạng.

- Bảng call_zone: là bảng kết hợp giữa bảng call_detail và zone,

đƣa ra các vùng gọi đi của từng thuê bao.

- Bảng bill: là bảng kết hợp giữa bảng bill_data và promotion, đƣa

ra thông tin hóa đơn sử dụng tất cả các dịch vụ của thuê bao đã

đƣợc trừ đi khuyến mại.

- Bảng charges_real: là bảng lƣu thông cƣớc thực tế của thuê bao

chƣa trƣớc khi trừ khuyến mại.

“Churn” là một sự kiện quan hệ nhân quả do đó khi thực hiện chiết xuất

dữ liệu phải nắm bắt đƣợc những thay đổi trong các đặc điểm và hành vi của

khách hàng. Vai trò của một mô hình dự đoán là phát hiện những hành vi thay

đổi đáng chú ý dẫn đến rời mạng. Để thực hiện phân loại cần hai giai đoạn,

đầu tiên là giai đoạn phân tích, mà từ giai đoạn này có thể đƣa ra đƣợc những

42

đặc trƣng cho mỗi khách hàng. Giai đoạn còn lại đƣợc sử dụng để dán nhãn

phân biệt khách hàng rời mạng hoặc không rời mạng.

Do đặc trƣng của thuê bao trả sau là khách hàng thực hiện thanh toán

vào đầu tháng tiếp theo, nên thời gian đƣợc thiết lập để phân tích trong luận

văn này là 3 tháng và thời gian để quan sát là 1 tháng. Tất cả khách hàng đang

hoạt động vào đầu tháng quan sát sẽ nằm trong tập dữ liệu huấn luyện. Thời

gian quan sát đƣợc sử dụng để ghi nhãn khách hàng “churn” hoặc “no-churn”.

Những thuê bao rời mạng trong giai đoạn này đƣợc dán nhãn là “churn” và

những thuê bao không rời mạng sau giai đoạn này đƣợc dán nhãn là “no-

churn”. Sau thời gian quan sát một khách hàng “no-churn” có thể tiếp tục hoạt

động và sử dụng dịch vụ hoặc sau đó trở thành “churn”.

Hình 3.2 - Các giai đoạn của mô hình dự đoán thuê bao rời mạng

3.1.4. Lựa chọn thuộc tính

Lựa chọn thuộc tính liên quan đến quá trình lựa chọn một tập con của

các thuộc tính liên quan từ một tập các thuộc tính ban đầu. Lựa chọn thuộc

tính làm giảm số lƣợng các thuộc tính cho đầu vào các mô hình nhằm làm

43

giảm chi phí thu thập dữ liệu và chi phí tính toán. Hơn nữa, nó không những

mang lại kết quả chính xác hơn mà còn nhỏ gọn và dễ hiểu hơn."Lựa chọn

thuộc tính, như là một bước tiền xử lý cho quá trình học máy, rất hiệu quả

trong việc giảm chiều, loại bỏ dữ liệu không phù hợp, tăng độ chính xác, và

cải thiện toàn diện kết quả" (Kira & Rendell, 1992). Lựa chọn thuộc tính bao

gồm các lựa chọn riêng lẻ hoặc nhóm nhỏ. Lựa chọn thuộc tính riêng lẻ xếp

các thuộc tính riêng biệt theo một số liệu cụ thể mà lựa chọn nhóm có tính

đến sự tƣơng tác và mối tƣơng quan giữa các thuộc tính.

Trong bài toán phân lớp, lựa chọn thuộc tính nhằm mục đích chọn tập

các thuộc tính có khả năng phân biệt cao. Nói cách khác là chọn tính thuộc

tính có khả năng phân biệt các mẫu thuộc lớp khác nhau. Do thông tin của

nhãn là sẵn có nên sự phù hợp của các thộc tính đƣợc đánh giá cao.

Lựa chọn thuộc tính chủ yếu ảnh hƣởng đến giai đoạn đào tạo của bài

toán phân lớp [11,16]. Sau khi tạo ra các thuộc tính, thay vì trực tiếp huấn

luyện dữ liệu với toàn bộ các thuộc tính, ta thực hiện lựa chọn tập các tính

năng và sau đó huấn luyện dữ liệu với các tính năng đã đƣợc chọn. Các tính

năng đƣợc chọn có thể là độc lập với các thuật toán học (nhƣ filter models)

hoặc có thể lặp đi lặp lại sử dụng các thuật toán để đánh giá chất lƣợng các

tính năng lựa chọn (nhƣ wrapper models). Các tính năng đƣợc lựa chọn cuối

cùng đƣợc sử dụng cho giai đoạn phân lớp và dự báo.

44

Hình 3.3 - Lựa chọn thuộc tính trong phân lớp dữ liệu

Từ dữ liệu thu thập đƣợc và với thời gian phân tích là 3 tháng cho các

thuê bao tôi thu thập đƣợc 101 thuộc tính (chi tiết mô tả tại phụ lục 1 luận

văn)[11]. Trong 101 thuộc tính này có 5 thuộc tính nằm trong dữ liệu quản lý

khách hàng, 62 thuộc tính của thông tin chi tiết sử dụng dịch vụ của thuê bao

và 34 thuộc tính thuộc dữ liệu hóa đơn và khuyến mại của thuê bao.

Số lƣợng thuộc tính

Info: 5

Service: 62

Bill&Promo: 34

Hình 3.4 - Số lượng thuộc tính được thu thập

45

Từ các thuộc tính thu thập đƣợc ban đầu thực hiện lựa chọn và đánh giá

từng thộc tính, thực hiện loại bỏ các thuộc tính có độ chính xác thấp và các

thuộc tính có tỉ lệ lỗi ta thu đƣợc các thuộc tính lựa chọn (chi tiết phụ lục 2).

3.2. Lựa chọn phƣơng pháp, công cụ

3.2.1. Ngôn ngữ R

Phân tích số liệu và biểu đồ thƣờng đƣợc tiến hành bằng các phần mềm

thông dụng nhƣ SAS, SPSS, Stata, Statistica, và S-Plus. Đây là những phần

mềm đƣợc các công ty phần mềm phát triển và giới thiệu trên thị trƣờng

khoảng ba thập niên qua, và đã đƣợc các trƣờng đại học, các trung tâm nghiên

cứu và công ty trên toàn thế giới sử dụng cho giảng dạy và nghiên cứu.

Nhƣng vì chi phí để sử dụng các phần mềm này tuơng đối đắt tiền, một số

trƣờng đại học ở các nƣớc đang phát triển không có khả năng tài chính để sử

dụng chúng một cách lâu dài. Do đó, các nhà nghiên cứu thống kê trên thế

giới đã hợp tác với nhau để phát triển một phần mềm mới, với chủ trƣơng mã

nguồn mở, sao cho tất cả các thành viên trong ngành thống kê học và toán học

trên thế giới có thể sử dụng một cách thống nhất và hoàn toàn miễn phí.

Năm 1996, trong một bài báo quan trọng về tính toán thống kê, hai nhà

thống kê học Ross Ihaka và Robert Gentleman thuộc Trƣờng đại học

Auckland, New Zealand phát hoạ một ngôn ngữ mới cho phân tích thống kê

mà họ đặt tên là R. Sáng kiến này đƣợc rất nhiều nhà thống kê học trên thế

giới tán thành và tham gia vào việc phát triển R.

Cho đến nay, qua chƣa đầy 10 năm phát triển, càng ngày càng có nhiều

nhà thống kê học, toán học, nghiên cứu trong mọi lĩnh vực đã chuyển sang sử

dụng R để phân tích dữ liệu khoa học. Trên toàn cầu, đã có một mạng lƣới

hơn một triệu ngƣời sử dụng R, và con số này đang tăng rất nhanh. Có thể nói

46

trong vòng 10 năm nữa, vai trò của các phần mềm thống kê thƣơng mại sẽ

không còn lớn nhƣ trong thời gian qua nữa. Vậy R là gì? Nói một cách ngắn

gọn, R là một phần mề sử dụng cho phân tích thống kê và vẽ biểu đồ. Về bản

chất, R là ngôn ngữ máy tính đa năng, có thể sử dụng cho nhiều mục tiêu khác

nhau, từ tính toán đơn giản, toán học giải trí (recreational mathematics), tính

toán ma trận (matrix), đến các phân tích thống kê phức tạp. Vì là một ngôn

ngữ, cho nên ngƣời ta có thể sử dụng R để phát triển thành các phần mềm

chuyên môn.

Để sử dụng R, việc đầu tiên là chúng ta phải cài đặt R trong máy tính của

mình. Để làm việc này, ta phải truy nhập vào mạng và vào website có tên là

“Comprehensive R Archive Network” (CRAN) sau đây:

http://cran.R-project.org

Khi đã tải R xuống máy tính, bƣớc kế tiếp là cài đặt (set-up) vào máy

tính. Để làm việc này, chúng ta chỉ đơn giản nhấn chuột vào tài liệu trên và

làm theo hƣớng dẫn cách cài đặt trên màn hình. Đây là một bƣớc rất đơn giản,

chỉ cần 1 phút là việc cài đặt R có thể hoàn tất. Tài liệu cần tải về, tùy theo

phiên bản, nhƣng thƣờng có tên bắt đầu bằng mẫu tự R và số phiên bản

(version). Tài liệu này khoảng 26 MB, và địa chỉ cụ thể để tải là:

http://cran.r-project.org/bin/windows/base/R-2.2.2-win32.exe

47

Hình 3.5 – Giao diện làm việc trên ngôn ngữ R

3.2.2. Phƣơng pháp phân lớp

Luận văn lựa chọn thuật toán cây quyết định C4.5, NB, SVM để thử

nghiệm với bài toán phân lớp dữ liệu thuê bao rời mạng.

Đánh giá các phƣơng pháp phân lớp lựa chọn:

a. phƣơng pháp phân lớp cây quyết định

- Dễ hiểu không đòi hỏi chuẩn hóa dữ liệu nhƣ các thuật toán khác, có

thể xử lý lƣợng dữ liệu lớn thuê bao trong thời gian ngắn.

- Phƣơng pháp sử dụng giiải thuật tham lam chia để trị, đệ quy từ trên

xuống.

- Kết quả rễ ràng nhận thấy, có thể kiểm tra lại đơn giản bằng thống kê.

b. Phƣơng pháp phân lớp Naive bayes

48

Ƣu điểm:

- Dễ cài đặt thuật toán.

- Thời gian thi hành nhanh, tƣơng tự nhƣ phƣơng pháp cây quyết định.

- Đạt kết quả tốt trong phần lớn các trƣờng hợp thử nghiệm dữ liệu.

Nhƣợc điểm.

- Giả thiết về tính độc lập điều kiện các thuộc tính làm giảm độ chính

xác thuật toán.

c. Phƣơng pháp phân lớp SVM

Ƣu điểm:

- Hiệu quả với dữ liệu thuê bao số chiều lớn, giải quyết nhanh.

- Hiệu suất tổng hợp, tính toán tốt.

Nhƣợc điểm:

- Việc lựa chọn thuộc tính cho từng lớp là vấn đề quan trọng nó quyết

định đến hiệu quả phân lớp.

3.2.3. Đánh giá hiệu năng

Không có một thuật toán nào là ƣu việt hơn so với thuật toán khác trong

tất cả các lĩnh vực. Một số hoạt động tốt trong các lĩnh vực này, trong khi một

số khác thực hiện tốt hơn ở lĩnh vực khác. Trong luận văn này, các thuật toán

học đƣợc áp dụng để xây dựng các lớp. Hiệu năng của các lớp sẽ đƣợc so

sánh hay nói cách khác, các hiệu năng của các thuật toán khác nhau trên dữ

liệu sẽ đƣợc so sánh. Vậy, chỉ số "tốt" của một lớp là gì? Các tính chất mong

muốn là chính xác, tổng quát và mức độ tin cậy của dự báo. Ma trận nhầm lẫn

đƣa ra bốn kết quả khi một lớp đƣợc áp dụng trên một tập các trƣờng hợp.

49

Đƣợc phân lớp bởi thuật toán

Lớp 𝐶𝑖

Thuộc (yes) TPi Không thuộc (no) FNi Thuộc

Phân lớp thực sự đúng FPi TNi Không thuộc

Bảng 1 - Ma trận nhầm lẫn

Trong đó: - TPi:Số lƣợng các ví dụ thuộc lớp 𝐶𝑖 đƣợc phân loại chính xác

vào lớp 𝐶𝑖.

- FPi:: Số lƣợng các ví dụ không thuộc lớp 𝐶𝑖 bị phân loại nhầm

vào lớp 𝐶𝑖.

- TNi : Số lƣợng các ví dụ không thuộc lớp 𝐶𝑖 đƣợc phân loại

chính xác.

- FNi: Số lƣợng các ví dụ thuộc lớp 𝐶𝑖 bị phân loại nhầm vào các

lớp khác 𝐶𝑖

Khi đó độ chính xác Precision đối với lớp 𝐶𝑖

TP i TP i + FP i

(3.1) Precision Ci =

Độ hồi tƣởng Recall đối với lớp 𝐶𝑖

(3.2) Recall Ci =

Độ đo F = (3.3) TPi TPi + FNi Độ đo F1 đƣợc tính bằng công thức sau: 2 x P x R (P + R)

50

3.3. Thực nghiệm phân lớp trên ngôn ngữ R

Hình 3.6 – Quy trình thực nghiệm bài toán phân lớp dữ liệu thuê bao rời mạng

Quy trình thực nghiệm

Thực hiện làm việc với dữ liệu thực nghiệm thu thập đƣợc lƣu trữ tại thƣ

mục D:\churn\(các tệp excel). Các bƣớc thực hiện nhƣ sau:

Bƣớc 1: Nạp dữ liệu vào vùng làm việc

+ setwd("D:/Churn")

- Dịch chuyển con trỏ tới thƣ mục làm việc:

+ path=paste(getwd(),"/Data/",thisData,".class.csv",sep=""); + Y=read.csv(path,header=TRUE,sep=",")

+ path=paste(getwd(),"/Data/",thisData,".data.csv",sep=""); + X1 <- read.csv(path,header=TRUE,sep = "

- Thực hiện làm việc với các dữ liệu trong tệp

51

Bƣớc 2: Xử lý dữ liệu thu thập lựa chọn thuộc tính

Từ kho dữ liệu thực hiện lựa lựa chọn các thuộc tính có ảnh hƣởng tới

quá trình phân lớp nhiều nhất theo biến mục tiêu. Lựa chọn phƣơng pháp

InfoGain thực hiện đánh giá từng thuộc tính theo độ đo lƣợng thông tin và sau

đó xếp hạng và lựa chọn các thuộc tính có thứ hạng cao (chọn 20 thuộc tính

weights=information.gain(churn~., data) > subGain=cutoff.k(weights,20) - Thu đƣợc tập con gồm 20 thuộc tính

cao nhất).

Bƣớc 3: Thực hiện tạo 2 bộ dữ liệu phân lớp

- Bộ dữ liệu trainData: dùng huấn luyến ( tỷ lệ 70%)

> ind <- sample(2, nrow(dat), replace=TRUE, prob=c(0.7, 0.3)) > trainData <- dat[ind==1,]

> testData <- dat[ind==2,]

- Bộ dữ liệu testData: dùng kiểm thử (tỷ lệ 30%)

Bƣớc 4. Thực hiện phân lớp sử dụng các thuật toán lựa chọn

3.3.1. Phân lớp dữ liệu sử dụng cây quyết định C4.5

- Lựa chọn thuật toán cây quyết định C4.5 phân lớp ta có kết quả sau:

52

Hình 3-7 mô hình phân lớp cây quyết định

- Chi tiết nút nhánh thứ 15

Hình 3-8 Chi tiết nút nhánh thứ 15 trong phân lớp cây quyết định

+ Phần sẫm màu (no) thuê bao không rời mạng

+ Phần sáng màu (yes) khả năng thuê bao rời mạng

53

- Kết quả phân lớp:

Đƣợc phân lớp bởi thuật toán

Phân lớp

Thuộc (yes) Không thuộc (no)

146 78

Phân lớp thực sự đúng 10 1433 Thuộc (yes) Không thuộc (no)

Bảng 2 – Kết quả mô hình phân lớp sử dụng C 4.5

- Tỷ lệ phân lớp đúng: 94.43%

- Tỷ lệ phân lớp sai: 5.57%

Đánh giá hiệu năng:

Phƣơng pháp phân lớp Thuật toán Cây quyết định Precision 93.58 Recall 65.17 F-score 76.83

Bảng 3 – Độ đo hiệu năng thuật toán Cây quyết định

Kết quả thực nghiệm phân lớp sử dụng thuật toán Cây quyết định có độ

đo là: độ chính xác (P-Precision) đạt 93,58%, độ đo hồi tƣởng (R-Recall) đạt

65.17%, độ đo F đạt 76.83%.

3.3.2. Phân lớp dữ liệu sử dụng phƣơng pháp Naive Bayes

attach(churnTest) X=churnTest[,-20] Y=churnTest$churn model <- naiveBayes(churn~., data = churnTest) pred <- predict(model, X) table(pred,Y) Ta Thu đƣợc kết quả:

Lựa chon thuật toán NB thực hiện thực nghiệm với dữ liệu test:

54

Kết quả phân lớp:

Đƣợc phân lớp bởi thuật toán

Phân lớp

Thuộc (yes) Không thuộc (no)

118 59

Phân lớp thực sự đúng 106 1384 Thuộc (yes) Không thuộc (no)

Bảng 4 – Kết quả mô hình phân lớp sử dụng NB

- Tỷ lệ phân lớp đúng: 90.1%

- Tỷ lệ phân lớp sai: 9.9%

Đánh giá hiệu năng:

Phƣơng pháp phân lớp Thuật toán NB Precision 52.67 Recall 66.67 F-score 58.84

Bảng 5. – Độ đo hiệu năng thuật toán NB

Kết quả thực nghiệm phân lớp sử dụng thuật toán Cây quyết định có độ

đo là: độ chính xác (P-Precision) đạt 52.67%, độ đo hồi tƣởng (R-Recall) đạt

66.67 %, độ đo F đạt 58.84%.

55

3.3.3. Phân lớp dữ liệu bằng Support Vector Machines

- Thực hiện thực nghiệm với dữ liệu test với thuật toán SVM:

> attach(churnTest) > X=churnTrain[,-20] > Y=churnTrain$churn > msvm=svm(churn~.,data=churnTest) > summary(msvm)

Ta thu đƣợc kết quả:

Hình 3-9 Kết quả phân lớp dữ liệu bằng SVM

- Kết quả phân lớp:

Đƣợc phân lớp bởi thuật toán

Phân lớp

Thuộc (yes) Không thuộc (no)

32 0

Phân lớp thực sự đúng 192 1443 Thuộc (yes) Không thuộc (no)

Bảng 6 – Kết quả mô hình phân lớp sử dụng SVM

56

- Tỷ lệ phân lớp đúng: 88.48 %

- Tỷ lệ phân lớp sai: 11.52%

Đánh giá hiệu năng:

Phƣơng pháp phân lớp Thuật toán SVM Precision 14,28 Recall 100 F-score 24,99

Bảng 7. – Độ đo hiệu năng thuật toán SVM

Kết quả thực nghiệm phân lớp sử dụng thuật toán Cây quyết định có độ

đo là: độ chính xác (P-Precision) đạt 14,28 %, độ đo hồi tƣởng (R-Recall) đạt

100%, độ đo F đạt 24,99%.

3.3. Đánh giá kết quả

Do bài toán phân lớp dữ liệu thuê bao di động cần tìm ra lớp thuê bao rời

mạng, bởi vậy khi xem xét các mô hình cần ƣu tiên xem mức độ tin cậy của

lớp CHURN, hiệu năng của các thuật toán đối với lớp thuê bao rời mạng thể

hiện nhƣ sau:

- Tổng hợp hiệu năng các phƣơng pháp phân lớp

TT Phƣơng pháp phân lớp Precision Recall F-score

Thuật toán Cây quyết định 1 93.58 65.17 76.83

2 Thuật toán NB 52.67 66.67 58.84

3 Thuật toán SVM 14.28 100 24.99

Bảng 8. – Tổng hợp đánh giá hiệu năng các phương pháp phân lớp

57

120

100

80

Thuật toán Cây quyết định

60

Thuật toán NB

40

Thuật toán SVM

20

0

Precision

Recall

F-score

Hình 3.10 – Hiệu năng các thuật toán với lớp thuê bao rời mạng

Từ kết quả thực nghiệm, ta thấy mô hình phân lớp xây dựng từ thuật toán

cây quyết định C4.5 cho kết quả phân lớp tốt nhất.

Về thời gian xây dựng mô hình thuật toán cây quyết định C4.5 có thời

gian xây dựng mô hình là 0.1s, tiếp đó là thuật toán NB có thời gian xây dựng

nhanh nhất 0.19s, thuật toán SVM có thời gian xây dựng mô hình là 2,8s.

58

KẾT LUẬN

Trong giai đoạn thị trƣờng viễn thông đã đi vào giai đoạn bão hòa nhƣ

hiện nay, việc thuê bao rời mạng không những ảnh hƣởng đến doanh thu của

nhà mạng mà còn kéo theo hàng loạt hiệu ứng khác kèm theo. Bởi vậy dự

đoán thuê bao rời mạng để đƣa ra một chiến lƣợc kinh doanh hợp lý nhằm

ngăn khách hàng rời mạng là điều vô cùng cần thiết đối với các nhà

mạng.Trong luận văn này tôi đã nghiên cứu, tìm hiểu và phân tích dữ liệu

thuê bao di động và đạt đƣợc kết quả sau đây.

Nội dung đã đạt đƣợc

Đƣa ra cái nhìn tổng quan về thuê bao rời mạng, khái niệm thuê bao rời

mạng, các hình thức rời mạng của thuê bao.

Trình bày đƣợc lý thuyết khai phá dữ liệu, các ứng dụng khai phá dữ liệu

di động, bài toán phân lớp và dự báo.

Tìm hiểu các phƣơng pháp phân lớp dữ liệu.

Sau khi tìm hiểu và nghiên cứu lý thuyết phân lớp dữ liệu,thực nghiệm

phân lớp dữ liệu di động sử dụng các thuật toán cây quyết định C4.5, NB,

SVM và đánh giá kết quả thực nghiệm.

Hƣớng tiếp cận trong tƣơng lai

Do thời gian có hạn cùng với thuê bao trả trƣớc và thuê bao trả sau có

nhiều điểm khác biệt nhƣ hình thức thanh toán, giá cƣớc sử dụng hay các thuê

bao trả trƣớc có thể rời mạng một thời gian dài trƣớc khi nhà mạng nhận ra...

nên trong luận văn, bài toán phân lớp dữ liệu thuê bao rời mạng mới thực hiện

phân tích trên dữ liệu thuê bao trả sau mà chƣa thể áp dụng cho thuê bao trả

trƣớc. Vì vậy xây dựng bài toán phân lớp thuê bao rời mạng cho thuê bao trả

59

trƣớc là hƣớng nghiên cứu tiếp theo trong tƣơng lai và tôi tiếp tiếp tục nghiên

cứu phát triển sản phẩn thành phần mền dự báo ứng dụng với nhiều loại dữ

liệu khác nhau và để tích hợp trên các hệ thống khác.

60

TÀI LIỆU THAM KHẢO

Tài liệu tiếng Việt

[1]. Hà Quang Thụy, Phan Xuân Hiếu, Đoàn Sơn, Nguyễn Trí Thành, Nguyễn

Thu Trang, Nguyễn Cẩm Tú, Khai phá dữ liệu Web, NXB Giáo Dục, Hà Nội,

2009.

[2]. Nguyễn Đức Dũng, Lê Anh Cƣờng, Phân Xuân Hiếu, Lƣơng Chi Mai, Lê

Hải Sơn, Học máy - Machine Learning, Viện Công nghệ thông tin – Viện Hàn

lâm Khoa học và Công nghệ Việt Nam, 2015.

[3]. PGS -TS. Ngô Quốc Tạo, Bài giảng Khai phá dữ liệu - Đại học Công

nghệ thông tin và Truyền thông - Đại Học Thái Nguyên.

Tài liệu tiếng Anh

[4]. Jiawei Han University of Illinois at Urbana-Champaign, Micheline

Kamber, Jian Pei Simon Fraser University, Data Mining: Concepts and

Techniques - Third Edition, 2012.

[5]. K. H. Liao and H. E. Chueh, Applying fuzzy data mining to telecom

churn management - Intelligent Computing and Information Science, 2011.

[6]. Pushpa and G.Shobha, Social Network Analysis for Churn Prediction in

Telecom data, 2012.

[7]. J. O. Daramola, O. O Oladipupo, and G. A. Musa, A data mining process

framework for churn management in mobile telecommunication industry.

[8]. E. Shaaban, Y. Helmy, A. Khedr, and M. Nasr, A proposed churn

prediction model - International Journal of Engineering Research and

Applications.

[9]. Georges D. Olle Olle and Shuqin Cai, A Hybrid Churn Prediction Model

in Mobile Telecommunication Industry, 2014.

61

[10]. Jiliang Tang, Salem Alelyani and Huan Liu, Feature Selection for

Classification: A Review, 2013.

[11]. Huong Xuan Nguyen, Customer Churn Prediction for the Icelandic

Mobile Telephony Market, 2011.

[12]. Clement Kirui, Li Hong, Wilson Cheruiyot and Hillary Kirui, Predicting

Customer Churn in Mobile Telephony IndustryUsing Probabilistic Classifiers

in Data Mining, 2013.

[13]. Vladislav Lazarov, Marius Capota, Churn Prediction.

[14]. Ali Daud, Muhammad Akram Shaikh, and Faqir Muhammad, Pattern

Mining in Telecom Data.

[15]. Sen Wu, Naidong Kang, Liu Yang, Fraudulent Behavior Forecast in

Telecom IndustryBased on Data Mining Technology.

[16]. J. Burez, D. Van den Poel, Handling class imbalance in customer churn

prediction, 2009.

62

PHỤ LỤC 1

Danh sách các thuộc tính thu thập đƣợc

Thuộc tính Mô tả TT

1. Thông tin số tuổi của khách hàng

2. Loại thuê bao

3. Giới tính AGE TYPE_ID GENDER

Số ngày hoạt động của thuê bao 4. NUM_DATEACTIVE kê từ khi băt đầu

5. Bƣu cục thu của thuê bao POSTCODE

Số loại dịch vụ sử dụng lớn nhât 6. USE_SERVICE_MAX trong 3 tháng quan sát

Tháng sử dụng dịch vụ nhỏ nhât 7. USE SERVICE MIN MONTH trong 3 tháng quan sát

Tháng sử dụng dịch vụ lớn nhât 8. USE_SERVICE_MAX_MONTH trong 3 tháng quan sát

Tỉ lệ sử dụng dịch vụ trong tháng

9. quan sát đầu tiên so với tổng số USE_SERVICE_RATIO 1

lƣợng dịch vụ trong 3 tháng

Tỉ lệ sử dụng dịch vụ trong tháng

quan sát thứ 2 so với tổng số 10. USE_SERVICE_RATIO2

lƣợng dịch vụ trong 3 tháng

Tỉ lệ sử dụng dịch vụ trong tháng

quan sát thứ 3 so với tổng số 11. USE_SERVICE_RATIO3

lƣợng dịch vụ trong 3 tháng

Tỷ lệ số giây gọi nội mạng của 12. VOI_INNET_RA1

63

thuê bao trong tháng quan sát

đầu tiên so với tổng số giây gọi

ngoại mạng của 3 tháng quan sát

Tỷ lệ số giây gọi nội mạng của

thuê bao trong tháng quan sát

13. VOI INNET RATIO2 thứ 2 so với tổng số giây gọi

trong tháng

Tỷ lệ số giây gọi ngoại mạng của

thuê bao trong tháng quan sát

14. VOI_OUTNET_RA3 thứ 3 so với tổng số giây gọi

ngoại mạng của 3 tháng quan sát

Tỷ lệ số giây gọi ngoại mạng

trong tháng quan sát đầu tiên của

15. VOI OUTNET RATIO 1 thuê bao so với tổng số giây gọi

trong tháng

Tỷ lệ số giây gọi nƣớc ngoài của

thuê bao trong tháng quan sát

16. VOI_ABROAD_RA2 thứ 2 so với tổng số giây gọi

nƣớc ngoài của 3 tháng quan sát

Tỷ lệ số giây gọi ngƣớc ngoài

của thuê bao trong tháng quan

17. VOI_ABROAD_RATIO 1 sát đầu tiên so với tổng số giây

gọi trong tháng

Tỷ lệ số cuộc gọi nội mạng của

thuê bao trong tháng quan sát 18. VOI_INNET_FREQ_RA 1

đầu tiên so với tổng số cuộc gọi

64

ngoại mạng của 3 tháng quan sát

Tỷ lệ số cuộc gọi nội mạng của

thuê bao so với tổng số cuộc gọi 19. VOI_INNET_FREQ_RATIO1

trong tháng quan sát đầu tiên

Tỷ lệ số cuộc gọi ngoại mạng

của thuê bao so với tổng số cuộc 20. VOI_OUTNET_FREQ_RA1 gọi ngoại mạng của 3 tháng quan

sát

Tỷ lệ số cuộc gọi ngoại mạng

của thuê bao trong tháng quan

21. VOI_OUTNET_FREQ_RATIO1 sát đầu tiên so với tổng số cuộc

gọi trong tháng

Tỷ lệ số cuộc gọi nƣớc ngoài của

thuê bao trong tháng quan sát 22. VOI_ABROAD_FREQ_RA1 đầu tiên so với tổng số cuộc gọi

nƣớc ngoài của 3 tháng quan sát

Tỷ lệ số cuộc gọi ngƣớc ngoài

23. VOI_ABROAD_FREQ_RATIO1 của thuê bao so với tổng số cuộc

gọi trong tháng

Tỷ lệ số tin nhắn của thuê bao

tháng quan sát đầu tiên so với 24. SMS RA1

tổng số tin nhắn trong 3 tháng

Tỷ lệ số giây gọi nội mạng của

thuê bao trong tháng quan sát 25. VOI INNET RA2

thứ 2 so với tổng số giây gọi

65

ngoại mạng của 3 tháng quan sát

Tỷ lệ số giây gọi nội mạng của

thuê bao trong tháng quan sát 26. thứ 2 so với tổng số giây gọi VOI_INNET_RATIO2

trong tháng

Tỷ lệ số giây gọi ngoại mạng của

thuê bao trong tháng quan sát 27. thứ 2 so với tổng số giây gọi VOI_OUTNET_RA2

ngoại mạng của 3 tháng quan sát

Tỷ lệ số giây gọi ngoại mạng của

thuê bao trong tháng quan sát 28. thứ 2 so với tổng số giây gọi VOI_OUTNET_RATIO2

trong tháng

Tỷ lệ số giây gọi nƣớc ngoài của

thuê bao trong tháng quan sát 29. thứ 2 so với tổng số giây gọi VOI_ABROAD_RA2

nƣớc ngoài của 3 tháng quan sát

Tỷ lệ số giây gọi ngƣớc ngoài

của thuê bao trong tháng quan 30. sát thứ 2 so với tổng số giây gọi VOI_ABROAD_RATIO2

trong tháng

Tỷ lệ số cuộc gọi nội mạng của

thuê bao trong tháng quan sát 31. thứ 2 so với tổng số cuộc gọi VOI_INNET_FREQ_RA2

ngoại mạng của 3 tháng quan sát

Tỷ lệ số cuộc gọi nội mạng của 32. VOI_INNET_FREQ_RATIO2

66

thuê bao trong tháng quan sát

thứ 2 so với tổng số cuộc gọi

trong tháng

Tỷ lệ số cuộc gọi ngoại mạng

của thuê bao trong tháng quan 33. sát thứ 2 so với tổng số cuộc gọi VOI_OUTNET_FREQ_RA2

ngoại mạng của 3 tháng quan sát

Tỷ lệ số cuộc gọi ngoại mạng

của thuê bao trong tháng quan 34. sát thứ 2 so với tổng số cuộc gọi VOI_OUTNET_FREQ_RATIO2

trong tháng

Tỷ lệ số cuộc gọi nƣớc ngoài của

thuê bao trong tháng quan sát 35. thứ 2 so với tổng số cuộc gọi VOI_ABROAD_FREQ_RA2

nƣớc ngoài của 3 tháng quan sát

Tỷ lệ số cuộc gọi ngƣớc ngoài

của thuê bao trong tháng quan 36. VOI_ABROAD_FREQ_RATIO2 sát thứ 2 so với tổng số cuộc gọi

trong tháng

Tỷ lệ số tin nhắn của thuê bao

tháng quan sát thứ 2 so với tổng 37. SMS_RA2

số tin nhắn trong 3 tháng

Tỷ lệ số giây gọi nội mạng của

thuê bao trong tháng quan sát 38. thứ 3 so với tổng số giây gọi VOI_INNET_RA3

ngoại mạng của 3 tháng quan sát

67

Tỷ lệ số giây gọi nội mạng của

thuê bao trong tháng quan sát 39. thứ 3 so với tổng số giây gọi VOI_INNET_RATIO3

trong tháng

Tỷ lệ số giây gọi ngoại mạng của

thuê bao trong tháng quan sát 40. thứ 3 so với tổng số giây gọi VOI_OUTNET_RA3

ngoại mạng của 3 tháng quan sát

Tỷ lệ số giây gọi ngoại mạng của

thuê bao trong tháng quan sát 41. thứ 3 so với tổng số giây gọi VOI_OUTNET_RATIO3

trong tháng

Tỷ lệ số giây gọi nƣớc ngoài của

thuê bao trong tháng quan sát 42. thứ 3 so với tổng số giây gọi VOI_ABROAD_RA3

nƣớc ngoài của 3 tháng quan sát

Tỷ lệ số giây gọi ngƣớc ngoài

của thuê bao trong tháng quan 43. sát thứ 3 so với tổng số giây gọi VOI_ABROAD_RATIO3

trong tháng

Tỷ lệ số cuộc gọi nội mạng của

thuê bao trong tháng quan sát 44. thứ 3 so với tổng số cuộc gọi VOI_INNET_FREQ_RA3

ngoại mạng của 3 tháng quan sát

Tỷ lệ số cuộc gọi nội mạng của 45. thuê bao trong tháng quan sát VOI_INNET_FREQ_RATIO3

68

thứ 3 so với tổng số cuộc gọi

trong tháng

Tỷ lệ số cuộc gọi ngoại mạng

của thuê bao trong tháng quan 46. sát thứ 3 so với tổng số cuộc gọi VOI_OUTNET_FREQ_RA3

ngoại mạng của 3 tháng quan sát

Tỷ lệ số cuộc gọi ngoại mạng

của thuê bao trong tháng quan 47. sát thứ 3 so với tổng số cuộc gọi VOI_OUTNET_FREQ_RATIO3

trong tháng

Tỷ lệ số cuộc gọi nƣớc ngoài của

thuê bao trong tháng quan sát 48. thứ 3 so với tổng số cuộc gọi VOI_ABROAD_FREQ_RA3

nƣớc ngoài của 3 tháng quan sát

Tỷ lệ số cuộc gọi ngƣớc ngoài

của thuê bao trong tháng quan 49. sát thứ 3 so với tổng số cuộc gọi VOI_ABROAD_FREQ_RATIO3

trong tháng quan sát thứ 3

Tỷ lệ số tin nhắn của thuê bao

trong tháng quan sát thứ 3 so với 50. SMS_RA3

tổng số tin nhắn trong 3 tháng

Tháng có số lƣợng giây gọi nội

51. VOI_INNET_MAXM mạng lớn nhất

Tháng có số lƣợng cuộc gọi nội

52. VOI_INNET_FREQ_MAXM mạng lớn nhất

53. Tháng có số lƣợng giây gọi VOI_OUTNET_MAXM

69

ngoại mạng lớn nhất

Tháng có số lƣợng cuộc gọi

54. VOI_OUTET_FREQ_MAXM ngoại mạng lớn

Tháng có số lƣợng giây gọi quốc

55. VOI_ABROAD_MAXM tế lớn nhất

Tháng có số lƣợng cuộc gọi quốc

56. VOI_ABROAD_FREQ_MAXM tế lớn nhất

Tháng có số lƣợng giây gọi nội

57. VOI_INNET_MINM mạng nhỏ nhất

Tháng có số lƣợng cuộc gọi nội

58. VOI_INNET_FREQ_MINM mạng nhỏ nhất

Tháng có số lƣợng giây gọi 59. VOI_OUTNET_MINM ngoại mạng nhỏ nhất

Tháng có số lƣợng cuộc gọi 60. VOI_OUTET_FREQ_MINM ngoại mạng nhỏ nhất

Tháng có số lƣợng giây gọi quốc

61. VOI_ABROAD_MINM tế nhỏ nhất

Tháng có số lƣợng cuộc gọi quốc

62. VOI_ABROAD_FREQ_MINM tế nhỏ nhất

Tháng có số lƣợng SMS lớn nhất

Tháng có số lƣợng SMS bé nhất 63. SMS_MAXM 64. SMS_MINM

Tháng có dung lƣợng data lớn

65. DATA_MAXM nhất

Tháng có dung lƣợng data nhỏ

66. DATA_MINM nhất

Tháng có số giây (tất cả các cuộc 67. VOI_MAXM

70

gọi) tối đa

Tháng có số cuộc gọi lớn nhất 68. VOI_FREQ_MAXM

Tháng có số giây (tất cả các cuộc

69. VOI_MINM gọi) nhỏ nhất

Tháng có số cuộc gọi nhỏ nhất 70. VOI_FREQ_MINM

Tỷ lệ mức tiền trả các cuộc gọi

nội mạng so với mức cƣớc phát 71. sinh trong tháng quan sát đầu TCHARGE_INNET_RATIO1

tiên

Tỷ lệ mức tiền trả các cuộc gọi

ngoại mạng so với mức cƣớc 72. phát sinh trong tháng quan sát TCHARGE_OUTNET_RATIO1

đầu tiên

Tỷ lệ mức tiền trả các cuộc gọi

quốc tế so với mức cƣớc phát 73. sinh trong tháng quan sát đầu TCHARGE_ABROAD_RATIO1

tiên

Tỷ lệ mức tiền trả SMS so với

mức cƣớc phát sinh trong tháng 74. TCHARGE_SMS_RATIO1

quan sát đầu tiên

Tỷ lệ mức tiền trả Data so với

mức cƣớc phát sinh trong tháng 75. TCHARGE_DATA_RATIO1

quan sát đầu tiên

Tỷ lệ mức tiền trả các cuộc gọi

nội mạng so với mức cƣớc phát 76. TCHARGE_INNET_RATIO2

sinh trong tháng quan sát thứ 2

71

Tỷ lệ mức tiền trả các cuộc gọi

ngoại mạng so với mức cƣớc 77. phát sinh trong tháng quan sát TCHARGE_OUTNET_RATIO2

thứ 2

Tỷ lệ mức tiền trả các cuộc gọi

78. quốc tế so với mức cƣớc phát TCHARGE_ABROAD_RATIO2

sinh trong tháng quan sát thứ 2

Tỷ lệ mức tiền trả SMS so với

79. mức cƣớc phát sinh trong tháng TCHARGE_SMS_RATIO2

quan sát thứ 2

Tỷ lệ mức tiền trả Data so với

80. mức cƣớc phát sinh trong tháng TCHARGE_DATA_RATIO2

quan sát thứ 2

Tỷ lệ mức tiền trả các cuộc gọi

81. nội mạng so với mức cƣớc phát TCHARGE_INNET_RATIO3

sinh trong tháng quan sát thứ 3

Tỷ lệ mức tiền trả các cuộc gọi

ngoại mạng so với mức cƣớc 82. TCHARGE_OUTNET_RATIO3 phát sinh trong tháng quan sát

thứ 3

Tỷ lệ mức tiền trả các cuộc gọi

83. quốc tế so với mức cƣớc phát TCHARGE_ABROAD_RATIO3

sinh trong tháng quan sát thứ 3

Tỷ lệ mức tiền trả SMS so với

mức cƣớc phát sinh trong tháng 84. TCHARGE_SMS_RATIO3

quan sát thứ 3

72

Tỷ lệ mức tiền trả Data so với

85. mức cƣớc phát sinh trong tháng TCHARGE_DATA_RATIO3

quan sát thứ 3

Tháng có mức cƣớc phát sinh 86. TCHARGE_INNET_MAXM gọi nội mạng cao nhất

Tháng có mức cƣớc phát sinh 87. TCHARGE_OUTNET_MAXM gọi ngoại mạng cao nhất

Tháng có mức cƣớc phát sinh 88. TCHARGE_ABROAD_MAXM gọi quốc tế cao nhất

Tháng có mức cƣớc phát sinh

89. TCHARGE_SMS_MAXM SMS cao nhất

Tháng có mức cƣớc phát sinh

90. TCHARGE_DATA_MAXM Data cao nhất

Tháng có mức cƣớc phát sinh 91. TCHARGE_INNET_MINM gọi nội mạng thấp nhất

Tháng có mức cƣớc phát sinh 92. TCHARGE_OUTNET_MINM gọi ngoại mạng thấp nhất

Tháng có mức cƣớc phát sinh 93. TCHARGE_ABROAD_MINM gọi quốc tế thấp nhất

Tháng có mức cƣớc phát sinh

94. TCHARGE_SMS_MINM SMS thấp nhất

Tháng có mức cƣớc phát sinh

95. TCHARGE_DATA_MINM Data thấp nhất

Tháng có mức cƣớc phát sinh

96. TCHARGE_MAXM cao nhất

Tháng có mức cƣớc phát sinh 97. TCHARGE_MINM

73

thấp nhất

Tháng có tiền khuyến mại cao

98. PROMO_MAXM nhất

Tháng có tiền cƣớc khuyến mại

99. PROMO_MINM thấp nhất

Tháng có hóa đơn thanh toán cao

100. BILL_MAXM nhất

Tháng có hóa đơn thanh toán

101. BILL_MINM thấp nhất

74

PHỤ LỤC 2

Danh sách các thuộc tính đƣợc lựa chọn

TT Thuộc tính Mô tả

Tỷ lệ số giây gọi ngoại mạng

trong tháng quan sát đầu tiên của 1. VOI_OUTNET_RATIO1 thuê bao so với tổng số giây gọi

trong tháng

Số ngày hoạt động của thuê bao 2. NUM_DATEACTIVE kể từ khi bắt đầu

Tỷ lệ số tin nhắn của thuê bao

3. tháng quan sát thứ 2 so với tổng SMS_RA2

số tin nhắn trong 3 tháng

4. Loại thuê bao TYPE_ID

Tỷ lệ số tin nhắn của thuê bao

5. tháng quan sát đầu tiên so với SMS_RA1 tổng số tin nhắn trong 3 tháng

Tỷ lệ mức tiền trả Data so với

6. mức cƣớc phát sinh trong tháng TCHARGE_DATA_RATIO3

quan sát thứ 3

Tỷ lệ số giây gọi ngƣớc ngoài

của thuê bao trong tháng quan sát 7.

đầu tiên so với tổng số giây gọi VOI_ABROAD_RATIO1

trong tháng

Tỷ lệ mức tiền trả Data so với 8. TCHARGE_DATA_RATIO2 mức cƣớc phát sinh trong tháng

75

quan sát thứ 2

Tỷ lệ số giây gọi nội mạng của

thuê bao trong tháng quan sát 9.

đầu tiên so với tổng số giây gọi VOI_INNET_RA1

ngoại mạng của 3 tháng quan sát

Tỷ lệ số cuộc gọi nội mạng của

thuê bao trong tháng quan sát 10.

đầu tiên so với tổng số cuộc gọi VOI_INNET_FREQ_RA1

ngoại mạng của 3 tháng quan sát

Tỷ lệ số giây gọi ngoại mạng của

thuê bao trong tháng quan sát thứ 11.

3 so với tổng số giây gọi ngoại VOI_OUTNET_RA3

mạng của 3 tháng quan sát

Tỷ lệ mức tiền trả Data so với

12. mức cƣớc phát sinh trong tháng TCHARGE_DATA_RATIO1

quan sát đầu tiên

Tỷ lệ mức tiền trả các cuộc gọi

13. quốc tế so với mức cƣớc phát TCHARGE_ABROAD_RATIO2

sinh trong tháng quan sát thứ 2

Tỷ lệ mức cƣớc phát sinh trong

tháng đầu tiên quan sát so với 14.

tổng mức cƣớc phát sinh trong 3 TCHARGE_RATIO1

tháng quan sát

Tháng có dung lƣợng data nhỏ 15. DATA_MINM nhất

Tỷ lệ mức tiền trả các cuộc gọi 16. TCHARGE_INNET_RATIO2

76

nội mạng so với mức cƣớc phát

sinh trong tháng quan sát thứ 2

Tháng có mức cƣớc phát sinh gọi 17. TCHARGE_INNET_MINM nội mạng thấp nhất

Tỷ lệ mức tiền trả SMS so với

18. mức cƣớc phát sinh trong tháng TCHARGE_SMS_RATIO1

quan sát đầu tiên

Tháng có mức cƣớc phát sinh 19. TCHARGE_DATA_MINM Data thấp nhất

Tháng có tiền cƣớc khuyến mại 20. PROMO_MINM thấp nhất