ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ -------- Nguyễn Doãn Hiền ỨNG DỤNG MỘT SỐ THUẬT TOÁN PHÂN CỤM PHÂN TÍCH DỮ LIỆU NGÂN HÀNG LUẬN VĂN THẠC SỸ Hà Nội – 2006 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 1 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ -------- Nguyễn Doãn Hiền ỨNG DỤNG MỘT SỐ THUẬT TOÁN PHÂN CỤM PHÂN TÍCH DỮ LIỆU NGÂN HÀNG Ngành: Công nghệ Thông tin Mã số: 1.10 LUẬN VĂN THẠC SỸ Ngƣời hƣớng dẫn khoa học: PGS. Bùi Công Cƣờng Hà Nội – 2006 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 2 Lêi c¶m ¬n Sau một thời gian nghiên cứu và nỗ lực thực hiện, luận văn “Ứng dụng một số thuật toán phân cụm phân tích dữ liệu Ngân hàng” đã cơ bản hoàn thành. Ngoài sự cố gắng của bản thân, tôi đã nhận đƣợc sự giúp đỡ từ nhà trƣờng, thầy cô giáo, gia đình và bạn bè. Trƣớc hết, tôi xin đƣợc cảm ơn mẹ, ngƣời đã động viên và chăm sóc tôi trong quá trình học tập và hoàn thành luận văn. Tôi xin cảm ơn các thầy cô giáo trƣờng Đại học Công nghệ - Đại học Quốc gia Hà Nội đã truyền đạt những kiến thức quí báu cho tôi cũng nhƣ các học viên lớp Cao học Công nghệ K10T3. Đặc biệt, tôi xin cảm ơn sâu sắc tới thầy giáo Bùi Công Cƣờng, ngƣời đã trực tiếp tận tình giúp đỡ, hƣớng dẫn tôi trong quá trình thực hiện luận văn này. Nhân đây, tôi cũng gửi lời cảm ơn tới các bạn bè cùng lớp K10T3 đã cùng sát cánh và động viên tôi trong những ngày cùng nhau học tập tại trƣờng Đại học Công nghệ - Đại học Quốc Gia Hà Nội. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 3 MỤC LỤC MỞ ĐẦU . MỤC TIÊU, NỘI DUNG VÀ PHƢƠNG PHÁP NGHIÊN CỨU . TÓM TẮT NỘI DUNG CÁC CHƢƠNG . PHÂN CỤM DỮ LIỆU .1 KHÁI NIỆM PHÂN CỤM DỮ LIỆU .2 CÁC BƢỚC CƠ BẢN ĐỂ PHÂN CỤM .3 CÁC ỨNG DỤNG CỦA PHÂN CỤM .4 CÁC LOẠI ĐẶC TRƢNG .5 CÁC ĐỊNH NGHĨA PHÂN CỤM .1 Định nghĩa phân cụm .2 Định nghĩa phân cụm mờ .1 Độ đo không tƣơng tự .3 Độ đo gần gũi giữa các tập con của X .4 Các độ đo gần gũi giữa hai điểm .5 Các hàm gần gũi giữa một điểm và một tập .6 Các hàm gần gũi giữa hai tập .7 Đánh giá phân cụm . MỘT SỐ THUẬT TOÁN PHÂN CỤM .1 GIỚI THIỆU VỀ CÁC THUẬT TOÁN PHÂN CỤM .1 Số các phân cụm .2 Phân loại các thuật toán phân cụm .2 THUẬT TOÁN PHÂN CỤM TUẦN TỰ .1 Thuật toán phân cụm tuần tự .2 Ƣớc lƣợng số lƣợng các phân cụm . Một thuật toán BSAS cải tiến . Sơ đồ tuần tự với hai ngƣỡng . Thực hiện tinh chỉnh .3 THUẬT TOÁN PHÂN CỤM K-MEANS .1 Thuật toán K-means .2 Các bƣớc thực hiện thuật toán K-means .3 Ví dụ về áp dụng thuật toán K-means .4 Một số vấn đề và ƣu, nhƣợc điểm của K-means .5 Độ phức tạp của thuật toán K-means .4 THUẬT TOÁN PHÂN CỤM MỜ K-MEANS (FKM) .1 Khái niệm về tập mờ và phân cụm mờ . 53 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.2 Thuật toán phân cụm mờ K-means .3 Mô tả thuật toán .4 Độ phức tạp thuật toán .5 THUẬT TOÁN PHÂN CỤM HIERACHICAL .1 Nguyên lý thực hiện .2 Mô tả thuật toán .3 Ví dụ về thuật toán phân cấp.4 Ƣu, nhƣợc điểm của thuật toán .6 THUẬT TOÁN PHÂN CỤM K-LÁNG GIỀNG GẦN.1 Thuật toán K-láng giềng gần. Cách thức thực hiện thuật toán KNN . Một ví dụ áp dụng thuật toán KNN . Ƣu, nhƣợc điểm của thuật toán KNN . XÂY DỰNG CHƢƠNG TRÌNH PHÂN CỤM.1 PHÂN TÍCH CÁC MODULE .1 Module chuẩn bị dữ liệu .2 Tinh chỉnh dữ liệu .3 Hàm tính khoảng cách .2 CHƢƠNG TRÌNH MÔ PHỎNG CÁC THUẬT TOÁN .1 Giới thiệu chƣơng trình .2 Chuyển đổi và tinh chỉnh dữ liệu .3 Thuật toán K-means .4 Thuật toán phân cụm phân cấp (Hierachical) .5 Thuật toán Fuzzy K-means . ỨNG DỤNG PHÂN CỤM DỮ LIỆU GIAO DỊCH ATM.1 PHÁT BIỂU BÀI TOÁN . ÁP DỤNG VÀO CHƢƠNG TRÌNH ĐÃ XÂY DỰNG .1 Phƣơng pháp áp dụng .2 Đặc tả dữ liệu và cách thức thực hiện .3 Phân tích, đánh giá kết quả . TÓM TẮT KẾT QUẢ . PHƢƠNG HƢỚNG PHÁT TRIỂN. 85 TÀI LIỆU THAM KHẢO .87 PHỤ LỤC 1: MÃ NGUỒN CHƢƠNG TRÌNH.88 1 MODULE TÍNH KHOẢNG CÁCH GIỮA CÁC PHẦN TỬ .1 Tính khoảng cách theo Manhattan .2 Tính khoảng cách theo công thức Euclide .3 Tính khoảng cách hỗn hợp (công thức Kaufman và Rousseeuw) . MODULE THỰC HIỆN THUẬT TOÁN K-MEANS . MODULE THỰC HIỆN THUẬT TOÁN HIERACHICAL . 99 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 5 PHỤ LỤC 2: MÔ TẢ DỮ LIỆU GIAO DỊCH . Cấu trúc bảng dữ liệu . Danh sách mã loại thẻ . Danh sách mã giao dịch . Định dạng dữ liệu sau khi chuyển đổi . Định dạng dữ liệu sau phân cụm bằng thuật toán K-means . Định dạng dữ liệu sau phân cụm bằng thuật toán Hierachical . Định dạng cây phân cấp . 105 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 6 MỞ ĐẦU Đối với các Ngân hàng hiện nay, nắm đƣợc khách hàng là một trong những điểm mấu chốt tạo nên thành công trong kinh doanh. Để đạt đƣợc điều này, việc cần thiết đó là thiết lập đƣợc chiến lƣợc khách hàng đúng đắn để sao cho giành đƣợc các khách hàng mới và giữ đƣợc các khách hàng có chất lƣợng cao. Để đạt đƣợc những mục tiêu đó, các Ngân hàng đã xây dựng các hệ thống dữ liệu về khách hàng, từ đó có thể phân tích và xây dựng các chiến lƣợc kinh doanh cho mình. Thực tế cho thấy rằng, thay vì nhắm vào tất cả các khách hàng để đối xử, khuyến khích, Ngân hàng có thể lựa chọn các khách hàng đáp ứng một tiêu chuẩn nào đó về lợi nhuận dựa trên các thuộc tính giao dịch hay những thuộc tính khác của khách hàng [7]. Trong những năm gần đây, hệ thống máy giao dịch tự động (ATM – Automatic Teller Machine) đƣợc các Ngân hàng tại Việt Nam triển khai và phát triển khá mạnh mẽ. Hệ thống này cho phép khách hàng thực hiện giao dịch một cách tiện lợi về thời gian (online 24/7) cũng nhƣ cung cấp các dịch vụ (vấn tin, chuyển khoản, rút tiền, thanh toán hoá đơn, cách dịch vụ tín dụng . Vì vậy, có thể nói hệ thống ATM trở thành một trong những kênh quan trọng trong các kênh giao dịch của Ngân hàng cung cấp cho khách hàng. Tuy nhiên, để phát huy hiệu quả của hệ thống này, ngoài các thông tin cố định nhƣ lƣợng thẻ, lƣợng giao dịch, số máy ATM… Ngân hàng cần biết đƣợc các thuộc tính ẩn của khách hàng để đề ra chiến lƣợc phát triển đúng đắn cho loại hình dịch vụ này. Đó chính là lý do cần đến khoa học khai phá dữ liệu mà ở đây cụ thể hơn, chúng ta sẽ nghiên cứu về các thuật toán phân cụm dữ liệu để tìm ra các thuộc tính ẩn đó. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 7 CHƢƠNG 1. MỤC TIÊU, NỘI DUNG VÀ PHƢƠNG PHÁP NGHIÊN CỨU Mục tiêu của luận văn Nắm bắt đƣợc cơ sở lý thuyết của các thuật toán phân cụm, đƣa ra phƣơng hƣớng giải quyết cho bài toán áp dụng vào thực tế để thực hiện bài toán phân cụm dữ liệu ATM trong Ngân hàng. Nội dung chính của luận văn Luận văn có các nội dung chính nhƣ sau: - Khái quát cơ sở lý thuyết về phân cụm dữ liệu. - Tìm hiểu, trình bày một số thuật toán phân cụm đã và đang đƣợc sử dụng trên thế giớ1. - Xây dựng chƣơng trình mô phỏng các thuật toán phân cụm dữ liệu. - Áp dụng vào bào toán phân cụm dữ liệu ATM của Ngân hàng Đầu tƣ và Phát triển Việt nam (BIDV). Phƣơng pháp nghiên cứu - Kết hợp lý thuyết, thực nghiệm và thực tế để đƣa ra các đánh giá, kết luận. - Học hỏi, nghiên cứu, phân tích các lý thuyết về các lĩnh vực có liên quan trong luận văn, từ các nguồn: các thầy giáo, cô giáo, các nhà khoa học, các chuyên gia, các đồng nghiệp, sách, báo, tài liệu, internet, 5. - Tìm hiểu trên thực tế các yêu cầu, các tiêu chuẩn và các đánh giá về các hệ thống. - Xây dựng các sơ đồ cấu trúc, nguyên lý cho các hệ thống sao cho phù hợp với yêu cầu và khả năng, xây dựng mô hình thực nghiệm. - Đƣa ra kết luận từ kết quả nghiên cứu. LUAN VAN CHAT LUONG download : add luanvanchat@agmail. TÓM TẮT NỘI DUNG CÁC CHƢƠNG Luận văn có 4 chƣơng và phần mở đầu, kết luận: Phần mở đầu Phần này nêu lên sự cần thiết của vấn đề phân cụm dữ liệu nói chung và nhất là việc áp dụng vào phân tích dữ liệu trong Ngân hàng để từ đó định hƣớng cho việc mở rộng các dịch vụ với các dối tƣợng khách hàng hợp lý. Chƣơng một: Tổng quan Chƣơng này nêu lên mục tiêu, nội dung và phƣơng pháp nghiên cứu để hoàn thành bản luận văn này. Chƣơng hai: Phân cụm dữ liệu Chƣơng này nêu lên khái niệm cơ bản về phân cụm dữ liệu, các bƣớc cơ bản để thực hiện một thuật toán phân cụm, các loại đặc trƣng của phân cụm và các định nghĩa liên quan đến phân cụm. Chƣơng hai có đề cập đến một số ứng dụng của việc phân cụm và một nội dung quan trọng nhất của các thuật toán phân cụm là các độ đo. Chƣơng ba: Một số thuật toán phân cụm dữ liệu Chƣơng ba giới thiệu chi tiết về một số thuật toán phân cụm hiện đang đƣợc áp dụng phổ biến, đó là các thuật toán phân cụm tuần tự (Sequence), thuật toán phân cụm phân cấp (Hierachical), thuật toán K-trung bình (K-Means), K- trung bình mờ (Fuzzy K-Means) và thuật toán K láng giềng gần (K-Nearest Neighbour). Chƣơng bốn: Xây dựng chƣơng trình phân cụm LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 9 Chƣơng bốn giới thiệu chƣơng trình thực hiện một số thuật toán nêu tại Chƣơng ba bao gồm phần phân tích các module thực hiện và phần chƣơng trình thực hiện. Chƣơng năm: Ứng dụng phân cụm dữ liệu giao dịch ATM Chƣơng năm giới thiệu ứng dụng bài toán phân cụm vào việc phân tích dữ liệu giao dịch ATM của Ngân hàng, cụ thể là phát biểu bài toán, nêu phƣơng pháp áp dụng, đặc tả dữ liệu, phân tích đánh giá kết quả đầu ra và đề xuất phƣơng hƣớng phát triển của chƣơng trình. Phần kết luận Phần này nêu kết quả của luận văn và định hƣớng phát triển trong tƣơng lai.
Luận văn ThS: Ứng dụng thuật toán phân cụm phân tích dữ liệu ngân hàng
Luận văn thạc sĩ VNU UET nghiên cứu ứng dụng thuật toán phân cụm trong phân tích dữ liệu ngân hàng, góp phần nâng cao công nghệ thông tin.
Trường đại học
Trường Đại học Công nghệ - Đại học Quốc gia Hà NộiChuyên ngành
Công nghệ Thông tinNgười đăng
Ẩn danhThể loại
Luận văn thạc sỹPhí lưu trữ
35 PointMục lục chi tiết
THÔNG TIN CHI TIẾT
Tác giả: Nguyễn Doãn Hiền
Người hướng dẫn: PGS. Bùi Công Cường
Trường học: Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội
Chuyên ngành: Công nghệ Thông tin
Đề tài: Ứng dụng một số thuật toán phân cụm phân tích dữ liệu ngân hàng
Loại tài liệu: Luận văn thạc sỹ
Năm xuất bản: 2006
Địa điểm: Hà Nội
Trích đoạn nội dung tài liệu
Nội dung được bảo vệ bản quyền — Tải xuống đầy đủ