Luận văn Thạc sĩ Công nghệ thông tin: Một mô hình kết hợp học giám sát và bán giám sát cho bài toán dự báo khách hàng có nguy cơ rời mạng vinaphone

Chia sẻ: Tomjerry001 | Ngày: | Loại File: PDF | Số trang:44

Thêm vào BST

Báo xấu

29
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nội dung của luận văn bao gồm: Chương 1: Khái quát bài toán dự đoán khách hàng rời mạng giới thiệu khái quát dự đoán khách hàng rời mạng trong viễn thông, các khái niệm liên quan. Trình bày vai trò của khai phá dữ liệu trong dự đoán khách hàng rời mạng. Một số nghiên cứu về bài toán dự đoán khách hàng rời mạng. Chương 2: Một số mô hình điển hình cho bài toán dự báo khách hàng rời mạng giới thiệu một số mô hình điển hình cho bài toán dự bao khách hàng rời mạng. Chương 3: Kết hợp học giám sát và bán giám sát cho bài toán dự đoán khách hàng rời mạng phân tích, đề xuất, trình bày mô hình kết hợp giữa học bán giám sát self-training và học giám sát dựa trên luật cho bài toán dự đoán các khách hàng có nguy cơ rời mạng. Chương 4: Thực nghiệm và đánh giá kết quả trình bày quá trình thực nghiệm của luận văn, đưa ra một số đánh giá về hiệu quả của mô hình, nhận xét các kết quả đạt được.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Công nghệ thông tin: Một mô hình kết hợp học giám sát và bán giám sát cho bài toán dự báo khách hàng có nguy cơ rời mạng vinaphone

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ HOÀN MỘT MÔ HÌNH KẾT HỢP HỌC GIÁM SÁT VÀ BÁN GIÁM SÁT CHO BÀI TOÁN DỰ BÁO KHÁCH HÀNG CÓ NGUY CƠ RỜI MẠNG VINAPHONE LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN HÀ NỘI - 2015
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ HOÀN MỘT MÔ HÌNH KẾT HỢP HỌC GIÁM SÁT VÀ BÁN GIÁM SÁT CHO BÀI TOÁN DỰ BÁO KHÁCH HÀNG CÓ NGUY CƠ RỜI MẠNG VINAPHONE Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã số:60.48.01.04 LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN Ngƣời hƣớng dẫn khoa học: PGS.TS. HÀ QUANG THỤY HÀ NỘI - 2015 iii
Lời cảm ơn Lời đầu tiên tôi xin gửi lời cảm ơn chân thành và biết ơn sâu sắc tới PGS.TS Hà Quang Thụy, người Thầy đã chỉ bảo và hướng dẫn tận tình cho tôi trong suốt quá trình từ khi là sinh viên, tới khi học thạc sĩ và trong suốt quá trình nghiên cứu và thực hiện luận văn này. Tôi xin chân thành cảm ơn sự dậy bảo, giúp đỡ, tạo điều kiện của các Thầy, Cô trong trường Đại học Công Nghệ, Đại học Quốc Gia Hà Nội trong suốt quá trình tôi học tập tại Trường. Tôi xin chân thành cảm ơn sự giúp đỡ, tạo điều kiện và khuyến khích tôi trong quá trình nghiên cứu của các Thầy, Cô, anh chị tại phòng thí nghiệm Khoa học dữ liệu và Công nghệ tri thức (DS&KTLAB) và Đề tài ĐHQGHN QG.14.13. Cuối cùng, tôi xin gửi lời cảm ơn tới gia đình, người thân và bạn bè – những người luôn ở bên tôi trong lúc khó khăn, động viên, khuyến khích tôi trong cuộc sống và công việc. Tôi xin chân thành cảm ơn! Tác giả Nguyễn Thị Hoàn i
Lời cam đoan Tôi xin cam đoan luận văn được hoàn thành trên cơ sở nghiên cứu, tổng hợp và phát triển các nghiên cứu về bài toán dự báo khách hàng rời mạng trong nước và trên thế giới do tôi thực hiện. Luận văn này là mới, các đề xuất trong luận văn do chính tôi thực hiện, qua quá trình nghiên cứu đưa ra và không sao chép nguyên bản từ bất kỳ một nguồn tài liệu nào khác. ii
Mục lục Lời cảm ơn ....................................................................................................................... i Danh mục các hình vẽ và bảng biểu ................................................................................ v Danh mục từ viết tắt ....................................................................................................... vi Mở đầu ............................................................................................................................ 1 Chƣơng 1: Khái quát bài toán dự đoán khách hàng rời mạng ................................. 2 1.1.Bài toán dự đoán khách hàng rời mạng ..................................................................... 2 1.2.Vai trò của khai phá dữ liệu trong quản lý khách hàng rời mạng ............................. 3 1.3. Một số nghiên cứu cho bài toán dự đoán khách hàng rời mạng............................... 4 1.3.1. Đánh giá hiệu quả của mô hình ............................................................................. 4 1.3.2. Một số mô hình nghiên cứu về dự đoán khách hàng rời mạng ............................. 5 1.4.Tóm tắt chương 1....................................................................................................... 8 Chƣơng 2: Một số mô hình điển hình cho bài toán dự đoán khách hàng rời mạng9 2.1. Mô hình dựa trên luật cho bài toán dự đoán khách hàng rời mạng dịch vụ viễn thông ............................................................................................................................ 9 2.1.1. Giới thiệu mô hình phân lớp dựa trên luật ............................................................ 9 2.1.2. Mô hình sinh các luật ............................................................................................ 9 2.1.3. Phân lớp ............................................................................................................... 12 2.1.4. Kết quả và đánh giá mô hình ............................................................................... 13 2.2. Mô hình học lai cho bài toán dự đoán khách hàng rời mạng ................................. 15 2.3. Tóm tắt chương 2 .................................................................................................... 21 Chƣơng 3: Mô hình kết hợp giám sát và bán giám sát cho bài toán dự đoán khách hàng rời mạng .............................................................................................................. 22 3.1. Tiếp cận mô hình bài toán ...................................................................................... 22 3.2. Tiền xử lý dữ liệu ................................................................................................... 24 3.3. Mô hình học giám sát dựa trên thuật toán K-NN ................................................... 24 3.4. Mô hình học bán giám sát dựa trên thuật toán self-training ................................... 25 3.5. Mô hình học giám sát dựa trên hệ thống luật: ........................................................ 27 3.6. Phân lớp .................................................................................................................. 28 Tổng kết chương 3 ......................................................................................................... 29 iii
Chƣơng 4: Thực nghiệm và đánh giá kết quả .......................................................... 30 4.1. Môi trường thực nghiệm:........................................................................................ 30 4.2. Quá trình thực nghiệm ............................................................................................ 30 4.3. Kết quả thực nghiệm............................................................................................... 32 4.4. Đánh giá kết quả và hướng nghiên cứu tiếp theo ................................................... 34 4.5.Tóm tắt chương 4.................................................................................................... 34 Tài liệu tham khảo ....................................................................................................... 35 iv
Danh mục các hình vẽ và bảng biểu Hình 1: So sánh độ AUC giữa các mô hình .................................................................. 14 Hình 2: So sánh AUC mô hình CRL và DMEL cho tỉ lệ churn rate khác nhau ........... 15 Hình 3: So sánh AUC cho mô hình CRL và DMEL với tập dữ liệu UCI ..................... 15 Hình 4: Giải thuật sinh luật FOIL................................................................................. 17 Hình 5: Giải thuật sinh 1 luật FOIL............................................................................... 18 Hình 6: Mô hình dự đoán lai cua Ying Hwuang và cộng sự ......................................... 18 Hình 7: So sánh đường cong ROC, AUC với kỹ thuật phân lớp khác nhau ................ 21 Hình 8: So sánh hiệu quả của mô hình lai đề xuất và các mô hình lai khác dựa trên ROC ............................................................................................................................... 21 Hình 9: Mô hình kết hợp học giám sát và bán giám sát ................................................ 23 Hình 10: Một ví dụ về phân lớp KNN ........................................................................... 25 Hình 11: Mô hình học bán giám sát Self-training ......................................................... 26 Hình 12: Sơ đồ thuật toán Self-training......................................................................... 27 Hình 13: Giả mã học luật FOIL ..................................................................................... 28 Hình 14: Giả mã học 1 luật FOIL .................................................................................. 28 Bảng 1: Tỉ lệ rời mạng của các mạng tại Hàn Quốc năm 2007-2008 ............................. 9 Bảng 2: Chức năng, kỹ thuật khai phá dữ liệu và ứng dụng ........................................... 3 Bảng 3: Ma trận Confusion ............................................................................................. 4 Bảng 4: Tập dữ liệu cho mô hình dự đoán dựa trên luật ............................................... 13 Bảng 5: Tập dữ liệu mô hình Ying Hwuang và cộng sự ............................................... 20 Bảng 6: Kết quả mô hình Ying Hwuang và cộng sự sử dụng độ đo AUC.................... 20 Bảng 7: So sánh mô hình Ying Hwuang và cộng sự với một số mô hình khác ............ 20 Bảng 8: Phần mềm sử dụng trong luận văn ................................................................... 30 Bảng 9: Bảng mô tả dữ liệu mẫu .................................................................................. 31 Bảng 10: Trọng số một số thuộc tính dữ liệu ................................................................ 31 Bảng 11: Ma trận Confusion ......................................................................................... 33 Bảng 12: Kết quả thực nghiệm với trọng số weight2 .................................................... 33 Bảng 13: Kết quả thực nghiệm với trọng số weight1 .................................................... 34 v
Danh mục từ viết tắt STT Từ/cụm từ Tên viết tắt 1 K Nearest Neigbours KNN 2 Area Under ROC AUC 3 Support Vector Machines SVM 4 Classification by Rules Learning CRL 5 Data Mining by Evolutionary Learning DMEL 6 True Prediction/False Prediction TP/FP 7 First Order Inductive Learning FOIL vi
Mở đầu Sự phát triển mạnh mẽ của công nghệ viễn thông trong những năm gần đây đã mở ra nhiều cơ hội cho các nhà cung cấp dịch vụ mạng di động. Song song với việc mở rộng và phát triển các khách hàng mới, việc quản lý khách hàng cũ cũng là một nhiệm vụ quan trọng. Dự báo khách hàng có nguy cơ rời mạng chính là phần trọng yếu trong quản lý khách hàng rời mạng. Xác định được khách hàng có nguy cơ rời mạng giúp nhà cung cấp dịch vụ kịp thời đưa ra các biện pháp, phương thức để quản lý, chăm sóc khách hàng, tránh để khách hàng rời bỏ dịch vụ của mình. Nhiều mô hình cho bài toán dự báo khách hàng rời mạng đã được nghiên cứu và phát triển. Các công trình nghiên cứu về dự báo khách hàng rời mạng được công bố trong các hội nghị nổi tiếng như Elsevier1 và được áp dụng thực tế tại các nhà mạng lớn như Taiwan Mobile của Đài Loan, China Mobile, của Trung Quốc, T&T của Mỹ. Nội dung luận văn thạc sĩ “Một mô hình kết hợp học giám sát và bán giám sát cho bài toán dự báo khách hàng có nguy cơ rời mạng Vinaphone” tập trung vào nghiên cứu, khảo sát, đánh giá và đề xuất một mô hình dự đoán khách hàng rời mạng, bên cạnh đó, áp dụng mô hình này cho dự đoán khách hàng có nguy cơ rời bỏ mạng viễn thông VinaPhone. Ngoài phần mở đầu và kết luận, luận văn đƣợc tổ chức thành 4 chƣơng nhƣ sau: Chƣơng 1: Khái quát bài toán dự đoán khách hàng rời mạng giới thiệu khái quát dự đoán khách hàng rời mạng trong viễn thông, các khái niệm liên quan. Trình bày vai trò của khai phá dữ liệu trong dự đoán khách hàng rời mạng. Một số nghiên cứu về bài toán dự đoán khách hàng rời mạng. Chƣơng 2: Một số mô hình điển hình cho bài toán dự báo khách hàng rời mạng giới thiệu một số mô hình điển hình cho bài toán dự bao khách hàng rời mạng. Chƣơng 3: Kết hợp học giám sát và bán giám sát cho bài toán dự đoán khách hàng rời mạng phân tích, đề xuất, trình bày mô hình kết hợp giữa học bán giám sát self-training và học giám sát dựa trên luật cho bài toán dự đoán các khách hàng có nguy cơ rời mạng. Chƣơng 4: Thực nghiệm và đánh giá kết quả trình bày quá trình thực nghiệm của luận văn, đưa ra một số đánh giá về hiệu quả của mô hình, nhận xét các kết quả đạt được. 1
Chƣơng 1: Khái quát bài toán dự đoán khách hàng rời mạng 1.1. Bài toán dự đoán khách hàng rời mạng Trong những năm gần đây, có nhiều sự thay đổi lớn trong công nghiệp viễn thông như sự mở rộng của thị trường, các dịch vụ và công nghệ mới dẫn đến cạnh tranh khốc liệt trong thị trường viễn thông. Việc rời bỏ mạng của khách hàng làm sụt giảm một lượng lớn dịch vụ viễn thông và khiến nó trở thành vấn đề nghiêm trọng của các nhà cung cấp dịch vụ. Khách hàng rời mạng (customer churn) được xem là những khách hàng có giá trị rời bỏ sử dụng dịch của một nhà mạng sang sử dụng dịch vụ của một nhà mạng khác. Quản lý khách hàng rời mạng (churn management) là các chính sách xử lý của nhà mạng nhằm giữ chân các khách hàng có nguy cơ rời mạng. Một trong những thách thức của “churn management” là dự đoán các “churner”. Bài toán dự đoán khách hàng rời mạng (churn prediction) chính là đi tìm các “churner” dựa trên các thuộc tính của khách hàng như: dữ liệu hợp đồng, thông tin khách hàng, log sử dụng dịch vụ, chi tiết cuộc gọi, dữ liệu khiếu nại, thông tin hóa đơn và thanh toán. Theo các nghiên cứu thị trường của Berson, Smitch và cộng sự năm 2000 [C1_06], tỉ lệ khách hàng ngưng sử dụng dịch vụ của các nhà mạng di động lên tới 2% trên tháng. Điều đó có nghĩa mỗi nhà mạng mất gần ¼ lượng khách hàng mỗi năm, hơn nữa, các nhà mạng Châu Á phải đối mặt với nhiều thách thức rời mạng hơn là các nhà mạng khác trên thế giới. Hình 1: Tỉ lệ rời mạng của một số mạng Châu Âu năm 2010-2011(1) Trên thực tế, một nhà mạng có thể phân đoạn các khách hàng của họ dựa trên các lợi ích mà khách hàng mang lại và quản lý khách hàng chỉ dựa trên phân đoạn khách hàng có lợi ích. Tuy nhiên, công nghiệp dịch vụ viễn thông không thể tiêu 2
chuẩn hóa tập độ đo lợi ích. Vì vậy, kỹ thuật khai phá dữ liệu được áp dụng để giải quyết vấn đề thách thức của khách hàng rời mạng trong lĩnh vực dịch vụ viễn thông. 1.2. Vai trò của khai phá dữ liệu trong quản lý khách hàng rời mạng Áp dụng công cụ hỗ trợ của khai phá dữ liệu trong quản lý khách hàng là một xu hướng trong kinh tế toàn cầu. Phân tích và hiểu các hành vi, đặc tính của khách hàng để giữ lại các khách hàng tiềm năng, tối ưu hóa giá trị khách hàng. Công cụ khai phá dữ liệu tỏ ra hữu dụng trong việc trích xuất và xác định các thông tin hữu dụng, các kiến thức từ cơ sở dữ liệu khách hàng. Khai phá dữ liệu là trích xuất các thông tin ẩn từ một tập dữ liệu lớn với khả năng cao để giúp các công ty tìm ra các xu hướng quan trọng nhất trong dữ liệu lớn của họ. Các hỗ trợ từ công cụ khai phá dữ liệu có thể trả lời các câu hỏi mà kinh doanh truyền thống cần nhiều thời gian để giải quyết. Leijeune [Lei-01] cho rằng kỹ thuật khai phá dữ liệu là kỹ thuật cho phép biến đổi dữ liệu gốc thành tri thức kinh doanh. Viện SAS [SAS] định nghĩa khai phá dữ liệu như là “xử lý lựa chọn, biểu diễn và mô hình lượng lớn dữ liệu để khám phá ra các mẫu có lợi cho kinh doanh chưa được biết đến trước đó”. Tóm lại, chúng ta có thể nói rằng, khai phá dữ liệu là áp dụng các thuật toán phân tích và khám phá dữ liệu để phát hiện ra các mẫu cho dự đoán và mô tả. Trong quản lý quan hệ khách hàng, kỹ thuật khai phá dữ liệu hay được sử dụng nhất gồm: phân cụm, luật quy nạp, thuật toán di truyền, cây quyết định và mạng neuron. Bảng dưới chỉ ra các kỹ thuật, hàm khai phá dữ liệu và ứng dụng trong miền khai phá dữ liệu. Chức năng Kỹ thuật Ứng dụng Mạng Neuron Đánh gia tỉ lệ thay đổi Thống kê Đánh giá giá cổ phiếu Cây quyết định Biển thủ hóa đơn Làm mờ Phân đoạn thị trường Phân lớp Mạng Neuron Thuật toán di truyền Mạng Neuron Dự đoán khách hàng rời mạng Dự đoán Hồi quy Dự đoán gian lân Cây quyết định Mạng Neuron Thuật toán di truyền Phân đoạn thị trường Phân đoạn Cây quyết định Thống kê Bảng 1: Chức năng, kỹ thuật khai phá dữ liệu và ứng dụng 3
1.3. Một số nghiên cứu cho bài toán dự đoán khách hàng rời mạng 1.3.1. Đánh giá hiệu quả của mô hình Sau khi bộ phân lớp/dự đoán được xây dựng, nó được sử dụng để dự đoán các hành vi tương lai của khách hàng. Một trong những bước quan trọng để chắc chắn mô hình hoạt động tốt là đánh giá mô hình dự đoán, có nghĩa là xem xét tỉ lệ khách hàng rời mạng. Tỉ lệ dự đoán được đánh giá bằng tỉ lệ rời mạng đúng (True churn rate - TP) và tỉ lệ rời mạng sai (false churn rate– FP). Mục tiêu của phương pháp là đạt tỉ lệ TP cao và tỉ lệ FP thấp. Bảng 3 định nghĩa ma trận về tỉ lệ TP và FP, trong đó, a11 là số churner được dự đoán đúng, a12 là số churner được dự đoán sai, a21 là số non-churn được dự đoán đúng và a22 là số non-churn dự đoán sai. Theo ma trận, tỉ lệ TP - được định nghĩa là tỉ lệ các churner được phân lớp đúng, tính theo công thức: a11 TP  a11  a12 Và FP được định nghĩa là tỉ lệ các churner được phân lớp sai, tính theo công thức: a21 FP  a21  a22 Confusion matrix Predicted Actual Churn Non-churn Churn a11 a12 Non-churn a22 a21 Bảng 2: Ma trận Confusion Từ cặp TP và FE, kỹ thuật đường cong hoạt động nhận được (Receive Operationg Curves (ROC) ) [Bradley-97] được sử dụng để tìm cặp tỉ lệ dự đoán mong đợi (TP và FP). Tuy nhiên, kỹ thuật ROC thường khó sử dụng để đánh giá từ các kỹ thuật mô hình dự đoán khác nhau hoặc tập thuộc tính dữ liệu khác nhau. Để giải quyết khó khăn, kỹ thuật tính miền dưới đường cong ROC (Area under ROC AUC) được sử dụng để đánh giá mô hình và tập thuộc tính trong dự đoán khách hàng rời mạng. Miền dưới đường cong ROC được tính theo công thức: s0  n0 x(n0  1) x0.5 AUC  n0 n1 4
Với S0 là tổng xếp hạng của lớp 0 (churn) mẫu test, n0 là số mẫu trong tập test thuộc lớp 0(churn) và n1 là số mẫu thuộc tập lớp 1(nonchurn). 1.3.2. Một số mô hình nghiên cứu về dự đoán khách hàng rời mạng a. Trích chọn đặc trƣng Trích chọn đặc trưng là một bước quan trọng, có thể ảnh hưởng tới hiệu quả của mô hình dự đoán. Tập thuộc tính cho dự đoán khách hàng rời mạng trong lĩnh vực dịch vụ viễn thông chia thành các mục con sau:  Thông tin tiểu sử khách hàng: Các nhóm thông tin về giới tính, tuổi, loại khách hàng.  Thông tin về tài khoản: loại dịch vụ sử dụng (trả trước/trả sau), chu kỳ cước, tài khoản, loại thiết bị, phương thức thanh toán, tổng hợp các thuộc tính về thời lượng cuộc gọi, số cuộc gọi.  Dịch vụ sử dụng: Các gói cước đăng ký  Thông tin khiếu nại  Thông tin thanh toán và hóa đơn  Cuộc gọi chi tiết: Thời lượng cuộc gọi, giá cả, loại cuộc gọi cho mọi cuộc gọi.  Chi tiết cuộc gọi đến: b. Chuẩn hóa dữ liệu Một số mô hình dự đoán, phân lớp gặp khó khăn trong xử lý dữ liệu liên tục (dạng chuỗi,..). Quá trình chuẩn hóa dữ liệu chia các các thuộc tính liên tục thành các thuộc tính rời rạc. Quá trình này thường được sử dụng như bước đầu tiên trong các hàm tuyến tính hoặc học quy nạp. Mô tả dữ liệu thành dạng mà bộ phân lớp, dự đoán có thể hiểu được. c. Dự đoán/Phân lớp Rất nhiều kỹ thuật được đề xuất cho mô hình dự đoán trong viễn thông, dưới đây là bẩy mô hình phổ biến:  Mô hình hồi quy logic (Logistic Regressions): [Hosmer-89]: Được áp dụng rộng rãi cho phân lớp xác xuất rõ ràng. Hồi quy xác suất đánh giá xác suất để xảy ra sự kiện như sau: k 0   k k k 1 e prob( y  1)  k 0   k k 1 e k 1 Trong đó y là biến thập phân biểu diễn xuất hiện sự kiện (ví dụ y = 1 nếu sự kiện xảy ra, y =0 nếu ngược lại). 1,  2 ,...,  k là các tham số đầu vào độc lập. 0, 1 ,..., k là các hệ số hồi quy được đánh giá bởi phương thức thống kê cực đại, dựa trên các các 5
dữ liệu đào tạo được cung cấp. Chi tiết về phương pháp hồi quy logic được mô tả bởi Homsmer và Lemeseshow [Homs-89] .  Mô hình cây quyết định Phương pháp “chia để trị” được áp dụng để xây dựng một cây nhị phân. Ban đầu, phương pháp tìm kiếm các thuộc tính với thông tin tốt nhất để làm node gốc và chia cây nhị phân thành các cây con. Tương tự, đối với các cây con cũng được mở rộng với luật giống như cây cha.Việc phân chia dừng lại nếu đến node hoặc khi hết thông tin. Khi cây được tạo, các luật thu được bằng cách thăm mỗi nhánh của cây. Chi tiết về cây quyết định được Quinlan mô tả kỹ trong [Quinlan-96] .  Mô hình Naïve Bayes Thuật toán Naïve Bayes dựa trên định lý Bayes được phát biểu như sau: ( ) ( | ) ( ) ( | ) ( ) ( ) Áp dụng trong bài toán phân loại, 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 ⃗ ( )  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: ( | ) ( ) ( | ) ( ) Theo tính chất độc lập điều kiện: ( | ) ∏ ( | ) Trong đó:  ( | ) là xác suất thuộc phân lớp i khi biết trước mẫu X.  ( ) xác suất là phân lớp i.  ( | ) 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 Naïve Bayes: Bước 1: Huấn luyện Naïve Bayes (dựa vào tập dữ liệu), tính ( ) và ( | ) Bước 2: Phân lớp ( ), ta cần tính xác suất thuộc từng phân lớp khi đã biết new new trước X . X được gán vào lớp có xác suất lớn nhất theo công thức ( ( )∏ ( | )) 6
Chi tiết phân lớp Naïve Bayes chi tiết trong mô tả của [Langley-92]  Phân lớp tuyến tính (Linear Classifiers) Bộ phân lớp tuyến tính map một không gian thuộc tính X vào một tập nhãn lớp Y bằng một hàm tuyến tính. Hàm phân lớp tuyến tính f(x) có thể được viết như sau: f ( x)  sgn( w i xi  b) i Với w i  là trọng số của các lớp và b  là hằng số. giá trị của f ( x) với biến đầu vào x quyết định lớp gán nhãn. Ví dụ, trong phân lớp nhị phân, nhãn của lớp là +1 nếu f ( x)  0, ngược lại, gán nhãn là -1. Trong số wi và hằng số b được xác định từ tập ví dụ học đã gán nhãn. Chi tiết được mô tả trong [Vapnik-98].  Mạng Neuron nhân tạo (Artificial neural networks) Một một neuron đa lớp (Multilayer Perceptron Neural Networks (MLP)) là một mạng neuron giám sát, thường bao gồm lớp đầu và lớp ẩn và lớp đầu ra. Thông thường, hàm khởi động của MLP là hàm sigmoid. Ví dụ MLP với một lớp ẩn, đầu ra mạng có thể đạt được bằng cách biến đổi hàm khởi động của đơn vị ẩn sử dụng hai tầng xử lý. L D Outputnet ( j )  f ( w ji f ( w ii xi )), j  1,..., J i 1 i Với D, L và J là tổng số đơn vị lớp đầu vào, ẩn, và lớp ra, f là hàm khởi tạo. Chi tiết về mạng Neuron nhân tạo được Rumelhart, Hiton và Williams mô tả chi tiết trong [Rumelhart-86]  Máy Vector hỗ trợ (Support Vector Machines - SVM) Một bộ phân lớp SVM sử dụng thuật toán học nhằm xây dựng một siêu mặt phẳng làm cực tiểu hóa độ phân lớp sai của một đối tượng dữ liệu mới. Độ phân lớp sai của một siêu phẳng được đặc trưng bởi khoảng cách bé nhất tới siêu phẳng đấy. Xét bài toán phân lớp đơn giản nhất – phân lớp hai lớp với tập mẫu dữ liệu: {(x i ,yi )i=1,2,...N, x i  R m } Trong đó mẫu là các vector đối tượng được phân lớp thành các mẫu dương và mẫu âm. Các mẫu dương là các mẫu xi thuộc lĩnh vực quan tâm và được gãn nhãn yi=1. Các mẫu âm là các mẫu xi không thuộc lĩnh vực quan tâm và được gán nhãn yi=-1. Thực chất phương pháp này là một bài toán tối ưu, mục tiêu là tìm ra một không gian H và siêu mặt phẳng quyết định h trên H sao cho sai số phân lớp là thấp nhất. Trong trường hợp này, tập phân lớp SVM là mặt phẳng phân tách các mẫu dương khỏi các mẫu âm với độ chênh lệch cực đại, trong đó độ chênh lệch-còn gọi là 7
Lề (margin) xác định bằng khoảng cách giữa các mẫu dương và các mẫu âm gần mặt siêu phẳng nhất. Mặt siêu phẳng này được gọi là mặt siêu phẳng lề tối ưu. Tập phân lớp SVM được định nghĩa như sau: f ( x)  sign(C   w i x ) Với w = w1+w2+…+wn là bộ hệ số siêu phẳng hay là các vector trọng số. C là độ dịch. Trong đó: sign(z) = +1 nếu z  0 và sign(z) =-1 nếu z
Chƣơng 2: Một số mô hình điển hình cho bài toán dự đoán khách hàng rời mạng 2.1. Mô hình dựa trên luật cho bài toán dự đoán khách hàng rời mạng dịch vụ viễn thông 2.1.1. Giới thiệu mô hình phân lớp dựa trên luật Phương pháp phân lớp dựa trên học luật (classification by rule learning (CRL)) là một phương pháp nổi tiếng. Một trong những đặc trưng của quy nạp luật là chúng rõ ràng và dễ hiểu hơn những mô hình khác. Đã có nhiều nghiên cứu về lĩnh vực này. Trong xử lý luật quy nạp, hai phương pháp thường được sử dụng là: general-to- specific(top-down) tức là xử lý từ luật chung đến các luật riêng và phương pháp specific-to-general (bottom-up) tức là đi từ các luật riêng tới các luật chung. Trong đó, phương pháp top-down thường được áp dụng rộng rãi hơn. “Luật” được định nghĩa là một mệnh đề dạng: {NẾU Tiền đề THEN kết quả}, với tiền đề được định nghĩa là một sự kết hợp của một số cặp và kết quả là nhãn của lớp. “Luật chung” và “luật riêng” là hai khái niệm quan trọng. Thông thường, một luật với cặp nhỏ hơn trong kết quả thì “chung” hơn. 2.1.2. Mô hình sinh các luật Phân lớp dựa trên học luật (CRL) là một chiến lược từ chung-đến-riêng, vì vậy, nó bắt đầu bằng việc sinh các luật chung, first-order luật, sau đó sinh các luật lớp cao hơn dựa vào các luật bậc thập hơn (lower-order). Thuật toán [Giải thuật1] bên dưới minh họa việc xử lý sinh tập luật. Với SETrules là tập luật được sinh ra, k là số bậc. và threshold là số bậc tối đa. Giải thuật 1: CRL Algorithm (training data) 1: SETrules ←  ; 2: k ← 1; 3: SETrules ← First_order_rules(training data) 4: While k ≤ threshold do 5: high_order ← Higher_order_rules(lower_order_rules); 6: SETrules ← SETrules high_order; 8: end while 9: return SETrules 9
First-order Rules (Giải thuật 2): Thuật toán sinh ra luật bậc đầu tiên first-order rules. Để tránh mất thông tin, tất cả các cặp được đưa vào tài khoản. Trong thuật toán 2, num_attribute, num_interval và num_class định nghĩa số thuộc tính, số khoảng cách của thuộc tính hiện tại và số phân lớp khác nhau. Đầu tiên, set first_order_rule là rỗng, ruleijk là luật có dạng “IF fi=Intervalj THEN Classk”, Nếu Prunning(ruleijk) trả lại false, thì ruleijk được xem là một luật hữu ích. Giải thuật 2: First_order_rules(training data) 1. First_order_rules ←  ; 2. For i=1; i ≤ num_attribute; i++ do 3. For j=1; j≤ num_interval; j++ do 4. For k=1; k≤ num_class; k++ do 5. If Pruning (ruleijk) returns fales then 6. First_order_rules ← First_order_rule ruleijk 7. End if 8. End for 9. End for 10. End for 11. Return First_order_rules High-order Rules (Giải thuật 3): Highter-order rules được xây dựng lặp lại từ các luật cấp thấp hơn. Luật bậc 2 (second_order) được xây dựng từ luật bậc 1 (first_order), luật bậc 3 (third_order) được xây dựng từ luật bậc 2 (second_order). Luật (n-1)_order là cơ sơ để xây dựng luật n_order. Trong thuật toán 3, item được dùng để định nghĩa một cặp , positive_items bao gồm tất các các phần tử được trích xuất từ tất cả các luật dương. Tập các negative-items cũng được sinh tương tự. Mỗi luật riêng được đặc tả bởi thuật toán hill_climbing để thêm một phần tử vào phần tiền đề của luật hiện tại. Để đánh giá chất lượng của luật được sinh ra, chúng ta có thể sử dụng độ đo Weighted Relative Accuracy (WRA), được tính như sau: Num _(a) Num _(a, c) Num(c) WRA  x(  ) Num _ total Num _(a) Num _ total 10
Trong đó Num_(a) và Num_(c) là số trường hợp dữ liệu được trích xuất từ tiền đề và kết quả của luật, và num_total được định nghĩa là số trường hợp trong tập dữ liệu học. Giải thuật 3: Higher_order_rules (a set of lower_order_rules) 1. all_rules ←  ; 2. positive_items ← get all exclusive items from positive_lower_order_rules; 3. negative_items ← get all exclusive items from negative_lower_order_rules; 4. accuracy_list ←  ; 5. For i=1; i ≤ num_positive_rules; i++ do 6. High_rule ← hill_climbing (positivei , positive_item); 7. If Pruning (high_rule) returns false then 8. WRAi ← calculate the Weighted_Relative_Accuracy for high_rule; 9. If WRAi is not in the list of accuracy_list then 10. all_rules ← all_rules high_rule; 11. accuracy_list ← accuracy_list WRAi ; 12. end if 13. end if 14. end for 15. do same work to generate negative_rules; 16. all_rules ← all_rules negative_rule; 17. return all_rules Thuật toán hill_climbing Giải thuật 4: hill_climbing (one_lower_rule, all_low_items) 1. accuracy_list ←  ; 2. for i=1; i ≤ num_low_items; i++ do 3. If one_lower_rule does not include itemi then 4. one_high_rule ← combination of one_lower_rule and itemi; 5. WRAi ← calculate the Weighted_Relative_Accuracy for one_high_rule; 6. accuracy_list ← accuracy_list WRAi ; 7. end if 8. end for 9. BEST ← one of high order rules having the highest WRA; 10. return BEST Số lương luật sinh ra có thể rất lớn, để việc phân lớp được hiệu quả, Ying Hwuang và cộng sự đã loại bỏ bớt những luật xấu với các thông tin nhiễu hoặc không quan trọng. 11
Thông thường, một thống kê mẫu  2 được xử dụng để kiểm tra nếu tồn tại một quan hệ tuyến tính mạnh giữa hai thuộc tính.  2 được tính như sau: (O  E )2 2  E Với O và E là tần số mong đợi và quan sát, được tính bằng công thức: Num _(a) xNum _(c) O  Num _(a, c) E Num _ total Ngoài ra, còn có độ đánh giá Support và Confidence được sử dụng để đánh giá luật có bị loại bỏ (pruned) hay không? Num _(a, c) Num _(a, c) Support  Confidence  Num _ total Num _(a) Giải thuật (5) là một giải thuật tìm ra một luật có bị loại bỏ hay không? Với  là ngưỡng giá trị đánh giá  2 , minS và minC là hai giá trị ngưỡng, được định nghĩa là giá trị nhỏ nhất của support và confidence. Giải thuật 5: pruning (rule) 1. flag ← true; 2. If chi-square statistics > α AND support_rule > minS AND Confidence_rule > minC then 3. flag ← false; 4. End if 5. return flag; 2.1.3. Phân lớp Để phân lớp cho tập dữ liệu, Ying Hwuang và cộng sự coi Rules bao gồm hai lớp: churn và non-churn. Hai mô hình dự đoán được xây dựng dựa trên tất cả các luật churn và tất cả các luật non-churn. Để đánh giá độ quan trọng của các luật, Ying Hwuang và cộng sử xếp hạng các luật trong mỗi mô hình dựa trên một số nguyên lý sau:  Nếu confidence_1 > confidence_2 thì luật rule_1 có độ ưu tiên cao hơn rule_2.  Nếu confidence_1= confedence_2 và support_1 > support_2 thì luật rule_1 có độ ưu tiên cao hơn rule_2. 12