LUẬN VĂN: NGHIÊN CỨU CÁC KỸ THUẬT PHÂN CỤM DỮ LIỆU VÀ ỨNG DỤNG

Chia sẻ: Sunflower Sunflower_1 | Ngày: | Loại File: PDF | Số trang:101

Thêm vào BST

Báo xấu

645
lượt xem 182
download

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

Nội dung chính của luận văn được trình bày trong 3 chương:Chương 1: Tổng quan về khai phá tri thức và khai phá dữ liệu. Trong chương này trình bày tổng quan về khai phá tri thức, khai phá dữ liệu; qui trình khai phá tri thức, khai phá dữ liệu; …

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: NGHIÊN CỨU CÁC KỸ THUẬT PHÂN CỤM DỮ LIỆU VÀ ỨNG DỤNG

i ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ =================== Nguyễn Thị Huế NGHIÊN CỨU CÁC KỸ THUẬT PHÂN CỤM DỮ LIỆU VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ HÀ NỘI - 2011
ii LỜI CẢM ƠN Để hoàn thành được luận văn này, trước hết tôi xin gửi lời cảm ơn sâu sắc nhất tới GS.TS Vũ Đức Thi, Viện trưởng Viện công nghệ thông tin đã tận tình hướng dẫn, chỉ bảo, định hướng, đóng góp những ý kiến quý báu trong suốt 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ô giáo trong Bộ môn Hệ thống thông tin, Khoa Công nghệ thông tin, Phòng Đào tạo Sau đại học - Nghiên cứu Khoa học, Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội đã tạo mọi điều kiện tốt nhất để tôi hoàn thành khóa học này. Đồng thời, tôi cũng xin cảm ơn gia đình, bạn bè, những người luôn khuyến khích và giúp đỡ tôi trong mọi hoàn cảnh khó khăn. Tôi xin cảm ơn cơ quan và các đồng nghiệp đã hết sức tạo điều kiện cho tôi trong suốt quá trình học tập và làm luận văn này. Hà Nội, ngày 10 tháng 04 năm 2011 Học viên Nguyễn Thị Huế
iii LỜI CAM ĐOAN Tôi xin cam đoan những kiến thức trình bày trong luận văn này là do tôi tìm hiểu, nghiên cứu và trình bày lại theo cách hiểu của tôi. Trong quá trình làm luận văn tôi có tham khảo các tài liệu có liên quan và đã ghi rõ nguồn tài liệu tham khảo đó. Phần lớn những kiến thức tôi trình bày trong luận văn này chưa được trình bày hoàn chỉnh trong bất cứ tài liệu nào. Hà Nội, ngày 10 tháng 04 năm 2011 Học viên Nguyễn Thị Huế
iv MỤC LỤC MỞ ĐẦU ................................................................................................................ 1 Chương 1................................................................................................................. 3 TỔNG QUAN VỀ KHAI PHÁ TRI THỨC VÀ KHAI PHÁ DỮ LIỆU .................. 3 1.1. Giới thiệu chung ........................................................................................... 3 1.2. Khai phá tri thức và quá trình khai phá tri thức ............................................. 3 1.2.1. Khai phá tri thức .................................................................................... 3 1.2.2. Quá trình khai phá tri thức ..................................................................... 4 1.3. Khai phá dữ liệu ........................................................................................... 5 1.3.1. Khai phá dữ liệu ..................................................................................... 5 1.3.2. Mục tiêu của khai phá dữ liệu ................................................................ 6 1.3.3. Quá trình khai phá dữ liệu ...................................................................... 6 1.3.4. Các hướng tiếp cận cơ bản và kỹ thuật áp dụng trong khai phá dữ liệu .. 7 1.3.5. Thách thức – khó khăn trong khai phá tri thức và khai phá dữ liệu ....... 13 1.3.6. Ứng dụng của khai phá dữ liệu ............................................................. 13 1.3.7. Kết luận ............................................................................................... 14 Chương 2. PHÂN CỤM DỮ LIỆU VÀ CÁC THUẬT TOÁN TRONG ............... 15 PHÂN CỤM DỮ LIỆU ......................................................................................... 15 2.1. Giới thiệu.................................................................................................... 15 2.2. Các ứng dụng của phân cụm ....................................................................... 16 2.3. Các yêu cầu về thuật toán phân cụm dữ liệu................................................ 17 2.4. Các kiểu dữ liệu trong phân cụm ................................................................. 18 2.5. Phép đo độ tương tự và khoảng cách đối với các kiểu dữ liệu ..................... 21 2.6. Các hướng tiếp cận của bài toán phân cụm dữ liệu ...................................... 28 2.6.1. Phương pháp phân hoạch (Partitioning Methods) ........................... 28 2.6.2. Phương pháp phân cấp (Hierarchical Methods) .............................. 36 2.6.3. Phương pháp dựa trên mật độ (Density-Based Methods) ................ 44 2.6.4. Phương pháp dựa trên lưới (Gird-Based Methods).......................... 51 2.6.5. Kết luận .......................................................................................... 56 Chương 3: ỨNG DỤNG ........................................................................................ 58 KẾT LUẬN ........................................................................................................... 65 TÀI LIỆU THAM KHẢO ..................................................................................... 66 PHỤ LỤC.............................................................................................................. 68
v DANH MỤC CÁC KÝ HIỆU, TỪ VIẾT TẮT Từ hoặc cụm từ Từ viết tắt Từ tiếng Anh Cơ sở dữ liệu CSDL DataBase Khai phá tri thức trong cơ sở dữ liệu KDD Knowledge Discovery in Databases Khai phá dữ liệu KPDL Data Mining Phân cụm dữ liệu PCDL Data Clustering Khai phá tri thức KPTT Knowledge Discovery
vi DANH MỤC HÌNH VẼ Hình 1.2: Quá trình khai phá tri thức ..................................................................... 4 Hình 1.3: Qúa trình khai phá dữ liệu ....................................................................... 7 Hình 2.1: Mô hình về phân cụm dựa trên tiêu chuẩn thu nhập và số nợ................. 15 Hình 2.2: Khoảng cách Euclidean ........................................................................ 24 Hình 2.3: Bảng tham số ......................................................................................... 26 Hình 2.4: Ví dụ quá trình phân hoạch với k=3 ...................................................... 30 Hình 2.6: Ví dụ về một số hình dạng cụm dữ liệu được khám phá bởi K-means ..... 32 Hình 2.7: Các chiến lược phân cụm phân cấp ....................................................... 37 Hình 2.8: Ví dụ về kết quả phân cụm bằng thuật toán BIRCH. .............................. 39 Hình 2.9. Khái quát thuật toán CURE ................................................................... 41 Hình 2.10. Các cụm dữ liệu được khám phá bởi CURE ........................................ 41 Hình 2.11. Ví dụ thực hiện phân cụm bằng thuật toán CURE ............................... 43 Hình 2.12: Các bước thuật toán CHAMELEON .................................................... 44 Hình 2.13: Hình dạng các cụm được khám phá bởi DBSCAN ............................... 45 Hình 2.14: Mật độ - đến được trực tiếp ................................................................. 46 Hình 2.15: Mật độ - đến được................................................................................ 47 Hình 2.16: Mật độ - liên thông .............................................................................. 47 Hình 2.17: Cụm và nhiễu. ...................................................................................... 48 Hình 2.18: Mô hình cấu trúc dữ liệu lưới .............................................................. 52 Hình 2.19: Mô hình thuật toán STING. .................................................................. 53 Hình 3.1: Kết quả phân cụm với Minpt = 3, Epxilon = 200000000 ...................... 60 Hình 3.2: Kết quả phân cụm trên dữ liệu thuộc tính và trên bản đồ ....................... 61 Hình 3.3: Màu của các cụm thể hiện trên bản đồ .................................................. 61 Hình 3.4: Giao diện chương trình Phân cụm dữ liệu bằng thuật toán DBSCAN .... 68 Hình 3.5: Giao diện chương trình sau khi thực hiên phân cụm .............................. 69 Hình 3.6: Kết quả phân cụm .................................................................................. 70
1 MỞ ĐẦU Sự phát triển của công nghệ thông tin và việc ứng dụng công nghệ thông tin trong các lĩnh vực của đời sống, kinh tế, xã hội trong nhiều năm qua cũng đồng nghĩa với lượng dữ liệu đã được các cơ quan thu thập và lưu trữ ngày một tích lũy nhiều lên. Hơn nữa, các công nghệ lưu trữ và phục hồi dữ liệu phát triển một cách nhanh chóng vì thế cơ sở dữ liệu ở các cơ quan, doanh nghiệp, đơn vị ngày càng nhiều thông tin tiềm ẩn phong phú và đa dạng. Mặt khác, trong môi trường cạnh tranh, người ta ngày càng cần có nhiều thông tin với tốc độ nhanh để trợ giúp việc ra quyết định và ngày càng có nhiều câu hỏi mang tính chất định tính cần phải trả lời dựa trên một khối lượng dữ liệu khổng lồ đã có. Với những lý do như vậy, các phương pháp quản trị và khai thác cơ sở dữ liệu truyền thống ngày càng không đáp ứng được thực tế đã làm phát triển một khuynh hướng kỹ thuật mới đó là Kỹ thuật khai phá tri thức và khai phá dữ liệu (KDD - Knowledge Discovery and Data Mining). Khai phá tri thức trong cơ sở dữ liệu có thể được coi như quá trình tìm tri thức có ích, cần thiết, tiềm ẩn và chưa được biết trước trong cơ sở dữ liệu lớn (discovery of interesting, implicit, and previously unknown knowledge from large databases)[5] Kỹ thuật khai phá tri thức và khai phá dữ liệu đã và đang được nghiên cứu, ứng dụng trong nhiều lĩnh vực khác nhau ở các nước trên thế giới, tại Việt Nam kỹ thuật này tương đối còn mới mẻ tuy nhiên cũng đang được nghiên cứu và dần đưa vào ứng dụng trong những năm gần đây. Những vấn đề được quan tâm là phân lớp nhận dạng mẫu, luật kết hợp, phân cụm dữ liệu, phần tử dị biệt,… Phân cụm cơ sở dữ liệu là một trong những phương pháp quan trọng trong quá trình tìm kiếm tri thức. Phân cụm là phương pháp học từ quan sát (learning from obversation) hay còn gọi là học không thầy (unupervised learning or automatic classfication) trong trí tuệ nhân tạo. Phân cụm đặc biệt hiệu quả khi ta không biết về thông tin của các cụm, hoặc khi ta quan tâm tới những thuộc tính của cụm mà chưa biết hoặc biết rất ít về những thông tin đó. Phân cụm được coi như một công cụ độc lập để xem xét phân bố dữ liệu, làm bước tiền xử lý cho các thuật toán khác. Việc phân cụm dữ liệu có rất nhiều ứng dụng như trong tiếp thị, sử dụng đất, bảo hiểm, hoạch định thành phố … Hiện nay, phân cụm dữ liệu là một hướng được nghiên cứu rất nhiều trong Tin học. Chính vì lý do đó mà em chọn đề tài “Nghiên cứu các kỹ thuật phân cụm dữ liệu và Ứng dụng” là hướng nghiên cứu chính cho luận văn của mình.
2 Nội dung chính của luận văn được trình bày trong 3 chương: Chương 1: Tổng quan về khai phá tri thức và khai phá dữ liệu. Trong chương này trình bày tổng quan về khai phá tri thức, khai phá dữ liệu; qui trình khai phá tri thức, khai phá dữ liệu; … Chương 2: Phân cụm và các kỹ thuật phân cụm. Trong chương này trình bày tổng quan về phân cụm dữ liệu, một số phương pháp phân cụm dữ liệu dữ liệu phổ biến như phân cụm phân hoạch, phân cụm phân cấp, phân cụm dựa trên mật độ, phân cụm dựa trên lưới; trình bày một số giải thuật điển hình của mỗi phương pháp phân cụm; … Chương 3: Ứng dụng, triển khai bài toán với giải thuật DBSCAN Phần kết luận trình bày tóm tắt về các nội dung thực hiện trong luận văn, đồng thời đưa ra các vấn đề nghiên cứu tiếp cho tương lai. Phần phụ lục trình bày một số modul chương trình cài đặt bằng thuật toán DBSCAN. Do thời gian nghiên cứu và trình độ có hạn, luận văn không tránh khỏi những hạn chế và thiếu sót. Em rất mong nhận được sự chỉ bảo, đóng góp ý kiến của các thầy thầy/ cô giáo cũng như bạn bè và đồng nghiệp. Em xin chân thành cảm ơn!
3 Chương 1. TỔNG QUAN VỀ KHAI PHÁ TRI THỨC VÀ KHAI PHÁ DỮ LIỆU 1.1. Giới thiệu chung Cách mạng khoa học kỹ thuật tạo ra bước nhảy vọt trong tất cả các lĩnh vực của đời sống kinh tế, xã hội, … Một thành công không thể không kể đến của cuộc cách mạng này là sự bùng nổ thông tin, khiến cho khối lượng thông tin mà con người thu thập và lưu trữ ngày một khổng lồ, kích thước của CSDL tăng một cách nhanh chóng. Trong những CSDL đó tiềm ẩn nhiều rất nhiều tri thức mà con người chưa khám phá ra được. Đứng trước núi dữ liệu khổng lồ thu thập được, việc khám phá tri thức và thông tin trở nên rất khó khăn. Chính vì lý do đó nhu cầu tìm kiếm tri thức trong khối CSDL đã nảy sinh, nhu cầu này ngày một cấp thiết và dẫn tới sự hình thành của một lĩnh vực mới – lĩnh vực khai phá dữ liệu (Data Mining) hay khai phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in databases - KDD). Khai phá tri thức trong cơ sở dữ liệu có thể được coi như quá trình tìm tri thức có ích, cần thiết, tiềm ẩn và chưa được biết trước trong cơ sở dữ liệu lớn (discovery of interesting, implicit, and previously unknown knowledge from large databases) Tuy mới ra đời nhưng khai phá tri thức và khai phá dữ liệu đã và đang được nghiên cứu, ứng dụng trong nhiều lĩnh vực khác nhau ở các n ước trên thế giới, tại Việt Nam kỹ thuật này tương đối còn mới mẻ tuy nhiên cũng đang được nghiên cứu và dần đưa vào ứng dụng trong những năm gần đây. Những vấn đề được quan tâm là phân lớp nhận dạng mẫu, luật kết hợp, phân cụm dữ liệu, phần tử dị biệt,… 1.2. Khai phá tri thức và quá trình khai phá tri thức 1.2.1. Khai phá tri thức Khai phá hay phát hiện tri thức trong các cơ sở dữ liệu là một quy trình nhận biết các mẫu hoặc các mô hình trong dữ liệu với các tính năng: Phân tích, tổng hợp, hợp thức, khả ích, và có thể hiểu được. Còn khám phá dữ liệu là một bước trong qui trình khám phá tri thức gồm có các thuật toán khai thác dữ liệu chuyên dùng dưới một số qui định về hiệu quả tính toán chấp nhận được để tìm ra các mẫu hoặc các
4 mô hình trong dữ liệu. Nói một cách khác, mục đích của phát hiện tri thức và khai phá dữ liệu chính là tìm ra các mẫu và/hoặc các mô hình đang tồn tại trong các cơ sở dữ liệu nhưng nhưng vẫn còn bị che khuất bởi hàng núi dữ liệu. 1.2.2. Quá trình khai phá tri thức Việc khai phá tri thức thông thường có thể mô tả bằng sơ đồ các quy trình sau [4]: Hình 1.2: Quá trình khai phá tri thức Trong đó, mỗi bước là một quy trình có vai trò riêng và nhiệm vụ khác nhau, bao gồm: Bước thứ nhất: tìm hiểu lĩnh vực ứng dụng và hình thành bài toán, bước này sẽ quyết định cho việc rút ra được các tri thức hữu ích và cho phép chọn các phương pháp khai phá dữ liệu thích hợp với mục đích ứng dụng và bản chất của dữ liệu. Bước thứ hai: thu thập và xử lý dữ liệu thô, còn được gọi là tiền xử lý dữ liệu nhằm loại bỏ nhiễu, xử lý việc thiếu dữ liệu, biến đổi dữ liệu và rút gọn dữ liệu nếu cần thiết, bước này thường chiếm nhiều thời gian nhất trong toàn bộ quy trình khai phá tri thức. Bước thứ ba: khai phá dữ liệu, hay nói cách khác là trích ra các mẫu hoặc/và các mô hình ẩn dưới các dữ liệu.
5 Bước thứ tư: hiểu tri thức đã tìm được, đặc biệt là làm sáng tỏ các mô tả và dự đoán. Các bước trên có thể lặp đi lặp lại một số lần, kết quả thu được có thể được lấy trung bình trên tất cả các lần thực hiện. Bước thứ năm: sử dụng tri thức đã được khám phá vào thực tế, các tri thức phát hiện được tích hợp chặt chẽ trong hệ thống. Tuy nhiên để sử dụng được các tri thức đó đôi khi cần đến các chuyên gia trong các lĩnh vực quan tâm vì tri thức rút ra có thể chỉ mang tính chất hỗ trợ quyết định hoặc cũng có thể được sử dụng cho một quá trình khai phá tri thức khác. Mặc dù được tóm tắt thành năm bước như trên, nhưng thực chất quá trình xây dựng và thực hiện việc khám phá tri thức không chỉ phải tuân theo các bước cố định mà các quá trình này còn có thể được lặp đi lặp lại ở một hoặc một số giai đoạn, lần sau sẽ hoàn thiện hơn lần trước và giai đoạn sau dựa vào kết quả của giai đoạn trước và cứ tiếp tục như thế sẽ làm cho quá trình khai phá và tìm kiếm dữ liệu ngày càng hoàn thiện hơn. 1.3. Khai phá dữ liệu 1.3.1. Khai phá dữ liệu Khai phá dữ liệu là một giai đoạn quan trọng trong quá trình KPTT. Về bản chất nó là giai đoạn duy nhất tìm ra được thông tin mới. Việc khai phá dữ liệu còn được coi như là việc khai phá tri thức từ dữ liệu (knowlegde mining from databases), trích lọc tri thức (knowlegde extraction), phân tích dữ liệu - mẫu (data- partent analysis), khảo cứu dữ liệu (data archaeology), đào xới, nạo vét dữ liệu (data dredging). Khai phá dữ liệu (Data Mining) được định nghĩa là quá trình trích lọc các thông tin có giá trị ẩn trong lượng lớn dữ liệu được lưu trữ trong các CSDL hoặc các kho dữ liệu,… Khai phá dữ liệu cũng còn được coi là một quá trình tìm kiếm, khám phá ở nhiều góc độ để tìm ra các mối tương quan, các mối liên hệ dưới nhiều góc độ khác nhau nhằm tìm ra các mẫu hay các mô hình tồn tại bên trong cơ sở dữ liệu đang bị che khuất. Để trích rút các mẫu, mô hình tiềm ẩn có tính “tri thức” ta phải tìm và áp dụng các phương pháp, kỹ thuật khai phá sao cho các kỹ thuật và
6 phương pháp này phải phù hợp với tính chất, đặc trưng của dữ liệu và mục đích sử dụng. Tuy khai phá dữ liệu chỉ là một bước trong quá trình khám phá tri thức nhưng nó lại là bước tiên quyết, quan trọng và ảnh hưởng đến toàn bộ quá trình. Tóm lại, khai phá dữ liệu là một quá trình tìm kiếm thông tin “tri thức” tiềm ẩn trong cơ sở dữ liệu lớn, khổng lồ. Vì thế, có thể nói rằng hai thuật ngữ khám phá tri thức và khai phá dữ liệu là tương đương nếu nói ở khía cạnh tổng quan, còn nếu xét ở một góc độ chi tiết thì khai phá dữ liệu là một giai đoạn có vai trò quan trọng trong quá trình khám phá tri thức [3][4][9]. 1.3.2. Mục tiêu của khai phá dữ liệu Qua những nội dung đã trình bày ở trên, ta có thể hiểu một cách sơ lược rằng khai phá dữ liệu là quá trình tìm kiếm thông tin hữu ích, tiềm ẩn và mang tính dự báo trong các cơ sở dữ liệu lớn. Việc khai phá dữ liệu nhằm các mục đích chính như sau: - Khai thác những thông tin tiềm ẩn mang tính dự đoán từ những cơ sở dữ liệu lớn dựa trên các công cụ khai phá dữ liệu nhằm dự đoán những xu hướng trong tương lai nhằm giúp các đối tượng cần tri thức khai phá như: các tổ chức, doanh nghiệp, nhà nghiên cứu, …. để hỗ trợ việc đưa ra những quyết định kịp thời, được định hướng trên những tri thức được khám phá mang lại; - Thực hiện phân tích xử lý, tính toán dữ liệu một cách tự động cho mỗi quá trình xử lý dữ liệu để tìm ra tri thức. 1.3.3. Quá trình khai phá dữ liệu KPDL là một giai đoạn quan trọng trong quá trình KPTT. Về bản chất, nó là giai đoạn duy nhất tìm ra được thông tin mới, thông tin tiềm ẩn có trong CSDL chủ yếu phục vụ cho mô tả và dự đoán. Dự đoán là thực hiện việc suy luận trên dữ liệu để đưa ra các dự báo nhằm phân tích tập dữ liệu huấn luyện và tạo ra một mô hình cho phép dự đoán các mẫu, mô hình mới chưa biết. Mô tả dữ là tổng kết hoặc diễn tả những đặc điểm chung của những thuộc tính dữ liệu trong kho dữ liệu mà con người có thể hiểu được. Quá trình KPDL bao gồm các bước như trong hình sau:
7 Hình 1.3: Qúa trình khai phá dữ liệu  Xác định nhiệm vụ: Xác định chính xác các vấn đề cần giải quyết.  Xác định các dữ liệu liên quan: Dùng để xây dựng giải pháp.  Thu thập và tiền xử lý dữ liệu: Thu thập các dữ liệu liên quan và tiền xử lý chúng sao cho thuật toán KPDL có thể hiểu được. Đây là một quá trình rất khó khăn, có thể gặp phải rất nhiều các vướng mắc như: dữ liệu phải được sao ra nhiều bản (nếu được chiết xuất vào các tệp), quản lý tập các dữ liệu, phải lặp đi lặp lại nhiều lần toàn bộ quá trình (nếu mô hình dữ liệu thay đổi), v.v..  Thuật toán khai phá dữ liệu: Lựa chọn thuật toán KPDL và thực hiện việc PKDL để tìm được các mẫu có ý nghĩa, các mẫu này được biểu diễn dưới dạng luật kết hợp, cây quyết định... tương ứng với ý nghĩa của nó. 1.3.4. Các hướng tiếp cận cơ bản và kỹ thuật áp dụng trong khai phá dữ liệu Vấn đề khai phá dữ liệu có thể được phân chia theo lớp các hướng tiếp cận chính sau: 1.3.4.1. Phân lớp và dự đoán Hướng tiếp cận này làm nhiệm vụ đưa ra các dự đoán dựa vào các suy diễn trên dữ liệu hiện thời. Kỹ thuật này gồm có: phân lớp (classification), hồi quy (regression)... Là quá trình xếp một đối tượng vào một trong những lớp đã biết trước (ví dụ: phân lớp các bệnh nhân theo dữ liệu hồ sơ bệnh án, phân lớp vùng địa lý theo dữ liệu thời tiết...). Đối với hướng tiếp cận này thường sử dụng một số kỹ
8 thuật của học máy như cây quyết định (decision tree), mạng nơron nhân tạo (neural network),... 1.3.4.2. Phân cụm dữ liệu Mục tiêu của phương pháp phân cụm dữ liệu là quá trình nhóm các điểm dữ liệu trong cơ sở dữ liệu thành các cụm sao cho những điểm dữ liệu trong cùng một cụm có độ tương đồng lớn và những điểm không cùng một cụm có sự tương đồng là rất nhỏ. Điểm mạnh của phân cụm dữ liệu là đưa ra được những cấu trúc có ích hoặc những cụm các đối tượng tìm thấy trực tiếp từ dữ liệu mà không cần bất kì một tri thức cơ sở nào. Giống như cách tiếp cận học máy, phân cụm dữ liệu được hiểu như là phương pháp “học không có thầy” (unsupervised learning). 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 (learning by observation), trong khi phân lớp dữ liệu là học bằng ví dụ (learning by example). Trong phương pháp này sẽ không thể biết kết quả các cụm thu được sẽ như thế nào khi bắt đầu quá trình. Vì vậy, cần có một chuyên gia để đánh giá các cụm thu được. Phân cụm dữ liệu được sử dụng nhiều trong các ứng dụng về phân đoạn thị trường, phân đoạn khách hàng, nhận dạng mẫu, phân loại trang Web… 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. 1.3.4.3. Phân lớp dữ liệu và hồi qui Mục tiêu của phương pháp phân lớp dữ liệu là dự đoán nhãn lớp cho các mẫu dữ liệu. Quá trình phân lớp dữ liệu thường gồm 2 bước: xây dựng mô hình và sử dụng mô hình: - Bước 1: một mô hình sẽ được xây dựng dựa trên việc phân tích các mẫu dữ liệu sẵn có. Mỗi mẫu tương ứng với một lớp, được quyết định bởi một thuộc tính gọi là thuộc tính lớp. Các mẫu dữ liệu này còn được gọi là tập dữ liệu huấn luyện (training data set). Các nhãn lớp của tập dữ liệu huấn luyện đều phải được xác định trước khi xây dựng mô hình, vì vậy phương pháp này còn
9 được gọi là học có thầy (supervised learning) khác với phân cụm dữ liệu là học không có thầy (unsupervised learning). - Bước 2: sử dụng mô hình để phân lớp dữ liệu. Trước hết phải tính độ chính xác của mô hình. Nếu độ chính xác là chấp nhận được, mô hình sẽ được sử dụng để dự đoán nhãn lớp cho các mẫu dữ liệu khác trong tương lai. Phương pháp hồi qui khác với phân lớp dữ liệu ở chỗ, hồi qui dùng để dự đoán về các giá trị liên tục còn phân lớp dữ liệu thì chỉ dùng để dự đoán về các giá trị rời rạc. 1.3.4.4. Luật kết hợp Có rất nhiều kiểu luật có thể được phát hiện từ cơ sở dữ liệu nói chung. Ví dụ như luật đặc trưng, luật biệt số, luật kết hợp, luật về sự lệch hướng và sự phát triển. Phương pháp phát hiện luật kết hợp không gian cũng là một phương pháp quan trọng trong khám phá tri thức. Phương pháp phát hiện luật kết hợp đưa ra những luật về sự kết hợp giữa một hoặc nhiều thuộc tính đối với một hoặc nhiều thuộc tính khác. Hướng tiếp cận này được ứng dụng nhiều trong lĩnh vực kinh doanh, y học, tin sinh học, giáo dục, viễn thông, tài chính và thị trường chứng khoán,... Khái niệm về luật kết hợp được phát biểu diễn như sau: một luật có dạng X Y (c%) với X và Y là tập các thuộc tính với độ tin cậy là c% được coi là luật kết hợp nếu có ít nhất c% đối tượng trong cơ sở dữ liệu đang xét thoả mãn: nếu điều kiện X được thoả mãn thì điều kiện Y cũng thoả mãn. Ví dụ, luật sau là luật kết hợp: is_a(x, school)  close (x, park) (80%). Luật trên thể hiện là: 80% trường học gần với công viên. Như vậy, có rất nhiều kiểu thuộc tính có thể tạo thành những luật kết hợp. Điều này khiến cho trong nhiều trường hợp số luật kết hợp tìm được vượt quá nhu cầu. Để hạn chế số luật kết hợp tìm được, người ta sử dụng khái niệm hỗ trợ tối thiểu  (minimum support) và độ tin cậy tối thiểu  (minimum confidence). Hai tham số sẽ giúp loại bớt các luật tìm thấy và chỉ để lại những luật thực sự có ích cho người sử dụng: 1. Hỗ trợ tối thiểu
10 Trong cơ sở dữ liệu lớn, có thể có rất nhiều luật giữa các đối tượng nhưng phần lớn các luật đó chỉ có thể áp dụng vào một số nhỏ các đối tượng hoặc độ tin cậy của luật là rất thấp. Chính vì thế mà phần lớn các luật không có ích với người sử dụng. Ví dụ, người sử dụng có thể không quan tâm nhiều tới mối quan hệ giữa nhà ở và trường học nếu luật đó chỉ áp dụng cho 5% số nhà ở trong khi người ta muốn ít nhất luật đó cũng phải được áp dụng cho trên 50% các ngôi nhà. Do đó chúng ta có thể lọc bỏ những luật kết hợp mà chỉ có thể áp dụng cho % đối tượng trong cơ sở dữ liệu. 2. Độ tin cậy tối thiểu Nếu một luật được đưa ra với mức độ tin cậy (độ tin cậy là tỉ lệ số đối tượng dữ liệu thoả mãn X và thoả mãn Y so với tổng số các đối tượng thoả mãn X) thấp thì cũng không có ý nghĩa ứng dụng. Ví dụ như luật: số người bị bệnh tim do ăn cá biển chỉ đúng 1% thì gần như không có ý nghĩa trong y học khi chuẩn đoán nguyên nhân bị bệnh tim của một bệnh nhân. Do đó, chúng ta sẽ loại bỏ những luật có độ tin cậy thấp mà chỉ giữ lại luật có độ tin cậy cao tỷ lệ đúng tối thiểu %. 1.3.4.5. Phân tích chuỗi theo thời gian Cũng tương tự như khai phá dữ liệu bằng luật kết hợp nhưng có thêm tính thứ tự và tính thời gian. Một luật mô tả mẫu tuần tự có dạng tiêu biểu X -> Y, phản ánh sự xuất hiện của biến cố X sẽ dẫn đến việc xuất hiện biến cố Y. 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 bởi chúng có tính dự báo cao. 1.3.4.6. Khai phá dữ liệu sử dụng mạng Neural Mạng Neural là một phương pháp khai phá dữ liệu phát triển dựa trên cấu trúc toán học với khả năng học trên mô hình hệ thần kinh con người. Mạng Neural có thể đưa ra ý nghĩa các dữ liệu phức tạp hoặc không chính xác và có thể được sử dụng để chiết suất các mẫu và phát hiện xu hướng quá phức tạp mà con người cũng như các kỹ thuật máy tính khác không thể phát hiện được. Một trong những ưu điểm của mạng Neural là khả năng tạo ra các mô hình dự đoán do độ chính xác cao, có thể áp dụng cho nhiều các bài toán khác nhau, đáp ứng được các nhiệm vụ đặt ra của khai phá dữ liệu như: phân lớp, phân nhóm, mô hình hoá, dự báo…
11 Mẫu chiết suất bằng mạng Neural được thể hiện bằng một trong những nút đầu của mạng. Mạng Neural sử dụng các hàm số chứ không sử dụng các hàm biểu tượng để tính mức tích cực của các nút đầu ra và cập nhật các trọng số của nó. Đặc điểm của mạng Neural là không cần gia công dữ liệu nhiều, trước khi bắt đầu quá trình học như các kỹ thuật khác. Tuy nhiên, để có thể sử dụng mạng Neural có hiệu quả cần phải xác định các yếu tố khi thiết kế mạng như: - Mô hình mạng là gì? - Mạng cần bao nhiêu nút? - Số lớp ẩn sử dụng cho mạng là như thế nào? - Khi nào thì việc học dừng? Ngoài ra còn có nhiều bước quan trọng cần phải làm để tiền xử lý dữ liệu trước khi đưa vào mạng Neural để mạng có thể hiểu được. Mạng Neural được đóng gói với những thông tin trợ giúp của các chuyên gia đáng tin cậy và được họ đảm bảo các mô hình này làm việt tốt. Sau khi học, mạn g có thể được coi là một chuyên gia trong lĩnh vực thông tin mà nó vừa được học. 1.3.4.7. Khai phá dữ liệu sử dụng thuật giải di truyền Đây là phương pháp không chỉ thực hiện phát hiện tri thức mà còn phục vụ rất nhiều bài toán khác. Tư tưởng của thuật toán là áp dụng quy luật của sự chọn lọc tự nhiên. Người ta mô phỏng tập dữ liệu ban đầu bằng ký tự nhị phân và gọi là những quần thể xuất phát. Bằng các thao tác lai ghép, đột biến nhằm biến đổi quần thể gene ban đầu và loại đi một số gene, làm cho số lượng gene trong quần thể là không thay đổi. Một hàm thích nghi được xây dựng để xác định mức độ thích nghi ngày càng cao. Về mặt lý thuyết giải thuật di truyền cho lời giải tối ưu toàn cục (khác với phương pháp mạng Neural). Tuy nhiên, người ta cũng hạn chế lời giải với một mức độ thích nghi nào đó để hạn chế số lượng các bước xây dựng quần thể. Nói theo nghĩa rộng, giải thuật di truyền mô phỏng lại hệ thống tiến hoá trong tự nhiên, chính xác hơn là giải thuật chỉ ra tập các cá thể được hình thành, được ước lượng và biến đổi như thế nào. Ví dụ như xác định xem làm thế nào để lựa chọn các cá thể tạo giống và lựa chọn các cá thể nào để loại bỏ.
12 Giải thuật di truyền là một giải thuật tối ưu hoá, được sử dụng rất rộng rãi trong việc tối ưu hoá các kỹ thuật khai phá dữ liệu trong đó có kỹ thuật mạng Neural. Sự kết hợp của nó với các giải thuật khai phá dữ liệu ở chỗ tối ưu hoá là cần thiết để xác định các giá trị tham số nào tạo ra các luật tốt nhất. 1.3.4.8. Khai phá dữ liệu sử dụng cây quyết định Phân lớp khai phá dữ liệu luật là cách tiếp cận quan trọng trong quá trình khai phá dữ liệu, với mục tiêu nhằm tạo ra một tập luật tương đối nhỏ có độ đúng đắn cao từ cơ sở dữ liệu lớn. Cây quyết định được cọi là phương pháp tiếp cận truyền thống cho phép phân lớp luật [10]. Cây quyết định đưa ra cách tiếp cận heuristic nhằm tìm kiếm các thuộc tính tốt nhất và dẫn đến kết quả cao nhất. Tuy nhiên, cây quyết định có một số hạn chế khi triển khai lựa chọn thuộc tính khi xây dựng cây. Hạn chế của cây quyết định là các trường hợp phân rã và tái tạo, vấn đề khi phân rã là khi cây quyết định cần phân chia dữ liệu nhiều lần để có thể nhận biết được toàn bộ dữ liệu mẫu. Vấn đề khi tái tạo là một cây con cần được xây dựng lại nhiều lần làm cho cây quyết định có độ sâu quá lớn và khó hiểu. Cây quyết định là một mô tả tri thức dạng đơn giản nhằm phân các đối tượng dữ liệu thành một số lớp nhất định. Các nút của cây được gán nhãn là tên của các thuộc tính, các cạnh được gán các giá trị có thể của các thuộc tính, các lá mô tả các lớp khác nhau. Các đối tượng được phân lớp theo các đường đi trên cây, qua các cạnh tương ứng với giá trị của thuộc tính của đối tượng tới lá. Quá trình xây dựng cây quyết định là quá trình phát hiện ra các luật phân chia dữ liệu đã cho thành các lớp đã được định nghĩa. Trong thực tế, tập các cây quyết định có thể có đối với bài toán này rất lớn và rất khó có thể duyệt hết một cách tường tận. Có nhiều phương pháp xây dựng cây quyết định khi khai phá dữ liệu, đó l à các phương pháp sử dụng các thuật toán CLS, ID3, C4.5,… và một phương pháp tương đối tiên tiến hiện nay và đang là tâm điểm được nghiên cứu là phương pháp xây dựng cây quyết định dựa trên phụ thuộc hàm.
13 1.3.5. Thách thức – khó khăn trong khai phá tri thức và khai phá dữ liệu KPTT và KPDL liên quan đến nhiều ngành, nhiều lĩnh vực trong thực tế, vì vậy các thách thức và khó khăn ngày càng nhiều, càng lớn. Một số các thách thức và khó khăn cần được quan tâm: Các cơ sở dữ liệu lớn, các tập dữ liệu cần xử lý có kích thước rất lớn, trong thực tế, kích thước của các tập dữ liệu thường ở mức tera-byte (hàng ngàn giga- byte). - Mức độ nhiễu cao hoặc dữ liệu bị thiếu - Số chiều lớn - Thay đổi dữ liệu và tri thức có thể làm cho các mẫu đã phát hiện không còn phù hợp - Quan hệ giữa các trường phức tạp 1.3.6. Ứng dụng của khai phá dữ liệu Các kỹ thuật KDD có thể được áp dụng vào trong nhiều lĩnh vực, điển hình:  Thông tin thương mại: o Phân tích dữ liệu tiếp thị và bán hàng và thị trường; o Phân tích vốn đầu tư; o Quyết định cho vay vốn; o Phát hiện gian lận; o v.v..  Thông tin sản xuất: o Điều khiển và lập lịch; o Hệ thống quản lý; o Quản trị mạng; o Phân tích kết quả thí nghiệm; o V.v ...  Thông tin khoa học: o Dự báo thời tiết; o CSDL sinh học;
14 o Khoa học địa lý: tìm động đất; v.v..  Thông tin cá nhân  V.v… 1.3.7. Kết luận Khai phá dữ liệu là lĩnh vực đã và đang trở thành một trong những hướng nghiên cứu thu hút được sự quan tâm của nhiều chuyên gia về CNTT trên thế giới và được ứng dụng trong nhiều lĩnh vực khác nhau. Tại Việt Nam kỹ thuật này còn tương đối mới mẻ tuy nhiên cũng đang được nghiên cứu và dần đưa vào ứng dụng. Trong những năm gần đây, rất nhiều các phương pháp và thuật toán mới liên tục được công bố. Điều này chứng tỏ những ưu thế, lợi ích và khả năng ứng dụng thực tế to lớn của khai phá dữ liệu. Trong chương này đã trình bày một cách tổng quan về khai phá tri thức và khai phá dữ liệu.