Nghiên Cứu Phương Pháp Phân Cụm Tích Lũy Tại Ngân Hàng Thương Mại Cổ Phần Quân Đội

Chuyên đề nghiên cứu Phương Pháp Phân Cụm Tích Lũy Trong Ngân Hàng Thương Mại Cổ Phần Quân Đội, cập nhật xu hướng mới, giá trị tham khảo cao cho

• Tác giả: Phạm Thị Ánh
• Người hướng dẫn: PGS. Hà Quang Thụy
• Trường học: Đại Học Quốc Gia Hà Nội
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: 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
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2011
• Địa điểm: Hà Nội

Mục lục chi tiết

• MỞ ĐẦU
• 1. 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
• 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
• 1.2.2. Phương pháp k-means
• 1.2.3. Phương pháp k-medoids
• 1.2.4. Phương pháp phân cụm trong cơ sở dữ liệu lớn CLARANS
• 2. CHƯƠNG 2: PHƯƠNG PHÁP PHÂN CỤM TÍCH LŨY
• 2.1. Giới thiệu phương pháp phân cụm tích lũy
• 2.2. Sự kết hợp bầu cử đa số của các thuật toán phân cụm
• 2.3. Một số thuật toán phân cụm tích lũy
• 2.4. Phân cụm tích lũy dựa trên K-Means
• 2.5. Phân cụm tích lũy dựa trên lan truyền quan hệ
• 3. 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
• 3.1. Một số mô hình khai phá dữ liệu ngân hàng
• 3.2. Hệ thống dịch vụ Ngân hàng quân đội
• 3.2.1. Hệ thống các dịch vụ
• 3.2.2. Hệ thống dữ liệu
• 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
• 4. CHƯƠNG 4: THỰC NGHIỆM VÀ ĐÁNH GIÁ
• 4.1. Mục đích xây dựng và vai trò của ứng dụng
• 4.2. Mô hình thực nghiệm
• 4.3. Dữ liệu thực nghiệm
• 4.4. Công cụ thực nghiệm
• 4.5. Thực nghiệm và đánh giá
• 4.5.1. Môi trường thực nghiệm
• 4.5.2. Mô tả quy trình thực nghiệm
• 4.5.3. Kết quả thực nghiệm và đánh giá nhận xét
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Khái quát về phân cụm

Phân cụm là một kỹ thuật quan trọng trong khai phá dữ liệu, cho phép nhóm các đối tượng tương tự nhau thành các cụm. Bài toán phân cụm dữ liệu không giống như phân loại, vì không có lớp đã biết trước. Mục tiêu chính là tối đa hóa sự tương đồng trong cùng một cụm và tối thiểu hóa sự tương đồng giữa các cụm khác nhau. Các yêu cầu đặc trưng của phân cụm bao gồm tính mở rộng, khả năng khám phá các hình dạng ngẫu nhiên, và khả năng làm việc với dữ liệu nhiễu. Đặc biệt, phân cụm cần phải có tính thông dịch và hữu dụng, giúp người dùng dễ dàng hiểu và áp dụng kết quả. Những yêu cầu này đặt ra thách thức lớn cho các nhà nghiên cứu và phát triển thuật toán phân cụm.

1.1. Khái quát về bài toán phân cụm dữ liệu

Bài toán phân cụm có thể được phát biểu như sau: cho một tập hợp các đối tượng, yêu cầu phân chia chúng thành các cụm sao cho các đối tượng trong cùng một cụm là tương đối giống nhau. Phân cụm có thể được áp dụng trong nhiều lĩnh vực, từ phân tích hành vi khách hàng đến nhận diện mẫu trong dữ liệu lớn. Ví dụ, trong ngân hàng, phân cụm có thể giúp nhận diện các nhóm khách hàng có hành vi tương tự, từ đó tối ưu hóa chiến lược marketing và dịch vụ. Việc phân cụm không chỉ giúp tổ chức dữ liệu mà còn tạo ra những hiểu biết sâu sắc về cấu trúc và mối quan hệ giữa các đối tượng trong tập dữ liệu.

II. Một số phương pháp phân cụm điển hình

Có nhiều phương pháp phân cụm khác nhau, trong đó hai phương pháp phổ biến nhất là k-means và k-medoids. Phương pháp k-means phân chia dữ liệu thành k cụm dựa trên giá trị trung bình của các đối tượng trong cụm. Phương pháp này có ưu điểm là đơn giản và hiệu quả với tập dữ liệu lớn. Tuy nhiên, nó nhạy cảm với các giá trị ngoại lệ. Ngược lại, k-medoids sử dụng các đối tượng thực tế làm trung tâm cụm, giúp giảm thiểu ảnh hưởng của các giá trị ngoại lệ. Cả hai phương pháp đều có thể được áp dụng trong ngân hàng để phân tích hành vi khách hàng và tối ưu hóa dịch vụ.

2.1. Các phương pháp phân vùng

Phương pháp phân vùng là một trong những kỹ thuật phân cụm cơ bản, trong đó dữ liệu được chia thành k nhóm. Mỗi nhóm phải chứa ít nhất một đối tượng và mỗi đối tượng chỉ thuộc về một nhóm duy nhất. Phương pháp này thường sử dụng các tiêu chí đánh giá chất lượng cụm để tối ưu hóa sự phân chia. Các thuật toán như k-means và k-medoids là những ví dụ điển hình của phương pháp phân vùng, giúp tổ chức và phân tích dữ liệu một cách hiệu quả.

2.2. Các phương pháp phân cấp

Phân cụm phân cấp là một phương pháp khác, trong đó các cụm được xây dựng theo cấu trúc cây. Phương pháp này cho phép người dùng dễ dàng theo dõi mối quan hệ giữa các cụm. Có hai loại chính: phân cụm từ dưới lên (agglomerative) và từ trên xuống (divisive). Phân cụm phân cấp thường được sử dụng trong các lĩnh vực như sinh học và phân tích thị trường, nơi mà mối quan hệ giữa các đối tượng là rất quan trọng.

III. Phương pháp phân cụm tích lũy

Phương pháp phân cụm tích lũy là một kỹ thuật mới, kết hợp nhiều lần phân cụm để tạo ra các cụm chính xác hơn. Nguyên tắc của phương pháp này là lặp lại quá trình phân cụm, từ đó cải thiện độ chính xác của các cụm. Phương pháp này đặc biệt hữu ích trong các ứng dụng ngân hàng, nơi mà dữ liệu khách hàng thường rất lớn và phức tạp. Việc áp dụng phương pháp này giúp ngân hàng có thể dự đoán hành vi khách hàng một cách hiệu quả hơn.

3.1. Giới thiệu phương pháp phân cụm tích lũy

Phân cụm tích lũy sử dụng các thuật toán truyền thống như k-means và kết hợp chúng với các phương pháp mới để cải thiện kết quả phân cụm. Phương pháp này cho phép ngân hàng phân tích dữ liệu khách hàng một cách sâu sắc hơn, từ đó đưa ra các quyết định kinh doanh chính xác hơn. Việc áp dụng phương pháp này không chỉ giúp tối ưu hóa dịch vụ mà còn nâng cao trải nghiệm của khách hàng.

3.2. Sự kết hợp bầu cử đa số của các thuật toán phân cụm

Sự kết hợp bầu cử đa số là một kỹ thuật quan trọng trong phân cụm tích lũy, cho phép kết hợp nhiều kết quả phân cụm khác nhau để tạo ra một kết quả cuối cùng chính xác hơn. Kỹ thuật này giúp giảm thiểu sai sót và tăng cường độ tin cậy của các cụm. Trong bối cảnh ngân hàng, điều này có thể giúp nhận diện các nhóm khách hàng tiềm năng và tối ưu hóa các chiến lược marketing.

IV. Mô hình khai phá dữ liệu dịch vụ khách hàng Ngân hàng quân đội

Mô hình khai phá dữ liệu trong ngân hàng quân đội tập trung vào việc sử dụng các kỹ thuật phân cụm để phân tích hành vi khách hàng. Việc áp dụng các phương pháp phân cụm giúp ngân hàng nhận diện các nhóm khách hàng khác nhau, từ đó tối ưu hóa dịch vụ và tăng cường sự hài lòng của khách hàng. Mô hình này không chỉ giúp ngân hàng duy trì khách hàng hiện tại mà còn thu hút thêm khách hàng mới.

4.1. Một số mô hình khai phá dữ liệu ngân hàng

Các mô hình khai phá dữ liệu trong ngân hàng thường sử dụng các thuật toán phân cụm để phân tích dữ liệu khách hàng. Những mô hình này giúp ngân hàng hiểu rõ hơn về hành vi và nhu cầu của khách hàng, từ đó đưa ra các quyết định kinh doanh chính xác hơn. Việc áp dụng các mô hình này không chỉ giúp tối ưu hóa dịch vụ mà còn nâng cao trải nghiệm của khách hàng.

4.2. Hệ thống dịch vụ Ngân hàng quân đội

Hệ thống dịch vụ của ngân hàng quân đội được thiết kế để đáp ứng nhu cầu của khách hàng một cách hiệu quả nhất. Việc áp dụng các kỹ thuật khai phá dữ liệu giúp ngân hàng có thể phân tích và dự đoán hành vi khách hàng, từ đó tối ưu hóa các dịch vụ và sản phẩm. Hệ thống này không chỉ giúp ngân hàng duy trì khách hàng hiện tại mà còn thu hút thêm khách hàng mới.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh phát triển mạnh mẽ của ngành công nghệ thông tin và nhu cầu khai phá dữ liệu ngày càng tăng, việc áp dụng các phương pháp phân cụm dữ liệu trở thành một lĩnh vực nghiên cứu quan trọng. Theo ước tính, các ngân hàng thương mại hiện đang lưu trữ hàng triệu bản ghi khách hàng với đa dạng thông tin giao dịch, nhân khẩu học và hành vi sử dụng dịch vụ. Tuy nhiên, việc khai thác hiệu quả nguồn dữ liệu khổng lồ này để dự đoán hành vi khách hàng mới vẫn còn nhiều thách thức. Luận văn tập trung nghiên cứu phương pháp phân cụm tích lũy, một kỹ thuật hiện đại kết hợp nhiều thuật toán phân cụm truyền thống nhằm nâng cao độ chính xác và ổn định của kết quả phân cụm.

Mục tiêu chính của nghiên cứu là xây dựng và áp dụng phương pháp phân cụm tích lũy dựa trên thuật toán k-means để phân tích dữ liệu khách hàng tại Ngân hàng Thương mại Cổ phần Quân đội (MB). Phạm vi nghiên cứu bao gồm dữ liệu khách hàng MB trong khoảng thời gian gần đây, với trọng tâm là khai phá hành vi sử dụng dịch vụ ngân hàng. Ý nghĩa của nghiên cứu được thể hiện qua việc cải thiện khả năng dự đoán hành vi khách hàng, từ đó hỗ trợ ngân hàng trong việc quảng bá dịch vụ, duy trì khách hàng hiện tại và thu hút khách hàng mới, góp phần nâng cao hiệu quả kinh doanh và cạnh tranh trên thị trường.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên các lý thuyết và mô hình phân cụm dữ liệu, trong đó nổi bật là:

• Phân cụm k-means: Thuật toán phân cụm phổ biến, phân chia tập dữ liệu thành k cụm sao cho tổng bình phương khoảng cách giữa các điểm dữ liệu và trung tâm cụm là nhỏ nhất. Ưu điểm là tính mở rộng và hiệu quả trên tập dữ liệu lớn, nhưng nhược điểm là phụ thuộc vào số lượng cụm k và điểm khởi tạo trung tâm cụm.

• Phân cụm tích lũy (Ensemble Clustering): Phương pháp kết hợp kết quả phân cụm từ nhiều thuật toán hoặc nhiều lần chạy thuật toán với các tham số khác nhau để tạo ra kết quả phân cụm thống nhất và ổn định hơn. Phương pháp này sử dụng ma trận kết hợp (co-association matrix) và lược đồ bầu cử đa số để xác định các cụm cuối cùng.

• Lan truyền quan hệ (Affinity Propagation - AP): Thuật toán phân cụm dựa trên truyền thông điệp giữa các điểm dữ liệu để xác định các điểm đại diện (exemplars) mà không cần biết trước số lượng cụm. AP được sử dụng trong phương pháp tích lũy để tạo ra các phân cụm đa dạng, từ đó kết hợp bằng lược đồ bầu cử.

Các khái niệm chính bao gồm: ma trận kết hợp co-association, lược đồ bầu cử đa số, thuật toán k-means, thuật toán lan truyền quan hệ, và thuật toán MST đa gốc yếu dùng để gán điểm dữ liệu.

Phương pháp nghiên cứu

Nguồn dữ liệu chính là tập dữ liệu khách hàng của Ngân hàng MB, bao gồm thông tin nhân khẩu học, lịch sử giao dịch và sử dụng dịch vụ. Cỡ mẫu nghiên cứu khoảng vài nghìn khách hàng, được lựa chọn ngẫu nhiên từ cơ sở dữ liệu ngân hàng nhằm đảm bảo tính đại diện.

Phương pháp phân tích chính là áp dụng thuật toán phân cụm tích lũy dựa trên k-means (voting-k-means) và lan truyền quan hệ (voting-PAP). Quy trình nghiên cứu gồm các bước:

1. Tiền xử lý dữ liệu: làm sạch, chuẩn hóa và lựa chọn các thuộc tính phù hợp.
2. Thực hiện phân cụm nhiều lần với các tham số khởi tạo khác nhau để tạo ra nhiều kết quả phân cụm.
3. Xây dựng ma trận kết hợp co-association từ các kết quả phân cụm.
4. Áp dụng lược đồ bầu cử đa số để xác định các cụm thống nhất.
5. Đánh giá kết quả phân cụm bằng các chỉ số chất lượng như độ chính xác, độ ổn định và khả năng dự đoán hành vi khách hàng mới.

Thời gian nghiên cứu kéo dài trong vòng 12 tháng, bao gồm thu thập dữ liệu, phát triển thuật toán, thực nghiệm và đánh giá kết quả.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Tăng độ ổn định phân cụm: Thuật toán voting-k-means cải thiện đáng kể độ ổn định kết quả phân cụm so với k-means truyền thống. Ví dụ, khi chạy 10 lần với k=14, voting-k-means tạo ra các cụm ổn định với tỷ lệ đồng nhất trên 85%, trong khi k-means đơn lẻ chỉ đạt khoảng 60%.

2. Xác định số lượng cụm chính xác hơn: Phương pháp phân cụm tích lũy cho phép xác định số lượng cụm phù hợp mà không cần cố định trước, giảm thiểu sai số do lựa chọn k không chính xác. Qua thực nghiệm với dữ liệu MB, số lượng cụm tối ưu được xác định trong khoảng 3-5 cụm, phản ánh các nhóm khách hàng có đặc điểm hành vi khác biệt.

3. Hiệu quả dự đoán hành vi khách hàng mới: Ứng dụng mô hình phân cụm tích lũy giúp dự đoán chính xác hơn khả năng khách hàng sử dụng dịch vụ mới, với độ chính xác dự đoán tăng khoảng 15% so với phương pháp phân cụm đơn lẻ.

4. Khả năng xử lý dữ liệu lớn và đa chiều: Thuật toán voting-PAP kết hợp lan truyền quan hệ và MST đa gốc yếu cho phép xử lý hiệu quả tập dữ liệu lớn với nhiều thuộc tính, phát hiện các cụm có hình dạng phức tạp không bị giới hạn bởi giả định hình cầu.

Thảo luận kết quả

Nguyên nhân chính của sự cải thiện là do phương pháp phân cụm tích lũy tận dụng được sức mạnh tổng hợp của nhiều thuật toán và nhiều lần khởi tạo khác nhau, giảm thiểu ảnh hưởng của sự khởi tạo ngẫu nhiên và tham số đầu vào. Kết quả này phù hợp với các nghiên cứu gần đây trong lĩnh vực khai phá dữ liệu, cho thấy việc kết hợp các thuật toán phân cụm giúp tăng độ chính xác và tính ổn định.

Việc áp dụng thành công tại Ngân hàng MB chứng minh tính khả thi và hiệu quả của phương pháp trong thực tế, đặc biệt trong bối cảnh dữ liệu khách hàng đa dạng và phức tạp. Kết quả phân cụm có thể được trình bày qua biểu đồ phân bố các cụm khách hàng, bảng so sánh độ chính xác dự đoán giữa các phương pháp, và ma trận kết hợp co-association minh họa mức độ liên kết giữa các điểm dữ liệu.

Đề xuất và khuyến nghị

1. Triển khai hệ thống phân cụm tích lũy tự động: Ngân hàng nên xây dựng hệ thống khai phá dữ liệu tự động áp dụng thuật toán voting-k-means và voting-PAP để phân tích dữ liệu khách hàng định kỳ, nhằm cập nhật các nhóm khách hàng và dự đoán hành vi mới. Thời gian triển khai dự kiến 6 tháng, do phòng CNTT và bộ phận phân tích dữ liệu thực hiện.

2. Tăng cường đào tạo nhân sự về khai phá dữ liệu: Đào tạo chuyên sâu cho đội ngũ phân tích dữ liệu và quản lý marketing về các phương pháp phân cụm tích lũy và khai phá dữ liệu để nâng cao năng lực ứng dụng. Khuyến nghị tổ chức các khóa đào tạo trong vòng 3 tháng.

3. Mở rộng áp dụng phân cụm tích lũy cho các dịch vụ khác: Áp dụng phương pháp phân cụm tích lũy vào các lĩnh vực như quản lý rủi ro tín dụng, phát hiện gian lận và tối ưu danh mục đầu tư để nâng cao hiệu quả hoạt động. Thời gian thử nghiệm 9 tháng, phối hợp giữa các phòng ban liên quan.

4. Xây dựng kho dữ liệu tập trung và chuẩn hóa dữ liệu: Để đảm bảo chất lượng phân tích, ngân hàng cần đầu tư xây dựng kho dữ liệu tập trung, chuẩn hóa và làm sạch dữ liệu khách hàng, giao dịch. Dự kiến hoàn thành trong 12 tháng, phối hợp giữa phòng CNTT và quản lý dữ liệu.

Đối tượng nên tham khảo luận văn

1. Chuyên gia phân tích dữ liệu và khoa học dữ liệu: Luận văn cung cấp phương pháp và thuật toán phân cụm tích lũy hiện đại, giúp chuyên gia nâng cao kỹ năng khai phá dữ liệu trong lĩnh vực tài chính ngân hàng.

2. Nhà quản lý ngân hàng và marketing: Các nhà quản lý có thể áp dụng kết quả nghiên cứu để hiểu rõ hơn về phân khúc khách hàng, từ đó xây dựng chiến lược quảng cáo và chăm sóc khách hàng hiệu quả.

3. Nhà nghiên cứu và sinh viên ngành công nghệ thông tin, hệ thống thông tin: Luận văn là tài liệu tham khảo quý giá về các thuật toán phân cụm, phương pháp tích lũy và ứng dụng thực tiễn trong khai phá dữ liệu.

4. Phòng CNTT và phát triển sản phẩm ngân hàng: Các bộ phận này có thể sử dụng kết quả nghiên cứu để phát triển các ứng dụng khai phá dữ liệu, hỗ trợ ra quyết định và cải tiến dịch vụ ngân hàng.

Câu hỏi thường gặp

1. Phân cụm tích lũy khác gì so với phân cụm truyền thống?
   Phân cụm tích lũy kết hợp nhiều kết quả phân cụm từ các thuật toán hoặc lần chạy khác nhau để tạo ra kết quả ổn định và chính xác hơn, giảm thiểu ảnh hưởng của khởi tạo ngẫu nhiên và tham số đầu vào.

2. Tại sao cần sử dụng thuật toán voting-k-means thay vì k-means đơn lẻ?
   Voting-k-means cải thiện độ ổn định và khả năng xác định số lượng cụm phù hợp bằng cách tổng hợp kết quả từ nhiều lần chạy k-means với các tham số khác nhau, giúp tránh sai lệch do khởi tạo.

3. Phương pháp lan truyền quan hệ (AP) có ưu điểm gì?
   AP không cần biết trước số lượng cụm, tự động xác định các điểm đại diện dựa trên truyền thông điệp giữa các điểm dữ liệu, phù hợp với dữ liệu có hình dạng phức tạp và đa chiều.

4. Làm thế nào để chọn ngưỡng trong ma trận kết hợp co-association?
   Ngưỡng được chọn dựa trên việc so sánh chỉ số thống nhất vùng (pc_idx) giữa các phân cụm với các ngưỡng khác nhau, chọn ngưỡng đầu tiên làm giảm chỉ số này dưới 1.0 để đảm bảo kết quả phân cụm thống nhất.

5. Phân cụm tích lũy có thể áp dụng cho các lĩnh vực khác ngoài ngân hàng không?
   Có, phương pháp này có thể áp dụng rộng rãi trong các lĩnh vực như y tế, bán lẻ, viễn thông để phân tích dữ liệu khách hàng, phát hiện mẫu và dự đoán hành vi.

Kết luận

• Phân cụm tích lũy dựa trên k-means và lan truyền quan hệ là phương pháp hiệu quả để phân tích dữ liệu khách hàng ngân hàng, nâng cao độ chính xác và ổn định kết quả phân cụm.
• Việc áp dụng phương pháp này tại Ngân hàng MB giúp dự đoán hành vi khách hàng mới chính xác hơn, hỗ trợ chiến lược marketing và quản lý khách hàng.
• Nghiên cứu đã xây dựng thành công mô hình và ứng dụng thực nghiệm với dữ liệu thực tế, chứng minh tính khả thi và hiệu quả.
• Đề xuất triển khai hệ thống phân cụm tích lũy tự động, đào tạo nhân sự và mở rộng ứng dụng trong các lĩnh vực ngân hàng khác.
• Các bước tiếp theo bao gồm hoàn thiện hệ thống khai phá dữ liệu, chuẩn hóa dữ liệu và đánh giá liên tục hiệu quả ứng dụng trong thực tế.

Hành động ngay hôm nay: Các tổ chức ngân hàng và chuyên gia phân tích dữ liệu nên nghiên cứu và áp dụng phương pháp phân cụm tích lũy để nâng cao năng lực khai phá dữ liệu, từ đó tạo lợi thế cạnh tranh bền vững trên thị trường.

Trích đoạn nội dung tài liệu

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 z 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. 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. 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.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.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 z 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.2 Một số phương pháp phân cụm điển hình 1.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 z 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: z 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. 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. 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.

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.