Tài liệu Ứng dụng vài thuật toán phân cụm phân tích dữ liệu ngân hàng

ĐẠ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 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.01.10 LUẬN VĂN THẠC SỸ Ngƣời hƣớng dẫn khoa học: PGS. TSKH. Bùi Công Cƣờng Hà Nội – 2006 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. 3 MỤC LỤC MỞ ĐẦU ............................................................................................................................................6 CHƢƠNG 1. TỔNG QUAN .............................................................................................................7 1.1. MỤC TIÊU, NỘI DUNG VÀ PHƢƠNG PHÁP NGHIÊN CỨU ....................................................... 7 1.2. TÓM TẮT NỘI DUNG CÁC CHƢƠNG ............................................................................................ 8 CHƢƠNG 2. PHÂN CỤM DỮ LIỆU ............................................................................................10 2.1 KHÁI NIỆM PHÂN CỤM DỮ LIỆU ................................................................................................. 10 2.2 CÁC BƢỚC CƠ BẢN ĐỂ PHÂN CỤM ............................................................................................. 11 2.3 CÁC ỨNG DỤNG CỦA PHÂN CỤM ................................................................................................ 12 2.4 CÁC LOẠI ĐẶC TRƢNG .................................................................................................................. 13 2.5 CÁC ĐỊNH NGHĨA PHÂN CỤM ...................................................................................................... 14 2.5.1 Định nghĩa phân cụm .......................................................................................... 14 2.5.2 Định nghĩa phân cụm mờ .................................................................................... 15 2.6 CÁC ĐỘ ĐO ........................................................................................................................................ 16 2.6.1 Độ đo không tƣơng tự ......................................................................................... 16 2.6.2 Độ đo tƣơng tự .................................................................................................... 16 2.6.3 Độ đo gần gũi giữa các tập con của X ................................................................ 17 2.6.4 Các độ đo gần gũi giữa hai điểm ........................................................................ 18 2.6.5 Các hàm gần gũi giữa một điểm và một tập ....................................................... 27 2.6.6 Các hàm gần gũi giữa hai tập .............................................................................. 29 2.6.7 Đánh giá phân cụm ............................................................................................. 30 CHƢƠNG 3. MỘT SỐ THUẬT TOÁN PHÂN CỤM .................................................................32 3.1 GIỚI THIỆU VỀ CÁC THUẬT TOÁN PHÂN CỤM ...................................................................... 32 3.1.1 Số các phân cụm ................................................................................................. 32 3.1.2 Phân loại các thuật toán phân cụm ...................................................................... 33 3.2 THUẬT TOÁN PHÂN CỤM TUẦN TỰ ........................................................................................... 34 3.2.1 Thuật toán phân cụm tuần tự .............................................................................. 34 3.2.2 Ƣớc lƣợng số lƣợng các phân cụm ..................................................................... 37 3.2.3. Một thuật toán BSAS cải tiến ............................................................................ 39 3.2.4. Sơ đồ tuần tự với hai ngƣỡng ............................................................................. 41 3.2.5. Thực hiện tinh chỉnh .......................................................................................... 45 3.3 THUẬT TOÁN PHÂN CỤM K-MEANS .......................................................................................... 47 3.3.1 Thuật toán K-means ............................................................................................ 47 3.3.2 Các bƣớc thực hiện thuật toán K-means ............................................................. 47 3.3.3 Ví dụ về áp dụng thuật toán K-means ................................................................. 49 3.3.4 Một số vấn đề và ƣu, nhƣợc điểm của K-means ................................................ 52 3.3.5 Độ phức tạp của thuật toán K-means ................................................................. 53 3.4 THUẬT TOÁN PHÂN CỤM MỜ K-MEANS (FKM) ...................................................................... 53 3.4.1 Khái niệm về tập mờ và phân cụm mờ .............................................................. 53 4 3.4.2 Thuật toán phân cụm mờ K-means .................................................................... 55 3.4.3 Mô tả thuật toán ................................................................................................. 57 3.4.4 Độ phức tạp thuật toán ........................................................................................ 58 3.5 THUẬT TOÁN PHÂN CỤM HIERACHICAL ................................................................................ 59 3.5.1 Nguyên lý thực hiện ............................................................................................ 59 3.5.2 Mô tả thuật toán .................................................................................................. 60 3.5.3 Ví dụ về thuật toán phân cấp............................................................................... 61 3.5.4 Ƣu, nhƣợc điểm của thuật toán ........................................................................... 65 3.6 THUẬT TOÁN PHÂN CỤM K-LÁNG GIỀNG GẦN...................................................................... 66 3.6.1 Thuật toán K-láng giềng gần............................................................................... 66 3.6.2. Cách thức thực hiện thuật toán KNN ................................................................. 66 3.6.3. Một ví dụ áp dụng thuật toán KNN ................................................................... 69 3.6.4. Ƣu, nhƣợc điểm của thuật toán KNN ................................................................ 71 CHƢƠNG 4. XÂY DỰNG CHƢƠNG TRÌNH PHÂN CỤM......................................................72 4.1 PHÂN TÍCH CÁC MODULE ............................................................................................................ 72 4.1.1 Module chuẩn bị dữ liệu ..................................................................................... 72 4.1.2 Tinh chỉnh dữ liệu ............................................................................................... 72 4.1.3 Hàm tính khoảng cách ........................................................................................ 73 4.2 CHƢƠNG TRÌNH MÔ PHỎNG CÁC THUẬT TOÁN ................................................................... 75 4.2.1 Giới thiệu chƣơng trình ....................................................................................... 75 4.2.2 Chuyển đổi và tinh chỉnh dữ liệu ........................................................................ 75 4.2.3 Thuật toán K-means ............................................................................................ 76 4.2.4 Thuật toán phân cụm phân cấp (Hierachical) ..................................................... 77 4.2.5 Thuật toán Fuzzy K-means ................................................................................. 79 CHƢƠNG 5. ỨNG DỤNG PHÂN CỤM DỮ LIỆU GIAO DỊCH ATM....................................80 5.1 PHÁT BIỂU BÀI TOÁN ..................................................................................................................... 80 5.2. ÁP DỤNG VÀO CHƢƠNG TRÌNH ĐÃ XÂY DỰNG ..................................................................... 80 5.2.1 Phƣơng pháp áp dụng ......................................................................................... 80 5.2.2 Đặc tả dữ liệu và cách thức thực hiện ................................................................. 81 5.2.3 Phân tích, đánh giá kết quả ................................................................................. 81 KẾT LUẬN ......................................................................................................................................85 1. TÓM TẮT KẾT QUẢ ........................................................................................................................... 85 2. 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Ử .............................................................. 88 1.1 Tính khoảng cách theo Manhattan ......................................................................... 88 1.2 Tính khoảng cách theo công thức Euclide ............................................................. 89 1.3 Tính khoảng cách hỗn hợp (công thức Kaufman và Rousseeuw) .......................... 90 2. MODULE THỰC HIỆN THUẬT TOÁN K-MEANS ........................................................................ 96 3. MODULE THỰC HIỆN THUẬT TOÁN HIERACHICAL .............................................................. 99 5 PHỤ LỤC 2: MÔ TẢ DỮ LIỆU GIAO DỊCH ...........................................................................102 1. Cấu trúc bảng dữ liệu ............................................................................................. 102 2. Danh sách mã loại thẻ ............................................................................................ 102 3. Danh sách mã giao dịch ......................................................................................... 103 4. Định dạng dữ liệu sau khi chuyển đổi ................................................................... 103 5. Định dạng dữ liệu sau phân cụm bằng thuật toán K-means .................................. 104 6. Định dạng dữ liệu sau phân cụm bằng thuật toán Hierachical .............................. 104 7. Định dạng cây phân cấp ......................................................................................... 105 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 đó. 7 CHƢƠNG 1. TỔNG QUAN 1.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.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. 8 1.2. 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), Ktrung 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 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. 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. 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.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 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. 2.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 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ý. 2.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). 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ệ). 2.5 CÁC ĐỊNH NGHĨA PHÂN CỤM 2.5.1 Định nghĩa phân cụm Cho X là một tập dữ liệu: X={x1, x2, ..., xN} Ta định nghĩa m-phân cụm của X nhƣ một sự phân chia X thành m cụm (tập): C1, C2, ...,Cm sao cho thoả mãn 3 điều kiện: i) ii) Ci, i=1,...,m m C i  X i 1 iii) CiCj =; i  j; i,j =1,...,m Thêm vào đó, các véctơ trong một cụm là tƣơng tự nhau hơn so với các véctơ thuộc một cụm khác. Lƣợng hoá thuật ngữ tƣơng tự và không tƣơng tự phụ thuộc rất nhiều vào loại của cụm. Chẳng hạn, loại cụm chặt thì có một số độ đo phù hợp, trong khi loại cụm có hình dáng dài và mỏng lại phù hợp hơn với các loại độ đo khác (xem hình vẽ). 15 (a) (b) (c) (a) Các tập chặt Hình 2.2: (b) Các tập dài và mỏng (c) Các tập dạng cầu và elipxôit Với định nghĩa trên mỗi véctơ chỉ thuộc về một cụm riêng nên loại phân cụm này đôi khi còn đƣợc gọi là chặt (hard) hay rõ (crisp). 2.5.2 Định nghĩa phân cụm mờ Dựa vào khái niệm tập mờ ta có thể định nghĩa nhƣ sau: Một sự phân cụm mờ X thành m cụm đƣợc mô tả bởi m hàm thuộc Uj sao cho: X={x1, x2, ..., xN} Uj : X  [0,1] j = 1,..., m (2.2) và: m U j 1 j ( xi )  1 i = 1,2,..., N m 0< U j 1 j ( x i ) < N-1 j = 1,2,..m (2.3) Mỗi cụm trong trƣờng hợp này có thể không đƣợc định nghĩa chính xác. Nghĩa là mỗi véctơ x thuộc về nhiều hơn một cụm, với mỗi cụm nó lại thuộc về với độ thuộc uj: - Khi uj gần 1: mức độ thuộc của x vào cụm thứ j cao. - Khi uj gần 0: mức độ thuộc của x vào cụm thứ j thấp. Nếu một hàm thuộc có giá trị gần 1 với hai véctơ thì hai véctơ này đƣợc coi là tƣơng tự nhau. 16 Điều kiện (2.3) đảm bảo rằng không tồn tại một cụm mà không chứa bất kỳ véctơ nào. Định nghĩa 2.5.1 là trƣờng hợp riêng của định nghĩa 3.5.2 khi hàm thuộc chỉ nhận giá trị 0 và 1, lúc này nó đƣợc gọi là hàm đặc trƣng. 2.6 CÁC ĐỘ ĐO Ta xét định nghĩa liên quan đến độ đo giữa các véctơ, sau đó mở rộng cho trƣờng hợp độ đo giữa các tập véctơ 2.6.1 Độ đo không tƣơng tự Một độ đo không tƣơng tự d trên X là một hàm: d : X x X  R trong đó R là tập số thực sao cho: d0  R: - < d0  d(x,y)< +, x,yX (2.4) d(x,x) = d0, xX (2.5) Và: d(x,y) = d(y,x), x,yX (2.6) Ngoài ra: d(x,y) = d0 khi và chỉ khi: x= y (2.7) và d(x,z)  d(x,y) + d(y,z), x,y,zX (2.8) thì d đƣợc gọi là một DM Metric Theo (2.7) chỉ ra rằng độ đo không tƣơng tự nhỏ nhất khi hai véctơ là đồng nhất. Dễ dàng nhận thấy khoảng cách Euclid là một độ đo không tƣơng tự metric. 2.6.2 Độ đo tƣơng tự Một độ đo tƣơng tự s trên X là một hàm: s : X x X  R trong đó R là tập số thực sao cho: s0  R: - < s(x,y)  so < +, x,yX (2.9) s(x,x) = s0, xX (2.10) 17 Và: s(x,y) = s(y,x), x,yX (2.11) Ngoài ra: s(x,y) = s0 khi và chỉ khi: x = y (2.12) và s(x,y)s(y,z)  [s(x,y) +s(y,z)]s(x,z), x,y,zX (2.13) thì d đƣợc gọi là một SM metric 2.6.3 Độ đo gần gũi giữa các tập con của X Cho U là một lớp các tập con của X, Nghĩa là các Di X, i=1,..,k và U= {D1, D2, ..., Dk}. Một độ đo gần gũi giữa  trên U là một hàm: : U x U  R Các công thức (2.4) – (2.8) cho độ đo không tƣơng tự và (2.9)-(2.13) cho độ đo tƣơng tự đƣợc lặp lại với việc thay thế x, y và X lần lƣợt bởi Di, Dj và U. Thông thƣờng, các độ đo gần gũi giữa hai tập Di, Dj đƣợc định nghĩa thông qua độ đo gần gũi các phần tử của chúng. Ví dụ: Cho X = {x1, ..., x6} và U= {{x1,x2}, {x1,x4},{x3,x4,x5},{x1,x2 ,x3,x4,x5}} Và hàm không tƣơng tự sau đây: ss d min ( Di , D j )  min d 2 ( x, y) xDi , yD j Với d2 là khoảng cách Euclid giữa hai véctơ. Giá trị nhỏ nhất có thể của d mssin là 0 Vì khoảng cách Euclid giữa một véctơ với bản thân nó bằng 0 nên: d mssin ( Di , Di )  0 và ss ss dmin (Di , Dj )  dmin (Dj , Di ) 18 Vì vậy hàm này là một độ đo không tƣơng tự nhƣng nó không phải là một độ đo không tƣơng tự metric vì không thoả mãn (2.7). Thật vậy, xét các véctơ Di, Dj có phần tử chung, chẳng hạn: {x1,x2} và {x1,x4} thì: d mssin  x1 , x2 , x1 , x4   0 Trong khi chúng là 2 tập khác nhau. Một cách trực giác thì các định nghĩa trên cho thấy các DM là ngƣợc với các SM. Chẳng hạn, nếu d là một DM (metric) với d(x,y)>0, x,yX thì s = a/d với a>0 là một SM (metric): s = dmax+ k – d cũng là một SM (metric), với dmax là khoảng cách lớn nhất trong mọi cặp phần tử của X. Các nhận xét tƣơng tự cũng đúng với độ đo tƣơng tự và không tƣơng tự giữa các tập véctơ. Trong phần tiếp theo, ta ký hiệu bmax, bmin lần lƣợt là các giá trị max và min của tập dữ liệu X. 2.6.4 Các độ đo gần gũi giữa hai điểm 2.6.4.1. Các vectơ thực  Các độ đo không tương tự: Các độ đo không tƣơng tự phổ biến nhất trong thực hành là: + Các DM metric có trọng số lp:  1 d p ( x, y )    Wi xi  yi  i 1 1/ p p    (2.14) wi  0, i = 1,...,l; p > 0 wi là hệ số trọng số thứ i, chúng đƣợc sử dụng chủ yếu với các vectơ giá trị thực. Nếu wi = 1, i = 1,...,l ta có các DM metric không trọng số. Nếu p = 2 ta có khoảng cách Euclid. Các DM metric có trọng số l2 đƣợc tổng quát hoá nhƣ sau: 19 d ( x, y)  ( x  y)t B( x, y) , (2.15) Với B là ma trận đối xứng xác định dƣơng. Nó bao gồm cả khoảng cách Mahalanobis là một trƣờng hợp đặc biệt và khoảng cách Mahalanobis cũng là một DM metric. Các DM metric có trọng số lp đặc biệt cũng xuất hiện trong thực hành là chuẩn Manhattan l1 (có trọng số): 1 d1 ( x, y )   Wi xi  yi (2.16) i 1 Và chuẩn l (có trọng số): d ( x, y)  maxWi xi  yi (2.17) 1il Chuẩn l1 và l có thể đƣợc xem nhƣ ƣớc lƣợng trên và ƣớc lƣợng dƣới của chuẩn l2 , thật vậy: d (x,y)  d2(x,y)  d1(x,y) Khi l = 1 thì tất cả lp trùng nhau. Dựa vào các DM trên ta có thể định nghĩa các SM tƣơng ứng là: sp(x,y) = bmax- dp(x,y) Các DM khác là:  1 l xj  yp d G ( x, y)   log 10 1    l i 1 b j  a j      (2.18) trong đó: bj và aj là các giá trị lớn nhất và nhỏ nhất của đặc trƣng thứ j Dễ dàng thấy đây là một DM metric và nó không chỉ dựa trên x và y mà còn dựa vào toàn bộ tập X. Vì thế nếu dG(x,y) là khoảng cách giữa hai vectơ x, y và d‟G(x,y) là khoảng cách giữa hai vectơ trên nhƣng là khi chúng thuộc X* thì nói chung: dG(x,y)  d‟G(x,y) Một độ đo không tƣơng tự nữa là: