Tài liệu Phân cụm dữ liệu định tính sử dụng lý thuyết tập thô

bé gi¸o dôc vµ ®µo t¹o tr­êng ®¹i häc b¸ch khoa hµ néi --------------------------------------Hoµng thÞ hµ Ph©n côm d÷ liÖu ®Þnh tÝnh sö dông lý thuyÕt tËp th« Chuyªn ngµnh : C«ng nghÖ th«ng tin luËn v¨n th¹c sÜ c«ng nghÖ th«ng tin ng­êi h­íng dÉn khoa häc : TS. NguyÔn kim Anh Hµ NéI – 2008 1 DANH MỤC CÁC CHỮ VIẾT TẮT Từ hoặc cụm từ Từ viết tắt Từ tiếng Anh Cơ sở dữ liệu Phân cụm dữ liệu CSDL PCDL Database Data Clustering Công nghệ thông tin CNTT Khám phá tri thức KDD Information Technology Knowledge Discovery in Database Lý thuyết tập thô RST 2 Rough Set Theory MỤC LỤC Trang DANH MỤC CÁC CHỮ VIẾT TẮT ........................................................1 MỤC LỤC .................................................................................................3 DANH MỤC CÁC BẢNG .......................................................................5 DANH SÁCH HÌNH VẼ...........................................................................6 TỪ KHOÁ .................................................................................................6 CHƯƠNG 1 : TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ KHÁM PHÁ TRI THỨC TRONG CSDL............................................................10 1.1 Tổng quan về khai phá dữ liệu ......................................................................... 10 1.1.1 Giới thiệu chung ............................................................................................ 10 1.1.2 Lịch sử khai phá dữ liệu ............................................................................... 11 1.1.3 Các nhiệm vụ chính và những thách thức của khai phá dữ liệu.............. 12 1.1.4 Các kỹ thuật tiếp cận trong khai phá dữ liệu ............................................. 12 1.1.5 Ứng dụng của khai phá dữ liệu.................................................................... 13 1.2 Quá trình khám phá tri thức trong CSDL .................................................... 14 1.2.1 Khái niệm KDD ............................................................................................. 14 1.2.2 Quá trình khám phá tri thức trong CSDL .................................................. 14 1.3 Phân cụm dữ liệu và vai trò của nó trong khai phá dữ liệu....................... 16 CHƯƠNG 2: PHÂN CỤM DỮ LIỆU....................................................17 2.1 Giới thiệu chung................................................................................................... 17 2.2 Các giai đoạn phân cụm ..................................................................................... 19 2.3 Các ứng dụng của phân cụm............................................................................. 20 2.4 Các kiểu thuộc tính và các độ đo của chúng trong phân tích cụm........... 21 2.4.1 Phân loại các thuộc tính dựa trên kích thước miền [4][3]:.................... 21 2.4.2 Phân loại các thuộc tính dựa trên thang đo ............................................... 22 2.4.3 Tương tự và phi tương tự .............................................................................. 23 2.5 Các kỹ thuật phân cụm dữ liệu ........................................................................ 28 2.5.1 Các thuật toán phân hoạch .......................................................................... 29 2.5.2 Các thuật toán phân cấp ............................................................................... 29 2.5.3 Các thuật toán dựa trên mật độ ................................................................... 32 2.5.4 Các thuật toán dựa trên lưới ........................................................................ 32 2.6 Các tiêu chí đánh giá một thuật toán PCDL hiệu quả trong khai phá dữ liệu 34 CHƯƠNG 3: THUẬT TOÁN PHÂN CỤM DỮ LIỆU ĐỊNH TÍNH SỬ DỤNG LÝ THUYẾT TẬP THÔ.............................................................36 3.1 Giới thiệu chung................................................................................................... 36 3.2 Dữ liệu định tính và vấn đề phân cụm dữ liệu định tính ............................ 36 3.3 Khảo cứu một số thuật toán phân cụm dữ liệu định tính điển hình ........ 37 3.3.1 Thuật toán k-modes ...................................................................................... 37 3.3.2 Thuật toán ROCK [13] ................................................................................. 39 3.3.3 Thuật toán CACTUS [11]............................................................................. 39 3 3.3.4 Thuật toán phân cụm Squeezer [33] ........................................................... 40 3.3.5 Thuật toán phân cụm dữ liệu mờ Fuzzy K-modes ..................................... 41 3.3.6 Nhận xét chung về các thuật toán................................................................ 43 3.4 Tiếp cận lý thuyết tập thô phân cụm dữ liệu định tính............................... 44 3.4.1 Lý thuyết tập thô và ứng dụng..................................................................... 44 3.4.1.1 3.4.1.2 Một số khái niệm cơ bản [26] ......................................................................45 Các ứng dụng của RST.................................................................................49 3.4.2.1 3.4.2.2 3.4.2.3 3.4.2.4 3.4.2.5 Ý tưởng thuật toán........................................................................................50 Một số định nghĩa bổ trợ thuật toán ............................................................51 Thuật toán MIN-MIN-ROUGHNESS (MMR) ..............................................52 Ví dụ minh họa thuật toán MMR..................................................................55 Độ phức tạp của thuật toán MMR ...............................................................58 3.4.2 Thuật toán phân cụm dữ liệu định tính MMR ............................................ 50 CHƯƠNG 4: THỬ NGHIỆM VÀ ĐÁNH GIÁ GIẢI THUẬT MMR ..59 4.1 Xây dựng chương trình thử nghiệm................................................................ 59 4.1.1 Về môi trường lập trình ................................................................................ 59 4.1.2 Về chương trình ............................................................................................. 59 4.2 Dữ liệu thử nghiệm.............................................................................................. 62 4.3 Kết quả thử nghiệm và đánh giá giải thuật ................................................... 63 TÀI LIỆU THAM KHẢO .......................................................................71 PHỤ LỤC: MỘT SỐ MODUL CÀI ĐẶT ..............................................74 4 DANH MỤC CÁC BẢNG Bảng 2.1: Bảng sự kiện ...................................................................... 25 Bảng 3.1: Tổng kết một số đặc điểm của các thuật toán phân cụm dữ liệu định tính ............................................................................................ 43 Bảng 3.2 : Bảng thông tin về các triệu chứng của 6 bệnh nhân ............. 45 Bảng 3.3. Một số ứng dụng của RST .................................................. 50 Bảng 3.4: Tập dữ liệu mẫu ................................................................. 55 Bảng 3.5: Tính trung bình roughness cho thuộc tính a1 ....................... 56 Bảng 3.6: Tính MMR ........................................................................ 56 Bảng 4.1: Chi tiết các file dữ liệu thử nghiệm ..................................... 62 Bảng 4.2. Kết quả phân cụm tập dữ liệu Soybean................................ 63 Bảng 4.3. Kết quả phân cụm tập dữ liệu Zoo....................................... 64 Bảng 4.4: So sánh chất lượng phân cụm của thuật toán MMR với ba thuật toán fuzzy centroid, K-modes, fuzzy K-modes ............................ 65 Bảng 4.5 : So sánh chất lượng phân cụm của thuật toán MMR với Squeezer, K-mode .............................................................................. 66 5 DANH SÁCH HÌNH VẼ Hình 1.1: Các lĩnh vực liên quan đến khai phá dữ liệu ......................... 11 Hình 1.2: Các bước thực hiện trong quá trình khám phá tri thức .......... 14 Hình 2.1: Các bước xử lý phân cụm ................................................... 20 Hình 2.2: Các chiến lược phân cụm phân cấp...................................... 31 Hình 2.3: Phương pháp PCDL cổ điển “phân hoạch” và “phân cấp” .... 31 Hình 2.4: Mô hình cấu trúc dữ liệu lưới .............................................. 33 Hình 3.1: Thuật toán Fuzzy K-modes ................................................. 41 Hình 3.2: Mối quan hệ giữa xấp xỉ trên, xấp xỉ dưới và miền bao........ 48 Hình 3.3: Thuật toán MMR ................................................................ 54 Hình 3.4: Phần chia sau lần lặp đầu tiên.............................................. 57 Hình 4.1: Chức năng hiện cây phân cụm............................................. 60 Hình 4.2: Chức năng hiển thị thời gian và tiến trình tính toán .............. 61 Hình 4.3: Chức năng hiển thị Log quá trình tính toán .......................... 61 Hình 4.4. Biểu đồ biểu thị mối quan hệ giữa chất lượng cụm và số cụm62 Hình 4.5: Chất lượng phân cụm của MMR trên tập dữ liệu Zoo ........... 64 TỪ KHOÁ Khai phá dữ liệu, phân cụm dữ liệu, phân cụm dữ liệu định, lý thuyết tập thô 6 MỞ ĐẦU Với sự bùng nổ CNTT hiện nay, việc tìm ra các thông tin hữu ích, tiềm ẩn từ kho dữ liệu lớn là một vấn đề hết sức quan trọng trong nhiều ứng dụng thực tiễn. Quá trình tìm kiếm tri thức trong các CSDL lớn chính là nhiệm vụ của khai phá dữ liệu – một lĩnh vực khoa học đang được quan tâm nghiên cứu rộng rãi. Trong các nhiệm vụ của khai phá dữ liệu thì phân cụm dữ liệu đóng một vai trò quan trọng trong quá trình khám phá tri thức. Bài toán phân cụm dữ liệu thuộc lĩnh vực học không giám sát, nhằm phân tập dữ liệu thành các tập con thỏa mãn điều kiện: các đối tượng trong cùng một tập có độ tương đồng cao, các đối tượng ở các tập khác nhau có độ tương đồng thấp. Các kỹ thuật phân cụm đã được ứng dụng trong nhiều lĩnh vực, chẳng hạn như: trong Y học, trong kinh doanh, trong tin sinh,…Tuy nhiên, cho đến nay hầu hết các phương pháp phân cụm đều tập trung trên tập dữ liệu có các thuộc tính định lượng.Vì dữ liệu của thế giới thực rất đa dạng và tồn tại nhiều thuộc tính định tính nên những năm gần đây vấn đề phân cụm dữ liệu định tính đang được các nhà khoa học quan tâm. Thực tế, đã có một số công trình nghiên cứu thành công trên dữ liệu dạng này. Có thể kể đến một số thuật toán điển hình như: K-modes(1998), fuzzy K-mode (1999) của Huang; ROCK (1999) của Guha et al.; CACTUS (1999) của Venkatesh Ganti, Johannes Gehrke và Raghu Ramakrishnan; Squeezer(2000) của HE Zengyou, XU Xiaofei và DENG Shengchun,… Những thuật toán trên đã đóng góp rất lớn cho quá trình phân cụm dữ liệu định tính, nhưng phần lớn không được thiết kế để điều khiển không chắc chắn(uncertaily) trong quá trình phân cụm, một số ít có điều khiển mờ nhưng lại gặp phải vấn đề về tính ổn định. Điều này rất quan trọng đối với các ứng dụng thực. Vậy cần nghiên cứu một cách tiếp cận khác ổn định hơn mà vẫn có thể điều khiển không chắc chắn. Sử dụng lý thuyết tập thô để phân cụm dữ liệu có thể giải quyết được hai vấn đề nêu trên. Chính vì những lý do trên, tôi chọn hướng nghiên cứu “Phân cụm dữ liệu định tính sử dụng lý thuyết tập thô” làm đề tài nghiên cứu cho luận văn của mình. Luận văn trình bày hệ thống về khai phá dữ liệu, PCDL nói chung và 7 khảo cứu một số thuật toán PCDL định tính nói riêng. Đặc biệt, tập trung nghiên cứu thuật toán sử dụng lý thuyết tập thô vào quá trình phân cụm dữ liệu định tính. Trên cơ sở đó phân tích, đánh giá, so sánh với các hướng tiếp cận truyền thống. PCDL dựa trên RST là một cách tiếp cận hoàn toàn mới trong lĩnh vực phân cụm. Hiện nay, vấn đề này đang được các nhà khoa học quan tâm nghiên cứu nhằm tìm ra một giải pháp phân cụm đạt kết quả tốt cả về định lượng lẫn định tính. Luận văn được bố cục như sau: Chương 1 tập trung trình bày tổng quan về lĩnh vực khai phá dữ liệu, đồng thời chỉ ra các giai đoạn thực hiện trong quá trình khám phá tri thức và vai trò của PCDL trong khai phá dữ liệu . Chương 2 trình bày vấn đề về PCDL, đây là một hướng tiếp cận chính trong khai phá dữ liệu. Trong đó, đi sâu tìm hiểu chi tiết các vấn đề cơ bản trong PCDL và ý nghĩa của PCDL, đặc điểm của các kiểu dữ liệu cơ bản thường sử dụng trong PCDL như: dữ liệu có thuộc định lượng (number), dữ liệu có thuộc tính định tính (Categorica)l,… Các khái niệm về “tương tự” và “phi tương tự” cũng được trình bày trong chương này. Phần cuối của chương trình bày vắn tắt các đặc trưng của các phương pháp PCDL được sử dụng phổ biến như: Phương pháp phân cụm phân hoạch, phương pháp phân cụm phân cấp, phương pháp phân cụm dựa trên mật độ,…đồng thời nêu ra các tiêu chí đánh giá kết quả PCDL. Chương 3, khảo cứu một số thuật toán phân cụm dữ liệu định tính điển hình như: K-mode, ROCK, CACTUS, Squeezer, fuzzy K-mode có chỉ ra các ưu điểm, nhược điểm của mỗi thuật toán. Tiếp đó trình bày một cơ sở lý thuyết khá hiện đại - lý thuyết tập thô và nội dung thuật toán MMR áp dụng lý thuyết tập thô vào phân cụm dữ liệu định tính. Chương 4, thực hiện cài đặt và thử nghiệm thuật toán MMR đã được trình bày ở chương 3. Trên cơ sở đó phân tích, đánh giá và so sánh với các thuật toán đã trình bày ở đầu chương 3. 8 Phần kết luận, phần này trình bày tóm tắt về các nội dung thực hiện trong luận văn này, đồng thời đưa ra những vấn đề nghiên cứu tiếp theo cho tương lai. Phần phụ lục trình bày một số mô đun chương trình cài đặt cho thuật toán MMR. 9 CHƯƠNG 1 : TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ KHÁM PHÁ TRI THỨC TRONG CSDL 1.1 Tổng quan về khai phá dữ liệu 1.1.1 Giới thiệu chung Cùng với sự phát triển vượt bậc của các công nghệ điện tử và truyền thông, hiện nay có nhiều công cụ thu thập dữ liệu tự động và tổ chức cơ sở dữ liệu (CSDL) nên số lượng dữ liệu lưu trữ trong các CSDL khá khổng lồ. Thông tin trên thế giới cứ 20 tháng lại tăng lên gấp đôi [30]. Kích cỡ và số lượng các CSDL không ngừng được tăng lên theo hai hướng : - Tăng số các bản ghi (hoặc các đối tượng trong CSDL) - Tăng số các trường (hoặc các thuộc tính) của từng đối tượng. Tình trạng đó gây ra hiện tượng ứng lụt dữ liệu. Vấn đề đặt ra là phải xử lý thô thế nào để tìm thông tin hữu ích (phát hiện tri thức). Đây chính là nhiệm vụ đặt ra cho một lĩnh vực nghiên cứu được quan tâm nhiều trong những năm gần đây. Đó là lĩnh vực khai phá dữ liệu (Khai phá dữ liệu). Vậy Khai phá dữ liệu là gì?. Khai phá dữ liệu là một hướng nghiên cứu mới ra đời gần hai thập niên trở lại đây, các kỹ thuật chính được áp dụng trong lĩnh vực này phần lớn được thừa kế từ lĩnh vực CSDL, học máy, trí tuệ nhân tạo, lý thuyết thông tin, xác suất thống kê. Do sự phát triển nhanh của khai phá dữ liệu về phạm vi áp dụng và các phương pháp tìm kiếm tri thức, nên đã có nhiều quan điểm khác nhau về khai phá dữ liệu. Tuy nhiên, ở một mức trừu tượng nhất định, chúng ta định nghĩa khai phá dữ liệu như sau [14][8]: “Khai phá dữ liệu là một quá trình tìm kiếm, phát hiện các tri thức mới, tiềm ẩn, hữu dụng trong CSDL lớn”. Các lĩnh vực liên quan đến khai phá dữ liệu (Hình 1.1) [30]: 10 Công nghệ CSDL (Database Technology) Học máy (Machine Learning) Thống kê (Statistics) Trực quan hóa (Visualization) Khai phá dữ liệu (Data Mining) Trí truệ nhân tạo (Artificial Intelligence) Các lĩnh vực khác Hình 1.1: Các lĩnh vực liên quan đến khai phá dữ liệu 1.1.2 Lịch sử khai phá dữ liệu Khai phá dữ liệu là một lĩnh vực nghiên cứu được ra đời vào cuối những năm 1980s và đã nhanh chóng phát triển khá mạnh vào những năm 1990s. Các kết quả khoa học cùng những ứng dụng thành công trong khám phá tri thức, cho thấy, khai phá dữ liệu là một lĩnh vực phát triển bền vững, mang lại nhiều lợi ích và có nhiều triển vọng. Ngày nay, khai phá dữ liệu đã ứng dụng ngày càng rộng rãi vào nhiều lĩnh vực như : Thương mại, tài chính, điều trị y học, viễn thông, tin – sinh, xử lý ảnh…. Các kỹ thuật chính được áp dụng trong khai phá dữ liệu phần lớn được thừa kế từ ba lĩnh vực cơ bản : Thống kê (Statistics), trí tuệ nhân tạo (Artificial Intelligence), học máy (Machine Learning). Tùy thuộc vào từng ngành mà khai phá dữ liệu có các cách gọi riêng. Khai phá dữ liệu còn có một số thuật ngữ khác hay dùng như: khai phá tri thức quý (Gold Mining), trích rút tri thức (Knowledge extraction), phân tích mẫu hoặc dữ liệu (Data/pattern analysis), khám phá tri thức trong CSDL (Knowledge Discovery Databases - KDD), gặt hái thông tin (Information harvesting). 11 1.1.3 Các nhiệm vụ chính và những thách thức của khai phá dữ liệu * Những nhiệm vụ chính: Khai phá dữ liệu là quá trình khai phá tri thức tiềm ẩn, hữu ích từ kho dữ liệu lớn nên nó có những nhiệm vụ sau [30]:  Mô tả khái niệm các lớp(Concept/Class description)  Khám phá ra các luật kết hợp (Association rules discovery)  Phân lớp và dự đoán (Classification and Prediction)  Phân tích cụm (Cluster analysis)  Phân tích phần tử ngoại lai(Outlier analysis) * Những thách thức của khai phá dữ liệu: Ngày nay, khai phá dữ liệu đang đứng trước nhiều thách thức, đó là: kích thước của dữ liệu không ngừng được tăng lên, ngày càng có nhiều kiểu dữ liệu khác nhau xuất hiện trong các CSDL (text, HTML, XML, multimedia…)., chất lượng dữ liệu của thế giới thực (Real world data) thường lộn xộn và nhiều nhiễu… 1.1.4 Các kỹ thuật tiếp cận trong khai phá dữ liệu Nếu đứng trên quan điểm của học máy (Machine Learning), thì các kỹ thuật trong khai phá dữ liệu, bao gồm các kỹ thuật:  Học có giám sát (Supervised learning) : Là quá trình gán nhãn lớp cho các phần tử trong CSDL dựa trên một tập các ví dụ huấn luyện và các thông tin về nhãn lớp đã biết.  Học không có giám sát (Unsupervised learning): Là quá trình phân chia một tập dữ liệu thành các lớp hay là cụm (clustering) dữ liệu tương tự nhau mà chưa biết trước các thông tin về lớp hay tập các ví dụ huấn luyện.  Học nửa giám sát (Semi - Supervised learning) : Là quá trình phân chia một tập dữ liệu thành các lớp dựa trên một tập nhỏ các ví dụ huấn luyện và một số các thông tin về một số nhãn lớp đã biết trước. Nếu căn cứ vào lớp các bài toán cần giải quyết, thì khai phá dữ liệu bao gồm các kỹ thuật áp dụng sau[14][30]: 12  Phân lớp và dự đoán (classification and prediction): xếp một đối tượng vào một trong những lớp đã biết trước. Phân lớp và dự đoán còn được gọi là học có giám sát.  Luật kết hợp (association rules): là dạng luật biểu diễn tri thức ở dạng khá đơn giản. Luật kết hợp được ứng dụng nhiều trong lĩnh vực kinh doanh, y học, tin-sinh, tài chính và thị trường chứng khoán, .v.v.  Phân tích chuỗi theo thời gian (sequential/ temporal patterns): tương tự như khai phá luật kết hợp nhưng có thêm tính thứ tự và tính thời gian. Hướng tiếp cận này được ứng dụng nhiều trong lĩnh vực tài chính và thị trường chứng khoán vì nó có tính dự báo cao.  Phân cụm (clustering/ segmentation): xếp các đối tượng theo từng cụm dữ liệu tự nhiên. Phân cụm còn được gọi là học không có giám sát ( unsupervised learning).  Mô tả khái niệm (concept description and summarization): thiên về mô tả, tổng hợp và tóm tắt khái niệm. 1.1.5 Ứng dụng của khai phá dữ liệu Khai phá dữ liệu là một lĩnh vực hiện nay đang được thế giới ứng dụng khá rộng rãi. Một số ứng dụng điển hình trong khai phá dữ liệu có thể liệt kê như sau [30]:  Trong lĩnh vực khoa học(Science): Khai phá dữ liệu đã ứng dụng trong các ngành: Hóa học, Vật lý, Y học với các ứng dụng cụ thể như sau: Phân tích hóa sinh( Biochemical analysis), nghiên cứu các bộ cảm ứng xa trên vệ tinh (Remote sensors on a satellite), phân tích các ảnh trong Y học (Medical Image analysis),…  Trong lĩnh vực sinh học (Bioscience): PCDL được ứng dụng để, phân tích chuỗi (Sequence-based analysis), dự đoán cấu trúc Protein và dự đoán hàm (Protein structure and function prediction), tìm ra các lớp Protein cùng họ (Protein family classification), khám phá gene.  Trong ngành tài chính, ngân hàng, kinh doanh và thương mại điện tử: PCDL được ứng dụng để: phân tích sự đầu tư và chúng khoán( Stock and 13 investment analysis), nhận diện những khách hàng trung thành và không trung thành, quản lý rủi ro(Risk management), dự đoán bán hàng (Sales forecasting),…  Trong lĩnh vực phân tích cơ sở dữ liệu và hỗ trợ quyết định (Database analysis and decision support): PCDL được dùng để trợ giúp: quản lý và phân tích thị trường, quản lý và phân tích sự rủi ro, quản lý và dò tìm lỗi,… 1.2 Quá trình khám phá tri thức trong CSDL 1.2.1 Khái niệm KDD KDD chính là khám phá tri thức trong CSDL và cũng là mục tiêu chính của Khai phá dữ liệu, do vậy hai khái niệm Khai phá dữ liệu và KDD được các nhà khoa học trên hai lĩnh vực được xem là tương đương với nhau. Thế nhưng, nếu phân chia một cách chi tiết thì Khai phá dữ liệu là một bước chính trong quá trình KDD. 1.2.2 Quá trình khám phá tri thức trong CSDL Khám phá tri thức trong CSDL là lĩnh vực liên quan đến các ngành như: thống kê, học máy, CSDL, … Quá trình KDD có thể phân thành các giai đoạn sau [30] [14]: Tri thức Dữ liệu thô Biểu diễn tri thức Đánh giá và giải thích Các mẫu Khai phá dữ liệu Dữ liệu Trích chọn dữ liệu Tiền xử lý dữ liệu Dữ liệu Tiền xử lý Biến đổi dữ liệu Hình 1.2: Các bước thực hiện trong quá trình khám phá tri thức  Trích chọn dữ liệu : là bước trích chọn những tập dữ liệu cần được khai phá từ các tập dữ liệu lớn (databases, data warehouses, data repositories) ban đầu theo một số tiêu chí nhất định. 14  Tiền xử lý dữ liệu : là một trong những bước khá quan trọng trong quá trình KDD. Xứ lý này tốn rất nhiều thời gian và công sức của các nhà khai phá dữ liệu thực tế. Sau khi xác định rõ bài toán và thu thập được dữ liệu của bài toán, sẽ thực hiện các kỹ thuật thích hợp cho dữ liệu như loại bỏ nhiễu, quyết định các chiến lược đối với trường dữ liệu bị mất. Khi dữ liệu dầu vào từ nhiều nguồn khac nhau (có thể không nhất quán) cần điều hòa dữ liệu: khử các trường hợp dữ liệu lặp, thống nhất cách ký hiệu, ở đây thường dùng các công cụ thống kê làm trơn dữ liệu, khử nhiễu trong chúng. Sau đó thực hiện làm giảm số chiều dữ liệu (nếu cần thiết và nếu có thể được) bằng cách tìm các đặc trưng hữu dụng để biểu diễn dữ liệu phụ thuộc đích của nhiệm vụ. Tóm lại, đây là bước làm sạch dữ liệu (xử lý với dữ liệu không đầy đủ, dữ liệu nhiễu, dữ liệu không nhất quán, .v.v.), rút gọn dữ liệu (sử dụng hàm nhóm và tính tổng, các phương pháp nén dữ liệu, sử dụng histograms, lấy mẫu, .v.v.), rời rạc hóa dữ liệu (rời rạc hóa dựa vào histograms, dựa vào entropy, dựa vào phân khoảng, .v.v.). Sau bước này, dữ liệu sẽ nhất quán, đầy đủ, được rút gọn, và được rời rạc hóa.  Biến đổi dữ liệu: đây là bước chuẩn hóa và làm mịn dữ liệu để đưa dữ liệu về dạng thuận lợi nhất nhằm phục vụ cho các kỹ thuật khai phá ở bước sau.  Khai phá dữ liệu: đây là bước áp dụng những kỹ thuật phân tích (phần nhiều là các kỹ thuật của học máy) nhằm để khai thác dữ liệu, trích chọn được những mẫu thông tin, những mối liên hệ đặc biệt trong dữ liệu. Đây được xem là bước quan trọng nhất của toàn quá trình KDD.  Đánh giá và biểu diễn tri thức: những mẫu thông tin và mối liên hệ trong dữ liệu đã được khám phá ở bước trên được chuyển dạng và biểu diễn ở một dạng gần gũi với người sử dụng như đồ thị, cây, bảng biểu, luật, .v.v. Đồng thời bước này cũng đánh giá những tri thức khám phá được theo những tiêu chí nhất định. 15 1.3 Phân cụm dữ liệu và vai trò của nó trong khai phá dữ liệu Phân cụm dữ liệu là một kỹ thuật quan trọng trong khai phá dữ liệu dùng để nhóm các dữ liệu có những đặc điểm tương tự từ kho dữ liệu. Nó là một công cụ để khám phá ra các nhóm đối tượng tự nhiên. Từ đó, cho phép người ta đi sâu vào phân tích và nghiên cứu cho từng cụm dữ liệu để khám phá và tìm kiếm các thông tin tiềm ẩn, hữu ích phục vụ cho ra quyết định. Ngày nay, các kỹ thuật phân cụm được ứng dụng rộng rãi trong nhiều lĩnh vực, chẳng hạn như trong: sản xuất, y học, khoa học hạt nhân, tin_ sinh, kinh doanh, xử lý ảnh,…và đã đem lại nhiều thành công trong quá trính khám phá tri thức. Tuy nhiên, các nghiên cứu trước đây về phân cụm thường tập trung trên các dữ liệu có thuộc tính số (numeric attributes)- những thuộc tính có quan hệ thứ tự, liên tục, giữa các đối tượng có thể đo được mức độ sự khác biệt. Do gần đây, trong các CSDL xuất hiện rất nhiều kiểu dữ liệu như: dữ liệu có thuộc tính định tính hay còn gọi là thuộc tính phạm trù (catagorical attribute), dữ liệu dạng hình ảnh, dữ liệu dạng web,… nên vấn đề phân cụm dữ liệu trên các loại dữ liệu này đang nhận được nhiều sự quan tâm của các nhà khoa học.. Kết luận 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 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.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., (1998) đã đưa ra định nghĩa PCDL như sau [16] [9]: 2.1 "PCDL là một kỹ thuật trong khai phá dữ liệu, nhằm tìm kiếm, phát hiện các cụm, các mẫu dữ liệu tương tự nhau tiềm ẩn, quan tâm trong tập dữ liệu lớn, từ đó cung cấp thông tin, tri thức hữu ích cho hỗ trợ cho việc ra quyết định" Vậy, 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ự" (similar) với nhau và phần tử không thuộc cụm thì không tương tự (dissimilarity) với nhau. 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. 18 2.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 . Giai đoạn 2. 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. Giai đoạn 3. 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ó. Giai đoạn 4. 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ả Lựa chọn thuật toán phân cụm Trích chọn đặc trưng Kết quả cuả thuật toán Tri thức Kết quả PCDL cuối cùng Dữ liệu xử lý Hình 2.1: Các bước xử lý phân cụm 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. 2. 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. 3. 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ệ 2.3 20