ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ



PHẠM THỊ ÁNH


PHƯƠNG PHÁP PHÂN CỤM TÍCH LŨY VÀ ÁP DỤNG
TẠI NGÂN HÀNG THƯƠNG MẠI CỔ PHẦN QUÂN ĐỘI



LUẬN VĂN THẠC SĨ








Hà Nội - 2011
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ


PHẠM THỊ ÁNH


PHƯƠNG PHÁP PHÂN CỤM TÍCH LŨY VÀ ÁP DỤNG

TẠI NGÂN HÀNG THƯƠNG MẠI CỔ PHẦN QUÂN ĐỘI

Ngành: Công nghệ Thông tin
Chuyên ngành: Hệ thống Thông tin
Mã số: 60 48 05

LUẬN VĂN THẠC SĨ

NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS. Hà Quang Thụy




Hà Nội - 2011


MỤC LỤC
MỞ ĐẦU 6
Chương 1. Khái quát về phân cụm 3
1.1 Khái quát về bài toán phân cụm dữ liệu 3
1.2 Một số phương pháp phân cụm điển hình 4
1.2.1 Các phương pháp phân vùng 4
1.2.2 Các phương pháp phân cấp 10
1.2.3 Phương pháp phân cụm dựa trên mật độ 15
Chương 2. Phương pháp phân cụm tích lũy 19
2.1 Giới thiệu phương pháp phân cụm tích lũy 19
2.2 Sự kết hợp bầu cử đa số của các thuật toán phân cụm 20
2.3 Một số thuật toán phân cụm tích lũy 21
2.3.1. Phân cụm tích lũy dựa trên K-Means 22
2.3.2 Phân cụm tích lũy dựa trên lan truyền quan hệ 25

Chương 3. Mô hình khai phá dữ liệu dịch vụ khách hàng Ngân hàng quân đội 32
3.1 Một số mô hình khai phá dữ liệu ngân hàng 32
3.2 Hệ thống dịch vụ Ngân hàng quân đội 47
3.2.1 Hệ thống các dịch vụ 47
3.2.2 Hệ thống dữ liệu 48
3.3 Một mô hình phân cụm tích lũy dữ liệu khách hàng tại Ngân hàng quân đội 50
Chương 4. Thực nghiệm và đánh giá 52
4.1 Mục đích xây dựng và vai trò của ứng dụng 52
4.2. Mô hình thực nghiệm 52
4.2.1. Dữ liệu thực nghiệm 52
4.2.2 Công cụ thực nghiệm 57
4.3 Thực nghiệm và đánh giá 59
4.3.1 Môi trường thực nghiệm 59
4.3.2. Mô tả quy trình thực nghiệm 61
4.3.3. Kết quả thực nghiệm và đánh giá nhận xét 62


KẾT LUẬN 71
TÀI LIỆU THAM KHẢO 72


THUẬT NGỮ VÀ TỪ VIẾT TẮT

STT
Từ viết tắt
Giải thích
1
CSDL
Cơ sở dữ liệu
2

ATM
Máy rút tiền tự động
3
MB
Ngân hàng quân đội
4
CMTND
Chứng minh thư nhân dân
5
OLAP
Online analytical processing: xử lý phân tích trực
tuyến
6
CBM
Customer behavior modeling: mô hình hóa hành vi
khách hàng
7
NN
Neutral network: mạng nơron
8
AP
Affinity propagation: lan truyền quan hệ



DANH MỤC HÌNH VẼ

Hình 1.1: Một phần nhỏ của dữ liệu khách hàng về các vị trí khách hàng trong một thành
phố, chỉ ra ba phân cụm dữ liệu, Mỗi trung tâm phân cụm được đánh dấu „+‟ [1] 3
Hình 1.2: Quá trình phân cụm tập điểm thành 3 cụm theo k-means [1] 6

Hình 1.3 trường hợp của hàm chi phí cho phân cụm k-medoid [1] 8
Hình 1.4: Quá trình phân cụm tập điểm thành 3 cụm theo k- medoids [1] 9
Hình 1.5: phân cụm phân cấp dạng tích lũy và phân chia trên các đối tượng dữ liệu
{a,b,c,d,e} [1] 11
Hình 1.6: Một cây cấu trúc CF [1] 12
Hình 1.7: Phương pháp Chameleon 15
Hình 1.8 Phạm vi mật độ và sự liên kết mật độ trong phân cụm dựa trên mật độ [1] 16
Hình 1.9: Phân cụm dựa trên phương pháp mật độ [1] 18
Hình 2.1: Bổ xung sự phụ thuộc của thuật toán k-means trên sự khởi tạo trung tâm cụm,
k=2. (a)- vùng dữ liệu có được với việc chạy thuật toán k -means đơn. (b)- kết quả có
được khi sử dụng phương thức đề xuất với số lần lặp là 10. 23
Hình 2.2: Các cụm tạo ra bởi k-means (k=14) và các thuật toán voting-k-means. 24
Hình 2.3: Kết quả phân cụm cho một số phương pháp áp dụng cho tập dữ liệu kích thước
2000 là tổ hợp của 2 vòng xoắn. (a) k-means, k=45
2000
. (b) PAP (

=

). (c) PAP
(

=4). 30
Chương 3. Mô hình khai phá dữ liệu dịch vụ khách hàng Ngân hàng quân đội 32
Hình 3.1: Việc sử dụng kĩ thuật khai phá dữ liệu là một thách thức to lớn đối với ngành
tài chính. Nguồn dữ liệu to lớn của công ty có thể được sử dụng thông qua khai phá dữ
liệu cho những lĩnh vực ngành nghề khác[5] 35
Hình 3.2: Sử dụng kĩ thuật khai phá dữ liệu đối cho rủi ro khách hàng, công cụ tài chính,
danh mục đầu từ đối thị trường và với phương pháp đánh giá rủi ro tín dụng [5] 39
Hình 3.3: Sự quản lý danh mục công cụ là cơ sở đối với mọi thông tin, không những là

rủi ro, kịch bản và các mức độ tín dụng dự đoán, mà còn là các tin tức và tài nguyên
thông tin khác.[5] 44
Hình 3.4: Những người kinh doanh kiểm tra mối quan hệ giữa thông tin liên quan và giá
trị của tài sản ngành tài chính, và các mức độ an toàn mua hoặc bán khi họ phát hiện giá
lên hay xuống. [5] 45


Hình 3.5 Mô hình tính toán dữ liệu phương pháp phân cụm tích lũy dựa trên k-means 51
Hình 4.1: Giao diện ứng dụng cài đặt thuật toán phân cụm tích lũy dựa trên phương pháp
k-means 58
Hình 4.2: Mô hình ứng dụng cài đặt 61
Hình 4.3: Giao diện thực nghiệm theo phương án 1 63
Hình 4.4: Giao diện đồ họa thể hiện hai cụm theo phương án thực nghiệm 1 64
Hình 4.5: Thay đổi tham số đầu vào liên quan đến quá trình thực nghiệm 65
Hình 4.6: Giao diện đồ họa thể hiện khi thay đổi tham số thực nghiệm 66
Hình 4.7: (a) Phân cụm theo Phương pháp k-means; (b) Phân cụm theo Phương pháp
Phân cụm tích lũy dựa trên Phương pháp k-means. 67
Hình 4.8: Thực nghiệm theo phương án 2 69




MỞ ĐẦU
Những năm gần đây, ngành công nghệ thông tin chuyên nghiên cứu về các thuật
toán và phương pháp sử dụng trong lĩnh vực khai phá dữ liệu đã có những bước tiến mới
song song cùng với sự phát triển của ngành tin học nói chung. Đã có nhiều thuật toán
mới được đưa ra nhằm trích rút thông tin, phân loại dự đoán đặc điểm của dữ liệu từ tập
dữ liệu có trước. Đây là điều rất quan trọng đối với một xã hội phát triển trong đó đòi hỏi
nhu cầu hiệu quả trong hoạt động.
Trong vài năm trở lại đây, nhu cầu dự đoán hành vi khách hàng của các Ngân

hàng đang tăng cao. Ngân hàng Quân đội (MB) cũng không nằm ngoài xu hướng trên.
Mục đích của các Ngân hàng là làm thế nào để biết được rằng một khách hàng sẽ có khả
năng cao là sử dụng một dịch vụ cụ thể của mình. Để giải quyết bài toán trên, phương
pháp khai phá dữ liệu, dùng những thông tin có từ trước về tập khách hàng cũ để dự
đoán hành vi của khách hàng mới. Tuy nhiên, vấn đề là phải áp dụng phương pháp nào
để đảm bảo rằng công việc dự đoán là có hiệu quả nhất.
Một trong những phương pháp hiện đại được đưa ra trong năm vừa rồi là phương
pháp phân cụm tích lũy dựa trên một số phương pháp truyền thống. Nguyên tắc chung
của phương pháp là áp dụng lặp lại nhiều lần đối với việc phân cụm để tạo ra nhiều cụm
đã được phân cụm, rồi dựa trên các thông tin này để xây dựng lại các cụm. Công việc
này sẽ đảm bảo rằng việc phân cụm là chính xác.
Luận văn tập trung tìm hiểu phương pháp phân cụm tích lũy, phân tích nghiệp vụ
của Ngân hàng Quân đội và tập dữ liệu khách hàng, đồng thời qua đó nêu ra cách áp
dụng và xây dựng cài đặt ứng dụng dựa trên thuật toán phân cụm tích lũy dựa trên
phương pháp k-means để dự đoán hành vi khách hàng mới.
Nội dung của bản luận văn gồm có phần mở đầu, bốn chương và phần kết luận.
Chương 1 Luận văn trình bày khái niệm phân cụm, các phương pháp phân cụm
điển hình, xem xét các điểm mạnh, điểm yếu của từng phương pháp này.
Chương 2 Luận văn trình bày một phương pháp phân cụm mới được đưa ra là
phân cụm tích lũy. Phương pháp phân cụm tích lũy dựa trên phương pháp k-means được
khảo sát sâu nhằm áp dụng vào bài toán ứng dụng
Chương 3 Chương này, luận văn sẽ phân tích mô hình hoạt động kinh doanh của
Ngân hàng Quân đội (MB) và xem xét cách thức áp dụng khai phá dữ liệu trong Ngân
hàng này
2

Chương 4 Trong chương 3 luận văn đã phân tích thực trạng hoạt động kinh doanh
cũng như việc lưu trữ dữ liệu của Ngân hàng Quân đội và nhu cầu cần thiết phải có một
chương trình để có khả năng khai thác dữ liệu khách hàng đã có nhằm mục đích quảng
bá hình ảnh và dịch vụ của Ngân hàng Quân đội, nhằm duy trì khách hàng đã có và có

thêm khách hàng mới. Trong chương này sẽ tiến hành xây dựng ứng dụng nhằm phục vụ
cho mục tiêu khai phá dữ liệu đã đề ra, đồng thời xây dựng và thực hiện các phương án
thực nghiệm kết quả của ứng dụng.
Luận văn này được thực hiện dưới sự hướng dẫn khoa học của TS. Hà Quang
Thụy và được hỗ trợ một phần từ Đề tài QG.10-38. Tôi xin chân thành cảm ơn sâu sắc
tới Thầy đã chỉ dẫn tận tình giúp tôi có thể hoàn thành bản luận văn này. Tôi xin chân
thành cảm ơn các thầy giáo và các bạn trong bộ môn Các Hệ thống Thông tin đã có
những góp ý hữu ích trong quá trình thực hiện bản luận văn. Tôi cũng vô cùng cảm ơn sự
giúp đỡ và động viên khích lệ của người thân trong gia đình tôi, bạn bè và các đồng
nghiệp trong Ngân hàng MB trong suốt quá trình thực hiện luận văn.
3

Chương 1. Khái quát về phân cụm
1.1 Khái quát về bài toán phân cụm dữ liệu
Không giống sự phân loại và sự dự đoán dùng để phân tích lớp đối tượng, phân
loại theo lớp, sự phân cụm phân tích đối tượng dữ liệu mà không tham chiếu đến các lớp
đã được phân loại trước [1]. Nói chung, các lớp đã phân loại trước không xuất hiện trong
dữ liệu có sẵn. Sự phân cụm có thể được sử dụng để tạo ra các lớp. Bài toán phân cụm có
thể được phát biểu như sau: Cho một tập các đối tượng cho trước, yêu cầu phân các đối
tượng trên thành các cụm sao cho các đối tượng trong cùng một nhóm là tương đối giống
nhau, các đối tượng trong các nhóm khác nhau là rất khác nhau. Nói cách khác, các đối
tượng được phân cụm dựa trên nguyên lý của sự cực đại hóa sự giống nhau trong lớp và
tối thiểu hóa sự giống nhau giữa các lớp. Mỗi cụm được hình thành có thể được xem như
một lớp của các đối tượng, mà từ đó có thể tạo ra các luật.
Ví dụ, phân cụm có thể thực hiện trên dữ liệu khách hàng để nhận ra những tập
khách hàng đồng nhất. Những cụm này có thể biểu diễn các nhóm đích riêng biệt cho
việc quảng cáo. Hình 1.1 chỉ ra cụm 2-D của khách hàng ở trong một thành phố. Ba cụm
của điểm dữ liệu rất rõ ràng.

Hình 1.1: Một phần nhỏ của dữ liệu khách hàng về các vị trí khách hàng trong một thành phố,

chỉ ra ba phân cụm dữ liệu, Mỗi trung tâm phân cụm được đánh dấu ‘+’ [1]
Phân cụm là một lĩnh vực nghiên cứu đầy thách thức, trong đó, các ứng dụng tiềm
năng của nó đưa ra những đòi hỏi riêng. Sau đây là các yêu cầu đặc trưng của phân cụm:
 Tính mở rộng: nhiều thuật toán khai phá dữ liệu làm việc tốt trên những tập dữ
liệu chứa ít đối tượng; tuy nhiên, một cơ sở dữ liệu lớn thường chứa hàng triệu
đối tượng, đòi hỏi những thuật toán có khả năng mở rộng cao
 Khả năng khám phá các phân cụm với các hình dạng ngẫu nhiên: nhiều thuật toán
phân cụm xác định các cụm dựa trên đại lượng khoảng cách Euclidean hoặc
Manhattan. Những thuật toán dựa trên đại lượng khoảng cách này thường tìm
4

được các cụm hình cầu với kích thước và mật độ tương tự nhau. Tuy nhiên, một
cụm có thể có bất kì hình dạng nào khác. Cần phải phát triển một thuật toán phát
hiện cụm với hình dạng khác nhau.
 Các yêu cầu tối thiểu cho tri thức miền để xác định các tham số đầu vào: nhiều
thuật toán đòi hỏi người dùng phải đưa tham số đầu vào (ví dụ như số cụm). Kết
quả phân cụm có thể là rất nhậy cảm đối với tham số đầu vào. Các tham số đầu
vào thường khó xác định, đặc biệt là đối với các đối tượng nhiều chiều.
 Khả năng làm việc với dữ liệu nhiễu: hầu hết dữ liệu trên thế giới chứa những
thành phần bên ngoài hoặc dữ liệu bị thiếu hụt, bị lỗi, một số thuật toán nhạy cảm
với những loại dữ liệu trên dẫn tới việc phân cụm nghèo nàn.
 Khả năng phân cụm tăng dần và không nhạy cảm với trình tự bản ghi đầu vào:
một số thuật toán phân cụm không thể kết hợp dữ liệu thêm mới (nghĩa là, dữ liệu
cập nhật) vào trong các cấu trúc phân cụm đang tồn tại, và do đó phải xác định
một sự phân cụm mới từ đầu. Một số thuật toán phân cụm nhạy cảm với trình tự
dữ liệu đầu vào. Điều này quan trọng đối với các thuật toán phân cụm tăng dần và
thuật toán không nhạy cảm với thứ tự đầu vào.
 Số chiều lớn: một cơ sở dữ liệu hoặc kho dữ liệu có thể chứa một số chiều hoặc
các thuộc tính. Nhiều thuật toán phân cụm dùng tốt cho dữ liệu ít chiều, bao gồm
chỉ hai hoặc ba chiều. Mắt con người dùng tốt cho việc đánh giá lên đến ba chiều.

Tìm kiếm các phân cụm của các đối tượng dữ liệu trong không gian nhiều chiều là
một thách thức.
 Sự phân cụm dựa trên ràng buộc: các ứng dụng trong thế giới thực có thể cần sự
phân cụm dưa trên nhiều loại ràng buộc khác nhau. Gỉa sử rằng công việc của bạn
là tìm ra vị trí lựa chọn để đặt máy ATM, để quyết định việc này, bạn phải phân
cụm và xem xét vị trí, đường cao tốc, kiểu của khách hàng trên cụm….
 Tính thông dịch và hữu dụng: người dùng mong muốn kết quả phân cụm được
thông dịch, hiểu và sử dụng được. Đó là, phân cụm cần được kết hợp với sự thông
dịch ngữ nghĩa và các ứng dụng. Điều quan trọng là nghiên cứu làm thế nào một
mục đích ứng dụng có thể tác động lên sự lựa chọn của các đặc tính phân cụm và
các phương pháp.
1.2 Một số phương pháp phân cụm điển hình
1.2.1 Các phương pháp phân vùng
Cho một cơ sở dữ liệu của n đối tượng hoặc dòng dữ liệu, một phương pháp phân
cụm tạo ra k cụm của dữ liệu, trong đó mỗi vùng biểu diễn một cụm, và
nk 
. Phương
5

pháp này phân chia dữ liệu vào k nhóm, đáp ứng những yêu cầu sau: (1) mỗi nhóm phải
chứa ít nhất một đối tượng và, (2) mỗi đối tượng phải thuộc duy nhất một nhóm [1]. Chú
ý rằng yêu cầu thứ hai có thể bỏ qua trong một số kĩ thuật được miêu tả ở phần dưới.
Đưa ra k là số lượng cụm để xây dựng, một phương thức phân cụm cần khởi tạo
cụm. Sau đó sử dụng một kĩ thuật định vị trí lặp lại để cố gắng tăng sự cụm bằng cách rời
các đối tượng từ một nhóm tới một nhóm khác. Tiêu chuẩn chung của một sự phân cụm
tốt là các đối tượng trong cùng vùng là gần giống hoặc liên quan đến những đối tượng
khác, trong khi các đối tượng của các cụm khác nhau lại rất khác nhau. Có rất nhiều kiểu
tiêu chuẩn dành cho việc đánh giá chất lượng cụm.
Để có được sự tối ưu toàn diện trong cụm dựa trên sự phân cụm sẽ đòi hỏi số
lượng cực lớn của mọi sự phân cụm có thể. Thay vào đó, hầu hết các ứng dụng chấp

nhận một trong hai phương pháp heuristic phổ biến: thuật toán k-means, nơi mỗi cụm
được biểu diễn bởi giá trị trung bình của các giá trị trong cụm; và thuật toán k-medoids,
trong đó mỗi cụm được biểu diễn bởi một trong các đối tượng gần trung tâm của cụm.
Các phương thức cụm heuristic này làm việc tốt khi tìm kiếm các cụm hình cầu trong cơ
sở dữ liệu nhỏ hoặc trung bình. Khi tìm kiếm các cụm với hình dạng phức tạp và cho tập
dữ liệu lớn, các phương pháp phân cụm trên cần phải mở rộng.
 Phương pháp k-means
Thuật toán k-means có tham số đầu vào k, và phân một tập n đối tượng thành k
cụm sao cho các đối tượng trong một cụm là tương đối giống nhau còn các đối tượng
giữa các cụm lại có sự khác biệt khá rõ [1]. Sự giống nhau trong cụm được đánh giá theo
giá trị trung bình của các đối tượng trong đoạn, còn có thể được xem như là “trung tâm
của trọng lực” của cụm.
Thuật toán xử lý như sau: Đầu tiên, nó ngẫu nhiên lựa chọn k các đối tượng mà
mỗi đối tượng đại diện cho một trung bình hay trung tâm phân đoạn. Đối với mỗi đối
tượng còn lại, một đối tượng được gán cho một cụm mà giống nó nhất, dựa trên khoảng
cách giữa đối tượng và trung bình của đoạn. Nó sau đó sẽ tính trung bình mới cho mỗi
đoạn. Xử lý này được lặp lại tới tận khi hàm tiêu chuẩn hội tụ. Thường hàm hội tụ sau
được sử dụng:

Trong đó x là điểm trong không gian biểu diễn đối tượng đưa ra,
i
m
là trung bình của
cụm
i
C
(cả x và
i
m
là đa chiều). Hàm này cố gắng tạo ra k cụm phân biệt nhau tới mức

có thể. Thủ tục k trung bình được tổng kết ở hình bên dưới:
6

Thuật toán k means:
Đầu vào: Số cụm k, và một cơ sở dữ liệu chứa n đối tượng
Đầu ra: Một tập k cụm với trọng tâm của mỗi cụm
Thủ tục
1. Lựa chọn ngẫu nhiên k đối tượng là trọng tâm khởi tạo của k cụm
2. Lặp
2.1. Gán mỗi đối tượng vào cụm có trọng tâm giống nhất đối tượng nhất so
với các cụm khác
2.2. Cập nhật lại trọng tâm của các cụm, trong đó tọa độ của trọng tâm bằng
giá trị trung bình tọa độ các đối tượng trong cụm.
3. Cho đến khi giá trị hàm mục tiêu không thay đổi
Thuật toán cố gắng xác định k cụm mà tối thiểu hóa hàm mục tiêu đưa ra. Phương
thức này có khả năng mở rộng và hoạt động hiệu quả trong khi xử lý các tập dữ liệu lớn
bởi vì độ phức tạp tính toán của thuật toán là O (knt), trong đó n là tổng số đối tượng, k
là số cụm, và t là số lần lặp lại, thông thường
k
<<n và t<<n. Phương thức thường kết
thúc ở một sự tối thiểu cục bộ.

(a) (b) (c)
Hình 1.2: Quá trình phân cụm tập điểm thành 3 cụm theo k-means [1]
 Phương pháp k-medoids
Thuật toán k-means với đối tượng khác biệt (đối tượng có sự khác biệt so với
phần lớn các đối tượng trong tập) bởi vì một đối tượng với giá trị rất lớn có thể thay đổi
sự phân phối dữ liệu.
Làm thế nào thay đổi thuật toán để làm giảm bớt sự nhạy cảm như vậy? Thay cho
việc lấy giá trị trung bình của các đối tượng trong một phân cụm như điểm tham chiếu,

chúng ta có thể lấy những đối tượng thực để biểu diễn phân cụm, sử dụng một đối tượng
biểu diễn một phân cụm. Mỗi đối tượng đang tồn tại được phân cụm với đối tượng biểu
7

diễn mà giống nó nhất. Phương pháp phân cụm được thực hiện dựa trên nguyên lý tối
thiểu tổng của sự khác biệt giữa mỗi đối tượng và điểm tham chiếu của nó. Đó là, một
chuẩn lỗi-tuyệt đối (absolute-error criterion) được dùng như sau:



J
cp
j
k
j
opE ||
1

Trong đó E là tổng lỗi tuyệt đối của mọi đối tượng trong tập dữ liệu; p là điểm
trong không gian biểu diễn một đối tượng đưa ra trong phân cụm
j
C
; và o
j
là đối tượng
biểu diễn của
j
C
. Nói chung, trạng thái lặp đến tận khi mỗi đối tượng biểu diễn thực sự
là medoid, hoặc đối tượng nằm ở trung tâm

Xem xét trạng thái phân cụm k-medoid. Các đối tượng biểu diễn khởi tạo (hoặc
hạt giống) được chọn ngẫu nhiên.Việc thay thế các đối tượng biểu diễn bởi đối tượng
không biểu diễn còn lại sẽ được thực hiện nếu chất lượng của kết quả phân cụm được cải
tiến. Chất lượng này được đánh giá bằng cách sử dụng một hàm chi phí để đo lường sự
khác nhau trung bình giữa một đối tượng và đối tượng biểu diễn trong phân cụm của nó.
Để xác định một đối tượng không biểu diễn o
random
là sự thay thế tốt của đối tượng biểu
diễn o
j
hiện tại cần kiểm tra 4 trường hợp sau đối với mỗi đối tượng không biểu diễn p.
Xem mô tả trong hình 1.4
 Trường hợp 1: p hiện tại thuộc đối tượng biểu diễn o
j
. Nếu o
j
bị thay bằng
o
random
và p gần với một trong những đối tượng biểu diễn khác o
i
, với i

j thì
gán p thuộc o
i
.
 Trường hợp 2: p hiện tại thuộc đối tượng biểu diễn o
j
. Nếu o

j
bị thay bằng
o
random
và p gần nhất với o
random
thì gán p thuộc o
random
.
 Trường hơp 3: Nếu p hiện tại thuộc đối tượng biểu diễn o
i
(i

j). Nếu o
j
bị
thay bằng o
random
như một đối tượng biểu diễn và p gần nhất với o
i
, thì để
nguyên không thay đổi.
 Trường hợp 4: hiện tại p thuộc đối tượng biểu diễn o
i
(i

j). Nếu o
j
được thay
bằng o

random
và p gần o
random
nhất, p được gán thuộc o
random
.
8



Hình 1.3 trường hợp của hàm chi phí cho phân cụm k-medoid [1]
Hàm chi phí tính được tính dựa trên sự khác nhau trong giá trị lỗi-tuyệt đối nếu
một đối tượng biểu diễn hiện tại được thay bằng một đối tượng không biểu diễn. Giả sử
ban đầu cụm được biểu diễn bởi o
j
có tổng giá trị lỗi tuyệt đối là E
1,
sau đó cụm được
biểu diễn lại bởi giá trị o
random
có tổng giá trị lỗi tuyệt đối là E2. Khi đó tổng chi phí
chuyển đổi là|E
1
- E
2
|. Nếu tổng chi phí là âm, thì o
j
được thay thế hoặc đổi chỗ với
o
random

.
Nếu tổng chi phí dương, đối tượng biểu diễn hiện tại o
j
được chấp nhận, và không
có thay đổi trong việc lặp.
Thuật toán PAM (Partitioning Around Medoid) được chỉ ra bên dưới. Thuật toán
thực hiện phân n đối tượng làm k cụm, độ phức tạp là O(k(n-k)
2
). Đối với các giá trị lớn
của n và k, sự tính toán như vậy rất tốn chi phí.
Thuật toán k-medoid PAM, một trạng thái k-modoid cho cụm dựa trên medoid
hoặc các đối tượng trung tâm
Đầu vào: Số phân cụm k, tập dữ liệu D chứa n đối tượng.
Đầu ra: Một tập k phân cụm.
Thủ tục
1. Chọn ngẫu nhiên k (o
j
(j = 1 k)) đối tượng trong D như các đối tượng biểu
diễn khởi tạo hoặc điểm hạt giống
2. Lặp lại
9

2.1. Gán mỗi đối tượng còn lại cho phân cụm với đối tượng biểu diễn gần
nhất
2.2. Lựa chọn ngẫu nhiên một đối tượng không biểu diễn, o
random
.
2.3. Tính tổng chi phí, S = Ej-E
random
, của việc hoán chuyển đối tượng biểu

diễn, o
j
với o
random
.
2.4. Nếu S<0 thì hoán đổi o
j
và o
ramdon
để hình thành tập mới k đối tượng
biểu diễn.
3. Tới tận khi không có sự thay đổi thì kết thúc.
Phương thức k-medoid đáng tin cậy hơn k-trung bình bởi vì một medoid bị tác
động bởi các nhân tố bên ngoài hoặc các giá trị rất lớn ít hơn k trung bình.

Hình 1.4: Quá trình phân cụm tập điểm thành 3 cụm theo k- medoids [1]

 Phương pháp phân cụm trong cơ sở dữ liệu lớn CLARANS
Phương pháp k-medoid chỉ thích hợp với việc sử dụng cho tập dữ liệu nhỏ. Trong
cơ sở dữ liệu lớn, người ta sử dụng một phương pháp dựa trên mẫu, gọi là CLARA
(Clustering Large Application).
Ý tưởng của phương pháp này là thay cho việc dùng toàn bộ tập dữ liệu trong sự
phân cụm, một phần nhỏ của dữ liệu được chọn như đại diện cho tập dữ liệu. Các
medoid được chọn từ tập dữ liệu này sử dụng PAM. Nếu mẫu được chọn theo cách ngẫu
nhiên, nó gần như đại diện cho tập dữ liệu gốc. Các đối tượng biểu diễn được chọn sẽ
giống như trong toàn bộ cơ sở dữ liệu. CLARA dùng nhiều mẫu trong tập dữ liệu, sử
dụng PAM trên mỗi mẫu và trả lại phân cụm tốt nhất của nó. CLARA có thể làm việc
với tập dữ liệu lớn hơn PAM. Độ phức tạp của mỗi vòng lặp là O(ks
2


+k(n-k)), trong dó s
là kích thước mẫu, k là số phân cụm, và n là tổng số đối tượng.
10

Độ chính xác của thuật toán CLARA phụ thuộc vào kích thước mẫu. Chú ý rằng
PAM tìm kiếm k điểm trung tâm trong tập dữ liệu đưa ra, trong khi đó CLARA tìm kiếm
k điểm trung tâm trong tập mẫu được lựa chọn. CLARA không thể tìm được sự phân
cụm chính xác nhất nếu không tìm được tập mẫu đại diện chính xác. Ví dụ, O
i
là điểm
trung tâm tốt nhất của một trong k cụm nhưng lại không được lựa chọn trong mẫu,
CLARA sẽ không bao giờ tìm được cách phân cụm một cách chính xác.
Để cải tiến chất lượng của CLARA, một thuật toán phân cụm khác là
CLARANS (Clustering Large Applications based upon RANdomized Search)
được phát triển và giới thiệu bởi (Ng và Han 1994). CLARANS cũng sử dụng thuật toán
k-medoids áp dụng PAM kết hợp với kỹ thuật lấy mẫu. Tuy nhiên, không giống như
CLARA, CLARANS không giới hạn các mẫu trong mỗi lần lặp. Trong khi CLARA cố
định các mẫu tại tất cả các bước trong quá trình phân cụm, CLARANS lấy ra các mẫu
ngẫu nhiên trong từng bước.
1.2.2 Các phương pháp phân cấp
Phương pháp phân cấp là sự phân chia các đối tượng dữ liệu đưa ra theo các cấp.
Phương pháp phân cấp có thể được thực hiện theo các cách tích tụ hoặc phân rã
(agglomerative or divisive). Hướng tích tụ (agglomerative), còn gọi là hướng từ dưới lên
(bottom up) bắt đầu với mỗi đối tượng tạo thành một nhóm riêng rẽ. Nó hòa nhập các đối
tượng hoặc nhóm bên cạnh (gần nhau) thành một, tới tận khi mọi nhóm được hòa nhập
thành một (mức cao nhất của sự phân cấp), hoặc đến tận khi bắt gặp điều kiện kết thúc.
Hướng phân rã (divisive), còn gọi là từ trên xuống (top down), bắt đầu với mọi đối tượng
trong cùng cụm. Trong mỗi vòng lặp, một đoạn được phân chia thành những đoạn nhỏ
hơn, tới tận khi mỗi đối tượng tương ứng một đoạn, hoặc tận khi gặp điều kiện kết thúc.
Phương pháp phân cấp có nhược điểm là một khi một bước (hòa nhập hoặc phân

chia) được thực hiện, nó có thể không bao giờ thay đổi. Sự cứng nhắc này là chìa khóa
đối với sự thành công của nó bởi vì nó dẫn đến chi phí tính toán nhỏ mà không lo lắng về
một số sự tổ hợp của các lựa chọn khác nhau, đồng thời cũng là vấn đề chính bởi vì nó
không thể sửa các quyết định sai.
 Phân cụm phân cấp dạng tích lũy và phân chia (agglomerative and divisive
hierarchical Clustering)
Phân cụm phân cấp dạng tích lũy: chiến lược từ dưới lên này bắt đầu bằng việc
đặt mỗi đối tượng trong phân cụm của riêng nó và hòa nhập các phân cụm nhỏ thành
những phân cụm lớn hơn đến tận khi mọi đối tượng trong một phân cụm đơn hoặc đến
khi điều kiện kết thúc được thỏa mãn. Hầu hết các phương thức phân cụm phân cấp
thuộc loại này.
11

Phân cụm phân cấp phân chia: chiến lược này hướng từ trên xuống ngược với
chiến lược phân cụm tích lũy dần. Nó phân chia cụm thành những cụm nhỏ hơn đến khi
mỗi đối tượng tạo thành một cụm hoặc bắt gặp điều kiện kết thúc.

Hình 1.5: phân cụm phân cấp dạng tích lũy và phân chia trên các đối tượng dữ liệu {a,b,c,d,e}
[1]
Trong cả hai loại phân cụm phân cấp này, người dùng có thể xác định số cụm
mong muốn và điêu kiện kết thúc. Bốn độ đo khoảng cách sử dụng rộng rãi giữa các cụm
được chỉ ra bên dưới, trong đó |p-p‟| là khoảng cách giữa hai đối tượng hoặc điểm p và
p’, và m
i
là trung bình của cụm C
i
và n
i
là số đối tượng trong C
i

.

Khi thuật toán sử dụng khoảng cách nhỏ nhất d
min
(C
i
,C
j
) để đo khoảng cách giữa
các phân cụm, nó được gọi là k-nearest neighbor. Khi thuật toán sử dụng khoảng cách xa
nhất d
max
(C
i
,C
j
), thuật toán được gọi là thuật toán phân cụm farthest-neighbor.
 Phương pháp BIRCH (Balanced iterative Reducing and Clustering Using
Hierarchies).
BIRCH được thiết kế dành cho việc phân cụm lượng lớn dữ liệu số bằng cách tích
hợp phân cụm phân cấp (ở trạng thái khởi đầu phân cụm vi mô) và các phương pháp
phân cụm khác như phân cụm lặp (ở trạng thái sau phân cụm vĩ mô). Nó vượt qua hai sự
12

khó khăn của phương thức phân cụm tích lũy: (1) tính mở rộng và (2) khả năng không
thể quay lại bước trước.
BIRCH đưa ra hai khái niệm: đặc tính phân cụm và cây đặc tính phân cụm (CF
tree), được sử dụng để tổng kết các sự thể hiện phân cụm. Những cấu trúc này giúp
phương thức phân cụm đạt được tốc độ tốt và khả năng mở rộng trong cơ sở dữ liệu lớn,
hơn nữa làm tăng tính hiệu quả của phân cụm tăng dần và tính linh động của đối tượng

đầu vào.
Hãy xem xét sâu hơn các cấu trúc nhắc đến ở trên. Xem xét n đối tượng dữ liệu
hoặc điểm có d chiều trong một cụm, chúng ta có thể xác định trung tâm x
0
, bán kính R,
và đường kính D của cụm như sau:

Trong đó R là khoảng cách trung bình từ các đối tượng thành viên tới trung tâm,
và D là khoảng cách trung bình giữa các cặp trong cụm. Cả R và D phản ánh tính gần gũi
của cụm xung quanh trung tâm. Một đặc tính phân cụm (CF) là một vector 3 chiều tổng
hợp thông tin về các cụm của đối tượng. Xem xét n đối tượng hoặc điểm có d chiều trong
một phân cụm, {x
i
}, thì CF của cụm được định nghĩa là:
},,{ SSLSnCF 

Trong đó n là số lượng điểm của phân cụm, LS là tổng tuyến tính của n điểm
(nghĩa là, LS=


n
i
i
x
1
), và SS là tổng bình phương của các điểm (nghĩa là,


n
i

i
x
1
2
)


Hình 1.6: Một cây cấu trúc CF [1]
13

BIRCH áp dụng một kĩ thuật nhiều pha: Thực hiện quét một lần tập dữ liệu tạo ra
một phân cụm tốt ban đầu, và các lần quét sau đó được dùng để cải tiến chất lượng. Hai
pha chính là:
 Pha 1: BIRCH quét cơ sở dữ liệu để xây dựng một cây CF bộ nhớ ban đầu, có
thể được xem như là một sự nén đa cấp của dữ liệu để cố gắng bảo vệ cấu trúc
phân cụm có sẵn của dữ liệu
 Pha 2: BIRCH áp dụng một thuật toán phân cụm để phân cụm các node lá của
cây CF, cố gắng loại bỏ các phân cụm thừa và nhóm các phân cụm thành một
phân cụm lớn hơn.
CF có 2 tham số: tham số nhánh (branching factor) B và ngưỡng T. B quy định số
con lớn nhất mà một nút không phải nút lá có thể có, và T xác định đường kính lớn nhất
của một phân cụm con.
Ở bước 1, khi một đối tượng được thêm vào một cụm, nếu đường kính của cụm
này lớn hơn giá trị ngưỡng thì các cụm sẽ bị phân chia lại. Sau quá trình phân chia cụm
lại ta được một tập các cụm mới. Ở bước 2, có thể áp dụng một thuật toán phân cụm bất
kì nào để thực hiện việc phân tách hoặc hợp nhất các cụm lại.
Thuật toán BIRCH có độ phức tạp tính toán là O (n), trong đó n là số lượng đối
tượng được phân cụm.
 Phương pháp ROCK (Robust clustering using links).
ROCK là một thuật toán phân cụm phân cấp quan tâm đến khái niệm links (số

lượng hàng xóm chung của hai đối tượng) cho dữ liệu với các thuộc tính phân loại. Các
thuật toán phân cụm truyền thống cho dữ liệu phân cụm với thuộc tính Boolean và phân
loại sử dụng các hàm khoảng cách .Tuy nhiên, thí nghiệm chỉ ra rằng các độ đo khoảng
cách như vậy không thể dẫn đến các phân cụm chất lượng cao khi phân cụm dữ liệu phân
loại. Hơn nữa, hầu hết các thuật toán phân cụm chỉ đánh giá sự giống nhau giữa các điểm
khi phân cụm. Đó là, ở mỗi bước, các điểm giống nhau nhất được hòa nhập vào trong
một cụm duy nhất, hướng “cục bộ” này có thể dẫn tới lỗi. Ví dụ, hai phân cụm tách biệt
có thể có ít điểm hoặc các thành phần bên ngoài gần nhau, và do đó, dựa trên sự giống
nhau giữa các điểm để tạo các quyết định phân cụm có thể dẫn đến việc hai phân cụm bị
hòa nhập. ROCK quan tâm đến hướng toàn cục hơn để phân cụm bằng việc xem xét
quan hệ láng riềng của các cặp điểm riêng rẽ. Nếu hai điểm giống nhau có cùng quan hệ
hàng xóm, chúng có thể thuộc cùng cụm do đó có thể được hòa nhập.
Hình thức hơn nữa, hai điểm, p
i
và p
j
, là hàng xóm nếu sim (p
i
, pj)


, trong đó
sim là một hàm thể hiện sự giống nhau và

là một ngưỡng do người dùng xác định.
14

Chúng ta có thể chọn sim là một độ đo dạng khoảng cách hoặc thậm chí không phải độ
do dạng khoảng cách mà được chuẩn hóa để những giá trị của nó nằm trong khoảng 0 và
1, với những giá trị lớn hơn chỉ ra rằng những điểm này là giống nhau hơn. Số lượng

links giữa p
i
và p
j
được xác định như số lượng hàng xóm giữa p
i
và p
j
. Nếu số lượng
links giữa hai điểm lớn, có khả năng cao là hai điểm đó cùng thuộc cụm. Bằng việc xem
xét các điểm dữ liệu có quan hệ hàng xóm giữa cặp điểm riêng rẽ, ROCK đáng tin cậy
hơn các phương pháp phân cụm chuẩn chỉ tập trung vào sự giống nhau của các điểm.
 Phương pháp Chameleon.
Chameleon là một thuật toán phân cụm phân cấp sử dụng mô hình động để xác
định sự giống nhau giữa các cặp cụm [1]. Nó dựa trên việc xem xét điểm yếu hai thuật
toán phân cụm phân cấp là ROCK và CURE. ROCK liên quan đến lược đồ nhấn mạnh
sự tương tác cụm trong khi bỏ qua thông tin liên quan sự giống nhau cụm. CURE xem
xét sự giống nhau cụm và bỏ qua tính tương tác cụm. Trong Chameleon, sự giống nhau
cụm được đánh giá dựa trên việc các đối tượng trong cụm kết nối với nhau thế nào và
quan hệ gần gũi của các cụm. Do đó, hai cụm được hòa nhập nếu quan hệ tương tác giữa
chúng cao và chúng gần nhau. Do đó, Chameleon không dựa trên mô hình tĩnh và phụ
thuộc người dùng và có thể điều chỉnh tự động đối với các đặc tính bên trong của các
cụm được hòa nhập. Tiến trình hòa nhập làm tăng khả năng khám phá của các phân cụm
tự nhiên và áp dụng các kiểu của dữ liệu cũng như một hàm thể hiện sự giống nhau có
thể được xác định.
Chameleon làm việc thế nào? Hướng chính của Chameleon được đưa ra hình 1.7.
Chameleon sử dụng hướng đồ thị k-nearest neighbor để xây dựng một đồ thị thưa, trong
đó mỗi đỉnh của đồ thị biểu diễn một đối tượng dữ liệu, và tồn tại một cạnh giữa hai đỉnh
(hai đối tượng) nếu một đối tượng thuộc tập k đối tượng giống nhất của đối tượng còn
lại. Cạnh này được đánh trọng số để phản ánh sự giống nhau giữa các đối tượng.

Chameleon sử dụng một thuật toán cụm đồ thị để cụm đồ thị k nearest neighbor thành
một số lượng lớn của các phân cụm nhỏ. Nó sau đó sử dụng thuật toán phân cụm phân
cấp dạng tích lũy để hòa nhập các phân cụm con dựa trên sự giống nhau của chúng. Để
xác định các cặp phân cụm con giống nhau nhất, nó tính đến cả sự tương tác kết nối cũng
như tính gần gũi của các cụm.

15

Hình 1.7: Phương pháp Chameleon
Thuật toán cụm đồ thị cụm đồ thị k-nearest neighbor để tối thiểu hóa sự giảm bớt
cạnh. Đó là, một phân cụm C được phân cụm thành hai phân cụm nhỏ C
i
và C
j
,để tối
thiểu hóa trọng số các cạnh mà C được phân chia thành C
i
và C
j
. Sự giảm bớt cạnh được
chỉ ra bằng EC(C
i
,C
j)
và lượng giá tính kết nối tương tác giữa các phân cụm C
i
và C
j
.
Chameleon xác định tính giống nhau giữa hai cụm C

i
và C
j
dựa vào hai tham số
tính kết nối tương tác quan hệ RI(C
i
, C
j
) và tính gần gũi RC(C
i
, C
j
).


Trong đó
},{ CjCi
SEC
là giá trị trung bình trọng số của các cạnh nối các đỉnh trong
C
i
và các đỉnh trong C
j
, và
i
C
SEC
(hoặc
Cj
SEC

) là giá trị trung bình của các cạnh cụm C
i

(hoặc C
j
).
1.2.3 Phương pháp phân cụm dựa trên mật độ
Hầu hết các phương pháp phân cụm các đối tượng dựa trên khoảng các giữa các
đối tượng. Những phương pháp như vậy có thể chỉ tìm thấy các cụm dạng hình cầu và
gặp khó khăn khi tìm kiếm các cụm có hình dạng bất kì. Các phương pháp cụm được
phát triển dựa trên khái niệm mật độ. Ý tưởng chung là tiếp tục làm gia tăng cụm đưa ra
dựa vào mật độ (số lượng đối tượng hoặc các điểm dữ liệu) trong “khoảng” vượt ra ngoài
ngưỡng, nghĩa là, đối với mỗi điểm dữ liệu trong một cụm được đưa ra, hàng xóm
(neighbourhood) trong một bán kính đưa ra phải chứa ít nhất một số tối thiểu các điểm.
Phương pháp như vậy có thể được sử dụng để lọc ra các nhiễu, và khám phá các cụm có
hình dạng bất kì.
 Phương pháp DBSCAN (Density-Based Spatial Clustering of Application witch
Noise).
Đây là một thuật toán phân cụm dựa trên mật độ. Thuật toán xây dựng các vùng
với mật độ lớn thích hợp vào trong các phân cụm và khám phá các phân cụm có hình
dạng khác nhau trong cơ sở dữ liệu không gian với các nhiễu. Nó định nghĩa một phân
cụm như một tập tối đa của các điểm phụ thuộc mật độ.
16

Ý tưởng chính của phân cụm dựa trên mật độ là đối với mỗi đối tượng thuộc
nhóm vùng lân cận trong bán kính

được gọi là

-hàng xóm của đối tượng (-

neighborhood) có chứa ít nhất MinPts đối tượng.
 Nếu

-hàng xóm của một đối tượng chứa ít nhất một số tối thiểu MinPts các
đối tượng, thì đối tượng đó gọi là đối tượng trung tâm (core object).
 Xem xét một tập các đối tượng D, chúng ta nói rằng một đối tượng p thuộc
trong phạm vi mật độ trực tiếp của đối tượng q nếu p nằm trong

-hàng xóm
của đối tượng q và q là đối tượng trung tâm.
 Một đối tượng p nằm trong phạm vi mật độ của đối tượng q đối với

và
MinPts trong một tập các đối tượng D, nếu có một chuỗi các đối tượng p
1
,…,
pn trong đó p
1
=q và p
n
=p và p
i+1
nằm trong phạm vi mật độ trực tiếp của p
i
đối
với

và MinPts, với 1

i


n, pi

D.
 Một đối tượng p nằm trong phạm vi mật độ liên kết của đối tượng q đối với


và MinPts trong một tập các đối tượng D, nếu có một đối tượng o

D mà cả
p và q đều nằm trong phạm vi mật độ của o với

và MinPts.


Hình 1.8 Phạm vi mật độ và sự liên kết mật độ trong phân cụm dựa trên mật độ [1]
 Trong hình trên, các điểm m, p, o là đối tượng trung tâm bởi vi mỗi đối tượng
trong phạm vi

đều có ít nhất ba đối tượng khác.
 q nằm trong phạm vi trực tiếp của m, m nằm trong phạm vi trực tiếp của p và
ngược lại
17

 q nằm trong phạm vi gián tiếp của p, tuy nhiên p không nằm trong phạm vi
của q vì q không phải là đối tượng trung tâm.
 o, r và s đều có liên kết mật độ.
Một phân cụm dựa trên mật độ là một tập các đối tượng có liên kết mật độ được
làm tối đa hóa đối với phạm vi liên kết mật độ. Những đối tượng không thuộc cụm nào
xem như là nhiễu.

DBSCAN sẽ tìm trong các cụm bằng cách kiểm tra

-hàng xóm cho mỗi điểm
trong cơ sở dữ liệu. Nếu

-hàng xóm của một điểm p chứa nhiều hơn MinPts điểm, một
cụm mới với p là đối tượng trung tâm được tạo. DBSCAN tập hợp các đối tượng trong
phạm vi mật độ trực tiếp cho những đối tượng trung tâm, có thể thực hiện việc hòa nhập
một số ít cụm trong phạm vi mật độ. Tiến trình kết thúc khi không có điểm mới nào có
thể thêm vào bất kì cụm nào.
 Phương pháp DENCLUE (Density Based Clustering)
DENCLUE là một phương pháp phân cụm dựa trên một tập các hàm phương
pháp mật độ. Phương pháp được xây dựng trên những ý tưởng sau: (1) sự tác động của
mỗi điểm dữ liệu có thể được mô hình hóa hình thức sử dụng một hàm toán học, gọi là
hàm tác động (ingluence function), mô tả tác động của một điểm dữ liệu nằm trong quan
hệ hàng xóm của nó; (2) toàn thể mật độ của không gian dữ liệu có thể được mô hình hóa
như tổng của hàm tác động cho tất cả các điểm dữ liệu; và (3) các phân cụm có thể được
xác định bằng cách xác định các density attractor, trong đó các density attractor là các
cực đại cục bộ của toàn bộ hàm mật độ.
Giả sử x và y là các đối tượng hoặc điểm trong F
d
, một không gian đầu vào d
chiều. Hàm tác động của điểm dữ liệu y trên x là một hàm,


0
: RFf
dy
B
, được định

nghĩa như sau:
),()( yxfxf
B
y
B


Hàm này phản ánh tác động của y lên x. Theo nguyên tắc, hàm tác động có thể là
một hàm ngẫu nhiên mà có thể được xác định bởi khoảng cách giữa hai điểm trong một
quan hệ hàng xóm. Hàm khoảng cách d(x,y), nên là tương phản và đối xứng, như là hàm
khoảng cách Euclid. Nó được sử dụng để tính toán một hàm dạng:


18

hoặc dùng để tính hàm tác động Gaussian

Hàm mật độ ở một đối tượng hoặc một điểm x

F
d
được định nghĩa như một tổng
của các hàm tác động của mọi điểm dữ liệu. Đó là, tổng tác động lên x của tất cả mọi
điểm dữ liệu. Xem xét n đối tượng điểm, D={x
1
… xn}
d
F
, hàm mật độ ở x là:


Ví dụ, hàm mật độ có kết quả từ hàm tác động Gaussian là:

Hình 1.9 chỉ ra một tập dữ liệu 2-D cùng với toàn bộ hàm mật độ cho hàm tương
tác square wave và Gaussian
Từ hàm mật độ, chúng ta có thể xác định gradient của hàm và density attractor,
cực trị địa phương của toàn bộ hàm mật độ. Một điểm x được nói là bị thu hút mật độ đối
với một density attractor x
*
nếu có một tập các điểm x
0
, x
1
… x
k
mà x
0
=x, x
k
=x
*
và
gradient của x
i-1
nằm trong hướng của x
i
trong đó 0<i<k. Một cách trực quan, một
density attractor tác động lên nhiều điểm khác. Nói chung, những điểm bị thu hút mật độ
với x
*
sẽ tạo thành một cụm.


Hình 1.9: Phân cụm dựa trên phương pháp mật độ [1]