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

Được sự cho phép của Khoa Toán-Cơ-Tin, Trường Đại học Khoa học
tự nhiên, ĐHQGHN và sự đồng ý của cô giáo hướng dẫn TS Nguyễn Thị
Hồng Minh, tác giả đã thực hiện đề tài nghiên cứu “Thuật toán phân cụm
đồng thời và ứng dụng”.
Để hoàn thành luận văn này, tác giả xin chân thành cảm ơn các thầy cô
giáo Bộ môn Tin học, Khoa Toán-Cơ-Tin đã tận tình hướng dẫn, giảng dạy và
tạo điều kiện trong suốt quá trình học tập, nghiên cứu và rèn luyện ở trường
Đại học Khoa học tự nhiên.
Tác giả xin tỏ lòng biết ơn sâu sắc đến cô giáo TS. Nguyễn Thị Hồng
Minh đã tận tình, chu đáo hướng dẫn, giúp đỡ, tạo mọi điều kiện thuận lợi cho
tác giả trong suốt quá trình nghiên cứu, thực hiện luận văn này.
Xin được chân thành cảm ơn các bạn bè đã luôn động viên, khích lệ
tinh thần để tác giả có đủ nghị lực hoàn thành luận văn này.
Mặc dù đã có nhiều cố gắng để thực hiện đề tài một cách hoàn chỉnh
nhất. Song do thời gian thực tế vừa công tác, vừa đi học cùng với những hạn
chế về kiến thức và kinh nghiệm nên không thể tránh khỏi thiếu sót nhất định
mà bản thân chưa thấy được, tác giả rất mong được sự góp ý của quý thầy, cô
giáo và các bạn đồng nghiệp để luận văn và những nghiên cứu tiếp theo được
hoàn chỉnh hơn.
Tác giả xin chân thành cảm ơn!


MỤC LỤC

Nội dung

Trang

Mở đầu


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


2.1. Vấn đề phân cụm đồng thời - Biclustering

25

2.2. Phân loại các khối kết quả của phân cụm đồng thời

29

2.3. Cấu trúc các khối kết quả của phân cụm đồng thời

31

2.4. Thuật toán phân cụm đồng thời

35

2.4.1. Tìm hiểu thuật toán phân cụm đồng thời theo từng loại

35

khối kết quả
2.4.2. Thuật toán của Hartigan

42

2.4.3. Thuật toán của Cheng & Church

45

2.4.4. Thuật toán Bimax


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

3

Hình 1.2. Mô hình cấu trúc dữ liệu lưới

10

Hình 2.1. Ví dụ phân cụm đồng thời

26

Hình 2.2. Minh họa ma trận dữ liệu

27

Hình 2.3. Phân loại các khối kết quả của phân cụm đồng thời -

30

Biclusters
Hình 2.4: Cấu trúc các khối kết quả của phân cụm đồng thời

31

Hình 2.5. Chuỗi các giai đoạn chia tách của thuật toán của

44

Hartigan
Hình 2.6. Ví dụ ma trận biểu hiện và một ma trận con là bicluster


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


62

Hình 2.14. Sắp xếp lại hàng và cột theo thuật toán Bimax

63

Hình 2.15. Các ma trận con tiếp tục được xử lý lặp theo thuật toán

64

Bimax
Hình 3.1. Ma trận dữ liệu đầu vào

69

Hình 3.2. Hình ảnh ma trận dữ liệu đầu vào được tô màu

70

Hình 3.3. Hình ảnh Bicluster 25x6 tìm thấy bởi thuật toán Bimax

70


Hình 3.4. Hình ảnh Bicluster 19x7 tìm thấy bởi thuật toán Bimax

71

Hình 3.5. Hình ảnh Bicluster 37x19 tìm thấy bởi thuật toán Cheng


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



DANH MỤC CÁC BẢNG

Nội dung

Số trang

Bảng 1.1. Bảng tham số

19

Bảng 2.1. Tổng hợp các thuật toán phân cụm đồng thời

42

Bảng 3.1. Tính toán chỉ số Jaccard một số kết quả phân cụm đồng

73

thời
Bảng 3.2. Tính toán giá trị phương sai một số thuật toán phân cụm
đồng thời

73


MỞ ĐẦU

Việc phân tích dữ liệu biểu hiện gene, mà cụ thể là phân nhóm các gene
có sự biểu hiện giống nhau trong từng thời điểm thành các nhóm (cluster)
được thực hiện bởi các thuật toán phân cụm (clustering methods). Các thuật

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ố.

- Ứng dụng một số thuật toán biclustering vào tập dữ liệu thực cụ thể,
phân tích và đánh giá các cụm bicluster thu được.
Để hướng tới mục tiêu trên, tác giả đã thu thập và tìm đọc các tài liệu,
tổng hợp các nội dung lý thuyết, thực hiện việc phân tích, nghiên cứu các
công trình của các nhà khoa học đã công bố trước đây theo từng bước:
- Nghiên cứu lý thuyết cơ bản về phân cụm dữ liệu
- Nghiên cứu thuật toán phân cụm đồng thời.
- Nghiên cứu dữ liệu biểu hiện gene, một số lĩnh vực, bài toán mà phân
cụm đồng thời đã được áp dụng.
- Áp dụng một số thuật toán phân cụm đồng thời (biclustering) trên bộ
dữ liệu thực để thực nghiệm và đối chứng.
Sau quá trình nghiên cứu, tác giả đã hoàn thành bản luận văn của mình,
nội dung luận văn được trình bày trong 3 chương như sau:
Chương 1: Tổng quan về phân cụm dữ liệu. Trong chương này trình
bày tổng quan về hoạt động phân cụm dữ liệu, một số phương pháp phân cụm
dữ liệu phổ biến như phân cụm phân hoạch, phân cụm phân cấp, phân cụm
dựa trên mật độ,...
Chương 2: Phân cụm đồng thời. Trong chương này trình bày về một số
loại hình, cấu trúc của các bicluster có thể tồn tại trong cơ sở dữ liệu, trình
bày một số thuật toán tìm kiếm các bicluster trong đó, tóm tắt một số kết
nghiên cứu các thuật toán này.
Chương 3: Ứng dụng của phân cụm đồng thời. Trong chương này trình
bày những ứng dụng thực tế đã từng thực hiện bởi các nghiên cứu trước đây.
Áp dụng thuật toán phân cụm đồng thời (biclustering) vào bộ dữ liệu thực,
xem xét, tìm hiểu các bicluster thu được.
2


CHƯƠNG 1
TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU


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


Quá trình phân cụm là quá trình tìm ra các đối tượng trong cơ sở dữ liệu

một cách tự động. Không giống như phân lớp (classification), phân cụm không
cần những thông tin được xác định trước. Nói cách khác, phân cụm là phương
pháp học từ quan sát (learning from obversation) hay còn gọi là học không giám
sát (unsupervised learning or automatic classfication) trong trí tuệ nhân tạo.
Phân cụm đặc biệt hiệu quả khi không biết về thông tin các cụm, hoặc khi ta
quan tâm tới các thuộc tính của cụm mà chưa biết hoặc biết rất ít về các thông
tin đó.
Đã có rất nhiều thuật toán cũng như hệ thống được phát triển cho bài
toán phân cụm trong cơ sở dữ liệu lớn. Sự phát triển của lĩnh vực này đã được
áp dụng vào nhiều lĩnh vực ứng dụng như xử lý ảnh, nhận dạng, đánh giá kinh
doanh... Sự đa dạng của thuật toán phân cụm là do sự khác nhau của những ứng
dụng thực tế cũng dẫn tới những yêu cầu về dữ liệu khác nhau và đòi hỏi những
thuật toán phân cụm khác nhau.
Một trong những câu hỏi lớn đặt ra trong bài toán phân cụm là đo độ
tương đồng không gian giữa các đối tượng dữ liệu (spatial similarity). Trong
dữ liệu không gian thì độ đo tương đồng được xem như sự quan hệ về vị trí
không gian giữa các đối tượng dữ liệu. Nói cách khác thì hai đối tượng dữ liệu
được gọi là tương đồng nếu “khoảng cách không gian” giữa chúng là nhỏ.
Một trong những phương pháp đo độ tương đồng giữa hai đối tượng là
bằng nghịch đảo của hàm không tương đồng (dissimilarity function). Hàm
không tương đồng là hàm dựa trên những thuộc tính không gian của các đối
tượng dữ liệu như: toạ độ của các đối tượng, độ cao của các đối tượng... Trong
nhiều trường hợp thì hàm không tương đồng được xem như là hàm khoảng cách
không gian giữa các đối tượng như hàm khoảng cách Euclid, hàm khoảng cách
Manhattan, hàm khoảng cách Minkowski,...
Bài toán phân cụm là quá trình nhóm một cơ sở dữ liệu thành những
nhóm đối tượng dữ liệu phục vụ cho mục đích cụ thể của từng ứng dụng thực
tế. Không có một thuật toán phân cụm nào là tốt nhất và thích hợp cho tất cả
4



mọi ứng dụng mà với mỗi ứng dụng khác nhau thì người sử dụng phải lựa chọn
ra một thuật toán phân cụm cụ thể thích ứng với ứng dụng đó. Kết quả đánh giá
cho từng thuật toán cũng phụ thuộc vào những yêu cầu của từng ứng dụng.
1.2. Ứng dụng và yêu cầu của thuật toán phân cụm dữ liệu
1.2.1. Ứng dụng của phân cụm dữ liệu
Phân cụm dữ liệu đã và đang được nghiên cứu, ứng dụng trong nhiều
lĩnh vực khác nhau ở các nước trên thế giới, tại Việt Nam kỹ thuật này tương
đối còn mới mẻ tuy nhiên cũng đang được nghiên cứu và dần đưa vào ứng dụng
tại nhiều lĩnh vực như:
- Quy hoạch đô thị: Nhận dạng các nhóm nhà theo kiểu và vị trí địa lí,...
nhằm cung cấp thông tin cho quy hoạch đô thị;
- Nghiên cứu trái đất: Phân cụm để theo dõi các tâm động đất nhằm cung
cấp thông tin cho nhận dạng các vùng nguy hiểm;
- Thương mại: Tìm kiếm nhóm các khách hàng quan trọng có đặc trưng
tương đồng từ các bản ghi mua bán trong cơ sở dữ liệu mua, bán hàng;
- Sinh học: Phân loại các gene với các chức năng tương đồng và thu được
các cấu trúc trong mẫu;
- Thư viện: Theo dõi người đọc, sách, dự đoán nhu cầu của độc giả..
- Bảo hiểm: Phân nhóm các đối tượng sử dụng bảo hiểm và các dịch vụ
tài chính, dự đoán xu hướng của khách hàng, phát hiện gian lận tài chính;
- Phân loại tài liệu, phân loại người dùng web...
1.2.2. Yêu cầu về thuật toán phân cụm dữ liệu
Theo các nghiên cứu cho thấy hiệ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ơ sở
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 diễn cấu
trúc của cơ sở dữ liệu, với mỗi cách thức biểu diễn khác nhau sẽ có tương ứng
thuật toán phân cụm phù hợp. Vì vậy, phân cụm dữ liệu vẫn đang là một vấn
đề khó và mở vì phải giải quyết nhiều vấn đề cơ bản một cách trọn vẹn và phù
hợp với nhiều dạng dữ liệu khác nhau, đặc biệt là với kho dữ liệu hỗn hợp đang

5


ngày càng tăng và đây cũng là một trong những thách thức lớn trong lĩnh vực
khai phá dữ liệu.
Vậy phân cụm dữ liệu là một thách thức trong lĩnh vực nghiên cứu, vì
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. Do đặc thù của của cơ sở dữ liệu là lớn, phức tạp, và
có dữ liệu nhiễu nên những thuật toán phân cụm được áp dụng phải thoả mãn
những yêu cầu sau:
- Thuật toán phải hiệu quả và thời gian chạy phải là tăng tuyến tính theo
kích thước của dữ liệu;
- Thuật toán phải xử lý và áp dụng được với cơ sở dữ liệu nhiều nhiễu,
phức tạp gồm cả dữ liệu không gian, phi không gian, dữ liệu số, phi số, kiểu
nhị phân, dữ liệu định danh, hạng mục, thích nghi với kiểu dữ liệu hỗn hợp.
- Thuật toán phải có khả năng xác định được những cụm với hình dáng
bất kỳ bao gồm cả những cụm có hình dạng lồng nhau, cụm có hình dạng lõm,
hình cầu, hình que...
- Tối thiểu lượng tri thức cần cho xác định các tham số đầu vào. Do các
giá trị đầu vào thường ảnh hưởng rất lớn đến thuật toán phân cụm và rất phức
tạp để xác định các giá trị vào thích hợp đối với các cơ sở dữ liệu lớn.
- Thuật toán phải thực hiện với mọi thứ tự đầu vào dữ liệu. Nói cách khác
kết quả của thuật toán nên độc lập với dữ liệu đầu vào (Cùng một tập dữ liệu,
khi đưa vào xử lý cho thuật toán phân cụm dữ liệu với các thứ tự vào của các
đối tượng dữ liệu ở các lần thực hiện khác nhau thì không ảnh hưởng lớn đến
kết quả phân cụm);
- Thuật toán không đòi hỏi những tri thức về cơ sở dữ liệu từ người dùng;
- Thuật toán phải làm việc được với cơ sở dữ liệu chứa nhiều lớp đối
tượng dữ liệu phức tạp và có tính chất khác nhau;
- Thuật toán phải thích nghi với dữ liệu đa chiều: Thuật toán có khả năng

áp dụng hiệu quả cho dữ liệu có số khác chiều nhau;

6


- Thuật toán phải dễ hiểu, dễ cài đặt và khả thi: Người sử dụng có thể
chờ đợi những kết quả phân cụm dễ hiểu, dễ lý giải và dễ sử dụng. Nghĩa là, sự
phân cụm có thể cần được giải thích ý nghĩa và ứng dụng rõ ràng. Việc nghiên
cứu cách để một ứng dụng đạt được mục tiêu rất quan trọng có thể gây ảnh
hưởng tới sự lựa chọn các phương pháp phân cụm.
1.2.3. Các hướng tiếp cận của bài toán phân cụm dữ liệu
Các kỹ thuật phân cụm có rất nhiều cách tiếp cận và ứng dụng trong thực
tế, nó hướng tới hai mục tiêu chung đó là chất lượng của các cụm khám phá
được và tốc độ thực hiện của thuật toán. Hiện nay, các kỹ thuật phân cụm có
thể phân loại theo các cách tiếp cận chính sau.
1.2.3.1. Phương pháp phân cụm phân hoạch
Phương pháp phân cụm phân hoạch nhằm phân một tập dữ liệu có n phần
tử cho trước thành k nhóm dữ liệu sao cho: mỗi phần tử dữ liệu chỉ thuộc về
một nhóm dữ liệu và mỗi nhóm dữ liệu có tối thiểu ít nhất một phần tử dữ liệu.
Các thuật toán phân hoạch dữ liệu có độ phức tạp rất lớn khi xác định nghiệm
tối ưu toàn cục cho vấn đề phân cụm dữ liệu, do nó phải tìm kiếm tất cả các
cách phân hoạch có thể được. Chính vì vậy, trên thực tế người ta thường đi tìm
giải pháp tối ưu cục bộ cho vấn đề này bằng cách sử dụng một hàm tiêu chuẩn
để đánh giá chất lượng của các cụm cũng như để hướng dẫn cho quá trình tìm
kiếm phân hoạch dữ liệu. Với chiến lược này, thông thường người thực hiện
bắt đầu khởi tạo một phân hoạch ban đầu cho tập dữ liệu theo phép ngẫu nhiên
hoặc theo heuristic và liên tục tinh chỉnh nó cho đến khi thu được một phân
hoạch mong muốn, thoả mãn ràng buộc cho trước. Các thuật toán phân cụm
phân hoạch cố gắng cải tiến tiêu chuẩn phân cụm, bằng cách tính các giá trị đo
độ tương tự giữa các đối tượng dữ liệu và sắp xếp các giá trị này, sau đó thuật

toán lựa chọn một giá trị trong dãy sắp xếp sao cho hàm tiêu chuẩn đạt giá trị
tối thiểu. Như vậy, ý tưởng chính của thuật toán phân cụm phân hoạch tối ưu
cục bộ là sử dụng chiến lược tham lam (Greedy) để tìm kiếm nghiệm. Một số
thuật toán phân cụm phân hoạch điển hình như K-means, PAM, CLARA,
CLARANS,....
7


1.2.3.2. Phương pháp phân cụm phân cấp
Phương pháp này xây dựng một phân cấp trên cơ sở các đối tượng dữ
liệu đang xem xét. Nghĩa là sắp xếp một tập dữ liệu đã cho thành một cấu trúc
có dạng hình cây, cây phân cấp này được xây dựng theo kỹ thuật đệ quy có hai
cách tiếp cận phổ biến của kỹ thuật này đó là:
- Hòa nhập nhóm (thường được gọi là tiếp cận Bottom-Up): Phương pháp
này bắt đầu với mỗi đối tượng được khởi tạo tương ứng vói các cụm riêng biệt,
sau đó tiến hành nhóm các đối tượng theo một độ đo tương tự (như khoảng cách
giữa hai trung tâm của hai nhóm), quá trình này được thực hiện cho đến khi tất
cả các nhóm được hòa nhập vào một nhóm (mức cao nhất của cây phân cấp)
hoặc cho đến khi các điều kiện kết thúc thỏa mãn. Như vậy, cách tiếp cận này
sử dụng chiến lược tham lam trong quá trình phân cụm.
- Phân chia nhóm (thường được gọi là tiếp cận Top-Down): Bắt đầu với
trạng thái là tất cả các đối tượng được xếp trong cùng một cụm. Mỗi vòng lặp
thành công, một cụm được tách thành các cụm nhỏ hơn theo giá trị của một
phép đo độ tương tự nào đó cho đến khi mỗi đối tượng là một cụm, hoặc cho
đến khi điều kiện dừng thỏa mãn. Cách tiếp cận này sử dụng chiến lược chia để
trị trong quá trình phân cụm.
Một số thuật toán phân cụm phân cấp điển hình như CURE, BIRCH,...
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ương 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 quan 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
phân cụm dữ liệu cổ điển, hiện nay đã có 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 khai phá dữ liệu.
1.2.3.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 độ
đượ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 đã xác định
8


thì nó tiếp tục được phát triển thêm các đối tượng 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 có thể phát hiện ra các cụm dữ liệu với hình thù bất kỳ.
Kỹ thuật này có thể khắc phục được các phân tử ngoại lai hoặc giá trị nhiễu rất
tốt, 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ó tác động rất lớn đến kết quả phân cụm dữ liệu. Một
số thuật toán phân cụm dữ liệu dựa trên mật độ điển hình như DBSCAN,
OPTICS,...
1.2.3.4. Phương pháp phân cụm dựa trên lưới
Kỹ thuật phân cụm dựa trên mật độ không thích hợp với dữ liệu nhiều
chiều, để giải quyết cho đòi hỏi này, người ta đã dử dụng phương pháp phân
cụm dựa trên lưới. Đây là phương pháp dựa trên cấu trúc dữ liệu lưới để phân
cụm dữ liệu, phương pháp này chủ yếu tập trung áp dụng cho lớp dữ liệu không
gian. Thí dụ như dữ liệu được biểu diễn dưới dạng cấu trúc hình học của đối
tượng trong không gian cùng với các quan hệ, các thuộc tính, các hoạt động của
chúng. Mục tiêu của phương pháp này là lượng hoá tập dữ liệu thành các ô
(cell), các cell này tạo thành cấu trúc dữ liệu lưới, sau đó các thao tác phân cụm
dữ liệu làm việc với các đối tượng trong từng cell này. Cách tiếp cận dựa trên
lưới này không di chuyển các đối tượng trong các cell mà xây dựng nhiều mức

phân cấp của nhóm các đối tượng trong một cell. Trong ngữ cảnh này, phương
pháp này gần giống với phương pháp phân cụm phân cấp nhưng chỉ có điều
chúng không trộn các cell. Do vậy các cụm không dựa trên độ đo khoảng cách
(hay còn gọi là độ đo tương tự đối với các dữ liệu không gian) mà nó được
quyết định bởi một tham số xác định trước. Ưu điểm của phương pháp phân
cụm dữ liệu dựa trên lưới là thời gian xử lý nhanh và độc lập vói số đối tượng
dữ liệu trong tập dữ liệu ban đầu, thay vào đó là chúng phụ thuộc vào số cell
trong mỗi chiều của không gian lưới. Một thí dụ về cấu trúc dữ liệu lưới chứa
các cell trong không gian như hình sau:
9


Hình 1.2. Mô hình cấu trúc dữ liệu lưới
Một số thuật toán phân cụm dữ liệu dựa trên cấu trúc lưới điển hình:
Sting, WaveCluster,...
1.2.3.5. Phương pháp phân cụm dựa trên mô hình
Phương pháp này cố gắng khám phá các phép xấp xỉ tốt của các tham số
mô hình sao cho khớp với dữ liệu một cách tốt nhất. Chúng có thể sử đụng
chiến lược phân cụm phân hoạch hoặc chiến lược phân cụm phân cấp, dựa trên
cấu trúc hoặc mô hình mà chúng giả định về tập dữ liệu và cách mà chúng tinh
chỉnh các mô hình này để nhận dạng ra các phân hoạch.
Phương pháp phân cụm dữ liệu dựa trên mô hình cố gắng khớp giữa dữ
liệu với mô hình toán học, nó dựa trên giả định rằng dữ liệu được tạo ra bằng
hỗn hợp phân phối xác suất cơ bản. Các thuật toán phân cụm dựa trên mô hình
có hai tiếp cận chính: mô hình thống kê và mạng Nơron. Phương pháp này gần
giống với phương pháp dựa trên mật độ, bởi vì chúng phát triển các cụm riêng
biệt nhằm cải tiến các mô hình đã được xác định trước đó, nhưng đôi khi nó
không bắt đầu với một số cụm cố định và không sử dụng cùng một khái niệm
mật độ cho các cụm.
1.2.3.6. Phương pháp phân cụm có dữ liệu ràng buộc

Sự phát triển của phân cụm dữ liệu không gian trên cơ sở dữ liệu lớn đã
cung cấp nhiều công cụ tiện lợi cho việc phân tích thông tin địa lí, tuy nhiên
hầu hết các thuật toán này cung cấp rất ít cách thức cho người dùng để xác định
các ràng buộc trong thế giới thực cần phải được thỏa mãn trong quá trình phân
10


cụm. Để phân cụm dữ liệu không gian hiệu quả hơn, các nghiên cứu bổ sung
cần được thực hiện để cung cấp cho người dùng khả năng kết hợp các ràng buộc
trong thuật toán phân cụm.
Hiện nay, các phương pháp phân cụm trên đã, đang được phát triển và
áp dụng nhiều trong các lĩnh vực khác nhau và đã có một số nhánh nghiên cứu
được phát triển trên cơ sở của các phương pháp đó như:
- Phân cụm thống kê: Dựa trên các khái niệm phân tích thống kê, nhánh
nghiên cứu này sử dụng các độ đo tương tự để phân hoạch các đối tượng, nhưng
chúng chỉ áp dụng cho các dữ liệu có thuộc tính số.
- Phân cụm mờ: Sử dụng kỹ thuật mờ để phân cụm dữ liệu, các thuật toán
thuộc loại này chia ra lược đồ phân cụm thích hợp với tất cả các hoạt động đời
sống hàng ngày, chúng chỉ xử lí các dữ liệu thực hiện không chắc chắn.
- Phân cụm mạng Kohonen: Loại phân cụm này dựa trên khái niệm của
các mạng Nơron. Mạng Kohonen có tầng Nơron vào và các tầng Nơron ra. Mỗi
Nơron của tầng vào tương ứng với mỗi thuộc tính của bản ghi, mỗi một Nơron
vào kết nối với tất cả các Nơron của tầng ra. Mỗi liên kết được gắn liền với một
trọng số nhằm xác định vị trí của Nơron ra tương ứng.
Các kỹ thuật phân cụm dữ liệu trình bày ở trên đã được sử dụng rộng rãi
trong thực tế, thế nhưng hầu hết chúng chỉ nhằm áp dụng cho tập dữ liệu với
cùng một kiểu thuộc tính. Vì vậy, việc phân cụm dữ liệu trên tập dữ liệu có kiểu
hỗn hợp là một vấn đề đặt ra trong khai phá dữ liệu trong giai đoạn hiện nay.

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

Trong phân cụm, các đối tượng dữ liệu thường được diễn tả dưới dạng
các đặc tính hay còn gọi là thuộc tính (Khái niệm “các kiểu dữ liệu” và “các
kiểu thuộc tính dữ liệu” được xem là tương đương với nhau). Các thuộc tính
này là các tham số để giải quyết vấn đề phân cụm và sự lựa chọn chúng có tác
động đáng kể đến kết quả phân cụm. Phân loại các kiểu thuộc tính khác nhau
là vấn đề cần giải quyết đối với hầu hết các tập dữ liệu nhằm cung cấp các
11


phương tiện thuận lợi để nhận dạng sự khác nhau của các phần tử dữ liệu. Các
thuật toán phân cụm thường sử dụng một trong hai cấu trúc dữ liệu sau:
- Ma trận dữ liệu (Data matrix): là mảng n hàng, p cột, trong đó p là số
thuộc tính của mỗi đối tượng. Mỗi hàng biểu diễn một đối tượng, các phần tử
trong mỗi hàng chỉ giá trị thuộc tính tương ứng của đối tượng đó. Mảng được
cho như sau:
𝑥11
…
𝑥𝑖1
…
[𝑥𝑛1

… 𝑥1𝑓
… …
… 𝑥1𝑓
… …
… 𝑥𝑛𝑓

…
…
…

…
…

𝑥1𝑝
…
𝑥1𝑝
…
𝑥𝑛𝑝 ]

- Ma trận phi tương tự (Dissimilarity matrix): là mảng n hàng, n cột.
Phần tử d(i,j) chứa khoảng cách hay độ khác biệt giữa các đối tượng i và đối
tượng j; d(i,j) là một số không âm, trong đó nếu d(i,j) xấp xỉ 0 thì hai đối tượng
i và j là khá “gần” nhau, nếu d(i,j) càng lớn thì hai đối tượng i, j khá khác nhau.
Do d(i,i) = d(j,j) = 0 nên ta có thể biểu diễn ma trận phi tương tự như sau:
0
𝑑(2,1)
0
𝑑(3,1) 𝑑(3,2)
…
…
[𝑑(𝑛, 1) 𝑑(𝑛, 2)

0
…
…

…
…

…

0]

Phần lớn các thuật toán phân cụm sử dụng cấu trúc ma trận phi tương tự.
Do vậy, nếu dữ liệu cần phân cụm được tổ chức dưới dạng ma trận dữ liệu thì
cần biến đổi về dạng ma trận phi tương tự trước khi tiến hành phân cụm.
Có hai đặc trưng để phân loại: kích thước miền và hệ đo.
Cho một CSDL D chứa n đối tượng trong không gian k chiều; X, Y, Z là
các đối tượng thuộc D:
X = (x1,x2,...,xk); Y = (y1,...,yk); Z = (z1,z2,...zk) (trong đó xi, yi, zi với i =
1,.., k) là các đặc trưng hoặc thuộc tính tương ứng của các đối tượng X, Y, Z;
như vậy sẽ có các kiểu dữ liệu sau:
+ Kiểu dữ liệu dựa trên kích thước miền

12


- Thuộc tính liên tục: Nếu miền giá trị của nó là vô hạn không đếm được,
nghĩa là giữa hai giá trị tồn tại vô số giá trị khác (ví dụ, các thuộc tính màu,
nhiệt độ hoặc cường độ âm thanh,...)
- Thuộc tính rời rạc: Nếu miền giá trị của nó là tập hữu hạn, đếm đượ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,...)
+ 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 hoá của thuộc tính
nhị phân, trong đó có 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 nhưng 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 xi cách yi một
khoảng xi - yi tương ứng với thuộc tính thứ i.
Việc lựa chọn đơn vị đo cho các thuộc tính cũng ảnh hưởng đến chất
lượng phân cụm. Nếu đơn vị độ đo của một thuộc tính càng được chia nhỏ, thì
khoảng cách xác định của thuộc tính đó càng lớn và ảnh hưởng nhiều hơn đến
kết quả phân cụm. Để tránh phụ thuộc vào việc lựa chọn đơn vị đo, dữ liệu cần
được chuẩn hóa. Việc chuẩn hóa sẽ gán cho tất cả các thuộc tính một trọng số
bằng nhau. Tuy nhiên, trong nhiều trường hợp người sử dụng có thể thay đổi
trọng số cho các thuộc tính ưu tiên.
Để chuẩn hóa các độ đo, một cách làm phổ biến là biến đổi các thuộc
tính về dạng không có đơn vị đo. Giả sử đối với các thuộc tính f, ta thực hiện
như sau:
13


- Tính độ lệch trung bình:
1
(|𝑥 − 𝑚𝑓 | + |𝑥2𝑓 − 𝑚𝑓 |+ . . . + |𝑥𝑛𝑓 − 𝑚𝑓 |)
𝑛 1𝑓
Trong đó x1f, ..., xnf là giá trị thuộc tính f của n phần tử dữ liệu, và mf là
𝑆𝑓 =

giá trị trung bình của f, được cho như sau:
1
(𝑥 + 𝑥2𝑓 + . . . + 𝑥𝑛𝑓 )
𝑛 1𝑓
- Độ đo được chuẩn hóa:

𝑥𝑖𝑓 − 𝑚𝑓
𝑧𝑖𝑓 =
𝑆𝑓
𝑚𝑓 =

- Thuộc tính nhị phân là thuộc tính có hai giá trị là 0 và 1.
- Thuộc tính tỷ lệ: Là thuộc tính khoảng nhưng được xác định một cách
tương đối so với điểm mốc.
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 cách 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ề hình học,
quan hệ metric, quan hệ hướng,...). Dữ liệu không gian có thể là dữ liệu liên tục
hoặc rời rạc.
- Dữ liệu không gian liên tục: Bao chứa một vùng không gian.
- Dữ liệu không gian rời rạc: Có thể là một điểm trong không gian nhiều
chiều và cho phép xác định khoảng cách giữa các đối tượng dữ liệu trong không
gian.
1.4. Phép đo độ tương tự và khoảng cách đối với các kiểu dữ liệu
1.4.1. Khái niệm tương tự, phi tương tự
Để phân cụm, người ta phải đi tìm cách thích hợp để xác định “khoảng
cách” giữa các đối tượng, hay là phép đo tương tự dữ liệu. Đây là các hàm để
đo sự giống nhau giữa các cặp đối tượng dữ liệu, thông thường các hàm này
14


hoặc là để tính độ tương tự (Similar) hoặc là tính độ phi tương tự (Dissimilar)
giữa các đối tượng dữ liệu.

Giá trị của hàm tính độ đo tương tự càng lớn thì sự giống nhau giữa các
đối tượng càng lớn và ngược lại, còn hàm tính độ phi tương tự tỉ lệ nghịch với
hàm tính độ tương tự. Độ tương tự hoặc phi tương tự có nhiều cách để xác định,
chúng thường được đo bằng khoảng cách giữa các đối tượng. Tất cả các cách
đo độ tương tự đều phụ thuộc vào kiểu thuộc tính mà con người phân tích. Ví
dụ, thuộc tính hạng mục thì không sử dụng độ đo khoảng cách mà sử dụng một
hướng hình học của dữ liệu.
Tất cả các độ đo dưới đây được xác định trong không gian metric. Bất
kỳ một metric nào cũng là một độ đo, nhưng điều ngược lại không đúng. Để
tránh sự nhầm lẫn, thuật ngữ độ đo ở đây đề cập đến hàm tính độ tương tự hoặc
hàm tính độ phi tương tự. Một không gian metric là một tập trong đó có xác
định “khoảng cách” giữa từng cặp phần tử, với những tính chất thông thường
của khoảng cách hình học. Nghĩa là, một tập X (các phần tử của nó có thể là
những đối tượng bất kỳ) các đối tượng dữ liệu trong cơ sở dữ liệu D đề cập ở
trên được gọi là một không gian metric nếu:
- Với mỗi cặp phần tử x, y thuộc X đều xác định theo một quy tắc nào đó,
một số thực 𝛿(x,y) được gọi là khoảng cách giữa x và y.
- Quy tắc nói trên thỏa mãn hệ tính chất sau:
(i)

𝛿(x,y) > 0 nếu x ≠ y;

(ii)

𝛿(x,y) = 0 nếu x = y;

(iii)

𝛿(x,y) = 𝛿(y,x) với mọi x, y;


(iv)

𝛿(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ử x,y được
gọi là các điểm của không gian này.
1.4.2. Thuộc tính khoảng
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 vectơ thể hiện dữ liệu thuộc
15


trong cùng một đơn vị giống nhau thì nó tồn tại khoảng cách Euclidean 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 Euclidean cũng cho kết quả chính xác.
Tuy nhiên chú ý rằng đây không phải vấn đề đồ thị: vấn đề phát sinh từ
công thức toán học được sử dụng để kết hợp khoảng cách giữa các thành phần
đơn đặc tính dữ liệu vectơ vào trong một độ đo khoảng duy nhất mà có thể được
sử dụng cho mục đích phân cụm: các công thức khác nhau dẫn tới những cụm
khác nhau.
Các thuật toán cần có các phép đo khoảng cách hoặc độ tương tự giữa
hai đối tượng để thực hiện phân cụm. Kiến thức miền phải được sử dụng để
trình bày rõ ràng phép đo khoảng thích hợp cho mỗi ứng dụng. Hiện nay, phép
đo có nhiều mức độ khác nhau tùy theo từng trường hợp.
- Khoảng cách Minkowski:
𝑑𝑖𝑠𝑡𝑞 (𝑥, 𝑦) = (∑𝑛𝑖=1|𝑥𝑖 − 𝑦𝑖 |𝑞 )1/𝑞 , q ≥ 1;
Trong đó x, y là hai đối tượng với n là số lượng thuộc tính, x =
(x1,x2,...,xn) và y = (y1,y2,...,yn), dist là khoảng cách của 2 đối tượng.
- Khoảng cách Euclidean:
𝑛


𝑑𝑖𝑠𝑡𝑞 (𝑥, 𝑦) = √∑(𝑥𝑖 − 𝑦𝑖 )2
𝑖=1

là khoảng cách giữa hai đối tượng.
- Khoảng cách Manhattan:
𝑛

𝑑𝑖𝑠𝑡𝑞 (𝑥, 𝑦) = (∑|𝑥𝑖 − 𝑦𝑖 |)
𝑖=1

là khoảng cách trung bình giữa hai đối tượng trong trường hợp đặc biệt
q=l.
- Khoảng cách Chebychev:
dist∞(x, y) = maxi=1,…,n |xi - yi|;

16


Trong trường hợp q = ∞, hữu ích để định nghĩa các đối tượng phi tương
tự nếu chúng khác nhau chỉ trong một kích thước biến đổi.
- Bình phương khoảng cách Euclidean.
𝑛

𝑑𝑖𝑠𝑡𝑞 (𝑥, 𝑦) = ∑(𝑥𝑖 − 𝑦𝑖 )2
𝑖=1

- Tỉ lệ khác nhau. Giả sử các biến là tuyệt đối.
𝑑𝑖𝑠𝑡(𝑥, 𝑦) = (𝑁𝑢𝑚𝑏𝑒𝑟(𝑥𝑖 ≠ 𝑦𝑖 )) / 𝑖
Khoảng cách Euclidean được sử dụng phổ biến nhất để đo độ tương tự

của khoảng cách Minkowski. Giả sử có hai trường hợp C1 và C2 có các biến
liên tục x và y, lấy lần lượt các giá trị (x1, y1) và (x2, y2) tương ứng, có thể vẽ đồ
thị hai trường hợp trong không gian x-y:

Khoảng cách Euclidean
Tuy nhiên không có nguyên tắc tổng quát để chọn phép đo áp dụng cho
bất cứ bài toán nào. Một cách đơn giản để đo độ tương tự giữa các nhóm trong
khung tương tự bằng cách thay thế nhóm cho thuộc tính thứ i của đối tượng đo
chẳng hạn như khoảng cách Euclidean, khoảng cách Manhattan, hoặc bình
phương Mahalanobis. Ví dụ, giả sử rằng nhóm A có vectơ trung bình A =
[𝑥̅𝑎1 , 𝑥̅𝑎2 , . . . , 𝑥̅𝑎𝑛 ] và nhóm B có vectơ trung bình B = [𝑥̅𝑏1 , 𝑥̅𝑏2 , . . . , 𝑥̅𝑏𝑛 ] thì
cách đo bằng khoảng cách Euclidean giữa hai nhóm có thể được định nghĩa là:
𝑛

1/2

𝑑𝑖𝑠𝑡(𝐴, 𝐵) = (∑(𝑥̅𝑎𝑖 − 𝑥̅𝑏𝑖 )2 )
𝑖=1

17


Cách tiếp cận khác để tính là khoảng cách giữa phần tử gần nhất hoặc
phần tử xa nhất. Cách tiếp cận này sử dụng các thuật toán phân cụm phân cấp
chẳng hạn như liên kết đơn và liên kết đầy đủ. Vấn đề chính với hai cách tiếp
cận này giống nhau là không cảm nhận được mâu thuẫn định lượng và không
tính toán cho các yếu tố của các phần tử trong một nhóm.
Cách tiếp cận khác, là trung bình nhóm, có thể sử dụng phép đo độ tương
tự giữa các nhóm. Cách tiếp cận này, sự giống nhau giữa các nhóm được đo
bằng cách lấy giá trị trung bình của tất cả các phép đo giữa các đối tượng cho

từng cặp đối tượng trong các nhóm khác nhau. Ví dụ, trung bình phi tương tự
giữa nhóm A và B có thể được định nghĩa là:
𝑛𝑥 𝑛𝑏

𝑑𝑖𝑠𝑡(𝐴, 𝐵) = [∑ ∑ 𝑑(𝑥𝑖 , 𝑦𝑖 )] / 𝑛
𝑖=1 𝑗=1

trong đó, n là tổng số các đối tượng cùng cặp, n = nx x ny, nx và ny lần
lượt là số các đối tượng trong đối tượng xi và yi, d(xi,yi) là phi tương tự của một
cặp đối tượng xi và yi, xi ∈ A, yi ∈ B. Hàm phi tương tự có thể dễ dàng chuyển
đổi sang hàm tương tự bằng cách thay đổi cho nhau.
1.4.3. Thuộc tính nhị phân
Tất cả các phép đo được định nghĩa ở trên đa số thích hợp cho các biến
liên tục. Cho các biến danh nghĩa, “phép đo khoảng cách” là 0 nếu các trường
hợp có cùng giá trị danh nghĩa, và 1 nếu các trường hợp có các giá trị danh
nghĩa khác nhau, hoặc với độ đo tương tự 1 (nếu các trường hợp có cùng giá trị
danh nghĩa) và 0 (nếu không giống nhau).
Do đó nếu xem xét p biến định danh, có thể đánh giá độ tương tự của các
trường hợp bằng số các biến mà có giá trị giống nhau. Nói chung định nghĩa
với một biến nhị phân mới từ mỗi biến danh nghĩa, bằng việc nhóm các nhãn
danh nghĩa thành hai lớp, một nhãn là 1, nhãn khác là 0. Xây dựng và xem xét
bảng ngẫu nhiên các sự kiện có thể xảy ra và định nghĩa các thuộc tính của đối
tượng x, y bằng các biến số nhị phân 0 và 1.

18