Luận văn Nghiên cứu một số phương pháp phân cụm cho dữ liệu gene microarray

đời sống như: y học, sinh học, nông nghiệp, môi trường…. Việc phân cụm cho dữ liệu gene microarray giúp cho việc nhóm những gene dưới những điều kiện hay ở những mẫu khác nhau mà có “mô tả tương đồng” vào thành một nhóm. Điều này có ứng dụng quan trong trong y học đó là phân biệt các tế bào với nhau (tế bào bệnh với tế bào thường). Một ví dụ điển hình cho ứng dụng này là việc phân biệt những loại ung thư vú. Sử dụng việc phân tích dữ liệu microarray gene các nhà nghiên cứu có thể phân biệt được khối ung thư vú gây ra tính di truyền của bệnh và những khối ung thư vú mà không gây ra tính di truyền của bệnh. Ngoài ra, Với việc phân cụm cho dữ liệu microarray gene còn giúp các nhà nghiên cứu phát hiện ra những gene mới là những gene mà thường không thuộc vào cụm nào trong số các gene thí nghiệm đây là một phát hiện rất quan trọng trong sinh học. Generated by Foxit PDF Creator © Foxit Software For evaluation only. 14 Chương 2: Một số phương pháp phân cụm cho dữ liệu gene microarray Chương này trình bày về các phương pháp hay các giải thuật phân cụm sử dụng các tiếp cận phân cụm không có giám sát (unsupervised). Các phương pháp phân cụm sẽ được trình bày đó là: Hierarchical, K-means, SOM, PAM và một phương pháp phân cụm mới dựa trên khoảng cách “intra-cluster”. Trước tiên ta sẽ đi được giới thiệu về cơ sở toán học để nghiên cứu các phương pháp phân cụm này. 2.1. Cơ sở toán học 2.1.1. Biểu diễn dữ liệu gene microarraay Dữ liệu mô tả gene thường được biểu diễn dưới dạng số thập phân. Giá trị của dữ liệu mô tả gene có thể được biểu diễn thông qua logarit cơ số 2 của 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. 15 Hì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. Khoảng cách dựa trên tương quan Pearson[8] Ma trận tương đồng được sử dụng phổ biến nhất là dựa trên tương quan Pearson. Tương quan Pearson giữa hai tập dữ liệu X={x1, x2,…, xn} và Y={y1, y2,…, yn} được định nghĩa là: Với x tb là giá trung bình của những giá trị x, và σx là độ lệch chuẩn của những giá trị này. Công thức này được sử dụng nếu bạn lựa chọn tùy trọn Correlation(Centered) trong Cluster. Nếu bạn lựa chọn tùy trọn Correlation(Uncentered) thì công thức sau được sử dụng: Khoảng cách Tính tương đồng Generated by Foxit PDF Creator © Foxit Software For evaluation only. 16 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 rspearman=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 (xi, yi) và (xj, yj) và chúng ta gọi một cặp là phù hợp nếu: xi < xj và yi < yj hay xi > xj và yi > yj và là không phù hợp nếu: xi yj hay xi > xj và yi < yj Ta có thể biểu diễn ví dụ bởi bảng: Generated by Foxit PDF Creator © Foxit Software For evaluation only. 17 Từ bảng ta tính được số cặp phù hợp nc=4 và số cặp không phù hợp nd=2. Từ đó ta tính Kendall’s τ theo công thức: τ=2(nc- nd ) / 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: Khoảng cách City-block hay Manhattan[8] Là giống với khoảng cách Euclidean khoảng cách d được tính theo công thức: Chú ý: Với những dữ liệu x, y có giá trị missing value thì ta bỏ qua những giá trị này và chỉ tính hệ sô tương quan trên những giá trị có nghĩa. Tính toán ma trận khoảng cách là bước đầu tiên trong phân cụm hierachical với những ma trận tương quan thì khoảng cách d=1.0-corelation(hệ số tương quan). Việc tính toán này sẽ tốn thời gian ngoại trừ phân cụm single-linkage hierarchical vì có giải thuật với độ phức tạp tuyến tính. 2.2. Một số phương pháp phân cụm Khóa luận này sẽ giới thiệu 4 phương pháp phân cụm truyền thống là: phân cụm hierarchical, phân cụm K-means, SOM, và PAM 2.2.1. Phân cụm Hierarchical Là phương pháp phân cụm “ tích tụ” (agglomerative) nối những gene giống nhau vào cùng một nhóm. Tiến trình lặp tiếp tục với việc nối những nhóm kết quả dựa trên tính tương đồng của chúng cho đến khi các nhóm được được kết nối trong một cây cấu trúc.[2] Giải thuật: o Bước 1: Tính khoảng cách giữa các gene tạo thành ma trận khoảng cách (distance matrix). Tìm những khoảng cách nhỏ nhất. Nếu có một vài cặp có tính tương đồng như nhau, sử dụng quy tắc được xác định trước để quyết định lựa chọn cái nào. Generated by Foxit PDF Creator © Foxit Software For evaluation only. 18 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. Average Linkage: Khoảng cách giữa 2 đối tượng x, y là khoảng cách trung bình giữa những phần tử của x với những phần tử của y. DAB = 1/(nm) ∑∑( d(xi, yi) ) for all i = 1 to n and j = 1 to m. Complete Linkage: Khoảng cách giữa 2 đối tượng x, y là khoảng cách lớn 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=max(d(xi,yj)) for all i = 1 to n and j = 1 to m. Generated by Foxit PDF Creator © Foxit Software For evaluation only. 19 Hình 5: Mô tả những phương pháp linkage khác nhau Kết luận: Việc lựa chọn những phương pháp linkage nào để phân cụm có ảnh hưởng lớn đến độ phức tạp và hiệu năng của việc phân cụm. Single hay complete linkage yêu cầu ít tính toán hơn. Tuy nhiên single linkage thường tạo ra những cụm trải dài trông không đẹp mắt. Centroid và average linkage tạo ra những kết quả mà sự phù hợp về những cụm được tạo ra và biểu diễn cấu trúc của dữ liệu phù hợp hơn. Tuy nhiên những phương pháp này lại yêu cầu tính toán phức tạp hơn. Dựa trên kinh nghiệm trước nay, thì average và complete linkage là những phương pháp linkage được ưa chuộng hơn cả cho việc phân tích dữ liệu gene microarray. Ưu nhược điểm của giải thuật phân cụm Hierarchical o Kết quả phân cụm trực quan do được biểu diễn dưới dạng cây. 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 o k-means là tính mean của các đối tượng trong một cụm. Mean là trung bình trên tất cả các đối tượng trên một cụm cho mỗi chiều phân biệt. o Có một đề nghị rằng: Khi ta lựa chọn k-means ta lên sử dụng khoảng cách Euclidean. Là do sử dụng khoảng cách Euclidean sẽ có độ phức tạp tính toán thấp giúp cho K-means có thể áp dụng tốt cho những tập dữ liệu lớn. Ưu nhược điểm của giải thuật phân cụm K-means o Giải thuật phân cụm K-means là một trong những giải thuật đơn giản nhất và nhanh nhất. o Làm việc tốt với cả tập dữ liệu lớn. Nhược điểm o Kết quả của giải thuật phân cụm k-means có thể thay đổi theo các lần chạy bởi vì việc khởi tạo những cụm ban đầu là ngẫu nhiên. Kết quả là những người nghiên cứu phải đánh giá chất lượng của những kiểu cụm đạt được. Vì vậy mà phương pháp này thường kết thúc ở giải pháp tối ưu “cục bộ”. o Số cụm k phải được xác định trước bởi người dùng. o Nhậy cảm với những “điểm kỳ dị” (“outliers”) (outliers là những điểm mà không phụ thuộc vào cụm nào) những outlier này có thể bóp méo centroid của cụm và phá hủy việc phân cụm. o Giải thuật làm việc không hiệu quả với những tập dữ liệu có “dữ liệu khuyết” hay “missing value”. 2.2.3. Self-Organizing Maps(SOMs) Giải thuật này phân các đối tượng thành k cụm (k do người dùng chọn) mỗi cụm (gồm nhiều gene) được xem như các node được sắp xếp trong lưới 2 chiều. Mỗi node tương ứng với một cụm[1] Việc làm này cho phép thể hiện sự giống nhau giữa các cụm. 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 mi gần hơn bất kỳ medoid mw khác: d(i, mi)<= d(i, mw) với w=1,…,k. Những đối tượng đại diện cần làm nhỏ nhất “hàm mục tiêu”, hàm đối tượng là tổng khoảng cách không tương đồng của tất cả những đối tượng tới medoid gần nhất của chúng. Giải thuật: Bước khởi tạo: Bước này lựa chọn tuần tự những đối tượng đại diện, được dùng như những medoids ban đầu. Bước tráo đổi: Nếu “hàm mục tiêu” có thể giảm bằng việc tráo đổi một đối tượng được lựa chọn với một đối tượng không được lựa chọn, thì việc tráo đổi được thực hiện. Việc làm này tiếp tục cho tới khi “hàm mục tiêu” không thể giảm được nữa. Ưu nhược điểm của thuật phân cụm PAM Ưu điểm : o PAM là hiệu quả cho việc phân tích những tập dữ liệu có nhiều biến đổi hay dữ liệu có nhiều “điểm kỳ dị”. Nhược điểm : Generated by Foxit PDF Creator © Foxit Software For evaluation only. 22 o Không làm việc tốt với tập dữ liệu có dữ liệu khuyết (missing data). o Không hiệu quả với tập dữ liệu lớn. 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: Gi biểu diễn gene thứ i với i=1,…,n. Ej biểu diễn thí nghiệm thứ j với j=1,…,m. Xij 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. o Giá trị “ngưỡng” được tính theo công thức sau: o Thj=0.05*{(Xij)max-(Xij)min} với i=1,….n (n là số gene hay số hàng trong ma trận dữ liệu) và j=1,…m (m là số “mẫu”hay “thí nghiệm” hay số cột trong ma trận dữ liệu). Xác định “những thành viên cụm” Tại mỗi thời điểm ta xem mỗi gene là một “trung tâm cụm”(“cluster- centre”) và xét xem trong số n-1 gene còn lại gene nào thuộc vào cụm của gene đang xét này. Ví dụ, xét gene số 1, đầu tiên chúng ta đưa ra độ lệnh vệ giá trị của thí nghiệm đầu tiên ứng với G1 và G2, và xem xét nó có lằm trong giá trị “ngưỡng” của thí nghiệm 1 hay không, tức là X11 –X12 <Th1 hay không. Nếu điều kiện đó thỏa mãn, thì E1 được cho là một “thí nghiệm tương đồng” với G1 và G2. 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ì G2 được coi là thành viên của cụm có Generated by Foxit PDF Creator © Foxit Software For evaluation only. 23 G1 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à G1 và G3. Sau khi hoàn thành việc so sánh giữa G1 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=  j bjaj XX 2)( với j=1,…,m; a và b là 2 thành viên của cụm. Việc này được thực hiện trên tất cả những cặp thành viên có thể của cụm đó. Tiếp theo, những khoảng cách này được cộng vào để đưa ra tổng khoảng cách của cụm đó: Tổng khoảng cách= k D với k là số thành viên của cụm. Cuối cùng chúng ta tính “trung bình” của “tổng khoảng cách” của cụm đó trên tổng số cặp gene mà chúng ta đã xét. “Trung bình” này được gọi là “ khoảng cách intra-cluster trung bình” của một cụm. Các cụm sẽ được sắp xếp theo thứ tự tăng dần của “khoảng cách intra- cluster trung bình”. Những cụm tốt nhất được chọn là những cụm mà có giá trị khoảng cách này nhỏ nhất. Ưu nhược điểm của giải thuật phân cụm dựa trên khoảng cách “intra- cluster” Ưu điểm: o Đơn giản để cài đặt. o Không phụ thuộc vào tham số đầu vào. o Giải thuật có khả năng đạt được tối ưu toàn cục cao. Nhược điểm: o Khó khăn khi những thành viên của cụm biến đổi và chọn những cụm nào là tốt nhất. Generated by Foxit PDF Creator © Foxit Software For evaluation only. 24 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 Hiện tại có rất nhiều phần mềm có chức năng phân cụm cho dữ liệu gene, một ví dụ điển hình cho một phần mềm có chức năng phân cụm cho dữ liệu gene mà sử dụng 4 phương pháp phân cụm: Hierarchical, Kmeans, SOM, PAM đó là “Cluster 3.0”i Như trong chương trước tôi đã trình bày về các phương pháp phân cụm, giải thuật của từng phương pháp và một số ưu nhược điểm của các phương pháp. Dựa vào việc nghiên cứu trong báo cáo này cũng như theo hướng phát triển của phần mềm phân cụm “Cluster 3.0” tôi đã xây dựng một chương trình có chức năng phân cụm cho dữ liệu gene microarray là “Gene Cluster” mà sẽ khắc phục một số nhược điểm của Cluster 3.0 ví dụ: Vấn đề chức năng: “Gene Cluster” có thêm chức năng “xử lý dữ liệu khuyết” mà sẽ giúp cho kết quả phân cụm được chính xác hơn. Ngoài ra, ứng dụng của “Gene Cluster” của tôi cũng cài đặt một phương pháp phân cụm mới dựa trên khoảng cách “intra-cluster” mà khắc phục được một số nhược điểm quan trọng của 4 phương pháp đã trình bày ở trên như: Cho kết quả tốt với cả tập dữ liệu có dữ liệu khuyết. Không cần phải xác định trước tham số đầu vào. 3.1. Phương pháp phân cụm Căn cứ vào những nghiên cứu trên tôi đã quyết định chọn phương pháp phân cụm k-means và “intra-cluster” để xây dựng phần mềm. 3.1.1. Lý do chọn K-means Lý do quan trọng nhất khi chọn giải thuật k-means đó là tính đơn giản của giải thuật vì vậy nó dễ dàng để cài đặt hơn. Ngoài ra giải thuật K-means cài hiệu quả với tập dữ liệu lớn. Thêm vào đó tôi cũng đã tìm hiểu một số phương pháp để khắc phục một số nhược điểm của phương pháp phân cụm k-means (tôi sẽ giới thiệu phần này ở phần tiếp theo) 3.1.2. Lý do chọn “intra-cluster” Như đã trình bày một số phương pháp phân cụm ở trên có một vài nhược điểm như phụ thuộc vào tham số đầu vào mà thường rất khó để xác định bởi người dùng, không làm việc hiệu quả với tập dữ liệu có dữ liệu “trội”, hay có lúc không đạt được tối ưu toàn cục…. Vì vậy tôi quyết định chọ một phương pháp phân cụm mới dựa vào khoảng cách “intra-cluster” mà giải quyết được một số lớn các nhược điểm của các giải thuật phân cụm đã nghiên cứu ngoài ra nó còn đơn giản để cài đặt.[6] i Cluster 3.0 là phần mềm có chức năng phân cụm cho dữ liệu microarray gene. Phận mềm này đầu tiên được phát triển bởi Michael Eisen, 1998. Phần mềm này cài đặt sử dụng 4 phương pháp phân cụm: Hierarchical, K- means, SOM và PAM.[8] Generated by Foxit PDF Creator © Foxit Software For evaluation only. 25 3.2. Một số phương pháp khắc phục nhược điểm của k-means 3.2.1. Lọc dữ liệu Lọc dữ liệu giúp cho việc loại bỏ những “điểm kỳ dị” trong tập dữ liệu ban đầu để cho ra một kết quả phân cụm đúng đắn hơn. Việc lọc dữ liệu được thực hiện tùy theo mục đích hay kết quả phân cụm mong muốn dựa theo một số tiêu chí như sau:[8] % Present >=X. Điều kiện này bỏ đi những gene mà có những giá trị missing values lớn hơn (100-X) phần trăm của những cột. SD (Gene Vector) >=X. Điều kiện này bỏ đi những gene mà có độ lệch chuẩn về giá trị nhỏ hơn X. At least X observations with abs(Val) >=Y. Điều kiện này bỏ đi những gene không có ít nhất X giá trị với giá trị tuyệt đối lớn hơn Y. MaxVal-MinVal >=X. 3.2.2. K-medians Để khắc phục việc dữ liệu có những đối tượng có “phần trội” thì thay vì tính “mean” trong giải thuật k-means ta sẽ tính median cho mỗi cụm. Median là median cho tất cả những đối tượng trên mỗi chiều. 3.2.3. Xữ lý dữ liệu khuyết: Những giá trị khuyết xảy ra vì một vài lý do khác nhau, bao gồm: độ phân giải không đủ, hỏng hình ảnh, hay đơn giản là bẩn hoặc những vết sước trên mặt kính. Chúng cũng có thể là do lỗi hệ thống của những phương pháp robot tạo ra chúng. Trong khóa luận này tôi sẽ trình bày 2 phương pháp xử lý dữ liệu khuyết phổ biến K người hàng xóm gần nhất (K nearest neighbor-KNN) Trung bình hàng (Row average) K người hàng xóm gần nhất (K nearest neighbor-KNN) Giải thuật: o Phương pháp dựa trên KNN chọn những gene với mô tả giống với gene mà ta quan tâm để xử lý giá trị khuyết. Nếu ta xét gene A có 1 giá trị khuyết trong thí nghiệm 1 phương pháp này sẽ tìm k gene mà có biểu diễn giá trị trong thí nghiệm 1 với mô tả giống với gene A nhất trong những thí nghiệm từ 2 đến N với N là tổng số thí nghiệm. Giá trị trung bình từ k gene gần nhất trong thí nghiệm 1 sau đó được sử dụng để tính giá trị khuyết cho gene A ở thí nghiệm 1. o Trong phương pháp này công thức để tính khoảng cách giữa các gene sử dụng khoảng cách Euclidean sẽ mang lại tính chính xác nhất. Có điều cần lưu ý việc sử dụng khoảng cách Euclidean thường nhậy cảm với “điểm kỳ dị”. Tuy Generated by Foxit PDF Creator © Foxit Software For evaluation only. 26 nhiên người ta cũng tìm được cách khắc phục phần trội này là sử dụng dịch chuyển dữ liệu sang không gian log.[10] Trung bình hàng Trung bình hàng giả sử rằng mô tả của gene trong 1 thí nghiệm là giống với mô tả của nó trong các thí nghiệm khác vì vậy xét trương hợp khi gene A có dữ liệu bị khuyết ở thí nghiệm một thì giá trị bị khuyết này sẽ được thay bằng giá trị trung bình của các biểu diễn giá trị của gene A trong các thí nghiệm từ 2 đến N. Tuy nhiên việc giả sử này thường không đúng vì vậy phương pháp tính trung bình hành thường không mang lại hiệu quả hay tính đúng đắn như phương pháp KNN.[11] 3.2.4. Tìm giải pháp tối ưu “toàn cục” Để tìm giải pháp tối ưu cho giải thuật phân cụm k-means thì người ta sử dụng thêm môt tham số đầu vào nữa là số lần chạy của giải thuật n. Mỗi lần chạy lại cụm khởi tạo sẽ khác nhau. Tổng khoảng cách của các đối tượng với “trung tâm” hay “center” của cụm là được lưu lại sau mỗi lần chạy lại và giải pháp với tổng này nhỏ nhất sẽ được trả về là giải pháp tối ưu nhất trong các lần chạy. [8] Chú ý: o Số lần chạy lại giải thuật n phụ thuộc vào số đối tượng trong tập dữ liệu ban đầu. o Nếu giải pháp tối ưu được tìm thấy nhiều lần thì việc còn một giải pháp tốt hơn giải pháp vừa tìm là rất hiếm. o Nếu giải pháp tối ưu chỉ được tìm thấy một lần thì có thể sẽ có giải pháp khác tốt hơn (tức có tổng khoảng cách bên trong cụm nhỏ hơn). 3.2.5. Việc xác định số cụm k Hiện tại vẫn chưa có phương pháp hiệu quả nào để xác định trước số cụm k. Tuy nhiên có một phương pháp hay được dùng là tùy theo tập dữ liệu mà chọn nhiều giá trị của k sau đó đánh giá kết quả phân cụm (dùng một giải thuật đánh giá) của những giá trị k khác nhau. Generated by Foxit PDF Creator © Foxit Software For evaluation only. 27 Chương 4: Phát triển ứng dụng cho bài toán phân cụm dữ liệu gene microarray Trong những chương trước tôi đã trình bày về vấn đề phân cụm cho dữ liệu gene microarray, các phương pháp phân cụm cho dữ liệu gene microarray và hướng giải quyết cho bài toán phân cụm. Như đã trình bày, tôi sẽ chọn phương pháp phân cụm k- means để cài đặt trong ứng dụng của mình. Trong chương này sẽ trình bày chi tiết về việc phát triển chương trình ứng dụng “Gene Cluster”. Ứng dụng “Gene Cluster” là chương trình mà tôi phát triển dựa trên mã nguồn mở của phần mềm “Cluster 3.0” trong đó tôi có một số cải tiến thêm về giao diện cũng như về chức năng. 4.1. Các chức năng của ứng dụng Đầu tiên ứng dụng này cho phép người dùng tải tập dữ liệu vào (tập dữ liệu vào này thường được lưu ở file text). Sau khi tải xong ta thu được tập dữ liệu mà được biểu diễn dưới dạng các ma trận hay mảng ví dụ như ma trận dữ liệu mô tả gene, mảng chứa tên gene, ma trận đánh dấu dữ liệu khuyết,…. Người dùng có thể chọn chức năng lọc dữ liệu (Filter Data) để lọc đi những dữ liệu theo các tiêu chí người dùng chọn. Dữ liệu sau khi được lọc có thể qua chức năng điều chỉnh (Adjust Data) để giúp người dùng điều chỉnh lại tập dữ liệu thu được cho dễ dàng cho việc thực hiện chức năng phân cụm tiếp theo. Tập dữ liệu sau khi thu được sẽ được dùng làm đầu vào cho chức năng phân cụm K-means và Intra-Cluster Distance. Người dùng có thể chọn chức năng lưu file để lưu lại tập dữ liệu hiện tại dưới dạng file text. 4.1.1.Mô hình tương tác giữa các module Generated by Foxit PDF Creator © Foxit Software For evaluation only. 28 Hình 6 : Sơ đồ DFD mô tả sự tương tác dữ liệu và chức năng. Các tập dữ liệu ở đây là tập dữ liệu thu được sau khi qua các chức năng bao gồm các ma trận mô tả gene, ma trận đánh dấu dữ liệu khuyết, mảng chứa định danh các gene, tên các gene và một số mảng phụ khác. Sau đây tôi sẽ giới thiệu chi tiết về các chức năng trong chương trình “Gene Cluster”. 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 Tải file và lưu file Bạn có thể tải dữ liệu cần phân tích bằng việc chọn biểu tượng load file trong menu File. Và lưu lại tập dữ liệu dưới dạng file text bằng cách click vào biểu tượng Save file trong menu file. Điều chỉnh dữ liệu 5 Tải dữ liệu sinh viên 1 Lọc dữ liệu 3 K-means 6 Xử lý dữ liệu khuyết 4 Lưu file 2 Tập dữ liệu 1 T ập dữ liệu 2 Tập dữ liệu 3 Tập dữ liệu 4 T ập dữ liệu 4 Tập dữ liệu 1 Tập dữ liệu 5 Tập dữ liệu 3 Tập dữ liệu 2 Kết quả phân cụm Kết quả Generated by Foxit PDF Creator © Foxit Software For evaluation only. 29 Hình 7: Giao diện cho menu của chương trình Biểu tượng “Load file”. Biểu tượng “Save file” File Loaded: Đường dẫn tuyệt đối của file được tải vào JobName: Mặc định là tên của tập dữ liệu tải vào Dataset has: rows: Số hàng của tập dữ liệu (hay số gene ). Columns: Số cột của tập dữ liệu (hay số thí nghiệm) Lọc dữ liệu Chức năng này cho phép bạn bỏ đi những gene mà không có những thuộc tính mông muốn từ tập dữ liệu đầu vào. Bạn có thể lọc những gene theo những thuộc tính sau: % Present >=X. Điều kiện này bỏ đi những gene mà có những giá trị missing values lớn hơn (100-X) phần trăm của những cột. SD (Gene Vector) >=X. Điều kiện này bỏ đi những gene mà có độ lệch chuẩn về giá trị nhỏ hơn X. At least X observations with abs(Val) >=Y. Điều kiện này bỏ đi những gene không có ít nhất X giá trị với giá trị tuyệt đối lớn hơn Y. MaxVal-MinVal >=X. Hình 8: Giao diện cho chức năng filter data Generated by Foxit PDF Creator © Foxit Software For evaluation only. 30 Điều chỉnh dữ liệu Chức năng này cho phép bạn thực hiện một số biến đổi trên dữ liệu đầu vào. Bao gồm: Log Transfom Data: Thay thế những giá trị của x bởi log2x. Điều này giúp thuận tiện hơn cho việc tính toán sau này. Center genes: Trừ giá trị của từng hàng cho giá trị [mean or median] của hàng đó. Sau đó ta sẽ thu được giá trị mean or median của từng hàng là 0. Center arrays: Trừ giá trị của từng hàng cho giá trị [mean or median] của hàng đó. Sau đó ta sẽ thu được giá trị mean or median của từng hàng là 0. Nomalize genes: Nhân tất cả những giá trị của mỗi hàng với S để tổng bình phương của mỗi hàng là 1. Nomalize arrays: Nhân tất cả những giá trị của mỗi cột với S để tổng bình phương của mỗi cột là 1 Hình 9: Giao diện minh hoa cho chức năng adjust data. Xử lý dữ liệu khuyết (Processing Missing Val) Chức năng này có tác dụng điền vào những giá trị mô tả bị khuyết của những gene những giá trị mà được tính thông qua 2 giải thuật: o K nearest neighbor (KNN) o Row average Mặc định dữ liệu bị khuyết được coi là có giá trị bằng 0. Generated by Foxit PDF Creator © Foxit Software For evaluation only. 31 Hình 10: Giao diên chức năng xử lý dữ liệu khuyết. 4.1.3. Phân cụm K-means Chức năng này thực hiện việc phân cụm cho dữ liệu microarray gene sử dụng giải thuật K-means (như đã trình bày ở các chương trước), Việc phân cụm này được kỳ vọng là cho kết quả tốt hơn Cluster 3.0 vì nó có thêm chức năng xử lý dữ liệu khuyết. Hình sau đây là minh họa cho giao diện chính của chương trình “Gene Cluster”. Generated by Foxit PDF Creator © Foxit Software For evaluation only. 32 Hình 11: Giao diện chính của chương trình phân cụm “Gene Cluster” 4.3. Định dạng dữ liệu vào, ra. 4.3.1. Dữ liệu tải vào File dữ liệu tải vào thường là file text (file .txt). Còn dữ liệu trong file này nó giống như một ma trận gồm n hàng và m cột. Hình 12 : Mô tả định dạng dữ liệu tải vào. Ở đây, dữ liệu mầu xanh lá cây là định danh cho tên gene, những giá trị trống được gọi là “missing values”. Hàng mầu xanh ra trời là xác định điều kiện là thí Generated by Foxit PDF Creator © Foxit Software For evaluation only. 33 nghiệm trong ví dụ này là các nhãn thời gian khác nhau. Khi tải dữ liệu vào phần mềm sẽ chỉ ra số hàng và số cột tương ứng của dữ liệu vào. Thường thì n là số gene, còn m số thí nghiệm tiến hàng trên cùng một tập gene. 4.3.2. Định dạng dữ liệu ra Với chức năng “Save file” Dữ liệu ra là file dạng text có định dạng giống với dữ liệu tải vào. Với chức năng “K-means” Dữ liệu ra của giải thuật K-means được lưu dưới 2 file: File thứ nhất: Tên file: JobName_K_GKg_Aka.cdt. ‘JobName’: do người dùng đặt, ‘K’: là số cụm người dùng chọn trong chức năng K-means, ‘GKg’: nếu người dùng chọn phân cụm cho gene còn không thì là ‘Aka’. File này chứa dữ liệu mô tả gene được tổ chức theo cụm bằng việc sắp xếp lại những hàng và những cột tương ứng. Vì vậy dạng của file này cũng giống dạng của dữ liệu tải vào. File này sẽ được dùng là file dữ liệu vào-input cho phần mềm “TreeView”ii để hiển thị kết quả phân cụm của giải thuật phân cụm K-means. File thứ 2: Tên file: JobName_K_GKg.kgg. ‘JobName’: do người dùng đặt, ‘K’: là số cụm người dùng chọn trong chức năng K-means, ‘GKg’ và ‘kgg’: nếu người dùng chọn phân cụm cho gene còn không thì là ‘Aka’ và ‘kag’ tương ứng. File này chứa danh sách những gene hay mảng và những cụm mà chúng được gán cho. 4.4. Ngôn ngữ lập trình Chương trình của tôi được xây dựng bằng ngôn ngữ lập trình Java. Java là ngôn ngữ lập trình hướng đối tượng (tựa C++) do Sun Microsystem đưa ra vào giữa thập niên 90.Chương trình viết bằng ngôn ngữ lập trình java có thể chạy trên bất kỳ hệ thống nào có cài máy ảo java (Java Virtual Machine). 4.4.1. Một số ưu điểm của ngôn ngữ lập trình Java Độc lập nền: Độc lập nền là một trong những ưu điểm nổi bật nhất của Java. Một chương trình viết bằng ngôn ngữ Java có thể chạy trên nhiều máy tính có hệ điều hành khác nhau (Windows, Unix,Linux, …) miễn sao ở đó có cài đặt máy ảo java (Java Virtual Machine). Viết một lần chạy mọi nơi (write once run anywhere). ii Đây là phần mềm được phát triển để hiển thị một số kết quả phân cụm.[8] Generated by Foxit PDF Creator © Foxit Software For evaluation only. 34 Điều này là do chương trình biên dịch tạo ra mã byte (bytecodes) không phụ thuộc hệ thống máy sử dụng (bytecodes là tập hợp các câu lệnh tương tự như những lệnh mã máy (machine code), được tạo ra khi một chương trình Java được biên dịch) Hướng đối tượng: Hướng đối tượng trong Java tương tự như C++ nhưng Java là một ngôn ngữ lập trình hướng đối tượng hoàn toàn. Tất cả mọi thứ đề cập đến trong Java đều liên quan đến các đối tượng được định nghĩa trước, thậm chí hàm chính của một chương trình viết bằng Java (đó là hàm main) cũng phải đặt bên trong một lớp. Hướng đối tượng trong Java không có tính đa kế thừa (multi inheritance) như trong C++ mà thay vào đó Java đưa ra khái niệm interface để hỗ trợ tính đa kế thừa. Đa nhiệm - đa luồng (MultiTasking - Multithreading): Java hỗ trợ lập trình đa nhiệm, đa luồng cho phép nhiều tiến trình, tiểu trình có thể chạy song song cùng một thời điểm và tương tác với nhau Hỗ trợ mạnh cho việc phát triển ứng dụng: Công nghệ Java phát triển mạnh mẽ nhờ vào “đại gia Sun Microsystem” cung cấp nhiều công cụ, thư viện lập trình phong phú hỗ trợ cho việc phát triển nhiều loại hình ứng dụng khác nhau cụ thể như: J2SE (Java 2 Standard Edition) hỗ trợ phát triển những ứng dụng đơn, ứng dụng client-server; J2EE (Java 2 Enterprise Edition) hỗ trợ phát triển các ứng dụng thương mại, J2ME (Java 2 Micro Edition) hỗ trợ phát triển các ứng dụng trên các thiết bị di động, không dây, … Hình 13: Mô hình thực thi của một chương trình bằng Javaiii. iii Nguồn Hoàng Bảo Duy. Từ File nguồn .java T rình biên dịch java. T rìn h thô ng d ịch jav a. Formatted: Font: 13 pt, Bold, Font color: Red Formatted: Font: 14 pt, Font color: Red Formatted: Font: 13 pt Generated by Foxit PDF Creator © Foxit Software For evaluation only. 35 4.5. Môi trường phát triển ứng dụng Chương trình “Gene Cluster” của tôi được phát triển trên môi trường NetBean IDE. NetBean IDE là môi trường phát triển-một công cụ dành cho lập trình viên để viết, biên dịch, gỡ lỗi(debug) và triển khai(deploy) chương trinh. Chương trình được viết bằng Java nhưng có thể hỗ trợ bất kỳ ngôn ngữ lập trình nào. NetBean IDE là lựa chọn tốt để viết Java. Phiên bản mới nhất là NetBean IDE 6.9. Ứng dụng của tôi cài đặt trên NetBean IDE 6.8 có thể tải về và cài đặt miễn phí tại địa chỉ: version=6.8 Lưu ý: Nếu bạn tải chương trình theo địa chỉ ở trên thì nó đã bao gồm cả JDK, trong trường hợp bạn đã cài JDK thì không cần cài JDK nữa, chỉ cần bấm “next” để cài NetBean IDE. Generated by Foxit PDF Creator © Foxit Software For evaluation only. 36 Chương 5: Thực nghiệm và đánh giá Trong những chương trước tôi đã giới thiệu cho các bạn những khái niệm cơ bản cho bài toán phân cụm cho dữ liệu microarray gene, các phương pháp phân cụm phổ biến và cũng đã đưa ra các ưu nhược điểm của từng phương pháp. Tôi cũng đã giới thiệu về việc cài đặt ứng dụng phân cụm và việc chọn phương pháp phân cụm K- means và phương pháp dựa trên khoảng cách “intra-distance” để cài đặt cho chương trình phân cụm “Gene Cluster” của tôi. Chương này tôi sẽ đi trình bày về việc thực nghiệm và đánh giá kết quả phân cụm được thực hiện trên chương trình “Gene Cluster” của tôi và trên một phần mềm phân cụm khá là phổ biến “Cluster 3.0”(tải từ 5.1. Cài đặt ứng dụng “Gene Cluster” 5.1.1. Cài đặt ứng dụng Phần này sẽ giới thiệu cách cài đặt ứng dụng “Gene Cluster” trên WinXP : Ứng dụng chính “Gene Cluster” sẽ được đóng gói dưới dạng file .JAR cùng với một folder lib chứa thư viện mà cần dùng cho việc chạy ứng dụng và phân phối đến cho người dùng. Vì vậy để cài đặt ứng dụng người dùng cần làm 3 việc sau: 1. Tải file JA R và thư mục lib (chứa các thư viện mà tác giả đã dùng thêm cho việc chạy ứng dụng) đặt chúng trong cùng một thư mục. 2. Cài đặt jdk phiên bản 1.3 trở lên bấm vào cài đặt theo hướng dẫn. Bạn có thể download các phiên bản này tại java.sun.com/download. 3. Tải phần mềm TreeView từ rồi cài đặt theo hướng dẫn. 5.2. Thực nghiệm các phương pháp phân cụm Như đã được giới thiệu, “Cluster 3.0” là một chương trình có chức năng phân cụm cho dữ liệu gene microarray mà đã được xây dựng trước đây. Trong phần thực nghiệm này tôi sẽ thực nghiệm trên 2 chương trình phân cụm đó là “Cluster 3.0” và “Gene Cluster”. 5.2.1. Mô tả các tập dữ liệu thực nghiệm Bài báo cáo của tôi thực nghiệm trên 2 tập dữ liệu dataset1 (từ và dataset2 (từ Mô tả tập dữ liệu dataset1[9] Dữ liệu được thu thập dựa trên thí nghiệm sử dụng công nghệ DNA microarrays. Những mô tả của gene trong budding yeast Saccharomyces cerevisiae được nghiên cứu trong suốt chu kỳ phân chia tế bào giảm phân (mitotic cell division cycle) và chu kỳ dịch chuyển lưỡng sinh trưởng (diauxic shift), hình thành bào tử(sporulation), nhiệt độ và giảm nhiệt độ mạnh (temperature and reducing shocks) ie heat shock (he), Generated by Foxit PDF Creator © Foxit Software For evaluation only. 37 reducing shock (re), cold shock (co), chúng được xem như điều kiện thực hiện thí nghiệm. Dữ liệu biểu diễn như một ma trận mô tả gene với n=2467 hàng tương đương với 2467 gene và m=79 cột tương đương với 79 thí nghiệm. Dữ liệu có dạng như sau: Mô tả tập dữ liệu dataset2[5] Dữ liệu mô tả gene trong dataset2 lấy từ thí nghiệm sử dụng 40 mẫu B-DLCL và 13412 gene đã được biết đến và chưa được biết. B-DLCL (B cell diffuse large cell lymphoma) là loại tế bào lym phô phổ biển nhất trong lym phô của con người. Lyphoma là một loại bệnh có tên u lym phô hay ung thư hạch. Có 2 dạng phân biệt của B-DLCL thường được sử dụng đến là: germinal center B cell-like DLCL và activated B cell-like. Những bệnh nhân mang 2 dạng này được thấy có những chuẩn đoán khác nhau: Những bệnh nhân mang germinal center B cell-like DLCL có khả năng sống hơn là những bệnh nhân mang activated B cell- like DLCL. Bản thân của thí nghiệm này được sử dụng để phân cụm các mẫu DLCL trên cùng một gene. Dữ liệu có dạng như sau: 5.2.2. Thực nghiệm trên “Cluster 3.0” và “Gene Cluster” Giới thiệu về phần mềm phân cụm Cluster 3.0 Phiên bản đầu tiên của phần mềm Cluster được viết bởi Michael Eisen khi ông đang làm việc ở trường đại học Stanford. Cluster 3.0 được viết bởi Michiel de Hoon cùng với Seiya Imoto và Satoru Miyano của trường đại học Tokyo và Human Genome Center và tháng 7 năm 2002. Các phiên bản của phần mềm có thể download tại địa chỉ: Cluster 3.0 và Tree View là những chương trình cung cấp một môi trường tính toán và môi trường đồ họa cho việc phân tích dữ liệu từ những thí nghiệm DNA hay tập dữ liệu thuộc về gene khác. Cluster có thể tổ chức và phân tích dữ liều theo nhiều cách khác nhau. TreeView cho phép dữ liệu đã được tổ chức được trực quan hóa. Bạn có thể tải và cài đặt miễn phí phần mềm Treeview này tại địa chỉ: Generated by Foxit PDF Creator © Foxit Software For evaluation only. 38 Các thực nghiệm Các thực nghiệm tôi sẽ tiến hành trên 2 tập dữ liệu “dataset1” và “dataset2” trên 2 phần mềm đó là thực hiện phân cụm K-means cho tập dữ liệu “dataset1” với các tham số đầu vào chung. Cụ thể như sau: 1. Với tập dữ liệu “dataset1”: Tiến hành phân cụm trên gene có điều chỉnh dữ liệu và chọn những tham số chung cho K-means là: o Số lần chạy 100 o Phương pháp phân cụm là k-Means o Ma trận khoảng cách là “Euclidean distance”. Ta sẽ tiến hành 3 thực nghiệm sau: Một là: Thực hiện phân cụm K-means trên Cluster 3.0. Hai là: Thực hiện phân cụm K-means trên “Gene Cluster” không sử dụng chức năng xử lý dữ liệu khuyết. Ba là: Thực hiện phân cụm K-means trên “Gene Cluster” sử dụng chức năng xử lý dữ liệu khuyết. Với việc chọn 3 giá trị k (số cụm) ở 3 lần khác nhau là: Lần 1: Chọn số cụm k=10 Thực hiện 3 thực nghiệm trên. Lần 2: Chọn số cụm k=15 Thực hiện 3 thực nghiệm trên. Lần 3: Chọn số cụm k=20. Thực hiện 3 thực nghiệm trên. 2. Với tập dữ liệu “dataset2”: Với tập dữ liệu tôi sẽ thực hiện thực nghiệm “Lần 1” như với tập dữ liệu “dataset1”. 5.3. Kết quả và đánh giá 5.3.1. Kết quả Sau khi thực hiện các thực nghiệm trên tôi thu được các file kết quả của giải thuật K-means (các file này đã được mô tả trong chương 4). Tôi đã lưu trữ các file này vào một folder để thực hiện việc đánh giá sau. Sau đây là một vài hình ảnh hiển thị kết quả của các thí nghiệm bằng “TreeView”: Generated by Foxit PDF Creator © Foxit Software For evaluation only. 39 Hình 14: Hình ảnh phóng to của một số gene trong kết quả phân cụm K- means trên “Cluster 3.0” Hình 15: Hình ảnh phóng to của một số gene trong kết quả phân cụm K-means trên “Gene Cluster” không sử dụng chức năng sử lý dữ liệu khuyết. Generated by Foxit PDF Creator © Foxit Software For evaluation only. 40 Hình 15: Hình ảnh phóng to của một số gene trong kết quả phân cụm K-means trên “Gene Cluster” sử dụng chức năng sử lý dữ liệu khuyết. Thời gian chạy trên tập dữ liệu 1 “dataset1” Khởi tạo Phần mềm Lần 1: k=10, số lần lặp n=100. Lần 2: k=15, số lần lặp n=100. Lần 3: k=20, số lần lặp n=100. Trên “Cluster 3.0” 00’46 01’00 00’46 Trên“Gene Cluster” 01’24 01’50 02’17 Hình 16: Kết quả thời gian chạy Kmeans trên “dataset1” 5.3.2. Đánh giá Việc đánh giá kết quả của việc phân cụm có thể sử dụng một số phương pháp. Trong khóa luận này tôi giới thiệu 2 phương pháp. Phương pháp thứ nhất là dựa vào thời gian chạy của giải thuật. Phương pháp thứ 2 là phương pháp đánh giá kết quả của giải thuật phân cụm (các file dữ liệu kết quả) dựa trên 2 phép đo đó là: đo “chỉ số tương đồng sinh học”-“biological homogeneity index” (BHI) và đo “chỉ số ổn định sinh học”-“biological stability index” (BSI). Generated by Foxit PDF Creator © Foxit Software For evaluation only. 41 Phương pháp dựa trên thời gian Phương pháp này giúp đánh giá hiệu năng của giải thuật phân cụm và có thể được đánh giá thông qua thời gian chạy của giải thuật phân cụm. Nhìn thời gian chạy của giải thuật phân cụm ở hình 14 thì có thể thấy: Thời gian chạy của phần mềm “Cluster 3.0” là nhanh hơn và ổn định hơn (khi số cụm tăng) so với “Gene Cluster”. Nguyên nhân: Là do việc tối ưu hóa dữ liệu của tôi trong quá trình cài đặt phần mềm “Gene Cluster” còn chưa tốt. Tuy nhiên tôi kỳ vọng vào phần đánh giá chất lượng của các cụm kết quả hơn. Phương pháp đánh giá dựa trên các chỉ số “BSI” và “BHI” Với phương pháp này một giải thuật phân cụm được đánh giá là tốt khi nó có giá trị “BHI” và “BSI” cao.[16]. Tuy nhiên do chưa đủ điều kiện để thực hiện các phương pháp này nên ở đây tôi chỉ trình bày về ý tưởng và những kỳ vọng của tôi khi giới thiệu phương pháp đánh giá này. Thứ nhất là dựa trên phép đo chỉ số tương đồng sinh học (biological homogeneity index) (BHI). [16] Phép đo này sẽ độ tương đồng về mặt sinh học giữa các cụm là như thế nào. Phép đo này có thể được sử dụng để đánh giá hiệu năng của một giải thuật phân cụm hoặc đánh giá hiệu năng của nhiều giải thuật phân cụm mà áp dụng cho cùng một tập dữ liệu. Thứ hai là dựa trên phép đo chỉ số ổn định sinh học(biological stability index) (BSI). Với mỗi giải thuật phân cụm và một tập dữ liệu cho trước, phép đo này sẽ đo “tính nhất quán” của các kết quả phân cụm khi được áp dụng lặp đi lặp lại vài lần cho cùng một tập dữ liệu. [16] Những kỳ vọng của tôi khi sử dụng phương pháp đánh giá trên là tôi muốn tiến hành các so sánh: Với tập dữ liệu “dataset1” o So sánh sự khác nhau của kết quả phân cụm của 3 thực nghiệm ở lần 1. o So sánh sự khác nhau của kết quả phân cụm của 3 thực nghiệm ở lần 2. o So sánh sự khác nhau của kết quả phân cụm của 3 thực nghiệm ở lần 3. o So sánh kết quả phân cụm trên “Cluster 3.0” ở 3 lần. Để tìm ra số cụm nào là tốt nhất. o So sánh kết quả phân cụm của TN2 ở 3 lần. Để tìm ra số cụm nào là tốt nhất. Với tập dữ liệu “dataset2” o So sánh sự khác nhau của kết quả phân cụm của 3 thực nghiệm ở lần 1. Generated by Foxit PDF Creator © Foxit Software For evaluation only. 42 Tổng kết Trong khóa luận này tôi đã giới thiệu về công nghệ microarray một công nghệ mà sự xuật hiện của nó đã giúp cho việc giảm thời gian phân tích các chuỗi gene vì vậy tăng số lượng chuỗi được phân tích. Đặc biệt khóa luận này đã tập trung vào việc nghiên cứu 4 phương pháp phân cụm cho dữ liệu gene đó là Hiearchical, K-means, SOM và PAM đây là những phương pháp phân cụm truyền thống và được sử dụng khá là phổ biến trong các phần mềm phân cụm. Trong khóa luận này tôi đã chỉ ra ưu nhược điểm của 4 phương pháp phân cụm trên ví dụ như Hierarchical, K-means và SOM, PAM đều không hiệu quả với tập dữ liệu có dữ liệu khuyết, hay K-means phụ thuộc vào tham số đầu vào là số cụm k và SOM cũng phụ thuộc vào tham số đầu vào. Tuy nhiên cũng có những ưu điểm như K-means và SOM đều hiệu quả với tập dữ liệu lớn (do giải thuật có độ phức tạp thấp) và K-means đơn giản để cài đặt. Ngoài ra, Trong khóa luận này tôi cũng giới thiệu một phương pháp phân cụm mới dựa trên khoảng cách “intra-cluster” mà khắc phục nhược điểm của những phương pháp phân cụm trên là phụ thuộc vào tham số đầu vào. Trong khóa luận này tôi cũng đã trình bày về việc phát triển một ứng dụng có tên “Gene Cluster” sử dụng 2 phương pháp K-means và intra-cluster và tôi cũng đã cài đặt một một số phương pháp để khắc phục nhược điểm của K-means trên cơ sở lý thuyết đã nghiên cứu. Tuy nhiên ứng dụng này vẫn gặp một số nhược điểm đó là: Thời gian chạy của các chức năng: “Process Missing Val” và “K-means” còn chậm do vấn đề xử lý tập dữ liệu lớn của tôi chưa được tốt. Ngoài ra, phương pháp phân cụm mới “Intra-distance” cũng chưa hoạt động được tốt do tôi còn gặp 1 số vấn đề về xử lý giải thuật. Vì vậy, hướng phát triển tiếp theo cho ứng dụng là tôi muốn giải quyết 2 nhược điểm này của ứng dụng để đưa ra một ứng dụng phân cụm cho gene hoàn thiện hơn. Generated by Foxit PDF Creator © Foxit Software For evaluation only. 43 Tài liệu tham khảo [1] Anja von Heydebreck. Cluster analysis for microarray data. Tải từ [2] Alexander I. Saeed TIGR's TM4 Software Team Pathogen Functional Genomics Resource Center. Introduction to Microarray Data Analysis and MeV. The Institute for Genomic Research October 28, 2005. Từ jbpc.mbl.edu/GenomesCourse/media/200510280830-braisted.pdf [3] Hedenfalk. Gene-Expression Profiles in Hereditary Breast Cancer, 2001, issue of the New England Journal of Medicine, 244:539-548. Từ www.ncbi.nlm.nih.gov/pubmed/11207349. [4] Hong-min Wang, Wen-li Ma, Hai Huang, Wei-wei Xiao, Yan Wang and Wen-ling Zheng. DNA Microarray Probe Preparation by Gel Isolation Nested PCR. Từ [5] Izidore S. Lossos, Ash A. Alizadeh, Michael B. Eisen, Wing C. Chan, Patrick Brown, David Botstein, Louis M. Staudt, and Ronald Levy. Ongoing immunoglobulin somatic mutation in germinal center B cell-like but not in activated B cell-likediffuse large cell lymphomas, 2000. Từ www.pnas.org/cgi/doi/10.1073/pnas.180316097 [6] Kasturi Bhattacharjee, Soumyadeep Chatterjee, Amit Konar, R.Janarthanan. Novel Clustering Method for Gene Microarray Data Based on Intra-Cluster Distance. IEEE International Publication Date: 6-7 March 2009 .On page(s): 20 - 25 Location: Patiala Print ISBN: 978-1-4244-2927-1. [7] Li Qin, Luis Rueda, Adnan Ali and Alioune Ngom. Spot Detection and Image Segmentation in DNA Microarray. Từ [8] Michael Eisen. Manual “Cluster 3.0”. Updated in 2002 by Michiel de Hoon, University of Tokyo, Human Genome Center. Từ [9] Michael B. Eisen, Paul T. Spellman, Patrick O. Brown, và David Botstein. Cluster analysis and display of genome-wide expression patterns, 1998. [10] Nguyễn Xuân Hưng. Ứng dụng các kỹ thuật array trong lĩnh vực môi trường, từ [11] Olga Troyanskaya, Michael Cantor, Gavin Sherlock, Pat Brown, Trevor Hastie, Robert Tibshirani, David Botstein and Russ B. Altman. Missing value estimation methods for DNA Microarrays. Generated by Foxit PDF Creator © Foxit Software For evaluation only. 44 [12] Pang-Ning Tan, Michael Steinbach. Introduction to Data Mining. Addison-Wesley, 2002, tr. 490-495. [13] Pascale F. Macgregor and Jeremy A. Squire . Application of Microarrays to the Analysis of Gene Expression in Cancer, 2002. Từ [14] Prof. Abraham B. Korol. Microarray cluster analysis and applications. Institute of Evolution, University of Haifa, 2003. Từ www.science.co.il/enuka/Essays/Microarray-Review.pdf [15] DNA Microarray Technology. National Human Genome Research Institute, từ [16] Methods for evaluating clustering algorithms for gene expression data using a reference set of functional classes. Department of Bioinformatics and Biostatistics, University of Louisville, Louisville, KY 40202, USA. Tải từ . Generated by Foxit PDF Creator © Foxit Software For evaluation only.