Tài liệu Phân cụm dữ liệu và ứng dụng trong phân loại cấu trúc protein

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CNTT & TRUYỀN THÔNG TRẦN ĐỨC THUẬN PHÂN CỤM DỮ LIỆU VÀ ỨNG DỤNG TRONG PHÂN LOẠI CẤU TRÚC PROTEIN LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH THÁI NGUYÊN - 2012 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CNTT & TRUYỀN THÔNG TRẦN ĐỨC THUẬN PHÂN CỤM DỮ LIỆU VÀ ỨNG DỤNG TRONG PHÂN LOẠI CẤU TRÚC PROTEIN Chuyên ngành: Khoa học máy tính Mã số: 60.48.01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Người hướng dẫn khoa học: PGS.TS. ĐOÀN VĂN BAN THÁI NGUYÊN - 2012 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn i LỜI CAM ĐOAN Tôi xin cam đoan bản luận văn “Phân cụm dữ liệu và ứng dụng trong phân loại cấu trúc protein" là công trình nghiên cứu riêng của tôi. Các số liệu trong luận văn đƣợc sử dụng trung thực. Kết quả nghiên cứu đƣợc trình bày trong luận văn này chƣa từng đƣợc công bố tại bất kỳ công trình nào khác. Tôi cũng xin chân thành cảm ơn các thầy cô trong Viện Công nghệ Thông tin, các thầy cô trong Trƣờng Công Nghệ Thông Tin và Truyền thông Thái Nguyên, thầy giáo Trần Đăng Hƣng - Giảng viên Khoa Công nghệ thông tin và Trung tâm khoa học tính toán, Đại học Sƣ phạm Hà Nội, các bạn bè, đồng nghiệp tại Trung tâm Thông tin Công nghệ - Sở Khoa học Công nghệ Thái Nguyên, Cục Dự trữ Nhà nƣớc khu vực Bắc Thái đã giúp đỡ tôi rất nhiều trong quá trình học tập, sƣu tầm, tìm tòi tài liệu và trong công tác để tôi có thể hoàn thành bản luận văn này. Tôi xin bày tỏ lòng kính trọng, và biết ơn sâu sắc tới PGS.TS Đoàn Văn Ban, ngƣời đã trực tiếp hƣớng dẫn, giúp đỡ tôi trong suốt thời gian thực hiện luận văn này. Thái Nguyên, tháng 08 năm 2012 Học viên Trần Đức Thuận Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ii MỤC LỤC Lời cam đoan .......................................................................................................................... i Mục lục ..................................................................................................................................ii Danh mục bảng biểu .............................................................................................................. v Danh mục các hình ................................................................................................................ v Mở đầu ................................................................................................................................... 1 1. Lý do chọn đề tài. .............................................................................................................. 1 2. Mục tiêu nghiên cứu ...................................................................................................... 1 3. Phƣơng pháp nghiên cứu ............................................................................................... 2 4. Tổng quan luận văn........................................................................................................ 2 CHƢƠNG 1-TỔNG QUAN LÝ THUYẾT VỀ PHÂN CỤM DỮ LIỆU ............................. 3 1.1. Tổng quan về phân cụm dữ liệu.................................................................................. 3 1.2. Phân cụm trong phân loại dữ liệu ............................................................................... 4 1.3. Các yêu cầu của phân cụm dữ liệu............................................................................. 6 1.4. Các kiểu dữ liệu trong phân cụm ................................................................................ 8 1.4.1. Phân loại kiểu dữ liệu dựa trên kích thƣớc miền ................................................. 9 1.4.2. Phân loại kiểu dữ liệu dựa trên hệ đo ................................................................. 9 1.5. Các phép đo độ tƣơng tự và khoảng cách đối với các kiểu dữ liệu .......................... 10 1.5.1. Khái niệm tƣơng tự và phi tƣơng tự .................................................................. 10 1.5.2. Thuộc tính khoảng cách .................................................................................... 11 1.5.3. Thuộc tính nhị phân .......................................................................................... 13 1.5.4. Thuộc tính định danh ........................................................................................ 15 1.5.5. Thuộc tính có thứ tự .......................................................................................... 16 1.5.6. Thuộc tính tỉ lệ ................................................................................................... 16 1.6. Kết luận chƣơng ........................................................................................................ 17 CHƢƠNG 2 - KỸ THUẬT PHÂN CỤM DỮ LIỆU ỨNG DỤNG TRONG PHÂN LOẠI CẤU TRÚC PROTEIN ....................................................................................................... 18 2.1. Giới thiệu .................................................................................................................. 18 2.2. Thuật toán K-means .................................................................................................. 18 2.3. Thuật toán PAM........................................................................................................ 22 2.4. Thuật toán CLARA ................................................................................................... 24 2.5. Thuật toán CLARANS.............................................................................................. 26 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn iii 2.6. Kết luận chƣơng ........................................................................................................ 28 CHƢƠNG 3 - TIN SINH HỌC VÀ PHÂN LOẠI CẤU TRÚC PROTEIN ....................... 29 3.1. Tổng quan về tin sinh học ......................................................................................... 29 3.1.1. Chủ thuyết trung tâm của sinh học phân tử ....................................................... 29 3.1.2. DNA (DesoxyriboNucleic Acid) ....................................................................... 30 3.1.3. RNA (RiboNucleic Acid) .................................................................................. 31 3.1.4. Protein ................................................................................................................ 31 3.1.5. Các dạng protein. ............................................................................................... 32 3.2. Các phƣơng pháp phân loại cấu trúc protein ............................................................ 34 3.2.1. Phân loại cấu trúc với SCOP ............................................................................. 38 3.2.2. Phân loại cấu trúc với CATH............................................................................. 39 3.2.3. Phân loại cấu trúc với phân loại miền Dali (DDD) ........................................... 40 3.3. Kết luận chƣơng ........................................................................................................ 41 CHƢƠNG 4 - CHƢƠNG TRÌNH DEMO VỚI PHẦN MỀM CLUSTERS 3.0 ................. 42 4.1. Phần mềm Clusters 3.0 ............................................................................................. 42 4.1.1. Yêu cầu phần cứng............................................................................................. 42 4.1.2. Nguồn dữ liệu demo chƣơng trình ..................................................................... 42 4.1.3. Sử dụng thƣ viện phân cụm ............................................................................... 42 4.2. Sử dụng thuật toán K-mean, K-medians ................................................................... 43 4.2.1. Khởi tạo ............................................................................................................. 43 4.2.2. Tìm trọng tâm cụm ............................................................................................ 44 4.2.3. Tìm trung bình cụm, hoặc trung vị cụm ............................................................ 44 4.2.4 Tìm giải pháp tối ƣu với K-means và K-medians............................................... 46 4.3. Phần mềm demo........................................................................................................ 48 4.3.1. Đầu vào của chƣơng trình .................................................................................. 48 4.3.2. Giao diện một số chức năng chính của chƣơng trình ........................................ 49 4.3.3. Tệp đầu ra của chƣơng trình .............................................................................. 52 KẾT LUẬN VÀ HƢỚNG NGHIÊN CỨU ......................................................................... 53 Kết luận ............................................................................................................................ 53 Hƣớng nghiên cứu trong thời gian tới ............................................................................. 53 TÀI LIỆU THAM KHẢO ................................................................................................... 54 PHỤ LỤC ............................................................................................................................ 56 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn iv BẢNG KÝ HIỆU CÁC CHỮ VIẾT TẮT Chữ viết tắt Nghĩa tiếng anh Nghĩa tiếng việt 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 ử. PAM Partitioning Around Medoids Thuật toán phân cụm phân vùng xung quanh Medoids CLARA Clustering Large Application Thuật toán phân cụm ứng dụng lớn CLARANS Clustering Large Applications Thuật toán phân cụm với ứng based upon RANdomized dụng lớn trên cơ sở tìm kiếm Search ngẫu nhiên rRNA ribosome RNA Là ARN mã hóa và mang thông tin từ ADN tRNA transfer RNA Là RNA vận chuyển mRNA messenger RNA RNA thông tin SCOP Structural Classification of Proteins Phân loại cấu trúc các protein 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ự DNA Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn v DANH MỤC BẢNG BIỂU Bảng 1.1 Bảng dự đoán cho hai đối tƣợng nhị phân x và y……………... 14 Bảng 1.2 Ví dụ về độ phi tƣơng tự của thuộc tính nhị phân…………….. 15 Bảng 2.1. Bảng so sánh các thuật toán phân cụm trung tâm……………. 28 Bảng 3.1 Đƣa ra một số nguồn tài nguyên phân loại trình tự protein…... 35 Bảng 3.2 Nguồn tài nguyên cho phân loại cấu trúc protein……………... 36 Bảng 3.3 Các cấp độ chính của CATH………………………………….. 39 DANH MỤC CÁC HÌNH Hình 1.1. Phân cụm các vector truy vấn .................................................... Hình 1.2. Hình thành cụm cha ................................................................... Hình 1.3. Các tỉ lệ khác nhau có thể dẫn tới các cụm khác nhau .............. Hình 2.1 Sơ đồ phân loại các phƣơng pháp phân cụm………………….. Hình 2.2. Các thiết lập để xác định danh giới các cụm ban đầu ................ Hình 2.3. Tính toán trọng tâm của các cụm mới ........................................ Hình 2.4 Ví dụ minh họa thuật toán K-means ........................................... Hình 2.5 Ví dụ minh họa thuật toán PAM ................................................ Hình 3.1. Chủ thuyết trung tâm của sinh học phân tử ............................... Hình 3.2. Cấu trúc DNA ............................................................................ Hình 3.3. Các kiểu cấu trúc của Protein ..................................................... Hình 3.4. Cấu trúc bậc 2 thƣờng thấy của protein ..................................... Hình 3.5. Hai ví dụ về protein màng .......................................................... Hình 3.6. Sự phát triển của cấu trúc dữ liệu protein .................................. Hình 4.1 Đầu vào dữ liệu………………………………………………... Hình 4.2 Giao diện chọn tệp đầu vào……………………………………. Hình 4.3 Giao diện tab Lọc dữ liệu…………………………………….. Hình 4.4 Giao diện tab chỉnh sửa dữ liệu………………………………. Hình 4.5 Giao diện Tab K-Means, sử dụng K-means hoặc K-medians để phân cụm………………………………………………………………… Hình 4.6 Đầu ra dữ liệu…………………………………………………. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 5 6 12 18 19 20 21 24 30 30 32 33 34 35 48 49 49 50 51 52 1 MỞ ĐẦU 1. LÝ DO CHỌN ĐỀ TÀI Với sự phát triển vƣợt bậc của công nghệ thông tin, đặc biệt là ứng dụng công nghệ thông tin vào các ngành sinh học đã giúp ích rất nhiều cho việc tìm hiểu nghiên cứu về sinh học phân tử. Chính vì vậy 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. Nhƣ chúng ta đã biết, các cơ sở phân tử của cuộc sống dựa trên hoạt động của phân tử sinh học, bao gồm axit nucleic (DNA và RNA), carbohydrate, chất béo, và protein. Mặc dù mỗi loại đều đóng một vai trò thiết yếu trong cuộc sống, nhƣng protein có một sự nổi bật bởi chúng là thành phần biểu diễn chính các chức năng của tế bào. Chính vì vậy, tìm hiểu và nghiên cứu cấu trúc phân tử sinh học đã 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. Hƣớng phát triển này của sinh học đã trải qua với sự phát triển cao thông qua nghiên cứu cấu trúc với mục đích có cái nhìn toàn diện về không gian cấu trúc protein, thông tin lƣu trữ trong dữ liệu cấu trúc protein là chìa khóa để thành công nằm trong khả năng để tổ chức, phân tích thông tin chứa trong cơ sở dữ liệu, tích hợp những thông tin đó với những nỗ lực khác nhằm giải quyết những bí ẩn của chức năng tế bào. Nhận thấy tính thiết thực của vấn đề này và đƣợc sự gợi ý của giảng viên hƣớng dẫn, em đã chọn đề tài "Phân cụm dữ liệu và ứng dụng trong phân loại cấu trúc protein" 2. MỤC TIÊU NGHIÊN CỨU - Tìm hiểu tổng quan về lý thuyết phân cụm dữ liệu. - Nghiên cứu một số kỹ thuật phân cụm dữ liệu ứng dụng trong phân loại cấu trúc protein. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2 - Tìm hiểu về Tin sinh học và một số vấn đề liên quan, nghiên cứu các phƣơng pháp phân loại cấu trúc protein. - Tìm hiểu và sử dụng phần mềm Cluster 3.0 ứng dụng vào trong phân loại cấu trúc protein. 3. PHƢƠNG PHÁP NGHIÊN CỨU - Nghiên cứu qua các tài liệu nhƣ: sách, sách điện tử, các bài báo, thông tin tài liệu trên các website và các tài liệu liên quan. - Phân tích, tổng hợp lý thuyết và giới thiệu về phân cụm dữ liệu và một số thuật toán phân cụm dữ liệu dựa vào cụm trung tâm ứng dụng trong phân loại cấu trúc protein. - Tìm hiểu và sử dụng phần mềm Cluster 3.0 ứng dụng thuật toán Kmeans để phân loại cấu trúc protein. 4. TỔNG QUAN LUẬN VĂN Luận văn đƣợc trình bày trong 4 chƣơng và phần kết luận, với nội dung đƣợc trình bày từ việc tìm hiểu các khái niệm cơ bản đến các nội dung chính cần đi sâu tìm hiểu, giúp ngƣời đọc có cái nhìn tổng quan cũng nhƣ những vấn đề chính đƣợc nghiên cứu: - Chƣơng 1 - Tổng quan: Giới thiệu tổng quan về lý thuyết phân cụm dữ liệu. - Chƣơng 2 - Một số kỹ thuật phân cụm dữ liệu ứng dụng trong phân loại cấu trúc protein. - Chƣơng 3 - Tin sinh học và Phân loại cấu trúc Protein. - Chƣơng 4 - Chƣơng trình Demo với phần mềm cluster 3.0. - Kết luận - Tóm tắt các nội dung chính, các kết quả đạt đƣợc và hƣớng nghiên cứu tiếp theo của luận văn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 3 CHƢƠNG 1 TỔNG QUAN LÝ THUYẾT VỀ PHÂN CỤM DỮ LIỆU 1.1. TỔNG QUAN VỀ 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. Mỗi nhóm đƣợc gọi là một 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ề cluster, nhƣng các định nghĩa sau đây đƣợc sử dụng nhiều nhất [4]: - "Một cluster 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 cluster đó". - "Một cluster 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 cluster 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,… Bằng phân cụm, trong thƣơng mại có thể giúp những nhà phân tích thị trƣờng tìm ra những nhóm khách hàng có những nhu cầu riêng dựa trên độ tuổi, sở thích và tâm lý tiêu dùng. Trong sinh học, nó có thể đƣợc sử dụng để phân loại thực vật, động vật, phân loại cấu trúc protein dựa trên các cấu trúc tƣơng đồng vốn có, từ đó có thể xây dựng ngân hàng dữ liệu protein. Trong xử lý thông tin, phân cụm giúp phân loại các tài liệu với dạng lƣu trữ văn, trên đĩa Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 4 mềm, trên ổ cứng, trên mạng internet thành giúp tạo lập và hoàn chỉnh kho dữ liệu khổng lồ về tri thức của loài ngƣời. Là một chức năng khai phá dữ liệu, phân cụm có thể sử dụng nhƣ một công cụ độc lập để quan sát đặc trƣng của mỗi cụm thu đƣợc bên trong sự phân bố dữ liệu và tập trung vào một tập riêng biệt của các cụm để phân tích. Phân cụm có thể dụng nhƣ một bƣớc tiền xử lý cho các thuật toán nhƣ phân loại, mô tả đặc điểm, phát hiện ra các cụm với các đặc trƣng, tính chất khác nhau. 1.2. PHÂN CỤM TRONG PHÂN LOẠI DỮ LIỆU Các mục dữ liệu tƣơng tự nhau đƣợc nhóm lại để hình thành các cụm trên cơ sở độ đo mức tƣơng tự nào đó. Mỗi cụm đƣợc biểu diễn bởi trọng tâm vector đặc trƣng của cụm. Trong khi truy vấn, ta tính toán độ tƣơng tự giữa vector truy vấn và từng cụm (đại diện bởi trọng tâm cụm). Các cụm mà độ tƣơng tự của nó với vector truy vấn mà lớn hơn ngƣỡng nào đó thì đƣợc lựa chọn. Sau đó, độ tƣơng tự giữa vector truy vấn với từng vector đặc trƣng trong cụm đƣợc tính toán và k mục gần nhất đƣợc xếp hạng và đƣợc xem nhƣ kết quả. Ví dụ, các vector đặc trƣng trên hình 1.1 đƣợc nhóm vào 11 cụm. Trong khi truy tìm, vector truy vấn đƣợc so sánh với lần lƣợt 11 trọng tâm cụm. Nếu tìm thấy trọng tâm cụm 2 gần giống vector truy vấn nhất thì ta tính khoảng cách giữa vector truy vấn với từng vector đặc trƣng trong cụm 2. Tổng số tính toán khoảng cách đòi hỏi phải nhỏ hơn nhiều tổng các vector đặc trƣng trong cơ sở dữ liệu. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 5 Hình 1.1: Phân cụm các vector truy vấn Trong phƣơng pháp truy tìm trên cơ sở cụm trên đây, mức độ tƣơng tự đƣợc tính toán giữa câu truy vấn và từng trọng tâm và với từng vector đặc trƣng trong cụm lựa chọn. Khi tổng số cụm mà lớn, ta sử dụng cụm nhiều tầng để làm giảm tính toán mức độ tƣơng tự giữa truy vấn và trọng tâm. Các cụm tƣơng tự nhau đƣợc nhóm để hình thành cụm lớn hơn (super-cluster). Trong khi truy tìm, trƣớc hết so sánh vector truy vấn với trọng tâm của cụm cha sau đó so sánh với từng trọng tâm các cụm bên trong cụm cha, cuối cùng so sánh với các vector đặc trƣng của cụm con. Hãy xem xét không gian đặc trƣng trên hình 1.1, ta có thể hình thành cụm cha nhƣ hình 1.2. Trong khi truy vấn, so sánh vector truy vấn với từng trọng tâm của 4 cụm cha. Nếu tìm thấy trọng tâm của cụm cha 1 là gần vector truy vấn nhất, hãy so sánh vector truy vấn với ba trọng tâm cụm con trong cụm cha 1. Trong thí dụ cụm hai mức này, tổng số khoảng cách tính toán đòi hỏi giữa vector truy vấn và trọng tâm (của các cụm cha và cụm con) là 7 (4+3), nhỏ hơn 11 tính toán khi sử dụng cụm một tầng. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 6 Hình 1.2: Hình thành cụm cha Cụm không chỉ làm truy tìm hiệu quả mà còn làm dễ dàng cho việc duyệt và dẫn đƣờng. Với duyệt và dẫn đƣờng, một mục đại diện mà có vector đặc trƣng gần trọng tâm cụm của nó thì đƣợc hiển thị cho mỗi cụm. Nếu ngƣời sử dụng quan tâm đến mục đại diện thì họ có thể quan sát các mục khác trong cụm. Các kỹ thuật cụm đƣợc sử dụng chung với các cấu trúc dữ liệu để tìm kiếm hiệu quả hơn. Các mục tƣơng tự đƣợc nhóm thành cụm. Trọng tâm các cụm hoặc/và các mục trong mỗi cụm đƣợc tổ chức nhờ cấu trúc dữ liệu nào đó để tìm kiếm hiệu quả. 1.3. CÁC YÊU CẦU CỦA 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 [1]: - Có khả năng mở rộng: Nhiều thuật toán phân cụm làm việc tốt với những tập dữ liệu nhỏ chứa ít hơn 200 đối tƣợng, tuy nhiên, một cơ sở dữ liệu lớn có thể chứa tới hàng triệu đối tƣợng. Việc phân cụm với một tập dữ liệu lớn có thể làm ảnh hƣởng tới kết quả. Vậy làm cách nào để chúng ta có thể Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 7 phát triển các thuật toán phân cụm có khả năng mở rộng cao đối với các cơ sở dữ liệu lớn? - Khả năng thích nghi với các kiểu thuộc tính khác nhau: Nhiều thuật toán đƣợc thiết kế cho việc phân cụm dữ liệu có kiểu khoảng (kiểu số). Tuy nhiên, nhiều ứng dụng có thể đòi hỏi việc phân cụm với nhiều kiểu dữ liệu khác nhau, nhƣ kiểu nhị phân, kiểu tƣờng minh (định danh - không thứ tự), và dữ liệu có thứ tự hay dạng hỗn hợp của những kiểu dữ liệu này. - Khám phá các cụm với hình dạng bất kỳ: Nhiều thuật toán phân cụm xác định các cụm dựa trên các phép đo khoảng cách Euclide và khoảng cách Manhattan. Các thuật toán dựa trên các phép đo nhƣ vậy hƣớng tới việc tìm kiếm các cụm hình cầu với mật độ và kích cỡ tƣơng tự nhau. Tuy nhiên, một cụm có thể có bất cứ một hình dạng nào. Do đó, việc phát triển các thuật toán có thể khám phá ra các cụm có hình dạng bất kỳ là một việc làm quan trọng. - Tối thiểu lượng tri thức cần cho xác định các tham số đầu vào: Nhiều thuật toán phân cụm yêu cầu ngƣời dùng đƣa vào những tham số nhất định trong phân tích phân cụm (nhƣ số lƣợng các cụm mong muốn). Kết quả của phân cụm thƣờng khá nhạy cảm với các tham số đầu vào. Nhiều tham số rất khó để xác định, nhất là với các tập dữ liệu có lƣợng các đối tƣợng lớn. Điều này không những gây trở ngại cho ngƣời dùng mà còn làm cho khó có thể điều chỉnh đƣợc chất lƣợng của phân cụm. - Khả năng thích nghi với dữ liệu nhiễu: Hầu hết những cơ sở dữ liệu thực đều chứa đựng dữ liệu ngoại lai, dữ liệu lỗi, dữ liệu chƣa biết hoặc dữ liệu sai. Một số thuật toán phân cụm nhạy cảm với dữ liệu nhƣ vậy và có thể dẫn đến chất lƣợng phân cụm thấp. - Ít nhạy cảm với thứ tự của các dữ liệu vào: Một số thuật toán phân cụm nhạy cảm với thứ tự của dữ liệu vào, ví dụ nhƣ với cùng một tập dữ liệu, khi đƣợc đƣa ra với các thứ tự khác nhau thì với cùng một thuật toán có thể sinh Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 8 ra các cụm rất khác nhau. Do đó, việc quan trọng là phát triển các thuật toán mà ít nhạy cảm với thứ tự vào của dữ liệu. - Số chiều lớn: Một cơ sở dữ liệu hoặc một kho dữ liệu có thể chứa một số chiều hoặc một số các thuộc tính. Nhiều thuật toán phân cụm áp dụng tốt cho dữ liệu với số chiều thấp, bao gồm chỉ từ hai đến 3 chiều. Ngƣời ta đánh giá việc phân cụm là có chất lƣợng tốt nếu nó áp dụng đƣợc cho dữ liệu có từ 3 chiều trở lên. Nó là sự thách thức với các đối tƣợng dữ liệu cụm trong không gian với số chiều lớn, đặc biệt vì khi xét những không gian với số chiều lớn và có độ nghiêng lớn. - Phân cụm ràng buộc: Nhiều ứng dụng thực tế có thể cần thực hiện phân cụm dƣới các loại ràng buộc khác nhau. Giả sử rằng công việc của ta là lựa chọn vị trí cho một số trạm rút tiền tự động ở một thành phố. Để quyết định dựa trên điều này, có thể phân cụm những hộ gia đình trong khi xem xét các mạng lƣới sông và đại lộ, và những yêu cầu khách hàng của mỗi vùng nhƣ những sự ràng buộc. Một nhiệm vụ đặt ra là đi tìm những nhóm dữ liệu có trạng thái phân cụm tốt và thỏa mãn các ràng buộc. - Dễ hiểu và dễ sử dụng: Ngƣời sử dụng có thể chờ đợi những kết quả phân cụm dễ hiểu, dễ lý giải và dễ sử dụng. Nghĩa là, sự phân cụm có thể cần đƣợc giải thích ý nghĩa và ứng dụng rõ ràng. Việc nghiên cứu cách để một ứng dụng đạt đƣợc mục tiêu là rất quan trọng, có thể gây ảnh hƣởng tới sự lựa chọn các phƣơng pháp phân cụm. 1.4. CÁC KIỂU DỮ LIỆU TRONG PHÂN CỤM 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) [1]. Các thuộc tính này là các tham số cho phép giải quyết vấn đề phân cụm và chúng có tác động đáng kể đến kết quả phân cụm. Phân loại các kiểu thuộc tính khác nhau Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 9 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. 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 [9]. 1.4.1. Phân 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...) 1.4.2. Phân 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 x i > 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. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 10 - Thuộc tính tỉ lệ: Là thuộc tính khoảng nhƣng đƣợc xác định một cách tƣơng đối so với điểm mốc đầ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. - Dữ liệu không gian liên tục: Bao chứa một vùng không gian. - Dữ liệu không gian rời rạc: Có thể là một điểm trong không gian nhiều chiều và cho phép xác định đƣợc khoảng cách giữa các đối tƣợng dữ liệu trong không gian. Thông thƣờng, các thuộc tính số đƣợc đo bằng các đơn vị xác định nhƣ kilogams hay centimeters. Tuy nhiên, việc thay đổi các đơn vị đó có ảnh hƣởng đến kết quả phân cụm (ví dụ, thay đổi đơn vị đo cho thuộc tính chiều cao từ centimeters sang inches có thể mang lại kết quả khác nhau trong phân cụm). Để khắc phục điều này phải chuẩn hóa dữ liệu đƣợc thực hiện bằng cách thay thế mỗi một thuộc tính bằng thuộc tính số hoặc thêm các trọng số cho các thuộc tính. 1.5. CÁC PHÉP ĐO ĐỘ TƢƠNG TỰ VÀ KHOẢNG CÁCH ĐỐI VỚI CÁC KIỂU DỮ LIỆU 1.5.1. Khái niệm tƣơng tự và phi tƣơng tự 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 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ự Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 11 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. Ví dụ, đối với thuộc tính hạng mục thì không sử dụng độ đo khoảng cách mà sử dụng một hƣớng hình học của dữ liệu. Tất cả các độ đo dƣới đây đƣợc xác định trong không gian metric. Bất kỳ một metric nào cũng là một độ đo, nhƣng điều ngƣợc lại không đúng. Để tránh sự nhầm lẫn, thuật ngữ độ đo ở đây đề cập đến hàm tính độ tƣơng tự hoặc hàm tính độ phi tƣơng tự. 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. - Quy tắc nói trên thỏa mãn hệ tính chất sau: + δ(x, y) > 0 nếu x ≠ y; + δ(x, y) = 0 nếu x = y; + δ(x, y) = δ(y, x) với mọi x, y; + δ(x, y) ≤ δ(x, z)+ δ(z, y) Hàm δ(x, y) đƣợc gọi là một metric của không gian. Các phần tử của X đƣợc gọi là các điểm của không gian này. 1.5.2. Thuộc tính khoảng cách Một thành phần quan trọng trong thuật toán phân cụm là phép đo khoảng cách giữa hai điểm dữ liệu. Nếu thành phần của vector thể hiện dữ liệu thuộc Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 12 trong cùng một đơn vị giống nhau thì nó tồn tại khoảng cách Euclide có thể xác định đƣợc nhóm dữ liệu tƣơng tự. Tuy nhiên, không phải lúc nào khoảng cách Euclide cũng cho kết quả chính xác. Hình 1.3 minh họa ví dụ về phép đo chiều cao và chiều ngang của một đối tƣợng đƣợc thực hiện trong một đơn vị vật lí giống nhau nhƣng khác nhau về tỉ lệ. Hình 1.3: Các tỉ lệ khác nhau có thể dẫn tới các cụm khác nhau Tuy nhiên chú ý rằng đây không chỉ là vấn đề đồ thị: vấn đề phát sinh từ công thức toán học đƣợc sử dụng để kết hợp khoảng cách giữa các thành phần đơn đặc tính dữ liệu vector vào trong một độ đo khoảng duy nhất mà có thể đƣợc sử dụng cho mục đích phân cụm và các công thức khác nhau dẫn tới những cụm khác nhau. Các thuật toán cần có các phép đo khoảng cách hoặc độ tƣơng tự giữa hai đối tƣợng để thực hiện phân cụm. Kiến thức miền phải đƣợc sử dụng để biểu diễn phép đo khoảng cách thích hợp cho mỗi ứng dụng. Hiện nay thƣờng sử dụng một số phép đo khoảng cách phổ biến [8]: - Phép đo khoảng cách Minkowski đƣợc định nghĩa nhƣ sau:  n q dist q ( x, y )    xi  yi   i 1  1 q ,q 1 trong đó, x và y là hai đối tƣợng với n là số lƣợng thuộc tính, x = (x 1, x2,…, xn) và y = (y1, y2,…, yn); dist là kích thƣớc của dữ liệu, q là số nguyên dƣơng. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 13 - Phép đo khoảng cách Euclide: dist q ( x, y)  n  x  y  i 1 i 2 i ; là khoảng cách Minkowski giữa hai đối tƣợng trong trƣờng hợp q=2 - Phép đo khoảng cách Manhattan:  n dist q ( x, y)    xi  yi  i 1  ;  là khoảng cách Minkowski giữa hai đối tƣợng trong trƣờng hợp đặc biệt q =1. - Khoảng cách Chebychev: n dist  ( x, y)  max i=1 xi  yi ; Trong trƣờng hợp q = ∞, hữu ích để định nghĩa các đối tƣợng phi tƣơng tự nếu chúng khác nhau chỉ trong một kích thƣớc biến đổi. 1.5.3. Thuộc tính nhị phân Một thuộc tính nhị phân là một thuộc tính có hai giá trị chính xác nhất có thể, chẳng hạn nhƣ "Đúng" hay "Sai". Lƣu ý rằng các biến nhị phân có thể đƣợc chia thành hai loại: biến nhị phân đối xứng và các biến nhị phân bất đối xứng. Trong một biến nhị phân đối xứng, hai giá trị có quan trọng không kém nhau. Một ví dụ là "nam-nữ". Biến nhị phân đối xứng là một biến danh nghĩa. Trong một biến không đối xứng, một trong những giá trị của nó mang tầm quan trọng hơn biến khác. Ví dụ, "có" là viết tắt của sự hiện diện của một thuộc tính nhất định và "không" nghĩa là sự vắng mặt của một thuộc tính nhất định. Nếu xem xét p là biến định danh, có thể đánh giá độ tƣơng tự của các trƣờng hợp bằng số các biến mà có giá trị giống nhau, định nghĩa với một biến nhị phân mới từ mỗi biến danh nghĩa, bằng việc nhóm các nhãn danh nghĩa thành hai lớp, một nhãn là 1, và nhãn khác là 0. Xây dựng và xem xét Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn