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.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.
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 K- means để phân loại cấu trúc protein. 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. - 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.vn 3 CHƢƠNG 1 TỔNG QUAN LÝ THUYẾT VỀ PHÂN CỤM DỮ LIỆU 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.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.
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.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. 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.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ả. 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.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.