ĐẠ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

/>

ĐẠ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

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

/>

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

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


DNA

Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

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

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


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

/>

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

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

/>

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.

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

/>



/>

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


/>

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


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

đƣợ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

/>

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ề

+ (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.3.4.1. 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 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.
1.3.4.2. 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ó tầm
quan trọng không kém nhau.
1.3.4.4. Thuộc tính có thứ tự
Phép đo độ phi tƣơng tự giữa các đối tƣợng dữ liệu với thuộc tính
thứ tự đƣợc thực hiện nhƣ sau:
Giả sử i là thuộc tính thứ tự có Mi giá trị (Mi là kích thƣớc miền giá
trị):
Các trạng thái Mi đƣợc sắp thứ tự nhƣ nhau: [1...Mi], có thể thay thế
mỗi giá trị của thuộc tính bằng giá trị cùng loại ri với ri {1...Mi}.

Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

13


Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

14

1.3.5.1. Phương pháp phân cụm phân hoạch
Ý tƣởng chính của kỹ thuật này là phân hoạch một tập hợp dữ liệu có
n phần tử cho trƣớc thành k nhóm dữ liệu sao mỗi phần tử dữ liệu chỉ thuộc
về một nhóm dữ liệu có tối thiểu ít nhất một phần tử dữ liệu. Số các cụm
đƣợc thiết lập là các đặc trƣng đƣợc lựa chọn trƣớc. Phƣơng pháp này là tốt
cho việc tìm các cụm hình cầu trong không gian Euclidean. Ngoài ra,
phƣơng pháp này cũng phụ thuộc vào khoảng cách cơ bản giữa các điểm để
lựa chọn các điểm dữ liệu nào có quan hệ là gần nhau với mỗi điểm khác
và các điểm dữ liệu nào không có quan hệ hoặc có quan hệ là xa nhau so
với mỗi điểm khác. Tuy nhiên, phƣơng pháp này không thể xử lý các cụm
có hình dạng kỳ quặc hoặc các cụm có mật độ các điểm dầy đặc.
Lớp các thuật toán phân cụm phân hoạch bao gồm các thuật toán đề
xuất đầu tiên trong lĩnh vực KPDL cũng là thuật toán đƣợc áp dụng nhiều
trong thực tế nhƣ K-means, K-medoids, PAM, CLARA, CLARANS,... [6]
Thuật toán K-means là một trong những thuật toán phổ biến nhất. Nó
căn cứ vào khoảng cách giữa các đối tƣợng để phân cụm. Các đối tƣợng
đƣợc xếp vào một cụm dựa trên khoảng cách từ chúng tới tâm cụm. Trong
thuật toán này, chúng ta chọn một giá trị cho k (số các cụm mong muốn),
sau đó chọn ngẫu nhiên k đối tƣợng làm k cụm ban đầu. Tiếp theo ta tính
toán khoảng cách giữa từng đối tƣợng với k cụm này. Căn cứ vào khoảng
cách tính đƣợc để xếp từng đối tƣợng vào cụm thích hợp. Sau khi phân
cụm, ta lại tìm tâm mới cho từng cụm. Quá trình này đƣợc lặp lại cho đến
khi tâm các cụm ổn định. Thuật toán này có một vài phiên bản, phân biệt
với nhau bằng hàm tính khoảng cách. Thuật toán K-means thích hợp với

Hình 1.2. Các chiến lược phân cụm phân cấp

Số hóa bởi Trung tâm Học liệu - ĐHTN

/>

16

Trong thực tế áp dụng, có nhiều trƣờng hợp ngƣời ta kết hợp cả hai
phƣơng pháp phân cụm phân hoạch và phân cụm phân cấp, nghĩa là kết quả
thu đƣợc của phƣơng pháp phân cấp có thể cải tiến thông qua bƣớc phân
cụm phân hoạch. Phân cụm phân hoạch và phân cụm phân cấp là hai
phƣơng pháp PCDL cổ điển, hiện đã có rất nhiều thuật toán cải tiến dựa
trên hai phƣơng pháp này đã đƣợc áp dụng phổ biến trong KPDL. Phƣơng
pháp này bao gồm các thuật toán AGNES, DIANA, BIRCH, CURE,
ROCK, Chemeleon,...[4]
1.3.5.3. Phương pháp phân cụm dựa trên mật độ
Phƣơng pháp này nhóm các đối tƣợng theo hàm mật độ xác định.
Mật độ xác định đƣợc định nghĩa nhƣ là số các đối tƣợng lân cận của một
đối tƣợng dữ liệu theo một ngƣỡng nào đó. Trong cách tiếp cận này, khi
một cụm dữ liệu mới miễn là số các đối tƣợng lân cận của các đối tƣợng
này phải lớn hơn một ngƣỡng đã đƣợc xác định trƣớc. Phƣơng pháp phân
cụm dựa vào mật độ của các đối tƣợng để xác định các cụm dữ liệu và có
thể phát hiện ra các cụm dữ liệu với nhiều hình dạng bất kỳ. Tuy vậy, việc
xác định các tham số mật độ của thuật toán rất khó khăn, trong khi các
tham số này lại có thể tác động rất lớn đến kết quả của PCDL. Hình 1.3
minh hoạ về các cụm dữ liệu với các hình thù khác nhau dƣạ trên mật
độ đƣợc khám phá từ 3CSDL khác nhau.

Hình 1.3. Một số hình dạng khám phá bởi phân cụm dựa trên mật độ