ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Đỗ Thị Nương
NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP PHÂN
CỤM CHO DỮ LIỆU GENE MICROARRAY KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin
HÀ NỘI- 2010
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
HÀ NỘI-2010
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
i
Lời cảm ơn
Trước tiên, tôi muốn gửi lời cảm ơn sâu sắc đến cô Nguyễn Thị Hậu người đã
tận tình chỉ bảo tôi trong suốt quá trình thực hiện khóa luận.
Tôi cũng xin chân thành cảm ơn các thấy cô giáo của trường Đại Học Công
Nghệ, những người đã tận tình chỉ bảo dạy dỗ và trang bị cho tôi những kiến thức quý
báu trong suốt 4 năm học trong trường.
Tôi cũng muốn gửi lời cảm ơn tới những bạn trong lớp K51CD những người đã
đồng hành cùng tôi trong suốt những năm tháng ở giảng đường đại học. Các bạn cũng
luôn động viên và giúp đỡ tôi rất nhiều trong thời gian tôi làm khóa luận.
Cuối cùng, tôi cũng muốn gửi lời cảm ơn vô hạn đến gia đình và các bạn của tôi
những người luôn ở bên động viên tôi để tôi có thể hoàn thành tốt khóa luận này.
Hà Nội, ngày 17 tháng 5 năm 2010
Sinh Viên
Đỗ Thị Nương
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
iiTóm tắt nội dung
Dữ liệu microarrays là những bước đột phá mới nhất trong sinh học phân tử.
Nó cho phép kiểm tra mô tả gene của khoảng mười nghìn gene đồng thời.
Kết quả của những thí nghiệm sử dụng công nghệ microarray này sẽ được đem
phân tích ở mức thấp và cho ra một tập dữ liệu gọi là dữ liệu gene micrarray. Dữ liệu
Mở đầu 5
Chương 1: Giới thiệu bài toán phân cụm cho dữ liệu gene microarray 7
1.1.
Bài toán phân cụm nói chung 7
1.1.1.
Khái niệm 7
1.1.2.
Các kiểu phân cụm khác nhau 7
1.1.3.
Những loại cụm khác nhau 8
1.2.
Phân cụm cho dữ liệu gene microarray 9
1.2.1.
Giới thiệu công nghệ DNA microarray 9
1.2.2.
Một số phương pháp phân cụm 17
2.2.1.
Phân cụm Hierarchical 17
2.2.2.
K-Means Clustering (KMC) 19
2.2.3.
Self-Organizing Maps(SOMs) 20
2.2.4.
Principal Components Analysis-(PCA) 21
2.3. Phương pháp phân cụm intra-cluster 22
Chương 3: Đề xuất hướng giải quyết của bài toán phân cụm cho dữ liệu gene
microarray 24
3.1.
Phương pháp phân cụm 24
3.1.1. Lý do chọn K-means 24
3.1.2. Lý do chọn “intra-cluster” 24
iv
4.1.
Các chức năng của ứng dụng 27
4.1.1.Mô hình tương tác giữa các module 27
4.1.2.
Tải, Lưu file, lọc, điều chỉnh dữ liệu và xử lý dữ liệu khuyết 28
4.1.3.
Phân cụm K-means 31
4.3.
Định dạng dữ liệu vào, ra 32
4.3.1.
Dữ liệu tải vào 32
4.3.2.
Định dạng dữ liệu ra 33
4.4.
Kết quả và đánh giá 38
5.3.1.
Kết quả 38
5.3.2.
Đánh giá 40
Tổng kết 42
Tài liệu tham khảo 43Danh mục hình vẽ bảng biểu
Hình 1: Thí nghiệm microarray 11
Hình 2: Minh họa việc tính dữ liệu mô tả gene. 12
Hình 3: Ví dụ về vector mô tả gene trong log 14
Hình 4: Ví dụ về ma trận mô tả gene 15
Hình 5: Mô tả những phương pháp linkage khác nhau 19
Hình 6 : Sơ đồ DFD mô tả sự tương tác dữ liệu và chức năng 28
Hình 7: Giao diện cho menu của chương trình 29
đó. Những gene này được biểu hiện một cách chọn lọc trong mỗi tế bào phụ thuộc vào
từng loại tế bào, từng loại mô, và những điều kiện cả bên trong lẫn bên ngoài tế bào.
Do sự phát triển của những kỹ thuật sinh học phân tử và tái tổ hợp gene mà đã đưa ra
một kết luận rằng những sự kiện quan trọng trong đời sống của một tế bào là được quy
định bởi những nhân tố mà làm thay đổi những miêu tả của các gene của chúng. Vì
vậy việc hiểu mô tả của các gene đã trở thành lĩnh vực quan trọng trong việc nghiên
cứu sinh học hiện đại. Hai câu hỏi chính đặt ra khi quản lý việc miêu tả của gene là:
Việc mô tả gene làm cách nào có thể phát hiện ra chức năng của tế bào và bệnh lý của
tế bào? Những câu hỏi này có thể được phân chia chi tiết như sau:
Mức độ mô tả của gene trong những tế bào và những trạng thái khác nhau thì
khác nhau như thế nào?
Những chức năng của các genes khác nhau là gì? Và những mô tả của những
gene này thay đổi như thể nào tương ứng với những thay đổi vật lý bên trong môi
trường của tế bào.
Mô tả gene bị tác động bởi những loại bệnh như thế nào? Những gene nào quy
định tính di truyền của các bệnh.
Những gene nào bị tác động trong quá trình điều trị bệnh.
Những thay đổi của những giá trị mô tả gene là gì trong theo chuỗi thời gian tiến
hành thí nghiệm.
Trước khi phát triển công nghệ DNA microarray đã có một số phương pháp được
sử dụng để phân tích những mẫu mô tả của những gene. Tuy nhiên những phương
pháp này đều có hạn chế là chỉ thực hiện được trên một số ít các mẫu gene vì vậy
không đem lại hiệu quả cao.
Khi có sự xuất hiện của công nghệ micoarray, nó đã đưa ra được bước chuyển
biến mạnh mẽ trong việc phân tích những mẫu mô tả của hàng chục nghìn gene một
cách nhanh chóng và hiệu quả. Để có thể trả lời một cách chính xác và thỏa đáng
những câu hỏi trên thì bài toán đặt ra là “ tìm các phương pháp để phân cụm cho dữ
liệu gene microarray một cách hiệu quả”.
Khóa luận này sẽ giúp tìm hiểu về một số phương pháp cụm cho phổ biến. Tìm
ra những ưu nhược điểm của những phương pháp này và nghiên cứu những giải pháp
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
7
Chương 1: Giới thiệu bài toán phân cụm cho dữ
liệu gene microarray
1.1. Bài toán phân cụm nói chung
Trước khi thảo luận việc phân cụm cho dữ liệu gene microarray ta sẽ đi tìm hiểu
về khái niệm phân cụm nói chung. Đầu tiên, ta sẽ đi định nghĩa về phân tích cụm,
chứng minh vì sao nó khó và giải thích mối quan hệ của nó với các kỹ thuật nhóm dữ
liệu khác. Sau đó chúng ta sẽ đi khai thác 2 chủ đề quan trọng: (1) những cách nhóm
một tập các đối tượng thành một tập những cụm và (2) những loại cụm.
1.1.1. Khái niệm
Phân cụm là nhóm những đối tượng dựa trên thông tin mà tìm thấy trong dữ liệu
miêu tả đối tượng và những mối quan hệ của chúng. Mục đích của việc phân cụm là để
Kiểu phân cụm được thảo luận nhiều nhất trong số những kiểu phân cụm là tập
những cụm được “lồng nhau” hay “không lồng nhau” hay theo một thuật ngữ truyền
thống hơn là “cấu trúc” hay “phân vùng”. Phân cụm phân vùng đơn giản là phân chia
tập những đối tượng dữ liệu thành những tập con (những cụm) không gối trồng lên
nhau như là mỗi đối tượng dữ liệu chỉ ở một tập con.
Nếu chúng ta cho phép những cụm có những cụm con thì chúng ta sẽ thu được
phân cụm cấu trúc, chúng là một tập những cụm lồng nhau mà có thể được tổ chức
như một cây. Mỗi nút (cụm-cluster) trên cây ngoại trừ nút lá là hợp của những con
(những cụm con) của nó, và gốc của cây là những cụm mà chứa tất cả những đối
tượng.
Phân cụm mức đỉnh (exclusive), gối chồng (overlapping) và mờ (fuzzy)[12]
Phân cụm “mức đỉnh”: Gán mỗi đối tượng tới một cụm đơn.
Có rất nhiều trường hợp mà một đối tướng có thể phù hợp cho nhiều hơn một
cụm, những trường hợp này được gọi là non-exclusive. Theo một nghĩa chung nhất
overlapping hay non-exclusive thường được sử dụng để chỉ đến một đối tượng mà
đồng thời có thể thuộc nhiều hơn một cụm. Phân cụm non-exclusive một đối tượng là
ở giữa 2 hay nhiều hơn cụm và có thể được gán cho bất kỳ cụm nào trong số những
cụm này.
Trong phân cụm fuzzing mỗi đối tượng phụ thuộc vào mỗi cụm với ‘trọng số
thành viên ‘ nằm giữa 0 và 1 là 0 tức là tuyệt đối không phụ thuộc, 1 tức là tuyệt đối
phụ thuộc. Theo nghĩa khác, những cụm này được xem như là những tập ‘mờ’ hay
fuzzy. ( Theo toán học những tập mờ là tập mà một đối tượng phụ thuộc vào bất kỳ tập
nào với trọng lượng nằm giữa 0 và 1. Trong phân cụm mờ chúng ta thường cho thêm
ràng buộc tổng trọng lượng của mỗi đối tượng phải bằng 1. Trong thực tế, phân cụm
mờ thường được chuyển thành phân cụm mức đỉnh bằng việc gán mỗi đối tượng tới
cụm mà trọng lượng thành viên của nó là cao nhất.
Phân cụm một phần với đầy đủ(complete vs patial)[12]: Việc phân cụm đầy đủ
gán mỗi đối tượng tới cụm còn phân cụm một phần thì không . Động lực cho phân
cụm một phần là một vài đối tượng trong tập dữ liệu có thể không thuộc vào những
chia sẻ một vài thuộc tính chung những thuộc tính chung này được dẫn xuất từ toàn bộ
tập các điểm.
1.2. Phân cụm cho dữ liệu gene microarray
1.2.1. Giới thiệu công nghệ DNA microarray
Khái niệm công nghệ DNA microaray
Công nghệ microarray là công nghệ “highthroughput” (“highthroughput là những
thí nghiệm sử dụng những phương pháp nghiên cứu về bộ di truyền, protein, quá trình
sao chép, chuyển hóa) để xác định những genes một loại tế bào hay 1 cơ quan. Việc đo
mức độ mô tả của gene trong những điều kiện biến đổi cung cấp cho các nhà sinh học
hiểu rõ hơn về chức năng của gene và có những ứng dụng rộng rãi trong lĩnh vực khoa
học.
Ví dụ, microarrays cho phép so sánh mô tả gene giữa những tế bào ung thư và tế
bào thường.
Công nghệ này còn được biết với các tên như: DNA microarrays, DNA arrays,
DNA chips, và gene chips.
1.2.2. Thí nghiệm microarray
Về cơ bản, thí nghiệm với microarray gồm 4 bước:
Chuẩn bị microarray.
Chuẩn bị mẫu, tiến hành lai.
Phân tích thông tin mức thấp
Phân tích dữ liệu mức cao.
Bước 1: Chuẩn bị microarray
Có rất nhiều phương pháp để sản xuất microarray khác nhau. Thông thường
những microarrays được chuẩn bị trên một tấm nền bằng kính, ni lông hoặc thạch anh.
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
10
Bước quan trọng trong tiến trình này đó là việc lựa chọn những chuỗi DNA để đặt lên
bào đó. Sau đó người nghiên cứu sẽ gán nhãn chó mỗi RNA thông tin bằng thuốc
nhuộm huỳnh quang thường sử dụng thuốc nhuộm huỳnh quang Cy3 và Cy5. RNA
thông tin mà có mặt trong tế bào này , sau đó sẽ được lai với những DNA bổ xung của
nó trên microarray. [15] Xem hình 2. Sau khi thực hiện việc lai hóa một số mRNA có
thể được bao trong một spot khi nó tạo thành những cặp cơ sở (base pair) với cDNA
trên microarray. Một số không được bao trong spot.
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
11
Hình 1: Thí nghiệm microarray
Bước 3: Phân tích dữ liệu mức thấp-Quá trình lượng hóa hình ảnh
Sau quá trình lai hoá, nhà nghiên cứu gạt đi những mRNA không được bao trong
một spot phải sử dụng một máy quét đặc biệt để dò tìm những mRNA nào được bao
trong một spot bằng cách đo tỉ lệ huỳnh quang trên microarray. Điều này thực hiện
được là do thuốc nhuộm huỳnh quang được gán cho mỗi mRNA giúp cho số lượng
mẫu được bao trong một spot được đo bởi mức độ huỳnh quang phát ra khi được kích
thích bởi máy laser.[15]
Kết quả của thí nghiệm microarray được biểu diễn như một vector, mỗi thành
phần là một spot. Giá trị của 1 thành phần của vector là tỉ lệ của “độ dư” RNA thông
tin được đánh giá trong 2 mẫu. Với mỗi spot cho trước, nếu RNA thông tin từ mẫu mà
được gán nhãn sử dụng Cy3 có “độ dư” thì spot đó sẽ chuyển thành mầu xanh. Nếu
RNA thông tin từ mẫu mà được gán nhãn sử dụng Cy5 có “độ dư” thì spot đó sẽ
Bước 4: Phân tích dữ liệu mức cao
Phân tích các tập dữ gene microarray lớn là một lĩnh vực mới mà cũng có một
vài thách thức hay khóa khăn riêng của nó. Những cách tiếp cận khai phá dữ liệu
thông thường được chia làm 2 loại: “supervised” và “unsupervised”.
Phân tích có giám sát (supervised)
Phân tích “supervised” sử dụng những thông tin thêm vào. Phân tích
“supervised” bao gồm việc chọn từ toàn bộ tập dữ liệu một tập ‘thử’ và một tập ‘kiểm
tra’ và cũng bao gồm chỉ thị của những bộ phân loại, những chỉ thị này sẽ gán những
mô tả gene cho những lớp đã được định nghĩa trước. Khi bộ phân loại đã thử trên tập
‘thử’ và đã kiểm tra trên tập ‘kiểm tra’, sau đó nó có thể được áp dụng cho dữ liệu
chưa được phân loại.[13]
Phân tích không có giám sát (unsupervised)
Việc phân tích theo cách này là phù hợp khi không có tri thức trước về dữ liệu.
Tiếp cận duy nhất có thể là để nghiên cứu sự tương đồng giữa những mẫu hay những
thí nghiệm khác nhau. Quá trình phân tích này được gọi là học không giám sát-
unsupervised learning vì không có câu trả lời mong muốn được biết cho bất kì gene
hay thí nghiệm nào. Quá trình phân tích chỉ nhóm những thực thể giống nhau cùng
nhau. Việc phân tích có thể được làm trên gene, các điểm thời gian, các mẫu, trong các
chuỗi thời gian. Giải thuật phân cụm sẽ xem tất cả dữ liệu đầu vào nhưg là tập n số hay
vector n-chiều.[14]
Các phương pháp phân cụm Hierarchical, K-means, SOM là ví dụ điển hình của
việc phân tích dữ liệu gene microarray sử dụng cách tiếp cận phân cụm
“unsupervised”.
Vậy phân cụm cho dữ liệu gene microarray chính là phân tích “unsupervised”.
Việc phân cụm này sẽ nhóm những gene hay những thí nghiệm có mô tả tương đồng
cùng nhau.
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
13
giá trị đó
Lợi thế: Những mô tả trong logarit –log là dễ làm việc hơn những mô tả chính
quy.
2.1.2. Vector mô tả
Mô tả của 1 gene có thể được biểu diễn thông qua hàng loạt những thí nghiệm
khác nhau. Dãy những giá trị này được biến đến là vector mô tả gene.[2]
Hình 3: Ví dụ về vector mô tả gene trong log
2.1.3. Ma trận mô tả gene
Do chúng ta có thể nghiên cứu hàng nghìn gene trong hàng loạt những thí
nghiệm ở những điều kiện khác nhau. Kết quả là dữ liệu gene microarray tạo ra có thể
được biểu diễn như ma trận mô tả gene.[2]
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
15Hình 4: Ví dụ về ma trận mô tả gene
2.1.4. Khoảng cách hay sự tương đồng
Khi ta thực hiện phân cụm cho những thực thể biểu diễn trong tập dữ liệu gene
microarray tức là nhóm những thực thể mà tương đồng lại với nhau vì vậy chúng ta
cần đo tính tương đồng hay ngược lại là đo khoảng cách của các thực thể đó. Tức là ta
sẽ cần đo khoảng cách của các vector mô tả của các thực thể đó.
Việc phân cụm sẽ phụ thuộc vào ma trận khoảng cách được lựa chọn
Ma trận khoảng cách (Distance Matrix)
: Một số phương pháp đo khoảng
cách giữa 2 vector mô tả gene.
Trong trường hợp này ta giả định mean của các x là 0.
Cluster còn cung cấp 2 ma trận tương đồng là trị tuyệt đối của 2 hàm tương quan
trong 2 công thức trên là Absolute Correlation(Centered) và Absolute
Correlation(Uncentered) 2 ma trận này xem 2 đối tượng có những mẫu mô tả đối lập
nhau là giống nhau; Hệ số tương quan Pearson xem những gene đối lập nhau là rất
cách xa nhau.
Đo khoảng cách Non-parametric[8]
Spearman rank correlation và Kendall’s τ là 2 ma trận mà dựa trên hệ số tương
quan của Pearson.
Spearman rank correlation áp dụng trên 2 vector dữ liệu mà là hạng của những
giá trị dữ liệu trong 2 vector này.
Ví dụ: cho 2 vector:
x={2.3, 6.7. 4.5, 20.8} và y={2.1, 5.9, 4.4, 4.2} ta tính được r=0.2344
ta sẽ tính trên tập các hạng của 2 vector này là:
x={1, 3,2, 4} và y={1,4,3,2} thì ta tính được r
spearman
=0.4.
Tương quan Spearman được sử dụng như một thống kê kiểm tra cho sự độc lập
giữa x và y.
Kendall’s τ thì sử dụng quan hệ về thứ tự của x và y để tính sự tương quan. Nó
xem xét 2 vector dữ liệu (2 gene) như cặp những điểm (x
i
, y
i
) và (x
j
, y
j
) và chúng ta
i
> x
j
và y
i
< y
j
Ta có thể biểu diễn ví dụ bởi bảng:
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
17Từ bảng ta tính được số cặp phù hợp n
c
=4 và số cặp không phù hợp n
d
=2.
Từ đó ta tính Kendall’s τ theo công thức: τ=2(n
c
- n
d
)
/ n(n-1) trong trường hợp
này τ=0.33. Chúng ta cũng có thể sử dụng tương quan Kendall’s để kiểm tra sự độc
lập giữa x và y.
Đo khoảng cách dựa trên khoảng cách Euclidean[8]
Theo công thức:
o Bước 2: Hợp nhất 2 cụm được lựa chọn để tạo ra những cụm mới mà ban
đầu chứa ít nhất 2 đối tượng. Tính toán khoảng cách của tất cả những cụm mới
và những cụm khác.
o Bước 3
: Lặp lại bước 1 và 2 cho đến khi chỉ còn một cụm.
o Bước 4
: Vẽ một cây trình diễn kết quả.
o Bước 5: Trong khi khởi tạo cấu trúc, ta phải quyết định những cụm nào
lên được nối. Khoảng cách hay tính tương đồng giữa những cụm phải được
tính. Những quy tắc mà quản lý việc tính toán này là những phương pháp liên
kết-Linkage Methods.
Có 4 phương pháp liên kết phổ biến là:[8]
Centroid Linkage
Một vector được gán cho mỗi đối tượng giả (hay mỗi cụm-bao gồm một hay
nhiều đối tượng thật ) vector này sẽ được sử dụng để tính toán khoảng cách của đối
tượng giả này với tất cả những đối tượng còn lại hoặc đối tượng giả sử dụng ma trận
tương đồng được sử dụng để tính toán ma trận tương đồng ban đầu. Vector này là
trung bình của tất cả những vector của những đối tượng thực sự (đối tượng ở đây là
gene hay arrays) chứa trong đối tượng giả. Trong phương pháp này việc tính trung
bình của những vector bên trong sẽ bỏ qua những giá trị missing values, vì vậy vector
của đối tượng giả chỉ chứa missing value nêu tất cả những đối tượng trong nó chứa giá
trị missing value ở cột hay hàng tương ứng.
Single Linkage: Khoảng cách giữa 2 đối tượng(cụm) x, y là khoảng cách nhỏ
nhất giữa những phần tử của x với những phần tử của y.
Ví dụ: xét 2 tập đối tượng x bao gồm các phần tử xi i=1-n, y bao gồm các phần tử
ỵ j=1-m thì:
Dxy=min(d(xi,yj)) for all i = 1 to n and j = 1 to m.
o Không cần xác định tham số đầu vào (ví dụ số cụm như trong K-means)
Nhược điểm
o Không hiệu quả với tập dữ liệu lớn
o Không làm việc tốt với tập dữ liệu có dữ liệu khuyết.
o
Nhậy cảm với những “điểm kỳ dị” hay “outlier”.
2.2.2. K-Means Clustering (KMC)
Giải thuật này là giải thuật đươc sử dụng rộng rãi bởi vì việc cài đặt của giải
thuật này khá đơn giản. Giải thuật này yêu cầu đầu vào là số cụm k cận được định
trước bởi người dùng.[2]
Giải thuật
:
o Bước 1: Xác định trước số cụm k- number of clusters(k)
o Bước 2:
Gán ngẫu nhiên các gene tới những cụm này.
o Bước 3: Tính toán mean or median của những cụm khởi tạo.
o Bước 4: Lựa chọn một gene và di chuyển nó tới cụm mà giá trị của gene gần
với mean của cụm đó nhất.
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
20
o Bước 5: Nếu gene được di chuyển sang cụm mới, tính toán lại mean cho các
cụm.
o Bước 6:
Lặp lại bước 4,5 cho tới khi các gene không thể di chuyển được nữa
hay số bước lặp được xác định trước bởi người sử dụng(number of runs) đã
hết.
Chú ý k-means
Giải thuật:
Khởi tạo các nodes ở những vị trí ngẫu nhiên trong lưới 2 chiều rồi lặp lại các
bước sau:
o Chọn ngẫu nhiên một điểm dữ liệu ( gene) ta gọi điểm dữ liệu này là x.
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
21
o Di chuyển những nodes về phía x, những nodes mà gần x nhất
o Giảm số lần di chuyển qua số lần lặp(số lần lặp thường là một tham số
mà người dùng xác định khi sử dụng ứng dụng của giải thuật).
Ưu nhược điểm của giải thuật phân cụm SOM
o Ổn định với cả tập dữ liệu lớn
Nhược điểm:
o Thời gian chay chậm hơn K-means
o Phải xác định trước 2 tham số của “lưới”.
o Không làm việc tốt với tập dữ liệu có dữ liệu khuyết (missing data)
2.2.4. Principal Components Analysis-(PCA)
Được so sánh với giải thuật kmeans, PAM có những đặc tính sau:
Nó hoạt động dựa trên ma trận không tương đồng của tập dữ liệu cho trước.
Nó tối giản tổng khoảng cách không tương đồng thay vì tổng khoảng cách
Euclidean.
Nó cung cấp một hiển thị đồ họa, cho phép người dùng chọn số những cụm tối
ưu.
Giải thuật PAM đầu tiên tính k đối tượng đại diện, được gọi là các medoids. Một
medoid được định nghĩa là đối tượng của một cụm, mà tính không tương đồng trung
bình của nó tới các đối tượng trong cụm là nhỏ nhất. Sau khi tìm được tập các
medoids, mỗi đối tượng của tập dữ liệu được gán tới medoid gần nhất. Ví dụ, đối
tượng i được đặt vào cụm v khi medoid m
2.3. Phương pháp phân cụm intra-cluster
Qua quá trình tìm hiểu các phương pháp để khắc phục một số nhược điểm của 4
phương pháp phân cụm trên tôi đã tìm thấy một phương pháp đó là phương pháp phân
cụm dựa trên khoảng cách “intra-cluster” và tôi cũng đã quyết định tìm hiểu sâu hơn
để cài đặt phương pháp này trong ứng dụng phân cụm của mình.[1]
Phương pháp này xét dữ liệu mô tả gene được biểu diễn dưới dạng ma trận gồm
n hàng (tương ứng với các gene) và m cột (tương ứng với các thí nghiệm). Trong đó sử
dụng các ký hiệu:
G
i
biểu diễn gene thứ i với i=1,…,n.
E
j
biểu diễn thí nghiệm thứ j với j=1,…,m.
X
ij
biểu diễn giá trị mô tả gene của gene thứ i ở thí nghiệm j.
Tóm tắt giải thuật:
o Tính toán “giá trị ngưỡng”-“threshold” cho các cột (hay các thí nghiệm).
o Xem mỗi gene là một “trung tâm cụm”-“cluster-center”, “những thành viên
cụm”-“cluster-members” sẽ được tính dựa trên một giá trị mà ta đặt là
“count”(giá trị cao này sẽ được định nghĩa sau”.
o Cuối cùng, những cụm tốt nhất được xác định dựa trên sự giống nhau giữa
“những thành viên cụm” của một cụm.
Sau đây là ta sẽ đi chi tiết vào các bước trong giải thuật:
Tính giá trị “ngưỡng”-“threshold”:
o Đầu tiên tính giá trị “ngưỡng” của các cột trong ma trận dữ liệu,
o Tìm giá trị lớn nhất và nhỏ nhất của mỗi cột sau đó tính “độ lệch” của 2
giá trị này.
và G
2
. Việc làm trên được tiếp tục cho m-1 thí nghiệm còn lại. Nếu số “thí
nghiệm tương đồng” là lớn hơn 0.75 thì G
2
được coi là thành viên của cụm có
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
23
G
1
là “trung tâm cụm”. Tiếp theo, chúng ta tiếp tục với những gene tiếp theo,
trong trường hợp ví dụ này là G
1
và G
3
.
Sau khi hoàn thành việc so sánh giữa G
1
và tất cả những gene khác. Chúng
ta lập lại toàn bộ tiến trình trên cho n-1 gene còn lại mà lần lượt coi các gene là
“trung tâm cụm”.
Những cụm với số lượng gene lớn nhất được chọn và ta tiếp tục thực hiện
bước tiếp theo của giải thuật.
Tính toán sự giống nhau giữa các thành viên của cụm:
Với mỗi cụm, tính toán khoảng cách Euclidean giữa 2 thành viên bất kỳ của
cụm:
D=
nhất.
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
Copyright: Tài liệu đại học ©