Tài liệu Phương pháp phân cụm tích lũy và áp dụng tại ngân hàng thương mại cổ phần quân đội

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ PHẠM THỊ ÁNH PHƯƠNG PHÁP PHÂN CỤM TÍCH LŨY VÀ ÁP DỤNG TẠI NGÂN HÀNG THƯƠNG MẠI CỔ PHẦN QUÂN ĐỘI LUẬN VĂN THẠC SĨ Hà Nội - 2011 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ PHẠM THỊ ÁNH PHƯƠNG PHÁP PHÂN CỤM TÍCH LŨY VÀ ÁP DỤNG TẠI NGÂN HÀNG THƯƠNG MẠI CỔ PHẦN QUÂN ĐỘI Ngành: Công nghệ Thông tin Chuyên ngành: Hệ thống Thông tin Mã số: 60 48 05 LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS. Hà Quang Thụy Hà Nội - 2011 MỤC LỤC MỞ ĐẦU ........................................................................................................................ 6 Chương 1. Khái quát về phân cụm................................................................................... 3 1.1 Khái quát về bài toán phân cụm dữ liệu .................................................................. 3 1.2 Một số phương pháp phân cụm điển hình ............................................................... 4 1.2.1 Các phương pháp phân vùng ............................................................................ 4 1.2.2 Các phương pháp phân cấp ............................................................................ 10 1.2.3 Phương pháp phân cụm dựa trên mật độ ........................................................ 15 Chương 2. Phương pháp phân cụm tích lũy ................................................................... 19 2.1 Giới thiệu phương pháp phân cụm tích lũy ........................................................... 19 2.2 Sự kết hợp bầu cử đa số của các thuật toán phân cụm ........................................... 20 2.3 Một số thuật toán phân cụm tích lũy ..................................................................... 21 2.3.1. Phân cụm tích lũy dựa trên K-Means ............................................................ 22 2.3.2 Phân cụm tích lũy dựa trên lan truyền quan hệ ............................................... 25 Chương 3. Mô hình khai phá dữ liệu dịch vụ khách hàng Ngân hàng quân đội .............. 32 3.1 Một số mô hình khai phá dữ liệu ngân hàng ......................................................... 32 3.2 Hệ thống dịch vụ Ngân hàng quân đội .................................................................. 47 3.2.1 Hệ thống các dịch vụ ...................................................................................... 47 3.2.2 Hệ thống dữ liệu ............................................................................................ 48 3.3 Một mô hình phân cụm tích lũy dữ liệu khách hàng tại Ngân hàng quân đội ........ 50 Chương 4. Thực nghiệm và đánh giá ............................................................................. 52 4.1 Mục đích xây dựng và vai trò của ứng dụng ......................................................... 52 4.2. Mô hình thực nghiệm .......................................................................................... 52 4.2.1. Dữ liệu thực nghiệm ..................................................................................... 52 4.2.2 Công cụ thực nghiệm ..................................................................................... 57 4.3 Thực nghiệm và đánh giá ..................................................................................... 59 4.3.1 Môi trường thực nghiệm ................................................................................ 59 4.3.2. Mô tả quy trình thực nghiệm ......................................................................... 61 4.3.3. Kết quả thực nghiệm và đánh giá nhận xét .................................................... 62 KẾT LUẬN................................................................................................................... 71 TÀI LIỆU THAM KHẢO ............................................................................................. 72 THUẬT NGỮ VÀ TỪ VIẾT TẮT STT Từ viết tắt Giải thích 1 CSDL Cơ sở dữ liệu 2 ATM Máy rút tiền tự động 3 MB Ngân hàng quân đội 4 CMTND Chứng minh thư nhân dân 5 OLAP Online analytical processing: xử lý phân tích trực tuyến 6 CBM Customer behavior modeling: mô hình hóa hành vi khách hàng 7 NN Neutral network: mạng nơron 8 AP Affinity propagation: lan truyền quan hệ DANH MỤC HÌNH VẼ Hình 1.1: Một phần nhỏ của dữ liệu khách hàng về các vị trí khách hàng trong một thành phố, chỉ ra ba phân cụm dữ liệu, Mỗi trung tâm phân cụm được đánh dấu „+‟ [1] ........... 3 Hình 1.2: Quá trình phân cụm tập điểm thành 3 cụm theo k-means [1] ............................ 6 Hình 1.3 trường hợp của hàm chi phí cho phân cụm k-medoid [1] .................................. 8 Hình 1.4: Quá trình phân cụm tập điểm thành 3 cụm theo k- medoids [1] ....................... 9 Hình 1.5: phân cụm phân cấp dạng tích lũy và phân chia trên các đối tượng dữ liệu {a,b,c,d,e} [1]................................................................................................................ 11 Hình 1.6: Một cây cấu trúc CF [1] ................................................................................ 12 Hình 1.7: Phương pháp Chameleon ............................................................................... 15 Hình 1.8 Phạm vi mật độ và sự liên kết mật độ trong phân cụm dựa trên mật độ [1] ...... 16 Hình 1.9: Phân cụm dựa trên phương pháp mật độ [1] ................................................... 18 Hình 2.1: Bổ xung sự phụ thuộc của thuật toán k-means trên sự khởi tạo trung tâm cụm, k=2. (a)- vùng dữ liệu có được với việc chạy thuật toán k -means đơn. (b)- kết quả có được khi sử dụng phương thức đề xuất với số lần lặp là 10. .......................................... 23 Hình 2.2: Các cụm tạo ra bởi k-means (k=14) và các thuật toán voting-k-means. .......... 24 Hình 2.3: Kết quả phân cụm cho một số phương pháp áp dụng cho tập dữ liệu kích thước 2000 là tổ hợp của 2 vòng xoắn. (a) k-means, k=45  2000 . (b) PAP (  =  ). (c) PAP (  =4). .......................................................................................................................... 30 Chương 3. Mô hình khai phá dữ liệu dịch vụ khách hàng Ngân hàng quân đội .............. 32 Hình 3.1: Việc sử dụng kĩ thuật khai phá dữ liệu là một thách thức to lớn đối với ngành tài chính. Nguồn dữ liệu to lớn của công ty có thể được sử dụng thông qua khai phá dữ liệu cho những lĩnh vực ngành nghề khác[5] ................................................................. 35 Hình 3.2: Sử dụng kĩ thuật khai phá dữ liệu đối cho rủi ro khách hàng, công cụ tài chính, danh mục đầu từ đối thị trường và với phương pháp đánh giá rủi ro tín dụng [5] ........... 39 Hình 3.3: Sự quản lý danh mục công cụ là cơ sở đối với mọi thông tin, không những là rủi ro, kịch bản và các mức độ tín dụng dự đoán, mà còn là các tin tức và tài nguyên thông tin khác.[5] .......................................................................................................... 44 Hình 3.4: Những người kinh doanh kiểm tra mối quan hệ giữa thông tin liên quan và giá trị của tài sản ngành tài chính, và các mức độ an toàn mua hoặc bán khi họ phát hiện giá lên hay xuống. [5] ......................................................................................................... 45 Hình 3.5 Mô hình tính toán dữ liệu phương pháp phân cụm tích lũy dựa trên k-means .. 51 Hình 4.1: Giao diện ứng dụng cài đặt thuật toán phân cụm tích lũy dựa trên phương pháp k-means ......................................................................................................................... 58 Hình 4.2: Mô hình ứng dụng cài đặt .............................................................................. 61 Hình 4.3: Giao diện thực nghiệm theo phương án 1 ....................................................... 63 Hình 4.4: Giao diện đồ họa thể hiện hai cụm theo phương án thực nghiệm 1 ................. 64 Hình 4.5: Thay đổi tham số đầu vào liên quan đến quá trình thực nghiệm ..................... 65 Hình 4.6: Giao diện đồ họa thể hiện khi thay đổi tham số thực nghiệm ......................... 66 Hình 4.7: (a) Phân cụm theo Phương pháp k-means; (b) Phân cụm theo Phương pháp Phân cụm tích lũy dựa trên Phương pháp k-means. ....................................................... 67 Hình 4.8: Thực nghiệm theo phương án 2 ..................................................................... 69 MỞ ĐẦU Những năm gần đây, ngành công nghệ thông tin chuyên nghiên cứu về các thuật toán và phương pháp sử dụng trong lĩnh vực khai phá dữ liệu đã có những bước tiến mới song song cùng với sự phát triển của ngành tin học nói chung. Đã có nhiều thuật toán mới được đưa ra nhằm trích rút thông tin, phân loại dự đoán đặc điểm của dữ liệu từ tập dữ liệu có trước. Đây là điều rất quan trọng đối với một xã hội phát triển trong đó đòi hỏi nhu cầu hiệu quả trong hoạt động. Trong vài năm trở lại đây, nhu cầu dự đoán hành vi khách hàng của các Ngân hàng đang tăng cao. Ngân hàng Quân đội (MB) cũng không nằm ngoài xu hướng trên. Mục đích của các Ngân hàng là làm thế nào để biết được rằng một khách hàng sẽ có khả năng cao là sử dụng một dịch vụ cụ thể của mình. Để giải quyết bài toán trên, phương pháp khai phá dữ liệu, dùng những thông tin có từ trước về tập khách hàng cũ để dự đoán hành vi của khách hàng mới. Tuy nhiên, vấn đề là phải áp dụng phương pháp nào để đảm bảo rằng công việc dự đoán là có hiệu quả nhất. Một trong những phương pháp hiện đại được đưa ra trong năm vừa rồi là phương pháp phân cụm tích lũy dựa trên một số phương pháp truyền thống. Nguyên tắc chung của phương pháp là áp dụng lặp lại nhiều lần đối với việc phân cụm để tạo ra nhiều cụm đã được phân cụm, rồi dựa trên các thông tin này để xây dựng lại các cụm. Công việc này sẽ đảm bảo rằng việc phân cụm là chính xác. Luận văn tập trung tìm hiểu phương pháp phân cụm tích lũy, phân tích nghiệp vụ của Ngân hàng Quân đội và tập dữ liệu khách hàng, đồng thời qua đó nêu ra cách áp dụng và xây dựng cài đặt ứng dụng dựa trên thuật toán phân cụm tích lũy dựa trên phương pháp k-means để dự đoán hành vi khách hàng mới. Nội dung của bản luận văn gồm có phần mở đầu, bốn chương và phần kết luận. Chương 1 Luận văn trình bày khái niệm phân cụm, các phương pháp phân cụm điển hình, xem xét các điểm mạnh, điểm yếu của từng phương pháp này. Chương 2 Luận văn trình bày một phương pháp phân cụm mới được đưa ra là phân cụm tích lũy. Phương pháp phân cụm tích lũy dựa trên phương pháp k-means được khảo sát sâu nhằm áp dụng vào bài toán ứng dụng Chương 3 Chương này, luận văn sẽ phân tích mô hình hoạt động kinh doanh của Ngân hàng Quân đội (MB) và xem xét cách thức áp dụng khai phá dữ liệu trong Ngân hàng này 2 Chương 4 Trong chương 3 luận văn đã phân tích thực trạng hoạt động kinh doanh cũng như việc lưu trữ dữ liệu của Ngân hàng Quân đội và nhu cầu cần thiết phải có một chương trình để có khả năng khai thác dữ liệu khách hàng đã có nhằm mục đích quảng bá hình ảnh và dịch vụ của Ngân hàng Quân đội, nhằm duy trì khách hàng đã có và có thêm khách hàng mới. Trong chương này sẽ tiến hành xây dựng ứng dụng nhằm phục vụ cho mục tiêu khai phá dữ liệu đã đề ra, đồng thời xây dựng và thực hiện các phương án thực nghiệm kết quả của ứng dụng. Luận văn này được thực hiện dưới sự hướng dẫn khoa học của TS. Hà Quang Thụy và được hỗ trợ một phần từ Đề tài QG.10-38. Tôi xin chân thành cảm ơn sâu sắc tới Thầy đã chỉ dẫn tận tình giúp tôi có thể hoàn thành bản luận văn này. Tôi xin chân thành cảm ơn các thầy giáo và các bạn trong bộ môn Các Hệ thống Thông tin đã có những góp ý hữu ích trong quá trình thực hiện bản luận văn. Tôi cũng vô cùng cảm ơn sự giúp đỡ và động viên khích lệ của người thân trong gia đình tôi, bạn bè và các đồng nghiệp trong Ngân hàng MB trong suốt quá trình thực hiện luận văn. 3 Chương 1. Khái quát về phân cụm 1.1 Khái quát về bài toán phân cụm dữ liệu Không giống sự phân loại và sự dự đoán dùng để phân tích lớp đối tượng, phân loại theo lớp, sự phân cụm phân tích đối tượng dữ liệu mà không tham chiếu đến các lớp đã được phân loại trước [1]. Nói chung, các lớp đã phân loại trước không xuất hiện trong dữ liệu có sẵn. Sự phân cụm có thể được sử dụng để tạo ra các lớp. Bài toán phân cụm có thể được phát biểu như sau: Cho một tập các đối tượng cho trước, yêu cầu phân các đối tượng trên thành các cụm sao cho các đối tượng trong cùng một nhóm là tương đối giống nhau, các đối tượng trong các nhóm khác nhau là rất khác nhau. Nói cách khác, các đối tượng được phân cụm dựa trên nguyên lý của sự cực đại hóa sự giống nhau trong lớp và tối thiểu hóa sự giống nhau giữa các lớp. Mỗi cụm được hình thành có thể được xem như một lớp của các đối tượng, mà từ đó có thể tạo ra các luật. Ví dụ, phân cụm có thể thực hiện trên dữ liệu khách hàng để nhận ra những tập khách hàng đồng nhất. Những cụm này có thể biểu diễn các nhóm đích riêng biệt cho việc quảng cáo. Hình 1.1 chỉ ra cụm 2-D của khách hàng ở trong một thành phố. Ba cụm của điểm dữ liệu rất rõ ràng. Hình 1.1: Một phần nhỏ của dữ liệu khách hàng về các vị trí khách hàng trong một thành phố, chỉ ra ba phân cụm dữ liệu, Mỗi trung tâm phân cụm được đánh dấu ‘+’ [1] Phân cụm là một lĩnh vực nghiên cứu đầy thách thức, trong đó, các ứng dụng tiềm năng của nó đưa ra những đòi hỏi riêng. Sau đây là các yêu cầu đặc trưng của phân cụm:  Tính mở rộng: nhiều thuật toán khai phá dữ liệu làm việc tốt trên những tập dữ liệu chứa ít đối tượng; tuy nhiên, một cơ sở dữ liệu lớn thường chứa hàng triệu đối tượng, đòi hỏi những thuật toán có khả năng mở rộng cao  Khả năng khám phá các phân cụm với các hình dạng ngẫu nhiên: nhiều thuật toán phân cụm xác định các cụm dựa trên đại lượng khoảng cách Euclidean hoặc Manhattan. Những thuật toán dựa trên đại lượng khoảng cách này thường tìm 4 được các cụm hình cầu với kích thước và mật độ tương tự nhau. Tuy nhiên, một cụm có thể có bất kì hình dạng nào khác. Cần phải phát triển một thuật toán phát hiện cụm với hình dạng khác nhau.  Các yêu cầu tối thiểu cho tri thức miền để xác định các tham số đầu vào: nhiều thuật toán đòi hỏi người dùng phải đưa tham số đầu vào (ví dụ như số cụm). Kết quả phân cụm có thể là rất nhậy cảm đối với tham số đầu vào. Các tham số đầu vào thường khó xác định, đặc biệt là đối với các đối tượng nhiều chiều.  Khả năng làm việc với dữ liệu nhiễu: hầu hết dữ liệu trên thế giới chứa những thành phần bên ngoài hoặc dữ liệu bị thiếu hụt, bị lỗi, một số thuật toán nhạy cảm với những loại dữ liệu trên dẫn tới việc phân cụm nghèo nàn.  Khả năng phân cụm tăng dần và không nhạy cảm với trình tự bản ghi đầu vào: một số thuật toán phân cụm không thể kết hợp dữ liệu thêm mới (nghĩa là, dữ liệu cập nhật) vào trong các cấu trúc phân cụm đang tồn tại, và do đó phải xác định một sự phân cụm mới từ đầu. Một số thuật toán phân cụm nhạy cảm với trình tự dữ liệu đầu vào. Điều này quan trọng đối với các thuật toán phân cụm tăng dần và thuật toán không nhạy cảm với thứ tự đầu vào.  Số chiều lớn: một cơ sở dữ liệu hoặc kho dữ liệu có thể chứa một số chiều hoặc các thuộc tính. Nhiều thuật toán phân cụm dùng tốt cho dữ liệu ít chiều, bao gồm chỉ hai hoặc ba chiều. Mắt con người dùng tốt cho việc đánh giá lên đến ba chiều. Tìm kiếm các phân cụm của các đối tượng dữ liệu trong không gian nhiều chiều là một thách thức.  Sự phân cụm dựa trên ràng buộc: các ứng dụng trong thế giới thực có thể cần sự phân cụm dưa trên nhiều loại ràng buộc khác nhau. Gỉa sử rằng công việc của bạn là tìm ra vị trí lựa chọn để đặt máy ATM, để quyết định việc này, bạn phải phân cụm và xem xét vị trí, đường cao tốc, kiểu của khách hàng trên cụm….  Tính thông dịch và hữu dụng: người dùng mong muốn kết quả phân cụm được thông dịch, hiểu và sử dụng được. Đó là, phân cụm cần được kết hợp với sự thông dịch ngữ nghĩa và các ứng dụng. Điều quan trọng là nghiên cứu làm thế nào một mục đích ứng dụng có thể tác động lên sự lựa chọn của các đặc tính phân cụm và các phương pháp. 1.2 Một số phương pháp phân cụm điển hình 1.2.1 Các phương pháp phân vùng Cho một cơ sở dữ liệu của n đối tượng hoặc dòng dữ liệu, một phương pháp phân cụm tạo ra k cụm của dữ liệu, trong đó mỗi vùng biểu diễn một cụm, và k  n . Phương 5 pháp này phân chia dữ liệu vào k nhóm, đáp ứng những yêu cầu sau: (1) mỗi nhóm phải chứa ít nhất một đối tượng và, (2) mỗi đối tượng phải thuộc duy nhất một nhóm [1]. Chú ý rằng yêu cầu thứ hai có thể bỏ qua trong một số kĩ thuật được miêu tả ở phần dưới. Đưa ra k là số lượng cụm để xây dựng, một phương thức phân cụm cần khởi tạo cụm. Sau đó sử dụng một kĩ thuật định vị trí lặp lại để cố gắng tăng sự cụm bằng cách rời các đối tượng từ một nhóm tới một nhóm khác. Tiêu chuẩn chung của một sự phân cụm tốt là các đối tượng trong cùng vùng là gần giống hoặc liên quan đến những đối tượng khác, trong khi các đối tượng của các cụm khác nhau lại rất khác nhau. Có rất nhiều kiểu tiêu chuẩn dành cho việc đánh giá chất lượng cụm. Để có được sự tối ưu toàn diện trong cụm dựa trên sự phân cụm sẽ đòi hỏi số lượng cực lớn của mọi sự phân cụm có thể. Thay vào đó, hầu hết các ứng dụng chấp nhận một trong hai phương pháp heuristic phổ biến: thuật toán k-means, nơi mỗi cụm được biểu diễn bởi giá trị trung bình của các giá trị trong cụm; và thuật toán k-medoids, trong đó mỗi cụm được biểu diễn bởi một trong các đối tượng gần trung tâm của cụm. Các phương thức cụm heuristic này làm việc tốt khi tìm kiếm các cụm hình cầu trong cơ sở dữ liệu nhỏ hoặc trung bình. Khi tìm kiếm các cụm với hình dạng phức tạp và cho tập dữ liệu lớn, các phương pháp phân cụm trên cần phải mở rộng.  Phương pháp k-means Thuật toán k-means có tham số đầu vào k, và phân một tập n đối tượng thành k cụm sao cho các đối tượng trong một cụm là tương đối giống nhau còn các đối tượng giữa các cụm lại có sự khác biệt khá rõ [1]. Sự giống nhau trong cụm được đánh giá theo giá trị trung bình của các đối tượng trong đoạn, còn có thể được xem như là “trung tâm của trọng lực” của cụm. Thuật toán xử lý như sau: Đầu tiên, nó ngẫu nhiên lựa chọn k các đối tượng mà mỗi đối tượng đại diện cho một trung bình hay trung tâm phân đoạn. Đối với mỗi đối tượng còn lại, một đối tượng được gán cho một cụm mà giống nó nhất, dựa trên khoảng cách giữa đối tượng và trung bình của đoạn. Nó sau đó sẽ tính trung bình mới cho mỗi đoạn. Xử lý này được lặp lại tới tận khi hàm tiêu chuẩn hội tụ. Thường hàm hội tụ sau được sử dụng: Trong đó x là điểm trong không gian biểu diễn đối tượng đưa ra, mi là trung bình của cụm C i (cả x và mi là đa chiều). Hàm này cố gắng tạo ra k cụm phân biệt nhau tới mức có thể. Thủ tục k trung bình được tổng kết ở hình bên dưới: 6 Thuật toán k means: Đầu vào: Số cụm k, và một cơ sở dữ liệu chứa n đối tượng Đầu ra: Một tập k cụm với trọng tâm của mỗi cụm Thủ tục 1. Lựa chọn ngẫu nhiên k đối tượng là trọng tâm khởi tạo của k cụm 2. Lặp 2.1. Gán mỗi đối tượng vào cụm có trọng tâm giống nhất đối tượng nhất so với các cụm khác 2.2. Cập nhật lại trọng tâm của các cụm, trong đó tọa độ của trọng tâm bằng giá trị trung bình tọa độ các đối tượng trong cụm. 3. Cho đến khi giá trị hàm mục tiêu không thay đổi Thuật toán cố gắng xác định k cụm mà tối thiểu hóa hàm mục tiêu đưa ra. Phương thức này có khả năng mở rộng và hoạt động hiệu quả trong khi xử lý các tập dữ liệu lớn bởi vì độ phức tạp tính toán của thuật toán là O (knt), trong đó n là tổng số đối tượng, k là số cụm, và t là số lần lặp lại, thông thường k < - Xem thêm -