CHƯƠNG 1: PHÂN CỤM DỮ LIỆU VÀ PHÂN CỤM ĐỒ THỊ DỮ LIỆU 1. Phân cụm dữ liệu 1. Khái niệm và mục tiêu của phân cụm dữ liệu 1. Khái niệm phân cụm dữ liệu Phân cụm dữ liệu là một kỹ thuật trong Data mining 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 và quan trọng trong tập dữ liệu lớn để từ đó cung cấp thông tin, tri thức cho việc ra quyết định.
Phân cụm dữ liệu là sự phân chia một cơ sở dữ liệu lớn thành các nhóm dữ liệu với trong đó các đối tượng tương tự như nhau. Trong mỗi nhóm, một số chi tiết có thể không quan tâm đến để đổi lấy dữ liệu đơn giản hóa. Hay ta có thể hiểu “Phân cụm dữ liệu là quá trình tổ chức các đối tượng thành từng nhóm mà các đối tượng ở mỗi nhóm đều tương tự nhau theo một tính chất nào đó, những đối tượng không tương tự tính chất sẽ ở nhóm khác” [3]. Phân cụm dữ liệu là một ví dụ của phương pháp học không có thầy.
Không giống như phân lớp dữ liệu, phân cụm dữ liệu không đòi hỏi phải định nghĩa trước các mẫu dữ liệu huấn luyện. Vì thế, có thể coi phân cụm dữ liệu là một cách học bằng quan sát, trong khi phân lớp dữ liệu là học bằng ví dụ,. Ngoài ra phân cụm dữ liệu còn có thể được sử dụng như một bước tiền xử lí cho các thuật toán khai phá dữ liệu khác như là phân loại và mô tả đặc điểm, có tác dụng trong việc phát hiện ra các cụm. Chúng ta có thể thấy điều này với một ví dụ đơn giản như sau: Hình 1.1: Ví dụ về phân cụm dữ liệu [3].
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 5 Trong trường hợp này, chúng ta dễ dàng xác định được 4 cụm dựa vào các dữ liệu đã cho; các tiêu chí “tương tự” để phân cụm trong trường hợp này là khoảng cách: hai hoặc nhiều đối tượng thuộc nhóm của chúng được “đóng gói” theo một khoảng cách nhất định. Điều này được gọi là phân cụm dựa trên khoảng cách. Một kiểu khác của phân cụm dữ liệu là phân cụm dữ liệu dựa vào khái niệm: hai hay nhiều đối tượng thuộc cùng nhóm nếu có một định nghĩa khái niệm chung cho tất cả các đối tượng trong đó. Nói cách khác, đối tượng của nhóm phải phù hợp với nhau theo miêu tả các khái niệm đã được định nghĩa, không phải theo những biện pháp đơn giản tương tự.
Mục tiêu của phân cụm dữ liệu Mục tiêu của phân cụm dữ liệu là để xác định các nhóm nội tại bên trong một bộ dữ liệu không có nhãn. Nhưng để có thể quyết định được cái gì tạo thành một cụm tốt. Nhưng làm thế nào để quyết định cái gì đã tạo nên một phân cụm dữ liệu tốt ? Nó có thể được hiển thị rằng không có tiêu chuẩn tuyệt đối “tốt nhất” mà sẽ là độc lập với mục đích cuối cùng của phân cụm dữ liệu. Do đó, mà người sử dụng phải cung cấp tiêu chuẩn, theo cách như vậy mà kết quả của phân cụm dữ liệu sẽ phù hợp với nhu cầu của họ cần.
Ví dụ, chúng ta có thể quan tâm đến việc tìm kiếm đối tượng đại diện cho các nhóm đồng nhất trong “các cụm tự nhiên” và mô tả thuộc tính không biết của chúng trong việc tìm kiếm các nhóm hữu ích và phù hợp hoặc trong việc tìm kiếm các đối tượng bất thường trong dữ liệu (cá biệt, ngoại lệ, nhiễu).2: Ví dụ phân cụm các ngôi nhà dựa trên khoảng cách [3]. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 6 Một vấn đề thường gặp trong phân cụm là hầu hết các dữ liệu cần cho phân cụm đều có chứa dữ liệu 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 hoặc loại bỏ nhiễu trước khi chuyển sang giai đoạn phân tích cụm dữ liệu. Nhiễu ở đây được hiểu là các đối tượng dữ liệu không chính xác, không tường minh hoặc là các đối tượng dữ liệu 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ác thuộc tính của đối tượng nhiễu bằng giá trị thuộc tính tương ứng.
Ngoài ra, dò tìm đối tượng ngoại lai cũng là một trong những hướng nghiên cứu quan trọng trong phân cụm, chức năng của nó là xác định một nhóm nhỏ các đối tượng dữ liệu khác thường so với các dữ liệu trong cơ sở dữ liệu, tức là các đối tượng dữ liệu không tuân theo các hành vi hoặc mô hình dữ liệu nhằm tránh sự ảnh hưởng của chúng tới quá trình và kết quả của phân cụm.3: Ví dụ phân cụm các ngôi nhà dựa trên kích cỡ [3]. Theo các nghiên cứu đến thời điểm hiện nay thì chưa có một phương pháp phân cụm tổng quát nào có thể giải quyết trọn vẹn cho tất cả các dạng cấu trúc cơ sở dữ liệu. Hơn nữa, đối với các phương pháp phân cụm cần có cách thức biểu diễn cấu trúc của cơ sở dữ liệu, với mỗi cách thức biểu diễn khác nhau sẽ có tương ứng một thuật toán phân cụm phù hợp. Vì vậy phân cụm dữ liệu vẫn đang là một vấn đề khó và mở, vì phải giải quyết nhiều vấn đề cơ bản một cách trọn vẹn và phù hợp với nhiều dạng dữ liệu khác nhau, đặc biệt là đối với dữ liệu hỗn hợp đang ngày càng tăng trong các hệ quản trị dữ liệu và đây cũng là một trong những thách thức lớn trong lĩnh vực khai phá dữ liệu.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Một số khái niệm cần thiết khi tiếp cận phân cụm dữ liệu 1. Phân loại các kiểu dữ liệu Cho một CSDL D chứa n đối tượng trong không gian k chiều trong đó x, y, z là các đối tượng thuộc D : x = (x1,x2,.,zk), trong đó xi, yi, zi với i = 1…k là các đặc trưng hoặc thuộc tính tương ứng của các đối tượng x, y, z. Sau đây là các kiểu dữ liệu: a.
Phân loại các kiểu dữ liệu dựa trên kích thước miền - Thuộc tính liên tục (Continuous Attribute) : nếu miền giá trị của nó là vô hạn không đếm được - Thuộc tính rời rạc (DiscretteAttribute): Nếu miền giá trị của nó là tập hữu hạn, đếm được - Lớp các thuộc tính nhị phân: là trường hợp đặc biệt của thuộc tính rời rạc mà miền giá trị của nó chỉ có 2 phần tử được diễn tả như : Yes/No hoặc Nam/Nữ, False/true,… b. Phân loại các kiểu dữ liệu dựa trên hệ đo Giả sử rằng chúng ta có hai đối tượng x, y và các thuộc tính xi, yi tương ứng với thuộc tính thứ i của chúng. Chúng ta có các lớp kiểu dữ liệu như sau : - Thuộc tính định danh (Nominal Scale): đây là dạng thuộc tính khái quát hoá của thuộc tính nhị phân, trong đó miền giá trị là rời rạc không phân biệt thứ tự và có nhiều hơn hai phần tử -nghĩa là nếu x và y là hai đối tượng thuộc tính thì chỉ có thể xác định là x ≠ y hoặc x = y. - Thuộc tính có thứ tự (Ordinal Scale): là thuộc tính định danh có thêm tính thứ tự, nhưng chúng không được định lượng.
Nếu x và y là hai thuộc tính thứ tự thì ta có thể xác định là x ≠ y hoặc x = y hoặc x > y hoặc x < y. - Thuộc tính khoảng (Interval Scale): Với thuộc tính khoảng, chúng ta có thể xác định một thuộc tính là đứng trước hoặc đứng sau thuộc tính khác với một khoảng là bao nhiêu. Nếu xi > yi thì ta nói x cách y một khoảng xi - yi tương ứng với thuộc tính thứ i. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 8 - Thuộc tính tỉ lệ (Ratio Scale): là thuộc tính khoảng nhưng được xác định một cách tương đối so với điểm mốc, thí dụ như thuộc tính chiều cao hoặc cân nặng lấy điểm 0 làm mốc.
Trong các thuộc tính dữ liệu trình bày ở trên, thuộc tính định danh và thuộc tính có thứ tự gọi chung là thuộc tính hạng mục (Categorical), thuộc tính khoảng và thuộc tính tỉ lệ được gọi là thuộc tính số (Numeric). Độ đo tương tự và phi tương tự Để phân cụm, người ta phải đi tìm cách thích hợp để xác định “khoảng cách” giữa các đối tượng, hay là phép đo tương tự dữ liệu. Đây là các hàm để đo sự giống nhau giữa các cặp đối tượng dữ liệu, thông thường các hàm này hoặc là để tính độ tương tự (Similar) hoặc là tính độ phi tương tự (Dissimilar) giữa các đối tượng dữ liệu. Không gian metric Tất cả các độ đo dưới đây được xác định trong không gian độ đo metric.
Một không gian metric là một tập trong đó có xác định các “khoảng cách” giữa từng cặp phần tử, với những tính chất thông thường của khoảng cách hình học. Nghĩa là, một tập X (các phần tử của nó có thể là những đối tượng bất kỳ) các đối tượng dữ liệu trong CSDL D như đã đề cập ở trên được gọi là một không gian metric nếu: - Với mỗi cặp phần tử x, y thuộc X đều xác định, theo một quy tắc nào đó, một số thực δ(x,y), được gọi là khoảng cách giữa x và y. - Quy tắc nói trên thoả mãn hệ tính chất sau : δ(x,y) > 0 nếu x ≠ y ; (ii) δ(x, y) = 0 nếu x = y; (iii) δ(x,y) = δ(y,x) với mọi x,y; (iv) δ(x,y) ≤ δ(x,z) + δ(z,y). Hàm δ(x,y) được gọi là một metric của không gian.
Các phần tử của X được gọi là các điểm của không gian này. Thuộc tính khoảng cách: Sau khi chuẩn hoá, độ đo phi tương tự của hai đối tượng dữ liệu x,y được xác định bằng các metric khoảng cách như sau [6]: - Khoảng cách Minskowski: trong đó q là số tự nhiên dương.1) i 1 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 9 - Khoảng cách Euclide: Đây là trường hợp đặc biệt của khoảng cách Minskowski trong trường hợp q = 2.2) i 1 - Khoảng cách Manhattan: Đây là trường hợp đặc biệt của khoảng cách Minskowski trong trường hợp q = 1.3) i 1 - Khoảng cách cực đại: là trường hợp của khoảng cách Minskowski trong trường hợp q = ∞. d x, y Maxin1 xi yi (1.