chương 1: Như vậy, chương này đã trình bày một cách tổng quan về vấn đề khai phá dữ liệu với các ứng dụng của nó, quá trình khám phá tri thức trong CSDL và vai trò của PCDL trong khai phá dữ liệu. Nó làm nền tảng cho chương tiếp theo. 16 CHƯƠNG 2: PHÂN CỤM DỮ LIỆU 2.1 Giới thiệu chung Phân cụm dữ liệu là một kỹ thuật quan trọng trong khai phá dữ liệu đượ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. 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 để khám phá cấu trúc của dữ liệu mà không yêu cầu các giả thiết cho trước từ các phương pháp thống kê.
Mục tiêu của phương pháp phân cụm dữ liệu là tìm kiếm các nhóm đối tượng theo hình dạng tự nhiên. 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 [9][16]. Có nhiều định nghĩa về PCDL, tuy nhiên ở một mức cơ bản nhất, Guha et al.
Số các cụm dữ liệu được phân có thể được xác định trước theo kinh nghiệm hoặc có thể được tự động xác định theo thuật toán phân cụm. Một khó khăn thường gặp trong PCDL đó 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" (noise) 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 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 không chính xác, hoặc là các đối tượng dữ liệu khuyết thiếu 17 thông tin ở 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.
Ngoài ra, dò tìm phần tử ngoại lai (Outlier) là một trong những hướng nghiên cứu quan trọng trong phân cụm dữ liệu cũng như trong khai phá dữ liệu. 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 CSDL - 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 PCDL. Khám phá các phần tử ngoại lai đã được phát triển và ứng dụng trong viễn thông, dò tìm gian lận thương mại và trong làm sạch dữ liệu,vv… Phân cụm dữ liệu phải đi giải quyết các vấn đề cơ bản sau : Xây dụng hàm tính độ tương tự. Xây dựng các tiêu chuẩn phân cụm.
Xây dựng mô hình cho cấu trúc cụm dữ liệu Xây dựng thuật toán phân cụm và các xác lập các điều kiện khởi tạo. Xây dựng các thủ tục biểu diễn và đánh giá kết quả phân cụm Theo các nghiên cứu, đến nay 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ụm dữ liệu. Hơn nữa, 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ác cụm 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. PCDL đang là vấn đề mở và khó, vì rằng người ta cần phải đi giải quyết nhiều vấn đề cơ bản như đã đề cập ở trê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 các dữ liệu định tính (categorical data) và các dữ liệu hỗn hợp.
Những dạng dữ liệu này đang ngày càng tăng trưởng và không ngừng xuất hiện trong các CSDL, đâ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 trong những thập kỷ tiếp theo.2 Các giai đoạn phân cụm Theo Fayyad et al., 1996 phân cụm dữ liệu được chia thành các giai đoạn sau [8]: Giai đoạn 1. Trích chọn các đặc trưng (Feature Selection): Mục đí ch của giai đoạn này là trích chọn những đặc trưng hợp lệ đối với tập dữ liệu của bài toán xác định, tránh trường hợp tồn tại những đặc trưng dư thừa, nhằm áp dụng một cách hiệu quả các kỹ thuật khai phá dữ liệu. Lựa chọn thuật toán phân cụm (Selection Algorithm s): Đây là bước lựa chọn thuật toán phân cụm, sao cho nó phù hợp nhất với tập dữ liệu và yêu cầu đã cho. Độ đo sự tương tự (similary measure) hoặc phi tương tự (dissimilary measure) giữa hai đối tượng và điều kiện phân cụm (clustering criterion) trong mỗi thuật toán là những đặc điểm được xem xét chính để quyết định lựa chọn một thuật toán phân cụm hiệu quả đối với bài toán.
Ngoài hai đặc điểm trên cũng cần phải xem xét đến đặc điểm, kích thước chiều của tập dữ liệu. Xác nhận tính hợp lệ của các kết quả(Validation of results): Đây là một trong những giai đoạn cuối của quá trình phân cụm. Giai đoạn này thường dựa vào việc kiểm tra một cách thủ công và các các kỹ thuật trực quan để xác nhận kết quả phân cụm. Mặc dù vậy, khi tập dữ liệu lớn, thì việc sử dụng phương pháp trên là không thể.
Khi đó phải so sánh kết quả với các thuật toán đã có. Phiên dịch - giải thích (Interpretation) : Giai đoạn này các chuyên gia trong lĩnh vực ứng dụng phải kết hợp kết quả phân cụm với các minh chứng thử nghiệm khác phân tích, giải thích đưa ra kết luận đúng đắn cho người sử dụng. 19 Các giai đoạn phân cụm có thể được mô tả như sau (hình 2.1) [16]: Giải thích kết quả Xác nhận tính hợp lệ của kết quả Tri thức Lựa chọn thuật toán phân cụm Kết quả PCDL Kết quả cuối Trích chọn cùng đặc trưng cuả thuật toán Dữ liệu xử lý Hình 2.1: Các bước xử lý phân cụm 2.3 Các ứng dụng của phân cụm Phân cụm là một công cụ chính để xem xét phân bố dữ liệu và làm bước tiền xử lý cho các thuật toán khác. Hiện nay, nó đã ứng dụng ở nhiều trong lĩnh vực kinh doanh và khoa học.
Dưới đây sẽ nêu một số lĩnh vực ứng dụng của phân cụm [14]: 1. Trong kinh doanh (Business): Trong kinh doanh, phân cụm có thể giúp các cửa hàng khám phá ra các nhóm phân biệt trong CSDL mua hàng. Trong sinh học(Biology): Trong sinh học, nó có thể được sử dụng để định nghĩa sự phân loại, các nhóm genes có độ tương đồng cao. Trong phân tích dữ liệu không gian (Spatial data analysis): Phần lớn dữ liệu không gian có thể có được từ các ảnh vệ tinh, các thiết bị y tế, các hệ thống thông tin đại lý GIS, sự khám phá CSDL ảnh,…nó rất khó cho người sử dụng để kiểm tra dữ liệu vệ tinh một cách chi tiết.
Phân cụm có thể giúp tự động xử lý quá trình phân tích và hiểu dữ liệu vệ tinh. Nó rất có ích trong việc nhận diện và trích rút các đặc điểm và mẫu hứu ích tồn tại trong các CSDL vệ 20 tinh lớn. Ví dụ như trong sử dụng đất, phân cụm giúp nhận dạng các vùng đất sử dụng giống nhau khi khảo sát CSDL đất 4. Trong bảo hiểm: Phân cụm dùng để nhận dạng các nhóm công ty có chính sách bảo hiểm mô tô với chi phí đền bù trung bình cao 5.
Trong hoạch định thành phố: Phân cụm giúp nhận dạng các nhóm nhà cửa theo loại nhà, giá trị và vị trí địa lý. Khám phá Web (Web mining): Trong trường hợp này, phân cụm được sử dụng để khám phá các nhóm tài liệu hữu ích trên Web theo một số tiêu chí. Sự phân lớp các tài liệu Web giúp người sử dụng có thể khai phá thông tin.4 Các kiểu thuộc tính và các độ đo của chúng trong phân tích cụm Trong phần này chúng ta phân tích các kiểu dữ liệu thường được sử dụng trong phân cụm dữ liệu. Trong phân cụm dữ liệu, các đối tượng dữ liệu cần phân tích có thể là con người, cái nhà, tiền lương, quan điểm,….
Các đối tượng này thường được diễn tả dưới dạng các đặc tính hay còn gọi là thuộc tính. Các thuộc tính này là các tham số cho giải quyết vấn đề phân cụm dữ liệu và sự lựa chọn chúng có tác động đáng kể đến các kết quả phân cụm. Phân loại các kiểu thuộc tính khác nhau là một vấn đề cần giải quyết đối với hầu hết các tập dữ liệu, nhằm cung cấp các phương tiện thuận lợi để nhận dạng sự khác nhau của các phần tử dữ liệu. Dưới đây là cách phân loại dựa trên hai đặc trưng là: kíc h thước miền (Domain Size) và thang đo (Measurement Scale).
Cho một CSDL D chứa n đối tượng trong không gian k chiều, 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. Vì vậy, hai khái niệm “các kiểu dữ liệu” và “các kiểu dữ liệu thuộc tính” được xem là tương đương với nhau. Dưới đây sẽ giới thiệu một số kiểu dữ liệu: 2.1 Phân loại các thuộc tính dựa trên kích thước miền [4][3]: Thuộc tính liên tục (Continuous Attribute): là thuộc tính nếu miền giá trị của nó là vô hạn không đếm được, nghĩa là giữa hai giá trị tồn tại vô 21 số giá trị khác nhau. Thí dụ như các thuộc tính về màu, nhiệt độ hoặc cường độ âm thanh.
Thuộc tính rời rạc (DiscretteAttribute) : là thuộc tính nếu miền giá trị của nó là tập hữu hạn, đếm được. Thí dụ như các thuộc tính về số serial của một cuốn sách, số thành viên trong một gia đình, … 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 giá trị khác nhau, đối lập nhau được diễn tả như: Yes / No hoặc Male/Female, True/ False,… 2.2 Phân loại các thuộc tính dựa trên thang đo Cho thuộc tính i và hai đối tượng x, y có các giá trị xi, yi tương ứng trên thuộc tính này, người ta phân các thuộc tính như sau [4][3]: Thang đo khoảng (Interval Scale): Nhằm để đo các giá trị theo xấp xỉ tuyến tính. Với thang đo khoảng, chúng ta không chỉ xác định được một giá trị thuộc tính là đứng trước hoặc đứng sau một giá trị thuộc tính khác mà còn biết được chúng cách nhau một khoảng là bao nhiêu.