Luận văn Thạc sĩ kỹ thuật: Phân loại hành vi khách hàng sử dụng dịch vụ di động dựa trên thuật toán K-Means

Chia sẻ: Nguyễn Thị Thu Trang | Ngày: | Loại File: PDF | Số trang:28

Thêm vào BST

Báo xấu

170
lượt xem 35
download

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

Đề tài phân loại hành vi khách hàng sử dụng dịch vụ di động dựa trên thuật toán k-means. Mục đích của đề tài: hướng đến phân loại hành vi khách hàng, tìm ra các nhóm khác hàng phổ biến, đang hoạt động trong mạng di động Mobifone. Mời các bạn tham khảo!

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ĩ kỹ thuật: Phân loại hành vi khách hàng sử dụng dịch vụ di động dựa trên thuật toán K-Means

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG ------------------------------------------------- LÊ MINH HẢI PHÂN LOẠI HÀNH VI KHÁCH HÀNG SỬ DỤNG DỊCH VỤ DI ĐỘNG DỰA TRÊN THUẬT TOÁN K-MEANS LUẬN VĂN THẠC SỸ KỸ THUẬT HÀ NỘI - 2013
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- LÊ MINH HẢI PHÂN LOẠI HÀNH VI KHÁCH HÀNG SỬ DỤNG DỊCH VỤ DI ĐỘNG DỰA TRÊN THUẬT TOÁN K-MEANS Chuyên ngành: Khoa học máy tính Mã số: 60.48.01 TÓM TẮT LUẬN VĂN THẠC SĨ HÀ NỘI -2013
1 Luận văn được hoàn thành tại: HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Người hướng dẫn khoa học: TS NGUYỄN MẠNH HÙNG Phản biện 1: ………………………………………………………………………… Phản biện 2: ………………………………………………………………………….. Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn thạc sĩ tại Học viện Công nghệ Bưu chính Viễn thông Vào lúc: ....... giờ ....... ngày ....... tháng ....... .. năm ............... Có thể tìm hiểu luận văn tại: - Thư viện của Học viện Công nghệ Bưu chính Viễn thông
2 MỞ ĐẦU 1. Lý do chọn đề tài Đối với một doanh nghiệp thông di động di động việc phát triển thuê bao để kiếm tìm lợi nhuận vào thời điểm hiện tại đã không còn đem lại hiệu quả. Thay vào đó là một phương án kinh doanh tiến đến phát triển chất lượng dịch vụ cung cấp thêm nhiều dịch vụ giá trị gia tăng. Tuy nhiên các dịch vụ truyền thống như thoại, nhắn tin vẫn có thể đem lại nguồn lợi nhuận cao hơn nếu kích thích được nhu cầu sử dụng của khách hàng. Lưu lượng cuộc gọi theo giờ 80 70 60 Tỷ lệ lưu lượng (%) 50 40 Nhóm B Nhóm A 30 20 10 0 0 2 4 6 8 10 12 14 16 18 20 22 Thông thường mỗi cá nhân tùy vào vị trí xã hội, điều kiện kinh tế mỗi vùng mà có nhu cầu sử dụng thoại và tin nhắn khác nhau. Tại một vùng cụ thể, có những thời điểm năng lực mạng vẫn còn khả năng phục vụ nhưng do không có nhu cầu nên toàn bộ tài nguyên hoạt động ở hiệu suất thấp. Đây là những thời điểm các nhà mạng cần tăng cường tận dụng. Giả sử một địa phương có 02 nhóm người có hành vi tương tự nhau được thể hiện bằng biểu đồ như trên, nhóm A thường thực hiện cuộc gọi vào buổi sáng, nhóm B thường thực hiện cuộc gọi vào giờ chiều và tối; ban đầu chúng ta chưa xác định được 02 nhóm này. Để phân tích hành vi sử dụng các dịch vụ cơ bản thì cần khai thác nguồn dữ liệu tổng đài MSC. Các dữ liệu CDR ghi lại lịch sử cuộc gọi tại một địa điểm cụ thể, đây là nguồn dữ liệu rất thích hợp tuy nhiên khối lượng dữ liệu này rất lớn nên cần có các kỹ thuật phân tích
3 thích hợp. Hiện nay các kỹ thuật khai phá dữ liệu đã đạt được nhiều thành tựu có thể hỗ trợ bài toán phân tích hành vi khách hàng như phân cụm dựa vào thuật toán k-means. Dựa vào thực trạng như trên kết hợp với các kỹ thuật phân cụm trong khai phá dữ liệu đã được phát triển để đưa ra đề tài “Phân loại hành vi khách hàng sử dụng dịch vụ di động dựa trên thuật toán k-means”. 1. Mục đích của đề tài: đề tài hướng đến phân loại hành vi khách hàng, tìm ra các nhóm khác hàng phổ biến, đang hoạt động trong mạng di động Mobifone; tiến đến đề xuất tích hợp kết quả vào hệ thống báo cáo số liệu sản xuất kinh doanh cho Tập đoàn VNPT.. 2. Đối tượng và phạm vi nghiên cứu: Việc nghiên cứu sẽ tập trung vào lý thuyết phân cụm dữ liệu theo thuật toán k-means, áp dụng vào phân cụm hành vi sử dụng dịch vụ thoại và nhắn tin của khách hàng VMS Mobifone. 3. Phương pháp nghiên cứu: Tìm hiểu các tài liệu liên quan đến các kỹ thuật phân cụm, tập trung vào thuật toán k-means. 4. Kết cấu của luận văn Luận văn gồm 3 chương Chương 1: Bài toán phân nhóm khách hàng dựa trên hành vi sử dụng dịch vụ dị động. Chương này luận văn trình bày nhu cầu phân tích số liệu di động để đưa ra được thông tin về thói quen sử dụng dịch vụ viễn thông, dịch vụ truyền thống thoại và nhắn tin, trên một địa bàn. Chương 2: Thuật toán k-means. Chương này luận văn trình bày một trong những thuật toán phân cụm k-means và đánh giá khả năng áp dụng đối với bài toán phân cụm hành vi khách hàng sử dụng dịch vụ viễn thông. Chương 3: Áp dụng thuật toán k-means vào phân cụm hành vi sử dụng dịch vụ thoại và nhắn tin. Chương này luận văn trình bày các bước xử lỷ dữ liệu, xây dựng các nguồn dữ liệu đầu vào, thực hiện phân cụm theo phương pháp k-means và cuối cũng sẽ đánh giá một số thông tin rút ra được từ kết quả sau khi phân cụm.
4 CHƯƠNG 1. BÀI TOÁN PHÂN NHÓM KHÁCH HÀNG DỰA TRÊN HÀNH VI SỬ DỤNG DỊCH VỤ DỊ ĐỘNG 1.1. Đặt vấn đề 1.1.1. Một số định nghĩa Định nghĩa tổng lượng sử dụng của mạng trong một khoảng thời gian ∑ (1)  t là khoảng thời gian xem xét.  Lt là tổng lượng sử dụng dịch vụ (là giây với dịch vụ thoại, số lượng tin nhắn đối với dịch vụ nhắn tin).  n là tổng số thuê bao trong vùng đang xem xét.  Cit là tổng lượng sử dụng của khách hàng C i trong khoảng thời gian xem xét t. ∑ (2)  m là số cuộc gọi của khách hàng i trong khoản thời gian t.  Di,j là thời lượng cuộc gọi của khách hàng i trong cuộc gọi thứ j trong khoảng thời gian t. Với dịch vụ tin nhắn giá trị này = 1 hay Cit = m. Khung thời gian có Lt nhỏ nhất là khoảng thời gian cần kích thích để các thuê bao sử dụng sử dụng nhiều hơn. Định nghĩa hành vi: Hành vi nói chung là một khái niệm rộng. Trong luận văn này, khái niệm hành vi dùng để chỉ hành động thực hiện dịch vụ của khách hàng dựa vào vùng nơi thuê bao thực hiện dịch vụ và thời điểm thực hiện dịch vụ. 1.1.2. Nhu cầu phân tích hành vi sử dụng dịch vụ di động Hiện tại hệ thống báo cáo số liệu kinh doanh được tập đoàn VNPT khai thác đang cung cấp dữ liệu dạng tổng hợp. Tuy nhiên câu hỏi chỉ ra tính chất của dữ liệu chưa được khai thác. Luận văn đề xuất việc phân tích dữ liệu lịch sử cuộc gọi của khách hàng để tìm ra các nhóm hành vi. Xem xét các nhóm hành vi có thể chỉ ra được tác động của nhóm này đối
5 với năng lực mạng tại một địa bàn cụ thể; từ đó trợ giúp việc thiết kế các gói khuyến mại để tận dụng năng lực mạng. 1.1.3. Các khía cạnh phục vụ phân tích hành vi Thời điểm thực hiện dịch vụ: là một thuộc tính của hành vi sử dụng dịch vụ của khách hàng, chỉ ra thời điểm khách hàng bắt đầu sử dụng dịch vụ gọi điện hoặc nhắn tin. Lượng sử dụng dịch vụ: trong một khung thời gian được chia theo thuộc tính thời điểm, tổng lượng thời gian đàm thoại hoặc số tin nhắn của một khách hàng là lượng sử dụng dịch vụ của khách hàng trong khung thời gian đó. Địa điểm phát sinh cuộc gọi: Một nhóm hành vi sẽ là đặc trưng về lượng sử dụng của các thuê bao trong nhóm trên mỗi khung giờ được xem xét trên một địa phương cụ thể. Địa điểm phát sinh cuộc gọi là vùng quản lý trạm phát sóng phục vụ cho khách hàng đó. Trong luận văn địa điểm được phân tích ở cấp tỉnh/thành phố. 1.2 Trình bày một số giải pháp cho bài toán 1.2.1 Các giải pháp theo thống kê thông thường Phương pháp tổng hợp số liệu phổ biến là sử dụng các lệnh thống kê, sử dụng truy vấn dữ liệu theo chuẩn SQL 2.0. Để tìm ra các nhóm và số lượng khách hàng thuộc các nhóm đó cần thực hiện hai bước:  Khảo sát thị trường tìm ra các đặc trưng về thời điểm gọi, lượng sử dụng điển hình.  Sử dụng các giá trị đặc trưng của từng nhóm, xây dựng lệnh thống kê. Việc khảo sát thường đem lại kết quả chính xác không cao và tốn nhiều thời gian. Do hành vi sử dụng dịch vụ biến đổi liên tục phụ thuộc vào các sự kiện kinh tế chính trị, vì vậy việc phân tích nhóm cần thực hiện nhiều lần tại các thời điểm trong năm và trong nhiều năm; điều này khối lượng cần khảo sát sẽ chiếm nhiều chi phí. Phương pháp thống kê truyền thống tỏ ra không thích hợp để giải quyết bài toán. 1.2.2 Giải pháp ứng dụng các kỹ thuật khai phá dữ liệu Khai phá dữ liệu là vấn đề nhận được nhiều sự quan tâm. Nhu cầu khai phá dự liệu là nhu cầu tiếp theo sau khi một doanh nghiệp đã tổ chức được hệ thống cơ sở dữ liệu.
6 Hình 1. 1 Sự phát triển của hệ thống cơ sở dữ liệu (dựa trên [2, tr.2]) Hệ quản trị cơ sở dữ liệu quan hệ được xuất hiện từ những năm 1970 đến đầu 1980, đại diện là các tên tuổi lớn như Oracle, DB2, MS SQL, MySQL. Đến nay, hệ quản trị cở sở dữ liệu quan hệ có nhiều cải tiến mạnh mẽ và được ứng dụng rất rộng rãi. Các doanh nghiệp đã tích lũy các số liệu kinh doanh qua thời gian dài nhờ sử dụng cở sở dữ liệu, tuy nhiên các mẫu báo cáo kinh doanh thông thường vẫn chưa khai thác hết thông tin mà các dữ liệu đó đang cất giữ. Chính vì vậy các kỹ thuật khai phá dữ liệu được nghiên cứu và ứng dụng. Các kiến thức tìm được nhờ ưng dụng kỹ thuật khai phá dữ liệu gồm: Nhận biết và phân biệt các lớp dữ liệu: Nhận biết đặc tính dữ liệu là việc tìm ra một tổng kết về các đặc điểm chung hoặc các tính năng của một lớp dữ liệu mục tiêu. Phân biệt các lớp dữ liệu là việc so sánh các đặc tính dữ liệu của một lớp dữ liệu với một lớp khác hoặc một tập các lớp khác đã biết. Khai thác mẫu phổ biến: Mẫu phổ biến là các mẫu dữ liệu hay xuất hiện trong tập dữ liệu đang xét. Mẫu thường xuyên bao gồm các kiểu như tập phổ biến. các mẫu tuần tự.
7 Phân loại và dự báo: quá trình của việc tìm kiếm một mô hình (hoặc chức năng) mô tả và phân biệt các lớp dữ liệu hoặc các khái niệm, sử dụng các mô hình tìm được để dự đoán lớp của các đối tượng mà chưa gán được lớp. Phân cụm dữ liệu: Khác với phân loại và dự báo dữ liệu, phân cụm dữ liệu là phân tích dữ liệu mà không tham khảo một lớp dữ liệu biết trước nào. Với một nguồn dữ liệu biểu diễn một tập các đối tượng, phân cụm dữ liệu sẽ nhóm các đối tượng thành các nhóm dựa trên sự tối đa hóa sự sai khác các phần tử ở các nhóm khác nhau và tối thiểu hóa sự sai khác giữa các phần tử cùng nhóm. Phân tích bất thường: Một cơ sở dữ liệu có thể chứa các đối tượng dữ liệu mà không tuân thủ với các hành vi chung, mang các đặc điểm về dữ liệu khác nhiều so với đại bộ phận các đối tượng còn lại. Các đối tượng dữ liệu đó có thể coi là dữ liệu bất thường. Đánh giá dữ liệu theo thời gian: tìm ra các mô hình mô tả xu hướng của dữ liệu thay đổi theo thời gian. 1.2.3 Phân cụm dữ liệu Quá trình nhóm một tập hợp các đối tượng vật lý hay trừu tượng thành các lớp đối tượng tương tự được gọi là phân cụm. Một cụm là một tập các đối tượng dữ liệu tương tự và không giống các đối tượng trong các cụm khác. Hình 1. 2 Hình ảnh phân cụm các điểm trong mặt phẳng hai chiều [2, tr.64]
8 Phân cụm dữ liệu thực hiện gom nhóm dữ liệu theo hướng ngược lại. Tập các dữ liệu được gom thành các nhóm dựa trên sự tương tự nhau giữa các dữ liệu, và sau đó gán nhãn cho các nhóm. Số lượng các nhóm có thể được cài đặt trước và phân cụm dữ liệu trở nên thích nghi với sự biến đổi dữ liệu tốt hơn phân loại dữ liệu. Vấn đề xác định độ tương đồng của dữ liệu: Khi dữ liệu cần phân cụm có nhiều thuộc tính và các thuộc tính rất đa dạng nhiều kiểu. Trong thực tế việc xem xét phân cụm trong khi dữ liệu mang nhiều thuộc tính và nhiều kiểu thuộc tính là một vần đề cần giải quyết. Ngoài ra nhiều thuật toán xác định sự tương đồng của đối tượng dựa trên các khoảng cách Euclidean hoặc Manhattan thì cho ra các phần tử tương đồng tạo thành một cụm dạng cầu. Tuy nhiên cụm có thể có hình dạng bất kỳ vì vậy cần phát triển thuật toán tính độ tương đồng với hình dạng tuỳ ý. Vấn đề xử lý nhiễu trong phân cụm dữ liệu: Hầu hết các cơ sở dữ liệu thực tế có chứa các dữ liệu cá biệt hoặc mất tích, không rõ, hoặc dữ liệu sai. Một số thuật toán phân cụm nhạy cảm với các dữ liệu đó và có thể dẫn đến kết quả phân cụm có chất lượng kém. Tập dữ liệu gốc được loại bỏ các thành phần nhiễu sẽ trở thành đầu vào tốt cho giai đoại phân cụm dữ liệu. 1.3 Kết luận Trong chương 1, luận văn đã trình bày các vấn đề sau:  Nêu lên bài toán phân tích hành vi sử dụng dịch vụ khách hàng, để hỗ trợ việc xây dựng chính sách phát triển dịch vụ tận dụng tốt tài nguyên của mạng lưới.  Nêu các mặt khó khăn trong việc giải quyết bài toán dựa trên khảo sát thị trường. Đề xuất sử dụng kỹ thuật khai phá dữ liệu, cụ thể là phương pháp phân cụm dữ liệu, để phân tích các nhóm hành vi Chương tiếp theo luận văn trình bày kỹ thuật phân cụm k-means, bên cạnh đó đánh giá khả năng áp dụng thuật toán vào bài toán phân cụm hành vi.
9 CHƯƠNG 2. THUẬT TOÁN K-MEANS 2.1 Giới thiệu thuật toán k-means Thuật ngữ "k-means" lần đầu tiên được sử dụng bởi James MacQueen vào năm 1967, dựa trên ý tưởng trước đó của Hugo Steinhaus vào năm 1957. Tuy nhiên thuật toán hoản thiện được đề xuất lần đầu tiên bởi Stuart Lloyd vào năm 1957 mặc dù nó đã không được công bố cho đến năm 1982. Năm 1965, EWForgy công bố về một phương pháp về cơ bản tương tự với thuật toán của Stuart Lloyd, vì vậy đôi khi thuật toán k-means cũng được gọi là Lloyd-Forgy. Một phiên bản cải tiến đã được đề xuất và xuất bản tại Fortran bởi Hartigan và Wong năm 1975/1979 [7]. Có nhiều loại phương pháp phân cụm dữ liệu, k-means là một trong số những thuật toán phân cụm dựa trên phương pháp phân vùng. Phương pháp phân vùng được mô tả như sau : Cho một cơ sở dữ liệu có n đối tượng hoặc bộ dữ liệu, một phương pháp phân vùng xây dựng nên k vùng dữ liệu, nơi mà mỗi phân vùng đại diện cho một cụm và . Có nghĩa là, nó phân loại các dữ liệu vào k nhóm và cần đáp ứng các yêu cầu sau đây:  Mỗi nhóm phải có ít nhất một đối tượng.  Mỗi đối tượng phải thuộc về một nhóm. Với k cho trước, chính là số lượng các phân vùng cần xây dựng, thuật toán tạo ra k phân vùng đầu tiên. Sau đó sử dụng một kỹ thuật xác định nhóm cho các đối tượng lặp đi lặp lại, các đối tượng được di chuyển từ nhóm này sang nhóm khác đến khi đạt được tối ưu. Các tiêu chí chung của một phân vùng tốt là các đối tượng trong cùng một cụm có liên quan đến nhau hay khá tương đồng nhau, trong khi các đối tượng khác nhau thì khác nhau. 2.2 Cài đặt thuật toán 2.2.1 Dữ liệu đầu vào Thuật toán k-means yêu cầu hai nguồn dữ liệu đầu vào  k : số lượng các cụm mong muốn phân tách.  D : Tập dữ liệu chứa N phần tử cần phân cụm.
10 K cụm và vị trí ban đầu: Chọn k là một vấn đề trong phân cụm, và hiện chưa có sự thống nhất về giải pháp. Việc chọn k có thể ảnh hưởng lớn đến kết quả phân cụm. Chọn thêm hoặc số lượng hay việc xác định các vị trí ban đầu của k nhiều trưởng hợp sẽ cho ra kết quả khác nhau. Ví dụ phân cụm nhóm các điểm trong trong hình vuông 1x1. Hình 2. 1 Ví dụ việc chọn k tốt [6, tr.21] Hình 2. 2 Các kết quả sau khi thay đổi số cụm khởi tạo (dựa trên [6,tr.21])
11 Trên hình minh họa thể hiện khi k tăng và không được khởi tạo tốt cụm thứ năm có thể gần với một trong các cụm ban đầu; đây là trường hợp mong muốn. Khi phân cụm mà có những cụm các phần tử trong nó có độ sai khác không lớp thì không đạt được kỳ vọng của thuật toán phân cụm. 2.2.2 Dữ liệu đầu ra của thuật toán Thuật toán phân cụm yêu cầu đầu ra là các cụm chứa các phần tử mang giá trị gần nhau nhất. Cụm có thể được mô tả dưới nhiều cách hai cách  Cách thứ nhất: mô tả giá trị trung tâm cùng với số thành viên của cụm đó.  Cách thứ hai: liệt kê danh sách các phần tử trong từng cụm. 2.2.3 Thuật toán phân cụm Đầu vào thuật toán:  k: số lượng các cụm,  D: một tập dữ liệu chứa các đối tượng n. Đầu ra thuật toán:  Một tập hợp các k cụm. Phương pháp [2]: (1) tùy ý lựa chọn k đối tượng từ D là trung tâm cụm ban đầu; (2) lặp lại (3) Chỉ định (hoặc chỉ định lại) cho mỗi đối tượng một cụm mà đối tượng là tương tự nhất (gần nhất), dựa trên giá trị trung bình của các đối tượng trong cụm; (4) Cập nhật thông số cụm, nghĩa là, tính toán giá trị trung bình cho từng cụm; (5) cho đến khi không có cụm nào thay đổi;
12 Hình 2. 3 Mô tả thuật toán k-means [2, tr.403] Trong thuật toán phương pháp tính khoảng cách gần nhất cho mỗi khách hàng dựa vào công thức Euclidean, dựa trên [2,tr.389], như sau: √ Trong đó Pk là giá trị của các điểm trung tâm. Do các tham số để đánh giá khoảng cách có cùng thứ nguyên và bình đẳng vì vậy có thể sử dụng công thức Euclidean đối với các tham số. Trong nhiều trường hợp các tham số không cùng thứ nguyên ,ví dụ thuộc tính “giới tính” và “độ tuổi” của người, nên cần thiết phải chuyển đổi về cùng một đơn vị. 2.3 Đánh giá thuật toán 2.3.1 Đánh giá kết quả Với kết quả đầu ra dạng mô tả điểm trung tâm với các thuộc tính có giá trị trung bình của các phần tử trong nhóm, thuật toán đưa ra được kết quả phù hợp với nhu cầu phân tích hành vi khách hàng và các hành vi tương tự nhau được nhóm lại một vùng. Đánh giá dữ liệu đầu ra của thuật toán k-means đối với bài toán phân cụm hành vi sử dụng dịch vụ của khách hàng, khi các cụm hành vì được xác định, việc phân tích sâu hơn về nhóm đó là cần thiết. 2.3.2 Đánh giá khả năng triển khai Thuật toán k-means có độ phức tạp thuật toán tính theo công thức sau [2,tr.403].
13  là số phần tử trong tập phân cụm.  là số cụm cần phân chia  là số lần tái lặp xác định các phần tử trong mỗi cụm. Thông thường và nhỏ hơn rất nhiều so với , tuy phương pháp phân cụm dựa trên phương pháp phân cấp có độ phức tạp thuật toán tuy nhiên phương pháp này không sử dụng với các nhóm có hình dạng cầu vì không dùng công thức tính toán khoảng cách. Các tiêu chí đánh giá và xếp loại một hành vi sử dụng ba tiêu chí cùng ý nghĩa, vì vậy cách tính khoảng cách áp dụng trong thuật toán k-means đưa ra các nhóm hình cầu tỏ ra thích hợp. Bên cạnh đó, việc phân cụm được lặp lại hàng ngày; việc tái sử dụng kết quả phân cụm cũng giụp giảm số lần tái lặp , từ đó giảm chi phí thực hiện. Thuật toán k-means có một nhược điểm là có khả năng chống nhiễu kém; nếu trong nhóm có một lượng các giá trị nhiễu thì giá trị chung bình của nhóm sẽ bị thay đổi đáng kể từ đó dẫn đến kết nạp sai lầm tại những vòng lặp xử lý sau. Tuy nhiên vẫn có thể áp dụng một số phương pháp tiền xử lý dữ liệu đầu vào để giảm sự ảnh hưởng nhiễu. 2.4 Kết luận Trong chương 2, luận văn đã trình bày các vấn đề :  Giới thiệu thuật toán k-means.  Cài đặt thuật toán k-means  Đánh giá sơ bộ kết quả và khả năng triển khai thuật toán k-means vào công việc phân cụm hành vi sử dụng dịch vụ viễn thông. Chương tiếp theo luận văn trình bày quá trình áp dụng thuật toán k-means vào bài toán phân cụm hành vi sử dụng khách hàng của mạng di động VMS Mobifone.
14 CHƯƠNG 3. ÁP DỤNG THUẬT TOÁN K-MEANS VÀO PHÂN CỤM HÀNH VI SỬ DỤNG DỊCH VỤ THOẠI VÀ NHẮN TIN 3.1 Bài toán phân cụm hành vi Mục tiêu bài toán là tìm ra các nhóm thuê bao, trong mỗi nhóm chứa các thuê bao có cùng hành vi sử dụng dịch vụ thoại hoặc tin nhắn tại một địa bàn. Một hành vi được xác định bởi tỷ lệ tương quan lượng sử dụng dịch vụ (thời gian đàm thoại hoặc số lượng tin nhắn) trong các khung thời gian trong ngày. Cụ thể khung thời gian được chia thành:  S là tổng lượng sử dụng của số máy (tính bằng giây đối với dịch vụ thoại, tính bằng số lượng tin nhắn đối với dịch vụ nhắn) tin tính từ 4h sáng đến 11h 59 phút.  C là tổng lượng sử dụng của số máy tính từ 12h đến 19h 59 phút.  T là tổng lượng sử dụng của số máy tính 20h đến 23h59 và 0h đến 4h sáng. Gọi M là giá trị lớn nhất về lượng sử dụng của thuê bao trong một khung thời gian. Tỷ lệ tương quan của lượng sử dụng trong ba khung giờ được xác định như sau:  ; là giá trị tương quan lượng sử dụng buổi sáng với lượng sử dụng lớn nhất.  ; là giá trị tương quan lượng sử dụng buổi trưa với lượng sử dụng lớn nhất.  ; là giá trị tương quan lượng sử dụng buổi tối với lượng sử dụng lớn nhất. Bảng 3. 1 Tổng lưu lượng và tỷ lệ lưu lượng của thuê bao theo thời gian S (giây) C (giây) T (giây) PS PC PT 100 1000 50 0.1 1 0.05 Luận văn đề xuất một số mẫu kết quả cần đạt được như sau: Tiêu chí : đánh giá nhu cầu sử dụng dịch vụ của khách hàng theo khung thời gian. Bảng 3. 2 Định dạng mẫu đánh giá nhu cầu sử dụng dịch vụ của khách hàng theo thời gian Ngày /Tuần Địa Tổng thời gian gọi Tổng tin nhắn gửi /Tháng /Năm phương buổi buổi buổi buổi buổi buổi báo cáo (tỉnh/ thành sáng chiều tối sáng chiều tối phố)
15 Tiêu chí : đánh giá nhóm hành vi sử dụng dịch vụ thoại của khách hàng theo ngày của một địa phương. Bảng 3. 3 Định dạng mẫu đánh giá nhóm hành vi sử dụng dịch vụ thoại của khách hàng theo ngày của một địa phương Số thứ Số lượng Thời gian gọi trung bình Tổng thời gian gọi tự cụm thuê bao Buổi Buổi Buổi tối Buổi Buổi Buổi tối sáng chiều sáng chiều Tiêu chí : đánh giá nhóm hành vi sử dụng dịch vụ tin nhắn của khách hàng theo ngày của một địa phương. Bảng 3. 4 Định dạng mẫu đánh giá nhóm hành vi sử dụng dịch vụ tin nhắn của khách hàng theo ngày của một địa phương Số thứ Số lượng Số lượng tin nhắn gửi trung Tổng số tin nhắn gửi tự cụm thuê bao bình Buổi Buổi Buổi tối Buổi Buổi Buổi tối sáng chiều sáng chiều 3.2 Khảo sát nguồn dữ liệu lịch sử cuộc gọi 3.2.1 Khuôn dạng bản tin cuộc gọi, tin nhắn Nguồn dữ liệu ban đầu là các bản ghi được ghi bởi hệ thống tổng đài chuyển mạch di động (MSC – mobile switching center). VMS Mobifone quy định một chuẩn giản lược và đang khai thác dữ liệu lịch sử cuộc gọi theo chuẩn đo. Cấu trúc dữ liệu được áp dụng cho tất cả loại tổng đài và sử kiện và gồm hơn 43 trường. Dựa vào chuẩn dữ liệu VMS đang khai thác, luận văn xác định các thuộc tính có thể khai thác để phục vụ bài toán gồm: Thuộc tính “calling isdn” và “called_isdn” : sử dụng làm khóa xác định thuê bao. Thuộc tính này ghi lại số điện thoại mà tổng đài phục vụ. số máy này theo nguyên tắc thuộc về các thuê bao của Mobifone và các thuê bao sử dụng dịch vụ roaming qua mạng Mobifone. Đối với bản ghi cuộc gọi đi calling_isdn chứa thuê bao thực hiện quay số, đối với bản ghi cuộc gọi đến thì calling_isdn mang số máy nhận cuộc gọi hoặc tin nhắn. Thuộc
16 tính calling_isdn lại có giá trị để phân biệt khách hàng vì vậy calling_isdn có thể làm mã xác nhận phần tử trong thuật toán phân cụm k-means. Thuộc tính “call type”: nhận biết loại dịch vụ. Gồm các giá trị : OG: cuộc gọi đi. Số máy calling_isdn gọi cho số máy called_isdn; IC: cuộc gọi đến. Số máy calling_isdn nhận cuộc gọi từ số called_isdn; SMO: tin nhắn đi. Số máy calling_isdn nhắn tin cho số máy called_isdn; SMT: tin nhắn đến. Số máy calling_isdn nhận tin nhắn của called_isdn. Để xác định hành vi khách hàng, các sự kiện chủ động được quan tâm vì vậy chỉ khai thác sự kiện cuộc gọi đi (OG) và tin nhắn đi (SMO). Thuộc tính “call sta time” : nhận biết thời điểm cuộc gọi. Thời điểm bắt đầu cuộc gọi hay thời điểm tin nhắn. Định dạng dữ liệu là “DD/MM/YYYY HH:MI:SS” (Ngày/tháng/năm giờ/phút/giây). Thuộc tính “duration” : nhận biết lượng sử dụng của sự kiện. Đối với dịch vụ thoại thời lượng gọi chỉ ra số giây khách hàng thực hiện một cuộc gọi. Đối với dịch vụ tin nhắn thuộc tính này không có giá trị, lúc này có thể đánh giá hành vi nhắn tin bằng tổng số tin nhắn mà khách hàng gửi trong một khung thời gian. Thuộc tính “cell id” : nhận biết địa điểm cuộc gọi được khởi tạo. Mỗi lần tổng đài thực hiện khởi tạo dịch vụ thì đều ghi lại tọa độ nơi khách hàng bắt đầu sử dụng dịch vụ. Tọa độ “cell id” chính là mã các trạm phát sóng di động quy hoạch theo mạng tổ ong. Với cấp độ của bài toán hiện tại, luận văn chỉ khai thác thông tin đến địa bàn tỉnh, từ đó cung cấp cái nhìn tổng quát các nhóm hành vi trên toàn tỉnh. Nguồn dữ liệu xác định địa bàn của dựa vào cell_id có dạng sau: Bảng 3. 5 Cấu trúc dữ liệu quy hoạch trạm BTS Tên cột Dạng dữ liệu Ghi chú CELL_ID String Lưu mã trạm phát sóng DISTRICT String Mã huyện nơi đặt trạm PROVINCE String Mã tỉnh/thành phố nơi đặt trạm REGION String Mã trung tâm, nơi quản lý trạm.
17 3.2.2 Khối lượng dữ liệu cần xử lý VMS Mobifone có một hệ thống tổng đài MSC gồm 25 tổng đài. Trung bình một ngày cần xử lý hơn 30000 file và dung lượng trung bình 57GB. Theo thống kê, mỗi có khoảng 10 triệu thuê mobifone thực hiện 39 triệu cuộc gọi và thực hiện gửi 52 triệu tin nhắn tinh trên toàn mạng. Quá trình tiền xử lý dữ liệu cho đầu vào thuật toán k-means cần phải tổng hợp lượng sử dụng dịch vụ từ hơn 90 triệu bản ghi để tạo thành một nguồn 10 triệu bản ghi trong đó mỗi bản ghi lưu số máy và các đặc trưng sử dụng của số máy đó trong ngày. 3.3 Tiền xử lý dữ liệu đầu vào 3.3.1 Định dạng tập dữ liệu phần tử đầu vào thuật toán k-means Dựa vào cách mô tả hành vi sử dụng dịch vụ của một khách hàng, có thể xác định định dạng đầu ra kiểu liệt kê phần tử (định dạng đầu vào thuật toán k-means) như sau: Bảng 3. 6 Cấu trúc dữ liệu đầu ra thuật toán k-means dạng liệt kê phần tử Số thứ tự Tên cột Ý nghĩa 1 Phone Number Số điện thoại của khách hàng 2 S Tổng số thời lượng sử dụng buổi sáng 3 C Tổng số thời lượng sử dụng buổi chiều 4 T Tổng số thời lượng sử dụng buổi tối 5 Ps Tỷ lệ thời lượng sử dụng buổi sáng so với thời lượng lớn nhất 6 Pc Tỷ lệ thời lượng sử dụng buổi chiều so với thời lượng lớn nhất 7 Pt Tỷ lệ thời lượng sử dụng buổi tối so với thời lượng lớn nhất Với dữ liệu định dạng file đầu ra liệt kê các điểm trung tâm có dạng:
18 Bảng 3. 7 Cấu trúc dữ liệu đầu ra thuật toán k-means dạng mô tả điểm trung tâm Số thứ tự Tên cột Ý nghĩa 1 Round Lần xử lý 2 Count Số phần tử trong nhóm 3 Cluster Chỉ số cụm 4 S Trung bình tổng số thời lượng sử dụng buổi sáng 5 C Trung bình tổng số thời lượng sử dụng buổi chiều 6 T Trung bình tổng số thời lượng sử dụng buổi tối 7 PS Tỷ lệ thời lượng sử dụng buổi sáng so với thời lượng lớn nhất 8 PC Tỷ lệ thời lượng sử dụng buổi chiều so với thời lượng lớn nhất 9 PT Tỷ lệ thời lượng sử dụng buổi tối so với thời lượng lớn nhất 3.3.2 Phương pháp xác định k điểm khởi tạo ban đầu Mỗi một khách hàng cần được tổng hợp thành dữ liệu mô tả được tương quan lượng sử dụng giữa các buổi trong ngày tính theo tỷ lệ phần trăm so với giờ cao điểm nhất. Tương quan sử dụng dịch vụ giữa các khung giờ được định thành ba mức : 0; 0.5 và 1. Các giá trị khung giờ có thể mang một trong ba giá trị; tuy nhiên có một ràng buộc là trong ba giá trị phải bằng 1. Như vậy danh sách các điểm k khởi tạo gồm. Bảng 3. 8 Danh sách k điểm khởi tạo sau khi điều chỉnh Nhóm PS PC PT 0 0 0 1 1 0 0.5 1 2 0 1 0 3 0 1 0.5 4 0 1 1 5 0.5 0 1 6 0.5 0.5 1 7 0.5 1 0 8 0.5 1 0.5 9 0.5 1 1 10 1 0 0 11 1 0 0.5 12 1 0 1 13 1 0.5 0 14 1 0.5 0.5 15 1 0.5 1 16 1 1 0 17 1 1 0.5 18 1 1 1