- Ứng dụng một số kỹ thuật khai phá dữ liệu để phân tích dữ liệu viễn thông nhằm tăng cường chất lượng dịch vụ khách hàng An application of data mining techniques to analyze data telecommunications to enhance the quality of customer service NXB H. - Mã số: 60 48 05 Người hướng dẫn: PGS.TS.Nguyễn Hà Nam Năm bảo vệ: 2012 Abstract: Tổng quan về khai phá dữ liệu: khai phá dữ liệu. - Quá trình khai phá tri thức trong cơ sở dữ liệu (CSDL). - Các kỹ thuật tiếp cận trong khai phá dữ liệu. - Kiến trúc của hệ thống khai phá dữ liệu. - Ứng dụng khai phá dữ liệu. - Giới thiệu khai phá mẫu phổ biến, luật kết hợp bao gồm: khái niệm về khai phá phổ biến và tổng quan về luật kết hợp. - Lưu trữ dữ liệu lớn dựa trên Oracle DBMS. - Áp dụng Luật kết hợp vào Cơ Sở Dữ Liệu Oracle (đặc tả bài toán, tính độ hỗ trợ, các ví dụ minh họa). - Ứng dụng vào phân tích dữ liệu viễn thông tại Beeline Keywords: Công nghệ thông tin. - Khai phá dữ liệu. - Dữ liệu viễn thông. - Phân tích dữ liệu. - Hệ thống thông tin Content 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. - Ứng dụng kỹ thuật khai phá dữ liệu (data mining) để phát hiện các quy luật ẩn chứa trong khối dữ liệu khổng lồ đó sẽ mang lại cho các doanh nghiệp viễn thông nhiều cơ hội để phát triển các ứng dụng mang tính thực tiễn cao. - Khai phá dữ liệu chính là một trong những kỹ thuật hữu ích nhất để giải quyết những vấn đề này. - Vấn đề đặt ra: Bài toán đặt ra cho các nhà mạng di động là thu thập được các tri thức từ các kho dữ liệu khách hàng khổng lồ. - Phân loại dữ liệu cước di động là một phương pháp giúp cho các nhà mạng di động có thể phân loại được các nhóm đối tượng khách hàng khác nhau, từ đó đưa ra các chiến lược kinh doanh phù hợp với từng đối tượng khách hàng. - Luận văn “ứng dụng một số kỹ thuật khai phá dữ liệu để phân tích dữ liệu viễn thông nhằm tăng cường chất lượng dịch vụ khách hàng” Đề tài được nghiên cứu dựa trên luật kết hợp, một trong những những kỹ thuật rất quan trọng của khai phá dữ liệu. - Nội dung chính của luận văn được chia thành năm chương như sau: Chương 1: Mở đầu Chương 2: Giới thiệu khai phá mẫu phổ biến, luật kết hợp Chương 3: Lưu trữ dữ liệu lớn dựa trên Oracle DBMS Chương 4: Áp dụng Luật kết hợp vào Cơ Sở Dữ Liệu Oracle Chương 5: Ứng dụng vào phân tích dữ liệu viễn thông tại Beeline: Phân tích một cơ sở dữ liệu, trình bày về cách cài đặt chương trình khai thác luật kết hợp trong việc sử dụng các dịch vụ giá trị gia tăng của khách hàng. - Khai phá dữ liệu là một khái niệm ra đời vào những năm cuối của thập kỷ 80. - Nó bao hàm một loạt các kỹ thuật nhằm phát hiện ra các thông tin có giá trị tiềm ẩn trong các tập dữ liệu lớn (các kho dữ liệu). - Về bản chất, khai phá dữ liệu liên quan đến việc phân tích các dữ liệu và sử dụng các kỹ thuật để tìm ra các mẫu hình có tính chính quy trong tập dữ liệu. - Ở một mức độ trừu tượng nhất định có thể định nghĩa: Khai phá dữ liệu (Data Mining) là một quá trình tìm kiếm, phát hiện các tri thức mới, tiềm ẩn, hữu dụng trong CSDL lớn. - 2 Khai phá tri thức (KDD) là mục tiêu chính của khai phá dữ liệu, do vậy hai khái niệm đó được xem như hai lĩnh vực tương đương nhau. - Nhưng, nếu phân chia một cách tách bạch thì khai phá dữ liệu là một bước chính trong quá trình KDD. - Quá trình khai phá tri thức trong cơ sở dữ liệu Khai phá tri thức trong CSDL ( Knowledge Discovery in Databases - KDD) là lĩnh vực liên quan đến các ngành như: thống kê, học máy, CSDL, thuật toán, trực quan hóa dữ liệu, tính toán song song và hiệu năng cao,… Quá trình KDD có thể phân thành các giai đoạn sau: Hình 1.1: Khai phá dữ liệu là một bước trong quá trình khai phá tri thức Các kỹ thuật tiếp cận trong khai phá dữ liệu. - Kiến trúc của hệ thống khai phá dữ liệu Như đã trình bày ở trên, khai phá dữ liệu là một giai đoạn trong quá trình phát hiện tri thức từ số lượng lớn dữ liệu lưu trữ trong các cơ sở dữ liệu, kho dữ liệu hoặc các nơi lưu trữ khác. - 3 Hình 1.2: Kiến trúc của hệ thống khai phá dữ liệu Ứng dụng của khai phá dữ liệu Khai phá dữ liệu thu hút được rất nhiều sự quan tâm của các nhà nghiên cứu nhờ vào tính ứng dụng thực tiễn của nó. - Khai phá dữ liệu có nhiều ứng dụng trong thực tế. - Một trong số ứng dụng điển hình như: phân tích dữ liệu và hỗ trợ ra quyết định, tài chính và thị trường chứng khoán, điều trị và chăm sóc y tế, text mining & web mining, các lĩnh vực khoa học, mạng viễn thông. - Các ứng dụng quản lý và chăm sóc khách hàng Các công ty viễn thông quản lý một khối lượng lớn dữ liệu về thông tin khách hàng và dữ liệu về chi tiết cuộc gọi (call detail records). - Các ứng dụng khai phá dữ liệu phổ biến trong lĩnh vực viễn thông. - Ứng dụng khai phá dữ liệu dựa trên việc xem xét luật kết hợp giữa các dịch vụ viễn thông khách hàng sử dụng. - Dựa vào dữ liệu khách hàng và chi tiết cuộc gọi có thể tìm ra các luật để phân loại khách hàng. - Đề tài phân tích dữ liệu viễn thông nhằm nhận diện được những đặc tính của khách hàng và thông qua đó có thể đưa ra các chính sách chăm sóc khách hàng thích hợp dựa trên dự đoán hoặc có một chiến lược tiếp thị hiệu quả. - 4 Giới thiệu khai phá mẫu phổ biến, luật kết hợp Khái niệm về khai phá mẫu phổ biến Mẫu phổ biến Mẫu phổ biến (Frequent pattern): là mẫu (tập mục - itemsets, dãy mục – itemlists, dãy con – subsequence, hoặc cấu trúc con – substructures…) mà xuất hiện phổ biến trong một tập dữ liệu. - Agrawal, Imielinski, Swami – 1993 – trong ngữ cảnh bài toán tập phổ biến và luật kết hợp Ý nghĩa của khai phá mẫu phổ biến Tìm kiếm mẫu phổ biến đóng vai trò thiết yếu trong khai phá luật kết hợp, tìm kiếm mối tương quan, và các mối quan hệ trong cơ sở dữ liệu. - Hơn nữa nó giúp phân lớp, phân cụm dữ liệu, và hỗ trợ các nhiệm vụ khai phá dữ liệu khá tốt. - Do vậy, khai phá mẫu phổ biến đã trở thành nhiệm vụ quan trọng trong khai phá dữ liệu. - Bài toán thực tế Có thể kết luận rằng, khai phá mẫu phổ biến là quá trình tìm kiếm mối quan hệ tuần hoàn, lặp đi lặp lại trong một cơ sở dữ liệu. - Cho D là một cơ sở dữ liệu giao dịch như là danh sách các mặt hàng (mục: item) trong một phiếu mua hàng của khách hàng. - Gọi X Y là một “luật kết hợp” nếu X I, Y I và XY. - Luật kết hợp X Y có độ hỗ trợ (support) s trong CSDL giao dịch D nếu trong D có s% các giao dịch T chứa XY: chính là xác suất P(XY). - Luật kết hợp X Y có độ tin cậy (confidence) c trong CSDL D nếu như trong D có c% các giao dịch T chứa X thì cũng chứa Y: chính là xác suất P(X|Y). - Như vậy, quá trình khai phá luật kết hợp phải được thực hiện thông qua hai bước: Bước 1: Tìm tất cả các tập mục mà có độ hỗ trợ lớn hơn độ hỗ trợ tối thiểu do người dùng xác định. - Giải thuật Apriori để sinh các luật kết hợp. - Để hình dung rõ hơn các giai đoạn trong quá trình phát hiện luật kết hợp, chúng ta sẽ xem xét giải thuật Apriori phát hiện luật kết hợp từ cơ sở dữ liệu tác vụ. - Tiếp tục duyệt cơ sở dữ liệu giao dịch để có được độ hỗ trợ S của mỗi candidate k-itemset, so sánh S với min_sup để thu được tập phổ biến k –itemset (Fk) d. - Cơ sở dữ liệu giao dịch D = {t|t : giao dịch. - Thủ tục được gọi sau đó để sinh luật kết hợp từ tập mục phổ biến. - Lưu trữ dữ liệu lớn dựa trên Oracle DBMS Hầu hết các nghiên cứu về khai phá dữ liệu đã đề xuất thuật toán và tối ưu hóa làm việc trên các flat files, chứ không phải là một DBMS, chủ yếu do những lý do sau đây. - Việc tích hợp các thuật toán khai phá dữ liệu vào một DBMS sẽ mang lại khó khăn trên nền tảng mô hìnhquan hệ và kiến trúc hệ thống. - Do đó, người sử dụng các ứng dụng khai phá dữ liệu thường biến đổi các bộ dữ liệu bên trong DBMS ra flat files sau đó mới đưa vào công cụ khai phá dữ liệu, để tránh hiệu suất giảm và loại bỏ khả năng quản lý dữ liệu quan trọng như xử lý truy vấn và an ninh dữ liệu, đồng thời kiểm soát và khả năng chịu lỗi. - Hầu hết các thuật toán đã được tối ưu hóa để giảm bớt số lần duyệt các tập dữ liệu. - Hệ thống có thể phân tích lượng lớn các tập dữ liệu nhanh hơn so với các công cụ khai phá dữ liệu sử dụng flat files, ví dụ như weka. - Hướng nghiên cứu của đề tài nghiên cứu các vấn đề thực hiện khai phá dữ liệu bên trong một DBMS, chú ý đến các bộ dữ liệu lớn. - Giới thiệu hệ quản trị CSDL Oracle Các công ty viễn thông quản lý một khối lượng lớn dữ liệu về thông tin khách hàng và dữ liệu về chi tiết cuộc gọi (call detail records). - Và CSDL Oracle là một lựa chọn tối ưu để lưu trữ lượng dữ liệu lớn đó trong các doanh nghiệp viễn thông. - Oracle cung cấp một hệ quản trị cơ sở dữ liệu (Database Management System - DBMS) uyển chuyển: Oracle Server để lưu giữ và quản lý các thông tin dùng trong các ứng dụng. - 8 Phương pháp tiếp cận và kiến trúc Đề tài trình bày một hệ thống khai phá dữ liệu trên hệ quản trị cơ sở dữ liệu quan hệ Oracle dựa trên các truy vấn SQL và các hàm định nghĩa trực tiếp bởi người dùng, và sẽ chứng minh rằng “SQL là không hiệu quả hoặc không đầy đủ cho khai phá dữ liệu là sai”. - Mục đích của luận văn là khám phá rất nhiều những vấn đề gặp phải khi CSDL được tích hợp vào quá trình khai phá dữ liệu. - Hiện nay có nhiều công cụ khai phá dữ liệu thương mại sẵn có trên thị trường như IBM‟s Intelligent Miner, DBMiner,Oracle Data Mining, …Chúng có khả năng cung cấp khai phá dữ liệu trên CSDL quan hệ. - Các file sử dụng cho các thuật toán khai phá, chúng được sử dụng làm dữ liệu đầu vào và không chứa trong cơ sở dữ liệu. - Chúng thường bị giới hạn số lượng giao dịch có thể được khai phá. - Ví dụ, DBMiner giới hạn số lượng giao dịch là 64K mà nó có thể xử lý khai phá. - Phân tích kế hoạch truy vấn, lựa chọn kế hoạch tốt nhất cho mỗi tính toán khai phá dữ liệu, xác định tối ưu hóa hiệu năng. - Với các truy vấn SQL có rất nhiều bảng tạm thời được tạo ra trong quá trình duyệt dữ liệu. - Để có được hiệu năng tốt nhất, bảng dữ liệu lớn sẽ được tạo chỉ mục và phân khu dữ liệu. - Áp dụng Luật kết hợp vào Cơ Sở Dữ Liệu Oracle Đặc tả bài toán Dữ liệu vào: định dạng đầu vào là một bảng có hai cột. - Trong mỗi giao dịch, nếu có nhiều hơn một mặt hàng, thì sẽ có nhiều dòng dữ liệu trong bảng giao dịch với cùng giá trị trong cột tid và các giá trị khác nhau trong cột mặt hàng. - Ngoài ra cơ sở dữ liệu hiện tại trên thị trường có thể chỉ hỗ trợ số lượng nhất định các cột cho một bảng. - Nếu một trường hợp phát sinh trong đó có số lượng mặt hàng trong một giao dịch hơn mức cho phép của các cơ sở dữ liệu cơ bản, không có cách nào chúng ta có thể quản lý chính xác của dữ liệu. - Dữ liệu ra: Đầu ra là một tập các bộ quy tắc, dữ liệu được trình bày theo hình thức bảng được đặt tên là RULES. - Không phải luật kết hợp nào được sinh ra cũng cùng độ dài do đó chúng ta sẽ sử dụng độ dài tối đa để xác định số lượng các cột của bảng đầu ra. - Một luật kết hợp được sinh ra cần phải có ít mặt hàng (item) hơn số lượng cột trong bảng. - Những cột bổ sung cho luật kết hợp được sinh ra được gán giá trị 0. - trong luật kết hợp. - Confidence và support lần lượt là độ tin cậy và độ hỗ trợ của luật kết hợp được sinh ra. - Một phép kết nối với Ir (3 ‟ trong luật kết hợp và count là độ hỗ trợ. - Đối với một dòng dữ liệu trong bảng FISETS, có giá trị trong các cột (item1,…,itemk) tăng dần. - Hình 4.8: Liệt kê tổ hợp chập k của n phần tử Sinh các luật kết hợp Chúng ta sẽ kết hợp hai bảng FISETS và SUBSETS với điều kiện: SUBSETS .count min_ conf FISETS .count Cập nhật dữ liệu vào bảng RULES (item1. - s.itemk, s.nullm, s.rulem, (float(s.count)/f.count)*100 Confidence, s.count Support (3) from SUBSETS s, FISETS f 14 (4) where (s.item1 = f.item1 OR s.rulem 80% Phân tích dữ liệu kết quả thực nghiệm Mật độ phân bố luật kết hợp trên độ hỗ trợ và độ tin cậy Với số lượng 41.714 luật kết hợp, 29.112 luật kết hợp có độ hỗ trợ bé hơn luật kết hợp có độ hỗ bé hơn luật kết hợp có độ hỗ bé hơn 0.4, 116 luật kết hợp có độ hỗ có độ hỗ trợ bé hơn 0.5, 274 luật kết hợp có độ hỗ trợ bé hơn 0.8 và 680 luật kết hợp có độ hỗ bé hơn 1. - Hình 5.2: Mật độ luật kết hợp trên độ tin cậy Xác định mối quan hệ dịch vụ gia tăng bằng phát hiện luật kết hợp. - Với dữ liệu gốc ban đầu đã có, chương trình phần mêm đề tài phát triển sẽ giúp phát hiện các luật kết hợp. - Chạy chương trình trên tập dữ liệu phục vụ phát hiện luật kết hợp với việc lựa chọn độ hỗ trợ cực tiểu minSup = 0,01 (hay 1%) và độ tin cậy cực tiểu minConf = 0,8 (80. - đã nhận được 177 luật kết hợp (chi tiết xem Phụ lục, mục 5, kết quả phát hiện luật kết hợp), trong đó 5 luật có độ hỗ trợ cao nhất được trình bầy ở dưới : Luật 1: Local Incoming VC. - 18 Kết luận Khoá luận đã trình bày tổng quan và các nét đặc trưng nhất trong lĩnh vực Data Mining bao gồm các vấn đề cần khám phá tri thức, các hướng tiếp cận và nghiên cứu tiểu biểu, trong đó phát hiện luật kết hợp là một phương pháp khám phá tri thức quan trọng trong khai phá dữ liệu có nhiều ý nghĩa trong khoa học cũng như trong thực tiễn. - Về mặt lý thuyết, khai phá tri thức bao gồm các bước: Hình thành, xác định và định nghĩa bài toán. - thu thập và tiền xử lý dữ liệu. - khai phá dữ liệu, rút ra các tri thức. - Về thuật toán khai phá tri thức, luận văn trình bày thuật toán Apriori và minh hoạ thuật toán Apriori thực hiện phát hiện luật phổ biến trên CSDL quan hệ. - Về mặt cài đặt thử nghiệm, khoá luận giới thiệu kỹ thuật khai phá dữ liệu theo thuật toán Apriori áp dụng vào bài toán phát hiện và dự báo mức độ sử dụng các dịch vụ gia tăng của viễn thông. - Phát hiện luật kết hợp là kỹ thuật phát hiện thông tin, tri thức trên tập dữ liệu lớn hoặc rất lớn nên ý nghĩa và độ tin cậy của các luật này càng cao nếu tập dữ liệu càng lớn, nói cách khác số lượng các dịch vụ gia tăng được lựa chọn càng nhiều và dữ liệu chi tiết cuộc gọi càng dài về mặt thời gian càng tốt. - Số lượng các luật kết hợp nói chung là khá lớn và không tránh khỏi có một số luật kết hợp dư thừa. - Người ta có thể khắc phục số lượng các luật kết hợp bằng cách tăng độ hỗ trợ cực tiểu và độ tin cậy cực tiểu và luận văn đã thực hiện theo hướng này. - Các luật kết hợp nói chung có độ hỗ trợ không cao (điều đó là tự nhiên) nhưng độ tin cậy rất cao. - Điều đó ngầm định rằng các quan hệ về các dịch vụ giá tri gia tăng được sử dụng được tìm thấy thông qua luật kết hợp là rất đáng tin cậy. - Hà Quang Thụy, “Bài giảng cao học môn học Khai phá web”, Trường Đại học Công nghệ, 2007. - Trần Văn Thiện, “Ứng dụng các kỹ thuật khai phá dữ liệu vào lĩnh vực viễn thông”