Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
1
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG TỐNG ĐÌNH TIẾN
TỐI ƢU HÓA CÁC THÔNG SỐ HỆ MỜ SỬ DỤNG
PHÂN CỤM DỮ LIỆU TRỪ VÀ GIẢI THUẬT DI TRUYÊN
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
NGƢỜI HƢỚNG DẪN KHOA HỌC
P G S.TS LÊ BÁ DŨNG
THÁI NGUYÊN - 2014 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
3

LỜI CAM ĐOAN

Tôi xin cam đoan luận văn là kết quả của sự tìm hiểu, nghiên cứu các tài liệu
một cách nghiêm túc dưới sự hướng dẫn của PGS. TS Lê Bá Dũng. Nội dung luận
văn được phát triển từ ý tưởng, sự sáng tạo của bản thân và kết quả có được hoàn
toàn trung thực.

Học viên
Tống Đình Tiến

hộ, động viên và giúp đỡ để tôi có thể hoàn thành tốt luận văn.
Một lần nữa, em xin chân thành cảm ơn.
Thái Nguyên,15 tháng 3 năm 2014
Học viên
Tống Đình Tiến
Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
i
MỤC LỤC
LỜI CAM ĐOAN
LỜI CẢM ƠN
MỤC LỤC i
DANH MỤC CÁC KÍ HIỆU, CHỮ CÁI VIẾT TẮT iii
DANH MỤC CÁC BẢNG BIỂU iv
DANH MỤC CÁC HÌNH v
MỞ ĐẦU 1

2.1.2.2. Thuật toán phân cụm dữ liệu trừ mờ (FSC - Fuzzy Subtractive
Clustering) 27
2.2.1.3. Thuật toán phân cụm trừ mờ loại hai khoảng 29
2.2. Giải thuật di truyền. 31
2.2.1. Giải thuật di truyền và các phương pháp tối ưu truyền thống 31
2.2.2. Một giải thuật di truyền đơn giản 34
2.2.3. Giải thuật di truyền trong công việc-sự mô phỏng bằng tay 38
2.2.4. Lợi ích trong việc tìm kiếm những tương đồng quan trọng 41
2.2.4.1. Những khuôn mẫu giống nhau 42
2.2.4.2. Cái nào sẽ tồn tại và cái nào sẽ bị loại bỏ 44
CHƢƠNG 3 ỨNG DỤNG PHÂN CỤM DỮ LIỆU TRỪ VÀ GIẢI THUẬT DI
TRUYỀN TRONG VIỆC ĐO VÀ ĐIỀU KHIỂN NHIỆT 51
3.1. Phát biểu bài toán 51
3.2. Một số ứng dụng của phân cụm dữ liệu trừ cho đo và điều khiển tự động. 52
3.2.1. Ứng dụng thuật toán phân cụm trừ cho xây dựng hệ luật 52
3.2.2. Xây dựng hệ luật điều khiển mờ 53
3.2.3. Tối ưu các thông số cho luật điều khiển mờ 54
3.3 Thử nghiệm sử dụng các thuật toán phân cụm dữ liệu trừ, giải thuật di truyền
để xây dựng chương trình đo và điều khiển nhiệt độ. 59
3.3.1. Các chức năng của chương trình. 59
3.3.2. Giao diện chương trình 59
KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN 62
TÀI LIỆU THAM KHẢO 63 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
iii
DANH MỤC CÁC KÍ HIỆU, CHỮ CÁI VIẾT TẮT

CURE Clustering Using Representatives

Bảng 2.1. Ví dụ về các chuỗi và các độ thích nghi tương ứng 35
Bảng 2.2. Ví dụ về một quần thể cỡ 4 ban đầu39
Bảng 2.3 Quần thể sau khi ghép chéo 40
Bảng 3.1. Hệ luật mờ của hệ thống điều khiển cho ban đầu 54
Bảng 3.2. Kết quả phân cụm trừ 55 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
v

Hình 3.8. Biểu diễn hệ luật dwosi dạng đồ thị 60
Hình 3.9. Hàm thuộc và mặt suy diễn được tạo 61
Hình 3.10 a Tín hiệu ra tiệm cận với tín hiệu yêu cầu 61
Hình 3.10 b Tác động điều khiển 61

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
1
MỞ ĐẦU
Trong ngành khoa học máy tính, việc đi tìm kiếm lời giải tối ưu cho các bài
toán là vấn đề được các nhà khoa học máy tính đặc biệt rất quan tâm. Mục đích
chính của các thuật toán tìm kiếm lời giải là tìm ra lời giải tối ưu nhất cho bài toán
trong thời gian nhỏ nhất. Các thuật toán như tìm kiếm không có thông tin, vét cạn
(tìm kiếm trên danh sách, trên cây hoặc đồ thị ) sử dụng phương pháp đơn giản nhất
và trực quan nhất hoặc các thuật toán tìm kiếm có thông tin sử dụng Heurictics để
áp dụng các tri thức về cấu trúc của không gian tìm kiếm nhằm giảm thời gian cần
thiết cho việc tìm kiếm được sử dụng nhiều nhưng chỉ với không gian tìm kiếm nhỏ
và không hiệu quả khi tìm kiếm trong không gian tìm kiếm lớn. Tuy nhiên, trong
thực tiễn có rất nhiều bài toán tối ưu với không gian tìm kiếm rất lớn cần phải giải
quyết. Vì vậy, việc đòi hỏi thuật giải chất lượng cao và sử dụng kỹ thuật trí tuệ nhân
tạo đặc biệt rất cần thiết khi giải quyết các bài toán có không gian tìm kiếm lớn.
Giải thuật di truyền (Genetic algorithm) là một trong những kỹ thuật tìm kiếm lời
giải tối ưu đã đáp ứng được yêu cầu của nhiều bài toán và ứng dụng.
Thuật giải di truyền đã được phát minh ra để bắt chước quá trình phát triển tự
nhiên trong điều kiện quy định sẵn của môi trường. Các đặc điểm của quá trình này
đã thu hút sự chú ý của John Holand (ở đại học Michigan) ngay từ những năm
1970. Holand tin rằng sự gắn kết thích hợp trong thuật giải máy tính có thể tạo ra
một kỹ thuật giúp giải quyết các vấn đề khó khăn giống như trong tự nhiên đã diễn
ra-thông qua quá trình tiến hóa.
Trong thực tế cuộc sống, chúng ta bắt gặp nhiều bài toán như dự đoán thị
trường chứng khoán, dự đoán lưu lượng nước, dự đoán lượng ga tiêu thụ, dự đoán

có thể được tự động xác định theo phương pháp phân cụm.
Trong học máy, phân cụm dữ liệu được xem là vấn đề học không có giám sát,
vì nó phải giải quyết vấn đề tìm một cấu trúc trong tập hợp dữ liệu chưa biết trước
các thông tin về cụm hay các thông tin về tập huấn luyện. Trong nhiều trường hợp,
nếu phân lớp được xem là vấn đề học có giám sát thì phân cụm dữ liệu là một bước
trong phân lớp dữ liệu, phân cụm dữ liệu sẽ khởi tạo các lớp cho phân lớp bằng
cách xác định các nhãn cho các nhóm dữ liệu.
Phân cụm có ý nghĩa rất quan trọng trong hoạt động của con người. Ngay từ
lúc bé, con người đã học cách làm thế nào để phân biệt giữa mèo và chó, giữa động
vật và thực vật và liên tục đưa vào sơ đồ phân loại trong tiềm thức của mình. Phân
cụm được sử dụng rộng rãi trong nhiều ứng dụng, bao gồm nhận dạng mẫu, phân
tích dữ liệu, xử lý ảnh, nghiên cứu thị trường Với tư cách là một chức năng khai
phá dữ liệu, phân cụm có thể được sử dụng như một công cụ độc lập chuẩn để quan
sát đặc trưng của mỗi cụm thu được bên trong sự phân bố của dữ liệu và tập trung
vào một tập riêng biệt của các cụm để giúp cho việc phân tích đạt kết quả.
Một vấn đề thường gặp trong phân cụm là hầu hết các dữ liệu cần cho phân
cụm đều có chứa dữ liệu nhiễu do quá trình thu thập thiếu chính xác hoặc thiếu đầy
đủ, vì vậy cần phải xây dựng chiến lược cho bước tiền xử lý dữ liệu nhằm khắc
phục hoặc loại bỏ nhiễu trước khi chuyển sang giai đoạn phân tích cụm dữ liệu.
Nhiễu ở đây được hiểu là các đối tượng dữ liệu không chính xác, không tường minh

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
4
hoặc là các đối tượng dữ liệu khuyết thiếu thông tin về một số thuộc tính Một
trong các kỹ thuật xử lý nhiễu phổ biến là việc thay thế giá trị các thuộc tính của đối
tượng nhiễu bằng giá trị thuộc tính tương ứng. Ngoài ra, dò tìm phần tử ngoại lai
cũng là một trong những hướng nghiên cứu quan trọng trong phân cụm, chức năng
của nó là xác định một nhóm nhỏ các đối tượng dữ liệu khác thường so với các dữ
liệu trong cơ sở dữ liệu, tức là các đối tượng dữ liệu không tuân theo các hành vi
hoặc mô hình dữ liệu nhằm tránh sự ảnh hưởng của chúng tới quá trình và kết quả

cần phân cụm, mục đích của ứng dụng thực tế hoặc xác định độ ưu tiên giữa chất
lượng của các cụm hay tốc độ thực hiện thuật toán,
Hầu hết các nghiên cứu và phát triển thuật toán phân cụm dữ liệu đều nhằm
thỏa mãn các yêu cầu cơ bản sau:
- Có khả năng mở rộng: Nhiều thuật toán phân cụm làm việc tốt với những tập
dữ liệu nhỏ (chứa ít hơn 200 đối tượng), tuy nhiên một cơ sở dữ liệu lớn có thể chứa
tới hàng triệu đối tượng. Việc phân cụm trên một tập dữ liệu lớn có thể làm ảnh
hưởng tới kết quả. Vậy các thuật toán phân cụm dữ liệu có khả năng mở rộng cao là
cần thiết.
- Khả năng thích nghi với các kiểu dữ liệu khác nhau: Thuật toán có thể áp
dụng hiệu quả cho việc phân cụm các tập dữ liệu với nhiều kiểu dữ liệu khác nhau
như dữ liệu kiểu số, kiểu nhị phân, dữ liệu định danh, hạng mục, và thích nghi với
kiểu dữ liệu hỗn hợp.
- Khám phá các cụm với hình dạng bất kỳ: Do hầu hết các cơ sở dữ liệu có
chứa nhiều cụm dữ liệu với các hình thù khác nhau như: hình lõm, hình cầu, hình
que, Vì vậy, để khám phá được các cụm có tính tự nhiên thì các thuật toán phân
cụm cần phải có khả năng khám phá ra các cụm dữ liệu có hình thù bất kỳ.
- Tối thiểu lượng tri thức cần cho xác định các tham số đầu vào: 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.
- Ít nhạy cảm với thứ tự của dữ liệ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.

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
6
- Khả năng thích nghi với dữ liệu nhiễu cao: Hầu hết các dữ liệu phân cụm
trong khai phá dữ liệu đều chứa đựng các dữ liệu lỗi, dữ liệu không đầy đủ, dữ liệu
rác. Thuật toán phân cụm không những hiệu quả đối với các dữ liệu nhiễu mà còn
tránh dẫn đến chất lượng phân cụm thấp do nhạy cảm với nhiễu.

thông tin cho nhận dạng các vùng nguy hiểm.
- Thư viện: Phân loại các cụm sách có nội dung và ý nghĩa tương đồng nhau để
cung cấp cho độc giả.
- Bảo hiểm: Nhận dạng nhóm tham gia bảo hiểm có chi phí bồi thường cao,
nhận dạng gian lận thương mại.
- Khai phá web: Có thể khám phá các nhóm tài liệu quan trọng, có nhiều ý
nghĩa trong môi trường Web. Các lớp tài liệu này trợ giúp cho việc khai phá tri thức
từ dữ liệu web,…
1.4. Các kỹ thuật tiếp cận và một số thuật toán cơ bản trong phân cụm dữ liệu
Có nhiều thuật toán phân cụm, nhưng để đưa ra một sự phân loại rõ nét của
các phương pháp phân cụm là khó khăn bởi vì các loại này có thể chồng chéo lên
nhau, do đó một phương pháp có thể có những đặc tính của một số thuật toán khác
nhau. Các phương pháp phân cụm chính có thể được phân loại như sau:
1.4.1. Các phương pháp phân cụm phân hoạch - Partitioning Methods
Với một tập dữ liệu gồm n phần tử và k (k n) là số cụm được tạo thành. Một
thuật toán phân hoạch tổ chức các phần tử dữ liệu vào k phân vùng, mỗi phân vùng
thể hiện một cụm dữ liệu và thỏa mãn: mỗi cụm phải chứa ít nhất một phần tử dữ
liệu và mỗi phần tử dữ liệu chỉ thuộc vào một cụm.
Để đưa ra được k phân mảnh, một phương pháp phân mảnh tạo ra một phân
mảnh khởi tạo, sau đó sử dụng kỹ thuật lặp để cải thiện phân mảnh bằng cách di
chuyển các phần tử dữ liệu từ cụm này sang cụm khác. Tiêu chuẩn tổng quát của
quá trình phân mảnh tốt là các phần tử thuộc cùng một cụm thì “gần gũi” hoặc có
liên quan đến nhau, các phần tử khác cụm thì “xa nhau” hoặc rất khác nhau. Có
nhiều tiêu chuẩn khác nhau để đánh giá chất lượng của các phân mảnh.

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
8
Để đạt được tối ưu toàn cục trong phân cụm dựa trên phân hoạch yêu cầu phải
liệt kê đầy đủ tất cả các phân mảnh có thể có. Thay vào đó, hầu hết các ứng dụng
chấp nhận một trong các phương pháp heuristic phổ biến, như thuật toán K-means

Một phương pháp phân cụm phân cấp hoạt động bằng cách nhóm các đối
tượng dữ liệu vào một cây của các cụm. Phương pháp phân cụm phân cấp có thể
được phân loại là hợp nhất hoặc chia tách, tùy thuộc vào việc phân ly có thứ bậc
được hình thành dựa trên kiểu bottom-up (hòa trộn) hay top-down (phân chia). Hình 1.1. Các cách phân cụm phân cấp
Hiệu quả của một phương pháp phân cụm phân cấp thuần túy bỏ qua sự không
có khả năng để điều chỉnh một lần một quyết định hợp nhất hoặc chia tách đã được
thực hiện. Nghĩa là, nếu một quyết định hợp nhất hoặc chia tách cụ thể đã được thực
hiện, sau đó đẫn tới một lựa chọn kém thì phương pháp này không thể quay trở lại
và chỉnh sửa nó. Các nghiên cứu gần đây đã nhấn mạnh sự tích hợp của sự hợp nhất
phân cấp với các phương pháp lặp di dời.
Có hai loại phƣơng pháp phân cụm phân cấp:
Phân cụm phân cấp hợp nhất: Đây là chiến lược từ dưới lên bắt đầu bằng cách
đặt mỗi đối tượng trong một cụm riêng của mình, sau đó sát nhập các cụm nguyên
tử thành các cụm lớn hơn và lớn hơn, cho đến khi tất cả các đối tượng trong một
cụm duy nhất hoặc cho đến khi các điều kiện kết thúc phân cụm được thỏa mãn.
Hầu hết các phương pháp phân cụm phân cấp thuộc loại này. Chúng chỉ khác nhau
trong định nghĩa về sự tương tự của các phần tử trong cụm.
Phân cụm phân cấp chia tách: Đây là chiến lược từ trên xuống, đảo ngược của
phân cụm phân cấp hợp nhất bằng cách bắt đầu với tất cả các đối tượng trong một

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

11
thường độc lập với số lượng đối tượng dữ liệu, nhưng phụ thuộc vào số lượng các ô
trong mỗi chiều của của không gian lưới.

Hình 1.2. Cấu trúc phân cụm dựa trên lƣới điểm
Một số ví dụ điển hình của phương pháp tiếp cận dựa trên lưới bao gồm Sting,
khám phá các thông tin thống kê được lưu trữ trong các ô lưới; WaveCluster, phân
cụm bằng cách sử dụng một phương pháp biến đổi biến thiên trong một thời gian
nhất định; CLIQUE, đại diện cho một cách tiếp cận dựa trên mật độ và lưới trong
không gian dữ liệu có số chiều lớn.
1.4.5. Phương pháp phân cụm dựa trên mô hình - Model-Based Clustering
Methods
Phương pháp phân cụm dựa trên mô hình cố gắng để tối ưu hóa sự phù hợp
giữa dữ liệu cho trước và một số mô hình toán học. Những phương pháp này
thường được dựa trên giả định rằng các dữ liệu được tạo ra bởi sự hòa nhập của các
phân bố xác suất cơ bản.
Các thuật toán phân cụm dữ liệu dựa trên mô hình:
- Thuật toán EM (Expectation Maximization) gán các đối tượng cho các cụm
đã cho theo phân phối xác suất thành phần của đối tượng đó, thường sử dụng phân
phối xác suất Gaussian.
- Phân cụm dựa trên khái niệm (Conceptual Clustering) là một dạng của phân
cụm trong học máy (machine learning) cung cấp một chiến lược phân lớp trên tất cả
các đối tượng. Phân cụm thông thường chủ yếu xác định các nhóm đối tượng tương
tự, nhưng phân cụm dựa trên khái niệm tìm kiếm các mô tả đặc trưng cho từng
nhóm, mỗi nhóm đại diện cho một khái niệm hoặc lớp. Do đó, phân cụm dựa trên

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
12
khái niệm gồm hai bước: thực hiện phân cụm và sau đó mô tả đặc tính. Ở đây, chất
lượng phân cụm là sự kết hợp chặt chẽ các yếu tố như tính tổng quát và sự đơn giản

cụm có dữ liệu ràng buộc như sau:
- Phân cụm thống kê: Dựa trên các khái niệm phân tích hệ thống, 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ỉ
áp dụng cho các dữ liệu có thuộc tính số.
- Phân cụm khái niệm: Các kỹ thuật phân cụm được phát triển áp dụng cho dữ
liệu hạng mục, chúng phân cụm các đối tượng theo các khái niệm mà chúng xử lý.
- Phân cụm mờ: Thông thường mỗi phương pháp phân cụm dữ liệu phân một
tập dữ liệu ban đầu thành các cụm dữ liệu có tính tự nhiên và mỗi đối tượng dữ liệu
chỉ thuộc về một cụm dữ liệu, phương pháp này chỉ phù hợp với việc khám phá ra
các cụm có mật độ cao và rời nhau. Tuy nhiên, trong thực tế, các cụm dữ liệu lại có
thể chồng lên nhau (một số các đối tượng dữ liệu thuộc về nhiều các cụm khác
nhau), người ta đã áp dụng lý thuyết về tập mờ trong phân cụm dữ liệu để giải quyết
cho trường hợp này, cách thức kết hợp này được gọi là phân cụm mờ. Trong
phương pháp phân cụm mờ, độ phụ thuộc của đối tượng dữ liệu
k
x
vào cụm thứ i
(
ik
u
) có giá trị thuộc đoạn [0, 1]. Ý tưởng trên đã được giới thiệu bởi Ruspini (1969)
và được Dunn áp dụng năm 1973 nhằm xây dựng một phương pháp phân cụm mờ
dựa trên tối thiểu hóa hàm tiêu chuẩn. Bezdek (1982) đã tổng quát hóa phương pháp
này và xây dựng thành thuật toán phân cụm mờ c-means (FCM) có sử dụng trọng số
mũ. Sau đó nhiều phương pháp được đề xuất để cải tiến thuật toán FCM như: Phân
cụm dựa trên xác suất (keller, 1993), phân cụm nhiễu mờ (Dave, 1991), phân cụm
dựa trên toán tử Lp Norm (kersten, 1999), thuật toán -Insensitive Fuzzy c-means.
Một cách tiếp cận khác của phương pháp phân cụm mờ có khả năng xác định số
lượng cụm và các tâm cụm gồm: giải thuật Mountain, thuật toán phân cụm trừ và
phân cụm trừ mờ.

i2
,…,
X
in
}, i =
n,1
, sao cho hàm tiêu chuẩn:
Cix
i
k
i
mxDE )(
2
1
đạt giá trị tối
thiểu. Trong đó: m
i
là trọng tâm của cụm C
i
, D là khoảng cách giữa hai đối tượng.
Trọng tâm của một cụm là một vectơ, trong đó giá trị của mỗi phần tử của nó
là trung bình cộng của các thành phần tương ứng của các đối tượng vectơ dữ liệu
trong cụm đang xét. Tham số đầu vào của thuật toán là số cụm k, và tham số đầu ra
của thuật toán là các trọng tâm của cụm dữ liệu. Độ đo khoảng cách D giữa các đối
tượng dữ liệu thường được sử dụng là khoảng cách Euclide vì đây là mô hình
khoảng cách mà dễ lấy đạo hàm và xác định các cực trị tối thiểu. Hàm tiêu chuẩn và
độ đo khoảng cách có thể được xác định cụ thể hơn tùy vào ứng dụng hoặc quan
điểm của người dùng.
Thuật toán K-means được trình bày như sau:

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
16
tâm cụm bằng nhân tố co cụm. Quá trình này được lặp lại và như vậy trong quá
trình này, có thể đo tỉ lệ gia tăng của cụm. Tại mỗi bước của thuật toán, hai cụm có
cặp các điểm đại diện gần nhau (mỗi điểm trong cặp thuộc về mỗi cụm khác nhau)
được hoà nhập.
Như vậy, có nhiều hơn một điểm đại diện mỗi cụm cho phép CURE khám phá
được các cụm có hình dạng không phải hình cầu. Việc co lại các cụm có tác dụng
làm giảm tác động của các phần tử ngoại lai. Như vậy, thuật toán này có khả năng
xử lý tốt trong các trường hợp có các phân tử ngoại lai và làm cho nó hiệu quả với
những hình dạng không phải là hình cầu và kích thước độ rộng biến đổi. Hơn nữa,
nó tỉ lệ tốt với cơ sở dữ liệu lớn mà không làm giảm chất lượng phân cụm.
Để xử lý được các cơ sở dữ liệu lớn, CURE sử dụng mẫu ngẫu nhiên và phân
hoạch, một mẫu là được xác định ngẫu nhiên trước khi được phân hoạch, và sau đó
tiến hành phân cụm trên mỗi phân hoạch, như vậy trên mỗi phân hoạch là từng phần
đã được phân cụm, quá trình này lặp lại cho đến khi ta thu được phân hoạch đủ tốt.
Các cụm thu được lại được phân cụm lần thứ hai để thu được các cụm con mong
muốn, nhưng mẫu ngẫu nhiên không nhất thiết đưa ra một mô tả tốt cho toàn bộ tập
dữ liệu.
CURE là thuật toán tin cậy trong việc khám phá ra các cụm với hình dạng bất
kỳ và có thể áp dụng tốt đối với dữ liệu có phần tử ngoại lai, và trên các tập dữ liệu
hai chiều. Tuy nhiên, nó lại rất nhạy cảm với các tham số như số các đối tượng đại
diện, tỉ lệ của các phần tử đại diện.
Thuật toán CURE được thực hiện qua các bước cơ bản như sau:
- Chọn một mẫu ngẫu nhiên từ tập dữ liệu ban đầu.
- Phân hoạch mẫu này thành nhiều nhóm dữ liệu có kích thước bằng nhau: Ý
tưởng chính ở đây là phân hoạch mẫu thành p nhóm dữ liệu bằng nhau, kích thước
của mỗi phân hoạch là n’/p (n’ là kích thước của mẫu).