ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
--------------------------------

LƯU XUÂN VĂN

THUẬT TOÁN PHÂN CỤM ĐỒNG THỜI
VÀ ỨNG DỤNG

Chuyên ngành: Cơ sở toán cho tin học
Mã số: 60460110

LUẬN VĂN THẠC SĨ KHOA HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Nguyễn Thị Hồng Minh

Hà Nội - 2015


LỜI CAM ĐOAN

Tôi xin cam đoan đây là công trình nghiên cứu do chính tôi thực hiện.
Các số liệu, kết quả phân tích trong luận văn là hoàn toàn trung thực và chưa
từng được ai công bố trong bất kỳ công trình nghiên cứu nào trước đây.
Hà Nội, ngày 21 tháng 12 năm 2015
Tác giả

Lưu Xuân Văn


LỜI CẢM ƠN

1

Chương 1 - Tổng quan về phân cụm dữ liệu

3

1.1. Phân cụm dữ liệu

3

1.2. Ứng dụng và yêu cầu của thuật toán phân cụm dữ liệu

5

1.3. Các kiểu dữ liệu trong phân cụm

11

1.4. Phép đo độ tương tự và khoảng cách đối với các kiểu dữ liệu

14

1.5. Một số thuật toán phân cụm

21

Chương 2 - Phân cụm đồng thời

25



60

Chương 3 - Ứng dụng của phân cụm đồng thời

66

3.1. Ứng dụng của phân cụm đồng thời

66

3.2. Hoạt động thực nghiệm

68

Kết luận

78

Danh mục tài liệu tham khảo

80


DANH MỤC CÁC HÌNH

Nội dung
Hình 1.1. Ví dụ về phân cụm dữ liệu

Số trang

46

Hình 2.7. Ví dụ một ma trận con (bicluster) nhất quán hoàn hảo

47

Hình 2.8. Biểu đồ biểu diễn mức độ biểu hiện của gen theo từng

48

điều kiện
Hình 2.9. Ví dụ ma trận biểu hiện biến đổi logarit

49

Hình 2.10. Biểu đồ biểu diễn mức độ biểu hiện của gen theo từng

50

điều kiện (theo dữ liệu ma trận logarit)
Hình 2.11. Biểu đồ biểu hiện gien và giá trị MSR tương ứng

54

Hình 2.12. Minh họa hai vectơ nghịch đảo nhau

57

Hình 2.13. Ví dụ một ma trận nhị phân


71

& Church
Hình 3.6. Hình ảnh Bicluster 33x20 tìm thấy bởi thuật toán Cheng

72

& Church
Hình 3.7. Thời gian chạy của một số thuật toán phân cụm đồng

72

thời
Hình 3.8. Thực nghiệm thuật toán Cheng & Church với

74

Hình 3.9. Thực nghiệm thuật toán Cheng & Church với

75

Hình 3.10. Thực nghiệm thuật toán Cheng & Church với

76

Hình 3.11. Thực nghiệm thuật toán Cheng & Church với

76



toán này thường tìm cách nhóm các gene có sự biểu hiện phụ thuộc nhau trên
toàn bộ các điều kiện thí nghiệm. Tuy nhiên, trên thực tế các gene thường chỉ
thể hiện phụ thuộc với nhau trên một số điều kiện nào đó và độc lập với nhau
trong điều kiện khác. Điều này dẫn đến một hạn chế rất lớn của các thuật toán
clustering là không thể tìm ra được các gene chỉ thể hiện giống nhau trên một
số điều kiện thí nghiệm. Để khắc phục hạn chế này, các nhà khoa học đã đề
xuất một phương pháp phân cụm mới có tên là biclustering (hoặc coclustering). Các thuật toán biclustering sẽ tìm cách phân cụm đồng thời trên
các hàng (gene) và cột (condition) của ma trận dữ liệu biểu hiện gene nhằm
tìm ra các ma trận con thoả mãn một số tiêu chí đặt ra, từ đó có thể giúp
chúng ta hiểu thêm các tiến trình sinh học giữa các gene trong các cá thể.
Nhưng gần như tất cả các phương pháp tiếp cận đến nay là heuristic và không
đảm bảo để tìm giải pháp tối ưu.
Trong trường hợp dữ liệu biểu hiện gene theo chuỗi thời gian, thì các
mẫu sinh học thường được đo theo một thời điểm nhất định nhằm quan sát
các tiến trình sinh học xảy ra trong các cá thể. Vì vậy, việc tìm ra các mẫu có
thể hiện giống nhau trong một khoảng thời gian liên tục nào đó, có thể hình
dung như chúng vừa hoàn thành một tiến trình sinh học, hoặc một giai đoạn
chức năng sinh học nào đó. Việc phân tích trên dữ liệu thể hiện gene cho phép
hiểu được cơ chế điều khiển gene và tương tác giữa chúng. Các mẫu dữ liệu
này có thể coi như là một bicluster gồm các hàng và các cột trong ma trận.
Vì lý do đó, tác giả lựa chọn đề tài: “Thuật toán phân cụm đồng thời và
ứng dụng” là hướng nghiên cứu cho luận văn của mình.

1


Trong luận văn này, tác giả đặt mục tiêu như sau:
- Nghiên cứu những nội dung liên quan tới phân cụm dữ liệu, một số tư
tưởng và thuật toán cơ bản,....
- Nghiên cứu một số thuật toán phân cụm đồng thời đã được công bố.


1.1. Phân cụm dữ liệu
Khai phá dữ liệu (Data mining) là quá trình trích xuất các thông tin có
giá trị tiềm ẩn bên trong tập dữ liệu lớn được lưu trữ trong các cơ sở dữ liệu,
kho dữ liệu. Các nhà khoa học xác định:
“Phân cụm dữ liệu là một kỹ thuật trong khai phá dữ liệu, 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”.
Phân cụm là quá trình nhóm các điểm dữ liệu trong cơ sở dữ liệu thành
các cụm sao cho những điểm dữ liệu trong cùng một cụm có độ tương đồng lớn
và những điểm không cùng một cụm có sự tương đồng là rất nhỏ. Một cụm các
đối tượng dữ liệu có thể xem như là một nhóm trong nhiều ứng dụng, ví dụ: mô
hình về phân cụm các trường dựa trên tiêu chuẩn về thu nhập và số nợ. Cụm 1
là cụm những người thu nhập cao, số nợ nhiều. Cụm 2 gồm những người thu
nhập cao nhưng nợ ít. Cụm 3 gồm những đối tượng thu nhập ít nhưng nợ nhiều.

Cụm 1
Cụm 3
Nợ

Cụm 2

Thu nhập

Hình 1.1. Ví dụ về phân cụm dữ liệu

3


DANH MỤC TÀI LIỆU THAM KHẢO


6.

Demirtas, H. (2006), “A method for multivariate ordinal data
generation given marginal distributions and correlations”, Journal of
Statistical Computation and Simulation 76(11), 1017-1025.

7.

Dolnicar, S. (2002), “A review of data-driven market segmentation in
tourism”, Journal of Travel and Tourism Marketing 12 (1), 1 - 22.

8.

Dolnicar, S., S. Kaiser, K. Lazarevski, and F. Leisch (2011),
“Biclustering overcoming data dimensionality problems in market
segmentation”, Journal of Travel Research.

9.

Eran Segal, Ben Taskar, Audrey Gasch, Nir Friedman, and Daphne
Koller.

Rich

probabilistic

models

for


13.

Haixun Wang, Wei Wang, Jiong Yang, and Philip S. Yu. Clustering by
pattern similarity in large data sets. In Proceedings of the 2002 ACM
SIGMOD International Conference on Management of Data, pages
394–405, 2002.

14.

Hartigan, J. A. (1972), “Direct clustering of a data matrix”, Journal of
the American Statistical Association 67(337), 123-129.

15.

Jinze Liu and Wei Wang. Op-cluster: Clustering by tendency in high
dimensional space. In Proceedings of the 3rd IEEE International
Conference on Data Mining, pages 187–194, 2003.

16.

Kluger, Y., R. Basri, J. T. Chang, and M. Gerstein (2003), “Spectral
biclustering of microarray data: Coclustering genes and conditions”,
Genome Research 13, 703-716.

17.

Lazzeroni, L. and A. Owen (2002), “Plaid models for gene expression
data”, Statistica Sinica 12, 61-86.



methods

for

the

analysis

of

DNA

microarray

data. Technical report, Department of Health Research and Policy,
Department of Genetics and Department of Biochemestry, Stanford
University, 1999.
23.

Sheng, Q., Y. Moreau, and B. D. Moor (2003), “Biclustering
microarray data by Gibbs sampling”, Bioinformatics 19.

24.

Smith, W. R. (1956), “Product differentiation and market segmentation
as alternative marketing strategies”, The Journal of Marketing 21 (1),
pp. 3-8.

25.

motifs from gene expression data. In Proceedings of the Pacific
Symposium on Biocomputing, volume 8, pages 77–88, 2003.

30.

Williams, G. J. (2009, December), “Rattle: A data mining gui for r”,
The R Journal 1 (2), 45-55.

31.

Wikipedia, “Biclustering”, http://en.wikipedia.org/wiki/Biclustering.

83