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.
Phục lục mã nguồn chƣơng trình Mã nguồn thực hiện các thuật toán phân cụm và một số hàm liên quan nhƣ chuyển đổi dữ liệu, tinh chỉnh dữ liệu trƣớc khi phân cụm, tính khoảng cách và một số hàm khác liên quan. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 10 CHƢƠNG 2. PHÂN CỤM DỮ LIỆU 2.1 KHÁI NIỆM PHÂN CỤM DỮ LIỆU Phân cụm dữ liệu là quá trình phân chia một tập dữ liệu ban đầu thành các cụm dữ liệu sao cho các phần tử trong một cụm “tƣơng tự” với nhau và các phần tử trong các cụm khác nhau sẽ “không tƣơng tự”. Phân cụm dữ liệu nhằm tìm kiếm, phát hiện các cụm, các mẫu dữ liệu trong tập dữ liệu lớn, từ đó cung cấp thông tin hữu ích cho việc ra quyết định.
Hình vẽ sau mô phỏng vấn đề phân cụm: Hình 2.1: ví dụ phân cụm Trong hình vẽ trên, sau khi phân cụm chúng ta thu đƣợc bốn cụm trong đó các phần tử “gần nhau” hay là “tƣơng tự” thì đƣợc xếp vào một cụm, trong khi đó các phần tử “xa nhau” hay “không tƣơng tự” thì thuộc về các cụm khác nhau. Trong phân cụm dữ liệu khái niệm (Concept Clustering), hai hoặc nhiều đối tƣợng cùng đƣợc xếp vào một cụm nếu chúng có chung một định nghĩa về khái niệm hoặc xấp xỉ với các khái niệm mô tả cho trƣớc. Trong học máy, phân cụm dữ liệu đƣợc xem là vấn đề học không có giám sát vì nó phải đi giải quyết vấn đề tìm một cấu trúc trong tập hợp các dữ liệu chƣa biết trƣớc các thông tin về lớp hay các thông tin về tập ví dụ huấn luyện. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 11 Trong nhiều trƣờng hợp, khi phân lớp đƣợc xem là vấn đề học có giám sát thì phân cụm dữ liệu là một bƣớc trong phân lớp dữ liệu, trong đó phân cụm dữ liệu sẽ khởi tạo các lớp cho phân lớp bằng các xác định các nhãn cho các nhóm dữ liệu.
Một vấn đề thƣờng gặp trong phân cụm dữ liệu là hầu hết các dữ liệu cần cho phân cụm đều có chứa nhiễu do quá trình thu thập thiếu chính xác hoặc thiếu đầy đủ, vì vậy cần phải xây dựng chiến lƣợc cho bƣớc tiền xử lý dữ liệu nhặm khắc phục và loại bỏ nhiễu trƣớc khi bƣớc vào giai đoạn phân tích phân cụm dữ liệu. “Nhiễu” ở đây có thể là các đối tƣợng dữ liệu không chính xác, hoặc là các đối tƣợng khuyết thiếu thông tin về một số thuộc tính. Một trong các kỹ thuật xử lý nhiễu phổ biến là việc thay thế giá trị của các thuộc tính của đối tƣợng nhiễu bằng giá trị thuộc tính tƣơng ứng của đối tƣợng dữ liệu gần nhất.2 CÁC BƢỚC CƠ BẢN ĐỂ PHÂN CỤM - Chọn lựa đặc trƣng: các đặc trƣng phải đƣợc chọn lựa một cách hợp lý để có thể mã hoá nhiều nhất thông tin liên quan đến công việc quan tâm. Mục tiêu chính là phải giảm thiểu sự dƣ thừa thông tin giữa các đặc trƣng.
Các đặc trƣng cần đƣợc tiền xử lý trƣớc khi dùng chúng trong các bƣớc sau. - Chọn độ đo gần gũi: đây là một độ đo chỉ ra mức độ tƣơng tự hay không tƣơng tự giữa hai vectơ đặc trƣng. Phải đảm bảo rằng tất cả các vectơ đặc trƣng góp phần nhƣ nhau trong việc tính toán độ đo gần gũi và không có đặc trƣng nào át hẳn đặc trƣng nào, điều này đƣợc đảm bảo bởi quá trình tiền xử lý. - Tiêu chuẩn phân cụm: điều này phụ thuộc vào sự giải thích của chuyên gia cho thuật ngữ “dễ nhận thấy” dựa vào loại của các cụm đƣợc chuyên gia cho rằng đang ẩn giấu dƣới tập dữ liệu.
Chẳng hạn, một cụm loại chặt của véctơ đặc trƣng trong không gian n chiều có thể dễ nhận thấy theo một tiêu chuẩn, trong khi một cụm loại “dài và mỏng” lại có thể đƣợc dễ nhận thấy bởi một LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 12 tiêu chuẩn khác. Tiêu chuẩn phân loại có thể đƣợc diễn đạt bởi hàm chi phí hay một vài loại quy tắc khác. - Thuật toán phân loại: cần lựa chọn một sơ đồ thuật toán riêng biệt nhằm làm sáng tỏ cấu trúc phân cụm của tập dữ liệu. - Công nhận kết quả: khi đã có kết quả phân loại thì ta phải kiểm tra tính đúng đắn của nó.
Điều này thƣờng đƣợc thực hiện bởi việc dùng các kiểm định phù hợp. - Giải thích kết quả: trong nhiều trƣờng hợp, chuyên gia trong lĩnh vực ứng dụng phải kết hợp kết quả phân loại với những bằng chứng thực nghiệm và phân tích để đƣa ra các kết luận đúng đắn. Trong một số trƣờng hợp, nên có cả bƣớc phân tích khuynh hƣớng phân cụm, trong bƣớc này có các kiểm định khác nhau để chỉ ra tập dữ liệu có hay không một cấu trúc phân cụm. Ví dụ nhƣ tập dữ liệu của ta có thể hoàn toàn ngẫu nhiên vì vậy mọi cố gắng phân cụm đều là vô nghĩa.
Các lựa chọn khác nhau của các đặc trƣng, độ đo gần gũi, tiêu chuẩn phân cụm có thể dẫn tới các kết quả phân cụm khác nhau.3 CÁC ỨNG DỤNG CỦA PHÂN CỤM Phân cụm là một công cụ quan trọng trong một số ứng dụng, sau đây là một số ứng dụng của nó: - Giảm dữ liệu: Từ một số lƣợng lớn dữ liệu, phân cụm sẽ nhóm các dữ liệu này thành cụm dữ liệu nhỏ dễ nhận thấy sau đó xử lý mỗi cụm nhƣ một đối tƣợng đơn. - Rút ra các giả thuyết: Các giả thuyết này có liên quan đến tính tự nhiên của dữ liệu phải đƣợc kiểm tra bởi việc dùng một số tập dữ liệu khác. - Kiểm định giả thuyết: Phân cụm để xét xem có tồn tại một cụm nào đó trong tập dữ liệu thoả mãn các giả thiết đã cho hay không. - Dự đoán dựa trên các cụm: Trƣớc hết ta phải phân cụm một tập dữ liệu thành các cụm mang đặc điểm của các dạng mà nó chứa.
Sau đó, khi có một LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 13 dạng mới chƣa biết xác định xem nó có khả năng thuộc về cụm nào nhất và dự đoán đƣợc một số đặc điểm của dạng này nhờ các đặc trƣng chung của cả cụm. Trong thực tế, phân cụm đƣợc áp dụng vào nhiều lĩnh vực khác nhau nhƣ: - Tìm kiếm dữ liệu trên mạng: kết quả đƣợc phân thành các cụm tuỳ theo độ tƣơng tự với dữ liệu cần tìm. - Marketing: trợ giúp cán bộ thị trƣờng phát hiện đƣợc những phân đoạn thị trƣờng để có chiến lƣợc, sản phẩm hợp lý đối với các phân đoạn đó. - Phân loại khách hàng sử dụng các sản phẩm của Ngân hàng và các ngành tài chính, bảo hiểm.
- Lập bản đồ thành phố theo nhóm các loại nhà ở, giá trị tài sản hay vị trí địa lý.4 CÁC LOẠI ĐẶC TRƢNG Có 4 loại đặc trƣng đó là: - Các đặc trƣng danh nghĩa (nominal): gồm các đặc trƣng mà các giá trị của nó mã hoá các trạng thá1. Chẳng hạn cho một đặc trƣng là giới tính của một ngƣời thì các giá trị có thể của nó là 1 ứng với nam và 0 ứng với nữ. Rõ ràng là bất kỳ sự so sánh về lƣợng nào giữ các giá trị loại này đều vô nghĩa. - Các đặc trƣng thứ tự (ordinal): là các đặc trƣng mà các giá trị của nó có thể đƣợc sắp một cách có ý nghĩa.
Ví dụ về một đặc trƣng thể hiện sự hoàn thành khoá học của một sinh viên. Giả sử các giá trị có thể là 4, 3, 2, 1 tƣơng ứng với với việc xếp loại kết quả học tập của sinh viên là: “xuất sắc”, “giỏi”, “khá”, trung bình khá”, “trung bình”. Các giá trị này đƣợc sắp xếp theo một thứ tự có ý nghĩa nhƣng sự so sánh giữa hai giá trị liên tiếp là không quan trọng lắm về lƣợng. - Các đặc trƣng đo theo khoảng cách (interval-scaled) Với một đặc trƣng cụ thể nếu sự khác biệt giữa hai giá trị là có ý nghĩa về mặt số lƣợng thì ta có đặc trƣng đo theo khoảng (còn gọi là thang khoảng).
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 14 Ví dụ về đặc trƣng nhiệt độ, nếu từ 10 – 15 độ thì đƣợc coi là rét đậm, còn nếu dƣới 10 độ đƣợc coi là rét hạ1. Vì vậy mỗi khoảng nhiệt độ mang một ý nghĩa riêng. - Các đặc trƣng đo theo tỷ lệ (ratio-scaled): Cũng với ví dụ nhiệt độ ở trên ta không thể coi tỷ lệ giữa nhiệt độ Hà Nội 10 độ với nhiệt độ Matxcơva 1 độ mang ý nghĩa Hà Nội nóng gấp 10 lần Maxcơva. Trong khi đó, một ngƣời nặng 100kg đƣợc coi là nặng gấp 2 lần một ngƣời nặng 50kg, đặc trƣng cân nặng là một đặc trƣng đo theo tỷ lệ (thang tỷ lệ).