Tóm tắt luận văn Thạc sĩ: Ứng dụng khai phá dữ liệu tìm hiểu thông tin khách hàng Viễn Thông

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

Thêm vào BST

Báo xấu

161
lượt xem 31
download

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

Khai phá dữ liệu là một tiến trình khai phá tự động những tri thức tiềm ẩn trong cơ sở dữ liệu, cụ thể hơn là tiến trình lọc sản sinh những tri thức hoặc mẫu tiềm ẩn chứa thông tin hữu ích từ số lượng dữ liệu lớn. Để nắm rõ hơn mời các bạn tham khảo tài liệu.

Chủ đề:

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

Lưu

Nội dung Text: Tóm tắt luận văn Thạc sĩ: Ứng dụng khai phá dữ liệu tìm hiểu thông tin khách hàng Viễn Thông

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- NGUYỄN LÊ PHƯƠNG ỨNG DỤNG KHAI PHÁ DỮ LIỆU TÌM HIỂU THÔNG TIN KHÁCH HÀNG VIỄN THÔNG Chuyên ngành: Khoa học máy tính Mã số: 60.48.01 Người hướng dẫn khoa học: TS VŨ VĂN THỎA TÓM TẮT LUẬN VĂN THẠC SĨ HÀ NỘI - 2012
1 MỞ ĐẦU Khai phá dữ liệu (KPDL) là một tiến trình khai phá tự động những tri thức tiềm ẩn trong cơ sở dữ liệu, cụ thể hơn là tiến trình lọc sản sinh những tri thức hoặc mẫu tiềm ẩn chứa thông tin hữu ích từ số lượng dữ liệu lớn. KPDL là tiến trình khái quát các sự kiện rời rạc trong dữ liệu thành các tri thức mang tính quy luật, hỗ trợ tích cực cho việc đưa ra các quyết định. Khi việc lưu trữ dữ liệu không còn quá đắt đỏ, phần cứng có cấu hình cao, khối lượng dữ liệu khổng lồ, và có nhiều công cụ hỗ trợ cho việc phát triển khai phá dữ liệu, tất cả đã giúp KDPL trở thành lĩnh vực mang tính thời sự trong ngành công nghệ thông tin. Ngày nay, các công ty coi khách hàng là trung tâm. Họ cần có một môi trường cho phép hiểu rõ những yêu cầu của khách hàng. Ngành công nghiệp viễn thông lưu trữ một khối lượng dữ liệu khổng lồ, bao gồm: chi tiết cuộc gọi, thông tin cảnh báo trình trạng của hệ thống mạng viễn thông và thông tin dữ liệu về khách hàng. Các công ty viễn thông nắm bắt rất rõ các thông tin về khách hàng của mình. Họ biết những khách hàng của họ là ai, dễ dàng theo dõi những hành vi, thói quen của khách hàng. Một tập các hoạt động cho thực hiện công việc để xác định, điều kiện, bổ sung, phát triển, giữ lại những khách hàng trung thành và lợi nhuận bằng cách cung cấp sản phẩm hoặc dịch vụ, tới đúng khách hàng, đúng kênh, đúng thời điểm và giá thành. Khi đó một sản phẩm đúng hoặc dịch vụ đúng nghĩa là chỉ có sản phẩm hoặc dịch vụ đó phù hợp với cái khách hàng đang cần được xem xét. Ứng dụng kỹ thuật KPDL để phát hiện các quy luật ẩn chứa trong khối dữ liệu khổng lồ đó và đưa ra những dự đoán, quyết định đúng, sẽ mang lại cho các doanh nghiệp viễn thông nhiều cơ hội để phát triển các ứng dụng mang tính thực tiễn cao. Lý do cho việc ứng dụng KPDL cho công việc chăm sóc khách hàng trong thị trường viễn thông:  Thị trường cạnh tranh: sau nhiều năm là thị trường độc quyền, thị trường viễn thông ngày nay trở nên rất cạnh tranh. Khi thị trường là độc quyền thì hầu như không có biến động, nhưng khi thị trường cạnh tranh quyết liệt thì mọi thứ sẽ thay đổi liên tục. Khách hàng có thể chuyển đổi nhà
2 cung cấp dễ dàng, vì có rất nhiều sự lựa chọn. Vì lý do đó, những công ty viễn thông cần ứng dụng giải pháp KPDL để đạt những lợi thế cạnh tranh. Bằng cách hiểu những hành vi và thói quen của khách hàng, những công ty viễn thông sẽ đưa ra những chiến lược quảng bá hiệu quả để đưa ra những sản phẩm mà khách hàng yêu thích, phát triển khách hàng trung thành, và tăng lợi ích cho khách hàng.  Tốc độ phát triển thuê bao: số lượng thuê bao đề cập đến doanh thu hàng năm hoặc hàng tháng dựa trên cơ sở khách hàng. Việc canh tranh dẫn đến tỉ lệ phát triển thuê bao cao. Ban đầu, việc tăng trưởng trong thị trường viễn thông tăng theo cấp số nhân, do có rất nhiều khách hàng mới, tốc độ phát triển thuê bao không phải là vấn đề. Khi thị trường trở nên bão hòa, tốc độ phát triển thuê bao giảm. Việc bão hòa của các thuê bao và sự cạnh tranh ngày càng gay gắt dẫn đến việc những công ty viễn thông sẽ phải hướng tới vào những khách hàng đã có và tìm cách giữ họ lại. KPDLcó thể dùng trong việc phân tích tốc độ phát triển thuê bao để dự đoán dựa trên dữ liệu cụ thể là khách hàng sẽ không hoặc vẫn dùng sản phẩm của công ty và tại sao.  Bộ dữ liệu đồ sộ: các công ty viễn thông có một khối lượng dữ liệu đồ sộ. Khi những sản phẩm chính của các công ty được sử dụng, mỗi khách hàng đã tạo ra hàng trăm giao dịch trên một ngày. Một bản ghi cuộc gọi được lưu trữ trong cơ sở dữ liệu và nó là một nguồn dữ liệu rất lớn. Các công ty viễn thông cũng lưu trữ dữ liệu khách hàng, miêu tả khách hàng, dữ liệu mạng, và miêu tả họ sử dụng những dịch vụ nào. Luận văn: “Ứng dụng khai phá dữ liệu để tìm hiểu thông tin khách hàng viễn thông” nhằm góp phần nghiên cứu các mục tiêu nêu ra ở trên. Luận văn gồm các chương sau: Chương 1: Tổng quan về khai phá dữ liệu Chương 2: Khai phá dữ liệu bằng cây quyết định Chương 3: Xây dựng hệ thống tìm hiểu thông tin khách hàng
3 Chương 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 1.1 Tìm hiểu khai phá dữ liệu Sự phát triển của công nghệ phần cứng máy tính trong thời gian qua đã dẫn đến nguồn cung cấp các phương tiện lưu trữ dữ liệu tốt với giá cả phải chăng. Song song với điều đó, những tiến bộ trong quá trình thu thập đã dẫn tới sự tăng trưởng với số lượng lớn của dữ liệu. Công cụ KPDL thực thi việc phân tích dữ liệu và khám phá ra những mẫu quan trọng bị ẩn giấu. Việc mở rộng giữa dữ liệu và thông tin được gọi là công cụ phát triển khai thác hệ thống - công cụ khai phá dữ liệu. 1.1.1 Mục tiêu, nguồn gốc của khai phá dữ liệu KPDL là quá trình tìm kiếm các mẫu mới, những thông tin tiềm ẩn mang tính dự đoán trong các khối dữ liệu lớn. Những công cụ KPDL có thể phát hiện những xu hướng trong tương lai, các tri thức mà KPDL giúp doanh nghiệp sẽ đưa ra các quyết định kịp thời. Với ưu điểm trên, KPDL đã chứng tỏ được tính hữu dụng của nó trong môi trường kinh doanh đầy tính cạnh tranh và được ứng dụng rộng rãi trong các lĩnh vực thương mại, tài chính, y học, giáo dục, viễn thông..v.v. Hình 1.1:Nguồn gốc của khai phá dữ liệu Khai phá dữ liệu liên quan chặt chẽ đến những lĩnh vực sau: thống kê, máy học, cơ sở dữ liệu.  Thống kê  Trí tuệ nhân tạo(Artificial Intelligence - AI)  Hệ thống CSDL
4 1.1.2 Lý do khai phá dữ liệu Dựa trên thực tế, trên một khía cạnh nào đó, là đang tồn tại một lượng dữ liệu hệ thống khổng lồ mà chưa được khám phá một cách cụ thể. Nghĩa là đang có rất nhiều thông tin “ẩn giấu” và đã nằm ngoài khả năng phát hiện ra bởi những phương thức truyền thống và dựa trên khả năng phân tích của con người.Sự cần thiết của “khai phá” dữ liệu có thể miêu tả bằng sự cần thiết trong lĩnh vực cuộc sống thực:  Kinh tế, tài chính  Chăm sóc sức khỏe  Nghiên cứu khoa học Vậy, KPDL là gì? Tuy nhiên rất khó khăn để đưa ra một định nghĩa duy nhất mà phản ánh toàn sự kiện của hiện tượng. Vì thế, với từng cách tiếp cận khác nhau sẽ có những cái nhìn khác nhau về KPDL:  Là việc tìm kiếm tự động những mẫu trong CSDL khổng lồ, sử dụng công nghệ tính toán từ thống kê, học máy và nhận biết mẫu;  Là việc khai thác sự có ích của thông tin ẩn, mà trước đó chưa biết và có khả năng thông tin là hữu ích từ dữ liệu;  Kỹ thuật tách thông tin hữu dụng từ một tập dữ liệu lớn hoặc CSDL;  Việc thăm dò tự động hoặc bán tự động và phân tích một lượng lớn của dữ liệu, nhằm phát hiện những mô hình có ý nghĩa;  Tiến trình tự động khám phá thông tin, việc xác định mô hình và mối quan hệ ẩn giấu trong dữ liệu. Tóm lại, KPDL là quá trình phân tích của một tập dữ liệu quan sát (thường là rất lớn) để tìm ra những mối quan hệ ẩn giấu và tổng kết dữ liệu theo nhiều cách nhằm dễ hiểu và dễ sử dụng cho người sở hữu dữ liệu đó. 1.2 Quá trình khai phá dữ liệu Nói một cách đơn giản, KPDL liên quan đến việc “tách” hoặc “dò” tri thức từ một lượng lớn của dữ liệu, khai phá tri thức từ dữ liệu, tách tri thức, phân tích mẫu/dữ liệu....
5 Quá trình khai phá gồm những bước tuần tự như sau: 1. Làm sạch dữ liệu (loại bỏ những dữ liệu thừa và không có thông tin) 2. Tích hợp dữ liệu (khi nhiều nguồn dữ liệu được kết hợp) 3. Lựa chọn dữ liệu (lựa chọn những dữ liệu thích hợp cho việc phân tích được thực hiện lấy từ CSDL) 4. Chuyển đổi dữ liệu (nơi dữ liệu được chuyển đổi hoặc hợp nhất thành một thể thích hợp phù hợp cho việc khai phá bằng cách thực hiện các hoạt động tóm tắt hoặc tích hợp) 5. Khai phá dữ liệu (là tiến trình quan trọng với những phương thức thông minh được áp dụng cho việc tách những mẫu dữ liệu) 6. Định giá mẫu (Xác định những mẫu thực sự có ích miêu tả dữ liệu dựa trên một vài đơn vị đo lường sự có ích) 7. Miêu tả tri thức (khi việc miêu tả mô hình và dữ liệu thu được được sử dụng trong việc khai phá tri thức cho người dùng) Kiến trúc của một hệ thống KPDL điển hình chứa các thành phần sau:  CSDL, kho dữ liệu, web hoặc những hệ thống thông tin khác  Máy chủ CSDL hoặc kho dữ liệu  Dựa trên cơ sở tri thức  Cách thức KPDL  Module đánh giá mô hình  Giao diện người sử dụng 1.2.1 Tiền xử lý dữ liệu Tiền xử lý dữ liệu là quá trình chuẩn bị và xử lý dữ liệu. Trước khi sử dụng bất kỳ kỹ thuật KPDL nào để “khai phá” dữ liệu, một vấn đề cực kỳ cần thiết là phải xử lý dữ liệu thô. Đầu tiên, cần phải xử lý những vấn đề về chất lượng dữ liệu như nhiễu, bất thường… Khi vấn đề chất lượng dữ liệu được giải quyết, sẽ thực hiện công việc tiền xử lý, về nguyên tắc bao gồm những thủ tục sau:  Tập hợp (Aggregation)  Lấy mẫu (Sampling)
6  Giảm chiều thông tin (Dimensionality reduction)  Chọn tính năng (Feature selection)  Tạo ra các tính năng (Feature creation)  Rời rạc và nhị phân (Discretization and binarization)  Chuyển đổi thuộc tính (Atrribute transformation) 1.2.2 Xây dựng và xác nhận mô hình Xây dựng và xác nhận mô hình là một bước của tiến trình KPDL sau tiến trình tiền xử lý. Chú ý rằng, trong một tiến trình KPDL, trạng thái dữ liệu xử lý sẽ lặp lại nếu cần thiết. Một khi dữ liệu “khai phá” được chọn, cần phải quyết định lấy mẫu dữ liệu như thế nào khi không làm việc với toàn bộ CSDL. Một khi dữ liệu đã phân tích được xác định, khi đó sẽ quan tâm đến mục đích của tiến trình KPDL.  Hiểu các giới hạn  Chọn hướng nghiên cứu thích hợp  Kiểu nghiên cứu  Lựa chọn thành phần  Vấn đề lấy mẫu  Đọc dữ liệu và xây dựng mô hình 1.2.3 Áp dụng và đánh giá mô hình Sau khi mô hình xây dựng, áp dụng, cần phải quan tâm đến một số tính năng quan trọng:  Độ chính xác của mô hình (model accuracy)  Độ dễ hiểu của mô hình (model intelligibility)  Khả năng thực thi (performance)  Nhiễu (noise) Mỗi mô hình sẽ có một ngưỡng để chấp nhận nhiễu và đó là lý do cần của tiền xử lý dữ liệu.
7 1.3 Các kỹ thuật khai phá dữ liệu Theo nguyên lý, khi sử dụng phương thức KPDL để giải quyết một vấn đề cụ thể, cần phải hình dung ra loại vấn đề là gì, có thể tổng kết thành hai loại chính, cũng liên quan đến các đối tượng của khai phá dữ liệu:  KPDL dự đoán (predictive method): là đưa ra các dự đoán đựa vào các suy diễn trên dữ liệu hiện thời. KPDL dự đoán bao gồm các kỹ thuật phân loại (classification), hồi quy (regression)..  KPDL mô tả (descriptive method): có nhiệm vụ mô tả về các tính chất hoặc đặc tính chung của dữ liệu trong CSDL hiện có. Bao gồm các kỹ thuật: phân cụm (clustering), phân tích luật kết hợp (association rules), mẫu tuần tự (sequential patterns)... 1.3.1 Phân lớp 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 loại 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;  Mô hình sử dụng để dự đoán những lớp mới, những đối tượng chưa biết. Tập dữ liệu kiểm thử cũng dùng dể xác định độ chính xác của mô hình.
8 Khi một mô hình phân loại được xây dựng, nó sẽ phải so sánh với những mô hình khác để lựa chọn mô hình tốt nhất. Liên quan đến việc so sánh giữa các mô hình phân loại (mô hình phân lớp), sẽ có một số thành phần cần được tính đến.  Khả năng dự đoán (predictive accuracy)  Tốc độ (speed)  Độ mạnh mẽ (robustness)  Độ mềm dẻo (scalability)  Tính dễ diễn giải (interpreability)  Độ đơn giản (simplicity). 1.3.2 Phân cụm Nói đến phân cụm, nghĩa là nói đến chia một tập dữ liệu thành một vài cụm (cluster), dựa trên việc xác định những đặc điểm chung.  Các đối tượng thuộc 1 cụm là tương tự nhau.  Đối tượng ở cụm này sẽ ít tương tự với đối tượng ở cụm khác. Phân cụm dữ liệu được sử dụng nhiều trong các ứng dụng về phân đoạn thị trường, khân khúc khách hàng, nhận dạng mẫu, phân loại trang web… 1.3.3 Luật kết hợp Luật kết hợp là tiến trình xác định những luật phụ thuộc giữa những nhóm khác nhau của hiện tượng. Khai phá luật kết hợp dựa trên hai bước:  Tìm tất cả các tập mục phổ biến, được xác định qua tính hỗ trợ và thỏa mãn độ hỗ trợ cực tiểu;  Sinh ra các luật kết hợp từ các mục phổ biến, các luật phải thỏa mãn độ hỗ trợ cực tiểu và độ tin cậy cực tiểu. Phương pháp này được sử dụng hiệu quả trong các lĩnh vực như quảng cáo có chủ đích, phân tích quyết định, quản lý kinh doanh... 1.3.4 Mẫu tuần tự Mẫu tuần tự là xác định những mẫu mà sự xuất hiện của chúng trong CSDL thỏa mãn ngưỡng tối thiểu. Luật tuần tự được sinh ra từ mẫu tuần tự, biểu diễn mối
9 quan hệ giữa hai loạt sự kiện, loạt sự kiện này sẽ xảy ra sau loạt sự kiện kia, tuần tự theo thời gian, thể hiện tri thức tiềm ẩn của dữ liệu tuần tự Khai thác mẫu tuần tự được ứng dụng trong nhiều lĩnh vực như: phân tích thị trường, phân tích mẫu truy cập web, dự đoán nhu cầu mua sắm của khách hàng.. 1.3.5 Hồi quy Phương pháp hồi quy là học một hàm ánh xạ một mục dữ liệu và một biến dự báo giá trị thự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. Các ứng dụng của phương thức hồi quy:  Kinh tế  Dự báo thời tiết. 1.4 Ứng dụng, thách thức và hướng phát triển của KPDL Với mỗi phương thức riêng biệt, rất nhiều ứng dụng thành công sử dụng KPDL trong cuộc sống thực, sau đây là một số lĩnh vực mà áp dụng thành công kỹ thuật KPDL:  Lĩnh vực tài chính và ngân hàng  Những chiến lược bán hàng  Chăm sóc sức khỏe và y tế  Viễn thông: o Phát hiện gian lận trong cuộc gọi; o Xác định các hồ sơ khách hàng trung thành; o Xác định các nhân tố ảnh hưởng đến hành vi khách hàng liên quan đến các kiểu gọi điện thoại; o Xác định các rủi ro trong việc sử dụng đầu tư các công nghệ mới; o Xác định những sự khác nhau giữa các dịch vụ và sản phẩm giữa các đối thủ cạnh tranh.
10 Chương 2. KHAI PHÁ DỮ LIỆU BẰNG CÂY QUYẾT ĐỊNH 2.1 Cây quyết định 2.1.1 Vấn đề phân lớp Dữ liệu vào của một nhiệm vụ phân lớp là một tập hợp những bản ghi. Mỗi bản ghi, cũng được biết đến như một thể hiện hoặc ví dụ, được miêu tả bởi (x,y)= (x1, x2, x3..., xk, y) với x là tập thuộc tính, còn y là biến phụ thuộc (dependantvariable) cần tìm hiểu, phân loại hay tổng quát hóa, (x1, x2, x3..., xk, y) là các biến sẽ giúp thực hiện công việc đó, được gán như là nhãn của một lớp (category hoặc target attribute). Hình 2.1: Mô hình phân lớp Định nghĩa phân lớp: là hàm chức năng f mà ánh xạ mỗi thuộc tính từ tập x đến một trong những lớp đã được xác định trước của lớp dán nhãn y. Mô hình dự đoán: một mô hình phân lớp có thể được sử dụng để dự đoán những lớp mà chưa được dán nhãn. Như hình 2.1 mô hình phân lớp có thể được coi như là một hộp đen (black-box) tự động gán những nhãn cho lớp khi miêu tả những tập thuộc tính chưa rõ. Để so sánh mức độ hiệu quả của các phương pháp, sẽ sử dụng ma trận thực thi (perfomance metric) như là accuracy, được định nghĩa như sau: Accuracy = = (2.1) Tương tự, khả năng thực thi chính xác của mô hình có thể biểu diễn dưới dạng error rate, được cung cấp bởi điều kiện sau: Error rate = = (2.2) Hầu hết các thuật toán tìm kiếm trong phân lớp được chọn khi đạt được độ chính xác cao nhất hoặc hiệu quả, và tỉ lệ lỗi thấp.
11 2.1.2 Giới thiệu cây quyết định Một trong những phương pháp phân loại phổ biến là mô hình cây quyết định. Theo nguyên tắc, cây quyết định được sử dụng để dự đoán những thành viên của đối tượng theo những đề mục khác nhau (lớp), đưa vào các giá trị mà có liên quan đến thuộc tính (biến dự đoán), phương thức cây quyết định là một trong những kỹ thuật KPDL chính. Việc phân loại được xây dựng bằng cây quyết định dựa trên đặc trưng:  Mỗi cây(nội bộ) (ví dụ nút riêng rẽ) miêu tả những thử nghiệm dựa trên một thuộc tính nhất định.  Mỗi nhánh cây thể hiện kết quả của thử nghiệm  Mỗi nút lá (nút cuối cùng) miêu tả lớp (quyết định) Cây quyết định có ba cách tiếp cận cơ bản:  Cây phân loại: sử dụng khi kết quả dự đoán là một lớp trong thành phần dữ liệu.  Cây hồi quy: khi kết quả dự đoán có thể liên quan tới một số thực sự (giá dầu, giá trị ngôi nhà ..)  CART (classification and regression tree) liên quan đến cả hai trường hợp trên. 2.1.3 Xây dựng cây quyết định Một cây gồm ba kiểu của nút:  Nút gốc(Root node) không có cạnh đến và không hoặc nhiều cạnh đi ra;  Nút trung chuyển (Internal node): mỗi một nút sẽ có chính xác 1 cạnh đến và hai hoặc nhiều cạnh đi ra;  Lá hoặc nút đích (Leaf of terminal nodes): mỗi nút có chính xác 1 cạnh đến và không có cạnh đi ra.
12 Hình 2.4: Các nút của cây quyết định Thuật toán thường được sử dụng để phát triển là chiến lược tham lam. Nghĩa là phát triển cây bằng cách đưa ra một chuỗi các quyết định tối ưu cục bộ về thuộc tính được sử dụng trong dữ liệu. Một trong những thuật toán đó là thuật toán Hunt’s, sử dụng đệ quy để phát triển cây. Gọi Dt là các nhóm của tập kiểm thử gắn với nútt và C = {c1,c2,...cc} là tập nhãn. Theo tuần tự, thuật toán Hunts thực hiện theo những bước sau: 1. Biểu diễn tập Dt là tập các đối tượng học (dữ liệu) là nút t; 2. Nếu tập Dt là tập rỗng, thì t cũng chính là nútđích (nút lá) được gán nhãn bởi lớp Ot 3. Nếu Dt chứa những đối tượng mà phụ thuộc vào cùng lớp Ct, thì t cũng là nút lá, gán nhãn Ct. 4. Nếu Dt chứa đối tượng mà phụ thuộc nhiều hơn 1 lớp, thì sẽ sử dụng những thuộc tính lựa chọn để chia đối tượng thành những tập bé hơn. Từ thuật toán trên, có nhiều mở rộng của việc phân loại:  ID3, C4.5 C5.0 – máy học;  Cart (C&RT) – thống kê;  CHAID – nhận biết mẫu. Theo nguyên tắc, các phương thức liên quan đến cây quyết định sẽ bao gồm hai bước:  Xây dựng cây cơ bản, sử dụng những tập học có sẵn cho đến khi mỗi lá trở thành “thuần” (đồng nhất) hoặc gần như “thuần” (lá cuối cùng)
13  Tỉa cây đã trồng để cải thiện độ chính xác thu được trên tập kiểm tra. Thuật toán sau trình bày những thủ tục cơ bản liên quan đến việc xây dựng cây quyết định nhị phân. Tree building algorithm Tree building algorithm Make Tree(Training Data T) { Partition(T) } SPRINT algorithm(node S) Partition(Data S) { if(all points in S are in the same class)then return for each attribute A do evaluate splits on attribute A; use the best found split to partition S into S1 and S2 Partition(S1) Partition(S2) } Có rất nhiều đơn vị đo lường được sử dụng để xác định cách tốt nhất để chia tách cây. Những đơn vị đo lường đó định nghĩa như những thuật ngữ của việc phân chia thuộc tính lớp trước và sau khi chia.  Chỉ số GINI (impurity)  Chỉ số Entropy  Biện pháp phân loại sai. 2.3.1.1 GINI index Đặt f(i,j) là tần số xảy ra của lớp j tại nút i hoặc, nói theo cách khác, là vị trí của đối tượng phụ thuộc vào lớp j mà phân chia đến nút i (với m điểm đích lớp của đối tượng). Chỉ số GINI được tính như sau: I (i) = 1 − f (i, j)(2.3) Khi nút “cha” chia bởi p phần (con), chất lượng của việc phân chia được tính bởi chỉ số GINIsplitting: GINI = GINI(i) (2.4)
14 Chỉ số phân chia tối ưu của nút đảm bảo chỉ số GINIsplit thấp nhất (giá trị mong đợi =0) 2.3.1.2 Entropy index Công thức tính entropy như sau: Entropy (i) = I (i) = − ∑ f(i, j). log [f(i, j)] (2.5) Với tương tự như chỉ số GINI, f(i,j) là tần số xảy ra của lớp j tại nút i (tỷ lệ của đối tượng của lớp j phụ thuộc vào nút i). Khi nút cha được chia thành p phần, chất lượng của việc chia cắt được tính bởi chỉ số Entropy splitting: Entropysplit Entropy = I (i)(2.6) Giá trị phân chia tối ưu của một nút là số đảm bảo sao cho chỉ số Entropysplit là bé nhất (giá trị tốt nhất bằng 0). 2.3.1.3 Misclassfication measure (chỉ số đo lường sai) Một chỉ số để đo tạp chất đôi khi được sử dụng cho các nút phân chia dựa trên giá trị chỉ số đo lường sai. Chỉ số đo lường sai là là phân lớp lỗi mà có thể tạo ra tại các nút sử dụng điểm phân chia chính xác, và đưa ra bởi: Error(i) = I (i) = 1 − max f(i, j) (2.7) Với f(i,j) là tỷ lệ của đối tượng của lớp j mà gán bởi nút i. Khi nút “cha” được chia thành p phần, chất lượng của việc phân chia đo bởi chỉ số Errorsplit: = () (2.8) 2.2 Một số thuật toán xây dựng cây quyết định 2.2.1 ID3 Đầu vào: Một tập các ví dụ. Mỗi ví dụ bao gồm các thuộc tính rời rạc, mô tả một tình huống, hay một đối tượng nào đó, và một giá trị phân loại của nó Đầu ra: Cây quyết định có khả năng phân loại đúng các ví dụ trong tập dữ liệu rèn luyện, và phân loại đúng cho cả các ví dụ chưa gặp trong tương lai
15 Mã giả cho thuật toán ID3 Function ID3 (R: a set of non-categorical attributes, C: the categorical attribute, S: a training set) returns a decision tree; begin If S is empty, return a single node with value Failure; If S consists of records all with the same value for the categorical attribute, return a single node with that value; If R is empty, then return a single node with as value the most frequent of the values of the categorical attribute that are found in records of S; [note that then there will be errors, that is, records that will be improperly classified]; Let D be the attribute with largest Gain(D,S) among attributes in R; Let {dj| j=1,2, .., m} be the values of attribute D; Let {Sj| j=1,2, .., m} be the subsets of S consisting respectively of records with value dj for attribute D; Return a tree with root labeled D and arcs labeled d1, d2, .., dm going respectively to the trees ID3(R-{D}, C, S1), ID3(R-{D}, C, S2), .., ID3(R-{D}, C, Sm); end ID3; Hai độ đo được sử dụng trong ID3 là information gain và gain ratio. RF(Cj, S) biểu diễn tần xuất (Relative Frequency) các trường hợp trong S thuộc về lớp Cj: RF(Cj, S) =| Sj|/|S| Với | Sj| là kích thước tập các trường hợp có giá trị phân lớp là Cj. |S| là kích thước tập dữ liệu đào tạo. Việc tính toán chỉ số gain và tỉ lệ gain theo công thức 2.5 và 2.6 2.2.2 C4.5 C4.5 là thuật toán dùng để xây dựng cây quyết định được được đề xuất bởi Ross Quinlan, là mở rộng của ID3http://en.wikipedia.org/wiki/C4.5_algorithm - cite_note-0. Đặc điểm của C4.5 :  Cho phép dữ liệu đầu vào ở các thuộc tính là liên tục;  Cho phép thao tác với các thuộc tính có dữ liệu không xác định (do bị mất mát dữ liệu, …);  Đưa ra phương pháp “cắt tỉa” cây và giản lược các luật để phù hợp với những bộ dữ liệu lớn. C4.5 giới thiệu một số mở rộng của thuật toán ID3.
16 Đối với những thuộc tính liên tục sẽ được xử lý như sau: 1. Kỹ thuật Quick sort được sử dụng để sắp xếp các trường hợp trong tập dữ liệu đào tạo theo thứ tự tăng dần hoặc giảm dần các giá trị của thuộc tính liên tục V đang xét. Được tập giá trị V = {v1, v2, …, vm} 2. Chia tập dữ liệu thành hai tập con theo ngưỡng θi= (vi + vi+1)/2 nằm giữa hai giá trị liền kề nhau (vi,vi+1). Test để phân chia dữ liệu là test nhị phân dạng Vθi. Thực thi test đó ta được hai tập dữ liệu con: V1 = {v1, v2, …, vi} và V2 = {vi+1, vi+2, …, vm} 3. Xét (m-1) ngưỡng θi có thể có ứng với m giá trị của thuộc tính V bằng cách tính Information gain hay Gain ratio với từng ngưỡng đó. Ngưỡng có giá trị của Information gain hay Gain ratio lớn nhất sẽ được chọn làm ngưỡng phân chia của thuộc tính đó. Đối với những giá trị thiếu Trong quá trình xây dựng cây từ tập dữ liệu đào tạo S, B là tập dữ liệu kiểm thử dựa trên thuộc tính Aavới các giá trị đầu ra là (b1, b2, ..., bt). Tập S0là tập con các trường hợp trong S mà có giá trị thuộc tính Aakhông biết và Si biểu diễn các trường hợp với đầu ra là bitrong tậpB. Khi đó độ đo informationgain của tập B giảm vì không học được gì từ các trường hợp trong S0. ( , )= ( − , ) (công thức 2.9) Tương ứng với G(S, B), P(S, B) cũng thay đổi: | | | | | | | | ( , )=− log ( | | ) − ∑ log ( ) (công thức 2.10) | | | | | | Hai thay đổi này làm giảm giá trị của kiểm thử liên quan đến thuộc tính có tỉ lệ giá trị thiếu cao. Nếu tậpB được chọn, C4.5 không tạo một nhánh riêng trên cây quyết định cho S0. Thay vào đó, thuật toán có cơ chế phân chia các trường hợp trong S0về vác tập con Si là tập con mà có giá trị thuộc tính kiểm thử xác định theo trong số |Si|/|S– S 0|.
17 2.3 Cắt tỉa cây quyết định 2.3.1 Đặc trưng khi xây dựng cây quyết định Độ phức tạp tối đa là O(w) với w là độ sâu cây. 2.3.2 Độ chính xác trong tiên đoán Mục đích của việc xây dựng cây quyết định là đạt được dự đoán dữ liệu mới chính xác nhất có thể. Việc đó thực sự là khó khăn, nếu không muốn nói là bất khả thi, để xác định một cách tuyệt đối một giá trị với tính chính xác dự báo được, tuy nhiên, trong thực tế một số chỉ số của quá trình dự đoán, được coi là chi phí dự đoán. Sau đây là những chi phí chính có liên quan trong tiến trình phân loại:  Xác suất ưu tiên (prior probabilities)  Giá thành đo lường sai(Misclassification costs) 2.3.3 Điều kiện dừng cho quá trình tách Có hai luật điều khiển dừng khi muốn dừng phân tách:  Giá trị tối thiểu n  Tỷ lệ của các đối tượng. 2.3.4 Cắt tỉa cây quyết định Có hai kiểu của việc tỉa cây quyết định:  Tiền cắt tỉa (Pre-pruning): dừng sớm việc phát triển cây trước khi nó vươn đến điểm mà việc phân lớp các mẫu huấn luyện được hoàn thành. Hậu cắt tỉa (Post-pruning): Chiến thuật này ngược với chiến thuật tiền cắt tỉa, cho phép phát triển câyđầy đủ sau đó mới cắt tỉa. 2.3.5 Tách luật phân loại từ cây quyết định Một khi cây quyết định đã được xây dựng, mô hình được sử dụng để đưa ra quyết định một cách tối ưu. Tri thức đạt được bởi cấu trúc “của cây” có thể dễ dàng “đọc” bằng duyệt cây theo từng “nhánh” đến lá (duyệt từ gốc đến ngọn), vì thế, luật của cây phân loại theo câu lệnh if-then.
18 2.4 Đánh giá cây quyết định 2.4.1 Ưu điểm của cây quyết định  Khả năng tạo ra những luật dễ hiểu.  Khả năng xử lý với cả thuộc tính liên tục và thuộc tính rời rạc.  Thể hiện rõ ràng những thuộc tính tốt nhất.  Xử lý cả dữ liệu có giá trị bằng số và dữ liệu có giá trị theo loại  Cây quyết định là mô hình hộp trắng (whitebox) 2.4.2 Nhược điểm của cây quyết định  Mắc lỗi với quá nhiều lớp  Việc đào tạo tốn kém
19 Chương 3: XÂY DỰNG HỆ THỐNG TÌM HIỂUTHÔNG TIN KHÁCH HÀNG 3.1 Xây dựng cơ sở dữ liệu Hình 3.1: Hệ thống xử lý cước Hình 3.1 miêu tả một hệ thống xử lý cước, khi khách hàng thực hiện cuộc gọi/sử dụng, tổng đài sẽ ghi lại các thông tin như: chủ gọi, bị gọi, ngày, thời gian bắt đầu, thời gian kết thúc… các thông tin này được ghi lại, xử lý, lưu trữ gọi là CDR (Call detail records). Kết hợp với dữ liệu phát triển thuê bao do trung tâm khách hàng cung cấp để tính cước điện thoại. Việc khai phá dữ liệu thông tin khách hàng kết hợp trên ba cơ sở dữ liệu chính gồm: dữ liệu cuộc gọi, dữ liệu khách hàng, dữ liệu doanh thu. 3.2 Xây dựng mô hình Luận văn sử dụng thuật toán C4.5 thử nghiệm trên nguồn dữ liệu thói quen thanh toán hóa đơn điện thoại để phân loại khách hàng có thói quen trả hóa đơn điện thoại tốt/xấu. Đầu vào: o Nguồn dữ liệu thử nghiệm: paid_history.arff o Số mẫu:1000 o Số thuộc tính: 14