Luận văn Thạc sĩ Công nghệ thông tin: Tập thô và bài toán phân cụm dữ liệu

Chia sẻ: Tomjerry001 | Ngày: | Loại File: PDF | Số trang:70

Thêm vào BST

Báo xấu

24
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nội dung nghiên cứu của đề tài là Tổng quan về phân cụm dữ liệu. Giới thiệu về phân cụm dữ liệu và các phương pháp phân cụm với mỗi phương pháp trình bày một thuật toán tương ứng; Lý thuyết tập thô. Trình bày tổng quan về lý thuyết tập thô bao gồm hệ thông tin, hệ quyết định, tính không phân biệt được và xấp xỉ tập hợp.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Công nghệ thông tin: Tập thô và bài toán phân cụm dữ liệu

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ VŨ THỊ BÍCH THẢO TẬP THÔ VÀ BÀI TOÁN PHÂN CỤM DỮ LIỆU LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Hà Nội - 2014 1
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ VŨ THỊ BÍCH THẢO TẬP THÔ VÀ BÀI TOÁN PHÂN CỤM DỮ LIỆU Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60480104 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN HƯỚNG DẪN KHOA HỌC: PGS.TS HOÀNG XUÂN HUẤN Hà Nội - 2014 2
LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Kết quả trong luận văn là trung thực và chƣa từng đƣợc ai công bố trong bất kì công trình nào khác. Tác giả Vũ Thị Bích Thảo 3
LỜI CẢM ƠN Tôi xin gửi lời cảm ơn với lòng kính trọng và biết ơn sâu sắc tới PGS.TS Hoàng Xuân Huấn. Thầy đã hƣớng dẫn, chỉ bảo tận tình, cung cấp cho tôi những kiến thức bổ ích đồng thời tạo động lực giúp tôi hoàn thành luận văn đúng thời hạn. Thầy luôn theo sát, hỗ trợ nhiệt tình, giải đáp những vƣớng mắc trong quá trình tôi thực hiện luận văn. Tôi xin chân thành cảm ơn các Thầy, Cô trong khoa Công nghệ thông tin, trƣờng Đại học Công nghệ, đã tạo điều kiện cũng nhƣ môi trƣờng học tập tốt trong suốt quá trình tôi theo học ở đây. Tôi cũng xin gửi lời cảm ơn tới BGH trƣờng CĐCN Thực Phẩm, lãnh đạo Khoa CNTT cùng toàn thể cán bộ, giáo viên trong khoa đã hỗ trợ, tạo điều kiện tốt nhất để tôi có thể hoàn thành chƣơng trình học. Cuối cùng tôi xin cảm ơn gia đình hai bên nội, ngoại đã ủng hộ giúp đỡ tôi rất nhiều về mặt tinh thần trong tất cả những công việc mà tôi đã thực hiện. 4
MỤC LỤC LỜI CAM ĐOAN ............................................................................................................3 LỜI CẢM ƠN ..................................................................................................................4 MỤC LỤC .......................................................................................................................5 DANH MỤC KÝ HIỆU VIẾT TẮT ...............................................................................7 DANH MỤC CÁC HÌNH VẼ .....................................................................................8 MỞ ĐẦU .........................................................................................................................9 CHƢƠNG 1: TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU ...........................................12 1.1. Độ tƣơng đồng ....................................................................................................13 1.2. Các phƣơng pháp và các thuật toán phân cụm dữ liệu .......................................15 1.2.1 Phƣơng pháp dựa vào hàm mục tiêu ................................................................16 1.2.2. Các phƣơng pháp phân cụm phân cấp ............................................................20 1.2.3. Các phƣơng pháp dựa vào mật độ ...................................................................25 1.2.4. Các phƣơng pháp phân cụm dựa trên lƣới ......................................................29 CHƢƠNG 2: LÝ THUYẾT TẬP THÔ.........................................................................34 2.1 Hệ thông tin và hệ quyết định ..............................................................................34 2.2 Tính không phân biệt đƣợc (Indiscernibility) ......................................................36 2.3 Xấp xỉ tập hợp ......................................................................................................38 CHƢƠNG 3: TẬP THÔ VÀ BÀI TOÁN PHÂN CỤM ...............................................43 3.1. Phân cụm thô (Rough C-means) .........................................................................44 3.2. Phân cụm mờ .......................................................................................................47 3.3. Phân cụm thô-mờ (Rough-Fuzzy C-means) .......................................................50 5
3.4. Phân cụm bóng ....................................................................................................52 CHƢƠNG 4. ỨNG DỤNG RCM TRONG PHÂN CỤM ẢNH ...................................58 4.1 Phân vùng ảnh: .....................................................................................................58 4.2 Ảnh và những khái niệm liên quan ......................................................................59 4.2.1 Điểm ảnh (Picture Element) .............................................................................59 4.2.2 Độ phân giải của ảnh ........................................................................................60 4.2.3 Mức xám của ảnh .............................................................................................60 4.2 Phân cụm ảnh sử dụng phân cụm thô và phân cụm mờ .......................................61 4.3 Thử nghiệm phân cụm ảnh sử dụng phân cụm thô và phân cụm mờ ..................61 4.4 So sánh và đánh giá: ............................................................................................65 KẾT LUẬN ...................................................................................................................68 Tài liệu tham khảo .........................................................................................................69 6
DANH MỤC KÝ HIỆU VIẾT TẮT STT Từ viết tắt Từ hoặc cụm từ Fuzzy C-Means 1 FCM (Thuật toán phân cụm mờ) Rough C-Means 2 RCM (Thuật toán phân cụm thô) Rough Fuzzy C-Means 3 RFCM (Thuật toán phân cụm thô- mờ) Shadowed C-Means 4 SCM (Thuật toán phân cụm bóng) 5 RGB Red Green Blue Balanced Iterative Reducing and 6 BIRCH Clustering using Hierarchies 7 CURE Clustering Using Representatives Ordering Point To Identify the Clustering 8 OPTICS Structure 9 STING A STatistical INformation Grid approach 10 CF Clustering Feature 7
DANH MỤC CÁC HÌNH VẼ Hình 1.1 Ví dụ về phân cụm ..........................................................................................12 Hình 1.2 Biểu đồ hình sao thể hiện 3 cụm trong ma trận bộ phận U ............................17 Hình 1.3 Biểu đồ biểu diễn các mẫu trong phân cụm phân cấp ....................................21 Hình 1.4 Ba cách tính khoảng cách giữa hai cụm .........................................................22 Hình 1.5 Trộn 2 cụm theo thuật toán CURE .................................................................25 Hình 1.6 Hai cụm đƣợc tìm bởi thuật toán DBSCAN ...................................................27 Hình 1.7 Thứ tự cụm theo OPTICS ...............................................................................29 Hình 1.8 Ba tầng liên tiếp nhau của cấu trúc STING ....................................................30 Hình 1.9 CLIQUE xác định các vùng tiềm năng dựa trên các đơn vị dày đặc .............33 Hình 2.1: Hình minh họa khái niệm tập thô ..................................................................34 Hình 3.1 Ba vùng của một cụm .....................................................................................45 Hình 3.2: Hình minh họa cụm mờ .................................................................................47 Hình 3.3. Các tập bóng đƣợc tạo bởi tập mờ thông qua một ngƣỡng ...........................54 Hình 3.4. Các tập bóng đƣợc tạo ra bởi hàm thành viên mờ f(x) ..................................56 Hình 4.1 Minh họa ảnh đã phân vùng ...........................................................................58 Hình 4.2: Chuyển hình ảnh từ hệ màu RGB sang ảnh xám ..........................................62 Hình 4.3 Hình ảnh chụp cắt lớp sọ ngƣời ......................................................................63 Hình 4.4 Kết quả sau khi sử dụng phân cụm mờ ..........................................................64 Hình 4.5 Kết quả sau khi sử dụng phân cụm thô........... Error! Bookmark not defined. Hình 4.7 Kết quả sau khi sử dụng phân cụm mờ ..........................................................65 Hình 4.8 Kết quả sau khi sử dụng phân cụm thô........... Error! Bookmark not defined. 8
MỞ ĐẦU Phân cụm dữ liệu là một kỹ thuật quan trọng trong công nghệ tri thức, nó đƣợc ứng dụng rộng rãi và đa dạng trong các ngành khoa học nhƣ sinh học, tâm lý học, y học, ngành marketing, thị giác máy tính, và điều kiển học v.v. Phân cụm dữ liệu tổ chức dữ liệu bằng cách nhóm các đối tƣợng có độ tƣơng đồng cao vào một cụm, các đối tƣợng thuộc các cụm khác nhau có độ tƣơng đồng thấp hơn so với các đối tƣợng trong cùng một cụm. Tùy theo đặc điểm cấu trúc của tập dữ liệu và mục đích sử dụng, có các phƣơng pháp giải quyết khác nhau nhƣ: Phân cụm dựa vào hàm mục tiêu, phân cụm phân cấp, phân cụm dựa vào mật độ và phân cụm dựa vào lƣới. Thông thƣờng, thông tin về thế giới xung quanh là không chính xác, không đầy đủ, không chắc chắn hoặc chồng chéo. Đó cũng là vấn đề gặp phải khi phân cụm dữ liệu. Phân cụm đƣợc chia làm hai loại phân cụm là phân cụm cứng và phân cụm mềm. Trong phân cụm cứng đối tƣợng đƣợc phân thành các cụm khác nhau, mỗi đối tƣợng thuộc về chính xác một cụm, ngƣợc lại ở phân cụm mềm các đối tƣợng có thể thuộc về nhiều hơn một cụm và mỗi đối tƣợng có độ thuộc với cụm. Cụ thể trong luận văn, tôi sẽ nghiên cứu các thuật toán phân cụm trong cả hai loại phân cụm này: Phân cụm thô (phân cụm cứng) và phân cụm mờ (phân cụm mềm). Ngoài ra tôi cũng nghiên cứu thêm về 2 thuật toán kết hợp từ hai loại phân cụm trên là phân cụm thô mờ và phân cụm bóng. Năm 1965, giáo sƣ Lotfi A. Zadeh (Đại học California ở Berkeley) đề xuất lý thuyết tập mờ (fuzzy set), là phần mở rộng của lý thuyết tập hợp truyền thống. Ý tƣởng chính của lý thuyết tập mờ là các phần tử của tập có độ thuộc trong khoảng [0,1] thay vì giá trị nhị phân. Nó là công cụ mô hình hóa sự không chắc chắn, không rõ ràng trong hệ thống phức tạp. Trong phân cụm mờ, thuật toán thƣờng đƣợc sử dụng nhất là Fuzzy C-Means (FCM) đƣợc đề xuất vào năm 1973 bởi J.C Dunn và đƣợc cải tiến lại bởi Bezděk vào năm 1981. FCM thƣờng đƣợc sử dụng để xử lý trƣờng hợp các cụm chồng chéo nhau, tức là một số đối tƣợng có thể thuộc về nhiều hơn một cụm. Trong đó, mỗi một đối tƣợng có độ thuộc khác nhau đối với các cụm, chứ không hoàn toàn chỉ thuộc về một cụm đƣợc biểu diễn qua ma trận phân hoạch. FCM sử dụng giá trị trung bình (mean) độ thuộc của các đối tƣợng trong ma trận phân hoạch làm tâm cụm. Các bƣớc 9
trong thuật toán là quá trình thực hiện cập nhật các đối tƣợng của cụm và ma trận phân hoạch. Thuật toán chi tiết sẽ đƣợc trình bày cụ thể trong luận văn. Đến năm 1982, Zdzislaw Pawlak đề xuất ra lý thuyết tập thô với mục đích là để phân loại thông tin và tri thức không chính xác hoặc không đầy đủ. Khái niệm cơ bản của lý thuyết tập thô là xấp xỉ trên và xấp xỉ dƣới của một tập dữ liệu. Xấp xỉ dƣới bao gồm những đối tƣợng chắc chắn thuộc về cụm, trong khi xấp xỉ trên bao gồm những đối tƣợng có thể đƣợc phân lớp là thành viên không chắc chắn của cụm. Mỗi tập đƣợc xác định thông qua xấp xỉ trên và xấp xỉ dƣới đƣợc gọi là tập thô. Trong khuôn khổ luận văn, tôi tìm hiểu và trình bày cụ thể thuật toán Rough C-Means (RCM). Thuật toán RCM đƣợc Lingras và West đề xuất năm 2004 [4]. Trong đó, mỗi cụm có vùng xấp xỉ trên và vùng xấp xỉ dƣới của riêng mình. Việc xác định cụm phụ thuộc vào hai vùng xấp xỉ, không phải tất cả các đối tƣợng nhƣ trong FCM. Cụ thể, nếu nhƣ FCM xác định cụm dựa vào độ thuộc của đối tƣợng vào cụm thì RCM lựa chọn cụm bằng cách so sánh khoảng cách từ đối tƣợng tới tâm cụm so với một ngƣỡng mà ngƣời dùng tự chọn. Tất cả các đối tƣợng đƣợc chia vào ba vùng, cụ thể là, vùng lõi (Core level), vùng biên (Boundary level) và vùng loại trừ (Exclusion level). Các đối tƣợng nằm ở vùng lõi chắc chắn thuộc về cụm. Các đối tƣợng ở vùng biên có thể thuộc về cụm. Các đối tƣợng khác thuộc phạm vi vùng loại trừ không thuộc cụm. Ngoài ra, trong luận văn tôi trình bày chi tiết hai thuật toán nữa là phân cụm thô-mờ, phân cụm bóng tƣơng ứng là Rough Fuzzy C-Means (RFCM) và Shadowed C –Means (SCM). RFCM là thuật toán kết hợp từ FCM và RCM, trong đó cách xác định cụm của RFCM giống nhƣ RCM là dựa vào hai vùng xấp xỉ trên và xấp xỉ dƣới. Tuy nhiên cách xác định các vùng xấp xỉ này không dựa vào khoảng cách từ các đối tƣợng tới tâm mà dựa vào độ thuộc của phần tử đối với cụm giống nhƣ FCM. Thuật toán này giúp cho việc phân cụm mạnh hơn so với hai thuật toán phân cụm trƣớc. Đối với SCM, các đối tƣợng cũng đƣợc chia vào ba vùng tƣơng tự nhƣ trong RCM nhƣng tên gọi và cách xác định mỗi vùng là khác nhau. Ba vùng lõi, vùng biên và vùng loại trừ trong lý thuyết tập thô tƣơng ứng với ba giá trị logic 0,1, và [0,1] trong tập bóng, cụ thể, lõi (Core), loại trừ (Exclusion), bóng 10
(shadow). Ngoài ra, SCM tạo ra sự khác biệt với FCM là nó tăng độ thuộc của một số phần tử tới 1 và giảm độ thuộc của một số phần tử khác về 0 để làm tăng sự tƣơng phản của các phần tử nhằm làm giảm sự chồng chéo không chắc chắn nhƣ ở trong FCM. Theo khía cạnh này, tập bóng có thể đƣợc coi là cầu nối giữa tập mờ và thô. Hiện nay phân cụm ảnh là một vấn đề đang nhận đƣợc nhiều sự quan tâm từ các nhà nghiên cứu. Mục đích là để đơn giản hóa hoặc làm nổi bật một số đối tƣợng nhằm dễ dàng hơn trong việc phân tích hình ảnh. Để phân cụm ảnh, phải chuyển các điểm màu của ảnh sang hệ màu xám với giá trị từ 0 đến 255 sau đó áp dụng thuật toán phân cụm. Trƣớc đây, FCM đƣợc sử dụng nhiều trong phân cụm ảnh và nó đƣợc ứng dụng trong nhiều lĩnh vực khác nhau nhƣ phân tích hình ảnh y tế, phát hiện các đối tƣợng,… Trong cuốn luận văn này, tôi đã nghiên cứu và áp dụng RCM cho phân cụm ảnh, từ đó so sánh sự khác biệt so với phân cụm ảnh sử dụng FCM. Luận văn của tôi đƣợc chia làm 4 chƣơng với nội dung nhƣ sau: Chƣơng 1: Tổng quan về phân cụm dữ liệu. Giới thiệu về phân cụm dữ liệu và các phƣơng pháp phân cụm với mỗi phƣơng pháp trình bày một thuật toán tƣơng ứng. Chƣơng 2: Lý thuyết tập thô. Trình bày tổng quan về lý thuyết tập thô bao gồm hệ thông tin, hệ quyết định, tính không phân biệt đƣợc và xấp xỉ tập hợp. Chƣơng 3: Tập thô và bài toán phân cụm. Giới thiệu các thuật toán phân cụm: Phân cụm thô, phân cụm mờ, phân cụm thô-mờ, phân cụm bóng, các bƣớc phân cụm và công thức chi tiết của từng thuật toán. Chƣơng 4: Ứng dụng RCM trong phân cụm ảnh. Xây dựng phân cụm ảnh bằng RCM, đƣa ra kết quả phân cụm, đánh giá và so sánh với phân cụm ảnh bằng FCM. 11
CHƢƠNG 1: TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU Bài toán phân cụm dữ liệu là một kỹ thuật trong khai phá dữ liệu thuộc lĩnh vực học không giám sát, nhằm tìm kiếm, phát hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn đƣợc quan tâm trong tập dữ liệu lớn, từ đó cung cấp các thông tin hữu ích hỗ trợ cho việc ra quyết định. Các thuật toán phân cụm hƣớng tới việc tìm kiếm cấu trúc trong dữ liệu. Phƣơng pháp này còn đƣợc gọi là “học không thầy” hay “học không có giám sát” (Unsupervised Learning) trong lĩnh vực nhận dạng mẫu (Pattern Recognition) nói riêng và trong trí tuệ nhân tạo nói chung. Một cụm bao gồm một tập các đối tƣợng có độ tƣơng đồng cao. Định nghĩa về cụm đƣợc phát biểu một cách không hình thức nhƣ sau: Một cụm là một tập các thực thể (các đối tƣợng) tƣơng tự nhau, và các thực thể ở các cụm khác nhau thì không giống nhau. Hình 1.1 Ví dụ về phân cụm Tùy vào từng ứng dụng, đặc tính của dữ liệu và từng phƣơng pháp phân cụm cụ thể, chúng ta có thể xem xét các dữ liệu nhƣ là các điểm trong không gian thỏa mãn điều kiện độ tƣơng đồng giữa hai điểm bất kỳ trong một cụm lớn hơn độ tƣơng đồng giữa một điểm bất kỳ trong cụm đó với một điểm bất kỳ không thuộc cụm hoặc các cụm có thể đƣợc mô tả nhƣ là các vùng chứa các đối 12
tƣợng có mật độ cao trong không gian nhiều chiều, đƣợc tách với các vùng chứa các đối tƣợng có mật độ thấp hơn. Chúng ta có thể dễ dàng phát biểu không hình thức về một cụm, nhƣng lại rất khó để có thể đƣa ra một định nghĩa hình thức về cụm. Bởi vì thực tế thì các đối tƣợng đƣợc nhóm vào trong các cụm theo các mục đích khác nhau trong từng ứng dụng. Dữ liệu có thể cho thấy các cụm theo hình dạng và theo các kích thƣớc cụm. Các vấn đề liên quan tới bài toán phân cụm dữ liệu là vấn đề biểu diễn dữ liệu trong máy tính, xác định phƣơng pháp, từ đó đƣa ra thuật toán cụ thể để áp dụng, đồng thời xác định độ tƣơng đồng giữa các đối tƣợng. Đối với các thuật toán trong phƣơng pháp dựa vào phân hoạch thì chúng ta còn phải xây dựng hàm đánh giá phù hợp để thuật toán cho ra kết quả phân cụm tốt. 1.1. Độ tương đồng Độ tƣơng đồng giữa các đối tƣợng mô tả tính chất giống hoặc khác nhau giữa chúng theo một ý nghĩa nào đó. Có rất nhiều hàm đƣợc dùng để biểu diễn độ tƣơng đồng giữa các đối tƣợng. Tuy nhiên, trong khuôn khổ của luận văn chỉ trình bày một số các hàm đo tƣơng đồng phổ biến gọi là các hàm khoảng cách. Khoảng cách giữa hai mẫu thứ i và mẫu thứ k ký hiệu là d(i,k) phải thỏa mãn các tính chất sau: 1. d(i,i)=0 với mọi i. 2. d(i,k)=d(k,i) với mọi cặp (i,k). 3. d(i,k)>=0 với mọi cặp (i,k). Hàm đánh giá độ tƣơng đồng có thể đƣợc xác định theo một số cách. Giả sử rằng chúng ta có một ma trận mẫu [xij] với xij là giá trị của đặc trƣng thứ j của mẫu i. Tất cả các đặc trƣng là liên tục và đƣợc ƣớc lƣợng theo tỷ lệ xích. Hàm khoảng cách phổ biến là khoảng cách Minkowski (1) dùng để ƣớc lƣợng độ tƣơng đồng. Mẫu thứ i tƣơng ứng với dòng thứ i của ma trận mẫu đƣợc ký hiệu là một vector cột xi. xi  ( xi1 , xi 2 ,....., xin )T , i  1,2,..., n 13
Với d là số đặc trƣng, n là số lƣợng mẫu, T ký hiệu là vector chuyển vị. Khoảng cách Minkowski đƣợc định nghĩa nhƣ sau: d d (i, k )  ( | xij  xkj | r )1 / r với r>=1 (1.1) j 1 Các hàm khoảng cách Minkowski thỏa mãn tính chất các tính chất sau: 4. d(i,k)=0 nếu và chỉ nếu xi=xk 5. d(i,k)  d (i, m)  d (m, k ) với mọi (i,m,k) Có ba khoảng cách phổ biến sử dụng khoảng cách Minkowsky đƣợc định nghĩa nhƣ sau: Khoảng cách Euclide (r=2): d d (i, k )  ( | xij  xkj | 2 )1 / 2  [( xi  xk ) T ( xi  xk )]1 / 2 (1.2) j 1 Khoảng cách Manhattan (r=1) d d (i, k )  ( | xij  xkj | ) (1.3) j 1 Khoảng cách Max (r  ): max d (i, k )  ( | xij  xkj |) (1.4) 1 j  d Khoảng cách Euclide là chuẩn đƣợc dùng phổ biến nhất trong các chuẩn theo khoảng cách Minkowski. Các khái niệm hình học quen thuộc về tính bất biến của phép tịnh tiến và phép quay của không gian mẫu là phù hợp với chuẩn Euclide. Các ứng dụng cụ thể tác động lớn đến việc chọn ra hàm khoảng cách nào đƣợc sử dụng. Ngoài các hàm khoảng cách đƣợc sử dụng để đánh giá độ tƣơng đồng của các đối tƣợng nêu trên còn có rất nhiều cách đánh giá độ tƣơng đồng khác, tùy thuộc vào tính chất của tập dữ liệu. 14
Để biểu diễn độ tƣơng đồng của tất cả các đối tƣợng trong tập dữ liệu, ngƣời ta thƣờng sử dụng ma trận để lƣu lại giá trị tƣơng đồng giữa các cặp đối tƣợng. Ma trận này đƣợc gọi là ma trận tƣơng đồng. Có thể đƣa ra khái niệm về ma trận tƣơng đồng nhƣ sau: Ma trận tƣơng đồng [d(i,j)] lƣu giá trị tƣơng đồng trong một ma trận, mỗi dòng và mỗi cột của ma trận biểu diễn một mẫu. Trong đó d(i,j) là độ tƣơng tự giữa mẫu thứ i và mẫu thứ j. Chúng ta bỏ qua các giá trị nằm trên đƣờng chéo chính của ma trận tƣơng đồng khi giả sử rằng tất cả các mẫu có cùng mức độ tƣơng đồng với chính nó. Giả sử rằng ma trận tƣơng đồng là ma trận có tính đối xứng, tất cả các cặp đối tƣợng có cùng một giá trị tƣơng đồng, không phụ thuộc vào thứ tự sắp xếp. Một ma trận tƣơng đồng có thể là đƣợc gọi là ma trận độ tƣơng tự hoặc cũng có thể gọi là ma trận bất tƣơng đồng. Các giá trị tƣơng đồng cũng có thể là nhận giá trị nhị phân, rời rạc hoặc nhận giá trị liên tục. Ví dụ, giả sử rằng một tập đối tƣợng đƣợc phân hoạch vào các tập con. Giá trị nhị phân đo độ tƣơng đồng nhận giá trị 0 với các cặp đối tƣợng ở hai tập con khác nhau và nhận giá trị bằng 1 với các cặp ở cùng một tập con. Nếu giá trị tƣơng đồng là một số nguyên từ 1 tới n(n-1)/2 với n là số lƣợng các đối tƣợng đƣợc xem là ma trận tƣơng đồng nhận giá trị rời rạc. Nếu ma trận tƣơng đồng mà các phần tử nhận giá trị là khoảng cách Euclide giữa các mẫu trong không gian mẫu thì đƣợc xem là ma trận tƣơng đồng nhận giá trị liên tục. Các thuật toán phân cụm nhóm các đối tƣợng, hay các dữ liệu thành phần dựa trên độ tƣơng đồng giữa các cặp đối tƣợng. Các đối tƣợng đƣợc gọi là các điểm, các trƣờng hợp, các thành phần trong các ứng dụng khác nhau. 1.2. Các phương pháp và các thuật toán phân cụm dữ liệu Phân cụm dữ liệu biểu diễn mối quan hệ giữa các đối tƣợng trong ma trận tƣơng đồng. Nếu các đối tƣợng đƣợc đặc tả nhƣ là các mẫu hoặc các điểm trong không gian metric, thì độ tƣơng đồng có thể là khoảng cách giữa các cặp đối tƣợng, nhƣ là khoảng cách Euclide. Ma trận mẫu và ma trận tƣơng đồng là những dữ liệu vào cho các thuật toán phân cụm. Đã có rất nhiều thuật toán phân 15
cụm đƣợc xây dựng nhằm áp dụng vào các mục đích cụ thể. Các thuật toán này có thể đƣợc phân vào một trong 4 phƣơng pháp sau đây: 1. Phƣơng pháp phân cụm dựa vào hàm mục tiêu (Object Function- Based Clustering). 2. Phƣơng pháp phân cụm phân cấp (Hierarchical Clustering). 3. Phƣơng pháp phân cụm dựa trên mật độ (Density-Based Clustering). 4. Phƣơng pháp phân cụm dựa trên lƣới (Grid-Based Clustering). 1.2.1 Phương pháp dựa vào hàm mục tiêu Loại phân cụm này liên quan tới phân chia các tập dữ liệu dựa trên một vài chỉ số đƣợc biết đến là hàm mục tiêu. Về mặt bản chất, phân chia N mẫu vào c cụm. Đầu tiên, số lƣợng phân chia đƣợc tính theo công thức 1 c c i  c  N  ( 1)  i c ! i 1 i Con số này tăng lên rất nhanh nên không thể liệt kê số lƣợng phân chia này. Tối thiểu hàm mục tiêu có thể coi nhƣ phƣơng pháp tối ƣu hóa. Thách thức thiết kế chính chấp nhận tính toán một hàm mục tiêu có khả năng phản ảnh bản chất của vấn đề nên tối thiểu bộc lộ cấu trúc có nhiều nghĩa trong bộ dữ liệu. Tối thiểu sự khác biệt tiêu chuẩn là một trong những lựa chọn chung nhất. Có N mẫu trong Rn, chúng ta tính tổng khoảng cách giữa các mẫu và tập các nguyên mẫu v1, v2,…,vc c N 2 Q   uik xk  vi i 1 k 1 Với xk  vi là khoảng cách giữa xk và vi. Thành phần quan trọng của tổng trên là ma trận bộ phận U=[uik], i=1,2,…,c,k=1,2,...,N là đóng vai trò phân chia các mẫu vào các cụm. Các giá trị trong U là nhị phân. Mẫu k thuộc về cụm i khi uik=1. Ngƣợc lại k không thuộc về cụm i khi uik=0. Ma trận bộ phận thỏa mãn các điều kiện sau: 16
Mỗi cụm đều có giá trị, vì thế nó không chứa tất cả các mẫu và nó không rỗng: N 0   uik  N , i=1,2,…,c k 1 Mỗi mẫu thuộc về một cụm riêng: c u i 1 ik  1 , k=1,2,…,N Ma trận bộ phận kí hiệu là U (U là ma trận nhị phân). Ma trận bộ phận thể hiện trực quan cấu trúc của các cụm. Ví dụ, cho ma trận N=8 mẫu chia vào 3 cụm nhƣ sau: 1 0 0 1 0 1 0 1  U  0 1 1 0 0 0 0 0  0 0 0 0 1 0 1 0  Mỗi hàng thể hiện 1 cụm riêng biệt. Nhƣ vậy chúng ta có sự sắp xếp: Cụm đầu tiên chứa các mẫu {1,4,6,8}, cụm thứ hai chứa các mẫu {2,3} và cụm thứ ba chứa các mẫu còn lại {5,7}. Biểu diễn ma trận bộ phận bằng đồ thị hình sao (hay gọi là đồ thị radar) Hình 1.2 Biểu đồ hình sao thể hiện 3 cụm trong ma trận bộ phận U Một vài thuật toán đã đƣợc sử dụng để đạt đƣợc tối ƣu hóa. Thuật toán phổ biến nhất là C-Means (Duda và cộng sự, 2001; Webb, 2002), là cách thiết lập dữ liệu phân cụm tốt. 17
Phần này sẽ giới thiệu các thuật toán phân cụm dựa vào phân hoạch sau: Thuật toán K-Means (MacQueen, 1967), Thuật toán EM (Expectation Maximazation) (Dempster et al.,1977; Yu et al.,1998; Braley et al 1998), thuật toán K-Medoids. Ba thuật toán này có các cách biểu diễn các cụm khác nhau. Thuật toán K-Means sử dụng tâm (điểm trung bình) của các đối tƣợng trong một cụm làm tâm của cụm đó trong khi thuật toán K-Medoids sử dụng đối tƣợng gần điểm trung bình nhất làm tâm. Không giống nhƣ thuật toán K-Means và K- Medoid, thuật toán EM sử dụng điểm trung bình và ma trận hệ số kích thƣớc d*d biểu diễn mỗi cụm. Thay thế cho việc kết gán mỗi đối tƣợng tới một tâm duy nhất, thuật toán EM kết gán mỗi đối tƣợng tới một cụm theo một xác xuất đƣợc tính toán từ phân bố của mỗi cụm. Mặc dù các thuật toán phân cụm khác nhau tạo ra kết quả phân cụm là khác nhau, tuy nhiên ba thuật toán phân hoạch đều có một tiếp cận chung khi tính toán các lời giải của chúng. Thật vậy, quan sát ba thuật toán tìm kiếm K tâm và các phân bố để làm tối ƣu hàm mục tiêu. Một khi đã xác định đƣợc K tâm hay các phân bố tối ƣu, các đối tƣợng trong K cụm đƣợc xác định. Tuy nhiên, để tìm kiếm K tâm hay các phân bố tối ƣu là một bài toán NP-Hard (Garey và Johnson,1979). Do đó, một cách để tìm ra các tâm tối ƣu cục bộ phải dùng phƣơng pháp cập nhật tâm nhiều lần cho đến khi hàm mục tiêu đạt giá trị cực tiểu. Ba thuật toán này có các hàm mục tiêu khác nhau và các cách thực hiện khác nhau đƣợc thể hiện ở bƣớc 3 và 4 của thuật toán A. Một trở ngại của các thuật toán dựa vào hàm mục tiêu là yêu cầu phải biết trƣớc tham số K và chúng không có khả năng để tìm kiếm các cụm theo hình dạng bất kỳ. Chúng ta sẽ xem xét các thuật toán một cách chi tiết hơn. Thuật toán A : Input: Số lƣợng cụm K, và một cơ sở dữ liệu chứa N đối tƣợng. Output: Một tập gồm K cụm thỏa mãn điều kiện cực tiểu hóa hàm mục tiêu E. Phƣơng pháp: 1) Khởi tạo chọn ngẫu nhiên K tâm cho lời giải ban đầu. 2) Repeat 18
3) Phân hoạch các đối tƣợng trong cơ sở dữ liệu theo lời giải hiện tại. 4) Cập nhật các tâm theo các đối tƣợng đã đƣợc phân hoạch ở bƣớc 3 5) Until (E không thay đổi); Thuật toán K-Means Thuật toán K-Means (MacQueue, 1967) sử dụng giá trị trung bình của các đối tƣợng trong một cụm là tâm cụm. Hàm mục tiêu đƣợc sử dụng trong thuật toán là hàm sai số bình phƣơng đƣợc định nghĩa nhƣ sau: E  i1 xC | x  mi |2 k i (4) Với x là một điểm trong không gian biểu diễn các đối tƣợng, và mi là giá trị trung bình của cụm Ci. Thuật toán K-Means cơ bản dựa theo cấu trúc của thuật toán A. Trong bƣớc 3 của thuật toán, K-Means gán mỗi đối tƣợng vào trong tâm gần nhất của nó tạo ra tập các cụm mới. Trong bƣớc 4, tất cả các tâm của cụm mới đƣợc tính toán bằng giá trị trung bình của các đối tƣợng trong mỗi cụm. Quá trình này lặp đi lặp lại cho tới khi hàm mục tiêu E không thay đổi. Thuật toán K-Means là tƣơng đối mềm dẻo và hiệu quả trong việc 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(NKt), với N là tổng số các đối tƣợng, K là số lƣợng cụm, và t là số vòng lặp. Thông thƣờng thì K
Để thực hiện bƣớc 4 trong thuật toán A, thuật toán K-Medoids trƣớc đây nhƣ PAM (Partitioning Around Medoids) (Kaufman & Rousseeuw, 1990) lặp tất cả K tâm và cố gắng thay thế mỗi tâm bởi N-K đối tƣợng còn lại. Với mỗi sự thay thế này, nếu hàm sai số bình phƣơng E giảm, thì sự thay thế đƣợc giữ lại, và vòng lặp tiếp theo của thuật toán A đƣợc thực hiện. Tuy nhiên, nếu không có sự thay thế nào đƣợc tìm thấy sau khi đã thực hiện xong K tâm, tức là không làm giảm hàm E thì thuật toán sẽ kết thúc với nghiệm tối ƣu cục bộ. Do độ phức tạp lớn nên thuật toán phân hoạch nhƣ PAM chỉ thực hiện hiệu quả đối với các tập dữ liệu nhỏ, không phù hợp với các tập dữ liệu lớn. Để thực hiện với các tập dữ liệu lớn, phƣơng pháp phân cụm dựa trên mẫu (Sampling – based method) là CLARA (Clustering LARge Applications) đã đƣợc phát triển bởi Kaufman & Rousseeuw. Thuật toán chọn một phần của dữ liệu thực làm mẫu thay cho việc xem toàn bộ tập dữ liệu. Các tâm đƣợc chọn từ các mẫu sử dụng thuật toán PAM và độ bất tƣơng đồng trung bình đƣợc tính cho toàn bộ tập dữ liệu. Nếu có một tập các tâm mới có độ bất tƣơng đồng thấp hơn lời giải tốt nhất trƣớc đó, thì lời giải tốt nhất đƣợc thay thế bởi tập tâm mới này, chi tiết thuật toán xem ở. 1.2.2. Các phương pháp phân cụm phân cấp Phƣơng pháp phân cụm này tạo ra đồ thị dữ liệu. Cấu trúc của các đồ thị đƣợc thực hiện theo hai cách: bottom-up và top-down. Trong mô hình bottom-up, chúng ta xét từng mẫu nhƣ là cụm đơn lẻ và sau đó lần lƣợt kết hợp các cụm gần nhất. Qua từng lƣợt của thuật toán, chúng ta kết hợp hai cụm gần nhất. Quá trình đƣợc lặp lại cho đến khi chúng ta lấy đƣợc tập dữ liệu riêng biệt hoặc xác định chắc chắn giá trị ngƣỡng. Phƣơng pháp top-down, làm việc theo cách ngƣợc lại mô hình bottom-up: chúng ta bắt đầu bằng việc xét toàn bộ các tập nhƣ là cụm đơn và phân chia chúng vào các cụm nhỏ hơn. Xét về bản chất, những phƣơng thức này thƣờng không có khả năng tính toán, và có thể có ngoại lệ với các mẫu có giá trị nhị phân. 20