Tài liệu Các thuật toán phân cụm dữ liệu và ứng dụng trong phân loại Protein

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG PHẠM THỊ THU CÁC THUẬT TOÁN PHÂN CỤM DỮ DIỆU VÀ ỨNG DỤNG TRONG PHÂN LOẠI PROTEIN LUẬN VĂN THAC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên – 2015 Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG PHẠM THỊ THU CÁC THUẬT TOÁN PHÂN CỤM DỮ DIỆU VÀ ỨNG DỤNG TRONG PHÂN LOẠI PROTEIN Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 01 Ngƣời hƣớng dẫn khoa học PGS.TS. Đoàn Văn Ban Thái Nguyên - 2015 Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ i LỜI CẢM ƠN Để hoàn thành chƣơng trình cao học và viết luận văn này, tôi đã nhận đƣợc sự hƣớng dẫn, giúp đỡ và góp ý nhiệt tình của quý thầy cô trƣờng Đại học Công nghệ thông tin và Truyền thông. Đặc biệt là những thầy cô ở Viện công nghệ thông tin Hà Nội đã tận tình dạy bảo cho tôi suốt thời gian học tập tại trƣờng. Tôi xin gửi lời cảm ơn sâu sắc đến PGS.TS Đoàn Văn Ban đã dành nhiều thời gian và tâm huyết hƣớng dẫn tôi hoàn thành luận văn này. Mặc dù tôi đã có nhiều cố gắng hoàn thiện luận văn bằng tất cả năng lực của mình, tuy nhiên không thể tránh khỏi những thiếu sót, rất mong nhận đƣợc sự đóng góp quí báu của quí thầy cô và các bạn. Tôi xin chân thành cảm ơn! Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ ii LỜI CAM ĐOAN Tôi xin cam đoan tất cả các nội dung của luận văn này hoàn toàn đƣợc hình thành và phát triển từ quan điểm của chính cá nhân tôi, dƣới sự hƣớng dẫn chỉ bảo của PGS.TS Đoàn Văn Ban. Các số liệu kết quả có đƣợc trong luận văn tốt nghiệp là hoàn toàn trung thực. Học viên Phạm Thị Thu Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ iii BẢNG KÝ HIỆU CÁC CHỮ VIẾT TẮT Chữ viết tắt KDD CSDL Nghĩa tiếng anh Nghĩa tiếng việt Kownledge Discovery in Khám phá tri thức trong cơ sở dữ Database liệu Data base Cơ sở dữ liệu Khai phá dữ liệu KPDL Clustering Using Representatives Phân cụm dữ liệu sử dụng điểm đại diện Clustering Large Application Thuật toán phân cụm ứng dụng lớn Self-organizing Trees Cây tự tổ chức DesoxyriboNucleic Acid Phân tử nucleic acid mang thông tin di truyền mã hóa cho hoạt động sinh trƣởng và phát triển của các dạng sống RNA RiboNucleic Acid Là một trong hai loại axít nucleic, là cơ sở di truyền ở cấp độ phân tử. rRNA ribosome RNA Là ARN mã hóa và mang thông tin từ AND tRNA transfer RNA Là RNA vận chuyển mRNA messenger RNA RNA thông tin SCOP Structural Classification of Phân loại cấu trúc các protein Proteins CATH Class Architecture Topology Homologous superfamily Phân loại cấu trúc protein với CATH DDD Dali Domain Dictionary Từ điển miền Dali PDB Protein Data Bank Ngân hàng dữ liệu protein FSSP Families of Structurally Similar Proteins Dòng họ protein với cấu trúc tƣơng tự CURE CLARA SoT DNA Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ iv Trang Hình 1.1. Ví dụ phân cụm của tập dữ liệu vay nợ thành 3 cụm 6 Hình 1.2. Các chiến lƣợc phân cụm phân cấp 15 Hình 1.3. Một số hình dạng khám phá bởi phân cụm trên mật độ 16 độ Hình 1.4. Mô hình cấu trúc dữ liệu lƣới 18 Hình 2.1. Các thiết lập để xác định danh giới các cụm ban đầu 25 Hình 2.2. Tính toán trọng tâm của các cụm mới 26 Hình 2.3. Minh họa trực quan quá trình phân cụm 28 Hình 2.4. Phân cụm Chameleon 31 34 35 35 Hình 2.8. Nguyên lý chung của AntTree 37 Hình 2.9. Kiến trúc khác nhau giữa SOM và SoT 40 Hình 2.10. Phân việc từ cây treec cho treec 44 Hình 2.11. Tách subtreex khỏi cây treec và đƣa vào list 44 Hình 2.12. Tái liên kết subtreex vào treec 45 Hình 3.1. Thuyết trung tâm của sinh học phân tử 47 Hình 3.2. Cấu trúc DNA 48 Hình 3.3. Sự phát triển của cấu trúc dữ liệu protein 51 Hình 3.4. Dữ liệu đầu vào của thuật toán 57 Hình 3.5. Giao diện chọn bộ dữ liệu 65 old old Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ v Hình 3.6. Thông tin về bộ dữ liệu 66 Hình 3.7. Kết quả phân cụm với số tâm cụm bằng 10 67 Hình 3.8. Kết quả phân cụm bằng SoT với số tâm cụm bằng 10 67 Hình 3.9. Giao diện hiển thị 10 phân cụm trong thuật toán SoT 68 Hình 3.10. Chi tiết phân cụm thứ tám trong thuật toán SoT 68 Hình 3.11. Tập tin kết quả phân cụm clara 69 DANH MỤC BẢNG Bảng 3.1. Nguồn tài nguyên cho phân loại cấu trúc protein 52 Bảng 3. 2. Các cấp độ chính của CATH 53 Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ vi MỤC LỤC LỜI CẢM ƠN ......................................................................................................... i LỜI CAM ĐOAN .................................................................................................. ii BẢNG KÝ HIỆU CÁC CHỮ VIẾT TẮT ............................................................ iii ........................................................................................ iv MỞ ĐẦU ................................................................................................................ 1 CHƢƠNG 1. KHAI PHÁ DỮ LIỆU ..................................................................... 3 1.1. Khái niệm chung ......................................................................................... 3 1.2. Phân lớp dữ liệu .......................................................................................... 4 1.3. Phân cụm dữ liệu ......................................................................................... 5 1.3.1. Tổng quan về phân cụm dữ liệu ........................................................... 5 1.3.2. Các yêu cầu cơ bản đối với các kỹ thuật phân cụm dữ liệu ................. 9 1.3.3. Các kiểu dữ liệu trong phân cụm dữ liệu ............................................. 9 1.3.4. Độ đo trong phân cụm dữ liệu............................................................ 11 1.3.5. Các kỹ thuật tiếp cận với bài toán phân cụm ..................................... 13 1.4. Luật kết hợp .............................................................................................. 20 1.4.1. Một số khái niệm cơ sở ...................................................................... 20 ............................................. 21 ............................................................. 21 1.5. Một số ứng dụng của phân cụm dữ liệu .................................................... 22 1.5.1. Ứng dụng trong tin sinh học .............................................................. 22 1.5.2. Ứng dụng trong phân loại đối tƣợng văn bản .................................... 23 1.5.3. Ứng dụng trong phân đoạn ảnh, nhận dạng ....................................... 23 1.6. Kết luận chƣơng 1 ..................................................................................... 24 CHƢƠNG 2. CÁC THUẬT TOÁN PHÂN CỤM .............................................. 25 2.1. Thuật toán K-means .................................................................................. 25 2.2. Thuật toán CHAMELEON ....................................................................... 29 2.3. Thuật toán CLARA ................................................................................... 32 2.4. Thuật toán CURE ...................................................................................... 33 2.5. Thuật toán AntTree ................................................................................... 37 2.6. Thuật toán cây tự tổ chức SoT .................................................................. 39 2.7. Kết luận chƣơng 2 ..................................................................................... 46 CHƢƠNG 3. CHƢƠNG TRÌNH THỬ NGHIỆM .............................................. 47 Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ vii 3.1. Protein và các kỹ thuật phân loại Protein .................................................. 47 3.1.1. Thuyết trung tâm của sinh học phân tử .............................................. 47 3.1.2. Các kỹ thuật phân loại Protein ........................................................... 50 3.2. Cài đặt thử nghiệm thuật toán phân cụm dữ liệu trong phân loại Protein 55 3.2.1. Phát biểu bài toán ............................................................................... 55 3.2.2. Mô tả dữ liệu ...................................................................................... 56 3.2.3. Chuẩn bị dữ liệu ................................................................................. 57 3.2.4. Môi trƣờng cài đặt và thử nghiệm ...................................................... 61 3.3. Nhận xét, đánh giá chƣơng trình thử nghiệm............................................ 70 3.4. Kết luận chƣơng 3 ..................................................................................... 70 KẾT LUẬN VÀ HƢỚNG NGHIÊN CỨU ......................................................... 71 TÀI LIỆU THAM KHẢO .................................................................................... 72 Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 1 MỞ ĐẦU Trong những năm gần đây, cùng với sự phát triển vƣợt bậc của công nghệ thông tin, khả năng thu thập và lƣu trữ thông tin của các hệ thống thông tin không ngừng đƣợc nâng cao. Theo đó, lƣợng thông tin đƣợc lƣu trữ trên các thiết bị nhớ không ngừng tăng lên. Khai phá dữ liệu là quá trình khám phá các tri thức mới có ích ở dạng tiềm năng trong nguồn dữ liệu đã có. Quá trình khám phá tri thức là một chuỗi lặp gồm các bƣớc: làm sạch dữ liệu, tích hợp dữ liệu, chọn lựa dữ liệu, đánh giá mẫu, biểu diễn tri thức. Khai phá dữ liệu liên quan đến nhiều lĩnh vực khác nhau nhƣ: công nghệ cơ sở dữ liệu, lý thuyết thống kê, học máy, khoa học thông tin, trực quan hóa,... Vấn đề ứng dụng các kỹ thuật khai phá dữ liệu, phân cụm dữ liệu trong Tin sinh học, một lĩnh vực còn khá mới, đã ra đời, sử dụng các công nghệ của các ngành toán học ứng dụng, tin học, thống kê, khoa học máy tính, trí tuệ nhân tạo, hóa học, sinh học để giải quyết các vấn đề của sinh học. Việc tìm hiểu và nghiên cứu phân loại protein đã nổi lên nhƣ một hƣớng đi mới với những trải nghiệm hƣớng vào việc khám phá cấu trúc của các phân tử sinh học. Nghiên cứu và ứng dụng một cách hiệu quả các phƣơng pháp khai phá dữ liệu là vấn đề hấp dẫn, đã và đang thu hút sự quan tâm chẳng những của các nhà nghiên cứu, ứng dụng mà của cả các tổ chức, doanh nghiệp. Do đó, tôi đã chọn đề tài nghiên cứu “ Các thuật toán phân cụm dữ liệu và ứng dụng trong phân loại Protein” Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 2 Nội dung của đề tài gồm 3 chƣơng: Chƣơng 1. Khai phá dữ liệu: Chƣơng này trình bày tổng quan về khai phá dữ liệu và đi sâu tìm hiểu về phân cụm dữ liệu, các kỹ thuật phân cụm và một số ứng dụng của phân cụm dữ liệu. Chƣơng 2. Các thuật toán phân cụm dữ liệu: Trình bày về các thuật toán điển hình trong phân cụm dữ liệu là: K-Means, Chameleon, Clara, Cure, AntTree và SoT. Chƣơng 3. Chƣơng trình thử nghiệm: Để khẳng định cho khả năng và hiệu quả của một số thuật toán phân cụm dữ liệu đã trình bày ở chƣơng 2. Đó là thuật toán Clara và thuật toán SoT. Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 3 CHƢƠNG 1. KHAI PHÁ DỮ LIỆU 1.1. Khái niệm chung Cuối thập kỷ 80 của thế kỷ 20, sự phát triển rộng khắp của các CSDL đã tạo ra sự bùng nổ thông tin trên toàn cầu, vào thời gian này ngƣời ta bắt đầu đề cập đến khái niệm khủng hoảng trong việc phân tích dữ liệu tác nghiệp để cung cấp thông tin với yêu cầu chất lƣợng ngày càng cao cho ngƣời làm quyết định trong các tổ chức chính phủ, tài chính, thƣơng mại, khoa học, ... Lƣợng dữ liệu khổng lồ này thực sự là một nguồn tài nguyên có nhiều giá trị bởi thông tin là yếu tố then chốt phục vụ cho mọi hoạt động quản lý, kinh doanh, phát triển sản xuất và dịch vụ, ... nó giúp ngƣời điều hành và quản lý có những hiểu biết về môi trƣờng và tiến trình hoạt động của tổ chức mình trƣớc khi ra quyết định để tác động đến quá trình hoạt động nhằm đạt đƣợc các mục tiêu một cách hiệu quả và bền vững.[1] KPDL là một lĩnh vực mới đƣợc nghiên cứu, nhằm tự động khai thác thông tin, tri thức mới hữu ích, tiềm ẩn từ những CSDL lớn cho các đơn vị, tổ chức, doanh nghiệp, ... từ đó làm thúc đẩy khả năng sản xuất, kinh doanh, cạnh tranh cho các đơn vị, tổ chức này. Các kết quả nghiên cứu khoa học cùng những ứng dụng thành công trong KDD cho thấy KPDL 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 thời có ƣu thế hơn hẳn so với các công cụ tìm kiếm phân tích dữ liệu truyền thống. Các kỹ thuật chính đƣợc áp dụng trong lĩnh vực KPDL 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ê và tính toán hiệu năng cao, ... Nhƣ vậy, ta có thể khái quát hóa khái niệm KPDL là một quá trình tìm kiếm, phát hiện các tri thức mới, hữu ích, tiềm ẩn trong CSDL lớn. Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 4 KDD là mục tiêu chính của KPDL, do vậy hai khái niệm KPDL và KDD đƣợc các nhà khoa học trên hai lĩnh vự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ì KPDL là một bƣớc chính trong quá trình KDD. 1.2. Phân lớp dữ liệu Phân lớp dữ liệu là kỹ thuật dựa trên tập huấn luyện và những giá trị hay là nhãn của lớp trong một thuộc tính phân lớp và sử dụng nó trong việc phân lớp dữ liệu mới. Bên cạnh kỹ thuật phân lớp có một hình thức tƣơng tự là kỹ thuật tiên đoán, kỹ thuật tiên đoán khác với phân lớp ở chỗ phân lớp chỉ liên quan đến tiên đoán loại lớp của nhãn còn kĩ thuật tiên đoán mô hình những hàm đánh giá liên tục. Kỹ thuật phân lớp đƣợc tiến hành bao gồm 2 bƣớc: Xây dựng mô hình và sử dụng mô hình [1] + Xây dựng mô hình: Là mô tả một tập những lớp đƣợc định nghĩa trƣớc trong đó: mỗi bộ hoặc mẫu đƣợc gán thuộc về một lớp đƣợc định nghĩa trƣớc nhƣ là đƣợc xác định bởi thuộc tính nhãn lớp, tập hợp của những bộ đƣợc sử dụng trong việc sử dụng mô hình đƣợc gọi là tập huấn luyện. Mô hình đƣợc biểu diễn là những luật phân lớp, cây quyết định và những công thức toán học. + Sử dụng mô hình: Việc sử dụng mô hình phục vụ cho mục đích phân lớp dữ liệu trong tƣơng lai hoặc phân lớp cho những đối tƣợng chƣa biết đến. Trƣớc khi sử dụng mô hình ngƣời ta thƣờng phải đánh giá tính chính xác của mô hình, trong đó: nhãn đƣợc biết của mẫu kiểm tra đƣợc so sánh với kết quả phân lớp của mô hình, độ chính xác là phần trăm của tập hợp mẫu kiểm tra phân loại đúng bởi mô hình, tập kiểm tra là độc lập với tập huấn luyện. Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 5 Phân lớp là một hình thức học đƣợc giám sát tức là: tập dữ liệu huấn luyện (quan sát, thẩm định…) đi đôi với những với những nhãn chỉ định lớp quan sát những dữ liệu mới đƣợc phân lớp dựa trên tập huấn luyện. Ngƣợc lại với hình thức học đƣợc giám sát là hình thức học không đƣợc giám sát lúc đó nhãn lớp của tập dữ liệu huấn luyện là không đƣợc biết. 1.3. Phân cụm dữ liệu 1.3.1. Tổng quan về phân cụm dữ liệu Mục đích chính của phân cụm dữ liệu (PCDL) nhằm khám phá cấu trúc của mỗi dữ liệu để thành lập các nhóm dữ liệu từ tập dữ liệu lớn, theo đó nó 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 này nhằm khám phá và tìm kiếm các thông tin tiềm ẩn, hữu ích phục vụ cho việc ra quyết định. Ví dụ “Nhóm các khách hàng trong cơ sở dữ liệu (CSDL) ngân hàng có vốn các đầu tƣ vào bất động sản cao”,… Nhƣ vậy, PCDL là một phƣơng pháp xử lý thông tin quan trọng và phổ biển, nó nhằm khám phá mối liên hệ giữa các mẫu dữ liệu bằng cách tổ chức chúng thành các cụm. Ta có thể khái quát hóa khái niệm PCDL: PCDL là một kĩ thuật trong khai phá dữ liệu (KPDL), 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, quan trọng trong tập dữ liệu lớn từ đó cung cấp thông tin, tri thức hữu ích cho việc ra quyết định. [1] Nhƣ vậy, PCDL 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ự” với nhau và các phần tử trong các cụm khác nhau sẽ “phi tƣơng tự” với nhau. Số các cụm dữ liệu đƣợc phân ở đây có thể đƣợc xác định trƣớc theo kinh nghiệm hoặc có thể đƣợc tự động xác định của phƣơng pháp phân cụm. Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 6 Trong PCDL khái niệm hai hoặc nhiều đối tƣợng cùng đƣợc xếp vào một cụm nếu chúng có chung một định nghĩa về khái niệm hoặc chúng xấp xỉ với các khái niệm mô tả cho trƣớc. Trong học máy, PCDL đƣợc xem là vấn đề học không có giám sát, vì nó phải giải quyết vấn đề tìm một cấu trúc trong tập hợp dữ liệu chƣa biết trƣớc các thông tin về lớp hay các thông tin về tập huấn luyện. Trong nhiều trƣờng hợp, nếu phân lớp đƣợc xem là vấn đề học có giám sát thì PCDL là một bƣớc trong phân lớp dữ liệu, PCDL sẽ khởi tạo các lớp cho phân lớp bằng cách xác định các nhãn cho các nhóm dữ liệu. Trong KPDL, ngƣời ta có thể nghiên cứu các phƣơng pháp phân tích cụm có hiệu quả và hiệu suất cao trong CSDL lớn. Những mục tiêu trƣớc tiên của nghiên cứu là tập trung vào khả năng mở rộng của các phƣơng pháp phân cụm, tính hiệu quả của các phƣơng pháp phân cụm với các hình dạng phức tạp, những kĩ thuật cho phân cụm với nhiều kiểu dữ liệu có kích cỡ lớn và những phƣơng pháp cho PCDL tƣờng minh và những dữ liệu dạng số hỗn hợp trong CSDL lớn. PCDL đƣợc sử dụng rộng rãi trong nhiều ứng dụng, bao gồm nhận dạng mẫu, phân tích dữ liệu, xử lý ảnh, nghiên cứu thị trƣờng, ... Hình 1.1. Ví dụ phân cụm của tập dữ liệu vay nợ thành 3 cụm Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 7 Vấ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” do quá trình thu thập thiếu chính xác hoặc thiếu đầy đủ, vì 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 PCDL. Ở đây “nhiễu” có thể là các đối tƣợng dữ liệu không chính xác hoặc 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ủ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 là một trong những hƣớng nghiên cứu quan trọng trong PCDL, 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 khác trong CSDL tức là đố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, … Tóm lại, PCDL là một vấn đề khó vì ngƣời ta phải đi giải quyết các vấn đề con cơ bản nhƣ sau: - Biểu diễn dữ liệu. - 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à 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 thì đế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 Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 8 diễn cấu trúc các cụm dữ liệu khác nhau, với mỗi cách thức biểu diễn khác nhau sẽ có một thuật toán phân cụm phù hợp. PCDL đang là vấn đề mở và khó vì 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 đối tƣợng với dữ liệu hỗn hợp, đang ngày càng tăng trƣởng không ngừng trong các hệ quản trị dữ liệu, đây cũng là một trong những thách thức lớn trong lĩnh vực KPDL trong những thập kỷ tiếp theo và đặc biệt trong lĩnh vực KPDL bằng phƣơng pháp phân cụm dữ liệu. Phân cụm là chia dữ liệu thành các nhóm mà các đối tƣợng trong cùng một nhóm thì giống nhau theo một nghĩa nào đó và khác với các đối tƣợng trong các nhóm khác. Các phần tử tƣơng tự nhau đƣợc phân thành một cụm (cluster). Mỗi đối tƣợng đƣợc mô tả bởi một tập các độ đo hoặc bằng mối quan hệ với các đối tƣợng khác. Cũng có rất nhiều định nghĩa về cụm, nhƣng các định nghĩa sau đây đƣợc sử dụng nhiều nhất: - "Một cụm là một tập các đối tƣợng giống nhau và khác với các đối tƣợng không ở trong cụm đó". - "Một cụm là một tập các điểm trong không gian mà khoảng cách giữa hai điểm bất kì trong nó luôn nhỏ hơn khoảng cách giữa một điểm bất kì trong nó và một điểm ngoài". - "Các cụm có thể đƣợc mô tả nhƣ các miền liên thông trong không gian đa chiều chứa mật độ tƣơng đối cao các điểm, phân biệt giữa các miền bằng mật độ khá thấp của các điểm". Phân cụm có ý nghĩa rất quan trọng trong hoạt động của con ngƣời từ y tế, giáo dục, xử lý thông tin, nghiên cứu phân tích thị trƣờng,... Phân cụm đƣợc sử dụng rộng rãi trong nhiều ứng dụng, bao gồm nhận dạng mẫu, phân tích dữ liệu, xử lý ảnh, nghiên cứu thị trƣờng, phân loại trong tin sinh học,… Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 9 1.3.2. Các yêu cầu cơ bản đối với các kỹ thuật phân cụm dữ liệu Phân cụm là một thách thức trong lĩnh vực nghiên cứu ở chỗ những ứng dụng tiềm năng của chúng đƣợc đƣa ra ngay chính trong những yêu cầu đặc biệt của chúng, sau đây là một số yêu cầu cơ bản của phân cụm dữ liệu: - Có khả năng mở rộng - Khả năng thích nghi với các kiểu thuộc tính khác nhau - Khám phá các cụm với hình dạng bất kỳ - Tối thiểu lƣợng tri thức cần cho xác định các tham số đầu vào - Khả năng thích nghi với dữ liệu nhiễu - Ít nhạy cảm với thứ tự của các dữ liệu vào - Số chiều lớn - Phân cụm ràng buộc. - Dễ hiểu và dễ sử dụng 1.3.3. Các kiểu dữ liệu trong phân cụm dữ liệu Trong phân cụm, các đối tƣợng dữ liệu thƣờng đƣợc biểu diễn dƣới dạng các đặc tính hay còn gọi là thuộc tính (khái niệm “các kiểu dữ liệu” và “các kiểu thuộc tính dữ liệu” đƣợc xem là tƣơng đƣơng với nhau). Phân loại các kiểu thuộc tính khác nhau là 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. Có hai đặc trƣng để phân loại: kích thƣớc miền và hệ đo. Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 10 - Cho một cơ sở dữ liệu 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,...,xk); y = (yl, y2,..., yk); z = (zl, z2,..., 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; nhƣ vậy sẽ có các kiểu dữ liệu sau: * Loại kiểu dữ liệu dựa trên kích thƣớc miền:  Thuộc tính liên tục: 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ô số giá trị khác (ví dụ, các thuộc tính màu, nhiệt độ hoặc cƣờng độ âm thanh,...). Thuộc tính rời rạc: Nếu miền giá trị của nó là tập hữu hạn, đếm đƣợc (ví dụ, các thuộc tính số,...); trƣờng hợp đặc biệt của thuộc tính rời rạc là thuộc tính nhị phân mà miền giá trị chỉ có hai phần tử (ví dụ:Yes/No, True/False, On/Off...) * Loại kiểu dữ liệu dựa trên hệ đo:  Thuộc tính định danh: Là dạng thuộc tính khái quát hóa 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ử. 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ự: 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ì 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: Để đo các giá trị theo xấp xỉ tuyến tính, với thuộc tính khoảng 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ì có thể nói x cách y một khoảng xi - yi tƣơng ứng với thuộc tính thứ i.  Thuộc tính tỉ lệ: Là thuộc tính khoảng nhƣng đƣợc xác định một Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 11 cách tƣơng đối so với điểm mốc đầy ý nghĩa. Trong các thuộc tính 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, còn thuộc tính khoảng và thuộc tính tỉ lệ đƣợc gọi là thuộc tính số. Đặc biệt, còn có dữ liệu không gian là loại dữ liệu có thuộc tính số khái quát trong không gian nhiều chiều, dữ liệu không gian mô tả các thông tin liên quan đến không gian chứa đựng các đối tƣợng (ví dụ, thông tin về hình học, ...). Dữ liệu không gian có thể là dữ liệu liên tục hoặc rời rạc. 1.3.4. Độ đo trong phân cụm dữ liệu Khi các đặc tính của dữ liệu đƣợc xác định, phả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 của dữ liệu, thông thƣờng các hàm này hoặc là để tính độ tƣơng tự hoặc là tính độ phi tƣơng tự giữa các đối tƣợng dữ liệu. Giá trị của hàm tính độ đo tƣơng tự càng lớn thì sự giống nhau giữa các đối tƣợng càng lớn và ngƣợc lại còn hàm tính độ phi tƣơng tự tỉ lệ nghịch với hàm tính độ tƣơng tự. Độ tƣơng tự hoặc phi tƣơng tự có nhiều cách để xác định, chúng thƣờng đƣợc đo bằng khoảng cách giữa các đối tƣợng. Tất cả các cách đo độ tƣơng tự đều phụ thuộc vào kiểu thuộc tính mà ngƣời sử dụng phân tích [2] Tất cả các độ đo dƣới đây đƣợc xác định trong không gian metric. Một không gian metric là một tập trong đó có xác định 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 cơ sở dữ liệu D đề 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. Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/